JavaScriptCore:
[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 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();
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
237 CharacterClass* newlineCreate()
238 {
239     CharacterClass* characterClass = new CharacterClass();
240
241     characterClass->m_matches.append('\n');
242     characterClass->m_matches.append('\r');
243     characterClass->m_matchesUnicode.append(0x2028);
244     characterClass->m_matchesUnicode.append(0x2029);
245     
246     return characterClass;
247 }
248
249 CharacterClass* digitsCreate()
250 {
251     CharacterClass* characterClass = new CharacterClass();
252
253     characterClass->m_ranges.append(CharacterRange('0', '9'));
254     
255     return characterClass;
256 }
257
258 CharacterClass* spacesCreate()
259 {
260     CharacterClass* characterClass = new CharacterClass();
261
262     characterClass->m_matches.append(' ');
263     characterClass->m_ranges.append(CharacterRange('\t', '\r'));
264     characterClass->m_matchesUnicode.append(0x00a0);
265     characterClass->m_matchesUnicode.append(0x1680);
266     characterClass->m_matchesUnicode.append(0x180e);
267     characterClass->m_matchesUnicode.append(0x2028);
268     characterClass->m_matchesUnicode.append(0x2029);
269     characterClass->m_matchesUnicode.append(0x202f);
270     characterClass->m_matchesUnicode.append(0x205f);
271     characterClass->m_matchesUnicode.append(0x3000);
272     characterClass->m_rangesUnicode.append(CharacterRange(0x2000, 0x200a));
273     
274     return characterClass;
275 }
276
277 CharacterClass* wordcharCreate()
278 {
279     CharacterClass* characterClass = new CharacterClass();
280
281     characterClass->m_matches.append('_');
282     characterClass->m_ranges.append(CharacterRange('0', '9'));
283     characterClass->m_ranges.append(CharacterRange('A', 'Z'));
284     characterClass->m_ranges.append(CharacterRange('a', 'z'));
285     
286     return characterClass;
287 }
288
289 CharacterClass* nondigitsCreate()
290 {
291     CharacterClass* characterClass = new CharacterClass();
292
293     characterClass->m_ranges.append(CharacterRange(0, '0' - 1));
294     characterClass->m_ranges.append(CharacterRange('9' + 1, 0x7f));
295     characterClass->m_rangesUnicode.append(CharacterRange(0x80, 0xffff));
296     
297     return characterClass;
298 }
299
300 CharacterClass* nonspacesCreate()
301 {
302     CharacterClass* characterClass = new CharacterClass();
303
304     characterClass->m_ranges.append(CharacterRange(0, '\t' - 1));
305     characterClass->m_ranges.append(CharacterRange('\r' + 1, ' ' - 1));
306     characterClass->m_ranges.append(CharacterRange(' ' + 1, 0x7f));
307     characterClass->m_rangesUnicode.append(CharacterRange(0x0080, 0x009f));
308     characterClass->m_rangesUnicode.append(CharacterRange(0x00a1, 0x167f));
309     characterClass->m_rangesUnicode.append(CharacterRange(0x1681, 0x180d));
310     characterClass->m_rangesUnicode.append(CharacterRange(0x180f, 0x1fff));
311     characterClass->m_rangesUnicode.append(CharacterRange(0x200b, 0x2027));
312     characterClass->m_rangesUnicode.append(CharacterRange(0x202a, 0x202e));
313     characterClass->m_rangesUnicode.append(CharacterRange(0x2030, 0x205e));
314     characterClass->m_rangesUnicode.append(CharacterRange(0x2060, 0x2fff));
315     characterClass->m_rangesUnicode.append(CharacterRange(0x3001, 0xffff));
316     
317     return characterClass;
318 }
319
320 CharacterClass* nonwordcharCreate()
321 {
322     CharacterClass* characterClass = new CharacterClass();
323
324     characterClass->m_matches.append('`');
325     characterClass->m_ranges.append(CharacterRange(0, '0' - 1));
326     characterClass->m_ranges.append(CharacterRange('9' + 1, 'A' - 1));
327     characterClass->m_ranges.append(CharacterRange('Z' + 1, '_' - 1));
328     characterClass->m_ranges.append(CharacterRange('z' + 1, 0x7f));
329     characterClass->m_rangesUnicode.append(CharacterRange(0x80, 0xffff));
330
331     return characterClass;
332 }
333
334
335 class RegexPatternConstructor {
336 public:
337     RegexPatternConstructor(RegexPattern& pattern)
338         : m_pattern(pattern)
339         , m_characterClassConstructor(pattern.m_ignoreCase)
340     {
341     }
342
343     ~RegexPatternConstructor()
344     {
345     }
346
347     void reset()
348     {
349         m_pattern.reset();
350         m_characterClassConstructor.reset();
351     }
352     
353     void assertionBOL()
354     {
355         m_alternative->m_terms.append(PatternTerm::BOL());
356     }
357     void assertionEOL()
358     {
359         m_alternative->m_terms.append(PatternTerm::EOL());
360     }
361     void assertionWordBoundary(bool invert)
362     {
363         m_alternative->m_terms.append(PatternTerm::WordBoundary(invert));
364     }
365
366     void atomPatternCharacter(UChar ch)
367     {
368         // We handle case-insensitive checking of unicode characters which do have both
369         // cases by handling them as if they were defined using a CharacterClass.
370         if (m_pattern.m_ignoreCase && !isASCII(ch) && (Unicode::toUpper(ch) != Unicode::toLower(ch))) {
371             atomCharacterClassBegin();
372             atomCharacterClassAtom(ch);
373             atomCharacterClassEnd();
374         } else
375             m_alternative->m_terms.append(PatternTerm(ch));
376     }
377
378     void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
379     {
380         switch (classID) {
381         case DigitClassID:
382             m_alternative->m_terms.append(PatternTerm(m_pattern.digitsCharacterClass(), invert));
383             break;
384         case SpaceClassID:
385             m_alternative->m_terms.append(PatternTerm(m_pattern.spacesCharacterClass(), invert));
386             break;
387         case WordClassID:
388             m_alternative->m_terms.append(PatternTerm(m_pattern.wordcharCharacterClass(), invert));
389             break;
390         case NewlineClassID:
391             m_alternative->m_terms.append(PatternTerm(m_pattern.newlineCharacterClass(), invert));
392             break;
393         }
394     }
395
396     void atomCharacterClassBegin(bool invert = false)
397     {
398         m_invertCharacterClass = invert;
399     }
400
401     void atomCharacterClassAtom(UChar ch)
402     {
403         m_characterClassConstructor.putChar(ch);
404     }
405
406     void atomCharacterClassRange(UChar begin, UChar end)
407     {
408         m_characterClassConstructor.putRange(begin, end);
409     }
410
411     void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert)
412     {
413         ASSERT(classID != NewlineClassID);
414
415         switch (classID) {
416         case DigitClassID:
417             m_characterClassConstructor.append(invert ? m_pattern.nondigitsCharacterClass() : m_pattern.digitsCharacterClass());
418             break;
419         
420         case SpaceClassID:
421             m_characterClassConstructor.append(invert ? m_pattern.nonspacesCharacterClass() : m_pattern.spacesCharacterClass());
422             break;
423         
424         case WordClassID:
425             m_characterClassConstructor.append(invert ? m_pattern.nonwordcharCharacterClass() : m_pattern.wordcharCharacterClass());
426             break;
427         
428         default:
429             ASSERT_NOT_REACHED();
430         }
431     }
432
433     void atomCharacterClassEnd()
434     {
435         CharacterClass* newCharacterClass = m_characterClassConstructor.charClass();
436         m_pattern.m_userCharacterClasses.append(newCharacterClass);
437         m_alternative->m_terms.append(PatternTerm(newCharacterClass, m_invertCharacterClass));
438     }
439
440     void atomParenthesesSubpatternBegin(bool capture = true)
441     {
442         unsigned subpatternId = m_pattern.m_numSubpatterns + 1;
443         if (capture)
444             m_pattern.m_numSubpatterns++;
445
446         PatternDisjunction* parenthesesDisjunction = new PatternDisjunction(m_alternative);
447         m_pattern.m_disjunctions.append(parenthesesDisjunction);
448         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, capture));
449         m_alternative = parenthesesDisjunction->addNewAlternative();
450     }
451
452     void atomParentheticalAssertionBegin(bool invert = false)
453     {
454         PatternDisjunction* parenthesesDisjunction = new PatternDisjunction(m_alternative);
455         m_pattern.m_disjunctions.append(parenthesesDisjunction);
456         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction, invert));
457         m_alternative = parenthesesDisjunction->addNewAlternative();
458     }
459
460     void atomParenthesesEnd()
461     {
462         ASSERT(m_alternative->m_parent);
463         ASSERT(m_alternative->m_parent->m_parent);
464         m_alternative = m_alternative->m_parent->m_parent;
465         
466         m_alternative->lastTerm().parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
467     }
468
469     void atomBackReference(unsigned subpatternId)
470     {
471         ASSERT(subpatternId);
472         m_pattern.m_maxBackReference = std::max(m_pattern.m_maxBackReference, subpatternId);
473
474         if (subpatternId > m_pattern.m_numSubpatterns)
475             return;
476
477         PatternAlternative* currentAlternative = m_alternative;
478         ASSERT(currentAlternative);
479
480         // Note to self: if we waited until the AST was baked, we could also remove forwards refs 
481         while ((currentAlternative = currentAlternative->m_parent->m_parent)) {
482             PatternTerm& term = currentAlternative->lastTerm();
483             ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));
484
485             if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.invertOrCapture && (subpatternId == term.subpatternId))
486                 return;
487         }
488
489         m_alternative->m_terms.append(PatternTerm(subpatternId));
490     }
491
492     PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction)
493     {
494         PatternDisjunction* newDisjunction = new PatternDisjunction();
495
496         newDisjunction->m_parent = disjunction->m_parent;
497         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
498             PatternAlternative* alternative = disjunction->m_alternatives[alt];
499             PatternAlternative* newAlternative = newDisjunction->addNewAlternative();
500             for (unsigned i = 0; i < alternative->m_terms.size(); ++i)
501                 newAlternative->m_terms.append(copyTerm(alternative->m_terms[i]));
502         }
503
504         m_pattern.m_disjunctions.append(newDisjunction);
505         return newDisjunction;
506     }
507
508     PatternTerm copyTerm(PatternTerm& term)
509     {
510         if ((term.type != PatternTerm::TypeParenthesesSubpattern) && (term.type != PatternTerm::TypeParentheticalAssertion))
511             return PatternTerm(term);
512
513         PatternTerm termCopy = term;
514         termCopy.parentheses.disjunction = copyDisjunction(termCopy.parentheses.disjunction);
515         return termCopy;
516     }
517
518     void quantifyAtom(unsigned min, unsigned max, bool greedy)
519     {
520         ASSERT(min <= max);
521         ASSERT(m_alternative->m_terms.size());
522
523         if (!max) {
524             m_alternative->removeLastTerm();
525             return;
526         }
527
528         PatternTerm& term = m_alternative->lastTerm();
529         ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);
530         ASSERT((term.quantityCount == 1) && (term.quantityType == QuantifierFixedCount));
531
532         // For any assertion with a zero minimum, not matching is valid and has no effect,
533         // remove it.  Otherwise, we need to match as least once, but there is no point
534         // matching more than once, so remove the quantifier.  It is not entirely clear
535         // from the spec whether or not this behavior is correct, but I believe this
536         // matches Firefox. :-/
537         if (term.type == PatternTerm::TypeParentheticalAssertion) {
538             if (!min)
539                 m_alternative->removeLastTerm();
540             return;
541         }
542
543         if (min == 0)
544             term.quantify(max, greedy   ? QuantifierGreedy : QuantifierNonGreedy);
545         else if (min == max)
546             term.quantify(min, QuantifierFixedCount);
547         else {
548             term.quantify(min, QuantifierFixedCount);
549             m_alternative->m_terms.append(copyTerm(term));
550             // NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....
551             m_alternative->lastTerm().quantify((max == UINT_MAX) ? max : max - min, greedy ? QuantifierGreedy : QuantifierNonGreedy);
552             if (m_alternative->lastTerm().type == PatternTerm::TypeParenthesesSubpattern)
553                 m_alternative->lastTerm().parentheses.isCopy = true;
554         }
555     }
556
557     void disjunction()
558     {
559         m_alternative = m_alternative->m_parent->addNewAlternative();
560     }
561
562     void regexBegin()
563     {
564         m_pattern.m_body = new PatternDisjunction();
565         m_alternative = m_pattern.m_body->addNewAlternative();
566         m_pattern.m_disjunctions.append(m_pattern.m_body);
567     }
568     void regexEnd()
569     {
570     }
571     void regexError()
572     {
573     }
574
575     unsigned setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition)
576     {
577         alternative->m_hasFixedSize = true;
578         unsigned currentInputPosition = initialInputPosition;
579
580         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
581             PatternTerm& term = alternative->m_terms[i];
582
583             switch (term.type) {
584             case PatternTerm::TypeAssertionBOL:
585             case PatternTerm::TypeAssertionEOL:
586             case PatternTerm::TypeAssertionWordBoundary:
587                 term.inputPosition = currentInputPosition;
588                 break;
589
590             case PatternTerm::TypeBackReference:
591                 term.inputPosition = currentInputPosition;
592                 term.frameLocation = currentCallFrameSize;
593                 currentCallFrameSize += RegexStackSpaceForBackTrackInfoBackReference;
594                 alternative->m_hasFixedSize = false;
595                 break;
596
597             case PatternTerm::TypePatternCharacter:
598                 term.inputPosition = currentInputPosition;
599                 if (term.quantityType != QuantifierFixedCount) {
600                     term.frameLocation = currentCallFrameSize;
601                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoPatternCharacter;
602                     alternative->m_hasFixedSize = false;
603                 } else
604                     currentInputPosition += term.quantityCount;
605                 break;
606
607             case PatternTerm::TypeCharacterClass:
608                 term.inputPosition = currentInputPosition;
609                 if (term.quantityType != QuantifierFixedCount) {
610                     term.frameLocation = currentCallFrameSize;
611                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoCharacterClass;
612                     alternative->m_hasFixedSize = false;
613                 } else
614                     currentInputPosition += term.quantityCount;
615                 break;
616
617             case PatternTerm::TypeParenthesesSubpattern:
618                 // Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
619                 term.frameLocation = currentCallFrameSize;
620                 if ((term.quantityCount == 1) && !term.parentheses.isCopy) {
621                     if (term.quantityType == QuantifierFixedCount) {
622                         currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
623                         currentInputPosition += term.parentheses.disjunction->m_minimumSize;
624                     } else {
625                         currentCallFrameSize += RegexStackSpaceForBackTrackInfoParenthesesOnce;
626                         currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
627                     }
628                     term.inputPosition = currentInputPosition;
629                 } else {
630                     term.inputPosition = currentInputPosition;
631                     setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition);
632                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoParentheses;
633                 }
634                 // Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.
635                 alternative->m_hasFixedSize = false;
636                 break;
637
638             case PatternTerm::TypeParentheticalAssertion:
639                 term.inputPosition = currentInputPosition;
640                 term.frameLocation = currentCallFrameSize;
641                 currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + RegexStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition);
642                 break;
643             }
644         }
645
646         alternative->m_minimumSize = currentInputPosition - initialInputPosition;
647         return currentCallFrameSize;
648     }
649
650     unsigned setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition)
651     {
652         if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
653             initialCallFrameSize += RegexStackSpaceForBackTrackInfoAlternative;
654
655         unsigned minimumInputSize = UINT_MAX;
656         unsigned maximumCallFrameSize = 0;
657         bool hasFixedSize = true;
658
659         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
660             PatternAlternative* alternative = disjunction->m_alternatives[alt];
661             unsigned currentAlternativeCallFrameSize = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition);
662             minimumInputSize = min(minimumInputSize, alternative->m_minimumSize);
663             maximumCallFrameSize = max(maximumCallFrameSize, currentAlternativeCallFrameSize);
664             hasFixedSize &= alternative->m_hasFixedSize;
665         }
666         
667         ASSERT(minimumInputSize != UINT_MAX);
668         ASSERT(maximumCallFrameSize >= initialCallFrameSize);
669
670         disjunction->m_hasFixedSize = hasFixedSize;
671         disjunction->m_minimumSize = minimumInputSize;
672         disjunction->m_callFrameSize = maximumCallFrameSize;
673         return maximumCallFrameSize;
674     }
675
676     void setupOffsets()
677     {
678         setupDisjunctionOffsets(m_pattern.m_body, 0, 0);
679     }
680
681 private:
682     RegexPattern& m_pattern;
683     PatternAlternative* m_alternative;
684     CharacterClassConstructor m_characterClassConstructor;
685     bool m_invertCharacterClass;
686 };
687
688
689 const char* compileRegex(const UString& patternString, RegexPattern& pattern)
690 {
691     RegexPatternConstructor constructor(pattern);
692
693     if (const char* error = parse(constructor, patternString))
694         return error;
695     
696     // If the pattern contains illegal backreferences reset & reparse.
697     // Quoting Netscape's "What's new in JavaScript 1.2",
698     //      "Note: if the number of left parentheses is less than the number specified
699     //       in \#, the \# is taken as an octal escape as described in the next row."
700     if (pattern.containsIllegalBackReference()) {
701         unsigned numSubpatterns = pattern.m_numSubpatterns;
702
703         constructor.reset();
704 #ifndef NDEBUG
705         const char* error =
706 #endif
707             parse(constructor, patternString, numSubpatterns);
708
709         ASSERT(!error);
710         ASSERT(numSubpatterns == pattern.m_numSubpatterns);
711     }
712
713     constructor.setupOffsets();
714
715     return false;
716 };
717
718
719 } }
720
721 #endif