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 3577 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 53 matching lines @@
 
 
 void InstantiatedTypeArguments::SetTypeAt(intptr_t index,
                                           const AbstractType& value) const {
   // We only replace individual argument types during resolution at compile
   // time, when no type parameters are instantiated yet.
   UNREACHABLE();
 }
 
 
-RawAbstractTypeArguments* InstantiatedTypeArguments::Canonicalize() const {
+RawAbstractTypeArguments* InstantiatedTypeArguments::Canonicalize(
+    GrowableObjectArray* trail) const {
   const intptr_t num_types = Length();
   const TypeArguments& type_args = TypeArguments::Handle(
       TypeArguments::New(num_types, Heap::kOld));
   AbstractType& type = AbstractType::Handle();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     type_args.SetTypeAt(i, type);
   }
-  return type_args.Canonicalize();
+  return type_args.Canonicalize(trail);
 }
 
 
 void InstantiatedTypeArguments::set_uninstantiated_type_arguments(
     const AbstractTypeArguments& value) const {
   StorePointer(&raw_ptr()->uninstantiated_type_arguments_, value.raw());
 }
 
 
 void InstantiatedTypeArguments::set_instantiator_type_arguments(
@@ skipping 7585 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 118 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 ^= OnlyBuddyInTrail(trail);
+  if (!instantiated_type_ref.IsNull()) {
+    return instantiated_type_ref.raw();
+  }
+  instantiated_type_ref = TypeRef::New(Type::Handle(Type::DynamicType()));
+  AddOnlyBuddyToTrail(&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);
+  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);
-  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 3735 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Instance::PrintToJSONStream(stream, ref);
 }
 
 
 }  // namespace dart