Test concepts formatting
diff --git a/src/passes/GlobalEffects.cpp b/src/passes/GlobalEffects.cpp index 7f47cf1..41e1dff 100644 --- a/src/passes/GlobalEffects.cpp +++ b/src/passes/GlobalEffects.cpp
@@ -22,6 +22,7 @@ #include "ir/effects.h" #include "ir/module-utils.h" #include "pass.h" +#include "support/graph_traversal.h" #include "support/strongly_connected_components.h" #include "wasm.h"
diff --git a/src/support/graph_traversal.h b/src/support/graph_traversal.h new file mode 100644 index 0000000..7da0f78 --- /dev/null +++ b/src/support/graph_traversal.h
@@ -0,0 +1,72 @@ +/* + * Copyright 2026 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 <concepts> +#include <functional> +#include <iterator> +#include <unordered_set> + +namespace wasm { + +template<typename T, typename SuccessorFunction> + requires std:: + invocable<SuccessorFunction, std::function<void(const T&)>&, const T&> + class Graph { +public: + template<std::input_iterator It, std::sentinel_for<It> Sen> + requires std::convertible_to<std::iter_reference_t<It>, T> + Graph(It rootsBegin, Sen rootsEnd, auto&& successors) + : roots(rootsBegin, rootsEnd), + successors(std::forward<decltype(successors)>(successors)) {} + + // Traverse the graph depth-first, calling `successors` exactly once for each + // node (unless the node appears multiple times in `roots`). Return the set of + // nodes visited. + std::unordered_set<T> traverseDepthFirst() const { + std::vector<T> stack(roots.begin(), roots.end()); + std::unordered_set<T> visited(roots.begin(), roots.end()); + + while (!stack.empty()) { + auto curr = std::move(stack.back()); + stack.pop_back(); + + auto maybePush = [&](const T& t) { + if (visited.contains(t)) { + return; + } + + visited.insert(t); + stack.push_back(t); + }; + + successors(maybePush, curr); + } + + return visited; + } + +private: + std::vector<T> roots; + SuccessorFunction successors; +}; + +template<std::input_iterator It, + std::sentinel_for<It> Sen, + typename SuccessorFunction> +Graph(It, Sen, SuccessorFunction) + -> Graph<std::iter_value_t<It>, std::decay_t<SuccessorFunction>>; + +} // namespace wasm