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 |
|
26 | namespace souffle {
|
27 |
|
28 | namespace 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
|
42 | template <typename F>
|
43 | F 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 | */
|
71 | template <typename Iter, typename F>
|
72 | class TransformIterator {
|
73 | using iter_t = std::iterator_traits<Iter>;
|
74 |
|
75 | public:
|
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 |
|
179 | private:
|
180 | /* The nested iterator. */
|
181 | Iter iter;
|
182 | F fun;
|
183 | };
|
184 |
|
185 | template <typename Iter, typename F>
|
186 | auto operator+(
|
187 | typename TransformIterator<Iter, F>::difference_type n, TransformIterator<Iter, F> const& iter) {
|
188 | return iter + n;
|
189 | }
|
190 |
|
191 | template <typename Iter, typename F>
|
192 | auto 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 | */
|
201 | namespace detail {
|
202 | // HACK: Use explicit structure w/ `operator()` b/c pre-C++20 lambdas do not have copy-assign operators
|
203 | struct 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
|
211 | struct IterTransformToPtr {
|
212 | template <typename A>
|
213 | A* operator()(Own<A> const& x) const {
|
214 | return x.get();
|
215 | }
|
216 | };
|
217 |
|
218 | } // namespace detail
|
219 |
|
220 | template <typename Iter>
|
221 | using 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 | */
|
227 | template <typename Iter>
|
228 | auto 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 | */
|
235 | template <typename Iter>
|
236 | auto 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 | */
|
248 | template <typename Iter>
|
249 | struct 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 | */
|
327 | template <typename Iter>
|
328 | range<Iter> make_range(const Iter& a, const Iter& b) {
|
329 | return range<Iter>(a, b);
|
330 | }
|
331 |
|
332 | template <typename Iter, typename F>
|
333 | auto 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 |
|
337 | template <typename R, typename F>
|
338 | auto makeTransformRange(R&& range, F const& f) {
|
339 | return makeTransformRange(range.begin(), range.end(), f);
|
340 | }
|
341 |
|
342 | template <typename Iter>
|
343 | auto makeDerefRange(Iter&& begin, Iter&& end) {
|
344 | return make_range(derefIter(std::forward<Iter>(begin)), derefIter(std::forward<Iter>(end)));
|
345 | }
|
346 |
|
347 | template <typename R>
|
348 | auto 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 | */
|
355 | template <typename Range, typename F>
|
356 | class OwningTransformRange {
|
357 | public:
|
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 |
|
400 | private:
|
401 | Range range;
|
402 | F f;
|
403 | };
|
404 |
|
405 | } // namespace souffle
|