WTF::Thread should have the threads stack bounds.
[WebKit-https.git] / Source / JavaScriptCore / yarr / YarrPattern.cpp
1 /*
2  * Copyright (C) 2009, 2013-2016 Apple Inc. All rights reserved.
3  * Copyright (C) 2010 Peter Varga (pvarga@inf.u-szeged.hu), University of Szeged
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
25  */
26
27 #include "config.h"
28 #include "YarrPattern.h"
29
30 #include "Yarr.h"
31 #include "YarrCanonicalize.h"
32 #include "YarrParser.h"
33 #include <wtf/Vector.h>
34 #include <wtf/WTFThreadData.h>
35
36 using namespace WTF;
37
38 namespace JSC { namespace Yarr {
39
40 #include "RegExpJitTables.h"
41
42 class CharacterClassConstructor {
43 public:
44     CharacterClassConstructor(bool isCaseInsensitive, CanonicalMode canonicalMode)
45         : m_isCaseInsensitive(isCaseInsensitive)
46         , m_canonicalMode(canonicalMode)
47     {
48     }
49     
50     void reset()
51     {
52         m_matches.clear();
53         m_ranges.clear();
54         m_matchesUnicode.clear();
55         m_rangesUnicode.clear();
56     }
57
58     void append(const CharacterClass* other)
59     {
60         for (size_t i = 0; i < other->m_matches.size(); ++i)
61             addSorted(m_matches, other->m_matches[i]);
62         for (size_t i = 0; i < other->m_ranges.size(); ++i)
63             addSortedRange(m_ranges, other->m_ranges[i].begin, other->m_ranges[i].end);
64         for (size_t i = 0; i < other->m_matchesUnicode.size(); ++i)
65             addSorted(m_matchesUnicode, other->m_matchesUnicode[i]);
66         for (size_t i = 0; i < other->m_rangesUnicode.size(); ++i)
67             addSortedRange(m_rangesUnicode, other->m_rangesUnicode[i].begin, other->m_rangesUnicode[i].end);
68     }
69
70     void putChar(UChar32 ch)
71     {
72         if (!m_isCaseInsensitive) {
73             addSorted(ch);
74             return;
75         }
76
77         if (m_canonicalMode == CanonicalMode::UCS2 && isASCII(ch)) {
78             // Handle ASCII cases.
79             if (isASCIIAlpha(ch)) {
80                 addSorted(m_matches, toASCIIUpper(ch));
81                 addSorted(m_matches, toASCIILower(ch));
82             } else
83                 addSorted(m_matches, ch);
84             return;
85         }
86
87         // Add multiple matches, if necessary.
88         const CanonicalizationRange* info = canonicalRangeInfoFor(ch, m_canonicalMode);
89         if (info->type == CanonicalizeUnique)
90             addSorted(ch);
91         else
92             putUnicodeIgnoreCase(ch, info);
93     }
94
95     void putUnicodeIgnoreCase(UChar32 ch, const CanonicalizationRange* info)
96     {
97         ASSERT(m_isCaseInsensitive);
98         ASSERT(ch >= info->begin && ch <= info->end);
99         ASSERT(info->type != CanonicalizeUnique);
100         if (info->type == CanonicalizeSet) {
101             for (const UChar32* set = canonicalCharacterSetInfo(info->value, m_canonicalMode); (ch = *set); ++set)
102                 addSorted(ch);
103         } else {
104             addSorted(ch);
105             addSorted(getCanonicalPair(info, ch));
106         }
107     }
108
109     void putRange(UChar32 lo, UChar32 hi)
110     {
111         if (isASCII(lo)) {
112             char asciiLo = lo;
113             char asciiHi = std::min(hi, (UChar32)0x7f);
114             addSortedRange(m_ranges, lo, asciiHi);
115             
116             if (m_isCaseInsensitive) {
117                 if ((asciiLo <= 'Z') && (asciiHi >= 'A'))
118                     addSortedRange(m_ranges, std::max(asciiLo, 'A')+('a'-'A'), std::min(asciiHi, 'Z')+('a'-'A'));
119                 if ((asciiLo <= 'z') && (asciiHi >= 'a'))
120                     addSortedRange(m_ranges, std::max(asciiLo, 'a')+('A'-'a'), std::min(asciiHi, 'z')+('A'-'a'));
121             }
122         }
123         if (isASCII(hi))
124             return;
125
126         lo = std::max(lo, (UChar32)0x80);
127         addSortedRange(m_rangesUnicode, lo, hi);
128         
129         if (!m_isCaseInsensitive)
130             return;
131
132         const CanonicalizationRange* info = canonicalRangeInfoFor(lo, m_canonicalMode);
133         while (true) {
134             // Handle the range [lo .. end]
135             UChar32 end = std::min<UChar32>(info->end, hi);
136
137             switch (info->type) {
138             case CanonicalizeUnique:
139                 // Nothing to do - no canonical equivalents.
140                 break;
141             case CanonicalizeSet: {
142                 UChar ch;
143                 for (const UChar32* set = canonicalCharacterSetInfo(info->value, m_canonicalMode); (ch = *set); ++set)
144                     addSorted(m_matchesUnicode, ch);
145                 break;
146             }
147             case CanonicalizeRangeLo:
148                 addSortedRange(m_rangesUnicode, lo + info->value, end + info->value);
149                 break;
150             case CanonicalizeRangeHi:
151                 addSortedRange(m_rangesUnicode, lo - info->value, end - info->value);
152                 break;
153             case CanonicalizeAlternatingAligned:
154                 // Use addSortedRange since there is likely an abutting range to combine with.
155                 if (lo & 1)
156                     addSortedRange(m_rangesUnicode, lo - 1, lo - 1);
157                 if (!(end & 1))
158                     addSortedRange(m_rangesUnicode, end + 1, end + 1);
159                 break;
160             case CanonicalizeAlternatingUnaligned:
161                 // Use addSortedRange since there is likely an abutting range to combine with.
162                 if (!(lo & 1))
163                     addSortedRange(m_rangesUnicode, lo - 1, lo - 1);
164                 if (end & 1)
165                     addSortedRange(m_rangesUnicode, end + 1, end + 1);
166                 break;
167             }
168
169             if (hi == end)
170                 return;
171
172             ++info;
173             lo = info->begin;
174         };
175
176     }
177
178     std::unique_ptr<CharacterClass> charClass()
179     {
180         auto characterClass = std::make_unique<CharacterClass>();
181
182         characterClass->m_matches.swap(m_matches);
183         characterClass->m_ranges.swap(m_ranges);
184         characterClass->m_matchesUnicode.swap(m_matchesUnicode);
185         characterClass->m_rangesUnicode.swap(m_rangesUnicode);
186
187         return characterClass;
188     }
189
190 private:
191     void addSorted(UChar32 ch)
192     {
193         addSorted(isASCII(ch) ? m_matches : m_matchesUnicode, ch);
194     }
195
196     void addSorted(Vector<UChar32>& matches, UChar32 ch)
197     {
198         unsigned pos = 0;
199         unsigned range = matches.size();
200
201         // binary chop, find position to insert char.
202         while (range) {
203             unsigned index = range >> 1;
204
205             int val = matches[pos+index] - ch;
206             if (!val)
207                 return;
208             else if (val > 0)
209                 range = index;
210             else {
211                 pos += (index+1);
212                 range -= (index+1);
213             }
214         }
215         
216         if (pos == matches.size())
217             matches.append(ch);
218         else
219             matches.insert(pos, ch);
220     }
221
222     void addSortedRange(Vector<CharacterRange>& ranges, UChar32 lo, UChar32 hi)
223     {
224         unsigned end = ranges.size();
225         
226         // Simple linear scan - I doubt there are that many ranges anyway...
227         // feel free to fix this with something faster (eg binary chop).
228         for (unsigned i = 0; i < end; ++i) {
229             // does the new range fall before the current position in the array
230             if (hi < ranges[i].begin) {
231                 // optional optimization: concatenate appending ranges? - may not be worthwhile.
232                 if (hi == (ranges[i].begin - 1)) {
233                     ranges[i].begin = lo;
234                     return;
235                 }
236                 ranges.insert(i, CharacterRange(lo, hi));
237                 return;
238             }
239             // Okay, since we didn't hit the last case, the end of the new range is definitely at or after the begining
240             // If the new range start at or before the end of the last range, then the overlap (if it starts one after the
241             // end of the last range they concatenate, which is just as good.
242             if (lo <= (ranges[i].end + 1)) {
243                 // found an intersect! we'll replace this entry in the array.
244                 ranges[i].begin = std::min(ranges[i].begin, lo);
245                 ranges[i].end = std::max(ranges[i].end, hi);
246
247                 // now check if the new range can subsume any subsequent ranges.
248                 unsigned next = i+1;
249                 // each iteration of the loop we will either remove something from the list, or break the loop.
250                 while (next < ranges.size()) {
251                     if (ranges[next].begin <= (ranges[i].end + 1)) {
252                         // the next entry now overlaps / concatenates this one.
253                         ranges[i].end = std::max(ranges[i].end, ranges[next].end);
254                         ranges.remove(next);
255                     } else
256                         break;
257                 }
258                 
259                 return;
260             }
261         }
262
263         // CharacterRange comes after all existing ranges.
264         ranges.append(CharacterRange(lo, hi));
265     }
266
267     bool m_isCaseInsensitive;
268     CanonicalMode m_canonicalMode;
269
270     Vector<UChar32> m_matches;
271     Vector<CharacterRange> m_ranges;
272     Vector<UChar32> m_matchesUnicode;
273     Vector<CharacterRange> m_rangesUnicode;
274 };
275
276 class YarrPatternConstructor {
277 public:
278     YarrPatternConstructor(YarrPattern& pattern, void* stackLimit)
279         : m_pattern(pattern)
280         , m_characterClassConstructor(pattern.ignoreCase(), pattern.unicode() ? CanonicalMode::Unicode : CanonicalMode::UCS2)
281         , m_stackLimit(stackLimit)
282         , m_invertParentheticalAssertion(false)
283     {
284         auto body = std::make_unique<PatternDisjunction>();
285         m_pattern.m_body = body.get();
286         m_alternative = body->addNewAlternative();
287         m_pattern.m_disjunctions.append(WTFMove(body));
288     }
289
290     ~YarrPatternConstructor()
291     {
292     }
293
294     void reset()
295     {
296         m_pattern.reset();
297         m_characterClassConstructor.reset();
298
299         auto body = std::make_unique<PatternDisjunction>();
300         m_pattern.m_body = body.get();
301         m_alternative = body->addNewAlternative();
302         m_pattern.m_disjunctions.append(WTFMove(body));
303     }
304     
305     void assertionBOL()
306     {
307         if (!m_alternative->m_terms.size() && !m_invertParentheticalAssertion) {
308             m_alternative->m_startsWithBOL = true;
309             m_alternative->m_containsBOL = true;
310             m_pattern.m_containsBOL = true;
311         }
312         m_alternative->m_terms.append(PatternTerm::BOL());
313     }
314     void assertionEOL()
315     {
316         m_alternative->m_terms.append(PatternTerm::EOL());
317     }
318     void assertionWordBoundary(bool invert)
319     {
320         m_alternative->m_terms.append(PatternTerm::WordBoundary(invert));
321     }
322
323     void atomPatternCharacter(UChar32 ch)
324     {
325         // We handle case-insensitive checking of unicode characters which do have both
326         // cases by handling them as if they were defined using a CharacterClass.
327         if (!m_pattern.ignoreCase() || (isASCII(ch) && !m_pattern.unicode())) {
328             m_alternative->m_terms.append(PatternTerm(ch));
329             return;
330         }
331
332         const CanonicalizationRange* info = canonicalRangeInfoFor(ch, m_pattern.unicode() ? CanonicalMode::Unicode : CanonicalMode::UCS2);
333         if (info->type == CanonicalizeUnique) {
334             m_alternative->m_terms.append(PatternTerm(ch));
335             return;
336         }
337
338         m_characterClassConstructor.putUnicodeIgnoreCase(ch, info);
339         auto newCharacterClass = m_characterClassConstructor.charClass();
340         m_alternative->m_terms.append(PatternTerm(newCharacterClass.get(), false));
341         m_pattern.m_userCharacterClasses.append(WTFMove(newCharacterClass));
342     }
343
344     void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
345     {
346         switch (classID) {
347         case DigitClassID:
348             m_alternative->m_terms.append(PatternTerm(m_pattern.digitsCharacterClass(), invert));
349             break;
350         case SpaceClassID:
351             m_alternative->m_terms.append(PatternTerm(m_pattern.spacesCharacterClass(), invert));
352             break;
353         case WordClassID:
354             if (m_pattern.unicode() && m_pattern.ignoreCase())
355                 m_alternative->m_terms.append(PatternTerm(m_pattern.wordUnicodeIgnoreCaseCharCharacterClass(), invert));
356             else
357                 m_alternative->m_terms.append(PatternTerm(m_pattern.wordcharCharacterClass(), invert));
358             break;
359         case NewlineClassID:
360             m_alternative->m_terms.append(PatternTerm(m_pattern.newlineCharacterClass(), invert));
361             break;
362         }
363     }
364
365     void atomCharacterClassBegin(bool invert = false)
366     {
367         m_invertCharacterClass = invert;
368     }
369
370     void atomCharacterClassAtom(UChar32 ch)
371     {
372         m_characterClassConstructor.putChar(ch);
373     }
374
375     void atomCharacterClassRange(UChar32 begin, UChar32 end)
376     {
377         m_characterClassConstructor.putRange(begin, end);
378     }
379
380     void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert)
381     {
382         ASSERT(classID != NewlineClassID);
383
384         switch (classID) {
385         case DigitClassID:
386             m_characterClassConstructor.append(invert ? m_pattern.nondigitsCharacterClass() : m_pattern.digitsCharacterClass());
387             break;
388         
389         case SpaceClassID:
390             m_characterClassConstructor.append(invert ? m_pattern.nonspacesCharacterClass() : m_pattern.spacesCharacterClass());
391             break;
392         
393         case WordClassID:
394             if (m_pattern.unicode() && m_pattern.ignoreCase())
395                 m_characterClassConstructor.append(invert ? m_pattern.nonwordUnicodeIgnoreCaseCharCharacterClass() : m_pattern.wordUnicodeIgnoreCaseCharCharacterClass());
396             else
397                 m_characterClassConstructor.append(invert ? m_pattern.nonwordcharCharacterClass() : m_pattern.wordcharCharacterClass());
398             break;
399         
400         default:
401             RELEASE_ASSERT_NOT_REACHED();
402         }
403     }
404
405     void atomCharacterClassEnd()
406     {
407         auto newCharacterClass = m_characterClassConstructor.charClass();
408         m_alternative->m_terms.append(PatternTerm(newCharacterClass.get(), m_invertCharacterClass));
409         m_pattern.m_userCharacterClasses.append(WTFMove(newCharacterClass));
410     }
411
412     void atomParenthesesSubpatternBegin(bool capture = true)
413     {
414         unsigned subpatternId = m_pattern.m_numSubpatterns + 1;
415         if (capture)
416             m_pattern.m_numSubpatterns++;
417
418         auto parenthesesDisjunction = std::make_unique<PatternDisjunction>(m_alternative);
419         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction.get(), capture, false));
420         m_alternative = parenthesesDisjunction->addNewAlternative();
421         m_pattern.m_disjunctions.append(WTFMove(parenthesesDisjunction));
422     }
423
424     void atomParentheticalAssertionBegin(bool invert = false)
425     {
426         auto parenthesesDisjunction = std::make_unique<PatternDisjunction>(m_alternative);
427         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction.get(), false, invert));
428         m_alternative = parenthesesDisjunction->addNewAlternative();
429         m_invertParentheticalAssertion = invert;
430         m_pattern.m_disjunctions.append(WTFMove(parenthesesDisjunction));
431     }
432
433     void atomParenthesesEnd()
434     {
435         ASSERT(m_alternative->m_parent);
436         ASSERT(m_alternative->m_parent->m_parent);
437
438         PatternDisjunction* parenthesesDisjunction = m_alternative->m_parent;
439         m_alternative = m_alternative->m_parent->m_parent;
440
441         PatternTerm& lastTerm = m_alternative->lastTerm();
442
443         unsigned numParenAlternatives = parenthesesDisjunction->m_alternatives.size();
444         unsigned numBOLAnchoredAlts = 0;
445
446         for (unsigned i = 0; i < numParenAlternatives; i++) {
447             // Bubble up BOL flags
448             if (parenthesesDisjunction->m_alternatives[i]->m_startsWithBOL)
449                 numBOLAnchoredAlts++;
450         }
451
452         if (numBOLAnchoredAlts) {
453             m_alternative->m_containsBOL = true;
454             // If all the alternatives in parens start with BOL, then so does this one
455             if (numBOLAnchoredAlts == numParenAlternatives)
456                 m_alternative->m_startsWithBOL = true;
457         }
458
459         lastTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
460         m_invertParentheticalAssertion = false;
461     }
462
463     void atomBackReference(unsigned subpatternId)
464     {
465         ASSERT(subpatternId);
466         m_pattern.m_containsBackreferences = true;
467         m_pattern.m_maxBackReference = std::max(m_pattern.m_maxBackReference, subpatternId);
468
469         if (subpatternId > m_pattern.m_numSubpatterns) {
470             m_alternative->m_terms.append(PatternTerm::ForwardReference());
471             return;
472         }
473
474         PatternAlternative* currentAlternative = m_alternative;
475         ASSERT(currentAlternative);
476
477         // Note to self: if we waited until the AST was baked, we could also remove forwards refs 
478         while ((currentAlternative = currentAlternative->m_parent->m_parent)) {
479             PatternTerm& term = currentAlternative->lastTerm();
480             ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));
481
482             if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.capture() && (subpatternId == term.parentheses.subpatternId)) {
483                 m_alternative->m_terms.append(PatternTerm::ForwardReference());
484                 return;
485             }
486         }
487
488         m_alternative->m_terms.append(PatternTerm(subpatternId));
489     }
490
491     // deep copy the argument disjunction.  If filterStartsWithBOL is true, 
492     // skip alternatives with m_startsWithBOL set true.
493     PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction, bool filterStartsWithBOL = false)
494     {
495         std::unique_ptr<PatternDisjunction> newDisjunction;
496         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
497             PatternAlternative* alternative = disjunction->m_alternatives[alt].get();
498             if (!filterStartsWithBOL || !alternative->m_startsWithBOL) {
499                 if (!newDisjunction) {
500                     newDisjunction = std::make_unique<PatternDisjunction>();
501                     newDisjunction->m_parent = disjunction->m_parent;
502                 }
503                 PatternAlternative* newAlternative = newDisjunction->addNewAlternative();
504                 newAlternative->m_terms.reserveInitialCapacity(alternative->m_terms.size());
505                 for (unsigned i = 0; i < alternative->m_terms.size(); ++i)
506                     newAlternative->m_terms.append(copyTerm(alternative->m_terms[i], filterStartsWithBOL));
507             }
508         }
509         
510         if (!newDisjunction)
511             return 0;
512
513         PatternDisjunction* copiedDisjunction = newDisjunction.get();
514         m_pattern.m_disjunctions.append(WTFMove(newDisjunction));
515         return copiedDisjunction;
516     }
517     
518     PatternTerm copyTerm(PatternTerm& term, bool filterStartsWithBOL = false)
519     {
520         if ((term.type != PatternTerm::TypeParenthesesSubpattern) && (term.type != PatternTerm::TypeParentheticalAssertion))
521             return PatternTerm(term);
522         
523         PatternTerm termCopy = term;
524         termCopy.parentheses.disjunction = copyDisjunction(termCopy.parentheses.disjunction, filterStartsWithBOL);
525         m_pattern.m_hasCopiedParenSubexpressions = true;
526         return termCopy;
527     }
528     
529     void quantifyAtom(unsigned min, unsigned max, bool greedy)
530     {
531         ASSERT(min <= max);
532         ASSERT(m_alternative->m_terms.size());
533
534         if (!max) {
535             m_alternative->removeLastTerm();
536             return;
537         }
538
539         PatternTerm& term = m_alternative->lastTerm();
540         ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);
541         ASSERT(term.quantityMinCount == 1 && term.quantityMaxCount == 1 && term.quantityType == QuantifierFixedCount);
542
543         if (term.type == PatternTerm::TypeParentheticalAssertion) {
544             // If an assertion is quantified with a minimum count of zero, it can simply be removed.
545             // This arises from the RepeatMatcher behaviour in the spec. Matching an assertion never
546             // results in any input being consumed, however the continuation passed to the assertion
547             // (called in steps, 8c and 9 of the RepeatMatcher definition, ES5.1 15.10.2.5) will
548             // reject all zero length matches (see step 2.1). A match from the continuation of the
549             // expression will still be accepted regardless (via steps 8a and 11) - the upshot of all
550             // this is that matches from the assertion are not required, and won't be accepted anyway,
551             // so no need to ever run it.
552             if (!min)
553                 m_alternative->removeLastTerm();
554             // We never need to run an assertion more than once. Subsequent interations will be run
555             // with the same start index (since assertions are non-capturing) and the same captures
556             // (per step 4 of RepeatMatcher in ES5.1 15.10.2.5), and as such will always produce the
557             // same result and captures. If the first match succeeds then the subsequent (min - 1)
558             // matches will too. Any additional optional matches will fail (on the same basis as the
559             // minimum zero quantified assertions, above), but this will still result in a match.
560             return;
561         }
562
563         if (min == max)
564             term.quantify(min, max, QuantifierFixedCount);
565         else if (!min || (term.type == PatternTerm::TypeParenthesesSubpattern && m_pattern.m_hasCopiedParenSubexpressions))
566             term.quantify(min, max, greedy ? QuantifierGreedy : QuantifierNonGreedy);
567         else {
568             term.quantify(min, min, QuantifierFixedCount);
569             m_alternative->m_terms.append(copyTerm(term));
570             // NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....
571             m_alternative->lastTerm().quantify((max == quantifyInfinite) ? max : max - min, greedy ? QuantifierGreedy : QuantifierNonGreedy);
572             if (m_alternative->lastTerm().type == PatternTerm::TypeParenthesesSubpattern)
573                 m_alternative->lastTerm().parentheses.isCopy = true;
574         }
575     }
576
577     void disjunction()
578     {
579         m_alternative = m_alternative->m_parent->addNewAlternative();
580     }
581
582     YarrPattern::ErrorCode setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition, unsigned& newCallFrameSize) WARN_UNUSED_RETURN
583     {
584         if (UNLIKELY(!isSafeToRecurse()))
585             return YarrPattern::TooManyDisjunctions;
586
587         YarrPattern::ErrorCode error = YarrPattern::NoError;
588         alternative->m_hasFixedSize = true;
589         Checked<unsigned, RecordOverflow> currentInputPosition = initialInputPosition;
590
591         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
592             PatternTerm& term = alternative->m_terms[i];
593
594             switch (term.type) {
595             case PatternTerm::TypeAssertionBOL:
596             case PatternTerm::TypeAssertionEOL:
597             case PatternTerm::TypeAssertionWordBoundary:
598                 term.inputPosition = currentInputPosition.unsafeGet();
599                 break;
600
601             case PatternTerm::TypeBackReference:
602                 term.inputPosition = currentInputPosition.unsafeGet();
603                 term.frameLocation = currentCallFrameSize;
604                 currentCallFrameSize += YarrStackSpaceForBackTrackInfoBackReference;
605                 alternative->m_hasFixedSize = false;
606                 break;
607
608             case PatternTerm::TypeForwardReference:
609                 break;
610
611             case PatternTerm::TypePatternCharacter:
612                 term.inputPosition = currentInputPosition.unsafeGet();
613                 if (term.quantityType != QuantifierFixedCount) {
614                     term.frameLocation = currentCallFrameSize;
615                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoPatternCharacter;
616                     alternative->m_hasFixedSize = false;
617                 } else if (m_pattern.unicode()) {
618                     currentInputPosition += U16_LENGTH(term.patternCharacter) * term.quantityMaxCount;
619                 } else
620                     currentInputPosition += term.quantityMaxCount;
621                 break;
622
623             case PatternTerm::TypeCharacterClass:
624                 term.inputPosition = currentInputPosition.unsafeGet();
625                 if (term.quantityType != QuantifierFixedCount) {
626                     term.frameLocation = currentCallFrameSize;
627                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
628                     alternative->m_hasFixedSize = false;
629                 } else if (m_pattern.unicode()) {
630                     term.frameLocation = currentCallFrameSize;
631                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
632                     currentInputPosition += term.quantityMaxCount;
633                     alternative->m_hasFixedSize = false;
634                 } else
635                     currentInputPosition += term.quantityMaxCount;
636                 break;
637
638             case PatternTerm::TypeParenthesesSubpattern:
639                 // Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
640                 term.frameLocation = currentCallFrameSize;
641                 if (term.quantityMaxCount == 1 && !term.parentheses.isCopy) {
642                     if (term.quantityType != QuantifierFixedCount)
643                         currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesOnce;
644                     error = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet(), currentCallFrameSize);
645                     if (error)
646                         return error;
647                     // If quantity is fixed, then pre-check its minimum size.
648                     if (term.quantityType == QuantifierFixedCount)
649                         currentInputPosition += term.parentheses.disjunction->m_minimumSize;
650                     term.inputPosition = currentInputPosition.unsafeGet();
651                 } else if (term.parentheses.isTerminal) {
652                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesTerminal;
653                     error = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet(), currentCallFrameSize);
654                     if (error)
655                         return error;
656                     term.inputPosition = currentInputPosition.unsafeGet();
657                 } else {
658                     term.inputPosition = currentInputPosition.unsafeGet();
659                     unsigned ignoredCallFrameSize;
660                     error = setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition.unsafeGet(), ignoredCallFrameSize);
661                     if (error)
662                         return error;
663                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParentheses;
664                 }
665                 // Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.
666                 alternative->m_hasFixedSize = false;
667                 break;
668
669             case PatternTerm::TypeParentheticalAssertion:
670                 term.inputPosition = currentInputPosition.unsafeGet();
671                 term.frameLocation = currentCallFrameSize;
672                 error = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition.unsafeGet(), currentCallFrameSize);
673                 if (error)
674                     return error;
675                 break;
676
677             case PatternTerm::TypeDotStarEnclosure:
678                 ASSERT(!m_pattern.m_saveInitialStartValue);
679                 alternative->m_hasFixedSize = false;
680                 term.inputPosition = initialInputPosition;
681                 m_pattern.m_initialStartValueFrameLocation = currentCallFrameSize;
682                 currentCallFrameSize += YarrStackSpaceForDotStarEnclosure;
683                 m_pattern.m_saveInitialStartValue = true;
684                 break;
685             }
686             if (currentInputPosition.hasOverflowed())
687                 return YarrPattern::OffsetTooLarge;
688         }
689
690         alternative->m_minimumSize = (currentInputPosition - initialInputPosition).unsafeGet();
691         newCallFrameSize = currentCallFrameSize;
692         return error;
693     }
694
695     YarrPattern::ErrorCode setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition, unsigned& callFrameSize)
696     {
697         if (UNLIKELY(!isSafeToRecurse()))
698             return YarrPattern::TooManyDisjunctions;
699
700         if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
701             initialCallFrameSize += YarrStackSpaceForBackTrackInfoAlternative;
702
703         unsigned minimumInputSize = UINT_MAX;
704         unsigned maximumCallFrameSize = 0;
705         bool hasFixedSize = true;
706         YarrPattern::ErrorCode error = YarrPattern::NoError;
707
708         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
709             PatternAlternative* alternative = disjunction->m_alternatives[alt].get();
710             unsigned currentAlternativeCallFrameSize;
711             error = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition, currentAlternativeCallFrameSize);
712             if (error)
713                 return error;
714             minimumInputSize = std::min(minimumInputSize, alternative->m_minimumSize);
715             maximumCallFrameSize = std::max(maximumCallFrameSize, currentAlternativeCallFrameSize);
716             hasFixedSize &= alternative->m_hasFixedSize;
717             if (alternative->m_minimumSize > INT_MAX)
718                 m_pattern.m_containsUnsignedLengthPattern = true;
719         }
720         
721         ASSERT(minimumInputSize != UINT_MAX);
722         ASSERT(maximumCallFrameSize >= initialCallFrameSize);
723
724         disjunction->m_hasFixedSize = hasFixedSize;
725         disjunction->m_minimumSize = minimumInputSize;
726         disjunction->m_callFrameSize = maximumCallFrameSize;
727         callFrameSize = maximumCallFrameSize;
728         return error;
729     }
730
731     const char* setupOffsets()
732     {
733         // FIXME: Yarr should not use the stack to handle subpatterns (rdar://problem/26436314).
734         unsigned ignoredCallFrameSize;
735         YarrPattern::ErrorCode error = setupDisjunctionOffsets(m_pattern.m_body, 0, 0, ignoredCallFrameSize);
736         if (error)
737             return YarrPattern::errorMessage(error);
738         return nullptr;
739     }
740
741     // This optimization identifies sets of parentheses that we will never need to backtrack.
742     // In these cases we do not need to store state from prior iterations.
743     // We can presently avoid backtracking for:
744     //   * where the parens are at the end of the regular expression (last term in any of the
745     //     alternatives of the main body disjunction).
746     //   * where the parens are non-capturing, and quantified unbounded greedy (*).
747     //   * where the parens do not contain any capturing subpatterns.
748     void checkForTerminalParentheses()
749     {
750         // This check is much too crude; should be just checking whether the candidate
751         // node contains nested capturing subpatterns, not the whole expression!
752         if (m_pattern.m_numSubpatterns)
753             return;
754
755         Vector<std::unique_ptr<PatternAlternative>>& alternatives = m_pattern.m_body->m_alternatives;
756         for (size_t i = 0; i < alternatives.size(); ++i) {
757             Vector<PatternTerm>& terms = alternatives[i]->m_terms;
758             if (terms.size()) {
759                 PatternTerm& term = terms.last();
760                 if (term.type == PatternTerm::TypeParenthesesSubpattern
761                     && term.quantityType == QuantifierGreedy
762                     && term.quantityMinCount == 0
763                     && term.quantityMaxCount == quantifyInfinite
764                     && !term.capture())
765                     term.parentheses.isTerminal = true;
766             }
767         }
768     }
769
770     void optimizeBOL()
771     {
772         // Look for expressions containing beginning of line (^) anchoring and unroll them.
773         // e.g. /^a|^b|c/ becomes /^a|^b|c/ which is executed once followed by /c/ which loops
774         // This code relies on the parsing code tagging alternatives with m_containsBOL and
775         // m_startsWithBOL and rolling those up to containing alternatives.
776         // At this point, this is only valid for non-multiline expressions.
777         PatternDisjunction* disjunction = m_pattern.m_body;
778         
779         if (!m_pattern.m_containsBOL || m_pattern.multiline())
780             return;
781         
782         PatternDisjunction* loopDisjunction = copyDisjunction(disjunction, true);
783
784         // Set alternatives in disjunction to "onceThrough"
785         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt)
786             disjunction->m_alternatives[alt]->setOnceThrough();
787
788         if (loopDisjunction) {
789             // Move alternatives from loopDisjunction to disjunction
790             for (unsigned alt = 0; alt < loopDisjunction->m_alternatives.size(); ++alt)
791                 disjunction->m_alternatives.append(loopDisjunction->m_alternatives[alt].release());
792                 
793             loopDisjunction->m_alternatives.clear();
794         }
795     }
796
797     bool containsCapturingTerms(PatternAlternative* alternative, size_t firstTermIndex, size_t endIndex)
798     {
799         Vector<PatternTerm>& terms = alternative->m_terms;
800
801         ASSERT(endIndex <= terms.size());
802         for (size_t termIndex = firstTermIndex; termIndex < endIndex; ++termIndex) {
803             PatternTerm& term = terms[termIndex];
804
805             if (term.m_capture)
806                 return true;
807
808             if (term.type == PatternTerm::TypeParenthesesSubpattern) {
809                 PatternDisjunction* nestedDisjunction = term.parentheses.disjunction;
810                 for (unsigned alt = 0; alt < nestedDisjunction->m_alternatives.size(); ++alt) {
811                     if (containsCapturingTerms(nestedDisjunction->m_alternatives[alt].get(), 0, nestedDisjunction->m_alternatives[alt]->m_terms.size()))
812                         return true;
813                 }
814             }
815         }
816
817         return false;
818     }
819
820     // This optimization identifies alternatives in the form of 
821     // [^].*[?]<expression>.*[$] for expressions that don't have any 
822     // capturing terms. The alternative is changed to <expression> 
823     // followed by processing of the dot stars to find and adjust the 
824     // beginning and the end of the match.
825     void optimizeDotStarWrappedExpressions()
826     {
827         Vector<std::unique_ptr<PatternAlternative>>& alternatives = m_pattern.m_body->m_alternatives;
828         if (alternatives.size() != 1)
829             return;
830
831         PatternAlternative* alternative = alternatives[0].get();
832         Vector<PatternTerm>& terms = alternative->m_terms;
833         if (terms.size() >= 3) {
834             bool startsWithBOL = false;
835             bool endsWithEOL = false;
836             size_t termIndex, firstExpressionTerm;
837
838             termIndex = 0;
839             if (terms[termIndex].type == PatternTerm::TypeAssertionBOL) {
840                 startsWithBOL = true;
841                 ++termIndex;
842             }
843             
844             PatternTerm& firstNonAnchorTerm = terms[termIndex];
845             if ((firstNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (firstNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || !((firstNonAnchorTerm.quantityType == QuantifierGreedy) || (firstNonAnchorTerm.quantityType == QuantifierNonGreedy)))
846                 return;
847             
848             firstExpressionTerm = termIndex + 1;
849             
850             termIndex = terms.size() - 1;
851             if (terms[termIndex].type == PatternTerm::TypeAssertionEOL) {
852                 endsWithEOL = true;
853                 --termIndex;
854             }
855             
856             PatternTerm& lastNonAnchorTerm = terms[termIndex];
857             if ((lastNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (lastNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || (lastNonAnchorTerm.quantityType != QuantifierGreedy))
858                 return;
859
860             size_t endIndex = termIndex;
861             if (firstExpressionTerm >= endIndex)
862                 return;
863
864             if (!containsCapturingTerms(alternative, firstExpressionTerm, endIndex)) {
865                 for (termIndex = terms.size() - 1; termIndex >= endIndex; --termIndex)
866                     terms.remove(termIndex);
867
868                 for (termIndex = firstExpressionTerm; termIndex > 0; --termIndex)
869                     terms.remove(termIndex - 1);
870
871                 terms.append(PatternTerm(startsWithBOL, endsWithEOL));
872                 
873                 m_pattern.m_containsBOL = false;
874             }
875         }
876     }
877
878 private:
879     bool isSafeToRecurse() const
880     {
881         if (!m_stackLimit)
882             return true;
883         ASSERT(Thread::current().stack().isGrowingDownward());
884         int8_t* curr = reinterpret_cast<int8_t*>(&curr);
885         int8_t* limit = reinterpret_cast<int8_t*>(m_stackLimit);
886         return curr >= limit;
887     }
888
889     YarrPattern& m_pattern;
890     PatternAlternative* m_alternative;
891     CharacterClassConstructor m_characterClassConstructor;
892     void* m_stackLimit;
893     bool m_invertCharacterClass;
894     bool m_invertParentheticalAssertion;
895 };
896
897 const char* YarrPattern::errorMessage(YarrPattern::ErrorCode error)
898 {
899 #define REGEXP_ERROR_PREFIX "Invalid regular expression: "
900     // The order of this array must match the ErrorCode enum.
901     static const char* errorMessages[NumberOfErrorCodes] = {
902         nullptr,                                                              // NoError
903         REGEXP_ERROR_PREFIX "regular expression too large",                   // PatternTooLarge     
904         REGEXP_ERROR_PREFIX "numbers out of order in {} quantifier",          // QuantifierOutOfOrder
905         REGEXP_ERROR_PREFIX "nothing to repeat",                              // QuantifierWithoutAtom
906         REGEXP_ERROR_PREFIX "number too large in {} quantifier",              // QuantifierTooLarge
907         REGEXP_ERROR_PREFIX "missing )",                                      // MissingParentheses
908         REGEXP_ERROR_PREFIX "unmatched parentheses",                          // ParenthesesUnmatched
909         REGEXP_ERROR_PREFIX "unrecognized character after (?",                // ParenthesesTypeInvalid
910         REGEXP_ERROR_PREFIX "missing terminating ] for character class",      // CharacterClassUnmatched
911         REGEXP_ERROR_PREFIX "range out of order in character class",          // CharacterClassOutOfOrder
912         REGEXP_ERROR_PREFIX "\\ at end of pattern",                           // EscapeUnterminated
913         REGEXP_ERROR_PREFIX "invalid unicode {} escape",                      // InvalidUnicodeEscape
914         REGEXP_ERROR_PREFIX "invalid backreference for unicode pattern",      // InvalidBackreference
915         REGEXP_ERROR_PREFIX "invalid escaped character for unicode pattern",  // InvalidIdentityEscape
916         REGEXP_ERROR_PREFIX "too many nested disjunctions",                   // TooManyDisjunctions
917         REGEXP_ERROR_PREFIX "pattern exceeds string length limits",           // OffsetTooLarge
918         REGEXP_ERROR_PREFIX "invalid flags"                                   // InvalidRegularExpressionFlags
919     };
920
921     return errorMessages[error];
922 }
923
924 const char* YarrPattern::compile(const String& patternString, void* stackLimit)
925 {
926     YarrPatternConstructor constructor(*this, stackLimit);
927
928     if (m_flags == InvalidFlags)
929         return errorMessage(InvalidRegularExpressionFlags);
930
931     if (const char* error = parse(constructor, patternString, unicode()))
932         return error;
933     
934     // If the pattern contains illegal backreferences reset & reparse.
935     // Quoting Netscape's "What's new in JavaScript 1.2",
936     //      "Note: if the number of left parentheses is less than the number specified
937     //       in \#, the \# is taken as an octal escape as described in the next row."
938     if (containsIllegalBackReference()) {
939         if (unicode())
940             return errorMessage(InvalidBackreference);
941
942         unsigned numSubpatterns = m_numSubpatterns;
943
944         constructor.reset();
945 #if !ASSERT_DISABLED
946         const char* error =
947 #endif
948             parse(constructor, patternString, unicode(), numSubpatterns);
949
950         ASSERT(!error);
951         ASSERT(numSubpatterns == m_numSubpatterns);
952     }
953
954     constructor.checkForTerminalParentheses();
955     constructor.optimizeDotStarWrappedExpressions();
956     constructor.optimizeBOL();
957         
958     if (const char* error = constructor.setupOffsets())
959         return error;
960
961     return nullptr;
962 }
963
964 YarrPattern::YarrPattern(const String& pattern, RegExpFlags flags, const char** error, void* stackLimit)
965     : m_containsBackreferences(false)
966     , m_containsBOL(false)
967     , m_containsUnsignedLengthPattern(false)
968     , m_hasCopiedParenSubexpressions(false)
969     , m_saveInitialStartValue(false)
970     , m_flags(flags)
971     , m_numSubpatterns(0)
972     , m_maxBackReference(0)
973     , newlineCached(0)
974     , digitsCached(0)
975     , spacesCached(0)
976     , wordcharCached(0)
977     , wordUnicodeIgnoreCaseCharCached(0)
978     , nondigitsCached(0)
979     , nonspacesCached(0)
980     , nonwordcharCached(0)
981     , nonwordUnicodeIgnoreCasecharCached(0)
982 {
983     *error = compile(pattern, stackLimit);
984 }
985
986 } }