1// Copyright (C) 2023 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QSPAN_H
5#define QSPAN_H
6
7#include <QtCore/qcompilerdetection.h>
8#include <QtCore/qtypes.h>
9#include <QtCore/qcontainerfwd.h>
10
11#include <array>
12#include <cstddef>
13#include <cassert>
14#include <initializer_list>
15#include <QtCore/q20iterator.h>
16#include <QtCore/q20memory.h>
17#ifdef __cpp_lib_span
18#include <span>
19#endif
20#include <QtCore/q20type_traits.h>
21
22QT_BEGIN_NAMESPACE
23
24// like std::dynamic_extent
25namespace q20 {
26 inline constexpr auto dynamic_extent = std::size_t(-1);
27} // namespace q20
28
29QT_BEGIN_INCLUDE_NAMESPACE
30#ifdef __cpp_lib_span
31#ifdef __cpp_lib_concepts
32namespace std::ranges {
33// Officially, these are defined in <ranges>, but that is a heavy-hitter header.
34// OTOH, <span> must specialize these variable templates, too, so we assume that
35// <span> includes some meaningful subset of <ranges> and just go ahead and use them:
36template <typename T, std::size_t E>
37constexpr inline bool enable_borrowed_range<QT_PREPEND_NAMESPACE(QSpan)<T, E>> = true;
38template <typename T, std::size_t E>
39constexpr inline bool enable_view<QT_PREPEND_NAMESPACE(QSpan)<T, E>> = true;
40} // namespace std::ranges
41#endif // __cpp_lib_concepts
42#endif // __cpp_lib_span
43QT_END_INCLUDE_NAMESPACE
44
45namespace QSpanPrivate {
46
47template <typename From, typename To>
48std::conditional_t<std::is_const_v<From>, const To &, To &> // like [forward]/6.1 COPY_CONST
49const_propagated(To &in) { return in; }
50
51template <typename T, std::size_t E> class QSpanBase;
52
53template <typename T>
54struct is_qspan_helper : std::false_type {};
55template <typename T, std::size_t E>
56struct is_qspan_helper<QSpan<T, E>> : std::true_type {};
57template <typename T, std::size_t E>
58struct is_qspan_helper<QSpanBase<T, E>> : std::true_type {};
59template <typename T>
60using is_qspan = is_qspan_helper<q20::remove_cvref_t<T>>;
61
62template <typename T>
63struct is_std_span_helper : std::false_type {};
64#ifdef __cpp_lib_span
65template <typename T, std::size_t E>
66struct is_std_span_helper<std::span<T, E>> : std::true_type {};
67#endif // __cpp_lib_span
68template <typename T>
69using is_std_span = is_std_span_helper<q20::remove_cvref_t<T>>;
70
71template <typename T>
72struct is_std_array_helper : std::false_type {};
73template <typename T, std::size_t N>
74struct is_std_array_helper<std::array<T, N>> : std::true_type {};
75template <typename T>
76using is_std_array = is_std_array_helper<q20::remove_cvref_t<T>>;
77
78template <typename From, typename To>
79using is_qualification_conversion =
80 std::is_convertible<From(*)[], To(*)[]>; // https://eel.is/c++draft/span.cons#note-1
81template <typename From, typename To>
82constexpr inline bool is_qualification_conversion_v = is_qualification_conversion<From, To>::value;
83
84namespace AdlTester {
85#define MAKE_ADL_TEST(what) \
86 using std:: what; /* bring into scope */ \
87 template <typename T> using what ## _result = decltype( what (std::declval<T&&>())); \
88 /* end */
89MAKE_ADL_TEST(begin)
90MAKE_ADL_TEST(data)
91MAKE_ADL_TEST(size)
92#undef MAKE_ADL_TEST
93}
94
95// Replacements for std::ranges::XXX(), but only bringing in ADL XXX()s,
96// not doing the extra work C++20 requires
97template <typename Range>
98AdlTester::begin_result<Range> adl_begin(Range &&r) { using std::begin; return begin(r); }
99template <typename Range>
100AdlTester::data_result<Range> adl_data(Range &&r) { using std::data; return data(r); }
101template <typename Range>
102AdlTester::size_result<Range> adl_size(Range &&r) { using std::size; return size(r); }
103
104// Replacement for std::ranges::iterator_t (which depends on C++20 std::ranges::begin)
105// This one uses adl_begin() instead.
106template <typename Range>
107using iterator_t = decltype(QSpanPrivate::adl_begin(std::declval<Range&>()));
108template <typename Range>
109using range_reference_t = q20::iter_reference_t<QSpanPrivate::iterator_t<Range>>;
110
111template <typename T>
112class QSpanCommon {
113protected:
114 template <typename Iterator>
115 using is_compatible_iterator = std::conjunction<
116 // ### C++20: extend to contiguous_iteratorss
117 std::is_base_of<
118 std::random_access_iterator_tag,
119 typename std::iterator_traits<Iterator>::iterator_category
120 >,
121 is_qualification_conversion<
122 std::remove_reference_t<q20::iter_reference_t<Iterator>>,
123 T
124 >
125 >;
126 template <typename Iterator, typename End>
127 using is_compatible_iterator_and_sentinel = std::conjunction<
128 // ### C++20: extend to contiguous_iterators and real sentinels
129 is_compatible_iterator<Iterator>,
130 std::negation<std::is_convertible<End, std::size_t>>
131 >;
132 template <typename Range, typename = void> // wrap use of SFINAE-unfriendly iterator_t:
133 struct is_compatible_range_helper : std::false_type {};
134 template <typename Range>
135 struct is_compatible_range_helper<Range, std::void_t<QSpanPrivate::iterator_t<Range>>>
136 : is_compatible_iterator<QSpanPrivate::iterator_t<Range>> {};
137 template <typename Range>
138 using is_compatible_range = std::conjunction<
139 // ### C++20: extend to contiguous_iterators
140 std::negation<is_qspan<Range>>,
141 std::negation<is_std_span<Range>>,
142 std::negation<is_std_array<Range>>,
143 std::negation<std::is_array<q20::remove_cvref_t<Range>>>,
144 is_compatible_range_helper<Range>
145 >;
146
147 // constraints
148 template <typename Iterator>
149 using if_compatible_iterator = std::enable_if_t<
150 is_compatible_iterator<Iterator>::value
151 , bool>;
152 template <typename Iterator, typename End>
153 using if_compatible_iterator_and_sentinel = std::enable_if_t<
154 is_compatible_iterator_and_sentinel<Iterator, End>::value
155 , bool>;
156 template <typename Range>
157 using if_compatible_range = std::enable_if_t<is_compatible_range<Range>::value, bool>;
158}; // class QSpanCommon
159
160template <typename T, std::size_t E>
161class QSpanBase : protected QSpanCommon<T>
162{
163 static_assert(E < size_t{(std::numeric_limits<qsizetype>::max)()},
164 "QSpan only supports extents that fit into the signed size type (qsizetype).");
165
166 template <typename S, std::size_t N>
167 using if_compatible_array = std::enable_if_t<
168 N == E && is_qualification_conversion_v<S, T>
169 , bool>;
170
171 template <typename S>
172 using if_qualification_conversion = std::enable_if_t<
173 is_qualification_conversion_v<S, T>
174 , bool>;
175protected:
176 using Base = QSpanCommon<T>;
177
178 // data members:
179 T *m_data;
180 static constexpr qsizetype m_size = qsizetype(E);
181
182 // types and constants:
183 // (in QSpan only)
184
185 // constructors (need to be public d/t the way ctor inheriting works):
186public:
187 template <std::size_t E2 = E, std::enable_if_t<E2 == 0, bool> = true>
188 Q_IMPLICIT constexpr QSpanBase() noexcept : m_data{nullptr} {}
189
190 template <typename It, typename Base::template if_compatible_iterator<It> = true>
191 explicit constexpr QSpanBase(It first, qsizetype count)
192 : m_data{q20::to_address(first)}
193 {
194 Q_ASSERT(count == m_size);
195 }
196
197 template <typename It, typename End, typename Base::template if_compatible_iterator_and_sentinel<It, End> = true>
198 explicit constexpr QSpanBase(It first, End last)
199 : QSpanBase(first, last - first) {}
200
201 template <size_t N, std::enable_if_t<N == E, bool> = true>
202 Q_IMPLICIT constexpr QSpanBase(q20::type_identity_t<T> (&arr)[N]) noexcept
203 : QSpanBase(arr, N) {}
204
205 template <typename S, size_t N, if_compatible_array<S, N> = true>
206 Q_IMPLICIT constexpr QSpanBase(std::array<S, N> &arr) noexcept
207 : QSpanBase(arr.data(), N) {}
208
209 template <typename S, size_t N, if_compatible_array<S, N> = true>
210 Q_IMPLICIT constexpr QSpanBase(const std::array<S, N> &arr) noexcept
211 : QSpanBase(arr.data(), N) {}
212
213 template <typename Range, typename Base::template if_compatible_range<Range> = true>
214 Q_IMPLICIT constexpr QSpanBase(Range &&r)
215 : QSpanBase(QSpanPrivate::adl_data(QSpanPrivate::const_propagated<T>(r)), // no forward<>() here (std doesn't have it, either)
216 qsizetype(QSpanPrivate::adl_size(r))) // ditto, no forward<>()
217 {}
218
219 template <typename S, if_qualification_conversion<S> = true>
220 Q_IMPLICIT constexpr QSpanBase(QSpan<S, E> other) noexcept
221 : QSpanBase(other.data(), other.size())
222 {}
223
224 template <typename S, if_qualification_conversion<S> = true>
225 Q_IMPLICIT constexpr QSpanBase(QSpan<S> other)
226 : QSpanBase(other.data(), other.size())
227 {}
228
229 template <typename U = T, std::enable_if_t<std::is_const_v<U>, bool> = true>
230 Q_IMPLICIT constexpr QSpanBase(std::initializer_list<std::remove_cv_t<T>> il)
231 : QSpanBase(il.begin(), il.size())
232 {}
233
234#ifdef __cpp_lib_span
235 template <typename S, if_qualification_conversion<S> = true>
236 Q_IMPLICIT constexpr QSpanBase(std::span<S, E> other) noexcept
237 : QSpanBase(other.data(), other.size())
238 {}
239
240 template <typename S, if_qualification_conversion<S> = true>
241 Q_IMPLICIT constexpr QSpanBase(std::span<S> other)
242 : QSpanBase(other.data(), other.size())
243 {}
244#endif // __cpp_lib_span
245}; // class QSpanBase (fixed extent)
246
247template <typename T>
248class QSpanBase<T, q20::dynamic_extent> : protected QSpanCommon<T>
249{
250 template <typename S>
251 using if_qualification_conversion = std::enable_if_t<
252 is_qualification_conversion_v<S, T>
253 , bool>;
254protected:
255 using Base = QSpanCommon<T>;
256
257 // data members:
258 T *m_data;
259 qsizetype m_size;
260
261 // constructors (need to be public d/t the way ctor inheriting works):
262public:
263 Q_IMPLICIT constexpr QSpanBase() noexcept : m_data{nullptr}, m_size{0} {}
264
265 template <typename It, typename Base::template if_compatible_iterator<It> = true>
266 Q_IMPLICIT constexpr QSpanBase(It first, qsizetype count)
267 : m_data{q20::to_address(first)}, m_size{count} {}
268
269 template <typename It, typename End, typename Base::template if_compatible_iterator_and_sentinel<It, End> = true>
270 Q_IMPLICIT constexpr QSpanBase(It first, End last)
271 : QSpanBase(first, last - first) {}
272
273 template <size_t N>
274 Q_IMPLICIT constexpr QSpanBase(q20::type_identity_t<T> (&arr)[N]) noexcept
275 : QSpanBase(arr, N) {}
276
277 template <typename S, size_t N, if_qualification_conversion<S> = true>
278 Q_IMPLICIT constexpr QSpanBase(std::array<S, N> &arr) noexcept
279 : QSpanBase(arr.data(), N) {}
280
281 template <typename S, size_t N, if_qualification_conversion<S> = true>
282 Q_IMPLICIT constexpr QSpanBase(const std::array<S, N> &arr) noexcept
283 : QSpanBase(arr.data(), N) {}
284
285 template <typename Range, typename Base::template if_compatible_range<Range> = true>
286 Q_IMPLICIT constexpr QSpanBase(Range &&r)
287 : QSpanBase(QSpanPrivate::adl_data(QSpanPrivate::const_propagated<T>(r)), // no forward<>() here (std doesn't have it, either)
288 qsizetype(QSpanPrivate::adl_size(r))) // ditto, no forward<>()
289 {}
290
291 template <typename S, size_t N, if_qualification_conversion<S> = true>
292 Q_IMPLICIT constexpr QSpanBase(QSpan<S, N> other) noexcept
293 : QSpanBase(other.data(), other.size())
294 {}
295
296 template <typename U = T, std::enable_if_t<std::is_const_v<U>, bool> = true>
297 Q_IMPLICIT constexpr QSpanBase(std::initializer_list<std::remove_cv_t<T>> il) noexcept
298 : QSpanBase(il.begin(), il.size())
299 {}
300
301#ifdef __cpp_lib_span
302 template <typename S, size_t N, if_qualification_conversion<S> = true>
303 Q_IMPLICIT constexpr QSpanBase(std::span<S, N> other) noexcept
304 : QSpanBase(other.data(), other.size())
305 {}
306#endif // __cpp_lib_span
307}; // class QSpanBase (dynamic extent)
308
309} // namespace QSpanPrivate
310
311template <typename T, std::size_t E>
312class QSpan
313#ifndef Q_QDOC
314 : private QSpanPrivate::QSpanBase<T, E>
315#endif
316{
317 using Base = QSpanPrivate::QSpanBase<T, E>;
318 Q_ALWAYS_INLINE constexpr void verify([[maybe_unused]] qsizetype pos = 0,
319 [[maybe_unused]] qsizetype n = 1) const
320 {
321 Q_ASSERT(pos >= 0);
322 Q_ASSERT(pos <= size());
323 Q_ASSERT(n >= 0);
324 Q_ASSERT(n <= size() - pos);
325 }
326
327 template <std::size_t N>
328 static constexpr bool subspan_always_succeeds_v = N <= E && E != q20::dynamic_extent;
329public:
330 // constants and types
331 using value_type = std::remove_cv_t<T>;
332#ifdef QT_COMPILER_HAS_LWG3346
333 using iterator_concept = std::contiguous_iterator_tag;
334 using element_type = T;
335#endif
336 using size_type = qsizetype; // difference to std::span
337 using difference_type = qptrdiff; // difference to std::span
338 using pointer = T*;
339 using const_pointer = const T*;
340 using reference = T&;
341 using const_reference = const T&;
342 using iterator = pointer; // implementation-defined choice
343 using const_iterator = const_pointer; // implementation-defined choice
344 using reverse_iterator = std::reverse_iterator<iterator>;
345 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
346 static constexpr std::size_t extent = E;
347
348 // [span.cons], constructors, copy, and assignment
349 using Base::Base;
350#ifdef Q_QDOC
351 template <typename It> using if_compatible_iterator = bool;
352 template <typename S> using if_qualification_conversion = bool;
353 template <typename Range> using if_compatible_range = bool;
354 template <typename It, if_compatible_iterator<It> = true> constexpr QSpan(It first, qsizetype count);
355 template <typename It, if_compatible_iterator<It> = true> constexpr QSpan(It first, It last);
356 template <size_t N> constexpr QSpan(q20::type_identity_t<T> (&arr)[N]) noexcept;
357 template <typename S, size_t N, if_qualification_conversion<S> = true> constexpr QSpan(std::array<S, N> &arr) noexcept;
358 template <typename S, size_t N, if_qualification_conversion<S> = true> constexpr QSpan(const std::array<S, N> &arr) noexcept;
359 template <typename Range, if_compatible_range<Range> = true> constexpr QSpan(Range &&r);
360 template <typename S, size_t N, if_qualification_conversion<S> = true> constexpr QSpan(QSpan<S, N> other) noexcept;
361 template <typename S, size_t N, if_qualification_conversion<S> = true> constexpr QSpan(std::span<S, N> other) noexcept;
362 constexpr QSpan(std::initializer_list<value_type> il);
363#endif // Q_QDOC
364
365 // [span.obs]
366 [[nodiscard]] constexpr size_type size() const noexcept { return this->m_size; }
367 [[nodiscard]] constexpr size_type size_bytes() const noexcept { return size() * sizeof(T); }
368 [[nodiscard]] constexpr bool empty() const noexcept { return size() == 0; }
369
370 // [span.elem]
371 [[nodiscard]] constexpr reference operator[](size_type idx) const
372 { verify(pos: idx); return data()[idx]; }
373 [[nodiscard]] constexpr reference front() const { verify(); return *data(); }
374 [[nodiscard]] constexpr reference back() const { verify(); return data()[size() - 1]; }
375 [[nodiscard]] constexpr pointer data() const noexcept { return this->m_data; }
376
377 // [span.iterators]
378 [[nodiscard]] constexpr iterator begin() const noexcept { return data(); }
379 [[nodiscard]] constexpr iterator end() const noexcept { return data() + size(); }
380 [[nodiscard]] constexpr const_iterator cbegin() const noexcept { return begin(); }
381 [[nodiscard]] constexpr const_iterator cend() const noexcept { return end(); }
382 [[nodiscard]] constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
383 [[nodiscard]] constexpr reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }
384 [[nodiscard]] constexpr const_reverse_iterator crbegin() const noexcept { return rbegin(); }
385 [[nodiscard]] constexpr const_reverse_iterator crend() const noexcept { return rend(); }
386
387 // [span.sub]
388 template <std::size_t Count>
389 [[nodiscard]] constexpr QSpan<T, Count> first() const
390 noexcept(subspan_always_succeeds_v<Count>)
391 {
392 static_assert(Count <= E,
393 "Count cannot be larger than the span's extent.");
394 verify(pos: 0, n: Count);
395 return QSpan<T, Count>{data(), Count};
396 }
397
398 template <std::size_t Count>
399 [[nodiscard]] constexpr QSpan<T, Count> last() const
400 noexcept(subspan_always_succeeds_v<Count>)
401 {
402 static_assert(Count <= E,
403 "Count cannot be larger than the span's extent.");
404 verify(pos: 0, n: Count);
405 return QSpan<T, Count>{data() + (size() - Count), Count};
406 }
407
408 template <std::size_t Offset>
409 [[nodiscard]] constexpr auto subspan() const
410 noexcept(subspan_always_succeeds_v<Offset>)
411 {
412 static_assert(Offset <= E,
413 "Offset cannot be larger than the span's extent.");
414 verify(pos: Offset, n: 0);
415 if constexpr (E == q20::dynamic_extent)
416 return QSpan<T>{data() + Offset, qsizetype(size() - Offset)};
417 else
418 return QSpan<T, E - Offset>{data() + Offset, qsizetype(E - Offset)};
419 }
420
421 template <std::size_t Offset, std::size_t Count>
422 [[nodiscard]] constexpr auto subspan() const
423 noexcept(subspan_always_succeeds_v<Offset + Count>)
424 { return subspan<Offset>().template first<Count>(); }
425
426 [[nodiscard]] constexpr QSpan<T> first(size_type n) const { verify(pos: 0, n); return {data(), n}; }
427 [[nodiscard]] constexpr QSpan<T> last(size_type n) const { verify(pos: 0, n); return {data() + (size() - n), n}; }
428 [[nodiscard]] constexpr QSpan<T> subspan(size_type pos) const { verify(pos, n: 0); return {data() + pos, size() - pos}; }
429 [[nodiscard]] constexpr QSpan<T> subspan(size_type pos, size_type n) const { return subspan(pos).first(n); }
430
431 // Qt-compatibility API:
432 [[nodiscard]] constexpr bool isEmpty() const noexcept { return empty(); }
433 // nullary first()/last() clash with first<>() and last<>(), so they're not provided for QSpan
434 [[nodiscard]] constexpr QSpan<T> sliced(size_type pos) const { return subspan(pos); }
435 [[nodiscard]] constexpr QSpan<T> sliced(size_type pos, size_type n) const { return subspan(pos, n); }
436 [[nodiscard]] constexpr QSpan<T> chopped(size_type n) const { verify(pos: 0, n); return first(size() - n); }
437
438#ifdef __cpp_concepts
439# define QT_ONLY_IF_DYNAMIC_SPAN(DECL) \
440 DECL requires(E == q20::dynamic_extent)
441#else
442# define QT_ONLY_IF_DYNAMIC_SPAN(DECL) \
443 template <size_t M = E, typename = std::enable_if_t<M == q20::dynamic_extent>> DECL
444#endif
445 QT_ONLY_IF_DYNAMIC_SPAN(
446 constexpr void slice(size_type pos)
447 )
448 { *this = sliced(pos); }
449 QT_ONLY_IF_DYNAMIC_SPAN(
450 constexpr void slice(size_type pos, size_type n)
451 )
452 { *this = sliced(pos, n); }
453 QT_ONLY_IF_DYNAMIC_SPAN(
454 constexpr void chop(size_type n)
455 )
456 { *this = chopped(n); }
457#undef QT_ONLY_IF_DYNAMIC_SPAN
458
459private:
460 // [span.objectrep]
461 [[nodiscard]] friend
462 QSpan<const std::byte, E == q20::dynamic_extent ? q20::dynamic_extent : E * sizeof(T)>
463 as_bytes(QSpan s) noexcept
464 {
465 using R = QSpan<const std::byte, E == q20::dynamic_extent ? q20::dynamic_extent : E * sizeof(T)>;
466 return R{reinterpret_cast<const std::byte *>(s.data()), s.size_bytes()};
467 }
468
469 template <typename U>
470 using if_mutable = std::enable_if_t<!std::is_const_v<U>, bool>;
471
472#ifndef Q_QDOC
473 template <typename T2 = T, if_mutable<T2> = true>
474#endif
475 [[nodiscard]] friend
476 QSpan<std::byte, E == q20::dynamic_extent ? q20::dynamic_extent : E * sizeof(T)>
477 as_writable_bytes(QSpan s) noexcept
478 {
479 using R = QSpan<std::byte, E == q20::dynamic_extent ? q20::dynamic_extent : E * sizeof(T)>;
480 return R{reinterpret_cast<std::byte *>(s.data()), s.size_bytes()};
481 }
482}; // class QSpan
483
484// [span.deduct]
485template <class It, class EndOrSize>
486QSpan(It, EndOrSize) -> QSpan<std::remove_reference_t<q20::iter_reference_t<It>>>;
487template <class T, std::size_t N>
488QSpan(T (&)[N]) -> QSpan<T, N>;
489template <class T, std::size_t N>
490QSpan(std::array<T, N> &) -> QSpan<T, N>;
491template <class T, std::size_t N>
492QSpan(const std::array<T, N> &) -> QSpan<const T, N>;
493template <class R>
494QSpan(R&&) -> QSpan<std::remove_reference_t<QSpanPrivate::range_reference_t<R>>>;
495
496QT_END_NAMESPACE
497
498#endif // QSPAN_H
499

source code of qtbase/src/corelib/tools/qspan.h