[cfe] Add DartTypeComparator
The utility class DartTypeComparator allows to compare two dart types
under various assumptions, such as ignoring nullability at the
top-level type node or equating all top types.
Change-Id: I998e4a0a3ac236077cd1bcd12a5ad146ff10bb1d
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/149427
Commit-Queue: Dmitry Stefantsov <dmitryas@google.com>
Reviewed-by: Johnni Winther <johnniwinther@google.com>
diff --git a/pkg/front_end/test/spell_checking_list_common.txt b/pkg/front_end/test/spell_checking_list_common.txt
index 25a39e4..4a1e4e1 100644
--- a/pkg/front_end/test/spell_checking_list_common.txt
+++ b/pkg/front_end/test/spell_checking_list_common.txt
@@ -510,6 +510,7 @@
commonly
compact
comparable
+comparator
compare
comparing
comparison
@@ -997,6 +998,7 @@
equal
equality
equals
+equate
equivalence
equivalent
equivalents
@@ -2268,6 +2270,7 @@
properly
properties
property
+proposition
prototype
proves
provide
diff --git a/pkg/kernel/lib/src/dart_type_equivalence.dart b/pkg/kernel/lib/src/dart_type_equivalence.dart
new file mode 100644
index 0000000..731a5fe
--- /dev/null
+++ b/pkg/kernel/lib/src/dart_type_equivalence.dart
@@ -0,0 +1,281 @@
+// Copyright (c) 2020, 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.md file.
+
+import '../ast.dart';
+import '../core_types.dart';
+import '../visitor.dart';
+
+class DartTypeEquivalence implements DartTypeVisitor1<bool, DartType> {
+ final CoreTypes coreTypes;
+ final bool equateTopTypes;
+ final bool ignoreAllNullabilities;
+ final bool ignoreTopLevelNullability;
+
+ bool _atTopLevel = true;
+ List<Map<TypeParameter, TypeParameter>> _alphaRenamingStack = [];
+
+ DartTypeEquivalence(this.coreTypes,
+ {this.equateTopTypes = false,
+ this.ignoreAllNullabilities = false,
+ this.ignoreTopLevelNullability = false});
+
+ bool areEqual(DartType type1, DartType type2) {
+ _alphaRenamingStack.clear();
+ _atTopLevel = true;
+ return type1.accept1(this, type2);
+ }
+
+ @override
+ bool defaultDartType(DartType node, DartType other) {
+ throw new UnsupportedError("${node.runtimeType}");
+ }
+
+ @override
+ bool visitBottomType(BottomType node, DartType other) {
+ return other is BottomType;
+ }
+
+ @override
+ bool visitDynamicType(DynamicType node, DartType other) {
+ return equateTopTypes ? coreTypes.isTop(other) : other is DynamicType;
+ }
+
+ @override
+ bool visitFunctionType(FunctionType node, DartType other) {
+ if (other is FunctionType) {
+ if (!_checkAndRegisterNullabilities(
+ node.declaredNullability, other.declaredNullability)) {
+ return false;
+ }
+
+ // If the two types are un-aliased typedef instantiations, check that
+ // those instantiations are equal as well.
+ bool nodeIsUnaliased = node.typedefType != null;
+ bool otherIsUnaliased = other.typedefType != null;
+ if (nodeIsUnaliased != otherIsUnaliased) {
+ return false;
+ }
+ if (node.typedefType != null) {
+ // The assert below checks the implication: if the typedef types are
+ // equal, their un-aliased types are equal as well. The reverse is not
+ // true due to possibly unused type parameters F<int> and F<String> may
+ // be equal when un-aliased if the type parameter of typedef F isn't
+ // used on the right-hand side of the definition of F. The checked
+ // proposition in the assert allows to skip checking the function types
+ // themselves if the typedef types are equal.
+ assert(() {
+ DartTypeEquivalence copy = this.copy();
+ if (!copy.areEqual(node.typedefType, other.typedefType)) {
+ return true;
+ }
+ FunctionType nodeWithoutTypedefType = new FunctionType(
+ node.positionalParameters,
+ node.returnType,
+ node.declaredNullability,
+ namedParameters: node.namedParameters,
+ typeParameters: node.typeParameters,
+ requiredParameterCount: node.requiredParameterCount,
+ typedefType: null);
+ FunctionType otherWithoutTypedefType = new FunctionType(
+ other.positionalParameters,
+ other.returnType,
+ other.declaredNullability,
+ namedParameters: other.namedParameters,
+ typeParameters: other.typeParameters,
+ requiredParameterCount: other.requiredParameterCount,
+ typedefType: null);
+ return copy.areEqual(nodeWithoutTypedefType, otherWithoutTypedefType);
+ }());
+ return node.typedefType.accept1(this, other.typedefType);
+ }
+
+ // Perform simple number checks before the checks on parts.
+ if (node.typeParameters.length != other.typeParameters.length) {
+ return false;
+ }
+ if (node.positionalParameters.length !=
+ other.positionalParameters.length) {
+ return false;
+ }
+ if (node.requiredParameterCount != other.requiredParameterCount) {
+ return false;
+ }
+ if (node.namedParameters.length != other.namedParameters.length) {
+ return false;
+ }
+
+ // Enter new static scope. The scope must be exited before a return. To
+ // void multiple returns, the [result] variable is used below.
+ _pushTypeParameters(node.typeParameters, other.typeParameters);
+ bool result = true;
+
+ for (int i = 0; result && i < node.typeParameters.length; ++i) {
+ if (!node.typeParameters[i].bound
+ .accept1(this, other.typeParameters[i].bound)) {
+ result = false;
+ }
+ // Don't check defaultTypes: they are a convenience mechanism.
+ }
+ for (int i = 0; result && i < node.positionalParameters.length; ++i) {
+ if (!node.positionalParameters[i]
+ .accept1(this, other.positionalParameters[i])) {
+ result = false;
+ }
+ }
+ Map<String, DartType> nodeNamedParameters = {};
+ for (int i = 0; i < node.namedParameters.length; ++i) {
+ nodeNamedParameters[node.namedParameters[i].name] =
+ node.namedParameters[i].type;
+ }
+ for (int i = 0; result && i < other.namedParameters.length; ++i) {
+ String otherName = other.namedParameters[i].name;
+ DartType otherType = other.namedParameters[i].type;
+ if (!nodeNamedParameters.containsKey(otherName) ||
+ !nodeNamedParameters[otherName].accept1(this, otherType)) {
+ result = false;
+ }
+ }
+ if (!node.returnType.accept1(this, other.returnType)) {
+ result = false;
+ }
+
+ _dropTypeParameters();
+ return result;
+ }
+ return false;
+ }
+
+ @override
+ bool visitInterfaceType(InterfaceType node, DartType other) {
+ // First, check Object*, FutureOr<Object?>, etc.
+ if (equateTopTypes && coreTypes.isTop(node)) {
+ return coreTypes.isTop(other);
+ }
+
+ if (other is InterfaceType) {
+ if (!_checkAndRegisterNullabilities(
+ node.declaredNullability, other.declaredNullability)) {
+ return false;
+ }
+ if (node.classNode != other.classNode) {
+ return false;
+ }
+ assert(node.typeArguments.length == other.typeArguments.length);
+ for (int i = 0; i < node.typeArguments.length; ++i) {
+ if (!node.typeArguments[i].accept1(this, other.typeArguments[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+ return false;
+ }
+
+ @override
+ bool visitInvalidType(InvalidType node, DartType other) {
+ return other is InvalidType;
+ }
+
+ @override
+ bool visitNeverType(NeverType node, DartType other) {
+ if (other is NeverType) {
+ return _checkAndRegisterNullabilities(
+ node.declaredNullability, other.declaredNullability);
+ }
+ return false;
+ }
+
+ @override
+ bool visitTypeParameterType(TypeParameterType node, DartType other) {
+ if (other is TypeParameterType) {
+ bool nodeIsIntersection = node.promotedBound != null;
+ bool otherIsIntersection = other.promotedBound != null;
+ if (nodeIsIntersection != otherIsIntersection) {
+ return false;
+ }
+ if (!_checkAndRegisterNullabilities(
+ node.declaredNullability, other.declaredNullability)) {
+ return false;
+ }
+ if (!identical(_lookup(node.parameter), other.parameter)) {
+ return false;
+ }
+ return nodeIsIntersection
+ ? node.promotedBound.accept1(this, other.promotedBound)
+ : true;
+ }
+ return false;
+ }
+
+ @override
+ bool visitTypedefType(TypedefType node, DartType other) {
+ if (other is TypedefType) {
+ if (!_checkAndRegisterNullabilities(
+ node.declaredNullability, other.declaredNullability)) {
+ return false;
+ }
+ if (node.typedefNode != other.typedefNode) {
+ return false;
+ }
+ assert(node.typeArguments.length == other.typeArguments.length);
+ for (int i = 0; i < node.typeArguments.length; ++i) {
+ if (!node.typeArguments[i].accept1(this, node.typeArguments[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+ return false;
+ }
+
+ @override
+ bool visitVoidType(VoidType node, DartType other) {
+ return equateTopTypes ? coreTypes.isTop(other) : other is VoidType;
+ }
+
+ bool _checkAndRegisterNullabilities(
+ Nullability nodeNullability, Nullability otherNullability) {
+ bool result;
+ if (nodeNullability == otherNullability ||
+ ignoreAllNullabilities ||
+ ignoreTopLevelNullability && _atTopLevel) {
+ result = true;
+ } else {
+ result = false;
+ }
+ _atTopLevel = false;
+ return result;
+ }
+
+ void _pushTypeParameters(
+ List<TypeParameter> keys, List<TypeParameter> values) {
+ assert(keys.length == values.length);
+ Map<TypeParameter, TypeParameter> parameters =
+ new Map<TypeParameter, TypeParameter>.identity();
+ for (int i = 0; i < keys.length; ++i) {
+ parameters[keys[i]] = values[i];
+ }
+ _alphaRenamingStack.add(parameters);
+ }
+
+ void _dropTypeParameters() {
+ _alphaRenamingStack.removeLast();
+ }
+
+ TypeParameter _lookup(TypeParameter parameter) {
+ for (int i = _alphaRenamingStack.length - 1; i >= 0; --i) {
+ if (_alphaRenamingStack[i].containsKey(parameter)) {
+ return _alphaRenamingStack[i][parameter];
+ }
+ }
+ return parameter;
+ }
+
+ DartTypeEquivalence copy() {
+ return new DartTypeEquivalence(coreTypes,
+ equateTopTypes: equateTopTypes,
+ ignoreAllNullabilities: ignoreAllNullabilities,
+ ignoreTopLevelNullability: ignoreTopLevelNullability);
+ }
+}
diff --git a/pkg/kernel/test/dart_type_equivalence_test.dart b/pkg/kernel/test/dart_type_equivalence_test.dart
new file mode 100644
index 0000000..4ec0895
--- /dev/null
+++ b/pkg/kernel/test/dart_type_equivalence_test.dart
@@ -0,0 +1,228 @@
+// Copyright (c) 2020, 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.
+
+import "package:expect/expect.dart" show Expect;
+
+import 'package:kernel/ast.dart' hide MapEntry;
+import 'package:kernel/src/dart_type_equivalence.dart';
+import 'package:kernel/testing/type_parser_environment.dart';
+
+run() {
+ // Simple types.
+ areEqual("int", "int");
+ notEqual("int", "String");
+
+ // Simple types with nullabilities.
+ areEqual("int?", "int?");
+ notEqual("int", "int?");
+ notEqual("int?", "String?");
+
+ areEqual("int?", "int?", ignoreAllNullabilities: true);
+ areEqual("int", "int?", ignoreAllNullabilities: true);
+ notEqual("int?", "String?", ignoreAllNullabilities: true);
+
+ areEqual("int?", "int?", ignoreTopLevelNullability: true);
+ areEqual("int", "int?", ignoreTopLevelNullability: true);
+ notEqual("int?", "String?", ignoreTopLevelNullability: true);
+
+ // 1-level deep types.
+ areEqual("List<int?>?", "List<int?>?");
+ notEqual("List<int?>?", "List<int?>");
+ notEqual("List<int?>?", "List<int>?");
+ notEqual("List<int?>?", "List<int>");
+
+ areEqual("List<int?>?", "List<int?>?", ignoreAllNullabilities: true);
+ areEqual("List<int?>?", "List<int?>", ignoreAllNullabilities: true);
+ areEqual("List<int?>?", "List<int>?", ignoreAllNullabilities: true);
+ areEqual("List<int?>?", "List<int>", ignoreAllNullabilities: true);
+
+ areEqual("List<int?>?", "List<int?>?", ignoreTopLevelNullability: true);
+ areEqual("List<int?>?", "List<int?>", ignoreTopLevelNullability: true);
+ notEqual("List<int?>?", "List<int>?", ignoreTopLevelNullability: true);
+ notEqual("List<int?>?", "List<int>", ignoreTopLevelNullability: true);
+
+ // Top types.
+ areEqual("dynamic", "dynamic");
+ notEqual("dynamic", "Object?");
+ notEqual("dynamic", "Object*");
+ notEqual("dynamic", "void");
+ areEqual("Object?", "Object?");
+ notEqual("Object?", "Object*");
+ notEqual("Object?", "void");
+ areEqual("Object*", "Object*");
+ notEqual("Object*", "void");
+ areEqual("void", "void");
+ notEqual("FutureOr<dynamic>", "void");
+ notEqual("FutureOr<FutureOr<Object?>>", "Object*");
+ notEqual("FutureOr<FutureOr<FutureOr<Object*>?>>?", "dynamic");
+ notEqual("FutureOr<Object?>", "FutureOr<Object?>?");
+ notEqual("FutureOr<FutureOr<Object?>>", "FutureOr<FutureOr<Object?>?>?");
+ notEqual("FutureOr<FutureOr<Object?>>", "FutureOr<FutureOr<dynamic>?>?");
+
+ areEqual("dynamic", "Object?", equateTopTypes: true);
+ areEqual("dynamic", "Object*", equateTopTypes: true);
+ areEqual("dynamic", "void", equateTopTypes: true);
+ areEqual("Object?", "Object*", equateTopTypes: true);
+ areEqual("Object?", "void", equateTopTypes: true);
+ areEqual("Object*", "void", equateTopTypes: true);
+ areEqual("FutureOr<dynamic>", "void", equateTopTypes: true);
+ areEqual("FutureOr<FutureOr<Object?>>", "Object*", equateTopTypes: true);
+ areEqual("FutureOr<FutureOr<FutureOr<Object*>?>>?", "dynamic",
+ equateTopTypes: true);
+ areEqual("FutureOr<Object?>", "FutureOr<Object?>?", equateTopTypes: true);
+ areEqual("FutureOr<FutureOr<Object?>>", "FutureOr<FutureOr<Object?>?>?",
+ equateTopTypes: true);
+ areEqual("FutureOr<FutureOr<Object?>>", "FutureOr<FutureOr<dynamic>?>?",
+ equateTopTypes: true);
+
+ areEqual("Object?", "Object*", ignoreAllNullabilities: true);
+ areEqual("FutureOr<Object?>", "FutureOr<Object?>?",
+ ignoreAllNullabilities: true);
+ areEqual("FutureOr<FutureOr<Object?>>", "FutureOr<FutureOr<Object?>?>?",
+ ignoreAllNullabilities: true);
+ notEqual("FutureOr<FutureOr<Object?>>", "FutureOr<FutureOr<dynamic>?>?",
+ ignoreAllNullabilities: true);
+
+ areEqual("FutureOr<Object?>", "FutureOr<Object?>?",
+ ignoreTopLevelNullability: true);
+ notEqual("FutureOr<FutureOr<Object?>>", "FutureOr<FutureOr<Object?>?>?",
+ ignoreTopLevelNullability: true);
+ notEqual("FutureOr<FutureOr<Object?>>", "FutureOr<FutureOr<dynamic>?>?",
+ ignoreTopLevelNullability: true);
+
+ // Generic function types.
+ notEqual("<T extends dynamic>() ->? int", "<T extends Object?>() -> int?");
+ notEqual("<T extends dynamic>() ->? int", "<T extends Object?>() -> int?",
+ equateTopTypes: true);
+ notEqual("<T extends dynamic>() ->? int", "<T extends Object?>() -> int?",
+ ignoreAllNullabilities: true);
+ notEqual("<T extends dynamic>() ->? int", "<T extends Object?>() -> int?",
+ ignoreTopLevelNullability: true);
+ notEqual("<T extends dynamic>() ->? int", "<T extends Object?>() -> int?",
+ equateTopTypes: true, ignoreTopLevelNullability: true);
+ areEqual("<T extends dynamic>() ->? int", "<T extends Object?>() -> int?",
+ equateTopTypes: true, ignoreAllNullabilities: true);
+
+ notEqual("<T extends dynamic>() -> T?", "<S extends Object?>() -> S?");
+ areEqual("<T extends dynamic>() -> T?", "<S extends Object?>() -> S?",
+ equateTopTypes: true);
+
+ notEqual("<T extends dynamic>() -> T", "<S extends FutureOr<void>>() -> S?");
+ notEqual("<T extends dynamic>() -> T", "<S extends FutureOr<void>>() -> S?",
+ equateTopTypes: true);
+ notEqual("<T extends dynamic>() -> T", "<S extends FutureOr<void>>() -> S?",
+ ignoreAllNullabilities: true);
+ areEqual("<T extends dynamic>() -> T", "<S extends FutureOr<void>>() -> S?",
+ equateTopTypes: true, ignoreAllNullabilities: true);
+
+ areEqual("<T>(<S>() -> void) -> void", "<X>(<Y>() -> void) -> void");
+
+ notEqual("<T>(<S extends void>() -> void) -> void",
+ "<X>(<Y extends Object?>() -> void) -> void");
+ notEqual("<T>(<S extends void>() -> void) -> void",
+ "<X>(<Y extends Object?>() -> void) -> void",
+ ignoreAllNullabilities: true);
+
+ // Free type variables.
+ areEqual("T", "T", typeParameters: "T");
+ notEqual("T?", "T", typeParameters: "T");
+
+ notEqual("T", "S",
+ typeParameters: "T, S",
+ equateTopTypes: true,
+ ignoreAllNullabilities: true);
+
+ notEqual("T & int?", "T & int", typeParameters: "T");
+ notEqual("T & int?", "T & int",
+ typeParameters: "T", ignoreTopLevelNullability: true);
+ areEqual("T & int?", "T & int",
+ typeParameters: "T", ignoreAllNullabilities: true);
+
+ // Check that normalization is out of the scope of the equivalence, even with
+ // the most permissive flags.
+ notEqual("Never?", "Null",
+ equateTopTypes: true, ignoreAllNullabilities: true);
+ notEqual("FutureOr<Never>", "Future<Never>",
+ equateTopTypes: true, ignoreAllNullabilities: true);
+ notEqual("FutureOr<Object>", "Object",
+ equateTopTypes: true, ignoreAllNullabilities: true);
+}
+
+areEqual(String type1, String type2,
+ {String typeParameters = '',
+ bool equateTopTypes = false,
+ bool ignoreAllNullabilities = false,
+ bool ignoreTopLevelNullability = false}) {
+ Env env = new Env('')..extendWithTypeParameters(typeParameters);
+ DartType t1 = env.parseType(type1);
+ DartType t2 = env.parseType(type2);
+
+ List<String> flagNamesForDebug = [
+ if (equateTopTypes) "equateTopTypes",
+ if (ignoreAllNullabilities) "ignoreAllNullabilities",
+ if (ignoreTopLevelNullability) "ignoreTopLevelNullability",
+ ];
+
+ print("areEqual(${type1}, ${type2}"
+ "${flagNamesForDebug.map((f) => ", $f").join()})");
+ Expect.isTrue(
+ new DartTypeEquivalence(env.coreTypes,
+ equateTopTypes: equateTopTypes,
+ ignoreAllNullabilities: ignoreAllNullabilities,
+ ignoreTopLevelNullability: ignoreTopLevelNullability)
+ .areEqual(t1, t2),
+ "Expected '${type1}' and '${type2}' to be equal "
+ "with flags ${flagNamesForDebug.map((f) => "'$f'").join(", ")}.");
+
+ print("areEqual(${type2}, ${type1}"
+ "${flagNamesForDebug.map((f) => ", $f").join()})");
+ Expect.isTrue(
+ new DartTypeEquivalence(env.coreTypes,
+ equateTopTypes: equateTopTypes,
+ ignoreAllNullabilities: ignoreAllNullabilities,
+ ignoreTopLevelNullability: ignoreTopLevelNullability)
+ .areEqual(t2, t1),
+ "Expected '${type2}' and '${type1}' to be equal "
+ "with flags ${flagNamesForDebug.map((f) => "'$f'").join(", ")}.");
+}
+
+notEqual(String type1, String type2,
+ {String typeParameters = '',
+ bool equateTopTypes = false,
+ bool ignoreAllNullabilities = false,
+ bool ignoreTopLevelNullability = false}) {
+ Env env = new Env('')..extendWithTypeParameters(typeParameters);
+ DartType t1 = env.parseType(type1);
+ DartType t2 = env.parseType(type2);
+
+ List<String> flagNamesForDebug = [
+ if (equateTopTypes) "equateTopTypes",
+ if (ignoreAllNullabilities) "ignoreAllNullabilities",
+ if (ignoreTopLevelNullability) "ignoreTopLevelNullability",
+ ];
+
+ print("notEqual(${type1}, ${type2}"
+ "${flagNamesForDebug.map((f) => ", $f").join()})");
+ Expect.isFalse(
+ new DartTypeEquivalence(env.coreTypes,
+ equateTopTypes: equateTopTypes,
+ ignoreAllNullabilities: ignoreAllNullabilities,
+ ignoreTopLevelNullability: ignoreTopLevelNullability)
+ .areEqual(t1, t2),
+ "Expected '${type1}' and '${type2}' to be not equal "
+ "with flags ${flagNamesForDebug.map((f) => "'$f'").join(", ")}.");
+
+ print("notEqual(${type2}, ${type1}"
+ "${flagNamesForDebug.map((f) => ", $f").join()})");
+ Expect.isFalse(
+ new DartTypeEquivalence(env.coreTypes,
+ equateTopTypes: equateTopTypes,
+ ignoreAllNullabilities: ignoreAllNullabilities,
+ ignoreTopLevelNullability: ignoreTopLevelNullability)
+ .areEqual(t2, t1),
+ "Expected '${type2}' and '${type1}' to be not equal "
+ "with flags ${flagNamesForDebug.map((f) => "'$f'").join(", ")}.");
+}
+
+main() => run();
