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