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.Collections;
025import java.util.Deque;
026import java.util.HashMap;
027import java.util.HashSet;
028import java.util.LinkedList;
029import java.util.Map;
030import java.util.Queue;
031import java.util.Set;
032import java.util.stream.Collectors;
033
034import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
035import com.puppycrawl.tools.checkstyle.api.DetailAST;
036import com.puppycrawl.tools.checkstyle.api.TokenTypes;
037import com.puppycrawl.tools.checkstyle.utils.CheckUtils;
038import com.puppycrawl.tools.checkstyle.utils.ScopeUtils;
039
040/**
041 * <p>Checks that code doesn't rely on the &quot;this&quot; default.
042 * That is references to instance variables and methods of the present
043 * object are explicitly of the form &quot;this.varName&quot; or
044 * &quot;this.methodName(args)&quot;.
045 * </p>
046 * Check has the following options:
047 * <p><b>checkFields</b> - whether to check references to fields. Default value is <b>true</b>.</p>
048 * <p><b>checkMethods</b> - whether to check references to methods.
049 * Default value is <b>true</b>.</p>
050 * <p><b>validateOnlyOverlapping</b> - whether to check only overlapping by variables or
051 * arguments. Default value is <b>true</b>.</p>
052 *
053 * <p>Warning: the Check is very controversial if 'validateOnlyOverlapping' option is set to 'false'
054 * and not that actual nowadays.</p>
055 *
056 * <p>Examples of use:
057 * <pre>
058 * &lt;module name=&quot;RequireThis&quot;/&gt;
059 * </pre>
060 * An example of how to configure to check {@code this} qualifier for
061 * methods only:
062 * <pre>
063 * &lt;module name=&quot;RequireThis&quot;&gt;
064 *   &lt;property name=&quot;checkFields&quot; value=&quot;false&quot;/&gt;
065 *   &lt;property name=&quot;checkMethods&quot; value=&quot;true&quot;/&gt;
066 * &lt;/module&gt;
067 * </pre>
068 *
069 * <p>Rationale:</p>
070 * <ol>
071 *   <li>
072 *     The same notation/habit for C++ and Java (C++ have global methods, so having
073 *     &quot;this.&quot; do make sense in it to distinguish call of method of class
074 *     instead of global).
075 *   </li>
076 *   <li>
077 *     Non-IDE development (ease of refactoring, some clearness to distinguish
078 *     static and non-static methods).
079 *   </li>
080 * </ol>
081 *
082 * <p>Limitations: Nothing is currently done about static variables
083 * or catch-blocks.  Static methods invoked on a class name seem to be OK;
084 * both the class name and the method name have a DOT parent.
085 * Non-static methods invoked on either this or a variable name seem to be
086 * OK, likewise.</p>
087 *
088 * @author Stephen Bloch
089 * @author o_sukhodolsky
090 * @author Andrei Selkin
091 */
092public class RequireThisCheck extends AbstractCheck {
093
094    /**
095     * A key is pointing to the warning message text in "messages.properties"
096     * file.
097     */
098    public static final String MSG_METHOD = "require.this.method";
099    /**
100     * A key is pointing to the warning message text in "messages.properties"
101     * file.
102     */
103    public static final String MSG_VARIABLE = "require.this.variable";
104
105    /** Set of all declaration tokens. */
106    private static final Set<Integer> DECLARATION_TOKENS = Collections.unmodifiableSet(
107        Arrays.stream(new Integer[] {
108            TokenTypes.VARIABLE_DEF,
109            TokenTypes.CTOR_DEF,
110            TokenTypes.METHOD_DEF,
111            TokenTypes.CLASS_DEF,
112            TokenTypes.ENUM_DEF,
113            TokenTypes.INTERFACE_DEF,
114            TokenTypes.PARAMETER_DEF,
115            TokenTypes.TYPE_ARGUMENT,
116        }).collect(Collectors.toSet()));
117    /** Set of all assign tokens. */
118    private static final Set<Integer> ASSIGN_TOKENS = Collections.unmodifiableSet(
119        Arrays.stream(new Integer[] {
120            TokenTypes.ASSIGN,
121            TokenTypes.PLUS_ASSIGN,
122            TokenTypes.STAR_ASSIGN,
123            TokenTypes.DIV_ASSIGN,
124            TokenTypes.MOD_ASSIGN,
125            TokenTypes.SR_ASSIGN,
126            TokenTypes.BSR_ASSIGN,
127            TokenTypes.SL_ASSIGN,
128            TokenTypes.BAND_ASSIGN,
129            TokenTypes.BXOR_ASSIGN,
130        }).collect(Collectors.toSet()));
131    /** Set of all compound assign tokens. */
132    private static final Set<Integer> COMPOUND_ASSIGN_TOKENS = Collections.unmodifiableSet(
133        Arrays.stream(new Integer[] {
134            TokenTypes.PLUS_ASSIGN,
135            TokenTypes.STAR_ASSIGN,
136            TokenTypes.DIV_ASSIGN,
137            TokenTypes.MOD_ASSIGN,
138            TokenTypes.SR_ASSIGN,
139            TokenTypes.BSR_ASSIGN,
140            TokenTypes.SL_ASSIGN,
141            TokenTypes.BAND_ASSIGN,
142            TokenTypes.BXOR_ASSIGN,
143        }).collect(Collectors.toSet()));
144
145    /** Tree of all the parsed frames. */
146    private Map<DetailAST, AbstractFrame> frames;
147
148    /** Frame for the currently processed AST. */
149    private AbstractFrame current;
150
151    /** Whether we should check fields usage. */
152    private boolean checkFields = true;
153    /** Whether we should check methods usage. */
154    private boolean checkMethods = true;
155    /** Whether we should check only overlapping by variables or arguments. */
156    private boolean validateOnlyOverlapping = true;
157
158    /**
159     * Setter for checkFields property.
160     * @param checkFields should we check fields usage or not.
161     */
162    public void setCheckFields(boolean checkFields) {
163        this.checkFields = checkFields;
164    }
165
166    /**
167     * Setter for checkMethods property.
168     * @param checkMethods should we check methods usage or not.
169     */
170    public void setCheckMethods(boolean checkMethods) {
171        this.checkMethods = checkMethods;
172    }
173
174    /**
175     * Setter for validateOnlyOverlapping property.
176     * @param validateOnlyOverlapping should we check only overlapping by variables or arguments.
177     */
178    public void setValidateOnlyOverlapping(boolean validateOnlyOverlapping) {
179        this.validateOnlyOverlapping = validateOnlyOverlapping;
180    }
181
182    @Override
183    public int[] getDefaultTokens() {
184        return getAcceptableTokens();
185    }
186
187    @Override
188    public int[] getRequiredTokens() {
189        return getAcceptableTokens();
190    }
191
192    @Override
193    public int[] getAcceptableTokens() {
194        return new int[] {
195            TokenTypes.CLASS_DEF,
196            TokenTypes.INTERFACE_DEF,
197            TokenTypes.ENUM_DEF,
198            TokenTypes.CTOR_DEF,
199            TokenTypes.METHOD_DEF,
200            TokenTypes.SLIST,
201            TokenTypes.IDENT,
202        };
203    }
204
205    @Override
206    public void beginTree(DetailAST rootAST) {
207        frames = new HashMap<>();
208        current = null;
209
210        final Deque<AbstractFrame> frameStack = new LinkedList<>();
211        DetailAST curNode = rootAST;
212        while (curNode != null) {
213            collectDeclarations(frameStack, curNode);
214            DetailAST toVisit = curNode.getFirstChild();
215            while (curNode != null && toVisit == null) {
216                endCollectingDeclarations(frameStack, curNode);
217                toVisit = curNode.getNextSibling();
218                if (toVisit == null) {
219                    curNode = curNode.getParent();
220                }
221            }
222            curNode = toVisit;
223        }
224    }
225
226    @Override
227    public void visitToken(DetailAST ast) {
228        switch (ast.getType()) {
229            case TokenTypes.IDENT :
230                processIdent(ast);
231                break;
232            case TokenTypes.CLASS_DEF :
233            case TokenTypes.INTERFACE_DEF :
234            case TokenTypes.ENUM_DEF :
235            case TokenTypes.ANNOTATION_DEF :
236            case TokenTypes.SLIST :
237            case TokenTypes.METHOD_DEF :
238            case TokenTypes.CTOR_DEF :
239                current = frames.get(ast);
240                break;
241            default :
242                // do nothing
243        }
244    }
245
246    /**
247     * Checks if a given IDENT is method call or field name which
248     * requires explicit {@code this} qualifier.
249     * @param ast IDENT to check.
250     */
251    private void processIdent(DetailAST ast) {
252        final int parentType = ast.getParent().getType();
253        switch (parentType) {
254            case TokenTypes.ANNOTATION_MEMBER_VALUE_PAIR:
255            case TokenTypes.ANNOTATION:
256            case TokenTypes.ANNOTATION_FIELD_DEF:
257                // no need to check annotations content
258                break;
259            case TokenTypes.METHOD_CALL:
260                if (checkMethods) {
261                    final AbstractFrame frame = getMethodWithoutThis(ast);
262                    if (frame != null) {
263                        logViolation(MSG_METHOD, ast, frame);
264                    }
265                }
266                break;
267            default:
268                if (checkFields) {
269                    final AbstractFrame frame = getFieldWithoutThis(ast, parentType);
270                    if (frame != null) {
271                        logViolation(MSG_VARIABLE, ast, frame);
272                    }
273                }
274                break;
275        }
276    }
277
278    /**
279     * Helper method to log a LocalizedMessage.
280     * @param ast a node to get line id column numbers associated with the message.
281     * @param msgKey key to locale message format.
282     * @param frame the class frame where the violation is found.
283     */
284    private void logViolation(String msgKey, DetailAST ast, AbstractFrame frame) {
285        if (frame.getFrameName().equals(getNearestClassFrameName())) {
286            log(ast, msgKey, ast.getText(), "");
287        }
288        else if (!(frame instanceof AnonymousClassFrame)) {
289            log(ast, msgKey, ast.getText(), frame.getFrameName() + '.');
290        }
291    }
292
293    /**
294     * Returns the frame where the field is declared, if the given field is used without
295     * 'this', and null otherwise.
296     * @param ast field definition ast token.
297     * @param parentType type of the parent.
298     * @return the frame where the field is declared, if the given field is used without
299     *         'this' and null otherwise.
300     */
301    private AbstractFrame getFieldWithoutThis(DetailAST ast, int parentType) {
302        final boolean importOrPackage = ScopeUtils.getSurroundingScope(ast) == null;
303        final boolean methodNameInMethodCall = parentType == TokenTypes.DOT
304                && ast.getPreviousSibling() != null;
305        final boolean typeName = parentType == TokenTypes.TYPE
306                || parentType == TokenTypes.LITERAL_NEW;
307        AbstractFrame frame = null;
308
309        if (!importOrPackage
310                && !methodNameInMethodCall
311                && !typeName
312                && !isDeclarationToken(parentType)) {
313            final AbstractFrame fieldFrame = findClassFrame(ast, false);
314
315            if (fieldFrame != null && ((ClassFrame) fieldFrame).hasInstanceMember(ast)) {
316                frame = getClassFrameWhereViolationIsFound(ast);
317            }
318        }
319        return frame;
320    }
321
322    /**
323     * Parses the next AST for declarations.
324     * @param frameStack stack containing the FrameTree being built.
325     * @param ast AST to parse.
326     */
327    private static void collectDeclarations(Deque<AbstractFrame> frameStack, DetailAST ast) {
328        final AbstractFrame frame = frameStack.peek();
329        switch (ast.getType()) {
330            case TokenTypes.VARIABLE_DEF :
331                collectVariableDeclarations(ast, frame);
332                break;
333            case TokenTypes.PARAMETER_DEF :
334                if (!CheckUtils.isReceiverParameter(ast)) {
335                    final DetailAST parameterIdent = ast.findFirstToken(TokenTypes.IDENT);
336                    frame.addIdent(parameterIdent);
337                }
338                break;
339            case TokenTypes.CLASS_DEF :
340            case TokenTypes.INTERFACE_DEF :
341            case TokenTypes.ENUM_DEF :
342            case TokenTypes.ANNOTATION_DEF :
343                final DetailAST classFrameNameIdent = ast.findFirstToken(TokenTypes.IDENT);
344                frameStack.addFirst(new ClassFrame(frame, classFrameNameIdent));
345                break;
346            case TokenTypes.SLIST :
347                frameStack.addFirst(new BlockFrame(frame, ast));
348                break;
349            case TokenTypes.METHOD_DEF :
350                final DetailAST methodFrameNameIdent = ast.findFirstToken(TokenTypes.IDENT);
351                final DetailAST mods = ast.findFirstToken(TokenTypes.MODIFIERS);
352                if (mods.branchContains(TokenTypes.LITERAL_STATIC)) {
353                    ((ClassFrame) frame).addStaticMethod(methodFrameNameIdent);
354                }
355                else {
356                    ((ClassFrame) frame).addInstanceMethod(methodFrameNameIdent);
357                }
358                frameStack.addFirst(new MethodFrame(frame, methodFrameNameIdent));
359                break;
360            case TokenTypes.CTOR_DEF :
361                final DetailAST ctorFrameNameIdent = ast.findFirstToken(TokenTypes.IDENT);
362                frameStack.addFirst(new ConstructorFrame(frame, ctorFrameNameIdent));
363                break;
364            case TokenTypes.LITERAL_NEW:
365                if (isAnonymousClassDef(ast)) {
366                    frameStack.addFirst(new AnonymousClassFrame(frame,
367                            ast.getFirstChild().toString()));
368                }
369                break;
370            default:
371                // do nothing
372        }
373    }
374
375    /**
376     * Collects variable declarations.
377     * @param ast variable token.
378     * @param frame current frame.
379     */
380    private static void collectVariableDeclarations(DetailAST ast, AbstractFrame frame) {
381        final DetailAST ident = ast.findFirstToken(TokenTypes.IDENT);
382        if (frame.getType() == FrameType.CLASS_FRAME) {
383            final DetailAST mods =
384                    ast.findFirstToken(TokenTypes.MODIFIERS);
385            if (ScopeUtils.isInInterfaceBlock(ast)
386                    || mods.branchContains(TokenTypes.LITERAL_STATIC)) {
387                ((ClassFrame) frame).addStaticMember(ident);
388            }
389            else {
390                ((ClassFrame) frame).addInstanceMember(ident);
391            }
392        }
393        else {
394            frame.addIdent(ident);
395        }
396    }
397
398    /**
399     * Ends parsing of the AST for declarations.
400     * @param frameStack Stack containing the FrameTree being built.
401     * @param ast AST that was parsed.
402     */
403    private void endCollectingDeclarations(Queue<AbstractFrame> frameStack, DetailAST ast) {
404        switch (ast.getType()) {
405            case TokenTypes.CLASS_DEF :
406            case TokenTypes.INTERFACE_DEF :
407            case TokenTypes.ENUM_DEF :
408            case TokenTypes.ANNOTATION_DEF :
409            case TokenTypes.SLIST :
410            case TokenTypes.METHOD_DEF :
411            case TokenTypes.CTOR_DEF :
412                frames.put(ast, frameStack.poll());
413                break;
414            case TokenTypes.LITERAL_NEW :
415                if (isAnonymousClassDef(ast)) {
416                    frames.put(ast, frameStack.poll());
417                }
418                break;
419            default :
420                // do nothing
421        }
422    }
423
424    /**
425     * Whether the AST is a definition of an anonymous class.
426     * @param ast the AST to process.
427     * @return true if the AST is a definition of an anonymous class.
428     */
429    private static boolean isAnonymousClassDef(DetailAST ast) {
430        final DetailAST lastChild = ast.getLastChild();
431        return lastChild != null
432            && lastChild.getType() == TokenTypes.OBJBLOCK;
433    }
434
435    /**
436     * Returns the class frame where violation is found (where the field is used without 'this')
437     * or null otherwise.
438     * @param ast IDENT ast to check.
439     * @return the class frame where violation is found or null otherwise.
440     * @noinspection IfStatementWithIdenticalBranches
441     */
442    // -@cs[CyclomaticComplexity] Method already invokes too many methods that fully explain
443    // a logic, additional abstraction will not make logic/algorithm more readable.
444    private AbstractFrame getClassFrameWhereViolationIsFound(DetailAST ast) {
445        AbstractFrame frameWhereViolationIsFound = null;
446        final AbstractFrame variableDeclarationFrame = findFrame(ast, false);
447        final FrameType variableDeclarationFrameType = variableDeclarationFrame.getType();
448        final DetailAST prevSibling = ast.getPreviousSibling();
449        if (variableDeclarationFrameType == FrameType.CLASS_FRAME
450                && !validateOnlyOverlapping
451                && prevSibling == null
452                && canBeReferencedFromStaticContext(ast)) {
453            frameWhereViolationIsFound = variableDeclarationFrame;
454        }
455        else if (variableDeclarationFrameType == FrameType.METHOD_FRAME) {
456            if (isOverlappingByArgument(ast)) {
457                if (!isUserDefinedArrangementOfThis(variableDeclarationFrame, ast)
458                        && !isReturnedVariable(variableDeclarationFrame, ast)
459                        && canBeReferencedFromStaticContext(ast)
460                        && canAssignValueToClassField(ast)) {
461                    frameWhereViolationIsFound = findFrame(ast, true);
462                }
463            }
464            else if (!validateOnlyOverlapping
465                     && prevSibling == null
466                     && isAssignToken(ast.getParent().getType())
467                     && !isUserDefinedArrangementOfThis(variableDeclarationFrame, ast)
468                     && canBeReferencedFromStaticContext(ast)
469                     && canAssignValueToClassField(ast)) {
470                frameWhereViolationIsFound = findFrame(ast, true);
471
472            }
473        }
474        else if (variableDeclarationFrameType == FrameType.CTOR_FRAME
475                 && isOverlappingByArgument(ast)
476                 && !isUserDefinedArrangementOfThis(variableDeclarationFrame, ast)) {
477            frameWhereViolationIsFound = findFrame(ast, true);
478        }
479        else if (variableDeclarationFrameType == FrameType.BLOCK_FRAME
480                    && isOverlappingByLocalVariable(ast)
481                    && canAssignValueToClassField(ast)
482                    && !isUserDefinedArrangementOfThis(variableDeclarationFrame, ast)
483                    && !isReturnedVariable(variableDeclarationFrame, ast)
484                    && canBeReferencedFromStaticContext(ast)) {
485            frameWhereViolationIsFound = findFrame(ast, true);
486        }
487        return frameWhereViolationIsFound;
488    }
489
490    /**
491     * Checks whether user arranges 'this' for variable in method, constructor, or block on his own.
492     * @param currentFrame current frame.
493     * @param ident ident token.
494     * @return true if user arranges 'this' for variable in method, constructor,
495     *         or block on his own.
496     */
497    private static boolean isUserDefinedArrangementOfThis(AbstractFrame currentFrame,
498                                                          DetailAST ident) {
499        final DetailAST blockFrameNameIdent = currentFrame.getFrameNameIdent();
500        final DetailAST definitionToken = blockFrameNameIdent.getParent();
501        final DetailAST blockStartToken = definitionToken.findFirstToken(TokenTypes.SLIST);
502        final DetailAST blockEndToken = getBlockEndToken(blockFrameNameIdent, blockStartToken);
503
504        boolean userDefinedArrangementOfThis = false;
505
506        final Set<DetailAST> variableUsagesInsideBlock =
507            getAllTokensWhichAreEqualToCurrent(definitionToken, ident,
508                blockEndToken.getLineNo());
509
510        for (DetailAST variableUsage : variableUsagesInsideBlock) {
511            final DetailAST prevSibling = variableUsage.getPreviousSibling();
512            if (prevSibling != null
513                    && prevSibling.getType() == TokenTypes.LITERAL_THIS) {
514                userDefinedArrangementOfThis = true;
515                break;
516            }
517        }
518        return userDefinedArrangementOfThis;
519    }
520
521    /**
522     * Returns the token which ends the code block.
523     * @param blockNameIdent block name identifier.
524     * @param blockStartToken token which starts the block.
525     * @return the token which ends the code block.
526     */
527    private static DetailAST getBlockEndToken(DetailAST blockNameIdent, DetailAST blockStartToken) {
528        final Set<DetailAST> rcurlyTokens = getAllTokensOfType(blockNameIdent, TokenTypes.RCURLY);
529        DetailAST blockEndToken = null;
530        for (DetailAST currentRcurly : rcurlyTokens) {
531            final DetailAST parent = currentRcurly.getParent();
532            if (blockStartToken.getLineNo() == parent.getLineNo()) {
533                blockEndToken = currentRcurly;
534            }
535        }
536        return blockEndToken;
537    }
538
539    /**
540     * Checks whether the current variable is returned from the method.
541     * @param currentFrame current frame.
542     * @param ident variable ident token.
543     * @return true if the current variable is returned from the method.
544     */
545    private static boolean isReturnedVariable(AbstractFrame currentFrame, DetailAST ident) {
546        final DetailAST blockFrameNameIdent = currentFrame.getFrameNameIdent();
547        final DetailAST definitionToken = blockFrameNameIdent.getParent();
548        final DetailAST blockStartToken = definitionToken.findFirstToken(TokenTypes.SLIST);
549        final DetailAST blockEndToken = getBlockEndToken(blockFrameNameIdent, blockStartToken);
550
551        final Set<DetailAST> returnsInsideBlock = getAllTokensOfType(definitionToken,
552            TokenTypes.LITERAL_RETURN, blockEndToken.getLineNo());
553
554        boolean returnedVariable = false;
555        for (DetailAST returnToken : returnsInsideBlock) {
556            returnedVariable = returnToken.findAll(ident).hasMoreNodes();
557            if (returnedVariable) {
558                break;
559            }
560        }
561        return returnedVariable;
562    }
563
564    /**
565     * Checks whether a field can be referenced from a static context.
566     * @param ident ident token.
567     * @return true if field can be referenced from a static context.
568     */
569    private boolean canBeReferencedFromStaticContext(DetailAST ident) {
570        AbstractFrame variableDeclarationFrame = findFrame(ident, false);
571        boolean staticInitializationBlock = false;
572        while (variableDeclarationFrame.getType() == FrameType.BLOCK_FRAME) {
573            final DetailAST blockFrameNameIdent = variableDeclarationFrame.getFrameNameIdent();
574            final DetailAST definitionToken = blockFrameNameIdent.getParent();
575            if (definitionToken.getType() == TokenTypes.STATIC_INIT) {
576                staticInitializationBlock = true;
577                break;
578            }
579            variableDeclarationFrame = variableDeclarationFrame.getParent();
580        }
581
582        boolean staticContext = false;
583        if (staticInitializationBlock) {
584            staticContext = true;
585        }
586        else {
587            if (variableDeclarationFrame.getType() == FrameType.CLASS_FRAME) {
588                final DetailAST codeBlockDefinition = getCodeBlockDefinitionToken(ident);
589                if (codeBlockDefinition != null) {
590                    final DetailAST modifiers = codeBlockDefinition.getFirstChild();
591                    staticContext = codeBlockDefinition.getType() == TokenTypes.STATIC_INIT
592                        || modifiers.branchContains(TokenTypes.LITERAL_STATIC);
593                }
594            }
595            else {
596                final DetailAST frameNameIdent = variableDeclarationFrame.getFrameNameIdent();
597                final DetailAST definitionToken = frameNameIdent.getParent();
598                staticContext = definitionToken.branchContains(TokenTypes.LITERAL_STATIC);
599            }
600        }
601        return !staticContext;
602    }
603
604    /**
605     * Returns code block definition token for current identifier.
606     * @param ident ident token.
607     * @return code block definition token for current identifier or null if code block
608     *         definition was not found.
609     */
610    private static DetailAST getCodeBlockDefinitionToken(DetailAST ident) {
611        DetailAST parent = ident.getParent();
612        while (parent != null
613               && parent.getType() != TokenTypes.METHOD_DEF
614               && parent.getType() != TokenTypes.CTOR_DEF
615               && parent.getType() != TokenTypes.STATIC_INIT) {
616            parent = parent.getParent();
617        }
618        return parent;
619    }
620
621    /**
622     * Checks whether a value can be assigned to a field.
623     * A value can be assigned to a final field only in constructor block. If there is a method
624     * block, value assignment can be performed only to non final field.
625     * @param ast an identifier token.
626     * @return true if a value can be assigned to a field.
627     */
628    private boolean canAssignValueToClassField(DetailAST ast) {
629        final AbstractFrame fieldUsageFrame = findFrame(ast, false);
630        final boolean fieldUsageInConstructor = isInsideConstructorFrame(fieldUsageFrame);
631
632        final AbstractFrame declarationFrame = findFrame(ast, true);
633        final boolean finalField = ((ClassFrame) declarationFrame).hasFinalField(ast);
634
635        return fieldUsageInConstructor || !finalField;
636    }
637
638    /**
639     * Checks whether a field usage frame is inside constructor frame.
640     * @param frame frame, where field is used.
641     * @return true if the field usage frame is inside constructor frame.
642     */
643    private static boolean isInsideConstructorFrame(AbstractFrame frame) {
644        boolean assignmentInConstructor = false;
645        AbstractFrame fieldUsageFrame = frame;
646        if (fieldUsageFrame.getType() == FrameType.BLOCK_FRAME) {
647            while (fieldUsageFrame.getType() == FrameType.BLOCK_FRAME) {
648                fieldUsageFrame = fieldUsageFrame.getParent();
649            }
650            if (fieldUsageFrame.getType() == FrameType.CTOR_FRAME) {
651                assignmentInConstructor = true;
652            }
653        }
654        return assignmentInConstructor;
655    }
656
657    /**
658     * Checks whether an overlapping by method or constructor argument takes place.
659     * @param ast an identifier.
660     * @return true if an overlapping by method or constructor argument takes place.
661     */
662    private boolean isOverlappingByArgument(DetailAST ast) {
663        boolean overlapping = false;
664        final DetailAST parent = ast.getParent();
665        final DetailAST sibling = ast.getNextSibling();
666        if (sibling != null && isAssignToken(parent.getType())) {
667            final ClassFrame classFrame = (ClassFrame) findFrame(ast, true);
668            final Set<DetailAST> exprIdents = getAllTokensOfType(sibling, TokenTypes.IDENT);
669            if (isCompoundAssignToken(parent.getType())) {
670                overlapping = true;
671            }
672            else {
673                overlapping = classFrame.containsFieldOrVariableDef(exprIdents, ast);
674            }
675        }
676        return overlapping;
677    }
678
679    /**
680     * Checks whether an overlapping by local variable takes place.
681     * @param ast an identifier.
682     * @return true if an overlapping by local variable takes place.
683     */
684    private boolean isOverlappingByLocalVariable(DetailAST ast) {
685        boolean overlapping = false;
686        final DetailAST parent = ast.getParent();
687        final DetailAST sibling = ast.getNextSibling();
688        if (sibling != null && isAssignToken(parent.getType())) {
689            final ClassFrame classFrame = (ClassFrame) findFrame(ast, true);
690            final Set<DetailAST> exprIdents = getAllTokensOfType(sibling, TokenTypes.IDENT);
691            overlapping = classFrame.containsFieldOrVariableDef(exprIdents, ast);
692        }
693        return overlapping;
694    }
695
696    /**
697     * Collects all tokens of specific type starting with the current ast node.
698     * @param ast ast node.
699     * @param tokenType token type.
700     * @return a set of all tokens of specific type starting with the current ast node.
701     */
702    private static Set<DetailAST> getAllTokensOfType(DetailAST ast, int tokenType) {
703        DetailAST vertex = ast;
704        final Set<DetailAST> result = new HashSet<>();
705        final Deque<DetailAST> stack = new ArrayDeque<>();
706        while (vertex != null || !stack.isEmpty()) {
707            if (!stack.isEmpty()) {
708                vertex = stack.pop();
709            }
710            while (vertex != null) {
711                if (vertex.getType() == tokenType) {
712                    result.add(vertex);
713                }
714                if (vertex.getNextSibling() != null) {
715                    stack.push(vertex.getNextSibling());
716                }
717                vertex = vertex.getFirstChild();
718            }
719        }
720        return result;
721    }
722
723    /**
724     * Collects all tokens of specific type starting with the current ast node and which line
725     * number is lower or equal to the end line number.
726     * @param ast ast node.
727     * @param tokenType token type.
728     * @param endLineNumber end line number.
729     * @return a set of all tokens of specific type starting with the current ast node and which
730     *         line number is lower or equal to the end line number.
731     */
732    private static Set<DetailAST> getAllTokensOfType(DetailAST ast, int tokenType,
733                                                     int endLineNumber) {
734        DetailAST vertex = ast;
735        final Set<DetailAST> result = new HashSet<>();
736        final Deque<DetailAST> stack = new ArrayDeque<>();
737        while (vertex != null || !stack.isEmpty()) {
738            if (!stack.isEmpty()) {
739                vertex = stack.pop();
740            }
741            while (vertex != null) {
742                if (tokenType == vertex.getType()
743                    && vertex.getLineNo() <= endLineNumber) {
744                    result.add(vertex);
745                }
746                if (vertex.getNextSibling() != null) {
747                    stack.push(vertex.getNextSibling());
748                }
749                vertex = vertex.getFirstChild();
750            }
751        }
752        return result;
753    }
754
755    /**
756     * Collects all tokens which are equal to current token starting with the current ast node and
757     * which line number is lower or equal to the end line number.
758     * @param ast ast node.
759     * @param token token.
760     * @param endLineNumber end line number.
761     * @return a set of tokens which are equal to current token starting with the current ast node
762     *         and which line number is lower or equal to the end line number.
763     */
764    private static Set<DetailAST> getAllTokensWhichAreEqualToCurrent(DetailAST ast, DetailAST token,
765                                                                     int endLineNumber) {
766        DetailAST vertex = ast;
767        final Set<DetailAST> result = new HashSet<>();
768        final Deque<DetailAST> stack = new ArrayDeque<>();
769        while (vertex != null || !stack.isEmpty()) {
770            if (!stack.isEmpty()) {
771                vertex = stack.pop();
772            }
773            while (vertex != null) {
774                if (token.equals(vertex)
775                        && vertex.getLineNo() <= endLineNumber) {
776                    result.add(vertex);
777                }
778                if (vertex.getNextSibling() != null) {
779                    stack.push(vertex.getNextSibling());
780                }
781                vertex = vertex.getFirstChild();
782            }
783        }
784        return result;
785    }
786
787    /**
788     * Returns the frame where the method is declared, if the given method is used without
789     * 'this' and null otherwise.
790     * @param ast the IDENT ast of the name to check.
791     * @return the frame where the method is declared, if the given method is used without
792     *         'this' and null otherwise.
793     */
794    private AbstractFrame getMethodWithoutThis(DetailAST ast) {
795        AbstractFrame result = null;
796        final AbstractFrame frame = findFrame(ast, true);
797        if (!validateOnlyOverlapping
798                && ((ClassFrame) frame).hasInstanceMethod(ast)
799                && !((ClassFrame) frame).hasStaticMethod(ast)) {
800            result = frame;
801        }
802        return result;
803    }
804
805    /**
806     * Find the class frame containing declaration.
807     * @param name IDENT ast of the declaration to find.
808     * @param lookForMethod whether we are looking for a method name.
809     * @return AbstractFrame containing declaration or null.
810     */
811    private AbstractFrame findClassFrame(DetailAST name, boolean lookForMethod) {
812        AbstractFrame frame = current;
813
814        while (true) {
815            frame = findFrame(frame, name, lookForMethod);
816
817            if (frame == null || frame instanceof ClassFrame) {
818                break;
819            }
820
821            frame = frame.getParent();
822        }
823
824        return frame;
825    }
826
827    /**
828     * Find frame containing declaration.
829     * @param name IDENT ast of the declaration to find.
830     * @param lookForMethod whether we are looking for a method name.
831     * @return AbstractFrame containing declaration or null.
832     */
833    private AbstractFrame findFrame(DetailAST name, boolean lookForMethod) {
834        return findFrame(current, name, lookForMethod);
835    }
836
837    /**
838     * Find frame containing declaration.
839     * @param frame The parent frame to searching in.
840     * @param name IDENT ast of the declaration to find.
841     * @param lookForMethod whether we are looking for a method name.
842     * @return AbstractFrame containing declaration or null.
843     */
844    private static AbstractFrame findFrame(AbstractFrame frame, DetailAST name,
845            boolean lookForMethod) {
846        final AbstractFrame result;
847        if (frame == null) {
848            result = null;
849        }
850        else {
851            result = frame.getIfContains(name, lookForMethod);
852        }
853        return result;
854    }
855
856    /**
857     * Check that token is related to Definition tokens.
858     * @param parentType token Type.
859     * @return true if token is related to Definition Tokens.
860     */
861    private static boolean isDeclarationToken(int parentType) {
862        return DECLARATION_TOKENS.contains(parentType);
863    }
864
865    /**
866     * Check that token is related to assign tokens.
867     * @param tokenType token type.
868     * @return true if token is related to assign tokens.
869     */
870    private static boolean isAssignToken(int tokenType) {
871        return ASSIGN_TOKENS.contains(tokenType);
872    }
873
874    /**
875     * Check that token is related to compound assign tokens.
876     * @param tokenType token type.
877     * @return true if token is related to compound assign tokens.
878     */
879    private static boolean isCompoundAssignToken(int tokenType) {
880        return COMPOUND_ASSIGN_TOKENS.contains(tokenType);
881    }
882
883    /**
884     * Gets the name of the nearest parent ClassFrame.
885     * @return the name of the nearest parent ClassFrame.
886     */
887    private String getNearestClassFrameName() {
888        AbstractFrame frame = current;
889        while (frame.getType() != FrameType.CLASS_FRAME) {
890            frame = frame.getParent();
891        }
892        return frame.getFrameName();
893    }
894
895    /** An AbstractFrame type. */
896    private enum FrameType {
897        /** Class frame type. */
898        CLASS_FRAME,
899        /** Constructor frame type. */
900        CTOR_FRAME,
901        /** Method frame type. */
902        METHOD_FRAME,
903        /** Block frame type. */
904        BLOCK_FRAME,
905    }
906
907    /**
908     * A declaration frame.
909     * @author Stephen Bloch
910     * @author Andrei Selkin
911     */
912    private abstract static class AbstractFrame {
913        /** Set of name of variables declared in this frame. */
914        private final Set<DetailAST> varIdents;
915
916        /** Parent frame. */
917        private final AbstractFrame parent;
918
919        /** Name identifier token. */
920        private final DetailAST frameNameIdent;
921
922        /**
923         * Constructor -- invokable only via super() from subclasses.
924         * @param parent parent frame.
925         * @param ident frame name ident.
926         */
927        protected AbstractFrame(AbstractFrame parent, DetailAST ident) {
928            this.parent = parent;
929            frameNameIdent = ident;
930            varIdents = new HashSet<>();
931        }
932
933        /**
934         * Get the type of the frame.
935         * @return a FrameType.
936         */
937        protected abstract FrameType getType();
938
939        /**
940         * Add a name to the frame.
941         * @param identToAdd the name we're adding.
942         */
943        private void addIdent(DetailAST identToAdd) {
944            varIdents.add(identToAdd);
945        }
946
947        protected AbstractFrame getParent() {
948            return parent;
949        }
950
951        protected String getFrameName() {
952            return frameNameIdent.getText();
953        }
954
955        public DetailAST getFrameNameIdent() {
956            return frameNameIdent;
957        }
958
959        /**
960         * Check whether the frame contains a field or a variable with the given name.
961         * @param nameToFind the IDENT ast of the name we're looking for.
962         * @return whether it was found.
963         */
964        protected boolean containsFieldOrVariable(DetailAST nameToFind) {
965            return containsFieldOrVariableDef(varIdents, nameToFind);
966        }
967
968        /**
969         * Check whether the frame contains a given name.
970         * @param nameToFind IDENT ast of the name we're looking for.
971         * @param lookForMethod whether we are looking for a method name.
972         * @return whether it was found.
973         */
974        protected AbstractFrame getIfContains(DetailAST nameToFind, boolean lookForMethod) {
975            final AbstractFrame frame;
976
977            if (!lookForMethod
978                && containsFieldOrVariable(nameToFind)) {
979                frame = this;
980            }
981            else {
982                frame = parent.getIfContains(nameToFind, lookForMethod);
983            }
984            return frame;
985        }
986
987        /**
988         * Whether the set contains a declaration with the text of the specified
989         * IDENT ast and it is declared in a proper position.
990         * @param set the set of declarations.
991         * @param ident the specified IDENT ast.
992         * @return true if the set contains a declaration with the text of the specified
993         *         IDENT ast and it is declared in a proper position.
994         */
995        protected boolean containsFieldOrVariableDef(Set<DetailAST> set, DetailAST ident) {
996            boolean result = false;
997            for (DetailAST ast: set) {
998                if (isProperDefinition(ident, ast)) {
999                    result = true;
1000                    break;
1001                }
1002            }
1003            return result;
1004        }
1005
1006        /**
1007         * Whether the definition is correspondent to the IDENT.
1008         * @param ident the IDENT ast to check.
1009         * @param ast the IDENT ast of the definition to check.
1010         * @return true if ast is correspondent to ident.
1011         */
1012        protected boolean isProperDefinition(DetailAST ident, DetailAST ast) {
1013            final String nameToFind = ident.getText();
1014            return nameToFind.equals(ast.getText())
1015                && checkPosition(ast, ident);
1016        }
1017
1018        /**
1019         * Whether the declaration is located before the checked ast.
1020         * @param ast1 the IDENT ast of the declaration.
1021         * @param ast2 the IDENT ast to check.
1022         * @return true, if the declaration is located before the checked ast.
1023         */
1024        private static boolean checkPosition(DetailAST ast1, DetailAST ast2) {
1025            boolean result = false;
1026            if (ast1.getLineNo() < ast2.getLineNo()
1027                    || ast1.getLineNo() == ast2.getLineNo()
1028                    && ast1.getColumnNo() < ast2.getColumnNo()) {
1029                result = true;
1030            }
1031            return result;
1032        }
1033    }
1034
1035    /**
1036     * A frame initiated at method definition; holds a method definition token.
1037     * @author Stephen Bloch
1038     * @author Andrei Selkin
1039     */
1040    private static class MethodFrame extends AbstractFrame {
1041
1042        /**
1043         * Creates method frame.
1044         * @param parent parent frame.
1045         * @param ident method name identifier token.
1046         */
1047        protected MethodFrame(AbstractFrame parent, DetailAST ident) {
1048            super(parent, ident);
1049        }
1050
1051        @Override
1052        protected FrameType getType() {
1053            return FrameType.METHOD_FRAME;
1054        }
1055    }
1056
1057    /**
1058     * A frame initiated at constructor definition.
1059     * @author Andrei Selkin
1060     */
1061    private static class ConstructorFrame extends AbstractFrame {
1062
1063        /**
1064         * Creates a constructor frame.
1065         * @param parent parent frame.
1066         * @param ident frame name ident.
1067         */
1068        protected ConstructorFrame(AbstractFrame parent, DetailAST ident) {
1069            super(parent, ident);
1070        }
1071
1072        @Override
1073        protected FrameType getType() {
1074            return FrameType.CTOR_FRAME;
1075        }
1076    }
1077
1078    /**
1079     * A frame initiated at class, enum or interface definition; holds instance variable names.
1080     * @author Stephen Bloch
1081     * @author Andrei Selkin
1082     */
1083    private static class ClassFrame extends AbstractFrame {
1084        /** Set of idents of instance members declared in this frame. */
1085        private final Set<DetailAST> instanceMembers;
1086        /** Set of idents of instance methods declared in this frame. */
1087        private final Set<DetailAST> instanceMethods;
1088        /** Set of idents of variables declared in this frame. */
1089        private final Set<DetailAST> staticMembers;
1090        /** Set of idents of static methods declared in this frame. */
1091        private final Set<DetailAST> staticMethods;
1092
1093        /**
1094         * Creates new instance of ClassFrame.
1095         * @param parent parent frame.
1096         * @param ident frame name ident.
1097         */
1098        ClassFrame(AbstractFrame parent, DetailAST ident) {
1099            super(parent, ident);
1100            instanceMembers = new HashSet<>();
1101            instanceMethods = new HashSet<>();
1102            staticMembers = new HashSet<>();
1103            staticMethods = new HashSet<>();
1104        }
1105
1106        @Override
1107        protected FrameType getType() {
1108            return FrameType.CLASS_FRAME;
1109        }
1110
1111        /**
1112         * Adds static member's ident.
1113         * @param ident an ident of static member of the class.
1114         */
1115        public void addStaticMember(final DetailAST ident) {
1116            staticMembers.add(ident);
1117        }
1118
1119        /**
1120         * Adds static method's name.
1121         * @param ident an ident of static method of the class.
1122         */
1123        public void addStaticMethod(final DetailAST ident) {
1124            staticMethods.add(ident);
1125        }
1126
1127        /**
1128         * Adds instance member's ident.
1129         * @param ident an ident of instance member of the class.
1130         */
1131        public void addInstanceMember(final DetailAST ident) {
1132            instanceMembers.add(ident);
1133        }
1134
1135        /**
1136         * Adds instance method's name.
1137         * @param ident an ident of instance method of the class.
1138         */
1139        public void addInstanceMethod(final DetailAST ident) {
1140            instanceMethods.add(ident);
1141        }
1142
1143        /**
1144         * Checks if a given name is a known instance member of the class.
1145         * @param ident the IDENT ast of the name to check.
1146         * @return true is the given name is a name of a known
1147         *         instance member of the class.
1148         */
1149        public boolean hasInstanceMember(final DetailAST ident) {
1150            return containsFieldOrVariableDef(instanceMembers, ident);
1151        }
1152
1153        /**
1154         * Checks if a given name is a known instance method of the class.
1155         * @param ident the IDENT ast of the method call to check.
1156         * @return true if the given ast is correspondent to a known
1157         *         instance method of the class.
1158         */
1159        public boolean hasInstanceMethod(final DetailAST ident) {
1160            return containsMethodDef(instanceMethods, ident);
1161        }
1162
1163        /**
1164         * Checks if a given name is a known static method of the class.
1165         * @param ident the IDENT ast of the method call to check.
1166         * @return true is the given ast is correspondent to a known
1167         *         instance method of the class.
1168         */
1169        public boolean hasStaticMethod(final DetailAST ident) {
1170            return containsMethodDef(staticMethods, ident);
1171        }
1172
1173        /**
1174         * Checks whether given instance member has final modifier.
1175         * @param instanceMember an instance member of a class.
1176         * @return true if given instance member has final modifier.
1177         */
1178        public boolean hasFinalField(final DetailAST instanceMember) {
1179            boolean result = false;
1180            for (DetailAST member : instanceMembers) {
1181                final DetailAST mods = member.getParent().findFirstToken(TokenTypes.MODIFIERS);
1182                final boolean finalMod = mods.branchContains(TokenTypes.FINAL);
1183                if (finalMod && member.equals(instanceMember)) {
1184                    result = true;
1185                    break;
1186                }
1187            }
1188            return result;
1189        }
1190
1191        @Override
1192        protected boolean containsFieldOrVariable(DetailAST nameToFind) {
1193            return containsFieldOrVariableDef(instanceMembers, nameToFind)
1194                    || containsFieldOrVariableDef(staticMembers, nameToFind);
1195        }
1196
1197        @Override
1198        protected boolean isProperDefinition(DetailAST ident, DetailAST ast) {
1199            final String nameToFind = ident.getText();
1200            return nameToFind.equals(ast.getText());
1201        }
1202
1203        @Override
1204        protected AbstractFrame getIfContains(DetailAST nameToFind, boolean lookForMethod) {
1205            AbstractFrame frame = null;
1206
1207            if (lookForMethod && containsMethod(nameToFind)
1208                || containsFieldOrVariable(nameToFind)) {
1209                frame = this;
1210            }
1211            else if (getParent() != null) {
1212                frame = getParent().getIfContains(nameToFind, lookForMethod);
1213            }
1214            return frame;
1215        }
1216
1217        /**
1218         * Check whether the frame contains a given method.
1219         * @param methodToFind the AST of the method to find.
1220         * @return true, if a method with the same name and number of parameters is found.
1221         */
1222        private boolean containsMethod(DetailAST methodToFind) {
1223            return containsMethodDef(instanceMethods, methodToFind)
1224                || containsMethodDef(staticMethods, methodToFind);
1225        }
1226
1227        /**
1228         * Whether the set contains a method definition with the
1229         *     same name and number of parameters.
1230         * @param set the set of definitions.
1231         * @param ident the specified method call IDENT ast.
1232         * @return true if the set contains a definition with the
1233         *     same name and number of parameters.
1234         */
1235        private static boolean containsMethodDef(Set<DetailAST> set, DetailAST ident) {
1236            boolean result = false;
1237            for (DetailAST ast: set) {
1238                if (isSimilarSignature(ident, ast)) {
1239                    result = true;
1240                    break;
1241                }
1242            }
1243            return result;
1244        }
1245
1246        /**
1247         * Whether the method definition has the same name and number of parameters.
1248         * @param ident the specified method call IDENT ast.
1249         * @param ast the ast of a method definition to compare with.
1250         * @return true if a method definition has the same name and number of parameters
1251         *     as the method call.
1252         */
1253        private static boolean isSimilarSignature(DetailAST ident, DetailAST ast) {
1254            boolean result = false;
1255            final DetailAST elistToken = ident.getParent().findFirstToken(TokenTypes.ELIST);
1256            if (elistToken != null && ident.getText().equals(ast.getText())) {
1257                final int paramsNumber =
1258                    ast.getParent().findFirstToken(TokenTypes.PARAMETERS).getChildCount();
1259                final int argsNumber = elistToken.getChildCount();
1260                result = paramsNumber == argsNumber;
1261            }
1262            return result;
1263        }
1264    }
1265
1266    /**
1267     * An anonymous class frame; holds instance variable names.
1268     */
1269    private static class AnonymousClassFrame extends ClassFrame {
1270
1271        /** The name of the frame. */
1272        private final String frameName;
1273
1274        /**
1275         * Creates anonymous class frame.
1276         * @param parent parent frame.
1277         * @param frameName name of the frame.
1278         */
1279        protected AnonymousClassFrame(AbstractFrame parent, String frameName) {
1280            super(parent, null);
1281            this.frameName = frameName;
1282        }
1283
1284        @Override
1285        protected String getFrameName() {
1286            return frameName;
1287        }
1288    }
1289
1290    /**
1291     * A frame initiated on entering a statement list; holds local variable names.
1292     * @author Stephen Bloch
1293     */
1294    private static class BlockFrame extends AbstractFrame {
1295
1296        /**
1297         * Creates block frame.
1298         * @param parent parent frame.
1299         * @param ident ident frame name ident.
1300         */
1301        protected BlockFrame(AbstractFrame parent, DetailAST ident) {
1302            super(parent, ident);
1303        }
1304
1305        @Override
1306        protected FrameType getType() {
1307            return FrameType.BLOCK_FRAME;
1308        }
1309    }
1310}