X64: Implement RegExp natively.

src/regexp-macro-assembler.h

 // Copyright 2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 28 matching lines @@
 
 class RegExpMacroAssembler {
  public:
   // The implementation must be able to handle at least:
   static const int kMaxRegister = (1 << 16) - 1;
   static const int kMaxCPOffset = (1 << 15) - 1;
   static const int kMinCPOffset = -(1 << 15);
   enum IrregexpImplementation {
     kIA32Implementation,
     kARMImplementation,
+    kX64Implementation,
     kBytecodeImplementation
   };
 
   enum StackCheckFlag {
     kNoStackLimitCheck = false,
     kCheckStackLimit = true
   };
 
   RegExpMacroAssembler();
   virtual ~RegExpMacroAssembler();
   // The maximal number of pushes between stack checks. Users must supply
   // kCheckStackLimit flag to push operations (instead of kNoStackLimitCheck)
   // at least once for every stack_limit() pushes that are executed.
   virtual int stack_limit_slack() = 0;
   virtual void AdvanceCurrentPosition(int by) = 0;  // Signed cp change.
   virtual void AdvanceRegister(int reg, int by) = 0;  // r[reg] += by.
   // Continues execution from the position pushed on the top of the backtrack
   // stack by an earlier PushBacktrack(Label*).
   virtual void Backtrack() = 0;
   virtual void Bind(Label* label) = 0;
   virtual void CheckAtStart(Label* on_at_start) = 0;
-  // Check the current character against a bitmap.  The range of the current
-  // character must be from start to start + length_of_bitmap_in_bits.
-  virtual void CheckBitmap(
-      uc16 start,           // The bitmap is indexed from this character.
-      Label* bitmap,        // Where the bitmap is emitted.
-      Label* on_zero) = 0;  // Where to go if the bit is 0.  Fall through on 1.
   // Dispatch after looking the current character up in a 2-bits-per-entry
   // map.  The destinations vector has up to 4 labels.
   virtual void CheckCharacter(uint32_t c, Label* on_equal) = 0;
   // Bitwise and the current character with the given constant and then
   // check for a match with c.
   virtual void CheckCharacterAfterAnd(uint32_t c,
                                       uint32_t and_with,
                                       Label* on_equal) = 0;
   virtual void CheckCharacterGT(uc16 limit, Label* on_greater) = 0;
   virtual void CheckCharacterLT(uc16 limit, Label* on_less) = 0;
@@ skipping 39 matching lines @@
   // Check whether a standard/default character class matches the current
   // character. Returns false if the type of special character class does
   // not have custom support.
   // May clobber the current loaded character.
   virtual bool CheckSpecialCharacterClass(uc16 type,
                                           int cp_offset,
                                           bool check_offset,
                                           Label* on_no_match) {
     return false;
   }
-  // Dispatch after looking the current character up in a byte map.  The
-  // destinations vector has up to 256 labels.
-  virtual void DispatchByteMap(
-      uc16 start,
-      Label* byte_map,
-      const Vector<Label*>& destinations) = 0;
-  virtual void DispatchHalfNibbleMap(
-      uc16 start,
-      Label* half_nibble_map,
-      const Vector<Label*>& destinations) = 0;
-  // Dispatch after looking the high byte of the current character up in a byte
-  // map.  The destinations vector has up to 256 labels.
-  virtual void DispatchHighByteMap(
-      byte start,
-      Label* byte_map,
-      const Vector<Label*>& destinations) = 0;
-  virtual void EmitOrLink(Label* label) = 0;
   virtual void Fail() = 0;
   virtual Handle<Object> GetCode(Handle<String> source) = 0;
   virtual void GoTo(Label* label) = 0;
   // Check whether a register is >= a given constant and go to a label if it
   // is.  Backtracks instead if the label is NULL.
   virtual void IfRegisterGE(int reg, int comparand, Label* if_ge) = 0;
   // Check whether a register is < a given constant and go to a label if it is.
   // Backtracks instead if the label is NULL.
   virtual void IfRegisterLT(int reg, int comparand, Label* if_lt) = 0;
   // Check whether a register is == to the current position and go to a
@@ skipping 12 matching lines @@
   virtual void PushCurrentPosition() = 0;
   virtual void PushRegister(int register_index,
                             StackCheckFlag check_stack_limit) = 0;
   virtual void ReadCurrentPositionFromRegister(int reg) = 0;
   virtual void ReadStackPointerFromRegister(int reg) = 0;
   virtual void SetRegister(int register_index, int to) = 0;
   virtual void Succeed() = 0;
   virtual void WriteCurrentPositionToRegister(int reg, int cp_offset) = 0;
   virtual void ClearRegisters(int reg_from, int reg_to) = 0;
   virtual void WriteStackPointerToRegister(int reg) = 0;
-
- private:
 };
 
 
-struct ArraySlice {
+class NativeRegExpMacroAssembler: public RegExpMacroAssembler {
  public:
-  ArraySlice(Handle<ByteArray> array, size_t offset)
-    : array_(array), offset_(offset) {}
-  Handle<ByteArray> array() { return array_; }
-  // Offset in the byte array data.
-  size_t offset() { return offset_; }
-  // Offset from the ByteArray pointer.
-  size_t base_offset() {
-    return ByteArray::kHeaderSize - kHeapObjectTag + offset_;
-  }
-  void* location() {
-    return reinterpret_cast<void*>(array_->GetDataStartAddress() + offset_);
-  }
-  template <typename T>
-  T& at(int idx) {
-    return reinterpret_cast<T*>(array_->GetDataStartAddress() + offset_)[idx];
-  }
- private:
-  Handle<ByteArray> array_;
-  size_t offset_;
-};
+  // Type of input string to generate code for.
+  enum Mode { ASCII = 1, UC16 = 2 };
 
+  // Result of calling generated native RegExp code.
+  // RETRY: Something significant changed during execution, and the matching
+  //        should be retried from scratch.
+  // EXCEPTION: Something failed during execution. If no exception has been
+  //        thrown, it's an internal out-of-memory, and the caller should
+  //        throw the exception.
+  // FAILURE: Matching failed.
+  // SUCCESS: Matching succeeded, and the output array has been filled with
+  //        capture positions.
+  enum Result { RETRY = -2, EXCEPTION = -1, FAILURE = 0, SUCCESS = 1 };
 
-class ByteArrayProvider {
- public:
-  explicit ByteArrayProvider(unsigned int initial_size);
-  // Provides a place to put "size" elements of size "element_size".
-  // The information can be stored in the provided ByteArray at the "offset".
-  // The offset is aligned to the element size.
-  ArraySlice GetBuffer(unsigned int size,
-                       unsigned int element_size);
-  template <typename T>
-  ArraySlice GetBuffer(Vector<T> values);
- private:
-  size_t byte_array_size_;
-  Handle<ByteArray> current_byte_array_;
-  int current_byte_array_free_offset_;
+  NativeRegExpMacroAssembler();
+  virtual ~NativeRegExpMacroAssembler();
+
+  static Result Match(Handle<Code> regexp,
+                      Handle<String> subject,
+                      int* offsets_vector,
+                      int offsets_vector_length,
+                      int previous_index);
+
+  // Compares two-byte strings case insensitively.
+  // Called from generated RegExp code.
+  static int CaseInsensitiveCompareUC16(Address byte_offset1,
+                                        Address byte_offset2,
+                                        size_t byte_length);
+
+  static const byte* StringCharacterPosition(String* subject, int start_index);
+
+  static Result Execute(Code* code,
+                        String* input,
+                        int start_offset,
+                        const byte* input_start,
+                        const byte* input_end,
+                        int* output,
+                        bool at_start);
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_REGEXP_MACRO_ASSEMBLER_H_