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

405 lines, 210 significant
1/*
2 * Souffle - A Datalog Compiler
3 * Copyright (c) 2020, 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 Iteration.h
12 *
13 * @brief Utilities for iterators and ranges
14 *
15 ***********************************************************************/
16
17#pragma once
18
19#include "souffle/utility/Types.h"
20
21#include <iterator>
22#include <type_traits>
23#include <utility>
24#include <vector>
25
26namespace souffle {
27
28namespace detail {
29#ifdef _MSC_VER
30#pragma warning(push)
31#pragma warning(disable : 4172)
32#elif defined(__GNUC__) && (__GNUC__ >= 7)
33#pragma GCC diagnostic push
34#pragma GCC diagnostic ignored "-Wreturn-local-addr"
35#elif defined(__has_warning)
36#pragma clang diagnostic push
37#if __has_warning("-Wreturn-stack-address")
38#pragma clang diagnostic ignored "-Wreturn-stack-address"
39#endif
40#endif
41// This is a helper in the cases when the lambda is stateless
42template <typename F>
43F makeFun() {
44 static_assert(std::is_empty_v<F>);
45 // Even thought the lambda is stateless, it has no default ctor
46 // Is this gross? Yes, yes it is.
47 // FIXME: Remove after C++20
48 typename std::aligned_storage<sizeof(F)>::type fakeLam{};
49 return reinterpret_cast<F const&>(fakeLam);
50}
51#ifdef _MSC_VER
52#pragma warning(pop)
53#elif defined(__GNUC__) && (__GNUC__ >= 7)
54#pragma GCC diagnostic pop
55#elif defined(__has_warning)
56#pragma clang diagnostic pop
57#endif
58} // namespace detail
59
60// -------------------------------------------------------------
61// Iterators
62// -------------------------------------------------------------
63/**
64 * A wrapper for an iterator that transforms values returned by
65 * the underlying iter.
66 *
67 * @tparam Iter ... the type of wrapped iterator
68 * @tparam F ... the function to apply
69 *
70 */
71template <typename Iter, typename F>
72class TransformIterator {
73 using iter_t = std::iterator_traits<Iter>;
74
75public:
76 using difference_type = typename iter_t::difference_type;
77 // TODO: The iterator concept doesn't map correctly to ephemeral views.
78 // e.g. there is no l-value store for a deref.
79 // Figure out what these should be set to.
80 using value_type = decltype(std::declval<F>()(*std::declval<Iter>()));
81 using pointer = std::remove_reference_t<value_type>*;
82 using reference = value_type;
83 static_assert(std::is_empty_v<F>, "Function object must be stateless");
84
85 // some constructors
86 template <typename = std::enable_if_t<std::is_empty_v<F>>>
87 TransformIterator(Iter iter) : TransformIterator(std::move(iter), detail::makeFun<F>()) {}
88 TransformIterator(Iter iter, F f) : iter(std::move(iter)), fun(std::move(f)) {}
89
90 /* The equality operator as required by the iterator concept. */
91 bool operator==(const TransformIterator& other) const {
92 return iter == other.iter;
93 }
94
95 /* The not-equality operator as required by the iterator concept. */
96 bool operator!=(const TransformIterator& other) const {
97 return iter != other.iter;
98 }
99
100 bool operator<(TransformIterator const& other) const {
101 return iter < other.iter;
102 }
103
104 bool operator<=(TransformIterator const& other) const {
105 return iter <= other.iter;
106 }
107
108 bool operator>(TransformIterator const& other) const {
109 return iter > other.iter;
110 }
111
112 bool operator>=(TransformIterator const& other) const {
113 return iter >= other.iter;
114 }
115
116 /* The deref operator as required by the iterator concept. */
117 auto operator*() const -> reference {
118 return fun(*iter);
119 }
120
121 /* Support for the pointer operator. */
122 auto operator->() const {
123 return &**this;
124 }
125
126 /* The increment operator as required by the iterator concept. */
127 TransformIterator& operator++() {
128 ++iter;
129 return *this;
130 }
131
132 TransformIterator operator++(int) {
133 auto res = *this;
134 ++iter;
135 return res;
136 }
137
138 TransformIterator& operator--() {
139 --iter;
140 return *this;
141 }
142
143 TransformIterator operator--(int) {
144 auto res = *this;
145 --iter;
146 return res;
147 }
148
149 TransformIterator& operator+=(difference_type n) {
150 iter += n;
151 return *this;
152 }
153
154 TransformIterator operator+(difference_type n) {
155 auto res = *this;
156 res += n;
157 return res;
158 }
159
160 TransformIterator& operator-=(difference_type n) {
161 iter -= n;
162 return *this;
163 }
164
165 TransformIterator operator-(difference_type n) {
166 auto res = *this;
167 res -= n;
168 return res;
169 }
170
171 difference_type operator-(TransformIterator const& other) {
172 return iter - other.iter;
173 }
174
175 auto operator[](difference_type ii) const -> reference {
176 return f(iter[ii]);
177 }
178
179private:
180 /* The nested iterator. */
181 Iter iter;
182 F fun;
183};
184
185template <typename Iter, typename F>
186auto operator+(
187 typename TransformIterator<Iter, F>::difference_type n, TransformIterator<Iter, F> const& iter) {
188 return iter + n;
189}
190
191template <typename Iter, typename F>
192auto transformIter(Iter&& iter, F&& f) {
193 return TransformIterator<remove_cvref_t<Iter>, std::remove_reference_t<F>>(
194 std::forward<Iter>(iter), std::forward<F>(f));
195}
196
197/**
198 * A wrapper for an iterator obtaining pointers of a certain type,
199 * dereferencing values before forwarding them to the consumer.
200 */
201namespace detail {
202// HACK: Use explicit structure w/ `operator()` b/c pre-C++20 lambdas do not have copy-assign operators
203struct IterTransformDeref {
204 template <typename A>
205 auto operator()(A&& x) const -> decltype(*x) {
206 return *x;
207 }
208};
209
210// HACK: Use explicit structure w/ `operator()` b/c pre-C++20 lambdas do not have copy-assign operators
211struct IterTransformToPtr {
212 template <typename A>
213 A* operator()(Own<A> const& x) const {
214 return x.get();
215 }
216};
217
218} // namespace detail
219
220template <typename Iter>
221using IterDerefWrapper = TransformIterator<Iter, detail::IterTransformDeref>;
222
223/**
224 * A factory function enabling the construction of a dereferencing
225 * iterator utilizing the automated deduction of template parameters.
226 */
227template <typename Iter>
228auto derefIter(Iter&& iter) {
229 return transformIter(std::forward<Iter>(iter), detail::IterTransformDeref{});
230}
231
232/**
233 * A factory function that transforms an smart-ptr iter to dumb-ptr iter.
234 */
235template <typename Iter>
236auto ptrIter(Iter&& iter) {
237 return transformIter(std::forward<Iter>(iter), detail::IterTransformToPtr{});
238}
239
240// -------------------------------------------------------------
241// Ranges
242// -------------------------------------------------------------
243
244/**
245 * A utility class enabling representation of ranges by pairing
246 * two iterator instances marking lower and upper boundaries.
247 */
248template <typename Iter>
249struct range {
250 using iterator = Iter;
251 using const_iterator = Iter;
252
253 // the lower and upper boundary
254 Iter a, b;
255
256 // a constructor accepting a lower and upper boundary
257 range(Iter a, Iter b) : a(std::move(a)), b(std::move(b)) {}
258
259 // default copy / move and assignment support
260 range(const range&) = default;
261 range(range&&) = default;
262 range& operator=(const range&) = default;
263
264 // get the lower boundary (for for-all loop)
265 Iter& begin() {
266 return a;
267 }
268 const Iter& begin() const {
269 return a;
270 }
271
272 // get the upper boundary (for for-all loop)
273 Iter& end() {
274 return b;
275 }
276 const Iter& end() const {
277 return b;
278 }
279
280 // emptiness check
281 bool empty() const {
282 return a == b;
283 }
284
285 // splits up this range into the given number of partitions
286 std::vector<range> partition(std::size_t np = 100) {
287 // obtain the size
288 std::size_t n = 0;
289 for (auto i = a; i != b; ++i) {
290 n++;
291 }
292
293 // split it up
294 auto s = n / np;
295 auto r = n % np;
296 std::vector<range> res;
297 res.reserve(np);
298 auto cur = a;
299 auto last = cur;
300 std::size_t i = 0;
301 std::size_t p = 0;
302 while (cur != b) {
303 ++cur;
304 i++;
305 if (i >= (s + (p < r ? 1 : 0))) {
306 res.push_back({last, cur});
307 last = cur;
308 p++;
309 i = 0;
310 }
311 }
312 if (cur != last) {
313 res.push_back({last, cur});
314 }
315 return res;
316 }
317};
318
319/**
320 * A utility function enabling the construction of ranges
321 * without explicitly specifying the iterator type.
322 *
323 * @tparam Iter .. the iterator type
324 * @param a .. the lower boundary
325 * @param b .. the upper boundary
326 */
327template <typename Iter>
328range<Iter> make_range(const Iter& a, const Iter& b) {
329 return range<Iter>(a, b);
330}
331
332template <typename Iter, typename F>
333auto makeTransformRange(Iter&& begin, Iter&& end, F const& f) {
334 return make_range(transformIter(std::forward<Iter>(begin), f), transformIter(std::forward<Iter>(end), f));
335}
336
337template <typename R, typename F>
338auto makeTransformRange(R&& range, F const& f) {
339 return makeTransformRange(range.begin(), range.end(), f);
340}
341
342template <typename Iter>
343auto makeDerefRange(Iter&& begin, Iter&& end) {
344 return make_range(derefIter(std::forward<Iter>(begin)), derefIter(std::forward<Iter>(end)));
345}
346
347template <typename R>
348auto makePtrRange(R const& xs) {
349 return make_range(ptrIter(std::begin(xs)), ptrIter(std::end(xs)));
350}
351
352/**
353 * This wraps the Range container, and const_casts in place.
354 */
355template <typename Range, typename F>
356class OwningTransformRange {
357public:
358 using iterator = decltype(transformIter(std::begin(std::declval<Range>()), std::declval<F>()));
359 using const_iterator =
360 decltype(transformIter(std::begin(std::declval<const Range>()), std::declval<const F>()));
361
362 OwningTransformRange(Range&& range, F f) : range(std::move(range)), f(std::move(f)) {}
363
364 auto begin() {
365 return transformIter(std::begin(range), f);
366 }
367
368 auto begin() const {
369 return transformIter(std::begin(range), f);
370 }
371
372 auto cbegin() const {
373 return transformIter(std::cbegin(range), f);
374 }
375
376 auto end() {
377 return transformIter(std::end(range), f);
378 }
379
380 auto end() const {
381 return transformIter(std::end(range), f);
382 }
383
384 auto cend() const {
385 return transformIter(std::cend(range), f);
386 }
387
388 auto size() const {
389 return range.size();
390 }
391
392 auto& operator[](std::size_t ii) {
393 return begin()[ii];
394 }
395
396 auto& operator[](std::size_t ii) const {
397 return cbegin()[ii];
398 }
399
400private:
401 Range range;
402 F f;
403};
404
405} // namespace souffle