2011-03-27 Oliver Hunt <oliver@apple.com>
[WebKit-https.git] / Source / JavaScriptCore / yarr / YarrJIT.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 "YarrJIT.h"
28
29 #include "ASCIICType.h"
30 #include "LinkBuffer.h"
31 #include "Yarr.h"
32
33 #if ENABLE(YARR_JIT)
34
35 using namespace WTF;
36
37 namespace JSC { namespace Yarr {
38
39 class YarrGenerator : private MacroAssembler {
40     friend void jitCompile(JSGlobalData*, YarrCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);
41
42 #if CPU(ARM)
43     static const RegisterID input = ARMRegisters::r0;
44     static const RegisterID index = ARMRegisters::r1;
45     static const RegisterID length = ARMRegisters::r2;
46     static const RegisterID output = ARMRegisters::r4;
47
48     static const RegisterID regT0 = ARMRegisters::r5;
49     static const RegisterID regT1 = ARMRegisters::r6;
50
51     static const RegisterID returnRegister = ARMRegisters::r0;
52 #elif CPU(MIPS)
53     static const RegisterID input = MIPSRegisters::a0;
54     static const RegisterID index = MIPSRegisters::a1;
55     static const RegisterID length = MIPSRegisters::a2;
56     static const RegisterID output = MIPSRegisters::a3;
57
58     static const RegisterID regT0 = MIPSRegisters::t4;
59     static const RegisterID regT1 = MIPSRegisters::t5;
60
61     static const RegisterID returnRegister = MIPSRegisters::v0;
62 #elif CPU(X86)
63     static const RegisterID input = X86Registers::eax;
64     static const RegisterID index = X86Registers::edx;
65     static const RegisterID length = X86Registers::ecx;
66     static const RegisterID output = X86Registers::edi;
67
68     static const RegisterID regT0 = X86Registers::ebx;
69     static const RegisterID regT1 = X86Registers::esi;
70
71     static const RegisterID returnRegister = X86Registers::eax;
72 #elif CPU(X86_64)
73     static const RegisterID input = X86Registers::edi;
74     static const RegisterID index = X86Registers::esi;
75     static const RegisterID length = X86Registers::edx;
76     static const RegisterID output = X86Registers::ecx;
77
78     static const RegisterID regT0 = X86Registers::eax;
79     static const RegisterID regT1 = X86Registers::ebx;
80
81     static const RegisterID returnRegister = X86Registers::eax;
82 #endif
83
84     void optimizeAlternative(PatternAlternative* alternative)
85     {
86         if (!alternative->m_terms.size())
87             return;
88
89         for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {
90             PatternTerm& term = alternative->m_terms[i];
91             PatternTerm& nextTerm = alternative->m_terms[i + 1];
92
93             if ((term.type == PatternTerm::TypeCharacterClass)
94                 && (term.quantityType == QuantifierFixedCount)
95                 && (nextTerm.type == PatternTerm::TypePatternCharacter)
96                 && (nextTerm.quantityType == QuantifierFixedCount)) {
97                 PatternTerm termCopy = term;
98                 alternative->m_terms[i] = nextTerm;
99                 alternative->m_terms[i + 1] = termCopy;
100             }
101         }
102     }
103
104     void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
105     {
106         do {
107             // pick which range we're going to generate
108             int which = count >> 1;
109             char lo = ranges[which].begin;
110             char hi = ranges[which].end;
111
112             // check if there are any ranges or matches below lo.  If not, just jl to failure -
113             // if there is anything else to check, check that first, if it falls through jmp to failure.
114             if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
115                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
116
117                 // generate code for all ranges before this one
118                 if (which)
119                     matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
120
121                 while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
122                     matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
123                     ++*matchIndex;
124                 }
125                 failures.append(jump());
126
127                 loOrAbove.link(this);
128             } else if (which) {
129                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
130
131                 matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
132                 failures.append(jump());
133
134                 loOrAbove.link(this);
135             } else
136                 failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));
137
138             while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
139                 ++*matchIndex;
140
141             matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
142             // fall through to here, the value is above hi.
143
144             // shuffle along & loop around if there are any more matches to handle.
145             unsigned next = which + 1;
146             ranges += next;
147             count -= next;
148         } while (count);
149     }
150
151     void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
152     {
153         if (charClass->m_table) {
154             ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table));
155             matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry));
156             return;
157         }
158         Jump unicodeFail;
159         if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
160             Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f));
161
162             if (charClass->m_matchesUnicode.size()) {
163                 for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {
164                     UChar ch = charClass->m_matchesUnicode[i];
165                     matchDest.append(branch32(Equal, character, Imm32(ch)));
166                 }
167             }
168
169             if (charClass->m_rangesUnicode.size()) {
170                 for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {
171                     UChar lo = charClass->m_rangesUnicode[i].begin;
172                     UChar hi = charClass->m_rangesUnicode[i].end;
173
174                     Jump below = branch32(LessThan, character, Imm32(lo));
175                     matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
176                     below.link(this);
177                 }
178             }
179
180             unicodeFail = jump();
181             isAscii.link(this);
182         }
183
184         if (charClass->m_ranges.size()) {
185             unsigned matchIndex = 0;
186             JumpList failures;
187             matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
188             while (matchIndex < charClass->m_matches.size())
189                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
190
191             failures.link(this);
192         } else if (charClass->m_matches.size()) {
193             // optimization: gather 'a','A' etc back together, can mask & test once.
194             Vector<char> matchesAZaz;
195
196             for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {
197                 char ch = charClass->m_matches[i];
198                 if (m_pattern.m_ignoreCase) {
199                     if (isASCIILower(ch)) {
200                         matchesAZaz.append(ch);
201                         continue;
202                     }
203                     if (isASCIIUpper(ch))
204                         continue;
205                 }
206                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
207             }
208
209             if (unsigned countAZaz = matchesAZaz.size()) {
210                 or32(TrustedImm32(32), character);
211                 for (unsigned i = 0; i < countAZaz; ++i)
212                     matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));
213             }
214         }
215
216         if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())
217             unicodeFail.link(this);
218     }
219
220     // Jumps if input not available; will have (incorrectly) incremented already!
221     Jump jumpIfNoAvailableInput(unsigned countToCheck)
222     {
223         add32(Imm32(countToCheck), index);
224         return branch32(Above, index, length);
225     }
226
227     Jump jumpIfAvailableInput(unsigned countToCheck)
228     {
229         add32(Imm32(countToCheck), index);
230         return branch32(BelowOrEqual, index, length);
231     }
232
233     Jump checkInput()
234     {
235         return branch32(BelowOrEqual, index, length);
236     }
237
238     Jump atEndOfInput()
239     {
240         return branch32(Equal, index, length);
241     }
242
243     Jump notAtEndOfInput()
244     {
245         return branch32(NotEqual, index, length);
246     }
247
248     Jump jumpIfCharEquals(UChar ch, int inputPosition)
249     {
250         return branch16(Equal, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
251     }
252
253     Jump jumpIfCharNotEquals(UChar ch, int inputPosition)
254     {
255         return branch16(NotEqual, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
256     }
257
258     void readCharacter(int inputPosition, RegisterID reg)
259     {
260         load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
261     }
262
263     void storeToFrame(RegisterID reg, unsigned frameLocation)
264     {
265         poke(reg, frameLocation);
266     }
267
268     void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
269     {
270         poke(imm, frameLocation);
271     }
272
273     DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
274     {
275         return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
276     }
277
278     void loadFromFrame(unsigned frameLocation, RegisterID reg)
279     {
280         peek(reg, frameLocation);
281     }
282
283     void loadFromFrameAndJump(unsigned frameLocation)
284     {
285         jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
286     }
287
288     struct IndirectJumpEntry {
289         IndirectJumpEntry(int32_t stackOffset)
290             : m_stackOffset(stackOffset)
291         {
292         }
293
294         IndirectJumpEntry(int32_t stackOffset, Jump jump)
295             : m_stackOffset(stackOffset)
296         {
297             addJump(jump);
298         }
299
300         IndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
301         : m_stackOffset(stackOffset)
302         {
303             addDataLabel(dataLabel);
304         }
305
306         void addJump(Jump jump)
307         {
308             m_relJumps.append(jump);
309         }
310         
311         void addDataLabel(DataLabelPtr dataLabel)
312         {
313             m_dataLabelPtrVector.append(dataLabel);
314         }
315
316         int32_t m_stackOffset;
317         JumpList m_relJumps;
318         Vector<DataLabelPtr, 16> m_dataLabelPtrVector;
319     };
320
321     struct AlternativeBacktrackRecord {
322         DataLabelPtr dataLabel;
323         Label backtrackLocation;
324
325         AlternativeBacktrackRecord(DataLabelPtr dataLabel, Label backtrackLocation)
326             : dataLabel(dataLabel)
327             , backtrackLocation(backtrackLocation)
328         {
329         }
330     };
331
332     struct ParenthesesTail;
333     struct TermGenerationState;
334
335     struct GenerationState {
336         typedef HashMap<int, IndirectJumpEntry*, WTF::IntHash<uint32_t>, UnsignedWithZeroKeyHashTraits<uint32_t> > IndirectJumpHashMap;
337
338         GenerationState()
339             : m_parenNestingLevel(0)
340         {
341         }
342
343         void addIndirectJumpEntry(int32_t stackOffset, Jump jump)
344         {
345             IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset);
346
347             ASSERT(stackOffset >= 0);
348
349             uint32_t offset = static_cast<uint32_t>(stackOffset);
350
351             if (result == m_indirectJumpMap.end())
352                 m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, jump));
353             else
354                 result->second->addJump(jump);
355         }
356
357         void addIndirectJumpEntry(int32_t stackOffset, JumpList jumps)
358         {
359             JumpList::JumpVector jumpVector = jumps.jumps();
360             size_t size = jumpVector.size();
361             for (size_t i = 0; i < size; ++i)
362                 addIndirectJumpEntry(stackOffset, jumpVector[i]);
363
364             jumps.empty();
365         }
366
367         void addIndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
368         {
369             IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset);
370
371             ASSERT(stackOffset >= 0);
372
373             uint32_t offset = static_cast<uint32_t>(stackOffset);
374
375             if (result == m_indirectJumpMap.end())
376                 m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, dataLabel));
377             else
378                 result->second->addDataLabel(dataLabel);
379         }
380
381         void emitIndirectJumpTable(MacroAssembler* masm)
382         {
383             for (IndirectJumpHashMap::iterator iter = m_indirectJumpMap.begin(); iter != m_indirectJumpMap.end(); ++iter) {
384                 IndirectJumpEntry* indJumpEntry = iter->second;
385                 size_t size = indJumpEntry->m_dataLabelPtrVector.size();
386                 if (size) {
387                     // Link any associated DataLabelPtr's with indirect jump via label
388                     Label hereLabel = masm->label();
389                     for (size_t i = 0; i < size; ++i)
390                         m_backtrackRecords.append(AlternativeBacktrackRecord(indJumpEntry->m_dataLabelPtrVector[i], hereLabel));
391                 }
392                 indJumpEntry->m_relJumps.link(masm);
393                 masm->jump(Address(stackPointerRegister, indJumpEntry->m_stackOffset));
394                 delete indJumpEntry;
395             }
396         }
397
398         void incrementParenNestingLevel()
399         {
400             ++m_parenNestingLevel;
401         }
402
403         void decrementParenNestingLevel()
404         {
405             --m_parenNestingLevel;
406         }
407
408         ParenthesesTail* addParenthesesTail(PatternTerm& term, JumpList* jumpListToPriorParen)
409         {
410             ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, jumpListToPriorParen);
411             m_parenTails.append(parenthesesTail);
412             m_parenTailsForIteration.append(parenthesesTail);
413
414             return parenthesesTail;
415         }
416
417         void emitParenthesesTail(YarrGenerator* generator)
418         {
419             unsigned vectorSize = m_parenTails.size();
420             bool priorBacktrackFallThrough = false;
421
422             // Emit in reverse order so parentTail N can fall through to N-1
423             for (unsigned index = vectorSize; index > 0; --index) {
424                 JumpList jumpsToNext;
425                 priorBacktrackFallThrough = m_parenTails[index-1].get()->generateCode(generator, jumpsToNext, priorBacktrackFallThrough, index > 1);
426                 if (index > 1)
427                     jumpsToNext.linkTo(generator->label(), generator);
428                 else
429                     addJumpsToNextInteration(jumpsToNext);
430             }
431             m_parenTails.clear();
432         }
433
434         void addJumpToNextInteration(Jump jump)
435         {
436             m_jumpsToNextInteration.append(jump);
437         }
438
439         void addJumpsToNextInteration(JumpList jumps)
440         {
441             m_jumpsToNextInteration.append(jumps);
442         }
443
444         void addDataLabelToNextIteration(DataLabelPtr dataLabel)
445         {
446             m_dataPtrsToNextIteration.append(dataLabel);
447         }
448
449         void linkToNextIteration(Label label)
450         {
451             m_nextIteration = label;
452
453             for (unsigned i = 0; i < m_dataPtrsToNextIteration.size(); ++i)
454                 m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataPtrsToNextIteration[i], m_nextIteration));
455
456             m_dataPtrsToNextIteration.clear();
457
458             for (unsigned i = 0; i < m_parenTailsForIteration.size(); ++i)
459                 m_parenTailsForIteration[i]->setNextIteration(m_nextIteration);
460
461             m_parenTailsForIteration.clear();
462         }
463
464         void linkToNextIteration(YarrGenerator* generator)
465         {
466             m_jumpsToNextInteration.linkTo(m_nextIteration, generator);
467         }
468
469         int m_parenNestingLevel;
470         Vector<AlternativeBacktrackRecord> m_backtrackRecords;
471         IndirectJumpHashMap m_indirectJumpMap;
472         Label m_nextIteration;
473         Vector<OwnPtr<ParenthesesTail> > m_parenTails;
474         JumpList m_jumpsToNextInteration;
475         Vector<DataLabelPtr> m_dataPtrsToNextIteration;
476         Vector<ParenthesesTail*> m_parenTailsForIteration;
477     };
478
479     struct BacktrackDestination {
480         typedef enum {
481             NoBacktrack,
482             BacktrackLabel,
483             BacktrackStackOffset,
484             BacktrackJumpList,
485             BacktrackLinked
486         } BacktrackType;
487
488         BacktrackDestination()
489             : m_backtrackType(NoBacktrack)
490             , m_backtrackToLabel(0)
491             , m_subDataLabelPtr(0)
492             , m_nextBacktrack(0)
493             , m_backtrackSourceLabel(0)
494             , m_backtrackSourceJumps(0)
495         {
496         }
497
498         BacktrackDestination(int32_t stackOffset)
499             : m_backtrackType(BacktrackStackOffset)
500             , m_backtrackStackOffset(stackOffset)
501             , m_backtrackToLabel(0)
502             , m_subDataLabelPtr(0)
503             , m_nextBacktrack(0)
504             , m_backtrackSourceLabel(0)
505             , m_backtrackSourceJumps(0)
506         {
507         }
508
509         BacktrackDestination(Label label)
510             : m_backtrackType(BacktrackLabel)
511             , m_backtrackLabel(label)
512             , m_backtrackToLabel(0)
513             , m_subDataLabelPtr(0)
514             , m_nextBacktrack(0)
515             , m_backtrackSourceLabel(0)
516             , m_backtrackSourceJumps(0)
517         {
518         }
519
520         void clear(bool doDataLabelClear = true)
521         {
522             m_backtrackType = NoBacktrack;
523             if (doDataLabelClear)
524                 clearDataLabel();
525             m_nextBacktrack = 0;
526         }
527
528         void clearDataLabel()
529         {
530             m_dataLabelPtr = DataLabelPtr();
531         }
532
533         bool hasDestination()
534         {
535             return (m_backtrackType != NoBacktrack);
536         }
537
538         bool isStackOffset()
539         {
540             return (m_backtrackType == BacktrackStackOffset);
541         }
542
543         bool isLabel()
544         {
545             return (m_backtrackType == BacktrackLabel);
546         }
547
548         bool isJumpList()
549         {
550             return (m_backtrackType == BacktrackJumpList);
551         }
552
553         bool hasDataLabel()
554         {
555             return m_dataLabelPtr.isSet();
556         }
557
558         void copyTarget(BacktrackDestination& rhs, bool copyDataLabel = true)
559         {
560             m_backtrackType = rhs.m_backtrackType;
561             if (m_backtrackType == BacktrackStackOffset)
562                 m_backtrackStackOffset = rhs.m_backtrackStackOffset;
563             else if (m_backtrackType == BacktrackLabel)
564                 m_backtrackLabel = rhs.m_backtrackLabel;
565             if (copyDataLabel)
566                 m_dataLabelPtr = rhs.m_dataLabelPtr;
567             m_backtrackSourceJumps = rhs.m_backtrackSourceJumps;
568             m_backtrackSourceLabel = rhs.m_backtrackSourceLabel;
569         }
570
571         void copyTo(BacktrackDestination& lhs)
572         {
573             lhs.m_backtrackType = m_backtrackType;
574             if (m_backtrackType == BacktrackStackOffset)
575                 lhs.m_backtrackStackOffset = m_backtrackStackOffset;
576             else if (m_backtrackType == BacktrackLabel)
577                 lhs.m_backtrackLabel = m_backtrackLabel;
578             lhs.m_backtrackSourceJumps = m_backtrackSourceJumps;
579             lhs.m_backtrackSourceLabel = m_backtrackSourceLabel;
580             lhs.m_dataLabelPtr = m_dataLabelPtr;
581             lhs.m_backTrackJumps = m_backTrackJumps;
582         }
583
584         void addBacktrackJump(Jump jump)
585         {
586             m_backTrackJumps.append(jump);
587         }
588
589         void setStackOffset(int32_t stackOffset)
590         {
591             m_backtrackType = BacktrackStackOffset;
592             m_backtrackStackOffset = stackOffset;
593         }
594
595         void setLabel(Label label)
596         {
597             m_backtrackType = BacktrackLabel;
598             m_backtrackLabel = label;
599         }
600
601         void setNextBacktrackLabel(Label label)
602         {
603             if (m_nextBacktrack)
604                 m_nextBacktrack->setLabel(label);
605         }
606
607         void propagateBacktrackToLabel(const BacktrackDestination& rhs)
608         {
609             if (!m_backtrackToLabel && rhs.m_backtrackToLabel)
610                 m_backtrackToLabel = rhs.m_backtrackToLabel;
611         }
612
613         void setBacktrackToLabel(Label* backtrackToLabel)
614         {
615             if (!m_backtrackToLabel)
616                 m_backtrackToLabel = backtrackToLabel;
617         }
618
619         bool hasBacktrackToLabel()
620         {
621             return m_backtrackToLabel;
622         }
623
624         void setBacktrackJumpList(JumpList* jumpList)
625         {
626             m_backtrackType = BacktrackJumpList;
627             m_backtrackSourceJumps = jumpList;
628         }
629
630         void setBacktrackSourceLabel(Label* backtrackSourceLabel)
631         {
632             m_backtrackSourceLabel = backtrackSourceLabel;
633         }
634
635         void setDataLabel(DataLabelPtr dp)
636         {
637             if (m_subDataLabelPtr) {
638                 *m_subDataLabelPtr = dp;
639                 m_subDataLabelPtr = 0;
640             } else {
641                 ASSERT(!hasDataLabel());
642                 m_dataLabelPtr = dp;
643             }
644         }
645
646         void clearSubDataLabelPtr()
647         {
648             m_subDataLabelPtr = 0;
649         }
650
651         void setSubDataLabelPtr(DataLabelPtr* subDataLabelPtr)
652         {
653             m_subDataLabelPtr = subDataLabelPtr;
654         }
655
656         void linkToNextBacktrack(BacktrackDestination* nextBacktrack)
657         {
658             m_nextBacktrack = nextBacktrack;
659         }
660
661         int32_t getStackOffset()
662         {
663             ASSERT(m_backtrackType == BacktrackStackOffset);
664             return m_backtrackStackOffset;
665         }
666
667         Label getLabel()
668         {
669             ASSERT(m_backtrackType == BacktrackLabel);
670             return m_backtrackLabel;
671         }
672
673         JumpList& getBacktrackJumps()
674         {
675             return m_backTrackJumps;
676         }
677
678         DataLabelPtr& getDataLabel()
679         {
680             return m_dataLabelPtr;
681         }
682
683         void jumpToBacktrack(MacroAssembler* masm)
684         {
685             if (isJumpList()) {
686                 if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
687                     masm->jump().linkTo(*m_backtrackSourceLabel, masm);
688                 else
689                     m_backtrackSourceJumps->append(masm->jump());
690             } else if (isStackOffset())
691                 masm->jump(Address(stackPointerRegister, m_backtrackStackOffset));
692             else if (isLabel())
693                 masm->jump().linkTo(m_backtrackLabel, masm);
694             else
695                 m_backTrackJumps.append(masm->jump());
696         }
697
698         void jumpToBacktrack(YarrGenerator* generator, Jump jump)
699         {
700             if (isJumpList()) {
701                 if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
702                     jump.linkTo(*m_backtrackSourceLabel, generator);
703                 else
704                     m_backtrackSourceJumps->append(jump);
705             } else if (isStackOffset())
706                 generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jump);
707             else if (isLabel())
708                 jump.linkTo(getLabel(), generator);
709             else
710                 m_backTrackJumps.append(jump);
711         }
712
713         void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps)
714         {
715             if (isJumpList()) {
716                 if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
717                     jumps.linkTo(*m_backtrackSourceLabel, generator);
718                 else
719                     m_backtrackSourceJumps->append(jumps);
720             } else if (isStackOffset())
721                 generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jumps);
722             else if (isLabel())
723                 jumps.linkTo(getLabel(), generator);
724             else
725                 m_backTrackJumps.append(jumps);
726         }
727
728         bool plantJumpToBacktrackIfExists(YarrGenerator* generator)
729         {
730             if (isJumpList()) {
731                 if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
732                     generator->jump(*m_backtrackSourceLabel);
733                 else
734                     m_backtrackSourceJumps->append(generator->jump());
735
736                 return true;
737             }
738
739             if (isStackOffset()) {
740                 generator->jump(Address(stackPointerRegister, getStackOffset()));
741                 return true;
742             }
743
744             if (isLabel()) {
745                 generator->jump(getLabel());
746                 if (hasDataLabel()) {
747                     generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), getLabel()));
748                     clearDataLabel();
749                 }
750                 return true;
751             }
752
753             return false;
754         }
755
756         void linkBacktrackToLabel(Label backtrackLabel)
757         {
758             if (m_backtrackToLabel)
759                 *m_backtrackToLabel = backtrackLabel;
760         }
761
762         void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false)
763         {
764             Label hereLabel = generator->label();
765
766             if (m_backtrackToLabel) {
767                 *m_backtrackToLabel = hereLabel;
768                 m_backtrackToLabel = 0;
769             }
770
771             m_backTrackJumps.link(generator);
772
773             if (nextIteration)
774                 generator->m_expressionState.linkToNextIteration(hereLabel);
775
776             if (hasDataLabel()) {
777                 generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), hereLabel));
778                 // data label cleared as a result of the clear() below
779             }
780
781             clear();
782         }
783
784         void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false)
785         {
786             m_backTrackJumps.linkTo(label, generator);
787
788             if (nextIteration)
789                 generator->m_expressionState.linkToNextIteration(label);
790
791             if (hasDataLabel()) {
792                 generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), label));
793                 clearDataLabel();
794             }
795         }
796
797     private:
798         BacktrackType m_backtrackType;
799         int32_t m_backtrackStackOffset;
800         Label m_backtrackLabel;
801         DataLabelPtr m_dataLabelPtr;
802         Label* m_backtrackToLabel;
803         DataLabelPtr* m_subDataLabelPtr;
804         BacktrackDestination* m_nextBacktrack;
805         Label* m_backtrackSourceLabel;
806         JumpList* m_backtrackSourceJumps;
807         JumpList m_backTrackJumps;
808     };
809
810     struct TermGenerationState {
811         TermGenerationState(PatternDisjunction* disjunction, unsigned checkedTotal)
812             : disjunction(disjunction)
813             , checkedTotal(checkedTotal)
814             , m_subParenNum(0)
815             , m_linkedBacktrack(0)
816             , m_jumpList(0)
817         {
818         }
819
820         void resetAlternative()
821         {
822             m_backtrack.clear();
823             alt = 0;
824         }
825         bool alternativeValid()
826         {
827             return alt < disjunction->m_alternatives.size();
828         }
829         void nextAlternative()
830         {
831             ++alt;
832         }
833         PatternAlternative* alternative()
834         {
835             return disjunction->m_alternatives[alt];
836         }
837         bool isLastAlternative()
838         {
839             return (alt + 1) == disjunction->m_alternatives.size();
840         }
841
842         void resetTerm()
843         {
844             ASSERT(alternativeValid());
845             t = 0;
846             m_subParenNum = 0;
847         }
848         bool termValid()
849         {
850             ASSERT(alternativeValid());
851             return t < alternative()->m_terms.size();
852         }
853         void nextTerm()
854         {
855             ASSERT(alternativeValid());
856             ++t;
857         }
858         PatternTerm& term()
859         {
860             ASSERT(alternativeValid());
861             return alternative()->m_terms[t];
862         }
863         bool isLastTerm()
864         {
865             ASSERT(alternativeValid());
866             return (t + 1) == alternative()->m_terms.size();
867         }
868         unsigned getSubParenNum()
869         {
870             return m_subParenNum++;
871         }
872         bool isMainDisjunction()
873         {
874             return !disjunction->m_parent;
875         }
876
877         void setJumpListToPriorParen(JumpList* jumpList)
878         {
879             m_jumpList = jumpList;
880         }
881
882         JumpList* getJumpListToPriorParen()
883         {
884             return m_jumpList;
885         }
886
887         PatternTerm& lookaheadTerm()
888         {
889             ASSERT(alternativeValid());
890             ASSERT((t + 1) < alternative()->m_terms.size());
891             return alternative()->m_terms[t + 1];
892         }
893         bool isSinglePatternCharacterLookaheadTerm()
894         {
895             ASSERT(alternativeValid());
896             return ((t + 1) < alternative()->m_terms.size())
897                 && (lookaheadTerm().type == PatternTerm::TypePatternCharacter)
898                 && (lookaheadTerm().quantityType == QuantifierFixedCount)
899                 && (lookaheadTerm().quantityCount == 1);
900         }
901
902         int inputOffset()
903         {
904             return term().inputPosition - checkedTotal;
905         }
906
907         void clearBacktrack()
908         {
909             m_backtrack.clear(false);
910             m_linkedBacktrack = 0;
911         }
912
913         void jumpToBacktrack(MacroAssembler* masm)
914         {
915             m_backtrack.jumpToBacktrack(masm);
916         }
917
918         void jumpToBacktrack(YarrGenerator* generator, Jump jump)
919         {
920             m_backtrack.jumpToBacktrack(generator, jump);
921         }
922
923         void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps)
924         {
925             m_backtrack.jumpToBacktrack(generator, jumps);
926         }
927
928         bool plantJumpToBacktrackIfExists(YarrGenerator* generator)
929         {
930             return m_backtrack.plantJumpToBacktrackIfExists(generator);
931         }
932
933         void linkDataLabelToBacktrackIfExists(YarrGenerator* generator, DataLabelPtr dataLabel)
934         {
935             // If we have a stack offset backtrack destination, use it directly
936             if (m_backtrack.isStackOffset()) {
937                 generator->m_expressionState.addIndirectJumpEntry(m_backtrack.getStackOffset(), dataLabel);
938                 m_backtrack.clearSubDataLabelPtr();
939             } else {
940                 // If we have a backtrack label, connect the datalabel to it directly.
941                 if (m_backtrack.isLabel())
942                     generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(dataLabel, m_backtrack.getLabel()));
943                 else
944                     setBacktrackDataLabel(dataLabel);
945             }
946         }
947
948         void addBacktrackJump(Jump jump)
949         {
950             m_backtrack.addBacktrackJump(jump);
951         }
952
953         void setBacktrackDataLabel(DataLabelPtr dp)
954         {
955             m_backtrack.setDataLabel(dp);
956         }
957
958         void setBackTrackStackOffset(int32_t stackOffset)
959         {
960             m_backtrack.setStackOffset(stackOffset);
961         }
962
963         void setBacktrackLabel(Label label)
964         {
965             m_backtrack.setLabel(label);
966         }
967
968         void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false)
969         {
970             m_backtrack.linkAlternativeBacktracks(generator, nextIteration);
971             m_linkedBacktrack = 0;
972         }
973
974         void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false)
975         {
976             m_backtrack.linkAlternativeBacktracksTo(generator, label, nextIteration);
977         }
978
979         void setBacktrackLink(BacktrackDestination* linkedBacktrack)
980         {
981             m_linkedBacktrack = linkedBacktrack;
982         }
983
984         void chainBacktracks(BacktrackDestination* followonBacktrack)
985         {
986             if (m_linkedBacktrack)
987                 m_linkedBacktrack->linkToNextBacktrack(followonBacktrack);
988         }
989
990         BacktrackDestination& getBacktrackDestination()
991         {
992             return m_backtrack;
993         }
994
995         void propagateBacktrackingFrom(YarrGenerator* generator, BacktrackDestination& backtrack, bool doJump = true)
996         {
997             if (doJump)
998                 m_backtrack.jumpToBacktrack(generator, backtrack.getBacktrackJumps());
999
1000             if (m_backtrack.isLabel() && backtrack.hasBacktrackToLabel())
1001                 backtrack.linkBacktrackToLabel(m_backtrack.getLabel());
1002
1003             if (backtrack.hasDestination()) {
1004                 if (m_backtrack.hasDataLabel())
1005                     generator->m_expressionState.addDataLabelToNextIteration(m_backtrack.getDataLabel());
1006
1007                 m_backtrack.copyTarget(backtrack, doJump);
1008             }
1009         }
1010
1011         PatternDisjunction* disjunction;
1012         int checkedTotal;
1013     private:
1014         unsigned alt;
1015         unsigned t;
1016         unsigned m_subParenNum;
1017         BacktrackDestination m_backtrack;
1018         BacktrackDestination* m_linkedBacktrack;
1019         JumpList* m_jumpList;
1020     };
1021
1022     struct ParenthesesTail {
1023         ParenthesesTail(PatternTerm& term, int nestingLevel, JumpList* jumpListToPriorParen)
1024             : m_term(term)
1025             , m_nestingLevel(nestingLevel)
1026             , m_subParenIndex(0)
1027             , m_jumpListToPriorParen(jumpListToPriorParen)
1028         {
1029         }
1030
1031         void processBacktracks(YarrGenerator* generator, TermGenerationState& state, TermGenerationState& parenthesesState, Label nonGreedyTryParentheses, Label fallThrough)
1032         {
1033             m_nonGreedyTryParentheses = nonGreedyTryParentheses;
1034             m_fallThrough = fallThrough;
1035
1036             m_subParenIndex = state.getSubParenNum();
1037             parenthesesState.getBacktrackDestination().copyTo(m_parenBacktrack);
1038             state.chainBacktracks(&m_backtrack);
1039             BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
1040             stateBacktrack.copyTo(m_backtrack);
1041             stateBacktrack.setBacktrackToLabel(&m_backtrackToLabel);
1042             state.setBacktrackLink(&m_backtrack);
1043             stateBacktrack.setSubDataLabelPtr(&m_dataAfterLabelPtr);
1044
1045             m_doDirectBacktrack = m_parenBacktrack.hasDestination();
1046
1047             if ((m_term.quantityType == QuantifierGreedy) || (m_term.quantityType == QuantifierNonGreedy))
1048                 m_doDirectBacktrack = false;
1049
1050             if (m_doDirectBacktrack)
1051                 state.propagateBacktrackingFrom(generator, m_parenBacktrack, false);
1052             else {
1053                 stateBacktrack.setBacktrackJumpList(&m_afterBacktrackJumps);
1054                 stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens);
1055             }
1056         }
1057
1058         void setNextIteration(Label nextIteration)
1059         {
1060             if (!m_nestingLevel && !m_backtrackToLabel.isSet())
1061                 m_backtrackToLabel = nextIteration;
1062         }
1063
1064         void addAfterParenJump(Jump jump)
1065         {
1066             m_afterBacktrackJumps.append(jump);
1067         }
1068
1069         bool generateCode(YarrGenerator* generator, JumpList& jumpsToNext, bool priorBackTrackFallThrough, bool nextBacktrackFallThrough)
1070         {
1071             const RegisterID indexTemporary = regT0;
1072             unsigned parenthesesFrameLocation = m_term.frameLocation;
1073             Jump fromPriorBacktrack;
1074             bool needJumpForPriorParenTail = false;
1075
1076             if (priorBackTrackFallThrough
1077                 && ((m_term.quantityType == QuantifierGreedy)
1078                  || (m_term.quantityType == QuantifierNonGreedy)
1079                  || (!m_doDirectBacktrack && m_parenBacktrack.hasDestination()))) {
1080                 // If the prior paren tail code assumed that it could fall through,
1081                 // but we need to generate after paren backtrack code, then provide
1082                 // a jump around that code for the prior paren tail code.
1083                 // A regular expressing like ((xxx)...)? needs this.
1084                 fromPriorBacktrack = generator->jump();
1085                 needJumpForPriorParenTail = true;
1086             }
1087
1088             if (!m_backtrack.hasDestination()) {
1089                 if (m_backtrackToLabel.isSet()) {
1090                     m_backtrack.setLabel(m_backtrackToLabel);
1091                     nextBacktrackFallThrough = false;
1092                 } else if (m_jumpListToPriorParen) {
1093                     // If we don't have a destination, go back to either the prior paren or the next outer paren.
1094                     m_backtrack.setBacktrackJumpList(m_jumpListToPriorParen);
1095                     nextBacktrackFallThrough = false;
1096                 } else
1097                     m_backtrack.setBacktrackJumpList(&jumpsToNext);
1098             } else
1099                 nextBacktrackFallThrough = false;
1100
1101             // A failure AFTER the parens jumps here - Backtrack to this paren
1102             m_backtrackFromAfterParens = generator->label();
1103
1104             if (m_dataAfterLabelPtr.isSet())
1105                 generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataAfterLabelPtr, m_backtrackFromAfterParens));
1106
1107             m_afterBacktrackJumps.link(generator);
1108
1109             if (m_term.quantityType == QuantifierGreedy) {
1110                 // If this is -1 we have now tested with both with and without the parens.
1111                 generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
1112                 m_backtrack.jumpToBacktrack(generator, generator->branch32(Equal, indexTemporary, TrustedImm32(-1)));
1113             } else if (m_term.quantityType == QuantifierNonGreedy) {
1114                 // If this is -1 we have now tested with both with and without the parens.
1115                 generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
1116                 generator->branch32(Equal, indexTemporary, TrustedImm32(-1)).linkTo(m_nonGreedyTryParentheses, generator);
1117             }
1118
1119             if (!m_doDirectBacktrack)
1120                 m_parenBacktrack.plantJumpToBacktrackIfExists(generator);
1121
1122             // A failure WITHIN the parens jumps here
1123             if (needJumpForPriorParenTail)
1124                 fromPriorBacktrack.link(generator);
1125             m_parenBacktrack.linkAlternativeBacktracks(generator);
1126             m_withinBacktrackJumps.link(generator);
1127
1128             if (m_term.capture())
1129                 generator->store32(TrustedImm32(-1), Address(output, (m_term.parentheses.subpatternId << 1) * sizeof(int)));
1130
1131             if (m_term.quantityType == QuantifierGreedy) {
1132                 generator->storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1133                 generator->jump().linkTo(m_fallThrough, generator);
1134                 nextBacktrackFallThrough = false;
1135             } else if (!nextBacktrackFallThrough)
1136                 m_backtrack.jumpToBacktrack(generator);
1137
1138             if (!m_doDirectBacktrack)
1139                 m_backtrack.setNextBacktrackLabel(m_backtrackFromAfterParens);
1140
1141             return nextBacktrackFallThrough;
1142         }
1143
1144         PatternTerm& m_term;
1145         int m_nestingLevel;
1146         unsigned m_subParenIndex;
1147         JumpList* m_jumpListToPriorParen;
1148         Label m_nonGreedyTryParentheses;
1149         Label m_fallThrough;
1150         Label m_backtrackToLabel;
1151         Label m_backtrackFromAfterParens;
1152         DataLabelPtr m_dataAfterLabelPtr;
1153         JumpList m_withinBacktrackJumps;
1154         JumpList m_afterBacktrackJumps;
1155         BacktrackDestination m_parenBacktrack;
1156         BacktrackDestination m_backtrack;
1157         bool m_doDirectBacktrack;
1158     };
1159
1160     void generateAssertionBOL(TermGenerationState& state)
1161     {
1162         PatternTerm& term = state.term();
1163
1164         if (m_pattern.m_multiline) {
1165             const RegisterID character = regT0;
1166
1167             JumpList matchDest;
1168             if (!term.inputPosition)
1169                 matchDest.append(branch32(Equal, index, Imm32(state.checkedTotal)));
1170
1171             readCharacter(state.inputOffset() - 1, character);
1172             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1173             state.jumpToBacktrack(this);
1174
1175             matchDest.link(this);
1176         } else {
1177             // Erk, really should poison out these alternatives early. :-/
1178             if (term.inputPosition)
1179                 state.jumpToBacktrack(this);
1180             else
1181                 state.jumpToBacktrack(this, branch32(NotEqual, index, Imm32(state.checkedTotal)));
1182         }
1183     }
1184
1185     void generateAssertionEOL(TermGenerationState& state)
1186     {
1187         PatternTerm& term = state.term();
1188
1189         if (m_pattern.m_multiline) {
1190             const RegisterID character = regT0;
1191
1192             JumpList matchDest;
1193             if (term.inputPosition == state.checkedTotal)
1194                 matchDest.append(atEndOfInput());
1195
1196             readCharacter(state.inputOffset(), character);
1197             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1198             state.jumpToBacktrack(this);
1199
1200             matchDest.link(this);
1201         } else {
1202             if (term.inputPosition == state.checkedTotal)
1203                 state.jumpToBacktrack(this, notAtEndOfInput());
1204             // Erk, really should poison out these alternatives early. :-/
1205             else
1206                 state.jumpToBacktrack(this);
1207         }
1208     }
1209
1210     // Also falls though on nextIsNotWordChar.
1211     void matchAssertionWordchar(TermGenerationState& state, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
1212     {
1213         const RegisterID character = regT0;
1214         PatternTerm& term = state.term();
1215
1216         if (term.inputPosition == state.checkedTotal)
1217             nextIsNotWordChar.append(atEndOfInput());
1218
1219         readCharacter(state.inputOffset(), character);
1220         matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
1221     }
1222
1223     void generateAssertionWordBoundary(TermGenerationState& state)
1224     {
1225         const RegisterID character = regT0;
1226         PatternTerm& term = state.term();
1227
1228         Jump atBegin;
1229         JumpList matchDest;
1230         if (!term.inputPosition)
1231             atBegin = branch32(Equal, index, Imm32(state.checkedTotal));
1232         readCharacter(state.inputOffset() - 1, character);
1233         matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
1234         if (!term.inputPosition)
1235             atBegin.link(this);
1236
1237         // We fall through to here if the last character was not a wordchar.
1238         JumpList nonWordCharThenWordChar;
1239         JumpList nonWordCharThenNonWordChar;
1240         if (term.invert()) {
1241             matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
1242             nonWordCharThenWordChar.append(jump());
1243         } else {
1244             matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
1245             nonWordCharThenNonWordChar.append(jump());
1246         }
1247         state.jumpToBacktrack(this, nonWordCharThenNonWordChar);
1248
1249         // We jump here if the last character was a wordchar.
1250         matchDest.link(this);
1251         JumpList wordCharThenWordChar;
1252         JumpList wordCharThenNonWordChar;
1253         if (term.invert()) {
1254             matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
1255             wordCharThenWordChar.append(jump());
1256         } else {
1257             matchAssertionWordchar(state, wordCharThenWordChar, wordCharThenNonWordChar);
1258             // This can fall-though!
1259         }
1260
1261         state.jumpToBacktrack(this, wordCharThenWordChar);
1262
1263         nonWordCharThenWordChar.link(this);
1264         wordCharThenNonWordChar.link(this);
1265     }
1266
1267     void generatePatternCharacterSingle(TermGenerationState& state)
1268     {
1269         const RegisterID character = regT0;
1270         UChar ch = state.term().patternCharacter;
1271
1272         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1273             readCharacter(state.inputOffset(), character);
1274             or32(TrustedImm32(32), character);
1275             state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1276         } else {
1277             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1278             state.jumpToBacktrack(this, jumpIfCharNotEquals(ch, state.inputOffset()));
1279         }
1280     }
1281
1282     void generatePatternCharacterPair(TermGenerationState& state)
1283     {
1284         const RegisterID character = regT0;
1285         UChar ch1 = state.term().patternCharacter;
1286         UChar ch2 = state.lookaheadTerm().patternCharacter;
1287
1288         int mask = 0;
1289         int chPair = ch1 | (ch2 << 16);
1290
1291         if (m_pattern.m_ignoreCase) {
1292             if (isASCIIAlpha(ch1))
1293                 mask |= 32;
1294             if (isASCIIAlpha(ch2))
1295                 mask |= 32 << 16;
1296         }
1297
1298         if (mask) {
1299             load32WithUnalignedHalfWords(BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), character);
1300             or32(Imm32(mask), character);
1301             state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(chPair | mask)));
1302         } else
1303             state.jumpToBacktrack(this, branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)));
1304     }
1305
1306     void generatePatternCharacterFixed(TermGenerationState& state)
1307     {
1308         const RegisterID character = regT0;
1309         const RegisterID countRegister = regT1;
1310         PatternTerm& term = state.term();
1311         UChar ch = term.patternCharacter;
1312
1313         move(index, countRegister);
1314         sub32(Imm32(term.quantityCount), countRegister);
1315
1316         Label loop(this);
1317         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1318             load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
1319             or32(TrustedImm32(32), character);
1320             state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1321         } else {
1322             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1323             state.jumpToBacktrack(this, branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)));
1324         }
1325         add32(TrustedImm32(1), countRegister);
1326         branch32(NotEqual, countRegister, index).linkTo(loop, this);
1327     }
1328
1329     void generatePatternCharacterGreedy(TermGenerationState& state)
1330     {
1331         const RegisterID character = regT0;
1332         const RegisterID countRegister = regT1;
1333         PatternTerm& term = state.term();
1334         UChar ch = term.patternCharacter;
1335
1336         move(TrustedImm32(0), countRegister);
1337
1338         JumpList failures;
1339         Label loop(this);
1340         failures.append(atEndOfInput());
1341         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1342             readCharacter(state.inputOffset(), character);
1343             or32(TrustedImm32(32), character);
1344             failures.append(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1345         } else {
1346             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1347             failures.append(jumpIfCharNotEquals(ch, state.inputOffset()));
1348         }
1349
1350         add32(TrustedImm32(1), countRegister);
1351         add32(TrustedImm32(1), index);
1352         if (term.quantityCount != quantifyInfinite) {
1353             branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
1354             failures.append(jump());
1355         } else
1356             jump(loop);
1357
1358         Label backtrackBegin(this);
1359         loadFromFrame(term.frameLocation, countRegister);
1360         state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
1361         sub32(TrustedImm32(1), countRegister);
1362         sub32(TrustedImm32(1), index);
1363
1364         failures.link(this);
1365
1366         storeToFrame(countRegister, term.frameLocation);
1367
1368         state.setBacktrackLabel(backtrackBegin);
1369     }
1370
1371     void generatePatternCharacterNonGreedy(TermGenerationState& state)
1372     {
1373         const RegisterID character = regT0;
1374         const RegisterID countRegister = regT1;
1375         PatternTerm& term = state.term();
1376         UChar ch = term.patternCharacter;
1377
1378         move(TrustedImm32(0), countRegister);
1379
1380         Jump firstTimeDoNothing = jump();
1381
1382         Label hardFail(this);
1383         sub32(countRegister, index);
1384         state.jumpToBacktrack(this);
1385
1386         Label backtrackBegin(this);
1387         loadFromFrame(term.frameLocation, countRegister);
1388
1389         atEndOfInput().linkTo(hardFail, this);
1390         if (term.quantityCount != quantifyInfinite)
1391             branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
1392         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1393             readCharacter(state.inputOffset(), character);
1394             or32(TrustedImm32(32), character);
1395             branch32(NotEqual, character, Imm32(Unicode::toLower(ch))).linkTo(hardFail, this);
1396         } else {
1397             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1398             jumpIfCharNotEquals(ch, state.inputOffset()).linkTo(hardFail, this);
1399         }
1400
1401         add32(TrustedImm32(1), countRegister);
1402         add32(TrustedImm32(1), index);
1403
1404         firstTimeDoNothing.link(this);
1405         storeToFrame(countRegister, term.frameLocation);
1406
1407         state.setBacktrackLabel(backtrackBegin);
1408     }
1409
1410     void generateCharacterClassSingle(TermGenerationState& state)
1411     {
1412         const RegisterID character = regT0;
1413         PatternTerm& term = state.term();
1414
1415         JumpList matchDest;
1416         readCharacter(state.inputOffset(), character);
1417         matchCharacterClass(character, matchDest, term.characterClass);
1418
1419         if (term.invert())
1420             state.jumpToBacktrack(this, matchDest);
1421         else {
1422             state.jumpToBacktrack(this);
1423             matchDest.link(this);
1424         }
1425     }
1426
1427     void generateCharacterClassFixed(TermGenerationState& state)
1428     {
1429         const RegisterID character = regT0;
1430         const RegisterID countRegister = regT1;
1431         PatternTerm& term = state.term();
1432
1433         move(index, countRegister);
1434         sub32(Imm32(term.quantityCount), countRegister);
1435
1436         Label loop(this);
1437         JumpList matchDest;
1438         load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
1439         matchCharacterClass(character, matchDest, term.characterClass);
1440
1441         if (term.invert())
1442             state.jumpToBacktrack(this, matchDest);
1443         else {
1444             state.jumpToBacktrack(this);
1445             matchDest.link(this);
1446         }
1447
1448         add32(TrustedImm32(1), countRegister);
1449         branch32(NotEqual, countRegister, index).linkTo(loop, this);
1450     }
1451
1452     void generateCharacterClassGreedy(TermGenerationState& state)
1453     {
1454         const RegisterID character = regT0;
1455         const RegisterID countRegister = regT1;
1456         PatternTerm& term = state.term();
1457
1458         move(TrustedImm32(0), countRegister);
1459
1460         JumpList failures;
1461         Label loop(this);
1462         failures.append(atEndOfInput());
1463
1464         if (term.invert()) {
1465             readCharacter(state.inputOffset(), character);
1466             matchCharacterClass(character, failures, term.characterClass);
1467         } else {
1468             JumpList matchDest;
1469             readCharacter(state.inputOffset(), character);
1470             matchCharacterClass(character, matchDest, term.characterClass);
1471             failures.append(jump());
1472             matchDest.link(this);
1473         }
1474
1475         add32(TrustedImm32(1), countRegister);
1476         add32(TrustedImm32(1), index);
1477         if (term.quantityCount != quantifyInfinite) {
1478             branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
1479             failures.append(jump());
1480         } else
1481             jump(loop);
1482
1483         Label backtrackBegin(this);
1484         loadFromFrame(term.frameLocation, countRegister);
1485         state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
1486         sub32(TrustedImm32(1), countRegister);
1487         sub32(TrustedImm32(1), index);
1488
1489         failures.link(this);
1490
1491         storeToFrame(countRegister, term.frameLocation);
1492
1493         state.setBacktrackLabel(backtrackBegin);
1494     }
1495
1496     void generateCharacterClassNonGreedy(TermGenerationState& state)
1497     {
1498         const RegisterID character = regT0;
1499         const RegisterID countRegister = regT1;
1500         PatternTerm& term = state.term();
1501
1502         move(TrustedImm32(0), countRegister);
1503
1504         Jump firstTimeDoNothing = jump();
1505
1506         Label hardFail(this);
1507         sub32(countRegister, index);
1508         state.jumpToBacktrack(this);
1509
1510         Label backtrackBegin(this);
1511         loadFromFrame(term.frameLocation, countRegister);
1512
1513         atEndOfInput().linkTo(hardFail, this);
1514         branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
1515
1516         JumpList matchDest;
1517         readCharacter(state.inputOffset(), character);
1518         matchCharacterClass(character, matchDest, term.characterClass);
1519
1520         if (term.invert())
1521             matchDest.linkTo(hardFail, this);
1522         else {
1523             jump(hardFail);
1524             matchDest.link(this);
1525         }
1526
1527         add32(TrustedImm32(1), countRegister);
1528         add32(TrustedImm32(1), index);
1529
1530         firstTimeDoNothing.link(this);
1531         storeToFrame(countRegister, term.frameLocation);
1532
1533         state.setBacktrackLabel(backtrackBegin);
1534     }
1535
1536     void generateParenthesesDisjunction(PatternTerm& parenthesesTerm, TermGenerationState& state, unsigned alternativeFrameLocation)
1537     {
1538         ASSERT((parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern) || (parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion));
1539         ASSERT(parenthesesTerm.quantityCount == 1);
1540
1541         PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
1542         unsigned preCheckedCount = ((parenthesesTerm.quantityType == QuantifierFixedCount) && (parenthesesTerm.type != PatternTerm::TypeParentheticalAssertion)) ? disjunction->m_minimumSize : 0;
1543
1544         if (disjunction->m_alternatives.size() == 1) {
1545             state.resetAlternative();
1546             ASSERT(state.alternativeValid());
1547             PatternAlternative* alternative = state.alternative();
1548             optimizeAlternative(alternative);
1549
1550             int countToCheck = alternative->m_minimumSize - preCheckedCount;
1551             if (countToCheck) {
1552                 ASSERT((parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion) || (parenthesesTerm.quantityType != QuantifierFixedCount));
1553
1554                 // FIXME: This is quite horrible.  The call to 'plantJumpToBacktrackIfExists'
1555                 // will be forced to always trampoline into here, just to decrement the index.
1556                 // Ick. 
1557                 Jump skip = jump();
1558
1559                 Label backtrackBegin(this);
1560                 sub32(Imm32(countToCheck), index);
1561                 state.addBacktrackJump(jump());
1562
1563                 skip.link(this);
1564
1565                 state.setBacktrackLabel(backtrackBegin);
1566
1567                 state.jumpToBacktrack(this, jumpIfNoAvailableInput(countToCheck));
1568                 state.checkedTotal += countToCheck;
1569             }
1570
1571             for (state.resetTerm(); state.termValid(); state.nextTerm())
1572                 generateTerm(state);
1573
1574             state.checkedTotal -= countToCheck;
1575         } else {
1576             JumpList successes;
1577             bool propogateBacktrack = false;
1578
1579             // Save current state's paren jump list for use with each alternative 
1580             JumpList* outerJumpList = state.getJumpListToPriorParen();
1581
1582             for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative(), state.setJumpListToPriorParen(outerJumpList)) {
1583                 PatternAlternative* alternative = state.alternative();
1584                 optimizeAlternative(alternative);
1585
1586                 ASSERT(alternative->m_minimumSize >= preCheckedCount);
1587                 int countToCheck = alternative->m_minimumSize - preCheckedCount;
1588                 if (countToCheck) {
1589                     state.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
1590                     state.checkedTotal += countToCheck;
1591                 }
1592
1593                 for (state.resetTerm(); state.termValid(); state.nextTerm())
1594                     generateTerm(state);
1595
1596                 // Matched an alternative.
1597                 DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation);
1598
1599                 if (!state.isLastAlternative() || countToCheck)
1600                     successes.append(jump());
1601
1602                 // Alternative did not match.
1603
1604                 // Do we have a backtrack destination?
1605                 //    if so, link the data label to it.
1606                 state.linkDataLabelToBacktrackIfExists(this, dataLabel);
1607
1608                 if (!state.isLastAlternative() || countToCheck)
1609                     state.linkAlternativeBacktracks(this);
1610
1611                 if (countToCheck) {
1612                     sub32(Imm32(countToCheck), index);
1613                     state.checkedTotal -= countToCheck;
1614                 } else if (state.isLastAlternative())
1615                     propogateBacktrack = true;
1616             }
1617             // We fall through to here when the last alternative fails.
1618             // Add a backtrack out of here for the parenthese handling code to link up.
1619             if (!propogateBacktrack)
1620                 state.addBacktrackJump(jump());
1621
1622             // Save address on stack for the parens code to backtrack to, to retry the
1623             // next alternative.
1624             state.setBackTrackStackOffset(alternativeFrameLocation * sizeof(void*));
1625
1626             successes.link(this);
1627         }
1628     }
1629
1630     void generateParenthesesSingle(TermGenerationState& state)
1631     {
1632         const RegisterID indexTemporary = regT0;
1633         PatternTerm& term = state.term();
1634         PatternDisjunction* disjunction = term.parentheses.disjunction;
1635         ASSERT(term.quantityCount == 1);
1636
1637         unsigned preCheckedCount = (term.quantityType == QuantifierFixedCount) ? disjunction->m_minimumSize : 0;
1638
1639         unsigned parenthesesFrameLocation = term.frameLocation;
1640         unsigned alternativeFrameLocation = parenthesesFrameLocation;
1641         if (term.quantityType != QuantifierFixedCount)
1642             alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1643
1644         // optimized case - no capture & no quantifier can be handled in a light-weight manner.
1645         if (!term.capture() && (term.quantityType == QuantifierFixedCount)) {
1646             m_expressionState.incrementParenNestingLevel();
1647
1648             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1649
1650             // Use the current state's jump list for the nested parentheses.
1651             parenthesesState.setJumpListToPriorParen(state.getJumpListToPriorParen());
1652
1653             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1654             // this expects that any backtracks back out of the parentheses will be in the
1655             // parenthesesState's m_backTrackJumps vector, and that if they need backtracking
1656             // they will have set an entry point on the parenthesesState's m_backtrackLabel.
1657             BacktrackDestination& parenthesesBacktrack = parenthesesState.getBacktrackDestination();
1658             BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
1659
1660             state.propagateBacktrackingFrom(this, parenthesesBacktrack);
1661             stateBacktrack.propagateBacktrackToLabel(parenthesesBacktrack);
1662
1663             state.setJumpListToPriorParen(parenthesesState.getJumpListToPriorParen());
1664
1665             m_expressionState.decrementParenNestingLevel();
1666         } else {
1667             Jump nonGreedySkipParentheses;
1668             Label nonGreedyTryParentheses;
1669             if (term.quantityType == QuantifierGreedy)
1670                 storeToFrame(index, parenthesesFrameLocation);
1671             else if (term.quantityType == QuantifierNonGreedy) {
1672                 storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1673                 nonGreedySkipParentheses = jump();
1674                 nonGreedyTryParentheses = label();
1675                 storeToFrame(index, parenthesesFrameLocation);
1676             }
1677
1678             // store the match start index
1679             if (term.capture()) {
1680                 int inputOffset = state.inputOffset() - preCheckedCount;
1681                 if (inputOffset) {
1682                     move(index, indexTemporary);
1683                     add32(Imm32(inputOffset), indexTemporary);
1684                     store32(indexTemporary, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
1685                 } else
1686                     store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
1687             }
1688
1689             ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getJumpListToPriorParen());
1690
1691             m_expressionState.incrementParenNestingLevel();
1692
1693             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1694
1695             // Save the parenthesesTail for backtracking from nested parens to this one.
1696             parenthesesState.setJumpListToPriorParen(&parenthesesTail->m_withinBacktrackJumps);
1697
1698             // generate the body of the parentheses
1699             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1700
1701             // For non-fixed counts, backtrack if we didn't match anything.
1702             if (term.quantityType != QuantifierFixedCount)
1703                 parenthesesTail->addAfterParenJump(branch32(Equal, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*)))));
1704
1705             // store the match end index
1706             if (term.capture()) {
1707                 int inputOffset = state.inputOffset();
1708                 if (inputOffset) {
1709                     move(index, indexTemporary);
1710                     add32(Imm32(state.inputOffset()), indexTemporary);
1711                     store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
1712                 } else
1713                     store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
1714             }
1715
1716             m_expressionState.decrementParenNestingLevel();
1717
1718             parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label());
1719
1720             state.setJumpListToPriorParen(&parenthesesTail->m_afterBacktrackJumps);
1721             
1722             parenthesesState.getBacktrackDestination().clear();
1723
1724             if (term.quantityType == QuantifierNonGreedy)
1725                 nonGreedySkipParentheses.link(this);
1726         }
1727     }
1728
1729     void generateParenthesesGreedyNoBacktrack(TermGenerationState& state)
1730     {
1731         PatternTerm& parenthesesTerm = state.term();
1732         PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
1733         ASSERT(parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern);
1734         ASSERT(parenthesesTerm.quantityCount != 1); // Handled by generateParenthesesSingle.
1735
1736         TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1737
1738         Label matchAgain(this);
1739
1740         storeToFrame(index, parenthesesTerm.frameLocation); // Save the current index to check for zero len matches later.
1741
1742         for (parenthesesState.resetAlternative(); parenthesesState.alternativeValid(); parenthesesState.nextAlternative()) {
1743
1744             PatternAlternative* alternative = parenthesesState.alternative();
1745             optimizeAlternative(alternative);
1746
1747             int countToCheck = alternative->m_minimumSize;
1748             if (countToCheck) {
1749                 parenthesesState.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
1750                 parenthesesState.checkedTotal += countToCheck;
1751             }
1752
1753             for (parenthesesState.resetTerm(); parenthesesState.termValid(); parenthesesState.nextTerm())
1754                 generateTerm(parenthesesState);
1755
1756             // If we get here, we matched! If the index advanced then try to match more since limit isn't supported yet.
1757             branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesTerm.frameLocation * sizeof(void*))), matchAgain);
1758
1759             // If we get here we matched, but we matched "" - cannot accept this alternative as is, so either backtrack,
1760             // or fall through to try the next alternative if no backtrack is available.
1761             parenthesesState.plantJumpToBacktrackIfExists(this);
1762
1763             parenthesesState.linkAlternativeBacktracks(this);
1764
1765             // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop.
1766
1767             if (countToCheck) {
1768                 sub32(Imm32(countToCheck), index);
1769                 parenthesesState.checkedTotal -= countToCheck;
1770             }
1771         }
1772
1773         // If the last alternative falls through to here, we have a failed match...
1774         // Which means that we match whatever we have matched up to this point (even if nothing).
1775     }
1776
1777     void generateParentheticalAssertion(TermGenerationState& state)
1778     {
1779         PatternTerm& term = state.term();
1780         PatternDisjunction* disjunction = term.parentheses.disjunction;
1781         ASSERT(term.quantityCount == 1);
1782         ASSERT(term.quantityType == QuantifierFixedCount);
1783
1784         unsigned parenthesesFrameLocation = term.frameLocation;
1785         unsigned alternativeFrameLocation = parenthesesFrameLocation + YarrStackSpaceForBackTrackInfoParentheticalAssertion;
1786
1787         int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;
1788
1789         if (term.invert()) {
1790             // Inverted case
1791             storeToFrame(index, parenthesesFrameLocation);
1792
1793             state.checkedTotal -= countCheckedAfterAssertion;
1794             if (countCheckedAfterAssertion)
1795                 sub32(Imm32(countCheckedAfterAssertion), index);
1796
1797             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1798             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1799             // Success! - which means - Fail!
1800             loadFromFrame(parenthesesFrameLocation, index);
1801             state.jumpToBacktrack(this);
1802
1803             // And fail means success.
1804             parenthesesState.linkAlternativeBacktracks(this);
1805
1806             loadFromFrame(parenthesesFrameLocation, index);
1807
1808             state.checkedTotal += countCheckedAfterAssertion;
1809         } else {
1810             // Normal case
1811             storeToFrame(index, parenthesesFrameLocation);
1812
1813             state.checkedTotal -= countCheckedAfterAssertion;
1814             if (countCheckedAfterAssertion)
1815                 sub32(Imm32(countCheckedAfterAssertion), index);
1816
1817             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1818             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1819             // Success! - which means - Success!
1820             loadFromFrame(parenthesesFrameLocation, index);
1821             Jump success = jump();
1822
1823             parenthesesState.linkAlternativeBacktracks(this);
1824
1825             loadFromFrame(parenthesesFrameLocation, index);
1826             state.jumpToBacktrack(this);
1827
1828             success.link(this);
1829
1830             state.checkedTotal += countCheckedAfterAssertion;
1831         }
1832     }
1833
1834     void generateTerm(TermGenerationState& state)
1835     {
1836         PatternTerm& term = state.term();
1837
1838         switch (term.type) {
1839         case PatternTerm::TypeAssertionBOL:
1840             generateAssertionBOL(state);
1841             break;
1842
1843         case PatternTerm::TypeAssertionEOL:
1844             generateAssertionEOL(state);
1845             break;
1846
1847         case PatternTerm::TypeAssertionWordBoundary:
1848             generateAssertionWordBoundary(state);
1849             break;
1850
1851         case PatternTerm::TypePatternCharacter:
1852             switch (term.quantityType) {
1853             case QuantifierFixedCount:
1854                 if (term.quantityCount == 1) {
1855                     if (state.isSinglePatternCharacterLookaheadTerm() && (state.lookaheadTerm().inputPosition == (term.inputPosition + 1))) {
1856                         generatePatternCharacterPair(state);
1857                         state.nextTerm();
1858                     } else
1859                         generatePatternCharacterSingle(state);
1860                 } else
1861                     generatePatternCharacterFixed(state);
1862                 break;
1863             case QuantifierGreedy:
1864                 generatePatternCharacterGreedy(state);
1865                 break;
1866             case QuantifierNonGreedy:
1867                 generatePatternCharacterNonGreedy(state);
1868                 break;
1869             }
1870             break;
1871
1872         case PatternTerm::TypeCharacterClass:
1873             switch (term.quantityType) {
1874             case QuantifierFixedCount:
1875                 if (term.quantityCount == 1)
1876                     generateCharacterClassSingle(state);
1877                 else
1878                     generateCharacterClassFixed(state);
1879                 break;
1880             case QuantifierGreedy:
1881                 generateCharacterClassGreedy(state);
1882                 break;
1883             case QuantifierNonGreedy:
1884                 generateCharacterClassNonGreedy(state);
1885                 break;
1886             }
1887             break;
1888
1889         case PatternTerm::TypeBackReference:
1890             m_shouldFallBack = true;
1891             break;
1892
1893         case PatternTerm::TypeForwardReference:
1894             break;
1895
1896         case PatternTerm::TypeParenthesesSubpattern:
1897             if (term.quantityCount == 1 && !term.parentheses.isCopy)
1898                 generateParenthesesSingle(state);
1899             else if (term.parentheses.isTerminal)
1900                 generateParenthesesGreedyNoBacktrack(state);
1901             else
1902                 m_shouldFallBack = true;
1903             break;
1904
1905         case PatternTerm::TypeParentheticalAssertion:
1906             generateParentheticalAssertion(state);
1907             break;
1908         }
1909     }
1910
1911     void generateDisjunction(PatternDisjunction* disjunction)
1912     {
1913         TermGenerationState state(disjunction, 0);
1914         state.resetAlternative();
1915
1916         // check availability for the next alternative
1917         int countCheckedForCurrentAlternative = 0;
1918         int countToCheckForFirstAlternative = 0;
1919         bool hasShorterAlternatives = false;
1920         bool setRepeatAlternativeLabels = false;
1921         JumpList notEnoughInputForPreviousAlternative;
1922         Label firstAlternative;
1923         Label firstAlternativeInputChecked;
1924
1925         // The label 'firstAlternative' is used to plant a check to see if there is 
1926         // sufficient input available to run the first repeating alternative.
1927         // The label 'firstAlternativeInputChecked' will jump directly to matching 
1928         // the first repeating alternative having skipped this check.
1929
1930         if (state.alternativeValid()) {
1931             PatternAlternative* alternative = state.alternative();
1932             if (!alternative->onceThrough()) {
1933                 firstAlternative = Label(this);
1934                 setRepeatAlternativeLabels = true;
1935             }
1936             countToCheckForFirstAlternative = alternative->m_minimumSize;
1937             state.checkedTotal += countToCheckForFirstAlternative;
1938             if (countToCheckForFirstAlternative)
1939                 notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
1940             countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
1941         }
1942
1943         if (setRepeatAlternativeLabels)
1944             firstAlternativeInputChecked = Label(this);
1945
1946         while (state.alternativeValid()) {
1947             PatternAlternative* alternative = state.alternative();
1948             optimizeAlternative(alternative);
1949
1950             // Track whether any alternatives are shorter than the first one.
1951             if (!alternative->onceThrough())
1952                 hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative);
1953
1954             for (state.resetTerm(); state.termValid(); state.nextTerm())
1955                 generateTerm(state);
1956
1957             // If we get here, the alternative matched.
1958             if (m_pattern.m_body->m_callFrameSize)
1959                 addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1960
1961             ASSERT(index != returnRegister);
1962             if (m_pattern.m_body->m_hasFixedSize) {
1963                 move(index, returnRegister);
1964                 if (alternative->m_minimumSize)
1965                     sub32(Imm32(alternative->m_minimumSize), returnRegister);
1966
1967                 store32(returnRegister, output);
1968             } else
1969                 load32(Address(output), returnRegister);
1970
1971             store32(index, Address(output, 4));
1972
1973             generateReturn();
1974
1975             state.nextAlternative();
1976             if (alternative->onceThrough() && state.alternativeValid())
1977                 state.clearBacktrack();
1978
1979             // if there are any more alternatives, plant the check for input before looping.
1980             if (state.alternativeValid()) {
1981                 state.setJumpListToPriorParen(0);
1982                 PatternAlternative* nextAlternative = state.alternative();
1983                 if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
1984                     // We have handled non-repeating alternatives, jump to next iteration 
1985                     // and loop over repeating alternatives.
1986                     state.jumpToBacktrack(this);
1987
1988                     countToCheckForFirstAlternative = nextAlternative->m_minimumSize;
1989
1990                     // If we get here, there the last input checked failed.
1991                     notEnoughInputForPreviousAlternative.link(this);
1992
1993                     state.linkAlternativeBacktracks(this);
1994
1995                     // Back up to start the looping alternatives.
1996                     if (countCheckedForCurrentAlternative)
1997                         sub32(Imm32(countCheckedForCurrentAlternative), index);
1998
1999                     firstAlternative = Label(this);
2000
2001                     state.checkedTotal = countToCheckForFirstAlternative;
2002                     if (countToCheckForFirstAlternative)
2003                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
2004
2005                     countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
2006
2007                     firstAlternativeInputChecked = Label(this);
2008
2009                     setRepeatAlternativeLabels = true;
2010                 } else {
2011                     int countToCheckForNextAlternative = nextAlternative->m_minimumSize;
2012
2013                     if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one.
2014                         // If we get here, then the last input checked failed.
2015                         notEnoughInputForPreviousAlternative.link(this);
2016
2017                         // Check if sufficent input available to run the next alternative 
2018                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
2019                         // We are now in the correct state to enter the next alternative; this add is only required
2020                         // to mirror and revert operation of the sub32, just below.
2021                         add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
2022
2023                         // If we get here, then the last input checked passed.
2024                         state.linkAlternativeBacktracks(this);
2025
2026                         // No need to check if we can run the next alternative, since it is shorter -
2027                         // just update index.
2028                         sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
2029                     } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one.
2030                         // If we get here, then the last input checked failed.
2031                         // If there is insufficient input to run the current alternative, and the next alternative is longer,
2032                         // then there is definitely not enough input to run it - don't even check. Just adjust index, as if
2033                         // we had checked.
2034                         notEnoughInputForPreviousAlternative.link(this);
2035                         add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index);
2036                         notEnoughInputForPreviousAlternative.append(jump());
2037
2038                         // The next alternative is longer than the current one; check the difference.
2039                         state.linkAlternativeBacktracks(this);
2040
2041                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
2042                     } else { // CASE 3: Both alternatives are the same length.
2043                         ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative);
2044
2045                         // If the next alterative is the same length as this one, then no need to check the input -
2046                         // if there was sufficent input to run the current alternative then there is sufficient
2047                         // input to run the next one; if not, there isn't.
2048                         state.linkAlternativeBacktracks(this);
2049                     }
2050                     state.checkedTotal -= countCheckedForCurrentAlternative;
2051                     countCheckedForCurrentAlternative = countToCheckForNextAlternative;
2052                     state.checkedTotal += countCheckedForCurrentAlternative;
2053                 }
2054             }
2055         }
2056
2057         // If we get here, all Alternatives failed...
2058
2059         state.checkedTotal -= countCheckedForCurrentAlternative;
2060
2061         if (!setRepeatAlternativeLabels) {
2062             // If there are no alternatives that need repeating (all are marked 'onceThrough') then just link
2063             // the match failures to this point, and fall through to the return below.
2064             state.linkAlternativeBacktracks(this, true);
2065
2066             notEnoughInputForPreviousAlternative.link(this);
2067         } else {
2068             // How much more input need there be to be able to retry from the first alternative?
2069             // examples:
2070             //   /yarr_jit/ or /wrec|pcre/
2071             //     In these examples we need check for one more input before looping.
2072             //   /yarr_jit|pcre/
2073             //     In this case we need check for 5 more input to loop (+4 to allow for the first alterative
2074             //     being four longer than the last alternative checked, and another +1 to effectively move
2075             //     the start position along by one).
2076             //   /yarr|rules/ or /wrec|notsomuch/
2077             //     In these examples, provided that there was sufficient input to have just been matching for
2078             //     the second alternative we can loop without checking for available input (since the second
2079             //     alternative is longer than the first).  In the latter example we need to decrement index
2080             //     (by 4) so the start position is only progressed by 1 from the last iteration.
2081             int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1;
2082
2083             // First, deal with the cases where there was sufficient input to try the last alternative.
2084             if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below.
2085                 state.linkAlternativeBacktracks(this, true);
2086             else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop!
2087                 state.linkAlternativeBacktracksTo(this, firstAlternativeInputChecked, true);
2088             else { // no need to check the input, but we do have some bookkeeping to do first.
2089                 state.linkAlternativeBacktracks(this, true);
2090
2091                 // Where necessary update our preserved start position.
2092                 if (!m_pattern.m_body->m_hasFixedSize) {
2093                     move(index, regT0);
2094                     sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
2095                     store32(regT0, Address(output));
2096                 }
2097
2098                 // Update index if necessary, and loop (without checking).
2099                 if (incrementForNextIter)
2100                     add32(Imm32(incrementForNextIter), index);
2101                 jump().linkTo(firstAlternativeInputChecked, this);
2102             }
2103
2104             notEnoughInputForPreviousAlternative.link(this);
2105             // Update our idea of the start position, if we're tracking this.
2106             if (!m_pattern.m_body->m_hasFixedSize) {
2107                 if (countCheckedForCurrentAlternative - 1) {
2108                     move(index, regT0);
2109                     sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
2110                     store32(regT0, Address(output));
2111                 } else
2112                     store32(index, Address(output));
2113             }
2114
2115             // Check if there is sufficent input to run the first alternative again.
2116             jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this);
2117             // No - insufficent input to run the first alteranative, are there any other alternatives we
2118             // might need to check?  If so, the last check will have left the index incremented by
2119             // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative
2120             // LESS input is available, to have the effect of just progressing the start position by 1
2121             // from the last iteration.  If this check passes we can just jump up to the check associated
2122             // with the first alternative in the loop.  This is a bit sad, since we'll end up trying the
2123             // first alternative again, and this check will fail (otherwise the check planted just above
2124             // here would have passed).  This is a bit sad, however it saves trying to do something more
2125             // complex here in compilation, and in the common case we should end up coallescing the checks.
2126             //
2127             // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least
2128             // of the minimum-alternative-lengths.  E.g. if I have two alternatives of length 200 and 150,
2129             // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there
2130             // is sufficient input to run either alternative (constantly failing).  If there had been only
2131             // one alternative, or if the shorter alternative had come first, we would have terminated
2132             // immediately. :-/
2133             if (hasShorterAlternatives)
2134                 jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this);
2135             // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true,
2136             // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ... 
2137             // but since we're about to return a failure this doesn't really matter!)
2138         }
2139
2140         if (m_pattern.m_body->m_callFrameSize)
2141             addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
2142
2143         move(TrustedImm32(-1), returnRegister);
2144
2145         generateReturn();
2146
2147         m_expressionState.emitParenthesesTail(this);
2148         m_expressionState.emitIndirectJumpTable(this);
2149         m_expressionState.linkToNextIteration(this);
2150     }
2151
2152     void generateEnter()
2153     {
2154 #if CPU(X86_64)
2155         push(X86Registers::ebp);
2156         move(stackPointerRegister, X86Registers::ebp);
2157         push(X86Registers::ebx);
2158 #elif CPU(X86)
2159         push(X86Registers::ebp);
2160         move(stackPointerRegister, X86Registers::ebp);
2161         // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
2162         push(X86Registers::ebx);
2163         push(X86Registers::edi);
2164         push(X86Registers::esi);
2165         // load output into edi (2 = saved ebp + return address).
2166     #if COMPILER(MSVC)
2167         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
2168         loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
2169         loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
2170         loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
2171     #else
2172         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
2173     #endif
2174 #elif CPU(ARM)
2175         push(ARMRegisters::r4);
2176         push(ARMRegisters::r5);
2177         push(ARMRegisters::r6);
2178 #if CPU(ARM_TRADITIONAL)
2179         push(ARMRegisters::r8); // scratch register
2180 #endif
2181         move(ARMRegisters::r3, output);
2182 #elif CPU(MIPS)
2183         // Do nothing.
2184 #endif
2185     }
2186
2187     void generateReturn()
2188     {
2189 #if CPU(X86_64)
2190         pop(X86Registers::ebx);
2191         pop(X86Registers::ebp);
2192 #elif CPU(X86)
2193         pop(X86Registers::esi);
2194         pop(X86Registers::edi);
2195         pop(X86Registers::ebx);
2196         pop(X86Registers::ebp);
2197 #elif CPU(ARM)
2198 #if CPU(ARM_TRADITIONAL)
2199         pop(ARMRegisters::r8); // scratch register
2200 #endif
2201         pop(ARMRegisters::r6);
2202         pop(ARMRegisters::r5);
2203         pop(ARMRegisters::r4);
2204 #elif CPU(MIPS)
2205         // Do nothing
2206 #endif
2207         ret();
2208     }
2209
2210 public:
2211     YarrGenerator(YarrPattern& pattern)
2212         : m_pattern(pattern)
2213         , m_shouldFallBack(false)
2214     {
2215     }
2216
2217     void generate()
2218     {
2219         generateEnter();
2220
2221         if (!m_pattern.m_body->m_hasFixedSize)
2222             store32(index, Address(output));
2223
2224         if (m_pattern.m_body->m_callFrameSize)
2225             subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
2226
2227         generateDisjunction(m_pattern.m_body);
2228     }
2229
2230     void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject)
2231     {
2232         generate();
2233
2234         LinkBuffer patchBuffer(this, globalData->regexAllocator.poolForSize(size()), 0);
2235
2236         for (unsigned i = 0; i < m_expressionState.m_backtrackRecords.size(); ++i)
2237             patchBuffer.patch(m_expressionState.m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_expressionState.m_backtrackRecords[i].backtrackLocation));
2238
2239         jitObject.set(patchBuffer.finalizeCode());
2240         jitObject.setFallBack(m_shouldFallBack);
2241     }
2242
2243 private:
2244     YarrPattern& m_pattern;
2245     bool m_shouldFallBack;
2246     GenerationState m_expressionState;
2247 };
2248
2249 void jitCompile(YarrPattern& pattern, JSGlobalData* globalData, YarrCodeBlock& jitObject)
2250 {
2251     YarrGenerator(pattern).compile(globalData, jitObject);
2252 }
2253
2254 int execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output)
2255 {
2256     return jitObject.execute(input, start, length, output);
2257 }
2258
2259 }}
2260
2261 #endif