1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/yarr/YarrJIT.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,2804 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + *
1.7 + * Copyright (C) 2009 Apple Inc. All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions
1.11 + * are met:
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + * 2. Redistributions in binary form must reproduce the above copyright
1.15 + * notice, this list of conditions and the following disclaimer in the
1.16 + * documentation and/or other materials provided with the distribution.
1.17 + *
1.18 + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
1.19 + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.20 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
1.21 + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
1.22 + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
1.23 + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
1.24 + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
1.25 + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
1.26 + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.27 + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.28 + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.29 + */
1.30 +
1.31 +#include "yarr/YarrJIT.h"
1.32 +
1.33 +#include "assembler/assembler/LinkBuffer.h"
1.34 +#include "yarr/Yarr.h"
1.35 +#include "yarr/YarrCanonicalizeUCS2.h"
1.36 +
1.37 +#if ENABLE_YARR_JIT
1.38 +
1.39 +using namespace WTF;
1.40 +
1.41 +namespace JSC { namespace Yarr {
1.42 +
1.43 +template<YarrJITCompileMode compileMode>
1.44 +class YarrGenerator : private MacroAssembler {
1.45 + friend void jitCompile(JSGlobalData*, YarrCodeBlock& jitObject, const String& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);
1.46 +
1.47 +#if WTF_CPU_ARM
1.48 + static const RegisterID input = ARMRegisters::r0;
1.49 + static const RegisterID index = ARMRegisters::r1;
1.50 + static const RegisterID length = ARMRegisters::r2;
1.51 + static const RegisterID output = ARMRegisters::r4;
1.52 +
1.53 + static const RegisterID regT0 = ARMRegisters::r5;
1.54 + static const RegisterID regT1 = ARMRegisters::r6;
1.55 +
1.56 + static const RegisterID returnRegister = ARMRegisters::r0;
1.57 + static const RegisterID returnRegister2 = ARMRegisters::r1;
1.58 +#elif WTF_CPU_MIPS
1.59 + static const RegisterID input = MIPSRegisters::a0;
1.60 + static const RegisterID index = MIPSRegisters::a1;
1.61 + static const RegisterID length = MIPSRegisters::a2;
1.62 + static const RegisterID output = MIPSRegisters::a3;
1.63 +
1.64 + static const RegisterID regT0 = MIPSRegisters::t4;
1.65 + static const RegisterID regT1 = MIPSRegisters::t5;
1.66 +
1.67 + static const RegisterID returnRegister = MIPSRegisters::v0;
1.68 + static const RegisterID returnRegister2 = MIPSRegisters::v1;
1.69 +#elif WTF_CPU_SH4
1.70 + static const RegisterID input = SH4Registers::r4;
1.71 + static const RegisterID index = SH4Registers::r5;
1.72 + static const RegisterID length = SH4Registers::r6;
1.73 + static const RegisterID output = SH4Registers::r7;
1.74 +
1.75 + static const RegisterID regT0 = SH4Registers::r0;
1.76 + static const RegisterID regT1 = SH4Registers::r1;
1.77 +
1.78 + static const RegisterID returnRegister = SH4Registers::r0;
1.79 + static const RegisterID returnRegister2 = SH4Registers::r1;
1.80 +#elif WTF_CPU_SPARC
1.81 + static const RegisterID input = SparcRegisters::i0;
1.82 + static const RegisterID index = SparcRegisters::i1;
1.83 + static const RegisterID length = SparcRegisters::i2;
1.84 + static const RegisterID output = SparcRegisters::i3;
1.85 +
1.86 + static const RegisterID regT0 = SparcRegisters::i4;
1.87 + static const RegisterID regT1 = SparcRegisters::i5;
1.88 +
1.89 + static const RegisterID returnRegister = SparcRegisters::i0;
1.90 +#elif WTF_CPU_X86
1.91 + static const RegisterID input = X86Registers::eax;
1.92 + static const RegisterID index = X86Registers::edx;
1.93 + static const RegisterID length = X86Registers::ecx;
1.94 + static const RegisterID output = X86Registers::edi;
1.95 +
1.96 + static const RegisterID regT0 = X86Registers::ebx;
1.97 + static const RegisterID regT1 = X86Registers::esi;
1.98 +
1.99 + static const RegisterID returnRegister = X86Registers::eax;
1.100 + static const RegisterID returnRegister2 = X86Registers::edx;
1.101 +#elif WTF_CPU_X86_64
1.102 +# if WTF_PLATFORM_WIN
1.103 + static const RegisterID input = X86Registers::ecx;
1.104 + static const RegisterID index = X86Registers::edx;
1.105 + static const RegisterID length = X86Registers::r8;
1.106 + static const RegisterID output = X86Registers::r9;
1.107 +# else
1.108 + static const RegisterID input = X86Registers::edi;
1.109 + static const RegisterID index = X86Registers::esi;
1.110 + static const RegisterID length = X86Registers::edx;
1.111 + static const RegisterID output = X86Registers::ecx;
1.112 +# endif
1.113 +
1.114 + static const RegisterID regT0 = X86Registers::eax;
1.115 + static const RegisterID regT1 = X86Registers::ebx;
1.116 +
1.117 + static const RegisterID returnRegister = X86Registers::eax;
1.118 +
1.119 +# if !WTF_PLATFORM_WIN
1.120 + // no way to use int128_t as return value on Win64 ABI
1.121 + static const RegisterID returnRegister2 = X86Registers::edx;
1.122 +# endif
1.123 +#endif
1.124 +
1.125 + void optimizeAlternative(PatternAlternative* alternative)
1.126 + {
1.127 + if (!alternative->m_terms.size())
1.128 + return;
1.129 +
1.130 + for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {
1.131 + PatternTerm& term = alternative->m_terms[i];
1.132 + PatternTerm& nextTerm = alternative->m_terms[i + 1];
1.133 +
1.134 + if ((term.type == PatternTerm::TypeCharacterClass)
1.135 + && (term.quantityType == QuantifierFixedCount)
1.136 + && (nextTerm.type == PatternTerm::TypePatternCharacter)
1.137 + && (nextTerm.quantityType == QuantifierFixedCount)) {
1.138 + PatternTerm termCopy = term;
1.139 + alternative->m_terms[i] = nextTerm;
1.140 + alternative->m_terms[i + 1] = termCopy;
1.141 + }
1.142 + }
1.143 + }
1.144 +
1.145 + void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
1.146 + {
1.147 + do {
1.148 + // pick which range we're going to generate
1.149 + int which = count >> 1;
1.150 + char lo = ranges[which].begin;
1.151 + char hi = ranges[which].end;
1.152 +
1.153 + // check if there are any ranges or matches below lo. If not, just jl to failure -
1.154 + // if there is anything else to check, check that first, if it falls through jmp to failure.
1.155 + if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
1.156 + Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
1.157 +
1.158 + // generate code for all ranges before this one
1.159 + if (which)
1.160 + matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
1.161 +
1.162 + while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
1.163 + matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
1.164 + ++*matchIndex;
1.165 + }
1.166 + failures.append(jump());
1.167 +
1.168 + loOrAbove.link(this);
1.169 + } else if (which) {
1.170 + Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
1.171 +
1.172 + matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
1.173 + failures.append(jump());
1.174 +
1.175 + loOrAbove.link(this);
1.176 + } else
1.177 + failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));
1.178 +
1.179 + while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
1.180 + ++*matchIndex;
1.181 +
1.182 + matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
1.183 + // fall through to here, the value is above hi.
1.184 +
1.185 + // shuffle along & loop around if there are any more matches to handle.
1.186 + unsigned next = which + 1;
1.187 + ranges += next;
1.188 + count -= next;
1.189 + } while (count);
1.190 + }
1.191 +
1.192 + void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
1.193 + {
1.194 + if (charClass->m_table) {
1.195 + ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table));
1.196 + matchDest.append(branchTest8(charClass->m_tableInverted ? Zero : NonZero, tableEntry));
1.197 + return;
1.198 + }
1.199 + Jump unicodeFail;
1.200 + if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
1.201 + Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f));
1.202 +
1.203 + if (charClass->m_matchesUnicode.size()) {
1.204 + for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {
1.205 + UChar ch = charClass->m_matchesUnicode[i];
1.206 + matchDest.append(branch32(Equal, character, Imm32(ch)));
1.207 + }
1.208 + }
1.209 +
1.210 + if (charClass->m_rangesUnicode.size()) {
1.211 + for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {
1.212 + UChar lo = charClass->m_rangesUnicode[i].begin;
1.213 + UChar hi = charClass->m_rangesUnicode[i].end;
1.214 +
1.215 + Jump below = branch32(LessThan, character, Imm32(lo));
1.216 + matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
1.217 + below.link(this);
1.218 + }
1.219 + }
1.220 +
1.221 + unicodeFail = jump();
1.222 + isAscii.link(this);
1.223 + }
1.224 +
1.225 + if (charClass->m_ranges.size()) {
1.226 + unsigned matchIndex = 0;
1.227 + JumpList failures;
1.228 + matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
1.229 + while (matchIndex < charClass->m_matches.size())
1.230 + matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
1.231 +
1.232 + failures.link(this);
1.233 + } else if (charClass->m_matches.size()) {
1.234 + // optimization: gather 'a','A' etc back together, can mask & test once.
1.235 + Vector<char> matchesAZaz;
1.236 +
1.237 + for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {
1.238 + char ch = charClass->m_matches[i];
1.239 + if (m_pattern.m_ignoreCase) {
1.240 + if (isASCIILower(ch)) {
1.241 + matchesAZaz.append(ch);
1.242 + continue;
1.243 + }
1.244 + if (isASCIIUpper(ch))
1.245 + continue;
1.246 + }
1.247 + matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
1.248 + }
1.249 +
1.250 + if (unsigned countAZaz = matchesAZaz.size()) {
1.251 + or32(TrustedImm32(32), character);
1.252 + for (unsigned i = 0; i < countAZaz; ++i)
1.253 + matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));
1.254 + }
1.255 + }
1.256 +
1.257 + if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())
1.258 + unicodeFail.link(this);
1.259 + }
1.260 +
1.261 + // Jumps if input not available; will have (incorrectly) incremented already!
1.262 + Jump jumpIfNoAvailableInput(unsigned countToCheck = 0)
1.263 + {
1.264 + if (countToCheck)
1.265 + add32(Imm32(countToCheck), index);
1.266 + return branch32(Above, index, length);
1.267 + }
1.268 +
1.269 + Jump jumpIfAvailableInput(unsigned countToCheck)
1.270 + {
1.271 + add32(Imm32(countToCheck), index);
1.272 + return branch32(BelowOrEqual, index, length);
1.273 + }
1.274 +
1.275 + Jump checkInput()
1.276 + {
1.277 + return branch32(BelowOrEqual, index, length);
1.278 + }
1.279 +
1.280 + Jump atEndOfInput()
1.281 + {
1.282 + return branch32(Equal, index, length);
1.283 + }
1.284 +
1.285 + Jump notAtEndOfInput()
1.286 + {
1.287 + return branch32(NotEqual, index, length);
1.288 + }
1.289 +
1.290 + Jump jumpIfCharNotEquals(UChar ch, int inputPosition, RegisterID character)
1.291 + {
1.292 + readCharacter(inputPosition, character);
1.293 +
1.294 + // For case-insesitive compares, non-ascii characters that have different
1.295 + // upper & lower case representations are converted to a character class.
1.296 + ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));
1.297 + if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1.298 + or32(TrustedImm32(0x20), character);
1.299 + ch |= 0x20;
1.300 + }
1.301 +
1.302 + return branch32(NotEqual, character, Imm32(ch));
1.303 + }
1.304 +
1.305 + void readCharacter(int inputPosition, RegisterID reg)
1.306 + {
1.307 + if (m_charSize == Char8)
1.308 + load8(BaseIndex(input, index, TimesOne, inputPosition * sizeof(char)), reg);
1.309 + else
1.310 + load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
1.311 + }
1.312 +
1.313 + void storeToFrame(RegisterID reg, unsigned frameLocation)
1.314 + {
1.315 + poke(reg, frameLocation);
1.316 + }
1.317 +
1.318 + void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
1.319 + {
1.320 + poke(imm, frameLocation);
1.321 + }
1.322 +
1.323 + DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
1.324 + {
1.325 + return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
1.326 + }
1.327 +
1.328 + void loadFromFrame(unsigned frameLocation, RegisterID reg)
1.329 + {
1.330 + peek(reg, frameLocation);
1.331 + }
1.332 +
1.333 + void loadFromFrameAndJump(unsigned frameLocation)
1.334 + {
1.335 + jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
1.336 + }
1.337 +
1.338 + void initCallFrame()
1.339 + {
1.340 + unsigned callFrameSize = m_pattern.m_body->m_callFrameSize;
1.341 + if (callFrameSize)
1.342 + subPtr(Imm32(callFrameSize * sizeof(void*)), stackPointerRegister);
1.343 + }
1.344 + void removeCallFrame()
1.345 + {
1.346 + unsigned callFrameSize = m_pattern.m_body->m_callFrameSize;
1.347 + if (callFrameSize)
1.348 + addPtr(Imm32(callFrameSize * sizeof(void*)), stackPointerRegister);
1.349 + }
1.350 +
1.351 + // Used to record subpatters, should only be called if compileMode is IncludeSubpatterns.
1.352 + void setSubpatternStart(RegisterID reg, unsigned subpattern)
1.353 + {
1.354 + ASSERT(subpattern);
1.355 + // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
1.356 + store32(reg, Address(output, (subpattern << 1) * sizeof(int)));
1.357 + }
1.358 + void setSubpatternEnd(RegisterID reg, unsigned subpattern)
1.359 + {
1.360 + ASSERT(subpattern);
1.361 + // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
1.362 + store32(reg, Address(output, ((subpattern << 1) + 1) * sizeof(int)));
1.363 + }
1.364 + void clearSubpatternStart(unsigned subpattern)
1.365 + {
1.366 + ASSERT(subpattern);
1.367 + // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
1.368 + store32(TrustedImm32(-1), Address(output, (subpattern << 1) * sizeof(int)));
1.369 + }
1.370 +
1.371 + // We use one of three different strategies to track the start of the current match,
1.372 + // while matching.
1.373 + // 1) If the pattern has a fixed size, do nothing! - we calculate the value lazily
1.374 + // at the end of matching. This is irrespective of compileMode, and in this case
1.375 + // these methods should never be called.
1.376 + // 2) If we're compiling IncludeSubpatterns, 'output' contains a pointer to an output
1.377 + // vector, store the match start in the output vector.
1.378 + // 3) If we're compiling MatchOnly, 'output' is unused, store the match start directly
1.379 + // in this register.
1.380 + void setMatchStart(RegisterID reg)
1.381 + {
1.382 + ASSERT(!m_pattern.m_body->m_hasFixedSize);
1.383 + if (compileMode == IncludeSubpatterns)
1.384 + store32(reg, output);
1.385 + else
1.386 + move(reg, output);
1.387 + }
1.388 + void getMatchStart(RegisterID reg)
1.389 + {
1.390 + ASSERT(!m_pattern.m_body->m_hasFixedSize);
1.391 + if (compileMode == IncludeSubpatterns)
1.392 + load32(output, reg);
1.393 + else
1.394 + move(output, reg);
1.395 + }
1.396 +
1.397 + enum YarrOpCode {
1.398 + // These nodes wrap body alternatives - those in the main disjunction,
1.399 + // rather than subpatterns or assertions. These are chained together in
1.400 + // a doubly linked list, with a 'begin' node for the first alternative,
1.401 + // a 'next' node for each subsequent alternative, and an 'end' node at
1.402 + // the end. In the case of repeating alternatives, the 'end' node also
1.403 + // has a reference back to 'begin'.
1.404 + OpBodyAlternativeBegin,
1.405 + OpBodyAlternativeNext,
1.406 + OpBodyAlternativeEnd,
1.407 + // Similar to the body alternatives, but used for subpatterns with two
1.408 + // or more alternatives.
1.409 + OpNestedAlternativeBegin,
1.410 + OpNestedAlternativeNext,
1.411 + OpNestedAlternativeEnd,
1.412 + // Used for alternatives in subpatterns where there is only a single
1.413 + // alternative (backtrackingis easier in these cases), or for alternatives
1.414 + // which never need to be backtracked (those in parenthetical assertions,
1.415 + // terminal subpatterns).
1.416 + OpSimpleNestedAlternativeBegin,
1.417 + OpSimpleNestedAlternativeNext,
1.418 + OpSimpleNestedAlternativeEnd,
1.419 + // Used to wrap 'Once' subpattern matches (quantityCount == 1).
1.420 + OpParenthesesSubpatternOnceBegin,
1.421 + OpParenthesesSubpatternOnceEnd,
1.422 + // Used to wrap 'Terminal' subpattern matches (at the end of the regexp).
1.423 + OpParenthesesSubpatternTerminalBegin,
1.424 + OpParenthesesSubpatternTerminalEnd,
1.425 + // Used to wrap parenthetical assertions.
1.426 + OpParentheticalAssertionBegin,
1.427 + OpParentheticalAssertionEnd,
1.428 + // Wraps all simple terms (pattern characters, character classes).
1.429 + OpTerm,
1.430 + // Where an expression contains only 'once through' body alternatives
1.431 + // and no repeating ones, this op is used to return match failure.
1.432 + OpMatchFailed
1.433 + };
1.434 +
1.435 + // This structure is used to hold the compiled opcode information,
1.436 + // including reference back to the original PatternTerm/PatternAlternatives,
1.437 + // and JIT compilation data structures.
1.438 + struct YarrOp {
1.439 + explicit YarrOp(PatternTerm* term)
1.440 + : m_op(OpTerm)
1.441 + , m_term(term)
1.442 + , m_isDeadCode(false)
1.443 + {
1.444 + }
1.445 +
1.446 + explicit YarrOp(YarrOpCode op)
1.447 + : m_op(op)
1.448 + , m_isDeadCode(false)
1.449 + {
1.450 + }
1.451 +
1.452 + // The operation, as a YarrOpCode, and also a reference to the PatternTerm.
1.453 + YarrOpCode m_op;
1.454 + PatternTerm* m_term;
1.455 +
1.456 + // For alternatives, this holds the PatternAlternative and doubly linked
1.457 + // references to this alternative's siblings. In the case of the
1.458 + // OpBodyAlternativeEnd node at the end of a section of repeating nodes,
1.459 + // m_nextOp will reference the OpBodyAlternativeBegin node of the first
1.460 + // repeating alternative.
1.461 + PatternAlternative* m_alternative;
1.462 + size_t m_previousOp;
1.463 + size_t m_nextOp;
1.464 +
1.465 + // Used to record a set of Jumps out of the generated code, typically
1.466 + // used for jumps out to backtracking code, and a single reentry back
1.467 + // into the code for a node (likely where a backtrack will trigger
1.468 + // rematching).
1.469 + Label m_reentry;
1.470 + JumpList m_jumps;
1.471 +
1.472 + // Used for backtracking when the prior alternative did not consume any
1.473 + // characters but matched.
1.474 + Jump m_zeroLengthMatch;
1.475 +
1.476 + // This flag is used to null out the second pattern character, when
1.477 + // two are fused to match a pair together.
1.478 + bool m_isDeadCode;
1.479 +
1.480 + // Currently used in the case of some of the more complex management of
1.481 + // 'm_checked', to cache the offset used in this alternative, to avoid
1.482 + // recalculating it.
1.483 + int m_checkAdjust;
1.484 +
1.485 + // Used by OpNestedAlternativeNext/End to hold the pointer to the
1.486 + // value that will be pushed into the pattern's frame to return to,
1.487 + // upon backtracking back into the disjunction.
1.488 + DataLabelPtr m_returnAddress;
1.489 + };
1.490 +
1.491 + // BacktrackingState
1.492 + // This class encapsulates information about the state of code generation
1.493 + // whilst generating the code for backtracking, when a term fails to match.
1.494 + // Upon entry to code generation of the backtracking code for a given node,
1.495 + // the Backtracking state will hold references to all control flow sources
1.496 + // that are outputs in need of further backtracking from the prior node
1.497 + // generated (which is the subsequent operation in the regular expression,
1.498 + // and in the m_ops Vector, since we generated backtracking backwards).
1.499 + // These references to control flow take the form of:
1.500 + // - A jump list of jumps, to be linked to code that will backtrack them
1.501 + // further.
1.502 + // - A set of DataLabelPtr values, to be populated with values to be
1.503 + // treated effectively as return addresses backtracking into complex
1.504 + // subpatterns.
1.505 + // - A flag indicating that the current sequence of generated code up to
1.506 + // this point requires backtracking.
1.507 + class BacktrackingState {
1.508 + public:
1.509 + BacktrackingState()
1.510 + : m_pendingFallthrough(false)
1.511 + {
1.512 + }
1.513 +
1.514 + // Add a jump or jumps, a return address, or set the flag indicating
1.515 + // that the current 'fallthrough' control flow requires backtracking.
1.516 + void append(const Jump& jump)
1.517 + {
1.518 + m_laterFailures.append(jump);
1.519 + }
1.520 + void append(JumpList& jumpList)
1.521 + {
1.522 + m_laterFailures.append(jumpList);
1.523 + }
1.524 + void append(const DataLabelPtr& returnAddress)
1.525 + {
1.526 + m_pendingReturns.append(returnAddress);
1.527 + }
1.528 + void fallthrough()
1.529 + {
1.530 + ASSERT(!m_pendingFallthrough);
1.531 + m_pendingFallthrough = true;
1.532 + }
1.533 +
1.534 + // These methods clear the backtracking state, either linking to the
1.535 + // current location, a provided label, or copying the backtracking out
1.536 + // to a JumpList. All actions may require code generation to take place,
1.537 + // and as such are passed a pointer to the assembler.
1.538 + void link(MacroAssembler* assembler)
1.539 + {
1.540 + if (m_pendingReturns.size()) {
1.541 + Label here(assembler);
1.542 + for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
1.543 + m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));
1.544 + m_pendingReturns.clear();
1.545 + }
1.546 + m_laterFailures.link(assembler);
1.547 + m_laterFailures.clear();
1.548 + m_pendingFallthrough = false;
1.549 + }
1.550 + void linkTo(Label label, MacroAssembler* assembler)
1.551 + {
1.552 + if (m_pendingReturns.size()) {
1.553 + for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
1.554 + m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], label));
1.555 + m_pendingReturns.clear();
1.556 + }
1.557 + if (m_pendingFallthrough)
1.558 + assembler->jump(label);
1.559 + m_laterFailures.linkTo(label, assembler);
1.560 + m_laterFailures.clear();
1.561 + m_pendingFallthrough = false;
1.562 + }
1.563 + void takeBacktracksToJumpList(JumpList& jumpList, MacroAssembler* assembler)
1.564 + {
1.565 + if (m_pendingReturns.size()) {
1.566 + Label here(assembler);
1.567 + for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
1.568 + m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));
1.569 + m_pendingReturns.clear();
1.570 + m_pendingFallthrough = true;
1.571 + }
1.572 + if (m_pendingFallthrough)
1.573 + jumpList.append(assembler->jump());
1.574 + jumpList.append(m_laterFailures);
1.575 + m_laterFailures.clear();
1.576 + m_pendingFallthrough = false;
1.577 + }
1.578 +
1.579 + bool isEmpty()
1.580 + {
1.581 + return m_laterFailures.empty() && m_pendingReturns.isEmpty() && !m_pendingFallthrough;
1.582 + }
1.583 +
1.584 + // Called at the end of code generation to link all return addresses.
1.585 + void linkDataLabels(LinkBuffer& linkBuffer)
1.586 + {
1.587 + ASSERT(isEmpty());
1.588 + for (unsigned i = 0; i < m_backtrackRecords.size(); ++i)
1.589 + linkBuffer.patch(m_backtrackRecords[i].m_dataLabel, linkBuffer.locationOf(m_backtrackRecords[i].m_backtrackLocation));
1.590 + }
1.591 +
1.592 + private:
1.593 + struct ReturnAddressRecord {
1.594 + ReturnAddressRecord(DataLabelPtr dataLabel, Label backtrackLocation)
1.595 + : m_dataLabel(dataLabel)
1.596 + , m_backtrackLocation(backtrackLocation)
1.597 + {
1.598 + }
1.599 +
1.600 + DataLabelPtr m_dataLabel;
1.601 + Label m_backtrackLocation;
1.602 + };
1.603 +
1.604 + JumpList m_laterFailures;
1.605 + bool m_pendingFallthrough;
1.606 + Vector<DataLabelPtr, 4> m_pendingReturns;
1.607 + Vector<ReturnAddressRecord, 4> m_backtrackRecords;
1.608 + };
1.609 +
1.610 + // Generation methods:
1.611 + // ===================
1.612 +
1.613 + // This method provides a default implementation of backtracking common
1.614 + // to many terms; terms commonly jump out of the forwards matching path
1.615 + // on any failed conditions, and add these jumps to the m_jumps list. If
1.616 + // no special handling is required we can often just backtrack to m_jumps.
1.617 + bool backtrackTermDefault(size_t opIndex)
1.618 + {
1.619 + YarrOp& op = m_ops[opIndex];
1.620 + m_backtrackingState.append(op.m_jumps);
1.621 + return true;
1.622 + }
1.623 +
1.624 + bool generateAssertionBOL(size_t opIndex)
1.625 + {
1.626 + YarrOp& op = m_ops[opIndex];
1.627 + PatternTerm* term = op.m_term;
1.628 +
1.629 + if (m_pattern.m_multiline) {
1.630 + const RegisterID character = regT0;
1.631 +
1.632 + JumpList matchDest;
1.633 + if (!term->inputPosition)
1.634 + matchDest.append(branch32(Equal, index, Imm32(m_checked)));
1.635 +
1.636 + readCharacter((term->inputPosition - m_checked) - 1, character);
1.637 + matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1.638 + op.m_jumps.append(jump());
1.639 +
1.640 + matchDest.link(this);
1.641 + } else {
1.642 + // Erk, really should poison out these alternatives early. :-/
1.643 + if (term->inputPosition)
1.644 + op.m_jumps.append(jump());
1.645 + else
1.646 + op.m_jumps.append(branch32(NotEqual, index, Imm32(m_checked)));
1.647 + }
1.648 + return true;
1.649 + }
1.650 + bool backtrackAssertionBOL(size_t opIndex)
1.651 + {
1.652 + return backtrackTermDefault(opIndex);
1.653 + }
1.654 +
1.655 + bool generateAssertionEOL(size_t opIndex)
1.656 + {
1.657 + YarrOp& op = m_ops[opIndex];
1.658 + PatternTerm* term = op.m_term;
1.659 +
1.660 + if (m_pattern.m_multiline) {
1.661 + const RegisterID character = regT0;
1.662 +
1.663 + JumpList matchDest;
1.664 + if (term->inputPosition == m_checked)
1.665 + matchDest.append(atEndOfInput());
1.666 +
1.667 + readCharacter(term->inputPosition - m_checked, character);
1.668 + matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1.669 + op.m_jumps.append(jump());
1.670 +
1.671 + matchDest.link(this);
1.672 + } else {
1.673 + if (term->inputPosition == m_checked)
1.674 + op.m_jumps.append(notAtEndOfInput());
1.675 + // Erk, really should poison out these alternatives early. :-/
1.676 + else
1.677 + op.m_jumps.append(jump());
1.678 + }
1.679 + return true;
1.680 + }
1.681 + bool backtrackAssertionEOL(size_t opIndex)
1.682 + {
1.683 + return backtrackTermDefault(opIndex);
1.684 + }
1.685 +
1.686 + // Also falls though on nextIsNotWordChar.
1.687 + void matchAssertionWordchar(size_t opIndex, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
1.688 + {
1.689 + YarrOp& op = m_ops[opIndex];
1.690 + PatternTerm* term = op.m_term;
1.691 +
1.692 + const RegisterID character = regT0;
1.693 +
1.694 + if (term->inputPosition == m_checked)
1.695 + nextIsNotWordChar.append(atEndOfInput());
1.696 +
1.697 + readCharacter((term->inputPosition - m_checked), character);
1.698 + matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
1.699 + }
1.700 +
1.701 + bool generateAssertionWordBoundary(size_t opIndex)
1.702 + {
1.703 + YarrOp& op = m_ops[opIndex];
1.704 + PatternTerm* term = op.m_term;
1.705 +
1.706 + const RegisterID character = regT0;
1.707 +
1.708 + Jump atBegin;
1.709 + JumpList matchDest;
1.710 + if (!term->inputPosition)
1.711 + atBegin = branch32(Equal, index, Imm32(m_checked));
1.712 + readCharacter((term->inputPosition - m_checked) - 1, character);
1.713 + matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
1.714 + if (!term->inputPosition)
1.715 + atBegin.link(this);
1.716 +
1.717 + // We fall through to here if the last character was not a wordchar.
1.718 + JumpList nonWordCharThenWordChar;
1.719 + JumpList nonWordCharThenNonWordChar;
1.720 + if (term->invert()) {
1.721 + matchAssertionWordchar(opIndex, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
1.722 + nonWordCharThenWordChar.append(jump());
1.723 + } else {
1.724 + matchAssertionWordchar(opIndex, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
1.725 + nonWordCharThenNonWordChar.append(jump());
1.726 + }
1.727 + op.m_jumps.append(nonWordCharThenNonWordChar);
1.728 +
1.729 + // We jump here if the last character was a wordchar.
1.730 + matchDest.link(this);
1.731 + JumpList wordCharThenWordChar;
1.732 + JumpList wordCharThenNonWordChar;
1.733 + if (term->invert()) {
1.734 + matchAssertionWordchar(opIndex, wordCharThenNonWordChar, wordCharThenWordChar);
1.735 + wordCharThenWordChar.append(jump());
1.736 + } else {
1.737 + matchAssertionWordchar(opIndex, wordCharThenWordChar, wordCharThenNonWordChar);
1.738 + // This can fall-though!
1.739 + }
1.740 +
1.741 + op.m_jumps.append(wordCharThenWordChar);
1.742 +
1.743 + nonWordCharThenWordChar.link(this);
1.744 + wordCharThenNonWordChar.link(this);
1.745 + return true;
1.746 + }
1.747 + bool backtrackAssertionWordBoundary(size_t opIndex)
1.748 + {
1.749 + return backtrackTermDefault(opIndex);
1.750 + }
1.751 +
1.752 + bool generatePatternCharacterOnce(size_t opIndex)
1.753 + {
1.754 + YarrOp& op = m_ops[opIndex];
1.755 +
1.756 + if (op.m_isDeadCode)
1.757 + return true;
1.758 +
1.759 + // m_ops always ends with a OpBodyAlternativeEnd or OpMatchFailed
1.760 + // node, so there must always be at least one more node.
1.761 + ASSERT(opIndex + 1 < m_ops.size());
1.762 + YarrOp* nextOp = &m_ops[opIndex + 1];
1.763 +
1.764 + PatternTerm* term = op.m_term;
1.765 + UChar ch = term->patternCharacter;
1.766 +
1.767 + if ((ch > 0xff) && (m_charSize == Char8)) {
1.768 + // Have a 16 bit pattern character and an 8 bit string - short circuit
1.769 + op.m_jumps.append(jump());
1.770 + return true;
1.771 + }
1.772 +
1.773 + const RegisterID character = regT0;
1.774 + int maxCharactersAtOnce = m_charSize == Char8 ? 4 : 2;
1.775 + unsigned ignoreCaseMask = 0;
1.776 +#if CPU(BIG_ENDIAN)
1.777 + int allCharacters = ch << (m_charSize == Char8 ? 24 : 16);
1.778 +#else
1.779 + int allCharacters = ch;
1.780 +#endif
1.781 + int numberCharacters;
1.782 + int startTermPosition = term->inputPosition;
1.783 +
1.784 + // For case-insesitive compares, non-ascii characters that have different
1.785 + // upper & lower case representations are converted to a character class.
1.786 + ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));
1.787 +
1.788 + if (m_pattern.m_ignoreCase && isASCIIAlpha(ch))
1.789 +#if CPU(BIG_ENDIAN)
1.790 + ignoreCaseMask |= 32 << (m_charSize == Char8 ? 24 : 16);
1.791 +#else
1.792 + ignoreCaseMask |= 32;
1.793 +#endif
1.794 +
1.795 + for (numberCharacters = 1; numberCharacters < maxCharactersAtOnce && nextOp->m_op == OpTerm; ++numberCharacters, nextOp = &m_ops[opIndex + numberCharacters]) {
1.796 + PatternTerm* nextTerm = nextOp->m_term;
1.797 +
1.798 + if (nextTerm->type != PatternTerm::TypePatternCharacter
1.799 + || nextTerm->quantityType != QuantifierFixedCount
1.800 + || nextTerm->quantityCount != 1
1.801 + || nextTerm->inputPosition != (startTermPosition + numberCharacters))
1.802 + break;
1.803 +
1.804 + nextOp->m_isDeadCode = true;
1.805 +
1.806 +#if CPU(BIG_ENDIAN)
1.807 + int shiftAmount = (m_charSize == Char8 ? 24 : 16) - ((m_charSize == Char8 ? 8 : 16) * numberCharacters);
1.808 +#else
1.809 + int shiftAmount = (m_charSize == Char8 ? 8 : 16) * numberCharacters;
1.810 +#endif
1.811 +
1.812 + UChar currentCharacter = nextTerm->patternCharacter;
1.813 +
1.814 + if ((currentCharacter > 0xff) && (m_charSize == Char8)) {
1.815 + // Have a 16 bit pattern character and an 8 bit string - short circuit
1.816 + op.m_jumps.append(jump());
1.817 + return true;
1.818 + }
1.819 +
1.820 + // For case-insesitive compares, non-ascii characters that have different
1.821 + // upper & lower case representations are converted to a character class.
1.822 + ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(currentCharacter) || isCanonicallyUnique(currentCharacter));
1.823 +
1.824 + allCharacters |= (currentCharacter << shiftAmount);
1.825 +
1.826 + if ((m_pattern.m_ignoreCase) && (isASCIIAlpha(currentCharacter)))
1.827 + ignoreCaseMask |= 32 << shiftAmount;
1.828 + }
1.829 +
1.830 + if (m_charSize == Char8) {
1.831 + switch (numberCharacters) {
1.832 + case 1:
1.833 + op.m_jumps.append(jumpIfCharNotEquals(ch, startTermPosition - m_checked, character));
1.834 + return true;
1.835 + case 2: {
1.836 + BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
1.837 + load16Unaligned(address, character);
1.838 + break;
1.839 + }
1.840 + case 3: {
1.841 + BaseIndex highAddress(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
1.842 + load16Unaligned(highAddress, character);
1.843 + if (ignoreCaseMask)
1.844 + or32(Imm32(ignoreCaseMask), character);
1.845 + op.m_jumps.append(branch32(NotEqual, character, Imm32((allCharacters & 0xffff) | ignoreCaseMask)));
1.846 + op.m_jumps.append(jumpIfCharNotEquals(allCharacters >> 16, startTermPosition + 2 - m_checked, character));
1.847 + return true;
1.848 + }
1.849 + case 4: {
1.850 + BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
1.851 + load32WithUnalignedHalfWords(address, character);
1.852 + break;
1.853 + }
1.854 + }
1.855 + } else {
1.856 + switch (numberCharacters) {
1.857 + case 1:
1.858 + op.m_jumps.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
1.859 + return true;
1.860 + case 2:
1.861 + BaseIndex address(input, index, TimesTwo, (term->inputPosition - m_checked) * sizeof(UChar));
1.862 + load32WithUnalignedHalfWords(address, character);
1.863 + break;
1.864 + }
1.865 + }
1.866 +
1.867 + if (ignoreCaseMask)
1.868 + or32(Imm32(ignoreCaseMask), character);
1.869 + op.m_jumps.append(branch32(NotEqual, character, Imm32(allCharacters | ignoreCaseMask)));
1.870 + return true;
1.871 + }
1.872 + bool backtrackPatternCharacterOnce(size_t opIndex)
1.873 + {
1.874 + return backtrackTermDefault(opIndex);
1.875 + }
1.876 +
1.877 + bool generatePatternCharacterFixed(size_t opIndex)
1.878 + {
1.879 + YarrOp& op = m_ops[opIndex];
1.880 + PatternTerm* term = op.m_term;
1.881 + UChar ch = term->patternCharacter;
1.882 +
1.883 + const RegisterID character = regT0;
1.884 + const RegisterID countRegister = regT1;
1.885 +
1.886 + move(index, countRegister);
1.887 + if (term->quantityCount.hasOverflowed())
1.888 + return false;
1.889 + sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);
1.890 +
1.891 + Label loop(this);
1.892 + int offset;
1.893 + if ((Checked<int>(term->inputPosition - m_checked + Checked<int64_t>(term->quantityCount)) * static_cast<int>(m_charSize == Char8 ? sizeof(char) : sizeof(UChar))).safeGet(offset))
1.894 + return false;
1.895 + BaseIndex address(input, countRegister, m_charScale, offset);
1.896 +
1.897 + if (m_charSize == Char8)
1.898 + load8(address, character);
1.899 + else
1.900 + load16(address, character);
1.901 +
1.902 + // For case-insesitive compares, non-ascii characters that have different
1.903 + // upper & lower case representations are converted to a character class.
1.904 + ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));
1.905 + if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
1.906 + or32(TrustedImm32(0x20), character);
1.907 + ch |= 0x20;
1.908 + }
1.909 +
1.910 + op.m_jumps.append(branch32(NotEqual, character, Imm32(ch)));
1.911 + add32(TrustedImm32(1), countRegister);
1.912 + branch32(NotEqual, countRegister, index).linkTo(loop, this);
1.913 +
1.914 + return true;
1.915 + }
1.916 + bool backtrackPatternCharacterFixed(size_t opIndex)
1.917 + {
1.918 + return backtrackTermDefault(opIndex);
1.919 + }
1.920 +
1.921 + bool generatePatternCharacterGreedy(size_t opIndex)
1.922 + {
1.923 + YarrOp& op = m_ops[opIndex];
1.924 + PatternTerm* term = op.m_term;
1.925 + UChar ch = term->patternCharacter;
1.926 +
1.927 + const RegisterID character = regT0;
1.928 + const RegisterID countRegister = regT1;
1.929 +
1.930 + move(TrustedImm32(0), countRegister);
1.931 +
1.932 + // Unless have a 16 bit pattern character and an 8 bit string - short circuit
1.933 + if (!((ch > 0xff) && (m_charSize == Char8))) {
1.934 + JumpList failures;
1.935 + Label loop(this);
1.936 + failures.append(atEndOfInput());
1.937 + failures.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
1.938 +
1.939 + add32(TrustedImm32(1), countRegister);
1.940 + add32(TrustedImm32(1), index);
1.941 + if (term->quantityCount == quantifyInfinite) {
1.942 + jump(loop);
1.943 + } else {
1.944 + if (term->quantityCount.hasOverflowed())
1.945 + return false;
1.946 + branch32(NotEqual, countRegister, Imm32(term->quantityCount.unsafeGet())).linkTo(loop, this);
1.947 + }
1.948 +
1.949 + failures.link(this);
1.950 + }
1.951 + op.m_reentry = label();
1.952 +
1.953 + storeToFrame(countRegister, term->frameLocation);
1.954 + return true;
1.955 + }
1.956 + bool backtrackPatternCharacterGreedy(size_t opIndex)
1.957 + {
1.958 + YarrOp& op = m_ops[opIndex];
1.959 + PatternTerm* term = op.m_term;
1.960 +
1.961 + const RegisterID countRegister = regT1;
1.962 +
1.963 + m_backtrackingState.link(this);
1.964 +
1.965 + loadFromFrame(term->frameLocation, countRegister);
1.966 + m_backtrackingState.append(branchTest32(Zero, countRegister));
1.967 + sub32(TrustedImm32(1), countRegister);
1.968 + sub32(TrustedImm32(1), index);
1.969 + jump(op.m_reentry);
1.970 +
1.971 + return true;
1.972 + }
1.973 +
1.974 + bool generatePatternCharacterNonGreedy(size_t opIndex)
1.975 + {
1.976 + YarrOp& op = m_ops[opIndex];
1.977 + PatternTerm* term = op.m_term;
1.978 +
1.979 + const RegisterID countRegister = regT1;
1.980 +
1.981 + move(TrustedImm32(0), countRegister);
1.982 + op.m_reentry = label();
1.983 + storeToFrame(countRegister, term->frameLocation);
1.984 + return true;
1.985 + }
1.986 + bool backtrackPatternCharacterNonGreedy(size_t opIndex)
1.987 + {
1.988 + YarrOp& op = m_ops[opIndex];
1.989 + PatternTerm* term = op.m_term;
1.990 + UChar ch = term->patternCharacter;
1.991 +
1.992 + const RegisterID character = regT0;
1.993 + const RegisterID countRegister = regT1;
1.994 +
1.995 + m_backtrackingState.link(this);
1.996 +
1.997 + loadFromFrame(term->frameLocation, countRegister);
1.998 +
1.999 + // Unless have a 16 bit pattern character and an 8 bit string - short circuit
1.1000 + if (!((ch > 0xff) && (m_charSize == Char8))) {
1.1001 + JumpList nonGreedyFailures;
1.1002 + nonGreedyFailures.append(atEndOfInput());
1.1003 + if (term->quantityCount != quantifyInfinite) {
1.1004 + if (term->quantityCount.hasOverflowed())
1.1005 + return false;
1.1006 + nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));
1.1007 + }
1.1008 + nonGreedyFailures.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
1.1009 +
1.1010 + add32(TrustedImm32(1), countRegister);
1.1011 + add32(TrustedImm32(1), index);
1.1012 +
1.1013 + jump(op.m_reentry);
1.1014 + nonGreedyFailures.link(this);
1.1015 + }
1.1016 +
1.1017 + sub32(countRegister, index);
1.1018 + m_backtrackingState.fallthrough();
1.1019 +
1.1020 + return true;
1.1021 + }
1.1022 +
1.1023 + bool generateCharacterClassOnce(size_t opIndex)
1.1024 + {
1.1025 + YarrOp& op = m_ops[opIndex];
1.1026 + PatternTerm* term = op.m_term;
1.1027 +
1.1028 + const RegisterID character = regT0;
1.1029 +
1.1030 + JumpList matchDest;
1.1031 + readCharacter(term->inputPosition - m_checked, character);
1.1032 + matchCharacterClass(character, matchDest, term->characterClass);
1.1033 +
1.1034 + if (term->invert())
1.1035 + op.m_jumps.append(matchDest);
1.1036 + else {
1.1037 + op.m_jumps.append(jump());
1.1038 + matchDest.link(this);
1.1039 + }
1.1040 + return true;
1.1041 + }
1.1042 + bool backtrackCharacterClassOnce(size_t opIndex)
1.1043 + {
1.1044 + return backtrackTermDefault(opIndex);
1.1045 + }
1.1046 +
1.1047 + bool generateCharacterClassFixed(size_t opIndex)
1.1048 + {
1.1049 + YarrOp& op = m_ops[opIndex];
1.1050 + PatternTerm* term = op.m_term;
1.1051 +
1.1052 + const RegisterID character = regT0;
1.1053 + const RegisterID countRegister = regT1;
1.1054 +
1.1055 + move(index, countRegister);
1.1056 + if (term->quantityCount.hasOverflowed())
1.1057 + return false;
1.1058 + sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);
1.1059 +
1.1060 + Label loop(this);
1.1061 + JumpList matchDest;
1.1062 +
1.1063 + int offset;
1.1064 + Checked<int64_t> checkedOffset(term->inputPosition - m_checked + Checked<int64_t>(term->quantityCount));
1.1065 +
1.1066 + if (m_charSize == Char8) {
1.1067 + if ((Checked<int>(checkedOffset) * static_cast<int>(sizeof(char))).safeGet(offset))
1.1068 + return false;
1.1069 + load8(BaseIndex(input, countRegister, TimesOne, offset), character);
1.1070 + } else {
1.1071 + if ((Checked<int>(checkedOffset) * static_cast<int>(sizeof(UChar))).safeGet(offset))
1.1072 + return false;
1.1073 + load16(BaseIndex(input, countRegister, TimesTwo, offset), character);
1.1074 + }
1.1075 + matchCharacterClass(character, matchDest, term->characterClass);
1.1076 +
1.1077 + if (term->invert())
1.1078 + op.m_jumps.append(matchDest);
1.1079 + else {
1.1080 + op.m_jumps.append(jump());
1.1081 + matchDest.link(this);
1.1082 + }
1.1083 +
1.1084 + add32(TrustedImm32(1), countRegister);
1.1085 + branch32(NotEqual, countRegister, index).linkTo(loop, this);
1.1086 + return true;
1.1087 + }
1.1088 + bool backtrackCharacterClassFixed(size_t opIndex)
1.1089 + {
1.1090 + return backtrackTermDefault(opIndex);
1.1091 + }
1.1092 +
1.1093 + bool generateCharacterClassGreedy(size_t opIndex)
1.1094 + {
1.1095 + YarrOp& op = m_ops[opIndex];
1.1096 + PatternTerm* term = op.m_term;
1.1097 +
1.1098 + const RegisterID character = regT0;
1.1099 + const RegisterID countRegister = regT1;
1.1100 +
1.1101 + move(TrustedImm32(0), countRegister);
1.1102 +
1.1103 + JumpList failures;
1.1104 + Label loop(this);
1.1105 + failures.append(atEndOfInput());
1.1106 +
1.1107 + if (term->invert()) {
1.1108 + readCharacter(term->inputPosition - m_checked, character);
1.1109 + matchCharacterClass(character, failures, term->characterClass);
1.1110 + } else {
1.1111 + JumpList matchDest;
1.1112 + readCharacter(term->inputPosition - m_checked, character);
1.1113 + matchCharacterClass(character, matchDest, term->characterClass);
1.1114 + failures.append(jump());
1.1115 + matchDest.link(this);
1.1116 + }
1.1117 +
1.1118 + add32(TrustedImm32(1), countRegister);
1.1119 + add32(TrustedImm32(1), index);
1.1120 + if (term->quantityCount != quantifyInfinite) {
1.1121 + unsigned quantityCount;
1.1122 + if (term->quantityCount.safeGet(quantityCount))
1.1123 + return false;
1.1124 + branch32(NotEqual, countRegister, Imm32(quantityCount)).linkTo(loop, this);
1.1125 + failures.append(jump());
1.1126 + } else
1.1127 + jump(loop);
1.1128 +
1.1129 + failures.link(this);
1.1130 + op.m_reentry = label();
1.1131 +
1.1132 + storeToFrame(countRegister, term->frameLocation);
1.1133 + return true;
1.1134 + }
1.1135 + bool backtrackCharacterClassGreedy(size_t opIndex)
1.1136 + {
1.1137 + YarrOp& op = m_ops[opIndex];
1.1138 + PatternTerm* term = op.m_term;
1.1139 +
1.1140 + const RegisterID countRegister = regT1;
1.1141 +
1.1142 + m_backtrackingState.link(this);
1.1143 +
1.1144 + loadFromFrame(term->frameLocation, countRegister);
1.1145 + m_backtrackingState.append(branchTest32(Zero, countRegister));
1.1146 + sub32(TrustedImm32(1), countRegister);
1.1147 + sub32(TrustedImm32(1), index);
1.1148 + jump(op.m_reentry);
1.1149 +
1.1150 + return true;
1.1151 + }
1.1152 +
1.1153 + bool generateCharacterClassNonGreedy(size_t opIndex)
1.1154 + {
1.1155 + YarrOp& op = m_ops[opIndex];
1.1156 + PatternTerm* term = op.m_term;
1.1157 +
1.1158 + const RegisterID countRegister = regT1;
1.1159 +
1.1160 + move(TrustedImm32(0), countRegister);
1.1161 + op.m_reentry = label();
1.1162 + storeToFrame(countRegister, term->frameLocation);
1.1163 + return true;
1.1164 + }
1.1165 + bool backtrackCharacterClassNonGreedy(size_t opIndex)
1.1166 + {
1.1167 + YarrOp& op = m_ops[opIndex];
1.1168 + PatternTerm* term = op.m_term;
1.1169 +
1.1170 + const RegisterID character = regT0;
1.1171 + const RegisterID countRegister = regT1;
1.1172 +
1.1173 + JumpList nonGreedyFailures;
1.1174 +
1.1175 + m_backtrackingState.link(this);
1.1176 +
1.1177 + loadFromFrame(term->frameLocation, countRegister);
1.1178 +
1.1179 + nonGreedyFailures.append(atEndOfInput());
1.1180 + if (term->quantityCount.hasOverflowed())
1.1181 + return false;
1.1182 + nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));
1.1183 +
1.1184 + JumpList matchDest;
1.1185 + readCharacter(term->inputPosition - m_checked, character);
1.1186 + matchCharacterClass(character, matchDest, term->characterClass);
1.1187 +
1.1188 + if (term->invert())
1.1189 + nonGreedyFailures.append(matchDest);
1.1190 + else {
1.1191 + nonGreedyFailures.append(jump());
1.1192 + matchDest.link(this);
1.1193 + }
1.1194 +
1.1195 + add32(TrustedImm32(1), countRegister);
1.1196 + add32(TrustedImm32(1), index);
1.1197 +
1.1198 + jump(op.m_reentry);
1.1199 +
1.1200 + nonGreedyFailures.link(this);
1.1201 + sub32(countRegister, index);
1.1202 + m_backtrackingState.fallthrough();
1.1203 +
1.1204 + return true;
1.1205 + }
1.1206 +
1.1207 + bool generateDotStarEnclosure(size_t opIndex)
1.1208 + {
1.1209 + YarrOp& op = m_ops[opIndex];
1.1210 + PatternTerm* term = op.m_term;
1.1211 +
1.1212 + const RegisterID character = regT0;
1.1213 + const RegisterID matchPos = regT1;
1.1214 +
1.1215 + JumpList foundBeginningNewLine;
1.1216 + JumpList saveStartIndex;
1.1217 + JumpList foundEndingNewLine;
1.1218 +
1.1219 + ASSERT(!m_pattern.m_body->m_hasFixedSize);
1.1220 + getMatchStart(matchPos);
1.1221 +
1.1222 + saveStartIndex.append(branchTest32(Zero, matchPos));
1.1223 + Label findBOLLoop(this);
1.1224 + sub32(TrustedImm32(1), matchPos);
1.1225 + if (m_charSize == Char8)
1.1226 + load8(BaseIndex(input, matchPos, TimesOne, 0), character);
1.1227 + else
1.1228 + load16(BaseIndex(input, matchPos, TimesTwo, 0), character);
1.1229 + matchCharacterClass(character, foundBeginningNewLine, m_pattern.newlineCharacterClass());
1.1230 + branchTest32(NonZero, matchPos).linkTo(findBOLLoop, this);
1.1231 + saveStartIndex.append(jump());
1.1232 +
1.1233 + foundBeginningNewLine.link(this);
1.1234 + add32(TrustedImm32(1), matchPos); // Advance past newline
1.1235 + saveStartIndex.link(this);
1.1236 +
1.1237 + if (!m_pattern.m_multiline && term->anchors.bolAnchor)
1.1238 + op.m_jumps.append(branchTest32(NonZero, matchPos));
1.1239 +
1.1240 + ASSERT(!m_pattern.m_body->m_hasFixedSize);
1.1241 + setMatchStart(matchPos);
1.1242 +
1.1243 + move(index, matchPos);
1.1244 +
1.1245 + Label findEOLLoop(this);
1.1246 + foundEndingNewLine.append(branch32(Equal, matchPos, length));
1.1247 + if (m_charSize == Char8)
1.1248 + load8(BaseIndex(input, matchPos, TimesOne, 0), character);
1.1249 + else
1.1250 + load16(BaseIndex(input, matchPos, TimesTwo, 0), character);
1.1251 + matchCharacterClass(character, foundEndingNewLine, m_pattern.newlineCharacterClass());
1.1252 + add32(TrustedImm32(1), matchPos);
1.1253 + jump(findEOLLoop);
1.1254 +
1.1255 + foundEndingNewLine.link(this);
1.1256 +
1.1257 + if (!m_pattern.m_multiline && term->anchors.eolAnchor)
1.1258 + op.m_jumps.append(branch32(NotEqual, matchPos, length));
1.1259 +
1.1260 + move(matchPos, index);
1.1261 + return true;
1.1262 + }
1.1263 +
1.1264 + bool backtrackDotStarEnclosure(size_t opIndex)
1.1265 + {
1.1266 + return backtrackTermDefault(opIndex);
1.1267 + }
1.1268 +
1.1269 + // Code generation/backtracking for simple terms
1.1270 + // (pattern characters, character classes, and assertions).
1.1271 + // These methods farm out work to the set of functions above.
1.1272 + bool generateTerm(size_t opIndex)
1.1273 + {
1.1274 + YarrOp& op = m_ops[opIndex];
1.1275 + PatternTerm* term = op.m_term;
1.1276 +
1.1277 + switch (term->type) {
1.1278 + case PatternTerm::TypePatternCharacter:
1.1279 + switch (term->quantityType) {
1.1280 + case QuantifierFixedCount:
1.1281 + if (term->quantityCount == 1)
1.1282 + return generatePatternCharacterOnce(opIndex);
1.1283 + else
1.1284 + return generatePatternCharacterFixed(opIndex);
1.1285 + break;
1.1286 + case QuantifierGreedy:
1.1287 + return generatePatternCharacterGreedy(opIndex);
1.1288 + case QuantifierNonGreedy:
1.1289 + return generatePatternCharacterNonGreedy(opIndex);
1.1290 + }
1.1291 + break;
1.1292 +
1.1293 + case PatternTerm::TypeCharacterClass:
1.1294 + switch (term->quantityType) {
1.1295 + case QuantifierFixedCount:
1.1296 + if (term->quantityCount == 1)
1.1297 + return generateCharacterClassOnce(opIndex);
1.1298 + else
1.1299 + return generateCharacterClassFixed(opIndex);
1.1300 + break;
1.1301 + case QuantifierGreedy:
1.1302 + return generateCharacterClassGreedy(opIndex);
1.1303 + case QuantifierNonGreedy:
1.1304 + return generateCharacterClassNonGreedy(opIndex);
1.1305 + }
1.1306 + break;
1.1307 +
1.1308 + case PatternTerm::TypeAssertionBOL:
1.1309 + return generateAssertionBOL(opIndex);
1.1310 +
1.1311 + case PatternTerm::TypeAssertionEOL:
1.1312 + return generateAssertionEOL(opIndex);
1.1313 +
1.1314 + case PatternTerm::TypeAssertionWordBoundary:
1.1315 + return generateAssertionWordBoundary(opIndex);
1.1316 +
1.1317 + case PatternTerm::TypeForwardReference:
1.1318 + return true;
1.1319 +
1.1320 + case PatternTerm::TypeParenthesesSubpattern:
1.1321 + case PatternTerm::TypeParentheticalAssertion:
1.1322 + ASSERT_NOT_REACHED();
1.1323 + return false;
1.1324 + case PatternTerm::TypeBackReference:
1.1325 + return false;
1.1326 + case PatternTerm::TypeDotStarEnclosure:
1.1327 + return generateDotStarEnclosure(opIndex);
1.1328 + }
1.1329 +
1.1330 + return false;
1.1331 + }
1.1332 + bool backtrackTerm(size_t opIndex)
1.1333 + {
1.1334 + YarrOp& op = m_ops[opIndex];
1.1335 + PatternTerm* term = op.m_term;
1.1336 +
1.1337 + switch (term->type) {
1.1338 + case PatternTerm::TypePatternCharacter:
1.1339 + switch (term->quantityType) {
1.1340 + case QuantifierFixedCount:
1.1341 + if (term->quantityCount == 1)
1.1342 + return backtrackPatternCharacterOnce(opIndex);
1.1343 + else
1.1344 + return backtrackPatternCharacterFixed(opIndex);
1.1345 + case QuantifierGreedy:
1.1346 + return backtrackPatternCharacterGreedy(opIndex);
1.1347 + case QuantifierNonGreedy:
1.1348 + return backtrackPatternCharacterNonGreedy(opIndex);
1.1349 + }
1.1350 + break;
1.1351 +
1.1352 + case PatternTerm::TypeCharacterClass:
1.1353 + switch (term->quantityType) {
1.1354 + case QuantifierFixedCount:
1.1355 + if (term->quantityCount == 1)
1.1356 + return backtrackCharacterClassOnce(opIndex);
1.1357 + else
1.1358 + return backtrackCharacterClassFixed(opIndex);
1.1359 + case QuantifierGreedy:
1.1360 + return backtrackCharacterClassGreedy(opIndex);
1.1361 + case QuantifierNonGreedy:
1.1362 + return backtrackCharacterClassNonGreedy(opIndex);
1.1363 + }
1.1364 + break;
1.1365 +
1.1366 + case PatternTerm::TypeAssertionBOL:
1.1367 + return backtrackAssertionBOL(opIndex);
1.1368 +
1.1369 + case PatternTerm::TypeAssertionEOL:
1.1370 + return backtrackAssertionEOL(opIndex);
1.1371 +
1.1372 + case PatternTerm::TypeAssertionWordBoundary:
1.1373 + return backtrackAssertionWordBoundary(opIndex);
1.1374 +
1.1375 + case PatternTerm::TypeForwardReference:
1.1376 + return true;
1.1377 +
1.1378 + case PatternTerm::TypeParenthesesSubpattern:
1.1379 + case PatternTerm::TypeParentheticalAssertion:
1.1380 + ASSERT_NOT_REACHED();
1.1381 + return false;
1.1382 +
1.1383 + case PatternTerm::TypeDotStarEnclosure:
1.1384 + return backtrackDotStarEnclosure(opIndex);
1.1385 +
1.1386 + case PatternTerm::TypeBackReference:
1.1387 + return false;
1.1388 + }
1.1389 + return true;
1.1390 + }
1.1391 +
1.1392 + bool generate()
1.1393 + {
1.1394 + // Forwards generate the matching code.
1.1395 + ASSERT(m_ops.size());
1.1396 + size_t opIndex = 0;
1.1397 +
1.1398 + do {
1.1399 + YarrOp& op = m_ops[opIndex];
1.1400 + switch (op.m_op) {
1.1401 +
1.1402 + case OpTerm:
1.1403 + if (!generateTerm(opIndex))
1.1404 + return false;
1.1405 + break;
1.1406 +
1.1407 + // OpBodyAlternativeBegin/Next/End
1.1408 + //
1.1409 + // These nodes wrap the set of alternatives in the body of the regular expression.
1.1410 + // There may be either one or two chains of OpBodyAlternative nodes, one representing
1.1411 + // the 'once through' sequence of alternatives (if any exist), and one representing
1.1412 + // the repeating alternatives (again, if any exist).
1.1413 + //
1.1414 + // Upon normal entry to the Begin alternative, we will check that input is available.
1.1415 + // Reentry to the Begin alternative will take place after the check has taken place,
1.1416 + // and will assume that the input position has already been progressed as appropriate.
1.1417 + //
1.1418 + // Entry to subsequent Next/End alternatives occurs when the prior alternative has
1.1419 + // successfully completed a match - return a success state from JIT code.
1.1420 + //
1.1421 + // Next alternatives allow for reentry optimized to suit backtracking from its
1.1422 + // preceding alternative. It expects the input position to still be set to a position
1.1423 + // appropriate to its predecessor, and it will only perform an input check if the
1.1424 + // predecessor had a minimum size less than its own.
1.1425 + //
1.1426 + // In the case 'once through' expressions, the End node will also have a reentry
1.1427 + // point to jump to when the last alternative fails. Again, this expects the input
1.1428 + // position to still reflect that expected by the prior alternative.
1.1429 + case OpBodyAlternativeBegin: {
1.1430 + PatternAlternative* alternative = op.m_alternative;
1.1431 +
1.1432 + // Upon entry at the head of the set of alternatives, check if input is available
1.1433 + // to run the first alternative. (This progresses the input position).
1.1434 + op.m_jumps.append(jumpIfNoAvailableInput(alternative->m_minimumSize));
1.1435 + // We will reenter after the check, and assume the input position to have been
1.1436 + // set as appropriate to this alternative.
1.1437 + op.m_reentry = label();
1.1438 +
1.1439 + if (alternative->m_minimumSize > INT_MAX)
1.1440 + return false;
1.1441 + m_checked = alternative->m_minimumSize;
1.1442 + break;
1.1443 + }
1.1444 + case OpBodyAlternativeNext:
1.1445 + case OpBodyAlternativeEnd: {
1.1446 + PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
1.1447 + PatternAlternative* alternative = op.m_alternative;
1.1448 +
1.1449 + // If we get here, the prior alternative matched - return success.
1.1450 +
1.1451 + // Adjust the stack pointer to remove the pattern's frame.
1.1452 +#if !WTF_CPU_SPARC
1.1453 + removeCallFrame();
1.1454 +#endif
1.1455 +
1.1456 + // Load appropriate values into the return register and the first output
1.1457 + // slot, and return. In the case of pattern with a fixed size, we will
1.1458 + // not have yet set the value in the first
1.1459 + ASSERT(index != returnRegister);
1.1460 + if (m_pattern.m_body->m_hasFixedSize) {
1.1461 + move(index, returnRegister);
1.1462 + if (priorAlternative->m_minimumSize)
1.1463 + sub32(Imm32(priorAlternative->m_minimumSize), returnRegister);
1.1464 + if (compileMode == IncludeSubpatterns)
1.1465 + store32(returnRegister, output);
1.1466 + } else
1.1467 + getMatchStart(returnRegister);
1.1468 + if (compileMode == IncludeSubpatterns)
1.1469 + store32(index, Address(output, 4));
1.1470 +#if WTF_CPU_X86_64
1.1471 + // upper 32bit to 0
1.1472 + move32(returnRegister, returnRegister);
1.1473 + lshiftPtr(Imm32(32), index);
1.1474 + orPtr(index, returnRegister);
1.1475 +#else
1.1476 + move(index, returnRegister2);
1.1477 +#endif
1.1478 +
1.1479 + generateReturn();
1.1480 +
1.1481 + // This is the divide between the tail of the prior alternative, above, and
1.1482 + // the head of the subsequent alternative, below.
1.1483 +
1.1484 + if (op.m_op == OpBodyAlternativeNext) {
1.1485 + // This is the reentry point for the Next alternative. We expect any code
1.1486 + // that jumps here to do so with the input position matching that of the
1.1487 + // PRIOR alteranative, and we will only check input availability if we
1.1488 + // need to progress it forwards.
1.1489 + op.m_reentry = label();
1.1490 + if (alternative->m_minimumSize > priorAlternative->m_minimumSize) {
1.1491 + add32(Imm32(alternative->m_minimumSize - priorAlternative->m_minimumSize), index);
1.1492 + op.m_jumps.append(jumpIfNoAvailableInput());
1.1493 + } else if (priorAlternative->m_minimumSize > alternative->m_minimumSize)
1.1494 + sub32(Imm32(priorAlternative->m_minimumSize - alternative->m_minimumSize), index);
1.1495 + } else if (op.m_nextOp == notFound) {
1.1496 + // This is the reentry point for the End of 'once through' alternatives,
1.1497 + // jumped to when the last alternative fails to match.
1.1498 + op.m_reentry = label();
1.1499 + sub32(Imm32(priorAlternative->m_minimumSize), index);
1.1500 + }
1.1501 +
1.1502 + if (op.m_op == OpBodyAlternativeNext)
1.1503 + m_checked += alternative->m_minimumSize;
1.1504 + m_checked -= priorAlternative->m_minimumSize;
1.1505 + break;
1.1506 + }
1.1507 +
1.1508 + // OpSimpleNestedAlternativeBegin/Next/End
1.1509 + // OpNestedAlternativeBegin/Next/End
1.1510 + //
1.1511 + // These nodes are used to handle sets of alternatives that are nested within
1.1512 + // subpatterns and parenthetical assertions. The 'simple' forms are used where
1.1513 + // we do not need to be able to backtrack back into any alternative other than
1.1514 + // the last, the normal forms allow backtracking into any alternative.
1.1515 + //
1.1516 + // Each Begin/Next node is responsible for planting an input check to ensure
1.1517 + // sufficient input is available on entry. Next nodes additionally need to
1.1518 + // jump to the end - Next nodes use the End node's m_jumps list to hold this
1.1519 + // set of jumps.
1.1520 + //
1.1521 + // In the non-simple forms, successful alternative matches must store a
1.1522 + // 'return address' using a DataLabelPtr, used to store the address to jump
1.1523 + // to when backtracking, to get to the code for the appropriate alternative.
1.1524 + case OpSimpleNestedAlternativeBegin:
1.1525 + case OpNestedAlternativeBegin: {
1.1526 + PatternTerm* term = op.m_term;
1.1527 + PatternAlternative* alternative = op.m_alternative;
1.1528 + PatternDisjunction* disjunction = term->parentheses.disjunction;
1.1529 +
1.1530 + // Calculate how much input we need to check for, and if non-zero check.
1.1531 + op.m_checkAdjust = alternative->m_minimumSize;
1.1532 + if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion))
1.1533 + op.m_checkAdjust -= disjunction->m_minimumSize;
1.1534 + if (op.m_checkAdjust)
1.1535 + op.m_jumps.append(jumpIfNoAvailableInput(op.m_checkAdjust));
1.1536 +
1.1537 + m_checked += op.m_checkAdjust;
1.1538 + break;
1.1539 + }
1.1540 + case OpSimpleNestedAlternativeNext:
1.1541 + case OpNestedAlternativeNext: {
1.1542 + PatternTerm* term = op.m_term;
1.1543 + PatternAlternative* alternative = op.m_alternative;
1.1544 + PatternDisjunction* disjunction = term->parentheses.disjunction;
1.1545 +
1.1546 + // In the non-simple case, store a 'return address' so we can backtrack correctly.
1.1547 + if (op.m_op == OpNestedAlternativeNext) {
1.1548 + unsigned parenthesesFrameLocation = term->frameLocation;
1.1549 + unsigned alternativeFrameLocation = parenthesesFrameLocation;
1.1550 + if (term->quantityType != QuantifierFixedCount)
1.1551 + alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1.1552 + op.m_returnAddress = storeToFrameWithPatch(alternativeFrameLocation);
1.1553 + }
1.1554 +
1.1555 + if (term->quantityType != QuantifierFixedCount && !m_ops[op.m_previousOp].m_alternative->m_minimumSize) {
1.1556 + // If the previous alternative matched without consuming characters then
1.1557 + // backtrack to try to match while consumming some input.
1.1558 + op.m_zeroLengthMatch = branch32(Equal, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
1.1559 + }
1.1560 +
1.1561 + // If we reach here then the last alternative has matched - jump to the
1.1562 + // End node, to skip over any further alternatives.
1.1563 + //
1.1564 + // FIXME: this is logically O(N^2) (though N can be expected to be very
1.1565 + // small). We could avoid this either by adding an extra jump to the JIT
1.1566 + // data structures, or by making backtracking code that jumps to Next
1.1567 + // alternatives are responsible for checking that input is available (if
1.1568 + // we didn't need to plant the input checks, then m_jumps would be free).
1.1569 + YarrOp* endOp = &m_ops[op.m_nextOp];
1.1570 + while (endOp->m_nextOp != notFound) {
1.1571 + ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext);
1.1572 + endOp = &m_ops[endOp->m_nextOp];
1.1573 + }
1.1574 + ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd);
1.1575 + endOp->m_jumps.append(jump());
1.1576 +
1.1577 + // This is the entry point for the next alternative.
1.1578 + op.m_reentry = label();
1.1579 +
1.1580 + // Calculate how much input we need to check for, and if non-zero check.
1.1581 + op.m_checkAdjust = alternative->m_minimumSize;
1.1582 + if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion))
1.1583 + op.m_checkAdjust -= disjunction->m_minimumSize;
1.1584 + if (op.m_checkAdjust)
1.1585 + op.m_jumps.append(jumpIfNoAvailableInput(op.m_checkAdjust));
1.1586 +
1.1587 + YarrOp& lastOp = m_ops[op.m_previousOp];
1.1588 + m_checked -= lastOp.m_checkAdjust;
1.1589 + m_checked += op.m_checkAdjust;
1.1590 + break;
1.1591 + }
1.1592 + case OpSimpleNestedAlternativeEnd:
1.1593 + case OpNestedAlternativeEnd: {
1.1594 + PatternTerm* term = op.m_term;
1.1595 +
1.1596 + // In the non-simple case, store a 'return address' so we can backtrack correctly.
1.1597 + if (op.m_op == OpNestedAlternativeEnd) {
1.1598 + unsigned parenthesesFrameLocation = term->frameLocation;
1.1599 + unsigned alternativeFrameLocation = parenthesesFrameLocation;
1.1600 + if (term->quantityType != QuantifierFixedCount)
1.1601 + alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1.1602 + op.m_returnAddress = storeToFrameWithPatch(alternativeFrameLocation);
1.1603 + }
1.1604 +
1.1605 + if (term->quantityType != QuantifierFixedCount && !m_ops[op.m_previousOp].m_alternative->m_minimumSize) {
1.1606 + // If the previous alternative matched without consuming characters then
1.1607 + // backtrack to try to match while consumming some input.
1.1608 + op.m_zeroLengthMatch = branch32(Equal, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
1.1609 + }
1.1610 +
1.1611 + // If this set of alternatives contains more than one alternative,
1.1612 + // then the Next nodes will have planted jumps to the End, and added
1.1613 + // them to this node's m_jumps list.
1.1614 + op.m_jumps.link(this);
1.1615 + op.m_jumps.clear();
1.1616 +
1.1617 + YarrOp& lastOp = m_ops[op.m_previousOp];
1.1618 + m_checked -= lastOp.m_checkAdjust;
1.1619 + break;
1.1620 + }
1.1621 +
1.1622 + // OpParenthesesSubpatternOnceBegin/End
1.1623 + //
1.1624 + // These nodes support (optionally) capturing subpatterns, that have a
1.1625 + // quantity count of 1 (this covers fixed once, and ?/?? quantifiers).
1.1626 + case OpParenthesesSubpatternOnceBegin: {
1.1627 + PatternTerm* term = op.m_term;
1.1628 + unsigned parenthesesFrameLocation = term->frameLocation;
1.1629 + const RegisterID indexTemporary = regT0;
1.1630 + ASSERT(term->quantityCount == 1);
1.1631 +
1.1632 + // Upon entry to a Greedy quantified set of parenthese store the index.
1.1633 + // We'll use this for two purposes:
1.1634 + // - To indicate which iteration we are on of mathing the remainder of
1.1635 + // the expression after the parentheses - the first, including the
1.1636 + // match within the parentheses, or the second having skipped over them.
1.1637 + // - To check for empty matches, which must be rejected.
1.1638 + //
1.1639 + // At the head of a NonGreedy set of parentheses we'll immediately set the
1.1640 + // value on the stack to -1 (indicating a match skipping the subpattern),
1.1641 + // and plant a jump to the end. We'll also plant a label to backtrack to
1.1642 + // to reenter the subpattern later, with a store to set up index on the
1.1643 + // second iteration.
1.1644 + //
1.1645 + // FIXME: for capturing parens, could use the index in the capture array?
1.1646 + if (term->quantityType == QuantifierGreedy)
1.1647 + storeToFrame(index, parenthesesFrameLocation);
1.1648 + else if (term->quantityType == QuantifierNonGreedy) {
1.1649 + storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1.1650 + op.m_jumps.append(jump());
1.1651 + op.m_reentry = label();
1.1652 + storeToFrame(index, parenthesesFrameLocation);
1.1653 + }
1.1654 +
1.1655 + // If the parenthese are capturing, store the starting index value to the
1.1656 + // captures array, offsetting as necessary.
1.1657 + //
1.1658 + // FIXME: could avoid offsetting this value in JIT code, apply
1.1659 + // offsets only afterwards, at the point the results array is
1.1660 + // being accessed.
1.1661 + if (term->capture() && compileMode == IncludeSubpatterns) {
1.1662 + int inputOffset = term->inputPosition - m_checked;
1.1663 + if (term->quantityType == QuantifierFixedCount)
1.1664 + inputOffset -= term->parentheses.disjunction->m_minimumSize;
1.1665 + if (inputOffset) {
1.1666 + move(index, indexTemporary);
1.1667 + add32(Imm32(inputOffset), indexTemporary);
1.1668 + setSubpatternStart(indexTemporary, term->parentheses.subpatternId);
1.1669 + } else
1.1670 + setSubpatternStart(index, term->parentheses.subpatternId);
1.1671 + }
1.1672 + break;
1.1673 + }
1.1674 + case OpParenthesesSubpatternOnceEnd: {
1.1675 + PatternTerm* term = op.m_term;
1.1676 + const RegisterID indexTemporary = regT0;
1.1677 + ASSERT(term->quantityCount == 1);
1.1678 +
1.1679 +#ifndef NDEBUG
1.1680 + // Runtime ASSERT to make sure that the nested alternative handled the
1.1681 + // "no input consumed" check.
1.1682 + if (term->quantityType != QuantifierFixedCount && !term->parentheses.disjunction->m_minimumSize) {
1.1683 + Jump pastBreakpoint;
1.1684 + pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
1.1685 + breakpoint();
1.1686 + pastBreakpoint.link(this);
1.1687 + }
1.1688 +#endif
1.1689 +
1.1690 + // If the parenthese are capturing, store the ending index value to the
1.1691 + // captures array, offsetting as necessary.
1.1692 + //
1.1693 + // FIXME: could avoid offsetting this value in JIT code, apply
1.1694 + // offsets only afterwards, at the point the results array is
1.1695 + // being accessed.
1.1696 + if (term->capture() && compileMode == IncludeSubpatterns) {
1.1697 + int inputOffset = term->inputPosition - m_checked;
1.1698 + if (inputOffset) {
1.1699 + move(index, indexTemporary);
1.1700 + add32(Imm32(inputOffset), indexTemporary);
1.1701 + setSubpatternEnd(indexTemporary, term->parentheses.subpatternId);
1.1702 + } else
1.1703 + setSubpatternEnd(index, term->parentheses.subpatternId);
1.1704 + }
1.1705 +
1.1706 + // If the parentheses are quantified Greedy then add a label to jump back
1.1707 + // to if get a failed match from after the parentheses. For NonGreedy
1.1708 + // parentheses, link the jump from before the subpattern to here.
1.1709 + if (term->quantityType == QuantifierGreedy)
1.1710 + op.m_reentry = label();
1.1711 + else if (term->quantityType == QuantifierNonGreedy) {
1.1712 + YarrOp& beginOp = m_ops[op.m_previousOp];
1.1713 + beginOp.m_jumps.link(this);
1.1714 + }
1.1715 + break;
1.1716 + }
1.1717 +
1.1718 + // OpParenthesesSubpatternTerminalBegin/End
1.1719 + case OpParenthesesSubpatternTerminalBegin: {
1.1720 + PatternTerm* term = op.m_term;
1.1721 + ASSERT(term->quantityType == QuantifierGreedy);
1.1722 + ASSERT(term->quantityCount == quantifyInfinite);
1.1723 + ASSERT(!term->capture());
1.1724 +
1.1725 + // Upon entry set a label to loop back to.
1.1726 + op.m_reentry = label();
1.1727 +
1.1728 + // Store the start index of the current match; we need to reject zero
1.1729 + // length matches.
1.1730 + storeToFrame(index, term->frameLocation);
1.1731 + break;
1.1732 + }
1.1733 + case OpParenthesesSubpatternTerminalEnd: {
1.1734 + YarrOp& beginOp = m_ops[op.m_previousOp];
1.1735 +#ifndef NDEBUG
1.1736 + PatternTerm* term = op.m_term;
1.1737 +
1.1738 + // Runtime ASSERT to make sure that the nested alternative handled the
1.1739 + // "no input consumed" check.
1.1740 + Jump pastBreakpoint;
1.1741 + pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
1.1742 + breakpoint();
1.1743 + pastBreakpoint.link(this);
1.1744 +#endif
1.1745 +
1.1746 + // We know that the match is non-zero, we can accept it and
1.1747 + // loop back up to the head of the subpattern.
1.1748 + jump(beginOp.m_reentry);
1.1749 +
1.1750 + // This is the entry point to jump to when we stop matching - we will
1.1751 + // do so once the subpattern cannot match any more.
1.1752 + op.m_reentry = label();
1.1753 + break;
1.1754 + }
1.1755 +
1.1756 + // OpParentheticalAssertionBegin/End
1.1757 + case OpParentheticalAssertionBegin: {
1.1758 + PatternTerm* term = op.m_term;
1.1759 +
1.1760 + // Store the current index - assertions should not update index, so
1.1761 + // we will need to restore it upon a successful match.
1.1762 + unsigned parenthesesFrameLocation = term->frameLocation;
1.1763 + storeToFrame(index, parenthesesFrameLocation);
1.1764 +
1.1765 + // Check
1.1766 + op.m_checkAdjust = m_checked - term->inputPosition;
1.1767 + if (op.m_checkAdjust)
1.1768 + sub32(Imm32(op.m_checkAdjust), index);
1.1769 +
1.1770 + m_checked -= op.m_checkAdjust;
1.1771 + break;
1.1772 + }
1.1773 + case OpParentheticalAssertionEnd: {
1.1774 + PatternTerm* term = op.m_term;
1.1775 +
1.1776 + // Restore the input index value.
1.1777 + unsigned parenthesesFrameLocation = term->frameLocation;
1.1778 + loadFromFrame(parenthesesFrameLocation, index);
1.1779 +
1.1780 + // If inverted, a successful match of the assertion must be treated
1.1781 + // as a failure, so jump to backtracking.
1.1782 + if (term->invert()) {
1.1783 + op.m_jumps.append(jump());
1.1784 + op.m_reentry = label();
1.1785 + }
1.1786 +
1.1787 + YarrOp& lastOp = m_ops[op.m_previousOp];
1.1788 + m_checked += lastOp.m_checkAdjust;
1.1789 + break;
1.1790 + }
1.1791 +
1.1792 + case OpMatchFailed:
1.1793 +#if !WTF_CPU_SPARC
1.1794 + removeCallFrame();
1.1795 +#endif
1.1796 +#if WTF_CPU_X86_64
1.1797 + move(TrustedImm32(int(WTF::notFound)), returnRegister);
1.1798 +#else
1.1799 + move(TrustedImmPtr((void*)WTF::notFound), returnRegister);
1.1800 + move(TrustedImm32(0), returnRegister2);
1.1801 +#endif
1.1802 + generateReturn();
1.1803 + break;
1.1804 + }
1.1805 +
1.1806 + ++opIndex;
1.1807 + } while (opIndex < m_ops.size());
1.1808 +
1.1809 + return true;
1.1810 + }
1.1811 +
1.1812 + bool backtrack()
1.1813 + {
1.1814 + // Backwards generate the backtracking code.
1.1815 + size_t opIndex = m_ops.size();
1.1816 + ASSERT(opIndex);
1.1817 +
1.1818 + do {
1.1819 + --opIndex;
1.1820 + YarrOp& op = m_ops[opIndex];
1.1821 + switch (op.m_op) {
1.1822 +
1.1823 + case OpTerm:
1.1824 + if (!backtrackTerm(opIndex))
1.1825 + return false;
1.1826 + break;
1.1827 +
1.1828 + // OpBodyAlternativeBegin/Next/End
1.1829 + //
1.1830 + // For each Begin/Next node representing an alternative, we need to decide what to do
1.1831 + // in two circumstances:
1.1832 + // - If we backtrack back into this node, from within the alternative.
1.1833 + // - If the input check at the head of the alternative fails (if this exists).
1.1834 + //
1.1835 + // We treat these two cases differently since in the former case we have slightly
1.1836 + // more information - since we are backtracking out of a prior alternative we know
1.1837 + // that at least enough input was available to run it. For example, given the regular
1.1838 + // expression /a|b/, if we backtrack out of the first alternative (a failed pattern
1.1839 + // character match of 'a'), then we need not perform an additional input availability
1.1840 + // check before running the second alternative.
1.1841 + //
1.1842 + // Backtracking required differs for the last alternative, which in the case of the
1.1843 + // repeating set of alternatives must loop. The code generated for the last alternative
1.1844 + // will also be used to handle all input check failures from any prior alternatives -
1.1845 + // these require similar functionality, in seeking the next available alternative for
1.1846 + // which there is sufficient input.
1.1847 + //
1.1848 + // Since backtracking of all other alternatives simply requires us to link backtracks
1.1849 + // to the reentry point for the subsequent alternative, we will only be generating any
1.1850 + // code when backtracking the last alternative.
1.1851 + case OpBodyAlternativeBegin:
1.1852 + case OpBodyAlternativeNext: {
1.1853 + PatternAlternative* alternative = op.m_alternative;
1.1854 +
1.1855 + if (op.m_op == OpBodyAlternativeNext) {
1.1856 + PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
1.1857 + m_checked += priorAlternative->m_minimumSize;
1.1858 + }
1.1859 + m_checked -= alternative->m_minimumSize;
1.1860 +
1.1861 + // Is this the last alternative? If not, then if we backtrack to this point we just
1.1862 + // need to jump to try to match the next alternative.
1.1863 + if (m_ops[op.m_nextOp].m_op != OpBodyAlternativeEnd) {
1.1864 + m_backtrackingState.linkTo(m_ops[op.m_nextOp].m_reentry, this);
1.1865 + break;
1.1866 + }
1.1867 + YarrOp& endOp = m_ops[op.m_nextOp];
1.1868 +
1.1869 + YarrOp* beginOp = &op;
1.1870 + while (beginOp->m_op != OpBodyAlternativeBegin) {
1.1871 + ASSERT(beginOp->m_op == OpBodyAlternativeNext);
1.1872 + beginOp = &m_ops[beginOp->m_previousOp];
1.1873 + }
1.1874 +
1.1875 + bool onceThrough = endOp.m_nextOp == notFound;
1.1876 +
1.1877 + // First, generate code to handle cases where we backtrack out of an attempted match
1.1878 + // of the last alternative. If this is a 'once through' set of alternatives then we
1.1879 + // have nothing to do - link this straight through to the End.
1.1880 + if (onceThrough)
1.1881 + m_backtrackingState.linkTo(endOp.m_reentry, this);
1.1882 + else {
1.1883 + // If we don't need to move the input poistion, and the pattern has a fixed size
1.1884 + // (in which case we omit the store of the start index until the pattern has matched)
1.1885 + // then we can just link the backtrack out of the last alternative straight to the
1.1886 + // head of the first alternative.
1.1887 + if (m_pattern.m_body->m_hasFixedSize
1.1888 + && (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize)
1.1889 + && (alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize == 1))
1.1890 + m_backtrackingState.linkTo(beginOp->m_reentry, this);
1.1891 + else {
1.1892 + // We need to generate a trampoline of code to execute before looping back
1.1893 + // around to the first alternative.
1.1894 + m_backtrackingState.link(this);
1.1895 +
1.1896 + // If the pattern size is not fixed, then store the start index, for use if we match.
1.1897 + if (!m_pattern.m_body->m_hasFixedSize) {
1.1898 + if (alternative->m_minimumSize == 1)
1.1899 + setMatchStart(index);
1.1900 + else {
1.1901 + move(index, regT0);
1.1902 + if (alternative->m_minimumSize)
1.1903 + sub32(Imm32(alternative->m_minimumSize - 1), regT0);
1.1904 + else
1.1905 + add32(TrustedImm32(1), regT0);
1.1906 + setMatchStart(regT0);
1.1907 + }
1.1908 + }
1.1909 +
1.1910 + // Generate code to loop. Check whether the last alternative is longer than the
1.1911 + // first (e.g. /a|xy/ or /a|xyz/).
1.1912 + if (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize) {
1.1913 + // We want to loop, and increment input position. If the delta is 1, it is
1.1914 + // already correctly incremented, if more than one then decrement as appropriate.
1.1915 + unsigned delta = alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize;
1.1916 + ASSERT(delta);
1.1917 + if (delta != 1)
1.1918 + sub32(Imm32(delta - 1), index);
1.1919 + jump(beginOp->m_reentry);
1.1920 + } else {
1.1921 + // If the first alternative has minimum size 0xFFFFFFFFu, then there cannot
1.1922 + // be sufficent input available to handle this, so just fall through.
1.1923 + unsigned delta = beginOp->m_alternative->m_minimumSize - alternative->m_minimumSize;
1.1924 + if (delta != 0xFFFFFFFFu) {
1.1925 + // We need to check input because we are incrementing the input.
1.1926 + add32(Imm32(delta + 1), index);
1.1927 + checkInput().linkTo(beginOp->m_reentry, this);
1.1928 + }
1.1929 + }
1.1930 + }
1.1931 + }
1.1932 +
1.1933 + // We can reach this point in the code in two ways:
1.1934 + // - Fallthrough from the code above (a repeating alternative backtracked out of its
1.1935 + // last alternative, and did not have sufficent input to run the first).
1.1936 + // - We will loop back up to the following label when a releating alternative loops,
1.1937 + // following a failed input check.
1.1938 + //
1.1939 + // Either way, we have just failed the input check for the first alternative.
1.1940 + Label firstInputCheckFailed(this);
1.1941 +
1.1942 + // Generate code to handle input check failures from alternatives except the last.
1.1943 + // prevOp is the alternative we're handling a bail out from (initially Begin), and
1.1944 + // nextOp is the alternative we will be attempting to reenter into.
1.1945 + //
1.1946 + // We will link input check failures from the forwards matching path back to the code
1.1947 + // that can handle them.
1.1948 + YarrOp* prevOp = beginOp;
1.1949 + YarrOp* nextOp = &m_ops[beginOp->m_nextOp];
1.1950 + while (nextOp->m_op != OpBodyAlternativeEnd) {
1.1951 + prevOp->m_jumps.link(this);
1.1952 +
1.1953 + // We only get here if an input check fails, it is only worth checking again
1.1954 + // if the next alternative has a minimum size less than the last.
1.1955 + if (prevOp->m_alternative->m_minimumSize > nextOp->m_alternative->m_minimumSize) {
1.1956 + // FIXME: if we added an extra label to YarrOp, we could avoid needing to
1.1957 + // subtract delta back out, and reduce this code. Should performance test
1.1958 + // the benefit of this.
1.1959 + unsigned delta = prevOp->m_alternative->m_minimumSize - nextOp->m_alternative->m_minimumSize;
1.1960 + sub32(Imm32(delta), index);
1.1961 + Jump fail = jumpIfNoAvailableInput();
1.1962 + add32(Imm32(delta), index);
1.1963 + jump(nextOp->m_reentry);
1.1964 + fail.link(this);
1.1965 + } else if (prevOp->m_alternative->m_minimumSize < nextOp->m_alternative->m_minimumSize)
1.1966 + add32(Imm32(nextOp->m_alternative->m_minimumSize - prevOp->m_alternative->m_minimumSize), index);
1.1967 + prevOp = nextOp;
1.1968 + nextOp = &m_ops[nextOp->m_nextOp];
1.1969 + }
1.1970 +
1.1971 + // We fall through to here if there is insufficient input to run the last alternative.
1.1972 +
1.1973 + // If there is insufficient input to run the last alternative, then for 'once through'
1.1974 + // alternatives we are done - just jump back up into the forwards matching path at the End.
1.1975 + if (onceThrough) {
1.1976 + op.m_jumps.linkTo(endOp.m_reentry, this);
1.1977 + jump(endOp.m_reentry);
1.1978 + break;
1.1979 + }
1.1980 +
1.1981 + // For repeating alternatives, link any input check failure from the last alternative to
1.1982 + // this point.
1.1983 + op.m_jumps.link(this);
1.1984 +
1.1985 + bool needsToUpdateMatchStart = !m_pattern.m_body->m_hasFixedSize;
1.1986 +
1.1987 + // Check for cases where input position is already incremented by 1 for the last
1.1988 + // alternative (this is particularly useful where the minimum size of the body
1.1989 + // disjunction is 0, e.g. /a*|b/).
1.1990 + if (needsToUpdateMatchStart && alternative->m_minimumSize == 1) {
1.1991 + // index is already incremented by 1, so just store it now!
1.1992 + setMatchStart(index);
1.1993 + needsToUpdateMatchStart = false;
1.1994 + }
1.1995 +
1.1996 + // Check whether there is sufficient input to loop. Increment the input position by
1.1997 + // one, and check. Also add in the minimum disjunction size before checking - there
1.1998 + // is no point in looping if we're just going to fail all the input checks around
1.1999 + // the next iteration.
1.2000 + ASSERT(alternative->m_minimumSize >= m_pattern.m_body->m_minimumSize);
1.2001 + if (alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) {
1.2002 + // If the last alternative had the same minimum size as the disjunction,
1.2003 + // just simply increment input pos by 1, no adjustment based on minimum size.
1.2004 + add32(TrustedImm32(1), index);
1.2005 + } else {
1.2006 + // If the minumum for the last alternative was one greater than than that
1.2007 + // for the disjunction, we're already progressed by 1, nothing to do!
1.2008 + unsigned delta = (alternative->m_minimumSize - m_pattern.m_body->m_minimumSize) - 1;
1.2009 + if (delta)
1.2010 + sub32(Imm32(delta), index);
1.2011 + }
1.2012 + Jump matchFailed = jumpIfNoAvailableInput();
1.2013 +
1.2014 + if (needsToUpdateMatchStart) {
1.2015 + if (!m_pattern.m_body->m_minimumSize)
1.2016 + setMatchStart(index);
1.2017 + else {
1.2018 + move(index, regT0);
1.2019 + sub32(Imm32(m_pattern.m_body->m_minimumSize), regT0);
1.2020 + setMatchStart(regT0);
1.2021 + }
1.2022 + }
1.2023 +
1.2024 + // Calculate how much more input the first alternative requires than the minimum
1.2025 + // for the body as a whole. If no more is needed then we dont need an additional
1.2026 + // input check here - jump straight back up to the start of the first alternative.
1.2027 + if (beginOp->m_alternative->m_minimumSize == m_pattern.m_body->m_minimumSize)
1.2028 + jump(beginOp->m_reentry);
1.2029 + else {
1.2030 + if (beginOp->m_alternative->m_minimumSize > m_pattern.m_body->m_minimumSize)
1.2031 + add32(Imm32(beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize), index);
1.2032 + else
1.2033 + sub32(Imm32(m_pattern.m_body->m_minimumSize - beginOp->m_alternative->m_minimumSize), index);
1.2034 + checkInput().linkTo(beginOp->m_reentry, this);
1.2035 + jump(firstInputCheckFailed);
1.2036 + }
1.2037 +
1.2038 + // We jump to here if we iterate to the point that there is insufficient input to
1.2039 + // run any matches, and need to return a failure state from JIT code.
1.2040 + matchFailed.link(this);
1.2041 +
1.2042 +#if !WTF_CPU_SPARC
1.2043 + removeCallFrame();
1.2044 +#endif
1.2045 +#if WTF_CPU_X86_64
1.2046 + move(TrustedImm32(int(WTF::notFound)), returnRegister);
1.2047 +#else
1.2048 + move(TrustedImmPtr((void*)WTF::notFound), returnRegister);
1.2049 + move(TrustedImm32(0), returnRegister2);
1.2050 +#endif
1.2051 + generateReturn();
1.2052 + break;
1.2053 + }
1.2054 + case OpBodyAlternativeEnd: {
1.2055 + // We should never backtrack back into a body disjunction.
1.2056 + ASSERT(m_backtrackingState.isEmpty());
1.2057 +
1.2058 + PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
1.2059 + m_checked += priorAlternative->m_minimumSize;
1.2060 + break;
1.2061 + }
1.2062 +
1.2063 + // OpSimpleNestedAlternativeBegin/Next/End
1.2064 + // OpNestedAlternativeBegin/Next/End
1.2065 + //
1.2066 + // Generate code for when we backtrack back out of an alternative into
1.2067 + // a Begin or Next node, or when the entry input count check fails. If
1.2068 + // there are more alternatives we need to jump to the next alternative,
1.2069 + // if not we backtrack back out of the current set of parentheses.
1.2070 + //
1.2071 + // In the case of non-simple nested assertions we need to also link the
1.2072 + // 'return address' appropriately to backtrack back out into the correct
1.2073 + // alternative.
1.2074 + case OpSimpleNestedAlternativeBegin:
1.2075 + case OpSimpleNestedAlternativeNext:
1.2076 + case OpNestedAlternativeBegin:
1.2077 + case OpNestedAlternativeNext: {
1.2078 + YarrOp& nextOp = m_ops[op.m_nextOp];
1.2079 + bool isBegin = op.m_previousOp == notFound;
1.2080 + bool isLastAlternative = nextOp.m_nextOp == notFound;
1.2081 + ASSERT(isBegin == (op.m_op == OpSimpleNestedAlternativeBegin || op.m_op == OpNestedAlternativeBegin));
1.2082 + ASSERT(isLastAlternative == (nextOp.m_op == OpSimpleNestedAlternativeEnd || nextOp.m_op == OpNestedAlternativeEnd));
1.2083 +
1.2084 + // Treat an input check failure the same as a failed match.
1.2085 + m_backtrackingState.append(op.m_jumps);
1.2086 +
1.2087 + // Set the backtracks to jump to the appropriate place. We may need
1.2088 + // to link the backtracks in one of three different way depending on
1.2089 + // the type of alternative we are dealing with:
1.2090 + // - A single alternative, with no simplings.
1.2091 + // - The last alternative of a set of two or more.
1.2092 + // - An alternative other than the last of a set of two or more.
1.2093 + //
1.2094 + // In the case of a single alternative on its own, we don't need to
1.2095 + // jump anywhere - if the alternative fails to match we can just
1.2096 + // continue to backtrack out of the parentheses without jumping.
1.2097 + //
1.2098 + // In the case of the last alternative in a set of more than one, we
1.2099 + // need to jump to return back out to the beginning. We'll do so by
1.2100 + // adding a jump to the End node's m_jumps list, and linking this
1.2101 + // when we come to generate the Begin node. For alternatives other
1.2102 + // than the last, we need to jump to the next alternative.
1.2103 + //
1.2104 + // If the alternative had adjusted the input position we must link
1.2105 + // backtracking to here, correct, and then jump on. If not we can
1.2106 + // link the backtracks directly to their destination.
1.2107 + if (op.m_checkAdjust) {
1.2108 + // Handle the cases where we need to link the backtracks here.
1.2109 + m_backtrackingState.link(this);
1.2110 + sub32(Imm32(op.m_checkAdjust), index);
1.2111 + if (!isLastAlternative) {
1.2112 + // An alternative that is not the last should jump to its successor.
1.2113 + jump(nextOp.m_reentry);
1.2114 + } else if (!isBegin) {
1.2115 + // The last of more than one alternatives must jump back to the beginning.
1.2116 + nextOp.m_jumps.append(jump());
1.2117 + } else {
1.2118 + // A single alternative on its own can fall through.
1.2119 + m_backtrackingState.fallthrough();
1.2120 + }
1.2121 + } else {
1.2122 + // Handle the cases where we can link the backtracks directly to their destinations.
1.2123 + if (!isLastAlternative) {
1.2124 + // An alternative that is not the last should jump to its successor.
1.2125 + m_backtrackingState.linkTo(nextOp.m_reentry, this);
1.2126 + } else if (!isBegin) {
1.2127 + // The last of more than one alternatives must jump back to the beginning.
1.2128 + m_backtrackingState.takeBacktracksToJumpList(nextOp.m_jumps, this);
1.2129 + }
1.2130 + // In the case of a single alternative on its own do nothing - it can fall through.
1.2131 + }
1.2132 +
1.2133 + // If there is a backtrack jump from a zero length match link it here.
1.2134 + if (op.m_zeroLengthMatch.isSet())
1.2135 + m_backtrackingState.append(op.m_zeroLengthMatch);
1.2136 +
1.2137 + // At this point we've handled the backtracking back into this node.
1.2138 + // Now link any backtracks that need to jump to here.
1.2139 +
1.2140 + // For non-simple alternatives, link the alternative's 'return address'
1.2141 + // so that we backtrack back out into the previous alternative.
1.2142 + if (op.m_op == OpNestedAlternativeNext)
1.2143 + m_backtrackingState.append(op.m_returnAddress);
1.2144 +
1.2145 + // If there is more than one alternative, then the last alternative will
1.2146 + // have planted a jump to be linked to the end. This jump was added to the
1.2147 + // End node's m_jumps list. If we are back at the beginning, link it here.
1.2148 + if (isBegin) {
1.2149 + YarrOp* endOp = &m_ops[op.m_nextOp];
1.2150 + while (endOp->m_nextOp != notFound) {
1.2151 + ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext);
1.2152 + endOp = &m_ops[endOp->m_nextOp];
1.2153 + }
1.2154 + ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd);
1.2155 + m_backtrackingState.append(endOp->m_jumps);
1.2156 + }
1.2157 +
1.2158 + if (!isBegin) {
1.2159 + YarrOp& lastOp = m_ops[op.m_previousOp];
1.2160 + m_checked += lastOp.m_checkAdjust;
1.2161 + }
1.2162 + m_checked -= op.m_checkAdjust;
1.2163 + break;
1.2164 + }
1.2165 + case OpSimpleNestedAlternativeEnd:
1.2166 + case OpNestedAlternativeEnd: {
1.2167 + PatternTerm* term = op.m_term;
1.2168 +
1.2169 + // If there is a backtrack jump from a zero length match link it here.
1.2170 + if (op.m_zeroLengthMatch.isSet())
1.2171 + m_backtrackingState.append(op.m_zeroLengthMatch);
1.2172 +
1.2173 + // If we backtrack into the end of a simple subpattern do nothing;
1.2174 + // just continue through into the last alternative. If we backtrack
1.2175 + // into the end of a non-simple set of alterntives we need to jump
1.2176 + // to the backtracking return address set up during generation.
1.2177 + if (op.m_op == OpNestedAlternativeEnd) {
1.2178 + m_backtrackingState.link(this);
1.2179 +
1.2180 + // Plant a jump to the return address.
1.2181 + unsigned parenthesesFrameLocation = term->frameLocation;
1.2182 + unsigned alternativeFrameLocation = parenthesesFrameLocation;
1.2183 + if (term->quantityType != QuantifierFixedCount)
1.2184 + alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1.2185 + loadFromFrameAndJump(alternativeFrameLocation);
1.2186 +
1.2187 + // Link the DataLabelPtr associated with the end of the last
1.2188 + // alternative to this point.
1.2189 + m_backtrackingState.append(op.m_returnAddress);
1.2190 + }
1.2191 +
1.2192 + YarrOp& lastOp = m_ops[op.m_previousOp];
1.2193 + m_checked += lastOp.m_checkAdjust;
1.2194 + break;
1.2195 + }
1.2196 +
1.2197 + // OpParenthesesSubpatternOnceBegin/End
1.2198 + //
1.2199 + // When we are backtracking back out of a capturing subpattern we need
1.2200 + // to clear the start index in the matches output array, to record that
1.2201 + // this subpattern has not been captured.
1.2202 + //
1.2203 + // When backtracking back out of a Greedy quantified subpattern we need
1.2204 + // to catch this, and try running the remainder of the alternative after
1.2205 + // the subpattern again, skipping the parentheses.
1.2206 + //
1.2207 + // Upon backtracking back into a quantified set of parentheses we need to
1.2208 + // check whether we were currently skipping the subpattern. If not, we
1.2209 + // can backtrack into them, if we were we need to either backtrack back
1.2210 + // out of the start of the parentheses, or jump back to the forwards
1.2211 + // matching start, depending of whether the match is Greedy or NonGreedy.
1.2212 + case OpParenthesesSubpatternOnceBegin: {
1.2213 + PatternTerm* term = op.m_term;
1.2214 + ASSERT(term->quantityCount == 1);
1.2215 +
1.2216 + // We only need to backtrack to thispoint if capturing or greedy.
1.2217 + if ((term->capture() && compileMode == IncludeSubpatterns) || term->quantityType == QuantifierGreedy) {
1.2218 + m_backtrackingState.link(this);
1.2219 +
1.2220 + // If capturing, clear the capture (we only need to reset start).
1.2221 + if (term->capture() && compileMode == IncludeSubpatterns)
1.2222 + clearSubpatternStart(term->parentheses.subpatternId);
1.2223 +
1.2224 + // If Greedy, jump to the end.
1.2225 + if (term->quantityType == QuantifierGreedy) {
1.2226 + // Clear the flag in the stackframe indicating we ran through the subpattern.
1.2227 + unsigned parenthesesFrameLocation = term->frameLocation;
1.2228 + storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
1.2229 + // Jump to after the parentheses, skipping the subpattern.
1.2230 + jump(m_ops[op.m_nextOp].m_reentry);
1.2231 + // A backtrack from after the parentheses, when skipping the subpattern,
1.2232 + // will jump back to here.
1.2233 + op.m_jumps.link(this);
1.2234 + }
1.2235 +
1.2236 + m_backtrackingState.fallthrough();
1.2237 + }
1.2238 + break;
1.2239 + }
1.2240 + case OpParenthesesSubpatternOnceEnd: {
1.2241 + PatternTerm* term = op.m_term;
1.2242 +
1.2243 + if (term->quantityType != QuantifierFixedCount) {
1.2244 + m_backtrackingState.link(this);
1.2245 +
1.2246 + // Check whether we should backtrack back into the parentheses, or if we
1.2247 + // are currently in a state where we had skipped over the subpattern
1.2248 + // (in which case the flag value on the stack will be -1).
1.2249 + unsigned parenthesesFrameLocation = term->frameLocation;
1.2250 + Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, parenthesesFrameLocation * sizeof(void*)), TrustedImm32(-1));
1.2251 +
1.2252 + if (term->quantityType == QuantifierGreedy) {
1.2253 + // For Greedy parentheses, we skip after having already tried going
1.2254 + // through the subpattern, so if we get here we're done.
1.2255 + YarrOp& beginOp = m_ops[op.m_previousOp];
1.2256 + beginOp.m_jumps.append(hadSkipped);
1.2257 + } else {
1.2258 + // For NonGreedy parentheses, we try skipping the subpattern first,
1.2259 + // so if we get here we need to try running through the subpattern
1.2260 + // next. Jump back to the start of the parentheses in the forwards
1.2261 + // matching path.
1.2262 + ASSERT(term->quantityType == QuantifierNonGreedy);
1.2263 + YarrOp& beginOp = m_ops[op.m_previousOp];
1.2264 + hadSkipped.linkTo(beginOp.m_reentry, this);
1.2265 + }
1.2266 +
1.2267 + m_backtrackingState.fallthrough();
1.2268 + }
1.2269 +
1.2270 + m_backtrackingState.append(op.m_jumps);
1.2271 + break;
1.2272 + }
1.2273 +
1.2274 + // OpParenthesesSubpatternTerminalBegin/End
1.2275 + //
1.2276 + // Terminal subpatterns will always match - there is nothing after them to
1.2277 + // force a backtrack, and they have a minimum count of 0, and as such will
1.2278 + // always produce an acceptable result.
1.2279 + case OpParenthesesSubpatternTerminalBegin: {
1.2280 + // We will backtrack to this point once the subpattern cannot match any
1.2281 + // more. Since no match is accepted as a successful match (we are Greedy
1.2282 + // quantified with a minimum of zero) jump back to the forwards matching
1.2283 + // path at the end.
1.2284 + YarrOp& endOp = m_ops[op.m_nextOp];
1.2285 + m_backtrackingState.linkTo(endOp.m_reentry, this);
1.2286 + break;
1.2287 + }
1.2288 + case OpParenthesesSubpatternTerminalEnd:
1.2289 + // We should never be backtracking to here (hence the 'terminal' in the name).
1.2290 + ASSERT(m_backtrackingState.isEmpty());
1.2291 + m_backtrackingState.append(op.m_jumps);
1.2292 + break;
1.2293 +
1.2294 + // OpParentheticalAssertionBegin/End
1.2295 + case OpParentheticalAssertionBegin: {
1.2296 + PatternTerm* term = op.m_term;
1.2297 + YarrOp& endOp = m_ops[op.m_nextOp];
1.2298 +
1.2299 + // We need to handle the backtracks upon backtracking back out
1.2300 + // of a parenthetical assertion if either we need to correct
1.2301 + // the input index, or the assertion was inverted.
1.2302 + if (op.m_checkAdjust || term->invert()) {
1.2303 + m_backtrackingState.link(this);
1.2304 +
1.2305 + if (op.m_checkAdjust)
1.2306 + add32(Imm32(op.m_checkAdjust), index);
1.2307 +
1.2308 + // In an inverted assertion failure to match the subpattern
1.2309 + // is treated as a successful match - jump to the end of the
1.2310 + // subpattern. We already have adjusted the input position
1.2311 + // back to that before the assertion, which is correct.
1.2312 + if (term->invert())
1.2313 + jump(endOp.m_reentry);
1.2314 +
1.2315 + m_backtrackingState.fallthrough();
1.2316 + }
1.2317 +
1.2318 + // The End node's jump list will contain any backtracks into
1.2319 + // the end of the assertion. Also, if inverted, we will have
1.2320 + // added the failure caused by a successful match to this.
1.2321 + m_backtrackingState.append(endOp.m_jumps);
1.2322 +
1.2323 + m_checked += op.m_checkAdjust;
1.2324 + break;
1.2325 + }
1.2326 + case OpParentheticalAssertionEnd: {
1.2327 + // FIXME: We should really be clearing any nested subpattern
1.2328 + // matches on bailing out from after the pattern. Firefox has
1.2329 + // this bug too (presumably because they use YARR!)
1.2330 +
1.2331 + // Never backtrack into an assertion; later failures bail to before the begin.
1.2332 + m_backtrackingState.takeBacktracksToJumpList(op.m_jumps, this);
1.2333 +
1.2334 + YarrOp& lastOp = m_ops[op.m_previousOp];
1.2335 + m_checked -= lastOp.m_checkAdjust;
1.2336 + break;
1.2337 + }
1.2338 +
1.2339 + case OpMatchFailed:
1.2340 + break;
1.2341 + }
1.2342 +
1.2343 + } while (opIndex);
1.2344 +
1.2345 + return true;
1.2346 + }
1.2347 +
1.2348 + // Compilation methods:
1.2349 + // ====================
1.2350 +
1.2351 + // opCompileParenthesesSubpattern
1.2352 + // Emits ops for a subpattern (set of parentheses). These consist
1.2353 + // of a set of alternatives wrapped in an outer set of nodes for
1.2354 + // the parentheses.
1.2355 + // Supported types of parentheses are 'Once' (quantityCount == 1)
1.2356 + // and 'Terminal' (non-capturing parentheses quantified as greedy
1.2357 + // and infinite).
1.2358 + // Alternatives will use the 'Simple' set of ops if either the
1.2359 + // subpattern is terminal (in which case we will never need to
1.2360 + // backtrack), or if the subpattern only contains one alternative.
1.2361 + void opCompileParenthesesSubpattern(PatternTerm* term)
1.2362 + {
1.2363 + YarrOpCode parenthesesBeginOpCode;
1.2364 + YarrOpCode parenthesesEndOpCode;
1.2365 + YarrOpCode alternativeBeginOpCode = OpSimpleNestedAlternativeBegin;
1.2366 + YarrOpCode alternativeNextOpCode = OpSimpleNestedAlternativeNext;
1.2367 + YarrOpCode alternativeEndOpCode = OpSimpleNestedAlternativeEnd;
1.2368 +
1.2369 + // We can currently only compile quantity 1 subpatterns that are
1.2370 + // not copies. We generate a copy in the case of a range quantifier,
1.2371 + // e.g. /(?:x){3,9}/, or /(?:x)+/ (These are effectively expanded to
1.2372 + // /(?:x){3,3}(?:x){0,6}/ and /(?:x)(?:x)*/ repectively). The problem
1.2373 + // comes where the subpattern is capturing, in which case we would
1.2374 + // need to restore the capture from the first subpattern upon a
1.2375 + // failure in the second.
1.2376 + if (term->quantityCount == 1 && !term->parentheses.isCopy) {
1.2377 + // Select the 'Once' nodes.
1.2378 + parenthesesBeginOpCode = OpParenthesesSubpatternOnceBegin;
1.2379 + parenthesesEndOpCode = OpParenthesesSubpatternOnceEnd;
1.2380 +
1.2381 + // If there is more than one alternative we cannot use the 'simple' nodes.
1.2382 + if (term->parentheses.disjunction->m_alternatives.size() != 1) {
1.2383 + alternativeBeginOpCode = OpNestedAlternativeBegin;
1.2384 + alternativeNextOpCode = OpNestedAlternativeNext;
1.2385 + alternativeEndOpCode = OpNestedAlternativeEnd;
1.2386 + }
1.2387 + } else if (term->parentheses.isTerminal) {
1.2388 + // Terminal groups are optimized on the assumption that matching will never
1.2389 + // backtrack into the terminal group. But this is false if there is more
1.2390 + // than one alternative and one of the alternatives can match empty. In that
1.2391 + // case, the empty match is counted as a failure, so we would need to backtrack.
1.2392 + // The backtracking code doesn't handle this case correctly, so we fall back
1.2393 + // to the interpreter.
1.2394 + Vector<PatternAlternative*>& alternatives = term->parentheses.disjunction->m_alternatives;
1.2395 + if (alternatives.size() != 1) {
1.2396 + for (unsigned i = 0; i < alternatives.size(); ++i) {
1.2397 + if (alternatives[i]->m_minimumSize == 0) {
1.2398 + m_shouldFallBack = true;
1.2399 + return;
1.2400 + }
1.2401 + }
1.2402 + }
1.2403 +
1.2404 + // Select the 'Terminal' nodes.
1.2405 + parenthesesBeginOpCode = OpParenthesesSubpatternTerminalBegin;
1.2406 + parenthesesEndOpCode = OpParenthesesSubpatternTerminalEnd;
1.2407 + } else {
1.2408 + // This subpattern is not supported by the JIT.
1.2409 + m_shouldFallBack = true;
1.2410 + return;
1.2411 + }
1.2412 +
1.2413 + size_t parenBegin = m_ops.size();
1.2414 + m_ops.append(parenthesesBeginOpCode);
1.2415 +
1.2416 + m_ops.append(alternativeBeginOpCode);
1.2417 + m_ops.last().m_previousOp = notFound;
1.2418 + m_ops.last().m_term = term;
1.2419 + Vector<PatternAlternative*>& alternatives = term->parentheses.disjunction->m_alternatives;
1.2420 + for (unsigned i = 0; i < alternatives.size(); ++i) {
1.2421 + size_t lastOpIndex = m_ops.size() - 1;
1.2422 +
1.2423 + PatternAlternative* nestedAlternative = alternatives[i];
1.2424 + opCompileAlternative(nestedAlternative);
1.2425 +
1.2426 + size_t thisOpIndex = m_ops.size();
1.2427 + m_ops.append(YarrOp(alternativeNextOpCode));
1.2428 +
1.2429 + YarrOp& lastOp = m_ops[lastOpIndex];
1.2430 + YarrOp& thisOp = m_ops[thisOpIndex];
1.2431 +
1.2432 + lastOp.m_alternative = nestedAlternative;
1.2433 + lastOp.m_nextOp = thisOpIndex;
1.2434 + thisOp.m_previousOp = lastOpIndex;
1.2435 + thisOp.m_term = term;
1.2436 + }
1.2437 + YarrOp& lastOp = m_ops.last();
1.2438 + ASSERT(lastOp.m_op == alternativeNextOpCode);
1.2439 + lastOp.m_op = alternativeEndOpCode;
1.2440 + lastOp.m_alternative = 0;
1.2441 + lastOp.m_nextOp = notFound;
1.2442 +
1.2443 + size_t parenEnd = m_ops.size();
1.2444 + m_ops.append(parenthesesEndOpCode);
1.2445 +
1.2446 + m_ops[parenBegin].m_term = term;
1.2447 + m_ops[parenBegin].m_previousOp = notFound;
1.2448 + m_ops[parenBegin].m_nextOp = parenEnd;
1.2449 + m_ops[parenEnd].m_term = term;
1.2450 + m_ops[parenEnd].m_previousOp = parenBegin;
1.2451 + m_ops[parenEnd].m_nextOp = notFound;
1.2452 + }
1.2453 +
1.2454 + // opCompileParentheticalAssertion
1.2455 + // Emits ops for a parenthetical assertion. These consist of an
1.2456 + // OpSimpleNestedAlternativeBegin/Next/End set of nodes wrapping
1.2457 + // the alternatives, with these wrapped by an outer pair of
1.2458 + // OpParentheticalAssertionBegin/End nodes.
1.2459 + // We can always use the OpSimpleNestedAlternative nodes in the
1.2460 + // case of parenthetical assertions since these only ever match
1.2461 + // once, and will never backtrack back into the assertion.
1.2462 + void opCompileParentheticalAssertion(PatternTerm* term)
1.2463 + {
1.2464 + size_t parenBegin = m_ops.size();
1.2465 + m_ops.append(OpParentheticalAssertionBegin);
1.2466 +
1.2467 + m_ops.append(OpSimpleNestedAlternativeBegin);
1.2468 + m_ops.last().m_previousOp = notFound;
1.2469 + m_ops.last().m_term = term;
1.2470 + Vector<PatternAlternative*>& alternatives = term->parentheses.disjunction->m_alternatives;
1.2471 + for (unsigned i = 0; i < alternatives.size(); ++i) {
1.2472 + size_t lastOpIndex = m_ops.size() - 1;
1.2473 +
1.2474 + PatternAlternative* nestedAlternative = alternatives[i];
1.2475 + opCompileAlternative(nestedAlternative);
1.2476 +
1.2477 + size_t thisOpIndex = m_ops.size();
1.2478 + m_ops.append(YarrOp(OpSimpleNestedAlternativeNext));
1.2479 +
1.2480 + YarrOp& lastOp = m_ops[lastOpIndex];
1.2481 + YarrOp& thisOp = m_ops[thisOpIndex];
1.2482 +
1.2483 + lastOp.m_alternative = nestedAlternative;
1.2484 + lastOp.m_nextOp = thisOpIndex;
1.2485 + thisOp.m_previousOp = lastOpIndex;
1.2486 + thisOp.m_term = term;
1.2487 + }
1.2488 + YarrOp& lastOp = m_ops.last();
1.2489 + ASSERT(lastOp.m_op == OpSimpleNestedAlternativeNext);
1.2490 + lastOp.m_op = OpSimpleNestedAlternativeEnd;
1.2491 + lastOp.m_alternative = 0;
1.2492 + lastOp.m_nextOp = notFound;
1.2493 +
1.2494 + size_t parenEnd = m_ops.size();
1.2495 + m_ops.append(OpParentheticalAssertionEnd);
1.2496 +
1.2497 + m_ops[parenBegin].m_term = term;
1.2498 + m_ops[parenBegin].m_previousOp = notFound;
1.2499 + m_ops[parenBegin].m_nextOp = parenEnd;
1.2500 + m_ops[parenEnd].m_term = term;
1.2501 + m_ops[parenEnd].m_previousOp = parenBegin;
1.2502 + m_ops[parenEnd].m_nextOp = notFound;
1.2503 + }
1.2504 +
1.2505 + // opCompileAlternative
1.2506 + // Called to emit nodes for all terms in an alternative.
1.2507 + void opCompileAlternative(PatternAlternative* alternative)
1.2508 + {
1.2509 + optimizeAlternative(alternative);
1.2510 +
1.2511 + for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
1.2512 + PatternTerm* term = &alternative->m_terms[i];
1.2513 +
1.2514 + switch (term->type) {
1.2515 + case PatternTerm::TypeParenthesesSubpattern:
1.2516 + opCompileParenthesesSubpattern(term);
1.2517 + break;
1.2518 +
1.2519 + case PatternTerm::TypeParentheticalAssertion:
1.2520 + opCompileParentheticalAssertion(term);
1.2521 + break;
1.2522 +
1.2523 + default:
1.2524 + m_ops.append(term);
1.2525 + }
1.2526 + }
1.2527 + }
1.2528 +
1.2529 + // opCompileBody
1.2530 + // This method compiles the body disjunction of the regular expression.
1.2531 + // The body consists of two sets of alternatives - zero or more 'once
1.2532 + // through' (BOL anchored) alternatives, followed by zero or more
1.2533 + // repeated alternatives.
1.2534 + // For each of these two sets of alteratives, if not empty they will be
1.2535 + // wrapped in a set of OpBodyAlternativeBegin/Next/End nodes (with the
1.2536 + // 'begin' node referencing the first alternative, and 'next' nodes
1.2537 + // referencing any further alternatives. The begin/next/end nodes are
1.2538 + // linked together in a doubly linked list. In the case of repeating
1.2539 + // alternatives, the end node is also linked back to the beginning.
1.2540 + // If no repeating alternatives exist, then a OpMatchFailed node exists
1.2541 + // to return the failing result.
1.2542 + void opCompileBody(PatternDisjunction* disjunction)
1.2543 + {
1.2544 + Vector<PatternAlternative*>& alternatives = disjunction->m_alternatives;
1.2545 + size_t currentAlternativeIndex = 0;
1.2546 +
1.2547 + // Emit the 'once through' alternatives.
1.2548 + if (alternatives.size() && alternatives[0]->onceThrough()) {
1.2549 + m_ops.append(YarrOp(OpBodyAlternativeBegin));
1.2550 + m_ops.last().m_previousOp = notFound;
1.2551 +
1.2552 + do {
1.2553 + size_t lastOpIndex = m_ops.size() - 1;
1.2554 + PatternAlternative* alternative = alternatives[currentAlternativeIndex];
1.2555 + opCompileAlternative(alternative);
1.2556 +
1.2557 + size_t thisOpIndex = m_ops.size();
1.2558 + m_ops.append(YarrOp(OpBodyAlternativeNext));
1.2559 +
1.2560 + YarrOp& lastOp = m_ops[lastOpIndex];
1.2561 + YarrOp& thisOp = m_ops[thisOpIndex];
1.2562 +
1.2563 + lastOp.m_alternative = alternative;
1.2564 + lastOp.m_nextOp = thisOpIndex;
1.2565 + thisOp.m_previousOp = lastOpIndex;
1.2566 +
1.2567 + ++currentAlternativeIndex;
1.2568 + } while (currentAlternativeIndex < alternatives.size() && alternatives[currentAlternativeIndex]->onceThrough());
1.2569 +
1.2570 + YarrOp& lastOp = m_ops.last();
1.2571 +
1.2572 + ASSERT(lastOp.m_op == OpBodyAlternativeNext);
1.2573 + lastOp.m_op = OpBodyAlternativeEnd;
1.2574 + lastOp.m_alternative = 0;
1.2575 + lastOp.m_nextOp = notFound;
1.2576 + }
1.2577 +
1.2578 + if (currentAlternativeIndex == alternatives.size()) {
1.2579 + m_ops.append(YarrOp(OpMatchFailed));
1.2580 + return;
1.2581 + }
1.2582 +
1.2583 + // Emit the repeated alternatives.
1.2584 + size_t repeatLoop = m_ops.size();
1.2585 + m_ops.append(YarrOp(OpBodyAlternativeBegin));
1.2586 + m_ops.last().m_previousOp = notFound;
1.2587 + do {
1.2588 + size_t lastOpIndex = m_ops.size() - 1;
1.2589 + PatternAlternative* alternative = alternatives[currentAlternativeIndex];
1.2590 + ASSERT(!alternative->onceThrough());
1.2591 + opCompileAlternative(alternative);
1.2592 +
1.2593 + size_t thisOpIndex = m_ops.size();
1.2594 + m_ops.append(YarrOp(OpBodyAlternativeNext));
1.2595 +
1.2596 + YarrOp& lastOp = m_ops[lastOpIndex];
1.2597 + YarrOp& thisOp = m_ops[thisOpIndex];
1.2598 +
1.2599 + lastOp.m_alternative = alternative;
1.2600 + lastOp.m_nextOp = thisOpIndex;
1.2601 + thisOp.m_previousOp = lastOpIndex;
1.2602 +
1.2603 + ++currentAlternativeIndex;
1.2604 + } while (currentAlternativeIndex < alternatives.size());
1.2605 + YarrOp& lastOp = m_ops.last();
1.2606 + ASSERT(lastOp.m_op == OpBodyAlternativeNext);
1.2607 + lastOp.m_op = OpBodyAlternativeEnd;
1.2608 + lastOp.m_alternative = 0;
1.2609 + lastOp.m_nextOp = repeatLoop;
1.2610 + }
1.2611 +
1.2612 + void generateEnter()
1.2613 + {
1.2614 +#if WTF_CPU_X86_64
1.2615 + push(X86Registers::ebp);
1.2616 + move(stackPointerRegister, X86Registers::ebp);
1.2617 + push(X86Registers::ebx);
1.2618 + // The ABI doesn't guarantee the upper bits are zero on unsigned arguments, so clear them ourselves.
1.2619 + zeroExtend32ToPtr(index, index);
1.2620 + zeroExtend32ToPtr(length, length);
1.2621 +#elif WTF_CPU_X86
1.2622 + push(X86Registers::ebp);
1.2623 + move(stackPointerRegister, X86Registers::ebp);
1.2624 + // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
1.2625 + push(X86Registers::ebx);
1.2626 + push(X86Registers::edi);
1.2627 + push(X86Registers::esi);
1.2628 + // load output into edi (2 = saved ebp + return address).
1.2629 +# if WTF_COMPILER_MSVC || WTF_COMPILER_SUNCC
1.2630 + loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
1.2631 + loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
1.2632 + loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
1.2633 + if (compileMode == IncludeSubpatterns)
1.2634 + loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
1.2635 +# else
1.2636 + if (compileMode == IncludeSubpatterns)
1.2637 + loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
1.2638 +# endif
1.2639 +#elif WTF_CPU_ARM
1.2640 + push(ARMRegisters::r4);
1.2641 + push(ARMRegisters::r5);
1.2642 + push(ARMRegisters::r6);
1.2643 +# if WTF_CPU_ARM_TRADITIONAL
1.2644 + push(ARMRegisters::r8); // scratch register
1.2645 +# endif
1.2646 + if (compileMode == IncludeSubpatterns)
1.2647 + move(ARMRegisters::r3, output);
1.2648 +#elif WTF_CPU_SH4
1.2649 + push(SH4Registers::r11);
1.2650 + push(SH4Registers::r13);
1.2651 +#elif WTF_CPU_SPARC
1.2652 + save(Imm32(-m_pattern.m_body->m_callFrameSize * sizeof(void*)));
1.2653 +#elif WTF_CPU_MIPS
1.2654 + // Do nothing.
1.2655 +#endif
1.2656 + }
1.2657 +
1.2658 + void generateReturn()
1.2659 + {
1.2660 +#if WTF_CPU_X86_64
1.2661 + pop(X86Registers::ebx);
1.2662 + pop(X86Registers::ebp);
1.2663 +#elif WTF_CPU_X86
1.2664 + pop(X86Registers::esi);
1.2665 + pop(X86Registers::edi);
1.2666 + pop(X86Registers::ebx);
1.2667 + pop(X86Registers::ebp);
1.2668 +#elif WTF_CPU_ARM
1.2669 +# if WTF_CPU_ARM_TRADITIONAL
1.2670 + pop(ARMRegisters::r8); // scratch register
1.2671 +# endif
1.2672 + pop(ARMRegisters::r6);
1.2673 + pop(ARMRegisters::r5);
1.2674 + pop(ARMRegisters::r4);
1.2675 +#elif WTF_CPU_SH4
1.2676 + pop(SH4Registers::r13);
1.2677 + pop(SH4Registers::r11);
1.2678 +#elif WTF_CPU_SPARC
1.2679 + ret_and_restore();
1.2680 + return;
1.2681 +#elif WTF_CPU_MIPS
1.2682 + // Do nothing
1.2683 +#endif
1.2684 + ret();
1.2685 + }
1.2686 +
1.2687 +public:
1.2688 + YarrGenerator(YarrPattern& pattern, YarrCharSize charSize)
1.2689 + : m_pattern(pattern)
1.2690 + , m_charSize(charSize)
1.2691 + , m_charScale(m_charSize == Char8 ? TimesOne: TimesTwo)
1.2692 + , m_shouldFallBack(false)
1.2693 + , m_checked(0)
1.2694 + {
1.2695 + }
1.2696 +
1.2697 + void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject)
1.2698 + {
1.2699 + generateEnter();
1.2700 +
1.2701 + Jump hasInput = checkInput();
1.2702 +#if WTF_CPU_X86_64
1.2703 + move(TrustedImm32(int(WTF::notFound)), returnRegister);
1.2704 +#else
1.2705 + move(TrustedImmPtr((void*)WTF::notFound), returnRegister);
1.2706 + move(TrustedImm32(0), returnRegister2);
1.2707 +#endif
1.2708 + generateReturn();
1.2709 + hasInput.link(this);
1.2710 +
1.2711 + if (compileMode == IncludeSubpatterns) {
1.2712 + for (unsigned i = 0; i < m_pattern.m_numSubpatterns + 1; ++i)
1.2713 + store32(TrustedImm32(-1), Address(output, (i << 1) * sizeof(int)));
1.2714 + }
1.2715 +
1.2716 + if (!m_pattern.m_body->m_hasFixedSize)
1.2717 + setMatchStart(index);
1.2718 +
1.2719 + initCallFrame();
1.2720 +
1.2721 + // Compile the pattern to the internal 'YarrOp' representation.
1.2722 + opCompileBody(m_pattern.m_body);
1.2723 +
1.2724 + // If we encountered anything we can't handle in the JIT code
1.2725 + // (e.g. backreferences) then return early.
1.2726 + if (m_shouldFallBack) {
1.2727 + jitObject.setFallBack(true);
1.2728 + return;
1.2729 + }
1.2730 +
1.2731 + if (!generate() || !backtrack()) {
1.2732 + jitObject.setFallBack(true);
1.2733 + return;
1.2734 + }
1.2735 +
1.2736 + // Link & finalize the code.
1.2737 + ExecutablePool *pool;
1.2738 + bool ok;
1.2739 + LinkBuffer linkBuffer(this, globalData->regexAllocator, &pool, &ok, REGEXP_CODE);
1.2740 +
1.2741 + // Attempt to detect OOM during linkBuffer creation.
1.2742 + if (linkBuffer.unsafeCode() == nullptr) {
1.2743 + jitObject.setFallBack(true);
1.2744 + return;
1.2745 + }
1.2746 +
1.2747 + m_backtrackingState.linkDataLabels(linkBuffer);
1.2748 +
1.2749 + if (compileMode == MatchOnly) {
1.2750 +#if YARR_8BIT_CHAR_SUPPORT
1.2751 + if (m_charSize == Char8)
1.2752 + jitObject.set8BitCodeMatchOnly(linkBuffer.finalizeCode());
1.2753 + else
1.2754 +#endif
1.2755 + jitObject.set16BitCodeMatchOnly(linkBuffer.finalizeCode());
1.2756 + } else {
1.2757 +#if YARR_8BIT_CHAR_SUPPORT
1.2758 + if (m_charSize == Char8)
1.2759 + jitObject.set8BitCode(linkBuffer.finalizeCode());
1.2760 + else
1.2761 +#endif
1.2762 + jitObject.set16BitCode(linkBuffer.finalizeCode());
1.2763 + }
1.2764 + jitObject.setFallBack(m_shouldFallBack);
1.2765 + }
1.2766 +
1.2767 +private:
1.2768 + YarrPattern& m_pattern;
1.2769 +
1.2770 + YarrCharSize m_charSize;
1.2771 +
1.2772 + Scale m_charScale;
1.2773 +
1.2774 + // Used to detect regular expression constructs that are not currently
1.2775 + // supported in the JIT; fall back to the interpreter when this is detected.
1.2776 + bool m_shouldFallBack;
1.2777 +
1.2778 + // The regular expression expressed as a linear sequence of operations.
1.2779 + Vector<YarrOp, 128> m_ops;
1.2780 +
1.2781 + // This records the current input offset being applied due to the current
1.2782 + // set of alternatives we are nested within. E.g. when matching the
1.2783 + // character 'b' within the regular expression /abc/, we will know that
1.2784 + // the minimum size for the alternative is 3, checked upon entry to the
1.2785 + // alternative, and that 'b' is at offset 1 from the start, and as such
1.2786 + // when matching 'b' we need to apply an offset of -2 to the load.
1.2787 + //
1.2788 + // FIXME: This should go away. Rather than tracking this value throughout
1.2789 + // code generation, we should gather this information up front & store it
1.2790 + // on the YarrOp structure.
1.2791 + int m_checked;
1.2792 +
1.2793 + // This class records state whilst generating the backtracking path of code.
1.2794 + BacktrackingState m_backtrackingState;
1.2795 +};
1.2796 +
1.2797 +void jitCompile(YarrPattern& pattern, YarrCharSize charSize, JSGlobalData* globalData, YarrCodeBlock& jitObject, YarrJITCompileMode mode)
1.2798 +{
1.2799 + if (mode == MatchOnly)
1.2800 + YarrGenerator<MatchOnly>(pattern, charSize).compile(globalData, jitObject);
1.2801 + else
1.2802 + YarrGenerator<IncludeSubpatterns>(pattern, charSize).compile(globalData, jitObject);
1.2803 +}
1.2804 +
1.2805 +}}
1.2806 +
1.2807 +#endif
