Fix finalization of recursive type graph with bounds (issue 25389).

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 3858 matching lines @@
     Array& interfaces = Array::Handle(zone, thsi.interfaces());
     AbstractType& interface = AbstractType::Handle(zone);
     Class& interface_class = Class::Handle(zone);
     TypeArguments& interface_args = TypeArguments::Handle(zone);
     Error& error = Error::Handle(zone);
     for (intptr_t i = 0; i < interfaces.Length(); i++) {
       interface ^= interfaces.At(i);
       if (!interface.IsFinalized()) {
         // We may be checking bounds at finalization time and can encounter
         // a still unfinalized interface.
+        if (interface.IsBeingFinalized()) {
+          // Interface is part of a still unfinalized recursive type graph.
+          // Skip it. The caller will create a bounded type to be checked at
+          // runtime if this type test returns false at compile time.
+          continue;
+        }
         ClassFinalizer::FinalizeType(
             thsi, interface, ClassFinalizer::kCanonicalize);
         interfaces.SetAt(i, interface);
       }
       if (interface.IsMalbounded()) {
         // Return the first bound error to the caller if it requests it.
         if ((bound_error != NULL) && bound_error->IsNull()) {
           *bound_error = interface.error();
         }
         continue;  // Another interface may work better.
@@ skipping 11617 matching lines @@
     // Build the bound name without causing divergence.
     const AbstractType& bound = AbstractType::Handle(
         zone, BoundedType::Cast(*this).bound());
     String& bound_name = String::Handle(zone);
     if (bound.IsTypeParameter()) {
       bound_name = TypeParameter::Cast(bound).name();
       pieces.Add(bound_name);
     } else if (bound.IsType()) {
       const Class& cls = Class::Handle(zone, Type::Cast(bound).type_class());
       bound_name = cls.Name();
+      pieces.Add(bound_name);
       if (Type::Cast(bound).arguments() != TypeArguments::null()) {
-        pieces.Add(bound_name);
         pieces.Add(Symbols::OptimizedOut());
       }
     } else {
       pieces.Add(Symbols::OptimizedOut());
     }
     return Symbols::FromConcatAll(pieces);
   }
   if (IsTypeParameter()) {
     return TypeParameter::Cast(*this).name();
   }
@@ skipping 192 matching lines @@
     ASSERT(Isolate::Current()->flags().type_checks());
     if ((bound_error != NULL) && bound_error->IsNull()) {
       *bound_error = other.error();
     }
     return false;
   }
   if (IsBoundedType() || other.IsBoundedType()) {
     if (Equals(other)) {
       return true;
     }
+    // Redundant check if other type is equal to the upper bound of this type.
+    if (IsBoundedType() &&
+        AbstractType::Handle(BoundedType::Cast(*this).bound()).Equals(other)) {
+      return true;
+    }
     return false;  // TODO(regis): We should return "maybe after instantiation".
   }
   // Type parameters cannot be handled by Class::TypeTest().
   // When comparing two uninstantiated function types, one returning type
   // parameter K, the other returning type parameter V, we cannot assume that K
   // is a subtype of V, or vice versa. We only return true if K equals V, as
   // defined by TypeParameter::Equals.
   // The same rule applies when checking the upper bound of a still
   // uninstantiated type at compile time. Returning false will defer the test
   // to run time.
@@ skipping 397 matching lines @@
   if (from_index > 0) {
     // Verify that the type arguments of the super class match, since they
     // depend solely on the type parameters that were just verified to match.
     ASSERT(type_args.Length() >= (from_index + num_type_params));
     ASSERT(other_type_args.Length() >= (from_index + num_type_params));
     AbstractType& type_arg = AbstractType::Handle(zone);
     AbstractType& other_type_arg = AbstractType::Handle(zone);
     for (intptr_t i = 0; i < from_index; i++) {
       type_arg = type_args.TypeAt(i);
       other_type_arg = other_type_args.TypeAt(i);
+      // Ignore bounds of bounded types.
+      while (type_arg.IsBoundedType()) {
+        type_arg = BoundedType::Cast(type_arg).type();
+      }
+      while (other_type_arg.IsBoundedType()) {
+        other_type_arg = BoundedType::Cast(other_type_arg).type();
+      }
       ASSERT(type_arg.IsEquivalent(other_type_arg, trail));
     }
   }
 #endif
   return true;
 }
 
 
 bool Type::IsRecursive() const {
   return TypeArguments::Handle(arguments()).IsRecursive();
@@ skipping 809 matching lines @@
     ASSERT(!upper_bound.IsObjectType() && !upper_bound.IsDynamicType());
     const TypeParameter& type_param = TypeParameter::Handle(type_parameter());
     if (!upper_bound.IsInstantiated()) {
       upper_bound = upper_bound.InstantiateFrom(instantiator_type_arguments,
                                                 bound_error,
                                                 trail,
                                                 space);
       // Instantiated upper_bound may not be finalized. See comment above.
     }
     if (bound_error->IsNull()) {
-      if (!type_param.CheckBound(bounded_type, upper_bound, bound_error) &&
-          bound_error->IsNull()) {
+      if (bounded_type.IsBeingFinalized() ||
+          upper_bound.IsBeingFinalized() ||
+          (!type_param.CheckBound(bounded_type, upper_bound, bound_error) &&
+           bound_error->IsNull())) {
         // We cannot determine yet whether the bounded_type is below the
-        // upper_bound, because one or both of them is still uninstantiated.
-        ASSERT(!bounded_type.IsInstantiated() || !upper_bound.IsInstantiated());
-        // Postpone bound check by returning a new BoundedType with partially
-        // instantiated bounded_type and upper_bound, but keeping type_param.
+        // upper_bound, because one or both of them is still being finalized or
+        // uninstantiated.
+        ASSERT(bounded_type.IsBeingFinalized() ||
+               upper_bound.IsBeingFinalized() ||
+               !bounded_type.IsInstantiated() ||
+               !upper_bound.IsInstantiated());
+        // Postpone bound check by returning a new BoundedType with unfinalized
+        // or partially instantiated bounded_type and upper_bound, but keeping
+        // type_param.
         bounded_type = BoundedType::New(bounded_type, upper_bound, type_param);
       }
     }
   }
   return bounded_type.raw();
 }
 
 
 RawAbstractType* BoundedType::CloneUnfinalized() const {
   if (IsFinalized()) {
@@ skipping 5040 matching lines @@
   return tag_label.ToCString();
 }
 
 
 void UserTag::PrintJSONImpl(JSONStream* stream, bool ref) const {
   Instance::PrintJSONImpl(stream, ref);
 }
 
 
 }  // namespace dart