1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
33
34
35
36
37
38
39
40 @FileStatefulCheck
41 public final class NPathComplexityCheck extends AbstractCheck {
42
43
44
45
46
47 public static final String MSG_KEY = "npathComplexity";
48
49
50 private static final int DEFAULT_MAX = 200;
51
52
53 private static final BigInteger INITIAL_VALUE = BigInteger.ZERO;
54
55
56
57
58 private final Deque<BigInteger> rangeValues = new ArrayDeque<>();
59
60
61 private final Deque<Integer> expressionValues = new ArrayDeque<>();
62
63
64 private final Deque<Boolean> afterValues = new ArrayDeque<>();
65
66
67
68
69
70 private final TokenEnd processingTokenEnd = new TokenEnd();
71
72
73 private BigInteger currentRangeValue = INITIAL_VALUE;
74
75
76 private int max = DEFAULT_MAX;
77
78
79 private boolean branchVisited;
80
81
82
83
84
85 public void setMax(int max) {
86 this.max = max;
87 }
88
89 @Override
90 public int[] getDefaultTokens() {
91 return getRequiredTokens();
92 }
93
94 @Override
95 public int[] getAcceptableTokens() {
96 return getRequiredTokens();
97 }
98
99 @Override
100 public int[] getRequiredTokens() {
101 return new int[] {
102 TokenTypes.CTOR_DEF,
103 TokenTypes.METHOD_DEF,
104 TokenTypes.STATIC_INIT,
105 TokenTypes.INSTANCE_INIT,
106 TokenTypes.LITERAL_WHILE,
107 TokenTypes.LITERAL_DO,
108 TokenTypes.LITERAL_FOR,
109 TokenTypes.LITERAL_IF,
110 TokenTypes.LITERAL_ELSE,
111 TokenTypes.LITERAL_SWITCH,
112 TokenTypes.CASE_GROUP,
113 TokenTypes.LITERAL_TRY,
114 TokenTypes.LITERAL_CATCH,
115 TokenTypes.QUESTION,
116 TokenTypes.LITERAL_RETURN,
117 TokenTypes.LITERAL_DEFAULT,
118 };
119 }
120
121 @Override
122 public void beginTree(DetailAST rootAST) {
123 rangeValues.clear();
124 expressionValues.clear();
125 afterValues.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
216
217
218
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
234
235
236
237
238 private void visitUnitaryOperator(DetailAST ast, int basicBranchingFactor) {
239 final boolean isAfter = processingTokenEnd.isAfter(ast);
240 afterValues.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
250
251 private void leaveUnitaryOperator() {
252 if (!afterValues.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
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
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
295
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
307 private void leaveAddingConditional() {
308 currentRangeValue = currentRangeValue.add(popValue().getRangeValue().add(BigInteger.ONE));
309 }
310
311
312
313
314
315
316 private void pushValue(Integer expressionValue) {
317 rangeValues.push(currentRangeValue);
318 expressionValues.push(expressionValue);
319 currentRangeValue = INITIAL_VALUE;
320 }
321
322
323
324
325
326 private Values popValue() {
327 final int expressionValue = expressionValues.pop();
328 return new Values(rangeValues.pop(), BigInteger.valueOf(expressionValue));
329 }
330
331
332 private void leaveMultiplyingConditional() {
333 currentRangeValue = currentRangeValue.add(BigInteger.ONE)
334 .multiply(popValue().getRangeValue().add(BigInteger.ONE));
335 }
336
337
338
339
340
341
342
343
344
345
346
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
366
367
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
383
384
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
399
400
401 private static class TokenEnd {
402
403
404 private int endLineNo;
405
406
407 private int endColumnNo;
408
409
410
411
412
413 public void setToken(DetailAST endToken) {
414 if (!isAfter(endToken)) {
415 endLineNo = endToken.getLineNo();
416 endColumnNo = endToken.getColumnNo();
417 }
418 }
419
420
421 public void reset() {
422 endLineNo = 0;
423 endColumnNo = 0;
424 }
425
426
427
428
429
430
431 public boolean isAfter(DetailAST ast) {
432 final int lineNo = ast.getLineNo();
433 final int columnNo = ast.getColumnNo();
434 boolean isAfter = true;
435 if (lineNo > endLineNo
436 || lineNo == endLineNo
437 && columnNo > endColumnNo) {
438 isAfter = false;
439 }
440 return isAfter;
441 }
442
443 }
444
445
446
447
448 private static class Values {
449
450
451 private final BigInteger rangeValue;
452
453
454 private final BigInteger expressionValue;
455
456
457
458
459
460
461 Values(BigInteger valueOfRange, BigInteger valueOfExpression) {
462 rangeValue = valueOfRange;
463 expressionValue = valueOfExpression;
464 }
465
466
467
468
469
470 public BigInteger getRangeValue() {
471 return rangeValue;
472 }
473
474
475
476
477
478 public BigInteger getExpressionValue() {
479 return expressionValue;
480 }
481
482 }
483
484 }