[analyzer] Faster export scope calculation in bad cases
With the `big_chain_benchmark` for ImportExportCycle and
ImportCycleExportChain it scales a lot better. The other ones
(ImportCycle, ImportChain, ImportExportChain) doesn't change.
For ImportExportCycle, in AOT mode, before we got:
```
+------+-----------+------------+------------+
| Size | Initial | Completion | Fully done |
+------+-----------+------------+------------+
| 16 | 0.46673 | 0.169486 | 0.406448 |
| 32 | 0.875871 | 0.242876 | 0.85543 |
| 64 | 1.583077 | 0.465915 | 1.506953 |
| 128 | 3.198071 | 0.903894 | 3.09165 |
| 256 | 6.786677 | 2.149489 | 6.779569 |
| 512 | 17.346131 | 8.92149 | 17.971033 |
| 1024 | 63.358453 | 46.152089 | 65.401559 |
+------+-----------+------------+------------+
```
now instead we get:
```
+------+-----------+------------+------------+
| Size | Initial | Completion | Fully done |
+------+-----------+------------+------------+
| 16 | 0.474942 | 0.166857 | 0.411457 |
| 32 | 0.834925 | 0.243397 | 0.76843 |
| 64 | 1.608813 | 0.439885 | 1.53438 |
| 128 | 3.198453 | 0.805756 | 3.302559 |
| 256 | 6.347211 | 1.712426 | 6.165624 |
| 512 | 12.874747 | 3.551489 | 13.1461 |
| 1024 | 27.14403 | 7.844261 | 27.32785 |
+------+-----------+------------+------------+
```
An almost 6x improvement for completion and 2x+ improvement for both
initial analysis and analysing after the change.
For ImportCycleExportChain, in AOT mode, before we got:
```
+------+-----------+------------+------------+
| Size | Initial | Completion | Fully done |
+------+-----------+------------+------------+
| 16 | 0.454349 | 0.152505 | 0.400889 |
| 32 | 0.892146 | 0.302407 | 0.81263 |
| 64 | 1.67604 | 0.439954 | 1.517379 |
| 128 | 3.335087 | 0.907002 | 3.262481 |
| 256 | 6.378526 | 1.943725 | 6.292922 |
| 512 | 15.477861 | 6.461358 | 15.560008 |
| 1024 | 50.671197 | 33.14349 | 51.689455 |
+------+-----------+------------+------------+
```
now instead we get:
```
+------+-----------+------------+------------+
| Size | Initial | Completion | Fully done |
+------+-----------+------------+------------+
| 16 | 0.548357 | 0.166257 | 0.415632 |
| 32 | 0.906483 | 0.296618 | 0.910544 |
| 64 | 1.623723 | 0.464061 | 1.527888 |
| 128 | 3.067769 | 0.801507 | 2.927981 |
| 256 | 6.224551 | 1.596711 | 6.098531 |
| 512 | 12.941757 | 3.277487 | 12.345753 |
| 1024 | 25.870713 | 7.020787 | 25.760605 |
+------+-----------+------------+------------+
```
A ~4.7x improvement on completion and ~2x improvement for both initial
analysis and analysing after the change.
Change-Id: I052879c1695ad5f0aa63c2d96013a1e3eae96428
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/413421
Reviewed-by: Lasse Nielsen <lrn@google.com>
Commit-Queue: Jens Johansen <jensj@google.com>
diff --git a/pkg/analyzer/lib/src/summary2/export.dart b/pkg/analyzer/lib/src/summary2/export.dart
index 0a20b67..542214a 100644
--- a/pkg/analyzer/lib/src/summary2/export.dart
+++ b/pkg/analyzer/lib/src/summary2/export.dart
@@ -61,6 +61,7 @@
});
void addLocation(ExportLocation location) {
+ // This list is very small, contains on it is probably ok.
if (!locations.contains(location)) {
locations.add(location);
}
diff --git a/pkg/analyzer/lib/src/summary2/link.dart b/pkg/analyzer/lib/src/summary2/link.dart
index a908e30..bd801f6 100644
--- a/pkg/analyzer/lib/src/summary2/link.dart
+++ b/pkg/analyzer/lib/src/summary2/link.dart
@@ -15,6 +15,7 @@
import 'package:analyzer/src/fine/library_manifest.dart';
import 'package:analyzer/src/summary2/bundle_writer.dart';
import 'package:analyzer/src/summary2/detach_nodes.dart';
+import 'package:analyzer/src/summary2/export.dart';
import 'package:analyzer/src/summary2/library_builder.dart';
import 'package:analyzer/src/summary2/linked_element_factory.dart';
import 'package:analyzer/src/summary2/reference.dart';
@@ -179,19 +180,47 @@
}
}
- while (true) {
- var hasChanges = false;
+ // We keep a queue of exports to propagate.
+ // First we loop over every reference that both exports and is exported,
+ // but then we only process the exports that should be propagated.
+ var additionalExportData = <_AdditionalExport>[];
+
+ void addExport(Export export, String name, ExportedReference reference) {
+ if (export.addToExportScope(name, reference)) {
+ // We've added [name] to [export.exporter]s export scope.
+ // We need to propagate that to anyone that exports that library.
+ additionalExportData
+ .add(_AdditionalExport(export.exporter, name, reference));
+ }
+ }
+
+ for (var exported in both) {
+ for (var export in exported.exports) {
+ exported.exportScope.forEach((name, reference) {
+ addExport(export, name, reference);
+ });
+ }
+ }
+
+ while (additionalExportData.isNotEmpty) {
+ var data = additionalExportData.removeLast();
+ for (var export in data.exported.exports) {
+ addExport(export, data.name, data.reference);
+ }
+ }
+
+ assert(() {
for (var exported in both) {
for (var export in exported.exports) {
exported.exportScope.forEach((name, reference) {
if (export.addToExportScope(name, reference)) {
- hasChanges = true;
+ throw "Error in export calculation: Assert failed.";
}
});
}
}
- if (!hasChanges) break;
- }
+ return true;
+ }(), true);
for (var library in builders.values) {
library.storeExportScope();
@@ -362,3 +391,11 @@
required this.resolutionBytes,
});
}
+
+class _AdditionalExport {
+ final LibraryBuilder exported;
+ final String name;
+ final ExportedReference reference;
+
+ _AdditionalExport(this.exported, this.name, this.reference);
+}
diff --git a/tests/language/export/bigger_cyclic_helper_1.dart b/tests/language/export/bigger_cyclic_helper_1.dart
new file mode 100644
index 0000000..b9a8a99
--- /dev/null
+++ b/tests/language/export/bigger_cyclic_helper_1.dart
@@ -0,0 +1,18 @@
+// Copyright (c) 2025, 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 "bigger_cyclic_helper_2.dart";
+export "bigger_cyclic_helper_2.dart";
+
+void get2(int i) {
+ print("2: $i");
+ if (i > 0) {
+ get1(i - 1);
+ get2(i - 1);
+ get3(i - 1);
+ get4(i - 1);
+ get5(i - 1);
+ get6(i - 1);
+ }
+}
diff --git a/tests/language/export/bigger_cyclic_helper_2.dart b/tests/language/export/bigger_cyclic_helper_2.dart
new file mode 100644
index 0000000..3857708
--- /dev/null
+++ b/tests/language/export/bigger_cyclic_helper_2.dart
@@ -0,0 +1,18 @@
+// Copyright (c) 2025, 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 "bigger_cyclic_helper_3.dart";
+export "bigger_cyclic_helper_3.dart";
+
+void get3(int i) {
+ print("3: $i");
+ if (i > 0) {
+ get1(i - 1);
+ get2(i - 1);
+ get3(i - 1);
+ get4(i - 1);
+ get5(i - 1);
+ get6(i - 1);
+ }
+}
diff --git a/tests/language/export/bigger_cyclic_helper_3.dart b/tests/language/export/bigger_cyclic_helper_3.dart
new file mode 100644
index 0000000..109347f
--- /dev/null
+++ b/tests/language/export/bigger_cyclic_helper_3.dart
@@ -0,0 +1,18 @@
+// Copyright (c) 2025, 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 "bigger_cyclic_helper_4.dart";
+export "bigger_cyclic_helper_4.dart";
+
+void get4(int i) {
+ print("4: $i");
+ if (i > 0) {
+ get1(i - 1);
+ get2(i - 1);
+ get3(i - 1);
+ get4(i - 1);
+ get5(i - 1);
+ get6(i - 1);
+ }
+}
diff --git a/tests/language/export/bigger_cyclic_helper_4.dart b/tests/language/export/bigger_cyclic_helper_4.dart
new file mode 100644
index 0000000..00bea4e
--- /dev/null
+++ b/tests/language/export/bigger_cyclic_helper_4.dart
@@ -0,0 +1,18 @@
+// Copyright (c) 2025, 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 "bigger_cyclic_helper_5.dart";
+export "bigger_cyclic_helper_5.dart";
+
+void get5(int i) {
+ print("5: $i");
+ if (i > 0) {
+ get1(i - 1);
+ get2(i - 1);
+ get3(i - 1);
+ get4(i - 1);
+ get5(i - 1);
+ get6(i - 1);
+ }
+}
diff --git a/tests/language/export/bigger_cyclic_helper_5.dart b/tests/language/export/bigger_cyclic_helper_5.dart
new file mode 100644
index 0000000..4b1086a
--- /dev/null
+++ b/tests/language/export/bigger_cyclic_helper_5.dart
@@ -0,0 +1,18 @@
+// Copyright (c) 2025, 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 "bigger_cyclic_test.dart";
+export "bigger_cyclic_test.dart";
+
+void get6(int i) {
+ print("6: $i");
+ if (i > 0) {
+ get1(i - 1);
+ get2(i - 1);
+ get3(i - 1);
+ get4(i - 1);
+ get5(i - 1);
+ get6(i - 1);
+ }
+}
diff --git a/tests/language/export/bigger_cyclic_test.dart b/tests/language/export/bigger_cyclic_test.dart
new file mode 100644
index 0000000..b321be0
--- /dev/null
+++ b/tests/language/export/bigger_cyclic_test.dart
@@ -0,0 +1,22 @@
+// Copyright (c) 2025, 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 "bigger_cyclic_helper_1.dart";
+export "bigger_cyclic_helper_1.dart";
+
+void main() {
+ get1(1);
+}
+
+void get1(int i) {
+ print("1: $i");
+ if (i > 0) {
+ get1(i - 1);
+ get2(i - 1);
+ get3(i - 1);
+ get4(i - 1);
+ get5(i - 1);
+ get6(i - 1);
+ }
+}
