View Javadoc
1   ////////////////////////////////////////////////////////////////////////////////
2   // checkstyle: Checks Java source code for adherence to a set of rules.
3   // Copyright (C) 2001-2017 the original author or authors.
4   //
5   // This library is free software; you can redistribute it and/or
6   // modify it under the terms of the GNU Lesser General Public
7   // License as published by the Free Software Foundation; either
8   // version 2.1 of the License, or (at your option) any later version.
9   //
10  // This library is distributed in the hope that it will be useful,
11  // but WITHOUT ANY WARRANTY; without even the implied warranty of
12  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  // Lesser General Public License for more details.
14  //
15  // You should have received a copy of the GNU Lesser General Public
16  // License along with this library; if not, write to the Free Software
17  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18  ////////////////////////////////////////////////////////////////////////////////
19  
20  package com.puppycrawl.tools.checkstyle.checks.metrics;
21  
22  import java.math.BigInteger;
23  import java.util.ArrayDeque;
24  import java.util.Deque;
25  
26  import com.puppycrawl.tools.checkstyle.FileStatefulCheck;
27  import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
28  import com.puppycrawl.tools.checkstyle.api.DetailAST;
29  import com.puppycrawl.tools.checkstyle.api.TokenTypes;
30  
31  /**
32   * Checks the npath complexity against a specified limit (default = 200).
33   * The npath metric computes the number of possible execution paths
34   * through a function. Similar to the cyclomatic complexity but also
35   * takes into account the nesting of conditional statements and
36   * multi-part boolean expressions.
37   *
38   * @author <a href="mailto:simon@redhillconsulting.com.au">Simon Harris</a>
39   * @author o_sukhodolsky
40   */
41  // -@cs[AbbreviationAsWordInName] Can't change check name
42  @FileStatefulCheck
43  public final class NPathComplexityCheck extends AbstractCheck {
44  
45      /**
46       * A key is pointing to the warning message text in "messages.properties"
47       * file.
48       */
49      public static final String MSG_KEY = "npathComplexity";
50  
51      /** Default allowed complexity. */
52      private static final int DEFAULT_MAX = 200;
53  
54      /** The initial current value. */
55      private static final BigInteger INITIAL_VALUE = BigInteger.ZERO;
56  
57      /**
58       * Stack of NP values for ranges.
59       */
60      private final Deque<BigInteger> rangeValues = new ArrayDeque<>();
61  
62      /** Stack of NP values for expressions. */
63      private final Deque<Integer> expressionValues = new ArrayDeque<>();
64  
65      /** Stack of belongs to range values for question operator. */
66      private final Deque<Boolean> isAfterValues = new ArrayDeque<>();
67  
68      /**
69       * Range of the last processed expression. Used for checking that ternary operation
70       * which is a part of expression won't be processed for second time.
71       */
72      private final TokenEnd processingTokenEnd = new TokenEnd();
73  
74      /** NP value for current range. */
75      private BigInteger currentRangeValue = INITIAL_VALUE;
76  
77      /** Threshold to report error for. */
78      private int max = DEFAULT_MAX;
79  
80      /** True, when branch is visited, but not leaved. */
81      private boolean branchVisited;
82  
83      /**
84       * Set the maximum threshold allowed.
85       * @param max the maximum threshold
86       */
87      public void setMax(int max) {
88          this.max = max;
89      }
90  
91      @Override
92      public int[] getDefaultTokens() {
93          return getRequiredTokens();
94      }
95  
96      @Override
97      public int[] getAcceptableTokens() {
98          return getRequiredTokens();
99      }
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         /** End line of token. */
405         private int endLineNo;
406 
407         /** End column of token. */
408         private int endColumnNo;
409 
410         /**
411          * Sets end coordinates from given token.
412          * @param endToken token.
413          */
414         public void setToken(DetailAST endToken) {
415             if (!isAfter(endToken)) {
416                 endLineNo = endToken.getLineNo();
417                 endColumnNo = endToken.getColumnNo();
418             }
419         }
420 
421         /** Sets end token coordinates to the start of the file. */
422         public void reset() {
423             endLineNo = 0;
424             endColumnNo = 0;
425         }
426 
427         /**
428          * Checks if saved coordinates located after given token.
429          * @param ast given token.
430          * @return true, if saved coordinates located after given token.
431          */
432         public boolean isAfter(DetailAST ast) {
433             final int lineNo = ast.getLineNo();
434             final int columnNo = ast.getColumnNo();
435             boolean isAfter = true;
436             if (lineNo > endLineNo
437                     || lineNo == endLineNo
438                     && columnNo > endColumnNo) {
439                 isAfter = false;
440             }
441             return isAfter;
442         }
443     }
444 
445     /**
446      * Class that store range value and expression value.
447      */
448     private static class Values {
449 
450         /** NP value for range. */
451         private final BigInteger rangeValue;
452 
453         /** NP value for expression. */
454         private final BigInteger expressionValue;
455 
456         /**
457          * Constructor that assigns all of class fields.
458          * @param valueOfRange NP value for range
459          * @param valueOfExpression NP value for expression
460          */
461         Values(BigInteger valueOfRange, BigInteger valueOfExpression) {
462             rangeValue = valueOfRange;
463             expressionValue = valueOfExpression;
464         }
465 
466         /**
467          * Returns NP value for range.
468          * @return NP value for range
469          */
470         public BigInteger getRangeValue() {
471             return rangeValue;
472         }
473 
474         /**
475          * Returns NP value for expression.
476          * @return NP value for expression
477          */
478         public BigInteger getExpressionValue() {
479             return expressionValue;
480         }
481 
482     }
483 
484 }