Add a piece of analyzer/CFE shared infractructure for language issue 731.
This algorithm will form a piece of the solution to
https://github.com/dart-lang/language/issues/731 (improved inference
for fold etc.). In particular, when performing generic type inference
on an invocation where more than one argument is a closure, it will
determine the order in which type inference should visit the closures
to maximize the chances of producing meaningful assignments of types
to type parameters.
Change-Id: Ifc2202cb713965373981574f276dffbf1b3f48c1
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/239364
Reviewed-by: Konstantin Shcheglov <scheglov@google.com>
Commit-Queue: Paul Berry <paulberry@google.com>
diff --git a/pkg/_fe_analyzer_shared/lib/src/deferred_closure_heuristic.dart b/pkg/_fe_analyzer_shared/lib/src/deferred_closure_heuristic.dart
new file mode 100644
index 0000000..d5f823a
--- /dev/null
+++ b/pkg/_fe_analyzer_shared/lib/src/deferred_closure_heuristic.dart
@@ -0,0 +1,139 @@
+// Copyright (c) 2022, 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:_fe_analyzer_shared/src/util/dependency_walker.dart';
+
+/// Data structure tracking the type inference dependencies between closures
+/// passed as invocation parameters.
+///
+/// [planClosureReconciliationStages] is used as part of support for
+/// https://github.com/dart-lang/language/issues/731 (improved inference for
+/// fold etc.) to choose the proper order in which to recursively analyze
+/// closures passed as invocation arguments.
+abstract class ClosureDependencies<TypeVariable, Closure> {
+ final List<_ClosureNode<Closure>> _closureNodes = [];
+
+ /// Construct a [ClosureDependencies] object that's prepared to determine the
+ /// order to resolve [closures] for a generic invocation involving the given
+ /// [typeVariables].
+ ClosureDependencies(
+ Iterable<Closure> closures, Iterable<TypeVariable> typeVariables) {
+ Map<TypeVariable, Set<_ClosureNode<Closure>>> closuresDependingOnTypeVar =
+ {};
+ Map<TypeVariable, Set<_ClosureNode<Closure>>> closuresConstrainingTypeVar =
+ {};
+ for (Closure closure in closures) {
+ _ClosureNode<Closure> closureNode = new _ClosureNode<Closure>(closure);
+ _closureNodes.add(closureNode);
+ for (TypeVariable v in typeVarsFreeInClosureArguments(closure)) {
+ (closuresDependingOnTypeVar[v] ??= {}).add(closureNode);
+ }
+ for (TypeVariable v in typeVarsFreeInClosureReturns(closure)) {
+ (closuresConstrainingTypeVar[v] ??= {}).add(closureNode);
+ }
+ }
+ for (TypeVariable typeVariable in typeVariables) {
+ for (_ClosureNode<Closure> closureNode
+ in closuresDependingOnTypeVar[typeVariable] ?? const {}) {
+ closureNode.dependencies
+ .addAll(closuresConstrainingTypeVar[typeVariable] ?? const {});
+ }
+ }
+ }
+
+ /// Computes the order in which to resolve the closures passed to the
+ /// constructor.
+ ///
+ /// Each entry in the returned list represents the set of closures that should
+ /// be visited during a single stage of resolution; after each stage, the
+ /// assignment of actual types to type variables should be refined.
+ ///
+ /// So, for example, if the closures in question are A, B, and C, and the
+ /// returned list is `[{A, B}, {C}]`, then first closures A and B should be
+ /// resolved, then the assignment of actual types to type variables should be
+ /// refined, and then C should be resolved, and then the final assignment of
+ /// actual types to type variables should be computed.
+ List<Set<Closure>> planClosureReconciliationStages() {
+ _DependencyWalker<Closure> walker = new _DependencyWalker<Closure>();
+ for (_ClosureNode<Closure> closureNode in _closureNodes) {
+ walker.walk(closureNode);
+ }
+ return walker.closureReconciliationStages;
+ }
+
+ /// If the type of the parameter corresponding to [closure] is a function
+ /// type, the set of type parameters referred to by the parameter types of
+ /// that parameter. If the type of the parameter is not a function type, an
+ /// empty iterable should be returned.
+ ///
+ /// Should be overridden by the client.
+ Iterable<TypeVariable> typeVarsFreeInClosureArguments(Closure closure);
+
+ /// If the type of the parameter corresponding to [closure] is a function
+ /// type, the set of type parameters referred to by the return type of that
+ /// parameter. If the type of the parameter is not a function type, the set
+ /// type parameters referred to by the type of the parameter should be
+ /// returned.
+ ///
+ /// Should be overridden by the client.
+ Iterable<TypeVariable> typeVarsFreeInClosureReturns(Closure closure);
+}
+
+/// Node type representing a single [Closure] for purposes of walking the
+/// graph of type inference dependencies among closures.
+class _ClosureNode<Closure> extends Node<_ClosureNode<Closure>> {
+ /// The [Closure] being represented by this node.
+ final Closure closure;
+
+ /// If not `null`, the index of the reconciliation stage to which this closure
+ /// has been assigned.
+ int? stageNum;
+
+ /// The nodes for the closures depended on by this closure.
+ final List<_ClosureNode<Closure>> dependencies = [];
+
+ _ClosureNode(this.closure);
+
+ @override
+ bool get isEvaluated => stageNum != null;
+
+ @override
+ List<_ClosureNode<Closure>> computeDependencies() => dependencies;
+}
+
+/// Derived class of [DependencyWalker] capable of walking the graph of type
+/// inference dependencies among closures.
+class _DependencyWalker<Closure>
+ extends DependencyWalker<_ClosureNode<Closure>> {
+ /// The set of closure reconciliation stages accumulated so far.
+ final List<Set<Closure>> closureReconciliationStages = [];
+
+ @override
+ void evaluate(_ClosureNode v) => evaluateScc([v]);
+
+ @override
+ void evaluateScc(List<_ClosureNode> nodes) {
+ int stageNum = 0;
+ for (_ClosureNode node in nodes) {
+ for (_ClosureNode dependency in node.dependencies) {
+ int? dependencyStageNum = dependency.stageNum;
+ if (dependencyStageNum != null && dependencyStageNum >= stageNum) {
+ stageNum = dependencyStageNum + 1;
+ }
+ }
+ }
+ if (closureReconciliationStages.length <= stageNum) {
+ closureReconciliationStages.add({});
+ // `stageNum` can't grow by more than 1 each time `evaluateScc` is called,
+ // so adding one stage is sufficient to make sure the list is now long
+ // enough.
+ assert(stageNum < closureReconciliationStages.length);
+ }
+ Set<Closure> stage = closureReconciliationStages[stageNum];
+ for (_ClosureNode node in nodes) {
+ node.stageNum = stageNum;
+ stage.add(node.closure);
+ }
+ }
+}
diff --git a/pkg/_fe_analyzer_shared/test/deferred_closure_heuristic_test.dart b/pkg/_fe_analyzer_shared/test/deferred_closure_heuristic_test.dart
new file mode 100644
index 0000000..ab4b8f9
--- /dev/null
+++ b/pkg/_fe_analyzer_shared/test/deferred_closure_heuristic_test.dart
@@ -0,0 +1,138 @@
+// Copyright (c) 2022, 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:_fe_analyzer_shared/src/deferred_closure_heuristic.dart';
+import 'package:test/test.dart';
+
+main() {
+ test('single', () {
+ // If there is just a single closure and no type variables, it is selected.
+ var f = Closure('f');
+ expect(
+ _TestClosureDeps(typeVars: [], closures: [f])
+ .planClosureReconciliationStages(),
+ [
+ {f}
+ ]);
+ });
+
+ test('simple dependency', () {
+ // If f depends on g, then g is selected first, and then f.
+ var f = Closure('f', argTypes: ['T']);
+ var g = Closure('g', retTypes: ['T']);
+ expect(
+ _TestClosureDeps(typeVars: ['T'], closures: [f, g])
+ .planClosureReconciliationStages(),
+ [
+ {g},
+ {f}
+ ]);
+ });
+
+ test('long chain', () {
+ // If f depends on g and g depends on h, then we do three separate stages:
+ // h, then g, then f.
+ var f = Closure('f', argTypes: ['T']);
+ var g = Closure('g', argTypes: ['U'], retTypes: ['T']);
+ var h = Closure('h', retTypes: ['U']);
+ expect(
+ _TestClosureDeps(typeVars: ['T', 'U'], closures: [f, g, h])
+ .planClosureReconciliationStages(),
+ [
+ {h},
+ {g},
+ {f}
+ ]);
+ });
+
+ test('unrelated closure', () {
+ // Closures that are independent of all the others are inferred during the
+ // first stage.
+ var f = Closure('f', argTypes: ['T']);
+ var g = Closure('g', retTypes: ['T']);
+ var h = Closure('h');
+ expect(
+ _TestClosureDeps(typeVars: ['T', 'U'], closures: [f, g, h])
+ .planClosureReconciliationStages(),
+ [
+ {g, h},
+ {f}
+ ]);
+ });
+
+ test('independent chains', () {
+ // If f depends on g, and h depends on i, then g and i are selected first,
+ // and then f and h.
+ var f = Closure('f', argTypes: ['T']);
+ var g = Closure('g', retTypes: ['T']);
+ var h = Closure('h', argTypes: ['U']);
+ var i = Closure('i', retTypes: ['U']);
+ expect(
+ _TestClosureDeps(typeVars: ['T', 'U'], closures: [f, g, h, i])
+ .planClosureReconciliationStages(),
+ [
+ {g, i},
+ {f, h}
+ ]);
+ });
+
+ test('diamond', () {
+ // Test a diamond dependency shape: f depends on g and h; g and h both
+ // depend on i.
+ var f = Closure('f', argTypes: ['T', 'U']);
+ var g = Closure('g', argTypes: ['V'], retTypes: ['T']);
+ var h = Closure('h', argTypes: ['V'], retTypes: ['U']);
+ var i = Closure('i', retTypes: ['V']);
+ expect(
+ _TestClosureDeps(typeVars: ['T', 'U', 'V'], closures: [f, g, h, i])
+ .planClosureReconciliationStages(),
+ [
+ {i},
+ {g, h},
+ {f}
+ ]);
+ });
+
+ test('cycle', () {
+ // A dependency cycle is inferred all at once.
+ var f = Closure('f', argTypes: ['T']);
+ var g = Closure('g', argTypes: ['U']);
+ var h = Closure('h', argTypes: ['U'], retTypes: ['T']);
+ var i = Closure('i', argTypes: ['T'], retTypes: ['U']);
+ expect(
+ _TestClosureDeps(typeVars: ['T', 'U'], closures: [f, g, h, i])
+ .planClosureReconciliationStages(),
+ [
+ {h, i},
+ {f, g}
+ ]);
+ });
+}
+
+class Closure {
+ final String name;
+ final List<String> argTypes;
+ final List<String> retTypes;
+
+ Closure(this.name, {this.argTypes = const [], this.retTypes = const []});
+
+ @override
+ String toString() => name;
+}
+
+class _TestClosureDeps extends ClosureDependencies<String, Closure> {
+ final List<String> typeVars;
+ final List<Closure> closures;
+
+ _TestClosureDeps({required this.typeVars, required this.closures})
+ : super(closures, typeVars);
+
+ @override
+ Set<String> typeVarsFreeInClosureArguments(Closure closure) =>
+ closure.argTypes.toSet();
+
+ @override
+ Set<String> typeVarsFreeInClosureReturns(Closure closure) =>
+ closure.retTypes.toSet();
+}
diff --git a/pkg/front_end/test/spell_checking_list_code.txt b/pkg/front_end/test/spell_checking_list_code.txt
index 5b21bf7..a85eeaf 100644
--- a/pkg/front_end/test/spell_checking_list_code.txt
+++ b/pkg/front_end/test/spell_checking_list_code.txt
@@ -245,6 +245,7 @@
connectivity
consideration
constness
+constraining
consult
consumers
container
@@ -320,6 +321,7 @@
demangle
demangled
dep
+depended
dependency's
deps
dereferencing
@@ -1024,6 +1026,7 @@
recompiling
recompute
recomputed
+reconciliation
reconstruct
recorder
recoveries
@@ -1038,6 +1041,7 @@
reexports
ref
refactoring
+refined
reflect
reflectee
reflective
@@ -1214,6 +1218,7 @@
stability
stacktrace
stacktraces
+stages
stale
stand
starter
