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.Violation; 046import com.puppycrawl.tools.checkstyle.utils.TokenUtil; 047 048/** 049 * Responsible for walking an abstract syntax tree and notifying interested 050 * checks at each node. 051 * 052 */ 053@FileStatefulCheck 054public final class TreeWalker extends AbstractFileSetCheck implements ExternalResourceHolder { 055 056 /** Maps from token name to ordinary checks. */ 057 private final Map<Integer, Set<AbstractCheck>> tokenToOrdinaryChecks = 058 new HashMap<>(); 059 060 /** Maps from token name to comment checks. */ 061 private final Map<Integer, Set<AbstractCheck>> tokenToCommentChecks = 062 new HashMap<>(); 063 064 /** Registered ordinary checks, that don't use comment nodes. */ 065 private final Set<AbstractCheck> ordinaryChecks = createNewCheckSortedSet(); 066 067 /** Registered comment checks. */ 068 private final Set<AbstractCheck> commentChecks = createNewCheckSortedSet(); 069 070 /** The ast filters. */ 071 private final Set<TreeWalkerFilter> filters = new HashSet<>(); 072 073 /** The sorted set of violations. */ 074 private final SortedSet<Violation> violations = new TreeSet<>(); 075 076 /** Context of child components. */ 077 private Context childContext; 078 079 /** A factory for creating submodules (i.e. the Checks) */ 080 private ModuleFactory moduleFactory; 081 082 /** 083 * Creates a new {@code TreeWalker} instance. 084 */ 085 public TreeWalker() { 086 setFileExtensions("java"); 087 } 088 089 /** 090 * Sets the module factory for creating child modules (Checks). 091 * 092 * @param moduleFactory the factory 093 */ 094 public void setModuleFactory(ModuleFactory moduleFactory) { 095 this.moduleFactory = moduleFactory; 096 } 097 098 @Override 099 public void finishLocalSetup() { 100 final DefaultContext checkContext = new DefaultContext(); 101 checkContext.add("severity", getSeverity()); 102 checkContext.add("tabWidth", String.valueOf(getTabWidth())); 103 childContext = checkContext; 104 } 105 106 /** 107 * {@inheritDoc} Creates child module. 108 * 109 * @noinspection ChainOfInstanceofChecks 110 * @noinspectionreason ChainOfInstanceofChecks - we treat checks and filters differently 111 */ 112 @Override 113 public void setupChild(Configuration childConf) 114 throws CheckstyleException { 115 final String name = childConf.getName(); 116 final Object module; 117 118 try { 119 module = moduleFactory.createModule(name); 120 if (module instanceof AbstractAutomaticBean) { 121 final AbstractAutomaticBean bean = (AbstractAutomaticBean) module; 122 bean.contextualize(childContext); 123 bean.configure(childConf); 124 } 125 } 126 catch (final CheckstyleException ex) { 127 throw new CheckstyleException("cannot initialize module " + name 128 + " - " + ex.getMessage(), ex); 129 } 130 if (module instanceof AbstractCheck) { 131 final AbstractCheck check = (AbstractCheck) module; 132 check.init(); 133 registerCheck(check); 134 } 135 else if (module instanceof TreeWalkerFilter) { 136 final TreeWalkerFilter filter = (TreeWalkerFilter) module; 137 filters.add(filter); 138 } 139 else { 140 throw new CheckstyleException( 141 "TreeWalker is not allowed as a parent of " + name 142 + " Please review 'Parent Module' section for this Check in web" 143 + " documentation if Check is standard."); 144 } 145 } 146 147 @Override 148 protected void processFiltered(File file, FileText fileText) throws CheckstyleException { 149 // check if already checked and passed the file 150 if (!ordinaryChecks.isEmpty() || !commentChecks.isEmpty()) { 151 final FileContents contents = getFileContents(); 152 final DetailAST rootAST = JavaParser.parse(contents); 153 if (!ordinaryChecks.isEmpty()) { 154 walk(rootAST, contents, AstState.ORDINARY); 155 } 156 if (!commentChecks.isEmpty()) { 157 final DetailAST astWithComments = JavaParser.appendHiddenCommentNodes(rootAST); 158 walk(astWithComments, contents, AstState.WITH_COMMENTS); 159 } 160 if (filters.isEmpty()) { 161 addViolations(violations); 162 } 163 else { 164 final SortedSet<Violation> filteredViolations = 165 getFilteredViolations(file.getAbsolutePath(), contents, rootAST); 166 addViolations(filteredViolations); 167 } 168 violations.clear(); 169 } 170 } 171 172 /** 173 * Returns filtered set of {@link Violation}. 174 * 175 * @param fileName path to the file 176 * @param fileContents the contents of the file 177 * @param rootAST root AST element {@link DetailAST} of the file 178 * @return filtered set of violations 179 */ 180 private SortedSet<Violation> getFilteredViolations( 181 String fileName, FileContents fileContents, DetailAST rootAST) { 182 final SortedSet<Violation> result = new TreeSet<>(violations); 183 for (Violation element : violations) { 184 final TreeWalkerAuditEvent event = 185 new TreeWalkerAuditEvent(fileContents, fileName, element, rootAST); 186 for (TreeWalkerFilter filter : filters) { 187 if (!filter.accept(event)) { 188 result.remove(element); 189 break; 190 } 191 } 192 } 193 return result; 194 } 195 196 /** 197 * Register a check for a given configuration. 198 * 199 * @param check the check to register 200 * @throws CheckstyleException if an error occurs 201 */ 202 private void registerCheck(AbstractCheck check) throws CheckstyleException { 203 final int[] tokens; 204 final Set<String> checkTokens = check.getTokenNames(); 205 if (checkTokens.isEmpty()) { 206 tokens = check.getDefaultTokens(); 207 } 208 else { 209 tokens = check.getRequiredTokens(); 210 211 // register configured tokens 212 final int[] acceptableTokens = check.getAcceptableTokens(); 213 Arrays.sort(acceptableTokens); 214 for (String token : checkTokens) { 215 final int tokenId = TokenUtil.getTokenId(token); 216 if (Arrays.binarySearch(acceptableTokens, tokenId) >= 0) { 217 registerCheck(tokenId, check); 218 } 219 else { 220 final String message = String.format(Locale.ROOT, "Token \"%s\" was " 221 + "not found in Acceptable tokens list in check %s", 222 token, check.getClass().getName()); 223 throw new CheckstyleException(message); 224 } 225 } 226 } 227 for (int element : tokens) { 228 registerCheck(element, check); 229 } 230 if (check.isCommentNodesRequired()) { 231 commentChecks.add(check); 232 } 233 else { 234 ordinaryChecks.add(check); 235 } 236 } 237 238 /** 239 * Register a check for a specified token id. 240 * 241 * @param tokenId the id of the token 242 * @param check the check to register 243 * @throws CheckstyleException if Check is misconfigured 244 */ 245 private void registerCheck(int tokenId, AbstractCheck check) throws CheckstyleException { 246 if (check.isCommentNodesRequired()) { 247 tokenToCommentChecks.computeIfAbsent(tokenId, empty -> createNewCheckSortedSet()) 248 .add(check); 249 } 250 else if (TokenUtil.isCommentType(tokenId)) { 251 final String message = String.format(Locale.ROOT, "Check '%s' waits for comment type " 252 + "token ('%s') and should override 'isCommentNodesRequired()' " 253 + "method to return 'true'", check.getClass().getName(), 254 TokenUtil.getTokenName(tokenId)); 255 throw new CheckstyleException(message); 256 } 257 else { 258 tokenToOrdinaryChecks.computeIfAbsent(tokenId, empty -> createNewCheckSortedSet()) 259 .add(check); 260 } 261 } 262 263 /** 264 * Initiates the walk of an AST. 265 * 266 * @param ast the root AST 267 * @param contents the contents of the file the AST was generated from. 268 * @param astState state of AST. 269 */ 270 private void walk(DetailAST ast, FileContents contents, 271 AstState astState) { 272 notifyBegin(ast, contents, astState); 273 processIter(ast, astState); 274 notifyEnd(ast, astState); 275 } 276 277 /** 278 * Notify checks that we are about to begin walking a tree. 279 * 280 * @param rootAST the root of the tree. 281 * @param contents the contents of the file the AST was generated from. 282 * @param astState state of AST. 283 */ 284 private void notifyBegin(DetailAST rootAST, FileContents contents, 285 AstState astState) { 286 final Set<AbstractCheck> checks; 287 288 if (astState == AstState.WITH_COMMENTS) { 289 checks = commentChecks; 290 } 291 else { 292 checks = ordinaryChecks; 293 } 294 295 for (AbstractCheck check : checks) { 296 check.setFileContents(contents); 297 check.clearViolations(); 298 check.beginTree(rootAST); 299 } 300 } 301 302 /** 303 * Notify checks that we have finished walking a tree. 304 * 305 * @param rootAST the root of the tree. 306 * @param astState state of AST. 307 */ 308 private void notifyEnd(DetailAST rootAST, AstState astState) { 309 final Set<AbstractCheck> checks; 310 311 if (astState == AstState.WITH_COMMENTS) { 312 checks = commentChecks; 313 } 314 else { 315 checks = ordinaryChecks; 316 } 317 318 for (AbstractCheck check : checks) { 319 check.finishTree(rootAST); 320 violations.addAll(check.getViolations()); 321 } 322 } 323 324 /** 325 * Notify checks that visiting a node. 326 * 327 * @param ast the node to notify for. 328 * @param astState state of AST. 329 */ 330 private void notifyVisit(DetailAST ast, AstState astState) { 331 final Collection<AbstractCheck> visitors = getListOfChecks(ast, astState); 332 333 if (visitors != null) { 334 for (AbstractCheck check : visitors) { 335 check.visitToken(ast); 336 } 337 } 338 } 339 340 /** 341 * Notify checks that leaving a node. 342 * 343 * @param ast 344 * the node to notify for 345 * @param astState state of AST. 346 */ 347 private void notifyLeave(DetailAST ast, AstState astState) { 348 final Collection<AbstractCheck> visitors = getListOfChecks(ast, astState); 349 350 if (visitors != null) { 351 for (AbstractCheck check : visitors) { 352 check.leaveToken(ast); 353 } 354 } 355 } 356 357 /** 358 * Method returns list of checks. 359 * 360 * @param ast 361 * the node to notify for 362 * @param astState 363 * state of AST. 364 * @return list of visitors 365 */ 366 private Collection<AbstractCheck> getListOfChecks(DetailAST ast, AstState astState) { 367 final Collection<AbstractCheck> visitors; 368 final int tokenId = ast.getType(); 369 370 if (astState == AstState.WITH_COMMENTS) { 371 visitors = tokenToCommentChecks.get(tokenId); 372 } 373 else { 374 visitors = tokenToOrdinaryChecks.get(tokenId); 375 } 376 return visitors; 377 } 378 379 @Override 380 public void destroy() { 381 ordinaryChecks.forEach(AbstractCheck::destroy); 382 commentChecks.forEach(AbstractCheck::destroy); 383 super.destroy(); 384 } 385 386 @Override 387 public Set<String> getExternalResourceLocations() { 388 return Stream.concat(filters.stream(), 389 Stream.concat(ordinaryChecks.stream(), commentChecks.stream())) 390 .filter(ExternalResourceHolder.class::isInstance) 391 .flatMap(resource -> { 392 return ((ExternalResourceHolder) resource) 393 .getExternalResourceLocations().stream(); 394 }) 395 .collect(Collectors.toUnmodifiableSet()); 396 } 397 398 /** 399 * Processes a node calling interested checks at each node. 400 * Uses iterative algorithm. 401 * 402 * @param root the root of tree for process 403 * @param astState state of AST. 404 */ 405 private void processIter(DetailAST root, AstState astState) { 406 DetailAST curNode = root; 407 while (curNode != null) { 408 notifyVisit(curNode, astState); 409 DetailAST toVisit = curNode.getFirstChild(); 410 while (curNode != null && toVisit == null) { 411 notifyLeave(curNode, astState); 412 toVisit = curNode.getNextSibling(); 413 curNode = curNode.getParent(); 414 } 415 curNode = toVisit; 416 } 417 } 418 419 /** 420 * Creates a new {@link SortedSet} with a deterministic order based on the 421 * Check's name before the default ordering. 422 * 423 * @return The new {@link SortedSet}. 424 */ 425 private static SortedSet<AbstractCheck> createNewCheckSortedSet() { 426 return new TreeSet<>( 427 Comparator.<AbstractCheck, String>comparing(check -> check.getClass().getName()) 428 .thenComparing(AbstractCheck::getId, 429 Comparator.nullsLast(Comparator.naturalOrder())) 430 .thenComparingInt(AbstractCheck::hashCode)); 431 } 432 433 /** 434 * State of AST. 435 * Indicates whether tree contains certain nodes. 436 */ 437 private enum AstState { 438 439 /** 440 * Ordinary tree. 441 */ 442 ORDINARY, 443 444 /** 445 * AST contains comment nodes. 446 */ 447 WITH_COMMENTS, 448 449 } 450 451}