Keep a trail while checking upper bounds in the VM in order to properly handle

runtime/vm/object.h

 // 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.
 
 #ifndef VM_OBJECT_H_
 #define VM_OBJECT_H_
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "platform/utils.h"
@@ skipping 883 matching lines @@
     return ZoneHandle(zone, Object::null());
   }
 
  private:
   PassiveObject() : Object() {}
   DISALLOW_ALLOCATION();
   DISALLOW_COPY_AND_ASSIGN(PassiveObject);
 };
 
 
+typedef ZoneGrowableHandlePtrArray<const AbstractType> Trail;
+typedef ZoneGrowableHandlePtrArray<const AbstractType>* TrailPtr;
+
+
 class Class : public Object {
  public:
   intptr_t instance_size() const {
     ASSERT(is_finalized() || is_prefinalized());
     return (raw_ptr()->instance_size_in_words_ * kWordSize);
   }
   void set_instance_size(intptr_t value_in_bytes) const {
     ASSERT(kWordSize != 0);
     set_instance_size_in_words(value_in_bytes / kWordSize);
   }
@@ skipping 201 matching lines @@
   static bool IsInFullSnapshot(RawClass* cls) {
     NoSafepointScope no_safepoint;
     return cls->ptr()->library_->ptr()->is_in_fullsnapshot_;
   }
 
   // Check the subtype relationship.
   bool IsSubtypeOf(const TypeArguments& type_arguments,
                    const Class& other,
                    const TypeArguments& other_type_arguments,
                    Error* bound_error,
+                   TrailPtr bound_trail = NULL,
                    Heap::Space space = Heap::kNew) const {
     return TypeTest(kIsSubtypeOf,
                     type_arguments,
                     other,
                     other_type_arguments,
                     bound_error,
+                    bound_trail,
                     space);
   }
 
   // Check the 'more specific' relationship.
   bool IsMoreSpecificThan(const TypeArguments& type_arguments,
                           const Class& other,
                           const TypeArguments& other_type_arguments,
                           Error* bound_error,
+                          TrailPtr bound_trail = NULL,
                           Heap::Space space = Heap::kNew) const {
     return TypeTest(kIsMoreSpecificThan,
                     type_arguments,
                     other,
                     other_type_arguments,
                     bound_error,
+                    bound_trail,
                     space);
   }
 
   // Check if this is the top level class.
   bool IsTopLevel() const;
 
   bool IsPrivate() const;
 
   RawArray* fields() const { return raw_ptr()->fields_; }
   void SetFields(const Array& value) const;
@@ skipping 302 matching lines @@
 
   // Allocate an instance class which has a VM implementation.
   template <class FakeInstance> static RawClass* New(intptr_t id);
 
   // Check the subtype or 'more specific' relationship.
   bool TypeTest(TypeTestKind test_kind,
                 const TypeArguments& type_arguments,
                 const Class& other,
                 const TypeArguments& other_type_arguments,
                 Error* bound_error,
+                TrailPtr bound_trail,
                 Heap::Space space) const;
 
   static bool TypeTestNonRecursive(
       const Class& cls,
       TypeTestKind test_kind,
       const TypeArguments& type_arguments,
       const Class& other,
       const TypeArguments& other_type_arguments,
       Error* bound_error,
+      TrailPtr bound_trail,
       Heap::Space space);
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(Class, Object);
   friend class AbstractType;
   friend class Instance;
   friend class Object;
   friend class Type;
   friend class FunctionType;
   friend class Intrinsifier;
   friend class Precompiler;
@@ skipping 25 matching lines @@
   void set_ident(const String& ident) const;
   void set_token_pos(TokenPosition token_pos) const;
 
   static RawUnresolvedClass* New();
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(UnresolvedClass, Object);
   friend class Class;
 };
 
 
-typedef ZoneGrowableHandlePtrArray<const AbstractType> Trail;
-typedef ZoneGrowableHandlePtrArray<const AbstractType>* TrailPtr;
-
 // A TypeArguments is an array of AbstractType.
 class TypeArguments : public Object {
  public:
   intptr_t Length() const;
   RawAbstractType* TypeAt(intptr_t index) const;
   static intptr_t type_at_offset(intptr_t index) {
     return OFFSET_OF_RETURNED_VALUE(
         RawTypeArguments, types) + index * kWordSize;
   }
   void SetTypeAt(intptr_t index, const AbstractType& value) const;
@@ skipping 28 matching lines @@
   bool IsRawInstantiatedRaw(intptr_t len) const {
     return IsDynamicTypes(true, 0, len);
   }
 
   // Check the subtype relationship, considering only a subvector of length
   // 'len' starting at 'from_index'.
   bool IsSubtypeOf(const TypeArguments& other,
                    intptr_t from_index,
                    intptr_t len,
                    Error* bound_error,
+                   TrailPtr bound_trail = NULL,
                    Heap::Space space = Heap::kNew) const {
-    return TypeTest(kIsSubtypeOf, other, from_index, len, bound_error, space);
+    return TypeTest(kIsSubtypeOf, other, from_index, len,
+                    bound_error, bound_trail, space);
   }
 
   // Check the 'more specific' relationship, considering only a subvector of
   // length 'len' starting at 'from_index'.
   bool IsMoreSpecificThan(const TypeArguments& other,
                           intptr_t from_index,
                           intptr_t len,
                           Error* bound_error,
+                          TrailPtr bound_trail = NULL,
                           Heap::Space space = Heap::kNew) const {
-    return TypeTest(kIsMoreSpecificThan,
-        other, from_index, len, bound_error, space);
+    return TypeTest(kIsMoreSpecificThan, other, from_index, len,
+                    bound_error, bound_trail, space);
   }
 
   // Check if the vectors are equal (they may be null).
   bool Equals(const TypeArguments& other) const {
     return IsSubvectorEquivalent(other, 0, IsNull() ? 0 : Length());
   }
 
   bool IsEquivalent(const TypeArguments& other, TrailPtr trail = NULL) const {
     return IsSubvectorEquivalent(other, 0, IsNull() ? 0 : Length(), trail);
   }
@@ skipping 35 matching lines @@
   RawTypeArguments* Canonicalize(TrailPtr trail = NULL) const;
 
   // Return 'this' if this type argument vector is instantiated, i.e. if it does
   // not refer to type parameters. Otherwise, return a new type argument vector
   // where each reference to a type parameter is replaced with the corresponding
   // type of the instantiator type argument vector.
   // If bound_error is not NULL, it may be set to reflect a bound error.
   RawTypeArguments* InstantiateFrom(
       const TypeArguments& instantiator_type_arguments,
       Error* bound_error,
-      TrailPtr trail = NULL,
+      TrailPtr instantiation_trail = NULL,
+      TrailPtr bound_trail = NULL,
       Heap::Space space = Heap::kNew) const;
 
   // Runtime instantiation with canonicalization. Not to be used during type
   // finalization at compile time.
   RawTypeArguments* InstantiateAndCanonicalizeFrom(
       const TypeArguments& instantiator_type_arguments,
       Error* bound_error) const;
 
   // Return true if this type argument vector has cached instantiations.
   bool HasInstantiations() const;
@@ skipping 36 matching lines @@
                       intptr_t from_index,
                       intptr_t len) const;
 
   // Check the subtype or 'more specific' relationship, considering only a
   // subvector of length 'len' starting at 'from_index'.
   bool TypeTest(TypeTestKind test_kind,
                 const TypeArguments& other,
                 intptr_t from_index,
                 intptr_t len,
                 Error* bound_error,
+                TrailPtr bound_trail,
                 Heap::Space space) const;
 
   // Return the internal or public name of a subvector of this type argument
   // vector, e.g. "<T, dynamic, List<T>, int>".
   RawString* SubvectorName(intptr_t from_index,
                            intptr_t len,
                            NameVisibility name_visibility) const;
 
   RawArray* instantiations() const;
   void set_instantiations(const Array& value) const;
@@ skipping 784 matching lines @@
                     bound_error,
                     space);
   }
 
   // Returns true if the type of this function is more specific than the type of
   // the other function.
   bool IsMoreSpecificThan(const TypeArguments& type_arguments,
                           const Function& other,
                           const TypeArguments& other_type_arguments,
                           Error* bound_error,
-                   Heap::Space space = Heap::kNew) const {
+                          Heap::Space space = Heap::kNew) const {
     return TypeTest(kIsMoreSpecificThan,
                     type_arguments,
                     other,
                     other_type_arguments,
                     bound_error,
                     space);
   }
 
   // Check the subtype or 'more specific' relationship.
   bool TypeTest(TypeTestKind test_kind,
@@ skipping 2747 matching lines @@
   }
   virtual bool IsEquivalent(const Instance& other, TrailPtr trail = NULL) const;
   virtual bool IsRecursive() const;
 
   // Instantiate this type using the given type argument vector.
   // Return a new type, or return 'this' if it is already instantiated.
   // If bound_error is not NULL, it may be set to reflect a bound error.
   virtual RawAbstractType* InstantiateFrom(
       const TypeArguments& instantiator_type_arguments,
       Error* bound_error,
-      TrailPtr trail = NULL,
+      TrailPtr instantiation_trail = NULL,
+      TrailPtr bound_trail = NULL,
       Heap::Space space = Heap::kNew) const;
 
   // Return a clone of this unfinalized type or the type itself if it is
   // already finalized. Apply recursively to type arguments, i.e. finalized
   // type arguments of an unfinalized type are not cloned, but shared.
   virtual RawAbstractType* CloneUnfinalized() const;
 
   // Return a clone of this uninstantiated type where all references to type
   // parameters are replaced with references to type parameters of the same name
   // but belonging to the new owner class.
@@ skipping 10 matching lines @@
   virtual RawAbstractType* Canonicalize(TrailPtr trail = NULL) const;
 
   // Return the object associated with the receiver in the trail or
   // AbstractType::null() if the receiver is not contained in the trail.
   RawAbstractType* OnlyBuddyInTrail(TrailPtr trail) const;
 
   // If the trail is null, allocate a trail, add the pair <receiver, buddy> to
   // the trail. The receiver may only be added once with its only buddy.
   void AddOnlyBuddyToTrail(TrailPtr* trail, const AbstractType& buddy) const;
 
+  // Return true if the receiver is contained in the trail.
+  // Otherwise, if the trail is null, allocate a trail, then add the receiver to
+  // the trail and return false.
+  bool TestAndAddToTrail(TrailPtr* trail) const;
+
+  // Return true if the pair <receiver, buddy> is contained in the trail.
+  // Otherwise, if the trail is null, allocate a trail, add the pair <receiver,
+  // buddy> to the trail and return false.
+  // The receiver may be added several times, each time with a different buddy.
+  bool TestAndAddBuddyToTrail(TrailPtr* trail, const AbstractType& buddy) const;
+
   // The name of this type, including the names of its type arguments, if any.
   virtual RawString* Name() const {
     return BuildName(kInternalName);
   }
 
   virtual RawString* PrettyName() const {
     return BuildName(kPrettyName);
   }
 
   // The name of this type, including the names of its type arguments, if any.
@@ skipping 52 matching lines @@
 
   // Check if this type represents the 'String' type.
   bool IsStringType() const;
 
   // Check if this type represents the Dart 'Function' type.
   bool IsDartFunctionType() const;
 
   // Check the subtype relationship.
   bool IsSubtypeOf(const AbstractType& other,
                    Error* bound_error,
+                   TrailPtr bound_trail = NULL,
                    Heap::Space space = Heap::kNew) const {
-    return TypeTest(kIsSubtypeOf, other, bound_error, space);
+    return TypeTest(kIsSubtypeOf, other, bound_error, bound_trail, space);
   }
 
   // Check the 'more specific' relationship.
   bool IsMoreSpecificThan(const AbstractType& other,
                           Error* bound_error,
+                          TrailPtr bound_trail = NULL,
                           Heap::Space space = Heap::kNew) const {
-    return TypeTest(kIsMoreSpecificThan, other, bound_error, space);
+    return TypeTest(kIsMoreSpecificThan, other,
+                    bound_error, bound_trail, space);
   }
 
  private:
   // Check the subtype or 'more specific' relationship.
   bool TypeTest(TypeTestKind test_kind,
                 const AbstractType& other,
                 Error* bound_error,
+                TrailPtr bound_trail,
                 Heap::Space space) const;
 
   // Return the internal or public name of this type, including the names of its
   // type arguments, if any.
   RawString* BuildName(NameVisibility visibility) const;
 
  protected:
   HEAP_OBJECT_IMPLEMENTATION(AbstractType, Instance);
   friend class Class;
   friend class Function;
@@ skipping 38 matching lines @@
   virtual RawUnresolvedClass* unresolved_class() const;
   virtual RawTypeArguments* arguments() const { return raw_ptr()->arguments_; }
   virtual void set_arguments(const TypeArguments& value) const;
   virtual TokenPosition token_pos() const { return raw_ptr()->token_pos_; }
   virtual bool IsInstantiated(TrailPtr trail = NULL) const;
   virtual bool IsEquivalent(const Instance& other, TrailPtr trail = NULL) const;
   virtual bool IsRecursive() const;
   virtual RawAbstractType* InstantiateFrom(
       const TypeArguments& instantiator_type_arguments,
       Error* bound_error,
-      TrailPtr trail = NULL,
+      TrailPtr instantiation_trail = NULL,
+      TrailPtr bound_trail = NULL,
       Heap::Space space = Heap::kNew) const;
   virtual RawAbstractType* CloneUnfinalized() const;
   virtual RawAbstractType* CloneUninstantiated(
       const Class& new_owner,
       TrailPtr trail = NULL) const;
   virtual RawAbstractType* Canonicalize(TrailPtr trail = NULL) const;
 
   virtual intptr_t Hash() const;
 
   static intptr_t InstanceSize() {
@@ skipping 126 matching lines @@
   virtual RawTypeArguments* arguments() const { return raw_ptr()->arguments_; }
   virtual void set_arguments(const TypeArguments& value) const;
   RawFunction* signature() const { return raw_ptr()->signature_; }
   virtual TokenPosition token_pos() const { return raw_ptr()->token_pos_; }
   virtual bool IsInstantiated(TrailPtr trail = NULL) const;
   virtual bool IsEquivalent(const Instance& other, TrailPtr trail = NULL) const;
   virtual bool IsRecursive() const;
   virtual RawAbstractType* InstantiateFrom(
       const TypeArguments& instantiator_type_arguments,
       Error* malformed_error,
-      TrailPtr trail = NULL,
+      TrailPtr instantiation_trail = NULL,
+      TrailPtr bound_trail = NULL,
       Heap::Space space = Heap::kNew) const;
   virtual RawAbstractType* CloneUnfinalized() const;
   virtual RawAbstractType* CloneUninstantiated(
       const Class& new_owner,
       TrailPtr trail = NULL) const;
   virtual RawAbstractType* Canonicalize(TrailPtr trail = NULL) const;
 
   virtual intptr_t Hash() const;
 
   static intptr_t InstanceSize() {
@@ skipping 55 matching lines @@
   virtual TokenPosition token_pos() const {
     return AbstractType::Handle(type()).token_pos();
   }
   virtual bool IsInstantiated(TrailPtr trail = NULL) const;
   virtual bool IsEquivalent(const Instance& other,
                             TrailPtr trail = NULL) const;
   virtual bool IsRecursive() const { return true; }
   virtual RawTypeRef* InstantiateFrom(
       const TypeArguments& instantiator_type_arguments,
       Error* bound_error,
-      TrailPtr trail = NULL,
+      TrailPtr instantiation_trail = NULL,
+      TrailPtr bound_trail = NULL,
       Heap::Space space = Heap::kNew) const;
   virtual RawTypeRef* CloneUninstantiated(
       const Class& new_owner,
       TrailPtr trail = NULL) const;
   virtual RawAbstractType* Canonicalize(TrailPtr trail = NULL) const;
 
   virtual intptr_t Hash() const;
 
-  // Return true if the receiver is contained in the trail.
-  // Otherwise, if the trail is null, allocate a trail, then add the receiver to
-  // the trail and return false.
-  bool TestAndAddToTrail(TrailPtr* trail) const;
-
-  // Return true if the pair <receiver, buddy> is contained in the trail.
-  // Otherwise, if the trail is null, allocate a trail, add the pair <receiver,
-  // buddy> to the trail and return false.
-  // The receiver may be added several times, each time with a different buddy.
-  bool TestAndAddBuddyToTrail(TrailPtr* trail, const AbstractType& buddy) const;
-
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawTypeRef));
   }
 
   static RawTypeRef* New(const AbstractType& type);
 
  private:
   static RawTypeRef* New();
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(TypeRef, AbstractType);
@@ skipping 32 matching lines @@
   void set_index(intptr_t value) const;
   RawAbstractType* bound() const { return raw_ptr()->bound_; }
   void set_bound(const AbstractType& value) const;
   // Returns true if bounded_type is below upper_bound, otherwise return false
   // and set bound_error if both bounded_type and upper_bound are instantiated.
   // If one or both are not instantiated, returning false only means that the
   // bound cannot be checked yet and this is not an error.
   bool CheckBound(const AbstractType& bounded_type,
                   const AbstractType& upper_bound,
                   Error* bound_error,
+                  TrailPtr bound_trail = NULL,
                   Heap::Space space = Heap::kNew) const;
   virtual TokenPosition token_pos() const { return raw_ptr()->token_pos_; }
   virtual bool IsInstantiated(TrailPtr trail = NULL) const {
     return false;
   }
   virtual bool IsEquivalent(const Instance& other, TrailPtr trail = NULL) const;
   virtual bool IsRecursive() const { return false; }
   virtual RawAbstractType* InstantiateFrom(
       const TypeArguments& instantiator_type_arguments,
       Error* bound_error,
-      TrailPtr trail = NULL,
+      TrailPtr instantiation_trail = NULL,
+      TrailPtr bound_trail = NULL,
       Heap::Space space = Heap::kNew) const;
   virtual RawAbstractType* CloneUnfinalized() const;
   virtual RawAbstractType* CloneUninstantiated(
       const Class& new_owner, TrailPtr trail = NULL) const;
   virtual RawAbstractType* Canonicalize(TrailPtr trail = NULL) const {
     return raw();
   }
 
   virtual intptr_t Hash() const;
 
@@ skipping 64 matching lines @@
     // uninstantiated upper bound. Therefore, we do not need to check if the
     // bound is instantiated. Moreover, doing so could lead into cycles, as in
     // class C<T extends C<C>> { }.
     return AbstractType::Handle(type()).IsInstantiated();
   }
   virtual bool IsEquivalent(const Instance& other, TrailPtr trail = NULL) const;
   virtual bool IsRecursive() const;
   virtual RawAbstractType* InstantiateFrom(
       const TypeArguments& instantiator_type_arguments,
       Error* bound_error,
-      TrailPtr trail = NULL,
+      TrailPtr instantiation_trail = NULL,
+      TrailPtr bound_trail = NULL,
       Heap::Space space = Heap::kNew) const;
   virtual RawAbstractType* CloneUnfinalized() const;
   virtual RawAbstractType* CloneUninstantiated(
       const Class& new_owner, TrailPtr trail = NULL) const;
   virtual RawAbstractType* Canonicalize(TrailPtr trail = NULL) const {
     return raw();
   }
 
   virtual intptr_t Hash() const;
 
@@ skipping 2570 matching lines @@
 
 
 RawObject* MegamorphicCache::GetTargetFunction(const Array& array,
                                                intptr_t index) {
   return array.At((index * kEntryLength) + kTargetFunctionIndex);
 }
 
 }  // namespace dart
 
 #endif  // VM_OBJECT_H_