YARR: Multi-character read optimization for 8bit strings
[WebKit-https.git] / Source / JavaScriptCore / yarr / YarrJIT.cpp
1 /*
2  * Copyright (C) 2009 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "YarrJIT.h"
28
29 #include "ASCIICType.h"
30 #include "LinkBuffer.h"
31 #include "Yarr.h"
32
33 #if ENABLE(YARR_JIT)
34
35 using namespace WTF;
36
37 namespace JSC { namespace Yarr {
38
39 class YarrGenerator : private MacroAssembler {
40     friend void jitCompile(JSGlobalData*, YarrCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);
41
42 #if CPU(ARM)
43     static const RegisterID input = ARMRegisters::r0;
44     static const RegisterID index = ARMRegisters::r1;
45     static const RegisterID length = ARMRegisters::r2;
46     static const RegisterID output = ARMRegisters::r4;
47
48     static const RegisterID regT0 = ARMRegisters::r5;
49     static const RegisterID regT1 = ARMRegisters::r6;
50
51     static const RegisterID returnRegister = ARMRegisters::r0;
52 #elif CPU(MIPS)
53     static const RegisterID input = MIPSRegisters::a0;
54     static const RegisterID index = MIPSRegisters::a1;
55     static const RegisterID length = MIPSRegisters::a2;
56     static const RegisterID output = MIPSRegisters::a3;
57
58     static const RegisterID regT0 = MIPSRegisters::t4;
59     static const RegisterID regT1 = MIPSRegisters::t5;
60
61     static const RegisterID returnRegister = MIPSRegisters::v0;
62 #elif CPU(SH4)
63     static const RegisterID input = SH4Registers::r4;
64     static const RegisterID index = SH4Registers::r5;
65     static const RegisterID length = SH4Registers::r6;
66     static const RegisterID output = SH4Registers::r7;
67
68     static const RegisterID regT0 = SH4Registers::r0;
69     static const RegisterID regT1 = SH4Registers::r1;
70
71     static const RegisterID returnRegister = SH4Registers::r0;
72 #elif CPU(X86)
73     static const RegisterID input = X86Registers::eax;
74     static const RegisterID index = X86Registers::edx;
75     static const RegisterID length = X86Registers::ecx;
76     static const RegisterID output = X86Registers::edi;
77
78     static const RegisterID regT0 = X86Registers::ebx;
79     static const RegisterID regT1 = X86Registers::esi;
80
81     static const RegisterID returnRegister = X86Registers::eax;
82 #elif CPU(X86_64)
83     static const RegisterID input = X86Registers::edi;
84     static const RegisterID index = X86Registers::esi;
85     static const RegisterID length = X86Registers::edx;
86     static const RegisterID output = X86Registers::ecx;
87
88     static const RegisterID regT0 = X86Registers::eax;
89     static const RegisterID regT1 = X86Registers::ebx;
90
91     static const RegisterID returnRegister = X86Registers::eax;
92 #endif
93
94     void optimizeAlternative(PatternAlternative* alternative)
95     {
96         if (!alternative->m_terms.size())
97             return;
98
99         for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {
100             PatternTerm& term = alternative->m_terms[i];
101             PatternTerm& nextTerm = alternative->m_terms[i + 1];
102
103             if ((term.type == PatternTerm::TypeCharacterClass)
104                 && (term.quantityType == QuantifierFixedCount)
105                 && (nextTerm.type == PatternTerm::TypePatternCharacter)
106                 && (nextTerm.quantityType == QuantifierFixedCount)) {
107                 PatternTerm termCopy = term;
108                 alternative->m_terms[i] = nextTerm;
109                 alternative->m_terms[i + 1] = termCopy;
110             }
111         }
112     }
113
114     void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
115     {
116         do {
117             // pick which range we're going to generate
118             int which = count >> 1;
119             char lo = ranges[which].begin;
120             char hi = ranges[which].end;
121
122             // check if there are any ranges or matches below lo.  If not, just jl to failure -
123             // if there is anything else to check, check that first, if it falls through jmp to failure.
124             if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
125                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
126
127                 // generate code for all ranges before this one
128                 if (which)
129                     matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
130
131                 while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
132                     matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
133                     ++*matchIndex;
134                 }
135                 failures.append(jump());
136
137                 loOrAbove.link(this);
138             } else if (which) {
139                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
140
141                 matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
142                 failures.append(jump());
143
144                 loOrAbove.link(this);
145             } else
146                 failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));
147
148             while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
149                 ++*matchIndex;
150
151             matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
152             // fall through to here, the value is above hi.
153
154             // shuffle along & loop around if there are any more matches to handle.
155             unsigned next = which + 1;
156             ranges += next;
157             count -= next;
158         } while (count);
159     }
160
161     void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
162     {
163         if (charClass->m_table) {
164             ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table));
165             matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry));
166             return;
167         }
168         Jump unicodeFail;
169         if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
170             Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f));
171
172             if (charClass->m_matchesUnicode.size()) {
173                 for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {
174                     UChar ch = charClass->m_matchesUnicode[i];
175                     matchDest.append(branch32(Equal, character, Imm32(ch)));
176                 }
177             }
178
179             if (charClass->m_rangesUnicode.size()) {
180                 for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {
181                     UChar lo = charClass->m_rangesUnicode[i].begin;
182                     UChar hi = charClass->m_rangesUnicode[i].end;
183
184                     Jump below = branch32(LessThan, character, Imm32(lo));
185                     matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
186                     below.link(this);
187                 }
188             }
189
190             unicodeFail = jump();
191             isAscii.link(this);
192         }
193
194         if (charClass->m_ranges.size()) {
195             unsigned matchIndex = 0;
196             JumpList failures;
197             matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
198             while (matchIndex < charClass->m_matches.size())
199                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
200
201             failures.link(this);
202         } else if (charClass->m_matches.size()) {
203             // optimization: gather 'a','A' etc back together, can mask & test once.
204             Vector<char> matchesAZaz;
205
206             for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {
207                 char ch = charClass->m_matches[i];
208                 if (m_pattern.m_ignoreCase) {
209                     if (isASCIILower(ch)) {
210                         matchesAZaz.append(ch);
211                         continue;
212                     }
213                     if (isASCIIUpper(ch))
214                         continue;
215                 }
216                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
217             }
218
219             if (unsigned countAZaz = matchesAZaz.size()) {
220                 or32(TrustedImm32(32), character);
221                 for (unsigned i = 0; i < countAZaz; ++i)
222                     matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));
223             }
224         }
225
226         if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())
227             unicodeFail.link(this);
228     }
229
230     // Jumps if input not available; will have (incorrectly) incremented already!
231     Jump jumpIfNoAvailableInput(unsigned countToCheck = 0)
232     {
233         if (countToCheck)
234             add32(Imm32(countToCheck), index);
235         return branch32(Above, index, length);
236     }
237
238     Jump jumpIfAvailableInput(unsigned countToCheck)
239     {
240         add32(Imm32(countToCheck), index);
241         return branch32(BelowOrEqual, index, length);
242     }
243
244     Jump checkInput()
245     {
246         return branch32(BelowOrEqual, index, length);
247     }
248
249     Jump atEndOfInput()
250     {
251         return branch32(Equal, index, length);
252     }
253
254     Jump notAtEndOfInput()
255     {
256         return branch32(NotEqual, index, length);
257     }
258
259     Jump jumpIfCharNotEquals(UChar ch, int inputPosition, RegisterID character)
260     {
261         readCharacter(inputPosition, character);
262
263         // For case-insesitive compares, non-ascii characters that have different
264         // upper & lower case representations are converted to a character class.
265         ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
266         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
267             or32(TrustedImm32(32), character);
268             ch = Unicode::toLower(ch);
269         }
270
271         return branch32(NotEqual, character, Imm32(ch));
272     }
273
274     void readCharacter(int inputPosition, RegisterID reg)
275     {
276         if (m_charSize == Char8)
277             load8(BaseIndex(input, index, TimesOne, inputPosition * sizeof(char)), reg);
278         else
279             load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
280     }
281
282     void storeToFrame(RegisterID reg, unsigned frameLocation)
283     {
284         poke(reg, frameLocation);
285     }
286
287     void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
288     {
289         poke(imm, frameLocation);
290     }
291
292     DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
293     {
294         return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
295     }
296
297     void loadFromFrame(unsigned frameLocation, RegisterID reg)
298     {
299         peek(reg, frameLocation);
300     }
301
302     void loadFromFrameAndJump(unsigned frameLocation)
303     {
304         jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
305     }
306
307     enum YarrOpCode {
308         // These nodes wrap body alternatives - those in the main disjunction,
309         // rather than subpatterns or assertions. These are chained together in
310         // a doubly linked list, with a 'begin' node for the first alternative,
311         // a 'next' node for each subsequent alternative, and an 'end' node at
312         // the end. In the case of repeating alternatives, the 'end' node also
313         // has a reference back to 'begin'.
314         OpBodyAlternativeBegin,
315         OpBodyAlternativeNext,
316         OpBodyAlternativeEnd,
317         // Similar to the body alternatives, but used for subpatterns with two
318         // or more alternatives.
319         OpNestedAlternativeBegin,
320         OpNestedAlternativeNext,
321         OpNestedAlternativeEnd,
322         // Used for alternatives in subpatterns where there is only a single
323         // alternative (backtrackingis easier in these cases), or for alternatives
324         // which never need to be backtracked (those in parenthetical assertions,
325         // terminal subpatterns).
326         OpSimpleNestedAlternativeBegin,
327         OpSimpleNestedAlternativeNext,
328         OpSimpleNestedAlternativeEnd,
329         // Used to wrap 'Once' subpattern matches (quantityCount == 1).
330         OpParenthesesSubpatternOnceBegin,
331         OpParenthesesSubpatternOnceEnd,
332         // Used to wrap 'Terminal' subpattern matches (at the end of the regexp).
333         OpParenthesesSubpatternTerminalBegin,
334         OpParenthesesSubpatternTerminalEnd,
335         // Used to wrap parenthetical assertions.
336         OpParentheticalAssertionBegin,
337         OpParentheticalAssertionEnd,
338         // Wraps all simple terms (pattern characters, character classes).
339         OpTerm,
340         // Where an expression contains only 'once through' body alternatives
341         // and no repeating ones, this op is used to return match failure.
342         OpMatchFailed
343     };
344
345     // This structure is used to hold the compiled opcode information,
346     // including reference back to the original PatternTerm/PatternAlternatives,
347     // and JIT compilation data structures.
348     struct YarrOp {
349         explicit YarrOp(PatternTerm* term)
350             : m_op(OpTerm)
351             , m_term(term)
352             , m_isDeadCode(false)
353         {
354         }
355
356         explicit YarrOp(YarrOpCode op)
357             : m_op(op)
358             , m_isDeadCode(false)
359         {
360         }
361
362         // The operation, as a YarrOpCode, and also a reference to the PatternTerm.
363         YarrOpCode m_op;
364         PatternTerm* m_term;
365
366         // For alternatives, this holds the PatternAlternative and doubly linked
367         // references to this alternative's siblings. In the case of the
368         // OpBodyAlternativeEnd node at the end of a section of repeating nodes,
369         // m_nextOp will reference the OpBodyAlternativeBegin node of the first
370         // repeating alternative.
371         PatternAlternative* m_alternative;
372         size_t m_previousOp;
373         size_t m_nextOp;
374
375         // Used to record a set of Jumps out of the generated code, typically
376         // used for jumps out to backtracking code, and a single reentry back
377         // into the code for a node (likely where a backtrack will trigger
378         // rematching).
379         Label m_reentry;
380         JumpList m_jumps;
381
382         // This flag is used to null out the second pattern character, when
383         // two are fused to match a pair together.
384         bool m_isDeadCode;
385
386         // Currently used in the case of some of the more complex management of
387         // 'm_checked', to cache the offset used in this alternative, to avoid
388         // recalculating it.
389         int m_checkAdjust;
390
391         // Used by OpNestedAlternativeNext/End to hold the pointer to the
392         // value that will be pushed into the pattern's frame to return to,
393         // upon backtracking back into the disjunction.
394         DataLabelPtr m_returnAddress;
395     };
396
397     // BacktrackingState
398     // This class encapsulates information about the state of code generation
399     // whilst generating the code for backtracking, when a term fails to match.
400     // Upon entry to code generation of the backtracking code for a given node,
401     // the Backtracking state will hold references to all control flow sources
402     // that are outputs in need of further backtracking from the prior node
403     // generated (which is the subsequent operation in the regular expression,
404     // and in the m_ops Vector, since we generated backtracking backwards).
405     // These references to control flow take the form of:
406     //  - A jump list of jumps, to be linked to code that will backtrack them
407     //    further.
408     //  - A set of DataLabelPtr values, to be populated with values to be
409     //    treated effectively as return addresses backtracking into complex
410     //    subpatterns.
411     //  - A flag indicating that the current sequence of generated code up to
412     //    this point requires backtracking.
413     class BacktrackingState {
414     public:
415         BacktrackingState()
416             : m_pendingFallthrough(false)
417         {
418         }
419
420         // Add a jump or jumps, a return address, or set the flag indicating
421         // that the current 'fallthrough' control flow requires backtracking.
422         void append(const Jump& jump)
423         {
424             m_laterFailures.append(jump);
425         }
426         void append(JumpList& jumpList)
427         {
428             m_laterFailures.append(jumpList);
429         }
430         void append(const DataLabelPtr& returnAddress)
431         {
432             m_pendingReturns.append(returnAddress);
433         }
434         void fallthrough()
435         {
436             ASSERT(!m_pendingFallthrough);
437             m_pendingFallthrough = true;
438         }
439
440         // These methods clear the backtracking state, either linking to the
441         // current location, a provided label, or copying the backtracking out
442         // to a JumpList. All actions may require code generation to take place,
443         // and as such are passed a pointer to the assembler.
444         void link(MacroAssembler* assembler)
445         {
446             if (m_pendingReturns.size()) {
447                 Label here(assembler);
448                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
449                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));
450                 m_pendingReturns.clear();
451             }
452             m_laterFailures.link(assembler);
453             m_laterFailures.clear();
454             m_pendingFallthrough = false;
455         }
456         void linkTo(Label label, MacroAssembler* assembler)
457         {
458             if (m_pendingReturns.size()) {
459                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
460                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], label));
461                 m_pendingReturns.clear();
462             }
463             if (m_pendingFallthrough)
464                 assembler->jump(label);
465             m_laterFailures.linkTo(label, assembler);
466             m_laterFailures.clear();
467             m_pendingFallthrough = false;
468         }
469         void takeBacktracksToJumpList(JumpList& jumpList, MacroAssembler* assembler)
470         {
471             if (m_pendingReturns.size()) {
472                 Label here(assembler);
473                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
474                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));
475                 m_pendingReturns.clear();
476                 m_pendingFallthrough = true;
477             }
478             if (m_pendingFallthrough)
479                 jumpList.append(assembler->jump());
480             jumpList.append(m_laterFailures);
481             m_laterFailures.clear();
482             m_pendingFallthrough = false;
483         }
484
485         bool isEmpty()
486         {
487             return m_laterFailures.empty() && m_pendingReturns.isEmpty() && !m_pendingFallthrough;
488         }
489
490         // Called at the end of code generation to link all return addresses.
491         void linkDataLabels(LinkBuffer& linkBuffer)
492         {
493             ASSERT(isEmpty());
494             for (unsigned i = 0; i < m_backtrackRecords.size(); ++i)
495                 linkBuffer.patch(m_backtrackRecords[i].m_dataLabel, linkBuffer.locationOf(m_backtrackRecords[i].m_backtrackLocation));
496         }
497
498     private:
499         struct ReturnAddressRecord {
500             ReturnAddressRecord(DataLabelPtr dataLabel, Label backtrackLocation)
501                 : m_dataLabel(dataLabel)
502                 , m_backtrackLocation(backtrackLocation)
503             {
504             }
505
506             DataLabelPtr m_dataLabel;
507             Label m_backtrackLocation;
508         };
509
510         JumpList m_laterFailures;
511         bool m_pendingFallthrough;
512         Vector<DataLabelPtr, 4> m_pendingReturns;
513         Vector<ReturnAddressRecord, 4> m_backtrackRecords;
514     };
515
516     // Generation methods:
517     // ===================
518
519     // This method provides a default implementation of backtracking common
520     // to many terms; terms commonly jump out of the forwards  matching path
521     // on any failed conditions, and add these jumps to the m_jumps list. If
522     // no special handling is required we can often just backtrack to m_jumps.
523     void backtrackTermDefault(size_t opIndex)
524     {
525         YarrOp& op = m_ops[opIndex];
526         m_backtrackingState.append(op.m_jumps);
527     }
528
529     void generateAssertionBOL(size_t opIndex)
530     {
531         YarrOp& op = m_ops[opIndex];
532         PatternTerm* term = op.m_term;
533
534         if (m_pattern.m_multiline) {
535             const RegisterID character = regT0;
536
537             JumpList matchDest;
538             if (!term->inputPosition)
539                 matchDest.append(branch32(Equal, index, Imm32(m_checked)));
540
541             readCharacter((term->inputPosition - m_checked) - 1, character);
542             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
543             op.m_jumps.append(jump());
544
545             matchDest.link(this);
546         } else {
547             // Erk, really should poison out these alternatives early. :-/
548             if (term->inputPosition)
549                 op.m_jumps.append(jump());
550             else
551                 op.m_jumps.append(branch32(NotEqual, index, Imm32(m_checked)));
552         }
553     }
554     void backtrackAssertionBOL(size_t opIndex)
555     {
556         backtrackTermDefault(opIndex);
557     }
558
559     void generateAssertionEOL(size_t opIndex)
560     {
561         YarrOp& op = m_ops[opIndex];
562         PatternTerm* term = op.m_term;
563
564         if (m_pattern.m_multiline) {
565             const RegisterID character = regT0;
566
567             JumpList matchDest;
568             if (term->inputPosition == m_checked)
569                 matchDest.append(atEndOfInput());
570
571             readCharacter(term->inputPosition - m_checked, character);
572             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
573             op.m_jumps.append(jump());
574
575             matchDest.link(this);
576         } else {
577             if (term->inputPosition == m_checked)
578                 op.m_jumps.append(notAtEndOfInput());
579             // Erk, really should poison out these alternatives early. :-/
580             else
581                 op.m_jumps.append(jump());
582         }
583     }
584     void backtrackAssertionEOL(size_t opIndex)
585     {
586         backtrackTermDefault(opIndex);
587     }
588
589     // Also falls though on nextIsNotWordChar.
590     void matchAssertionWordchar(size_t opIndex, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
591     {
592         YarrOp& op = m_ops[opIndex];
593         PatternTerm* term = op.m_term;
594
595         const RegisterID character = regT0;
596
597         if (term->inputPosition == m_checked)
598             nextIsNotWordChar.append(atEndOfInput());
599
600         readCharacter((term->inputPosition - m_checked), character);
601         matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
602     }
603
604     void generateAssertionWordBoundary(size_t opIndex)
605     {
606         YarrOp& op = m_ops[opIndex];
607         PatternTerm* term = op.m_term;
608
609         const RegisterID character = regT0;
610
611         Jump atBegin;
612         JumpList matchDest;
613         if (!term->inputPosition)
614             atBegin = branch32(Equal, index, Imm32(m_checked));
615         readCharacter((term->inputPosition - m_checked) - 1, character);
616         matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
617         if (!term->inputPosition)
618             atBegin.link(this);
619
620         // We fall through to here if the last character was not a wordchar.
621         JumpList nonWordCharThenWordChar;
622         JumpList nonWordCharThenNonWordChar;
623         if (term->invert()) {
624             matchAssertionWordchar(opIndex, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
625             nonWordCharThenWordChar.append(jump());
626         } else {
627             matchAssertionWordchar(opIndex, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
628             nonWordCharThenNonWordChar.append(jump());
629         }
630         op.m_jumps.append(nonWordCharThenNonWordChar);
631
632         // We jump here if the last character was a wordchar.
633         matchDest.link(this);
634         JumpList wordCharThenWordChar;
635         JumpList wordCharThenNonWordChar;
636         if (term->invert()) {
637             matchAssertionWordchar(opIndex, wordCharThenNonWordChar, wordCharThenWordChar);
638             wordCharThenWordChar.append(jump());
639         } else {
640             matchAssertionWordchar(opIndex, wordCharThenWordChar, wordCharThenNonWordChar);
641             // This can fall-though!
642         }
643
644         op.m_jumps.append(wordCharThenWordChar);
645
646         nonWordCharThenWordChar.link(this);
647         wordCharThenNonWordChar.link(this);
648     }
649     void backtrackAssertionWordBoundary(size_t opIndex)
650     {
651         backtrackTermDefault(opIndex);
652     }
653
654     void generatePatternCharacterOnce(size_t opIndex)
655     {
656         YarrOp& op = m_ops[opIndex];
657
658         if (op.m_isDeadCode)
659             return;
660         
661         // m_ops always ends with a OpBodyAlternativeEnd or OpMatchFailed
662         // node, so there must always be at least one more node.
663         ASSERT(opIndex + 1 < m_ops.size());
664         YarrOp* nextOp = &m_ops[opIndex + 1];
665
666         PatternTerm* term = op.m_term;
667         UChar ch = term->patternCharacter;
668
669         if ((ch > 0xff) && (m_charSize == Char8)) {
670             // Have a 16 bit pattern character and an 8 bit string - short circuit
671             op.m_jumps.append(jump());
672             return;
673         }
674
675         const RegisterID character = regT0;
676         int maxCharactersAtOnce = m_charSize == Char8 ? 4 : 2;
677         unsigned ignoreCaseMask = 0;
678         unsigned currentCharacterMask = m_charSize == Char8 ? 0xff : 0xffff;
679         int allCharacters = ch;
680         int numberCharacters;
681         int startTermPosition = term->inputPosition;
682
683         // For case-insesitive compares, non-ascii characters that have different
684         // upper & lower case representations are converted to a character class.
685         ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
686
687         if ((m_pattern.m_ignoreCase) && (isASCIIAlpha(ch)))
688             ignoreCaseMask |= 32;
689
690         for (numberCharacters = 1; numberCharacters < maxCharactersAtOnce && nextOp->m_op == OpTerm; ++numberCharacters, nextOp = &m_ops[opIndex + numberCharacters]) {
691             PatternTerm* nextTerm = nextOp->m_term;
692             
693             if (nextTerm->type != PatternTerm::TypePatternCharacter
694                 || nextTerm->quantityType != QuantifierFixedCount
695                 || nextTerm->quantityCount != 1
696                 || nextTerm->inputPosition != (startTermPosition + numberCharacters))
697                 break;
698
699             nextOp->m_isDeadCode = true;
700
701             int shiftAmount = (m_charSize == Char8 ? 8 : 16) * numberCharacters;
702             currentCharacterMask = (m_charSize == Char8 ? 0xff : 0xffff) << shiftAmount;  
703
704             UChar currentCharacter = nextTerm->patternCharacter;
705
706             if ((currentCharacter > 0xff) && (m_charSize == Char8)) {
707                 // Have a 16 bit pattern character and an 8 bit string - short circuit
708                 op.m_jumps.append(jump());
709                 return;
710             }
711
712             // For case-insesitive compares, non-ascii characters that have different
713             // upper & lower case representations are converted to a character class.
714             ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(currentCharacter) || (Unicode::toLower(currentCharacter) == Unicode::toUpper(currentCharacter)));
715
716             allCharacters |= (currentCharacter << shiftAmount);
717
718             if ((m_pattern.m_ignoreCase) && (isASCIIAlpha(currentCharacter)))
719                 ignoreCaseMask |= 32 << shiftAmount;                    
720         }
721
722         if (m_charSize == Char8) {
723             switch (numberCharacters) {
724             case 1:
725                 op.m_jumps.append(jumpIfCharNotEquals(ch, startTermPosition - m_checked, character));
726                 return;
727             case 2: {
728                 BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
729                 load16(address, character);
730                 break;
731             }
732             case 3: {
733                 BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
734                 load32WithUnalignedHalfWords(address, character);
735                 and32(Imm32(0xffffff), character);
736                 break;
737             }
738             case 4: {
739                 BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
740                 load32WithUnalignedHalfWords(address, character);
741                 break;
742             }
743             }
744         } else {
745             switch (numberCharacters) {
746             case 1:
747                 op.m_jumps.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
748                 return;
749             case 2:
750                 BaseIndex address(input, index, TimesTwo, (term->inputPosition - m_checked) * sizeof(UChar));
751                 load32WithUnalignedHalfWords(address, character);
752                 break;
753             }
754         }
755
756         if (ignoreCaseMask)
757             or32(Imm32(ignoreCaseMask), character);
758         op.m_jumps.append(branch32(NotEqual, character, Imm32(allCharacters | ignoreCaseMask)));
759         return;
760     }
761     void backtrackPatternCharacterOnce(size_t opIndex)
762     {
763         backtrackTermDefault(opIndex);
764     }
765
766     void generatePatternCharacterFixed(size_t opIndex)
767     {
768         YarrOp& op = m_ops[opIndex];
769         PatternTerm* term = op.m_term;
770         UChar ch = term->patternCharacter;
771
772         const RegisterID character = regT0;
773         const RegisterID countRegister = regT1;
774
775         move(index, countRegister);
776         sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);
777
778         Label loop(this);
779         BaseIndex address(input, countRegister, m_charScale, (Checked<int>(term->inputPosition - m_checked + Checked<int64_t>(term->quantityCount)) * static_cast<int>(m_charSize == Char8 ? sizeof(char) : sizeof(UChar))).unsafeGet());
780
781         if (m_charSize == Char8)
782             load8(address, character);
783         else
784             load16(address, character);
785
786         // For case-insesitive compares, non-ascii characters that have different
787         // upper & lower case representations are converted to a character class.
788         ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
789         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
790             or32(TrustedImm32(32), character);
791             ch = Unicode::toLower(ch);
792         }
793
794         op.m_jumps.append(branch32(NotEqual, character, Imm32(ch)));
795         add32(TrustedImm32(1), countRegister);
796         branch32(NotEqual, countRegister, index).linkTo(loop, this);
797     }
798     void backtrackPatternCharacterFixed(size_t opIndex)
799     {
800         backtrackTermDefault(opIndex);
801     }
802
803     void generatePatternCharacterGreedy(size_t opIndex)
804     {
805         YarrOp& op = m_ops[opIndex];
806         PatternTerm* term = op.m_term;
807         UChar ch = term->patternCharacter;
808
809         const RegisterID character = regT0;
810         const RegisterID countRegister = regT1;
811
812         move(TrustedImm32(0), countRegister);
813
814         if ((ch > 0xff) && (m_charSize == Char8)) {
815             // Have a 16 bit pattern character and an 8 bit string - short circuit
816             op.m_jumps.append(jump());
817         } else {
818             JumpList failures;
819             Label loop(this);
820             failures.append(atEndOfInput());
821             failures.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
822
823             add32(TrustedImm32(1), countRegister);
824             add32(TrustedImm32(1), index);
825             if (term->quantityCount == quantifyInfinite)
826                 jump(loop);
827             else
828                 branch32(NotEqual, countRegister, Imm32(term->quantityCount.unsafeGet())).linkTo(loop, this);
829
830             failures.link(this);
831         }
832         op.m_reentry = label();
833
834         storeToFrame(countRegister, term->frameLocation);
835
836     }
837     void backtrackPatternCharacterGreedy(size_t opIndex)
838     {
839         YarrOp& op = m_ops[opIndex];
840         PatternTerm* term = op.m_term;
841
842         const RegisterID countRegister = regT1;
843
844         m_backtrackingState.link(this);
845
846         loadFromFrame(term->frameLocation, countRegister);
847         m_backtrackingState.append(branchTest32(Zero, countRegister));
848         sub32(TrustedImm32(1), countRegister);
849         sub32(TrustedImm32(1), index);
850         jump(op.m_reentry);
851     }
852
853     void generatePatternCharacterNonGreedy(size_t opIndex)
854     {
855         YarrOp& op = m_ops[opIndex];
856         PatternTerm* term = op.m_term;
857
858         const RegisterID countRegister = regT1;
859
860         move(TrustedImm32(0), countRegister);
861         op.m_reentry = label();
862         storeToFrame(countRegister, term->frameLocation);
863     }
864     void backtrackPatternCharacterNonGreedy(size_t opIndex)
865     {
866         YarrOp& op = m_ops[opIndex];
867         PatternTerm* term = op.m_term;
868         UChar ch = term->patternCharacter;
869
870         const RegisterID character = regT0;
871         const RegisterID countRegister = regT1;
872
873         JumpList nonGreedyFailures;
874
875         m_backtrackingState.link(this);
876
877         loadFromFrame(term->frameLocation, countRegister);
878
879         if ((ch > 0xff) && (m_charSize == Char8)) {
880             // Have a 16 bit pattern character and an 8 bit string - short circuit
881             nonGreedyFailures.append(jump());
882         } else {
883             nonGreedyFailures.append(atEndOfInput());
884             if (term->quantityCount != quantifyInfinite)
885                 nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));
886             nonGreedyFailures.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
887
888             add32(TrustedImm32(1), countRegister);
889             add32(TrustedImm32(1), index);
890
891             jump(op.m_reentry);
892         }
893         nonGreedyFailures.link(this);
894
895         sub32(countRegister, index);
896         m_backtrackingState.fallthrough();
897     }
898
899     void generateCharacterClassOnce(size_t opIndex)
900     {
901         YarrOp& op = m_ops[opIndex];
902         PatternTerm* term = op.m_term;
903
904         const RegisterID character = regT0;
905
906         JumpList matchDest;
907         readCharacter(term->inputPosition - m_checked, character);
908         matchCharacterClass(character, matchDest, term->characterClass);
909
910         if (term->invert())
911             op.m_jumps.append(matchDest);
912         else {
913             op.m_jumps.append(jump());
914             matchDest.link(this);
915         }
916     }
917     void backtrackCharacterClassOnce(size_t opIndex)
918     {
919         backtrackTermDefault(opIndex);
920     }
921
922     void generateCharacterClassFixed(size_t opIndex)
923     {
924         YarrOp& op = m_ops[opIndex];
925         PatternTerm* term = op.m_term;
926
927         const RegisterID character = regT0;
928         const RegisterID countRegister = regT1;
929
930         move(index, countRegister);
931         sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);
932
933         Label loop(this);
934         JumpList matchDest;
935         if (m_charSize == Char8)
936             load8(BaseIndex(input, countRegister, TimesOne, (Checked<int>(term->inputPosition - m_checked + Checked<int64_t>(term->quantityCount)) * static_cast<int>(sizeof(char))).unsafeGet()), character);
937         else
938             load16(BaseIndex(input, countRegister, TimesTwo, (Checked<int>(term->inputPosition - m_checked + Checked<int64_t>(term->quantityCount)) * static_cast<int>(sizeof(UChar))).unsafeGet()), character);
939         matchCharacterClass(character, matchDest, term->characterClass);
940
941         if (term->invert())
942             op.m_jumps.append(matchDest);
943         else {
944             op.m_jumps.append(jump());
945             matchDest.link(this);
946         }
947
948         add32(TrustedImm32(1), countRegister);
949         branch32(NotEqual, countRegister, index).linkTo(loop, this);
950     }
951     void backtrackCharacterClassFixed(size_t opIndex)
952     {
953         backtrackTermDefault(opIndex);
954     }
955
956     void generateCharacterClassGreedy(size_t opIndex)
957     {
958         YarrOp& op = m_ops[opIndex];
959         PatternTerm* term = op.m_term;
960
961         const RegisterID character = regT0;
962         const RegisterID countRegister = regT1;
963
964         move(TrustedImm32(0), countRegister);
965
966         JumpList failures;
967         Label loop(this);
968         failures.append(atEndOfInput());
969
970         if (term->invert()) {
971             readCharacter(term->inputPosition - m_checked, character);
972             matchCharacterClass(character, failures, term->characterClass);
973         } else {
974             JumpList matchDest;
975             readCharacter(term->inputPosition - m_checked, character);
976             matchCharacterClass(character, matchDest, term->characterClass);
977             failures.append(jump());
978             matchDest.link(this);
979         }
980
981         add32(TrustedImm32(1), countRegister);
982         add32(TrustedImm32(1), index);
983         if (term->quantityCount != quantifyInfinite) {
984             branch32(NotEqual, countRegister, Imm32(term->quantityCount.unsafeGet())).linkTo(loop, this);
985             failures.append(jump());
986         } else
987             jump(loop);
988
989         failures.link(this);
990         op.m_reentry = label();
991
992         storeToFrame(countRegister, term->frameLocation);
993     }
994     void backtrackCharacterClassGreedy(size_t opIndex)
995     {
996         YarrOp& op = m_ops[opIndex];
997         PatternTerm* term = op.m_term;
998
999         const RegisterID countRegister = regT1;
1000
1001         m_backtrackingState.link(this);
1002
1003         loadFromFrame(term->frameLocation, countRegister);
1004         m_backtrackingState.append(branchTest32(Zero, countRegister));
1005         sub32(TrustedImm32(1), countRegister);
1006         sub32(TrustedImm32(1), index);
1007         jump(op.m_reentry);
1008     }
1009
1010     void generateCharacterClassNonGreedy(size_t opIndex)
1011     {
1012         YarrOp& op = m_ops[opIndex];
1013         PatternTerm* term = op.m_term;
1014
1015         const RegisterID countRegister = regT1;
1016
1017         move(TrustedImm32(0), countRegister);
1018         op.m_reentry = label();
1019         storeToFrame(countRegister, term->frameLocation);
1020     }
1021     void backtrackCharacterClassNonGreedy(size_t opIndex)
1022     {
1023         YarrOp& op = m_ops[opIndex];
1024         PatternTerm* term = op.m_term;
1025
1026         const RegisterID character = regT0;
1027         const RegisterID countRegister = regT1;
1028
1029         JumpList nonGreedyFailures;
1030
1031         m_backtrackingState.link(this);
1032
1033         Label backtrackBegin(this);
1034         loadFromFrame(term->frameLocation, countRegister);
1035
1036         nonGreedyFailures.append(atEndOfInput());
1037         nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));
1038
1039         JumpList matchDest;
1040         readCharacter(term->inputPosition - m_checked, character);
1041         matchCharacterClass(character, matchDest, term->characterClass);
1042
1043         if (term->invert())
1044             nonGreedyFailures.append(matchDest);
1045         else {
1046             nonGreedyFailures.append(jump());
1047             matchDest.link(this);
1048         }
1049
1050         add32(TrustedImm32(1), countRegister);
1051         add32(TrustedImm32(1), index);
1052
1053         jump(op.m_reentry);
1054
1055         nonGreedyFailures.link(this);
1056         sub32(countRegister, index);
1057         m_backtrackingState.fallthrough();
1058     }
1059
1060     void generateDotStarEnclosure(size_t opIndex)
1061     {
1062         YarrOp& op = m_ops[opIndex];
1063         PatternTerm* term = op.m_term;
1064
1065         const RegisterID character = regT0;
1066         const RegisterID matchPos = regT1;
1067
1068         JumpList foundBeginningNewLine;
1069         JumpList saveStartIndex;
1070         JumpList foundEndingNewLine;
1071
1072         if (m_pattern.m_body->m_hasFixedSize) {
1073             move(index, matchPos);
1074             sub32(Imm32(m_checked), matchPos);
1075         } else
1076             load32(Address(output), matchPos);
1077
1078         saveStartIndex.append(branchTest32(Zero, matchPos));
1079         Label findBOLLoop(this);
1080         sub32(TrustedImm32(1), matchPos);
1081         if (m_charSize == Char8)
1082             load8(BaseIndex(input, matchPos, TimesOne, 0), character);
1083         else
1084             load16(BaseIndex(input, matchPos, TimesTwo, 0), character);
1085         matchCharacterClass(character, foundBeginningNewLine, m_pattern.newlineCharacterClass());
1086         branchTest32(NonZero, matchPos).linkTo(findBOLLoop, this);
1087         saveStartIndex.append(jump());
1088
1089         foundBeginningNewLine.link(this);
1090         add32(TrustedImm32(1), matchPos); // Advance past newline
1091         saveStartIndex.link(this);
1092
1093         if (!m_pattern.m_multiline && term->anchors.bolAnchor)
1094             op.m_jumps.append(branchTest32(NonZero, matchPos));
1095
1096         store32(matchPos, Address(output));
1097
1098         move(index, matchPos);
1099
1100         Label findEOLLoop(this);        
1101         foundEndingNewLine.append(branch32(Equal, matchPos, length));
1102         if (m_charSize == Char8)
1103             load8(BaseIndex(input, matchPos, TimesOne, 0), character);
1104         else
1105             load16(BaseIndex(input, matchPos, TimesTwo, 0), character);
1106         matchCharacterClass(character, foundEndingNewLine, m_pattern.newlineCharacterClass());
1107         add32(TrustedImm32(1), matchPos);
1108         jump(findEOLLoop);
1109
1110         foundEndingNewLine.link(this);
1111
1112         if (!m_pattern.m_multiline && term->anchors.eolAnchor)
1113             op.m_jumps.append(branch32(NotEqual, matchPos, length));
1114
1115         move(matchPos, index);
1116     }
1117
1118     void backtrackDotStarEnclosure(size_t opIndex)
1119     {
1120         backtrackTermDefault(opIndex);
1121     }
1122     
1123     // Code generation/backtracking for simple terms
1124     // (pattern characters, character classes, and assertions).
1125     // These methods farm out work to the set of functions above.
1126     void generateTerm(size_t opIndex)
1127     {
1128         YarrOp& op = m_ops[opIndex];
1129         PatternTerm* term = op.m_term;
1130
1131         switch (term->type) {
1132         case PatternTerm::TypePatternCharacter:
1133             switch (term->quantityType) {
1134             case QuantifierFixedCount:
1135                 if (term->quantityCount == 1)
1136                     generatePatternCharacterOnce(opIndex);
1137                 else
1138                     generatePatternCharacterFixed(opIndex);
1139                 break;
1140             case QuantifierGreedy:
1141                 generatePatternCharacterGreedy(opIndex);
1142                 break;
1143             case QuantifierNonGreedy:
1144                 generatePatternCharacterNonGreedy(opIndex);
1145                 break;
1146             }
1147             break;
1148
1149         case PatternTerm::TypeCharacterClass:
1150             switch (term->quantityType) {
1151             case QuantifierFixedCount:
1152                 if (term->quantityCount == 1)
1153                     generateCharacterClassOnce(opIndex);
1154                 else
1155                     generateCharacterClassFixed(opIndex);
1156                 break;
1157             case QuantifierGreedy:
1158                 generateCharacterClassGreedy(opIndex);
1159                 break;
1160             case QuantifierNonGreedy:
1161                 generateCharacterClassNonGreedy(opIndex);
1162                 break;
1163             }
1164             break;
1165
1166         case PatternTerm::TypeAssertionBOL:
1167             generateAssertionBOL(opIndex);
1168             break;
1169
1170         case PatternTerm::TypeAssertionEOL:
1171             generateAssertionEOL(opIndex);
1172             break;
1173
1174         case PatternTerm::TypeAssertionWordBoundary:
1175             generateAssertionWordBoundary(opIndex);
1176             break;
1177
1178         case PatternTerm::TypeForwardReference:
1179             break;
1180
1181         case PatternTerm::TypeParenthesesSubpattern:
1182         case PatternTerm::TypeParentheticalAssertion:
1183             ASSERT_NOT_REACHED();
1184         case PatternTerm::TypeBackReference:
1185             m_shouldFallBack = true;
1186             break;
1187         case PatternTerm::TypeDotStarEnclosure:
1188             generateDotStarEnclosure(opIndex);
1189             break;
1190         }
1191     }
1192     void backtrackTerm(size_t opIndex)
1193     {
1194         YarrOp& op = m_ops[opIndex];
1195         PatternTerm* term = op.m_term;
1196
1197         switch (term->type) {
1198         case PatternTerm::TypePatternCharacter:
1199             switch (term->quantityType) {
1200             case QuantifierFixedCount:
1201                 if (term->quantityCount == 1)
1202                     backtrackPatternCharacterOnce(opIndex);
1203                 else
1204                     backtrackPatternCharacterFixed(opIndex);
1205                 break;
1206             case QuantifierGreedy:
1207                 backtrackPatternCharacterGreedy(opIndex);
1208                 break;
1209             case QuantifierNonGreedy:
1210                 backtrackPatternCharacterNonGreedy(opIndex);
1211                 break;
1212             }
1213             break;
1214
1215         case PatternTerm::TypeCharacterClass:
1216             switch (term->quantityType) {
1217             case QuantifierFixedCount:
1218                 if (term->quantityCount == 1)
1219                     backtrackCharacterClassOnce(opIndex);
1220                 else
1221                     backtrackCharacterClassFixed(opIndex);
1222                 break;
1223             case QuantifierGreedy:
1224                 backtrackCharacterClassGreedy(opIndex);
1225                 break;
1226             case QuantifierNonGreedy:
1227                 backtrackCharacterClassNonGreedy(opIndex);
1228                 break;
1229             }
1230             break;
1231
1232         case PatternTerm::TypeAssertionBOL:
1233             backtrackAssertionBOL(opIndex);
1234             break;
1235
1236         case PatternTerm::TypeAssertionEOL:
1237             backtrackAssertionEOL(opIndex);
1238             break;
1239
1240         case PatternTerm::TypeAssertionWordBoundary:
1241             backtrackAssertionWordBoundary(opIndex);
1242             break;
1243
1244         case PatternTerm::TypeForwardReference:
1245             break;
1246
1247         case PatternTerm::TypeParenthesesSubpattern:
1248         case PatternTerm::TypeParentheticalAssertion:
1249             ASSERT_NOT_REACHED();
1250
1251         case PatternTerm::TypeDotStarEnclosure:
1252             backtrackDotStarEnclosure(opIndex);
1253             break;
1254
1255         case PatternTerm::TypeBackReference:
1256             m_shouldFallBack = true;
1257             break;
1258         }
1259     }
1260
1261     void generate()
1262     {
1263         // Forwards generate the matching code.
1264         ASSERT(m_ops.size());
1265         size_t opIndex = 0;
1266
1267         do {
1268             YarrOp& op = m_ops[opIndex];
1269             switch (op.m_op) {
1270
1271             case OpTerm:
1272                 generateTerm(opIndex);
1273                 break;
1274
1275             // OpBodyAlternativeBegin/Next/End
1276             //
1277             // These nodes wrap the set of alternatives in the body of the regular expression.
1278             // There may be either one or two chains of OpBodyAlternative nodes, one representing
1279             // the 'once through' sequence of alternatives (if any exist), and one representing
1280             // the repeating alternatives (again, if any exist).
1281             //
1282             // Upon normal entry to the Begin alternative, we will check that input is available.
1283             // Reentry to the Begin alternative will take place after the check has taken place,
1284             // and will assume that the input position has already been progressed as appropriate.
1285             //
1286             // Entry to subsequent Next/End alternatives occurs when the prior alternative has
1287             // successfully completed a match - return a success state from JIT code.
1288             //
1289             // Next alternatives allow for reentry optimized to suit backtracking from its
1290             // preceding alternative. It expects the input position to still be set to a position
1291             // appropriate to its predecessor, and it will only perform an input check if the
1292             // predecessor had a minimum size less than its own.
1293             //
1294             // In the case 'once through' expressions, the End node will also have a reentry
1295             // point to jump to when the last alternative fails. Again, this expects the input
1296             // position to still reflect that expected by the prior alternative.
1297             case OpBodyAlternativeBegin: {
1298                 PatternAlternative* alternative = op.m_alternative;
1299
1300                 // Upon entry at the head of the set of alternatives, check if input is available
1301                 // to run the first alternative. (This progresses the input position).
1302                 op.m_jumps.append(jumpIfNoAvailableInput(alternative->m_minimumSize));
1303                 // We will reenter after the check, and assume the input position to have been
1304                 // set as appropriate to this alternative.
1305                 op.m_reentry = label();
1306
1307                 m_checked += alternative->m_minimumSize;
1308                 break;
1309             }
1310             case OpBodyAlternativeNext:
1311             case OpBodyAlternativeEnd: {
1312                 PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
1313                 PatternAlternative* alternative = op.m_alternative;
1314
1315                 // If we get here, the prior alternative matched - return success.
1316                 
1317                 // Adjust the stack pointer to remove the pattern's frame.
1318                 if (m_pattern.m_body->m_callFrameSize)
1319                     addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1320
1321                 // Load appropriate values into the return register and the first output
1322                 // slot, and return. In the case of pattern with a fixed size, we will
1323                 // not have yet set the value in the first 
1324                 ASSERT(index != returnRegister);
1325                 if (m_pattern.m_body->m_hasFixedSize) {
1326                     move(index, returnRegister);
1327                     if (priorAlternative->m_minimumSize)
1328                         sub32(Imm32(priorAlternative->m_minimumSize), returnRegister);
1329                     store32(returnRegister, output);
1330                 } else
1331                     load32(Address(output), returnRegister);
1332                 store32(index, Address(output, 4));
1333                 generateReturn();
1334
1335                 // This is the divide between the tail of the prior alternative, above, and
1336                 // the head of the subsequent alternative, below.
1337
1338                 if (op.m_op == OpBodyAlternativeNext) {
1339                     // This is the reentry point for the Next alternative. We expect any code
1340                     // that jumps here to do so with the input position matching that of the
1341                     // PRIOR alteranative, and we will only check input availability if we
1342                     // need to progress it forwards.
1343                     op.m_reentry = label();
1344                     if (alternative->m_minimumSize > priorAlternative->m_minimumSize) {
1345                         add32(Imm32(alternative->m_minimumSize - priorAlternative->m_minimumSize), index);
1346                         op.m_jumps.append(jumpIfNoAvailableInput());
1347                     } else if (priorAlternative->m_minimumSize > alternative->m_minimumSize)
1348                         sub32(Imm32(priorAlternative->m_minimumSize - alternative->m_minimumSize), index);
1349                 } else if (op.m_nextOp == notFound) {
1350                     // This is the reentry point for the End of 'once through' alternatives,
1351                     // jumped to when the last alternative fails to match.
1352                     op.m_reentry = label();
1353                     sub32(Imm32(priorAlternative->m_minimumSize), index);
1354                 }
1355
1356                 if (op.m_op == OpBodyAlternativeNext)
1357                     m_checked += alternative->m_minimumSize;
1358                 m_checked -= priorAlternative->m_minimumSize;
1359                 break;
1360             }
1361
1362             // OpSimpleNestedAlternativeBegin/Next/End
1363             // OpNestedAlternativeBegin/Next/End
1364             //
1365             // These nodes are used to handle sets of alternatives that are nested within
1366             // subpatterns and parenthetical assertions. The 'simple' forms are used where
1367             // we do not need to be able to backtrack back into any alternative other than
1368             // the last, the normal forms allow backtracking into any alternative.
1369             //
1370             // Each Begin/Next node is responsible for planting an input check to ensure
1371             // sufficient input is available on entry. Next nodes additionally need to
1372             // jump to the end - Next nodes use the End node's m_jumps list to hold this
1373             // set of jumps.
1374             //
1375             // In the non-simple forms, successful alternative matches must store a
1376             // 'return address' using a DataLabelPtr, used to store the address to jump
1377             // to when backtracking, to get to the code for the appropriate alternative.
1378             case OpSimpleNestedAlternativeBegin:
1379             case OpNestedAlternativeBegin: {
1380                 PatternTerm* term = op.m_term;
1381                 PatternAlternative* alternative = op.m_alternative;
1382                 PatternDisjunction* disjunction = term->parentheses.disjunction;
1383
1384                 // Calculate how much input we need to check for, and if non-zero check.
1385                 op.m_checkAdjust = alternative->m_minimumSize;
1386                 if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion))
1387                     op.m_checkAdjust -= disjunction->m_minimumSize;
1388                 if (op.m_checkAdjust)
1389                     op.m_jumps.append(jumpIfNoAvailableInput(op.m_checkAdjust));
1390  
1391                 m_checked += op.m_checkAdjust;
1392                 break;
1393             }
1394             case OpSimpleNestedAlternativeNext:
1395             case OpNestedAlternativeNext: {
1396                 PatternTerm* term = op.m_term;
1397                 PatternAlternative* alternative = op.m_alternative;
1398                 PatternDisjunction* disjunction = term->parentheses.disjunction;
1399
1400                 // In the non-simple case, store a 'return address' so we can backtrack correctly.
1401                 if (op.m_op == OpNestedAlternativeNext) {
1402                     unsigned parenthesesFrameLocation = term->frameLocation;
1403                     unsigned alternativeFrameLocation = parenthesesFrameLocation;
1404                     if (term->quantityType != QuantifierFixedCount)
1405                         alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1406                     op.m_returnAddress = storeToFrameWithPatch(alternativeFrameLocation);
1407                 }
1408
1409                 // If we reach here then the last alternative has matched - jump to the
1410                 // End node, to skip over any further alternatives.
1411                 //
1412                 // FIXME: this is logically O(N^2) (though N can be expected to be very
1413                 // small). We could avoid this either by adding an extra jump to the JIT
1414                 // data structures, or by making backtracking code that jumps to Next
1415                 // alternatives are responsible for checking that input is available (if
1416                 // we didn't need to plant the input checks, then m_jumps would be free).
1417                 YarrOp* endOp = &m_ops[op.m_nextOp];
1418                 while (endOp->m_nextOp != notFound) {
1419                     ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext);
1420                     endOp = &m_ops[endOp->m_nextOp];
1421                 }
1422                 ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd);
1423                 endOp->m_jumps.append(jump());
1424
1425                 // This is the entry point for the next alternative.
1426                 op.m_reentry = label();
1427
1428                 // Calculate how much input we need to check for, and if non-zero check.
1429                 op.m_checkAdjust = alternative->m_minimumSize;
1430                 if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion))
1431                     op.m_checkAdjust -= disjunction->m_minimumSize;
1432                 if (op.m_checkAdjust)
1433                     op.m_jumps.append(jumpIfNoAvailableInput(op.m_checkAdjust));
1434
1435                 YarrOp& lastOp = m_ops[op.m_previousOp];
1436                 m_checked -= lastOp.m_checkAdjust;
1437                 m_checked += op.m_checkAdjust;
1438                 break;
1439             }
1440             case OpSimpleNestedAlternativeEnd:
1441             case OpNestedAlternativeEnd: {
1442                 PatternTerm* term = op.m_term;
1443
1444                 // In the non-simple case, store a 'return address' so we can backtrack correctly.
1445                 if (op.m_op == OpNestedAlternativeEnd) {
1446                     unsigned parenthesesFrameLocation = term->frameLocation;
1447                     unsigned alternativeFrameLocation = parenthesesFrameLocation;
1448                     if (term->quantityType != QuantifierFixedCount)
1449                         alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1450                     op.m_returnAddress = storeToFrameWithPatch(alternativeFrameLocation);
1451                 }
1452
1453                 // If this set of alternatives contains more than one alternative,
1454                 // then the Next nodes will have planted jumps to the End, and added
1455                 // them to this node's m_jumps list.
1456                 op.m_jumps.link(this);
1457                 op.m_jumps.clear();
1458
1459                 YarrOp& lastOp = m_ops[op.m_previousOp];
1460                 m_checked -= lastOp.m_checkAdjust;
1461                 break;
1462             }
1463
1464             // OpParenthesesSubpatternOnceBegin/End
1465             //
1466             // These nodes support (optionally) capturing subpatterns, that have a
1467             // quantity count of 1 (this covers fixed once, and ?/?? quantifiers). 
1468             case OpParenthesesSubpatternOnceBegin: {
1469                 PatternTerm* term = op.m_term;
1470                 unsigned parenthesesFrameLocation = term->frameLocation;
1471                 const RegisterID indexTemporary = regT0;
1472                 ASSERT(term->quantityCount == 1);
1473
1474                 // Upon entry to a Greedy quantified set of parenthese store the index.
1475                 // We'll use this for two purposes:
1476                 //  - To indicate which iteration we are on of mathing the remainder of
1477                 //    the expression after the parentheses - the first, including the
1478                 //    match within the parentheses, or the second having skipped over them.
1479                 //  - To check for empty matches, which must be rejected.
1480                 //
1481                 // At the head of a NonGreedy set of parentheses we'll immediately set the
1482                 // value on the stack to -1 (indicating a match skipping the subpattern),
1483                 // and plant a jump to the end. We'll also plant a label to backtrack to
1484                 // to reenter the subpattern later, with a store to set up index on the
1485                 // second iteration.
1486                 //
1487                 // FIXME: for capturing parens, could use the index in the capture array?
1488                 if (term->quantityType == QuantifierGreedy)
1489                     storeToFrame(index, parenthesesFrameLocation);
1490                 else if (term->quantityType == QuantifierNonGreedy) {
1491                     storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1492                     op.m_jumps.append(jump());
1493                     op.m_reentry = label();
1494                     storeToFrame(index, parenthesesFrameLocation);
1495                 }
1496
1497                 // If the parenthese are capturing, store the starting index value to the
1498                 // captures array, offsetting as necessary.
1499                 //
1500                 // FIXME: could avoid offsetting this value in JIT code, apply
1501                 // offsets only afterwards, at the point the results array is
1502                 // being accessed.
1503                 if (term->capture()) {
1504                     int offsetId = term->parentheses.subpatternId << 1;
1505                     int inputOffset = term->inputPosition - m_checked;
1506                     if (term->quantityType == QuantifierFixedCount)
1507                         inputOffset -= term->parentheses.disjunction->m_minimumSize;
1508                     if (inputOffset) {
1509                         move(index, indexTemporary);
1510                         add32(Imm32(inputOffset), indexTemporary);
1511                         store32(indexTemporary, Address(output, offsetId * sizeof(int)));
1512                     } else
1513                         store32(index, Address(output, offsetId * sizeof(int)));
1514                 }
1515                 break;
1516             }
1517             case OpParenthesesSubpatternOnceEnd: {
1518                 PatternTerm* term = op.m_term;
1519                 unsigned parenthesesFrameLocation = term->frameLocation;
1520                 const RegisterID indexTemporary = regT0;
1521                 ASSERT(term->quantityCount == 1);
1522
1523                 // For Greedy/NonGreedy quantified parentheses, we must reject zero length
1524                 // matches. If the minimum size is know to be non-zero we need not check.
1525                 if (term->quantityType != QuantifierFixedCount && !term->parentheses.disjunction->m_minimumSize)
1526                     op.m_jumps.append(branch32(Equal, index, Address(stackPointerRegister, parenthesesFrameLocation * sizeof(void*))));
1527
1528                 // If the parenthese are capturing, store the ending index value to the
1529                 // captures array, offsetting as necessary.
1530                 //
1531                 // FIXME: could avoid offsetting this value in JIT code, apply
1532                 // offsets only afterwards, at the point the results array is
1533                 // being accessed.
1534                 if (term->capture()) {
1535                     int offsetId = (term->parentheses.subpatternId << 1) + 1;
1536                     int inputOffset = term->inputPosition - m_checked;
1537                     if (inputOffset) {
1538                         move(index, indexTemporary);
1539                         add32(Imm32(inputOffset), indexTemporary);
1540                         store32(indexTemporary, Address(output, offsetId * sizeof(int)));
1541                     } else
1542                         store32(index, Address(output, offsetId * sizeof(int)));
1543                 }
1544
1545                 // If the parentheses are quantified Greedy then add a label to jump back
1546                 // to if get a failed match from after the parentheses. For NonGreedy
1547                 // parentheses, link the jump from before the subpattern to here.
1548                 if (term->quantityType == QuantifierGreedy)
1549                     op.m_reentry = label();
1550                 else if (term->quantityType == QuantifierNonGreedy) {
1551                     YarrOp& beginOp = m_ops[op.m_previousOp];
1552                     beginOp.m_jumps.link(this);
1553                 }
1554                 break;
1555             }
1556
1557             // OpParenthesesSubpatternTerminalBegin/End
1558             case OpParenthesesSubpatternTerminalBegin: {
1559                 PatternTerm* term = op.m_term;
1560                 ASSERT(term->quantityType == QuantifierGreedy);
1561                 ASSERT(term->quantityCount == quantifyInfinite);
1562                 ASSERT(!term->capture());
1563
1564                 // Upon entry set a label to loop back to.
1565                 op.m_reentry = label();
1566
1567                 // Store the start index of the current match; we need to reject zero
1568                 // length matches.
1569                 storeToFrame(index, term->frameLocation);
1570                 break;
1571             }
1572             case OpParenthesesSubpatternTerminalEnd: {
1573                 PatternTerm* term = op.m_term;
1574
1575                 // Check for zero length matches - if the match is non-zero, then we
1576                 // can accept it & loop back up to the head of the subpattern.
1577                 YarrOp& beginOp = m_ops[op.m_previousOp];
1578                 branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)), beginOp.m_reentry);
1579
1580                 // Reject the match - backtrack back into the subpattern.
1581                 op.m_jumps.append(jump());
1582
1583                 // This is the entry point to jump to when we stop matching - we will
1584                 // do so once the subpattern cannot match any more.
1585                 op.m_reentry = label();
1586                 break;
1587             }
1588
1589             // OpParentheticalAssertionBegin/End
1590             case OpParentheticalAssertionBegin: {
1591                 PatternTerm* term = op.m_term;
1592
1593                 // Store the current index - assertions should not update index, so
1594                 // we will need to restore it upon a successful match.
1595                 unsigned parenthesesFrameLocation = term->frameLocation;
1596                 storeToFrame(index, parenthesesFrameLocation);
1597
1598                 // Check 
1599                 op.m_checkAdjust = m_checked - term->inputPosition;
1600                 if (op.m_checkAdjust)
1601                     sub32(Imm32(op.m_checkAdjust), index);
1602
1603                 m_checked -= op.m_checkAdjust;
1604                 break;
1605             }
1606             case OpParentheticalAssertionEnd: {
1607                 PatternTerm* term = op.m_term;
1608
1609                 // Restore the input index value.
1610                 unsigned parenthesesFrameLocation = term->frameLocation;
1611                 loadFromFrame(parenthesesFrameLocation, index);
1612
1613                 // If inverted, a successful match of the assertion must be treated
1614                 // as a failure, so jump to backtracking.
1615                 if (term->invert()) {
1616                     op.m_jumps.append(jump());
1617                     op.m_reentry = label();
1618                 }
1619
1620                 YarrOp& lastOp = m_ops[op.m_previousOp];
1621                 m_checked += lastOp.m_checkAdjust;
1622                 break;
1623             }
1624
1625             case OpMatchFailed:
1626                 if (m_pattern.m_body->m_callFrameSize)
1627                     addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1628                 move(TrustedImm32(-1), returnRegister);
1629                 generateReturn();
1630                 break;
1631             }
1632
1633             ++opIndex;
1634         } while (opIndex < m_ops.size());
1635     }
1636
1637     void backtrack()
1638     {
1639         // Backwards generate the backtracking code.
1640         size_t opIndex = m_ops.size();
1641         ASSERT(opIndex);
1642
1643         do {
1644             --opIndex;
1645             YarrOp& op = m_ops[opIndex];
1646             switch (op.m_op) {
1647
1648             case OpTerm:
1649                 backtrackTerm(opIndex);
1650                 break;
1651
1652             // OpBodyAlternativeBegin/Next/End
1653             //
1654             // For each Begin/Next node representing an alternative, we need to decide what to do
1655             // in two circumstances:
1656             //  - If we backtrack back into this node, from within the alternative.
1657             //  - If the input check at the head of the alternative fails (if this exists).
1658             //
1659             // We treat these two cases differently since in the former case we have slightly
1660             // more information - since we are backtracking out of a prior alternative we know
1661             // that at least enough input was available to run it. For example, given the regular
1662             // expression /a|b/, if we backtrack out of the first alternative (a failed pattern
1663             // character match of 'a'), then we need not perform an additional input availability
1664             // check before running the second alternative.
1665             //
1666             // Backtracking required differs for the last alternative, which in the case of the
1667             // repeating set of alternatives must loop. The code generated for the last alternative
1668             // will also be used to handle all input check failures from any prior alternatives -
1669             // these require similar functionality, in seeking the next available alternative for
1670             // which there is sufficient input.
1671             //
1672             // Since backtracking of all other alternatives simply requires us to link backtracks
1673             // to the reentry point for the subsequent alternative, we will only be generating any
1674             // code when backtracking the last alternative.
1675             case OpBodyAlternativeBegin:
1676             case OpBodyAlternativeNext: {
1677                 PatternAlternative* alternative = op.m_alternative;
1678
1679                 if (op.m_op == OpBodyAlternativeNext) {
1680                     PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
1681                     m_checked += priorAlternative->m_minimumSize;
1682                 }
1683                 m_checked -= alternative->m_minimumSize;
1684
1685                 // Is this the last alternative? If not, then if we backtrack to this point we just
1686                 // need to jump to try to match the next alternative.
1687                 if (m_ops[op.m_nextOp].m_op != OpBodyAlternativeEnd) {
1688                     m_backtrackingState.linkTo(m_ops[op.m_nextOp].m_reentry, this);
1689                     break;
1690                 }
1691                 YarrOp& endOp = m_ops[op.m_nextOp];
1692
1693                 YarrOp* beginOp = &op;
1694                 while (beginOp->m_op != OpBodyAlternativeBegin) {
1695                     ASSERT(beginOp->m_op == OpBodyAlternativeNext);
1696                     beginOp = &m_ops[beginOp->m_previousOp];
1697                 }
1698
1699                 bool onceThrough = endOp.m_nextOp == notFound;
1700
1701                 // First, generate code to handle cases where we backtrack out of an attempted match
1702                 // of the last alternative. If this is a 'once through' set of alternatives then we
1703                 // have nothing to do - link this straight through to the End.
1704                 if (onceThrough)
1705                     m_backtrackingState.linkTo(endOp.m_reentry, this);
1706                 else {
1707                     // If we don't need to move the input poistion, and the pattern has a fixed size
1708                     // (in which case we omit the store of the start index until the pattern has matched)
1709                     // then we can just link the backtrack out of the last alternative straight to the
1710                     // head of the first alternative.
1711                     if (m_pattern.m_body->m_hasFixedSize
1712                         && (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize)
1713                         && (alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize == 1))
1714                         m_backtrackingState.linkTo(beginOp->m_reentry, this);
1715                     else {
1716                         // We need to generate a trampoline of code to execute before looping back
1717                         // around to the first alternative.
1718                         m_backtrackingState.link(this);
1719
1720                         // If the pattern size is not fixed, then store the start index, for use if we match.
1721                         if (!m_pattern.m_body->m_hasFixedSize) {
1722                             if (alternative->m_minimumSize == 1)
1723                                 store32(index, Address(output));
1724                             else {
1725                                 move(index, regT0);
1726                                 if (alternative->m_minimumSize)
1727                                     sub32(Imm32(alternative->m_minimumSize - 1), regT0);
1728                                 else
1729                                     add32(Imm32(1), regT0);
1730                                 store32(regT0, Address(output));
1731                             }
1732                         }
1733
1734                         // Generate code to loop. Check whether the last alternative is longer than the
1735                         // first (e.g. /a|xy/ or /a|xyz/).
1736                         if (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize) {
1737                             // We want to loop, and increment input position. If the delta is 1, it is
1738                             // already correctly incremented, if more than one then decrement as appropriate.
1739                             unsigned delta = alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize;
1740                             ASSERT(delta);
1741                             if (delta != 1)
1742                                 sub32(Imm32(delta - 1), index);
1743                             jump(beginOp->m_reentry);
1744                         } else {
1745                             // If the first alternative has minimum size 0xFFFFFFFFu, then there cannot
1746                             // be sufficent input available to handle this, so just fall through.
1747                             unsigned delta = beginOp->m_alternative->m_minimumSize - alternative->m_minimumSize;
1748                             if (delta != 0xFFFFFFFFu) {
1749                                 // We need to check input because we are incrementing the input.
1750                                 add32(Imm32(delta + 1), index);
1751                                 checkInput().linkTo(beginOp->m_reentry, this);
1752                             }
1753                         }
1754                     }
1755                 }
1756
1757                 // We can reach this point in the code in two ways:
1758                 //  - Fallthrough from the code above (a repeating alternative backtracked out of its
1759                 //    last alternative, and did not have sufficent input to run the first).
1760                 //  - We will loop back up to the following label when a releating alternative loops,
1761                 //    following a failed input check.
1762                 //
1763                 // Either way, we have just failed the input check for the first alternative.
1764                 Label firstInputCheckFailed(this);
1765
1766                 // Generate code to handle input check failures from alternatives except the last.
1767                 // prevOp is the alternative we're handling a bail out from (initially Begin), and
1768                 // nextOp is the alternative we will be attempting to reenter into.
1769                 // 
1770                 // We will link input check failures from the forwards matching path back to the code
1771                 // that can handle them.
1772                 YarrOp* prevOp = beginOp;
1773                 YarrOp* nextOp = &m_ops[beginOp->m_nextOp];
1774                 while (nextOp->m_op != OpBodyAlternativeEnd) {
1775                     prevOp->m_jumps.link(this);
1776
1777                     // We only get here if an input check fails, it is only worth checking again
1778                     // if the next alternative has a minimum size less than the last.
1779                     if (prevOp->m_alternative->m_minimumSize > nextOp->m_alternative->m_minimumSize) {
1780                         // FIXME: if we added an extra label to YarrOp, we could avoid needing to
1781                         // subtract delta back out, and reduce this code. Should performance test
1782                         // the benefit of this.
1783                         unsigned delta = prevOp->m_alternative->m_minimumSize - nextOp->m_alternative->m_minimumSize;
1784                         sub32(Imm32(delta), index);
1785                         Jump fail = jumpIfNoAvailableInput();
1786                         add32(Imm32(delta), index);
1787                         jump(nextOp->m_reentry);
1788                         fail.link(this);
1789                     } else if (prevOp->m_alternative->m_minimumSize < nextOp->m_alternative->m_minimumSize)
1790                         add32(Imm32(nextOp->m_alternative->m_minimumSize - prevOp->m_alternative->m_minimumSize), index);
1791                     prevOp = nextOp;
1792                     nextOp = &m_ops[nextOp->m_nextOp];
1793                 }
1794
1795                 // We fall through to here if there is insufficient input to run the last alternative.
1796
1797                 // If there is insufficient input to run the last alternative, then for 'once through'
1798                 // alternatives we are done - just jump back up into the forwards matching path at the End.
1799                 if (onceThrough) {
1800                     op.m_jumps.linkTo(endOp.m_reentry, this);
1801                     jump(endOp.m_reentry);
1802                     break;
1803                 }
1804
1805                 // For repeating alternatives, link any input check failure from the last alternative to
1806                 // this point.
1807                 op.m_jumps.link(this);
1808
1809                 bool needsToUpdateMatchStart = !m_pattern.m_body->m_hasFixedSize;
1810
1811                 // Check for cases where input position is already incremented by 1 for the last
1812                 // alternative (this is particularly useful where the minimum size of the body
1813                 // disjunction is 0, e.g. /a*|b/).
1814                 if (needsToUpdateMatchStart && alternative->m_minimumSize == 1) {
1815                     // index is already incremented by 1, so just store it now!
1816                     store32(index, Address(output));
1817                     needsToUpdateMatchStart = false;
1818                 }
1819
1820                 // Check whether there is sufficient input to loop. Increment the input position by
1821                 // one, and check. Also add in the minimum disjunction size before checking - there
1822                 // is no point in looping if we're just going to fail all the input checks around
1823                 // the next iteration.
1824                 ASSERT(alternative->m_minimumSize >= m_pattern.m_body->m_minimumSize);
1825                 if (alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) {
1826                     // If the last alternative had the same minimum size as the disjunction,
1827                     // just simply increment input pos by 1, no adjustment based on minimum size.
1828                     add32(Imm32(1), index);
1829                 } else {
1830                     // If the minumum for the last alternative was one greater than than that
1831                     // for the disjunction, we're already progressed by 1, nothing to do!
1832                     unsigned delta = (alternative->m_minimumSize - m_pattern.m_body->m_minimumSize) - 1;
1833                     if (delta)
1834                         sub32(Imm32(delta), index);
1835                 }
1836                 Jump matchFailed = jumpIfNoAvailableInput();
1837
1838                 if (needsToUpdateMatchStart) {
1839                     if (!m_pattern.m_body->m_minimumSize)
1840                         store32(index, Address(output));
1841                     else {
1842                         move(index, regT0);
1843                         sub32(Imm32(m_pattern.m_body->m_minimumSize), regT0);
1844                         store32(regT0, Address(output));
1845                     }
1846                 }
1847
1848                 // Calculate how much more input the first alternative requires than the minimum
1849                 // for the body as a whole. If no more is needed then we dont need an additional
1850                 // input check here - jump straight back up to the start of the first alternative.
1851                 if (beginOp->m_alternative->m_minimumSize == m_pattern.m_body->m_minimumSize)
1852                     jump(beginOp->m_reentry);
1853                 else {
1854                     if (beginOp->m_alternative->m_minimumSize > m_pattern.m_body->m_minimumSize)
1855                         add32(Imm32(beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize), index);
1856                     else
1857                         sub32(Imm32(m_pattern.m_body->m_minimumSize - beginOp->m_alternative->m_minimumSize), index);
1858                     checkInput().linkTo(beginOp->m_reentry, this);
1859                     jump(firstInputCheckFailed);
1860                 }
1861
1862                 // We jump to here if we iterate to the point that there is insufficient input to
1863                 // run any matches, and need to return a failure state from JIT code.
1864                 matchFailed.link(this);
1865
1866                 if (m_pattern.m_body->m_callFrameSize)
1867                     addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1868                 move(TrustedImm32(-1), returnRegister);
1869                 generateReturn();
1870                 break;
1871             }
1872             case OpBodyAlternativeEnd: {
1873                 // We should never backtrack back into a body disjunction.
1874                 ASSERT(m_backtrackingState.isEmpty());
1875
1876                 PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
1877                 m_checked += priorAlternative->m_minimumSize;
1878                 break;
1879             }
1880
1881             // OpSimpleNestedAlternativeBegin/Next/End
1882             // OpNestedAlternativeBegin/Next/End
1883             //
1884             // Generate code for when we backtrack back out of an alternative into
1885             // a Begin or Next node, or when the entry input count check fails. If
1886             // there are more alternatives we need to jump to the next alternative,
1887             // if not we backtrack back out of the current set of parentheses.
1888             //
1889             // In the case of non-simple nested assertions we need to also link the
1890             // 'return address' appropriately to backtrack back out into the correct
1891             // alternative.
1892             case OpSimpleNestedAlternativeBegin:
1893             case OpSimpleNestedAlternativeNext:
1894             case OpNestedAlternativeBegin:
1895             case OpNestedAlternativeNext: {
1896                 YarrOp& nextOp = m_ops[op.m_nextOp];
1897                 bool isBegin = op.m_previousOp == notFound;
1898                 bool isLastAlternative = nextOp.m_nextOp == notFound;
1899                 ASSERT(isBegin == (op.m_op == OpSimpleNestedAlternativeBegin || op.m_op == OpNestedAlternativeBegin));
1900                 ASSERT(isLastAlternative == (nextOp.m_op == OpSimpleNestedAlternativeEnd || nextOp.m_op == OpNestedAlternativeEnd));
1901
1902                 // Treat an input check failure the same as a failed match.
1903                 m_backtrackingState.append(op.m_jumps);
1904
1905                 // Set the backtracks to jump to the appropriate place. We may need
1906                 // to link the backtracks in one of three different way depending on
1907                 // the type of alternative we are dealing with:
1908                 //  - A single alternative, with no simplings.
1909                 //  - The last alternative of a set of two or more.
1910                 //  - An alternative other than the last of a set of two or more.
1911                 //
1912                 // In the case of a single alternative on its own, we don't need to
1913                 // jump anywhere - if the alternative fails to match we can just
1914                 // continue to backtrack out of the parentheses without jumping.
1915                 //
1916                 // In the case of the last alternative in a set of more than one, we
1917                 // need to jump to return back out to the beginning. We'll do so by
1918                 // adding a jump to the End node's m_jumps list, and linking this
1919                 // when we come to generate the Begin node. For alternatives other
1920                 // than the last, we need to jump to the next alternative.
1921                 //
1922                 // If the alternative had adjusted the input position we must link
1923                 // backtracking to here, correct, and then jump on. If not we can
1924                 // link the backtracks directly to their destination.
1925                 if (op.m_checkAdjust) {
1926                     // Handle the cases where we need to link the backtracks here.
1927                     m_backtrackingState.link(this);
1928                     sub32(Imm32(op.m_checkAdjust), index);
1929                     if (!isLastAlternative) {
1930                         // An alternative that is not the last should jump to its successor.
1931                         jump(nextOp.m_reentry);
1932                     } else if (!isBegin) {
1933                         // The last of more than one alternatives must jump back to the begnning.
1934                         nextOp.m_jumps.append(jump());
1935                     } else {
1936                         // A single alternative on its own can fall through.
1937                         m_backtrackingState.fallthrough();
1938                     }
1939                 } else {
1940                     // Handle the cases where we can link the backtracks directly to their destinations.
1941                     if (!isLastAlternative) {
1942                         // An alternative that is not the last should jump to its successor.
1943                         m_backtrackingState.linkTo(nextOp.m_reentry, this);
1944                     } else if (!isBegin) {
1945                         // The last of more than one alternatives must jump back to the begnning.
1946                         m_backtrackingState.takeBacktracksToJumpList(nextOp.m_jumps, this);
1947                     }
1948                     // In the case of a single alternative on its own do nothing - it can fall through.
1949                 }
1950
1951                 // At this point we've handled the backtracking back into this node.
1952                 // Now link any backtracks that need to jump to here.
1953
1954                 // For non-simple alternatives, link the alternative's 'return address'
1955                 // so that we backtrack back out into the previous alternative.
1956                 if (op.m_op == OpNestedAlternativeNext)
1957                     m_backtrackingState.append(op.m_returnAddress);
1958
1959                 // If there is more than one alternative, then the last alternative will
1960                 // have planted a jump to be linked to the end. This jump was added to the
1961                 // End node's m_jumps list. If we are back at the beginning, link it here.
1962                 if (isBegin) {
1963                     YarrOp* endOp = &m_ops[op.m_nextOp];
1964                     while (endOp->m_nextOp != notFound) {
1965                         ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext);
1966                         endOp = &m_ops[endOp->m_nextOp];
1967                     }
1968                     ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd);
1969                     m_backtrackingState.append(endOp->m_jumps);
1970                 }
1971
1972                 if (!isBegin) {
1973                     YarrOp& lastOp = m_ops[op.m_previousOp];
1974                     m_checked += lastOp.m_checkAdjust;
1975                 }
1976                 m_checked -= op.m_checkAdjust;
1977                 break;
1978             }
1979             case OpSimpleNestedAlternativeEnd:
1980             case OpNestedAlternativeEnd: {
1981                 PatternTerm* term = op.m_term;
1982
1983                 // If we backtrack into the end of a simple subpattern do nothing;
1984                 // just continue through into the last alternative. If we backtrack
1985                 // into the end of a non-simple set of alterntives we need to jump
1986                 // to the backtracking return address set up during generation.
1987                 if (op.m_op == OpNestedAlternativeEnd) {
1988                     m_backtrackingState.link(this);
1989
1990                     // Plant a jump to the return address.
1991                     unsigned parenthesesFrameLocation = term->frameLocation;
1992                     unsigned alternativeFrameLocation = parenthesesFrameLocation;
1993                     if (term->quantityType != QuantifierFixedCount)
1994                         alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1995                     loadFromFrameAndJump(alternativeFrameLocation);
1996
1997                     // Link the DataLabelPtr associated with the end of the last
1998                     // alternative to this point.
1999                     m_backtrackingState.append(op.m_returnAddress);
2000                 }
2001
2002                 YarrOp& lastOp = m_ops[op.m_previousOp];
2003                 m_checked += lastOp.m_checkAdjust;
2004                 break;
2005             }
2006
2007             // OpParenthesesSubpatternOnceBegin/End
2008             //
2009             // When we are backtracking back out of a capturing subpattern we need
2010             // to clear the start index in the matches output array, to record that
2011             // this subpattern has not been captured.
2012             //
2013             // When backtracking back out of a Greedy quantified subpattern we need
2014             // to catch this, and try running the remainder of the alternative after
2015             // the subpattern again, skipping the parentheses.
2016             //
2017             // Upon backtracking back into a quantified set of parentheses we need to
2018             // check whether we were currently skipping the subpattern. If not, we
2019             // can backtrack into them, if we were we need to either backtrack back
2020             // out of the start of the parentheses, or jump back to the forwards
2021             // matching start, depending of whether the match is Greedy or NonGreedy.
2022             case OpParenthesesSubpatternOnceBegin: {
2023                 PatternTerm* term = op.m_term;
2024                 ASSERT(term->quantityCount == 1);
2025
2026                 // We only need to backtrack to thispoint if capturing or greedy.
2027                 if (term->capture() || term->quantityType == QuantifierGreedy) {
2028                     m_backtrackingState.link(this);
2029
2030                     // If capturing, clear the capture (we only need to reset start).
2031                     if (term->capture())
2032                         store32(TrustedImm32(-1), Address(output, (term->parentheses.subpatternId << 1) * sizeof(int)));
2033
2034                     // If Greedy, jump to the end.
2035                     if (term->quantityType == QuantifierGreedy) {
2036                         // Clear the flag in the stackframe indicating we ran through the subpattern.
2037                         unsigned parenthesesFrameLocation = term->frameLocation;
2038                         storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
2039                         // Jump to after the parentheses, skipping the subpattern.
2040                         jump(m_ops[op.m_nextOp].m_reentry);
2041                         // A backtrack from after the parentheses, when skipping the subpattern,
2042                         // will jump back to here.
2043                         op.m_jumps.link(this);
2044                     }
2045
2046                     m_backtrackingState.fallthrough();
2047                 }
2048                 break;
2049             }
2050             case OpParenthesesSubpatternOnceEnd: {
2051                 PatternTerm* term = op.m_term;
2052
2053                 if (term->quantityType != QuantifierFixedCount) {
2054                     m_backtrackingState.link(this);
2055
2056                     // Check whether we should backtrack back into the parentheses, or if we
2057                     // are currently in a state where we had skipped over the subpattern
2058                     // (in which case the flag value on the stack will be -1).
2059                     unsigned parenthesesFrameLocation = term->frameLocation;
2060                     Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, parenthesesFrameLocation * sizeof(void*)), TrustedImm32(-1));
2061
2062                     if (term->quantityType == QuantifierGreedy) {
2063                         // For Greedy parentheses, we skip after having already tried going
2064                         // through the subpattern, so if we get here we're done.
2065                         YarrOp& beginOp = m_ops[op.m_previousOp];
2066                         beginOp.m_jumps.append(hadSkipped);
2067                     } else {
2068                         // For NonGreedy parentheses, we try skipping the subpattern first,
2069                         // so if we get here we need to try running through the subpattern
2070                         // next. Jump back to the start of the parentheses in the forwards
2071                         // matching path.
2072                         ASSERT(term->quantityType == QuantifierNonGreedy);
2073                         YarrOp& beginOp = m_ops[op.m_previousOp];
2074                         hadSkipped.linkTo(beginOp.m_reentry, this);
2075                     }
2076
2077                     m_backtrackingState.fallthrough();
2078                 }
2079
2080                 m_backtrackingState.append(op.m_jumps);
2081                 break;
2082             }
2083
2084             // OpParenthesesSubpatternTerminalBegin/End
2085             //
2086             // Terminal subpatterns will always match - there is nothing after them to
2087             // force a backtrack, and they have a minimum count of 0, and as such will
2088             // always produce an acceptable result.
2089             case OpParenthesesSubpatternTerminalBegin: {
2090                 // We will backtrack to this point once the subpattern cannot match any
2091                 // more. Since no match is accepted as a successful match (we are Greedy
2092                 // quantified with a minimum of zero) jump back to the forwards matching
2093                 // path at the end.
2094                 YarrOp& endOp = m_ops[op.m_nextOp];
2095                 m_backtrackingState.linkTo(endOp.m_reentry, this);
2096                 break;
2097             }
2098             case OpParenthesesSubpatternTerminalEnd:
2099                 // We should never be backtracking to here (hence the 'terminal' in the name).
2100                 ASSERT(m_backtrackingState.isEmpty());
2101                 m_backtrackingState.append(op.m_jumps);
2102                 break;
2103
2104             // OpParentheticalAssertionBegin/End
2105             case OpParentheticalAssertionBegin: {
2106                 PatternTerm* term = op.m_term;
2107                 YarrOp& endOp = m_ops[op.m_nextOp];
2108
2109                 // We need to handle the backtracks upon backtracking back out
2110                 // of a parenthetical assertion if either we need to correct
2111                 // the input index, or the assertion was inverted.
2112                 if (op.m_checkAdjust || term->invert()) {
2113                      m_backtrackingState.link(this);
2114
2115                     if (op.m_checkAdjust)
2116                         add32(Imm32(op.m_checkAdjust), index);
2117
2118                     // In an inverted assertion failure to match the subpattern
2119                     // is treated as a successful match - jump to the end of the
2120                     // subpattern. We already have adjusted the input position
2121                     // back to that before the assertion, which is correct.
2122                     if (term->invert())
2123                         jump(endOp.m_reentry);
2124
2125                     m_backtrackingState.fallthrough();
2126                 }
2127
2128                 // The End node's jump list will contain any backtracks into
2129                 // the end of the assertion. Also, if inverted, we will have
2130                 // added the failure caused by a successful match to this.
2131                 m_backtrackingState.append(endOp.m_jumps);
2132
2133                 m_checked += op.m_checkAdjust;
2134                 break;
2135             }
2136             case OpParentheticalAssertionEnd: {
2137                 // FIXME: We should really be clearing any nested subpattern
2138                 // matches on bailing out from after the pattern. Firefox has
2139                 // this bug too (presumably because they use YARR!)
2140
2141                 // Never backtrack into an assertion; later failures bail to before the begin.
2142                 m_backtrackingState.takeBacktracksToJumpList(op.m_jumps, this);
2143
2144                 YarrOp& lastOp = m_ops[op.m_previousOp];
2145                 m_checked -= lastOp.m_checkAdjust;
2146                 break;
2147             }
2148
2149             case OpMatchFailed:
2150                 break;
2151             }
2152
2153         } while (opIndex);
2154     }
2155
2156     // Compilation methods:
2157     // ====================
2158
2159     // opCompileParenthesesSubpattern
2160     // Emits ops for a subpattern (set of parentheses). These consist
2161     // of a set of alternatives wrapped in an outer set of nodes for
2162     // the parentheses.
2163     // Supported types of parentheses are 'Once' (quantityCount == 1)
2164     // and 'Terminal' (non-capturing parentheses quantified as greedy
2165     // and infinite).
2166     // Alternatives will use the 'Simple' set of ops if either the
2167     // subpattern is terminal (in which case we will never need to
2168     // backtrack), or if the subpattern only contains one alternative.
2169     void opCompileParenthesesSubpattern(PatternTerm* term)
2170     {
2171         YarrOpCode parenthesesBeginOpCode;
2172         YarrOpCode parenthesesEndOpCode;
2173         YarrOpCode alternativeBeginOpCode = OpSimpleNestedAlternativeBegin;
2174         YarrOpCode alternativeNextOpCode = OpSimpleNestedAlternativeNext;
2175         YarrOpCode alternativeEndOpCode = OpSimpleNestedAlternativeEnd;
2176
2177         // We can currently only compile quantity 1 subpatterns that are
2178         // not copies. We generate a copy in the case of a range quantifier,
2179         // e.g. /(?:x){3,9}/, or /(?:x)+/ (These are effectively expanded to
2180         // /(?:x){3,3}(?:x){0,6}/ and /(?:x)(?:x)*/ repectively). The problem
2181         // comes where the subpattern is capturing, in which case we would
2182         // need to restore the capture from the first subpattern upon a
2183         // failure in the second.
2184         if (term->quantityCount == 1 && !term->parentheses.isCopy) {
2185             // Select the 'Once' nodes.
2186             parenthesesBeginOpCode = OpParenthesesSubpatternOnceBegin;
2187             parenthesesEndOpCode = OpParenthesesSubpatternOnceEnd;
2188
2189             // If there is more than one alternative we cannot use the 'simple' nodes.
2190             if (term->parentheses.disjunction->m_alternatives.size() != 1) {
2191                 alternativeBeginOpCode = OpNestedAlternativeBegin;
2192                 alternativeNextOpCode = OpNestedAlternativeNext;
2193                 alternativeEndOpCode = OpNestedAlternativeEnd;
2194             }
2195         } else if (term->parentheses.isTerminal) {
2196             // Select the 'Terminal' nodes.
2197             parenthesesBeginOpCode = OpParenthesesSubpatternTerminalBegin;
2198             parenthesesEndOpCode = OpParenthesesSubpatternTerminalEnd;
2199         } else {
2200             // This subpattern is not supported by the JIT.
2201             m_shouldFallBack = true;
2202             return;
2203         }
2204
2205         size_t parenBegin = m_ops.size();
2206         m_ops.append(parenthesesBeginOpCode);
2207
2208         m_ops.append(alternativeBeginOpCode);
2209         m_ops.last().m_previousOp = notFound;
2210         m_ops.last().m_term = term;
2211         Vector<PatternAlternative*>& alternatives =  term->parentheses.disjunction->m_alternatives;
2212         for (unsigned i = 0; i < alternatives.size(); ++i) {
2213             size_t lastOpIndex = m_ops.size() - 1;
2214
2215             PatternAlternative* nestedAlternative = alternatives[i];
2216             opCompileAlternative(nestedAlternative);
2217
2218             size_t thisOpIndex = m_ops.size();
2219             m_ops.append(YarrOp(alternativeNextOpCode));
2220
2221             YarrOp& lastOp = m_ops[lastOpIndex];
2222             YarrOp& thisOp = m_ops[thisOpIndex];
2223
2224             lastOp.m_alternative = nestedAlternative;
2225             lastOp.m_nextOp = thisOpIndex;
2226             thisOp.m_previousOp = lastOpIndex;
2227             thisOp.m_term = term;
2228         }
2229         YarrOp& lastOp = m_ops.last();
2230         ASSERT(lastOp.m_op == alternativeNextOpCode);
2231         lastOp.m_op = alternativeEndOpCode;
2232         lastOp.m_alternative = 0;
2233         lastOp.m_nextOp = notFound;
2234
2235         size_t parenEnd = m_ops.size();
2236         m_ops.append(parenthesesEndOpCode);
2237
2238         m_ops[parenBegin].m_term = term;
2239         m_ops[parenBegin].m_previousOp = notFound;
2240         m_ops[parenBegin].m_nextOp = parenEnd;
2241         m_ops[parenEnd].m_term = term;
2242         m_ops[parenEnd].m_previousOp = parenBegin;
2243         m_ops[parenEnd].m_nextOp = notFound;
2244     }
2245
2246     // opCompileParentheticalAssertion
2247     // Emits ops for a parenthetical assertion. These consist of an
2248     // OpSimpleNestedAlternativeBegin/Next/End set of nodes wrapping
2249     // the alternatives, with these wrapped by an outer pair of
2250     // OpParentheticalAssertionBegin/End nodes.
2251     // We can always use the OpSimpleNestedAlternative nodes in the
2252     // case of parenthetical assertions since these only ever match
2253     // once, and will never backtrack back into the assertion.
2254     void opCompileParentheticalAssertion(PatternTerm* term)
2255     {
2256         size_t parenBegin = m_ops.size();
2257         m_ops.append(OpParentheticalAssertionBegin);
2258
2259         m_ops.append(OpSimpleNestedAlternativeBegin);
2260         m_ops.last().m_previousOp = notFound;
2261         m_ops.last().m_term = term;
2262         Vector<PatternAlternative*>& alternatives =  term->parentheses.disjunction->m_alternatives;
2263         for (unsigned i = 0; i < alternatives.size(); ++i) {
2264             size_t lastOpIndex = m_ops.size() - 1;
2265
2266             PatternAlternative* nestedAlternative = alternatives[i];
2267             opCompileAlternative(nestedAlternative);
2268
2269             size_t thisOpIndex = m_ops.size();
2270             m_ops.append(YarrOp(OpSimpleNestedAlternativeNext));
2271
2272             YarrOp& lastOp = m_ops[lastOpIndex];
2273             YarrOp& thisOp = m_ops[thisOpIndex];
2274
2275             lastOp.m_alternative = nestedAlternative;
2276             lastOp.m_nextOp = thisOpIndex;
2277             thisOp.m_previousOp = lastOpIndex;
2278             thisOp.m_term = term;
2279         }
2280         YarrOp& lastOp = m_ops.last();
2281         ASSERT(lastOp.m_op == OpSimpleNestedAlternativeNext);
2282         lastOp.m_op = OpSimpleNestedAlternativeEnd;
2283         lastOp.m_alternative = 0;
2284         lastOp.m_nextOp = notFound;
2285
2286         size_t parenEnd = m_ops.size();
2287         m_ops.append(OpParentheticalAssertionEnd);
2288
2289         m_ops[parenBegin].m_term = term;
2290         m_ops[parenBegin].m_previousOp = notFound;
2291         m_ops[parenBegin].m_nextOp = parenEnd;
2292         m_ops[parenEnd].m_term = term;
2293         m_ops[parenEnd].m_previousOp = parenBegin;
2294         m_ops[parenEnd].m_nextOp = notFound;
2295     }
2296
2297     // opCompileAlternative
2298     // Called to emit nodes for all terms in an alternative.
2299     void opCompileAlternative(PatternAlternative* alternative)
2300     {
2301         optimizeAlternative(alternative);
2302
2303         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
2304             PatternTerm* term = &alternative->m_terms[i];
2305
2306             switch (term->type) {
2307             case PatternTerm::TypeParenthesesSubpattern:
2308                 opCompileParenthesesSubpattern(term);
2309                 break;
2310
2311             case PatternTerm::TypeParentheticalAssertion:
2312                 opCompileParentheticalAssertion(term);
2313                 break;
2314
2315             default:
2316                 m_ops.append(term);
2317             }
2318         }
2319     }
2320
2321     // opCompileBody
2322     // This method compiles the body disjunction of the regular expression.
2323     // The body consists of two sets of alternatives - zero or more 'once
2324     // through' (BOL anchored) alternatives, followed by zero or more
2325     // repeated alternatives.
2326     // For each of these two sets of alteratives, if not empty they will be
2327     // wrapped in a set of OpBodyAlternativeBegin/Next/End nodes (with the
2328     // 'begin' node referencing the first alternative, and 'next' nodes
2329     // referencing any further alternatives. The begin/next/end nodes are
2330     // linked together in a doubly linked list. In the case of repeating
2331     // alternatives, the end node is also linked back to the beginning.
2332     // If no repeating alternatives exist, then a OpMatchFailed node exists
2333     // to return the failing result.
2334     void opCompileBody(PatternDisjunction* disjunction)
2335     {
2336         Vector<PatternAlternative*>& alternatives =  disjunction->m_alternatives;
2337         size_t currentAlternativeIndex = 0;
2338
2339         // Emit the 'once through' alternatives.
2340         if (alternatives.size() && alternatives[0]->onceThrough()) {
2341             m_ops.append(YarrOp(OpBodyAlternativeBegin));
2342             m_ops.last().m_previousOp = notFound;
2343
2344             do {
2345                 size_t lastOpIndex = m_ops.size() - 1;
2346                 PatternAlternative* alternative = alternatives[currentAlternativeIndex];
2347                 opCompileAlternative(alternative);
2348
2349                 size_t thisOpIndex = m_ops.size();
2350                 m_ops.append(YarrOp(OpBodyAlternativeNext));
2351
2352                 YarrOp& lastOp = m_ops[lastOpIndex];
2353                 YarrOp& thisOp = m_ops[thisOpIndex];
2354
2355                 lastOp.m_alternative = alternative;
2356                 lastOp.m_nextOp = thisOpIndex;
2357                 thisOp.m_previousOp = lastOpIndex;
2358                 
2359                 ++currentAlternativeIndex;
2360             } while (currentAlternativeIndex < alternatives.size() && alternatives[currentAlternativeIndex]->onceThrough());
2361
2362             YarrOp& lastOp = m_ops.last();
2363
2364             ASSERT(lastOp.m_op == OpBodyAlternativeNext);
2365             lastOp.m_op = OpBodyAlternativeEnd;
2366             lastOp.m_alternative = 0;
2367             lastOp.m_nextOp = notFound;
2368         }
2369
2370         if (currentAlternativeIndex == alternatives.size()) {
2371             m_ops.append(YarrOp(OpMatchFailed));
2372             return;
2373         }
2374
2375         // Emit the repeated alternatives.
2376         size_t repeatLoop = m_ops.size();
2377         m_ops.append(YarrOp(OpBodyAlternativeBegin));
2378         m_ops.last().m_previousOp = notFound;
2379         do {
2380             size_t lastOpIndex = m_ops.size() - 1;
2381             PatternAlternative* alternative = alternatives[currentAlternativeIndex];
2382             ASSERT(!alternative->onceThrough());
2383             opCompileAlternative(alternative);
2384
2385             size_t thisOpIndex = m_ops.size();
2386             m_ops.append(YarrOp(OpBodyAlternativeNext));
2387
2388             YarrOp& lastOp = m_ops[lastOpIndex];
2389             YarrOp& thisOp = m_ops[thisOpIndex];
2390
2391             lastOp.m_alternative = alternative;
2392             lastOp.m_nextOp = thisOpIndex;
2393             thisOp.m_previousOp = lastOpIndex;
2394             
2395             ++currentAlternativeIndex;
2396         } while (currentAlternativeIndex < alternatives.size());
2397         YarrOp& lastOp = m_ops.last();
2398         ASSERT(lastOp.m_op == OpBodyAlternativeNext);
2399         lastOp.m_op = OpBodyAlternativeEnd;
2400         lastOp.m_alternative = 0;
2401         lastOp.m_nextOp = repeatLoop;
2402     }
2403
2404     void generateEnter()
2405     {
2406 #if CPU(X86_64)
2407         push(X86Registers::ebp);
2408         move(stackPointerRegister, X86Registers::ebp);
2409         push(X86Registers::ebx);
2410 #elif CPU(X86)
2411         push(X86Registers::ebp);
2412         move(stackPointerRegister, X86Registers::ebp);
2413         // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
2414         push(X86Registers::ebx);
2415         push(X86Registers::edi);
2416         push(X86Registers::esi);
2417         // load output into edi (2 = saved ebp + return address).
2418     #if COMPILER(MSVC)
2419         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
2420         loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
2421         loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
2422         loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
2423     #else
2424         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
2425     #endif
2426 #elif CPU(ARM)
2427         push(ARMRegisters::r4);
2428         push(ARMRegisters::r5);
2429         push(ARMRegisters::r6);
2430 #if CPU(ARM_TRADITIONAL)
2431         push(ARMRegisters::r8); // scratch register
2432 #endif
2433         move(ARMRegisters::r3, output);
2434 #elif CPU(SH4)
2435         push(SH4Registers::r11);
2436         push(SH4Registers::r13);
2437 #elif CPU(MIPS)
2438         // Do nothing.
2439 #endif
2440     }
2441
2442     void generateReturn()
2443     {
2444 #if CPU(X86_64)
2445         pop(X86Registers::ebx);
2446         pop(X86Registers::ebp);
2447 #elif CPU(X86)
2448         pop(X86Registers::esi);
2449         pop(X86Registers::edi);
2450         pop(X86Registers::ebx);
2451         pop(X86Registers::ebp);
2452 #elif CPU(ARM)
2453 #if CPU(ARM_TRADITIONAL)
2454         pop(ARMRegisters::r8); // scratch register
2455 #endif
2456         pop(ARMRegisters::r6);
2457         pop(ARMRegisters::r5);
2458         pop(ARMRegisters::r4);
2459 #elif CPU(SH4)
2460         pop(SH4Registers::r13);
2461         pop(SH4Registers::r11);
2462 #elif CPU(MIPS)
2463         // Do nothing
2464 #endif
2465         ret();
2466     }
2467
2468 public:
2469     YarrGenerator(YarrPattern& pattern, YarrCharSize charSize)
2470         : m_pattern(pattern)
2471         , m_charSize(charSize)
2472         , m_charScale(m_charSize == Char8 ? TimesOne: TimesTwo)
2473         , m_shouldFallBack(false)
2474         , m_checked(0)
2475     {
2476     }
2477
2478     void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject)
2479     {
2480         generateEnter();
2481
2482         if (!m_pattern.m_body->m_hasFixedSize)
2483             store32(index, Address(output));
2484
2485         if (m_pattern.m_body->m_callFrameSize)
2486             subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
2487
2488         // Compile the pattern to the internal 'YarrOp' representation.
2489         opCompileBody(m_pattern.m_body);
2490
2491         // If we encountered anything we can't handle in the JIT code
2492         // (e.g. backreferences) then return early.
2493         if (m_shouldFallBack) {
2494             jitObject.setFallBack(true);
2495             return;
2496         }
2497
2498         generate();
2499         backtrack();
2500
2501         // Link & finalize the code.
2502         LinkBuffer linkBuffer(*globalData, this);
2503         m_backtrackingState.linkDataLabels(linkBuffer);
2504         if (m_charSize == Char8)
2505             jitObject.set8BitCode(linkBuffer.finalizeCode());
2506         else
2507             jitObject.set16BitCode(linkBuffer.finalizeCode());
2508         jitObject.setFallBack(m_shouldFallBack);
2509     }
2510
2511 private:
2512     YarrPattern& m_pattern;
2513
2514     YarrCharSize m_charSize;
2515
2516     Scale m_charScale;
2517
2518     // Used to detect regular expression constructs that are not currently
2519     // supported in the JIT; fall back to the interpreter when this is detected.
2520     bool m_shouldFallBack;
2521
2522     // The regular expression expressed as a linear sequence of operations.
2523     Vector<YarrOp, 128> m_ops;
2524
2525     // This records the current input offset being applied due to the current
2526     // set of alternatives we are nested within. E.g. when matching the
2527     // character 'b' within the regular expression /abc/, we will know that
2528     // the minimum size for the alternative is 3, checked upon entry to the
2529     // alternative, and that 'b' is at offset 1 from the start, and as such
2530     // when matching 'b' we need to apply an offset of -2 to the load.
2531     //
2532     // FIXME: This should go away. Rather than tracking this value throughout
2533     // code generation, we should gather this information up front & store it
2534     // on the YarrOp structure.
2535     int m_checked;
2536
2537     // This class records state whilst generating the backtracking path of code.
2538     BacktrackingState m_backtrackingState;
2539 };
2540
2541 void jitCompile(YarrPattern& pattern, YarrCharSize charSize, JSGlobalData* globalData, YarrCodeBlock& jitObject)
2542 {
2543     YarrGenerator(pattern, charSize).compile(globalData, jitObject);
2544 }
2545
2546 int execute(YarrCodeBlock& jitObject, const LChar* input, unsigned start, unsigned length, int* output)
2547 {
2548     return jitObject.execute(input, start, length, output);
2549 }
2550
2551 int execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output)
2552 {
2553     return jitObject.execute(input, start, length, output);
2554 }
2555
2556 }}
2557
2558 #endif