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