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

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 3597 matching lines @@
 // Type S is specified by this class parameterized with 'type_arguments', and
 // type T by class 'other' parameterized with 'other_type_arguments'.
 // This class and class 'other' do not need to be finalized, however, they must
 // be resolved as well as their interfaces.
 bool Class::TypeTestNonRecursive(const Class& cls,
                                  Class::TypeTestKind test_kind,
                                  const TypeArguments& type_arguments,
                                  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.
   Zone* zone = Thread::Current()->zone();
   Class& thsi = Class::Handle(zone, cls.raw());
   while (true) {
     ASSERT(!thsi.IsVoidClass());
     // Check for DynamicType.
     // Each occurrence of DynamicType in type T is interpreted as the dynamic
     // type, a supertype of all types.
@@ skipping 38 matching lines @@
         // Other type can't be more specific than this one because for that
         // it would have to have all dynamic type arguments which is checked
         // above.
         return test_kind == Class::kIsSubtypeOf;
       }
       return type_arguments.TypeTest(test_kind,
                                      other_type_arguments,
                                      from_index,
                                      num_type_params,
                                      bound_error,
+                                     bound_trail,
                                      space);
     }
     if (other.IsFunctionClass()) {
       // Check if type S has a call() method.
       Function& function =
           Function::Handle(zone, thsi.LookupDynamicFunction(Symbols::Call()));
       if (function.IsNull()) {
         // Walk up the super_class chain.
         Class& cls = Class::Handle(zone, thsi.SuperClass());
         while (!cls.IsNull() && function.IsNull()) {
@@ skipping 40 matching lines @@
         // This type class implements an interface that is parameterized with
         // generic type(s), e.g. it implements List<T>.
         // The uninstantiated type T must be instantiated using the type
         // parameters of this type before performing the type test.
         // The type arguments of this type that are referred to by the type
         // parameters of the interface are at the end of the type vector,
         // after the type arguments of the super type of this type.
         // 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()) {
             *bound_error = error.raw();
           }
           continue;  // Another interface may work better.
         }
       }
       if (interface_class.TypeTest(test_kind,
                                    interface_args,
                                    other,
                                    other_type_arguments,
                                    bound_error,
+                                   bound_trail,
                                    space)) {
         return true;
       }
     }
     // "Recurse" up the class hierarchy until we have reached the top.
     thsi = thsi.SuperClass();
     if (thsi.IsNull()) {
       return false;
     }
   }
   UNREACHABLE();
   return false;
 }
 
 
 // If test_kind == kIsSubtypeOf, checks if type S is a subtype of type T.
 // If test_kind == kIsMoreSpecificThan, checks if S is more specific than T.
 // Type S is specified by this class parameterized with 'type_arguments', and
 // type T by class 'other' parameterized with 'other_type_arguments'.
 // This class and class 'other' do not need to be finalized, however, they must
 // be resolved as well as their interfaces.
 bool Class::TypeTest(TypeTestKind test_kind,
                      const TypeArguments& type_arguments,
                      const Class& other,
                      const TypeArguments& other_type_arguments,
                      Error* bound_error,
+                     TrailPtr bound_trail,
                      Heap::Space space) const {
   return TypeTestNonRecursive(*this,
                               test_kind,
                               type_arguments,
                               other,
                               other_type_arguments,
                               bound_error,
+                              bound_trail,
                               space);
 }
 
 
 bool Class::IsTopLevel() const {
   return Name() == Symbols::TopLevel().raw();
 }
 
 
 bool Class::IsPrivate() const {
@@ skipping 489 matching lines @@
   }
   return true;
 }
 
 
 bool TypeArguments::TypeTest(TypeTestKind test_kind,
                              const TypeArguments& other,
                              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());
   ASSERT(other.Length() >= (from_index + len));
   AbstractType& type = AbstractType::Handle();
   AbstractType& other_type = AbstractType::Handle();
   for (intptr_t i = 0; i < len; i++) {
     type = TypeAt(from_index + i);
     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;
     }
   }
   return true;
 }
 
 
 bool TypeArguments::HasInstantiations() const {
   const Array& prior_instantiations = Array::Handle(instantiations());
   ASSERT(prior_instantiations.Length() > 0);  // Always at least a sentinel.
@@ skipping 29 matching lines @@
 }
 
 
 RawAbstractType* TypeArguments::TypeAt(intptr_t index) const {
   return *TypeAddr(index);
 }
 
 
 void TypeArguments::SetTypeAt(intptr_t index,
                                 const AbstractType& value) const {
+  ASSERT(!IsCanonical());
   StorePointer(TypeAddr(index), value.raw());
 }
 
 
 bool TypeArguments::IsResolved() const {
   AbstractType& type = AbstractType::Handle();
   const intptr_t num_types = Length();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     if (!type.IsResolved()) {
@@ skipping 157 matching lines @@
       return true;
     }
   }
   return false;
 }
 
 
 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() &&
       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, space));
   AbstractType& type = AbstractType::Handle();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     // If this type argument T is null, the type A containing T in its flattened
     // type argument vector V is recursive and is still being finalized.
     // T is the type argument of a super type of A. T is being instantiated
     // during finalization of V, which is also the instantiator. T depends
     // solely on the type parameters of A and will be replaced by a non-null
     // type before A is marked as finalized.
     if (!type.IsNull() && !type.IsInstantiated()) {
       type = type.InstantiateFrom(instantiator_type_arguments,
                                   bound_error,
-                                  trail,
+                                  instantiation_trail,
+                                  bound_trail,
                                   space);
     }
     instantiated_array.SetTypeAt(i, type);
   }
   return instantiated_array.raw();
 }
 
 
 RawTypeArguments* TypeArguments::InstantiateAndCanonicalizeFrom(
     const TypeArguments& instantiator_type_arguments,
@@ skipping 13 matching lines @@
       return TypeArguments::RawCast(prior_instantiations.At(index + 1));
     }
     if (prior_instantiations.At(index) == Smi::New(StubCode::kNoInstantiator)) {
       break;
     }
     index += 2;
   }
   // Cache lookup failed. Instantiate the type arguments.
   TypeArguments& result = TypeArguments::Handle();
   result = InstantiateFrom(
-      instantiator_type_arguments, bound_error, NULL, Heap::kOld);
+      instantiator_type_arguments, bound_error, NULL, NULL, Heap::kOld);
   if ((bound_error != NULL) && !bound_error->IsNull()) {
     return result.raw();
   }
   // Instantiation did not result in bound error. Canonicalize type arguments.
   result = result.Canonicalize();
   // InstantiateAndCanonicalizeFrom is not reentrant. It cannot have been called
   // indirectly, so the prior_instantiations array cannot have grown.
   ASSERT(prior_instantiations.raw() == instantiations());
   // Add instantiator and result to instantiations array.
   intptr_t length = prior_instantiations.Length();
@@ skipping 210 matching lines @@
   const intptr_t hash = Hash();
   intptr_t index = FindIndexInCanonicalTypeArguments(zone, table, *this, hash);
   TypeArguments& result = TypeArguments::Handle(zone);
   result ^= table.At(index);
   if (result.IsNull()) {
     // Canonicalize each type argument.
     AbstractType& type_arg = AbstractType::Handle(zone);
     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.
     intptr_t canonical_hash = hash;
     if (IsRecursive()) {
       canonical_hash = Hash();
     }
     // Canonicalization of the type argument's own type arguments may add an
     // entry to the table, or even grow the table, and thereby change the
     // previously calculated index.
@@ skipping 1092 matching lines @@
     intptr_t parameter_position,
     intptr_t other_parameter_position,
     const TypeArguments& type_arguments,
     const Function& other,
     const TypeArguments& other_type_arguments,
     Error* bound_error,
     Heap::Space space) const {
   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()) {
     return true;
   }
   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;
     }
   }
   return true;
 }
 
 
 bool Function::TypeTest(TypeTestKind test_kind,
                         const TypeArguments& type_arguments,
                         const Function& other,
@@ skipping 402 matching lines @@
   ASSERT((num_fixed_params + num_opt_params) == num_params);
   intptr_t i = 0;
   if (name_visibility == kUserVisibleName) {
     // Hide implicit parameters.
     i = NumImplicitParameters();
   }
   String& name = String::Handle(zone);
   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);
     pieces->Add(name);
     if (i != (num_params - 1)) {
       pieces->Add(Symbols::CommaSpace());
     }
     i++;
   }
   if (num_opt_params > 0) {
     if (num_opt_pos_params > 0) {
       pieces->Add(Symbols::LBracket());
     } else {
       pieces->Add(Symbols::LBrace());
     }
     for (intptr_t i = num_fixed_params; i < num_params; i++) {
       // The parameter name of an optional positional parameter does not need
       // to be part of the signature, since it is not used.
       if (num_opt_named_params > 0) {
         name = ParameterNameAt(i);
         pieces->Add(name);
         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());
       name = param_type.BuildName(name_visibility);
       pieces->Add(name);
       if (i != (num_params - 1)) {
         pieces->Add(Symbols::CommaSpace());
       }
     }
     if (num_opt_pos_params > 0) {
@@ skipping 77 matching lines @@
       pieces.Add(Symbols::RAngleBracket());
     }
   }
   pieces.Add(Symbols::LParen());
   BuildSignatureParameters(instantiate,
                            name_visibility,
                            instantiator,
                            &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);
   pieces.Add(name);
   return Symbols::FromConcatAll(pieces);
 }
 
 
 bool Function::HasInstantiatedSignature() const {
   AbstractType& type = AbstractType::Handle(result_type());
@@ skipping 7749 matching lines @@
                            Heap::kOld)) {
         return true;
       }
     }
   }
   if (!instantiated_other.IsType()) {
     return false;
   }
   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);
 }
 
 
 bool Instance::OperatorEquals(const Instance& other) const {
   // TODO(koda): Optimize for all builtin classes and all classes
   // that do not override operator==.
   return DartLibraryCalls::Equals(*this, other) == Object::bool_true().raw();
 }
 
 
@@ skipping 306 matching lines @@
 bool AbstractType::IsRecursive() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
 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();
   return NULL;
 }
 
 
 RawAbstractType* AbstractType::CloneUnfinalized() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
@@ skipping 39 matching lines @@
   if (*trail == NULL) {
     *trail = new Trail(Thread::Current()->zone(), 4);
   } else {
     ASSERT(OnlyBuddyInTrail(*trail) == AbstractType::null());
   }
   (*trail)->Add(*this);
   (*trail)->Add(buddy);
 }
 
 
+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()) {
     const AbstractType& type = AbstractType::Handle(
         BoundedType::Cast(*this).type());
     if (name_visibility == kPrettyName) {
       return type.BuildName(kPrettyName);
     } else if (name_visibility == kUserVisibleName) {
       return type.BuildName(kUserVisibleName);
     }
@@ skipping 186 matching lines @@
 
 bool AbstractType::IsDartFunctionType() const {
   return HasResolvedTypeClass() &&
       (type_class() == Type::Handle(Type::Function()).type_class());
 }
 
 
 bool AbstractType::TypeTest(TypeTestKind test_kind,
                             const AbstractType& other,
                             Error* bound_error,
+                            TrailPtr bound_trail,
                             Heap::Space space) const {
   ASSERT(IsFinalized());
   ASSERT(other.IsFinalized());
   if (IsMalformed() || other.IsMalformed()) {
     // Malformed types involved in subtype tests should be handled specially
     // by the caller. Malformed types should only be encountered here in a
     // more specific than test.
     ASSERT(test_kind == kIsMoreSpecificThan);
     return false;
   }
@@ skipping 50 matching lines @@
       if (type_param.Equals(other_type_param)) {
         return true;
       }
     }
     const AbstractType& bound = AbstractType::Handle(zone, type_param.bound());
     // We may be checking bounds at finalization time and can encounter
     // a still unfinalized bound. Finalizing the bound here may lead to cycles.
     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".
   }
   if (other.IsTypeParameter()) {
     return false;  // TODO(regis): We should return "maybe after instantiation".
   }
   const Class& type_cls = Class::Handle(zone, type_class());
   // Function types cannot be handled by Class::TypeTest().
   const bool other_is_dart_function_type = other.IsDartFunctionType();
@@ skipping 39 matching lines @@
     }
   }
   if (IsFunctionType()) {
     return false;
   }
   return type_cls.TypeTest(test_kind,
                            TypeArguments::Handle(zone, arguments()),
                            Class::Handle(zone, other.type_class()),
                            TypeArguments::Handle(zone, other.arguments()),
                            bound_error,
+                           bound_trail,
                            space);
 }
 
 
 intptr_t AbstractType::Hash() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return 0;
 }
 
@@ skipping 224 matching lines @@
     num_type_args = len;
     len = cls.NumTypeParameters();  // Check the type parameters only.
   }
   return (len == 0) || args.IsSubvectorInstantiated(num_type_args - len, len);
 }
 
 
 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());
   ASSERT(!IsInstantiated());
   // Return the uninstantiated type unchanged if malformed. No copy needed.
   if (IsMalformed()) {
     return raw();
   }
   // Instantiating this type with its own type arguments as instantiator can
   // occur during finalization and bounds checking. Return the type unchanged.
   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());
-
+  TypeArguments& type_arguments = TypeArguments::Handle(zone, arguments());
+  ASSERT(type_arguments.Length() == cls.NumTypeArguments());
+  type_arguments = type_arguments.InstantiateFrom(instantiator_type_arguments,
+                                                  bound_error,
+                                                  instantiation_trail,
+                                                  bound_trail,
+                                                  space);
   // 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,
-                                                  space);
-  instantiated_type.set_arguments(type_arguments);
+  const Type& instantiated_type =
+      Type::Handle(zone, Type::New(cls, type_arguments, token_pos(), space));
   if (IsFinalized()) {
     instantiated_type.SetIsFinalized();
   } else {
     instantiated_type.SetIsResolved();
   }
   // Canonicalization is not part of instantiation.
   return instantiated_type.raw();
 }
 
 
@@ skipping 143 matching lines @@
     return Object::dynamic_type().raw();
   }
   // Fast canonical lookup/registry for simple types.
   if (!cls.IsGeneric() && !cls.IsClosureClass()) {
     type = cls.CanonicalType();
     if (type.IsNull()) {
       ASSERT(!cls.raw()->IsVMHeapObject() || (isolate == Dart::vm_isolate()));
       // 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()) {
         cls.set_canonical_types(*this);
         SetCanonical();
         return this->raw();
       }
     }
     ASSERT(this->Equals(type));
     ASSERT(type.IsCanonical());
@@ skipping 24 matching lines @@
     index++;
   }
   // The type was not found in the table. It is not canonical yet.
 
   // Canonicalize the type arguments.
   TypeArguments& type_args = TypeArguments::Handle(zone, arguments());
   // In case the type is first canonicalized at runtime, its type argument
   // vector may be longer than necessary. This is not an issue.
   ASSERT(type_args.IsNull() || (type_args.Length() >= cls.NumTypeArguments()));
   type_args = type_args.Canonicalize(trail);
+  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
   // grown the table, or may even have canonicalized this type.
   canonical_types ^= cls.canonical_types();
   if (canonical_types.IsNull()) {
     canonical_types = empty_array().raw();
   }
   length = canonical_types.Length();
   while (index < length) {
@@ skipping 38 matching lines @@
 }
 
 
 void Type::set_type_class(const Object& value) const {
   ASSERT(!value.IsNull() && (value.IsClass() || value.IsUnresolvedClass()));
   StorePointer(&raw_ptr()->type_class_, value.raw());
 }
 
 
 void Type::set_arguments(const TypeArguments& value) const {
+  ASSERT(!IsCanonical());
   StorePointer(&raw_ptr()->arguments_, value.raw());
 }
 
 
 RawType* Type::New(Heap::Space space) {
   RawObject* raw = Object::Allocate(Type::kClassId,
                                     Type::InstanceSize(),
                                     space);
   return reinterpret_cast<RawType*>(raw);
 }
@@ skipping 144 matching lines @@
   return
       (num_type_params == 0) ||
       type_arguments.IsSubvectorInstantiated(num_type_args - num_type_params,
                                              num_type_params);
 }
 
 
 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());
   ASSERT(!IsInstantiated());
   ASSERT(!IsMalformed());  // FunctionType cannot be malformed.
   // Instantiating this type with its own type arguments as instantiator can
   // occur during finalization and bounds checking. Return the type unchanged.
   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());
-
+  TypeArguments& type_arguments = TypeArguments::Handle(zone, arguments());
+  ASSERT(type_arguments.Length() == cls.NumTypeArguments());
+  type_arguments = type_arguments.InstantiateFrom(instantiator_type_arguments,
+                                                  bound_error,
+                                                  instantiation_trail,
+                                                  bound_trail,
+                                                  space);
   // This uninstantiated type is not modified, as it can be instantiated
   // with different instantiators. Allocate a new instantiated version of it.
-  instantiated_type =
+  const FunctionType& instantiated_type = FunctionType::Handle(zone,
       FunctionType::New(cls,
-                        TypeArguments::Handle(zone),
+                        type_arguments,
                         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,
-                                                  space);
-  instantiated_type.set_arguments(type_arguments);
+                        space));
   if (IsFinalized()) {
     instantiated_type.SetIsFinalized();
   } else {
     instantiated_type.SetIsResolved();
   }
   // Canonicalization is not part of instantiation.
   return instantiated_type.raw();
 }
 
 
@@ skipping 187 matching lines @@
   }
   // The type was not found in the table. It is not canonical yet.
 
   // Canonicalize the type arguments.
   TypeArguments& type_args = TypeArguments::Handle(zone, arguments());
   // In case the type is first canonicalized at runtime, its type argument
   // vector may be longer than necessary. This is not an issue.
   ASSERT(type_args.IsNull() ||
          (type_args.Length() >= 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.
   const Function& fun = Function::Handle(zone, signature());
   if (!fun.IsSignatureFunction()) {
     Function& sig_fun = Function::Handle(zone,
         Function::NewSignatureFunction(scope_cls, TokenPosition::kNoSource));
     type = fun.result_type();
     type = type.Canonicalize(trail);
     sig_fun.set_result_type(type);
@@ skipping 77 matching lines @@
 }
 
 
 void FunctionType::set_scope_class(const Class& value) const {
   ASSERT(!value.IsNull());
   StorePointer(&raw_ptr()->scope_class_, value.raw());
 }
 
 
 void FunctionType::set_arguments(const TypeArguments& value) const {
+  ASSERT(!IsCanonical());
   StorePointer(&raw_ptr()->arguments_, value.raw());
 }
 
 
 void FunctionType::set_signature(const Function& value) const {
   StorePointer(&raw_ptr()->signature_, value.raw());
 }
 
 
 RawFunctionType* FunctionType::New(Heap::Space space) {
@@ skipping 80 matching lines @@
   if (TestAndAddBuddyToTrail(&trail, AbstractType::Cast(other))) {
     return true;
   }
   return AbstractType::Handle(type()).IsEquivalent(other, trail);
 }
 
 
 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();
 }
 
 
 RawTypeRef* TypeRef::CloneUninstantiated(const Class& new_owner,
                                          TrailPtr trail) const {
   TypeRef& cloned_type_ref = TypeRef::Handle();
   cloned_type_ref ^= OnlyBuddyInTrail(trail);
   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();
 }
 
 
 void TypeRef::set_type(const AbstractType& value) const {
   ASSERT(value.IsFunctionType() || value.HasResolvedTypeClass());
   ASSERT(!value.IsTypeRef());
   StorePointer(&raw_ptr()->type_, value.raw());
 }
 
@@ skipping 16 matching lines @@
 
 
 intptr_t TypeRef::Hash() const {
   // Do not calculate the hash of the referenced type to avoid divergence.
   const uint32_t result =
       Class::Handle(AbstractType::Handle(type()).type_class()).id();
   return FinalizeHash(result);
 }
 
 
-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(),
                                     Heap::kOld);
   return reinterpret_cast<RawTypeRef*>(raw);
 }
 
 
 RawTypeRef* TypeRef::New(const AbstractType& type) {
   const TypeRef& result = TypeRef::Handle(TypeRef::New());
@@ skipping 68 matching lines @@
 
 
 void TypeParameter::set_bound(const AbstractType& value) const {
   StorePointer(&raw_ptr()->bound_, value.raw());
 }
 
 
 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()) {
     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.
+
+  // 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();
 }
 
 
 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.
   if ((bound_error != NULL) && bound_error->IsNull()) {
     // Report the bound error only if both the bounded type and the upper bound
     // are instantiated. Otherwise, we cannot tell yet it is a bound error.
     if (bounded_type.IsInstantiated() && upper_bound.IsInstantiated()) {
       const String& bounded_type_name = String::Handle(
           bounded_type.UserVisibleName());
       const String& upper_bound_name = String::Handle(
@@ skipping 36 matching lines @@
                             index(),
                             String::Handle(name()),
                             AbstractType::Handle(bound()),
                             token_pos());
 }
 
 
 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();
 }
 
 
 intptr_t TypeParameter::Hash() const {
   ASSERT(IsFinalized());
   uint32_t result = Class::Handle(parameterized_class()).id();
   // No need to include the hash of the bound, since the type parameter is fully
   // identified by its class and index.
   result = CombineHashes(result, index());
@@ skipping 134 matching lines @@
   // 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());
 }
 
 
 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()) &&
       (bound_error != NULL) && bound_error->IsNull()) {
     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();
 }
 
 
 RawAbstractType* BoundedType::CloneUnfinalized() const {
   if (IsFinalized()) {
     return raw();
   }
   AbstractType& bounded_type = AbstractType::Handle(type());
 
   bounded_type = bounded_type.CloneUnfinalized();
@@ skipping 4726 matching lines @@
   return UserTag::null();
 }
 
 
 const char* UserTag::ToCString() const {
   const String& tag_label = String::Handle(label());
   return tag_label.ToCString();
 }
 
 }  // namespace dart