Use trail in type tests involving the call function (fixes #29405).

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/become.h"
@@ skipping 6429 matching lines @@
     this_fun = this_fun.InstantiateSignatureFrom(Object::null_type_arguments(),
                                                  Object::null_type_arguments(),
                                                  Heap::kOld);
   }
   Function& other_fun = Function::Handle(other.raw());
   if (!other_fun.HasInstantiatedSignature()) {
     other_fun = other_fun.InstantiateSignatureFrom(
         Object::null_type_arguments(), Object::null_type_arguments(),
         Heap::kOld);
   }
-  if (!this_fun.TypeTest(kIsSubtypeOf, other_fun, bound_error, Heap::kOld)) {
+  if (!this_fun.TypeTest(kIsSubtypeOf, other_fun, bound_error, NULL,
+                         Heap::kOld)) {
     // For more informative error reporting, use the location of the other
     // function here, since the caller will use the location of this function.
     *bound_error = LanguageError::NewFormatted(
         *bound_error,  // A bound error if non null.
         Script::Handle(other.script()), other.token_pos(), Report::AtLocation,
         Report::kError, Heap::kNew,
         "signature type '%s' of function '%s' is not a subtype of signature "
         "type '%s' of function '%s'\n",
         String::Handle(UserVisibleSignature()).ToCString(),
         String::Handle(UserVisibleName()).ToCString(),
@@ skipping 54 matching lines @@
 // If test_kind == kIsMoreSpecificThan, checks if the type of the specified
 // parameter of this function is more specific than the type of the specified
 // parameter of the other function.
 // Note that we do not apply contravariance of parameter types, but covariance
 // of both parameter types and result type.
 bool Function::TestParameterType(TypeTestKind test_kind,
                                  intptr_t parameter_position,
                                  intptr_t other_parameter_position,
                                  const Function& other,
                                  Error* bound_error,
+                                 TrailPtr bound_trail,
                                  Heap::Space space) const {
   const AbstractType& other_param_type =
       AbstractType::Handle(other.ParameterTypeAt(other_parameter_position));
   if (other_param_type.IsDynamicType()) {
     return true;
   }
   const AbstractType& param_type =
       AbstractType::Handle(ParameterTypeAt(parameter_position));
   if (param_type.IsDynamicType()) {
     return test_kind == kIsSubtypeOf;
   }
   if (test_kind == kIsSubtypeOf) {
-    if (!param_type.IsSubtypeOf(other_param_type, bound_error, NULL, space) &&
-        !other_param_type.IsSubtypeOf(param_type, bound_error, NULL, space)) {
+    if (!param_type.IsSubtypeOf(other_param_type, bound_error, bound_trail,
+                                space) &&
+        !other_param_type.IsSubtypeOf(param_type, bound_error, bound_trail,
+                                      space)) {
       return false;
     }
   } else {
     ASSERT(test_kind == kIsMoreSpecificThan);
-    if (!param_type.IsMoreSpecificThan(other_param_type, bound_error, NULL,
-                                       space)) {
+    if (!param_type.IsMoreSpecificThan(other_param_type, bound_error,
+                                       bound_trail, space)) {
       return false;
     }
   }
   return true;
 }
 
 
 bool Function::HasSameTypeParametersAndBounds(const Function& other) const {
   Thread* thread = Thread::Current();
   Zone* zone = thread->zone();
@@ skipping 24 matching lines @@
       }
     }
   }
   return true;
 }
 
 
 bool Function::TypeTest(TypeTestKind test_kind,
                         const Function& other,
                         Error* bound_error,
+                        TrailPtr bound_trail,
                         Heap::Space space) const {
   const intptr_t num_fixed_params = num_fixed_parameters();
   const intptr_t num_opt_pos_params = NumOptionalPositionalParameters();
   const intptr_t num_opt_named_params = NumOptionalNamedParameters();
   const intptr_t other_num_fixed_params = other.num_fixed_parameters();
   const intptr_t other_num_opt_pos_params =
       other.NumOptionalPositionalParameters();
   const intptr_t other_num_opt_named_params =
       other.NumOptionalNamedParameters();
   // This function requires the same arguments or less and accepts the same
@@ skipping 18 matching lines @@
   Zone* zone = thread->zone();
   // Check the result type.
   const AbstractType& other_res_type =
       AbstractType::Handle(zone, other.result_type());
   if (!other_res_type.IsDynamicType() && !other_res_type.IsVoidType()) {
     const AbstractType& res_type = AbstractType::Handle(zone, result_type());
     if (res_type.IsVoidType()) {
       return false;
     }
     if (test_kind == kIsSubtypeOf) {
-      if (!res_type.IsSubtypeOf(other_res_type, bound_error, NULL, space) &&
-          !other_res_type.IsSubtypeOf(res_type, bound_error, NULL, space)) {
+      if (!res_type.IsSubtypeOf(other_res_type, bound_error, bound_trail,
+                                space) &&
+          !other_res_type.IsSubtypeOf(res_type, bound_error, bound_trail,
+                                      space)) {
         return false;
       }
     } else {
       ASSERT(test_kind == kIsMoreSpecificThan);
-      if (!res_type.IsMoreSpecificThan(other_res_type, bound_error, NULL,
+      if (!res_type.IsMoreSpecificThan(other_res_type, bound_error, bound_trail,
                                        space)) {
         return false;
       }
     }
   }
   // Check the types of fixed and optional positional parameters.
   for (intptr_t i = 0; i < (other_num_fixed_params - other_num_ignored_params +
                             other_num_opt_pos_params);
        i++) {
     if (!TestParameterType(test_kind, i + num_ignored_params,
                            i + other_num_ignored_params, other, bound_error,
-                           space)) {
+                           bound_trail, space)) {
       return false;
     }
   }
   // Check the names and types of optional named parameters.
   if (other_num_opt_named_params == 0) {
     return true;
   }
   // Check that for each optional named parameter of type T of the other
   // function type, there exists an optional named parameter of this function
   // type with an identical name and with a type S that is a either a subtype
   // or supertype of T (if test_kind == kIsSubtypeOf) or that is more specific
   // than T (if test_kind == kIsMoreSpecificThan).
   // Note that SetParameterNameAt() guarantees that names are symbols, so we
   // can compare their raw pointers.
   const int num_params = num_fixed_params + num_opt_named_params;
   const int other_num_params =
       other_num_fixed_params + other_num_opt_named_params;
   bool found_param_name;
   String& other_param_name = String::Handle(zone);
   for (intptr_t i = other_num_fixed_params; i < other_num_params; i++) {
     other_param_name = other.ParameterNameAt(i);
     ASSERT(other_param_name.IsSymbol());
     found_param_name = false;
     for (intptr_t j = num_fixed_params; j < num_params; j++) {
       ASSERT(String::Handle(zone, ParameterNameAt(j)).IsSymbol());
       if (ParameterNameAt(j) == other_param_name.raw()) {
         found_param_name = true;
-        if (!TestParameterType(test_kind, j, i, other, bound_error, space)) {
+        if (!TestParameterType(test_kind, j, i, other, bound_error, bound_trail,
+                               space)) {
           return false;
         }
         break;
       }
     }
     if (!found_param_name) {
       return false;
     }
   }
   return true;
@@ skipping 9157 matching lines @@
         Function::Handle(zone, Type::Cast(instantiated_other).signature());
     Function& sig_fun = Function::Handle(zone, Closure::Cast(*this).function());
     if (!sig_fun.HasInstantiatedSignature()) {
       const TypeArguments& instantiator_type_arguments = TypeArguments::Handle(
           zone, Closure::Cast(*this).instantiator_type_arguments());
       const TypeArguments& function_type_arguments = TypeArguments::Handle(
           zone, Closure::Cast(*this).function_type_arguments());
       sig_fun = sig_fun.InstantiateSignatureFrom(
           instantiator_type_arguments, function_type_arguments, Heap::kOld);
     }
-    return sig_fun.IsSubtypeOf(other_signature, bound_error, Heap::kOld);
+    return sig_fun.IsSubtypeOf(other_signature, bound_error, NULL, Heap::kOld);
   }
   TypeArguments& type_arguments = TypeArguments::Handle(zone);
   if (cls.NumTypeArguments() > 0) {
     type_arguments = GetTypeArguments();
     ASSERT(type_arguments.IsNull() || type_arguments.IsCanonical());
     // The number of type arguments in the instance must be greater or equal to
     // the number of type arguments expected by the instance class.
     // A discrepancy is allowed for closures, which borrow the type argument
     // vector of their instantiator, which may be of a subclass of the class
     // defining the closure. Truncating the vector to the correct length on
@@ skipping 34 matching lines @@
       }
       if (!sig_fun.HasInstantiatedSignature()) {
         const TypeArguments& function_type_arguments =
             TypeArguments::Handle(zone, sig_fun.type_parameters());
         // No bound error possible, since the instance exists.
         sig_fun = sig_fun.InstantiateSignatureFrom(
             type_arguments, function_type_arguments, Heap::kOld);
       }
       const Function& other_signature =
           Function::Handle(zone, Type::Cast(instantiated_other).signature());
-      if (sig_fun.IsSubtypeOf(other_signature, bound_error, Heap::kOld)) {
+      if (sig_fun.IsSubtypeOf(other_signature, bound_error, NULL, Heap::kOld)) {
         return true;
       }
     }
   }
   if (!instantiated_other.IsType()) {
     return false;
   }
   other_class = instantiated_other.type_class();
   if (IsNull()) {
     ASSERT(cls.IsNullClass());
@@ skipping 425 matching lines @@
 
 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);
+    // Note that at least one of 'this' and 'buddy' should be a typeref, with
+    // one exception, when the class of the 'this' type implements the 'call'
+    // method, thereby possibly creating a recursive type (see regress_29405).
     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);
@@ skipping 341 matching lines @@
   if (other_is_dart_function_type || other.IsFunctionType()) {
     if (IsFunctionType()) {
       if (other_is_dart_function_type) {
         return true;
       }
       const Function& other_fun =
           Function::Handle(zone, Type::Cast(other).signature());
       // Check for two function types.
       const Function& fun =
           Function::Handle(zone, Type::Cast(*this).signature());
-      return fun.TypeTest(test_kind, other_fun, bound_error, space);
+      return fun.TypeTest(test_kind, other_fun, bound_error, bound_trail,
+                          space);
     }
     // Check if type S has a call() method of function type T.
     const Function& call_function =
         Function::Handle(zone, type_cls.LookupCallFunctionForTypeTest());
     if (!call_function.IsNull()) {
-      if (other_is_dart_function_type ||
-          call_function.TypeTest(
+      if (other_is_dart_function_type) {
+        return true;
+      }
+      // Shortcut the test involving the call function if the
+      // pair <this, other> is already in the trail.
+      if (TestAndAddBuddyToTrail(&bound_trail, other)) {
+        return true;
+      }
+      if (call_function.TypeTest(
               test_kind, Function::Handle(zone, Type::Cast(other).signature()),
-              bound_error, space)) {
+              bound_error, bound_trail, space)) {
         return true;
       }
     }
   }
   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()),
@@ skipping 6556 matching lines @@
   return UserTag::null();
 }
 
 
 const char* UserTag::ToCString() const {
   const String& tag_label = String::Handle(label());
   return tag_label.ToCString();
 }
 
 }  // namespace dart