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