Complete implementation of bounds checking in the vm, by introducing a vm object

runtime/vm/object.cc

Index: runtime/vm/object.cc
===================================================================
--- runtime/vm/object.cc	(revision 19513)
+++ runtime/vm/object.cc	(working copy)
@@ -702,6 +702,9 @@
   cls = Class::New<TypeParameter>();
   object_store->set_type_parameter_class(cls);
 
+  cls = Class::New<BoundedType>();
+  object_store->set_bounded_type_class(cls);
+
   // Pre-allocate the OneByteString class needed by the symbol table.
   cls = Class::NewStringClass(kOneByteStringCid);
   object_store->set_one_byte_string_class(cls);
@@ -1093,6 +1096,9 @@
   cls = Class::New<TypeParameter>();
   object_store->set_type_parameter_class(cls);
 
+  cls = Class::New<BoundedType>();
+  object_store->set_bounded_type_class(cls);
+
   cls = Class::New<Array>();
   object_store->set_array_class(cls);
 
@@ -1663,7 +1669,7 @@
 
 
 RawClass* Class::SuperClass() const {
-  const Type& sup_type = Type::Handle(super_type());
+  const AbstractType& sup_type = AbstractType::Handle(super_type());
   if (sup_type.IsNull()) {
     return Class::null();
   }
@@ -1671,7 +1677,8 @@
 }
 
 
-void Class::set_super_type(const Type& value) const {
+void Class::set_super_type(const AbstractType& value) const {
+  ASSERT(value.IsNull() || value.IsType() || value.IsBoundedType());
   StorePointer(&raw_ptr()->super_type_, value.raw());
 }
 
@@ -1686,24 +1693,11 @@
     intptr_t num_type_params = type_params.Length();
     TypeParameter& type_param = TypeParameter::Handle();
     String& type_param_name = String::Handle();
-    // TODO(regis): We do not copy the bound (= type_param.bound()), since
-    // we are not able to finalize the bounds of type parameter references
-    // without getting into cycles. Revisit.
-    const AbstractType& bound = AbstractType::Handle(
-        Isolate::Current()->object_store()->object_type());
     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();
-        // 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);
-        }
-        return TypeParameter::New(*this, index, type_name, bound, token_pos);
+        return type_param.raw();
       }
     }
   }
@@ -2244,6 +2238,7 @@
   AbstractType& interface = AbstractType::Handle();
   Class& interface_class = Class::Handle();
   AbstractTypeArguments& interface_args = AbstractTypeArguments::Handle();
+  Error& args_malformed_error = Error::Handle();
   for (intptr_t i = 0; i < interfaces.Length(); i++) {
     interface ^= interfaces.At(i);
     interface_class = interface.type_class();
@@ -2258,19 +2253,15 @@
       // after the type arguments of the super type of this type.
       // The index of the type parameters is adjusted upon finalization.
       ASSERT(interface.IsFinalized());
-      interface_args = interface_args.InstantiateFrom(type_arguments);
-      // In checked mode, verify that the instantiated interface type
-      // arguments are within the bounds specified by the interface class.
-      // Note that the additional bounds check in checked mode may lead to a
-      // dynamic type error, but it will never change the result of the type
-      // check from true in production mode to false in checked mode.
-      if (FLAG_enable_type_checks && !interface_args.IsNull()) {
-        // Pass type_arguments as bounds instantiator.
-        if (!interface_args.IsWithinBoundsOf(interface_class,
-                                             type_arguments,
-                                             malformed_error)) {
-          continue;
+      args_malformed_error = Error::null();
+      interface_args = interface_args.InstantiateFrom(type_arguments,
+                                                      &args_malformed_error);
+      if (!args_malformed_error.IsNull()) {
+        // Return the first malformed error to the caller if it requests it.
+        if ((malformed_error != NULL) && malformed_error->IsNull()) {
+          *malformed_error = args_malformed_error.raw();
         }
+        continue;  // Another interface may work better.
       }
     }
     if (interface_class.TypeTest(test_kind,
@@ -2694,6 +2685,13 @@
 }
 
 
+bool AbstractTypeArguments::IsBounded() const {
+  // AbstractTypeArguments is an abstract class.
+  UNREACHABLE();
+  return false;
+}
+
+
 static intptr_t FinalizeHash(uword hash) {
   hash += hash << 3;
   hash ^= hash >> 11;
@@ -2785,7 +2783,8 @@
 
 
 RawAbstractTypeArguments* AbstractTypeArguments::InstantiateFrom(
-    const AbstractTypeArguments& instantiator_type_arguments) const {
+    const AbstractTypeArguments& instantiator_type_arguments,
+    Error* malformed_error) const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return NULL;
@@ -2802,10 +2801,12 @@
     ASSERT(!type.IsNull());
     if (!type.HasResolvedTypeClass()) {
       if (raw_instantiated && type.IsTypeParameter()) {
-        // An uninstantiated type parameter is equivalent to dynamic.
+        // An uninstantiated type parameter is equivalent to dynamic (even in
+        // the presence of a malformed bound in checked mode).
         continue;
       }
       ASSERT((!raw_instantiated && type.IsTypeParameter()) ||
+             type.IsBoundedType() ||
              type.IsMalformed());
       return false;
     }
@@ -2833,69 +2834,6 @@
 }
 
 
-bool AbstractTypeArguments::IsWithinBoundsOf(
-    const Class& cls,
-    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& this_type_arg = AbstractType::Handle();
-  AbstractType& cls_type_arg = AbstractType::Handle();
-  AbstractType& 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));
-  for (intptr_t i = 0; i < num_type_params; i++) {
-    cls_type_arg = cls_type_params.TypeAt(i);
-    const TypeParameter& cls_type_param = TypeParameter::Cast(cls_type_arg);
-    bound = cls_type_param.bound();
-    if (!bound.IsDynamicType()) {
-      this_type_arg = 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() ||
-          !this_type_arg.IsSubtypeOf(bound, malformed_error)) {
-        // Ignore this bound error if another malformed error was already
-        // reported for this type test.
-        if ((malformed_error != NULL) && malformed_error->IsNull()) {
-          const String& type_arg_name =
-              String::Handle(this_type_arg.UserVisibleName());
-          const String& class_name = String::Handle(cls.Name());
-          const String& bound_name = String::Handle(bound.UserVisibleName());
-          const Script& script = Script::Handle(cls.script());
-          // Since the bound was canonicalized, its token index was lost,
-          // therefore, use the token index of the corresponding type parameter.
-          *malformed_error ^= FormatError(malformed_bound_error,
-                                          script, cls_type_param.token_pos(),
-                                          "type argument '%s' does not "
-                                          "extend bound '%s' of '%s'\n",
-                                          type_arg_name.ToCString(),
-                                          bound_name.ToCString(),
-                                          class_name.ToCString());
-        }
-        return false;
-      }
-    }
-  }
-  const Class& super_class = Class::Handle(cls.SuperClass());
-  if (!super_class.IsNull() &&
-      !IsWithinBoundsOf(super_class, bounds_instantiator, malformed_error)) {
-    return false;
-  }
-  return true;
-}
-
-
 bool AbstractTypeArguments::TypeTest(TypeTestKind test_kind,
                                      const AbstractTypeArguments& other,
                                      intptr_t len,
@@ -2983,16 +2921,53 @@
       return false;
     }
     const TypeParameter& type_param = TypeParameter::Cast(type);
+    ASSERT(type_param.IsFinalized());
     if ((type_param.index() != i)) {
       return false;
     }
+    // If this type parameter specifies an upper bound, then the type argument
+    // vector does not really represent the identity vector. It cannot be
+    // substituted by the instantiator's type argument vector without checking
+    // the upper bound.
+    const AbstractType& bound = AbstractType::Handle(type_param.bound());
+    ASSERT(bound.IsFinalized());
+    if (!bound.IsObjectType() && !bound.IsDynamicType()) {
+      return false;
+    }
   }
   return true;
 }
 
 
+bool TypeArguments::IsBounded() const {
+  AbstractType& type = AbstractType::Handle();
+  intptr_t num_types = Length();
+  for (intptr_t i = 0; i < num_types; i++) {
+    type = TypeAt(i);
+    if (type.IsBoundedType()) {
+      return true;
+    }
+    if (type.IsTypeParameter()) {
+      const AbstractType& bound = AbstractType::Handle(
+          TypeParameter::Cast(type).bound());
+      if (!bound.IsObjectType() && !bound.IsDynamicType()) {
+        return true;
+      }
+      continue;
+    }
+    const AbstractTypeArguments& type_args = AbstractTypeArguments::Handle(
+        Type::Cast(type).arguments());
+    if (!type_args.IsNull() && type_args.IsBounded()) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
 RawAbstractTypeArguments* TypeArguments::InstantiateFrom(
-    const AbstractTypeArguments& instantiator_type_arguments) const {
+    const AbstractTypeArguments& instantiator_type_arguments,
+    Error* malformed_error) const {
   ASSERT(!IsInstantiated());
   if (!instantiator_type_arguments.IsNull() &&
       IsUninstantiatedIdentity() &&
@@ -3006,7 +2981,7 @@
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     if (!type.IsInstantiated()) {
-      type = type.InstantiateFrom(instantiator_type_arguments);
+      type = type.InstantiateFrom(instantiator_type_arguments, malformed_error);
     }
     instantiated_array.SetTypeAt(i, type);
   }
@@ -3180,13 +3155,18 @@
 
 
 RawAbstractType* InstantiatedTypeArguments::TypeAt(intptr_t index) const {
-  const AbstractType& type = AbstractType::Handle(
-      AbstractTypeArguments::Handle(
-          uninstantiated_type_arguments()).TypeAt(index));
+  AbstractType& type = AbstractType::Handle(AbstractTypeArguments::Handle(
+      uninstantiated_type_arguments()).TypeAt(index));
   if (!type.IsInstantiated()) {
     const AbstractTypeArguments& instantiator_type_args =
         AbstractTypeArguments::Handle(instantiator_type_arguments());
-    return type.InstantiateFrom(instantiator_type_args);
+    Error& malformed_error = Error::Handle();
+    type = type.InstantiateFrom(instantiator_type_args, &malformed_error);
+    // InstantiatedTypeArguments cannot include unchecked bounds.
+    // In the presence of unchecked bounds, no InstantiatedTypeArguments are
+    // allocated, but the type arguments are instantiated individually and their
+    // bounds are checked.
+    ASSERT(malformed_error.IsNull());
   }
   return type.raw();
 }
@@ -3984,7 +3964,9 @@
   AbstractType& other_param_type =
       AbstractType::Handle(other.ParameterTypeAt(other_parameter_position));
   if (!other_param_type.IsInstantiated()) {
-    other_param_type = other_param_type.InstantiateFrom(other_type_arguments);
+    other_param_type = other_param_type.InstantiateFrom(other_type_arguments,
+                                                        malformed_error);
+    ASSERT((malformed_error == NULL) || malformed_error->IsNull());
   }
   if (other_param_type.IsDynamicType()) {
     return true;
@@ -3992,7 +3974,8 @@
   AbstractType& param_type =
       AbstractType::Handle(ParameterTypeAt(parameter_position));
   if (!param_type.IsInstantiated()) {
-    param_type = param_type.InstantiateFrom(type_arguments);
+    param_type = param_type.InstantiateFrom(type_arguments, malformed_error);
+    ASSERT((malformed_error == NULL) || malformed_error->IsNull());
   }
   if (param_type.IsDynamicType()) {
     return test_kind == kIsSubtypeOf;
@@ -4033,12 +4016,15 @@
   // Check the result type.
   AbstractType& other_res_type = AbstractType::Handle(other.result_type());
   if (!other_res_type.IsInstantiated()) {
-    other_res_type = other_res_type.InstantiateFrom(other_type_arguments);
+    other_res_type = other_res_type.InstantiateFrom(other_type_arguments,
+                                                    malformed_error);
+    ASSERT((malformed_error == NULL) || malformed_error->IsNull());
   }
   if (!other_res_type.IsDynamicType() && !other_res_type.IsVoidType()) {
     AbstractType& res_type = AbstractType::Handle(result_type());
     if (!res_type.IsInstantiated()) {
-      res_type = res_type.InstantiateFrom(type_arguments);
+      res_type = res_type.InstantiateFrom(type_arguments, malformed_error);
+      ASSERT((malformed_error == NULL) || malformed_error->IsNull());
     }
     if (res_type.IsVoidType()) {
       return false;
@@ -4350,7 +4336,7 @@
     param_type = ParameterTypeAt(i);
     ASSERT(!param_type.IsNull());
     if (instantiate && !param_type.IsInstantiated()) {
-      param_type = param_type.InstantiateFrom(instantiator);
+      param_type = param_type.InstantiateFrom(instantiator, NULL);
     }
     name = param_type.BuildName(name_visibility);
     pieces.Add(name);
@@ -4375,7 +4361,7 @@
       }
       param_type = ParameterTypeAt(i);
       if (instantiate && !param_type.IsInstantiated()) {
-        param_type = param_type.InstantiateFrom(instantiator);
+        param_type = param_type.InstantiateFrom(instantiator, NULL);
       }
       ASSERT(!param_type.IsNull());
       name = param_type.BuildName(name_visibility);
@@ -4393,7 +4379,7 @@
   pieces.Add(Symbols::RParenArrow());
   AbstractType& res_type = AbstractType::Handle(result_type());
   if (instantiate && !res_type.IsInstantiated()) {
-    res_type = res_type.InstantiateFrom(instantiator);
+    res_type = res_type.InstantiateFrom(instantiator, NULL);
   }
   name = res_type.BuildName(name_visibility);
   pieces.Add(name);
@@ -8809,7 +8795,7 @@
     // Verify that the number of type arguments in the instance matches the
     // number of type arguments expected by the instance class.
     // A discrepancy is allowed for closures, which borrow the type argument
-    // vector of their instantiator, which may be of a super class of the class
+    // vector of their instantiator, which may be of a subclass of the class
     // defining the closure. Truncating the vector to the correct length on
     // instantiation is unnecessary. The vector may therefore be longer.
     ASSERT(type_arguments.IsNull() ||
@@ -8819,31 +8805,19 @@
   }
   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;
+  // Note that we may encounter a bound error in checked mode.
+  if (!other.IsInstantiated()) {
+    const AbstractType& instantiated_other = AbstractType::Handle(
+        other.InstantiateFrom(other_instantiator, malformed_error));
+    if ((malformed_error != NULL) && !malformed_error->IsNull()) {
+      ASSERT(FLAG_enable_type_checks);
+      return false;
     }
-    const TypeParameter& other_type_param = TypeParameter::Cast(other);
-    AbstractType& instantiated_other = AbstractType::Handle(
-        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() &&
-        !other_type_arguments.IsInstantiated()) {
-      other_type_arguments =
-          other_type_arguments.InstantiateFrom(other_instantiator);
-    }
   }
   return cls.IsSubtypeOf(type_arguments, other_class, other_type_arguments,
                          malformed_error);
@@ -9037,13 +9011,14 @@
 
 bool AbstractType::Equals(const Instance& other) const {
   // AbstractType is an abstract class.
-  UNREACHABLE();
-  return false;
+  ASSERT(raw() == AbstractType::null());
+  return other.IsNull();
 }
 
 
 RawAbstractType* AbstractType::InstantiateFrom(
-    const AbstractTypeArguments& instantiator_type_arguments) const {
+    const AbstractTypeArguments& instantiator_type_arguments,
+    Error* malformed_error) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return NULL;
@@ -9058,6 +9033,13 @@
 
 
 RawString* AbstractType::BuildName(NameVisibility name_visibility) const {
+  if (IsBoundedType()) {
+    // TODO(regis): Should the bound be visible in the name for debug purposes
+    // if name_visibility is kInternalName?
+    const AbstractType& type = AbstractType::Handle(
+        BoundedType::Cast(*this).type());
+    return type.BuildName(name_visibility);
+  }
   if (IsTypeParameter()) {
     return TypeParameter::Cast(*this).name();
   }
@@ -9196,42 +9178,48 @@
     return false;
   }
   if (other.IsMalformed()) {
-    ASSERT(FLAG_enable_type_checks);
+    // Note that 'other' may represent an unresolved bound that is checked at
+    // compile time, even in production mode, in which case the resulting
+    // BoundedType is ignored at run time if in production mode.
+    // Therefore, we cannot assert that we are in checked mode here.
     if ((malformed_error != NULL) && malformed_error->IsNull()) {
       *malformed_error = other.malformed_error();
     }
     return false;
   }
-  // AbstractType parameters cannot be handled by Class::TypeTest().
+  if (IsBoundedType() || other.IsBoundedType()) {
+    if (Equals(other)) {
+      return true;
+    }
+    return false;  // TODO(regis): We should return "maybe after instantiation".
+  }
+  // Type parameters cannot be handled by Class::TypeTest().
   // When comparing two uninstantiated function types, one returning type
   // parameter K, the other returning type parameter V, we cannot assume that K
-  // 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
+  // is a subtype of V, or vice versa. We only return true if K equals V, as
+  // defined by TypeParameter::Equals.
+  // 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.
+  // to run time.
+  // We may think that some cases 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
+  // a class B<T> will never require a run time bound check, even if T is
   // uninstantiated at compile time.
+  // However, this is not true, because bounds are ignored in production mode,
+  // and even if we are running in checked mode, we may generate a snapshot
+  // that will be executed in production mode.
   if (IsTypeParameter()) {
     const TypeParameter& type_param = TypeParameter::Cast(*this);
     if (other.IsTypeParameter()) {
       const TypeParameter& other_type_param = TypeParameter::Cast(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)) {
+      if (type_param.Equals(other_type_param)) {
         return true;
       }
     }
-    return false;
+    return false;  // TODO(regis): We should return "maybe after instantiation".
   }
   if (other.IsTypeParameter()) {
-    return false;
+    return false;  // TODO(regis): We should return "maybe after instantiation".
   }
   const Class& cls = Class::Handle(type_class());
   return cls.TypeTest(test_kind,
@@ -9442,14 +9430,22 @@
 
 
 RawAbstractType* Type::InstantiateFrom(
-    const AbstractTypeArguments& instantiator_type_arguments) const {
+    const AbstractTypeArguments& instantiator_type_arguments,
+    Error* malformed_error) const {
   ASSERT(IsFinalized());
   ASSERT(!IsInstantiated());
+  // Return the uninstantiated type unchanged if malformed. No copy needed.
+  if (IsMalformed()) {
+    return raw();
+  }
   AbstractTypeArguments& type_arguments =
       AbstractTypeArguments::Handle(arguments());
-  type_arguments = type_arguments.InstantiateFrom(instantiator_type_arguments);
+  type_arguments = type_arguments.InstantiateFrom(instantiator_type_arguments,
+                                                  malformed_error);
   const Class& cls = Class::Handle(type_class());
   ASSERT(cls.is_finalized());
+  // This uninstantiated type is not modified, as it can be instantiated
+  // with different instantiators.
   Type& instantiated_type = Type::Handle(
       Type::New(cls, type_arguments, token_pos()));
   ASSERT(type_arguments.IsNull() ||
@@ -9466,7 +9462,7 @@
   if (!other.IsType()) {
     return false;
   }
-  const AbstractType& other_type = AbstractType::Cast(other);
+  const Type& other_type = Type::Cast(other);
   ASSERT(IsFinalized() && other_type.IsFinalized());
   if (IsMalformed() || other_type.IsMalformed()) {
     return false;
@@ -9632,6 +9628,7 @@
 
 
 bool TypeParameter::Equals(const Instance& other) const {
+  ASSERT(IsFinalized());
   if (raw() == other.raw()) {
     return true;
   }
@@ -9639,9 +9636,7 @@
     return false;
   }
   const TypeParameter& other_type_param = TypeParameter::Cast(other);
-  if (IsFinalized() != other_type_param.IsFinalized()) {
-    return false;
-  }
+  ASSERT(other_type_param.IsFinalized());
   if (parameterized_class() != other_type_param.parameterized_class()) {
     return false;
   }
@@ -9674,20 +9669,65 @@
   StorePointer(&raw_ptr()->bound_, value.raw());
 }
 
+
 RawAbstractType* TypeParameter::InstantiateFrom(
-    const AbstractTypeArguments& instantiator_type_arguments) const {
+    const AbstractTypeArguments& instantiator_type_arguments,
+    Error* malformed_error) const {
   ASSERT(IsFinalized());
   if (instantiator_type_arguments.IsNull()) {
     return Type::DynamicType();
   }
+  // Bound checks should never appear in the instantiator type arguments.
+  ASSERT(!AbstractType::Handle(
+      instantiator_type_arguments.TypeAt(index())).IsBoundedType());
   return instantiator_type_arguments.TypeAt(index());
 }
 
 
+void TypeParameter::CheckBound(const AbstractType& bounded_type,
+                               const AbstractType& upper_bound,
+                               Error* malformed_error) const {
+  ASSERT(malformed_error->IsNull());
+  ASSERT(bounded_type.IsFinalized());
+  ASSERT(upper_bound.IsFinalized());
+  ASSERT(!bounded_type.IsMalformed());
+  if (bounded_type.IsSubtypeOf(upper_bound, malformed_error) ||
+      !malformed_error->IsNull()) {
+    return;
+  }
+  // Report the bound error.
+  const String& bounded_type_name = String::Handle(
+      bounded_type.UserVisibleName());
+  const String& upper_bound_name = String::Handle(
+      upper_bound.UserVisibleName());
+  const AbstractType& declared_bound = AbstractType::Handle(bound());
+  const String& declared_bound_name = String::Handle(
+      declared_bound.UserVisibleName());
+  const String& type_param_name = String::Handle(UserVisibleName());
+  const Class& cls = Class::Handle(parameterized_class());
+  const String& class_name = String::Handle(cls.Name());
+  const Script& script = Script::Handle(cls.script());
+  // Since the bound may have been canonicalized, its token index is
+  // meaningless, therefore use the token index of this type parameter.
+  *malformed_error = FormatError(
+      *malformed_error,
+      script,
+      token_pos(),
+      "type parameter '%s' of class '%s' must extend bound '%s', "
+      "but type argument '%s' is not a subtype of '%s'\n",
+      type_param_name.ToCString(),
+      class_name.ToCString(),
+      declared_bound_name.ToCString(),
+      bounded_type_name.ToCString(),
+      upper_bound_name.ToCString());
+}
+
+
 intptr_t TypeParameter::Hash() const {
   ASSERT(IsFinalized());
   uword result = 0;
   result += Class::Handle(parameterized_class()).id();
+  // Do not include the hash of the bound, which could lead to cycles.
   result <<= index();
   return FinalizeHash(result);
 }
@@ -9746,6 +9786,154 @@
 }
 
 
+bool BoundedType::IsMalformed() const {
+  return FLAG_enable_type_checks && AbstractType::Handle(bound()).IsMalformed();
+}
+
+
+RawError* BoundedType::malformed_error() const {
+  ASSERT(FLAG_enable_type_checks);
+  return AbstractType::Handle(bound()).malformed_error();
+}
+
+
+bool BoundedType::Equals(const Instance& other) const {
+  // BoundedType are not canonicalized, because their bound may get finalized
+  // after the BoundedType is created and initialized.
+  if (raw() == other.raw()) {
+    return true;
+  }
+  if (!other.IsBoundedType()) {
+    return false;
+  }
+  const BoundedType& other_bounded = BoundedType::Cast(other);
+  if (type_parameter() != other_bounded.type_parameter()) {
+    // Not a structural compare.
+    // Note that a deep comparison of bounds could lead to cycles.
+    return false;
+  }
+  const AbstractType& this_type = AbstractType::Handle(type());
+  const AbstractType& other_type = AbstractType::Handle(other_bounded.type());
+  if (!this_type.Equals(other_type)) {
+    return false;
+  }
+  const AbstractType& this_bound = AbstractType::Handle(bound());
+  const AbstractType& other_bound = AbstractType::Handle(other_bounded.bound());
+  return this_bound.IsFinalized() &&
+         other_bound.IsFinalized() &&
+         this_bound.Equals(other_bound);
+}
+
+
+void BoundedType::set_type(const AbstractType& value) const {
+  ASSERT(value.IsFinalized());
+  ASSERT(!value.IsMalformed());
+  StorePointer(&raw_ptr()->type_, value.raw());
+}
+
+
+void BoundedType::set_bound(const AbstractType& value) const {
+  // The bound may still be unfinalized because of legal cycles.
+  // It must be finalized before it is checked at run time, though.
+  StorePointer(&raw_ptr()->bound_, value.raw());
+}
+
+
+void BoundedType::set_type_parameter(const TypeParameter& value) const {
+  // A null type parameter is set when marking a type malformed because of a
+  // bound error at compile time.
+  ASSERT(value.IsNull() || value.IsFinalized());
+  StorePointer(&raw_ptr()->type_parameter_, value.raw());
+}
+
+
+void BoundedType::set_is_being_checked(bool value) const {
+  raw_ptr()->is_being_checked_ = value;
+}
+
+
+RawAbstractType* BoundedType::InstantiateFrom(
+    const AbstractTypeArguments& instantiator_type_arguments,
+    Error* malformed_error) const {
+  ASSERT(IsFinalized());
+  AbstractType& bounded_type = AbstractType::Handle(type());
+  if (!bounded_type.IsInstantiated()) {
+    bounded_type = bounded_type.InstantiateFrom(instantiator_type_arguments,
+                                                malformed_error);
+  }
+  if (FLAG_enable_type_checks &&
+      malformed_error->IsNull() &&
+      !is_being_checked()) {
+    // Avoid endless recursion while checking and instantiating bound.
+    set_is_being_checked(true);
+    AbstractType& upper_bound = AbstractType::Handle(bound());
+    ASSERT(!upper_bound.IsObjectType() && !upper_bound.IsDynamicType());
+    const TypeParameter& type_param = TypeParameter::Handle(type_parameter());
+    if (!upper_bound.IsInstantiated()) {
+      upper_bound = upper_bound.InstantiateFrom(instantiator_type_arguments,
+                                                malformed_error);
+    }
+    if (malformed_error->IsNull()) {
+      type_param.CheckBound(bounded_type, upper_bound, malformed_error);
+    }
+    set_is_being_checked(false);
+  }
+  return bounded_type.raw();
+}
+
+
+intptr_t BoundedType::Hash() const {
+  uword result = 0;
+  result += AbstractType::Handle(type()).Hash();
+  // Do not include the hash of the bound, which could lead to cycles.
+  TypeParameter& type_param = TypeParameter::Handle(type_parameter());
+  if (!type_param.IsNull()) {
+    result += type_param.Hash();
+  }
+return FinalizeHash(result);
+}
+
+
+RawBoundedType* BoundedType::New() {
+  ASSERT(Isolate::Current()->object_store()->bounded_type_class() !=
+         Class::null());
+  RawObject* raw = Object::Allocate(BoundedType::kClassId,
+                                    BoundedType::InstanceSize(),
+                                    Heap::kOld);
+  return reinterpret_cast<RawBoundedType*>(raw);
+}
+
+
+RawBoundedType* BoundedType::New(const AbstractType& type,
+                                 const AbstractType& bound,
+                                 const TypeParameter& type_parameter) {
+  const BoundedType& result = BoundedType::Handle(BoundedType::New());
+  result.set_type(type);
+  result.set_bound(bound);
+  result.set_type_parameter(type_parameter);
+  result.set_is_being_checked(false);
+  return result.raw();
+}
+
+
+const char* BoundedType::ToCString() const {
+  const char* format = "BoundedType: type %s; bound: %s; class: %s";
+  const char* type_cstr = String::Handle(AbstractType::Handle(
+      type()).Name()).ToCString();
+  const char* bound_cstr = String::Handle(AbstractType::Handle(
+      bound()).Name()).ToCString();
+  const Class& cls = Class::Handle(TypeParameter::Handle(
+      type_parameter()).parameterized_class());
+  const char* cls_cstr =
+      cls.IsNull() ? " null" : String::Handle(cls.Name()).ToCString();
+  intptr_t len = OS::SNPrint(
+      NULL, 0, format, type_cstr, bound_cstr, cls_cstr) + 1;
+  char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
+  OS::SNPrint(chars, len, format, type_cstr, bound_cstr, cls_cstr);
+  return chars;
+}
+
+
 const char* Number::ToCString() const {
   // Number is an interface. No instances of Number should exist.
   UNREACHABLE();