001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2015 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.coding;
021
022import java.util.ArrayDeque;
023import java.util.Deque;
024import java.util.HashSet;
025import java.util.LinkedList;
026import java.util.List;
027import java.util.Set;
028
029import com.google.common.collect.Sets;
030import com.puppycrawl.tools.checkstyle.api.Check;
031import com.puppycrawl.tools.checkstyle.api.DetailAST;
032import com.puppycrawl.tools.checkstyle.api.TokenTypes;
033
034/**
035 * Check for ensuring that for loop control variables are not modified
036 * inside the for block. An example is:
037 *
038 * <pre>
039 * {@code
040 * for (int i = 0; i &lt; 1; i++) {
041 *     i++;//violation
042 * }
043 * }
044 * </pre>
045 * Rationale: If the control variable is modified inside the loop
046 * body, the program flow becomes more difficult to follow.<br>
047 * See <a href="http://docs.oracle.com/javase/specs/jls/se8/html/jls-14.html#jls-14.14">
048 * FOR statement</a> specification for more details.
049 * <p>Examples:</p>
050 *
051 * <pre>
052 * &lt;module name=&quot;ModifiedControlVariable&quot;&gt;
053 * &lt;/module&gt;
054 * </pre>
055 *
056 * <p>Such loop would be suppressed:
057 *
058 * <pre>
059 * {@code
060 * for(int i=0; i &lt; 10;) {
061 *     i++;
062 * }
063 * }
064 * </pre>
065 *
066 * <p>
067 * By default, This Check validates
068 *  <a href = "http://docs.oracle.com/javase/specs/jls/se8/html/jls-14.html#jls-14.14.2">
069 * Enhanced For-Loop</a>.
070 * </p>
071 * <p>
072 * Option 'skipEnhancedForLoopVariable' could be used to skip check of variable
073 *  from Enhanced For Loop.
074 * </p>
075 * <p>
076 * An example of how to configure the check so that it skips enhanced For Loop Variable is:
077 * </p>
078 * <pre>
079 * &lt;module name="ModifiedControlVariable"&gt;
080 *     &lt;property name="skipEnhancedForLoopVariable" value="true"/&gt;
081 * &lt;/module&gt;
082 * </pre>
083 * <p>Example:</p>
084 *
085 * <pre>
086 * {@code
087 * for (String line: lines) {
088 *     line = line.trim();   // it will skip this violation
089 * }
090 * }
091 * </pre>
092 *
093 *
094 * @author Daniel Grenner
095 * @author <a href="mailto:piotr.listkiewicz@gmail.com">liscju</a>
096 */
097public final class ModifiedControlVariableCheck extends Check {
098
099    /**
100     * A key is pointing to the warning message text in "messages.properties"
101     * file.
102     */
103    public static final String MSG_KEY = "modified.control.variable";
104
105    /**
106     * Message thrown with IllegalStateException.
107     */
108    private static final String ILLEGAL_TYPE_OF_TOKEN = "Illegal type of token: ";
109
110    /** Operations which can change control variable in update part of the loop. */
111    private static final Set<Integer> MUTATION_OPERATIONS =
112            Sets.newHashSet(TokenTypes.POST_INC, TokenTypes.POST_DEC, TokenTypes.DEC,
113                    TokenTypes.INC, TokenTypes.ASSIGN);
114
115    /** Stack of block parameters. */
116    private final Deque<Deque<String>> variableStack = new ArrayDeque<>();
117
118    /** Controls whether to skip enhanced for-loop variable. */
119    private boolean skipEnhancedForLoopVariable;
120
121    /**
122     * Whether to skip enhanced for-loop variable or not.
123     * @param skipEnhancedForLoopVariable whether to skip enhanced for-loop variable
124     */
125    public void setSkipEnhancedForLoopVariable(boolean skipEnhancedForLoopVariable) {
126        this.skipEnhancedForLoopVariable = skipEnhancedForLoopVariable;
127    }
128
129    @Override
130    public int[] getDefaultTokens() {
131        return getAcceptableTokens();
132    }
133
134    @Override
135    public int[] getRequiredTokens() {
136        return getAcceptableTokens();
137    }
138
139    @Override
140    public int[] getAcceptableTokens() {
141        return new int[] {
142            TokenTypes.OBJBLOCK,
143            TokenTypes.LITERAL_FOR,
144            TokenTypes.FOR_ITERATOR,
145            TokenTypes.FOR_EACH_CLAUSE,
146            TokenTypes.ASSIGN,
147            TokenTypes.PLUS_ASSIGN,
148            TokenTypes.MINUS_ASSIGN,
149            TokenTypes.STAR_ASSIGN,
150            TokenTypes.DIV_ASSIGN,
151            TokenTypes.MOD_ASSIGN,
152            TokenTypes.SR_ASSIGN,
153            TokenTypes.BSR_ASSIGN,
154            TokenTypes.SL_ASSIGN,
155            TokenTypes.BAND_ASSIGN,
156            TokenTypes.BXOR_ASSIGN,
157            TokenTypes.BOR_ASSIGN,
158            TokenTypes.INC,
159            TokenTypes.POST_INC,
160            TokenTypes.DEC,
161            TokenTypes.POST_DEC,
162        };
163    }
164
165    @Override
166    public void beginTree(DetailAST rootAST) {
167        // clear data
168        variableStack.clear();
169        variableStack.push(new ArrayDeque<String>());
170    }
171
172    @Override
173    public void visitToken(DetailAST ast) {
174        switch (ast.getType()) {
175            case TokenTypes.OBJBLOCK:
176                enterBlock();
177                break;
178            case TokenTypes.LITERAL_FOR:
179            case TokenTypes.FOR_ITERATOR:
180            case TokenTypes.FOR_EACH_CLAUSE:
181                //we need that Tokens only at leaveToken()
182                break;
183            case TokenTypes.ASSIGN:
184            case TokenTypes.PLUS_ASSIGN:
185            case TokenTypes.MINUS_ASSIGN:
186            case TokenTypes.STAR_ASSIGN:
187            case TokenTypes.DIV_ASSIGN:
188            case TokenTypes.MOD_ASSIGN:
189            case TokenTypes.SR_ASSIGN:
190            case TokenTypes.BSR_ASSIGN:
191            case TokenTypes.SL_ASSIGN:
192            case TokenTypes.BAND_ASSIGN:
193            case TokenTypes.BXOR_ASSIGN:
194            case TokenTypes.BOR_ASSIGN:
195            case TokenTypes.INC:
196            case TokenTypes.POST_INC:
197            case TokenTypes.DEC:
198            case TokenTypes.POST_DEC:
199                checkIdent(ast);
200                break;
201            default:
202                throw new IllegalStateException(ILLEGAL_TYPE_OF_TOKEN + ast);
203        }
204    }
205
206    @Override
207    public void leaveToken(DetailAST ast) {
208        switch (ast.getType()) {
209            case TokenTypes.FOR_ITERATOR:
210                leaveForIter(ast.getParent());
211                break;
212            case TokenTypes.FOR_EACH_CLAUSE:
213                if (!skipEnhancedForLoopVariable) {
214                    final DetailAST paramDef = ast.findFirstToken(TokenTypes.VARIABLE_DEF);
215                    leaveForEach(paramDef);
216                }
217                break;
218            case TokenTypes.LITERAL_FOR:
219                if (!getCurrentVariables().isEmpty()) {
220                    leaveForDef(ast);
221                }
222                break;
223            case TokenTypes.OBJBLOCK:
224                exitBlock();
225                break;
226            case TokenTypes.ASSIGN:
227            case TokenTypes.PLUS_ASSIGN:
228            case TokenTypes.MINUS_ASSIGN:
229            case TokenTypes.STAR_ASSIGN:
230            case TokenTypes.DIV_ASSIGN:
231            case TokenTypes.MOD_ASSIGN:
232            case TokenTypes.SR_ASSIGN:
233            case TokenTypes.BSR_ASSIGN:
234            case TokenTypes.SL_ASSIGN:
235            case TokenTypes.BAND_ASSIGN:
236            case TokenTypes.BXOR_ASSIGN:
237            case TokenTypes.BOR_ASSIGN:
238            case TokenTypes.INC:
239            case TokenTypes.POST_INC:
240            case TokenTypes.DEC:
241            case TokenTypes.POST_DEC:
242                //we need that Tokens only at visitToken()
243                break;
244            default:
245                throw new IllegalStateException(ILLEGAL_TYPE_OF_TOKEN + ast);
246        }
247    }
248
249    /**
250     * Enters an inner class, which requires a new variable set.
251     */
252    private void enterBlock() {
253        variableStack.push(new ArrayDeque<String>());
254    }
255
256    /**
257     * Leave an inner class, so restore variable set.
258     */
259    private void exitBlock() {
260        variableStack.pop();
261    }
262
263    /**
264     * Get current variable stack.
265     * @return current variable stack
266     */
267    private Deque<String> getCurrentVariables() {
268        return variableStack.peek();
269    }
270
271    /**
272     * Check if ident is parameter.
273     * @param ast ident to check.
274     */
275    private void checkIdent(DetailAST ast) {
276        if (!getCurrentVariables().isEmpty()) {
277            final DetailAST identAST = ast.getFirstChild();
278
279            if (identAST != null && identAST.getType() == TokenTypes.IDENT
280                && getCurrentVariables().contains(identAST.getText())) {
281                log(ast.getLineNo(), ast.getColumnNo(),
282                    MSG_KEY, identAST.getText());
283            }
284        }
285    }
286
287    /**
288     * Push current variables to the stack.
289     * @param ast a for definition.
290     */
291    private void leaveForIter(DetailAST ast) {
292        final Set<String> variablesToPutInScope = getVariablesManagedByForLoop(ast);
293        for (String variableName : variablesToPutInScope) {
294            getCurrentVariables().push(variableName);
295        }
296    }
297
298    /**
299     * Determines which variable are specific to for loop and should not be
300     * change by inner loop body.
301     * @param ast For Loop
302     * @return Set of Variable Name which are managed by for
303     */
304    private static Set<String> getVariablesManagedByForLoop(DetailAST ast) {
305        final Set<String> initializedVariables = getForInitVariables(ast);
306        final Set<String> iteratingVariables = getForIteratorVariables(ast);
307
308        return Sets.intersection(initializedVariables, iteratingVariables);
309    }
310
311    /**
312     * Push current variables to the stack.
313     * @param paramDef a for-each clause variable
314     */
315    private void leaveForEach(DetailAST paramDef) {
316        final DetailAST paramName = paramDef.findFirstToken(TokenTypes.IDENT);
317        getCurrentVariables().push(paramName.getText());
318    }
319
320    /**
321     * Pops the variables from the stack.
322     * @param ast a for definition.
323     */
324    private void leaveForDef(DetailAST ast) {
325        final DetailAST forInitAST = ast.findFirstToken(TokenTypes.FOR_INIT);
326        if (forInitAST == null) {
327            // this is for-each loop, just pop variables
328            getCurrentVariables().pop();
329        }
330        else {
331            final Set<String> variablesManagedByForLoop = getVariablesManagedByForLoop(ast);
332            popCurrentVariables(variablesManagedByForLoop.size());
333        }
334    }
335
336    /**
337     * Pops given number of variables from currentVariables.
338     * @param count Count of variables to be popped from currentVariables
339     */
340    private void popCurrentVariables(int count) {
341        for (int i = 0; i < count; i++) {
342            getCurrentVariables().pop();
343        }
344    }
345
346    /**
347     * Get all variables initialized In init part of for loop.
348     * @param ast for loop token
349     * @return set of variables initialized in for loop
350     */
351    private static Set<String> getForInitVariables(DetailAST ast) {
352        final Set<String> initializedVariables = new HashSet<>();
353        final DetailAST forInitAST = ast.findFirstToken(TokenTypes.FOR_INIT);
354
355        for (DetailAST parameterDefAST = forInitAST.findFirstToken(TokenTypes.VARIABLE_DEF);
356             parameterDefAST != null;
357             parameterDefAST = parameterDefAST.getNextSibling()) {
358            if (parameterDefAST.getType() == TokenTypes.VARIABLE_DEF) {
359                final DetailAST param =
360                        parameterDefAST.findFirstToken(TokenTypes.IDENT);
361
362                initializedVariables.add(param.getText());
363            }
364        }
365        return initializedVariables;
366    }
367
368    /**
369     * Get all variables which for loop iterating part change in every loop.
370     * @param ast for loop literal(TokenTypes.LITERAL_FOR)
371     * @return names of variables change in iterating part of for
372     */
373    private static Set<String> getForIteratorVariables(DetailAST ast) {
374        final Set<String> iteratorVariables = new HashSet<>();
375        final DetailAST forIteratorAST = ast.findFirstToken(TokenTypes.FOR_ITERATOR);
376        final DetailAST forUpdateListAST = forIteratorAST.findFirstToken(TokenTypes.ELIST);
377
378        for (DetailAST iteratingExpressionAST : findChildrenOfExpressionType(forUpdateListAST)) {
379
380            if (MUTATION_OPERATIONS.contains(iteratingExpressionAST.getType())) {
381                final DetailAST oneVariableOperatorChild = iteratingExpressionAST.getFirstChild();
382                if (oneVariableOperatorChild.getType() == TokenTypes.IDENT) {
383                    iteratorVariables.add(oneVariableOperatorChild.getText());
384                }
385            }
386        }
387
388        return iteratorVariables;
389    }
390
391    /**
392     * Find all child of given AST of type TokenType.EXPR
393     * @param ast parent of expressions to find
394     * @return all child of given ast
395     */
396    private static List<DetailAST> findChildrenOfExpressionType(DetailAST ast) {
397        final List<DetailAST> foundExpressions = new LinkedList<>();
398        if (ast != null) {
399            for (DetailAST iteratingExpressionAST = ast.findFirstToken(TokenTypes.EXPR);
400                 iteratingExpressionAST != null;
401                 iteratingExpressionAST = iteratingExpressionAST.getNextSibling()) {
402                if (iteratingExpressionAST.getType() == TokenTypes.EXPR) {
403                    foundExpressions.add(iteratingExpressionAST.getFirstChild());
404                }
405            }
406        }
407        return foundExpressions;
408    }
409}