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