Tree shaker:

runtime/vm/object.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/become.h"
@@ skipping 10214 matching lines @@
       Isolate::Current()->object_store()->libraries());
   Library& lib = Library::Handle();
   intptr_t num_libs = libs.Length();
   for (intptr_t i = 0; i < num_libs; i++) {
     lib ^= libs.At(i);
     lib.ClearExportedNamesCache();
   }
 }
 
 
-void Library::GrowDictionary(const Array& dict, intptr_t dict_size) const {
-  // TODO(iposva): Avoid exponential growth.
-  intptr_t new_dict_size = dict_size * 2;
+void Library::RehashDictionary(const Array& old_dict,
+                               intptr_t new_dict_size) const {
+  intptr_t old_dict_size = old_dict.Length() - 1;
   const Array& new_dict =
       Array::Handle(Array::New(new_dict_size + 1, Heap::kOld));
   // Rehash all elements from the original dictionary
   // to the newly allocated array.
   Object& entry = Class::Handle();
   String& entry_name = String::Handle();
   Object& new_entry = Object::Handle();
-  for (intptr_t i = 0; i < dict_size; i++) {
-    entry = dict.At(i);
+  intptr_t used = 0;
+  for (intptr_t i = 0; i < old_dict_size; i++) {
+    entry = old_dict.At(i);
     if (!entry.IsNull()) {
       entry_name = entry.DictionaryName();
       ASSERT(!entry_name.IsNull());
       const intptr_t hash = entry_name.Hash();
       intptr_t index = hash % new_dict_size;
       new_entry = new_dict.At(index);
       while (!new_entry.IsNull()) {
         index = (index + 1) % new_dict_size;  // Move to next element.
         new_entry = new_dict.At(index);
       }
       new_dict.SetAt(index, entry);
+      used++;
     }
   }
-  // Copy used count.
-  new_entry = dict.At(dict_size);
+  // Set used count.
+  ASSERT(used < new_dict_size);  // Need at least one empty slot.
+  new_entry = Smi::New(used);
   new_dict.SetAt(new_dict_size, new_entry);
   // Remember the new dictionary now.
   StorePointer(&raw_ptr()->dictionary_, new_dict.raw());
 }
 
 
 void Library::AddObject(const Object& obj, const String& name) const {
   ASSERT(Thread::Current()->IsMutatorThread());
   ASSERT(obj.IsClass() || obj.IsFunction() || obj.IsField() ||
          obj.IsLibraryPrefix());
@@ skipping 13 matching lines @@
 
   // Insert the object at the empty slot.
   dict.SetAt(index, obj);
   // One more element added.
   intptr_t used_elements = Smi::Value(Smi::RawCast(dict.At(dict_size))) + 1;
   const Smi& used = Smi::Handle(Smi::New(used_elements));
   dict.SetAt(dict_size, used);  // Update used count.
 
   // Rehash if symbol_table is 75% full.
   if (used_elements > ((dict_size / 4) * 3)) {
-    GrowDictionary(dict, dict_size);
+    // TODO(iposva): Avoid exponential growth.
+    RehashDictionary(dict, 2 * dict_size);
   }
 
   // Invalidate the cache of loaded scripts.
   if (loaded_scripts() != Array::null()) {
     StorePointer(&raw_ptr()->loaded_scripts_, Array::null());
   }
 }
 
 
 // Lookup a name in the library's re-export namespace.
@@ skipping 71 matching lines @@
   ASSERT(LookupLocalObject(name) != Object::null());
 
   intptr_t index;
   LookupEntry(name, &index);
   // The value is guaranteed to be found.
   const Array& dict = Array::Handle(dictionary());
   dict.SetAt(index, obj);
 }
 
 
-bool Library::RemoveObject(const Object& obj, const String& name) const {
-  Thread* thread = Thread::Current();
-  ASSERT(thread->IsMutatorThread());
-  Zone* zone = thread->zone();
-  Object& entry = Object::Handle(zone);
-
-  intptr_t index;
-  entry = LookupEntry(name, &index);
-  if (entry.raw() != obj.raw()) {
-    return false;
-  }
-
-  const Array& dict = Array::Handle(zone, dictionary());
-  dict.SetAt(index, Object::null_object());
-  intptr_t dict_size = dict.Length() - 1;
-
-  // Fix any downstream collisions.
-  String& key = String::Handle(zone);
-  for (;;) {
-    index = (index + 1) % dict_size;
-    entry = dict.At(index);
-
-    if (entry.IsNull()) break;
-
-    key = entry.DictionaryName();
-    intptr_t new_index = key.Hash() % dict_size;
-    while ((dict.At(new_index) != entry.raw()) &&
-           (dict.At(new_index) != Object::null())) {
-      new_index = (new_index + 1) % dict_size;
-    }
-
-    if (index != new_index) {
-      ASSERT(dict.At(new_index) == Object::null());
-      dict.SetAt(new_index, entry);
-      dict.SetAt(index, Object::null_object());
-    }
-  }
-
-  // Update used count.
-  intptr_t used_elements = Smi::Value(Smi::RawCast(dict.At(dict_size))) - 1;
-  dict.SetAt(dict_size, Smi::Handle(zone, Smi::New(used_elements)));
-
-  ClearResolvedNamesCache();
-  InvalidateExportedNamesCaches();
-
-  return true;
-}
-
-
 void Library::AddClass(const Class& cls) const {
   ASSERT(!Compiler::IsBackgroundCompilation());
   const String& class_name = String::Handle(cls.Name());
   AddObject(cls, class_name);
   // Link class to this library.
   cls.set_library(*this);
   InvalidateResolvedName(class_name);
 }
 
 
@@ skipping 338 matching lines @@
       imported = prefix.GetLibrary(i);
       if (imported.IsCoreLibrary()) {
         return true;
       }
     }
   }
   return false;
 }
 
 
-void Library::DropDependencies() const {
+void Library::DropDependenciesAndCaches() const {
   StorePointer(&raw_ptr()->imports_, Object::empty_array().raw());
   StorePointer(&raw_ptr()->exports_, Object::empty_array().raw());
   StoreNonPointer(&raw_ptr()->num_imports_, 0);
+  StorePointer(&raw_ptr()->resolved_names_, Array::null());
+  StorePointer(&raw_ptr()->exported_names_, Array::null());
+  StorePointer(&raw_ptr()->loaded_scripts_, Array::null());
 }
 
 
 void Library::AddImport(const Namespace& ns) const {
   Array& imports = Array::Handle(this->imports());
   intptr_t capacity = imports.Length();
   if (num_imports() == capacity) {
     capacity = capacity + kImportsCapacityIncrement;
     imports = Array::Grow(imports, capacity);
     StorePointer(&raw_ptr()->imports_, imports.raw());
@@ skipping 12375 matching lines @@
   return UserTag::null();
 }
 
 
 const char* UserTag::ToCString() const {
   const String& tag_label = String::Handle(label());
   return tag_label.ToCString();
 }
 
 }  // namespace dart