View Javadoc
1   ///////////////////////////////////////////////////////////////////////////////////////////////
2   // checkstyle: Checks Java source code and other text files for adherence to a set of rules.
3   // Copyright (C) 2001-2024 the original author or authors.
4   //
5   // This library is free software; you can redistribute it and/or
6   // modify it under the terms of the GNU Lesser General Public
7   // License as published by the Free Software Foundation; either
8   // version 2.1 of the License, or (at your option) any later version.
9   //
10  // This library is distributed in the hope that it will be useful,
11  // but WITHOUT ANY WARRANTY; without even the implied warranty of
12  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  // Lesser General Public License for more details.
14  //
15  // You should have received a copy of the GNU Lesser General Public
16  // License along with this library; if not, write to the Free Software
17  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18  ///////////////////////////////////////////////////////////////////////////////////////////////
19  
20  package com.puppycrawl.tools.checkstyle;
21  
22  import java.io.File;
23  import java.util.Arrays;
24  import java.util.Collection;
25  import java.util.Comparator;
26  import java.util.HashMap;
27  import java.util.HashSet;
28  import java.util.Locale;
29  import java.util.Map;
30  import java.util.Set;
31  import java.util.SortedSet;
32  import java.util.TreeSet;
33  import java.util.stream.Collectors;
34  import java.util.stream.Stream;
35  
36  import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
37  import com.puppycrawl.tools.checkstyle.api.AbstractFileSetCheck;
38  import com.puppycrawl.tools.checkstyle.api.CheckstyleException;
39  import com.puppycrawl.tools.checkstyle.api.Configuration;
40  import com.puppycrawl.tools.checkstyle.api.Context;
41  import com.puppycrawl.tools.checkstyle.api.DetailAST;
42  import com.puppycrawl.tools.checkstyle.api.ExternalResourceHolder;
43  import com.puppycrawl.tools.checkstyle.api.FileContents;
44  import com.puppycrawl.tools.checkstyle.api.FileText;
45  import com.puppycrawl.tools.checkstyle.api.Violation;
46  import com.puppycrawl.tools.checkstyle.utils.TokenUtil;
47  
48  /**
49   * Responsible for walking an abstract syntax tree and notifying interested
50   * checks at each node.
51   *
52   */
53  @FileStatefulCheck
54  public final class TreeWalker extends AbstractFileSetCheck implements ExternalResourceHolder {
55  
56      /** Maps from token name to ordinary checks. */
57      private final Map<Integer, Set<AbstractCheck>> tokenToOrdinaryChecks =
58          new HashMap<>();
59  
60      /** Maps from token name to comment checks. */
61      private final Map<Integer, Set<AbstractCheck>> tokenToCommentChecks =
62              new HashMap<>();
63  
64      /** Registered ordinary checks, that don't use comment nodes. */
65      private final Set<AbstractCheck> ordinaryChecks = createNewCheckSortedSet();
66  
67      /** Registered comment checks. */
68      private final Set<AbstractCheck> commentChecks = createNewCheckSortedSet();
69  
70      /** The ast filters. */
71      private final Set<TreeWalkerFilter> filters = new HashSet<>();
72  
73      /** The sorted set of violations. */
74      private final SortedSet<Violation> violations = new TreeSet<>();
75  
76      /** Context of child components. */
77      private Context childContext;
78  
79      /** A factory for creating submodules (i.e. the Checks) */
80      private ModuleFactory moduleFactory;
81  
82      /**
83       * Creates a new {@code TreeWalker} instance.
84       */
85      public TreeWalker() {
86          setFileExtensions("java");
87      }
88  
89      /**
90       * Sets the module factory for creating child modules (Checks).
91       *
92       * @param moduleFactory the factory
93       */
94      public void setModuleFactory(ModuleFactory moduleFactory) {
95          this.moduleFactory = moduleFactory;
96      }
97  
98      @Override
99      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 }