001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2020 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 * <p>
033 * Checks cyclomatic complexity against a specified limit. It is a measure of
034 * the minimum number of possible paths through the source and therefore the
035 * number of required tests, it is not a about quality of code! It is only
036 * applied to methods, c-tors,
037 * <a href="https://docs.oracle.com/javase/tutorial/java/javaOO/initial.html">
038 * static initializers and instance initializers</a>.
039 * </p>
040 * <p>
041 * The complexity is equal to the number of decision points {@code + 1}.
042 * Decision points: {@code if}, {@code while}, {@code do}, {@code for},
043 * {@code ?:}, {@code catch}, {@code switch}, {@code case} statements and
044 * operators {@code &amp;&amp;} and {@code ||} in the body of target.
045 * </p>
046 * <p>
047 * By pure theory level 1-4 is considered easy to test, 5-7 OK, 8-10 consider
048 * re-factoring to ease testing, and 11+ re-factor now as testing will be painful.
049 * </p>
050 * <p>
051 * When it comes to code quality measurement by this metric level 10 is very
052 * good level as a ultimate target (that is hard to archive). Do not be ashamed
053 * to have complexity level 15 or even higher, but keep it below 20 to catch
054 * really bad designed code automatically.
055 * </p>
056 * <p>
057 * Please use Suppression to avoid violations on cases that could not be split
058 * in few methods without damaging readability of code or encapsulation.
059 * </p>
060 * <ul>
061 * <li>
062 * Property {@code max} - Specify the maximum threshold allowed.
063 * Type is {@code int}.
064 * Default value is {@code 10}.
065 * </li>
066 * <li>
067 * Property {@code switchBlockAsSingleDecisionPoint} - Control whether to treat
068 * the whole switch block as a single decision point.
069 * Type is {@code boolean}.
070 * Default value is {@code false}.
071 * </li>
072 * <li>
073 * Property {@code tokens} - tokens to check
074 * Type is {@code java.lang.String[]}.
075 * Validation type is {@code tokenSet}.
076 * Default value is:
077 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LITERAL_WHILE">
078 * LITERAL_WHILE</a>,
079 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LITERAL_DO">
080 * LITERAL_DO</a>,
081 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LITERAL_FOR">
082 * LITERAL_FOR</a>,
083 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LITERAL_IF">
084 * LITERAL_IF</a>,
085 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LITERAL_SWITCH">
086 * LITERAL_SWITCH</a>,
087 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LITERAL_CASE">
088 * LITERAL_CASE</a>,
089 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LITERAL_CATCH">
090 * LITERAL_CATCH</a>,
091 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#QUESTION">
092 * QUESTION</a>,
093 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LAND">
094 * LAND</a>,
095 * <a href="https://checkstyle.org/apidocs/com/puppycrawl/tools/checkstyle/api/TokenTypes.html#LOR">
096 * LOR</a>.
097 * </li>
098 * </ul>
099 * <p>
100 * To configure the check:
101 * </p>
102 * <pre>
103 * &lt;module name="CyclomaticComplexity"/&gt;
104 * </pre>
105 * <p>
106 * Example:
107 * </p>
108 * <pre>
109 * class CyclomaticComplexity {
110 *   // Cyclomatic Complexity = 11
111 *   int a, b, c, d, n;
112 *   public void foo() { // 1, function declaration
113 *     if (a == 1) { // 2, if
114 *       fun1();
115 *     } else if (a == b // 3, if
116 *       &amp;&amp; a == c) { // 4, &amp;&amp; operator
117 *       if (c == 2) { // 5, if
118 *         fun2();
119 *       }
120 *     } else if (a == d) { // 6, if
121 *       try {
122 *         fun4();
123 *       } catch (Exception e) { // 7, catch
124 *       }
125 *     } else {
126 *       switch(n) {
127 *         case 1: // 8, case
128 *           fun1();
129 *           break;
130 *         case 2: // 9, case
131 *           fun2();
132 *           break;
133 *         case 3: // 10, case
134 *           fun3();
135 *           break;
136 *         default:
137 *           break;
138 *       }
139 *     }
140 *     d = a &lt; 0 ? -1 : 1; // 11, ternary operator
141 *   }
142 * }
143 * </pre>
144 * <p>
145 * To configure the check with a threshold of 4 and check only for while and do-while loops:
146 * </p>
147 * <pre>
148 * &lt;module name="CyclomaticComplexity"&gt;
149 *   &lt;property name="max" value="4"/&gt;
150 *   &lt;property name="tokens" value="LITERAL_WHILE, LITERAL_DO"/&gt;
151 * &lt;/module&gt;
152 * </pre>
153 * <p>
154 * Example:
155 * </p>
156 * <pre>
157 * class CyclomaticComplexity {
158 *   // Cyclomatic Complexity = 5
159 *   int a, b, c, d;
160 *   public void foo() { // 1, function declaration
161 *     while (a &lt; b // 2, while
162 *       &amp;&amp; a &gt; c) {
163 *       fun();
164 *     }
165 *     if (a == b) {
166 *       do { // 3, do
167 *         fun();
168 *       } while (d);
169 *     } else if (c == d) {
170 *       while (c &gt; 0) { // 4, while
171 *         fun();
172 *       }
173 *       do { // 5, do-while
174 *         fun();
175 *       } while (a);
176 *     }
177 *   }
178 * }
179 * </pre>
180 * <p>
181 * To configure the check to consider switch-case block as one decision point.
182 * </p>
183 * <pre>
184 * &lt;module name="CyclomaticComplexity"&gt;
185 *   &lt;property name="switchBlockAsSingleDecisionPoint" value="true"/&gt;
186 * &lt;/module&gt;
187 * </pre>
188 * <p>
189 * Example:
190 * </p>
191 * <pre>
192 * class CyclomaticComplexity {
193 *   // Cyclomatic Complexity = 11
194 *   int a, b, c, d, e, n;
195 *   public void foo() { // 1, function declaration
196 *     if (a == b) { // 2, if
197 *       fun1();
198 *     } else if (a == 0 // 3, if
199 *       &amp;&amp; b == c) { // 4, &amp;&amp; operator
200 *       if (c == -1) { // 5, if
201 *         fun2();
202 *       }
203 *     } else if (a == c // 6, if
204 *       || a == d) { // 7, || operator
205 *       fun3();
206 *     } else if (d == e) { // 8, if
207 *       try {
208 *         fun4();
209 *       } catch (Exception e) { // 9, catch
210 *       }
211 *     } else {
212 *       switch(n) { // 10, switch
213 *         case 1:
214 *           fun1();
215 *           break;
216 *         case 2:
217 *           fun2();
218 *           break;
219 *         default:
220 *           break;
221 *       }
222 *     }
223 *     a = a &gt; 0 ? b : c; // 11, ternary operator
224 *   }
225 * }
226 * </pre>
227 * <p>
228 * Parent is {@code com.puppycrawl.tools.checkstyle.TreeWalker}
229 * </p>
230 * <p>
231 * Violation Message Keys:
232 * </p>
233 * <ul>
234 * <li>
235 * {@code cyclomaticComplexity}
236 * </li>
237 * </ul>
238 *
239 * @since 3.2
240 */
241@FileStatefulCheck
242public class CyclomaticComplexityCheck
243    extends AbstractCheck {
244
245    /**
246     * A key is pointing to the warning message text in "messages.properties"
247     * file.
248     */
249    public static final String MSG_KEY = "cyclomaticComplexity";
250
251    /** The initial current value. */
252    private static final BigInteger INITIAL_VALUE = BigInteger.ONE;
253
254    /** Default allowed complexity. */
255    private static final int DEFAULT_COMPLEXITY_VALUE = 10;
256
257    /** Stack of values - all but the current value. */
258    private final Deque<BigInteger> valueStack = new ArrayDeque<>();
259
260    /** Control whether to treat the whole switch block as a single decision point. */
261    private boolean switchBlockAsSingleDecisionPoint;
262
263    /** The current value. */
264    private BigInteger currentValue = INITIAL_VALUE;
265
266    /** Specify the maximum threshold allowed. */
267    private int max = DEFAULT_COMPLEXITY_VALUE;
268
269    /**
270     * Setter to control whether to treat the whole switch block as a single decision point.
271     *
272     * @param switchBlockAsSingleDecisionPoint whether to treat the whole switch
273     *                                          block as a single decision point.
274     */
275    public void setSwitchBlockAsSingleDecisionPoint(boolean switchBlockAsSingleDecisionPoint) {
276        this.switchBlockAsSingleDecisionPoint = switchBlockAsSingleDecisionPoint;
277    }
278
279    /**
280     * Setter to specify the maximum threshold allowed.
281     *
282     * @param max the maximum threshold
283     */
284    public final void setMax(int max) {
285        this.max = max;
286    }
287
288    @Override
289    public int[] getDefaultTokens() {
290        return new int[] {
291            TokenTypes.CTOR_DEF,
292            TokenTypes.METHOD_DEF,
293            TokenTypes.INSTANCE_INIT,
294            TokenTypes.STATIC_INIT,
295            TokenTypes.LITERAL_WHILE,
296            TokenTypes.LITERAL_DO,
297            TokenTypes.LITERAL_FOR,
298            TokenTypes.LITERAL_IF,
299            TokenTypes.LITERAL_SWITCH,
300            TokenTypes.LITERAL_CASE,
301            TokenTypes.LITERAL_CATCH,
302            TokenTypes.QUESTION,
303            TokenTypes.LAND,
304            TokenTypes.LOR,
305            TokenTypes.COMPACT_CTOR_DEF,
306        };
307    }
308
309    @Override
310    public int[] getAcceptableTokens() {
311        return new int[] {
312            TokenTypes.CTOR_DEF,
313            TokenTypes.METHOD_DEF,
314            TokenTypes.INSTANCE_INIT,
315            TokenTypes.STATIC_INIT,
316            TokenTypes.LITERAL_WHILE,
317            TokenTypes.LITERAL_DO,
318            TokenTypes.LITERAL_FOR,
319            TokenTypes.LITERAL_IF,
320            TokenTypes.LITERAL_SWITCH,
321            TokenTypes.LITERAL_CASE,
322            TokenTypes.LITERAL_CATCH,
323            TokenTypes.QUESTION,
324            TokenTypes.LAND,
325            TokenTypes.LOR,
326            TokenTypes.COMPACT_CTOR_DEF,
327        };
328    }
329
330    @Override
331    public final int[] getRequiredTokens() {
332        return new int[] {
333            TokenTypes.CTOR_DEF,
334            TokenTypes.METHOD_DEF,
335            TokenTypes.INSTANCE_INIT,
336            TokenTypes.STATIC_INIT,
337            TokenTypes.COMPACT_CTOR_DEF,
338        };
339    }
340
341    @Override
342    public void visitToken(DetailAST ast) {
343        switch (ast.getType()) {
344            case TokenTypes.CTOR_DEF:
345            case TokenTypes.METHOD_DEF:
346            case TokenTypes.INSTANCE_INIT:
347            case TokenTypes.STATIC_INIT:
348            case TokenTypes.COMPACT_CTOR_DEF:
349                visitMethodDef();
350                break;
351            default:
352                visitTokenHook(ast);
353        }
354    }
355
356    @Override
357    public void leaveToken(DetailAST ast) {
358        switch (ast.getType()) {
359            case TokenTypes.CTOR_DEF:
360            case TokenTypes.METHOD_DEF:
361            case TokenTypes.INSTANCE_INIT:
362            case TokenTypes.STATIC_INIT:
363            case TokenTypes.COMPACT_CTOR_DEF:
364                leaveMethodDef(ast);
365                break;
366            default:
367                break;
368        }
369    }
370
371    /**
372     * Hook called when visiting a token. Will not be called the method
373     * definition tokens.
374     *
375     * @param ast the token being visited
376     */
377    private void visitTokenHook(DetailAST ast) {
378        if (switchBlockAsSingleDecisionPoint) {
379            if (ast.getType() != TokenTypes.LITERAL_CASE) {
380                incrementCurrentValue(BigInteger.ONE);
381            }
382        }
383        else if (ast.getType() != TokenTypes.LITERAL_SWITCH) {
384            incrementCurrentValue(BigInteger.ONE);
385        }
386    }
387
388    /**
389     * Process the end of a method definition.
390     *
391     * @param ast the token representing the method definition
392     */
393    private void leaveMethodDef(DetailAST ast) {
394        final BigInteger bigIntegerMax = BigInteger.valueOf(max);
395        if (currentValue.compareTo(bigIntegerMax) > 0) {
396            log(ast, MSG_KEY, currentValue, bigIntegerMax);
397        }
398        popValue();
399    }
400
401    /**
402     * Increments the current value by a specified amount.
403     *
404     * @param amount the amount to increment by
405     */
406    private void incrementCurrentValue(BigInteger amount) {
407        currentValue = currentValue.add(amount);
408    }
409
410    /** Push the current value on the stack. */
411    private void pushValue() {
412        valueStack.push(currentValue);
413        currentValue = INITIAL_VALUE;
414    }
415
416    /**
417     * Pops a value off the stack and makes it the current value.
418     */
419    private void popValue() {
420        currentValue = valueStack.pop();
421    }
422
423    /** Process the start of the method definition. */
424    private void visitMethodDef() {
425        pushValue();
426    }
427
428}