Experimental support for RegExp lookbehind.

src/regexp/ia32/regexp-macro-assembler-ia32.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_IA32
 
 #include "src/regexp/ia32/regexp-macro-assembler-ia32.h"
 
 #include "src/log.h"
 #include "src/macro-assembler.h"
@@ skipping 138 matching lines @@
 }
 
 
 void RegExpMacroAssemblerIA32::CheckCharacterGT(uc16 limit, Label* on_greater) {
   __ cmp(current_character(), limit);
   BranchOrBacktrack(greater, 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);
 }
 
 
 void RegExpMacroAssemblerIA32::CheckCharacterLT(uc16 limit, Label* on_less) {
   __ cmp(current_character(), limit);
   BranchOrBacktrack(less, on_less);
 }
 
 
 void RegExpMacroAssemblerIA32::CheckGreedyLoop(Label* on_equal) {
   Label fallthrough;
   __ cmp(edi, Operand(backtrack_stackpointer(), 0));
   __ j(not_equal, &fallthrough);
   __ add(backtrack_stackpointer(), Immediate(kPointerSize));  // Pop.
   BranchOrBacktrack(no_condition, on_equal);
   __ bind(&fallthrough);
 }
 
 
 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;
     Label fail;
     Label loop_increment;
     // Save register contents to make the registers available below.
     __ push(edi);
     __ push(backtrack_stackpointer());
     // After this, the eax, ecx, and edi registers are available.
 
     __ 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;
     __ bind(&loop);
     __ movzx_b(eax, Operand(edi, 0));
     __ cmpb_al(Operand(edx, 0));
     __ j(equal, &loop_increment);
 
     // Mismatch, try case-insensitive match (converting letters to lower-case).
     __ or_(eax, 0x20);  // Convert match character to lower-case.
@@ skipping 30 matching lines @@
     __ pop(edi);
     BranchOrBacktrack(no_condition, on_no_match);
 
     __ bind(&success);
     // Restore original value before continuing.
     __ pop(backtrack_stackpointer());
     // Drop original value of character position.
     __ 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.
     __ push(esi);
     __ push(edi);
     __ push(backtrack_stackpointer());
     __ push(ebx);
 
     static const int argument_count = 4;
     __ PrepareCallCFunction(argument_count, ecx);
     // Put arguments into allocated stack area, last argument highest on stack.
     // 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
 
     // Set isolate.
     __ mov(Operand(esp, 3 * kPointerSize),
            Immediate(ExternalReference::isolate_address(isolate())));
     // Set byte_length.
     __ mov(Operand(esp, 2 * kPointerSize), ebx);
     // Set byte_offset2.
     // 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.
     __ add(edx, esi);
     __ mov(Operand(esp, 0 * kPointerSize), edx);
 
     {
       AllowExternalCallThatCantCauseGC scope(masm_);
       ExternalReference compare =
           ExternalReference::re_case_insensitive_compare_uc16(isolate());
       __ CallCFunction(compare, argument_count);
     }
     // Pop original values before reacting on result value.
     __ pop(ebx);
     __ pop(backtrack_stackpointer());
     __ pop(edi);
     __ pop(esi);
 
     // 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);
 }
 
 
 void RegExpMacroAssemblerIA32::CheckNotBackReference(
     int start_reg,
+    bool read_backward,
     Label* on_no_match) {
   Label fallthrough;
   Label success;
   Label fail;
 
   // Find length of back-referenced capture.
   __ 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
+  __ add(edx, esi);  // Start of capture.
   __ lea(ebx, Operand(esi, edi, times_1, 0));  // Start of match.
-  __ add(edx, esi);  // Start of capture.
+  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;
   __ bind(&loop);
   if (mode_ == LATIN1) {
     __ movzx_b(eax, Operand(edx, 0));
     __ cmpb_al(Operand(ebx, 0));
   } else {
     DCHECK(mode_ == UC16);
     __ movzx_w(eax, Operand(edx, 0));
@@ skipping 10 matching lines @@
 
   __ bind(&fail);
   // Restore backtrack stackpointer.
   __ pop(backtrack_stackpointer());
   BranchOrBacktrack(no_condition, on_no_match);
 
   __ bind(&success);
   // 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());
 
   __ bind(&fallthrough);
 }
 
 
 void RegExpMacroAssemblerIA32::CheckNotCharacter(uint32_t c,
                                                  Label* on_not_equal) {
   __ cmp(current_character(), c);
@@ skipping 358 matching lines @@
         // Convert to index from start of string, not end.
         __ add(eax, ecx);
         if (mode_ == UC16) {
           __ sar(eax, 1);  // Convert byte index to character index.
         }
         __ mov(Operand(ebx, i * kPointerSize), eax);
       }
     }
 
     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
       // output registers is reduced by the number of stored captures.
       __ mov(ecx, Operand(ebp, kNumOutputRegisters));
       __ sub(ecx, Immediate(num_saved_registers_));
       // Check whether we have enough room for another set of capture results.
       __ cmp(ecx, Immediate(num_saved_registers_));
       __ j(less, &exit_label_);
 
@@ skipping 156 matching lines @@
 RegExpMacroAssembler::IrregexpImplementation
     RegExpMacroAssemblerIA32::Implementation() {
   return kIA32Implementation;
 }
 
 
 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);
 }
 
 
 void RegExpMacroAssemblerIA32::PopCurrentPosition() {
   Pop(edi);
 }
 
 
@@ skipping 132 matching lines @@
   DCHECK(register_index < (1<<30));
   if (num_registers_ <= register_index) {
     num_registers_ = register_index + 1;
   }
   return Operand(ebp, kRegisterZero - register_index * kPointerSize);
 }
 
 
 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);
+  }
 }
 
 
 void RegExpMacroAssemblerIA32::BranchOrBacktrack(Condition condition,
                                                  Label* to) {
   if (condition < 0) {  // No condition
     if (to == NULL) {
       Backtrack();
       return;
     }
@@ skipping 104 matching lines @@
 
 
 #undef __
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_TARGET_ARCH_IA32