Experimental support for RegExp lookbehind.

src/regexp/arm64/regexp-macro-assembler-arm64.cc

 // Copyright 2013 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_ARM64
 
 #include "src/regexp/arm64/regexp-macro-assembler-arm64.h"
 
 #include "src/code-stubs.h"
 #include "src/log.h"
@@ skipping 192 matching lines @@
 }
 
 
 void RegExpMacroAssemblerARM64::CheckCharacterGT(uc16 limit,
                                                  Label* on_greater) {
   CompareAndBranchOrBacktrack(current_character(), limit, hi, on_greater);
 }
 
 
 void RegExpMacroAssemblerARM64::CheckAtStart(Label* on_at_start) {
-  Label not_at_start;
-  // Did we start the match at the start of the input string?
-  CompareAndBranchOrBacktrack(start_offset(), 0, ne, &not_at_start);
-  // If we did, are we still at the start of the input string?
-  __ Add(x10, input_end(), Operand(current_input_offset(), SXTW));
-  __ Cmp(x10, input_start());
+  __ Add(w10, current_input_offset(), Operand(-char_size()));
+  __ Cmp(w10, string_start_minus_one());
   BranchOrBacktrack(eq, on_at_start);
-  __ Bind(&not_at_start);
 }
 
 
-void RegExpMacroAssemblerARM64::CheckNotAtStart(Label* on_not_at_start) {
-  // Did we start the match at the start of the input string?
-  CompareAndBranchOrBacktrack(start_offset(), 0, ne, on_not_at_start);
-  // If we did, are we still at the start of the input string?
-  __ Add(x10, input_end(), Operand(current_input_offset(), SXTW));
-  __ Cmp(x10, input_start());
+void RegExpMacroAssemblerARM64::CheckNotAtStart(int cp_offset,
+                                                Label* on_not_at_start) {
+  __ Add(w10, current_input_offset(),
+         Operand(-char_size() + cp_offset * char_size()));
+  __ Cmp(w10, string_start_minus_one());
   BranchOrBacktrack(ne, on_not_at_start);
 }
 
 
 void RegExpMacroAssemblerARM64::CheckCharacterLT(uc16 limit, Label* on_less) {
   CompareAndBranchOrBacktrack(current_character(), limit, lo, on_less);
 }
 
 
 void RegExpMacroAssemblerARM64::CheckCharacters(Vector<const uc16> str,
@@ skipping 30 matching lines @@
 
 void RegExpMacroAssemblerARM64::CheckGreedyLoop(Label* on_equal) {
   __ Ldr(w10, MemOperand(backtrack_stackpointer()));
   __ Cmp(current_input_offset(), w10);
   __ Cset(x11, eq);
   __ Add(backtrack_stackpointer(),
          backtrack_stackpointer(), Operand(x11, LSL, kWRegSizeLog2));
   BranchOrBacktrack(eq, on_equal);
 }
 
+
 void RegExpMacroAssemblerARM64::CheckNotBackReferenceIgnoreCase(
-    int start_reg,
-    Label* on_no_match) {
+    int start_reg, bool read_backward, Label* on_no_match) {
   Label fallthrough;
 
   Register capture_start_offset = w10;
   // Save the capture length in a callee-saved register so it will
   // be preserved if we call a C helper.
   Register capture_length = w19;
   DCHECK(kCalleeSaved.IncludesAliasOf(capture_length));
 
   // Find length of back-referenced capture.
   DCHECK((start_reg % 2) == 0);
   if (start_reg < kNumCachedRegisters) {
     __ Mov(capture_start_offset.X(), GetCachedRegister(start_reg));
     __ Lsr(x11, GetCachedRegister(start_reg), kWRegSizeInBits);
   } else {
     __ Ldp(w11, capture_start_offset, capture_location(start_reg, x10));
   }
   __ Sub(capture_length, w11, capture_start_offset);  // Length to check.
-  // Succeed on empty capture (including no capture).
-  __ Cbz(capture_length, &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.
+  __ CompareAndBranch(capture_length, Operand(0), le, &fallthrough);
 
   // Check that there are enough characters left in the input.
-  __ Cmn(capture_length, current_input_offset());
-  BranchOrBacktrack(gt, on_no_match);
+  if (read_backward) {
+    __ Sub(w12, current_input_offset(), capture_length);
+    __ Cmp(w12, string_start_minus_one());
+    BranchOrBacktrack(le, on_no_match);
+  } else {
+    __ Cmn(capture_length, current_input_offset());
+    BranchOrBacktrack(gt, on_no_match);
+  }
 
   if (mode_ == LATIN1) {
     Label success;
     Label fail;
     Label loop_check;
 
     Register capture_start_address = x12;
     Register capture_end_addresss = x13;
     Register current_position_address = x14;
 
     __ Add(capture_start_address,
            input_end(),
            Operand(capture_start_offset, SXTW));
     __ Add(capture_end_addresss,
            capture_start_address,
            Operand(capture_length, SXTW));
     __ Add(current_position_address,
            input_end(),
            Operand(current_input_offset(), SXTW));
+    if (read_backward) {
+      // Offset by length when matching backwards.
+      __ Sub(current_position_address, current_position_address,
+             Operand(capture_length, SXTW));
+    }
 
     Label loop;
     __ Bind(&loop);
     __ Ldrb(w10, MemOperand(capture_start_address, 1, PostIndex));
     __ Ldrb(w11, MemOperand(current_position_address, 1, PostIndex));
     __ Cmp(w10, w11);
     __ B(eq, &loop_check);
 
     // Mismatch, try case-insensitive match (converting letters to lower-case).
     __ Orr(w10, w10, 0x20);  // Convert capture character to lower-case.
@@ skipping 19 matching lines @@
 
     __ Bind(&success);
     // Compute new value of character position after the matched part.
     __ Sub(current_input_offset().X(), current_position_address, input_end());
     if (masm_->emit_debug_code()) {
       __ Cmp(current_input_offset().X(), Operand(current_input_offset(), SXTW));
       __ Ccmp(current_input_offset(), 0, NoFlag, eq);
       // The current input offset should be <= 0, and fit in a W register.
       __ Check(le, kOffsetOutOfRange);
     }
+    if (read_backward) {
+      __ Sub(current_input_offset(), current_input_offset(),
+             Operand(capture_length, SXTW));
+    }
   } else {
     DCHECK(mode_ == UC16);
     int argument_count = 4;
 
     // The cached registers need to be retained.
     CPURegList cached_registers(CPURegister::kRegister, kXRegSizeInBits, 0, 7);
     DCHECK((cached_registers.Count() * 2) == kNumCachedRegisters);
     __ PushCPURegList(cached_registers);
 
     // Put arguments into arguments registers.
     // Parameters are
     //   x0: Address byte_offset1 - Address captured substring's start.
     //   x1: Address byte_offset2 - Address of current character position.
     //   w2: size_t byte_length - length of capture in bytes(!)
     //   x3: Isolate* isolate
 
     // Address of start of capture.
     __ Add(x0, input_end(), Operand(capture_start_offset, SXTW));
     // Length of capture.
     __ Mov(w2, capture_length);
     // Address of current input position.
     __ Add(x1, input_end(), Operand(current_input_offset(), SXTW));
+    if (read_backward) {
+      __ Sub(x1, x1, Operand(capture_length, SXTW));
+    }
     // Isolate.
     __ Mov(x3, 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.
     // x0 is one of the registers used as a cache so it must be tested before
     // the cache is restored.
     __ Cmp(x0, 0);
     __ PopCPURegList(cached_registers);
     BranchOrBacktrack(eq, on_no_match);
 
-    // On success, increment position by length of capture.
-    __ Add(current_input_offset(), current_input_offset(), capture_length);
+    // On success, advance position by length of capture.
+    if (read_backward) {
+      __ Sub(current_input_offset(), current_input_offset(), capture_length);
+    } else {
+      __ Add(current_input_offset(), current_input_offset(), capture_length);
+    }
   }
 
   __ Bind(&fallthrough);
 }
 
-void RegExpMacroAssemblerARM64::CheckNotBackReference(
-    int start_reg,
-    Label* on_no_match) {
+void RegExpMacroAssemblerARM64::CheckNotBackReference(int start_reg,
+                                                      bool read_backward,
+                                                      Label* on_no_match) {
   Label fallthrough;
 
   Register capture_start_address = x12;
   Register capture_end_address = x13;
   Register current_position_address = x14;
   Register capture_length = w15;
 
   // Find length of back-referenced capture.
   DCHECK((start_reg % 2) == 0);
   if (start_reg < kNumCachedRegisters) {
     __ Mov(x10, GetCachedRegister(start_reg));
     __ Lsr(x11, GetCachedRegister(start_reg), kWRegSizeInBits);
   } else {
     __ Ldp(w11, w10, capture_location(start_reg, x10));
   }
   __ Sub(capture_length, w11, w10);  // Length to check.
-  // Succeed on empty capture (including no capture).
-  __ Cbz(capture_length, &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.
+  __ CompareAndBranch(capture_length, Operand(0), le, &fallthrough);
 
   // Check that there are enough characters left in the input.
-  __ Cmn(capture_length, current_input_offset());
-  BranchOrBacktrack(gt, on_no_match);
+  if (read_backward) {
+    __ Sub(w12, current_input_offset(), capture_length);
+    __ Cmp(w12, string_start_minus_one());
+    BranchOrBacktrack(le, on_no_match);
+  } else {
+    __ Cmn(capture_length, current_input_offset());
+    BranchOrBacktrack(gt, on_no_match);
+  }
 
   // Compute pointers to match string and capture string
   __ Add(capture_start_address, input_end(), Operand(w10, SXTW));
   __ Add(capture_end_address,
          capture_start_address,
          Operand(capture_length, SXTW));
   __ Add(current_position_address,
          input_end(),
          Operand(current_input_offset(), SXTW));
+  if (read_backward) {
+    // Offset by length when matching backwards.
+    __ Sub(current_position_address, current_position_address,
+           Operand(capture_length, SXTW));
+  }
 
   Label loop;
   __ Bind(&loop);
   if (mode_ == LATIN1) {
     __ Ldrb(w10, MemOperand(capture_start_address, 1, PostIndex));
     __ Ldrb(w11, MemOperand(current_position_address, 1, PostIndex));
   } else {
     DCHECK(mode_ == UC16);
     __ Ldrh(w10, MemOperand(capture_start_address, 2, PostIndex));
     __ Ldrh(w11, MemOperand(current_position_address, 2, PostIndex));
   }
   __ Cmp(w10, w11);
   BranchOrBacktrack(ne, on_no_match);
   __ Cmp(capture_start_address, capture_end_address);
   __ B(lt, &loop);
 
   // Move current character position to position after match.
   __ Sub(current_input_offset().X(), current_position_address, input_end());
+  if (read_backward) {
+    __ Sub(current_input_offset(), current_input_offset(),
+           Operand(capture_length, SXTW));
+  }
+
   if (masm_->emit_debug_code()) {
     __ Cmp(current_input_offset().X(), Operand(current_input_offset(), SXTW));
     __ Ccmp(current_input_offset(), 0, NoFlag, eq);
     // The current input offset should be <= 0, and fit in a W register.
     __ Check(le, kOffsetOutOfRange);
   }
   __ Bind(&fallthrough);
 }
 
 
@@ skipping 279 matching lines @@
     // Check that the input string length is < 2^30.
     __ Neg(x11, x10);
     __ Cmp(x11, (1<<30) - 1);
     __ Check(ls, kInputStringTooLong);
   }
   __ Mov(current_input_offset(), w10);
 
   // The non-position value is used as a clearing value for the
   // capture registers, it corresponds to the position of the first character
   // minus one.
-  __ Sub(non_position_value(), current_input_offset(), char_size());
-  __ Sub(non_position_value(), non_position_value(),
+  __ Sub(string_start_minus_one(), current_input_offset(), char_size());
+  __ Sub(string_start_minus_one(), string_start_minus_one(),
          Operand(start_offset(), LSL, (mode_ == UC16) ? 1 : 0));
   // We can store this value twice in an X register for initializing
   // on-stack registers later.
-  __ Orr(twice_non_position_value(),
-         non_position_value().X(),
-         Operand(non_position_value().X(), LSL, kWRegSizeInBits));
+  __ Orr(twice_non_position_value(), string_start_minus_one().X(),
+         Operand(string_start_minus_one().X(), LSL, kWRegSizeInBits));
 
   // 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.
   __ Cbnz(start_offset(), &load_char_start_regexp);
   __ Mov(current_character(), '\n');
   __ B(&start_regexp);
 
@@ skipping 295 matching lines @@
   return kARM64Implementation;
 }
 
 
 void RegExpMacroAssemblerARM64::LoadCurrentCharacter(int cp_offset,
                                                      Label* on_end_of_input,
                                                      bool check_bounds,
                                                      int characters) {
   // TODO(pielan): Make sure long strings are caught before this, and not
   // just asserted in debug mode.
-  DCHECK(cp_offset >= -1);      // ^ and \b can look behind one character.
   // Be sane! (And ensure that an int32_t can be used to index the string)
   DCHECK(cp_offset < (1<<30));
   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 RegExpMacroAssemblerARM64::PopCurrentPosition() {
   Pop(current_input_offset());
 }
 
 
@@ skipping 104 matching lines @@
 }
 
 
 void RegExpMacroAssemblerARM64::ClearRegisters(int reg_from, int reg_to) {
   DCHECK(reg_from <= reg_to);
   int num_registers = reg_to - reg_from + 1;
 
   // If the first capture register is cached in a hardware register but not
   // aligned on a 64-bit one, we need to clear the first one specifically.
   if ((reg_from < kNumCachedRegisters) && ((reg_from % 2) != 0)) {
-    StoreRegister(reg_from, non_position_value());
+    StoreRegister(reg_from, string_start_minus_one());
     num_registers--;
     reg_from++;
   }
 
   // Clear cached registers in pairs as far as possible.
   while ((num_registers >= 2) && (reg_from < kNumCachedRegisters)) {
     DCHECK(GetRegisterState(reg_from) == CACHED_LSW);
     __ Mov(GetCachedRegister(reg_from), twice_non_position_value());
     reg_from += 2;
     num_registers -= 2;
   }
 
   if ((num_registers % 2) == 1) {
-    StoreRegister(reg_from, non_position_value());
+    StoreRegister(reg_from, string_start_minus_one());
     num_registers--;
     reg_from++;
   }
 
   if (num_registers > 0) {
     // If there are some remaining registers, they are stored on the stack.
     DCHECK(reg_from >= kNumCachedRegisters);
 
     // Move down the indexes of the registers on stack to get the correct offset
     // in memory.
@@ skipping 56 matching lines @@
     const byte** input_start, const byte** input_end) {
   return NativeRegExpMacroAssembler::CheckStackGuardState(
       frame_entry<Isolate*>(re_frame, kIsolate), start_index,
       frame_entry<int>(re_frame, kDirectCall) == 1, return_address, re_code,
       frame_entry_address<String*>(re_frame, kInput), input_start, input_end);
 }
 
 
 void RegExpMacroAssemblerARM64::CheckPosition(int cp_offset,
                                               Label* on_outside_input) {
-  CompareAndBranchOrBacktrack(current_input_offset(),
-                              -cp_offset * char_size(),
-                              ge,
-                              on_outside_input);
+  if (cp_offset >= 0) {
+    CompareAndBranchOrBacktrack(current_input_offset(),
+                                -cp_offset * char_size(), ge, on_outside_input);
+  } else {
+    __ Add(w12, current_input_offset(), Operand(cp_offset * char_size()));
+    __ Cmp(w12, string_start_minus_one());
+    BranchOrBacktrack(le, on_outside_input);
+  }
 }
 
 
 bool RegExpMacroAssemblerARM64::CanReadUnaligned() {
   // TODO(pielan): See whether or not we should disable unaligned accesses.
   return !slow_safe();
 }
 
 
 // Private methods:
@@ skipping 288 matching lines @@
     }
   }
 }
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_TARGET_ARCH_ARM64