Detect and reject illegal recursive types (non-contractive types).

runtime/vm/class_finalizer.cc

Index: runtime/vm/class_finalizer.cc
===================================================================
--- runtime/vm/class_finalizer.cc	(revision 34457)
+++ runtime/vm/class_finalizer.cc	(working copy)
@@ -512,6 +512,72 @@
 }
 
 
+// This function reports a compilation error if the recursive 'type' being
+// finalized is a non-contractive type, i.e. if the induced type set of the
+// instantiation of 'type' with its own type parameters is not finite (see
+// the Dart Language Specification for the definition of the induced type set).
+// This can be detected by looking at the queue of types pending finalization
+// that may be mutually recursive with the checked type.
+void ClassFinalizer::CheckRecursiveType(const Class& cls,
+                                        const Type& type,
+                                        GrowableObjectArray* pending_types) {
+  Isolate* isolate = Isolate::Current();
+  if (FLAG_trace_type_finalization) {
+    OS::Print("Checking recursive type '%s' for class '%s'\n",
+              String::Handle(type.Name()).ToCString(),
+              cls.ToCString());
+  }
+  const Class& type_cls = Class::Handle(isolate, type.type_class());
+  const TypeArguments& arguments =
+      TypeArguments::Handle(isolate, type.arguments());
+  // A type can only be recursive via its type arguments.
+  ASSERT(!arguments.IsNull());
+  const intptr_t num_type_args = arguments.Length();
+  ASSERT(num_type_args > 0);
+  ASSERT(num_type_args == type_cls.NumTypeArguments());
+  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.
+  Type& pending_type = Type::Handle(isolate);
+  TypeArguments& pending_arguments = TypeArguments::Handle(isolate);
+  const intptr_t num_pending_types = pending_types->Length();
+  for (intptr_t i = num_pending_types - 1; i >= 0; i--) {
+    pending_type ^= pending_types->At(i);
+    if (FLAG_trace_type_finalization) {
+      OS::Print("  Comparing with pending type '%s'\n",
+                String::Handle(pending_type.Name()).ToCString());
+    }
+    if ((pending_type.raw() != type.raw()) &&
+        (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 Script& script = Script::Handle(isolate, cls.script());
+        const String& type_name = String::Handle(isolate, type.Name());
+        ReportError(Error::Handle(isolate),  // No previous error.
+                    script, type.token_pos(),
+                    "illegal recursive type '%s'",
+                    type_name.ToCString());
+      }
+    }
+  }
+}
+
+
 // Finalize the type argument vector 'arguments' of the type defined by the
 // class 'cls' parameterized with the type arguments 'cls_args'.
 // The vector 'cls_args' is already initialized as a subvector at the correct
@@ -543,12 +609,15 @@
 // It is too early to canonicalize the type arguments of the vector, because
 // several type argument vectors may be mutually recursive and finalized at the
 // same time. Canonicalization happens when pending types are processed.
+// The trail is required to correctly instantiate a recursive type argument
+// of the super type.
 void ClassFinalizer::FinalizeTypeArguments(
     const Class& cls,
     const TypeArguments& arguments,
     intptr_t num_uninitialized_arguments,
     Error* bound_error,
-    GrowableObjectArray* pending_types) {
+    GrowableObjectArray* pending_types,
+    GrowableObjectArray* trail) {
   ASSERT(arguments.Length() >= cls.NumTypeArguments());
   if (!cls.is_type_finalized()) {
     FinalizeTypeParameters(cls, pending_types);
@@ -574,19 +643,38 @@
     for (intptr_t i = super_offset; i < num_uninitialized_arguments; i++) {
       if (!super_type_args.IsNull()) {
         super_type_arg = super_type_args.TypeAt(i);
-        if (!super_type_arg.IsFinalized()) {
-          super_type_arg ^= FinalizeType(
-              cls, super_type_arg, kFinalize, pending_types);
-          super_type_args.SetTypeAt(i, super_type_arg);
+        if (!super_type_arg.IsTypeRef()) {
+          if (super_type_arg.IsBeingFinalized()) {
+            ASSERT(super_type_arg.IsType());
+            CheckRecursiveType(cls, Type::Cast(super_type_arg), pending_types);
+            if (FLAG_trace_type_finalization) {
+              OS::Print("Creating TypeRef '%s' for class '%s'\n",
+                        String::Handle(super_type_arg.Name()).ToCString(),
+                        cls.ToCString());
+            }
+            super_type_arg = TypeRef::New(super_type_arg);
+            super_type_args.SetTypeAt(i, super_type_arg);
+          } else {
+            if (!super_type_arg.IsFinalized()) {
+              super_type_arg ^= FinalizeType(
+                  cls, super_type_arg, kFinalize, pending_types);
+              super_type_args.SetTypeAt(i, super_type_arg);
+              // Note that super_type_arg may still not be finalized here, in
+              // which case it is a TypeRef to a legal recursive type.
+              // Therefore, it does not need to be instantiated below.
+              // See tests/language/regress_16640_test.dart for an example.
+            }
+          }
         }
         if (!super_type_arg.IsBeingFinalized() &&
             !super_type_arg.IsInstantiated()) {
           Error& error = Error::Handle();
-          super_type_arg = super_type_arg.InstantiateFrom(arguments, &error);
+          super_type_arg =
+              super_type_arg.InstantiateFrom(arguments, &error, trail);
           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.
+            // 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()) {
@@ -598,7 +686,7 @@
       arguments.SetTypeAt(i, super_type_arg);
     }
     FinalizeTypeArguments(super_class, arguments, super_offset,
-                          bound_error, pending_types);
+                          bound_error, pending_types, trail);
   }
 }
 
@@ -763,26 +851,28 @@
     return type.raw();
   }
 
-  if (type.IsBeingFinalized()) {
-    if (FLAG_trace_type_finalization) {
-      OS::Print("Creating TypeRef '%s' for class '%s'\n",
-                String::Handle(type.Name()).ToCString(),
-                cls.ToCString());
-    }
-    return TypeRef::New(type);
+  // Recursive types must be processed in FinalizeTypeArguments() and cannot be
+  // encountered here.
+  ASSERT(!type.IsBeingFinalized());
+
+  // A malformed type gets mapped to a finalized type.
+  ResolveType(cls, type);
+  if (type.IsMalformed()) {
+    ASSERT(type.IsFinalized());
+    return type.raw();
   }
 
-  ResolveType(cls, type);
+  Isolate* isolate = Isolate::Current();
   if (FLAG_trace_type_finalization) {
     OS::Print("Finalizing type '%s' for class '%s'\n",
-              String::Handle(type.Name()).ToCString(),
+              String::Handle(isolate, type.Name()).ToCString(),
               cls.ToCString());
   }
 
   if (type.IsTypeParameter()) {
     const TypeParameter& type_parameter = TypeParameter::Cast(type);
     const Class& parameterized_class =
-        Class::Handle(type_parameter.parameterized_class());
+        Class::Handle(isolate, type_parameter.parameterized_class());
     ASSERT(!parameterized_class.IsNull());
     // The index must reflect the position of this type parameter in the type
     // arguments vector of its parameterized class. The offset to add is the
@@ -802,7 +892,7 @@
 
     if (FLAG_trace_type_finalization) {
       OS::Print("Done finalizing type parameter '%s' with index %" Pd "\n",
-                String::Handle(type_parameter.name()).ToCString(),
+                String::Handle(isolate, type_parameter.name()).ToCString(),
                 type_parameter.index());
     }
 
@@ -813,7 +903,6 @@
   // At this point, we can only have a parameterized_type.
   const Type& parameterized_type = Type::Cast(type);
 
-  Isolate* isolate = Isolate::Current();
   // This type is the root type of the type graph if no pending types queue is
   // allocated yet.
   const bool is_root_type = (pending_types == NULL);
@@ -862,6 +951,12 @@
     parameterized_type.set_arguments(arguments);
   }
 
+  // Mark the type as being finalized in order to detect self reference and
+  // postpone bound checking until after all types in the graph of
+  // mutually recursive types are finalized.
+  parameterized_type.set_is_being_finalized();
+  pending_types->Add(parameterized_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.
@@ -894,8 +989,6 @@
       // checking, in which case type arguments of super classes will be seen
       // as dynamic.
       parameterized_type.set_arguments(full_arguments);
-      // Mark type as being finalized in order to detect self reference.
-      parameterized_type.set_is_being_finalized();
       // Finalize the current type arguments of the type, which are still the
       // parsed type arguments.
       if (!arguments.IsNull()) {
@@ -928,17 +1021,15 @@
         owner_class = type_class.raw();
       }
       if (offset > 0) {
+        GrowableObjectArray& trail =
+            GrowableObjectArray::Handle(isolate, GrowableObjectArray::New());
         FinalizeTypeArguments(owner_class, full_arguments, offset,
-                              &bound_error, pending_types);
+                              &bound_error, pending_types, &trail);
       }
       if (full_arguments.IsRaw(0, num_type_arguments)) {
         // The parameterized_type is raw. Set its argument vector to null, which
         // is more efficient in type tests.
         full_arguments = TypeArguments::null();
-      } else {
-        // Postpone bound checking until after all types in the graph of
-        // mutually recursive types are finalized.
-        pending_types->Add(parameterized_type);
       }
       parameterized_type.set_arguments(full_arguments);
     } else {
@@ -952,6 +1043,7 @@
            !full_arguments.IsRaw(0, num_type_arguments));
     // Mark the type as finalized.
     parameterized_type.SetIsFinalized();
+    // Do not yet remove the type from the pending_types array.
   }
 
   // If we are done finalizing a graph of mutually recursive types, check their
@@ -2387,27 +2479,28 @@
     const MixinAppType& mixin_app_type) {
   // Lookup or create mixin application classes in the library of cls
   // and resolve super type and mixin types.
-  const Library& library = Library::Handle(cls.library());
+  Isolate* isolate = Isolate::Current();
+  const Library& library = Library::Handle(isolate, cls.library());
   ASSERT(!library.IsNull());
-  const Script& script = Script::Handle(cls.script());
+  const Script& script = Script::Handle(isolate, cls.script());
   ASSERT(!script.IsNull());
   const GrowableObjectArray& type_args =
-      GrowableObjectArray::Handle(GrowableObjectArray::New());
+      GrowableObjectArray::Handle(isolate, GrowableObjectArray::New());
   AbstractType& mixin_super_type =
-      AbstractType::Handle(mixin_app_type.super_type());
+      AbstractType::Handle(isolate, mixin_app_type.super_type());
   ResolveType(cls, mixin_super_type);
   ASSERT(mixin_super_type.HasResolvedTypeClass());  // Even if malformed.
   // The super type may have a BoundedType as type argument, but cannot be
   // a BoundedType itself.
   CollectTypeArguments(cls, Type::Cast(mixin_super_type), type_args);
-  AbstractType& mixin_type = AbstractType::Handle();
-  Type& generic_mixin_type = Type::Handle();
-  Class& mixin_type_class = Class::Handle();
-  Class& mixin_app_class = Class::Handle();
-  String& mixin_app_class_name = String::Handle();
-  String& mixin_type_class_name = String::Handle();
-  AbstractType& super_type_arg = AbstractType::Handle();
-  AbstractType& mixin_type_arg = AbstractType::Handle();
+  AbstractType& mixin_type = AbstractType::Handle(isolate);
+  Type& generic_mixin_type = Type::Handle(isolate);
+  Class& mixin_type_class = Class::Handle(isolate);
+  Class& mixin_app_class = Class::Handle(isolate);
+  String& mixin_app_class_name = String::Handle(isolate);
+  String& mixin_type_class_name = String::Handle(isolate);
+  AbstractType& super_type_arg = AbstractType::Handle(isolate);
+  AbstractType& mixin_type_arg = AbstractType::Handle(isolate);
   const intptr_t depth = mixin_app_type.Depth();
   for (intptr_t i = 0; i < depth; i++) {
     mixin_type = mixin_app_type.MixinTypeAt(i);
@@ -2469,7 +2562,7 @@
       // Add the mixin type to the list of interfaces that the mixin application
       // class implements. This is necessary so that cycle check work at
       // compile time (type arguments are ignored by that check).
-      const Array& interfaces = Array::Handle(Array::New(1));
+      const Array& interfaces = Array::Handle(isolate, Array::New(1));
       interfaces.SetAt(0, generic_mixin_type);
       ASSERT(mixin_app_class.interfaces() == Object::empty_array().raw());
       mixin_app_class.set_interfaces(interfaces);
@@ -2491,12 +2584,14 @@
                                  Object::null_type_arguments(),
                                  mixin_type.token_pos());
   }
-  AbstractType& type_arg = AbstractType::Handle();
-  const TypeArguments& mixin_app_args =
-    TypeArguments::Handle(TypeArguments::New(type_args.Length()));
-  for (intptr_t i = 0; i < type_args.Length(); i++) {
-    type_arg ^= type_args.At(i);
-    mixin_app_args.SetTypeAt(i, type_arg);
+  TypeArguments& mixin_app_args = TypeArguments::Handle(isolate);
+  if (type_args.Length() > 0) {
+    mixin_app_args = TypeArguments::New(type_args.Length());
+    AbstractType& type_arg = AbstractType::Handle(isolate);
+    for (intptr_t i = 0; i < type_args.Length(); i++) {
+      type_arg ^= type_args.At(i);
+      mixin_app_args.SetTypeAt(i, type_arg);
+    }
   }
   if (FLAG_trace_class_finalization) {
     OS::Print("ResolveMixinAppType: mixin appl type args: %s\n",
@@ -2528,13 +2623,14 @@
   if (FLAG_trace_class_finalization) {
     OS::Print("Resolving super and interfaces: %s\n", cls.ToCString());
   }
+  Isolate* isolate = Isolate::Current();
   const intptr_t cls_index = cls.id();
   for (intptr_t i = 0; i < visited->length(); i++) {
     if ((*visited)[i] == cls_index) {
       // We have already visited class 'cls'. We found a cycle.
-      const String& class_name = String::Handle(cls.Name());
-      const Script& script = Script::Handle(cls.script());
-      ReportError(Error::Handle(),  // No previous error.
+      const String& class_name = String::Handle(isolate, cls.Name());
+      const Script& script = Script::Handle(isolate, cls.script());
+      ReportError(Error::Handle(isolate),  // No previous error.
                   script, cls.token_pos(),
                   "cyclic reference found for class '%s'",
                   class_name.ToCString());
@@ -2543,8 +2639,8 @@
 
   // If the class/interface has no explicit super class/interfaces
   // and is not a mixin application, we are done.
-  AbstractType& super_type = AbstractType::Handle(cls.super_type());
-  Array& super_interfaces = Array::Handle(cls.interfaces());
+  AbstractType& super_type = AbstractType::Handle(isolate, cls.super_type());
+  Array& super_interfaces = Array::Handle(isolate, cls.interfaces());
   if ((super_type.IsNull() || super_type.IsObjectType()) &&
       (super_interfaces.Length() == 0)) {
     cls.set_is_cycle_free();
@@ -2567,29 +2663,30 @@
 
   // Resolve and check the super type and interfaces of cls.
   visited->Add(cls_index);
-  AbstractType& interface = AbstractType::Handle();
-  Class& interface_class = Class::Handle();
+  AbstractType& interface = AbstractType::Handle(isolate);
+  Class& interface_class = Class::Handle(isolate);
 
   // Resolve super type. Failures lead to a longjmp.
   ResolveType(cls, super_type);
   if (super_type.IsMalformedOrMalbounded()) {
-    ReportError(Error::Handle(super_type.error()));
+    ReportError(Error::Handle(isolate, super_type.error()));
   }
   if (super_type.IsDynamicType()) {
-    const Script& script = Script::Handle(cls.script());
-    ReportError(Error::Handle(),  // No previous error.
+    const Script& script = Script::Handle(isolate, cls.script());
+    ReportError(Error::Handle(isolate),  // No previous error.
                 script, cls.token_pos(),
                 "class '%s' may not extend 'dynamic'",
-                String::Handle(cls.Name()).ToCString());
+                String::Handle(isolate, cls.Name()).ToCString());
   }
   interface_class = super_type.type_class();
   if (interface_class.IsSignatureClass()) {
-    const Script& script = Script::Handle(cls.script());
-    ReportError(Error::Handle(),  // No previous error.
+    const Script& script = Script::Handle(isolate, cls.script());
+    ReportError(Error::Handle(isolate),  // No previous error.
                 script, cls.token_pos(),
                 "class '%s' may not extend function type alias '%s'",
-                String::Handle(cls.Name()).ToCString(),
-                String::Handle(super_type.UserVisibleName()).ToCString());
+                String::Handle(isolate, cls.Name()).ToCString(),
+                String::Handle(isolate,
+                               super_type.UserVisibleName()).ToCString());
   }
 
   // If cls belongs to core lib or to core lib's implementation, restrictions
@@ -2634,12 +2731,12 @@
       }
     }
     if (is_error) {
-      const Script& script = Script::Handle(cls.script());
-      ReportError(Error::Handle(),  // No previous error.
+      const Script& script = Script::Handle(isolate, cls.script());
+      ReportError(Error::Handle(isolate),  // No previous error.
                   script, cls.token_pos(),
                   "'%s' is not allowed to extend '%s'",
-                  String::Handle(cls.Name()).ToCString(),
-                  String::Handle(interface_class.Name()).ToCString());
+                  String::Handle(isolate, cls.Name()).ToCString(),
+                  String::Handle(isolate, interface_class.Name()).ToCString());
     }
   }
   // Now resolve the super interfaces of the super type.
@@ -2652,21 +2749,21 @@
     ASSERT(!interface.IsTypeParameter());  // Should be detected by parser.
     // A malbounded interface is only reported when involved in a type test.
     if (interface.IsMalformed()) {
-      ReportError(Error::Handle(interface.error()));
+      ReportError(Error::Handle(isolate, interface.error()));
     }
     if (interface.IsDynamicType()) {
-      const Script& script = Script::Handle(cls.script());
-      ReportError(Error::Handle(),  // No previous error.
+      const Script& script = Script::Handle(isolate, cls.script());
+      ReportError(Error::Handle(isolate),  // No previous error.
                   script, cls.token_pos(),
                   "'dynamic' may not be used as interface");
     }
     interface_class = interface.type_class();
     if (interface_class.IsSignatureClass()) {
-      const Script& script = Script::Handle(cls.script());
-      ReportError(Error::Handle(),  // No previous error.
+      const Script& script = Script::Handle(isolate, cls.script());
+      ReportError(Error::Handle(isolate),  // No previous error.
                   script, cls.token_pos(),
                   "function type alias '%s' may not be used as interface",
-                  String::Handle(interface_class.Name()).ToCString());
+                  String::Handle(isolate, interface_class.Name()).ToCString());
     }
     // Verify that unless cls belongs to core lib, it cannot extend, implement,
     // or mixin any of Null, bool, num, int, double, String, dynamic.
@@ -2678,18 +2775,19 @@
           interface.IsDoubleType() ||
           interface.IsStringType() ||
           interface.IsDynamicType()) {
-        const Script& script = Script::Handle(cls.script());
-        const String& interface_name = String::Handle(interface_class.Name());
+        const Script& script = Script::Handle(isolate, cls.script());
+        const String& interface_name = String::Handle(isolate,
+                                                      interface_class.Name());
         if (cls.IsMixinApplication()) {
-          ReportError(Error::Handle(),  // No previous error.
+          ReportError(Error::Handle(isolate),  // No previous error.
                       script, cls.token_pos(),
                       "illegal mixin of '%s'",
                       interface_name.ToCString());
         } else {
-          ReportError(Error::Handle(),  // No previous error.
+          ReportError(Error::Handle(isolate),  // No previous error.
                       script, cls.token_pos(),
                       "'%s' is not allowed to extend or implement '%s'",
-                      String::Handle(cls.Name()).ToCString(),
+                      String::Handle(isolate, cls.Name()).ToCString(),
                       interface_name.ToCString());
         }
       }