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}