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