yarr/RegexInterpreter.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 "RegexInterpreter.h"
  28
  29 #include "RegexCompiler.h"
  30 #include "RegexPattern.h"
  31
  32 #ifndef NDEBUG
  33 #include <stdio.h>
  34 #endif
  35
  36 #if ENABLE(YARR)
  37
  38 using namespace WTF;
  39
  40 namespace JSC { namespace Yarr {
  41
  42 class Interpreter {
  43 public:
  44     struct ParenthesesDisjunctionContext;
  45
  46     struct BackTrackInfoPatternCharacter {
  47         uintptr_t matchAmount;
  48     };
  49     struct BackTrackInfoCharacterClass {
  50         uintptr_t matchAmount;
  51     };
  52     struct BackTrackInfoBackReference {
  53         uintptr_t begin; // Not really needed for greedy quantifiers.
  54         uintptr_t matchAmount; // Not really needed for fixed quantifiers.
  55     };
  56     struct BackTrackInfoAlternative {
  57         uintptr_t offset;
  58     };
  59     struct BackTrackInfoParentheticalAssertion {
  60         uintptr_t begin;
  61     };
  62     struct BackTrackInfoParenthesesOnce {
  63         uintptr_t inParentheses;
  64     };
  65     struct BackTrackInfoParentheses {
  66         uintptr_t matchAmount;
  67         ParenthesesDisjunctionContext* lastContext;
  68         uintptr_t prevBegin;
  69         uintptr_t prevEnd;
  70     };
  71
  72     static inline void appendParenthesesDisjunctionContext(BackTrackInfoParentheses* backTrack, ParenthesesDisjunctionContext* context)
  73     {
  74         context->next = backTrack->lastContext;
  75         backTrack->lastContext = context;
  76         ++backTrack->matchAmount;
  77     }
  78
  79     static inline void popParenthesesDisjunctionContext(BackTrackInfoParentheses* backTrack)
  80     {
  81         ASSERT(backTrack->matchAmount);
  82         ASSERT(backTrack->lastContext);
  83         backTrack->lastContext = backTrack->lastContext->next;
  84         --backTrack->matchAmount;
  85     }
  86
  87     struct DisjunctionContext
  88     {
  89         DisjunctionContext()
  90             : term(0)
  91         {
  92         }
  93
  94         void* operator new(size_t, void* where)
  95         {
  96             return where;
  97         }
  98
  99         int term;
 100         unsigned matchBegin;
 101         unsigned matchEnd;
 102         uintptr_t frame[1];
 103     };
 104
 105     DisjunctionContext* allocDisjunctionContext(ByteDisjunction* disjunction)
 106     {
 107         return new(malloc(sizeof(DisjunctionContext) + (disjunction->m_frameSize - 1) * sizeof(uintptr_t))) DisjunctionContext();
 108     }
 109
 110     void freeDisjunctionContext(DisjunctionContext* context)
 111     {
 112         free(context);
 113     }
 114
 115     struct ParenthesesDisjunctionContext
 116     {
 117         ParenthesesDisjunctionContext(int* output, ByteTerm& term)
 118             : next(0)
 119         {
 120             unsigned firstSubpatternId = term.atom.subpatternId;
 121             unsigned numNestedSubpatterns = term.atom.parenthesesDisjunction->m_numSubpatterns;
 122
 123             for (unsigned i = 0; i < (numNestedSubpatterns << 1); ++i) {
 124                 subpatternBackup[i] = output[(firstSubpatternId << 1) + i];
 125                 output[(firstSubpatternId << 1) + i] = -1;
 126             }
 127
 128             new(getDisjunctionContext(term)) DisjunctionContext();
 129         }
 130
 131         void* operator new(size_t, void* where)
 132         {
 133             return where;
 134         }
 135
 136         void restoreOutput(int* output, unsigned firstSubpatternId, unsigned numNestedSubpatterns)
 137         {
 138             for (unsigned i = 0; i < (numNestedSubpatterns << 1); ++i)
 139                 output[(firstSubpatternId << 1) + i] = subpatternBackup[i];
 140         }
 141
 142         DisjunctionContext* getDisjunctionContext(ByteTerm& term)
 143         {
 144             return reinterpret_cast<DisjunctionContext*>(&(subpatternBackup[term.atom.parenthesesDisjunction->m_numSubpatterns << 1]));
 145         }
 146
 147         ParenthesesDisjunctionContext* next;
 148         int subpatternBackup[1];
 149     };
 150
 151     ParenthesesDisjunctionContext* allocParenthesesDisjunctionContext(ByteDisjunction* disjunction, int* output, ByteTerm& term)
 152     {
 153         return new(malloc(sizeof(ParenthesesDisjunctionContext) + (((term.atom.parenthesesDisjunction->m_numSubpatterns << 1) - 1) * sizeof(int)) + sizeof(DisjunctionContext) + (disjunction->m_frameSize - 1) * sizeof(uintptr_t))) ParenthesesDisjunctionContext(output, term);
 154     }
 155
 156     void freeParenthesesDisjunctionContext(ParenthesesDisjunctionContext* context)
 157     {
 158         free(context);
 159     }
 160
 161     class InputStream {
 162     public:
 163         InputStream(const UChar* input, unsigned start, unsigned length)
 164             : input(input)
 165             , pos(start)
 166             , length(length)
 167         {
 168         }
 169
 170         void next()
 171         {
 172             ++pos;
 173         }
 174
 175         void rewind(unsigned amount)
 176         {
 177             ASSERT(pos >= amount);
 178             pos -= amount;
 179         }
 180
 181         int read()
 182         {
 183             ASSERT(pos < length);
 184             if (pos < length)
 185                 return input[pos];
 186             return -1;
 187         }
 188
 189         int readChecked(int position)
 190         {
 191             ASSERT(position < 0);
 192             ASSERT((unsigned)-position <= pos);
 193             unsigned p = pos + position;
 194             ASSERT(p < length);
 195             return input[p];
 196         }
 197
 198         int reread(unsigned from)
 199         {
 200             ASSERT(from < length);
 201             return input[from];
 202         }
 203
 204         int prev()
 205         {
 206             ASSERT(!(pos > length));
 207             if (pos && length)
 208                 return input[pos - 1];
 209             return -1;
 210         }
 211
 212         unsigned getPos()
 213         {
 214             return pos;
 215         }
 216
 217         void setPos(unsigned p)
 218         {
 219             pos = p;
 220         }
 221
 222         bool atStart()
 223         {
 224             return pos == 0;
 225         }
 226
 227         bool atEnd()
 228         {
 229             return pos == length;
 230         }
 231
 232         bool checkInput(int count)
 233         {
 234             if ((pos + count) <= length) {
 235                 pos += count;
 236                 return true;
 237             } else
 238                 return false;
 239         }
 240
 241         void uncheckInput(int count)
 242         {
 243             pos -= count;
 244         }
 245
 246         bool atStart(int position)
 247         {
 248             return (pos + position) == 0;
 249         }
 250
 251         bool atEnd(int position)
 252         {
 253             return (pos + position) == length;
 254         }
 255
 256     private:
 257         const UChar* input;
 258         unsigned pos;
 259         unsigned length;
 260     };
 261
 262     bool testCharacterClass(CharacterClass* characterClass, int ch)
 263     {
 264         if (ch & 0xFF80) {
 265             for (unsigned i = 0; i < characterClass->m_matchesUnicode.size(); ++i)
 266                 if (ch == characterClass->m_matchesUnicode[i])
 267                     return true;
 268             for (unsigned i = 0; i < characterClass->m_rangesUnicode.size(); ++i)
 269                 if ((ch >= characterClass->m_rangesUnicode[i].begin) && (ch <= characterClass->m_rangesUnicode[i].end))
 270                     return true;
 271         } else {
 272             for (unsigned i = 0; i < characterClass->m_matches.size(); ++i)
 273                 if (ch == characterClass->m_matches[i])
 274                     return true;
 275             for (unsigned i = 0; i < characterClass->m_ranges.size(); ++i)
 276                 if ((ch >= characterClass->m_ranges[i].begin) && (ch <= characterClass->m_ranges[i].end))
 277                     return true;
 278         }
 279
 280         return false;
 281     }
 282
 283     bool tryConsumeCharacter(int testChar)
 284     {
 285         if (input.atEnd())
 286             return false;
 287
 288         int ch = input.read();
 289
 290         if (pattern->m_ignoreCase ? ((Unicode::toLower(testChar) == ch) || (Unicode::toUpper(testChar) == ch)) : (testChar == ch)) {
 291             input.next();
 292             return true;
 293         }
 294         return false;
 295     }
 296
 297     bool checkCharacter(int testChar, int inputPosition)
 298     {
 299         return testChar == input.readChecked(inputPosition);
 300     }
 301
 302     bool checkCasedCharacter(int loChar, int hiChar, int inputPosition)
 303     {
 304         int ch = input.readChecked(inputPosition);
 305         return (loChar == ch) || (hiChar == ch);
 306     }
 307
 308     bool tryConsumeCharacterClass(CharacterClass* characterClass, bool invert)
 309     {
 310         if (input.atEnd())
 311             return false;
 312
 313         bool match = testCharacterClass(characterClass, input.read());
 314
 315         if (invert)
 316             match = !match;
 317
 318         if (match) {
 319             input.next();
 320             return true;
 321         }
 322         return false;
 323     }
 324
 325     bool checkCharacterClass(CharacterClass* characterClass, bool invert, int inputPosition)
 326     {
 327         bool match = testCharacterClass(characterClass, input.readChecked(inputPosition));
 328         return invert ? !match : match;
 329     }
 330
 331     bool tryConsumeBackReference(int matchBegin, int matchEnd, int inputOffset)
 332     {
 333         int matchSize = matchEnd - matchBegin;
 334
 335         if (!input.checkInput(matchSize))
 336             return false;
 337
 338         for (int i = 0; i < matchSize; ++i) {
 339             if (!checkCharacter(input.reread(matchBegin + i), inputOffset - matchSize + i)) {
 340                 input.uncheckInput(matchSize);
 341                 return false;
 342             }
 343         }
 344
 345         return true;
 346     }
 347
 348     bool matchAssertionBOL(ByteTerm& term)
 349     {
 350         return (input.atStart(term.inputPosition)) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.readChecked(term.inputPosition - 1)));
 351     }
 352
 353     bool matchAssertionEOL(ByteTerm& term)
 354     {
 355         if (term.inputPosition)
 356             return (input.atEnd(term.inputPosition)) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.readChecked(term.inputPosition)));
 357         else
 358             return (input.atEnd()) || (pattern->m_multiline && testCharacterClass(pattern->newlineCharacterClass, input.read()));
 359     }
 360
 361     bool matchAssertionWordBoundary(ByteTerm& term)
 362     {
 363         bool prevIsWordchar = !input.atStart(term.inputPosition) && testCharacterClass(pattern->wordcharCharacterClass, input.readChecked(term.inputPosition - 1));
 364         bool readIsWordchar;
 365         if (term.inputPosition)
 366             readIsWordchar = !input.atEnd(term.inputPosition) && testCharacterClass(pattern->wordcharCharacterClass, input.readChecked(term.inputPosition));
 367         else
 368             readIsWordchar = !input.atEnd() && testCharacterClass(pattern->wordcharCharacterClass, input.read());
 369
 370         bool wordBoundary = prevIsWordchar != readIsWordchar;
 371         return term.invert() ? !wordBoundary : wordBoundary;
 372     }
 373
 374     bool backtrackPatternCharacter(ByteTerm& term, DisjunctionContext* context)
 375     {
 376         BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);
 377
 378         switch (term.atom.quantityType) {
 379         case QuantifierFixedCount:
 380             break;
 381
 382         case QuantifierGreedy:
 383             if (backTrack->matchAmount) {
 384                 --backTrack->matchAmount;
 385                 input.uncheckInput(1);
 386                 return true;
 387             }
 388             break;
 389
 390         case QuantifierNonGreedy:
 391             if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {
 392                 ++backTrack->matchAmount;
 393                 if (checkCharacter(term.atom.patternCharacter, term.inputPosition - 1))
 394                     return true;
 395             }
 396             input.uncheckInput(backTrack->matchAmount);
 397             break;
 398         }
 399
 400         return false;
 401     }
 402
 403     bool backtrackPatternCasedCharacter(ByteTerm& term, DisjunctionContext* context)
 404     {
 405         BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);
 406
 407         switch (term.atom.quantityType) {
 408         case QuantifierFixedCount:
 409             break;
 410
 411         case QuantifierGreedy:
 412             if (backTrack->matchAmount) {
 413                 --backTrack->matchAmount;
 414                 input.uncheckInput(1);
 415                 return true;
 416             }
 417             break;
 418
 419         case QuantifierNonGreedy:
 420             if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {
 421                 ++backTrack->matchAmount;
 422                 if (checkCasedCharacter(term.atom.casedCharacter.lo, term.atom.casedCharacter.hi, term.inputPosition - 1))
 423                     return true;
 424             }
 425             input.uncheckInput(backTrack->matchAmount);
 426             break;
 427         }
 428
 429         return false;
 430     }
 431
 432     bool matchCharacterClass(ByteTerm& term, DisjunctionContext* context)
 433     {
 434         ASSERT(term.type == ByteTerm::TypeCharacterClass);
 435         BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);
 436
 437         switch (term.atom.quantityType) {
 438         case QuantifierFixedCount: {
 439             for (unsigned matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {
 440                 if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition + matchAmount))
 441                     return false;
 442             }
 443             return true;
 444         }
 445
 446         case QuantifierGreedy: {
 447             unsigned matchAmount = 0;
 448             while ((matchAmount < term.atom.quantityCount) && input.checkInput(1)) {
 449                 if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition - 1)) {
 450                     input.uncheckInput(1);
 451                     break;
 452                 }
 453                 ++matchAmount;
 454             }
 455             backTrack->matchAmount = matchAmount;
 456
 457             return true;
 458         }
 459
 460         case QuantifierNonGreedy:
 461             backTrack->matchAmount = 0;
 462             return true;
 463         }
 464
 465         ASSERT_NOT_REACHED();
 466         return false;
 467     }
 468
 469     bool backtrackCharacterClass(ByteTerm& term, DisjunctionContext* context)
 470     {
 471         ASSERT(term.type == ByteTerm::TypeCharacterClass);
 472         BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + term.frameLocation);
 473
 474         switch (term.atom.quantityType) {
 475         case QuantifierFixedCount:
 476             break;
 477
 478         case QuantifierGreedy:
 479             if (backTrack->matchAmount) {
 480                 --backTrack->matchAmount;
 481                 input.uncheckInput(1);
 482                 return true;
 483             }
 484             break;
 485
 486         case QuantifierNonGreedy:
 487             if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {
 488                 ++backTrack->matchAmount;
 489                 if (checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition - 1))
 490                     return true;
 491             }
 492             input.uncheckInput(backTrack->matchAmount);
 493             break;
 494         }
 495
 496         return false;
 497     }
 498
 499     bool matchBackReference(ByteTerm& term, DisjunctionContext* context)
 500     {
 501         ASSERT(term.type == ByteTerm::TypeBackReference);
 502         BackTrackInfoBackReference* backTrack = reinterpret_cast<BackTrackInfoBackReference*>(context->frame + term.frameLocation);
 503
 504         int matchBegin = output[(term.atom.subpatternId << 1)];
 505         int matchEnd = output[(term.atom.subpatternId << 1) + 1];
 506         ASSERT((matchBegin == -1) == (matchEnd == -1));
 507         ASSERT(matchBegin <= matchEnd);
 508
 509         if (matchBegin == matchEnd)
 510             return true;
 511
 512         switch (term.atom.quantityType) {
 513         case QuantifierFixedCount: {
 514             backTrack->begin = input.getPos();
 515             for (unsigned matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {
 516                 if (!tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {
 517                     input.setPos(backTrack->begin);
 518                     return false;
 519                 }
 520             }
 521             return true;
 522         }
 523
 524         case QuantifierGreedy: {
 525             unsigned matchAmount = 0;
 526             while ((matchAmount < term.atom.quantityCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition))
 527                 ++matchAmount;
 528             backTrack->matchAmount = matchAmount;
 529             return true;
 530         }
 531
 532         case QuantifierNonGreedy:
 533             backTrack->begin = input.getPos();
 534             backTrack->matchAmount = 0;
 535             return true;
 536         }
 537
 538         ASSERT_NOT_REACHED();
 539         return false;
 540     }
 541
 542     bool backtrackBackReference(ByteTerm& term, DisjunctionContext* context)
 543     {
 544         ASSERT(term.type == ByteTerm::TypeBackReference);
 545         BackTrackInfoBackReference* backTrack = reinterpret_cast<BackTrackInfoBackReference*>(context->frame + term.frameLocation);
 546
 547         int matchBegin = output[(term.atom.subpatternId << 1)];
 548         int matchEnd = output[(term.atom.subpatternId << 1) + 1];
 549         ASSERT((matchBegin == -1) == (matchEnd == -1));
 550         ASSERT(matchBegin <= matchEnd);
 551
 552         if (matchBegin == matchEnd)
 553             return false;
 554
 555         switch (term.atom.quantityType) {
 556         case QuantifierFixedCount:
 557             // for quantityCount == 1, could rewind.
 558             input.setPos(backTrack->begin);
 559             break;
 560
 561         case QuantifierGreedy:
 562             if (backTrack->matchAmount) {
 563                 --backTrack->matchAmount;
 564                 input.rewind(matchEnd - matchBegin);
 565                 return true;
 566             }
 567             break;
 568
 569         case QuantifierNonGreedy:
 570             if ((backTrack->matchAmount < term.atom.quantityCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {
 571                 ++backTrack->matchAmount;
 572                 return true;
 573             } else
 574                 input.setPos(backTrack->begin);
 575             break;
 576         }
 577
 578         return false;
 579     }
 580
 581     void recordParenthesesMatch(ByteTerm& term, ParenthesesDisjunctionContext* context)
 582     {
 583         if (term.capture()) {
 584             unsigned subpatternId = term.atom.subpatternId;
 585             output[(subpatternId << 1)] = context->getDisjunctionContext(term)->matchBegin + term.inputPosition;
 586             output[(subpatternId << 1) + 1] = context->getDisjunctionContext(term)->matchEnd + term.inputPosition;
 587         }
 588     }
 589     void resetMatches(ByteTerm& term, ParenthesesDisjunctionContext* context)
 590     {
 591         unsigned firstSubpatternId = term.atom.subpatternId;
 592         unsigned count = term.atom.parenthesesDisjunction->m_numSubpatterns;
 593         context->restoreOutput(output, firstSubpatternId, count);
 594     }
 595     void resetAssertionMatches(ByteTerm& term)
 596     {
 597         unsigned firstSubpatternId = term.atom.subpatternId;
 598         unsigned count = term.atom.parenthesesDisjunction->m_numSubpatterns;
 599         for (unsigned i = 0; i < (count << 1); ++i)
 600             output[(firstSubpatternId << 1) + i] = -1;
 601     }
 602     bool parenthesesDoBacktrack(ByteTerm& term, BackTrackInfoParentheses* backTrack)
 603     {
 604         while (backTrack->matchAmount) {
 605             ParenthesesDisjunctionContext* context = backTrack->lastContext;
 606
 607             if (matchDisjunction(term.atom.parenthesesDisjunction, context->getDisjunctionContext(term), true))
 608                 return true;
 609
 610             resetMatches(term, context);
 611             popParenthesesDisjunctionContext(backTrack);
 612             freeParenthesesDisjunctionContext(context);
 613         }
 614
 615         return false;
 616     }
 617
 618     bool matchParenthesesOnceBegin(ByteTerm& term, DisjunctionContext* context)
 619     {
 620         ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceBegin);
 621         ASSERT(term.atom.quantityCount == 1);
 622
 623         BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);
 624
 625         switch (term.atom.quantityType) {
 626         case QuantifierGreedy: {
 627             // set this speculatively; if we get to the parens end this will be true.
 628             backTrack->inParentheses = 1;
 629             break;
 630         }
 631         case QuantifierNonGreedy: {
 632             backTrack->inParentheses = 0;
 633             context->term += term.atom.parenthesesWidth;
 634             return true;
 635         }
 636         case QuantifierFixedCount:
 637             break;
 638         }
 639
 640         if (term.capture()) {
 641             unsigned subpatternId = term.atom.subpatternId;
 642             output[(subpatternId << 1)] = input.getPos() + term.inputPosition;
 643         }
 644
 645         return true;
 646     }
 647
 648     bool matchParenthesesOnceEnd(ByteTerm& term, DisjunctionContext*)
 649     {
 650         ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceEnd);
 651         ASSERT(term.atom.quantityCount == 1);
 652
 653         if (term.capture()) {
 654             unsigned subpatternId = term.atom.subpatternId;
 655             output[(subpatternId << 1) + 1] = input.getPos() + term.inputPosition;
 656         }
 657         return true;
 658     }
 659
 660     bool backtrackParenthesesOnceBegin(ByteTerm& term, DisjunctionContext* context)
 661     {
 662         ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceBegin);
 663         ASSERT(term.atom.quantityCount == 1);
 664
 665         BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);
 666
 667         if (term.capture()) {
 668             unsigned subpatternId = term.atom.subpatternId;
 669             output[(subpatternId << 1)] = -1;
 670             output[(subpatternId << 1) + 1] = -1;
 671         }
 672
 673         switch (term.atom.quantityType) {
 674         case QuantifierGreedy:
 675             // if we backtrack to this point, there is another chance - try matching nothing.
 676             ASSERT(backTrack->inParentheses);
 677             backTrack->inParentheses = 0;
 678             context->term += term.atom.parenthesesWidth;
 679             return true;
 680         case QuantifierNonGreedy:
 681             ASSERT(backTrack->inParentheses);
 682         case QuantifierFixedCount:
 683             break;
 684         }
 685
 686         return false;
 687     }
 688
 689     bool backtrackParenthesesOnceEnd(ByteTerm& term, DisjunctionContext* context)
 690     {
 691         ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceEnd);
 692         ASSERT(term.atom.quantityCount == 1);
 693
 694         BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);
 695
 696         switch (term.atom.quantityType) {
 697         case QuantifierGreedy:
 698             if (!backTrack->inParentheses) {
 699                 context->term -= term.atom.parenthesesWidth;
 700                 return false;
 701             }
 702         case QuantifierNonGreedy:
 703             if (!backTrack->inParentheses) {
 704                 // now try to match the parens; set this speculatively.
 705                 backTrack->inParentheses = 1;
 706                 if (term.capture()) {
 707                     unsigned subpatternId = term.atom.subpatternId;
 708                     output[(subpatternId << 1) + 1] = input.getPos() + term.inputPosition;
 709                 }
 710                 context->term -= term.atom.parenthesesWidth;
 711                 return true;
 712             }
 713         case QuantifierFixedCount:
 714             break;
 715         }
 716
 717         return false;
 718     }
 719
 720     bool matchParentheticalAssertionBegin(ByteTerm& term, DisjunctionContext* context)
 721     {
 722         ASSERT(term.type == ByteTerm::TypeParentheticalAssertionBegin);
 723         ASSERT(term.atom.quantityCount == 1);
 724
 725         BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);
 726
 727         backTrack->begin = input.getPos();
 728         return true;
 729     }
 730
 731     bool matchParentheticalAssertionEnd(ByteTerm& term, DisjunctionContext* context)
 732     {
 733         ASSERT(term.type == ByteTerm::TypeParentheticalAssertionEnd);
 734         ASSERT(term.atom.quantityCount == 1);
 735
 736         BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);
 737
 738         input.setPos(backTrack->begin);
 739
 740         // We've reached the end of the parens; if they are inverted, this is failure.
 741         if (term.invert()) {
 742             context->term -= term.atom.parenthesesWidth;
 743             return false;
 744         }
 745
 746         return true;
 747     }
 748
 749     bool backtrackParentheticalAssertionBegin(ByteTerm& term, DisjunctionContext* context)
 750     {
 751         ASSERT(term.type == ByteTerm::TypeParentheticalAssertionBegin);
 752         ASSERT(term.atom.quantityCount == 1);
 753
 754         // We've failed to match parens; if they are inverted, this is win!
 755         if (term.invert()) {
 756             context->term += term.atom.parenthesesWidth;
 757             return true;
 758         }
 759
 760         return false;
 761     }
 762
 763     bool backtrackParentheticalAssertionEnd(ByteTerm& term, DisjunctionContext* context)
 764     {
 765         ASSERT(term.type == ByteTerm::TypeParentheticalAssertionEnd);
 766         ASSERT(term.atom.quantityCount == 1);
 767
 768         BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);
 769
 770         input.setPos(backTrack->begin);
 771
 772         context->term -= term.atom.parenthesesWidth;
 773         return false;
 774     }
 775
 776     bool matchParentheses(ByteTerm& term, DisjunctionContext* context)
 777     {
 778         ASSERT(term.type == ByteTerm::TypeParenthesesSubpattern);
 779
 780         BackTrackInfoParentheses* backTrack = reinterpret_cast<BackTrackInfoParentheses*>(context->frame + term.frameLocation);
 781
 782         unsigned subpatternId = term.atom.subpatternId;
 783         ByteDisjunction* disjunctionBody = term.atom.parenthesesDisjunction;
 784
 785         backTrack->prevBegin = output[(subpatternId << 1)];
 786         backTrack->prevEnd = output[(subpatternId << 1) + 1];
 787
 788         backTrack->matchAmount = 0;
 789         backTrack->lastContext = 0;
 790
 791         switch (term.atom.quantityType) {
 792         case QuantifierFixedCount: {
 793             // While we haven't yet reached our fixed limit,
 794             while (backTrack->matchAmount < term.atom.quantityCount) {
 795                 // Try to do a match, and it it succeeds, add it to the list.
 796                 ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
 797                 if (matchDisjunction(disjunctionBody, context->getDisjunctionContext(term)))
 798                     appendParenthesesDisjunctionContext(backTrack, context);
 799                 else {
 800                     // The match failed; try to find an alternate point to carry on from.
 801                     resetMatches(term, context);
 802                     freeParenthesesDisjunctionContext(context);
 803                     if (!parenthesesDoBacktrack(term, backTrack))
 804                         return false;
 805                 }
 806             }
 807
 808             ASSERT(backTrack->matchAmount == term.atom.quantityCount);
 809             ParenthesesDisjunctionContext* context = backTrack->lastContext;
 810             recordParenthesesMatch(term, context);
 811             return true;
 812         }
 813
 814         case QuantifierGreedy: {
 815             while (backTrack->matchAmount < term.atom.quantityCount) {
 816                 ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
 817                 if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term)))
 818                     appendParenthesesDisjunctionContext(backTrack, context);
 819                 else {
 820                     resetMatches(term, context);
 821                     freeParenthesesDisjunctionContext(context);
 822                     break;
 823                 }
 824             }
 825
 826             if (backTrack->matchAmount) {
 827                 ParenthesesDisjunctionContext* context = backTrack->lastContext;
 828                 recordParenthesesMatch(term, context);
 829             }
 830             return true;
 831         }
 832
 833         case QuantifierNonGreedy:
 834             return true;
 835         }
 836
 837         ASSERT_NOT_REACHED();
 838         return false;
 839     }
 840
 841     // Rules for backtracking differ depending on whether this is greedy or non-greedy.
 842     //
 843     // Greedy matches never should try just adding more - you should already have done
 844     // the 'more' cases.  Always backtrack, at least a leetle bit.  However cases where
 845     // you backtrack an item off the list needs checking, since we'll never have matched
 846     // the one less case.  Tracking forwards, still add as much as possible.
 847     //
 848     // Non-greedy, we've already done the one less case, so don't match on popping.
 849     // We haven't done the one more case, so always try to add that.
 850     //
 851     bool backtrackParentheses(ByteTerm& term, DisjunctionContext* context)
 852     {
 853         ASSERT(term.type == ByteTerm::TypeParenthesesSubpattern);
 854
 855         BackTrackInfoParentheses* backTrack = reinterpret_cast<BackTrackInfoParentheses*>(context->frame + term.frameLocation);
 856
 857         if (term.capture()) {
 858             unsigned subpatternId = term.atom.subpatternId;
 859             output[(subpatternId << 1)] = backTrack->prevBegin;
 860             output[(subpatternId << 1) + 1] = backTrack->prevEnd;
 861         }
 862
 863         ByteDisjunction* disjunctionBody = term.atom.parenthesesDisjunction;
 864
 865         switch (term.atom.quantityType) {
 866         case QuantifierFixedCount: {
 867             ASSERT(backTrack->matchAmount == term.atom.quantityCount);
 868
 869             ParenthesesDisjunctionContext* context = 0;
 870
 871             if (!parenthesesDoBacktrack(term, backTrack))
 872                 return false;
 873
 874             // While we haven't yet reached our fixed limit,
 875             while (backTrack->matchAmount < term.atom.quantityCount) {
 876                 // Try to do a match, and it it succeeds, add it to the list.
 877                 context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
 878                 if (matchDisjunction(disjunctionBody, context->getDisjunctionContext(term)))
 879                     appendParenthesesDisjunctionContext(backTrack, context);
 880                 else {
 881                     // The match failed; try to find an alternate point to carry on from.
 882                     resetMatches(term, context);
 883                     freeParenthesesDisjunctionContext(context);
 884                     if (!parenthesesDoBacktrack(term, backTrack))
 885                         return false;
 886                 }
 887             }
 888
 889             ASSERT(backTrack->matchAmount == term.atom.quantityCount);
 890             context = backTrack->lastContext;
 891             recordParenthesesMatch(term, context);
 892             return true;
 893         }
 894
 895         case QuantifierGreedy: {
 896             if (!backTrack->matchAmount)
 897                 return false;
 898
 899             ParenthesesDisjunctionContext* context = backTrack->lastContext;
 900             if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term), true)) {
 901                 while (backTrack->matchAmount < term.atom.quantityCount) {
 902                     ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
 903                     if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term)))
 904                         appendParenthesesDisjunctionContext(backTrack, context);
 905                     else {
 906                         resetMatches(term, context);
 907                         freeParenthesesDisjunctionContext(context);
 908                         break;
 909                     }
 910                 }
 911             } else {
 912                 resetMatches(term, context);
 913                 popParenthesesDisjunctionContext(backTrack);
 914                 freeParenthesesDisjunctionContext(context);
 915             }
 916
 917             if (backTrack->matchAmount) {
 918                 ParenthesesDisjunctionContext* context = backTrack->lastContext;
 919                 recordParenthesesMatch(term, context);
 920             }
 921             return true;
 922         }
 923
 924         case QuantifierNonGreedy: {
 925             // If we've not reached the limit, try to add one more match.
 926             if (backTrack->matchAmount < term.atom.quantityCount) {
 927                 ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
 928                 if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term))) {
 929                     appendParenthesesDisjunctionContext(backTrack, context);
 930                     recordParenthesesMatch(term, context);
 931                     return true;
 932                 } else {
 933                     resetMatches(term, context);
 934                     freeParenthesesDisjunctionContext(context);
 935                 }
 936             }
 937
 938             // Nope - okay backtrack looking for an alternative.
 939             while (backTrack->matchAmount) {
 940                 ParenthesesDisjunctionContext* context = backTrack->lastContext;
 941                 if (matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term), true)) {
 942                     // successful backtrack! we're back in the game!
 943                     if (backTrack->matchAmount) {
 944                         context = backTrack->lastContext;
 945                         recordParenthesesMatch(term, context);
 946                     }
 947                     return true;
 948                 }
 949
 950                 // pop a match off the stack
 951                 resetMatches(term, context);
 952                 popParenthesesDisjunctionContext(backTrack);
 953                 freeParenthesesDisjunctionContext(context);
 954             }
 955
 956             return false;
 957         }
 958         }
 959
 960         ASSERT_NOT_REACHED();
 961         return false;
 962     }
 963
 964 #define MATCH_NEXT() { ++context->term; goto matchAgain; }
 965 #define BACKTRACK() { --context->term; goto backtrack; }
 966 #define currentTerm() (disjunction->terms[context->term])
 967     bool matchDisjunction(ByteDisjunction* disjunction, DisjunctionContext* context, bool btrack = false)
 968     {
 969         if (btrack)
 970             BACKTRACK();
 971
 972         context->matchBegin = input.getPos();
 973         context->term = 0;
 974
 975     matchAgain:
 976         ASSERT(context->term < static_cast<int>(disjunction->terms.size()));
 977
 978         switch (currentTerm().type) {
 979         case ByteTerm::TypeSubpatternBegin:
 980             MATCH_NEXT();
 981         case ByteTerm::TypeSubpatternEnd:
 982             context->matchEnd = input.getPos();
 983             return true;
 984
 985         case ByteTerm::TypeBodyAlternativeBegin:
 986             MATCH_NEXT();
 987         case ByteTerm::TypeBodyAlternativeDisjunction:
 988         case ByteTerm::TypeBodyAlternativeEnd:
 989             context->matchEnd = input.getPos();
 990             return true;
 991
 992         case ByteTerm::TypeAlternativeBegin:
 993             MATCH_NEXT();
 994         case ByteTerm::TypeAlternativeDisjunction:
 995         case ByteTerm::TypeAlternativeEnd: {
 996             int offset = currentTerm().alternative.end;
 997             BackTrackInfoAlternative* backTrack = reinterpret_cast<BackTrackInfoAlternative*>(context->frame + currentTerm().frameLocation);
 998             backTrack->offset = offset;
 999             context->term += offset;
1000             MATCH_NEXT();
1001         }
1002
1003         case ByteTerm::TypeAssertionBOL:
1004             if (matchAssertionBOL(currentTerm()))
1005                 MATCH_NEXT();
1006             BACKTRACK();
1007         case ByteTerm::TypeAssertionEOL:
1008             if (matchAssertionEOL(currentTerm()))
1009                 MATCH_NEXT();
1010             BACKTRACK();
1011         case ByteTerm::TypeAssertionWordBoundary:
1012             if (matchAssertionWordBoundary(currentTerm()))
1013                 MATCH_NEXT();
1014             BACKTRACK();
1015
1016         case ByteTerm::TypePatternCharacterOnce:
1017         case ByteTerm::TypePatternCharacterFixed: {
1018             for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityCount; ++matchAmount) {
1019                 if (!checkCharacter(currentTerm().atom.patternCharacter, currentTerm().inputPosition + matchAmount))
1020                     BACKTRACK();
1021             }
1022             MATCH_NEXT();
1023         }
1024         case ByteTerm::TypePatternCharacterGreedy: {
1025             BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + currentTerm().frameLocation);
1026             unsigned matchAmount = 0;
1027             while ((matchAmount < currentTerm().atom.quantityCount) && input.checkInput(1)) {
1028                 if (!checkCharacter(currentTerm().atom.patternCharacter, currentTerm().inputPosition - 1)) {
1029                     input.uncheckInput(1);
1030                     break;
1031                 }
1032                 ++matchAmount;
1033             }
1034             backTrack->matchAmount = matchAmount;
1035
1036             MATCH_NEXT();
1037         }
1038         case ByteTerm::TypePatternCharacterNonGreedy: {
1039             BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + currentTerm().frameLocation);
1040             backTrack->matchAmount = 0;
1041             MATCH_NEXT();
1042         }
1043
1044         case ByteTerm::TypePatternCasedCharacterOnce:
1045         case ByteTerm::TypePatternCasedCharacterFixed: {
1046             for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityCount; ++matchAmount) {
1047                 if (!checkCasedCharacter(currentTerm().atom.casedCharacter.lo, currentTerm().atom.casedCharacter.hi, currentTerm().inputPosition + matchAmount))
1048                     BACKTRACK();
1049             }
1050             MATCH_NEXT();
1051         }
1052         case ByteTerm::TypePatternCasedCharacterGreedy: {
1053             BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + currentTerm().frameLocation);
1054             unsigned matchAmount = 0;
1055             while ((matchAmount < currentTerm().atom.quantityCount) && input.checkInput(1)) {
1056                 if (!checkCasedCharacter(currentTerm().atom.casedCharacter.lo, currentTerm().atom.casedCharacter.hi, currentTerm().inputPosition - 1)) {
1057                     input.uncheckInput(1);
1058                     break;
1059                 }
1060                 ++matchAmount;
1061             }
1062             backTrack->matchAmount = matchAmount;
1063
1064             MATCH_NEXT();
1065         }
1066         case ByteTerm::TypePatternCasedCharacterNonGreedy: {
1067             BackTrackInfoPatternCharacter* backTrack = reinterpret_cast<BackTrackInfoPatternCharacter*>(context->frame + currentTerm().frameLocation);
1068             backTrack->matchAmount = 0;
1069             MATCH_NEXT();
1070         }
1071
1072         case ByteTerm::TypeCharacterClass:
1073             if (matchCharacterClass(currentTerm(), context))
1074                 MATCH_NEXT();
1075             BACKTRACK();
1076         case ByteTerm::TypeBackReference:
1077             if (matchBackReference(currentTerm(), context))
1078                 MATCH_NEXT();
1079             BACKTRACK();
1080         case ByteTerm::TypeParenthesesSubpattern:
1081             if (matchParentheses(currentTerm(), context))
1082                 MATCH_NEXT();
1083             BACKTRACK();
1084         case ByteTerm::TypeParenthesesSubpatternOnceBegin:
1085             if (matchParenthesesOnceBegin(currentTerm(), context))
1086                 MATCH_NEXT();
1087             BACKTRACK();
1088         case ByteTerm::TypeParenthesesSubpatternOnceEnd:
1089             if (matchParenthesesOnceEnd(currentTerm(), context))
1090                 MATCH_NEXT();
1091             BACKTRACK();
1092         case ByteTerm::TypeParentheticalAssertionBegin:
1093             if (matchParentheticalAssertionBegin(currentTerm(), context))
1094                 MATCH_NEXT();
1095             BACKTRACK();
1096         case ByteTerm::TypeParentheticalAssertionEnd:
1097             if (matchParentheticalAssertionEnd(currentTerm(), context))
1098                 MATCH_NEXT();
1099             BACKTRACK();
1100
1101         case ByteTerm::TypeCheckInput:
1102             if (input.checkInput(currentTerm().checkInputCount))
1103                 MATCH_NEXT();
1104             BACKTRACK();
1105         }
1106
1107         // We should never fall-through to here.
1108         ASSERT_NOT_REACHED();
1109
1110     backtrack:
1111         ASSERT(context->term < static_cast<int>(disjunction->terms.size()));
1112
1113         switch (currentTerm().type) {
1114         case ByteTerm::TypeSubpatternBegin:
1115             return false;
1116         case ByteTerm::TypeSubpatternEnd:
1117             ASSERT_NOT_REACHED();
1118
1119         case ByteTerm::TypeBodyAlternativeBegin:
1120         case ByteTerm::TypeBodyAlternativeDisjunction: {
1121             int offset = currentTerm().alternative.next;
1122             context->term += offset;
1123             if (offset > 0)
1124                 MATCH_NEXT();
1125
1126             if (input.atEnd())
1127                 return false;
1128
1129             input.next();
1130             context->matchBegin = input.getPos();
1131             MATCH_NEXT();
1132         }
1133         case ByteTerm::TypeBodyAlternativeEnd:
1134             ASSERT_NOT_REACHED();
1135
1136             case ByteTerm::TypeAlternativeBegin:
1137             case ByteTerm::TypeAlternativeDisjunction: {
1138                 int offset = currentTerm().alternative.next;
1139                 context->term += offset;
1140                 if (offset > 0)
1141                     MATCH_NEXT();
1142                 BACKTRACK();
1143             }
1144             case ByteTerm::TypeAlternativeEnd: {
1145                 // We should never backtrack back into an alternative of the main body of the regex.
1146                 BackTrackInfoAlternative* backTrack = reinterpret_cast<BackTrackInfoAlternative*>(context->frame + currentTerm().frameLocation);
1147                 unsigned offset = backTrack->offset;
1148                 context->term -= offset;
1149                 BACKTRACK();
1150             }
1151
1152             case ByteTerm::TypeAssertionBOL:
1153             case ByteTerm::TypeAssertionEOL:
1154             case ByteTerm::TypeAssertionWordBoundary:
1155                 BACKTRACK();
1156
1157             case ByteTerm::TypePatternCharacterOnce:
1158             case ByteTerm::TypePatternCharacterFixed:
1159             case ByteTerm::TypePatternCharacterGreedy:
1160             case ByteTerm::TypePatternCharacterNonGreedy:
1161                 if (backtrackPatternCharacter(currentTerm(), context))
1162                     MATCH_NEXT();
1163                 BACKTRACK();
1164             case ByteTerm::TypePatternCasedCharacterOnce:
1165             case ByteTerm::TypePatternCasedCharacterFixed:
1166             case ByteTerm::TypePatternCasedCharacterGreedy:
1167             case ByteTerm::TypePatternCasedCharacterNonGreedy:
1168                 if (backtrackPatternCasedCharacter(currentTerm(), context))
1169                     MATCH_NEXT();
1170                 BACKTRACK();
1171             case ByteTerm::TypeCharacterClass:
1172                 if (backtrackCharacterClass(currentTerm(), context))
1173                     MATCH_NEXT();
1174                 BACKTRACK();
1175             case ByteTerm::TypeBackReference:
1176                 if (backtrackBackReference(currentTerm(), context))
1177                     MATCH_NEXT();
1178                 BACKTRACK();
1179             case ByteTerm::TypeParenthesesSubpattern:
1180                 if (backtrackParentheses(currentTerm(), context))
1181                     MATCH_NEXT();
1182                 BACKTRACK();
1183             case ByteTerm::TypeParenthesesSubpatternOnceBegin:
1184                 if (backtrackParenthesesOnceBegin(currentTerm(), context))
1185                     MATCH_NEXT();
1186                 BACKTRACK();
1187             case ByteTerm::TypeParenthesesSubpatternOnceEnd:
1188                 if (backtrackParenthesesOnceEnd(currentTerm(), context))
1189                     MATCH_NEXT();
1190                 BACKTRACK();
1191             case ByteTerm::TypeParentheticalAssertionBegin:
1192                 if (backtrackParentheticalAssertionBegin(currentTerm(), context))
1193                     MATCH_NEXT();
1194                 BACKTRACK();
1195             case ByteTerm::TypeParentheticalAssertionEnd:
1196                 if (backtrackParentheticalAssertionEnd(currentTerm(), context))
1197                     MATCH_NEXT();
1198                 BACKTRACK();
1199
1200             case ByteTerm::TypeCheckInput:
1201                 input.uncheckInput(currentTerm().checkInputCount);
1202                 BACKTRACK();
1203         }
1204
1205         ASSERT_NOT_REACHED();
1206         return false;
1207     }
1208
1209     bool matchNonZeroDisjunction(ByteDisjunction* disjunction, DisjunctionContext* context, bool btrack = false)
1210     {
1211         if (matchDisjunction(disjunction, context, btrack)) {
1212             while (context->matchBegin == context->matchEnd) {
1213                 if (!matchDisjunction(disjunction, context, true))
1214                     return false;
1215             }
1216             return true;
1217         }
1218
1219         return false;
1220     }
1221
1222     int interpret()
1223     {
1224         for (unsigned i = 0; i < ((pattern->m_body->m_numSubpatterns + 1) << 1); ++i)
1225             output[i] = -1;
1226
1227         DisjunctionContext* context = allocDisjunctionContext(pattern->m_body.get());
1228
1229         if (matchDisjunction(pattern->m_body.get(), context)) {
1230             output[0] = context->matchBegin;
1231             output[1] = context->matchEnd;
1232         }
1233
1234         freeDisjunctionContext(context);
1235
1236         return output[0];
1237     }
1238
1239     Interpreter(BytecodePattern* pattern, int* output, const UChar* inputChar, unsigned start, unsigned length)
1240         : pattern(pattern)
1241         , output(output)
1242         , input(inputChar, start, length)
1243     {
1244     }
1245
1246 private:
1247     BytecodePattern *pattern;
1248     int* output;
1249     InputStream input;
1250 };
1251
1252
1253
1254 class ByteCompiler {
1255     struct ParenthesesStackEntry {
1256         unsigned beginTerm;
1257         unsigned savedAlternativeIndex;
1258         ParenthesesStackEntry(unsigned beginTerm, unsigned savedAlternativeIndex/*, unsigned subpatternId, bool capture = false*/)
1259             : beginTerm(beginTerm)
1260             , savedAlternativeIndex(savedAlternativeIndex)
1261         {
1262         }
1263     };
1264
1265 public:
1266     ByteCompiler(RegexPattern& pattern)
1267         : m_pattern(pattern)
1268     {
1269         m_bodyDisjunction = 0;
1270         m_currentAlternativeIndex = 0;
1271     }
1272
1273     BytecodePattern* compile()
1274     {
1275         regexBegin(m_pattern.m_numSubpatterns, m_pattern.m_body->m_callFrameSize);
1276         emitDisjunction(m_pattern.m_body);
1277         regexEnd();
1278
1279         return new BytecodePattern(m_bodyDisjunction, m_allParenthesesInfo, m_pattern);
1280     }
1281
1282     void checkInput(unsigned count)
1283     {
1284         m_bodyDisjunction->terms.append(ByteTerm::CheckInput(count));
1285     }
1286
1287     void assertionBOL(int inputPosition)
1288     {
1289         m_bodyDisjunction->terms.append(ByteTerm::BOL(inputPosition));
1290     }
1291
1292     void assertionEOL(int inputPosition)
1293     {
1294         m_bodyDisjunction->terms.append(ByteTerm::EOL(inputPosition));
1295     }
1296
1297     void assertionWordBoundary(bool invert, int inputPosition)
1298     {
1299         m_bodyDisjunction->terms.append(ByteTerm::WordBoundary(invert, inputPosition));
1300     }
1301
1302     void atomPatternCharacter(UChar ch, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
1303     {
1304         if (m_pattern.m_ignoreCase) {
1305             UChar lo = Unicode::toLower(ch);
1306             UChar hi = Unicode::toUpper(ch);
1307
1308             if (lo != hi) {
1309                 m_bodyDisjunction->terms.append(ByteTerm(lo, hi, inputPosition, frameLocation, quantityCount, quantityType));
1310                 return;
1311             }
1312         }
1313
1314         m_bodyDisjunction->terms.append(ByteTerm(ch, inputPosition, frameLocation, quantityCount, quantityType));
1315     }
1316
1317     void atomCharacterClass(CharacterClass* characterClass, bool invert, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
1318     {
1319         m_bodyDisjunction->terms.append(ByteTerm(characterClass, invert, inputPosition));
1320
1321         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount;
1322         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType;
1323         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
1324     }
1325
1326     void atomBackReference(unsigned subpatternId, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
1327     {
1328         ASSERT(subpatternId);
1329
1330         m_bodyDisjunction->terms.append(ByteTerm::BackReference(subpatternId, inputPosition));
1331
1332         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount;
1333         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType;
1334         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
1335     }
1336
1337     void atomParenthesesSubpatternBegin(unsigned subpatternId, bool capture, int inputPosition, unsigned frameLocation, unsigned alternativeFrameLocation)
1338     {
1339         int beginTerm = m_bodyDisjunction->terms.size();
1340
1341         m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, inputPosition));
1342         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
1343         m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());
1344         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;
1345
1346         m_parenthesesStack.append(ParenthesesStackEntry(beginTerm, m_currentAlternativeIndex));
1347         m_currentAlternativeIndex = beginTerm + 1;
1348     }
1349
1350     void atomParentheticalAssertionBegin(unsigned subpatternId, bool invert, unsigned frameLocation, unsigned alternativeFrameLocation)
1351     {
1352         int beginTerm = m_bodyDisjunction->terms.size();
1353
1354         m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParentheticalAssertionBegin, subpatternId, invert, 0));
1355         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
1356         m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());
1357         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;
1358
1359         m_parenthesesStack.append(ParenthesesStackEntry(beginTerm, m_currentAlternativeIndex));
1360         m_currentAlternativeIndex = beginTerm + 1;
1361     }
1362
1363     unsigned popParenthesesStack()
1364     {
1365         ASSERT(m_parenthesesStack.size());
1366         int stackEnd = m_parenthesesStack.size() - 1;
1367         unsigned beginTerm = m_parenthesesStack[stackEnd].beginTerm;
1368         m_currentAlternativeIndex = m_parenthesesStack[stackEnd].savedAlternativeIndex;
1369         m_parenthesesStack.shrink(stackEnd);
1370
1371         ASSERT(beginTerm < m_bodyDisjunction->terms.size());
1372         ASSERT(m_currentAlternativeIndex < m_bodyDisjunction->terms.size());
1373
1374         return beginTerm;
1375     }
1376
1377 #ifndef NDEBUG
1378     void dumpDisjunction(ByteDisjunction* disjunction)
1379     {
1380         printf("ByteDisjunction(%p):\n\t", disjunction);
1381         for (unsigned i = 0; i < disjunction->terms.size(); ++i)
1382             printf("{ %d } ", disjunction->terms[i].type);
1383         printf("\n");
1384     }
1385 #endif
1386
1387     void closeAlternative(int beginTerm)
1388     {
1389         int origBeginTerm = beginTerm;
1390         ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeAlternativeBegin);
1391         int endIndex = m_bodyDisjunction->terms.size();
1392
1393         unsigned frameLocation = m_bodyDisjunction->terms[beginTerm].frameLocation;
1394
1395         if (!m_bodyDisjunction->terms[beginTerm].alternative.next)
1396             m_bodyDisjunction->terms.remove(beginTerm);
1397         else {
1398             while (m_bodyDisjunction->terms[beginTerm].alternative.next) {
1399                 beginTerm += m_bodyDisjunction->terms[beginTerm].alternative.next;
1400                 ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeAlternativeDisjunction);
1401                 m_bodyDisjunction->terms[beginTerm].alternative.end = endIndex - beginTerm;
1402                 m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;
1403             }
1404
1405             m_bodyDisjunction->terms[beginTerm].alternative.next = origBeginTerm - beginTerm;
1406
1407             m_bodyDisjunction->terms.append(ByteTerm::AlternativeEnd());
1408             m_bodyDisjunction->terms[endIndex].frameLocation = frameLocation;
1409         }
1410     }
1411
1412     void closeBodyAlternative()
1413     {
1414         int beginTerm = 0;
1415         int origBeginTerm = 0;
1416         ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeBodyAlternativeBegin);
1417         int endIndex = m_bodyDisjunction->terms.size();
1418
1419         unsigned frameLocation = m_bodyDisjunction->terms[beginTerm].frameLocation;
1420
1421         while (m_bodyDisjunction->terms[beginTerm].alternative.next) {
1422             beginTerm += m_bodyDisjunction->terms[beginTerm].alternative.next;
1423             ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeBodyAlternativeDisjunction);
1424             m_bodyDisjunction->terms[beginTerm].alternative.end = endIndex - beginTerm;
1425             m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;
1426         }
1427
1428         m_bodyDisjunction->terms[beginTerm].alternative.next = origBeginTerm - beginTerm;
1429
1430         m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeEnd());
1431         m_bodyDisjunction->terms[endIndex].frameLocation = frameLocation;
1432     }
1433
1434     void atomParenthesesEnd(bool doInline, unsigned lastSubpatternId, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType, unsigned callFrameSize = 0)
1435     {
1436         unsigned beginTerm = popParenthesesStack();
1437         closeAlternative(beginTerm + 1);
1438         unsigned endTerm = m_bodyDisjunction->terms.size();
1439
1440         bool isAssertion = m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeParentheticalAssertionBegin;
1441         bool invertOrCapture = m_bodyDisjunction->terms[beginTerm].invertOrCapture;
1442         unsigned subpatternId = m_bodyDisjunction->terms[beginTerm].atom.subpatternId;
1443
1444         m_bodyDisjunction->terms.append(ByteTerm(isAssertion ? ByteTerm::TypeParentheticalAssertionEnd : ByteTerm::TypeParenthesesSubpatternOnceEnd, subpatternId, invertOrCapture, inputPosition));
1445         m_bodyDisjunction->terms[beginTerm].atom.parenthesesWidth = endTerm - beginTerm;
1446         m_bodyDisjunction->terms[endTerm].atom.parenthesesWidth = endTerm - beginTerm;
1447         m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation;
1448
1449         if (doInline) {
1450             m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount;
1451             m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
1452             m_bodyDisjunction->terms[endTerm].atom.quantityCount = quantityCount;
1453             m_bodyDisjunction->terms[endTerm].atom.quantityType = quantityType;
1454         } else {
1455             ByteTerm& parenthesesBegin = m_bodyDisjunction->terms[beginTerm];
1456             ASSERT(parenthesesBegin.type == ByteTerm::TypeParenthesesSubpatternOnceBegin);
1457
1458             bool invertOrCapture = parenthesesBegin.invertOrCapture;
1459             unsigned subpatternId = parenthesesBegin.atom.subpatternId;
1460
1461             unsigned numSubpatterns = lastSubpatternId - subpatternId + 1;
1462             ByteDisjunction* parenthesesDisjunction = new ByteDisjunction(numSubpatterns, callFrameSize);
1463
1464             parenthesesDisjunction->terms.append(ByteTerm::SubpatternBegin());
1465             for (unsigned termInParentheses = beginTerm + 1; termInParentheses < endTerm; ++termInParentheses)
1466                 parenthesesDisjunction->terms.append(m_bodyDisjunction->terms[termInParentheses]);
1467             parenthesesDisjunction->terms.append(ByteTerm::SubpatternEnd());
1468
1469             m_bodyDisjunction->terms.shrink(beginTerm);
1470
1471             m_allParenthesesInfo.append(parenthesesDisjunction);
1472             m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, invertOrCapture, inputPosition));
1473
1474             m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount;
1475             m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
1476             m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;
1477         }
1478     }
1479
1480     void regexBegin(unsigned numSubpatterns, unsigned callFrameSize)
1481     {
1482         m_bodyDisjunction = new ByteDisjunction(numSubpatterns, callFrameSize);
1483         m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeBegin());
1484         m_bodyDisjunction->terms[0].frameLocation = 0;
1485         m_currentAlternativeIndex = 0;
1486     }
1487
1488     void regexEnd()
1489     {
1490         closeBodyAlternative();
1491     }
1492
1493     void alternativeBodyDisjunction()
1494     {
1495         int newAlternativeIndex = m_bodyDisjunction->terms.size();
1496         m_bodyDisjunction->terms[m_currentAlternativeIndex].alternative.next = newAlternativeIndex - m_currentAlternativeIndex;
1497         m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeDisjunction());
1498
1499         m_currentAlternativeIndex = newAlternativeIndex;
1500     }
1501
1502     void alternativeDisjunction()
1503     {
1504         int newAlternativeIndex = m_bodyDisjunction->terms.size();
1505         m_bodyDisjunction->terms[m_currentAlternativeIndex].alternative.next = newAlternativeIndex - m_currentAlternativeIndex;
1506         m_bodyDisjunction->terms.append(ByteTerm::AlternativeDisjunction());
1507
1508         m_currentAlternativeIndex = newAlternativeIndex;
1509     }
1510
1511     void emitDisjunction(PatternDisjunction* disjunction, unsigned inputCountAlreadyChecked = 0, unsigned parenthesesInputCountAlreadyChecked = 0)
1512     {
1513         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
1514             unsigned currentCountAlreadyChecked = inputCountAlreadyChecked;
1515
1516             if (alt) {
1517                 if (disjunction == m_pattern.m_body)
1518                     alternativeBodyDisjunction();
1519                 else
1520                     alternativeDisjunction();
1521             }
1522
1523             PatternAlternative* alternative = disjunction->m_alternatives[alt];
1524             unsigned minimumSize = alternative->m_minimumSize;
1525
1526             ASSERT(minimumSize >= parenthesesInputCountAlreadyChecked);
1527             unsigned countToCheck = minimumSize - parenthesesInputCountAlreadyChecked;
1528             if (countToCheck)
1529                 checkInput(countToCheck);
1530             currentCountAlreadyChecked += countToCheck;
1531
1532             for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
1533                 PatternTerm& term = alternative->m_terms[i];
1534
1535                 switch (term.type) {
1536                 case PatternTerm::TypeAssertionBOL:
1537                     assertionBOL(term.inputPosition - currentCountAlreadyChecked);
1538                     break;
1539
1540                 case PatternTerm::TypeAssertionEOL:
1541                     assertionEOL(term.inputPosition - currentCountAlreadyChecked);
1542                     break;
1543
1544                 case PatternTerm::TypeAssertionWordBoundary:
1545                     assertionWordBoundary(term.invertOrCapture, term.inputPosition - currentCountAlreadyChecked);
1546                     break;
1547
1548                 case PatternTerm::TypePatternCharacter:
1549                     atomPatternCharacter(term.patternCharacter, term.inputPosition - currentCountAlreadyChecked, term.frameLocation, term.quantityCount, term.quantityType);
1550                     break;
1551
1552                 case PatternTerm::TypeCharacterClass:
1553                     atomCharacterClass(term.characterClass, term.invertOrCapture, term.inputPosition - currentCountAlreadyChecked, term.frameLocation, term.quantityCount, term.quantityType);
1554                     break;
1555
1556                 case PatternTerm::TypeBackReference:
1557                     atomBackReference(term.subpatternId, term.inputPosition - currentCountAlreadyChecked, term.frameLocation, term.quantityCount, term.quantityType);
1558                         break;
1559
1560                 case PatternTerm::TypeForwardReference:
1561                     break;
1562
1563                 case PatternTerm::TypeParenthesesSubpattern: {
1564                     unsigned disjunctionAlreadyCheckedCount = 0;
1565                     if ((term.quantityCount == 1) && !term.parentheses.isCopy) {
1566                         if (term.quantityType == QuantifierFixedCount) {
1567                             disjunctionAlreadyCheckedCount = term.parentheses.disjunction->m_minimumSize;
1568                             unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
1569                             atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, term.frameLocation);
1570                             emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, term.parentheses.disjunction->m_minimumSize);
1571                             atomParenthesesEnd(true, term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
1572                         } else {
1573                             unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
1574                             atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, term.frameLocation + RegexStackSpaceForBackTrackInfoParenthesesOnce);
1575                             emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0);
1576                             atomParenthesesEnd(true, term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
1577                         }
1578                     } else {
1579                         unsigned delegateEndInputOffset = term.inputPosition - currentCountAlreadyChecked;
1580                         atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.invertOrCapture, delegateEndInputOffset - disjunctionAlreadyCheckedCount, term.frameLocation, 0);
1581                         emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0);
1582                         atomParenthesesEnd(false, term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
1583                     }
1584                     break;
1585                 }
1586
1587                 case PatternTerm::TypeParentheticalAssertion: {
1588                     unsigned alternativeFrameLocation = term.inputPosition + RegexStackSpaceForBackTrackInfoParentheticalAssertion;
1589
1590                     atomParentheticalAssertionBegin(term.parentheses.subpatternId, term.invertOrCapture, term.frameLocation, alternativeFrameLocation);
1591                     emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0);
1592                     atomParenthesesEnd(true, term.parentheses.lastSubpatternId, 0, term.frameLocation, term.quantityCount, term.quantityType);
1593                     break;
1594                 }
1595                 }
1596             }
1597         }
1598     }
1599
1600 private:
1601     RegexPattern& m_pattern;
1602     ByteDisjunction* m_bodyDisjunction;
1603     unsigned m_currentAlternativeIndex;
1604     Vector<ParenthesesStackEntry> m_parenthesesStack;
1605     Vector<ByteDisjunction*> m_allParenthesesInfo;
1606 };
1607
1608
1609 BytecodePattern* byteCompileRegex(const UString& patternString, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline)
1610 {
1611     RegexPattern pattern(ignoreCase, multiline);
1612
1613     if ((error = compileRegex(patternString, pattern)))
1614         return 0;
1615
1616     numSubpatterns = pattern.m_numSubpatterns;
1617
1618     return ByteCompiler(pattern).compile();
1619 }
1620
1621 int interpretRegex(BytecodePattern* regex, const UChar* input, unsigned start, unsigned length, int* output)
1622 {
1623     return Interpreter(regex, output, input, start, length).interpret();
1624 }
1625
1626
1627 COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoPatternCharacter) == (RegexStackSpaceForBackTrackInfoPatternCharacter * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoPatternCharacter);
1628 COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoCharacterClass) == (RegexStackSpaceForBackTrackInfoCharacterClass * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoCharacterClass);
1629 COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoBackReference) == (RegexStackSpaceForBackTrackInfoBackReference * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoBackReference);
1630 COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoAlternative) == (RegexStackSpaceForBackTrackInfoAlternative * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoAlternative);
1631 COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoParentheticalAssertion) == (RegexStackSpaceForBackTrackInfoParentheticalAssertion * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoParentheticalAssertion);
1632 COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoParenthesesOnce) == (RegexStackSpaceForBackTrackInfoParenthesesOnce * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoParenthesesOnce);
1633 COMPILE_ASSERT(sizeof(Interpreter::BackTrackInfoParentheses) == (RegexStackSpaceForBackTrackInfoParentheses * sizeof(uintptr_t)), CheckRegexStackSpaceForBackTrackInfoParentheses);
1634
1635
1636 } }
1637
1638 #endif