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