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

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/heap.h"
 #include "vm/isolate.h"
@@ skipping 494 matching lines @@
     for (intptr_t i = 0; i < num_types; i++) {
       type_parameter ^= type_parameters.TypeAt(i);
       type_parameter ^= FinalizeType(
           cls, type_parameter, kFinalize, pending_types);
       type_parameters.SetTypeAt(i, type_parameter);
     }
   }
 }
 
 
+// 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
 // position in the passed in 'arguments' vector.
 // The subvector 'cls_args' has length cls.NumTypeParameters() and starts at
 // offset cls.NumTypeArguments() - cls.NumTypeParameters() of the 'arguments'
 // vector.
 // The type argument vector of cls may overlap the type argument vector of its
 // super class. In case of an overlap, the overlapped type arguments of the
 // super class are already initialized. The still uninitialized ones have an
@@ skipping 11 matching lines @@
 //             class B<T> extends A<int> { ... }
 //   Input:    C<String, double> expressed as
 //             cls = C, arguments = [dynamic, String, double],
 //             num_uninitialized_arguments = 1,
 //             i.e. cls_args = [String, double], offset = 1, length = 2.
 //   Output:   arguments = [int, String, double]
 //
 // 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);
     ResolveUpperBounds(cls);
   }
   AbstractType& super_type = AbstractType::Handle(cls.super_type());
   if (!super_type.IsNull()) {
     const Class& super_class = Class::Handle(super_type.type_class());
     const intptr_t num_super_type_params = super_class.NumTypeParameters();
     const intptr_t num_super_type_args = super_class.NumTypeArguments();
     ASSERT(num_super_type_args ==
            (cls.NumTypeArguments() - cls.NumOwnTypeArguments()));
     if (!super_type.IsFinalized() && !super_type.IsBeingFinalized()) {
       super_type ^= FinalizeType(
           cls, super_type, kFinalize, pending_types);
       cls.set_super_type(super_type);
     }
     TypeArguments& super_type_args = TypeArguments::Handle(
         super_type.arguments());
     // Offset of super type's type parameters in cls' type argument vector.
     const intptr_t super_offset = num_super_type_args - num_super_type_params;
     AbstractType& super_type_arg = AbstractType::Handle(Type::DynamicType());
     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()) {
               *bound_error = error.raw();
             }
           }
         }
       }
       arguments.SetTypeAt(i, super_type_arg);
     }
     FinalizeTypeArguments(super_class, arguments, super_offset,
-                          bound_error, pending_types);
+                          bound_error, pending_types, trail);
   }
 }
 
 
 // Check the type argument vector 'arguments' against the corresponding bounds
 // of the type parameters of class 'cls' and, recursively, of its superclasses.
 // Replace a type argument that cannot be checked at compile time by a
 // BoundedType, thereby postponing the bound check to run time.
 // Return a bound error if a type argument is not within bound at compile time.
 void ClassFinalizer::CheckTypeArgumentBounds(const Class& cls,
@@ skipping 144 matching lines @@
     return type.raw();
   }
   ASSERT(finalization >= kFinalize);
 
   if (type.IsTypeRef()) {
     // The referenced type will be finalized later by the code that set the
     // is_being_finalized mark bit.
     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
     // number of type arguments in the super type, which is equal to the
     // difference in number of type arguments and type parameters of the
     // parameterized class.
     const intptr_t offset = parameterized_class.NumTypeArguments() -
                             parameterized_class.NumTypeParameters();
     // Calling NumTypeParameters() may finalize this type parameter if it
     // belongs to a mixin application class.
     if (!type_parameter.IsFinalized()) {
       type_parameter.set_index(type_parameter.index() + offset);
       type_parameter.set_is_finalized();
     } else {
       ASSERT(cls.IsMixinApplication());
     }
 
     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());
     }
 
     // We do not canonicalize type parameters.
     return type_parameter.raw();
   }
 
   // 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);
   GrowableObjectArray& types = GrowableObjectArray::Handle(isolate);
   if (is_root_type) {
     types = GrowableObjectArray::New();
     pending_types = &types;
   }
 
   // The type class does not need to be finalized in order to finalize the type,
@@ skipping 28 matching lines @@
                   script, parameterized_type.token_pos(),
                   "wrong number of type arguments for class '%s'",
                   type_class_name.ToCString());
     }
     // Make the type raw and continue without reporting any error.
     // A static warning should have been reported.
     arguments = TypeArguments::null();
     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.
   TypeArguments& full_arguments = TypeArguments::Handle(isolate);
   Error& bound_error = Error::Handle(isolate);
   if (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 12 matching lines @@
         }
         full_arguments.SetTypeAt(offset + i, type_arg);
       }
       // Replace the compile-time argument vector (of length zero or
       // num_type_parameters) of this type being finalized with the still
       // unfinalized run-time argument vector (of length num_type_arguments).
       // This type being finalized may be recursively reached via bounds
       // 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()) {
         for (intptr_t i = 0; i < num_type_parameters; i++) {
           type_arg = full_arguments.TypeAt(offset + i);
           ASSERT(!type_arg.IsBeingFinalized());
           type_arg = FinalizeType(cls, type_arg, kFinalize, pending_types);
           if (type_arg.IsMalformed()) {
             // Malformed type arguments are mapped to dynamic.
             type_arg = Type::DynamicType();
@@ skipping 12 matching lines @@
       Class& owner_class = Class::Handle(isolate);
       if (type_class.IsSignatureClass()) {
         const Function& signature_fun =
             Function::Handle(isolate, type_class.signature_function());
         ASSERT(!signature_fun.is_static());
         owner_class = signature_fun.Owner();
       } else {
         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 {
       ASSERT(full_arguments.IsNull());  // Use null vector for raw type.
     }
   }
 
   // Self referencing types may get finalized indirectly.
   if (!parameterized_type.IsFinalized()) {
     ASSERT(full_arguments.IsNull() ||
            !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
   // bounds.
   if (is_root_type) {
     Type& type = Type::Handle(isolate);
     for (intptr_t i = 0; i < types.Length(); i++) {
       type ^= types.At(i);
       CheckTypeBounds(cls, type);
     }
@@ skipping 1414 matching lines @@
     arg = Type::DynamicType();
     collected_args.Add(arg);
   }
 }
 
 
 RawType* ClassFinalizer::ResolveMixinAppType(
     const Class& cls,
     const MixinAppType& mixin_app_type) {
   // Lookup or create mixin application classes in the library of cls
   // and resolve super type and mixin types.

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

This method may benefit from prefetching isolate.

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

Done.

   const Library& library = Library::Handle(cls.library());
   ASSERT(!library.IsNull());
   const Script& script = Script::Handle(cls.script());
   ASSERT(!script.IsNull());
   const GrowableObjectArray& type_args =
       GrowableObjectArray::Handle(GrowableObjectArray::New());
   AbstractType& mixin_super_type =
       AbstractType::Handle(mixin_app_type.super_type());
   ResolveType(cls, mixin_super_type);
   ASSERT(mixin_super_type.HasResolvedTypeClass());  // Even if malformed.
@@ skipping 84 matching lines @@
                   mixin_app_class.ToCString());
       }
     }
     // This mixin application class becomes the type class of the super type of
     // the next mixin application class. It is however too early to provide the
     // correct super type arguments. We use the raw type for now.
     mixin_super_type = Type::New(mixin_app_class,
                                  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",
               mixin_app_args.ToCString());
   }
   // The mixin application class at depth k is a subclass of mixin application
   // class at depth k - 1. Build a new super type with the class at the highest
   // depth (the last one processed by the loop above) as the type class and the
   // collected type arguments from the super type and all mixin types.
   // This super type replaces the MixinAppType object in the class that extends
@@ skipping 421 matching lines @@
   expected_name ^= String::New("_offset");
   ASSERT(String::EqualsIgnoringPrivateKey(name, expected_name));
   field ^= fields_array.At(2);
   ASSERT(field.Offset() == TypedDataView::length_offset());
   name ^= field.name();
   ASSERT(name.Equals("length"));
 #endif
 }
 
 }  // namespace dart