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