Info propagation.

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 414 matching lines @@
   static TextElement Atom(RegExpAtom* atom);
   static TextElement CharClass(RegExpCharacterClass* char_class);
   Type type;
   union {
     RegExpAtom* u_atom;
     RegExpCharacterClass* u_char_class;
   } data;
 };
 
 
-class NodeInfo {
- public:
+struct NodeInfo {
   NodeInfo()
     : being_analyzed(false),
       been_analyzed(false),
-      propagate_word(false),
-      propagate_newline(false),
-      propagate_start(false),
+      determine_word(false),
+      determine_newline(false),
+      determine_start(false),
       follows_word_interest(false),
       follows_newline_interest(false),
       follows_start_interest(false) { }
+  bool SameInterests(NodeInfo* that) {
+    return (follows_word_interest == that->follows_word_interest)
+        && (follows_newline_interest == that->follows_newline_interest)
+        && (follows_start_interest == that->follows_start_interest);
+  }
+  void AdoptInterests(NodeInfo* that) {
+    follows_word_interest = that->follows_word_interest;
+    follows_newline_interest = that->follows_newline_interest;
+    follows_start_interest = that->follows_start_interest;
+  }
+  bool prev_determine_word() {
+    return determine_word || follows_word_interest;
+  }
+  bool prev_determine_newline() {
+    return determine_newline || follows_newline_interest;
+  }
+  bool prev_determine_start() {
+    return determine_start || follows_start_interest;
+  }
   bool being_analyzed: 1;
   bool been_analyzed: 1;
-  bool propagate_word: 1;
-  bool propagate_newline: 1;
-  bool propagate_start: 1;
+  bool determine_word: 1;
+  bool determine_newline: 1;
+  bool determine_start: 1;
   bool follows_word_interest: 1;
   bool follows_newline_interest: 1;
   bool follows_start_interest: 1;
 };
 
 
 STATIC_CHECK(sizeof(NodeInfo) <= sizeof(int));  // NOLINT
 
 
+class SiblingList {
+public:
+  SiblingList() : list_(NULL) { }
+  int length() {
+    return list_ == NULL ? 0 : list_->length();
+  }
+  void Ensure(RegExpNode* parent) {
+    if (list_ == NULL) {
+      list_ = new ZoneList<RegExpNode*>(2);
+      list_->Add(parent);
+    }
+  }
+  void Add(RegExpNode* node) { list_->Add(node); }
+  RegExpNode* Get(int index) { return list_->at(index); }
+private:
+  ZoneList<RegExpNode*>* list_;
+};
+
+
 class RegExpNode: public ZoneObject {
  public:
   virtual ~RegExpNode() { }
   virtual void Accept(NodeVisitor* visitor) = 0;
   // Generates a goto to this node or actually generates the code at this point.
   // Until the implementation is complete we will return true for success and
   // false for failure.
   bool GoTo(RegExpCompiler* compiler);
   Label* label();
 
   // Until the implementation is complete we will return true for success and
   // false for failure.
   virtual bool Emit(RegExpCompiler* compiler) = 0;
+  virtual RegExpNode* PropagateInterest(NodeInfo* info) = 0;
   NodeInfo* info() { return &info_; }
   virtual bool IsBacktrack() { return false; }
+  RegExpNode* GetSibling(NodeInfo* info);
+  void EnsureSiblings() { siblings_.Ensure(this); }
+  void AddSibling(RegExpNode* node) { siblings_.Add(node); }
  private:
   Label label_;
   NodeInfo info_;
+  SiblingList siblings_;
 };
 
 
 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 bool Emit(RegExpCompiler* compiler) { return false; }
  private:
   RegExpNode* on_success_;
 };
 
 
 class ActionNode: public SeqRegExpNode {
  public:
   enum Type {
     STORE_REGISTER,
     INCREMENT_REGISTER,
     STORE_POSITION,
     RESTORE_POSITION,
     BEGIN_SUBMATCH,
     ESCAPE_SUBMATCH,
     END_SUBMATCH
   };
   static ActionNode* StoreRegister(int reg, int val, RegExpNode* on_success);
   static ActionNode* IncrementRegister(int reg, RegExpNode* on_success);
   static ActionNode* StorePosition(int reg, RegExpNode* on_success);
   static ActionNode* RestorePosition(int reg, RegExpNode* on_success);
   static ActionNode* BeginSubmatch(RegExpNode* on_success);
   static ActionNode* EscapeSubmatch(RegExpNode* on_success);
   static ActionNode* EndSubmatch(RegExpNode* on_success);
   virtual void Accept(NodeVisitor* visitor);
   virtual bool Emit(RegExpCompiler* compiler);
+  virtual RegExpNode* PropagateInterest(NodeInfo* info);
  private:
   union {
     struct {
       int reg;
       int value;
     } u_store_register;
     struct {
       int reg;
     } u_increment_register;
     struct {
@@ skipping 11 matching lines @@
 class TextNode: public SeqRegExpNode {
  public:
   TextNode(ZoneList<TextElement>* elms,
            RegExpNode* on_success,
            RegExpNode* on_failure)
     : SeqRegExpNode(on_success),
       on_failure_(on_failure),
       elms_(elms) { }
   virtual void Accept(NodeVisitor* visitor);
   virtual bool Emit(RegExpCompiler* compiler) { return false; }
+  virtual RegExpNode* PropagateInterest(NodeInfo* info);
   RegExpNode* on_failure() { return on_failure_; }
   ZoneList<TextElement>* elements() { return elms_; }
  private:
   RegExpNode* on_failure_;
   ZoneList<TextElement>* elms_;
 };
 
 
 class BackreferenceNode: public SeqRegExpNode {
  public:
   BackreferenceNode(int start_reg,
                     int end_reg,
                     RegExpNode* on_success,
                     RegExpNode* on_failure)
     : SeqRegExpNode(on_success),
       on_failure_(on_failure),
       start_reg_(start_reg),
       end_reg_(end_reg) { }
   virtual void Accept(NodeVisitor* visitor);
   RegExpNode* on_failure() { return on_failure_; }
   int start_register() { return start_reg_; }
   int end_register() { return end_reg_; }
   virtual bool Emit(RegExpCompiler* compiler) { return false; }
+  virtual RegExpNode* PropagateInterest(NodeInfo* info);
  private:
   RegExpNode* on_failure_;
   int start_reg_;
   int end_reg_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK };
   explicit EndNode(Action action) : action_(action) { }
   virtual void Accept(NodeVisitor* visitor);
   virtual bool Emit(RegExpCompiler* compiler);
+  virtual RegExpNode* PropagateInterest(NodeInfo* info);
   virtual bool IsBacktrack() { return action_ == BACKTRACK; }
  private:
   Action action_;
 };
 
 
 class Guard: public ZoneObject {
  public:
   enum Relation { LT, GEQ };
   Guard(int reg, Relation op, int value)
     : reg_(reg),
       op_(op),
       value_(value) { }
   int reg() { return reg_; }
   Relation op() { return op_; }
   int value() { return value_; }
  private:
   int reg_;
   Relation op_;
   int value_;
 };
 
 
 class GuardedAlternative {
  public:
   explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { }
   void AddGuard(Guard* guard);
   RegExpNode* node() { return node_; }
+  void set_node(RegExpNode* node) { node_ = node; }
   ZoneList<Guard*>* guards() { return guards_; }
  private:
   RegExpNode* node_;
   ZoneList<Guard*>* guards_;
 };
 
 
 class ChoiceNode: public RegExpNode {
  public:
   explicit ChoiceNode(int expected_size, RegExpNode* on_failure)
     : on_failure_(on_failure),
       alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
       table_calculated_(false),
       being_calculated_(false) { }
   virtual void Accept(NodeVisitor* visitor);
   void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
   ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
   DispatchTable* table() { return &table_; }
   RegExpNode* on_failure() { return on_failure_; }
   virtual bool Emit(RegExpCompiler* compiler);
+  virtual RegExpNode* PropagateInterest(NodeInfo* info);
   bool table_calculated() { return table_calculated_; }
   void set_table_calculated(bool b) { table_calculated_ = b; }
   bool being_calculated() { return being_calculated_; }
   void set_being_calculated(bool b) { being_calculated_ = b; }
  private:
   void GenerateGuard(RegExpCompiler* compiler,
                      Guard *guard,
                      Label* on_failure);
   RegExpNode* on_failure_;
   ZoneList<GuardedAlternative>* alternatives_;
@@ skipping 67 matching lines @@
   static Handle<FixedArray> Compile(RegExpParseResult* input,
                                     RegExpNode** node_return,
                                     bool ignore_case);
   static void DotPrint(const char* label, RegExpNode* node);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_