Use a trail instead of a mark bit when processing recursive types in the VM

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 3383 matching lines @@
 }
 
 
 bool AbstractTypeArguments::IsResolved() const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
-bool AbstractTypeArguments::IsInstantiated() const {
+bool AbstractTypeArguments::IsInstantiated(GrowableObjectArray* trail) const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
 bool AbstractTypeArguments::IsUninstantiatedIdentity() const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return false;
@@ skipping 57 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 AbstractTypeArguments::Equals(const AbstractTypeArguments& other) const {
+bool AbstractTypeArguments::IsEquivalent(const AbstractTypeArguments& other,
+                                         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++) {
     type = TypeAt(i);
     other_type = other.TypeAt(i);
-    if (!type.Equals(other_type)) {
+    if (!type.IsEquivalent(other_type, trail)) {
       return false;
     }
   }
   return true;
 }
 
 
 RawAbstractTypeArguments* AbstractTypeArguments::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
-    Error* bound_error) const {
+    Error* bound_error,
+    GrowableObjectArray* trail) const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return NULL;
 }
 
 
 bool AbstractTypeArguments::IsDynamicTypes(bool raw_instantiated,
                                            intptr_t from_index,
                                            intptr_t len) const {
   ASSERT(Length() >= (from_index + len));
@@ skipping 88 matching lines @@
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     if (!type.IsResolved()) {
       return false;
     }
   }
   return true;
 }
 
 
-bool TypeArguments::IsInstantiated() const {
+bool TypeArguments::IsInstantiated(GrowableObjectArray* trail) const {
   AbstractType& type = AbstractType::Handle();
   const intptr_t num_types = Length();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     ASSERT(!type.IsNull());
-    if (!type.IsInstantiated()) {
+    if (!type.IsInstantiated(trail)) {
       return false;
     }
   }
   return true;
 }
 
 
 bool TypeArguments::IsUninstantiatedIdentity() const {
   ASSERT(!IsInstantiated());
   AbstractType& type = AbstractType::Handle();
@@ skipping 129 matching lines @@
     if (!type_args.IsNull() && type_args.IsBounded()) {
       return true;
     }
   }
   return false;
 }
 
 
 RawAbstractTypeArguments* TypeArguments::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
-    Error* bound_error) const {
+    Error* bound_error,
+    GrowableObjectArray* trail) const {
   ASSERT(!IsInstantiated());
   if (!instantiator_type_arguments.IsNull() &&
       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.IsInstantiated()) {
-      type = type.InstantiateFrom(instantiator_type_arguments, bound_error);
+      type = type.InstantiateFrom(instantiator_type_arguments,
+                                  bound_error,
+                                  trail);
     }
     instantiated_array.SetTypeAt(i, type);
   }
   return instantiated_array.raw();
 }
 
 
 RawTypeArguments* TypeArguments::New(intptr_t len, Heap::Space space) {
   if (len < 0 || len > kMaxElements) {
     // This should be caught before we reach here.
@@ skipping 110 matching lines @@
       TypeArguments::New(num_types));
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     type = type.CloneUnfinalized();
     clone.SetTypeAt(i, type);
   }
   return clone.raw();
 }
 
 
-RawAbstractTypeArguments* TypeArguments::Canonicalize() const {
+RawAbstractTypeArguments* TypeArguments::Canonicalize(
+    GrowableObjectArray* trail) const {
   if (IsNull() || IsCanonical()) {
     ASSERT(IsOld());
     return this->raw();
   }
   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());
   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);
     for (intptr_t i = 0; i < num_types; i++) {
       type = TypeAt(i);
-      type = type.Canonicalize();
+      type = type.Canonicalize(trail);
       SetTypeAt(i, type);
     }
     // 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);
@@ skipping 7596 matching lines @@
 }
 
 
 intptr_t AbstractType::token_pos() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return -1;
 }
 
 
-bool AbstractType::IsInstantiated() const {
+bool AbstractType::IsInstantiated(GrowableObjectArray* trail) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
 bool AbstractType::IsFinalized() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return false;
@@ skipping 34 matching lines @@
   return LanguageError::null();
 }
 
 
 void AbstractType::set_error(const LanguageError& value) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
 }
 
 
-bool AbstractType::Equals(const Instance& other) const {
+bool AbstractType::IsEquivalent(const Instance& other,
+                                GrowableObjectArray* trail) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
 RawAbstractType* AbstractType::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
-    Error* bound_error) const {
+    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() const {
+RawAbstractType* AbstractType::Canonicalize(GrowableObjectArray* trail) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return NULL;
 }
 
 
 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());
-    // Building the bound name may lead into cycles.
+    // Build the bound name without causing divergence.
     const AbstractType& bound = AbstractType::Handle(
         BoundedType::Cast(*this).bound());
     String& bound_name = String::Handle();
     if (bound.IsTypeParameter()) {
       bound_name = TypeParameter::Cast(bound).name();
     } else if (bound.IsType()) {
       const Class& cls = Class::Handle(Type::Cast(bound).type_class());
       bound_name = cls.Name();
       if (Type::Cast(bound).arguments() != AbstractTypeArguments::null()) {
         bound_name = String::Concat(bound_name, Symbols::OptimizedOut());
@@ skipping 40 matching lines @@
       // The actual type argument vector can be longer than necessary, because
       // of type optimizations.
       if (IsFinalized() && cls.is_type_finalized()) {
         first_type_param_index = cls.NumTypeArguments() - num_type_params;
       } else {
         first_type_param_index = num_args - num_type_params;
       }
     }
     if (cls.IsSignatureClass()) {
       // We may be reporting an error about a malformed function type. In that
-      // case, avoid instantiating the signature, since it may lead to cycles.
+      // case, avoid instantiating the signature, since it may cause divergence.
       if (!IsFinalized() || IsBeingFinalized() || IsMalformed()) {
         return class_name.raw();
       }
-      // In order to avoid cycles, print the name of a typedef (non-canonical
+      // To avoid divergence, print the name of a typedef (non-canonical
       // signature class) as a regular, possibly parameterized, class.
       if (cls.IsCanonicalSignatureClass()) {
         const Function& signature_function = Function::Handle(
             cls.signature_function());
         // Signature classes have no super type, however, they take as many
         // type arguments as the owner class of their signature function (if it
         // is non static and generic, see Class::NumTypeArguments()). Therefore,
         // first_type_param_index may be greater than 0 here.
         return signature_function.InstantiatedSignatureFrom(args,
                                                             name_visibility);
@@ skipping 384 matching lines @@
   return reinterpret_cast<RawUnresolvedClass*>(raw_ptr()->type_class_);
 #endif
 }
 
 
 RawAbstractTypeArguments* Type::arguments() const {
   return raw_ptr()->arguments_;
 }
 
 
-bool Type::IsInstantiated() const {
+bool Type::IsInstantiated(GrowableObjectArray* trail) const {
   if (raw_ptr()->type_state_ == RawType::kFinalizedInstantiated) {
     return true;
   }
   if (raw_ptr()->type_state_ == RawType::kFinalizedUninstantiated) {
     return false;
   }
   const AbstractTypeArguments& args =
       AbstractTypeArguments::Handle(arguments());
-  return args.IsNull() || args.IsInstantiated();
+  return args.IsNull() || args.IsInstantiated(trail);
 }
 
 
 RawAbstractType* Type::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
-    Error* bound_error) const {
+    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();
   }
   AbstractTypeArguments& type_arguments =
       AbstractTypeArguments::Handle(arguments());
   type_arguments = type_arguments.InstantiateFrom(instantiator_type_arguments,
-                                                  bound_error);
+                                                  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.
   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()));
   instantiated_type.SetIsFinalized();
   return instantiated_type.raw();
 }
 
 
-bool Type::Equals(const Instance& other) const {
+bool Type::IsEquivalent(const Instance& other,
+                        GrowableObjectArray* trail) const {
   ASSERT(!IsNull());
   if (raw() == other.raw()) {
     return true;
   }
   if (other.IsTypeRef()) {
-    // TODO(regis): Use trail. For now, we "unfold" the right hand type.
-    return Equals(AbstractType::Handle(TypeRef::Cast(other).type()));
+    // Unfold right hand type. Divergence is controlled by left hand type.
+    const AbstractType& other_ref_type = AbstractType::Handle(
+        TypeRef::Cast(other).type());
+    ASSERT(!other_ref_type.IsTypeRef());
+    return IsEquivalent(other_ref_type, trail);
   }
   if (!other.IsType()) {
     return false;
   }
   const Type& other_type = Type::Cast(other);
   ASSERT(IsResolved() && other_type.IsResolved());
   if (IsMalformed() || other_type.IsMalformed()) {
     return false;
   }
   if (type_class() != other_type.type_class()) {
@@ skipping 23 matching lines @@
   if (other_type_args.IsNull()) {
     return type_args.IsRaw(from_index, 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();
   AbstractType& other_type_arg = AbstractType::Handle();
   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.Equals(other_type_arg)) {
+    if (!type_arg.IsEquivalent(other_type_arg, trail)) {
       return false;
     }
   }
   return true;
 }
 
 
 RawAbstractType* Type::CloneUnfinalized() const {
   ASSERT(IsResolved());
   if (IsFinalized()) {
     return raw();
   }
   ASSERT(!IsMalformed());  // Malformed types are finalized.
   ASSERT(!IsBeingFinalized());  // Cloning must occur prior to finalization.
   AbstractTypeArguments& type_args = AbstractTypeArguments::Handle(arguments());
   type_args = type_args.CloneUnfinalized();
   const Class& type_cls = Class::Handle(type_class());
   return Type::New(type_cls, type_args, token_pos());
 }
 
 
-RawAbstractType* Type::Canonicalize() const {
+RawAbstractType* Type::Canonicalize(GrowableObjectArray* trail) const {
   ASSERT(IsFinalized());
   if (IsCanonical() || IsMalformed()) {
     ASSERT(IsMalformed() || AbstractTypeArguments::Handle(arguments()).IsOld());
     return this->raw();
   }
   Isolate* isolate = Isolate::Current();
   Type& type = Type::Handle(isolate);
   const Class& cls = Class::Handle(isolate, type_class());
   if (cls.raw() == Object::dynamic_class() && (isolate != Dart::vm_isolate())) {
     return Object::dynamic_type();
@@ skipping 30 matching lines @@
     ASSERT(type.IsFinalized());
     if (this->Equals(type)) {
       return type.raw();
     }
     index++;
   }
   // Canonicalize the type arguments.
   AbstractTypeArguments& type_args =
       AbstractTypeArguments::Handle(isolate, arguments());
   ASSERT(type_args.IsNull() || (type_args.Length() == cls.NumTypeArguments()));
-  type_args = type_args.Canonicalize();
+  type_args = type_args.Canonicalize(trail);
   set_arguments(type_args);
   // The type needs to be added to the list. Grow the list if it is full.
   if (index == canonical_types_len) {
     const intptr_t kLengthIncrement = 2;  // Raw and parameterized.
     const intptr_t new_length = canonical_types.Length() + kLengthIncrement;
     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 117 matching lines @@
     return "Unresolved Type";
   }
 }
 
 
 void Type::PrintToJSONStream(JSONStream* stream, bool ref) const {
   JSONObject jsobj(stream);
 }
 
 
-bool TypeRef::IsInstantiated() const {
-  if (is_being_checked()) {
+bool TypeRef::IsInstantiated(GrowableObjectArray* trail) const {
+  if (TestAndAddToTrail(&trail)) {
     return true;
   }
-  set_is_being_checked(true);
-  const bool result = AbstractType::Handle(type()).IsInstantiated();
-  set_is_being_checked(false);
-  return result;
+  return AbstractType::Handle(type()).IsInstantiated(trail);
 }
 
 
-bool TypeRef::Equals(const Instance& other) const {
-  // TODO(regis): Use trail instead of mark bit.
+bool TypeRef::IsEquivalent(const Instance& other,
+                           GrowableObjectArray* trail) const {
   if (raw() == other.raw()) {
     return true;
   }
-  if (is_being_checked()) {
+  if (TestAndAddBuddyToTrail(&trail, other)) {
     return true;
   }
-  set_is_being_checked(true);
-  const bool result = AbstractType::Handle(type()).Equals(other);
-  set_is_being_checked(false);
-  return result;
+  return AbstractType::Handle(type()).IsEquivalent(other, trail);
 }
 
 
 RawAbstractType* TypeRef::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
-    Error* bound_error) const {
+    Error* bound_error,
+    GrowableObjectArray* trail) const {
+  TypeRef& instantiated_type_ref = TypeRef::Handle();
+  instantiated_type_ref ^= BuddyInTrail(trail);
+  if (!instantiated_type_ref.IsNull()) {
+    return instantiated_type_ref.raw();
+  }
+  instantiated_type_ref = TypeRef::New(Type::Handle(Type::DynamicType()));
+  AddBuddyToTrail(&trail, instantiated_type_ref);
   const AbstractType& ref_type = AbstractType::Handle(type());
-  // TODO(regis): Use trail instead of mark bit plus temporary redirection,
-  // because it could be marked for another reason.
-  if (is_being_checked()) {
-    ASSERT(ref_type.IsTypeRef());
-    return ref_type.raw();
-  }
-  set_is_being_checked(true);
   ASSERT(!ref_type.IsTypeRef());
-  const TypeRef& instantiated_type_ref = TypeRef::Handle(
-      TypeRef::New(ref_type));
-  // TODO(regis): instantiated_type_ref should be stored in the trail instead.
-  set_type(instantiated_type_ref);
   const AbstractType& instantiated_ref_type = AbstractType::Handle(
-      ref_type.InstantiateFrom(instantiator_type_arguments, bound_error));
+      ref_type.InstantiateFrom(instantiator_type_arguments,
+                               bound_error,
+                               trail));
   instantiated_type_ref.set_type(instantiated_ref_type);
-  set_type(ref_type);
-  set_is_being_checked(false);
   return instantiated_type_ref.raw();
 }
 
 
 void TypeRef::set_type(const AbstractType& value) const {
   ASSERT(value.HasResolvedTypeClass());
   StorePointer(&raw_ptr()->type_, value.raw());
 }
 
 
-void TypeRef::set_is_being_checked(bool value) const {
-  raw_ptr()->is_being_checked_ = value;
-}
-
-
-// This function only canonicalizes the referenced type, but not the TypeRef
-// itself, since it cannot be canonical by definition.
+// 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.
-RawAbstractType* TypeRef::Canonicalize() const {
-  // TODO(regis): Use trail, not mark bit.
-  if (is_being_checked()) {
+RawAbstractType* TypeRef::Canonicalize(GrowableObjectArray* trail) const {
+  if (TestAndAddToTrail(&trail)) {
     return raw();
   }
-  set_is_being_checked(true);
   AbstractType& ref_type = AbstractType::Handle(type());
-  ASSERT(!ref_type.IsTypeRef());
-  ref_type = ref_type.Canonicalize();
+  ref_type = ref_type.Canonicalize(trail);
   set_type(ref_type);
-  // No need to call SetCanonical(), since a TypeRef cannot be canonical by
-  // definition.
-  set_is_being_checked(false);
-  // We return the referenced type instead of the TypeRef in order to provide
-  // pointer equality in simple cases, e.g. in language/f_bounded_equality_test.
-  return ref_type.raw();
+  return raw();
 }
 
 
 intptr_t TypeRef::Hash() const {
-  // TODO(regis): Use trail and hash of referenced type.
-  // Do not calculate the hash of the referenced type to avoid cycles.
+  // Do not calculate the hash of the referenced type to avoid divergence.
   uword 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++) {
+      if ((*trail)->At(i) == this->raw()) {
+        return true;
+      }
+    }
+  }
+  (*trail)->Add(*this);
+  return false;
+}
+
+
+bool TypeRef::TestAndAddBuddyToTrail(GrowableObjectArray** trail,
+                                     const Object& buddy) const {
+  if (*trail == NULL) {
+    *trail = &GrowableObjectArray::ZoneHandle(GrowableObjectArray::New());
+  } else {
+    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()) &&
+          ((*trail)->At(i + 1) == buddy.raw())) {
+        return true;
+      }
+    }
+  }
+  (*trail)->Add(*this);
+  (*trail)->Add(buddy);

[siva, 2013/12/20 19:35:10]

The code in this function seems to imply that a receiver can have
multiple buddies in the trail but AddBuddyToTrail below does not
allow that, it will ASSERT if you try to add a second buddy to a
receiver. This divergence seems confusing.

Maybe you could rename the function AddBuddyToTrail as
AddFirstBuddyToTrail or something like that to indicate we don't
expect to see any buddies for the receiver at that point.

[regis, 2014/01/07 20:26:27]

I renamed the other function AddOnlyBuddyToTrail. This one allows more that one
pair for a given receiver. I updated the comment in the header.

+  return false;
+}
+
+
+RawObject* TypeRef::BuddyInTrail(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()) {

[siva, 2013/12/20 19:35:10]

Should there be an assert here:
ASSERT(trail->At(i + 1) != Object::null());

[regis, 2014/01/07 20:26:27]

Done.

+      return trail->At(i + 1);
+    }
+  }
+  return Object::null();
+}
+
+
+void TypeRef::AddBuddyToTrail(GrowableObjectArray** trail,
+                              const Object& buddy) const {
+  if (*trail == NULL) {
+    *trail = &GrowableObjectArray::ZoneHandle(GrowableObjectArray::New());
+  } else {
+    ASSERT(BuddyInTrail(*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);
-  result.set_is_being_checked(false);
   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() == AbstractTypeArguments::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;
 }
 
 
 void TypeRef::PrintToJSONStream(JSONStream* stream, bool ref) const {
   JSONObject jsobj(stream);
 }
 
 
 void TypeParameter::set_is_finalized() const {
   ASSERT(!IsFinalized());
   set_type_state(RawTypeParameter::kFinalizedUninstantiated);
 }
 
 
-bool TypeParameter::Equals(const Instance& other) const {
+bool TypeParameter::IsEquivalent(const Instance& other,
+                                 GrowableObjectArray* trail) const {
   if (raw() == other.raw()) {
     return true;
   }
   if (other.IsTypeRef()) {
-    // TODO(regis): Use trail. For now, we "unfold" the right hand type.
-    return Equals(AbstractType::Handle(TypeRef::Cast(other).type()));
+    // Unfold right hand type. Divergence is controlled by left hand type.
+    const AbstractType& other_ref_type = AbstractType::Handle(
+        TypeRef::Cast(other).type());
+    ASSERT(!other_ref_type.IsTypeRef());
+    return IsEquivalent(other_ref_type, trail);
   }
   if (!other.IsTypeParameter()) {
     return false;
   }
   const TypeParameter& other_type_param = TypeParameter::Cast(other);
   if (parameterized_class() != other_type_param.parameterized_class()) {
     return false;
   }
   if (IsFinalized() == other_type_param.IsFinalized()) {
     return index() == other_type_param.index();
@@ skipping 20 matching lines @@
 }
 
 
 void TypeParameter::set_bound(const AbstractType& value) const {
   StorePointer(&raw_ptr()->bound_, value.raw());
 }
 
 
 RawAbstractType* TypeParameter::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
-    Error* bound_error) const {
+    Error* bound_error,
+    GrowableObjectArray* trail) const {
   ASSERT(IsFinalized());
   if (instantiator_type_arguments.IsNull()) {
     return Type::DynamicType();
   }
   const AbstractType& type_arg = AbstractType::Handle(
       instantiator_type_arguments.TypeAt(index()));
   // There is no need to canonicalize the instantiated type parameter, since all
   // type arguments are canonicalized at type finalization time. It would be too
   // early to canonicalize the returned type argument here, since instantiation
   // not only happens at run time, but also during type finalization.
-  // However, if the type argument is a reference to a canonical type, we
-  // return the referenced canonical type instead of the type reference to
-  // provide pointer equality in some simple cases, e.g. in
-  // language/f_bounded_equality_test.
-  if (type_arg.IsTypeRef()) {
-    const AbstractType& ref_type = AbstractType::Handle(
-        TypeRef::Cast(type_arg).type());
-    if (ref_type.IsCanonical()) {
-      return ref_type.raw();
-    }
-  }
   return type_arg.raw();
 }
 
 
 bool TypeParameter::CheckBound(const AbstractType& bounded_type,
                                const AbstractType& upper_bound,
                                Error* bound_error) const {
   ASSERT((bound_error != NULL) && bound_error->IsNull());
   ASSERT(bounded_type.IsFinalized());
   ASSERT(upper_bound.IsFinalized());
@@ skipping 46 matching lines @@
                             index(),
                             String::Handle(name()),
                             AbstractType::Handle(bound()),
                             token_pos());
 }
 
 
 intptr_t TypeParameter::Hash() const {
   ASSERT(IsFinalized());
   uword result = Class::Handle(parameterized_class()).id();
-  // Do not include the hash of the bound, which could lead to cycles.
+  // No need to include the hash of the bound, since the type parameter is fully
+  // identified by its class and index.
   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(),
@@ skipping 63 matching lines @@
 bool BoundedType::IsMalformedOrMalbounded() const {
   return AbstractType::Handle(type()).IsMalformedOrMalbounded();
 }
 
 
 RawLanguageError* BoundedType::error() const {
   return AbstractType::Handle(type()).error();
 }
 
 
-bool BoundedType::Equals(const Instance& other) const {
+bool BoundedType::IsEquivalent(const Instance& other,
+                               GrowableObjectArray* trail) const {
   // BoundedType are not canonicalized, because their bound may get finalized
   // after the BoundedType is created and initialized.
   if (raw() == other.raw()) {
     return true;
   }
   if (other.IsTypeRef()) {
-    // TODO(regis): Use trail. For now, we "unfold" the right hand type.
-    return Equals(AbstractType::Handle(TypeRef::Cast(other).type()));
+    // Unfold right hand type. Divergence is controlled by left hand type.
+    const AbstractType& other_ref_type = AbstractType::Handle(
+        TypeRef::Cast(other).type());
+    ASSERT(!other_ref_type.IsTypeRef());
+    return IsEquivalent(other_ref_type, trail);
   }
   if (!other.IsBoundedType()) {
     return false;
   }
   const BoundedType& other_bounded = BoundedType::Cast(other);
   if (type_parameter() != other_bounded.type_parameter()) {
-    // Not a structural compare.
-    // Note that a deep comparison of bounds could lead to cycles.
     return false;
   }
   const AbstractType& this_type = AbstractType::Handle(type());
   const AbstractType& other_type = AbstractType::Handle(other_bounded.type());
-  if (!this_type.Equals(other_type)) {
+  if (!this_type.IsEquivalent(other_type, trail)) {
     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);
+         this_bound.Equals(other_bound);  // Different graph, do not pass trail.
 }
 
 
 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.
   StorePointer(&raw_ptr()->bound_, value.raw());
 }
 
 
 void BoundedType::set_type_parameter(const TypeParameter& value) const {
   // A null type parameter is set when marking a type malformed because of a
   // bound error at compile time.
   ASSERT(value.IsNull() || value.IsFinalized());
   StorePointer(&raw_ptr()->type_parameter_, value.raw());
 }
 
 
-void BoundedType::set_is_being_checked(bool value) const {
-  raw_ptr()->is_being_checked_ = value;
-}
-
-
 RawAbstractType* BoundedType::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
-    Error* bound_error) const {
+    Error* bound_error,
+    GrowableObjectArray* trail) const {
   ASSERT(IsFinalized());
   AbstractType& bounded_type = AbstractType::Handle(type());
   if (!bounded_type.IsInstantiated()) {
     bounded_type = bounded_type.InstantiateFrom(instantiator_type_arguments,
-                                                bound_error);
+                                                bound_error,
+                                                trail);
   }
-  if (FLAG_enable_type_checks &&
-      bound_error->IsNull() &&
-      !is_being_checked()) {
-    // Avoid endless recursion while checking and instantiating bound.
-    set_is_being_checked(true);
+  if (FLAG_enable_type_checks && bound_error->IsNull()) {
     AbstractType& upper_bound = AbstractType::Handle(bound());
     ASSERT(!upper_bound.IsObjectType() && !upper_bound.IsDynamicType());
     const TypeParameter& type_param = TypeParameter::Handle(type_parameter());
     if (!upper_bound.IsInstantiated()) {
       upper_bound = upper_bound.InstantiateFrom(instantiator_type_arguments,
-                                                bound_error);
+                                                bound_error,
+                                                trail);
     }
     if (bound_error->IsNull()) {
       if (!type_param.CheckBound(bounded_type, upper_bound, bound_error) &&
           bound_error->IsNull()) {
         // We cannot determine yet whether the bounded_type is below the
         // upper_bound, because one or both of them is still uninstantiated.
         ASSERT(!bounded_type.IsInstantiated() || !upper_bound.IsInstantiated());
         // Postpone bound check by returning a new BoundedType with partially
         // instantiated bounded_type and upper_bound, but keeping type_param.
         bounded_type = BoundedType::New(bounded_type, upper_bound, type_param);
       }
     }
-    set_is_being_checked(false);
   }
   return bounded_type.raw();
 }
 
 
 RawAbstractType* BoundedType::CloneUnfinalized() const {
   if (IsFinalized()) {
     return raw();
   }
   AbstractType& bounded_type = AbstractType::Handle(type());
 
   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();
-  // Do not include the hash of the bound, which could lead to cycles.
+  // 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);
 }
 
 
 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);
 }
 
 
 RawBoundedType* BoundedType::New(const AbstractType& type,
                                  const AbstractType& bound,
                                  const TypeParameter& type_parameter) {
   const BoundedType& result = BoundedType::Handle(BoundedType::New());
   result.set_type(type);
   result.set_bound(bound);
   result.set_type_parameter(type_parameter);
-  result.set_is_being_checked(false);
   return result.raw();
 }
 
 
 const char* BoundedType::ToCString() const {
   const char* format = "BoundedType: type %s; bound: %s; type param: %s of %s";
   const char* type_cstr = String::Handle(AbstractType::Handle(
       type()).Name()).ToCString();
   const char* bound_cstr = String::Handle(AbstractType::Handle(
       bound()).Name()).ToCString();
@@ skipping 3587 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Instance::PrintToJSONStream(stream, ref);
 }
 
 
 }  // namespace dart