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 34435)
+++ runtime/vm/class_finalizer.cc	(working copy)
@@ -512,6 +512,69 @@
 }
 
 
+// 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 parameters are instantiated (or null), no divergence can occur.
+  if ((num_type_params == 0) ||

[srdjan, 2014/03/26 21:35:02]

Does num_type_parames ==0 means that the type parameters are null, or that they
do not exist in type_cls, or is that the same?

[regis, 2014/03/26 23:24:58]

It means that the type_cls is not parameterized (no declared type parameters).
The comment is confusing: "or null" refers to a raw type, not to a
non-parameterized type. I clarified the commment.

+      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 +606,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.

[srdjan, 2014/03/26 21:35:02]

What does it contain/return?

[regis, 2014/03/26 23:24:58]

The trail is not new to this cl. See other functions in object.cc using a trail
to process recursive types.

 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 +640,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 +683,7 @@
       arguments.SetTypeAt(i, super_type_arg);
     }
     FinalizeTypeArguments(super_class, arguments, super_offset,
-                          bound_error, pending_types);
+                          bound_error, pending_types, trail);
   }
 }
 
@@ -763,26 +848,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 +889,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 +900,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 +948,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 +986,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 +1018,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 +1040,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
@@ -2491,12 +2580,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();
+  if (type_args.Length() > 0) {
+    mixin_app_args = TypeArguments::New(type_args.Length());
+    AbstractType& type_arg = AbstractType::Handle();
+    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",