Restructure analysis

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 148 matching lines @@
   void set_to(uc16 value) { to_ = value; }
   bool is_valid() { return from_ <= to_; }
   bool IsSingleton() { return (from_ == to_); }
  private:
   uc16 from_;
   uc16 to_;
 };
 
 
 template <typename Node, class Callback>
-static void DoForEach(Node* node, Callback callback);
+static void DoForEach(Node* node, Callback* callback);
 
 
 // A zone splay tree.  The config type parameter encapsulates the
 // different configurations of a concrete splay tree:
 //
 //   typedef Key: the key type
 //   typedef Value: the value type
 //   static const kNoKey: the dummy key used when no key is set
 //   static const kNoValue: the dummy value used to initialize nodes
 //   int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function
@@ skipping 71 matching lines @@
     Locator() : node_(NULL) { }
     const Key& key() { return node_->key_; }
     Value& value() { return node_->value_; }
     void set_value(const Value& value) { node_->value_ = value; }
     inline void bind(Node* node) { node_ = node; }
    private:
     Node* node_;
   };
 
   template <class Callback>
-  void ForEach(Callback c) {
+  void ForEach(Callback* c) {
     DoForEach<typename ZoneSplayTree<Config>::Node, Callback>(root_, c);
   }
 
  private:
   Node* root_;
 };
 
 
 // A set of unsigned integers that behaves especially well on small
 // integers (< 32).  May do zone-allocation.
@@ skipping 58 matching lines @@
       else
         return 1;
     }
   };
 
   void AddRange(CharacterRange range, int value);
   OutSet* Get(uc16 value);
   void Dump();
 
   template <typename Callback>
-  void ForEach(Callback callback) { return tree()->ForEach(callback); }
+  void ForEach(Callback* callback) { return tree()->ForEach(callback); }
  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_;
 };
 
 
 #define FOR_EACH_NODE_TYPE(VISIT)                                    \
   VISIT(End)                                                         \
   VISIT(Atom)                                                        \
   VISIT(Action)                                                      \
   VISIT(Choice)                                                      \
   VISIT(Backreference)                                               \
   VISIT(CharacterClass)
 
 
+class NodeInfo {
+ public:
+  NodeInfo()
+    : being_analyzed(false),
+      been_analyzed(false),
+      propagate_word(false),
+      propagate_line(false) { }
+  bool being_analyzed: 1;
+  bool been_analyzed: 1;
+  bool propagate_word: 1;
+  bool propagate_line: 1;
+};
+
+
+STATIC_CHECK(sizeof(NodeInfo) <= sizeof(int));  // NOLINT
+
+
 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.
   void GoTo(RegExpCompiler* compiler);
   void EmitAddress(RegExpCompiler* compiler);
   virtual void Emit(RegExpCompiler* compiler) = 0;
+  NodeInfo* info() { return &info_; }
+  virtual bool IsBacktrack() { return false; }
  private:
   Label label;
+  NodeInfo info_;
 };
 
 
 class SeqRegExpNode: public RegExpNode {
  public:
   explicit SeqRegExpNode(RegExpNode* on_success)
     : on_success_(on_success) { }
   RegExpNode* on_success() { return on_success_; }
   virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
  private:
@@ skipping 103 matching lines @@
  private:
   RegExpNode* on_failure_;
   ZoneList<CharacterRange>* ranges_;
   bool is_negated_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK };
+  explicit EndNode(Action action) : action_(action) { }
   virtual void Accept(NodeVisitor* visitor);
-  static EndNode* GetAccept() { return &kAccept; }
-  static EndNode* GetBacktrack() { return &kBacktrack; }
   virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
+  virtual bool IsBacktrack() { return action_ == BACKTRACK; }
  private:
-  explicit EndNode(Action action) : action_(action) { }
   Action action_;
-  static EndNode kAccept;
-  static EndNode kBacktrack;
 };
 
 
 class Guard: public ZoneObject {
  public:
   enum Relation { LT, GEQ };
   Guard(int reg, Relation op, int value)
     : reg_(reg),
       op_(op),
       value_(value) { }
@@ skipping 16 matching lines @@
  private:
   RegExpNode* node_;
   ZoneList<Guard*>* guards_;
 };
 
 
 class ChoiceNode: public RegExpNode {
  public:
   explicit ChoiceNode(int expected_size, RegExpNode* on_failure)
     : on_failure_(on_failure),
-      choices_(new ZoneList<GuardedAlternative>(expected_size)),
-      visited_(false) { }
+      alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
+      table_calculated_(false),
+      being_calculated_(false) { }
   virtual void Accept(NodeVisitor* visitor);
-  void AddChild(GuardedAlternative node) { choices()->Add(node); }
-  ZoneList<GuardedAlternative>* choices() { return choices_; }
+  void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
+  ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
   DispatchTable* table() { return &table_; }
   RegExpNode* on_failure() { return on_failure_; }
   virtual void Emit(RegExpCompiler* compiler);
-  bool visited() { return visited_; }
-  void set_visited(bool value) { visited_ = value; }
+  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:
   RegExpNode* on_failure_;
-  ZoneList<GuardedAlternative>* choices_;
+  ZoneList<GuardedAlternative>* alternatives_;
   DispatchTable table_;
-  bool visited_;
+  bool table_calculated_;
+  bool being_calculated_;
 };
 
 
+class NodeVisitor {
+ public:
+  virtual ~NodeVisitor() { }
+#define DECLARE_VISIT(Type)                                          \
+  virtual void Visit##Type(Type##Node* that) = 0;
+FOR_EACH_NODE_TYPE(DECLARE_VISIT)
+#undef DECLARE_VISIT
+};
+
+
+// Node visitor used to add the start set of the alternatives to the
+// dispatch table of a choice node.
+class DispatchTableConstructor: public NodeVisitor {
+ public:
+  explicit DispatchTableConstructor(DispatchTable* table)
+    : table_(table),
+      choice_index_(-1) { }
+
+  void BuildTable(ChoiceNode* node);
+
+  void AddRange(CharacterRange range) {
+    table()->AddRange(range, choice_index_);
+  }
+
+  void AddInverse(ZoneList<CharacterRange>* ranges);
+
+#define DECLARE_VISIT(Type)                                          \
+  virtual void Visit##Type(Type##Node* that);
+FOR_EACH_NODE_TYPE(DECLARE_VISIT)
+#undef DECLARE_VISIT
+
+  DispatchTable* table() { return table_; }
+  void set_choice_index(int value) { choice_index_ = value; }
+
+ protected:
+  DispatchTable *table_;
+  int choice_index_;
+};
+
+
+class Analysis: public NodeVisitor {
+ public:
+  void EnsureAnalyzed(RegExpNode* node);
+
+#define DECLARE_VISIT(Type)                                          \
+  virtual void Visit##Type(Type##Node* that);
+FOR_EACH_NODE_TYPE(DECLARE_VISIT)
+#undef DECLARE_VISIT
+};
+
+
 struct RegExpParseResult {
   RegExpTree* tree;
   bool has_character_escapes;
   Handle<String> error;
   int capture_count;
 };
 
 
 class RegExpEngine: public AllStatic {
  public:
   static RegExpNode* Compile(RegExpParseResult* input);
   static void DotPrint(const char* label, RegExpNode* node);
 };
 
 
-class RegExpCompiler;
-
-
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_