Add .*?(...) to regexps

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 617 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 RegExpCompiler;
 class DotPrinter;
 
 
 class RegExpCompiler {
  public:
   explicit RegExpCompiler(int 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;
@@ skipping 245 matching lines @@
           case Guard::LT:
             stream()->Add("$%i < %i", guard->reg(), guard->value());
             break;
         }
       }
       stream()->Add("]");
     }
     stream()->Add("\"];\n");
     that->choices()->at(i).node()->Accept(this);
   }
-  OS::PrintError("--- %p ---\n", static_cast<void*>(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());
@@ skipping 11 matching lines @@
   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=\"[...]\"];\n", 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:
@@ skipping 95 matching lines @@
 }
 
 
 RegExpNode* RegExpDisjunction::ToNode(RegExpCompiler* compiler,
                                       RegExpNode* on_success,
                                       RegExpNode* on_failure) {
   ZoneList<RegExpTree*>* children = nodes();
   int length = children->length();
   ChoiceNode* result = new ChoiceNode(length, on_failure);
   for (int i = 0; i < length; i++) {
-    GuardedAlternative child(compiler->Compile(children->at(i),
-                                               on_success,
-                                               on_failure));
+    GuardedAlternative child(children->at(i)->ToNode(compiler,
+                                                     on_success,
+                                                     on_failure));
     result->AddChild(child);
   }
   return result;
 }
 
 
 RegExpNode* RegExpQuantifier::ToNode(RegExpCompiler* compiler,
                                      RegExpNode* on_success,
                                      RegExpNode* on_failure) {
+  return ToNode(min(),
+                max(),
+                is_greedy(),
+                body(),
+                compiler,
+                on_success,
+                on_failure);
+}
+
+
+RegExpNode* RegExpQuantifier::ToNode(int min,
+                                     int max,
+                                     bool is_greedy,
+                                     RegExpTree* body,
+                                     RegExpCompiler* compiler,
+                                     RegExpNode* on_success,
+                                     RegExpNode* on_failure) {
   // x{f, t} becomes this:
   //
   //             (r++)<-.
   //               |     `
   //               |     (x)
   //               v     ^
   //      (r=0)-->(?)---/ [if r < t]
   //               |
   //   [if r >= f] \----> ...
   //
   //
   // TODO(someone): clear captures on repetition and handle empty
   //   matches.
-  bool has_min = min() > 0;
-  bool has_max = max() < RegExpQuantifier::kInfinity;
+  bool has_min = min > 0;
+  bool has_max = max < RegExpQuantifier::kInfinity;
   bool needs_counter = has_min || has_max;
   int reg_ctr = needs_counter ? compiler->AllocateRegister() : -1;
   ChoiceNode* center = new ChoiceNode(2, on_failure);
   RegExpNode* loop_return = needs_counter
       ? static_cast<RegExpNode*>(ActionNode::IncrementRegister(reg_ctr, center))
       : static_cast<RegExpNode*>(center);
-  RegExpNode* body_node = compiler->Compile(body(), loop_return, on_failure);
+  RegExpNode* body_node = body->ToNode(compiler, loop_return, on_failure);
   GuardedAlternative body_alt(body_node);
   if (has_max) {
-    Guard* body_guard = new Guard(reg_ctr, Guard::LT, 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());
+    Guard* rest_guard = new Guard(reg_ctr, Guard::GEQ, min);
     rest_alt.AddGuard(rest_guard);
   }
-  if (is_greedy()) {
+  if (is_greedy) {
     center->AddChild(body_alt);
     center->AddChild(rest_alt);
   } else {
     center->AddChild(rest_alt);
     center->AddChild(body_alt);
   }
   if (needs_counter) {
     return ActionNode::StoreRegister(reg_ctr, 0, center);
   } else {
     return center;
@@ skipping 35 matching lines @@
     // $reg = $pos
     // if [body]
     // then
     //   $pos = $reg
     //   escape submatch scope (drop all backtracks created in scope)
     //   succeed
     // else
     //   end submatch scope (nothing to clean up, just exit the scope)
     //   fail
     return ActionNode::BeginSubmatch(ActionNode::StorePosition(
-        position_register, compiler->Compile(body(),
+        position_register, body()->ToNode(compiler,
             ActionNode::RestorePosition(position_register,
                 ActionNode::EscapeSubmatch(on_success)),
             ActionNode::EndSubmatch(on_failure))));
   } else {
     // begin submatch scope
     // try
     // first if (body)
     //       then
     //         escape submatch scope
     //         fail
     //       else
     //         backtrack
     // second
     //       end submatch scope
     //       succeed
     ChoiceNode* try_node =
         new ChoiceNode(1, ActionNode::EndSubmatch(on_success));
-    RegExpNode* body_node = compiler->Compile(body(),
+    RegExpNode* body_node = body()->ToNode(compiler,
         ActionNode::EscapeSubmatch(on_failure),
         EndNode::GetBacktrack());
     GuardedAlternative body_alt(body_node);
     try_node->AddChild(body_alt);
     return ActionNode::BeginSubmatch(try_node);
   }
 }
 
 
 RegExpNode* RegExpCapture::ToNode(RegExpCompiler* compiler,
                                   RegExpNode* on_success,
                                   RegExpNode* on_failure) {
-  int start_reg = RegExpCapture::StartRegister(index());
-  int end_reg = RegExpCapture::EndRegister(index());
+  return ToNode(body(), index(), compiler, on_success, on_failure);
+}
+
+
+RegExpNode* RegExpCapture::ToNode(RegExpTree* body,
+                                  int index,
+                                  RegExpCompiler* compiler,
+                                  RegExpNode* on_success,
+                                  RegExpNode* on_failure) {
+  int start_reg = RegExpCapture::StartRegister(index);
+  int end_reg = RegExpCapture::EndRegister(index);
   RegExpNode* store_end = ActionNode::StorePosition(end_reg, on_success);
-  RegExpNode* body_node = compiler->Compile(body(), store_end, on_failure);
+  RegExpNode* body_node = body->ToNode(compiler, store_end, on_failure);
   return ActionNode::StorePosition(start_reg, body_node);
 }
 
 
 RegExpNode* RegExpAlternative::ToNode(RegExpCompiler* compiler,
                                       RegExpNode* on_success,
                                       RegExpNode* on_failure) {
   ZoneList<RegExpTree*>* children = nodes();
   RegExpNode* current = on_success;
   for (int i = children->length() - 1; i >= 0; i--) {
-    current = compiler->Compile(children->at(i), current, on_failure);
+    current = children->at(i)->ToNode(compiler, current, on_failure);
   }
   return current;
 }
 
 
 static const int kSpaceRangeCount = 20;
 static const uc16 kSpaceRanges[kSpaceRangeCount] = {
   0x0009, 0x0009, 0x000B, 0x000C, 0x0020, 0x0020, 0x00A0, 0x00A0,
   0x1680, 0x1680, 0x180E, 0x180E, 0x2000, 0x200A, 0x202F, 0x202F,
   0x205F, 0x205F, 0x3000, 0x3000
@@ skipping 353 matching lines @@
   outgoing.set_table(NULL);
   outgoing.Analyze(that->on_success());
 }
 
 
 void Analysis::VisitAction(ActionNode* that) {
   Analyze(that->on_success());
 }
 
 
-RegExpNode* RegExpCompiler::Compile(RegExpTree* tree,
-                                    RegExpNode* on_success,
-                                    RegExpNode* on_failure) {
-  return tree->ToNode(this, on_success, on_failure);
-}
-
-
 RegExpNode* RegExpEngine::Compile(RegExpParseResult* input) {
   RegExpCompiler compiler(input->capture_count);
-  RegExpNode* node = compiler.Compile(input->tree,
-                                      EndNode::GetAccept(),
-                                      EndNode::GetBacktrack());
+  // Wrap the body of the regexp in capture #0.
+  RegExpNode* captured_body = RegExpCapture::ToNode(input->tree,
+                                                    0,
+                                                    &compiler,
+                                                    EndNode::GetAccept(),
+                                                    EndNode::GetBacktrack());
+  // 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;
 }
 
 
 RegExpMacroAssembler::~RegExpMacroAssembler() {
 }
 
 
 }}  // namespace v8::internal