001package org.jsoup.select;
002
003import org.jsoup.helper.Regex;
004import org.jsoup.internal.StringUtil;
005import org.jsoup.helper.Validate;
006import org.jsoup.nodes.CDataNode;
007import org.jsoup.nodes.Comment;
008import org.jsoup.nodes.DataNode;
009import org.jsoup.nodes.LeafNode;
010import org.jsoup.nodes.Node;
011import org.jsoup.nodes.TextNode;
012import org.jsoup.parser.TokenQueue;
013import org.jspecify.annotations.Nullable;
014
015import java.util.function.Function;
016import java.util.regex.Matcher;
017import java.util.regex.Pattern;
018
019import static org.jsoup.select.StructuralEvaluator.ImmediateParentRun;
020import static org.jsoup.internal.Normalizer.normalize;
021
022/**
023 * Parses a CSS selector into an Evaluator tree.
024 */
025public class QueryParser implements AutoCloseable {
026    private final static char[] Combinators = {'>', '+', '~'}; // ' ' is also a combinator, but found implicitly
027    private final static String[] AttributeEvals = new String[]{"=", "!=", "^=", "$=", "*=", "~="};
028    private final static char[] SequenceEnders = {',', ')'};
029
030    private final TokenQueue tq;
031    private final String query;
032    private boolean inNodeContext; // ::comment:contains should act on node value, vs element text
033
034    /**
035     * Create a new QueryParser.
036     * @param query CSS query
037     */
038    private QueryParser(String query) {
039        Validate.notEmpty(query);
040        query = query.trim();
041        this.query = query;
042        this.tq = new TokenQueue(query);
043    }
044
045    /**
046     Parse a CSS query into an Evaluator. If you are evaluating the same query repeatedly, it may be more efficient to
047     parse it once and reuse the Evaluator.
048
049     @param query CSS query
050     @return Evaluator
051     @see Selector selector query syntax
052     @throws Selector.SelectorParseException if the CSS query is invalid
053     */
054    public static Evaluator parse(String query) {
055        try (QueryParser p = new QueryParser(query)) {
056            return p.parse();
057        } catch (IllegalArgumentException e) {
058            throw new Selector.SelectorParseException(e.getMessage());
059        }
060    }
061
062    /**
063     Parse the query. We use this simplified expression of the grammar:
064     <pre>
065     SelectorGroup   ::= Selector (',' Selector)*
066     Selector        ::= [ Combinator ] SimpleSequence ( Combinator SimpleSequence )*
067     SimpleSequence  ::= [ TypeSelector ] ( ID | Class | Attribute | Pseudo )*
068     Pseudo           ::= ':' Name [ '(' SelectorGroup ')' ]
069     Combinator      ::= S+         // descendant (whitespace)
070     | '>'       // child
071     | '+'       // adjacent sibling
072     | '~'       // general sibling
073     </pre>
074
075     See <a href="https://www.w3.org/TR/selectors-4/#grammar">selectors-4</a> for the real thing
076     */
077    Evaluator parse() {
078        Evaluator eval = parseSelectorGroup();
079        tq.consumeWhitespace();
080        if (!tq.isEmpty())
081            throw new Selector.SelectorParseException("Could not parse query '%s': unexpected token at '%s'", query, tq.remainder());
082        return eval;
083    }
084
085    Evaluator parseSelectorGroup() {
086        // SelectorGroup. Into an Or if > 1 Selector
087        Evaluator left = parseSelector();
088        while (tq.matchChomp(',')) {
089            Evaluator right = parseSelector();
090            left = or(left, right);
091        }
092        return left;
093    }
094
095    Evaluator parseSelector() {
096        // Selector ::= [ Combinator ] SimpleSequence ( Combinator SimpleSequence )*
097        tq.consumeWhitespace();
098
099        Evaluator left;
100        if (tq.matchesAny(Combinators)) {
101            // e.g. query is "> div"; left side is root element
102            left = new StructuralEvaluator.Root();
103        } else {
104            left = parseSimpleSequence();
105        }
106
107        while (true) {
108            char combinator = 0;
109            if (tq.consumeWhitespace())
110                combinator = ' ';            // maybe descendant?
111            if (tq.matchesAny(Combinators)) // no, explicit
112                combinator = tq.consume();
113            else if (tq.matchesAny(SequenceEnders)) // , - space after simple like "foo , bar"; ) - close of :has()
114                break;
115
116            if (combinator != 0) {
117                Evaluator right = parseSimpleSequence();
118                left = combinator(left, combinator, right);
119            } else {
120                break;
121            }
122        }
123        return left;
124    }
125
126    Evaluator parseSimpleSequence() {
127        // SimpleSequence ::= TypeSelector? ( Hash | Class | Pseudo )*
128        Evaluator left = null;
129        tq.consumeWhitespace();
130
131        // one optional type selector
132        if (tq.matchesWord() || tq.matches("*|"))
133            left = byTag();
134        else if (tq.matchChomp('*'))
135            left = new Evaluator.AllElements();
136
137        // zero or more subclasses (#, ., [)
138        while(true) {
139            Evaluator right = parseSubclass();
140            if (right != null) {
141                left = and(left, right);
142            }
143            else break; // no more simple tokens
144        }
145
146        if (left == null)
147            throw new Selector.SelectorParseException("Could not parse query '%s': unexpected token at '%s'", query, tq.remainder());
148        return left;
149    }
150
151    static Evaluator combinator(Evaluator left, char combinator, Evaluator right) {
152        switch (combinator) {
153            case '>':
154                ImmediateParentRun run = left instanceof ImmediateParentRun ?
155                    (ImmediateParentRun) left : new ImmediateParentRun(left);
156                run.add(right);
157                return run;
158            case ' ':
159                return and(new StructuralEvaluator.Ancestor(left), right);
160            case '+':
161                return and(new StructuralEvaluator.ImmediatePreviousSibling(left), right);
162            case '~':
163                return and(new StructuralEvaluator.PreviousSibling(left), right);
164            default:
165                throw new Selector.SelectorParseException("Unknown combinator '%s'", combinator);
166        }
167    }
168
169    @Nullable Evaluator parseSubclass() {
170        //  Subclass: ID | Class | Attribute | Pseudo
171        if      (tq.matchChomp('#'))    return byId();
172        else if (tq.matchChomp('.'))    return byClass();
173        else if (tq.matches('['))       return byAttribute();
174        else if (tq.matchChomp("::"))   return parseNodeSelector(); // ::comment etc
175        else if (tq.matchChomp(':'))    return parsePseudoSelector();
176        else                            return null;
177    }
178
179    /** Merge two evals into an Or. */
180    static Evaluator or(Evaluator left, Evaluator right) {
181        if (left instanceof CombiningEvaluator.Or) {
182            ((CombiningEvaluator.Or) left).add(right);
183            return left;
184        }
185        return new CombiningEvaluator.Or(left, right);
186    }
187
188    /** Merge two evals into an And. */
189    static Evaluator and(@Nullable Evaluator left, Evaluator right) {
190        if (left == null) return right;
191        if (left instanceof CombiningEvaluator.And) {
192            ((CombiningEvaluator.And) left).add(right);
193            return left;
194        }
195        return new CombiningEvaluator.And(left, right);
196    }
197
198    private Evaluator parsePseudoSelector() {
199        final String pseudo = tq.consumeCssIdentifier();
200        switch (pseudo) {
201            case "lt":
202                return new Evaluator.IndexLessThan(consumeIndex());
203            case "gt":
204                return new Evaluator.IndexGreaterThan(consumeIndex());
205            case "eq":
206                return new Evaluator.IndexEquals(consumeIndex());
207            case "has":
208                return has();
209            case "is":
210                return is();
211            case "contains":
212                return contains(false);
213            case "containsOwn":
214                return contains(true);
215            case "containsWholeText":
216                return containsWholeText(false);
217            case "containsWholeOwnText":
218                return containsWholeText(true);
219            case "containsData":
220                return containsData();
221            case "matches":
222                return matches(false);
223            case "matchesOwn":
224                return matches(true);
225            case "matchesWholeText":
226                return matchesWholeText(false);
227            case "matchesWholeOwnText":
228                return matchesWholeText(true);
229            case "not":
230                return not();
231            case "nth-child":
232                return cssNthChild(false, false);
233            case "nth-last-child":
234                return cssNthChild(true, false);
235            case "nth-of-type":
236                return cssNthChild(false, true);
237            case "nth-last-of-type":
238                return cssNthChild(true, true);
239            case "first-child":
240                return new Evaluator.IsFirstChild();
241            case "last-child":
242                return new Evaluator.IsLastChild();
243            case "first-of-type":
244                return new Evaluator.IsFirstOfType();
245            case "last-of-type":
246                return new Evaluator.IsLastOfType();
247            case "only-child":
248                return new Evaluator.IsOnlyChild();
249            case "only-of-type":
250                return new Evaluator.IsOnlyOfType();
251            case "empty":
252                return new Evaluator.IsEmpty();
253            case "blank":
254                return new NodeEvaluator.BlankValue();
255            case "root":
256                return new Evaluator.IsRoot();
257            case "matchText": {
258                @SuppressWarnings("deprecation") // :matchText remains supported until its scheduled removal.
259                Evaluator.MatchText matchText = new Evaluator.MatchText();
260                return matchText;
261            }
262            default:
263                throw new Selector.SelectorParseException("Could not parse query '%s': unexpected token at '%s'", query, tq.remainder());
264        }
265    }
266
267    // ::comment etc
268    private Evaluator parseNodeSelector() {
269        final String pseudo = tq.consumeCssIdentifier();
270        inNodeContext = true;  // Enter node context
271
272        Evaluator left;
273        switch (pseudo) {
274            case "node":
275                left = new NodeEvaluator.InstanceType(Node.class, pseudo);
276                break;
277            case "leafnode":
278                left = new NodeEvaluator.InstanceType(LeafNode.class, pseudo);
279                break;
280            case "text":
281                left = new NodeEvaluator.InstanceType(TextNode.class, pseudo);
282                break;
283            case "comment":
284                left = new NodeEvaluator.InstanceType(Comment.class, pseudo);
285                break;
286            case "data":
287                left = new NodeEvaluator.InstanceType(DataNode.class, pseudo);
288                break;
289            case "cdata":
290                left = new NodeEvaluator.InstanceType(CDataNode.class, pseudo);
291                break;
292            default:
293                throw new Selector.SelectorParseException(
294                    "Could not parse query '%s': unknown node type '::%s'", query, pseudo);
295        }
296
297        // Handle following subclasses in node context (like ::comment:contains())
298        Evaluator right;
299        while ((right = parseSubclass()) != null) {
300            left = and(left, right);
301        }
302
303        inNodeContext = false;
304        return left;
305    }
306
307    private Evaluator byId() {
308        String id = tq.consumeCssIdentifier();
309        Validate.notEmpty(id);
310        return new Evaluator.Id(id);
311    }
312
313    private Evaluator byClass() {
314        String className = tq.consumeCssIdentifier();
315        Validate.notEmpty(className);
316        return new Evaluator.Class(className.trim());
317    }
318
319    private Evaluator byTag() {
320        // todo - these aren't dealing perfectly with case sensitivity. For case sensitive parsers, we should also make
321        // the tag in the selector case-sensitive (and also attribute names). But for now, normalize (lower-case) for
322        // consistency - both the selector and the element tag
323        String tagName = normalize(tq.consumeElementSelector());
324        Validate.notEmpty(tagName);
325
326        // namespaces:
327        if (tagName.startsWith("*|")) { // namespaces: wildcard match equals(tagName) or ending in ":"+tagName
328            String plainTag = tagName.substring(2); // strip *|
329            return new CombiningEvaluator.Or(
330                new Evaluator.Tag(plainTag),
331                new Evaluator.TagEndsWith(":" + plainTag)
332            );
333        } else if (tagName.endsWith("|*")) { // ns|*
334            String ns = tagName.substring(0, tagName.length() - 2) + ":"; // strip |*, to ns:
335            return new Evaluator.TagStartsWith(ns);
336        } else if (tagName.contains("|")) { // flip "abc|def" to "abc:def"
337            tagName = tagName.replace("|", ":");
338        }
339
340        return new Evaluator.Tag(tagName);
341    }
342
343    private Evaluator byAttribute() {
344        try (TokenQueue cq = new TokenQueue(tq.chompBalanced('[', ']'))) {
345            return evaluatorForAttribute(cq);
346        }
347    }
348
349    private Evaluator evaluatorForAttribute(TokenQueue cq) {
350        String key = cq.consumeToAny(AttributeEvals); // eq, not, start, end, contain, match, (no val)
351        key = normalize(key);
352        Validate.notEmpty(key);
353        Validate.isFalse(key.equals("abs:"), "Absolute attribute key must have a name");
354        cq.consumeWhitespace();
355        final Evaluator eval;
356
357        if (cq.isEmpty()) {
358            if (key.startsWith("^"))
359                eval = new Evaluator.AttributeStarting(key.substring(1));
360            else if (key.equals("*")) // any attribute
361                eval = new Evaluator.AttributeStarting("");
362            else
363                eval = new Evaluator.Attribute(key);
364        } else {
365            if (cq.matchChomp('='))
366                eval = new Evaluator.AttributeWithValue(key, cq.remainder());
367            else if (cq.matchChomp("!="))
368                eval = new Evaluator.AttributeWithValueNot(key, cq.remainder());
369            else if (cq.matchChomp("^="))
370                eval = new Evaluator.AttributeWithValueStarting(key, cq.remainder());
371            else if (cq.matchChomp("$="))
372                eval = new Evaluator.AttributeWithValueEnding(key, cq.remainder());
373            else if (cq.matchChomp("*="))
374                eval = new Evaluator.AttributeWithValueContaining(key, cq.remainder());
375            else if (cq.matchChomp("~="))
376                eval = new Evaluator.AttributeWithValueMatching(key, Regex.compile(cq.remainder()));
377            else
378                throw new Selector.SelectorParseException(
379                    "Could not parse attribute query '%s': unexpected token at '%s'", query, cq.remainder());
380        }
381        return eval;
382    }
383
384    //pseudo selectors :first-child, :last-child, :nth-child, ...
385    private static final Pattern NthStepOffset = Pattern.compile("(([+-])?(\\d+)?)n(\\s*([+-])?\\s*\\d+)?", Pattern.CASE_INSENSITIVE);
386    private static final Pattern NthOffset = Pattern.compile("([+-])?(\\d+)");
387
388    private Evaluator cssNthChild(boolean last, boolean ofType) {
389        String arg = normalize(consumeParens()); // arg is like "odd", or "-n+2", within nth-child(odd)
390        final int step, offset;
391        if ("odd".equals(arg)) {
392            step = 2;
393            offset = 1;
394        } else if ("even".equals(arg)) {
395            step = 2;
396            offset = 0;
397        } else {
398            Matcher stepOffsetM, stepM;
399            if ((stepOffsetM = NthStepOffset.matcher(arg)).matches()) {
400                if (stepOffsetM.group(3) != null) // has digits, like 3n+2 or -3n+2
401                    step = Integer.parseInt(stepOffsetM.group(1).replaceFirst("^\\+", ""));
402                else // no digits, might be like n+2, or -n+2. if group(2) == "-", it’s -1;
403                    step = "-".equals(stepOffsetM.group(2)) ? -1 : 1;
404                offset =
405                    stepOffsetM.group(4) != null ? Integer.parseInt(stepOffsetM.group(4).replaceFirst("^\\+", "")) : 0;
406            } else if ((stepM = NthOffset.matcher(arg)).matches()) {
407                step = 0;
408                offset = Integer.parseInt(stepM.group().replaceFirst("^\\+", ""));
409            } else {
410                throw new Selector.SelectorParseException("Could not parse nth-index '%s': unexpected format", arg);
411            }
412        }
413
414        return ofType
415            ? (last ? new Evaluator.IsNthLastOfType(step, offset) : new Evaluator.IsNthOfType(step, offset))
416            : (last ? new Evaluator.IsNthLastChild(step, offset) : new Evaluator.IsNthChild(step, offset));
417    }
418
419    private String consumeParens() {
420        return tq.chompBalanced('(', ')');
421    }
422
423    private int consumeIndex() {
424        String index = consumeParens().trim();
425        Validate.isTrue(StringUtil.isNumeric(index), "Index must be numeric");
426        return Integer.parseInt(index);
427    }
428
429    // pseudo selector :has(el)
430    private Evaluator has() {
431        return parseNested(StructuralEvaluator.Has::new, ":has() must have a selector");
432    }
433
434    // pseudo selector :is()
435    private Evaluator is() {
436        return parseNested(StructuralEvaluator.Is::new, ":is() must have a selector");
437    }
438
439    private Evaluator parseNested(Function<Evaluator, Evaluator> func, String err) {
440        Validate.isTrue(tq.matchChomp('('), err);
441        Evaluator eval = parseSelectorGroup();
442        Validate.isTrue(tq.matchChomp(')'), err);
443        return func.apply(eval);
444    }
445
446    // pseudo selector :contains(text), containsOwn(text)
447    private Evaluator contains(boolean own) {
448        String query = own ? ":containsOwn" : ":contains";
449        String searchText = TokenQueue.unescape(consumeParens());
450        Validate.notEmpty(searchText, query + "(text) query must not be empty");
451
452        if (inNodeContext)
453            return new NodeEvaluator.ContainsValue(searchText);
454
455        return own
456            ? new Evaluator.ContainsOwnText(searchText)
457            : new Evaluator.ContainsText(searchText);
458    }
459
460    private Evaluator containsWholeText(boolean own) {
461        String query = own ? ":containsWholeOwnText" : ":containsWholeText";
462        String searchText = TokenQueue.unescape(consumeParens());
463        Validate.notEmpty(searchText, query + "(text) query must not be empty");
464        return own
465            ? new Evaluator.ContainsWholeOwnText(searchText)
466            : new Evaluator.ContainsWholeText(searchText);
467    }
468
469    // pseudo selector :containsData(data)
470    private Evaluator containsData() {
471        String searchText = TokenQueue.unescape(consumeParens());
472        Validate.notEmpty(searchText, ":containsData(text) query must not be empty");
473        return new Evaluator.ContainsData(searchText);
474    }
475
476    // :matches(regex), matchesOwn(regex)
477    private Evaluator matches(boolean own) {
478        String query = own ? ":matchesOwn" : ":matches";
479        String regex = consumeParens(); // don't unescape, as regex bits will be escaped
480        Validate.notEmpty(regex, query + "(regex) query must not be empty");
481        Regex pattern = Regex.compile(regex);
482
483        if (inNodeContext)
484            return new NodeEvaluator.MatchesValue(pattern);
485
486        return own
487            ? new Evaluator.MatchesOwn(pattern)
488            : new Evaluator.Matches(pattern);
489    }
490
491    // :matches(regex), matchesOwn(regex)
492    private Evaluator matchesWholeText(boolean own) {
493        String query = own ? ":matchesWholeOwnText" : ":matchesWholeText";
494        String regex = consumeParens(); // don't unescape, as regex bits will be escaped
495        Validate.notEmpty(regex, query + "(regex) query must not be empty");
496
497        Regex pattern = Regex.compile(regex);
498        return own
499            ? new Evaluator.MatchesWholeOwnText(pattern)
500            : new Evaluator.MatchesWholeText(pattern);
501    }
502
503    // :not(selector)
504    private Evaluator not() {
505        String subQuery = consumeParens();
506        Validate.notEmpty(subQuery, ":not(selector) subselect must not be empty");
507
508        return new StructuralEvaluator.Not(parse(subQuery));
509    }
510
511    @Override
512    public String toString() {
513        return query;
514    }
515
516    @Override
517    public void close() {
518        tq.close();
519    }
520}