001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2017 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.io.Reader;
024import java.io.StringReader;
025import java.util.AbstractMap.SimpleEntry;
026import java.util.Arrays;
027import java.util.Collection;
028import java.util.HashSet;
029import java.util.List;
030import java.util.Locale;
031import java.util.Map.Entry;
032import java.util.Set;
033
034import antlr.CommonHiddenStreamToken;
035import antlr.RecognitionException;
036import antlr.Token;
037import antlr.TokenStreamException;
038import antlr.TokenStreamHiddenTokenFilter;
039import antlr.TokenStreamRecognitionException;
040import com.google.common.collect.HashMultimap;
041import com.google.common.collect.Multimap;
042import com.puppycrawl.tools.checkstyle.api.AbstractCheck;
043import com.puppycrawl.tools.checkstyle.api.AbstractFileSetCheck;
044import com.puppycrawl.tools.checkstyle.api.CheckstyleException;
045import com.puppycrawl.tools.checkstyle.api.Configuration;
046import com.puppycrawl.tools.checkstyle.api.Context;
047import com.puppycrawl.tools.checkstyle.api.DetailAST;
048import com.puppycrawl.tools.checkstyle.api.ExternalResourceHolder;
049import com.puppycrawl.tools.checkstyle.api.FileContents;
050import com.puppycrawl.tools.checkstyle.api.FileText;
051import com.puppycrawl.tools.checkstyle.api.TokenTypes;
052import com.puppycrawl.tools.checkstyle.grammars.GeneratedJavaLexer;
053import com.puppycrawl.tools.checkstyle.grammars.GeneratedJavaRecognizer;
054import com.puppycrawl.tools.checkstyle.utils.CommonUtils;
055import com.puppycrawl.tools.checkstyle.utils.TokenUtils;
056
057/**
058 * Responsible for walking an abstract syntax tree and notifying interested
059 * checks at each each node.
060 *
061 * @author Oliver Burn
062 */
063public final class TreeWalker extends AbstractFileSetCheck implements ExternalResourceHolder {
064
065    /** Default distance between tab stops. */
066    private static final int DEFAULT_TAB_WIDTH = 8;
067
068    /** Maps from token name to ordinary checks. */
069    private final Multimap<String, AbstractCheck> tokenToOrdinaryChecks =
070        HashMultimap.create();
071
072    /** Maps from token name to comment checks. */
073    private final Multimap<String, AbstractCheck> tokenToCommentChecks =
074            HashMultimap.create();
075
076    /** Registered ordinary checks, that don't use comment nodes. */
077    private final Set<AbstractCheck> ordinaryChecks = new HashSet<>();
078
079    /** Registered comment checks. */
080    private final Set<AbstractCheck> commentChecks = new HashSet<>();
081
082    /** The distance between tab stops. */
083    private int tabWidth = DEFAULT_TAB_WIDTH;
084
085    /** Class loader to resolve classes with. **/
086    private ClassLoader classLoader;
087
088    /** Context of child components. */
089    private Context childContext;
090
091    /** A factory for creating submodules (i.e. the Checks) */
092    private ModuleFactory moduleFactory;
093
094    /**
095     * Creates a new {@code TreeWalker} instance.
096     */
097    public TreeWalker() {
098        setFileExtensions("java");
099    }
100
101    /**
102     * Sets tab width.
103     * @param tabWidth the distance between tab stops
104     */
105    public void setTabWidth(int tabWidth) {
106        this.tabWidth = tabWidth;
107    }
108
109    /**
110     * Sets cache file.
111     * @deprecated Use {@link Checker#setCacheFile} instead. It does not do anything now. We just
112     *             keep the setter for transition period to the same option in Checker. The
113     *             method will be completely removed in Checkstyle 8.0. See
114     *             <a href="https://github.com/checkstyle/checkstyle/issues/2883">issue#2883</a>
115     * @param fileName the cache file
116     */
117    @Deprecated
118    public void setCacheFile(String fileName) {
119        // Deprecated
120    }
121
122    /**
123     * @param classLoader class loader to resolve classes with.
124     */
125    public void setClassLoader(ClassLoader classLoader) {
126        this.classLoader = classLoader;
127    }
128
129    /**
130     * Sets the module factory for creating child modules (Checks).
131     * @param moduleFactory the factory
132     */
133    public void setModuleFactory(ModuleFactory moduleFactory) {
134        this.moduleFactory = moduleFactory;
135    }
136
137    @Override
138    public void finishLocalSetup() {
139        final DefaultContext checkContext = new DefaultContext();
140        checkContext.add("classLoader", classLoader);
141        checkContext.add("messages", getMessageCollector());
142        checkContext.add("severity", getSeverity());
143        checkContext.add("tabWidth", String.valueOf(tabWidth));
144
145        childContext = checkContext;
146    }
147
148    @Override
149    public void setupChild(Configuration childConf)
150            throws CheckstyleException {
151        final String name = childConf.getName();
152        final Object module = moduleFactory.createModule(name);
153        if (!(module instanceof AbstractCheck)) {
154            throw new CheckstyleException(
155                "TreeWalker is not allowed as a parent of " + name);
156        }
157        final AbstractCheck check = (AbstractCheck) module;
158        check.contextualize(childContext);
159        check.configure(childConf);
160        check.init();
161
162        registerCheck(check);
163    }
164
165    @Override
166    protected void processFiltered(File file, List<String> lines) throws CheckstyleException {
167        // check if already checked and passed the file
168        if (CommonUtils.matchesFileExtension(file, getFileExtensions())) {
169            final String msg = "%s occurred during the analysis of file %s.";
170            final String fileName = file.getPath();
171            try {
172                final FileText text = FileText.fromLines(file, lines);
173                final FileContents contents = new FileContents(text);
174                final DetailAST rootAST = parse(contents);
175
176                getMessageCollector().reset();
177
178                walk(rootAST, contents, AstState.ORDINARY);
179
180                final DetailAST astWithComments = appendHiddenCommentNodes(rootAST);
181
182                walk(astWithComments, contents, AstState.WITH_COMMENTS);
183            }
184            catch (final TokenStreamRecognitionException tre) {
185                final String exceptionMsg = String.format(Locale.ROOT, msg,
186                        "TokenStreamRecognitionException", fileName);
187                throw new CheckstyleException(exceptionMsg, tre);
188            }
189            catch (RecognitionException | TokenStreamException ex) {
190                final String exceptionMsg = String.format(Locale.ROOT, msg,
191                        ex.getClass().getSimpleName(), fileName);
192                throw new CheckstyleException(exceptionMsg, ex);
193            }
194        }
195    }
196
197    /**
198     * Register a check for a given configuration.
199     * @param check the check to register
200     * @throws CheckstyleException if an error occurs
201     */
202    private void registerCheck(AbstractCheck check)
203            throws CheckstyleException {
204        validateDefaultTokens(check);
205        final int[] tokens;
206        final Set<String> checkTokens = check.getTokenNames();
207        if (checkTokens.isEmpty()) {
208            tokens = check.getDefaultTokens();
209        }
210        else {
211            tokens = check.getRequiredTokens();
212
213            //register configured tokens
214            final int[] acceptableTokens = check.getAcceptableTokens();
215            Arrays.sort(acceptableTokens);
216            for (String token : checkTokens) {
217                final int tokenId = TokenUtils.getTokenId(token);
218                if (Arrays.binarySearch(acceptableTokens, tokenId) >= 0) {
219                    registerCheck(token, check);
220                }
221                else {
222                    final String message = String.format(Locale.ROOT, "Token \"%s\" was "
223                            + "not found in Acceptable tokens list in check %s",
224                            token, check.getClass().getName());
225                    throw new CheckstyleException(message);
226                }
227            }
228        }
229        for (int element : tokens) {
230            registerCheck(element, check);
231        }
232        if (check.isCommentNodesRequired()) {
233            commentChecks.add(check);
234        }
235        else {
236            ordinaryChecks.add(check);
237        }
238    }
239
240    /**
241     * Register a check for a specified token id.
242     * @param tokenId the id of the token
243     * @param check the check to register
244     * @throws CheckstyleException if Check is misconfigured
245     */
246    private void registerCheck(int tokenId, AbstractCheck check) throws CheckstyleException {
247        registerCheck(TokenUtils.getTokenName(tokenId), check);
248    }
249
250    /**
251     * Register a check for a specified token name.
252     * @param token the name of the token
253     * @param check the check to register
254     * @throws CheckstyleException if Check is misconfigured
255     */
256    private void registerCheck(String token, AbstractCheck check) throws CheckstyleException {
257        if (check.isCommentNodesRequired()) {
258            tokenToCommentChecks.put(token, check);
259        }
260        else if (TokenUtils.isCommentType(token)) {
261            final String message = String.format(Locale.ROOT, "Check '%s' waits for comment type "
262                    + "token ('%s') and should override 'isCommentNodesRequired()' "
263                    + "method to return 'true'", check.getClass().getName(), token);
264            throw new CheckstyleException(message);
265        }
266        else {
267            tokenToOrdinaryChecks.put(token, check);
268        }
269    }
270
271    /**
272     * Validates that check's required tokens are subset of default tokens.
273     * @param check to validate
274     * @throws CheckstyleException when validation of default tokens fails
275     */
276    private static void validateDefaultTokens(AbstractCheck check) throws CheckstyleException {
277        if (check.getRequiredTokens().length != 0) {
278            final int[] defaultTokens = check.getDefaultTokens();
279            Arrays.sort(defaultTokens);
280            for (final int token : check.getRequiredTokens()) {
281                if (Arrays.binarySearch(defaultTokens, token) < 0) {
282                    final String message = String.format(Locale.ROOT, "Token \"%s\" from required "
283                            + "tokens was not found in default tokens list in check %s",
284                            token, check.getClass().getName());
285                    throw new CheckstyleException(message);
286                }
287            }
288        }
289    }
290
291    /**
292     * Initiates the walk of an AST.
293     * @param ast the root AST
294     * @param contents the contents of the file the AST was generated from.
295     * @param astState state of AST.
296     */
297    private void walk(DetailAST ast, FileContents contents,
298            AstState astState) {
299        notifyBegin(ast, contents, astState);
300
301        // empty files are not flagged by javac, will yield ast == null
302        if (ast != null) {
303            processIter(ast, astState);
304        }
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.beginTree(rootAST);
328        }
329    }
330
331    /**
332     * Notify checks that we have finished walking a tree.
333     * @param rootAST the root of the tree.
334     * @param astState state of AST.
335     */
336    private void notifyEnd(DetailAST rootAST, AstState astState) {
337        final Set<AbstractCheck> checks;
338
339        if (astState == AstState.WITH_COMMENTS) {
340            checks = commentChecks;
341        }
342        else {
343            checks = ordinaryChecks;
344        }
345
346        for (AbstractCheck check : checks) {
347            check.finishTree(rootAST);
348        }
349    }
350
351    /**
352     * Notify checks that visiting a node.
353     * @param ast the node to notify for.
354     * @param astState state of AST.
355     */
356    private void notifyVisit(DetailAST ast, AstState astState) {
357        final Collection<AbstractCheck> visitors = getListOfChecks(ast, astState);
358
359        if (visitors != null) {
360            for (AbstractCheck check : visitors) {
361                check.visitToken(ast);
362            }
363        }
364    }
365
366    /**
367     * Notify checks that leaving a node.
368     * @param ast
369     *        the node to notify for
370     * @param astState state of AST.
371     */
372    private void notifyLeave(DetailAST ast, AstState astState) {
373        final Collection<AbstractCheck> visitors = getListOfChecks(ast, astState);
374
375        if (visitors != null) {
376            for (AbstractCheck check : visitors) {
377                check.leaveToken(ast);
378            }
379        }
380    }
381
382    /**
383     * Method returns list of checks
384     *
385     * @param ast
386     *            the node to notify for
387     * @param astState
388     *            state of AST.
389     * @return list of visitors
390     */
391    private Collection<AbstractCheck> getListOfChecks(DetailAST ast, AstState astState) {
392        Collection<AbstractCheck> visitors = null;
393        final String tokenType = TokenUtils.getTokenName(ast.getType());
394
395        if (astState == AstState.WITH_COMMENTS) {
396            if (tokenToCommentChecks.containsKey(tokenType)) {
397                visitors = tokenToCommentChecks.get(tokenType);
398            }
399        }
400        else {
401            if (tokenToOrdinaryChecks.containsKey(tokenType)) {
402                visitors = tokenToOrdinaryChecks.get(tokenType);
403            }
404        }
405        return visitors;
406    }
407
408    /**
409     * Static helper method to parses a Java source file.
410     *
411     * @param contents
412     *                contains the contents of the file
413     * @return the root of the AST
414     * @throws TokenStreamException
415     *                 if lexing failed
416     * @throws RecognitionException
417     *                 if parsing failed
418     */
419    public static DetailAST parse(FileContents contents)
420            throws RecognitionException, TokenStreamException {
421        final String fullText = contents.getText().getFullText().toString();
422        final Reader reader = new StringReader(fullText);
423        final GeneratedJavaLexer lexer = new GeneratedJavaLexer(reader);
424        lexer.setFilename(contents.getFileName());
425        lexer.setCommentListener(contents);
426        lexer.setTreatAssertAsKeyword(true);
427        lexer.setTreatEnumAsKeyword(true);
428        lexer.setTokenObjectClass("antlr.CommonHiddenStreamToken");
429
430        final TokenStreamHiddenTokenFilter filter =
431                new TokenStreamHiddenTokenFilter(lexer);
432        filter.hide(TokenTypes.SINGLE_LINE_COMMENT);
433        filter.hide(TokenTypes.BLOCK_COMMENT_BEGIN);
434
435        final GeneratedJavaRecognizer parser =
436            new GeneratedJavaRecognizer(filter);
437        parser.setFilename(contents.getFileName());
438        parser.setASTNodeClass(DetailAST.class.getName());
439        parser.compilationUnit();
440
441        return (DetailAST) parser.getAST();
442    }
443
444    /**
445     * Parses Java source file. Result AST contains comment nodes.
446     * @param contents source file content
447     * @return DetailAST tree
448     * @throws RecognitionException if parser failed
449     * @throws TokenStreamException if lexer failed
450     */
451    public static DetailAST parseWithComments(FileContents contents)
452            throws RecognitionException, TokenStreamException {
453        return appendHiddenCommentNodes(parse(contents));
454    }
455
456    @Override
457    public void destroy() {
458        ordinaryChecks.forEach(AbstractCheck::destroy);
459        commentChecks.forEach(AbstractCheck::destroy);
460        super.destroy();
461    }
462
463    @Override
464    public Set<String> getExternalResourceLocations() {
465        final Set<String> orinaryChecksResources = getExternalResourceLocations(ordinaryChecks);
466        final Set<String> commentChecksResources = getExternalResourceLocations(commentChecks);
467        final int resultListSize = orinaryChecksResources.size() + commentChecksResources.size();
468        final Set<String> resourceLocations = new HashSet<>(resultListSize);
469        resourceLocations.addAll(orinaryChecksResources);
470        resourceLocations.addAll(commentChecksResources);
471        return resourceLocations;
472    }
473
474    /**
475     * Returns a set of external configuration resource locations which are used by the checks set.
476     * @param checks a set of checks.
477     * @return a set of external configuration resource locations which are used by the checks set.
478     */
479    private static Set<String> getExternalResourceLocations(Set<AbstractCheck> checks) {
480        final Set<String> externalConfigurationResources = new HashSet<>();
481        checks.stream().filter(check -> check instanceof ExternalResourceHolder).forEach(check -> {
482            final Set<String> checkExternalResources =
483                ((ExternalResourceHolder) check).getExternalResourceLocations();
484            externalConfigurationResources.addAll(checkExternalResources);
485        });
486        return externalConfigurationResources;
487    }
488
489    /**
490     * Processes a node calling interested checks at each node.
491     * Uses iterative algorithm.
492     * @param root the root of tree for process
493     * @param astState state of AST.
494     */
495    private void processIter(DetailAST root, AstState astState) {
496        DetailAST curNode = root;
497        while (curNode != null) {
498            notifyVisit(curNode, astState);
499            DetailAST toVisit = curNode.getFirstChild();
500            while (curNode != null && toVisit == null) {
501                notifyLeave(curNode, astState);
502                toVisit = curNode.getNextSibling();
503                if (toVisit == null) {
504                    curNode = curNode.getParent();
505                }
506            }
507            curNode = toVisit;
508        }
509    }
510
511    /**
512     * Appends comment nodes to existing AST.
513     * It traverses each node in AST, looks for hidden comment tokens
514     * and appends found comment tokens as nodes in AST.
515     * @param root
516     *        root of AST.
517     * @return root of AST with comment nodes.
518     */
519    private static DetailAST appendHiddenCommentNodes(DetailAST root) {
520        DetailAST result = root;
521        DetailAST curNode = root;
522        DetailAST lastNode = root;
523
524        while (curNode != null) {
525            if (isPositionGreater(curNode, lastNode)) {
526                lastNode = curNode;
527            }
528
529            CommonHiddenStreamToken tokenBefore = curNode.getHiddenBefore();
530            DetailAST currentSibling = curNode;
531            while (tokenBefore != null) {
532                final DetailAST newCommentNode =
533                         createCommentAstFromToken(tokenBefore);
534
535                currentSibling.addPreviousSibling(newCommentNode);
536
537                if (currentSibling == result) {
538                    result = newCommentNode;
539                }
540
541                currentSibling = newCommentNode;
542                tokenBefore = tokenBefore.getHiddenBefore();
543            }
544
545            DetailAST toVisit = curNode.getFirstChild();
546            while (curNode != null && toVisit == null) {
547                toVisit = curNode.getNextSibling();
548                if (toVisit == null) {
549                    curNode = curNode.getParent();
550                }
551            }
552            curNode = toVisit;
553        }
554        if (lastNode != null) {
555            CommonHiddenStreamToken tokenAfter = lastNode.getHiddenAfter();
556            DetailAST currentSibling = lastNode;
557            while (tokenAfter != null) {
558                final DetailAST newCommentNode =
559                        createCommentAstFromToken(tokenAfter);
560
561                currentSibling.addNextSibling(newCommentNode);
562
563                currentSibling = newCommentNode;
564                tokenAfter = tokenAfter.getHiddenAfter();
565            }
566        }
567        return result;
568    }
569
570    /**
571     * Checks if position of first DetailAST is greater than position of
572     * second DetailAST. Position is line number and column number in source
573     * file.
574     * @param ast1
575     *        first DetailAST node.
576     * @param ast2
577     *        second DetailAST node.
578     * @return true if position of ast1 is greater than position of ast2.
579     */
580    private static boolean isPositionGreater(DetailAST ast1, DetailAST ast2) {
581        if (ast1.getLineNo() == ast2.getLineNo()) {
582            return ast1.getColumnNo() > ast2.getColumnNo();
583        }
584        else {
585            return ast1.getLineNo() > ast2.getLineNo();
586        }
587    }
588
589    /**
590     * Create comment AST from token. Depending on token type
591     * SINGLE_LINE_COMMENT or BLOCK_COMMENT_BEGIN is created.
592     * @param token
593     *        Token object.
594     * @return DetailAST of comment node.
595     */
596    private static DetailAST createCommentAstFromToken(Token token) {
597        if (token.getType() == TokenTypes.SINGLE_LINE_COMMENT) {
598            return createSlCommentNode(token);
599        }
600        else {
601            return createBlockCommentNode(token);
602        }
603    }
604
605    /**
606     * Create single-line comment from token.
607     * @param token
608     *        Token object.
609     * @return DetailAST with SINGLE_LINE_COMMENT type.
610     */
611    private static DetailAST createSlCommentNode(Token token) {
612        final DetailAST slComment = new DetailAST();
613        slComment.setType(TokenTypes.SINGLE_LINE_COMMENT);
614        slComment.setText("//");
615
616        // column counting begins from 0
617        slComment.setColumnNo(token.getColumn() - 1);
618        slComment.setLineNo(token.getLine());
619
620        final DetailAST slCommentContent = new DetailAST();
621        slCommentContent.initialize(token);
622        slCommentContent.setType(TokenTypes.COMMENT_CONTENT);
623
624        // column counting begins from 0
625        // plus length of '//'
626        slCommentContent.setColumnNo(token.getColumn() - 1 + 2);
627        slCommentContent.setLineNo(token.getLine());
628        slCommentContent.setText(token.getText());
629
630        slComment.addChild(slCommentContent);
631        return slComment;
632    }
633
634    /**
635     * Create block comment from token.
636     * @param token
637     *        Token object.
638     * @return DetailAST with BLOCK_COMMENT type.
639     */
640    private static DetailAST createBlockCommentNode(Token token) {
641        final DetailAST blockComment = new DetailAST();
642        blockComment.initialize(TokenTypes.BLOCK_COMMENT_BEGIN, "/*");
643
644        // column counting begins from 0
645        blockComment.setColumnNo(token.getColumn() - 1);
646        blockComment.setLineNo(token.getLine());
647
648        final DetailAST blockCommentContent = new DetailAST();
649        blockCommentContent.initialize(token);
650        blockCommentContent.setType(TokenTypes.COMMENT_CONTENT);
651
652        // column counting begins from 0
653        // plus length of '/*'
654        blockCommentContent.setColumnNo(token.getColumn() - 1 + 2);
655        blockCommentContent.setLineNo(token.getLine());
656        blockCommentContent.setText(token.getText());
657
658        final DetailAST blockCommentClose = new DetailAST();
659        blockCommentClose.initialize(TokenTypes.BLOCK_COMMENT_END, "*/");
660
661        final Entry<Integer, Integer> linesColumns = countLinesColumns(
662                token.getText(), token.getLine(), token.getColumn());
663        blockCommentClose.setLineNo(linesColumns.getKey());
664        blockCommentClose.setColumnNo(linesColumns.getValue());
665
666        blockComment.addChild(blockCommentContent);
667        blockComment.addChild(blockCommentClose);
668        return blockComment;
669    }
670
671    /**
672     * Count lines and columns (in last line) in text.
673     * @param text
674     *        String.
675     * @param initialLinesCnt
676     *        initial value of lines counter.
677     * @param initialColumnsCnt
678     *        initial value of columns counter.
679     * @return entry(pair), first element is lines counter, second - columns
680     *         counter.
681     */
682    private static Entry<Integer, Integer> countLinesColumns(
683            String text, int initialLinesCnt, int initialColumnsCnt) {
684        int lines = initialLinesCnt;
685        int columns = initialColumnsCnt;
686        boolean foundCr = false;
687        for (char c : text.toCharArray()) {
688            if (c == '\n') {
689                foundCr = false;
690                lines++;
691                columns = 0;
692            }
693            else {
694                if (foundCr) {
695                    foundCr = false;
696                    lines++;
697                    columns = 0;
698                }
699                if (c == '\r') {
700                    foundCr = true;
701                }
702                columns++;
703            }
704        }
705        if (foundCr) {
706            lines++;
707            columns = 0;
708        }
709        return new SimpleEntry<>(lines, columns);
710    }
711
712    /**
713     * State of AST.
714     * Indicates whether tree contains certain nodes.
715     */
716    private enum AstState {
717        /**
718         * Ordinary tree.
719         */
720        ORDINARY,
721
722        /**
723         * AST contains comment nodes.
724         */
725        WITH_COMMENTS
726    }
727}