| OLD | NEW |
| 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 165 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 176 static int utf8_position_; | 176 static int utf8_position_; |
| 177 static int character_position_; | 177 static int character_position_; |
| 178 }; | 178 }; |
| 179 | 179 |
| 180 | 180 |
| 181 class CharacterRange { | 181 class CharacterRange { |
| 182 public: | 182 public: |
| 183 CharacterRange() : from_(0), to_(0) { } | 183 CharacterRange() : from_(0), to_(0) { } |
| 184 // For compatibility with the CHECK_OK macro | 184 // For compatibility with the CHECK_OK macro |
| 185 CharacterRange(void* null) { ASSERT_EQ(NULL, null); } //NOLINT | 185 CharacterRange(void* null) { ASSERT_EQ(NULL, null); } //NOLINT |
| 186 CharacterRange(uc16 from, uc16 to) | 186 CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { } |
| 187 : from_(from), | |
| 188 to_(to) { | |
| 189 } | |
| 190 static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges); | 187 static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges); |
| 191 static inline CharacterRange Singleton(uc16 value) { | 188 static inline CharacterRange Singleton(uc16 value) { |
| 192 return CharacterRange(value, value); | 189 return CharacterRange(value, value); |
| 193 } | 190 } |
| 194 static inline CharacterRange Range(uc16 from, uc16 to) { | 191 static inline CharacterRange Range(uc16 from, uc16 to) { |
| 195 ASSERT(from <= to); | 192 ASSERT(from <= to); |
| 196 return CharacterRange(from, to); | 193 return CharacterRange(from, to); |
| 197 } | 194 } |
| 198 static inline CharacterRange Everything() { | 195 static inline CharacterRange Everything() { |
| 199 return CharacterRange(0, 0xFFFF); | 196 return CharacterRange(0, 0xFFFF); |
| (...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 269 | 266 |
| 270 // Perform the splay operation for the given key. Moves the node with | 267 // Perform the splay operation for the given key. Moves the node with |
| 271 // the given key to the top of the tree. If no node has the given | 268 // the given key to the top of the tree. If no node has the given |
| 272 // key, the last node on the search path is moved to the top of the | 269 // key, the last node on the search path is moved to the top of the |
| 273 // tree. | 270 // tree. |
| 274 void Splay(const Key& key); | 271 void Splay(const Key& key); |
| 275 | 272 |
| 276 class Node : public ZoneObject { | 273 class Node : public ZoneObject { |
| 277 public: | 274 public: |
| 278 Node(const Key& key, const Value& value) | 275 Node(const Key& key, const Value& value) |
| 279 : key_(key), | 276 : key_(key), |
| 280 value_(value), | 277 value_(value), |
| 281 left_(NULL), | 278 left_(NULL), |
| 282 right_(NULL) { } | 279 right_(NULL) { } |
| 283 Key key() { return key_; } | 280 Key key() { return key_; } |
| 284 Value value() { return value_; } | 281 Value value() { return value_; } |
| 285 Node* left() { return left_; } | 282 Node* left() { return left_; } |
| 286 Node* right() { return right_; } | 283 Node* right() { return right_; } |
| 287 private: | 284 private: |
| 288 friend class ZoneSplayTree; | 285 friend class ZoneSplayTree; |
| 289 friend class Locator; | 286 friend class Locator; |
| 290 Key key_; | 287 Key key_; |
| 291 Value value_; | 288 Value value_; |
| 292 Node* left_; | 289 Node* left_; |
| 293 Node* right_; | 290 Node* right_; |
| 294 }; | 291 }; |
| 295 | 292 |
| 296 // A locator provides access to a node in the tree without actually | 293 // A locator provides access to a node in the tree without actually |
| (...skipping 21 matching lines...) Expand all Loading... |
| 318 | 315 |
| 319 | 316 |
| 320 // A set of unsigned integers that behaves especially well on small | 317 // A set of unsigned integers that behaves especially well on small |
| 321 // integers (< 32). May do zone-allocation. | 318 // integers (< 32). May do zone-allocation. |
| 322 class OutSet: public ZoneObject { | 319 class OutSet: public ZoneObject { |
| 323 public: | 320 public: |
| 324 OutSet() : first_(0), remaining_(NULL), successors_(NULL) { } | 321 OutSet() : first_(0), remaining_(NULL), successors_(NULL) { } |
| 325 OutSet* Extend(unsigned value); | 322 OutSet* Extend(unsigned value); |
| 326 bool Get(unsigned value); | 323 bool Get(unsigned value); |
| 327 static const unsigned kFirstLimit = 32; | 324 static const unsigned kFirstLimit = 32; |
| 325 |
| 328 private: | 326 private: |
| 329 | |
| 330 // Destructively set a value in this set. In most cases you want | 327 // Destructively set a value in this set. In most cases you want |
| 331 // to use Extend instead to ensure that only one instance exists | 328 // to use Extend instead to ensure that only one instance exists |
| 332 // that contains the same values. | 329 // that contains the same values. |
| 333 void Set(unsigned value); | 330 void Set(unsigned value); |
| 334 | 331 |
| 335 // The successors are a list of sets that contain the same values | 332 // The successors are a list of sets that contain the same values |
| 336 // as this set and the one more value that is not present in this | 333 // as this set and the one more value that is not present in this |
| 337 // set. | 334 // set. |
| 338 ZoneList<OutSet*>* successors() { return successors_; } | 335 ZoneList<OutSet*>* successors() { return successors_; } |
| 339 | 336 |
| 340 OutSet(uint32_t first, ZoneList<unsigned>* remaining) | 337 OutSet(uint32_t first, ZoneList<unsigned>* remaining) |
| 341 : first_(first), remaining_(remaining), successors_(NULL) { } | 338 : first_(first), remaining_(remaining), successors_(NULL) { } |
| 342 uint32_t first_; | 339 uint32_t first_; |
| 343 ZoneList<unsigned>* remaining_; | 340 ZoneList<unsigned>* remaining_; |
| 344 ZoneList<OutSet*>* successors_; | 341 ZoneList<OutSet*>* successors_; |
| 345 }; | 342 }; |
| 346 | 343 |
| 347 | 344 |
| 348 // A mapping from integers, specified as ranges, to a set of integers. | 345 // A mapping from integers, specified as ranges, to a set of integers. |
| 349 // Used for mapping character ranges to choices. | 346 // Used for mapping character ranges to choices. |
| 350 class DispatchTable { | 347 class DispatchTable { |
| 351 public: | 348 public: |
| 352 class Entry { | 349 class Entry { |
| 353 public: | 350 public: |
| 354 Entry() | 351 Entry() : from_(0), to_(0), out_set_(NULL) { } |
| 355 : from_(0), to_(0), out_set_(NULL) { } | |
| 356 Entry(uc16 from, uc16 to, OutSet* out_set) | 352 Entry(uc16 from, uc16 to, OutSet* out_set) |
| 357 : from_(from), to_(to), out_set_(out_set) { } | 353 : from_(from), to_(to), out_set_(out_set) { } |
| 358 uc16 from() { return from_; } | 354 uc16 from() { return from_; } |
| 359 uc16 to() { return to_; } | 355 uc16 to() { return to_; } |
| 360 void set_to(uc16 value) { to_ = value; } | 356 void set_to(uc16 value) { to_ = value; } |
| 361 void AddValue(int value) { out_set_ = out_set_->Extend(value); } | 357 void AddValue(int value) { out_set_ = out_set_->Extend(value); } |
| 362 OutSet* out_set() { return out_set_; } | 358 OutSet* out_set() { return out_set_; } |
| 363 private: | 359 private: |
| 364 uc16 from_; | 360 uc16 from_; |
| 365 uc16 to_; | 361 uc16 to_; |
| 366 OutSet* out_set_; | 362 OutSet* out_set_; |
| 367 }; | 363 }; |
| (...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 435 Type type; | 431 Type type; |
| 436 union { | 432 union { |
| 437 RegExpAtom* u_atom; | 433 RegExpAtom* u_atom; |
| 438 RegExpCharacterClass* u_char_class; | 434 RegExpCharacterClass* u_char_class; |
| 439 } data; | 435 } data; |
| 440 }; | 436 }; |
| 441 | 437 |
| 442 | 438 |
| 443 struct NodeInfo { | 439 struct NodeInfo { |
| 444 NodeInfo() | 440 NodeInfo() |
| 445 : being_analyzed(false), | 441 : being_analyzed(false), |
| 446 been_analyzed(false), | 442 been_analyzed(false), |
| 447 determine_word(false), | 443 determine_word(false), |
| 448 determine_newline(false), | 444 determine_newline(false), |
| 449 determine_start(false), | 445 determine_start(false), |
| 450 follows_word_interest(false), | 446 follows_word_interest(false), |
| 451 follows_newline_interest(false), | 447 follows_newline_interest(false), |
| 452 follows_start_interest(false) { } | 448 follows_start_interest(false) { } |
| 453 bool SameInterests(NodeInfo* that) { | 449 bool SameInterests(NodeInfo* that) { |
| 454 return (follows_word_interest == that->follows_word_interest) | 450 return (follows_word_interest == that->follows_word_interest) |
| 455 && (follows_newline_interest == that->follows_newline_interest) | 451 && (follows_newline_interest == that->follows_newline_interest) |
| 456 && (follows_start_interest == that->follows_start_interest); | 452 && (follows_start_interest == that->follows_start_interest); |
| 457 } | 453 } |
| 458 void AdoptInterests(NodeInfo* that) { | 454 void AdoptInterests(NodeInfo* that) { |
| 459 follows_word_interest = that->follows_word_interest; | 455 follows_word_interest = that->follows_word_interest; |
| 460 follows_newline_interest = that->follows_newline_interest; | 456 follows_newline_interest = that->follows_newline_interest; |
| 461 follows_start_interest = that->follows_start_interest; | 457 follows_start_interest = that->follows_start_interest; |
| 462 } | 458 } |
| (...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 526 private: | 522 private: |
| 527 Label label_; | 523 Label label_; |
| 528 NodeInfo info_; | 524 NodeInfo info_; |
| 529 SiblingList siblings_; | 525 SiblingList siblings_; |
| 530 }; | 526 }; |
| 531 | 527 |
| 532 | 528 |
| 533 class SeqRegExpNode: public RegExpNode { | 529 class SeqRegExpNode: public RegExpNode { |
| 534 public: | 530 public: |
| 535 explicit SeqRegExpNode(RegExpNode* on_success) | 531 explicit SeqRegExpNode(RegExpNode* on_success) |
| 536 : on_success_(on_success) { } | 532 : on_success_(on_success) { } |
| 537 RegExpNode* on_success() { return on_success_; } | 533 RegExpNode* on_success() { return on_success_; } |
| 538 void set_on_success(RegExpNode* node) { on_success_ = node; } | 534 void set_on_success(RegExpNode* node) { on_success_ = node; } |
| 539 virtual bool Emit(RegExpCompiler* compiler) { return false; } | 535 virtual bool Emit(RegExpCompiler* compiler) { return false; } |
| 540 private: | 536 private: |
| 541 RegExpNode* on_success_; | 537 RegExpNode* on_success_; |
| 542 }; | 538 }; |
| 543 | 539 |
| 544 | 540 |
| 545 class ActionNode: public SeqRegExpNode { | 541 class ActionNode: public SeqRegExpNode { |
| 546 public: | 542 public: |
| (...skipping 26 matching lines...) Expand all Loading... |
| 573 int reg; | 569 int reg; |
| 574 } u_increment_register; | 570 } u_increment_register; |
| 575 struct { | 571 struct { |
| 576 int reg; | 572 int reg; |
| 577 } u_position_register; | 573 } u_position_register; |
| 578 struct { | 574 struct { |
| 579 int reg; | 575 int reg; |
| 580 } u_submatch_stack_pointer_register; | 576 } u_submatch_stack_pointer_register; |
| 581 } data_; | 577 } data_; |
| 582 ActionNode(Type type, RegExpNode* on_success) | 578 ActionNode(Type type, RegExpNode* on_success) |
| 583 : SeqRegExpNode(on_success), | 579 : SeqRegExpNode(on_success), |
| 584 type_(type) { } | 580 type_(type) { } |
| 585 Type type_; | 581 Type type_; |
| 586 friend class DotPrinter; | 582 friend class DotPrinter; |
| 587 }; | 583 }; |
| 588 | 584 |
| 589 | 585 |
| 590 class TextNode: public SeqRegExpNode { | 586 class TextNode: public SeqRegExpNode { |
| 591 public: | 587 public: |
| 592 TextNode(ZoneList<TextElement>* elms, | 588 TextNode(ZoneList<TextElement>* elms, |
| 593 RegExpNode* on_success, | 589 RegExpNode* on_success, |
| 594 RegExpNode* on_failure) | 590 RegExpNode* on_failure) |
| 595 : SeqRegExpNode(on_success), | 591 : SeqRegExpNode(on_success), |
| 596 on_failure_(on_failure), | 592 on_failure_(on_failure), |
| 597 elms_(elms) { } | 593 elms_(elms) { } |
| 598 virtual void Accept(NodeVisitor* visitor); | 594 virtual void Accept(NodeVisitor* visitor); |
| 599 virtual RegExpNode* PropagateInterest(NodeInfo* info); | 595 virtual RegExpNode* PropagateInterest(NodeInfo* info); |
| 600 RegExpNode* on_failure() { return on_failure_; } | 596 RegExpNode* on_failure() { return on_failure_; } |
| 601 virtual bool Emit(RegExpCompiler* compiler); | 597 virtual bool Emit(RegExpCompiler* compiler); |
| 602 ZoneList<TextElement>* elements() { return elms_; } | 598 ZoneList<TextElement>* elements() { return elms_; } |
| 603 private: | 599 private: |
| 604 RegExpNode* on_failure_; | 600 RegExpNode* on_failure_; |
| 605 ZoneList<TextElement>* elms_; | 601 ZoneList<TextElement>* elms_; |
| 606 }; | 602 }; |
| 607 | 603 |
| 608 | 604 |
| 609 class BackReferenceNode: public SeqRegExpNode { | 605 class BackReferenceNode: public SeqRegExpNode { |
| 610 public: | 606 public: |
| 611 BackReferenceNode(int start_reg, | 607 BackReferenceNode(int start_reg, |
| 612 int end_reg, | 608 int end_reg, |
| 613 RegExpNode* on_success, | 609 RegExpNode* on_success, |
| 614 RegExpNode* on_failure) | 610 RegExpNode* on_failure) |
| 615 : SeqRegExpNode(on_success), | 611 : SeqRegExpNode(on_success), |
| 616 on_failure_(on_failure), | 612 on_failure_(on_failure), |
| 617 start_reg_(start_reg), | 613 start_reg_(start_reg), |
| 618 end_reg_(end_reg) { } | 614 end_reg_(end_reg) { } |
| 619 virtual void Accept(NodeVisitor* visitor); | 615 virtual void Accept(NodeVisitor* visitor); |
| 620 RegExpNode* on_failure() { return on_failure_; } | 616 RegExpNode* on_failure() { return on_failure_; } |
| 621 int start_register() { return start_reg_; } | 617 int start_register() { return start_reg_; } |
| 622 int end_register() { return end_reg_; } | 618 int end_register() { return end_reg_; } |
| 623 virtual bool Emit(RegExpCompiler* compiler); | 619 virtual bool Emit(RegExpCompiler* compiler); |
| 624 virtual RegExpNode* PropagateInterest(NodeInfo* info); | 620 virtual RegExpNode* PropagateInterest(NodeInfo* info); |
| 625 private: | 621 private: |
| 626 RegExpNode* on_failure_; | 622 RegExpNode* on_failure_; |
| 627 int start_reg_; | 623 int start_reg_; |
| 628 int end_reg_; | 624 int end_reg_; |
| (...skipping 11 matching lines...) Expand all Loading... |
| 640 virtual bool GoTo(RegExpCompiler* compiler); | 636 virtual bool GoTo(RegExpCompiler* compiler); |
| 641 private: | 637 private: |
| 642 Action action_; | 638 Action action_; |
| 643 }; | 639 }; |
| 644 | 640 |
| 645 | 641 |
| 646 class Guard: public ZoneObject { | 642 class Guard: public ZoneObject { |
| 647 public: | 643 public: |
| 648 enum Relation { LT, GEQ }; | 644 enum Relation { LT, GEQ }; |
| 649 Guard(int reg, Relation op, int value) | 645 Guard(int reg, Relation op, int value) |
| 650 : reg_(reg), | 646 : reg_(reg), |
| 651 op_(op), | 647 op_(op), |
| 652 value_(value) { } | 648 value_(value) { } |
| 653 int reg() { return reg_; } | 649 int reg() { return reg_; } |
| 654 Relation op() { return op_; } | 650 Relation op() { return op_; } |
| 655 int value() { return value_; } | 651 int value() { return value_; } |
| 656 private: | 652 private: |
| 657 int reg_; | 653 int reg_; |
| 658 Relation op_; | 654 Relation op_; |
| 659 int value_; | 655 int value_; |
| 660 }; | 656 }; |
| 661 | 657 |
| 662 | 658 |
| 663 class GuardedAlternative { | 659 class GuardedAlternative { |
| 664 public: | 660 public: |
| 665 explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { } | 661 explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { } |
| 666 void AddGuard(Guard* guard); | 662 void AddGuard(Guard* guard); |
| 667 RegExpNode* node() { return node_; } | 663 RegExpNode* node() { return node_; } |
| 668 void set_node(RegExpNode* node) { node_ = node; } | 664 void set_node(RegExpNode* node) { node_ = node; } |
| 669 ZoneList<Guard*>* guards() { return guards_; } | 665 ZoneList<Guard*>* guards() { return guards_; } |
| 670 private: | 666 private: |
| 671 RegExpNode* node_; | 667 RegExpNode* node_; |
| 672 ZoneList<Guard*>* guards_; | 668 ZoneList<Guard*>* guards_; |
| 673 }; | 669 }; |
| 674 | 670 |
| 675 | 671 |
| 676 class ChoiceNode: public RegExpNode { | 672 class ChoiceNode: public RegExpNode { |
| 677 public: | 673 public: |
| 678 explicit ChoiceNode(int expected_size, RegExpNode* on_failure) | 674 explicit ChoiceNode(int expected_size, RegExpNode* on_failure) |
| 679 : on_failure_(on_failure), | 675 : on_failure_(on_failure), |
| 680 alternatives_(new ZoneList<GuardedAlternative>(expected_size)), | 676 alternatives_(new ZoneList<GuardedAlternative>(expected_size)), |
| 681 table_calculated_(false), | 677 table_calculated_(false), |
| 682 being_calculated_(false) { } | 678 being_calculated_(false) { } |
| 683 virtual void Accept(NodeVisitor* visitor); | 679 virtual void Accept(NodeVisitor* visitor); |
| 684 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); } | 680 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); } |
| 685 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } | 681 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } |
| 686 DispatchTable* table() { return &table_; } | 682 DispatchTable* table() { return &table_; } |
| 687 RegExpNode* on_failure() { return on_failure_; } | 683 RegExpNode* on_failure() { return on_failure_; } |
| 688 virtual bool Emit(RegExpCompiler* compiler); | 684 virtual bool Emit(RegExpCompiler* compiler); |
| 689 virtual RegExpNode* PropagateInterest(NodeInfo* info); | 685 virtual RegExpNode* PropagateInterest(NodeInfo* info); |
| 690 bool table_calculated() { return table_calculated_; } | 686 bool table_calculated() { return table_calculated_; } |
| 691 void set_table_calculated(bool b) { table_calculated_ = b; } | 687 void set_table_calculated(bool b) { table_calculated_ = b; } |
| 692 bool being_calculated() { return being_calculated_; } | 688 bool being_calculated() { return being_calculated_; } |
| (...skipping 18 matching lines...) Expand all Loading... |
| 711 FOR_EACH_NODE_TYPE(DECLARE_VISIT) | 707 FOR_EACH_NODE_TYPE(DECLARE_VISIT) |
| 712 #undef DECLARE_VISIT | 708 #undef DECLARE_VISIT |
| 713 }; | 709 }; |
| 714 | 710 |
| 715 | 711 |
| 716 // Node visitor used to add the start set of the alternatives to the | 712 // Node visitor used to add the start set of the alternatives to the |
| 717 // dispatch table of a choice node. | 713 // dispatch table of a choice node. |
| 718 class DispatchTableConstructor: public NodeVisitor { | 714 class DispatchTableConstructor: public NodeVisitor { |
| 719 public: | 715 public: |
| 720 explicit DispatchTableConstructor(DispatchTable* table) | 716 explicit DispatchTableConstructor(DispatchTable* table) |
| 721 : table_(table), | 717 : table_(table), |
| 722 choice_index_(-1) { } | 718 choice_index_(-1) { } |
| 723 | 719 |
| 724 void BuildTable(ChoiceNode* node); | 720 void BuildTable(ChoiceNode* node); |
| 725 | 721 |
| 726 void AddRange(CharacterRange range) { | 722 void AddRange(CharacterRange range) { |
| 727 table()->AddRange(range, choice_index_); | 723 table()->AddRange(range, choice_index_); |
| 728 } | 724 } |
| 729 | 725 |
| 730 void AddInverse(ZoneList<CharacterRange>* ranges); | 726 void AddInverse(ZoneList<CharacterRange>* ranges); |
| 731 | 727 |
| 732 #define DECLARE_VISIT(Type) \ | 728 #define DECLARE_VISIT(Type) \ |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 767 static Handle<FixedArray> Compile(RegExpParseResult* input, | 763 static Handle<FixedArray> Compile(RegExpParseResult* input, |
| 768 RegExpNode** node_return, | 764 RegExpNode** node_return, |
| 769 bool ignore_case); | 765 bool ignore_case); |
| 770 static void DotPrint(const char* label, RegExpNode* node); | 766 static void DotPrint(const char* label, RegExpNode* node); |
| 771 }; | 767 }; |
| 772 | 768 |
| 773 | 769 |
| 774 } } // namespace v8::internal | 770 } } // namespace v8::internal |
| 775 | 771 |
| 776 #endif // V8_JSREGEXP_H_ | 772 #endif // V8_JSREGEXP_H_ |
| OLD | NEW |