Regexp: Remove nodes from the regexp that cannot match because

src/jsregexp.h

Index: src/jsregexp.h
===================================================================
--- src/jsregexp.h	(revision 11428)
+++ src/jsregexp.h	(working copy)
@@ -225,6 +225,8 @@
 };
 
 
+// Represents code units in the range from from_ to to_, both ends are
+// inclusive.
 class CharacterRange {
  public:
   CharacterRange() : from_(0), to_(0) { }
@@ -519,9 +521,12 @@
 };
 
 
+extern int kUninitializedRegExpNodePlaceHolder;
+
+
 class RegExpNode: public ZoneObject {
  public:
-  RegExpNode() : trace_count_(0) {
+  RegExpNode() : replacement_(Uninitialized()), trace_count_(0) {
     bm_info_[0] = bm_info_[1] = NULL;
   }
   virtual ~RegExpNode();
@@ -572,6 +577,16 @@
       int offset, BoyerMooreLookahead* bm, bool not_at_start) {
     UNREACHABLE();
   }
+
+  // If we know that the input is ASCII then there are some nodes that can
+  // never match.  This method returns returns a node that can be substituted

[ulan, 2012/04/25 12:55:28]

double "returns"

[Erik Corry, 2012/04/26 08:23:11]

done done

+  // for itself, or NULL if the node can never match.
+  virtual RegExpNode* FilterASCII(int depth) { return this; }
+  // Helper for FilterASCII.
+  RegExpNode* Uninitialized() {

[ulan, 2012/04/25 12:55:28]

If it doesn't make big difference in speed/space then I would
prefer a separate flag that indicates whether the replacement_ was initialized
or not?

[Erik Corry, 2012/04/26 08:23:11]

Done.

+    return reinterpret_cast<RegExpNode*>(&kUninitializedRegExpNodePlaceHolder);
+  }
+
   // We want to avoid recalculating the lookahead info, so we store it on the
   // node.  Only info that is for this node is stored.  We can tell that the
   // info is for this node when offset == 0, so the information is calculated
@@ -596,14 +611,10 @@
 
  protected:
   enum LimitResult { DONE, CONTINUE };
+  RegExpNode* replacement_;
 
   LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace);
 
-  // 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;
   }
@@ -655,11 +666,16 @@
       : on_success_(on_success) { }
   RegExpNode* on_success() { return on_success_; }
   void set_on_success(RegExpNode* node) { on_success_ = node; }
+  virtual RegExpNode* FilterASCII(int depth);
   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);
   }
+
+ protected:
+  RegExpNode* FilterSuccessor(int depth);
+
  private:
   RegExpNode* on_success_;
 };
@@ -711,7 +727,6 @@
   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); }
 
  private:
   union {
@@ -778,12 +793,8 @@
       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 RegExpNode* FilterASCII(int depth);
 
  private:
   enum TextEmitPassType {
@@ -842,7 +853,6 @@
                                     bool not_at_start);
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool not_at_start);
-  virtual AssertionNode* Clone() { return new AssertionNode(*this); }
   AssertionNodeType type() { return type_; }
   void set_type(AssertionNodeType type) { type_ = type; }
 
@@ -881,7 +891,6 @@
   }
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool not_at_start);
-  virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }
 
  private:
   int start_reg_;
@@ -910,7 +919,7 @@
     // Returning 0 from EatsAtLeast should ensure we never get here.
     UNREACHABLE();
   }
-  virtual EndNode* Clone() { return new EndNode(*this); }
+
  private:
   Action action_;
 };
@@ -958,6 +967,8 @@
 class GuardedAlternative {
  public:
   explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { }
+  GuardedAlternative(RegExpNode* node, ZoneList<Guard*>* guards)

[ulan, 2012/04/25 12:55:28]

This seems to be unused.

[Erik Corry, 2012/04/26 08:23:11]

Done.

+      : node_(node), guards_(guards) { }
   void AddGuard(Guard* guard);
   RegExpNode* node() { return node_; }
   void set_node(RegExpNode* node) { node_ = node; }
@@ -997,13 +1008,13 @@
                                     bool not_at_start);
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool not_at_start);
-  virtual ChoiceNode* Clone() { return new ChoiceNode(*this); }
 
   bool being_calculated() { return being_calculated_; }
   bool not_at_start() { return not_at_start_; }
   void set_not_at_start() { not_at_start_ = true; }
   void set_being_calculated(bool b) { being_calculated_ = b; }
   virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; }
+  virtual RegExpNode* FilterASCII(int depth);
 
  protected:
   int GreedyLoopTextLengthForAlternative(GuardedAlternative* alternative);
@@ -1056,6 +1067,7 @@
   // 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 RegExpNode* FilterASCII(int depth);
 };
 
 
@@ -1078,11 +1090,11 @@
                                     bool not_at_start);
   virtual void FillInBMInfo(
       int offset, BoyerMooreLookahead* bm, bool not_at_start);
-  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);
+  virtual RegExpNode* FilterASCII(int depth);
 
  private:
   // AddAlternative is made private for loop nodes because alternatives