001/////////////////////////////////////////////////////////////////////////////////////////////// 002// checkstyle: Checks Java source code and other text files for adherence to a set of rules. 003// Copyright (C) 2001-2024 the original author or authors. 004// 005// This library is free software; you can redistribute it and/or 006// modify it under the terms of the GNU Lesser General Public 007// License as published by the Free Software Foundation; either 008// version 2.1 of the License, or (at your option) any later version. 009// 010// This library is distributed in the hope that it will be useful, 011// but WITHOUT ANY WARRANTY; without even the implied warranty of 012// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 013// Lesser General Public License for more details. 014// 015// You should have received a copy of the GNU Lesser General Public 016// License along with this library; if not, write to the Free Software 017// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 018/////////////////////////////////////////////////////////////////////////////////////////////// 019 020package com.puppycrawl.tools.checkstyle; 021 022import java.io.File; 023import java.util.Arrays; 024import java.util.Collection; 025import java.util.Comparator; 026import java.util.HashMap; 027import java.util.HashSet; 028import java.util.Locale; 029import java.util.Map; 030import java.util.Set; 031import java.util.SortedSet; 032import java.util.TreeSet; 033import java.util.stream.Collectors; 034import java.util.stream.Stream; 035 036import com.puppycrawl.tools.checkstyle.api.AbstractCheck; 037import com.puppycrawl.tools.checkstyle.api.AbstractFileSetCheck; 038import com.puppycrawl.tools.checkstyle.api.CheckstyleException; 039import com.puppycrawl.tools.checkstyle.api.Configuration; 040import com.puppycrawl.tools.checkstyle.api.Context; 041import com.puppycrawl.tools.checkstyle.api.DetailAST; 042import com.puppycrawl.tools.checkstyle.api.ExternalResourceHolder; 043import com.puppycrawl.tools.checkstyle.api.FileContents; 044import com.puppycrawl.tools.checkstyle.api.FileText; 045import com.puppycrawl.tools.checkstyle.api.SeverityLevel; 046import com.puppycrawl.tools.checkstyle.api.Violation; 047import com.puppycrawl.tools.checkstyle.utils.TokenUtil; 048 049/** 050 * Responsible for walking an abstract syntax tree and notifying interested 051 * checks at each node. 052 * 053 */ 054@FileStatefulCheck 055public final class TreeWalker extends AbstractFileSetCheck implements ExternalResourceHolder { 056 057 /** Message to use when an exception occurs and should be printed as a violation. */ 058 public static final String PARSE_EXCEPTION_MSG = "parse.exception"; 059 060 /** Maps from token name to ordinary checks. */ 061 private final Map<Integer, Set<AbstractCheck>> tokenToOrdinaryChecks = 062 new HashMap<>(); 063 064 /** Maps from token name to comment checks. */ 065 private final Map<Integer, Set<AbstractCheck>> tokenToCommentChecks = 066 new HashMap<>(); 067 068 /** Registered ordinary checks, that don't use comment nodes. */ 069 private final Set<AbstractCheck> ordinaryChecks = createNewCheckSortedSet(); 070 071 /** Registered comment checks. */ 072 private final Set<AbstractCheck> commentChecks = createNewCheckSortedSet(); 073 074 /** The ast filters. */ 075 private final Set<TreeWalkerFilter> filters = new HashSet<>(); 076 077 /** The sorted set of violations. */ 078 private final SortedSet<Violation> violations = new TreeSet<>(); 079 080 /** Context of child components. */ 081 private Context childContext; 082 083 /** A factory for creating submodules (i.e. the Checks) */ 084 private ModuleFactory moduleFactory; 085 086 /** Control whether to skip files with Java parsing exceptions. */ 087 private boolean skipFileOnJavaParseException; 088 089 /** Specify severity Level to log Java parsing exceptions when they are skipped. */ 090 private SeverityLevel javaParseExceptionSeverity = SeverityLevel.ERROR; 091 092 /** 093 * Creates a new {@code TreeWalker} instance. 094 */ 095 public TreeWalker() { 096 setFileExtensions("java"); 097 } 098 099 /** 100 * Sets the module factory for creating child modules (Checks). 101 * 102 * @param moduleFactory the factory 103 */ 104 public void setModuleFactory(ModuleFactory moduleFactory) { 105 this.moduleFactory = moduleFactory; 106 } 107 108 /** 109 * Setter to control whether to skip files with Java parsing exceptions. 110 * 111 * @param skipFileOnJavaParseException whether to skip files with Java parsing errors. 112 * @since 10.18.0 113 */ 114 public void setSkipFileOnJavaParseException(boolean skipFileOnJavaParseException) { 115 this.skipFileOnJavaParseException = skipFileOnJavaParseException; 116 } 117 118 /** 119 * Setter to specify the severity level 120 * to log Java parsing exceptions when they are skipped. 121 * 122 * @param javaParseExceptionSeverity severity level to log parsing exceptions 123 * when they are skipped. 124 * @since 10.18.0 125 */ 126 public void setJavaParseExceptionSeverity(SeverityLevel javaParseExceptionSeverity) { 127 this.javaParseExceptionSeverity = javaParseExceptionSeverity; 128 } 129 130 @Override 131 public void finishLocalSetup() { 132 final DefaultContext checkContext = new DefaultContext(); 133 checkContext.add("severity", getSeverity()); 134 checkContext.add("tabWidth", String.valueOf(getTabWidth())); 135 childContext = checkContext; 136 } 137 138 /** 139 * {@inheritDoc} Creates child module. 140 * 141 * @noinspection ChainOfInstanceofChecks 142 * @noinspectionreason ChainOfInstanceofChecks - we treat checks and filters differently 143 */ 144 @Override 145 public void setupChild(Configuration childConf) 146 throws CheckstyleException { 147 final String name = childConf.getName(); 148 final Object module; 149 150 try { 151 module = moduleFactory.createModule(name); 152 if (module instanceof AbstractAutomaticBean) { 153 final AbstractAutomaticBean bean = (AbstractAutomaticBean) module; 154 bean.contextualize(childContext); 155 bean.configure(childConf); 156 } 157 } 158 catch (final CheckstyleException ex) { 159 throw new CheckstyleException("cannot initialize module " + name 160 + " - " + ex.getMessage(), ex); 161 } 162 if (module instanceof AbstractCheck) { 163 final AbstractCheck check = (AbstractCheck) module; 164 check.init(); 165 registerCheck(check); 166 } 167 else if (module instanceof TreeWalkerFilter) { 168 final TreeWalkerFilter filter = (TreeWalkerFilter) module; 169 filters.add(filter); 170 } 171 else { 172 throw new CheckstyleException( 173 "TreeWalker is not allowed as a parent of " + name 174 + " Please review 'Parent Module' section for this Check in web" 175 + " documentation if Check is standard."); 176 } 177 } 178 179 /** 180 * {@inheritDoc} Processes the file. 181 * 182 * @noinspection ProhibitedExceptionThrown 183 * @noinspectionreason ProhibitedExceptionThrown - there is no other way to obey 184 * skipFileOnJavaParseException field 185 */ 186 @Override 187 protected void processFiltered(File file, FileText fileText) throws CheckstyleException { 188 // check if already checked and passed the file 189 if (!ordinaryChecks.isEmpty() || !commentChecks.isEmpty()) { 190 final FileContents contents = getFileContents(); 191 DetailAST rootAST = null; 192 // whether skip the procedure after parsing Java files. 193 boolean skip = false; 194 try { 195 rootAST = JavaParser.parse(contents); 196 } 197 // -@cs[IllegalCatch] There is no other way to obey skipFileOnJavaParseException field 198 catch (Exception ex) { 199 if (!skipFileOnJavaParseException) { 200 throw ex; 201 } 202 skip = true; 203 violations.add(new Violation(1, Definitions.CHECKSTYLE_BUNDLE, PARSE_EXCEPTION_MSG, 204 new Object[] {ex.getMessage()}, javaParseExceptionSeverity, null, 205 getClass(), null)); 206 addViolations(violations); 207 } 208 209 if (!skip) { 210 if (!ordinaryChecks.isEmpty()) { 211 walk(rootAST, contents, AstState.ORDINARY); 212 } 213 if (!commentChecks.isEmpty()) { 214 final DetailAST astWithComments = JavaParser.appendHiddenCommentNodes(rootAST); 215 walk(astWithComments, contents, AstState.WITH_COMMENTS); 216 } 217 if (filters.isEmpty()) { 218 addViolations(violations); 219 } 220 else { 221 final SortedSet<Violation> filteredViolations = 222 getFilteredViolations(file.getAbsolutePath(), contents, rootAST); 223 addViolations(filteredViolations); 224 } 225 } 226 violations.clear(); 227 } 228 } 229 230 /** 231 * Returns filtered set of {@link Violation}. 232 * 233 * @param fileName path to the file 234 * @param fileContents the contents of the file 235 * @param rootAST root AST element {@link DetailAST} of the file 236 * @return filtered set of violations 237 */ 238 private SortedSet<Violation> getFilteredViolations( 239 String fileName, FileContents fileContents, DetailAST rootAST) { 240 final SortedSet<Violation> result = new TreeSet<>(violations); 241 for (Violation element : violations) { 242 final TreeWalkerAuditEvent event = 243 new TreeWalkerAuditEvent(fileContents, fileName, element, rootAST); 244 for (TreeWalkerFilter filter : filters) { 245 if (!filter.accept(event)) { 246 result.remove(element); 247 break; 248 } 249 } 250 } 251 return result; 252 } 253 254 /** 255 * Register a check for a given configuration. 256 * 257 * @param check the check to register 258 * @throws CheckstyleException if an error occurs 259 */ 260 private void registerCheck(AbstractCheck check) throws CheckstyleException { 261 final int[] tokens; 262 final Set<String> checkTokens = check.getTokenNames(); 263 if (checkTokens.isEmpty()) { 264 tokens = check.getDefaultTokens(); 265 } 266 else { 267 tokens = check.getRequiredTokens(); 268 269 // register configured tokens 270 final int[] acceptableTokens = check.getAcceptableTokens(); 271 Arrays.sort(acceptableTokens); 272 for (String token : checkTokens) { 273 final int tokenId = TokenUtil.getTokenId(token); 274 if (Arrays.binarySearch(acceptableTokens, tokenId) >= 0) { 275 registerCheck(tokenId, check); 276 } 277 else { 278 final String message = String.format(Locale.ROOT, "Token \"%s\" was " 279 + "not found in Acceptable tokens list in check %s", 280 token, check.getClass().getName()); 281 throw new CheckstyleException(message); 282 } 283 } 284 } 285 for (int element : tokens) { 286 registerCheck(element, check); 287 } 288 if (check.isCommentNodesRequired()) { 289 commentChecks.add(check); 290 } 291 else { 292 ordinaryChecks.add(check); 293 } 294 } 295 296 /** 297 * Register a check for a specified token id. 298 * 299 * @param tokenId the id of the token 300 * @param check the check to register 301 * @throws CheckstyleException if Check is misconfigured 302 */ 303 private void registerCheck(int tokenId, AbstractCheck check) throws CheckstyleException { 304 if (check.isCommentNodesRequired()) { 305 tokenToCommentChecks.computeIfAbsent(tokenId, empty -> createNewCheckSortedSet()) 306 .add(check); 307 } 308 else if (TokenUtil.isCommentType(tokenId)) { 309 final String message = String.format(Locale.ROOT, "Check '%s' waits for comment type " 310 + "token ('%s') and should override 'isCommentNodesRequired()' " 311 + "method to return 'true'", check.getClass().getName(), 312 TokenUtil.getTokenName(tokenId)); 313 throw new CheckstyleException(message); 314 } 315 else { 316 tokenToOrdinaryChecks.computeIfAbsent(tokenId, empty -> createNewCheckSortedSet()) 317 .add(check); 318 } 319 } 320 321 /** 322 * Initiates the walk of an AST. 323 * 324 * @param ast the root AST 325 * @param contents the contents of the file the AST was generated from. 326 * @param astState state of AST. 327 */ 328 private void walk(DetailAST ast, FileContents contents, 329 AstState astState) { 330 notifyBegin(ast, contents, astState); 331 processIter(ast, astState); 332 notifyEnd(ast, astState); 333 } 334 335 /** 336 * Notify checks that we are about to begin walking a tree. 337 * 338 * @param rootAST the root of the tree. 339 * @param contents the contents of the file the AST was generated from. 340 * @param astState state of AST. 341 */ 342 private void notifyBegin(DetailAST rootAST, FileContents contents, 343 AstState astState) { 344 final Set<AbstractCheck> checks; 345 346 if (astState == AstState.WITH_COMMENTS) { 347 checks = commentChecks; 348 } 349 else { 350 checks = ordinaryChecks; 351 } 352 353 for (AbstractCheck check : checks) { 354 check.setFileContents(contents); 355 check.clearViolations(); 356 check.beginTree(rootAST); 357 } 358 } 359 360 /** 361 * Notify checks that we have finished walking a tree. 362 * 363 * @param rootAST the root of the tree. 364 * @param astState state of AST. 365 */ 366 private void notifyEnd(DetailAST rootAST, AstState astState) { 367 final Set<AbstractCheck> checks; 368 369 if (astState == AstState.WITH_COMMENTS) { 370 checks = commentChecks; 371 } 372 else { 373 checks = ordinaryChecks; 374 } 375 376 for (AbstractCheck check : checks) { 377 check.finishTree(rootAST); 378 violations.addAll(check.getViolations()); 379 } 380 } 381 382 /** 383 * Notify checks that visiting a node. 384 * 385 * @param ast the node to notify for. 386 * @param astState state of AST. 387 */ 388 private void notifyVisit(DetailAST ast, AstState astState) { 389 final Collection<AbstractCheck> visitors = getListOfChecks(ast, astState); 390 391 if (visitors != null) { 392 for (AbstractCheck check : visitors) { 393 check.visitToken(ast); 394 } 395 } 396 } 397 398 /** 399 * Notify checks that leaving a node. 400 * 401 * @param ast 402 * the node to notify for 403 * @param astState state of AST. 404 */ 405 private void notifyLeave(DetailAST ast, AstState astState) { 406 final Collection<AbstractCheck> visitors = getListOfChecks(ast, astState); 407 408 if (visitors != null) { 409 for (AbstractCheck check : visitors) { 410 check.leaveToken(ast); 411 } 412 } 413 } 414 415 /** 416 * Method returns list of checks. 417 * 418 * @param ast 419 * the node to notify for 420 * @param astState 421 * state of AST. 422 * @return list of visitors 423 */ 424 private Collection<AbstractCheck> getListOfChecks(DetailAST ast, AstState astState) { 425 final Collection<AbstractCheck> visitors; 426 final int tokenId = ast.getType(); 427 428 if (astState == AstState.WITH_COMMENTS) { 429 visitors = tokenToCommentChecks.get(tokenId); 430 } 431 else { 432 visitors = tokenToOrdinaryChecks.get(tokenId); 433 } 434 return visitors; 435 } 436 437 @Override 438 public void destroy() { 439 ordinaryChecks.forEach(AbstractCheck::destroy); 440 commentChecks.forEach(AbstractCheck::destroy); 441 super.destroy(); 442 } 443 444 @Override 445 public Set<String> getExternalResourceLocations() { 446 return Stream.concat(filters.stream(), 447 Stream.concat(ordinaryChecks.stream(), commentChecks.stream())) 448 .filter(ExternalResourceHolder.class::isInstance) 449 .flatMap(resource -> { 450 return ((ExternalResourceHolder) resource) 451 .getExternalResourceLocations().stream(); 452 }) 453 .collect(Collectors.toUnmodifiableSet()); 454 } 455 456 /** 457 * Processes a node calling interested checks at each node. 458 * Uses iterative algorithm. 459 * 460 * @param root the root of tree for process 461 * @param astState state of AST. 462 */ 463 private void processIter(DetailAST root, AstState astState) { 464 DetailAST curNode = root; 465 while (curNode != null) { 466 notifyVisit(curNode, astState); 467 DetailAST toVisit = curNode.getFirstChild(); 468 while (curNode != null && toVisit == null) { 469 notifyLeave(curNode, astState); 470 toVisit = curNode.getNextSibling(); 471 curNode = curNode.getParent(); 472 } 473 curNode = toVisit; 474 } 475 } 476 477 /** 478 * Creates a new {@link SortedSet} with a deterministic order based on the 479 * Check's name before the default ordering. 480 * 481 * @return The new {@link SortedSet}. 482 */ 483 private static SortedSet<AbstractCheck> createNewCheckSortedSet() { 484 return new TreeSet<>( 485 Comparator.<AbstractCheck, String>comparing(check -> check.getClass().getName()) 486 .thenComparing(AbstractCheck::getId, 487 Comparator.nullsLast(Comparator.naturalOrder())) 488 .thenComparingInt(AbstractCheck::hashCode)); 489 } 490 491 /** 492 * State of AST. 493 * Indicates whether tree contains certain nodes. 494 */ 495 private enum AstState { 496 497 /** 498 * Ordinary tree. 499 */ 500 ORDINARY, 501 502 /** 503 * AST contains comment nodes. 504 */ 505 WITH_COMMENTS, 506 507 } 508 509}