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