Rudimentary analysis

src/jsregexp.cc

 // 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 629 matching lines @@
   void PrintNode(const char* label, RegExpNode* node);
   void Visit(RegExpNode* node);
   StringStream* stream() { return &stream_; }
  private:
   HeapStringAllocator alloc_;
   StringStream stream_;
   std::set<RegExpNode*> seen_;
 };
 
 
+// Data that is passed around during analysis.
+class AnalysisData {
+ public:
+  AnalysisData(RegExpCompiler* compiler)
+    : compiler_(compiler),
+      table_(NULL),
+      choice_index_(-1) { }
+  DispatchTable* table() { return table_; }
+  RegExpCompiler* compiler() { return compiler_; }
+  int choice_index() { return choice_index_; }
+ protected:
+  AnalysisData(AnalysisData* prev) { *this = *prev; }
+  RegExpCompiler* compiler_;
+  DispatchTable *table_;
+  int choice_index_;
+};
+
+
+// A subclass of analysis data that allows fields to be set.  Anyone
+// who needs to create new analysis data creates an instance of this
+// class, configures it, and then passes it on as an AnalysisData
+// which doesn't allow its fields to be changed.
+class SubAnalysisData: public AnalysisData {

[Lasse Reichstein, 2008/11/10 16:35:45]

How about AnalysisDataBuilder? 
SubAnalysisData doesn't say anything about what it's good for, just that it's a
subclass.

[Christian Plesner Hansen, 2008/11/11 06:12:35]

The 'Sub' was meant to convey that the result is a "child" of the prev data
given to the constructor.  But builder is a much better name.

+ public:
+  SubAnalysisData(AnalysisData* prev) : AnalysisData(prev) { }
+  void set_table(DispatchTable* value) { table_ = value; }
+  void set_choice_index(int value) { choice_index_ = value; }
+};
+
+
 class RegExpCompiler {
  public:
   explicit RegExpCompiler(int capture_count)
     : next_register_(2 * capture_count) { }
 
   RegExpNode* Compile(RegExpTree* tree,
                       RegExpNode* on_success,
-                      RegExpNode* on_failure) {
-    return tree->ToNode(this, on_success, on_failure);
-  }
+                      RegExpNode* on_failure);
 
   int AllocateRegister() { return next_register_++; }
 
  private:
   int next_register_;
 };
 
 
 class RegExpNode: public ZoneObject {
  public:
   virtual ~RegExpNode() { }
   virtual void EmitDot(DotPrinter* out);
+  virtual void Analyze(AnalysisData* data) = 0;
 };
 
 
 class SeqRegExpNode: public RegExpNode {
  public:
   explicit SeqRegExpNode(RegExpNode* on_success)
     : on_success_(on_success) { }
   RegExpNode* on_success() { return on_success_; }
  private:
   RegExpNode* on_success_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK };
   virtual void EmitDot(DotPrinter* out);
+  virtual void Analyze(AnalysisData* data);
   static EndNode* GetAccept() { return &kAccept; }
   static EndNode* GetBacktrack() { return &kBacktrack; }
  private:
   explicit EndNode(Action action) : action_(action) { }
   Action action_;
   static EndNode kAccept;
   static EndNode kBacktrack;
 };
 
 
 EndNode EndNode::kAccept(ACCEPT);
 EndNode EndNode::kBacktrack(BACKTRACK);
 
 
 class AtomNode: public SeqRegExpNode {
  public:
   AtomNode(Vector<const uc16> data,
            RegExpNode* on_success,
            RegExpNode* on_failure)
     : SeqRegExpNode(on_success),
       on_failure_(on_failure),
       data_(data) { }
   virtual void EmitDot(DotPrinter* out);
+  virtual void Analyze(AnalysisData* data);
   Vector<const uc16> data() { return data_; }
   RegExpNode* on_failure() { return on_failure_; }
  private:
   RegExpNode* on_failure_;
   Vector<const uc16> data_;
 };
 
 
 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 EmitDot(DotPrinter* out);
+  virtual void Analyze(AnalysisData* data);
   RegExpNode* on_failure() { return on_failure_; }
   int start_register() { return start_reg_; }
   int end_register() { return end_reg_; }
  private:
   RegExpNode* on_failure_;
   int start_reg_;
   int end_reg_;
 };
 
 
 class CharacterClassNode: public SeqRegExpNode {
  public:
   CharacterClassNode(ZoneList<CharacterRange>* ranges,
                      RegExpNode* on_success,
                      RegExpNode* on_failure)
     : SeqRegExpNode(on_success),
       on_failure_(on_failure),
       ranges_(ranges) { }
   virtual void EmitDot(DotPrinter* out);
+  virtual void Analyze(AnalysisData* data);
   ZoneList<CharacterRange>* ranges() { return ranges_; }
   RegExpNode* on_failure() { return on_failure_; }
  private:
   RegExpNode* on_failure_;
   ZoneList<CharacterRange>* ranges_;
 };
 
 
 class Guard: public ZoneObject {
  public:
@@ skipping 28 matching lines @@
   if (guards_ == NULL)
     guards_ = new ZoneList<Guard*>(1);
   guards_->Add(guard);
 }
 
 
 class ChoiceNode: public RegExpNode {
  public:
   explicit ChoiceNode(int expected_size, RegExpNode* on_failure)
     : on_failure_(on_failure),
-      choices_(new ZoneList<GuardedAlternative>(expected_size)) { }
+      choices_(new ZoneList<GuardedAlternative>(expected_size)),
+      visited_(false) { }

[Lasse Reichstein, 2008/11/10 16:35:45]

Why is it only ChoiceNode that has a visited field?
Other nodes might be the first to be visited twice.

[Christian Plesner Hansen, 2008/11/11 06:12:35]

Yes, but it does no harm if you don't catch it until you meet the next choice
node.  In any case I expect to change the structure so this is just temporary.

   virtual void EmitDot(DotPrinter* out);
+  virtual void Analyze(AnalysisData* data);
   void AddChild(GuardedAlternative node) { choices()->Add(node); }
   ZoneList<GuardedAlternative>* choices() { return choices_; }
   DispatchTable* table() { return &table_; }
   RegExpNode* on_failure() { return on_failure_; }
  private:
   RegExpNode* on_failure_;
   ZoneList<GuardedAlternative>* choices_;
   DispatchTable table_;
+  bool visited_;
 };
 
 
 class ActionNode: public SeqRegExpNode {
  public:
   enum Type {
     STORE_REGISTER,
     INCREMENT_REGISTER,
     STORE_POSITION,
     RESTORE_POSITION,
@@ skipping 25 matching lines @@
   static ActionNode* BeginSubmatch(RegExpNode* on_success) {
     return new ActionNode(BEGIN_SUBMATCH, on_success);
   }
   static ActionNode* EscapeSubmatch(RegExpNode* on_success) {
     return new ActionNode(ESCAPE_SUBMATCH, on_success);
   }
   static ActionNode* EndSubmatch(RegExpNode* on_success) {
     return new ActionNode(END_SUBMATCH, on_success);
   }
   virtual void EmitDot(DotPrinter* out);
+  virtual void Analyze(AnalysisData* data);
   Type type() { return type_; }
  private:
   ActionNode(Type type, RegExpNode* on_success)
     : SeqRegExpNode(on_success),
       type_(type) { }
   Type type_;
   union {
     struct {
       int reg_;
       int value_;
@@ skipping 49 matching lines @@
 static void PrintOnFailure(DotPrinter* out,
                            RegExpNode* from,
                            RegExpNode* on_failure) {
   if (on_failure == EndNode::GetBacktrack()) return;
   out->stream()->Add("  n%p -> n%p [style=dotted];\n", from, on_failure);
   out->Visit(on_failure);
 }
 
 
 void ChoiceNode::EmitDot(DotPrinter* out) {
-  out->stream()->Add("  n%p [label=\"?\", shape=circle];\n", this);
+  out->stream()->Add("  n%p [label=\"? (%p)\"];\n", this, this);
   PrintOnFailure(out, this, this->on_failure());
   for (int i = 0; i < choices()->length(); i++) {
     GuardedAlternative alt = choices()->at(i);
     out->stream()->Add("  n%p -> n%p [label=\"%i",
                        this,
                        alt.node(),
                        i);
     if (alt.guards() != NULL) {
       out->stream()->Add(" [");
       for (int j = 0; j < alt.guards()->length(); j++) {
         if (j > 0) out->stream()->Add(" ");
         Guard* guard = alt.guards()->at(j);
         switch (guard->op()) {
           case Guard::GEQ:
             out->stream()->Add("$%i &#8805; %i", guard->reg(), guard->value());
             break;
           case Guard::LT:
             out->stream()->Add("$%i < %i", guard->reg(), guard->value());
             break;
         }
       }
       out->stream()->Add("]");
     }
     out->stream()->Add("\"];\n");
     out->Visit(choices()->at(i).node());
   }
+  fprintf(stderr, "--- %p ---\n", static_cast<void*>(this));

[Lasse Reichstein, 2008/11/10 16:35:45]

Debug-print?

[Christian Plesner Hansen, 2008/11/11 06:12:35]

It turns out I can use OS::PrintError.  Also, I'll guard all this with #ifdef
DEBUG.

+  table()->Dump();
 }
 
 
 void AtomNode::EmitDot(DotPrinter* out) {
   out->stream()->Add("  n%p [label=\"'%w'\", shape=doubleoctagon];\n",
                      this,
                      data());
   out->stream()->Add("  n%p -> n%p;\n", this, this->on_success());
   out->Visit(this->on_success());
   PrintOnFailure(out, this, this->on_failure());
@@ skipping 426 matching lines @@
       // There is no overlap so we can just add the range
       ZoneSplayTree<Config>::Locator ins;
       ASSERT_RESULT(tree()->Insert(current.from(), &ins));
       ins.set_value(Entry(current.from(), current.to(), value));
       break;
     }
   }
 }
 
 
+class DispatchTableDumper {
+ public:
+  DispatchTableDumper(StringStream* stream) : stream_(stream) { }
+  void Call(uc16 key, DispatchTable::Entry entry);
+  StringStream* stream() { return stream_; }
+ private:
+  StringStream* stream_;
+};
+
+
+void DispatchTableDumper::Call(uc16 key, DispatchTable::Entry entry) {
+  stream()->Add("[%k-%k]: {", key, entry.from());
+  OutSet set = entry.out_set();
+  bool first = true;
+  for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
+    if (set.Get(i)) {
+      if (first) first = false;
+      else stream()->Add(", ");
+      stream()->Add("%i", i);
+    }
+  }
+  stream()->Add("}\n");
+}
+
+
+void DispatchTable::Dump() {
+  HeapStringAllocator alloc;
+  StringStream stream(&alloc);
+  tree()->ForEach(DispatchTableDumper(&stream));
+  fprintf(stderr, "%s", *stream.ToCString());
+}
+
+
 OutSet DispatchTable::Get(uc16 value) {
   ZoneSplayTree<Config>::Locator loc;
   if (!tree()->FindGreatestLessThan(value, &loc))
     return OutSet::empty();
   Entry* entry = &loc.value();
   if (value <= entry->to())
     return entry->out_set();
   else
     return OutSet::empty();
 }
 
 
+// -------------------------------------------------------------------
+// Analysis
+
+
+void EndNode::Analyze(AnalysisData* data) {
+  // nothing to do
+}
+
+
+void ChoiceNode::Analyze(AnalysisData* incoming) {
+  if (visited_) return;
+  visited_ = true;
+  ZoneList<GuardedAlternative>* choices = this->choices();
+  SubAnalysisData data(incoming);
+  data.set_table(table());
+  for (int i = 0; i < choices->length(); i++) {
+    data.set_choice_index(i);
+    choices->at(i).node()->Analyze(&data);
+  }
+  visited_ = false;
+}
+
+
+void BackreferenceNode::Analyze(AnalysisData* data) {
+  UNIMPLEMENTED();
+}
+
+
+void CharacterClassNode::Analyze(AnalysisData* data) {
+  if (data->table() != NULL) {
+    int index = data->choice_index();
+    ZoneList<CharacterRange>* ranges = this->ranges();
+    for (int i = 0; i < ranges->length(); i++) {
+      CharacterRange range = ranges->at(i);
+      data->table()->AddRange(range, index);
+    }
+  }
+  SubAnalysisData outgoing(data);
+  outgoing.set_table(NULL);
+  on_success()->Analyze(&outgoing);
+}
+
+
+void AtomNode::Analyze(AnalysisData* data) {
+  if (data->table() != NULL) {
+    uc16 c = this->data()[0];
+    data->table()->AddRange(CharacterRange(c, c), data->choice_index());
+  }
+  SubAnalysisData outgoing(data);
+  outgoing.set_table(NULL);
+  on_success()->Analyze(&outgoing);
+}
+
+
+void ActionNode::Analyze(AnalysisData* data) {
+  on_success()->Analyze(data);
+}
+
+
+RegExpNode* RegExpCompiler::Compile(RegExpTree* tree,
+                                    RegExpNode* on_success,
+                                    RegExpNode* on_failure) {
+  RegExpNode* node = tree->ToNode(this, on_success, on_failure);
+  AnalysisData data(this);
+  node->Analyze(&data);
+  return node;
+}
+
+
 void RegExpEngine::DotPrint(const char* label, RegExpNode* node) {
   DotPrinter printer;
   printer.PrintNode(label, node);
 }
 
 
 RegExpNode* RegExpEngine::Compile(RegExpParseResult* input) {
   RegExpCompiler compiler(input->capture_count);
   RegExpNode* node = compiler.Compile(input->tree,
                                       EndNode::GetAccept(),
                                       EndNode::GetBacktrack());
   return node;
 }
 
 
 }}  // namespace v8::internal