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