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