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