8a8397be9aa15d7e2cd3a000605e663f546e7ef9
[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                 else
956                     setBacktrackDataLabel(dataLabel);
957             }
958         }
959
960         void addBacktrackJump(Jump jump)
961         {
962             m_backtrack.addBacktrackJump(jump);
963         }
964
965         void setBacktrackDataLabel(DataLabelPtr dp)
966         {
967             m_backtrack.setDataLabel(dp);
968         }
969
970         void setBackTrackStackOffset(int32_t stackOffset)
971         {
972             m_backtrack.setStackOffset(stackOffset);
973         }
974
975         void setBacktrackLabel(Label label)
976         {
977             m_backtrack.setLabel(label);
978         }
979
980         void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false)
981         {
982             m_backtrack.linkAlternativeBacktracks(generator, nextIteration);
983             m_linkedBacktrack = 0;
984         }
985
986         void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false)
987         {
988             m_backtrack.linkAlternativeBacktracksTo(generator, label, nextIteration);
989         }
990
991         void setBacktrackLink(BacktrackDestination* linkedBacktrack)
992         {
993             m_linkedBacktrack = linkedBacktrack;
994         }
995
996         void chainBacktracks(BacktrackDestination* followonBacktrack)
997         {
998             if (m_linkedBacktrack)
999                 m_linkedBacktrack->linkToNextBacktrack(followonBacktrack);
1000         }
1001
1002         BacktrackDestination& getBacktrackDestination()
1003         {
1004             return m_backtrack;
1005         }
1006
1007         void propagateBacktrackingFrom(YarrGenerator* generator, BacktrackDestination& backtrack, bool doJump = true)
1008         {
1009             if (doJump)
1010                 m_backtrack.jumpToBacktrack(generator, backtrack.getBacktrackJumps());
1011
1012             if (m_backtrack.isLabel() && backtrack.hasBacktrackToLabel())
1013                 backtrack.linkBacktrackToLabel(m_backtrack.getLabel());
1014
1015             if (backtrack.hasDestination()) {
1016                 if (m_backtrack.hasDataLabel())
1017                     generator->m_expressionState.addDataLabelToNextIteration(m_backtrack.getDataLabel());
1018
1019                 m_backtrack.copyTarget(backtrack, doJump);
1020             }
1021         }
1022
1023         PatternDisjunction* disjunction;
1024         int checkedTotal;
1025     private:
1026         unsigned alt;
1027         unsigned t;
1028         unsigned m_subParenNum;
1029         BacktrackDestination m_backtrack;
1030         BacktrackDestination* m_linkedBacktrack;
1031         JumpList* m_jumpList;
1032     };
1033
1034     struct ParenthesesTail {
1035         ParenthesesTail(PatternTerm& term, int nestingLevel, JumpList* jumpListToPriorParen)
1036             : m_term(term)
1037             , m_nestingLevel(nestingLevel)
1038             , m_subParenIndex(0)
1039             , m_jumpListToPriorParen(jumpListToPriorParen)
1040         {
1041         }
1042
1043         void processBacktracks(YarrGenerator* generator, TermGenerationState& state, TermGenerationState& parenthesesState, Label nonGreedyTryParentheses, Label fallThrough)
1044         {
1045             m_nonGreedyTryParentheses = nonGreedyTryParentheses;
1046             m_fallThrough = fallThrough;
1047
1048             m_subParenIndex = state.getSubParenNum();
1049             parenthesesState.getBacktrackDestination().copyTo(m_parenBacktrack);
1050             state.chainBacktracks(&m_backtrack);
1051             BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
1052             stateBacktrack.copyTo(m_backtrack);
1053             stateBacktrack.setBacktrackToLabel(&m_backtrackToLabel);
1054             state.setBacktrackLink(&m_backtrack);
1055             stateBacktrack.setSubDataLabelPtr(&m_dataAfterLabelPtr);
1056
1057             m_doDirectBacktrack = m_parenBacktrack.hasDestination();
1058
1059             if ((m_term.quantityType == QuantifierGreedy) || (m_term.quantityType == QuantifierNonGreedy))
1060                 m_doDirectBacktrack = false;
1061
1062             if (m_doDirectBacktrack)
1063                 state.propagateBacktrackingFrom(generator, m_parenBacktrack, false);
1064             else {
1065                 stateBacktrack.setBacktrackJumpList(&m_afterBacktrackJumps);
1066                 stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens);
1067             }
1068         }
1069
1070         void setNextIteration(Label nextIteration)
1071         {
1072             if (!m_nestingLevel && !m_backtrackToLabel.isSet())
1073                 m_backtrackToLabel = nextIteration;
1074         }
1075
1076         void addAfterParenJump(Jump jump)
1077         {
1078             m_afterBacktrackJumps.append(jump);
1079         }
1080
1081         bool generateCode(YarrGenerator* generator, JumpList& jumpsToNext, bool priorBackTrackFallThrough, bool nextBacktrackFallThrough)
1082         {
1083             const RegisterID indexTemporary = regT0;
1084             unsigned parenthesesFrameLocation = m_term.frameLocation;
1085             Jump fromPriorBacktrack;
1086             bool needJumpForPriorParenTail = false;
1087
1088             if (priorBackTrackFallThrough
1089                 && ((m_term.quantityType == QuantifierGreedy)
1090                  || (m_term.quantityType == QuantifierNonGreedy)
1091                  || (!m_doDirectBacktrack && m_parenBacktrack.hasDestination()))) {
1092                 // If the prior paren tail code assumed that it could fall through,
1093                 // but we need to generate after paren backtrack code, then provide
1094                 // a jump around that code for the prior paren tail code.
1095                 // A regular expressing like ((xxx)...)? needs this.
1096                 fromPriorBacktrack = generator->jump();
1097                 needJumpForPriorParenTail = true;
1098             }
1099
1100             if (!m_backtrack.hasDestination()) {
1101                 if (m_backtrackToLabel.isSet()) {
1102                     m_backtrack.setLabel(m_backtrackToLabel);
1103                     nextBacktrackFallThrough = false;
1104                 } else if (m_jumpListToPriorParen) {
1105                     // If we don't have a destination, go back to either the prior paren or the next outer paren.
1106                     m_backtrack.setBacktrackJumpList(m_jumpListToPriorParen);
1107                     nextBacktrackFallThrough = false;
1108                 } else
1109                     m_backtrack.setBacktrackJumpList(&jumpsToNext);
1110             } else
1111                 nextBacktrackFallThrough = false;
1112
1113             // A failure AFTER the parens jumps here - Backtrack to this paren
1114             m_backtrackFromAfterParens = generator->label();
1115
1116             if (m_dataAfterLabelPtr.isSet())
1117                 generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataAfterLabelPtr, m_backtrackFromAfterParens));
1118
1119             m_afterBacktrackJumps.link(generator);
1120
1121             if (m_term.quantityType == QuantifierGreedy) {
1122                 // If this is -1 we have now tested with both with and without the parens.
1123                 generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
1124                 m_backtrack.jumpToBacktrack(generator, generator->branch32(Equal, indexTemporary, TrustedImm32(-1)));
1125             } else if (m_term.quantityType == QuantifierNonGreedy) {
1126                 // If this is -1 we have now tested with both with and without the parens.
1127                 generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
1128                 generator->branch32(Equal, indexTemporary, TrustedImm32(-1)).linkTo(m_nonGreedyTryParentheses, generator);
1129             }
1130
1131             if (!m_doDirectBacktrack)
1132                 m_parenBacktrack.plantJumpToBacktrackIfExists(generator);
1133
1134             // A failure WITHIN the parens jumps here
1135             if (needJumpForPriorParenTail)
1136                 fromPriorBacktrack.link(generator);
1137             m_parenBacktrack.linkAlternativeBacktracks(generator);
1138             m_withinBacktrackJumps.link(generator);
1139
1140             if (m_term.capture())
1141                 generator->store32(TrustedImm32(-1), Address(output, (m_term.parentheses.subpatternId << 1) * sizeof(int)));
1142
1143             if (m_term.quantityType == QuantifierGreedy) {
1144                 generator->storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1145                 generator->jump().linkTo(m_fallThrough, generator);
1146                 nextBacktrackFallThrough = false;
1147             } else if (!nextBacktrackFallThrough)
1148                 m_backtrack.jumpToBacktrack(generator);
1149
1150             if (!m_doDirectBacktrack)
1151                 m_backtrack.setNextBacktrackLabel(m_backtrackFromAfterParens);
1152
1153             return nextBacktrackFallThrough;
1154         }
1155
1156         PatternTerm& m_term;
1157         int m_nestingLevel;
1158         unsigned m_subParenIndex;
1159         JumpList* m_jumpListToPriorParen;
1160         Label m_nonGreedyTryParentheses;
1161         Label m_fallThrough;
1162         Label m_backtrackToLabel;
1163         Label m_backtrackFromAfterParens;
1164         DataLabelPtr m_dataAfterLabelPtr;
1165         JumpList m_withinBacktrackJumps;
1166         JumpList m_afterBacktrackJumps;
1167         BacktrackDestination m_parenBacktrack;
1168         BacktrackDestination m_backtrack;
1169         bool m_doDirectBacktrack;
1170     };
1171
1172     void generateAssertionBOL(TermGenerationState& state)
1173     {
1174         PatternTerm& term = state.term();
1175
1176         if (m_pattern.m_multiline) {
1177             const RegisterID character = regT0;
1178
1179             JumpList matchDest;
1180             if (!term.inputPosition)
1181                 matchDest.append(branch32(Equal, index, Imm32(state.checkedTotal)));
1182
1183             readCharacter(state.inputOffset() - 1, character);
1184             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1185             state.jumpToBacktrack(this);
1186
1187             matchDest.link(this);
1188         } else {
1189             // Erk, really should poison out these alternatives early. :-/
1190             if (term.inputPosition)
1191                 state.jumpToBacktrack(this);
1192             else
1193                 state.jumpToBacktrack(this, branch32(NotEqual, index, Imm32(state.checkedTotal)));
1194         }
1195     }
1196
1197     void generateAssertionEOL(TermGenerationState& state)
1198     {
1199         PatternTerm& term = state.term();
1200
1201         if (m_pattern.m_multiline) {
1202             const RegisterID character = regT0;
1203
1204             JumpList matchDest;
1205             if (term.inputPosition == state.checkedTotal)
1206                 matchDest.append(atEndOfInput());
1207
1208             readCharacter(state.inputOffset(), character);
1209             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1210             state.jumpToBacktrack(this);
1211
1212             matchDest.link(this);
1213         } else {
1214             if (term.inputPosition == state.checkedTotal)
1215                 state.jumpToBacktrack(this, notAtEndOfInput());
1216             // Erk, really should poison out these alternatives early. :-/
1217             else
1218                 state.jumpToBacktrack(this);
1219         }
1220     }
1221
1222     // Also falls though on nextIsNotWordChar.
1223     void matchAssertionWordchar(TermGenerationState& state, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
1224     {
1225         const RegisterID character = regT0;
1226         PatternTerm& term = state.term();
1227
1228         if (term.inputPosition == state.checkedTotal)
1229             nextIsNotWordChar.append(atEndOfInput());
1230
1231         readCharacter(state.inputOffset(), character);
1232         matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
1233     }
1234
1235     void generateAssertionWordBoundary(TermGenerationState& state)
1236     {
1237         const RegisterID character = regT0;
1238         PatternTerm& term = state.term();
1239
1240         Jump atBegin;
1241         JumpList matchDest;
1242         if (!term.inputPosition)
1243             atBegin = branch32(Equal, index, Imm32(state.checkedTotal));
1244         readCharacter(state.inputOffset() - 1, character);
1245         matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
1246         if (!term.inputPosition)
1247             atBegin.link(this);
1248
1249         // We fall through to here if the last character was not a wordchar.
1250         JumpList nonWordCharThenWordChar;
1251         JumpList nonWordCharThenNonWordChar;
1252         if (term.invert()) {
1253             matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
1254             nonWordCharThenWordChar.append(jump());
1255         } else {
1256             matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
1257             nonWordCharThenNonWordChar.append(jump());
1258         }
1259         state.jumpToBacktrack(this, nonWordCharThenNonWordChar);
1260
1261         // We jump here if the last character was a wordchar.
1262         matchDest.link(this);
1263         JumpList wordCharThenWordChar;
1264         JumpList wordCharThenNonWordChar;
1265         if (term.invert()) {
1266             matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
1267             wordCharThenWordChar.append(jump());
1268         } else {
1269             matchAssertionWordchar(state, wordCharThenWordChar, wordCharThenNonWordChar);
1270             // This can fall-though!
1271         }
1272
1273         state.jumpToBacktrack(this, wordCharThenWordChar);
1274
1275         nonWordCharThenWordChar.link(this);
1276         wordCharThenNonWordChar.link(this);
1277     }
1278
1279     void generatePatternCharacterSingle(TermGenerationState& state)
1280     {
1281         const RegisterID character = regT0;
1282         UChar ch = state.term().patternCharacter;
1283
1284         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1285             readCharacter(state.inputOffset(), character);
1286             or32(TrustedImm32(32), character);
1287             state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1288         } else {
1289             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1290             state.jumpToBacktrack(this, jumpIfCharNotEquals(ch, state.inputOffset()));
1291         }
1292     }
1293
1294     void generatePatternCharacterPair(TermGenerationState& state)
1295     {
1296         const RegisterID character = regT0;
1297         UChar ch1 = state.term().patternCharacter;
1298         UChar ch2 = state.lookaheadTerm().patternCharacter;
1299
1300         int mask = 0;
1301         int chPair = ch1 | (ch2 << 16);
1302
1303         if (m_pattern.m_ignoreCase) {
1304             if (isASCIIAlpha(ch1))
1305                 mask |= 32;
1306             if (isASCIIAlpha(ch2))
1307                 mask |= 32 << 16;
1308         }
1309
1310         if (mask) {
1311             load32WithUnalignedHalfWords(BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), character);
1312             or32(Imm32(mask), character);
1313             state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(chPair | mask)));
1314         } else
1315             state.jumpToBacktrack(this, branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)));
1316     }
1317
1318     void generatePatternCharacterFixed(TermGenerationState& state)
1319     {
1320         const RegisterID character = regT0;
1321         const RegisterID countRegister = regT1;
1322         PatternTerm& term = state.term();
1323         UChar ch = term.patternCharacter;
1324
1325         move(index, countRegister);
1326         sub32(Imm32(term.quantityCount), countRegister);
1327
1328         Label loop(this);
1329         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1330             load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
1331             or32(TrustedImm32(32), character);
1332             state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1333         } else {
1334             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1335             state.jumpToBacktrack(this, branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)));
1336         }
1337         add32(TrustedImm32(1), countRegister);
1338         branch32(NotEqual, countRegister, index).linkTo(loop, this);
1339     }
1340
1341     void generatePatternCharacterGreedy(TermGenerationState& state)
1342     {
1343         const RegisterID character = regT0;
1344         const RegisterID countRegister = regT1;
1345         PatternTerm& term = state.term();
1346         UChar ch = term.patternCharacter;
1347
1348         move(TrustedImm32(0), countRegister);
1349
1350         JumpList failures;
1351         Label loop(this);
1352         failures.append(atEndOfInput());
1353         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1354             readCharacter(state.inputOffset(), character);
1355             or32(TrustedImm32(32), character);
1356             failures.append(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1357         } else {
1358             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1359             failures.append(jumpIfCharNotEquals(ch, state.inputOffset()));
1360         }
1361
1362         add32(TrustedImm32(1), countRegister);
1363         add32(TrustedImm32(1), index);
1364         if (term.quantityCount != quantifyInfinite) {
1365             branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
1366             failures.append(jump());
1367         } else
1368             jump(loop);
1369
1370         Label backtrackBegin(this);
1371         loadFromFrame(term.frameLocation, countRegister);
1372         state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
1373         sub32(TrustedImm32(1), countRegister);
1374         sub32(TrustedImm32(1), index);
1375
1376         failures.link(this);
1377
1378         storeToFrame(countRegister, term.frameLocation);
1379
1380         state.setBacktrackLabel(backtrackBegin);
1381     }
1382
1383     void generatePatternCharacterNonGreedy(TermGenerationState& state)
1384     {
1385         const RegisterID character = regT0;
1386         const RegisterID countRegister = regT1;
1387         PatternTerm& term = state.term();
1388         UChar ch = term.patternCharacter;
1389
1390         move(TrustedImm32(0), countRegister);
1391
1392         Jump firstTimeDoNothing = jump();
1393
1394         Label hardFail(this);
1395         sub32(countRegister, index);
1396         state.jumpToBacktrack(this);
1397
1398         Label backtrackBegin(this);
1399         loadFromFrame(term.frameLocation, countRegister);
1400
1401         atEndOfInput().linkTo(hardFail, this);
1402         if (term.quantityCount != quantifyInfinite)
1403             branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
1404         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1405             readCharacter(state.inputOffset(), character);
1406             or32(TrustedImm32(32), character);
1407             branch32(NotEqual, character, Imm32(Unicode::toLower(ch))).linkTo(hardFail, this);
1408         } else {
1409             ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1410             jumpIfCharNotEquals(ch, state.inputOffset()).linkTo(hardFail, this);
1411         }
1412
1413         add32(TrustedImm32(1), countRegister);
1414         add32(TrustedImm32(1), index);
1415
1416         firstTimeDoNothing.link(this);
1417         storeToFrame(countRegister, term.frameLocation);
1418
1419         state.setBacktrackLabel(backtrackBegin);
1420     }
1421
1422     void generateCharacterClassSingle(TermGenerationState& state)
1423     {
1424         const RegisterID character = regT0;
1425         PatternTerm& term = state.term();
1426
1427         JumpList matchDest;
1428         readCharacter(state.inputOffset(), character);
1429         matchCharacterClass(character, matchDest, term.characterClass);
1430
1431         if (term.invert())
1432             state.jumpToBacktrack(this, matchDest);
1433         else {
1434             state.jumpToBacktrack(this);
1435             matchDest.link(this);
1436         }
1437     }
1438
1439     void generateCharacterClassFixed(TermGenerationState& state)
1440     {
1441         const RegisterID character = regT0;
1442         const RegisterID countRegister = regT1;
1443         PatternTerm& term = state.term();
1444
1445         move(index, countRegister);
1446         sub32(Imm32(term.quantityCount), countRegister);
1447
1448         Label loop(this);
1449         JumpList matchDest;
1450         load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
1451         matchCharacterClass(character, matchDest, term.characterClass);
1452
1453         if (term.invert())
1454             state.jumpToBacktrack(this, matchDest);
1455         else {
1456             state.jumpToBacktrack(this);
1457             matchDest.link(this);
1458         }
1459
1460         add32(TrustedImm32(1), countRegister);
1461         branch32(NotEqual, countRegister, index).linkTo(loop, this);
1462     }
1463
1464     void generateCharacterClassGreedy(TermGenerationState& state)
1465     {
1466         const RegisterID character = regT0;
1467         const RegisterID countRegister = regT1;
1468         PatternTerm& term = state.term();
1469
1470         move(TrustedImm32(0), countRegister);
1471
1472         JumpList failures;
1473         Label loop(this);
1474         failures.append(atEndOfInput());
1475
1476         if (term.invert()) {
1477             readCharacter(state.inputOffset(), character);
1478             matchCharacterClass(character, failures, term.characterClass);
1479         } else {
1480             JumpList matchDest;
1481             readCharacter(state.inputOffset(), character);
1482             matchCharacterClass(character, matchDest, term.characterClass);
1483             failures.append(jump());
1484             matchDest.link(this);
1485         }
1486
1487         add32(TrustedImm32(1), countRegister);
1488         add32(TrustedImm32(1), index);
1489         if (term.quantityCount != quantifyInfinite) {
1490             branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
1491             failures.append(jump());
1492         } else
1493             jump(loop);
1494
1495         Label backtrackBegin(this);
1496         loadFromFrame(term.frameLocation, countRegister);
1497         state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
1498         sub32(TrustedImm32(1), countRegister);
1499         sub32(TrustedImm32(1), index);
1500
1501         failures.link(this);
1502
1503         storeToFrame(countRegister, term.frameLocation);
1504
1505         state.setBacktrackLabel(backtrackBegin);
1506     }
1507
1508     void generateCharacterClassNonGreedy(TermGenerationState& state)
1509     {
1510         const RegisterID character = regT0;
1511         const RegisterID countRegister = regT1;
1512         PatternTerm& term = state.term();
1513
1514         move(TrustedImm32(0), countRegister);
1515
1516         Jump firstTimeDoNothing = jump();
1517
1518         Label hardFail(this);
1519         sub32(countRegister, index);
1520         state.jumpToBacktrack(this);
1521
1522         Label backtrackBegin(this);
1523         loadFromFrame(term.frameLocation, countRegister);
1524
1525         atEndOfInput().linkTo(hardFail, this);
1526         branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
1527
1528         JumpList matchDest;
1529         readCharacter(state.inputOffset(), character);
1530         matchCharacterClass(character, matchDest, term.characterClass);
1531
1532         if (term.invert())
1533             matchDest.linkTo(hardFail, this);
1534         else {
1535             jump(hardFail);
1536             matchDest.link(this);
1537         }
1538
1539         add32(TrustedImm32(1), countRegister);
1540         add32(TrustedImm32(1), index);
1541
1542         firstTimeDoNothing.link(this);
1543         storeToFrame(countRegister, term.frameLocation);
1544
1545         state.setBacktrackLabel(backtrackBegin);
1546     }
1547
1548     void generateParenthesesDisjunction(PatternTerm& parenthesesTerm, TermGenerationState& state, unsigned alternativeFrameLocation)
1549     {
1550         ASSERT((parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern) || (parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion));
1551         ASSERT(parenthesesTerm.quantityCount == 1);
1552
1553         PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
1554         unsigned preCheckedCount = ((parenthesesTerm.quantityType == QuantifierFixedCount) && (parenthesesTerm.type != PatternTerm::TypeParentheticalAssertion)) ? disjunction->m_minimumSize : 0;
1555
1556         if (disjunction->m_alternatives.size() == 1) {
1557             state.resetAlternative();
1558             ASSERT(state.alternativeValid());
1559             PatternAlternative* alternative = state.alternative();
1560             optimizeAlternative(alternative);
1561
1562             int countToCheck = alternative->m_minimumSize - preCheckedCount;
1563             if (countToCheck) {
1564                 ASSERT((parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion) || (parenthesesTerm.quantityType != QuantifierFixedCount));
1565
1566                 // FIXME: This is quite horrible.  The call to 'plantJumpToBacktrackIfExists'
1567                 // will be forced to always trampoline into here, just to decrement the index.
1568                 // Ick. 
1569                 Jump skip = jump();
1570
1571                 Label backtrackBegin(this);
1572                 sub32(Imm32(countToCheck), index);
1573                 state.addBacktrackJump(jump());
1574
1575                 skip.link(this);
1576
1577                 state.setBacktrackLabel(backtrackBegin);
1578
1579                 state.jumpToBacktrack(this, jumpIfNoAvailableInput(countToCheck));
1580                 state.checkedTotal += countToCheck;
1581             }
1582
1583             for (state.resetTerm(); state.termValid(); state.nextTerm())
1584                 generateTerm(state);
1585
1586             state.checkedTotal -= countToCheck;
1587         } else {
1588             JumpList successes;
1589             bool propogateBacktrack = false;
1590
1591             // Save current state's paren jump list for use with each alternative 
1592             JumpList* outerJumpList = state.getJumpListToPriorParen();
1593
1594             for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative(), state.setJumpListToPriorParen(outerJumpList)) {
1595                 PatternAlternative* alternative = state.alternative();
1596                 optimizeAlternative(alternative);
1597
1598                 ASSERT(alternative->m_minimumSize >= preCheckedCount);
1599                 int countToCheck = alternative->m_minimumSize - preCheckedCount;
1600                 if (countToCheck) {
1601                     state.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
1602                     state.checkedTotal += countToCheck;
1603                 }
1604
1605                 for (state.resetTerm(); state.termValid(); state.nextTerm())
1606                     generateTerm(state);
1607
1608                 // Matched an alternative.
1609                 DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation);
1610
1611                 if (!state.isLastAlternative() || countToCheck)
1612                     successes.append(jump());
1613
1614                 // Alternative did not match.
1615
1616                 // Do we have a backtrack destination?
1617                 //    if so, link the data label to it.
1618                 state.linkDataLabelToBacktrackIfExists(this, dataLabel);
1619
1620                 if (!state.isLastAlternative() || countToCheck)
1621                     state.linkAlternativeBacktracks(this);
1622
1623                 if (countToCheck) {
1624                     sub32(Imm32(countToCheck), index);
1625                     state.checkedTotal -= countToCheck;
1626                 } else if (state.isLastAlternative())
1627                     propogateBacktrack = true;
1628             }
1629             // We fall through to here when the last alternative fails.
1630             // Add a backtrack out of here for the parenthese handling code to link up.
1631             if (!propogateBacktrack)
1632                 state.addBacktrackJump(jump());
1633
1634             // Save address on stack for the parens code to backtrack to, to retry the
1635             // next alternative.
1636             state.setBackTrackStackOffset(alternativeFrameLocation * sizeof(void*));
1637
1638             successes.link(this);
1639         }
1640     }
1641
1642     void generateParenthesesSingle(TermGenerationState& state)
1643     {
1644         const RegisterID indexTemporary = regT0;
1645         PatternTerm& term = state.term();
1646         PatternDisjunction* disjunction = term.parentheses.disjunction;
1647         ASSERT(term.quantityCount == 1);
1648
1649         unsigned preCheckedCount = (term.quantityType == QuantifierFixedCount) ? disjunction->m_minimumSize : 0;
1650
1651         unsigned parenthesesFrameLocation = term.frameLocation;
1652         unsigned alternativeFrameLocation = parenthesesFrameLocation;
1653         if (term.quantityType != QuantifierFixedCount)
1654             alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1655
1656         // optimized case - no capture & no quantifier can be handled in a light-weight manner.
1657         if (!term.capture() && (term.quantityType == QuantifierFixedCount)) {
1658             m_expressionState.incrementParenNestingLevel();
1659
1660             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1661
1662             // Use the current state's jump list for the nested parentheses.
1663             parenthesesState.setJumpListToPriorParen(state.getJumpListToPriorParen());
1664
1665             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1666             // this expects that any backtracks back out of the parentheses will be in the
1667             // parenthesesState's m_backTrackJumps vector, and that if they need backtracking
1668             // they will have set an entry point on the parenthesesState's m_backtrackLabel.
1669             BacktrackDestination& parenthesesBacktrack = parenthesesState.getBacktrackDestination();
1670             BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
1671
1672             state.propagateBacktrackingFrom(this, parenthesesBacktrack);
1673             stateBacktrack.propagateBacktrackToLabel(parenthesesBacktrack);
1674
1675             state.setJumpListToPriorParen(parenthesesState.getJumpListToPriorParen());
1676
1677             m_expressionState.decrementParenNestingLevel();
1678         } else {
1679             Jump nonGreedySkipParentheses;
1680             Label nonGreedyTryParentheses;
1681             if (term.quantityType == QuantifierGreedy)
1682                 storeToFrame(index, parenthesesFrameLocation);
1683             else if (term.quantityType == QuantifierNonGreedy) {
1684                 storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1685                 nonGreedySkipParentheses = jump();
1686                 nonGreedyTryParentheses = label();
1687                 storeToFrame(index, parenthesesFrameLocation);
1688             }
1689
1690             // store the match start index
1691             if (term.capture()) {
1692                 int inputOffset = state.inputOffset() - preCheckedCount;
1693                 if (inputOffset) {
1694                     move(index, indexTemporary);
1695                     add32(Imm32(inputOffset), indexTemporary);
1696                     store32(indexTemporary, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
1697                 } else
1698                     store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
1699             }
1700
1701             ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getJumpListToPriorParen());
1702
1703             m_expressionState.incrementParenNestingLevel();
1704
1705             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1706
1707             // Save the parenthesesTail for backtracking from nested parens to this one.
1708             parenthesesState.setJumpListToPriorParen(&parenthesesTail->m_withinBacktrackJumps);
1709
1710             // generate the body of the parentheses
1711             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1712
1713             // For non-fixed counts, backtrack if we didn't match anything.
1714             if (term.quantityType != QuantifierFixedCount)
1715                 parenthesesTail->addAfterParenJump(branch32(Equal, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*)))));
1716
1717             // store the match end index
1718             if (term.capture()) {
1719                 int inputOffset = state.inputOffset();
1720                 if (inputOffset) {
1721                     move(index, indexTemporary);
1722                     add32(Imm32(state.inputOffset()), indexTemporary);
1723                     store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
1724                 } else
1725                     store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
1726             }
1727
1728             m_expressionState.decrementParenNestingLevel();
1729
1730             parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label());
1731
1732             state.setJumpListToPriorParen(&parenthesesTail->m_afterBacktrackJumps);
1733             
1734             parenthesesState.getBacktrackDestination().clear();
1735
1736             if (term.quantityType == QuantifierNonGreedy)
1737                 nonGreedySkipParentheses.link(this);
1738         }
1739     }
1740
1741     void generateParenthesesGreedyNoBacktrack(TermGenerationState& state)
1742     {
1743         PatternTerm& parenthesesTerm = state.term();
1744         PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
1745         ASSERT(parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern);
1746         ASSERT(parenthesesTerm.quantityCount != 1); // Handled by generateParenthesesSingle.
1747
1748         TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1749
1750         Label matchAgain(this);
1751
1752         storeToFrame(index, parenthesesTerm.frameLocation); // Save the current index to check for zero len matches later.
1753
1754         for (parenthesesState.resetAlternative(); parenthesesState.alternativeValid(); parenthesesState.nextAlternative()) {
1755
1756             PatternAlternative* alternative = parenthesesState.alternative();
1757             optimizeAlternative(alternative);
1758
1759             int countToCheck = alternative->m_minimumSize;
1760             if (countToCheck) {
1761                 parenthesesState.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
1762                 parenthesesState.checkedTotal += countToCheck;
1763             }
1764
1765             for (parenthesesState.resetTerm(); parenthesesState.termValid(); parenthesesState.nextTerm())
1766                 generateTerm(parenthesesState);
1767
1768             // If we get here, we matched! If the index advanced then try to match more since limit isn't supported yet.
1769             branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesTerm.frameLocation * sizeof(void*))), matchAgain);
1770
1771             // If we get here we matched, but we matched "" - cannot accept this alternative as is, so either backtrack,
1772             // or fall through to try the next alternative if no backtrack is available.
1773             parenthesesState.plantJumpToBacktrackIfExists(this);
1774
1775             parenthesesState.linkAlternativeBacktracks(this);
1776
1777             // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop.
1778
1779             if (countToCheck) {
1780                 sub32(Imm32(countToCheck), index);
1781                 parenthesesState.checkedTotal -= countToCheck;
1782             }
1783         }
1784
1785         // If the last alternative falls through to here, we have a failed match...
1786         // Which means that we match whatever we have matched up to this point (even if nothing).
1787     }
1788
1789     void generateParentheticalAssertion(TermGenerationState& state)
1790     {
1791         PatternTerm& term = state.term();
1792         PatternDisjunction* disjunction = term.parentheses.disjunction;
1793         ASSERT(term.quantityCount == 1);
1794         ASSERT(term.quantityType == QuantifierFixedCount);
1795
1796         unsigned parenthesesFrameLocation = term.frameLocation;
1797         unsigned alternativeFrameLocation = parenthesesFrameLocation + YarrStackSpaceForBackTrackInfoParentheticalAssertion;
1798
1799         int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;
1800
1801         if (term.invert()) {
1802             // Inverted case
1803             storeToFrame(index, parenthesesFrameLocation);
1804
1805             state.checkedTotal -= countCheckedAfterAssertion;
1806             if (countCheckedAfterAssertion)
1807                 sub32(Imm32(countCheckedAfterAssertion), index);
1808
1809             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1810             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1811             // Success! - which means - Fail!
1812             loadFromFrame(parenthesesFrameLocation, index);
1813             state.jumpToBacktrack(this);
1814
1815             // And fail means success.
1816             parenthesesState.linkAlternativeBacktracks(this);
1817
1818             loadFromFrame(parenthesesFrameLocation, index);
1819
1820             state.checkedTotal += countCheckedAfterAssertion;
1821         } else {
1822             // Normal case
1823             storeToFrame(index, parenthesesFrameLocation);
1824
1825             state.checkedTotal -= countCheckedAfterAssertion;
1826             if (countCheckedAfterAssertion)
1827                 sub32(Imm32(countCheckedAfterAssertion), index);
1828
1829             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1830             generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1831             // Success! - which means - Success!
1832             loadFromFrame(parenthesesFrameLocation, index);
1833             Jump success = jump();
1834
1835             parenthesesState.linkAlternativeBacktracks(this);
1836
1837             loadFromFrame(parenthesesFrameLocation, index);
1838             state.jumpToBacktrack(this);
1839
1840             success.link(this);
1841
1842             state.checkedTotal += countCheckedAfterAssertion;
1843         }
1844     }
1845
1846     void generateTerm(TermGenerationState& state)
1847     {
1848         PatternTerm& term = state.term();
1849
1850         switch (term.type) {
1851         case PatternTerm::TypeAssertionBOL:
1852             generateAssertionBOL(state);
1853             break;
1854
1855         case PatternTerm::TypeAssertionEOL:
1856             generateAssertionEOL(state);
1857             break;
1858
1859         case PatternTerm::TypeAssertionWordBoundary:
1860             generateAssertionWordBoundary(state);
1861             break;
1862
1863         case PatternTerm::TypePatternCharacter:
1864             switch (term.quantityType) {
1865             case QuantifierFixedCount:
1866                 if (term.quantityCount == 1) {
1867                     if (state.isSinglePatternCharacterLookaheadTerm() && (state.lookaheadTerm().inputPosition == (term.inputPosition + 1))) {
1868                         generatePatternCharacterPair(state);
1869                         state.nextTerm();
1870                     } else
1871                         generatePatternCharacterSingle(state);
1872                 } else
1873                     generatePatternCharacterFixed(state);
1874                 break;
1875             case QuantifierGreedy:
1876                 generatePatternCharacterGreedy(state);
1877                 break;
1878             case QuantifierNonGreedy:
1879                 generatePatternCharacterNonGreedy(state);
1880                 break;
1881             }
1882             break;
1883
1884         case PatternTerm::TypeCharacterClass:
1885             switch (term.quantityType) {
1886             case QuantifierFixedCount:
1887                 if (term.quantityCount == 1)
1888                     generateCharacterClassSingle(state);
1889                 else
1890                     generateCharacterClassFixed(state);
1891                 break;
1892             case QuantifierGreedy:
1893                 generateCharacterClassGreedy(state);
1894                 break;
1895             case QuantifierNonGreedy:
1896                 generateCharacterClassNonGreedy(state);
1897                 break;
1898             }
1899             break;
1900
1901         case PatternTerm::TypeBackReference:
1902             m_shouldFallBack = true;
1903             break;
1904
1905         case PatternTerm::TypeForwardReference:
1906             break;
1907
1908         case PatternTerm::TypeParenthesesSubpattern:
1909             if (term.quantityCount == 1 && !term.parentheses.isCopy)
1910                 generateParenthesesSingle(state);
1911             else if (term.parentheses.isTerminal)
1912                 generateParenthesesGreedyNoBacktrack(state);
1913             else
1914                 m_shouldFallBack = true;
1915             break;
1916
1917         case PatternTerm::TypeParentheticalAssertion:
1918             generateParentheticalAssertion(state);
1919             break;
1920         }
1921     }
1922
1923     void generateDisjunction(PatternDisjunction* disjunction)
1924     {
1925         TermGenerationState state(disjunction, 0);
1926         state.resetAlternative();
1927
1928         // check availability for the next alternative
1929         int countCheckedForCurrentAlternative = 0;
1930         int countToCheckForFirstAlternative = 0;
1931         bool hasShorterAlternatives = false;
1932         bool setRepeatAlternativeLabels = false;
1933         JumpList notEnoughInputForPreviousAlternative;
1934         Label firstAlternative;
1935         Label firstAlternativeInputChecked;
1936
1937         // The label 'firstAlternative' is used to plant a check to see if there is 
1938         // sufficient input available to run the first repeating alternative.
1939         // The label 'firstAlternativeInputChecked' will jump directly to matching 
1940         // the first repeating alternative having skipped this check.
1941
1942         if (state.alternativeValid()) {
1943             PatternAlternative* alternative = state.alternative();
1944             if (!alternative->onceThrough()) {
1945                 firstAlternative = Label(this);
1946                 setRepeatAlternativeLabels = true;
1947             }
1948             countToCheckForFirstAlternative = alternative->m_minimumSize;
1949             state.checkedTotal += countToCheckForFirstAlternative;
1950             if (countToCheckForFirstAlternative)
1951                 notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
1952             countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
1953         }
1954
1955         if (setRepeatAlternativeLabels)
1956             firstAlternativeInputChecked = Label(this);
1957
1958         while (state.alternativeValid()) {
1959             PatternAlternative* alternative = state.alternative();
1960             optimizeAlternative(alternative);
1961
1962             // Track whether any alternatives are shorter than the first one.
1963             if (!alternative->onceThrough())
1964                 hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative);
1965
1966             for (state.resetTerm(); state.termValid(); state.nextTerm())
1967                 generateTerm(state);
1968
1969             // If we get here, the alternative matched.
1970             if (m_pattern.m_body->m_callFrameSize)
1971                 addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1972
1973             ASSERT(index != returnRegister);
1974             if (m_pattern.m_body->m_hasFixedSize) {
1975                 move(index, returnRegister);
1976                 if (alternative->m_minimumSize)
1977                     sub32(Imm32(alternative->m_minimumSize), returnRegister);
1978
1979                 store32(returnRegister, output);
1980             } else
1981                 load32(Address(output), returnRegister);
1982
1983             store32(index, Address(output, 4));
1984
1985             generateReturn();
1986
1987             state.nextAlternative();
1988             if (alternative->onceThrough() && state.alternativeValid())
1989                 state.clearBacktrack();
1990
1991             // if there are any more alternatives, plant the check for input before looping.
1992             if (state.alternativeValid()) {
1993                 state.setJumpListToPriorParen(0);
1994                 PatternAlternative* nextAlternative = state.alternative();
1995                 if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
1996                     // We have handled non-repeating alternatives, jump to next iteration 
1997                     // and loop over repeating alternatives.
1998                     state.jumpToBacktrack(this);
1999
2000                     countToCheckForFirstAlternative = nextAlternative->m_minimumSize;
2001
2002                     // If we get here, there the last input checked failed.
2003                     notEnoughInputForPreviousAlternative.link(this);
2004
2005                     state.linkAlternativeBacktracks(this);
2006
2007                     // Back up to start the looping alternatives.
2008                     if (countCheckedForCurrentAlternative)
2009                         sub32(Imm32(countCheckedForCurrentAlternative), index);
2010
2011                     firstAlternative = Label(this);
2012
2013                     state.checkedTotal = countToCheckForFirstAlternative;
2014                     if (countToCheckForFirstAlternative)
2015                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
2016
2017                     countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
2018
2019                     firstAlternativeInputChecked = Label(this);
2020
2021                     setRepeatAlternativeLabels = true;
2022                 } else {
2023                     int countToCheckForNextAlternative = nextAlternative->m_minimumSize;
2024
2025                     if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one.
2026                         // If we get here, then the last input checked failed.
2027                         notEnoughInputForPreviousAlternative.link(this);
2028
2029                         // Check if sufficent input available to run the next alternative 
2030                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
2031                         // We are now in the correct state to enter the next alternative; this add is only required
2032                         // to mirror and revert operation of the sub32, just below.
2033                         add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
2034
2035                         // If we get here, then the last input checked passed.
2036                         state.linkAlternativeBacktracks(this);
2037
2038                         // No need to check if we can run the next alternative, since it is shorter -
2039                         // just update index.
2040                         sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
2041                     } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one.
2042                         // If we get here, then the last input checked failed.
2043                         // If there is insufficient input to run the current alternative, and the next alternative is longer,
2044                         // then there is definitely not enough input to run it - don't even check. Just adjust index, as if
2045                         // we had checked.
2046                         notEnoughInputForPreviousAlternative.link(this);
2047                         add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index);
2048                         notEnoughInputForPreviousAlternative.append(jump());
2049
2050                         // The next alternative is longer than the current one; check the difference.
2051                         state.linkAlternativeBacktracks(this);
2052
2053                         notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
2054                     } else { // CASE 3: Both alternatives are the same length.
2055                         ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative);
2056
2057                         // If the next alterative is the same length as this one, then no need to check the input -
2058                         // if there was sufficent input to run the current alternative then there is sufficient
2059                         // input to run the next one; if not, there isn't.
2060                         state.linkAlternativeBacktracks(this);
2061                     }
2062                     state.checkedTotal -= countCheckedForCurrentAlternative;
2063                     countCheckedForCurrentAlternative = countToCheckForNextAlternative;
2064                     state.checkedTotal += countCheckedForCurrentAlternative;
2065                 }
2066             }
2067         }
2068
2069         // If we get here, all Alternatives failed...
2070
2071         state.checkedTotal -= countCheckedForCurrentAlternative;
2072
2073         if (!setRepeatAlternativeLabels) {
2074             // If there are no alternatives that need repeating (all are marked 'onceThrough') then just link
2075             // the match failures to this point, and fall through to the return below.
2076             state.linkAlternativeBacktracks(this, true);
2077
2078             notEnoughInputForPreviousAlternative.link(this);
2079         } else {
2080             // How much more input need there be to be able to retry from the first alternative?
2081             // examples:
2082             //   /yarr_jit/ or /wrec|pcre/
2083             //     In these examples we need check for one more input before looping.
2084             //   /yarr_jit|pcre/
2085             //     In this case we need check for 5 more input to loop (+4 to allow for the first alterative
2086             //     being four longer than the last alternative checked, and another +1 to effectively move
2087             //     the start position along by one).
2088             //   /yarr|rules/ or /wrec|notsomuch/
2089             //     In these examples, provided that there was sufficient input to have just been matching for
2090             //     the second alternative we can loop without checking for available input (since the second
2091             //     alternative is longer than the first).  In the latter example we need to decrement index
2092             //     (by 4) so the start position is only progressed by 1 from the last iteration.
2093             int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1;
2094
2095             // First, deal with the cases where there was sufficient input to try the last alternative.
2096             if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below.
2097                 state.linkAlternativeBacktracks(this, true);
2098             else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop!
2099                 state.linkAlternativeBacktracksTo(this, firstAlternativeInputChecked, true);
2100             else { // no need to check the input, but we do have some bookkeeping to do first.
2101                 state.linkAlternativeBacktracks(this, true);
2102
2103                 // Where necessary update our preserved start position.
2104                 if (!m_pattern.m_body->m_hasFixedSize) {
2105                     move(index, regT0);
2106                     sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
2107                     store32(regT0, Address(output));
2108                 }
2109
2110                 // Update index if necessary, and loop (without checking).
2111                 if (incrementForNextIter)
2112                     add32(Imm32(incrementForNextIter), index);
2113                 jump().linkTo(firstAlternativeInputChecked, this);
2114             }
2115
2116             notEnoughInputForPreviousAlternative.link(this);
2117             // Update our idea of the start position, if we're tracking this.
2118             if (!m_pattern.m_body->m_hasFixedSize) {
2119                 if (countCheckedForCurrentAlternative - 1) {
2120                     move(index, regT0);
2121                     sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
2122                     store32(regT0, Address(output));
2123                 } else
2124                     store32(index, Address(output));
2125             }
2126
2127             // Check if there is sufficent input to run the first alternative again.
2128             jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this);
2129             // No - insufficent input to run the first alteranative, are there any other alternatives we
2130             // might need to check?  If so, the last check will have left the index incremented by
2131             // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative
2132             // LESS input is available, to have the effect of just progressing the start position by 1
2133             // from the last iteration.  If this check passes we can just jump up to the check associated
2134             // with the first alternative in the loop.  This is a bit sad, since we'll end up trying the
2135             // first alternative again, and this check will fail (otherwise the check planted just above
2136             // here would have passed).  This is a bit sad, however it saves trying to do something more
2137             // complex here in compilation, and in the common case we should end up coallescing the checks.
2138             //
2139             // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least
2140             // of the minimum-alternative-lengths.  E.g. if I have two alternatives of length 200 and 150,
2141             // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there
2142             // is sufficient input to run either alternative (constantly failing).  If there had been only
2143             // one alternative, or if the shorter alternative had come first, we would have terminated
2144             // immediately. :-/
2145             if (hasShorterAlternatives)
2146                 jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this);
2147             // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true,
2148             // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ... 
2149             // but since we're about to return a failure this doesn't really matter!)
2150         }
2151
2152         if (m_pattern.m_body->m_callFrameSize)
2153             addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
2154
2155         move(TrustedImm32(-1), returnRegister);
2156
2157         generateReturn();
2158
2159         m_expressionState.emitParenthesesTail(this);
2160         m_expressionState.emitIndirectJumpTable(this);
2161         m_expressionState.linkToNextIteration(this);
2162     }
2163
2164     void generateEnter()
2165     {
2166 #if CPU(X86_64)
2167         push(X86Registers::ebp);
2168         move(stackPointerRegister, X86Registers::ebp);
2169         push(X86Registers::ebx);
2170 #elif CPU(X86)
2171         push(X86Registers::ebp);
2172         move(stackPointerRegister, X86Registers::ebp);
2173         // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
2174         push(X86Registers::ebx);
2175         push(X86Registers::edi);
2176         push(X86Registers::esi);
2177         // load output into edi (2 = saved ebp + return address).
2178     #if COMPILER(MSVC)
2179         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
2180         loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
2181         loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
2182         loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
2183     #else
2184         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
2185     #endif
2186 #elif CPU(ARM)
2187         push(ARMRegisters::r4);
2188         push(ARMRegisters::r5);
2189         push(ARMRegisters::r6);
2190 #if CPU(ARM_TRADITIONAL)
2191         push(ARMRegisters::r8); // scratch register
2192 #endif
2193         move(ARMRegisters::r3, output);
2194 #elif CPU(SH4)
2195         push(SH4Registers::r11);
2196         push(SH4Registers::r13);
2197 #elif CPU(MIPS)
2198         // Do nothing.
2199 #endif
2200     }
2201
2202     void generateReturn()
2203     {
2204 #if CPU(X86_64)
2205         pop(X86Registers::ebx);
2206         pop(X86Registers::ebp);
2207 #elif CPU(X86)
2208         pop(X86Registers::esi);
2209         pop(X86Registers::edi);
2210         pop(X86Registers::ebx);
2211         pop(X86Registers::ebp);
2212 #elif CPU(ARM)
2213 #if CPU(ARM_TRADITIONAL)
2214         pop(ARMRegisters::r8); // scratch register
2215 #endif
2216         pop(ARMRegisters::r6);
2217         pop(ARMRegisters::r5);
2218         pop(ARMRegisters::r4);
2219 #elif CPU(SH4)
2220         pop(SH4Registers::r13);
2221         pop(SH4Registers::r11);
2222 #elif CPU(MIPS)
2223         // Do nothing
2224 #endif
2225         ret();
2226     }
2227
2228 public:
2229     YarrGenerator(YarrPattern& pattern)
2230         : m_pattern(pattern)
2231         , m_shouldFallBack(false)
2232     {
2233     }
2234
2235     void generate()
2236     {
2237         generateEnter();
2238
2239         if (!m_pattern.m_body->m_hasFixedSize)
2240             store32(index, Address(output));
2241
2242         if (m_pattern.m_body->m_callFrameSize)
2243             subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
2244
2245         generateDisjunction(m_pattern.m_body);
2246     }
2247
2248     void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject)
2249     {
2250         generate();
2251
2252         LinkBuffer patchBuffer(this, globalData->regexAllocator.poolForSize(size()), 0);
2253
2254         for (unsigned i = 0; i < m_expressionState.m_backtrackRecords.size(); ++i)
2255             patchBuffer.patch(m_expressionState.m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_expressionState.m_backtrackRecords[i].backtrackLocation));
2256
2257         jitObject.set(patchBuffer.finalizeCode());
2258         jitObject.setFallBack(m_shouldFallBack);
2259     }
2260
2261 private:
2262     YarrPattern& m_pattern;
2263     bool m_shouldFallBack;
2264     GenerationState m_expressionState;
2265 };
2266
2267 void jitCompile(YarrPattern& pattern, JSGlobalData* globalData, YarrCodeBlock& jitObject)
2268 {
2269     YarrGenerator(pattern).compile(globalData, jitObject);
2270 }
2271
2272 int execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output)
2273 {
2274     return jitObject.execute(input, start, length, output);
2275 }
2276
2277 }}
2278
2279 #endif