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