Support cyclic types and F-bounded quantification (issue 439).

runtime/vm/class_finalizer.cc

Index: runtime/vm/class_finalizer.cc
===================================================================
--- runtime/vm/class_finalizer.cc	(revision 7045)
+++ runtime/vm/class_finalizer.cc	(working copy)
@@ -518,11 +518,29 @@
   }
   Type& super_type = Type::Handle(cls.super_type());
   if (!super_type.IsNull()) {
-    super_type ^= FinalizeType(cls, super_type, finalization);
-    cls.set_super_type(super_type);
     const Class& super_class = Class::Handle(super_type.type_class());
-    const AbstractTypeArguments& super_type_args =
-        AbstractTypeArguments::Handle(super_type.arguments());
+    AbstractTypeArguments& super_type_args = AbstractTypeArguments::Handle();
+    if (super_type.IsBeingFinalized()) {
+      // This type references itself via its type arguments. This is legal, but
+      // we must avoid the fractal of death. We therefore map the inner most

[srdjan, 2012/04/26 22:30:21]

Need a link to 'fractal of death'  description ;-)

Also "innermost"

[regis, 2012/04/26 22:39:04]

Renamed "fractal of death" to "endless recursion".
Done.

+      // super type to Dynamic.
+      // Note that a direct self-reference via the super class chain is illegal
+      // and reported as an error earlier.
+      // Such legal self-references occur with F-bounded quantification.
+      // Example 1: class Derived extends Base<Derived>.
+      // The type 'Derived' forms a cycle by pointing to itself via its
+      // flattened type argument vector: Derived[Base[Derived[Base[...]]]]
+      // We break the cycle as follows: Derived[Base[Derived[Dynamic]]]
+      // Example 2: class Derived extends Base<Middle<Derived>> results in
+      // Derived[Base[Middle[Derived[Dynamic]]]]
+      // Example 3: class Derived<T> extends Base<Derived<T>> results in
+      // Derived[Base[Derived[Dynamic]], T].
+      ASSERT(super_type_args.IsNull());  // Same as a vector of Dynamic.
+    } else {
+      super_type ^= FinalizeType(cls, super_type, finalization);
+      cls.set_super_type(super_type);
+      super_type_args = super_type.arguments();
+    }
     const intptr_t num_super_type_params = super_class.NumTypeParameters();
     const intptr_t offset = super_class.NumTypeArguments();
     const intptr_t super_offset = offset - num_super_type_params;
@@ -592,6 +610,19 @@
   // Mark type as being finalized in order to detect illegal self reference.
   parameterized_type.set_is_being_finalized();
 
+  // The type class does not need to be finalized in order to finalize the type,
+  // however, it must at least be resolved (this was done as part of resolving
+  // the type itself, a precondition to calling FinalizeType).
+  // Also, the interfaces of the type class must be resolved and the type
+  // parameters of the type class must be finalized.
+  Class& type_class = Class::Handle(parameterized_type.type_class());
+  if (!type_class.is_finalized()) {
+    const GrowableObjectArray& visited =
+      GrowableObjectArray::Handle(GrowableObjectArray::New());
+    ResolveInterfaces(type_class, visited);
+    FinalizeTypeParameters(type_class);
+  }
+
   // Finalize the current type arguments of the type, which are still the
   // parsed type arguments.
   AbstractTypeArguments& arguments =
@@ -605,19 +636,6 @@
     }
   }
 
-  // The type class does not need to be finalized in order to finalize the type,
-  // however, it must at least be resolved (this was done as part of resolving
-  // the type itself, a precondition to calling FinalizeType).
-  // Also, the interfaces of the type class must be resolved and the type
-  // parameters of the type class must be finalized.
-  Class& type_class = Class::Handle(parameterized_type.type_class());
-  if (!type_class.is_finalized()) {
-    const GrowableObjectArray& visited =
-      GrowableObjectArray::Handle(GrowableObjectArray::New());
-    ResolveInterfaces(type_class, visited);
-    FinalizeTypeParameters(type_class);
-  }
-
   // If the type class is a signature class, we are finalizing its signature
   // type, thereby finalizing the result type and parameter types of its
   // signature function.