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

277 lines, 119 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 ContainerUtil.h
12 *
13 * @brief Datalog project utilities
14 *
15 ***********************************************************************/
16
17#pragma once
18
19#include "souffle/utility/DynamicCasting.h"
20#include "souffle/utility/Iteration.h"
21#include "souffle/utility/MiscUtil.h"
22#include "souffle/utility/Types.h"
23
24#include <algorithm>
25#include <functional>
26#include <iterator>
27#include <map>
28#include <set>
29#include <type_traits>
30#include <utility>
31#include <vector>
32
33namespace souffle {
34
35// -------------------------------------------------------------------------------
36// General Container Utilities
37// -------------------------------------------------------------------------------
38
39/**
40 * Use to range-for iterate in reverse.
41 * Assumes `std::rbegin` and `std::rend` are defined for type `A`.
42 */
43template <typename A>
44struct reverse {
45 reverse(A& iterable) : iterable(iterable) {}
46 A& iterable;
47
48 auto begin() {
49 return std::rbegin(iterable);
50 }
51
52 auto end() {
53 return std::rend(iterable);
54 }
55};
56
57/**
58 * A utility to check generically whether a given element is contained in a given
59 * container.
60 */
61template <typename C, typename = std::enable_if_t<!is_associative<C>>>
62bool contains(const C& container, const typename C::value_type& element) {
63 return std::find(container.begin(), container.end(), element) != container.end();
64}
65
66/**
67 * A utility to check generically whether a given key exists within a given
68 * associative container.
69 */
70template <typename C, typename A, typename = std::enable_if_t<is_associative<C>>>
71bool contains(const C& container, A&& element) {
72 return container.find(element) != container.end();
73}
74
75/**
76 * Returns the first element in a container that satisfies a given predicate,
77 * nullptr otherwise.
78 */
79template <typename C, typename F>
80auto getIf(C&& container, F&& pred) {
81 auto it = std::find_if(container.begin(), container.end(), std::forward<F>(pred));
82 return it == container.end() ? nullptr : *it;
83}
84
85/**
86 * Get value for a given key; if not found, return default value.
87 */
88template <typename C, typename A, typename = std::enable_if_t<is_associative<C>>>
89typename C::mapped_type const& getOr(
90 const C& container, A&& key, const typename C::mapped_type& defaultValue) {
91 auto it = container.find(key);
92
93 if (it != container.end()) {
94 return it->second;
95 } else {
96 return defaultValue;
97 }
98}
99
100/**
101 * Append elements to a container
102 */
103template <class C, typename R>
104void append(C& container, R&& range) {
105 container.insert(container.end(), std::begin(range), std::end(range));
106}
107
108/**
109 * A utility function enabling the creation of a vector with a fixed set of
110 * elements within a single expression. This is the base case covering empty
111 * vectors.
112 */
113template <typename T>
114std::vector<T> toVector() {
115 return std::vector<T>();
116}
117
118/**
119 * A utility function enabling the creation of a vector with a fixed set of
120 * elements within a single expression. This is the step case covering vectors
121 * of arbitrary length.
122 */
123template <typename T, typename... R>
124std::vector<T> toVector(T first, R... rest) {
125 // Init-lists are effectively const-arrays. You can't `move` out of them.
126 // Combine with `vector`s not having variadic constructors, can't do:
127 // `vector{Own<A>{}, Own<A>{}}`
128 // This is inexcusably awful and defeats the purpose of having init-lists.
129 std::vector<T> xs;
130 T ary[] = {std::move(first), std::move(rest)...};
131 for (auto& x : ary) {
132 xs.push_back(std::move(x));
133 }
134 return xs;
135}
136
137/**
138 * A utility function enabling the creation of a vector of pointers.
139 */
140template <typename A = void, typename T, typename U = std::conditional_t<std::is_same_v<A, void>, T, A>>
141std::vector<U*> toPtrVector(const VecOwn<T>& v) {
142 std::vector<U*> res;
143 for (auto& e : v) {
144 res.push_back(e.get());
145 }
146 return res;
147}
148
149// -------------------------------------------------------------------------------
150// Equality Utilities
151// -------------------------------------------------------------------------------
152
153/**
154 * Cast the values, from baseType to toType and compare using ==. (if casting fails -> return false.)
155 *
156 * @tparam baseType, initial Type of values
157 * @tparam toType, type where equality comparison takes place.
158 */
159template <typename toType, typename baseType>
160bool castEq(const baseType* left, const baseType* right) {
161 if (auto castedLeft = as<toType>(left)) {
162 if (auto castedRight = as<toType>(right)) {
163 return castedLeft == castedRight;
164 }
165 }
166 return false;
167}
168
169/**
170 * A functor class supporting the values pointers are pointing to.
171 */
172template <typename T>
173struct comp_deref {
174 bool operator()(const T& a, const T& b) const {
175 if (a == nullptr) {
176 return false;
177 }
178 if (b == nullptr) {
179 return false;
180 }
181 return *a == *b;
182 }
183};
184
185/**
186 * A function testing whether two containers are equal with the given Comparator.
187 */
188template <typename Container, typename Comparator>
189bool equal_targets(const Container& a, const Container& b, const Comparator& comp) {
190 // check reference
191 if (&a == &b) {
192 return true;
193 }
194
195 // check size
196 if (a.size() != b.size()) {
197 return false;
198 }
199
200 // check content
201 return std::equal(a.begin(), a.end(), b.begin(), comp);
202}
203
204/**
205 * A function testing whether two containers of pointers are referencing equivalent
206 * targets.
207 */
208template <typename T, template <typename...> class Container>
209bool equal_targets(const Container<T*>& a, const Container<T*>& b) {
210 return equal_targets(a, b, comp_deref<T*>());
211}
212
213/**
214 * A function testing whether two containers of unique pointers are referencing equivalent
215 * targets.
216 */
217template <typename T, template <typename...> class Container>
218bool equal_targets(const Container<Own<T>>& a, const Container<Own<T>>& b) {
219 return equal_targets(a, b, comp_deref<Own<T>>());
220}
221
222#ifdef _MSC_VER
223// issue:
224// https://developercommunity.visualstudio.com/t/c-template-template-not-recognized-as-class-templa/558979
225template <typename T>
226bool equal_targets(const std::vector<Own<T>>& a, const std::vector<Own<T>>& b) {
227 return equal_targets(a, b, comp_deref<Own<T>>());
228}
229
230template <typename T>
231bool equal_targets(const std::vector<T>& a, const std::vector<T>& b) {
232 return equal_targets(a, b, comp_deref<T>());
233}
234#endif
235
236/**
237 * A function testing whether two maps of unique pointers are referencing to equivalent
238 * targets.
239 */
240template <typename Key, typename Value, typename Cmp>
241bool equal_targets(const std::map<Key, Own<Value>, Cmp>& a, const std::map<Key, Own<Value>, Cmp>& b) {
242 auto comp = comp_deref<Own<Value>>();
243 return equal_targets(
244 a, b, [&comp](auto& a, auto& b) { return a.first == b.first && comp(a.second, b.second); });
245}
246
247/**
248 * A function testing whether two maps are equivalent using projected values.
249 */
250template <typename Key, typename Value, typename Cmp, typename F>
251bool equal_targets_map(const std::map<Key, Value, Cmp>& a, const std::map<Key, Value, Cmp>& b, F&& comp) {
252 return equal_targets(
253 a, b, [&](auto& a, auto& b) { return a.first == b.first && comp(a.second, b.second); });
254}
255
256// -------------------------------------------------------------------------------
257// Checking Utilities
258// -------------------------------------------------------------------------------
259template <typename R>
260bool allValidPtrs(R const& range) {
261 return std::all_of(range.begin(), range.end(), [](auto&& p) { return (bool)p; });
262}
263
264} // namespace souffle
265
266namespace std {
267template <typename Iter, typename F>
268struct iterator_traits<souffle::TransformIterator<Iter, F>> {
269 using iter_t = std::iterator_traits<Iter>;
270 using iter_tag = typename iter_t::iterator_category;
271 using difference_type = typename iter_t::difference_type;
272 using reference = decltype(std::declval<F&>()(*std::declval<Iter>()));
273 using value_type = std::remove_cv_t<std::remove_reference_t<reference>>;
274 using iterator_category = std::conditional_t<std::is_base_of_v<std::random_access_iterator_tag, iter_tag>,
275 std::random_access_iterator_tag, iter_tag>;
276};
277} // namespace std