Make cycle checking of super interfaces linear instead of quadratic by marking

runtime/vm/class_finalizer.cc

 // Copyright (c) 2013, 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/class_finalizer.h"
 
 #include "vm/code_generator.h"
 #include "vm/flags.h"
 #include "vm/heap.h"
 #include "vm/isolate.h"
@@ skipping 1389 matching lines @@
       mixin_app_class.super_type());
   ASSERT(super_type.IsResolved());
   const Class& super_class = Class::Handle(isolate, super_type.type_class());
   const intptr_t num_super_type_params = super_class.NumTypeParameters();
   const Type& mixin_type = Type::Handle(isolate, mixin_app_class.mixin());
   const Class& mixin_class = Class::Handle(isolate, mixin_type.type_class());
   const intptr_t num_mixin_type_params = mixin_class.NumTypeParameters();
   // The mixin class cannot be Object and this was checked earlier.
   ASSERT(!mixin_class.IsObjectClass());
 
-  // Add the mixin type to the interfaces that the mixin application
-  // class implements. This is necessary so that type tests work.
-  const Array& interfaces = Array::Handle(isolate, Array::New(1));
-  interfaces.SetAt(0, mixin_type);
-  ASSERT(mixin_app_class.interfaces() == Object::empty_array().raw());
-  mixin_app_class.set_interfaces(interfaces);
+  // The mixin type (in raw form) should have been added to the interfaces
+  // implemented by the mixin application class. This is necessary so that cycle
+  // check works at compile time (type arguments are ignored) and so that
+  // type tests work at runtime (by then, type arguments will have been set, see
+  // below).
+  ASSERT(mixin_app_class.interfaces() != Object::empty_array().raw());
 
   // If both the super type and the mixin type are non generic, the mixin
   // application class is non generic as well and we can skip type parameter
   // cloning.
   bool has_uninstantiated_bounds = false;
   if ((num_super_type_params + num_mixin_type_params) > 0) {
     // If the last ampersand in the name of the mixin application class is
     // doubled, the same type parameters can propagate the type arguments to
     // the super type and to the mixin type.
     bool share_type_params = false;
@@ skipping 242 matching lines @@
 
     // The mixin type and interface type must also be set before calling
     // CloneMixinAppTypeParameters.
     // After FinalizeTypesInClass, they will refer to the type parameters of
     // the mixin class typedef.
     const Type& generic_mixin_type = Type::Handle(isolate,
         Type::New(Class::Handle(isolate, aliased_mixin_type.type_class()),
                   Object::null_type_arguments(),
                   aliased_mixin_type.token_pos()));
     inserted_class.set_mixin(generic_mixin_type);
-    // The interface will be set in CloneMixinAppTypeParameters.
+    // Add the mixin type to the list of interfaces that the mixin application
+    // class implements. This is necessary so that cycle check work at
+    // compile time (type arguments are ignored by that check).
+    const Array& interfaces = Array::Handle(Array::New(1));
+    interfaces.SetAt(0, generic_mixin_type);
+    ASSERT(inserted_class.interfaces() == Object::empty_array().raw());
+    inserted_class.set_interfaces(interfaces);
+    // The type arguments of the interface, if any, will be set in
+    // CloneMixinAppTypeParameters, which is called indirectly from
+    // FinalizeTypesInClass below.
   }
 
   // Finalize the types and call CloneMixinAppTypeParameters.
   FinalizeTypesInClass(inserted_class);
 
   // The super type of this mixin application class must point to the
   // inserted class. The super type arguments are the concatenation of the
   // old super type arguments (propagating type arguments to the super class)
   // with new type arguments providing type arguments to the mixin.
   // The appended type arguments are those of the super type of the mixin
@@ skipping 757 matching lines @@
       mixin_app_class_name = Symbols::New(mixin_app_class_name);
       mixin_app_class = Class::New(mixin_app_class_name,
                                    script,
                                    mixin_type.token_pos());
       mixin_app_class.set_super_type(mixin_super_type);
       mixin_type_class = mixin_type.type_class();
       generic_mixin_type = Type::New(mixin_type_class,
                                      Object::null_type_arguments(),
                                      mixin_type.token_pos());
       mixin_app_class.set_mixin(generic_mixin_type);
+      // Add the mixin type to the list of interfaces that the mixin application
+      // class implements. This is necessary so that cycle check work at
+      // compile time (type arguments are ignored by that check).
+      const Array& interfaces = Array::Handle(Array::New(1));
+      interfaces.SetAt(0, generic_mixin_type);
+      ASSERT(mixin_app_class.interfaces() == Object::empty_array().raw());
+      mixin_app_class.set_interfaces(interfaces);
       mixin_app_class.set_is_synthesized_class();
       library.AddClass(mixin_app_class);
 
       // No need to add the new class to pending_classes, since it will be
       // processed via the super_type chain of a pending class.
 
       if (FLAG_trace_class_finalization) {
         OS::Print("Creating mixin application %s\n",
                   mixin_app_class.ToCString());
       }
@@ skipping 28 matching lines @@
 
 // Recursively walks the graph of explicitly declared super type and
 // interfaces, resolving unresolved super types and interfaces.
 // Reports an error if there is an interface reference that cannot be
 // resolved, or if there is a cycle in the graph. We detect cycles by
 // remembering interfaces we've visited in each path through the
 // graph. If we visit an interface a second time on a given path,
 // we found a loop.
 void ClassFinalizer::ResolveSuperTypeAndInterfaces(
     const Class& cls, GrowableArray<intptr_t>* visited) {
+  if (cls.is_cycle_free()) {
+    return;
+  }
   ASSERT(visited != NULL);
   if (FLAG_trace_class_finalization) {
     OS::Print("Resolving super and interfaces: %s\n", cls.ToCString());
   }
   const intptr_t cls_index = cls.id();
   for (intptr_t i = 0; i < visited->length(); i++) {
     if ((*visited)[i] == cls_index) {
       // We have already visited class 'cls'. We found a cycle.
       const String& class_name = String::Handle(cls.Name());
       const Script& script = Script::Handle(cls.script());
       ReportError(Error::Handle(),  // No previous error.
                   script, cls.token_pos(),
                   "cyclic reference found for class '%s'",
                   class_name.ToCString());
     }
   }
 
   // If the class/interface has no explicit super class/interfaces
   // and is not a mixin application, we are done.
   AbstractType& super_type = AbstractType::Handle(cls.super_type());
   Array& super_interfaces = Array::Handle(cls.interfaces());
   if ((super_type.IsNull() || super_type.IsObjectType()) &&
       (super_interfaces.Length() == 0)) {
+    cls.set_is_cycle_free();
     return;
   }
 
   if (super_type.IsMixinAppType()) {
+    // For the cycle check below to work, ResolveMixinAppType needs to set
+    // the mixin interfaces in the super classes, even if only in raw form.
+    // It is indeed too early to set the correct type arguments, which is not
+    // a problem since they are ignored in the cycle check.
     const MixinAppType& mixin_app_type = MixinAppType::Cast(super_type);
     super_type = ResolveMixinAppType(cls, mixin_app_type);
     cls.set_super_type(super_type);
   }
 
   // If cls belongs to core lib, restrictions about allowed interfaces
   // are lifted.
   const bool cls_belongs_to_core_lib = cls.library() == Library::CoreLibrary();
 
   // Resolve and check the super type and interfaces of cls.
@@ skipping 123 matching lines @@
                       String::Handle(cls.Name()).ToCString(),
                       interface_name.ToCString());
         }
       }
     }
     interface_class.set_is_implemented();
     // Now resolve the super interfaces.
     ResolveSuperTypeAndInterfaces(interface_class, visited);
   }
   visited->RemoveLast();
+  cls.set_is_cycle_free();
 }
 
 
 // A class is marked as constant if it has one constant constructor.
 // A constant class can only have final instance fields.
 // Note: we must check for cycles before checking for const properties.
 void ClassFinalizer::CheckForLegalConstClass(const Class& cls) {
   ASSERT(cls.is_const());
   const Array& fields_array = Array::Handle(cls.fields());
   intptr_t len = fields_array.Length();
@@ skipping 218 matching lines @@
   expected_name ^= String::New("_offset");
   ASSERT(String::EqualsIgnoringPrivateKey(name, expected_name));
   field ^= fields_array.At(2);
   ASSERT(field.Offset() == TypedDataView::length_offset());
   name ^= field.name();
   ASSERT(name.Equals("length"));
 #endif
 }
 
 }  // namespace dart