Experimental support for RegExp lookbehind.

src/regexp/x64/regexp-macro-assembler-x64.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_X64
 
 #include "src/regexp/x64/regexp-macro-assembler-x64.h"
 
 #include "src/log.h"
 #include "src/macro-assembler.h"
@@ skipping 46 matching lines @@
  *    - capture array size   (may fit multiple sets of matches)
  *    - int* capture_array   (int[num_saved_registers_], for output).
  *    - end of input         (address of end of string)
  *    - start of input       (address of first character in string)
  *    - start index          (character index of start)
  *    - String* input_string (input string)
  *    - return address
  *    - backup of callee save registers (rbx, possibly rsi and rdi).
  *    - success counter      (only useful for global regexp to count matches)
  *    - Offset of location before start of input (effectively character
- *      position -1).  Used to initialize capture registers to a non-position.
+ *      string start - 1).  Used to initialize capture registers to a
+ *      non-position.
  *    - At start of string (if 1, we are starting at the start of the
  *      string, otherwise 0)
  *    - register 0  rbp[-n]   (Only positions must be stored in the first
  *    - register 1  rbp[-n-8]  num_saved_registers_ registers)
  *    - ...
  *
  * The first num_saved_registers_ registers are initialized to point to
  * "character -1" in the string (i.e., char_size() bytes before the first
  * character of the string).  The remaining registers starts out uninitialized.
  *
@@ skipping 86 matching lines @@
 }
 
 
 void RegExpMacroAssemblerX64::CheckCharacterGT(uc16 limit, Label* on_greater) {
   __ cmpl(current_character(), Immediate(limit));
   BranchOrBacktrack(greater, on_greater);
 }
 
 
 void RegExpMacroAssemblerX64::CheckAtStart(Label* on_at_start) {
-  Label not_at_start;
-  // Did we start the match at the start of the string at all?
-  __ cmpl(Operand(rbp, kStartIndex), Immediate(0));
-  BranchOrBacktrack(not_equal, &not_at_start);
-  // If we did, are we still at the start of the input?
-  __ leap(rax, Operand(rsi, rdi, times_1, 0));
-  __ cmpp(rax, Operand(rbp, kInputStart));
+  __ leap(rax, Operand(rdi, -char_size()));
+  __ cmpp(rax, Operand(rbp, kStringStartMinusOne));
   BranchOrBacktrack(equal, on_at_start);
-  __ bind(&not_at_start);
 }
 
 
-void RegExpMacroAssemblerX64::CheckNotAtStart(Label* on_not_at_start) {
-  // Did we start the match at the start of the string at all?
-  __ cmpl(Operand(rbp, kStartIndex), Immediate(0));
-  BranchOrBacktrack(not_equal, on_not_at_start);
-  // If we did, are we still at the start of the input?
-  __ leap(rax, Operand(rsi, rdi, times_1, 0));
-  __ cmpp(rax, Operand(rbp, kInputStart));
+void RegExpMacroAssemblerX64::CheckNotAtStart(int cp_offset,
+                                              Label* on_not_at_start) {
+  __ leap(rax, Operand(rdi, -char_size() + cp_offset * char_size()));
+  __ cmpp(rax, Operand(rbp, kStringStartMinusOne));
   BranchOrBacktrack(not_equal, on_not_at_start);
 }
 
 
 void RegExpMacroAssemblerX64::CheckCharacterLT(uc16 limit, Label* on_less) {
   __ cmpl(current_character(), Immediate(limit));
   BranchOrBacktrack(less, on_less);
 }
 
 
 void RegExpMacroAssemblerX64::CheckGreedyLoop(Label* on_equal) {
   Label fallthrough;
   __ cmpl(rdi, Operand(backtrack_stackpointer(), 0));
   __ j(not_equal, &fallthrough);
   Drop();
   BranchOrBacktrack(no_condition, on_equal);
   __ bind(&fallthrough);
 }
 
 
 void RegExpMacroAssemblerX64::CheckNotBackReferenceIgnoreCase(
-    int start_reg,
-    Label* on_no_match) {
+    int start_reg, bool read_backward, Label* on_no_match) {
   Label fallthrough;
   ReadPositionFromRegister(rdx, start_reg);  // Offset of start of capture
   ReadPositionFromRegister(rbx, start_reg + 1);  // Offset of end of capture
   __ subp(rbx, rdx);  // Length of capture.
 
   // -----------------------
   // rdx  = Start offset of capture.
   // rbx = Length of capture
 
-  // If length is negative, this code will fail (it's a symptom of a partial or
-  // illegal capture where start of capture after end of capture).
-  // This must not happen (no back-reference can reference a capture that wasn't
-  // closed before in the reg-exp, and we must not generate code that can cause
-  // this condition).
+  // 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);
 
-  // If length is zero, either the capture is empty or it is nonparticipating.
-  // In either case succeed immediately.
-  __ j(equal, &fallthrough);
 
   // -----------------------
   // rdx - Start of capture
   // rbx - length of capture
   // Check that there are sufficient characters left in the input.
-  __ movl(rax, rdi);
-  __ addl(rax, rbx);
-  BranchOrBacktrack(greater, on_no_match);
+  if (read_backward) {
+    __ movp(rax, rdi);
+    __ subp(rax, rbx);
+    __ cmpp(rax, Operand(rbp, kStringStartMinusOne));
+    BranchOrBacktrack(less_equal, on_no_match);
+  } else {
+    __ movl(rax, rdi);
+    __ addl(rax, rbx);
+    BranchOrBacktrack(greater, on_no_match);
+  }
 
   if (mode_ == LATIN1) {
     Label loop_increment;
     if (on_no_match == NULL) {
       on_no_match = &backtrack_label_;
     }
 
     __ leap(r9, Operand(rsi, rdx, times_1, 0));
     __ leap(r11, Operand(rsi, rdi, times_1, 0));
+    if (read_backward) {
+      __ subp(r11, rbx);  // Offset by length when matching backwards.
+    }
     __ addp(rbx, r9);  // End of capture
     // ---------------------
     // r11 - current input character address
     // r9 - current capture character address
     // rbx - end of capture
 
     Label loop;
     __ bind(&loop);
     __ movzxbl(rdx, Operand(r9, 0));
     __ movzxbl(rax, Operand(r11, 0));
@@ skipping 22 matching lines @@
     // Increment pointers into match and capture strings.
     __ addp(r11, Immediate(1));
     __ addp(r9, Immediate(1));
     // Compare to end of capture, and loop if not done.
     __ cmpp(r9, rbx);
     __ j(below, &loop);
 
     // Compute new value of character position after the matched part.
     __ movp(rdi, r11);
     __ subq(rdi, rsi);
+    if (read_backward) {
+      // Subtract match length if we matched backward.
+      __ addq(rdi, register_location(start_reg));
+      __ subq(rdi, register_location(start_reg + 1));
+    }
   } else {
     DCHECK(mode_ == UC16);
     // Save important/volatile registers before calling C function.
 #ifndef _WIN64
     // Caller save on Linux and callee save in Windows.
     __ pushq(rsi);
     __ pushq(rdi);
 #endif
     __ pushq(backtrack_stackpointer());
 
     static const int num_arguments = 4;
     __ PrepareCallCFunction(num_arguments);
 
     // Put arguments into parameter registers. Parameters are
     //   Address byte_offset1 - Address captured substring's start.
     //   Address byte_offset2 - Address of current character position.
     //   size_t byte_length - length of capture in bytes(!)
     //   Isolate* isolate
 #ifdef _WIN64
     // Compute and set byte_offset1 (start of capture).
     __ leap(rcx, Operand(rsi, rdx, times_1, 0));
     // Set byte_offset2.
     __ leap(rdx, Operand(rsi, rdi, times_1, 0));
+    if (read_backward) {
+      __ subq(rdx, rbx);
+    }
     // Set byte_length.
     __ movp(r8, rbx);
     // Isolate.
     __ LoadAddress(r9, ExternalReference::isolate_address(isolate()));
 #else  // AMD64 calling convention
     // Compute byte_offset2 (current position = rsi+rdi).
     __ leap(rax, Operand(rsi, rdi, times_1, 0));
     // Compute and set byte_offset1 (start of capture).
     __ leap(rdi, Operand(rsi, rdx, times_1, 0));
     // Set byte_offset2.
     __ movp(rsi, rax);
+    if (read_backward) {
+      __ subq(rsi, rbx);
+    }
     // Set byte_length.
     __ movp(rdx, rbx);
     // Isolate.
     __ LoadAddress(rcx, ExternalReference::isolate_address(isolate()));
 #endif
 
     { // NOLINT: Can't find a way to open this scope without confusing the
       // linter.
       AllowExternalCallThatCantCauseGC scope(&masm_);
       ExternalReference compare =
           ExternalReference::re_case_insensitive_compare_uc16(isolate());
       __ CallCFunction(compare, num_arguments);
     }
 
     // Restore original values before reacting on result value.
     __ Move(code_object_pointer(), masm_.CodeObject());
     __ popq(backtrack_stackpointer());
 #ifndef _WIN64
     __ popq(rdi);
     __ popq(rsi);
 #endif
 
     // Check if function returned non-zero for success or zero for failure.
     __ testp(rax, rax);
     BranchOrBacktrack(zero, on_no_match);
-    // On success, increment position by length of capture.
+    // On success, advance position by length of capture.
     // Requires that rbx is callee save (true for both Win64 and AMD64 ABIs).
-    __ addq(rdi, rbx);
+    if (read_backward) {
+      __ subq(rdi, rbx);
+    } else {
+      __ addq(rdi, rbx);
+    }
   }
   __ bind(&fallthrough);
 }
 
 
-void RegExpMacroAssemblerX64::CheckNotBackReference(
-    int start_reg,
-    Label* on_no_match) {
+void RegExpMacroAssemblerX64::CheckNotBackReference(int start_reg,
+                                                    bool read_backward,
+                                                    Label* on_no_match) {
   Label fallthrough;
 
   // Find length of back-referenced capture.
   ReadPositionFromRegister(rdx, start_reg);  // Offset of start of capture
   ReadPositionFromRegister(rax, start_reg + 1);  // Offset of end of capture
   __ subp(rax, rdx);  // Length to check.
-
-  // Fail on partial or illegal capture (start of capture after end of capture).
-  // This must not happen (no back-reference can reference a capture that wasn't
-  // closed before in the reg-exp).
-  __ Check(greater_equal, kInvalidCaptureReferenced);
-
-  // Succeed on empty capture (including non-participating 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);
 
   // -----------------------
   // rdx - Start of capture
   // rax - length of capture
-
   // Check that there are sufficient characters left in the input.
-  __ movl(rbx, rdi);
-  __ addl(rbx, rax);
-  BranchOrBacktrack(greater, on_no_match);
+  if (read_backward) {
+    __ movp(rbx, rdi);
+    __ subp(rbx, rax);
+    __ cmpp(rbx, Operand(rbp, kStringStartMinusOne));
+    BranchOrBacktrack(less_equal, on_no_match);
+  } else {
+    __ movl(rbx, rdi);
+    __ addl(rbx, rax);
+    BranchOrBacktrack(greater, on_no_match);
+  }
 
   // Compute pointers to match string and capture string
   __ leap(rbx, Operand(rsi, rdi, times_1, 0));  // Start of match.
+  if (read_backward) {
+    __ subq(rbx, rax);  // Offset by length when matching backwards.
+  }
   __ addp(rdx, rsi);  // Start of capture.
   __ leap(r9, Operand(rdx, rax, times_1, 0));  // End of capture
 
   // -----------------------
   // rbx - current capture character address.
   // rbx - current input character address .
   // r9 - end of input to match (capture length after rbx).
 
   Label loop;
   __ bind(&loop);
@@ skipping 10 matching lines @@
   __ addp(rbx, Immediate(char_size()));
   __ addp(rdx, Immediate(char_size()));
   // Check if we have reached end of match area.
   __ cmpp(rdx, r9);
   __ j(below, &loop);
 
   // Success.
   // Set current character position to position after match.
   __ movp(rdi, rbx);
   __ subq(rdi, rsi);
+  if (read_backward) {
+    // Subtract match length if we matched backward.
+    __ addq(rdi, register_location(start_reg));
+    __ subq(rdi, register_location(start_reg + 1));
+  }
 
   __ bind(&fallthrough);
 }
 
 
 void RegExpMacroAssemblerX64::CheckNotCharacter(uint32_t c,
                                                 Label* on_not_equal) {
   __ cmpl(current_character(), Immediate(c));
   BranchOrBacktrack(not_equal, on_not_equal);
 }
@@ skipping 246 matching lines @@
   __ pushq(rsi);
   __ pushq(rdx);
   __ pushq(rcx);
   __ pushq(r8);
   __ pushq(r9);
 
   __ pushq(rbx);  // Callee-save
 #endif
 
   __ Push(Immediate(0));  // Number of successful matches in a global regexp.
-  __ Push(Immediate(0));  // Make room for "input start - 1" constant.
+  __ Push(Immediate(0));  // 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(isolate());
   __ movp(rcx, rsp);
   __ Move(kScratchRegister, stack_limit);
   __ subp(rcx, Operand(kScratchRegister, 0));
@@ skipping 29 matching lines @@
   // (effectively string position -1).
   __ movp(rbx, Operand(rbp, kStartIndex));
   __ negq(rbx);
   if (mode_ == UC16) {
     __ leap(rax, Operand(rdi, rbx, times_2, -char_size()));
   } else {
     __ leap(rax, Operand(rdi, rbx, times_1, -char_size()));
   }
   // Store this value in a local variable, for use when clearing
   // position registers.
-  __ movp(Operand(rbp, kInputStartMinusOne), rax);
+  __ movp(Operand(rbp, kStringStartMinusOne), rax);
 
 #if V8_OS_WIN
   // Ensure that we have written to each stack page, in order. Skipping a page
   // on Windows can cause segmentation faults. Assuming page size is 4k.
   const int kPageSize = 4096;
   const int kRegistersPerPage = kPageSize / kPointerSize;
   for (int i = num_saved_registers_ + kRegistersPerPage - 1;
       i < num_registers_;
       i += kRegistersPerPage) {
     __ movp(register_location(i), rax);  // One write every page.
@@ skipping 82 matching lines @@
       // Check whether we have enough room for another set of capture results.
       __ cmpp(rcx, Immediate(num_saved_registers_));
       __ j(less, &exit_label_);
 
       __ movp(Operand(rbp, kNumOutputRegisters), rcx);
       // Advance the location for output.
       __ addp(Operand(rbp, kRegisterOutput),
               Immediate(num_saved_registers_ * kIntSize));
 
       // Prepare rax to initialize registers with its value in the next run.
-      __ movp(rax, Operand(rbp, kInputStartMinusOne));
+      __ movp(rax, Operand(rbp, kStringStartMinusOne));
 
       if (global_with_zero_length_check()) {
         // Special case for zero-length matches.
         // rdx: capture start index
         __ cmpp(rdi, rdx);
         // Not a zero-length match, restart.
         __ j(not_equal, &load_char_start_regexp);
         // rdi (offset from the end) is zero if we already reached the end.
         __ testp(rdi, rdi);
         __ j(zero, &exit_label_, Label::kNear);
@@ skipping 162 matching lines @@
 RegExpMacroAssembler::IrregexpImplementation
     RegExpMacroAssemblerX64::Implementation() {
   return kX64Implementation;
 }
 
 
 void RegExpMacroAssemblerX64::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 RegExpMacroAssemblerX64::PopCurrentPosition() {
   Pop(rdi);
 }
 
 
@@ skipping 82 matching lines @@
     __ movp(register_location(reg), rdi);
   } else {
     __ leap(rax, Operand(rdi, cp_offset * char_size()));
     __ movp(register_location(reg), rax);
   }
 }
 
 
 void RegExpMacroAssemblerX64::ClearRegisters(int reg_from, int reg_to) {
   DCHECK(reg_from <= reg_to);
-  __ movp(rax, Operand(rbp, kInputStartMinusOne));
+  __ movp(rax, Operand(rbp, kStringStartMinusOne));
   for (int reg = reg_from; reg <= reg_to; reg++) {
     __ movp(register_location(reg), rax);
   }
 }
 
 
 void RegExpMacroAssemblerX64::WriteStackPointerToRegister(int reg) {
   __ movp(rax, backtrack_stackpointer());
   __ subp(rax, Operand(rbp, kStackHighEnd));
   __ movp(register_location(reg), rax);
@@ skipping 60 matching lines @@
   DCHECK(register_index < (1<<30));
   if (num_registers_ <= register_index) {
     num_registers_ = register_index + 1;
   }
   return Operand(rbp, kRegisterZero - register_index * kPointerSize);
 }
 
 
 void RegExpMacroAssemblerX64::CheckPosition(int cp_offset,
                                             Label* on_outside_input) {
-  __ cmpl(rdi, Immediate(-cp_offset * char_size()));
-  BranchOrBacktrack(greater_equal, on_outside_input);
+  if (cp_offset >= 0) {
+    __ cmpl(rdi, Immediate(-cp_offset * char_size()));
+    BranchOrBacktrack(greater_equal, on_outside_input);
+  } else {
+    __ leap(rax, Operand(rdi, cp_offset * char_size()));
+    __ cmpp(rax, Operand(rbp, kStringStartMinusOne));
+    BranchOrBacktrack(less_equal, on_outside_input);
+  }
 }
 
 
 void RegExpMacroAssemblerX64::BranchOrBacktrack(Condition condition,
                                                 Label* to) {
   if (condition < 0) {  // No condition
     if (to == NULL) {
       Backtrack();
       return;
     }
@@ skipping 132 matching lines @@
 }
 
 #undef __
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_TARGET_ARCH_X64