Add a utility for iterating over all topological orders (#6801)

Use an extension of Kahn's algorithm for finding topological orders that
iteratively makes every possible choice at every step to find all the
topological orders. The order being constructed and the set of possible
choices are managed in-place in the same buffer, so the algorithm takes
linear time and space plus amortized constant time per generated order.

This will be used in an upcoming type optimization.

2 files changed, 102 insertions, 0 deletions

diff --git a/test/gtest/CMakeLists.txt b/test/gtest/CMakeLists.txt
index 538ec1cdc..e8eec3f1d 100644
--- a/test/gtest/CMakeLists.txt
+++ b/test/gtest/CMakeLists.txt
@@ -12,6 +12,7 @@ set(unittest_SOURCES
   scc.cpp
   stringify.cpp
   suffix_tree.cpp
+  topological-orders.cpp
   type-builder.cpp
   wat-lexer.cpp
   validator.cpp
diff --git a/test/gtest/topological-orders.cpp b/test/gtest/topological-orders.cpp
new file mode 100644
index 000000000..7eeb8fdc2
--- /dev/null
+++ b/test/gtest/topological-orders.cpp
@@ -0,0 +1,101 @@
+/*
+ * Copyright 2024 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <cstddef>
+#include <optional>
+#include <vector>
+
+#include "support/topological_orders.h"
+#include "gtest/gtest.h"
+
+using namespace wasm;
+
+using Graph = std::vector<std::vector<size_t>>;
+
+TEST(TopologicalOrdersTest, Empty) {
+  Graph graph;
+  TopologicalOrders orders(graph);
+  EXPECT_EQ(orders.begin(), orders.end());
+}
+
+TEST(TopologicalOrdersTest, Singleton) {
+  Graph graph(1);
+  TopologicalOrders orders(graph);
+  auto it = orders.begin();
+  ASSERT_NE(it, orders.end());
+  EXPECT_EQ(*it, std::vector<size_t>{0});
+  ++it;
+  EXPECT_EQ(it, orders.end());
+}
+
+TEST(TopologicalOrdersTest, Permutations) {
+  Graph graph(3);
+  TopologicalOrders orders(graph);
+  std::set<std::vector<size_t>> results(orders.begin(), orders.end());
+  std::set<std::vector<size_t>> expected{
+    {0, 1, 2},
+    {0, 2, 1},
+    {1, 0, 2},
+    {1, 2, 0},
+    {2, 0, 1},
+    {2, 1, 0},
+  };
+  EXPECT_EQ(results, expected);
+}
+
+TEST(TopologicalOrdersTest, Chain) {
+  constexpr size_t n = 10;
+  Graph graph(n);
+  for (size_t i = 1; i < n; ++i) {
+    graph[i].push_back(i - 1);
+  }
+  TopologicalOrders orders(graph);
+  std::set<std::vector<size_t>> results(orders.begin(), orders.end());
+  std::set<std::vector<size_t>> expected{{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}};
+  EXPECT_EQ(results, expected);
+}
+
+TEST(TopologicalOrdersTest, TwoChains) {
+  Graph graph(4);
+  graph[0].push_back(2);
+  graph[1].push_back(3);
+  TopologicalOrders orders(graph);
+  std::set<std::vector<size_t>> results(orders.begin(), orders.end());
+  std::set<std::vector<size_t>> expected{
+    {0, 1, 2, 3},
+    {0, 1, 3, 2},
+    {0, 2, 1, 3},
+    {1, 0, 2, 3},
+    {1, 0, 3, 2},
+    {1, 3, 0, 2},
+  };
+  EXPECT_EQ(results, expected);
+}
+
+TEST(TopologicalOrdersTest, Diamond) {
+  Graph graph(4);
+  graph[0].push_back(1);
+  graph[0].push_back(2);
+  graph[1].push_back(3);
+  graph[2].push_back(3);
+  TopologicalOrders orders(graph);
+  std::set<std::vector<size_t>> results(orders.begin(), orders.end());
+  std::set<std::vector<size_t>> expected{
+    {0, 1, 2, 3},
+    {0, 2, 1, 3},
+  };
+  EXPECT_EQ(results, expected);
+}