Keep a trail while checking upper bounds in the VM in order to properly handle

runtime/vm/object.cc

Index: runtime/vm/object.cc
diff --git a/runtime/vm/object.cc b/runtime/vm/object.cc
index ed737215e2b5f2c70108357d1470eab41711ddde..a36f70cd84bb67d21b507a2636a1822ea4cf0c15 100644
--- a/runtime/vm/object.cc
+++ b/runtime/vm/object.cc
@@ -3615,6 +3615,7 @@ bool Class::TypeTestNonRecursive(const Class& cls,
                                  const Class& other,
                                  const TypeArguments& other_type_arguments,
                                  Error* bound_error,
+                                 TrailPtr bound_trail,
                                  Heap::Space space) {
   // Use the thsi object as if it was the receiver of this method, but instead
   // of recursing reset it to the super class and loop.
@@ -3673,6 +3674,7 @@ bool Class::TypeTestNonRecursive(const Class& cls,
                                      from_index,
                                      num_type_params,
                                      bound_error,
+                                     bound_trail,
                                      space);
     }
     if (other.IsFunctionClass()) {
@@ -3733,7 +3735,11 @@ bool Class::TypeTestNonRecursive(const Class& cls,
         // The index of the type parameters is adjusted upon finalization.
         error = Error::null();
         interface_args =
-            interface_args.InstantiateFrom(type_arguments, &error, NULL, space);
+            interface_args.InstantiateFrom(type_arguments,
+                                           &error,
+                                           NULL,
+                                           bound_trail,
+                                           space);
         if (!error.IsNull()) {
           // Return the first bound error to the caller if it requests it.
           if ((bound_error != NULL) && bound_error->IsNull()) {
@@ -3747,6 +3753,7 @@ bool Class::TypeTestNonRecursive(const Class& cls,
                                    other,
                                    other_type_arguments,
                                    bound_error,
+                                   bound_trail,
                                    space)) {
         return true;
       }
@@ -3773,6 +3780,7 @@ bool Class::TypeTest(TypeTestKind test_kind,
                      const Class& other,
                      const TypeArguments& other_type_arguments,
                      Error* bound_error,
+                     TrailPtr bound_trail,
                      Heap::Space space) const {
   return TypeTestNonRecursive(*this,
                               test_kind,
@@ -3780,6 +3788,7 @@ bool Class::TypeTest(TypeTestKind test_kind,
                               other,
                               other_type_arguments,
                               bound_error,
+                              bound_trail,
                               space);
 }
 
@@ -4289,6 +4298,7 @@ bool TypeArguments::TypeTest(TypeTestKind test_kind,
                              intptr_t from_index,
                              intptr_t len,
                              Error* bound_error,
+                             TrailPtr bound_trail,
                              Heap::Space space) const {
   ASSERT(Length() >= (from_index + len));
   ASSERT(!other.IsNull());
@@ -4300,7 +4310,11 @@ bool TypeArguments::TypeTest(TypeTestKind test_kind,
     ASSERT(!type.IsNull());
     other_type = other.TypeAt(from_index + i);
     ASSERT(!other_type.IsNull());
-    if (!type.TypeTest(test_kind, other_type, bound_error, space)) {
+    if (!type.TypeTest(test_kind,
+                       other_type,
+                       bound_error,
+                       bound_trail,
+                       space)) {
       return false;
     }
   }
@@ -4350,6 +4364,7 @@ RawAbstractType* TypeArguments::TypeAt(intptr_t index) const {
 
 void TypeArguments::SetTypeAt(intptr_t index,
                                 const AbstractType& value) const {
+  ASSERT(!IsCanonical());
   StorePointer(TypeAddr(index), value.raw());
 }
 
@@ -4527,7 +4542,8 @@ bool TypeArguments::IsBounded() const {
 RawTypeArguments* TypeArguments::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
-    TrailPtr trail,
+    TrailPtr instantiation_trail,
+    TrailPtr bound_trail,
     Heap::Space space) const {
   ASSERT(!IsInstantiated());
   if (!instantiator_type_arguments.IsNull() &&
@@ -4550,7 +4566,8 @@ RawTypeArguments* TypeArguments::InstantiateFrom(
     if (!type.IsNull() && !type.IsInstantiated()) {
       type = type.InstantiateFrom(instantiator_type_arguments,
                                   bound_error,
-                                  trail,
+                                  instantiation_trail,
+                                  bound_trail,
                                   space);
     }
     instantiated_array.SetTypeAt(i, type);
@@ -4584,7 +4601,7 @@ RawTypeArguments* TypeArguments::InstantiateAndCanonicalizeFrom(
   // Cache lookup failed. Instantiate the type arguments.
   TypeArguments& result = TypeArguments::Handle();
   result = InstantiateFrom(
-      instantiator_type_arguments, bound_error, NULL, Heap::kOld);
+      instantiator_type_arguments, bound_error, NULL, NULL, Heap::kOld);
   if ((bound_error != NULL) && !bound_error->IsNull()) {
     return result.raw();
   }
@@ -4815,6 +4832,12 @@ RawTypeArguments* TypeArguments::Canonicalize(TrailPtr trail) const {
     for (intptr_t i = 0; i < num_types; i++) {
       type_arg = TypeAt(i);
       type_arg = type_arg.Canonicalize(trail);
+      if (IsCanonical()) {
+        // Canonicalizing this type_arg canonicalized this type.
+        ASSERT(IsRecursive());
+        ASSERT(IsOld());

[rmacnak, 2016/02/09 00:50:22]

I don't like the IsOld assertions. The type system shouldn't care if canonical
objects are always old or not.

[regis, 2016/02/09 17:17:38]

Unfortunately, the type system does care. If you look below at line 4859, we
clone new canonical types to the old space before inserting them in the table.

This ASSERT would catch cases where this type was somehow canonicalized, but not
via the code below. I agree this assert is confusing and probably not very
useful, so I removed this assert here and in 3 other similar locations where the
same test is performed.

Now, I agree with your comment in general and I do not like the cloning code
below either. It is possible that this code is not required anymore, now that we
pass a space argument to all calls allocating new types. This would require some
investigation and cleanup, but in a separate cl.

[rmacnak, 2016/02/09 18:11:20]

I mean everything should still work if we didn't put canonical objects in old
space because doing so is a GC optimization and not an essential part of the
type rules.

+        return this->raw();
+      }
       SetTypeAt(i, type_arg);
     }
     // Canonicalization of a recursive type may change its hash.
@@ -5927,10 +5950,12 @@ bool Function::TestParameterType(
   AbstractType& other_param_type =
       AbstractType::Handle(other.ParameterTypeAt(other_parameter_position));
   if (!other_param_type.IsInstantiated()) {
-    other_param_type = other_param_type.InstantiateFrom(other_type_arguments,
-                                                        bound_error,
-                                                        NULL,  // trail
-                                                        space);
+    other_param_type =
+        other_param_type.InstantiateFrom(other_type_arguments,
+                                         bound_error,
+                                         NULL,  // instantiation_trail
+                                         NULL,  // bound_trail
+                                         space);
     ASSERT((bound_error == NULL) || bound_error->IsNull());
   }
   if (other_param_type.IsDynamicType()) {
@@ -5939,21 +5964,25 @@ bool Function::TestParameterType(
   AbstractType& param_type =
       AbstractType::Handle(ParameterTypeAt(parameter_position));
   if (!param_type.IsInstantiated()) {
-    param_type = param_type.InstantiateFrom(
-        type_arguments, bound_error, NULL /*trail*/, space);
+    param_type = param_type.InstantiateFrom(type_arguments,
+                                            bound_error,
+                                            NULL,  // instantiation_trail
+                                            NULL,  // bound_trail
+                                            space);
     ASSERT((bound_error == NULL) || bound_error->IsNull());
   }
   if (param_type.IsDynamicType()) {
     return test_kind == kIsSubtypeOf;
   }
   if (test_kind == kIsSubtypeOf) {
-    if (!param_type.IsSubtypeOf(other_param_type, bound_error, space) &&
-        !other_param_type.IsSubtypeOf(param_type, bound_error, space)) {
+    if (!param_type.IsSubtypeOf(other_param_type, bound_error, NULL, space) &&
+        !other_param_type.IsSubtypeOf(param_type, bound_error, NULL, space)) {
       return false;
     }
   } else {
     ASSERT(test_kind == kIsMoreSpecificThan);
-    if (!param_type.IsMoreSpecificThan(other_param_type, bound_error, space)) {
+    if (!param_type.IsMoreSpecificThan(
+            other_param_type, bound_error, NULL, space)) {
       return false;
     }
   }
@@ -6376,7 +6405,9 @@ void Function::BuildSignatureParameters(
   while (i < num_fixed_params) {
     param_type = ParameterTypeAt(i);
     ASSERT(!param_type.IsNull());
-    if (instantiate && !param_type.IsInstantiated()) {
+    if (instantiate &&
+        param_type.IsFinalized() &&
+        !param_type.IsInstantiated()) {
       param_type = param_type.InstantiateFrom(instantiator, NULL);
     }
     name = param_type.BuildName(name_visibility);
@@ -6401,7 +6432,9 @@ void Function::BuildSignatureParameters(
         pieces->Add(Symbols::ColonSpace());
       }
       param_type = ParameterTypeAt(i);
-      if (instantiate && !param_type.IsInstantiated()) {
+      if (instantiate &&
+          param_type.IsFinalized() &&
+          !param_type.IsInstantiated()) {
         param_type = param_type.InstantiateFrom(instantiator, NULL);
       }
       ASSERT(!param_type.IsNull());
@@ -6499,7 +6532,7 @@ RawString* Function::BuildSignature(bool instantiate,
                            &pieces);
   pieces.Add(Symbols::RParenArrow());
   AbstractType& res_type = AbstractType::Handle(zone, result_type());
-  if (instantiate && !res_type.IsInstantiated()) {
+  if (instantiate && res_type.IsFinalized() && !res_type.IsInstantiated()) {
     res_type = res_type.InstantiateFrom(instantiator, NULL);
   }
   name = res_type.BuildName(name_visibility);
@@ -14269,7 +14302,7 @@ bool Instance::IsInstanceOf(const AbstractType& other,
   }
   other_class = instantiated_other.type_class();
   return cls.IsSubtypeOf(type_arguments, other_class, other_type_arguments,
-                         bound_error, Heap::kOld);
+                         bound_error, NULL, Heap::kOld);
 }
 
 
@@ -14596,7 +14629,8 @@ bool AbstractType::IsRecursive() const {
 RawAbstractType* AbstractType::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
-    TrailPtr trail,
+    TrailPtr instantiation_trail,
+    TrailPtr bound_trail,
     Heap::Space space) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
@@ -14656,6 +14690,47 @@ void AbstractType::AddOnlyBuddyToTrail(TrailPtr* trail,
 }
 
 
+bool AbstractType::TestAndAddToTrail(TrailPtr* trail) const {
+  if (*trail == NULL) {
+    *trail = new Trail(Thread::Current()->zone(), 4);
+  } else {
+    const intptr_t len = (*trail)->length();
+    for (intptr_t i = 0; i < len; i++) {
+      if ((*trail)->At(i).raw() == this->raw()) {
+        return true;
+      }
+    }
+  }
+  (*trail)->Add(*this);
+  return false;
+}
+
+
+bool AbstractType::TestAndAddBuddyToTrail(TrailPtr* trail,
+                                          const AbstractType& buddy) const {
+  if (*trail == NULL) {
+    *trail = new Trail(Thread::Current()->zone(), 4);
+  } else {
+    const intptr_t len = (*trail)->length();
+    ASSERT((len % 2) == 0);
+    const bool this_is_typeref = IsTypeRef();
+    const bool buddy_is_typeref = buddy.IsTypeRef();
+    ASSERT(this_is_typeref || buddy_is_typeref);
+    for (intptr_t i = 0; i < len; i += 2) {
+      if ((((*trail)->At(i).raw() == this->raw()) ||
+           (buddy_is_typeref && (*trail)->At(i).Equals(*this))) &&
+          (((*trail)->At(i + 1).raw() == buddy.raw()) ||
+           (this_is_typeref && (*trail)->At(i + 1).Equals(buddy)))) {
+        return true;
+      }
+    }
+  }
+  (*trail)->Add(*this);
+  (*trail)->Add(buddy);
+  return false;
+}
+
+
 RawString* AbstractType::BuildName(NameVisibility name_visibility) const {
   Zone* zone = Thread::Current()->zone();
   if (IsBoundedType()) {
@@ -14862,6 +14937,7 @@ bool AbstractType::IsDartFunctionType() const {
 bool AbstractType::TypeTest(TypeTestKind test_kind,
                             const AbstractType& other,
                             Error* bound_error,
+                            TrailPtr bound_trail,
                             Heap::Space space) const {
   ASSERT(IsFinalized());
   ASSERT(other.IsFinalized());
@@ -14932,7 +15008,9 @@ bool AbstractType::TypeTest(TypeTestKind test_kind,
     if (!bound.IsFinalized()) {
       return false;    // TODO(regis): Return "maybe after instantiation".
     }
-    if (bound.IsMoreSpecificThan(other, bound_error)) {
+    // The current bound_trail cannot be used, because operands are swapped and
+    // the test is different anyway (more specific vs. subtype).
+    if (bound.IsMoreSpecificThan(other, bound_error, NULL)) {
       return true;
     }
     return false;  // TODO(regis): We should return "maybe after instantiation".
@@ -14992,6 +15070,7 @@ bool AbstractType::TypeTest(TypeTestKind test_kind,
                            Class::Handle(zone, other.type_class()),
                            TypeArguments::Handle(zone, other.arguments()),
                            bound_error,
+                           bound_trail,
                            space);
 }
 
@@ -15236,7 +15315,8 @@ bool Type::IsInstantiated(TrailPtr trail) const {
 RawAbstractType* Type::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
-    TrailPtr trail,
+    TrailPtr instantiation_trail,
+    TrailPtr bound_trail,
     Heap::Space space) const {
   Zone* zone = Thread::Current()->zone();
   ASSERT(IsFinalized() || IsBeingFinalized());
@@ -15250,32 +15330,21 @@ RawAbstractType* Type::InstantiateFrom(
   if (arguments() == instantiator_type_arguments.raw()) {
     return raw();
   }
-  // If this type is recursive, we may already be instantiating it.
-  Type& instantiated_type = Type::Handle(zone);
-  instantiated_type ^= OnlyBuddyInTrail(trail);
-  if (!instantiated_type.IsNull()) {
-    ASSERT(IsRecursive());
-    return instantiated_type.raw();
-  }
   // 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 or
   // finalizing the type argument vector of a recursive type.
   const Class& cls = Class::Handle(zone, type_class());
-
-  // This uninstantiated type is not modified, as it can be instantiated
-  // with different instantiators. Allocate a new instantiated version of it.
-  instantiated_type =
-      Type::New(cls, TypeArguments::Handle(zone), token_pos(), space);
   TypeArguments& type_arguments = TypeArguments::Handle(zone, 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,
+                                                  instantiation_trail,
+                                                  bound_trail,
                                                   space);
-  instantiated_type.set_arguments(type_arguments);
+  // This uninstantiated type is not modified, as it can be instantiated
+  // with different instantiators. Allocate a new instantiated version of it.
+  const Type& instantiated_type =
+      Type::Handle(zone, Type::New(cls, type_arguments, token_pos(), space));
   if (IsFinalized()) {
     instantiated_type.SetIsFinalized();
   } else {
@@ -15439,6 +15508,12 @@ RawAbstractType* Type::Canonicalize(TrailPtr trail) const {
       // Canonicalize the type arguments of the supertype, if any.
       TypeArguments& type_args = TypeArguments::Handle(zone, arguments());
       type_args = type_args.Canonicalize(trail);
+      if (IsCanonical()) {
+        // Canonicalizing type_args canonicalized this type.
+        ASSERT(IsRecursive());
+        ASSERT(IsOld());
+        return this->raw();
+      }
       set_arguments(type_args);
       type = cls.CanonicalType();  // May be set while canonicalizing type args.
       if (type.IsNull()) {
@@ -15483,6 +15558,12 @@ RawAbstractType* Type::Canonicalize(TrailPtr trail) const {
   // vector may be longer than necessary. This is not an issue.
   ASSERT(type_args.IsNull() || (type_args.Length() >= cls.NumTypeArguments()));
   type_args = type_args.Canonicalize(trail);
+  if (IsCanonical()) {
+    // Canonicalizing type_args canonicalized this type as a side effect.
+    ASSERT(IsRecursive());
+    ASSERT(IsOld());
+    return this->raw();
+  }
   set_arguments(type_args);
 
   // Canonicalizing the type arguments may have changed the index, may have
@@ -15541,6 +15622,7 @@ void Type::set_type_class(const Object& value) const {
 
 
 void Type::set_arguments(const TypeArguments& value) const {
+  ASSERT(!IsCanonical());
   StorePointer(&raw_ptr()->arguments_, value.raw());
 }
 
@@ -15705,7 +15787,8 @@ bool FunctionType::IsInstantiated(TrailPtr trail) const {
 RawAbstractType* FunctionType::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
-    TrailPtr trail,
+    TrailPtr instantiation_trail,
+    TrailPtr bound_trail,
     Heap::Space space) const {
   Zone* zone = Thread::Current()->zone();
   ASSERT(IsFinalized() || IsBeingFinalized());
@@ -15716,36 +15799,25 @@ RawAbstractType* FunctionType::InstantiateFrom(
   if (arguments() == instantiator_type_arguments.raw()) {
     return raw();
   }
-  // If this type is recursive, we may already be instantiating it.
-  FunctionType& instantiated_type = FunctionType::Handle(zone);
-  instantiated_type ^= OnlyBuddyInTrail(trail);
-  if (!instantiated_type.IsNull()) {
-    ASSERT(IsRecursive());
-    return instantiated_type.raw();
-  }
   // Note that the scope class has to be resolved at this time, but not
   // 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(zone, scope_class());
-
-  // This uninstantiated type is not modified, as it can be instantiated
-  // with different instantiators. Allocate a new instantiated version of it.
-  instantiated_type =
-      FunctionType::New(cls,
-                        TypeArguments::Handle(zone),
-                        Function::Handle(zone, signature()),
-                        token_pos(),
-                        space);
   TypeArguments& type_arguments = TypeArguments::Handle(zone, 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,
+                                                  instantiation_trail,
+                                                  bound_trail,
                                                   space);
-  instantiated_type.set_arguments(type_arguments);
+  // This uninstantiated type is not modified, as it can be instantiated
+  // with different instantiators. Allocate a new instantiated version of it.
+  const FunctionType& instantiated_type = FunctionType::Handle(zone,
+      FunctionType::New(cls,
+                        type_arguments,
+                        Function::Handle(zone, signature()),
+                        token_pos(),
+                        space));
   if (IsFinalized()) {
     instantiated_type.SetIsFinalized();
   } else {
@@ -15953,6 +16025,18 @@ RawAbstractType* FunctionType::Canonicalize(TrailPtr trail) const {
   ASSERT(type_args.IsNull() ||
          (type_args.Length() >= scope_cls.NumTypeArguments()));
   type_args = type_args.Canonicalize(trail);
+  // Canonicalizing type_args cannot canonicalize this function type as a side
+  // effect, because function types cannot be recursive. Cycles via typedefs
+  // are detected and disallowed. This is in contract to regular types, where

[rmacnak, 2016/02/09 00:50:22]

contrast

Shouldn't this be ASSERT(!IsCanonical()) then?

[regis, 2016/02/09 17:17:38]

Good catch! The comment on lines 16028-16031 is outdated and not true. I deleted
it. The code and comments below are correct. I first thought that function type
cannot be recursive, but they can as explained below.

+  // the test is necessary. See Type::Canonicalize.
+  if (IsCanonical()) {
+    // Canonicalizing type_args canonicalized this type as a side effect.
+    ASSERT(IsRecursive());
+    // Cycles via typedefs are detected and disallowed, but a function type can
+    // be recursive due to a cycle in its type arguments.
+    ASSERT(IsOld());
+    return this->raw();
+  }
   set_arguments(type_args);
 
   // Replace the actual function by a signature function.
@@ -16050,6 +16134,7 @@ void FunctionType::set_scope_class(const Class& value) const {
 
 
 void FunctionType::set_arguments(const TypeArguments& value) const {
+  ASSERT(!IsCanonical());
   StorePointer(&raw_ptr()->arguments_, value.raw());
 }
 
@@ -16150,21 +16235,28 @@ bool TypeRef::IsEquivalent(const Instance& other, TrailPtr trail) const {
 RawTypeRef* TypeRef::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
-    TrailPtr trail,
+    TrailPtr instantiation_trail,
+    TrailPtr bound_trail,
     Heap::Space space) const {
   TypeRef& instantiated_type_ref = TypeRef::Handle();
-  instantiated_type_ref ^= OnlyBuddyInTrail(trail);
+  instantiated_type_ref ^= OnlyBuddyInTrail(instantiation_trail);
   if (!instantiated_type_ref.IsNull()) {
     return instantiated_type_ref.raw();
   }
+  instantiated_type_ref = TypeRef::New();
+  AddOnlyBuddyToTrail(&instantiation_trail, instantiated_type_ref);
+
   AbstractType& ref_type = AbstractType::Handle(type());
   ASSERT(!ref_type.IsTypeRef());
   AbstractType& instantiated_ref_type = AbstractType::Handle();
   instantiated_ref_type = ref_type.InstantiateFrom(
-      instantiator_type_arguments, bound_error, trail, space);
+      instantiator_type_arguments,
+      bound_error,
+      instantiation_trail,
+      bound_trail,
+      space);
   ASSERT(!instantiated_ref_type.IsTypeRef());
-  instantiated_type_ref = TypeRef::New(instantiated_ref_type);
-  AddOnlyBuddyToTrail(&trail, instantiated_type_ref);
+  instantiated_type_ref.set_type(instantiated_ref_type);
   return instantiated_type_ref.raw();
 }
 
@@ -16176,13 +16268,14 @@ RawTypeRef* TypeRef::CloneUninstantiated(const Class& new_owner,
   if (!cloned_type_ref.IsNull()) {
     return cloned_type_ref.raw();
   }
+  cloned_type_ref = TypeRef::New();
+  AddOnlyBuddyToTrail(&trail, cloned_type_ref);
   AbstractType& ref_type = AbstractType::Handle(type());
   ASSERT(!ref_type.IsTypeRef());
   AbstractType& cloned_ref_type = AbstractType::Handle();
   cloned_ref_type = ref_type.CloneUninstantiated(new_owner, trail);
   ASSERT(!cloned_ref_type.IsTypeRef());
-  cloned_type_ref = TypeRef::New(cloned_ref_type);
-  AddOnlyBuddyToTrail(&trail, cloned_type_ref);
+  cloned_type_ref.set_type(cloned_ref_type);
   return cloned_type_ref.raw();
 }
 
@@ -16219,42 +16312,6 @@ intptr_t TypeRef::Hash() const {
 }
 
 
-bool TypeRef::TestAndAddToTrail(TrailPtr* trail) const {
-  if (*trail == NULL) {
-    *trail = new Trail(Thread::Current()->zone(), 4);
-  } else {
-    const intptr_t len = (*trail)->length();
-    for (intptr_t i = 0; i < len; i++) {
-      if ((*trail)->At(i).raw() == this->raw()) {
-        return true;
-      }
-    }
-  }
-  (*trail)->Add(*this);
-  return false;
-}
-
-
-bool TypeRef::TestAndAddBuddyToTrail(TrailPtr* trail,
-                                     const AbstractType& buddy) const {
-  if (*trail == NULL) {
-    *trail = new Trail(Thread::Current()->zone(), 4);
-  } else {
-    const intptr_t len = (*trail)->length();
-    ASSERT((len % 2) == 0);
-    for (intptr_t i = 0; i < len; i += 2) {
-      if (((*trail)->At(i).raw() == this->raw()) &&
-          ((*trail)->At(i + 1).raw() == buddy.raw())) {
-        return true;
-      }
-    }
-  }
-  (*trail)->Add(*this);
-  (*trail)->Add(buddy);
-  return false;
-}
-
-
 RawTypeRef* TypeRef::New() {
   RawObject* raw = Object::Allocate(TypeRef::kClassId,
                                     TypeRef::InstanceSize(),
@@ -16343,7 +16400,8 @@ void TypeParameter::set_bound(const AbstractType& value) const {
 RawAbstractType* TypeParameter::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
-    TrailPtr trail,
+    TrailPtr instantiation_trail,
+    TrailPtr bound_trail,
     Heap::Space space) const {
   ASSERT(IsFinalized());
   if (instantiator_type_arguments.IsNull()) {
@@ -16355,6 +16413,12 @@ RawAbstractType* TypeParameter::InstantiateFrom(
   // 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.
+
+  // If the instantiated type parameter type_arg is a BoundedType, it means that
+  // it is still uninstantiated and that we are instantiating at finalization
+  // time (i.e. compile time).
+  // Indeed, the instantiator (type arguments of an instance) is always
+  // instantiated at run time and any bounds were checked during allocation.
   return type_arg.raw();
 }
 
@@ -16362,12 +16426,21 @@ RawAbstractType* TypeParameter::InstantiateFrom(
 bool TypeParameter::CheckBound(const AbstractType& bounded_type,
                                const AbstractType& upper_bound,
                                Error* bound_error,
+                               TrailPtr bound_trail,
                                Heap::Space space) const {
   ASSERT((bound_error != NULL) && bound_error->IsNull());
   ASSERT(bounded_type.IsFinalized());
   ASSERT(upper_bound.IsFinalized());
   ASSERT(!bounded_type.IsMalformed());
-  if (bounded_type.IsSubtypeOf(upper_bound, bound_error, space)) {
+  if (bounded_type.IsTypeRef() || upper_bound.IsTypeRef()) {
+    // Shortcut the bound check if the pair <bounded_type, upper_bound> is
+    // already in the trail.
+    if (bounded_type.TestAndAddBuddyToTrail(&bound_trail, upper_bound)) {
+      return true;
+    }
+  }
+
+  if (bounded_type.IsSubtypeOf(upper_bound, bound_error, bound_trail, space)) {
     return true;
   }
   // Set bound_error if the caller is interested and if this is the first error.
@@ -16424,18 +16497,24 @@ RawAbstractType* TypeParameter::CloneUnfinalized() const {
 RawAbstractType* TypeParameter::CloneUninstantiated(
     const Class& new_owner, TrailPtr trail) const {
   ASSERT(IsFinalized());
-  AbstractType& upper_bound = AbstractType::Handle(bound());
-  upper_bound = upper_bound.CloneUninstantiated(new_owner, trail);
+  TypeParameter& clone = TypeParameter::Handle();
+  clone ^= OnlyBuddyInTrail(trail);
+  if (!clone.IsNull()) {
+    return clone.raw();
+  }
   const Class& old_owner = Class::Handle(parameterized_class());
   const intptr_t new_index = index() +
       new_owner.NumTypeArguments() - old_owner.NumTypeArguments();
-  const TypeParameter& clone = TypeParameter::Handle(
-      TypeParameter::New(new_owner,
-                         new_index,
-                         String::Handle(name()),
-                         upper_bound,
-                         token_pos()));
+  AbstractType& upper_bound = AbstractType::Handle(bound());
+  clone = TypeParameter::New(new_owner,
+                             new_index,
+                             String::Handle(name()),
+                             upper_bound,  // Not cloned yet.
+                             token_pos());
   clone.SetIsFinalized();
+  AddOnlyBuddyToTrail(&trail, clone);
+  upper_bound = upper_bound.CloneUninstantiated(new_owner, trail);
+  clone.set_bound(upper_bound);
   return clone.raw();
 }
 
@@ -16590,18 +16669,24 @@ void BoundedType::set_type_parameter(const TypeParameter& value) const {
 RawAbstractType* BoundedType::InstantiateFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error,
-    TrailPtr trail,
+    TrailPtr instantiation_trail,
+    TrailPtr bound_trail,
     Heap::Space space) const {
   ASSERT(IsFinalized());
   AbstractType& bounded_type = AbstractType::Handle(type());
   ASSERT(bounded_type.IsFinalized());
+  AbstractType& instantiated_bounded_type =
+      AbstractType::Handle(bounded_type.raw());
   if (!bounded_type.IsInstantiated()) {
-    bounded_type = bounded_type.InstantiateFrom(instantiator_type_arguments,
-                                                bound_error,
-                                                trail,
-                                                space);
-    // In case types of instantiator_type_arguments are not finalized, then
-    // the instantiated bounded_type is not finalized either.
+    instantiated_bounded_type =
+        bounded_type.InstantiateFrom(instantiator_type_arguments,
+                                     bound_error,
+                                     instantiation_trail,
+                                     bound_trail,
+                                     space);
+    // In case types of instantiator_type_arguments are not finalized
+    // (or instantiated), then the instantiated_bounded_type is not finalized
+    // (or instantiated) either.
     // Note that instantiator_type_arguments must have the final length, though.
   }
   if ((Isolate::Current()->flags().type_checks()) &&
@@ -16609,34 +16694,49 @@ RawAbstractType* BoundedType::InstantiateFrom(
     AbstractType& upper_bound = AbstractType::Handle(bound());
     ASSERT(upper_bound.IsFinalized());
     ASSERT(!upper_bound.IsObjectType() && !upper_bound.IsDynamicType());
-    const TypeParameter& type_param = TypeParameter::Handle(type_parameter());
+    AbstractType& instantiated_upper_bound =
+        AbstractType::Handle(upper_bound.raw());
     if (!upper_bound.IsInstantiated()) {
-      upper_bound = upper_bound.InstantiateFrom(instantiator_type_arguments,
-                                                bound_error,
-                                                trail,
-                                                space);
-      // Instantiated upper_bound may not be finalized. See comment above.
+      instantiated_upper_bound =
+          upper_bound.InstantiateFrom(instantiator_type_arguments,
+                                      bound_error,
+                                      instantiation_trail,
+                                      bound_trail,
+                                      space);
+      // The instantiated_upper_bound may not be finalized or instantiated.
+      // See comment above.
     }
     if (bound_error->IsNull()) {
-      if (bounded_type.IsBeingFinalized() ||
-          upper_bound.IsBeingFinalized() ||
-          (!type_param.CheckBound(bounded_type, upper_bound, bound_error) &&
+      // Shortcut the F-bounded case where we have reached a fixpoint.
+      if (instantiated_bounded_type.Equals(bounded_type) &&
+          instantiated_upper_bound.Equals(upper_bound)) {
+        return bounded_type.raw();
+      }
+      const TypeParameter& type_param = TypeParameter::Handle(type_parameter());
+      if (instantiated_bounded_type.IsBeingFinalized() ||
+          instantiated_upper_bound.IsBeingFinalized() ||
+          (!type_param.CheckBound(instantiated_bounded_type,
+                                  instantiated_upper_bound,
+                                  bound_error,
+                                  bound_trail) &&
            bound_error->IsNull())) {
         // We cannot determine yet whether the bounded_type is below the
         // upper_bound, because one or both of them is still being finalized or
         // uninstantiated.
-        ASSERT(bounded_type.IsBeingFinalized() ||
-               upper_bound.IsBeingFinalized() ||
-               !bounded_type.IsInstantiated() ||
-               !upper_bound.IsInstantiated());
+        ASSERT(instantiated_bounded_type.IsBeingFinalized() ||
+               instantiated_upper_bound.IsBeingFinalized() ||
+               !instantiated_bounded_type.IsInstantiated() ||
+               !instantiated_upper_bound.IsInstantiated());
         // Postpone bound check by returning a new BoundedType with unfinalized
         // or partially instantiated bounded_type and upper_bound, but keeping
         // type_param.
-        bounded_type = BoundedType::New(bounded_type, upper_bound, type_param);
+        instantiated_bounded_type = BoundedType::New(instantiated_bounded_type,
+                                                     instantiated_upper_bound,
+                                                     type_param);
       }
     }
   }
-  return bounded_type.raw();
+  return instantiated_bounded_type.raw();
 }