001///////////////////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code and other text files for adherence to a set of rules.
003// Copyright (C) 2001-2025 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.Collection;
023import java.util.HashSet;
024import java.util.List;
025import java.util.Optional;
026import java.util.Set;
027import java.util.regex.Matcher;
028import java.util.regex.Pattern;
029import java.util.stream.Collectors;
030import java.util.stream.Stream;
031
032import org.checkerframework.checker.index.qual.IndexOrLow;
033
034import com.puppycrawl.tools.checkstyle.FileStatefulCheck;
035import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
036import com.puppycrawl.tools.checkstyle.api.DetailAST;
037import com.puppycrawl.tools.checkstyle.api.FileContents;
038import com.puppycrawl.tools.checkstyle.api.FullIdent;
039import com.puppycrawl.tools.checkstyle.api.TextBlock;
040import com.puppycrawl.tools.checkstyle.api.TokenTypes;
041import com.puppycrawl.tools.checkstyle.checks.javadoc.JavadocTag;
042import com.puppycrawl.tools.checkstyle.utils.CommonUtil;
043import com.puppycrawl.tools.checkstyle.utils.JavadocUtil;
044import com.puppycrawl.tools.checkstyle.utils.TokenUtil;
045
046/**
047 * <div>
048 * Checks for unused import statements. An import statement
049 * is considered unused if:
050 * </div>
051 *
052 * <ul>
053 * <li>
054 * It is not referenced in the file. The algorithm does not support wild-card
055 * imports like {@code import java.io.*;}. Most IDE's provide very sophisticated
056 * checks for imports that handle wild-card imports.
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 * A static method is imported when used as method reference. In that case,
067 * only the type needs to be imported and that's enough to resolve the method.
068 * </li>
069 * <li>
070 * <b>Optionally:</b> it is referenced in Javadoc comments. This check is on by
071 * default, but it is considered bad practice to introduce a compile-time
072 * dependency for documentation purposes only. As an example, the import
073 * {@code java.util.List} would be considered referenced with the Javadoc
074 * comment {@code {@link List}}. The alternative to avoid introducing a compile-time
075 * dependency would be to write the Javadoc comment as {@code {&#64;link java.util.List}}.
076 * </li>
077 * </ul>
078 *
079 * <p>
080 * The main limitation of this check is handling the cases where:
081 * </p>
082 * <ul>
083 * <li>
084 * An imported type has the same name as a declaration, such as a member variable.
085 * </li>
086 * <li>
087 * There are two or more static imports with the same method name
088 * (javac can distinguish imports with same name but different parameters, but checkstyle can not
089 * due to <a href="https://checkstyle.org/writingchecks.html#Limitations">limitation.</a>)
090 * </li>
091 * </ul>
092 * <ul>
093 * <li>
094 * Property {@code processJavadoc} - Control whether to process Javadoc comments.
095 * Type is {@code boolean}.
096 * Default value is {@code true}.
097 * </li>
098 * </ul>
099 *
100 * <p>
101 * Parent is {@code com.puppycrawl.tools.checkstyle.TreeWalker}
102 * </p>
103 *
104 * <p>
105 * Violation Message Keys:
106 * </p>
107 * <ul>
108 * <li>
109 * {@code import.unused}
110 * </li>
111 * </ul>
112 *
113 * @since 3.0
114 */
115@FileStatefulCheck
116public class UnusedImportsCheck extends AbstractCheck {
117
118    /**
119     * A key is pointing to the warning message text in "messages.properties"
120     * file.
121     */
122    public static final String MSG_KEY = "import.unused";
123
124    /** Regex to match class names. */
125    private static final Pattern CLASS_NAME = CommonUtil.createPattern(
126           "((:?[\\p{L}_$][\\p{L}\\p{N}_$]*\\.)*[\\p{L}_$][\\p{L}\\p{N}_$]*)");
127    /** Regex to match the first class name. */
128    private static final Pattern FIRST_CLASS_NAME = CommonUtil.createPattern(
129           "^" + CLASS_NAME);
130    /** Regex to match argument names. */
131    private static final Pattern ARGUMENT_NAME = CommonUtil.createPattern(
132           "[(,]\\s*" + CLASS_NAME.pattern());
133
134    /** Regexp pattern to match java.lang package. */
135    private static final Pattern JAVA_LANG_PACKAGE_PATTERN =
136        CommonUtil.createPattern("^java\\.lang\\.[a-zA-Z]+$");
137
138    /** Reference pattern. */
139    private static final Pattern REFERENCE = Pattern.compile(
140            "^([a-z_$][a-z\\d_$<>.]*)?(#(.*))?$",
141            Pattern.CASE_INSENSITIVE
142    );
143
144    /** Method pattern. */
145    private static final Pattern METHOD = Pattern.compile(
146            "^([a-z_$#][a-z\\d_$]*)(\\([^)]*\\))?$",
147            Pattern.CASE_INSENSITIVE
148    );
149
150    /** Suffix for the star import. */
151    private static final String STAR_IMPORT_SUFFIX = ".*";
152
153    /** Set of the imports. */
154    private final Set<FullIdent> imports = new HashSet<>();
155
156    /** Flag to indicate when time to start collecting references. */
157    private boolean collect;
158    /** Control whether to process Javadoc comments. */
159    private boolean processJavadoc = true;
160
161    /**
162     * The scope is being processed.
163     * Types declared in a scope can shadow imported types.
164     */
165    private Frame currentFrame;
166
167    /**
168     * Setter to control whether to process Javadoc comments.
169     *
170     * @param value Flag for processing Javadoc comments.
171     * @since 5.4
172     */
173    public void setProcessJavadoc(boolean value) {
174        processJavadoc = value;
175    }
176
177    @Override
178    public void beginTree(DetailAST rootAST) {
179        collect = false;
180        currentFrame = Frame.compilationUnit();
181        imports.clear();
182    }
183
184    @Override
185    public void finishTree(DetailAST rootAST) {
186        currentFrame.finish();
187        // loop over all the imports to see if referenced.
188        imports.stream()
189            .filter(imprt -> isUnusedImport(imprt.getText()))
190            .forEach(imprt -> log(imprt.getDetailAst(), MSG_KEY, imprt.getText()));
191    }
192
193    @Override
194    public int[] getDefaultTokens() {
195        return getRequiredTokens();
196    }
197
198    @Override
199    public int[] getRequiredTokens() {
200        return new int[] {
201            TokenTypes.IDENT,
202            TokenTypes.IMPORT,
203            TokenTypes.STATIC_IMPORT,
204            // Definitions that may contain Javadoc...
205            TokenTypes.PACKAGE_DEF,
206            TokenTypes.ANNOTATION_DEF,
207            TokenTypes.ANNOTATION_FIELD_DEF,
208            TokenTypes.ENUM_DEF,
209            TokenTypes.ENUM_CONSTANT_DEF,
210            TokenTypes.CLASS_DEF,
211            TokenTypes.INTERFACE_DEF,
212            TokenTypes.METHOD_DEF,
213            TokenTypes.CTOR_DEF,
214            TokenTypes.VARIABLE_DEF,
215            TokenTypes.RECORD_DEF,
216            TokenTypes.COMPACT_CTOR_DEF,
217            // Tokens for creating a new frame
218            TokenTypes.OBJBLOCK,
219            TokenTypes.SLIST,
220        };
221    }
222
223    @Override
224    public int[] getAcceptableTokens() {
225        return getRequiredTokens();
226    }
227
228    @Override
229    public void visitToken(DetailAST ast) {
230        switch (ast.getType()) {
231            case TokenTypes.IDENT:
232                if (collect) {
233                    processIdent(ast);
234                }
235                break;
236            case TokenTypes.IMPORT:
237                processImport(ast);
238                break;
239            case TokenTypes.STATIC_IMPORT:
240                processStaticImport(ast);
241                break;
242            case TokenTypes.OBJBLOCK:
243            case TokenTypes.SLIST:
244                currentFrame = currentFrame.push();
245                break;
246            default:
247                collect = true;
248                if (processJavadoc) {
249                    collectReferencesFromJavadoc(ast);
250                }
251                break;
252        }
253    }
254
255    @Override
256    public void leaveToken(DetailAST ast) {
257        if (TokenUtil.isOfType(ast, TokenTypes.OBJBLOCK, TokenTypes.SLIST)) {
258            currentFrame = currentFrame.pop();
259        }
260    }
261
262    /**
263     * Checks whether an import is unused.
264     *
265     * @param imprt an import.
266     * @return true if an import is unused.
267     */
268    private boolean isUnusedImport(String imprt) {
269        final Matcher javaLangPackageMatcher = JAVA_LANG_PACKAGE_PATTERN.matcher(imprt);
270        return !currentFrame.isReferencedType(CommonUtil.baseClassName(imprt))
271            || javaLangPackageMatcher.matches();
272    }
273
274    /**
275     * Collects references made by IDENT.
276     *
277     * @param ast the IDENT node to process
278     */
279    private void processIdent(DetailAST ast) {
280        final DetailAST parent = ast.getParent();
281        final int parentType = parent.getType();
282
283        final boolean isClassOrMethod = parentType == TokenTypes.DOT
284                || parentType == TokenTypes.METHOD_DEF || parentType == TokenTypes.METHOD_REF;
285
286        if (TokenUtil.isTypeDeclaration(parentType)) {
287            currentFrame.addDeclaredType(ast.getText());
288        }
289        else if (!isClassOrMethod || isQualifiedIdentifier(ast)) {
290            currentFrame.addReferencedType(ast.getText());
291        }
292    }
293
294    /**
295     * Checks whether ast is a fully qualified identifier.
296     *
297     * @param ast to check
298     * @return true if given ast is a fully qualified identifier
299     */
300    private static boolean isQualifiedIdentifier(DetailAST ast) {
301        final DetailAST parent = ast.getParent();
302        final int parentType = parent.getType();
303
304        final boolean isQualifiedIdent = parentType == TokenTypes.DOT
305                && !TokenUtil.isOfType(ast.getPreviousSibling(), TokenTypes.DOT)
306                && ast.getNextSibling() != null;
307        final boolean isQualifiedIdentFromMethodRef = parentType == TokenTypes.METHOD_REF
308                && ast.getNextSibling() != null;
309        return isQualifiedIdent || isQualifiedIdentFromMethodRef;
310    }
311
312    /**
313     * Collects the details of imports.
314     *
315     * @param ast node containing the import details
316     */
317    private void processImport(DetailAST ast) {
318        final FullIdent name = FullIdent.createFullIdentBelow(ast);
319        if (!name.getText().endsWith(STAR_IMPORT_SUFFIX)) {
320            imports.add(name);
321        }
322    }
323
324    /**
325     * Collects the details of static imports.
326     *
327     * @param ast node containing the static import details
328     */
329    private void processStaticImport(DetailAST ast) {
330        final FullIdent name =
331            FullIdent.createFullIdent(
332                ast.getFirstChild().getNextSibling());
333        if (!name.getText().endsWith(STAR_IMPORT_SUFFIX)) {
334            imports.add(name);
335        }
336    }
337
338    /**
339     * Collects references made in Javadoc comments.
340     *
341     * @param ast node to inspect for Javadoc
342     */
343    // suppress deprecation until https://github.com/checkstyle/checkstyle/issues/11166
344    @SuppressWarnings("deprecation")
345    private void collectReferencesFromJavadoc(DetailAST ast) {
346        final FileContents contents = getFileContents();
347        final int lineNo = ast.getLineNo();
348        final TextBlock textBlock = contents.getJavadocBefore(lineNo);
349        if (textBlock != null) {
350            currentFrame.addReferencedTypes(collectReferencesFromJavadoc(textBlock));
351        }
352    }
353
354    /**
355     * Process a javadoc {@link TextBlock} and return the set of classes
356     * referenced within.
357     *
358     * @param textBlock The javadoc block to parse
359     * @return a set of classes referenced in the javadoc block
360     */
361    private static Set<String> collectReferencesFromJavadoc(TextBlock textBlock) {
362        // Process INLINE tags
363        final List<JavadocTag> inlineTags = getTargetTags(textBlock,
364                JavadocUtil.JavadocTagType.INLINE);
365        // Process BLOCK tags
366        final List<JavadocTag> blockTags = getTargetTags(textBlock,
367                JavadocUtil.JavadocTagType.BLOCK);
368        final List<JavadocTag> targetTags = Stream.concat(inlineTags.stream(), blockTags.stream())
369                .collect(Collectors.toUnmodifiableList());
370
371        final Set<String> references = new HashSet<>();
372
373        targetTags.stream()
374            .filter(JavadocTag::canReferenceImports)
375            .forEach(tag -> references.addAll(processJavadocTag(tag)));
376        return references;
377    }
378
379    /**
380     * Returns the list of valid tags found in a javadoc {@link TextBlock}.
381     * Filters tags based on whether they are inline or block tags, ensuring they match
382     * the correct format supported.
383     *
384     * @param cmt The javadoc block to parse
385     * @param javadocTagType The type of tags we're interested in
386     * @return the list of tags
387     */
388    private static List<JavadocTag> getTargetTags(TextBlock cmt,
389            JavadocUtil.JavadocTagType javadocTagType) {
390        return JavadocUtil.getJavadocTags(cmt, javadocTagType)
391            .getValidTags()
392            .stream()
393            .filter(tag -> isMatchingTagType(tag, javadocTagType))
394            .map(UnusedImportsCheck::bestTryToMatchReference)
395            .flatMap(Optional::stream)
396            .collect(Collectors.toUnmodifiableList());
397    }
398
399    /**
400     * Returns a list of references that found in a javadoc {@link JavadocTag}.
401     *
402     * @param tag The javadoc tag to parse
403     * @return A list of references that found in this tag
404     */
405    private static Set<String> processJavadocTag(JavadocTag tag) {
406        final Set<String> references = new HashSet<>();
407        final String identifier = tag.getFirstArg();
408        for (Pattern pattern : new Pattern[]
409        {FIRST_CLASS_NAME, ARGUMENT_NAME}) {
410            references.addAll(matchPattern(identifier, pattern));
411        }
412        return references;
413    }
414
415    /**
416     * Extracts a set of texts matching a {@link Pattern} from a
417     * {@link String}.
418     *
419     * @param identifier The String to match the pattern against
420     * @param pattern The Pattern used to extract the texts
421     * @return A set of texts which matched the pattern
422     */
423    private static Set<String> matchPattern(String identifier, Pattern pattern) {
424        final Set<String> references = new HashSet<>();
425        final Matcher matcher = pattern.matcher(identifier);
426        while (matcher.find()) {
427            references.add(topLevelType(matcher.group(1)));
428        }
429        return references;
430    }
431
432    /**
433     * If the given type string contains "." (e.g. "Map.Entry"), returns the
434     * top level type (e.g. "Map"), as that is what must be imported for the
435     * type to resolve. Otherwise, returns the type as-is.
436     *
437     * @param type A possibly qualified type name
438     * @return The simple name of the top level type
439     */
440    private static String topLevelType(String type) {
441        final String topLevelType;
442        final int dotIndex = type.indexOf('.');
443        if (dotIndex == -1) {
444            topLevelType = type;
445        }
446        else {
447            topLevelType = type.substring(0, dotIndex);
448        }
449        return topLevelType;
450    }
451
452    /**
453     * Checks if a Javadoc tag matches the expected type based on its extraction format.
454     * This method checks if an inline tag is extracted as a block tag or vice versa.
455     * It ensures that block tags are correctly recognized as block tags and inline tags
456     * as inline tags during processing.
457     *
458     * @param tag The Javadoc tag to check.
459     * @param javadocTagType The expected type of the tag (BLOCK or INLINE).
460     * @return {@code true} if the tag matches the expected type, otherwise {@code false}.
461     */
462    private static boolean isMatchingTagType(JavadocTag tag,
463                                             JavadocUtil.JavadocTagType javadocTagType) {
464        final boolean isInlineTag = tag.isInlineTag();
465        final boolean isBlockTagType = javadocTagType == JavadocUtil.JavadocTagType.BLOCK;
466
467        return isBlockTagType != isInlineTag;
468    }
469
470    /**
471     * Attempts to match a reference string against a predefined pattern
472     * and extracts valid reference.
473     *
474     * @param tag the input tag to check
475     * @return Optional of extracted references
476     */
477    public static Optional<JavadocTag> bestTryToMatchReference(JavadocTag tag) {
478        final String content = tag.getFirstArg();
479        final int referenceIndex = extractReferencePart(content);
480        Optional<JavadocTag> validTag = Optional.empty();
481
482        if (referenceIndex != -1) {
483            final String referenceString;
484            if (referenceIndex == 0) {
485                referenceString = content;
486            }
487            else {
488                referenceString = content.substring(0, referenceIndex);
489            }
490            final Matcher matcher = REFERENCE.matcher(referenceString);
491            if (matcher.matches()) {
492                final int methodIndex = 3;
493                final String methodPart = matcher.group(methodIndex);
494                final boolean isValid = methodPart == null
495                        || METHOD.matcher(methodPart).matches();
496                if (isValid) {
497                    validTag = Optional.of(tag);
498                }
499            }
500        }
501        return validTag;
502    }
503
504    /**
505     * Extracts the reference part from an input string while ensuring balanced parentheses.
506     *
507     * @param input the input string
508     * @return -1 if parentheses are unbalanced, 0 if no method is found,
509     *         or the index of the first space outside parentheses.
510     */
511    private static @IndexOrLow("#1")int extractReferencePart(String input) {
512        int parenthesesCount = 0;
513        int firstSpaceOutsideParens = -1;
514        for (int index = 0; index < input.length(); index++) {
515            final char currentCharacter = input.charAt(index);
516
517            if (currentCharacter == '(') {
518                parenthesesCount++;
519            }
520            else if (currentCharacter == ')') {
521                parenthesesCount--;
522            }
523            else if (currentCharacter == ' ' && parenthesesCount == 0) {
524                firstSpaceOutsideParens = index;
525                break;
526            }
527        }
528
529        int methodIndex = -1;
530        if (parenthesesCount == 0) {
531            if (firstSpaceOutsideParens == -1) {
532                methodIndex = 0;
533            }
534            else {
535                methodIndex = firstSpaceOutsideParens;
536            }
537        }
538        return methodIndex;
539    }
540
541    /**
542     * Holds the names of referenced types and names of declared inner types.
543     */
544    private static final class Frame {
545
546        /** Parent frame. */
547        private final Frame parent;
548
549        /** Nested types declared in the current scope. */
550        private final Set<String> declaredTypes;
551
552        /** Set of references - possibly to imports or locally declared types. */
553        private final Set<String> referencedTypes;
554
555        /**
556         * Private constructor. Use {@link #compilationUnit()} to create a new top-level frame.
557         *
558         * @param parent the parent frame
559         */
560        private Frame(Frame parent) {
561            this.parent = parent;
562            declaredTypes = new HashSet<>();
563            referencedTypes = new HashSet<>();
564        }
565
566        /**
567         * Adds new inner type.
568         *
569         * @param type the type name
570         */
571        public void addDeclaredType(String type) {
572            declaredTypes.add(type);
573        }
574
575        /**
576         * Adds new type reference to the current frame.
577         *
578         * @param type the type name
579         */
580        public void addReferencedType(String type) {
581            referencedTypes.add(type);
582        }
583
584        /**
585         * Adds new inner types.
586         *
587         * @param types the type names
588         */
589        public void addReferencedTypes(Collection<String> types) {
590            referencedTypes.addAll(types);
591        }
592
593        /**
594         * Filters out all references to locally defined types.
595         *
596         */
597        public void finish() {
598            referencedTypes.removeAll(declaredTypes);
599        }
600
601        /**
602         * Creates new inner frame.
603         *
604         * @return a new frame.
605         */
606        public Frame push() {
607            return new Frame(this);
608        }
609
610        /**
611         * Pulls all referenced types up, except those that are declared in this scope.
612         *
613         * @return the parent frame
614         */
615        public Frame pop() {
616            finish();
617            parent.addReferencedTypes(referencedTypes);
618            return parent;
619        }
620
621        /**
622         * Checks whether this type name is used in this frame.
623         *
624         * @param type the type name
625         * @return {@code true} if the type is used
626         */
627        public boolean isReferencedType(String type) {
628            return referencedTypes.contains(type);
629        }
630
631        /**
632         * Creates a new top-level frame for the compilation unit.
633         *
634         * @return a new frame.
635         */
636        public static Frame compilationUnit() {
637            return new Frame(null);
638        }
639
640    }
641
642}