Rubber stamped by Sam Weinig.
[WebKit-https.git] / Source / JavaScriptCore / yarr / YarrPattern.cpp
1 /*
2  * Copyright (C) 2009 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 "YarrParser.h"
32 #include <wtf/Vector.h>
33
34 using namespace WTF;
35
36 namespace JSC { namespace Yarr {
37
38 #include "RegExpJitTables.h"
39
40 class CharacterClassConstructor {
41 public:
42     CharacterClassConstructor(bool isCaseInsensitive = false)
43         : m_isCaseInsensitive(isCaseInsensitive)
44     {
45     }
46     
47     void reset()
48     {
49         m_matches.clear();
50         m_ranges.clear();
51         m_matchesUnicode.clear();
52         m_rangesUnicode.clear();
53     }
54
55     void append(const CharacterClass* other)
56     {
57         for (size_t i = 0; i < other->m_matches.size(); ++i)
58             addSorted(m_matches, other->m_matches[i]);
59         for (size_t i = 0; i < other->m_ranges.size(); ++i)
60             addSortedRange(m_ranges, other->m_ranges[i].begin, other->m_ranges[i].end);
61         for (size_t i = 0; i < other->m_matchesUnicode.size(); ++i)
62             addSorted(m_matchesUnicode, other->m_matchesUnicode[i]);
63         for (size_t i = 0; i < other->m_rangesUnicode.size(); ++i)
64             addSortedRange(m_rangesUnicode, other->m_rangesUnicode[i].begin, other->m_rangesUnicode[i].end);
65     }
66
67     void putChar(UChar ch)
68     {
69         if (ch <= 0x7f) {
70             if (m_isCaseInsensitive && isASCIIAlpha(ch)) {
71                 addSorted(m_matches, toASCIIUpper(ch));
72                 addSorted(m_matches, toASCIILower(ch));
73             } else
74                 addSorted(m_matches, ch);
75         } else {
76             UChar upper, lower;
77             if (m_isCaseInsensitive && ((upper = Unicode::toUpper(ch)) != (lower = Unicode::toLower(ch)))) {
78                 addSorted(m_matchesUnicode, upper);
79                 addSorted(m_matchesUnicode, lower);
80             } else
81                 addSorted(m_matchesUnicode, ch);
82         }
83     }
84
85     // returns true if this character has another case, and 'ch' is the upper case form.
86     static inline bool isUnicodeUpper(UChar ch)
87     {
88         return ch != Unicode::toLower(ch);
89     }
90
91     // returns true if this character has another case, and 'ch' is the lower case form.
92     static inline bool isUnicodeLower(UChar ch)
93     {
94         return ch != Unicode::toUpper(ch);
95     }
96
97     void putRange(UChar lo, UChar hi)
98     {
99         if (lo <= 0x7f) {
100             char asciiLo = lo;
101             char asciiHi = std::min(hi, (UChar)0x7f);
102             addSortedRange(m_ranges, lo, asciiHi);
103             
104             if (m_isCaseInsensitive) {
105                 if ((asciiLo <= 'Z') && (asciiHi >= 'A'))
106                     addSortedRange(m_ranges, std::max(asciiLo, 'A')+('a'-'A'), std::min(asciiHi, 'Z')+('a'-'A'));
107                 if ((asciiLo <= 'z') && (asciiHi >= 'a'))
108                     addSortedRange(m_ranges, std::max(asciiLo, 'a')+('A'-'a'), std::min(asciiHi, 'z')+('A'-'a'));
109             }
110         }
111         if (hi >= 0x80) {
112             uint32_t unicodeCurr = std::max(lo, (UChar)0x80);
113             addSortedRange(m_rangesUnicode, unicodeCurr, hi);
114             
115             if (m_isCaseInsensitive) {
116                 while (unicodeCurr <= hi) {
117                     // If the upper bound of the range (hi) is 0xffff, the increments to
118                     // unicodeCurr in this loop may take it to 0x10000.  This is fine
119                     // (if so we won't re-enter the loop, since the loop condition above
120                     // will definitely fail) - but this does mean we cannot use a UChar
121                     // to represent unicodeCurr, we must use a 32-bit value instead.
122                     ASSERT(unicodeCurr <= 0xffff);
123
124                     if (isUnicodeUpper(unicodeCurr)) {
125                         UChar lowerCaseRangeBegin = Unicode::toLower(unicodeCurr);
126                         UChar lowerCaseRangeEnd = lowerCaseRangeBegin;
127                         while ((++unicodeCurr <= hi) && isUnicodeUpper(unicodeCurr) && (Unicode::toLower(unicodeCurr) == (lowerCaseRangeEnd + 1)))
128                             lowerCaseRangeEnd++;
129                         addSortedRange(m_rangesUnicode, lowerCaseRangeBegin, lowerCaseRangeEnd);
130                     } else if (isUnicodeLower(unicodeCurr)) {
131                         UChar upperCaseRangeBegin = Unicode::toUpper(unicodeCurr);
132                         UChar upperCaseRangeEnd = upperCaseRangeBegin;
133                         while ((++unicodeCurr <= hi) && isUnicodeLower(unicodeCurr) && (Unicode::toUpper(unicodeCurr) == (upperCaseRangeEnd + 1)))
134                             upperCaseRangeEnd++;
135                         addSortedRange(m_rangesUnicode, upperCaseRangeBegin, upperCaseRangeEnd);
136                     } else
137                         ++unicodeCurr;
138                 }
139             }
140         }
141     }
142
143     CharacterClass* charClass()
144     {
145         CharacterClass* characterClass = new CharacterClass(0);
146
147         characterClass->m_matches.swap(m_matches);
148         characterClass->m_ranges.swap(m_ranges);
149         characterClass->m_matchesUnicode.swap(m_matchesUnicode);
150         characterClass->m_rangesUnicode.swap(m_rangesUnicode);
151
152         return characterClass;
153     }
154
155 private:
156     void addSorted(Vector<UChar>& matches, UChar ch)
157     {
158         unsigned pos = 0;
159         unsigned range = matches.size();
160
161         // binary chop, find position to insert char.
162         while (range) {
163             unsigned index = range >> 1;
164
165             int val = matches[pos+index] - ch;
166             if (!val)
167                 return;
168             else if (val > 0)
169                 range = index;
170             else {
171                 pos += (index+1);
172                 range -= (index+1);
173             }
174         }
175         
176         if (pos == matches.size())
177             matches.append(ch);
178         else
179             matches.insert(pos, ch);
180     }
181
182     void addSortedRange(Vector<CharacterRange>& ranges, UChar lo, UChar hi)
183     {
184         unsigned end = ranges.size();
185         
186         // Simple linear scan - I doubt there are that many ranges anyway...
187         // feel free to fix this with something faster (eg binary chop).
188         for (unsigned i = 0; i < end; ++i) {
189             // does the new range fall before the current position in the array
190             if (hi < ranges[i].begin) {
191                 // optional optimization: concatenate appending ranges? - may not be worthwhile.
192                 if (hi == (ranges[i].begin - 1)) {
193                     ranges[i].begin = lo;
194                     return;
195                 }
196                 ranges.insert(i, CharacterRange(lo, hi));
197                 return;
198             }
199             // Okay, since we didn't hit the last case, the end of the new range is definitely at or after the begining
200             // If the new range start at or before the end of the last range, then the overlap (if it starts one after the
201             // end of the last range they concatenate, which is just as good.
202             if (lo <= (ranges[i].end + 1)) {
203                 // found an intersect! we'll replace this entry in the array.
204                 ranges[i].begin = std::min(ranges[i].begin, lo);
205                 ranges[i].end = std::max(ranges[i].end, hi);
206
207                 // now check if the new range can subsume any subsequent ranges.
208                 unsigned next = i+1;
209                 // each iteration of the loop we will either remove something from the list, or break the loop.
210                 while (next < ranges.size()) {
211                     if (ranges[next].begin <= (ranges[i].end + 1)) {
212                         // the next entry now overlaps / concatenates this one.
213                         ranges[i].end = std::max(ranges[i].end, ranges[next].end);
214                         ranges.remove(next);
215                     } else
216                         break;
217                 }
218                 
219                 return;
220             }
221         }
222
223         // CharacterRange comes after all existing ranges.
224         ranges.append(CharacterRange(lo, hi));
225     }
226
227     bool m_isCaseInsensitive;
228
229     Vector<UChar> m_matches;
230     Vector<CharacterRange> m_ranges;
231     Vector<UChar> m_matchesUnicode;
232     Vector<CharacterRange> m_rangesUnicode;
233 };
234
235 class YarrPatternConstructor {
236 public:
237     YarrPatternConstructor(YarrPattern& pattern)
238         : m_pattern(pattern)
239         , m_characterClassConstructor(pattern.m_ignoreCase)
240         , m_invertParentheticalAssertion(false)
241     {
242         m_pattern.m_body = new PatternDisjunction();
243         m_alternative = m_pattern.m_body->addNewAlternative();
244         m_pattern.m_disjunctions.append(m_pattern.m_body);
245     }
246
247     ~YarrPatternConstructor()
248     {
249     }
250
251     void reset()
252     {
253         m_pattern.reset();
254         m_characterClassConstructor.reset();
255
256         m_pattern.m_body = new PatternDisjunction();
257         m_alternative = m_pattern.m_body->addNewAlternative();
258         m_pattern.m_disjunctions.append(m_pattern.m_body);
259     }
260     
261     void assertionBOL()
262     {
263         if (!m_alternative->m_terms.size() & !m_invertParentheticalAssertion) {
264             m_alternative->m_startsWithBOL = true;
265             m_alternative->m_containsBOL = true;
266             m_pattern.m_containsBOL = true;
267         }
268         m_alternative->m_terms.append(PatternTerm::BOL());
269     }
270     void assertionEOL()
271     {
272         m_alternative->m_terms.append(PatternTerm::EOL());
273     }
274     void assertionWordBoundary(bool invert)
275     {
276         m_alternative->m_terms.append(PatternTerm::WordBoundary(invert));
277     }
278
279     void atomPatternCharacter(UChar ch)
280     {
281         // We handle case-insensitive checking of unicode characters which do have both
282         // cases by handling them as if they were defined using a CharacterClass.
283         if (m_pattern.m_ignoreCase && !isASCII(ch) && (Unicode::toUpper(ch) != Unicode::toLower(ch))) {
284             atomCharacterClassBegin();
285             atomCharacterClassAtom(ch);
286             atomCharacterClassEnd();
287         } else
288             m_alternative->m_terms.append(PatternTerm(ch));
289     }
290
291     void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
292     {
293         switch (classID) {
294         case DigitClassID:
295             m_alternative->m_terms.append(PatternTerm(m_pattern.digitsCharacterClass(), invert));
296             break;
297         case SpaceClassID:
298             m_alternative->m_terms.append(PatternTerm(m_pattern.spacesCharacterClass(), invert));
299             break;
300         case WordClassID:
301             m_alternative->m_terms.append(PatternTerm(m_pattern.wordcharCharacterClass(), invert));
302             break;
303         case NewlineClassID:
304             m_alternative->m_terms.append(PatternTerm(m_pattern.newlineCharacterClass(), invert));
305             break;
306         }
307     }
308
309     void atomCharacterClassBegin(bool invert = false)
310     {
311         m_invertCharacterClass = invert;
312     }
313
314     void atomCharacterClassAtom(UChar ch)
315     {
316         m_characterClassConstructor.putChar(ch);
317     }
318
319     void atomCharacterClassRange(UChar begin, UChar end)
320     {
321         m_characterClassConstructor.putRange(begin, end);
322     }
323
324     void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert)
325     {
326         ASSERT(classID != NewlineClassID);
327
328         switch (classID) {
329         case DigitClassID:
330             m_characterClassConstructor.append(invert ? m_pattern.nondigitsCharacterClass() : m_pattern.digitsCharacterClass());
331             break;
332         
333         case SpaceClassID:
334             m_characterClassConstructor.append(invert ? m_pattern.nonspacesCharacterClass() : m_pattern.spacesCharacterClass());
335             break;
336         
337         case WordClassID:
338             m_characterClassConstructor.append(invert ? m_pattern.nonwordcharCharacterClass() : m_pattern.wordcharCharacterClass());
339             break;
340         
341         default:
342             ASSERT_NOT_REACHED();
343         }
344     }
345
346     void atomCharacterClassEnd()
347     {
348         CharacterClass* newCharacterClass = m_characterClassConstructor.charClass();
349         m_pattern.m_userCharacterClasses.append(newCharacterClass);
350         m_alternative->m_terms.append(PatternTerm(newCharacterClass, m_invertCharacterClass));
351     }
352
353     void atomParenthesesSubpatternBegin(bool capture = true)
354     {
355         unsigned subpatternId = m_pattern.m_numSubpatterns + 1;
356         if (capture)
357             m_pattern.m_numSubpatterns++;
358
359         PatternDisjunction* parenthesesDisjunction = new PatternDisjunction(m_alternative);
360         m_pattern.m_disjunctions.append(parenthesesDisjunction);
361         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, capture, false));
362         m_alternative = parenthesesDisjunction->addNewAlternative();
363     }
364
365     void atomParentheticalAssertionBegin(bool invert = false)
366     {
367         PatternDisjunction* parenthesesDisjunction = new PatternDisjunction(m_alternative);
368         m_pattern.m_disjunctions.append(parenthesesDisjunction);
369         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction, false, invert));
370         m_alternative = parenthesesDisjunction->addNewAlternative();
371         m_invertParentheticalAssertion = invert;
372     }
373
374     void atomParenthesesEnd()
375     {
376         ASSERT(m_alternative->m_parent);
377         ASSERT(m_alternative->m_parent->m_parent);
378
379         PatternDisjunction* parenthesesDisjunction = m_alternative->m_parent;
380         m_alternative = m_alternative->m_parent->m_parent;
381
382         PatternTerm& lastTerm = m_alternative->lastTerm();
383
384         unsigned numParenAlternatives = parenthesesDisjunction->m_alternatives.size();
385         unsigned numBOLAnchoredAlts = 0;
386
387         for (unsigned i = 0; i < numParenAlternatives; i++) {
388             // Bubble up BOL flags
389             if (parenthesesDisjunction->m_alternatives[i]->m_startsWithBOL)
390                 numBOLAnchoredAlts++;
391         }
392
393         if (numBOLAnchoredAlts) {
394             m_alternative->m_containsBOL = true;
395             // If all the alternatives in parens start with BOL, then so does this one
396             if (numBOLAnchoredAlts == numParenAlternatives)
397                 m_alternative->m_startsWithBOL = true;
398         }
399
400         lastTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
401         m_invertParentheticalAssertion = false;
402     }
403
404     void atomBackReference(unsigned subpatternId)
405     {
406         ASSERT(subpatternId);
407         m_pattern.m_containsBackreferences = true;
408         m_pattern.m_maxBackReference = std::max(m_pattern.m_maxBackReference, subpatternId);
409
410         if (subpatternId > m_pattern.m_numSubpatterns) {
411             m_alternative->m_terms.append(PatternTerm::ForwardReference());
412             return;
413         }
414
415         PatternAlternative* currentAlternative = m_alternative;
416         ASSERT(currentAlternative);
417
418         // Note to self: if we waited until the AST was baked, we could also remove forwards refs 
419         while ((currentAlternative = currentAlternative->m_parent->m_parent)) {
420             PatternTerm& term = currentAlternative->lastTerm();
421             ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));
422
423             if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.capture() && (subpatternId == term.parentheses.subpatternId)) {
424                 m_alternative->m_terms.append(PatternTerm::ForwardReference());
425                 return;
426             }
427         }
428
429         m_alternative->m_terms.append(PatternTerm(subpatternId));
430     }
431
432     // deep copy the argument disjunction.  If filterStartsWithBOL is true, 
433     // skip alternatives with m_startsWithBOL set true.
434     PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction, bool filterStartsWithBOL = false)
435     {
436         PatternDisjunction* newDisjunction = 0;
437         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
438             PatternAlternative* alternative = disjunction->m_alternatives[alt];
439             if (!filterStartsWithBOL || !alternative->m_startsWithBOL) {
440                 if (!newDisjunction) {
441                     newDisjunction = new PatternDisjunction();
442                     newDisjunction->m_parent = disjunction->m_parent;
443                 }
444                 PatternAlternative* newAlternative = newDisjunction->addNewAlternative();
445                 for (unsigned i = 0; i < alternative->m_terms.size(); ++i)
446                     newAlternative->m_terms.append(copyTerm(alternative->m_terms[i], filterStartsWithBOL));
447             }
448         }
449         
450         if (newDisjunction)
451             m_pattern.m_disjunctions.append(newDisjunction);
452         return newDisjunction;
453     }
454     
455     PatternTerm copyTerm(PatternTerm& term, bool filterStartsWithBOL = false)
456     {
457         if ((term.type != PatternTerm::TypeParenthesesSubpattern) && (term.type != PatternTerm::TypeParentheticalAssertion))
458             return PatternTerm(term);
459         
460         PatternTerm termCopy = term;
461         termCopy.parentheses.disjunction = copyDisjunction(termCopy.parentheses.disjunction, filterStartsWithBOL);
462         return termCopy;
463     }
464     
465     void quantifyAtom(unsigned min, unsigned max, bool greedy)
466     {
467         ASSERT(min <= max);
468         ASSERT(m_alternative->m_terms.size());
469
470         if (!max) {
471             m_alternative->removeLastTerm();
472             return;
473         }
474
475         PatternTerm& term = m_alternative->lastTerm();
476         ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);
477         ASSERT((term.quantityCount == 1) && (term.quantityType == QuantifierFixedCount));
478
479         if (term.type == PatternTerm::TypeParentheticalAssertion) {
480             // If an assertion is quantified with a minimum count of zero, it can simply be removed.
481             // This arises from the RepeatMatcher behaviour in the spec. Matching an assertion never
482             // results in any input being consumed, however the continuation passed to the assertion
483             // (called in steps, 8c and 9 of the RepeatMatcher definition, ES5.1 15.10.2.5) will
484             // reject all zero length matches (see step 2.1). A match from the continuation of the
485             // expression will still be accepted regardless (via steps 8a and 11) - the upshot of all
486             // this is that matches from the assertion are not required, and won't be accepted anyway,
487             // so no need to ever run it.
488             if (!min)
489                 m_alternative->removeLastTerm();
490             // We never need to run an assertion more than once. Subsequent interations will be run
491             // with the same start index (since assertions are non-capturing) and the same captures
492             // (per step 4 of RepeatMatcher in ES5.1 15.10.2.5), and as such will always produce the
493             // same result and captures. If the first match succeeds then the subsequent (min - 1)
494             // matches will too. Any additional optional matches will fail (on the same basis as the
495             // minimum zero quantified assertions, above), but this will still result in a match.
496             return;
497         }
498
499         if (min == 0)
500             term.quantify(max, greedy   ? QuantifierGreedy : QuantifierNonGreedy);
501         else if (min == max)
502             term.quantify(min, QuantifierFixedCount);
503         else {
504             term.quantify(min, QuantifierFixedCount);
505             m_alternative->m_terms.append(copyTerm(term));
506             // NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....
507             m_alternative->lastTerm().quantify((max == quantifyInfinite) ? max : max - min, greedy ? QuantifierGreedy : QuantifierNonGreedy);
508             if (m_alternative->lastTerm().type == PatternTerm::TypeParenthesesSubpattern)
509                 m_alternative->lastTerm().parentheses.isCopy = true;
510         }
511     }
512
513     void disjunction()
514     {
515         m_alternative = m_alternative->m_parent->addNewAlternative();
516     }
517
518     unsigned setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition)
519     {
520         alternative->m_hasFixedSize = true;
521         Checked<unsigned> currentInputPosition = initialInputPosition;
522
523         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
524             PatternTerm& term = alternative->m_terms[i];
525
526             switch (term.type) {
527             case PatternTerm::TypeAssertionBOL:
528             case PatternTerm::TypeAssertionEOL:
529             case PatternTerm::TypeAssertionWordBoundary:
530                 term.inputPosition = currentInputPosition.unsafeGet();
531                 break;
532
533             case PatternTerm::TypeBackReference:
534                 term.inputPosition = currentInputPosition.unsafeGet();
535                 term.frameLocation = currentCallFrameSize;
536                 currentCallFrameSize += YarrStackSpaceForBackTrackInfoBackReference;
537                 alternative->m_hasFixedSize = false;
538                 break;
539
540             case PatternTerm::TypeForwardReference:
541                 break;
542
543             case PatternTerm::TypePatternCharacter:
544                 term.inputPosition = currentInputPosition.unsafeGet();
545                 if (term.quantityType != QuantifierFixedCount) {
546                     term.frameLocation = currentCallFrameSize;
547                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoPatternCharacter;
548                     alternative->m_hasFixedSize = false;
549                 } else
550                     currentInputPosition += term.quantityCount;
551                 break;
552
553             case PatternTerm::TypeCharacterClass:
554                 term.inputPosition = currentInputPosition.unsafeGet();
555                 if (term.quantityType != QuantifierFixedCount) {
556                     term.frameLocation = currentCallFrameSize;
557                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
558                     alternative->m_hasFixedSize = false;
559                 } else
560                     currentInputPosition += term.quantityCount;
561                 break;
562
563             case PatternTerm::TypeParenthesesSubpattern:
564                 // Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
565                 term.frameLocation = currentCallFrameSize;
566                 if (term.quantityCount == 1 && !term.parentheses.isCopy) {
567                     if (term.quantityType != QuantifierFixedCount)
568                         currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesOnce;
569                     currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet());
570                     // If quantity is fixed, then pre-check its minimum size.
571                     if (term.quantityType == QuantifierFixedCount)
572                         currentInputPosition += term.parentheses.disjunction->m_minimumSize;
573                     term.inputPosition = currentInputPosition.unsafeGet();
574                 } else if (term.parentheses.isTerminal) {
575                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesTerminal;
576                     currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet());
577                     term.inputPosition = currentInputPosition.unsafeGet();
578                 } else {
579                     term.inputPosition = currentInputPosition.unsafeGet();
580                     setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition.unsafeGet());
581                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParentheses;
582                 }
583                 // Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.
584                 alternative->m_hasFixedSize = false;
585                 break;
586
587             case PatternTerm::TypeParentheticalAssertion:
588                 term.inputPosition = currentInputPosition.unsafeGet();
589                 term.frameLocation = currentCallFrameSize;
590                 currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition.unsafeGet());
591                 break;
592
593             case PatternTerm::TypeDotStarEnclosure:
594                 alternative->m_hasFixedSize = false;
595                 term.inputPosition = initialInputPosition;
596                 break;
597             }
598         }
599
600         alternative->m_minimumSize = (currentInputPosition - initialInputPosition).unsafeGet();
601         return currentCallFrameSize;
602     }
603
604     unsigned setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition)
605     {
606         if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
607             initialCallFrameSize += YarrStackSpaceForBackTrackInfoAlternative;
608
609         unsigned minimumInputSize = UINT_MAX;
610         unsigned maximumCallFrameSize = 0;
611         bool hasFixedSize = true;
612
613         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
614             PatternAlternative* alternative = disjunction->m_alternatives[alt];
615             unsigned currentAlternativeCallFrameSize = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition);
616             minimumInputSize = min(minimumInputSize, alternative->m_minimumSize);
617             maximumCallFrameSize = max(maximumCallFrameSize, currentAlternativeCallFrameSize);
618             hasFixedSize &= alternative->m_hasFixedSize;
619         }
620         
621         ASSERT(minimumInputSize != UINT_MAX);
622         ASSERT(maximumCallFrameSize >= initialCallFrameSize);
623
624         disjunction->m_hasFixedSize = hasFixedSize;
625         disjunction->m_minimumSize = minimumInputSize;
626         disjunction->m_callFrameSize = maximumCallFrameSize;
627         return maximumCallFrameSize;
628     }
629
630     void setupOffsets()
631     {
632         setupDisjunctionOffsets(m_pattern.m_body, 0, 0);
633     }
634
635     // This optimization identifies sets of parentheses that we will never need to backtrack.
636     // In these cases we do not need to store state from prior iterations.
637     // We can presently avoid backtracking for:
638     //   * where the parens are at the end of the regular expression (last term in any of the
639     //     alternatives of the main body disjunction).
640     //   * where the parens are non-capturing, and quantified unbounded greedy (*).
641     //   * where the parens do not contain any capturing subpatterns.
642     void checkForTerminalParentheses()
643     {
644         // This check is much too crude; should be just checking whether the candidate
645         // node contains nested capturing subpatterns, not the whole expression!
646         if (m_pattern.m_numSubpatterns)
647             return;
648
649         Vector<PatternAlternative*>& alternatives = m_pattern.m_body->m_alternatives;
650         for (size_t i = 0; i < alternatives.size(); ++i) {
651             Vector<PatternTerm>& terms = alternatives[i]->m_terms;
652             if (terms.size()) {
653                 PatternTerm& term = terms.last();
654                 if (term.type == PatternTerm::TypeParenthesesSubpattern
655                     && term.quantityType == QuantifierGreedy
656                     && term.quantityCount == quantifyInfinite
657                     && !term.capture())
658                     term.parentheses.isTerminal = true;
659             }
660         }
661     }
662
663     void optimizeBOL()
664     {
665         // Look for expressions containing beginning of line (^) anchoring and unroll them.
666         // e.g. /^a|^b|c/ becomes /^a|^b|c/ which is executed once followed by /c/ which loops
667         // This code relies on the parsing code tagging alternatives with m_containsBOL and
668         // m_startsWithBOL and rolling those up to containing alternatives.
669         // At this point, this is only valid for non-multiline expressions.
670         PatternDisjunction* disjunction = m_pattern.m_body;
671         
672         if (!m_pattern.m_containsBOL || m_pattern.m_multiline)
673             return;
674         
675         PatternDisjunction* loopDisjunction = copyDisjunction(disjunction, true);
676
677         // Set alternatives in disjunction to "onceThrough"
678         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt)
679             disjunction->m_alternatives[alt]->setOnceThrough();
680
681         if (loopDisjunction) {
682             // Move alternatives from loopDisjunction to disjunction
683             for (unsigned alt = 0; alt < loopDisjunction->m_alternatives.size(); ++alt)
684                 disjunction->m_alternatives.append(loopDisjunction->m_alternatives[alt]);
685                 
686             loopDisjunction->m_alternatives.clear();
687         }
688     }
689
690     bool containsCapturingTerms(PatternAlternative* alternative, size_t firstTermIndex, size_t lastTermIndex)
691     {
692         Vector<PatternTerm>& terms = alternative->m_terms;
693
694         for (size_t termIndex = firstTermIndex; termIndex <= lastTermIndex; ++termIndex) {
695             PatternTerm& term = terms[termIndex];
696
697             if (term.m_capture)
698                 return true;
699
700             if (term.type == PatternTerm::TypeParenthesesSubpattern) {
701                 PatternDisjunction* nestedDisjunction = term.parentheses.disjunction;
702                 for (unsigned alt = 0; alt < nestedDisjunction->m_alternatives.size(); ++alt) {
703                     if (containsCapturingTerms(nestedDisjunction->m_alternatives[alt], 0, nestedDisjunction->m_alternatives[alt]->m_terms.size() - 1))
704                         return true;
705                 }
706             }
707         }
708
709         return false;
710     }
711
712     // This optimization identifies alternatives in the form of 
713     // [^].*[?]<expression>.*[$] for expressions that don't have any 
714     // capturing terms. The alternative is changed to <expression> 
715     // followed by processing of the dot stars to find and adjust the 
716     // beginning and the end of the match.
717     void optimizeDotStarWrappedExpressions()
718     {
719         Vector<PatternAlternative*>& alternatives = m_pattern.m_body->m_alternatives;
720         if (alternatives.size() != 1)
721             return;
722
723         PatternAlternative* alternative = alternatives[0];
724         Vector<PatternTerm>& terms = alternative->m_terms;
725         if (terms.size() >= 3) {
726             bool startsWithBOL = false;
727             bool endsWithEOL = false;
728             size_t termIndex, firstExpressionTerm, lastExpressionTerm;
729
730             termIndex = 0;
731             if (terms[termIndex].type == PatternTerm::TypeAssertionBOL) {
732                 startsWithBOL = true;
733                 ++termIndex;
734             }
735             
736             PatternTerm& firstNonAnchorTerm = terms[termIndex];
737             if ((firstNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (firstNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || !((firstNonAnchorTerm.quantityType == QuantifierGreedy) || (firstNonAnchorTerm.quantityType == QuantifierNonGreedy)))
738                 return;
739             
740             firstExpressionTerm = termIndex + 1;
741             
742             termIndex = terms.size() - 1;
743             if (terms[termIndex].type == PatternTerm::TypeAssertionEOL) {
744                 endsWithEOL = true;
745                 --termIndex;
746             }
747             
748             PatternTerm& lastNonAnchorTerm = terms[termIndex];
749             if ((lastNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (lastNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || (lastNonAnchorTerm.quantityType != QuantifierGreedy))
750                 return;
751             
752             lastExpressionTerm = termIndex - 1;
753
754             if (firstExpressionTerm > lastExpressionTerm)
755                 return;
756
757             if (!containsCapturingTerms(alternative, firstExpressionTerm, lastExpressionTerm)) {
758                 for (termIndex = terms.size() - 1; termIndex > lastExpressionTerm; --termIndex)
759                     terms.remove(termIndex);
760
761                 for (termIndex = firstExpressionTerm; termIndex > 0; --termIndex)
762                     terms.remove(termIndex - 1);
763
764                 terms.append(PatternTerm(startsWithBOL, endsWithEOL));
765                 
766                 m_pattern.m_containsBOL = false;
767             }
768         }
769     }
770
771 private:
772     YarrPattern& m_pattern;
773     PatternAlternative* m_alternative;
774     CharacterClassConstructor m_characterClassConstructor;
775     bool m_invertCharacterClass;
776     bool m_invertParentheticalAssertion;
777 };
778
779 const char* YarrPattern::compile(const UString& patternString)
780 {
781     YarrPatternConstructor constructor(*this);
782
783     if (const char* error = parse(constructor, patternString))
784         return error;
785     
786     // If the pattern contains illegal backreferences reset & reparse.
787     // Quoting Netscape's "What's new in JavaScript 1.2",
788     //      "Note: if the number of left parentheses is less than the number specified
789     //       in \#, the \# is taken as an octal escape as described in the next row."
790     if (containsIllegalBackReference()) {
791         unsigned numSubpatterns = m_numSubpatterns;
792
793         constructor.reset();
794 #if !ASSERT_DISABLED
795         const char* error =
796 #endif
797             parse(constructor, patternString, numSubpatterns);
798
799         ASSERT(!error);
800         ASSERT(numSubpatterns == m_numSubpatterns);
801     }
802
803     constructor.checkForTerminalParentheses();
804     constructor.optimizeDotStarWrappedExpressions();
805     constructor.optimizeBOL();
806         
807     constructor.setupOffsets();
808
809     return 0;
810 }
811
812 YarrPattern::YarrPattern(const UString& pattern, bool ignoreCase, bool multiline, const char** error)
813     : m_ignoreCase(ignoreCase)
814     , m_multiline(multiline)
815     , m_containsBackreferences(false)
816     , m_containsBOL(false)
817     , m_numSubpatterns(0)
818     , m_maxBackReference(0)
819     , newlineCached(0)
820     , digitsCached(0)
821     , spacesCached(0)
822     , wordcharCached(0)
823     , nondigitsCached(0)
824     , nonspacesCached(0)
825     , nonwordcharCached(0)
826 {
827     *error = compile(pattern);
828 }
829
830 } }