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