Detect cycles in type variable bounds

Fixes #32989.

Change-Id: I809d67a4c0cbbb24446ace6fd56bb3b1a4c1364a
Reviewed-on: https://dart-review.googlesource.com/73120
Commit-Queue: Jens Johansen <jensj@google.com>
Reviewed-by: Peter von der Ahé <ahe@google.com>
diff --git a/pkg/front_end/lib/src/fasta/fasta_codes_generated.dart b/pkg/front_end/lib/src/fasta/fasta_codes_generated.dart
index b04f0f2..712912b 100644
--- a/pkg/front_end/lib/src/fasta/fasta_codes_generated.dart
+++ b/pkg/front_end/lib/src/fasta/fasta_codes_generated.dart
@@ -1623,6 +1623,35 @@
     tip: r"""Try removing the 'covariant' keyword.""");
 
 // DO NOT EDIT. THIS FILE IS GENERATED. SEE TOP OF FILE.
+const Template<
+    Message Function(
+        String name,
+        String
+            string)> templateCycleInTypeVariables = const Template<
+        Message Function(String name, String string)>(
+    messageTemplate: r"""Type '#name' is a bound of itself via '#string'.""",
+    tipTemplate:
+        r"""Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.""",
+    withArguments: _withArgumentsCycleInTypeVariables);
+
+// DO NOT EDIT. THIS FILE IS GENERATED. SEE TOP OF FILE.
+const Code<Message Function(String name, String string)>
+    codeCycleInTypeVariables =
+    const Code<Message Function(String name, String string)>(
+        "CycleInTypeVariables", templateCycleInTypeVariables,
+        analyzerCode: "TYPE_PARAMETER_SUPERTYPE_OF_ITS_BOUND",
+        severity: Severity.error);
+
+// DO NOT EDIT. THIS FILE IS GENERATED. SEE TOP OF FILE.
+Message _withArgumentsCycleInTypeVariables(String name, String string) {
+  return new Message(codeCycleInTypeVariables,
+      message: """Type '${name}' is a bound of itself via '${string}'.""",
+      tip:
+          """Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.""",
+      arguments: {'name': name, 'string': string});
+}
+
+// DO NOT EDIT. THIS FILE IS GENERATED. SEE TOP OF FILE.
 const Template<Message Function(String name, String string)>
     templateCyclicClassHierarchy =
     const Template<Message Function(String name, String string)>(
diff --git a/pkg/front_end/lib/src/fasta/source/outline_builder.dart b/pkg/front_end/lib/src/fasta/source/outline_builder.dart
index f094ef3..c3c9a85 100644
--- a/pkg/front_end/lib/src/fasta/source/outline_builder.dart
+++ b/pkg/front_end/lib/src/fasta/source/outline_builder.dart
@@ -28,6 +28,7 @@
         messageOperatorWithOptionalFormals,
         messageStaticConstructor,
         messageTypedefNotFunction,
+        templateCycleInTypeVariables,
         templateDuplicatedParameterName,
         templateDuplicatedParameterNameCause,
         templateOperatorMinusParameterMismatch,
@@ -1146,6 +1147,53 @@
   void endTypeVariables(Token beginToken, Token endToken) {
     debugEvent("endTypeVariables");
 
+    // Peek to leave type parameters on top of stack.
+    List typeParameters = peek();
+
+    Map<String, TypeVariableBuilder> typeVariablesByName;
+    for (TypeVariableBuilder builder in typeParameters) {
+      if (builder.bound != null) {
+        if (typeVariablesByName == null) {
+          typeVariablesByName = new Map<String, TypeVariableBuilder>();
+          for (TypeVariableBuilder builder in typeParameters) {
+            typeVariablesByName[builder.name] = builder;
+          }
+        }
+
+        // Find cycle: If there's no cycle we can at most step through all
+        // `typeParameters` (at which point the last builders bound will be
+        // null).
+        // If there is a cycle with `builder` 'inside' the steps to get back to
+        // it will also be bound by `typeParameters.length`.
+        // If there is a cycle without `builder` 'inside' we will just ignore it
+        // for now. It will be reported when processing one of the `builder`s
+        // that is in fact `inside` the cycle. This matches the cyclic class
+        // hierarchy error.
+        TypeVariableBuilder bound = builder;
+        for (int steps = 0;
+            bound.bound != null && steps < typeParameters.length;
+            ++steps) {
+          bound = typeVariablesByName[bound.bound.name];
+          if (bound == null || bound == builder) break;
+        }
+        if (bound == builder && bound.bound != null) {
+          // Write out cycle.
+          List<String> via = new List<String>();
+          bound = typeVariablesByName[builder.bound.name];
+          while (bound != builder) {
+            via.add(bound.name);
+            bound = typeVariablesByName[bound.bound.name];
+          }
+          String involvedString = via.join("', '");
+          addCompileTimeError(
+              templateCycleInTypeVariables.withArguments(
+                  builder.name, involvedString),
+              builder.charOffset,
+              builder.name.length);
+        }
+      }
+    }
+
     if (inConstructorName) {
       addProblem(messageConstructorWithTypeParameters,
           offsetForToken(beginToken), lengthOfSpan(beginToken, endToken));
diff --git a/pkg/front_end/messages.yaml b/pkg/front_end/messages.yaml
index a61d019..1f03eb8 100644
--- a/pkg/front_end/messages.yaml
+++ b/pkg/front_end/messages.yaml
@@ -2638,6 +2638,14 @@
   template: "Bound of this variable references raw type '#name'."
   severity: CONTEXT
 
+CycleInTypeVariables:
+  template: "Type '#name' is a bound of itself via '#string'."
+  tip: "Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle."
+  severity: ERROR
+  analyzerCode: TYPE_PARAMETER_SUPERTYPE_OF_ITS_BOUND
+  script:
+    - "foo<A extends A>() {}"
+
 CantUsePrefixAsExpression:
   template: "A prefix can't be used as an expression."
   severity: ERROR
diff --git a/pkg/front_end/testcases/dartino/super_is_parameter.incremental.yaml b/pkg/front_end/testcases/dartino/super_is_parameter.incremental.yaml
index 65037fa..fef1a3e 100644
--- a/pkg/front_end/testcases/dartino/super_is_parameter.incremental.yaml
+++ b/pkg/front_end/testcases/dartino/super_is_parameter.incremental.yaml
@@ -6,7 +6,7 @@
   <<<< []
   class A<S> {
   ==== []
-  class A<S extends S> {
+  class A<S extends num> {
   >>>>
     S field;
   }
diff --git a/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.direct.expect b/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.direct.expect
index e8031c5..964c88f 100644
--- a/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.direct.expect
+++ b/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.direct.expect
@@ -1,3 +1,25 @@
+// Errors:
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:41:9: Error: Type 'T' is a bound of itself via 'U', 'Y', 'Z'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+// class I<T extends U, U extends Y, V extends Function(W), W extends Function(X),
+//         ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:41:22: Error: Type 'U' is a bound of itself via 'Y', 'Z', 'T'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+// class I<T extends U, U extends Y, V extends Function(W), W extends Function(X),
+//                      ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:42:28: Error: Type 'Y' is a bound of itself via 'Z', 'T', 'U'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+//     X extends Function(V), Y extends Z, Z extends T> {}
+//                            ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:42:41: Error: Type 'Z' is a bound of itself via 'T', 'U', 'Y'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+//     X extends Function(V), Y extends Z, Z extends T> {}
+//                                         ^
+
 library;
 import self as self;
 import "dart:core" as core;
diff --git a/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.direct.transformed.expect b/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.direct.transformed.expect
index e8031c5..964c88f 100644
--- a/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.direct.transformed.expect
+++ b/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.direct.transformed.expect
@@ -1,3 +1,25 @@
+// Errors:
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:41:9: Error: Type 'T' is a bound of itself via 'U', 'Y', 'Z'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+// class I<T extends U, U extends Y, V extends Function(W), W extends Function(X),
+//         ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:41:22: Error: Type 'U' is a bound of itself via 'Y', 'Z', 'T'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+// class I<T extends U, U extends Y, V extends Function(W), W extends Function(X),
+//                      ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:42:28: Error: Type 'Y' is a bound of itself via 'Z', 'T', 'U'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+//     X extends Function(V), Y extends Z, Z extends T> {}
+//                            ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:42:41: Error: Type 'Z' is a bound of itself via 'T', 'U', 'Y'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+//     X extends Function(V), Y extends Z, Z extends T> {}
+//                                         ^
+
 library;
 import self as self;
 import "dart:core" as core;
diff --git a/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.strong.expect b/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.strong.expect
index 7b2576f..b442329 100644
--- a/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.strong.expect
+++ b/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.strong.expect
@@ -1,3 +1,25 @@
+// Errors:
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:41:9: Error: Type 'T' is a bound of itself via 'U', 'Y', 'Z'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+// class I<T extends U, U extends Y, V extends Function(W), W extends Function(X),
+//         ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:41:22: Error: Type 'U' is a bound of itself via 'Y', 'Z', 'T'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+// class I<T extends U, U extends Y, V extends Function(W), W extends Function(X),
+//                      ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:42:28: Error: Type 'Y' is a bound of itself via 'Z', 'T', 'U'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+//     X extends Function(V), Y extends Z, Z extends T> {}
+//                            ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:42:41: Error: Type 'Z' is a bound of itself via 'T', 'U', 'Y'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+//     X extends Function(V), Y extends Z, Z extends T> {}
+//                                         ^
+
 library;
 import self as self;
 import "dart:core" as core;
diff --git a/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.strong.transformed.expect b/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.strong.transformed.expect
index 7b2576f..b442329 100644
--- a/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.strong.transformed.expect
+++ b/pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart.strong.transformed.expect
@@ -1,3 +1,25 @@
+// Errors:
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:41:9: Error: Type 'T' is a bound of itself via 'U', 'Y', 'Z'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+// class I<T extends U, U extends Y, V extends Function(W), W extends Function(X),
+//         ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:41:22: Error: Type 'U' is a bound of itself via 'Y', 'Z', 'T'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+// class I<T extends U, U extends Y, V extends Function(W), W extends Function(X),
+//                      ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:42:28: Error: Type 'Y' is a bound of itself via 'Z', 'T', 'U'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+//     X extends Function(V), Y extends Z, Z extends T> {}
+//                            ^
+//
+// pkg/front_end/testcases/instantiate_to_bound/multiple_strongly_connected.dart:42:41: Error: Type 'Z' is a bound of itself via 'T', 'U', 'Y'.
+// Try breaking the cycle by removing at least on of the 'extends' clauses in the cycle.
+//     X extends Function(V), Y extends Z, Z extends T> {}
+//                                         ^
+
 library;
 import self as self;
 import "dart:core" as core;
diff --git a/tests/co19_2/co19_2-kernel.status b/tests/co19_2/co19_2-kernel.status
index 82afac9..505724f 100644
--- a/tests/co19_2/co19_2-kernel.status
+++ b/tests/co19_2/co19_2-kernel.status
@@ -182,10 +182,8 @@
 LanguageFeatures/Instantiate-to-bound/Callable/Callable_ret_extends_neg_assign_l1_t18: MissingCompileTimeError
 LanguageFeatures/Instantiate-to-bound/Callable/Callable_ret_extends_neg_assign_l1_t20: MissingCompileTimeError
 LanguageFeatures/Instantiate-to-bound/Callable/Callable_ret_extends_neg_assign_l1_t21: MissingCompileTimeError
-LanguageFeatures/Instantiate-to-bound/class/custom_extends_neg_l1_t01: MissingCompileTimeError
 LanguageFeatures/Instantiate-to-bound/class/custom_extends_neg_l1_t04: MissingCompileTimeError
 LanguageFeatures/Instantiate-to-bound/class/custom_extends_neg_l1_t05: MissingCompileTimeError
-LanguageFeatures/Instantiate-to-bound/class/custom_extends_neg_l2_t01: MissingCompileTimeError
 LanguageFeatures/Instantiate-to-bound/function/function_named_extends_neg_assign_l1_t01: MissingCompileTimeError
 LanguageFeatures/Instantiate-to-bound/function/function_named_extends_neg_assign_l1_t03: MissingCompileTimeError
 LanguageFeatures/Instantiate-to-bound/function/function_named_extends_neg_assign_l1_t04: MissingCompileTimeError
diff --git a/tests/language_2/language_2_kernel.status b/tests/language_2/language_2_kernel.status
index 1fb1238..818a556 100644
--- a/tests/language_2/language_2_kernel.status
+++ b/tests/language_2/language_2_kernel.status
@@ -213,10 +213,6 @@
 const_types_test/34: MissingCompileTimeError # Issue 31590
 const_types_test/39: MissingCompileTimeError # Issue 31590
 constructor_reference_test/27: MissingCompileTimeError # Issue 32972 (parsed as method call)
-cyclic_type_variable_test/01: MissingCompileTimeError # Issue 32989 (missing cycle check in bounds)
-cyclic_type_variable_test/02: MissingCompileTimeError # Issue 32989 (missing cycle check in bounds)
-cyclic_type_variable_test/03: MissingCompileTimeError # Issue 32989 (missing cycle check in bounds)
-cyclic_type_variable_test/04: MissingCompileTimeError # Issue 32989 (missing cycle check in bounds)
 default_factory2_test/01: MissingCompileTimeError # Issue 31590
 default_factory_test/01: MissingCompileTimeError # Issue 31590
 deferred_inheritance_constraints_test/extends: MissingCompileTimeError # Fasta/KernelVM bug: Deferred loading kernel issue 30273.