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

src/jsregexp.cc

Index: src/jsregexp.cc
===================================================================
--- src/jsregexp.cc	(revision 799)
+++ src/jsregexp.cc	(working copy)
@@ -1012,25 +1012,31 @@
 }
 
 
-ActionNode* ActionNode::RestorePosition(int reg, RegExpNode* on_success) {
-  ActionNode* result = new ActionNode(RESTORE_POSITION, on_success);
+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::BeginSubmatch(RegExpNode* on_success) {
-  return new ActionNode(BEGIN_SUBMATCH, on_success);
+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::EscapeSubmatch(RegExpNode* on_success) {
-  return new ActionNode(ESCAPE_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::EndSubmatch(RegExpNode* on_success) {
-  return new ActionNode(END_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;
 }
 
 
@@ -1078,18 +1084,22 @@
       }
       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;
         }
 
@@ -1098,29 +1108,58 @@
           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:
@@ -1128,6 +1167,7 @@
         return false;
     }
   }
+  compiler->AddWork(on_failure_);
   macro_assembler->AdvanceCurrentPosition(cp_offset);
   return on_success()->GoTo(compiler);
 }
@@ -1172,11 +1212,11 @@
   }
   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;
 }
 
@@ -1218,18 +1258,22 @@
       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;
@@ -1433,6 +1477,10 @@
       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);
@@ -1443,9 +1491,6 @@
     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());
@@ -1653,8 +1698,9 @@
 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]
@@ -1665,11 +1711,17 @@
     // 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
@@ -1681,15 +1733,21 @@
     //         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));
   }
 }