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

vm/object.cc

Index: vm/object.cc
===================================================================
--- vm/object.cc	(revision 4983)
+++ vm/object.cc	(working copy)
@@ -444,6 +444,11 @@
   // 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 it's field is an array object.

[hausner, 2012/03/06 00:30:47]

it's -> its

Also missing ) in comment.

[siva, 2012/03/06 23:32:33]

Done.

+  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);
@@ -466,7 +471,9 @@
   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);
@@ -475,83 +482,82 @@
   // 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());
@@ -564,7 +570,7 @@
   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);
 
@@ -586,42 +592,42 @@
   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);
 
@@ -646,9 +652,6 @@
   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);
@@ -713,6 +716,9 @@
   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);
 
@@ -1279,6 +1285,9 @@
     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();
@@ -3530,26 +3539,18 @@
 }
 
 
-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 "));
@@ -3561,24 +3562,26 @@
         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();
@@ -3586,42 +3589,46 @@
   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)));
 }
 
@@ -4301,13 +4308,15 @@
   // 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()) {
@@ -4326,27 +4335,22 @@
         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();
 }
@@ -7952,6 +7956,58 @@
 }
 
 
+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::null());
+  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.set_length(0);
+  growable_array.set_capacity(0);
+  growable_array.set_data(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) {

[hausner, 2012/03/06 00:30:47]

Will this filler array/object be collected by the GC? Neat.

[siva, 2012/03/06 23:32:33]

Yes, this would be an unreferenced object and hence would get collected.

On 2012/03/06 00:30:47, hausner wrote:

+    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();
@@ -7965,6 +8021,98 @@
 }
 
 
+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;

[cshapiro, 2012/03/06 00:56:31]

Overflow check?

[siva, 2012/03/06 23:32:33]

I added a check to throw an exception if new_capacity is smaller than the old
capacity.

+    StorePointer(&(raw_ptr()->data_),
+                 Array::Grow(contents, new_capacity, space));
+    set_capacity(new_capacity);
+    contents = data();
+  }
+  ASSERT(Length() < Capacity());
+  intptr_t index = Length();
+  set_length(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());
+  set_length(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;
+  }
+
+  // Both must have the same type arguments.
+  if (!AbstractTypeArguments::AreEqual(

[hausner, 2012/03/06 00:30:47]

Would it make sense to compare the length first? I wouldn't be surprised if the
type arguments would often by "Dynamic" on both arrays, but the size may be
different.

[siva, 2012/03/06 23:32:33]

Done.

+      AbstractTypeArguments::Handle(GetTypeArguments()),
+      AbstractTypeArguments::Handle(other.GetTypeArguments()))) {
+    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;
+  }
+
+  // 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.set_capacity(capacity);
+    result.set_length(0);
+    result.set_data(data);
+  }
+  return result.raw();
+}
+
+
+const char* GrowableObjectArray::ToCString() const {
+  return "GrowableObjectArray";
+}
+
+
 intptr_t ByteArray::Length() const {
   // ByteArray is an abstract class.
   UNREACHABLE();