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 (raw() == other.raw()) {
+    return true;
+  }
+  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()) {
+    // Types defined in the VM isolate are canonicalized via the object store.
+    // TODO(regis): Should we add null_class_, void_class_, dynamic_class_ to
+    // the object store, remove all types from the object store, and replace
+    // the test above by an assert?
+    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();
+    }
+  }
+  // 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 kLengthIncrement = 2;  // Raw and parameterized.
+    const intptr_t new_length = canonical_types.Length() + kLengthIncrement;
+    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 (raw() == other.raw()) {
+    return true;
+  }
+  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.raw() == other_arguments.raw()) {
+    return true;
+  }
+  if (arguments.IsNull()) {
+    return 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