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

runtime/vm/class_finalizer.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/class_finalizer.h"
 
 #include "vm/flags.h"
 #include "vm/heap.h"
 #include "vm/isolate.h"
 #include "vm/longjump.h"
@@ skipping 500 matching lines @@
     FinalizationKind finalization) {
   ASSERT(arguments.Length() >= cls.NumTypeArguments());
   if (!cls.is_finalized()) {
     const GrowableObjectArray& visited =
       GrowableObjectArray::Handle(GrowableObjectArray::New());
     ResolveInterfaces(cls, visited);
     FinalizeTypeParameters(cls);
   }
   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;
     ASSERT(offset == (cls.NumTypeArguments() - cls.NumTypeParameters()));
     AbstractType& super_type_arg = AbstractType::Handle(Type::DynamicType());
     for (intptr_t i = 0; i < num_super_type_params; i++) {
       if (!super_type_args.IsNull()) {
         super_type_arg = super_type_args.TypeAt(super_offset + i);
         if (!super_type_arg.IsInstantiated()) {
           super_type_arg = super_type_arg.InstantiateFrom(arguments);
@@ skipping 49 matching lines @@
         Error::Handle(),  // No previous error.
         cls, parameterized_type, finalization,
         "type '%s' illegally refers to itself",
         String::Handle(parameterized_type.Name()).ToCString());
     return parameterized_type.raw();
   }
 
   // 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 =
       AbstractTypeArguments::Handle(parameterized_type.arguments());
   if (!arguments.IsNull()) {
     intptr_t num_arguments = arguments.Length();
     for (intptr_t i = 0; i < num_arguments; i++) {
       AbstractType& type_argument = AbstractType::Handle(arguments.TypeAt(i));
       type_argument = FinalizeType(cls, type_argument, finalization);
       arguments.SetTypeAt(i, type_argument);
     }
   }
 
-  // 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.
   // Do this before marking this type as finalized in order to detect cycles.
   if (type_class.IsSignatureClass()) {
     // Signature classes are finalized upon creation.
     ASSERT(type_class.is_finalized());
     // Resolve and finalize the result and parameter types of the signature
     // function of this signature class.
     ResolveAndFinalizeSignature(
@@ skipping 713 matching lines @@
 void ClassFinalizer::ReportError(const char* format, ...) {
   va_list args;
   va_start(args, format);
   const Error& error = Error::Handle(
       Parser::FormatError(Script::Handle(), -1, "Error", format, args));
   va_end(args);
   ReportError(error);
 }
 
 }  // namespace dart