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 89bb3e7f22b4d483a29bb9c73676dd43a5bbe164..7622c2654ecd760bc9af96c19927a8c79752e6f0 100644
--- a/sdk/lib/_internal/compiler/implementation/resolution/members.dart
+++ b/sdk/lib/_internal/compiler/implementation/resolution/members.dart
@@ -3230,7 +3230,92 @@ 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);
+      type.accept(visitor, null);
+    }
+    compiler.enqueuer.resolution.addPostProcessAction(element,
+                                                   checkCyclicReference);

[ahe, 2013/09/17 09:40:18]

Weird indentation.

[Johnni Winther, 2013/09/18 07:57:15]

Done.

+  }
+}
+
+// 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 DartTypeVisitor {
+  final Compiler compiler;
+  final TypedefElement element;
+  bool hasCyclicReference = false;
+  int seenBoundsCount = 0;

[ahe, 2013/09/17 09:40:18]

Please document this field.

[Johnni Winther, 2013/09/18 07:57:15]

Done.

+  Link<TypedefElement> seenTypedefs = const Link<TypedefElement>();
+  Link<TypeVariableElement> seenTypeVariables =
+      const Link<TypeVariableElement>();
+
+  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 (seenBoundsCount > 0) {
+          compiler.reportError(element, MessageKind.CYCLIC_TYPEDEF_TYPEVAR);
+        } else if (seenTypedefs.tail.isEmpty) {
+          // Direct cyclicity.
+          compiler.reportError(element,
+              MessageKind.CYCLIC_TYPEDEF,
+              {'typedefName': element.name});
+        } else if (seenTypedefs.tail.tail.isEmpty) {

[karlklose, 2013/09/17 08:56:15]

It would be easier to read if you computed (or tracked) the length of this list
and compared against a number here.

[Johnni Winther, 2013/09/18 07:57:15]

Done.

+          // Cyclicity through one other typedef.
+          compiler.reportError(element,
+              MessageKind.CYCLIC_TYPEDEF_ONE,
+              {'typedefName': element.name,
+               'otherTypedefName': seenTypedefs.head.name});
+        } else {
+          // Cyclicity through more than one other typedef.
+          for (TypedefElement cycle in seenTypedefs) {
+            if (!identical(typedefElement, cycle)) {
+              compiler.reportError(element,
+                  MessageKind.CYCLIC_TYPEDEF_ONE,
+                  {'typedefName': element.name,
+                   'otherTypedefName': cycle.name});
+            }
+          }
+        }
+      }
+      return;
+    }

[karlklose, 2013/09/17 08:56:15]

Please use an else block here. The return is easy to miss.

[Johnni Winther, 2013/09/18 07:57:15]

Done.

+    seenTypedefs = seenTypedefs.prepend(typedefElement);
+    type.visitChildren(this, null);
+    typedefElement.alias.accept(this, null);
+    seenTypedefs = seenTypedefs.tail;
+  }
+
+  visitFunctionType(FunctionType type, _) {
+    type.visitChildren(this, null);
+  }
+
+  visitInterfaceType(InterfaceType type, _) {
+    type.visitChildren(this, null);
+  }
+
+  visitTypeVariableType(TypeVariableType type, _) {
+    TypeVariableElement typeVariableElement = type.element;
+    if (seenTypeVariables.contains(typeVariableElement)) {
+      // Avoid running in cycles on cyclic type variable bounds.
+      // Cyclicity is reported elsewhere.
+      return;
+    }
+    seenTypeVariables = seenTypeVariables.prepend(typeVariableElement);
+    seenBoundsCount++;
+    typeVariableElement.bound.accept(this, null);
+    seenBoundsCount--;
+    seenTypeVariables = seenTypeVariables.tail;
   }
 }