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