Detect and reject illegal recursive types (non-contractive 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 3994 matching lines @@
   OS::SNPrint(chars, len, format, cname);
   return chars;
 }
 
 
 void UnresolvedClass::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Object::PrintToJSONStream(stream, ref);
 }
 
 
-static intptr_t FinalizeHash(uword hash) {
+static intptr_t CombineHashes(uint32_t hash, uint32_t other_hash) {
+  hash += other_hash;
+  hash += hash << 10;
+  hash ^= hash >> 6;  // Logical shift, unsigned hash.
+  return hash;
+}
+
+
+static intptr_t FinalizeHash(uint32_t hash) {
   hash += hash << 3;
-  hash ^= hash >> 11;
+  hash ^= hash >> 11;  // Logical shift, unsigned hash.
   hash += hash << 15;
   return hash;
 }
 
 
 intptr_t TypeArguments::Hash() const {
   if (IsNull()) return 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;
+    result = CombineHashes(result, type.Hash());
   }
   return FinalizeHash(result);
 }
 
 
 RawString* TypeArguments::SubvectorName(intptr_t from_index,
                                         intptr_t len,
                                         NameVisibility name_visibility) const {
   ASSERT(from_index + len <= Length());
   String& name = String::Handle();
@@ skipping 10 matching lines @@
       strings.SetAt(s++, Symbols::CommaSpace());
     }
   }
   strings.SetAt(s++, Symbols::RAngleBracket());
   ASSERT(s == num_strings);
   name = String::ConcatAll(strings);
   return Symbols::New(name);
 }
 
 
-bool TypeArguments::IsEquivalent(const TypeArguments& other,
-                                 GrowableObjectArray* trail) const {
+bool TypeArguments::IsSubvectorEquivalent(const TypeArguments& other,
+                                          intptr_t from_index,
+                                          intptr_t len,
+                                          GrowableObjectArray* trail) const {
   if (this->raw() == other.raw()) {
     return true;
   }
   if (IsNull() || other.IsNull()) {
     return false;
   }
   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++) {
+  for (intptr_t i = from_index; i < from_index + len; i++) {
     type = TypeAt(i);
     other_type = other.TypeAt(i);
     if (!type.IsEquivalent(other_type, trail)) {
       return false;
     }
   }
   return true;
 }
 
 
+bool TypeArguments::IsRecursive() const {
+  if (IsNull()) return false;
+  const intptr_t num_types = Length();
+  AbstractType& type = AbstractType::Handle();
+  for (intptr_t i = 0; i < num_types; i++) {
+    type = TypeAt(i);
+    if (type.IsRecursive()) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
 bool TypeArguments::IsDynamicTypes(bool raw_instantiated,
                                    intptr_t from_index,
                                    intptr_t len) const {
   ASSERT(Length() >= (from_index + len));
   AbstractType& type = AbstractType::Handle();
   Class& type_class = Class::Handle();
   for (intptr_t i = 0; i < len; i++) {
     type = TypeAt(from_index + i);
-    ASSERT(!type.IsNull());
     if (!type.HasResolvedTypeClass()) {
       if (raw_instantiated && type.IsTypeParameter()) {
         // An uninstantiated type parameter is equivalent to dynamic (even in
         // the presence of a malformed bound in checked mode).
         continue;
       }
       return false;
     }
     type_class = type.type_class();
     if (!type_class.IsDynamicClass()) {
@@ skipping 147 matching lines @@
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     if (!type.IsResolved()) {
       return false;
     }
   }
   return true;
 }
 
 
-bool TypeArguments::IsInstantiated(GrowableObjectArray* trail) const {
+bool TypeArguments::IsSubvectorInstantiated(intptr_t from_index,
+                                            intptr_t len,
+                                            GrowableObjectArray* trail) const {
+  ASSERT(!IsNull());
   AbstractType& type = AbstractType::Handle();
-  const intptr_t num_types = Length();
-  for (intptr_t i = 0; i < num_types; i++) {
-    type = TypeAt(i);
-    if (!type.IsBeingFinalized() && !type.IsInstantiated(trail)) {
+  for (intptr_t i = 0; i < len; i++) {
+    type = TypeAt(from_index + i);
+    if (!type.IsInstantiated(trail)) {
       return false;
     }
   }
   return true;
 }
 
 
 bool TypeArguments::IsUninstantiatedIdentity() const {
   ASSERT(!IsInstantiated());
   AbstractType& type = AbstractType::Handle();
@@ skipping 143 matching lines @@
       IsUninstantiatedIdentity() &&
       (instantiator_type_arguments.Length() == Length())) {
     return instantiator_type_arguments.raw();
   }
   const intptr_t num_types = Length();
   TypeArguments& instantiated_array =
       TypeArguments::Handle(TypeArguments::New(num_types, Heap::kNew));
   AbstractType& type = AbstractType::Handle();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
-    if (!type.IsBeingFinalized() && !type.IsInstantiated()) {
+    if (!type.IsInstantiated()) {
       type = type.InstantiateFrom(instantiator_type_arguments,
                                   bound_error,
                                   trail);
     }
     instantiated_array.SetTypeAt(i, type);
   }
   return instantiated_array.raw();
 }
 
 
@@ skipping 95 matching lines @@
   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();
+      const intptr_t hash = element.Hash();
       ASSERT(Utils::IsPowerOfTwo(new_table_size));
       intptr_t index = hash & (new_table_size - 1);
       new_element = new_table.At(index);
       while (!new_element.IsNull()) {
         index = (index + 1) & (new_table_size - 1);  // Move to next element.
         new_element = new_table.At(index);
       }
       new_table.SetAt(index, element);
     }
   }
@@ skipping 12 matching lines @@
   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.
   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);
 
+#ifdef DEBUG
+  // Verify that there are no duplicates.
+  // Duplicates could appear if hash values are not kept constant across
+  // snapshots, e.g. if class ids are not preserved by the snapshots.
+  TypeArguments& other_arguments = TypeArguments::Handle();
+  for (intptr_t i = 0; i < table_size; i++) {
+    if ((i != index) && (table.At(i) != TypeArguments::null())) {
+      other_arguments ^= table.At(i);
+      if (arguments.Equals(other_arguments)) {
+        // Recursive types may be equal, but have different hashes.
+        ASSERT(arguments.IsRecursive());
+        ASSERT(other_arguments.IsRecursive());
+        ASSERT(arguments.Hash() != other_arguments.Hash());
+      }
+    }
+  }
+#endif
+
   // 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,
@@ skipping 41 matching lines @@
   }
   const intptr_t num_types = Length();
   if (IsRaw(0, num_types)) {
     return TypeArguments::null();
   }
   Isolate* isolate = Isolate::Current();
   ObjectStore* object_store = isolate->object_store();
   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 =
+  const intptr_t num_used =
       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.
     AbstractType& type_arg = AbstractType::Handle(isolate);
     for (intptr_t i = 0; i < num_types; i++) {
       type_arg = TypeAt(i);
       type_arg = type_arg.Canonicalize(trail);
       SetTypeAt(i, type_arg);
     }
-    // Canonicalization of a recursive type may change its hash.
-    const intptr_t new_hash = Hash();
+    // Canonicalization of a type should not change its hash. Verify.
+    ASSERT(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);
+    if (Smi::Value(Smi::RawCast(table.At(table.Length() - 1))) != num_used) {
+      index = FindIndexInCanonicalTypeArguments(isolate, table, *this, hash);
       result ^= table.At(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());
@@ skipping 7972 matching lines @@
 
 
 bool AbstractType::IsEquivalent(const Instance& other,
                                 GrowableObjectArray* trail) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
+bool AbstractType::IsRecursive() const {
+  // AbstractType is an abstract class.
+  UNREACHABLE();
+  return false;
+}
+
+
 RawAbstractType* AbstractType::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
     GrowableObjectArray* trail) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return NULL;
 }
 
 
 RawAbstractType* AbstractType::CloneUnfinalized() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return NULL;
 }
 
 
 RawAbstractType* AbstractType::Canonicalize(GrowableObjectArray* trail) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return NULL;
 }
 
 
+RawObject* AbstractType::OnlyBuddyInTrail(GrowableObjectArray* trail) const {
+  if (trail == NULL) {
+    return Object::null();
+  }
+  const intptr_t len = trail->Length();
+  ASSERT((len % 2) == 0);
+  for (intptr_t i = 0; i < len; i += 2) {
+    if (trail->At(i) == this->raw()) {
+      ASSERT(trail->At(i + 1) != Object::null());
+      return trail->At(i + 1);
+    }
+  }
+  return Object::null();
+}
+
+
+void AbstractType::AddOnlyBuddyToTrail(GrowableObjectArray** trail,
+                                       const Object& buddy) const {
+  if (*trail == NULL) {
+    *trail = &GrowableObjectArray::ZoneHandle(GrowableObjectArray::New());
+  } else {
+    ASSERT(OnlyBuddyInTrail(*trail) == Object::null());
+  }
+  (*trail)->Add(*this);
+  (*trail)->Add(buddy);
+}
+
+
 RawString* AbstractType::BuildName(NameVisibility name_visibility) const {
   if (IsBoundedType()) {
     const AbstractType& type = AbstractType::Handle(
         BoundedType::Cast(*this).type());
     if (name_visibility == kUserVisibleName) {
       return type.BuildName(kUserVisibleName);
     }
     String& type_name = String::Handle(type.BuildName(kInternalName));
     type_name = String::Concat(type_name, Symbols::SpaceExtendsSpace());
     // Build the bound name without causing divergence.
@@ skipping 19 matching lines @@
   }
   // If the type is still being finalized, we may be reporting an error about
   // a malformed 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());
-    num_type_params = cls.NumTypeParameters();  // Do not print the full vector.
+    if (IsResolved() || !cls.IsMixinApplication()) {
+      // Do not print the full vector, but only the declared type parameters.
+      num_type_params = cls.NumTypeParameters();
+    } else {
+      // Do not print the type parameters of an unresolved mixin application,
+      // since it would prematurely trigger the application of the mixin type.
+      num_type_params = 0;
+    }
     if (name_visibility == kInternalName) {
       class_name = cls.Name();
     } else {
       ASSERT(name_visibility == kUserVisibleName);
       // Map internal types to their corresponding public interfaces.
       class_name = cls.UserVisibleName();
     }
     if (num_type_params > num_args) {
       first_type_param_index = 0;
       if (!IsFinalized() || IsBeingFinalized() || IsMalformed()) {
@@ skipping 431 matching lines @@
 }
 
 
 bool Type::IsInstantiated(GrowableObjectArray* trail) const {
   if (raw_ptr()->type_state_ == RawType::kFinalizedInstantiated) {
     return true;
   }
   if (raw_ptr()->type_state_ == RawType::kFinalizedUninstantiated) {
     return false;
   }
+  if (arguments() == TypeArguments::null()) {
+    return true;
+  }
   const TypeArguments& args = TypeArguments::Handle(arguments());
-  return args.IsNull() || args.IsInstantiated(trail);
+  const intptr_t num_type_args = args.Length();
+  intptr_t len = num_type_args;  // Check the full vector of type args.
+  ASSERT(num_type_args > 0);
+  // This type is not instantiated if it refers to type parameters.
+  // This IsInstantiated() call may be invoked on an unresolved signature type.
+  // Although this type may still be unresolved, the type parameters it may
+  // refer to are resolved by definition. We can therefore return the correct
+  // result even for an unresolved type. We just need to look at all type
+  // arguments and not just at the type parameters.
+  if (HasResolvedTypeClass()) {
+    const Class& cls = Class::Handle(type_class());
+    len = cls.NumTypeParameters();  // Check the type parameters only.
+    ASSERT(num_type_args == cls.NumTypeArguments());
+  }
+  return (len == 0) || args.IsSubvectorInstantiated(num_type_args - len, len);
 }
 
 
 RawAbstractType* Type::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
     GrowableObjectArray* trail) const {
   ASSERT(IsFinalized() || IsBeingFinalized());
   ASSERT(!IsInstantiated());
   // Return the uninstantiated type unchanged if malformed. No copy needed.
   if (IsMalformed()) {
     return raw();
   }
-  TypeArguments& type_arguments = TypeArguments::Handle(arguments());
-  type_arguments = type_arguments.InstantiateFrom(instantiator_type_arguments,
-                                                  bound_error,
-                                                  trail);
   // Note that the type class has to be resolved at this time, but not
-  // necessarily finalized yet. We may be checking bounds at compile time.
+  // necessarily finalized yet. We may be checking bounds at compile time or
+  // finalizing the type argument vector of a recursive type.
   const Class& cls = Class::Handle(type_class());
   // This uninstantiated type is not modified, as it can be instantiated
   // with different instantiators.
   Type& instantiated_type = Type::Handle(
-      Type::New(cls, type_arguments, token_pos()));
-  ASSERT(type_arguments.IsNull() ||
-         (type_arguments.Length() == cls.NumTypeArguments()));
+      Type::New(cls, TypeArguments::Handle(), token_pos()));
+  if (arguments() != TypeArguments::null()) {
+    TypeArguments& type_arguments = TypeArguments::Handle(arguments());
+    ASSERT(type_arguments.Length() == cls.NumTypeArguments());
+    if (type_arguments.IsRecursive()) {
+      AddOnlyBuddyToTrail(&trail, instantiated_type);
+    }
+    type_arguments = type_arguments.InstantiateFrom(instantiator_type_arguments,
+                                                    bound_error,
+                                                    trail);
+    instantiated_type.set_arguments(type_arguments);
+  }
   instantiated_type.SetIsFinalized();
   // Canonicalization is not part of instantiation.
   return instantiated_type.raw();
 }
 
 
 bool Type::IsEquivalent(const Instance& other,
                         GrowableObjectArray* trail) const {
   ASSERT(!IsNull());
   if (raw() == other.raw()) {
@@ skipping 29 matching lines @@
   if (num_type_params == 0) {
     // Shortcut unnecessary handle allocation below.
     return true;
   }
   const intptr_t num_type_args = cls.NumTypeArguments();
   const intptr_t from_index = num_type_args - num_type_params;
   const TypeArguments& type_args = TypeArguments::Handle(isolate, arguments());
   const TypeArguments& other_type_args = TypeArguments::Handle(
       isolate, other_type.arguments());
   if (type_args.IsNull()) {
-    return other_type_args.IsRaw(from_index, num_type_params);
+    // Ignore from_index.
+    return other_type_args.IsRaw(0, num_type_params);
   }
   if (other_type_args.IsNull()) {
-    return type_args.IsRaw(from_index, num_type_params);
+    // Ignore from_index.
+    return type_args.IsRaw(0, num_type_params);
   }
-  ASSERT(type_args.Length() >= (from_index + num_type_params));
-  ASSERT(other_type_args.Length() >= (from_index + num_type_params));
-  AbstractType& type_arg = AbstractType::Handle(isolate);
-  AbstractType& other_type_arg = AbstractType::Handle(isolate);
-  for (intptr_t i = 0; i < num_type_params; i++) {
-    type_arg = type_args.TypeAt(from_index + i);
-    other_type_arg = other_type_args.TypeAt(from_index + i);
-    if (!type_arg.IsEquivalent(other_type_arg, trail)) {
-      return false;
+  if (!type_args.IsSubvectorEquivalent(other_type_args,
+                                       from_index,
+                                       num_type_params)) {
+    return false;
+  }
+#ifdef DEBUG
+  if (from_index > 0) {
+    // Verify that the type arguments of the super class match, since they
+    // depend solely on the type parameters that were just verified to match.
+    ASSERT(type_args.Length() >= (from_index + num_type_params));
+    ASSERT(other_type_args.Length() >= (from_index + num_type_params));
+    AbstractType& type_arg = AbstractType::Handle(isolate);
+    AbstractType& other_type_arg = AbstractType::Handle(isolate);
+    for (intptr_t i = 0; i < from_index; i++) {
+      type_arg = type_args.TypeAt(i);
+      other_type_arg = other_type_args.TypeAt(i);
+      ASSERT(type_arg.IsEquivalent(other_type_arg, trail));
     }
   }
+#endif
   return true;
 }
 
 
+bool Type::IsRecursive() const {
+  return TypeArguments::Handle(arguments()).IsRecursive();
+}
+
+
 RawAbstractType* Type::CloneUnfinalized() const {
   ASSERT(IsResolved());
   if (IsFinalized()) {
     return raw();
   }
   ASSERT(!IsMalformed());  // Malformed types are finalized.
   ASSERT(!IsBeingFinalized());  // Cloning must occur prior to finalization.
   TypeArguments& type_args = TypeArguments::Handle(arguments());
   type_args = type_args.CloneUnfinalized();
   const Class& type_cls = Class::Handle(type_class());
@@ skipping 117 matching lines @@
 #endif
   ASSERT(IsOld());
   ASSERT(type_args.IsNull() || type_args.IsOld());
   SetCanonical();
   return this->raw();
 }
 
 
 intptr_t Type::Hash() const {
   ASSERT(IsFinalized());
-  uword result = 1;
+  intptr_t result = 1;
   if (IsMalformed()) return result;
-  result += Class::Handle(type_class()).id();
-  result += TypeArguments::Handle(arguments()).Hash();
+  result = CombineHashes(result, Class::Handle(type_class()).id());
+  result = CombineHashes(result, TypeArguments::Handle(arguments()).Hash());
   return FinalizeHash(result);
 }
 
 
 void Type::set_type_class(const Object& value) const {
   ASSERT(!value.IsNull() && (value.IsClass() || value.IsUnresolvedClass()));
   StorePointer(&raw_ptr()->type_class_, value.raw());
 }
 
 
@@ skipping 46 matching lines @@
           Class::Handle(type_class()).Name()).ToCString();
     } else {
       class_name = UnresolvedClass::Handle(unresolved_class()).ToCString();
     }
     if (type_arguments.IsNull()) {
       const char* format = "Type: class '%s'";
       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 if (IsFinalized() && IsRecursive()) {
+      const char* format = "Type: (@%" Px " H%" Px ") class '%s', args:[%s]";
+      const intptr_t hash = Hash();
+      const char* args_cstr = TypeArguments::Handle(arguments()).ToCString();
+      const intptr_t len =
+          OS::SNPrint(NULL, 0, format, raw(), hash, class_name, args_cstr) + 1;
+      char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
+      OS::SNPrint(chars, len, format, raw(), hash, class_name, args_cstr);
+      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;
+      const 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;
     }
   } else {
     return "Unresolved Type";
   }
 }
 
 
@@ skipping 39 matching lines @@
     return true;
   }
   return AbstractType::Handle(type()).IsEquivalent(other, trail);
 }
 
 
 RawAbstractType* TypeRef::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
     GrowableObjectArray* trail) const {
-  TypeRef& instantiated_type_ref = TypeRef::Handle();
-  instantiated_type_ref ^= OnlyBuddyInTrail(trail);
-  if (!instantiated_type_ref.IsNull()) {
-    return instantiated_type_ref.raw();
+  AbstractType& ref_type = AbstractType::Handle(type());
+  ASSERT(!ref_type.IsTypeRef());
+  AbstractType& instantiated_ref_type = AbstractType::Handle();
+  instantiated_ref_type ^= ref_type.OnlyBuddyInTrail(trail);
+  if (instantiated_ref_type.IsNull()) {
+    // The referenced type is first encountered here during instantiation.
+    instantiated_ref_type = ref_type.InstantiateFrom(
+        instantiator_type_arguments, bound_error, trail);
   }
-  instantiated_type_ref = TypeRef::New(Type::Handle(Type::DynamicType()));
-  AddOnlyBuddyToTrail(&trail, instantiated_type_ref);
-  const AbstractType& ref_type = AbstractType::Handle(type());
-  ASSERT(!ref_type.IsTypeRef());
-  const AbstractType& instantiated_ref_type = AbstractType::Handle(
-      ref_type.InstantiateFrom(instantiator_type_arguments,
-                               bound_error,
-                               trail));
-  instantiated_type_ref.set_type(instantiated_ref_type);
-  return instantiated_type_ref.raw();
+  ASSERT(!instantiated_ref_type.IsTypeRef());
+  return TypeRef::New(instantiated_ref_type);
 }
 
 
 void TypeRef::set_type(const AbstractType& value) const {
   ASSERT(value.HasResolvedTypeClass());
   StorePointer(&raw_ptr()->type_, value.raw());
 }
 
 
 // A TypeRef cannot be canonical by definition. Only its referenced type can be.
 // Consider the type Derived, where class Derived extends Base<Derived>.
 // The first type argument of its flattened type argument vector is Derived,
-// i.e. itself, but pointer equality is not possible.
+// represented by a TypeRef pointing to itself.
 RawAbstractType* TypeRef::Canonicalize(GrowableObjectArray* trail) const {
   if (TestAndAddToTrail(&trail)) {
     return raw();
   }
   AbstractType& ref_type = AbstractType::Handle(type());
   ref_type = ref_type.Canonicalize(trail);
   set_type(ref_type);
   return raw();
 }
 
 
 intptr_t TypeRef::Hash() const {
   // Do not calculate the hash of the referenced type to avoid divergence.
-  uword result = Class::Handle(AbstractType::Handle(type()).type_class()).id();
+  const intptr_t result =
+      Class::Handle(AbstractType::Handle(type()).type_class()).id();
   return FinalizeHash(result);
 }
 
 
 bool TypeRef::TestAndAddToTrail(GrowableObjectArray** trail) const {
   if (*trail == NULL) {
     *trail = &GrowableObjectArray::ZoneHandle(GrowableObjectArray::New());
   } else {
     const intptr_t len = (*trail)->Length();
     for (intptr_t i = 0; i < len; i++) {
@@ skipping 20 matching lines @@
         return true;
       }
     }
   }
   (*trail)->Add(*this);
   (*trail)->Add(buddy);
   return false;
 }
 
 
-RawObject* TypeRef::OnlyBuddyInTrail(GrowableObjectArray* trail) const {
-  if (trail == NULL) {
-    return Object::null();
-  }
-  const intptr_t len = trail->Length();
-  ASSERT((len % 2) == 0);
-  for (intptr_t i = 0; i < len; i += 2) {
-    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 {
-  if (*trail == NULL) {
-    *trail = &GrowableObjectArray::ZoneHandle(GrowableObjectArray::New());
-  } else {
-    ASSERT(OnlyBuddyInTrail(*trail) == Object::null());
-  }
-  (*trail)->Add(*this);
-  (*trail)->Add(buddy);
-}
-
-
 RawTypeRef* TypeRef::New() {
   ASSERT(Isolate::Current()->object_store()->type_ref_class() != Class::null());
   RawObject* raw = Object::Allocate(TypeRef::kClassId,
                                     TypeRef::InstanceSize(),
                                     Heap::kOld);
   return reinterpret_cast<RawTypeRef*>(raw);
 }
 
 
 RawTypeRef* TypeRef::New(const AbstractType& type) {
   const TypeRef& result = TypeRef::Handle(TypeRef::New());
   result.set_type(type);
   return result.raw();
 }
 
 
 const char* TypeRef::ToCString() const {
-  const char* format = "TypeRef: %s%s";
-  const char* type_cstr = String::Handle(Class::Handle(AbstractType::Handle(
-      type()).type_class()).Name()).ToCString();
-  const char* args_cstr = (AbstractType::Handle(
-      type()).arguments() == TypeArguments::null()) ? "" : "<...>";
-  intptr_t len = OS::SNPrint(NULL, 0, format, type_cstr, args_cstr) + 1;
-  char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
-  OS::SNPrint(chars, len, format, type_cstr, args_cstr);
-  return chars;
+  const char* type_cstr = String::Handle(Class::Handle(
+      type_class()).Name()).ToCString();
+  AbstractType& ref_type = AbstractType::Handle(type());
+  if (ref_type.IsFinalized()) {
+    const char* format = "TypeRef: %s<...> (@%" Px " H%" Px ")";
+    const intptr_t hash = ref_type.Hash();
+    const intptr_t len =
+        OS::SNPrint(NULL, 0, format, type_cstr, ref_type.raw(), hash) + 1;
+    char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
+    OS::SNPrint(chars, len, format, type_cstr, ref_type.raw(), hash);
+    return chars;
+  } else {
+    const char* format = "TypeRef: %s<...>";
+    const intptr_t len = OS::SNPrint(NULL, 0, format, type_cstr) + 1;
+    char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
+    OS::SNPrint(chars, len, format, type_cstr);
+    return chars;
+  }
 }
 
 
 void TypeRef::PrintToJSONStream(JSONStream* stream, bool ref) const {
   JSONObject jsobj(stream);
   ObjectIdRing* ring = Isolate::Current()->object_id_ring();
   const intptr_t id = ring->GetIdForObject(raw());
   jsobj.AddProperty("type", JSONType(ref));
   jsobj.AddPropertyF("id", "objects/%" Pd "", id);
   const char* name = String::Handle(Name()).ToCString();
@@ skipping 134 matching lines @@
   return TypeParameter::New(Class::Handle(parameterized_class()),
                             index(),
                             String::Handle(name()),
                             AbstractType::Handle(bound()),
                             token_pos());
 }
 
 
 intptr_t TypeParameter::Hash() const {
   ASSERT(IsFinalized());
-  uword result = Class::Handle(parameterized_class()).id();
+  intptr_t result = Class::Handle(parameterized_class()).id();
   // No need to include the hash of the bound, since the type parameter is fully
   // identified by its class and index.
-  result <<= index();
+  result = CombineHashes(result, index());
   return FinalizeHash(result);
 }
 
 
 RawTypeParameter* TypeParameter::New() {
   ASSERT(Isolate::Current()->object_store()->type_parameter_class() !=
          Class::null());
   RawObject* raw = Object::Allocate(TypeParameter::kClassId,
                                     TypeParameter::InstanceSize(),
                                     Heap::kOld);
@@ skipping 116 matching lines @@
     return false;
   }
   const AbstractType& this_bound = AbstractType::Handle(bound());
   const AbstractType& other_bound = AbstractType::Handle(other_bounded.bound());
   return this_bound.IsFinalized() &&
          other_bound.IsFinalized() &&
          this_bound.Equals(other_bound);  // Different graph, do not pass trail.
 }
 
 
+bool BoundedType::IsRecursive() const {
+  return AbstractType::Handle(type()).IsRecursive();
+}
+
+
 void BoundedType::set_type(const AbstractType& value) const {
   ASSERT(value.IsFinalized() || value.IsBeingFinalized());
   ASSERT(!value.IsMalformed());
   StorePointer(&raw_ptr()->type_, value.raw());
 }
 
 
 void BoundedType::set_bound(const AbstractType& value) const {
   // The bound may still be unfinalized because of legal cycles.
   // It must be finalized before it is checked at run time, though.
@@ skipping 54 matching lines @@
   bounded_type = bounded_type.CloneUnfinalized();
   // No need to clone bound or type parameter, as they are not part of the
   // finalization state of this bounded type.
   return BoundedType::New(bounded_type,
                           AbstractType::Handle(bound()),
                           TypeParameter::Handle(type_parameter()));
 }
 
 
 intptr_t BoundedType::Hash() const {
-  uword result = AbstractType::Handle(type()).Hash();
+  intptr_t result = AbstractType::Handle(type()).Hash();
   // No need to include the hash of the bound, since the bound is defined by the
   // type parameter (modulo instantiation state).
-  result += TypeParameter::Handle(type_parameter()).Hash();
-return FinalizeHash(result);
+  result = CombineHashes(result,
+                         TypeParameter::Handle(type_parameter()).Hash());
+  return FinalizeHash(result);
 }
 
 
 RawBoundedType* BoundedType::New() {
   ASSERT(Isolate::Current()->object_store()->bounded_type_class() !=
          Class::null());
   RawObject* raw = Object::Allocate(BoundedType::kClassId,
                                     BoundedType::InstanceSize(),
                                     Heap::kOld);
   return reinterpret_cast<RawBoundedType*>(raw);
@@ skipping 980 matching lines @@
 void Bigint::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Number::PrintToJSONStream(stream, ref);
 }
 
 
 // Synchronize with implementation in compiler (intrinsifier).
 class StringHasher : ValueObject {
  public:
   StringHasher() : hash_(0) {}
   void Add(int32_t ch) {
-    hash_ += ch;
-    hash_ += hash_ << 10;
-    hash_ ^= hash_ >> 6;
+    hash_ = CombineHashes(hash_, ch);
   }
   // Return a non-zero hash of at most 'bits' bits.
   intptr_t Finalize(int bits) {
     ASSERT(1 <= bits && bits <= (kBitsPerWord - 1));
-    hash_ += hash_ << 3;
-    hash_ ^= hash_ >> 11;
-    hash_ += hash_ << 15;
+    hash_ = FinalizeHash(hash_);
     hash_ = hash_ & ((static_cast<intptr_t>(1) << bits) - 1);
     ASSERT(hash_ <= static_cast<uint32_t>(kMaxInt32));
     return hash_ == 0 ? 1 : hash_;
   }
  private:
   uint32_t hash_;
 };
 
 
 intptr_t String::Hash(const String& str, intptr_t begin_index, intptr_t len) {
@@ skipping 2926 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Instance::PrintToJSONStream(stream, ref);
 }
 
 
 }  // namespace dart