9f9e02876518434926c819ac5fb33b6f8d65e07e
[WebKit-https.git] / JavaScriptCore / yarr / RegexCompiler.cpp
1 /*
2  * Copyright (C) 2009 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "RegexCompiler.h"
28
29 #include "RegexInterpreter.h"
30 #include "RegexPattern.h"
31 #include <wtf/Vector.h>
32
33 #if ENABLE(YARR)
34
35 using namespace WTF;
36
37 namespace JSC { namespace Yarr {
38
39 #include "RegExpJitTables.h"
40
41 class CharacterClassConstructor {
42 public:
43     CharacterClassConstructor(bool isCaseInsensitive = false)
44         : m_isCaseInsensitive(isCaseInsensitive)
45     {
46     }
47     
48     void reset()
49     {
50         m_matches.clear();
51         m_ranges.clear();
52         m_matchesUnicode.clear();
53         m_rangesUnicode.clear();
54     }
55
56     void append(const CharacterClass* other)
57     {
58         for (size_t i = 0; i < other->m_matches.size(); ++i)
59             addSorted(m_matches, other->m_matches[i]);
60         for (size_t i = 0; i < other->m_ranges.size(); ++i)
61             addSortedRange(m_ranges, other->m_ranges[i].begin, other->m_ranges[i].end);
62         for (size_t i = 0; i < other->m_matchesUnicode.size(); ++i)
63             addSorted(m_matchesUnicode, other->m_matchesUnicode[i]);
64         for (size_t i = 0; i < other->m_rangesUnicode.size(); ++i)
65             addSortedRange(m_rangesUnicode, other->m_rangesUnicode[i].begin, other->m_rangesUnicode[i].end);
66     }
67
68     void putChar(UChar ch)
69     {
70         if (ch <= 0x7f) {
71             if (m_isCaseInsensitive && isASCIIAlpha(ch)) {
72                 addSorted(m_matches, toASCIIUpper(ch));
73                 addSorted(m_matches, toASCIILower(ch));
74             } else
75                 addSorted(m_matches, ch);
76         } else {
77             UChar upper, lower;
78             if (m_isCaseInsensitive && ((upper = Unicode::toUpper(ch)) != (lower = Unicode::toLower(ch)))) {
79                 addSorted(m_matchesUnicode, upper);
80                 addSorted(m_matchesUnicode, lower);
81             } else
82                 addSorted(m_matchesUnicode, ch);
83         }
84     }
85
86     // returns true if this character has another case, and 'ch' is the upper case form.
87     static inline bool isUnicodeUpper(UChar ch)
88     {
89         return ch != Unicode::toLower(ch);
90     }
91
92     // returns true if this character has another case, and 'ch' is the lower case form.
93     static inline bool isUnicodeLower(UChar ch)
94     {
95         return ch != Unicode::toUpper(ch);
96     }
97
98     void putRange(UChar lo, UChar hi)
99     {
100         if (lo <= 0x7f) {
101             char asciiLo = lo;
102             char asciiHi = std::min(hi, (UChar)0x7f);
103             addSortedRange(m_ranges, lo, asciiHi);
104             
105             if (m_isCaseInsensitive) {
106                 if ((asciiLo <= 'Z') && (asciiHi >= 'A'))
107                     addSortedRange(m_ranges, std::max(asciiLo, 'A')+('a'-'A'), std::min(asciiHi, 'Z')+('a'-'A'));
108                 if ((asciiLo <= 'z') && (asciiHi >= 'a'))
109                     addSortedRange(m_ranges, std::max(asciiLo, 'a')+('A'-'a'), std::min(asciiHi, 'z')+('A'-'a'));
110             }
111         }
112         if (hi >= 0x80) {
113             uint32_t unicodeCurr = std::max(lo, (UChar)0x80);
114             addSortedRange(m_rangesUnicode, unicodeCurr, hi);
115             
116             if (m_isCaseInsensitive) {
117                 while (unicodeCurr <= hi) {
118                     // If the upper bound of the range (hi) is 0xffff, the increments to
119                     // unicodeCurr in this loop may take it to 0x10000.  This is fine
120                     // (if so we won't re-enter the loop, since the loop condition above
121                     // will definitely fail) - but this does mean we cannot use a UChar
122                     // to represent unicodeCurr, we must use a 32-bit value instead.
123                     ASSERT(unicodeCurr <= 0xffff);
124
125                     if (isUnicodeUpper(unicodeCurr)) {
126                         UChar lowerCaseRangeBegin = Unicode::toLower(unicodeCurr);
127                         UChar lowerCaseRangeEnd = lowerCaseRangeBegin;
128                         while ((++unicodeCurr <= hi) && isUnicodeUpper(unicodeCurr) && (Unicode::toLower(unicodeCurr) == (lowerCaseRangeEnd + 1)))
129                             lowerCaseRangeEnd++;
130                         addSortedRange(m_rangesUnicode, lowerCaseRangeBegin, lowerCaseRangeEnd);
131                     } else if (isUnicodeLower(unicodeCurr)) {
132                         UChar upperCaseRangeBegin = Unicode::toUpper(unicodeCurr);
133                         UChar upperCaseRangeEnd = upperCaseRangeBegin;
134                         while ((++unicodeCurr <= hi) && isUnicodeLower(unicodeCurr) && (Unicode::toUpper(unicodeCurr) == (upperCaseRangeEnd + 1)))
135                             upperCaseRangeEnd++;
136                         addSortedRange(m_rangesUnicode, upperCaseRangeBegin, upperCaseRangeEnd);
137                     } else
138                         ++unicodeCurr;
139                 }
140             }
141         }
142     }
143
144     CharacterClass* charClass()
145     {
146         CharacterClass* characterClass = new CharacterClass(0);
147
148         characterClass->m_matches.append(m_matches);
149         characterClass->m_ranges.append(m_ranges);
150         characterClass->m_matchesUnicode.append(m_matchesUnicode);
151         characterClass->m_rangesUnicode.append(m_rangesUnicode);
152
153         reset();
154
155         return characterClass;
156     }
157
158 private:
159     void addSorted(Vector<UChar>& matches, UChar ch)
160     {
161         unsigned pos = 0;
162         unsigned range = matches.size();
163
164         // binary chop, find position to insert char.
165         while (range) {
166             unsigned index = range >> 1;
167
168             int val = matches[pos+index] - ch;
169             if (!val)
170                 return;
171             else if (val > 0)
172                 range = index;
173             else {
174                 pos += (index+1);
175                 range -= (index+1);
176             }
177         }
178         
179         if (pos == matches.size())
180             matches.append(ch);
181         else
182             matches.insert(pos, ch);
183     }
184
185     void addSortedRange(Vector<CharacterRange>& ranges, UChar lo, UChar hi)
186     {
187         unsigned end = ranges.size();
188         
189         // Simple linear scan - I doubt there are that many ranges anyway...
190         // feel free to fix this with something faster (eg binary chop).
191         for (unsigned i = 0; i < end; ++i) {
192             // does the new range fall before the current position in the array
193             if (hi < ranges[i].begin) {
194                 // optional optimization: concatenate appending ranges? - may not be worthwhile.
195                 if (hi == (ranges[i].begin - 1)) {
196                     ranges[i].begin = lo;
197                     return;
198                 }
199                 ranges.insert(i, CharacterRange(lo, hi));
200                 return;
201             }
202             // Okay, since we didn't hit the last case, the end of the new range is definitely at or after the begining
203             // If the new range start at or before the end of the last range, then the overlap (if it starts one after the
204             // end of the last range they concatenate, which is just as good.
205             if (lo <= (ranges[i].end + 1)) {
206                 // found an intersect! we'll replace this entry in the array.
207                 ranges[i].begin = std::min(ranges[i].begin, lo);
208                 ranges[i].end = std::max(ranges[i].end, hi);
209
210                 // now check if the new range can subsume any subsequent ranges.
211                 unsigned next = i+1;
212                 // each iteration of the loop we will either remove something from the list, or break the loop.
213                 while (next < ranges.size()) {
214                     if (ranges[next].begin <= (ranges[i].end + 1)) {
215                         // the next entry now overlaps / concatenates this one.
216                         ranges[i].end = std::max(ranges[i].end, ranges[next].end);
217                         ranges.remove(next);
218                     } else
219                         break;
220                 }
221                 
222                 return;
223             }
224         }
225
226         // CharacterRange comes after all existing ranges.
227         ranges.append(CharacterRange(lo, hi));
228     }
229
230     bool m_isCaseInsensitive;
231
232     Vector<UChar> m_matches;
233     Vector<CharacterRange> m_ranges;
234     Vector<UChar> m_matchesUnicode;
235     Vector<CharacterRange> m_rangesUnicode;
236 };
237
238 class RegexPatternConstructor {
239 public:
240     RegexPatternConstructor(RegexPattern& pattern)
241         : m_pattern(pattern)
242         , m_characterClassConstructor(pattern.m_ignoreCase)
243         , m_invertParentheticalAssertion(false)
244     {
245     }
246
247     ~RegexPatternConstructor()
248     {
249     }
250
251     void reset()
252     {
253         m_pattern.reset();
254         m_characterClassConstructor.reset();
255     }
256     
257     void assertionBOL()
258     {
259         if (!m_alternative->m_terms.size() & !m_invertParentheticalAssertion) {
260             m_alternative->m_startsWithBOL = true;
261             m_alternative->m_containsBOL = true;
262             m_pattern.m_containsBOL = true;
263         }
264         m_alternative->m_terms.append(PatternTerm::BOL());
265     }
266     void assertionEOL()
267     {
268         m_alternative->m_terms.append(PatternTerm::EOL());
269     }
270     void assertionWordBoundary(bool invert)
271     {
272         m_alternative->m_terms.append(PatternTerm::WordBoundary(invert));
273     }
274
275     void atomPatternCharacter(UChar ch)
276     {
277         // We handle case-insensitive checking of unicode characters which do have both
278         // cases by handling them as if they were defined using a CharacterClass.
279         if (m_pattern.m_ignoreCase && !isASCII(ch) && (Unicode::toUpper(ch) != Unicode::toLower(ch))) {
280             atomCharacterClassBegin();
281             atomCharacterClassAtom(ch);
282             atomCharacterClassEnd();
283         } else
284             m_alternative->m_terms.append(PatternTerm(ch));
285     }
286
287     void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
288     {
289         switch (classID) {
290         case DigitClassID:
291             m_alternative->m_terms.append(PatternTerm(m_pattern.digitsCharacterClass(), invert));
292             break;
293         case SpaceClassID:
294             m_alternative->m_terms.append(PatternTerm(m_pattern.spacesCharacterClass(), invert));
295             break;
296         case WordClassID:
297             m_alternative->m_terms.append(PatternTerm(m_pattern.wordcharCharacterClass(), invert));
298             break;
299         case NewlineClassID:
300             m_alternative->m_terms.append(PatternTerm(m_pattern.newlineCharacterClass(), invert));
301             break;
302         }
303     }
304
305     void atomCharacterClassBegin(bool invert = false)
306     {
307         m_invertCharacterClass = invert;
308     }
309
310     void atomCharacterClassAtom(UChar ch)
311     {
312         m_characterClassConstructor.putChar(ch);
313     }
314
315     void atomCharacterClassRange(UChar begin, UChar end)
316     {
317         m_characterClassConstructor.putRange(begin, end);
318     }
319
320     void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert)
321     {
322         ASSERT(classID != NewlineClassID);
323
324         switch (classID) {
325         case DigitClassID:
326             m_characterClassConstructor.append(invert ? m_pattern.nondigitsCharacterClass() : m_pattern.digitsCharacterClass());
327             break;
328         
329         case SpaceClassID:
330             m_characterClassConstructor.append(invert ? m_pattern.nonspacesCharacterClass() : m_pattern.spacesCharacterClass());
331             break;
332         
333         case WordClassID:
334             m_characterClassConstructor.append(invert ? m_pattern.nonwordcharCharacterClass() : m_pattern.wordcharCharacterClass());
335             break;
336         
337         default:
338             ASSERT_NOT_REACHED();
339         }
340     }
341
342     void atomCharacterClassEnd()
343     {
344         CharacterClass* newCharacterClass = m_characterClassConstructor.charClass();
345         m_pattern.m_userCharacterClasses.append(newCharacterClass);
346         m_alternative->m_terms.append(PatternTerm(newCharacterClass, m_invertCharacterClass));
347     }
348
349     void atomParenthesesSubpatternBegin(bool capture = true)
350     {
351         unsigned subpatternId = m_pattern.m_numSubpatterns + 1;
352         if (capture)
353             m_pattern.m_numSubpatterns++;
354
355         PatternDisjunction* parenthesesDisjunction = new PatternDisjunction(m_alternative);
356         m_pattern.m_disjunctions.append(parenthesesDisjunction);
357         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, capture));
358         m_alternative = parenthesesDisjunction->addNewAlternative();
359     }
360
361     void atomParentheticalAssertionBegin(bool invert = false)
362     {
363         PatternDisjunction* parenthesesDisjunction = new PatternDisjunction(m_alternative);
364         m_pattern.m_disjunctions.append(parenthesesDisjunction);
365         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction, invert));
366         m_alternative = parenthesesDisjunction->addNewAlternative();
367         m_invertParentheticalAssertion = invert;
368     }
369
370     void atomParenthesesEnd()
371     {
372         ASSERT(m_alternative->m_parent);
373         ASSERT(m_alternative->m_parent->m_parent);
374
375         PatternDisjunction* parenthesisDisjunction = m_alternative->m_parent;
376         m_alternative = m_alternative->m_parent->m_parent;
377
378         PatternTerm& lastTerm = m_alternative->lastTerm();
379         
380         unsigned numParenAlternatives = parenthesisDisjunction->m_alternatives.size();
381         unsigned numBOLAnchoredAlts = 0;
382         // Bubble up BOL flags
383         for (unsigned i = 0; i < numParenAlternatives; i++) {
384             if (parenthesisDisjunction->m_alternatives[i]->m_startsWithBOL)
385                 numBOLAnchoredAlts++;
386         }
387         
388         if (numBOLAnchoredAlts) {
389             m_alternative->m_containsBOL = true;
390             // If all the alternatives in parens start with BOL, then so does this one
391             if (numBOLAnchoredAlts == numParenAlternatives)
392                 m_alternative->m_startsWithBOL = true;
393         }
394         
395         lastTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
396         m_invertParentheticalAssertion = false;
397     }
398
399     void atomBackReference(unsigned subpatternId)
400     {
401         ASSERT(subpatternId);
402         m_pattern.m_containsBackreferences = true;
403         m_pattern.m_maxBackReference = std::max(m_pattern.m_maxBackReference, subpatternId);
404
405         if (subpatternId > m_pattern.m_numSubpatterns) {
406             m_alternative->m_terms.append(PatternTerm::ForwardReference());
407             return;
408         }
409
410         PatternAlternative* currentAlternative = m_alternative;
411         ASSERT(currentAlternative);
412
413         // Note to self: if we waited until the AST was baked, we could also remove forwards refs 
414         while ((currentAlternative = currentAlternative->m_parent->m_parent)) {
415             PatternTerm& term = currentAlternative->lastTerm();
416             ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));
417
418             if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.invertOrCapture && (subpatternId == term.subpatternId)) {
419                 m_alternative->m_terms.append(PatternTerm::ForwardReference());
420                 return;
421             }
422         }
423
424         m_alternative->m_terms.append(PatternTerm(subpatternId));
425     }
426
427     // deep copy the argument disjunction.  If filterStartsWithBOL is true, 
428     // skip alternatives with m_startsWithBOL set true.
429     PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction, bool filterStartsWithBOL = false)
430     {
431         PatternDisjunction* newDisjunction = 0;
432         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
433             PatternAlternative* alternative = disjunction->m_alternatives[alt];
434             if (!filterStartsWithBOL || !alternative->m_startsWithBOL) {
435                 if (!newDisjunction) {
436                     newDisjunction = new PatternDisjunction();
437                     newDisjunction->m_parent = disjunction->m_parent;
438                 }
439                 PatternAlternative* newAlternative = newDisjunction->addNewAlternative();
440                 for (unsigned i = 0; i < alternative->m_terms.size(); ++i)
441                     newAlternative->m_terms.append(copyTerm(alternative->m_terms[i], filterStartsWithBOL));
442             }
443         }
444         
445         if (newDisjunction)
446             m_pattern.m_disjunctions.append(newDisjunction);
447         return newDisjunction;
448     }
449     
450     PatternTerm copyTerm(PatternTerm& term, bool filterStartsWithBOL = false)
451     {
452         if ((term.type != PatternTerm::TypeParenthesesSubpattern) && (term.type != PatternTerm::TypeParentheticalAssertion))
453             return PatternTerm(term);
454         
455         PatternTerm termCopy = term;
456         termCopy.parentheses.disjunction = copyDisjunction(termCopy.parentheses.disjunction, filterStartsWithBOL);
457         return termCopy;
458     }
459     
460     void quantifyAtom(unsigned min, unsigned max, bool greedy)
461     {
462         ASSERT(min <= max);
463         ASSERT(m_alternative->m_terms.size());
464
465         if (!max) {
466             m_alternative->removeLastTerm();
467             return;
468         }
469
470         PatternTerm& term = m_alternative->lastTerm();
471         ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);
472         ASSERT((term.quantityCount == 1) && (term.quantityType == QuantifierFixedCount));
473
474         // For any assertion with a zero minimum, not matching is valid and has no effect,
475         // remove it.  Otherwise, we need to match as least once, but there is no point
476         // matching more than once, so remove the quantifier.  It is not entirely clear
477         // from the spec whether or not this behavior is correct, but I believe this
478         // matches Firefox. :-/
479         if (term.type == PatternTerm::TypeParentheticalAssertion) {
480             if (!min)
481                 m_alternative->removeLastTerm();
482             return;
483         }
484
485         if (min == 0)
486             term.quantify(max, greedy   ? QuantifierGreedy : QuantifierNonGreedy);
487         else if (min == max)
488             term.quantify(min, QuantifierFixedCount);
489         else {
490             term.quantify(min, QuantifierFixedCount);
491             m_alternative->m_terms.append(copyTerm(term));
492             // NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....
493             m_alternative->lastTerm().quantify((max == UINT_MAX) ? max : max - min, greedy ? QuantifierGreedy : QuantifierNonGreedy);
494             if (m_alternative->lastTerm().type == PatternTerm::TypeParenthesesSubpattern)
495                 m_alternative->lastTerm().parentheses.isCopy = true;
496         }
497     }
498
499     void disjunction()
500     {
501         m_alternative = m_alternative->m_parent->addNewAlternative();
502     }
503
504     void regexBegin()
505     {
506         m_pattern.m_body = new PatternDisjunction();
507         m_alternative = m_pattern.m_body->addNewAlternative();
508         m_pattern.m_disjunctions.append(m_pattern.m_body);
509     }
510     void regexEnd()
511     {
512     }
513     void regexError()
514     {
515     }
516
517     unsigned setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition)
518     {
519         alternative->m_hasFixedSize = true;
520         unsigned currentInputPosition = initialInputPosition;
521
522         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
523             PatternTerm& term = alternative->m_terms[i];
524
525             switch (term.type) {
526             case PatternTerm::TypeAssertionBOL:
527             case PatternTerm::TypeAssertionEOL:
528             case PatternTerm::TypeAssertionWordBoundary:
529                 term.inputPosition = currentInputPosition;
530                 break;
531
532             case PatternTerm::TypeBackReference:
533                 term.inputPosition = currentInputPosition;
534                 term.frameLocation = currentCallFrameSize;
535                 currentCallFrameSize += RegexStackSpaceForBackTrackInfoBackReference;
536                 alternative->m_hasFixedSize = false;
537                 break;
538
539             case PatternTerm::TypeForwardReference:
540                 break;
541
542             case PatternTerm::TypePatternCharacter:
543                 term.inputPosition = currentInputPosition;
544                 if (term.quantityType != QuantifierFixedCount) {
545                     term.frameLocation = currentCallFrameSize;
546                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoPatternCharacter;
547                     alternative->m_hasFixedSize = false;
548                 } else
549                     currentInputPosition += term.quantityCount;
550                 break;
551
552             case PatternTerm::TypeCharacterClass:
553                 term.inputPosition = currentInputPosition;
554                 if (term.quantityType != QuantifierFixedCount) {
555                     term.frameLocation = currentCallFrameSize;
556                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoCharacterClass;
557                     alternative->m_hasFixedSize = false;
558                 } else
559                     currentInputPosition += term.quantityCount;
560                 break;
561
562             case PatternTerm::TypeParenthesesSubpattern:
563                 // Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
564                 term.frameLocation = currentCallFrameSize;
565                 if ((term.quantityCount == 1) && !term.parentheses.isCopy) {
566                     if (term.quantityType == QuantifierFixedCount) {
567                         currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
568                         currentInputPosition += term.parentheses.disjunction->m_minimumSize;
569                     } else {
570                         currentCallFrameSize += RegexStackSpaceForBackTrackInfoParenthesesOnce;
571                         currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
572                     }
573                     term.inputPosition = currentInputPosition;
574                 } else {
575                     term.inputPosition = currentInputPosition;
576                     setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition);
577                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoParentheses;
578                 }
579                 // Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.
580                 alternative->m_hasFixedSize = false;
581                 break;
582
583             case PatternTerm::TypeParentheticalAssertion:
584                 term.inputPosition = currentInputPosition;
585                 term.frameLocation = currentCallFrameSize;
586                 currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + RegexStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition);
587                 break;
588             }
589         }
590
591         alternative->m_minimumSize = currentInputPosition - initialInputPosition;
592         return currentCallFrameSize;
593     }
594
595     unsigned setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition)
596     {
597         if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
598             initialCallFrameSize += RegexStackSpaceForBackTrackInfoAlternative;
599
600         unsigned minimumInputSize = UINT_MAX;
601         unsigned maximumCallFrameSize = 0;
602         bool hasFixedSize = true;
603
604         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
605             PatternAlternative* alternative = disjunction->m_alternatives[alt];
606             unsigned currentAlternativeCallFrameSize = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition);
607             minimumInputSize = min(minimumInputSize, alternative->m_minimumSize);
608             maximumCallFrameSize = max(maximumCallFrameSize, currentAlternativeCallFrameSize);
609             hasFixedSize &= alternative->m_hasFixedSize;
610         }
611         
612         ASSERT(minimumInputSize != UINT_MAX);
613         ASSERT(maximumCallFrameSize >= initialCallFrameSize);
614
615         disjunction->m_hasFixedSize = hasFixedSize;
616         disjunction->m_minimumSize = minimumInputSize;
617         disjunction->m_callFrameSize = maximumCallFrameSize;
618         return maximumCallFrameSize;
619     }
620
621     void setupOffsets()
622     {
623         setupDisjunctionOffsets(m_pattern.m_body, 0, 0);
624     }
625
626     void optimizeBOL()
627     {
628         // Look for expressions containing beginning of line (^) anchoring and unroll them.
629         // e.g. /^a|^b|c/ becomes /^a|^b|c/ which is executed once followed by /c/ which loops
630         // This code relies on the parsing code tagging alternatives with m_containsBOL and
631         // m_startsWithBOL and rolling those up to containing alternatives.
632         // At this point, this is only valid for non-multiline expressions.
633         PatternDisjunction* disjunction = m_pattern.m_body;
634         
635         if (!m_pattern.m_containsBOL || m_pattern.m_multiline)
636             return;
637         
638         PatternDisjunction* loopDisjunction = copyDisjunction(disjunction, true);
639
640         // Set alternatives in disjunction to "onceThrough"
641         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt)
642             disjunction->m_alternatives[alt]->setOnceThrough();
643
644         if (loopDisjunction) {
645             // Move alternatives from loopDisjunction to disjunction
646             for (unsigned alt = 0; alt < loopDisjunction->m_alternatives.size(); ++alt)
647                 disjunction->m_alternatives.append(loopDisjunction->m_alternatives[alt]);
648                 
649             loopDisjunction->m_alternatives.clear();
650         }
651     }
652     
653     
654 private:
655     RegexPattern& m_pattern;
656     PatternAlternative* m_alternative;
657     CharacterClassConstructor m_characterClassConstructor;
658     bool m_invertCharacterClass;
659     bool m_invertParentheticalAssertion;
660 };
661
662
663 const char* compileRegex(const UString& patternString, RegexPattern& pattern)
664 {
665     RegexPatternConstructor constructor(pattern);
666
667     if (const char* error = parse(constructor, patternString))
668         return error;
669     
670     // If the pattern contains illegal backreferences reset & reparse.
671     // Quoting Netscape's "What's new in JavaScript 1.2",
672     //      "Note: if the number of left parentheses is less than the number specified
673     //       in \#, the \# is taken as an octal escape as described in the next row."
674     if (pattern.containsIllegalBackReference()) {
675         unsigned numSubpatterns = pattern.m_numSubpatterns;
676
677         constructor.reset();
678 #if !ASSERT_DISABLED
679         const char* error =
680 #endif
681             parse(constructor, patternString, numSubpatterns);
682
683         ASSERT(!error);
684         ASSERT(numSubpatterns == pattern.m_numSubpatterns);
685     }
686
687     constructor.optimizeBOL();
688         
689     constructor.setupOffsets();
690
691     return 0;
692 };
693
694
695 } }
696
697 #endif