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