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