Check for cyclic reference in typedefs

sdk/lib/_internal/compiler/implementation/resolution/members.dart

 // 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.
 
 part of resolution;
 
 abstract class TreeElements {
   Element get currentElement;
   Set<Node> get superUses;
 
@@ skipping 2988 matching lines @@
     TypedefType type = element.computeType(compiler);
     scope = new TypeDeclarationScope(scope, element);
     resolveTypeVariableBounds(node.typeParameters);
 
     element.functionSignature = SignatureResolver.analyze(
         compiler, node.formals, node.returnType, element);
 
     element.alias = compiler.computeFunctionType(
         element, element.functionSignature);
 
-    // TODO(johnniwinther): Check for cyclic references in the typedef alias.
+    void checkCyclicReference() {
+      var visitor = new TypedefCyclicVisitor(compiler, element);
+      visitor.visit(type);

[ahe, 2013/04/02 08:22:39]

This is probably slightly faster:

type.accept(visitor, null);

Generally, the visit method becomes polymorphic, but type.accept is monomorphic
here.

[Johnni Winther, 2013/04/02 09:40:14]

Done.

+    }
+    compiler.enqueuer.resolution.addPostProcessing(element,
+                                                   checkCyclicReference);
   }
 }
 
+// TODO(johnniwinther): Replace with a traversal on the AST when the type
+// annotations in typedef alias are stored in a [TreeElements] mapping.
+class TypedefCyclicVisitor extends DartTypeTraversal {
+  final Compiler compiler;
+  final TypedefElement element;
+  bool hasCyclicReference = false;
+  Link<TypedefElement> seenTypedefs = const Link<TypedefElement>();
+
+  TypedefCyclicVisitor(Compiler this.compiler, TypedefElement this.element);
+
+  visitType(DartType type, _) {
+    // Do nothing.
+  }
+
+  visitTypedefType(TypedefType type, _) {
+    TypedefElement typedefElement = type.element;
+    if (seenTypedefs.contains(typedefElement)) {
+      if (!hasCyclicReference && identical(element, typedefElement)) {
+        // Only report an error on the checked typedef to avoid generating
+        // multiple errors for the same cyclicity.
+        hasCyclicReference = true;
+        if (seenTypedefs.tail.isEmpty) {
+          // Direct cyclicity.

[ahe, 2013/04/02 08:22:39]

I don't think "cyclicity" is a word.

[Johnni Winther, 2013/04/02 09:40:14]

It is! (and not just in my vocabulary: http://en.wiktionary.org/wiki/cyclicity)

+          compiler.reportErrorCode(element,
+              MessageKind.CYCLIC_TYPEDEF, {'typedefName': element.name});
+        } else if (seenTypedefs.tail.tail.isEmpty) {
+          // Cyclicity through one other typedef.

[ahe, 2013/04/02 08:22:39]

"cyclicity"

[Johnni Winther, 2013/04/02 09:40:14]

Ditto.

+          compiler.reportErrorCode(element,
+              MessageKind.CYCLIC_TYPEDEF_ONE,
+              {'typedefName': element.name,
+               'otherTypedefName': seenTypedefs.head.name});
+        } else {
+          // Cyclicity through more than one other typedef.
+          compiler.reportErrorCode(element,

[ahe, 2013/04/02 08:22:39]

I'd drop this error code and use:

for (TypedefElement cycle in seenTypedefs) {
  compiler.reportErrorCode(element, MessageKind.CYCLIC_TYPEDEF_ONE, ...);
}

[Johnni Winther, 2013/04/02 09:40:14]

Done.

+              MessageKind.CYCLIC_TYPEDEF_MORE, {'typedefName': element.name});
+        }
+      }
+      return;
+    }
+    seenTypedefs = seenTypedefs.prepend(typedefElement);
+    visitList(type.typeArguments);
+    visit(typedefElement.alias);
+    seenTypedefs = seenTypedefs.tail;
+  }
+}
+
 /**
  * The implementation of [ResolverTask.resolveClass].
  *
  * This visitor has to be extra careful as it is building the basic
  * element information, and cannot safely look at other elements as
  * this may lead to cycles.
  *
  * This visitor can assume that the supertypes have already been
  * resolved, but it cannot call [ResolverTask.resolveClass] directly
  * or indirectly (through [ClassElement.ensureResolved]) for any other
@@ skipping 804 matching lines @@
     return e;
   }
 
   /// Assumed to be called by [resolveRedirectingFactory].
   Element visitReturn(Return node) {
     Node expression = node.expression;
     return finishConstructorReference(visit(expression),
                                       expression, expression);
   }
 }