* Add support for positive lookahead assertions and negative...

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 994 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(RegExpNode* on_success) {
-  return new ActionNode(BEGIN_SUBMATCH, on_success);
+ActionNode* ActionNode::BeginSubmatch(int reg, RegExpNode* on_success) {
+  ActionNode* result = new ActionNode(BEGIN_SUBMATCH, on_success);
+  result->data_.u_submatch_stack_pointer_register.reg = reg;
+  return result;
 }
 
 
-ActionNode* ActionNode::EscapeSubmatch(RegExpNode* on_success) {
-  return new ActionNode(ESCAPE_SUBMATCH, on_success);
+ActionNode* ActionNode::EscapeSubmatch(int reg, RegExpNode* on_success) {
+  ActionNode* result = new ActionNode(ESCAPE_SUBMATCH, on_success);
+  result->data_.u_submatch_stack_pointer_register.reg = reg;
+  return result;
 }
 
 
-ActionNode* ActionNode::EndSubmatch(RegExpNode* on_success) {
-  return new ActionNode(END_SUBMATCH, on_success);
-}
-
-
 #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.
@@ skipping 24 matching lines @@
       case TextElement::ATOM: {
         Vector<const uc16> quarks = elm.data.u_atom->data();
         macro_assembler->CheckCharacters(quarks,
                                          cp_offset,
                                          on_failure_->label());
         cp_offset += quarks.length();
         break;
       }
       case TextElement::CHAR_CLASS: {
         RegExpCharacterClass* cc = elm.data.u_char_class;
-        if (cc->is_negated()) return false;
         macro_assembler->LoadCurrentCharacter(cp_offset, on_failure_->label());
         cp_offset++;
 
         ZoneList<CharacterRange>* ranges = cc->ranges();
 
-        Label found;
+        Label success;
+
+        Label *char_is_in_class =
+            cc->is_negated() ? on_failure_->label() : &success;
 
         int range_count = ranges->length();
 
         if (range_count == 0) {
-          on_failure()->GoTo(compiler);
+          if (!cc->is_negated()) {
+            on_failure()->GoTo(compiler);
+          }
           break;
         }
 
         for (int i = 0; i < range_count - 1; i++) {
           CharacterRange& range = (*ranges)[i];
           Label next_range;
           uc16 from = range.from();
           uc16 to = range.to();
-          if (from != 0) {
-            macro_assembler->CheckCharacterLT(from, &next_range);
-          }
-          if (to != 0xffff) {
-            macro_assembler->CheckCharacterLT(to + 1, &found);
+          if (to == from) {
+            macro_assembler->CheckCharacter(to, char_is_in_class);
           } else {
-            macro_assembler->AdvanceCurrentPosition(1);
-            on_success()->GoTo(compiler);
+            if (from != 0) {
+              macro_assembler->CheckCharacterLT(from, &next_range);
+            }
+            if (to != 0xffff) {
+              macro_assembler->CheckCharacterLT(to + 1, char_is_in_class);
+            } else {
+              macro_assembler->GoTo(char_is_in_class);
+            }
           }
           macro_assembler->Bind(&next_range);
         }
 
-        CharacterRange& range = (*ranges)[range_count - 1];
-        uc16 from = range.from();
-        uc16 to = range.to();
-        if (from != 0) {
-          macro_assembler->CheckCharacterLT(from, on_failure_->label());
+        if (range_count != 0) {
+          CharacterRange& range = (*ranges)[range_count - 1];
+          uc16 from = range.from();
+          uc16 to = range.to();
+
+          if (to == from) {
+            if (cc->is_negated()) {
+              macro_assembler->CheckCharacter(to, on_failure_->label());
+            } else {
+              macro_assembler->CheckNotCharacter(to, on_failure_->label());
+            }
+          } else {
+            if (from != 0) {
+              if (!cc->is_negated()) {
+                macro_assembler->CheckCharacterLT(from, &on_failure_->label());
+              } else {
+                macro_assembler->CheckCharacterLT(from, &success);
+              }
+            }
+            if (to != 0xffff) {
+              if (!cc->is_negated()) {
+                macro_assembler->CheckCharacterGT(to, on_failure_->label());
+              } else {
+                macro_assembler->CheckCharacterLT(to + 1, on_failure_->label());
+              }
+            } else {
+              if (cc->is_negated()) {
+                macro_assembler->GoTo(on_failure_->label());
+              }
+            }
+          }
+        } else if (cc->is_negated()) {
+          macro_assembler->GoTo(on_failure_->label());
         }
-        if (to != 0xffff) {
-          macro_assembler->CheckCharacterGT(to, on_failure_->label());
-        }
-        compiler->AddWork(on_failure_);
-        macro_assembler->Bind(&found);
+
+        macro_assembler->Bind(&success);
+
         break;
       }
       default:
         UNREACHABLE();
         return false;
     }
   }
+  compiler->AddWork(on_failure_);
   macro_assembler->AdvanceCurrentPosition(cp_offset);
   return on_success()->GoTo(compiler);
 }
 
 
 bool ChoiceNode::Emit(RegExpCompiler* compiler) {
   int choice_count = alternatives_->length();
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   Bind(macro_assembler);
   // For now we just call all choices one after the other.  The idea ultimately
@@ skipping 24 matching lines @@
   GuardedAlternative alternative = (*alternatives_)[i];
   ZoneList<Guard*>* guards = alternative.guards();
   if (guards != NULL) {
     int guard_count = guards->length();
     for (int j = 0; j < guard_count; j++) {
       GenerateGuard(macro_assembler, (*guards)[j], on_failure_->label());
     }
   }
   if (!on_failure_->IsBacktrack()) {
     macro_assembler->PushBacktrack(on_failure_->label());
+    compiler->AddWork(on_failure_);
   }
   if (!alternative.node()->GoTo(compiler)) {
     return false;
   }
-  compiler->AddWork(on_failure_);
   return true;
 }
 
 
 bool ActionNode::Emit(RegExpCompiler* compiler) {
   RegExpMacroAssembler* macro = compiler->macro_assembler();
   Bind(macro);
   switch (type_) {
     case STORE_REGISTER:
       macro->SetRegister(data_.u_store_register.reg,
@@ skipping 21 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:
-      // TODO(erikcorry): Implement this.
-      return false;
+      macro->SetCurrentPositionFromRegister(
+          data_.u_position_register.reg);
+      break;
     case BEGIN_SUBMATCH:
-      // TODO(erikcorry): Implement this.
-      return false;
+      macro->WriteStackPointerToRegister(
+          data_.u_submatch_stack_pointer_register.reg);
+      break;
     case ESCAPE_SUBMATCH:
-      // TODO(erikcorry): Implement this.
-      return false;
-    case END_SUBMATCH:
-      // TODO(erikcorry): Implement this.
-      return false;
+      macro->SetStackPointerFromRegister(
+          data_.u_submatch_stack_pointer_register.reg);
+      break;
     default:
       UNREACHABLE();
       return false;
   }
   return on_success()->GoTo(compiler);
 }
 
 
 // -------------------------------------------------------------------
 // Dot/dotty output
@@ skipping 183 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");
       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:
   explicit DispatchTableDumper(StringStream* stream) : stream_(stream) { }
@@ skipping 187 matching lines @@
 RegExpNode* RegExpEmpty::ToNode(RegExpCompiler* compiler,
                                 RegExpNode* on_success,
                                 RegExpNode* on_failure) {
   return on_success;
 }
 
 
 RegExpNode* RegExpLookahead::ToNode(RegExpCompiler* compiler,
                                     RegExpNode* on_success,
                                     RegExpNode* on_failure) {
+  int stack_pointer_register = compiler->AllocateRegister();

[Lasse Reichstein, 2008/11/20 10:32:11]

You never free a register again. 
Would it be possible to free registers, and perhaps reuse them?

[Erik Corry, 2008/11/20 11:37:34]

We could free them if we checked for nested expressions.  I don't think it's
worth worrying about at this stage.

+  int position_register = compiler->AllocateRegister();
   if (is_positive()) {
-    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, body()->ToNode(compiler,
-            ActionNode::RestorePosition(position_register,
-                ActionNode::EscapeSubmatch(on_success)),
-            ActionNode::EndSubmatch(on_failure))));
+    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)));
   } 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::EndSubmatch(on_success));
-    RegExpNode* body_node = body()->ToNode(compiler,
-        ActionNode::EscapeSubmatch(on_failure),
+        new ChoiceNode(1, ActionNode::RestorePosition(position_register,
+                                                      on_success));
+    RegExpNode* body_node = body()->ToNode(
+        compiler,
+        ActionNode::EscapeSubmatch(stack_pointer_register, on_failure),
         compiler->backtrack());
     GuardedAlternative body_alt(body_node);
     try_node->AddAlternative(body_alt);
-    return ActionNode::BeginSubmatch(try_node);
+    return ActionNode::BeginSubmatch(stack_pointer_register,
+                                     ActionNode::SavePosition(
+                                         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 539 matching lines @@
 }
 
 RegExpMacroAssembler::RegExpMacroAssembler() {
 }
 
 RegExpMacroAssembler::~RegExpMacroAssembler() {
 }
 
 
 }}  // namespace v8::internal