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             m_alternative->m_terms.append(PatternTerm::ForwardReference());
 476             return;
 477         }
 478
 479         PatternAlternative* currentAlternative = m_alternative;
 480         ASSERT(currentAlternative);
 481
 482         // Note to self: if we waited until the AST was baked, we could also remove forwards refs
 483         while ((currentAlternative = currentAlternative->m_parent->m_parent)) {
 484             PatternTerm& term = currentAlternative->lastTerm();
 485             ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));
 486
 487             if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.invertOrCapture && (subpatternId == term.subpatternId)) {
 488                 m_alternative->m_terms.append(PatternTerm::ForwardReference());
 489                 return;
 490             }
 491         }
 492
 493         m_alternative->m_terms.append(PatternTerm(subpatternId));
 494     }
 495
 496     PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction)
 497     {
 498         PatternDisjunction* newDisjunction = new PatternDisjunction();
 499
 500         newDisjunction->m_parent = disjunction->m_parent;
 501         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
 502             PatternAlternative* alternative = disjunction->m_alternatives[alt];
 503             PatternAlternative* newAlternative = newDisjunction->addNewAlternative();
 504             for (unsigned i = 0; i < alternative->m_terms.size(); ++i)
 505                 newAlternative->m_terms.append(copyTerm(alternative->m_terms[i]));
 506         }
 507
 508         m_pattern.m_disjunctions.append(newDisjunction);
 509         return newDisjunction;
 510     }
 511
 512     PatternTerm copyTerm(PatternTerm& term)
 513     {
 514         if ((term.type != PatternTerm::TypeParenthesesSubpattern) && (term.type != PatternTerm::TypeParentheticalAssertion))
 515             return PatternTerm(term);
 516
 517         PatternTerm termCopy = term;
 518         termCopy.parentheses.disjunction = copyDisjunction(termCopy.parentheses.disjunction);
 519         return termCopy;
 520     }
 521
 522     void quantifyAtom(unsigned min, unsigned max, bool greedy)
 523     {
 524         ASSERT(min <= max);
 525         ASSERT(m_alternative->m_terms.size());
 526
 527         if (!max) {
 528             m_alternative->removeLastTerm();
 529             return;
 530         }
 531
 532         PatternTerm& term = m_alternative->lastTerm();
 533         ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);
 534         ASSERT((term.quantityCount == 1) && (term.quantityType == QuantifierFixedCount));
 535
 536         // For any assertion with a zero minimum, not matching is valid and has no effect,
 537         // remove it.  Otherwise, we need to match as least once, but there is no point
 538         // matching more than once, so remove the quantifier.  It is not entirely clear
 539         // from the spec whether or not this behavior is correct, but I believe this
 540         // matches Firefox. :-/
 541         if (term.type == PatternTerm::TypeParentheticalAssertion) {
 542             if (!min)
 543                 m_alternative->removeLastTerm();
 544             return;
 545         }
 546
 547         if (min == 0)
 548             term.quantify(max, greedy   ? QuantifierGreedy : QuantifierNonGreedy);
 549         else if (min == max)
 550             term.quantify(min, QuantifierFixedCount);
 551         else {
 552             term.quantify(min, QuantifierFixedCount);
 553             m_alternative->m_terms.append(copyTerm(term));
 554             // NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....
 555             m_alternative->lastTerm().quantify((max == UINT_MAX) ? max : max - min, greedy ? QuantifierGreedy : QuantifierNonGreedy);
 556             if (m_alternative->lastTerm().type == PatternTerm::TypeParenthesesSubpattern)
 557                 m_alternative->lastTerm().parentheses.isCopy = true;
 558         }
 559     }
 560
 561     void disjunction()
 562     {
 563         m_alternative = m_alternative->m_parent->addNewAlternative();
 564     }
 565
 566     void regexBegin()
 567     {
 568         m_pattern.m_body = new PatternDisjunction();
 569         m_alternative = m_pattern.m_body->addNewAlternative();
 570         m_pattern.m_disjunctions.append(m_pattern.m_body);
 571     }
 572     void regexEnd()
 573     {
 574     }
 575     void regexError()
 576     {
 577     }
 578
 579     unsigned setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition)
 580     {
 581         alternative->m_hasFixedSize = true;
 582         unsigned currentInputPosition = initialInputPosition;
 583
 584         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
 585             PatternTerm& term = alternative->m_terms[i];
 586
 587             switch (term.type) {
 588             case PatternTerm::TypeAssertionBOL:
 589             case PatternTerm::TypeAssertionEOL:
 590             case PatternTerm::TypeAssertionWordBoundary:
 591                 term.inputPosition = currentInputPosition;
 592                 break;
 593
 594             case PatternTerm::TypeBackReference:
 595                 term.inputPosition = currentInputPosition;
 596                 term.frameLocation = currentCallFrameSize;
 597                 currentCallFrameSize += RegexStackSpaceForBackTrackInfoBackReference;
 598                 alternative->m_hasFixedSize = false;
 599                 break;
 600
 601             case PatternTerm::TypeForwardReference:
 602                 break;
 603
 604             case PatternTerm::TypePatternCharacter:
 605                 term.inputPosition = currentInputPosition;
 606                 if (term.quantityType != QuantifierFixedCount) {
 607                     term.frameLocation = currentCallFrameSize;
 608                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoPatternCharacter;
 609                     alternative->m_hasFixedSize = false;
 610                 } else
 611                     currentInputPosition += term.quantityCount;
 612                 break;
 613
 614             case PatternTerm::TypeCharacterClass:
 615                 term.inputPosition = currentInputPosition;
 616                 if (term.quantityType != QuantifierFixedCount) {
 617                     term.frameLocation = currentCallFrameSize;
 618                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoCharacterClass;
 619                     alternative->m_hasFixedSize = false;
 620                 } else
 621                     currentInputPosition += term.quantityCount;
 622                 break;
 623
 624             case PatternTerm::TypeParenthesesSubpattern:
 625                 // Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
 626                 term.frameLocation = currentCallFrameSize;
 627                 if ((term.quantityCount == 1) && !term.parentheses.isCopy) {
 628                     if (term.quantityType == QuantifierFixedCount) {
 629                         currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
 630                         currentInputPosition += term.parentheses.disjunction->m_minimumSize;
 631                     } else {
 632                         currentCallFrameSize += RegexStackSpaceForBackTrackInfoParenthesesOnce;
 633                         currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
 634                     }
 635                     term.inputPosition = currentInputPosition;
 636                 } else {
 637                     term.inputPosition = currentInputPosition;
 638                     setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition);
 639                     currentCallFrameSize += RegexStackSpaceForBackTrackInfoParentheses;
 640                 }
 641                 // Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.
 642                 alternative->m_hasFixedSize = false;
 643                 break;
 644
 645             case PatternTerm::TypeParentheticalAssertion:
 646                 term.inputPosition = currentInputPosition;
 647                 term.frameLocation = currentCallFrameSize;
 648                 currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + RegexStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition);
 649                 break;
 650             }
 651         }
 652
 653         alternative->m_minimumSize = currentInputPosition - initialInputPosition;
 654         return currentCallFrameSize;
 655     }
 656
 657     unsigned setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition)
 658     {
 659         if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
 660             initialCallFrameSize += RegexStackSpaceForBackTrackInfoAlternative;
 661
 662         unsigned minimumInputSize = UINT_MAX;
 663         unsigned maximumCallFrameSize = 0;
 664         bool hasFixedSize = true;
 665
 666         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
 667             PatternAlternative* alternative = disjunction->m_alternatives[alt];
 668             unsigned currentAlternativeCallFrameSize = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition);
 669             minimumInputSize = min(minimumInputSize, alternative->m_minimumSize);
 670             maximumCallFrameSize = max(maximumCallFrameSize, currentAlternativeCallFrameSize);
 671             hasFixedSize &= alternative->m_hasFixedSize;
 672         }
 673
 674         ASSERT(minimumInputSize != UINT_MAX);
 675         ASSERT(maximumCallFrameSize >= initialCallFrameSize);
 676
 677         disjunction->m_hasFixedSize = hasFixedSize;
 678         disjunction->m_minimumSize = minimumInputSize;
 679         disjunction->m_callFrameSize = maximumCallFrameSize;
 680         return maximumCallFrameSize;
 681     }
 682
 683     void setupOffsets()
 684     {
 685         setupDisjunctionOffsets(m_pattern.m_body, 0, 0);
 686     }
 687
 688 private:
 689     RegexPattern& m_pattern;
 690     PatternAlternative* m_alternative;
 691     CharacterClassConstructor m_characterClassConstructor;
 692     bool m_invertCharacterClass;
 693 };
 694
 695
 696 const char* compileRegex(const UString& patternString, RegexPattern& pattern)
 697 {
 698     RegexPatternConstructor constructor(pattern);
 699
 700     if (const char* error = parse(constructor, patternString))
 701         return error;
 702
 703     // If the pattern contains illegal backreferences reset & reparse.
 704     // Quoting Netscape's "What's new in JavaScript 1.2",
 705     //      "Note: if the number of left parentheses is less than the number specified
 706     //       in \#, the \# is taken as an octal escape as described in the next row."
 707     if (pattern.containsIllegalBackReference()) {
 708         unsigned numSubpatterns = pattern.m_numSubpatterns;
 709
 710         constructor.reset();
 711 #if !ASSERT_DISABLED
 712         const char* error =
 713 #endif
 714             parse(constructor, patternString, numSubpatterns);
 715
 716         ASSERT(!error);
 717         ASSERT(numSubpatterns == pattern.m_numSubpatterns);
 718     }
 719
 720     constructor.setupOffsets();
 721
 722     return false;
 723 };
 724
 725
 726 } }
 727
 728 #endif