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