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

runtime/vm/object.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/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 30 matching lines @@
 #include "vm/symbols.h"
 #include "vm/timer.h"
 #include "vm/unicode.h"
 
 namespace dart {
 
 DEFINE_FLAG(int, huge_method_cutoff_in_code_size, 200000,
     "Huge method cutoff in unoptimized code size (in bytes).");
 DEFINE_FLAG(int, huge_method_cutoff_in_tokens, 20000,
     "Huge method cutoff in tokens: Disables optimizations for huge methods.");
+DEFINE_FLAG(bool, overlap_type_arguments, true,
+    "When possible, partially or fully overlap the type arguments of a type "
+    "with the type arguments of its super type.");
 DEFINE_FLAG(bool, show_internal_names, false,
     "Show names of internal classes (e.g. \"OneByteString\") in error messages "
     "instead of showing the corresponding interface names (e.g. \"String\")");
 DEFINE_FLAG(bool, trace_disabling_optimized_code, false,
     "Trace disabling optimized code.");
 DEFINE_FLAG(bool, throw_on_javascript_int_overflow, false,
     "Throw an exception when the result of an integer calculation will not "
     "fit into a javascript integer.");
 DECLARE_FLAG(bool, eliminate_type_checks);
 DECLARE_FLAG(bool, enable_type_checks);
@@ skipping 1636 matching lines @@
     ClassFinalizer::ApplyMixinType(*this);
   }
   if (type_parameters() == TypeArguments::null()) {
     return 0;
   }
   const TypeArguments& type_params = TypeArguments::Handle(type_parameters());
   return type_params.Length();
 }
 
 
+intptr_t Class::NumOwnTypeArguments() const {

[hausner, 2013/10/11 18:00:58]

As discussed offline, it may be worth it to cache this computed value in the
class object. (Separate change.)

[regis, 2013/10/11 18:36:09]

Yes, it is worth doing (in another change).

+  Isolate* isolate = Isolate::Current();
+  const intptr_t num_type_params = NumTypeParameters();
+  if (!FLAG_overlap_type_arguments ||
+      (num_type_params == 0) ||
+      (super_type() == AbstractType::null()) ||
+      (super_type() == isolate->object_store()->object_type())) {
+    return num_type_params;
+  }
+  ASSERT(!IsMixinApplication() || is_mixin_type_applied());
+  const AbstractType& sup_type = AbstractType::Handle(isolate, super_type());
+  ASSERT(sup_type.IsResolved());
+  const AbstractTypeArguments& sup_type_args =
+      AbstractTypeArguments::Handle(isolate, sup_type.arguments());
+  if (sup_type_args.IsNull()) {
+    // The super type is raw or the super class is non generic.
+    // In either case, overlapping is not possible.
+    return num_type_params;
+  }
+  const intptr_t num_sup_type_args = sup_type_args.Length();
+  // At this point, the super type may or may not be finalized. In either case,
+  // the result of this function must remain the same.
+  // The value of num_sup_type_args may increase when the super type is
+  // finalized, but the last num_sup_type_args type arguments will not be
+  // modified by finalization, only shifted to higher indices in the vector.
+  // They may however get wrapped in a BoundedType, which we skip.
+  const AbstractTypeArguments& type_params =
+      AbstractTypeArguments::Handle(isolate, type_parameters());
+  // Determine the maximum overlap of a prefix of the vector consisting of the
+  // type parameters of this class with a suffix of the vector consisting of the
+  // type arguments of the super type of this class.
+  // The number of own type arguments of this class is the number of its type
+  // parameters minus the number of type arguments in the overlap.
+  // Attempt to overlap the whole vector of type parameters; reduce the size
+  // of the vector (keeping the first type parameter) until it fits or until
+  // its size is zero.
+  TypeParameter& type_param = TypeParameter::Handle(isolate);
+  AbstractType& sup_type_arg = AbstractType::Handle(isolate);
+  for (intptr_t num_overlapping_type_args =
+           (num_type_params < num_sup_type_args) ?
+               num_type_params : num_sup_type_args;
+       num_overlapping_type_args > 0; num_overlapping_type_args--) {
+    intptr_t i = 0;
+    for (; i < num_overlapping_type_args; i++) {
+      type_param ^= type_params.TypeAt(i);
+      sup_type_arg = sup_type_args.TypeAt(
+          num_sup_type_args - num_overlapping_type_args + i);
+      // BoundedType can nest in case the finalized super type has bounded type
+      // arguments that overlap multiple times in its own super class chain.
+      while (sup_type_arg.IsBoundedType()) {
+        sup_type_arg = BoundedType::Cast(sup_type_arg).type();
+      }
+      if (!type_param.Equals(sup_type_arg)) break;
+    }
+    if (i == num_overlapping_type_args) {
+      // Overlap found.
+      return num_type_params - num_overlapping_type_args;
+    }
+  }
+  // No overlap found.
+  return num_type_params;
+}
+
+
 intptr_t Class::NumTypeArguments() const {
   // To work properly, this call requires the super class of this class to be
   // resolved, which is checked by the type_class() call on the super type.
   // Note that calling type_class() on a MixinAppType fails.
   Isolate* isolate = Isolate::Current();
   Class& cls = Class::Handle(isolate);
-  TypeArguments& type_params = TypeArguments::Handle(isolate);
   AbstractType& sup_type = AbstractType::Handle(isolate);
   cls = raw();
   intptr_t num_type_args = 0;
-
   do {
     if (cls.IsSignatureClass()) {
       Function& signature_fun = Function::Handle(isolate);
       signature_fun ^= cls.signature_function();
       if (!signature_fun.is_static() &&
           !signature_fun.HasInstantiatedSignature()) {
         cls = signature_fun.Owner();
       }
     }
-    // Calling NumTypeParameters() on a mixin application class will setup the
+    // Calling NumOwnTypeArguments() on a mixin application class will setup the
     // type parameters if not already done.
-    if (cls.NumTypeParameters() > 0) {
-      type_params ^= cls.type_parameters();
-      num_type_args += type_params.Length();
-    }
+    num_type_args += cls.NumOwnTypeArguments();
     // Super type of Object class is null.
-    if (cls.super_type() == AbstractType::null() ||
-        cls.super_type() == isolate->object_store()->object_type()) {
+    if ((cls.super_type() == AbstractType::null()) ||
+        (cls.super_type() == isolate->object_store()->object_type())) {
       break;
     }
     sup_type = cls.super_type();
     cls = sup_type.type_class();
   } while (true);
   return num_type_args;
 }
 
 
 // More efficient than calling NumTypeArguments().
@@ skipping 1646 matching lines @@
       return false;
     }
   }
   return true;
   // Note that it is not necessary to verify at runtime that the instantiator
   // type vector is long enough, since this uninstantiated vector contains as
   // many different type parameters as it is long.
 }
 
 
+// Return true if this uninstantiated type argument vector, once instantiated
+// at runtime, is a prefix of the type argument vector of its instantiator.
 bool TypeArguments::CanShareInstantiatorTypeArguments(
       const Class& instantiator_class) const {
   ASSERT(!IsInstantiated());
+  const intptr_t num_type_args = Length();
   const intptr_t num_instantiator_type_args =
       instantiator_class.NumTypeArguments();
+  if (num_type_args > num_instantiator_type_args) {
+    // This vector cannot be a prefix of a shorter vector.
+    return false;
+  }
   const intptr_t num_instantiator_type_params =
       instantiator_class.NumTypeParameters();
-  const intptr_t num_super_instantiator_type_args =
+  const intptr_t first_type_param_offset =
       num_instantiator_type_args - num_instantiator_type_params;
-  const intptr_t num_type_args = Length();
-  // As a first requirement in order to share the instantiator type argument
-  // vector, this type argument vector must refer to the type parameters of the
-  // instantiator class in declaration order. It does not need to contain all
-  // type parameters.
-  if (num_type_args < num_super_instantiator_type_args) {
-    return false;
-  }
+  // At compile time, the type argument vector of the instantiator consists of
+  // the type argument vector of its super type, which may refer to the type
+  // parameters of the instantiator class, followed by (or overlapping partially
+  // or fully with) the type parameters of the instantiator class in declaration
+  // order.
+  // In other words, the only variables are the type parameters of the
+  // instantiator class.
+  // This uninstantiated type argument vector is also expressed in terms of the
+  // type parameters of the instantiator class. Therefore, in order to be a
+  // prefix once instantiated at runtime, every one of its type argument must be
+  // equal to the type argument of the instantiator vector at the same index.
+
+  // As a first requirement, the last num_instantiator_type_params type
+  // arguments of this type argument vector must refer to the corresponding type
+  // parameters of the instantiator class.
   AbstractType& type_arg = AbstractType::Handle();
-  for (intptr_t i = num_super_instantiator_type_args; i < num_type_args; i++) {
+  for (intptr_t i = first_type_param_offset; i < num_type_args; i++) {
     type_arg = TypeAt(i);
     if (!type_arg.IsTypeParameter()) {
       return false;
     }
     const TypeParameter& type_param = TypeParameter::Cast(type_arg);
     ASSERT(type_param.IsFinalized());
     if ((type_param.index() != i)) {
       return false;
     }
   }
   // As a second requirement, the type arguments corresponding to the super type
-  // must be identical.
-  if (num_super_instantiator_type_args == 0) {
+  // must be identical. Overlapping ones have already been checked starting at
+  // first_type_param_offset.
+  if (first_type_param_offset == 0) {
     return true;
   }
   AbstractType& super_type = AbstractType::Handle(
       instantiator_class.super_type());
   const AbstractTypeArguments& super_type_args = AbstractTypeArguments::Handle(
       super_type.arguments());
   if (super_type_args.IsNull()) {
     return false;
   }
   AbstractType& super_type_arg = AbstractType::Handle();
-  for (intptr_t i = 0; i < num_super_instantiator_type_args; i++) {
+  for (intptr_t i = 0;
+       (i < first_type_param_offset) && (i < num_type_args); i++) {
     type_arg = TypeAt(i);
     super_type_arg = super_type_args.TypeAt(i);
     if (!type_arg.Equals(super_type_arg)) {
       return false;
     }
   }
   return true;
 }
 
 
@@ skipping 8165 matching lines @@
 
 
 bool TypeParameter::Equals(const Instance& other) const {
   if (raw() == other.raw()) {
     return true;
   }
   if (!other.IsTypeParameter()) {
     return false;
   }
   const TypeParameter& other_type_param = TypeParameter::Cast(other);
-  ASSERT(other_type_param.IsFinalized());
   if (parameterized_class() != other_type_param.parameterized_class()) {
     return false;
   }
-  if (IsFinalized() != other_type_param.IsFinalized()) {
-    return false;
+  if (IsFinalized() == other_type_param.IsFinalized()) {
+    return index() == other_type_param.index();
   }
-  if (index() != other_type_param.index()) {
-    return false;
-  }
-  return true;
+  return String::Handle(name()).Equals(String::Handle(other_type_param.name()));

[hausner, 2013/10/11 18:00:58]

Can't you just compare raw pointers here? The names are canonicalized strings.

[regis, 2013/10/11 18:36:09]

Done.

 }
 
 
 void TypeParameter::set_parameterized_class(const Class& value) const {
   // Set value may be null.
   StorePointer(&raw_ptr()->parameterized_class_, value.raw());
 }
 
 
 void TypeParameter::set_index(intptr_t value) const {
@@ skipping 3696 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   JSONObject jsobj(stream);
 }
 
 
 }  // namespace dart