297 lines
11 KiB
C++
297 lines
11 KiB
C++
#pragma once
|
|
|
|
#include <flow/common.hpp>
|
|
#include <flow/detail/walk.hpp>
|
|
#include <flow/impl.hpp>
|
|
|
|
#include <stdx/ct_string.hpp>
|
|
#include <stdx/cx_multimap.hpp>
|
|
#include <stdx/cx_set.hpp>
|
|
#include <stdx/cx_vector.hpp>
|
|
#include <stdx/span.hpp>
|
|
#include <stdx/static_assert.hpp>
|
|
#include <stdx/tuple_algorithms.hpp>
|
|
#include <stdx/type_traits.hpp>
|
|
#include <stdx/utility.hpp>
|
|
|
|
#include <boost/mp11/set.hpp>
|
|
|
|
#include <algorithm>
|
|
#include <array>
|
|
#include <cstddef>
|
|
#include <iterator>
|
|
#include <optional>
|
|
#include <utility>
|
|
|
|
namespace flow {
|
|
namespace detail {
|
|
template <typename T> using is_duplicated = std::bool_constant<(T::size() > 1)>;
|
|
|
|
template <typename CTNode, typename Output>
|
|
concept is_output_compatible = requires(CTNode n) {
|
|
{ Output::create_node(n) } -> std::same_as<typename Output::node_t>;
|
|
};
|
|
} // namespace detail
|
|
|
|
template <typename T> using name_for = typename T::name_t;
|
|
|
|
[[nodiscard]] constexpr auto edge_size(auto const &nodes,
|
|
auto const &edges) -> std::size_t {
|
|
auto const edge_capacities = transform(
|
|
[&]<typename N>(N const &) {
|
|
return edges.fold_left(
|
|
std::size_t{}, []<typename E>(auto acc, E const &) {
|
|
if constexpr (std::is_same_v<name_for<typename E::source_t>,
|
|
name_for<N>> or
|
|
std::is_same_v<name_for<typename E::dest_t>,
|
|
name_for<N>>) {
|
|
return ++acc;
|
|
} else {
|
|
return acc;
|
|
}
|
|
});
|
|
},
|
|
nodes);
|
|
|
|
return edge_capacities.fold_left(std::size_t{1}, [](auto acc, auto next) {
|
|
return std::max(acc, next);
|
|
});
|
|
}
|
|
|
|
template <stdx::ct_string Name,
|
|
template <stdx::ct_string, std::size_t> typename Impl>
|
|
struct graph_builder {
|
|
// NOLINTBEGIN(readability-function-cognitive-complexity)
|
|
template <typename Output, std::size_t N, std::size_t E>
|
|
[[nodiscard]] constexpr static auto make_graph(auto const &nodes,
|
|
auto const &edges) {
|
|
using output_node_t = typename Output::node_t;
|
|
using graph_t = stdx::cx_multimap<output_node_t, output_node_t, N, E>;
|
|
graph_t g{};
|
|
for_each([&]<typename Node>(Node n) { g.put(Output::create_node(n)); },
|
|
nodes);
|
|
|
|
auto const named_nodes = stdx::apply_indices<name_for>(nodes);
|
|
for_each(
|
|
[&]<typename Lhs, typename Rhs, typename Cond>(
|
|
dsl::edge<Lhs, Rhs, Cond> const &) {
|
|
auto lhs = get<name_for<Lhs>>(named_nodes);
|
|
auto rhs = get<name_for<Rhs>>(named_nodes);
|
|
|
|
using lhs_t = std::remove_cvref_t<decltype(lhs)>;
|
|
using rhs_t = std::remove_cvref_t<decltype(rhs)>;
|
|
using lhs_cond_t = std::remove_cvref_t<decltype(lhs.condition)>;
|
|
using rhs_cond_t = std::remove_cvref_t<decltype(rhs.condition)>;
|
|
|
|
using edge_ps_t = decltype(Cond::predicates);
|
|
auto node_ps = stdx::to_unsorted_set(stdx::tuple_cat(
|
|
lhs_t::condition.predicates, rhs_t::condition.predicates));
|
|
|
|
stdx::for_each(
|
|
[&]<typename P>(P const &) {
|
|
STATIC_ASSERT(
|
|
(stdx::contains_type<edge_ps_t, P>),
|
|
"The conditions on the sequence ({} >> {})[{}] are "
|
|
"weaker than those on {}[{}] or {}[{}]. "
|
|
"Specifically, the sequence is missing the "
|
|
"predicate: {}",
|
|
CX_VALUE(lhs_t::ct_name), CX_VALUE(rhs_t::ct_name),
|
|
CX_VALUE(Cond::ct_name), CX_VALUE(lhs_t::ct_name),
|
|
CX_VALUE(lhs_cond_t::ct_name),
|
|
CX_VALUE(rhs_t::ct_name),
|
|
CX_VALUE(rhs_cond_t::ct_name), CX_VALUE(P));
|
|
},
|
|
node_ps);
|
|
|
|
g.put(Output::create_node(lhs), Output::create_node(rhs));
|
|
},
|
|
edges);
|
|
return g;
|
|
}
|
|
// NOLINTEND(readability-function-cognitive-complexity)
|
|
|
|
template <typename Node, typename Graph>
|
|
[[nodiscard]] constexpr static auto is_source_of(Node const &node,
|
|
Graph const &g) -> bool {
|
|
return std::find_if(g.begin(), g.end(), [&](auto const &entry) {
|
|
return entry.value.contains(node);
|
|
}) == g.end();
|
|
}
|
|
|
|
template <typename Graph>
|
|
[[nodiscard]] constexpr static auto get_sources(Graph const &g)
|
|
-> stdx::cx_set<typename Graph::key_type, Graph::capacity()> {
|
|
stdx::cx_set<typename Graph::key_type, Graph::capacity()> s;
|
|
for (auto const &entry : g) {
|
|
s.insert(entry.key);
|
|
}
|
|
for (auto const &entry : g) {
|
|
for (auto const &dst : entry.value) {
|
|
s.erase(dst);
|
|
}
|
|
}
|
|
return s;
|
|
}
|
|
|
|
template <typename Output, typename Graph>
|
|
[[nodiscard]] constexpr static auto
|
|
topo_sort(Graph &g) -> std::optional<Output> {
|
|
stdx::cx_vector<typename Graph::key_type, Graph::capacity()>
|
|
ordered_list{};
|
|
|
|
auto sources = get_sources(g);
|
|
while (not sources.empty()) {
|
|
auto n = sources.pop_back();
|
|
ordered_list.push_back(n);
|
|
|
|
if (g.contains(n)) {
|
|
auto ms = g.get(n);
|
|
if (ms.empty()) {
|
|
g.erase(n);
|
|
} else {
|
|
for (auto const &entry : ms) {
|
|
g.erase(n, entry);
|
|
if (is_source_of(entry, g)) {
|
|
sources.insert(entry);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (not g.empty()) {
|
|
return {};
|
|
}
|
|
using span_t =
|
|
stdx::span<typename Graph::key_type const, Graph::capacity()>;
|
|
return std::optional<Output>{std::in_place, span_t{ordered_list}};
|
|
}
|
|
|
|
template <typename T>
|
|
constexpr static auto error_steps =
|
|
stdx::transform([](auto N) { return stdx::ct_string_from_type(N); },
|
|
T{})
|
|
.join(stdx::ct_string{""}, [](auto x, auto y) {
|
|
using namespace stdx::literals;
|
|
return x + ", "_cts + y;
|
|
});
|
|
|
|
constexpr static void check_for_missing_nodes(auto nodes,
|
|
auto mentioned_nodes) {
|
|
constexpr auto get_name = []<typename N>(N) ->
|
|
typename N::name_t { return {}; };
|
|
auto node_names = stdx::transform(get_name, nodes);
|
|
auto mentioned_node_names = stdx::transform(get_name, mentioned_nodes);
|
|
|
|
using node_names_t = decltype(stdx::to_sorted_set(node_names));
|
|
using mentioned_node_names_t =
|
|
decltype(stdx::to_sorted_set(mentioned_node_names));
|
|
using missing_nodes_t =
|
|
boost::mp11::mp_set_difference<mentioned_node_names_t,
|
|
node_names_t>;
|
|
STATIC_ASSERT(
|
|
(std::is_same_v<node_names_t, mentioned_node_names_t>),
|
|
"One or more steps are referenced in the flow ({}) but not "
|
|
"explicitly added with the * operator. The missing steps are: {}.",
|
|
CX_VALUE(Name), CX_VALUE(error_steps<missing_nodes_t>));
|
|
|
|
constexpr auto duplicates = stdx::transform(
|
|
[](auto e) { return stdx::get<0>(e); },
|
|
stdx::filter<detail::is_duplicated>(stdx::gather(node_names)));
|
|
using duplicate_nodes_t = decltype(duplicates);
|
|
STATIC_ASSERT(
|
|
stdx::tuple_size_v<duplicate_nodes_t> == 0,
|
|
"One or more steps in the flow ({}) are explicitly added more than "
|
|
"once using the * operator. The duplicate steps are: {}.",
|
|
CX_VALUE(Name), CX_VALUE(error_steps<duplicate_nodes_t>));
|
|
}
|
|
|
|
template <typename Graph>
|
|
[[nodiscard]] constexpr static auto build(Graph const &input) {
|
|
auto nodes = flow::dsl::get_nodes(input);
|
|
auto mentioned_nodes = flow::dsl::get_all_mentioned_nodes(input);
|
|
|
|
check_for_missing_nodes(nodes, mentioned_nodes);
|
|
|
|
auto node_set = stdx::to_unsorted_set(nodes);
|
|
auto edges = stdx::to_unsorted_set(flow::dsl::get_edges(input));
|
|
|
|
constexpr auto node_capacity = stdx::tuple_size_v<decltype(node_set)>;
|
|
constexpr auto edge_capacity = edge_size(node_set, edges);
|
|
|
|
using output_t = Impl<Graph::name, node_capacity>;
|
|
static_assert(
|
|
all_of(
|
|
[]<typename N>(N const &) {
|
|
return detail::is_output_compatible<N, output_t>;
|
|
},
|
|
node_set),
|
|
"Output node type is not compatible with given input nodes");
|
|
|
|
auto g =
|
|
make_graph<output_t, node_capacity, edge_capacity>(node_set, edges);
|
|
return topo_sort<output_t>(g);
|
|
}
|
|
|
|
template <typename Initialized> class built_flow {
|
|
constexpr static auto built() {
|
|
constexpr auto v = Initialized::value;
|
|
constexpr auto built = build(v);
|
|
static_assert(built.has_value(),
|
|
"Topological sort failed: cycle in flow");
|
|
|
|
constexpr auto functionPtrs = built->functionPtrs;
|
|
constexpr auto size = std::size(functionPtrs);
|
|
constexpr auto name = built->name;
|
|
|
|
return [&]<std::size_t... Is>(std::index_sequence<Is...>) {
|
|
return detail::inlined_func_list<name, functionPtrs[Is]...>{};
|
|
}(std::make_index_sequence<size>{});
|
|
}
|
|
|
|
constexpr static auto run() { built()(); }
|
|
|
|
public:
|
|
// NOLINTNEXTLINE(google-explicit-constructor)
|
|
constexpr explicit(false) operator FunctionPtr() const { return run; }
|
|
constexpr auto operator()() const -> void { run(); }
|
|
constexpr static bool active = decltype(built())::active;
|
|
};
|
|
|
|
template <typename Initialized>
|
|
[[nodiscard]] constexpr static auto render() -> built_flow<Initialized> {
|
|
return {};
|
|
}
|
|
};
|
|
|
|
template <stdx::ct_string Name = "",
|
|
typename Renderer = graph_builder<Name, impl>,
|
|
flow::dsl::subgraph... Fragments>
|
|
class graph {
|
|
template <typename Tag>
|
|
friend constexpr auto tag_invoke(Tag, graph const &g) {
|
|
return g.fragments.apply([](auto const &...frags) {
|
|
return stdx::tuple_cat(Tag{}(frags)...);
|
|
});
|
|
}
|
|
|
|
public:
|
|
template <flow::dsl::subgraph... Ns>
|
|
[[nodiscard]] constexpr auto add(Ns &&...ns) {
|
|
return fragments.apply([&](auto &...frags) {
|
|
return graph<Name, Renderer, Fragments...,
|
|
stdx::remove_cvref_t<Ns>...>{
|
|
{frags..., std::forward<Ns>(ns)...}};
|
|
});
|
|
}
|
|
|
|
template <typename BuilderValue>
|
|
[[nodiscard]] constexpr static auto build() {
|
|
return Renderer::template render<BuilderValue>();
|
|
}
|
|
|
|
constexpr static auto name = Name;
|
|
stdx::tuple<Fragments...> fragments;
|
|
};
|
|
} // namespace flow
|