Canonicalize types.

runtime/vm/object.cc

Index: runtime/vm/object.cc
===================================================================
--- runtime/vm/object.cc	(revision 1040)
+++ runtime/vm/object.cc	(working copy)
@@ -614,8 +614,7 @@
 
   // 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);
 
@@ -774,6 +773,7 @@
   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();
@@ -793,6 +793,7 @@
       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());
 }
@@ -1010,6 +1011,7 @@
   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();
@@ -1210,6 +1212,26 @@
 }
 
 
+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());
@@ -1654,6 +1676,13 @@
 }
 
 
+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 {
@@ -1663,6 +1692,13 @@
 }
 
 
+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.
@@ -1891,6 +1927,7 @@
   type ^= ParameterizedType::New(
       Object::Handle(type_class.raw()), no_type_arguments);
   type.set_is_finalized();
+  type ^= type.Canonicalize();
   return type.raw();
 }
 
@@ -1997,6 +2034,58 @@
 }
 
 
+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());
@@ -2042,6 +2131,16 @@
 }
 
 
+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;
@@ -2177,6 +2276,26 @@
 }
 
 
+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 {
@@ -2303,6 +2422,24 @@
 }
 
 
+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 {
@@ -6421,8 +6558,10 @@
     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;
   }