• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  
35  using namespace WTF;
36  
37  namespace JSC { namespace Yarr {
38  
39  class 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  
optimizeAlternative(PatternAlternative * alternative)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  
matchCharacterClassRange(RegisterID character,JumpList & failures,JumpList & matchDest,const CharacterRange * ranges,unsigned count,unsigned * matchIndex,const UChar * matches,unsigned matchCount)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  
matchCharacterClass(RegisterID character,JumpList & matchDest,const CharacterClass * charClass)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!
jumpIfNoAvailableInput(unsigned countToCheck)231      Jump jumpIfNoAvailableInput(unsigned countToCheck)
232      {
233          add32(Imm32(countToCheck), index);
234          return branch32(Above, index, length);
235      }
236  
jumpIfAvailableInput(unsigned countToCheck)237      Jump jumpIfAvailableInput(unsigned countToCheck)
238      {
239          add32(Imm32(countToCheck), index);
240          return branch32(BelowOrEqual, index, length);
241      }
242  
checkInput()243      Jump checkInput()
244      {
245          return branch32(BelowOrEqual, index, length);
246      }
247  
atEndOfInput()248      Jump atEndOfInput()
249      {
250          return branch32(Equal, index, length);
251      }
252  
notAtEndOfInput()253      Jump notAtEndOfInput()
254      {
255          return branch32(NotEqual, index, length);
256      }
257  
jumpIfCharEquals(UChar ch,int inputPosition)258      Jump jumpIfCharEquals(UChar ch, int inputPosition)
259      {
260          return branch16(Equal, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
261      }
262  
jumpIfCharNotEquals(UChar ch,int inputPosition)263      Jump jumpIfCharNotEquals(UChar ch, int inputPosition)
264      {
265          return branch16(NotEqual, BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), Imm32(ch));
266      }
267  
readCharacter(int inputPosition,RegisterID reg)268      void readCharacter(int inputPosition, RegisterID reg)
269      {
270          load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
271      }
272  
storeToFrame(RegisterID reg,unsigned frameLocation)273      void storeToFrame(RegisterID reg, unsigned frameLocation)
274      {
275          poke(reg, frameLocation);
276      }
277  
storeToFrame(TrustedImm32 imm,unsigned frameLocation)278      void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
279      {
280          poke(imm, frameLocation);
281      }
282  
storeToFrameWithPatch(unsigned frameLocation)283      DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
284      {
285          return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
286      }
287  
loadFromFrame(unsigned frameLocation,RegisterID reg)288      void loadFromFrame(unsigned frameLocation, RegisterID reg)
289      {
290          peek(reg, frameLocation);
291      }
292  
loadFromFrameAndJump(unsigned frameLocation)293      void loadFromFrameAndJump(unsigned frameLocation)
294      {
295          jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
296      }
297  
298      struct IndirectJumpEntry {
IndirectJumpEntryJSC::Yarr::YarrGenerator::IndirectJumpEntry299          IndirectJumpEntry(int32_t stackOffset)
300              : m_stackOffset(stackOffset)
301          {
302          }
303  
IndirectJumpEntryJSC::Yarr::YarrGenerator::IndirectJumpEntry304          IndirectJumpEntry(int32_t stackOffset, Jump jump)
305              : m_stackOffset(stackOffset)
306          {
307              addJump(jump);
308          }
309  
IndirectJumpEntryJSC::Yarr::YarrGenerator::IndirectJumpEntry310          IndirectJumpEntry(int32_t stackOffset, DataLabelPtr dataLabel)
311          : m_stackOffset(stackOffset)
312          {
313              addDataLabel(dataLabel);
314          }
315  
addJumpJSC::Yarr::YarrGenerator::IndirectJumpEntry316          void addJump(Jump jump)
317          {
318              m_relJumps.append(jump);
319          }
320  
addDataLabelJSC::Yarr::YarrGenerator::IndirectJumpEntry321          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  
AlternativeBacktrackRecordJSC::Yarr::YarrGenerator::AlternativeBacktrackRecord335          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  
GenerationStateJSC::Yarr::YarrGenerator::GenerationState348          GenerationState()
349              : m_parenNestingLevel(0)
350          {
351          }
352  
addIndirectJumpEntryJSC::Yarr::YarrGenerator::GenerationState353          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  
addIndirectJumpEntryJSC::Yarr::YarrGenerator::GenerationState367          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  
addIndirectJumpEntryJSC::Yarr::YarrGenerator::GenerationState377          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  
emitIndirectJumpTableJSC::Yarr::YarrGenerator::GenerationState391          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  
incrementParenNestingLevelJSC::Yarr::YarrGenerator::GenerationState408          void incrementParenNestingLevel()
409          {
410              ++m_parenNestingLevel;
411          }
412  
decrementParenNestingLevelJSC::Yarr::YarrGenerator::GenerationState413          void decrementParenNestingLevel()
414          {
415              --m_parenNestingLevel;
416          }
417  
addParenthesesTailJSC::Yarr::YarrGenerator::GenerationState418          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  
emitParenthesesTailJSC::Yarr::YarrGenerator::GenerationState427          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  
addJumpToNextInterationJSC::Yarr::YarrGenerator::GenerationState444          void addJumpToNextInteration(Jump jump)
445          {
446              m_jumpsToNextInteration.append(jump);
447          }
448  
addJumpsToNextInterationJSC::Yarr::YarrGenerator::GenerationState449          void addJumpsToNextInteration(JumpList jumps)
450          {
451              m_jumpsToNextInteration.append(jumps);
452          }
453  
addDataLabelToNextIterationJSC::Yarr::YarrGenerator::GenerationState454          void addDataLabelToNextIteration(DataLabelPtr dataLabel)
455          {
456              m_dataPtrsToNextIteration.append(dataLabel);
457          }
458  
linkToNextIterationJSC::Yarr::YarrGenerator::GenerationState459          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  
linkToNextIterationJSC::Yarr::YarrGenerator::GenerationState474          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  
BacktrackDestinationJSC::Yarr::YarrGenerator::BacktrackDestination498          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  
BacktrackDestinationJSC::Yarr::YarrGenerator::BacktrackDestination508          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  
BacktrackDestinationJSC::Yarr::YarrGenerator::BacktrackDestination519          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  
clearJSC::Yarr::YarrGenerator::BacktrackDestination530          void clear(bool doDataLabelClear = true)
531          {
532              m_backtrackType = NoBacktrack;
533              if (doDataLabelClear)
534                  clearDataLabel();
535              m_nextBacktrack = 0;
536          }
537  
clearDataLabelJSC::Yarr::YarrGenerator::BacktrackDestination538          void clearDataLabel()
539          {
540              m_dataLabelPtr = DataLabelPtr();
541          }
542  
hasDestinationJSC::Yarr::YarrGenerator::BacktrackDestination543          bool hasDestination()
544          {
545              return (m_backtrackType != NoBacktrack);
546          }
547  
isStackOffsetJSC::Yarr::YarrGenerator::BacktrackDestination548          bool isStackOffset()
549          {
550              return (m_backtrackType == BacktrackStackOffset);
551          }
552  
isLabelJSC::Yarr::YarrGenerator::BacktrackDestination553          bool isLabel()
554          {
555              return (m_backtrackType == BacktrackLabel);
556          }
557  
isJumpListJSC::Yarr::YarrGenerator::BacktrackDestination558          bool isJumpList()
559          {
560              return (m_backtrackType == BacktrackJumpList);
561          }
562  
hasDataLabelJSC::Yarr::YarrGenerator::BacktrackDestination563          bool hasDataLabel()
564          {
565              return m_dataLabelPtr.isSet();
566          }
567  
copyTargetJSC::Yarr::YarrGenerator::BacktrackDestination568          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  
copyToJSC::Yarr::YarrGenerator::BacktrackDestination581          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  
addBacktrackJumpJSC::Yarr::YarrGenerator::BacktrackDestination594          void addBacktrackJump(Jump jump)
595          {
596              m_backTrackJumps.append(jump);
597          }
598  
setStackOffsetJSC::Yarr::YarrGenerator::BacktrackDestination599          void setStackOffset(int32_t stackOffset)
600          {
601              m_backtrackType = BacktrackStackOffset;
602              m_backtrackStackOffset = stackOffset;
603          }
604  
setLabelJSC::Yarr::YarrGenerator::BacktrackDestination605          void setLabel(Label label)
606          {
607              m_backtrackType = BacktrackLabel;
608              m_backtrackLabel = label;
609          }
610  
setNextBacktrackLabelJSC::Yarr::YarrGenerator::BacktrackDestination611          void setNextBacktrackLabel(Label label)
612          {
613              if (m_nextBacktrack)
614                  m_nextBacktrack->setLabel(label);
615          }
616  
propagateBacktrackToLabelJSC::Yarr::YarrGenerator::BacktrackDestination617          void propagateBacktrackToLabel(const BacktrackDestination& rhs)
618          {
619              if (!m_backtrackToLabel && rhs.m_backtrackToLabel)
620                  m_backtrackToLabel = rhs.m_backtrackToLabel;
621          }
622  
setBacktrackToLabelJSC::Yarr::YarrGenerator::BacktrackDestination623          void setBacktrackToLabel(Label* backtrackToLabel)
624          {
625              if (!m_backtrackToLabel)
626                  m_backtrackToLabel = backtrackToLabel;
627          }
628  
hasBacktrackToLabelJSC::Yarr::YarrGenerator::BacktrackDestination629          bool hasBacktrackToLabel()
630          {
631              return m_backtrackToLabel;
632          }
633  
setBacktrackJumpListJSC::Yarr::YarrGenerator::BacktrackDestination634          void setBacktrackJumpList(JumpList* jumpList)
635          {
636              m_backtrackType = BacktrackJumpList;
637              m_backtrackSourceJumps = jumpList;
638          }
639  
setBacktrackSourceLabelJSC::Yarr::YarrGenerator::BacktrackDestination640          void setBacktrackSourceLabel(Label* backtrackSourceLabel)
641          {
642              m_backtrackSourceLabel = backtrackSourceLabel;
643          }
644  
setDataLabelJSC::Yarr::YarrGenerator::BacktrackDestination645          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  
clearSubDataLabelPtrJSC::Yarr::YarrGenerator::BacktrackDestination656          void clearSubDataLabelPtr()
657          {
658              m_subDataLabelPtr = 0;
659          }
660  
setSubDataLabelPtrJSC::Yarr::YarrGenerator::BacktrackDestination661          void setSubDataLabelPtr(DataLabelPtr* subDataLabelPtr)
662          {
663              m_subDataLabelPtr = subDataLabelPtr;
664          }
665  
linkToNextBacktrackJSC::Yarr::YarrGenerator::BacktrackDestination666          void linkToNextBacktrack(BacktrackDestination* nextBacktrack)
667          {
668              m_nextBacktrack = nextBacktrack;
669          }
670  
getStackOffsetJSC::Yarr::YarrGenerator::BacktrackDestination671          int32_t getStackOffset()
672          {
673              ASSERT(m_backtrackType == BacktrackStackOffset);
674              return m_backtrackStackOffset;
675          }
676  
getLabelJSC::Yarr::YarrGenerator::BacktrackDestination677          Label getLabel()
678          {
679              ASSERT(m_backtrackType == BacktrackLabel);
680              return m_backtrackLabel;
681          }
682  
getBacktrackJumpsJSC::Yarr::YarrGenerator::BacktrackDestination683          JumpList& getBacktrackJumps()
684          {
685              return m_backTrackJumps;
686          }
687  
getDataLabelJSC::Yarr::YarrGenerator::BacktrackDestination688          DataLabelPtr& getDataLabel()
689          {
690              return m_dataLabelPtr;
691          }
692  
jumpToBacktrackJSC::Yarr::YarrGenerator::BacktrackDestination693          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  
jumpToBacktrackJSC::Yarr::YarrGenerator::BacktrackDestination708          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  
jumpToBacktrackJSC::Yarr::YarrGenerator::BacktrackDestination723          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  
plantJumpToBacktrackIfExistsJSC::Yarr::YarrGenerator::BacktrackDestination738          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  
linkBacktrackToLabelJSC::Yarr::YarrGenerator::BacktrackDestination766          void linkBacktrackToLabel(Label backtrackLabel)
767          {
768              if (m_backtrackToLabel)
769                  *m_backtrackToLabel = backtrackLabel;
770          }
771  
linkAlternativeBacktracksJSC::Yarr::YarrGenerator::BacktrackDestination772          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  
linkAlternativeBacktracksToJSC::Yarr::YarrGenerator::BacktrackDestination794          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 {
TermGenerationStateJSC::Yarr::YarrGenerator::TermGenerationState821          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  
resetAlternativeJSC::Yarr::YarrGenerator::TermGenerationState830          void resetAlternative()
831          {
832              m_backtrack.clear();
833              alt = 0;
834          }
alternativeValidJSC::Yarr::YarrGenerator::TermGenerationState835          bool alternativeValid()
836          {
837              return alt < disjunction->m_alternatives.size();
838          }
nextAlternativeJSC::Yarr::YarrGenerator::TermGenerationState839          void nextAlternative()
840          {
841              ++alt;
842          }
alternativeJSC::Yarr::YarrGenerator::TermGenerationState843          PatternAlternative* alternative()
844          {
845              return disjunction->m_alternatives[alt];
846          }
isLastAlternativeJSC::Yarr::YarrGenerator::TermGenerationState847          bool isLastAlternative()
848          {
849              return (alt + 1) == disjunction->m_alternatives.size();
850          }
851  
resetTermJSC::Yarr::YarrGenerator::TermGenerationState852          void resetTerm()
853          {
854              ASSERT(alternativeValid());
855              t = 0;
856              m_subParenNum = 0;
857          }
termValidJSC::Yarr::YarrGenerator::TermGenerationState858          bool termValid()
859          {
860              ASSERT(alternativeValid());
861              return t < alternative()->m_terms.size();
862          }
nextTermJSC::Yarr::YarrGenerator::TermGenerationState863          void nextTerm()
864          {
865              ASSERT(alternativeValid());
866              ++t;
867          }
termJSC::Yarr::YarrGenerator::TermGenerationState868          PatternTerm& term()
869          {
870              ASSERT(alternativeValid());
871              return alternative()->m_terms[t];
872          }
isLastTermJSC::Yarr::YarrGenerator::TermGenerationState873          bool isLastTerm()
874          {
875              ASSERT(alternativeValid());
876              return (t + 1) == alternative()->m_terms.size();
877          }
getSubParenNumJSC::Yarr::YarrGenerator::TermGenerationState878          unsigned getSubParenNum()
879          {
880              return m_subParenNum++;
881          }
isMainDisjunctionJSC::Yarr::YarrGenerator::TermGenerationState882          bool isMainDisjunction()
883          {
884              return !disjunction->m_parent;
885          }
886  
setJumpListToPriorParenJSC::Yarr::YarrGenerator::TermGenerationState887          void setJumpListToPriorParen(JumpList* jumpList)
888          {
889              m_jumpList = jumpList;
890          }
891  
getJumpListToPriorParenJSC::Yarr::YarrGenerator::TermGenerationState892          JumpList* getJumpListToPriorParen()
893          {
894              return m_jumpList;
895          }
896  
lookaheadTermJSC::Yarr::YarrGenerator::TermGenerationState897          PatternTerm& lookaheadTerm()
898          {
899              ASSERT(alternativeValid());
900              ASSERT((t + 1) < alternative()->m_terms.size());
901              return alternative()->m_terms[t + 1];
902          }
isSinglePatternCharacterLookaheadTermJSC::Yarr::YarrGenerator::TermGenerationState903          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  
inputOffsetJSC::Yarr::YarrGenerator::TermGenerationState912          int inputOffset()
913          {
914              return term().inputPosition - checkedTotal;
915          }
916  
clearBacktrackJSC::Yarr::YarrGenerator::TermGenerationState917          void clearBacktrack()
918          {
919              m_backtrack.clear(false);
920              m_linkedBacktrack = 0;
921          }
922  
jumpToBacktrackJSC::Yarr::YarrGenerator::TermGenerationState923          void jumpToBacktrack(MacroAssembler* masm)
924          {
925              m_backtrack.jumpToBacktrack(masm);
926          }
927  
jumpToBacktrackJSC::Yarr::YarrGenerator::TermGenerationState928          void jumpToBacktrack(YarrGenerator* generator, Jump jump)
929          {
930              m_backtrack.jumpToBacktrack(generator, jump);
931          }
932  
jumpToBacktrackJSC::Yarr::YarrGenerator::TermGenerationState933          void jumpToBacktrack(YarrGenerator* generator, JumpList& jumps)
934          {
935              m_backtrack.jumpToBacktrack(generator, jumps);
936          }
937  
plantJumpToBacktrackIfExistsJSC::Yarr::YarrGenerator::TermGenerationState938          bool plantJumpToBacktrackIfExists(YarrGenerator* generator)
939          {
940              return m_backtrack.plantJumpToBacktrackIfExists(generator);
941          }
942  
linkDataLabelToBacktrackIfExistsJSC::Yarr::YarrGenerator::TermGenerationState943          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  
addBacktrackJumpJSC::Yarr::YarrGenerator::TermGenerationState958          void addBacktrackJump(Jump jump)
959          {
960              m_backtrack.addBacktrackJump(jump);
961          }
962  
setBacktrackDataLabelJSC::Yarr::YarrGenerator::TermGenerationState963          void setBacktrackDataLabel(DataLabelPtr dp)
964          {
965              m_backtrack.setDataLabel(dp);
966          }
967  
setBackTrackStackOffsetJSC::Yarr::YarrGenerator::TermGenerationState968          void setBackTrackStackOffset(int32_t stackOffset)
969          {
970              m_backtrack.setStackOffset(stackOffset);
971          }
972  
setBacktrackLabelJSC::Yarr::YarrGenerator::TermGenerationState973          void setBacktrackLabel(Label label)
974          {
975              m_backtrack.setLabel(label);
976          }
977  
linkAlternativeBacktracksJSC::Yarr::YarrGenerator::TermGenerationState978          void linkAlternativeBacktracks(YarrGenerator* generator, bool nextIteration = false)
979          {
980              m_backtrack.linkAlternativeBacktracks(generator, nextIteration);
981              m_linkedBacktrack = 0;
982          }
983  
linkAlternativeBacktracksToJSC::Yarr::YarrGenerator::TermGenerationState984          void linkAlternativeBacktracksTo(YarrGenerator* generator, Label label, bool nextIteration = false)
985          {
986              m_backtrack.linkAlternativeBacktracksTo(generator, label, nextIteration);
987          }
988  
setBacktrackLinkJSC::Yarr::YarrGenerator::TermGenerationState989          void setBacktrackLink(BacktrackDestination* linkedBacktrack)
990          {
991              m_linkedBacktrack = linkedBacktrack;
992          }
993  
chainBacktracksJSC::Yarr::YarrGenerator::TermGenerationState994          void chainBacktracks(BacktrackDestination* followonBacktrack)
995          {
996              if (m_linkedBacktrack)
997                  m_linkedBacktrack->linkToNextBacktrack(followonBacktrack);
998          }
999  
getBacktrackDestinationJSC::Yarr::YarrGenerator::TermGenerationState1000          BacktrackDestination& getBacktrackDestination()
1001          {
1002              return m_backtrack;
1003          }
1004  
propagateBacktrackingFromJSC::Yarr::YarrGenerator::TermGenerationState1005          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 {
ParenthesesTailJSC::Yarr::YarrGenerator::ParenthesesTail1033          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  
processBacktracksJSC::Yarr::YarrGenerator::ParenthesesTail1041          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  
setNextIterationJSC::Yarr::YarrGenerator::ParenthesesTail1068          void setNextIteration(Label nextIteration)
1069          {
1070              if (!m_nestingLevel && !m_backtrackToLabel.isSet())
1071                  m_backtrackToLabel = nextIteration;
1072          }
1073  
addAfterParenJumpJSC::Yarr::YarrGenerator::ParenthesesTail1074          void addAfterParenJump(Jump jump)
1075          {
1076              m_afterBacktrackJumps.append(jump);
1077          }
1078  
generateCodeJSC::Yarr::YarrGenerator::ParenthesesTail1079          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  
generateAssertionBOL(TermGenerationState & state)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  
generateAssertionEOL(TermGenerationState & state)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.
matchAssertionWordchar(TermGenerationState & state,JumpList & nextIsWordChar,JumpList & 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  
generateAssertionWordBoundary(TermGenerationState & state)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  
generatePatternCharacterSingle(TermGenerationState & state)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  
generatePatternCharacterPair(TermGenerationState & state)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  
generatePatternCharacterFixed(TermGenerationState & state)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  
generatePatternCharacterGreedy(TermGenerationState & state)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  
generatePatternCharacterNonGreedy(TermGenerationState & state)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  
generateCharacterClassSingle(TermGenerationState & state)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  
generateCharacterClassFixed(TermGenerationState & state)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  
generateCharacterClassGreedy(TermGenerationState & state)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  
generateCharacterClassNonGreedy(TermGenerationState & state)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  
generateParenthesesDisjunction(PatternTerm & parenthesesTerm,TermGenerationState & state,unsigned alternativeFrameLocation)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  
generateParenthesesSingle(TermGenerationState & state)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  
generateParenthesesGreedyNoBacktrack(TermGenerationState & state)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  
generateParentheticalAssertion(TermGenerationState & state)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  
generateTerm(TermGenerationState & state)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  
generateDisjunction(PatternDisjunction * disjunction)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  
generateEnter()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  
generateReturn()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  
2226  public:
YarrGenerator(YarrPattern & pattern)2227      YarrGenerator(YarrPattern& pattern)
2228          : m_pattern(pattern)
2229          , m_shouldFallBack(false)
2230      {
2231      }
2232  
generate()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  
compile(JSGlobalData * globalData,YarrCodeBlock & jitObject)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  
2259  private:
2260      YarrPattern& m_pattern;
2261      bool m_shouldFallBack;
2262      GenerationState m_expressionState;
2263  };
2264  
jitCompile(YarrPattern & pattern,JSGlobalData * globalData,YarrCodeBlock & jitObject)2265  void jitCompile(YarrPattern& pattern, JSGlobalData* globalData, YarrCodeBlock& jitObject)
2266  {
2267      YarrGenerator(pattern).compile(globalData, jitObject);
2268  }
2269  
execute(YarrCodeBlock & jitObject,const UChar * input,unsigned start,unsigned length,int * output)2270  int 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