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