1/*
2 * Copyright (C) 2009 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "YarrJIT.h"
28
29#include "ASCIICType.h"
30#include "LinkBuffer.h"
31#include "Yarr.h"
32
33#if ENABLE(YARR_JIT)
34
35using namespace WTF;
36
37namespace JSC { namespace Yarr {
38
39class YarrGenerator : private MacroAssembler {
40    friend void jitCompile(JSGlobalData*, YarrCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);
41
42#if CPU(ARM)
43    static const RegisterID input = ARMRegisters::r0;
44    static const RegisterID index = ARMRegisters::r1;
45    static const RegisterID length = ARMRegisters::r2;
46    static const RegisterID output = ARMRegisters::r4;
47
48    static const RegisterID regT0 = ARMRegisters::r5;
49    static const RegisterID regT1 = ARMRegisters::r6;
50
51    static const RegisterID returnRegister = ARMRegisters::r0;
52#elif CPU(MIPS)
53    static const RegisterID input = MIPSRegisters::a0;
54    static const RegisterID index = MIPSRegisters::a1;
55    static const RegisterID length = MIPSRegisters::a2;
56    static const RegisterID output = MIPSRegisters::a3;
57
58    static const RegisterID regT0 = MIPSRegisters::t4;
59    static const RegisterID regT1 = MIPSRegisters::t5;
60
61    static const RegisterID returnRegister = MIPSRegisters::v0;
62#elif CPU(SH4)
63    static const RegisterID input = SH4Registers::r4;
64    static const RegisterID index = SH4Registers::r5;
65    static const RegisterID length = SH4Registers::r6;
66    static const RegisterID output = SH4Registers::r7;
67
68    static const RegisterID regT0 = SH4Registers::r0;
69    static const RegisterID regT1 = SH4Registers::r1;
70
71    static const RegisterID returnRegister = SH4Registers::r0;
72#elif CPU(X86)
73    static const RegisterID input = X86Registers::eax;
74    static const RegisterID index = X86Registers::edx;
75    static const RegisterID length = X86Registers::ecx;
76    static const RegisterID output = X86Registers::edi;
77
78    static const RegisterID regT0 = X86Registers::ebx;
79    static const RegisterID regT1 = X86Registers::esi;
80
81    static const RegisterID returnRegister = X86Registers::eax;
82#elif CPU(X86_64)
83    static const RegisterID input = X86Registers::edi;
84    static const RegisterID index = X86Registers::esi;
85    static const RegisterID length = X86Registers::edx;
86    static const RegisterID output = X86Registers::ecx;
87
88    static const RegisterID regT0 = X86Registers::eax;
89    static const RegisterID regT1 = X86Registers::ebx;
90
91    static const RegisterID returnRegister = X86Registers::eax;
92#endif
93
94    void optimizeAlternative(PatternAlternative* alternative)
95    {
96        if (!alternative->m_terms.size())
97            return;
98
99        for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {
100            PatternTerm& term = alternative->m_terms[i];
101            PatternTerm& nextTerm = alternative->m_terms[i + 1];
102
103            if ((term.type == PatternTerm::TypeCharacterClass)
104                && (term.quantityType == QuantifierFixedCount)
105                && (nextTerm.type == PatternTerm::TypePatternCharacter)
106                && (nextTerm.quantityType == QuantifierFixedCount)) {
107                PatternTerm termCopy = term;
108                alternative->m_terms[i] = nextTerm;
109                alternative->m_terms[i + 1] = termCopy;
110            }
111        }
112    }
113
114    void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
115    {
116        do {
117            // pick which range we're going to generate
118            int which = count >> 1;
119            char lo = ranges[which].begin;
120            char hi = ranges[which].end;
121
122            // check if there are any ranges or matches below lo.  If not, just jl to failure -
123            // if there is anything else to check, check that first, if it falls through jmp to failure.
124            if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
125                Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
126
127                // generate code for all ranges before this one
128                if (which)
129                    matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
130
131                while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
132                    matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
133                    ++*matchIndex;
134                }
135                failures.append(jump());
136
137                loOrAbove.link(this);
138            } else if (which) {
139                Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
140
141                matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
142                failures.append(jump());
143
144                loOrAbove.link(this);
145            } else
146                failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));
147
148            while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
149                ++*matchIndex;
150
151            matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
152            // fall through to here, the value is above hi.
153
154            // shuffle along & loop around if there are any more matches to handle.
155            unsigned next = which + 1;
156            ranges += next;
157            count -= next;
158        } while (count);
159    }
160
161    void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
162    {
163        if (charClass->m_table) {
164            ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table));
165            matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry));
166            return;
167        }
168        Jump unicodeFail;
169        if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
170            Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f));
171
172            if (charClass->m_matchesUnicode.size()) {
173                for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {
174                    UChar ch = charClass->m_matchesUnicode[i];
175                    matchDest.append(branch32(Equal, character, Imm32(ch)));
176                }
177            }
178
179            if (charClass->m_rangesUnicode.size()) {
180                for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {
181                    UChar lo = charClass->m_rangesUnicode[i].begin;
182                    UChar hi = charClass->m_rangesUnicode[i].end;
183
184                    Jump below = branch32(LessThan, character, Imm32(lo));
185                    matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
186                    below.link(this);
187                }
188            }
189
190            unicodeFail = jump();
191            isAscii.link(this);
192        }
193
194        if (charClass->m_ranges.size()) {
195            unsigned matchIndex = 0;
196            JumpList failures;
197            matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
198            while (matchIndex < charClass->m_matches.size())
199                matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
200
201            failures.link(this);
202        } else if (charClass->m_matches.size()) {
203            // optimization: gather 'a','A' etc back together, can mask & test once.
204            Vector<char> matchesAZaz;
205
206            for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {
207                char ch = charClass->m_matches[i];
208                if (m_pattern.m_ignoreCase) {
209                    if (isASCIILower(ch)) {
210                        matchesAZaz.append(ch);
211                        continue;
212                    }
213                    if (isASCIIUpper(ch))
214                        continue;
215                }
216                matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
217            }
218
219            if (unsigned countAZaz = matchesAZaz.size()) {
220                or32(TrustedImm32(32), character);
221                for (unsigned i = 0; i < countAZaz; ++i)
222                    matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));
223            }
224        }
225
226        if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())
227            unicodeFail.link(this);
228    }
229
230    // Jumps if input not available; will have (incorrectly) incremented already!
231    Jump jumpIfNoAvailableInput(unsigned countToCheck)
232    {
233        add32(Imm32(countToCheck), index);
234        return branch32(Above, index, length);
235    }
236
237    Jump jumpIfAvailableInput(unsigned countToCheck)
238    {
239        add32(Imm32(countToCheck), index);
240        return branch32(BelowOrEqual, index, length);
241    }
242
243    Jump checkInput()
244    {
245        return branch32(BelowOrEqual, index, length);
246    }
247
248    Jump atEndOfInput()
249    {
250        return branch32(Equal, index, length);
251    }
252
253    Jump notAtEndOfInput()
254    {
255        return branch32(NotEqual, index, length);
256    }
257
258    Jump jumpIfCharEquals(UChar ch, int inputPosition)
259    {
260        return branch16(Equal, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
261    }
262
263    Jump jumpIfCharNotEquals(UChar ch, int inputPosition)
264    {
265        return branch16(NotEqual, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
266    }
267
268    void readCharacter(int inputPosition, RegisterID reg)
269    {
270        load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
271    }
272
273    void storeToFrame(RegisterID reg, unsigned frameLocation)
274    {
275        poke(reg, frameLocation);
276    }
277
278    void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
279    {
280        poke(imm, frameLocation);
281    }
282
283    DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
284    {
285        return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
286    }
287
288    void loadFromFrame(unsigned frameLocation, RegisterID reg)
289    {
290        peek(reg, frameLocation);
291    }
292
293    void loadFromFrameAndJump(unsigned frameLocation)
294    {
295        jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
296    }
297
298    struct IndirectJumpEntry {
299        IndirectJumpEntry(int32_t stackOffset)
300            : m_stackOffset(stackOffset)
301        {
302        }
303
304        IndirectJumpEntry(int32_t stackOffset, Jump jump)
305            : m_stackOffset(stackOffset)
306        {
307            addJump(jump);
308        }
309
310        IndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
311        : m_stackOffset(stackOffset)
312        {
313            addDataLabel(dataLabel);
314        }
315
316        void addJump(Jump jump)
317        {
318            m_relJumps.append(jump);
319        }
320
321        void addDataLabel(DataLabelPtr dataLabel)
322        {
323            m_dataLabelPtrVector.append(dataLabel);
324        }
325
326        int32_t m_stackOffset;
327        JumpList m_relJumps;
328        Vector<DataLabelPtr, 16> m_dataLabelPtrVector;
329    };
330
331    struct AlternativeBacktrackRecord {
332        DataLabelPtr dataLabel;
333        Label backtrackLocation;
334
335        AlternativeBacktrackRecord(DataLabelPtr dataLabel, Label backtrackLocation)
336            : dataLabel(dataLabel)
337            , backtrackLocation(backtrackLocation)
338        {
339        }
340    };
341
342    struct ParenthesesTail;
343    struct TermGenerationState;
344
345    struct GenerationState {
346        typedef HashMap<int, IndirectJumpEntry*, WTF::IntHash<uint32_t>, UnsignedWithZeroKeyHashTraits<uint32_t> > IndirectJumpHashMap;
347
348        GenerationState()
349            : m_parenNestingLevel(0)
350        {
351        }
352
353        void addIndirectJumpEntry(int32_t stackOffset, Jump jump)
354        {
355            IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset);
356
357            ASSERT(stackOffset >= 0);
358
359            uint32_t offset = static_cast<uint32_t>(stackOffset);
360
361            if (result == m_indirectJumpMap.end())
362                m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, jump));
363            else
364                result->second->addJump(jump);
365        }
366
367        void addIndirectJumpEntry(int32_t stackOffset, JumpList jumps)
368        {
369            JumpList::JumpVector jumpVector = jumps.jumps();
370            size_t size = jumpVector.size();
371            for (size_t i = 0; i < size; ++i)
372                addIndirectJumpEntry(stackOffset, jumpVector[i]);
373
374            jumps.empty();
375        }
376
377        void addIndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
378        {
379            IndirectJumpHashMap::iterator result = m_indirectJumpMap.find(stackOffset);
380
381            ASSERT(stackOffset >= 0);
382
383            uint32_t offset = static_cast<uint32_t>(stackOffset);
384
385            if (result == m_indirectJumpMap.end())
386                m_indirectJumpMap.add(offset, new IndirectJumpEntry(stackOffset, dataLabel));
387            else
388                result->second->addDataLabel(dataLabel);
389        }
390
391        void emitIndirectJumpTable(MacroAssembler* masm)
392        {
393            for (IndirectJumpHashMap::iterator iter = m_indirectJumpMap.begin(); iter != m_indirectJumpMap.end(); ++iter) {
394                IndirectJumpEntry* indJumpEntry = iter->second;
395                size_t size = indJumpEntry->m_dataLabelPtrVector.size();
396                if (size) {
397                    // Link any associated DataLabelPtr's with indirect jump via label
398                    Label hereLabel = masm->label();
399                    for (size_t i = 0; i < size; ++i)
400                        m_backtrackRecords.append(AlternativeBacktrackRecord(indJumpEntry->m_dataLabelPtrVector[i], hereLabel));
401                }
402                indJumpEntry->m_relJumps.link(masm);
403                masm->jump(Address(stackPointerRegister, indJumpEntry->m_stackOffset));
404                delete indJumpEntry;
405            }
406        }
407
408        void incrementParenNestingLevel()
409        {
410            ++m_parenNestingLevel;
411        }
412
413        void decrementParenNestingLevel()
414        {
415            --m_parenNestingLevel;
416        }
417
418        ParenthesesTail* addParenthesesTail(PatternTerm& term, JumpList* jumpListToPriorParen)
419        {
420            ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, jumpListToPriorParen);
421            m_parenTails.append(parenthesesTail);
422            m_parenTailsForIteration.append(parenthesesTail);
423
424            return parenthesesTail;
425        }
426
427        void emitParenthesesTail(YarrGenerator* generator)
428        {
429            unsigned vectorSize = m_parenTails.size();
430            bool priorBacktrackFallThrough = false;
431
432            // Emit in reverse order so parentTail N can fall through to N-1
433            for (unsigned index = vectorSize; index > 0; --index) {
434                JumpList jumpsToNext;
435                priorBacktrackFallThrough = m_parenTails[index-1].get()->generateCode(generator, jumpsToNext, priorBacktrackFallThrough, index > 1);
436                if (index > 1)
437                    jumpsToNext.linkTo(generator->label(), generator);
438                else
439                    addJumpsToNextInteration(jumpsToNext);
440            }
441            m_parenTails.clear();
442        }
443
444        void addJumpToNextInteration(Jump jump)
445        {
446            m_jumpsToNextInteration.append(jump);
447        }
448
449        void addJumpsToNextInteration(JumpList jumps)
450        {
451            m_jumpsToNextInteration.append(jumps);
452        }
453
454        void addDataLabelToNextIteration(DataLabelPtr dataLabel)
455        {
456            m_dataPtrsToNextIteration.append(dataLabel);
457        }
458
459        void linkToNextIteration(Label label)
460        {
461            m_nextIteration = label;
462
463            for (unsigned i = 0; i < m_dataPtrsToNextIteration.size(); ++i)
464                m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataPtrsToNextIteration[i], m_nextIteration));
465
466            m_dataPtrsToNextIteration.clear();
467
468            for (unsigned i = 0; i < m_parenTailsForIteration.size(); ++i)
469                m_parenTailsForIteration[i]->setNextIteration(m_nextIteration);
470
471            m_parenTailsForIteration.clear();
472        }
473
474        void linkToNextIteration(YarrGenerator* generator)
475        {
476            m_jumpsToNextInteration.linkTo(m_nextIteration, generator);
477        }
478
479        int m_parenNestingLevel;
480        Vector<AlternativeBacktrackRecord> m_backtrackRecords;
481        IndirectJumpHashMap m_indirectJumpMap;
482        Label m_nextIteration;
483        Vector<OwnPtr<ParenthesesTail> > m_parenTails;
484        JumpList m_jumpsToNextInteration;
485        Vector<DataLabelPtr> m_dataPtrsToNextIteration;
486        Vector<ParenthesesTail*> m_parenTailsForIteration;
487    };
488
489    struct BacktrackDestination {
490        typedef enum {
491            NoBacktrack,
492            BacktrackLabel,
493            BacktrackStackOffset,
494            BacktrackJumpList,
495            BacktrackLinked
496        } BacktrackType;
497
498        BacktrackDestination()
499            : m_backtrackType(NoBacktrack)
500            , m_backtrackToLabel(0)
501            , m_subDataLabelPtr(0)
502            , m_nextBacktrack(0)
503            , m_backtrackSourceLabel(0)
504            , m_backtrackSourceJumps(0)
505        {
506        }
507
508        BacktrackDestination(int32_t stackOffset)
509            : m_backtrackType(BacktrackStackOffset)
510            , m_backtrackStackOffset(stackOffset)
511            , m_backtrackToLabel(0)
512            , m_subDataLabelPtr(0)
513            , m_nextBacktrack(0)
514            , m_backtrackSourceLabel(0)
515            , m_backtrackSourceJumps(0)
516        {
517        }
518
519        BacktrackDestination(Label label)
520            : m_backtrackType(BacktrackLabel)
521            , m_backtrackLabel(label)
522            , m_backtrackToLabel(0)
523            , m_subDataLabelPtr(0)
524            , m_nextBacktrack(0)
525            , m_backtrackSourceLabel(0)
526            , m_backtrackSourceJumps(0)
527        {
528        }
529
530        void clear(bool doDataLabelClear = true)
531        {
532            m_backtrackType = NoBacktrack;
533            if (doDataLabelClear)
534                clearDataLabel();
535            m_nextBacktrack = 0;
536        }
537
538        void clearDataLabel()
539        {
540            m_dataLabelPtr = DataLabelPtr();
541        }
542
543        bool hasDestination()
544        {
545            return (m_backtrackType != NoBacktrack);
546        }
547
548        bool isStackOffset()
549        {
550            return (m_backtrackType == BacktrackStackOffset);
551        }
552
553        bool isLabel()
554        {
555            return (m_backtrackType == BacktrackLabel);
556        }
557
558        bool isJumpList()
559        {
560            return (m_backtrackType == BacktrackJumpList);
561        }
562
563        bool hasDataLabel()
564        {
565            return m_dataLabelPtr.isSet();
566        }
567
568        void copyTarget(BacktrackDestination& rhs, bool copyDataLabel = true)
569        {
570            m_backtrackType = rhs.m_backtrackType;
571            if (m_backtrackType == BacktrackStackOffset)
572                m_backtrackStackOffset = rhs.m_backtrackStackOffset;
573            else if (m_backtrackType == BacktrackLabel)
574                m_backtrackLabel = rhs.m_backtrackLabel;
575            if (copyDataLabel)
576                m_dataLabelPtr = rhs.m_dataLabelPtr;
577            m_backtrackSourceJumps = rhs.m_backtrackSourceJumps;
578            m_backtrackSourceLabel = rhs.m_backtrackSourceLabel;
579        }
580
581        void copyTo(BacktrackDestination& lhs)
582        {
583            lhs.m_backtrackType = m_backtrackType;
584            if (m_backtrackType == BacktrackStackOffset)
585                lhs.m_backtrackStackOffset = m_backtrackStackOffset;
586            else if (m_backtrackType == BacktrackLabel)
587                lhs.m_backtrackLabel = m_backtrackLabel;
588            lhs.m_backtrackSourceJumps = m_backtrackSourceJumps;
589            lhs.m_backtrackSourceLabel = m_backtrackSourceLabel;
590            lhs.m_dataLabelPtr = m_dataLabelPtr;
591            lhs.m_backTrackJumps = m_backTrackJumps;
592        }
593
594        void addBacktrackJump(Jump jump)
595        {
596            m_backTrackJumps.append(jump);
597        }
598
599        void setStackOffset(int32_t stackOffset)
600        {
601            m_backtrackType = BacktrackStackOffset;
602            m_backtrackStackOffset = stackOffset;
603        }
604
605        void setLabel(Label label)
606        {
607            m_backtrackType = BacktrackLabel;
608            m_backtrackLabel = label;
609        }
610
611        void setNextBacktrackLabel(Label label)
612        {
613            if (m_nextBacktrack)
614                m_nextBacktrack->setLabel(label);
615        }
616
617        void propagateBacktrackToLabel(const BacktrackDestination& rhs)
618        {
619            if (!m_backtrackToLabel && rhs.m_backtrackToLabel)
620                m_backtrackToLabel = rhs.m_backtrackToLabel;
621        }
622
623        void setBacktrackToLabel(Label* backtrackToLabel)
624        {
625            if (!m_backtrackToLabel)
626                m_backtrackToLabel = backtrackToLabel;
627        }
628
629        bool hasBacktrackToLabel()
630        {
631            return m_backtrackToLabel;
632        }
633
634        void setBacktrackJumpList(JumpList* jumpList)
635        {
636            m_backtrackType = BacktrackJumpList;
637            m_backtrackSourceJumps = jumpList;
638        }
639
640        void setBacktrackSourceLabel(Label* backtrackSourceLabel)
641        {
642            m_backtrackSourceLabel = backtrackSourceLabel;
643        }
644
645        void setDataLabel(DataLabelPtr dp)
646        {
647            if (m_subDataLabelPtr) {
648                *m_subDataLabelPtr = dp;
649                m_subDataLabelPtr = 0;
650            } else {
651                ASSERT(!hasDataLabel());
652                m_dataLabelPtr = dp;
653            }
654        }
655
656        void clearSubDataLabelPtr()
657        {
658            m_subDataLabelPtr = 0;
659        }
660
661        void setSubDataLabelPtr(DataLabelPtr* subDataLabelPtr)
662        {
663            m_subDataLabelPtr = subDataLabelPtr;
664        }
665
666        void linkToNextBacktrack(BacktrackDestination* nextBacktrack)
667        {
668            m_nextBacktrack = nextBacktrack;
669        }
670
671        int32_t getStackOffset()
672        {
673            ASSERT(m_backtrackType == BacktrackStackOffset);
674            return m_backtrackStackOffset;
675        }
676
677        Label getLabel()
678        {
679            ASSERT(m_backtrackType == BacktrackLabel);
680            return m_backtrackLabel;
681        }
682
683        JumpList& getBacktrackJumps()
684        {
685            return m_backTrackJumps;
686        }
687
688        DataLabelPtr& getDataLabel()
689        {
690            return m_dataLabelPtr;
691        }
692
693        void jumpToBacktrack(MacroAssembler* masm)
694        {
695            if (isJumpList()) {
696                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
697                    masm->jump().linkTo(*m_backtrackSourceLabel, masm);
698                else
699                    m_backtrackSourceJumps->append(masm->jump());
700            } else if (isStackOffset())
701                masm->jump(Address(stackPointerRegister, m_backtrackStackOffset));
702            else if (isLabel())
703                masm->jump().linkTo(m_backtrackLabel, masm);
704            else
705                m_backTrackJumps.append(masm->jump());
706        }
707
708        void jumpToBacktrack(YarrGenerator* generator, Jump jump)
709        {
710            if (isJumpList()) {
711                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
712                    jump.linkTo(*m_backtrackSourceLabel, generator);
713                else
714                    m_backtrackSourceJumps->append(jump);
715            } else if (isStackOffset())
716                generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jump);
717            else if (isLabel())
718                jump.linkTo(getLabel(), generator);
719            else
720                m_backTrackJumps.append(jump);
721        }
722
723        void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps)
724        {
725            if (isJumpList()) {
726                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
727                    jumps.linkTo(*m_backtrackSourceLabel, generator);
728                else
729                    m_backtrackSourceJumps->append(jumps);
730            } else if (isStackOffset())
731                generator->m_expressionState.addIndirectJumpEntry(getStackOffset(), jumps);
732            else if (isLabel())
733                jumps.linkTo(getLabel(), generator);
734            else
735                m_backTrackJumps.append(jumps);
736        }
737
738        bool plantJumpToBacktrackIfExists(YarrGenerator* generator)
739        {
740            if (isJumpList()) {
741                if (m_backtrackSourceLabel && (m_backtrackSourceLabel->isSet()))
742                    generator->jump(*m_backtrackSourceLabel);
743                else
744                    m_backtrackSourceJumps->append(generator->jump());
745
746                return true;
747            }
748
749            if (isStackOffset()) {
750                generator->jump(Address(stackPointerRegister, getStackOffset()));
751                return true;
752            }
753
754            if (isLabel()) {
755                generator->jump(getLabel());
756                if (hasDataLabel()) {
757                    generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), getLabel()));
758                    clearDataLabel();
759                }
760                return true;
761            }
762
763            return false;
764        }
765
766        void linkBacktrackToLabel(Label backtrackLabel)
767        {
768            if (m_backtrackToLabel)
769                *m_backtrackToLabel = backtrackLabel;
770        }
771
772        void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false)
773        {
774            Label hereLabel = generator->label();
775
776            if (m_backtrackToLabel) {
777                *m_backtrackToLabel = hereLabel;
778                m_backtrackToLabel = 0;
779            }
780
781            m_backTrackJumps.link(generator);
782
783            if (nextIteration)
784                generator->m_expressionState.linkToNextIteration(hereLabel);
785
786            if (hasDataLabel()) {
787                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), hereLabel));
788                // data label cleared as a result of the clear() below
789            }
790
791            clear();
792        }
793
794        void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false)
795        {
796            m_backTrackJumps.linkTo(label, generator);
797
798            if (nextIteration)
799                generator->m_expressionState.linkToNextIteration(label);
800
801            if (hasDataLabel()) {
802                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(getDataLabel(), label));
803                clearDataLabel();
804            }
805        }
806
807    private:
808        BacktrackType m_backtrackType;
809        int32_t m_backtrackStackOffset;
810        Label m_backtrackLabel;
811        DataLabelPtr m_dataLabelPtr;
812        Label* m_backtrackToLabel;
813        DataLabelPtr* m_subDataLabelPtr;
814        BacktrackDestination* m_nextBacktrack;
815        Label* m_backtrackSourceLabel;
816        JumpList* m_backtrackSourceJumps;
817        JumpList m_backTrackJumps;
818    };
819
820    struct TermGenerationState {
821        TermGenerationState(PatternDisjunction* disjunction, unsigned checkedTotal)
822            : disjunction(disjunction)
823            , checkedTotal(checkedTotal)
824            , m_subParenNum(0)
825            , m_linkedBacktrack(0)
826            , m_jumpList(0)
827        {
828        }
829
830        void resetAlternative()
831        {
832            m_backtrack.clear();
833            alt = 0;
834        }
835        bool alternativeValid()
836        {
837            return alt < disjunction->m_alternatives.size();
838        }
839        void nextAlternative()
840        {
841            ++alt;
842        }
843        PatternAlternative* alternative()
844        {
845            return disjunction->m_alternatives[alt];
846        }
847        bool isLastAlternative()
848        {
849            return (alt + 1) == disjunction->m_alternatives.size();
850        }
851
852        void resetTerm()
853        {
854            ASSERT(alternativeValid());
855            t = 0;
856            m_subParenNum = 0;
857        }
858        bool termValid()
859        {
860            ASSERT(alternativeValid());
861            return t < alternative()->m_terms.size();
862        }
863        void nextTerm()
864        {
865            ASSERT(alternativeValid());
866            ++t;
867        }
868        PatternTerm& term()
869        {
870            ASSERT(alternativeValid());
871            return alternative()->m_terms[t];
872        }
873        bool isLastTerm()
874        {
875            ASSERT(alternativeValid());
876            return (t + 1) == alternative()->m_terms.size();
877        }
878        unsigned getSubParenNum()
879        {
880            return m_subParenNum++;
881        }
882        bool isMainDisjunction()
883        {
884            return !disjunction->m_parent;
885        }
886
887        void setJumpListToPriorParen(JumpList* jumpList)
888        {
889            m_jumpList = jumpList;
890        }
891
892        JumpList* getJumpListToPriorParen()
893        {
894            return m_jumpList;
895        }
896
897        PatternTerm& lookaheadTerm()
898        {
899            ASSERT(alternativeValid());
900            ASSERT((t + 1) < alternative()->m_terms.size());
901            return alternative()->m_terms[t + 1];
902        }
903        bool isSinglePatternCharacterLookaheadTerm()
904        {
905            ASSERT(alternativeValid());
906            return ((t + 1) < alternative()->m_terms.size())
907                && (lookaheadTerm().type == PatternTerm::TypePatternCharacter)
908                && (lookaheadTerm().quantityType == QuantifierFixedCount)
909                && (lookaheadTerm().quantityCount == 1);
910        }
911
912        int inputOffset()
913        {
914            return term().inputPosition - checkedTotal;
915        }
916
917        void clearBacktrack()
918        {
919            m_backtrack.clear(false);
920            m_linkedBacktrack = 0;
921        }
922
923        void jumpToBacktrack(MacroAssembler* masm)
924        {
925            m_backtrack.jumpToBacktrack(masm);
926        }
927
928        void jumpToBacktrack(YarrGenerator* generator, Jump jump)
929        {
930            m_backtrack.jumpToBacktrack(generator, jump);
931        }
932
933        void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps)
934        {
935            m_backtrack.jumpToBacktrack(generator, jumps);
936        }
937
938        bool plantJumpToBacktrackIfExists(YarrGenerator* generator)
939        {
940            return m_backtrack.plantJumpToBacktrackIfExists(generator);
941        }
942
943        void linkDataLabelToBacktrackIfExists(YarrGenerator* generator, DataLabelPtr dataLabel)
944        {
945            // If we have a stack offset backtrack destination, use it directly
946            if (m_backtrack.isStackOffset()) {
947                generator->m_expressionState.addIndirectJumpEntry(m_backtrack.getStackOffset(), dataLabel);
948                m_backtrack.clearSubDataLabelPtr();
949            } else {
950                // If we have a backtrack label, connect the datalabel to it directly.
951                if (m_backtrack.isLabel())
952                    generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(dataLabel, m_backtrack.getLabel()));
953                else
954                    setBacktrackDataLabel(dataLabel);
955            }
956        }
957
958        void addBacktrackJump(Jump jump)
959        {
960            m_backtrack.addBacktrackJump(jump);
961        }
962
963        void setBacktrackDataLabel(DataLabelPtr dp)
964        {
965            m_backtrack.setDataLabel(dp);
966        }
967
968        void setBackTrackStackOffset(int32_t stackOffset)
969        {
970            m_backtrack.setStackOffset(stackOffset);
971        }
972
973        void setBacktrackLabel(Label label)
974        {
975            m_backtrack.setLabel(label);
976        }
977
978        void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false)
979        {
980            m_backtrack.linkAlternativeBacktracks(generator, nextIteration);
981            m_linkedBacktrack = 0;
982        }
983
984        void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false)
985        {
986            m_backtrack.linkAlternativeBacktracksTo(generator, label, nextIteration);
987        }
988
989        void setBacktrackLink(BacktrackDestination* linkedBacktrack)
990        {
991            m_linkedBacktrack = linkedBacktrack;
992        }
993
994        void chainBacktracks(BacktrackDestination* followonBacktrack)
995        {
996            if (m_linkedBacktrack)
997                m_linkedBacktrack->linkToNextBacktrack(followonBacktrack);
998        }
999
1000        BacktrackDestination& getBacktrackDestination()
1001        {
1002            return m_backtrack;
1003        }
1004
1005        void propagateBacktrackingFrom(YarrGenerator* generator, BacktrackDestination& backtrack, bool doJump = true)
1006        {
1007            if (doJump)
1008                m_backtrack.jumpToBacktrack(generator, backtrack.getBacktrackJumps());
1009
1010            if (m_backtrack.isLabel() && backtrack.hasBacktrackToLabel())
1011                backtrack.linkBacktrackToLabel(m_backtrack.getLabel());
1012
1013            if (backtrack.hasDestination()) {
1014                if (m_backtrack.hasDataLabel())
1015                    generator->m_expressionState.addDataLabelToNextIteration(m_backtrack.getDataLabel());
1016
1017                m_backtrack.copyTarget(backtrack, doJump);
1018            }
1019        }
1020
1021        PatternDisjunction* disjunction;
1022        int checkedTotal;
1023    private:
1024        unsigned alt;
1025        unsigned t;
1026        unsigned m_subParenNum;
1027        BacktrackDestination m_backtrack;
1028        BacktrackDestination* m_linkedBacktrack;
1029        JumpList* m_jumpList;
1030    };
1031
1032    struct ParenthesesTail {
1033        ParenthesesTail(PatternTerm& term, int nestingLevel, JumpList* jumpListToPriorParen)
1034            : m_term(term)
1035            , m_nestingLevel(nestingLevel)
1036            , m_subParenIndex(0)
1037            , m_jumpListToPriorParen(jumpListToPriorParen)
1038        {
1039        }
1040
1041        void processBacktracks(YarrGenerator* generator, TermGenerationState& state, TermGenerationState& parenthesesState, Label nonGreedyTryParentheses, Label fallThrough)
1042        {
1043            m_nonGreedyTryParentheses = nonGreedyTryParentheses;
1044            m_fallThrough = fallThrough;
1045
1046            m_subParenIndex = state.getSubParenNum();
1047            parenthesesState.getBacktrackDestination().copyTo(m_parenBacktrack);
1048            state.chainBacktracks(&m_backtrack);
1049            BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
1050            stateBacktrack.copyTo(m_backtrack);
1051            stateBacktrack.setBacktrackToLabel(&m_backtrackToLabel);
1052            state.setBacktrackLink(&m_backtrack);
1053            stateBacktrack.setSubDataLabelPtr(&m_dataAfterLabelPtr);
1054
1055            m_doDirectBacktrack = m_parenBacktrack.hasDestination();
1056
1057            if ((m_term.quantityType == QuantifierGreedy) || (m_term.quantityType == QuantifierNonGreedy))
1058                m_doDirectBacktrack = false;
1059
1060            if (m_doDirectBacktrack)
1061                state.propagateBacktrackingFrom(generator, m_parenBacktrack, false);
1062            else {
1063                stateBacktrack.setBacktrackJumpList(&m_afterBacktrackJumps);
1064                stateBacktrack.setBacktrackSourceLabel(&m_backtrackFromAfterParens);
1065            }
1066        }
1067
1068        void setNextIteration(Label nextIteration)
1069        {
1070            if (!m_nestingLevel && !m_backtrackToLabel.isSet())
1071                m_backtrackToLabel = nextIteration;
1072        }
1073
1074        void addAfterParenJump(Jump jump)
1075        {
1076            m_afterBacktrackJumps.append(jump);
1077        }
1078
1079        bool generateCode(YarrGenerator* generator, JumpList& jumpsToNext, bool priorBackTrackFallThrough, bool nextBacktrackFallThrough)
1080        {
1081            const RegisterID indexTemporary = regT0;
1082            unsigned parenthesesFrameLocation = m_term.frameLocation;
1083            Jump fromPriorBacktrack;
1084            bool needJumpForPriorParenTail = false;
1085
1086            if (priorBackTrackFallThrough
1087                && ((m_term.quantityType == QuantifierGreedy)
1088                 || (m_term.quantityType == QuantifierNonGreedy)
1089                 || (!m_doDirectBacktrack && m_parenBacktrack.hasDestination()))) {
1090                // If the prior paren tail code assumed that it could fall through,
1091                // but we need to generate after paren backtrack code, then provide
1092                // a jump around that code for the prior paren tail code.
1093                // A regular expressing like ((xxx)...)? needs this.
1094                fromPriorBacktrack = generator->jump();
1095                needJumpForPriorParenTail = true;
1096            }
1097
1098            if (!m_backtrack.hasDestination()) {
1099                if (m_backtrackToLabel.isSet()) {
1100                    m_backtrack.setLabel(m_backtrackToLabel);
1101                    nextBacktrackFallThrough = false;
1102                } else if (m_jumpListToPriorParen) {
1103                    // If we don't have a destination, go back to either the prior paren or the next outer paren.
1104                    m_backtrack.setBacktrackJumpList(m_jumpListToPriorParen);
1105                    nextBacktrackFallThrough = false;
1106                } else
1107                    m_backtrack.setBacktrackJumpList(&jumpsToNext);
1108            } else
1109                nextBacktrackFallThrough = false;
1110
1111            // A failure AFTER the parens jumps here - Backtrack to this paren
1112            m_backtrackFromAfterParens = generator->label();
1113
1114            if (m_dataAfterLabelPtr.isSet())
1115                generator->m_expressionState.m_backtrackRecords.append(AlternativeBacktrackRecord(m_dataAfterLabelPtr, m_backtrackFromAfterParens));
1116
1117            m_afterBacktrackJumps.link(generator);
1118
1119            if (m_term.quantityType == QuantifierGreedy) {
1120                // If this is -1 we have now tested with both with and without the parens.
1121                generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
1122                m_backtrack.jumpToBacktrack(generator, generator->branch32(Equal, indexTemporary, TrustedImm32(-1)));
1123            } else if (m_term.quantityType == QuantifierNonGreedy) {
1124                // If this is -1 we have now tested with both with and without the parens.
1125                generator->loadFromFrame(parenthesesFrameLocation, indexTemporary);
1126                generator->branch32(Equal, indexTemporary, TrustedImm32(-1)).linkTo(m_nonGreedyTryParentheses, generator);
1127            }
1128
1129            if (!m_doDirectBacktrack)
1130                m_parenBacktrack.plantJumpToBacktrackIfExists(generator);
1131
1132            // A failure WITHIN the parens jumps here
1133            if (needJumpForPriorParenTail)
1134                fromPriorBacktrack.link(generator);
1135            m_parenBacktrack.linkAlternativeBacktracks(generator);
1136            m_withinBacktrackJumps.link(generator);
1137
1138            if (m_term.capture())
1139                generator->store32(TrustedImm32(-1), Address(output, (m_term.parentheses.subpatternId << 1) * sizeof(int)));
1140
1141            if (m_term.quantityType == QuantifierGreedy) {
1142                generator->storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1143                generator->jump().linkTo(m_fallThrough, generator);
1144                nextBacktrackFallThrough = false;
1145            } else if (!nextBacktrackFallThrough)
1146                m_backtrack.jumpToBacktrack(generator);
1147
1148            if (!m_doDirectBacktrack)
1149                m_backtrack.setNextBacktrackLabel(m_backtrackFromAfterParens);
1150
1151            return nextBacktrackFallThrough;
1152        }
1153
1154        PatternTerm& m_term;
1155        int m_nestingLevel;
1156        unsigned m_subParenIndex;
1157        JumpList* m_jumpListToPriorParen;
1158        Label m_nonGreedyTryParentheses;
1159        Label m_fallThrough;
1160        Label m_backtrackToLabel;
1161        Label m_backtrackFromAfterParens;
1162        DataLabelPtr m_dataAfterLabelPtr;
1163        JumpList m_withinBacktrackJumps;
1164        JumpList m_afterBacktrackJumps;
1165        BacktrackDestination m_parenBacktrack;
1166        BacktrackDestination m_backtrack;
1167        bool m_doDirectBacktrack;
1168    };
1169
1170    void generateAssertionBOL(TermGenerationState& state)
1171    {
1172        PatternTerm& term = state.term();
1173
1174        if (m_pattern.m_multiline) {
1175            const RegisterID character = regT0;
1176
1177            JumpList matchDest;
1178            if (!term.inputPosition)
1179                matchDest.append(branch32(Equal, index, Imm32(state.checkedTotal)));
1180
1181            readCharacter(state.inputOffset() - 1, character);
1182            matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1183            state.jumpToBacktrack(this);
1184
1185            matchDest.link(this);
1186        } else {
1187            // Erk, really should poison out these alternatives early. :-/
1188            if (term.inputPosition)
1189                state.jumpToBacktrack(this);
1190            else
1191                state.jumpToBacktrack(this, branch32(NotEqual, index, Imm32(state.checkedTotal)));
1192        }
1193    }
1194
1195    void generateAssertionEOL(TermGenerationState& state)
1196    {
1197        PatternTerm& term = state.term();
1198
1199        if (m_pattern.m_multiline) {
1200            const RegisterID character = regT0;
1201
1202            JumpList matchDest;
1203            if (term.inputPosition == state.checkedTotal)
1204                matchDest.append(atEndOfInput());
1205
1206            readCharacter(state.inputOffset(), character);
1207            matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1208            state.jumpToBacktrack(this);
1209
1210            matchDest.link(this);
1211        } else {
1212            if (term.inputPosition == state.checkedTotal)
1213                state.jumpToBacktrack(this, notAtEndOfInput());
1214            // Erk, really should poison out these alternatives early. :-/
1215            else
1216                state.jumpToBacktrack(this);
1217        }
1218    }
1219
1220    // Also falls though on nextIsNotWordChar.
1221    void matchAssertionWordchar(TermGenerationState& state, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
1222    {
1223        const RegisterID character = regT0;
1224        PatternTerm& term = state.term();
1225
1226        if (term.inputPosition == state.checkedTotal)
1227            nextIsNotWordChar.append(atEndOfInput());
1228
1229        readCharacter(state.inputOffset(), character);
1230        matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
1231    }
1232
1233    void generateAssertionWordBoundary(TermGenerationState& state)
1234    {
1235        const RegisterID character = regT0;
1236        PatternTerm& term = state.term();
1237
1238        Jump atBegin;
1239        JumpList matchDest;
1240        if (!term.inputPosition)
1241            atBegin = branch32(Equal, index, Imm32(state.checkedTotal));
1242        readCharacter(state.inputOffset() - 1, character);
1243        matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
1244        if (!term.inputPosition)
1245            atBegin.link(this);
1246
1247        // We fall through to here if the last character was not a wordchar.
1248        JumpList nonWordCharThenWordChar;
1249        JumpList nonWordCharThenNonWordChar;
1250        if (term.invert()) {
1251            matchAssertionWordchar(state, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
1252            nonWordCharThenWordChar.append(jump());
1253        } else {
1254            matchAssertionWordchar(state, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
1255            nonWordCharThenNonWordChar.append(jump());
1256        }
1257        state.jumpToBacktrack(this, nonWordCharThenNonWordChar);
1258
1259        // We jump here if the last character was a wordchar.
1260        matchDest.link(this);
1261        JumpList wordCharThenWordChar;
1262        JumpList wordCharThenNonWordChar;
1263        if (term.invert()) {
1264            matchAssertionWordchar(state, wordCharThenNonWordChar, wordCharThenWordChar);
1265            wordCharThenWordChar.append(jump());
1266        } else {
1267            matchAssertionWordchar(state, wordCharThenWordChar, wordCharThenNonWordChar);
1268            // This can fall-though!
1269        }
1270
1271        state.jumpToBacktrack(this, wordCharThenWordChar);
1272
1273        nonWordCharThenWordChar.link(this);
1274        wordCharThenNonWordChar.link(this);
1275    }
1276
1277    void generatePatternCharacterSingle(TermGenerationState& state)
1278    {
1279        const RegisterID character = regT0;
1280        UChar ch = state.term().patternCharacter;
1281
1282        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1283            readCharacter(state.inputOffset(), character);
1284            or32(TrustedImm32(32), character);
1285            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1286        } else {
1287            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1288            state.jumpToBacktrack(this, jumpIfCharNotEquals(ch, state.inputOffset()));
1289        }
1290    }
1291
1292    void generatePatternCharacterPair(TermGenerationState& state)
1293    {
1294        const RegisterID character = regT0;
1295        UChar ch1 = state.term().patternCharacter;
1296        UChar ch2 = state.lookaheadTerm().patternCharacter;
1297
1298        int mask = 0;
1299        int chPair = ch1 | (ch2 << 16);
1300
1301        if (m_pattern.m_ignoreCase) {
1302            if (isASCIIAlpha(ch1))
1303                mask |= 32;
1304            if (isASCIIAlpha(ch2))
1305                mask |= 32 << 16;
1306        }
1307
1308        if (mask) {
1309            load32WithUnalignedHalfWords(BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), character);
1310            or32(Imm32(mask), character);
1311            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(chPair | mask)));
1312        } else
1313            state.jumpToBacktrack(this, branch32WithUnalignedHalfWords(NotEqual, BaseIndex(input, index, TimesTwo, state.inputOffset() * sizeof(UChar)), Imm32(chPair)));
1314    }
1315
1316    void generatePatternCharacterFixed(TermGenerationState& state)
1317    {
1318        const RegisterID character = regT0;
1319        const RegisterID countRegister = regT1;
1320        PatternTerm& term = state.term();
1321        UChar ch = term.patternCharacter;
1322
1323        move(index, countRegister);
1324        sub32(Imm32(term.quantityCount), countRegister);
1325
1326        Label loop(this);
1327        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1328            load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
1329            or32(TrustedImm32(32), character);
1330            state.jumpToBacktrack(this, branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1331        } else {
1332            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1333            state.jumpToBacktrack(this, branch16(NotEqual, BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), Imm32(ch)));
1334        }
1335        add32(TrustedImm32(1), countRegister);
1336        branch32(NotEqual, countRegister, index).linkTo(loop, this);
1337    }
1338
1339    void generatePatternCharacterGreedy(TermGenerationState& state)
1340    {
1341        const RegisterID character = regT0;
1342        const RegisterID countRegister = regT1;
1343        PatternTerm& term = state.term();
1344        UChar ch = term.patternCharacter;
1345
1346        move(TrustedImm32(0), countRegister);
1347
1348        JumpList failures;
1349        Label loop(this);
1350        failures.append(atEndOfInput());
1351        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1352            readCharacter(state.inputOffset(), character);
1353            or32(TrustedImm32(32), character);
1354            failures.append(branch32(NotEqual, character, Imm32(Unicode::toLower(ch))));
1355        } else {
1356            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1357            failures.append(jumpIfCharNotEquals(ch, state.inputOffset()));
1358        }
1359
1360        add32(TrustedImm32(1), countRegister);
1361        add32(TrustedImm32(1), index);
1362        if (term.quantityCount != quantifyInfinite) {
1363            branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
1364            failures.append(jump());
1365        } else
1366            jump(loop);
1367
1368        Label backtrackBegin(this);
1369        loadFromFrame(term.frameLocation, countRegister);
1370        state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
1371        sub32(TrustedImm32(1), countRegister);
1372        sub32(TrustedImm32(1), index);
1373
1374        failures.link(this);
1375
1376        storeToFrame(countRegister, term.frameLocation);
1377
1378        state.setBacktrackLabel(backtrackBegin);
1379    }
1380
1381    void generatePatternCharacterNonGreedy(TermGenerationState& state)
1382    {
1383        const RegisterID character = regT0;
1384        const RegisterID countRegister = regT1;
1385        PatternTerm& term = state.term();
1386        UChar ch = term.patternCharacter;
1387
1388        move(TrustedImm32(0), countRegister);
1389
1390        Jump firstTimeDoNothing = jump();
1391
1392        Label hardFail(this);
1393        sub32(countRegister, index);
1394        state.jumpToBacktrack(this);
1395
1396        Label backtrackBegin(this);
1397        loadFromFrame(term.frameLocation, countRegister);
1398
1399        atEndOfInput().linkTo(hardFail, this);
1400        if (term.quantityCount != quantifyInfinite)
1401            branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
1402        if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1403            readCharacter(state.inputOffset(), character);
1404            or32(TrustedImm32(32), character);
1405            branch32(NotEqual, character, Imm32(Unicode::toLower(ch))).linkTo(hardFail, this);
1406        } else {
1407            ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch)));
1408            jumpIfCharNotEquals(ch, state.inputOffset()).linkTo(hardFail, this);
1409        }
1410
1411        add32(TrustedImm32(1), countRegister);
1412        add32(TrustedImm32(1), index);
1413
1414        firstTimeDoNothing.link(this);
1415        storeToFrame(countRegister, term.frameLocation);
1416
1417        state.setBacktrackLabel(backtrackBegin);
1418    }
1419
1420    void generateCharacterClassSingle(TermGenerationState& state)
1421    {
1422        const RegisterID character = regT0;
1423        PatternTerm& term = state.term();
1424
1425        JumpList matchDest;
1426        readCharacter(state.inputOffset(), character);
1427        matchCharacterClass(character, matchDest, term.characterClass);
1428
1429        if (term.invert())
1430            state.jumpToBacktrack(this, matchDest);
1431        else {
1432            state.jumpToBacktrack(this);
1433            matchDest.link(this);
1434        }
1435    }
1436
1437    void generateCharacterClassFixed(TermGenerationState& state)
1438    {
1439        const RegisterID character = regT0;
1440        const RegisterID countRegister = regT1;
1441        PatternTerm& term = state.term();
1442
1443        move(index, countRegister);
1444        sub32(Imm32(term.quantityCount), countRegister);
1445
1446        Label loop(this);
1447        JumpList matchDest;
1448        load16(BaseIndex(input, countRegister, TimesTwo, (state.inputOffset() + term.quantityCount) * sizeof(UChar)), character);
1449        matchCharacterClass(character, matchDest, term.characterClass);
1450
1451        if (term.invert())
1452            state.jumpToBacktrack(this, matchDest);
1453        else {
1454            state.jumpToBacktrack(this);
1455            matchDest.link(this);
1456        }
1457
1458        add32(TrustedImm32(1), countRegister);
1459        branch32(NotEqual, countRegister, index).linkTo(loop, this);
1460    }
1461
1462    void generateCharacterClassGreedy(TermGenerationState& state)
1463    {
1464        const RegisterID character = regT0;
1465        const RegisterID countRegister = regT1;
1466        PatternTerm& term = state.term();
1467
1468        move(TrustedImm32(0), countRegister);
1469
1470        JumpList failures;
1471        Label loop(this);
1472        failures.append(atEndOfInput());
1473
1474        if (term.invert()) {
1475            readCharacter(state.inputOffset(), character);
1476            matchCharacterClass(character, failures, term.characterClass);
1477        } else {
1478            JumpList matchDest;
1479            readCharacter(state.inputOffset(), character);
1480            matchCharacterClass(character, matchDest, term.characterClass);
1481            failures.append(jump());
1482            matchDest.link(this);
1483        }
1484
1485        add32(TrustedImm32(1), countRegister);
1486        add32(TrustedImm32(1), index);
1487        if (term.quantityCount != quantifyInfinite) {
1488            branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this);
1489            failures.append(jump());
1490        } else
1491            jump(loop);
1492
1493        Label backtrackBegin(this);
1494        loadFromFrame(term.frameLocation, countRegister);
1495        state.jumpToBacktrack(this, branchTest32(Zero, countRegister));
1496        sub32(TrustedImm32(1), countRegister);
1497        sub32(TrustedImm32(1), index);
1498
1499        failures.link(this);
1500
1501        storeToFrame(countRegister, term.frameLocation);
1502
1503        state.setBacktrackLabel(backtrackBegin);
1504    }
1505
1506    void generateCharacterClassNonGreedy(TermGenerationState& state)
1507    {
1508        const RegisterID character = regT0;
1509        const RegisterID countRegister = regT1;
1510        PatternTerm& term = state.term();
1511
1512        move(TrustedImm32(0), countRegister);
1513
1514        Jump firstTimeDoNothing = jump();
1515
1516        Label hardFail(this);
1517        sub32(countRegister, index);
1518        state.jumpToBacktrack(this);
1519
1520        Label backtrackBegin(this);
1521        loadFromFrame(term.frameLocation, countRegister);
1522
1523        atEndOfInput().linkTo(hardFail, this);
1524        branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail);
1525
1526        JumpList matchDest;
1527        readCharacter(state.inputOffset(), character);
1528        matchCharacterClass(character, matchDest, term.characterClass);
1529
1530        if (term.invert())
1531            matchDest.linkTo(hardFail, this);
1532        else {
1533            jump(hardFail);
1534            matchDest.link(this);
1535        }
1536
1537        add32(TrustedImm32(1), countRegister);
1538        add32(TrustedImm32(1), index);
1539
1540        firstTimeDoNothing.link(this);
1541        storeToFrame(countRegister, term.frameLocation);
1542
1543        state.setBacktrackLabel(backtrackBegin);
1544    }
1545
1546    void generateParenthesesDisjunction(PatternTerm& parenthesesTerm, TermGenerationState& state, unsigned alternativeFrameLocation)
1547    {
1548        ASSERT((parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern) || (parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion));
1549        ASSERT(parenthesesTerm.quantityCount == 1);
1550
1551        PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
1552        unsigned preCheckedCount = ((parenthesesTerm.quantityType == QuantifierFixedCount) && (parenthesesTerm.type != PatternTerm::TypeParentheticalAssertion)) ? disjunction->m_minimumSize : 0;
1553
1554        if (disjunction->m_alternatives.size() == 1) {
1555            state.resetAlternative();
1556            ASSERT(state.alternativeValid());
1557            PatternAlternative* alternative = state.alternative();
1558            optimizeAlternative(alternative);
1559
1560            int countToCheck = alternative->m_minimumSize - preCheckedCount;
1561            if (countToCheck) {
1562                ASSERT((parenthesesTerm.type == PatternTerm::TypeParentheticalAssertion) || (parenthesesTerm.quantityType != QuantifierFixedCount));
1563
1564                // FIXME: This is quite horrible.  The call to 'plantJumpToBacktrackIfExists'
1565                // will be forced to always trampoline into here, just to decrement the index.
1566                // Ick.
1567                Jump skip = jump();
1568
1569                Label backtrackBegin(this);
1570                sub32(Imm32(countToCheck), index);
1571                state.addBacktrackJump(jump());
1572
1573                skip.link(this);
1574
1575                state.setBacktrackLabel(backtrackBegin);
1576
1577                state.jumpToBacktrack(this, jumpIfNoAvailableInput(countToCheck));
1578                state.checkedTotal += countToCheck;
1579            }
1580
1581            for (state.resetTerm(); state.termValid(); state.nextTerm())
1582                generateTerm(state);
1583
1584            state.checkedTotal -= countToCheck;
1585        } else {
1586            JumpList successes;
1587            bool propogateBacktrack = false;
1588
1589            // Save current state's paren jump list for use with each alternative
1590            JumpList* outerJumpList = state.getJumpListToPriorParen();
1591
1592            for (state.resetAlternative(); state.alternativeValid(); state.nextAlternative(), state.setJumpListToPriorParen(outerJumpList)) {
1593                PatternAlternative* alternative = state.alternative();
1594                optimizeAlternative(alternative);
1595
1596                ASSERT(alternative->m_minimumSize >= preCheckedCount);
1597                int countToCheck = alternative->m_minimumSize - preCheckedCount;
1598                if (countToCheck) {
1599                    state.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
1600                    state.checkedTotal += countToCheck;
1601                }
1602
1603                for (state.resetTerm(); state.termValid(); state.nextTerm())
1604                    generateTerm(state);
1605
1606                // Matched an alternative.
1607                DataLabelPtr dataLabel = storeToFrameWithPatch(alternativeFrameLocation);
1608
1609                if (!state.isLastAlternative() || countToCheck)
1610                    successes.append(jump());
1611
1612                // Alternative did not match.
1613
1614                // Do we have a backtrack destination?
1615                //    if so, link the data label to it.
1616                state.linkDataLabelToBacktrackIfExists(this, dataLabel);
1617
1618                if (!state.isLastAlternative() || countToCheck)
1619                    state.linkAlternativeBacktracks(this);
1620
1621                if (countToCheck) {
1622                    sub32(Imm32(countToCheck), index);
1623                    state.checkedTotal -= countToCheck;
1624                } else if (state.isLastAlternative())
1625                    propogateBacktrack = true;
1626            }
1627            // We fall through to here when the last alternative fails.
1628            // Add a backtrack out of here for the parenthese handling code to link up.
1629            if (!propogateBacktrack)
1630                state.addBacktrackJump(jump());
1631
1632            // Save address on stack for the parens code to backtrack to, to retry the
1633            // next alternative.
1634            state.setBackTrackStackOffset(alternativeFrameLocation * sizeof(void*));
1635
1636            successes.link(this);
1637        }
1638    }
1639
1640    void generateParenthesesSingle(TermGenerationState& state)
1641    {
1642        const RegisterID indexTemporary = regT0;
1643        PatternTerm& term = state.term();
1644        PatternDisjunction* disjunction = term.parentheses.disjunction;
1645        ASSERT(term.quantityCount == 1);
1646
1647        unsigned preCheckedCount = (term.quantityType == QuantifierFixedCount) ? disjunction->m_minimumSize : 0;
1648
1649        unsigned parenthesesFrameLocation = term.frameLocation;
1650        unsigned alternativeFrameLocation = parenthesesFrameLocation;
1651        if (term.quantityType != QuantifierFixedCount)
1652            alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1653
1654        // optimized case - no capture & no quantifier can be handled in a light-weight manner.
1655        if (!term.capture() && (term.quantityType == QuantifierFixedCount)) {
1656            m_expressionState.incrementParenNestingLevel();
1657
1658            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1659
1660            // Use the current state's jump list for the nested parentheses.
1661            parenthesesState.setJumpListToPriorParen(state.getJumpListToPriorParen());
1662
1663            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1664            // this expects that any backtracks back out of the parentheses will be in the
1665            // parenthesesState's m_backTrackJumps vector, and that if they need backtracking
1666            // they will have set an entry point on the parenthesesState's m_backtrackLabel.
1667            BacktrackDestination& parenthesesBacktrack = parenthesesState.getBacktrackDestination();
1668            BacktrackDestination& stateBacktrack = state.getBacktrackDestination();
1669
1670            state.propagateBacktrackingFrom(this, parenthesesBacktrack);
1671            stateBacktrack.propagateBacktrackToLabel(parenthesesBacktrack);
1672
1673            state.setJumpListToPriorParen(parenthesesState.getJumpListToPriorParen());
1674
1675            m_expressionState.decrementParenNestingLevel();
1676        } else {
1677            Jump nonGreedySkipParentheses;
1678            Label nonGreedyTryParentheses;
1679            if (term.quantityType == QuantifierGreedy)
1680                storeToFrame(index, parenthesesFrameLocation);
1681            else if (term.quantityType == QuantifierNonGreedy) {
1682                storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1683                nonGreedySkipParentheses = jump();
1684                nonGreedyTryParentheses = label();
1685                storeToFrame(index, parenthesesFrameLocation);
1686            }
1687
1688            // store the match start index
1689            if (term.capture()) {
1690                int inputOffset = state.inputOffset() - preCheckedCount;
1691                if (inputOffset) {
1692                    move(index, indexTemporary);
1693                    add32(Imm32(inputOffset), indexTemporary);
1694                    store32(indexTemporary, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
1695                } else
1696                    store32(index, Address(output, (term.parentheses.subpatternId << 1) * sizeof(int)));
1697            }
1698
1699            ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getJumpListToPriorParen());
1700
1701            m_expressionState.incrementParenNestingLevel();
1702
1703            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1704
1705            // Save the parenthesesTail for backtracking from nested parens to this one.
1706            parenthesesState.setJumpListToPriorParen(&parenthesesTail->m_withinBacktrackJumps);
1707
1708            // generate the body of the parentheses
1709            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1710
1711            // For non-fixed counts, backtrack if we didn't match anything.
1712            if (term.quantityType != QuantifierFixedCount)
1713                parenthesesTail->addAfterParenJump(branch32(Equal, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*)))));
1714
1715            // store the match end index
1716            if (term.capture()) {
1717                int inputOffset = state.inputOffset();
1718                if (inputOffset) {
1719                    move(index, indexTemporary);
1720                    add32(Imm32(state.inputOffset()), indexTemporary);
1721                    store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
1722                } else
1723                    store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int)));
1724            }
1725
1726            m_expressionState.decrementParenNestingLevel();
1727
1728            parenthesesTail->processBacktracks(this, state, parenthesesState, nonGreedyTryParentheses, label());
1729
1730            state.setJumpListToPriorParen(&parenthesesTail->m_afterBacktrackJumps);
1731
1732            parenthesesState.getBacktrackDestination().clear();
1733
1734            if (term.quantityType == QuantifierNonGreedy)
1735                nonGreedySkipParentheses.link(this);
1736        }
1737    }
1738
1739    void generateParenthesesGreedyNoBacktrack(TermGenerationState& state)
1740    {
1741        PatternTerm& parenthesesTerm = state.term();
1742        PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction;
1743        ASSERT(parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern);
1744        ASSERT(parenthesesTerm.quantityCount != 1); // Handled by generateParenthesesSingle.
1745
1746        TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1747
1748        Label matchAgain(this);
1749
1750        storeToFrame(index, parenthesesTerm.frameLocation); // Save the current index to check for zero len matches later.
1751
1752        for (parenthesesState.resetAlternative(); parenthesesState.alternativeValid(); parenthesesState.nextAlternative()) {
1753
1754            PatternAlternative* alternative = parenthesesState.alternative();
1755            optimizeAlternative(alternative);
1756
1757            int countToCheck = alternative->m_minimumSize;
1758            if (countToCheck) {
1759                parenthesesState.addBacktrackJump(jumpIfNoAvailableInput(countToCheck));
1760                parenthesesState.checkedTotal += countToCheck;
1761            }
1762
1763            for (parenthesesState.resetTerm(); parenthesesState.termValid(); parenthesesState.nextTerm())
1764                generateTerm(parenthesesState);
1765
1766            // If we get here, we matched! If the index advanced then try to match more since limit isn't supported yet.
1767            branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesTerm.frameLocation * sizeof(void*))), matchAgain);
1768
1769            // If we get here we matched, but we matched "" - cannot accept this alternative as is, so either backtrack,
1770            // or fall through to try the next alternative if no backtrack is available.
1771            parenthesesState.plantJumpToBacktrackIfExists(this);
1772
1773            parenthesesState.linkAlternativeBacktracks(this);
1774
1775            // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop.
1776
1777            if (countToCheck) {
1778                sub32(Imm32(countToCheck), index);
1779                parenthesesState.checkedTotal -= countToCheck;
1780            }
1781        }
1782
1783        // If the last alternative falls through to here, we have a failed match...
1784        // Which means that we match whatever we have matched up to this point (even if nothing).
1785    }
1786
1787    void generateParentheticalAssertion(TermGenerationState& state)
1788    {
1789        PatternTerm& term = state.term();
1790        PatternDisjunction* disjunction = term.parentheses.disjunction;
1791        ASSERT(term.quantityCount == 1);
1792        ASSERT(term.quantityType == QuantifierFixedCount);
1793
1794        unsigned parenthesesFrameLocation = term.frameLocation;
1795        unsigned alternativeFrameLocation = parenthesesFrameLocation + YarrStackSpaceForBackTrackInfoParentheticalAssertion;
1796
1797        int countCheckedAfterAssertion = state.checkedTotal - term.inputPosition;
1798
1799        if (term.invert()) {
1800            // Inverted case
1801            storeToFrame(index, parenthesesFrameLocation);
1802
1803            state.checkedTotal -= countCheckedAfterAssertion;
1804            if (countCheckedAfterAssertion)
1805                sub32(Imm32(countCheckedAfterAssertion), index);
1806
1807            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1808            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1809            // Success! - which means - Fail!
1810            loadFromFrame(parenthesesFrameLocation, index);
1811            state.jumpToBacktrack(this);
1812
1813            // And fail means success.
1814            parenthesesState.linkAlternativeBacktracks(this);
1815
1816            loadFromFrame(parenthesesFrameLocation, index);
1817
1818            state.checkedTotal += countCheckedAfterAssertion;
1819        } else {
1820            // Normal case
1821            storeToFrame(index, parenthesesFrameLocation);
1822
1823            state.checkedTotal -= countCheckedAfterAssertion;
1824            if (countCheckedAfterAssertion)
1825                sub32(Imm32(countCheckedAfterAssertion), index);
1826
1827            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
1828            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
1829            // Success! - which means - Success!
1830            loadFromFrame(parenthesesFrameLocation, index);
1831            Jump success = jump();
1832
1833            parenthesesState.linkAlternativeBacktracks(this);
1834
1835            loadFromFrame(parenthesesFrameLocation, index);
1836            state.jumpToBacktrack(this);
1837
1838            success.link(this);
1839
1840            state.checkedTotal += countCheckedAfterAssertion;
1841        }
1842    }
1843
1844    void generateTerm(TermGenerationState& state)
1845    {
1846        PatternTerm& term = state.term();
1847
1848        switch (term.type) {
1849        case PatternTerm::TypeAssertionBOL:
1850            generateAssertionBOL(state);
1851            break;
1852
1853        case PatternTerm::TypeAssertionEOL:
1854            generateAssertionEOL(state);
1855            break;
1856
1857        case PatternTerm::TypeAssertionWordBoundary:
1858            generateAssertionWordBoundary(state);
1859            break;
1860
1861        case PatternTerm::TypePatternCharacter:
1862            switch (term.quantityType) {
1863            case QuantifierFixedCount:
1864                if (term.quantityCount == 1) {
1865                    if (state.isSinglePatternCharacterLookaheadTerm() && (state.lookaheadTerm().inputPosition == (term.inputPosition + 1))) {
1866                        generatePatternCharacterPair(state);
1867                        state.nextTerm();
1868                    } else
1869                        generatePatternCharacterSingle(state);
1870                } else
1871                    generatePatternCharacterFixed(state);
1872                break;
1873            case QuantifierGreedy:
1874                generatePatternCharacterGreedy(state);
1875                break;
1876            case QuantifierNonGreedy:
1877                generatePatternCharacterNonGreedy(state);
1878                break;
1879            }
1880            break;
1881
1882        case PatternTerm::TypeCharacterClass:
1883            switch (term.quantityType) {
1884            case QuantifierFixedCount:
1885                if (term.quantityCount == 1)
1886                    generateCharacterClassSingle(state);
1887                else
1888                    generateCharacterClassFixed(state);
1889                break;
1890            case QuantifierGreedy:
1891                generateCharacterClassGreedy(state);
1892                break;
1893            case QuantifierNonGreedy:
1894                generateCharacterClassNonGreedy(state);
1895                break;
1896            }
1897            break;
1898
1899        case PatternTerm::TypeBackReference:
1900            m_shouldFallBack = true;
1901            break;
1902
1903        case PatternTerm::TypeForwardReference:
1904            break;
1905
1906        case PatternTerm::TypeParenthesesSubpattern:
1907            if (term.quantityCount == 1 && !term.parentheses.isCopy)
1908                generateParenthesesSingle(state);
1909            else if (term.parentheses.isTerminal)
1910                generateParenthesesGreedyNoBacktrack(state);
1911            else
1912                m_shouldFallBack = true;
1913            break;
1914
1915        case PatternTerm::TypeParentheticalAssertion:
1916            generateParentheticalAssertion(state);
1917            break;
1918        }
1919    }
1920
1921    void generateDisjunction(PatternDisjunction* disjunction)
1922    {
1923        TermGenerationState state(disjunction, 0);
1924        state.resetAlternative();
1925
1926        // check availability for the next alternative
1927        int countCheckedForCurrentAlternative = 0;
1928        int countToCheckForFirstAlternative = 0;
1929        bool hasShorterAlternatives = false;
1930        bool setRepeatAlternativeLabels = false;
1931        JumpList notEnoughInputForPreviousAlternative;
1932        Label firstAlternative;
1933        Label firstAlternativeInputChecked;
1934
1935        // The label 'firstAlternative' is used to plant a check to see if there is
1936        // sufficient input available to run the first repeating alternative.
1937        // The label 'firstAlternativeInputChecked' will jump directly to matching
1938        // the first repeating alternative having skipped this check.
1939
1940        if (state.alternativeValid()) {
1941            PatternAlternative* alternative = state.alternative();
1942            if (!alternative->onceThrough()) {
1943                firstAlternative = Label(this);
1944                setRepeatAlternativeLabels = true;
1945            }
1946            countToCheckForFirstAlternative = alternative->m_minimumSize;
1947            state.checkedTotal += countToCheckForFirstAlternative;
1948            if (countToCheckForFirstAlternative)
1949                notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
1950            countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
1951        }
1952
1953        if (setRepeatAlternativeLabels)
1954            firstAlternativeInputChecked = Label(this);
1955
1956        while (state.alternativeValid()) {
1957            PatternAlternative* alternative = state.alternative();
1958            optimizeAlternative(alternative);
1959
1960            // Track whether any alternatives are shorter than the first one.
1961            if (!alternative->onceThrough())
1962                hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative);
1963
1964            for (state.resetTerm(); state.termValid(); state.nextTerm())
1965                generateTerm(state);
1966
1967            // If we get here, the alternative matched.
1968            if (m_pattern.m_body->m_callFrameSize)
1969                addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
1970
1971            ASSERT(index != returnRegister);
1972            if (m_pattern.m_body->m_hasFixedSize) {
1973                move(index, returnRegister);
1974                if (alternative->m_minimumSize)
1975                    sub32(Imm32(alternative->m_minimumSize), returnRegister);
1976
1977                store32(returnRegister, output);
1978            } else
1979                load32(Address(output), returnRegister);
1980
1981            store32(index, Address(output, 4));
1982
1983            generateReturn();
1984
1985            state.nextAlternative();
1986            if (alternative->onceThrough() && state.alternativeValid())
1987                state.clearBacktrack();
1988
1989            // if there are any more alternatives, plant the check for input before looping.
1990            if (state.alternativeValid()) {
1991                state.setJumpListToPriorParen(0);
1992                PatternAlternative* nextAlternative = state.alternative();
1993                if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) {
1994                    // We have handled non-repeating alternatives, jump to next iteration
1995                    // and loop over repeating alternatives.
1996                    state.jumpToBacktrack(this);
1997
1998                    countToCheckForFirstAlternative = nextAlternative->m_minimumSize;
1999
2000                    // If we get here, there the last input checked failed.
2001                    notEnoughInputForPreviousAlternative.link(this);
2002
2003                    state.linkAlternativeBacktracks(this);
2004
2005                    // Back up to start the looping alternatives.
2006                    if (countCheckedForCurrentAlternative)
2007                        sub32(Imm32(countCheckedForCurrentAlternative), index);
2008
2009                    firstAlternative = Label(this);
2010
2011                    state.checkedTotal = countToCheckForFirstAlternative;
2012                    if (countToCheckForFirstAlternative)
2013                        notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative));
2014
2015                    countCheckedForCurrentAlternative = countToCheckForFirstAlternative;
2016
2017                    firstAlternativeInputChecked = Label(this);
2018
2019                    setRepeatAlternativeLabels = true;
2020                } else {
2021                    int countToCheckForNextAlternative = nextAlternative->m_minimumSize;
2022
2023                    if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one.
2024                        // If we get here, then the last input checked failed.
2025                        notEnoughInputForPreviousAlternative.link(this);
2026
2027                        // Check if sufficent input available to run the next alternative
2028                        notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
2029                        // We are now in the correct state to enter the next alternative; this add is only required
2030                        // to mirror and revert operation of the sub32, just below.
2031                        add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
2032
2033                        // If we get here, then the last input checked passed.
2034                        state.linkAlternativeBacktracks(this);
2035
2036                        // No need to check if we can run the next alternative, since it is shorter -
2037                        // just update index.
2038                        sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index);
2039                    } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one.
2040                        // If we get here, then the last input checked failed.
2041                        // If there is insufficient input to run the current alternative, and the next alternative is longer,
2042                        // then there is definitely not enough input to run it - don't even check. Just adjust index, as if
2043                        // we had checked.
2044                        notEnoughInputForPreviousAlternative.link(this);
2045                        add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index);
2046                        notEnoughInputForPreviousAlternative.append(jump());
2047
2048                        // The next alternative is longer than the current one; check the difference.
2049                        state.linkAlternativeBacktracks(this);
2050
2051                        notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative));
2052                    } else { // CASE 3: Both alternatives are the same length.
2053                        ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative);
2054
2055                        // If the next alterative is the same length as this one, then no need to check the input -
2056                        // if there was sufficent input to run the current alternative then there is sufficient
2057                        // input to run the next one; if not, there isn't.
2058                        state.linkAlternativeBacktracks(this);
2059                    }
2060                    state.checkedTotal -= countCheckedForCurrentAlternative;
2061                    countCheckedForCurrentAlternative = countToCheckForNextAlternative;
2062                    state.checkedTotal += countCheckedForCurrentAlternative;
2063                }
2064            }
2065        }
2066
2067        // If we get here, all Alternatives failed...
2068
2069        state.checkedTotal -= countCheckedForCurrentAlternative;
2070
2071        if (!setRepeatAlternativeLabels) {
2072            // If there are no alternatives that need repeating (all are marked 'onceThrough') then just link
2073            // the match failures to this point, and fall through to the return below.
2074            state.linkAlternativeBacktracks(this, true);
2075
2076            notEnoughInputForPreviousAlternative.link(this);
2077        } else {
2078            // How much more input need there be to be able to retry from the first alternative?
2079            // examples:
2080            //   /yarr_jit/ or /wrec|pcre/
2081            //     In these examples we need check for one more input before looping.
2082            //   /yarr_jit|pcre/
2083            //     In this case we need check for 5 more input to loop (+4 to allow for the first alterative
2084            //     being four longer than the last alternative checked, and another +1 to effectively move
2085            //     the start position along by one).
2086            //   /yarr|rules/ or /wrec|notsomuch/
2087            //     In these examples, provided that there was sufficient input to have just been matching for
2088            //     the second alternative we can loop without checking for available input (since the second
2089            //     alternative is longer than the first).  In the latter example we need to decrement index
2090            //     (by 4) so the start position is only progressed by 1 from the last iteration.
2091            int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1;
2092
2093            // First, deal with the cases where there was sufficient input to try the last alternative.
2094            if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below.
2095                state.linkAlternativeBacktracks(this, true);
2096            else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop!
2097                state.linkAlternativeBacktracksTo(this, firstAlternativeInputChecked, true);
2098            else { // no need to check the input, but we do have some bookkeeping to do first.
2099                state.linkAlternativeBacktracks(this, true);
2100
2101                // Where necessary update our preserved start position.
2102                if (!m_pattern.m_body->m_hasFixedSize) {
2103                    move(index, regT0);
2104                    sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
2105                    store32(regT0, Address(output));
2106                }
2107
2108                // Update index if necessary, and loop (without checking).
2109                if (incrementForNextIter)
2110                    add32(Imm32(incrementForNextIter), index);
2111                jump().linkTo(firstAlternativeInputChecked, this);
2112            }
2113
2114            notEnoughInputForPreviousAlternative.link(this);
2115            // Update our idea of the start position, if we're tracking this.
2116            if (!m_pattern.m_body->m_hasFixedSize) {
2117                if (countCheckedForCurrentAlternative - 1) {
2118                    move(index, regT0);
2119                    sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0);
2120                    store32(regT0, Address(output));
2121                } else
2122                    store32(index, Address(output));
2123            }
2124
2125            // Check if there is sufficent input to run the first alternative again.
2126            jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this);
2127            // No - insufficent input to run the first alteranative, are there any other alternatives we
2128            // might need to check?  If so, the last check will have left the index incremented by
2129            // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative
2130            // LESS input is available, to have the effect of just progressing the start position by 1
2131            // from the last iteration.  If this check passes we can just jump up to the check associated
2132            // with the first alternative in the loop.  This is a bit sad, since we'll end up trying the
2133            // first alternative again, and this check will fail (otherwise the check planted just above
2134            // here would have passed).  This is a bit sad, however it saves trying to do something more
2135            // complex here in compilation, and in the common case we should end up coallescing the checks.
2136            //
2137            // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least
2138            // of the minimum-alternative-lengths.  E.g. if I have two alternatives of length 200 and 150,
2139            // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there
2140            // is sufficient input to run either alternative (constantly failing).  If there had been only
2141            // one alternative, or if the shorter alternative had come first, we would have terminated
2142            // immediately. :-/
2143            if (hasShorterAlternatives)
2144                jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this);
2145            // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true,
2146            // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ...
2147            // but since we're about to return a failure this doesn't really matter!)
2148        }
2149
2150        if (m_pattern.m_body->m_callFrameSize)
2151            addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
2152
2153        move(TrustedImm32(-1), returnRegister);
2154
2155        generateReturn();
2156
2157        m_expressionState.emitParenthesesTail(this);
2158        m_expressionState.emitIndirectJumpTable(this);
2159        m_expressionState.linkToNextIteration(this);
2160    }
2161
2162    void generateEnter()
2163    {
2164#if CPU(X86_64)
2165        push(X86Registers::ebp);
2166        move(stackPointerRegister, X86Registers::ebp);
2167        push(X86Registers::ebx);
2168#elif CPU(X86)
2169        push(X86Registers::ebp);
2170        move(stackPointerRegister, X86Registers::ebp);
2171        // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
2172        push(X86Registers::ebx);
2173        push(X86Registers::edi);
2174        push(X86Registers::esi);
2175        // load output into edi (2 = saved ebp + return address).
2176    #if COMPILER(MSVC)
2177        loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
2178        loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
2179        loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
2180        loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
2181    #else
2182        loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
2183    #endif
2184#elif CPU(ARM)
2185        push(ARMRegisters::r4);
2186        push(ARMRegisters::r5);
2187        push(ARMRegisters::r6);
2188#if CPU(ARM_TRADITIONAL)
2189        push(ARMRegisters::r8); // scratch register
2190#endif
2191        move(ARMRegisters::r3, output);
2192#elif CPU(SH4)
2193        push(SH4Registers::r11);
2194        push(SH4Registers::r13);
2195#elif CPU(MIPS)
2196        // Do nothing.
2197#endif
2198    }
2199
2200    void generateReturn()
2201    {
2202#if CPU(X86_64)
2203        pop(X86Registers::ebx);
2204        pop(X86Registers::ebp);
2205#elif CPU(X86)
2206        pop(X86Registers::esi);
2207        pop(X86Registers::edi);
2208        pop(X86Registers::ebx);
2209        pop(X86Registers::ebp);
2210#elif CPU(ARM)
2211#if CPU(ARM_TRADITIONAL)
2212        pop(ARMRegisters::r8); // scratch register
2213#endif
2214        pop(ARMRegisters::r6);
2215        pop(ARMRegisters::r5);
2216        pop(ARMRegisters::r4);
2217#elif CPU(SH4)
2218        pop(SH4Registers::r13);
2219        pop(SH4Registers::r11);
2220#elif CPU(MIPS)
2221        // Do nothing
2222#endif
2223        ret();
2224    }
2225
2226public:
2227    YarrGenerator(YarrPattern& pattern)
2228        : m_pattern(pattern)
2229        , m_shouldFallBack(false)
2230    {
2231    }
2232
2233    void generate()
2234    {
2235        generateEnter();
2236
2237        if (!m_pattern.m_body->m_hasFixedSize)
2238            store32(index, Address(output));
2239
2240        if (m_pattern.m_body->m_callFrameSize)
2241            subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister);
2242
2243        generateDisjunction(m_pattern.m_body);
2244    }
2245
2246    void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject)
2247    {
2248        generate();
2249
2250        LinkBuffer patchBuffer(this, globalData->regexAllocator.poolForSize(size()), 0);
2251
2252        for (unsigned i = 0; i < m_expressionState.m_backtrackRecords.size(); ++i)
2253            patchBuffer.patch(m_expressionState.m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_expressionState.m_backtrackRecords[i].backtrackLocation));
2254
2255        jitObject.set(patchBuffer.finalizeCode());
2256        jitObject.setFallBack(m_shouldFallBack);
2257    }
2258
2259private:
2260    YarrPattern& m_pattern;
2261    bool m_shouldFallBack;
2262    GenerationState m_expressionState;
2263};
2264
2265void jitCompile(YarrPattern& pattern, JSGlobalData* globalData, YarrCodeBlock& jitObject)
2266{
2267    YarrGenerator(pattern).compile(globalData, jitObject);
2268}
2269
2270int execute(YarrCodeBlock& jitObject, const UChar* input, unsigned start, unsigned length, int* output)
2271{
2272    return jitObject.execute(input, start, length, output);
2273}
2274
2275}}
2276
2277#endif
2278