[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 ↗

(On Diff #355600)

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 ↗

(On Diff #355600)

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 ↗

(On Diff #355600)

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

35–42

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

libcxx/include/__ranges/subrange.h

20–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

31

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

24

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

27–28

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 ↗

(On Diff #355600)

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

31

has_X is a trait, not a concept :)

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

24

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

27–28

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

22

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

27–28

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

38–42

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

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

1

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

1

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

1

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/Status/RangesPaper.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
   __mutex_base
   __node_handle
   __nullptr
   __random/uniform_int_distribution.h
   __ranges/access.h
   __ranges/all.h
   __ranges/concepts.h
   __ranges/copyable_box.h
+  __ranges/dangling.h
   __ranges/data.h
   __ranges/drop_view.h
   __ranges/empty_view.h
   __ranges/empty.h
   __ranges/enable_borrowed_range.h
   __ranges/enable_view.h
   __ranges/ref_view.h
   __ranges/size.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>
+#include <type_traits>
+
+#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;
+  _LIBCPP_HIDE_FROM_ABI constexpr dangling(auto&&...) noexcept {}
+};
+
+template <range _Rp>
+using borrowed_iterator_t = _If<borrowed_range<_Rp>, iterator_t<_Rp>, dangling>;
+
+// borrowed_subrange_t defined in <__ranges/subrange.h>
+} // 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 <__config>
 #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/dangling.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/size.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
namespace ranges {
   template<size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
     requires (_Index < 2)
   constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) {
     if constexpr (_Index == 0)
       return __subrange.begin();
     else
       return __subrange.end();
   }
+
+  template<range _Rp>
+  using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp> >, dangling>;
 } // namespace ranges
 
 using ranges::get;
 
 // clang-format off
 
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___RANGES_SUBRANGE_H

libcxx/include/module.modulemap

module ranges {
     export iterator
     export *
 
     module __ranges {
       module access                 { header "__ranges/access.h"                }
       module all                    { header "__ranges/all.h"                   }
       module concepts               { header "__ranges/concepts.h"              }
       module copyable_box           { header "__ranges/copyable_box.h"          }
+      module dangling               { header "__ranges/dangling.h"              }
       module data                   { header "__ranges/data.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"              }

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/concepts.h>
+#include <__ranges/dangling.h>
 #include <__ranges/data.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>
 #include <__ranges/view_interface.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::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::string&>, std::string::iterator>);
+static_assert(std::same_as<std::ranges::borrowed_iterator_t<std::string_view>, std::string_view::iterator>);
+static_assert(std::same_as<std::ranges::borrowed_iterator_t<std::span<int> >, std::span<int>::iterator>);
+
+template <class T>
+constexpr bool has_borrowed_iterator = requires {
+  typename std::ranges::borrowed_iterator_t<T>;
+};
+
+static_assert(!has_borrowed_iterator<int>);
+
+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>>);

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::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::string&>, std::ranges::subrange<std::string::iterator> >);
+
+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 (*)()>);
+static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, int, int, int>);
+
+struct S {};
+static_assert(std::is_nothrow_constructible_v<std::ranges::dangling, S>);
+
+static_assert(std::is_empty_v<std::ranges::dangling>);