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.

1 files changed, 104 insertions, 0 deletions

diff --git a/src/support/topological_orders.h b/src/support/topological_orders.h
new file mode 100644
index 000000000..acab78ee5
--- /dev/null
+++ b/src/support/topological_orders.h
@@ -0,0 +1,104 @@
+/*
+ * 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.
+ */
+
+#ifndef wasm_support_topological_orders_h
+#define wasm_support_topological_orders_h
+
+#include <cstddef>
+#include <optional>
+#include <vector>
+
+namespace wasm {
+
+// 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 {
+  // 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);
+
+  struct Iterator {
+    using value_type = const std::vector<size_t>;
+    using difference_type = std::ptrdiff_t;
+    using reference = const std::vector<size_t>&;
+    using pointer = const std::vector<size_t>*;
+    using iterator_category = std::input_iterator_tag;
+
+    TopologicalOrders* parent;
+
+    bool isEnd() const { return !parent || parent->selectors.empty(); }
+    bool operator==(const Iterator& other) const {
+      return isEnd() == other.isEnd();
+    }
+    bool operator!=(const Iterator& other) const { return !(*this == other); }
+    const std::vector<size_t>& operator*() { return parent->buf; }
+    const std::vector<size_t>* operator->() { return &parent->buf; }
+    Iterator& operator++() {
+      parent->advance();
+      return *this;
+    }
+    Iterator operator++(int) { return ++(*this); }
+  };
+
+  Iterator begin() { return {this}; }
+  Iterator end() { return {nullptr}; }
+
+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;
+  // 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.
+  std::vector<size_t> indegrees;
+  // The buffer in which we are constructing a permutation. It contains a
+  // sequence of selected vertices followed by a sequence of possible choices
+  // for the next vertex.
+  std::vector<size_t> buf;
+
+  // The state for tracking the possible choices for a single vertex in the
+  // output order.
+  struct Selector {
+    // The start index of the sequence of available choices. Also the index
+    // where we place the current choice.
+    size_t start;
+    // The number of choices we have.
+    size_t count;
+    // The index of the current choice in the original order.
+    size_t index;
+
+    // Select the next available vertex, decrement in-degrees, and update the
+    // sequence of available vertices. Return the Selector for the next vertex.
+    Selector select(TopologicalOrders& ctx);
+
+    // Undo the current selection, move the next selection into the first
+    // position and return the new selector for the next position. Returns
+    // nullopt if advancing wraps back around to the original configuration.
+    std::optional<Selector> advance(TopologicalOrders& ctx);
+  };
+
+  // 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;
+
+  void advance();
+};
+
+} // namespace wasm
+
+#endif // wasm_support_topological_orders_h