[NFC] Change topological sort utilities to functions (#6889)

Previously they were structs and their results were accessed with
`operator*()`, but that was unnecessarily complicated and could lead to
problems with temporary lifetimes being too short. Simplify the
utilities by making them functions. This also allows the wrapper
templates to infer the proper element types automatically.

4 files changed, 83 insertions, 84 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
diff --git a/test/gtest/topological-orders.cpp b/test/gtest/topological-orders.cpp
index ba370123d..41e1df483 100644
--- a/test/gtest/topological-orders.cpp
+++ b/test/gtest/topological-orders.cpp
@@ -102,14 +102,13 @@ TEST(TopologicalOrdersTest, Diamond) {
 
 TEST(MinTopologicalSortTest, Empty) {
   Graph graph(0);
-  EXPECT_EQ(*MinTopologicalSort(graph), std::vector<size_t>{});
+  EXPECT_EQ(TopologicalSort::minSort(graph), std::vector<size_t>{});
 }
 
 TEST(MinTopologicalSortTest, Unconstrained) {
   Graph graph(3);
-  MinTopologicalSort order(graph);
   std::vector<size_t> expected{0, 1, 2};
-  EXPECT_EQ(*MinTopologicalSort(graph), expected);
+  EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
 TEST(MinTopologicalSortTest, Reversed) {
@@ -117,7 +116,7 @@ TEST(MinTopologicalSortTest, Reversed) {
   graph[2].push_back(1);
   graph[1].push_back(0);
   std::vector<size_t> expected{2, 1, 0};
-  EXPECT_EQ(*MinTopologicalSort(graph), expected);
+  EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
 TEST(MinTopologicalSortTest, OneBeforeZero) {
@@ -125,7 +124,7 @@ TEST(MinTopologicalSortTest, OneBeforeZero) {
   graph[1].push_back(0);
   // 2 last because it is greater than 1 and 0
   std::vector<size_t> expected{1, 0, 2};
-  EXPECT_EQ(*MinTopologicalSort(graph), expected);
+  EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
 TEST(MinTopologicalSortTest, TwoBeforeOne) {
@@ -133,7 +132,7 @@ TEST(MinTopologicalSortTest, TwoBeforeOne) {
   graph[2].push_back(1);
   // 0 first because it is less than 2 and 1
   std::vector<size_t> expected{0, 2, 1};
-  EXPECT_EQ(*MinTopologicalSort(graph), expected);
+  EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
 TEST(MinTopologicalSortTest, TwoBeforeZero) {
@@ -141,7 +140,7 @@ TEST(MinTopologicalSortTest, TwoBeforeZero) {
   graph[2].push_back(0);
   // 1 first because it is less than 2 and zero is not eligible.
   std::vector<size_t> expected{1, 2, 0};
-  EXPECT_EQ(*MinTopologicalSort(graph), expected);
+  EXPECT_EQ(TopologicalSort::minSort(graph), expected);
 }
 
 TEST(MinTopologicalSortTest, Strings) {
@@ -151,6 +150,5 @@ TEST(MinTopologicalSortTest, Strings) {
     {"dog", {}},
     {"mammal", {"cat", "dog"}}};
   std::vector<std::string> expected{"animal", "mammal", "cat", "dog"};
-  EXPECT_EQ(*MinTopologicalSortOf<std::string>(graph.begin(), graph.end()),
-            expected);
+  EXPECT_EQ(TopologicalSort::minSortOf(graph.begin(), graph.end()), expected);
 }