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