Experimental support for RegExp lookbehind.

src/regexp/arm/regexp-macro-assembler-arm.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_ARM
 
 #include "src/regexp/arm/regexp-macro-assembler-arm.h"
 
 #include "src/code-stubs.h"
 #include "src/log.h"
@@ skipping 158 matching lines @@
 }
 
 
 void RegExpMacroAssemblerARM::CheckCharacterGT(uc16 limit, Label* on_greater) {
   __ cmp(current_character(), Operand(limit));
   BranchOrBacktrack(gt, on_greater);
 }
 
 
 void RegExpMacroAssemblerARM::CheckAtStart(Label* on_at_start) {
-  Label not_at_start;
-  // Did we start the match at the start of the string at all?
-  __ ldr(r0, MemOperand(frame_pointer(), kStartIndex));
-  __ cmp(r0, Operand::Zero());
-  BranchOrBacktrack(ne, &not_at_start);
-
-  // If we did, are we still at the start of the input?
+  __ add(r0, end_of_input_address(), current_input_offset());
+  __ ldr(r1, MemOperand(frame_pointer(), kStartIndex));
+  for (int i = 0; i < char_size(); i++) {
+    __ add(r0, r0, r1);
+  }
   __ ldr(r1, MemOperand(frame_pointer(), kInputStart));
-  __ add(r0, end_of_input_address(), Operand(current_input_offset()));
   __ cmp(r0, r1);
   BranchOrBacktrack(eq, on_at_start);
-  __ bind(&not_at_start);
 }
 
 
-void RegExpMacroAssemblerARM::CheckNotAtStart(Label* on_not_at_start) {
-  // Did we start the match at the start of the string at all?
-  __ ldr(r0, MemOperand(frame_pointer(), kStartIndex));
-  __ cmp(r0, Operand::Zero());
-  BranchOrBacktrack(ne, on_not_at_start);
-  // If we did, are we still at the start of the input?
+void RegExpMacroAssemblerARM::CheckNotAtStart(int cp_offset,
+                                              Label* on_not_at_start) {
+  __ add(r0, end_of_input_address(), current_input_offset());
+  __ add(r0, r0, Operand(cp_offset * char_size()));
+  __ ldr(r1, MemOperand(frame_pointer(), kStartIndex));
+  for (int i = 0; i < char_size(); i++) {
+    __ add(r0, r0, r1);
+  }
   __ ldr(r1, MemOperand(frame_pointer(), kInputStart));
-  __ add(r0, end_of_input_address(), Operand(current_input_offset()));
   __ cmp(r0, r1);
   BranchOrBacktrack(ne, on_not_at_start);
 }
 
 
 void RegExpMacroAssemblerARM::CheckCharacterLT(uc16 limit, Label* on_less) {
   __ cmp(current_character(), Operand(limit));
   BranchOrBacktrack(lt, on_less);
 }
 
 
 void RegExpMacroAssemblerARM::CheckGreedyLoop(Label* on_equal) {
   __ ldr(r0, MemOperand(backtrack_stackpointer(), 0));
   __ cmp(current_input_offset(), r0);
   __ add(backtrack_stackpointer(),
          backtrack_stackpointer(), Operand(kPointerSize), LeaveCC, eq);
   BranchOrBacktrack(eq, on_equal);
 }
 
 
 void RegExpMacroAssemblerARM::CheckNotBackReferenceIgnoreCase(
-    int start_reg,
-    Label* on_no_match) {
+    int start_reg, bool read_backward, Label* on_no_match) {
   Label fallthrough;
   __ ldr(r0, register_location(start_reg));  // Index of start of capture
   __ ldr(r1, register_location(start_reg + 1));  // Index of end of capture
   __ sub(r1, r1, r0, SetCC);  // Length of capture.
 
-  // If length is zero, either the capture is empty or it is not participating.
-  // In either case succeed immediately.
-  __ b(eq, &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.
+  __ b(le, &fallthrough);
 
   // Check that there are enough characters left in the input.
-  __ cmn(r1, Operand(current_input_offset()));
-  BranchOrBacktrack(gt, on_no_match);
+  if (read_backward) {
+    __ add(r2, end_of_input_address(), current_input_offset());
+    __ ldr(r3, MemOperand(frame_pointer(), kStartIndex));
+    for (int i = 0; i < char_size(); i++) {
+      __ add(r2, r2, r3);
+    }
+    __ ldr(r3, MemOperand(frame_pointer(), kInputStart));
+    __ cmp(r2, r3);
+    BranchOrBacktrack(lt, on_no_match);
+  } else {
+    __ cmn(r1, Operand(current_input_offset()));
+    BranchOrBacktrack(gt, on_no_match);
+  }
 
   if (mode_ == LATIN1) {
     Label success;
     Label fail;
     Label loop_check;
 
     // r0 - offset of start of capture
     // r1 - length of capture
-    __ add(r0, r0, Operand(end_of_input_address()));
-    __ add(r2, end_of_input_address(), Operand(current_input_offset()));
-    __ add(r1, r0, Operand(r1));
+    __ add(r0, r0, end_of_input_address());
+    __ add(r2, end_of_input_address(), current_input_offset());
+    if (read_backward) {
+      __ sub(r2, r2, r1);  // Offset by length when matching backwards.
+    }
+    __ add(r1, r0, r1);
 
     // r0 - Address of start of capture.
     // r1 - Address of end of capture
     // r2 - Address of current input position.
 
     Label loop;
     __ bind(&loop);
     __ ldrb(r3, MemOperand(r0, char_size(), PostIndex));
     __ ldrb(r4, MemOperand(r2, char_size(), PostIndex));
     __ cmp(r4, r3);
@@ skipping 18 matching lines @@
     __ cmp(r0, r1);
     __ b(lt, &loop);
     __ jmp(&success);
 
     __ bind(&fail);
     BranchOrBacktrack(al, on_no_match);
 
     __ bind(&success);
     // Compute new value of character position after the matched part.
     __ sub(current_input_offset(), r2, end_of_input_address());
+    if (read_backward) {
+      __ ldr(r0, register_location(start_reg));  // Index of start of capture
+      __ ldr(r1, register_location(start_reg + 1));  // Index of end of capture
+      __ add(current_input_offset(), current_input_offset(), r0);
+      __ sub(current_input_offset(), current_input_offset(), r1);
+    }
   } else {
     DCHECK(mode_ == UC16);
     int argument_count = 4;
     __ PrepareCallCFunction(argument_count, r2);
 
     // r0 - offset of start of capture
     // r1 - length of capture
 
     // Put arguments into arguments registers.
     // Parameters are
     //   r0: Address byte_offset1 - Address captured substring's start.
     //   r1: Address byte_offset2 - Address of current character position.
     //   r2: size_t byte_length - length of capture in bytes(!)
     //   r3: Isolate* isolate
 
     // Address of start of capture.
     __ add(r0, r0, Operand(end_of_input_address()));
     // Length of capture.
     __ mov(r2, Operand(r1));
     // Save length in callee-save register for use on return.
     __ mov(r4, Operand(r1));
     // Address of current input position.
-    __ add(r1, current_input_offset(), Operand(end_of_input_address()));
+    __ add(r1, current_input_offset(), end_of_input_address());
+    if (read_backward) {
+      __ sub(r1, r1, r4);
+    }
     // Isolate.
     __ mov(r3, Operand(ExternalReference::isolate_address(isolate())));
 
     {
       AllowExternalCallThatCantCauseGC scope(masm_);
       ExternalReference function =
           ExternalReference::re_case_insensitive_compare_uc16(isolate());
       __ CallCFunction(function, argument_count);
     }
 
     // Check if function returned non-zero for success or zero for failure.
     __ cmp(r0, Operand::Zero());
     BranchOrBacktrack(eq, on_no_match);
-    // On success, increment position by length of capture.
-    __ add(current_input_offset(), current_input_offset(), Operand(r4));
+
+    // On success, advance position by length of capture.
+    if (read_backward) {
+      __ sub(current_input_offset(), current_input_offset(), r4);
+    } else {
+      __ add(current_input_offset(), current_input_offset(), r4);
+    }
   }
 
   __ bind(&fallthrough);
 }
 
 
-void RegExpMacroAssemblerARM::CheckNotBackReference(
-    int start_reg,
-    Label* on_no_match) {
+void RegExpMacroAssemblerARM::CheckNotBackReference(int start_reg,
+                                                    bool read_backward,
+                                                    Label* on_no_match) {
   Label fallthrough;
   Label success;
 
   // Find length of back-referenced capture.
   __ ldr(r0, register_location(start_reg));
   __ ldr(r1, register_location(start_reg + 1));
   __ sub(r1, r1, r0, SetCC);  // Length to check.
-  // Succeed on empty capture (including no capture).
-  __ b(eq, &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.
+  __ b(le, &fallthrough);
 
   // Check that there are enough characters left in the input.
-  __ cmn(r1, Operand(current_input_offset()));
-  BranchOrBacktrack(gt, on_no_match);
+  if (read_backward) {
+    __ add(r2, end_of_input_address(), current_input_offset());
+    __ ldr(r3, MemOperand(frame_pointer(), kStartIndex));
+    for (int i = 0; i < char_size(); i++) {
+      __ add(r2, r2, r3);
+    }
+    __ ldr(r3, MemOperand(frame_pointer(), kInputStart));
+    __ cmp(r2, r3);
+    BranchOrBacktrack(lt, on_no_match);
+  } else {
+    __ cmn(r1, Operand(current_input_offset()));
+    BranchOrBacktrack(gt, on_no_match);
+  }
 
-  // Compute pointers to match string and capture string
-  __ add(r0, r0, Operand(end_of_input_address()));
-  __ add(r2, end_of_input_address(), Operand(current_input_offset()));
-  __ add(r1, r1, Operand(r0));
+  // r0 - offset of start of capture
+  // r1 - length of capture
+  __ add(r0, r0, end_of_input_address());
+  __ add(r2, end_of_input_address(), current_input_offset());
+  if (read_backward) {
+    __ sub(r2, r2, r1);  // Offset by length when matching backwards.
+  }
+  __ add(r1, r0, r1);
 
   Label loop;
   __ bind(&loop);
   if (mode_ == LATIN1) {
     __ ldrb(r3, MemOperand(r0, char_size(), PostIndex));
     __ ldrb(r4, MemOperand(r2, char_size(), PostIndex));
   } else {
     DCHECK(mode_ == UC16);
     __ ldrh(r3, MemOperand(r0, char_size(), PostIndex));
     __ ldrh(r4, MemOperand(r2, char_size(), PostIndex));
   }
   __ cmp(r3, r4);
   BranchOrBacktrack(ne, on_no_match);
   __ cmp(r0, r1);
   __ b(lt, &loop);
 
   // Move current character position to position after match.
   __ sub(current_input_offset(), r2, end_of_input_address());
+  if (read_backward) {
+    __ ldr(r0, register_location(start_reg));      // Index of start of capture
+    __ ldr(r1, register_location(start_reg + 1));  // Index of end of capture
+    __ add(current_input_offset(), current_input_offset(), r0);
+    __ sub(current_input_offset(), current_input_offset(), r1);
+  }
+
   __ bind(&fallthrough);
 }
 
 
 void RegExpMacroAssemblerARM::CheckNotCharacter(unsigned c,
                                                 Label* on_not_equal) {
   __ cmp(current_character(), Operand(c));
   BranchOrBacktrack(ne, on_not_equal);
 }
 
@@ skipping 258 matching lines @@
   // Load string end.
   __ ldr(end_of_input_address(), MemOperand(frame_pointer(), kInputEnd));
   // Load input start.
   __ ldr(r0, MemOperand(frame_pointer(), kInputStart));
   // Find negative length (offset of start relative to end).
   __ sub(current_input_offset(), r0, end_of_input_address());
   // Set r0 to address of char before start of the input string
   // (effectively string position -1).
   __ ldr(r1, MemOperand(frame_pointer(), kStartIndex));
   __ sub(r0, current_input_offset(), Operand(char_size()));
   __ sub(r0, r0, Operand(r1, LSL, (mode_ == UC16) ? 1 : 0));

[erikcorry, 2015/11/13 14:30:13]

This instruction is better than the short for loop with 1 or 2 subs/adds.

   // Store this value in a local variable, for use when clearing
   // position registers.
   __ str(r0, MemOperand(frame_pointer(), kInputStartMinusOne));

[erikcorry, 2015/11/13 14:30:13]

This looks useful.  It's the actual position 1 less than the real start of the
string.  We can use this in the ^-checking code to avoid having to do maths? 
Will also produce more compact code I think.

 
   // Initialize code pointer register
   __ mov(code_pointer(), Operand(masm_->CodeObject()));
 
   Label load_char_start_regexp, start_regexp;
   // Load newline if index is at start, previous character otherwise.
   __ cmp(r1, Operand::Zero());
   __ b(ne, &load_char_start_regexp);
   __ mov(current_character(), Operand('\n'), LeaveCC, eq);
   __ jmp(&start_regexp);
@@ skipping 224 matching lines @@
 RegExpMacroAssembler::IrregexpImplementation
     RegExpMacroAssemblerARM::Implementation() {
   return kARMImplementation;
 }
 
 
 void RegExpMacroAssemblerARM::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 RegExpMacroAssemblerARM::PopCurrentPosition() {
   Pop(current_input_offset());
 }
 
 
@@ skipping 153 matching lines @@
   if (num_registers_ <= register_index) {
     num_registers_ = register_index + 1;
   }
   return MemOperand(frame_pointer(),
                     kRegisterZero - register_index * kPointerSize);
 }
 
 
 void RegExpMacroAssemblerARM::CheckPosition(int cp_offset,
                                             Label* on_outside_input) {
-  __ cmp(current_input_offset(), Operand(-cp_offset * char_size()));
-  BranchOrBacktrack(ge, on_outside_input);
+  if (cp_offset >= 0) {
+    __ cmp(current_input_offset(), Operand(-cp_offset * char_size()));
+    BranchOrBacktrack(ge, on_outside_input);
+  } else {
+    __ add(r0, end_of_input_address(), current_input_offset());
+    __ add(r0, r0, Operand(cp_offset * char_size()));
+    __ ldr(r1, MemOperand(frame_pointer(), kStartIndex));
+    for (int i = 0; i < char_size(); i++) {
+      __ add(r0, r0, r1);
+    }
+    __ ldr(r1, MemOperand(frame_pointer(), kInputStart));
+    __ cmp(r0, r1);
+    BranchOrBacktrack(lt, on_outside_input);
+  }
 }
 
 
 void RegExpMacroAssemblerARM::BranchOrBacktrack(Condition condition,
                                                 Label* to) {
   if (condition == al) {  // Unconditional.
     if (to == NULL) {
       Backtrack();
       return;
     }
@@ skipping 104 matching lines @@
 
 
 #undef __
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_TARGET_ARCH_ARM