More work on finalization of recursive types (fixes #29357).

runtime/vm/class_finalizer.cc

Index: runtime/vm/class_finalizer.cc
diff --git a/runtime/vm/class_finalizer.cc b/runtime/vm/class_finalizer.cc
index 873092feb4bdd7ba2226b5f27bade77d665a0b89..2a8cb59be218b99b61f473db1e8b6ee5bf5eb41d 100644
--- a/runtime/vm/class_finalizer.cc
+++ b/runtime/vm/class_finalizer.cc
@@ -674,9 +674,11 @@ void ClassFinalizer::CheckRecursiveType(const Class& cls,
       arguments.IsSubvectorInstantiated(first_type_param, num_type_params)) {
     return;
   }
-  // The type parameters are not instantiated. Verify that there is no other
-  // type pending finalization with the same type class, but different
-  // uninstantiated type parameters.
+  // Consider mutually recursive and uninstantiated types pending finalization
+  // with the same type class and report an error if they are not equal in their
+  // raw form, i.e. where each type parameter is substituted with dynamic.
+  // This test eliminates divergent types without restricting recursive types
+  // typically found in the wild.
   TypeArguments& pending_arguments = TypeArguments::Handle(zone);
   const intptr_t num_pending_types = pending_types->length();
   for (intptr_t i = num_pending_types - 1; i >= 0; i--) {
@@ -693,10 +695,21 @@ void ClassFinalizer::CheckRecursiveType(const Class& cls,
                                                    num_type_params) &&
           !pending_arguments.IsSubvectorInstantiated(first_type_param,
                                                      num_type_params)) {
-        // Reject the non-contractive recursive type.
-        const String& type_name = String::Handle(zone, type.Name());
-        ReportError(cls, type.token_pos(), "illegal recursive type '%s'",
-                    type_name.ToCString());
+        const TypeArguments& instantiated_arguments = TypeArguments::Handle(
+            zone, arguments.InstantiateFrom(Object::null_type_arguments(),
+                                            Object::null_type_arguments(), NULL,
+                                            NULL, NULL, Heap::kNew));
+        const TypeArguments& instantiated_pending_arguments =
+            TypeArguments::Handle(zone, pending_arguments.InstantiateFrom(
+                                            Object::null_type_arguments(),
+                                            Object::null_type_arguments(), NULL,
+                                            NULL, NULL, Heap::kNew));
+        if (!instantiated_pending_arguments.IsSubvectorEquivalent(
+                instantiated_arguments, first_type_param, num_type_params)) {
+          const String& type_name = String::Handle(zone, type.Name());
+          ReportError(cls, type.token_pos(), "illegal recursive type '%s'",
+                      type_name.ToCString());
+        }
       }
     }
   }
@@ -754,9 +767,8 @@ intptr_t ClassFinalizer::ExpandAndFinalizeTypeArguments(
   // postpone bound checking (if required) until after all types in the graph of
   // mutually recursive types are finalized.
   type.SetIsBeingFinalized();
-  if (pending_types != NULL) {
-    pending_types->Add(type);
-  }
+  ASSERT(pending_types != NULL);
+  pending_types->Add(type);
 
   // The full type argument vector consists of the type arguments of the
   // super types of type_class, which are initialized from the parsed
@@ -925,8 +937,9 @@ void ClassFinalizer::FinalizeTypeArguments(const Class& cls,
           // Example: class B<T>; class D<T> extends B<D<T>>;
           // While finalizing D<T>, the super type arg D<T> (a typeref) gets
           // instantiated from vector [T], yielding itself.
-          if (super_type_arg.IsTypeRef() && super_type_arg.IsBeingFinalized() &&
+          if (super_type_arg.IsTypeRef() &&
               (super_type_arg.arguments() == arguments.raw())) {
+            ASSERT(super_type_arg.IsBeingFinalized());
             arguments.SetTypeAt(i, super_type_arg);
             continue;
           }
@@ -950,12 +963,30 @@ void ClassFinalizer::FinalizeTypeArguments(const Class& cls,
             ASSERT(super_type_arg.IsTypeRef());
             AbstractType& ref_super_type_arg =
                 AbstractType::Handle(TypeRef::Cast(super_type_arg).type());
+            if (FLAG_trace_type_finalization) {
+              THR_Print("Instantiated TypeRef '%s': '%s'\n",
+                        String::Handle(super_type_arg.Name()).ToCString(),
+                        ref_super_type_arg.ToCString());
+            }
+            CheckRecursiveType(cls, ref_super_type_arg, pending_types);
+            pending_types->Add(ref_super_type_arg);
+            const Class& super_cls =
+                Class::Handle(ref_super_type_arg.type_class());
+            const TypeArguments& super_args =
+                TypeArguments::Handle(ref_super_type_arg.arguments());
+            // Mark as finalized before finalizing to avoid cycles.
             ref_super_type_arg.SetIsFinalized();
-            const Class& cls = Class::Handle(ref_super_type_arg.type_class());
+            // Since the instantiator is different, do not pass the current
+            // instantiation trail, but create a new one by passing NULL.
             FinalizeTypeArguments(
-                cls, TypeArguments::Handle(ref_super_type_arg.arguments()),
-                cls.NumTypeArguments() - cls.NumTypeParameters(), bound_error,
-                pending_types, instantiation_trail);
+                super_cls, super_args,
+                super_cls.NumTypeArguments() - super_cls.NumTypeParameters(),
+                bound_error, pending_types, NULL);
+            if (FLAG_trace_type_finalization) {
+              THR_Print("Finalized instantiated TypeRef '%s': '%s'\n",
+                        String::Handle(super_type_arg.Name()).ToCString(),
+                        ref_super_type_arg.ToCString());
+            }
           }
         }
       }
@@ -1211,9 +1242,8 @@ RawAbstractType* ClassFinalizer::FinalizeType(const Class& cls,
   ASSERT(type.IsType());
 
   // This type is the root type of the type graph if no pending types queue is
-  // allocated yet, and if canonicalization is required.
-  const bool is_root_type =
-      (pending_types == NULL) && (finalization >= kCanonicalize);
+  // allocated yet.
+  const bool is_root_type = pending_types == NULL;
   if (is_root_type) {
     pending_types = new PendingTypes(zone, 4);
   }