1 ////////////////////////////////////////////////////////////////////////////////
2 // checkstyle: Checks Java source code for adherence to a set of rules.
3 // Copyright (C) 2001-2019 the original author or authors.
4 //
5 // This library is free software; you can redistribute it and/or
6 // modify it under the terms of the GNU Lesser General Public
7 // License as published by the Free Software Foundation; either
8 // version 2.1 of the License, or (at your option) any later version.
9 //
10 // This library is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 // Lesser General Public License for more details.
14 //
15 // You should have received a copy of the GNU Lesser General Public
16 // License along with this library; if not, write to the Free Software
17 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 ////////////////////////////////////////////////////////////////////////////////
19
20 package com.puppycrawl.tools.checkstyle.xpath;
21
22 import java.util.ArrayList;
23 import java.util.List;
24 import java.util.stream.Collectors;
25
26 import com.puppycrawl.tools.checkstyle.TreeWalkerAuditEvent;
27 import com.puppycrawl.tools.checkstyle.api.DetailAST;
28 import com.puppycrawl.tools.checkstyle.api.FileText;
29 import com.puppycrawl.tools.checkstyle.utils.CommonUtil;
30 import com.puppycrawl.tools.checkstyle.utils.TokenUtil;
31 import com.puppycrawl.tools.checkstyle.utils.XpathUtil;
32
33 /**
34 * Generates xpath queries. Xpath queries are generated based on received
35 * {@code DetailAst} element, line number, column number and token type.
36 * Token type parameter is optional.
37 *
38 * <p>
39 * Example class
40 * </p>
41 * <pre>
42 * public class Main {
43 *
44 * public String sayHello(String name) {
45 * return "Hello, " + name;
46 * }
47 * }
48 * </pre>
49 *
50 * <p>
51 * Following expression returns list of queries. Each query is the string representing full
52 * path to the node inside Xpath tree, whose line number is 3 and column number is 4.
53 * </p>
54 * <pre>
55 * new XpathQueryGenerator(rootAst, 3, 4).generate();
56 * </pre>
57 *
58 * <p>
59 * Result list
60 * </p>
61 * <ul>
62 * <li>
63 * /CLASS_DEF[./IDENT[@text='Main']]/OBJBLOCK/METHOD_DEF[./IDENT[@text='sayHello']]
64 * </li>
65 * <li>
66 * /CLASS_DEF[./IDENT[@text='Main']]/OBJBLOCK/METHOD_DEF[./IDENT[@text='sayHello']]
67 * /MODIFIERS
68 * </li>
69 * <li>
70 * /CLASS_DEF[./IDENT[@text='Main']]/OBJBLOCK/METHOD_DEF[./IDENT[@text='sayHello']]
71 * /MODIFIERS/LITERAL_PUBLIC
72 * </li>
73 * </ul>
74 *
75 */
76 public class XpathQueryGenerator {
77
78 /** The root ast. */
79 private final DetailAST rootAst;
80 /** The line number of the element for which the query should be generated. */
81 private final int lineNumber;
82 /** The column number of the element for which the query should be generated. */
83 private final int columnNumber;
84 /** The token type of the element for which the query should be generated. Optional. */
85 private final int tokenType;
86 /** The {@code FileText} object, representing content of the file. */
87 private final FileText fileText;
88 /** The distance between tab stop position. */
89 private final int tabWidth;
90
91 /**
92 * Creates a new {@code XpathQueryGenerator} instance.
93 *
94 * @param event {@code TreeWalkerAuditEvent} object
95 * @param tabWidth distance between tab stop position
96 */
97 public XpathQueryGenerator(TreeWalkerAuditEvent event, int tabWidth) {
98 this(event.getRootAst(), event.getLine(), event.getColumn(), event.getTokenType(),
99 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 * @return list of xpath queries of nodes, matching line number, column number and token type
140 */
141 public List<String> generate() {
142 return getMatchingAstElements()
143 .stream()
144 .map(XpathQueryGenerator::generateXpathQuery)
145 .collect(Collectors.toList());
146 }
147
148 /**
149 * Returns child {@code DetailAst} element of the given root, which has text attribute.
150 * @param root {@code DetailAST} root ast
151 * @return child {@code DetailAst} element of the given root
152 */
153 private static DetailAST findChildWithTextAttribute(DetailAST root) {
154 return TokenUtil.findFirstTokenByPredicate(root,
155 XpathUtil::supportsTextAttribute).orElse(null);
156 }
157
158 /**
159 * Returns child {@code DetailAst} element of the given root, which has text attribute.
160 * Performs search recursively inside node's subtree.
161 * @param root {@code DetailAST} root ast
162 * @return child {@code DetailAst} element of the given root
163 */
164 private static DetailAST findChildWithTextAttributeRecursively(DetailAST root) {
165 DetailAST res = findChildWithTextAttribute(root);
166 for (DetailAST ast = root.getFirstChild(); ast != null && res == null;
167 ast = ast.getNextSibling()) {
168 res = findChildWithTextAttributeRecursively(ast);
169 }
170 return res;
171 }
172
173 /**
174 * Returns full xpath query for given ast element.
175 * @param ast {@code DetailAST} ast element
176 * @return full xpath query for given ast element
177 */
178 private static String generateXpathQuery(DetailAST ast) {
179 final StringBuilder xpathQueryBuilder = new StringBuilder(getXpathQuery(null, ast));
180 if (!isXpathQueryForNodeIsAccurateEnough(ast)) {
181 xpathQueryBuilder.append('[');
182 final DetailAST child = findChildWithTextAttributeRecursively(ast);
183 if (child == null) {
184 xpathQueryBuilder.append(findPositionAmongSiblings(ast));
185 }
186 else {
187 xpathQueryBuilder.append('.').append(getXpathQuery(ast, child));
188 }
189 xpathQueryBuilder.append(']');
190 }
191 return xpathQueryBuilder.toString();
192 }
193
194 /**
195 * Finds position of the ast element among siblings.
196 * @param ast {@code DetailAST} ast element
197 * @return position of the ast element
198 */
199 private static int findPositionAmongSiblings(DetailAST ast) {
200 DetailAST cur = ast;
201 int pos = 0;
202 while (cur != null) {
203 if (cur.getType() == ast.getType()) {
204 pos++;
205 }
206 cur = cur.getPreviousSibling();
207 }
208 return pos;
209 }
210
211 /**
212 * Checks if ast element has all requirements to have unique xpath query.
213 * @param ast {@code DetailAST} ast element
214 * @return true if ast element will have unique xpath query, false otherwise
215 */
216 private static boolean isXpathQueryForNodeIsAccurateEnough(DetailAST ast) {
217 return !hasAtLeastOneSiblingWithSameTokenType(ast)
218 || XpathUtil.supportsTextAttribute(ast)
219 || findChildWithTextAttribute(ast) != null;
220 }
221
222 /**
223 * Returns list of nodes matching defined line number, column number and token type.
224 * @return list of nodes matching defined line number, column number and token type
225 */
226 private List<DetailAST> getMatchingAstElements() {
227 final List<DetailAST> result = new ArrayList<>();
228 DetailAST curNode = rootAst;
229 while (curNode != null) {
230 if (isMatchingByLineAndColumnAndTokenType(curNode)) {
231 result.add(curNode);
232 }
233 DetailAST toVisit = curNode.getFirstChild();
234 while (curNode != null && toVisit == null) {
235 toVisit = curNode.getNextSibling();
236 curNode = curNode.getParent();
237 }
238
239 curNode = toVisit;
240 }
241 return result;
242 }
243
244 /**
245 * Returns relative xpath query for given ast element from root.
246 * @param root {@code DetailAST} root element
247 * @param ast {@code DetailAST} ast element
248 * @return relative xpath query for given ast element from root
249 */
250 private static String getXpathQuery(DetailAST root, DetailAST ast) {
251 final StringBuilder resultBuilder = new StringBuilder(1024);
252 DetailAST cur = ast;
253 while (cur != root) {
254 final StringBuilder curNodeQueryBuilder = new StringBuilder(256);
255 curNodeQueryBuilder.append('/')
256 .append(TokenUtil.getTokenName(cur.getType()));
257 if (XpathUtil.supportsTextAttribute(cur)) {
258 curNodeQueryBuilder.append("[@text='")
259 .append(XpathUtil.getTextAttributeValue(cur))
260 .append("']");
261 }
262 else {
263 final DetailAST child = findChildWithTextAttribute(cur);
264 if (child != null && child != ast) {
265 curNodeQueryBuilder.append("[.")
266 .append(getXpathQuery(cur, child))
267 .append(']');
268 }
269 }
270
271 resultBuilder.insert(0, curNodeQueryBuilder);
272 cur = cur.getParent();
273 }
274 return resultBuilder.toString();
275 }
276
277 /**
278 * Checks if the given ast element has unique {@code TokenTypes} among siblings.
279 * @param ast {@code DetailAST} ast element
280 * @return if the given ast element has unique {@code TokenTypes} among siblings
281 */
282 private static boolean hasAtLeastOneSiblingWithSameTokenType(DetailAST ast) {
283 boolean result = false;
284 DetailAST prev = ast.getPreviousSibling();
285 while (prev != null) {
286 if (prev.getType() == ast.getType()) {
287 result = true;
288 break;
289 }
290 prev = prev.getPreviousSibling();
291 }
292 DetailAST next = ast.getNextSibling();
293 while (next != null) {
294 if (next.getType() == ast.getType()) {
295 result = true;
296 break;
297 }
298 next = next.getNextSibling();
299 }
300 return result;
301 }
302
303 /**
304 * Returns the column number with tabs expanded.
305 * @param ast {@code DetailAST} root ast
306 * @return the column number with tabs expanded
307 */
308 private int expandedTabColumn(DetailAST ast) {
309 return 1 + CommonUtil.lengthExpandedTabs(fileText.get(lineNumber - 1),
310 ast.getColumnNo(), tabWidth);
311 }
312
313 /**
314 * Checks if the given {@code DetailAST} node is matching line number, column number and token
315 * type.
316 * @param ast {@code DetailAST} ast element
317 * @return true if the given {@code DetailAST} node is matching
318 */
319 private boolean isMatchingByLineAndColumnAndTokenType(DetailAST ast) {
320 return ast.getLineNo() == lineNumber
321 && expandedTabColumn(ast) == columnNumber
322 && (tokenType == 0 || tokenType == ast.getType());
323 }
324 }