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