Source code

001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2018 the original author or authors.
004//
005// This library is free software; you can redistribute it and/or
006// modify it under the terms of the GNU Lesser General Public
007// License as published by the Free Software Foundation; either
008// version 2.1 of the License, or (at your option) any later version.
009//
010// This library is distributed in the hope that it will be useful,
011// but WITHOUT ANY WARRANTY; without even the implied warranty of
012// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013// Lesser General Public License for more details.
014//
015// You should have received a copy of the GNU Lesser General Public
016// License along with this library; if not, write to the Free Software
017// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
018////////////////////////////////////////////////////////////////////////////////
019
020package com.puppycrawl.tools.checkstyle.checks.metrics;
021
022import java.math.BigInteger;
023import java.util.ArrayDeque;
024import java.util.Deque;
025
026import com.puppycrawl.tools.checkstyle.FileStatefulCheck;
027import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
028import com.puppycrawl.tools.checkstyle.api.DetailAST;
029import com.puppycrawl.tools.checkstyle.api.TokenTypes;
030
031/**
032 * Checks the npath complexity against a specified limit (default = 200).
033 * The npath metric computes the number of possible execution paths
034 * through a function. Similar to the cyclomatic complexity but also
035 * takes into account the nesting of conditional statements and
036 * multi-part boolean expressions.
037 *
038 * @author <a href="mailto:simon@redhillconsulting.com.au">Simon Harris</a>
039 * @author o_sukhodolsky
040 */
041// -@cs[AbbreviationAsWordInName] Can't change check name
042@FileStatefulCheck
043public final class NPathComplexityCheck extends AbstractCheck {
044
045    /**
046     * A key is pointing to the warning message text in "messages.properties"
047     * file.
048     */
049    public static final String MSG_KEY = "npathComplexity";
050
051    /** Default allowed complexity. */
052    private static final int DEFAULT_MAX = 200;
053
054    /** The initial current value. */
055    private static final BigInteger INITIAL_VALUE = BigInteger.ZERO;
056
057    /**
058     * Stack of NP values for ranges.
059     */
060    private final Deque<BigInteger> rangeValues = new ArrayDeque<>();
061
062    /** Stack of NP values for expressions. */
063    private final Deque<Integer> expressionValues = new ArrayDeque<>();
064
065    /** Stack of belongs to range values for question operator. */
066    private final Deque<Boolean> isAfterValues = new ArrayDeque<>();
067
068    /**
069     * Range of the last processed expression. Used for checking that ternary operation
070     * which is a part of expression won't be processed for second time.
071     */
072    private final TokenEnd processingTokenEnd = new TokenEnd();
073
074    /** NP value for current range. */
075    private BigInteger currentRangeValue = INITIAL_VALUE;
076
077    /** Threshold to report error for. */
078    private int max = DEFAULT_MAX;
079
080    /** True, when branch is visited, but not leaved. */
081    private boolean branchVisited;
082
083    /**
084     * Set the maximum threshold allowed.
085     * @param max the maximum threshold
086     */
087    public void setMax(int max) {
088        this.max = max;
089    }
090
091    @Override
092    public int[] getDefaultTokens() {
093        return getRequiredTokens();
094    }
095
096    @Override
097    public int[] getAcceptableTokens() {
098        return getRequiredTokens();
099    }
100
101    @Override
102    public int[] getRequiredTokens() {
103        return new int[] {
104            TokenTypes.CTOR_DEF,
105            TokenTypes.METHOD_DEF,
106            TokenTypes.STATIC_INIT,
107            TokenTypes.INSTANCE_INIT,
108            TokenTypes.LITERAL_WHILE,
109            TokenTypes.LITERAL_DO,
110            TokenTypes.LITERAL_FOR,
111            TokenTypes.LITERAL_IF,
112            TokenTypes.LITERAL_ELSE,
113            TokenTypes.LITERAL_SWITCH,
114            TokenTypes.CASE_GROUP,
115            TokenTypes.LITERAL_TRY,
116            TokenTypes.LITERAL_CATCH,
117            TokenTypes.QUESTION,
118            TokenTypes.LITERAL_RETURN,
119            TokenTypes.LITERAL_DEFAULT,
120        };
121    }
122
123    @Override
124    public void beginTree(DetailAST rootAST) {
125        rangeValues.clear();
126        expressionValues.clear();
127        isAfterValues.clear();
128        processingTokenEnd.reset();
129        currentRangeValue = INITIAL_VALUE;
130        branchVisited = false;
131    }
132
133    @Override
134    public void visitToken(DetailAST ast) {
135        switch (ast.getType()) {
136            case TokenTypes.LITERAL_IF:
137            case TokenTypes.LITERAL_SWITCH:
138            case TokenTypes.LITERAL_WHILE:
139            case TokenTypes.LITERAL_DO:
140            case TokenTypes.LITERAL_FOR:
141                visitConditional(ast, 1);
142                break;
143            case TokenTypes.QUESTION:
144                visitUnitaryOperator(ast, 2);
145                break;
146            case TokenTypes.LITERAL_RETURN:
147                visitUnitaryOperator(ast, 0);
148                break;
149            case TokenTypes.CASE_GROUP:
150                final int caseNumber = countCaseTokens(ast);
151                branchVisited = true;
152                pushValue(caseNumber);
153                break;
154            case TokenTypes.LITERAL_ELSE:
155                branchVisited = true;
156                if (currentRangeValue.equals(BigInteger.ZERO)) {
157                    currentRangeValue = BigInteger.ONE;
158                }
159                pushValue(0);
160                break;
161            case TokenTypes.LITERAL_TRY:
162            case TokenTypes.LITERAL_CATCH:
163            case TokenTypes.LITERAL_DEFAULT:
164                pushValue(1);
165                break;
166            case TokenTypes.CTOR_DEF:
167            case TokenTypes.METHOD_DEF:
168            case TokenTypes.INSTANCE_INIT:
169            case TokenTypes.STATIC_INIT:
170                pushValue(0);
171                break;
172            default:
173                break;
174        }
175    }
176
177    @Override
178    public void leaveToken(DetailAST ast) {
179        switch (ast.getType()) {
180            case TokenTypes.LITERAL_WHILE:
181            case TokenTypes.LITERAL_DO:
182            case TokenTypes.LITERAL_FOR:
183            case TokenTypes.LITERAL_IF:
184            case TokenTypes.LITERAL_SWITCH:
185                leaveConditional();
186                break;
187            case TokenTypes.LITERAL_TRY:
188                leaveMultiplyingConditional();
189                break;
190            case TokenTypes.LITERAL_RETURN:
191            case TokenTypes.QUESTION:
192                leaveUnitaryOperator();
193                break;
194            case TokenTypes.LITERAL_CATCH:
195                leaveAddingConditional();
196                break;
197            case TokenTypes.LITERAL_DEFAULT:
198                leaveBranch();
199                break;
200            case TokenTypes.LITERAL_ELSE:
201            case TokenTypes.CASE_GROUP:
202                leaveBranch();
203                branchVisited = false;
204                break;
205            case TokenTypes.CTOR_DEF:
206            case TokenTypes.METHOD_DEF:
207            case TokenTypes.INSTANCE_INIT:
208            case TokenTypes.STATIC_INIT:
209                leaveMethodDef(ast);
210                break;
211            default:
212                break;
213        }
214    }
215
216    /**
217     * Visits if, while, do-while, for and switch tokens - all of them have expression in
218     * parentheses which is used for calculation.
219     * @param ast visited token.
220     * @param basicBranchingFactor default number of branches added.
221     */
222    private void visitConditional(DetailAST ast, int basicBranchingFactor) {
223        int expressionValue = basicBranchingFactor;
224        DetailAST bracketed;
225        for (bracketed = ast.findFirstToken(TokenTypes.LPAREN).getNextSibling();
226                bracketed.getType() != TokenTypes.RPAREN;
227                bracketed = bracketed.getNextSibling()) {
228            expressionValue += countConditionalOperators(bracketed);
229        }
230        processingTokenEnd.setToken(bracketed);
231        pushValue(expressionValue);
232    }
233
234    /**
235     * Visits ternary operator (?:) and return tokens. They differ from those processed by
236     * visitConditional method in that their expression isn't bracketed.
237     * @param ast visited token.
238     * @param basicBranchingFactor number of branches inherently added by this token.
239     */
240    private void visitUnitaryOperator(DetailAST ast, int basicBranchingFactor) {
241        final boolean isAfter = processingTokenEnd.isAfter(ast);
242        isAfterValues.push(isAfter);
243        if (!isAfter) {
244            processingTokenEnd.setToken(getLastToken(ast));
245            final int expressionValue = basicBranchingFactor + countConditionalOperators(ast);
246            pushValue(expressionValue);
247        }
248    }
249
250    /**
251     * Leaves ternary operator (?:) and return tokens.
252     */
253    private void leaveUnitaryOperator() {
254        if (!isAfterValues.pop()) {
255            final Values valuePair = popValue();
256            BigInteger basicRangeValue = valuePair.getRangeValue();
257            BigInteger expressionValue = valuePair.getExpressionValue();
258            if (expressionValue.equals(BigInteger.ZERO)) {
259                expressionValue = BigInteger.ONE;
260            }
261            if (basicRangeValue.equals(BigInteger.ZERO)) {
262                basicRangeValue = BigInteger.ONE;
263            }
264            currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
265        }
266    }
267
268    /** Leaves while, do, for, if, ternary (?::), return or switch. */
269    private void leaveConditional() {
270        final Values valuePair = popValue();
271        final BigInteger expressionValue = valuePair.getExpressionValue();
272        BigInteger basicRangeValue = valuePair.getRangeValue();
273        if (currentRangeValue.equals(BigInteger.ZERO)) {
274            currentRangeValue = BigInteger.ONE;
275        }
276        if (basicRangeValue.equals(BigInteger.ZERO)) {
277            basicRangeValue = BigInteger.ONE;
278        }
279        currentRangeValue = currentRangeValue.add(expressionValue).multiply(basicRangeValue);
280    }
281
282    /** Leaves else, default or case group tokens. */
283    private void leaveBranch() {
284        final Values valuePair = popValue();
285        final BigInteger basicRangeValue = valuePair.getRangeValue();
286        final BigInteger expressionValue = valuePair.getExpressionValue();
287        if (branchVisited && currentRangeValue.equals(BigInteger.ZERO)) {
288            currentRangeValue = BigInteger.ONE;
289        }
290        currentRangeValue = currentRangeValue.subtract(BigInteger.ONE)
291                .add(basicRangeValue)
292                .add(expressionValue);
293    }
294
295    /**
296     * Process the end of a method definition.
297     * @param ast the token type representing the method definition
298     */
299    private void leaveMethodDef(DetailAST ast) {
300        final BigInteger bigIntegerMax = BigInteger.valueOf(max);
301        if (currentRangeValue.compareTo(bigIntegerMax) > 0) {
302            log(ast, MSG_KEY, currentRangeValue, bigIntegerMax);
303        }
304        popValue();
305        currentRangeValue = INITIAL_VALUE;
306    }
307
308    /** Leaves catch. */
309    private void leaveAddingConditional() {
310        currentRangeValue = currentRangeValue.add(popValue().getRangeValue().add(BigInteger.ONE));
311    }
312
313    /**
314     * Pushes the current range value on the range value stack. Pushes this token expression value
315     * on the expression value stack.
316     * @param expressionValue value of expression calculated for current token.
317     */
318    private void pushValue(Integer expressionValue) {
319        rangeValues.push(currentRangeValue);
320        expressionValues.push(expressionValue);
321        currentRangeValue = INITIAL_VALUE;
322    }
323
324    /**
325     * Pops values from both stack of expression values and stack of range values.
326     * @return pair of head values from both of the stacks.
327     */
328    private Values popValue() {
329        final int expressionValue = expressionValues.pop();
330        return new Values(rangeValues.pop(), BigInteger.valueOf(expressionValue));
331    }
332
333    /** Leaves try. */
334    private void leaveMultiplyingConditional() {
335        currentRangeValue = currentRangeValue.add(BigInteger.ONE)
336                .multiply(popValue().getRangeValue().add(BigInteger.ONE));
337    }
338
339    /**
340     * Calculates number of conditional operators, including inline ternary operator, for a token.
341     * @param ast inspected token.
342     * @return number of conditional operators.
343     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.23">
344     * Java Language Specification, &sect;15.23</a>
345     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.24">
346     * Java Language Specification, &sect;15.24</a>
347     * @see <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.25">
348     * Java Language Specification, &sect;15.25</a>
349     */
350    private static int countConditionalOperators(DetailAST ast) {
351        int number = 0;
352        for (DetailAST child = ast.getFirstChild(); child != null;
353                child = child.getNextSibling()) {
354            final int type = child.getType();
355            if (type == TokenTypes.LOR || type == TokenTypes.LAND) {
356                number++;
357            }
358            else if (type == TokenTypes.QUESTION) {
359                number += 2;
360            }
361            number += countConditionalOperators(child);
362        }
363        return number;
364    }
365
366    /**
367     * Finds a leaf, which is the most distant from the root.
368     * @param ast the root of tree.
369     * @return the leaf.
370     */
371    private static DetailAST getLastToken(DetailAST ast) {
372        final DetailAST lastChild = ast.getLastChild();
373        final DetailAST result;
374        if (lastChild.getFirstChild() == null) {
375            result = lastChild;
376        }
377        else {
378            result = getLastToken(lastChild);
379        }
380        return result;
381    }
382
383    /**
384     * Counts number of case tokens subject to a case group token.
385     * @param ast case group token.
386     * @return number of case tokens.
387     */
388    private static int countCaseTokens(DetailAST ast) {
389        int counter = 0;
390        for (DetailAST iterator = ast.getFirstChild(); iterator != null;
391                iterator = iterator.getNextSibling()) {
392            if (iterator.getType() == TokenTypes.LITERAL_CASE) {
393                counter++;
394            }
395        }
396        return counter;
397    }
398
399    /**
400     * Coordinates of token end. Used to prevent inline ternary
401     * operator from being processed twice.
402     */
403    private static class TokenEnd {
404
405        /** End line of token. */
406        private int endLineNo;
407
408        /** End column of token. */
409        private int endColumnNo;
410
411        /**
412         * Sets end coordinates from given token.
413         * @param endToken token.
414         */
415        public void setToken(DetailAST endToken) {
416            if (!isAfter(endToken)) {
417                endLineNo = endToken.getLineNo();
418                endColumnNo = endToken.getColumnNo();
419            }
420        }
421
422        /** Sets end token coordinates to the start of the file. */
423        public void reset() {
424            endLineNo = 0;
425            endColumnNo = 0;
426        }
427
428        /**
429         * Checks if saved coordinates located after given token.
430         * @param ast given token.
431         * @return true, if saved coordinates located after given token.
432         */
433        public boolean isAfter(DetailAST ast) {
434            final int lineNo = ast.getLineNo();
435            final int columnNo = ast.getColumnNo();
436            boolean isAfter = true;
437            if (lineNo > endLineNo
438                    || lineNo == endLineNo
439                    && columnNo > endColumnNo) {
440                isAfter = false;
441            }
442            return isAfter;
443        }
444
445    }
446
447    /**
448     * Class that store range value and expression value.
449     */
450    private static class Values {
451
452        /** NP value for range. */
453        private final BigInteger rangeValue;
454
455        /** NP value for expression. */
456        private final BigInteger expressionValue;
457
458        /**
459         * Constructor that assigns all of class fields.
460         * @param valueOfRange NP value for range
461         * @param valueOfExpression NP value for expression
462         */
463        Values(BigInteger valueOfRange, BigInteger valueOfExpression) {
464            rangeValue = valueOfRange;
465            expressionValue = valueOfExpression;
466        }
467
468        /**
469         * Returns NP value for range.
470         * @return NP value for range
471         */
472        public BigInteger getRangeValue() {
473            return rangeValue;
474        }
475
476        /**
477         * Returns NP value for expression.
478         * @return NP value for expression
479         */
480        public BigInteger getExpressionValue() {
481            return expressionValue;
482        }
483
484    }
485
486}