Version 2.17.0-23.0.dev
Merge commit 'ae593598f8a7708a40c37ab57b5f85d61b65224c' into 'dev'
diff --git a/pkg/front_end/benchmarks/patterns/test_lists.dart b/pkg/front_end/benchmarks/patterns/test_lists.dart
new file mode 100644
index 0000000..4a20f36
--- /dev/null
+++ b/pkg/front_end/benchmarks/patterns/test_lists.dart
@@ -0,0 +1,271 @@
+// 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 'util.dart';
+
+typedef TestFunction<T> = List<T> Function(List<T>);
+
+class InputOutputData<T> {
+ final List<T> input;
+ final List<T> output;
+
+ const InputOutputData(this.input, this.output);
+}
+
+const Strategy simpleAddStrategy = Strategy('simple-add', '''
+Add entries to a list one at a time.''');
+
+const Strategy spreadStrategy = Strategy('spread', '''
+Create the list via spreads.''');
+
+const Strategy listGenerateGrowableStrategy =
+ Strategy('list-generate-growable', '''
+Create list via List.generate with growable = true.''');
+
+const Strategy listGenerateNotGrowableStrategy =
+ Strategy('list-generate-not-growable', '''
+Create list via List.generate with growable = false.''');
+
+const Strategy listFilledGrowableStrategy = Strategy('list-filled-growable', '''
+Create list via List.generate with growable = true.''');
+
+const Strategy listFilledNotGrowableStrategy =
+ Strategy('list-filled-not-growable', '''
+Create list via List.generate with growable = false.''');
+
+const Strategy listFilledAlternativeGrowableStrategy =
+ Strategy('list-filled-alt-growable', '''
+Create list via List.generate with growable = true in an alternative way.''');
+
+const Strategy listFilledAlternativeNotGrowableStrategy =
+ Strategy('list-filled-alt-not-growable', '''
+Create list via List.generate with growable = false in an alternative way.''');
+
+const Scenario emptyScenario = Scenario('empty', '''
+The input and output is empty.''');
+const Scenario oneEntryScenario = Scenario('one', '''
+The input is one entry.''');
+const Scenario severalEntriesScenario = Scenario('several', '''
+The input has several entries.''');
+
+Map<Scenario, InputOutputData<String>> scenarios = {
+ emptyScenario: const InputOutputData([], []),
+ oneEntryScenario: const InputOutputData(["a"], ["<", "a", ">"]),
+ severalEntriesScenario: const InputOutputData(
+ [
+ "a",
+ "b",
+ "c",
+ "d",
+ "e",
+ "f",
+ "g",
+ ],
+ [
+ "<",
+ "a",
+ ", ",
+ "b",
+ ", ",
+ "c",
+ ", ",
+ "d",
+ ", ",
+ "e",
+ ", ",
+ "f",
+ ", ",
+ "g",
+ ">",
+ ],
+ ),
+};
+
+class Test<T> {
+ final int size;
+ final Map<Strategy, TestFunction<T>> strategies;
+
+ const Test(this.size, this.strategies);
+
+ void _test(Registry registry, SeriesKey key, int runs, int iterations,
+ List<T> input, List<T> expectedResult, TestFunction<T> testFunction) {
+ for (int run = 0; run < runs; run++) {
+ Stopwatch sw = new Stopwatch();
+ for (int i = 0; i < iterations; i++) {
+ sw.start();
+ List<T> actualOutput = testFunction(input);
+ sw.stop();
+ checkEquals(actualOutput, expectedResult);
+ }
+ registry.registerData(key, size, sw.elapsedMicroseconds);
+ }
+ }
+
+ void checkEquals(List<T> a, List<T> b) {
+ if (a.length != b.length) throw "length for $a vs $b";
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i]) throw "index $i for $a vs $b";
+ }
+ }
+
+ void performTest(
+ {required Registry registry,
+ required int runs,
+ required int iterations,
+ required Map<Scenario, InputOutputData<T>> scenarios}) {
+ for (MapEntry<Scenario, InputOutputData<T>> scenario in scenarios.entries) {
+ List<T> scenarioInput = scenario.value.input;
+ List<T> scenarioExpectedOutput = scenario.value.output;
+ for (MapEntry<Strategy, TestFunction<T>> entry in strategies.entries) {
+ _test(registry, new SeriesKey(entry.key, scenario.key), runs,
+ iterations, scenarioInput, scenarioExpectedOutput, entry.value);
+ }
+ }
+ }
+}
+
+List<Test<String>> tests = [
+ // "size" isn't used here...
+ Test<String>(-1, {
+ simpleAddStrategy: simplyAdd,
+ listGenerateGrowableStrategy: listGenerateGrowable,
+ listGenerateNotGrowableStrategy: listGenerateNotGrowable,
+ listFilledGrowableStrategy: listFilledGrowable,
+ listFilledNotGrowableStrategy: listFilledNotGrowable,
+ listFilledAlternativeGrowableStrategy: listFilledAlternativeGrowable,
+ listFilledAlternativeNotGrowableStrategy: listFilledAlternativeNotGrowable,
+ spreadStrategy: spread,
+ }),
+];
+
+List<String> simplyAdd(List<String> input) {
+ if (input.isEmpty) return [];
+ List<String> result = [];
+ result.add("<");
+ result.add(input[0]);
+ for (int i = 1; i < input.length; i++) {
+ result.add(", ");
+ result.add(input[i]);
+ }
+ result.add(">");
+ return result;
+}
+
+List<String> listGenerateGrowable(List<String> input) {
+ if (input.isEmpty) return [];
+ int size = input.length * 2 + 1;
+ return List<String>.generate(size, (index) {
+ if (index == 0) return "<";
+ if (index == size - 1) return ">";
+ if (index.isEven) return ", ";
+ return input[index >> 1];
+ }, growable: true);
+}
+
+List<String> listGenerateNotGrowable(List<String> input) {
+ if (input.isEmpty) return [];
+ int size = input.length * 2 + 1;
+ return List<String>.generate(size, (index) {
+ if (index == 0) return "<";
+ if (index == size - 1) return ">";
+ if (index.isEven) return ", ";
+ return input[index >> 1];
+ }, growable: false);
+}
+
+List<String> listFilledAlternativeGrowable(List<String> input) {
+ if (input.isEmpty) return [];
+ int size = input.length * 2 + 1;
+ List<String> result = List<String>.filled(size, ", ", growable: true);
+ for (int i = 0; i < input.length; i++) {
+ result[(i << 1) + 1] = input[i];
+ }
+ result[0] = "<";
+ result[result.length - 1] = ">";
+
+ return result;
+}
+
+List<String> listFilledAlternativeNotGrowable(List<String> input) {
+ if (input.isEmpty) return [];
+ int size = input.length * 2 + 1;
+ List<String> result = List<String>.filled(size, ", ", growable: false);
+ for (int i = 0; i < input.length; i++) {
+ result[(i << 1) + 1] = input[i];
+ }
+ result[0] = "<";
+ result[result.length - 1] = ">";
+
+ return result;
+}
+
+List<String> listFilledGrowable(List<String> input) {
+ if (input.isEmpty) return [];
+ int size = input.length * 2 + 1;
+ List<String> result = List<String>.filled(size, "", growable: true);
+ int j = 0;
+ result[j++] = "<";
+ result[j++] = input[0];
+ for (int i = 1; i < input.length; i++) {
+ result[j++] = ", ";
+ result[j++] = input[i];
+ }
+ result[j++] = ">";
+
+ return result;
+}
+
+List<String> listFilledNotGrowable(List<String> input) {
+ if (input.isEmpty) return [];
+ int size = input.length * 2 + 1;
+ List<String> result = List<String>.filled(size, "", growable: false);
+ int j = 0;
+ result[j++] = "<";
+ result[j++] = input[0];
+ for (int i = 1; i < input.length; i++) {
+ result[j++] = ", ";
+ result[j++] = input[i];
+ }
+ result[j++] = ">";
+
+ return result;
+}
+
+List<String> spread(List<String> input) {
+ return [
+ if (input.isNotEmpty) ...[
+ '<',
+ input.first,
+ for (String s in input.skip(1)) ...[', ', s],
+ '>',
+ ]
+ ];
+}
+
+void main() {
+ // Dry run
+ for (Test test in tests) {
+ test.performTest(
+ registry: new Registry(),
+ runs: 5,
+ iterations: 10,
+ scenarios: scenarios);
+ }
+ // Actual test
+ Registry registry = new Registry();
+ for (Test test in tests) {
+ test.performTest(
+ registry: registry, runs: 10, iterations: 100000, scenarios: scenarios);
+ }
+ SeriesSet seriesSet = registry.generateSeriesSet();
+ print('== Raw data ==');
+ for (Scenario scenario in scenarios.keys) {
+ print(seriesSet.getFullSpreadByScenario(scenario));
+ }
+ print('== Reduced averages ==');
+ SeriesSet reducedSeriesSet = seriesSet.filter((list) => removeMax(list, 3));
+ for (Scenario scenario in scenarios.keys) {
+ print(reducedSeriesSet.getAveragedSpreadByScenario(scenario));
+ }
+}
diff --git a/pkg/kernel/lib/util/graph.dart b/pkg/kernel/lib/util/graph.dart
index 105b170b..eef4b6b 100644
--- a/pkg/kernel/lib/util/graph.dart
+++ b/pkg/kernel/lib/util/graph.dart
@@ -208,3 +208,37 @@
/// That is, `layers[i]` contain the list of vertices with index `i`.
final List<List<T>> layers = [];
}
+
+/// Find vertices in [graph] that either is in [vertices], has a neighbor in
+/// [vertices], has a neighbor of a neighbor (etc) in [vertices].
+Set<T> calculateTransitiveDependenciesOf<T>(Graph<T> graph, Set<T> vertices) {
+ // Compute direct dependencies for each vertex (the reverse of the
+ // edges returned by `graph.neighborsOf`).
+ Map<T, Set<T>> directDependencies = <T, Set<T>>{};
+ List<T> workList = [];
+ {
+ for (T vertex in graph.vertices) {
+ if (vertices.contains(vertex)) workList.add(vertex);
+ for (T neighbor in graph.neighborsOf(vertex)) {
+ (directDependencies[neighbor] ??= new Set<T>()).add(vertex);
+ if (vertices.contains(neighbor)) workList.add(vertex);
+ }
+ }
+ }
+
+ // Collect and remove all dependencies.
+ Set<T> left = new Set<T>.from(graph.vertices);
+ Set<T> transitive = {};
+ while (workList.isNotEmpty) {
+ T removed = workList.removeLast();
+ if (left.remove(removed)) {
+ Set<T>? s = directDependencies[removed];
+ if (s != null) {
+ // [s] is null for leaves.
+ workList.addAll(s);
+ }
+ transitive.add(removed);
+ }
+ }
+ return transitive;
+}
diff --git a/pkg/kernel/test/graph_test.dart b/pkg/kernel/test/graph_test.dart
index 83827be..cbcb0d1 100644
--- a/pkg/kernel/test/graph_test.dart
+++ b/pkg/kernel/test/graph_test.dart
@@ -556,4 +556,103 @@
[F]
]
]);
+
+ testTransitiveDependencies(graphData: {
+ A: [B],
+ B: [A],
+ }, of: {
+ A
+ }, expected: {
+ A,
+ B,
+ });
+
+ testTransitiveDependencies(graphData: {}, of: {
+ A,
+ B,
+ C,
+ D,
+ E,
+ F,
+ }, expected: {});
+
+ {
+ String MAIN = "MAIN";
+ String DARTFFI = "DARTFFI";
+ testTransitiveDependencies(graphData: {
+ MAIN: [DARTFFI],
+ }, of: {
+ DARTFFI
+ }, expected: {
+ MAIN,
+ });
+ }
+
+ testTransitiveDependencies(graphData: {
+ A: [B],
+ B: [C],
+ C: [B, D],
+ D: [C],
+ E: [A],
+ F: [B],
+ }, of: {
+ A
+ }, expected: {
+ A,
+ E
+ });
+
+ {
+ String MAIN = "MAIN";
+ String TARGET = "TARGET";
+
+ testTransitiveDependencies(graphData: {
+ MAIN: [A, E],
+ A: [B],
+ B: [A, C],
+ C: [TARGET],
+ D: [],
+ E: [D],
+ }, of: {
+ TARGET,
+ }, expected: {
+ C,
+ B,
+ A,
+ MAIN,
+ });
+
+ testTransitiveDependencies(graphData: {
+ MAIN: [A, E],
+ A: [B],
+ B: [A, C],
+ C: [],
+ D: [],
+ E: [D],
+ }, of: {
+ TARGET,
+ }, expected: {});
+
+ testTransitiveDependencies(graphData: {
+ MAIN: [A, C, E, TARGET],
+ A: [B],
+ B: [A, C],
+ C: [],
+ D: [],
+ E: [D],
+ }, of: {
+ TARGET,
+ }, expected: {
+ MAIN,
+ });
+ }
+}
+
+void testTransitiveDependencies(
+ {required Set<String> of,
+ required Set<String> expected,
+ required Map<String, List<String>> graphData}) {
+ Graph<String> graph = new TestGraph(graphData);
+ Set<String> actual = calculateTransitiveDependenciesOf(graph, of);
+ Expect.setEquals(expected, actual);
}
diff --git a/pkg/vm/lib/target/vm.dart b/pkg/vm/lib/target/vm.dart
index da77a9e..b1a60d8 100644
--- a/pkg/vm/lib/target/vm.dart
+++ b/pkg/vm/lib/target/vm.dart
@@ -18,7 +18,8 @@
import '../transformations/call_site_annotator.dart' as callSiteAnnotator;
import '../transformations/lowering.dart' as lowering
show transformLibraries, transformProcedure;
-import '../transformations/ffi/common.dart' as ffiHelper show importsFfi;
+import '../transformations/ffi/common.dart' as ffiHelper
+ show calculateTransitiveImportsOfDartFfiIfUsed;
import '../transformations/ffi/definitions.dart' as transformFfiDefinitions
show transformLibraries;
import '../transformations/ffi/native.dart' as transformFfiNative
@@ -154,7 +155,9 @@
this, coreTypes, hierarchy, libraries, referenceFromIndex);
logger?.call("Transformed mixin applications");
- if (!ffiHelper.importsFfi(component, libraries)) {
+ List<Library>? transitiveImportingDartFfi = ffiHelper
+ .calculateTransitiveImportsOfDartFfiIfUsed(component, libraries);
+ if (transitiveImportingDartFfi == null) {
logger?.call("Skipped ffi transformation");
} else {
// Transform @FfiNative(..) functions into FFI native call functions.
@@ -163,21 +166,19 @@
// Transform arguments that extend NativeFieldWrapperClass1 to Pointer if
// the native function expects Pointer (to avoid Handle overhead).
transformFfiNative.transformLibraries(component, coreTypes, hierarchy,
- libraries, diagnosticReporter, referenceFromIndex);
+ transitiveImportingDartFfi, diagnosticReporter, referenceFromIndex);
logger?.call("Transformed ffi natives");
- // TODO(jensj/dacoharkes): We can probably limit the transformations to
- // libraries that transitivley depend on dart:ffi.
transformFfiDefinitions.transformLibraries(
component,
coreTypes,
hierarchy,
- libraries,
+ transitiveImportingDartFfi,
diagnosticReporter,
referenceFromIndex,
changedStructureNotifier);
transformFfiUseSites.transformLibraries(component, coreTypes, hierarchy,
- libraries, diagnosticReporter, referenceFromIndex);
+ transitiveImportingDartFfi, diagnosticReporter, referenceFromIndex);
logger?.call("Transformed ffi annotations");
}
diff --git a/pkg/vm/lib/transformations/ffi/common.dart b/pkg/vm/lib/transformations/ffi/common.dart
index 4446159..c23bddb 100644
--- a/pkg/vm/lib/transformations/ffi/common.dart
+++ b/pkg/vm/lib/transformations/ffi/common.dart
@@ -16,6 +16,7 @@
import 'package:kernel/type_algebra.dart' show Substitution;
import 'package:kernel/type_environment.dart'
show TypeEnvironment, SubtypeCheckMode;
+import 'package:kernel/util/graph.dart' as kernelGraph;
import 'abi.dart';
import 'native_type_cfe.dart';
@@ -980,18 +981,61 @@
}
}
+/// Returns all libraries including the ones from component except for platform
+/// libraries that are only in component.
+Set<Library> _getAllRelevantLibraries(
+ Component component, List<Library> libraries) {
+ Set<Library> allLibs = {};
+ allLibs.addAll(libraries);
+ for (Library lib in component.libraries) {
+ // Skip real dart: libraries. dart:core imports dart:ffi, but that doesn't
+ // mean we have to transform anything.
+ if (lib.importUri.scheme == "dart" && !lib.isSynthetic) continue;
+ allLibs.add(lib);
+ }
+ return allLibs;
+}
+
/// Checks if any library depends on dart:ffi.
-bool importsFfi(Component component, List<Library> libraries) {
- Set<Library> allLibs = {...component.libraries, ...libraries};
+Library? importsFfi(Component component, List<Library> libraries) {
final Uri dartFfiUri = Uri.parse("dart:ffi");
+ Set<Library> allLibs = _getAllRelevantLibraries(component, libraries);
for (Library lib in allLibs) {
for (LibraryDependency dependency in lib.dependencies) {
- if (dependency.targetLibrary.importUri == dartFfiUri) {
- return true;
+ Library targetLibrary = dependency.targetLibrary;
+ if (targetLibrary.importUri == dartFfiUri) {
+ return targetLibrary;
}
}
}
- return false;
+ return null;
+}
+
+/// Calculates the libraries in [libraries] that transitively imports dart:ffi.
+///
+/// Returns null if dart:ffi is not imported.
+List<Library>? calculateTransitiveImportsOfDartFfiIfUsed(
+ Component component, List<Library> libraries) {
+ Set<Library> allLibs = _getAllRelevantLibraries(component, libraries);
+
+ final Uri dartFfiUri = Uri.parse("dart:ffi");
+ Library? dartFfi;
+ canFind:
+ for (Library lib in allLibs) {
+ for (LibraryDependency dependency in lib.dependencies) {
+ Library targetLibrary = dependency.targetLibrary;
+ if (targetLibrary.importUri == dartFfiUri) {
+ dartFfi = targetLibrary;
+ break canFind;
+ }
+ }
+ }
+ if (dartFfi == null) return null;
+
+ kernelGraph.LibraryGraph graph = new kernelGraph.LibraryGraph(allLibs);
+ Set<Library> result =
+ kernelGraph.calculateTransitiveDependenciesOf(graph, {dartFfi});
+ return (result..retainAll(libraries)).toList();
}
extension on Map<Abi, Object?> {
diff --git a/tools/VERSION b/tools/VERSION
index bb88572..9973e4e 100644
--- a/tools/VERSION
+++ b/tools/VERSION
@@ -27,5 +27,5 @@
MAJOR 2
MINOR 17
PATCH 0
-PRERELEASE 22
+PRERELEASE 23
PRERELEASE_PATCH 0
\ No newline at end of file
