* We want to be able to find atoms and character classes without advancing th...

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 22 matching lines @@
 #include "ast.h"
 #include "execution.h"
 #include "factory.h"
 #include "jsregexp-inl.h"
 #include "platform.h"
 #include "runtime.h"
 #include "top.h"
 #include "compilation-cache.h"
 #include "string-stream.h"
 #include "parser.h"
+#include "regexp-macro-assembler.h"
 
 // Including pcre.h undefines DEBUG to avoid getting debug output from
 // the JSCRE implementation. Make sure to redefine it in debug mode
 // after having included the header file.
 #ifdef DEBUG
 #include "third_party/jscre/pcre.h"
 #define DEBUG
 #else
 #include "third_party/jscre/pcre.h"
 #endif
@@ skipping 572 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 ExecutionState;
+class RegExpCompiler;
+class DotPrinter;
 
 
 class RegExpCompiler {
  public:
   explicit RegExpCompiler(int capture_count)
-    : next_register_(2 * capture_count) { }
+    : next_register_(2 * capture_count),
+      work_list_(NULL) { }
 
   RegExpNode* Compile(RegExpTree* tree,
                       RegExpNode* on_success,
                       RegExpNode* on_failure);
 
   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_;
+  }
  private:
   int next_register_;
+  List<RegExpNode*>* work_list_;
+  RegExpMacroAssembler* macro_assembler_;
 };
 
 
+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);
+  }
+  Handle<FixedArray> array = Factory::NewFixedArray(3);
+  array->set(kImplementationOffset,
+             Smi::FromInt(macro_assembler->Implementation()),
+             SKIP_WRITE_BARRIER);
+  array->set(kNumberOfRegistersOffset,
+             Smi::FromInt(next_register_),
+             SKIP_WRITE_BARRIER);
+  Handle<Object> code = macro_assembler->GetCode();
+  work_list_ = NULL;
+  return array;
+}
+
+
 #define FOR_EACH_NODE_TYPE(VISIT)                                    \
   VISIT(End)                                                         \
   VISIT(Atom)                                                        \
   VISIT(Action)                                                      \
   VISIT(Choice)                                                      \
   VISIT(Backreference)                                               \
   VISIT(CharacterClass)
 
 
-class RegExpNode: public ZoneObject {
- public:
-  virtual ~RegExpNode() { }
-  virtual void Accept(NodeVisitor* visitor) = 0;
-};
+void RegExpNode::GoTo(RegExpCompiler* compiler) {
+  if (label.is_bound()) {
+    compiler->macro_assembler()->GoTo(&label);
+  } else {
+    Emit(compiler);
+  }
+}
+
+
+void RegExpNode::EmitAddress(RegExpCompiler* compiler) {
+  compiler->macro_assembler()->EmitOrLink(&label);
+}
 
 
 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:
   RegExpNode* on_success_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK };
   virtual void Accept(NodeVisitor* visitor);
   static EndNode* GetAccept() { return &kAccept; }
   static EndNode* GetBacktrack() { return &kBacktrack; }
+  virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
  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 Accept(NodeVisitor* visitor);
   Vector<const uc16> data() { return data_; }
   RegExpNode* on_failure() { return on_failure_; }
+  virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
  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 Accept(NodeVisitor* visitor);
   RegExpNode* on_failure() { return on_failure_; }
   int start_register() { return start_reg_; }
   int end_register() { return end_reg_; }
+  virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
  private:
   RegExpNode* on_failure_;
   int start_reg_;
   int end_reg_;
 };
 
 
 class CharacterClassNode: public SeqRegExpNode {
  public:
   CharacterClassNode(ZoneList<CharacterRange>* ranges,
                      bool is_negated,
                      RegExpNode* on_success,
                      RegExpNode* on_failure)
     : SeqRegExpNode(on_success),
       on_failure_(on_failure),
       ranges_(ranges),
-      is_negated_(is_negated ){ }
+      is_negated_(is_negated ) { }
   virtual void Accept(NodeVisitor* visitor);
   ZoneList<CharacterRange>* ranges() { return ranges_; }
   bool is_negated() { return is_negated_; }
   RegExpNode* on_failure() { return on_failure_; }
+  virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
   static void AddInverseToTable(List<CharacterRange> ranges,
                                 DispatchTable* table,
                                 int index);
  private:
   RegExpNode* on_failure_;
   ZoneList<CharacterRange>* ranges_;
   bool is_negated_;
 };
 
 
@@ skipping 37 matching lines @@
  public:
   explicit ChoiceNode(int expected_size, RegExpNode* on_failure)
     : on_failure_(on_failure),
       choices_(new ZoneList<GuardedAlternative>(expected_size)),
       visited_(false) { }
   virtual void Accept(NodeVisitor* visitor);
   void AddChild(GuardedAlternative node) { choices()->Add(node); }
   ZoneList<GuardedAlternative>* choices() { return choices_; }
   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; }
  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,
     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);
-  Type type;
+  virtual void Emit(RegExpCompiler* compiler);
+ private:
   union {
     struct {
       int reg;
       int value;
     } u_store_register;
     struct {
       int reg;
     } u_increment_register;
     struct {
       int reg;
     } u_position_register;
-  } data;
- private:
-  ActionNode(Type _type, RegExpNode* on_success)
+  } data_;
+  ActionNode(Type type, RegExpNode* on_success)
     : SeqRegExpNode(on_success),
-      type(_type) { }
+      type_(type) { }
+  Type type_;
+  friend class DotPrinter;
 };
 
 
 ActionNode* ActionNode::StoreRegister(int reg,
                                       int val,
                                       RegExpNode* on_success) {
   ActionNode* result = new ActionNode(STORE_REGISTER, on_success);
-  result->data.u_store_register.reg = reg;
-  result->data.u_store_register.value = val;
+  result->data_.u_store_register.reg = reg;
+  result->data_.u_store_register.value = val;
   return result;
 }
 
 
 ActionNode* ActionNode::IncrementRegister(int reg, RegExpNode* on_success) {
   ActionNode* result = new ActionNode(INCREMENT_REGISTER, on_success);
-  result->data.u_increment_register.reg = reg;
+  result->data_.u_increment_register.reg = reg;
   return result;
 }
 
 
 ActionNode* ActionNode::StorePosition(int reg, RegExpNode* on_success) {
   ActionNode* result = new ActionNode(STORE_POSITION, on_success);
-  result->data.u_position_register.reg = reg;
+  result->data_.u_position_register.reg = reg;
   return result;
 }
 
 
 ActionNode* ActionNode::RestorePosition(int reg, RegExpNode* on_success) {
   ActionNode* result = new ActionNode(RESTORE_POSITION, on_success);
-  result->data.u_position_register.reg = reg;
+  result->data_.u_position_register.reg = reg;
   return result;
 }
 
 
 ActionNode* ActionNode::BeginSubmatch(RegExpNode* on_success) {
   return new ActionNode(BEGIN_SUBMATCH, on_success);
 }
 
 
 ActionNode* ActionNode::EscapeSubmatch(RegExpNode* on_success) {
@@ skipping 18 matching lines @@
 
 #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.
+
+
+void ChoiceNode::Emit(RegExpCompiler* compiler) {
+  // TODO(erikcorry): Implement this.
+  UNREACHABLE();
+}
+
+
+void ActionNode::Emit(RegExpCompiler* compiler) {
+  RegExpMacroAssembler* macro = compiler->macro_assembler();
+  switch (type_) {
+    case STORE_REGISTER:
+      macro->SetRegister(data_.u_store_register.reg,
+                         data_.u_store_register.value);
+      break;
+    case INCREMENT_REGISTER:
+      macro->AdvanceRegister(data_.u_increment_register.reg, 1);
+      break;
+    case STORE_POSITION:
+      macro->PushCurrentPosition();
+      break;
+    case RESTORE_POSITION:
+      macro->PopCurrentPosition();
+      break;
+    case BEGIN_SUBMATCH:
+      // TODO(erikcorry): Implement this.
+      UNREACHABLE();
+      break;
+    case ESCAPE_SUBMATCH:
+      // TODO(erikcorry): Implement this.
+      UNREACHABLE();
+      break;
+    case END_SUBMATCH:
+      // TODO(erikcorry): Implement this.
+      UNREACHABLE();
+      break;
+  }
+}
+
+
+// -------------------------------------------------------------------
 // Dot/dotty output
 
 
 #ifdef DEBUG
 
 
 class DotPrinter: public NodeVisitor {
  public:
   DotPrinter() : stream_(&alloc_) { }
   void PrintNode(const char* label, RegExpNode* node);
@@ skipping 110 matching lines @@
 void DotPrinter::VisitCharacterClass(CharacterClassNode* that) {
   stream()->Add("  n%p [label=\"[...]\"];\n", that);
   stream()->Add("  n%p -> n%p;\n", that, that->on_success());
   Visit(that->on_success());
   PrintOnFailure(that, that->on_failure());
 }
 
 
 void DotPrinter::VisitAction(ActionNode* that) {
   stream()->Add("  n%p [", that);
-  switch (that->type) {
+  switch (that->type_) {
     case ActionNode::STORE_REGISTER:
       stream()->Add("label=\"$%i:=%i\", shape=box",
-                    that->data.u_store_register.reg,
-                    that->data.u_store_register.value);
+                    that->data_.u_store_register.reg,
+                    that->data_.u_store_register.value);
       break;
     case ActionNode::INCREMENT_REGISTER:
       stream()->Add("label=\"$%i++\", shape=box",
-                    that->data.u_increment_register.reg);
+                    that->data_.u_increment_register.reg);
       break;
     case ActionNode::STORE_POSITION:
       stream()->Add("label=\"$%i:=$pos\", shape=box",
-                    that->data.u_position_register.reg);
+                    that->data_.u_position_register.reg);
       break;
     case ActionNode::RESTORE_POSITION:
       stream()->Add("label=\"$pos:=$%i\", shape=box",
-                    that->data.u_position_register.reg);
+                    that->data_.u_position_register.reg);
       break;
     case ActionNode::BEGIN_SUBMATCH:
       stream()->Add("label=\"begin\", shape=septagon");
       break;
     case ActionNode::ESCAPE_SUBMATCH:
       stream()->Add("label=\"escape\", shape=septagon");
       break;
     case ActionNode::END_SUBMATCH:
       stream()->Add("label=\"end\", shape=septagon");
       break;
   }
   stream()->Add("];\n");
   stream()->Add("  n%p -> n%p;\n", that, that->on_success());
   Visit(that->on_success());
 }
 
 
 class DispatchTableDumper {
  public:
-  DispatchTableDumper(StringStream* stream) : stream_(stream) { }
+  explicit 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.to());
   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(", ");
+      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));
   OS::PrintError("%s", *stream.ToCString());
 }
 
 
 void RegExpEngine::DotPrint(const char* label, RegExpNode* node) {
   DotPrinter printer;
   printer.PrintNode(label, node);
 }
 
 
-#endif // DEBUG
+#endif  // DEBUG
 
 
 // -------------------------------------------------------------------
 // Tree to graph conversion
 
 
 RegExpNode* RegExpAtom::ToNode(RegExpCompiler* compiler,
                                RegExpNode* on_success,
                                RegExpNode* on_failure) {
   return new AtomNode(data(), on_success, on_failure);
@@ skipping 386 matching lines @@
     return empty();
 }
 
 
 // -------------------------------------------------------------------
 // Analysis
 
 
 class Analysis: public NodeVisitor {
  public:
-  Analysis(RegExpCompiler* compiler)
+  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:
-  Analysis(Analysis* prev) { *this = *prev; }
+  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:
-  AnalysisBuilder(Analysis* prev) : Analysis(prev) { }
+  explicit AnalysisBuilder(Analysis* prev) : Analysis(prev) { }
   void set_table(DispatchTable* value) { table_ = value; }
   void set_choice_index(int value) { choice_index_ = value; }
 };
 
 
 void Analysis::VisitEnd(EndNode* that) {
   // nothing to do
 }
 
 
 class AddDispatchRange {
  public:
-  AddDispatchRange(Analysis* analysis) : analysis_(analysis) { }
+  explicit AddDispatchRange(Analysis* analysis) : analysis_(analysis) { }
   void Call(uc32 from, DispatchTable::Entry entry);
  private:
   Analysis* analysis_;
 };
 
 
 void AddDispatchRange::Call(uc32 from, DispatchTable::Entry entry) {
   CharacterRange range(from, entry.to());
   analysis_->table()->AddRange(range, analysis_->choice_index());
 }
@@ skipping 64 matching lines @@
 
 RegExpNode* RegExpEngine::Compile(RegExpParseResult* input) {
   RegExpCompiler compiler(input->capture_count);
   RegExpNode* node = compiler.Compile(input->tree,
                                       EndNode::GetAccept(),
                                       EndNode::GetBacktrack());
   return node;
 }
 
 
+RegExpMacroAssembler::~RegExpMacroAssembler() {
+}
+
+
 }}  // namespace v8::internal