Fix canonicalization of types.

runtime/vm/object.cc

 // Copyright (c) 2012, 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 "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 3233 matching lines @@
 RawObject* Class::canonical_types() const {
   return raw_ptr()->canonical_types_;
 }
 
 void Class::set_canonical_types(const Object& value) const {
   ASSERT(!value.IsNull());
   StorePointer(&raw_ptr()->canonical_types_, value.raw());
 }
 
 
+intptr_t Class::NumCanonicalTypes() const {
+  if (CanonicalType() != Type::null()) {
+    return 1;
+  }
+  const Object& types = Object::Handle(canonical_types());
+  if (types.IsNull()) {
+    return 0;
+  }
+  intptr_t num_types = Array::Cast(types).Length();
+  while ((num_types > 0) &&
+         (Array::Cast(types).At(num_types - 1) == Type::null())) {
+    num_types--;
+  }
+  return num_types;
+}
+
+
+intptr_t Class::FindCanonicalTypeIndex(const Type& needle) const {
+  Isolate* isolate = Isolate::Current();
+  if (EnsureIsFinalized(isolate) != Error::null()) {
+    return -1;
+  }
+  if (needle.raw() == CanonicalType()) {
+    return 0;
+  }
+  REUSABLE_OBJECT_HANDLESCOPE(isolate);
+  Object& types = isolate->ObjectHandle();
+  types = canonical_types();
+  if (types.IsNull()) {
+    return -1;
+  }
+  const intptr_t len = Array::Cast(types).Length();
+  REUSABLE_ABSTRACT_TYPE_HANDLESCOPE(isolate);
+  AbstractType& type = isolate->AbstractTypeHandle();
+  for (intptr_t i = 0; i < len; i++) {
+    type ^= Array::Cast(types).At(i);
+    if (needle.raw() == type.raw()) {
+      return i;
+    }
+  }
+  // No type found.
+  return -1;
+}
+
+
+RawType* Class::CanonicalTypeFromIndex(intptr_t idx) const {
+  Type& type = Type::Handle();
+  if (idx == 0) {
+    type = CanonicalType();
+    if (!type.IsNull()) {
+      return type.raw();
+    }
+  }
+  Object& types = Object::Handle(canonical_types());
+  if (types.IsNull()) {
+    return Type::null();
+  }
+  if ((idx < 0) || (idx >= Array::Cast(types).Length())) {
+    return Type::null();
+  }
+  type ^= Array::Cast(types).At(idx);
+  ASSERT(!type.IsNull());
+  return type.raw();
+}
+
+
 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::IsFunctionClass() const {
   return raw() == Type::Handle(Type::Function()).type_class();
 }
@@ skipping 342 matching lines @@
   Isolate* isolate = Isolate::Current();
   if (EnsureIsFinalized(isolate) != Error::null()) {
     return Function::null();
   }
   REUSABLE_ARRAY_HANDLESCOPE(isolate);
   REUSABLE_FUNCTION_HANDLESCOPE(isolate);
   REUSABLE_STRING_HANDLESCOPE(isolate);
   Array& funcs = isolate->ArrayHandle();
   funcs ^= functions();
   ASSERT(!funcs.IsNull());
-  intptr_t len = funcs.Length();
+  const intptr_t len = funcs.Length();
   Function& function = isolate->FunctionHandle();
   String& function_name = isolate->StringHandle();
   for (intptr_t i = 0; i < len; i++) {
     function ^= funcs.At(i);
     function_name ^= function.name();
     if (String::EqualsIgnoringPrivateKey(function_name, name)) {
       return CheckFunctionType(function, type);
     }
   }
   // No function found.
@@ skipping 322 matching lines @@
 static intptr_t FinalizeHash(uword hash) {
   hash += hash << 3;
   hash ^= hash >> 11;
   hash += hash << 15;
   return hash;
 }
 
 
 intptr_t TypeArguments::Hash() const {
   if (IsNull()) return 0;
-  uword result = 0;
   const intptr_t num_types = Length();
+  if (IsRaw(0, num_types)) return 0;
+  intptr_t result = 0;
   AbstractType& type = AbstractType::Handle();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     result += type.Hash();
     result += result << 10;
     result ^= result >> 6;
   }
   return FinalizeHash(result);
 }
 
@@ skipping 95 matching lines @@
   }
   return true;
 }
 
 
 void TypeArguments::PrintToJSONStream(JSONStream* stream, bool ref) const {
   JSONObject jsobj(stream);
 }
 
 
+bool TypeArguments::HasInstantiations() const {
+  const Array& prior_instantiations = Array::Handle(instantiations());
+  ASSERT(prior_instantiations.Length() > 0);  // Always at least a sentinel.
+  return prior_instantiations.Length() > 1;
+}
+
+
+intptr_t TypeArguments::NumInstantiations() const {
+  const Array& prior_instantiations = Array::Handle(instantiations());
+  ASSERT(prior_instantiations.Length() > 0);  // Always at least a sentinel.
+  intptr_t i = 0;
+  while (prior_instantiations.At(i) != Smi::New(StubCode::kNoInstantiator)) {
+    i += 2;
+  }
+  return i/2;
+}
+
+
 RawArray* TypeArguments::instantiations() const {
   return raw_ptr()->instantiations_;
 }
 
+
 void TypeArguments::set_instantiations(const Array& value) const {
   ASSERT(!value.IsNull());
   StorePointer(&raw_ptr()->instantiations_, value.raw());
 }
 
 
 intptr_t TypeArguments::Length() const {
   ASSERT(!IsNull());
   return Smi::Value(raw_ptr()->length_);
 }
@@ skipping 219 matching lines @@
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error) const {
   ASSERT(!IsInstantiated());
   ASSERT(instantiator_type_arguments.IsNull() ||
          instantiator_type_arguments.IsCanonical());
   // Lookup instantiator and, if found, return paired instantiated result.
   Array& prior_instantiations = Array::Handle(instantiations());
   ASSERT(!prior_instantiations.IsNull() && prior_instantiations.IsArray());
   // The instantiations cache is initialized with Object::zero_array() and is
   // therefore guaranteed to contain kNoInstantiator. No length check needed.
-  ASSERT(prior_instantiations.Length() > 0);
+  ASSERT(prior_instantiations.Length() > 0);  // Always at least a sentinel.
   intptr_t index = 0;
   while (true) {
     if (prior_instantiations.At(index) == instantiator_type_arguments.raw()) {
       return TypeArguments::RawCast(prior_instantiations.At(index + 1));
     }
     if (prior_instantiations.At(index) == Smi::New(StubCode::kNoInstantiator)) {
       break;
     }
     index += 2;
   }
   // Cache lookup failed. Instantiate the type arguments.
   TypeArguments& result = TypeArguments::Handle();
   result = InstantiateFrom(instantiator_type_arguments, bound_error);
   if ((bound_error != NULL) && !bound_error->IsNull()) {
     return result.raw();
   }
   // Instantiation did not result in bound error. Canonicalize type arguments.
   result = result.Canonicalize();
+  // InstantiateAndCanonicalizeFrom is not reentrant. It cannot have been called
+  // indirectly, so the prior_instantiations array cannot have grown.
+  ASSERT(prior_instantiations.raw() == instantiations());
   // Add instantiator and result to instantiations array.
   intptr_t length = prior_instantiations.Length();
   if ((index + 2) >= length) {
     // Grow the instantiations array.
     // The initial array is Object::zero_array() of length 1.
     length = (length > 64) ?
         (length + 64) :
         ((length == 1) ? 3 : ((length - 1) * 2 + 1));
     prior_instantiations =
         Array::Grow(prior_instantiations, length, Heap::kOld);
@@ skipping 42 matching lines @@
 void TypeArguments::SetLength(intptr_t value) const {
   ASSERT(!IsCanonical());
   // This is only safe because we create a new Smi, which does not cause
   // heap allocation.
   raw_ptr()->length_ = Smi::New(value);
 }
 
 
 static void GrowCanonicalTypeArguments(Isolate* isolate, const Array& table) {
   // Last element of the array is the number of used elements.
-  intptr_t table_size = table.Length() - 1;
-  intptr_t new_table_size = table_size * 2;
+  const intptr_t table_size = table.Length() - 1;
+  const intptr_t new_table_size = table_size * 2;
   Array& new_table = Array::Handle(isolate, Array::New(new_table_size + 1));
   // Copy all elements from the original table to the newly allocated
   // array.
   TypeArguments& element = TypeArguments::Handle(isolate);
   Object& new_element = Object::Handle(isolate);
   for (intptr_t i = 0; i < table_size; i++) {
     element ^= table.At(i);
     if (!element.IsNull()) {
       intptr_t hash = element.Hash();
       ASSERT(Utils::IsPowerOfTwo(new_table_size));
@@ skipping 15 matching lines @@
 
 
 static void InsertIntoCanonicalTypeArguments(Isolate* isolate,
                                              const Array& table,
                                              const TypeArguments& arguments,
                                              intptr_t index) {
   arguments.SetCanonical();  // Mark object as being canonical.
   table.SetAt(index, arguments);  // Remember the new element.
   // Update used count.
   // Last element of the array is the number of used elements.
-  intptr_t table_size = table.Length() - 1;
-  intptr_t used_elements = Smi::Value(Smi::RawCast(table.At(table_size))) + 1;
+  const intptr_t table_size = table.Length() - 1;
+  const intptr_t used_elements =
+      Smi::Value(Smi::RawCast(table.At(table_size))) + 1;
   const Smi& used = Smi::Handle(isolate, Smi::New(used_elements));
   table.SetAt(table_size, used);
 
   // Rehash if table is 75% full.
   if (used_elements > ((table_size / 4) * 3)) {
     GrowCanonicalTypeArguments(isolate, table);
   }
 }
 
 
 static intptr_t FindIndexInCanonicalTypeArguments(
     Isolate* isolate,
     const Array& table,
     const TypeArguments& arguments,
     intptr_t hash) {
   // Last element of the array is the number of used elements.
-  intptr_t table_size = table.Length() - 1;
+  const intptr_t table_size = table.Length() - 1;
   ASSERT(Utils::IsPowerOfTwo(table_size));
   intptr_t index = hash & (table_size - 1);
 
   TypeArguments& current = TypeArguments::Handle(isolate);
   current ^= table.At(index);
   while (!current.IsNull() && !current.Equals(arguments)) {
     index = (index + 1) & (table_size - 1);  // Move to next element.
     current ^= table.At(index);
   }
   return index;  // Index of element if found or slot into which to add it.
@@ skipping 18 matching lines @@
   return clone.raw();
 }
 
 
 RawTypeArguments* TypeArguments::Canonicalize(
     GrowableObjectArray* trail) const {
   if (IsNull() || IsCanonical()) {
     ASSERT(IsOld());
     return this->raw();
   }
+  const intptr_t num_types = Length();
+  if (IsRaw(0, num_types)) {
+    return TypeArguments::null();
+  }
   Isolate* isolate = Isolate::Current();
   ObjectStore* object_store = isolate->object_store();
-  const Array& table = Array::Handle(isolate,
-                                     object_store->canonical_type_arguments());
-  ASSERT(table.Length() > 0);
-  intptr_t index = FindIndexInCanonicalTypeArguments(isolate,
-                                                     table,
-                                                     *this,
-                                                     Hash());
+  Array& table = Array::Handle(isolate,
+                               object_store->canonical_type_arguments());
+  // Last element of the array is the number of used elements.
+  const intptr_t used_elements =
+      Smi::Value(Smi::RawCast(table.At(table.Length() - 1)));
+  const intptr_t hash = Hash();
+  intptr_t index =
+      FindIndexInCanonicalTypeArguments(isolate, table, *this, hash);
   TypeArguments& result = TypeArguments::Handle(isolate);
   result ^= table.At(index);
   if (result.IsNull()) {
     // Canonicalize each type argument.
-    const intptr_t num_types = Length();
-    AbstractType& type = AbstractType::Handle(isolate);
+    AbstractType& type_arg = AbstractType::Handle(isolate);
     for (intptr_t i = 0; i < num_types; i++) {
-      type = TypeAt(i);
-      type = type.Canonicalize(trail);
-      SetTypeAt(i, type);
+      type_arg = TypeAt(i);
+      type_arg = type_arg.Canonicalize(trail);
+      SetTypeAt(i, type_arg);
     }
-    // Make sure we have an old space object and add it to the table.
-    if (this->IsNew()) {
-      result ^= Object::Clone(*this, Heap::kOld);
-    } else {
-      result ^= this->raw();
+    // Canonicalization of a recursive type may change its hash.
+    const intptr_t new_hash = Hash();
+    // Canonicalization of the type argument's own type arguments may add an
+    // entry to the table, or even grow the table, and thereby change the
+    // previously calculated index.
+    table = object_store->canonical_type_arguments();
+    if ((new_hash != hash) ||
+        (Smi::Value(Smi::RawCast(table.At(table.Length() - 1)))
+         != used_elements)) {
+      index =
+          FindIndexInCanonicalTypeArguments(isolate, table, *this, new_hash);
+      result ^= table.At(index);
     }
-    ASSERT(result.IsOld());
-    InsertIntoCanonicalTypeArguments(isolate, table, result, index);
+    if (result.IsNull()) {
+      // Make sure we have an old space object and add it to the table.
+      if (this->IsNew()) {
+        result ^= Object::Clone(*this, Heap::kOld);
+      } else {
+        result ^= this->raw();
+      }
+      ASSERT(result.IsOld());
+      InsertIntoCanonicalTypeArguments(isolate, table, result, index);
+    }
   }
   ASSERT(result.Equals(*this));
   ASSERT(!result.IsNull());
   ASSERT(result.IsTypeArguments());
   ASSERT(result.IsCanonical());
   return result.raw();
 }
 
 
 const char* TypeArguments::ToCString() const {
@@ skipping 3490 matching lines @@
   // Rehash all elements from the original dictionary
   // to the newly allocated array.
   Object& entry = Class::Handle();
   String& entry_name = String::Handle();
   Object& new_entry = Object::Handle();
   for (intptr_t i = 0; i < dict_size; i++) {
     entry = dict.At(i);
     if (!entry.IsNull()) {
       entry_name = entry.DictionaryName();
       ASSERT(!entry_name.IsNull());
-      intptr_t hash = entry_name.Hash();
+      const intptr_t hash = entry_name.Hash();
       intptr_t index = hash % new_dict_size;
       new_entry = new_dict.At(index);
       while (!new_entry.IsNull()) {
         index = (index + 1) % new_dict_size;  // Move to next element.
         new_entry = new_dict.At(index);
       }
       new_dict.SetAt(index, entry);
     }
   }
   // Copy used count.
@@ skipping 5085 matching lines @@
     }
     ASSERT(this->Equals(type));
     return type.raw();
   }
 
   Array& canonical_types = Array::Handle(isolate);
   canonical_types ^= cls.canonical_types();
   if (canonical_types.IsNull()) {
     canonical_types = empty_array().raw();
   }
-  const intptr_t length = canonical_types.Length();
+  intptr_t length = canonical_types.Length();
   // Linear search to see whether this type is already present in the
   // list of canonicalized types.
   // TODO(asiva): Try to re-factor this lookup code to make sharing
   // easy between the 4 versions of this loop.
   intptr_t index = 0;
   while (index < length) {
     type ^= canonical_types.At(index);
     if (type.IsNull()) {
       break;
     }
     ASSERT(type.IsFinalized());
     if (this->Equals(type)) {
       return type.raw();
     }
     index++;
   }
+  // The type was not found in the table. It is not canonical yet.
+
   // Canonicalize the type arguments.
   TypeArguments& type_args = TypeArguments::Handle(isolate, arguments());
   // In case the type is first canonicalized at runtime, its type argument
   // vector may be longer than necessary. This is not an issue.
   ASSERT(type_args.IsNull() || (type_args.Length() >= cls.NumTypeArguments()));
   type_args = type_args.Canonicalize(trail);
   set_arguments(type_args);
+
+  // Canonicalizing the type arguments may have changed the index, may have
+  // grown the table, or may even have canonicalized this type.
+  canonical_types ^= cls.canonical_types();
+  if (canonical_types.IsNull()) {
+    canonical_types = empty_array().raw();
+  }
+  length = canonical_types.Length();
+  while (index < length) {
+    type ^= canonical_types.At(index);
+    if (type.IsNull()) {
+      break;
+    }
+    ASSERT(type.IsFinalized());
+    if (this->Equals(type)) {
+      return type.raw();
+    }
+    index++;
+  }
+
   // The type needs to be added to the list. Grow the list if it is full.
   if (index == length) {
     const intptr_t new_length = (length > 64) ?
         (length + 64) :
         ((length == 0) ? 1 : (length * 2));
     const Array& new_canonical_types = Array::Handle(
         isolate, Array::Grow(canonical_types, new_length, Heap::kOld));
     cls.set_canonical_types(new_canonical_types);
     new_canonical_types.SetAt(index, *this);
   } else {
@@ skipping 91 matching lines @@
     const TypeArguments& type_arguments = TypeArguments::Handle(arguments());
     const char* class_name;
     if (HasResolvedTypeClass()) {
       class_name = String::Handle(
           Class::Handle(type_class()).Name()).ToCString();
     } else {
       class_name = UnresolvedClass::Handle(unresolved_class()).ToCString();
     }
     if (type_arguments.IsNull()) {
       const char* format = "Type: class '%s'";
-      intptr_t len = OS::SNPrint(NULL, 0, format, class_name) + 1;
+      const intptr_t len = OS::SNPrint(NULL, 0, format, class_name) + 1;
       char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
       OS::SNPrint(chars, len, format, class_name);
       return chars;
     } else {
       const char* format = "Type: class '%s', args:[%s]";
       const char* args_cstr = TypeArguments::Handle(arguments()).ToCString();
       intptr_t len = OS::SNPrint(NULL, 0, format, class_name, args_cstr) + 1;
       char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
       OS::SNPrint(chars, len, format, class_name, args_cstr);
       return chars;
@@ skipping 125 matching lines @@
     if (trail->At(i) == this->raw()) {
       ASSERT(trail->At(i + 1) != Object::null());
       return trail->At(i + 1);
     }
   }
   return Object::null();
 }
 
 
 void TypeRef::AddOnlyBuddyToTrail(GrowableObjectArray** trail,
-                              const Object& buddy) const {
+                                  const Object& buddy) const {
   if (*trail == NULL) {
     *trail = &GrowableObjectArray::ZoneHandle(GrowableObjectArray::New());
   } else {
     ASSERT(OnlyBuddyInTrail(*trail) == Object::null());
   }
   (*trail)->Add(*this);
   (*trail)->Add(buddy);
 }
 
 
@@ skipping 4278 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Instance::PrintToJSONStream(stream, ref);
 }
 
 
 }  // namespace dart