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

runtime/vm/class_finalizer.cc

 // Copyright (c) 2013, 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/class_finalizer.h"
 
 #include "vm/code_generator.h"
 #include "vm/flags.h"
 #include "vm/hash_table.h"
 #include "vm/heap.h"
@@ skipping 656 matching lines @@
   const intptr_t num_type_params = type_cls.NumTypeParameters();
   const intptr_t first_type_param = num_type_args - num_type_params;
   // If the type is not generic (num_type_params == 0) or if its type parameters
   // are instantiated, no divergence can occur. Note that if the type parameters
   // are null, i.e. if the generic type is raw, they are considered
   // instantiated and no divergence can occur.
   if ((num_type_params == 0) ||
       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--) {
     const AbstractType& pending_type = pending_types->At(i);
     if (FLAG_trace_type_finalization) {
       THR_Print("  Comparing with pending type '%s': %s\n",
                 String::Handle(pending_type.Name()).ToCString(),
                 pending_type.ToCString());
     }
     if ((pending_type.raw() != type.raw()) && pending_type.IsType() &&
         (pending_type.type_class() == type_cls.raw())) {
       pending_arguments = pending_type.arguments();
       if (!pending_arguments.IsSubvectorEquivalent(arguments, first_type_param,
                                                    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());
+        }
       }
     }
   }
 }
 
 
 // Expand the type arguments of the given type and finalize its full type
 // argument vector. Return the number of type arguments (0 for a raw type).
 intptr_t ClassFinalizer::ExpandAndFinalizeTypeArguments(
     const Class& cls,
@@ skipping 37 matching lines @@
     // Make the type raw and continue without reporting any error.
     // A static warning should have been reported.
     arguments = TypeArguments::null();
     type.set_arguments(arguments);
   }
 
   // Mark the type as being finalized in order to detect self reference and
   // 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
   // type arguments, followed by the parsed type arguments.
   TypeArguments& full_arguments = TypeArguments::Handle(zone);
   if (FLAG_reify && (num_type_arguments > 0)) {
     // If no type arguments were parsed and if the super types do not prepend
     // type arguments to the vector, we can leave the vector as null.
     if (!arguments.IsNull() || (num_type_arguments > num_type_parameters)) {
       full_arguments = TypeArguments::New(num_type_arguments);
@@ skipping 148 matching lines @@
                 "Instantiating TypeRef '%s': '%s'\n"
                 "  instantiator: '%s'\n",
                 String::Handle(super_type_arg.Name()).ToCString(),
                 ref_type.ToCString(), arguments.ToCString());
           }
           // In the typical case of an F-bounded type, the instantiation of the
           // super_type_arg from arguments is a fixpoint. Take the shortcut.
           // 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;
           }
           Error& error = Error::Handle();
           super_type_arg = super_type_arg.InstantiateFrom(
               arguments, Object::null_type_arguments(), &error,
               instantiation_trail, NULL, Heap::kOld);
           if (!error.IsNull()) {
             // InstantiateFrom does not report an error if the type is still
             // uninstantiated. Instead, it will return a new BoundedType so
             // that the check is postponed to run time.
             ASSERT(super_type_arg.IsInstantiated());
             // Keep only the first bound error.
             if (bound_error->IsNull()) {
               *bound_error = error.raw();
             }
           }
           if (super_type_arg.IsBeingFinalized()) {
             // The super_type_arg was instantiated from a type being finalized.
             // We need to finish finalizing its type arguments.
             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());
+            }
           }
         }
       }
       arguments.SetTypeAt(i, super_type_arg);
     }
     FinalizeTypeArguments(super_class, arguments, super_offset, bound_error,
                           pending_types, instantiation_trail);
   }
 }
 
@@ skipping 235 matching lines @@
     }
 
     // We do not canonicalize type parameters.
     return type_parameter.raw();
   }
 
   // At this point, we can only have a Type.
   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);
   }
 
   const intptr_t num_expanded_type_arguments =
       ExpandAndFinalizeTypeArguments(cls, type, pending_types);
 
   // Self referencing types may get finalized indirectly.
   if (!type.IsFinalized()) {
     // If the type is a function type, we also need to finalize the types in its
@@ skipping 2543 matching lines @@
   ProgramVisitor::VisitFunctions(&function_visitor);
 
   class ClearCodeClassVisitor : public ClassVisitor {
     void Visit(const Class& cls) { cls.DisableAllocationStub(); }
   };
   ClearCodeClassVisitor class_visitor;
   ProgramVisitor::VisitClasses(&class_visitor);
 }
 
 }  // namespace dart