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

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