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