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