Store canonical type argments in a hash table instead of linear list.

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 901 matching lines @@
   bool Equals(const AbstractTypeArguments& other) 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 IsUninstantiatedIdentity() const;
 
+  virtual uword Hash() const;

[Ivan Posva, 2012/12/11 14:54:52]

Hash is not an address, please use intptr_t.

[Florian Schneider, 2012/12/11 15:42:32]

I think uword is appropiate also for things like sizes, array length, table
indices.

Since intptr_t can be negative, I need a explicit cast every  time I use the
hash for indexing. 

I think intptr_t is less safe because of the required cast or relying on the
hash computation to never produce a negative value.

Otherwise, I can choose to make the hash unsigned by type and no static_cast
etc. is needed.

+
  private:
   // Check if this type argument vector consists solely of DynamicType,
   // considering only a prefix of length 'len'.
   // 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 len) const;
 
   // Check the subtype or 'more specific' relationship, considering only a
   // prefix of length 'len'.
   bool TypeTest(TypeTestKind test_kind,
@@ skipping 2310 matching lines @@
   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);
   }
 
+  virtual uword Hash() const;

[Ivan Posva, 2012/12/11 14:54:52]

ditto

+
   // The name of this type's class, i.e. without the type argument names of this
   // type.
   RawString* ClassName() const;
 
   // Check if this type represents the 'dynamic' type.
   bool IsDynamicType() const {
     return HasResolvedTypeClass() && (type_class() == Object::dynamic_class());
   }
 
   // Check if this type represents the 'Null' type.
@@ skipping 92 matching lines @@
   RawString* TypeClassName() 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 RawAbstractType* InstantiateFrom(
       const AbstractTypeArguments& instantiator_type_arguments) const;
   virtual RawAbstractType* Canonicalize() const;
 
+  virtual uword Hash() const;

[Ivan Posva, 2012/12/11 14:54:52]

ditto

+
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawType));
   }
 
   // The type of the literal 'null'.
   static RawType* NullType();
 
   // The 'dynamic' type.
   static RawType* DynamicType();
 
@@ skipping 78 matching lines @@
   void set_index(intptr_t value) const;
   RawAbstractType* bound() const { return raw_ptr()->bound_; }
   void set_bound(const AbstractType& value) 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 RawAbstractType* InstantiateFrom(
       const AbstractTypeArguments& instantiator_type_arguments) const;
   virtual RawAbstractType* Canonicalize() const { return raw(); }
 
+  virtual uword Hash() const;

[Ivan Posva, 2012/12/11 14:54:52]

ditto

+
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawTypeParameter));
   }
 
   static RawTypeParameter* New(const Class& parameterized_class,
                                intptr_t index,
                                const String& name,
                                const AbstractType& bound,
                                intptr_t token_pos);
 
@@ skipping 2669 matching lines @@
 
 
 RawObject* MegamorphicCache::GetTargetFunction(const Array& array,
                                                intptr_t index) {
   return array.At((index * kEntryLength) + kTargetFunctionIndex);
 }
 
 }  // namespace dart
 
 #endif  // VM_OBJECT_H_