Implement latest rules prohibiting some self referencing typedefs.

runtime/vm/class_finalizer.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/class_finalizer.h"
 
 #include "vm/flags.h"
 #include "vm/heap.h"
 #include "vm/isolate.h"
 #include "vm/longjump.h"
@@ skipping 545 matching lines @@
 //   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 AbstractTypeArguments& arguments,
     FinalizationKind finalization) {
   ASSERT(arguments.Length() >= cls.NumTypeArguments());
   if (!cls.is_finalized()) {
-    const GrowableObjectArray& visited =
-      GrowableObjectArray::Handle(GrowableObjectArray::New());
-    ResolveInterfaces(cls, visited);
+    GrowableArray<intptr_t> visited_interfaces;
+    ResolveInterfaces(cls, &visited_interfaces);
     FinalizeTypeParameters(cls);
   }
   Type& super_type = Type::Handle(cls.super_type());
   if (!super_type.IsNull()) {
     const Class& super_class = Class::Handle(super_type.type_class());
     AbstractTypeArguments& super_type_args = AbstractTypeArguments::Handle();
     if (super_type.IsBeingFinalized()) {
       // This type references itself via its type arguments. This is legal, but
       // we must avoid endless recursion. We therefore map the innermost
       // super type to Dynamic.
@@ skipping 83 matching lines @@
   // Mark type as being finalized in order to detect illegal self reference.
   parameterized_type.set_is_being_finalized();
 
   // 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, a precondition to calling FinalizeType).
   // Also, the interfaces of the type class must be resolved and the type
   // parameters of the type class must be finalized.
   Class& type_class = Class::Handle(parameterized_type.type_class());
   if (!type_class.is_finalized()) {
-    const GrowableObjectArray& visited =
-      GrowableObjectArray::Handle(GrowableObjectArray::New());
-    ResolveInterfaces(type_class, visited);
+    GrowableArray<intptr_t> visited_interfaces;
+    ResolveInterfaces(type_class, &visited_interfaces);
     FinalizeTypeParameters(type_class);
   }
 
   // Finalize the current type arguments of the type, which are still the
   // parsed type arguments.
   AbstractTypeArguments& arguments =
       AbstractTypeArguments::Handle(parameterized_type.arguments());
   if (!arguments.IsNull()) {
     intptr_t num_arguments = arguments.Length();
     for (intptr_t i = 0; i < num_arguments; i++) {
@@ skipping 60 matching lines @@
         // FinalizeTypeArguments can modify 'full_arguments',
         // canonicalize afterwards.
         full_arguments ^= full_arguments.Canonicalize();
       }
       parameterized_type.set_arguments(full_arguments);
     } else {
       ASSERT(full_arguments.IsNull());  // Use null vector for raw type.
     }
   }
 
-  // Illegally self referencing types may get finalized indirectly.
-  if (parameterized_type.IsFinalized()) {
-    ASSERT(parameterized_type.IsMalformed());
-  } else {
+  // Self referencing types may get finalized indirectly.
+  if (!parameterized_type.IsFinalized()) {
     // Mark the type as finalized.
     if (parameterized_type.IsInstantiated()) {
       parameterized_type.set_is_finalized_instantiated();
     } else {
       parameterized_type.set_is_finalized_uninstantiated();
     }
   }
 
   // Upper bounds of the finalized type arguments are only verified in checked
   // mode, since bound errors are never reported by the vm in production mode.
@@ skipping 15 matching lines @@
       // when finalizing the malformed type.
       FinalizeMalformedType(
           malformed_error,
           cls, parameterized_type, kFinalize,
           "type arguments of type '%s' are not within bounds",
           String::Handle(parameterized_type.Name()).ToCString());
       return parameterized_type.raw();
     }
   }
 
-  // If the type class is a signature class, we also finalize its signature
-  // type, thereby finalizing the result type and parameter types of its
-  // signature function.
+  // If the type class is a signature class, we are currently finalizing a
+  // signature type, i.e. finalizing the result type and parameter types of the
+  // signature function of this signature type.
   // We do this after marking this type as finalized in order to allow a
   // function type to refer to itself via its parameter types and result type.
   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()));
+    // Signature classes are finalized upon creation, except function type
+    // aliases.
+    if (type_class.IsCanonicalSignatureClass()) {
+      ASSERT(type_class.is_finalized());
+      // Resolve and finalize the result and parameter types of the signature
+      // function of this signature class.
+      ASSERT(type_class.SignatureType() == type.raw());
+      ResolveAndFinalizeSignature(
+          type_class, Function::Handle(type_class.signature_function()));
+    } else {
+      // This type is a function type alias. Its class may need to be finalized
+      // and checked for illegal self reference.
+      FinalizeClass(type_class, false);
+      // Finalizing the signature function here (as in the canonical case above)
+      // would not mark the canonical signature type as finalized.
+      const Type& signature_type = Type::Handle(type_class.SignatureType());
+      FinalizeType(cls, signature_type, finalization);
+    }
   }
 
   return parameterized_type.Canonicalize();
 }
 
 
 void ClassFinalizer::ResolveAndFinalizeSignature(const Class& cls,
                                                  const Function& function) {
   // Resolve result type.
   AbstractType& type = AbstractType::Handle(function.result_type());
@@ skipping 236 matching lines @@
 }
 
 
 void ClassFinalizer::FinalizeClass(const Class& cls, bool generating_snapshot) {
   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());
     const Script& script = Script::Handle(cls.script());
     ReportError(script, cls.token_index(),
                 "class '%s' has a cycle in its superclass relationship",
                 name.ToCString());
   }
-  const GrowableObjectArray& visited =
-      GrowableObjectArray::Handle(GrowableObjectArray::New());
-  ResolveInterfaces(cls, visited);
+  GrowableArray<intptr_t> visited_interfaces;
+  ResolveInterfaces(cls, &visited_interfaces);
   // Finalize super class.
   const Class& super_class = Class::Handle(cls.SuperClass());
   if (!super_class.IsNull()) {
     FinalizeClass(super_class, generating_snapshot);
   }
   // Finalize type parameters before finalizing the super type.
   FinalizeTypeParameters(cls);
   // Finalize super type.
   Type& super_type = Type::Handle(cls.super_type());
   if (!super_type.IsNull()) {
     super_type ^= FinalizeType(cls, super_type, kFinalizeWellFormed);
     cls.set_super_type(super_type);
   }
+  // Signature classes are finalized upon creation, except function type
+  // aliases.
+  if (cls.IsSignatureClass()) {
+    ASSERT(!cls.IsCanonicalSignatureClass());
+    // Check for illegal self references.
+    GrowableArray<intptr_t> visited_aliases;
+    if (!IsAliasCycleFree(cls, &visited_aliases)) {
+      const String& name = String::Handle(cls.Name());
+      const Script& script = Script::Handle(cls.script());
+      ReportError(script, cls.token_index(),
+                  "typedef '%s' illegally refers to itself",
+                  name.ToCString());
+    }
+    // TODO(regis): Also check this: "It is a compile-time error if any default
+    // values are specified in the signature of a function type alias".
+    cls.Finalize();
+    return;
+  }
   // Finalize factory class, if any.
   if (cls.is_interface()) {
     if (cls.HasFactoryClass()) {
       const Class& factory_class = Class::Handle(cls.FactoryClass());
       if (!factory_class.is_finalized()) {
         FinalizeClass(factory_class, generating_snapshot);
         // Finalizing the factory class may indirectly finalize this interface.
         if (cls.is_finalized()) {
           return;
         }
@@ skipping 49 matching lines @@
     test2 = test2.SuperClass();
     if (!test2.IsNull()) {
       test2 = test2.SuperClass();
     }
   }
   // No cycles.
   return true;
 }
 
 
+// Returns false if the function type alias illegally refers to itself.
+bool ClassFinalizer::IsAliasCycleFree(const Class& cls,
+                                      GrowableArray<intptr_t>* visited) {
+  ASSERT(cls.IsSignatureClass());
+  ASSERT(!cls.IsCanonicalSignatureClass());
+  ASSERT(!cls.is_finalized());
+  ASSERT(visited != NULL);
+  const intptr_t cls_index = cls.index();
+  for (int i = 0; i < visited->length(); i++) {
+    if ((*visited)[i] == cls_index) {
+      // We have already visited alias 'cls'. We found a cycle.
+      return false;
+    }
+  }
+
+  // Visit the result type and parameter types of this signature type.
+  visited->Add(cls.index());
+  const Function& function = Function::Handle(cls.signature_function());
+  // Check class of result type.
+  AbstractType& type = AbstractType::Handle(function.result_type());
+  ResolveType(cls, type, kFinalize);
+  if (type.IsType() && !type.IsMalformed()) {
+    const Class& type_class = Class::Handle(type.type_class());
+    if (!type_class.is_finalized() &&
+        type_class.IsSignatureClass() &&
+        !type_class.IsCanonicalSignatureClass()) {
+      if (!IsAliasCycleFree(type_class, visited)) {
+        return false;
+      }
+    }
+  }
+  // Check classes of formal parameter types.
+  const intptr_t num_parameters = function.NumberOfParameters();
+  for (intptr_t i = 0; i < num_parameters; i++) {
+    type = function.ParameterTypeAt(i);
+    ResolveType(cls, type, kFinalize);
+    if (type.IsType() && !type.IsMalformed()) {
+      const Class& type_class = Class::Handle(type.type_class());
+      if (!type_class.is_finalized() &&
+          type_class.IsSignatureClass() &&
+          !type_class.IsCanonicalSignatureClass()) {
+        if (!IsAliasCycleFree(type_class, visited)) {
+          return false;
+        }
+      }
+    }
+  }
+  visited->RemoveLast();
+  return true;
+}
+
+
 bool ClassFinalizer::AddInterfaceIfUnique(
     const GrowableObjectArray& interface_list,
     const AbstractType& interface,
     AbstractType* conflicting) {
   String& interface_class_name = String::Handle(interface.ClassName());
   String& existing_interface_class_name = String::Handle();
   String& interface_name = String::Handle();
   String& existing_interface_name = String::Handle();
   AbstractType& other_interface = AbstractType::Handle();
   for (intptr_t i = 0; i < interface_list.Length(); i++) {
@@ skipping 18 matching lines @@
 
 
 // Walks the graph of explicitly declared interfaces of classes and
 // interfaces recursively. Resolves unresolved interfaces.
 // Returns false 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::ResolveInterfaces(const Class& cls,
-                                       const GrowableObjectArray& visited) {
-  ASSERT(!visited.IsNull());
-  Class& visited_cls = Class::Handle();
-  for (int i = 0; i < visited.Length(); i++) {
-    visited_cls ^= visited.At(i);
-    if (visited_cls.raw() == cls.raw()) {
+                                       GrowableArray<intptr_t>* visited) {
+  ASSERT(visited != NULL);
+  const intptr_t cls_index = cls.index();
+  for (int i = 0; i < visited->length(); i++) {
+    if ((*visited)[i] == cls_index) {
       // We have already visited interface class 'cls'. We found a cycle.
       const String& interface_name = String::Handle(cls.Name());
       const Script& script = Script::Handle(cls.script());
       ReportError(script, cls.token_index(),
                   "cyclic reference found for interface '%s'",
                   interface_name.ToCString());
     }
   }
 
   // If the class/interface has no explicit interfaces, we are done.
   Array& super_interfaces = Array::Handle(cls.interfaces());
   if (super_interfaces.Length() == 0) {
     return;
   }
 
   // If cls belongs to core lib or to core lib's implementation, restrictions
   // about allowed interfaces are lifted.
   const bool cls_belongs_to_core_lib =
       (cls.library() == Library::CoreLibrary()) ||
       (cls.library() == Library::CoreImplLibrary());
 
   // Resolve and check the interfaces of cls.
-  visited.Add(cls);
+  visited->Add(cls_index);
   AbstractType& interface = AbstractType::Handle();
   Class& interface_class = Class::Handle();
   for (intptr_t i = 0; i < super_interfaces.Length(); i++) {
     interface ^= super_interfaces.At(i);
     ResolveType(cls, interface, kFinalizeWellFormed);
     if (interface.IsTypeParameter()) {
       const Script& script = Script::Handle(cls.script());
       ReportError(script, cls.token_index(),
                   "type parameter '%s' cannot be used as interface",
                   String::Handle(interface.Name()).ToCString());
@@ skipping 20 matching lines @@
         const Script& script = Script::Handle(cls.script());
         ReportError(script, cls.token_index(),
                     "'%s' is not allowed to extend or implement '%s'",
                     String::Handle(cls.Name()).ToCString(),
                     String::Handle(interface_class.Name()).ToCString());
       }
     }
     // Now resolve the super interfaces.
     ResolveInterfaces(interface_class, visited);
   }
-  visited.RemoveLast();
+  visited->RemoveLast();
 }
 
 
 // A class is marked as constant if it has one constant constructor.
 // A constant class:
 // - may extend only const classes.
 // - has only const instance fields.
 // Note: we must check for cycles before checking for const properties.
 void ClassFinalizer::CheckForLegalConstClass(const Class& cls) {
   ASSERT(cls.is_const());
@@ skipping 135 matching lines @@
 void ClassFinalizer::ReportError(const char* format, ...) {
   va_list args;
   va_start(args, format);
   const Error& error = Error::Handle(
       Parser::FormatError(Script::Handle(), -1, "Error", format, args));
   va_end(args);
   ReportError(error);
 }
 
 }  // namespace dart