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