Experimental support for RegExp lookbehind.

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

Index: src/regexp/mips/regexp-macro-assembler-mips.cc
diff --git a/src/regexp/mips/regexp-macro-assembler-mips.cc b/src/regexp/mips/regexp-macro-assembler-mips.cc
index 77f09917c06026535608c0cae952f2546ef4579f..d2ae650df26bc0ff97d504cc7926b11de3d9f15a 100644
--- a/src/regexp/mips/regexp-macro-assembler-mips.cc
+++ b/src/regexp/mips/regexp-macro-assembler-mips.cc
@@ -181,26 +181,25 @@ void RegExpMacroAssemblerMIPS::CheckCharacterGT(uc16 limit, Label* on_greater) {
 
 
 void RegExpMacroAssemblerMIPS::CheckAtStart(Label* on_at_start) {
-  Label not_at_start;
-  // Did we start the match at the start of the string at all?
-  __ lw(a0, MemOperand(frame_pointer(), kStartIndex));
-  BranchOrBacktrack(&not_at_start, ne, a0, Operand(zero_reg));
-
-  // If we did, are we still at the start of the input?
-  __ lw(a1, MemOperand(frame_pointer(), kInputStart));
   __ Addu(a0, end_of_input_address(), Operand(current_input_offset()));
+  __ lw(a1, MemOperand(frame_pointer(), kStartIndex));
+  for (int i = 0; i < char_size(); i++) {
+    __ Addu(a0, a0, Operand(a1));
+  }
+  __ lw(a1, MemOperand(frame_pointer(), kInputStart));
   BranchOrBacktrack(on_at_start, eq, a0, Operand(a1));
-  __ bind(&not_at_start);
 }
 
 
-void RegExpMacroAssemblerMIPS::CheckNotAtStart(Label* on_not_at_start) {
-  // Did we start the match at the start of the string at all?
-  __ lw(a0, MemOperand(frame_pointer(), kStartIndex));
-  BranchOrBacktrack(on_not_at_start, ne, a0, Operand(zero_reg));
-  // If we did, are we still at the start of the input?
-  __ lw(a1, MemOperand(frame_pointer(), kInputStart));
+void RegExpMacroAssemblerMIPS::CheckNotAtStart(int cp_offset,
+                                               Label* on_not_at_start) {
   __ Addu(a0, end_of_input_address(), Operand(current_input_offset()));
+  __ Addu(a0, a0, Operand(cp_offset * char_size()));
+  __ lw(a1, MemOperand(frame_pointer(), kStartIndex));
+  for (int i = 0; i < char_size(); i++) {
+    __ Addu(a0, a0, Operand(a1));
+  }
+  __ lw(a1, MemOperand(frame_pointer(), kInputStart));
   BranchOrBacktrack(on_not_at_start, ne, a0, Operand(a1));
 }
 
@@ -223,20 +222,30 @@ void RegExpMacroAssemblerMIPS::CheckGreedyLoop(Label* on_equal) {
 
 
 void RegExpMacroAssemblerMIPS::CheckNotBackReferenceIgnoreCase(
-    int start_reg,
-    Label* on_no_match) {
+    int start_reg, bool read_backward, Label* on_no_match) {
   Label fallthrough;
   __ lw(a0, register_location(start_reg));  // Index of start of capture.
   __ lw(a1, register_location(start_reg + 1));  // Index of end of capture.
   __ Subu(a1, a1, a0);  // Length of capture.
 
-  // If length is zero, either the capture is empty or it is not participating.
-  // In either case succeed immediately.
-  __ Branch(&fallthrough, eq, a1, Operand(zero_reg));
+  // 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.
+  __ Branch(&fallthrough, le, a1, Operand(zero_reg));
 
-  __ Addu(t5, a1, current_input_offset());
-  // Check that there are enough characters left in the input.
-  BranchOrBacktrack(on_no_match, gt, t5, Operand(zero_reg));
+  if (read_backward) {
+    __ Addu(t5, end_of_input_address(), Operand(current_input_offset()));
+    __ lw(t0, MemOperand(frame_pointer(), kStartIndex));
+    for (int i = 0; i < char_size(); i++) {
+      __ Addu(t5, t5, Operand(t0));
+    }
+    __ lw(t0, MemOperand(frame_pointer(), kInputStart));
+    BranchOrBacktrack(on_no_match, lt, t5, Operand(t0));
+  } else {
+    __ Addu(t5, a1, current_input_offset());
+    // Check that there are enough characters left in the input.
+    BranchOrBacktrack(on_no_match, gt, t5, Operand(zero_reg));
+  }
 
   if (mode_ == LATIN1) {
     Label success;
@@ -247,6 +256,9 @@ void RegExpMacroAssemblerMIPS::CheckNotBackReferenceIgnoreCase(
     // a1 - length of capture.
     __ Addu(a0, a0, Operand(end_of_input_address()));
     __ Addu(a2, end_of_input_address(), Operand(current_input_offset()));
+    if (read_backward) {
+      __ Subu(a2, a2, Operand(a1));
+    }
     __ Addu(a1, a0, Operand(a1));
 
     // a0 - Address of start of capture.
@@ -285,6 +297,12 @@ void RegExpMacroAssemblerMIPS::CheckNotBackReferenceIgnoreCase(
     __ bind(&success);
     // Compute new value of character position after the matched part.
     __ Subu(current_input_offset(), a2, end_of_input_address());
+    if (read_backward) {
+      __ lw(t0, register_location(start_reg));  // Index of start of capture.
+      __ lw(t5, register_location(start_reg + 1));  // Index of end of capture.
+      __ Addu(current_input_offset(), current_input_offset(), Operand(t0));
+      __ Subu(current_input_offset(), current_input_offset(), Operand(t5));
+    }
   } else {
     DCHECK(mode_ == UC16);
     // Put regexp engine registers on stack.
@@ -313,6 +331,9 @@ void RegExpMacroAssemblerMIPS::CheckNotBackReferenceIgnoreCase(
     __ mov(s3, a1);
     // Address of current input position.
     __ Addu(a1, current_input_offset(), Operand(end_of_input_address()));
+    if (read_backward) {
+      __ Subu(a1, a1, Operand(s3));
+    }
     // Isolate.
     __ li(a3, Operand(ExternalReference::isolate_address(masm_->isolate())));
 
@@ -330,17 +351,21 @@ void RegExpMacroAssemblerMIPS::CheckNotBackReferenceIgnoreCase(
 
     // Check if function returned non-zero for success or zero for failure.
     BranchOrBacktrack(on_no_match, eq, v0, Operand(zero_reg));
-    // On success, increment position by length of capture.
-    __ Addu(current_input_offset(), current_input_offset(), Operand(s3));
+    // On success, advance position by length of capture.
+    if (read_backward) {
+      __ Subu(current_input_offset(), current_input_offset(), Operand(s3));
+    } else {
+      __ Addu(current_input_offset(), current_input_offset(), Operand(s3));
+    }
   }
 
   __ bind(&fallthrough);
 }
 
 
-void RegExpMacroAssemblerMIPS::CheckNotBackReference(
-    int start_reg,
-    Label* on_no_match) {
+void RegExpMacroAssemblerMIPS::CheckNotBackReference(int start_reg,
+                                                     bool read_backward,
+                                                     Label* on_no_match) {
   Label fallthrough;
   Label success;
 
@@ -348,17 +373,38 @@ void RegExpMacroAssemblerMIPS::CheckNotBackReference(
   __ lw(a0, register_location(start_reg));
   __ lw(a1, register_location(start_reg + 1));
   __ Subu(a1, a1, a0);  // Length to check.
-  // Succeed on empty capture (including no capture).
-  __ Branch(&fallthrough, eq, a1, Operand(zero_reg));
-
-  __ Addu(t5, a1, current_input_offset());
-  // Check that there are enough characters left in the input.
-  BranchOrBacktrack(on_no_match, gt, t5, Operand(zero_reg));
+  // 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.
+  __ Branch(&fallthrough, le, a1, Operand(zero_reg));
+
+  if (read_backward) {
+    __ Addu(t5, end_of_input_address(), Operand(current_input_offset()));
+    __ lw(t0, MemOperand(frame_pointer(), kStartIndex));
+    for (int i = 0; i < char_size(); i++) {
+      __ Addu(t5, t5, Operand(t0));
+    }
+    __ lw(t0, MemOperand(frame_pointer(), kInputStart));
+    BranchOrBacktrack(on_no_match, lt, t5, Operand(t0));
+  } else {
+    __ Addu(t5, a1, current_input_offset());
+    // Check that there are enough characters left in the input.
+    BranchOrBacktrack(on_no_match, gt, t5, Operand(zero_reg));
+  }
 
-  // Compute pointers to match string and capture string.
+  // a0 - offset of start of capture.
+  // a1 - length of capture.
   __ Addu(a0, a0, Operand(end_of_input_address()));
   __ Addu(a2, end_of_input_address(), Operand(current_input_offset()));
-  __ Addu(a1, a1, Operand(a0));
+  if (read_backward) {
+    __ Subu(a2, a2, Operand(a1));
+  }
+  __ Addu(a1, a0, Operand(a1));
+
+  // a0 - Address of start of capture.
+  // a1 - Address of end of capture.
+  // a2 - Address of current input position.
+
 
   Label loop;
   __ bind(&loop);
@@ -379,6 +425,12 @@ void RegExpMacroAssemblerMIPS::CheckNotBackReference(
 
   // Move current character position to position after match.
   __ Subu(current_input_offset(), a2, end_of_input_address());
+  if (read_backward) {
+    __ lw(t0, register_location(start_reg));      // Index of start of capture.
+    __ lw(t5, register_location(start_reg + 1));  // Index of end of capture.
+    __ Addu(current_input_offset(), current_input_offset(), Operand(t0));
+    __ Subu(current_input_offset(), current_input_offset(), Operand(t5));
+  }
   __ bind(&fallthrough);
 }
 
@@ -905,10 +957,13 @@ void RegExpMacroAssemblerMIPS::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);
 }
@@ -1129,10 +1184,19 @@ MemOperand RegExpMacroAssemblerMIPS::register_location(int register_index) {
 
 void RegExpMacroAssemblerMIPS::CheckPosition(int cp_offset,
                                              Label* on_outside_input) {
-  BranchOrBacktrack(on_outside_input,
-                    ge,
-                    current_input_offset(),
-                    Operand(-cp_offset * char_size()));
+  if (cp_offset >= 0) {
+    BranchOrBacktrack(on_outside_input, ge, current_input_offset(),
+                      Operand(-cp_offset * char_size()));
+  } else {
+    __ Addu(a0, end_of_input_address(), Operand(current_input_offset()));
+    __ Addu(a0, a0, Operand(cp_offset * char_size()));
+    __ lw(a1, MemOperand(frame_pointer(), kStartIndex));
+    for (int i = 0; i < char_size(); i++) {
+      __ Addu(a0, a0, Operand(a1));
+    }
+    __ lw(a1, MemOperand(frame_pointer(), kInputStart));
+    BranchOrBacktrack(on_outside_input, lt, a0, Operand(a1));
+  }
 }