Restructure 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 618 matching lines @@
 ByteArray* RegExpImpl::JsreInternal(Handle<JSRegExp> re) {
   FixedArray* value = FixedArray::cast(re->DataAt(JSRegExp::kJscreDataIndex));
   return ByteArray::cast(value->get(INTERNAL_INDEX));
 }
 
 
 // -------------------------------------------------------------------
 // New regular expression engine
 
 
-class DotPrinter;
-
-
 class RegExpCompiler {
  public:
-  explicit RegExpCompiler(int capture_count)
-    : next_register_(2 * capture_count),
-      work_list_(NULL) { }
+  explicit RegExpCompiler(int capture_count);
 
   int AllocateRegister() { return next_register_++; }
 
   Handle<FixedArray> Assemble(RegExpMacroAssembler* assembler,
                               RegExpNode* start);
 
   inline void AddWork(RegExpNode* node) { work_list_->Add(node); }
 
   static const int kImplementationOffset = 0;
   static const int kNumberOfRegistersOffset = 0;
   static const int kCodeOffset = 1;
 
-  RegExpMacroAssembler* macro_assembler() {
-    return macro_assembler_;
-  }
+  RegExpMacroAssembler* macro_assembler() { return macro_assembler_; }
+  EndNode* accept() { return accept_; }
+  EndNode* backtrack() { return backtrack_; }
+
  private:
+  EndNode* accept_;
+  EndNode* backtrack_;
   int next_register_;
   List<RegExpNode*>* work_list_;
   RegExpMacroAssembler* macro_assembler_;
 };
 
 
+RegExpCompiler::RegExpCompiler(int capture_count)
+  : next_register_(2 * capture_count),
+    work_list_(NULL) {
+  accept_ = new EndNode(EndNode::ACCEPT);
+  backtrack_ = new EndNode(EndNode::BACKTRACK);
+}
+
+
 Handle<FixedArray> RegExpCompiler::Assemble(
     RegExpMacroAssembler* macro_assembler,
     RegExpNode* start) {
   macro_assembler_ = macro_assembler;
   List <RegExpNode*> work_list(0);
   work_list_ = &work_list;
   start->GoTo(this);
   while (!work_list.is_empty()) {
     work_list.RemoveLast()->Emit(this);
   }
@@ skipping 17 matching lines @@
     Emit(compiler);
   }
 }
 
 
 void RegExpNode::EmitAddress(RegExpCompiler* compiler) {
   compiler->macro_assembler()->EmitOrLink(&label);
 }
 
 
-EndNode EndNode::kAccept(ACCEPT);
-EndNode EndNode::kBacktrack(BACKTRACK);
-
-
 void GuardedAlternative::AddGuard(Guard* guard) {
   if (guards_ == NULL)
     guards_ = new ZoneList<Guard*>(1);
   guards_->Add(guard);
 }
 
 
 ActionNode* ActionNode::StoreRegister(int reg,
                                       int val,
                                       RegExpNode* on_success) {
@@ skipping 33 matching lines @@
 ActionNode* ActionNode::EscapeSubmatch(RegExpNode* on_success) {
   return new ActionNode(ESCAPE_SUBMATCH, on_success);
 }
 
 
 ActionNode* ActionNode::EndSubmatch(RegExpNode* on_success) {
   return new ActionNode(END_SUBMATCH, on_success);
 }
 
 
-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
-};
-
-
 #define DEFINE_ACCEPT(Type)                                          \
   void Type##Node::Accept(NodeVisitor* visitor) {                    \
     visitor->Visit##Type(this);                                      \
   }
 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
 #undef DEFINE_ACCEPT
 
 
 // -------------------------------------------------------------------
 // Emit code.
@@ skipping 70 matching lines @@
         stream()->Add("\\\\");
         break;
       case '"':
         stream()->Add("\"");
         break;
       default:
         stream()->Put(label[i]);
         break;
     }
   }
-  stream()->Add("\"]; \n");
+  stream()->Add("\"];\n");
   Visit(node);
   stream()->Add("}\n");
   printf("%s", *(stream()->ToCString()));
 }
 
 
 void DotPrinter::Visit(RegExpNode* node) {
   if (seen_.find(node) != seen_.end())
     return;
   seen_.insert(node);
   node->Accept(this);
 }
 
 
 void DotPrinter::PrintOnFailure(RegExpNode* from, RegExpNode* on_failure) {
-  if (on_failure == EndNode::GetBacktrack()) return;
+  if (on_failure->IsBacktrack()) return;
   stream()->Add("  n%p -> n%p [style=dotted];\n", from, on_failure);
   Visit(on_failure);
 }
 
 
+class TableEntryBodyPrinter {
+ public:
+   TableEntryBodyPrinter(StringStream* stream, ChoiceNode* choice)
+    : stream_(stream), choice_(choice) { }
+  void Call(uc16 from, DispatchTable::Entry entry) {
+    OutSet* out_set = entry.out_set();
+    for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
+      if (out_set->Get(i)) {
+        stream()->Add("    n%p:s%io%i -> n%p;\n",
+                      choice(),
+                      from,
+                      i,
+                      choice()->alternatives()->at(i).node());
+      }
+    }
+  }
+ private:
+  StringStream* stream() { return stream_; }
+  ChoiceNode* choice() { return choice_; }
+  StringStream* stream_;
+  ChoiceNode* choice_;
+};
+
+
+class TableEntryHeaderPrinter {
+ public:
+  TableEntryHeaderPrinter(StringStream* stream)
+    : first_(true), stream_(stream) { }
+  void Call(uc16 from, DispatchTable::Entry entry) {
+    if (first_) {
+      first_ = false;
+    } else {
+      stream()->Add("|");
+    }
+    stream()->Add("{%k-%k|{", from, from, entry.to());
+    OutSet* out_set = entry.out_set();
+    int priority = 0;
+    for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
+      if (out_set->Get(i)) {
+        if (priority > 0) stream()->Add("|");
+        stream()->Add("<s%io%i> %i", from, i, priority);
+        priority++;
+      }
+    }
+    stream()->Add("}}");
+  }
+ private:
+  bool first_;
+  StringStream* stream() { return stream_; }
+  StringStream* stream_;
+};
+
+
 void DotPrinter::VisitChoice(ChoiceNode* that) {
-  stream()->Add("  n%p [label=\"? (%p)\"];\n", that, that);
+  stream()->Add("  n%p [shape=Mrecord, label=\"", that);
+  TableEntryHeaderPrinter header_printer(stream());
+  that->table()->ForEach(&header_printer);
+  stream()->Add("\"]\n", that);
+  TableEntryBodyPrinter body_printer(stream(), that);
+  that->table()->ForEach(&body_printer);
   PrintOnFailure(that, that->on_failure());
-  for (int i = 0; i < that->choices()->length(); i++) {
-    GuardedAlternative alt = that->choices()->at(i);
-    stream()->Add("  n%p -> n%p [label=\"%i",
-                       that,
-                       alt.node(),
-                       i);
-    if (alt.guards() != NULL) {
-      stream()->Add(" [");
-      for (int j = 0; j < alt.guards()->length(); j++) {
-        if (j > 0) stream()->Add(" ");
-        Guard* guard = alt.guards()->at(j);
-        switch (guard->op()) {
-          case Guard::GEQ:
-            stream()->Add("$%i &#8805; %i", guard->reg(), guard->value());
-            break;
-          case Guard::LT:
-            stream()->Add("$%i < %i", guard->reg(), guard->value());
-            break;
-        }
-      }
-      stream()->Add("]");
-    }
-    stream()->Add("\"];\n");
-    that->choices()->at(i).node()->Accept(this);
+  for (int i = 0; i < that->alternatives()->length(); i++) {
+    GuardedAlternative alt = that->alternatives()->at(i);
+    alt.node()->Accept(this);
   }
-  OS::PrintError("--- %p ---\n", static_cast<void*>(that));
-  that->table()->Dump();
 }
 
 
 void DotPrinter::VisitAtom(AtomNode* that) {
   stream()->Add("  n%p [label=\"'%w'\", shape=doubleoctagon];\n",
                 that,
                 that->data());
   stream()->Add("  n%p -> n%p;\n", that, that->on_success());
   Visit(that->on_success());
   PrintOnFailure(that, that->on_failure());
@@ skipping 91 matching lines @@
       stream()->Add("%i", i);
     }
   }
   stream()->Add("}\n");
 }
 
 
 void DispatchTable::Dump() {
   HeapStringAllocator alloc;
   StringStream stream(&alloc);
-  tree()->ForEach(DispatchTableDumper(&stream));
+  DispatchTableDumper dumper(&stream);
+  tree()->ForEach(&dumper);
   OS::PrintError("%s", *stream.ToCString());
 }
 
 
 void RegExpEngine::DotPrint(const char* label, RegExpNode* node) {
   DotPrinter printer;
   printer.PrintNode(label, node);
 }
 
 
@@ skipping 17 matching lines @@
   return new CharacterClassNode(ranges(),
                                 is_negated(),
                                 on_success,
                                 on_failure);
 }
 
 
 RegExpNode* RegExpDisjunction::ToNode(RegExpCompiler* compiler,
                                       RegExpNode* on_success,
                                       RegExpNode* on_failure) {
-  ZoneList<RegExpTree*>* children = nodes();
-  int length = children->length();
+  ZoneList<RegExpTree*>* alternatives = this->alternatives();
+  int length = alternatives->length();
   ChoiceNode* result = new ChoiceNode(length, on_failure);
   for (int i = 0; i < length; i++) {
-    GuardedAlternative child(children->at(i)->ToNode(compiler,
-                                                     on_success,
-                                                     on_failure));
-    result->AddChild(child);
+    GuardedAlternative alternative(alternatives->at(i)->ToNode(compiler,
+                                                               on_success,
+                                                               on_failure));
+    result->AddAlternative(alternative);
   }
   return result;
 }
 
 
 RegExpNode* RegExpQuantifier::ToNode(RegExpCompiler* compiler,
                                      RegExpNode* on_success,
                                      RegExpNode* on_failure) {
   return ToNode(min(),
                 max(),
@@ skipping 38 matching lines @@
   if (has_max) {
     Guard* body_guard = new Guard(reg_ctr, Guard::LT, max);
     body_alt.AddGuard(body_guard);
   }
   GuardedAlternative rest_alt(on_success);
   if (has_min) {
     Guard* rest_guard = new Guard(reg_ctr, Guard::GEQ, min);
     rest_alt.AddGuard(rest_guard);
   }
   if (is_greedy) {
-    center->AddChild(body_alt);
-    center->AddChild(rest_alt);
+    center->AddAlternative(body_alt);
+    center->AddAlternative(rest_alt);
   } else {
-    center->AddChild(rest_alt);
-    center->AddChild(body_alt);
+    center->AddAlternative(rest_alt);
+    center->AddAlternative(body_alt);
   }
   if (needs_counter) {
     return ActionNode::StoreRegister(reg_ctr, 0, center);
   } else {
     return center;
   }
 }
 
 
 RegExpNode* RegExpAssertion::ToNode(RegExpCompiler* compiler,
@@ skipping 50 matching lines @@
     //         fail
     //       else
     //         backtrack
     // second
     //       end submatch scope
     //       succeed
     ChoiceNode* try_node =
         new ChoiceNode(1, ActionNode::EndSubmatch(on_success));
     RegExpNode* body_node = body()->ToNode(compiler,
         ActionNode::EscapeSubmatch(on_failure),
-        EndNode::GetBacktrack());
+        compiler->backtrack());
     GuardedAlternative body_alt(body_node);
-    try_node->AddChild(body_alt);
+    try_node->AddAlternative(body_alt);
     return ActionNode::BeginSubmatch(try_node);
   }
 }
 
 
 RegExpNode* RegExpCapture::ToNode(RegExpCompiler* compiler,
                                   RegExpNode* on_success,
                                   RegExpNode* on_failure) {
   return ToNode(body(), index(), compiler, on_success, on_failure);
 }
@@ skipping 246 matching lines @@
     return entry->out_set();
   else
     return empty();
 }
 
 
 // -------------------------------------------------------------------
 // Analysis
 
 
-class Analysis: public NodeVisitor {
- public:
-  explicit Analysis(RegExpCompiler* compiler)
-    : compiler_(compiler),
-      table_(NULL),
-      choice_index_(-1) { }
-  DispatchTable* table() { return table_; }
-  RegExpCompiler* compiler() { return compiler_; }
-  int choice_index() { return choice_index_; }
-  void Analyze(RegExpNode* node) { node->Accept(this); }
-#define DECLARE_VISIT(Type)                                          \
-  virtual void Visit##Type(Type##Node* that);
-FOR_EACH_NODE_TYPE(DECLARE_VISIT)
-#undef DECLARE_VISIT
- protected:
-  explicit Analysis(Analysis* 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 AnalysisBuilder: public Analysis {
- public:
-  explicit AnalysisBuilder(Analysis* prev) : Analysis(prev) { }
-  void set_table(DispatchTable* value) { table_ = value; }
-  void set_choice_index(int value) { choice_index_ = value; }
-};
+void Analysis::EnsureAnalyzed(RegExpNode* that) {
+  if (that->info()->been_analyzed || that->info()->being_analyzed)
+    return;
+  that->info()->being_analyzed = true;
+  that->Accept(this);
+  that->info()->being_analyzed = false;
+  that->info()->been_analyzed = true;
+}
 
 
 void Analysis::VisitEnd(EndNode* that) {
   // nothing to do
 }
 
 
+void Analysis::VisitAtom(AtomNode* that) {
+  EnsureAnalyzed(that->on_success());
+  EnsureAnalyzed(that->on_failure());
+}
+
+
+void Analysis::VisitAction(ActionNode* that) {
+  RegExpNode* next = that->on_success();
+  EnsureAnalyzed(next);
+  that->info()->propagate_line = next->info()->propagate_line;
+  that->info()->propagate_word = next->info()->propagate_word;
+}
+
+
+void Analysis::VisitChoice(ChoiceNode* that) {
+  NodeInfo* info = that->info();
+  for (int i = 0; i < that->alternatives()->length(); i++) {
+    RegExpNode* node = that->alternatives()->at(i).node();
+    EnsureAnalyzed(node);
+    info->propagate_line |= node->info()->propagate_line;
+    info->propagate_word |= node->info()->propagate_word;
+  }
+  DispatchTableConstructor cons(that->table());
+  cons.BuildTable(that);
+  EnsureAnalyzed(that->on_failure());
+}
+
+
+void Analysis::VisitBackreference(BackreferenceNode* that) {
+  EnsureAnalyzed(that->on_success());
+  EnsureAnalyzed(that->on_failure());
+}
+
+
+void Analysis::VisitCharacterClass(CharacterClassNode* that) {
+  EnsureAnalyzed(that->on_success());
+  EnsureAnalyzed(that->on_failure());
+}
+
+
+// -------------------------------------------------------------------
+// Dispatch table construction
+
+
+void DispatchTableConstructor::VisitEnd(EndNode* that) {
+  // nothing to do
+}
+
+
+void DispatchTableConstructor::BuildTable(ChoiceNode* node) {
+  ASSERT(!node->table_calculated());
+  node->set_being_calculated(true);
+  ZoneList<GuardedAlternative>* alternatives = node->alternatives();
+  for (int i = 0; i < alternatives->length(); i++) {
+    set_choice_index(i);
+    alternatives->at(i).node()->Accept(this);
+  }
+  node->set_being_calculated(false);
+  node->set_table_calculated(true);
+}
+
+
 class AddDispatchRange {
  public:
-  explicit AddDispatchRange(Analysis* analysis) : analysis_(analysis) { }
+  explicit AddDispatchRange(DispatchTableConstructor* constructor)
+    : constructor_(constructor) { }
   void Call(uc32 from, DispatchTable::Entry entry);
  private:
-  Analysis* analysis_;
+  DispatchTableConstructor* constructor_;
 };
 
 
 void AddDispatchRange::Call(uc32 from, DispatchTable::Entry entry) {
   CharacterRange range(from, entry.to());
-  analysis_->table()->AddRange(range, analysis_->choice_index());
+  constructor_->AddRange(range);
 }
 
 
-void Analysis::VisitChoice(ChoiceNode* node) {
-  if (node->visited()) return;
-  node->set_visited(true);
-  ZoneList<GuardedAlternative>* choices = node->choices();
-  AnalysisBuilder data(this);
-  data.set_table(node->table());
-  for (int i = 0; i < choices->length(); i++) {
-    data.set_choice_index(i);
-    data.Analyze(choices->at(i).node());
+void DispatchTableConstructor::VisitChoice(ChoiceNode* node) {
+  if (node->being_calculated())
+    return;
+  if (!node->table_calculated()) {
+    DispatchTableConstructor constructor(node->table());
+    constructor.BuildTable(node);
   }
-  node->set_visited(false);
-  if (table() != NULL) {
-    data.table()->ForEach(AddDispatchRange(this));
-  }
+  ASSERT(node->table_calculated());
+  AddDispatchRange adder(this);
+  node->table()->ForEach(&adder);
 }
 
 
-void Analysis::VisitBackreference(BackreferenceNode* that) {
+void DispatchTableConstructor::VisitBackreference(BackreferenceNode* that) {
   UNIMPLEMENTED();
 }
 
 
 
 static int CompareRangeByFrom(const CharacterRange* a,
                               const CharacterRange* b) {
   return Spaceship<uc16>(a->from(), b->from());
 }
 
 
-void CharacterClassNode::AddInverseToTable(ZoneList<CharacterRange>* ranges,
-                                           DispatchTable* table,
-                                           int index) {
+void DispatchTableConstructor::AddInverse(ZoneList<CharacterRange>* ranges) {
   ranges->Sort(CompareRangeByFrom);
   uc16 last = 0;
   for (int i = 0; i < ranges->length(); i++) {
     CharacterRange range = ranges->at(i);
     if (last < range.from())
-      table->AddRange(CharacterRange(last, range.from() - 1), index);
+      AddRange(CharacterRange(last, range.from() - 1));
     if (range.to() >= last) {
       if (range.to() == 0xFFFF) {
         return;
       } else {
         last = range.to() + 1;
       }
     }
   }
-  table->AddRange(CharacterRange(last, 0xFFFF), index);
+  AddRange(CharacterRange(last, 0xFFFF));
 }
 
 
-void Analysis::VisitCharacterClass(CharacterClassNode* that) {
-  if (table() != NULL) {
-    int index = choice_index();
-    ZoneList<CharacterRange>* ranges = that->ranges();
-    if (that->is_negated()) {
-      CharacterClassNode::AddInverseToTable(ranges, table(), index);
-    } else {
-      for (int i = 0; i < ranges->length(); i++) {
-        CharacterRange range = ranges->at(i);
-        table()->AddRange(range, index);
-      }
+void DispatchTableConstructor::VisitCharacterClass(CharacterClassNode* that) {
+  ZoneList<CharacterRange>* ranges = that->ranges();
+  if (that->is_negated()) {
+    AddInverse(ranges);
+  } else {
+    for (int i = 0; i < ranges->length(); i++) {
+      AddRange(ranges->at(i));
     }
   }
-  AnalysisBuilder outgoing(this);
-  outgoing.set_table(NULL);
-  outgoing.Analyze(that->on_success());
 }
 
 
-void Analysis::VisitAtom(AtomNode* that) {
-  if (table() != NULL) {
-    uc16 c = that->data()[0];
-    table()->AddRange(CharacterRange(c, c), choice_index());
-  }
-  AnalysisBuilder outgoing(this);
-  outgoing.set_table(NULL);
-  outgoing.Analyze(that->on_success());
+void DispatchTableConstructor::VisitAtom(AtomNode* that) {
+  uc16 c = that->data()[0];
+  AddRange(CharacterRange(c, c));
 }
 
 
-void Analysis::VisitAction(ActionNode* that) {
-  Analyze(that->on_success());
+void DispatchTableConstructor::VisitAction(ActionNode* that) {
+  that->on_success()->Accept(this);
 }
 
 
 RegExpNode* RegExpEngine::Compile(RegExpParseResult* input) {
   RegExpCompiler compiler(input->capture_count);
   // Wrap the body of the regexp in capture #0.
   RegExpNode* captured_body = RegExpCapture::ToNode(input->tree,
                                                     0,
                                                     &compiler,
-                                                    EndNode::GetAccept(),
-                                                    EndNode::GetBacktrack());
+                                                    compiler.accept(),
+                                                    compiler.backtrack());
   // Add a .*? at the beginning, outside the body capture.
   // Note: We could choose to not add this if the regexp is anchored at
   //   the start of the input but I'm not sure how best to do that and
   //   since we don't even handle ^ yet I'm saving that optimization for
   //   later.
-  RegExpNode* node = RegExpQuantifier::ToNode(0,
-                                              RegExpQuantifier::kInfinity,
-                                              false,
-                                              new RegExpCharacterClass('.'),
-                                              &compiler,
-                                              captured_body,
-                                              EndNode::GetBacktrack());
-  Analysis analysis(&compiler);
-  analysis.Analyze(node);
-  return node;
+  RegExpNode* result = RegExpQuantifier::ToNode(0,
+                                                RegExpQuantifier::kInfinity,
+                                                false,
+                                                new RegExpCharacterClass('.'),
+                                                &compiler,
+                                                captured_body,
+                                                compiler.backtrack());
+  Analysis analysis;
+  analysis.EnsureAnalyzed(result);
+  return result;
 }
 
 
 RegExpMacroAssembler::~RegExpMacroAssembler() {
 }
 
 
 }}  // namespace v8::internal