Canonicalize TypeArguments.

runtime/vm/object.cc

Index: runtime/vm/object.cc
===================================================================
--- runtime/vm/object.cc	(revision 2094)
+++ runtime/vm/object.cc	(working copy)
@@ -391,6 +391,10 @@
   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);
@@ -2312,7 +2316,7 @@
 
 
 RawAbstractTypeArguments* InstantiatedType::arguments() const {
-  return AbstractTypeArguments::NewInstantiatedTypeArguments(
+  return InstantiatedTypeArguments::New(
       AbstractTypeArguments::Handle(AbstractType::Handle(
           uninstantiated_type()).arguments()),
       AbstractTypeArguments::Handle(instantiator_type_arguments()));
@@ -2400,9 +2404,23 @@
 
 
 bool AbstractTypeArguments::Equals(const AbstractTypeArguments& other) const {
-  // AbstractTypeArguments is an abstract class.
-  UNREACHABLE();
-  return false;
+  if (this->raw() == other.raw()) {
+    return true;
+  }
+  intptr_t num_types = Length();
+  if (num_types != other.Length()) {
+    return false;
+  }
+  AbstractType& type = AbstractType::Handle();
+  AbstractType& other_type = AbstractType::Handle();
+  for (intptr_t i = 0; i < num_types; i++) {
+    type = TypeAt(i);
+    other_type = other.TypeAt(i);
+    if (!type.IsNull() && !type.Equals(other_type)) {

[regis, 2011/12/05 23:16:35]

What if type.IsNull() && !other_type.IsNull()?

[srdjan, 2011/12/06 17:24:15]

Type can't be NULL, removed test (see comment below).

+      return false;
+    }
+  }
+  return true;
 }
 
 
@@ -2472,14 +2490,6 @@
 }
 
 
-RawAbstractTypeArguments* AbstractTypeArguments::NewInstantiatedTypeArguments(
-    const AbstractTypeArguments& uninstantiated_type_arguments,
-    const AbstractTypeArguments& instantiator_type_arguments) {
-  return InstantiatedTypeArguments::New(uninstantiated_type_arguments,
-                                        instantiator_type_arguments);
-}
-
-
 const char* AbstractTypeArguments::ToCString() const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
@@ -2522,7 +2532,8 @@
   intptr_t num_types = Length();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
-    if (!type.IsInstantiated()) {
+    // type.IsNull() means it is Dynamic type.

[regis, 2011/12/05 23:16:35]

We should not encounter a Null type in a non-null type arguments. Either the
vector is null or its elements are not null. We should debug when this case
arises.

[srdjan, 2011/12/06 17:24:15]

Removed isNull case (reverting the lines here). It was occurring in some of my
test code that is now removed.

+    if (!type.IsNull() && !type.IsInstantiated()) {
       return false;
     }
   }
@@ -2544,24 +2555,6 @@
 }
 
 
-bool TypeArguments::Equals(const AbstractTypeArguments& other) const {
-  intptr_t num_types = Length();
-  if (num_types != other.Length()) {
-    return false;
-  }
-  AbstractType& type = AbstractType::Handle();
-  AbstractType& other_type = AbstractType::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;
-}
-
-
 RawAbstractTypeArguments* TypeArguments::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
     intptr_t offset) const {
@@ -2603,15 +2596,18 @@
                                       Heap::kOld);
     NoGCScope no_gc;
     result ^= raw;
+    // Length must be set before we start storing into the array.
     result.SetLength(len);
     for (intptr_t i = 0; i < len; i++) {
       *result.TypeAddr(i) = Type::null();
     }
   }
+  result.set_is_canonical(false);
   return result.raw();
 }
 
 
+
 RawAbstractType** TypeArguments::TypeAddr(intptr_t index) const {
   // TODO(iposva): Determine if we should throw an exception here.
   ASSERT((index >= 0) && (index < Length()));
@@ -2626,6 +2622,44 @@
 }
 
 
+RawAbstractTypeArguments* TypeArguments::Canonicalize() const {

[regis, 2011/12/05 23:16:35]

I would add a comment that Canonicalize for a non-instantiated type arguments is
a no-op.

[srdjan, 2011/12/06 17:24:15]

Expanded the existing comment in header file.

+  if (IsNull() || is_canonical() || !IsInstantiated()) {
+    return this->raw();
+  }
+  ObjectStore* object_store = Isolate::Current()->object_store();
+  // 'table' must be null terminated.
+  Array& table = Array::Handle(object_store->canonical_type_arguments());
+  ASSERT(table.Length() > 0);
+  intptr_t ix = 0;

[regis, 2011/12/05 23:16:35]

index?

[srdjan, 2011/12/06 17:24:15]

Done.

+  TypeArguments& other = TypeArguments::Handle();
+  other ^= table.At(ix);
+  while (!other.IsNull()) {
+    if (this->Equals(other)) {
+      return other.raw();
+    }
+    other ^= table.At(++ix);
+  }
+  // Not found. Add 'this' to table.
+  if (ix == table.Length() - 1) {
+    table = Array::Grow(table, table.Length() + 4, Heap::kOld);
+    object_store->set_canonical_type_arguments(table);
+  }
+  table.SetAt(ix, *this);
+  this->set_is_canonical(true);
+  return this->raw();
+}
+
+
+bool TypeArguments::is_canonical() const {
+  return raw_ptr()->is_canonical_ == Bool::True();
+}
+
+
+void TypeArguments::set_is_canonical(bool value) const {
+  raw_ptr()->is_canonical_ = value ? Bool::True() : Bool::False();

[regis, 2011/12/05 23:16:35]

Why do you store a dart value?
Other flags in classes and types are not dart values.

[srdjan, 2011/12/06 17:24:15]

I am moving it to above the length of RawTypeArgument and converting it to bool.

+}
+
+
 const char* TypeArguments::ToCString() const {
   if (IsNull()) {
     return "NULL TypeArguments";
@@ -2633,7 +2667,8 @@
   const char* format = "%s [%s]";
   const char* prev_cstr = "TypeArguments:";
   for (int i = 0; i < Length(); i++) {
-    const char* type_cstr = AbstractType::Handle(TypeAt(i)).ToCString();
+    const AbstractType& type_at = AbstractType::Handle(TypeAt(i));
+    const char* type_cstr = type_at.IsNull() ? "null" : type_at.ToCString();
     intptr_t len = OS::SNPrint(NULL, 0, format, prev_cstr, type_cstr) + 1;
     char* chars = reinterpret_cast<char*>(
         Isolate::Current()->current_zone()->Allocate(len));
@@ -2712,7 +2747,7 @@
   if (IsNull()) {
     return "NULL InstantiatedTypeArguments";
   }
-  const char* format = "InstantiatedTypeArguments: [%s] instantiator: [%s]\n";
+  const char* format = "InstantiatedTypeArguments: [%s] instantiator: [%s]";
   const char* arg_cstr =
       AbstractTypeArguments::Handle(
           uninstantiated_type_arguments()).ToCString();
@@ -5037,7 +5072,7 @@
   const Class& cls = Class::Handle(clazz());
   intptr_t field_offset = cls.type_arguments_instance_field_offset();
   ASSERT(field_offset != Class::kNoTypeArguments);
-  *FieldAddrAtOffset(field_offset) = value.raw();
+  *FieldAddrAtOffset(field_offset) = value.Canonicalize();

[regis, 2011/12/05 23:16:35]

Same comment: What about inline assembly?

[srdjan, 2011/12/06 17:24:15]

Discussed, not an issue.

 }