Add a first class GrowableObjectArray type in the VM and use it internally in the VM at all spots w…

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 "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/bigint_operations.h"
 #include "vm/bootstrap.h"
@@ skipping 426 matching lines @@
   cls.set_type_arguments_instance_field_offset(Array::type_arguments_offset());
 
   Array& empty_array = Array::Handle();
   empty_array = Array::New(0, Heap::kOld);
   object_store->set_empty_array(empty_array);
 
   // Re-initialize fields of the array class now that the empty array
   // has been created.
   cls.InitEmptyFields();
 
+  // Set up the growable object array class (Has to be done after the array
+  // class is setup as one of its field is an array object).
+  cls = Class::New<GrowableObjectArray>();
+  object_store->set_growable_object_array_class(cls);
+
   // Setup the symbol table used within the String class.
   const int kInitialSymbolTableSize = 16;
   array = Array::New(kInitialSymbolTableSize + 1);
   // Last element contains the count of used slots.
   array.SetAt(kInitialSymbolTableSize, Smi::Handle(Smi::New(0)));
   object_store->set_symbol_table(array);
 
   // canonical_type_arguments_ are NULL terminated.
   array = Array::New(4);
   object_store->set_canonical_type_arguments(array);
 
   // Pre-allocate the OneByteString class needed by the symbol table.
   cls = Class::New<OneByteString>();
   object_store->set_one_byte_string_class(cls);
 
   // Basic infrastructure has been setup, initialize the class dictionary.
   Library::InitCoreLibrary(isolate);
   Library& core_lib = Library::Handle(Library::CoreLibrary());
   ASSERT(!core_lib.IsNull());
   Library& core_impl_lib = Library::Handle(Library::CoreImplLibrary());
   ASSERT(!core_impl_lib.IsNull());
 
-  object_store->set_pending_classes(Array::Handle(Array::Empty()));
+  const GrowableObjectArray& pending_classes =
+      GrowableObjectArray::Handle(GrowableObjectArray::New(Heap::kOld));
+  object_store->set_pending_classes(pending_classes);
 
   Context& context = Context::Handle(Context::New(0));
   object_store->set_empty_context(context);
 
   // Now that the symbol table is initialized and that the core dictionary as
   // well as the core implementation dictionary have been setup, preallocate
   // remaining classes and register them by name in the dictionaries.
   const Script& impl_script = Script::Handle(Bootstrap::LoadImplScript());
-  GrowableArray<const Class*> pending_classes;
 
   cls = Class::New<Smi>();
   object_store->set_smi_class(cls);
   RegisterClass(cls, "Smi", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<Mint>();
   object_store->set_mint_class(cls);
   RegisterClass(cls, "Mint", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<Bigint>();
   object_store->set_bigint_class(cls);
   RegisterClass(cls, "Bigint", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<Double>();
   object_store->set_double_class(cls);
   RegisterClass(cls, "Double", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<Bool>();
   object_store->set_bool_class(cls);
   RegisterClass(cls, "Bool", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = object_store->array_class();  // Was allocated above.
   RegisterClass(cls, "ObjectArray", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<ImmutableArray>();
   object_store->set_immutable_array_class(cls);
   cls.set_type_arguments_instance_field_offset(Array::type_arguments_offset());
   ASSERT(object_store->immutable_array_class() != object_store->array_class());
   RegisterClass(cls, "ImmutableArray", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = object_store->one_byte_string_class();  // Was allocated above.
   RegisterClass(cls, "OneByteString", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<TwoByteString>();
   object_store->set_two_byte_string_class(cls);
   RegisterClass(cls, "TwoByteString", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<FourByteString>();
   object_store->set_four_byte_string_class(cls);
   RegisterClass(cls, "FourByteString", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<ExternalOneByteString>();
   object_store->set_external_one_byte_string_class(cls);
   RegisterClass(cls, "ExternalOneByteString", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<ExternalTwoByteString>();
   object_store->set_external_two_byte_string_class(cls);
   RegisterClass(cls, "ExternalTwoByteString", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<ExternalFourByteString>();
   object_store->set_external_four_byte_string_class(cls);
   RegisterClass(cls, "ExternalFourByteString", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   cls = Class::New<Stacktrace>();
   object_store->set_stacktrace_class(cls);
   RegisterClass(cls, "Stacktrace", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   // Super type set below, after Object is allocated.
 
   cls = Class::New<JSRegExp>();
   object_store->set_jsregexp_class(cls);
   RegisterClass(cls, "JSSyntaxRegExp", impl_script, core_impl_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
 
   // Initialize the base interfaces used by the core VM classes.
   const Script& script = Script::Handle(Bootstrap::LoadScript());
 
   // Allocate and initialize the Object class and type.
   // The Object and ExternalByteArray classes are the only pre-allocated
   // non-interface classes in the core library.
   cls = Class::New<Instance>();
   object_store->set_object_class(cls);
   cls.set_name(String::Handle(String::NewSymbol("Object")));
   cls.set_script(script);
   core_lib.AddClass(cls);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_object_type(type);
 
   cls = Class::New<InternalByteArray>();
   object_store->set_internal_byte_array_class(cls);
   cls.set_name(String::Handle(core_lib.PrivateName("_InternalByteArray")));
   cls.set_script(script);
   core_lib.AddClass(cls);
 
   cls = Class::New<ExternalByteArray>();
   object_store->set_external_byte_array_class(cls);
   cls.set_name(String::Handle(core_lib.PrivateName("_ExternalByteArray")));
   cls.set_script(script);
   core_lib.AddClass(cls);
 
   // Set the super type of class Stacktrace to Object type so that the
   // 'toString' method is implemented.
   cls = object_store->stacktrace_class();
   cls.set_super_type(type);
 
   cls = CreateAndRegisterInterface("Function", script, core_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_function_interface(type);
 
   cls = CreateAndRegisterInterface("num", script, core_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_number_interface(type);
 
   cls = CreateAndRegisterInterface("int", script, core_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_int_interface(type);
 
   cls = CreateAndRegisterInterface("double", script, core_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_double_interface(type);
 
   cls = CreateAndRegisterInterface("String", script, core_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_string_interface(type);
 
   cls = CreateAndRegisterInterface("bool", script, core_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_bool_interface(type);
 
   cls = CreateAndRegisterInterface("List", script, core_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_list_interface(type);
 
   cls = CreateAndRegisterInterface("ByteArray", script, core_lib);
-  pending_classes.Add(&Class::ZoneHandle(cls.raw()));
+  pending_classes.Add(cls, Heap::kOld);
   type = Type::NewNonParameterizedType(cls);
   object_store->set_byte_array_interface(type);
 
   // The classes 'Null' and 'void' are not registered in the class dictionary,
   // because their names are reserved keywords. Their names are not heap
   // allocated, because the classes reside in the VM isolate.
   // The corresponding types are stored in the object store.
   cls = null_class_;
   type = Type::NewNonParameterizedType(cls);
   object_store->set_null_type(type);
 
   cls = void_class_;
   type = Type::NewNonParameterizedType(cls);
   object_store->set_void_type(type);
 
   // The class 'Dynamic' is registered in the class dictionary because its name
   // is a built-in identifier, rather than a reserved keyword. Its name is not
   // heap allocated, because the class resides in the VM isolate.
   // The corresponding type, the "unknown type", is stored in the object store.
   cls = dynamic_class_;
   type = Type::NewNonParameterizedType(cls);
   object_store->set_dynamic_type(type);
   core_lib.AddClass(cls);
 
-  // Add the preallocated classes to the list of classes to be finalized.
-  ClassFinalizer::AddPendingClasses(pending_classes);
-
   // Allocate pre-initialized values.
   Bool& bool_value = Bool::Handle();
   bool_value = Bool::New(true);
   object_store->set_true_value(bool_value);
   bool_value = Bool::New(false);
   object_store->set_false_value(bool_value);
 
   // Setup some default native field classes which can be extended for
   // specifying native fields in dart classes.
   Library::InitNativeWrappersLibrary(isolate);
@@ skipping 44 matching lines @@
   cls = Class::New<Array>();
   object_store->set_array_class(cls);
 
   Array& empty_array = Array::Handle();
   empty_array = Array::New(0);
   object_store->set_empty_array(empty_array);
 
   cls = Class::New<ImmutableArray>();
   object_store->set_immutable_array_class(cls);
 
+  cls = Class::New<GrowableObjectArray>();
+  object_store->set_growable_object_array_class(cls);
+
   cls = Class::New<InternalByteArray>();
   object_store->set_internal_byte_array_class(cls);
 
   cls = Class::New<ExternalByteArray>();
   object_store->set_external_byte_array_class(cls);
 
   cls = Class::New<Instance>();
   object_store->set_object_class(cls);
 
   cls = Class::New<Smi>();
@@ skipping 546 matching lines @@
       return object_store->external_four_byte_string_class();
     case kBool:
       ASSERT(object_store->bool_class() != Class::null());
       return object_store->bool_class();
     case kArray:
       ASSERT(object_store->array_class() != Class::null());
       return object_store->array_class();
     case kImmutableArray:
       ASSERT(object_store->immutable_array_class() != Class::null());
       return object_store->immutable_array_class();
+    case kGrowableObjectArray:
+      ASSERT(object_store->growable_object_array_class() != Class::null());
+      return object_store->growable_object_array_class();
     case kInternalByteArray:
       ASSERT(object_store->internal_byte_array_class() != Class::null());
       return object_store->internal_byte_array_class();
     case kExternalByteArray:
       ASSERT(object_store->external_byte_array_class() != Class::null());
       return object_store->external_byte_array_class();
     case kStacktrace:
       ASSERT(object_store->stacktrace_class() != Class::null());
       return object_store->stacktrace_class();
     case kJSRegExp:
@@ skipping 2231 matching lines @@
     ClassFinalizer::FinalizeType(
         signature_class, signature_type, ClassFinalizer::kFinalize);
   }
   ASSERT(closure_function.signature_class() == signature_class.raw());
   set_implicit_closure_function(closure_function);
   ASSERT(closure_function.IsImplicitClosureFunction());
   return closure_function.raw();
 }
 
 
-template<typename T>
-static RawArray* NewArray(const GrowableArray<T*>& objs) {
-  Array& a = Array::Handle(Array::New(objs.length(), Heap::kOld));
-  for (int i = 0; i < objs.length(); i++) {
-    a.SetAt(i, *objs[i]);
-  }
-  return a.raw();
-}
-
-
 RawString* Function::BuildSignature(
     bool instantiate,
     const AbstractTypeArguments& instantiator) const {
-  GrowableArray<const String*> pieces;
+  const GrowableObjectArray& pieces =
+      GrowableObjectArray::Handle(GrowableObjectArray::New());
   const String& kCommaSpace = String::Handle(String::NewSymbol(", "));
   const String& kColonSpace = String::Handle(String::NewSymbol(": "));
   const String& kLParen = String::Handle(String::NewSymbol("("));
   const String& kRParen = String::Handle(String::NewSymbol(") => "));
   const String& kLBracket = String::Handle(String::NewSymbol("["));
   const String& kRBracket = String::Handle(String::NewSymbol("]"));
+  String& name = String::Handle();
   if (!instantiate && !is_static()) {
     const String& kSpaceExtendsSpace =
         String::Handle(String::NewSymbol(" extends "));
     const String& kLAngleBracket = String::Handle(String::NewSymbol("<"));
     const String& kRAngleBracket = String::Handle(String::NewSymbol(">"));
     const Class& function_class = Class::Handle(owner());
     ASSERT(!function_class.IsNull());
     const TypeArguments& type_parameters = TypeArguments::Handle(
         function_class.type_parameters());
     if (!type_parameters.IsNull()) {
       intptr_t num_type_parameters = type_parameters.Length();
-      pieces.Add(&kLAngleBracket);
+      pieces.Add(kLAngleBracket);
       const TypeArguments& bounds = TypeArguments::Handle(
           function_class.type_parameter_bounds());
       AbstractType& type_parameter = AbstractType::Handle();
       AbstractType& bound = AbstractType::Handle();
       for (intptr_t i = 0; i < num_type_parameters; i++) {
         type_parameter ^= type_parameters.TypeAt(i);
-        pieces.Add(&String::ZoneHandle(type_parameter.Name()));
+        name = type_parameter.Name();
+        pieces.Add(name);
         bound = bounds.TypeAt(i);
         if (!bound.IsNull() && !bound.IsDynamicType()) {
-          pieces.Add(&kSpaceExtendsSpace);
-          pieces.Add(&String::ZoneHandle(bound.Name()));
+          pieces.Add(kSpaceExtendsSpace);
+          name = bound.Name();
+          pieces.Add(name);
         }
         if (i < num_type_parameters - 1) {
-          pieces.Add(&kCommaSpace);
+          pieces.Add(kCommaSpace);
         }
       }
-      pieces.Add(&kRAngleBracket);
+      pieces.Add(kRAngleBracket);
     }
   }
   AbstractType& param_type = AbstractType::Handle();
   const intptr_t num_params = NumberOfParameters();
   const intptr_t num_fixed_params = num_fixed_parameters();
   const intptr_t num_opt_params = num_optional_parameters();
   ASSERT((num_fixed_params + num_opt_params) == num_params);
-  pieces.Add(&kLParen);
+  pieces.Add(kLParen);
   for (intptr_t i = 0; i < num_fixed_params; i++) {
     param_type = ParameterTypeAt(i);
     ASSERT(!param_type.IsNull());
     if (instantiate && !param_type.IsInstantiated()) {
       param_type = param_type.InstantiateFrom(instantiator);
     }
-    pieces.Add(&String::ZoneHandle(param_type.Name()));
+    name = param_type.Name();
+    pieces.Add(name);
     if (i != (num_params - 1)) {
-      pieces.Add(&kCommaSpace);
+      pieces.Add(kCommaSpace);
     }
   }
   if (num_opt_params > 0) {
-    pieces.Add(&kLBracket);
+    pieces.Add(kLBracket);
     for (intptr_t i = num_fixed_params; i < num_params; i++) {
-      pieces.Add(&String::ZoneHandle(ParameterNameAt(i)));
-      pieces.Add(&kColonSpace);
+      name = ParameterNameAt(i);
+      pieces.Add(name);
+      pieces.Add(kColonSpace);
       param_type = ParameterTypeAt(i);
       if (instantiate && !param_type.IsInstantiated()) {
         param_type = param_type.InstantiateFrom(instantiator);
       }
       ASSERT(!param_type.IsNull());
-      pieces.Add(&String::ZoneHandle(param_type.Name()));
+      name = param_type.Name();
+      pieces.Add(name);
       if (i != (num_params - 1)) {
-        pieces.Add(&kCommaSpace);
+        pieces.Add(kCommaSpace);
       }
     }
-    pieces.Add(&kRBracket);
+    pieces.Add(kRBracket);
   }
-  pieces.Add(&kRParen);
+  pieces.Add(kRParen);
   AbstractType& res_type = AbstractType::Handle(result_type());
   if (instantiate && !res_type.IsInstantiated()) {
     res_type = res_type.InstantiateFrom(instantiator);
   }
-  pieces.Add(&String::Handle(res_type.Name()));
-  const Array& strings = Array::Handle(NewArray<const String>(pieces));
+  name = res_type.Name();
+  pieces.Add(name);
+  const Array& strings = Array::Handle(Array::MakeArray(pieces));
   return String::NewSymbol(String::Handle(String::ConcatAll(strings)));
 }
 
 
 bool Function::HasInstantiatedSignature() const {
   AbstractType& type = AbstractType::Handle(result_type());
   if (!type.IsInstantiated()) {
     return false;
   }
   const intptr_t num_parameters = NumberOfParameters();
@@ skipping 659 matching lines @@
   // Link class to this library.
   cls.set_library(*this);
 }
 
 
 RawArray* Library::LoadedScripts() const {
   // We compute the list of loaded scripts lazily. The result is
   // cached in loaded_scripts_.
   if (loaded_scripts() == Array::null()) {
     // Iterate over the library dictionary and collect all scripts.
-    GrowableArray<Script*> scripts(8);
+    const GrowableObjectArray& scripts =
+        GrowableObjectArray::Handle(GrowableObjectArray::New(8));
     Object& entry = Object::Handle();
     Function& func = Function::Handle();
     Field& field = Field::Handle();
     Class& cls = Class::Handle();
     Script& owner_script = Script::Handle();
     DictionaryIterator it(*this);
+    Script& script_obj = Script::Handle();
     while (it.HasNext()) {
       entry = it.GetNext();
       if (entry.IsClass()) {
         cls ^= entry.raw();
       } else if (entry.IsFunction()) {
         func ^= entry.raw();
         cls = func.owner();
       } else if (entry.IsField()) {
         field ^= entry.raw();
         cls = field.owner();
       } else {
         continue;
       }
       owner_script = cls.script();
       if (owner_script.IsNull()) {
         continue;
       }
       bool is_unique = true;
-      for (int i = 0; i < scripts.length(); i++) {
-        if (scripts[i]->raw() == owner_script.raw()) {
+      for (int i = 0; i < scripts.Length(); i++) {
+        script_obj ^= scripts.At(i);
+        if (script_obj.raw() == owner_script.raw()) {
           // We already have a reference to this script.
           is_unique = false;
           break;
         }
       }
       if (is_unique) {
-        // Create a unique script handle and add it to the list of scripts.
-        Script& unique_script = Script::Handle(owner_script.raw());
-        scripts.Add(&unique_script);
+        // Add script to the list of scripts.
+        scripts.Add(owner_script);
       }
     }
 
     // Create the array of scripts and cache it in loaded_scripts_.
-    const Array& loaded_scripts =
-        Array::Handle(Array::New(scripts.length(), Heap::kOld));
-    for (int i = 0; i < scripts.length(); i++) {
-      loaded_scripts.SetAt(i, *scripts[i]);
-    }
-    StorePointer(&raw_ptr()->loaded_scripts_, loaded_scripts.raw());
+    StorePointer(&raw_ptr()->loaded_scripts_, Array::MakeArray(scripts));
   }
   return loaded_scripts();
 }
 
 
 // TODO(hausner): we might want to add a script dictionary to the
 // library class to make this lookup faster.
 RawScript* Library::LookupScript(const String& url) const {
   const Array& scripts = Array::Handle(LoadedScripts());
   Script& script = Script::Handle();
@@ skipping 3585 matching lines @@
   }
   return result.raw();
 }
 
 
 RawArray* Array::Empty() {
   return Isolate::Current()->object_store()->empty_array();
 }
 
 
+RawArray* Array::MakeArray(const GrowableObjectArray& growable_array) {
+  intptr_t used_len = growable_array.Length();
+  intptr_t capacity_len = growable_array.Capacity();
+  Isolate* isolate = Isolate::Current();
+  Array& array = Array::Handle(isolate, growable_array.data());
+  Array& new_array = Array::Handle(isolate, Array::Empty());
+  intptr_t capacity_size = Array::InstanceSize(capacity_len);
+  intptr_t used_size = Array::InstanceSize(used_len);
+
+  // Update the size in the header field and length of the array object.
+  uword tags = 0;
+  tags = RawObject::SizeTag::update(used_size, tags);
+  array.raw_ptr()->tags_ = tags;
+  array.SetLength(used_len);
+
+  // Null the GrowableObjectArray, we are removing it's backing array.
+  growable_array.SetLength(0);
+  growable_array.SetData(new_array);
+
+  // If there is any left over space fill it with either an Array object or
+  // just a plain object (depending on the amount of left over space) so
+  // that it can be traversed over successfully during garbage collection.
+  if (capacity_size != used_size) {
+    NoGCScope no_gc;
+    ASSERT(capacity_len > used_len);
+    intptr_t leftover_size = capacity_size - used_size;
+
+    uword addr = RawObject::ToAddr(array.raw()) + used_size;
+    if (leftover_size >= Array::InstanceSize(0)) {
+      // As we have enough space to use an array object, update the leftover
+      // space as an Array object.
+      new_array.raw_ = reinterpret_cast<RawArray*>(RawObject::FromAddr(addr));
+      new_array.raw_ptr()->class_ = isolate->object_store()->array_class();
+      tags = RawObject::SizeTag::update(leftover_size, tags);
+      new_array.raw_ptr()->tags_ = tags;
+      intptr_t leftover_len =
+          ((leftover_size - Array::InstanceSize(0)) / kWordSize);
+      new_array.SetLength(leftover_len);
+    } else {
+      // Update the leftover space as a basic object.
+      ASSERT(leftover_size == Object::InstanceSize());
+      Object& new_object = Object::Handle(isolate, RawObject::FromAddr(addr));
+      new_object.raw()->ptr()->class_ = isolate->object_store()->object_class();
+      tags = RawObject::SizeTag::update(leftover_size, tags);
+      new_object.raw()->ptr()->tags_ = tags;
+    }
+  }
+  return array.raw();
+}
+
+
 RawImmutableArray* ImmutableArray::New(intptr_t len,
                                        Heap::Space space) {
   ObjectStore* object_store = Isolate::Current()->object_store();
   Class& cls = Class::Handle(object_store->immutable_array_class());
   return reinterpret_cast<RawImmutableArray*>(Array::New(cls, len, space));
 }
 
 
 const char* ImmutableArray::ToCString() const {
   return "ImmutableArray";
 }
 
 
+void GrowableObjectArray::Add(const Object& value, Heap::Space space) const {
+  ASSERT(!IsNull());
+  Array& contents = Array::Handle(data());
+  if (Length() == Capacity()) {
+    intptr_t new_capacity = Capacity() * 2;
+    if (new_capacity <= Capacity()) {
+      // Use the preallocated out of memory exception to avoid calling
+      // into dart code or allocating any code.
+      const Instance& exception =
+          Instance::Handle(Isolate::Current()->object_store()->out_of_memory());
+      Exceptions::Throw(exception);
+      UNREACHABLE();
+    }
+    StorePointer(&(raw_ptr()->data_),
+                 Array::Grow(contents, new_capacity, space));
+    contents = data();
+  }
+  ASSERT(Length() < Capacity());
+  intptr_t index = Length();
+  SetLength(index + 1);
+  contents.SetAt(index, value);
+}
+
+
+RawObject* GrowableObjectArray::RemoveLast() const {
+  ASSERT(!IsNull());
+  ASSERT(Length() > 0);
+  intptr_t index = Length() - 1;
+  const Array& contents = Array::Handle(data());
+  const Object& obj = Object::Handle(contents.At(index));
+  contents.SetAt(index, Object::Handle());
+  SetLength(index);
+  return obj.raw();
+}
+
+
+bool GrowableObjectArray::Equals(const Instance& other) const {
+  // If both handles point to the same raw instance they are equal.
+  if (this->raw() == other.raw()) {
+    return true;
+  }
+
+  // Other instance must be non null and a GrowableObjectArray.
+  if (!other.IsGrowableObjectArray() || other.IsNull()) {
+    return false;
+  }
+
+  GrowableObjectArray& other_arr = GrowableObjectArray::Handle();
+  other_arr ^= other.raw();
+
+  // The capacity and length of both objects must be equal.
+  if (Capacity() != other_arr.Capacity() || Length() != other_arr.Length()) {
+    return false;
+  }
+
+  // Both must have the same type arguments.
+  if (!AbstractTypeArguments::AreEqual(
+      AbstractTypeArguments::Handle(GetTypeArguments()),
+      AbstractTypeArguments::Handle(other.GetTypeArguments()))) {
+    return false;
+  }
+
+  // The data part in both arrays must be identical.
+  const Array& contents = Array::Handle(data());
+  const Array& other_contents = Array::Handle(other_arr.data());
+  for (intptr_t i = 0; i < Length(); i++) {
+    if (contents.At(i) != other_contents.At(i)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+
+RawGrowableObjectArray* GrowableObjectArray::New(intptr_t capacity,
+                                                 Heap::Space space) {
+  ObjectStore* object_store = Isolate::Current()->object_store();
+  Class& cls = Class::Handle(object_store->growable_object_array_class());
+  const Array& data = Array::Handle(Array::New(capacity, space));
+  GrowableObjectArray& result = GrowableObjectArray::Handle();
+  {
+    RawObject* raw = Object::Allocate(cls,
+                                      GrowableObjectArray::InstanceSize(),
+                                      space);
+    NoGCScope no_gc;
+    result ^= raw;
+    result.SetLength(0);
+    result.SetData(data);
+  }
+  return result.raw();
+}
+
+
+const char* GrowableObjectArray::ToCString() const {
+  return "GrowableObjectArray";
+}
+
+
 intptr_t ByteArray::Length() const {
   // ByteArray is an abstract class.
   UNREACHABLE();
   return 0;
 }
 
 
 void ByteArray::Copy(uint8_t* dst,
                      const ByteArray& src,
                      intptr_t src_offset,
@@ skipping 546 matching lines @@
   result.set_num_args_tested(num_args_tested);
   // Number of array elements in one test entry (num_args_tested + 1)
   intptr_t len = result.TestEntryLength();
   // IC data array must be null terminated (sentinel entry).
   Array& ic_data = Array::Handle(Array::New(len, Heap::kOld));
   result.set_ic_data(ic_data);
   return result.raw();
 }
 
 }  // namespace dart