Overlap type arguments of a type with the type arguments of its super type

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/flags.h"
 #include "vm/heap.h"
 #include "vm/isolate.h"
 #include "vm/longjump.h"
@@ skipping 516 matching lines @@
 }
 
 
 // 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.
-// Example:
+// 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
+// offset smaller than 'num_uninitialized_arguments'.
+// Example 1 (without overlap):
 //   Declared: class C<K, V> extends B<V> { ... }
 //             class B<T> extends A<int> { ... }
 //   Input:    C<String, double> expressed as
-//             cls = C, arguments = [null, null, String, double],
+//             cls = C, arguments = [dynamic, dynamic, String, double],
+//             num_uninitialized_arguments = 2,
 //             i.e. cls_args = [String, double], offset = 2, length = 2.
 //   Output:   arguments = [int, double, String, double]
+// Example 2 (with overlap):
+//   Declared: class C<K, V> extends B<K> { ... }
+//             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]
 void ClassFinalizer::FinalizeTypeArguments(
     const Class& cls,
     const AbstractTypeArguments& arguments,
+    intptr_t num_uninitialized_arguments,
     FinalizationKind finalization,
     Error* bound_error) {
   ASSERT(arguments.Length() >= cls.NumTypeArguments());
   if (!cls.is_type_finalized()) {
     FinalizeTypeParameters(cls);
     ResolveUpperBounds(cls);
   }
   AbstractType& super_type = AbstractType::Handle(cls.super_type());
   if (!super_type.IsNull()) {
     const Class& super_class = Class::Handle(super_type.type_class());
@@ skipping 15 matching lines @@
       // 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()));
+    ASSERT(offset == (cls.NumTypeArguments() - cls.NumOwnTypeArguments()));
     AbstractType& super_type_arg = AbstractType::Handle(Type::DynamicType());
-    for (intptr_t i = 0; i < num_super_type_params; i++) {
+    for (intptr_t i = 0; super_offset + i < num_uninitialized_arguments; i++) {
       if (!super_type_args.IsNull()) {
         super_type_arg = super_type_args.TypeAt(super_offset + i);
         if (!super_type_arg.IsInstantiated()) {
           Error& malformed_error = Error::Handle();
           super_type_arg = super_type_arg.InstantiateFrom(arguments,
                                                           &malformed_error);
           if (!malformed_error.IsNull()) {
             if (!super_type_arg.IsInstantiated()) {
               // CheckTypeArgumentBounds will insert a BoundedType.
             } else if (bound_error->IsNull()) {
               *bound_error = malformed_error.raw();
             }
           }
         }
         if (finalization >= kCanonicalize) {
           super_type_arg = super_type_arg.Canonicalize();
         }
       }
       arguments.SetTypeAt(super_offset + i, super_type_arg);
     }
-    FinalizeTypeArguments(super_class, arguments, finalization, bound_error);
+    FinalizeTypeArguments(super_class, arguments, super_offset,
+                          finalization, bound_error);
   }
 }
 
 
 // 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(
@@ skipping 13 matching lines @@
   const intptr_t num_type_params = cls.NumTypeParameters();
   const intptr_t offset = cls.NumTypeArguments() - num_type_params;
   AbstractType& type_arg = AbstractType::Handle();
   AbstractType& cls_type_param = AbstractType::Handle();
   AbstractType& declared_bound = AbstractType::Handle();
   AbstractType& instantiated_bound = AbstractType::Handle();
   const TypeArguments& cls_type_params =
       TypeArguments::Handle(cls.type_parameters());
   ASSERT((cls_type_params.IsNull() && (num_type_params == 0)) ||
          (cls_type_params.Length() == num_type_params));
+  // In case of overlapping type argument vectors, the same type argument may
+  // get checked against different bounds.
   for (intptr_t i = 0; i < num_type_params; i++) {
     type_arg = arguments.TypeAt(offset + i);
     if (type_arg.IsDynamicType()) {
       continue;
     }
     cls_type_param = cls_type_params.TypeAt(i);
     const TypeParameter& type_param = TypeParameter::Cast(cls_type_param);
     ASSERT(type_param.IsFinalized());
     declared_bound = type_param.bound();
     if (!declared_bound.IsObjectType() && !declared_bound.IsDynamicType()) {
@@ skipping 68 matching lines @@
     // malformed.
     if ((finalization >= kCanonicalize) && !type.IsMalformed()) {
       return type.Canonicalize();
     }
     return type.raw();
   }
   ASSERT(type.IsResolved());
   ASSERT(finalization >= kFinalize);
 
   if (FLAG_trace_type_finalization) {
-    OS::Print("Finalize type '%s' for class '%s'\n",
+    OS::Print("Finalizing type '%s' for class '%s'\n",
               String::Handle(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());
     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(),
+                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);
 
   // Types illegally referring to themselves should have been detected earlier.
   ASSERT(!parameterized_type.IsBeingFinalized());
 
@@ skipping 47 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 = AbstractTypeArguments::null();
     parameterized_type.set_arguments(arguments);
   }
   // The full type argument vector consists of the type arguments of the
-  // super types of type_class, which may be initialized from the parsed
+  // super types of type_class, which are initialized from the parsed
   // type arguments, followed by the parsed type arguments.
   TypeArguments& full_arguments = TypeArguments::Handle();
   Error& bound_error = Error::Handle();
   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);
       // Copy the parsed type arguments at the correct offset in the full type
       // argument vector.
@@ skipping 25 matching lines @@
       // of its signature function and no super type is involved.
       // If the signature class is canonical (not an alias), the owner of its
       // signature function may either be an alias or the enclosing class of a
       // local function, in which case the super type of the enclosing class is
       // also considered when filling up the argument vector.
       if (type_class.IsSignatureClass()) {
         const Function& signature_fun =
             Function::Handle(type_class.signature_function());
         ASSERT(!signature_fun.is_static());
         const Class& sig_fun_owner = Class::Handle(signature_fun.Owner());
-        FinalizeTypeArguments(
-            sig_fun_owner, full_arguments, finalization, &bound_error);
+        if (offset > 0) {
+          FinalizeTypeArguments(sig_fun_owner, full_arguments, offset,
+                                finalization, &bound_error);
+        }
         CheckTypeArgumentBounds(sig_fun_owner, full_arguments, &bound_error);
       } else {
-        FinalizeTypeArguments(
-            type_class, full_arguments, finalization, &bound_error);
+        if (offset > 0) {
+          FinalizeTypeArguments(type_class, full_arguments, offset,
+                                finalization, &bound_error);
+        }
         CheckTypeArgumentBounds(type_class, full_arguments, &bound_error);
       }
       if (full_arguments.IsRaw(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 if (finalization >= kCanonicalize) {
         // FinalizeTypeArguments can modify 'full_arguments',
         // canonicalize afterwards.
         full_arguments ^= full_arguments.Canonicalize();
@@ skipping 26 matching lines @@
   if (!bound_error.IsNull()) {
     // No compile-time error during finalization.
     const String& parameterized_type_name = String::Handle(
         parameterized_type.UserVisibleName());
     const Type& malformed_bound = Type::Handle(
         NewFinalizedMalformedType(bound_error,
                                   Script::Handle(cls.script()),
                                   parameterized_type.token_pos(),
                                   "type '%s' has an out of bound type argument",
                                   parameterized_type_name.ToCString()));
+
+    if (FLAG_trace_type_finalization) {
+      OS::Print("Done finalizing malbounded type '%s' with bound error: %s\n",
+                String::Handle(parameterized_type.Name()).ToCString(),
+                bound_error.ToCString());
+    }
+
     return BoundedType::New(parameterized_type,
                             malformed_bound,
                             TypeParameter::Handle());
   }
 
+  if (FLAG_trace_type_finalization) {
+    OS::Print("Done finalizing type '%s' with %" Pd " type args\n",
+              String::Handle(parameterized_type.Name()).ToCString(),
+              parameterized_type.arguments() == AbstractTypeArguments::null() ?
+                  0 : num_type_arguments);
+  }
+
   if (finalization >= kCanonicalize) {
     return parameterized_type.Canonicalize();
   } else {
     return parameterized_type.raw();
   }
 }
 
 
 void ClassFinalizer::ResolveAndFinalizeSignature(const Class& cls,
                                                  const Function& function) {
@@ skipping 547 matching lines @@
 as the superclass of S&A. The class S&A` declares a type argument T:
 
 Instead of
 S&A<T`, U, V> extends S<T`> implements A<U, V> { }
 
 We now have:
 S&A`<T`, T> extends S<T`> implements M<T> { ... members of M applied here ... }
 S&A<T`, U, V> extends S&A`<T`, Map<U, V>> implements A<U, V> { }
 
 The main implementation difficulty resides in the fact that the type parameters
-U and V in the super type S&A`<T`, Map<U, V>> of S&A refer to the type
-parameters U and V of S&A, not to U and V of A. An instantiation step with
-a properly crafted instantiator vector takes care of the required type parameter
-substitution.
+U and V in the super type S&A`<T`, Map<U, V>> of S&A must refer to the type
+parameters U and V of S&A. However, Map<U, V> is copied from the super type
+Object&M<Map<U, V>> of A and, therefore, U and V refer to A. An instantiation
+step with a properly crafted instantiator vector takes care of the required type
+parameter substitution.
+
+The instantiator vector must end with the type parameters U and V of S&A.
+The offset of the first type parameter U of S&A must be at the finalized index
+of type parameter U of A.
 */
 void ClassFinalizer::ApplyMixinTypedef(const Class& mixin_app_class) {
   // If this mixin typedef is aliasing another mixin typedef, another class
   // will be inserted via recursion. No need to check here.
+  // The mixin type may or may not be finalized yet.
   const Type& mixin_type = Type::Handle(mixin_app_class.mixin());
   const Class& mixin_class = Class::Handle(mixin_type.type_class());
   ASSERT(mixin_class.is_mixin_typedef());
   const Class& aliased_mixin_app_class = Class::Handle(
       mixin_class.SuperClass());
   const Type& aliased_mixin_type = Type::Handle(
       aliased_mixin_app_class.mixin());
   // The name of the inserted mixin application class is the name of mixin
   // class name with a backtick added.
   String& inserted_class_name = String::Handle(mixin_app_class.Name());
@@ skipping 35 matching lines @@
   // It is important that the type parameters of the mixin application class
   // are not finalized yet, because new type parameters may have been added
   // to the super class.
   Class& super_class = Class::Handle(super_type.type_class());
   ASSERT(mixin_app_class.SuperClass() == super_class.raw());
   while (super_class.IsMixinApplication()) {
     super_class = super_class.SuperClass();
   }
   const intptr_t num_super_type_params = super_class.NumTypeParameters();
   const intptr_t num_mixin_type_params = mixin_class.NumTypeParameters();
-  intptr_t offset = aliased_mixin_app_class.NumTypeArguments();
+  intptr_t offset =
+      mixin_class.NumTypeArguments() - mixin_class.NumTypeParameters();
   const TypeArguments& type_params =
       TypeArguments::Handle(mixin_app_class.type_parameters());
   TypeArguments& instantiator = TypeArguments::Handle(
       TypeArguments::New(offset + num_mixin_type_params));
   AbstractType& type = AbstractType::Handle();
   for (intptr_t i = 0; i < num_mixin_type_params; i++) {
     type = type_params.TypeAt(num_super_type_params + i);
     instantiator.SetTypeAt(offset + i, type);
   }
   ASSERT(aliased_mixin_type.IsFinalized());
@@ skipping 43 matching lines @@
       new_super_type_args.SetTypeAt(num_super_type_params + i, type);
     }
   }
   super_type = Type::New(inserted_class,
                          new_super_type_args,
                          mixin_app_class.token_pos());
   mixin_app_class.set_super_type(super_type);
   // Mark this mixin application class as being a typedef.
   mixin_app_class.set_is_mixin_typedef();
   ASSERT(!mixin_app_class.is_type_finalized());
+  ASSERT(!mixin_app_class.is_mixin_type_applied());
   if (FLAG_trace_class_finalization) {
     OS::Print("Inserting class %s to mixin typedef application %s "
               "with super type '%s'\n",
               inserted_class.ToCString(),
               mixin_app_class.ToCString(),
               String::Handle(super_type.Name()).ToCString());
   }
 }
 
 
@@ skipping 985 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