Second attempt at finalizing all classes in the VM (fix issue 364).

runtime/vm/class_finalizer.cc

 // Copyright (c) 2011, 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/flags.h"
 #include "vm/heap.h"
 #include "vm/isolate.h"
 #include "vm/longjump.h"
 #include "vm/object_store.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, print_classes, false, "Prints details about loaded classes.");
 DEFINE_FLAG(bool, trace_class_finalization, false, "Trace class finalization.");
+DEFINE_FLAG(bool, trace_type_finalization, false, "Trace type finalization.");
 DEFINE_FLAG(bool, verify_implements, false,
     "Verify that all classes implement their interface.");
 DECLARE_FLAG(bool, enable_type_checks);
 
 void ClassFinalizer::AddPendingClasses(
     const GrowableArray<const Class*>& classes) {
   if (!classes.is_empty()) {
     ObjectStore* object_store = Isolate::Current()->object_store();
     const Array& old_array = Array::Handle(object_store->pending_classes());
     const intptr_t old_length = old_array.Length();
@@ skipping 208 matching lines @@
     OS::PrintErr("Could not verify bootstrap classes : %s\n", err.ToCString());
     OS::Exit(255);
   }
   if (FLAG_trace_class_finalization) {
     OS::Print("VerifyBootstrapClasses END.\n");
   }
   Isolate::Current()->heap()->Verify();
 }
 
 
+// Resolve unresolved_class in the library of cls.
+RawClass* ClassFinalizer::ResolveClass(
+    const Class& cls, const UnresolvedClass& unresolved_class) {
+  Library& lib = Library::Handle();
+  if (unresolved_class.qualifier() == String::null()) {
+    lib = cls.library();
+  } else {
+    const String& qualifier = String::Handle(unresolved_class.qualifier());
+    LibraryPrefix& lib_prefix = LibraryPrefix::Handle();
+    lib_prefix = cls.LookupLibraryPrefix(qualifier);
+    if (lib_prefix.IsNull()) {
+      const Script& script = Script::Handle(cls.script());
+      ReportError(script, unresolved_class.token_index(),
+                  "cannot resolve library prefix '%s' from '%s'.\n",
+                  String::Handle(unresolved_class.Name()).ToCString(),
+                  String::Handle(cls.Name()).ToCString());
+    }
+    lib = lib_prefix.library();
+  }
+  ASSERT(!lib.IsNull());
+  const String& class_name = String::Handle(unresolved_class.ident());
+  const Class& resolved_class = Class::Handle(lib.LookupClass(class_name));
+  if (resolved_class.IsNull()) {
+    const Script& script = Script::Handle(cls.script());
+    ReportError(script, unresolved_class.token_index(),
+                "cannot resolve class name '%s' from '%s'.\n",
+                String::Handle(unresolved_class.Name()).ToCString(),
+                String::Handle(cls.Name()).ToCString());
+  }
+  return resolved_class.raw();
+}
+
+
 // Resolve unresolved superclasses (String -> Class).
 void ClassFinalizer::ResolveSuperClass(const Class& cls) {
   if (cls.is_finalized()) {
     return;
   }
   Type& super_type = Type::Handle(cls.super_type());
   if (super_type.IsNull()) {
     return;
   }
   // Resolve failures lead to a longjmp.
   super_type = ResolveType(cls, super_type);
+  if (super_type.IsTypeParameter()) {
+    String& class_name = String::Handle(cls.Name());
+    String& type_parameter_name = String::Handle(super_type.Name());
+    ReportError("'%s' cannot extend or implement type parameter '%s'.\n",
+                class_name.ToCString(),
+                type_parameter_name.ToCString());
+  }
   cls.set_super_type(super_type);
   const Class& super_class = Class::Handle(super_type.type_class());
   if (cls.is_interface() != super_class.is_interface()) {
     String& class_name = String::Handle(cls.Name());
     String& super_class_name = String::Handle(super_class.Name());
     ReportError("class '%s' and superclass '%s' are not "
                 "both classes or both interfaces.\n",
                 class_name.ToCString(),
                 super_class_name.ToCString());
   }
@@ skipping 53 matching lines @@
     ReportError("default clause of interface '%s' does not name a class\n",
                 interface_name.ToCString());
   }
 }
 
 
 RawType* ClassFinalizer::ResolveType(const Class& cls, const Type& type) {
   if (type.IsResolved()) {
     return type.raw();
   }
+  if (FLAG_trace_type_finalization) {
+    OS::Print("Resolve type '%s'\n", String::Handle(type.Name()).ToCString());
+  }
 
   // Resolve the type class.
   if (!type.HasResolvedTypeClass()) {
     const UnresolvedClass& unresolved_class =
         UnresolvedClass::Handle(type.unresolved_class());
     const String& type_class_name = String::Handle(unresolved_class.ident());
 
     // The type class name may be a type parameter of cls that was not resolved
     // by the parser because it appeared as part of the declaration
     // as T1 in B<T1, T2 extends A<T1>> or
     // as T2 in B<T1 extends A<T2>, T2>>.
     const TypeParameter& type_parameter = TypeParameter::Handle(
         cls.LookupTypeParameter(type_class_name));
     if (!type_parameter.IsNull()) {
       // No need to check for proper instance scoping, since another type
       // parameter must be involved for the type to still be unresolved.
       // The scope checking was performed for the other type parameter already.
 
       // A type parameter cannot be parameterized, so report an error if type
       // arguments have previously been parsed.
       if (type.arguments() != TypeArguments::null()) {
         ReportError("type parameter '%s' cannot be parameterized",
                     type_class_name.ToCString());
       }
       return type_parameter.raw();
     }
 
     // Lookup the type class.
-    Class& type_class = Class::Handle();
-    Library& lib = Library::Handle();
-    if (unresolved_class.qualifier() == String::null()) {
-      lib = cls.library();
-    } else {
-      const String& qualifier = String::Handle(unresolved_class.qualifier());
-      LibraryPrefix& lib_prefix = LibraryPrefix::Handle();
-      lib_prefix = cls.LookupLibraryPrefix(qualifier);
-      if (lib_prefix.IsNull()) {
-        const Script& script = Script::Handle(cls.script());
-        ReportError(script, unresolved_class.token_index(),
-                    "cannot resolve name '%s'\n",
-                    String::Handle(unresolved_class.Name()).ToCString());
-      }
-      lib = lib_prefix.library();
-    }
-    ASSERT(!lib.IsNull());
-    type_class = lib.LookupClass(type_class_name);
-    if (type_class.IsNull()) {
-      const Script& script = Script::Handle(cls.script());
-      ReportError(script, unresolved_class.token_index(),
-                  "cannot resolve class name '%s' from '%s'\n",
-                  String::Handle(unresolved_class.Name()).ToCString(),
-                  String::Handle(cls.Name()).ToCString());
-    }
+    const Class& type_class =
+        Class::Handle(ResolveClass(cls, unresolved_class));
+
     // Replace unresolved class with resolved type class.
     ASSERT(type.IsParameterizedType());
     ParameterizedType& parameterized_type = ParameterizedType::Handle();
     parameterized_type ^= type.raw();
     parameterized_type.set_type_class(Object::Handle(type_class.raw()));
   }
 
   // Resolve type arguments, if any.
   const TypeArguments& arguments = TypeArguments::Handle(type.arguments());
   if (!arguments.IsNull()) {
@@ skipping 19 matching lines @@
 // Example:
 //   Declared: class C<K, V> extends B<V> { ... }
 //             class B<T> extends Array<int> { ... }
 //   Input:    C<String, double> expressed as
 //             cls = C, arguments = [null, null, String, double],
 //             i.e. cls_args = [String, double], offset = 2, length = 2.
 //   Output:   arguments = [int, double, String, double]
 void ClassFinalizer::FinalizeTypeArguments(const Class& cls,
                                            const TypeArguments& arguments) {
   ASSERT(arguments.Length() >= cls.NumTypeArguments());
-  // If type checks are enabled, verify the subtyping constraints.
-  if (FLAG_enable_type_checks) {
-    const intptr_t num_type_params = cls.NumTypeParameters();
-    const intptr_t offset = cls.NumTypeArguments() - num_type_params;
-    Type& type = Type::Handle();
-    Type& type_extends = Type::Handle();
-    const TypeArguments& extends_array =
-        TypeArguments::Handle(cls.type_parameter_extends());
-    ASSERT((extends_array.IsNull() && (num_type_params == 0)) ||
-           (extends_array.Length() == num_type_params));
-    for (intptr_t i = 0; i < num_type_params; i++) {
-      type_extends = extends_array.TypeAt(i);
-      if (!type_extends.IsDynamicType()) {
-        type = arguments.TypeAt(offset + i);
-        if (type.IsInstantiated()) {
-          if (!type_extends.IsInstantiated()) {
-            type_extends = type_extends.InstantiateFrom(arguments, offset);
-          }
-          // TODO(regis): Where do we check the constraints when the type is
-          // generic?
-          if (!type.IsSubtypeOf(type_extends)) {
-            const String& type_name = String::Handle(type.Name());
-            const String& extends_name = String::Handle(type_extends.Name());
-            ReportError("type argument '%s' does not extend type '%s'\n",
-                        type_name.ToCString(),
-                        extends_name.ToCString());
-          }
-        }
-      }
-    }
-  }
   Type& super_type = Type::Handle(cls.super_type());
   if (!super_type.IsNull()) {
     super_type = FinalizeType(super_type);
     cls.set_super_type(super_type);
     const Class& super_class = Class::Handle(super_type.type_class());
     const TypeArguments& super_type_args =
         TypeArguments::Handle(super_type.arguments());
     const intptr_t num_super_type_params = super_class.NumTypeParameters();
     const intptr_t offset = super_class.NumTypeArguments();
     const intptr_t super_offset = offset - num_super_type_params;
     ASSERT(offset == (cls.NumTypeArguments() - cls.NumTypeParameters()));
     Type& super_type_arg = Type::Handle();
     for (intptr_t i = 0; i < num_super_type_params; i++) {
       super_type_arg = super_type_args.TypeAt(super_offset + i);
       if (!super_type_arg.IsInstantiated()) {
         super_type_arg = super_type_arg.InstantiateFrom(arguments, offset);
       }
       super_type_arg = super_type_arg.Canonicalize();
       arguments.SetTypeAt(super_offset + i, super_type_arg);
     }
     FinalizeTypeArguments(super_class, arguments);
   }
 }
 
 
+// Verify the upper bounds of the type arguments of class cls.
+void ClassFinalizer::VerifyUpperBounds(const Class& cls,
+                                       const TypeArguments& arguments) {
+  ASSERT(FLAG_enable_type_checks);
+  ASSERT(arguments.Length() >= cls.NumTypeArguments());
+  const intptr_t num_type_params = cls.NumTypeParameters();
+  const intptr_t offset = cls.NumTypeArguments() - num_type_params;
+  Type& type = Type::Handle();
+  Type& type_extends = Type::Handle();
+  const TypeArguments& extends_array =
+      TypeArguments::Handle(cls.type_parameter_extends());
+  ASSERT((extends_array.IsNull() && (num_type_params == 0)) ||
+         (extends_array.Length() == num_type_params));
+  for (intptr_t i = 0; i < num_type_params; i++) {
+    type_extends = extends_array.TypeAt(i);
+    if (!type_extends.IsDynamicType()) {
+      type = arguments.TypeAt(offset + i);
+      if (type.IsInstantiated()) {
+        if (!type_extends.IsInstantiated()) {
+          type_extends = type_extends.InstantiateFrom(arguments, offset);
+        }
+        // TODO(regis): Where do we check the constraints when the type is
+        // generic?
+        if (!type.IsSubtypeOf(type_extends)) {
+          const String& type_name = String::Handle(type.Name());
+          const String& extends_name = String::Handle(type_extends.Name());
+          ReportError("type argument '%s' of class '%s' "
+                      "does not extend type '%s'\n",
+                      type_name.ToCString(),
+                      extends_name.ToCString());
+        }
+      }
+    }
+  }
+  Type& super_type = Type::Handle(cls.super_type());
+  if (!super_type.IsNull()) {
+    ASSERT(super_type.IsFinalized());
+    const Class& super_class = Class::Handle(super_type.type_class());
+    VerifyUpperBounds(super_class, arguments);
+  }
+}
+
+
 RawType* ClassFinalizer::FinalizeType(const Type& type) {
   ASSERT(type.IsResolved());
   if (type.IsFinalized()) {
     return type.raw();
   }
+  if (FLAG_trace_type_finalization) {
+    OS::Print("Finalize type '%s'\n", String::Handle(type.Name()).ToCString());
+  }
 
   // At this point, we can only have a parameterized_type.
   ParameterizedType& parameterized_type = ParameterizedType::Handle();
   parameterized_type ^= type.raw();
 
   if (parameterized_type.IsBeingFinalized()) {
     ReportError("type '%s' illegally refers to itself\n",
                 String::Handle(parameterized_type.Name()).ToCString());
   }
 
   // Mark type as being finalized in order to detect illegal self reference.
   parameterized_type.set_is_being_finalized();
 
   // Finalize the current type arguments of the type, which are still the
   // parsed type arguments.
   TypeArguments& arguments =
       TypeArguments::Handle(parameterized_type.arguments());
   if (!arguments.IsNull()) {
     intptr_t num_arguments = arguments.Length();
     for (intptr_t i = 0; i < num_arguments; i++) {
       Type& type_argument = Type::Handle(arguments.TypeAt(i));
       type_argument = FinalizeType(type_argument);
       arguments.SetTypeAt(i, type_argument);
     }
   }
 
   // The type class does not need to be finalized in order to finalize the type,
-  // however, it must at least be resolved. This was done as part of resolving
-  // the type itself.
+  // however, it must at least be resolved (this was done as part of resolving
+  // the type itself, a precondition to calling FinalizeType) and the upper
+  // bounds of its type parameters must be finalized (done here).
   Class& type_class = Class::Handle(parameterized_type.type_class());
 
+  // If the type class is a signature class, we are finalizing its signature
+  // type, thereby finalizing the result type and parameter types of its
+  // signature function.
+  // Do this before marking this type as finalized in order to detect cycles.
+  if (type_class.IsSignatureClass()) {
+    // Signature classes are finalized upon creation.
+    ASSERT(type_class.is_finalized());
+    // Resolve and finalize the result and parameter types of the signature
+    // function of this signature class.
+    ResolveAndFinalizeSignature(
+        type_class, Function::Handle(type_class.signature_function()));
+  }
+
   // The finalized type argument vector needs num_type_arguments types.
   const intptr_t num_type_arguments = type_class.NumTypeArguments();
   // The type class has num_type_parameters type parameters.
   const intptr_t num_type_parameters = type_class.NumTypeParameters();
 
   // Initialize the type argument vector.
   // Check the number of parsed type arguments, if any.
   // Specifying no type arguments indicates a raw type, which is not an error.
   // However, subtyping constraints are checked below, even for a raw type.
   if (!arguments.IsNull() && (arguments.Length() != num_type_parameters)) {
@@ skipping 12 matching lines @@
     const intptr_t offset = num_type_arguments - num_type_parameters;
     Type& type = Type::Handle(Type::DynamicType());
     for (intptr_t i = 0; i < num_type_parameters; i++) {
       // If no type parameters were provided, a raw type is desired, so we
       // create a vector of DynamicType.
       if (!arguments.IsNull()) {
         type = arguments.TypeAt(i);
       }
       full_arguments.SetTypeAt(offset + i, type);
     }
-    FinalizeTypeArguments(type_class, full_arguments);
+    if (type_class.IsSignatureClass()) {
+      const Function& signature_fun =
+          Function::Handle(type_class.signature_function());
+      ASSERT(!signature_fun.is_static());
+      const Class& signature_fun_owner = Class::Handle(signature_fun.owner());
+      FinalizeTypeArguments(signature_fun_owner, full_arguments);
+    } else {
+      FinalizeTypeArguments(type_class, full_arguments);
+    }
     parameterized_type.set_arguments(full_arguments);
+
+    // Mark the type as finalized before finalizing the upper bounds, because
+    // cycles via upper bounds are legal at compile time.
+    parameterized_type.set_is_finalized();
+
+    ResolveAndFinalizeUpperBounds(type_class);
+    if (FLAG_enable_type_checks) {
+      VerifyUpperBounds(type_class, full_arguments);
+    }
+  } else {
+    parameterized_type.set_is_finalized();
   }
-
-  // If the type is a function type, finalize the result and parameter types.
-  if (type_class.IsSignatureClass()) {
-    ResolveAndFinalizeSignature(
-        type_class, Function::Handle(type_class.signature_function()));
-  }
-
-  parameterized_type.set_is_finalized();
   return parameterized_type.Canonicalize();
 }
 
 
 RawType* ClassFinalizer::FinalizeAndCanonicalizeType(const Type& type,
                                                      String* errmsg) {
   Isolate* isolate = Isolate::Current();
   ASSERT(isolate != NULL);
   LongJump* base = isolate->long_jump_base();
   LongJump jump;
   isolate->set_long_jump_base(&jump);
   if (setjmp(*jump.Set()) == 0) {
     const Type& canonical_type = Type::Handle(FinalizeType(type));
     isolate->set_long_jump_base(base);
     *errmsg = String::null();
     return canonical_type.raw();
   } else {
     // Error occured: Get the error message.
     isolate->set_long_jump_base(base);
     *errmsg = isolate->object_store()->sticky_error();
     return type.raw();
   }
   UNREACHABLE();
   return Type::null();
 }
 
 
-// Top level function signatures are canonicalized, added to the library class
-// dictionary, and finalized with other library classes and interfaces.
-// Function signatures used as type of a local variable or of a local function
-// are canonicalized and finalized upon creation, since all the types they
-// reference are already resolved.
 void ClassFinalizer::ResolveAndFinalizeSignature(const Class& cls,
                                                  const Function& function) {
   // Resolve result type.
   Type& type = Type::Handle(function.result_type());
   type = ResolveType(cls, type);
   function.set_result_type(type);
   type = FinalizeType(type);
   function.set_result_type(type);
   // Resolve formal parameter types.
   const intptr_t num_parameters = function.NumberOfParameters();
@@ skipping 39 matching lines @@
     function = super_class.LookupFunction(name);
     if (!function.IsNull()) {
       return super_class.raw();
     }
     super_class = super_class.SuperClass();
   }
   return Class::null();
 }
 
 
+// Resolve and finalize the upper bounds of the type parameters of class cls.
+void ClassFinalizer::ResolveAndFinalizeUpperBounds(const Class& cls) {
+  const intptr_t num_type_params = cls.NumTypeParameters();
+  Type& type_extends = Type::Handle();
+  const TypeArguments& extends_array =
+      TypeArguments::Handle(cls.type_parameter_extends());
+  ASSERT((extends_array.IsNull() && (num_type_params == 0)) ||
+         (extends_array.Length() == num_type_params));
+  for (intptr_t i = 0; i < num_type_params; i++) {
+    type_extends = extends_array.TypeAt(i);
+    type_extends = ResolveType(cls, type_extends);
+    extends_array.SetTypeAt(i, type_extends);
+    type_extends = FinalizeType(type_extends);
+    extends_array.SetTypeAt(i, type_extends);
+  }
+}
+
+
 void ClassFinalizer::ResolveAndFinalizeMemberTypes(const Class& cls) {
   // Note that getters and setters are explicitly listed as such in the list of
   // functions of a class, so we do not need to consider fields as implicitly
   // generating getters and setters.
   // The only compile errors we report are therefore:
   // - a getter having the same name as a method (but not a getter) in a super
   //   class or in a subclass.
   // - a setter having the same name as a method (but not a setter) in a super
   //   class or in a subclass.
   // - a static field, instance field, or static method (but not an instance
@@ skipping 113 matching lines @@
         const String& super_class_name = String::Handle(super_class.Name());
         ReportError("function '%s' of class '%s' conflicts with "
                     "setter '%s' of super class '%s'.\n",
                     function_name.ToCString(),
                     class_name.ToCString(),
                     function_name.ToCString(),
                     super_class_name.ToCString());
       }
     }
   }
-  // Resolve the signature type if this class is a signature class.
-  if (cls.IsSignatureClass()) {
-    Type& signature_type = Type::Handle(cls.SignatureType());
-    signature_type = FinalizeType(signature_type);
-    // Signature types are canonicalized by default.
-    ASSERT(signature_type.raw() == cls.SignatureType());
-  }
 }
 
 
 void ClassFinalizer::FinalizeClass(const Class& cls) {
   if (cls.is_finalized()) {
     return;
   }
   if (FLAG_trace_class_finalization) {
     OS::Print("Finalize %s\n", cls.ToCString());
   }
+  // Signature classes are finalized upon creation.
+  ASSERT(!cls.IsSignatureClass());
   if (!IsSuperCycleFree(cls)) {
     const String& name = String::Handle(cls.Name());
     ReportError("class '%s' has a cycle in its superclass relationship.\n",
                 name.ToCString());
   }
   GrowableArray<const Class*> visited;
   ResolveInterfaces(cls, &visited);
   Type& super_type = Type::Handle(cls.super_type());
   if (!super_type.IsNull()) {
     const Class& super_class = Class::Handle(super_type.type_class());
@@ skipping 19 matching lines @@
     }
   }
   // Finalize interface types (but not necessarily interface classes).
   Array& interface_types = Array::Handle(cls.interfaces());
   Type& interface_type = Type::Handle();
   for (intptr_t i = 0; i < interface_types.Length(); i++) {
     interface_type ^= interface_types.At(i);
     interface_type = FinalizeType(interface_type);
     interface_types.SetAt(i, interface_type);
   }
-  // Mark as finalized before resolving member types in order to break cycles.
+  // Mark as finalized before resolving type parameter upper bounds and member
+  // types in order to break cycles.
   cls.Finalize();
+  ResolveAndFinalizeUpperBounds(cls);
   ResolveAndFinalizeMemberTypes(cls);
   // Run additional checks after all types are finalized.
   if (cls.is_const()) {
     CheckForLegalConstClass(cls);
   }
 }
 
 
 bool ClassFinalizer::IsSuperCycleFree(const Class& cls) {
   Class& test1 = Class::Handle(cls.raw());
@@ skipping 109 matching lines @@
           interface.IsNumberInterface() ||
           interface.IsIntInterface() ||
           interface.IsDoubleInterface() ||
           interface.IsStringInterface() ||
           (interface.IsFunctionInterface() && !cls.IsSignatureClass()) ||
           interface.IsDynamicType()) {
         ReportError("'%s' is not allowed to extend or implement '%s'\n",
                     String::Handle(cls.Name()).ToCString(),
                     String::Handle(interface_class.Name()).ToCString());
       }
-      // TODO(regis): We also need to prevent extending classes Smi, Mint,
-      // BigInt, Double, OneByteString, TwoByteString, FourByteString.
     }
     // Now resolve the super interfaces.
     ResolveInterfaces(interface_class, visited);
   }
   visited->RemoveLast();
 }
 
 
 // A class is marked as constant if it has one constant constructor.
 // A constant class:
@@ skipping 105 matching lines @@
   ASSERT(msg_buffer != NULL);
   va_list args;
   va_start(args, format);
   OS::VSNPrint(msg_buffer, kBufferLength, format, args);
   va_end(args);
   isolate->long_jump_base()->Jump(1, msg_buffer);
   UNREACHABLE();
 }
 
 }  // namespace dart