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