OILS / vendor / souffle / utility / NodeMapper.h View on Github | oilshell.org

192 lines, 117 significant
1/*
2 * Souffle - A Datalog Compiler
3 * Copyright (c) 2021, The Souffle Developers. All rights reserved
4 * Licensed under the Universal Permissive License v 1.0 as shown at:
5 * - https://opensource.org/licenses/UPL
6 * - <souffle root>/licenses/SOUFFLE-UPL.txt
7 */
8
9/************************************************************************
10 *
11 * @file Mapper.h
12 *
13 * Defines generic transformation helpers for nodes
14 *
15 ***********************************************************************/
16
17#pragma once
18
19#include "souffle/utility/ContainerUtil.h"
20#include "souffle/utility/FunctionalUtil.h"
21#include "souffle/utility/MiscUtil.h"
22#include "souffle/utility/NodeMapperFwd.h"
23#include "souffle/utility/Types.h"
24#include "souffle/utility/Visitor.h"
25#include <type_traits>
26#include <utility>
27
28namespace souffle {
29
30namespace detail {
31
32template <typename F>
33using infer_mapper_arg_type = visit_root_type<
34 typename lambda_traits<F>::template arg<lambda_traits<F>::arity::value - 1>::element_type>;
35
36template <typename F, typename N, typename = void>
37struct infer_mapper_arg_type_or_given {
38 using type = N;
39};
40
41template <typename F, typename N>
42struct infer_mapper_arg_type_or_given<F, N, std::enable_if_t<std::is_same_v<N, void>>> {
43 using type = detail::infer_mapper_arg_type<F>;
44};
45
46template <typename F /* B <: A. Own<A> -> Own<B> */, typename A>
47SOUFFLE_ALWAYS_INLINE void matchMutateInPlace([[maybe_unused]] F&& f, [[maybe_unused]] Own<A>& x) {
48 using FInfo = lambda_traits<std::decay_t<F>>;
49 using Arg = typename std::decay_t<typename FInfo::template arg<0>>::element_type;
50 if constexpr (std::is_base_of_v<A, Arg> || std::is_base_of_v<Arg, A>) {
51 if (auto y = as<Arg>(x)) {
52 x.release();
53 x = UNSAFE_cast<A>(f(Own<Arg>(y)));
54 }
55 }
56}
57
58/**
59 * @class LambdaNodeMapper
60 * @brief A special NodeMapper wrapping a lambda conducting node transformations.
61 */
62template <typename Node, typename F>
63class LambdaNodeMapper : public NodeMapper<Node> {
64 F lambda;
65
66 template <typename A, typename = decltype(lambda(A{}))>
67 SOUFFLE_ALWAYS_INLINE auto go(A node) const {
68 return lambda(std::move(node));
69 }
70
71 template <typename A, typename R = decltype(lambda(std::declval<NodeMapper<Node> const&>(), A{}))>
72 SOUFFLE_ALWAYS_INLINE R go(A node) const {
73 return lambda(*this, std::move(node));
74 }
75
76public:
77 /**
78 * @brief Constructor for LambdaNodeMapper
79 */
80 LambdaNodeMapper(F lambda) : lambda(std::move(lambda)) {}
81
82 /**
83 * @brief Applies lambda
84 */
85 Own<Node> operator()(Own<Node> node) const override {
86 Own<Node> result = go(std::move(node));
87 assert(result != nullptr && "null-pointer in lambda ram-node mapper");
88 return result;
89 }
90};
91
92} // namespace detail
93
94template <typename N = void, typename F,
95 typename Node = typename detail::infer_mapper_arg_type_or_given<F, N>::type>
96auto nodeMapper(F f) {
97 return detail::LambdaNodeMapper<Node, F>{std::move(f)};
98}
99
100template <typename A, typename F, typename Node = detail::visit_root_type<A>>
101void mapChildPre(A& root, F&& f) {
102 root.apply(nodeMapper<Node>([&](auto&& go, Own<Node> node) {
103 detail::matchMutateInPlace(f, node);
104 node->apply(go);
105 return node;
106 }));
107}
108
109template <typename A, typename F, typename = std::enable_if_t<detail::is_visitable_node<A>>>
110void mapPre(Own<A>& xs, F&& f) {
111 assert(xs);
112 detail::matchMutateInPlace(f, xs);
113 mapChildPre(*xs, f);
114}
115
116template <typename A, typename F, typename = std::enable_if_t<detail::is_visitable_node<A>>>
117Own<A> mapPre(Own<A>&& x, F&& f) {
118 mapPre(x, std::forward<F>(f));
119 return std::move(x);
120}
121
122template <typename CC, typename F, typename = std::enable_if_t<detail::is_visitable_container<CC>>>
123void mapPre(CC& xs, F&& f) {
124 for (auto& x : xs)
125 mapPre(x, f);
126}
127
128template <typename A, typename F, typename Node = detail::visit_root_type<A>>
129void mapChildPost(A& root, F&& f) {
130 root.apply(nodeMapper<Node>([&](auto&& go, Own<Node> node) {
131 node->apply(go);
132 detail::matchMutateInPlace(f, node);
133 return node;
134 }));
135}
136
137template <typename A, typename F, typename = std::enable_if_t<detail::is_visitable_node<A>>>
138void mapPost(Own<A>& xs, F&& f) {
139 assert(xs);
140 mapChildPost(*xs, f);
141 detail::matchMutateInPlace(f, xs);
142}
143
144template <typename A, typename F, typename = std::enable_if_t<detail::is_visitable_node<A>>>
145Own<A> mapPost(Own<A>&& x, F&& f) {
146 mapPost(x, std::forward<F>(f));
147 return std::move(x);
148}
149
150template <typename CC, typename F, typename = std::enable_if_t<detail::is_visitable_container<CC>>>
151void mapPost(CC& xs, F&& f) {
152 for (auto& x : reverse{xs})
153 mapPost(x, f);
154}
155
156template <typename A, typename F /* Own<A> -> std::pair<Own<A>, bool> */,
157 typename Root = detail::visit_root_type<A>>
158size_t mapChildFrontier(A& root, F&& frontier);
159
160template <typename A, typename F /* Own<A> -> std::pair<Own<A>, bool> */,
161 typename Root = detail::visit_root_type<A>>
162size_t mapFrontier(Own<A>& root, F&& frontier) {
163 assert(root);
164 using Arg = typename std::decay_t<typename lambda_traits<F>::template arg<0>>::element_type;
165 if (auto arg = as<Arg>(root)) {
166 root.release();
167 auto&& [tmp, seen_frontier] = frontier(Own<Arg>(arg));
168 root = std::move(tmp);
169 if (seen_frontier) return 1;
170 }
171
172 return mapChildFrontier(*root, std::forward<F>(frontier));
173}
174
175template <typename A, typename F /* Own<A> -> std::pair<Own<A>, bool> */,
176 typename Root = detail::visit_root_type<A>>
177std::pair<Own<A>, size_t> mapFrontier(Own<A>&& root, F&& frontier) {
178 auto n = mapFrontier(root, std::forward<F>(frontier));
179 return {std::move(root), n};
180}
181
182template <typename A, typename F /* Own<A> -> std::pair<Own<A>, bool> */, typename Root>
183size_t mapChildFrontier(A& root, F&& frontier) {
184 size_t frontiers = 0;
185 root.apply(nodeMapper<Root>([&](Own<Root> node) {
186 frontiers += mapFrontier(node, frontier);
187 return node;
188 }));
189 return frontiers;
190}
191
192} // namespace souffle