1// Components for manipulating non-owning sequences of objects -*- C++ -*-
2
3// Copyright (C) 2019-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file span
26 *  This is a Standard C++ Library header.
27 */
28
29//
30// P0122 span library
31// Contributed by ThePhD
32//
33
34#ifndef _GLIBCXX_SPAN
35#define _GLIBCXX_SPAN 1
36
37#pragma GCC system_header
38
39#if __cplusplus > 201703L
40
41#include <type_traits>
42#include <array>
43#include <bits/stl_iterator.h>
44#include <bits/range_access.h>
45
46#if __cpp_lib_concepts
47namespace std _GLIBCXX_VISIBILITY(default)
48{
49_GLIBCXX_BEGIN_NAMESPACE_VERSION
50
51#define __cpp_lib_span 202002L
52
53  inline constexpr size_t dynamic_extent = static_cast<size_t>(-1);
54
55  template<typename _Type, size_t _Extent>
56    class span;
57
58  namespace __detail
59  {
60    template<typename _Tp>
61      struct __is_std_span : false_type { };
62
63    template<typename _Tp, size_t _Num>
64      struct __is_std_span<span<_Tp, _Num>> : true_type { };
65
66    template<typename _Tp>
67      struct __is_std_array : false_type { };
68
69    template<typename _Tp, size_t _Num>
70      struct __is_std_array<_GLIBCXX_STD_C::array<_Tp, _Num>> : true_type { };
71
72#ifdef _GLIBCXX_DEBUG
73    template<typename _Tp, size_t _Num>
74      struct __is_std_array<__debug::array<_Tp, _Num>> : true_type { };
75#endif
76
77    template<size_t _Extent>
78      class __extent_storage
79      {
80      public:
81	constexpr
82	__extent_storage(size_t) noexcept
83	{ }
84
85	static constexpr size_t
86	_M_extent() noexcept
87	{ return _Extent; }
88      };
89
90    template<>
91      class __extent_storage<dynamic_extent>
92      {
93      public:
94	constexpr
95	__extent_storage(size_t __extent) noexcept
96	: _M_extent_value(__extent)
97	{ }
98
99	constexpr size_t
100	_M_extent() const noexcept
101	{ return this->_M_extent_value; }
102
103      private:
104	size_t _M_extent_value;
105      };
106  } // namespace __detail
107
108  template<typename _Type, size_t _Extent = dynamic_extent>
109    class span
110    {
111      template<size_t _Offset, size_t _Count>
112	static constexpr size_t
113	_S_subspan_extent()
114	{
115	  if constexpr (_Count != dynamic_extent)
116	    return _Count;
117	  else if constexpr (extent != dynamic_extent)
118	    return _Extent - _Offset;
119	  else
120	    return dynamic_extent;
121	}
122
123      // _GLIBCXX_RESOLVE_LIB_DEFECTS
124      // 3255. span's array constructor is too strict
125      template<typename _Tp, size_t _ArrayExtent>
126	requires (_Extent == dynamic_extent || _ArrayExtent == _Extent)
127	using __is_compatible_array = __is_array_convertible<_Type, _Tp>;
128
129      template<typename _Ref>
130	using __is_compatible_ref
131	  = __is_array_convertible<_Type, remove_reference_t<_Ref>>;
132
133    public:
134      // member types
135      using element_type           = _Type;
136      using value_type             = remove_cv_t<_Type>;
137      using size_type              = size_t;
138      using difference_type        = ptrdiff_t;
139      using pointer                = _Type*;
140      using const_pointer          = const _Type*;
141      using reference              = element_type&;
142      using const_reference        = const element_type&;
143      using iterator = __gnu_cxx::__normal_iterator<pointer, span>;
144      using reverse_iterator       = std::reverse_iterator<iterator>;
145
146      // member constants
147      static constexpr size_t extent = _Extent;
148
149      // constructors, copy and assignment
150
151      constexpr
152      span() noexcept
153      requires ((_Extent + 1u) <= 1u)
154      : _M_extent(0), _M_ptr(nullptr)
155      { }
156
157      template<contiguous_iterator _It>
158	requires __is_compatible_ref<iter_reference_t<_It>>::value
159	constexpr explicit(extent != dynamic_extent)
160	span(_It __first, size_type __count)
161	noexcept
162	: _M_extent(__count), _M_ptr(std::to_address(__first))
163	{
164	  if constexpr (_Extent != dynamic_extent)
165	    {
166	      __glibcxx_assert(__count == _Extent);
167	    }
168	}
169
170      template<contiguous_iterator _It, sized_sentinel_for<_It> _End>
171	requires __is_compatible_ref<iter_reference_t<_It>>::value
172	  && (!is_convertible_v<_End, size_type>)
173	constexpr explicit(extent != dynamic_extent)
174	span(_It __first, _End __last)
175	noexcept(noexcept(__last - __first))
176	: _M_extent(static_cast<size_type>(__last - __first)),
177	  _M_ptr(std::to_address(__first))
178	{
179	  if constexpr (_Extent != dynamic_extent)
180	    {
181	      __glibcxx_assert((__last - __first) == _Extent);
182	    }
183	}
184
185      template<size_t _ArrayExtent>
186	requires (_Extent == dynamic_extent || _ArrayExtent == _Extent)
187	constexpr
188	span(type_identity_t<element_type> (&__arr)[_ArrayExtent]) noexcept
189	: span(static_cast<pointer>(__arr), _ArrayExtent)
190	{ }
191
192      template<typename _Tp, size_t _ArrayExtent>
193	requires __is_compatible_array<_Tp, _ArrayExtent>::value
194	constexpr
195	span(array<_Tp, _ArrayExtent>& __arr) noexcept
196	: span(static_cast<pointer>(__arr.data()), _ArrayExtent)
197	{ }
198
199      template<typename _Tp, size_t _ArrayExtent>
200	requires __is_compatible_array<const _Tp, _ArrayExtent>::value
201	constexpr
202	span(const array<_Tp, _ArrayExtent>& __arr) noexcept
203	: span(static_cast<pointer>(__arr.data()), _ArrayExtent)
204	{ }
205
206      template<typename _Range>
207	requires ranges::contiguous_range<_Range> && ranges::sized_range<_Range>
208	  && (ranges::borrowed_range<_Range> || is_const_v<element_type>)
209	  && (!__detail::__is_std_span<remove_cvref_t<_Range>>::value)
210	  && (!__detail::__is_std_array<remove_cvref_t<_Range>>::value)
211	  && (!is_array_v<remove_cvref_t<_Range>>)
212	  && __is_compatible_ref<ranges::range_reference_t<_Range>>::value
213	constexpr explicit(extent != dynamic_extent)
214	span(_Range&& __range)
215	noexcept(noexcept(ranges::data(__range))
216		  && noexcept(ranges::size(__range)))
217	: span(ranges::data(__range), ranges::size(__range))
218	{
219	  if constexpr (extent != dynamic_extent)
220	    {
221	      __glibcxx_assert(ranges::size(__range) == extent);
222	    }
223	}
224
225      constexpr
226      span(const span&) noexcept = default;
227
228      template<typename _OType, size_t _OExtent>
229	requires (_Extent == dynamic_extent || _OExtent == dynamic_extent
230		  || _Extent == _OExtent)
231	  && (__is_array_convertible<_Type, _OType>::value)
232	constexpr
233	explicit(extent != dynamic_extent && _OExtent == dynamic_extent)
234	span(const span<_OType, _OExtent>& __s) noexcept
235	: _M_extent(__s.size()), _M_ptr(__s.data())
236	{
237	  if constexpr (extent != dynamic_extent)
238	    {
239	      __glibcxx_assert(__s.size() == extent);
240	    }
241	}
242
243      ~span() noexcept = default;
244
245      constexpr span&
246      operator=(const span&) noexcept = default;
247
248      // observers
249
250      constexpr size_type
251      size() const noexcept
252      { return this->_M_extent._M_extent(); }
253
254      constexpr size_type
255      size_bytes() const noexcept
256      { return this->_M_extent._M_extent() * sizeof(element_type); }
257
258      [[nodiscard]] constexpr bool
259      empty() const noexcept
260      { return size() == 0; }
261
262      // element access
263
264      constexpr reference
265      front() const noexcept
266      {
267	__glibcxx_assert(!empty());
268	return *this->_M_ptr;
269      }
270
271      constexpr reference
272      back() const noexcept
273      {
274	__glibcxx_assert(!empty());
275	return *(this->_M_ptr + (size() - 1));
276      }
277
278      constexpr reference
279      operator[](size_type __idx) const noexcept
280      {
281	__glibcxx_assert(__idx < size());
282	return *(this->_M_ptr + __idx);
283      }
284
285      constexpr pointer
286      data() const noexcept
287      { return this->_M_ptr; }
288
289      // iterator support
290
291      constexpr iterator
292      begin() const noexcept
293      { return iterator(this->_M_ptr); }
294
295      constexpr iterator
296      end() const noexcept
297      { return iterator(this->_M_ptr + this->size()); }
298
299      constexpr reverse_iterator
300      rbegin() const noexcept
301      { return reverse_iterator(this->end()); }
302
303      constexpr reverse_iterator
304      rend() const noexcept
305      { return reverse_iterator(this->begin()); }
306
307      // subviews
308
309      template<size_t _Count>
310	constexpr span<element_type, _Count>
311	first() const noexcept
312	{
313	  if constexpr (_Extent == dynamic_extent)
314	    __glibcxx_assert(_Count <= size());
315	  else
316	    static_assert(_Count <= extent);
317	  using _Sp = span<element_type, _Count>;
318	  return _Sp{ this->data(), _Count };
319	}
320
321      constexpr span<element_type, dynamic_extent>
322      first(size_type __count) const noexcept
323      {
324	__glibcxx_assert(__count <= size());
325	return { this->data(), __count };
326      }
327
328      template<size_t _Count>
329	constexpr span<element_type, _Count>
330	last() const noexcept
331	{
332	  if constexpr (_Extent == dynamic_extent)
333	    __glibcxx_assert(_Count <= size());
334	  else
335	    static_assert(_Count <= extent);
336	  using _Sp = span<element_type, _Count>;
337	  return _Sp{ this->data() + (this->size() - _Count), _Count };
338	}
339
340      constexpr span<element_type, dynamic_extent>
341      last(size_type __count) const noexcept
342      {
343	__glibcxx_assert(__count <= size());
344	return { this->data() + (this->size() - __count), __count };
345      }
346
347      template<size_t _Offset, size_t _Count = dynamic_extent>
348	constexpr auto
349	subspan() const noexcept
350	-> span<element_type, _S_subspan_extent<_Offset, _Count>()>
351	{
352	  if constexpr (_Extent == dynamic_extent)
353	    {
354	      __glibcxx_assert(_Offset <= size());
355	    }
356	  else
357	    static_assert(_Offset <= extent);
358
359	  using _Sp = span<element_type, _S_subspan_extent<_Offset, _Count>()>;
360
361	  if constexpr (_Count == dynamic_extent)
362	    return _Sp{ this->data() + _Offset, this->size() - _Offset };
363	  else
364	    {
365	      if constexpr (_Extent == dynamic_extent)
366		{
367		  __glibcxx_assert(_Count <= size());
368		  __glibcxx_assert(_Count <= (size() - _Offset));
369		}
370	      else
371		{
372		  static_assert(_Count <= extent);
373		  static_assert(_Count <= (extent - _Offset));
374		}
375	      return _Sp{ this->data() + _Offset, _Count };
376	    }
377	}
378
379      constexpr span<element_type, dynamic_extent>
380      subspan(size_type __offset, size_type __count = dynamic_extent) const
381      noexcept
382      {
383	__glibcxx_assert(__offset <= size());
384	if (__count == dynamic_extent)
385	  __count = this->size() - __offset;
386	else
387	  {
388	    __glibcxx_assert(__count <= size());
389	    __glibcxx_assert(__offset + __count <= size());
390	  }
391	return {this->data() + __offset, __count};
392      }
393
394    private:
395      [[no_unique_address]] __detail::__extent_storage<extent> _M_extent;
396      pointer _M_ptr;
397    };
398
399  // deduction guides
400
401  template<typename _Type, size_t _ArrayExtent>
402    span(_Type(&)[_ArrayExtent]) -> span<_Type, _ArrayExtent>;
403
404  template<typename _Type, size_t _ArrayExtent>
405    span(array<_Type, _ArrayExtent>&) -> span<_Type, _ArrayExtent>;
406
407  template<typename _Type, size_t _ArrayExtent>
408    span(const array<_Type, _ArrayExtent>&)
409      -> span<const _Type, _ArrayExtent>;
410
411  template<contiguous_iterator _Iter, typename _End>
412    span(_Iter, _End)
413      -> span<remove_reference_t<iter_reference_t<_Iter>>>;
414
415  template<typename _Range>
416    span(_Range &&)
417      -> span<remove_reference_t<ranges::range_reference_t<_Range&>>>;
418
419  template<typename _Type, size_t _Extent>
420    inline
421    span<const byte, _Extent == dynamic_extent
422	? dynamic_extent : _Extent * sizeof(_Type)>
423    as_bytes(span<_Type, _Extent> __sp) noexcept
424    {
425      auto data = reinterpret_cast<const byte*>(__sp.data());
426      auto size = __sp.size_bytes();
427      constexpr auto extent = _Extent == dynamic_extent
428	? dynamic_extent : _Extent * sizeof(_Type);
429      return span<const byte, extent>{data, size};
430    }
431
432  template<typename _Type, size_t _Extent>
433    requires (!is_const_v<_Type>)
434    inline
435    span<byte, _Extent == dynamic_extent
436       ? dynamic_extent : _Extent * sizeof(_Type)>
437    as_writable_bytes(span<_Type, _Extent> __sp) noexcept
438    {
439      auto data = reinterpret_cast<byte*>(__sp.data());
440      auto size = __sp.size_bytes();
441      constexpr auto extent = _Extent == dynamic_extent
442	? dynamic_extent : _Extent * sizeof(_Type);
443      return span<byte, extent>{data, size};
444    }
445
446  namespace ranges
447  {
448    // Opt-in to borrowed_range concept
449    template<typename _ElementType, size_t _Extent>
450      inline constexpr bool
451	enable_borrowed_range<span<_ElementType, _Extent>> = true;
452
453    // Opt-in to view concept
454    template<typename _ElementType, size_t _Extent>
455      inline constexpr bool
456	enable_view<span<_ElementType, _Extent>>
457	  = _Extent == 0 || _Extent == dynamic_extent;
458  }
459_GLIBCXX_END_NAMESPACE_VERSION
460} // namespace std
461#endif // concepts
462#endif // C++20
463#endif // _GLIBCXX_SPAN
464