Replace the use CharacterStreams in Heap::AllocateSymbolInternal and String::ComputeHash

src/objects.cc

 // Copyright 2012 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 7003 matching lines @@
     start_ = content.ToUC16Vector().start();
   }
 }
 
 
 void StringInputBuffer::Seek(unsigned pos) {
   Reset(pos, input_);
 }
 
 
-String* ConsStringIteratorOp::Operate(ConsString* cons_string,
-    unsigned* offset_out, int32_t* type_out, unsigned* length_out) {
-  ASSERT(*length_out == (unsigned)cons_string->length());
-  ASSERT(depth_ == 0);
-  // Push the root string.
-  PushLeft(cons_string);
+String* ConsStringIteratorOp::Operate(String* string,
+                                      unsigned* offset_out,
+                                      int32_t* type_out,
+                                      unsigned* length_out) {
+  ASSERT(string->IsConsString());
+  ConsString* cons_string = ConsString::cast(string);
+  // Set up search data.
   root_ = cons_string;
-  root_type_ = *type_out;
-  root_length_ = *length_out;
   consumed_ = *offset_out;
-  unsigned targetOffset = *offset_out;
+  // Now search.
+  return Search(offset_out, type_out, length_out);
+}
+
+
+String* ConsStringIteratorOp::Search(unsigned* offset_out,
+                                     int32_t* type_out,
+                                     unsigned* length_out) {
+  ConsString* cons_string = root_;
+  // Reset the stack, pushing the root string.
+  depth_ = 1;
+  maximum_depth_ = 1;
+  frames_[0] = cons_string;
+  const unsigned consumed = consumed_;
   unsigned offset = 0;
   while (true) {
     // Loop until the string is found which contains the target offset.
     String* string = cons_string->first();
     unsigned length = string->length();
     int32_t type;
-    if (targetOffset < offset + length) {
+    if (consumed < offset + length) {
       // Target offset is in the left branch.
       // Keep going if we're still in a ConString.
       type = string->map()->instance_type();
       if ((type & kStringRepresentationMask) == kConsStringTag) {
         cons_string = ConsString::cast(string);
         PushLeft(cons_string);
         continue;
       }
       // Tell the stack we're done decending.
       AdjustMaximumDepth();
     } else {
       // Descend right.
       // Update progress through the string.
       offset += length;
       // Keep going if we're still in a ConString.
       string = cons_string->second();
       type = string->map()->instance_type();
       if ((type & kStringRepresentationMask) == kConsStringTag) {
         cons_string = ConsString::cast(string);
         PushRight(cons_string);
         // TODO(dcarney) Add back root optimization.
         continue;
       }
       // Need this to be updated for the current string.
       length = string->length();
       // Account for the possibility of an empty right leaf.
       // This happens only if we have asked for an offset outside the string.
       if (length == 0) {
+        // Reset depth so future operations will return null immediately.
         Reset();
         return NULL;
       }
       // Tell the stack we're done decending.
       AdjustMaximumDepth();
       // Pop stack so next iteration is in correct place.
       Pop();
     }
     ASSERT(length != 0);
     // Adjust return values and exit.
-    unsigned innerOffset = targetOffset - offset;
-    consumed_ += length - innerOffset;
-    *offset_out = innerOffset;
+    consumed_ = offset + length;
+    *offset_out = consumed - offset;
     *type_out = type;
     *length_out = length;
     return string;
   }
   UNREACHABLE();
   return NULL;
 }
 
 
-String* ConsStringIteratorOp::NextLeaf(
-    bool* blew_stack, int32_t* type_out, unsigned* length_out) {
+String* ConsStringIteratorOp::NextLeaf(bool* blew_stack,
+                                       int32_t* type_out,
+                                       unsigned* length_out) {
   while (true) {
     // Tree traversal complete.
     if (depth_ == 0) {
       *blew_stack = false;
       return NULL;
     }
     // We've lost track of higher nodes.
     if (maximum_depth_ - depth_ == kStackSize) {
       *blew_stack = true;
       return NULL;
     }
     // Go right.
     ConsString* cons_string = frames_[OffsetForDepth(depth_ - 1)];
     String* string = cons_string->second();
     int32_t type = string->map()->instance_type();
     if ((type & kStringRepresentationMask) != kConsStringTag) {
       // Pop stack so next iteration is in correct place.
       Pop();
       unsigned length = (unsigned) string->length();
       // Could be a flattened ConsString.
       if (length == 0) continue;
       *length_out = length;
       *type_out = type;
+      consumed_ += length;
       return string;
     }
     cons_string = ConsString::cast(string);
     // TODO(dcarney) Add back root optimization.
     PushRight(cons_string);
     // Need to traverse all the way left.
     while (true) {
       // Continue left.
       string = cons_string->first();
       type = string->map()->instance_type();
       if ((type & kStringRepresentationMask) != kConsStringTag) {
         AdjustMaximumDepth();
+        unsigned length = (unsigned) string->length();
+        ASSERT(length != 0);
+        *length_out = length;
         *type_out = type;
-        *length_out = string->length();
+        consumed_ += length;
         return string;
       }
       cons_string = ConsString::cast(string);
       PushLeft(cons_string);
     }
   }
   UNREACHABLE();
   return NULL;
 }
 
@@ skipping 518 matching lines @@
   if (content.IsTwoByte()) {
     return CompareChars(content.ToUC16Vector().start(), str.start(), slen) == 0;
   }
   for (int i = 0; i < slen; i++) {
     if (Get(i) != str[i]) return false;
   }
   return true;
 }
 
 
+class IteratingStringHasher: public StringHasher {
+ public:
+  static inline uint32_t Hash(String* string, uint32_t seed) {
+    const unsigned len = static_cast<unsigned>(string->length());
+    IteratingStringHasher hasher(len, seed);
+    if (hasher.has_trivial_hash()) {
+      return hasher.GetHashField();
+    }
+    int32_t type = string->map()->instance_type();
+    ConsStringNullOp null_op;
+    String::Visit(string, 0, hasher, null_op, type, len);
+    // Flat strings terminate immediately.
+    if (hasher.consumed_ == len) {
+      ASSERT(!string->IsConsString());
+      return hasher.GetHashField();
+    }
+    ASSERT(string->IsConsString());
+    // This is a ConsString, iterate across it.
+    ConsStringIteratorOp op;
+    unsigned offset = 0;
+    unsigned leaf_length = len;
+    string = op.Operate(string, &offset, &type, &leaf_length);
+    while (true) {
+      ASSERT(hasher.consumed_ < len);
+      String::Visit(string, 0, hasher, null_op, type, leaf_length);
+      if (hasher.consumed_ == len) break;
+      string = op.ContinueOperation(&type, &leaf_length);
+      // This should be taken care of by the length check.
+      ASSERT(string != NULL);
+    }
+    return hasher.GetHashField();
+  }
+  inline void VisitOneByteString(const uint8_t* chars, unsigned length) {
+    AddCharacters(chars, static_cast<int>(length));
+    consumed_ += length;
+  }
+  inline void VisitTwoByteString(const uint16_t* chars, unsigned length) {
+    AddCharacters(chars, static_cast<int>(length));
+    consumed_ += length;
+  }
+
+ private:
+  inline IteratingStringHasher(int len, uint32_t seed)
+    : StringHasher(len, seed),
+      consumed_(0) {}
+  unsigned consumed_;
+  DISALLOW_COPY_AND_ASSIGN(IteratingStringHasher);
+};
+
+
 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(SeqOneByteString::cast(this)->GetChars(),
-                                 len,
-                                 GetHeap()->HashSeed());
-  } else if (StringShape(this).IsSequentialTwoByte()) {
-    field = HashSequentialString(SeqTwoByteString::cast(this)->GetChars(),
-                                 len,
-                                 GetHeap()->HashSeed());
-  } else {
-    StringInputBuffer buffer(this);
-    field = ComputeHashField(&buffer, len, GetHeap()->HashSeed());
-  }
-
   // Store the hash code in the object.
+  uint32_t field = IteratingStringHasher::Hash(this, GetHeap()->HashSeed());
   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 83 matching lines @@
   value <<= String::kHashShift;
   value |= length << String::kArrayIndexHashLengthShift;
 
   ASSERT((value & String::kIsNotArrayIndexMask) == 0);
   ASSERT((length > String::kMaxCachedArrayIndexLength) ||
          (value & String::kContainsCachedArrayIndexMask) == 0);
   return value;
 }
 
 
-void StringHasher::AddSurrogatePair(uc32 c) {
-  uint16_t lead = unibrow::Utf16::LeadSurrogate(c);
-  AddCharacter(lead);
-  uint16_t trail = unibrow::Utf16::TrailSurrogate(c);
-  AddCharacter(trail);
-}
-
-
-void StringHasher::AddSurrogatePairNoIndex(uc32 c) {
-  uint16_t lead = unibrow::Utf16::LeadSurrogate(c);
-  AddCharacterNoIndex(lead);
-  uint16_t trail = unibrow::Utf16::TrailSurrogate(c);
-  AddCharacterNoIndex(trail);
-}
-
-
 uint32_t StringHasher::GetHashField() {
   if (length_ <= String::kMaxHashCalcLength) {
-    if (is_array_index()) {
-      return MakeArrayIndexHash(array_index(), length_);
+    if (is_array_index_) {
+      return MakeArrayIndexHash(array_index_, length_);
     }
-    return (GetHash() << String::kHashShift) | String::kIsNotArrayIndexMask;
+    return (GetHashCore(raw_running_hash_) << String::kHashShift) |
+           String::kIsNotArrayIndexMask;
   } else {
     return (length_ << String::kHashShift) | String::kIsNotArrayIndexMask;
   }
 }
 
 
-uint32_t String::ComputeHashField(unibrow::CharacterStream* buffer,
-                                  int length,
-                                  uint32_t seed) {
+uint32_t StringHasher::ComputeHashField(unibrow::CharacterStream* buffer,
+                                        int length,
+                                        uint32_t seed) {
+  typedef unibrow::Utf16 u;
   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()) {
-    hasher.AddCharacter(buffer->GetNext());
+  if (hasher.is_array_index_) {
+    while (buffer->has_more()) {
+      uint32_t c = buffer->GetNext();
+      if (c > u::kMaxNonSurrogateCharCode) {
+        uint16_t c1 = u::LeadSurrogate(c);
+        uint16_t c2 = u::TrailSurrogate(c);
+        hasher.AddCharacter(c1);
+        hasher.AddCharacter(c2);
+        if (!hasher.UpdateIndex(c1)) break;
+        if (!hasher.UpdateIndex(c2)) break;
+      } else {
+        hasher.AddCharacter(c);
+        if (!hasher.UpdateIndex(c)) break;
+      }
+    }
   }
-
   // Process the remaining characters without updating the array
   // index.
   while (buffer->has_more()) {
-    hasher.AddCharacterNoIndex(buffer->GetNext());
+    ASSERT(!hasher.is_array_index_);
+    uint32_t c = buffer->GetNext();
+    if (c > u::kMaxNonSurrogateCharCode) {
+      hasher.AddCharacter(u::LeadSurrogate(c));
+      hasher.AddCharacter(u::TrailSurrogate(c));
+    } else {
+      hasher.AddCharacter(c);
+    }
   }
-
   return hasher.GetHashField();
 }
 
 
 MaybeObject* String::SubString(int start, int end, PretenureFlag pretenure) {
   Heap* heap = GetHeap();
   if (start == 0 && end == length()) return this;
   MaybeObject* result = heap->AllocateSubString(this, start, end, pretenure);
   return result;
 }
@@ skipping 3790 matching lines @@
 
   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.Utf16Length();
-    hash_field_ = String::ComputeHashField(&buffer, chars_, seed_);
+    hash_field_ = StringHasher::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, uint32_t seed)
       : string_(string), hash_field_(0), seed_(seed) { }
 
   uint32_t Hash() {
-    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()) {
-        hasher.AddCharacter(static_cast<uc32>(string_[i]));
-        i++;
-      }
-
-      // Process the remaining characters without updating the array
-      // index.
-      while (i < string_.length()) {
-        hasher.AddCharacterNoIndex(static_cast<uc32>(string_[i]));
-        i++;
-      }
-      hash_field_ = hasher.GetHashField();
-    }
+    hash_field_ = StringHasher::HashSequentialString<Char>(string_.start(),
+                                                           string_.length(),
+                                                           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();
   }
@@ skipping 24 matching lines @@
 class SubStringAsciiSymbolKey : public HashTableKey {
  public:
   explicit SubStringAsciiSymbolKey(Handle<SeqOneByteString> string,
                                    int from,
                                    int length)
       : string_(string), from_(from), length_(length) { }
 
   uint32_t Hash() {
     ASSERT(length_ >= 0);
     ASSERT(from_ + length_ <= string_->length());
-    StringHasher hasher(length_, string_->GetHeap()->HashSeed());
-
-    // 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()) {
-        hasher.AddCharacter(static_cast<uc32>(
-            string_->SeqOneByteStringGet(i + from_)));
-        i++;
-      }
-
-      // Process the remaining characters without updating the array
-      // index.
-      while (i < length_) {
-        hasher.AddCharacterNoIndex(static_cast<uc32>(
-            string_->SeqOneByteStringGet(i + from_)));
-        i++;
-      }
-      hash_field_ = hasher.GetHashField();
-    }
-
+    char* chars = string_->GetChars() + from_;
+    hash_field_ = StringHasher::HashSequentialString(
+        chars, length_, string_->GetHeap()->HashSeed());
     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();
   }
 
@@ skipping 54 matching lines @@
     string_ = string_->TryFlattenGetString();
     Heap* heap = string_->GetHeap();
     // Transform string to symbol if possible.
     Map* map = heap->SymbolMapForString(string_);
     if (map != NULL) {
       string_->set_map_no_write_barrier(map);
       ASSERT(string_->IsSymbol());
       return string_;
     }
     // Otherwise allocate a new symbol.
-    StringInputBuffer buffer(string_);
-    return heap->AllocateInternalSymbol(&buffer,
+    return heap->AllocateInternalSymbol(string_,
                                         string_->length(),
                                         string_->hash_field());
   }
 
   static uint32_t StringHash(Object* obj) {
     return String::cast(obj)->Hash();
   }
 
   String* string_;
 };
@@ skipping 749 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, uint32_t seed)
+  TwoCharHashTableKey(uint16_t c1, uint16_t c2, uint32_t seed)
     : c1_(c1), c2_(c2) {
     // Char 1.
     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 & String::kHashBitMask) == 0) hash = StringHasher::kZeroHash;
+    hash_ = hash;
 #ifdef DEBUG
-    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));
+    uint16_t chars[2] = {c1, c2};
+    uint32_t check_hash = StringHasher::HashSequentialString(chars, 2, seed);
+    hash = (hash << String::kHashShift) | String::kIsNotArrayIndexMask;
+    ASSERT_EQ(static_cast<int32_t>(hash), static_cast<int32_t>(check_hash));
 #endif
-    hash_ = hash;
   }
 
   bool IsMatch(Object* o) {
     if (!o->IsString()) return false;
     String* other = String::cast(o);
     if (other->length() != 2) return false;
     if (other->Get(0) != c1_) return false;
     return other->Get(1) == c2_;
   }
 
   uint32_t Hash() { return hash_; }
   uint32_t HashForObject(Object* key) {
     if (!key->IsString()) return 0;
     return String::cast(key)->Hash();
   }
 
   Object* AsObject() {
     // The TwoCharHashTableKey is only used for looking in the symbol
     // table, not for adding to it.
     UNREACHABLE();
     return NULL;
   }
 
  private:
-  uint32_t c1_;
-  uint32_t c2_;
+  uint16_t c1_;
+  uint16_t c2_;
   uint32_t hash_;
 };
 
 
 bool SymbolTable::LookupSymbolIfExists(String* string, String** symbol) {
   SymbolKey key(string);
   int entry = FindEntry(&key);
   if (entry == kNotFound) {
     return false;
   } else {
     String* result = String::cast(KeyAt(entry));
     ASSERT(StringShape(result).IsSymbol());
     *symbol = result;
     return true;
   }
 }
 
 
-bool SymbolTable::LookupTwoCharsSymbolIfExists(uint32_t c1,
-                                               uint32_t c2,
+bool SymbolTable::LookupTwoCharsSymbolIfExists(uint16_t c1,
+                                               uint16_t c2,
                                                String** symbol) {
   TwoCharHashTableKey key(c1, c2, GetHeap()->HashSeed());
   int entry = FindEntry(&key);
   if (entry == kNotFound) {
     return false;
   } else {
     String* result = String::cast(KeyAt(entry));
     ASSERT(StringShape(result).IsSymbol());
     *symbol = result;
     return true;
@@ skipping 1321 matching lines @@
   set_year(Smi::FromInt(year), SKIP_WRITE_BARRIER);
   set_month(Smi::FromInt(month), SKIP_WRITE_BARRIER);
   set_day(Smi::FromInt(day), SKIP_WRITE_BARRIER);
   set_weekday(Smi::FromInt(weekday), SKIP_WRITE_BARRIER);
   set_hour(Smi::FromInt(hour), SKIP_WRITE_BARRIER);
   set_min(Smi::FromInt(min), SKIP_WRITE_BARRIER);
   set_sec(Smi::FromInt(sec), SKIP_WRITE_BARRIER);
 }
 
 } }  // namespace v8::internal