Backport hash collision workaround to 3.6.

src/objects.cc

 // Copyright 2011 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 5908 matching lines @@
 
 bool String::SlowEquals(String* other) {
   // Fast check: negative check with lengths.
   int len = length();
   if (len != other->length()) return false;
   if (len == 0) return true;
 
   // Fast check: if hash code is computed for both strings
   // a fast negative check can be performed.
   if (HasHashCode() && other->HasHashCode()) {
+#ifdef DEBUG
+    if (FLAG_enable_slow_asserts) {
+      if (Hash() != other->Hash()) {
+        bool found_difference = false;
+        for (int i = 0; i < len; i++) {
+          if (Get(i) != other->Get(i)) {
+            found_difference = true;
+            break;
+          }
+        }
+        ASSERT(found_difference);
+      }
+    }
+#endif
     if (Hash() != other->Hash()) return false;
   }
 
   // We know the strings are both non-empty. Compare the first chars
   // before we try to flatten the strings.
   if (this->Get(0) != other->Get(0)) return false;
 
   String* lhs = this->TryFlattenGetString();
   String* rhs = other->TryFlattenGetString();
 
@@ skipping 115 matching lines @@
 
 uint32_t String::ComputeAndSetHash() {
   // Should only be called if hash code has not yet been computed.
   ASSERT(!HasHashCode());
 
   const int len = length();
 
   // Compute the hash code.
   uint32_t field = 0;
   if (StringShape(this).IsSequentialAscii()) {
-    field = HashSequentialString(SeqAsciiString::cast(this)->GetChars(), len);
+    field = HashSequentialString(SeqAsciiString::cast(this)->GetChars(),
+                                 len,
+                                 GetHeap()->StringHashSeed());
   } else if (StringShape(this).IsSequentialTwoByte()) {
-    field = HashSequentialString(SeqTwoByteString::cast(this)->GetChars(), len);
+    field = HashSequentialString(SeqTwoByteString::cast(this)->GetChars(),
+                                 len,
+                                 GetHeap()->StringHashSeed());
   } else {
     StringInputBuffer buffer(this);
-    field = ComputeHashField(&buffer, len);
+    field = ComputeHashField(&buffer, len, GetHeap()->StringHashSeed());
   }
 
   // Store the hash code in the object.
   set_hash_field(field);
 
   // Check the hash code is there.
   ASSERT(HasHashCode());
   uint32_t result = field >> kHashShift;
   ASSERT(result != 0);  // Ensure that the hash value of 0 is never computed.
   return result;
@@ skipping 70 matching lines @@
       return MakeArrayIndexHash(array_index(), length_);
     }
     return (GetHash() << String::kHashShift) | String::kIsNotArrayIndexMask;
   } else {
     return (length_ << String::kHashShift) | String::kIsNotArrayIndexMask;
   }
 }
 
 
 uint32_t String::ComputeHashField(unibrow::CharacterStream* buffer,
-                                  int length) {
-  StringHasher hasher(length);
+                                  int length,
+                                  uint32_t seed) {
+  StringHasher hasher(length, seed);
 
   // Very long strings have a trivial hash that doesn't inspect the
   // string contents.
   if (hasher.has_trivial_hash()) {
     return hasher.GetHashField();
   }
 
   // Do the iterative array index computation as long as there is a
   // chance this is an array index.
   while (buffer->has_more() && hasher.is_array_index()) {
@@ skipping 3363 matching lines @@
     return string->Hash() + flags->value();
   }
 
   String* string_;
   Smi* flags_;
 };
 
 // Utf8SymbolKey carries a vector of chars as key.
 class Utf8SymbolKey : public HashTableKey {
  public:
-  explicit Utf8SymbolKey(Vector<const char> string)
-      : string_(string), hash_field_(0) { }
+  explicit Utf8SymbolKey(Vector<const char> string, uint32_t seed)
+      : string_(string), hash_field_(0), seed_(seed) { }
 
   bool IsMatch(Object* string) {
     return String::cast(string)->IsEqualTo(string_);
   }
 
   uint32_t Hash() {
     if (hash_field_ != 0) return hash_field_ >> String::kHashShift;
     unibrow::Utf8InputBuffer<> buffer(string_.start(),
                                       static_cast<unsigned>(string_.length()));
     chars_ = buffer.Length();
-    hash_field_ = String::ComputeHashField(&buffer, chars_);
+    hash_field_ = String::ComputeHashField(&buffer, chars_, seed_);
     uint32_t result = hash_field_ >> String::kHashShift;
     ASSERT(result != 0);  // Ensure that the hash value of 0 is never computed.
     return result;
   }
 
   uint32_t HashForObject(Object* other) {
     return String::cast(other)->Hash();
   }
 
   MaybeObject* AsObject() {
     if (hash_field_ == 0) Hash();
     return Isolate::Current()->heap()->AllocateSymbol(
         string_, chars_, hash_field_);
   }
 
   Vector<const char> string_;
   uint32_t hash_field_;
   int chars_;  // Caches the number of characters when computing the hash code.
+  uint32_t seed_;
 };
 
 
 template <typename Char>
 class SequentialSymbolKey : public HashTableKey {
  public:
-  explicit SequentialSymbolKey(Vector<const Char> string)
-      : string_(string), hash_field_(0) { }
+  explicit SequentialSymbolKey(Vector<const Char> string, uint32_t seed)
+      : string_(string), hash_field_(0), seed_(seed) { }
 
   uint32_t Hash() {
-    StringHasher hasher(string_.length());
+    StringHasher hasher(string_.length(), seed_);
 
     // Very long strings have a trivial hash that doesn't inspect the
     // string contents.
     if (hasher.has_trivial_hash()) {
       hash_field_ = hasher.GetHashField();
     } else {
       int i = 0;
       // Do the iterative array index computation as long as there is a
       // chance this is an array index.
       while (i < string_.length() && hasher.is_array_index()) {
@@ skipping 15 matching lines @@
     return result;
   }
 
 
   uint32_t HashForObject(Object* other) {
     return String::cast(other)->Hash();
   }
 
   Vector<const Char> string_;
   uint32_t hash_field_;
+  uint32_t seed_;
 };
 
 
 
 class AsciiSymbolKey : public SequentialSymbolKey<char> {
  public:
-  explicit AsciiSymbolKey(Vector<const char> str)
-      : SequentialSymbolKey<char>(str) { }
+  AsciiSymbolKey(Vector<const char> str, uint32_t seed)
+      : SequentialSymbolKey<char>(str, seed) { }
 
   bool IsMatch(Object* string) {
     return String::cast(string)->IsAsciiEqualTo(string_);
   }
 
   MaybeObject* AsObject() {
     if (hash_field_ == 0) Hash();
     return HEAP->AllocateAsciiSymbol(string_, hash_field_);
   }
 };
 
 
 class SubStringAsciiSymbolKey : public HashTableKey {
  public:
   explicit SubStringAsciiSymbolKey(Handle<SeqAsciiString> string,
                                    int from,
-                                   int length)
-      : string_(string), from_(from), length_(length) { }
+                                   int length,
+                                   uint32_t seed)
+      : string_(string), from_(from), length_(length), seed_(seed) { }
 
   uint32_t Hash() {
     ASSERT(length_ >= 0);
     ASSERT(from_ + length_ <= string_->length());
-    StringHasher hasher(length_);
+    StringHasher hasher(length_, string_->GetHeap()->StringHashSeed());
 
     // Very long strings have a trivial hash that doesn't inspect the
     // string contents.
     if (hasher.has_trivial_hash()) {
       hash_field_ = hasher.GetHashField();
     } else {
       int i = 0;
       // Do the iterative array index computation as long as there is a
       // chance this is an array index.
       while (i < length_ && hasher.is_array_index()) {
@@ skipping 31 matching lines @@
     if (hash_field_ == 0) Hash();
     Vector<const char> chars(string_->GetChars() + from_, length_);
     return HEAP->AllocateAsciiSymbol(chars, hash_field_);
   }
 
  private:
   Handle<SeqAsciiString> string_;
   int from_;
   int length_;
   uint32_t hash_field_;
+  uint32_t seed_;
 };
 
 
 class TwoByteSymbolKey : public SequentialSymbolKey<uc16> {
  public:
-  explicit TwoByteSymbolKey(Vector<const uc16> str)
-      : SequentialSymbolKey<uc16>(str) { }
+  explicit TwoByteSymbolKey(Vector<const uc16> str, uint32_t seed)
+      : SequentialSymbolKey<uc16>(str, seed) { }
 
   bool IsMatch(Object* string) {
     return String::cast(string)->IsTwoByteEqualTo(string_);
   }
 
   MaybeObject* AsObject() {
     if (hash_field_ == 0) Hash();
     return HEAP->AllocateTwoByteSymbol(string_, hash_field_);
   }
 };
@@ skipping 751 matching lines @@
 }
 
 
 // This class is used for looking up two character strings in the symbol table.
 // If we don't have a hit we don't want to waste much time so we unroll the
 // string hash calculation loop here for speed.  Doesn't work if the two
 // characters form a decimal integer, since such strings have a different hash
 // algorithm.
 class TwoCharHashTableKey : public HashTableKey {
  public:
-  TwoCharHashTableKey(uint32_t c1, uint32_t c2)
+  TwoCharHashTableKey(uint32_t c1, uint32_t c2, uint32_t seed)
     : c1_(c1), c2_(c2) {
     // Char 1.
-    uint32_t hash = c1 + (c1 << 10);
+    uint32_t hash = seed;
+    hash += c1;
+    hash += hash << 10;
     hash ^= hash >> 6;
     // Char 2.
     hash += c2;
     hash += hash << 10;
     hash ^= hash >> 6;
     // GetHash.
     hash += hash << 3;
     hash ^= hash >> 11;
     hash += hash << 15;
-    if (hash == 0) hash = 27;
+    if ((hash & String::kHashBitMask) == 0) hash = 27;
 #ifdef DEBUG
-    StringHasher hasher(2);
+    StringHasher hasher(2, seed);
     hasher.AddCharacter(c1);
     hasher.AddCharacter(c2);
     // If this assert fails then we failed to reproduce the two-character
     // version of the string hashing algorithm above.  One reason could be
     // that we were passed two digits as characters, since the hash
     // algorithm is different in that case.
     ASSERT_EQ(static_cast<int>(hasher.GetHash()), static_cast<int>(hash));
 #endif
     hash_ = hash;
   }
@@ skipping 36 matching lines @@
     ASSERT(StringShape(result).IsSymbol());
     *symbol = result;
     return true;
   }
 }
 
 
 bool SymbolTable::LookupTwoCharsSymbolIfExists(uint32_t c1,
                                                uint32_t c2,
                                                String** symbol) {
-  TwoCharHashTableKey key(c1, c2);
+  TwoCharHashTableKey key(c1, c2, GetHeap()->StringHashSeed());
   int entry = FindEntry(&key);
   if (entry == kNotFound) {
     return false;
   } else {
     String* result = String::cast(KeyAt(entry));
     ASSERT(StringShape(result).IsSymbol());
     *symbol = result;
     return true;
   }
 }
 
 
-MaybeObject* SymbolTable::LookupSymbol(Vector<const char> str, Object** s) {
-  Utf8SymbolKey key(str);
+MaybeObject* SymbolTable::LookupSymbol(Vector<const char> str,
+                                       Object** s) {
+  Utf8SymbolKey key(str, GetHeap()->StringHashSeed());
   return LookupKey(&key, s);
 }
 
 
 MaybeObject* SymbolTable::LookupAsciiSymbol(Vector<const char> str,
                                             Object** s) {
-  AsciiSymbolKey key(str);
+  AsciiSymbolKey key(str, GetHeap()->StringHashSeed());
   return LookupKey(&key, s);
 }
 
 
 MaybeObject* SymbolTable::LookupSubStringAsciiSymbol(Handle<SeqAsciiString> str,
                                                      int from,
                                                      int length,
                                                      Object** s) {
-  SubStringAsciiSymbolKey key(str, from, length);
+  SubStringAsciiSymbolKey key(str, from, length, GetHeap()->StringHashSeed());
   return LookupKey(&key, s);
 }
 
 
 MaybeObject* SymbolTable::LookupTwoByteSymbol(Vector<const uc16> str,
                                               Object** s) {
-  TwoByteSymbolKey key(str);
+  TwoByteSymbolKey key(str, GetHeap()->StringHashSeed());
   return LookupKey(&key, s);
 }
 
 MaybeObject* SymbolTable::LookupKey(HashTableKey* key, Object** s) {
   int entry = FindEntry(key);
 
   // Symbol already in table.
   if (entry != kNotFound) {
     *s = KeyAt(entry);
     return this;
@@ skipping 996 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single break point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal