Regexp: Unify the lookahead code for the BoyerMoore-like skipping

src/jsregexp.h

 // Copyright 2012 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 22 matching lines @@
 #include "zone-inl.h"
 
 namespace v8 {
 namespace internal {
 
 class NodeVisitor;
 class RegExpCompiler;
 class RegExpMacroAssembler;
 class RegExpNode;
 class RegExpTree;
+class BoyerMooreLookahead;
 
 class RegExpImpl {
  public:
   // Whether V8 is compiled with native regexp support or not.
   static bool UsesNativeRegExp() {
 #ifdef V8_INTERPRETED_REGEXP
     return false;
 #else
     return true;
 #endif
@@ skipping 164 matching lines @@
 // 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 Vector<const int> GetWordBounds();
   static inline CharacterRange Singleton(uc16 value) {
     return CharacterRange(value, value);
   }
   static inline CharacterRange Range(uc16 from, uc16 to) {
     ASSERT(from <= to);
     return CharacterRange(from, to);
   }
   static inline CharacterRange Everything() {
     return CharacterRange(0, 0xFFFF);
   }
   bool Contains(uc16 i) { return from_ <= i && i <= to_; }
   uc16 from() const { return from_; }
   void set_from(uc16 value) { from_ = value; }
   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,
+                    Vector<const int> 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 kStartMarker = (1 << 24);
   static const int kPayloadMask = (1 << 24) - 1;
 
  private:
   uc16 from_;
   uc16 to_;
 };
@@ skipping 74 matching lines @@
  private:
   // There can't be a static empty set since it allocates its
   // successors in a zone and caches them.
   OutSet* empty() { return &empty_; }
   OutSet empty_;
   ZoneSplayTree<Config>* tree() { return &tree_; }
   ZoneSplayTree<Config> tree_;
 };
 
 
-// Improve the speed that we scan for an initial point where a non-anchored
-// regexp can match by using a Boyer-Moore-like table. This is done by
-// identifying non-greedy non-capturing loops in the nodes that eat any
-// character one at a time.  For example in the middle of the regexp
-// /foo[\s\S]*?bar/ we find such a loop.  There is also such a loop implicitly
-// inserted at the start of any non-anchored regexp.
-//
-// When we have found such a loop we look ahead in the nodes to find the set of
-// characters that can come at given distances. For example for the regexp
-// /.?foo/ we know that there are at least 3 characters ahead of us, and the
-// sets of characters that can occur are [any, [f, o], [o]]. We find a range in
-// the lookahead info where the set of characters is reasonably constrained. In
-// our example this is from index 1 to 2 (0 is not constrained). We can now
-// look 3 characters ahead and if we don't find one of [f, o] (the union of
-// [f, o] and [o]) then we can skip forwards by the range size (in this case 2).
-//
-// For Unicode input strings we do the same, but modulo 128.
-//
-// We also look at the first string fed to the regexp and use that to get a hint
-// of the character frequencies in the inputs. This affects the assessment of
-// whether the set of characters is 'reasonably constrained'.
-//
-// We also have another lookahead mechanism (called quick check in the code),
-// which uses a wide load of multiple characters followed by a mask and compare
-// to determine whether a match is possible at this point.
-class BoyerMooreLookahead {
- public:
-  BoyerMooreLookahead(int length, int map_length, RegExpCompiler* compiler);
-
-  int length() { return length_; }
-  int max_char() { return max_char_; }
-  RegExpCompiler* compiler() { return compiler_; }
-
-  static const int kTooManyCharacters = 32;
-
-  int Count(int map_number) {
-    ZoneList<bool>* map = bitmaps_->at(map_number);
-    if (map == NULL) return map_length_;
-    int count = 0;
-    for (int i = 0; i < map_length_; i++) {
-      if (map->at(i)) count++;
-    }
-    return count;
-  }
-
-  void Set(int map_number, int character) {
-    if (character > max_char_) return;
-    ZoneList<bool>* map = bitmaps_->at(map_number);
-    if (map == NULL) return;
-    map->at(character & (map_length_ - 1)) = true;
-  }
-
-  void SetAll(int map_number) {
-    bitmaps_->at(map_number) = NULL;
-  }
-
-  void SetRest(int from_map) {
-    for (int i = from_map; i < length_; i++) SetAll(i);
-  }
-  bool EmitSkipInstructions(RegExpMacroAssembler* masm);
-
- private:
-  // This is the value obtained by EatsAtLeast.  If we do not have at least this
-  // many characters left in the sample string then the match is bound to fail.
-  // Therefore it is OK to read a character this far ahead of the current match
-  // point.
-  int length_;
-  // We conservatively consider all character values modulo this length.  For
-  // ASCII there is no loss of precision, since this has a value of 128.
-  int map_length_;
-  RegExpCompiler* compiler_;
-  // 0x7f for ASCII, 0xffff for UTF-16.
-  int max_char_;
-  ZoneList<ZoneList<bool>*>* bitmaps_;
-
-  int GetSkipTable(int min_lookahead,
-                   int max_lookahead,
-                   Handle<ByteArray> boolean_skip_table);
-  bool FindWorthwhileInterval(int* from, int* to);
-  int FindBestInterval(
-    int max_number_of_chars, int old_biggest_points, int* from, int* to);
-};
-
-
 #define FOR_EACH_NODE_TYPE(VISIT)                                    \
   VISIT(End)                                                         \
   VISIT(Action)                                                      \
   VISIT(Choice)                                                      \
   VISIT(BackReference)                                               \
   VISIT(Assertion)                                                   \
   VISIT(Text)
 
 
 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT)                            \
@@ skipping 162 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() : first_character_set_(NULL), trace_count_(0) { }
+  RegExpNode() : first_character_set_(NULL), trace_count_(0) {
+    bm_info_[0] = bm_info_[1] = NULL;
+  }
   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.  The not_at_start argument is
   // used to indicate that we know we are not at the start of the input.  In
   // this case anchored branches will always fail and can be ignored when
@@ skipping 23 matching lines @@
   // Only returns the successor for a text node of length 1 that matches any
   // character and that has no guards on it.
   virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
       RegExpCompiler* compiler) {
     return NULL;
   }
 
   // Collects information on the possible code units (mod 128) that can match if
   // we look forward.  This is used for a Boyer-Moore-like string searching
   // implementation.  TODO(erikcorry):  This should share more code with
-  // EatsAtLeast, GetQuickCheckDetails and ComputeFirstCharacterSet.
+  // EatsAtLeast, GetQuickCheckDetails.
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool not_at_start) {
     UNREACHABLE();
   }
 
   Label* label() { return &label_; }
   // If non-generic code is generated for a node (i.e. the node is not at the
   // start of the trace) then it cannot be reused.  This variable sets a limit
   // on how often we allow that to happen before we insist on starting a new
   // trace and generating generic code for a node that can be reused by flushing
   // the deferred actions in the current trace and generating a goto.
   static const int kMaxCopiesCodeGenerated = 10;
 
   NodeInfo* info() { return &info_; }
 
   void AddSibling(RegExpNode* node) { siblings_.Add(node); }
 
   // 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;
   }
+  BoyerMooreLookahead* bm_info(bool not_at_start) {
+    return bm_info_[not_at_start ? 1 : 0];
+  }
 
  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;
 
+  void set_bm_info(bool not_at_start, BoyerMooreLookahead* bm) {
+    bm_info_[not_at_start ? 1 : 0] = bm;
+  }
+
  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_;
+  BoyerMooreLookahead* bm_info_[2];
 };
 
 
 // A simple closed interval.
 class Interval {
  public:
   Interval() : from_(kNone), to_(kNone) { }
   Interval(int from, int to) : from_(from), to_(to) { }
   Interval Union(Interval that) {
     if (that.from_ == kNone)
       return *this;
     else if (from_ == kNone)
       return that;
     else
       return Interval(Min(from_, that.from_), Max(to_, that.to_));
   }
   bool Contains(int value) {
     return (from_ <= value) && (value <= to_);
   }
   bool is_empty() { return from_ == kNone; }
-  int from() { return from_; }
-  int to() { return to_; }
+  int from() const { return from_; }
+  int to() const { return to_; }
   static Interval Empty() { return Interval(); }
   static const int kNone = -1;
  private:
   int from_;
   int to_;
 };
 
 
 class SeqRegExpNode: public RegExpNode {
  public:
   explicit SeqRegExpNode(RegExpNode* on_success)
       : on_success_(on_success) { }
   RegExpNode* on_success() { return on_success_; }
   void set_on_success(RegExpNode* node) { on_success_ = node; }
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool not_at_start) {
     on_success_->FillInBMInfo(offset, bm, not_at_start);
+    if (offset == 0) set_bm_info(not_at_start, bm);
   }
  private:
   RegExpNode* on_success_;
 };
 
 
 class ActionNode: public SeqRegExpNode {
  public:
   enum Type {
     SET_REGISTER,
@@ skipping 33 matching lines @@
                                     bool not_at_start) {
     return on_success()->GetQuickCheckDetails(
         details, compiler, filled_in, not_at_start);
   }
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool 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;
@@ skipping 52 matching lines @@
   virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
       RegExpCompiler* compiler);
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool not_at_start);
   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);
@@ skipping 10 matching lines @@
 };
 
 
 class AssertionNode: public SeqRegExpNode {
  public:
   enum AssertionNodeType {
     AT_END,
     AT_START,
     AT_BOUNDARY,
     AT_NON_BOUNDARY,
-    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
+    AFTER_NEWLINE
   };
   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,
                           bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int filled_in,
                                     bool not_at_start);
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, 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:
+  void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace);
+  enum IfPrevious { kIsNonWord, kIsWord };
+  void BacktrackIfPrevious(RegExpCompiler* compiler,
+                           Trace* trace,
+                           IfPrevious backtrack_if_previous);
   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,
                           bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start) {
     return;
   }
   virtual void FillInBMInfo(
-      int offset, BoyerMooreLookahead* bm, bool not_at_start) {
-    // Working out the set of characters that a backreference can match is too
-    // hard, so we just say that any character can match.
-    bm->SetRest(offset);
-  }
+      int offset, BoyerMooreLookahead* bm, bool not_at_start);
   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 };
@@ skipping 146 matching lines @@
   virtual int EatsAtLeast(int still_to_find,
                           int recursion_depth,
                           bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start);
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool not_at_start) {
     alternatives_->at(1).node()->FillInBMInfo(offset, bm, not_at_start);
+    if (offset == 0) set_bm_info(not_at_start, bm);
   }
   // 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,
                           bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start);
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, 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.
   void AddAlternative(GuardedAlternative node) {
     ChoiceNode::AddAlternative(node);
   }
 
   RegExpNode* loop_node_;
   RegExpNode* continue_node_;
   bool body_can_be_zero_length_;
 };
 
 
+// Improve the speed that we scan for an initial point where a non-anchored
+// regexp can match by using a Boyer-Moore-like table. This is done by
+// identifying non-greedy non-capturing loops in the nodes that eat any
+// character one at a time.  For example in the middle of the regexp
+// /foo[\s\S]*?bar/ we find such a loop.  There is also such a loop implicitly
+// inserted at the start of any non-anchored regexp.
+//
+// When we have found such a loop we look ahead in the nodes to find the set of
+// characters that can come at given distances. For example for the regexp
+// /.?foo/ we know that there are at least 3 characters ahead of us, and the
+// sets of characters that can occur are [any, [f, o], [o]]. We find a range in
+// the lookahead info where the set of characters is reasonably constrained. In
+// our example this is from index 1 to 2 (0 is not constrained). We can now
+// look 3 characters ahead and if we don't find one of [f, o] (the union of
+// [f, o] and [o]) then we can skip forwards by the range size (in this case 2).
+//
+// For Unicode input strings we do the same, but modulo 128.
+//
+// We also look at the first string fed to the regexp and use that to get a hint
+// of the character frequencies in the inputs. This affects the assessment of
+// whether the set of characters is 'reasonably constrained'.
+//
+// We also have another lookahead mechanism (called quick check in the code),
+// which uses a wide load of multiple characters followed by a mask and compare
+// to determine whether a match is possible at this point.
+enum ContainedInLattice {
+  kNotYet = 0,
+  kLatticeIn = 1,
+  kLatticeOut = 2,
+  kLatticeUnknown = 3  // Can also mean both in and out.
+};
+
+
+ContainedInLattice AddRange(ContainedInLattice a,
+                            const int* ranges,
+                            int ranges_size,
+                            Interval new_range);
+
+
+class BoyerMoorePositionInfo : public ZoneObject {
+ public:
+  BoyerMoorePositionInfo()
+      : map_(new ZoneList<bool>(kMapSize)),
+        map_count_(0),
+        w_(kNotYet),
+        s_(kNotYet),
+        d_(kNotYet),
+        surrogate_(kNotYet) {
+     for (int i = 0; i < kMapSize; i++) {
+       map_->Add(false);
+     }
+  }
+
+  bool& at(int i) { return map_->at(i); }
+
+  static const int kMapSize = 128;
+  static const int kMask = kMapSize -1 ;

[ulan, 2012/04/16 13:52:22]

Should be kMapSize - 1;

[Erik Corry, 2012/04/17 07:51:45]

Done.

+
+  int map_count() const { return map_count_; }
+
+  void Set(int character);
+  void SetInterval(const Interval& interval);
+  void SetAll();
+  bool is_non_word() { return w_ == kLatticeOut; }
+  bool is_word() { return w_ == kLatticeIn; }
+
+ private:
+  ZoneList<bool>* map_;
+  int map_count_;  // Number of set bits in the map.
+  ContainedInLattice w_;  // The \w character class.
+  ContainedInLattice s_;  // The \s character class.
+  ContainedInLattice d_;  // The \d character class.
+  ContainedInLattice surrogate_;  // Surrogate UTF-16 code units.
+};
+
+
+class BoyerMooreLookahead : public ZoneObject {
+ public:
+  BoyerMooreLookahead(int length, RegExpCompiler* compiler);
+
+  int length() { return length_; }
+  int max_char() { return max_char_; }
+  RegExpCompiler* compiler() { return compiler_; }
+
+  int Count(int map_number) {
+    return bitmaps_->at(map_number)->map_count();
+  }
+
+  BoyerMoorePositionInfo* at(int i) { return bitmaps_->at(i); }
+
+  void Set(int map_number, int character) {
+    if (character > max_char_) return;
+    BoyerMoorePositionInfo* info = bitmaps_->at(map_number);
+    info->Set(character);
+  }
+
+  void SetInterval(int map_number, const Interval& interval) {
+    if (interval.from() > max_char_) return;
+    BoyerMoorePositionInfo* info = bitmaps_->at(map_number);
+    if (interval.to() > max_char_) {
+      info->SetInterval(Interval(interval.from(), max_char_));
+    } else {
+      info->SetInterval(interval);
+    }
+  }
+
+  void SetAll(int map_number) {
+    bitmaps_->at(map_number)->SetAll();
+  }
+
+  void SetRest(int from_map) {
+    for (int i = from_map; i < length_; i++) SetAll(i);
+  }
+  bool EmitSkipInstructions(RegExpMacroAssembler* masm);
+
+ private:
+  // This is the value obtained by EatsAtLeast.  If we do not have at least this
+  // many characters left in the sample string then the match is bound to fail.
+  // Therefore it is OK to read a character this far ahead of the current match
+  // point.
+  int length_;
+  RegExpCompiler* compiler_;
+  // 0x7f for ASCII, 0xffff for UTF-16.
+  int max_char_;
+  ZoneList<BoyerMoorePositionInfo*>* bitmaps_;
+
+  int GetSkipTable(int min_lookahead,
+                   int max_lookahead,
+                   Handle<ByteArray> boolean_skip_table);
+  bool FindWorthwhileInterval(int* from, int* to);
+  int FindBestInterval(
+    int max_number_of_chars, int old_biggest_points, int* from, int* to);
+};
+
+
 // There are many ways to generate code for a node.  This class encapsulates
 // the current way we should be generating.  In other words it encapsulates
 // the current state of the code generator.  The effect of this is that we
 // generate code for paths that the matcher can take through the regular
 // expression.  A given node in the regexp can be code-generated several times
 // as it can be part of several traces.  For example for the regexp:
 // /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part
 // of the foo-bar-baz trace and once as part of the foo-ip-baz trace.  The code
 // to match foo is generated only once (the traces have a common prefix).  The
 // code to store the capture is deferred and generated (twice) after the places
@@ skipping 314 matching lines @@
   int* vector_;
   int offsets_vector_length_;
 
   friend class ExternalReference;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_