Canonicalize TypeArguments.

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 373 matching lines @@
   // has been created.
   cls.InitEmptyFields();
 
   // Setup the symbol table used within the String class.
   const int kInitialSymbolTableSize = 16;
   array = Array::New(kInitialSymbolTableSize + 1);
   // Last element contains the count of used slots.
   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);
 
   // Basic infrastructure has been setup, initialize the class dictionary.
   Library::InitCoreLibrary(isolate);
   Library& core_lib = Library::Handle(Library::CoreLibrary());
   ASSERT(!core_lib.IsNull());
   Library& core_impl_lib = Library::Handle(Library::CoreImplLibrary());
   ASSERT(!core_impl_lib.IsNull());
@@ skipping 1901 matching lines @@
   return chars;
 }
 
 
 RawClass* InstantiatedType::type_class() const {
   return AbstractType::Handle(uninstantiated_type()).type_class();
 }
 
 
 RawAbstractTypeArguments* InstantiatedType::arguments() const {
-  return AbstractTypeArguments::NewInstantiatedTypeArguments(
+  return InstantiatedTypeArguments::New(
       AbstractTypeArguments::Handle(AbstractType::Handle(
           uninstantiated_type()).arguments()),
       AbstractTypeArguments::Handle(instantiator_type_arguments()));
 }
 
 
 void InstantiatedType::set_uninstantiated_type(
     const AbstractType& value) const {
   StorePointer(&raw_ptr()->uninstantiated_type_, value.raw());
 }
@@ skipping 67 matching lines @@
 
 
 bool AbstractTypeArguments::IsUninstantiatedIdentity() const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
 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;
 }
 
 
 bool AbstractTypeArguments::AreEqual(
     const AbstractTypeArguments& arguments,
     const AbstractTypeArguments& other_arguments) {
   if (arguments.raw() == other_arguments.raw()) {
     return true;
   }
   if (arguments.IsNull()) {
@@ skipping 49 matching lines @@
     other_type = other.TypeAt(i);
     ASSERT(!other_type.IsNull());
     if (!type.IsMoreSpecificThan(other_type)) {
       return false;
     }
   }
   return true;
 }
 
 
-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();
   return "AbstractTypeArguments";
 }
 
 
 intptr_t TypeArguments::Length() const {
   ASSERT(!IsNull());
   return Smi::Value(raw_ptr()->length_);
@@ skipping 22 matching lines @@
   }
   return true;
 }
 
 
 bool TypeArguments::IsInstantiated() const {
   AbstractType& type = AbstractType::Handle();
   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;
     }
   }
   return true;
 }
 
 
 bool TypeArguments::IsUninstantiatedIdentity() const {
   ASSERT(!IsInstantiated());
   AbstractType& type = AbstractType::Handle();
   intptr_t num_types = Length();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     if (!type.IsTypeParameter() || (type.Index() != i)) {
       return false;
     }
   }
   return true;
 }
 
 
-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 {
   ASSERT(!IsInstantiated());
   if ((offset == 0) &&
       !instantiator_type_arguments.IsNull() &&
       IsUninstantiatedIdentity() &&
       (instantiator_type_arguments.Length() == Length())) {
     return instantiator_type_arguments.raw();
   }
@@ skipping 21 matching lines @@
 
   const Class& type_arguments_class =
       Class::Handle(Object::type_arguments_class());
   TypeArguments& result = TypeArguments::Handle();
   {
     RawObject* raw = Object::Allocate(type_arguments_class,
                                       TypeArguments::InstanceSize(len),
                                       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()));
   return &raw_ptr()->types_[index];
 }
 
 
 void TypeArguments::SetLength(intptr_t value) {
   // This is only safe because we create a new Smi, which does not cause
   // heap allocation.
   raw_ptr()->length_ = Smi::New(value);
 }
 
 
+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";
   }
   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));
     OS::SNPrint(chars, len, format, prev_cstr, type_cstr);
     prev_cstr = chars;
   }
   return prev_cstr;
 }
 
 
@@ skipping 58 matching lines @@
   result.set_uninstantiated_type_arguments(uninstantiated_type_arguments);
   result.set_instantiator_type_arguments(instantiator_type_arguments);
   return result.raw();
 }
 
 
 const char* InstantiatedTypeArguments::ToCString() const {
   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();
   const char* instantiator_cstr =
       AbstractTypeArguments::Handle(instantiator_type_arguments()).ToCString();
   intptr_t len =
       OS::SNPrint(NULL, 0, format, arg_cstr, instantiator_cstr) + 1;
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(len));
   OS::SNPrint(chars, len, format, arg_cstr, instantiator_cstr);
@@ skipping 2304 matching lines @@
   AbstractTypeArguments& type_arguments = AbstractTypeArguments::Handle();
   type_arguments ^= *FieldAddrAtOffset(field_offset);
   return type_arguments.raw();
 }
 
 
 void Instance::SetTypeArguments(const AbstractTypeArguments& value) const {
   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.

 }
 
 
 bool Instance::TestType(TypeTestKind test,
                         const AbstractType& other,
                         const AbstractTypeArguments& other_instantiator) const {
   ASSERT(other.IsFinalized());
   ASSERT(!other.IsDynamicType());
   ASSERT(!other.IsVoidType());
   if (IsNull()) {
@@ skipping 2232 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