Use a trail instead of a mark bit when processing recursive types in the VM

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 1195 matching lines @@
   // Returns true if all types of this vector are finalized.
   virtual bool IsFinalized() const { return true; }
 
   // 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.
   virtual RawAbstractTypeArguments* InstantiateFrom(
       const AbstractTypeArguments& instantiator_type_arguments,
-      Error* bound_error) const;
+      Error* bound_error,
+      GrowableObjectArray* trail = NULL) const;
 
   // Do not clone InstantiatedTypeArguments or null vectors, since they are
   // considered finalized.
   virtual RawAbstractTypeArguments* CloneUnfinalized() const {
     return this->raw();
   }
 
   // Null vectors are canonical.
-  virtual RawAbstractTypeArguments* Canonicalize() const { return this->raw(); }
+  virtual RawAbstractTypeArguments* Canonicalize(
+      GrowableObjectArray* trail = NULL) const {
+    return this->raw();
+  }
 
   // The name of this type argument vector, e.g. "<T, dynamic, List<T>, Smi>".
   virtual RawString* Name() const {
     return SubvectorName(0, Length(), kInternalName);
   }
 
   // The name of this type argument vector, e.g. "<T, dynamic, List<T>, int>".
   // Names of internal classes are mapped to their public interfaces.
   virtual RawString* UserVisibleName() const {
     return SubvectorName(0, Length(), kUserVisibleName);
@@ skipping 25 matching lines @@
   // Check the 'more specific' relationship, considering only a subvector of
   // length 'len' starting at 'from_index'.
   bool IsMoreSpecificThan(const AbstractTypeArguments& other,
                           intptr_t from_index,
                           intptr_t len,
                           Error* bound_error) const {
     return TypeTest(kIsMoreSpecificThan, other, from_index, len, bound_error);
   }
 
   // Check if the vectors are equal.
-  bool Equals(const AbstractTypeArguments& other) const;
+  bool Equals(const AbstractTypeArguments& other) const {
+    return IsEquivalent(other);
+  }
+
+  bool IsEquivalent(const AbstractTypeArguments& other,
+                    GrowableObjectArray* trail = NULL) const;
 
   // UNREACHABLEs as AbstractTypeArguments is an abstract class.
   virtual intptr_t Length() const;
   virtual RawAbstractType* TypeAt(intptr_t index) const;
   virtual void SetTypeAt(intptr_t index, const AbstractType& value) const;
   virtual bool IsResolved() const;
-  virtual bool IsInstantiated() const;
+  virtual bool IsInstantiated(GrowableObjectArray* trail = NULL) const;
   virtual bool IsUninstantiatedIdentity() const;
   virtual bool CanShareInstantiatorTypeArguments(
       const Class& instantiator_class) const;
   virtual bool IsBounded() const;
 
   virtual intptr_t Hash() const;
 
  private:
   // Check if the subvector of length 'len' starting at 'from_index' of this
   // type argument vector consists solely of DynamicType.
@@ skipping 27 matching lines @@
 // A TypeArguments is an array of AbstractType.
 class TypeArguments : public AbstractTypeArguments {
  public:
   virtual intptr_t Length() const;
   virtual RawAbstractType* TypeAt(intptr_t index) const;
   static intptr_t type_at_offset(intptr_t index) {
     return OFFSET_OF(RawTypeArguments, types_) + index * kWordSize;
   }
   virtual void SetTypeAt(intptr_t index, const AbstractType& value) const;
   virtual bool IsResolved() const;
-  virtual bool IsInstantiated() const;
+  virtual bool IsInstantiated(GrowableObjectArray* trail = NULL) const;
   virtual bool IsUninstantiatedIdentity() const;
   virtual bool CanShareInstantiatorTypeArguments(
       const Class& instantiator_class) const;
   virtual bool IsFinalized() const;
   virtual bool IsBounded() const;
   virtual RawAbstractTypeArguments* CloneUnfinalized() const;
   // Canonicalize only if instantiated, otherwise returns 'this'.
-  virtual RawAbstractTypeArguments* Canonicalize() const;
+  virtual RawAbstractTypeArguments* Canonicalize(
+      GrowableObjectArray* trail = NULL) const;
 
   virtual RawAbstractTypeArguments* InstantiateFrom(
       const AbstractTypeArguments& instantiator_type_arguments,
-      Error* bound_error) const;
+      Error* bound_error,
+      GrowableObjectArray* trail = NULL) const;
 
   static const intptr_t kBytesPerElement = kWordSize;
   static const intptr_t kMaxElements = kSmiMax / kBytesPerElement;
 
   static intptr_t length_offset() {
     return OFFSET_OF(RawTypeArguments, length_);
   }
 
   static intptr_t InstanceSize() {
     ASSERT(sizeof(RawTypeArguments) == OFFSET_OF(RawTypeArguments, types_));
@@ skipping 28 matching lines @@
 // one TypeParameter object, i.e. to a type that is not known at compile time.
 // The second type argument vector is the instantiator, because each type
 // parameter with index i in the first vector can be substituted (or
 // "instantiated") with the type at index i in the second type argument vector.
 class InstantiatedTypeArguments : public AbstractTypeArguments {
  public:
   virtual intptr_t Length() const;
   virtual RawAbstractType* TypeAt(intptr_t index) const;
   virtual void SetTypeAt(intptr_t index, const AbstractType& value) const;
   virtual bool IsResolved() const { return true; }
-  virtual bool IsInstantiated() const { return true; }
+  virtual bool IsInstantiated(GrowableObjectArray* trail = NULL) const {
+    return true;
+  }
   virtual bool IsUninstantiatedIdentity() const {
     UNREACHABLE();
     return false;
   }
   virtual bool CanShareInstantiatorTypeArguments(
       const Class& instantiator_class) const {
     UNREACHABLE();
     return false;
   }
   virtual bool IsBounded() const { return false; }  // Bounds were checked.
-  virtual RawAbstractTypeArguments* Canonicalize() const;
+  virtual RawAbstractTypeArguments* Canonicalize(
+      GrowableObjectArray* trail = NULL) const;
 
   RawAbstractTypeArguments* uninstantiated_type_arguments() const {
     return raw_ptr()->uninstantiated_type_arguments_;
   }
   static intptr_t uninstantiated_type_arguments_offset() {
     return OFFSET_OF(RawInstantiatedTypeArguments,
                      uninstantiated_type_arguments_);
   }
 
   RawAbstractTypeArguments* instantiator_type_arguments() const {
@@ skipping 2670 matching lines @@
   virtual bool IsMalbounded() const;
   virtual bool IsMalformedOrMalbounded() const;
   virtual RawLanguageError* error() const;
   virtual void set_error(const LanguageError& value) const;
   virtual bool IsResolved() const;
   virtual bool HasResolvedTypeClass() const;
   virtual RawClass* type_class() const;
   virtual RawUnresolvedClass* unresolved_class() const;
   virtual RawAbstractTypeArguments* arguments() const;
   virtual intptr_t token_pos() const;
-  virtual bool IsInstantiated() const;
-  virtual bool Equals(const Instance& other) const;
+  virtual bool IsInstantiated(GrowableObjectArray* trail = NULL) const;
+  virtual bool Equals(const Instance& other) const {
+    return IsEquivalent(other);
+  }
+  virtual bool IsEquivalent(const Instance& other,
+                            GrowableObjectArray* trail = NULL) 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 AbstractTypeArguments& instantiator_type_arguments,
-      Error* bound_error) const;
+      Error* bound_error,
+      GrowableObjectArray* trail = NULL) 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;
 
   virtual RawInstance* CheckAndCanonicalize(const char** error_str) const {
     return Canonicalize();
   }
 
   // Return the canonical version of this type.
-  virtual RawAbstractType* Canonicalize() const;
+  virtual RawAbstractType* Canonicalize(
+      GrowableObjectArray* trail = NULL) const;
 
   // The name of this type, including the names of its type arguments, if any.
   virtual RawString* Name() const {
     return BuildName(kInternalName);
   }
 
   // The name of this type, including the names of its type arguments, if any.
   // Names of internal classes are mapped to their public interfaces.
   virtual RawString* UserVisibleName() const {
     return BuildName(kUserVisibleName);
@@ skipping 105 matching lines @@
   virtual RawLanguageError* error() const { return raw_ptr()->error_; }
   virtual void set_error(const LanguageError& value) const;
   virtual bool IsResolved() const;  // Class and all arguments classes resolved.
   virtual bool HasResolvedTypeClass() const;  // Own type class resolved.
   virtual RawClass* type_class() const;
   void set_type_class(const Object& value) const;
   virtual RawUnresolvedClass* unresolved_class() const;
   virtual RawAbstractTypeArguments* arguments() const;
   void set_arguments(const AbstractTypeArguments& value) const;
   virtual intptr_t token_pos() const { return raw_ptr()->token_pos_; }
-  virtual bool IsInstantiated() const;
-  virtual bool Equals(const Instance& other) const;
+  virtual bool IsInstantiated(GrowableObjectArray* trail = NULL) const;
+  virtual bool IsEquivalent(const Instance& other,
+                            GrowableObjectArray* trail = NULL) const;
   virtual RawAbstractType* InstantiateFrom(
       const AbstractTypeArguments& instantiator_type_arguments,
-      Error* malformed_error) const;
+      Error* malformed_error,
+      GrowableObjectArray* trail = NULL) const;
   virtual RawAbstractType* CloneUnfinalized() const;
-  virtual RawAbstractType* Canonicalize() const;
+  virtual RawAbstractType* Canonicalize(
+      GrowableObjectArray* trail = NULL) const;
 
   virtual intptr_t Hash() const;
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawType));
   }
 
   // The type of the literal 'null'.
   static RawType* NullType();
 
@@ skipping 84 matching lines @@
   void set_type(const AbstractType& value) const;
   virtual RawClass* type_class() const {
     return AbstractType::Handle(type()).type_class();
   }
   virtual RawAbstractTypeArguments* arguments() const {
     return AbstractType::Handle(type()).arguments();
   }
   virtual intptr_t token_pos() const {
     return AbstractType::Handle(type()).token_pos();
   }
-  virtual bool IsInstantiated() const;
-  virtual bool Equals(const Instance& other) const;
+  virtual bool IsInstantiated(GrowableObjectArray* trail = NULL) const;
+  virtual bool IsEquivalent(const Instance& other,
+                            GrowableObjectArray* trail = NULL) const;
   virtual RawAbstractType* InstantiateFrom(
       const AbstractTypeArguments& instantiator_type_arguments,
-      Error* bound_error) const;
-  virtual RawAbstractType* Canonicalize() const;
+      Error* bound_error,
+      GrowableObjectArray* trail = NULL) const;
+  virtual RawAbstractType* Canonicalize(
+      GrowableObjectArray* 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(GrowableObjectArray** 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(GrowableObjectArray** trail,
+                              const Object& buddy) const;
+
+  // Return the object associated with the receiver in the trail or
+  // Object::null() if the receiver is not contained in the trail.
+  RawObject* OnlyBuddyInTrail(GrowableObjectArray* 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(GrowableObjectArray** trail,
+                           const Object& buddy) const;
+
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawTypeRef));
   }
 
   static RawTypeRef* New(const AbstractType& type);
 
  private:
-  bool is_being_checked() const {
-    return raw_ptr()->is_being_checked_;
-  }
-  void set_is_being_checked(bool value) const;
-
   static RawTypeRef* New();
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(TypeRef, AbstractType);
   friend class Class;
 };
 
 
 // A TypeParameter represents a type parameter of a parameterized class.
 // It specifies its index (and its name for debugging purposes), as well as its
 // upper bound.
@@ skipping 26 matching lines @@
   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) const;
   virtual intptr_t token_pos() const { return raw_ptr()->token_pos_; }
-  virtual bool IsInstantiated() const { return false; }
-  virtual bool Equals(const Instance& other) const;
+  virtual bool IsInstantiated(GrowableObjectArray* trail = NULL) const {
+    return false;
+  }
+  virtual bool IsEquivalent(const Instance& other,
+                            GrowableObjectArray* trail = NULL) const;
   virtual RawAbstractType* InstantiateFrom(
       const AbstractTypeArguments& instantiator_type_arguments,
-      Error* bound_error) const;
+      Error* bound_error,
+      GrowableObjectArray* trail = NULL) const;
   virtual RawAbstractType* CloneUnfinalized() const;
-  virtual RawAbstractType* Canonicalize() const { return raw(); }
+  virtual RawAbstractType* Canonicalize(
+      GrowableObjectArray* trail = NULL) const {
+    return raw();
+  }
 
   virtual intptr_t Hash() const;
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawTypeParameter));
   }
 
   static RawTypeParameter* New(const Class& parameterized_class,
                                intptr_t index,
                                const String& name,
@@ skipping 45 matching lines @@
     return AbstractType::Handle(type()).arguments();
   }
   RawAbstractType* type() const { return raw_ptr()->type_; }
   RawAbstractType* bound() const { return raw_ptr()->bound_; }
   RawTypeParameter* type_parameter() const {
     return raw_ptr()->type_parameter_;
   }
   virtual intptr_t token_pos() const {
     return AbstractType::Handle(type()).token_pos();
   }
-  virtual bool IsInstantiated() const {
+  virtual bool IsInstantiated(GrowableObjectArray* trail = NULL) const {
     // It is not possible to encounter an instantiated bounded type with an
     // 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 Equals(const Instance& other) const;
+  virtual bool IsEquivalent(const Instance& other,
+                            GrowableObjectArray* trail = NULL) const;
   virtual RawAbstractType* InstantiateFrom(
       const AbstractTypeArguments& instantiator_type_arguments,
-      Error* bound_error) const;
+      Error* bound_error,
+      GrowableObjectArray* trail = NULL) const;
   virtual RawAbstractType* CloneUnfinalized() const;
-  virtual RawAbstractType* Canonicalize() const { return raw(); }
+  virtual RawAbstractType* Canonicalize(
+      GrowableObjectArray* trail = NULL) const {
+    return raw();
+  }
 
   virtual intptr_t Hash() const;
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawBoundedType));
   }
 
   static RawBoundedType* New(const AbstractType& type,
                              const AbstractType& bound,
                              const TypeParameter& type_parameter);
 
  private:
   void set_type(const AbstractType& value) const;
   void set_bound(const AbstractType& value) const;
   void set_type_parameter(const TypeParameter& value) const;
 
-  bool is_being_checked() const {
-    return raw_ptr()->is_being_checked_;
-  }
-  void set_is_being_checked(bool value) const;
-
   static RawBoundedType* New();
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(BoundedType, AbstractType);
   friend class Class;
 };
 
 
 // A MixinAppType represents a parsed mixin application clause, e.g.
 // "S<T> with M<U>, N<V>".
 // MixinAppType objects do not survive finalization, so they do not
@@ skipping 2053 matching lines @@
 
 
 RawObject* MegamorphicCache::GetTargetFunction(const Array& array,
                                                intptr_t index) {
   return array.At((index * kEntryLength) + kTargetFunctionIndex);
 }
 
 }  // namespace dart
 
 #endif  // VM_OBJECT_H_