WIP: Parser: delay string internalization.

src/parser-symbol-table.cc

+// Copyright 2014 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
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include "parser-symbol-table.h"
+
+#include "api.h"
+#include "objects.h"
+
+namespace v8 {
+namespace internal {
+
+namespace {
+
+template <typename Char>
+int vector_hash(Vector<const Char> string) {
+  int hash = 0;
+  for (int i = 0; i < string.length(); i++) {
+    int c = static_cast<int>(string[i]);
+    hash += c;
+    hash += (hash << 10);
+    hash ^= (hash >> 6);
+  }
+  return hash;
+}
+
+
+bool vector_compare(void* a, void* b) {
+  ParserSymbolTable::Symbol* string1 =
+      reinterpret_cast<ParserSymbolTable::Symbol*>(a);
+  ParserSymbolTable::Symbol* string2 =
+      reinterpret_cast<ParserSymbolTable::Symbol*>(b);
+  if (string1->is_one_byte != string2->is_one_byte) return false;
+  if (string1->hash != string2->hash) return false;

[ulan, 2014/05/21 15:01:22]

I think HashMap guarantees that the hashes are equal upon calling this function.

[marja, 2014/05/21 17:16:45]

Actually, not. Turns out this case is sometimes hit. (We might bucket elements
with different hash functions together. Which is good. We don't want to have a
2^32 element hash array or anything like that.)

+  int length = string1->literal_bytes.length();
+  if (string2->literal_bytes.length() != length) return false;
+  return memcmp(string1->literal_bytes.start(),
+                string2->literal_bytes.start(), length) == 0;
+}
+
+}
+
+
+ParserSymbolTable::ParserSymbolTable()
+    : literal_chars_(0),
+      symbol_keys_(0),
+      string_table_(vector_compare),
+      isolate_(NULL) {
+  {

[ulan, 2014/05/21 15:01:22]

How about second order macro for this? :)

+    const char* data = "(anonymous function)";
+    anonymous_function_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 20));
+  }
+  {
+    const char* data = "arguments";
+    arguments_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 9));
+  }
+  {
+    const char* data = ".for";
+    dot_for_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 4));
+  }
+  {
+    const char* data = ".iterator";
+    dot_iterator_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 9));
+  }
+  {
+    const char* data = ".module";
+    dot_module_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 7));
+  }
+  {
+    const char* data = ".result";
+    dot_result_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 7));
+  }
+  {
+    const char* data = "";
+    empty_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 0));
+  }
+  {
+    const char* data = "eval";
+    eval_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 4));
+  }
+  {
+    const char* data = "InitializeConstGlobal";
+    initialize_const_global_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 21));
+  }
+  {
+    const char* data = "InitializeVarGlobal";
+    initialize_var_global_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 19));
+  }
+  {
+    const char* data = "MakeReferenceError";
+    make_reference_error_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 18));
+  }
+  {
+    const char* data = "MakeSyntaxError";
+    make_syntax_error_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 15));
+  }
+  {
+    const char* data = "MakeTypeError";
+    make_type_error_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 13));
+  }
+  {
+    const char* data = "module";
+    module_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 6));
+  }
+  {
+    const char* data = "native";
+    native_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 6));
+  }
+  {
+    const char* data = "prototype";
+    prototype_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 9));
+  }
+  {
+    const char* data = "this";
+    this_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 4));
+  }
+  {
+    const char* data = "use strict";
+    use_strict_string_ = GetOneByteSymbol(
+        Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), 10));
+  }
+}
+
+
+ParserSymbolTable::Symbol* ParserSymbolTable::GetOneByteSymbol(
+    Vector<const uint8_t> literal) {
+  return GetSymbol(vector_hash(literal), true, literal);
+}
+
+
+ParserSymbolTable::Symbol* ParserSymbolTable::GetTwoByteSymbol(
+    Vector<const uint16_t> literal) {
+  return GetSymbol(vector_hash(literal), false,
+                   Vector<const byte>::cast(literal));
+}
+
+
+ParserSymbolTable::Symbol* ParserSymbolTable::GetSymbol(
+    Handle<String> literal) {
+  DisallowHeapAllocation no_gc;
+  String::FlatContent content = literal->GetFlatContent();
+  if (content.IsAscii()) {
+    return GetOneByteSymbol(content.ToOneByteVector());
+  }
+  ASSERT(content.IsTwoByte());
+  return GetTwoByteSymbol(content.ToUC16Vector());
+}
+
+
+bool ParserSymbolTable::SymbolMatches(Symbol* symbol, const char* data,
+                                      int length) {
+  if (symbol != NULL && symbol->is_one_byte &&
+      symbol->literal_bytes.length() == length) {
+    const char* token =
+        reinterpret_cast<const char*>(symbol->literal_bytes.start());
+    return !strncmp(token, data, length);
+  }
+  return false;
+}
+
+
+void ParserSymbolTable::Internalize(Isolate* isolate) {
+  for (HashMap::Entry* p = string_table_.Start(); p != NULL;
+       p = string_table_.Next(p)) {
+    ParserSymbolTable::Symbol* symbol =
+        reinterpret_cast<ParserSymbolTable::Symbol*>(p->key);
+    Internalize(symbol, isolate);
+  }
+  // FIXME: can we free the backing store now? Maybe not.
+  isolate_ = isolate;
+}
+
+
+bool ParserSymbolTable::IsArrayIndexSlow(Symbol* symbol, uint32_t* index) {
+  ASSERT(symbol != NULL);
+  if (!symbol->is_one_byte) return false;
+  if (symbol->literal_bytes.length() == 0 ||
+      symbol->literal_bytes.length() > String::kMaxArrayIndexSize)
+    return false;
+
+  uint16_t ch = symbol->literal_bytes.at(0);
+  // If the string begins with a '0' character, it must only consist
+  // of it to be a legal array index.
+  if (ch == '0') {
+    if (index != NULL) *index = 0;
+    return symbol->literal_bytes.length() == 1;
+  }
+
+  int d = ch - '0';
+  if (d < 0 || d > 9) return false;
+  uint32_t result = d;
+  for (int i = 1; i < symbol->literal_bytes.length(); ++i) {
+    d = symbol->literal_bytes.at(i) - '0';
+    if (d < 0 || d > 9) return false;
+    // Check that the new result is below the 32 bit limit.
+    if (result > 429496729U - ((d > 5) ? 1 : 0)) return false;
+    result = (result * 10) + d;
+  }
+  if (index != NULL) *index = result;
+  return true;
+}
+
+
+ParserSymbolTable::Symbol* ParserSymbolTable::GetSymbol(
+    int hash, bool is_one_byte, Vector<const byte> literal_bytes) {
+  // literal_bytes here points to whatever the user passed, and this is OK
+  // because we use vector_compare (which checks the contents) to compare
+  // against the Symbols which are in the string_table_. We should not return
+  // this Symbol.
+  Symbol key(is_one_byte, literal_bytes, hash);
+  HashMap::Entry* entry = string_table_.Lookup(&key, hash, true);
+  if (entry->value == NULL) {
+    // Copy literal contents for later comparison.
+    key.literal_bytes =
+        Vector<const byte>::cast(literal_chars_.AddBlock(literal_bytes));
+    // This Vector will be valid as long as the Collector is alive (meaning that
+    // the Symbol will not be moved).
+    Vector<Symbol> symbol = symbol_keys_.AddBlock(1, key);
+    entry->key = &symbol[0];
+    if (isolate_) {
+      Internalize(&symbol[0], isolate_);
+    }
+    entry->value = reinterpret_cast<void*>(1);
+  }
+  return reinterpret_cast<Symbol*>(entry->key);
+}
+
+
+void ParserSymbolTable::Internalize(ParserSymbolTable::Symbol* symbol, Isolate* isolate) {
+  ASSERT(symbol != NULL);
+  if (symbol->literal_bytes.length() == 0) {
+    symbol->string_ = isolate->factory()->empty_string();
+  }
+  else if (symbol->is_one_byte) {
+    symbol->string_ = isolate->factory()->InternalizeOneByteString(symbol->literal_bytes);
+  } else {
+    symbol->string_ = isolate->factory()->InternalizeTwoByteString(
+        Vector<const uint16_t>::cast(symbol->literal_bytes));
+  }
+}
+
+
+} }  // namespace v8::internal