Experimental support for RegExp lookbehind.

src/regexp/ia32/regexp-macro-assembler-ia32.cc

Index: src/regexp/ia32/regexp-macro-assembler-ia32.cc
diff --git a/src/regexp/ia32/regexp-macro-assembler-ia32.cc b/src/regexp/ia32/regexp-macro-assembler-ia32.cc
index 9e50a105747db0c5e31114ce0d7e62d440129771..d189b90932357693fc20dfdd77aa4bed33d7fd1b 100644
--- a/src/regexp/ia32/regexp-macro-assembler-ia32.cc
+++ b/src/regexp/ia32/regexp-macro-assembler-ia32.cc
@@ -156,24 +156,21 @@ void RegExpMacroAssemblerIA32::CheckCharacterGT(uc16 limit, Label* on_greater) {
 
 
 void RegExpMacroAssemblerIA32::CheckAtStart(Label* on_at_start) {
-  Label not_at_start;
-  // Did we start the match at the start of the string at all?
-  __ cmp(Operand(ebp, kStartIndex), Immediate(0));
-  BranchOrBacktrack(not_equal, &not_at_start);
-  // If we did, are we still at the start of the input?
   __ lea(eax, Operand(esi, edi, times_1, 0));
+  for (int i = 0; i < char_size(); i++) {
+    __ add(eax, Operand(ebp, kStartIndex));
+  }
   __ cmp(eax, Operand(ebp, kInputStart));
   BranchOrBacktrack(equal, on_at_start);
-  __ bind(&not_at_start);
 }
 
 
-void RegExpMacroAssemblerIA32::CheckNotAtStart(Label* on_not_at_start) {
-  // Did we start the match at the start of the string at all?
-  __ cmp(Operand(ebp, kStartIndex), Immediate(0));
-  BranchOrBacktrack(not_equal, on_not_at_start);
-  // If we did, are we still at the start of the input?
-  __ lea(eax, Operand(esi, edi, times_1, 0));
+void RegExpMacroAssemblerIA32::CheckNotAtStart(int cp_offset,
+                                               Label* on_not_at_start) {
+  __ lea(eax, Operand(esi, edi, times_1, cp_offset * char_size()));
+  for (int i = 0; i < char_size(); i++) {
+    __ add(eax, Operand(ebp, kStartIndex));
+  }
   __ cmp(eax, Operand(ebp, kInputStart));
   BranchOrBacktrack(not_equal, on_not_at_start);
 }
@@ -197,25 +194,32 @@ void RegExpMacroAssemblerIA32::CheckGreedyLoop(Label* on_equal) {
 
 void RegExpMacroAssemblerIA32::CheckNotBackReferenceIgnoreCase(
     int start_reg,
+    bool read_backward,
     Label* on_no_match) {
   Label fallthrough;
   __ mov(edx, register_location(start_reg));  // Index of start of capture
   __ mov(ebx, register_location(start_reg + 1));  // Index of end of capture
   __ sub(ebx, edx);  // Length of capture.
 
-  // The length of a capture should not be negative. This can only happen
-  // if the end of the capture is unrecorded, or at a point earlier than
-  // the start of the capture.
-  BranchOrBacktrack(less, on_no_match);
-
-  // If length is zero, either the capture is empty or it is completely
-  // uncaptured. In either case succeed immediately.
-  __ j(equal, &fallthrough);
+  // The length of the capture can only be negative if the end of the
+  // capture is not yet recorded. If the length is zero, the capture is
+  // either empty or uncaptured. In either of those cases, succeed.
+  __ j(less_equal, &fallthrough);
 
   // Check that there are sufficient characters left in the input.
-  __ mov(eax, edi);
-  __ add(eax, ebx);
-  BranchOrBacktrack(greater, on_no_match);
+  if (read_backward) {
+    __ lea(eax, Operand(esi, edi, times_1, 0));
+    __ sub(eax, ebx);
+    for (int i = 0; i < char_size(); i++) {
+      __ add(eax, Operand(ebp, kStartIndex));
+    }
+    __ cmp(eax, Operand(ebp, kInputStart));
+    BranchOrBacktrack(less, on_no_match);
+  } else {
+    __ mov(eax, edi);
+    __ add(eax, ebx);
+    BranchOrBacktrack(greater, on_no_match);
+  }
 
   if (mode_ == LATIN1) {
     Label success;
@@ -228,6 +232,9 @@ void RegExpMacroAssemblerIA32::CheckNotBackReferenceIgnoreCase(
 
     __ add(edx, esi);  // Start of capture
     __ add(edi, esi);  // Start of text to match against capture.
+    if (read_backward) {
+      __ sub(edi, ebx);  // Offset by length when matching backwards.
+    }
     __ add(ebx, edi);  // End of text to match against capture.
 
     Label loop;
@@ -278,6 +285,11 @@ void RegExpMacroAssemblerIA32::CheckNotBackReferenceIgnoreCase(
     __ add(esp, Immediate(kPointerSize));
     // Compute new value of character position after the matched part.
     __ sub(edi, esi);
+    if (read_backward) {
+      // Subtract match length if we matched backward.
+      __ add(edi, register_location(start_reg));
+      __ sub(edi, register_location(start_reg + 1));
+    }
   } else {
     DCHECK(mode_ == UC16);
     // Save registers before calling C function.
@@ -304,6 +316,9 @@ void RegExpMacroAssemblerIA32::CheckNotBackReferenceIgnoreCase(
     // Found by adding negative string-end offset of current position (edi)
     // to end of string.
     __ add(edi, esi);
+    if (read_backward) {
+      __ sub(edi, ebx);  // Offset by length when matching backwards.
+    }
     __ mov(Operand(esp, 1 * kPointerSize), edi);
     // Set byte_offset1.
     // Start of capture, where edx already holds string-end negative offset.
@@ -325,8 +340,12 @@ void RegExpMacroAssemblerIA32::CheckNotBackReferenceIgnoreCase(
     // Check if function returned non-zero for success or zero for failure.
     __ or_(eax, eax);
     BranchOrBacktrack(zero, on_no_match);
-    // On success, increment position by length of capture.
-    __ add(edi, ebx);
+    // On success, advance position by length of capture.
+    if (read_backward) {
+      __ sub(edi, ebx);
+    } else {
+      __ add(edi, ebx);
+    }
   }
   __ bind(&fallthrough);
 }
@@ -334,6 +353,7 @@ void RegExpMacroAssemblerIA32::CheckNotBackReferenceIgnoreCase(
 
 void RegExpMacroAssemblerIA32::CheckNotBackReference(
     int start_reg,
+    bool read_backward,
     Label* on_no_match) {
   Label fallthrough;
   Label success;
@@ -343,22 +363,35 @@ void RegExpMacroAssemblerIA32::CheckNotBackReference(
   __ mov(edx, register_location(start_reg));
   __ mov(eax, register_location(start_reg + 1));
   __ sub(eax, edx);  // Length to check.
-  // Fail on partial or illegal capture (start of capture after end of capture).
-  BranchOrBacktrack(less, on_no_match);
-  // Succeed on empty capture (including no capture)
-  __ j(equal, &fallthrough);
+  // The length of the capture can only be negative if the end of the
+  // capture is not yet recorded. If the length is zero, the capture is
+  // either empty or uncaptured. In either of those cases, succeed.
+  __ j(less_equal, &fallthrough);
 
   // Check that there are sufficient characters left in the input.
-  __ mov(ebx, edi);
-  __ add(ebx, eax);
-  BranchOrBacktrack(greater, on_no_match);
+  if (read_backward) {
+    __ lea(ebx, Operand(esi, edi, times_1, 0));
+    __ sub(ebx, eax);
+    for (int i = 0; i < char_size(); i++) {
+      __ add(ebx, Operand(ebp, kStartIndex));
+    }
+    __ cmp(ebx, Operand(ebp, kInputStart));
+    BranchOrBacktrack(less, on_no_match);
+  } else {
+    __ mov(ebx, edi);
+    __ add(ebx, eax);
+    BranchOrBacktrack(greater, on_no_match);
+  }
 
   // Save register to make it available below.
   __ push(backtrack_stackpointer());
 
   // Compute pointers to match string and capture string
-  __ lea(ebx, Operand(esi, edi, times_1, 0));  // Start of match.
   __ add(edx, esi);  // Start of capture.
+  __ lea(ebx, Operand(esi, edi, times_1, 0));  // Start of match.
+  if (read_backward) {
+    __ sub(ebx, eax);  // Offset by length when matching backwards.
+  }
   __ lea(ecx, Operand(eax, ebx, times_1, 0));  // End of match
 
   Label loop;
@@ -389,6 +422,11 @@ void RegExpMacroAssemblerIA32::CheckNotBackReference(
   // Move current character position to position after match.
   __ mov(edi, ecx);
   __ sub(edi, esi);
+  if (read_backward) {
+    // Subtract match length if we matched backward.
+    __ add(edi, register_location(start_reg));
+    __ sub(edi, register_location(start_reg + 1));
+  }
   // Restore backtrack stackpointer.
   __ pop(backtrack_stackpointer());
 
@@ -767,7 +805,7 @@ Handle<HeapObject> RegExpMacroAssemblerIA32::GetCode(Handle<String> source) {
     }
 
     if (global()) {
-    // Restart matching if the regular expression is flagged as global.
+      // Restart matching if the regular expression is flagged as global.
       // Increment success counter.
       __ inc(Operand(ebp, kSuccessfulCaptures));
       // Capture results have been stored, so the number of remaining global
@@ -944,10 +982,13 @@ void RegExpMacroAssemblerIA32::LoadCurrentCharacter(int cp_offset,
                                                     Label* on_end_of_input,
                                                     bool check_bounds,
                                                     int characters) {
-  DCHECK(cp_offset >= -1);      // ^ and \b can look behind one character.
   DCHECK(cp_offset < (1<<30));  // Be sane! (And ensure negation works)
   if (check_bounds) {
-    CheckPosition(cp_offset + characters - 1, on_end_of_input);
+    if (cp_offset >= 0) {
+      CheckPosition(cp_offset + characters - 1, on_end_of_input);
+    } else {
+      CheckPosition(cp_offset, on_end_of_input);
+    }
   }
   LoadCurrentCharacterUnchecked(cp_offset, characters);
 }
@@ -1100,8 +1141,17 @@ Operand RegExpMacroAssemblerIA32::register_location(int register_index) {
 
 void RegExpMacroAssemblerIA32::CheckPosition(int cp_offset,
                                              Label* on_outside_input) {
-  __ cmp(edi, -cp_offset * char_size());
-  BranchOrBacktrack(greater_equal, on_outside_input);
+  if (cp_offset >= 0) {
+    __ cmp(edi, -cp_offset * char_size());
+    BranchOrBacktrack(greater_equal, on_outside_input);
+  } else {
+    __ lea(eax, Operand(esi, edi, times_1, cp_offset * char_size()));
+    for (int i = 0; i < char_size(); i++) {
+      __ add(eax, Operand(ebp, kStartIndex));
+    }
+    __ cmp(eax, Operand(ebp, kInputStart));
+    BranchOrBacktrack(less, on_outside_input);
+  }
 }