378609d97e62189e5a999901333c73d9d9895e87
[WebKit-https.git] / Source / JavaScriptCore / yarr / YarrParser.h
1 /*
2  * Copyright (C) 2009-2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #pragma once
27
28 #include "Yarr.h"
29 #include "YarrPattern.h"
30 #include <wtf/ASCIICType.h>
31 #include <wtf/HashSet.h>
32 #include <wtf/Optional.h>
33 #include <wtf/text/StringBuilder.h>
34 #include <wtf/text/WTFString.h>
35
36 namespace JSC { namespace Yarr {
37
38 enum BuiltInCharacterClassID {
39     DigitClassID,
40     SpaceClassID,
41     WordClassID,
42     DotClassID,
43 };
44
45 // The Parser class should not be used directly - only via the Yarr::parse() method.
46 template<class Delegate, typename CharType>
47 class Parser {
48 private:
49     template<class FriendDelegate>
50     friend const char* parse(FriendDelegate&, const String& pattern, bool isUnicode, unsigned backReferenceLimit);
51
52     /*
53      * CharacterClassParserDelegate:
54      *
55      * The class CharacterClassParserDelegate is used in the parsing of character
56      * classes.  This class handles detection of character ranges.  This class
57      * implements enough of the delegate interface such that it can be passed to
58      * parseEscape() as an EscapeDelegate.  This allows parseEscape() to be reused
59      * to perform the parsing of escape characters in character sets.
60      */
61     class CharacterClassParserDelegate {
62     public:
63         CharacterClassParserDelegate(Delegate& delegate, YarrPattern::ErrorCode& err)
64             : m_delegate(delegate)
65             , m_err(err)
66             , m_state(Empty)
67             , m_character(0)
68         {
69         }
70
71         /*
72          * begin():
73          *
74          * Called at beginning of construction.
75          */
76         void begin(bool invert)
77         {
78             m_delegate.atomCharacterClassBegin(invert);
79         }
80
81         /*
82          * atomPatternCharacter():
83          *
84          * This method is called either from parseCharacterClass() (for an unescaped
85          * character in a character class), or from parseEscape(). In the former case
86          * the value true will be passed for the argument 'hyphenIsRange', and in this
87          * mode we will allow a hypen to be treated as indicating a range (i.e. /[a-z]/
88          * is different to /[a\-z]/).
89          */
90         void atomPatternCharacter(UChar32 ch, bool hyphenIsRange = false)
91         {
92             switch (m_state) {
93             case AfterCharacterClass:
94                 // Following a builtin character class we need look out for a hyphen.
95                 // We're looking for invalid ranges, such as /[\d-x]/ or /[\d-\d]/.
96                 // If we see a hyphen following a charater class then unlike usual
97                 // we'll report it to the delegate immediately, and put ourself into
98                 // a poisoned state. Any following calls to add another character or
99                 // character class will result in an error. (A hypen following a
100                 // character-class is itself valid, but only  at the end of a regex).
101                 if (hyphenIsRange && ch == '-') {
102                     m_delegate.atomCharacterClassAtom('-');
103                     m_state = AfterCharacterClassHyphen;
104                     return;
105                 }
106                 // Otherwise just fall through - cached character so treat this as Empty.
107                 FALLTHROUGH;
108
109             case Empty:
110                 m_character = ch;
111                 m_state = CachedCharacter;
112                 return;
113
114             case CachedCharacter:
115                 if (hyphenIsRange && ch == '-')
116                     m_state = CachedCharacterHyphen;
117                 else {
118                     m_delegate.atomCharacterClassAtom(m_character);
119                     m_character = ch;
120                 }
121                 return;
122
123             case CachedCharacterHyphen:
124                 if (ch < m_character) {
125                     m_err = YarrPattern::CharacterClassOutOfOrder;
126                     return;
127                 }
128                 m_delegate.atomCharacterClassRange(m_character, ch);
129                 m_state = Empty;
130                 return;
131
132                 // See coment in atomBuiltInCharacterClass below.
133                 // This too is technically an error, per ECMA-262, and again we
134                 // we chose to allow this.  Note a subtlely here that while we
135                 // diverge from the spec's definition of CharacterRange we do
136                 // remain in compliance with the grammar.  For example, consider
137                 // the expression /[\d-a-z]/.  We comply with the grammar in
138                 // this case by not allowing a-z to be matched as a range.
139             case AfterCharacterClassHyphen:
140                 m_delegate.atomCharacterClassAtom(ch);
141                 m_state = Empty;
142                 return;
143             }
144         }
145
146         /*
147          * atomBuiltInCharacterClass():
148          *
149          * Adds a built-in character class, called by parseEscape().
150          */
151         void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
152         {
153             switch (m_state) {
154             case CachedCharacter:
155                 // Flush the currently cached character, then fall through.
156                 m_delegate.atomCharacterClassAtom(m_character);
157                 FALLTHROUGH;
158             case Empty:
159             case AfterCharacterClass:
160                 m_state = AfterCharacterClass;
161                 m_delegate.atomCharacterClassBuiltIn(classID, invert);
162                 return;
163
164                 // If we hit either of these cases, we have an invalid range that
165                 // looks something like /[x-\d]/ or /[\d-\d]/.
166                 // According to ECMA-262 this should be a syntax error, but
167                 // empirical testing shows this to break teh webz.  Instead we
168                 // comply with to the ECMA-262 grammar, and assume the grammar to
169                 // have matched the range correctly, but tweak our interpretation
170                 // of CharacterRange.  Effectively we implicitly handle the hyphen
171                 // as if it were escaped, e.g. /[\w-_]/ is treated as /[\w\-_]/.
172             case CachedCharacterHyphen:
173                 m_delegate.atomCharacterClassAtom(m_character);
174                 m_delegate.atomCharacterClassAtom('-');
175                 FALLTHROUGH;
176             case AfterCharacterClassHyphen:
177                 m_delegate.atomCharacterClassBuiltIn(classID, invert);
178                 m_state = Empty;
179                 return;
180             }
181         }
182
183         /*
184          * end():
185          *
186          * Called at end of construction.
187          */
188         void end()
189         {
190             if (m_state == CachedCharacter)
191                 m_delegate.atomCharacterClassAtom(m_character);
192             else if (m_state == CachedCharacterHyphen) {
193                 m_delegate.atomCharacterClassAtom(m_character);
194                 m_delegate.atomCharacterClassAtom('-');
195             }
196             m_delegate.atomCharacterClassEnd();
197         }
198
199         // parseEscape() should never call these delegate methods when
200         // invoked with inCharacterClass set.
201         NO_RETURN_DUE_TO_ASSERT void assertionWordBoundary(bool) { RELEASE_ASSERT_NOT_REACHED(); }
202         NO_RETURN_DUE_TO_ASSERT void atomBackReference(unsigned) { RELEASE_ASSERT_NOT_REACHED(); }
203         NO_RETURN_DUE_TO_ASSERT void atomNamedBackReference(String) { RELEASE_ASSERT_NOT_REACHED(); }
204
205     private:
206         Delegate& m_delegate;
207         YarrPattern::ErrorCode& m_err;
208         enum CharacterClassConstructionState {
209             Empty,
210             CachedCharacter,
211             CachedCharacterHyphen,
212             AfterCharacterClass,
213             AfterCharacterClassHyphen,
214         } m_state;
215         UChar32 m_character;
216     };
217
218     Parser(Delegate& delegate, const String& pattern, bool isUnicode, unsigned backReferenceLimit)
219         : m_delegate(delegate)
220         , m_backReferenceLimit(backReferenceLimit)
221         , m_err(YarrPattern::NoError)
222         , m_data(pattern.characters<CharType>())
223         , m_size(pattern.length())
224         , m_index(0)
225         , m_isUnicode(isUnicode)
226         , m_parenthesesNestingDepth(0)
227     {
228     }
229
230     // The handling of IdentityEscapes is different depending on the unicode flag.
231     // For Unicode patterns, IdentityEscapes only include SyntaxCharacters or '/'.
232     // For non-unicode patterns, most any character can be escaped.
233     bool isIdentityEscapeAnError(int ch)
234     {
235         if (m_isUnicode && !strchr("^$\\.*+?()[]{}|/", ch)) {
236             m_err = YarrPattern::InvalidIdentityEscape;
237             return true;
238         }
239
240         return false;
241     }
242
243     /*
244      * parseEscape():
245      *
246      * Helper for parseTokens() AND parseCharacterClass().
247      * Unlike the other parser methods, this function does not report tokens
248      * directly to the member delegate (m_delegate), instead tokens are
249      * emitted to the delegate provided as an argument.  In the case of atom
250      * escapes, parseTokens() will call parseEscape() passing m_delegate as
251      * an argument, and as such the escape will be reported to the delegate.
252      *
253      * However this method may also be used by parseCharacterClass(), in which
254      * case a CharacterClassParserDelegate will be passed as the delegate that
255      * tokens should be added to.  A boolean flag is also provided to indicate
256      * whether that an escape in a CharacterClass is being parsed (some parsing
257      * rules change in this context).
258      *
259      * The boolean value returned by this method indicates whether the token
260      * parsed was an atom (outside of a characted class \b and \B will be
261      * interpreted as assertions).
262      */
263     template<bool inCharacterClass, class EscapeDelegate>
264     bool parseEscape(EscapeDelegate& delegate)
265     {
266         ASSERT(!m_err);
267         ASSERT(peek() == '\\');
268         consume();
269
270         if (atEndOfPattern()) {
271             m_err = YarrPattern::EscapeUnterminated;
272             return false;
273         }
274
275         switch (peek()) {
276         // Assertions
277         case 'b':
278             consume();
279             if (inCharacterClass) {
280                 if (isIdentityEscapeAnError('b'))
281                     break;
282
283                 delegate.atomPatternCharacter('\b');
284             } else {
285                 delegate.assertionWordBoundary(false);
286                 return false;
287             }
288             break;
289         case 'B':
290             consume();
291             if (inCharacterClass) {
292                 if (isIdentityEscapeAnError('B'))
293                     break;
294
295                 delegate.atomPatternCharacter('B');
296             } else {
297                 delegate.assertionWordBoundary(true);
298                 return false;
299             }
300             break;
301
302         // CharacterClassEscape
303         case 'd':
304             consume();
305             delegate.atomBuiltInCharacterClass(DigitClassID, false);
306             break;
307         case 's':
308             consume();
309             delegate.atomBuiltInCharacterClass(SpaceClassID, false);
310             break;
311         case 'w':
312             consume();
313             delegate.atomBuiltInCharacterClass(WordClassID, false);
314             break;
315         case 'D':
316             consume();
317             delegate.atomBuiltInCharacterClass(DigitClassID, true);
318             break;
319         case 'S':
320             consume();
321             delegate.atomBuiltInCharacterClass(SpaceClassID, true);
322             break;
323         case 'W':
324             consume();
325             delegate.atomBuiltInCharacterClass(WordClassID, true);
326             break;
327
328         // DecimalEscape
329         case '1':
330         case '2':
331         case '3':
332         case '4':
333         case '5':
334         case '6':
335         case '7':
336         case '8':
337         case '9': {
338             // To match Firefox, we parse an invalid backreference in the range [1-7] as an octal escape.
339             // First, try to parse this as backreference.
340             if (!inCharacterClass) {
341                 ParseState state = saveState();
342
343                 unsigned backReference = consumeNumber();
344                 if (backReference <= m_backReferenceLimit) {
345                     delegate.atomBackReference(backReference);
346                     break;
347                 }
348
349                 restoreState(state);
350
351                 if (m_isUnicode) {
352                     m_err = YarrPattern::InvalidBackreference;
353                     return false;
354                 }
355             }
356
357             // Not a backreference, and not octal. Just a number.
358             if (peek() >= '8') {
359                 delegate.atomPatternCharacter(consume());
360                 break;
361             }
362
363             // Fall-through to handle this as an octal escape.
364             FALLTHROUGH;
365         }
366
367         // Octal escape
368         case '0':
369             delegate.atomPatternCharacter(consumeOctal());
370             break;
371
372         // ControlEscape
373         case 'f':
374             consume();
375             delegate.atomPatternCharacter('\f');
376             break;
377         case 'n':
378             consume();
379             delegate.atomPatternCharacter('\n');
380             break;
381         case 'r':
382             consume();
383             delegate.atomPatternCharacter('\r');
384             break;
385         case 't':
386             consume();
387             delegate.atomPatternCharacter('\t');
388             break;
389         case 'v':
390             consume();
391             delegate.atomPatternCharacter('\v');
392             break;
393
394         // ControlLetter
395         case 'c': {
396             ParseState state = saveState();
397             consume();
398             if (!atEndOfPattern()) {
399                 int control = consume();
400
401                 // To match Firefox, inside a character class, we also accept numbers and '_' as control characters.
402                 if (inCharacterClass ? WTF::isASCIIAlphanumeric(control) || (control == '_') : WTF::isASCIIAlpha(control)) {
403                     delegate.atomPatternCharacter(control & 0x1f);
404                     break;
405                 }
406             }
407             restoreState(state);
408             delegate.atomPatternCharacter('\\');
409             break;
410         }
411
412         // HexEscape
413         case 'x': {
414             consume();
415             int x = tryConsumeHex(2);
416             if (x == -1) {
417                 if (isIdentityEscapeAnError('x'))
418                     break;
419
420                 delegate.atomPatternCharacter('x');
421             } else
422                 delegate.atomPatternCharacter(x);
423             break;
424         }
425
426         // Named backreference
427         case 'k': {
428             consume();
429             ParseState state = saveState();
430             if (!atEndOfPattern() && !inCharacterClass) {
431                 if (consume() == '<') {
432                     auto groupName = tryConsumeGroupName();
433                     if (groupName && m_captureGroupNames.contains(groupName.value())) {
434                         delegate.atomNamedBackReference(groupName.value());
435                         break;
436                     }
437                     if (m_isUnicode) {
438                         m_err = YarrPattern::InvalidBackreference;
439                         break;
440                     }
441                 }
442             }
443             restoreState(state);
444             delegate.atomPatternCharacter('k');
445             break;
446         }
447
448         // UnicodeEscape
449         case 'u': {
450             consume();
451             if (atEndOfPattern()) {
452                 if (isIdentityEscapeAnError('u'))
453                     break;
454
455                 delegate.atomPatternCharacter('u');
456                 break;
457             }
458
459             if (m_isUnicode && peek() == '{') {
460                 consume();
461                 UChar32 codePoint = 0;
462                 do {
463                     if (atEndOfPattern() || !isASCIIHexDigit(peek())) {
464                         m_err = YarrPattern::InvalidUnicodeEscape;
465                         break;
466                     }
467
468                     codePoint = (codePoint << 4) | toASCIIHexValue(consume());
469
470                     if (codePoint > UCHAR_MAX_VALUE)
471                         m_err = YarrPattern::InvalidUnicodeEscape;
472                 } while (!atEndOfPattern() && peek() != '}');
473                 if (!atEndOfPattern() && peek() == '}')
474                     consume();
475                 else if (!m_err)
476                     m_err = YarrPattern::InvalidUnicodeEscape;
477                 if (m_err)
478                     return false;
479
480                 delegate.atomPatternCharacter(codePoint);
481                 break;
482             }
483             int u = tryConsumeHex(4);
484             if (u == -1) {
485                 if (isIdentityEscapeAnError('u'))
486                     break;
487
488                 delegate.atomPatternCharacter('u');
489             } else {
490                 // If we have the first of a surrogate pair, look for the second.
491                 if (U16_IS_LEAD(u) && m_isUnicode && (patternRemaining() >= 6) && peek() == '\\') {
492                     ParseState state = saveState();
493                     consume();
494                     
495                     if (tryConsume('u')) {
496                         int surrogate2 = tryConsumeHex(4);
497                         if (U16_IS_TRAIL(surrogate2)) {
498                             u = U16_GET_SUPPLEMENTARY(u, surrogate2);
499                             delegate.atomPatternCharacter(u);
500                             break;
501                         }
502                     }
503
504                     restoreState(state);
505                 }
506                 delegate.atomPatternCharacter(u);
507             }
508             break;
509         }
510
511         // IdentityEscape
512         default:
513             int ch = peek();
514
515             if (ch == '-' && m_isUnicode && inCharacterClass) {
516                 // \- is allowed for ClassEscape with unicode flag.
517                 delegate.atomPatternCharacter(consume());
518                 break;
519             }
520
521             if (isIdentityEscapeAnError(ch))
522                 break;
523
524             delegate.atomPatternCharacter(consume());
525         }
526         
527         return true;
528     }
529
530     UChar32 consumePossibleSurrogatePair()
531     {
532         UChar32 ch = consume();
533         if (U16_IS_LEAD(ch) && m_isUnicode && (patternRemaining() > 0)) {
534             ParseState state = saveState();
535
536             UChar32 surrogate2 = consume();
537             if (U16_IS_TRAIL(surrogate2))
538                 ch = U16_GET_SUPPLEMENTARY(ch, surrogate2);
539             else
540                 restoreState(state);
541         }
542
543         return ch;
544     }
545
546     /*
547      * parseAtomEscape(), parseCharacterClassEscape():
548      *
549      * These methods alias to parseEscape().
550      */
551     bool parseAtomEscape()
552     {
553         return parseEscape<false>(m_delegate);
554     }
555     void parseCharacterClassEscape(CharacterClassParserDelegate& delegate)
556     {
557         parseEscape<true>(delegate);
558     }
559
560     /*
561      * parseCharacterClass():
562      *
563      * Helper for parseTokens(); calls dirctly and indirectly (via parseCharacterClassEscape)
564      * to an instance of CharacterClassParserDelegate, to describe the character class to the
565      * delegate.
566      */
567     void parseCharacterClass()
568     {
569         ASSERT(!m_err);
570         ASSERT(peek() == '[');
571         consume();
572
573         CharacterClassParserDelegate characterClassConstructor(m_delegate, m_err);
574
575         characterClassConstructor.begin(tryConsume('^'));
576
577         while (!atEndOfPattern()) {
578             switch (peek()) {
579             case ']':
580                 consume();
581                 characterClassConstructor.end();
582                 return;
583
584             case '\\':
585                 parseCharacterClassEscape(characterClassConstructor);
586                 break;
587
588             default:
589                 characterClassConstructor.atomPatternCharacter(consumePossibleSurrogatePair(), true);
590             }
591
592             if (m_err)
593                 return;
594         }
595
596         m_err = YarrPattern::CharacterClassUnmatched;
597     }
598
599     /*
600      * parseParenthesesBegin():
601      *
602      * Helper for parseTokens(); checks for parentheses types other than regular capturing subpatterns.
603      */
604     void parseParenthesesBegin()
605     {
606         ASSERT(!m_err);
607         ASSERT(peek() == '(');
608         consume();
609
610         if (tryConsume('?')) {
611             if (atEndOfPattern()) {
612                 m_err = YarrPattern::ParenthesesTypeInvalid;
613                 return;
614             }
615
616             switch (consume()) {
617             case ':':
618                 m_delegate.atomParenthesesSubpatternBegin(false);
619                 break;
620             
621             case '=':
622                 m_delegate.atomParentheticalAssertionBegin();
623                 break;
624
625             case '!':
626                 m_delegate.atomParentheticalAssertionBegin(true);
627                 break;
628
629             case '<': {
630                 auto groupName = tryConsumeGroupName();
631                 if (groupName) {
632                     auto setAddResult = m_captureGroupNames.add(groupName.value());
633                     if (setAddResult.isNewEntry)
634                         m_delegate.atomParenthesesSubpatternBegin(true, groupName);
635                     else
636                         m_err = YarrPattern::DuplicateGroupName;
637                 } else
638                     m_err = YarrPattern::InvalidGroupName;
639
640                 break;
641             }
642
643             default:
644                 m_err = YarrPattern::ParenthesesTypeInvalid;
645             }
646         } else
647             m_delegate.atomParenthesesSubpatternBegin();
648
649         ++m_parenthesesNestingDepth;
650     }
651
652     /*
653      * parseParenthesesEnd():
654      *
655      * Helper for parseTokens(); checks for parse errors (due to unmatched parentheses).
656      */
657     void parseParenthesesEnd()
658     {
659         ASSERT(!m_err);
660         ASSERT(peek() == ')');
661         consume();
662
663         if (m_parenthesesNestingDepth > 0)
664             m_delegate.atomParenthesesEnd();
665         else
666             m_err = YarrPattern::ParenthesesUnmatched;
667
668         --m_parenthesesNestingDepth;
669     }
670
671     /*
672      * parseQuantifier():
673      *
674      * Helper for parseTokens(); checks for parse errors and non-greedy quantifiers.
675      */
676     void parseQuantifier(bool lastTokenWasAnAtom, unsigned min, unsigned max)
677     {
678         ASSERT(!m_err);
679         ASSERT(min <= max);
680
681         if (min == UINT_MAX) {
682             m_err = YarrPattern::QuantifierTooLarge;
683             return;
684         }
685
686         if (lastTokenWasAnAtom)
687             m_delegate.quantifyAtom(min, max, !tryConsume('?'));
688         else
689             m_err = YarrPattern::QuantifierWithoutAtom;
690     }
691
692     /*
693      * parseTokens():
694      *
695      * This method loops over the input pattern reporting tokens to the delegate.
696      * The method returns when a parse error is detected, or the end of the pattern
697      * is reached.  One piece of state is tracked around the loop, which is whether
698      * the last token passed to the delegate was an atom (this is necessary to detect
699      * a parse error when a quantifier provided without an atom to quantify).
700      */
701     void parseTokens()
702     {
703         bool lastTokenWasAnAtom = false;
704
705         while (!atEndOfPattern()) {
706             switch (peek()) {
707             case '|':
708                 consume();
709                 m_delegate.disjunction();
710                 lastTokenWasAnAtom = false;
711                 break;
712
713             case '(':
714                 parseParenthesesBegin();
715                 lastTokenWasAnAtom = false;
716                 break;
717
718             case ')':
719                 parseParenthesesEnd();
720                 lastTokenWasAnAtom = true;
721                 break;
722
723             case '^':
724                 consume();
725                 m_delegate.assertionBOL();
726                 lastTokenWasAnAtom = false;
727                 break;
728
729             case '$':
730                 consume();
731                 m_delegate.assertionEOL();
732                 lastTokenWasAnAtom = false;
733                 break;
734
735             case '.':
736                 consume();
737                 m_delegate.atomBuiltInCharacterClass(DotClassID, false);
738                 lastTokenWasAnAtom = true;
739                 break;
740
741             case '[':
742                 parseCharacterClass();
743                 lastTokenWasAnAtom = true;
744                 break;
745
746             case '\\':
747                 lastTokenWasAnAtom = parseAtomEscape();
748                 break;
749
750             case '*':
751                 consume();
752                 parseQuantifier(lastTokenWasAnAtom, 0, quantifyInfinite);
753                 lastTokenWasAnAtom = false;
754                 break;
755
756             case '+':
757                 consume();
758                 parseQuantifier(lastTokenWasAnAtom, 1, quantifyInfinite);
759                 lastTokenWasAnAtom = false;
760                 break;
761
762             case '?':
763                 consume();
764                 parseQuantifier(lastTokenWasAnAtom, 0, 1);
765                 lastTokenWasAnAtom = false;
766                 break;
767
768             case '{': {
769                 ParseState state = saveState();
770
771                 consume();
772                 if (peekIsDigit()) {
773                     unsigned min = consumeNumber();
774                     unsigned max = min;
775                     
776                     if (tryConsume(','))
777                         max = peekIsDigit() ? consumeNumber() : quantifyInfinite;
778
779                     if (tryConsume('}')) {
780                         if (min <= max)
781                             parseQuantifier(lastTokenWasAnAtom, min, max);
782                         else
783                             m_err = YarrPattern::QuantifierOutOfOrder;
784                         lastTokenWasAnAtom = false;
785                         break;
786                     }
787                 }
788
789                 restoreState(state);
790             }
791             // if we did not find a complete quantifer, fall through to the default case.
792             FALLTHROUGH;
793
794             default:
795                 m_delegate.atomPatternCharacter(consumePossibleSurrogatePair());
796                 lastTokenWasAnAtom = true;
797             }
798
799             if (m_err)
800                 return;
801         }
802
803         if (m_parenthesesNestingDepth > 0)
804             m_err = YarrPattern::MissingParentheses;
805     }
806
807     /*
808      * parse():
809      *
810      * This method calls parseTokens() to parse over the input and converts any
811      * error code to a const char* for a result.
812      */
813     const char* parse()
814     {
815         if (m_size > MAX_PATTERN_SIZE)
816             m_err = YarrPattern::PatternTooLarge;
817         else
818             parseTokens();
819         ASSERT(atEndOfPattern() || m_err);
820         
821         return YarrPattern::errorMessage(m_err);
822     }
823
824     // Misc helper functions:
825
826     typedef unsigned ParseState;
827     
828     ParseState saveState()
829     {
830         return m_index;
831     }
832
833     void restoreState(ParseState state)
834     {
835         m_index = state;
836     }
837
838     bool atEndOfPattern()
839     {
840         ASSERT(m_index <= m_size);
841         return m_index == m_size;
842     }
843
844     unsigned patternRemaining()
845     {
846         ASSERT(m_index <= m_size);
847         return m_size - m_index;
848     }
849
850     int peek()
851     {
852         ASSERT(m_index < m_size);
853         return m_data[m_index];
854     }
855
856     bool peekIsDigit()
857     {
858         return !atEndOfPattern() && WTF::isASCIIDigit(peek());
859     }
860
861     unsigned peekDigit()
862     {
863         ASSERT(peekIsDigit());
864         return peek() - '0';
865     }
866
867     int tryConsumeUnicodeEscape()
868     {
869         if (!tryConsume('u'))
870             return -1;
871
872         if (m_isUnicode && tryConsume('{')) {
873             int codePoint = 0;
874             do {
875                 if (atEndOfPattern() || !isASCIIHexDigit(peek())) {
876                     m_err = YarrPattern::InvalidUnicodeEscape;
877                     return -1;
878                 }
879
880                 codePoint = (codePoint << 4) | toASCIIHexValue(consume());
881
882                 if (codePoint > UCHAR_MAX_VALUE) {
883                     m_err = YarrPattern::InvalidUnicodeEscape;
884                     return -1;
885                 }
886             } while (!atEndOfPattern() && peek() != '}');
887             if (!atEndOfPattern() && peek() == '}')
888                 consume();
889             else if (!m_err)
890                 m_err = YarrPattern::InvalidUnicodeEscape;
891             if (m_err)
892                 return -1;
893
894             return codePoint;
895         }
896
897         int u = tryConsumeHex(4);
898         if (u == -1)
899             return -1;
900
901         // If we have the first of a surrogate pair, look for the second.
902         if (U16_IS_LEAD(u) && m_isUnicode && (patternRemaining() >= 6) && peek() == '\\') {
903             ParseState state = saveState();
904             consume();
905
906             if (tryConsume('u')) {
907                 int surrogate2 = tryConsumeHex(4);
908                 if (U16_IS_TRAIL(surrogate2)) {
909                     u = U16_GET_SUPPLEMENTARY(u, surrogate2);
910                     return u;
911                 }
912             }
913
914             restoreState(state);
915         }
916
917         return u;
918     }
919
920     int tryConsumeIdentifierCharacter()
921     {
922         int ch = peek();
923
924         if (ch == '\\') {
925             consume();
926             ch = tryConsumeUnicodeEscape();
927         } else
928             consume();
929
930         return ch;
931     }
932
933     bool isIdentifierStart(int ch)
934     {
935         return (WTF::isASCII(ch) && (WTF::isASCIIAlpha(ch) || ch == '_' || ch == '$')) || (U_GET_GC_MASK(ch) & U_GC_L_MASK);
936     }
937
938     bool isIdentifierPart(int ch)
939     {
940         return (WTF::isASCII(ch) && (WTF::isASCIIAlpha(ch) || ch == '_' || ch == '$')) || (U_GET_GC_MASK(ch) & (U_GC_L_MASK | U_GC_MN_MASK | U_GC_MC_MASK | U_GC_ND_MASK | U_GC_PC_MASK)) || ch == 0x200C || ch == 0x200D;
941     }
942
943     int consume()
944     {
945         ASSERT(m_index < m_size);
946         return m_data[m_index++];
947     }
948
949     unsigned consumeDigit()
950     {
951         ASSERT(peekIsDigit());
952         return consume() - '0';
953     }
954
955     unsigned consumeNumber()
956     {
957         unsigned n = consumeDigit();
958         // check for overflow.
959         for (unsigned newValue; peekIsDigit() && ((newValue = n * 10 + peekDigit()) >= n); ) {
960             n = newValue;
961             consume();
962         }
963         return n;
964     }
965
966     unsigned consumeOctal()
967     {
968         ASSERT(WTF::isASCIIOctalDigit(peek()));
969
970         unsigned n = consumeDigit();
971         while (n < 32 && !atEndOfPattern() && WTF::isASCIIOctalDigit(peek()))
972             n = n * 8 + consumeDigit();
973         return n;
974     }
975
976     bool tryConsume(UChar ch)
977     {
978         if (atEndOfPattern() || (m_data[m_index] != ch))
979             return false;
980         ++m_index;
981         return true;
982     }
983
984     int tryConsumeHex(int count)
985     {
986         ParseState state = saveState();
987
988         int n = 0;
989         while (count--) {
990             if (atEndOfPattern() || !WTF::isASCIIHexDigit(peek())) {
991                 restoreState(state);
992                 return -1;
993             }
994             n = (n << 4) | WTF::toASCIIHexValue(consume());
995         }
996         return n;
997     }
998
999     std::optional<String> tryConsumeGroupName()
1000     {
1001         ParseState state = saveState();
1002         StringBuilder identifierBuilder;
1003
1004         while (!atEndOfPattern()) {
1005             int ch = tryConsumeIdentifierCharacter();
1006             if (ch == '>') {
1007                 if (identifierBuilder.length())
1008                     return std::optional<String>(identifierBuilder.toString());
1009                 break;
1010             }
1011             if (!isIdentifierPart(ch))
1012                 break;
1013
1014             identifierBuilder.append(ch);
1015         }
1016
1017         restoreState(state);
1018
1019         return std::nullopt;
1020     }
1021
1022     Delegate& m_delegate;
1023     unsigned m_backReferenceLimit;
1024     YarrPattern::ErrorCode m_err;
1025     const CharType* m_data;
1026     unsigned m_size;
1027     unsigned m_index;
1028     bool m_isUnicode;
1029     unsigned m_parenthesesNestingDepth;
1030     HashSet<String> m_captureGroupNames;
1031
1032     // Derived by empirical testing of compile time in PCRE and WREC.
1033     static const unsigned MAX_PATTERN_SIZE = 1024 * 1024;
1034 };
1035
1036 /*
1037  * Yarr::parse():
1038  *
1039  * The parse method is passed a pattern to be parsed and a delegate upon which
1040  * callbacks will be made to record the parsed tokens forming the regex.
1041  * Yarr::parse() returns null on success, or a const C string providing an error
1042  * message where a parse error occurs.
1043  *
1044  * The Delegate must implement the following interface:
1045  *
1046  *    void assertionBOL();
1047  *    void assertionEOL();
1048  *    void assertionWordBoundary(bool invert);
1049  *
1050  *    void atomPatternCharacter(UChar32 ch);
1051  *    void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert);
1052  *    void atomCharacterClassBegin(bool invert)
1053  *    void atomCharacterClassAtom(UChar32 ch)
1054  *    void atomCharacterClassRange(UChar32 begin, UChar32 end)
1055  *    void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert)
1056  *    void atomCharacterClassEnd()
1057  *    void atomParenthesesSubpatternBegin(bool capture = true, std::optional<String> groupName);
1058  *    void atomParentheticalAssertionBegin(bool invert = false);
1059  *    void atomParenthesesEnd();
1060  *    void atomBackReference(unsigned subpatternId);
1061  *    void atomNamedBackReference(String subpatternName);
1062  *
1063  *    void quantifyAtom(unsigned min, unsigned max, bool greedy);
1064  *
1065  *    void disjunction();
1066  *
1067  * The regular expression is described by a sequence of assertion*() and atom*()
1068  * callbacks to the delegate, describing the terms in the regular expression.
1069  * Following an atom a quantifyAtom() call may occur to indicate that the previous
1070  * atom should be quantified.  In the case of atoms described across multiple
1071  * calls (parentheses and character classes) the call to quantifyAtom() will come
1072  * after the call to the atom*End() method, never after atom*Begin().
1073  *
1074  * Character classes may either be described by a single call to
1075  * atomBuiltInCharacterClass(), or by a sequence of atomCharacterClass*() calls.
1076  * In the latter case, ...Begin() will be called, followed by a sequence of
1077  * calls to ...Atom(), ...Range(), and ...BuiltIn(), followed by a call to ...End().
1078  *
1079  * Sequences of atoms and assertions are broken into alternatives via calls to
1080  * disjunction().  Assertions, atoms, and disjunctions emitted between calls to
1081  * atomParenthesesBegin() and atomParenthesesEnd() form the body of a subpattern.
1082  * atomParenthesesBegin() is passed a subpatternId.  In the case of a regular
1083  * capturing subpattern, this will be the subpatternId associated with these
1084  * parentheses, and will also by definition be the lowest subpatternId of these
1085  * parentheses and of any nested paretheses.  The atomParenthesesEnd() method
1086  * is passed the subpatternId of the last capturing subexpression nested within
1087  * these paretheses.  In the case of a capturing subpattern with no nested
1088  * capturing subpatterns, the same subpatternId will be passed to the begin and
1089  * end functions.  In the case of non-capturing subpatterns the subpatternId
1090  * passed to the begin method is also the first possible subpatternId that might
1091  * be nested within these paretheses.  If a set of non-capturing parentheses does
1092  * not contain any capturing subpatterns, then the subpatternId passed to begin
1093  * will be greater than the subpatternId passed to end.
1094  */
1095
1096 template<class Delegate>
1097 const char* parse(Delegate& delegate, const String& pattern, bool isUnicode, unsigned backReferenceLimit = quantifyInfinite)
1098 {
1099     if (pattern.is8Bit())
1100         return Parser<Delegate, LChar>(delegate, pattern, isUnicode, backReferenceLimit).parse();
1101     return Parser<Delegate, UChar>(delegate, pattern, isUnicode, backReferenceLimit).parse();
1102 }
1103
1104 } } // namespace JSC::Yarr