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;
021
022import java.io.File;
023import java.util.Arrays;
024import java.util.Collection;
025import java.util.Comparator;
026import java.util.HashMap;
027import java.util.HashSet;
028import java.util.Locale;
029import java.util.Map;
030import java.util.Set;
031import java.util.SortedSet;
032import java.util.TreeSet;
033import java.util.stream.Collectors;
034import java.util.stream.Stream;
035
036import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
037import com.puppycrawl.tools.checkstyle.api.AbstractFileSetCheck;
038import com.puppycrawl.tools.checkstyle.api.CheckstyleException;
039import com.puppycrawl.tools.checkstyle.api.Configuration;
040import com.puppycrawl.tools.checkstyle.api.Context;
041import com.puppycrawl.tools.checkstyle.api.DetailAST;
042import com.puppycrawl.tools.checkstyle.api.ExternalResourceHolder;
043import com.puppycrawl.tools.checkstyle.api.FileContents;
044import com.puppycrawl.tools.checkstyle.api.FileText;
045import com.puppycrawl.tools.checkstyle.api.SeverityLevel;
046import com.puppycrawl.tools.checkstyle.api.Violation;
047import com.puppycrawl.tools.checkstyle.utils.TokenUtil;
048
049/**
050 * Responsible for walking an abstract syntax tree and notifying interested
051 * checks at each node.
052 *
053 */
054@FileStatefulCheck
055public final class TreeWalker extends AbstractFileSetCheck implements ExternalResourceHolder {
056
057    /** Message to use when an exception occurs and should be printed as a violation. */
058    public static final String PARSE_EXCEPTION_MSG = "parse.exception";
059
060    /** Maps from token name to ordinary checks. */
061    private final Map<Integer, Set<AbstractCheck>> tokenToOrdinaryChecks =
062        new HashMap<>();
063
064    /** Maps from token name to comment checks. */
065    private final Map<Integer, Set<AbstractCheck>> tokenToCommentChecks =
066            new HashMap<>();
067
068    /** Registered ordinary checks, that don't use comment nodes. */
069    private final Set<AbstractCheck> ordinaryChecks = createNewCheckSortedSet();
070
071    /** Registered comment checks. */
072    private final Set<AbstractCheck> commentChecks = createNewCheckSortedSet();
073
074    /** The ast filters. */
075    private final Set<TreeWalkerFilter> filters = new HashSet<>();
076
077    /** The sorted set of violations. */
078    private final SortedSet<Violation> violations = new TreeSet<>();
079
080    /** Context of child components. */
081    private Context childContext;
082
083    /** A factory for creating submodules (i.e. the Checks) */
084    private ModuleFactory moduleFactory;
085
086    /** Control whether to skip files with Java parsing exceptions. */
087    private boolean skipFileOnJavaParseException;
088
089    /** Specify severity Level to log Java parsing exceptions when they are skipped. */
090    private SeverityLevel javaParseExceptionSeverity = SeverityLevel.ERROR;
091
092    /**
093     * Creates a new {@code TreeWalker} instance.
094     */
095    public TreeWalker() {
096        setFileExtensions("java");
097    }
098
099    /**
100     * Sets the module factory for creating child modules (Checks).
101     *
102     * @param moduleFactory the factory
103     */
104    public void setModuleFactory(ModuleFactory moduleFactory) {
105        this.moduleFactory = moduleFactory;
106    }
107
108    /**
109     * Setter to control whether to skip files with Java parsing exceptions.
110     *
111     *  @param skipFileOnJavaParseException whether to skip files with Java parsing errors.
112     *  @since 10.18.0
113     */
114    public void setSkipFileOnJavaParseException(boolean skipFileOnJavaParseException) {
115        this.skipFileOnJavaParseException = skipFileOnJavaParseException;
116    }
117
118    /**
119     * Setter to specify the severity level
120     * to log Java parsing exceptions when they are skipped.
121     *
122     *  @param javaParseExceptionSeverity severity level to log parsing exceptions
123     *      when they are skipped.
124     *  @since 10.18.0
125     */
126    public void setJavaParseExceptionSeverity(SeverityLevel javaParseExceptionSeverity) {
127        this.javaParseExceptionSeverity = javaParseExceptionSeverity;
128    }
129
130    @Override
131    public void finishLocalSetup() {
132        final DefaultContext checkContext = new DefaultContext();
133        checkContext.add("severity", getSeverity());
134        checkContext.add("tabWidth", String.valueOf(getTabWidth()));
135        childContext = checkContext;
136    }
137
138    /**
139     * {@inheritDoc} Creates child module.
140     *
141     * @noinspection ChainOfInstanceofChecks
142     * @noinspectionreason ChainOfInstanceofChecks - we treat checks and filters differently
143     */
144    @Override
145    public void setupChild(Configuration childConf)
146            throws CheckstyleException {
147        final String name = childConf.getName();
148        final Object module;
149
150        try {
151            module = moduleFactory.createModule(name);
152            if (module instanceof AbstractAutomaticBean) {
153                final AbstractAutomaticBean bean = (AbstractAutomaticBean) module;
154                bean.contextualize(childContext);
155                bean.configure(childConf);
156            }
157        }
158        catch (final CheckstyleException ex) {
159            throw new CheckstyleException("cannot initialize module " + name
160                    + " - " + ex.getMessage(), ex);
161        }
162        if (module instanceof AbstractCheck) {
163            final AbstractCheck check = (AbstractCheck) module;
164            check.init();
165            registerCheck(check);
166        }
167        else if (module instanceof TreeWalkerFilter) {
168            final TreeWalkerFilter filter = (TreeWalkerFilter) module;
169            filters.add(filter);
170        }
171        else {
172            throw new CheckstyleException(
173                "TreeWalker is not allowed as a parent of " + name
174                        + " Please review 'Parent Module' section for this Check in web"
175                        + " documentation if Check is standard.");
176        }
177    }
178
179    /**
180     * {@inheritDoc} Processes the file.
181     *
182     * @noinspection ProhibitedExceptionThrown
183     * @noinspectionreason ProhibitedExceptionThrown - there is no other way to obey
184     *     skipFileOnJavaParseException field
185     */
186    @Override
187    protected void processFiltered(File file, FileText fileText) throws CheckstyleException {
188        // check if already checked and passed the file
189        if (!ordinaryChecks.isEmpty() || !commentChecks.isEmpty()) {
190            final FileContents contents = getFileContents();
191            DetailAST rootAST = null;
192            // whether skip the procedure after parsing Java files.
193            boolean skip = false;
194            try {
195                rootAST = JavaParser.parse(contents);
196            }
197            // -@cs[IllegalCatch] There is no other way to obey skipFileOnJavaParseException field
198            catch (Exception ex) {
199                if (!skipFileOnJavaParseException) {
200                    throw ex;
201                }
202                skip = true;
203                violations.add(new Violation(1, Definitions.CHECKSTYLE_BUNDLE, PARSE_EXCEPTION_MSG,
204                            new Object[] {ex.getMessage()}, javaParseExceptionSeverity, null,
205                            getClass(), null));
206                addViolations(violations);
207            }
208
209            if (!skip) {
210                if (!ordinaryChecks.isEmpty()) {
211                    walk(rootAST, contents, AstState.ORDINARY);
212                }
213                if (!commentChecks.isEmpty()) {
214                    final DetailAST astWithComments = JavaParser.appendHiddenCommentNodes(rootAST);
215                    walk(astWithComments, contents, AstState.WITH_COMMENTS);
216                }
217                if (filters.isEmpty()) {
218                    addViolations(violations);
219                }
220                else {
221                    final SortedSet<Violation> filteredViolations =
222                            getFilteredViolations(file.getAbsolutePath(), contents, rootAST);
223                    addViolations(filteredViolations);
224                }
225            }
226            violations.clear();
227        }
228    }
229
230    /**
231     * Returns filtered set of {@link Violation}.
232     *
233     * @param fileName path to the file
234     * @param fileContents the contents of the file
235     * @param rootAST root AST element {@link DetailAST} of the file
236     * @return filtered set of violations
237     */
238    private SortedSet<Violation> getFilteredViolations(
239            String fileName, FileContents fileContents, DetailAST rootAST) {
240        final SortedSet<Violation> result = new TreeSet<>(violations);
241        for (Violation element : violations) {
242            final TreeWalkerAuditEvent event =
243                    new TreeWalkerAuditEvent(fileContents, fileName, element, rootAST);
244            for (TreeWalkerFilter filter : filters) {
245                if (!filter.accept(event)) {
246                    result.remove(element);
247                    break;
248                }
249            }
250        }
251        return result;
252    }
253
254    /**
255     * Register a check for a given configuration.
256     *
257     * @param check the check to register
258     * @throws CheckstyleException if an error occurs
259     */
260    private void registerCheck(AbstractCheck check) throws CheckstyleException {
261        final int[] tokens;
262        final Set<String> checkTokens = check.getTokenNames();
263        if (checkTokens.isEmpty()) {
264            tokens = check.getDefaultTokens();
265        }
266        else {
267            tokens = check.getRequiredTokens();
268
269            // register configured tokens
270            final int[] acceptableTokens = check.getAcceptableTokens();
271            Arrays.sort(acceptableTokens);
272            for (String token : checkTokens) {
273                final int tokenId = TokenUtil.getTokenId(token);
274                if (Arrays.binarySearch(acceptableTokens, tokenId) >= 0) {
275                    registerCheck(tokenId, check);
276                }
277                else {
278                    final String message = String.format(Locale.ROOT, "Token \"%s\" was "
279                            + "not found in Acceptable tokens list in check %s",
280                            token, check.getClass().getName());
281                    throw new CheckstyleException(message);
282                }
283            }
284        }
285        for (int element : tokens) {
286            registerCheck(element, check);
287        }
288        if (check.isCommentNodesRequired()) {
289            commentChecks.add(check);
290        }
291        else {
292            ordinaryChecks.add(check);
293        }
294    }
295
296    /**
297     * Register a check for a specified token id.
298     *
299     * @param tokenId the id of the token
300     * @param check the check to register
301     * @throws CheckstyleException if Check is misconfigured
302     */
303    private void registerCheck(int tokenId, AbstractCheck check) throws CheckstyleException {
304        if (check.isCommentNodesRequired()) {
305            tokenToCommentChecks.computeIfAbsent(tokenId, empty -> createNewCheckSortedSet())
306                    .add(check);
307        }
308        else if (TokenUtil.isCommentType(tokenId)) {
309            final String message = String.format(Locale.ROOT, "Check '%s' waits for comment type "
310                    + "token ('%s') and should override 'isCommentNodesRequired()' "
311                    + "method to return 'true'", check.getClass().getName(),
312                    TokenUtil.getTokenName(tokenId));
313            throw new CheckstyleException(message);
314        }
315        else {
316            tokenToOrdinaryChecks.computeIfAbsent(tokenId, empty -> createNewCheckSortedSet())
317                    .add(check);
318        }
319    }
320
321    /**
322     * Initiates the walk of an AST.
323     *
324     * @param ast the root AST
325     * @param contents the contents of the file the AST was generated from.
326     * @param astState state of AST.
327     */
328    private void walk(DetailAST ast, FileContents contents,
329            AstState astState) {
330        notifyBegin(ast, contents, astState);
331        processIter(ast, astState);
332        notifyEnd(ast, astState);
333    }
334
335    /**
336     * Notify checks that we are about to begin walking a tree.
337     *
338     * @param rootAST the root of the tree.
339     * @param contents the contents of the file the AST was generated from.
340     * @param astState state of AST.
341     */
342    private void notifyBegin(DetailAST rootAST, FileContents contents,
343            AstState astState) {
344        final Set<AbstractCheck> checks;
345
346        if (astState == AstState.WITH_COMMENTS) {
347            checks = commentChecks;
348        }
349        else {
350            checks = ordinaryChecks;
351        }
352
353        for (AbstractCheck check : checks) {
354            check.setFileContents(contents);
355            check.clearViolations();
356            check.beginTree(rootAST);
357        }
358    }
359
360    /**
361     * Notify checks that we have finished walking a tree.
362     *
363     * @param rootAST the root of the tree.
364     * @param astState state of AST.
365     */
366    private void notifyEnd(DetailAST rootAST, AstState astState) {
367        final Set<AbstractCheck> checks;
368
369        if (astState == AstState.WITH_COMMENTS) {
370            checks = commentChecks;
371        }
372        else {
373            checks = ordinaryChecks;
374        }
375
376        for (AbstractCheck check : checks) {
377            check.finishTree(rootAST);
378            violations.addAll(check.getViolations());
379        }
380    }
381
382    /**
383     * Notify checks that visiting a node.
384     *
385     * @param ast the node to notify for.
386     * @param astState state of AST.
387     */
388    private void notifyVisit(DetailAST ast, AstState astState) {
389        final Collection<AbstractCheck> visitors = getListOfChecks(ast, astState);
390
391        if (visitors != null) {
392            for (AbstractCheck check : visitors) {
393                check.visitToken(ast);
394            }
395        }
396    }
397
398    /**
399     * Notify checks that leaving a node.
400     *
401     * @param ast
402     *        the node to notify for
403     * @param astState state of AST.
404     */
405    private void notifyLeave(DetailAST ast, AstState astState) {
406        final Collection<AbstractCheck> visitors = getListOfChecks(ast, astState);
407
408        if (visitors != null) {
409            for (AbstractCheck check : visitors) {
410                check.leaveToken(ast);
411            }
412        }
413    }
414
415    /**
416     * Method returns list of checks.
417     *
418     * @param ast
419     *            the node to notify for
420     * @param astState
421     *            state of AST.
422     * @return list of visitors
423     */
424    private Collection<AbstractCheck> getListOfChecks(DetailAST ast, AstState astState) {
425        final Collection<AbstractCheck> visitors;
426        final int tokenId = ast.getType();
427
428        if (astState == AstState.WITH_COMMENTS) {
429            visitors = tokenToCommentChecks.get(tokenId);
430        }
431        else {
432            visitors = tokenToOrdinaryChecks.get(tokenId);
433        }
434        return visitors;
435    }
436
437    @Override
438    public void destroy() {
439        ordinaryChecks.forEach(AbstractCheck::destroy);
440        commentChecks.forEach(AbstractCheck::destroy);
441        super.destroy();
442    }
443
444    @Override
445    public Set<String> getExternalResourceLocations() {
446        return Stream.concat(filters.stream(),
447                Stream.concat(ordinaryChecks.stream(), commentChecks.stream()))
448            .filter(ExternalResourceHolder.class::isInstance)
449            .flatMap(resource -> {
450                return ((ExternalResourceHolder) resource)
451                        .getExternalResourceLocations().stream();
452            })
453            .collect(Collectors.toUnmodifiableSet());
454    }
455
456    /**
457     * Processes a node calling interested checks at each node.
458     * Uses iterative algorithm.
459     *
460     * @param root the root of tree for process
461     * @param astState state of AST.
462     */
463    private void processIter(DetailAST root, AstState astState) {
464        DetailAST curNode = root;
465        while (curNode != null) {
466            notifyVisit(curNode, astState);
467            DetailAST toVisit = curNode.getFirstChild();
468            while (curNode != null && toVisit == null) {
469                notifyLeave(curNode, astState);
470                toVisit = curNode.getNextSibling();
471                curNode = curNode.getParent();
472            }
473            curNode = toVisit;
474        }
475    }
476
477    /**
478     * Creates a new {@link SortedSet} with a deterministic order based on the
479     * Check's name before the default ordering.
480     *
481     * @return The new {@link SortedSet}.
482     */
483    private static SortedSet<AbstractCheck> createNewCheckSortedSet() {
484        return new TreeSet<>(
485                Comparator.<AbstractCheck, String>comparing(check -> check.getClass().getName())
486                        .thenComparing(AbstractCheck::getId,
487                                Comparator.nullsLast(Comparator.naturalOrder()))
488                        .thenComparingInt(AbstractCheck::hashCode));
489    }
490
491    /**
492     * State of AST.
493     * Indicates whether tree contains certain nodes.
494     */
495    private enum AstState {
496
497        /**
498         * Ordinary tree.
499         */
500        ORDINARY,
501
502        /**
503         * AST contains comment nodes.
504         */
505        WITH_COMMENTS,
506
507    }
508
509}