[libcxx][ranges] Add class ref_view.

[zoecarver]

Rebase.

[zoecarver]

• Fix and add tests.

[zoecarver]

This is also now ready for review.

[• Quuxplusone]

libcxx/include/CMakeLists.txt

45

Please alphabetize.

libcxx/include/__ranges/ref_view.h

14–15

Please alphabetize.

40–43

The sized_range concept should go in the same header that defines ranges::size.

I'm fairly confident that concept borrowed_range doesn't belong in ref_view.h either, but I have no particular suggestion of where it should go. It's also a duplicate of concept __can_borrow from __ranges/access.h; please figure something out.

76

Nit: For readability, I'd like to see the requires-clauses on line 75 and 71 line-broken and indented the same way you've done on line 68.

85

Nit: I'd prefer to see all of these noisy // clang-format {off,on} comments eliminated. (I'm planning to do that once this code stabilizes, anyway. Just complainin'. It'd make all your PRs four lines shorter!)

libcxx/include/ranges

93

Please alphabetize.

libcxx/test/std/ranges/range.adaptors/range.ref.view.pass.cpp

22

In @cjdb's tests he's been using namespace stdr = std::ranges, which has two advantages: shortness and greppability. I think you should make the switch. (My personal preference is namespace rg, but we've already got stdr in the codebase, and anyway it's easy to switch from anything to anything, as long as it's not namespace ranges.)

31–34

friend constexpr, not constexpr friend — but also, why are these friends instead of member begin/end? Making them members would be a lot less typing.

44

But ValidRefView<int[4]> would be OK, right?

83–84

Isn't this the sort of thing that the reversed synthesized candidates are supposed to handle for us?
Orthogonally: hidden friend plz... or actually, wait, what? You're adding comparison operators to cpp20_input_iterator itself? That doesn't seem right. You should just make Cpp20InputRange::end() return a value of type cpp20_input_iterator::sentinel.

106

Throughout: I'd like to see these tests use stdr::ref_view<Range> view = range; instead of direct-curly-brace-initialization.

libcxx/test/support/test_iterators.h

645–649

Defaulted SMFs are constexpr (and noexcept) by default. You don't need this diff.

657–666

This looks good. While you're in the vicinity, I recommend moving cpp20_input_iterator up next to the other test iterators (namely, next to cpp17_input_iterator), and making it look like them:

• remove the C++20 iter_value_t dependency, just use iterator_traits like they do
• remove the [[nodiscard]] cruft
• add the missing base(I) free function
• add the missing deleted operator,
• ifdef it to C++14-and-later since its definition doesn't depend on anything from '17 or '20 (except iter_value_t which we can remove)
• add a nested type struct sentinel {} which is comparable to cpp20_input_iterator<T> (via hidden friends)

Ping me if you want me to just do this.

[zoecarver]

libcxx/include/__ranges/ref_view.h

40–43

I posted this in another thread too, but I did a bad job documenting these concepts. They will both be implemented in their own patches at some point soon (I was hoping for today... but that didn't happen).

I didn't realize they were needed until too late so I just copied them in; they're not part of this review.

libcxx/test/support/test_iterators.h

645–649

Fair enough, will remove. Semi-related: from the synopsis of ref_view:

constexpr ref_view() noexcept = default;

657–666

I'll do this in another PR.

[zoecarver]

Apply Arthur's comments.

[zoecarver]

Rebase.

[zoecarver]

@Quuxplusone friendly ping.

[• Quuxplusone]

libcxx/include/__ranges/ref_view.h

35

__range_

63

Has contiguous_range landed yet? If so, please DO this TODO; otherwise ok, not a blocker.

libcxx/test/std/ranges/range.adaptors/range.ref.view.pass.cpp

66

Pass-by-const-value alert! Remove const.

83–84

This comment relates to the code now on lines 77-78, and it hasn't been addressed yet.

98–105

Naming nit: EmptyIsInvocable, or HasEmpty; but let's avoid any potential confusion with the jargon use of Invocable as a noun. I'd go with HasEmpty, myself; it's shortest.

124

nit: whitespace

[ldionne]

Basically LGTM, requesting changes just so it shows up right in the queue since there are a few pending comments to apply.

libcxx/include/__ranges/ref_view.h

40–41

Those can be made private, and I would perhaps rename it to something like __binds_to_lvalue_ref or something like that.

Do you have a better understanding of what this function is used for than I do? IIUC, it's only used to check that __tp in the constructor below would bind to a lvalue, but not to a rvalue. I'm kind of wondering why the Standard is using this obtuse wording -- there must be a good reason?

44

I guess you want to use __not_same_as here. Not a big fan of that helper concept, but oh well.

[tcanens]

libcxx/include/__ranges/ref_view.h

40–41

This is the LWG2993 dance to avoid having an ICS from rvalues.

[zoecarver]

Okay, I think that's everything.

libcxx/include/__ranges/ref_view.h

63

No, another thing I need to do :(

libcxx/test/std/ranges/range.adaptors/range.ref.view.pass.cpp

66

Removed, but it is at least more OK in this situation where the argument is named and used.

98–105

We're not really asking if the member exists, it always does exist. We're asking whether we can call/invoke it. Also, I don't really see how EmptyIsInvocable is any better than EmptyInvocable. (Not done.)

[zoecarver]

Apply review comments.

[• Quuxplusone]

libcxx/test/std/ranges/range.adaptors/range.ref.view.pass.cpp

98–105

Also, I don't really see how EmptyIsInvocable is any better than EmptyInvocable.

As I said, it's better in that it avoids (confusion with) the jargon use of "invocable" as a noun. I understand what regular_invocable<R> means, but what is EmptyInvocable<R>? What is an "empty invocable"?

[zoecarver]

• Diff off correct commit.
• EmptyInvocable -> EmptyIsInvocable

[ldionne]

LGTM. Please make __binds_to_lvalue_ref private, and we might want to rename it to something like __avoid_ICS_from_rvalue or something like that.

libcxx/include/__ranges/ref_view.h

40–41

Thanks for the context. I must say though, I was unable to construct a case where dropping requires { __binds_to_lvalue_ref(declval<_Tp>()); } would make a difference since we're already checking for convertible_to<_Tp, _Range&>.

In LWG2993, I understand why reference_wrapper used to be broken with the reference_wrapper(T&&) = delete overload, but I fail to see how this applies here. I guess it's not relevant to this review, I'm just curious in case you have time to elaborate.

libcxx/test/std/ranges/range.adaptors/range.ref.view.pass.cpp

2

I just want to say: normally, we'd split this into several files, one per tested thing. But ref_view is almost only its synopsis, so I think this is fine.

[• Quuxplusone]

libcxx/include/__ranges/ref_view.h

40–41

I believe the only case this catches is when T is ambiguously convertible to both R& and R&&:
https://godbolt.org/z/hT4jraEo7

struct Evil {
    operator std::vector<int>& () const;
    operator std::vector<int>&& () const;
};
static_assert(!std::is_convertible_v<Evil, std::reference_wrapper<std::vector<int>>>);
static_assert(!std::is_convertible_v<Evil, std::ranges::ref_view<std::vector<int>>>);

I don't think there was ever a good reason for reference_wrapper to not-bind-to-rvalues, but it's true that reference_wrapper and ref_view are doing the exact same dance here and for exactly isomorphic reasons. (And that's a good reason to keep the naming convention the same, btw. reference_wrapper calls the helper function __fun, and I think we should do exactly the same here.)

[ldionne]

Still LGTM.

libcxx/include/__ranges/ref_view.h

40–41

calls the helper function __fun, and I think we should do exactly the same here

Yeah, I considering that when I wrote my comment and I think the fact that you're suggesting it is enough to sway me. @zoecarver , if you agree, I would go back to the not-very-descriptive-but-consistent-and-close-to-the-standard __fun naming you had initially.

Perhaps you could also add a test like what Arthur suggested?

[tcanens]

libcxx/include/__ranges/ref_view.h

40–41

_Range can be const-qualified, and then _Range& can bind to rvalues, which is what this is trying to disallow.

I'm not sure if this actually needs the 2993 do-not-even-have-an-ICS treatment though (as opposed to = delete;). It's pretty straightforward to come up with toy examples where it makes a difference, but realistic examples are harder to come by.

[ldionne]

Per offline discussion,

• Change back to __fun
• Add a test like Arthur suggested
• Update for P2325

[zoecarver]

Apply Louis' feedback.

[zoecarver]

Remove added empty file.

[zoecarver]

• Fix indenting.
• Remove white space
• Remove no-longer-needed operator==s.

[zoecarver]

Rebase.

[ldionne]

Pending passing CI, of course.

[zoecarver]

Add ref_view.h to the cmake lists after it was removed during rebase (and not caught locally due to caching).

libcxx/include/CMakeLists.txt

set(files
   __mutex_base
   __node_handle
   __nullptr
   __ranges/access.h
   __ranges/concepts.h
   __ranges/data.h
   __ranges/empty.h
   __ranges/enable_borrowed_range.h
-  __ranges/view.h
+  __ranges/ref_view.h
   __ranges/size.h
+  __ranges/view.h
   __ranges/view_interface.h
   __split_buffer
   __std_stream
   __string
   __threading_support
   __tree
   __tuple
   __undef_macros

libcxx/include/__ranges/ref_view.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_REF_VIEW_H
+#define _LIBCPP___RANGES_REF_VIEW_H
+
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__ranges/access.h>
+#include <__ranges/data.h>
+#include <__ranges/view_interface.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 {
+  template<range _Range>
+    requires is_object_v<_Range>
+  class ref_view : public view_interface<ref_view<_Range>> {
+    _Range *__range = nullptr;
+
+public:
+    constexpr ref_view() noexcept = default;
+
+    static void __test(_Range&);
+    static void __test(_Range&&) = delete;
+
+    template<class _Tp>
+      requires (!same_as<_Tp, ref_view>) &&
+        convertible_to<_Tp, _Range&> && requires { __test(declval<_Tp>()); }
+    constexpr ref_view(_Tp&& __t)
+      : __range(_VSTD::addressof(static_cast<_Range&>(_VSTD::forward<_Tp>(__t))))
+    {}
+
+    constexpr _Range& base() const { return *__range; }
+
+    constexpr iterator_t<_Range> begin() const { return ranges::begin(*__range); }
+    constexpr sentinel_t<_Range> end() const { return ranges::end(*__range); }
+
+    constexpr bool empty() const
+      requires requires { ranges::empty(*__range); }
+    { return ranges::empty(*__range); }
+
+    constexpr auto size() const
+      requires sized_range<_Range>
+    { return ranges::size(*__range); }
+
+    // TODO: This needs to use contiguous_range.
+    constexpr auto data() const
+      requires contiguous_iterator<iterator_t<_Range>>
+    { return ranges::data(*__range); }
+  };
+
+  template<class _Range>
+  ref_view(_Range&) -> ref_view<_Range>;
+
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___RANGES_REF_VIEW_H

libcxx/include/__ranges/view_interface.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_VIEW_INTERFACE_H
 #define _LIBCPP___RANGES_VIEW_INTERFACE_H
 
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/concepts.h>
 #include <__ranges/access.h>
 #include <__ranges/empty.h>
+#include <__ranges/view.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/ranges

 */
 
 #include <__config>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/data.h>
 #include <__ranges/empty.h>
 #include <__ranges/enable_borrowed_range.h>
-#include <__ranges/view.h>
+#include <__ranges/ref_view.h>
 #include <__ranges/size.h>
+#include <__ranges/view.h>
 #include <__ranges/view_interface.h>
 #include <compare>          // Required by the standard.
 #include <initializer_list> // Required by the standard.
 #include <iterator>         // Required by the standard.
 #include <type_traits>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/test/std/ranges/range.adaptors/range.ref.view.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
+
+// std::ranges::ref_view
+
+#include <ranges>
+
+#include <cassert>
+#include "test_macros.h"
+#include "test_iterators.h"
+
+int globalBuff[8];
+
+template<class T>
+concept ValidRefView = requires { typename std::ranges::ref_view<T>; };
+
+struct Range {
+  int start = 0;
+  constexpr friend int* begin(Range const& range) { return globalBuff + range.start; }
+  constexpr friend int* end(Range const&) { return globalBuff + 8; }
+  constexpr friend int* begin(Range& range) { return globalBuff + range.start; }
+  constexpr friend int* end(Range&) { return globalBuff + 8; }
+};
+
+struct BeginOnly {
+  friend int* begin(BeginOnly const&);
+  friend int* begin(BeginOnly &);
+};
+
+static_assert( ValidRefView<Range>);
+static_assert(!ValidRefView<BeginOnly>);
+static_assert(!ValidRefView<int (&)[4]>);
+static_assert( ValidRefView<int[4]>);
+
+static_assert(std::derived_from<std::ranges::ref_view<Range>, std::ranges::view_interface<std::ranges::ref_view<Range>>>);
+static_assert(std::semiregular<std::ranges::ref_view<Range>>);
+
+struct RangeConvertible {
+  operator Range& ();
+};
+
+struct RValueRangeConvertible {
+  operator Range&& ();
+};
+
+static_assert( std::is_constructible_v<std::ranges::ref_view<Range>, Range&>);
+static_assert( std::is_constructible_v<std::ranges::ref_view<Range>, RangeConvertible>);
+static_assert(!std::is_constructible_v<std::ranges::ref_view<Range>, RValueRangeConvertible>);
+
+struct ForwardRange {
+  constexpr forward_iterator<int*> begin() const { return forward_iterator<int*>(globalBuff); }
+  constexpr forward_iterator<int*> end() const { return forward_iterator<int*>(globalBuff + 8); }
+};
+
+struct Cpp17InputRange {
+  struct sentinel {
+    friend constexpr bool operator==(sentinel, const cpp17_input_iterator<int*> iter) { return iter.base() == globalBuff + 8; }
+    friend constexpr std::ptrdiff_t operator-(sentinel, cpp17_input_iterator<int*>) { return -8; }
+    friend constexpr std::ptrdiff_t operator-(cpp17_input_iterator<int*>, sentinel) { return 8; }
+  };
+
+  constexpr cpp17_input_iterator<int*> begin() const {
+    return cpp17_input_iterator<int*>(globalBuff);
+  }
+  constexpr sentinel end() const { return {}; }
+};
+
+bool operator==(cpp17_input_iterator<int*> lhs, int* rhs) { return lhs.base() == rhs; }
+bool operator==(int* lhs, cpp17_input_iterator<int*> rhs) { return rhs.base() == lhs; }
+
+struct Cpp20InputRange {
+  struct sentinel {
+    friend constexpr bool operator==(sentinel, const cpp20_input_iterator<int*> &iter) { return iter.base() == globalBuff + 8; }
+    friend constexpr std::ptrdiff_t operator-(sentinel, const cpp20_input_iterator<int*>&) { return -8; }
+    friend constexpr std::ptrdiff_t operator-(const cpp20_input_iterator<int*>&, sentinel) { return 8; }
+  };
+
+  constexpr cpp20_input_iterator<int*> begin() const {
+    return cpp20_input_iterator<int*>(globalBuff);
+  }
+  constexpr sentinel end() const { return {}; }
+};
+
+
+
+template<>
+inline constexpr bool std::ranges::enable_borrowed_range<Cpp20InputRange> = true;
+
+template<class R>
+concept EmptyInvocable = requires (std::ranges::ref_view<R> view) { view.empty(); };
+
+template<class R>
+concept SizeInvocable = requires (std::ranges::ref_view<R> view) { view.size(); };
+
+template<class R>
+concept DataInvocable = requires (std::ranges::ref_view<R> view) { view.data(); };
+
+// Testing ctad.
+static_assert(std::same_as<decltype(std::ranges::ref_view(std::declval<Range&>())),
+              std::ranges::ref_view<Range>>);
+
+constexpr bool test() {
+  {
+    // ref_view::base
+    Range range;
+    std::ranges::ref_view<Range> view{range};
+    assert(view.begin() == globalBuff);
+    view.base() = Range{2};
+    assert(view.begin() == globalBuff + 2);
+  }
+
+  {
+    // ref_view::begin
+    Range range1;
+    std::ranges::ref_view<Range> view1 = range1 ;
+    assert(view1.begin() == globalBuff);
+
+    ForwardRange range2;
+    std::ranges::ref_view<ForwardRange> view2 = range2;
+    assert(view2.begin().base() == globalBuff);
+
+    Cpp17InputRange range3;
+    std::ranges::ref_view<Cpp17InputRange> view3 = range3;
+    assert(view3.begin().base() == globalBuff);
+
+    Cpp20InputRange range4;
+    std::ranges::ref_view<Cpp20InputRange> view4 = range4;
+    assert(view4.begin().base() == globalBuff);
+  }
+
+  {
+    // ref_view::end
+    Range range1;
+    std::ranges::ref_view<Range> view1 = range1;
+    assert(view1.end() == globalBuff + 8);
+
+    ForwardRange range2;
+    std::ranges::ref_view<ForwardRange> view2 = range2;
+    assert(view2.end().base() == globalBuff + 8);
+
+    Cpp17InputRange range3;
+    std::ranges::ref_view<Cpp17InputRange> view3 = range3;
+    assert(view3.end() == cpp17_input_iterator(globalBuff + 8));
+
+    Cpp20InputRange range4;
+    std::ranges::ref_view<Cpp20InputRange> view4 = range4;
+    assert(view4.end() == cpp20_input_iterator(globalBuff + 8));
+  }
+
+  {
+    // ref_view::empty
+    Range range{8};
+    std::ranges::ref_view<Range> view1 = range;
+    assert(view1.empty());
+
+    ForwardRange range2;
+    std::ranges::ref_view<ForwardRange> view2 = range2;
+    assert(!view2.empty());
+
+    static_assert(!EmptyInvocable<Cpp17InputRange>);
+    static_assert(!EmptyInvocable<Cpp20InputRange>);
+  }
+
+  {
+    // ref_view::size
+    Range range1{8};
+    std::ranges::ref_view<Range> view1 = range1;
+    assert(view1.size() == 0);
+
+    Range range2{2};
+    std::ranges::ref_view<Range> view2 = range2;
+    assert(view2.size() == 6);
+
+    static_assert(!SizeInvocable<ForwardRange>);
+  }
+
+  {
+    // ref_view::data
+    Range range1;
+    std::ranges::ref_view<Range> view1 = range1;
+    assert(view1.data() == globalBuff);
+
+    Range range2{2};
+    std::ranges::ref_view<Range> view2 = range2;
+    assert(view2.data() == globalBuff + 2);
+
+    static_assert(!DataInvocable<ForwardRange>);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/support/test_iterators.h

 #ifdef TEST_SUPPORTS_RANGES
 
 template <class I>
 struct cpp20_input_iterator {
   using value_type = std::iter_value_t<I>;
   using difference_type = std::iter_difference_t<I>;
   using iterator_concept = std::input_iterator_tag;
 
   cpp20_input_iterator() = default;
 
   cpp20_input_iterator(cpp20_input_iterator&&) = default;
   cpp20_input_iterator& operator=(cpp20_input_iterator&&) = default;
 
   cpp20_input_iterator(cpp20_input_iterator const&) = delete;
   cpp20_input_iterator& operator=(cpp20_input_iterator const&) = delete;
 
   explicit constexpr cpp20_input_iterator(I base) : base_(std::move(base)) {}
 
   constexpr decltype(auto) operator*() const { return *base_; }
 
-  cpp20_input_iterator& operator++() {
+  constexpr cpp20_input_iterator& operator++() {
     ++base_;
     return *this;
   }
 
-  void operator++(int) { ++base_; }
+  constexpr void operator++(int) { ++base_; }
 
-  [[nodiscard]] I const& base() const& { return base_; }
+  [[nodiscard]] constexpr I const& base() const& { return base_; }
 
-  [[nodiscard]] I base() && { return std::move(base_); }
+  [[nodiscard]] constexpr I base() && { return std::move(base_); }
 
 private:
   I base_ = I();
 };
 
 #endif // TEST_STD_VER > 17 && defined(__cpp_lib_concepts)
 
 #undef DELETE_FUNCTION
 
 #endif // ITERATORS_H