Implement $ for non-multiline.

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 974 matching lines @@
   }
 #endif
   return array;
 }
 
 
 bool RegExpNode::GoTo(RegExpCompiler* compiler) {
   // TODO(erikcorry): Implement support.
   if (info_.follows_word_interest ||
       info_.follows_newline_interest ||
-      info_.follows_start_interest ||
-      info_.at_end) {
+      info_.follows_start_interest) {
     return false;
   }
   if (label_.is_bound()) {
     compiler->macro_assembler()->GoTo(&label_);
     return true;
   } else {
     if (compiler->recursion_depth() > RegExpCompiler::kMaxRecursion) {
       compiler->macro_assembler()->GoTo(&label_);
       compiler->AddWork(this);
       return true;
     } else {
       compiler->IncrementRecursionDepth();
       bool how_it_went = Emit(compiler);
       compiler->DecrementRecursionDepth();
       return how_it_went;
     }
   }
 }
 
 
+// EndNodes are special.  Because they can be very common and they are very
+// short we normally inline them.  That is, if we are asked to emit a GoTo
+// we just emit the entire node.  Since they don't have successors this
+// works.
 bool EndNode::GoTo(RegExpCompiler* compiler) {
   if (info()->follows_word_interest ||
       info()->follows_newline_interest ||
-      info()->follows_start_interest ||
-      info()->at_end) {
+      info()->follows_start_interest) {
     return false;
   }
-  if (!label()->is_bound()) {
-    Bind(compiler->macro_assembler());
-  }
-  switch (action_) {
-    case ACCEPT:
-      compiler->macro_assembler()->Succeed();
-      break;
-    case BACKTRACK:
-      compiler->macro_assembler()->Backtrack();
-      break;
-  }
-  return true;
+  return Emit(compiler);
 }
 
 
 Label* RegExpNode::label() {
   return &label_;
 }
 
 
 bool EndNode::Emit(RegExpCompiler* compiler) {
   RegExpMacroAssembler* macro = compiler->macro_assembler();
   switch (action_) {
     case ACCEPT:
-      Bind(macro);
+      if (!label()->is_bound()) Bind(macro);
+      if (info()->at_end) {
+        Label succeed;
+        // LoadCurrentCharacter will go to the label if we are at the end of the
+        // input string.
+        macro->LoadCurrentCharacter(0, &succeed);
+        macro->Backtrack();
+        macro->Bind(&succeed);
+      }
       macro->Succeed();
       return true;
     case BACKTRACK:
-      Bind(macro);
+      if (!label()->is_bound()) Bind(macro);
+      ASSERT(!info()->at_end);
       macro->Backtrack();
       return true;
   }
   return false;
 }
 
 
 void GuardedAlternative::AddGuard(Guard* guard) {
   if (guards_ == NULL)
     guards_ = new ZoneList<Guard*>(1);
@@ skipping 18 matching lines @@
 }
 
 
 ActionNode* ActionNode::StorePosition(int reg, RegExpNode* on_success) {
   ActionNode* result = new ActionNode(STORE_POSITION, on_success);
   result->data_.u_position_register.reg = reg;
   return result;
 }
 
 
-ActionNode* ActionNode::SavePosition(int reg, RegExpNode* on_success) {
-  ActionNode* result = new ActionNode(SAVE_POSITION, on_success);
-  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;
   return result;
 }
 
 
-ActionNode* ActionNode::BeginSubmatch(int reg, RegExpNode* on_success) {
+ActionNode* ActionNode::BeginSubmatch(int stack_reg,
+                                      int position_reg,
+                                      RegExpNode* on_success) {
   ActionNode* result = new ActionNode(BEGIN_SUBMATCH, on_success);
-  result->data_.u_submatch_stack_pointer_register.reg = reg;
+  result->data_.u_submatch.stack_pointer_register = stack_reg;
+  result->data_.u_submatch.current_position_register = position_reg;
   return result;
 }
 
 
-ActionNode* ActionNode::EscapeSubmatch(int reg, RegExpNode* on_success) {
+ActionNode* ActionNode::EscapeSubmatch(int stack_reg,
+                                       bool restore_position,
+                                       int position_reg,
+                                       RegExpNode* on_success) {
   ActionNode* result = new ActionNode(ESCAPE_SUBMATCH, on_success);
-  result->data_.u_submatch_stack_pointer_register.reg = reg;
+  result->data_.u_submatch.stack_pointer_register = stack_reg;
+  if (restore_position) {
+    result->data_.u_submatch.current_position_register = position_reg;
+  } else {
+    result->data_.u_submatch.current_position_register = -1;
+  }
   return result;
 }
 
 
 #define DEFINE_ACCEPT(Type)                                          \
   void Type##Node::Accept(NodeVisitor* visitor) {                    \
     visitor->Visit##Type(this);                                      \
   }
 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
 #undef DEFINE_ACCEPT
@@ skipping 188 matching lines @@
   }
   macro_assembler->Bind(&success);
 }
 
 
 
 bool TextNode::Emit(RegExpCompiler* compiler) {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   Bind(macro_assembler);
   int element_count = elms_->length();
+  ASSERT(element_count != 0);
   int cp_offset = 0;
+  if (info()->at_end) {
+    macro_assembler->Backtrack();
+    return true;
+  }
   // First, handle straight character matches.
   for (int i = 0; i < element_count; i++) {
     TextElement elm = elms_->at(i);
     if (elm.type == TextElement::ATOM) {
       Vector<const uc16> quarks = elm.data.u_atom->data();
       if (compiler->ignore_case()) {
         EmitAtomNonLetters(macro_assembler,
                            elm,
                            quarks,
                            on_failure_->label(),
@@ skipping 140 matching lines @@
       bool ok = on_success()->GoTo(compiler);
       if (!ok) {
         undo.Unuse();
         return false;
       }
       macro->Bind(&undo);
       macro->PopRegister(data_.u_position_register.reg);
       macro->Backtrack();
       break;
     }
-    case SAVE_POSITION:
-      macro->WriteCurrentPositionToRegister(
-          data_.u_position_register.reg);
-      break;
     case RESTORE_POSITION:
       macro->ReadCurrentPositionFromRegister(
           data_.u_position_register.reg);
       break;
     case BEGIN_SUBMATCH:
+      macro->WriteCurrentPositionToRegister(
+          data_.u_submatch.current_position_register);
       macro->WriteStackPointerToRegister(
-          data_.u_submatch_stack_pointer_register.reg);
+          data_.u_submatch.stack_pointer_register);
       break;
     case ESCAPE_SUBMATCH:
+      if (info()->at_end) {
+        Label at_end;
+        // Load current character jumps to the label if we are beyond the string
+        // end.
+        macro->LoadCurrentCharacter(0, &at_end);
+        macro->Backtrack();
+        macro->Bind(&at_end);
+      }
+      if (data_.u_submatch.current_position_register != -1) {
+        macro->ReadCurrentPositionFromRegister(
+            data_.u_submatch.current_position_register);
+      }
       macro->ReadStackPointerFromRegister(
-          data_.u_submatch_stack_pointer_register.reg);
+          data_.u_submatch.stack_pointer_register);
       break;
     default:
       UNREACHABLE();
       return false;
   }
   return on_success()->GoTo(compiler);
 }
 
 
 bool BackReferenceNode::Emit(RegExpCompiler* compiler) {
   RegExpMacroAssembler* macro = compiler->macro_assembler();
   Bind(macro);
   // Check whether the registers are uninitialized and always
   // succeed if they are.
   macro->IfRegisterLT(start_reg_, 0, on_success()->label());
   macro->IfRegisterLT(end_reg_, 0, on_success()->label());
   ASSERT_EQ(start_reg_ + 1, end_reg_);
-  if (compiler->ignore_case()) {
-    macro->CheckNotBackReferenceIgnoreCase(start_reg_, on_failure_->label());
+  if (info()->at_end) {
+    // If we are constrained to match at the end of the input then succeed
+    // iff the back reference is empty.
+    macro->CheckNotRegistersEqual(start_reg_, end_reg_, on_failure_->label());
   } else {
-    macro->CheckNotBackReference(start_reg_, on_failure_->label());
+    if (compiler->ignore_case()) {
+      macro->CheckNotBackReferenceIgnoreCase(start_reg_, on_failure_->label());
+    } else {
+      macro->CheckNotBackReference(start_reg_, on_failure_->label());
+    }
   }
   return on_success()->GoTo(compiler);
 }
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
 
 
 #ifdef DEBUG
@@ skipping 214 matching lines @@
                     that->data_.u_store_register.value);
       break;
     case ActionNode::INCREMENT_REGISTER:
       stream()->Add("label=\"$%i++\", shape=octagon",
                     that->data_.u_increment_register.reg);
       break;
     case ActionNode::STORE_POSITION:
       stream()->Add("label=\"$%i:=$pos\", shape=octagon",
                     that->data_.u_position_register.reg);
       break;
-    case ActionNode::SAVE_POSITION:
-      stream()->Add("label=\"$%i:=$pos\", shape=octagon",
-                    that->data_.u_position_register.reg);
-      break;
     case ActionNode::RESTORE_POSITION:
       stream()->Add("label=\"$pos:=$%i\", shape=octagon",
                     that->data_.u_position_register.reg);
       break;
     case ActionNode::BEGIN_SUBMATCH:
-      stream()->Add("label=\"begin\", shape=septagon");
+      stream()->Add("label=\"$%i:=$pos,begin\", shape=septagon",
+                    that->data_.u_submatch.current_position_register);
       break;
     case ActionNode::ESCAPE_SUBMATCH:
       stream()->Add("label=\"escape\", shape=septagon");
       break;
   }
   stream()->Add("];\n");
   PrintAttributes(that);
   stream()->Add("  n%p -> n%p;\n", that, that->on_success());
   Visit(that->on_success());
 }
@@ skipping 210 matching lines @@
     // 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(
         stack_pointer_register,
-        ActionNode::SavePosition(
-            position_register,
-            body()->ToNode(
-                compiler,
-                ActionNode::RestorePosition(
-                    position_register,
-                    ActionNode::EscapeSubmatch(stack_pointer_register,
-                                               on_success)),
-                on_failure)));
+        position_register,
+        body()->ToNode(
+            compiler,
+            ActionNode::EscapeSubmatch(
+                stack_pointer_register,
+                true,                    // Also restore input position.
+                position_register,
+                on_success),
+            on_failure));
   } else {
     // begin submatch scope
     // try
     // first if (body)
     //       then
     //         escape submatch scope
     //         fail
     //       else
     //         backtrack
     // second
     //       end submatch scope
     //       restore current position
     //       succeed
     ChoiceNode* try_node =
         new ChoiceNode(1, ActionNode::RestorePosition(position_register,
                                                       on_success));
     RegExpNode* body_node = body()->ToNode(
         compiler,
-        ActionNode::EscapeSubmatch(stack_pointer_register, on_failure),
+        ActionNode::EscapeSubmatch(stack_pointer_register,
+                                   false,        // Don't also restore position
+                                   0,            // Unused arguments.
+                                   on_failure),
         compiler->backtrack());
     GuardedAlternative body_alt(body_node);
     try_node->AddAlternative(body_alt);
     return ActionNode::BeginSubmatch(stack_pointer_register,
-                                     ActionNode::SavePosition(
-                                         position_register,
-                                         try_node));
+                                     position_register,
+                                     try_node);
   }
 }
 
 
 RegExpNode* RegExpCapture::ToNode(RegExpCompiler* compiler,
                                   RegExpNode* on_success,
                                   RegExpNode* on_failure) {
   return ToNode(body(), index(), compiler, on_success, on_failure);
 }
 
@@ skipping 224 matching lines @@
 
 RegExpNode* ActionNode::PropagateForward(NodeInfo* info) {
   NodeInfo full_info(*this->info());
   full_info.AddFromPreceding(info);
   RegExpNode* sibling = GetSibling(&full_info);
   if (sibling != NULL) return sibling;
   EnsureSiblings();
   ActionNode* action = new ActionNode(*this);
   action->info()->AddFromPreceding(&full_info);
   AddSibling(action);
-  action->set_on_success(action->on_success()->PropagateForward(info));
+  if (type_ != ESCAPE_SUBMATCH) {
+    action->set_on_success(action->on_success()->PropagateForward(info));
+  }
   return action;
 }
 
 
 RegExpNode* ChoiceNode::PropagateForward(NodeInfo* info) {
   NodeInfo full_info(*this->info());
   full_info.AddFromPreceding(info);
   RegExpNode* sibling = GetSibling(&full_info);
   if (sibling != NULL) return sibling;
   EnsureSiblings();
   ChoiceNode* choice = new ChoiceNode(*this);
   choice->info()->AddFromPreceding(&full_info);
   AddSibling(choice);
   ZoneList<GuardedAlternative>* old_alternatives = alternatives();
   int count = old_alternatives->length();
   choice->alternatives_ = new ZoneList<GuardedAlternative>(count);
   for (int i = 0; i < count; i++) {
     GuardedAlternative alternative = old_alternatives->at(i);
     alternative.set_node(alternative.node()->PropagateForward(info));
     choice->alternatives()->Add(alternative);
   }
+  if (!choice->on_failure_->IsBacktrack()) {
+    choice->on_failure_ = choice->on_failure_->PropagateForward(info);
+  }
   return choice;
 }
 
 
 RegExpNode* EndNode::PropagateForward(NodeInfo* info) {
   return PropagateToEndpoint(this, info);
 }
 
 
 RegExpNode* BackReferenceNode::PropagateForward(NodeInfo* info) {
-  return PropagateToEndpoint(this, info);
+  NodeInfo full_info(*this->info());
+  full_info.AddFromPreceding(info);
+  RegExpNode* sibling = GetSibling(&full_info);
+  if (sibling != NULL) return sibling;
+  EnsureSiblings();
+  BackReferenceNode* back_ref = new BackReferenceNode(*this);
+  back_ref->info()->AddFromPreceding(&full_info);
+  AddSibling(back_ref);
+  // TODO(erikcorry): A back reference has to have two successors (by default

[Christian Plesner Hansen, 2008/11/28 08:44:53]

I wonder if maybe we always have to propagate to the on-failure continuation. 
In most cases it will be a backtrack node and it won't matter, but it may not be
and in that case we must propagate.

+  // the same node).  The first is used if the back reference matches a non-
+  // empty back reference, the second if it matches an empty one.  This doesn't
+  // matter for at_end, which is the only one implemented right now, but it will
+  // matter for other pieces of info.
+  back_ref->set_on_success(back_ref->on_success()->PropagateForward(info));
+  return back_ref;
 }
 
 
 RegExpNode* TextNode::PropagateForward(NodeInfo* info) {
   return PropagateToEndpoint(this, info);
 }
 
 
 // -------------------------------------------------------------------
 // Splay tree
@@ skipping 349 matching lines @@
                                               captured_body,
                                               compiler.backtrack());
   if (node_return != NULL) *node_return = node;
   Analysis analysis(ignore_case);
   analysis.EnsureAnalyzed(node);
 
   if (!FLAG_irregexp) {
     return Handle<FixedArray>::null();
   }
 
+  if (is_multiline && !FLAG_attempt_multiline_irregexp) {
+    return Handle<FixedArray>::null();
+  }
+
   if (FLAG_irregexp_native) {
 #ifdef ARM
     UNIMPLEMENTED();
 #else  // IA32
     RegExpMacroAssemblerIA32 macro_assembler(RegExpMacroAssemblerIA32::UC16,
                                              (input->capture_count + 1) * 2);
     return compiler.Assemble(&macro_assembler,
                              node,
                              input->capture_count);
 #endif
   }
   byte codes[1024];
   IrregexpAssembler assembler(Vector<byte>(codes, 1024));
   RegExpMacroAssemblerIrregexp macro_assembler(&assembler);
   return compiler.Assemble(&macro_assembler,
                            node,
                            input->capture_count);
 }
 
 
 }}  // namespace v8::internal