001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2018 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;
028import java.util.Optional;
029
030import com.puppycrawl.tools.checkstyle.FileStatefulCheck;
031import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
032import com.puppycrawl.tools.checkstyle.api.DetailAST;
033import com.puppycrawl.tools.checkstyle.api.TokenTypes;
034import com.puppycrawl.tools.checkstyle.utils.ScopeUtils;
035
036/**
037 * <p>
038 * Ensures that local variables that never get their values changed,
039 * must be declared final.
040 * </p>
041 * <p>
042 * An example of how to configure the check to validate variable definition is:
043 * </p>
044 * <pre>
045 * &lt;module name="FinalLocalVariable"&gt;
046 *     &lt;property name="tokens" value="VARIABLE_DEF"/&gt;
047 * &lt;/module&gt;
048 * </pre>
049 * <p>
050 * By default, this Check skip final validation on
051 *  <a href = "https://docs.oracle.com/javase/specs/jls/se8/html/jls-14.html#jls-14.14.2">
052 * Enhanced For-Loop</a>
053 * </p>
054 * <p>
055 * Option 'validateEnhancedForLoopVariable' could be used to make Check to validate even variable
056 *  from Enhanced For Loop.
057 * </p>
058 * <p>
059 * An example of how to configure the check so that it also validates enhanced For Loop Variable is:
060 * </p>
061 * <pre>
062 * &lt;module name="FinalLocalVariable"&gt;
063 *     &lt;property name="tokens" value="VARIABLE_DEF"/&gt;
064 *     &lt;property name="validateEnhancedForLoopVariable" value="true"/&gt;
065 * &lt;/module&gt;
066 * </pre>
067 * <p>Example:</p>
068 * <p>
069 * {@code
070 * for (int number : myNumbers) { // violation
071 *    System.out.println(number);
072 * }
073 * }
074 * </p>
075 */
076@FileStatefulCheck
077public class FinalLocalVariableCheck extends AbstractCheck {
078
079    /**
080     * A key is pointing to the warning message text in "messages.properties"
081     * file.
082     */
083    public static final String MSG_KEY = "final.variable";
084
085    /**
086     * Assign operator types.
087     */
088    private static final int[] ASSIGN_OPERATOR_TYPES = {
089        TokenTypes.POST_INC,
090        TokenTypes.POST_DEC,
091        TokenTypes.ASSIGN,
092        TokenTypes.PLUS_ASSIGN,
093        TokenTypes.MINUS_ASSIGN,
094        TokenTypes.STAR_ASSIGN,
095        TokenTypes.DIV_ASSIGN,
096        TokenTypes.MOD_ASSIGN,
097        TokenTypes.SR_ASSIGN,
098        TokenTypes.BSR_ASSIGN,
099        TokenTypes.SL_ASSIGN,
100        TokenTypes.BAND_ASSIGN,
101        TokenTypes.BXOR_ASSIGN,
102        TokenTypes.BOR_ASSIGN,
103        TokenTypes.INC,
104        TokenTypes.DEC,
105    };
106
107    /**
108     * Loop types.
109     */
110    private static final int[] LOOP_TYPES = {
111        TokenTypes.LITERAL_FOR,
112        TokenTypes.LITERAL_WHILE,
113        TokenTypes.LITERAL_DO,
114    };
115
116    /** Scope Deque. */
117    private final Deque<ScopeData> scopeStack = new ArrayDeque<>();
118
119    /** Uninitialized variables of previous scope. */
120    private final Deque<Deque<DetailAST>> prevScopeUninitializedVariables =
121            new ArrayDeque<>();
122
123    /** Assigned variables of current scope. */
124    private final Deque<Deque<DetailAST>> currentScopeAssignedVariables =
125            new ArrayDeque<>();
126
127    /** Controls whether to check enhanced for-loop variable. */
128    private boolean validateEnhancedForLoopVariable;
129
130    static {
131        // Array sorting for binary search
132        Arrays.sort(ASSIGN_OPERATOR_TYPES);
133        Arrays.sort(LOOP_TYPES);
134    }
135
136    /**
137     * Whether to check enhanced for-loop variable or not.
138     * @param validateEnhancedForLoopVariable whether to check for-loop variable
139     */
140    public final void setValidateEnhancedForLoopVariable(boolean validateEnhancedForLoopVariable) {
141        this.validateEnhancedForLoopVariable = validateEnhancedForLoopVariable;
142    }
143
144    @Override
145    public int[] getRequiredTokens() {
146        return new int[] {
147            TokenTypes.IDENT,
148            TokenTypes.CTOR_DEF,
149            TokenTypes.METHOD_DEF,
150            TokenTypes.SLIST,
151            TokenTypes.OBJBLOCK,
152            TokenTypes.LITERAL_BREAK,
153        };
154    }
155
156    @Override
157    public int[] getDefaultTokens() {
158        return new int[] {
159            TokenTypes.IDENT,
160            TokenTypes.CTOR_DEF,
161            TokenTypes.METHOD_DEF,
162            TokenTypes.SLIST,
163            TokenTypes.OBJBLOCK,
164            TokenTypes.LITERAL_BREAK,
165            TokenTypes.VARIABLE_DEF,
166        };
167    }
168
169    @Override
170    public int[] getAcceptableTokens() {
171        return new int[] {
172            TokenTypes.IDENT,
173            TokenTypes.CTOR_DEF,
174            TokenTypes.METHOD_DEF,
175            TokenTypes.SLIST,
176            TokenTypes.OBJBLOCK,
177            TokenTypes.LITERAL_BREAK,
178            TokenTypes.VARIABLE_DEF,
179            TokenTypes.PARAMETER_DEF,
180        };
181    }
182
183    // -@cs[CyclomaticComplexity] The only optimization which can be done here is moving CASE-block
184    // expressions to separate methods, but that will not increase readability.
185    @Override
186    public void visitToken(DetailAST ast) {
187        switch (ast.getType()) {
188            case TokenTypes.OBJBLOCK:
189            case TokenTypes.METHOD_DEF:
190            case TokenTypes.CTOR_DEF:
191                scopeStack.push(new ScopeData());
192                break;
193            case TokenTypes.SLIST:
194                currentScopeAssignedVariables.push(new ArrayDeque<>());
195                if (ast.getParent().getType() != TokenTypes.CASE_GROUP
196                    || ast.getParent().getParent().findFirstToken(TokenTypes.CASE_GROUP)
197                    == ast.getParent()) {
198                    storePrevScopeUninitializedVariableData();
199                    scopeStack.push(new ScopeData());
200                }
201                break;
202            case TokenTypes.PARAMETER_DEF:
203                if (!isInLambda(ast)
204                        && ast.findFirstToken(TokenTypes.MODIFIERS)
205                            .findFirstToken(TokenTypes.FINAL) == null
206                        && !isInAbstractOrNativeMethod(ast)
207                        && !ScopeUtils.isInInterfaceBlock(ast)
208                        && !isMultipleTypeCatch(ast)) {
209                    insertParameter(ast);
210                }
211                break;
212            case TokenTypes.VARIABLE_DEF:
213                if (ast.getParent().getType() != TokenTypes.OBJBLOCK
214                        && ast.findFirstToken(TokenTypes.MODIFIERS)
215                            .findFirstToken(TokenTypes.FINAL) == null
216                        && !isVariableInForInit(ast)
217                        && shouldCheckEnhancedForLoopVariable(ast)) {
218                    insertVariable(ast);
219                }
220                break;
221            case TokenTypes.IDENT:
222                final int parentType = ast.getParent().getType();
223                if (isAssignOperator(parentType) && isFirstChild(ast)) {
224                    final Optional<FinalVariableCandidate> candidate = getFinalCandidate(ast);
225                    if (candidate.isPresent()) {
226                        determineAssignmentConditions(ast, candidate.get());
227                        currentScopeAssignedVariables.peek().add(ast);
228                    }
229                    removeFinalVariableCandidateFromStack(ast);
230                }
231                break;
232            case TokenTypes.LITERAL_BREAK:
233                scopeStack.peek().containsBreak = true;
234                break;
235            default:
236                throw new IllegalStateException("Incorrect token type");
237        }
238    }
239
240    @Override
241    public void leaveToken(DetailAST ast) {
242        Map<String, FinalVariableCandidate> scope = null;
243        switch (ast.getType()) {
244            case TokenTypes.OBJBLOCK:
245            case TokenTypes.CTOR_DEF:
246            case TokenTypes.METHOD_DEF:
247                scope = scopeStack.pop().scope;
248                break;
249            case TokenTypes.SLIST:
250                // -@cs[MoveVariableInsideIf] assignment value is modified later so it can't be
251                // moved
252                final Deque<DetailAST> prevScopeUninitializedVariableData =
253                    prevScopeUninitializedVariables.peek();
254                boolean containsBreak = false;
255                if (ast.getParent().getType() != TokenTypes.CASE_GROUP
256                    || findLastChildWhichContainsSpecifiedToken(ast.getParent().getParent(),
257                            TokenTypes.CASE_GROUP, TokenTypes.SLIST) == ast.getParent()) {
258                    containsBreak = scopeStack.peek().containsBreak;
259                    scope = scopeStack.pop().scope;
260                    prevScopeUninitializedVariables.pop();
261                }
262                final DetailAST parent = ast.getParent();
263                if (containsBreak || shouldUpdateUninitializedVariables(parent)) {
264                    updateAllUninitializedVariables(prevScopeUninitializedVariableData);
265                }
266                updateCurrentScopeAssignedVariables();
267                break;
268            default:
269                // do nothing
270        }
271        if (scope != null) {
272            for (FinalVariableCandidate candidate : scope.values()) {
273                final DetailAST ident = candidate.variableIdent;
274                log(ident.getLineNo(), ident.getColumnNo(), MSG_KEY, ident.getText());
275            }
276        }
277    }
278
279    /**
280     * Update assigned variables in a temporary stack.
281     */
282    private void updateCurrentScopeAssignedVariables() {
283        // -@cs[MoveVariableInsideIf] assignment value is a modification call so it can't be moved
284        final Deque<DetailAST> poppedScopeAssignedVariableData =
285                currentScopeAssignedVariables.pop();
286        final Deque<DetailAST> currentScopeAssignedVariableData =
287                currentScopeAssignedVariables.peek();
288        if (currentScopeAssignedVariableData != null) {
289            currentScopeAssignedVariableData.addAll(poppedScopeAssignedVariableData);
290        }
291    }
292
293    /**
294     * Determines identifier assignment conditions (assigned or already assigned).
295     * @param ident identifier.
296     * @param candidate final local variable candidate.
297     */
298    private static void determineAssignmentConditions(DetailAST ident,
299                                                      FinalVariableCandidate candidate) {
300        if (candidate.assigned) {
301            if (!isInSpecificCodeBlock(ident, TokenTypes.LITERAL_ELSE)
302                    && !isInSpecificCodeBlock(ident, TokenTypes.CASE_GROUP)) {
303                candidate.alreadyAssigned = true;
304            }
305        }
306        else {
307            candidate.assigned = true;
308        }
309    }
310
311    /**
312     * Checks whether the scope of a node is restricted to a specific code block.
313     * @param node node.
314     * @param blockType block type.
315     * @return true if the scope of a node is restricted to a specific code block.
316     */
317    private static boolean isInSpecificCodeBlock(DetailAST node, int blockType) {
318        boolean returnValue = false;
319        for (DetailAST token = node.getParent(); token != null; token = token.getParent()) {
320            final int type = token.getType();
321            if (type == blockType) {
322                returnValue = true;
323                break;
324            }
325        }
326        return returnValue;
327    }
328
329    /**
330     * Gets final variable candidate for ast.
331     * @param ast ast.
332     * @return Optional of {@link FinalVariableCandidate} for ast from scopeStack.
333     */
334    private Optional<FinalVariableCandidate> getFinalCandidate(DetailAST ast) {
335        Optional<FinalVariableCandidate> result = Optional.empty();
336        final Iterator<ScopeData> iterator = scopeStack.descendingIterator();
337        while (iterator.hasNext() && !result.isPresent()) {
338            final ScopeData scopeData = iterator.next();
339            result = scopeData.findFinalVariableCandidateForAst(ast);
340        }
341        return result;
342    }
343
344    /**
345     * Store un-initialized variables in a temporary stack for future use.
346     */
347    private void storePrevScopeUninitializedVariableData() {
348        final ScopeData scopeData = scopeStack.peek();
349        final Deque<DetailAST> prevScopeUninitializedVariableData =
350                new ArrayDeque<>();
351        scopeData.uninitializedVariables.forEach(prevScopeUninitializedVariableData::push);
352        prevScopeUninitializedVariables.push(prevScopeUninitializedVariableData);
353    }
354
355    /**
356     * Update current scope data uninitialized variable according to the whole scope data.
357     * @param prevScopeUninitializedVariableData variable for previous stack of uninitialized
358     *     variables
359     * @noinspection MethodParameterNamingConvention
360     */
361    private void updateAllUninitializedVariables(
362            Deque<DetailAST> prevScopeUninitializedVariableData) {
363        // Check for only previous scope
364        updateUninitializedVariables(prevScopeUninitializedVariableData);
365        // Check for rest of the scope
366        prevScopeUninitializedVariables.forEach(this::updateUninitializedVariables);
367    }
368
369    /**
370     * Update current scope data uninitialized variable according to the specific scope data.
371     * @param scopeUninitializedVariableData variable for specific stack of uninitialized variables
372     */
373    private void updateUninitializedVariables(Deque<DetailAST> scopeUninitializedVariableData) {
374        final Iterator<DetailAST> iterator = currentScopeAssignedVariables.peek().iterator();
375        while (iterator.hasNext()) {
376            final DetailAST assignedVariable = iterator.next();
377            for (DetailAST variable : scopeUninitializedVariableData) {
378                for (ScopeData scopeData : scopeStack) {
379                    final FinalVariableCandidate candidate =
380                        scopeData.scope.get(variable.getText());
381                    DetailAST storedVariable = null;
382                    if (candidate != null) {
383                        storedVariable = candidate.variableIdent;
384                    }
385                    if (storedVariable != null
386                            && isSameVariables(storedVariable, variable)
387                            && isSameVariables(assignedVariable, variable)) {
388                        scopeData.uninitializedVariables.push(variable);
389                        iterator.remove();
390                    }
391                }
392            }
393        }
394    }
395
396    /**
397     * If token is LITERAL_IF and there is an {@code else} following or token is CASE_GROUP and
398     * there is another {@code case} following, then update the uninitialized variables.
399     * @param ast token to be checked
400     * @return true if should be updated, else false
401     */
402    private static boolean shouldUpdateUninitializedVariables(DetailAST ast) {
403        return isIfTokenWithAnElseFollowing(ast) || isCaseTokenWithAnotherCaseFollowing(ast);
404    }
405
406    /**
407     * If token is LITERAL_IF and there is an {@code else} following.
408     * @param ast token to be checked
409     * @return true if token is LITERAL_IF and there is an {@code else} following, else false
410     */
411    private static boolean isIfTokenWithAnElseFollowing(DetailAST ast) {
412        return ast.getType() == TokenTypes.LITERAL_IF
413                && ast.getLastChild().getType() == TokenTypes.LITERAL_ELSE;
414    }
415
416    /**
417     * If token is CASE_GROUP and there is another {@code case} following.
418     * @param ast token to be checked
419     * @return true if token is CASE_GROUP and there is another {@code case} following, else false
420     */
421    private static boolean isCaseTokenWithAnotherCaseFollowing(DetailAST ast) {
422        return ast.getType() == TokenTypes.CASE_GROUP
423                && findLastChildWhichContainsSpecifiedToken(
424                        ast.getParent(), TokenTypes.CASE_GROUP, TokenTypes.SLIST) != ast;
425    }
426
427    /**
428     * Returns the last child token that makes a specified type and contains containType in
429     * its branch.
430     * @param ast token to be tested
431     * @param childType the token type to match
432     * @param containType the token type which has to be present in the branch
433     * @return the matching token, or null if no match
434     */
435    private static DetailAST findLastChildWhichContainsSpecifiedToken(DetailAST ast, int childType,
436                                                              int containType) {
437        DetailAST returnValue = null;
438        for (DetailAST astIterator = ast.getFirstChild(); astIterator != null;
439                astIterator = astIterator.getNextSibling()) {
440            if (astIterator.getType() == childType
441                    && astIterator.findFirstToken(containType) != null) {
442                returnValue = astIterator;
443            }
444        }
445        return returnValue;
446    }
447
448    /**
449     * Determines whether enhanced for-loop variable should be checked or not.
450     * @param ast The ast to compare.
451     * @return true if enhanced for-loop variable should be checked.
452     */
453    private boolean shouldCheckEnhancedForLoopVariable(DetailAST ast) {
454        return validateEnhancedForLoopVariable
455                || ast.getParent().getType() != TokenTypes.FOR_EACH_CLAUSE;
456    }
457
458    /**
459     * Insert a parameter at the topmost scope stack.
460     * @param ast the variable to insert.
461     */
462    private void insertParameter(DetailAST ast) {
463        final Map<String, FinalVariableCandidate> scope = scopeStack.peek().scope;
464        final DetailAST astNode = ast.findFirstToken(TokenTypes.IDENT);
465        scope.put(astNode.getText(), new FinalVariableCandidate(astNode));
466    }
467
468    /**
469     * Insert a variable at the topmost scope stack.
470     * @param ast the variable to insert.
471     */
472    private void insertVariable(DetailAST ast) {
473        final Map<String, FinalVariableCandidate> scope = scopeStack.peek().scope;
474        final DetailAST astNode = ast.findFirstToken(TokenTypes.IDENT);
475        scope.put(astNode.getText(), new FinalVariableCandidate(astNode));
476        if (!isInitialized(astNode)) {
477            scopeStack.peek().uninitializedVariables.add(astNode);
478        }
479    }
480
481    /**
482     * Check if VARIABLE_DEF is initialized or not.
483     * @param ast VARIABLE_DEF to be checked
484     * @return true if initialized
485     */
486    private static boolean isInitialized(DetailAST ast) {
487        return ast.getParent().getLastChild().getType() == TokenTypes.ASSIGN;
488    }
489
490    /**
491     * Whether the ast is the first child of its parent.
492     * @param ast the ast to check.
493     * @return true if the ast is the first child of its parent.
494     */
495    private static boolean isFirstChild(DetailAST ast) {
496        return ast.getPreviousSibling() == null;
497    }
498
499    /**
500     * Removes the final variable candidate from the Stack.
501     * @param ast variable to remove.
502     */
503    private void removeFinalVariableCandidateFromStack(DetailAST ast) {
504        final Iterator<ScopeData> iterator = scopeStack.descendingIterator();
505        while (iterator.hasNext()) {
506            final ScopeData scopeData = iterator.next();
507            final Map<String, FinalVariableCandidate> scope = scopeData.scope;
508            final FinalVariableCandidate candidate = scope.get(ast.getText());
509            DetailAST storedVariable = null;
510            if (candidate != null) {
511                storedVariable = candidate.variableIdent;
512            }
513            if (storedVariable != null && isSameVariables(storedVariable, ast)) {
514                if (shouldRemoveFinalVariableCandidate(scopeData, ast)) {
515                    scope.remove(ast.getText());
516                }
517                break;
518            }
519        }
520    }
521
522    /**
523     * Check if given parameter definition is a multiple type catch.
524     * @param parameterDefAst parameter definition
525     * @return true if it is a multiple type catch, false otherwise
526     */
527    private static boolean isMultipleTypeCatch(DetailAST parameterDefAst) {
528        final DetailAST typeAst = parameterDefAst.findFirstToken(TokenTypes.TYPE);
529        return typeAst.getFirstChild().getType() == TokenTypes.BOR;
530    }
531
532    /**
533     * Whether the final variable candidate should be removed from the list of final local variable
534     * candidates.
535     * @param scopeData the scope data of the variable.
536     * @param ast the variable ast.
537     * @return true, if the variable should be removed.
538     */
539    private static boolean shouldRemoveFinalVariableCandidate(ScopeData scopeData, DetailAST ast) {
540        boolean shouldRemove = true;
541        for (DetailAST variable : scopeData.uninitializedVariables) {
542            if (variable.getText().equals(ast.getText())) {
543                // if the variable is declared outside the loop and initialized inside
544                // the loop, then it cannot be declared final, as it can be initialized
545                // more than once in this case
546                if (isInTheSameLoop(variable, ast) || !isUseOfExternalVariableInsideLoop(ast)) {
547                    final FinalVariableCandidate candidate = scopeData.scope.get(ast.getText());
548                    shouldRemove = candidate.alreadyAssigned;
549                }
550                scopeData.uninitializedVariables.remove(variable);
551                break;
552            }
553        }
554        return shouldRemove;
555    }
556
557    /**
558     * Checks whether a variable which is declared outside loop is used inside loop.
559     * For example:
560     * <p>
561     * {@code
562     * int x;
563     * for (int i = 0, j = 0; i < j; i++) {
564     *     x = 5;
565     * }
566     * }
567     * </p>
568     * @param variable variable.
569     * @return true if a variable which is declared outside loop is used inside loop.
570     */
571    private static boolean isUseOfExternalVariableInsideLoop(DetailAST variable) {
572        DetailAST loop2 = variable.getParent();
573        while (loop2 != null
574            && !isLoopAst(loop2.getType())) {
575            loop2 = loop2.getParent();
576        }
577        return loop2 != null;
578    }
579
580    /**
581     * Is Arithmetic operator.
582     * @param parentType token AST
583     * @return true is token type is in arithmetic operator
584     */
585    private static boolean isAssignOperator(int parentType) {
586        return Arrays.binarySearch(ASSIGN_OPERATOR_TYPES, parentType) >= 0;
587    }
588
589    /**
590     * Checks if current variable is defined in
591     *  {@link TokenTypes#FOR_INIT for-loop init}, e.g.:
592     * <p>
593     * {@code
594     * for (int i = 0, j = 0; i < j; i++) { . . . }
595     * }
596     * </p>
597     * {@code i, j} are defined in {@link TokenTypes#FOR_INIT for-loop init}
598     * @param variableDef variable definition node.
599     * @return true if variable is defined in {@link TokenTypes#FOR_INIT for-loop init}
600     */
601    private static boolean isVariableInForInit(DetailAST variableDef) {
602        return variableDef.getParent().getType() == TokenTypes.FOR_INIT;
603    }
604
605    /**
606     * Determines whether an AST is a descendant of an abstract or native method.
607     * @param ast the AST to check.
608     * @return true if ast is a descendant of an abstract or native method.
609     */
610    private static boolean isInAbstractOrNativeMethod(DetailAST ast) {
611        boolean abstractOrNative = false;
612        DetailAST parent = ast.getParent();
613        while (parent != null && !abstractOrNative) {
614            if (parent.getType() == TokenTypes.METHOD_DEF) {
615                final DetailAST modifiers =
616                    parent.findFirstToken(TokenTypes.MODIFIERS);
617                abstractOrNative = modifiers.findFirstToken(TokenTypes.ABSTRACT) != null
618                        || modifiers.findFirstToken(TokenTypes.LITERAL_NATIVE) != null;
619            }
620            parent = parent.getParent();
621        }
622        return abstractOrNative;
623    }
624
625    /**
626     * Check if current param is lambda's param.
627     * @param paramDef {@link TokenTypes#PARAMETER_DEF parameter def}.
628     * @return true if current param is lambda's param.
629     */
630    private static boolean isInLambda(DetailAST paramDef) {
631        return paramDef.getParent().getParent().getType() == TokenTypes.LAMBDA;
632    }
633
634    /**
635     * Find the Class, Constructor, Enum, Method, or Field in which it is defined.
636     * @param ast Variable for which we want to find the scope in which it is defined
637     * @return ast The Class or Constructor or Method in which it is defined.
638     */
639    private static DetailAST findFirstUpperNamedBlock(DetailAST ast) {
640        DetailAST astTraverse = ast;
641        while (astTraverse.getType() != TokenTypes.METHOD_DEF
642                && astTraverse.getType() != TokenTypes.CLASS_DEF
643                && astTraverse.getType() != TokenTypes.ENUM_DEF
644                && astTraverse.getType() != TokenTypes.CTOR_DEF
645                && !ScopeUtils.isClassFieldDef(astTraverse)) {
646            astTraverse = astTraverse.getParent();
647        }
648        return astTraverse;
649    }
650
651    /**
652     * Check if both the Variables are same.
653     * @param ast1 Variable to compare
654     * @param ast2 Variable to compare
655     * @return true if both the variables are same, otherwise false
656     */
657    private static boolean isSameVariables(DetailAST ast1, DetailAST ast2) {
658        final DetailAST classOrMethodOfAst1 =
659            findFirstUpperNamedBlock(ast1);
660        final DetailAST classOrMethodOfAst2 =
661            findFirstUpperNamedBlock(ast2);
662        return classOrMethodOfAst1 == classOrMethodOfAst2 && ast1.getText().equals(ast2.getText());
663    }
664
665    /**
666     * Check if both the variables are in the same loop.
667     * @param ast1 variable to compare.
668     * @param ast2 variable to compare.
669     * @return true if both the variables are in the same loop.
670     */
671    private static boolean isInTheSameLoop(DetailAST ast1, DetailAST ast2) {
672        DetailAST loop1 = ast1.getParent();
673        while (loop1 != null && !isLoopAst(loop1.getType())) {
674            loop1 = loop1.getParent();
675        }
676        DetailAST loop2 = ast2.getParent();
677        while (loop2 != null && !isLoopAst(loop2.getType())) {
678            loop2 = loop2.getParent();
679        }
680        return loop1 != null && loop1 == loop2;
681    }
682
683    /**
684     * Checks whether the ast is a loop.
685     * @param ast the ast to check.
686     * @return true if the ast is a loop.
687     */
688    private static boolean isLoopAst(int ast) {
689        return Arrays.binarySearch(LOOP_TYPES, ast) >= 0;
690    }
691
692    /**
693     * Holder for the scope data.
694     */
695    private static class ScopeData {
696
697        /** Contains variable definitions. */
698        private final Map<String, FinalVariableCandidate> scope = new HashMap<>();
699
700        /** Contains definitions of uninitialized variables. */
701        private final Deque<DetailAST> uninitializedVariables = new ArrayDeque<>();
702
703        /** Whether there is a {@code break} in the scope. */
704        private boolean containsBreak;
705
706        /**
707         * Searches for final local variable candidate for ast in the scope.
708         * @param ast ast.
709         * @return Optional of {@link FinalVariableCandidate}.
710         */
711        public Optional<FinalVariableCandidate> findFinalVariableCandidateForAst(DetailAST ast) {
712            Optional<FinalVariableCandidate> result = Optional.empty();
713            DetailAST storedVariable = null;
714            final Optional<FinalVariableCandidate> candidate =
715                Optional.ofNullable(scope.get(ast.getText()));
716            if (candidate.isPresent()) {
717                storedVariable = candidate.get().variableIdent;
718            }
719            if (storedVariable != null && isSameVariables(storedVariable, ast)) {
720                result = candidate;
721            }
722            return result;
723        }
724
725    }
726
727    /**Represents information about final local variable candidate. */
728    private static class FinalVariableCandidate {
729
730        /** Identifier token. */
731        private final DetailAST variableIdent;
732        /** Whether the variable is assigned. */
733        private boolean assigned;
734        /** Whether the variable is already assigned. */
735        private boolean alreadyAssigned;
736
737        /**
738         * Creates new instance.
739         * @param variableIdent variable identifier.
740         */
741        FinalVariableCandidate(DetailAST variableIdent) {
742            this.variableIdent = variableIdent;
743        }
744
745    }
746
747}