Repository: jhy/jsoup
Pull request #2310 (2025-04-24 04:03:31)

Revamp QueryParser
The QueryParser, which parses CSS selectors, was growing unwieldy. This simplifies the implementation into a clearer recursive descent parser.

Particularly this removes some ugly precedence handling for the or `,` grouping, and redundant unescape / escape hops.


Patch:
diff --git a/src/main/java/org/jsoup/parser/TokenQueue.java b/src/main/java/org/jsoup/parser/TokenQueue.java
index e5553caf..6b17beda 100644
--- a/src/main/java/org/jsoup/parser/TokenQueue.java
+++ b/src/main/java/org/jsoup/parser/TokenQueue.java
@@ -69,6 +69,11 @@ public class TokenQueue {
         return reader.matchesIgnoreCase(seq);
     }
 
+    /** Tests if the next character on the queue matches the character, case-sensitively. */
+    public boolean matches(char c) {
+        return reader.matches(c);
+    }
+
     /**
      @deprecated will be removed in 1.21.1.
      */
@@ -98,6 +103,15 @@ public class TokenQueue {
         return reader.matchConsumeIgnoreCase(seq);
     }
 
+    /** If the queue matches the supplied (case-sensitive) character, consume it off the queue. */
+    public boolean matchChomp(char c) {
+        if (reader.matches(c)) {
+            consume();
+            return true;
+        }
+        return false;
+    }
+
     /**
      Tests if queue starts with a whitespace character.
      @return if starts with whitespace
diff --git a/src/main/java/org/jsoup/select/CombiningEvaluator.java b/src/main/java/org/jsoup/select/CombiningEvaluator.java
index 610ff13b..17968789 100644
--- a/src/main/java/org/jsoup/select/CombiningEvaluator.java
+++ b/src/main/java/org/jsoup/select/CombiningEvaluator.java
@@ -31,6 +31,11 @@ public abstract class CombiningEvaluator extends Evaluator {
         updateEvaluators();
     }
 
+    public void add(Evaluator e) {
+        evaluators.add(e);
+        updateEvaluators();
+    }
+
     @Override protected void reset() {
         for (Evaluator evaluator : evaluators) {
             evaluator.reset();
@@ -42,15 +47,6 @@ public abstract class CombiningEvaluator extends Evaluator {
         return cost;
     }
 
-    @Nullable Evaluator rightMostEvaluator() {
-        return num > 0 ? evaluators.get(num - 1) : null;
-    }
-    
-    void replaceRightMostEvaluator(Evaluator replacement) {
-        evaluators.set(num - 1, replacement);
-        updateEvaluators();
-    }
-
     void updateEvaluators() {
         // used so we don't need to bash on size() for every match test
         num = evaluators.size();
@@ -110,11 +106,6 @@ public abstract class CombiningEvaluator extends Evaluator {
             super();
         }
 
-        public void add(Evaluator e) {
-            evaluators.add(e);
-            updateEvaluators();
-        }
-
         @Override
         public boolean matches(Element root, Element node) {
             for (int i = 0; i < num; i++) {
diff --git a/src/main/java/org/jsoup/select/QueryParser.java b/src/main/java/org/jsoup/select/QueryParser.java
index 4180dd29..d564b66a 100644
--- a/src/main/java/org/jsoup/select/QueryParser.java
+++ b/src/main/java/org/jsoup/select/QueryParser.java
@@ -3,9 +3,9 @@ package org.jsoup.select;
 import org.jsoup.internal.StringUtil;
 import org.jsoup.helper.Validate;
 import org.jsoup.parser.TokenQueue;
+import org.jspecify.annotations.Nullable;
 
-import java.util.ArrayList;
-import java.util.List;
+import java.util.function.Function;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 
@@ -16,12 +16,12 @@ import static org.jsoup.internal.Normalizer.normalize;
  * Parses a CSS selector into an Evaluator tree.
  */
 public class QueryParser {
-    private final static char[] Combinators = {',', '>', '+', '~', ' '};
+    private final static char[] Combinators = {'>', '+', '~'}; // ' ' is also a combinator, but found implicitly
     private final static String[] AttributeEvals = new String[]{"=", "!=", "^=", "$=", "*=", "~="};
+    private final static char[] SequenceEnders = {',', ')'};
 
     private final TokenQueue tq;
     private final String query;
-    private final List<Evaluator> evals = new ArrayList<>();
 
     /**
      * Create a new QueryParser.
@@ -35,11 +35,12 @@ public class QueryParser {
     }
 
     /**
-     * Parse a CSS query into an Evaluator. If you are evaluating the same query repeatedly, it may be more efficient to
-     * parse it once and reuse the Evaluator.
-     * @param query CSS query
-     * @return Evaluator
-     * @see Selector selector query syntax
+     Parse a CSS query into an Evaluator. If you are evaluating the same query repeatedly, it may be more efficient to
+     parse it once and reuse the Evaluator.
+
+     @param query CSS query
+     @return Evaluator
+     @see Selector selector query syntax
      */
     public static Evaluator parse(String query) {
         try {
@@ -51,137 +52,131 @@ public class QueryParser {
     }
 
     /**
-     * Parse the query
-     * @return Evaluator
+     Parse the query. We use this simplified expression of the grammar:
+     <pre>
+     SelectorGroup   ::= Selector (',' Selector)*
+     Selector        ::= SimpleSequence ( Combinator SimpleSequence )*
+     SimpleSequence  ::= [ TypeSelector ] ( ID | Class | Attribute | Pseudo )*
+     Pseudo           ::= ':' Name [ '(' SelectorGroup ')' ]
+     Combinator      ::= S+         // descendant (whitespace)
+     | '>'       // child
+     | '+'       // adjacent sibling
+     | '~'       // general sibling
+     </pre>
+
+     See <a href="https://www.w3.org/TR/selectors-4/#grammar">selectors-4</a> for the real thing
      */
     Evaluator parse() {
+        Evaluator eval = parseSelectorGroup();
         tq.consumeWhitespace();
+        if (!tq.isEmpty())
+            throw new Selector.SelectorParseException("Could not parse query '%s': unexpected token at '%s'", query, tq.remainder());
+        return eval;
+    }
 
-        if (tq.matchesAny(Combinators)) { // if starts with a combinator, use root as elements
-            evals.add(new StructuralEvaluator.Root());
-            combinator(tq.consume());
-        } else {
-            evals.add(consumeEvaluator());
+    Evaluator parseSelectorGroup() {
+        // SelectorGroup. Into an Or if > 1 Selector
+        Evaluator left = parseSelector();
+        while (tq.matchChomp(',')) {
+            Evaluator right = parseSelector();
+            left = or(left, right);
         }
+        return left;
+    }
 
-        while (!tq.isEmpty()) {
-            // hierarchy and extras
-            boolean seenWhite = tq.consumeWhitespace();
+    Evaluator parseSelector() {
+        // SimpleSequence ( Combinator SimpleSequence )*
+        Evaluator left = parseSimpleSequence();
+
+        while (true) {
+            char combinator = 0;
+            if (tq.consumeWhitespace())
+                combinator = ' ';            // maybe descendant?
+            if (tq.matchesAny(Combinators)) // no, explicit
+                combinator = tq.consume();
+            else if (tq.matchesAny(SequenceEnders)) // , - space after simple like "foo , bar"; ) - close of :has()
+                break;
 
-            if (tq.matchesAny(Combinators)) {
-                combinator(tq.consume());
-            } else if (seenWhite) {
-                combinator(' ');
-            } else { // E.class, E#id, E[attr] etc. AND
-                evals.add(consumeEvaluator()); // take next el, #. etc off queue
+            if (combinator != 0) {
+                Evaluator right = parseSimpleSequence();
+                left = combinator(left, combinator, right);
+            } else {
+                break;
             }
         }
-
-        if (evals.size() == 1)
-            return evals.get(0);
-
-        return new CombiningEvaluator.And(evals);
+        return left;
     }
 
-    private void combinator(char combinator) {
+    Evaluator parseSimpleSequence() {
+        // SimpleSequence ::= TypeSelector? ( Hash | Class | Pseudo )*
+        Evaluator left = null;
         tq.consumeWhitespace();
-        String subQuery = consumeSubQuery(); // support multi > childs
-
-        Evaluator rootEval; // the new topmost evaluator
-        Evaluator currentEval; // the evaluator the new eval will be combined to. could be root, or rightmost or.
-        Evaluator newEval = parse(subQuery); // the evaluator to add into target evaluator
-        boolean replaceRightMost = false;
-
-        if (evals.size() == 1) {
-            rootEval = currentEval = evals.get(0);
-            // make sure OR (,) has precedence:
-            if (rootEval instanceof CombiningEvaluator.Or && combinator != ',') {
-                currentEval = ((CombiningEvaluator.Or) currentEval).rightMostEvaluator();
-                assert currentEval != null; // rightMost signature can return null (if none set), but always will have one by this point
-                replaceRightMost = true;
-            }
-        }
-        else {
-            rootEval = currentEval = new CombiningEvaluator.And(evals);
+
+        // one optional type selector
+        if (tq.matchesWord() || tq.matches("*|"))
+            left = byTag();
+        else if (tq.matchChomp('*'))
+            left = new Evaluator.AllElements();
+        else if (tq.matchesAny(Combinators))  // e.g. query is "> div"; type is root element
+            left = new StructuralEvaluator.Root();
+
+        // zero or more subclasses (#, ., [)
+        while(true) {
+            Evaluator right = parseSubclass();
+            if (right != null)
+                left = and(left, right);
+            else break; // no more simple tokens
         }
-        evals.clear();
 
-        // for most combinators: change the current eval into an AND of the current eval and the new eval
+        if (left == null)
+            throw new Selector.SelectorParseException("Could not parse query '%s': unexpected token at '%s'", query, tq.remainder());
+        return left;
+    }
+
+    static Evaluator combinator(Evaluator left, char combinator, Evaluator right) {
         switch (combinator) {
             case '>':
-                ImmediateParentRun run = currentEval instanceof ImmediateParentRun ?
-                        (ImmediateParentRun) currentEval : new ImmediateParentRun(currentEval);
-                run.add(newEval);
-                currentEval = run;
-                break;
+                ImmediateParentRun run = left instanceof ImmediateParentRun ?
+                    (ImmediateParentRun) left : new ImmediateParentRun(left);
+                run.add(right);
+                return run;
             case ' ':
-                currentEval = new CombiningEvaluator.And(new StructuralEvaluator.Ancestor(currentEval), newEval);
-                break;
+                return and(new StructuralEvaluator.Ancestor(left), right);
             case '+':
-                currentEval = new CombiningEvaluator.And(new StructuralEvaluator.ImmediatePreviousSibling(currentEval), newEval);
-                break;
+                return and(new StructuralEvaluator.ImmediatePreviousSibling(left), right);
             case '~':
-                currentEval = new CombiningEvaluator.And(new StructuralEvaluator.PreviousSibling(currentEval), newEval);
-                break;
-            case ',':
-                CombiningEvaluator.Or or;
-                if (currentEval instanceof CombiningEvaluator.Or) {
-                    or = (CombiningEvaluator.Or) currentEval;
-                } else {
-                    or = new CombiningEvaluator.Or();
-                    or.add(currentEval);
-                }
-                or.add(newEval);
-                currentEval = or;
-                break;
+                return and(new StructuralEvaluator.PreviousSibling(left), right);
             default:
                 throw new Selector.SelectorParseException("Unknown combinator '%s'", combinator);
         }
+    }
 
-        if (replaceRightMost)
-            ((CombiningEvaluator.Or) rootEval).replaceRightMostEvaluator(currentEval);
-        else rootEval = currentEval;
-        evals.add(rootEval);
+    @Nullable Evaluator parseSubclass() {
+        //  Subclass: ID | Class | Attribute | Pseudo
+        if      (tq.matchChomp('#'))    return byId();
+        else if (tq.matchChomp('.'))    return byClass();
+        else if (tq.matches('['))       return byAttribute();
+        else if (tq.matchChomp(':'))    return parsePseudoSelector();
+        else                            return null;
     }
 
-    private String consumeSubQuery() {
-        StringBuilder sq = StringUtil.borrowBuilder();
-        boolean seenClause = false; // eat until we hit a combinator after eating something else
-        while (!tq.isEmpty()) {
-            if (tq.matchesAny(Combinators)) {
-                if (seenClause)
-                    break;
-                sq.append(tq.consume());
-                continue;
-            }
-            seenClause = true;
-            if (tq.matches("("))
-                sq.append("(").append(tq.chompBalanced('(', ')')).append(")");
-            else if (tq.matches("["))
-                sq.append("[").append(tq.chompBalanced('[', ']')).append("]");
-            else if (tq.matches("\\")) { // bounce over escapes
-                sq.append(TokenQueue.escapeCssIdentifier(tq.consumeCssIdentifier()));
-            } else
-                sq.append(tq.consume());
+    /** Merge two evals into an Or. */
+    static Evaluator or(Evaluator left, Evaluator right) {
+        if (left instanceof CombiningEvaluator.Or) {
+            ((CombiningEvaluator.Or) left).add(right);
+            return left;
         }
-        return StringUtil.releaseBuilder(sq);
+        return new CombiningEvaluator.Or(left, right);
     }
 
-    private Evaluator consumeEvaluator() {
-        if (tq.matchChomp("#"))
-            return byId();
-        else if (tq.matchChomp("."))
-            return byClass();
-        else if (tq.matchesWord() || tq.matches("*|"))
-            return byTag();
-        else if (tq.matches("["))
-            return byAttribute();
-        else if (tq.matchChomp("*"))
-            return new Evaluator.AllElements();
-        else if (tq.matchChomp(":"))
-            return parsePseudoSelector();
-		else // unhandled
-            throw new Selector.SelectorParseException("Could not parse query '%s': unexpected token at '%s'", query, tq.remainder());
+    /** Merge two evals into an And. */
+    static Evaluator and(@Nullable Evaluator left, Evaluator right) {
+        if (left == null) return right;
+        if (left instanceof CombiningEvaluator.And) {
+            ((CombiningEvaluator.And) left).add(right);
+            return left;
+        }
+        return new CombiningEvaluator.And(left, right);
     }
 
     private Evaluator parsePseudoSelector() {
@@ -299,7 +294,7 @@ public class QueryParser {
             else
                 eval = new Evaluator.Attribute(key);
         } else {
-            if (cq.matchChomp("="))
+            if (cq.matchChomp('='))
                 eval = new Evaluator.AttributeWithValue(key, cq.remainder());
             else if (cq.matchChomp("!="))
                 eval = new Evaluator.AttributeWithValueNot(key, cq.remainder());
@@ -364,16 +359,19 @@ public class QueryParser {
 
     // pseudo selector :has(el)
     private Evaluator has() {
-        String subQuery = consumeParens();
-        Validate.notEmpty(subQuery, ":has(selector) sub-select must not be empty");
-        return new StructuralEvaluator.Has(parse(subQuery));
+        return parseNested(StructuralEvaluator.Has::new, ":has() must have a selector");
     }
 
-    // psuedo selector :is()
+    // pseudo selector :is()
     private Evaluator is() {
-        String subQuery = consumeParens();
-        Validate.notEmpty(subQuery, ":is(selector) sub-select must not be empty");
-        return new StructuralEvaluator.Is(parse(subQuery));
+        return parseNested(StructuralEvaluator.Is::new, ":is() must have a selector");
+    }
+
+    private Evaluator parseNested(Function<Evaluator, Evaluator> func, String err) {
+        Validate.isTrue(tq.matchChomp('('), err);
+        Evaluator eval = parseSelectorGroup();
+        Validate.isTrue(tq.matchChomp(')'), err);
+        return func.apply(eval);
     }
 
     // pseudo selector :contains(text), containsOwn(text)


Test patch:
diff --git a/src/test/java/org/jsoup/select/QueryParserTest.java b/src/test/java/org/jsoup/select/QueryParserTest.java
index 8d20051a..d48c1270 100644
--- a/src/test/java/org/jsoup/select/QueryParserTest.java
+++ b/src/test/java/org/jsoup/select/QueryParserTest.java
@@ -23,6 +23,7 @@ public class QueryParserTest {
                 "<p><strong>yes</strong></p>" +
                 "</body></html>");
         assertEquals("l1 yes", doc.body().select(">p>strong,>li>strong").text()); // selecting immediate from body
+        assertEquals("l1 yes", doc.body().select(" > p > strong , > li > strong").text()); // space variants
         assertEquals("l2 yes", doc.select("body>p>strong,body>*>li>strong").text());
         assertEquals("l2 yes", doc.select("body>*>li>strong,body>p>strong").text());
         assertEquals("l2 yes", doc.select("body>p>strong,body>*>li>strong").text());
@@ -157,7 +158,7 @@ public class QueryParserTest {
     public void exceptOnUnhandledEvaluator() {
         SelectorParseException exception =
             assertThrows(SelectorParseException.class, () -> QueryParser.parse("div / foo"));
-        assertEquals("Could not parse query '/': unexpected token at '/'", exception.getMessage());
+        assertEquals("Could not parse query 'div / foo': unexpected token at '/ foo'", exception.getMessage());
     }
 
     @Test public void okOnSpacesForeAndAft() {
@@ -207,4 +208,10 @@ public class QueryParserTest {
         assertEquals("(ImmediateParentRun (Tag 'html')(Tag 'body')(And (Tag 'div')(Class '.-4a')))", sexpr(genClassQ));
         assertEquals("(ImmediateParentRun (Tag 'html')(Tag 'body')(Id '#-4a'))", sexpr(deepIdQ));
     }
+
+    @Test void trailingParens() {
+        SelectorParseException exception =
+            assertThrows(SelectorParseException.class, () -> QueryParser.parse("div:has(p))"));
+        assertEquals("Could not parse query 'div:has(p))': unexpected token at ')'", exception.getMessage());
+    }
 }
diff --git a/src/test/java/org/jsoup/select/SelectorTest.java b/src/test/java/org/jsoup/select/SelectorTest.java
index 049f95dd..75606981 100644
--- a/src/test/java/org/jsoup/select/SelectorTest.java
+++ b/src/test/java/org/jsoup/select/SelectorTest.java
@@ -1473,5 +1473,4 @@ public class SelectorTest {
         assertEquals("-0a", Selector.unescapeCssIdentifier("-\\30 a"));
         assertEquals("a0b", Selector.unescapeCssIdentifier("a0b"));
     }
-
 }