001///////////////////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code and other text files for adherence to a set of rules.
003// Copyright (C) 2001-2024 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.BitSet;
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;
035import com.puppycrawl.tools.checkstyle.utils.TokenUtil;
036
037/**
038 * <p>
039 * Checks that for loop control variables are not modified
040 * inside the for block. An example is:
041 * </p>
042 * <pre>
043 * for (int i = 0; i &lt; 1; i++) {
044 *   i++; // violation
045 * }
046 * </pre>
047 * <p>
048 * Rationale: If the control variable is modified inside the loop
049 * body, the program flow becomes more difficult to follow.
050 * See <a href="https://docs.oracle.com/javase/specs/jls/se11/html/jls-14.html#jls-14.14">
051 * FOR statement</a> specification for more details.
052 * </p>
053 * <p>
054 * Such loop would be suppressed:
055 * </p>
056 * <pre>
057 * for (int i = 0; i &lt; 10;) {
058 *   i++;
059 * }
060 * </pre>
061 * <p>
062 * NOTE:The check works with only primitive type variables.
063 * The check will not work for arrays used as control variable.An example is
064 * </p>
065 * <pre>
066 * for (int a[]={0};a[0] &lt; 10;a[0]++) {
067 *  a[0]++;   // it will skip this violation
068 * }
069 * </pre>
070 * <ul>
071 * <li>
072 * Property {@code skipEnhancedForLoopVariable} - Control whether to check
073 * <a href="https://docs.oracle.com/javase/specs/jls/se11/html/jls-14.html#jls-14.14.2">
074 * enhanced for-loop</a> variable.
075 * Type is {@code boolean}.
076 * Default value is {@code false}.
077 * </li>
078 * </ul>
079 * <p>
080 * Parent is {@code com.puppycrawl.tools.checkstyle.TreeWalker}
081 * </p>
082 * <p>
083 * Violation Message Keys:
084 * </p>
085 * <ul>
086 * <li>
087 * {@code modified.control.variable}
088 * </li>
089 * </ul>
090 *
091 * @since 3.5
092 */
093@FileStatefulCheck
094public final class ModifiedControlVariableCheck extends AbstractCheck {
095
096    /**
097     * A key is pointing to the warning message text in "messages.properties"
098     * file.
099     */
100    public static final String MSG_KEY = "modified.control.variable";
101
102    /**
103     * Message thrown with IllegalStateException.
104     */
105    private static final String ILLEGAL_TYPE_OF_TOKEN = "Illegal type of token: ";
106
107    /** Operations which can change control variable in update part of the loop. */
108    private static final BitSet MUTATION_OPERATIONS = TokenUtil.asBitSet(
109            TokenTypes.POST_INC,
110            TokenTypes.POST_DEC,
111            TokenTypes.DEC,
112            TokenTypes.INC,
113            TokenTypes.ASSIGN);
114
115    /** Stack of block parameters. */
116    private final Deque<Deque<String>> variableStack = new ArrayDeque<>();
117
118    /**
119     * Control whether to check
120     * <a href="https://docs.oracle.com/javase/specs/jls/se11/html/jls-14.html#jls-14.14.2">
121     * enhanced for-loop</a> variable.
122     */
123    private boolean skipEnhancedForLoopVariable;
124
125    /**
126     * Setter to control whether to check
127     * <a href="https://docs.oracle.com/javase/specs/jls/se11/html/jls-14.html#jls-14.14.2">
128     * enhanced for-loop</a> variable.
129     *
130     * @param skipEnhancedForLoopVariable whether to skip enhanced for-loop variable
131     * @since 6.8
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                leaveForDef(ast);
227                break;
228            case TokenTypes.OBJBLOCK:
229                exitBlock();
230                break;
231            case TokenTypes.ASSIGN:
232            case TokenTypes.PLUS_ASSIGN:
233            case TokenTypes.MINUS_ASSIGN:
234            case TokenTypes.STAR_ASSIGN:
235            case TokenTypes.DIV_ASSIGN:
236            case TokenTypes.MOD_ASSIGN:
237            case TokenTypes.SR_ASSIGN:
238            case TokenTypes.BSR_ASSIGN:
239            case TokenTypes.SL_ASSIGN:
240            case TokenTypes.BAND_ASSIGN:
241            case TokenTypes.BXOR_ASSIGN:
242            case TokenTypes.BOR_ASSIGN:
243            case TokenTypes.INC:
244            case TokenTypes.POST_INC:
245            case TokenTypes.DEC:
246            case TokenTypes.POST_DEC:
247                // we need that Tokens only at visitToken()
248                break;
249            default:
250                throw new IllegalStateException(ILLEGAL_TYPE_OF_TOKEN + ast);
251        }
252    }
253
254    /**
255     * Enters an inner class, which requires a new variable set.
256     */
257    private void enterBlock() {
258        variableStack.push(new ArrayDeque<>());
259    }
260
261    /**
262     * Leave an inner class, so restore variable set.
263     */
264    private void exitBlock() {
265        variableStack.pop();
266    }
267
268    /**
269     * Get current variable stack.
270     *
271     * @return current variable stack
272     */
273    private Deque<String> getCurrentVariables() {
274        return variableStack.peek();
275    }
276
277    /**
278     * Check if ident is parameter.
279     *
280     * @param ast ident to check.
281     */
282    private void checkIdent(DetailAST ast) {
283        final Deque<String> currentVariables = getCurrentVariables();
284        final DetailAST identAST = ast.getFirstChild();
285
286        if (identAST != null && identAST.getType() == TokenTypes.IDENT
287            && currentVariables.contains(identAST.getText())) {
288            log(ast, MSG_KEY, identAST.getText());
289        }
290    }
291
292    /**
293     * Push current variables to the stack.
294     *
295     * @param ast a for definition.
296     */
297    private void leaveForIter(DetailAST ast) {
298        final Set<String> variablesToPutInScope = getVariablesManagedByForLoop(ast);
299        for (String variableName : variablesToPutInScope) {
300            getCurrentVariables().push(variableName);
301        }
302    }
303
304    /**
305     * Determines which variable are specific to for loop and should not be
306     * change by inner loop body.
307     *
308     * @param ast For Loop
309     * @return Set of Variable Name which are managed by for
310     */
311    private static Set<String> getVariablesManagedByForLoop(DetailAST ast) {
312        final Set<String> initializedVariables = getForInitVariables(ast);
313        final Set<String> iteratingVariables = getForIteratorVariables(ast);
314        return initializedVariables.stream().filter(iteratingVariables::contains)
315            .collect(Collectors.toUnmodifiableSet());
316    }
317
318    /**
319     * Push current variables to the stack.
320     *
321     * @param paramDef a for-each clause variable
322     */
323    private void leaveForEach(DetailAST paramDef) {
324        // When using record decomposition in enhanced for loops,
325        // we are not able to declare a 'control variable'.
326        final boolean isRecordPattern = paramDef == null;
327
328        if (!isRecordPattern) {
329            final DetailAST paramName = paramDef.findFirstToken(TokenTypes.IDENT);
330            getCurrentVariables().push(paramName.getText());
331        }
332    }
333
334    /**
335     * Pops the variables from the stack.
336     *
337     * @param ast a for definition.
338     */
339    private void leaveForDef(DetailAST ast) {
340        final DetailAST forInitAST = ast.findFirstToken(TokenTypes.FOR_INIT);
341        if (forInitAST == null) {
342            final Deque<String> currentVariables = getCurrentVariables();
343            if (!skipEnhancedForLoopVariable && !currentVariables.isEmpty()) {
344                // this is for-each loop, just pop variables
345                currentVariables.pop();
346            }
347        }
348        else {
349            final Set<String> variablesManagedByForLoop = getVariablesManagedByForLoop(ast);
350            popCurrentVariables(variablesManagedByForLoop.size());
351        }
352    }
353
354    /**
355     * Pops given number of variables from currentVariables.
356     *
357     * @param count Count of variables to be popped from currentVariables
358     */
359    private void popCurrentVariables(int count) {
360        for (int i = 0; i < count; i++) {
361            getCurrentVariables().pop();
362        }
363    }
364
365    /**
366     * Get all variables initialized In init part of for loop.
367     *
368     * @param ast for loop token
369     * @return set of variables initialized in for loop
370     */
371    private static Set<String> getForInitVariables(DetailAST ast) {
372        final Set<String> initializedVariables = new HashSet<>();
373        final DetailAST forInitAST = ast.findFirstToken(TokenTypes.FOR_INIT);
374
375        for (DetailAST parameterDefAST = forInitAST.findFirstToken(TokenTypes.VARIABLE_DEF);
376             parameterDefAST != null;
377             parameterDefAST = parameterDefAST.getNextSibling()) {
378            if (parameterDefAST.getType() == TokenTypes.VARIABLE_DEF) {
379                final DetailAST param =
380                        parameterDefAST.findFirstToken(TokenTypes.IDENT);
381
382                initializedVariables.add(param.getText());
383            }
384        }
385        return initializedVariables;
386    }
387
388    /**
389     * Get all variables which for loop iterating part change in every loop.
390     *
391     * @param ast for loop literal(TokenTypes.LITERAL_FOR)
392     * @return names of variables change in iterating part of for
393     */
394    private static Set<String> getForIteratorVariables(DetailAST ast) {
395        final Set<String> iteratorVariables = new HashSet<>();
396        final DetailAST forIteratorAST = ast.findFirstToken(TokenTypes.FOR_ITERATOR);
397        final DetailAST forUpdateListAST = forIteratorAST.findFirstToken(TokenTypes.ELIST);
398
399        findChildrenOfExpressionType(forUpdateListAST).stream()
400            .filter(iteratingExpressionAST -> {
401                return MUTATION_OPERATIONS.get(iteratingExpressionAST.getType());
402            }).forEach(iteratingExpressionAST -> {
403                final DetailAST oneVariableOperatorChild = iteratingExpressionAST.getFirstChild();
404                iteratorVariables.add(oneVariableOperatorChild.getText());
405            });
406
407        return iteratorVariables;
408    }
409
410    /**
411     * Find all child of given AST of type TokenType.EXPR
412     *
413     * @param ast parent of expressions to find
414     * @return all child of given ast
415     */
416    private static List<DetailAST> findChildrenOfExpressionType(DetailAST ast) {
417        final List<DetailAST> foundExpressions = new LinkedList<>();
418        if (ast != null) {
419            for (DetailAST iteratingExpressionAST = ast.findFirstToken(TokenTypes.EXPR);
420                 iteratingExpressionAST != null;
421                 iteratingExpressionAST = iteratingExpressionAST.getNextSibling()) {
422                if (iteratingExpressionAST.getType() == TokenTypes.EXPR) {
423                    foundExpressions.add(iteratingExpressionAST.getFirstChild());
424                }
425            }
426        }
427        return foundExpressions;
428    }
429
430}