Canonicalize types.

runtime/vm/object.cc

 // Copyright (c) 2011, 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 "vm/assembler.h"
 #include "vm/assert.h"
 #include "vm/bigint_operations.h"
 #include "vm/bootstrap.h"
@@ skipping 596 matching lines @@
 
 
 void Object::InitFromSnapshot(Isolate* isolate) {
   TIMERSCOPE(time_bootstrap);
   ObjectStore* object_store = isolate->object_store();
 
   Class& cls = Class::Handle();
 
   // Set up empty classes in the object store, these will get
   // initialized correctly when we read from the snapshot.
-  // This is done do allow bootstrapping of reading classes from
-  // the snapshot.
+  // This is done to allow bootstrapping of reading classes from the snapshot.
   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);
 
@@ skipping 138 matching lines @@
   result.set_instance_size(FakeObject::InstanceSize());
   result.set_next_field_offset(FakeObject::InstanceSize());
   result.set_instance_kind(FakeObject::kInstanceKind);
   result.raw_ptr()->is_const_ = false;
   result.raw_ptr()->is_interface_ = false;
   // VM backed classes are almost ready: run checks and resolve class
   // references, but do not recompute size.
   result.raw_ptr()->class_state_ = RawClass::kPreFinalized;
   result.raw_ptr()->type_arguments_instance_field_offset_ = kNoTypeArguments;
   result.raw_ptr()->num_constants_ = 0;
+  result.raw_ptr()->num_canonical_types_ = 0;
   result.raw_ptr()->num_native_fields_ = 0;
   result.InitEmptyFields();
   return result.raw();
 }
 
 
 // Initialize class fields of type Array with empty array.
 void Class::InitEmptyFields() {
   const Array& empty_array = Array::Handle(Array::Empty());
   if (empty_array.IsNull()) {
     // The empty array has not been initialized yet.
     return;
   }
   StorePointer(&raw_ptr()->interfaces_, empty_array.raw());
   // TODO(srdjan): Make functions_cache growable and start with a smaller size.
   Array& fcache =
       Array::Handle(Array::New(FunctionsCache::kNumEntries * 32, Heap::kOld));
   StorePointer(&raw_ptr()->functions_cache_, fcache.raw());
   StorePointer(&raw_ptr()->constants_, empty_array.raw());
+  StorePointer(&raw_ptr()->canonical_types_, empty_array.raw());
   StorePointer(&raw_ptr()->functions_, empty_array.raw());
   StorePointer(&raw_ptr()->fields_, empty_array.raw());
 }
 
 void Class::SetFunctions(const Array& value) const {
   ASSERT(!value.IsNull());
   // Bind all the functions in the array to this class.
   Function& func = Function::Handle();
   intptr_t len = value.Length();
   for (intptr_t i = 0; i < len; i++) {
@@ skipping 197 matching lines @@
   result.set_instance_size(FakeInstance::InstanceSize());
   result.set_next_field_offset(FakeInstance::InstanceSize());
   result.set_instance_kind(FakeInstance::kInstanceKind);
   result.set_name(name);
   result.set_script(script);
   result.raw_ptr()->is_const_ = false;
   result.raw_ptr()->is_interface_ = false;
   result.raw_ptr()->class_state_ = RawClass::kAllocated;
   result.raw_ptr()->type_arguments_instance_field_offset_ = kNoTypeArguments;
   result.raw_ptr()->num_constants_ = 0;
+  result.raw_ptr()->num_canonical_types_ = 0;
   result.raw_ptr()->num_native_fields_ = 0;
   result.InitEmptyFields();
   return result.raw();
 }
 
 
 RawClass* Class::New(const String& name, const Script& script) {
   Class& result = Class::Handle(New<Instance>(name, script));
   return result.raw();
 }
@@ skipping 180 matching lines @@
 intptr_t Class::num_constants() const {
   return raw_ptr()->num_constants_;
 }
 
 
 void Class::set_num_constants(intptr_t value) const {
   raw_ptr()->num_constants_ = value;
 }
 
 
+RawArray* Class::canonical_types() const {
+  return raw_ptr()->canonical_types_;
+}
+
+void Class::set_canonical_types(const Array& value) const {
+  ASSERT(!value.IsNull());
+  StorePointer(&raw_ptr()->canonical_types_, value.raw());
+}
+
+
+intptr_t Class::num_canonical_types() const {
+  return raw_ptr()->num_canonical_types_;
+}
+
+
+void Class::set_num_canonical_types(intptr_t value) const {
+  raw_ptr()->num_canonical_types_ = value;
+}
+
+
 void Class::set_allocation_stub(const Code& value) const {
   ASSERT(!value.IsNull());
   ASSERT(raw_ptr()->allocation_stub_ == Code::null());
   StorePointer(&raw_ptr()->allocation_stub_, value.raw());
 }
 
 
 bool Class::IsObjectClass() const {
   return raw() == Type::Handle(Type::ObjectType()).type_class();
 }
@@ skipping 424 matching lines @@
 }
 
 
 bool Type::IsBeingFinalized() const {
   // Type is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
+bool Type::Equals(const Type& other) const {
+  // Type is an abstract class.
+  UNREACHABLE();
+  return false;
+}
+
+
 RawType* Type::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     intptr_t offset) const {
   // Type is an abstract class.
   UNREACHABLE();
   return Type::null();
 }
 
 
+RawType* Type::Canonicalize() const {
+  // Type is an abstract class.
+  UNREACHABLE();
+  return Type::null();
+}
+
+
 RawString* Type::Name() const {
   // If the type is still being finalized, we may be reporting an error about
   // an illformed type, so proceed with caution.
   const TypeArguments& args = TypeArguments::Handle(arguments());
   const intptr_t num_args = args.IsNull() ? 0 : args.Length();
   String& class_name = String::Handle();
   intptr_t first_type_param_index;
   intptr_t num_type_params;  // Number of type parameters to print.
   if (HasResolvedTypeClass()) {
     const Class& cls = Class::Handle(type_class());
@@ skipping 208 matching lines @@
 }
 
 
 RawType* Type::NewNonParameterizedType(const Class& type_class) {
   ASSERT(!type_class.HasTypeArguments());
   const TypeArguments& no_type_arguments = TypeArguments::Handle();
   ParameterizedType& type = ParameterizedType::Handle();
   type ^= ParameterizedType::New(
       Object::Handle(type_class.raw()), no_type_arguments);
   type.set_is_finalized();
+  type ^= type.Canonicalize();
   return type.raw();
 }
 
 
 RawType* Type::NewParameterizedType(const Object& clazz,
                                     const TypeArguments& arguments) {
   return ParameterizedType::New(clazz, arguments);
 }
 
 
@@ skipping 86 matching lines @@
   const Class& cls = Class::Handle(type_class());
   ParameterizedType& instantiated_type = ParameterizedType::Handle(
       ParameterizedType::New(cls, type_arguments));
   ASSERT(type_arguments.IsNull() ||
          (type_arguments.Length() == cls.NumTypeArguments()));
   instantiated_type.set_is_finalized();
   return instantiated_type.raw();
 }
 
 
+bool ParameterizedType::Equals(const Type& other) const {
+  ASSERT(IsFinalized() && other.IsFinalized());
+  if (!other.IsParameterizedType()) {
+    return false;
+  }
+  ParameterizedType& other_parameterized_type = ParameterizedType::Handle();
+  other_parameterized_type ^= other.raw();
+  if (type_class() != other_parameterized_type.type_class()) {
+    return false;
+  }
+  return TypeArguments::AreEqual(TypeArguments::Handle(arguments()),
+                                 TypeArguments::Handle(other.arguments()));
+}
+
+
+RawType* ParameterizedType::Canonicalize() const {
+  const Class& cls = Class::Handle(type_class());
+  Array& canonical_types = Array::Handle(cls.canonical_types());
+  if (canonical_types.IsNull()) {

[srdjan, 2011/11/01 20:51:43]

Should this be an assert (canonical types is initialized to empty array).

[regis, 2011/11/01 21:54:50]

No, this is more complicated. Classes of the VM isolate (e.g. null_class_,
void_class_, dynamic_class_) cannot point to arrays allocated in other isolates.
We would have to store these classes in the object store.
I added a TODO, in case we decide to do just that.
It may then be possible to remove all types from the object store and rely on
type canonicalization instead. I'd prefer to do this in a following cl.

+    // Types defined in the VM isolate are canonicalized via the object store.
+    return this->raw();
+  }
+  const intptr_t num_canonical_types = cls.num_canonical_types();
+  ASSERT(canonical_types.Length() >= num_canonical_types);
+  // Linear search to see whether this type is already present in the
+  // list of canonicalized types.
+  Type& type = Type::Handle();
+  for (int i = 0; i < num_canonical_types; i++) {
+    type ^= canonical_types.At(i);
+    ASSERT(!type.IsNull());
+    if (this->Equals(type)) {
+      return type.raw();
+    }
+  }

[srdjan, 2011/11/01 20:51:43]

I wonder if you need num_canonical_types variable. Instead you can use the
canonical_types.Length() and abort once you meet type.IsNull.

[regis, 2011/11/01 21:54:50]

There is not sentinel ending the array with a null type. I duplicated the code
used for constants.

[srdjan, 2011/11/01 22:05:14]

You do not need a NULL sentinel as you would iterate for length of array and
break when null encountered. Grow operation fills array with null objects.

[regis, 2011/11/01 22:28:53]

Ah, I now see what you mean. Clever!
I missed the fact that we can rely on the Grow operation initializing the empty
space.
I will remove the num_canonical_types_ as well as the num_contants_ field.

+  // The type needs to be added to the list. Grow the list if it is full.
+  if (canonical_types.Length() == num_canonical_types) {
+    const intptr_t kInitialCanonicalTypesLength = 2;  // Raw and parameterized.
+    const intptr_t old_length = canonical_types.Length();
+    const intptr_t new_length =
+        (old_length == 0) ? kInitialCanonicalTypesLength : old_length * 2;

[srdjan, 2011/11/01 20:51:43]

The growth (old_length * 2) seems a little excessive. Why not + kGrowthConstant

[regis, 2011/11/01 21:54:50]

OK, I now add 2 elements each time the array grows. 

[srdjan, 2011/11/01 22:05:14]

If you add only one, you can get rid of a field in class and make the algorithm
simpler :-).

[regis, 2011/11/01 22:28:53]

Actually, I think I can still simplify and remove the field while incrementing
by 2 :-)

+    const Array& new_canonical_types =
+        Array::Handle(Array::Grow(canonical_types, new_length, Heap::kOld));
+    cls.set_canonical_types(new_canonical_types);
+    new_canonical_types.SetAt(num_canonical_types, *this);
+  } else {
+    canonical_types.SetAt(num_canonical_types, *this);
+  }
+  cls.set_num_canonical_types(num_canonical_types + 1);
+  return this->raw();
+}
+
+
 void ParameterizedType::set_type_class(const Object& value) const {
   ASSERT(!value.IsNull() && (value.IsClass() || value.IsUnresolvedClass()));
   StorePointer(&raw_ptr()->type_class_, value.raw());
 }
 
 
 void ParameterizedType::set_arguments(const TypeArguments& value) const {
   StorePointer(&raw_ptr()->arguments_, value.raw());
 }
 
@@ skipping 25 matching lines @@
          state == RawParameterizedType::kFinalized);
   raw_ptr()->type_state_ = state;
 }
 
 
 const char* ParameterizedType::ToCString() const {
   return "ParameterizedType";
 }
 
 
+bool TypeParameter::Equals(const Type& other) const {
+  if (!other.IsTypeParameter()) {
+    return false;
+  }
+  TypeParameter& other_type_parameter = TypeParameter::Handle();
+  other_type_parameter ^= other.raw();
+  return Index() == other_type_parameter.Index();
+}
+
+
 void TypeParameter::set_index(intptr_t value) const {
   ASSERT(value >= 0);
   raw_ptr()->index_ = value;
 }
 
 
 void TypeParameter::set_name(const String& value) const {
   ASSERT(value.IsSymbol());
   StorePointer(&raw_ptr()->name_, value.raw());
 }
@@ skipping 115 matching lines @@
 }
 
 
 bool TypeArguments::IsUninstantiatedIdentity() const {
   // TypeArguments is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
+bool TypeArguments::Equals(const TypeArguments& other) const {
+  // TypeArguments is an abstract class.
+  UNREACHABLE();
+  return false;
+}
+
+
+bool TypeArguments::AreEqual(const TypeArguments& arguments,
+                             const TypeArguments& other_arguments) {
+  if (arguments.IsNull()) {
+    return (other_arguments.IsNull() ||
+            other_arguments.IsDynamicTypes(other_arguments.Length()));
+  }
+  if (other_arguments.IsNull()) {
+    return arguments.IsDynamicTypes(arguments.Length());
+  }
+  return arguments.Equals(other_arguments);
+}
+
+
 RawTypeArguments* TypeArguments::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     intptr_t offset) const {
   // TypeArguments is an abstract class.
   UNREACHABLE();
   return TypeArguments::null();
 }
 
 
 bool TypeArguments::IsDynamicTypes(intptr_t len) const {
@@ skipping 106 matching lines @@
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     if (!type.IsTypeParameter() || (type.Index() != i)) {
       return false;
     }
   }
   return true;
 }
 
 
+bool TypeArray::Equals(const TypeArguments& other) const {
+  intptr_t num_types = Length();
+  if (num_types != other.Length()) {
+    return false;
+  }
+  Type& type = Type::Handle();
+  Type& other_type = Type::Handle();
+  for (intptr_t i = 0; i < num_types; i++) {
+    type = TypeAt(i);
+    other_type = other.TypeAt(i);
+    if (!type.Equals(other_type)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+
 RawTypeArguments* TypeArray::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     intptr_t offset) const {
   ASSERT(!IsInstantiated());
   if (instantiator_type_arguments.IsNull()) {
     return TypeArguments::null();
   }
   if ((offset == 0) &&
       !instantiator_type_arguments.IsNull() &&
       IsUninstantiatedIdentity() &&
@@ skipping 4098 matching lines @@
 bool Array::Equals(const Instance& other) const {
   if (this->raw() == other.raw()) {
     // Both handles point to the same raw instance.
     return true;
   }
 
   if (!other.IsArray() || other.IsNull()) {
     return false;
   }
 
-  // Must have the same type.
-  if (GetTypeArguments() != other.GetTypeArguments()) {
+  // Must have the same type arguments.
+  if (!TypeArguments::AreEqual(
+      TypeArguments::Handle(GetTypeArguments()),
+      TypeArguments::Handle(other.GetTypeArguments()))) {
     return false;
   }
 
   Array& other_arr = Array::Handle();
   other_arr ^= other.raw();
 
   intptr_t len = this->Length();
   if (len != other_arr.Length()) {
     return false;
   }
@@ skipping 374 matching lines @@
   const String& str = String::Handle(pattern());
   const char* format = "JSRegExp: pattern=%s flags=%s";
   intptr_t len = OS::SNPrint(NULL, 0, format, str.ToCString(), Flags());
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(len + 1));
   OS::SNPrint(chars, (len + 1), format, str.ToCString(), Flags());
   return chars;
 }
 
 }  // namespace dart