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

runtime/vm/object.h

Index: runtime/vm/object.h
===================================================================
--- runtime/vm/object.h	(revision 31270)
+++ runtime/vm/object.h	(working copy)
@@ -1201,7 +1201,8 @@
   // 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.
@@ -1210,7 +1211,10 @@
   }
 
   // Do not canonicalize InstantiatedTypeArguments or null vectors.
-  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 {
@@ -1256,14 +1260,19 @@
   }
 
   // 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;
@@ -1311,7 +1320,7 @@
   }
   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;
@@ -1319,11 +1328,13 @@
   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;
@@ -1372,7 +1383,9 @@
   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;
@@ -4069,15 +4082,20 @@
   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
@@ -4089,7 +4107,8 @@
   }
 
   // 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 {
@@ -4215,13 +4234,16 @@
   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;
 
@@ -4326,15 +4348,37 @@
   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.
+  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* BuddyInTrail(GrowableObjectArray* trail) const;
+
+  // If the trail is null, allocate a trail, add the pair <receiver, buddy> to
+  // the trail.

[siva, 2013/12/20 19:35:10]

Comment does not indicate what happens if the receiver already exists in the
trail (should state that it does not expect a receiver with a buddy in the
trail)

[regis, 2014/01/07 20:26:27]

I added a comment and renamed the call to AddOnlyBuddyToTrail.

+  void AddBuddyToTrail(GrowableObjectArray** trail, const Object& buddy) const;
+
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawTypeRef));
   }
@@ -4342,11 +4386,6 @@
   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);
@@ -4393,13 +4432,20 @@
                   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;
 
@@ -4465,19 +4511,24 @@
   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;
 
@@ -4494,11 +4545,6 @@
   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);