001/////////////////////////////////////////////////////////////////////////////////////////////// 002// checkstyle: Checks Java source code and other text files for adherence to a set of rules. 003// Copyright (C) 2001-2025 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.xpath; 021 022import java.util.ArrayList; 023import java.util.List; 024 025import javax.annotation.Nullable; 026 027import com.puppycrawl.tools.checkstyle.TreeWalkerAuditEvent; 028import com.puppycrawl.tools.checkstyle.api.DetailAST; 029import com.puppycrawl.tools.checkstyle.api.FileText; 030import com.puppycrawl.tools.checkstyle.utils.CommonUtil; 031import com.puppycrawl.tools.checkstyle.utils.TokenUtil; 032import com.puppycrawl.tools.checkstyle.utils.XpathUtil; 033 034/** 035 * Generates xpath queries. Xpath queries are generated based on received 036 * {@code DetailAst} element, line number, column number and token type. 037 * Token type parameter is optional. 038 * 039 * <p> 040 * Example class 041 * </p> 042 * <pre> 043 * public class Main { 044 * 045 * public String sayHello(String name) { 046 * return "Hello, " + name; 047 * } 048 * } 049 * </pre> 050 * 051 * <p> 052 * Following expression returns list of queries. Each query is the string representing full 053 * path to the node inside Xpath tree, whose line number is 3 and column number is 4. 054 * </p> 055 * <pre> 056 * new XpathQueryGenerator(rootAst, 3, 4).generate(); 057 * </pre> 058 * 059 * <p> 060 * Result list 061 * </p> 062 * <ul> 063 * <li> 064 * /COMPILATION_UNIT/CLASS_DEF[./IDENT[@text='Main']]/OBJBLOCK/METHOD_DEF[./IDENT[@text='sayHello']] 065 * </li> 066 * <li> 067 * /COMPILATION_UNIT/CLASS_DEF[./IDENT[@text='Main']]/OBJBLOCK/METHOD_DEF[./IDENT[@text='sayHello']] 068 * /MODIFIERS 069 * </li> 070 * <li> 071 * /COMPILATION_UNIT/CLASS_DEF[./IDENT[@text='Main']]/OBJBLOCK/METHOD_DEF[./IDENT[@text='sayHello']] 072 * /MODIFIERS/LITERAL_PUBLIC 073 * </li> 074 * </ul> 075 * 076 */ 077public class XpathQueryGenerator { 078 079 /** The root ast. */ 080 private final DetailAST rootAst; 081 /** The line number of the element for which the query should be generated. */ 082 private final int lineNumber; 083 /** The column number of the element for which the query should be generated. */ 084 private final int columnNumber; 085 /** The token type of the element for which the query should be generated. Optional. */ 086 private final int tokenType; 087 /** The {@code FileText} object, representing content of the file. */ 088 private final FileText fileText; 089 /** The distance between tab stop position. */ 090 private final int tabWidth; 091 092 /** 093 * Creates a new {@code XpathQueryGenerator} instance. 094 * 095 * @param event {@code TreeWalkerAuditEvent} object 096 * @param tabWidth distance between tab stop position 097 */ 098 public XpathQueryGenerator(TreeWalkerAuditEvent event, int tabWidth) { 099 this(event.getRootAst(), event.getLine(), event.getColumn(), event.getTokenType(), 100 event.getFileContents().getText(), tabWidth); 101 } 102 103 /** 104 * Creates a new {@code XpathQueryGenerator} instance. 105 * 106 * @param rootAst root ast 107 * @param lineNumber line number of the element for which the query should be generated 108 * @param columnNumber column number of the element for which the query should be generated 109 * @param fileText the {@code FileText} object 110 * @param tabWidth distance between tab stop position 111 */ 112 public XpathQueryGenerator(DetailAST rootAst, int lineNumber, int columnNumber, 113 FileText fileText, int tabWidth) { 114 this(rootAst, lineNumber, columnNumber, 0, fileText, tabWidth); 115 } 116 117 /** 118 * Creates a new {@code XpathQueryGenerator} instance. 119 * 120 * @param rootAst root ast 121 * @param lineNumber line number of the element for which the query should be generated 122 * @param columnNumber column number of the element for which the query should be generated 123 * @param tokenType token type of the element for which the query should be generated 124 * @param fileText the {@code FileText} object 125 * @param tabWidth distance between tab stop position 126 */ 127 public XpathQueryGenerator(DetailAST rootAst, int lineNumber, int columnNumber, int tokenType, 128 FileText fileText, int tabWidth) { 129 this.rootAst = rootAst; 130 this.lineNumber = lineNumber; 131 this.columnNumber = columnNumber; 132 this.tokenType = tokenType; 133 this.fileText = fileText; 134 this.tabWidth = tabWidth; 135 } 136 137 /** 138 * Returns list of xpath queries of nodes, matching line number, column number and token type. 139 * This approach uses DetailAST traversal. DetailAST means detail abstract syntax tree. 140 * 141 * @return list of xpath queries of nodes, matching line number, column number and token type 142 */ 143 public List<String> generate() { 144 return getMatchingAstElements() 145 .stream() 146 .map(XpathQueryGenerator::generateXpathQuery) 147 .toList(); 148 } 149 150 /** 151 * Returns child {@code DetailAst} element of the given root, which has text attribute. 152 * 153 * @param root {@code DetailAST} root ast 154 * @return child {@code DetailAst} element of the given root 155 */ 156 @Nullable 157 private static DetailAST findChildWithTextAttribute(DetailAST root) { 158 return TokenUtil.findFirstTokenByPredicate(root, 159 XpathUtil::supportsTextAttribute).orElse(null); 160 } 161 162 /** 163 * Returns child {@code DetailAst} element of the given root, which has text attribute. 164 * Performs search recursively inside node's subtree. 165 * 166 * @param root {@code DetailAST} root ast 167 * @return child {@code DetailAst} element of the given root 168 */ 169 @Nullable 170 private static DetailAST findChildWithTextAttributeRecursively(DetailAST root) { 171 DetailAST res = findChildWithTextAttribute(root); 172 for (DetailAST ast = root.getFirstChild(); ast != null && res == null; 173 ast = ast.getNextSibling()) { 174 res = findChildWithTextAttributeRecursively(ast); 175 } 176 return res; 177 } 178 179 /** 180 * Returns full xpath query for given ast element. 181 * 182 * @param ast {@code DetailAST} ast element 183 * @return full xpath query for given ast element 184 */ 185 public static String generateXpathQuery(DetailAST ast) { 186 final StringBuilder xpathQueryBuilder = new StringBuilder(getXpathQuery(null, ast)); 187 if (!isXpathQueryForNodeIsAccurateEnough(ast)) { 188 xpathQueryBuilder.append('['); 189 final DetailAST child = findChildWithTextAttributeRecursively(ast); 190 if (child == null) { 191 xpathQueryBuilder.append(findPositionAmongSiblings(ast)); 192 } 193 else { 194 xpathQueryBuilder.append('.').append(getXpathQuery(ast, child)); 195 } 196 xpathQueryBuilder.append(']'); 197 } 198 return xpathQueryBuilder.toString(); 199 } 200 201 /** 202 * Finds position of the ast element among siblings. 203 * 204 * @param ast {@code DetailAST} ast element 205 * @return position of the ast element 206 */ 207 private static int findPositionAmongSiblings(DetailAST ast) { 208 DetailAST cur = ast; 209 int pos = 0; 210 while (cur != null) { 211 if (cur.getType() == ast.getType()) { 212 pos++; 213 } 214 cur = cur.getPreviousSibling(); 215 } 216 return pos; 217 } 218 219 /** 220 * Checks if ast element has all requirements to have unique xpath query. 221 * 222 * @param ast {@code DetailAST} ast element 223 * @return true if ast element will have unique xpath query, false otherwise 224 */ 225 private static boolean isXpathQueryForNodeIsAccurateEnough(DetailAST ast) { 226 return !hasAtLeastOneSiblingWithSameTokenType(ast) 227 || XpathUtil.supportsTextAttribute(ast) 228 || findChildWithTextAttribute(ast) != null; 229 } 230 231 /** 232 * Returns list of nodes matching defined line number, column number and token type. 233 * 234 * @return list of nodes matching defined line number, column number and token type 235 */ 236 private List<DetailAST> getMatchingAstElements() { 237 final List<DetailAST> result = new ArrayList<>(); 238 DetailAST curNode = rootAst; 239 while (curNode != null) { 240 if (isMatchingByLineAndColumnAndTokenType(curNode)) { 241 result.add(curNode); 242 } 243 DetailAST toVisit = curNode.getFirstChild(); 244 while (curNode != null && toVisit == null) { 245 toVisit = curNode.getNextSibling(); 246 curNode = curNode.getParent(); 247 } 248 249 curNode = toVisit; 250 } 251 return result; 252 } 253 254 /** 255 * Returns relative xpath query for given ast element from root. 256 * 257 * @param root {@code DetailAST} root element 258 * @param ast {@code DetailAST} ast element 259 * @return relative xpath query for given ast element from root 260 */ 261 private static String getXpathQuery(DetailAST root, DetailAST ast) { 262 final StringBuilder resultBuilder = new StringBuilder(1024); 263 DetailAST cur = ast; 264 while (cur != root) { 265 final StringBuilder curNodeQueryBuilder = new StringBuilder(256); 266 curNodeQueryBuilder.append('/') 267 .append(TokenUtil.getTokenName(cur.getType())); 268 if (XpathUtil.supportsTextAttribute(cur)) { 269 curNodeQueryBuilder.append("[@text='") 270 .append(encode(XpathUtil.getTextAttributeValue(cur))) 271 .append("']"); 272 } 273 else { 274 final DetailAST child = findChildWithTextAttribute(cur); 275 if (child != null && child != ast) { 276 curNodeQueryBuilder.append("[.") 277 .append(getXpathQuery(cur, child)) 278 .append(']'); 279 } 280 } 281 282 resultBuilder.insert(0, curNodeQueryBuilder); 283 cur = cur.getParent(); 284 } 285 return resultBuilder.toString(); 286 } 287 288 /** 289 * Checks if the given ast element has unique {@code TokenTypes} among siblings. 290 * 291 * @param ast {@code DetailAST} ast element 292 * @return if the given ast element has unique {@code TokenTypes} among siblings 293 */ 294 private static boolean hasAtLeastOneSiblingWithSameTokenType(DetailAST ast) { 295 boolean result = false; 296 DetailAST prev = ast.getPreviousSibling(); 297 while (prev != null) { 298 if (prev.getType() == ast.getType()) { 299 result = true; 300 break; 301 } 302 prev = prev.getPreviousSibling(); 303 } 304 DetailAST next = ast.getNextSibling(); 305 while (next != null) { 306 if (next.getType() == ast.getType()) { 307 result = true; 308 break; 309 } 310 next = next.getNextSibling(); 311 } 312 return result; 313 } 314 315 /** 316 * Returns the column number with tabs expanded. 317 * 318 * @param ast {@code DetailAST} root ast 319 * @return the column number with tabs expanded 320 */ 321 private int expandedTabColumn(DetailAST ast) { 322 return 1 + CommonUtil.lengthExpandedTabs(fileText.get(lineNumber - 1), 323 ast.getColumnNo(), tabWidth); 324 } 325 326 /** 327 * Checks if the given {@code DetailAST} node is matching line number, column number and token 328 * type. 329 * 330 * @param ast {@code DetailAST} ast element 331 * @return true if the given {@code DetailAST} node is matching 332 */ 333 private boolean isMatchingByLineAndColumnAndTokenType(DetailAST ast) { 334 return ast.getLineNo() == lineNumber 335 && expandedTabColumn(ast) == columnNumber 336 && (tokenType == 0 || tokenType == ast.getType()); 337 } 338 339 /** 340 * Escape <, >, &, ' and " as their entities. 341 * Custom method for Xpath generation to maintain compatibility 342 * with Saxon and encoding outside Ascii range characters. 343 * 344 * <p>According to 345 * <a href="https://saxon.sourceforge.net/saxon7.1/expressions.html">Saxon documentation</a>: 346 * <br> 347 * From Saxon 7.1, string delimiters can be doubled within the string to represent` 348 * the delimiter itself: for example select='"He said, ""Go!"""'. 349 * 350 * <p>Guava cannot as Guava encoding does not meet our requirements like 351 * double encoding for apos, removed slashes which are basic requirements 352 * for Saxon to decode. 353 * 354 * @param value the value to escape. 355 * @return the escaped value if necessary. 356 */ 357 private static String encode(String value) { 358 final StringBuilder sb = new StringBuilder(256); 359 value.codePoints().forEach( 360 chr -> { 361 sb.append(encodeCharacter(Character.toChars(chr)[0])); 362 } 363 ); 364 return sb.toString(); 365 } 366 367 /** 368 * Encodes escape character for Xpath. Escape characters need '&' before, but it also 369 * requires XML 1.1 370 * until <a href="https://github.com/checkstyle/checkstyle/issues/5168">#5168</a>. 371 * 372 * @param chr Character to check. 373 * @return String, Encoded string. 374 */ 375 private static String encodeCharacter(char chr) { 376 final String encode; 377 switch (chr) { 378 case '<': 379 encode = "<"; 380 break; 381 case '>': 382 encode = ">"; 383 break; 384 case '\'': 385 encode = "''"; 386 break; 387 case '\"': 388 encode = """; 389 break; 390 case '&': 391 encode = "&"; 392 break; 393 default: 394 encode = String.valueOf(chr); 395 break; 396 } 397 return encode; 398 } 399}