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 35 matching lines @@
  *       - start index          (character index of start)
  *       - String* input_string (location of a handle containing the string)
  *       --- frame alignment (if applicable) ---
  *       - return address
  * ebp-> - old ebp
  *       - backup of caller esi
  *       - backup of caller edi
  *       - backup of caller ebx
  *       - success counter      (only for global regexps 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.
  *       - register 0  ebp[-4]  (only positions must be stored in the first
  *       - register 1  ebp[-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 as garbage.
  *
  * The data up to the return address must be placed there by the calling
  * code, by calling the code entry as cast to a function with the signature:
@@ skipping 82 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));
-  __ cmp(eax, Operand(ebp, kInputStart));
+  __ lea(eax, Operand(edi, -char_size()));
+  __ cmp(eax, Operand(ebp, kStringStartMinusOne));
   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));
-  __ cmp(eax, Operand(ebp, kInputStart));
+void RegExpMacroAssemblerIA32::CheckNotAtStart(int cp_offset,
+                                               Label* on_not_at_start) {
+  __ lea(eax, Operand(edi, -char_size() + cp_offset * char_size()));
+  __ cmp(eax, Operand(ebp, kStringStartMinusOne));
   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,
-    Label* on_no_match) {
+    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.
+  // At this point, the capture registers are either both set or both cleared.
+  // If the capture length is zero, then the capture is either empty or cleared.
+  // Fall through in both cases.
   __ j(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) {
+    __ mov(eax, Operand(ebp, kStringStartMinusOne));
+    __ add(eax, ebx);
+    __ cmp(edi, eax);
+    BranchOrBacktrack(less_equal, 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,
-    Label* on_no_match) {
+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)
+
+  // At this point, the capture registers are either both set or both cleared.
+  // If the capture length is zero, then the capture is either empty or cleared.
+  // Fall through in both cases.
   __ j(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) {
+    __ mov(ebx, Operand(ebp, kStringStartMinusOne));
+    __ add(ebx, eax);
+    __ cmp(edi, ebx);
+    BranchOrBacktrack(less_equal, 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 225 matching lines @@
 
   // Actually emit code to start a new stack frame.
   __ push(ebp);
   __ mov(ebp, esp);
   // Save callee-save registers. Order here should correspond to order of
   // kBackup_ebx etc.
   __ push(esi);
   __ push(edi);
   __ push(ebx);  // Callee-save on MacOS.
   __ 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());
   __ mov(ecx, esp);
   __ sub(ecx, Operand::StaticVariable(stack_limit));
   // Handle it if the stack pointer is already below the stack limit.
@@ skipping 29 matching lines @@
   // Set eax to address of char before start of the string.
   // (effectively string position -1).
   __ neg(ebx);
   if (mode_ == UC16) {
     __ lea(eax, Operand(edi, ebx, times_2, -char_size()));
   } else {
     __ lea(eax, Operand(edi, ebx, times_1, -char_size()));
   }
   // Store this value in a local variable, for use when clearing
   // position registers.
-  __ mov(Operand(ebp, kInputStartMinusOne), eax);
+  __ mov(Operand(ebp, kStringStartMinusOne), eax);
 
 #if V8_OS_WIN
   // Ensure that we write 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) {
     __ mov(register_location(i), eax);  // One write every page.
@@ skipping 62 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_);
 
       __ mov(Operand(ebp, kNumOutputRegisters), ecx);
       // Advance the location for output.
       __ add(Operand(ebp, kRegisterOutput),
              Immediate(num_saved_registers_ * kPointerSize));
 
       // Prepare eax to initialize registers with its value in the next run.
-      __ mov(eax, Operand(ebp, kInputStartMinusOne));
+      __ mov(eax, Operand(ebp, kStringStartMinusOne));
 
       if (global_with_zero_length_check()) {
         // Special case for zero-length matches.
         // edx: capture start index
         __ cmp(edi, edx);
         // Not a zero-length match, restart.
         __ j(not_equal, &load_char_start_regexp);
         // edi (offset from the end) is zero if we already reached the end.
         __ test(edi, edi);
         __ j(zero, &exit_label_, Label::kNear);
@@ skipping 139 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 63 matching lines @@
     __ mov(register_location(reg), edi);
   } else {
     __ lea(eax, Operand(edi, cp_offset * char_size()));
     __ mov(register_location(reg), eax);
   }
 }
 
 
 void RegExpMacroAssemblerIA32::ClearRegisters(int reg_from, int reg_to) {
   DCHECK(reg_from <= reg_to);
-  __ mov(eax, Operand(ebp, kInputStartMinusOne));
+  __ mov(eax, Operand(ebp, kStringStartMinusOne));
   for (int reg = reg_from; reg <= reg_to; reg++) {
     __ mov(register_location(reg), eax);
   }
 }
 
 
 void RegExpMacroAssemblerIA32::WriteStackPointerToRegister(int reg) {
   __ mov(eax, backtrack_stackpointer());
   __ sub(eax, Operand(ebp, kStackHighEnd));
   __ mov(register_location(reg), eax);
@@ skipping 48 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(edi, cp_offset * char_size()));
+    __ cmp(eax, Operand(ebp, kStringStartMinusOne));
+    BranchOrBacktrack(less_equal, 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