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