Introduce text nodes

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 770 matching lines @@
 Handle<ByteArray> RegExpImpl::Re2kCode(Handle<JSRegExp> re) {
   FixedArray* value = FixedArray::cast(re->DataAt(JSRegExp::kRe2kDataIndex));
   return Handle<ByteArray>(ByteArray::cast(value->get(kRe2kCodeIndex)));
 }
 
 
 // -------------------------------------------------------------------
 // New regular expression engine
 
 
+void RegExpTree::AppendToText(RegExpText* text) {
+  UNREACHABLE();
+}
+
+
+void RegExpAtom::AppendToText(RegExpText* text) {
+  text->AddElement(TextElement::Atom(this));
+}
+
+
+void RegExpCharacterClass::AppendToText(RegExpText* text) {
+  text->AddElement(TextElement::CharClass(this));
+}
+
+
+void RegExpText::AppendToText(RegExpText* text) {
+  for (int i = 0; i < elements()->length(); i++)
+    text->AddElement(elements()->at(i));
+}
+
+
+TextElement TextElement::Atom(RegExpAtom* atom) {
+  TextElement result = TextElement(ATOM);
+  result.data.u_atom = atom;
+  return result;
+}
+
+
+TextElement TextElement::CharClass(
+      RegExpCharacterClass* char_class) {
+  TextElement result = TextElement(CHAR_CLASS);
+  result.data.u_char_class = char_class;
+  return result;
+}
+
+
 class RegExpCompiler {
  public:
   explicit RegExpCompiler(int capture_count);
 
   int AllocateRegister() { return next_register_++; }
 
   Handle<FixedArray> Assemble(RegExpMacroAssembler* assembler,
                               RegExpNode* start,
                               int capture_count,
                               bool case_independent);
@@ skipping 328 matching lines @@
 class TableEntryHeaderPrinter {
  public:
   explicit 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());
+    stream()->Add("{\\%k-\\%k|{", 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("}}");
@@ skipping 13 matching lines @@
   TableEntryBodyPrinter body_printer(stream(), that);
   that->table()->ForEach(&body_printer);
   PrintOnFailure(that, that->on_failure());
   for (int i = 0; i < that->alternatives()->length(); i++) {
     GuardedAlternative alt = that->alternatives()->at(i);
     alt.node()->Accept(this);
   }
 }
 
 
-void DotPrinter::VisitAtom(AtomNode* that) {
-  stream()->Add("  n%p [label=\"'%w'\", shape=doubleoctagon];\n",
-                that,
-                that->data());
+void DotPrinter::VisitText(TextNode* that) {
+  stream()->Add("  n%p [label=\"", that);
+  for (int i = 0; i < that->elements()->length(); i++) {
+    if (i > 0) stream()->Add(" ");
+    TextElement elm = that->elements()->at(i);
+    switch (elm.type) {
+      case TextElement::ATOM: {
+        stream()->Add("'%w'", elm.data.u_atom->data());
+        break;
+      }
+      case TextElement::CHAR_CLASS: {
+        RegExpCharacterClass* node = elm.data.u_char_class;
+        stream()->Add("[");
+        if (node->is_negated())
+          stream()->Add("^");
+        for (int j = 0; j < node->ranges()->length(); j++) {
+          CharacterRange range = node->ranges()->at(j);
+          stream()->Add("%k-%k", range.from(), range.to());
+        }
+        stream()->Add("]");
+        break;
+      }
+      default:
+        UNREACHABLE();
+    }
+  }
+  stream()->Add("\", shape=box, peripheries=2];\n");
   stream()->Add("  n%p -> n%p;\n", that, that->on_success());
   Visit(that->on_success());
   PrintOnFailure(that, that->on_failure());
 }
 
 
 void DotPrinter::VisitBackreference(BackreferenceNode* that) {
   stream()->Add("  n%p [label=\"$%i..$%i\", shape=doubleoctagon];\n",
                 that,
                 that->start_register(),
                 that->end_register());
   stream()->Add("  n%p -> n%p;\n", that, that->on_success());
   Visit(that->on_success());
   PrintOnFailure(that, that->on_failure());
 }
 
 
 void DotPrinter::VisitEnd(EndNode* that) {
   stream()->Add("  n%p [style=bold, shape=point];\n", that);
 }
 
 
-void DotPrinter::VisitCharacterClass(CharacterClassNode* that) {
-  stream()->Add("  n%p [label=\"[", that);
-  if (that->is_negated())
-    stream()->Add("^");
-  for (int i = 0; i < that->ranges()->length(); i++) {
-    CharacterRange range = that->ranges()->at(i);
-    stream()->Add("%k-%k", range.from(), range.to());
-  }
-  stream()->Add("]\"];\n");
-  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_) {
     case ActionNode::STORE_REGISTER:
-      stream()->Add("label=\"$%i:=%i\", shape=box",
+      stream()->Add("label=\"$%i:=%i\", shape=octagon",
                     that->data_.u_store_register.reg,
                     that->data_.u_store_register.value);
       break;
     case ActionNode::INCREMENT_REGISTER:
-      stream()->Add("label=\"$%i++\", shape=box",
+      stream()->Add("label=\"$%i++\", shape=octagon",
                     that->data_.u_increment_register.reg);
       break;
     case ActionNode::STORE_POSITION:
-      stream()->Add("label=\"$%i:=$pos\", shape=box",
+      stream()->Add("label=\"$%i:=$pos\", shape=octagon",
                     that->data_.u_position_register.reg);
       break;
     case ActionNode::RESTORE_POSITION:
-      stream()->Add("label=\"$pos:=$%i\", shape=box",
+      stream()->Add("label=\"$pos:=$%i\", shape=octagon",
                     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");
@@ skipping 51 matching lines @@
 #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);
+  ZoneList<TextElement>* elms = new ZoneList<TextElement>(1);
+  elms->Add(TextElement::Atom(this));
+  return new TextNode(elms, on_success, on_failure);
+}
+
+
+RegExpNode* RegExpText::ToNode(RegExpCompiler* compiler,
+                               RegExpNode* on_success,
+                               RegExpNode* on_failure) {
+  return new TextNode(elements(), on_success, on_failure);
 }
 
 
 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler,
                                          RegExpNode* on_success,
                                          RegExpNode* on_failure) {
-  return new CharacterClassNode(ranges(),
-                                is_negated(),
-                                on_success,
-                                on_failure);
+  ZoneList<TextElement>* elms = new ZoneList<TextElement>(1);
+  elms->Add(TextElement::CharClass(this));
+  return new TextNode(elms, on_success, on_failure);
 }
 
 
 RegExpNode* RegExpDisjunction::ToNode(RegExpCompiler* compiler,
                                       RegExpNode* on_success,
                                       RegExpNode* on_failure) {
   ZoneList<RegExpTree*>* alternatives = this->alternatives();
   int length = alternatives->length();
   ChoiceNode* result = new ChoiceNode(length, on_failure);
   for (int i = 0; i < length; i++) {
@@ skipping 235 matching lines @@
     case 'W':
       AddClassNegated(kWordRanges, kWordRangeCount, ranges);
       break;
     case 'd':
       AddClass(kDigitRanges, kDigitRangeCount, ranges);
       break;
     case 'D':
       AddClassNegated(kDigitRanges, kDigitRangeCount, ranges);
       break;
     case '.':
-      ranges->Add(CharacterRange(0x0000, 0xFFFF));
+      ranges->Add(CharacterRange::Everything());
       break;
     default:
       UNREACHABLE();
   }
 }
 
 
 // -------------------------------------------------------------------
 // Splay tree
 
@@ skipping 155 matching lines @@
   that->info()->being_analyzed = false;
   that->info()->been_analyzed = true;
 }
 
 
 void Analysis::VisitEnd(EndNode* that) {
   // nothing to do
 }
 
 
-void Analysis::VisitAtom(AtomNode* that) {
+void Analysis::VisitText(TextNode* 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;
@@ skipping 15 matching lines @@
   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
+  AddRange(CharacterRange::Everything());
 }
 
 
 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);
@@ skipping 56 matching lines @@
         return;
       } else {
         last = range.to() + 1;
       }
     }
   }
   AddRange(CharacterRange(last, 0xFFFF));
 }
 
 
-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));
+void DispatchTableConstructor::VisitText(TextNode* that) {
+  TextElement elm = that->elements()->at(0);
+  switch (elm.type) {
+    case TextElement::ATOM: {
+      uc16 c = elm.data.u_atom->data()[0];
+      AddRange(CharacterRange(c, c));
+      break;
+    }
+    case TextElement::CHAR_CLASS: {
+      RegExpCharacterClass* tree = elm.data.u_char_class;
+      ZoneList<CharacterRange>* ranges = tree->ranges();
+      if (tree->is_negated()) {
+        AddInverse(ranges);
+      } else {
+        for (int i = 0; i < ranges->length(); i++)
+          AddRange(ranges->at(i));
+      }
+      break;
+    }
+    default: {
+      UNIMPLEMENTED();
     }
   }
 }
 
 
-void DispatchTableConstructor::VisitAtom(AtomNode* that) {
-  uc16 c = that->data()[0];
-  AddRange(CharacterRange(c, c));
-}
-
-
 void DispatchTableConstructor::VisitAction(ActionNode* that) {
   that->on_success()->Accept(this);
 }
 
 
 Handle<FixedArray> RegExpEngine::Compile(RegExpParseResult* input,
                                          RegExpNode** node_return,
                                          bool ignore_case) {
   RegExpCompiler compiler(input->capture_count);
   // Wrap the body of the regexp in capture #0.
@@ skipping 27 matching lines @@
 }
 
 RegExpMacroAssembler::RegExpMacroAssembler() {
 }
 
 RegExpMacroAssembler::~RegExpMacroAssembler() {
 }
 
 
 }}  // namespace v8::internal