001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2016 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 */
040public final class NPathComplexityCheck extends AbstractCheck {
041
042    /**
043     * A key is pointing to the warning message text in "messages.properties"
044     * file.
045     */
046    public static final String MSG_KEY = "npathComplexity";
047
048    /** Default allowed complexity. */
049    private static final int DEFAULT_MAX = 200;
050
051    /** The initial current value. */
052    private static final BigInteger INITIAL_VALUE = BigInteger.ONE;
053
054    /** Stack of values - all but the current value. */
055    private final Deque<BigInteger> valueStack = new ArrayDeque<>();
056
057    /** The current value. */
058    private BigInteger currentValue = INITIAL_VALUE;
059
060    /** Threshold to report error for. */
061    private int max = DEFAULT_MAX;
062
063    /**
064     * Set the maximum threshold allowed.
065     *
066     * @param max the maximum threshold
067     */
068    public void setMax(int max) {
069        this.max = max;
070    }
071
072    @Override
073    public int[] getDefaultTokens() {
074        return new int[] {
075            TokenTypes.CTOR_DEF,
076            TokenTypes.METHOD_DEF,
077            TokenTypes.STATIC_INIT,
078            TokenTypes.INSTANCE_INIT,
079            TokenTypes.LITERAL_WHILE,
080            TokenTypes.LITERAL_DO,
081            TokenTypes.LITERAL_FOR,
082            TokenTypes.LITERAL_IF,
083            TokenTypes.LITERAL_ELSE,
084            TokenTypes.LITERAL_SWITCH,
085            TokenTypes.LITERAL_CASE,
086            TokenTypes.LITERAL_TRY,
087            TokenTypes.LITERAL_CATCH,
088            TokenTypes.QUESTION,
089        };
090    }
091
092    @Override
093    public int[] getAcceptableTokens() {
094        return new int[] {
095            TokenTypes.CTOR_DEF,
096            TokenTypes.METHOD_DEF,
097            TokenTypes.STATIC_INIT,
098            TokenTypes.INSTANCE_INIT,
099            TokenTypes.LITERAL_WHILE,
100            TokenTypes.LITERAL_DO,
101            TokenTypes.LITERAL_FOR,
102            TokenTypes.LITERAL_IF,
103            TokenTypes.LITERAL_ELSE,
104            TokenTypes.LITERAL_SWITCH,
105            TokenTypes.LITERAL_CASE,
106            TokenTypes.LITERAL_TRY,
107            TokenTypes.LITERAL_CATCH,
108            TokenTypes.QUESTION,
109        };
110    }
111
112    @Override
113    public int[] getRequiredTokens() {
114        return new int[] {
115            TokenTypes.CTOR_DEF,
116            TokenTypes.METHOD_DEF,
117            TokenTypes.INSTANCE_INIT,
118            TokenTypes.STATIC_INIT,
119        };
120    }
121
122    @Override
123    public void visitToken(DetailAST ast) {
124        switch (ast.getType()) {
125            case TokenTypes.LITERAL_WHILE:
126            case TokenTypes.LITERAL_DO:
127            case TokenTypes.LITERAL_FOR:
128            case TokenTypes.LITERAL_IF:
129            case TokenTypes.QUESTION:
130            case TokenTypes.LITERAL_TRY:
131            case TokenTypes.LITERAL_SWITCH:
132                visitMultiplyingConditional();
133                break;
134            case TokenTypes.LITERAL_ELSE:
135            case TokenTypes.LITERAL_CATCH:
136            case TokenTypes.LITERAL_CASE:
137                visitAddingConditional();
138                break;
139            case TokenTypes.CTOR_DEF:
140            case TokenTypes.METHOD_DEF:
141            case TokenTypes.INSTANCE_INIT:
142            case TokenTypes.STATIC_INIT:
143                visitMethodDef();
144                break;
145            default:
146                break;
147        }
148    }
149
150    @Override
151    public void leaveToken(DetailAST ast) {
152        switch (ast.getType()) {
153            case TokenTypes.LITERAL_WHILE:
154            case TokenTypes.LITERAL_DO:
155            case TokenTypes.LITERAL_FOR:
156            case TokenTypes.LITERAL_IF:
157            case TokenTypes.QUESTION:
158            case TokenTypes.LITERAL_TRY:
159            case TokenTypes.LITERAL_SWITCH:
160                leaveMultiplyingConditional();
161                break;
162            case TokenTypes.LITERAL_ELSE:
163            case TokenTypes.LITERAL_CATCH:
164            case TokenTypes.LITERAL_CASE:
165                leaveAddingConditional();
166                break;
167            case TokenTypes.CTOR_DEF:
168            case TokenTypes.METHOD_DEF:
169            case TokenTypes.INSTANCE_INIT:
170            case TokenTypes.STATIC_INIT:
171                leaveMethodDef(ast);
172                break;
173            default:
174                break;
175        }
176    }
177
178    /** Visits else, catch or case. */
179    private void visitAddingConditional() {
180        pushValue();
181    }
182
183    /** Leaves else, catch or case. */
184    private void leaveAddingConditional() {
185        currentValue = currentValue.subtract(BigInteger.ONE).add(popValue());
186    }
187
188    /** Visits while, do, for, if, try, ? (in ?::) or switch. */
189    private void visitMultiplyingConditional() {
190        pushValue();
191    }
192
193    /** Leaves while, do, for, if, try, ? (in ?::) or switch. */
194    private void leaveMultiplyingConditional() {
195        currentValue = currentValue.add(BigInteger.ONE).multiply(popValue());
196    }
197
198    /** Push the current value on the stack. */
199    private void pushValue() {
200        valueStack.push(currentValue);
201        currentValue = INITIAL_VALUE;
202    }
203
204    /**
205     * Pops a value off the stack and makes it the current value.
206     * @return pop a value off the stack and make it the current value
207     */
208    private BigInteger popValue() {
209        currentValue = valueStack.pop();
210        return currentValue;
211    }
212
213    /** Process the start of the method definition. */
214    private void visitMethodDef() {
215        pushValue();
216    }
217
218    /**
219     * Process the end of a method definition.
220     *
221     * @param ast the token representing the method definition
222     */
223    private void leaveMethodDef(DetailAST ast) {
224        final BigInteger bigIntegerMax = BigInteger.valueOf(max);
225        if (currentValue.compareTo(bigIntegerMax) > 0) {
226            log(ast, MSG_KEY, currentValue, bigIntegerMax);
227        }
228        popValue();
229    }
230}