Introduce class TypeRef in the VM to fully support recursive types.

runtime/vm/object.cc

Index: runtime/vm/object.cc
===================================================================
--- runtime/vm/object.cc	(revision 31085)
+++ runtime/vm/object.cc	(working copy)
@@ -902,6 +902,9 @@
   cls = Class::New<Type>();
   object_store->set_type_class(cls);
 
+  cls = Class::New<TypeRef>();
+  object_store->set_type_ref_class(cls);
+
   cls = Class::New<TypeParameter>();
   object_store->set_type_parameter_class(cls);
 
@@ -1033,6 +1036,10 @@
   RegisterPrivateClass(cls, Symbols::Type(), core_lib);
   pending_classes.Add(cls);
 
+  cls = object_store->type_ref_class();
+  RegisterPrivateClass(cls, Symbols::TypeRef(), core_lib);
+  pending_classes.Add(cls);
+
   cls = object_store->type_parameter_class();
   RegisterPrivateClass(cls, Symbols::TypeParameter(), core_lib);
   pending_classes.Add(cls);
@@ -1290,6 +1297,9 @@
   cls = Class::New<Type>();
   object_store->set_type_class(cls);
 
+  cls = Class::New<TypeRef>();
+  object_store->set_type_ref_class(cls);
+
   cls = Class::New<TypeParameter>();
   object_store->set_type_parameter_class(cls);
 
@@ -1991,6 +2001,7 @@
 void Class::set_super_type(const AbstractType& value) const {
   ASSERT(value.IsNull() ||
          (value.IsType() && !value.IsDynamicType()) ||
+         value.IsTypeRef() ||
          value.IsBoundedType() ||
          value.IsMixinAppType());
   StorePointer(&raw_ptr()->super_type_, value.raw());
@@ -3513,9 +3524,6 @@
         // 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();
@@ -3579,8 +3587,14 @@
 
 
 void TypeArguments::SetTypeAt(intptr_t index, const AbstractType& value) const {
-  ASSERT(!IsCanonical());
-  StorePointer(TypeAddr(index), value.raw());
+  const AbstractType& type_arg = AbstractType::Handle(TypeAt(index));
+  if (type_arg.IsTypeRef()) {
+    if (value.raw() != type_arg.raw()) {
+      TypeRef::Cast(type_arg).set_type(value);
+    }
+  } else {
+    StorePointer(TypeAddr(index), value.raw());
+  }
 }
 
 
@@ -3915,6 +3929,14 @@
   TypeArguments& result = TypeArguments::Handle(isolate);
   result ^= table.At(index);
   if (result.IsNull()) {
+    // Canonicalize each type argument.
+    const intptr_t num_types = Length();
+    AbstractType& type = AbstractType::Handle(isolate);
+    for (intptr_t i = 0; i < num_types; i++) {
+      type = TypeAt(i);
+      type = type.Canonicalize();
+      SetTypeAt(i, type);
+    }
     // Make sure we have an old space object and add it to the table.
     if (this->IsNew()) {
       result ^= Object::Clone(*this, Heap::kOld);
@@ -11563,8 +11585,8 @@
 
 bool AbstractType::Equals(const Instance& other) const {
   // AbstractType is an abstract class.
-  ASSERT(raw() == AbstractType::null());
-  return other.IsNull();
+  UNREACHABLE();
+  return false;
 }
 
 
@@ -11685,7 +11707,8 @@
     first_type_param_index = 0;
   }
   String& type_name = String::Handle();
-  if (num_type_params == 0) {
+  if ((num_type_params == 0) ||
+      args.IsRaw(first_type_param_index, num_type_params)) {
     type_name = class_name.raw();
   } else {
     const String& args_name = String::Handle(
@@ -12054,17 +12077,6 @@
 }
 
 
-RawString* Type::TypeClassName() const {
-  if (HasResolvedTypeClass()) {
-    const Class& cls = Class::Handle(type_class());
-    return cls.Name();
-  } else {
-    const UnresolvedClass& cls = UnresolvedClass::Handle(unresolved_class());
-    return cls.Name();
-  }
-}
-
-
 RawAbstractTypeArguments* Type::arguments() const {
   return raw_ptr()->arguments_;
 }
@@ -12086,7 +12098,7 @@
 RawAbstractType* Type::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
     Error* bound_error) const {
-  ASSERT(IsResolved());
+  ASSERT(IsFinalized() || IsBeingFinalized());
   ASSERT(!IsInstantiated());
   // Return the uninstantiated type unchanged if malformed. No copy needed.
   if (IsMalformed()) {
@@ -12115,6 +12127,10 @@
   if (raw() == other.raw()) {
     return true;
   }
+  if (other.IsTypeRef()) {
+    // TODO(regis): Use trail. For now, we "unfold" the right hand type.
+    return Equals(AbstractType::Handle(TypeRef::Cast(other).type()));
+  }
   if (!other.IsType()) {
     return false;
   }
@@ -12133,13 +12149,17 @@
     return true;
   }
   const Class& cls = Class::Handle(type_class());
+  const intptr_t num_type_params = cls.NumTypeParameters();
+  if (num_type_params == 0) {
+    // Shortcut unnecessary handle allocation below.
+    return true;
+  }
+  const intptr_t num_type_args = cls.NumTypeArguments();
+  const intptr_t from_index = num_type_args - num_type_params;
   const AbstractTypeArguments& type_args = AbstractTypeArguments::Handle(
       arguments());
   const AbstractTypeArguments& other_type_args = AbstractTypeArguments::Handle(
       other_type.arguments());
-  const intptr_t num_type_args = cls.NumTypeArguments();
-  const intptr_t num_type_params = cls.NumTypeParameters();
-  const intptr_t from_index = num_type_args - num_type_params;
   if (type_args.IsNull()) {
     return other_type_args.IsRaw(from_index, num_type_params);
   }
@@ -12346,6 +12366,135 @@
 }
 
 
+bool TypeRef::IsInstantiated() const {
+  if (is_being_checked()) {
+    return true;
+  }
+  set_is_being_checked(true);
+  const bool result = AbstractType::Handle(type()).IsInstantiated();
+  set_is_being_checked(false);
+  return result;
+}
+
+
+bool TypeRef::Equals(const Instance& other) const {
+  // TODO(regis): Use trail instead of mark bit.
+  if (raw() == other.raw()) {
+    return true;
+  }
+  if (is_being_checked()) {
+    return true;
+  }
+  set_is_being_checked(true);
+  const bool result = AbstractType::Handle(type()).Equals(other);
+  set_is_being_checked(false);
+  return result;
+}
+
+
+RawAbstractType* TypeRef::InstantiateFrom(
+    const AbstractTypeArguments& instantiator_type_arguments,
+    Error* bound_error) const {
+  const AbstractType& ref_type = AbstractType::Handle(type());
+  // TODO(regis): Use trail instead of mark bit plus temporary redirection,
+  // because it could be marked for another reason.
+  if (is_being_checked()) {
+    ASSERT(ref_type.IsTypeRef());
+    return ref_type.raw();
+  }
+  set_is_being_checked(true);
+  ASSERT(!ref_type.IsTypeRef());
+  const TypeRef& instantiated_type_ref = TypeRef::Handle(
+      TypeRef::New(ref_type));
+  // TODO(regis): instantiated_type_ref should be stored in the trail instead.
+  set_type(instantiated_type_ref);
+  const AbstractType& instantiated_ref_type = AbstractType::Handle(
+      ref_type.InstantiateFrom(instantiator_type_arguments, bound_error));
+  instantiated_type_ref.set_type(instantiated_ref_type);
+  set_type(ref_type);
+  set_is_being_checked(false);
+  return instantiated_type_ref.raw();
+}
+
+
+void TypeRef::set_type(const AbstractType& value) const {
+  ASSERT(value.HasResolvedTypeClass());
+  StorePointer(&raw_ptr()->type_, value.raw());
+}
+
+
+void TypeRef::set_is_being_checked(bool value) const {
+  raw_ptr()->is_being_checked_ = value;
+}
+
+
+// This function only canonicalizes the referenced type, but not the TypeRef
+// itself, since it cannot be canonical by definition.
+// Consider the type Derived, where class Derived extends Base<Derived>.
+// The first type argument of its flattened type argument vector is Derived,
+// i.e. itself, but pointer equality is not possible.
+RawAbstractType* TypeRef::Canonicalize() const {
+  // TODO(regis): Use trail, not mark bit.
+  if (is_being_checked()) {
+    return raw();
+  }
+  set_is_being_checked(true);
+  AbstractType& ref_type = AbstractType::Handle(type());
+  ASSERT(!ref_type.IsTypeRef());
+  ref_type = ref_type.Canonicalize();
+  set_type(ref_type);
+  // No need to call SetCanonical(), since a TypeRef cannot be canonical by
+  // definition.
+  set_is_being_checked(false);
+  // We return the referenced type instead of the TypeRef in order to provide
+  // pointer equality in simple cases, e.g. in language/f_bounded_equality_test.
+  return ref_type.raw();
+}
+
+
+intptr_t TypeRef::Hash() const {
+  // TODO(regis): Use trail and hash of referenced type.
+  // Do not calculate the hash of the referenced type to avoid cycles.
+  uword result = Class::Handle(AbstractType::Handle(type()).type_class()).id();
+  return FinalizeHash(result);
+}
+
+
+RawTypeRef* TypeRef::New() {
+  ASSERT(Isolate::Current()->object_store()->type_ref_class() != Class::null());
+  RawObject* raw = Object::Allocate(TypeRef::kClassId,
+                                    TypeRef::InstanceSize(),
+                                    Heap::kOld);
+  return reinterpret_cast<RawTypeRef*>(raw);
+}
+
+
+RawTypeRef* TypeRef::New(const AbstractType& type) {
+  const TypeRef& result = TypeRef::Handle(TypeRef::New());
+  result.set_type(type);
+  result.set_is_being_checked(false);
+  return result.raw();
+}
+
+
+const char* TypeRef::ToCString() const {
+  const char* format = "TypeRef: %s%s";
+  const char* type_cstr = String::Handle(Class::Handle(AbstractType::Handle(
+      type()).type_class()).Name()).ToCString();
+  const char* args_cstr = (AbstractType::Handle(
+      type()).arguments() == AbstractTypeArguments::null()) ? "" : "<...>";
+  intptr_t len = OS::SNPrint(NULL, 0, format, type_cstr, args_cstr) + 1;
+  char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
+  OS::SNPrint(chars, len, format, type_cstr, args_cstr);
+  return chars;
+}
+
+
+void TypeRef::PrintToJSONStream(JSONStream* stream, bool ref) const {
+  JSONObject jsobj(stream);
+}
+
+
 void TypeParameter::set_is_finalized() const {
   ASSERT(!IsFinalized());
   set_type_state(RawTypeParameter::kFinalizedUninstantiated);
@@ -12356,6 +12505,10 @@
   if (raw() == other.raw()) {
     return true;
   }
+  if (other.IsTypeRef()) {
+    // TODO(regis): Use trail. For now, we "unfold" the right hand type.
+    return Equals(AbstractType::Handle(TypeRef::Cast(other).type()));
+  }
   if (!other.IsTypeParameter()) {
     return false;
   }
@@ -12400,7 +12553,24 @@
   if (instantiator_type_arguments.IsNull()) {
     return Type::DynamicType();
   }
-  return instantiator_type_arguments.TypeAt(index());
+  const AbstractType& type_arg = AbstractType::Handle(
+      instantiator_type_arguments.TypeAt(index()));
+  // There is no need to canonicalize the instantiated type parameter, since all
+  // type arguments are canonicalized at type finalization time. It would be too
+  // early to canonicalize the returned type argument here, since instantiation
+  // not only happens at run time, but also during type finalization.
+  // However, if the type argument is a reference to a canonical type, we
+  // return the referenced canonical type instead of the type reference to
+  // provide pointer equality in some simple cases, e.g. in
+  // language/f_bounded_equality_test.
+  if (type_arg.IsTypeRef()) {
+    const AbstractType& ref_type = AbstractType::Handle(
+        TypeRef::Cast(type_arg).type());
+    if (ref_type.IsCanonical()) {
+      return ref_type.raw();
+    }
+  }
+  return type_arg.raw();
 }
 
 
@@ -12465,8 +12635,7 @@
 
 intptr_t TypeParameter::Hash() const {
   ASSERT(IsFinalized());
-  uword result = 0;
-  result += Class::Handle(parameterized_class()).id();
+  uword result = Class::Handle(parameterized_class()).id();
   // Do not include the hash of the bound, which could lead to cycles.
   result <<= index();
   return FinalizeHash(result);
@@ -12557,6 +12726,10 @@
   if (raw() == other.raw()) {
     return true;
   }
+  if (other.IsTypeRef()) {
+    // TODO(regis): Use trail. For now, we "unfold" the right hand type.
+    return Equals(AbstractType::Handle(TypeRef::Cast(other).type()));
+  }
   if (!other.IsBoundedType()) {
     return false;
   }
@@ -12580,7 +12753,7 @@
 
 
 void BoundedType::set_type(const AbstractType& value) const {
-  ASSERT(value.IsFinalized());
+  ASSERT(value.IsFinalized() || value.IsBeingFinalized());
   ASSERT(!value.IsMalformed());
   StorePointer(&raw_ptr()->type_, value.raw());
 }
@@ -12660,13 +12833,9 @@
 
 
 intptr_t BoundedType::Hash() const {
-  uword result = 0;
-  result += AbstractType::Handle(type()).Hash();
+  uword 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();
-  }
+  result += TypeParameter::Handle(type_parameter()).Hash();
 return FinalizeHash(result);
 }