[cfe] Add test for compilation sequence to macro test
This CL adds a test for the minimal sequence of compilation steps
that need to be performed to compile the test while ensuring that
macro declarations are compiled before any application.
Change-Id: Icd6b9140e60d35d2b2b034c16e0807262f971418
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/220768
Reviewed-by: Jens Johansen <jensj@google.com>
Commit-Queue: Johnni Winther <johnniwinther@google.com>
diff --git a/pkg/front_end/lib/src/fasta/kernel/macro.dart b/pkg/front_end/lib/src/fasta/kernel/macro.dart
index 63dff78..249b4ab 100644
--- a/pkg/front_end/lib/src/fasta/kernel/macro.dart
+++ b/pkg/front_end/lib/src/fasta/kernel/macro.dart
@@ -13,6 +13,7 @@
Class? macroClass;
Map<Library, List<Class>> macroDeclarations = {};
Set<Class> macroClasses = {};
+ List<List<Library>> compilationSequence = [];
}
class MacroApplicationData {
diff --git a/pkg/front_end/test/macros/data/tests/declare_macro.dart b/pkg/front_end/test/macros/data/tests/declare_macro.dart
index 58edc63..5d396f7 100644
--- a/pkg/front_end/test/macros/data/tests/declare_macro.dart
+++ b/pkg/front_end/test/macros/data/tests/declare_macro.dart
@@ -3,6 +3,9 @@
// BSD-style license that can be found in the LICENSE file.
/*library:
+ compilationSequence=[
+ package:macro_builder/src/macro.dart,
+ main.dart|package:macro_builder/macro_builder.dart],
declaredMacros=[MyMacro],
macrosAreAvailable
*/
diff --git a/pkg/front_end/test/macros/data/tests/declare_vs_apply/apply_lib.dart b/pkg/front_end/test/macros/data/tests/declare_vs_apply/apply_lib.dart
new file mode 100644
index 0000000..f4e6484
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/declare_vs_apply/apply_lib.dart
@@ -0,0 +1,18 @@
+// Copyright (c) 2021, 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.
+
+/*library:
+ macrosAreApplied,
+ macrosAreAvailable
+*/
+
+import 'macro_lib.dart';
+import 'apply_lib_dep.dart';
+
+@Macro1()
+/*class: Class:
+ appliedMacros=[Macro1],
+ macrosAreApplied
+*/
+class Class extends Super {}
diff --git a/pkg/front_end/test/macros/data/tests/declare_vs_apply/apply_lib_dep.dart b/pkg/front_end/test/macros/data/tests/declare_vs_apply/apply_lib_dep.dart
new file mode 100644
index 0000000..018b909
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/declare_vs_apply/apply_lib_dep.dart
@@ -0,0 +1,7 @@
+// Copyright (c) 2021, 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.
+
+/*library: macrosAreAvailable*/
+
+class Super {}
diff --git a/pkg/front_end/test/macros/data/tests/declare_vs_apply/macro_lib.dart b/pkg/front_end/test/macros/data/tests/declare_vs_apply/macro_lib.dart
new file mode 100644
index 0000000..149d512
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/declare_vs_apply/macro_lib.dart
@@ -0,0 +1,15 @@
+// Copyright (c) 2021, 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.
+
+/*library:
+ declaredMacros=[Macro1],
+ macrosAreAvailable
+*/
+
+import 'package:macro_builder/macro_builder.dart';
+import 'macro_lib_dep.dart';
+
+class Macro1 extends MacroBase implements Macro {
+ const Macro1();
+}
diff --git a/pkg/front_end/test/macros/data/tests/declare_vs_apply/macro_lib_dep.dart b/pkg/front_end/test/macros/data/tests/declare_vs_apply/macro_lib_dep.dart
new file mode 100644
index 0000000..13c27f8
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/declare_vs_apply/macro_lib_dep.dart
@@ -0,0 +1,9 @@
+// Copyright (c) 2021, 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.
+
+/*library: macrosAreAvailable*/
+
+class MacroBase {
+ const MacroBase();
+}
diff --git a/pkg/front_end/test/macros/data/tests/declare_vs_apply/main.dart b/pkg/front_end/test/macros/data/tests/declare_vs_apply/main.dart
new file mode 100644
index 0000000..868f08d
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/declare_vs_apply/main.dart
@@ -0,0 +1,19 @@
+// Copyright (c) 2021, 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.
+
+/*library:
+ compilationSequence=[
+ apply_lib_dep.dart|macro_lib_dep.dart|main_lib_dep.dart|package:macro_builder/src/macro.dart,
+ macro_lib.dart|package:macro_builder/macro_builder.dart,
+ apply_lib.dart|main.dart],
+ macrosAreAvailable
+*/
+
+import 'apply_lib.dart';
+import 'main_lib_dep.dart';
+
+void main() {
+ new Class();
+ method();
+}
diff --git a/pkg/front_end/test/macros/data/tests/declare_vs_apply/main_lib_dep.dart b/pkg/front_end/test/macros/data/tests/declare_vs_apply/main_lib_dep.dart
new file mode 100644
index 0000000..684c9d7
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/declare_vs_apply/main_lib_dep.dart
@@ -0,0 +1,7 @@
+// Copyright (c) 2021, 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.
+
+/*library: macrosAreAvailable*/
+
+void method() {}
diff --git a/pkg/front_end/test/macros/data/tests/direct_import.dart b/pkg/front_end/test/macros/data/tests/direct_import.dart
index b2f6177..f3484cd 100644
--- a/pkg/front_end/test/macros/data/tests/direct_import.dart
+++ b/pkg/front_end/test/macros/data/tests/direct_import.dart
@@ -2,7 +2,12 @@
// 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.
-/*library: macrosAreAvailable*/
+/*library:
+ compilationSequence=[
+ package:macro_builder/src/macro.dart,
+ main.dart],
+ macrosAreAvailable
+*/
// ignore: unused_import
import 'package:macro_builder/src/macro.dart';
diff --git a/pkg/front_end/test/macros/data/tests/import_macro_builder.dart b/pkg/front_end/test/macros/data/tests/import_macro_builder.dart
index 14e5966c..dca3012 100644
--- a/pkg/front_end/test/macros/data/tests/import_macro_builder.dart
+++ b/pkg/front_end/test/macros/data/tests/import_macro_builder.dart
@@ -2,7 +2,12 @@
// 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.
-/*library: macrosAreAvailable*/
+/*library:
+ compilationSequence=[
+ package:macro_builder/src/macro.dart,
+ main.dart|package:macro_builder/macro_builder.dart],
+ macrosAreAvailable
+*/
// ignore: unused_import
import 'package:macro_builder/macro_builder.dart';
diff --git a/pkg/front_end/test/macros/data/tests/import_macro_package.dart b/pkg/front_end/test/macros/data/tests/import_macro_package.dart
index 5e69df3..1fabb48 100644
--- a/pkg/front_end/test/macros/data/tests/import_macro_package.dart
+++ b/pkg/front_end/test/macros/data/tests/import_macro_package.dart
@@ -2,7 +2,13 @@
// 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.
-/*library: macrosAreAvailable*/
+/*library:
+ compilationSequence=[
+ package:macro_builder/src/macro.dart,
+ package:macro/macro.dart|package:macro_builder/macro_builder.dart,
+ main.dart],
+ macrosAreAvailable
+*/
// ignore: unused_import
import 'package:macro/macro.dart';
diff --git a/pkg/front_end/test/macros/data/tests/import_macro_source/main.dart b/pkg/front_end/test/macros/data/tests/import_macro_source/main.dart
index 625315b..5b109f4 100644
--- a/pkg/front_end/test/macros/data/tests/import_macro_source/main.dart
+++ b/pkg/front_end/test/macros/data/tests/import_macro_source/main.dart
@@ -2,7 +2,13 @@
// 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.
-/*library: macrosAreAvailable*/
+/*library:
+ compilationSequence=[
+ package:macro_builder/src/macro.dart,
+ macro_lib.dart|package:macro_builder/macro_builder.dart,
+ main.dart],
+ macrosAreAvailable
+*/
// ignore: unused_import
import 'macro_lib.dart';
diff --git a/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib1.dart b/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib1.dart
new file mode 100644
index 0000000..a05f387
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib1.dart
@@ -0,0 +1,14 @@
+// Copyright (c) 2021, 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.
+
+/*library:
+ declaredMacros=[Macro1],
+ macrosAreAvailable
+*/
+
+import 'package:macro_builder/macro_builder.dart';
+
+class Macro1 implements Macro {
+ const Macro1();
+}
diff --git a/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib2a.dart b/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib2a.dart
new file mode 100644
index 0000000..967801f
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib2a.dart
@@ -0,0 +1,14 @@
+// Copyright (c) 2021, 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.
+
+/*library:
+ declaredMacros=[Macro2a],
+ macrosAreAvailable
+*/
+
+import 'package:macro_builder/macro_builder.dart';
+
+class Macro2a implements Macro {
+ const Macro2a();
+}
diff --git a/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib2b.dart b/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib2b.dart
new file mode 100644
index 0000000..b9bc7d2
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/multiple_macros/macro_lib2b.dart
@@ -0,0 +1,21 @@
+// Copyright (c) 2021, 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.
+
+/*library:
+ declaredMacros=[Macro2b],
+ macrosAreApplied,
+ macrosAreAvailable
+*/
+
+import 'package:macro_builder/macro_builder.dart';
+import 'macro_lib2a.dart';
+
+@Macro2a()
+/*class: Macro2b:
+ appliedMacros=[Macro2a],
+ macrosAreApplied
+*/
+class Macro2b implements Macro {
+ const Macro2b();
+}
diff --git a/pkg/front_end/test/macros/data/tests/multiple_macros/main.dart b/pkg/front_end/test/macros/data/tests/multiple_macros/main.dart
new file mode 100644
index 0000000..1d1f1e5
--- /dev/null
+++ b/pkg/front_end/test/macros/data/tests/multiple_macros/main.dart
@@ -0,0 +1,26 @@
+// Copyright (c) 2021, 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.
+
+/*library:
+ compilationSequence=[
+ package:macro_builder/src/macro.dart,
+ macro_lib1.dart|macro_lib2a.dart|package:macro_builder/macro_builder.dart,
+ macro_lib2b.dart,
+ main.dart],
+ macrosAreApplied,
+ macrosAreAvailable
+*/
+
+import 'macro_lib1.dart';
+import 'macro_lib2a.dart';
+import 'macro_lib2b.dart';
+
+@Macro1()
+@Macro2a()
+@Macro2b()
+/*member: main:appliedMacros=[
+ Macro1,
+ Macro2a,
+ Macro2b]*/
+main() {}
diff --git a/pkg/front_end/test/macros/data/tests/no_import.dart b/pkg/front_end/test/macros/data/tests/no_import.dart
index e5c2fad..fbe2463 100644
--- a/pkg/front_end/test/macros/data/tests/no_import.dart
+++ b/pkg/front_end/test/macros/data/tests/no_import.dart
@@ -2,4 +2,6 @@
// 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.
+/*library: compilationSequence=[main.dart]*/
+
void main() {}
diff --git a/pkg/front_end/test/macros/data/tests/use_macro_package.dart b/pkg/front_end/test/macros/data/tests/use_macro_package.dart
index 09c2b3b..74f18ff 100644
--- a/pkg/front_end/test/macros/data/tests/use_macro_package.dart
+++ b/pkg/front_end/test/macros/data/tests/use_macro_package.dart
@@ -4,6 +4,10 @@
/*library:
appliedMacros=[Macro3],
+ compilationSequence=[
+ package:macro_builder/src/macro.dart,
+ package:macro/macro.dart|package:macro_builder/macro_builder.dart,
+ main.dart],
macrosAreApplied,
macrosAreAvailable
*/
diff --git a/pkg/front_end/test/macros/data/tests/use_macro_source/main.dart b/pkg/front_end/test/macros/data/tests/use_macro_source/main.dart
index f5a3e60..930eb5c 100644
--- a/pkg/front_end/test/macros/data/tests/use_macro_source/main.dart
+++ b/pkg/front_end/test/macros/data/tests/use_macro_source/main.dart
@@ -3,6 +3,10 @@
// BSD-style license that can be found in the LICENSE file.
/*library:
+ compilationSequence=[
+ package:macro_builder/src/macro.dart,
+ macro_lib.dart|package:macro_builder/macro_builder.dart,
+ main.dart],
macrosAreApplied,
macrosAreAvailable
*/
diff --git a/pkg/front_end/test/macros/macro_test.dart b/pkg/front_end/test/macros/macro_test.dart
index bcc7294..8f109a0 100644
--- a/pkg/front_end/test/macros/macro_test.dart
+++ b/pkg/front_end/test/macros/macro_test.dart
@@ -11,6 +11,7 @@
import 'package:front_end/src/fasta/kernel/macro.dart';
import 'package:front_end/src/testing/id_testing_helper.dart';
import 'package:kernel/ast.dart';
+import 'package:kernel/util/graph.dart';
Future<void> main(List<String> args) async {
enableMacros = true;
@@ -70,10 +71,61 @@
class Tags {
static const String macrosAreAvailable = 'macrosAreAvailable';
static const String macrosAreApplied = 'macrosAreApplied';
+ static const String compilationSequence = 'compilationSequence';
static const String declaredMacros = 'declaredMacros';
static const String appliedMacros = 'appliedMacros';
}
+String libraryToString(Library library) {
+ if (library.importUri.scheme == 'package') {
+ return library.importUri.toString();
+ } else if (library.importUri.scheme == 'dart') {
+ return library.importUri.toString();
+ } else {
+ return library.importUri.pathSegments.last;
+ }
+}
+
+String strongComponentToString(Iterable<Library> libraries) {
+ List<String> list = libraries.map(libraryToString).toList();
+ list.sort();
+ return list.join('|');
+}
+
+void computeCompilationSequence(
+ MacroDeclarationData macroDeclarationData, Graph<Library> libraryGraph,
+ {required bool Function(Library) filter}) {
+ List<List<Library>> stronglyConnectedComponents =
+ computeStrongComponents(libraryGraph);
+
+ Graph<List<Library>> strongGraph =
+ new StrongComponentGraph(libraryGraph, stronglyConnectedComponents);
+ List<List<List<Library>>> componentLayers = [];
+ topologicalSort(strongGraph, layers: componentLayers);
+ List<List<Library>> layeredComponents = [];
+ List<Library> currentLayer = [];
+ for (List<List<Library>> layer in componentLayers) {
+ bool declaresMacro = false;
+ for (List<Library> component in layer) {
+ for (Library library in component) {
+ if (filter(library)) continue;
+ if (macroDeclarationData.macroDeclarations.containsKey(library)) {
+ declaresMacro = true;
+ }
+ currentLayer.add(library);
+ }
+ }
+ if (declaresMacro) {
+ layeredComponents.add(currentLayer);
+ currentLayer = [];
+ }
+ }
+ if (currentLayer.isNotEmpty) {
+ layeredComponents.add(currentLayer);
+ }
+ macroDeclarationData.compilationSequence = layeredComponents;
+}
+
class MacroDataExtractor extends CfeDataExtractor<Features> {
late final MacroDeclarationData macroDeclarationData;
late final MacroApplicationData macroApplicationData;
@@ -91,6 +143,13 @@
return macroApplicationData.libraryData[library];
}
+ List<List<Library>> getCompilationSequence() {
+ computeCompilationSequence(macroDeclarationData,
+ new LibraryGraph(compilerResult.component!.libraries),
+ filter: (Library library) => library.importUri.scheme == 'dart');
+ return macroDeclarationData.compilationSequence;
+ }
+
MacroApplications? getLibraryMacroApplications(Library library) {
return getLibraryMacroApplicationData(library)?.libraryApplications;
}
@@ -129,11 +188,28 @@
}
@override
+ Features computeClassValue(Id id, Class node) {
+ Features features = new Features();
+ if (getClassMacroApplicationData(node) != null) {
+ features.add(Tags.macrosAreApplied);
+ }
+ registerMacroApplications(features, getClassMacroApplications(node));
+ return features;
+ }
+
+ @override
Features computeLibraryValue(Id id, Library node) {
Features features = new Features();
if (macroDeclarationData.macroClass != null) {
features.add(Tags.macrosAreAvailable);
}
+ if (node == compilerResult.component!.mainMethod!.enclosingLibrary) {
+ features.markAsUnsorted(Tags.compilationSequence);
+ for (List<Library> component in getCompilationSequence()) {
+ features.addElement(
+ Tags.compilationSequence, strongComponentToString(component));
+ }
+ }
List<Class>? macroClasses = macroDeclarationData.macroDeclarations[node];
if (macroClasses != null) {
for (Class cls in macroClasses) {
@@ -148,16 +224,6 @@
}
@override
- Features computeClassValue(Id id, Class node) {
- Features features = new Features();
- if (getClassMacroApplicationData(node) != null) {
- features.add(Tags.macrosAreApplied);
- }
- registerMacroApplications(features, getClassMacroApplications(node));
- return features;
- }
-
- @override
Features computeMemberValue(Id id, Member node) {
Features features = new Features();
registerMacroApplications(features, getMemberMacroApplications(node));
diff --git a/pkg/front_end/test/spell_checking_list_code.txt b/pkg/front_end/test/spell_checking_list_code.txt
index fcf3a64..f7058af 100644
--- a/pkg/front_end/test/spell_checking_list_code.txt
+++ b/pkg/front_end/test/spell_checking_list_code.txt
@@ -679,6 +679,7 @@
launched
launcher
layer
+layers
layout
lc
ld
@@ -1215,6 +1216,7 @@
subexpression
subexpression's
subexpressions
+subgraph
subnode
subnodes
subscription
diff --git a/pkg/front_end/test/spell_checking_list_tests.txt b/pkg/front_end/test/spell_checking_list_tests.txt
index 86bfe96..bb52fe8 100644
--- a/pkg/front_end/test/spell_checking_list_tests.txt
+++ b/pkg/front_end/test/spell_checking_list_tests.txt
@@ -598,10 +598,13 @@
la
launch
launching
+layered
layers
le
legs
lengths
+lib2a
+lib2b
lightly
likewise
lily
@@ -644,6 +647,8 @@
loopback
mac
macro
+macro2a
+macro2b
macros
maker
matters
diff --git a/pkg/kernel/lib/util/graph.dart b/pkg/kernel/lib/util/graph.dart
index 4119f1b..aedbf14 100644
--- a/pkg/kernel/lib/util/graph.dart
+++ b/pkg/kernel/lib/util/graph.dart
@@ -4,12 +4,42 @@
library fasta.graph;
+import 'dart:math';
+
+import '../ast.dart';
+
abstract class Graph<T> {
Iterable<T> get vertices;
Iterable<T> neighborsOf(T vertex);
}
+/// [Graph] implementation using a collection of [Library] nodes as the graph
+/// vertices and using library dependencies to compute neighbors.
+///
+/// If [coreLibrary] is provided, it will be included in the neighbor of all
+/// vertices. Otherwise, `dart:core` will only be neighboring libraries that
+/// explicitly dependent on it.
+class LibraryGraph implements Graph<Library> {
+ final Iterable<Library> libraries;
+ final Library? coreLibrary;
+
+ LibraryGraph(this.libraries, {this.coreLibrary});
+
+ @override
+ Iterable<Library> get vertices => libraries;
+
+ @override
+ Iterable<Library> neighborsOf(Library library) sync* {
+ if (coreLibrary != null && library != coreLibrary) {
+ yield coreLibrary!;
+ }
+ for (LibraryDependency dependency in library.dependencies) {
+ yield dependency.targetLibrary;
+ }
+ }
+}
+
/// Computes the strongly connected components of [graph].
///
/// This implementation is based on [Dijkstra's path-based strong component
@@ -77,3 +107,93 @@
return result;
}
+
+/// A [Graph] using strongly connected components, as computed by
+/// [computeStrongComponents], as vertices. Neighbors are computed using the
+/// neighbors of the provided [subgraph] which was used to compute the strongly
+/// connected components.
+class StrongComponentGraph<T> implements Graph<List<T>> {
+ final Graph<T> subgraph;
+ final List<List<T>> components;
+ final Map<T, List<T>> _elementToComponentMap = {};
+ final Map<List<T>, Set<List<T>>> _neighborsMap = {};
+
+ StrongComponentGraph(this.subgraph, this.components) {
+ for (List<T> component in components) {
+ for (T element in component) {
+ _elementToComponentMap[element] = component;
+ }
+ }
+ }
+
+ Set<List<T>> _computeNeighborsOf(List<T> component) {
+ Set<List<T>> neighbors = {};
+ for (T element in component) {
+ for (T neighborElement in subgraph.neighborsOf(element)) {
+ List<T> neighborComponent = _elementToComponentMap[neighborElement]!;
+ if (component != neighborComponent) {
+ neighbors.add(neighborComponent);
+ }
+ }
+ }
+ return neighbors;
+ }
+
+ @override
+ Iterable<List<T>> neighborsOf(List<T> vertex) {
+ return _neighborsMap[vertex] ??= _computeNeighborsOf(vertex);
+ }
+
+ @override
+ Iterable<List<T>> get vertices => components;
+}
+
+/// Returns the non-cyclic vertices of [graph] sorted in topological order.
+///
+/// If [indexMap] is provided, it is filled with "index" of each vertex.
+/// If [layers] is provided, it is filled with a list of the vertices for each
+/// "index".
+///
+/// Here, the "index" of a vertex is the length of the longest path through
+/// neighbors. For vertices with no neighbors, the index is 0. For any other
+/// vertex, it is 1 plus max of the index of its neighbors.
+List<T> topologicalSort<T>(Graph<T> graph,
+ {Map<T, int>? indexMap, List<List<T>>? layers}) {
+ List<T> workList = graph.vertices.toList();
+ indexMap ??= {};
+ List<T> topologicallySortedVertices = [];
+ List<T> previousWorkList;
+ do {
+ previousWorkList = workList;
+ workList = [];
+ for (int i = 0; i < previousWorkList.length; i++) {
+ T vertex = previousWorkList[i];
+ int index = 0;
+ bool allSupertypesProcessed = true;
+ for (T neighbor in graph.neighborsOf(vertex)) {
+ int? neighborIndex = indexMap[neighbor];
+ if (neighborIndex == null) {
+ allSupertypesProcessed = false;
+ break;
+ } else {
+ index = max(index, neighborIndex + 1);
+ }
+ }
+ if (allSupertypesProcessed) {
+ indexMap[vertex] = index;
+ topologicallySortedVertices.add(vertex);
+ if (layers != null) {
+ if (index >= layers.length) {
+ assert(index == layers.length);
+ layers.add([vertex]);
+ } else {
+ layers[index].add(vertex);
+ }
+ }
+ } else {
+ workList.add(vertex);
+ }
+ }
+ } while (previousWorkList.length != workList.length);
+ return topologicallySortedVertices;
+}
