Source code

001package org.jsoup.parser;
002
003import org.jsoup.internal.StringUtil;
004import org.jsoup.helper.Validate;
005
006/**
007 A character reader with helpers focusing on parsing CSS selectors. Used internally by jsoup. API subject to changes.
008 */
009
010public class TokenQueue implements AutoCloseable {
011    private static final char Esc = '\\'; // escape char for chomp balanced.
012    private static final char Hyphen_Minus = '-';
013    private static final char Unicode_Null = '\u0000';
014    private static final char Replacement = '\uFFFD';
015
016    private final CharacterReader reader;
017
018    /**
019     Create a new TokenQueue.
020     @param data string of data to back queue.
021     */
022    public TokenQueue(String data) {
023        reader = new CharacterReader(data);
024    }
025
026    /**
027     Is the queue empty?
028     @return true if no data left in queue.
029     */
030    public boolean isEmpty() {
031        return reader.isEmpty();
032    }
033
034    /**
035     Get the current zero-based character offset in the input.
036
037     @since 1.24.1
038     */
039    public int pos() {
040        return reader.pos();
041    }
042
043    /**
044     Consume one character off queue.
045     @return first character on queue.
046     */
047    public char consume() {
048        return reader.consume();
049    }
050
051    /**
052     Drops the next character off the queue.
053     */
054    public void advance() {
055        if (!isEmpty()) reader.advance();
056    }
057
058    char current() {
059        return reader.current();
060    }
061
062    /**
063     Tests if the next characters on the queue match the sequence, case-insensitively.
064     @param seq String to check queue for.
065     @return true if the next characters match.
066     */
067    public boolean matches(String seq) {
068        return reader.matchesIgnoreCase(seq);
069    }
070
071    /** Tests if the next character on the queue matches the character, case-sensitively. */
072    public boolean matches(char c) {
073        return reader.matches(c);
074    }
075
076    /**
077     Tests if the next characters match any of the sequences, case-<b>sensitively</b>.
078     @param seq list of chars to case-sensitively check for
079     @return true of any matched, false if none did
080     */
081    public boolean matchesAny(char... seq) {
082        return reader.matchesAny(seq);
083    }
084
085    /**
086     If the queue case-insensitively matches the supplied string, consume it off the queue.
087     @param seq String to search for, and if found, remove from queue.
088     @return true if found and removed, false if not found.
089     */
090    public boolean matchChomp(String seq) {
091        return reader.matchConsumeIgnoreCase(seq);
092    }
093
094    /** If the queue matches the supplied (case-sensitive) character, consume it off the queue. */
095    public boolean matchChomp(char c) {
096        if (reader.matches(c)) {
097            consume();
098            return true;
099        }
100        return false;
101    }
102
103    /**
104     Tests if queue starts with a whitespace character.
105     @return if starts with whitespace
106     */
107    public boolean matchesWhitespace() {
108        return StringUtil.isWhitespace(reader.current());
109    }
110
111    /**
112     Test if the queue matches a tag word character (letter or digit).
113     @return if matches a word character
114     */
115    public boolean matchesWord() {
116        return Character.isLetterOrDigit(reader.current());
117    }
118
119    /**
120     Consumes the supplied sequence of the queue, case-insensitively. If the queue does not start with the supplied
121     sequence, will throw an illegal state exception -- but you should be running match() against that condition.
122
123     @param seq sequence to remove from head of queue.
124     */
125    public void consume(String seq) {
126        boolean found = reader.matchConsumeIgnoreCase(seq);
127        if (!found) throw new IllegalStateException("Queue did not match expected sequence");
128    }
129
130    /**
131     Pulls a string off the queue, up to but exclusive of the match sequence, or to the queue running out.
132     @param seq String to end on (and not include in return, but leave on queue). <b>Case-sensitive.</b>
133     @return The matched data consumed from queue.
134     */
135    public String consumeTo(String seq) {
136        return reader.consumeTo(seq);
137    }
138
139    /**
140     Consumes to the first sequence provided, or to the end of the queue. Leaves the terminator on the queue.
141     @param seq any number of terminators to consume to. <b>Case-insensitive.</b>
142     @return consumed string
143     */
144    public String consumeToAny(String... seq) {
145        StringBuilder sb = StringUtil.borrowBuilder();
146        OUT: while (!isEmpty()) {
147            for (String s : seq) {
148                if (reader.matchesIgnoreCase(s)) break OUT;
149            }
150            sb.append(consume());
151        }
152        return StringUtil.releaseBuilder(sb);
153    }
154
155    /**
156     Pulls a balanced string off the queue. E.g. if queue is "(one (two) three) four", (,) will return "one (two) three",
157     and leave " four" on the queue. Unbalanced openers and closers can be quoted (with ' or ") or escaped (with \).
158     Those escapes will be left in the returned string, which is suitable for regexes (where we need to preserve the
159     escape), but unsuitable for contains text strings; use unescape for that.
160
161     @param open opener
162     @param close closer
163     @return data matched from the queue
164     */
165    public String chompBalanced(char open, char close) {
166        return chompBalanced(open, close, 0);
167    }
168
169    /**
170     Consume the remainder of a group whose opening delimiter has already been consumed. The closing delimiter is
171     consumed but excluded from the result. Quotes and escapes follow {@link #chompBalanced(char, char)}.
172     If the group is unbalanced, restore the queue position.
173
174     @param open opener
175     @param close closer
176     @return remaining group contents, excluding the closing delimiter
177     @throws IllegalArgumentException if the group is unbalanced
178     @since 1.24.1
179     */
180    public String chompBalancedRemainder(char open, char close) {
181        return chompBalanced(open, close, 1);
182    }
183
184    private String chompBalanced(char open, char close, int depth) {
185        StringBuilder accum = StringUtil.borrowBuilder();
186        char prev = 0;
187        boolean inSingle = false;
188        boolean inDouble = false;
189        boolean inRegexQE = false; // regex \Q .. \E escapes from Pattern.quote()
190        reader.mark(); // mark the initial position to restore if needed
191
192        do {
193            if (isEmpty()) break;
194            char c = consume();
195            if (prev == Esc) {
196                if      (c == 'Q') inRegexQE = true;
197                else if (c == 'E') inRegexQE = false;
198                accum.append(c);
199            } else {
200                if      (c == '\'' && c != open && !inDouble) inSingle = !inSingle;
201                else if (c == '"'  && c != open && !inSingle) inDouble = !inDouble;
202
203                if (inSingle || inDouble || inRegexQE) {
204                    accum.append(c);
205                } else if (c == open) {
206                    depth++;
207                    if (depth > 1) accum.append(c); // don't include the outer match pair in the return
208                } else if (c == close) {
209                    depth--;
210                    if (depth > 0) accum.append(c);
211                } else {
212                    accum.append(c);
213                }
214            }
215            prev = c;
216        } while (depth > 0);
217
218        String out = StringUtil.releaseBuilder(accum);
219        if (depth > 0) {// ran out of queue before seeing enough )
220            reader.rewindToMark(); // restore position if we don't have a balanced string
221            Validate.fail("Did not find balanced marker at '" + out + "'");
222        }
223        return out;
224    }
225    
226    /**
227     * Unescape a \ escaped string.
228     * @param in backslash escaped string
229     * @return unescaped string
230     */
231    public static String unescape(String in) {
232        if (in.indexOf(Esc) == -1) return in;
233
234        StringBuilder out = StringUtil.borrowBuilder();
235        char last = 0;
236        for (char c : in.toCharArray()) {
237            if (c == Esc) {
238                if (last == Esc) {
239                    out.append(c);
240                    c = 0;
241                }
242            }
243            else 
244                out.append(c);
245            last = c;
246        }
247        return StringUtil.releaseBuilder(out);
248    }
249
250    /**
251     Given a CSS identifier (such as a tag, ID, or class), escape any CSS special characters that would otherwise not be
252     valid in a selector.
253
254     @see <a href="https://www.w3.org/TR/cssom-1/#serialize-an-identifier">CSS Object Model, serialize an identifier</a>
255     */
256    public static String escapeCssIdentifier(String in) {
257        if (in.isEmpty()) return in;
258
259        StringBuilder out = StringUtil.borrowBuilder();
260        TokenQueue q = new TokenQueue(in);
261
262        char firstChar = q.current();
263        if (firstChar == Hyphen_Minus) {
264            q.advance();
265            if (q.isEmpty()) {
266                // If the character is the first character and is a "-" (U+002D), and there is no second character, then
267                // the escaped character.
268                appendEscaped(out, Hyphen_Minus);
269            } else {
270                out.append(Hyphen_Minus);
271
272                char secondChar = q.current();
273                if (StringUtil.isDigit(secondChar)) {
274                    // If the character is the second character and is in the range [0-9] (U+0030 to U+0039) and the
275                    // first character is a "-" (U+002D), then the character escaped as code point.
276                    appendEscapedCodepoint(out, q.consume());
277                }
278            }
279        } else if (StringUtil.isDigit(firstChar)) {
280            // If the character is the first character and is in the range [0-9] (U+0030 to U+0039), then the character
281            // escaped as code point.
282            appendEscapedCodepoint(out, q.consume());
283        }
284
285        while (!q.isEmpty()) {
286            // Note: It's fine to iterate on chars because non-ASCII characters are never escaped. So surrogate pairs
287            // are kept intact.
288            char c = q.consume();
289            if (c == Unicode_Null) {
290                // If the character is NULL (U+0000), then the REPLACEMENT CHARACTER (U+FFFD).
291                out.append(Replacement);
292            } else if (c <= '\u001F' || c == '\u007F') {
293                // If the character is in the range [\1-\1f] (U+0001 to U+001F) or is U+007F, then the character
294                // escaped as code point.
295                appendEscapedCodepoint(out, c);
296            } else if (isIdent(c)) {
297                // If the character is not handled by one of the above rules and is greater than or equal to U+0080,
298                // is "-" (U+002D) or "_" (U+005F), or is in one of the ranges [0-9] (U+0030 to U+0039),
299                // [A-Z] (U+0041 to U+005A), or [a-z] (U+0061 to U+007A), then the character itself.
300                out.append(c);
301            } else {
302                // Otherwise, the escaped character.
303                appendEscaped(out, c);
304            }
305        }
306
307        q.close();
308        return StringUtil.releaseBuilder(out);
309    }
310
311    private static void appendEscaped(StringBuilder out, char c) {
312        out.append(Esc).append(c);
313    }
314
315    private static void appendEscapedCodepoint(StringBuilder out, char c) {
316        out.append(Esc).append(Integer.toHexString(c)).append(' ');
317    }
318
319    /**
320     * Pulls the next run of whitespace characters of the queue.
321     * @return Whether consuming whitespace or not
322     */
323    public boolean consumeWhitespace() {
324        boolean seen = false;
325        while (matchesWhitespace()) {
326            advance();
327            seen = true;
328        }
329        return seen;
330    }
331
332    /**
333     * Consume a CSS element selector (tag name, but | instead of : for namespaces (or *| for wildcard namespace), to not conflict with :pseudo selects).
334     * 
335     * @return tag name
336     */
337    public String consumeElementSelector() {
338        return consumeEscapedCssIdentifier(ElementSelectorChars);
339    }
340    private static final char[] ElementSelectorChars = {'*', '|', '_', '-'};
341
342    /**
343     Consume a CSS identifier (ID or class) off the queue.
344     <p>Note: For backwards compatibility this method supports improperly formatted CSS identifiers, e.g. {@code 1} instead
345     of {@code \31}.</p>
346
347     @return The unescaped identifier.
348     @throws IllegalArgumentException if an invalid escape sequence was found. Afterward, the state of the TokenQueue
349     is undefined.
350     @see <a href="https://www.w3.org/TR/css-syntax-3/#consume-name">CSS Syntax Module Level 3, Consume an ident sequence</a>
351     @see <a href="https://www.w3.org/TR/css-syntax-3/#typedef-ident-token">CSS Syntax Module Level 3, ident-token</a>
352     */
353    public String consumeCssIdentifier() {
354        if (isEmpty()) throw new IllegalArgumentException("CSS identifier expected, but end of input found");
355
356        // Fast path for CSS identifiers that don't contain escape sequences.
357        String identifier = reader.consumeMatching(TokenQueue::isIdent);
358        char c = current();
359        if (c != Esc && c != Unicode_Null) {
360            // If we didn't end on an Esc or a Null, we consumed the whole identifier
361            return identifier;
362        }
363
364        // An escape sequence was found. Use a StringBuilder to store the decoded CSS identifier.
365        StringBuilder out = StringUtil.borrowBuilder();
366        if (!identifier.isEmpty()) {
367            // Copy the CSS identifier up to the first escape sequence.
368            out.append(identifier);
369        }
370
371        while (!isEmpty()) {
372            c = current();
373            if (isIdent(c)) {
374                out.append(consume());
375            } else if (c == Unicode_Null) {
376                // https://www.w3.org/TR/css-syntax-3/#input-preprocessing
377                advance();
378                out.append(Replacement);
379            } else if (c == Esc) {
380                reader.mark(); // keep the backslash available if newline lookahead reaches a buffer boundary
381                advance();
382                if (!isEmpty() && isNewline(current())) {
383                    // Not a valid escape sequence. This is treated as the end of the CSS identifier.
384                    reader.rewindToMark();
385                    break;
386                } else {
387                    reader.unmark();
388                    consumeCssEscapeSequenceInto(out);
389                }
390            } else {
391                break;
392            }
393        }
394        return StringUtil.releaseBuilder(out);
395    }
396
397    /**
398     Consume a quoted CSS string or an unquoted CSS identifier, resolving escapes and removing surrounding quotes.
399
400     @return the decoded value
401     @throws IllegalArgumentException if a valid value is not at the current position
402     @since 1.24.1
403     */
404    public String consumeCssValue() {
405        if (matches('\'') || matches('"')) return consumeCssString();
406        char first = current();
407        Validate.isTrue(first == Unicode_Null || first == '\\' || first == '-' || first == '_' || Character.isLetter(first) || first >= 0x80,
408            "Attribute value must be a CSS identifier or quoted string");
409        if (first == '-') {
410            reader.mark(); // keep the hyphen available while checking the next character
411            advance();
412            char next = current();
413            boolean valid = !isEmpty() && (next == Unicode_Null || next == '-' || next == '_' || next == Esc || Character.isLetter(next) || next >= 0x80);
414            reader.rewindToMark();
415            Validate.isTrue(valid, "Attribute value must be a CSS identifier or quoted string");
416        }
417        String value = consumeCssIdentifier();
418        Validate.notEmpty(value, "Attribute value expected");
419        return value;
420    }
421
422    /**
423     When {@code extended} is true, consume unquoted text up to unescaped whitespace or the end of input.
424     Resolve CSS escapes, but treat quotes as literal characters. Otherwise, use {@link #consumeCssValue()}.
425
426     @param extended whether to allow unquoted text beyond CSS identifiers
427     @return the decoded value
428     @since 1.24.1
429     */
430    public String consumeCssValue(boolean extended) {
431        if (!extended) return consumeCssValue();
432        StringBuilder out = new StringBuilder();
433        while (!isEmpty() && !matchesWhitespace()) {
434            char c = consume();
435            if (c == Esc) {
436                Validate.isFalse(!isEmpty() && isNewline(current()), "Invalid escape in unquoted attribute value");
437                consumeCssEscapeSequenceInto(out);
438            } else {
439                out.append(c == Unicode_Null ? Replacement : c);
440            }
441        }
442        Validate.isTrue(out.length() != 0, "Attribute value expected");
443        return out.toString();
444    }
445
446    private String consumeCssString() {
447        char quote = consume();
448        Validate.isTrue(quote == '\'' || quote == '"', "CSS string must start with a quote");
449        StringBuilder out = new StringBuilder();
450        while (!isEmpty()) {
451            char c = consume();
452            if (c == quote) return out.toString();
453            if (c == '\\') {
454                if (isEmpty()) break;
455                if (isNewline(current())) {
456                    char newline = consume();
457                    if (newline == '\r' && current() == '\n') advance();
458                } else consumeCssEscapeSequenceInto(out);
459            } else {
460                Validate.isFalse(isNewline(c), "Unescaped newline in CSS string");
461                out.append(c == Unicode_Null ? Replacement : c);
462            }
463        }
464        throw new IllegalArgumentException("Unclosed CSS string");
465    }
466
467    private void consumeCssEscapeSequenceInto(StringBuilder out) {
468        if (isEmpty()) {
469            out.append(Replacement);
470            return;
471        }
472
473        char firstEscaped = consume();
474        if (!StringUtil.isHexDigit(firstEscaped)) {
475            out.append(firstEscaped);
476        } else {
477            reader.unconsume(); // put back the first hex digit
478            String hexString = reader.consumeMatching(StringUtil::isHexDigit, 6); // consume up to 6 hex digits
479            int codePoint;
480            try {
481                codePoint = Integer.parseInt(hexString, 16);
482            } catch (NumberFormatException e) {
483                throw new IllegalArgumentException("Invalid escape sequence: " + hexString, e);
484            }
485            if (isValidCodePoint(codePoint)) {
486                out.appendCodePoint(codePoint);
487            } else {
488                out.append(Replacement);
489            }
490
491            if (!isEmpty()) {
492                char c = current();
493                if (c == '\r') {
494                    // Since there's currently no input preprocessing, check for CRLF here.
495                    // https://www.w3.org/TR/css-syntax-3/#input-preprocessing
496                    advance();
497                    if (!isEmpty() && current() == '\n') advance();
498                } else if (c == ' ' || c == '\t' || isNewline(c)) {
499                    advance();
500                }
501            }
502        }
503    }
504
505    // statics below specifically for CSS identifiers:
506
507    // https://www.w3.org/TR/css-syntax-3/#non-ascii-code-point
508    private static boolean isNonAscii(char c) {
509        return c >= '\u0080';
510    }
511
512    // https://www.w3.org/TR/css-syntax-3/#ident-start-code-point
513    private static boolean isIdentStart(char c) {
514        return c == '_' || StringUtil.isAsciiLetter(c) || isNonAscii(c);
515    }
516
517    // https://www.w3.org/TR/css-syntax-3/#ident-code-point
518    private static boolean isIdent(char c) {
519        return c == Hyphen_Minus || StringUtil.isDigit(c) || isIdentStart(c);
520    }
521
522    // https://www.w3.org/TR/css-syntax-3/#newline
523    // Note: currently there's no preprocessing happening.
524    private static boolean isNewline(char c) {
525        return c == '\n' || c == '\r' || c == '\f';
526    }
527
528    // https://www.w3.org/TR/css-syntax-3/#consume-an-escaped-code-point
529    private static boolean isValidCodePoint(int codePoint) {
530        return codePoint != 0 && Character.isValidCodePoint(codePoint) && !Character.isSurrogate((char) codePoint);
531    }
532
533    private static final char[] CssIdentifierChars = {'-', '_'};
534
535    private String consumeEscapedCssIdentifier(char... matches) {
536        StringBuilder sb = StringUtil.borrowBuilder();
537        while (!isEmpty()) {
538            char c = current();
539            if (c == Esc) {
540                advance();
541                if (!isEmpty()) sb.append(consume());
542                else break;
543            } else if (matchesCssIdentifier(matches)) {
544                sb.append(c);
545                advance();
546            } else {
547                break;
548            }
549        }
550        return StringUtil.releaseBuilder(sb);
551    }
552
553    private boolean matchesCssIdentifier(char... matches) {
554        return matchesWord() || reader.matchesAny(matches);
555    }
556
557    /**
558     Consume and return whatever is left on the queue.
559     @return remainder of queue.
560     */
561    public String remainder() {
562        return reader.consumeToEnd();
563    }
564
565    @Override
566    public String toString() {
567        return reader.toString();
568    }
569
570    @Override
571    public void close() {
572        reader.close(); // releases buffer back to pool
573    }
574}