* Fix bug in regexp parser.

regexp2000/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 796 matching lines @@
   DispatchTable table_;
 };
 
 
 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) {
     ActionNode* result = new ActionNode(STORE_REGISTER, on_success);
     result->data_.u_store_register.reg_ = reg;
     result->data_.u_store_register.value_ = val;
     return result;
   }
   static ActionNode* IncrementRegister(int reg, RegExpNode* on_success) {
     ActionNode* result = new ActionNode(INCREMENT_REGISTER, on_success);
     result->data_.u_increment_register.reg_ = reg;
     return result;
   }
   static ActionNode* StorePosition(int reg, RegExpNode* on_success) {
     ActionNode* result = new ActionNode(STORE_POSITION, on_success);
-    result->data_.u_store_position.reg_ = reg;
+    result->data_.u_position_register.reg_ = reg;
+    return result;
+  }
+  static ActionNode* RestorePosition(int reg, RegExpNode* on_success) {
+    ActionNode* result = new ActionNode(RESTORE_POSITION, on_success);
+    result->data_.u_position_register.reg_ = reg;
     return result;
   }
   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);
   Type type() { return type_; }
  private:
   ActionNode(Type type, RegExpNode* on_success)
     : SeqRegExpNode(on_success),
       type_(type) { }
   Type type_;
   union {
     struct {
       int reg_;
       int value_;
     } u_store_register;
     struct {
       int reg_;
     } u_increment_register;
     struct {
       int reg_;
-    } u_store_position;
+    } u_position_register;
   } data_;
 };
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
 
 void DotPrinter::PrintNode(const char* label, RegExpNode* node) {
   stream()->Add("digraph G {\n  graph [label=\"");
   for (int i = 0; label[i]; i++) {
@@ skipping 110 matching lines @@
       out->stream()->Add("label=\"$%i:=%i\", shape=box",
                          data_.u_store_register.reg_,
                          data_.u_store_register.value_);
       break;
     case INCREMENT_REGISTER:
       out->stream()->Add("label=\"$%i++\", shape=box",
                          data_.u_increment_register.reg_);
       break;
     case STORE_POSITION:
       out->stream()->Add("label=\"$%i:=$pos\", shape=box",
-                         data_.u_store_position.reg_);
+                         data_.u_position_register.reg_);
+      break;
+    case RESTORE_POSITION:
+      out->stream()->Add("label=\"$pos:=$%i\", shape=box",
+                         data_.u_position_register.reg_);
       break;
     case BEGIN_SUBMATCH:
       out->stream()->Add("label=\"begin\", shape=septagon");
       break;
     case ESCAPE_SUBMATCH:
       out->stream()->Add("label=\"escape\", shape=septagon");
       break;
     case END_SUBMATCH:
       out->stream()->Add("label=\"end\", shape=septagon");
       break;
@@ skipping 50 matching lines @@
   //      (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 needs_counter = has_min || has_max;
-  int reg = needs_counter ? compiler->AllocateRegister() : -1;
+  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, center))
+      ? static_cast<RegExpNode*>(ActionNode::IncrementRegister(reg_ctr, center))
       : static_cast<RegExpNode*>(center);
   RegExpNode* body_node = compiler->Compile(body(), loop_return, on_failure);
   GuardedAlternative body_alt(body_node);
   if (has_max) {
-    Guard* body_guard = new Guard(reg, 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, Guard::GEQ, 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);
   } else {
     center->AddChild(rest_alt);
     center->AddChild(body_alt);
   }
   if (needs_counter) {
-    return ActionNode::StoreRegister(reg, 0, center);
+    return ActionNode::StoreRegister(reg_ctr, 0, center);
   } else {
     return center;
   }
 }
 
 
 RegExpNode* RegExpAssertion::ToNode(RegExpCompiler* compiler,
                                     RegExpNode* on_success,
                                     RegExpNode* on_failure) {
   // TODO(self): implement assertions.
@@ skipping 15 matching lines @@
                                 RegExpNode* on_success,
                                 RegExpNode* on_failure) {
   return on_success;
 }
 
 
 RegExpNode* RegExpLookahead::ToNode(RegExpCompiler* compiler,
                                     RegExpNode* on_success,
                                     RegExpNode* on_failure) {
   if (is_positive()) {
-    RegExpNode* proceed = ActionNode::EndSubmatch(on_success);
-    RegExpNode* escape = ActionNode::EscapeSubmatch(on_failure);
-    RegExpNode* body_node = compiler->Compile(body(), proceed, escape);
-    return ActionNode::BeginSubmatch(body_node);
+    int position_register = compiler->AllocateRegister();
+    // begin submatch scope
+    // $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(),
+            ActionNode::RestorePosition(position_register,
+                ActionNode::EscapeSubmatch(on_success)),
+            ActionNode::EndSubmatch(on_failure))));
   } else {
-    RegExpNode* failed = ActionNode::EscapeSubmatch(on_success);
-    RegExpNode* succeeded = ActionNode::EndSubmatch(on_failure);
-    RegExpNode* body_node = compiler->Compile(body(), succeeded, failed);
-    return ActionNode::BeginSubmatch(body_node);
+    // 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(),
+        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());
   RegExpNode* store_end = ActionNode::StorePosition(end_reg, on_success);
@@ skipping 232 matching lines @@
 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