Experimental support for RegExp lookbehind.

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

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #if V8_TARGET_ARCH_MIPS64
 
 #include "src/regexp/mips64/regexp-macro-assembler-mips64.h"
 
 #include "src/code-stubs.h"
 #include "src/log.h"
@@ skipping 43 matching lines @@
  *  - fp[36]  return address      (lr).
  *  - fp[32]  old frame pointer   (r11).
  *  - fp[0..31]  backup of registers s0..s7.
  *  --- frame pointer ----
  *  - fp[-4]  end of input       (address of end of string).
  *  - fp[-8]  start of input     (address of first character in string).
  *  - fp[-12] start index        (character index of start).
  *  - fp[-16] void* input_string (location of a handle containing the string).
  *  - fp[-20] success counter    (only for global regexps to count matches).
  *  - fp[-24] Offset of location before start of input (effectively character
- *            position -1). Used to initialize capture registers to a
+ *            string start - 1). Used to initialize capture registers to a
  *            non-position.
  *  - fp[-28] At start (if 1, we are starting at the start of the
  *    string, otherwise 0)
  *  - fp[-32] register 0         (Only positions must be stored in the first
  *  -         register 1          num_saved_registers_ registers)
  *  -         ...
  *  -         register num_registers-1
  *  --- sp ---
  *
  *
  * The N64 stack will have the following structure:
  *
  *  - fp[88]  Isolate* isolate   (address of the current isolate)               kIsolate
  *  - fp[80]  secondary link/return address used by exit frame on native call.  kSecondaryReturnAddress
                                                                                 kStackFrameHeader
  *  --- sp when called ---
  *  - fp[72]  ra                 Return from RegExp code (ra).                  kReturnAddress
  *  - fp[64]  s9, old-fp         Old fp, callee saved(s9).
  *  - fp[0..63]  s0..s7          Callee-saved registers s0..s7.
  *  --- frame pointer ----
  *  - fp[-8]  direct_call        (1 = direct call from JS, 0 = from runtime)    kDirectCall
  *  - fp[-16] stack_base         (Top of backtracking stack).                   kStackHighEnd
  *  - fp[-24] capture array size (may fit multiple sets of matches)             kNumOutputRegisters
  *  - fp[-32] int* capture_array (int[num_saved_registers_], for output).       kRegisterOutput
  *  - fp[-40] end of input       (address of end of string).                    kInputEnd
  *  - fp[-48] start of input     (address of first character in string).        kInputStart
  *  - fp[-56] start index        (character index of start).                    kStartIndex
  *  - fp[-64] void* input_string (location of a handle containing the string).  kInputString
  *  - fp[-72] success counter    (only for global regexps to count matches).    kSuccessfulCaptures
- *  - fp[-80] Offset of location before start of input (effectively character   kInputStartMinusOne
+ *  - fp[-80] Offset of location before start of input (effectively character   kStringStartMinusOne
  *            position -1). Used to initialize capture registers to a
  *            non-position.
  *  --------- The following output registers are 32-bit values. ---------
  *  - fp[-88] register 0         (Only positions must be stored in the first    kRegisterZero
  *  -         register 1          num_saved_registers_ registers)
  *  -         ...
  *  -         register num_registers-1
  *  --- sp ---
  *
  * The first num_saved_registers_ registers are initialized to point to
@@ skipping 105 matching lines @@
   BranchOrBacktrack(on_equal, eq, current_character(), Operand(c));
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckCharacterGT(uc16 limit, Label* on_greater) {
   BranchOrBacktrack(on_greater, gt, current_character(), Operand(limit));
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckAtStart(Label* on_at_start) {
-  Label not_at_start;
-  // Did we start the match at the start of the string at all?
-  __ ld(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?
-  __ ld(a1, MemOperand(frame_pointer(), kInputStart));
-  __ Daddu(a0, end_of_input_address(), Operand(current_input_offset()));
+  __ ld(a1, MemOperand(frame_pointer(), kStringStartMinusOne));
+  __ Daddu(a0, current_input_offset(), Operand(-char_size()));
   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?
-  __ ld(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?
-  __ ld(a1, MemOperand(frame_pointer(), kInputStart));
-  __ Daddu(a0, end_of_input_address(), Operand(current_input_offset()));
+void RegExpMacroAssemblerMIPS::CheckNotAtStart(int cp_offset,
+                                               Label* on_not_at_start) {
+  __ ld(a1, MemOperand(frame_pointer(), kStringStartMinusOne));
+  __ Daddu(a0, current_input_offset(),
+           Operand(-char_size() + cp_offset * char_size()));
   BranchOrBacktrack(on_not_at_start, ne, a0, Operand(a1));
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckCharacterLT(uc16 limit, Label* on_less) {
   BranchOrBacktrack(on_less, lt, current_character(), Operand(limit));
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckGreedyLoop(Label* on_equal) {
   Label backtrack_non_equal;
   __ lw(a0, MemOperand(backtrack_stackpointer(), 0));
   __ Branch(&backtrack_non_equal, ne, current_input_offset(), Operand(a0));
   __ Daddu(backtrack_stackpointer(),
           backtrack_stackpointer(),
           Operand(kIntSize));
   __ bind(&backtrack_non_equal);
   BranchOrBacktrack(on_equal, eq, current_input_offset(), Operand(a0));
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckNotBackReferenceIgnoreCase(
-    int start_reg,
-    Label* on_no_match) {
+    int start_reg, bool read_backward, Label* on_no_match) {
   Label fallthrough;
   __ ld(a0, register_location(start_reg));  // Index of start of capture.
   __ ld(a1, register_location(start_reg + 1));  // Index of end of capture.
   __ Dsubu(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));
 
-  __ Daddu(t1, a1, current_input_offset());
-  // Check that there are enough characters left in the input.
-  BranchOrBacktrack(on_no_match, gt, t1, Operand(zero_reg));
+  if (read_backward) {
+    __ ld(t1, MemOperand(frame_pointer(), kStringStartMinusOne));
+    __ Dsubu(a2, current_input_offset(), a1);
+    BranchOrBacktrack(on_no_match, le, a2, Operand(t1));
+  } else {
+    __ Daddu(t1, a1, current_input_offset());
+    // Check that there are enough characters left in the input.
+    BranchOrBacktrack(on_no_match, gt, t1, Operand(zero_reg));
+  }
 
   if (mode_ == LATIN1) {
     Label success;
     Label fail;
     Label loop_check;
 
     // a0 - offset of start of capture.
     // a1 - length of capture.
     __ Daddu(a0, a0, Operand(end_of_input_address()));
     __ Daddu(a2, end_of_input_address(), Operand(current_input_offset()));
+    if (read_backward) {
+      __ Dsubu(a2, a2, Operand(a1));
+    }
     __ Daddu(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);
     __ lbu(a3, MemOperand(a0, 0));
     __ daddiu(a0, a0, char_size());
@@ skipping 18 matching lines @@
     __ bind(&loop_check);
     __ Branch(&loop, lt, a0, Operand(a1));
     __ jmp(&success);
 
     __ bind(&fail);
     GoTo(on_no_match);
 
     __ bind(&success);
     // Compute new value of character position after the matched part.
     __ Dsubu(current_input_offset(), a2, end_of_input_address());
+    if (read_backward) {
+      __ ld(t1, register_location(start_reg));  // Index of start of capture.
+      __ ld(a2, register_location(start_reg + 1));  // Index of end of capture.
+      __ Daddu(current_input_offset(), current_input_offset(), Operand(t1));
+      __ Dsubu(current_input_offset(), current_input_offset(), Operand(a2));
+    }
   } else {
     DCHECK(mode_ == UC16);
     // Put regexp engine registers on stack.
     RegList regexp_registers_to_retain = current_input_offset().bit() |
         current_character().bit() | backtrack_stackpointer().bit();
     __ MultiPush(regexp_registers_to_retain);
 
     int argument_count = 4;
     __ PrepareCallCFunction(argument_count, a2);
 
     // a0 - offset of start of capture.
     // a1 - length of capture.
 
     // Put arguments into arguments registers.
     // Parameters are
     //   a0: Address byte_offset1 - Address captured substring's start.
     //   a1: Address byte_offset2 - Address of current character position.
     //   a2: size_t byte_length - length of capture in bytes(!).
     //   a3: Isolate* isolate.
 
     // Address of start of capture.
     __ Daddu(a0, a0, Operand(end_of_input_address()));
     // Length of capture.
     __ mov(a2, a1);
     // Save length in callee-save register for use on return.
     __ mov(s3, a1);
     // Address of current input position.
     __ Daddu(a1, current_input_offset(), Operand(end_of_input_address()));
+    if (read_backward) {
+      __ Dsubu(a1, a1, Operand(s3));
+    }
     // Isolate.
     __ li(a3, Operand(ExternalReference::isolate_address(masm_->isolate())));
 
     {
       AllowExternalCallThatCantCauseGC scope(masm_);
       ExternalReference function =
           ExternalReference::re_case_insensitive_compare_uc16(masm_->isolate());
       __ CallCFunction(function, argument_count);
     }
 
     // Restore regexp engine registers.
     __ MultiPop(regexp_registers_to_retain);
     __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
     __ ld(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
 
     // 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.
-    __ Daddu(current_input_offset(), current_input_offset(), Operand(s3));
+    if (read_backward) {
+      __ Dsubu(current_input_offset(), current_input_offset(), Operand(s3));
+    } else {
+      __ Daddu(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;
 
   // Find length of back-referenced capture.
   __ ld(a0, register_location(start_reg));
   __ ld(a1, register_location(start_reg + 1));
   __ Dsubu(a1, a1, a0);  // Length to check.
-  // Succeed on empty capture (including no capture).
-  __ 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));
 
-  __ Daddu(t1, a1, current_input_offset());
-  // Check that there are enough characters left in the input.
-  BranchOrBacktrack(on_no_match, gt, t1, Operand(zero_reg));
+  if (read_backward) {
+    __ ld(t1, MemOperand(frame_pointer(), kStringStartMinusOne));
+    __ Dsubu(a2, current_input_offset(), a1);
+    BranchOrBacktrack(on_no_match, le, a2, Operand(t1));
+  } else {
+    __ Daddu(t1, a1, current_input_offset());
+    // Check that there are enough characters left in the input.
+    BranchOrBacktrack(on_no_match, gt, t1, Operand(zero_reg));
+  }
 
   // Compute pointers to match string and capture string.
   __ Daddu(a0, a0, Operand(end_of_input_address()));
   __ Daddu(a2, end_of_input_address(), Operand(current_input_offset()));
+  if (read_backward) {
+    __ Dsubu(a2, a2, Operand(a1));
+  }
   __ Daddu(a1, a1, Operand(a0));
 
   Label loop;
   __ bind(&loop);
   if (mode_ == LATIN1) {
     __ lbu(a3, MemOperand(a0, 0));
     __ daddiu(a0, a0, char_size());
     __ lbu(a4, MemOperand(a2, 0));
     __ daddiu(a2, a2, char_size());
   } else {
     DCHECK(mode_ == UC16);
     __ lhu(a3, MemOperand(a0, 0));
     __ daddiu(a0, a0, char_size());
     __ lhu(a4, MemOperand(a2, 0));
     __ daddiu(a2, a2, char_size());
   }
   BranchOrBacktrack(on_no_match, ne, a3, Operand(a4));
   __ Branch(&loop, lt, a0, Operand(a1));
 
   // Move current character position to position after match.
   __ Dsubu(current_input_offset(), a2, end_of_input_address());
+  if (read_backward) {
+    __ ld(t1, register_location(start_reg));      // Index of start of capture.
+    __ ld(a2, register_location(start_reg + 1));  // Index of end of capture.
+    __ Daddu(current_input_offset(), current_input_offset(), Operand(t1));
+    __ Dsubu(current_input_offset(), current_input_offset(), Operand(a2));
+  }
   __ bind(&fallthrough);
 }
 
 
 void RegExpMacroAssemblerMIPS::CheckNotCharacter(uint32_t c,
                                                  Label* on_not_equal) {
   BranchOrBacktrack(on_not_equal, ne, current_character(), Operand(c));
 }
 
 
@@ skipping 209 matching lines @@
       argument_registers |= a4.bit() | a5.bit() | a6.bit() | a7.bit();
     }
 
     __ MultiPush(argument_registers | registers_to_retain | ra.bit());
     // Set frame pointer in space for it if this is not a direct call
     // from generated code.
     // TODO(plind): this 8 is the # of argument regs, should have definition.
     __ Daddu(frame_pointer(), sp, Operand(8 * kPointerSize));
     __ mov(a0, zero_reg);
     __ push(a0);  // Make room for success counter and initialize it to 0.
-    __ push(a0);  // Make room for "position - 1" constant (value irrelevant).
+    __ push(a0);  // Make room for "string start - 1" constant.
 
     // Check if we have space on the stack for registers.
     Label stack_limit_hit;
     Label stack_ok;
 
     ExternalReference stack_limit =
         ExternalReference::address_of_stack_limit(masm_->isolate());
     __ li(a0, Operand(stack_limit));
     __ ld(a0, MemOperand(a0));
     __ Dsubu(a0, sp, a0);
@@ skipping 22 matching lines @@
     // Find negative length (offset of start relative to end).
     __ Dsubu(current_input_offset(), a0, end_of_input_address());
     // Set a0 to address of char before start of the input string
     // (effectively string position -1).
     __ ld(a1, MemOperand(frame_pointer(), kStartIndex));
     __ Dsubu(a0, current_input_offset(), Operand(char_size()));
     __ dsll(t1, a1, (mode_ == UC16) ? 1 : 0);
     __ Dsubu(a0, a0, t1);
     // Store this value in a local variable, for use when clearing
     // position registers.
-    __ sd(a0, MemOperand(frame_pointer(), kInputStartMinusOne));
+    __ sd(a0, MemOperand(frame_pointer(), kStringStartMinusOne));
 
     // Initialize code pointer register
     __ li(code_pointer(), Operand(masm_->CodeObject()), CONSTANT_SIZE);
 
     Label load_char_start_regexp, start_regexp;
     // Load newline if index is at start, previous character otherwise.
     __ Branch(&load_char_start_regexp, ne, a1, Operand(zero_reg));
     __ li(current_character(), Operand('\n'));
     __ jmp(&start_regexp);
 
@@ skipping 89 matching lines @@
         // Check whether we have enough room for another set of capture results.
         __ mov(v0, a0);
         __ Branch(&return_v0, lt, a1, Operand(num_saved_registers_));
 
         __ sd(a1, MemOperand(frame_pointer(), kNumOutputRegisters));
         // Advance the location for output.
         __ Daddu(a2, a2, num_saved_registers_ * kIntSize);
         __ sd(a2, MemOperand(frame_pointer(), kRegisterOutput));
 
         // Prepare a0 to initialize registers with its value in the next run.
-        __ ld(a0, MemOperand(frame_pointer(), kInputStartMinusOne));
+        __ ld(a0, MemOperand(frame_pointer(), kStringStartMinusOne));
 
         if (global_with_zero_length_check()) {
           // Special case for zero-length matches.
           // t3: capture start index
           // Not a zero-length match, restart.
           __ Branch(
               &load_char_start_regexp, ne, current_input_offset(), Operand(t3));
           // Offset from the end is zero if we already reached the end.
           __ Branch(&exit_label_, eq, current_input_offset(),
                     Operand(zero_reg));
@@ skipping 133 matching lines @@
 RegExpMacroAssembler::IrregexpImplementation
     RegExpMacroAssemblerMIPS::Implementation() {
   return kMIPSImplementation;
 }
 
 
 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);
 }
 
 
 void RegExpMacroAssemblerMIPS::PopCurrentPosition() {
   Pop(current_input_offset());
 }
 
 
@@ skipping 87 matching lines @@
     __ sd(current_input_offset(), register_location(reg));
   } else {
     __ Daddu(a0, current_input_offset(), Operand(cp_offset * char_size()));
     __ sd(a0, register_location(reg));
   }
 }
 
 
 void RegExpMacroAssemblerMIPS::ClearRegisters(int reg_from, int reg_to) {
   DCHECK(reg_from <= reg_to);
-  __ ld(a0, MemOperand(frame_pointer(), kInputStartMinusOne));
+  __ ld(a0, MemOperand(frame_pointer(), kStringStartMinusOne));
   for (int reg = reg_from; reg <= reg_to; reg++) {
     __ sd(a0, register_location(reg));
   }
 }
 
 
 void RegExpMacroAssemblerMIPS::WriteStackPointerToRegister(int reg) {
   __ ld(a1, MemOperand(frame_pointer(), kStackHighEnd));
   __ Dsubu(a0, backtrack_stackpointer(), a1);
   __ sd(a0, register_location(reg));
@@ skipping 92 matching lines @@
   if (num_registers_ <= register_index) {
     num_registers_ = register_index + 1;
   }
   return MemOperand(frame_pointer(),
                     kRegisterZero - register_index * kPointerSize);
 }
 
 
 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 {
+    __ ld(a1, MemOperand(frame_pointer(), kStringStartMinusOne));
+    __ Daddu(a0, current_input_offset(), Operand(cp_offset * char_size()));
+    BranchOrBacktrack(on_outside_input, le, a0, Operand(a1));
+  }
 }
 
 
 void RegExpMacroAssemblerMIPS::BranchOrBacktrack(Label* to,
                                                  Condition condition,
                                                  Register rs,
                                                  const Operand& rt) {
   if (condition == al) {  // Unconditional.
     if (to == NULL) {
       Backtrack();
@@ skipping 89 matching lines @@
 }
 
 #undef __
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_TARGET_ARCH_MIPS64