[V8] Add hashing and comparison methods to v8::String

This allows us to more rapidly search for a v8::String inside a hash
of QStrings.

Change-Id: I8f7d7499b02103f346ef02a1e2c70033a0619fbe
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

7 files changed, 197 insertions, 2 deletions

diff --git a/src/3rdparty/v8/include/v8.h b/src/3rdparty/v8/include/v8.h
index cf9275d..175df14 100644
--- a/src/3rdparty/v8/include/v8.h
+++ b/src/3rdparty/v8/include/v8.h
@@ -1062,6 +1062,51 @@ class String : public Primitive {
   V8EXPORT bool MayContainNonAscii() const;
 
   /**
+   * Returns the hash of this string.
+   */
+  V8EXPORT uint32_t Hash() const;
+
+  struct CompleteHashData {
+    CompleteHashData() : length(0), hash(0), symbol_id(0) {}
+    int length;
+    uint32_t hash;
+    uint32_t symbol_id;
+  };
+
+  /**
+   * Returns the "complete" hash of the string.  This is
+   * all the information about the string needed to implement
+   * a very efficient hash keyed on the string.
+   *
+   * The members of CompleteHashData are:
+   *    length: The length of the string.  Equivalent to Length()
+   *    hash: The hash of the string.  Equivalent to Hash()
+   *    symbol_id: If the string is a sequential symbol, the symbol
+   *        id, otherwise 0.  If the symbol ids of two strings are
+   *        the same (and non-zero) the two strings are identical.
+   *        If the symbol ids are different the strings may still be
+   *        identical, but an Equals() check must be performed.
+   */
+  V8EXPORT CompleteHashData CompleteHash() const;
+
+  /**
+   * Compute a hash value for the passed UTF16 string
+   * data.
+   */
+  V8EXPORT static uint32_t ComputeHash(uint16_t *string, int length);
+  V8EXPORT static uint32_t ComputeHash(char *string, int length);
+
+  /**
+   * Returns true if this string is equal to the external
+   * string data provided.
+   */
+  V8EXPORT bool Equals(uint16_t *string, int length);
+  V8EXPORT bool Equals(char *string, int length);
+  inline bool Equals(Handle<Value> that) const {
+    return v8::Value::Equals(that);
+  }
+
+  /**
    * Write the contents of the string to an external buffer.
    * If no arguments are given, expects the buffer to be large
    * enough to hold the entire string and NULL terminator. Copies
@@ -1093,6 +1138,8 @@ class String : public Primitive {
     PRESERVE_ASCII_NULL = 4
   };
 
+  V8EXPORT uint16_t GetCharacter(int index);
+
   // 16-bit character codes.
   V8EXPORT int Write(uint16_t* buffer,
                      int start = 0,
diff --git a/src/3rdparty/v8/src/api.cc b/src/3rdparty/v8/src/api.cc
index 4820f9d..8921c0b 100644
--- a/src/3rdparty/v8/src/api.cc
+++ b/src/3rdparty/v8/src/api.cc
@@ -3887,6 +3887,59 @@ bool String::MayContainNonAscii() const {
 }
 
 
+uint32_t String::Hash() const {
+  i::Handle<i::String> str = Utils::OpenHandle(this);
+  if (IsDeadCheck(str->GetIsolate(), "v8::String::Hash()")) return 0;
+  return str->Hash();
+}
+
+
+String::CompleteHashData String::CompleteHash() const {
+  i::Handle<i::String> str = Utils::OpenHandle(this);
+  if (IsDeadCheck(str->GetIsolate(), "v8::String::CompleteHash()")) {
+    return CompleteHashData();
+  }
+  CompleteHashData result;
+  result.length = str->length();
+  result.hash = str->Hash();
+  if (str->IsSeqAsciiString() && str->IsSymbol())
+      result.symbol_id = i::SeqString::cast(*str)->symbol_id();
+  return result;
+}
+
+
+uint32_t String::ComputeHash(uint16_t *string, int length) {
+  return i::HashSequentialString<i::uc16>(string, length, i::kZeroHashSeed) >>
+      i::String::kHashShift;
+}
+
+
+uint32_t String::ComputeHash(char *string, int length) {
+  return i::HashSequentialString<char>(string, length, i::kZeroHashSeed) >>
+      i::String::kHashShift;
+}
+
+
+uint16_t String::GetCharacter(int index) {
+  i::Handle<i::String> str = Utils::OpenHandle(this);
+  return str->Get(index);
+}
+
+
+bool String::Equals(uint16_t *string, int length) {
+  i::Handle<i::String> str = Utils::OpenHandle(this);
+  if (IsDeadCheck(str->GetIsolate(), "v8::String::Equals()")) return 0;
+  return str->SlowEqualsExternal(string, length);
+}
+
+
+bool String::Equals(char *string, int length) {
+  i::Handle<i::String> str = Utils::OpenHandle(this);
+  if (IsDeadCheck(str->GetIsolate(), "v8::String::Equals()")) return 0;
+  return str->SlowEqualsExternal(string, length);
+}
+
+
 int String::WriteUtf8(char* buffer,
                       int capacity,
                       int* nchars_ref,
diff --git a/src/3rdparty/v8/src/heap-inl.h b/src/3rdparty/v8/src/heap-inl.h
index e038453..07f7d3a 100644
--- a/src/3rdparty/v8/src/heap-inl.h
+++ b/src/3rdparty/v8/src/heap-inl.h
@@ -130,6 +130,7 @@ MaybeObject* Heap::AllocateAsciiSymbol(Vector<const char> str,
   String* answer = String::cast(result);
   answer->set_length(str.length());
   answer->set_hash_field(hash_field);
+  SeqString::cast(answer)->set_symbol_id(0);
 
   ASSERT_EQ(size, answer->Size());
 
diff --git a/src/3rdparty/v8/src/heap.cc b/src/3rdparty/v8/src/heap.cc
index b85f1bc..18004be 100644
--- a/src/3rdparty/v8/src/heap.cc
+++ b/src/3rdparty/v8/src/heap.cc
@@ -4698,6 +4698,7 @@ MaybeObject* Heap::AllocateInternalSymbol(unibrow::CharacterStream* buffer,
   String* answer = String::cast(result);
   answer->set_length(chars);
   answer->set_hash_field(hash_field);
+  SeqString::cast(answer)->set_symbol_id(0);
 
   ASSERT_EQ(size, answer->Size());
 
diff --git a/src/3rdparty/v8/src/objects-inl.h b/src/3rdparty/v8/src/objects-inl.h
index d5815f2..62de787 100644
--- a/src/3rdparty/v8/src/objects-inl.h
+++ b/src/3rdparty/v8/src/objects-inl.h
@@ -2407,6 +2407,7 @@ SMI_ACCESSORS(FixedArrayBase, length, kLengthOffset)
 SMI_ACCESSORS(FreeSpace, size, kSizeOffset)
 
 SMI_ACCESSORS(String, length, kLengthOffset)
+SMI_ACCESSORS(SeqString, symbol_id, kSymbolIdOffset)
 
 
 uint32_t String::hash_field() {
diff --git a/src/3rdparty/v8/src/objects.cc b/src/3rdparty/v8/src/objects.cc
index fa5bfed..66ced63 100644
--- a/src/3rdparty/v8/src/objects.cc
+++ b/src/3rdparty/v8/src/objects.cc
@@ -7352,6 +7352,72 @@ static inline bool CompareStringContentsPartial(Isolate* isolate,
 }
 
 
+bool String::SlowEqualsExternal(uc16 *string, int length) {
+  int len = this->length();
+  if (len != length) return false;
+  if (len == 0) return true;
+
+  // We know the strings are both non-empty. Compare the first chars
+  // before we try to flatten the strings.
+  if (this->Get(0) != string[0]) return false;
+
+  String* lhs = this->TryFlattenGetString();
+
+  if (lhs->IsFlat()) {
+    String::FlatContent lhs_content = lhs->GetFlatContent();
+    if (lhs->IsAsciiRepresentation()) {
+      Vector<const char> vec1 = lhs_content.ToAsciiVector();
+      VectorIterator<char> buf1(vec1);
+      VectorIterator<uc16> ib(string, length);
+      return CompareStringContents(&buf1, &ib);
+    } else {
+      Vector<const uc16> vec1 = lhs_content.ToUC16Vector();
+      Vector<const uc16> vec2(string, length);
+      return CompareRawStringContents(vec1, vec2);
+    }
+  } else {
+    Isolate* isolate = GetIsolate();
+    isolate->objects_string_compare_buffer_a()->Reset(0, lhs);
+    VectorIterator<uc16> ib(string, length);
+    return CompareStringContents(isolate->objects_string_compare_buffer_a(),
+                                 &ib);
+  }
+}
+
+
+bool String::SlowEqualsExternal(char *string, int length) {
+  int len = this->length();
+  if (len != length) return false;
+  if (len == 0) return true;
+
+  // We know the strings are both non-empty. Compare the first chars
+  // before we try to flatten the strings.
+  if (this->Get(0) != string[0]) return false;
+
+  String* lhs = this->TryFlattenGetString();
+
+  if (StringShape(lhs).IsSequentialAscii()) {
+      const char* str1 = SeqAsciiString::cast(lhs)->GetChars();
+      return CompareRawStringContents(Vector<const char>(str1, len),
+                                      Vector<const char>(string, len));
+  }
+
+  if (lhs->IsFlat()) {
+    String::FlatContent lhs_content = lhs->GetFlatContent();
+    Vector<const uc16> vec1 = lhs_content.ToUC16Vector();
+    VectorIterator<const uc16> buf1(vec1);
+    VectorIterator<char> buf2(string, length);
+    return CompareStringContents(&buf1, &buf2);
+  } else {
+    Isolate* isolate = GetIsolate();
+    isolate->objects_string_compare_buffer_a()->Reset(0, lhs);
+    VectorIterator<char> ib(string, length);
+    return CompareStringContents(isolate->objects_string_compare_buffer_a(),
+                                 &ib);
+  }
+}
+
+
 bool String::SlowEquals(String* other) {
   // Fast check: negative check with lengths.
   int len = length();
@@ -11565,9 +11631,27 @@ class AsciiSymbolKey : public SequentialSymbolKey<char> {
 
   MaybeObject* AsObject() {
     if (hash_field_ == 0) Hash();
-    return HEAP->AllocateAsciiSymbol(string_, hash_field_);
+    MaybeObject *result = HEAP->AllocateAsciiSymbol(string_, hash_field_);
+    if (!result->IsFailure() && result->ToObjectUnchecked()->IsSeqString()) {
+        while (true) {
+            Atomic32 my_symbol_id = next_symbol_id;
+            if (my_symbol_id > Smi::kMaxValue)
+                break;
+            if (my_symbol_id == NoBarrier_CompareAndSwap(&next_symbol_id,
+                                                         my_symbol_id,
+                                                         my_symbol_id + 1)) {
+                SeqString::cast(result->ToObjectUnchecked())->
+                    set_symbol_id(my_symbol_id);
+                break;
+            }
+        }
+    }
+    return result;
   }
+
+  static Atomic32 next_symbol_id;
 };
+Atomic32 AsciiSymbolKey::next_symbol_id = 1;
 
 
 class SubStringAsciiSymbolKey : public HashTableKey {
diff --git a/src/3rdparty/v8/src/objects.h b/src/3rdparty/v8/src/objects.h
index c86c0b2..9e45a72 100644
--- a/src/3rdparty/v8/src/objects.h
+++ b/src/3rdparty/v8/src/objects.h
@@ -7318,6 +7318,9 @@ class String: public HeapObject {
   bool IsAsciiEqualTo(Vector<const char> str);
   bool IsTwoByteEqualTo(Vector<const uc16> str);
 
+  bool SlowEqualsExternal(uc16 *string, int length);
+  bool SlowEqualsExternal(char *string, int length);
+
   // Return a UTF8 representation of the string.  The string is null
   // terminated but may optionally contain nulls.  Length is returned
   // in length_output if length_output is not a null pointer  The string
@@ -7587,8 +7590,13 @@ class SeqString: public String {
   // Casting.
   static inline SeqString* cast(Object* obj);
 
+  // Get and set the symbol id of the string
+  inline int symbol_id();
+  inline void set_symbol_id(int value);
+
   // Layout description.
-  static const int kHeaderSize = String::kSize;
+  static const int kSymbolIdOffset = String::kSize;
+  static const int kHeaderSize = kSymbolIdOffset + kPointerSize;
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(SeqString);