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

666 lines, 425 significant
1#pragma once
2
3#if __cplusplus >= 202000L
4
5#include <span> // use std lib impl
6
7namespace souffle {
8constexpr auto dynamic_extent = std::dynamic_extent;
9
10template <typename A, std::size_t E = std::dynamic_extent>
11using span = std::span<A, E>;
12} // namespace souffle
13
14#else
15
16// clang-format off
17/*
18This is an implementation of C++20's std::span
19http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/n4820.pdf
20*/
21
22// Copyright Tristan Brindle 2018.
23// Distributed under the Boost Software License, Version 1.0.
24// (See accompanying file ../../LICENSE_1_0.txt or copy at
25// https://www.boost.org/LICENSE_1_0.txt)
26
27#ifndef TCB_SPAN_HPP_INCLUDED
28#define TCB_SPAN_HPP_INCLUDED
29
30#include <array>
31#include <cstddef>
32#include <cstdint>
33#include <type_traits>
34
35#ifndef TCB_SPAN_NO_EXCEPTIONS
36// Attempt to discover whether we're being compiled with exception support
37#if !(defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND))
38#define TCB_SPAN_NO_EXCEPTIONS
39#endif
40#endif
41
42#ifndef TCB_SPAN_NO_EXCEPTIONS
43#include <cstdio>
44#include <stdexcept>
45#endif
46
47// Various feature test macros
48
49#ifndef TCB_SPAN_NAMESPACE_NAME
50#define TCB_SPAN_NAMESPACE_NAME tcb
51#endif
52
53#if __cplusplus >= 201703L || (defined(_MSVC_LANG) && _MSVC_LANG >= 201703L)
54#define TCB_SPAN_HAVE_CPP17
55#endif
56
57#if __cplusplus >= 201402L || (defined(_MSVC_LANG) && _MSVC_LANG >= 201402L)
58#define TCB_SPAN_HAVE_CPP14
59#endif
60
61namespace TCB_SPAN_NAMESPACE_NAME {
62
63// Establish default contract checking behavior
64#if !defined(TCB_SPAN_THROW_ON_CONTRACT_VIOLATION) && \
65 !defined(TCB_SPAN_TERMINATE_ON_CONTRACT_VIOLATION) && \
66 !defined(TCB_SPAN_NO_CONTRACT_CHECKING)
67#if defined(NDEBUG) || !defined(TCB_SPAN_HAVE_CPP14)
68#define TCB_SPAN_NO_CONTRACT_CHECKING
69#else
70#define TCB_SPAN_TERMINATE_ON_CONTRACT_VIOLATION
71#endif
72#endif
73
74#if defined(TCB_SPAN_THROW_ON_CONTRACT_VIOLATION)
75struct contract_violation_error : std::logic_error {
76 explicit contract_violation_error(const char* msg) : std::logic_error(msg)
77 {}
78};
79
80inline void contract_violation(const char* msg)
81{
82 throw contract_violation_error(msg);
83}
84
85#elif defined(TCB_SPAN_TERMINATE_ON_CONTRACT_VIOLATION)
86[[noreturn]] inline void contract_violation(const char* /*unused*/)
87{
88 std::terminate();
89}
90#endif
91
92#if !defined(TCB_SPAN_NO_CONTRACT_CHECKING)
93#define TCB_SPAN_STRINGIFY(cond) #cond
94#define TCB_SPAN_EXPECT(cond) \
95 cond ? (void) 0 : contract_violation("Expected " TCB_SPAN_STRINGIFY(cond))
96#else
97#define TCB_SPAN_EXPECT(cond)
98#endif
99
100#if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_inline_variables)
101#define TCB_SPAN_INLINE_VAR inline
102#else
103#define TCB_SPAN_INLINE_VAR
104#endif
105
106#if defined(TCB_SPAN_HAVE_CPP14) || \
107 (defined(__cpp_constexpr) && __cpp_constexpr >= 201304)
108#define TCB_SPAN_HAVE_CPP14_CONSTEXPR
109#endif
110
111#if defined(TCB_SPAN_HAVE_CPP14_CONSTEXPR)
112#define TCB_SPAN_CONSTEXPR14 constexpr
113#else
114#define TCB_SPAN_CONSTEXPR14
115#endif
116
117#if defined(TCB_SPAN_HAVE_CPP14_CONSTEXPR) && \
118 (!defined(_MSC_VER) || _MSC_VER > 1900)
119#define TCB_SPAN_CONSTEXPR_ASSIGN constexpr
120#else
121#define TCB_SPAN_CONSTEXPR_ASSIGN
122#endif
123
124#if defined(TCB_SPAN_NO_CONTRACT_CHECKING)
125#define TCB_SPAN_CONSTEXPR11 constexpr
126#else
127#define TCB_SPAN_CONSTEXPR11 TCB_SPAN_CONSTEXPR14
128#endif
129
130#if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_deduction_guides)
131#define TCB_SPAN_HAVE_DEDUCTION_GUIDES
132#endif
133
134#if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_lib_byte)
135#define TCB_SPAN_HAVE_STD_BYTE
136#endif
137
138#if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_lib_array_constexpr)
139#define TCB_SPAN_HAVE_CONSTEXPR_STD_ARRAY_ETC
140#endif
141
142#if defined(TCB_SPAN_HAVE_CONSTEXPR_STD_ARRAY_ETC)
143#define TCB_SPAN_ARRAY_CONSTEXPR constexpr
144#else
145#define TCB_SPAN_ARRAY_CONSTEXPR
146#endif
147
148#ifdef TCB_SPAN_HAVE_STD_BYTE
149using byte = std::byte;
150#else
151using byte = unsigned char;
152#endif
153
154#if defined(TCB_SPAN_HAVE_CPP17)
155#define TCB_SPAN_NODISCARD [[nodiscard]]
156#else
157#define TCB_SPAN_NODISCARD
158#endif
159
160TCB_SPAN_INLINE_VAR constexpr std::size_t dynamic_extent = SIZE_MAX;
161
162template <typename ElementType, std::size_t Extent = dynamic_extent>
163class span;
164
165namespace detail {
166
167template <typename E, std::size_t S>
168struct span_storage {
169 constexpr span_storage() noexcept = default;
170
171 constexpr span_storage(E* p_ptr, std::size_t /*unused*/) noexcept
172 : ptr(p_ptr)
173 {}
174
175 E* ptr = nullptr;
176 static constexpr std::size_t size = S;
177};
178
179template <typename E>
180struct span_storage<E, dynamic_extent> {
181 constexpr span_storage() noexcept = default;
182
183 constexpr span_storage(E* p_ptr, std::size_t p_size) noexcept
184 : ptr(p_ptr), size(p_size)
185 {}
186
187 E* ptr = nullptr;
188 std::size_t size = 0;
189};
190
191// Reimplementation of C++17 std::size() and std::data()
192#if defined(TCB_SPAN_HAVE_CPP17) || \
193 defined(__cpp_lib_nonmember_container_access)
194using std::data;
195using std::size;
196#else
197template <class C>
198constexpr auto size(const C& c) -> decltype(c.size())
199{
200 return c.size();
201}
202
203template <class T, std::size_t N>
204constexpr std::size_t size(const T (&)[N]) noexcept
205{
206 return N;
207}
208
209template <class C>
210constexpr auto data(C& c) -> decltype(c.data())
211{
212 return c.data();
213}
214
215template <class C>
216constexpr auto data(const C& c) -> decltype(c.data())
217{
218 return c.data();
219}
220
221template <class T, std::size_t N>
222constexpr T* data(T (&array)[N]) noexcept
223{
224 return array;
225}
226
227template <class E>
228constexpr const E* data(std::initializer_list<E> il) noexcept
229{
230 return il.begin();
231}
232#endif // TCB_SPAN_HAVE_CPP17
233
234#if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_lib_void_t)
235using std::void_t;
236#else
237template <typename...>
238using void_t = void;
239#endif
240
241template <typename T>
242using uncvref_t =
243 typename std::remove_cv<typename std::remove_reference<T>::type>::type;
244
245template <typename>
246struct is_span : std::false_type {};
247
248template <typename T, std::size_t S>
249struct is_span<span<T, S>> : std::true_type {};
250
251template <typename>
252struct is_std_array : std::false_type {};
253
254template <typename T, std::size_t N>
255struct is_std_array<std::array<T, N>> : std::true_type {};
256
257template <typename, typename = void>
258struct has_size_and_data : std::false_type {};
259
260template <typename T>
261struct has_size_and_data<T, void_t<decltype(detail::size(std::declval<T>())),
262 decltype(detail::data(std::declval<T>()))>>
263 : std::true_type {};
264
265template <typename C, typename U = uncvref_t<C>>
266struct is_container {
267 static constexpr bool value =
268 !is_span<U>::value && !is_std_array<U>::value &&
269 !std::is_array<U>::value && has_size_and_data<C>::value;
270};
271
272template <typename T>
273using remove_pointer_t = typename std::remove_pointer<T>::type;
274
275template <typename, typename, typename = void>
276struct is_container_element_type_compatible : std::false_type {};
277
278template <typename T, typename E>
279struct is_container_element_type_compatible<
280 T, E,
281 typename std::enable_if<
282 !std::is_same<typename std::remove_cv<decltype(
283 detail::data(std::declval<T>()))>::type,
284 void>::value>::type>
285 // HACK: WORKAROUND - GCC 9.2.1 claims `A* (*)[]` is not compatible w/ `A const* (*)[]`.
286 // This seems BS and Clang 10.0 is perfectly happy.
287 // GCC 9.2.1 does, however, agree that `A**` is compatible w/ `A const**`.
288 // Use the `*` test instead of `(*)[]`.
289 : std::is_convertible<
290 remove_pointer_t<decltype(detail::data(std::declval<T>()))>*,
291 E*> {};
292
293template <typename, typename = std::size_t>
294struct is_complete : std::false_type {};
295
296template <typename T>
297struct is_complete<T, decltype(sizeof(T))> : std::true_type {};
298
299} // namespace detail
300
301template <typename ElementType, std::size_t Extent>
302class span {
303 static_assert(std::is_object<ElementType>::value,
304 "A span's ElementType must be an object type (not a "
305 "reference type or void)");
306 static_assert(detail::is_complete<ElementType>::value,
307 "A span's ElementType must be a complete type (not a forward "
308 "declaration)");
309 static_assert(!std::is_abstract<ElementType>::value,
310 "A span's ElementType cannot be an abstract class type");
311
312 using storage_type = detail::span_storage<ElementType, Extent>;
313
314public:
315 // constants and types
316 using element_type = ElementType;
317 using value_type = typename std::remove_cv<ElementType>::type;
318 using size_type = std::size_t;
319 using difference_type = std::ptrdiff_t;
320 using pointer = element_type*;
321 using const_pointer = const element_type*;
322 using reference = element_type&;
323 using const_reference = const element_type&;
324 using iterator = pointer;
325 using reverse_iterator = std::reverse_iterator<iterator>;
326
327 static constexpr size_type extent = Extent;
328
329 // [span.cons], span constructors, copy, assignment, and destructor
330 template <
331 std::size_t E = Extent,
332 typename std::enable_if<(E == dynamic_extent || E <= 0), int>::type = 0>
333 constexpr span() noexcept // NOLINT : clang-tidy is mistaken. one cannot `default` a template ctor
334 {}
335
336 TCB_SPAN_CONSTEXPR11 span(pointer ptr, size_type count)
337 : storage_(ptr, count)
338 {
339 TCB_SPAN_EXPECT(extent == dynamic_extent || count == extent);
340 }
341
342 TCB_SPAN_CONSTEXPR11 span(pointer first_elem, pointer last_elem)
343 : storage_(first_elem, last_elem - first_elem)
344 {
345 TCB_SPAN_EXPECT(extent == dynamic_extent ||
346 last_elem - first_elem ==
347 static_cast<std::ptrdiff_t>(extent));
348 }
349
350 template <std::size_t N, std::size_t E = Extent,
351 typename std::enable_if<
352 (E == dynamic_extent || N == E) &&
353 detail::is_container_element_type_compatible<
354 element_type (&)[N], ElementType>::value,
355 int>::type = 0>
356 constexpr span(element_type (&arr)[N]) noexcept : storage_(arr, N)
357 {}
358
359 template <std::size_t N, std::size_t E = Extent,
360 typename std::enable_if<
361 (E == dynamic_extent || N == E) &&
362 detail::is_container_element_type_compatible<
363 std::array<value_type, N>&, ElementType>::value,
364 int>::type = 0>
365 TCB_SPAN_ARRAY_CONSTEXPR span(std::array<value_type, N>& arr) noexcept
366 : storage_(arr.data(), N)
367 {}
368
369 template <std::size_t N, std::size_t E = Extent,
370 typename std::enable_if<
371 (E == dynamic_extent || N == E) &&
372 detail::is_container_element_type_compatible<
373 const std::array<value_type, N>&, ElementType>::value,
374 int>::type = 0>
375 TCB_SPAN_ARRAY_CONSTEXPR span(const std::array<value_type, N>& arr) noexcept
376 : storage_(arr.data(), N)
377 {}
378
379 template <
380 typename Container, std::size_t E = Extent,
381 typename std::enable_if<
382 E == dynamic_extent && detail::is_container<Container>::value &&
383 detail::is_container_element_type_compatible<
384 Container&, ElementType>::value,
385 int>::type = 0>
386 constexpr span(Container& cont)
387 : storage_(detail::data(cont), detail::size(cont))
388 {}
389
390 template <
391 typename Container, std::size_t E = Extent,
392 typename std::enable_if<
393 E == dynamic_extent && detail::is_container<Container>::value &&
394 detail::is_container_element_type_compatible<
395 const Container&, ElementType>::value,
396 int>::type = 0>
397 constexpr span(const Container& cont)
398 : storage_(detail::data(cont), detail::size(cont))
399 {}
400
401 constexpr span(const span& other) noexcept = default;
402
403 template <typename OtherElementType, std::size_t OtherExtent,
404 typename std::enable_if<
405 (Extent == OtherExtent || Extent == dynamic_extent) &&
406 std::is_convertible<OtherElementType (*)[],
407 ElementType (*)[]>::value,
408 int>::type = 0>
409 constexpr span(const span<OtherElementType, OtherExtent>& other) noexcept
410 : storage_(other.data(), other.size())
411 {}
412
413 ~span() noexcept = default;
414
415 TCB_SPAN_CONSTEXPR_ASSIGN span&
416 operator=(const span& other) noexcept = default;
417
418 // [span.sub], span subviews
419 template <std::size_t Count>
420 TCB_SPAN_CONSTEXPR11 span<element_type, Count> first() const
421 {
422 TCB_SPAN_EXPECT(Count <= size());
423 return {data(), Count};
424 }
425
426 template <std::size_t Count>
427 TCB_SPAN_CONSTEXPR11 span<element_type, Count> last() const
428 {
429 TCB_SPAN_EXPECT(Count <= size());
430 return {data() + (size() - Count), Count};
431 }
432
433 template <std::size_t Offset, std::size_t Count = dynamic_extent>
434 using subspan_return_t =
435 span<ElementType, Count != dynamic_extent
436 ? Count
437 : (Extent != dynamic_extent ? Extent - Offset
438 : dynamic_extent)>;
439
440 template <std::size_t Offset, std::size_t Count = dynamic_extent>
441 TCB_SPAN_CONSTEXPR11 subspan_return_t<Offset, Count> subspan() const
442 {
443 TCB_SPAN_EXPECT(Offset <= size() &&
444 (Count == dynamic_extent || Offset + Count <= size()));
445 return {data() + Offset,
446 Count != dynamic_extent ? Count : size() - Offset};
447 }
448
449 TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
450 first(size_type count) const
451 {
452 TCB_SPAN_EXPECT(count <= size());
453 return {data(), count};
454 }
455
456 TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
457 last(size_type count) const
458 {
459 TCB_SPAN_EXPECT(count <= size());
460 return {data() + (size() - count), count};
461 }
462
463 TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
464 subspan(size_type offset, size_type count = dynamic_extent) const
465 {
466 TCB_SPAN_EXPECT(offset <= size() &&
467 (count == dynamic_extent || offset + count <= size()));
468 return {data() + offset,
469 count == dynamic_extent ? size() - offset : count};
470 }
471
472 // [span.obs], span observers
473 constexpr size_type size() const noexcept { return storage_.size; }
474
475 constexpr size_type size_bytes() const noexcept
476 {
477 return size() * sizeof(element_type);
478 }
479
480 TCB_SPAN_NODISCARD constexpr bool empty() const noexcept
481 {
482 return size() == 0;
483 }
484
485 // [span.elem], span element access
486 TCB_SPAN_CONSTEXPR11 reference operator[](size_type idx) const
487 {
488 TCB_SPAN_EXPECT(idx < size());
489 return *(data() + idx);
490 }
491
492 TCB_SPAN_CONSTEXPR11 reference front() const
493 {
494 TCB_SPAN_EXPECT(!empty());
495 return *data();
496 }
497
498 TCB_SPAN_CONSTEXPR11 reference back() const
499 {
500 TCB_SPAN_EXPECT(!empty());
501 return *(data() + (size() - 1));
502 }
503
504 constexpr pointer data() const noexcept { return storage_.ptr; }
505
506 // [span.iterators], span iterator support
507 constexpr iterator begin() const noexcept { return data(); }
508
509 constexpr iterator end() const noexcept { return data() + size(); }
510
511 TCB_SPAN_ARRAY_CONSTEXPR reverse_iterator rbegin() const noexcept
512 {
513 return reverse_iterator(end());
514 }
515
516 TCB_SPAN_ARRAY_CONSTEXPR reverse_iterator rend() const noexcept
517 {
518 return reverse_iterator(begin());
519 }
520
521private:
522 storage_type storage_{};
523};
524
525#ifdef TCB_SPAN_HAVE_DEDUCTION_GUIDES
526
527/* Deduction Guides */
528template <class T, std::size_t N>
529span(T (&)[N])->span<T, N>;
530
531template <class T, std::size_t N>
532span(std::array<T, N>&)->span<T, N>;
533
534template <class T, std::size_t N>
535span(const std::array<T, N>&)->span<const T, N>;
536
537template <class Container>
538span(Container&)->span<typename Container::value_type>;
539
540template <class Container>
541span(const Container&)->span<const typename Container::value_type>;
542
543#endif // TCB_HAVE_DEDUCTION_GUIDES
544
545template <typename ElementType, std::size_t Extent>
546constexpr span<ElementType, Extent>
547make_span(span<ElementType, Extent> s) noexcept
548{
549 return s;
550}
551
552template <typename T, std::size_t N>
553constexpr span<T, N> make_span(T (&arr)[N]) noexcept
554{
555 return {arr};
556}
557
558template <typename T, std::size_t N>
559TCB_SPAN_ARRAY_CONSTEXPR span<T, N> make_span(std::array<T, N>& arr) noexcept
560{
561 return {arr};
562}
563
564template <typename T, std::size_t N>
565TCB_SPAN_ARRAY_CONSTEXPR span<const T, N>
566make_span(const std::array<T, N>& arr) noexcept
567{
568 return {arr};
569}
570
571template <typename Container>
572constexpr span<typename Container::value_type> make_span(Container& cont)
573{
574 return {cont};
575}
576
577template <typename Container>
578constexpr span<const typename Container::value_type>
579make_span(const Container& cont)
580{
581 return {cont};
582}
583
584template <typename ElementType, std::size_t Extent>
585span<const byte, ((Extent == dynamic_extent) ? dynamic_extent
586 : sizeof(ElementType) * Extent)>
587as_bytes(span<ElementType, Extent> s) noexcept
588{
589 return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()};
590}
591
592template <
593 class ElementType, std::size_t Extent,
594 typename std::enable_if<!std::is_const<ElementType>::value, int>::type = 0>
595span<byte, ((Extent == dynamic_extent) ? dynamic_extent
596 : sizeof(ElementType) * Extent)>
597as_writable_bytes(span<ElementType, Extent> s) noexcept
598{
599 return {reinterpret_cast<byte*>(s.data()), s.size_bytes()};
600}
601
602template <std::size_t N, typename E, std::size_t S>
603constexpr auto get(span<E, S> s) -> decltype(s[N])
604{
605 return s[N];
606}
607
608} // namespace TCB_SPAN_NAMESPACE_NAME
609
610namespace std {
611
612// see: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82716
613// libc++: https://reviews.llvm.org/D55466#1325498
614// `libc++` changed to use `struct`
615// spec: http://eel.is/c++draft/tuple.helper
616// Spec says to use `struct`.
617// MSVC: Has different ABI for `class`/`struct`.
618// Defined `tuple_size` as `class`.
619#if defined(_MSC_VER)
620 #define TCB_SPAN_TUPLE_SIZE_KIND class
621#else
622 #define TCB_SPAN_TUPLE_SIZE_KIND struct
623#endif
624
625#if defined(__clang__)
626 #pragma clang diagnostic push
627 #pragma clang diagnostic ignored "-Wmismatched-tags"
628#endif
629
630template <typename ElementType, std::size_t Extent>
631TCB_SPAN_TUPLE_SIZE_KIND tuple_size<TCB_SPAN_NAMESPACE_NAME::span<ElementType, Extent>>
632 : public integral_constant<std::size_t, Extent> {};
633
634template <typename ElementType>
635TCB_SPAN_TUPLE_SIZE_KIND tuple_size<TCB_SPAN_NAMESPACE_NAME::span<
636 ElementType, TCB_SPAN_NAMESPACE_NAME::dynamic_extent>>; // not defined
637
638template <std::size_t I, typename ElementType, std::size_t Extent>
639TCB_SPAN_TUPLE_SIZE_KIND tuple_element<I, TCB_SPAN_NAMESPACE_NAME::span<ElementType, Extent>> {
640public:
641 static_assert(Extent != TCB_SPAN_NAMESPACE_NAME::dynamic_extent &&
642 I < Extent,
643 "");
644 using type = ElementType;
645};
646
647#if defined(__clang__)
648 #pragma clang diagnostic pop
649#endif
650
651#undef TCB_SPAN_TUPLE_SIZE_KIND
652
653} // end namespace std
654
655#endif // TCB_SPAN_HPP_INCLUDED
656
657// clang-format on
658
659namespace souffle {
660constexpr auto dynamic_extent = tcb::dynamic_extent;
661
662template <typename A, std::size_t E = tcb::dynamic_extent>
663using span = tcb::span<A, E>;
664} // namespace souffle
665
666#endif