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