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

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/bigint_operations.h"
@@ skipping 684 matching lines @@
   array.SetAt(kInitialCanonicalTypeArgumentsSize, Smi::Handle(Smi::New(0)));
   object_store->set_canonical_type_arguments(array);
 
   // Setup type class early in the process.
   cls = Class::New<Type>();
   object_store->set_type_class(cls);
 
   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);
 
   // Pre-allocate the TwoByteString class needed by the symbol table.
   cls = Class::NewStringClass(kTwoByteStringCid);
   object_store->set_two_byte_string_class(cls);
 
   // Setup the symbol table for the symbols created in the isolate.
   Symbols::SetupSymbolTable(isolate);
@@ skipping 371 matching lines @@
   // This is done to allow bootstrapping of reading classes from the snapshot.
   cls = Class::New<Instance>(kInstanceCid);
   object_store->set_object_class(cls);
 
   cls = Class::New<Type>();
   object_store->set_type_class(cls);
 
   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);
 
   cls = Class::New<ImmutableArray>();
   object_store->set_immutable_array_class(cls);
 
   cls = Class::New<GrowableObjectArray>();
   object_store->set_growable_object_array_class(cls);
 
   cls = Class::New<Float32x4>();
@@ skipping 550 matching lines @@
     // More efficient than calling NumTypeArguments().
     return type_arguments_field_offset() != kNoTypeArguments;
   } else {
     // No need to check NumTypeArguments() if class has type parameters.
     return (NumTypeParameters() > 0) || (NumTypeArguments() > 0);
   }
 }
 
 
 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();
   }
   return sup_type.type_class();
 }
 
 
-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());
 }
 
 
 // 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();
-    // 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();
       }
     }
   }
   return TypeParameter::null();
 }
 
 
 void Class::CalculateFieldOffsets() const {
   Array& flds = Array::Handle(fields());
   const Class& super = Class::Handle(SuperClass());
@@ skipping 520 matching lines @@
         return true;
       }
     }
   }
   // Check for 'direct super type' specified in the implements clause
   // and check for transitivity at the same time.
   Array& interfaces = Array::Handle(this->interfaces());
   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();
     interface_args = interface.arguments();
     if (!interface_args.IsNull() && !interface_args.IsInstantiated()) {
       // This type class implements an interface that is parameterized with
       // generic type(s), e.g. it implements List<T>.
       // The uninstantiated type T must be instantiated using the type
       // parameters of this type before performing the type test.
       // The type arguments of this type that are referred to by the type
       // parameters of the interface are at the end of the type vector,
       // 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,
                                  interface_args,
                                  other,
                                  other_type_arguments,
                                  malformed_error)) {
       return true;
     }
   }
@@ skipping 403 matching lines @@
 }
 
 
 bool AbstractTypeArguments::IsUninstantiatedIdentity() const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return false;
 }
 
 
+bool AbstractTypeArguments::IsBounded() const {
+  // AbstractTypeArguments is an abstract class.
+  UNREACHABLE();
+  return false;
+}
+
+
 static intptr_t FinalizeHash(uword hash) {
   hash += hash << 3;
   hash ^= hash >> 11;
   hash += hash << 15;
   return hash;
 }
 
 
 intptr_t AbstractTypeArguments::Hash() const {
   if (IsNull()) return 0;
@@ skipping 71 matching lines @@
     return other_arguments.IsDynamicTypes(false, other_arguments.Length());
   }
   if (other_arguments.IsNull()) {
     return arguments.IsDynamicTypes(false, arguments.Length());
   }
   return arguments.Equals(other_arguments);
 }
 
 
 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;
 }
 
 
 bool AbstractTypeArguments::IsDynamicTypes(bool raw_instantiated,
                                            intptr_t len) const {
   ASSERT(Length() >= len);
   AbstractType& type = AbstractType::Handle();
   Class& type_class = Class::Handle();
   for (intptr_t i = 0; i < len; i++) {
     type = TypeAt(i);
     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;
     }
     type_class = type.type_class();
     if (!type_class.IsDynamicClass()) {
       return false;
     }
   }
   return true;
 }
 
 
 static RawError* FormatError(const Error& prev_error,
                              const Script& script,
                              intptr_t token_pos,
                              const char* format, ...) {
   va_list args;
   va_start(args, format);
   if (prev_error.IsNull()) {
     return Parser::FormatError(script, token_pos, "Error", format, args);
   } else {
     return Parser::FormatErrorWithAppend(prev_error, script, token_pos,
                                          "Error", format, args);
   }
 }
 
 
-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,
                                      Error* malformed_error) const {
   ASSERT(Length() >= len);
   ASSERT(!other.IsNull());
   ASSERT(other.Length() >= len);
   AbstractType& type = AbstractType::Handle();
   AbstractType& other_type = AbstractType::Handle();
   for (intptr_t i = 0; i < len; i++) {
@@ skipping 67 matching lines @@
 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()) {
       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() &&
       (instantiator_type_arguments.Length() == Length())) {
     return instantiator_type_arguments.raw();
   }
   const intptr_t num_types = Length();
   TypeArguments& instantiated_array =
       TypeArguments::Handle(TypeArguments::New(num_types, Heap::kNew));
   AbstractType& type = AbstractType::Handle();
   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);
   }
   return instantiated_array.raw();
 }
 
 
 RawTypeArguments* TypeArguments::New(intptr_t len, Heap::Space space) {
   if (len < 0 || len > kMaxElements) {
     // This should be caught before we reach here.
@@ skipping 153 matching lines @@
 }
 
 
 intptr_t InstantiatedTypeArguments::Length() const {
   return AbstractTypeArguments::Handle(
       uninstantiated_type_arguments()).Length();
 }
 
 
 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();
 }
 
 
 void InstantiatedTypeArguments::SetTypeAt(intptr_t index,
                                           const AbstractType& value) const {
   // We only replace individual argument types during resolution at compile
   // time, when no type parameters are instantiated yet.
   UNREACHABLE();
@@ skipping 777 matching lines @@
     TypeTestKind test_kind,
     intptr_t parameter_position,
     intptr_t other_parameter_position,
     const AbstractTypeArguments& type_arguments,
     const Function& other,
     const AbstractTypeArguments& other_type_arguments,
     Error* malformed_error) const {
   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;
   }
   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;
   }
   if (test_kind == kIsSubtypeOf) {
     if (!param_type.IsSubtypeOf(other_param_type, malformed_error) &&
         !other_param_type.IsSubtypeOf(param_type, malformed_error)) {
       return false;
     }
   } else {
@@ skipping 20 matching lines @@
   const intptr_t other_num_opt_named_params =
       other.NumOptionalNamedParameters();
   if ((num_fixed_params != other_num_fixed_params) ||
       (num_opt_pos_params < other_num_opt_pos_params) ||
       (num_opt_named_params < other_num_opt_named_params)) {
     return false;
   }
   // 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;
     }
     if (test_kind == kIsSubtypeOf) {
       if (!res_type.IsSubtypeOf(other_res_type, malformed_error) &&
           !other_res_type.IsSubtypeOf(res_type, malformed_error)) {
         return false;
       }
     } else {
@@ skipping 291 matching lines @@
   pieces.Add(Symbols::LParen());
   intptr_t i = 0;
   if (name_visibility == kUserVisibleName) {
     // Hide implicit parameters.
     i = NumImplicitParameters();
   }
   while (i < num_fixed_params) {
     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);
     if (i != (num_params - 1)) {
       pieces.Add(Symbols::CommaSpace());
     }
     i++;
   }
   if (num_opt_params > 0) {
     if (num_opt_pos_params > 0) {
       pieces.Add(Symbols::LBracket());
     } else {
       pieces.Add(Symbols::LBrace());
     }
     for (intptr_t i = num_fixed_params; i < num_params; i++) {
       // The parameter name of an optional positional parameter does not need
       // to be part of the signature, since it is not used.
       if (num_opt_named_params > 0) {
         name = ParameterNameAt(i);
         pieces.Add(name);
         pieces.Add(Symbols::ColonSpace());
       }
       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);
       pieces.Add(name);
       if (i != (num_params - 1)) {
         pieces.Add(Symbols::CommaSpace());
       }
     }
     if (num_opt_pos_params > 0) {
       pieces.Add(Symbols::RBracket());
     } else {
       pieces.Add(Symbols::RBrace());
     }
   }
   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);
   const Array& strings = Array::Handle(Array::MakeArray(pieces));
   return Symbols::New(String::Handle(String::ConcatAll(strings)));
 }
 
 
 bool Function::HasInstantiatedSignature() const {
   AbstractType& type = AbstractType::Handle(result_type());
@@ skipping 4395 matching lines @@
   const intptr_t num_type_arguments = cls.NumTypeArguments();
   if (num_type_arguments > 0) {
     type_arguments = GetTypeArguments();
     if (!type_arguments.IsNull() && !type_arguments.IsCanonical()) {
       type_arguments = type_arguments.Canonicalize();
       SetTypeArguments(type_arguments);
     }
     // 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() ||
            (type_arguments.Length() == num_type_arguments) ||
            (cls.IsSignatureClass() &&
             (type_arguments.Length() > num_type_arguments)));
   }
   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 = TypeParameter::Cast(other);
-    AbstractType& instantiated_other = AbstractType::Handle(
-        other_instantiator.TypeAt(other_type_param.index()));
-    if (instantiated_other.IsDynamicType() ||
-        instantiated_other.IsTypeParameter()) {
-      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;
     }
     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);
 }
 
 
 void Instance::SetNativeField(int index, intptr_t value) const {
   ASSERT(IsValidNativeIndex(index));
   Object& native_fields = Object::Handle(*NativeFieldsAddr());
   if (native_fields.IsNull()) {
@@ skipping 173 matching lines @@
 
 
 void AbstractType::set_malformed_error(const Error& value) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
 }
 
 
 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;
 }
 
 
 RawAbstractType* AbstractType::Canonicalize() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return NULL;
 }
 
 
 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();
   }
   // If the type is still being finalized, we may be reporting an error about
   // a malformed type, so proceed with caution.
   const AbstractTypeArguments& args =
       AbstractTypeArguments::Handle(arguments());
   const intptr_t num_args = args.IsNull() ? 0 : args.Length();
   String& class_name = String::Handle();
   intptr_t first_type_param_index;
@@ skipping 118 matching lines @@
   // and/or malformed parameter types, which will then be encountered here at
   // run time.
   if (IsMalformed()) {
     ASSERT(FLAG_enable_type_checks);
     if ((malformed_error != NULL) && malformed_error->IsNull()) {
       *malformed_error = this->malformed_error();
     }
     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,
                       AbstractTypeArguments::Handle(arguments()),
                       Class::Handle(other.type_class()),
                       AbstractTypeArguments::Handle(other.arguments()),
                       malformed_error);
 }
 
 
@@ skipping 190 matching lines @@
   if (raw_ptr()->type_state_ == RawType::kFinalizedUninstantiated) {
     return false;
   }
   const AbstractTypeArguments& args =
       AbstractTypeArguments::Handle(arguments());
   return args.IsNull() || args.IsInstantiated();
 }
 
 
 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() ||
          (type_arguments.Length() == cls.NumTypeArguments()));
   instantiated_type.SetIsFinalized();
   return instantiated_type.raw();
 }
 
 
 bool Type::Equals(const Instance& other) const {
   if (raw() == other.raw()) {
     return true;
   }
   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;
   }
   if (type_class() != other_type.type_class()) {
     return false;
   }
   return AbstractTypeArguments::AreEqual(
       AbstractTypeArguments::Handle(arguments()),
       AbstractTypeArguments::Handle(other_type.arguments()));
@@ skipping 145 matching lines @@
 }
 
 
 void TypeParameter::set_is_finalized() const {
   ASSERT(!IsFinalized());
   set_type_state(RawTypeParameter::kFinalizedUninstantiated);
 }
 
 
 bool TypeParameter::Equals(const Instance& other) const {
+  ASSERT(IsFinalized());
   if (raw() == other.raw()) {
     return true;
   }
   if (!other.IsTypeParameter()) {
     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;
   }
   if (index() != other_type_param.index()) {
     return false;
   }
   return true;
 }
 
 
@@ skipping 12 matching lines @@
 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 {
+    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);
 }
 
 
 RawTypeParameter* TypeParameter::New() {
   ASSERT(Isolate::Current()->object_store()->type_parameter_class() !=
          Class::null());
   RawObject* raw = Object::Allocate(TypeParameter::kClassId,
                                     TypeParameter::InstanceSize(),
@@ skipping 38 matching lines @@
   const Class& cls = Class::Handle(parameterized_class());
   const char* cls_cstr =
       cls.IsNull() ? " null" : String::Handle(cls.Name()).ToCString();
   intptr_t len = OS::SNPrint(NULL, 0, format, name_cstr, index(), cls_cstr) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, format, name_cstr, index(), cls_cstr);
   return chars;
 }
 
 
+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();
   return "Number";
 }
 
 
 const char* Integer::ToCString() const {
   // Integer is an interface. No instances of Integer should exist.
   UNREACHABLE();
@@ skipping 3438 matching lines @@
   }
   return result.raw();
 }
 
 
 const char* WeakProperty::ToCString() const {
   return "_WeakProperty";
 }
 
 }  // namespace dart