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

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/cpu.h"
@@ skipping 884 matching lines @@
   // Last element contains the count of used slots.
   const intptr_t kInitialCanonicalTypeArgumentsSize = 4;
   array = Array::New(kInitialCanonicalTypeArgumentsSize + 1);
   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<TypeRef>();
+  object_store->set_type_ref_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<MixinAppType>();
   object_store->set_mixin_app_type_class(cls);
 
   // Pre-allocate the OneByteString class needed by the symbol table.
@@ skipping 111 matching lines @@
   cls.set_num_type_arguments(0);
   cls.set_num_own_type_arguments(0);
   cls.set_is_prefinalized();
   RegisterClass(cls, Symbols::Null(), core_lib);
   pending_classes.Add(cls);
 
   cls = object_store->type_class();
   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);
 
   cls = object_store->bounded_type_class();
   RegisterPrivateClass(cls, Symbols::BoundedType(), core_lib);
   pending_classes.Add(cls);
 
   cls = object_store->mixin_app_type_class();
   RegisterPrivateClass(cls, Symbols::MixinAppType(), core_lib);
@@ skipping 237 matching lines @@
 
   // Set up empty classes in the object store, these will get
   // initialized correctly when we read from the snapshot.
   // 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<TypeRef>();
+  object_store->set_type_ref_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<MixinAppType>();
   object_store->set_mixin_app_type_class(cls);
 
   cls = Class::New<Array>();
@@ skipping 681 matching lines @@
     return Class::null();
   }
   const AbstractType& sup_type = AbstractType::Handle(super_type());
   return sup_type.type_class();
 }
 
 
 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());
 }
 
 
 // Return a TypeParameter if the type_name is a type parameter of this class.
 // Return null otherwise.
 RawTypeParameter* Class::LookupTypeParameter(const String& type_name) const {
   ASSERT(!type_name.IsNull());
@@ skipping 1502 matching lines @@
   Class& type_class = Class::Handle();
   for (intptr_t i = 0; i < len; i++) {
     type = TypeAt(from_index + i);
     ASSERT(!type.IsNull());
     if (!type.HasResolvedTypeClass()) {
       if (raw_instantiated && type.IsTypeParameter()) {
         // 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;
 }
 
@@ skipping 43 matching lines @@
   return Smi::Value(raw_ptr()->length_);
 }
 
 
 RawAbstractType* TypeArguments::TypeAt(intptr_t index) const {
   return *TypeAddr(index);
 }
 
 
 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());
+  }
 }
 
 
 bool TypeArguments::IsResolved() const {
   AbstractType& type = AbstractType::Handle();
   const intptr_t num_types = Length();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     if (!type.IsResolved()) {
       return false;
@@ skipping 314 matching lines @@
   const Array& table = Array::Handle(isolate,
                                      object_store->canonical_type_arguments());
   ASSERT(table.Length() > 0);
   intptr_t index = FindIndexInCanonicalTypeArguments(isolate,
                                                      table,
                                                      *this,
                                                      Hash());
   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);
     } else {
       result ^= this->raw();
     }
     ASSERT(result.IsOld());
     InsertIntoCanonicalTypeArguments(isolate, table, result, index);
   }
   ASSERT(result.Equals(*this));
@@ skipping 7628 matching lines @@
 
 
 void AbstractType::set_error(const LanguageError& value) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
 }
 
 
 bool AbstractType::Equals(const Instance& other) const {
   // AbstractType is an abstract class.
-  ASSERT(raw() == AbstractType::null());
-  return other.IsNull();
+  UNREACHABLE();
+  return false;
 }
 
 
 RawAbstractType* AbstractType::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
     Error* bound_error) const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return NULL;
 }
@@ skipping 100 matching lines @@
                                                             name_visibility);
       }
     }
   } else {
     const UnresolvedClass& cls = UnresolvedClass::Handle(unresolved_class());
     class_name = cls.Name();
     num_type_params = num_args;
     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(
         args.SubvectorName(first_type_param_index,
                            num_type_params,
                            name_visibility));
     type_name = String::Concat(class_name, args_name);
   }
   // The name is only used for type checking and debugging purposes.
   // Unless profiling data shows otherwise, it is not worth caching the name in
@@ skipping 348 matching lines @@
   ASSERT(!unresolved_class.IsNull());
   return unresolved_class.raw();
 #else
   ASSERT(!Object::Handle(raw_ptr()->type_class_).IsNull());
   ASSERT(Object::Handle(raw_ptr()->type_class_).IsUnresolvedClass());
   return reinterpret_cast<RawUnresolvedClass*>(raw_ptr()->type_class_);
 #endif
 }
 
 
-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_;
 }
 
 
 bool Type::IsInstantiated() const {
   if (raw_ptr()->type_state_ == RawType::kFinalizedInstantiated) {
     return true;
   }
   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,
     Error* bound_error) const {
-  ASSERT(IsResolved());
+  ASSERT(IsFinalized() || IsBeingFinalized());
   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,
                                                   bound_error);
   // Note that the type class has to be resolved at this time, but not
   // necessarily finalized yet. We may be checking bounds at compile time.
   const Class& cls = Class::Handle(type_class());
   // 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 {
   ASSERT(!IsNull());
   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;
   }
   const Type& other_type = Type::Cast(other);
   ASSERT(IsResolved() && other_type.IsResolved());
   if (IsMalformed() || other_type.IsMalformed()) {
     return false;
   }
   if (type_class() != other_type.type_class()) {
     return false;
   }
   if (!IsFinalized() || !other_type.IsFinalized()) {
     return false;
   }
   if (arguments() == other_type.arguments()) {
     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);
   }
   if (other_type_args.IsNull()) {
     return type_args.IsRaw(from_index, num_type_params);
   }
   ASSERT(type_args.Length() >= (from_index + num_type_params));
   ASSERT(other_type_args.Length() >= (from_index + num_type_params));
   AbstractType& type_arg = AbstractType::Handle();
   AbstractType& other_type_arg = AbstractType::Handle();
@@ skipping 186 matching lines @@
     return "Unresolved Type";
   }
 }
 
 
 void Type::PrintToJSONStream(JSONStream* stream, bool ref) const {
   JSONObject jsobj(stream);
 }
 
 
+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);
 }
 
 
 bool TypeParameter::Equals(const Instance& other) const {
   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;
   }
   const TypeParameter& other_type_param = TypeParameter::Cast(other);
   if (parameterized_class() != other_type_param.parameterized_class()) {
     return false;
   }
   if (IsFinalized() == other_type_param.IsFinalized()) {
     return index() == other_type_param.index();
   }
@@ skipping 24 matching lines @@
 }
 
 
 RawAbstractType* TypeParameter::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
     Error* bound_error) const {
   ASSERT(IsFinalized());
   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();
 }
 
 
 bool TypeParameter::CheckBound(const AbstractType& bounded_type,
                                const AbstractType& upper_bound,
                                Error* bound_error) const {
   ASSERT((bound_error != NULL) && bound_error->IsNull());
   ASSERT(bounded_type.IsFinalized());
   ASSERT(upper_bound.IsFinalized());
   ASSERT(!bounded_type.IsMalformed());
@@ skipping 44 matching lines @@
   return TypeParameter::New(Class::Handle(parameterized_class()),
                             index(),
                             String::Handle(name()),
                             AbstractType::Handle(bound()),
                             token_pos());
 }
 
 
 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);
 }
 
 
 RawTypeParameter* TypeParameter::New() {
   ASSERT(Isolate::Current()->object_store()->type_parameter_class() !=
          Class::null());
   RawObject* raw = Object::Allocate(TypeParameter::kClassId,
@@ skipping 70 matching lines @@
   return AbstractType::Handle(type()).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.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;
   }
   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.IsFinalized() || value.IsBeingFinalized());
   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());
 }
@@ skipping 59 matching lines @@
   bounded_type = bounded_type.CloneUnfinalized();
   // No need to clone bound or type parameter, as they are not part of the
   // finalization state of this bounded type.
   return BoundedType::New(bounded_type,
                           AbstractType::Handle(bound()),
                           TypeParameter::Handle(type_parameter()));
 }
 
 
 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);
 }
 
 
 RawBoundedType* BoundedType::New() {
   ASSERT(Isolate::Current()->object_store()->bounded_type_class() !=
          Class::null());
   RawObject* raw = Object::Allocate(BoundedType::kClassId,
                                     BoundedType::InstanceSize(),
                                     Heap::kOld);
@@ skipping 3507 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Instance::PrintToJSONStream(stream, ref);
 }
 
 
 }  // namespace dart