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 153 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));
+  for (int i = 0; i < char_size(); i++) {
+    __ addp(rax, Operand(rbp, kStartIndex));
+  }
   __ cmpp(rax, Operand(rbp, kInputStart));
   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));
+void RegExpMacroAssemblerX64::CheckNotAtStart(int cp_offset,
+                                              Label* on_not_at_start) {
+  __ leap(rax, Operand(rsi, rdi, times_1, cp_offset * char_size()));
+  for (int i = 0; i < char_size(); i++) {
+    __ addp(rax, Operand(rbp, kStartIndex));
+  }
   __ cmpp(rax, Operand(rbp, kInputStart));
   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) {
+    __ leap(rax, Operand(rsi, rdi, times_1, 0));
+    __ subp(rax, rbx);
+    for (int i = 0; i < char_size(); i++) {
+      __ addp(rax, Operand(rbp, kStartIndex));
+    }
+    __ cmpp(rax, Operand(rbp, kInputStart));
+    BranchOrBacktrack(less, 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) {
+    __ leap(rbx, Operand(rsi, rdi, times_1, 0));
+    __ subp(rbx, rax);
+    for (int i = 0; i < char_size(); i++) {
+      __ addp(rbx, Operand(rbp, kStartIndex));
+    }
+    __ cmpp(rbx, Operand(rbp, kInputStart));
+    BranchOrBacktrack(less, 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 582 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 163 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 {
+    __ leaq(rax, Operand(rsi, rdi, times_1, cp_offset * char_size()));
+    for (int i = 0; i < char_size(); i++) {
+      __ addq(rax, Operand(rbp, kStartIndex));
+    }
+    __ cmpq(rax, Operand(rbp, kInputStart));
+    BranchOrBacktrack(less, 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