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.Arrays;
024import java.util.Deque;
025import java.util.HashMap;
026import java.util.Iterator;
027import java.util.Map;
028
029import com.puppycrawl.tools.checkstyle.api.Check;
030import com.puppycrawl.tools.checkstyle.api.DetailAST;
031import com.puppycrawl.tools.checkstyle.api.TokenTypes;
032import com.puppycrawl.tools.checkstyle.utils.ScopeUtils;
033
034/**
035 * <p>
036 * Ensures that local variables that never get their values changed,
037 * must be declared final.
038 * </p>
039 * <p>
040 * An example of how to configure the check to validate variable definition is:
041 * </p>
042 * <pre>
043 * &lt;module name="FinalLocalVariable"&gt;
044 *     &lt;property name="tokens" value="VARIABLE_DEF"/&gt;
045 * &lt;/module&gt;
046 * </pre>
047 * <p>
048 * By default, this Check skip final validation on
049 *  <a href = "http://docs.oracle.com/javase/specs/jls/se8/html/jls-14.html#jls-14.14.2">
050 * Enhanced For-Loop</a>
051 * </p>
052 * <p>
053 * Option 'validateEnhancedForLoopVariable' could be used to make Check to validate even variable
054 *  from Enhanced For Loop.
055 * </p>
056 * <p>
057 * An example of how to configure the check so that it also validates enhanced For Loop Variable is:
058 * </p>
059 * <pre>
060 * &lt;module name="FinalLocalVariable"&gt;
061 *     &lt;property name="tokens" value="VARIABLE_DEF"/&gt;
062 *     &lt;property name="validateEnhancedForLoopVariable" value="true"/&gt;
063 * &lt;/module&gt;
064 * </pre>
065 * <p>Example:</p>
066 * <p>
067 * {@code
068 * for (int number : myNumbers) { // violation
069 *    System.out.println(number);
070 * }
071 * }
072 * </p>
073 * @author k_gibbs, r_auckenthaler
074 * @author Vladislav Lisetskiy
075 */
076public class FinalLocalVariableCheck extends Check {
077
078    /**
079     * A key is pointing to the warning message text in "messages.properties"
080     * file.
081     */
082    public static final String MSG_KEY = "final.variable";
083
084    /**
085     * Assign operator types.
086     */
087    private static final int[] ASSIGN_OPERATOR_TYPES = {
088        TokenTypes.POST_INC,
089        TokenTypes.POST_DEC,
090        TokenTypes.ASSIGN,
091        TokenTypes.PLUS_ASSIGN,
092        TokenTypes.MINUS_ASSIGN,
093        TokenTypes.STAR_ASSIGN,
094        TokenTypes.DIV_ASSIGN,
095        TokenTypes.MOD_ASSIGN,
096        TokenTypes.SR_ASSIGN,
097        TokenTypes.BSR_ASSIGN,
098        TokenTypes.SL_ASSIGN,
099        TokenTypes.BAND_ASSIGN,
100        TokenTypes.BXOR_ASSIGN,
101        TokenTypes.BOR_ASSIGN,
102        TokenTypes.INC,
103        TokenTypes.DEC,
104    };
105
106    /**
107     * Loop types.
108     */
109    private static final int[] LOOP_TYPES = {
110        TokenTypes.LITERAL_FOR,
111        TokenTypes.LITERAL_WHILE,
112        TokenTypes.LITERAL_DO,
113    };
114
115    /** Scope Deque. */
116    private final Deque<ScopeData> scopeStack = new ArrayDeque<>();
117
118    /** Controls whether to check enhanced for-loop variable. */
119    private boolean validateEnhancedForLoopVariable;
120
121    static {
122        // Array sorting for binary search
123        Arrays.sort(ASSIGN_OPERATOR_TYPES);
124        Arrays.sort(LOOP_TYPES);
125    }
126
127    /**
128     * Whether to check enhanced for-loop variable or not.
129     * @param validateEnhancedForLoopVariable whether to check for-loop variable
130     */
131    public final void setValidateEnhancedForLoopVariable(boolean validateEnhancedForLoopVariable) {
132        this.validateEnhancedForLoopVariable = validateEnhancedForLoopVariable;
133    }
134
135    @Override
136    public int[] getRequiredTokens() {
137        return new int[] {
138            TokenTypes.IDENT,
139            TokenTypes.CTOR_DEF,
140            TokenTypes.METHOD_DEF,
141            TokenTypes.SLIST,
142            TokenTypes.OBJBLOCK,
143        };
144    }
145
146    @Override
147    public int[] getDefaultTokens() {
148        return new int[] {
149            TokenTypes.IDENT,
150            TokenTypes.CTOR_DEF,
151            TokenTypes.METHOD_DEF,
152            TokenTypes.SLIST,
153            TokenTypes.OBJBLOCK,
154            TokenTypes.VARIABLE_DEF,
155        };
156    }
157
158    @Override
159    public int[] getAcceptableTokens() {
160        return new int[] {
161            TokenTypes.IDENT,
162            TokenTypes.CTOR_DEF,
163            TokenTypes.METHOD_DEF,
164            TokenTypes.SLIST,
165            TokenTypes.OBJBLOCK,
166            TokenTypes.VARIABLE_DEF,
167            TokenTypes.PARAMETER_DEF,
168        };
169    }
170
171    @Override
172    public void visitToken(DetailAST ast) {
173        switch (ast.getType()) {
174            case TokenTypes.OBJBLOCK:
175            case TokenTypes.SLIST:
176            case TokenTypes.METHOD_DEF:
177            case TokenTypes.CTOR_DEF:
178                scopeStack.push(new ScopeData());
179                break;
180
181            case TokenTypes.PARAMETER_DEF:
182                if (!isInLambda(ast)
183                        && !ast.branchContains(TokenTypes.FINAL)
184                        && !isInAbstractOrNativeMethod(ast)
185                        && !ScopeUtils.isInInterfaceBlock(ast)) {
186                    insertParameter(ast);
187                }
188                break;
189            case TokenTypes.VARIABLE_DEF:
190                if (ast.getParent().getType() != TokenTypes.OBJBLOCK
191                        && !ast.branchContains(TokenTypes.FINAL)
192                        && !isVariableInForInit(ast)
193                        && shouldCheckEnhancedForLoopVariable(ast)) {
194                    insertVariable(ast);
195                }
196                break;
197
198            case TokenTypes.IDENT:
199                final int parentType = ast.getParent().getType();
200                if (isAssignOperator(parentType)
201                        && isFirstChild(ast)) {
202                    removeVariable(ast);
203                }
204                break;
205
206            default:
207                throw new IllegalStateException("Incorrect token type");
208        }
209    }
210
211    @Override
212    public void leaveToken(DetailAST ast) {
213        switch (ast.getType()) {
214            case TokenTypes.OBJBLOCK:
215            case TokenTypes.SLIST:
216            case TokenTypes.CTOR_DEF:
217            case TokenTypes.METHOD_DEF:
218                final Map<String, DetailAST> scope = scopeStack.pop().scope;
219                for (DetailAST node : scope.values()) {
220                    log(node.getLineNo(), node.getColumnNo(), MSG_KEY, node
221                        .getText());
222                }
223                break;
224            default:
225                // do nothing
226        }
227    }
228
229    /**
230     * Determines whether enhanced for-loop variable should be checked or not.
231     * @param ast The ast to compare.
232     * @return true if enhanced for-loop variable should be checked.
233     */
234    private boolean shouldCheckEnhancedForLoopVariable(DetailAST ast) {
235        return validateEnhancedForLoopVariable
236                || ast.getParent().getType() != TokenTypes.FOR_EACH_CLAUSE;
237    }
238
239    /**
240     * Insert a parameter at the topmost scope stack.
241     * @param ast the variable to insert.
242     */
243    private void insertParameter(DetailAST ast) {
244        final Map<String, DetailAST> scope = scopeStack.peek().scope;
245        final DetailAST astNode = ast.findFirstToken(TokenTypes.IDENT);
246        scope.put(astNode.getText(), astNode);
247    }
248
249    /**
250     * Insert a variable at the topmost scope stack.
251     * @param ast the variable to insert.
252     */
253    private void insertVariable(DetailAST ast) {
254        final Map<String, DetailAST> scope = scopeStack.peek().scope;
255        final DetailAST astNode = ast.findFirstToken(TokenTypes.IDENT);
256        scope.put(astNode.getText(), astNode);
257        if (!isInitialized(astNode)) {
258            scopeStack.peek().uninitializedVariables.add(astNode);
259        }
260    }
261
262    /**
263     * Check if VARIABLE_DEF is initialized or not.
264     * @param ast VARIABLE_DEF to be checked
265     * @return true if initialized
266     */
267    private static boolean isInitialized(DetailAST ast) {
268        return ast.getParent().getLastChild().getType() == TokenTypes.ASSIGN;
269    }
270
271    /**
272     * Whether the ast is the first child of its parent.
273     * @param ast the ast to check.
274     * @return true if the ast is the first child of its parent.
275     */
276    private static boolean isFirstChild(DetailAST ast) {
277        return ast.getPreviousSibling() == null;
278    }
279
280    /**
281     * Remove the variable from the Stack.
282     * @param ast Variable to remove
283     */
284    private void removeVariable(DetailAST ast) {
285        final Iterator<ScopeData> iterator = scopeStack.descendingIterator();
286        while (iterator.hasNext()) {
287            final ScopeData scopeData = iterator.next();
288            final Map<String, DetailAST> scope = scopeData.scope;
289            final DetailAST storedVariable = scope.get(ast.getText());
290            if (storedVariable != null && isSameVariables(storedVariable, ast)) {
291                if (shouldRemoveVariable(scopeData, ast)) {
292                    scope.remove(ast.getText());
293                }
294                break;
295            }
296        }
297    }
298
299    /**
300     * Whether the variable should be removed from the list of final local variable
301     * candidates.
302     * @param scopeData the scope data of the variable.
303     * @param ast the variable ast.
304     * @return true, if the variable should be removed.
305     */
306    private boolean shouldRemoveVariable(ScopeData scopeData, DetailAST ast) {
307        boolean shouldRemove = true;
308        for (DetailAST variable : scopeData.uninitializedVariables) {
309            if (variable.getText().equals(ast.getText())) {
310
311                // if the variable is declared outside the loop and initialized inside
312                // the loop, then it cannot be declared final, as it can be initialized
313                // more than once in this case
314                if (isInTheSameLoop(variable, ast)) {
315                    shouldRemove = false;
316                }
317                scopeData.uninitializedVariables.remove(variable);
318                break;
319            }
320        }
321        return shouldRemove;
322    }
323
324    /**
325     * Is Arithmetic operator.
326     * @param parentType token AST
327     * @return true is token type is in arithmetic operator
328     */
329    private static boolean isAssignOperator(int parentType) {
330        return Arrays.binarySearch(ASSIGN_OPERATOR_TYPES, parentType) >= 0;
331    }
332
333    /**
334     * Checks if current variable is defined in
335     *  {@link TokenTypes#FOR_INIT for-loop init}, e.g.:
336     * <p>
337     * {@code
338     * for (int i = 0, j = 0; i < j; i++) { . . . }
339     * }
340     * </p>
341     * {@code i, j} are defined in {@link TokenTypes#FOR_INIT for-loop init}
342     * @param variableDef variable definition node.
343     * @return true if variable is defined in {@link TokenTypes#FOR_INIT for-loop init}
344     */
345    private static boolean isVariableInForInit(DetailAST variableDef) {
346        return variableDef.getParent().getType() == TokenTypes.FOR_INIT;
347    }
348
349    /**
350     * Determines whether an AST is a descendant of an abstract or native method.
351     * @param ast the AST to check.
352     * @return true if ast is a descendant of an abstract or native method.
353     */
354    private static boolean isInAbstractOrNativeMethod(DetailAST ast) {
355        boolean abstractOrNative = false;
356        DetailAST parent = ast.getParent();
357        while (parent != null && !abstractOrNative) {
358            if (parent.getType() == TokenTypes.METHOD_DEF) {
359                final DetailAST modifiers =
360                    parent.findFirstToken(TokenTypes.MODIFIERS);
361                abstractOrNative = modifiers.branchContains(TokenTypes.ABSTRACT)
362                        || modifiers.branchContains(TokenTypes.LITERAL_NATIVE);
363            }
364            parent = parent.getParent();
365        }
366        return abstractOrNative;
367    }
368
369    /**
370     * Check if current param is lambda's param.
371     * @param paramDef {@link TokenTypes#PARAMETER_DEF parameter def}.
372     * @return true if current param is lambda's param.
373     */
374    private static boolean isInLambda(DetailAST paramDef) {
375        return paramDef.getParent().getParent().getType() == TokenTypes.LAMBDA;
376    }
377
378    /**
379     * Find the Class, Constructor, Enum or Method in which it is defined.
380     * @param ast Variable for which we want to find the scope in which it is defined
381     * @return ast The Class or Constructor or Method in which it is defined.
382     */
383    private static DetailAST findFirstUpperNamedBlock(DetailAST ast) {
384        DetailAST astTraverse = ast;
385        while (astTraverse.getType() != TokenTypes.METHOD_DEF
386                && astTraverse.getType() != TokenTypes.CLASS_DEF
387                && astTraverse.getType() != TokenTypes.ENUM_DEF
388                && astTraverse.getType() != TokenTypes.CTOR_DEF) {
389            astTraverse = astTraverse.getParent();
390        }
391        return astTraverse;
392    }
393
394    /**
395     * Check if both the Variables are same.
396     * @param ast1 Variable to compare
397     * @param ast2 Variable to compare
398     * @return true if both the variables are same, otherwise false
399     */
400    private static boolean isSameVariables(DetailAST ast1, DetailAST ast2) {
401        final DetailAST classOrMethodOfAst1 =
402            findFirstUpperNamedBlock(ast1);
403        final DetailAST classOrMethodOfAst2 =
404            findFirstUpperNamedBlock(ast2);
405        return classOrMethodOfAst1 == classOrMethodOfAst2;
406    }
407
408    /**
409     * Check if both the variables are in the same loop.
410     * @param ast1 variable to compare.
411     * @param ast2 variable to compare.
412     * @return true if both the variables are in the same loop.
413     */
414    private static boolean isInTheSameLoop(DetailAST ast1, DetailAST ast2) {
415        DetailAST loop1 = ast1.getParent();
416        while (loop1 != null && !isLoopAst(loop1.getType())) {
417            loop1 = loop1.getParent();
418        }
419        DetailAST loop2 = ast2.getParent();
420        while (loop2 != null && !isLoopAst(loop2.getType())) {
421            loop2 = loop2.getParent();
422        }
423        return loop1 == null && loop2 == null
424                || loop1 != null && loop1 == loop2;
425    }
426
427    /**
428     * Checks whether the ast is a loop.
429     * @param ast the ast to check.
430     * @return true if the ast is a loop.
431     */
432    private static boolean isLoopAst(int ast) {
433        return Arrays.binarySearch(LOOP_TYPES, ast) >= 0;
434    }
435
436    /**
437     * Holder for the scope data.
438     */
439    private static class ScopeData {
440        /** Contains variable definitions. */
441        private final Map<String, DetailAST> scope = new HashMap<>();
442
443        /** Contains definitions of uninitialized variables. */
444        private final Deque<DetailAST> uninitializedVariables = new ArrayDeque<>();
445    }
446}