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 &lt;, &gt;, &amp;, &#39; and &quot; 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 '&amp;' 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 = "&lt;";
377                break;
378            case '>':
379                encode = "&gt;";
380                break;
381            case '\'':
382                encode = "&apos;&apos;";
383                break;
384            case '\"':
385                encode = "&quot;";
386                break;
387            case '&':
388                encode = "&amp;";
389                break;
390            default:
391                encode = String.valueOf(chr);
392                break;
393        }
394        return encode;
395    }
396}