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