001////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code for adherence to a set of rules.
003// Copyright (C) 2001-2014  Oliver Burn
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////////////////////////////////////////////////////////////////////////////////
019package com.puppycrawl.tools.checkstyle;
020
021import antlr.RecognitionException;
022import antlr.TokenStreamException;
023import antlr.TokenStreamRecognitionException;
024
025import com.google.common.collect.HashMultimap;
026import com.google.common.collect.Multimap;
027import com.google.common.collect.Sets;
028import com.puppycrawl.tools.checkstyle.api.AbstractFileSetCheck;
029import com.puppycrawl.tools.checkstyle.api.Check;
030import com.puppycrawl.tools.checkstyle.api.CheckstyleException;
031import com.puppycrawl.tools.checkstyle.api.Configuration;
032import com.puppycrawl.tools.checkstyle.api.Context;
033import com.puppycrawl.tools.checkstyle.api.DetailAST;
034import com.puppycrawl.tools.checkstyle.api.FileContents;
035import com.puppycrawl.tools.checkstyle.api.FileText;
036import com.puppycrawl.tools.checkstyle.api.LocalizedMessage;
037import com.puppycrawl.tools.checkstyle.api.TokenTypes;
038import com.puppycrawl.tools.checkstyle.api.Utils;
039import com.puppycrawl.tools.checkstyle.grammars.GeneratedJavaLexer;
040import com.puppycrawl.tools.checkstyle.grammars.GeneratedJavaRecognizer;
041import java.io.File;
042import java.io.Reader;
043import java.io.StringReader;
044import java.util.Arrays;
045import java.util.Collection;
046import java.util.List;
047import java.util.Set;
048import org.apache.commons.logging.Log;
049import org.apache.commons.logging.LogFactory;
050
051/**
052 * Responsible for walking an abstract syntax tree and notifying interested
053 * checks at each each node.
054 *
055 * @author Oliver Burn
056 * @version 1.0
057 */
058public final class TreeWalker
059    extends AbstractFileSetCheck
060{
061    /** default distance between tab stops */
062    private static final int DEFAULT_TAB_WIDTH = 8;
063
064    /** maps from token name to checks */
065    private final Multimap<String, Check> mTokenToChecks =
066        HashMultimap.create();
067    /** all the registered checks */
068    private final Set<Check> mAllChecks = Sets.newHashSet();
069    /** the distance between tab stops */
070    private int mTabWidth = DEFAULT_TAB_WIDTH;
071    /** cache file **/
072    private PropertyCacheFile mCache = new PropertyCacheFile(null, null);
073
074    /** class loader to resolve classes with. **/
075    private ClassLoader mClassLoader;
076
077    /** context of child components */
078    private Context mChildContext;
079
080    /** a factory for creating submodules (i.e. the Checks) */
081    private ModuleFactory mModuleFactory;
082
083    /** controls whether we should use recursive or iterative
084     * algorithm for tree processing.
085     */
086    private final boolean mRecursive;
087
088    /** logger for debug purpose */
089    private static final Log LOG =
090        LogFactory.getLog("com.puppycrawl.tools.checkstyle.TreeWalker");
091
092    /**
093     * Creates a new <code>TreeWalker</code> instance.
094     */
095    public TreeWalker()
096    {
097        setFileExtensions(new String[]{"java"});
098        // Tree walker can use two possible algorithms for
099        // tree processing (iterative and recursive.
100        // Recursive is default for now.
101        final String recursive =
102            System.getProperty("checkstyle.use.recursive.algorithm", "false");
103        mRecursive = "true".equals(recursive);
104        if (mRecursive) {
105            LOG.debug("TreeWalker uses recursive algorithm");
106        }
107        else {
108            LOG.debug("TreeWalker uses iterative algorithm");
109        }
110    }
111
112    /** @param aTabWidth the distance between tab stops */
113    public void setTabWidth(int aTabWidth)
114    {
115        mTabWidth = aTabWidth;
116    }
117
118    /** @param aFileName the cache file */
119    public void setCacheFile(String aFileName)
120    {
121        final Configuration configuration = getConfiguration();
122        mCache = new PropertyCacheFile(configuration, aFileName);
123    }
124
125    /** @param aClassLoader class loader to resolve classes with. */
126    public void setClassLoader(ClassLoader aClassLoader)
127    {
128        mClassLoader = aClassLoader;
129    }
130
131    /**
132     * Sets the module factory for creating child modules (Checks).
133     * @param aModuleFactory the factory
134     */
135    public void setModuleFactory(ModuleFactory aModuleFactory)
136    {
137        mModuleFactory = aModuleFactory;
138    }
139
140    @Override
141    public void finishLocalSetup()
142    {
143        final DefaultContext checkContext = new DefaultContext();
144        checkContext.add("classLoader", mClassLoader);
145        checkContext.add("messages", getMessageCollector());
146        checkContext.add("severity", getSeverity());
147        // TODO: hmmm.. this looks less than elegant
148        // we have just parsed the string,
149        // now we're recreating it only to parse it again a few moments later
150        checkContext.add("tabWidth", String.valueOf(mTabWidth));
151
152        mChildContext = checkContext;
153    }
154
155    @Override
156    public void setupChild(Configuration aChildConf)
157        throws CheckstyleException
158    {
159        // TODO: improve the error handing
160        final String name = aChildConf.getName();
161        final Object module = mModuleFactory.createModule(name);
162        if (!(module instanceof Check)) {
163            throw new CheckstyleException(
164                "TreeWalker is not allowed as a parent of " + name);
165        }
166        final Check c = (Check) module;
167        c.contextualize(mChildContext);
168        c.configure(aChildConf);
169        c.init();
170
171        registerCheck(c);
172    }
173
174    @Override
175    protected void processFiltered(File aFile, List<String> aLines)
176    {
177        // check if already checked and passed the file
178        final String fileName = aFile.getPath();
179        final long timestamp = aFile.lastModified();
180        if (mCache.alreadyChecked(fileName, timestamp)) {
181            return;
182        }
183
184        try {
185            final FileText text = FileText.fromLines(aFile, aLines);
186            final FileContents contents = new FileContents(text);
187            final DetailAST rootAST = TreeWalker.parse(contents);
188            walk(rootAST, contents);
189        }
190        catch (final RecognitionException re) {
191            Utils.getExceptionLogger()
192                .debug("RecognitionException occured.", re);
193            getMessageCollector().add(
194                new LocalizedMessage(
195                    re.getLine(),
196                    re.getColumn(),
197                    Defn.CHECKSTYLE_BUNDLE,
198                    "general.exception",
199                    new String[] {re.getMessage()},
200                    getId(),
201                    this.getClass(), null));
202        }
203        catch (final TokenStreamRecognitionException tre) {
204            Utils.getExceptionLogger()
205                .debug("TokenStreamRecognitionException occured.", tre);
206            final RecognitionException re = tre.recog;
207            if (re != null) {
208                getMessageCollector().add(
209                    new LocalizedMessage(
210                        re.getLine(),
211                        re.getColumn(),
212                        Defn.CHECKSTYLE_BUNDLE,
213                        "general.exception",
214                        new String[] {re.getMessage()},
215                        getId(),
216                        this.getClass(), null));
217            }
218            else {
219                getMessageCollector().add(
220                    new LocalizedMessage(
221                        0,
222                        Defn.CHECKSTYLE_BUNDLE,
223                        "general.exception",
224                        new String[]
225                        {"TokenStreamRecognitionException occured."},
226                        getId(),
227                        this.getClass(), null));
228            }
229        }
230        catch (final TokenStreamException te) {
231            Utils.getExceptionLogger()
232                .debug("TokenStreamException occured.", te);
233            getMessageCollector().add(
234                new LocalizedMessage(
235                    0,
236                    Defn.CHECKSTYLE_BUNDLE,
237                    "general.exception",
238                    new String[] {te.getMessage()},
239                    getId(),
240                    this.getClass(), null));
241        }
242        catch (final Throwable err) {
243            Utils.getExceptionLogger().debug("Throwable occured.", err);
244            getMessageCollector().add(
245                new LocalizedMessage(
246                    0,
247                    Defn.CHECKSTYLE_BUNDLE,
248                    "general.exception",
249                    new String[] {"" + err},
250                    getId(),
251                    this.getClass(), null));
252        }
253
254        if (getMessageCollector().size() == 0) {
255            mCache.checkedOk(fileName, timestamp);
256        }
257    }
258
259    /**
260     * Register a check for a given configuration.
261     * @param aCheck the check to register
262     * @throws CheckstyleException if an error occurs
263     */
264    private void registerCheck(Check aCheck)
265        throws CheckstyleException
266    {
267        final int[] tokens;
268        final Set<String> checkTokens = aCheck.getTokenNames();
269        if (!checkTokens.isEmpty()) {
270            tokens = aCheck.getRequiredTokens();
271
272            //register configured tokens
273            final int acceptableTokens[] = aCheck.getAcceptableTokens();
274            Arrays.sort(acceptableTokens);
275            for (String token : checkTokens) {
276                try {
277                    final int tokenId = TokenTypes.getTokenId(token);
278                    if (Arrays.binarySearch(acceptableTokens, tokenId) >= 0) {
279                        registerCheck(token, aCheck);
280                    }
281                    // TODO: else log warning
282                }
283                catch (final IllegalArgumentException ex) {
284                    throw new CheckstyleException("illegal token \""
285                        + token + "\" in check " + aCheck, ex);
286                }
287            }
288        }
289        else {
290            tokens = aCheck.getDefaultTokens();
291        }
292        for (int element : tokens) {
293            registerCheck(element, aCheck);
294        }
295        mAllChecks.add(aCheck);
296    }
297
298    /**
299     * Register a check for a specified token id.
300     * @param aTokenID the id of the token
301     * @param aCheck the check to register
302     */
303    private void registerCheck(int aTokenID, Check aCheck)
304    {
305        registerCheck(TokenTypes.getTokenName(aTokenID), aCheck);
306    }
307
308    /**
309     * Register a check for a specified token name
310     * @param aToken the name of the token
311     * @param aCheck the check to register
312     */
313    private void registerCheck(String aToken, Check aCheck)
314    {
315        mTokenToChecks.put(aToken, aCheck);
316    }
317
318    /**
319     * Initiates the walk of an AST.
320     * @param aAST the root AST
321     * @param aContents the contents of the file the AST was generated from
322     */
323    private void walk(DetailAST aAST, FileContents aContents)
324    {
325        getMessageCollector().reset();
326        notifyBegin(aAST, aContents);
327
328        // empty files are not flagged by javac, will yield aAST == null
329        if (aAST != null) {
330            if (useRecursiveAlgorithm()) {
331                processRec(aAST);
332            }
333            else {
334                processIter(aAST);
335            }
336        }
337
338        notifyEnd(aAST);
339    }
340
341
342    /**
343     * Notify interested checks that about to begin walking a tree.
344     * @param aRootAST the root of the tree
345     * @param aContents the contents of the file the AST was generated from
346     */
347    private void notifyBegin(DetailAST aRootAST, FileContents aContents)
348    {
349        for (Check ch : mAllChecks) {
350            ch.setFileContents(aContents);
351            ch.beginTree(aRootAST);
352        }
353    }
354
355    /**
356     * Notify checks that finished walking a tree.
357     * @param aRootAST the root of the tree
358     */
359    private void notifyEnd(DetailAST aRootAST)
360    {
361        for (Check ch : mAllChecks) {
362            ch.finishTree(aRootAST);
363        }
364    }
365
366    /**
367     * Recursively processes a node calling interested checks at each node.
368     * Uses recursive algorithm.
369     * @param aAST the node to start from
370     */
371    private void processRec(DetailAST aAST)
372    {
373        if (aAST == null) {
374            return;
375        }
376
377        notifyVisit(aAST);
378
379        final DetailAST child = aAST.getFirstChild();
380        if (child != null) {
381            processRec(child);
382        }
383
384        notifyLeave(aAST);
385
386        final DetailAST sibling = aAST.getNextSibling();
387        if (sibling != null) {
388            processRec(sibling);
389        }
390    }
391
392    /**
393     * Notify interested checks that visiting a node.
394     * @param aAST the node to notify for
395     */
396    private void notifyVisit(DetailAST aAST)
397    {
398        final Collection<Check> visitors =
399            mTokenToChecks.get(TokenTypes.getTokenName(aAST.getType()));
400        for (Check c : visitors) {
401            c.visitToken(aAST);
402        }
403    }
404
405    /**
406     * Notify interested checks that leaving a node.
407     *
408     * @param aAST
409     *                the node to notify for
410     */
411    private void notifyLeave(DetailAST aAST)
412    {
413        final Collection<Check> visitors =
414            mTokenToChecks.get(TokenTypes.getTokenName(aAST.getType()));
415        for (Check ch : visitors) {
416            ch.leaveToken(aAST);
417        }
418    }
419
420    /**
421     * Static helper method to parses a Java source file.
422     *
423     * @param aContents
424     *                contains the contents of the file
425     * @throws TokenStreamException
426     *                 if lexing failed
427     * @throws RecognitionException
428     *                 if parsing failed
429     * @return the root of the AST
430     */
431    public static DetailAST parse(FileContents aContents)
432        throws RecognitionException, TokenStreamException
433    {
434        final String fullText = aContents.getText().getFullText().toString();
435        final Reader sr = new StringReader(fullText);
436        final GeneratedJavaLexer lexer = new GeneratedJavaLexer(sr);
437        lexer.setFilename(aContents.getFilename());
438        lexer.setCommentListener(aContents);
439        lexer.setTreatAssertAsKeyword(true);
440        lexer.setTreatEnumAsKeyword(true);
441
442        final GeneratedJavaRecognizer parser =
443            new GeneratedJavaRecognizer(lexer);
444        parser.setFilename(aContents.getFilename());
445        parser.setASTNodeClass(DetailAST.class.getName());
446        parser.compilationUnit();
447
448        return (DetailAST) parser.getAST();
449    }
450
451    @Override
452    public void destroy()
453    {
454        for (Check c : mAllChecks) {
455            c.destroy();
456        }
457        mCache.destroy();
458        super.destroy();
459    }
460
461    /**
462     * @return true if we should use recursive algorithm
463     *         for tree processing, false for iterative one.
464     */
465    private boolean useRecursiveAlgorithm()
466    {
467        return mRecursive;
468    }
469
470    /**
471     * Processes a node calling interested checks at each node.
472     * Uses iterative algorithm.
473     * @param aRoot the root of tree for process
474     */
475    private void processIter(DetailAST aRoot)
476    {
477        DetailAST curNode = aRoot;
478        while (curNode != null) {
479            notifyVisit(curNode);
480            DetailAST toVisit = curNode.getFirstChild();
481            while ((curNode != null) && (toVisit == null)) {
482                notifyLeave(curNode);
483                toVisit = curNode.getNextSibling();
484                if (toVisit == null) {
485                    curNode = curNode.getParent();
486                }
487            }
488            curNode = toVisit;
489        }
490    }
491}