js/src/yarr/yarr/RegexJIT.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 "RegexJIT.h"
  27
  28 #if ENABLE_ASSEMBLER
  29
  30 #include "assembler/assembler/LinkBuffer.h"
  31 #include "assembler/assembler/MacroAssembler.h"
  32 #include "RegexCompiler.h"
  33
  34 #include "yarr/pcre/pcre.h" // temporary, remove when fallback is removed.
  35
  36 using namespace WTF;
  37
  38 namespace JSC { namespace Yarr {
  39
  40 class JSGlobalData;
  41
  42 class RegexGenerator : private MacroAssembler {
  43     friend void jitCompileRegex(JSGlobalData* globalData, RegexCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);
  44
  45 #if WTF_CPU_ARM
  46     static const RegisterID input = ARMRegisters::r0;
  47     static const RegisterID index = ARMRegisters::r1;
  48     static const RegisterID length = ARMRegisters::r2;
  49     static const RegisterID output = ARMRegisters::r4;
  50
  51     static const RegisterID regT0 = ARMRegisters::r5;
  52     static const RegisterID regT1 = ARMRegisters::r6;
  53
  54     static const RegisterID returnRegister = ARMRegisters::r0;
  55 #elif WTF_CPU_MIPS
  56     static const RegisterID input = MIPSRegisters::a0;
  57     static const RegisterID index = MIPSRegisters::a1;
  58     static const RegisterID length = MIPSRegisters::a2;
  59     static const RegisterID output = MIPSRegisters::a3;
  60
  61     static const RegisterID regT0 = MIPSRegisters::t4;
  62     static const RegisterID regT1 = MIPSRegisters::t5;
  63
  64     static const RegisterID returnRegister = MIPSRegisters::v0;
  65 #elif WTF_CPU_X86
  66     static const RegisterID input = X86Registers::eax;
  67     static const RegisterID index = X86Registers::edx;
  68     static const RegisterID length = X86Registers::ecx;
  69     static const RegisterID output = X86Registers::edi;
  70
  71     static const RegisterID regT0 = X86Registers::ebx;
  72     static const RegisterID regT1 = X86Registers::esi;
  73
  74     static const RegisterID returnRegister = X86Registers::eax;
  75 #elif WTF_CPU_X86_64
  76 #if WTF_PLATFORM_WIN
  77     static const RegisterID input = X86Registers::ecx;
  78     static const RegisterID index = X86Registers::edx;
  79     static const RegisterID length = X86Registers::r8;
  80     static const RegisterID output = X86Registers::r9;
  81 #else
  82     static const RegisterID input = X86Registers::edi;
  83     static const RegisterID index = X86Registers::esi;
  84     static const RegisterID length = X86Registers::edx;
  85     static const RegisterID output = X86Registers::ecx;
  86 #endif
  87
  88     static const RegisterID regT0 = X86Registers::eax;
  89     static const RegisterID regT1 = X86Registers::ebx;
  90
  91     static const RegisterID returnRegister = X86Registers::eax;
  92 #endif
  93
  94     void optimizeAlternative(PatternAlternative* alternative)
  95     {
  96         if (!alternative->m_terms.length())
  97             return;
  98
  99         for (unsigned i = 0; i < alternative->m_terms.length() - 1; ++i) {
 100             PatternTerm& term = alternative->m_terms[i];
 101             PatternTerm& nextTerm = alternative->m_terms[i + 1];
 102
 103             if ((term.type == PatternTerm::TypeCharacterClass)
 104                 && (term.quantityType == QuantifierFixedCount)
 105                 && (nextTerm.type == PatternTerm::TypePatternCharacter)
 106                 && (nextTerm.quantityType == QuantifierFixedCount)) {
 107                 PatternTerm termCopy = term;
 108                 alternative->m_terms[i] = nextTerm;
 109                 alternative->m_terms[i + 1] = termCopy;
 110             }
 111         }
 112     }
 113
 114     void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
 115     {
 116         do {
 117             // pick which range we're going to generate
 118             int which = count >> 1;
 119             char lo = ranges[which].begin;
 120             char hi = ranges[which].end;
 121
 122             // check if there are any ranges or matches below lo.  If not, just jl to failure -
 123             // if there is anything else to check, check that first, if it falls through jmp to failure.
 124             if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
 125                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
 126
 127                 // generate code for all ranges before this one
 128                 if (which)
 129                     matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
 130
 131                 while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
 132                     matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
 133                     ++*matchIndex;
 134                 }
 135                 failures.append(jump());
 136
 137                 loOrAbove.link(this);
 138             } else if (which) {
 139                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
 140
 141                 matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
 142                 failures.append(jump());
 143
 144                 loOrAbove.link(this);
 145             } else
 146                 failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));
 147
 148             while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
 149                 ++*matchIndex;
 150
 151             matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
 152             // fall through to here, the value is above hi.
 153
 154             // shuffle along & loop around if there are any more matches to handle.
 155             unsigned next = which + 1;
 156             ranges += next;
 157             count -= next;
 158         } while (count);
 159     }
 160
 161     void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
 162     {
 163         if (charClass->m_table) {
 164             ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table));
 165             matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry));
 166             return;
 167         }
 168         Jump unicodeFail;
 169         if (charClass->m_matchesUnicode.length() || charClass->m_rangesUnicode.length()) {
 170             Jump isAscii = branch32(LessThanOrEqual, character, Imm32(0x7f));
 171
 172             if (charClass->m_matchesUnicode.length()) {
 173                 for (unsigned i = 0; i < charClass->m_matchesUnicode.length(); ++i) {
 174                     UChar ch = charClass->m_matchesUnicode[i];
 175                     matchDest.append(branch32(Equal, character, Imm32(ch)));
 176                 }
 177             }
 178
 179             if (charClass->m_rangesUnicode.length()) {
 180                 for (unsigned i = 0; i < charClass->m_rangesUnicode.length(); ++i) {
 181                     UChar lo = charClass->m_rangesUnicode[i].begin;
 182                     UChar hi = charClass->m_rangesUnicode[i].end;
 183
 184                     Jump below = branch32(LessThan, character, Imm32(lo));
 185                     matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
 186                     below.link(this);
 187                 }
 188             }
 189
 190             unicodeFail = jump();
 191             isAscii.link(this);
 192         }
 193
 194         if (charClass->m_ranges.length()) {
 195             unsigned matchIndex = 0;
 196             JumpList failures;
 197             matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.length(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.length());
 198             while (matchIndex < charClass->m_matches.length())
 199                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
 200
 201             failures.link(this);
 202         } else if (charClass->m_matches.length()) {
 203             // optimization: gather 'a','A' etc back together, can mask & test once.
 204             js::Vector<char, 16, js::SystemAllocPolicy> matchesAZaz;
 205
 206             for (unsigned i = 0; i < charClass->m_matches.length(); ++i) {
 207                 char ch = charClass->m_matches[i];
 208                 if (m_pattern.m_ignoreCase) {
 209                     if (isASCIILower(ch)) {
 210                         matchesAZaz.append(ch);
 211                         continue;
 212                     }
 213                     if (isASCIIUpper(ch))
 214                         continue;
 215                 }
 216                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
 217             }
 218
 219             if (unsigned countAZaz = matchesAZaz.length()) {
 220                 or32(Imm32(32), character);
 221                 for (unsigned i = 0; i < countAZaz; ++i)
 222                     matchDest.append(branch32(Equal, character, Imm32(matchesAZaz[i])));
 223             }
 224         }
 225
 226         if (charClass->m_matchesUnicode.length() || charClass->m_rangesUnicode.length())
 227             unicodeFail.link(this);
 228     }
 229
 230     // Jumps if input not available; will have (incorrectly) incremented already!
 231     Jump jumpIfNoAvailableInput(unsigned countToCheck)
 232     {
 233         add32(Imm32(countToCheck), index);
 234         return branch32(Above, index, length);
 235     }
 236
 237     Jump jumpIfAvailableInput(unsigned countToCheck)
 238     {
 239         add32(Imm32(countToCheck), index);
 240         return branch32(BelowOrEqual, index, length);
 241     }
 242
 243     Jump checkInput()
 244     {
 245         return branch32(BelowOrEqual, index, length);
 246     }
 247
 248     Jump atEndOfInput()
 249     {
 250         return branch32(Equal, index, length);
 251     }
 252
 253     Jump notAtEndOfInput()
 254     {
 255         return branch32(NotEqual, index, length);
 256     }
 257
 258     Jump jumpIfCharEquals(UChar ch, int inputPosition)
 259     {
 260         return branch16(Equal, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
 261     }
 262
 263     Jump jumpIfCharNotEquals(UChar ch, int inputPosition)
 264     {
 265         return branch16(NotEqual, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
 266     }
 267
 268     void readCharacter(int inputPosition, RegisterID reg)
 269     {
 270         load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
 271     }
 272
 273     void storeToFrame(RegisterID reg, unsigned frameLocation)
 274     {
 275         poke(reg, frameLocation);
 276     }
 277
 278     void storeToFrame(Imm32 imm, unsigned frameLocation)
 279     {
 280         poke(imm, frameLocation);
 281     }
 282
 283     DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
 284     {
 285         return storePtrWithPatch(ImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
 286     }
 287
 288     void loadFromFrame(unsigned frameLocation, RegisterID reg)
 289     {
 290         peek(reg, frameLocation);
 291     }
 292
 293     void loadFromFrameAndJump(unsigned frameLocation)
 294     {
 295         jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
 296     }
 297
 298     struct AlternativeBacktrackRecord {
 299         DataLabelPtr dataLabel;
 300         Label backtrackLocation;
 301
 302         AlternativeBacktrackRecord(DataLabelPtr dataLabel, Label backtrackLocation)
 303             : dataLabel(dataLabel)
 304             , backtrackLocation(backtrackLocation)
 305         {
 306         }
 307     };
 308
 309     struct TermGenerationState {
 310         TermGenerationState(PatternDisjunction* disjunction, unsigned checkedTotal)
 311             : disjunction(disjunction)
 312             , checkedTotal(checkedTotal)
 313         {
 314         }
 315
 316         void resetAlternative()
 317         {
 318             isBackTrackGenerated = false;
 319             alt = 0;
 320         }
 321         bool alternativeValid()
 322         {
 323             return alt < disjunction->m_alternatives.length();
 324         }
 325         void nextAlternative()
 326         {
 327             ++alt;
 328         }
 329         PatternAlternative* alternative()
 330         {
 331             return disjunction->m_alternatives[alt];
 332         }
 333
 334         void resetTerm()
 335         {
 336             ASSERT(alternativeValid());
 337             t = 0;
 338         }
 339         bool termValid()
 340         {
 341             ASSERT(alternativeValid());
 342             return t < alternative()->m_terms.length();
 343         }
 344         void nextTerm()
 345         {
 346             ASSERT(alternativeValid());
 347             ++t;
 348         }
 349         PatternTerm& term()
 350         {
 351             ASSERT(alternativeValid());
 352             return alternative()->m_terms[t];
 353         }
 354         bool isLastTerm()
 355         {
 356             ASSERT(alternativeValid());
 357             return (t + 1) == alternative()->m_terms.length();
 358         }
 359         bool isMainDisjunction()
 360         {
 361             return !disjunction->m_parent;
 362         }
 363
 364         PatternTerm& lookaheadTerm()
 365         {
 366             ASSERT(alternativeValid());
 367             ASSERT((t + 1) < alternative()->m_terms.length());
 368             return alternative()->m_terms[t + 1];
 369         }
 370         bool isSinglePatternCharacterLookaheadTerm()
 371         {
 372             ASSERT(alternativeValid());
 373             return ((t + 1) < alternative()->m_terms.length())
 374                 && (lookaheadTerm().type == PatternTerm::TypePatternCharacter)
 375                 && (lookaheadTerm().quantityType == QuantifierFixedCount)
 376                 && (lookaheadTerm().quantityCount == 1);
 377         }
 378
 379         int inputOffset()
 380         {
 381             return term().inputPosition - checkedTotal;
 382         }
 383
 384         void jumpToBacktrack(Jump jump, MacroAssembler* masm)
 385         {
 386             if (isBackTrackGenerated)
 387                 jump.linkTo(backtrackLabel, masm);
 388             else
 389                 backTrackJumps.append(jump);
 390         }
 391         void jumpToBacktrack(JumpList& jumps, MacroAssembler* masm)
 392         {
 393             if (isBackTrackGenerated)
 394                 jumps.linkTo(backtrackLabel, masm);
 395             else
 396                 backTrackJumps.append(jumps);
 397         }
 398         bool plantJumpToBacktrackIfExists(MacroAssembler* masm)
 399         {
 400             if (isBackTrackGenerated) {
 401                 masm->jump(backtrackLabel);
 402                 return true;
 403             }
 404             return false;
 405         }
 406         void addBacktrackJump(Jump jump)
 407         {
 408             backTrackJumps.append(jump);
 409         }
 410         void setBacktrackGenerated(Label label)
 411         {
 412             isBackTrackGenerated = true;
 413             backtrackLabel = label;
 414         }
 415         void linkAlternativeBacktracks(MacroAssembler* masm)
 416         {
 417             isBackTrackGenerated = false;
 418             backTrackJumps.link(masm);
 419         }
 420         void linkAlternativeBacktracksTo(Label label, MacroAssembler* masm)
 421         {
 422             isBackTrackGenerated = false;
 423             backTrackJumps.linkTo(label, masm);
 424         }
 425         void propagateBacktrackingFrom(TermGenerationState& nestedParenthesesState, MacroAssembler* masm)
 426         {
 427             jumpToBacktrack(nestedParenthesesState.backTrackJumps, masm);
 428             if (nestedParenthesesState.isBackTrackGenerated)
 429                 setBacktrackGenerated(nestedParenthesesState.backtrackLabel);
 430         }
 431
 432         PatternDisjunction* disjunction;
 433         int checkedTotal;
 434     private:
 435         unsigned alt;
 436         unsigned t;
 437         JumpList backTrackJumps;
 438         Label backtrackLabel;
 439         bool isBackTrackGenerated;
 440     };
 441
 442     void generateAssertionBOL(TermGenerationState& state)
 443     {
 444         PatternTerm& term = state.term();
 445
 446         if (m_pattern.m_multiline) {
 447             const RegisterID character = regT0;
 448
 449             JumpList matchDest;
 450             if (!term.inputPosition)
 451                 matchDest.append(branch32(Equal, index, Imm32(state.checkedTotal)));
 452
 453             readCharacter(state.inputOffset() - 1, character);
 454             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
 455             state.jumpToBacktrack(jump(), this);
 456
 457             matchDest.link(this);
 458         } else {
 459             // Erk, really should poison out these alternatives early. :-/
 460             if (term.inputPosition)
 461                 state.jumpToBacktrack(jump(), this);
 462             else
 463                 state.jumpToBacktrack(branch32(NotEqual, index, Imm32(state.checkedTotal)), this);
 464         }
 465     }
 466
 467     void generateAssertionEOL(TermGenerationState& state)
 468     {
 469         PatternTerm& term = state.term();
 470
 471         if (m_pattern.m_multiline) {
 472             const RegisterID character = regT0;
 473
 474             JumpList matchDest;
 475             if (term.inputPosition == state.checkedTotal)
 476                 matchDest.append(atEndOfInput());
 477
 478             readCharacter(state.inputOffset(), character);
 479             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
 480             state.jumpToBacktrack(jump(), this);
 481
 482             matchDest.link(this);
 483         } else {
 484             if (term.inputPosition == state.checkedTotal)
 485                 state.jumpToBacktrack(notAtEndOfInput(), this);
 486             // Erk, really should poison out these alternatives early. :-/
 487             else
 488                 state.jumpToBacktrack(jump(), this);
 489         }
 490     }
 491
 492     // Also falls though on nextIsNotWordChar.
 493     void matchAssertionWordchar(TermGenerationState& state, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
 494     {
 495         const RegisterID character = regT0;
 496         PatternTerm& term = state.term();
 497
 498         if (term.inputPosition == state.checkedTotal)
 499             nextIsNotWordChar.append(atEndOfInput());
 500
 501         readCharacter(state.inputOffset(), character);
 502         matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
 503     }
 504
 505     void generateAssertionWordBoundary(TermGenerationState& state)
 506     {
 507         const RegisterID character = regT0;
 508         PatternTerm& term = state.term();
 509
 510         Jump atBegin;
 511         JumpList matchDest;
 512         if (!term.inputPosition)
 513             atBegin = branch32(Equal, index, Imm32(state.checkedTotal));
 514         readCharacter(state.inputOffset() - 1, character);
 515         matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
 516         if (!term.inputPosition)
 517             atBegin.link(this);
 518
 519         // We fall through to here if the last character was not a wordchar.
 520         JumpList nonWordCharThenWordChar;
 521         JumpList nonWordCharThenNonWordChar;
 522         if (term.invertOrCapture) {
 523             matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
 524             nonWordCharThenWordChar.append(jump());
 525         } else {
 526             matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
 527             nonWordCharThenNonWordChar.append(jump());
 528         }
 529         state.jumpToBacktrack(nonWordCharThenNonWordChar, this);
 530
 531         // We jump here if the last character was a wordchar.
 532         matchDest.link(this);
 533         JumpList wordCharThenWordChar;
 534         JumpList wordCharThenNonWordChar;
 535         if (term.invertOrCapture) {
 536             matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
 537             wordCharThenWordChar.append(jump());
 538         } else {
 539             matchAssertionWordchar(state, wordCharThenWordChar, wordCharThenNonWordChar);
 540             // This can fall-though!
 541         }
 542
 543         state.jumpToBacktrack(wordCharThenWordChar, this);
 544
 545         nonWordCharThenWordChar.link(this);
 546         wordCharThenNonWordChar.link(this);
 547     }
 548
 549     void generatePatternCharacterSingle(TermGenerationState& state)
 550     {
 551         const RegisterID character = regT0;
 552         UChar ch = state.term().patternCharacter;
 553
 554         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
 555             readCharacter(state.inputOffset(), character);
 556             or32(Imm32(32), character);
 557             state.jumpToBacktrack(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))), this);
 558         } else {
 559             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
 560             state.jumpToBacktrack(jumpIfCharNotEquals(ch, state.inputOffset()), this);
 561         }
 562     }
 563
 564     void generatePatternCharacterPair(TermGenerationState& state)
 565     {
 566         const RegisterID character = regT0;
 567         UChar ch1 = state.term().patternCharacter;
 568         UChar ch2 = state.lookaheadTerm().patternCharacter;
 569
 570         int mask = 0;
 571         int chPair = ch1 | (ch2 << 16);
 572
 573         if (m_pattern.m_ignoreCase) {
 574             if (isASCIIAlpha(ch1))
 575                 mask |= 32;
 576             if (isASCIIAlpha(ch2))
 577                 mask |= 32 << 16;
 578         }
 579
 580         if (mask) {
 581             load32WithUnalignedHalfWords(BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), character);
 582             or32(Imm32(mask), character);
 583             state.jumpToBacktrack(branch32(NotEqual, character, Imm32(chPair | mask)), this);
 584         } else
 585             state.jumpToBacktrack(branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)), this);
 586     }
 587
 588     void generatePatternCharacterFixed(TermGenerationState& state)
 589     {
 590         const RegisterID character = regT0;
 591         const RegisterID countRegister = regT1;
 592         PatternTerm& term = state.term();
 593         UChar ch = term.patternCharacter;
 594
 595         move(index, countRegister);
 596         sub32(Imm32(term.quantityCount), countRegister);
 597
 598         Label loop(this);
 599         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
 600             load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
 601             or32(Imm32(32), character);
 602             state.jumpToBacktrack(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))), this);
 603         } else {
 604             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
 605             state.jumpToBacktrack(branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)), this);
 606         }
 607         add32(Imm32(1), countRegister);
 608         branch32(NotEqual, countRegister, index).linkTo(loop, this);
 609     }
 610
 611     void generatePatternCharacterGreedy(TermGenerationState& state)
 612     {
 613         const RegisterID character = regT0;
 614         const RegisterID countRegister = regT1;
 615         PatternTerm& term = state.term();
 616         UChar ch = term.patternCharacter;
 617
 618         move(Imm32(0), countRegister);
 619
 620         JumpList failures;
 621         Label loop(this);
 622         failures.append(atEndOfInput());
 623         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
 624             readCharacter(state.inputOffset(), character);
 625             or32(Imm32(32), character);
 626             failures.append(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
 627         } else {
 628             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
 629             failures.append(jumpIfCharNotEquals(ch, state.inputOffset()));
 630         }
 631
 632         add32(Imm32(1), countRegister);
 633         add32(Imm32(1), index);
 634         if (term.quantityCount != 0xffffffff) {
 635             branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
 636             failures.append(jump());
 637         } else
 638             jump(loop);
 639
 640         Label backtrackBegin(this);
 641         loadFromFrame(term.frameLocation, countRegister);
 642         state.jumpToBacktrack(branchTest32(Zero, countRegister), this);
 643         sub32(Imm32(1), countRegister);
 644         sub32(Imm32(1), index);
 645
 646         failures.link(this);
 647
 648         storeToFrame(countRegister, term.frameLocation);
 649
 650         state.setBacktrackGenerated(backtrackBegin);
 651     }
 652
 653     void generatePatternCharacterNonGreedy(TermGenerationState& state)
 654     {
 655         const RegisterID character = regT0;
 656         const RegisterID countRegister = regT1;
 657         PatternTerm& term = state.term();
 658         UChar ch = term.patternCharacter;
 659
 660         move(Imm32(0), countRegister);
 661
 662         Jump firstTimeDoNothing = jump();
 663
 664         Label hardFail(this);
 665         sub32(countRegister, index);
 666         state.jumpToBacktrack(jump(), this);
 667
 668         Label backtrackBegin(this);
 669         loadFromFrame(term.frameLocation, countRegister);
 670
 671         atEndOfInput().linkTo(hardFail, this);
 672         if (term.quantityCount != 0xffffffff)
 673             branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
 674         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
 675             readCharacter(state.inputOffset(), character);
 676             or32(Imm32(32), character);
 677             branch32(NotEqual, character, Imm32(Unicode::toLower(ch))).linkTo(hardFail, this);
 678         } else {
 679             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
 680             jumpIfCharNotEquals(ch, state.inputOffset()).linkTo(hardFail, this);
 681         }
 682
 683         add32(Imm32(1), countRegister);
 684         add32(Imm32(1), index);
 685
 686         firstTimeDoNothing.link(this);
 687         storeToFrame(countRegister, term.frameLocation);
 688
 689         state.setBacktrackGenerated(backtrackBegin);
 690     }
 691
 692     void generateCharacterClassSingle(TermGenerationState& state)
 693     {
 694         const RegisterID character = regT0;
 695         PatternTerm& term = state.term();
 696
 697         JumpList matchDest;
 698         readCharacter(state.inputOffset(), character);
 699         matchCharacterClass(character, matchDest, term.characterClass);
 700
 701         if (term.invertOrCapture)
 702             state.jumpToBacktrack(matchDest, this);
 703         else {
 704             state.jumpToBacktrack(jump(), this);
 705             matchDest.link(this);
 706         }
 707     }
 708
 709     void generateCharacterClassFixed(TermGenerationState& state)
 710     {
 711         const RegisterID character = regT0;
 712         const RegisterID countRegister = regT1;
 713         PatternTerm& term = state.term();
 714
 715         move(index, countRegister);
 716         sub32(Imm32(term.quantityCount), countRegister);
 717
 718         Label loop(this);
 719         JumpList matchDest;
 720         load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
 721         matchCharacterClass(character, matchDest, term.characterClass);
 722
 723         if (term.invertOrCapture)
 724             state.jumpToBacktrack(matchDest, this);
 725         else {
 726             state.jumpToBacktrack(jump(), this);
 727             matchDest.link(this);
 728         }
 729
 730         add32(Imm32(1), countRegister);
 731         branch32(NotEqual, countRegister, index).linkTo(loop, this);
 732     }
 733
 734     void generateCharacterClassGreedy(TermGenerationState& state)
 735     {
 736         const RegisterID character = regT0;
 737         const RegisterID countRegister = regT1;
 738         PatternTerm& term = state.term();
 739
 740         move(Imm32(0), countRegister);
 741
 742         JumpList failures;
 743         Label loop(this);
 744         failures.append(atEndOfInput());
 745
 746         if (term.invertOrCapture) {
 747             readCharacter(state.inputOffset(), character);
 748             matchCharacterClass(character, failures, term.characterClass);
 749         } else {
 750             JumpList matchDest;
 751             readCharacter(state.inputOffset(), character);
 752             matchCharacterClass(character, matchDest, term.characterClass);
 753             failures.append(jump());
 754             matchDest.link(this);
 755         }
 756
 757         add32(Imm32(1), countRegister);
 758         add32(Imm32(1), index);
 759         if (term.quantityCount != 0xffffffff) {
 760             branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
 761             failures.append(jump());
 762         } else
 763             jump(loop);
 764
 765         Label backtrackBegin(this);
 766         loadFromFrame(term.frameLocation, countRegister);
 767         state.jumpToBacktrack(branchTest32(Zero, countRegister), this);
 768         sub32(Imm32(1), countRegister);
 769         sub32(Imm32(1), index);
 770
 771         failures.link(this);
 772
 773         storeToFrame(countRegister, term.frameLocation);
 774
 775         state.setBacktrackGenerated(backtrackBegin);
 776     }
 777
 778     void generateCharacterClassNonGreedy(TermGenerationState& state)
 779     {
 780         const RegisterID character = regT0;
 781         const RegisterID countRegister = regT1;
 782         PatternTerm& term = state.term();
 783
 784         move(Imm32(0), countRegister);
 785
 786         Jump firstTimeDoNothing = jump();
 787
 788         Label hardFail(this);
 789         sub32(countRegister, index);
 790         state.jumpToBacktrack(jump(), this);
 791
 792         Label backtrackBegin(this);
 793         loadFromFrame(term.frameLocation, countRegister);
 794
 795         atEndOfInput().linkTo(hardFail, this);
 796         branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
 797
 798         JumpList matchDest;
 799         readCharacter(state.inputOffset(), character);
 800         matchCharacterClass(character, matchDest, term.characterClass);
 801
 802         if (term.invertOrCapture)
 803             matchDest.linkTo(hardFail, this);
 804         else {
 805             jump(hardFail);
 806             matchDest.link(this);
 807         }
 808
 809         add32(Imm32(1), countRegister);
 810         add32(Imm32(1), index);
 811
 812         firstTimeDoNothing.link(this);
 813         storeToFrame(countRegister, term.frameLocation);
 814
 815         state.setBacktrackGenerated(backtrackBegin);
 816     }
 817
 818     void generateParenthesesDisjunction(PatternTerm& parenthesesTerm, TermGenerationState& state, unsigned alternativeFrameLocation)
 819     {
 820         ASSERT((parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern) || (parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion));
 821         ASSERT(parenthesesTerm.quantityCount == 1);
 822
 823         PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
 824         unsigned preCheckedCount = ((parenthesesTerm.quantityType == QuantifierFixedCount) && (parenthesesTerm.type != PatternTerm::TypeParentheticalAssertion)) ? disjunction->m_minimumSize : 0;
 825
 826         if (disjunction->m_alternatives.length() == 1) {
 827             state.resetAlternative();
 828             ASSERT(state.alternativeValid());
 829             PatternAlternative* alternative = state.alternative();
 830             optimizeAlternative(alternative);
 831
 832             int countToCheck = alternative->m_minimumSize - preCheckedCount;
 833             if (countToCheck) {
 834                 ASSERT((parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion) || (parenthesesTerm.quantityType != QuantifierFixedCount));
 835
 836                 // FIXME: This is quite horrible.  The call to 'plantJumpToBacktrackIfExists'
 837                 // will be forced to always trampoline into here, just to decrement the index.
 838                 // Ick.
 839                 Jump skip = jump();
 840
 841                 Label backtrackBegin(this);
 842                 sub32(Imm32(countToCheck), index);
 843                 state.addBacktrackJump(jump());
 844
 845                 skip.link(this);
 846
 847                 state.setBacktrackGenerated(backtrackBegin);
 848
 849                 state.jumpToBacktrack(jumpIfNoAvailableInput(countToCheck), this);
 850                 state.checkedTotal += countToCheck;
 851             }
 852
 853             for (state.resetTerm(); state.termValid(); state.nextTerm())
 854                 generateTerm(state);
 855
 856             state.checkedTotal -= countToCheck;
 857         } else {
 858             JumpList successes;
 859
 860             for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative()) {
 861
 862                 PatternAlternative* alternative = state.alternative();
 863                 optimizeAlternative(alternative);
 864
 865                 ASSERT(alternative->m_minimumSize >= preCheckedCount);
 866                 int countToCheck = alternative->m_minimumSize - preCheckedCount;
 867                 if (countToCheck) {
 868                     state.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
 869                     state.checkedTotal += countToCheck;
 870                 }
 871
 872                 for (state.resetTerm(); state.termValid(); state.nextTerm())
 873                     generateTerm(state);
 874
 875                 // Matched an alternative.
 876                 DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation);
 877                 successes.append(jump());
 878
 879                 // Alternative did not match.
 880                 Label backtrackLocation(this);
 881
 882                 // Can we backtrack the alternative? - if so, do so.  If not, just fall through to the next one.
 883                 state.plantJumpToBacktrackIfExists(this);
 884
 885                 state.linkAlternativeBacktracks(this);
 886
 887                 if (countToCheck) {
 888                     sub32(Imm32(countToCheck), index);
 889                     state.checkedTotal -= countToCheck;
 890                 }
 891
 892                 m_backtrackRecords.append(AlternativeBacktrackRecord(dataLabel, backtrackLocation));
 893             }
 894             // We fall through to here when the last alternative fails.
 895             // Add a backtrack out of here for the parenthese handling code to link up.
 896             state.addBacktrackJump(jump());
 897
 898             // Generate a trampoline for the parens code to backtrack to, to retry the
 899             // next alternative.
 900             state.setBacktrackGenerated(label());
 901             loadFromFrameAndJump(alternativeFrameLocation);
 902
 903             // FIXME: both of the above hooks are a little inefficient, in that you
 904             // may end up trampolining here, just to trampoline back out to the
 905             // parentheses code, or vice versa.  We can probably eliminate a jump
 906             // by restructuring, but coding this way for now for simplicity during
 907             // development.
 908
 909             successes.link(this);
 910         }
 911     }
 912
 913     void generateParenthesesSingle(TermGenerationState& state)
 914     {
 915         const RegisterID indexTemporary = regT0;
 916         PatternTerm& term = state.term();
 917         PatternDisjunction* disjunction = term.parentheses.disjunction;
 918         ASSERT(term.quantityCount == 1);
 919
 920         unsigned preCheckedCount = (term.quantityType == QuantifierFixedCount) ? disjunction->m_minimumSize : 0;
 921
 922         unsigned parenthesesFrameLocation = term.frameLocation;
 923         unsigned alternativeFrameLocation = parenthesesFrameLocation;
 924         if (term.quantityType != QuantifierFixedCount)
 925             alternativeFrameLocation += RegexStackSpaceForBackTrackInfoParenthesesOnce;
 926
 927         // optimized case - no capture & no quantifier can be handled in a light-weight manner.
 928         if (!term.invertOrCapture && (term.quantityType == QuantifierFixedCount)) {
 929             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
 930             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
 931             // this expects that any backtracks back out of the parentheses will be in the
 932             // parenthesesState's backTrackJumps vector, and that if they need backtracking
 933             // they will have set an entry point on the parenthesesState's backtrackLabel.
 934             state.propagateBacktrackingFrom(parenthesesState, this);
 935         } else {
 936             Jump nonGreedySkipParentheses;
 937             Label nonGreedyTryParentheses;
 938             if (term.quantityType == QuantifierGreedy)
 939                 storeToFrame(index, parenthesesFrameLocation);
 940             else if (term.quantityType == QuantifierNonGreedy) {
 941                 storeToFrame(Imm32(-1), parenthesesFrameLocation);
 942                 nonGreedySkipParentheses = jump();
 943                 nonGreedyTryParentheses = label();
 944                 storeToFrame(index, parenthesesFrameLocation);
 945             }
 946
 947             // store the match start index
 948             if (term.invertOrCapture) {
 949                 int inputOffset = state.inputOffset() - preCheckedCount;
 950                 if (inputOffset) {
 951                     move(index, indexTemporary);
 952                     add32(Imm32(inputOffset), indexTemporary);
 953                     store32(indexTemporary, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
 954                 } else
 955                     store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
 956             }
 957
 958             // generate the body of the parentheses
 959             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
 960             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
 961
 962             Jump success = (term.quantityType == QuantifierFixedCount) ?
 963                 jump() :
 964                 branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*))));
 965
 966             // A failure AFTER the parens jumps here
 967             Label backtrackFromAfterParens(this);
 968
 969             if (term.quantityType == QuantifierGreedy) {
 970                 // If this is -1 we have now tested with both with and without the parens.
 971                 loadFromFrame(parenthesesFrameLocation, indexTemporary);
 972                 state.jumpToBacktrack(branch32(Equal, indexTemporary, Imm32(-1)), this);
 973             } else if (term.quantityType == QuantifierNonGreedy) {
 974                 // If this is -1 we have now tested without the parens, now test with.
 975                 loadFromFrame(parenthesesFrameLocation, indexTemporary);
 976                 branch32(Equal, indexTemporary, Imm32(-1)).linkTo(nonGreedyTryParentheses, this);
 977             }
 978
 979             parenthesesState.plantJumpToBacktrackIfExists(this);
 980             // A failure WITHIN the parens jumps here
 981             parenthesesState.linkAlternativeBacktracks(this);
 982             if (term.invertOrCapture) {
 983                 store32(Imm32(-1), Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
 984 #if 0
 985                 store32(Imm32(-1), Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
 986 #endif
 987             }
 988
 989             if (term.quantityType == QuantifierGreedy)
 990                 storeToFrame(Imm32(-1), parenthesesFrameLocation);
 991             else
 992                 state.jumpToBacktrack(jump(), this);
 993
 994             state.setBacktrackGenerated(backtrackFromAfterParens);
 995             if (term.quantityType == QuantifierNonGreedy)
 996                 nonGreedySkipParentheses.link(this);
 997             success.link(this);
 998
 999             // store the match end index
1000             if (term.invertOrCapture) {
1001                 int inputOffset = state.inputOffset();
1002                 if (inputOffset) {
1003                     move(index, indexTemporary);
1004                     add32(Imm32(state.inputOffset()), indexTemporary);
1005                     store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
1006                 } else
1007                     store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
1008             }
1009         }
1010     }
1011
1012     void generateParenthesesGreedyNoBacktrack(TermGenerationState& state)
1013     {
1014         PatternTerm& parenthesesTerm = state.term();
1015         PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
1016         ASSERT(parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern);
1017         ASSERT(parenthesesTerm.quantityCount != 1); // Handled by generateParenthesesSingle.
1018
1019         TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1020
1021         Label matchAgain(this);
1022
1023         storeToFrame(index, parenthesesTerm.frameLocation); // Save the current index to check for zero len matches later.
1024
1025         for (parenthesesState.resetAlternative(); parenthesesState.alternativeValid(); parenthesesState.nextAlternative()) {
1026
1027             PatternAlternative* alternative = parenthesesState.alternative();
1028             optimizeAlternative(alternative);
1029
1030             int countToCheck = alternative->m_minimumSize;
1031             if (countToCheck) {
1032                 parenthesesState.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
1033                 parenthesesState.checkedTotal += countToCheck;
1034             }
1035
1036             for (parenthesesState.resetTerm(); parenthesesState.termValid(); parenthesesState.nextTerm())
1037                 generateTerm(parenthesesState);
1038
1039             // If we get here, we matched! If the index advanced then try to match more since limit isn't supported yet.
1040             branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesTerm.frameLocation * sizeof(void*))), matchAgain);
1041
1042             // If we get here we matched, but we matched "" - cannot accept this alternative as is, so either backtrack,
1043             // or fall through to try the next alternative if no backtrack is available.
1044             parenthesesState.plantJumpToBacktrackIfExists(this);
1045
1046             parenthesesState.linkAlternativeBacktracks(this);
1047             // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop.
1048
1049             if (countToCheck) {
1050                 sub32(Imm32(countToCheck), index);
1051                 parenthesesState.checkedTotal -= countToCheck;
1052             }
1053         }
1054
1055         // If the last alternative falls through to here, we have a failed match...
1056         // Which means that we match whatever we have matched up to this point (even if nothing).
1057     }
1058
1059     void generateParentheticalAssertion(TermGenerationState& state)
1060     {
1061         PatternTerm& term = state.term();
1062         PatternDisjunction* disjunction = term.parentheses.disjunction;
1063         ASSERT(term.quantityCount == 1);
1064         ASSERT(term.quantityType == QuantifierFixedCount);
1065
1066         unsigned parenthesesFrameLocation = term.frameLocation;
1067         unsigned alternativeFrameLocation = parenthesesFrameLocation + RegexStackSpaceForBackTrackInfoParentheticalAssertion;
1068
1069         int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;
1070
1071         if (term.invertOrCapture) {
1072             // Inverted case
1073             storeToFrame(index, parenthesesFrameLocation);
1074
1075             state.checkedTotal -= countCheckedAfterAssertion;
1076             if (countCheckedAfterAssertion)
1077                 sub32(Imm32(countCheckedAfterAssertion), index);
1078
1079             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1080             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1081             // Success! - which means - Fail!
1082             loadFromFrame(parenthesesFrameLocation, index);
1083             state.jumpToBacktrack(jump(), this);
1084
1085             // And fail means success.
1086             parenthesesState.linkAlternativeBacktracks(this);
1087             loadFromFrame(parenthesesFrameLocation, index);
1088
1089             state.checkedTotal += countCheckedAfterAssertion;
1090         } else {
1091             // Normal case
1092             storeToFrame(index, parenthesesFrameLocation);
1093
1094             state.checkedTotal -= countCheckedAfterAssertion;
1095             if (countCheckedAfterAssertion)
1096                 sub32(Imm32(countCheckedAfterAssertion), index);
1097
1098             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1099             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1100             // Success! - which means - Success!
1101             loadFromFrame(parenthesesFrameLocation, index);
1102             Jump success = jump();
1103
1104             parenthesesState.linkAlternativeBacktracks(this);
1105             loadFromFrame(parenthesesFrameLocation, index);
1106             state.jumpToBacktrack(jump(), this);
1107
1108             success.link(this);
1109
1110             state.checkedTotal += countCheckedAfterAssertion;
1111         }
1112     }
1113
1114     void generateTerm(TermGenerationState& state)
1115     {
1116         PatternTerm& term = state.term();
1117
1118         switch (term.type) {
1119         case PatternTerm::TypeAssertionBOL:
1120             generateAssertionBOL(state);
1121             break;
1122
1123         case PatternTerm::TypeAssertionEOL:
1124             generateAssertionEOL(state);
1125             break;
1126
1127         case PatternTerm::TypeAssertionWordBoundary:
1128             generateAssertionWordBoundary(state);
1129             break;
1130
1131         case PatternTerm::TypePatternCharacter:
1132             switch (term.quantityType) {
1133             case QuantifierFixedCount:
1134                 if (term.quantityCount == 1) {
1135                     if (state.isSinglePatternCharacterLookaheadTerm() && (state.lookaheadTerm().inputPosition == (term.inputPosition + 1))) {
1136                         generatePatternCharacterPair(state);
1137                         state.nextTerm();
1138                     } else
1139                         generatePatternCharacterSingle(state);
1140                 } else
1141                     generatePatternCharacterFixed(state);
1142                 break;
1143             case QuantifierGreedy:
1144                 generatePatternCharacterGreedy(state);
1145                 break;
1146             case QuantifierNonGreedy:
1147                 generatePatternCharacterNonGreedy(state);
1148                 break;
1149             }
1150             break;
1151
1152         case PatternTerm::TypeCharacterClass:
1153             switch (term.quantityType) {
1154             case QuantifierFixedCount:
1155                 if (term.quantityCount == 1)
1156                     generateCharacterClassSingle(state);
1157                 else
1158                     generateCharacterClassFixed(state);
1159                 break;
1160             case QuantifierGreedy:
1161                 generateCharacterClassGreedy(state);
1162                 break;
1163             case QuantifierNonGreedy:
1164                 generateCharacterClassNonGreedy(state);
1165                 break;
1166             }
1167             break;
1168
1169         case PatternTerm::TypeBackReference:
1170             m_shouldFallBack = true;
1171             break;
1172
1173         case PatternTerm::TypeForwardReference:
1174             break;
1175
1176         case PatternTerm::TypeParenthesesSubpattern:
1177             if (term.quantityCount == 1 && !term.parentheses.isCopy)
1178                 generateParenthesesSingle(state);
1179             else if (term.parentheses.isTerminal)
1180                 generateParenthesesGreedyNoBacktrack(state);
1181             else
1182                 m_shouldFallBack = true;
1183             break;
1184
1185         case PatternTerm::TypeParentheticalAssertion:
1186             generateParentheticalAssertion(state);
1187             break;
1188         }
1189     }
1190
1191     void generateDisjunction(PatternDisjunction* disjunction)
1192     {
1193         TermGenerationState state(disjunction, 0);
1194         state.resetAlternative();
1195
1196         // check availability for the next alternative
1197         int countCheckedForCurrentAlternative = 0;
1198         int countToCheckForFirstAlternative = 0;
1199         bool hasShorterAlternatives = false;
1200         bool setRepeatAlternativeLabels = false;
1201         JumpList notEnoughInputForPreviousAlternative;
1202         Label firstAlternative;
1203         Label firstAlternativeInputChecked;
1204
1205         // The label 'firstAlternative' is used to plant a check to see if there is
1206         // sufficient input available to run the first repeating alternative.
1207         // The label 'firstAlternativeInputChecked' will jump directly to matching
1208         // the first repeating alternative having skipped this check.
1209
1210         if (state.alternativeValid()) {
1211             PatternAlternative* alternative = state.alternative();
1212             if (!alternative->onceThrough()) {
1213                 firstAlternative = Label(this);
1214                 setRepeatAlternativeLabels = true;
1215             }
1216             countToCheckForFirstAlternative = alternative->m_minimumSize;
1217             state.checkedTotal += countToCheckForFirstAlternative;
1218             if (countToCheckForFirstAlternative)
1219                 notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
1220             countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
1221         }
1222
1223         if (setRepeatAlternativeLabels)
1224             firstAlternativeInputChecked = Label(this);
1225
1226         while (state.alternativeValid()) {
1227             PatternAlternative* alternative = state.alternative();
1228             optimizeAlternative(alternative);
1229
1230             // Track whether any alternatives are shorter than the first one.
1231             if (!alternative->onceThrough())
1232                 hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative);
1233
1234             for (state.resetTerm(); state.termValid(); state.nextTerm())
1235                 generateTerm(state);
1236
1237             // If we get here, the alternative matched.
1238             if (m_pattern.m_body->m_callFrameSize)
1239                 addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1240
1241             ASSERT(index != returnRegister);
1242             if (m_pattern.m_body->m_hasFixedSize) {
1243                 move(index, returnRegister);
1244                 if (alternative->m_minimumSize)
1245                     sub32(Imm32(alternative->m_minimumSize), returnRegister);
1246
1247                 store32(returnRegister, output);
1248             } else
1249                 load32(Address(output), returnRegister);
1250
1251             store32(index, Address(output, 4));
1252
1253             generateReturn();
1254
1255             state.nextAlternative();
1256
1257             // if there are any more alternatives, plant the check for input before looping.
1258             if (state.alternativeValid()) {
1259                 PatternAlternative* nextAlternative = state.alternative();
1260                 if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
1261                     // We have handled non-repeating alternatives, jump to next iteration
1262                     // and loop over repeating alternatives.
1263                     state.jumpToBacktrack(jump(), this);
1264
1265                     countToCheckForFirstAlternative = nextAlternative->m_minimumSize;
1266
1267                     // If we get here, there the last input checked failed.
1268                     notEnoughInputForPreviousAlternative.link(this);
1269
1270                     state.linkAlternativeBacktracks(this);
1271
1272                     // Back up to start the looping alternatives.
1273                     if (countCheckedForCurrentAlternative)
1274                         sub32(Imm32(countCheckedForCurrentAlternative), index);
1275
1276                     firstAlternative = Label(this);
1277
1278                     state.checkedTotal = countToCheckForFirstAlternative;
1279                     if (countToCheckForFirstAlternative)
1280                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
1281
1282                     countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
1283
1284                     firstAlternativeInputChecked = Label(this);
1285
1286                     setRepeatAlternativeLabels = true;
1287                 } else {
1288                     int countToCheckForNextAlternative = nextAlternative->m_minimumSize;
1289
1290                     if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one.
1291                         // If we get here, then the last input checked failed.
1292                         notEnoughInputForPreviousAlternative.link(this);
1293
1294                         // Check if sufficent input available to run the next alternative
1295                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
1296                         // We are now in the correct state to enter the next alternative; this add is only required
1297                         // to mirror and revert operation of the sub32, just below.
1298                         add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
1299
1300                         // If we get here, then the last input checked passed.
1301                         state.linkAlternativeBacktracks(this);
1302                         // No need to check if we can run the next alternative, since it is shorter -
1303                         // just update index.
1304                         sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
1305                     } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one.
1306                         // If we get here, then the last input checked failed.
1307                         // If there is insufficient input to run the current alternative, and the next alternative is longer,
1308                         // then there is definitely not enough input to run it - don't even check. Just adjust index, as if
1309                         // we had checked.
1310                         notEnoughInputForPreviousAlternative.link(this);
1311                         add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index);
1312                         notEnoughInputForPreviousAlternative.append(jump());
1313
1314                         // The next alternative is longer than the current one; check the difference.
1315                         state.linkAlternativeBacktracks(this);
1316                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
1317                     } else { // CASE 3: Both alternatives are the same length.
1318                         ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative);
1319
1320                         // If the next alterative is the same length as this one, then no need to check the input -
1321                         // if there was sufficent input to run the current alternative then there is sufficient
1322                         // input to run the next one; if not, there isn't.
1323                         state.linkAlternativeBacktracks(this);
1324                     }
1325                     state.checkedTotal -= countCheckedForCurrentAlternative;
1326                     countCheckedForCurrentAlternative = countToCheckForNextAlternative;
1327                     state.checkedTotal += countCheckedForCurrentAlternative;
1328                 }
1329             }
1330         }
1331
1332         // If we get here, all Alternatives failed...
1333
1334         state.checkedTotal -= countCheckedForCurrentAlternative;
1335
1336         if (!setRepeatAlternativeLabels) {
1337             // If there are no alternatives that need repeating (all are marked 'onceThrough') then just link
1338             // the match failures to this point, and fall through to the return below.
1339             state.linkAlternativeBacktracks(this);
1340             notEnoughInputForPreviousAlternative.link(this);
1341         } else {
1342             // How much more input need there be to be able to retry from the first alternative?
1343             // examples:
1344             //   /yarr_jit/ or /wrec|pcre/
1345             //     In these examples we need check for one more input before looping.
1346             //   /yarr_jit|pcre/
1347             //     In this case we need check for 5 more input to loop (+4 to allow for the first alterative
1348             //     being four longer than the last alternative checked, and another +1 to effectively move
1349             //     the start position along by one).
1350             //   /yarr|rules/ or /wrec|notsomuch/
1351             //     In these examples, provided that there was sufficient input to have just been matching for
1352             //     the second alternative we can loop without checking for available input (since the second
1353             //     alternative is longer than the first).  In the latter example we need to decrement index
1354             //     (by 4) so the start position is only progressed by 1 from the last iteration.
1355             int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1;
1356
1357             // First, deal with the cases where there was sufficient input to try the last alternative.
1358             if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below.
1359                 state.linkAlternativeBacktracks(this);
1360             else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop!
1361                 state.linkAlternativeBacktracksTo(firstAlternativeInputChecked, this);
1362             else { // no need to check the input, but we do have some bookkeeping to do first.
1363                 state.linkAlternativeBacktracks(this);
1364
1365                 // Where necessary update our preserved start position.
1366                 if (!m_pattern.m_body->m_hasFixedSize) {
1367                     move(index, regT0);
1368                     sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
1369                     store32(regT0, Address(output));
1370                 }
1371
1372                 // Update index if necessary, and loop (without checking).
1373                 if (incrementForNextIter)
1374                     add32(Imm32(incrementForNextIter), index);
1375                 jump().linkTo(firstAlternativeInputChecked, this);
1376             }
1377
1378             notEnoughInputForPreviousAlternative.link(this);
1379             // Update our idea of the start position, if we're tracking this.
1380             if (!m_pattern.m_body->m_hasFixedSize) {
1381                 if (countCheckedForCurrentAlternative - 1) {
1382                     move(index, regT0);
1383                     sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
1384                     store32(regT0, Address(output));
1385                 } else
1386                     store32(index, Address(output));
1387             }
1388
1389             // Check if there is sufficent input to run the first alternative again.
1390             jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this);
1391             // No - insufficent input to run the first alteranative, are there any other alternatives we
1392             // might need to check?  If so, the last check will have left the index incremented by
1393             // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative
1394             // LESS input is available, to have the effect of just progressing the start position by 1
1395             // from the last iteration.  If this check passes we can just jump up to the check associated
1396             // with the first alternative in the loop.  This is a bit sad, since we'll end up trying the
1397             // first alternative again, and this check will fail (otherwise the check planted just above
1398             // here would have passed).  This is a bit sad, however it saves trying to do something more
1399             // complex here in compilation, and in the common case we should end up coallescing the checks.
1400             //
1401             // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least
1402             // of the minimum-alternative-lengths.  E.g. if I have two alternatives of length 200 and 150,
1403             // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there
1404             // is sufficient input to run either alternative (constantly failing).  If there had been only
1405             // one alternative, or if the shorter alternative had come first, we would have terminated
1406             // immediately. :-/
1407             if (hasShorterAlternatives)
1408                 jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this);
1409             // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true,
1410             // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ...
1411             // but since we're about to return a failure this doesn't really matter!)
1412         }
1413
1414         if (m_pattern.m_body->m_callFrameSize)
1415             addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1416
1417         move(Imm32(-1), returnRegister);
1418
1419         generateReturn();
1420     }
1421
1422     void generateEnter()
1423     {
1424 #if WTF_CPU_X86_64
1425         push(X86Registers::ebp);
1426         move(stackPointerRegister, X86Registers::ebp);
1427         push(X86Registers::ebx);
1428 #elif WTF_CPU_X86
1429         push(X86Registers::ebp);
1430         move(stackPointerRegister, X86Registers::ebp);
1431         // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
1432         push(X86Registers::ebx);
1433         push(X86Registers::edi);
1434         push(X86Registers::esi);
1435         // load output into edi (2 = saved ebp + return address).
1436     #if WTF_COMPILER_MSVC || WTF_COMPILER_SUNPRO
1437         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
1438         loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
1439         loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
1440         loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
1441     #else
1442         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
1443     #endif
1444 #elif WTF_CPU_ARM
1445         push(ARMRegisters::r4);
1446         push(ARMRegisters::r5);
1447         push(ARMRegisters::r6);
1448 #if WTF_CPU_ARM_TRADITIONAL
1449         push(ARMRegisters::r8); // scratch register
1450 #endif
1451         move(ARMRegisters::r3, output);
1452 #elif WTF_CPU_MIPS
1453         // Do nothing.
1454 #endif
1455     }
1456
1457     void generateReturn()
1458     {
1459 #if WTF_CPU_X86_64
1460         pop(X86Registers::ebx);
1461         pop(X86Registers::ebp);
1462 #elif WTF_CPU_X86
1463         pop(X86Registers::esi);
1464         pop(X86Registers::edi);
1465         pop(X86Registers::ebx);
1466         pop(X86Registers::ebp);
1467 #elif WTF_CPU_ARM
1468 #if WTF_CPU_ARM_TRADITIONAL
1469         pop(ARMRegisters::r8); // scratch register
1470 #endif
1471         pop(ARMRegisters::r6);
1472         pop(ARMRegisters::r5);
1473         pop(ARMRegisters::r4);
1474 #elif WTF_CPU_MIPS
1475         // Do nothing
1476 #endif
1477         ret();
1478     }
1479
1480 public:
1481     RegexGenerator(RegexPattern& pattern)
1482         : m_pattern(pattern)
1483         , m_shouldFallBack(false)
1484     {
1485     }
1486
1487     void generate()
1488     {
1489         generateEnter();
1490
1491         if (!m_pattern.m_body->m_hasFixedSize)
1492             store32(index, Address(output));
1493
1494         if (m_pattern.m_body->m_callFrameSize)
1495             subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1496
1497         generateDisjunction(m_pattern.m_body);
1498     }
1499
1500     void compile(ExecutableAllocator& allocator, RegexCodeBlock& jitObject)
1501     {
1502         generate();
1503
1504         if (oom()) {
1505             m_shouldFallBack = true;
1506             return;
1507         }
1508
1509         ExecutablePool *executablePool = allocator.poolForSize(size());
1510         if (!executablePool) {
1511             m_shouldFallBack = true;
1512             return;
1513         }
1514
1515         LinkBuffer patchBuffer(this, executablePool);
1516
1517         for (unsigned i = 0; i < m_backtrackRecords.length(); ++i)
1518             patchBuffer.patch(m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_backtrackRecords[i].backtrackLocation));
1519
1520         jitObject.set(patchBuffer.finalizeCode());
1521     }
1522
1523     bool shouldFallBack()
1524     {
1525         return m_shouldFallBack;
1526     }
1527
1528 private:
1529     RegexPattern& m_pattern;
1530     bool m_shouldFallBack;
1531     js::Vector<AlternativeBacktrackRecord, 0, js::SystemAllocPolicy> m_backtrackRecords;
1532 };
1533
1534 void jitCompileRegex(ExecutableAllocator& allocator, RegexCodeBlock& jitObject, const UString&patternString, unsigned& numSubpatterns, int &error, bool &fellBack, bool ignoreCase, bool multiline
1535 #ifdef ANDROID
1536                      , bool forceFallback
1537 #endif
1538 )
1539 {
1540 #ifdef ANDROID
1541     if (!forceFallback) {
1542 #endif
1543     fellBack = false;
1544     RegexPattern pattern(ignoreCase, multiline);
1545     if ((error = compileRegex(patternString, pattern)))
1546         return;
1547     numSubpatterns = pattern.m_numSubpatterns;
1548
1549     if (!pattern.m_containsBackreferences) {
1550         RegexGenerator generator(pattern);
1551         generator.compile(allocator, jitObject);
1552         if (!generator.shouldFallBack())
1553             return;
1554     }
1555 #ifdef ANDROID
1556     } // forceFallback
1557 #endif
1558
1559     fellBack = true;
1560     JSRegExpIgnoreCaseOption ignoreCaseOption = ignoreCase ? JSRegExpIgnoreCase : JSRegExpDoNotIgnoreCase;
1561     JSRegExpMultilineOption multilineOption = multiline ? JSRegExpMultiline : JSRegExpSingleLine;
1562     jitObject.setFallback(jsRegExpCompile(reinterpret_cast<const UChar*>(const_cast<UString &>(patternString).chars()), patternString.length(), ignoreCaseOption, multilineOption, &numSubpatterns, &error));
1563 }
1564
1565 }}
1566
1567 #endif