Consider upper bounds of type parameters in type checks.

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 "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/bigint_operations.h"
 #include "vm/bootstrap.h"
@@ skipping 1169 matching lines @@
 void Class::set_library(const Library& value) const {
   StorePointer(&raw_ptr()->library_, value.raw());
 }
 
 
 void Class::set_type_parameters(const TypeArguments& value) const {
   StorePointer(&raw_ptr()->type_parameters_, value.raw());
 }
 
 
-void Class::set_type_parameter_bounds(const TypeArguments& value) const {
-  StorePointer(&raw_ptr()->type_parameter_bounds_, value.raw());
-}
-
-
 intptr_t Class::NumTypeParameters() const {
   const TypeArguments& type_params = TypeArguments::Handle(type_parameters());
   if (type_params.IsNull()) {
     return 0;
   } else {
     return type_params.Length();
   }
 }
 
 
@@ skipping 80 matching lines @@
 // Return a TypeParameter if the type_name is a type parameter of this class.
 // Return null otherwise.
 RawTypeParameter* Class::LookupTypeParameter(const String& type_name,
                                              intptr_t token_pos) const {
   ASSERT(!type_name.IsNull());
   const TypeArguments& type_params = TypeArguments::Handle(type_parameters());
   if (!type_params.IsNull()) {
     intptr_t num_type_params = type_params.Length();
     TypeParameter& type_param = TypeParameter::Handle();
     String& type_param_name = String::Handle();
+    AbstractType& bound = AbstractType::Handle();
     for (intptr_t i = 0; i < num_type_params; i++) {
       type_param ^= type_params.TypeAt(i);
       type_param_name = type_param.Name();
       if (type_param_name.Equals(type_name)) {
-        intptr_t index = type_param.Index();
+        intptr_t index = type_param.index();
+        bound = type_param.bound();
         // Create a non-finalized new TypeParameter with the given token_pos.
         if (type_param.IsFinalized()) {
           // The index was adjusted during finalization. Revert.
           index -= NumTypeArguments() - num_type_params;
         } else {
-          ASSERT(type_param.Index() == i);
+          ASSERT(type_param.index() == i);
         }
-        return TypeParameter::New(*this, index, type_name, token_pos);
+        return TypeParameter::New(*this, index, type_name, bound, token_pos);
       }
     }
   }
   return TypeParameter::null();
 }
 
 
 void Class::CalculateFieldOffsets() const {
   Array& flds = Array::Handle(fields());
   const Class& super = Class::Handle(SuperClass());
@@ skipping 124 matching lines @@
 }
 
 
 RawClass* Class::NewSignatureClass(const String& name,
                                    const Function& signature_function,
                                    const Script& script) {
   ASSERT(!signature_function.IsNull());
   const Class& owner_class = Class::Handle(signature_function.owner());
   ASSERT(!owner_class.IsNull());
   TypeArguments& type_parameters = TypeArguments::Handle();
-  TypeArguments& type_parameter_bounds = TypeArguments::Handle();
   // A signature class extends class Instance and is parameterized in the same
   // way as the owner class of its non-static signature function.
   // It is not type parameterized if its signature function is static.
   if (!signature_function.is_static()) {
     if ((owner_class.NumTypeParameters() > 0) &&
         !signature_function.HasInstantiatedSignature()) {
       type_parameters = owner_class.type_parameters();
-      type_parameter_bounds = owner_class.type_parameter_bounds();
     }
   }
   const intptr_t token_pos = signature_function.token_pos();
   Class& result = Class::Handle(New<Closure>(name, script, token_pos));
   const Type& super_type = Type::Handle(Type::ObjectType());
   ASSERT(!super_type.IsNull());
   result.set_super_type(super_type);
   result.set_signature_function(signature_function);
   result.set_type_parameters(type_parameters);
-  result.set_type_parameter_bounds(type_parameter_bounds);
   result.SetFields(Array::Handle(Array::Empty()));
   result.SetFunctions(Array::Handle(Array::Empty()));
   result.set_type_arguments_instance_field_offset(
       Closure::type_arguments_offset());
   // Implements interface "Function".
   const Type& function_interface = Type::Handle(Type::FunctionInterface());
   const Array& interfaces = Array::Handle(Array::New(1, Heap::kOld));
   interfaces.SetAt(0, function_interface);
   result.set_interfaces(interfaces);
   // Unless the signature function already has a signature class, create a
@@ skipping 787 matching lines @@
 }
 
 
 bool AbstractType::Equals(const AbstractType& other) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
-bool AbstractType::IsIdentical(const AbstractType& other) const {
+bool AbstractType::IsIdentical(const AbstractType& other,
+                               bool check_type_parameter_bound) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
 RawAbstractType* AbstractType::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
@@ skipping 63 matching lines @@
         args.SubvectorName(first_type_param_index, num_type_params));
     type_name = String::Concat(class_name, args_name);
   }
   // The name is only used for type checking and debugging purposes.
   // Unless profiling data shows otherwise, it is not worth caching the name in
   // the type.
   return String::NewSymbol(type_name);
 }
 
 
-intptr_t AbstractType::Index() const {
-  // AbstractType is an abstract class.
-  UNREACHABLE();
-  return -1;
-}
-
-
 RawString* AbstractType::ClassName() const {
   if (HasResolvedTypeClass()) {
     return Class::Handle(type_class()).Name();
   } else {
     return UnresolvedClass::Handle(unresolved_class()).Name();
   }
 }
 
 
 bool AbstractType::IsBoolInterface() const {
@@ skipping 68 matching lines @@
   // is a subtype of V, or vice versa. We only return true if K == V, i.e. if
   // they have the same index (both are finalized, so their indices are
   // comparable).
   // The same rule applies When checking the upper bound of a still
   // uninstantiated type at compile time. Returning false will defer the test
   // to run time. But there are cases where it can be decided at compile time.
   // For example, with class A<K, V extends K>, new A<T, T> called from within
   // a class B<T> will never require a run time bounds check, even it T is
   // uninstantiated at compile time.
   if (IsTypeParameter()) {
+    // TODO(regis): Introduce and use TypeParameter::Cast().
+    const TypeParameter* type_param =
+        reinterpret_cast<const TypeParameter*>(this);
     if (other.IsTypeParameter()) {
-      return Index() == other.Index();
-    } else {
-      // TODO(regis): In checked mode, if the other type is the upper bound of
-      // this type parameter, then return true.
-      // We would need to keep the upper bound associated to the type parameter.
+      const TypeParameter* other_type_param =
+          reinterpret_cast<const TypeParameter*>(&other);
+      return type_param->index() == other_type_param->index();
+    } else if (FLAG_enable_type_checks) {
+      // In checked mode, if the upper bound of this type is more specific than
+      // the other type, then this type is more specific than the other type.
+      const AbstractType& type_param_bound =
+          AbstractType::Handle(type_param->bound());
+      if (type_param_bound.IsMoreSpecificThan(other, malformed_error)) {
+        return true;
+      }
     }
     return false;
   }
   if (other.IsTypeParameter()) {
     return false;
   }
   const Class& cls = Class::Handle(type_class());
   return cls.TypeTest(test_kind,
                       AbstractTypeArguments::Handle(arguments()),
                       Class::Handle(other.type_class()),
@@ skipping 205 matching lines @@
   }
   if (type_class() != other.type_class()) {
     return false;
   }
   return AbstractTypeArguments::AreEqual(
       AbstractTypeArguments::Handle(arguments()),
       AbstractTypeArguments::Handle(other.arguments()));
 }
 
 
-bool Type::IsIdentical(const AbstractType& other) const {
+bool Type::IsIdentical(const AbstractType& other,
+                       bool check_type_parameter_bounds) const {
   if (raw() == other.raw()) {
     return true;
   }
   if (!other.IsType()) {
     return false;
   }
   Type& other_type = Type::Handle();
   other_type ^= other.raw();
   // Both type classes may not be resolved yet.
   String& name = String::Handle(TypeClassName());
   String& other_name = String::Handle(other_type.TypeClassName());
   if (!name.Equals(other_name)) {
     return false;
   }
   return AbstractTypeArguments::AreIdentical(
       AbstractTypeArguments::Handle(arguments()),
-      AbstractTypeArguments::Handle(other.arguments()));
+      AbstractTypeArguments::Handle(other.arguments()),
+      false);  // Bounds are only checked at the top level.

[hausner, 2012/06/27 19:59:40]

Indentation

[regis, 2012/06/27 20:06:50]

I think the indentation is correct.

 }
 
 
 RawAbstractType* Type::Canonicalize() const {
   ASSERT(IsFinalized());
   const Class& cls = Class::Handle(type_class());
   Array& canonical_types = Array::Handle(cls.canonical_types());
   if (canonical_types.IsNull()) {
     // Types defined in the VM isolate are canonicalized via the object store.
     return this->raw();
@@ skipping 112 matching lines @@
     }
   } else {
     return "Unresolved Type";
   }
 }
 
 
 void TypeParameter::set_is_finalized() const {
   ASSERT(!IsFinalized());
   set_type_state(RawTypeParameter::kFinalizedUninstantiated);
-  // Field parameterized_class_ is not needed after finalization anymore.
-  set_parameterized_class(Class::Handle());
 }
 
 
 bool TypeParameter::Equals(const AbstractType& other) const {
   if (raw() == other.raw()) {
     return true;
   }
   if (!other.IsTypeParameter()) {
     return false;
   }
   TypeParameter& other_type_param = TypeParameter::Handle();
   other_type_param ^= other.raw();
   if (IsFinalized() != other_type_param.IsFinalized()) {
     return false;
   }
   if (parameterized_class() != other_type_param.parameterized_class()) {
     return false;
   }
-  if (Index() != other_type_param.Index()) {
+  if (index() != other_type_param.index()) {
     return false;
   }
   const String& name = String::Handle(Name());
   const String& other_type_param_name = String::Handle(other_type_param.Name());
   return name.Equals(other_type_param_name);
 }
 
 
-bool TypeParameter::IsIdentical(const AbstractType& other) const {
+bool TypeParameter::IsIdentical(const AbstractType& other,
+                                bool check_type_parameter_bound) const {
   if (raw() == other.raw()) {
     return true;
   }
   if (!other.IsTypeParameter()) {
     return false;
   }
   TypeParameter& other_type_param = TypeParameter::Handle();
   other_type_param ^= other.raw();
   // IsIdentical may be called on type parameters belonging to different
   // classes, e.g. to an interface and to its default factory class.
   // Therefore, both type parameters may have different parameterized classes
-  // and different indices. Compare the type parameter names only.
+  // and different indices. Compare the type parameter names only, and their
+  // bounds if requested.
   String& name = String::Handle(Name());
   String& other_name = String::Handle(other_type_param.Name());
-  return name.Equals(other_name);
+  if (!name.Equals(other_name)) {
+    return false;
+  }
+  if (check_type_parameter_bound) {
+    AbstractType& this_bound = AbstractType::Handle(bound());
+    AbstractType& other_bound = AbstractType::Handle(other_type_param.bound());
+    // Bounds are only checked at the top level.
+    const bool check_type_parameter_bounds = false;
+    if (!this_bound.IsIdentical(other_bound, check_type_parameter_bounds)) {
+      return false;
+    }
+  }
+  return true;
 }
 
 
 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 {
   ASSERT(value >= 0);
   raw_ptr()->index_ = value;
 }
 
 
 void TypeParameter::set_name(const String& value) const {
   ASSERT(value.IsSymbol());
   StorePointer(&raw_ptr()->name_, value.raw());
 }
 
 
+void TypeParameter::set_bound(const AbstractType& value) const {
+  StorePointer(&raw_ptr()->bound_, value.raw());
+}
+
 RawAbstractType* TypeParameter::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments) const {
   ASSERT(IsFinalized());
   if (instantiator_type_arguments.IsNull()) {
     return Type::DynamicType();
   }
-  return instantiator_type_arguments.TypeAt(Index());
+  return instantiator_type_arguments.TypeAt(index());
 }
 
 
 RawTypeParameter* TypeParameter::New() {
   const Class& type_parameter_class =
       Class::Handle(Object::type_parameter_class());
   RawObject* raw = Object::Allocate(type_parameter_class,
                                     TypeParameter::InstanceSize(),
                                     Heap::kOld);
   return reinterpret_cast<RawTypeParameter*>(raw);
 }
 
 
 RawTypeParameter* TypeParameter::New(const Class& parameterized_class,
                                      intptr_t index,
                                      const String& name,
+                                     const AbstractType& bound,
                                      intptr_t token_pos) {
   const TypeParameter& result = TypeParameter::Handle(TypeParameter::New());
   result.set_parameterized_class(parameterized_class);
   result.set_index(index);
   result.set_name(name);
+  result.set_bound(bound);
   result.set_token_pos(token_pos);
   result.raw_ptr()->type_state_ = RawTypeParameter::kAllocated;
   return result.raw();
 }
 
 
 void TypeParameter::set_token_pos(intptr_t token_pos) const {
   ASSERT(token_pos >= 0);
   raw_ptr()->token_pos_ = token_pos;
 }
 
 
 void TypeParameter::set_type_state(int8_t state) const {
   ASSERT((state == RawTypeParameter::kAllocated) ||
          (state == RawTypeParameter::kBeingFinalized) ||
          (state == RawTypeParameter::kFinalizedUninstantiated));
   raw_ptr()->type_state_ = state;
 }
 
 
 const char* TypeParameter::ToCString() const {
   const char* format = "TypeParameter: name %s; index: %d";
   const char* name_cstr = String::Handle(Name()).ToCString();
-  intptr_t len = OS::SNPrint(NULL, 0, format, name_cstr, Index()) + 1;
+  intptr_t len = OS::SNPrint(NULL, 0, format, name_cstr, index()) + 1;
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(len));
-  OS::SNPrint(chars, len, format, name_cstr, Index());
+  OS::SNPrint(chars, len, format, name_cstr, index());
   return chars;
 }
 
 
 intptr_t AbstractTypeArguments::Length() const  {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return -1;
 }
 
@@ skipping 94 matching lines @@
   }
   if (other_arguments.IsNull()) {
     return arguments.IsDynamicTypes(false, arguments.Length());
   }
   return arguments.Equals(other_arguments);
 }
 
 
 bool AbstractTypeArguments::AreIdentical(
     const AbstractTypeArguments& arguments,
-    const AbstractTypeArguments& other_arguments) {
+    const AbstractTypeArguments& other_arguments,
+    bool check_type_parameter_bounds) {
   if (arguments.raw() == other_arguments.raw()) {
     return true;
   }
   if (arguments.IsNull() || other_arguments.IsNull()) {
     return false;
   }
   intptr_t num_types = arguments.Length();
   if (num_types != other_arguments.Length()) {
     return false;
   }
   AbstractType& type = AbstractType::Handle();
   AbstractType& other_type = AbstractType::Handle();
   for (intptr_t i = 0; i < num_types; i++) {
     type ^= arguments.TypeAt(i);
     ASSERT(!type.IsNull());
     other_type ^= other_arguments.TypeAt(i);
-    if (!type.IsIdentical(other_type)) {
+    if (!type.IsIdentical(other_type, check_type_parameter_bounds)) {
       return false;
     }
   }
   return true;
 }
 
 
 RawAbstractTypeArguments* AbstractTypeArguments::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments) const {
   // AbstractTypeArguments is an abstract class.
@@ skipping 48 matching lines @@
     const AbstractTypeArguments& bounds_instantiator,
     Error* malformed_error) const {
   ASSERT(FLAG_enable_type_checks);
   // This function may be called at compile time on (partially) uninstantiated
   // type arguments and may return true, in which case a run time bounds check
   // can be avoided.
   ASSERT(Length() >= cls.NumTypeArguments());
   const intptr_t num_type_params = cls.NumTypeParameters();
   const intptr_t offset = cls.NumTypeArguments() - num_type_params;
   AbstractType& type = AbstractType::Handle();
+  TypeParameter& type_param = TypeParameter::Handle();
   AbstractType& bound = AbstractType::Handle();
-  const TypeArguments& bounds =
-      TypeArguments::Handle(cls.type_parameter_bounds());
-  ASSERT((bounds.IsNull() && (num_type_params == 0)) ||
-         (bounds.Length() == num_type_params));
+  const TypeArguments& type_params =
+      TypeArguments::Handle(cls.type_parameters());
+  ASSERT((type_params.IsNull() && (num_type_params == 0)) ||
+         (type_params.Length() == num_type_params));
   for (intptr_t i = 0; i < num_type_params; i++) {
-    bound = bounds.TypeAt(i);
+    type_param ^= type_params.TypeAt(i);
+    bound = type_param.bound();
     if (!bound.IsDynamicType()) {
       type = TypeAt(offset + i);
       Error& malformed_bound_error = Error::Handle();
       if (bound.IsMalformed()) {
         malformed_bound_error = bound.malformed_error();
       } else if (!bound.IsInstantiated()) {
         bound = bound.InstantiateFrom(bounds_instantiator);
       }
       if (!malformed_bound_error.IsNull() ||
           !type.IsSubtypeOf(bound, malformed_error)) {
@@ skipping 107 matching lines @@
   return true;
 }
 
 
 bool TypeArguments::IsUninstantiatedIdentity() const {
   ASSERT(!IsInstantiated());
   AbstractType& type = AbstractType::Handle();
   intptr_t num_types = Length();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
-    if (!type.IsTypeParameter() || (type.Index() != i)) {
+    if (!type.IsTypeParameter()) {
+      return false;
+    }
+    // TODO(regis): Introduce and use TypeParameter::Cast().
+    TypeParameter* type_param = reinterpret_cast<TypeParameter*>(&type);
+    if ((type_param->index() != i)) {
       return false;
     }
   }
   return true;
 }
 
 
 RawAbstractTypeArguments* TypeArguments::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments) const {
   ASSERT(!IsInstantiated());
@@ skipping 734 matching lines @@
         String::Handle(String::NewSymbol(" extends "));
     const String& kLAngleBracket = String::Handle(String::NewSymbol("<"));
     const String& kRAngleBracket = String::Handle(String::NewSymbol(">"));
     const Class& function_class = Class::Handle(owner());
     ASSERT(!function_class.IsNull());
     const TypeArguments& type_parameters = TypeArguments::Handle(
         function_class.type_parameters());
     if (!type_parameters.IsNull()) {
       intptr_t num_type_parameters = type_parameters.Length();
       pieces.Add(kLAngleBracket);
-      const TypeArguments& bounds = TypeArguments::Handle(
-          function_class.type_parameter_bounds());
-      AbstractType& type_parameter = AbstractType::Handle();
+      TypeParameter& type_parameter = TypeParameter::Handle();
       AbstractType& bound = AbstractType::Handle();
       for (intptr_t i = 0; i < num_type_parameters; i++) {
         type_parameter ^= type_parameters.TypeAt(i);
         name = type_parameter.Name();
         pieces.Add(name);
-        bound = bounds.TypeAt(i);
+        bound = type_parameter.bound();
         if (!bound.IsNull() && !bound.IsDynamicType()) {
           pieces.Add(kSpaceExtendsSpace);
           name = bound.Name();
           pieces.Add(name);
         }
         if (i < num_type_parameters - 1) {
           pieces.Add(kCommaSpace);
         }
       }
       pieces.Add(kRAngleBracket);
@@ skipping 3119 matching lines @@
   ASSERT(other.IsFinalized());
   ASSERT(!other.IsDynamicType());
   ASSERT(!other.IsVoidType());
   ASSERT(!other.IsMalformed());
   if (IsNull()) {
     Class& other_class = Class::Handle();
     if (other.IsTypeParameter()) {
       if (other_instantiator.IsNull()) {
         return true;  // Other type is uninstantiated, i.e. Dynamic.
       }
-      const AbstractType& instantiated_other =
-          AbstractType::Handle(other_instantiator.TypeAt(other.Index()));
+      // TODO(regis): Introduce and use TypeParameter::Cast().
+      const TypeParameter* other_type_param =
+          reinterpret_cast<const TypeParameter*>(&other);
+      const AbstractType& instantiated_other = AbstractType::Handle(
+          other_instantiator.TypeAt(other_type_param->index()));
       ASSERT(instantiated_other.IsInstantiated());
       other_class = instantiated_other.type_class();
     } else {
       other_class = other.type_class();
     }
     return other_class.IsObjectClass() || other_class.IsDynamicClass();
   }
   const Class& cls = Class::Handle(clazz());
   // We must not encounter Object::sentinel() or Object::transition_sentinel(),
   // both instances of class NullClass, but not instance Object::null().
@@ skipping 20 matching lines @@
   Class& other_class = Class::Handle();
   AbstractTypeArguments& other_type_arguments = AbstractTypeArguments::Handle();
   // In case 'other' is not instantiated, we could simply call
   // other.InstantiateFrom(other_instantiator), however, we can save the
   // allocation of a new AbstractType by inlining the code.
   if (other.IsTypeParameter()) {
     if (other_instantiator.IsNull()) {
       // An uninstantiated type parameter is equivalent to Dynamic.
       return true;
     }
+    const TypeParameter* other_type_param =
+        reinterpret_cast<const TypeParameter*>(&other);
     AbstractType& instantiated_other = AbstractType::Handle(
-        other_instantiator.TypeAt(other.Index()));
+        other_instantiator.TypeAt(other_type_param->index()));
     if (instantiated_other.IsDynamicType() ||
         instantiated_other.IsTypeParameter()) {
       return true;
     }
     other_class = instantiated_other.type_class();
     other_type_arguments = instantiated_other.arguments();
   } else {
     other_class = other.type_class();
     other_type_arguments = other.arguments();
     if (!other_type_arguments.IsNull() &&
@@ skipping 2994 matching lines @@
   const String& str = String::Handle(pattern());
   const char* format = "JSRegExp: pattern=%s flags=%s";
   intptr_t len = OS::SNPrint(NULL, 0, format, str.ToCString(), Flags());
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(len + 1));
   OS::SNPrint(chars, (len + 1), format, str.ToCString(), Flags());
   return chars;
 }
 
 }  // namespace dart