Source code

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