Check for cyclic reference in typedefs

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

Index: sdk/lib/_internal/compiler/implementation/resolution/members.dart
diff --git a/sdk/lib/_internal/compiler/implementation/resolution/members.dart b/sdk/lib/_internal/compiler/implementation/resolution/members.dart
index e6fd47862ac1280627bedfdbbf339ae86f10a11c..9e2e458b1b6ba4d60a4a11d8c8d0372e529947fc 100644
--- a/sdk/lib/_internal/compiler/implementation/resolution/members.dart
+++ b/sdk/lib/_internal/compiler/implementation/resolution/members.dart
@@ -3006,7 +3006,58 @@ class TypedefResolverVisitor extends TypeDefinitionVisitor {
     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;
   }
 }