3 files changed, 76 insertions, 75 deletions
diff --git a/src/passes/ReorderGlobals.cpp b/src/passes/ReorderGlobals.cpp
index d17bb86cc..dab4625fe 100644
--- a/src/passes/ReorderGlobals.cpp
+++ b/src/passes/ReorderGlobals.cpp
@@ -199,8 +199,7 @@ struct ReorderGlobals : public Pass {
       }
     }
 
-    auto sort = *TopologicalSort(dependenceGraph);
-    for (auto global : sort) {
+    for (auto global : TopologicalSort::sort(dependenceGraph)) {
       // We can compute this global's count as in the sorted order all the
       // values it cares about are resolved. Start with the self-count, then
       // add the deps.
@@ -294,7 +293,7 @@ struct ReorderGlobals : public Pass {
       graph.emplace_back(i, std::move(children));
     }
 
-    return *MinTopologicalSortOf<Index>(graph.begin(), graph.end());
+    return TopologicalSort::minSortOf(graph.begin(), graph.end());
   }
 
   // Given an indexing of the globals and the counts of how many times each is
diff --git a/src/support/topological_orders.cpp b/src/support/topological_orders.cpp
index 0536d4ed9..aeec95d18 100644
--- a/src/support/topological_orders.cpp
+++ b/src/support/topological_orders.cpp
@@ -78,8 +78,7 @@ TopologicalOrders::Selector::advance(TopologicalOrders& ctx) {
   return select(ctx);
 }
 
-TopologicalOrders::TopologicalOrders(
-  const std::vector<std::vector<size_t>>& graph, SelectionMethod method)
+TopologicalOrders::TopologicalOrders(const Graph& graph, SelectionMethod method)
   : graph(graph), indegrees(graph.size()), buf(graph.size()) {
   if (graph.size() == 0) {
     return;
@@ -145,4 +144,16 @@ size_t TopologicalOrders::popChoice() {
   return choice;
 }
 
+namespace TopologicalSort {
+
+std::vector<size_t> sort(const Graph& graph) {
+  return *TopologicalOrders(graph, TopologicalOrders::InPlace);
+}
+
+std::vector<size_t> minSort(const Graph& graph) {
+  return *TopologicalOrders(graph, TopologicalOrders::MinHeap);
+}
+
+} // namespace TopologicalSort
+
 } // namespace wasm
diff --git a/src/support/topological_orders.h b/src/support/topological_orders.h
index 4332f7a91..1a5828247 100644
--- a/src/support/topological_orders.h
+++ b/src/support/topological_orders.h
@@ -20,16 +20,71 @@
 #include <cassert>
 #include <cstddef>
 #include <optional>
+#include <type_traits>
 #include <unordered_map>
 #include <vector>
 
 namespace wasm {
 
+namespace TopologicalSort {
+
+// An adjacency list containing edges from vertices to their successors.
+using Graph = std::vector<std::vector<size_t>>;
+
+// Return a topological sort of the vertices in the given adjacency graph.
+std::vector<size_t> sort(const Graph& graph);
+
+// Return the topological sort of the vertices in the given adjacency graph that
+// is closest to their original order. Implemented using a min-heap internally.
+std::vector<size_t> minSort(const Graph& graph);
+
+// A utility that finds a topological sort of a graph with arbitrary element
+// types. The provided iterators must be to pairs of elements and collections of
+// their children.
+template<typename It, std::vector<size_t> (*TopoSort)(const Graph&) = sort>
+decltype(auto) sortOf(It begin, It end) {
+  using T = std::remove_cv_t<typename It::value_type::first_type>;
+  std::unordered_map<T, size_t> indices;
+  std::vector<T> elements;
+  // Assign indices to each element.
+  for (auto it = begin; it != end; ++it) {
+    auto inserted = indices.insert({it->first, elements.size()});
+    assert(inserted.second && "unexpected repeat element");
+    elements.push_back(inserted.first->first);
+  }
+  // Collect the graph in terms of indices.
+  Graph indexGraph;
+  indexGraph.reserve(elements.size());
+  for (auto it = begin; it != end; ++it) {
+    indexGraph.emplace_back();
+    for (const auto& child : it->second) {
+      indexGraph.back().push_back(indices.at(child));
+    }
+  }
+  // Compute the topological order and convert back to original elements.
+  std::vector<T> order;
+  order.reserve(elements.size());
+  auto indexOrder = TopoSort(indexGraph);
+  for (auto i : indexOrder) {
+    order.emplace_back(std::move(elements[i]));
+  }
+  return order;
+}
+
+// Find the topological sort of a graph with arbitrary element types that is
+// closest to their original order.
+template<typename It> decltype(auto) minSortOf(It begin, It end) {
+  return sortOf<It, minSort>(begin, end);
+}
+
+} // namespace TopologicalSort
+
 // A utility for iterating through all possible topological orders in a graph
 // using an extension of Kahn's algorithm (see
 // https://en.wikipedia.org/wiki/Topological_sorting) that iteratively makes all
 // possible choices for each position of the output order.
 struct TopologicalOrders {
+  using Graph = TopologicalSort::Graph;
   using value_type = const std::vector<size_t>;
   using difference_type = std::ptrdiff_t;
   using reference = const std::vector<size_t>&;
@@ -38,8 +93,7 @@ struct TopologicalOrders {
 
   // Takes an adjacency list, where the list for each vertex is a sorted list of
   // the indices of its children, which will appear after it in the order.
-  TopologicalOrders(const std::vector<std::vector<size_t>>& graph)
-    : TopologicalOrders(graph, InPlace) {}
+  TopologicalOrders(const Graph& graph) : TopologicalOrders(graph, InPlace) {}
 
   TopologicalOrders begin() { return TopologicalOrders(graph); }
   TopologicalOrders end() { return TopologicalOrders({}); }
@@ -55,15 +109,13 @@ struct TopologicalOrders {
   TopologicalOrders& operator++();
   TopologicalOrders operator++(int) { return ++(*this); }
 
-protected:
+private:
   enum SelectionMethod { InPlace, MinHeap };
-  TopologicalOrders(const std::vector<std::vector<size_t>>& graph,
-                    SelectionMethod method);
+  TopologicalOrders(const Graph& graph, SelectionMethod method);
 
-private:
   // The input graph given as an adjacency list with edges from vertices to
   // their dependent children.
-  const std::vector<std::vector<size_t>>& graph;
+  const Graph& graph;
   // The current in-degrees for each vertex. When a vertex is appended to our
   // permutation, the in-degrees of its children are decremented and those that
   // go to zero become available for the next selection.
@@ -103,72 +155,11 @@ private:
   // A stack of selectors, one for each vertex in a complete topological order.
   // Empty if we've already seen every possible ordering.
   std::vector<Selector> selectors;
-};
-
-// A utility for finding a single topological order of a graph.
-struct TopologicalSort : private TopologicalOrders {
-  TopologicalSort(const std::vector<std::vector<size_t>>& graph)
-    : TopologicalOrders(graph) {}
 
-  const std::vector<size_t>& operator*() const {
-    return TopologicalOrders::operator*();
-  }
-};
-
-// A utility for finding the topological order that is as close as possible to
-// the original order of elements. Internally uses a min-heap to choose the best
-// available next element.
-struct MinTopologicalSort : private TopologicalOrders {
-  MinTopologicalSort(const std::vector<std::vector<size_t>>& graph)
-    : TopologicalOrders(graph, MinHeap) {}
-
-  const std::vector<size_t>& operator*() const {
-    return TopologicalOrders::operator*();
-  }
-};
-
-// A utility that finds a topological sort of a graph with arbitrary element
-// types.
-template<typename T, typename TopoSort = TopologicalSort>
-struct TopologicalSortOf {
-  std::vector<T> order;
-
-  // The value of the iterators must be a pair of an element and an iterable of
-  // its children.
-  template<typename It> TopologicalSortOf(It begin, It end) {
-    std::unordered_map<T, size_t> indices;
-    std::vector<T> elements;
-    // Assign indices to each element.
-    for (auto it = begin; it != end; ++it) {
-      auto inserted = indices.insert({it->first, elements.size()});
-      assert(inserted.second && "unexpected repeat element");
-      elements.push_back(inserted.first->first);
-    }
-    // Collect the graph in terms of indices.
-    std::vector<std::vector<size_t>> indexGraph;
-    indexGraph.reserve(elements.size());
-    for (auto it = begin; it != end; ++it) {
-      indexGraph.emplace_back();
-      for (const auto& child : it->second) {
-        indexGraph.back().push_back(indices.at(child));
-      }
-    }
-    // Compute the topological order and convert back to original elements.
-    order.reserve(elements.size());
-    auto indexOrder = *TopoSort(indexGraph);
-    for (auto i : indexOrder) {
-      order.emplace_back(std::move(elements[i]));
-    }
-  }
-
-  const std::vector<T>& operator*() const { return order; }
+  friend std::vector<size_t> TopologicalSort::sort(const Graph&);
+  friend std::vector<size_t> TopologicalSort::minSort(const Graph&);
 };
 
-// A utility that finds the minimum topological sort of a graph with arbitrary
-// element types.
-template<typename T>
-using MinTopologicalSortOf = TopologicalSortOf<T, MinTopologicalSort>;
-
 } // namespace wasm
 
 #endif // wasm_support_topological_orders_h