Canonicalize generic types in an isolate specific hash table

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 1033 matching lines @@
   // Returns the cached canonical type of this class, i.e. the canonical type
   // whose type class is this class and whose type arguments are the
   // uninstantiated type parameters declared by this class if it is generic,
   // e.g. Map<K, V>.
   // Returns Type::null() if the canonical type is not cached yet.
   RawType* CanonicalType() const;
 
   // Caches the canonical type of this class.
   void SetCanonicalType(const Type& type) const;
 
-  static intptr_t canonical_types_offset() {
-    return OFFSET_OF(RawClass, canonical_types_);
+  static intptr_t canonical_type_offset() {
+    return OFFSET_OF(RawClass, canonical_type_);
   }
 
   // The super type of this class, Object type if not explicitly specified.
   // Note that the super type may be bounded, as in this example:
   // class C<T> extends S<T> { }; class S<T extends num> { };
   RawAbstractType* super_type() const { return raw_ptr()->super_type_; }
   void set_super_type(const AbstractType& value) const;
   static intptr_t super_type_offset() {
     return OFFSET_OF(RawClass, super_type_);
   }
@@ skipping 148 matching lines @@
   // The methods above are more efficient than this generic one.
   RawInstance* LookupCanonicalInstance(Zone* zone,
                                        const Instance& value) const;
 
   RawInstance* InsertCanonicalConstant(Zone* zone,
                                        const Instance& constant) const;
   void InsertCanonicalNumber(Zone* zone,
                              intptr_t index,
                              const Number& constant) const;
 
-  intptr_t FindCanonicalTypeIndex(const AbstractType& needle) const;
-  RawAbstractType* CanonicalTypeFromIndex(intptr_t idx) const;
-
   void RehashConstants(Zone* zone) const;
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawClass));
   }
 
   bool is_implemented() const {
     return ImplementedBit::decode(raw_ptr()->state_bits_);
   }
   void set_is_implemented() const;
@@ skipping 210 matching lines @@
   class EnumBit : public BitField<uint16_t, bool, kEnumBit, 1> {};
   class IsAllocatedBit : public BitField<uint16_t, bool, kIsAllocatedBit, 1> {};
 
   void set_name(const String& value) const;
   void set_user_name(const String& value) const;
   RawString* GenerateUserVisibleName() const;
   void set_state_bits(intptr_t bits) const;
 
   void set_constants(const Array& value) const;
 
-  void set_canonical_types(const Object& value) const;
-  RawObject* canonical_types() const;
+  void set_canonical_type(const Type& value) const;
+  RawType* canonical_type() const;
 
   RawArray* invocation_dispatcher_cache() const;
   void set_invocation_dispatcher_cache(const Array& cache) const;
   RawFunction* CreateInvocationDispatcher(const String& target_name,
                                           const Array& args_desc,
                                           RawFunction::Kind kind) const;
 
   void CalculateFieldOffsets() const;
 
   // functions_hash_table is in use iff there are at least this many functions.
@@ skipping 43 matching lines @@
   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);
 
-  // Returns AbstractType::null() if type not found.
-  RawAbstractType* LookupCanonicalType(Zone* zone,
-                                       const AbstractType& type,
-                                       intptr_t* index) const;
-
-  // Returns canonical type. Thread safe.
-  RawAbstractType* LookupOrAddCanonicalType(const AbstractType& type,
-                                            intptr_t start_index) const;
-
   FINAL_HEAP_OBJECT_IMPLEMENTATION(Class, Object);
   friend class AbstractType;
   friend class Instance;
   friend class Object;
   friend class Type;
   friend class Intrinsifier;
   friend class Precompiler;
 };
 
 
@@ skipping 25 matching lines @@
   static RawUnresolvedClass* New();
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(UnresolvedClass, Object);
   friend class Class;
 };
 
 
 // A TypeArguments is an array of AbstractType.
 class TypeArguments : public Object {
  public:
+  // We use 30 bits for the hash code so hashes in a snapshot taken on a
+  // 64-bit architecture stay in Smi range when loaded on a 32-bit
+  // architecture.
+  static const intptr_t kHashBits = 30;
+
   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;
 
   // The name of this type argument vector, e.g. "<T, dynamic, List<T>, Smi>".
   RawString* Name() const {
@@ skipping 124 matching lines @@
   static const intptr_t kMaxElements = kSmiMax / kBytesPerElement;
 
   static intptr_t InstanceSize() {
     ASSERT(sizeof(RawTypeArguments) ==
            OFFSET_OF_RETURNED_VALUE(RawTypeArguments, types));
     return 0;
   }
 
   static intptr_t InstanceSize(intptr_t len) {
     // Ensure that the types() is not adding to the object size, which includes
-    // 2 fields: instantiations_ and length_.
-    ASSERT(sizeof(RawTypeArguments) == (sizeof(RawObject) + (2 * kWordSize)));
+    // 3 fields: instantiations_, length_ and hash_.
+    ASSERT(sizeof(RawTypeArguments) ==
+           (sizeof(RawObject) + (kNumFields * kWordSize)));
     ASSERT(0 <= len && len <= kMaxElements);
     return RoundedAllocationSize(
         sizeof(RawTypeArguments) + (len * kBytesPerElement));
   }
 
   intptr_t Hash() const;
 
   static RawTypeArguments* New(intptr_t len, Heap::Space space = Heap::kOld);
 
  private:
+  intptr_t ComputeHash() const;
+  void SetHash(intptr_t value) const;
+
   // Check if the subvector of length 'len' starting at 'from_index' of this
   // type argument vector consists solely of DynamicType.
   // If raw_instantiated is true, consider each type parameter to be first
   // instantiated from a vector of dynamic types.
   bool IsDynamicTypes(bool raw_instantiated,
                       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;
   RawAbstractType* const* TypeAddr(intptr_t index) const;
   void SetLength(intptr_t value) const;
+  // Number of fields in the raw object=3 (instantiations_, length_ and hash_).
+  static const int kNumFields = 3;
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(TypeArguments, Object);
   friend class AbstractType;
   friend class Class;
 };
 
 
 class PatchClass : public Object {
  public:
   RawClass* patched_class() const { return raw_ptr()->patched_class_; }
@@ skipping 3793 matching lines @@
 
 // A Type consists of a class, possibly parameterized with type
 // arguments. Example: C<T1, T2>.
 // An unresolved class is a String specifying the class name.
 //
 // Caution: 'RawType*' denotes a 'raw' pointer to a VM object of class Type, as
 // opposed to 'Type' denoting a 'handle' to the same object. 'RawType' does not
 // relate to a 'raw type', as opposed to a 'cooked type' or 'rare type'.
 class Type : public AbstractType {
  public:
+  // We use 30 bits for the hash code so that we consistently use a
+  // 32bit Smi representation for the hash code on all architectures.
+  static const intptr_t kHashBits = 30;
+
   static intptr_t type_class_offset() {
     return OFFSET_OF(RawType, type_class_);
   }
   virtual bool IsFinalized() const {
     return
         (raw_ptr()->type_state_ == RawType::kFinalizedInstantiated) ||
         (raw_ptr()->type_state_ == RawType::kFinalizedUninstantiated);
   }
   virtual void SetIsFinalized() const;
   void ResetIsFinalized() const;  // Ignore current state and set again.
@@ skipping 95 matching lines @@
 
   // The finalized type of the given non-parameterized class.
   static RawType* NewNonParameterizedType(const Class& type_class);
 
   static RawType* New(const Object& clazz,
                       const TypeArguments& arguments,
                       TokenPosition token_pos,
                       Heap::Space space = Heap::kOld);
 
  private:
+  intptr_t ComputeHash() const;
+  void SetHash(intptr_t value) const;
+
   void set_token_pos(TokenPosition token_pos) const;
   void set_type_state(int8_t state) const;
 
   static RawType* New(Heap::Space space = Heap::kOld);
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(Type, AbstractType);
   friend class Class;
   friend class TypeArguments;
 };
 
@@ skipping 70 matching lines @@
 // upper bound.
 // For example, the type parameter 'V' is specified as index 1 in the context of
 // the class HashMap<K, V>. At compile time, the TypeParameter is not
 // instantiated yet, i.e. it is only a place holder.
 // Upon finalization, the TypeParameter index is changed to reflect its position
 // as type argument (rather than type parameter) of the parameterized class.
 // If the type parameter is declared without an extends clause, its bound is set
 // to the ObjectType.
 class TypeParameter : public AbstractType {
  public:
+  // We use 30 bits for the hash code so that we consistently use a
+  // 32bit Smi representation for the hash code on all architectures.
+  static const intptr_t kHashBits = 30;
+
   virtual bool IsFinalized() const {
     ASSERT(raw_ptr()->type_state_ != RawTypeParameter::kFinalizedInstantiated);
     return raw_ptr()->type_state_ == RawTypeParameter::kFinalizedUninstantiated;
   }
   virtual void SetIsFinalized() const;
   virtual bool IsBeingFinalized() const { return false; }
   virtual bool IsMalformed() const { return false; }
   virtual bool IsMalbounded() const { return false; }
   virtual bool IsMalformedOrMalbounded() const { return false; }
   virtual bool IsResolved() const { return true; }
@@ skipping 41 matching lines @@
     return RoundedAllocationSize(sizeof(RawTypeParameter));
   }
 
   static RawTypeParameter* New(const Class& parameterized_class,
                                intptr_t index,
                                const String& name,
                                const AbstractType& bound,
                                TokenPosition token_pos);
 
  private:
+  intptr_t ComputeHash() const;
+  void SetHash(intptr_t value) const;
+
   void set_parameterized_class(const Class& value) const;
   void set_name(const String& value) const;
   void set_token_pos(TokenPosition token_pos) const;
   void set_type_state(int8_t state) const;
 
   static RawTypeParameter* New();
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(TypeParameter, AbstractType);
   friend class Class;
 };
 
 
 // A BoundedType represents a type instantiated at compile time from a type
 // parameter specifying a bound that either cannot be checked at compile time
 // because the type or the bound are still uninstantiated or can be checked and
 // would trigger a bound error in checked mode. The bound must be checked at
 // runtime once the type and its bound are instantiated and when the execution
 // mode is known to be checked mode.
 class BoundedType : public AbstractType {
  public:
+  // We use 30 bits for the hash code so that we consistently use a
+  // 32bit Smi representation for the hash code on all architectures.
+  static const intptr_t kHashBits = 30;
+
   virtual bool IsFinalized() const {
     return AbstractType::Handle(type()).IsFinalized();
   }
   virtual bool IsBeingFinalized() const {
     return AbstractType::Handle(type()).IsBeingFinalized();
   }
   virtual bool IsMalformed() const;
   virtual bool IsMalbounded() const;
   virtual bool IsMalformedOrMalbounded() const;
   virtual RawLanguageError* error() const;
@@ skipping 45 matching lines @@
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawBoundedType));
   }
 
   static RawBoundedType* New(const AbstractType& type,
                              const AbstractType& bound,
                              const TypeParameter& type_parameter);
 
  private:
+  intptr_t ComputeHash() const;
+  void SetHash(intptr_t value) const;
+
   void set_type(const AbstractType& value) const;
   void set_bound(const AbstractType& value) const;
   void set_type_parameter(const TypeParameter& value) const;
 
   static RawBoundedType* New();
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(BoundedType, AbstractType);
   friend class Class;
 };
 
@@ skipping 1174 matching lines @@
   static RawBool* New(bool value);
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(Bool, Instance);
   friend class Class;
   friend class Object;  // To initialize the true and false values.
 };
 
 
 class Array : public Instance {
  public:
+  // We use 30 bits for the hash code so that we consistently use a
+  // 32bit Smi representation for the hash code on all architectures.
+  static const intptr_t kHashBits = 30;
+
   intptr_t Length() const {
     ASSERT(!IsNull());
     return Smi::Value(raw_ptr()->length_);
   }
   static intptr_t length_offset() { return OFFSET_OF(RawArray, length_); }
   static intptr_t data_offset() {
     return OFFSET_OF_RETURNED_VALUE(RawArray, data);
   }
   static intptr_t element_offset(intptr_t index) {
     return OFFSET_OF_RETURNED_VALUE(RawArray, data) + kWordSize * index;
@@ skipping 347 matching lines @@
   }
 
  private:
   FINAL_HEAP_OBJECT_IMPLEMENTATION(Float64x2, Instance);
   friend class Class;
 };
 
 
 class TypedData : public Instance {
  public:
+  // We use 30 bits for the hash code so that we consistently use a
+  // 32bit Smi representation for the hash code on all architectures.
+  static const intptr_t kHashBits = 30;
+
   intptr_t Length() const {
     ASSERT(!IsNull());
     return Smi::Value(raw_ptr()->length_);
   }
 
   intptr_t ElementSizeInBytes() const {
     intptr_t cid = raw()->GetClassId();
     return ElementSizeInBytes(cid);
   }
 
@@ skipping 1026 matching lines @@
 RawObject* MegamorphicCache::GetClassId(const Array& array, intptr_t index) {
   return array.At((index * kEntryLength) + kClassIdIndex);
 }
 
 
 RawObject* MegamorphicCache::GetTargetFunction(const Array& array,
                                                intptr_t index) {
   return array.At((index * kEntryLength) + kTargetFunctionIndex);
 }
 
+
+inline intptr_t Type::Hash() const {
+  intptr_t result = Smi::Value(raw_ptr()->hash_);
+  if (result != 0) {
+    return result;
+  }
+  return ComputeHash();
+}
+
+
+inline void Type::SetHash(intptr_t value) const {
+  // This is only safe because we create a new Smi, which does not cause
+  // heap allocation.
+  StoreSmi(&raw_ptr()->hash_, Smi::New(value));
+}
+
+
+inline intptr_t TypeParameter::Hash() const {
+  ASSERT(IsFinalized());
+  intptr_t result = Smi::Value(raw_ptr()->hash_);
+  if (result != 0) {
+    return result;
+  }
+  return ComputeHash();
+}
+
+
+inline void TypeParameter::SetHash(intptr_t value) const {
+  // This is only safe because we create a new Smi, which does not cause
+  // heap allocation.
+  StoreSmi(&raw_ptr()->hash_, Smi::New(value));
+}
+
+
+inline intptr_t BoundedType::Hash() const {
+  intptr_t result = Smi::Value(raw_ptr()->hash_);
+  if (result != 0) {
+    return result;
+  }
+  return ComputeHash();
+}
+
+
+inline void BoundedType::SetHash(intptr_t value) const {
+  // This is only safe because we create a new Smi, which does not cause
+  // heap allocation.
+  StoreSmi(&raw_ptr()->hash_, Smi::New(value));
+}
+
+
+inline intptr_t TypeArguments::Hash() const {
+  if (IsNull()) return 0;
+  intptr_t result = Smi::Value(raw_ptr()->hash_);
+  if (result != 0) {
+    return result;
+  }
+  return ComputeHash();
+}
+
+
+inline void TypeArguments::SetHash(intptr_t value) const {
+  // This is only safe because we create a new Smi, which does not cause
+  // heap allocation.
+  StoreSmi(&raw_ptr()->hash_, Smi::New(value));
+}
+
 }  // namespace dart
 
 #endif  // VM_OBJECT_H_