1 | /* |
2 | * Copyright (C) 2009-2018 Apple Inc. All rights reserved. |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions |
6 | * are met: |
7 | * 1. Redistributions of source code must retain the above copyright |
8 | * notice, this list of conditions and the following disclaimer. |
9 | * 2. Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * |
13 | * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
14 | * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
15 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
17 | * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
18 | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
19 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
20 | * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
21 | * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
22 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
23 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
24 | */ |
25 | |
26 | #include "config.h" |
27 | #include "YarrJIT.h" |
28 | |
29 | #include <wtf/ASCIICType.h> |
30 | #include "LinkBuffer.h" |
31 | #include "Options.h" |
32 | #include "VM.h" |
33 | #include "Yarr.h" |
34 | #include "YarrCanonicalize.h" |
35 | |
36 | #include <private/qv4functiontable_p.h> |
37 | |
38 | #if ENABLE(YARR_JIT) |
39 | |
40 | namespace JSC { namespace Yarr { |
41 | |
42 | template<YarrJITCompileMode compileMode> |
43 | class YarrGenerator : private DefaultMacroAssembler { |
44 | |
45 | #if CPU(ARM_THUMB2) |
46 | static const RegisterID input = ARMRegisters::r0; |
47 | static const RegisterID index = ARMRegisters::r1; |
48 | static const RegisterID length = ARMRegisters::r2; |
49 | static const RegisterID output = ARMRegisters::r3; |
50 | |
51 | static const RegisterID regT0 = ARMRegisters::r4; |
52 | static const RegisterID regT1 = ARMRegisters::r5; |
53 | static const RegisterID initialStart = ARMRegisters::r8; |
54 | |
55 | static const RegisterID returnRegister = ARMRegisters::r0; |
56 | static const RegisterID returnRegister2 = ARMRegisters::r1; |
57 | |
58 | #define HAVE_INITIAL_START_REG |
59 | #elif CPU(ARM64) |
60 | // Argument registers |
61 | static const RegisterID input = ARM64Registers::x0; |
62 | static const RegisterID index = ARM64Registers::x1; |
63 | static const RegisterID length = ARM64Registers::x2; |
64 | static const RegisterID output = ARM64Registers::x3; |
65 | static const RegisterID freelistRegister = ARM64Registers::x4; |
66 | static const RegisterID freelistSizeRegister = ARM64Registers::x5; |
67 | |
68 | // Scratch registers |
69 | static const RegisterID regT0 = ARM64Registers::x6; |
70 | static const RegisterID regT1 = ARM64Registers::x7; |
71 | static const RegisterID regT2 = ARM64Registers::x8; |
72 | static const RegisterID remainingMatchCount = ARM64Registers::x9; |
73 | static const RegisterID regUnicodeInputAndTrail = ARM64Registers::x10; |
74 | static const RegisterID initialStart = ARM64Registers::x11; |
75 | static const RegisterID supplementaryPlanesBase = ARM64Registers::x12; |
76 | static const RegisterID surrogateTagMask = ARM64Registers::x13; |
77 | static const RegisterID leadingSurrogateTag = ARM64Registers::x14; |
78 | static const RegisterID trailingSurrogateTag = ARM64Registers::x15; |
79 | |
80 | static const RegisterID returnRegister = ARM64Registers::x0; |
81 | static const RegisterID returnRegister2 = ARM64Registers::x1; |
82 | |
83 | #define HAVE_INITIAL_START_REG |
84 | #define JIT_UNICODE_EXPRESSIONS |
85 | #elif CPU(MIPS) |
86 | static const RegisterID input = MIPSRegisters::a0; |
87 | static const RegisterID index = MIPSRegisters::a1; |
88 | static const RegisterID length = MIPSRegisters::a2; |
89 | static const RegisterID output = MIPSRegisters::a3; |
90 | |
91 | static const RegisterID regT0 = MIPSRegisters::t4; |
92 | static const RegisterID regT1 = MIPSRegisters::t5; |
93 | static const RegisterID initialStart = MIPSRegisters::t6; |
94 | |
95 | static const RegisterID returnRegister = MIPSRegisters::v0; |
96 | static const RegisterID returnRegister2 = MIPSRegisters::v1; |
97 | |
98 | #define HAVE_INITIAL_START_REG |
99 | #elif CPU(X86) |
100 | static const RegisterID input = X86Registers::eax; |
101 | static const RegisterID index = X86Registers::edx; |
102 | static const RegisterID length = X86Registers::ecx; |
103 | static const RegisterID output = X86Registers::edi; |
104 | |
105 | static const RegisterID regT0 = X86Registers::ebx; |
106 | static const RegisterID regT1 = X86Registers::esi; |
107 | |
108 | static const RegisterID returnRegister = X86Registers::eax; |
109 | static const RegisterID returnRegister2 = X86Registers::edx; |
110 | #elif CPU(X86_64) |
111 | #if !OS(WINDOWS) |
112 | // Argument registers |
113 | static const RegisterID input = X86Registers::edi; |
114 | static const RegisterID index = X86Registers::esi; |
115 | static const RegisterID length = X86Registers::edx; |
116 | static const RegisterID output = X86Registers::ecx; |
117 | static const RegisterID freelistRegister = X86Registers::r8; |
118 | static const RegisterID freelistSizeRegister = X86Registers::r9; // Only used during initialization. |
119 | #else |
120 | // If the return value doesn't fit in 64bits, its destination is pointed by rcx and the parameters are shifted. |
121 | // http://msdn.microsoft.com/en-us/library/7572ztz4.aspx |
122 | COMPILE_ASSERT(sizeof(MatchResult) > sizeof(void*), MatchResult_does_not_fit_in_64bits); |
123 | static const RegisterID input = X86Registers::edx; |
124 | static const RegisterID index = X86Registers::r8; |
125 | static const RegisterID length = X86Registers::r9; |
126 | static const RegisterID output = X86Registers::r10; |
127 | #endif |
128 | |
129 | // Scratch registers |
130 | static const RegisterID regT0 = X86Registers::eax; |
131 | #if !OS(WINDOWS) |
132 | static const RegisterID regT1 = X86Registers::r9; |
133 | static const RegisterID regT2 = X86Registers::r10; |
134 | #else |
135 | static const RegisterID regT1 = X86Registers::ecx; |
136 | static const RegisterID regT2 = X86Registers::edi; |
137 | #endif |
138 | |
139 | static const RegisterID initialStart = X86Registers::ebx; |
140 | #if !OS(WINDOWS) |
141 | static const RegisterID remainingMatchCount = X86Registers::r12; |
142 | #else |
143 | static const RegisterID remainingMatchCount = X86Registers::esi; |
144 | #endif |
145 | static const RegisterID regUnicodeInputAndTrail = X86Registers::r13; |
146 | static const RegisterID leadingSurrogateTag = X86Registers::r14; |
147 | static const RegisterID trailingSurrogateTag = X86Registers::r15; |
148 | |
149 | static const RegisterID returnRegister = X86Registers::eax; |
150 | static const RegisterID returnRegister2 = X86Registers::edx; |
151 | |
152 | const TrustedImm32 supplementaryPlanesBase = TrustedImm32(0x10000); |
153 | const TrustedImm32 surrogateTagMask = TrustedImm32(0xfffffc00); |
154 | #define HAVE_INITIAL_START_REG |
155 | #define JIT_UNICODE_EXPRESSIONS |
156 | #endif |
157 | |
158 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
159 | struct ParenContextSizes { |
160 | size_t m_numSubpatterns; |
161 | size_t m_frameSlots; |
162 | |
163 | ParenContextSizes(size_t numSubpatterns, size_t frameSlots) |
164 | : m_numSubpatterns(numSubpatterns) |
165 | , m_frameSlots(frameSlots) |
166 | { |
167 | } |
168 | |
169 | size_t numSubpatterns() { return m_numSubpatterns; } |
170 | |
171 | size_t frameSlots() { return m_frameSlots; } |
172 | }; |
173 | |
174 | struct ParenContext { |
175 | struct ParenContext* next; |
176 | uint32_t begin; |
177 | uint32_t matchAmount; |
178 | uintptr_t returnAddress; |
179 | #if OS(INTEGRITY) |
180 | union { |
181 | struct Subpatterns { |
182 | unsigned start; |
183 | unsigned end; |
184 | } subpatterns[1]; |
185 | uintptr_t frameSlots[1]; |
186 | }; |
187 | #else |
188 | struct Subpatterns { |
189 | unsigned start; |
190 | unsigned end; |
191 | } subpatterns[0]; |
192 | uintptr_t frameSlots[0]; |
193 | #endif |
194 | |
195 | static size_t sizeFor(ParenContextSizes& parenContextSizes) |
196 | { |
197 | return sizeof(ParenContext) + sizeof(Subpatterns) * parenContextSizes.numSubpatterns() + sizeof(uintptr_t) * parenContextSizes.frameSlots(); |
198 | } |
199 | |
200 | static ptrdiff_t nextOffset() |
201 | { |
202 | return offsetof(ParenContext, next); |
203 | } |
204 | |
205 | static ptrdiff_t beginOffset() |
206 | { |
207 | return offsetof(ParenContext, begin); |
208 | } |
209 | |
210 | static ptrdiff_t matchAmountOffset() |
211 | { |
212 | return offsetof(ParenContext, matchAmount); |
213 | } |
214 | |
215 | static ptrdiff_t returnAddressOffset() |
216 | { |
217 | return offsetof(ParenContext, returnAddress); |
218 | } |
219 | |
220 | static ptrdiff_t subpatternOffset(size_t subpattern) |
221 | { |
222 | return offsetof(ParenContext, subpatterns) + (subpattern - 1) * sizeof(Subpatterns); |
223 | } |
224 | |
225 | static ptrdiff_t savedFrameOffset(ParenContextSizes& parenContextSizes) |
226 | { |
227 | return offsetof(ParenContext, subpatterns) + (parenContextSizes.numSubpatterns()) * sizeof(Subpatterns); |
228 | } |
229 | }; |
230 | |
231 | void initParenContextFreeList() |
232 | { |
233 | RegisterID parenContextPointer = regT0; |
234 | RegisterID nextParenContextPointer = regT2; |
235 | |
236 | size_t parenContextSize = ParenContext::sizeFor(m_parenContextSizes); |
237 | |
238 | parenContextSize = WTF::roundUpToMultipleOf<sizeof(uintptr_t)>(x: parenContextSize); |
239 | |
240 | // Check that the paren context is a reasonable size. |
241 | if (parenContextSize > INT16_MAX) |
242 | m_abortExecution.append(jump()); |
243 | |
244 | Jump emptyFreeList = branchTestPtr(Zero, freelistRegister); |
245 | move(freelistRegister, parenContextPointer); |
246 | addPtr(TrustedImm32(parenContextSize), freelistRegister, nextParenContextPointer); |
247 | addPtr(freelistRegister, freelistSizeRegister); |
248 | subPtr(TrustedImm32(parenContextSize), freelistSizeRegister); |
249 | |
250 | Label loopTop(this); |
251 | Jump initDone = branchPtr(Above, nextParenContextPointer, freelistSizeRegister); |
252 | storePtr(nextParenContextPointer, Address(parenContextPointer, ParenContext::nextOffset())); |
253 | move(nextParenContextPointer, parenContextPointer); |
254 | addPtr(TrustedImm32(parenContextSize), parenContextPointer, nextParenContextPointer); |
255 | jump(loopTop); |
256 | |
257 | initDone.link(masm: this); |
258 | storePtr(TrustedImmPtr(nullptr), Address(parenContextPointer, ParenContext::nextOffset())); |
259 | emptyFreeList.link(masm: this); |
260 | } |
261 | |
262 | void allocateParenContext(RegisterID result) |
263 | { |
264 | m_abortExecution.append(branchTestPtr(Zero, freelistRegister)); |
265 | sub32(TrustedImm32(1), remainingMatchCount); |
266 | m_hitMatchLimit.append(branchTestPtr(Zero, remainingMatchCount)); |
267 | move(freelistRegister, result); |
268 | loadPtr(Address(freelistRegister, ParenContext::nextOffset()), freelistRegister); |
269 | } |
270 | |
271 | void freeParenContext(RegisterID headPtrRegister, RegisterID newHeadPtrRegister) |
272 | { |
273 | loadPtr(Address(headPtrRegister, ParenContext::nextOffset()), newHeadPtrRegister); |
274 | storePtr(freelistRegister, Address(headPtrRegister, ParenContext::nextOffset())); |
275 | move(headPtrRegister, freelistRegister); |
276 | } |
277 | |
278 | void saveParenContext(RegisterID parenContextReg, RegisterID tempReg, unsigned firstSubpattern, unsigned lastSubpattern, unsigned subpatternBaseFrameLocation) |
279 | { |
280 | store32(index, Address(parenContextReg, ParenContext::beginOffset())); |
281 | loadFromFrame(frameLocation: subpatternBaseFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), reg: tempReg); |
282 | store32(tempReg, Address(parenContextReg, ParenContext::matchAmountOffset())); |
283 | loadFromFrame(frameLocation: subpatternBaseFrameLocation + BackTrackInfoParentheses::returnAddressIndex(), reg: tempReg); |
284 | storePtr(tempReg, Address(parenContextReg, ParenContext::returnAddressOffset())); |
285 | if (compileMode == IncludeSubpatterns) { |
286 | for (unsigned subpattern = firstSubpattern; subpattern <= lastSubpattern; subpattern++) { |
287 | loadPtr(Address(output, (subpattern << 1) * sizeof(unsigned)), tempReg); |
288 | storePtr(tempReg, Address(parenContextReg, ParenContext::subpatternOffset(subpattern))); |
289 | clearSubpatternStart(subpattern); |
290 | } |
291 | } |
292 | subpatternBaseFrameLocation += YarrStackSpaceForBackTrackInfoParentheses; |
293 | for (unsigned frameLocation = subpatternBaseFrameLocation; frameLocation < m_parenContextSizes.frameSlots(); frameLocation++) { |
294 | loadFromFrame(frameLocation, reg: tempReg); |
295 | storePtr(tempReg, Address(parenContextReg, ParenContext::savedFrameOffset(m_parenContextSizes) + frameLocation * sizeof(uintptr_t))); |
296 | } |
297 | } |
298 | |
299 | void restoreParenContext(RegisterID parenContextReg, RegisterID tempReg, unsigned firstSubpattern, unsigned lastSubpattern, unsigned subpatternBaseFrameLocation) |
300 | { |
301 | load32(Address(parenContextReg, ParenContext::beginOffset()), index); |
302 | storeToFrame(index, subpatternBaseFrameLocation + BackTrackInfoParentheses::beginIndex()); |
303 | load32(Address(parenContextReg, ParenContext::matchAmountOffset()), tempReg); |
304 | storeToFrame(tempReg, subpatternBaseFrameLocation + BackTrackInfoParentheses::matchAmountIndex()); |
305 | loadPtr(Address(parenContextReg, ParenContext::returnAddressOffset()), tempReg); |
306 | storeToFrame(tempReg, subpatternBaseFrameLocation + BackTrackInfoParentheses::returnAddressIndex()); |
307 | if (compileMode == IncludeSubpatterns) { |
308 | for (unsigned subpattern = firstSubpattern; subpattern <= lastSubpattern; subpattern++) { |
309 | loadPtr(Address(parenContextReg, ParenContext::subpatternOffset(subpattern)), tempReg); |
310 | storePtr(tempReg, Address(output, (subpattern << 1) * sizeof(unsigned))); |
311 | } |
312 | } |
313 | subpatternBaseFrameLocation += YarrStackSpaceForBackTrackInfoParentheses; |
314 | for (unsigned frameLocation = subpatternBaseFrameLocation; frameLocation < m_parenContextSizes.frameSlots(); frameLocation++) { |
315 | loadPtr(Address(parenContextReg, ParenContext::savedFrameOffset(m_parenContextSizes) + frameLocation * sizeof(uintptr_t)), tempReg); |
316 | storeToFrame(tempReg, frameLocation); |
317 | } |
318 | } |
319 | #endif |
320 | |
321 | void optimizeAlternative(PatternAlternative* alternative) |
322 | { |
323 | if (!alternative->m_terms.size()) |
324 | return; |
325 | |
326 | for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) { |
327 | PatternTerm& term = alternative->m_terms[i]; |
328 | PatternTerm& nextTerm = alternative->m_terms[i + 1]; |
329 | |
330 | // We can move BMP only character classes after fixed character terms. |
331 | if ((term.type == PatternTerm::TypeCharacterClass) |
332 | && (term.quantityType == QuantifierFixedCount) |
333 | && (!m_decodeSurrogatePairs || (!term.characterClass->m_hasNonBMPCharacters && !term.m_invert)) |
334 | && (nextTerm.type == PatternTerm::TypePatternCharacter) |
335 | && (nextTerm.quantityType == QuantifierFixedCount)) { |
336 | PatternTerm termCopy = term; |
337 | alternative->m_terms[i] = nextTerm; |
338 | alternative->m_terms[i + 1] = termCopy; |
339 | } |
340 | } |
341 | } |
342 | |
343 | void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar32* matches, unsigned matchCount) |
344 | { |
345 | do { |
346 | // pick which range we're going to generate |
347 | int which = count >> 1; |
348 | char lo = ranges[which].begin; |
349 | char hi = ranges[which].end; |
350 | |
351 | // check if there are any ranges or matches below lo. If not, just jl to failure - |
352 | // if there is anything else to check, check that first, if it falls through jmp to failure. |
353 | if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) { |
354 | Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo)); |
355 | |
356 | // generate code for all ranges before this one |
357 | if (which) |
358 | matchCharacterClassRange(character, failures, matchDest, ranges, count: which, matchIndex, matches, matchCount); |
359 | |
360 | while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) { |
361 | matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex]))); |
362 | ++*matchIndex; |
363 | } |
364 | failures.append(jump()); |
365 | |
366 | loOrAbove.link(masm: this); |
367 | } else if (which) { |
368 | Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo)); |
369 | |
370 | matchCharacterClassRange(character, failures, matchDest, ranges, count: which, matchIndex, matches, matchCount); |
371 | failures.append(jump()); |
372 | |
373 | loOrAbove.link(masm: this); |
374 | } else |
375 | failures.append(branch32(LessThan, character, Imm32((unsigned short)lo))); |
376 | |
377 | while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi)) |
378 | ++*matchIndex; |
379 | |
380 | matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi))); |
381 | // fall through to here, the value is above hi. |
382 | |
383 | // shuffle along & loop around if there are any more matches to handle. |
384 | unsigned next = which + 1; |
385 | ranges += next; |
386 | count -= next; |
387 | } while (count); |
388 | } |
389 | |
390 | void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass) |
391 | { |
392 | if (charClass->m_table && !m_decodeSurrogatePairs) { |
393 | ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table)); |
394 | matchDest.append(branchTest8(charClass->m_tableInverted ? Zero : NonZero, tableEntry)); |
395 | return; |
396 | } |
397 | JumpList unicodeFail; |
398 | if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) { |
399 | JumpList isAscii; |
400 | if (charClass->m_matches.size() || charClass->m_ranges.size()) |
401 | isAscii.append(branch32(LessThanOrEqual, character, TrustedImm32(0x7f))); |
402 | |
403 | if (charClass->m_matchesUnicode.size()) { |
404 | for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) { |
405 | UChar32 ch = charClass->m_matchesUnicode[i]; |
406 | matchDest.append(branch32(Equal, character, Imm32(ch))); |
407 | } |
408 | } |
409 | |
410 | if (charClass->m_rangesUnicode.size()) { |
411 | for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) { |
412 | UChar32 lo = charClass->m_rangesUnicode[i].begin; |
413 | UChar32 hi = charClass->m_rangesUnicode[i].end; |
414 | |
415 | Jump below = branch32(LessThan, character, Imm32(lo)); |
416 | matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi))); |
417 | below.link(masm: this); |
418 | } |
419 | } |
420 | |
421 | if (charClass->m_matches.size() || charClass->m_ranges.size()) |
422 | unicodeFail = jump(); |
423 | isAscii.link(masm: this); |
424 | } |
425 | |
426 | if (charClass->m_ranges.size()) { |
427 | unsigned matchIndex = 0; |
428 | JumpList failures; |
429 | matchCharacterClassRange(character, failures, matchDest, ranges: charClass->m_ranges.data(), count: charClass->m_ranges.size(), |
430 | matchIndex: &matchIndex, matches: charClass->m_matches.data(), matchCount: charClass->m_matches.size()); |
431 | while (matchIndex < charClass->m_matches.size()) |
432 | matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++]))); |
433 | |
434 | failures.link(masm: this); |
435 | } else if (charClass->m_matches.size()) { |
436 | // optimization: gather 'a','A' etc back together, can mask & test once. |
437 | Vector<char> matchesAZaz; |
438 | |
439 | for (unsigned i = 0; i < charClass->m_matches.size(); ++i) { |
440 | char ch = charClass->m_matches[i]; |
441 | if (m_pattern.ignoreCase()) { |
442 | if (isASCIILower(c: ch)) { |
443 | matchesAZaz.append(value: ch); |
444 | continue; |
445 | } |
446 | if (isASCIIUpper(c: ch)) |
447 | continue; |
448 | } |
449 | matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch))); |
450 | } |
451 | |
452 | if (unsigned countAZaz = matchesAZaz.size()) { |
453 | or32(TrustedImm32(32), character); |
454 | for (unsigned i = 0; i < countAZaz; ++i) |
455 | matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i]))); |
456 | } |
457 | } |
458 | |
459 | if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) |
460 | unicodeFail.link(masm: this); |
461 | } |
462 | |
463 | // Jumps if input not available; will have (incorrectly) incremented already! |
464 | Jump jumpIfNoAvailableInput(unsigned countToCheck = 0) |
465 | { |
466 | if (countToCheck) |
467 | add32(Imm32(countToCheck), index); |
468 | return branch32(Above, index, length); |
469 | } |
470 | |
471 | Jump jumpIfAvailableInput(unsigned countToCheck) |
472 | { |
473 | add32(Imm32(countToCheck), index); |
474 | return branch32(BelowOrEqual, index, length); |
475 | } |
476 | |
477 | Jump checkNotEnoughInput(RegisterID additionalAmount) |
478 | { |
479 | add32(index, additionalAmount); |
480 | return branch32(Above, additionalAmount, length); |
481 | } |
482 | |
483 | Jump checkInput() |
484 | { |
485 | return branch32(BelowOrEqual, index, length); |
486 | } |
487 | |
488 | Jump atEndOfInput() |
489 | { |
490 | return branch32(Equal, index, length); |
491 | } |
492 | |
493 | Jump notAtEndOfInput() |
494 | { |
495 | return branch32(NotEqual, index, length); |
496 | } |
497 | |
498 | BaseIndex negativeOffsetIndexedAddress(Checked<unsigned> negativeCharacterOffset, RegisterID tempReg, RegisterID indexReg = index) |
499 | { |
500 | RegisterID base = input; |
501 | |
502 | // BaseIndex() addressing can take a int32_t offset. Given that we can have a regular |
503 | // expression that has unsigned character offsets, BaseIndex's signed offset is insufficient |
504 | // for addressing in extreme cases where we might underflow. Therefore we check to see if |
505 | // negativeCharacterOffset will underflow directly or after converting for 16 bit characters. |
506 | // If so, we do our own address calculating by adjusting the base, using the result register |
507 | // as a temp address register. |
508 | unsigned maximumNegativeOffsetForCharacterSize = m_charSize == Char8 ? 0x7fffffff : 0x3fffffff; |
509 | unsigned offsetAdjustAmount = 0x40000000; |
510 | if (negativeCharacterOffset.unsafeGet() > maximumNegativeOffsetForCharacterSize) { |
511 | base = tempReg; |
512 | move(input, base); |
513 | while (negativeCharacterOffset.unsafeGet() > maximumNegativeOffsetForCharacterSize) { |
514 | subPtr(TrustedImm32(offsetAdjustAmount), base); |
515 | if (m_charSize != Char8) |
516 | subPtr(TrustedImm32(offsetAdjustAmount), base); |
517 | negativeCharacterOffset -= offsetAdjustAmount; |
518 | } |
519 | } |
520 | |
521 | Checked<int32_t> characterOffset(-static_cast<int32_t>(negativeCharacterOffset.unsafeGet())); |
522 | |
523 | if (m_charSize == Char8) |
524 | return BaseIndex(input, indexReg, TimesOne, (characterOffset * static_cast<int32_t>(sizeof(char))).unsafeGet()); |
525 | |
526 | return BaseIndex(input, indexReg, TimesTwo, (characterOffset * static_cast<int32_t>(sizeof(UChar))).unsafeGet()); |
527 | } |
528 | |
529 | #ifdef JIT_UNICODE_EXPRESSIONS |
530 | void tryReadUnicodeCharImpl(RegisterID resultReg) |
531 | { |
532 | ASSERT(m_charSize == Char16); |
533 | |
534 | JumpList notUnicode; |
535 | load16Unaligned(regUnicodeInputAndTrail, resultReg); |
536 | and32(surrogateTagMask, resultReg, regT2); |
537 | notUnicode.append(branch32(NotEqual, regT2, leadingSurrogateTag)); |
538 | addPtr(TrustedImm32(2), regUnicodeInputAndTrail); |
539 | getEffectiveAddress(address: BaseIndex(input, length, TimesTwo), dest: regT2); |
540 | notUnicode.append(branch32(AboveOrEqual, regUnicodeInputAndTrail, regT2)); |
541 | load16Unaligned(Address(regUnicodeInputAndTrail), regUnicodeInputAndTrail); |
542 | and32(surrogateTagMask, regUnicodeInputAndTrail, regT2); |
543 | notUnicode.append(branch32(NotEqual, regT2, trailingSurrogateTag)); |
544 | sub32(leadingSurrogateTag, resultReg); |
545 | sub32(trailingSurrogateTag, regUnicodeInputAndTrail); |
546 | lshift32(TrustedImm32(10), resultReg); |
547 | or32(regUnicodeInputAndTrail, resultReg); |
548 | add32(supplementaryPlanesBase, resultReg); |
549 | notUnicode.link(masm: this); |
550 | } |
551 | |
552 | void tryReadUnicodeChar(BaseIndex address, RegisterID resultReg) |
553 | { |
554 | ASSERT(m_charSize == Char16); |
555 | |
556 | getEffectiveAddress(address, dest: regUnicodeInputAndTrail); |
557 | |
558 | if (resultReg == regT0) |
559 | m_tryReadUnicodeCharacterCalls.append(nearCall()); |
560 | else |
561 | tryReadUnicodeCharImpl(resultReg); |
562 | } |
563 | #endif |
564 | |
565 | void readCharacterDontDecodeSurrogates(Checked<unsigned> negativeCharacterOffset, RegisterID resultReg, RegisterID indexReg = index) |
566 | { |
567 | BaseIndex address = negativeOffsetIndexedAddress(negativeCharacterOffset, tempReg: resultReg, indexReg); |
568 | |
569 | if (m_charSize == Char8) |
570 | load8(address, resultReg); |
571 | else |
572 | load16Unaligned(address, resultReg); |
573 | } |
574 | |
575 | void readCharacter(Checked<unsigned> negativeCharacterOffset, RegisterID resultReg, RegisterID indexReg = index) |
576 | { |
577 | BaseIndex address = negativeOffsetIndexedAddress(negativeCharacterOffset, tempReg: resultReg, indexReg); |
578 | |
579 | if (m_charSize == Char8) |
580 | load8(address, resultReg); |
581 | #ifdef JIT_UNICODE_EXPRESSIONS |
582 | else if (m_decodeSurrogatePairs) |
583 | tryReadUnicodeChar(address, resultReg); |
584 | #endif |
585 | else |
586 | load16Unaligned(address, resultReg); |
587 | } |
588 | |
589 | Jump jumpIfCharNotEquals(UChar32 ch, Checked<unsigned> negativeCharacterOffset, RegisterID character) |
590 | { |
591 | readCharacter(negativeCharacterOffset, resultReg: character); |
592 | |
593 | // For case-insesitive compares, non-ascii characters that have different |
594 | // upper & lower case representations are converted to a character class. |
595 | ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode)); |
596 | if (m_pattern.ignoreCase() && isASCIIAlpha(c: ch)) { |
597 | or32(TrustedImm32(0x20), character); |
598 | ch |= 0x20; |
599 | } |
600 | |
601 | return branch32(NotEqual, character, Imm32(ch)); |
602 | } |
603 | |
604 | void storeToFrame(RegisterID reg, unsigned frameLocation) |
605 | { |
606 | poke(reg, frameLocation); |
607 | } |
608 | |
609 | void storeToFrame(TrustedImm32 imm, unsigned frameLocation) |
610 | { |
611 | poke(imm, frameLocation); |
612 | } |
613 | |
614 | #if CPU(ARM64) || CPU(X86_64) |
615 | void storeToFrame(TrustedImmPtr imm, unsigned frameLocation) |
616 | { |
617 | poke(imm, frameLocation); |
618 | } |
619 | #endif |
620 | |
621 | DataLabelPtr storeToFrameWithPatch(unsigned frameLocation) |
622 | { |
623 | return storePtrWithPatch(initialValue: TrustedImmPtr(nullptr), address: Address(stackPointerRegister, frameLocation * sizeof(void*))); |
624 | } |
625 | |
626 | void loadFromFrame(unsigned frameLocation, RegisterID reg) |
627 | { |
628 | peek(dest: reg, index: frameLocation); |
629 | } |
630 | |
631 | void loadFromFrameAndJump(unsigned frameLocation) |
632 | { |
633 | jump(Address(stackPointerRegister, frameLocation * sizeof(void*))); |
634 | } |
635 | |
636 | unsigned alignCallFrameSizeInBytes(unsigned callFrameSize) |
637 | { |
638 | if (!callFrameSize) |
639 | return 0; |
640 | |
641 | callFrameSize *= sizeof(void*); |
642 | if (callFrameSize / sizeof(void*) != m_pattern.m_body->m_callFrameSize) |
643 | CRASH(); |
644 | callFrameSize = (callFrameSize + 0x3f) & ~0x3f; |
645 | return callFrameSize; |
646 | } |
647 | void initCallFrame() |
648 | { |
649 | unsigned callFrameSizeInBytes = alignCallFrameSizeInBytes(callFrameSize: m_pattern.m_body->m_callFrameSize); |
650 | if (callFrameSizeInBytes) { |
651 | #if CPU(X86_64) || CPU(ARM64) |
652 | if (Options::zeroStackFrame()) { |
653 | // We need to start from the stack pointer, because we could have spilled callee saves |
654 | move(stackPointerRegister, regT0); |
655 | subPtr(Imm32(callFrameSizeInBytes), stackPointerRegister); |
656 | if (callFrameSizeInBytes <= 128) { |
657 | for (unsigned offset = 0; offset < callFrameSizeInBytes; offset += sizeof(intptr_t)) |
658 | storePtr(TrustedImmPtr(0), Address(regT0, -8 - int(offset))); |
659 | } else { |
660 | Label zeroLoop = label(); |
661 | subPtr(TrustedImm32(sizeof(intptr_t) * 2), regT0); |
662 | #if CPU(ARM64) |
663 | storePair64(ARM64Registers::zr, ARM64Registers::zr, regT0); |
664 | #else |
665 | storePtr(TrustedImmPtr(0), Address(regT0)); |
666 | storePtr(TrustedImmPtr(0), Address(regT0, sizeof(intptr_t))); |
667 | #endif |
668 | branchPtr(NotEqual, regT0, stackPointerRegister).linkTo(zeroLoop, this); |
669 | } |
670 | } else |
671 | #endif |
672 | subPtr(Imm32(callFrameSizeInBytes), stackPointerRegister); |
673 | |
674 | } |
675 | } |
676 | void removeCallFrame() |
677 | { |
678 | unsigned callFrameSizeInBytes = alignCallFrameSizeInBytes(callFrameSize: m_pattern.m_body->m_callFrameSize); |
679 | if (callFrameSizeInBytes) |
680 | addPtr(Imm32(callFrameSizeInBytes), stackPointerRegister); |
681 | } |
682 | |
683 | void generateFailReturn() |
684 | { |
685 | move(TrustedImmPtr((void*)WTF::notFound), returnRegister); |
686 | move(TrustedImm32(0), returnRegister2); |
687 | generateReturn(); |
688 | } |
689 | |
690 | void generateJITFailReturn() |
691 | { |
692 | if (m_abortExecution.empty() && m_hitMatchLimit.empty()) |
693 | return; |
694 | |
695 | JumpList finishExiting; |
696 | if (!m_abortExecution.empty()) { |
697 | m_abortExecution.link(masm: this); |
698 | move(TrustedImmPtr((void*)static_cast<size_t>(-2)), returnRegister); |
699 | finishExiting.append(jump()); |
700 | } |
701 | |
702 | if (!m_hitMatchLimit.empty()) { |
703 | m_hitMatchLimit.link(masm: this); |
704 | move(TrustedImmPtr((void*)static_cast<size_t>(-1)), returnRegister); |
705 | } |
706 | |
707 | finishExiting.link(masm: this); |
708 | removeCallFrame(); |
709 | move(TrustedImm32(0), returnRegister2); |
710 | generateReturn(); |
711 | } |
712 | |
713 | // Used to record subpatterns, should only be called if compileMode is IncludeSubpatterns. |
714 | void setSubpatternStart(RegisterID reg, unsigned subpattern) |
715 | { |
716 | ASSERT(subpattern); |
717 | // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-( |
718 | store32(reg, Address(output, (subpattern << 1) * sizeof(int))); |
719 | } |
720 | void setSubpatternEnd(RegisterID reg, unsigned subpattern) |
721 | { |
722 | ASSERT(subpattern); |
723 | // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-( |
724 | store32(reg, Address(output, ((subpattern << 1) + 1) * sizeof(int))); |
725 | } |
726 | void clearSubpatternStart(unsigned subpattern) |
727 | { |
728 | ASSERT(subpattern); |
729 | // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-( |
730 | store32(TrustedImm32(-1), Address(output, (subpattern << 1) * sizeof(int))); |
731 | } |
732 | |
733 | void clearMatches(unsigned subpattern, unsigned lastSubpattern) |
734 | { |
735 | for (; subpattern <= lastSubpattern; subpattern++) |
736 | clearSubpatternStart(subpattern); |
737 | } |
738 | |
739 | // We use one of three different strategies to track the start of the current match, |
740 | // while matching. |
741 | // 1) If the pattern has a fixed size, do nothing! - we calculate the value lazily |
742 | // at the end of matching. This is irrespective of compileMode, and in this case |
743 | // these methods should never be called. |
744 | // 2) If we're compiling IncludeSubpatterns, 'output' contains a pointer to an output |
745 | // vector, store the match start in the output vector. |
746 | // 3) If we're compiling MatchOnly, 'output' is unused, store the match start directly |
747 | // in this register. |
748 | void setMatchStart(RegisterID reg) |
749 | { |
750 | ASSERT(!m_pattern.m_body->m_hasFixedSize); |
751 | if (compileMode == IncludeSubpatterns) |
752 | store32(reg, output); |
753 | else |
754 | move(reg, output); |
755 | } |
756 | void getMatchStart(RegisterID reg) |
757 | { |
758 | ASSERT(!m_pattern.m_body->m_hasFixedSize); |
759 | if (compileMode == IncludeSubpatterns) |
760 | load32(output, reg); |
761 | else |
762 | move(output, reg); |
763 | } |
764 | |
765 | enum YarrOpCode { |
766 | // These nodes wrap body alternatives - those in the main disjunction, |
767 | // rather than subpatterns or assertions. These are chained together in |
768 | // a doubly linked list, with a 'begin' node for the first alternative, |
769 | // a 'next' node for each subsequent alternative, and an 'end' node at |
770 | // the end. In the case of repeating alternatives, the 'end' node also |
771 | // has a reference back to 'begin'. |
772 | OpBodyAlternativeBegin, |
773 | OpBodyAlternativeNext, |
774 | OpBodyAlternativeEnd, |
775 | // Similar to the body alternatives, but used for subpatterns with two |
776 | // or more alternatives. |
777 | OpNestedAlternativeBegin, |
778 | OpNestedAlternativeNext, |
779 | OpNestedAlternativeEnd, |
780 | // Used for alternatives in subpatterns where there is only a single |
781 | // alternative (backtracking is easier in these cases), or for alternatives |
782 | // which never need to be backtracked (those in parenthetical assertions, |
783 | // terminal subpatterns). |
784 | OpSimpleNestedAlternativeBegin, |
785 | OpSimpleNestedAlternativeNext, |
786 | OpSimpleNestedAlternativeEnd, |
787 | // Used to wrap 'Once' subpattern matches (quantityMaxCount == 1). |
788 | OpParenthesesSubpatternOnceBegin, |
789 | OpParenthesesSubpatternOnceEnd, |
790 | // Used to wrap 'Terminal' subpattern matches (at the end of the regexp). |
791 | OpParenthesesSubpatternTerminalBegin, |
792 | OpParenthesesSubpatternTerminalEnd, |
793 | // Used to wrap generic captured matches |
794 | OpParenthesesSubpatternBegin, |
795 | OpParenthesesSubpatternEnd, |
796 | // Used to wrap parenthetical assertions. |
797 | OpParentheticalAssertionBegin, |
798 | OpParentheticalAssertionEnd, |
799 | // Wraps all simple terms (pattern characters, character classes). |
800 | OpTerm, |
801 | // Where an expression contains only 'once through' body alternatives |
802 | // and no repeating ones, this op is used to return match failure. |
803 | OpMatchFailed |
804 | }; |
805 | |
806 | // This structure is used to hold the compiled opcode information, |
807 | // including reference back to the original PatternTerm/PatternAlternatives, |
808 | // and JIT compilation data structures. |
809 | struct YarrOp { |
810 | explicit YarrOp(PatternTerm* term) |
811 | : m_op(OpTerm) |
812 | , m_term(term) |
813 | , m_isDeadCode(false) |
814 | { |
815 | } |
816 | |
817 | explicit YarrOp(YarrOpCode op) |
818 | : m_op(op) |
819 | , m_isDeadCode(false) |
820 | { |
821 | } |
822 | |
823 | // The operation, as a YarrOpCode, and also a reference to the PatternTerm. |
824 | YarrOpCode m_op; |
825 | PatternTerm* m_term = nullptr; |
826 | |
827 | // For alternatives, this holds the PatternAlternative and doubly linked |
828 | // references to this alternative's siblings. In the case of the |
829 | // OpBodyAlternativeEnd node at the end of a section of repeating nodes, |
830 | // m_nextOp will reference the OpBodyAlternativeBegin node of the first |
831 | // repeating alternative. |
832 | PatternAlternative* m_alternative = nullptr; |
833 | size_t m_previousOp = 0; |
834 | size_t m_nextOp = 0; |
835 | |
836 | // Used to record a set of Jumps out of the generated code, typically |
837 | // used for jumps out to backtracking code, and a single reentry back |
838 | // into the code for a node (likely where a backtrack will trigger |
839 | // rematching). |
840 | Label m_reentry; |
841 | JumpList m_jumps; |
842 | |
843 | // Used for backtracking when the prior alternative did not consume any |
844 | // characters but matched. |
845 | Jump m_zeroLengthMatch; |
846 | |
847 | // This flag is used to null out the second pattern character, when |
848 | // two are fused to match a pair together. |
849 | bool m_isDeadCode; |
850 | |
851 | // Currently used in the case of some of the more complex management of |
852 | // 'm_checkedOffset', to cache the offset used in this alternative, to avoid |
853 | // recalculating it. |
854 | Checked<unsigned> m_checkAdjust; |
855 | |
856 | // Used by OpNestedAlternativeNext/End to hold the pointer to the |
857 | // value that will be pushed into the pattern's frame to return to, |
858 | // upon backtracking back into the disjunction. |
859 | DataLabelPtr m_returnAddress; |
860 | }; |
861 | |
862 | // BacktrackingState |
863 | // This class encapsulates information about the state of code generation |
864 | // whilst generating the code for backtracking, when a term fails to match. |
865 | // Upon entry to code generation of the backtracking code for a given node, |
866 | // the Backtracking state will hold references to all control flow sources |
867 | // that are outputs in need of further backtracking from the prior node |
868 | // generated (which is the subsequent operation in the regular expression, |
869 | // and in the m_ops Vector, since we generated backtracking backwards). |
870 | // These references to control flow take the form of: |
871 | // - A jump list of jumps, to be linked to code that will backtrack them |
872 | // further. |
873 | // - A set of DataLabelPtr values, to be populated with values to be |
874 | // treated effectively as return addresses backtracking into complex |
875 | // subpatterns. |
876 | // - A flag indicating that the current sequence of generated code up to |
877 | // this point requires backtracking. |
878 | class BacktrackingState { |
879 | public: |
880 | BacktrackingState() |
881 | : m_pendingFallthrough(false) |
882 | { |
883 | } |
884 | |
885 | // Add a jump or jumps, a return address, or set the flag indicating |
886 | // that the current 'fallthrough' control flow requires backtracking. |
887 | void append(const Jump& jump) |
888 | { |
889 | m_laterFailures.append(jump); |
890 | } |
891 | void append(JumpList& jumpList) |
892 | { |
893 | m_laterFailures.append(other: jumpList); |
894 | } |
895 | void append(const DataLabelPtr& returnAddress) |
896 | { |
897 | m_pendingReturns.append(value: returnAddress); |
898 | } |
899 | void fallthrough() |
900 | { |
901 | ASSERT(!m_pendingFallthrough); |
902 | m_pendingFallthrough = true; |
903 | } |
904 | |
905 | // These methods clear the backtracking state, either linking to the |
906 | // current location, a provided label, or copying the backtracking out |
907 | // to a JumpList. All actions may require code generation to take place, |
908 | // and as such are passed a pointer to the assembler. |
909 | void link(MacroAssembler* assembler) |
910 | { |
911 | if (m_pendingReturns.size()) { |
912 | Label here(assembler); |
913 | for (unsigned i = 0; i < m_pendingReturns.size(); ++i) |
914 | m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here)); |
915 | m_pendingReturns.clear(); |
916 | } |
917 | m_laterFailures.link(masm: assembler); |
918 | m_laterFailures.clear(); |
919 | m_pendingFallthrough = false; |
920 | } |
921 | void linkTo(Label label, MacroAssembler* assembler) |
922 | { |
923 | if (m_pendingReturns.size()) { |
924 | for (unsigned i = 0; i < m_pendingReturns.size(); ++i) |
925 | m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], label)); |
926 | m_pendingReturns.clear(); |
927 | } |
928 | if (m_pendingFallthrough) |
929 | assembler->jump(target: label); |
930 | m_laterFailures.linkTo(label, masm: assembler); |
931 | m_laterFailures.clear(); |
932 | m_pendingFallthrough = false; |
933 | } |
934 | void takeBacktracksToJumpList(JumpList& jumpList, MacroAssembler* assembler) |
935 | { |
936 | if (m_pendingReturns.size()) { |
937 | Label here(assembler); |
938 | for (unsigned i = 0; i < m_pendingReturns.size(); ++i) |
939 | m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here)); |
940 | m_pendingReturns.clear(); |
941 | m_pendingFallthrough = true; |
942 | } |
943 | if (m_pendingFallthrough) |
944 | jumpList.append(jump: assembler->jump()); |
945 | jumpList.append(other: m_laterFailures); |
946 | m_laterFailures.clear(); |
947 | m_pendingFallthrough = false; |
948 | } |
949 | |
950 | bool isEmpty() |
951 | { |
952 | return m_laterFailures.empty() && m_pendingReturns.isEmpty() && !m_pendingFallthrough; |
953 | } |
954 | |
955 | // Called at the end of code generation to link all return addresses. |
956 | void linkDataLabels(DefaultLinkBuffer& linkBuffer) |
957 | { |
958 | ASSERT(isEmpty()); |
959 | for (unsigned i = 0; i < m_backtrackRecords.size(); ++i) |
960 | linkBuffer.patch(m_backtrackRecords[i].m_dataLabel, linkBuffer.locationOf(m_backtrackRecords[i].m_backtrackLocation)); |
961 | } |
962 | |
963 | private: |
964 | struct ReturnAddressRecord { |
965 | ReturnAddressRecord(DataLabelPtr dataLabel, Label backtrackLocation) |
966 | : m_dataLabel(dataLabel) |
967 | , m_backtrackLocation(backtrackLocation) |
968 | { |
969 | } |
970 | |
971 | DataLabelPtr m_dataLabel; |
972 | Label m_backtrackLocation; |
973 | }; |
974 | |
975 | JumpList m_laterFailures; |
976 | bool m_pendingFallthrough; |
977 | Vector<DataLabelPtr, 4> m_pendingReturns; |
978 | Vector<ReturnAddressRecord, 4> m_backtrackRecords; |
979 | }; |
980 | |
981 | // Generation methods: |
982 | // =================== |
983 | |
984 | // This method provides a default implementation of backtracking common |
985 | // to many terms; terms commonly jump out of the forwards matching path |
986 | // on any failed conditions, and add these jumps to the m_jumps list. If |
987 | // no special handling is required we can often just backtrack to m_jumps. |
988 | void backtrackTermDefault(size_t opIndex) |
989 | { |
990 | YarrOp& op = m_ops[opIndex]; |
991 | m_backtrackingState.append(op.m_jumps); |
992 | } |
993 | |
994 | void generateAssertionBOL(size_t opIndex) |
995 | { |
996 | YarrOp& op = m_ops[opIndex]; |
997 | PatternTerm* term = op.m_term; |
998 | |
999 | if (m_pattern.multiline()) { |
1000 | const RegisterID character = regT0; |
1001 | |
1002 | JumpList matchDest; |
1003 | if (!term->inputPosition) |
1004 | matchDest.append(branch32(Equal, index, Imm32(m_checkedOffset.unsafeGet()))); |
1005 | |
1006 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition + 1, resultReg: character); |
1007 | matchCharacterClass(character, matchDest, charClass: m_pattern.newlineCharacterClass()); |
1008 | op.m_jumps.append(jump()); |
1009 | |
1010 | matchDest.link(masm: this); |
1011 | } else { |
1012 | // Erk, really should poison out these alternatives early. :-/ |
1013 | if (term->inputPosition) |
1014 | op.m_jumps.append(jump()); |
1015 | else |
1016 | op.m_jumps.append(branch32(NotEqual, index, Imm32(m_checkedOffset.unsafeGet()))); |
1017 | } |
1018 | } |
1019 | void backtrackAssertionBOL(size_t opIndex) |
1020 | { |
1021 | backtrackTermDefault(opIndex); |
1022 | } |
1023 | |
1024 | void generateAssertionEOL(size_t opIndex) |
1025 | { |
1026 | YarrOp& op = m_ops[opIndex]; |
1027 | PatternTerm* term = op.m_term; |
1028 | |
1029 | if (m_pattern.multiline()) { |
1030 | const RegisterID character = regT0; |
1031 | |
1032 | JumpList matchDest; |
1033 | if (term->inputPosition == m_checkedOffset.unsafeGet()) |
1034 | matchDest.append(atEndOfInput()); |
1035 | |
1036 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition, resultReg: character); |
1037 | matchCharacterClass(character, matchDest, charClass: m_pattern.newlineCharacterClass()); |
1038 | op.m_jumps.append(jump()); |
1039 | |
1040 | matchDest.link(masm: this); |
1041 | } else { |
1042 | if (term->inputPosition == m_checkedOffset.unsafeGet()) |
1043 | op.m_jumps.append(notAtEndOfInput()); |
1044 | // Erk, really should poison out these alternatives early. :-/ |
1045 | else |
1046 | op.m_jumps.append(jump()); |
1047 | } |
1048 | } |
1049 | void backtrackAssertionEOL(size_t opIndex) |
1050 | { |
1051 | backtrackTermDefault(opIndex); |
1052 | } |
1053 | |
1054 | // Also falls though on nextIsNotWordChar. |
1055 | void matchAssertionWordchar(size_t opIndex, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar) |
1056 | { |
1057 | YarrOp& op = m_ops[opIndex]; |
1058 | PatternTerm* term = op.m_term; |
1059 | |
1060 | const RegisterID character = regT0; |
1061 | |
1062 | if (term->inputPosition == m_checkedOffset.unsafeGet()) |
1063 | nextIsNotWordChar.append(atEndOfInput()); |
1064 | |
1065 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition, resultReg: character); |
1066 | |
1067 | CharacterClass* wordcharCharacterClass; |
1068 | |
1069 | if (m_unicodeIgnoreCase) |
1070 | wordcharCharacterClass = m_pattern.wordUnicodeIgnoreCaseCharCharacterClass(); |
1071 | else |
1072 | wordcharCharacterClass = m_pattern.wordcharCharacterClass(); |
1073 | |
1074 | matchCharacterClass(character, matchDest&: nextIsWordChar, charClass: wordcharCharacterClass); |
1075 | } |
1076 | |
1077 | void generateAssertionWordBoundary(size_t opIndex) |
1078 | { |
1079 | YarrOp& op = m_ops[opIndex]; |
1080 | PatternTerm* term = op.m_term; |
1081 | |
1082 | const RegisterID character = regT0; |
1083 | |
1084 | Jump atBegin; |
1085 | JumpList matchDest; |
1086 | if (!term->inputPosition) |
1087 | atBegin = branch32(Equal, index, Imm32(m_checkedOffset.unsafeGet())); |
1088 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition + 1, resultReg: character); |
1089 | |
1090 | CharacterClass* wordcharCharacterClass; |
1091 | |
1092 | if (m_unicodeIgnoreCase) |
1093 | wordcharCharacterClass = m_pattern.wordUnicodeIgnoreCaseCharCharacterClass(); |
1094 | else |
1095 | wordcharCharacterClass = m_pattern.wordcharCharacterClass(); |
1096 | |
1097 | matchCharacterClass(character, matchDest, charClass: wordcharCharacterClass); |
1098 | if (!term->inputPosition) |
1099 | atBegin.link(masm: this); |
1100 | |
1101 | // We fall through to here if the last character was not a wordchar. |
1102 | JumpList nonWordCharThenWordChar; |
1103 | JumpList nonWordCharThenNonWordChar; |
1104 | if (term->invert()) { |
1105 | matchAssertionWordchar(opIndex, nextIsWordChar&: nonWordCharThenNonWordChar, nextIsNotWordChar&: nonWordCharThenWordChar); |
1106 | nonWordCharThenWordChar.append(jump()); |
1107 | } else { |
1108 | matchAssertionWordchar(opIndex, nextIsWordChar&: nonWordCharThenWordChar, nextIsNotWordChar&: nonWordCharThenNonWordChar); |
1109 | nonWordCharThenNonWordChar.append(jump()); |
1110 | } |
1111 | op.m_jumps.append(nonWordCharThenNonWordChar); |
1112 | |
1113 | // We jump here if the last character was a wordchar. |
1114 | matchDest.link(masm: this); |
1115 | JumpList wordCharThenWordChar; |
1116 | JumpList wordCharThenNonWordChar; |
1117 | if (term->invert()) { |
1118 | matchAssertionWordchar(opIndex, nextIsWordChar&: wordCharThenNonWordChar, nextIsNotWordChar&: wordCharThenWordChar); |
1119 | wordCharThenWordChar.append(jump()); |
1120 | } else { |
1121 | matchAssertionWordchar(opIndex, nextIsWordChar&: wordCharThenWordChar, nextIsNotWordChar&: wordCharThenNonWordChar); |
1122 | // This can fall-though! |
1123 | } |
1124 | |
1125 | op.m_jumps.append(wordCharThenWordChar); |
1126 | |
1127 | nonWordCharThenWordChar.link(masm: this); |
1128 | wordCharThenNonWordChar.link(masm: this); |
1129 | } |
1130 | void backtrackAssertionWordBoundary(size_t opIndex) |
1131 | { |
1132 | backtrackTermDefault(opIndex); |
1133 | } |
1134 | |
1135 | #if ENABLE(YARR_JIT_BACKREFERENCES) |
1136 | void matchBackreference(size_t opIndex, JumpList& characterMatchFails, RegisterID character, RegisterID patternIndex, RegisterID patternCharacter) |
1137 | { |
1138 | YarrOp& op = m_ops[opIndex]; |
1139 | PatternTerm* term = op.m_term; |
1140 | unsigned subpatternId = term->backReferenceSubpatternId; |
1141 | |
1142 | Label loop(this); |
1143 | |
1144 | readCharacterDontDecodeSurrogates(negativeCharacterOffset: 0, resultReg: patternCharacter, indexReg: patternIndex); |
1145 | readCharacterDontDecodeSurrogates(negativeCharacterOffset: m_checkedOffset - term->inputPosition, resultReg: character); |
1146 | |
1147 | if (!m_pattern.ignoreCase()) |
1148 | characterMatchFails.append(branch32(NotEqual, character, patternCharacter)); |
1149 | else { |
1150 | Jump charactersMatch = branch32(Equal, character, patternCharacter); |
1151 | ExtendedAddress characterTableEntry(character, reinterpret_cast<intptr_t>(&canonicalTableLChar)); |
1152 | load16(characterTableEntry, character); |
1153 | ExtendedAddress patternTableEntry(patternCharacter, reinterpret_cast<intptr_t>(&canonicalTableLChar)); |
1154 | load16(patternTableEntry, patternCharacter); |
1155 | characterMatchFails.append(branch32(NotEqual, character, patternCharacter)); |
1156 | charactersMatch.link(masm: this); |
1157 | } |
1158 | |
1159 | |
1160 | add32(TrustedImm32(1), index); |
1161 | add32(TrustedImm32(1), patternIndex); |
1162 | |
1163 | branch32(NotEqual, patternIndex, Address(output, ((subpatternId << 1) + 1) * sizeof(int))).linkTo(loop, this); |
1164 | } |
1165 | |
1166 | void generateBackReference(size_t opIndex) |
1167 | { |
1168 | YarrOp& op = m_ops[opIndex]; |
1169 | PatternTerm* term = op.m_term; |
1170 | |
1171 | if (m_pattern.ignoreCase() && m_charSize != Char8) { |
1172 | m_failureReason = JITFailureReason::BackReference; |
1173 | return; |
1174 | } |
1175 | |
1176 | unsigned subpatternId = term->backReferenceSubpatternId; |
1177 | unsigned parenthesesFrameLocation = term->frameLocation; |
1178 | |
1179 | const RegisterID characterOrTemp = regT0; |
1180 | const RegisterID patternIndex = regT1; |
1181 | const RegisterID patternTemp = regT2; |
1182 | |
1183 | storeToFrame(index, parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex()); |
1184 | if (term->quantityType != QuantifierFixedCount || term->quantityMaxCount != 1) |
1185 | storeToFrame(TrustedImm32(0), parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); |
1186 | |
1187 | JumpList matches; |
1188 | |
1189 | if (term->quantityType != QuantifierNonGreedy) { |
1190 | load32(Address(output, (subpatternId << 1) * sizeof(int)), patternIndex); |
1191 | load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternTemp); |
1192 | |
1193 | // An empty match is successful without consuming characters |
1194 | if (term->quantityType != QuantifierFixedCount || term->quantityMaxCount != 1) { |
1195 | matches.append(branch32(Equal, TrustedImm32(-1), patternIndex)); |
1196 | matches.append(branch32(Equal, patternIndex, patternTemp)); |
1197 | } else { |
1198 | Jump zeroLengthMatch = branch32(Equal, TrustedImm32(-1), patternIndex); |
1199 | Jump tryNonZeroMatch = branch32(NotEqual, patternIndex, patternTemp); |
1200 | zeroLengthMatch.link(masm: this); |
1201 | storeToFrame(TrustedImm32(1), parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); |
1202 | matches.append(jump()); |
1203 | tryNonZeroMatch.link(masm: this); |
1204 | } |
1205 | } |
1206 | |
1207 | switch (term->quantityType) { |
1208 | case QuantifierFixedCount: { |
1209 | Label outerLoop(this); |
1210 | |
1211 | // PatternTemp should contain pattern end index at this point |
1212 | sub32(patternIndex, patternTemp); |
1213 | if (m_checkedOffset - term->inputPosition) |
1214 | sub32(Imm32((m_checkedOffset - term->inputPosition).unsafeGet()), patternTemp); |
1215 | op.m_jumps.append(checkNotEnoughInput(additionalAmount: patternTemp)); |
1216 | |
1217 | matchBackreference(opIndex, characterMatchFails&: op.m_jumps, character: characterOrTemp, patternIndex, patternCharacter: patternTemp); |
1218 | |
1219 | if (term->quantityMaxCount != 1) { |
1220 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex(), reg: characterOrTemp); |
1221 | add32(TrustedImm32(1), characterOrTemp); |
1222 | storeToFrame(characterOrTemp, parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); |
1223 | matches.append(branch32(Equal, Imm32(term->quantityMaxCount.unsafeGet()), characterOrTemp)); |
1224 | load32(Address(output, (subpatternId << 1) * sizeof(int)), patternIndex); |
1225 | load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternTemp); |
1226 | jump(outerLoop); |
1227 | } |
1228 | matches.link(masm: this); |
1229 | break; |
1230 | } |
1231 | |
1232 | case QuantifierGreedy: { |
1233 | JumpList incompleteMatches; |
1234 | |
1235 | Label outerLoop(this); |
1236 | |
1237 | // PatternTemp should contain pattern end index at this point |
1238 | sub32(patternIndex, patternTemp); |
1239 | if (m_checkedOffset - term->inputPosition) |
1240 | sub32(Imm32((m_checkedOffset - term->inputPosition).unsafeGet()), patternTemp); |
1241 | matches.append(checkNotEnoughInput(additionalAmount: patternTemp)); |
1242 | |
1243 | matchBackreference(opIndex, characterMatchFails&: incompleteMatches, character: characterOrTemp, patternIndex, patternCharacter: patternTemp); |
1244 | |
1245 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex(), reg: characterOrTemp); |
1246 | add32(TrustedImm32(1), characterOrTemp); |
1247 | storeToFrame(characterOrTemp, parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); |
1248 | if (term->quantityMaxCount != quantifyInfinite) |
1249 | matches.append(branch32(Equal, Imm32(term->quantityMaxCount.unsafeGet()), characterOrTemp)); |
1250 | load32(Address(output, (subpatternId << 1) * sizeof(int)), patternIndex); |
1251 | load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternTemp); |
1252 | |
1253 | // Store current index in frame for restoring after a partial match |
1254 | storeToFrame(index, parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex()); |
1255 | jump(outerLoop); |
1256 | |
1257 | incompleteMatches.link(masm: this); |
1258 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex(), reg: index); |
1259 | |
1260 | matches.link(masm: this); |
1261 | op.m_reentry = label(); |
1262 | break; |
1263 | } |
1264 | |
1265 | case QuantifierNonGreedy: { |
1266 | JumpList incompleteMatches; |
1267 | |
1268 | matches.append(jump()); |
1269 | |
1270 | op.m_reentry = label(); |
1271 | |
1272 | load32(Address(output, (subpatternId << 1) * sizeof(int)), patternIndex); |
1273 | load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternTemp); |
1274 | |
1275 | // An empty match is successful without consuming characters |
1276 | Jump zeroLengthMatch = branch32(Equal, TrustedImm32(-1), patternIndex); |
1277 | Jump tryNonZeroMatch = branch32(NotEqual, patternIndex, patternTemp); |
1278 | zeroLengthMatch.link(masm: this); |
1279 | storeToFrame(TrustedImm32(1), parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); |
1280 | matches.append(jump()); |
1281 | tryNonZeroMatch.link(masm: this); |
1282 | |
1283 | // Check if we have input remaining to match |
1284 | sub32(patternIndex, patternTemp); |
1285 | if (m_checkedOffset - term->inputPosition) |
1286 | sub32(Imm32((m_checkedOffset - term->inputPosition).unsafeGet()), patternTemp); |
1287 | matches.append(checkNotEnoughInput(additionalAmount: patternTemp)); |
1288 | |
1289 | storeToFrame(index, parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex()); |
1290 | |
1291 | matchBackreference(opIndex, characterMatchFails&: incompleteMatches, character: characterOrTemp, patternIndex, patternCharacter: patternTemp); |
1292 | |
1293 | matches.append(jump()); |
1294 | |
1295 | incompleteMatches.link(masm: this); |
1296 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex(), reg: index); |
1297 | |
1298 | matches.link(masm: this); |
1299 | break; |
1300 | } |
1301 | } |
1302 | } |
1303 | void backtrackBackReference(size_t opIndex) |
1304 | { |
1305 | YarrOp& op = m_ops[opIndex]; |
1306 | PatternTerm* term = op.m_term; |
1307 | |
1308 | unsigned subpatternId = term->backReferenceSubpatternId; |
1309 | |
1310 | m_backtrackingState.link(this); |
1311 | op.m_jumps.link(this); |
1312 | |
1313 | JumpList failures; |
1314 | |
1315 | unsigned parenthesesFrameLocation = term->frameLocation; |
1316 | switch (term->quantityType) { |
1317 | case QuantifierFixedCount: |
1318 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex(), reg: index); |
1319 | break; |
1320 | |
1321 | case QuantifierGreedy: { |
1322 | const RegisterID matchAmount = regT0; |
1323 | const RegisterID patternStartIndex = regT1; |
1324 | const RegisterID patternEndIndexOrLen = regT2; |
1325 | |
1326 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex(), reg: matchAmount); |
1327 | failures.append(branchTest32(Zero, matchAmount)); |
1328 | |
1329 | load32(Address(output, (subpatternId << 1) * sizeof(int)), patternStartIndex); |
1330 | load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternEndIndexOrLen); |
1331 | sub32(patternStartIndex, patternEndIndexOrLen); |
1332 | sub32(patternEndIndexOrLen, index); |
1333 | |
1334 | sub32(TrustedImm32(1), matchAmount); |
1335 | storeToFrame(matchAmount, parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); |
1336 | jump(op.m_reentry); |
1337 | break; |
1338 | } |
1339 | |
1340 | case QuantifierNonGreedy: { |
1341 | const RegisterID matchAmount = regT0; |
1342 | |
1343 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex(), reg: matchAmount); |
1344 | if (term->quantityMaxCount != quantifyInfinite) |
1345 | failures.append(branch32(AboveOrEqual, Imm32(term->quantityMaxCount.unsafeGet()), matchAmount)); |
1346 | add32(TrustedImm32(1), matchAmount); |
1347 | storeToFrame(matchAmount, parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); |
1348 | jump(op.m_reentry); |
1349 | break; |
1350 | } |
1351 | } |
1352 | failures.link(masm: this); |
1353 | m_backtrackingState.fallthrough(); |
1354 | } |
1355 | #endif |
1356 | |
1357 | void generatePatternCharacterOnce(size_t opIndex) |
1358 | { |
1359 | YarrOp& op = m_ops[opIndex]; |
1360 | |
1361 | if (op.m_isDeadCode) |
1362 | return; |
1363 | |
1364 | // m_ops always ends with a OpBodyAlternativeEnd or OpMatchFailed |
1365 | // node, so there must always be at least one more node. |
1366 | ASSERT(opIndex + 1 < m_ops.size()); |
1367 | YarrOp* nextOp = &m_ops[opIndex + 1]; |
1368 | |
1369 | PatternTerm* term = op.m_term; |
1370 | UChar32 ch = term->patternCharacter; |
1371 | |
1372 | if ((ch > 0xff) && (m_charSize == Char8)) { |
1373 | // Have a 16 bit pattern character and an 8 bit string - short circuit |
1374 | op.m_jumps.append(jump()); |
1375 | return; |
1376 | } |
1377 | |
1378 | const RegisterID character = regT0; |
1379 | #if CPU(X86_64) || CPU(ARM64) |
1380 | unsigned maxCharactersAtOnce = m_charSize == Char8 ? 8 : 4; |
1381 | #else |
1382 | unsigned maxCharactersAtOnce = m_charSize == Char8 ? 4 : 2; |
1383 | #endif |
1384 | uint64_t ignoreCaseMask = 0; |
1385 | #if CPU(BIG_ENDIAN) |
1386 | uint64_t allCharacters = ch << (m_charSize == Char8 ? 24 : 16); |
1387 | #else |
1388 | uint64_t allCharacters = ch; |
1389 | #endif |
1390 | unsigned numberCharacters; |
1391 | unsigned startTermPosition = term->inputPosition; |
1392 | |
1393 | // For case-insesitive compares, non-ascii characters that have different |
1394 | // upper & lower case representations are converted to a character class. |
1395 | ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode)); |
1396 | |
1397 | if (m_pattern.ignoreCase() && isASCIIAlpha(c: ch)) { |
1398 | #if CPU(BIG_ENDIAN) |
1399 | ignoreCaseMask |= 32 << (m_charSize == Char8 ? 24 : 16); |
1400 | #else |
1401 | ignoreCaseMask |= 32; |
1402 | #endif |
1403 | } |
1404 | |
1405 | for (numberCharacters = 1; numberCharacters < maxCharactersAtOnce && nextOp->m_op == OpTerm; ++numberCharacters, nextOp = &m_ops[opIndex + numberCharacters]) { |
1406 | PatternTerm* nextTerm = nextOp->m_term; |
1407 | |
1408 | // YarrJIT handles decoded surrogate pair as one character if unicode flag is enabled. |
1409 | // Note that the numberCharacters become 1 while the width of the pattern character becomes 32bit in this case. |
1410 | if (nextTerm->type != PatternTerm::TypePatternCharacter |
1411 | || nextTerm->quantityType != QuantifierFixedCount |
1412 | || nextTerm->quantityMaxCount != 1 |
1413 | || nextTerm->inputPosition != (startTermPosition + numberCharacters) |
1414 | || (U16_LENGTH(nextTerm->patternCharacter) != 1 && m_decodeSurrogatePairs)) |
1415 | break; |
1416 | |
1417 | nextOp->m_isDeadCode = true; |
1418 | |
1419 | #if CPU(BIG_ENDIAN) |
1420 | int shiftAmount = (m_charSize == Char8 ? 24 : 16) - ((m_charSize == Char8 ? 8 : 16) * numberCharacters); |
1421 | #else |
1422 | int shiftAmount = (m_charSize == Char8 ? 8 : 16) * numberCharacters; |
1423 | #endif |
1424 | |
1425 | UChar32 currentCharacter = nextTerm->patternCharacter; |
1426 | |
1427 | if ((currentCharacter > 0xff) && (m_charSize == Char8)) { |
1428 | // Have a 16 bit pattern character and an 8 bit string - short circuit |
1429 | op.m_jumps.append(jump()); |
1430 | return; |
1431 | } |
1432 | |
1433 | // For case-insesitive compares, non-ascii characters that have different |
1434 | // upper & lower case representations are converted to a character class. |
1435 | ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(currentCharacter) || isCanonicallyUnique(currentCharacter, m_canonicalMode)); |
1436 | |
1437 | allCharacters |= (static_cast<uint64_t>(currentCharacter) << shiftAmount); |
1438 | |
1439 | if ((m_pattern.ignoreCase()) && (isASCIIAlpha(c: currentCharacter))) |
1440 | ignoreCaseMask |= 32ULL << shiftAmount; |
1441 | } |
1442 | |
1443 | if (m_decodeSurrogatePairs) |
1444 | op.m_jumps.append(jumpIfNoAvailableInput()); |
1445 | |
1446 | if (m_charSize == Char8) { |
1447 | auto check1 = [&] (Checked<unsigned> offset, UChar32 characters) { |
1448 | op.m_jumps.append(jumpIfCharNotEquals(ch: characters, negativeCharacterOffset: offset, character)); |
1449 | }; |
1450 | |
1451 | auto check2 = [&] (Checked<unsigned> offset, uint16_t characters, uint16_t mask) { |
1452 | load16Unaligned(negativeOffsetIndexedAddress(negativeCharacterOffset: offset, tempReg: character), character); |
1453 | if (mask) |
1454 | or32(Imm32(mask), character); |
1455 | op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask))); |
1456 | }; |
1457 | |
1458 | auto check4 = [&] (Checked<unsigned> offset, unsigned characters, unsigned mask) { |
1459 | if (mask) { |
1460 | load32WithUnalignedHalfWords(address: negativeOffsetIndexedAddress(negativeCharacterOffset: offset, tempReg: character), dest: character); |
1461 | if (mask) |
1462 | or32(Imm32(mask), character); |
1463 | op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask))); |
1464 | return; |
1465 | } |
1466 | op.m_jumps.append(branch32WithUnalignedHalfWords(cond: NotEqual, left: negativeOffsetIndexedAddress(negativeCharacterOffset: offset, tempReg: character), right: TrustedImm32(characters))); |
1467 | }; |
1468 | |
1469 | #if CPU(X86_64) || CPU(ARM64) |
1470 | auto check8 = [&] (Checked<unsigned> offset, uint64_t characters, uint64_t mask) { |
1471 | load64(negativeOffsetIndexedAddress(negativeCharacterOffset: offset, tempReg: character), character); |
1472 | if (mask) |
1473 | or64(TrustedImm64(mask), character); |
1474 | op.m_jumps.append(branch64(NotEqual, character, TrustedImm64(characters | mask))); |
1475 | }; |
1476 | #endif |
1477 | |
1478 | switch (numberCharacters) { |
1479 | case 1: |
1480 | // Use 32bit width of allCharacters since Yarr counts surrogate pairs as one character with unicode flag. |
1481 | check1(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff); |
1482 | return; |
1483 | case 2: { |
1484 | check2(m_checkedOffset - startTermPosition, allCharacters & 0xffff, ignoreCaseMask & 0xffff); |
1485 | return; |
1486 | } |
1487 | case 3: { |
1488 | check2(m_checkedOffset - startTermPosition, allCharacters & 0xffff, ignoreCaseMask & 0xffff); |
1489 | check1(m_checkedOffset - startTermPosition - 2, (allCharacters >> 16) & 0xff); |
1490 | return; |
1491 | } |
1492 | case 4: { |
1493 | check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); |
1494 | return; |
1495 | } |
1496 | #if CPU(X86_64) || CPU(ARM64) |
1497 | case 5: { |
1498 | check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); |
1499 | check1(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xff); |
1500 | return; |
1501 | } |
1502 | case 6: { |
1503 | check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); |
1504 | check2(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xffff, (ignoreCaseMask >> 32) & 0xffff); |
1505 | return; |
1506 | } |
1507 | case 7: { |
1508 | check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); |
1509 | check2(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xffff, (ignoreCaseMask >> 32) & 0xffff); |
1510 | check1(m_checkedOffset - startTermPosition - 6, (allCharacters >> 48) & 0xff); |
1511 | return; |
1512 | } |
1513 | case 8: { |
1514 | check8(m_checkedOffset - startTermPosition, allCharacters, ignoreCaseMask); |
1515 | return; |
1516 | } |
1517 | #endif |
1518 | } |
1519 | } else { |
1520 | auto check1 = [&] (Checked<unsigned> offset, UChar32 characters) { |
1521 | op.m_jumps.append(jumpIfCharNotEquals(ch: characters, negativeCharacterOffset: offset, character)); |
1522 | }; |
1523 | |
1524 | auto check2 = [&] (Checked<unsigned> offset, unsigned characters, unsigned mask) { |
1525 | if (mask) { |
1526 | load32WithUnalignedHalfWords(address: negativeOffsetIndexedAddress(negativeCharacterOffset: offset, tempReg: character), dest: character); |
1527 | if (mask) |
1528 | or32(Imm32(mask), character); |
1529 | op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask))); |
1530 | return; |
1531 | } |
1532 | op.m_jumps.append(branch32WithUnalignedHalfWords(cond: NotEqual, left: negativeOffsetIndexedAddress(negativeCharacterOffset: offset, tempReg: character), right: TrustedImm32(characters))); |
1533 | }; |
1534 | |
1535 | #if CPU(X86_64) || CPU(ARM64) |
1536 | auto check4 = [&] (Checked<unsigned> offset, uint64_t characters, uint64_t mask) { |
1537 | load64(negativeOffsetIndexedAddress(negativeCharacterOffset: offset, tempReg: character), character); |
1538 | if (mask) |
1539 | or64(TrustedImm64(mask), character); |
1540 | op.m_jumps.append(branch64(NotEqual, character, TrustedImm64(characters | mask))); |
1541 | }; |
1542 | #endif |
1543 | |
1544 | switch (numberCharacters) { |
1545 | case 1: |
1546 | // Use 32bit width of allCharacters since Yarr counts surrogate pairs as one character with unicode flag. |
1547 | check1(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff); |
1548 | return; |
1549 | case 2: |
1550 | check2(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); |
1551 | return; |
1552 | #if CPU(X86_64) || CPU(ARM64) |
1553 | case 3: |
1554 | check2(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); |
1555 | check1(m_checkedOffset - startTermPosition - 2, (allCharacters >> 32) & 0xffff); |
1556 | return; |
1557 | case 4: |
1558 | check4(m_checkedOffset - startTermPosition, allCharacters, ignoreCaseMask); |
1559 | return; |
1560 | #endif |
1561 | } |
1562 | } |
1563 | } |
1564 | void backtrackPatternCharacterOnce(size_t opIndex) |
1565 | { |
1566 | backtrackTermDefault(opIndex); |
1567 | } |
1568 | |
1569 | void generatePatternCharacterFixed(size_t opIndex) |
1570 | { |
1571 | YarrOp& op = m_ops[opIndex]; |
1572 | PatternTerm* term = op.m_term; |
1573 | UChar32 ch = term->patternCharacter; |
1574 | |
1575 | const RegisterID character = regT0; |
1576 | const RegisterID countRegister = regT1; |
1577 | |
1578 | if (m_decodeSurrogatePairs) |
1579 | op.m_jumps.append(jumpIfNoAvailableInput()); |
1580 | |
1581 | move(index, countRegister); |
1582 | Checked<unsigned> scaledMaxCount = term->quantityMaxCount; |
1583 | scaledMaxCount *= U_IS_BMP(ch) ? 1 : 2; |
1584 | sub32(Imm32(scaledMaxCount.unsafeGet()), countRegister); |
1585 | |
1586 | Label loop(this); |
1587 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition - scaledMaxCount, resultReg: character, indexReg: countRegister); |
1588 | // For case-insesitive compares, non-ascii characters that have different |
1589 | // upper & lower case representations are converted to a character class. |
1590 | ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode)); |
1591 | if (m_pattern.ignoreCase() && isASCIIAlpha(c: ch)) { |
1592 | or32(TrustedImm32(0x20), character); |
1593 | ch |= 0x20; |
1594 | } |
1595 | |
1596 | op.m_jumps.append(branch32(NotEqual, character, Imm32(ch))); |
1597 | #ifdef JIT_UNICODE_EXPRESSIONS |
1598 | if (m_decodeSurrogatePairs && !U_IS_BMP(ch)) |
1599 | add32(TrustedImm32(2), countRegister); |
1600 | else |
1601 | #endif |
1602 | add32(TrustedImm32(1), countRegister); |
1603 | branch32(NotEqual, countRegister, index).linkTo(loop, this); |
1604 | } |
1605 | void backtrackPatternCharacterFixed(size_t opIndex) |
1606 | { |
1607 | backtrackTermDefault(opIndex); |
1608 | } |
1609 | |
1610 | void generatePatternCharacterGreedy(size_t opIndex) |
1611 | { |
1612 | YarrOp& op = m_ops[opIndex]; |
1613 | PatternTerm* term = op.m_term; |
1614 | UChar32 ch = term->patternCharacter; |
1615 | |
1616 | const RegisterID character = regT0; |
1617 | const RegisterID countRegister = regT1; |
1618 | |
1619 | move(TrustedImm32(0), countRegister); |
1620 | |
1621 | // Unless have a 16 bit pattern character and an 8 bit string - short circuit |
1622 | if (!((ch > 0xff) && (m_charSize == Char8))) { |
1623 | JumpList failures; |
1624 | Label loop(this); |
1625 | failures.append(atEndOfInput()); |
1626 | failures.append(jumpIfCharNotEquals(ch, negativeCharacterOffset: m_checkedOffset - term->inputPosition, character)); |
1627 | |
1628 | add32(TrustedImm32(1), index); |
1629 | #ifdef JIT_UNICODE_EXPRESSIONS |
1630 | if (m_decodeSurrogatePairs && !U_IS_BMP(ch)) { |
1631 | Jump surrogatePairOk = notAtEndOfInput(); |
1632 | sub32(TrustedImm32(1), index); |
1633 | failures.append(jump()); |
1634 | surrogatePairOk.link(masm: this); |
1635 | add32(TrustedImm32(1), index); |
1636 | } |
1637 | #endif |
1638 | add32(TrustedImm32(1), countRegister); |
1639 | |
1640 | if (term->quantityMaxCount == quantifyInfinite) |
1641 | jump(loop); |
1642 | else |
1643 | branch32(NotEqual, countRegister, Imm32(term->quantityMaxCount.unsafeGet())).linkTo(loop, this); |
1644 | |
1645 | failures.link(masm: this); |
1646 | } |
1647 | op.m_reentry = label(); |
1648 | |
1649 | storeToFrame(countRegister, term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex()); |
1650 | } |
1651 | void backtrackPatternCharacterGreedy(size_t opIndex) |
1652 | { |
1653 | YarrOp& op = m_ops[opIndex]; |
1654 | PatternTerm* term = op.m_term; |
1655 | |
1656 | const RegisterID countRegister = regT1; |
1657 | |
1658 | m_backtrackingState.link(this); |
1659 | |
1660 | loadFromFrame(frameLocation: term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex(), reg: countRegister); |
1661 | m_backtrackingState.append(branchTest32(Zero, countRegister)); |
1662 | sub32(TrustedImm32(1), countRegister); |
1663 | if (!m_decodeSurrogatePairs || U_IS_BMP(term->patternCharacter)) |
1664 | sub32(TrustedImm32(1), index); |
1665 | else |
1666 | sub32(TrustedImm32(2), index); |
1667 | jump(op.m_reentry); |
1668 | } |
1669 | |
1670 | void generatePatternCharacterNonGreedy(size_t opIndex) |
1671 | { |
1672 | YarrOp& op = m_ops[opIndex]; |
1673 | PatternTerm* term = op.m_term; |
1674 | |
1675 | const RegisterID countRegister = regT1; |
1676 | |
1677 | move(TrustedImm32(0), countRegister); |
1678 | op.m_reentry = label(); |
1679 | storeToFrame(countRegister, term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex()); |
1680 | } |
1681 | void backtrackPatternCharacterNonGreedy(size_t opIndex) |
1682 | { |
1683 | YarrOp& op = m_ops[opIndex]; |
1684 | PatternTerm* term = op.m_term; |
1685 | UChar32 ch = term->patternCharacter; |
1686 | |
1687 | const RegisterID character = regT0; |
1688 | const RegisterID countRegister = regT1; |
1689 | |
1690 | m_backtrackingState.link(this); |
1691 | |
1692 | loadFromFrame(frameLocation: term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex(), reg: countRegister); |
1693 | |
1694 | // Unless have a 16 bit pattern character and an 8 bit string - short circuit |
1695 | if (!((ch > 0xff) && (m_charSize == Char8))) { |
1696 | JumpList nonGreedyFailures; |
1697 | nonGreedyFailures.append(atEndOfInput()); |
1698 | if (term->quantityMaxCount != quantifyInfinite) |
1699 | nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityMaxCount.unsafeGet()))); |
1700 | nonGreedyFailures.append(jumpIfCharNotEquals(ch, negativeCharacterOffset: m_checkedOffset - term->inputPosition, character)); |
1701 | |
1702 | add32(TrustedImm32(1), index); |
1703 | #ifdef JIT_UNICODE_EXPRESSIONS |
1704 | if (m_decodeSurrogatePairs && !U_IS_BMP(ch)) { |
1705 | Jump surrogatePairOk = notAtEndOfInput(); |
1706 | sub32(TrustedImm32(1), index); |
1707 | nonGreedyFailures.append(jump()); |
1708 | surrogatePairOk.link(masm: this); |
1709 | add32(TrustedImm32(1), index); |
1710 | } |
1711 | #endif |
1712 | add32(TrustedImm32(1), countRegister); |
1713 | |
1714 | jump(op.m_reentry); |
1715 | nonGreedyFailures.link(masm: this); |
1716 | } |
1717 | |
1718 | if (m_decodeSurrogatePairs && !U_IS_BMP(ch)) { |
1719 | // subtract countRegister*2 for non-BMP characters |
1720 | lshift32(TrustedImm32(1), countRegister); |
1721 | } |
1722 | |
1723 | sub32(countRegister, index); |
1724 | m_backtrackingState.fallthrough(); |
1725 | } |
1726 | |
1727 | void generateCharacterClassOnce(size_t opIndex) |
1728 | { |
1729 | YarrOp& op = m_ops[opIndex]; |
1730 | PatternTerm* term = op.m_term; |
1731 | |
1732 | const RegisterID character = regT0; |
1733 | |
1734 | if (m_decodeSurrogatePairs) { |
1735 | op.m_jumps.append(jumpIfNoAvailableInput()); |
1736 | storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex()); |
1737 | } |
1738 | |
1739 | JumpList matchDest; |
1740 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition, resultReg: character); |
1741 | // If we are matching the "any character" builtin class we only need to read the |
1742 | // character and don't need to match as it will always succeed. |
1743 | if (term->invert() || !term->characterClass->m_anyCharacter) { |
1744 | matchCharacterClass(character, matchDest, charClass: term->characterClass); |
1745 | |
1746 | if (term->invert()) |
1747 | op.m_jumps.append(matchDest); |
1748 | else { |
1749 | op.m_jumps.append(jump()); |
1750 | matchDest.link(masm: this); |
1751 | } |
1752 | } |
1753 | #ifdef JIT_UNICODE_EXPRESSIONS |
1754 | if (m_decodeSurrogatePairs) { |
1755 | Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase); |
1756 | add32(TrustedImm32(1), index); |
1757 | isBMPChar.link(masm: this); |
1758 | } |
1759 | #endif |
1760 | } |
1761 | void backtrackCharacterClassOnce(size_t opIndex) |
1762 | { |
1763 | #ifdef JIT_UNICODE_EXPRESSIONS |
1764 | if (m_decodeSurrogatePairs) { |
1765 | YarrOp& op = m_ops[opIndex]; |
1766 | PatternTerm* term = op.m_term; |
1767 | |
1768 | m_backtrackingState.link(this); |
1769 | loadFromFrame(frameLocation: term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), reg: index); |
1770 | m_backtrackingState.fallthrough(); |
1771 | } |
1772 | #endif |
1773 | backtrackTermDefault(opIndex); |
1774 | } |
1775 | |
1776 | void generateCharacterClassFixed(size_t opIndex) |
1777 | { |
1778 | YarrOp& op = m_ops[opIndex]; |
1779 | PatternTerm* term = op.m_term; |
1780 | |
1781 | const RegisterID character = regT0; |
1782 | const RegisterID countRegister = regT1; |
1783 | |
1784 | if (m_decodeSurrogatePairs) |
1785 | op.m_jumps.append(jumpIfNoAvailableInput()); |
1786 | |
1787 | move(index, countRegister); |
1788 | sub32(Imm32(term->quantityMaxCount.unsafeGet()), countRegister); |
1789 | |
1790 | Label loop(this); |
1791 | JumpList matchDest; |
1792 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition - term->quantityMaxCount, resultReg: character, indexReg: countRegister); |
1793 | // If we are matching the "any character" builtin class we only need to read the |
1794 | // character and don't need to match as it will always succeed. |
1795 | if (term->invert() || !term->characterClass->m_anyCharacter) { |
1796 | matchCharacterClass(character, matchDest, charClass: term->characterClass); |
1797 | |
1798 | if (term->invert()) |
1799 | op.m_jumps.append(matchDest); |
1800 | else { |
1801 | op.m_jumps.append(jump()); |
1802 | matchDest.link(masm: this); |
1803 | } |
1804 | } |
1805 | |
1806 | add32(TrustedImm32(1), countRegister); |
1807 | #ifdef JIT_UNICODE_EXPRESSIONS |
1808 | if (m_decodeSurrogatePairs) { |
1809 | Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase); |
1810 | op.m_jumps.append(atEndOfInput()); |
1811 | add32(TrustedImm32(1), countRegister); |
1812 | add32(TrustedImm32(1), index); |
1813 | isBMPChar.link(masm: this); |
1814 | } |
1815 | #endif |
1816 | branch32(NotEqual, countRegister, index).linkTo(loop, this); |
1817 | } |
1818 | void backtrackCharacterClassFixed(size_t opIndex) |
1819 | { |
1820 | backtrackTermDefault(opIndex); |
1821 | } |
1822 | |
1823 | void generateCharacterClassGreedy(size_t opIndex) |
1824 | { |
1825 | YarrOp& op = m_ops[opIndex]; |
1826 | PatternTerm* term = op.m_term; |
1827 | |
1828 | const RegisterID character = regT0; |
1829 | const RegisterID countRegister = regT1; |
1830 | |
1831 | if (m_decodeSurrogatePairs) |
1832 | storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex()); |
1833 | move(TrustedImm32(0), countRegister); |
1834 | |
1835 | JumpList failures; |
1836 | Label loop(this); |
1837 | failures.append(atEndOfInput()); |
1838 | |
1839 | if (term->invert()) { |
1840 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition, resultReg: character); |
1841 | matchCharacterClass(character, matchDest&: failures, charClass: term->characterClass); |
1842 | } else { |
1843 | JumpList matchDest; |
1844 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition, resultReg: character); |
1845 | // If we are matching the "any character" builtin class we only need to read the |
1846 | // character and don't need to match as it will always succeed. |
1847 | if (!term->characterClass->m_anyCharacter) { |
1848 | matchCharacterClass(character, matchDest, charClass: term->characterClass); |
1849 | failures.append(jump()); |
1850 | } |
1851 | matchDest.link(masm: this); |
1852 | } |
1853 | |
1854 | add32(TrustedImm32(1), index); |
1855 | #ifdef JIT_UNICODE_EXPRESSIONS |
1856 | if (m_decodeSurrogatePairs) { |
1857 | failures.append(atEndOfInput()); |
1858 | Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase); |
1859 | add32(TrustedImm32(1), index); |
1860 | isBMPChar.link(masm: this); |
1861 | } |
1862 | #endif |
1863 | add32(TrustedImm32(1), countRegister); |
1864 | |
1865 | if (term->quantityMaxCount != quantifyInfinite) { |
1866 | branch32(NotEqual, countRegister, Imm32(term->quantityMaxCount.unsafeGet())).linkTo(loop, this); |
1867 | failures.append(jump()); |
1868 | } else |
1869 | jump(loop); |
1870 | |
1871 | failures.link(masm: this); |
1872 | op.m_reentry = label(); |
1873 | |
1874 | storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex()); |
1875 | } |
1876 | void backtrackCharacterClassGreedy(size_t opIndex) |
1877 | { |
1878 | YarrOp& op = m_ops[opIndex]; |
1879 | PatternTerm* term = op.m_term; |
1880 | |
1881 | const RegisterID countRegister = regT1; |
1882 | |
1883 | m_backtrackingState.link(this); |
1884 | |
1885 | loadFromFrame(frameLocation: term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), reg: countRegister); |
1886 | m_backtrackingState.append(branchTest32(Zero, countRegister)); |
1887 | sub32(TrustedImm32(1), countRegister); |
1888 | if (!m_decodeSurrogatePairs) |
1889 | sub32(TrustedImm32(1), index); |
1890 | else { |
1891 | const RegisterID character = regT0; |
1892 | |
1893 | loadFromFrame(frameLocation: term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), reg: index); |
1894 | // Rematch one less |
1895 | storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex()); |
1896 | |
1897 | Label rematchLoop(this); |
1898 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition, resultReg: character); |
1899 | |
1900 | sub32(TrustedImm32(1), countRegister); |
1901 | add32(TrustedImm32(1), index); |
1902 | |
1903 | #ifdef JIT_UNICODE_EXPRESSIONS |
1904 | Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase); |
1905 | add32(TrustedImm32(1), index); |
1906 | isBMPChar.link(masm: this); |
1907 | #endif |
1908 | |
1909 | branchTest32(Zero, countRegister).linkTo(rematchLoop, this); |
1910 | |
1911 | loadFromFrame(frameLocation: term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), reg: countRegister); |
1912 | } |
1913 | jump(op.m_reentry); |
1914 | } |
1915 | |
1916 | void generateCharacterClassNonGreedy(size_t opIndex) |
1917 | { |
1918 | YarrOp& op = m_ops[opIndex]; |
1919 | PatternTerm* term = op.m_term; |
1920 | |
1921 | const RegisterID countRegister = regT1; |
1922 | |
1923 | move(TrustedImm32(0), countRegister); |
1924 | op.m_reentry = label(); |
1925 | if (m_decodeSurrogatePairs) |
1926 | storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex()); |
1927 | storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex()); |
1928 | } |
1929 | |
1930 | void backtrackCharacterClassNonGreedy(size_t opIndex) |
1931 | { |
1932 | YarrOp& op = m_ops[opIndex]; |
1933 | PatternTerm* term = op.m_term; |
1934 | |
1935 | const RegisterID character = regT0; |
1936 | const RegisterID countRegister = regT1; |
1937 | |
1938 | JumpList nonGreedyFailures; |
1939 | |
1940 | m_backtrackingState.link(this); |
1941 | |
1942 | if (m_decodeSurrogatePairs) |
1943 | loadFromFrame(frameLocation: term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), reg: index); |
1944 | loadFromFrame(frameLocation: term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), reg: countRegister); |
1945 | |
1946 | nonGreedyFailures.append(atEndOfInput()); |
1947 | nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityMaxCount.unsafeGet()))); |
1948 | |
1949 | JumpList matchDest; |
1950 | readCharacter(negativeCharacterOffset: m_checkedOffset - term->inputPosition, resultReg: character); |
1951 | // If we are matching the "any character" builtin class we only need to read the |
1952 | // character and don't need to match as it will always succeed. |
1953 | if (term->invert() || !term->characterClass->m_anyCharacter) { |
1954 | matchCharacterClass(character, matchDest, charClass: term->characterClass); |
1955 | |
1956 | if (term->invert()) |
1957 | nonGreedyFailures.append(other: matchDest); |
1958 | else { |
1959 | nonGreedyFailures.append(jump()); |
1960 | matchDest.link(masm: this); |
1961 | } |
1962 | } |
1963 | |
1964 | add32(TrustedImm32(1), index); |
1965 | #ifdef JIT_UNICODE_EXPRESSIONS |
1966 | if (m_decodeSurrogatePairs) { |
1967 | nonGreedyFailures.append(atEndOfInput()); |
1968 | Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase); |
1969 | add32(TrustedImm32(1), index); |
1970 | isBMPChar.link(masm: this); |
1971 | } |
1972 | #endif |
1973 | add32(TrustedImm32(1), countRegister); |
1974 | |
1975 | jump(op.m_reentry); |
1976 | |
1977 | nonGreedyFailures.link(masm: this); |
1978 | sub32(countRegister, index); |
1979 | m_backtrackingState.fallthrough(); |
1980 | } |
1981 | |
1982 | void generateDotStarEnclosure(size_t opIndex) |
1983 | { |
1984 | YarrOp& op = m_ops[opIndex]; |
1985 | PatternTerm* term = op.m_term; |
1986 | |
1987 | const RegisterID character = regT0; |
1988 | const RegisterID matchPos = regT1; |
1989 | #ifndef HAVE_INITIAL_START_REG |
1990 | const RegisterID initialStart = character; |
1991 | #endif |
1992 | |
1993 | JumpList foundBeginningNewLine; |
1994 | JumpList saveStartIndex; |
1995 | JumpList foundEndingNewLine; |
1996 | |
1997 | if (m_pattern.dotAll()) { |
1998 | move(TrustedImm32(0), matchPos); |
1999 | setMatchStart(matchPos); |
2000 | move(length, index); |
2001 | return; |
2002 | } |
2003 | |
2004 | ASSERT(!m_pattern.m_body->m_hasFixedSize); |
2005 | getMatchStart(reg: matchPos); |
2006 | |
2007 | #ifndef HAVE_INITIAL_START_REG |
2008 | loadFromFrame(m_pattern.m_initialStartValueFrameLocation, initialStart); |
2009 | #endif |
2010 | saveStartIndex.append(branch32(BelowOrEqual, matchPos, initialStart)); |
2011 | Label findBOLLoop(this); |
2012 | sub32(TrustedImm32(1), matchPos); |
2013 | if (m_charSize == Char8) |
2014 | load8(BaseIndex(input, matchPos, TimesOne, 0), character); |
2015 | else |
2016 | load16(BaseIndex(input, matchPos, TimesTwo, 0), character); |
2017 | matchCharacterClass(character, matchDest&: foundBeginningNewLine, charClass: m_pattern.newlineCharacterClass()); |
2018 | |
2019 | #ifndef HAVE_INITIAL_START_REG |
2020 | loadFromFrame(m_pattern.m_initialStartValueFrameLocation, initialStart); |
2021 | #endif |
2022 | branch32(Above, matchPos, initialStart).linkTo(findBOLLoop, this); |
2023 | saveStartIndex.append(jump()); |
2024 | |
2025 | foundBeginningNewLine.link(masm: this); |
2026 | add32(TrustedImm32(1), matchPos); // Advance past newline |
2027 | saveStartIndex.link(masm: this); |
2028 | |
2029 | if (!m_pattern.multiline() && term->anchors.bolAnchor) |
2030 | op.m_jumps.append(branchTest32(NonZero, matchPos)); |
2031 | |
2032 | ASSERT(!m_pattern.m_body->m_hasFixedSize); |
2033 | setMatchStart(matchPos); |
2034 | |
2035 | move(index, matchPos); |
2036 | |
2037 | Label findEOLLoop(this); |
2038 | foundEndingNewLine.append(branch32(Equal, matchPos, length)); |
2039 | if (m_charSize == Char8) |
2040 | load8(BaseIndex(input, matchPos, TimesOne, 0), character); |
2041 | else |
2042 | load16(BaseIndex(input, matchPos, TimesTwo, 0), character); |
2043 | matchCharacterClass(character, matchDest&: foundEndingNewLine, charClass: m_pattern.newlineCharacterClass()); |
2044 | add32(TrustedImm32(1), matchPos); |
2045 | jump(findEOLLoop); |
2046 | |
2047 | foundEndingNewLine.link(masm: this); |
2048 | |
2049 | if (!m_pattern.multiline() && term->anchors.eolAnchor) |
2050 | op.m_jumps.append(branch32(NotEqual, matchPos, length)); |
2051 | |
2052 | move(matchPos, index); |
2053 | } |
2054 | |
2055 | void backtrackDotStarEnclosure(size_t opIndex) |
2056 | { |
2057 | backtrackTermDefault(opIndex); |
2058 | } |
2059 | |
2060 | // Code generation/backtracking for simple terms |
2061 | // (pattern characters, character classes, and assertions). |
2062 | // These methods farm out work to the set of functions above. |
2063 | void generateTerm(size_t opIndex) |
2064 | { |
2065 | YarrOp& op = m_ops[opIndex]; |
2066 | PatternTerm* term = op.m_term; |
2067 | |
2068 | switch (term->type) { |
2069 | case PatternTerm::TypePatternCharacter: |
2070 | switch (term->quantityType) { |
2071 | case QuantifierFixedCount: |
2072 | if (term->quantityMaxCount == 1) |
2073 | generatePatternCharacterOnce(opIndex); |
2074 | else |
2075 | generatePatternCharacterFixed(opIndex); |
2076 | break; |
2077 | case QuantifierGreedy: |
2078 | generatePatternCharacterGreedy(opIndex); |
2079 | break; |
2080 | case QuantifierNonGreedy: |
2081 | generatePatternCharacterNonGreedy(opIndex); |
2082 | break; |
2083 | } |
2084 | break; |
2085 | |
2086 | case PatternTerm::TypeCharacterClass: |
2087 | switch (term->quantityType) { |
2088 | case QuantifierFixedCount: |
2089 | if (term->quantityMaxCount == 1) |
2090 | generateCharacterClassOnce(opIndex); |
2091 | else |
2092 | generateCharacterClassFixed(opIndex); |
2093 | break; |
2094 | case QuantifierGreedy: |
2095 | generateCharacterClassGreedy(opIndex); |
2096 | break; |
2097 | case QuantifierNonGreedy: |
2098 | generateCharacterClassNonGreedy(opIndex); |
2099 | break; |
2100 | } |
2101 | break; |
2102 | |
2103 | case PatternTerm::TypeAssertionBOL: |
2104 | generateAssertionBOL(opIndex); |
2105 | break; |
2106 | |
2107 | case PatternTerm::TypeAssertionEOL: |
2108 | generateAssertionEOL(opIndex); |
2109 | break; |
2110 | |
2111 | case PatternTerm::TypeAssertionWordBoundary: |
2112 | generateAssertionWordBoundary(opIndex); |
2113 | break; |
2114 | |
2115 | case PatternTerm::TypeForwardReference: |
2116 | m_failureReason = JITFailureReason::ForwardReference; |
2117 | break; |
2118 | |
2119 | case PatternTerm::TypeParenthesesSubpattern: |
2120 | case PatternTerm::TypeParentheticalAssertion: |
2121 | RELEASE_ASSERT_NOT_REACHED(); |
2122 | |
2123 | case PatternTerm::TypeBackReference: |
2124 | #if ENABLE(YARR_JIT_BACKREFERENCES) |
2125 | generateBackReference(opIndex); |
2126 | #else |
2127 | m_failureReason = JITFailureReason::BackReference; |
2128 | #endif |
2129 | break; |
2130 | case PatternTerm::TypeDotStarEnclosure: |
2131 | generateDotStarEnclosure(opIndex); |
2132 | break; |
2133 | } |
2134 | } |
2135 | void backtrackTerm(size_t opIndex) |
2136 | { |
2137 | YarrOp& op = m_ops[opIndex]; |
2138 | PatternTerm* term = op.m_term; |
2139 | |
2140 | switch (term->type) { |
2141 | case PatternTerm::TypePatternCharacter: |
2142 | switch (term->quantityType) { |
2143 | case QuantifierFixedCount: |
2144 | if (term->quantityMaxCount == 1) |
2145 | backtrackPatternCharacterOnce(opIndex); |
2146 | else |
2147 | backtrackPatternCharacterFixed(opIndex); |
2148 | break; |
2149 | case QuantifierGreedy: |
2150 | backtrackPatternCharacterGreedy(opIndex); |
2151 | break; |
2152 | case QuantifierNonGreedy: |
2153 | backtrackPatternCharacterNonGreedy(opIndex); |
2154 | break; |
2155 | } |
2156 | break; |
2157 | |
2158 | case PatternTerm::TypeCharacterClass: |
2159 | switch (term->quantityType) { |
2160 | case QuantifierFixedCount: |
2161 | if (term->quantityMaxCount == 1) |
2162 | backtrackCharacterClassOnce(opIndex); |
2163 | else |
2164 | backtrackCharacterClassFixed(opIndex); |
2165 | break; |
2166 | case QuantifierGreedy: |
2167 | backtrackCharacterClassGreedy(opIndex); |
2168 | break; |
2169 | case QuantifierNonGreedy: |
2170 | backtrackCharacterClassNonGreedy(opIndex); |
2171 | break; |
2172 | } |
2173 | break; |
2174 | |
2175 | case PatternTerm::TypeAssertionBOL: |
2176 | backtrackAssertionBOL(opIndex); |
2177 | break; |
2178 | |
2179 | case PatternTerm::TypeAssertionEOL: |
2180 | backtrackAssertionEOL(opIndex); |
2181 | break; |
2182 | |
2183 | case PatternTerm::TypeAssertionWordBoundary: |
2184 | backtrackAssertionWordBoundary(opIndex); |
2185 | break; |
2186 | |
2187 | case PatternTerm::TypeForwardReference: |
2188 | m_failureReason = JITFailureReason::ForwardReference; |
2189 | break; |
2190 | |
2191 | case PatternTerm::TypeParenthesesSubpattern: |
2192 | case PatternTerm::TypeParentheticalAssertion: |
2193 | RELEASE_ASSERT_NOT_REACHED(); |
2194 | |
2195 | case PatternTerm::TypeBackReference: |
2196 | #if ENABLE(YARR_JIT_BACKREFERENCES) |
2197 | backtrackBackReference(opIndex); |
2198 | #else |
2199 | m_failureReason = JITFailureReason::BackReference; |
2200 | #endif |
2201 | break; |
2202 | |
2203 | case PatternTerm::TypeDotStarEnclosure: |
2204 | backtrackDotStarEnclosure(opIndex); |
2205 | break; |
2206 | } |
2207 | } |
2208 | |
2209 | void generate() |
2210 | { |
2211 | // Forwards generate the matching code. |
2212 | ASSERT(m_ops.size()); |
2213 | size_t opIndex = 0; |
2214 | |
2215 | do { |
2216 | YarrOp& op = m_ops[opIndex]; |
2217 | switch (op.m_op) { |
2218 | |
2219 | case OpTerm: |
2220 | generateTerm(opIndex); |
2221 | break; |
2222 | |
2223 | // OpBodyAlternativeBegin/Next/End |
2224 | // |
2225 | // These nodes wrap the set of alternatives in the body of the regular expression. |
2226 | // There may be either one or two chains of OpBodyAlternative nodes, one representing |
2227 | // the 'once through' sequence of alternatives (if any exist), and one representing |
2228 | // the repeating alternatives (again, if any exist). |
2229 | // |
2230 | // Upon normal entry to the Begin alternative, we will check that input is available. |
2231 | // Reentry to the Begin alternative will take place after the check has taken place, |
2232 | // and will assume that the input position has already been progressed as appropriate. |
2233 | // |
2234 | // Entry to subsequent Next/End alternatives occurs when the prior alternative has |
2235 | // successfully completed a match - return a success state from JIT code. |
2236 | // |
2237 | // Next alternatives allow for reentry optimized to suit backtracking from its |
2238 | // preceding alternative. It expects the input position to still be set to a position |
2239 | // appropriate to its predecessor, and it will only perform an input check if the |
2240 | // predecessor had a minimum size less than its own. |
2241 | // |
2242 | // In the case 'once through' expressions, the End node will also have a reentry |
2243 | // point to jump to when the last alternative fails. Again, this expects the input |
2244 | // position to still reflect that expected by the prior alternative. |
2245 | case OpBodyAlternativeBegin: { |
2246 | PatternAlternative* alternative = op.m_alternative; |
2247 | |
2248 | // Upon entry at the head of the set of alternatives, check if input is available |
2249 | // to run the first alternative. (This progresses the input position). |
2250 | op.m_jumps.append(jumpIfNoAvailableInput(countToCheck: alternative->m_minimumSize)); |
2251 | // We will reenter after the check, and assume the input position to have been |
2252 | // set as appropriate to this alternative. |
2253 | op.m_reentry = label(); |
2254 | |
2255 | m_checkedOffset += alternative->m_minimumSize; |
2256 | break; |
2257 | } |
2258 | case OpBodyAlternativeNext: |
2259 | case OpBodyAlternativeEnd: { |
2260 | PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative; |
2261 | PatternAlternative* alternative = op.m_alternative; |
2262 | |
2263 | // If we get here, the prior alternative matched - return success. |
2264 | |
2265 | // Adjust the stack pointer to remove the pattern's frame. |
2266 | removeCallFrame(); |
2267 | |
2268 | // Load appropriate values into the return register and the first output |
2269 | // slot, and return. In the case of pattern with a fixed size, we will |
2270 | // not have yet set the value in the first |
2271 | ASSERT(index != returnRegister); |
2272 | if (m_pattern.m_body->m_hasFixedSize) { |
2273 | move(index, returnRegister); |
2274 | if (priorAlternative->m_minimumSize) |
2275 | sub32(Imm32(priorAlternative->m_minimumSize), returnRegister); |
2276 | if (compileMode == IncludeSubpatterns) |
2277 | store32(returnRegister, output); |
2278 | } else |
2279 | getMatchStart(reg: returnRegister); |
2280 | if (compileMode == IncludeSubpatterns) |
2281 | store32(index, Address(output, 4)); |
2282 | move(index, returnRegister2); |
2283 | |
2284 | generateReturn(); |
2285 | |
2286 | // This is the divide between the tail of the prior alternative, above, and |
2287 | // the head of the subsequent alternative, below. |
2288 | |
2289 | if (op.m_op == OpBodyAlternativeNext) { |
2290 | // This is the reentry point for the Next alternative. We expect any code |
2291 | // that jumps here to do so with the input position matching that of the |
2292 | // PRIOR alteranative, and we will only check input availability if we |
2293 | // need to progress it forwards. |
2294 | op.m_reentry = label(); |
2295 | if (alternative->m_minimumSize > priorAlternative->m_minimumSize) { |
2296 | add32(Imm32(alternative->m_minimumSize - priorAlternative->m_minimumSize), index); |
2297 | op.m_jumps.append(jumpIfNoAvailableInput()); |
2298 | } else if (priorAlternative->m_minimumSize > alternative->m_minimumSize) |
2299 | sub32(Imm32(priorAlternative->m_minimumSize - alternative->m_minimumSize), index); |
2300 | } else if (op.m_nextOp == notFound) { |
2301 | // This is the reentry point for the End of 'once through' alternatives, |
2302 | // jumped to when the last alternative fails to match. |
2303 | op.m_reentry = label(); |
2304 | sub32(Imm32(priorAlternative->m_minimumSize), index); |
2305 | } |
2306 | |
2307 | if (op.m_op == OpBodyAlternativeNext) |
2308 | m_checkedOffset += alternative->m_minimumSize; |
2309 | m_checkedOffset -= priorAlternative->m_minimumSize; |
2310 | break; |
2311 | } |
2312 | |
2313 | // OpSimpleNestedAlternativeBegin/Next/End |
2314 | // OpNestedAlternativeBegin/Next/End |
2315 | // |
2316 | // These nodes are used to handle sets of alternatives that are nested within |
2317 | // subpatterns and parenthetical assertions. The 'simple' forms are used where |
2318 | // we do not need to be able to backtrack back into any alternative other than |
2319 | // the last, the normal forms allow backtracking into any alternative. |
2320 | // |
2321 | // Each Begin/Next node is responsible for planting an input check to ensure |
2322 | // sufficient input is available on entry. Next nodes additionally need to |
2323 | // jump to the end - Next nodes use the End node's m_jumps list to hold this |
2324 | // set of jumps. |
2325 | // |
2326 | // In the non-simple forms, successful alternative matches must store a |
2327 | // 'return address' using a DataLabelPtr, used to store the address to jump |
2328 | // to when backtracking, to get to the code for the appropriate alternative. |
2329 | case OpSimpleNestedAlternativeBegin: |
2330 | case OpNestedAlternativeBegin: { |
2331 | PatternTerm* term = op.m_term; |
2332 | PatternAlternative* alternative = op.m_alternative; |
2333 | PatternDisjunction* disjunction = term->parentheses.disjunction; |
2334 | |
2335 | // Calculate how much input we need to check for, and if non-zero check. |
2336 | op.m_checkAdjust = Checked<unsigned>(alternative->m_minimumSize); |
2337 | if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion)) |
2338 | op.m_checkAdjust -= disjunction->m_minimumSize; |
2339 | if (op.m_checkAdjust) |
2340 | op.m_jumps.append(jumpIfNoAvailableInput(countToCheck: op.m_checkAdjust.unsafeGet())); |
2341 | |
2342 | m_checkedOffset += op.m_checkAdjust; |
2343 | break; |
2344 | } |
2345 | case OpSimpleNestedAlternativeNext: |
2346 | case OpNestedAlternativeNext: { |
2347 | PatternTerm* term = op.m_term; |
2348 | PatternAlternative* alternative = op.m_alternative; |
2349 | PatternDisjunction* disjunction = term->parentheses.disjunction; |
2350 | |
2351 | // In the non-simple case, store a 'return address' so we can backtrack correctly. |
2352 | if (op.m_op == OpNestedAlternativeNext) { |
2353 | unsigned parenthesesFrameLocation = term->frameLocation; |
2354 | op.m_returnAddress = storeToFrameWithPatch(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::returnAddressIndex()); |
2355 | } |
2356 | |
2357 | if (term->quantityType != QuantifierFixedCount && !m_ops[op.m_previousOp].m_alternative->m_minimumSize) { |
2358 | // If the previous alternative matched without consuming characters then |
2359 | // backtrack to try to match while consumming some input. |
2360 | op.m_zeroLengthMatch = branch32(Equal, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*))); |
2361 | } |
2362 | |
2363 | // If we reach here then the last alternative has matched - jump to the |
2364 | // End node, to skip over any further alternatives. |
2365 | // |
2366 | // FIXME: this is logically O(N^2) (though N can be expected to be very |
2367 | // small). We could avoid this either by adding an extra jump to the JIT |
2368 | // data structures, or by making backtracking code that jumps to Next |
2369 | // alternatives are responsible for checking that input is available (if |
2370 | // we didn't need to plant the input checks, then m_jumps would be free). |
2371 | YarrOp* endOp = &m_ops[op.m_nextOp]; |
2372 | while (endOp->m_nextOp != notFound) { |
2373 | ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext); |
2374 | endOp = &m_ops[endOp->m_nextOp]; |
2375 | } |
2376 | ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd); |
2377 | endOp->m_jumps.append(jump()); |
2378 | |
2379 | // This is the entry point for the next alternative. |
2380 | op.m_reentry = label(); |
2381 | |
2382 | // Calculate how much input we need to check for, and if non-zero check. |
2383 | op.m_checkAdjust = alternative->m_minimumSize; |
2384 | if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion)) |
2385 | op.m_checkAdjust -= disjunction->m_minimumSize; |
2386 | if (op.m_checkAdjust) |
2387 | op.m_jumps.append(jumpIfNoAvailableInput(countToCheck: op.m_checkAdjust.unsafeGet())); |
2388 | |
2389 | YarrOp& lastOp = m_ops[op.m_previousOp]; |
2390 | m_checkedOffset -= lastOp.m_checkAdjust; |
2391 | m_checkedOffset += op.m_checkAdjust; |
2392 | break; |
2393 | } |
2394 | case OpSimpleNestedAlternativeEnd: |
2395 | case OpNestedAlternativeEnd: { |
2396 | PatternTerm* term = op.m_term; |
2397 | |
2398 | // In the non-simple case, store a 'return address' so we can backtrack correctly. |
2399 | if (op.m_op == OpNestedAlternativeEnd) { |
2400 | unsigned parenthesesFrameLocation = term->frameLocation; |
2401 | op.m_returnAddress = storeToFrameWithPatch(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::returnAddressIndex()); |
2402 | } |
2403 | |
2404 | if (term->quantityType != QuantifierFixedCount && !m_ops[op.m_previousOp].m_alternative->m_minimumSize) { |
2405 | // If the previous alternative matched without consuming characters then |
2406 | // backtrack to try to match while consumming some input. |
2407 | op.m_zeroLengthMatch = branch32(Equal, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*))); |
2408 | } |
2409 | |
2410 | // If this set of alternatives contains more than one alternative, |
2411 | // then the Next nodes will have planted jumps to the End, and added |
2412 | // them to this node's m_jumps list. |
2413 | op.m_jumps.link(this); |
2414 | op.m_jumps.clear(); |
2415 | |
2416 | YarrOp& lastOp = m_ops[op.m_previousOp]; |
2417 | m_checkedOffset -= lastOp.m_checkAdjust; |
2418 | break; |
2419 | } |
2420 | |
2421 | // OpParenthesesSubpatternOnceBegin/End |
2422 | // |
2423 | // These nodes support (optionally) capturing subpatterns, that have a |
2424 | // quantity count of 1 (this covers fixed once, and ?/?? quantifiers). |
2425 | case OpParenthesesSubpatternOnceBegin: { |
2426 | PatternTerm* term = op.m_term; |
2427 | unsigned parenthesesFrameLocation = term->frameLocation; |
2428 | const RegisterID indexTemporary = regT0; |
2429 | ASSERT(term->quantityMaxCount == 1); |
2430 | |
2431 | // Upon entry to a Greedy quantified set of parenthese store the index. |
2432 | // We'll use this for two purposes: |
2433 | // - To indicate which iteration we are on of mathing the remainder of |
2434 | // the expression after the parentheses - the first, including the |
2435 | // match within the parentheses, or the second having skipped over them. |
2436 | // - To check for empty matches, which must be rejected. |
2437 | // |
2438 | // At the head of a NonGreedy set of parentheses we'll immediately set the |
2439 | // value on the stack to -1 (indicating a match skipping the subpattern), |
2440 | // and plant a jump to the end. We'll also plant a label to backtrack to |
2441 | // to reenter the subpattern later, with a store to set up index on the |
2442 | // second iteration. |
2443 | // |
2444 | // FIXME: for capturing parens, could use the index in the capture array? |
2445 | if (term->quantityType == QuantifierGreedy) |
2446 | storeToFrame(index, parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex()); |
2447 | else if (term->quantityType == QuantifierNonGreedy) { |
2448 | storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex()); |
2449 | op.m_jumps.append(jump()); |
2450 | op.m_reentry = label(); |
2451 | storeToFrame(index, parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex()); |
2452 | } |
2453 | |
2454 | // If the parenthese are capturing, store the starting index value to the |
2455 | // captures array, offsetting as necessary. |
2456 | // |
2457 | // FIXME: could avoid offsetting this value in JIT code, apply |
2458 | // offsets only afterwards, at the point the results array is |
2459 | // being accessed. |
2460 | if (term->capture() && compileMode == IncludeSubpatterns) { |
2461 | unsigned inputOffset = (m_checkedOffset - term->inputPosition).unsafeGet(); |
2462 | if (term->quantityType == QuantifierFixedCount) |
2463 | inputOffset += term->parentheses.disjunction->m_minimumSize; |
2464 | if (inputOffset) { |
2465 | move(index, indexTemporary); |
2466 | sub32(Imm32(inputOffset), indexTemporary); |
2467 | setSubpatternStart(reg: indexTemporary, subpattern: term->parentheses.subpatternId); |
2468 | } else |
2469 | setSubpatternStart(reg: index, subpattern: term->parentheses.subpatternId); |
2470 | } |
2471 | break; |
2472 | } |
2473 | case OpParenthesesSubpatternOnceEnd: { |
2474 | PatternTerm* term = op.m_term; |
2475 | const RegisterID indexTemporary = regT0; |
2476 | ASSERT(term->quantityMaxCount == 1); |
2477 | |
2478 | // Runtime ASSERT to make sure that the nested alternative handled the |
2479 | // "no input consumed" check. |
2480 | if (!ASSERT_DISABLED && term->quantityType != QuantifierFixedCount && !term->parentheses.disjunction->m_minimumSize) { |
2481 | Jump pastBreakpoint; |
2482 | pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*))); |
2483 | // ### abortWithReason(YARRNoInputConsumed); |
2484 | pastBreakpoint.link(masm: this); |
2485 | } |
2486 | |
2487 | // If the parenthese are capturing, store the ending index value to the |
2488 | // captures array, offsetting as necessary. |
2489 | // |
2490 | // FIXME: could avoid offsetting this value in JIT code, apply |
2491 | // offsets only afterwards, at the point the results array is |
2492 | // being accessed. |
2493 | if (term->capture() && compileMode == IncludeSubpatterns) { |
2494 | unsigned inputOffset = (m_checkedOffset - term->inputPosition).unsafeGet(); |
2495 | if (inputOffset) { |
2496 | move(index, indexTemporary); |
2497 | sub32(Imm32(inputOffset), indexTemporary); |
2498 | setSubpatternEnd(reg: indexTemporary, subpattern: term->parentheses.subpatternId); |
2499 | } else |
2500 | setSubpatternEnd(reg: index, subpattern: term->parentheses.subpatternId); |
2501 | } |
2502 | |
2503 | // If the parentheses are quantified Greedy then add a label to jump back |
2504 | // to if we get a failed match from after the parentheses. For NonGreedy |
2505 | // parentheses, link the jump from before the subpattern to here. |
2506 | if (term->quantityType == QuantifierGreedy) |
2507 | op.m_reentry = label(); |
2508 | else if (term->quantityType == QuantifierNonGreedy) { |
2509 | YarrOp& beginOp = m_ops[op.m_previousOp]; |
2510 | beginOp.m_jumps.link(this); |
2511 | } |
2512 | break; |
2513 | } |
2514 | |
2515 | // OpParenthesesSubpatternTerminalBegin/End |
2516 | case OpParenthesesSubpatternTerminalBegin: { |
2517 | PatternTerm* term = op.m_term; |
2518 | ASSERT(term->quantityType == QuantifierGreedy); |
2519 | ASSERT(term->quantityMaxCount == quantifyInfinite); |
2520 | ASSERT(!term->capture()); |
2521 | |
2522 | // Upon entry set a label to loop back to. |
2523 | op.m_reentry = label(); |
2524 | |
2525 | // Store the start index of the current match; we need to reject zero |
2526 | // length matches. |
2527 | storeToFrame(index, term->frameLocation + BackTrackInfoParenthesesTerminal::beginIndex()); |
2528 | break; |
2529 | } |
2530 | case OpParenthesesSubpatternTerminalEnd: { |
2531 | YarrOp& beginOp = m_ops[op.m_previousOp]; |
2532 | if (!ASSERT_DISABLED) { |
2533 | PatternTerm* term = op.m_term; |
2534 | |
2535 | // Runtime ASSERT to make sure that the nested alternative handled the |
2536 | // "no input consumed" check. |
2537 | Jump pastBreakpoint; |
2538 | pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*))); |
2539 | // ### abortWithReason(YARRNoInputConsumed); |
2540 | pastBreakpoint.link(masm: this); |
2541 | } |
2542 | |
2543 | // We know that the match is non-zero, we can accept it and |
2544 | // loop back up to the head of the subpattern. |
2545 | jump(beginOp.m_reentry); |
2546 | |
2547 | // This is the entry point to jump to when we stop matching - we will |
2548 | // do so once the subpattern cannot match any more. |
2549 | op.m_reentry = label(); |
2550 | break; |
2551 | } |
2552 | |
2553 | // OpParenthesesSubpatternBegin/End |
2554 | // |
2555 | // These nodes support generic subpatterns. |
2556 | case OpParenthesesSubpatternBegin: { |
2557 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
2558 | PatternTerm* term = op.m_term; |
2559 | unsigned parenthesesFrameLocation = term->frameLocation; |
2560 | |
2561 | // Upon entry to a Greedy quantified set of parenthese store the index. |
2562 | // We'll use this for two purposes: |
2563 | // - To indicate which iteration we are on of mathing the remainder of |
2564 | // the expression after the parentheses - the first, including the |
2565 | // match within the parentheses, or the second having skipped over them. |
2566 | // - To check for empty matches, which must be rejected. |
2567 | // |
2568 | // At the head of a NonGreedy set of parentheses we'll immediately set 'begin' |
2569 | // in the backtrack info to -1 (indicating a match skipping the subpattern), |
2570 | // and plant a jump to the end. We'll also plant a label to backtrack to |
2571 | // to reenter the subpattern later, with a store to set 'begin' to current index |
2572 | // on the second iteration. |
2573 | // |
2574 | // FIXME: for capturing parens, could use the index in the capture array? |
2575 | if (term->quantityType == QuantifierGreedy || term->quantityType == QuantifierNonGreedy) { |
2576 | storeToFrame(TrustedImm32(0), parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex()); |
2577 | storeToFrame(TrustedImmPtr(nullptr), parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex()); |
2578 | |
2579 | if (term->quantityType == QuantifierNonGreedy) { |
2580 | storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex()); |
2581 | op.m_jumps.append(jump()); |
2582 | } |
2583 | |
2584 | op.m_reentry = label(); |
2585 | RegisterID currParenContextReg = regT0; |
2586 | RegisterID newParenContextReg = regT1; |
2587 | |
2588 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex(), reg: currParenContextReg); |
2589 | allocateParenContext(result: newParenContextReg); |
2590 | storePtr(currParenContextReg, newParenContextReg); |
2591 | storeToFrame(newParenContextReg, parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex()); |
2592 | saveParenContext(parenContextReg: newParenContextReg, tempReg: regT2, firstSubpattern: term->parentheses.subpatternId, lastSubpattern: term->parentheses.lastSubpatternId, subpatternBaseFrameLocation: parenthesesFrameLocation); |
2593 | storeToFrame(index, parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex()); |
2594 | } |
2595 | |
2596 | // If the parenthese are capturing, store the starting index value to the |
2597 | // captures array, offsetting as necessary. |
2598 | // |
2599 | // FIXME: could avoid offsetting this value in JIT code, apply |
2600 | // offsets only afterwards, at the point the results array is |
2601 | // being accessed. |
2602 | if (term->capture() && compileMode == IncludeSubpatterns) { |
2603 | const RegisterID indexTemporary = regT0; |
2604 | unsigned inputOffset = (m_checkedOffset - term->inputPosition).unsafeGet(); |
2605 | if (term->quantityType == QuantifierFixedCount) |
2606 | inputOffset += term->parentheses.disjunction->m_minimumSize; |
2607 | if (inputOffset) { |
2608 | move(index, indexTemporary); |
2609 | sub32(Imm32(inputOffset), indexTemporary); |
2610 | setSubpatternStart(reg: indexTemporary, subpattern: term->parentheses.subpatternId); |
2611 | } else |
2612 | setSubpatternStart(reg: index, subpattern: term->parentheses.subpatternId); |
2613 | } |
2614 | #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS |
2615 | RELEASE_ASSERT_NOT_REACHED(); |
2616 | #endif |
2617 | break; |
2618 | } |
2619 | case OpParenthesesSubpatternEnd: { |
2620 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
2621 | PatternTerm* term = op.m_term; |
2622 | unsigned parenthesesFrameLocation = term->frameLocation; |
2623 | |
2624 | // Runtime ASSERT to make sure that the nested alternative handled the |
2625 | // "no input consumed" check. |
2626 | if (!ASSERT_DISABLED && term->quantityType != QuantifierFixedCount && !term->parentheses.disjunction->m_minimumSize) { |
2627 | Jump pastBreakpoint; |
2628 | pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, parenthesesFrameLocation * sizeof(void*))); |
2629 | // ### abortWithReason(YARRNoInputConsumed); |
2630 | pastBreakpoint.link(masm: this); |
2631 | } |
2632 | |
2633 | const RegisterID countTemporary = regT1; |
2634 | |
2635 | YarrOp& beginOp = m_ops[op.m_previousOp]; |
2636 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), reg: countTemporary); |
2637 | add32(TrustedImm32(1), countTemporary); |
2638 | storeToFrame(countTemporary, parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex()); |
2639 | |
2640 | // If the parenthese are capturing, store the ending index value to the |
2641 | // captures array, offsetting as necessary. |
2642 | // |
2643 | // FIXME: could avoid offsetting this value in JIT code, apply |
2644 | // offsets only afterwards, at the point the results array is |
2645 | // being accessed. |
2646 | if (term->capture() && compileMode == IncludeSubpatterns) { |
2647 | const RegisterID indexTemporary = regT0; |
2648 | |
2649 | unsigned inputOffset = (m_checkedOffset - term->inputPosition).unsafeGet(); |
2650 | if (inputOffset) { |
2651 | move(index, indexTemporary); |
2652 | sub32(Imm32(inputOffset), indexTemporary); |
2653 | setSubpatternEnd(reg: indexTemporary, subpattern: term->parentheses.subpatternId); |
2654 | } else |
2655 | setSubpatternEnd(reg: index, subpattern: term->parentheses.subpatternId); |
2656 | } |
2657 | |
2658 | // If the parentheses are quantified Greedy then add a label to jump back |
2659 | // to if we get a failed match from after the parentheses. For NonGreedy |
2660 | // parentheses, link the jump from before the subpattern to here. |
2661 | if (term->quantityType == QuantifierGreedy) { |
2662 | if (term->quantityMaxCount != quantifyInfinite) |
2663 | branch32(Below, countTemporary, Imm32(term->quantityMaxCount.unsafeGet())).linkTo(beginOp.m_reentry, this); |
2664 | else |
2665 | jump(beginOp.m_reentry); |
2666 | |
2667 | op.m_reentry = label(); |
2668 | } else if (term->quantityType == QuantifierNonGreedy) { |
2669 | YarrOp& beginOp = m_ops[op.m_previousOp]; |
2670 | beginOp.m_jumps.link(this); |
2671 | op.m_reentry = label(); |
2672 | } |
2673 | #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS |
2674 | RELEASE_ASSERT_NOT_REACHED(); |
2675 | #endif |
2676 | break; |
2677 | } |
2678 | |
2679 | // OpParentheticalAssertionBegin/End |
2680 | case OpParentheticalAssertionBegin: { |
2681 | PatternTerm* term = op.m_term; |
2682 | |
2683 | // Store the current index - assertions should not update index, so |
2684 | // we will need to restore it upon a successful match. |
2685 | unsigned parenthesesFrameLocation = term->frameLocation; |
2686 | storeToFrame(index, parenthesesFrameLocation + BackTrackInfoParentheticalAssertion::beginIndex()); |
2687 | |
2688 | // Check |
2689 | op.m_checkAdjust = m_checkedOffset - term->inputPosition; |
2690 | if (op.m_checkAdjust) |
2691 | sub32(Imm32(op.m_checkAdjust.unsafeGet()), index); |
2692 | |
2693 | m_checkedOffset -= op.m_checkAdjust; |
2694 | break; |
2695 | } |
2696 | case OpParentheticalAssertionEnd: { |
2697 | PatternTerm* term = op.m_term; |
2698 | |
2699 | // Restore the input index value. |
2700 | unsigned parenthesesFrameLocation = term->frameLocation; |
2701 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheticalAssertion::beginIndex(), reg: index); |
2702 | |
2703 | // If inverted, a successful match of the assertion must be treated |
2704 | // as a failure, so jump to backtracking. |
2705 | if (term->invert()) { |
2706 | op.m_jumps.append(jump()); |
2707 | op.m_reentry = label(); |
2708 | } |
2709 | |
2710 | YarrOp& lastOp = m_ops[op.m_previousOp]; |
2711 | m_checkedOffset += lastOp.m_checkAdjust; |
2712 | break; |
2713 | } |
2714 | |
2715 | case OpMatchFailed: |
2716 | removeCallFrame(); |
2717 | generateFailReturn(); |
2718 | break; |
2719 | } |
2720 | |
2721 | ++opIndex; |
2722 | } while (opIndex < m_ops.size()); |
2723 | } |
2724 | |
2725 | void backtrack() |
2726 | { |
2727 | // Backwards generate the backtracking code. |
2728 | size_t opIndex = m_ops.size(); |
2729 | ASSERT(opIndex); |
2730 | |
2731 | do { |
2732 | --opIndex; |
2733 | |
2734 | YarrOp& op = m_ops[opIndex]; |
2735 | switch (op.m_op) { |
2736 | |
2737 | case OpTerm: |
2738 | backtrackTerm(opIndex); |
2739 | break; |
2740 | |
2741 | // OpBodyAlternativeBegin/Next/End |
2742 | // |
2743 | // For each Begin/Next node representing an alternative, we need to decide what to do |
2744 | // in two circumstances: |
2745 | // - If we backtrack back into this node, from within the alternative. |
2746 | // - If the input check at the head of the alternative fails (if this exists). |
2747 | // |
2748 | // We treat these two cases differently since in the former case we have slightly |
2749 | // more information - since we are backtracking out of a prior alternative we know |
2750 | // that at least enough input was available to run it. For example, given the regular |
2751 | // expression /a|b/, if we backtrack out of the first alternative (a failed pattern |
2752 | // character match of 'a'), then we need not perform an additional input availability |
2753 | // check before running the second alternative. |
2754 | // |
2755 | // Backtracking required differs for the last alternative, which in the case of the |
2756 | // repeating set of alternatives must loop. The code generated for the last alternative |
2757 | // will also be used to handle all input check failures from any prior alternatives - |
2758 | // these require similar functionality, in seeking the next available alternative for |
2759 | // which there is sufficient input. |
2760 | // |
2761 | // Since backtracking of all other alternatives simply requires us to link backtracks |
2762 | // to the reentry point for the subsequent alternative, we will only be generating any |
2763 | // code when backtracking the last alternative. |
2764 | case OpBodyAlternativeBegin: |
2765 | case OpBodyAlternativeNext: { |
2766 | PatternAlternative* alternative = op.m_alternative; |
2767 | |
2768 | if (op.m_op == OpBodyAlternativeNext) { |
2769 | PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative; |
2770 | m_checkedOffset += priorAlternative->m_minimumSize; |
2771 | } |
2772 | m_checkedOffset -= alternative->m_minimumSize; |
2773 | |
2774 | // Is this the last alternative? If not, then if we backtrack to this point we just |
2775 | // need to jump to try to match the next alternative. |
2776 | if (m_ops[op.m_nextOp].m_op != OpBodyAlternativeEnd) { |
2777 | m_backtrackingState.linkTo(m_ops[op.m_nextOp].m_reentry, this); |
2778 | break; |
2779 | } |
2780 | YarrOp& endOp = m_ops[op.m_nextOp]; |
2781 | |
2782 | YarrOp* beginOp = &op; |
2783 | while (beginOp->m_op != OpBodyAlternativeBegin) { |
2784 | ASSERT(beginOp->m_op == OpBodyAlternativeNext); |
2785 | beginOp = &m_ops[beginOp->m_previousOp]; |
2786 | } |
2787 | |
2788 | bool onceThrough = endOp.m_nextOp == notFound; |
2789 | |
2790 | JumpList lastStickyAlternativeFailures; |
2791 | |
2792 | // First, generate code to handle cases where we backtrack out of an attempted match |
2793 | // of the last alternative. If this is a 'once through' set of alternatives then we |
2794 | // have nothing to do - link this straight through to the End. |
2795 | if (onceThrough) |
2796 | m_backtrackingState.linkTo(endOp.m_reentry, this); |
2797 | else { |
2798 | // If we don't need to move the input poistion, and the pattern has a fixed size |
2799 | // (in which case we omit the store of the start index until the pattern has matched) |
2800 | // then we can just link the backtrack out of the last alternative straight to the |
2801 | // head of the first alternative. |
2802 | if (m_pattern.m_body->m_hasFixedSize |
2803 | && (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize) |
2804 | && (alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize == 1)) |
2805 | m_backtrackingState.linkTo(beginOp->m_reentry, this); |
2806 | else if (m_pattern.sticky() && m_ops[op.m_nextOp].m_op == OpBodyAlternativeEnd) { |
2807 | // It is a sticky pattern and the last alternative failed, jump to the end. |
2808 | m_backtrackingState.takeBacktracksToJumpList(lastStickyAlternativeFailures, this); |
2809 | } else { |
2810 | // We need to generate a trampoline of code to execute before looping back |
2811 | // around to the first alternative. |
2812 | m_backtrackingState.link(this); |
2813 | |
2814 | // No need to advance and retry for a sticky pattern. |
2815 | if (!m_pattern.sticky()) { |
2816 | // If the pattern size is not fixed, then store the start index for use if we match. |
2817 | if (!m_pattern.m_body->m_hasFixedSize) { |
2818 | if (alternative->m_minimumSize == 1) |
2819 | setMatchStart(index); |
2820 | else { |
2821 | move(index, regT0); |
2822 | if (alternative->m_minimumSize) |
2823 | sub32(Imm32(alternative->m_minimumSize - 1), regT0); |
2824 | else |
2825 | add32(TrustedImm32(1), regT0); |
2826 | setMatchStart(regT0); |
2827 | } |
2828 | } |
2829 | |
2830 | // Generate code to loop. Check whether the last alternative is longer than the |
2831 | // first (e.g. /a|xy/ or /a|xyz/). |
2832 | if (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize) { |
2833 | // We want to loop, and increment input position. If the delta is 1, it is |
2834 | // already correctly incremented, if more than one then decrement as appropriate. |
2835 | unsigned delta = alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize; |
2836 | ASSERT(delta); |
2837 | if (delta != 1) |
2838 | sub32(Imm32(delta - 1), index); |
2839 | jump(beginOp->m_reentry); |
2840 | } else { |
2841 | // If the first alternative has minimum size 0xFFFFFFFFu, then there cannot |
2842 | // be sufficent input available to handle this, so just fall through. |
2843 | unsigned delta = beginOp->m_alternative->m_minimumSize - alternative->m_minimumSize; |
2844 | if (delta != 0xFFFFFFFFu) { |
2845 | // We need to check input because we are incrementing the input. |
2846 | add32(Imm32(delta + 1), index); |
2847 | checkInput().linkTo(beginOp->m_reentry, this); |
2848 | } |
2849 | } |
2850 | } |
2851 | } |
2852 | } |
2853 | |
2854 | // We can reach this point in the code in two ways: |
2855 | // - Fallthrough from the code above (a repeating alternative backtracked out of its |
2856 | // last alternative, and did not have sufficent input to run the first). |
2857 | // - We will loop back up to the following label when a repeating alternative loops, |
2858 | // following a failed input check. |
2859 | // |
2860 | // Either way, we have just failed the input check for the first alternative. |
2861 | Label firstInputCheckFailed(this); |
2862 | |
2863 | // Generate code to handle input check failures from alternatives except the last. |
2864 | // prevOp is the alternative we're handling a bail out from (initially Begin), and |
2865 | // nextOp is the alternative we will be attempting to reenter into. |
2866 | // |
2867 | // We will link input check failures from the forwards matching path back to the code |
2868 | // that can handle them. |
2869 | YarrOp* prevOp = beginOp; |
2870 | YarrOp* nextOp = &m_ops[beginOp->m_nextOp]; |
2871 | while (nextOp->m_op != OpBodyAlternativeEnd) { |
2872 | prevOp->m_jumps.link(this); |
2873 | |
2874 | // We only get here if an input check fails, it is only worth checking again |
2875 | // if the next alternative has a minimum size less than the last. |
2876 | if (prevOp->m_alternative->m_minimumSize > nextOp->m_alternative->m_minimumSize) { |
2877 | // FIXME: if we added an extra label to YarrOp, we could avoid needing to |
2878 | // subtract delta back out, and reduce this code. Should performance test |
2879 | // the benefit of this. |
2880 | unsigned delta = prevOp->m_alternative->m_minimumSize - nextOp->m_alternative->m_minimumSize; |
2881 | sub32(Imm32(delta), index); |
2882 | Jump fail = jumpIfNoAvailableInput(); |
2883 | add32(Imm32(delta), index); |
2884 | jump(nextOp->m_reentry); |
2885 | fail.link(masm: this); |
2886 | } else if (prevOp->m_alternative->m_minimumSize < nextOp->m_alternative->m_minimumSize) |
2887 | add32(Imm32(nextOp->m_alternative->m_minimumSize - prevOp->m_alternative->m_minimumSize), index); |
2888 | prevOp = nextOp; |
2889 | nextOp = &m_ops[nextOp->m_nextOp]; |
2890 | } |
2891 | |
2892 | // We fall through to here if there is insufficient input to run the last alternative. |
2893 | |
2894 | // If there is insufficient input to run the last alternative, then for 'once through' |
2895 | // alternatives we are done - just jump back up into the forwards matching path at the End. |
2896 | if (onceThrough) { |
2897 | op.m_jumps.linkTo(endOp.m_reentry, this); |
2898 | jump(endOp.m_reentry); |
2899 | break; |
2900 | } |
2901 | |
2902 | // For repeating alternatives, link any input check failure from the last alternative to |
2903 | // this point. |
2904 | op.m_jumps.link(this); |
2905 | |
2906 | bool needsToUpdateMatchStart = !m_pattern.m_body->m_hasFixedSize; |
2907 | |
2908 | // Check for cases where input position is already incremented by 1 for the last |
2909 | // alternative (this is particularly useful where the minimum size of the body |
2910 | // disjunction is 0, e.g. /a*|b/). |
2911 | if (needsToUpdateMatchStart && alternative->m_minimumSize == 1) { |
2912 | // index is already incremented by 1, so just store it now! |
2913 | setMatchStart(index); |
2914 | needsToUpdateMatchStart = false; |
2915 | } |
2916 | |
2917 | if (!m_pattern.sticky()) { |
2918 | // Check whether there is sufficient input to loop. Increment the input position by |
2919 | // one, and check. Also add in the minimum disjunction size before checking - there |
2920 | // is no point in looping if we're just going to fail all the input checks around |
2921 | // the next iteration. |
2922 | ASSERT(alternative->m_minimumSize >= m_pattern.m_body->m_minimumSize); |
2923 | if (alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) { |
2924 | // If the last alternative had the same minimum size as the disjunction, |
2925 | // just simply increment input pos by 1, no adjustment based on minimum size. |
2926 | add32(TrustedImm32(1), index); |
2927 | } else { |
2928 | // If the minumum for the last alternative was one greater than than that |
2929 | // for the disjunction, we're already progressed by 1, nothing to do! |
2930 | unsigned delta = (alternative->m_minimumSize - m_pattern.m_body->m_minimumSize) - 1; |
2931 | if (delta) |
2932 | sub32(Imm32(delta), index); |
2933 | } |
2934 | Jump matchFailed = jumpIfNoAvailableInput(); |
2935 | |
2936 | if (needsToUpdateMatchStart) { |
2937 | if (!m_pattern.m_body->m_minimumSize) |
2938 | setMatchStart(index); |
2939 | else { |
2940 | move(index, regT0); |
2941 | sub32(Imm32(m_pattern.m_body->m_minimumSize), regT0); |
2942 | setMatchStart(regT0); |
2943 | } |
2944 | } |
2945 | |
2946 | // Calculate how much more input the first alternative requires than the minimum |
2947 | // for the body as a whole. If no more is needed then we dont need an additional |
2948 | // input check here - jump straight back up to the start of the first alternative. |
2949 | if (beginOp->m_alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) |
2950 | jump(beginOp->m_reentry); |
2951 | else { |
2952 | if (beginOp->m_alternative->m_minimumSize > m_pattern.m_body->m_minimumSize) |
2953 | add32(Imm32(beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize), index); |
2954 | else |
2955 | sub32(Imm32(m_pattern.m_body->m_minimumSize - beginOp->m_alternative->m_minimumSize), index); |
2956 | checkInput().linkTo(beginOp->m_reentry, this); |
2957 | jump(firstInputCheckFailed); |
2958 | } |
2959 | |
2960 | // We jump to here if we iterate to the point that there is insufficient input to |
2961 | // run any matches, and need to return a failure state from JIT code. |
2962 | matchFailed.link(masm: this); |
2963 | } |
2964 | |
2965 | lastStickyAlternativeFailures.link(masm: this); |
2966 | removeCallFrame(); |
2967 | generateFailReturn(); |
2968 | break; |
2969 | } |
2970 | case OpBodyAlternativeEnd: { |
2971 | // We should never backtrack back into a body disjunction. |
2972 | ASSERT(m_backtrackingState.isEmpty()); |
2973 | |
2974 | PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative; |
2975 | m_checkedOffset += priorAlternative->m_minimumSize; |
2976 | break; |
2977 | } |
2978 | |
2979 | // OpSimpleNestedAlternativeBegin/Next/End |
2980 | // OpNestedAlternativeBegin/Next/End |
2981 | // |
2982 | // Generate code for when we backtrack back out of an alternative into |
2983 | // a Begin or Next node, or when the entry input count check fails. If |
2984 | // there are more alternatives we need to jump to the next alternative, |
2985 | // if not we backtrack back out of the current set of parentheses. |
2986 | // |
2987 | // In the case of non-simple nested assertions we need to also link the |
2988 | // 'return address' appropriately to backtrack back out into the correct |
2989 | // alternative. |
2990 | case OpSimpleNestedAlternativeBegin: |
2991 | case OpSimpleNestedAlternativeNext: |
2992 | case OpNestedAlternativeBegin: |
2993 | case OpNestedAlternativeNext: { |
2994 | YarrOp& nextOp = m_ops[op.m_nextOp]; |
2995 | bool isBegin = op.m_previousOp == notFound; |
2996 | bool isLastAlternative = nextOp.m_nextOp == notFound; |
2997 | ASSERT(isBegin == (op.m_op == OpSimpleNestedAlternativeBegin || op.m_op == OpNestedAlternativeBegin)); |
2998 | ASSERT(isLastAlternative == (nextOp.m_op == OpSimpleNestedAlternativeEnd || nextOp.m_op == OpNestedAlternativeEnd)); |
2999 | |
3000 | // Treat an input check failure the same as a failed match. |
3001 | m_backtrackingState.append(op.m_jumps); |
3002 | |
3003 | // Set the backtracks to jump to the appropriate place. We may need |
3004 | // to link the backtracks in one of three different way depending on |
3005 | // the type of alternative we are dealing with: |
3006 | // - A single alternative, with no simplings. |
3007 | // - The last alternative of a set of two or more. |
3008 | // - An alternative other than the last of a set of two or more. |
3009 | // |
3010 | // In the case of a single alternative on its own, we don't need to |
3011 | // jump anywhere - if the alternative fails to match we can just |
3012 | // continue to backtrack out of the parentheses without jumping. |
3013 | // |
3014 | // In the case of the last alternative in a set of more than one, we |
3015 | // need to jump to return back out to the beginning. We'll do so by |
3016 | // adding a jump to the End node's m_jumps list, and linking this |
3017 | // when we come to generate the Begin node. For alternatives other |
3018 | // than the last, we need to jump to the next alternative. |
3019 | // |
3020 | // If the alternative had adjusted the input position we must link |
3021 | // backtracking to here, correct, and then jump on. If not we can |
3022 | // link the backtracks directly to their destination. |
3023 | if (op.m_checkAdjust) { |
3024 | // Handle the cases where we need to link the backtracks here. |
3025 | m_backtrackingState.link(this); |
3026 | sub32(Imm32(op.m_checkAdjust.unsafeGet()), index); |
3027 | if (!isLastAlternative) { |
3028 | // An alternative that is not the last should jump to its successor. |
3029 | jump(nextOp.m_reentry); |
3030 | } else if (!isBegin) { |
3031 | // The last of more than one alternatives must jump back to the beginning. |
3032 | nextOp.m_jumps.append(jump()); |
3033 | } else { |
3034 | // A single alternative on its own can fall through. |
3035 | m_backtrackingState.fallthrough(); |
3036 | } |
3037 | } else { |
3038 | // Handle the cases where we can link the backtracks directly to their destinations. |
3039 | if (!isLastAlternative) { |
3040 | // An alternative that is not the last should jump to its successor. |
3041 | m_backtrackingState.linkTo(nextOp.m_reentry, this); |
3042 | } else if (!isBegin) { |
3043 | // The last of more than one alternatives must jump back to the beginning. |
3044 | m_backtrackingState.takeBacktracksToJumpList(nextOp.m_jumps, this); |
3045 | } |
3046 | // In the case of a single alternative on its own do nothing - it can fall through. |
3047 | } |
3048 | |
3049 | // If there is a backtrack jump from a zero length match link it here. |
3050 | if (op.m_zeroLengthMatch.isSet()) |
3051 | m_backtrackingState.append(op.m_zeroLengthMatch); |
3052 | |
3053 | // At this point we've handled the backtracking back into this node. |
3054 | // Now link any backtracks that need to jump to here. |
3055 | |
3056 | // For non-simple alternatives, link the alternative's 'return address' |
3057 | // so that we backtrack back out into the previous alternative. |
3058 | if (op.m_op == OpNestedAlternativeNext) |
3059 | m_backtrackingState.append(op.m_returnAddress); |
3060 | |
3061 | // If there is more than one alternative, then the last alternative will |
3062 | // have planted a jump to be linked to the end. This jump was added to the |
3063 | // End node's m_jumps list. If we are back at the beginning, link it here. |
3064 | if (isBegin) { |
3065 | YarrOp* endOp = &m_ops[op.m_nextOp]; |
3066 | while (endOp->m_nextOp != notFound) { |
3067 | ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext); |
3068 | endOp = &m_ops[endOp->m_nextOp]; |
3069 | } |
3070 | ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd); |
3071 | m_backtrackingState.append(endOp->m_jumps); |
3072 | } |
3073 | |
3074 | if (!isBegin) { |
3075 | YarrOp& lastOp = m_ops[op.m_previousOp]; |
3076 | m_checkedOffset += lastOp.m_checkAdjust; |
3077 | } |
3078 | m_checkedOffset -= op.m_checkAdjust; |
3079 | break; |
3080 | } |
3081 | case OpSimpleNestedAlternativeEnd: |
3082 | case OpNestedAlternativeEnd: { |
3083 | PatternTerm* term = op.m_term; |
3084 | |
3085 | // If there is a backtrack jump from a zero length match link it here. |
3086 | if (op.m_zeroLengthMatch.isSet()) |
3087 | m_backtrackingState.append(op.m_zeroLengthMatch); |
3088 | |
3089 | // If we backtrack into the end of a simple subpattern do nothing; |
3090 | // just continue through into the last alternative. If we backtrack |
3091 | // into the end of a non-simple set of alterntives we need to jump |
3092 | // to the backtracking return address set up during generation. |
3093 | if (op.m_op == OpNestedAlternativeEnd) { |
3094 | m_backtrackingState.link(this); |
3095 | |
3096 | // Plant a jump to the return address. |
3097 | unsigned parenthesesFrameLocation = term->frameLocation; |
3098 | loadFromFrameAndJump(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::returnAddressIndex()); |
3099 | |
3100 | // Link the DataLabelPtr associated with the end of the last |
3101 | // alternative to this point. |
3102 | m_backtrackingState.append(op.m_returnAddress); |
3103 | } |
3104 | |
3105 | YarrOp& lastOp = m_ops[op.m_previousOp]; |
3106 | m_checkedOffset += lastOp.m_checkAdjust; |
3107 | break; |
3108 | } |
3109 | |
3110 | // OpParenthesesSubpatternOnceBegin/End |
3111 | // |
3112 | // When we are backtracking back out of a capturing subpattern we need |
3113 | // to clear the start index in the matches output array, to record that |
3114 | // this subpattern has not been captured. |
3115 | // |
3116 | // When backtracking back out of a Greedy quantified subpattern we need |
3117 | // to catch this, and try running the remainder of the alternative after |
3118 | // the subpattern again, skipping the parentheses. |
3119 | // |
3120 | // Upon backtracking back into a quantified set of parentheses we need to |
3121 | // check whether we were currently skipping the subpattern. If not, we |
3122 | // can backtrack into them, if we were we need to either backtrack back |
3123 | // out of the start of the parentheses, or jump back to the forwards |
3124 | // matching start, depending of whether the match is Greedy or NonGreedy. |
3125 | case OpParenthesesSubpatternOnceBegin: { |
3126 | PatternTerm* term = op.m_term; |
3127 | ASSERT(term->quantityMaxCount == 1); |
3128 | |
3129 | // We only need to backtrack to this point if capturing or greedy. |
3130 | if ((term->capture() && compileMode == IncludeSubpatterns) || term->quantityType == QuantifierGreedy) { |
3131 | m_backtrackingState.link(this); |
3132 | |
3133 | // If capturing, clear the capture (we only need to reset start). |
3134 | if (term->capture() && compileMode == IncludeSubpatterns) |
3135 | clearSubpatternStart(subpattern: term->parentheses.subpatternId); |
3136 | |
3137 | // If Greedy, jump to the end. |
3138 | if (term->quantityType == QuantifierGreedy) { |
3139 | // Clear the flag in the stackframe indicating we ran through the subpattern. |
3140 | unsigned parenthesesFrameLocation = term->frameLocation; |
3141 | storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex()); |
3142 | // Jump to after the parentheses, skipping the subpattern. |
3143 | jump(m_ops[op.m_nextOp].m_reentry); |
3144 | // A backtrack from after the parentheses, when skipping the subpattern, |
3145 | // will jump back to here. |
3146 | op.m_jumps.link(this); |
3147 | } |
3148 | |
3149 | m_backtrackingState.fallthrough(); |
3150 | } |
3151 | break; |
3152 | } |
3153 | case OpParenthesesSubpatternOnceEnd: { |
3154 | PatternTerm* term = op.m_term; |
3155 | |
3156 | if (term->quantityType != QuantifierFixedCount) { |
3157 | m_backtrackingState.link(this); |
3158 | |
3159 | // Check whether we should backtrack back into the parentheses, or if we |
3160 | // are currently in a state where we had skipped over the subpattern |
3161 | // (in which case the flag value on the stack will be -1). |
3162 | unsigned parenthesesFrameLocation = term->frameLocation; |
3163 | Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, (parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex()) * sizeof(void*)), TrustedImm32(-1)); |
3164 | |
3165 | if (term->quantityType == QuantifierGreedy) { |
3166 | // For Greedy parentheses, we skip after having already tried going |
3167 | // through the subpattern, so if we get here we're done. |
3168 | YarrOp& beginOp = m_ops[op.m_previousOp]; |
3169 | beginOp.m_jumps.append(hadSkipped); |
3170 | } else { |
3171 | // For NonGreedy parentheses, we try skipping the subpattern first, |
3172 | // so if we get here we need to try running through the subpattern |
3173 | // next. Jump back to the start of the parentheses in the forwards |
3174 | // matching path. |
3175 | ASSERT(term->quantityType == QuantifierNonGreedy); |
3176 | YarrOp& beginOp = m_ops[op.m_previousOp]; |
3177 | hadSkipped.linkTo(label: beginOp.m_reentry, masm: this); |
3178 | } |
3179 | |
3180 | m_backtrackingState.fallthrough(); |
3181 | } |
3182 | |
3183 | m_backtrackingState.append(op.m_jumps); |
3184 | break; |
3185 | } |
3186 | |
3187 | // OpParenthesesSubpatternTerminalBegin/End |
3188 | // |
3189 | // Terminal subpatterns will always match - there is nothing after them to |
3190 | // force a backtrack, and they have a minimum count of 0, and as such will |
3191 | // always produce an acceptable result. |
3192 | case OpParenthesesSubpatternTerminalBegin: { |
3193 | // We will backtrack to this point once the subpattern cannot match any |
3194 | // more. Since no match is accepted as a successful match (we are Greedy |
3195 | // quantified with a minimum of zero) jump back to the forwards matching |
3196 | // path at the end. |
3197 | YarrOp& endOp = m_ops[op.m_nextOp]; |
3198 | m_backtrackingState.linkTo(endOp.m_reentry, this); |
3199 | break; |
3200 | } |
3201 | case OpParenthesesSubpatternTerminalEnd: |
3202 | // We should never be backtracking to here (hence the 'terminal' in the name). |
3203 | ASSERT(m_backtrackingState.isEmpty()); |
3204 | m_backtrackingState.append(op.m_jumps); |
3205 | break; |
3206 | |
3207 | // OpParenthesesSubpatternBegin/End |
3208 | // |
3209 | // When we are backtracking back out of a capturing subpattern we need |
3210 | // to clear the start index in the matches output array, to record that |
3211 | // this subpattern has not been captured. |
3212 | // |
3213 | // When backtracking back out of a Greedy quantified subpattern we need |
3214 | // to catch this, and try running the remainder of the alternative after |
3215 | // the subpattern again, skipping the parentheses. |
3216 | // |
3217 | // Upon backtracking back into a quantified set of parentheses we need to |
3218 | // check whether we were currently skipping the subpattern. If not, we |
3219 | // can backtrack into them, if we were we need to either backtrack back |
3220 | // out of the start of the parentheses, or jump back to the forwards |
3221 | // matching start, depending of whether the match is Greedy or NonGreedy. |
3222 | case OpParenthesesSubpatternBegin: { |
3223 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3224 | PatternTerm* term = op.m_term; |
3225 | unsigned parenthesesFrameLocation = term->frameLocation; |
3226 | |
3227 | if (term->quantityType != QuantifierFixedCount) { |
3228 | m_backtrackingState.link(this); |
3229 | |
3230 | RegisterID currParenContextReg = regT0; |
3231 | RegisterID newParenContextReg = regT1; |
3232 | |
3233 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex(), reg: currParenContextReg); |
3234 | |
3235 | restoreParenContext(parenContextReg: currParenContextReg, tempReg: regT2, firstSubpattern: term->parentheses.subpatternId, lastSubpattern: term->parentheses.lastSubpatternId, subpatternBaseFrameLocation: parenthesesFrameLocation); |
3236 | |
3237 | freeParenContext(headPtrRegister: currParenContextReg, newHeadPtrRegister: newParenContextReg); |
3238 | storeToFrame(newParenContextReg, parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex()); |
3239 | |
3240 | const RegisterID countTemporary = regT0; |
3241 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), reg: countTemporary); |
3242 | Jump zeroLengthMatch = branchTest32(Zero, countTemporary); |
3243 | |
3244 | sub32(TrustedImm32(1), countTemporary); |
3245 | storeToFrame(countTemporary, parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex()); |
3246 | |
3247 | jump(m_ops[op.m_nextOp].m_reentry); |
3248 | |
3249 | zeroLengthMatch.link(masm: this); |
3250 | |
3251 | // Clear the flag in the stackframe indicating we didn't run through the subpattern. |
3252 | storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex()); |
3253 | |
3254 | if (term->quantityType == QuantifierGreedy) |
3255 | jump(m_ops[op.m_nextOp].m_reentry); |
3256 | |
3257 | // If Greedy, jump to the end. |
3258 | if (term->quantityType == QuantifierGreedy) { |
3259 | // A backtrack from after the parentheses, when skipping the subpattern, |
3260 | // will jump back to here. |
3261 | op.m_jumps.link(this); |
3262 | } |
3263 | |
3264 | m_backtrackingState.fallthrough(); |
3265 | } |
3266 | #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS |
3267 | RELEASE_ASSERT_NOT_REACHED(); |
3268 | #endif |
3269 | break; |
3270 | } |
3271 | case OpParenthesesSubpatternEnd: { |
3272 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3273 | PatternTerm* term = op.m_term; |
3274 | |
3275 | if (term->quantityType != QuantifierFixedCount) { |
3276 | m_backtrackingState.link(this); |
3277 | |
3278 | unsigned parenthesesFrameLocation = term->frameLocation; |
3279 | |
3280 | if (term->quantityType == QuantifierGreedy) { |
3281 | // Check whether we should backtrack back into the parentheses, or if we |
3282 | // are currently in a state where we had skipped over the subpattern |
3283 | // (in which case the flag value on the stack will be -1). |
3284 | Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, (parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex()) * sizeof(void*)), TrustedImm32(-1)); |
3285 | |
3286 | // For Greedy parentheses, we skip after having already tried going |
3287 | // through the subpattern, so if we get here we're done. |
3288 | YarrOp& beginOp = m_ops[op.m_previousOp]; |
3289 | beginOp.m_jumps.append(hadSkipped); |
3290 | } else { |
3291 | // For NonGreedy parentheses, we try skipping the subpattern first, |
3292 | // so if we get here we need to try running through the subpattern |
3293 | // next. Jump back to the start of the parentheses in the forwards |
3294 | // matching path. |
3295 | ASSERT(term->quantityType == QuantifierNonGreedy); |
3296 | |
3297 | const RegisterID beginTemporary = regT0; |
3298 | const RegisterID countTemporary = regT1; |
3299 | |
3300 | YarrOp& beginOp = m_ops[op.m_previousOp]; |
3301 | |
3302 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex(), reg: beginTemporary); |
3303 | branch32(Equal, beginTemporary, TrustedImm32(-1)).linkTo(beginOp.m_reentry, this); |
3304 | |
3305 | JumpList exceededMatchLimit; |
3306 | |
3307 | if (term->quantityMaxCount != quantifyInfinite) { |
3308 | loadFromFrame(frameLocation: parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), reg: countTemporary); |
3309 | exceededMatchLimit.append(branch32(AboveOrEqual, countTemporary, Imm32(term->quantityMaxCount.unsafeGet()))); |
3310 | } |
3311 | |
3312 | branch32(Above, index, beginTemporary).linkTo(beginOp.m_reentry, this); |
3313 | |
3314 | exceededMatchLimit.link(masm: this); |
3315 | } |
3316 | |
3317 | m_backtrackingState.fallthrough(); |
3318 | } |
3319 | |
3320 | m_backtrackingState.append(op.m_jumps); |
3321 | #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS |
3322 | RELEASE_ASSERT_NOT_REACHED(); |
3323 | #endif |
3324 | break; |
3325 | } |
3326 | |
3327 | // OpParentheticalAssertionBegin/End |
3328 | case OpParentheticalAssertionBegin: { |
3329 | PatternTerm* term = op.m_term; |
3330 | YarrOp& endOp = m_ops[op.m_nextOp]; |
3331 | |
3332 | // We need to handle the backtracks upon backtracking back out |
3333 | // of a parenthetical assertion if either we need to correct |
3334 | // the input index, or the assertion was inverted. |
3335 | if (op.m_checkAdjust || term->invert()) { |
3336 | m_backtrackingState.link(this); |
3337 | |
3338 | if (op.m_checkAdjust) |
3339 | add32(Imm32(op.m_checkAdjust.unsafeGet()), index); |
3340 | |
3341 | // In an inverted assertion failure to match the subpattern |
3342 | // is treated as a successful match - jump to the end of the |
3343 | // subpattern. We already have adjusted the input position |
3344 | // back to that before the assertion, which is correct. |
3345 | if (term->invert()) |
3346 | jump(endOp.m_reentry); |
3347 | |
3348 | m_backtrackingState.fallthrough(); |
3349 | } |
3350 | |
3351 | // The End node's jump list will contain any backtracks into |
3352 | // the end of the assertion. Also, if inverted, we will have |
3353 | // added the failure caused by a successful match to this. |
3354 | m_backtrackingState.append(endOp.m_jumps); |
3355 | |
3356 | m_checkedOffset += op.m_checkAdjust; |
3357 | break; |
3358 | } |
3359 | case OpParentheticalAssertionEnd: { |
3360 | // FIXME: We should really be clearing any nested subpattern |
3361 | // matches on bailing out from after the pattern. Firefox has |
3362 | // this bug too (presumably because they use YARR!) |
3363 | |
3364 | // Never backtrack into an assertion; later failures bail to before the begin. |
3365 | m_backtrackingState.takeBacktracksToJumpList(op.m_jumps, this); |
3366 | |
3367 | YarrOp& lastOp = m_ops[op.m_previousOp]; |
3368 | m_checkedOffset -= lastOp.m_checkAdjust; |
3369 | break; |
3370 | } |
3371 | |
3372 | case OpMatchFailed: |
3373 | break; |
3374 | } |
3375 | |
3376 | } while (opIndex); |
3377 | } |
3378 | |
3379 | // Compilation methods: |
3380 | // ==================== |
3381 | |
3382 | // opCompileParenthesesSubpattern |
3383 | // Emits ops for a subpattern (set of parentheses). These consist |
3384 | // of a set of alternatives wrapped in an outer set of nodes for |
3385 | // the parentheses. |
3386 | // Supported types of parentheses are 'Once' (quantityMaxCount == 1), |
3387 | // 'Terminal' (non-capturing parentheses quantified as greedy |
3388 | // and infinite), and 0 based greedy / non-greedy quantified parentheses. |
3389 | // Alternatives will use the 'Simple' set of ops if either the |
3390 | // subpattern is terminal (in which case we will never need to |
3391 | // backtrack), or if the subpattern only contains one alternative. |
3392 | void opCompileParenthesesSubpattern(PatternTerm* term) |
3393 | { |
3394 | YarrOpCode parenthesesBeginOpCode; |
3395 | YarrOpCode parenthesesEndOpCode; |
3396 | YarrOpCode alternativeBeginOpCode = OpSimpleNestedAlternativeBegin; |
3397 | YarrOpCode alternativeNextOpCode = OpSimpleNestedAlternativeNext; |
3398 | YarrOpCode alternativeEndOpCode = OpSimpleNestedAlternativeEnd; |
3399 | |
3400 | // We can currently only compile quantity 1 subpatterns that are |
3401 | // not copies. We generate a copy in the case of a range quantifier, |
3402 | // e.g. /(?:x){3,9}/, or /(?:x)+/ (These are effectively expanded to |
3403 | // /(?:x){3,3}(?:x){0,6}/ and /(?:x)(?:x)*/ repectively). The problem |
3404 | // comes where the subpattern is capturing, in which case we would |
3405 | // need to restore the capture from the first subpattern upon a |
3406 | // failure in the second. |
3407 | if (term->quantityMinCount && term->quantityMinCount != term->quantityMaxCount) { |
3408 | m_failureReason = JITFailureReason::VariableCountedParenthesisWithNonZeroMinimum; |
3409 | return; |
3410 | } |
3411 | |
3412 | if (term->quantityMaxCount == 1 && !term->parentheses.isCopy) { |
3413 | // Select the 'Once' nodes. |
3414 | parenthesesBeginOpCode = OpParenthesesSubpatternOnceBegin; |
3415 | parenthesesEndOpCode = OpParenthesesSubpatternOnceEnd; |
3416 | |
3417 | // If there is more than one alternative we cannot use the 'simple' nodes. |
3418 | if (term->parentheses.disjunction->m_alternatives.size() != 1) { |
3419 | alternativeBeginOpCode = OpNestedAlternativeBegin; |
3420 | alternativeNextOpCode = OpNestedAlternativeNext; |
3421 | alternativeEndOpCode = OpNestedAlternativeEnd; |
3422 | } |
3423 | } else if (term->parentheses.isTerminal) { |
3424 | // Select the 'Terminal' nodes. |
3425 | parenthesesBeginOpCode = OpParenthesesSubpatternTerminalBegin; |
3426 | parenthesesEndOpCode = OpParenthesesSubpatternTerminalEnd; |
3427 | } else { |
3428 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3429 | // We only handle generic parenthesis with non-fixed counts. |
3430 | if (term->quantityType == QuantifierFixedCount) { |
3431 | // This subpattern is not supported by the JIT. |
3432 | m_failureReason = JITFailureReason::FixedCountParenthesizedSubpattern; |
3433 | return; |
3434 | } |
3435 | |
3436 | m_containsNestedSubpatterns = true; |
3437 | |
3438 | // Select the 'Generic' nodes. |
3439 | parenthesesBeginOpCode = OpParenthesesSubpatternBegin; |
3440 | parenthesesEndOpCode = OpParenthesesSubpatternEnd; |
3441 | |
3442 | // If there is more than one alternative we cannot use the 'simple' nodes. |
3443 | if (term->parentheses.disjunction->m_alternatives.size() != 1) { |
3444 | alternativeBeginOpCode = OpNestedAlternativeBegin; |
3445 | alternativeNextOpCode = OpNestedAlternativeNext; |
3446 | alternativeEndOpCode = OpNestedAlternativeEnd; |
3447 | } |
3448 | #else |
3449 | // This subpattern is not supported by the JIT. |
3450 | m_failureReason = JITFailureReason::ParenthesizedSubpattern; |
3451 | return; |
3452 | #endif |
3453 | } |
3454 | |
3455 | size_t parenBegin = m_ops.size(); |
3456 | m_ops.append(parenthesesBeginOpCode); |
3457 | |
3458 | m_ops.append(alternativeBeginOpCode); |
3459 | m_ops.last().m_previousOp = notFound; |
3460 | m_ops.last().m_term = term; |
3461 | Vector<std::unique_ptr<PatternAlternative>>& alternatives = term->parentheses.disjunction->m_alternatives; |
3462 | for (unsigned i = 0; i < alternatives.size(); ++i) { |
3463 | size_t lastOpIndex = m_ops.size() - 1; |
3464 | |
3465 | PatternAlternative* nestedAlternative = alternatives[i].get(); |
3466 | opCompileAlternative(alternative: nestedAlternative); |
3467 | |
3468 | size_t thisOpIndex = m_ops.size(); |
3469 | m_ops.append(YarrOp(alternativeNextOpCode)); |
3470 | |
3471 | YarrOp& lastOp = m_ops[lastOpIndex]; |
3472 | YarrOp& thisOp = m_ops[thisOpIndex]; |
3473 | |
3474 | lastOp.m_alternative = nestedAlternative; |
3475 | lastOp.m_nextOp = thisOpIndex; |
3476 | thisOp.m_previousOp = lastOpIndex; |
3477 | thisOp.m_term = term; |
3478 | } |
3479 | YarrOp& lastOp = m_ops.last(); |
3480 | ASSERT(lastOp.m_op == alternativeNextOpCode); |
3481 | lastOp.m_op = alternativeEndOpCode; |
3482 | lastOp.m_alternative = 0; |
3483 | lastOp.m_nextOp = notFound; |
3484 | |
3485 | size_t parenEnd = m_ops.size(); |
3486 | m_ops.append(parenthesesEndOpCode); |
3487 | |
3488 | m_ops[parenBegin].m_term = term; |
3489 | m_ops[parenBegin].m_previousOp = notFound; |
3490 | m_ops[parenBegin].m_nextOp = parenEnd; |
3491 | m_ops[parenEnd].m_term = term; |
3492 | m_ops[parenEnd].m_previousOp = parenBegin; |
3493 | m_ops[parenEnd].m_nextOp = notFound; |
3494 | } |
3495 | |
3496 | // opCompileParentheticalAssertion |
3497 | // Emits ops for a parenthetical assertion. These consist of an |
3498 | // OpSimpleNestedAlternativeBegin/Next/End set of nodes wrapping |
3499 | // the alternatives, with these wrapped by an outer pair of |
3500 | // OpParentheticalAssertionBegin/End nodes. |
3501 | // We can always use the OpSimpleNestedAlternative nodes in the |
3502 | // case of parenthetical assertions since these only ever match |
3503 | // once, and will never backtrack back into the assertion. |
3504 | void opCompileParentheticalAssertion(PatternTerm* term) |
3505 | { |
3506 | size_t parenBegin = m_ops.size(); |
3507 | m_ops.append(OpParentheticalAssertionBegin); |
3508 | |
3509 | m_ops.append(OpSimpleNestedAlternativeBegin); |
3510 | m_ops.last().m_previousOp = notFound; |
3511 | m_ops.last().m_term = term; |
3512 | Vector<std::unique_ptr<PatternAlternative>>& alternatives = term->parentheses.disjunction->m_alternatives; |
3513 | for (unsigned i = 0; i < alternatives.size(); ++i) { |
3514 | size_t lastOpIndex = m_ops.size() - 1; |
3515 | |
3516 | PatternAlternative* nestedAlternative = alternatives[i].get(); |
3517 | opCompileAlternative(alternative: nestedAlternative); |
3518 | |
3519 | size_t thisOpIndex = m_ops.size(); |
3520 | m_ops.append(YarrOp(OpSimpleNestedAlternativeNext)); |
3521 | |
3522 | YarrOp& lastOp = m_ops[lastOpIndex]; |
3523 | YarrOp& thisOp = m_ops[thisOpIndex]; |
3524 | |
3525 | lastOp.m_alternative = nestedAlternative; |
3526 | lastOp.m_nextOp = thisOpIndex; |
3527 | thisOp.m_previousOp = lastOpIndex; |
3528 | thisOp.m_term = term; |
3529 | } |
3530 | YarrOp& lastOp = m_ops.last(); |
3531 | ASSERT(lastOp.m_op == OpSimpleNestedAlternativeNext); |
3532 | lastOp.m_op = OpSimpleNestedAlternativeEnd; |
3533 | lastOp.m_alternative = 0; |
3534 | lastOp.m_nextOp = notFound; |
3535 | |
3536 | size_t parenEnd = m_ops.size(); |
3537 | m_ops.append(OpParentheticalAssertionEnd); |
3538 | |
3539 | m_ops[parenBegin].m_term = term; |
3540 | m_ops[parenBegin].m_previousOp = notFound; |
3541 | m_ops[parenBegin].m_nextOp = parenEnd; |
3542 | m_ops[parenEnd].m_term = term; |
3543 | m_ops[parenEnd].m_previousOp = parenBegin; |
3544 | m_ops[parenEnd].m_nextOp = notFound; |
3545 | } |
3546 | |
3547 | // opCompileAlternative |
3548 | // Called to emit nodes for all terms in an alternative. |
3549 | void opCompileAlternative(PatternAlternative* alternative) |
3550 | { |
3551 | optimizeAlternative(alternative); |
3552 | |
3553 | for (unsigned i = 0; i < alternative->m_terms.size(); ++i) { |
3554 | PatternTerm* term = &alternative->m_terms[i]; |
3555 | |
3556 | switch (term->type) { |
3557 | case PatternTerm::TypeParenthesesSubpattern: |
3558 | opCompileParenthesesSubpattern(term); |
3559 | break; |
3560 | |
3561 | case PatternTerm::TypeParentheticalAssertion: |
3562 | opCompileParentheticalAssertion(term); |
3563 | break; |
3564 | |
3565 | default: |
3566 | m_ops.append(term); |
3567 | } |
3568 | } |
3569 | } |
3570 | |
3571 | // opCompileBody |
3572 | // This method compiles the body disjunction of the regular expression. |
3573 | // The body consists of two sets of alternatives - zero or more 'once |
3574 | // through' (BOL anchored) alternatives, followed by zero or more |
3575 | // repeated alternatives. |
3576 | // For each of these two sets of alteratives, if not empty they will be |
3577 | // wrapped in a set of OpBodyAlternativeBegin/Next/End nodes (with the |
3578 | // 'begin' node referencing the first alternative, and 'next' nodes |
3579 | // referencing any further alternatives. The begin/next/end nodes are |
3580 | // linked together in a doubly linked list. In the case of repeating |
3581 | // alternatives, the end node is also linked back to the beginning. |
3582 | // If no repeating alternatives exist, then a OpMatchFailed node exists |
3583 | // to return the failing result. |
3584 | void opCompileBody(PatternDisjunction* disjunction) |
3585 | { |
3586 | Vector<std::unique_ptr<PatternAlternative>>& alternatives = disjunction->m_alternatives; |
3587 | size_t currentAlternativeIndex = 0; |
3588 | |
3589 | // Emit the 'once through' alternatives. |
3590 | if (alternatives.size() && alternatives[0]->onceThrough()) { |
3591 | m_ops.append(YarrOp(OpBodyAlternativeBegin)); |
3592 | m_ops.last().m_previousOp = notFound; |
3593 | |
3594 | do { |
3595 | size_t lastOpIndex = m_ops.size() - 1; |
3596 | PatternAlternative* alternative = alternatives[currentAlternativeIndex].get(); |
3597 | opCompileAlternative(alternative); |
3598 | |
3599 | size_t thisOpIndex = m_ops.size(); |
3600 | m_ops.append(YarrOp(OpBodyAlternativeNext)); |
3601 | |
3602 | YarrOp& lastOp = m_ops[lastOpIndex]; |
3603 | YarrOp& thisOp = m_ops[thisOpIndex]; |
3604 | |
3605 | lastOp.m_alternative = alternative; |
3606 | lastOp.m_nextOp = thisOpIndex; |
3607 | thisOp.m_previousOp = lastOpIndex; |
3608 | |
3609 | ++currentAlternativeIndex; |
3610 | } while (currentAlternativeIndex < alternatives.size() && alternatives[currentAlternativeIndex]->onceThrough()); |
3611 | |
3612 | YarrOp& lastOp = m_ops.last(); |
3613 | |
3614 | ASSERT(lastOp.m_op == OpBodyAlternativeNext); |
3615 | lastOp.m_op = OpBodyAlternativeEnd; |
3616 | lastOp.m_alternative = 0; |
3617 | lastOp.m_nextOp = notFound; |
3618 | } |
3619 | |
3620 | if (currentAlternativeIndex == alternatives.size()) { |
3621 | m_ops.append(YarrOp(OpMatchFailed)); |
3622 | return; |
3623 | } |
3624 | |
3625 | // Emit the repeated alternatives. |
3626 | size_t repeatLoop = m_ops.size(); |
3627 | m_ops.append(YarrOp(OpBodyAlternativeBegin)); |
3628 | m_ops.last().m_previousOp = notFound; |
3629 | do { |
3630 | size_t lastOpIndex = m_ops.size() - 1; |
3631 | PatternAlternative* alternative = alternatives[currentAlternativeIndex].get(); |
3632 | ASSERT(!alternative->onceThrough()); |
3633 | opCompileAlternative(alternative); |
3634 | |
3635 | size_t thisOpIndex = m_ops.size(); |
3636 | m_ops.append(YarrOp(OpBodyAlternativeNext)); |
3637 | |
3638 | YarrOp& lastOp = m_ops[lastOpIndex]; |
3639 | YarrOp& thisOp = m_ops[thisOpIndex]; |
3640 | |
3641 | lastOp.m_alternative = alternative; |
3642 | lastOp.m_nextOp = thisOpIndex; |
3643 | thisOp.m_previousOp = lastOpIndex; |
3644 | |
3645 | ++currentAlternativeIndex; |
3646 | } while (currentAlternativeIndex < alternatives.size()); |
3647 | YarrOp& lastOp = m_ops.last(); |
3648 | ASSERT(lastOp.m_op == OpBodyAlternativeNext); |
3649 | lastOp.m_op = OpBodyAlternativeEnd; |
3650 | lastOp.m_alternative = 0; |
3651 | lastOp.m_nextOp = repeatLoop; |
3652 | } |
3653 | |
3654 | void generateTryReadUnicodeCharacterHelper() |
3655 | { |
3656 | #ifdef JIT_UNICODE_EXPRESSIONS |
3657 | if (m_tryReadUnicodeCharacterCalls.isEmpty()) |
3658 | return; |
3659 | |
3660 | ASSERT(m_decodeSurrogatePairs); |
3661 | |
3662 | m_tryReadUnicodeCharacterEntry = label(); |
3663 | |
3664 | tryReadUnicodeCharImpl(resultReg: regT0); |
3665 | |
3666 | ret(); |
3667 | #endif |
3668 | } |
3669 | |
3670 | void generateEnter() |
3671 | { |
3672 | #if CPU(X86_64) |
3673 | push(X86Registers::ebp); |
3674 | move(stackPointerRegister, X86Registers::ebp); |
3675 | |
3676 | if (m_pattern.m_saveInitialStartValue) |
3677 | push(X86Registers::ebx); |
3678 | |
3679 | #if OS(WINDOWS) |
3680 | push(X86Registers::edi); |
3681 | #endif |
3682 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3683 | if (m_containsNestedSubpatterns) { |
3684 | #if OS(WINDOWS) |
3685 | push(X86Registers::esi); |
3686 | #endif |
3687 | push(X86Registers::r12); |
3688 | } |
3689 | #endif |
3690 | |
3691 | if (m_decodeSurrogatePairs) { |
3692 | push(X86Registers::r13); |
3693 | push(X86Registers::r14); |
3694 | push(X86Registers::r15); |
3695 | |
3696 | move(TrustedImm32(0xd800), leadingSurrogateTag); |
3697 | move(TrustedImm32(0xdc00), trailingSurrogateTag); |
3698 | } |
3699 | // The ABI doesn't guarantee the upper bits are zero on unsigned arguments, so clear them ourselves. |
3700 | zeroExtend32ToPtr(src: index, dest: index); |
3701 | zeroExtend32ToPtr(src: length, dest: length); |
3702 | #if OS(WINDOWS) |
3703 | if (compileMode == IncludeSubpatterns) |
3704 | loadPtr(Address(X86Registers::ebp, 6 * sizeof(void*)), output); |
3705 | // rcx is the pointer to the allocated space for result in x64 Windows. |
3706 | push(X86Registers::ecx); |
3707 | #endif |
3708 | #elif CPU(X86) |
3709 | push(X86Registers::ebp); |
3710 | move(stackPointerRegister, X86Registers::ebp); |
3711 | // TODO: do we need spill registers to fill the output pointer if there are no sub captures? |
3712 | push(X86Registers::ebx); |
3713 | push(X86Registers::edi); |
3714 | push(X86Registers::esi); |
3715 | // load output into edi (2 = saved ebp + return address). |
3716 | #if COMPILER(MSVC) |
3717 | loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input); |
3718 | loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index); |
3719 | loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length); |
3720 | if (compileMode == IncludeSubpatterns) |
3721 | loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output); |
3722 | #else |
3723 | if (compileMode == IncludeSubpatterns) |
3724 | loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output); |
3725 | #endif |
3726 | #elif CPU(ARM64) |
3727 | if (m_decodeSurrogatePairs) { |
3728 | pushPair(framePointerRegister, linkRegister); |
3729 | move(TrustedImm32(0x10000), supplementaryPlanesBase); |
3730 | move(TrustedImm32(0xfffffc00), surrogateTagMask); |
3731 | move(TrustedImm32(0xd800), leadingSurrogateTag); |
3732 | move(TrustedImm32(0xdc00), trailingSurrogateTag); |
3733 | } |
3734 | |
3735 | // The ABI doesn't guarantee the upper bits are zero on unsigned arguments, so clear them ourselves. |
3736 | zeroExtend32ToPtr(index, index); |
3737 | zeroExtend32ToPtr(length, length); |
3738 | #elif CPU(ARM_THUMB2) |
3739 | push(ARMRegisters::r4); |
3740 | push(ARMRegisters::r5); |
3741 | push(ARMRegisters::r6); |
3742 | push(ARMRegisters::r8); |
3743 | #elif CPU(MIPS) |
3744 | // Do nothing. |
3745 | #endif |
3746 | |
3747 | store8(TrustedImm32(1), &m_vm->isExecutingInRegExpJIT); |
3748 | } |
3749 | |
3750 | void generateReturn() |
3751 | { |
3752 | store8(TrustedImm32(0), &m_vm->isExecutingInRegExpJIT); |
3753 | |
3754 | #if CPU(X86_64) |
3755 | #if OS(WINDOWS) |
3756 | // Store the return value in the allocated space pointed by rcx. |
3757 | pop(X86Registers::ecx); |
3758 | store64(returnRegister, Address(X86Registers::ecx)); |
3759 | store64(returnRegister2, Address(X86Registers::ecx, sizeof(void*))); |
3760 | move(X86Registers::ecx, returnRegister); |
3761 | #endif |
3762 | if (m_decodeSurrogatePairs) { |
3763 | pop(X86Registers::r15); |
3764 | pop(X86Registers::r14); |
3765 | pop(X86Registers::r13); |
3766 | } |
3767 | |
3768 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3769 | if (m_containsNestedSubpatterns) { |
3770 | pop(X86Registers::r12); |
3771 | #if OS(WINDOWS) |
3772 | pop(X86Registers::esi); |
3773 | #endif |
3774 | } |
3775 | #endif |
3776 | #if OS(WINDOWS) |
3777 | pop(X86Registers::edi); |
3778 | #endif |
3779 | |
3780 | if (m_pattern.m_saveInitialStartValue) |
3781 | pop(X86Registers::ebx); |
3782 | pop(X86Registers::ebp); |
3783 | #elif CPU(X86) |
3784 | pop(X86Registers::esi); |
3785 | pop(X86Registers::edi); |
3786 | pop(X86Registers::ebx); |
3787 | pop(X86Registers::ebp); |
3788 | #elif CPU(ARM64) |
3789 | if (m_decodeSurrogatePairs) |
3790 | popPair(framePointerRegister, linkRegister); |
3791 | #elif CPU(ARM_THUMB2) |
3792 | pop(ARMRegisters::r8); |
3793 | pop(ARMRegisters::r6); |
3794 | pop(ARMRegisters::r5); |
3795 | pop(ARMRegisters::r4); |
3796 | #elif CPU(MIPS) |
3797 | // Do nothing |
3798 | #endif |
3799 | ret(); |
3800 | } |
3801 | |
3802 | public: |
3803 | YarrGenerator(VM* vm, YarrPattern& pattern, YarrCodeBlock& codeBlock, YarrCharSize charSize) |
3804 | : m_vm(vm) |
3805 | , m_pattern(pattern) |
3806 | , m_codeBlock(codeBlock) |
3807 | , m_charSize(charSize) |
3808 | , m_decodeSurrogatePairs(m_charSize == Char16 && m_pattern.unicode()) |
3809 | , m_unicodeIgnoreCase(m_pattern.unicode() && m_pattern.ignoreCase()) |
3810 | , m_canonicalMode(m_pattern.unicode() ? CanonicalMode::Unicode : CanonicalMode::UCS2) |
3811 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3812 | , m_containsNestedSubpatterns(false) |
3813 | , m_parenContextSizes(compileMode == IncludeSubpatterns ? m_pattern.m_numSubpatterns : 0, m_pattern.m_body->m_callFrameSize) |
3814 | #endif |
3815 | { |
3816 | } |
3817 | |
3818 | void compile() |
3819 | { |
3820 | YarrCodeBlock& codeBlock = m_codeBlock; |
3821 | |
3822 | #ifndef JIT_UNICODE_EXPRESSIONS |
3823 | if (m_decodeSurrogatePairs) { |
3824 | codeBlock.setFallBackWithFailureReason(JITFailureReason::DecodeSurrogatePair); |
3825 | return; |
3826 | } |
3827 | #endif |
3828 | |
3829 | if (m_pattern.m_containsBackreferences |
3830 | #if ENABLE(YARR_JIT_BACKREFERENCES) |
3831 | && (compileMode == MatchOnly || (m_pattern.ignoreCase() && m_charSize != Char8)) |
3832 | #endif |
3833 | ) { |
3834 | codeBlock.setFallBackWithFailureReason(JITFailureReason::BackReference); |
3835 | return; |
3836 | } |
3837 | |
3838 | // We need to compile before generating code since we set flags based on compilation that |
3839 | // are used during generation. |
3840 | opCompileBody(disjunction: m_pattern.m_body); |
3841 | |
3842 | if (m_failureReason) { |
3843 | codeBlock.setFallBackWithFailureReason(*m_failureReason); |
3844 | return; |
3845 | } |
3846 | |
3847 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3848 | if (m_containsNestedSubpatterns) |
3849 | codeBlock.setUsesPatternContextBuffer(); |
3850 | #endif |
3851 | |
3852 | generateEnter(); |
3853 | |
3854 | Jump hasInput = checkInput(); |
3855 | generateFailReturn(); |
3856 | hasInput.link(masm: this); |
3857 | |
3858 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3859 | if (m_containsNestedSubpatterns) |
3860 | move(TrustedImm32(matchLimit), remainingMatchCount); |
3861 | #endif |
3862 | |
3863 | if (compileMode == IncludeSubpatterns) { |
3864 | for (unsigned i = 0; i < m_pattern.m_numSubpatterns + 1; ++i) |
3865 | store32(TrustedImm32(-1), Address(output, (i << 1) * sizeof(int))); |
3866 | } |
3867 | |
3868 | if (!m_pattern.m_body->m_hasFixedSize) |
3869 | setMatchStart(index); |
3870 | |
3871 | initCallFrame(); |
3872 | |
3873 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3874 | if (m_containsNestedSubpatterns) |
3875 | initParenContextFreeList(); |
3876 | #endif |
3877 | |
3878 | if (m_pattern.m_saveInitialStartValue) { |
3879 | #ifdef HAVE_INITIAL_START_REG |
3880 | move(index, initialStart); |
3881 | #else |
3882 | storeToFrame(index, m_pattern.m_initialStartValueFrameLocation); |
3883 | #endif |
3884 | } |
3885 | |
3886 | generate(); |
3887 | backtrack(); |
3888 | |
3889 | generateTryReadUnicodeCharacterHelper(); |
3890 | |
3891 | generateJITFailReturn(); |
3892 | |
3893 | JSGlobalData data(m_vm->regExpAllocator); |
3894 | DefaultLinkBuffer linkBuffer(data, this, REGEXP_CODE_ID, JITCompilationCanFail); |
3895 | if (linkBuffer.didFailToAllocate()) { |
3896 | codeBlock.setFallBackWithFailureReason(JITFailureReason::ExecutableMemoryAllocationFailure); |
3897 | return; |
3898 | } |
3899 | |
3900 | if (!m_tryReadUnicodeCharacterCalls.isEmpty()) { |
3901 | CodeLocationLabel tryReadUnicodeCharacterHelper = linkBuffer.locationOf(label: m_tryReadUnicodeCharacterEntry); |
3902 | |
3903 | for (auto call : m_tryReadUnicodeCharacterCalls) |
3904 | linkBuffer.link(call, function: tryReadUnicodeCharacterHelper); |
3905 | } |
3906 | |
3907 | m_backtrackingState.linkDataLabels(linkBuffer); |
3908 | |
3909 | CodeRef codeRef; |
3910 | if (compileMode == MatchOnly) { |
3911 | if (m_charSize == Char8) { |
3912 | codeRef = FINALIZE_CODE(linkBuffer, "YarrJIT" , |
3913 | "Match-only 8-bit regular expression" ); |
3914 | codeBlock.set8BitCodeMatchOnly(codeRef); |
3915 | } else { |
3916 | codeRef = FINALIZE_CODE(linkBuffer, "YarrJIT" , |
3917 | "Match-only 16-bit regular expression" ); |
3918 | codeBlock.set16BitCodeMatchOnly(codeRef); |
3919 | } |
3920 | } else { |
3921 | if (m_charSize == Char8) { |
3922 | codeRef = FINALIZE_CODE(linkBuffer, "YarrJIT" , "8-bit regular expression" ); |
3923 | codeBlock.set8BitCode(codeRef); |
3924 | } else { |
3925 | codeRef = FINALIZE_CODE(linkBuffer, "YarrJIT" , "16-bit regular expression" ); |
3926 | codeBlock.set16BitCode(codeRef); |
3927 | } |
3928 | } |
3929 | QV4::generateFunctionTable(function: nullptr, codeRef: &codeRef); |
3930 | |
3931 | if (Q_UNLIKELY(!linkBuffer.makeExecutable())) |
3932 | m_failureReason = JITFailureReason::ExecutableMemoryAllocationFailure; |
3933 | |
3934 | if (m_failureReason) |
3935 | codeBlock.setFallBackWithFailureReason(*m_failureReason); |
3936 | } |
3937 | |
3938 | private: |
3939 | VM* m_vm; |
3940 | |
3941 | YarrPattern& m_pattern; |
3942 | |
3943 | YarrCodeBlock& m_codeBlock; |
3944 | YarrCharSize m_charSize; |
3945 | |
3946 | // Used to detect regular expression constructs that are not currently |
3947 | // supported in the JIT; fall back to the interpreter when this is detected. |
3948 | std::optional<JITFailureReason> m_failureReason; |
3949 | |
3950 | bool m_decodeSurrogatePairs; |
3951 | bool m_unicodeIgnoreCase; |
3952 | CanonicalMode m_canonicalMode; |
3953 | #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) |
3954 | bool m_containsNestedSubpatterns; |
3955 | ParenContextSizes m_parenContextSizes; |
3956 | #endif |
3957 | JumpList m_abortExecution; |
3958 | JumpList m_hitMatchLimit; |
3959 | Vector<Call> m_tryReadUnicodeCharacterCalls; |
3960 | Label m_tryReadUnicodeCharacterEntry; |
3961 | |
3962 | // The regular expression expressed as a linear sequence of operations. |
3963 | Vector<YarrOp, 128> m_ops; |
3964 | |
3965 | // This records the current input offset being applied due to the current |
3966 | // set of alternatives we are nested within. E.g. when matching the |
3967 | // character 'b' within the regular expression /abc/, we will know that |
3968 | // the minimum size for the alternative is 3, checked upon entry to the |
3969 | // alternative, and that 'b' is at offset 1 from the start, and as such |
3970 | // when matching 'b' we need to apply an offset of -2 to the load. |
3971 | // |
3972 | // FIXME: This should go away. Rather than tracking this value throughout |
3973 | // code generation, we should gather this information up front & store it |
3974 | // on the YarrOp structure. |
3975 | Checked<unsigned> m_checkedOffset; |
3976 | |
3977 | // This class records state whilst generating the backtracking path of code. |
3978 | BacktrackingState m_backtrackingState; |
3979 | }; |
3980 | |
3981 | void YarrCodeBlock::replaceCodeRef(MacroAssemblerCodeRef &target, |
3982 | const MacroAssemblerCodeRef &source) |
3983 | { |
3984 | if (!!target && target.code().executableAddress() != source.code().executableAddress()) |
3985 | QV4::destroyFunctionTable(function: nullptr, codeRef: &target); |
3986 | |
3987 | target = source; |
3988 | } |
3989 | |
3990 | static void dumpCompileFailure(JITFailureReason failure) |
3991 | { |
3992 | switch (failure) { |
3993 | case JITFailureReason::DecodeSurrogatePair: |
3994 | dataLog(value: "Can't JIT a pattern decoding surrogate pairs\n" ); |
3995 | break; |
3996 | case JITFailureReason::BackReference: |
3997 | dataLog(value: "Can't JIT some patterns containing back references\n" ); |
3998 | break; |
3999 | case JITFailureReason::ForwardReference: |
4000 | dataLog(value: "Can't JIT a pattern containing forward references\n" ); |
4001 | break; |
4002 | case JITFailureReason::VariableCountedParenthesisWithNonZeroMinimum: |
4003 | dataLog(value: "Can't JIT a pattern containing a variable counted parenthesis with a non-zero minimum\n" ); |
4004 | break; |
4005 | case JITFailureReason::ParenthesizedSubpattern: |
4006 | dataLog(value: "Can't JIT a pattern containing parenthesized subpatterns\n" ); |
4007 | break; |
4008 | case JITFailureReason::FixedCountParenthesizedSubpattern: |
4009 | dataLog(value: "Can't JIT a pattern containing fixed count parenthesized subpatterns\n" ); |
4010 | break; |
4011 | case JITFailureReason::ExecutableMemoryAllocationFailure: |
4012 | dataLog(value: "Can't JIT because of failure of allocation of executable memory\n" ); |
4013 | break; |
4014 | } |
4015 | } |
4016 | |
4017 | void jitCompile(YarrPattern& pattern, YarrCharSize charSize, VM* vm, YarrCodeBlock& codeBlock, YarrJITCompileMode mode) |
4018 | { |
4019 | if (mode == MatchOnly) |
4020 | YarrGenerator<MatchOnly>(vm, pattern, codeBlock, charSize).compile(); |
4021 | else |
4022 | YarrGenerator<IncludeSubpatterns>(vm, pattern, codeBlock, charSize).compile(); |
4023 | |
4024 | if (auto failureReason = codeBlock.failureReason()) { |
4025 | if (Options::dumpCompiledRegExpPatterns()) |
4026 | dumpCompileFailure(failure: *failureReason); |
4027 | } |
4028 | } |
4029 | |
4030 | }} |
4031 | |
4032 | #endif |
4033 | |