[libcxx][ranges] implements dangling, borrowed_iterator_t, borrowed_subrange_t

[cjdb]

Summary

• Implements part of P0896 'The One Ranges Proposal'
• Implements http://wg21.link/range.dangling

[cjdb]

removes stray include

[tcanens]

libcxx/include/__ranges/borrowed_subrange_t.h

37–38

I'm under the impression that libc++ has a "better conditional_t" somewhere that doesn't require one class template instantiation per type?

[ldionne]

libcxx/include/__ranges/borrowed_subrange_t.h

37–38

You can either use _If or just plain conditional_t. _If creates fewer instantiations.

[• Quuxplusone]

LGTM mod comments!

libcxx/include/__ranges/borrowed_subrange_t.h

37–38

Yes, and I think it's safe to use here because _Rp is already constrained to be a range, so subrange<iterator_t<_Rp>> is guaranteed well-formed. (If _Rp were allowed to be a non-range, then we couldn't use this trick: godbolt)

template<range _Rp>
using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>;

libcxx/include/__ranges/dangling.h

34–41

template<range _Rp>
using borrowed_subrange_t = _If<borrowed_range<_Rp>, iterator_t<_Rp>, dangling>;

libcxx/include/__ranges/subrange.h

21

Yikes. I guess I need to audit graph_header_deps.py; it should have caught even this trivially circular inclusion.

libcxx/include/ranges

133

a-z plz (and also in the modulemap and CMakeLists)

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_iterator.compile.pass.cpp

30

As long as you're using same_as instead of is_same_v, you might as well also use concept instead of constexpr bool — it's shorter (and this line coincidentally is 2 characters too long :)).

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_subrange.compile.pass.cpp

23

IMO it's worth testing std::ranges::borrowed_subrange_t<std::string&> and std::ranges::borrowed_subrange_t<std::string&&>.

Using string and string_view as your archetypes for "borrowed" and "non-borrowed" seems like a good idea to me. Vice versa, assuming that we've already got a good test verifying that std::ranges::borrowed_range<std::span<T>> in the test suite for span, I think it'd be fine to eliminate all the lines here involving <vector> and <span>: they're too redundantly similar to the string/string_view lines.

libcxx/test/std/ranges/range.utility/range.dangling/dangling.compile.pass.cpp

26–27

I'd lose lines 25-27 (as redundant) but add

static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, int, int, int>);
static_assert(std::is_trivial_v<std::ranges::dangling>);

assuming that those properties are in fact intentional and/or mandated.

[cjdb]

• replaces specialisations with _If
• adds tests
• moves borrowed_subrange_t into __range/subrange.h (ATTN @ldionne)

[cjdb]

fixes a few things

[zoecarver]

A few nits. But LGTM.

libcxx/include/ranges

98

Thanks.

101

Is this implemented? It doesn't look like it, yet.

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_iterator.compile.pass.cpp

33

While you're at it (changing to a concept) can you rename this to something more descriptive? Maybe something like "hasIterator" or "validForBorrowedIter" or something that indicates you're checking the requirements (that T is a range).

[cjdb]

libcxx/include/__ranges/borrowed_subrange_t.h

37–38

Fewer instantiations is always good.

libcxx/include/ranges

101

This was the first thing implemented in <ranges> (see line 136).

133

Done, done, and done!

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_iterator.compile.pass.cpp

30

has_X is a trait, not a concept :)

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_subrange.compile.pass.cpp

23

IMO it's worth testing std::ranges::borrowed_subrange_t<std::string&> and std::ranges::borrowed_subrange_t<std::string&&>.

Yes, good idea (also applied to borrowed_iterator).

Using string and string_view as your archetypes for "borrowed" and "non-borrowed" seems like a good idea to me. Vice versa, assuming that we've already got a good test verifying that std::ranges::borrowed_range<std::span<T>> in the test suite for span, I think it'd be fine to eliminate all the lines here involving <vector> and <span>: they're too redundantly similar to the string/string_view lines.

I'd still prefer to keep the other types to make sure borrowed_X isn't hard-coded to a single type.

libcxx/test/std/ranges/range.utility/range.dangling/dangling.compile.pass.cpp

26–27

I'd lose lines 25-27 (as redundant) but add

static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, int, int, int>);
static_assert(std::is_trivial_v<std::ranges::dangling>);

Keeping lines 25-7 (making sure this works with user-defined types is important), and added both your lines.

assuming that those properties are in fact intentional and/or mandated.

🤷 The constructor is variadic, so it's probably intentional and mandated?

[cjdb]

removes is_trivial test, since clang and gcc don't agree

[ldionne]

libcxx/include/__ranges/dangling.h

33

_LIBCPP_HIDE_FROM_ABI

libcxx/include/__ranges/subrange.h

21

You need <type_traits> for _If (here and in dangling.h).

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_iterator.compile.pass.cpp

33

Agreed, I would just use

template <class T>
concept has_borrowed_iterator = requires {
  typename std::ranges::borrowed_iterator_t<T>;
};

That's closest to what we do in other tests, no?

libcxx/test/std/ranges/range.utility/range.dangling/dangling.compile.pass.cpp

26–27

Instead, why not:

template<int> struct S { };
static_assert(std::is_nothrow_constructible_v<std::ranges::dangling>);
static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, S<0>>);
static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, S<0>, S<1>>);
static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, S<0>, S<1>, S<2>>);

Feel free to keep (or not) the int, int* and int (*)() ones, I'm not sure how much coverage they add. IMO using S<n> conveys more clearly that we're making sure that dangling can be constructed from something arbitrary.

[cjdb]

applies requested changes

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_iterator.compile.pass.cpp

33

Renamed, but keeping as constexpr bool (this is not a concept).

[ldionne]

@DavidSpickett I see the Linaro bots have started failing when building libunwind. I looked into it a little bit, but I didn't see any recent changes in libunwind. Did you make changes to your bots?

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_iterator.compile.pass.cpp

39–43

I think this belongs to dangling.compile.pass.cpp.

libcxx/test/std/ranges/range.utility/range.dangling/dangling.compile.pass.cpp

2

This should be a .pass.cpp test, and we should test that we can actually run (not only compile) code that calls the variadic constructor (and the default constructor), since it's defined with an empty body in the Standard. As it stands, I think our tests would pass if we had not defined the constructor at all and only declared it, but we would be non-conforming.

[cjdb]

rebases to use the new shiny CI

[ldionne]

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_iterator.compile.pass.cpp

39–43

I think this belongs to dangling.compile.pass.cpp.

This is where this comment belongs (for some reason it doesn't show up).

[cjdb]

applies @ldionne's feedback (in some fashion)

[cjdb]

libcxx/test/std/ranges/range.utility/range.dangling/dangling.compile.pass.cpp

2

Does it really need to be a .pass.cpp? Surely a bunch of constexpr objects should do the trick, no?

[cjdb]

fixes mistake

[ldionne]

libcxx/test/std/ranges/range.utility/range.dangling/dangling.compile.pass.cpp

2

We really want to test exactly what the users are going to do, and that includes "running" that empty constructor at runtime. Even though in practice we do know it will be optimized out and all, it's still what we need to check.

[cjdb]

Applies @ldionne's feedback about adding a run-time test.

Thought I already did this, but apparently not. Explains why there hasn't been any further progress on this.

[cjdb]

rebasing to activate CI

libcxx/docs/OneRangesProposalStatus.csv

 `[view.interface] <http://wg21.link/view.interface>`_,"`ranges::view_interface <https://llvm.org/D101737>`_","| [ranges.range]
 | [range.view]
 | [range.iterator.op.prev]
 | [range.refinements]",Zoe Carver,In progress
 `[range.subrange] <http://wg21.link/range.subrange>`_,`ranges::subrange <https://llvm.org/D102006>`_,[view.interface],Zoe Carver,In progress
 `[range.dangling] <http://wg21.link/range.dangling>`_,"| ranges::dangling
 | ranges::borrowed_iterator_t
 | ranges::borrowed_subrange_t","| [range.range]
-| [range.subrange]",Unassigned,Not started
+| [range.subrange]",Christopher Di Bella,✅
 `[range.all] <http://wg21.link/range.all>`_,`view::all <https://llvm.org/D102028>`_,"[range.subrange], [range.view.ref]",Zoe Carver,In progress
 `[range.view.ref] <http://wg21.link/range.view>`_,`ref-view <https://llvm.org/D102020>`_,[view.interface],Zoe Carver,In progress
 `[range.filter] <http://wg21.link/range.filter>`_,filter_view,[range.all],Louis Dionne,Not started
 `[range.transform] <http://wg21.link/range.transform>`_,`transform_view <https://llvm.org/D103056>`_,[range.all],Zoe Carver,In progress
 `[range.iota] <http://wg21.link/range.iota>`_,iota_view,[range.all],Louis Dionne,Not started
 `[range.take] <http://wg21.link/range.take>`_,take_view,[range.all],Zoe Carver,Not started
 `[range.join] <http://wg21.link/range.join>`_,join_view,[range.all],Christopher Di Bella,Not started
 `[range.empty] <http://wg21.link/range.empty>`_,`empty_view <https://reviews.llvm.org/D103208>`_,[view.interface],Zoe Carver,✅
 `[range.single] <http://wg21.link/range.single>`_,single_view,[view.interface],Unassigned,Not started
 `[range.split] <http://wg21.link/range.split>`_,split_view,[range.all],Unassigned,Not started
 `[range.counted] <http://wg21.link/range.counted>`_,view::counted,[range.subrange],Unassigned,Not started
 `[range.common] <http://wg21.link/range.common>`_,common_view,[range.all],Zoe Carver,Not started
 `[range.reverse] <http://wg21.link/range.reverse>`_,reverse_view,[range.all],Unassigned,Not started

libcxx/include/CMakeLists.txt

set(files
   __memory/uninitialized_algorithms.h
   __memory/unique_ptr.h
   __mutex_base
   __node_handle
   __nullptr
   __random/uniform_int_distribution.h
   __ranges/access.h
   __ranges/all.h
+  __ranges/borrowed_subrange_t.h
   __ranges/concepts.h
   __ranges/data.h
+  __ranges/dangling.h
   __ranges/drop_view.h
   __ranges/empty.h
   __ranges/empty_view.h
   __ranges/enable_borrowed_range.h
   __ranges/enable_view.h
   __ranges/view_interface.h
   __ranges/ref_view.h
   __ranges/size.h

libcxx/include/__ranges/borrowed_subrange_t.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___RANGES_BORROWED_SUBRANGE_T_H
+#define _LIBCPP___RANGES_BORROWED_SUBRANGE_T_H
+
+#include <__config>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__ranges/subrange.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  template<class>
+  struct __borrowed_subrange { using type = dangling; };
+
+  template<borrowed_range _Rp>
+  struct __borrowed_subrange<_Rp> { using type = subrange<iterator_t<_Rp>>; };
+
+  template<range _Rp>
+  using borrowed_subrange_t = typename __borrowed_subrange<_Rp>::type;
+} // namespace ranges
+
+#endif // !_LIBCPP_HAS_NO_RANGES
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___RANGES_BORROWED_SUBRANGE_T_H

libcxx/include/__ranges/dangling.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___RANGES_DANGLING_H
+#define _LIBCPP___RANGES_DANGLING_H
+
+#include <__config>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  struct dangling {
+    dangling() = default;
+    constexpr dangling(auto&&...) noexcept {}
+  };
+
+  template<class>
+  struct __borrowed_iterator { using type = dangling; };
+
+  template<borrowed_range _Rp>
+  struct __borrowed_iterator<_Rp> { using type = iterator_t<_Rp>; };
+
+  template<range _Rp>
+  using borrowed_iterator_t = typename __borrowed_iterator<_Rp>::type;
+} // namespace ranges
+
+#endif // !_LIBCPP_HAS_NO_RANGES
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___RANGES_DANGLING_H

libcxx/include/__ranges/subrange.h

 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/advance.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/size.h>
-#include <__ranges/subrange.h>
 #include <__ranges/view_interface.h>
 #include <concepts>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS

libcxx/include/module.modulemap

module ranges {
     export compare
     export initializer_list
     export iterator
     export *
 
     module __ranges {
       module access                 { header "__ranges/access.h"                }
       module all                    { header "__ranges/all.h"                   }
+      module borrowed_subrange_t    { header "__ranges/borrowed_subrange_t.h"   }
       module concepts               { header "__ranges/concepts.h"              }
       module data                   { header "__ranges/data.h"                  }
+      module dangling               { header "__ranges/dangling.h"              }
       module empty                  { header "__ranges/empty.h"                 }
       module empty_view             { header "__ranges/empty_view.h"            }
       module enable_borrowed_range  { header "__ranges/enable_borrowed_range.h" }
       module enable_view            { header "__ranges/enable_view.h"           }
       module ref_view               { header "__ranges/ref_view.h"              }
       module size                   { header "__ranges/size.h"                  }
       module subrange               { header "__ranges/subrange.h"              }
       module view_interface         { header "__ranges/view_interface.h"        }

libcxx/include/ranges

namespace std::ranges {
   template <class _Tp>
     concept common_range = see below;
 
   // [view.interface], class template view_interface
   template<class D>
     requires is_class_v<D> && same_as<D, remove_cv_t<D>>
   class view_interface;
 
+  // [range.subrange], sub-ranges
+  enum class subrange_kind : bool { unsized, sized };
+
+  template<input_or_output_iterator I, sentinel_for<I> S = I, subrange_kind K = see below>
+    requires (K == subrange_kind::sized || !sized_sentinel_for<S, I>)
+  class subrange;
+
+  template<class I, class S, subrange_kind K>
+    inline constexpr bool enable_borrowed_range<subrange<I, S, K>> = true;
+
+  // [range.dangling], dangling iterator handling
+  struct dangling;
+
+  template<range R>
+    using borrowed_iterator_t = see below;
+
+  template<range R>
+    using borrowed_subrange_t = see below;
+
   // [range.empty], empty view
   template<class T>
     requires is_object_v<T>
   class empty_view;
 
   // [range.drop], drop view
   template<view V>
     class drop_view;
 
   template<class T>
     inline constexpr bool enable_borrowed_range<drop_view<T>> = enable_borrowed_range<T>;
 }
 
 */
 
 #include <__config>
 #include <__ranges/access.h>
 #include <__ranges/all.h>
+#include <__ranges/borrowed_subrange_t.h>
 #include <__ranges/concepts.h>
 #include <__ranges/data.h>
+#include <__ranges/dangling.h>
 #include <__ranges/drop_view.h>
 #include <__ranges/empty.h>
 #include <__ranges/empty_view.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/enable_view.h>
 #include <__ranges/ref_view.h>
 #include <__ranges/size.h>
 #include <__ranges/subrange.h>

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_iterator.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// class std::ranges::borrowed_iterator_t;
+
+#include <ranges>
+
+#include <concepts>
+#include <span>
+#include <string>
+#include <string_view>
+#include <vector>
+
+static_assert(std::same_as<std::ranges::borrowed_iterator_t<std::string>, std::ranges::dangling>);
+static_assert(std::same_as<std::ranges::borrowed_iterator_t<std::vector<int>>, std::ranges::dangling>);
+
+static_assert(std::same_as<std::ranges::borrowed_iterator_t<std::span<int>>, std::span<int>::iterator>);
+static_assert(std::same_as<std::ranges::borrowed_iterator_t<std::string_view>, std::string_view::iterator>);
+
+template<class T>
+constexpr bool has_type = requires { typename std::ranges::borrowed_iterator_t<T>; };
+
+static_assert(!has_type<int>);
+
+struct S {};
+static_assert(!has_type<S>);

libcxx/test/std/ranges/range.utility/range.dangling/borrowed_subrange.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// class std::ranges::borrowed_subrange_t;
+
+#include <ranges>
+
+#include <concepts>
+#include <span>
+#include <string>
+#include <string_view>
+#include <vector>
+
+static_assert(std::same_as<std::ranges::borrowed_subrange_t<std::string>, std::ranges::dangling>);
+static_assert(std::same_as<std::ranges::borrowed_subrange_t<std::vector<int>>, std::ranges::dangling>);
+
+static_assert(std::same_as<std::ranges::borrowed_subrange_t<std::span<int>>,
+                           std::ranges::subrange<std::span<int>::iterator>>);
+
+static_assert(std::same_as<std::ranges::borrowed_subrange_t<std::string_view>,
+                           std::ranges::subrange<std::string_view::iterator>>);
+
+template<class T>
+constexpr bool has_type = requires { typename std::ranges::borrowed_subrange_t<T>; };
+
+static_assert(!has_type<int>);
+
+struct S {};
+static_assert(!has_type<S>);

libcxx/test/std/ranges/range.utility/range.dangling/dangling.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// class std::ranges::dangling;
+
+#include <ranges>
+
+#include <concepts>
+#include <type_traits>
+
+static_assert(std::default_initializable<std::ranges::dangling>);
+
+static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, int>);
+static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, int*>);
+static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, int(*)()>);
+
+struct S {};
+static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, S>);
+
+static_assert(std::is_empty_v<std::ranges::dangling>);