[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;
+}