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.