Attempt to make \b\w+ faster. Slight performance increase on, e.g., string unpacking.

src/jsregexp.h

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 149 matching lines @@
   // A one element cache of the last utf8_subject string and its length.  The
   // subject JS String object is cached in the heap.  We also cache a
   // translation between position and utf8 position.
   static char* utf8_subject_cache_;
   static int utf8_length_cache_;
   static int utf8_position_;
   static int character_position_;
 };
 
 
+// Represents the location of one element relative to the intersection of
+// two sets. Corresponds to the four areas of a Venn diagram.
+enum ElementInSetsRelation {
+  kInsideNone = 0,
+  kInsideFirst = 1,
+  kInsideSecond = 2,
+  kInsideBoth = 3
+};
+
+
+// Represents the relation of two sets.
+// Sets can be either disjoint, partially or fully overlapping, or equal.
+class SetRelation BASE_EMBEDDED {
+ public:
+  // Relation is represented by a bit saying whether there are elements in
+  // one set that is not in the other, and a bit saying that there are elements
+  // that are in both sets.
+
+  // Location of an element. Corresponds to the internal areas of
+  // a Venn diagram.
+  enum {
+    kInFirst = 1 << kInsideFirst,
+    kInSecond = 1 << kInsideSecond,
+    kInBoth = 1 << kInsideBoth
+  };
+  SetRelation() : bits_(0) {}
+  ~SetRelation() {}
+  // Add the existence of objects in a particular
+  void SetElementsInFirstSet() { bits_ |= kInFirst; }
+  void SetElementsInSecondSet() { bits_ |= kInSecond; }
+  void SetElementsInBothSets() { bits_ |= kInBoth; }
+  // Check the currently known relation of the sets (common functions only,
+  // for other combinations, use value() to get the bits and check them
+  // manually).
+  // Sets are completely disjoint.
+  bool Disjoint() { return (bits_ & kInBoth) == 0; }
+  // Sets are equal.
+  bool Equals() { return (bits_ & (kInFirst | kInSecond)) == 0; }
+  // First set contains second.
+  bool Contains() { return (bits_ & kInSecond) == 0; }
+  // Second set contains first.
+  bool ContainedIn() { return (bits_ & kInFirst) == 0; }
+  bool NonTrivialIntersection() {
+    return (bits_ == (kInFirst | kInSecond | kInBoth));
+  }
+  int value() { return bits_; }
+ private:
+  int bits_;
+};
+
+
 class CharacterRange {
  public:
   CharacterRange() : from_(0), to_(0) { }
   // For compatibility with the CHECK_OK macro
   CharacterRange(void* null) { ASSERT_EQ(NULL, null); }  //NOLINT
   CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { }
   static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges);
   static Vector<const uc16> GetWordBounds();
   static inline CharacterRange Singleton(uc16 value) {
     return CharacterRange(value, value);
@@ skipping 11 matching lines @@
   uc16 to() const { return to_; }
   void set_to(uc16 value) { to_ = value; }
   bool is_valid() { return from_ <= to_; }
   bool IsEverything(uc16 max) { return from_ == 0 && to_ >= max; }
   bool IsSingleton() { return (from_ == to_); }
   void AddCaseEquivalents(ZoneList<CharacterRange>* ranges, bool is_ascii);
   static void Split(ZoneList<CharacterRange>* base,
                     Vector<const uc16> overlay,
                     ZoneList<CharacterRange>** included,
                     ZoneList<CharacterRange>** excluded);
-
+  // Whether a range list is in canonical form: Ranges ordered by from value,
+  // and ranges non-overlapping and non-adjacent.
+  static bool IsCanonical(ZoneList<CharacterRange>* ranges);
+  // Convert range list to canonical form. The characters covered by the ranges
+  // will still be the same, but no character is in more than one range, and
+  // adjacent ranges are merged. The resulting list may be shorter than the
+  // original, but cannot be longer.
+  static void Canonicalize(ZoneList<CharacterRange>* ranges);
+  // Check how the set of characters defined by a CharacterRange list relates
+  // to the set of word characters. List must be in canonical form.
+  static SetRelation WordCharacterRelation(ZoneList<CharacterRange>* ranges);
+  // Takes two character range lists (representing character sets) in canonical
+  // form and merges them.
+  // The characters that are only covered by the first set are added to
+  // first_set_only_out. the characters that are only in the second set are
+  // added to second_set_only_out, and the characters that are in both are
+  // added to both_sets_out.
+  // The pointers to first_set_only_out, second_set_only_out and both_sets_out
+  // should be to empty lists, but they need not be distinct, and may be NULL.
+  // If NULL, the characters are dropped, and if two arguments are the same
+  // pointer, the result is the union of the two sets that would be created
+  // if the pointers had been distinct.
+  // This way, the Merge function can compute all the usual set operations:
+  // union (all three out-sets are equal), intersection (only both_sets_out is
+  // non-NULL), and set difference (only first_set is non-NULL).
+  static void Merge(ZoneList<CharacterRange>* first_set,
+                    ZoneList<CharacterRange>* second_set,
+                    ZoneList<CharacterRange>* first_set_only_out,
+                    ZoneList<CharacterRange>* second_set_only_out,
+                    ZoneList<CharacterRange>* both_sets_out);
+  // Negate the contents of a character range in canonical form.
+  static void Negate(ZoneList<CharacterRange>* src,
+                     ZoneList<CharacterRange>* dst);
   static const int kRangeCanonicalizeMax = 0x346;
   static const int kStartMarker = (1 << 24);
   static const int kPayloadMask = (1 << 24) - 1;
 
  private:
   uc16 from_;
   uc16 to_;
 };
 
 
@@ skipping 253 matching lines @@
   uint32_t mask_;
   uint32_t value_;
   // If set to true, there is no way this quick check can match at all.
   // E.g., if it requires to be at the start of the input, and isn't.
   bool cannot_match_;
 };
 
 
 class RegExpNode: public ZoneObject {
  public:
-  RegExpNode() : trace_count_(0) { }
+  RegExpNode() : first_character_set_(NULL), trace_count_(0) { }
   virtual ~RegExpNode();
   virtual void Accept(NodeVisitor* visitor) = 0;
   // Generates a goto to this node or actually generates the code at this point.
   virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0;
   // How many characters must this node consume at a minimum in order to
   // succeed.  If we have found at least 'still_to_find' characters that
   // must be consumed there is no need to ask any following nodes whether
   // they are sure to eat any more characters.
   virtual int EatsAtLeast(int still_to_find, int recursion_depth) = 0;
   // Emits some quick code that checks whether the preloaded characters match.
@@ skipping 30 matching lines @@
   // Static version of EnsureSibling that expresses the fact that the
   // result has the same type as the input.
   template <class C>
   static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) {
     return static_cast<C*>(node->EnsureSibling(info, cloned));
   }
 
   SiblingList* siblings() { return &siblings_; }
   void set_siblings(SiblingList* other) { siblings_ = *other; }
 
+  // Return the set of possible next characters recognized by the regexp
+  // (or a safe subset, potentially the set of all characters).
+  ZoneList<CharacterRange>* FirstCharacterSet();
+
+  // Compute (if possible within the budget of traversed nodes) the
+  // possible first characters of the input matched by this node and
+  // its continuation. Returns the remaining budget after the computation.
+  // If the budget is spent, the result is negative, and the cached
+  // first_character_set_ value isn't set.
+  virtual int ComputeFirstCharacterSet(int budget);
+
+  // Get and set the cached first character set value.
+  ZoneList<CharacterRange>* first_character_set() {
+    return first_character_set_;
+  }
+  void set_first_character_set(ZoneList<CharacterRange>* character_set) {
+    first_character_set_ = character_set;
+  }
+
  protected:
   enum LimitResult { DONE, CONTINUE };
+  static const int kComputeFirstCharacterSetFail = -1;
+
   LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace);
 
   // Returns a sibling of this node whose interests and assumptions
   // match the ones in the given node info.  If no sibling exists NULL
   // is returned.
   RegExpNode* TryGetSibling(NodeInfo* info);
 
   // Returns a sibling of this node whose interests match the ones in
   // the given node info.  The info must not contain any assertions.
   // If no node exists a new one will be created by cloning the current
   // node.  The result will always be an instance of the same concrete
   // class as this node.
   RegExpNode* EnsureSibling(NodeInfo* info, bool* cloned);
 
   // Returns a clone of this node initialized using the copy constructor
   // of its concrete class.  Note that the node may have to be pre-
   // processed before it is on a usable state.
   virtual RegExpNode* Clone() = 0;
 
  private:
+  static const int kFirstCharBudget = 10;
   Label label_;
   NodeInfo info_;
   SiblingList siblings_;
+  ZoneList<CharacterRange>* first_character_set_;
   // This variable keeps track of how many times code has been generated for
   // this node (in different traces).  We don't keep track of where the
   // generated code is located unless the code is generated at the start of
   // a trace, in which case it is generic and can be reused by flushing the
   // deferred operations in the current trace and generating a goto.
   int trace_count_;
 };
 
 
 // A simple closed interval.
@@ skipping 70 matching lines @@
                                     RegExpCompiler* compiler,
                                     int filled_in,
                                     bool not_at_start) {
     return on_success()->GetQuickCheckDetails(
         details, compiler, filled_in, not_at_start);
   }
   Type type() { return type_; }
   // TODO(erikcorry): We should allow some action nodes in greedy loops.
   virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
   virtual ActionNode* Clone() { return new ActionNode(*this); }
-
+  virtual int ComputeFirstCharacterSet(int budget);
  private:
   union {
     struct {
       int reg;
       int value;
     } u_store_register;
     struct {
       int reg;
     } u_increment_register;
     struct {
@@ skipping 45 matching lines @@
                                     bool not_at_start);
   ZoneList<TextElement>* elements() { return elms_; }
   void MakeCaseIndependent(bool is_ascii);
   virtual int GreedyLoopTextLength();
   virtual TextNode* Clone() {
     TextNode* result = new TextNode(*this);
     result->CalculateOffsets();
     return result;
   }
   void CalculateOffsets();
-
+  virtual int ComputeFirstCharacterSet(int budget);
  private:
   enum TextEmitPassType {
     NON_ASCII_MATCH,             // Check for characters that can't match.
     SIMPLE_CHARACTER_MATCH,      // Case-dependent single character check.
     NON_LETTER_CHARACTER_MATCH,  // Check characters that have no case equivs.
     CASE_CHARACTER_MATCH,        // Case-independent single character check.
     CHARACTER_CLASS_MATCH        // Character class.
   };
   static bool SkipPass(int pass, bool ignore_case);
   static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH;
   static const int kLastPass = CHARACTER_CLASS_MATCH;
   void TextEmitPass(RegExpCompiler* compiler,
                     TextEmitPassType pass,
                     bool preloaded,
                     Trace* trace,
                     bool first_element_checked,
                     int* checked_up_to);
   int Length();
   ZoneList<TextElement>* elms_;
 };
 
 
 class AssertionNode: public SeqRegExpNode {
  public:
   enum AssertionNodeType {
     AT_END,
     AT_START,
     AT_BOUNDARY,
     AT_NON_BOUNDARY,
-    AFTER_NEWLINE
+    AFTER_NEWLINE,
+    // Types not directly expressible in regexp syntax.
+    // Used for modifying a boundary node if its following character is
+    // known to be word and/or non-word.
+    AFTER_NONWORD_CHARACTER,
+    AFTER_WORD_CHARACTER
   };
   static AssertionNode* AtEnd(RegExpNode* on_success) {
     return new AssertionNode(AT_END, on_success);
   }
   static AssertionNode* AtStart(RegExpNode* on_success) {
     return new AssertionNode(AT_START, on_success);
   }
   static AssertionNode* AtBoundary(RegExpNode* on_success) {
     return new AssertionNode(AT_BOUNDARY, on_success);
   }
   static AssertionNode* AtNonBoundary(RegExpNode* on_success) {
     return new AssertionNode(AT_NON_BOUNDARY, on_success);
   }
   static AssertionNode* AfterNewline(RegExpNode* on_success) {
     return new AssertionNode(AFTER_NEWLINE, on_success);
   }
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int filled_in,
                                     bool not_at_start);
+  virtual int ComputeFirstCharacterSet(int budget);
   virtual AssertionNode* Clone() { return new AssertionNode(*this); }
   AssertionNodeType type() { return type_; }
+  void set_type(AssertionNodeType type) { type_ = type; }
  private:
   AssertionNode(AssertionNodeType t, RegExpNode* on_success)
       : SeqRegExpNode(on_success), type_(t) { }
   AssertionNodeType type_;
 };
 
 
 class BackReferenceNode: public SeqRegExpNode {
  public:
   BackReferenceNode(int start_reg,
                     int end_reg,
                     RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         start_reg_(start_reg),
         end_reg_(end_reg) { }
   virtual void Accept(NodeVisitor* visitor);
   int start_register() { return start_reg_; }
   int end_register() { return end_reg_; }
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start) {
     return;
   }
   virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }
-
+  virtual int ComputeFirstCharacterSet(int budget);
  private:
   int start_reg_;
   int end_reg_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
   explicit EndNode(Action action) : action_(action) { }
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth) { return 0; }
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start) {
     // Returning 0 from EatsAtLeast should ensure we never get here.
     UNREACHABLE();
   }
   virtual EndNode* Clone() { return new EndNode(*this); }
-
  private:
   Action action_;
 };
 
 
 class NegativeSubmatchSuccess: public EndNode {
  public:
   NegativeSubmatchSuccess(int stack_pointer_reg,
                           int position_reg,
                           int clear_capture_count,
@@ skipping 113 matching lines @@
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start);
   // For a negative lookahead we don't emit the quick check for the
   // alternative that is expected to fail.  This is because quick check code
   // starts by loading enough characters for the alternative that takes fewest
   // characters, but on a negative lookahead the negative branch did not take
   // part in that calculation (EatsAtLeast) so the assumptions don't hold.
   virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; }
+  virtual int ComputeFirstCharacterSet(int budget);
 };
 
 
 class LoopChoiceNode: public ChoiceNode {
  public:
   explicit LoopChoiceNode(bool body_can_be_zero_length)
       : ChoiceNode(2),
         loop_node_(NULL),
         continue_node_(NULL),
         body_can_be_zero_length_(body_can_be_zero_length) { }
   void AddLoopAlternative(GuardedAlternative alt);
   void AddContinueAlternative(GuardedAlternative alt);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start);
+  virtual int ComputeFirstCharacterSet(int budget);
   virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); }
   RegExpNode* loop_node() { return loop_node_; }
   RegExpNode* continue_node() { return continue_node_; }
   bool body_can_be_zero_length() { return body_can_be_zero_length_; }
   virtual void Accept(NodeVisitor* visitor);
 
  private:
   // AddAlternative is made private for loop nodes because alternatives
   // should not be added freely, we need to keep track of which node
   // goes back to the node itself.
@@ skipping 135 matching lines @@
   // These set methods and AdvanceCurrentPositionInTrace should be used only on
   // new traces - the intention is that traces are immutable after creation.
   void add_action(DeferredAction* new_action) {
     ASSERT(new_action->next_ == NULL);
     new_action->next_ = actions_;
     actions_ = new_action;
   }
   void set_backtrack(Label* backtrack) { backtrack_ = backtrack; }
   void set_stop_node(RegExpNode* node) { stop_node_ = node; }
   void set_loop_label(Label* label) { loop_label_ = label; }
-  void set_characters_preloaded(int cpre) { characters_preloaded_ = cpre; }
+  void set_characters_preloaded(int count) { characters_preloaded_ = count; }
   void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; }
   void set_flush_budget(int to) { flush_budget_ = to; }
   void set_quick_check_performed(QuickCheckDetails* d) {
     quick_check_performed_ = *d;
   }
   void InvalidateCurrentCharacter();
   void AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler);
  private:
   int FindAffectedRegisters(OutSet* affected_registers);
   void PerformDeferredActions(RegExpMacroAssembler* macro,
@@ skipping 142 matching lines @@
                                    Handle<String> pattern,
                                    bool is_ascii);
 
   static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_