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