001///////////////////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code and other text files for adherence to a set of rules.
003// Copyright (C) 2001-2022 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.imports;
021
022import java.util.ArrayList;
023import java.util.Collection;
024import java.util.HashSet;
025import java.util.List;
026import java.util.Set;
027import java.util.regex.Matcher;
028import java.util.regex.Pattern;
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.FileContents;
034import com.puppycrawl.tools.checkstyle.api.FullIdent;
035import com.puppycrawl.tools.checkstyle.api.TextBlock;
036import com.puppycrawl.tools.checkstyle.api.TokenTypes;
037import com.puppycrawl.tools.checkstyle.checks.javadoc.JavadocTag;
038import com.puppycrawl.tools.checkstyle.utils.CommonUtil;
039import com.puppycrawl.tools.checkstyle.utils.JavadocUtil;
040import com.puppycrawl.tools.checkstyle.utils.TokenUtil;
041
042/**
043 * <p>
044 * Checks for unused import statements. Checkstyle uses a simple but very
045 * reliable algorithm to report on unused import statements. An import statement
046 * is considered unused if:
047 * </p>
048 * <ul>
049 * <li>
050 * It is not referenced in the file. The algorithm does not support wild-card
051 * imports like {@code import java.io.*;}. Most IDE's provide very sophisticated
052 * checks for imports that handle wild-card imports.
053 * </li>
054 * <li>
055 * It is a duplicate of another import. This is when a class is imported more
056 * than once.
057 * </li>
058 * <li>
059 * The class imported is from the {@code java.lang} package. For example
060 * importing {@code java.lang.String}.
061 * </li>
062 * <li>
063 * The class imported is from the same package.
064 * </li>
065 * <li>
066 * <b>Optionally:</b> it is referenced in Javadoc comments. This check is on by
067 * default, but it is considered bad practice to introduce a compile-time
068 * dependency for documentation purposes only. As an example, the import
069 * {@code java.util.List} would be considered referenced with the Javadoc
070 * comment {@code {@link List}}. The alternative to avoid introducing a compile-time
071 * dependency would be to write the Javadoc comment as {@code {&#64;link java.util.List}}.
072 * </li>
073 * </ul>
074 * <p>
075 * The main limitation of this check is handling the case where an imported type
076 * has the same name as a declaration, such as a member variable.
077 * </p>
078 * <p>
079 * For example, in the following case the import {@code java.awt.Component}
080 * will not be flagged as unused:
081 * </p>
082 * <pre>
083 * import java.awt.Component;
084 * class FooBar {
085 *   private Object Component; // a bad practice in my opinion
086 *   ...
087 * }
088 * </pre>
089 * <ul>
090 * <li>
091 * Property {@code processJavadoc} - Control whether to process Javadoc comments.
092 * Type is {@code boolean}.
093 * Default value is {@code true}.
094 * </li>
095 * </ul>
096 * <p>
097 * To configure the check:
098 * </p>
099 * <pre>
100 * &lt;module name="UnusedImports"/&gt;
101 * </pre>
102 * <p>
103 * Parent is {@code com.puppycrawl.tools.checkstyle.TreeWalker}
104 * </p>
105 * <p>
106 * Violation Message Keys:
107 * </p>
108 * <ul>
109 * <li>
110 * {@code import.unused}
111 * </li>
112 * </ul>
113 *
114 * @since 3.0
115 */
116@FileStatefulCheck
117public class UnusedImportsCheck extends AbstractCheck {
118
119    /**
120     * A key is pointing to the warning message text in "messages.properties"
121     * file.
122     */
123    public static final String MSG_KEY = "import.unused";
124
125    /** Regex to match class names. */
126    private static final Pattern CLASS_NAME = CommonUtil.createPattern(
127           "((:?[\\p{L}_$][\\p{L}\\p{N}_$]*\\.)*[\\p{L}_$][\\p{L}\\p{N}_$]*)");
128    /** Regex to match the first class name. */
129    private static final Pattern FIRST_CLASS_NAME = CommonUtil.createPattern(
130           "^" + CLASS_NAME);
131    /** Regex to match argument names. */
132    private static final Pattern ARGUMENT_NAME = CommonUtil.createPattern(
133           "[(,]\\s*" + CLASS_NAME.pattern());
134
135    /** Regexp pattern to match java.lang package. */
136    private static final Pattern JAVA_LANG_PACKAGE_PATTERN =
137        CommonUtil.createPattern("^java\\.lang\\.[a-zA-Z]+$");
138
139    /** Suffix for the star import. */
140    private static final String STAR_IMPORT_SUFFIX = ".*";
141
142    /** Set of the imports. */
143    private final Set<FullIdent> imports = new HashSet<>();
144
145    /** Flag to indicate when time to start collecting references. */
146    private boolean collect;
147    /** Control whether to process Javadoc comments. */
148    private boolean processJavadoc = true;
149
150    /**
151     * The scope is being processed.
152     * Types declared in a scope can shadow imported types.
153     */
154    private Frame currentFrame;
155
156    /**
157     * Setter to control whether to process Javadoc comments.
158     *
159     * @param value Flag for processing Javadoc comments.
160     */
161    public void setProcessJavadoc(boolean value) {
162        processJavadoc = value;
163    }
164
165    @Override
166    public void beginTree(DetailAST rootAST) {
167        collect = false;
168        currentFrame = Frame.compilationUnit();
169        imports.clear();
170    }
171
172    @Override
173    public void finishTree(DetailAST rootAST) {
174        currentFrame.finish();
175        // loop over all the imports to see if referenced.
176        imports.stream()
177            .filter(imprt -> isUnusedImport(imprt.getText()))
178            .forEach(imprt -> log(imprt.getDetailAst(), MSG_KEY, imprt.getText()));
179    }
180
181    @Override
182    public int[] getDefaultTokens() {
183        return getRequiredTokens();
184    }
185
186    @Override
187    public int[] getRequiredTokens() {
188        return new int[] {
189            TokenTypes.IDENT,
190            TokenTypes.IMPORT,
191            TokenTypes.STATIC_IMPORT,
192            // Definitions that may contain Javadoc...
193            TokenTypes.PACKAGE_DEF,
194            TokenTypes.ANNOTATION_DEF,
195            TokenTypes.ANNOTATION_FIELD_DEF,
196            TokenTypes.ENUM_DEF,
197            TokenTypes.ENUM_CONSTANT_DEF,
198            TokenTypes.CLASS_DEF,
199            TokenTypes.INTERFACE_DEF,
200            TokenTypes.METHOD_DEF,
201            TokenTypes.CTOR_DEF,
202            TokenTypes.VARIABLE_DEF,
203            TokenTypes.RECORD_DEF,
204            TokenTypes.COMPACT_CTOR_DEF,
205            // Tokens for creating a new frame
206            TokenTypes.OBJBLOCK,
207            TokenTypes.SLIST,
208        };
209    }
210
211    @Override
212    public int[] getAcceptableTokens() {
213        return getRequiredTokens();
214    }
215
216    @Override
217    public void visitToken(DetailAST ast) {
218        switch (ast.getType()) {
219            case TokenTypes.IDENT:
220                if (collect) {
221                    processIdent(ast);
222                }
223                break;
224            case TokenTypes.IMPORT:
225                processImport(ast);
226                break;
227            case TokenTypes.STATIC_IMPORT:
228                processStaticImport(ast);
229                break;
230            case TokenTypes.OBJBLOCK:
231            case TokenTypes.SLIST:
232                currentFrame = currentFrame.push();
233                break;
234            default:
235                collect = true;
236                if (processJavadoc) {
237                    collectReferencesFromJavadoc(ast);
238                }
239                break;
240        }
241    }
242
243    @Override
244    public void leaveToken(DetailAST ast) {
245        if (TokenUtil.isOfType(ast, TokenTypes.OBJBLOCK, TokenTypes.SLIST)) {
246            currentFrame = currentFrame.pop();
247        }
248    }
249
250    /**
251     * Checks whether an import is unused.
252     *
253     * @param imprt an import.
254     * @return true if an import is unused.
255     */
256    private boolean isUnusedImport(String imprt) {
257        final Matcher javaLangPackageMatcher = JAVA_LANG_PACKAGE_PATTERN.matcher(imprt);
258        return !currentFrame.isReferencedType(CommonUtil.baseClassName(imprt))
259            || javaLangPackageMatcher.matches();
260    }
261
262    /**
263     * Collects references made by IDENT.
264     *
265     * @param ast the IDENT node to process
266     */
267    private void processIdent(DetailAST ast) {
268        final DetailAST parent = ast.getParent();
269        final int parentType = parent.getType();
270
271        final boolean isPossibleDotClassOrInMethod = parentType == TokenTypes.DOT
272                || parentType == TokenTypes.METHOD_DEF;
273
274        final boolean isQualifiedIdent = parentType == TokenTypes.DOT
275                && !TokenUtil.isOfType(ast.getPreviousSibling(), TokenTypes.DOT)
276                && ast.getNextSibling() != null;
277
278        if (TokenUtil.isTypeDeclaration(parentType)) {
279            currentFrame.addDeclaredType(ast.getText());
280        }
281        else if (!isPossibleDotClassOrInMethod || isQualifiedIdent) {
282            currentFrame.addReferencedType(ast.getText());
283        }
284    }
285
286    /**
287     * Collects the details of imports.
288     *
289     * @param ast node containing the import details
290     */
291    private void processImport(DetailAST ast) {
292        final FullIdent name = FullIdent.createFullIdentBelow(ast);
293        if (!name.getText().endsWith(STAR_IMPORT_SUFFIX)) {
294            imports.add(name);
295        }
296    }
297
298    /**
299     * Collects the details of static imports.
300     *
301     * @param ast node containing the static import details
302     */
303    private void processStaticImport(DetailAST ast) {
304        final FullIdent name =
305            FullIdent.createFullIdent(
306                ast.getFirstChild().getNextSibling());
307        if (!name.getText().endsWith(STAR_IMPORT_SUFFIX)) {
308            imports.add(name);
309        }
310    }
311
312    /**
313     * Collects references made in Javadoc comments.
314     *
315     * @param ast node to inspect for Javadoc
316     */
317    // suppress deprecation until https://github.com/checkstyle/checkstyle/issues/11166
318    @SuppressWarnings("deprecation")
319    private void collectReferencesFromJavadoc(DetailAST ast) {
320        final FileContents contents = getFileContents();
321        final int lineNo = ast.getLineNo();
322        final TextBlock textBlock = contents.getJavadocBefore(lineNo);
323        if (textBlock != null) {
324            currentFrame.addReferencedTypes(collectReferencesFromJavadoc(textBlock));
325        }
326    }
327
328    /**
329     * Process a javadoc {@link TextBlock} and return the set of classes
330     * referenced within.
331     *
332     * @param textBlock The javadoc block to parse
333     * @return a set of classes referenced in the javadoc block
334     */
335    private static Set<String> collectReferencesFromJavadoc(TextBlock textBlock) {
336        final List<JavadocTag> tags = new ArrayList<>();
337        // gather all the inline tags, like @link
338        // INLINE tags inside BLOCKs get hidden when using ALL
339        tags.addAll(getValidTags(textBlock, JavadocUtil.JavadocTagType.INLINE));
340        // gather all the block-level tags, like @throws and @see
341        tags.addAll(getValidTags(textBlock, JavadocUtil.JavadocTagType.BLOCK));
342
343        final Set<String> references = new HashSet<>();
344
345        tags.stream()
346            .filter(JavadocTag::canReferenceImports)
347            .forEach(tag -> references.addAll(processJavadocTag(tag)));
348        return references;
349    }
350
351    /**
352     * Returns the list of valid tags found in a javadoc {@link TextBlock}.
353     *
354     * @param cmt The javadoc block to parse
355     * @param tagType The type of tags we're interested in
356     * @return the list of tags
357     */
358    private static List<JavadocTag> getValidTags(TextBlock cmt,
359            JavadocUtil.JavadocTagType tagType) {
360        return JavadocUtil.getJavadocTags(cmt, tagType).getValidTags();
361    }
362
363    /**
364     * Returns a list of references that found in a javadoc {@link JavadocTag}.
365     *
366     * @param tag The javadoc tag to parse
367     * @return A list of references that found in this tag
368     */
369    private static Set<String> processJavadocTag(JavadocTag tag) {
370        final Set<String> references = new HashSet<>();
371        final String identifier = tag.getFirstArg().trim();
372        for (Pattern pattern : new Pattern[]
373        {FIRST_CLASS_NAME, ARGUMENT_NAME}) {
374            references.addAll(matchPattern(identifier, pattern));
375        }
376        return references;
377    }
378
379    /**
380     * Extracts a set of texts matching a {@link Pattern} from a
381     * {@link String}.
382     *
383     * @param identifier The String to match the pattern against
384     * @param pattern The Pattern used to extract the texts
385     * @return A set of texts which matched the pattern
386     */
387    private static Set<String> matchPattern(String identifier, Pattern pattern) {
388        final Set<String> references = new HashSet<>();
389        final Matcher matcher = pattern.matcher(identifier);
390        while (matcher.find()) {
391            references.add(topLevelType(matcher.group(1)));
392        }
393        return references;
394    }
395
396    /**
397     * If the given type string contains "." (e.g. "Map.Entry"), returns the
398     * top level type (e.g. "Map"), as that is what must be imported for the
399     * type to resolve. Otherwise, returns the type as-is.
400     *
401     * @param type A possibly qualified type name
402     * @return The simple name of the top level type
403     */
404    private static String topLevelType(String type) {
405        final String topLevelType;
406        final int dotIndex = type.indexOf('.');
407        if (dotIndex == -1) {
408            topLevelType = type;
409        }
410        else {
411            topLevelType = type.substring(0, dotIndex);
412        }
413        return topLevelType;
414    }
415
416    /**
417     * Holds the names of referenced types and names of declared inner types.
418     */
419    private static final class Frame {
420
421        /** Parent frame. */
422        private final Frame parent;
423
424        /** Nested types declared in the current scope. */
425        private final Set<String> declaredTypes;
426
427        /** Set of references - possibly to imports or locally declared types. */
428        private final Set<String> referencedTypes;
429
430        /**
431         * Private constructor. Use {@link #compilationUnit()} to create a new top-level frame.
432         *
433         * @param parent the parent frame
434         */
435        private Frame(Frame parent) {
436            this.parent = parent;
437            declaredTypes = new HashSet<>();
438            referencedTypes = new HashSet<>();
439        }
440
441        /**
442         * Adds new inner type.
443         *
444         * @param type the type name
445         */
446        public void addDeclaredType(String type) {
447            declaredTypes.add(type);
448        }
449
450        /**
451         * Adds new type reference to the current frame.
452         *
453         * @param type the type name
454         */
455        public void addReferencedType(String type) {
456            referencedTypes.add(type);
457        }
458
459        /**
460         * Adds new inner types.
461         *
462         * @param types the type names
463         */
464        public void addReferencedTypes(Collection<String> types) {
465            referencedTypes.addAll(types);
466        }
467
468        /**
469         * Filters out all references to locally defined types.
470         *
471         */
472        public void finish() {
473            referencedTypes.removeAll(declaredTypes);
474        }
475
476        /**
477         * Creates new inner frame.
478         *
479         * @return a new frame.
480         */
481        public Frame push() {
482            return new Frame(this);
483        }
484
485        /**
486         * Pulls all referenced types up, except those that are declared in this scope.
487         *
488         * @return the parent frame
489         */
490        public Frame pop() {
491            finish();
492            parent.addReferencedTypes(referencedTypes);
493            return parent;
494        }
495
496        /**
497         * Checks whether this type name is used in this frame.
498         *
499         * @param type the type name
500         * @return {@code true} if the type is used
501         */
502        public boolean isReferencedType(String type) {
503            return referencedTypes.contains(type);
504        }
505
506        /**
507         * Creates a new top-level frame for the compilation unit.
508         *
509         * @return a new frame.
510         */
511        public static Frame compilationUnit() {
512            return new Frame(null);
513        }
514
515    }
516
517}