Improve type test and type equality for generics (issue 15148).

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 2760 matching lines @@
       return (test_kind == Class::kIsMoreSpecificThan) ||
       other.IsObjectClass() || other.IsNullClass();
     }
     // Check for ObjectType. Any type that is not NullType or DynamicType
     // (already checked above), is more specific than ObjectType.
     if (other.IsObjectClass()) {
       return true;
     }
     // Check for reflexivity.
     if (thsi.raw() == other.raw()) {
-      const intptr_t len = thsi.NumTypeArguments();
-      if (len == 0) {
+      const intptr_t num_type_args = thsi.NumTypeArguments();
+      if (num_type_args == 0) {
         return true;
       }
+      const intptr_t num_type_params = thsi.NumTypeParameters();
+      const intptr_t from_index = num_type_args - num_type_params;
       // Since we do not truncate the type argument vector of a subclass (see
-      // below), we only check a prefix of the proper length.
+      // below), we only check a subvector of the proper length.
       // Check for covariance.
-      if (other_type_arguments.IsNull() || other_type_arguments.IsRaw(len)) {
+      if (other_type_arguments.IsNull() ||
+          other_type_arguments.IsRaw(from_index, num_type_params)) {
         return true;
       }
-      if (type_arguments.IsNull() || type_arguments.IsRaw(len)) {
+      if (type_arguments.IsNull() ||
+          type_arguments.IsRaw(from_index, num_type_params)) {
         // Other type can't be more specific than this one because for that
         // it would have to have all dynamic type arguments which is checked
         // above.
         return test_kind == Class::kIsSubtypeOf;
       }
       return type_arguments.TypeTest(test_kind,
                                      other_type_arguments,
-                                     len,
+                                     from_index,
+                                     num_type_params,
                                      bound_error);
     }
     const bool other_is_function_class = other.IsFunctionClass();
     if (other.IsSignatureClass() || other_is_function_class) {
       const Function& other_fun = Function::Handle(other.signature_function());
       if (thsi.IsSignatureClass()) {
         if (other_is_function_class) {
           return true;
         }
         // Check for two function types.
@@ skipping 642 matching lines @@
     }
   }
   strings.SetAt(s++, Symbols::RAngleBracket());
   ASSERT(s == num_strings);
   name = String::ConcatAll(strings);
   return Symbols::New(name);
 }
 
 
 bool AbstractTypeArguments::Equals(const AbstractTypeArguments& other) const {
-  ASSERT(!IsNull());  // Use AbstractTypeArguments::AreEqual().
   if (this->raw() == other.raw()) {
     return true;
   }
-  if (other.IsNull()) {
+  if (IsNull() || other.IsNull()) {
     return false;
   }
   const intptr_t num_types = Length();
   if (num_types != other.Length()) {
     return false;
   }
   AbstractType& type = AbstractType::Handle();
   AbstractType& other_type = AbstractType::Handle();
   for (intptr_t i = 0; i < num_types; i++) {
     type = TypeAt(i);
     other_type = other.TypeAt(i);
     if (!type.Equals(other_type)) {
       return false;
     }
   }
   return true;
 }
 
 
-bool AbstractTypeArguments::AreEqual(
-    const AbstractTypeArguments& arguments,
-    const AbstractTypeArguments& other_arguments) {
-  if (arguments.raw() == other_arguments.raw()) {
-    return true;
-  }
-  if (arguments.IsNull()) {
-    return other_arguments.IsDynamicTypes(false, other_arguments.Length());
-  }
-  if (other_arguments.IsNull()) {
-    return arguments.IsDynamicTypes(false, arguments.Length());
-  }
-  return arguments.Equals(other_arguments);
-}
-
-
 RawAbstractTypeArguments* AbstractTypeArguments::InstantiateFrom(
     const AbstractTypeArguments& instantiator_type_arguments,
     Error* bound_error) const {
   // AbstractTypeArguments is an abstract class.
   UNREACHABLE();
   return NULL;
 }
 
 
 bool AbstractTypeArguments::IsDynamicTypes(bool raw_instantiated,
+                                           intptr_t from_index,
                                            intptr_t len) const {
-  ASSERT(Length() >= len);
+  ASSERT(Length() >= (from_index + len));
   AbstractType& type = AbstractType::Handle();
   Class& type_class = Class::Handle();
   for (intptr_t i = 0; i < len; i++) {
-    type = TypeAt(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;
 }
 
 
 bool AbstractTypeArguments::TypeTest(TypeTestKind test_kind,
                                      const AbstractTypeArguments& other,
+                                     intptr_t from_index,
                                      intptr_t len,
                                      Error* bound_error) const {
-  ASSERT(Length() >= len);
+  ASSERT(Length() >= (from_index + len));
   ASSERT(!other.IsNull());
-  ASSERT(other.Length() >= len);
+  ASSERT(other.Length() >= (from_index + len));
   AbstractType& type = AbstractType::Handle();
   AbstractType& other_type = AbstractType::Handle();
   for (intptr_t i = 0; i < len; i++) {
-    type = TypeAt(i);
+    type = TypeAt(from_index + i);
     ASSERT(!type.IsNull());
-    other_type = other.TypeAt(i);
+    other_type = other.TypeAt(from_index + i);
     ASSERT(!other_type.IsNull());
     if (!type.TypeTest(test_kind, other_type, bound_error)) {
       return false;
     }
   }
   return true;
 }
 
 
 const char* AbstractTypeArguments::ToCString() const {
@@ skipping 8434 matching lines @@
   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.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;
   }
-  return AbstractTypeArguments::AreEqual(
-      AbstractTypeArguments::Handle(arguments()),
-      AbstractTypeArguments::Handle(other_type.arguments()));
+  if (arguments() == other_type.arguments()) {
+    return true;
+  }
+  const Class& cls = Class::Handle(type_class());
+  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();
+  for (intptr_t i = 0; i < num_type_params; i++) {
+    type_arg = type_args.TypeAt(from_index + i);
+    other_type_arg = other_type_args.TypeAt(from_index + i);
+    if (!type_arg.Equals(other_type_arg)) {
+      return false;
+    }
+  }
+  return true;
 }
 
 
 RawAbstractType* Type::CloneUnfinalized() const {
   ASSERT(IsResolved());
   if (IsFinalized()) {
     return raw();
   }
   ASSERT(!IsMalformed());  // Malformed types are finalized.
   ASSERT(!IsBeingFinalized());  // Cloning must occur prior to finalization.
@@ skipping 29 matching lines @@
       break;
     }
     ASSERT(type.IsFinalized());
     if (this->Equals(type)) {
       return type.raw();
     }
     index++;
   }
   // Canonicalize the type arguments.
   AbstractTypeArguments& type_args = AbstractTypeArguments::Handle(arguments());
+  ASSERT(type_args.IsNull() || (type_args.Length() == cls.NumTypeArguments()));
   type_args = type_args.Canonicalize();
   set_arguments(type_args);
   // The type needs to be added to the list. Grow the list if it is full.
   if (index == canonical_types_len) {
     const intptr_t kLengthIncrement = 2;  // Raw and parameterized.
     const intptr_t new_length = canonical_types.Length() + kLengthIncrement;
     const Array& new_canonical_types =
         Array::Handle(Array::Grow(canonical_types, new_length, Heap::kOld));
     cls.set_canonical_types(new_canonical_types);
     new_canonical_types.SetAt(index, *this);
@@ skipping 2784 matching lines @@
   JSONObject jsobj(stream);
 }
 
 
 bool Array::Equals(const Instance& other) const {
   if (this->raw() == other.raw()) {
     // Both handles point to the same raw instance.
     return true;
   }
 
+  // An Array may be compared to an ImmutableArray.
   if (!other.IsArray() || other.IsNull()) {
     return false;
   }
 
-  // Must have the same type arguments.
-  if (!AbstractTypeArguments::AreEqual(
-      AbstractTypeArguments::Handle(GetTypeArguments()),
-      AbstractTypeArguments::Handle(other.GetTypeArguments()))) {
+  // Both arrays must have the same type arguments.
+  const AbstractTypeArguments& type_args = AbstractTypeArguments::Handle(
+      GetTypeArguments());
+  const AbstractTypeArguments& other_type_args = AbstractTypeArguments::Handle(
+      other.GetTypeArguments());
+  if (!type_args.Equals(other_type_args)) {
     return false;
   }
 
   const Array& other_arr = Array::Cast(other);
 
   intptr_t len = this->Length();
   if (len != other_arr.Length()) {
     return false;
   }
 
@@ skipping 198 matching lines @@
     return false;
   }
 
   const GrowableObjectArray& other_arr = GrowableObjectArray::Cast(other);
 
   // The capacity and length of both objects must be equal.
   if (Capacity() != other_arr.Capacity() || Length() != other_arr.Length()) {
     return false;
   }
 
-  // Both must have the same type arguments.
-  if (!AbstractTypeArguments::AreEqual(
-      AbstractTypeArguments::Handle(GetTypeArguments()),
-      AbstractTypeArguments::Handle(other.GetTypeArguments()))) {
+  // Both arrays must have the same type arguments.
+  const AbstractTypeArguments& type_args = AbstractTypeArguments::Handle(
+      GetTypeArguments());
+  const AbstractTypeArguments& other_type_args = AbstractTypeArguments::Handle(
+      other.GetTypeArguments());
+  if (!type_args.Equals(other_type_args)) {
     return false;
   }
 
   // The data part in both arrays must be identical.
   const Array& contents = Array::Handle(data());
   const Array& other_contents = Array::Handle(other_arr.data());
   for (intptr_t i = 0; i < Length(); i++) {
     if (contents.At(i) != other_contents.At(i)) {
       return false;
     }
@@ skipping 814 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   JSONObject jsobj(stream);
 }
 
 
 }  // namespace dart