| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2012 the V8 project authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #ifndef V8_JSREGEXP_H_ | |
| 6 #define V8_JSREGEXP_H_ | |
| 7 | |
| 8 #include "src/allocation.h" | |
| 9 #include "src/assembler.h" | |
| 10 | |
| 11 namespace v8 { | |
| 12 namespace internal { | |
| 13 | |
| 14 class NodeVisitor; | |
| 15 class RegExpCompiler; | |
| 16 class RegExpMacroAssembler; | |
| 17 class RegExpNode; | |
| 18 class RegExpTree; | |
| 19 class BoyerMooreLookahead; | |
| 20 | |
| 21 class RegExpImpl { | |
| 22 public: | |
| 23 // Whether V8 is compiled with native regexp support or not. | |
| 24 static bool UsesNativeRegExp() { | |
| 25 #ifdef V8_INTERPRETED_REGEXP | |
| 26 return false; | |
| 27 #else | |
| 28 return true; | |
| 29 #endif | |
| 30 } | |
| 31 | |
| 32 // Creates a regular expression literal in the old space. | |
| 33 // This function calls the garbage collector if necessary. | |
| 34 MUST_USE_RESULT static MaybeHandle<Object> CreateRegExpLiteral( | |
| 35 Handle<JSFunction> constructor, | |
| 36 Handle<String> pattern, | |
| 37 Handle<String> flags); | |
| 38 | |
| 39 // Returns a string representation of a regular expression. | |
| 40 // Implements RegExp.prototype.toString, see ECMA-262 section 15.10.6.4. | |
| 41 // This function calls the garbage collector if necessary. | |
| 42 static Handle<String> ToString(Handle<Object> value); | |
| 43 | |
| 44 // Parses the RegExp pattern and prepares the JSRegExp object with | |
| 45 // generic data and choice of implementation - as well as what | |
| 46 // the implementation wants to store in the data field. | |
| 47 // Returns false if compilation fails. | |
| 48 MUST_USE_RESULT static MaybeHandle<Object> Compile(Handle<JSRegExp> re, | |
| 49 Handle<String> pattern, | |
| 50 JSRegExp::Flags flags); | |
| 51 | |
| 52 // See ECMA-262 section 15.10.6.2. | |
| 53 // This function calls the garbage collector if necessary. | |
| 54 MUST_USE_RESULT static MaybeHandle<Object> Exec( | |
| 55 Handle<JSRegExp> regexp, | |
| 56 Handle<String> subject, | |
| 57 int index, | |
| 58 Handle<JSArray> lastMatchInfo); | |
| 59 | |
| 60 // Prepares a JSRegExp object with Irregexp-specific data. | |
| 61 static void IrregexpInitialize(Handle<JSRegExp> re, | |
| 62 Handle<String> pattern, | |
| 63 JSRegExp::Flags flags, | |
| 64 int capture_register_count); | |
| 65 | |
| 66 | |
| 67 static void AtomCompile(Handle<JSRegExp> re, | |
| 68 Handle<String> pattern, | |
| 69 JSRegExp::Flags flags, | |
| 70 Handle<String> match_pattern); | |
| 71 | |
| 72 | |
| 73 static int AtomExecRaw(Handle<JSRegExp> regexp, | |
| 74 Handle<String> subject, | |
| 75 int index, | |
| 76 int32_t* output, | |
| 77 int output_size); | |
| 78 | |
| 79 | |
| 80 static Handle<Object> AtomExec(Handle<JSRegExp> regexp, | |
| 81 Handle<String> subject, | |
| 82 int index, | |
| 83 Handle<JSArray> lastMatchInfo); | |
| 84 | |
| 85 enum IrregexpResult { RE_FAILURE = 0, RE_SUCCESS = 1, RE_EXCEPTION = -1 }; | |
| 86 | |
| 87 // Prepare a RegExp for being executed one or more times (using | |
| 88 // IrregexpExecOnce) on the subject. | |
| 89 // This ensures that the regexp is compiled for the subject, and that | |
| 90 // the subject is flat. | |
| 91 // Returns the number of integer spaces required by IrregexpExecOnce | |
| 92 // as its "registers" argument. If the regexp cannot be compiled, | |
| 93 // an exception is set as pending, and this function returns negative. | |
| 94 static int IrregexpPrepare(Handle<JSRegExp> regexp, | |
| 95 Handle<String> subject); | |
| 96 | |
| 97 // Execute a regular expression on the subject, starting from index. | |
| 98 // If matching succeeds, return the number of matches. This can be larger | |
| 99 // than one in the case of global regular expressions. | |
| 100 // The captures and subcaptures are stored into the registers vector. | |
| 101 // If matching fails, returns RE_FAILURE. | |
| 102 // If execution fails, sets a pending exception and returns RE_EXCEPTION. | |
| 103 static int IrregexpExecRaw(Handle<JSRegExp> regexp, | |
| 104 Handle<String> subject, | |
| 105 int index, | |
| 106 int32_t* output, | |
| 107 int output_size); | |
| 108 | |
| 109 // Execute an Irregexp bytecode pattern. | |
| 110 // On a successful match, the result is a JSArray containing | |
| 111 // captured positions. On a failure, the result is the null value. | |
| 112 // Returns an empty handle in case of an exception. | |
| 113 MUST_USE_RESULT static MaybeHandle<Object> IrregexpExec( | |
| 114 Handle<JSRegExp> regexp, | |
| 115 Handle<String> subject, | |
| 116 int index, | |
| 117 Handle<JSArray> lastMatchInfo); | |
| 118 | |
| 119 // Set last match info. If match is NULL, then setting captures is omitted. | |
| 120 static Handle<JSArray> SetLastMatchInfo(Handle<JSArray> last_match_info, | |
| 121 Handle<String> subject, | |
| 122 int capture_count, | |
| 123 int32_t* match); | |
| 124 | |
| 125 | |
| 126 class GlobalCache { | |
| 127 public: | |
| 128 GlobalCache(Handle<JSRegExp> regexp, | |
| 129 Handle<String> subject, | |
| 130 bool is_global, | |
| 131 Isolate* isolate); | |
| 132 | |
| 133 INLINE(~GlobalCache()); | |
| 134 | |
| 135 // Fetch the next entry in the cache for global regexp match results. | |
| 136 // This does not set the last match info. Upon failure, NULL is returned. | |
| 137 // The cause can be checked with Result(). The previous | |
| 138 // result is still in available in memory when a failure happens. | |
| 139 INLINE(int32_t* FetchNext()); | |
| 140 | |
| 141 INLINE(int32_t* LastSuccessfulMatch()); | |
| 142 | |
| 143 INLINE(bool HasException()) { return num_matches_ < 0; } | |
| 144 | |
| 145 private: | |
| 146 int num_matches_; | |
| 147 int max_matches_; | |
| 148 int current_match_index_; | |
| 149 int registers_per_match_; | |
| 150 // Pointer to the last set of captures. | |
| 151 int32_t* register_array_; | |
| 152 int register_array_size_; | |
| 153 Handle<JSRegExp> regexp_; | |
| 154 Handle<String> subject_; | |
| 155 }; | |
| 156 | |
| 157 | |
| 158 // Array index in the lastMatchInfo array. | |
| 159 static const int kLastCaptureCount = 0; | |
| 160 static const int kLastSubject = 1; | |
| 161 static const int kLastInput = 2; | |
| 162 static const int kFirstCapture = 3; | |
| 163 static const int kLastMatchOverhead = 3; | |
| 164 | |
| 165 // Direct offset into the lastMatchInfo array. | |
| 166 static const int kLastCaptureCountOffset = | |
| 167 FixedArray::kHeaderSize + kLastCaptureCount * kPointerSize; | |
| 168 static const int kLastSubjectOffset = | |
| 169 FixedArray::kHeaderSize + kLastSubject * kPointerSize; | |
| 170 static const int kLastInputOffset = | |
| 171 FixedArray::kHeaderSize + kLastInput * kPointerSize; | |
| 172 static const int kFirstCaptureOffset = | |
| 173 FixedArray::kHeaderSize + kFirstCapture * kPointerSize; | |
| 174 | |
| 175 // Used to access the lastMatchInfo array. | |
| 176 static int GetCapture(FixedArray* array, int index) { | |
| 177 return Smi::cast(array->get(index + kFirstCapture))->value(); | |
| 178 } | |
| 179 | |
| 180 static void SetLastCaptureCount(FixedArray* array, int to) { | |
| 181 array->set(kLastCaptureCount, Smi::FromInt(to)); | |
| 182 } | |
| 183 | |
| 184 static void SetLastSubject(FixedArray* array, String* to) { | |
| 185 array->set(kLastSubject, to); | |
| 186 } | |
| 187 | |
| 188 static void SetLastInput(FixedArray* array, String* to) { | |
| 189 array->set(kLastInput, to); | |
| 190 } | |
| 191 | |
| 192 static void SetCapture(FixedArray* array, int index, int to) { | |
| 193 array->set(index + kFirstCapture, Smi::FromInt(to)); | |
| 194 } | |
| 195 | |
| 196 static int GetLastCaptureCount(FixedArray* array) { | |
| 197 return Smi::cast(array->get(kLastCaptureCount))->value(); | |
| 198 } | |
| 199 | |
| 200 // For acting on the JSRegExp data FixedArray. | |
| 201 static int IrregexpMaxRegisterCount(FixedArray* re); | |
| 202 static void SetIrregexpMaxRegisterCount(FixedArray* re, int value); | |
| 203 static int IrregexpNumberOfCaptures(FixedArray* re); | |
| 204 static int IrregexpNumberOfRegisters(FixedArray* re); | |
| 205 static ByteArray* IrregexpByteCode(FixedArray* re, bool is_one_byte); | |
| 206 static Code* IrregexpNativeCode(FixedArray* re, bool is_one_byte); | |
| 207 | |
| 208 // Limit the space regexps take up on the heap. In order to limit this we | |
| 209 // would like to keep track of the amount of regexp code on the heap. This | |
| 210 // is not tracked, however. As a conservative approximation we track the | |
| 211 // total regexp code compiled including code that has subsequently been freed | |
| 212 // and the total executable memory at any point. | |
| 213 static const int kRegExpExecutableMemoryLimit = 16 * MB; | |
| 214 static const int kRegExpCompiledLimit = 1 * MB; | |
| 215 static const int kRegExpTooLargeToOptimize = 20 * KB; | |
| 216 | |
| 217 private: | |
| 218 static bool CompileIrregexp(Handle<JSRegExp> re, | |
| 219 Handle<String> sample_subject, bool is_one_byte); | |
| 220 static inline bool EnsureCompiledIrregexp(Handle<JSRegExp> re, | |
| 221 Handle<String> sample_subject, | |
| 222 bool is_one_byte); | |
| 223 }; | |
| 224 | |
| 225 | |
| 226 // Represents the location of one element relative to the intersection of | |
| 227 // two sets. Corresponds to the four areas of a Venn diagram. | |
| 228 enum ElementInSetsRelation { | |
| 229 kInsideNone = 0, | |
| 230 kInsideFirst = 1, | |
| 231 kInsideSecond = 2, | |
| 232 kInsideBoth = 3 | |
| 233 }; | |
| 234 | |
| 235 | |
| 236 // Represents code units in the range from from_ to to_, both ends are | |
| 237 // inclusive. | |
| 238 class CharacterRange { | |
| 239 public: | |
| 240 CharacterRange() : from_(0), to_(0) { } | |
| 241 // For compatibility with the CHECK_OK macro | |
| 242 CharacterRange(void* null) { DCHECK_NULL(null); } // NOLINT | |
| 243 CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { } | |
| 244 static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges, | |
| 245 Zone* zone); | |
| 246 static Vector<const int> GetWordBounds(); | |
| 247 static inline CharacterRange Singleton(uc16 value) { | |
| 248 return CharacterRange(value, value); | |
| 249 } | |
| 250 static inline CharacterRange Range(uc16 from, uc16 to) { | |
| 251 DCHECK(from <= to); | |
| 252 return CharacterRange(from, to); | |
| 253 } | |
| 254 static inline CharacterRange Everything() { | |
| 255 return CharacterRange(0, 0xFFFF); | |
| 256 } | |
| 257 bool Contains(uc16 i) { return from_ <= i && i <= to_; } | |
| 258 uc16 from() const { return from_; } | |
| 259 void set_from(uc16 value) { from_ = value; } | |
| 260 uc16 to() const { return to_; } | |
| 261 void set_to(uc16 value) { to_ = value; } | |
| 262 bool is_valid() { return from_ <= to_; } | |
| 263 bool IsEverything(uc16 max) { return from_ == 0 && to_ >= max; } | |
| 264 bool IsSingleton() { return (from_ == to_); } | |
| 265 void AddCaseEquivalents(Isolate* isolate, Zone* zone, | |
| 266 ZoneList<CharacterRange>* ranges, bool is_one_byte); | |
| 267 static void Split(ZoneList<CharacterRange>* base, | |
| 268 Vector<const int> overlay, | |
| 269 ZoneList<CharacterRange>** included, | |
| 270 ZoneList<CharacterRange>** excluded, | |
| 271 Zone* zone); | |
| 272 // Whether a range list is in canonical form: Ranges ordered by from value, | |
| 273 // and ranges non-overlapping and non-adjacent. | |
| 274 static bool IsCanonical(ZoneList<CharacterRange>* ranges); | |
| 275 // Convert range list to canonical form. The characters covered by the ranges | |
| 276 // will still be the same, but no character is in more than one range, and | |
| 277 // adjacent ranges are merged. The resulting list may be shorter than the | |
| 278 // original, but cannot be longer. | |
| 279 static void Canonicalize(ZoneList<CharacterRange>* ranges); | |
| 280 // Negate the contents of a character range in canonical form. | |
| 281 static void Negate(ZoneList<CharacterRange>* src, | |
| 282 ZoneList<CharacterRange>* dst, | |
| 283 Zone* zone); | |
| 284 static const int kStartMarker = (1 << 24); | |
| 285 static const int kPayloadMask = (1 << 24) - 1; | |
| 286 | |
| 287 private: | |
| 288 uc16 from_; | |
| 289 uc16 to_; | |
| 290 }; | |
| 291 | |
| 292 | |
| 293 // A set of unsigned integers that behaves especially well on small | |
| 294 // integers (< 32). May do zone-allocation. | |
| 295 class OutSet: public ZoneObject { | |
| 296 public: | |
| 297 OutSet() : first_(0), remaining_(NULL), successors_(NULL) { } | |
| 298 OutSet* Extend(unsigned value, Zone* zone); | |
| 299 bool Get(unsigned value) const; | |
| 300 static const unsigned kFirstLimit = 32; | |
| 301 | |
| 302 private: | |
| 303 // Destructively set a value in this set. In most cases you want | |
| 304 // to use Extend instead to ensure that only one instance exists | |
| 305 // that contains the same values. | |
| 306 void Set(unsigned value, Zone* zone); | |
| 307 | |
| 308 // The successors are a list of sets that contain the same values | |
| 309 // as this set and the one more value that is not present in this | |
| 310 // set. | |
| 311 ZoneList<OutSet*>* successors(Zone* zone) { return successors_; } | |
| 312 | |
| 313 OutSet(uint32_t first, ZoneList<unsigned>* remaining) | |
| 314 : first_(first), remaining_(remaining), successors_(NULL) { } | |
| 315 uint32_t first_; | |
| 316 ZoneList<unsigned>* remaining_; | |
| 317 ZoneList<OutSet*>* successors_; | |
| 318 friend class Trace; | |
| 319 }; | |
| 320 | |
| 321 | |
| 322 // A mapping from integers, specified as ranges, to a set of integers. | |
| 323 // Used for mapping character ranges to choices. | |
| 324 class DispatchTable : public ZoneObject { | |
| 325 public: | |
| 326 explicit DispatchTable(Zone* zone) : tree_(zone) { } | |
| 327 | |
| 328 class Entry { | |
| 329 public: | |
| 330 Entry() : from_(0), to_(0), out_set_(NULL) { } | |
| 331 Entry(uc16 from, uc16 to, OutSet* out_set) | |
| 332 : from_(from), to_(to), out_set_(out_set) { } | |
| 333 uc16 from() { return from_; } | |
| 334 uc16 to() { return to_; } | |
| 335 void set_to(uc16 value) { to_ = value; } | |
| 336 void AddValue(int value, Zone* zone) { | |
| 337 out_set_ = out_set_->Extend(value, zone); | |
| 338 } | |
| 339 OutSet* out_set() { return out_set_; } | |
| 340 private: | |
| 341 uc16 from_; | |
| 342 uc16 to_; | |
| 343 OutSet* out_set_; | |
| 344 }; | |
| 345 | |
| 346 class Config { | |
| 347 public: | |
| 348 typedef uc16 Key; | |
| 349 typedef Entry Value; | |
| 350 static const uc16 kNoKey; | |
| 351 static const Entry NoValue() { return Value(); } | |
| 352 static inline int Compare(uc16 a, uc16 b) { | |
| 353 if (a == b) | |
| 354 return 0; | |
| 355 else if (a < b) | |
| 356 return -1; | |
| 357 else | |
| 358 return 1; | |
| 359 } | |
| 360 }; | |
| 361 | |
| 362 void AddRange(CharacterRange range, int value, Zone* zone); | |
| 363 OutSet* Get(uc16 value); | |
| 364 void Dump(); | |
| 365 | |
| 366 template <typename Callback> | |
| 367 void ForEach(Callback* callback) { | |
| 368 return tree()->ForEach(callback); | |
| 369 } | |
| 370 | |
| 371 private: | |
| 372 // There can't be a static empty set since it allocates its | |
| 373 // successors in a zone and caches them. | |
| 374 OutSet* empty() { return &empty_; } | |
| 375 OutSet empty_; | |
| 376 ZoneSplayTree<Config>* tree() { return &tree_; } | |
| 377 ZoneSplayTree<Config> tree_; | |
| 378 }; | |
| 379 | |
| 380 | |
| 381 #define FOR_EACH_NODE_TYPE(VISIT) \ | |
| 382 VISIT(End) \ | |
| 383 VISIT(Action) \ | |
| 384 VISIT(Choice) \ | |
| 385 VISIT(BackReference) \ | |
| 386 VISIT(Assertion) \ | |
| 387 VISIT(Text) | |
| 388 | |
| 389 | |
| 390 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \ | |
| 391 VISIT(Disjunction) \ | |
| 392 VISIT(Alternative) \ | |
| 393 VISIT(Assertion) \ | |
| 394 VISIT(CharacterClass) \ | |
| 395 VISIT(Atom) \ | |
| 396 VISIT(Quantifier) \ | |
| 397 VISIT(Capture) \ | |
| 398 VISIT(Lookahead) \ | |
| 399 VISIT(BackReference) \ | |
| 400 VISIT(Empty) \ | |
| 401 VISIT(Text) | |
| 402 | |
| 403 | |
| 404 #define FORWARD_DECLARE(Name) class RegExp##Name; | |
| 405 FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE) | |
| 406 #undef FORWARD_DECLARE | |
| 407 | |
| 408 | |
| 409 class TextElement final BASE_EMBEDDED { | |
| 410 public: | |
| 411 enum TextType { | |
| 412 ATOM, | |
| 413 CHAR_CLASS | |
| 414 }; | |
| 415 | |
| 416 static TextElement Atom(RegExpAtom* atom); | |
| 417 static TextElement CharClass(RegExpCharacterClass* char_class); | |
| 418 | |
| 419 int cp_offset() const { return cp_offset_; } | |
| 420 void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; } | |
| 421 int length() const; | |
| 422 | |
| 423 TextType text_type() const { return text_type_; } | |
| 424 | |
| 425 RegExpTree* tree() const { return tree_; } | |
| 426 | |
| 427 RegExpAtom* atom() const { | |
| 428 DCHECK(text_type() == ATOM); | |
| 429 return reinterpret_cast<RegExpAtom*>(tree()); | |
| 430 } | |
| 431 | |
| 432 RegExpCharacterClass* char_class() const { | |
| 433 DCHECK(text_type() == CHAR_CLASS); | |
| 434 return reinterpret_cast<RegExpCharacterClass*>(tree()); | |
| 435 } | |
| 436 | |
| 437 private: | |
| 438 TextElement(TextType text_type, RegExpTree* tree) | |
| 439 : cp_offset_(-1), text_type_(text_type), tree_(tree) {} | |
| 440 | |
| 441 int cp_offset_; | |
| 442 TextType text_type_; | |
| 443 RegExpTree* tree_; | |
| 444 }; | |
| 445 | |
| 446 | |
| 447 class Trace; | |
| 448 struct PreloadState; | |
| 449 class GreedyLoopState; | |
| 450 class AlternativeGenerationList; | |
| 451 | |
| 452 struct NodeInfo { | |
| 453 NodeInfo() | |
| 454 : being_analyzed(false), | |
| 455 been_analyzed(false), | |
| 456 follows_word_interest(false), | |
| 457 follows_newline_interest(false), | |
| 458 follows_start_interest(false), | |
| 459 at_end(false), | |
| 460 visited(false), | |
| 461 replacement_calculated(false) { } | |
| 462 | |
| 463 // Returns true if the interests and assumptions of this node | |
| 464 // matches the given one. | |
| 465 bool Matches(NodeInfo* that) { | |
| 466 return (at_end == that->at_end) && | |
| 467 (follows_word_interest == that->follows_word_interest) && | |
| 468 (follows_newline_interest == that->follows_newline_interest) && | |
| 469 (follows_start_interest == that->follows_start_interest); | |
| 470 } | |
| 471 | |
| 472 // Updates the interests of this node given the interests of the | |
| 473 // node preceding it. | |
| 474 void AddFromPreceding(NodeInfo* that) { | |
| 475 at_end |= that->at_end; | |
| 476 follows_word_interest |= that->follows_word_interest; | |
| 477 follows_newline_interest |= that->follows_newline_interest; | |
| 478 follows_start_interest |= that->follows_start_interest; | |
| 479 } | |
| 480 | |
| 481 bool HasLookbehind() { | |
| 482 return follows_word_interest || | |
| 483 follows_newline_interest || | |
| 484 follows_start_interest; | |
| 485 } | |
| 486 | |
| 487 // Sets the interests of this node to include the interests of the | |
| 488 // following node. | |
| 489 void AddFromFollowing(NodeInfo* that) { | |
| 490 follows_word_interest |= that->follows_word_interest; | |
| 491 follows_newline_interest |= that->follows_newline_interest; | |
| 492 follows_start_interest |= that->follows_start_interest; | |
| 493 } | |
| 494 | |
| 495 void ResetCompilationState() { | |
| 496 being_analyzed = false; | |
| 497 been_analyzed = false; | |
| 498 } | |
| 499 | |
| 500 bool being_analyzed: 1; | |
| 501 bool been_analyzed: 1; | |
| 502 | |
| 503 // These bits are set of this node has to know what the preceding | |
| 504 // character was. | |
| 505 bool follows_word_interest: 1; | |
| 506 bool follows_newline_interest: 1; | |
| 507 bool follows_start_interest: 1; | |
| 508 | |
| 509 bool at_end: 1; | |
| 510 bool visited: 1; | |
| 511 bool replacement_calculated: 1; | |
| 512 }; | |
| 513 | |
| 514 | |
| 515 // Details of a quick mask-compare check that can look ahead in the | |
| 516 // input stream. | |
| 517 class QuickCheckDetails { | |
| 518 public: | |
| 519 QuickCheckDetails() | |
| 520 : characters_(0), | |
| 521 mask_(0), | |
| 522 value_(0), | |
| 523 cannot_match_(false) { } | |
| 524 explicit QuickCheckDetails(int characters) | |
| 525 : characters_(characters), | |
| 526 mask_(0), | |
| 527 value_(0), | |
| 528 cannot_match_(false) { } | |
| 529 bool Rationalize(bool one_byte); | |
| 530 // Merge in the information from another branch of an alternation. | |
| 531 void Merge(QuickCheckDetails* other, int from_index); | |
| 532 // Advance the current position by some amount. | |
| 533 void Advance(int by, bool one_byte); | |
| 534 void Clear(); | |
| 535 bool cannot_match() { return cannot_match_; } | |
| 536 void set_cannot_match() { cannot_match_ = true; } | |
| 537 struct Position { | |
| 538 Position() : mask(0), value(0), determines_perfectly(false) { } | |
| 539 uc16 mask; | |
| 540 uc16 value; | |
| 541 bool determines_perfectly; | |
| 542 }; | |
| 543 int characters() { return characters_; } | |
| 544 void set_characters(int characters) { characters_ = characters; } | |
| 545 Position* positions(int index) { | |
| 546 DCHECK(index >= 0); | |
| 547 DCHECK(index < characters_); | |
| 548 return positions_ + index; | |
| 549 } | |
| 550 uint32_t mask() { return mask_; } | |
| 551 uint32_t value() { return value_; } | |
| 552 | |
| 553 private: | |
| 554 // How many characters do we have quick check information from. This is | |
| 555 // the same for all branches of a choice node. | |
| 556 int characters_; | |
| 557 Position positions_[4]; | |
| 558 // These values are the condensate of the above array after Rationalize(). | |
| 559 uint32_t mask_; | |
| 560 uint32_t value_; | |
| 561 // If set to true, there is no way this quick check can match at all. | |
| 562 // E.g., if it requires to be at the start of the input, and isn't. | |
| 563 bool cannot_match_; | |
| 564 }; | |
| 565 | |
| 566 | |
| 567 extern int kUninitializedRegExpNodePlaceHolder; | |
| 568 | |
| 569 | |
| 570 class RegExpNode: public ZoneObject { | |
| 571 public: | |
| 572 explicit RegExpNode(Zone* zone) | |
| 573 : replacement_(NULL), on_work_list_(false), trace_count_(0), zone_(zone) { | |
| 574 bm_info_[0] = bm_info_[1] = NULL; | |
| 575 } | |
| 576 virtual ~RegExpNode(); | |
| 577 virtual void Accept(NodeVisitor* visitor) = 0; | |
| 578 // Generates a goto to this node or actually generates the code at this point. | |
| 579 virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0; | |
| 580 // How many characters must this node consume at a minimum in order to | |
| 581 // succeed. If we have found at least 'still_to_find' characters that | |
| 582 // must be consumed there is no need to ask any following nodes whether | |
| 583 // they are sure to eat any more characters. The not_at_start argument is | |
| 584 // used to indicate that we know we are not at the start of the input. In | |
| 585 // this case anchored branches will always fail and can be ignored when | |
| 586 // determining how many characters are consumed on success. | |
| 587 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start) = 0; | |
| 588 // Emits some quick code that checks whether the preloaded characters match. | |
| 589 // Falls through on certain failure, jumps to the label on possible success. | |
| 590 // If the node cannot make a quick check it does nothing and returns false. | |
| 591 bool EmitQuickCheck(RegExpCompiler* compiler, | |
| 592 Trace* bounds_check_trace, | |
| 593 Trace* trace, | |
| 594 bool preload_has_checked_bounds, | |
| 595 Label* on_possible_success, | |
| 596 QuickCheckDetails* details_return, | |
| 597 bool fall_through_on_failure); | |
| 598 // For a given number of characters this returns a mask and a value. The | |
| 599 // next n characters are anded with the mask and compared with the value. | |
| 600 // A comparison failure indicates the node cannot match the next n characters. | |
| 601 // A comparison success indicates the node may match. | |
| 602 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 603 RegExpCompiler* compiler, | |
| 604 int characters_filled_in, | |
| 605 bool not_at_start) = 0; | |
| 606 static const int kNodeIsTooComplexForGreedyLoops = -1; | |
| 607 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | |
| 608 // Only returns the successor for a text node of length 1 that matches any | |
| 609 // character and that has no guards on it. | |
| 610 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( | |
| 611 RegExpCompiler* compiler) { | |
| 612 return NULL; | |
| 613 } | |
| 614 | |
| 615 // Collects information on the possible code units (mod 128) that can match if | |
| 616 // we look forward. This is used for a Boyer-Moore-like string searching | |
| 617 // implementation. TODO(erikcorry): This should share more code with | |
| 618 // EatsAtLeast, GetQuickCheckDetails. The budget argument is used to limit | |
| 619 // the number of nodes we are willing to look at in order to create this data. | |
| 620 static const int kRecursionBudget = 200; | |
| 621 bool KeepRecursing(RegExpCompiler* compiler); | |
| 622 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 623 BoyerMooreLookahead* bm, bool not_at_start) { | |
| 624 UNREACHABLE(); | |
| 625 } | |
| 626 | |
| 627 // If we know that the input is one-byte then there are some nodes that can | |
| 628 // never match. This method returns a node that can be substituted for | |
| 629 // itself, or NULL if the node can never match. | |
| 630 virtual RegExpNode* FilterOneByte(int depth, bool ignore_case) { | |
| 631 return this; | |
| 632 } | |
| 633 // Helper for FilterOneByte. | |
| 634 RegExpNode* replacement() { | |
| 635 DCHECK(info()->replacement_calculated); | |
| 636 return replacement_; | |
| 637 } | |
| 638 RegExpNode* set_replacement(RegExpNode* replacement) { | |
| 639 info()->replacement_calculated = true; | |
| 640 replacement_ = replacement; | |
| 641 return replacement; // For convenience. | |
| 642 } | |
| 643 | |
| 644 // We want to avoid recalculating the lookahead info, so we store it on the | |
| 645 // node. Only info that is for this node is stored. We can tell that the | |
| 646 // info is for this node when offset == 0, so the information is calculated | |
| 647 // relative to this node. | |
| 648 void SaveBMInfo(BoyerMooreLookahead* bm, bool not_at_start, int offset) { | |
| 649 if (offset == 0) set_bm_info(not_at_start, bm); | |
| 650 } | |
| 651 | |
| 652 Label* label() { return &label_; } | |
| 653 // If non-generic code is generated for a node (i.e. the node is not at the | |
| 654 // start of the trace) then it cannot be reused. This variable sets a limit | |
| 655 // on how often we allow that to happen before we insist on starting a new | |
| 656 // trace and generating generic code for a node that can be reused by flushing | |
| 657 // the deferred actions in the current trace and generating a goto. | |
| 658 static const int kMaxCopiesCodeGenerated = 10; | |
| 659 | |
| 660 bool on_work_list() { return on_work_list_; } | |
| 661 void set_on_work_list(bool value) { on_work_list_ = value; } | |
| 662 | |
| 663 NodeInfo* info() { return &info_; } | |
| 664 | |
| 665 BoyerMooreLookahead* bm_info(bool not_at_start) { | |
| 666 return bm_info_[not_at_start ? 1 : 0]; | |
| 667 } | |
| 668 | |
| 669 Zone* zone() const { return zone_; } | |
| 670 | |
| 671 protected: | |
| 672 enum LimitResult { DONE, CONTINUE }; | |
| 673 RegExpNode* replacement_; | |
| 674 | |
| 675 LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace); | |
| 676 | |
| 677 void set_bm_info(bool not_at_start, BoyerMooreLookahead* bm) { | |
| 678 bm_info_[not_at_start ? 1 : 0] = bm; | |
| 679 } | |
| 680 | |
| 681 private: | |
| 682 static const int kFirstCharBudget = 10; | |
| 683 Label label_; | |
| 684 bool on_work_list_; | |
| 685 NodeInfo info_; | |
| 686 // This variable keeps track of how many times code has been generated for | |
| 687 // this node (in different traces). We don't keep track of where the | |
| 688 // generated code is located unless the code is generated at the start of | |
| 689 // a trace, in which case it is generic and can be reused by flushing the | |
| 690 // deferred operations in the current trace and generating a goto. | |
| 691 int trace_count_; | |
| 692 BoyerMooreLookahead* bm_info_[2]; | |
| 693 | |
| 694 Zone* zone_; | |
| 695 }; | |
| 696 | |
| 697 | |
| 698 // A simple closed interval. | |
| 699 class Interval { | |
| 700 public: | |
| 701 Interval() : from_(kNone), to_(kNone) { } | |
| 702 Interval(int from, int to) : from_(from), to_(to) { } | |
| 703 Interval Union(Interval that) { | |
| 704 if (that.from_ == kNone) | |
| 705 return *this; | |
| 706 else if (from_ == kNone) | |
| 707 return that; | |
| 708 else | |
| 709 return Interval(Min(from_, that.from_), Max(to_, that.to_)); | |
| 710 } | |
| 711 bool Contains(int value) { | |
| 712 return (from_ <= value) && (value <= to_); | |
| 713 } | |
| 714 bool is_empty() { return from_ == kNone; } | |
| 715 int from() const { return from_; } | |
| 716 int to() const { return to_; } | |
| 717 static Interval Empty() { return Interval(); } | |
| 718 static const int kNone = -1; | |
| 719 private: | |
| 720 int from_; | |
| 721 int to_; | |
| 722 }; | |
| 723 | |
| 724 | |
| 725 class SeqRegExpNode: public RegExpNode { | |
| 726 public: | |
| 727 explicit SeqRegExpNode(RegExpNode* on_success) | |
| 728 : RegExpNode(on_success->zone()), on_success_(on_success) { } | |
| 729 RegExpNode* on_success() { return on_success_; } | |
| 730 void set_on_success(RegExpNode* node) { on_success_ = node; } | |
| 731 virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); | |
| 732 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 733 BoyerMooreLookahead* bm, bool not_at_start) { | |
| 734 on_success_->FillInBMInfo(isolate, offset, budget - 1, bm, not_at_start); | |
| 735 if (offset == 0) set_bm_info(not_at_start, bm); | |
| 736 } | |
| 737 | |
| 738 protected: | |
| 739 RegExpNode* FilterSuccessor(int depth, bool ignore_case); | |
| 740 | |
| 741 private: | |
| 742 RegExpNode* on_success_; | |
| 743 }; | |
| 744 | |
| 745 | |
| 746 class ActionNode: public SeqRegExpNode { | |
| 747 public: | |
| 748 enum ActionType { | |
| 749 SET_REGISTER, | |
| 750 INCREMENT_REGISTER, | |
| 751 STORE_POSITION, | |
| 752 BEGIN_SUBMATCH, | |
| 753 POSITIVE_SUBMATCH_SUCCESS, | |
| 754 EMPTY_MATCH_CHECK, | |
| 755 CLEAR_CAPTURES | |
| 756 }; | |
| 757 static ActionNode* SetRegister(int reg, int val, RegExpNode* on_success); | |
| 758 static ActionNode* IncrementRegister(int reg, RegExpNode* on_success); | |
| 759 static ActionNode* StorePosition(int reg, | |
| 760 bool is_capture, | |
| 761 RegExpNode* on_success); | |
| 762 static ActionNode* ClearCaptures(Interval range, RegExpNode* on_success); | |
| 763 static ActionNode* BeginSubmatch(int stack_pointer_reg, | |
| 764 int position_reg, | |
| 765 RegExpNode* on_success); | |
| 766 static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg, | |
| 767 int restore_reg, | |
| 768 int clear_capture_count, | |
| 769 int clear_capture_from, | |
| 770 RegExpNode* on_success); | |
| 771 static ActionNode* EmptyMatchCheck(int start_register, | |
| 772 int repetition_register, | |
| 773 int repetition_limit, | |
| 774 RegExpNode* on_success); | |
| 775 virtual void Accept(NodeVisitor* visitor); | |
| 776 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | |
| 777 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); | |
| 778 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 779 RegExpCompiler* compiler, | |
| 780 int filled_in, | |
| 781 bool not_at_start) { | |
| 782 return on_success()->GetQuickCheckDetails( | |
| 783 details, compiler, filled_in, not_at_start); | |
| 784 } | |
| 785 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 786 BoyerMooreLookahead* bm, bool not_at_start); | |
| 787 ActionType action_type() { return action_type_; } | |
| 788 // TODO(erikcorry): We should allow some action nodes in greedy loops. | |
| 789 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | |
| 790 | |
| 791 private: | |
| 792 union { | |
| 793 struct { | |
| 794 int reg; | |
| 795 int value; | |
| 796 } u_store_register; | |
| 797 struct { | |
| 798 int reg; | |
| 799 } u_increment_register; | |
| 800 struct { | |
| 801 int reg; | |
| 802 bool is_capture; | |
| 803 } u_position_register; | |
| 804 struct { | |
| 805 int stack_pointer_register; | |
| 806 int current_position_register; | |
| 807 int clear_register_count; | |
| 808 int clear_register_from; | |
| 809 } u_submatch; | |
| 810 struct { | |
| 811 int start_register; | |
| 812 int repetition_register; | |
| 813 int repetition_limit; | |
| 814 } u_empty_match_check; | |
| 815 struct { | |
| 816 int range_from; | |
| 817 int range_to; | |
| 818 } u_clear_captures; | |
| 819 } data_; | |
| 820 ActionNode(ActionType action_type, RegExpNode* on_success) | |
| 821 : SeqRegExpNode(on_success), | |
| 822 action_type_(action_type) { } | |
| 823 ActionType action_type_; | |
| 824 friend class DotPrinter; | |
| 825 }; | |
| 826 | |
| 827 | |
| 828 class TextNode: public SeqRegExpNode { | |
| 829 public: | |
| 830 TextNode(ZoneList<TextElement>* elms, | |
| 831 RegExpNode* on_success) | |
| 832 : SeqRegExpNode(on_success), | |
| 833 elms_(elms) { } | |
| 834 TextNode(RegExpCharacterClass* that, | |
| 835 RegExpNode* on_success) | |
| 836 : SeqRegExpNode(on_success), | |
| 837 elms_(new(zone()) ZoneList<TextElement>(1, zone())) { | |
| 838 elms_->Add(TextElement::CharClass(that), zone()); | |
| 839 } | |
| 840 virtual void Accept(NodeVisitor* visitor); | |
| 841 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | |
| 842 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); | |
| 843 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 844 RegExpCompiler* compiler, | |
| 845 int characters_filled_in, | |
| 846 bool not_at_start); | |
| 847 ZoneList<TextElement>* elements() { return elms_; } | |
| 848 void MakeCaseIndependent(Isolate* isolate, bool is_one_byte); | |
| 849 virtual int GreedyLoopTextLength(); | |
| 850 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( | |
| 851 RegExpCompiler* compiler); | |
| 852 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 853 BoyerMooreLookahead* bm, bool not_at_start); | |
| 854 void CalculateOffsets(); | |
| 855 virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); | |
| 856 | |
| 857 private: | |
| 858 enum TextEmitPassType { | |
| 859 NON_LATIN1_MATCH, // Check for characters that can't match. | |
| 860 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check. | |
| 861 NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs. | |
| 862 CASE_CHARACTER_MATCH, // Case-independent single character check. | |
| 863 CHARACTER_CLASS_MATCH // Character class. | |
| 864 }; | |
| 865 static bool SkipPass(int pass, bool ignore_case); | |
| 866 static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH; | |
| 867 static const int kLastPass = CHARACTER_CLASS_MATCH; | |
| 868 void TextEmitPass(RegExpCompiler* compiler, | |
| 869 TextEmitPassType pass, | |
| 870 bool preloaded, | |
| 871 Trace* trace, | |
| 872 bool first_element_checked, | |
| 873 int* checked_up_to); | |
| 874 int Length(); | |
| 875 ZoneList<TextElement>* elms_; | |
| 876 }; | |
| 877 | |
| 878 | |
| 879 class AssertionNode: public SeqRegExpNode { | |
| 880 public: | |
| 881 enum AssertionType { | |
| 882 AT_END, | |
| 883 AT_START, | |
| 884 AT_BOUNDARY, | |
| 885 AT_NON_BOUNDARY, | |
| 886 AFTER_NEWLINE | |
| 887 }; | |
| 888 static AssertionNode* AtEnd(RegExpNode* on_success) { | |
| 889 return new(on_success->zone()) AssertionNode(AT_END, on_success); | |
| 890 } | |
| 891 static AssertionNode* AtStart(RegExpNode* on_success) { | |
| 892 return new(on_success->zone()) AssertionNode(AT_START, on_success); | |
| 893 } | |
| 894 static AssertionNode* AtBoundary(RegExpNode* on_success) { | |
| 895 return new(on_success->zone()) AssertionNode(AT_BOUNDARY, on_success); | |
| 896 } | |
| 897 static AssertionNode* AtNonBoundary(RegExpNode* on_success) { | |
| 898 return new(on_success->zone()) AssertionNode(AT_NON_BOUNDARY, on_success); | |
| 899 } | |
| 900 static AssertionNode* AfterNewline(RegExpNode* on_success) { | |
| 901 return new(on_success->zone()) AssertionNode(AFTER_NEWLINE, on_success); | |
| 902 } | |
| 903 virtual void Accept(NodeVisitor* visitor); | |
| 904 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | |
| 905 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); | |
| 906 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 907 RegExpCompiler* compiler, | |
| 908 int filled_in, | |
| 909 bool not_at_start); | |
| 910 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 911 BoyerMooreLookahead* bm, bool not_at_start); | |
| 912 AssertionType assertion_type() { return assertion_type_; } | |
| 913 | |
| 914 private: | |
| 915 void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace); | |
| 916 enum IfPrevious { kIsNonWord, kIsWord }; | |
| 917 void BacktrackIfPrevious(RegExpCompiler* compiler, | |
| 918 Trace* trace, | |
| 919 IfPrevious backtrack_if_previous); | |
| 920 AssertionNode(AssertionType t, RegExpNode* on_success) | |
| 921 : SeqRegExpNode(on_success), assertion_type_(t) { } | |
| 922 AssertionType assertion_type_; | |
| 923 }; | |
| 924 | |
| 925 | |
| 926 class BackReferenceNode: public SeqRegExpNode { | |
| 927 public: | |
| 928 BackReferenceNode(int start_reg, | |
| 929 int end_reg, | |
| 930 RegExpNode* on_success) | |
| 931 : SeqRegExpNode(on_success), | |
| 932 start_reg_(start_reg), | |
| 933 end_reg_(end_reg) { } | |
| 934 virtual void Accept(NodeVisitor* visitor); | |
| 935 int start_register() { return start_reg_; } | |
| 936 int end_register() { return end_reg_; } | |
| 937 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | |
| 938 virtual int EatsAtLeast(int still_to_find, | |
| 939 int recursion_depth, | |
| 940 bool not_at_start); | |
| 941 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 942 RegExpCompiler* compiler, | |
| 943 int characters_filled_in, | |
| 944 bool not_at_start) { | |
| 945 return; | |
| 946 } | |
| 947 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 948 BoyerMooreLookahead* bm, bool not_at_start); | |
| 949 | |
| 950 private: | |
| 951 int start_reg_; | |
| 952 int end_reg_; | |
| 953 }; | |
| 954 | |
| 955 | |
| 956 class EndNode: public RegExpNode { | |
| 957 public: | |
| 958 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; | |
| 959 explicit EndNode(Action action, Zone* zone) | |
| 960 : RegExpNode(zone), action_(action) { } | |
| 961 virtual void Accept(NodeVisitor* visitor); | |
| 962 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | |
| 963 virtual int EatsAtLeast(int still_to_find, | |
| 964 int recursion_depth, | |
| 965 bool not_at_start) { return 0; } | |
| 966 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 967 RegExpCompiler* compiler, | |
| 968 int characters_filled_in, | |
| 969 bool not_at_start) { | |
| 970 // Returning 0 from EatsAtLeast should ensure we never get here. | |
| 971 UNREACHABLE(); | |
| 972 } | |
| 973 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 974 BoyerMooreLookahead* bm, bool not_at_start) { | |
| 975 // Returning 0 from EatsAtLeast should ensure we never get here. | |
| 976 UNREACHABLE(); | |
| 977 } | |
| 978 | |
| 979 private: | |
| 980 Action action_; | |
| 981 }; | |
| 982 | |
| 983 | |
| 984 class NegativeSubmatchSuccess: public EndNode { | |
| 985 public: | |
| 986 NegativeSubmatchSuccess(int stack_pointer_reg, | |
| 987 int position_reg, | |
| 988 int clear_capture_count, | |
| 989 int clear_capture_start, | |
| 990 Zone* zone) | |
| 991 : EndNode(NEGATIVE_SUBMATCH_SUCCESS, zone), | |
| 992 stack_pointer_register_(stack_pointer_reg), | |
| 993 current_position_register_(position_reg), | |
| 994 clear_capture_count_(clear_capture_count), | |
| 995 clear_capture_start_(clear_capture_start) { } | |
| 996 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | |
| 997 | |
| 998 private: | |
| 999 int stack_pointer_register_; | |
| 1000 int current_position_register_; | |
| 1001 int clear_capture_count_; | |
| 1002 int clear_capture_start_; | |
| 1003 }; | |
| 1004 | |
| 1005 | |
| 1006 class Guard: public ZoneObject { | |
| 1007 public: | |
| 1008 enum Relation { LT, GEQ }; | |
| 1009 Guard(int reg, Relation op, int value) | |
| 1010 : reg_(reg), | |
| 1011 op_(op), | |
| 1012 value_(value) { } | |
| 1013 int reg() { return reg_; } | |
| 1014 Relation op() { return op_; } | |
| 1015 int value() { return value_; } | |
| 1016 | |
| 1017 private: | |
| 1018 int reg_; | |
| 1019 Relation op_; | |
| 1020 int value_; | |
| 1021 }; | |
| 1022 | |
| 1023 | |
| 1024 class GuardedAlternative { | |
| 1025 public: | |
| 1026 explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { } | |
| 1027 void AddGuard(Guard* guard, Zone* zone); | |
| 1028 RegExpNode* node() { return node_; } | |
| 1029 void set_node(RegExpNode* node) { node_ = node; } | |
| 1030 ZoneList<Guard*>* guards() { return guards_; } | |
| 1031 | |
| 1032 private: | |
| 1033 RegExpNode* node_; | |
| 1034 ZoneList<Guard*>* guards_; | |
| 1035 }; | |
| 1036 | |
| 1037 | |
| 1038 class AlternativeGeneration; | |
| 1039 | |
| 1040 | |
| 1041 class ChoiceNode: public RegExpNode { | |
| 1042 public: | |
| 1043 explicit ChoiceNode(int expected_size, Zone* zone) | |
| 1044 : RegExpNode(zone), | |
| 1045 alternatives_(new(zone) | |
| 1046 ZoneList<GuardedAlternative>(expected_size, zone)), | |
| 1047 table_(NULL), | |
| 1048 not_at_start_(false), | |
| 1049 being_calculated_(false) { } | |
| 1050 virtual void Accept(NodeVisitor* visitor); | |
| 1051 void AddAlternative(GuardedAlternative node) { | |
| 1052 alternatives()->Add(node, zone()); | |
| 1053 } | |
| 1054 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } | |
| 1055 DispatchTable* GetTable(bool ignore_case); | |
| 1056 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | |
| 1057 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); | |
| 1058 int EatsAtLeastHelper(int still_to_find, | |
| 1059 int budget, | |
| 1060 RegExpNode* ignore_this_node, | |
| 1061 bool not_at_start); | |
| 1062 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 1063 RegExpCompiler* compiler, | |
| 1064 int characters_filled_in, | |
| 1065 bool not_at_start); | |
| 1066 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 1067 BoyerMooreLookahead* bm, bool not_at_start); | |
| 1068 | |
| 1069 bool being_calculated() { return being_calculated_; } | |
| 1070 bool not_at_start() { return not_at_start_; } | |
| 1071 void set_not_at_start() { not_at_start_ = true; } | |
| 1072 void set_being_calculated(bool b) { being_calculated_ = b; } | |
| 1073 virtual bool try_to_emit_quick_check_for_alternative(bool is_first) { | |
| 1074 return true; | |
| 1075 } | |
| 1076 virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); | |
| 1077 | |
| 1078 protected: | |
| 1079 int GreedyLoopTextLengthForAlternative(GuardedAlternative* alternative); | |
| 1080 ZoneList<GuardedAlternative>* alternatives_; | |
| 1081 | |
| 1082 private: | |
| 1083 friend class DispatchTableConstructor; | |
| 1084 friend class Analysis; | |
| 1085 void GenerateGuard(RegExpMacroAssembler* macro_assembler, | |
| 1086 Guard* guard, | |
| 1087 Trace* trace); | |
| 1088 int CalculatePreloadCharacters(RegExpCompiler* compiler, int eats_at_least); | |
| 1089 void EmitOutOfLineContinuation(RegExpCompiler* compiler, | |
| 1090 Trace* trace, | |
| 1091 GuardedAlternative alternative, | |
| 1092 AlternativeGeneration* alt_gen, | |
| 1093 int preload_characters, | |
| 1094 bool next_expects_preload); | |
| 1095 void SetUpPreLoad(RegExpCompiler* compiler, | |
| 1096 Trace* current_trace, | |
| 1097 PreloadState* preloads); | |
| 1098 void AssertGuardsMentionRegisters(Trace* trace); | |
| 1099 int EmitOptimizedUnanchoredSearch(RegExpCompiler* compiler, Trace* trace); | |
| 1100 Trace* EmitGreedyLoop(RegExpCompiler* compiler, | |
| 1101 Trace* trace, | |
| 1102 AlternativeGenerationList* alt_gens, | |
| 1103 PreloadState* preloads, | |
| 1104 GreedyLoopState* greedy_loop_state, | |
| 1105 int text_length); | |
| 1106 void EmitChoices(RegExpCompiler* compiler, | |
| 1107 AlternativeGenerationList* alt_gens, | |
| 1108 int first_choice, | |
| 1109 Trace* trace, | |
| 1110 PreloadState* preloads); | |
| 1111 DispatchTable* table_; | |
| 1112 // If true, this node is never checked at the start of the input. | |
| 1113 // Allows a new trace to start with at_start() set to false. | |
| 1114 bool not_at_start_; | |
| 1115 bool being_calculated_; | |
| 1116 }; | |
| 1117 | |
| 1118 | |
| 1119 class NegativeLookaheadChoiceNode: public ChoiceNode { | |
| 1120 public: | |
| 1121 explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail, | |
| 1122 GuardedAlternative then_do_this, | |
| 1123 Zone* zone) | |
| 1124 : ChoiceNode(2, zone) { | |
| 1125 AddAlternative(this_must_fail); | |
| 1126 AddAlternative(then_do_this); | |
| 1127 } | |
| 1128 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); | |
| 1129 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 1130 RegExpCompiler* compiler, | |
| 1131 int characters_filled_in, | |
| 1132 bool not_at_start); | |
| 1133 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 1134 BoyerMooreLookahead* bm, bool not_at_start) { | |
| 1135 alternatives_->at(1).node()->FillInBMInfo(isolate, offset, budget - 1, bm, | |
| 1136 not_at_start); | |
| 1137 if (offset == 0) set_bm_info(not_at_start, bm); | |
| 1138 } | |
| 1139 // For a negative lookahead we don't emit the quick check for the | |
| 1140 // alternative that is expected to fail. This is because quick check code | |
| 1141 // starts by loading enough characters for the alternative that takes fewest | |
| 1142 // characters, but on a negative lookahead the negative branch did not take | |
| 1143 // part in that calculation (EatsAtLeast) so the assumptions don't hold. | |
| 1144 virtual bool try_to_emit_quick_check_for_alternative(bool is_first) { | |
| 1145 return !is_first; | |
| 1146 } | |
| 1147 virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); | |
| 1148 }; | |
| 1149 | |
| 1150 | |
| 1151 class LoopChoiceNode: public ChoiceNode { | |
| 1152 public: | |
| 1153 explicit LoopChoiceNode(bool body_can_be_zero_length, Zone* zone) | |
| 1154 : ChoiceNode(2, zone), | |
| 1155 loop_node_(NULL), | |
| 1156 continue_node_(NULL), | |
| 1157 body_can_be_zero_length_(body_can_be_zero_length) | |
| 1158 { } | |
| 1159 void AddLoopAlternative(GuardedAlternative alt); | |
| 1160 void AddContinueAlternative(GuardedAlternative alt); | |
| 1161 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | |
| 1162 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); | |
| 1163 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | |
| 1164 RegExpCompiler* compiler, | |
| 1165 int characters_filled_in, | |
| 1166 bool not_at_start); | |
| 1167 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | |
| 1168 BoyerMooreLookahead* bm, bool not_at_start); | |
| 1169 RegExpNode* loop_node() { return loop_node_; } | |
| 1170 RegExpNode* continue_node() { return continue_node_; } | |
| 1171 bool body_can_be_zero_length() { return body_can_be_zero_length_; } | |
| 1172 virtual void Accept(NodeVisitor* visitor); | |
| 1173 virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); | |
| 1174 | |
| 1175 private: | |
| 1176 // AddAlternative is made private for loop nodes because alternatives | |
| 1177 // should not be added freely, we need to keep track of which node | |
| 1178 // goes back to the node itself. | |
| 1179 void AddAlternative(GuardedAlternative node) { | |
| 1180 ChoiceNode::AddAlternative(node); | |
| 1181 } | |
| 1182 | |
| 1183 RegExpNode* loop_node_; | |
| 1184 RegExpNode* continue_node_; | |
| 1185 bool body_can_be_zero_length_; | |
| 1186 }; | |
| 1187 | |
| 1188 | |
| 1189 // Improve the speed that we scan for an initial point where a non-anchored | |
| 1190 // regexp can match by using a Boyer-Moore-like table. This is done by | |
| 1191 // identifying non-greedy non-capturing loops in the nodes that eat any | |
| 1192 // character one at a time. For example in the middle of the regexp | |
| 1193 // /foo[\s\S]*?bar/ we find such a loop. There is also such a loop implicitly | |
| 1194 // inserted at the start of any non-anchored regexp. | |
| 1195 // | |
| 1196 // When we have found such a loop we look ahead in the nodes to find the set of | |
| 1197 // characters that can come at given distances. For example for the regexp | |
| 1198 // /.?foo/ we know that there are at least 3 characters ahead of us, and the | |
| 1199 // sets of characters that can occur are [any, [f, o], [o]]. We find a range in | |
| 1200 // the lookahead info where the set of characters is reasonably constrained. In | |
| 1201 // our example this is from index 1 to 2 (0 is not constrained). We can now | |
| 1202 // look 3 characters ahead and if we don't find one of [f, o] (the union of | |
| 1203 // [f, o] and [o]) then we can skip forwards by the range size (in this case 2). | |
| 1204 // | |
| 1205 // For Unicode input strings we do the same, but modulo 128. | |
| 1206 // | |
| 1207 // We also look at the first string fed to the regexp and use that to get a hint | |
| 1208 // of the character frequencies in the inputs. This affects the assessment of | |
| 1209 // whether the set of characters is 'reasonably constrained'. | |
| 1210 // | |
| 1211 // We also have another lookahead mechanism (called quick check in the code), | |
| 1212 // which uses a wide load of multiple characters followed by a mask and compare | |
| 1213 // to determine whether a match is possible at this point. | |
| 1214 enum ContainedInLattice { | |
| 1215 kNotYet = 0, | |
| 1216 kLatticeIn = 1, | |
| 1217 kLatticeOut = 2, | |
| 1218 kLatticeUnknown = 3 // Can also mean both in and out. | |
| 1219 }; | |
| 1220 | |
| 1221 | |
| 1222 inline ContainedInLattice Combine(ContainedInLattice a, ContainedInLattice b) { | |
| 1223 return static_cast<ContainedInLattice>(a | b); | |
| 1224 } | |
| 1225 | |
| 1226 | |
| 1227 ContainedInLattice AddRange(ContainedInLattice a, | |
| 1228 const int* ranges, | |
| 1229 int ranges_size, | |
| 1230 Interval new_range); | |
| 1231 | |
| 1232 | |
| 1233 class BoyerMoorePositionInfo : public ZoneObject { | |
| 1234 public: | |
| 1235 explicit BoyerMoorePositionInfo(Zone* zone) | |
| 1236 : map_(new(zone) ZoneList<bool>(kMapSize, zone)), | |
| 1237 map_count_(0), | |
| 1238 w_(kNotYet), | |
| 1239 s_(kNotYet), | |
| 1240 d_(kNotYet), | |
| 1241 surrogate_(kNotYet) { | |
| 1242 for (int i = 0; i < kMapSize; i++) { | |
| 1243 map_->Add(false, zone); | |
| 1244 } | |
| 1245 } | |
| 1246 | |
| 1247 bool& at(int i) { return map_->at(i); } | |
| 1248 | |
| 1249 static const int kMapSize = 128; | |
| 1250 static const int kMask = kMapSize - 1; | |
| 1251 | |
| 1252 int map_count() const { return map_count_; } | |
| 1253 | |
| 1254 void Set(int character); | |
| 1255 void SetInterval(const Interval& interval); | |
| 1256 void SetAll(); | |
| 1257 bool is_non_word() { return w_ == kLatticeOut; } | |
| 1258 bool is_word() { return w_ == kLatticeIn; } | |
| 1259 | |
| 1260 private: | |
| 1261 ZoneList<bool>* map_; | |
| 1262 int map_count_; // Number of set bits in the map. | |
| 1263 ContainedInLattice w_; // The \w character class. | |
| 1264 ContainedInLattice s_; // The \s character class. | |
| 1265 ContainedInLattice d_; // The \d character class. | |
| 1266 ContainedInLattice surrogate_; // Surrogate UTF-16 code units. | |
| 1267 }; | |
| 1268 | |
| 1269 | |
| 1270 class BoyerMooreLookahead : public ZoneObject { | |
| 1271 public: | |
| 1272 BoyerMooreLookahead(int length, RegExpCompiler* compiler, Zone* zone); | |
| 1273 | |
| 1274 int length() { return length_; } | |
| 1275 int max_char() { return max_char_; } | |
| 1276 RegExpCompiler* compiler() { return compiler_; } | |
| 1277 | |
| 1278 int Count(int map_number) { | |
| 1279 return bitmaps_->at(map_number)->map_count(); | |
| 1280 } | |
| 1281 | |
| 1282 BoyerMoorePositionInfo* at(int i) { return bitmaps_->at(i); } | |
| 1283 | |
| 1284 void Set(int map_number, int character) { | |
| 1285 if (character > max_char_) return; | |
| 1286 BoyerMoorePositionInfo* info = bitmaps_->at(map_number); | |
| 1287 info->Set(character); | |
| 1288 } | |
| 1289 | |
| 1290 void SetInterval(int map_number, const Interval& interval) { | |
| 1291 if (interval.from() > max_char_) return; | |
| 1292 BoyerMoorePositionInfo* info = bitmaps_->at(map_number); | |
| 1293 if (interval.to() > max_char_) { | |
| 1294 info->SetInterval(Interval(interval.from(), max_char_)); | |
| 1295 } else { | |
| 1296 info->SetInterval(interval); | |
| 1297 } | |
| 1298 } | |
| 1299 | |
| 1300 void SetAll(int map_number) { | |
| 1301 bitmaps_->at(map_number)->SetAll(); | |
| 1302 } | |
| 1303 | |
| 1304 void SetRest(int from_map) { | |
| 1305 for (int i = from_map; i < length_; i++) SetAll(i); | |
| 1306 } | |
| 1307 void EmitSkipInstructions(RegExpMacroAssembler* masm); | |
| 1308 | |
| 1309 private: | |
| 1310 // This is the value obtained by EatsAtLeast. If we do not have at least this | |
| 1311 // many characters left in the sample string then the match is bound to fail. | |
| 1312 // Therefore it is OK to read a character this far ahead of the current match | |
| 1313 // point. | |
| 1314 int length_; | |
| 1315 RegExpCompiler* compiler_; | |
| 1316 // 0xff for Latin1, 0xffff for UTF-16. | |
| 1317 int max_char_; | |
| 1318 ZoneList<BoyerMoorePositionInfo*>* bitmaps_; | |
| 1319 | |
| 1320 int GetSkipTable(int min_lookahead, | |
| 1321 int max_lookahead, | |
| 1322 Handle<ByteArray> boolean_skip_table); | |
| 1323 bool FindWorthwhileInterval(int* from, int* to); | |
| 1324 int FindBestInterval( | |
| 1325 int max_number_of_chars, int old_biggest_points, int* from, int* to); | |
| 1326 }; | |
| 1327 | |
| 1328 | |
| 1329 // There are many ways to generate code for a node. This class encapsulates | |
| 1330 // the current way we should be generating. In other words it encapsulates | |
| 1331 // the current state of the code generator. The effect of this is that we | |
| 1332 // generate code for paths that the matcher can take through the regular | |
| 1333 // expression. A given node in the regexp can be code-generated several times | |
| 1334 // as it can be part of several traces. For example for the regexp: | |
| 1335 // /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part | |
| 1336 // of the foo-bar-baz trace and once as part of the foo-ip-baz trace. The code | |
| 1337 // to match foo is generated only once (the traces have a common prefix). The | |
| 1338 // code to store the capture is deferred and generated (twice) after the places | |
| 1339 // where baz has been matched. | |
| 1340 class Trace { | |
| 1341 public: | |
| 1342 // A value for a property that is either known to be true, know to be false, | |
| 1343 // or not known. | |
| 1344 enum TriBool { | |
| 1345 UNKNOWN = -1, FALSE_VALUE = 0, TRUE_VALUE = 1 | |
| 1346 }; | |
| 1347 | |
| 1348 class DeferredAction { | |
| 1349 public: | |
| 1350 DeferredAction(ActionNode::ActionType action_type, int reg) | |
| 1351 : action_type_(action_type), reg_(reg), next_(NULL) { } | |
| 1352 DeferredAction* next() { return next_; } | |
| 1353 bool Mentions(int reg); | |
| 1354 int reg() { return reg_; } | |
| 1355 ActionNode::ActionType action_type() { return action_type_; } | |
| 1356 private: | |
| 1357 ActionNode::ActionType action_type_; | |
| 1358 int reg_; | |
| 1359 DeferredAction* next_; | |
| 1360 friend class Trace; | |
| 1361 }; | |
| 1362 | |
| 1363 class DeferredCapture : public DeferredAction { | |
| 1364 public: | |
| 1365 DeferredCapture(int reg, bool is_capture, Trace* trace) | |
| 1366 : DeferredAction(ActionNode::STORE_POSITION, reg), | |
| 1367 cp_offset_(trace->cp_offset()), | |
| 1368 is_capture_(is_capture) { } | |
| 1369 int cp_offset() { return cp_offset_; } | |
| 1370 bool is_capture() { return is_capture_; } | |
| 1371 private: | |
| 1372 int cp_offset_; | |
| 1373 bool is_capture_; | |
| 1374 void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; } | |
| 1375 }; | |
| 1376 | |
| 1377 class DeferredSetRegister : public DeferredAction { | |
| 1378 public: | |
| 1379 DeferredSetRegister(int reg, int value) | |
| 1380 : DeferredAction(ActionNode::SET_REGISTER, reg), | |
| 1381 value_(value) { } | |
| 1382 int value() { return value_; } | |
| 1383 private: | |
| 1384 int value_; | |
| 1385 }; | |
| 1386 | |
| 1387 class DeferredClearCaptures : public DeferredAction { | |
| 1388 public: | |
| 1389 explicit DeferredClearCaptures(Interval range) | |
| 1390 : DeferredAction(ActionNode::CLEAR_CAPTURES, -1), | |
| 1391 range_(range) { } | |
| 1392 Interval range() { return range_; } | |
| 1393 private: | |
| 1394 Interval range_; | |
| 1395 }; | |
| 1396 | |
| 1397 class DeferredIncrementRegister : public DeferredAction { | |
| 1398 public: | |
| 1399 explicit DeferredIncrementRegister(int reg) | |
| 1400 : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { } | |
| 1401 }; | |
| 1402 | |
| 1403 Trace() | |
| 1404 : cp_offset_(0), | |
| 1405 actions_(NULL), | |
| 1406 backtrack_(NULL), | |
| 1407 stop_node_(NULL), | |
| 1408 loop_label_(NULL), | |
| 1409 characters_preloaded_(0), | |
| 1410 bound_checked_up_to_(0), | |
| 1411 flush_budget_(100), | |
| 1412 at_start_(UNKNOWN) { } | |
| 1413 | |
| 1414 // End the trace. This involves flushing the deferred actions in the trace | |
| 1415 // and pushing a backtrack location onto the backtrack stack. Once this is | |
| 1416 // done we can start a new trace or go to one that has already been | |
| 1417 // generated. | |
| 1418 void Flush(RegExpCompiler* compiler, RegExpNode* successor); | |
| 1419 int cp_offset() { return cp_offset_; } | |
| 1420 DeferredAction* actions() { return actions_; } | |
| 1421 // A trivial trace is one that has no deferred actions or other state that | |
| 1422 // affects the assumptions used when generating code. There is no recorded | |
| 1423 // backtrack location in a trivial trace, so with a trivial trace we will | |
| 1424 // generate code that, on a failure to match, gets the backtrack location | |
| 1425 // from the backtrack stack rather than using a direct jump instruction. We | |
| 1426 // always start code generation with a trivial trace and non-trivial traces | |
| 1427 // are created as we emit code for nodes or add to the list of deferred | |
| 1428 // actions in the trace. The location of the code generated for a node using | |
| 1429 // a trivial trace is recorded in a label in the node so that gotos can be | |
| 1430 // generated to that code. | |
| 1431 bool is_trivial() { | |
| 1432 return backtrack_ == NULL && | |
| 1433 actions_ == NULL && | |
| 1434 cp_offset_ == 0 && | |
| 1435 characters_preloaded_ == 0 && | |
| 1436 bound_checked_up_to_ == 0 && | |
| 1437 quick_check_performed_.characters() == 0 && | |
| 1438 at_start_ == UNKNOWN; | |
| 1439 } | |
| 1440 TriBool at_start() { return at_start_; } | |
| 1441 void set_at_start(bool at_start) { | |
| 1442 at_start_ = at_start ? TRUE_VALUE : FALSE_VALUE; | |
| 1443 } | |
| 1444 Label* backtrack() { return backtrack_; } | |
| 1445 Label* loop_label() { return loop_label_; } | |
| 1446 RegExpNode* stop_node() { return stop_node_; } | |
| 1447 int characters_preloaded() { return characters_preloaded_; } | |
| 1448 int bound_checked_up_to() { return bound_checked_up_to_; } | |
| 1449 int flush_budget() { return flush_budget_; } | |
| 1450 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; } | |
| 1451 bool mentions_reg(int reg); | |
| 1452 // Returns true if a deferred position store exists to the specified | |
| 1453 // register and stores the offset in the out-parameter. Otherwise | |
| 1454 // returns false. | |
| 1455 bool GetStoredPosition(int reg, int* cp_offset); | |
| 1456 // These set methods and AdvanceCurrentPositionInTrace should be used only on | |
| 1457 // new traces - the intention is that traces are immutable after creation. | |
| 1458 void add_action(DeferredAction* new_action) { | |
| 1459 DCHECK(new_action->next_ == NULL); | |
| 1460 new_action->next_ = actions_; | |
| 1461 actions_ = new_action; | |
| 1462 } | |
| 1463 void set_backtrack(Label* backtrack) { backtrack_ = backtrack; } | |
| 1464 void set_stop_node(RegExpNode* node) { stop_node_ = node; } | |
| 1465 void set_loop_label(Label* label) { loop_label_ = label; } | |
| 1466 void set_characters_preloaded(int count) { characters_preloaded_ = count; } | |
| 1467 void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; } | |
| 1468 void set_flush_budget(int to) { flush_budget_ = to; } | |
| 1469 void set_quick_check_performed(QuickCheckDetails* d) { | |
| 1470 quick_check_performed_ = *d; | |
| 1471 } | |
| 1472 void InvalidateCurrentCharacter(); | |
| 1473 void AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler); | |
| 1474 | |
| 1475 private: | |
| 1476 int FindAffectedRegisters(OutSet* affected_registers, Zone* zone); | |
| 1477 void PerformDeferredActions(RegExpMacroAssembler* macro, | |
| 1478 int max_register, | |
| 1479 const OutSet& affected_registers, | |
| 1480 OutSet* registers_to_pop, | |
| 1481 OutSet* registers_to_clear, | |
| 1482 Zone* zone); | |
| 1483 void RestoreAffectedRegisters(RegExpMacroAssembler* macro, | |
| 1484 int max_register, | |
| 1485 const OutSet& registers_to_pop, | |
| 1486 const OutSet& registers_to_clear); | |
| 1487 int cp_offset_; | |
| 1488 DeferredAction* actions_; | |
| 1489 Label* backtrack_; | |
| 1490 RegExpNode* stop_node_; | |
| 1491 Label* loop_label_; | |
| 1492 int characters_preloaded_; | |
| 1493 int bound_checked_up_to_; | |
| 1494 QuickCheckDetails quick_check_performed_; | |
| 1495 int flush_budget_; | |
| 1496 TriBool at_start_; | |
| 1497 }; | |
| 1498 | |
| 1499 | |
| 1500 class GreedyLoopState { | |
| 1501 public: | |
| 1502 explicit GreedyLoopState(bool not_at_start); | |
| 1503 | |
| 1504 Label* label() { return &label_; } | |
| 1505 Trace* counter_backtrack_trace() { return &counter_backtrack_trace_; } | |
| 1506 | |
| 1507 private: | |
| 1508 Label label_; | |
| 1509 Trace counter_backtrack_trace_; | |
| 1510 }; | |
| 1511 | |
| 1512 | |
| 1513 struct PreloadState { | |
| 1514 static const int kEatsAtLeastNotYetInitialized = -1; | |
| 1515 bool preload_is_current_; | |
| 1516 bool preload_has_checked_bounds_; | |
| 1517 int preload_characters_; | |
| 1518 int eats_at_least_; | |
| 1519 void init() { | |
| 1520 eats_at_least_ = kEatsAtLeastNotYetInitialized; | |
| 1521 } | |
| 1522 }; | |
| 1523 | |
| 1524 | |
| 1525 class NodeVisitor { | |
| 1526 public: | |
| 1527 virtual ~NodeVisitor() { } | |
| 1528 #define DECLARE_VISIT(Type) \ | |
| 1529 virtual void Visit##Type(Type##Node* that) = 0; | |
| 1530 FOR_EACH_NODE_TYPE(DECLARE_VISIT) | |
| 1531 #undef DECLARE_VISIT | |
| 1532 virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); } | |
| 1533 }; | |
| 1534 | |
| 1535 | |
| 1536 // Node visitor used to add the start set of the alternatives to the | |
| 1537 // dispatch table of a choice node. | |
| 1538 class DispatchTableConstructor: public NodeVisitor { | |
| 1539 public: | |
| 1540 DispatchTableConstructor(DispatchTable* table, bool ignore_case, | |
| 1541 Zone* zone) | |
| 1542 : table_(table), | |
| 1543 choice_index_(-1), | |
| 1544 ignore_case_(ignore_case), | |
| 1545 zone_(zone) { } | |
| 1546 | |
| 1547 void BuildTable(ChoiceNode* node); | |
| 1548 | |
| 1549 void AddRange(CharacterRange range) { | |
| 1550 table()->AddRange(range, choice_index_, zone_); | |
| 1551 } | |
| 1552 | |
| 1553 void AddInverse(ZoneList<CharacterRange>* ranges); | |
| 1554 | |
| 1555 #define DECLARE_VISIT(Type) \ | |
| 1556 virtual void Visit##Type(Type##Node* that); | |
| 1557 FOR_EACH_NODE_TYPE(DECLARE_VISIT) | |
| 1558 #undef DECLARE_VISIT | |
| 1559 | |
| 1560 DispatchTable* table() { return table_; } | |
| 1561 void set_choice_index(int value) { choice_index_ = value; } | |
| 1562 | |
| 1563 protected: | |
| 1564 DispatchTable* table_; | |
| 1565 int choice_index_; | |
| 1566 bool ignore_case_; | |
| 1567 Zone* zone_; | |
| 1568 }; | |
| 1569 | |
| 1570 | |
| 1571 // Assertion propagation moves information about assertions such as | |
| 1572 // \b to the affected nodes. For instance, in /.\b./ information must | |
| 1573 // be propagated to the first '.' that whatever follows needs to know | |
| 1574 // if it matched a word or a non-word, and to the second '.' that it | |
| 1575 // has to check if it succeeds a word or non-word. In this case the | |
| 1576 // result will be something like: | |
| 1577 // | |
| 1578 // +-------+ +------------+ | |
| 1579 // | . | | . | | |
| 1580 // +-------+ ---> +------------+ | |
| 1581 // | word? | | check word | | |
| 1582 // +-------+ +------------+ | |
| 1583 class Analysis: public NodeVisitor { | |
| 1584 public: | |
| 1585 Analysis(Isolate* isolate, bool ignore_case, bool is_one_byte) | |
| 1586 : isolate_(isolate), | |
| 1587 ignore_case_(ignore_case), | |
| 1588 is_one_byte_(is_one_byte), | |
| 1589 error_message_(NULL) {} | |
| 1590 void EnsureAnalyzed(RegExpNode* node); | |
| 1591 | |
| 1592 #define DECLARE_VISIT(Type) \ | |
| 1593 virtual void Visit##Type(Type##Node* that); | |
| 1594 FOR_EACH_NODE_TYPE(DECLARE_VISIT) | |
| 1595 #undef DECLARE_VISIT | |
| 1596 virtual void VisitLoopChoice(LoopChoiceNode* that); | |
| 1597 | |
| 1598 bool has_failed() { return error_message_ != NULL; } | |
| 1599 const char* error_message() { | |
| 1600 DCHECK(error_message_ != NULL); | |
| 1601 return error_message_; | |
| 1602 } | |
| 1603 void fail(const char* error_message) { | |
| 1604 error_message_ = error_message; | |
| 1605 } | |
| 1606 | |
| 1607 Isolate* isolate() const { return isolate_; } | |
| 1608 | |
| 1609 private: | |
| 1610 Isolate* isolate_; | |
| 1611 bool ignore_case_; | |
| 1612 bool is_one_byte_; | |
| 1613 const char* error_message_; | |
| 1614 | |
| 1615 DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis); | |
| 1616 }; | |
| 1617 | |
| 1618 | |
| 1619 struct RegExpCompileData { | |
| 1620 RegExpCompileData() | |
| 1621 : tree(NULL), | |
| 1622 node(NULL), | |
| 1623 simple(true), | |
| 1624 contains_anchor(false), | |
| 1625 capture_count(0) { } | |
| 1626 RegExpTree* tree; | |
| 1627 RegExpNode* node; | |
| 1628 bool simple; | |
| 1629 bool contains_anchor; | |
| 1630 Handle<String> error; | |
| 1631 int capture_count; | |
| 1632 }; | |
| 1633 | |
| 1634 | |
| 1635 class RegExpEngine: public AllStatic { | |
| 1636 public: | |
| 1637 struct CompilationResult { | |
| 1638 CompilationResult(Isolate* isolate, const char* error_message) | |
| 1639 : error_message(error_message), | |
| 1640 code(isolate->heap()->the_hole_value()), | |
| 1641 num_registers(0) {} | |
| 1642 CompilationResult(Object* code, int registers) | |
| 1643 : error_message(NULL), code(code), num_registers(registers) {} | |
| 1644 const char* error_message; | |
| 1645 Object* code; | |
| 1646 int num_registers; | |
| 1647 }; | |
| 1648 | |
| 1649 static CompilationResult Compile(Isolate* isolate, Zone* zone, | |
| 1650 RegExpCompileData* input, bool ignore_case, | |
| 1651 bool global, bool multiline, bool sticky, | |
| 1652 Handle<String> pattern, | |
| 1653 Handle<String> sample_subject, | |
| 1654 bool is_one_byte); | |
| 1655 | |
| 1656 static bool TooMuchRegExpCode(Handle<String> pattern); | |
| 1657 | |
| 1658 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); | |
| 1659 }; | |
| 1660 | |
| 1661 | |
| 1662 } } // namespace v8::internal | |
| 1663 | |
| 1664 #endif // V8_JSREGEXP_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1285163003:
Move regexp implementation into its own folder. (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master