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