[libcxx][views] Add drop_view.

[zoecarver]

Summary

The first view in the libc++ ranges library 🚀

[zoecarver]

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

178 ↗

(On Diff #343544)

I just had a thought: I should add some tests where views::all comes into play (so make sure we use the deduction guides to automatically create drop_view<subrange> and drop_view<ref_view>). I'll do this tomorrow morning.

[cjdb]

Overall, this is great! Sadly, I can't LGTM till caching is implemented, but I think we'll be good to land this sometime next week :-)

libcxx/include/__iterator/primitives.h

98 ↗

(On Diff #343544)

If this is temporary, carry on. If there's a genuine concern, please highlight it in D101922.

libcxx/include/__ranges/drop_view.h

34–38

I'd very much appreciate a few simple libcxx tests for this concept. It's so important that I want so much as a light breeze nearby to cause a build failure.

42

Nit 1: please suffix members with an underscore.
Nit 2: please put private stuff at the bottom unless it needs to be seen.

59–61

Let's hold off on merging this with main till ranges::next is available (I'll throw up a patch as soon as D101922 is approved).

You also need to cache the result for forward ranges (see [range.semi.wrap]). This is observable behaviour, so please add a test to ensure the caching happens.

66–68

I'd suggest wrapping this into a static __begin_impl so there's a shared impl. Same with size, but not end.

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

23 ↗

(On Diff #343544)

Nit: I'd prefer if this were std::array<int, 8>.

27–66 ↗

(On Diff #343544)

You have four views that satisfy range<T const>, if I'm not mistaken. Please ensure there's at least one non-const input view, and one non-const forward view too. Also, please check out test/support/test_range.h to see if some of these are already available (I don't think they are), and add some utilities there, as they'll be necessary in other range tests too.

61–63 ↗

(On Diff #343544)

const-qualified access member functions should probably return const-iterators. Similarly elsewhere.

68 ↗

(On Diff #343544)

cpp17_ or cpp20_input_iterator

77–79 ↗

(On Diff #343544)

Please also expand to check const qualification. This is very important!

80–84 ↗

(On Diff #343544)

These should possibly go into their own ctad.compile.pass.cpp.

110–135 ↗

(On Diff #343544)

I'd prefer it if these were in functions such as check_begin(). The more intrinsic documentation we have, the less likely comments can go out of date.

116–117 ↗

(On Diff #343544)

Can we test with some odd numbers and even non-powers of 2 too please?

154–171 ↗

(On Diff #343544)

We should have const-qualified tests for all these.

[zoecarver]

• Implement caching.

[zoecarver]

• Uncomment the static_assert.

[cjdb]

libcxx/include/__ranges/drop_view.h

45

Caching should only be available for forward ranges (it's a logic error to cache for input ranges, and also not to spec). Also, please make this [[no_unique_address]].

[zoecarver]

• Move size into a helper function.

[ldionne]

Overall LGTM, left some comments and we just spoke offline too, so you know what else I want. Thanks a lot for working on this, I think this is a huge milestone!!

libcxx/include/__ranges/drop_view.h

36

This should eventually be lifted to a common header because I believe many views are going to depend on this exposition only concept.

48

The combination of = default on this constructor and default member initializers is IMO somewhat misleading. When I see = default, I generally think "oh, the constructor default constructs everything". But this is not the case here.

I think I would instead drop default-member-initializers and explicitly construct the members in the two constructors.

(Yes, I know default member initializers is the way the Standard exposts the class, but they don't have iterator caching).

Edit:

Actually coming back to this, I don't understand why we cache begin(__base) here in the constructor. Shouldn't we only cache it in begin()?

62

I think it would be more natural to use

if (!input_or_output_iterator<iterator_t<_View>>) {
 // cache here
}

65

Is this intended? else {}

If not... there's something funky here if your tests are passing! If so, I would reorganize to avoid this unusual construct.

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

89 ↗

(On Diff #343746)

Add a comment // test CTAD

[tcanens]

libcxx/include/__ranges/drop_view.h

45

There's no requirement that ranges::begin on a default-constructed view is even well-defined (see: ref_view).

Additionally, when a drop_view is copied, the cache must be invalidated in the copy.

[tcanens]

libcxx/include/__ranges/drop_view.h

45

...and when a drop_view is moved-from, the cache must be invalidated in the original.

[zoecarver]

Apply some of the comments.

I still need to:
-> Add a test for move-only input-iterator.
-> Expand the const tests.
-> Add tests for all_t CTAD.

[tcanens]

libcxx/include/__ranges/drop_view.h

57

I'd put __count before __base - see https://lists.isocpp.org/lib/2020/09/17540.php.

[cjdb]

libcxx/include/__ranges/drop_view.h

42

__cache_base is a bit too general a name.

45

@tcanens is this a non-propagating cache?

[tcanens]

libcxx/include/__ranges/drop_view.h

45

Yep. This is the original use case of non-propagating-cache in range-v3.

[zoecarver]

libcxx/include/__ranges/drop_view.h

45

Where in the standard does it say this is a non-propagating cache? Or is that what your paper does?

62

Unfortunately, I just realized that all iterators model input or output iterator, so I think we'll have to stick with forward_range.

[cjdb]

libcxx/include/__ranges/drop_view.h

45

The standard is very underspecified in what kind of cache is necessary here. I just checked, and range-v3 and cmcstl2 disagree on what kind of cache is necessary: range-v3 uses a non-propagating cache; cmcstl2 switches between a non-propagating cache and a simple cache, depending on whether or not we have a forwarding-range (which I think is now borrowed_range).
I'm inclined to support Tim's opinion here, because it's simpler, and doesn't need to introduce a __cached_position type that's dependent on __non_propagating_cache. Any opinions @CaseyCarter?

[tcanens]

libcxx/include/__ranges/drop_view.h

45

Where in the standard does it say this is a non-propagating cache? Or is that what your paper does?

It falls out of the fact that nothing in the standard allows "take a drop_view, call begin() on it, copy it, and call begin() on the copy" to not work.

[zoecarver]

Rebase.

[zoecarver]

Add tests for views::all ctad.

[zoecarver]

I need to update this to use semiregular box.

[cjdb]

Please update according to the recent changes made by P2325.

[ldionne]

• Some of my comments (especially about splitting tests) also apply to other in-flight reviews like transform_view.
• Please don't forget to mark comments as done when they're not relevant anymore (whether they have been implemented or you've decided you wouldn't do it), so it's easy to keep track of things.

I'll wait for this to be rebased onto non_propagating_cache before I re-review the implementation.

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

1 ↗

(On Diff #344559)

Please split this into more files as it makes sense. Each file tests one thing, and what's being tested is at the top of level in a comment, as we always do.

23 ↗

(On Diff #343544)

I'll actually disagree here - I think it's good to stay minimal when we don't lose anything doing so.

[ldionne]

There was quite a bit of discussion offline about the need to invalidate the cached begin() or not. I think we now all agree that we must not propagate the cached value on copies or moves. Here's what I ended up with that is not dependent on non_propagating_cache (we can go back afterwards and perhaps simplify some of this if we have non_propagating_cache):

namespace ranges {
  template<class _Range>
  concept __simple_view =
    view<_Range> && range<const _Range> &&
    same_as<sentinel_t<_Range>, iterator_t<const _Range>> &&
    same_as<iterator_t<_Range>, sentinel_t<const _Range>>;

  template<view _View>
  class drop_view
    : public view_interface<drop_view<_View>>,
  {
    static constexpr _UseCache = forward_range<_View> && !random_access_range<_View>;
    using _Cache = optional<iterator_t<_View>>;
    struct _Empty { };
    [[no_unique_address]] conditional_t<_UseCache, _Cache, _Empty> __cached_begin_;

    _View __base_;
    range_difference_t<_View> __count_;

public:
    constexpr drop_view() requires default_­initializable<_View> 
      : __cached_begin_(), __base_(), __count_(0) 
    { }

    constexpr drop_view(_View __base, range_difference_t<_View> __count)
      : __cached_begin_(), __base_(_VSTD::move(__base)), __count_(__count) {
      _LIBCPP_ASSERT(__count_ >= 0, "count must be greater than or equal to zero.");
    }

    constexpr drop_view(drop_view const& __other) 
      : __cached_begin_() // purposefully not propagating the cached value
      , __base_(__other.__base_)
      , __count_(__other.__count_)
    { }

    constexpr drop_view(drop_view&& __other) 
      : __cached_begin_() // purposefully not propagating the cached value
      , __base_(_VSTD::move(__other.__base_))
      , __count_(_VSTD::move(other.__count_))
    { }

    constexpr drop_view& operator=(drop_view const& __other) {
      if constexpr (_UseCache) {
        __cached_begin_.reset();
      }
      __base_ = __other.__base_;
      __count_ = __other.__count_;
      return *this;
    }

    constexpr drop_view& operator=(drop_view&& __other) {
      if constexpr (_UseCache) {
        __cached_begin_.reset();
        __other.__cached_begin_.reset();
      }
      __base_ = _VSTD::move(__other.__base_);
      __count_ = _VSTD::move(__other.__count_);
      return *this;
    }

    constexpr _View base() const& requires copy_constructible<_View> { return __base_; }
    constexpr _View base() && { return _VSTD::move(__base_); }

    constexpr auto begin()
      requires (!(__simple_view<_View> && random_access_range<const _View> && sized_range<const _View>))
    {
      if constexpr (_UseCache) {
        if (__cached_begin_.empty())
          __cached_begin_ = ranges​::​next(ranges​::​begin(__base_­), __count_­, ranges​::​end(__base_­));
        return *__cached_begin_;

      } else {
        return ranges​::​next(ranges​::​begin(__base_­), __count_­, ranges​::​end(__base_­));
      }
    }

    constexpr auto begin() const
      requires random_access_range<const _View> && sized_range<const _View>
    {
      return ranges​::​next(ranges​::​begin(__base_­), __count_­, ranges​::​end(__base_­));
    }

    constexpr auto end()
      requires (!__simple_view<_View>)
    { return ranges::end(__base_); }

    constexpr auto end() const
      requires range<const _View>
    { return ranges::end(__base_); }

    static constexpr auto __size(auto& __self) {
      const auto __s = ranges::size(__self.__base_);
      const auto __c = static_cast<decltype(__s)>(__self.__count_);
      return __s < __c ? 0 : __s - __c;
    }

    constexpr auto size()
      requires sized_range<_View>
    { return drop_view::__size(*this); }

    constexpr auto size() const
      requires sized_range<const _View>
    { return drop_view::__size(*this); }
  };

  template<class _Range>
  drop_view(_Range&&, range_difference_t<_Range>)
    -> drop_view<views::all_t<_Range>>;
} // namespace ranges

[zoecarver]

• Split up tests.
• Use std::optional as a non-propagating cache (and add a test).

[zoecarver]

libcxx/include/__ranges/drop_view.h

36

This was already done.

42

I'm going to leave it at the top. I don't really see a reason to put it at the bottom, especially when classes have private members by default.

45

For posterity: marking this whole chain as resolved after our discussion on discord.

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

20 ↗

(On Diff #344559)

Remove this.

[zoecarver]

Apply a few remaining review comments.

[• Quuxplusone]

libcxx/include/__ranges/drop_view.h

42

I'm going to leave it at the top

Please do as @ldionne says, and follow libc++ style. Private/data members go at the bottom (and data members get a suffix-underscore; thanks for addressing that part already).
Also, please consider putting __cached_begin_ in front of __count_, for layout reasons. It's more likely that _View begins with an _Empty member than that _View::difference_type does.

[• Quuxplusone]

@ldionne wrote:

Here's what I ended up with that is not dependent on non_propagating_cache (we can go back afterwards and perhaps simplify some of this if we have non_propagating_cache)

FYI, that looks pretty nice to me. And then non_propagating_cache would just be a thin wrapper around an optional — all it needs to provide is .has_value(), .get() (maybe more than one ref-qualification of .get()?), .assign (i.e. the-equivalent-of-operator=, not the-equivalent-of-.emplace), and a default constructor. One might reasonably say "If Louis' code works, then why do we even want a factored-out non_propagating_cache type?" But, I answer, it's still useful to wrap optional, in order to reduce its surface area to just these four necessary bits.

[cjdb]

Per offline discussion, I'm okay with this going ahead, provided we return to add __non_propagating_cache once I've landed it.

libcxx/include/__ranges/drop_view.h

134

Please line up requires-clauses with the start of the function declaration. Small clause (such as this) can go on the same line.

I've usually turned a blind eye to this because comments about formatting are noise that lead to unproductive debates, and my intention has been to get clang-format to take care of this inconsistency in one fell swoop. Having said that, since I don't know when I'll be able to apply the tool project-wide and not get something weird, it's probably worth adopting the "official" libc++ style for future contributors' sakes.

142–145

Does this need to be fixed?

libcxx/test/std/ranges/range.adaptors/range.drop/general.pass.cpp

62

I like that you're using this!

[tcanens]

libcxx/include/__ranges/drop_view.h

38

The cache needs to be used for random access ranges too unless the range is also sized.

[• Quuxplusone]

libcxx/include/__ranges/drop_view.h

134

FWIW, I agree about "unproductive debates" ;) but if there's an official libc++ style, it's always been "indent the subordinate clause by one level."

template<class T>
  requires foo<T>
auto bar()
  -> decltype(baz)
{
  return quux;
}

I don't think your insistence on following clang-format's (broken) formatting guidance here is helpful to the project. I predict that clang-format will eventually implement C++20 formatting, and then it'll be good that Zoe's been following the "indent requires-clauses" style.

[cjdb]

libcxx/include/__ranges/drop_view.h

134

Louis gave me creative freedom to set the style for requires-clauses. I made the decision that they wouldn't be indented.

[ldionne]

I would like to see tests for the constructors. They're going to be simple tests, but we should be testing everything systematically. Elsewhere we have xxxx.ctor.pass.cpp tests. Also, can you please explicitly mark where you're testing each overload of begin() and end()?

I've got a few comments, but they are pretty small. We should be able to land this today.

libcxx/include/__ranges/drop_view.h

50

noexcept(is_nothrow_default_constructible_v<_View>)?

Also, this should be tested.

67

I think __cached_begin_(nullopt) might be clearer - it's a nice reminder that we're not default-constructing the iterator itself, but only an optional. (here and elsewhere)

134

I had not realized that the WP was indenting requires-clauses, but I think it might make sense to try to follow that. @cjdb is there a reason why you went for no indentation in the first place?

What I care most about is that we're consistent and that our code is readable and idiomatic as much as possible. Is there an established way of formatting those in the community?

libcxx/test/std/ranges/range.adaptors/range.drop/begin.pass.cpp

14

Those should describe what's being tested in the test. We've always done that in libc++, and frankly it's quite useful to know exactly what's being tested (especially since we love to have subtly different overloads of functions in the stdlib).

[zoecarver]

libcxx/include/__ranges/drop_view.h

38

Why does the range being sized matter? Doesn't a random access range provide amortized constant-time complexity for element lookup (which is the requirement for drop_view)?

42

I reordered these based on Tim's suggestion:

I'd put count before base - see https://lists.isocpp.org/lib/2020/09/17540.php.

But you're right, I think cached_begin should still come first (then count, then base).

42

Private/data members go at the bottom (and data members get a suffix-underscore; thanks for addressing that part already).

Where does it say that private data members go at the bottom? If it's not documented anywhere, I'll go off of what style we currently use. Doing a quick audit of the first three types that come to mind, I see that basic_string, shared_ptr (and all of its helper classes), and map all put their data members at the top. After I continued to look, the only class I could find that didn't do this is vector, but even its base/helper classes put their private members at the top.

I find these comments about formatting (here and elsewhere) counter productive. I try not to comment on formatting unless it's really egregious. Until we create some formatting rules (which I think would be a great idea, because then contributors would know how to format their code, and you wouldn't have to waste time in reviews asking for changes), let's not comment about formatting unless it makes the code harder to understand.

142–145

At some point, yes. But we don't have all_t yet and this is not functionally different than what it will be.

[tcanens]

libcxx/include/__ranges/drop_view.h

38

You need the size of the underlying view to figure out how much to drop in constant time.

If you don't know that, then you have to advance the iterator one step at a time until you either reach the end of the range or N steps, and that's linear.

[cjdb]

libcxx/include/__ranges/drop_view.h

50

Why are we not just = defaulting this constructor?

134

is there a reason why you went for no indentation in the first place?

It's the style I adopted back in 2016 when working on cmcstl2; libc++ didn't have any established precedent for requires-clauses, so I paved a way forward. I also find it kind of arbitrary to indent it? We don't indent in the middle of a code block unless we open some sort of grouping tokens (usually parens or braces).
It also swallows up valuable horizontal width, which can impact readability.

Is there an established way of formatting those in the community?

• cmcstl2 and cjdb-ranges line it up
• Microsoft/STL and libstdc++ indent

All four use same-line requires-clauses for short requirements, which I think we should adopt in libc++.

I had not realized that the WP was indenting requires-clauses, but I think it might make sense to try to follow that.

Sure, if you want to rescind your offer from D99691, I'll play ball. I would like to know why you think it makes sense to follow the standard wording, but we can follow up with that offline.

[zoecarver]

Update based on review.

libcxx/include/__ranges/drop_view.h

38

Aha, that makes sense. Thanks for explaining! :)

libcxx/test/std/ranges/range.adaptors/range.drop/begin.pass.cpp

14

Good point. Fixing.

[ldionne]

LGTM pending CI and applying the comments you noted when we spoke just now.

This is awesome! Let's move to transform_view now!

libcxx/include/__ranges/drop_view.h

42

@zoecarver is right that we sometimes have private data members at the top, and sometimes at the bottom. I think either way's fine.

Regarding formatting comments, I think what's hurting is not that we have them during reviews, but that not everybody agrees on how to format things. That creates back-and-forth and arguing over those details, and that is what's harmful. Taking 2 seconds to reformat something that isn't formatted properly isn't the issue IMO.

[zoecarver]

Update based on the last few review comments.

When the CI is green I'll land it.

[tcanens]

libcxx/include/__ranges/drop_view.h

107

For the random-access-and-sized case, begin should not call ranges::next - that can be linear for sized-but-not-sized-sentinel ranges. It should just return ranges::begin(__base_) + std::min(__count_, ranges::distance(__base_)). Ditto below.

[zoecarver]

Remove shadowing for GCC.

[zoecarver]

Fix memset warning for GCC.

[zoecarver]

libcxx/include/__ranges/drop_view.h

107

I think it's OK to use next because we can ensure that next will always use something equivalent to ranges::begin(__base_) + std::min(__count_, ranges::distance(__base_)) (even if it's technically permitted to do something slower by the standard). I'd rather not add a special case here.

[tcanens]

libcxx/include/__ranges/drop_view.h

107

I think it's OK to use next because we can ensure that next will always use something equivalent to ranges::begin(__base_) + std::min(__count_, ranges::distance(__base_)) (even if it's technically permitted to do something slower by the standard).

The point is that you can't. For a sized-but-not-sized-sentinel range, the size information is only known from the range itself. Once you decompose the range into an iterator and a sentinel for ranges::next, that information is gone.

[zoecarver]

libcxx/include/__ranges/drop_view.h

107

I see what you're getting at. So we'd need to change the condition to be sized_sentinel_for (not sized_range) so that it matches what ranges::advance does (or, better yet, do what you suggested and take advantage of the sized range inside of this function).

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/data.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
   __ranges/subrange.h

libcxx/include/__ranges/drop_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_DROP_VIEW_H
+#define _LIBCPP___RANGES_DROP_VIEW_H
+
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
+#include <__ranges/access.h>
+#include <__ranges/view_interface.h>
+#include <__ranges/all.h>
+#include <type_traits>
+#include <optional>
+
+#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<view _View>
+  class drop_view
+    : public view_interface<drop_view<_View>> {
+
+    // We cache begin() whenever ranges::next is not guaranteed O(1) to provide an
+    // amortized O(1) begin() method. If this is an input_range, then we cannot cache
+    // begin because begin is not equality preserving.
+    // Note: drop_view<input-range>::begin() is still trivially amortized O(1) because
+    // one can't call begin() on it more than once.
+    static constexpr bool _UseCache = forward_range<_View> && !(random_access_range<_View> && sized_range<_View>);
+    using _Cache = optional<iterator_t<_View>>;
+    struct _Empty { };
+
+    // For forward ranges use std::optional to cache the begin iterator.
+    // No unique address + _Empty means we don't use any extra space when this
+    // is not a forward iterator.
+    [[no_unique_address]] conditional_t<_UseCache, _Cache, _Empty> __cached_begin_;
+    range_difference_t<_View> __count_ = 0;
+    _View __base_ = _View();
+
+public:
+    drop_view() requires default_initializable<_View> = default;
+
+    constexpr drop_view(_View __base, range_difference_t<_View> __count)
+      : __cached_begin_()
+      , __count_(__count)
+      , __base_(_VSTD::move(__base))
+    {
+      _LIBCPP_ASSERT(__count_ >= 0, "count must be greater than or equal to zero.");
+    }
+
+    constexpr drop_view(drop_view const& __other)
+      : __cached_begin_() // Intentionally not propagating the cached begin iterator.
+      , __count_(__other.__count_)
+      , __base_(__other.__base_)
+    { }
+
+    constexpr drop_view(drop_view&& __other)
+      : __cached_begin_() // Intentionally not propagating the cached begin iterator.
+      , __count_(_VSTD::move(__other.__count_))
+      , __base_(_VSTD::move(__other.__base_))
+    { }
+
+    constexpr drop_view& operator=(drop_view const& __other) {
+      if constexpr (_UseCache) {
+        __cached_begin_.reset();
+      }
+      __base_ = __other.__base_;
+      __count_ = __other.__count_;
+      return *this;
+    }
+
+    constexpr drop_view& operator=(drop_view&& __other) {
+      if constexpr (_UseCache) {
+        __cached_begin_.reset();
+        __other.__cached_begin_.reset();
+      }
+      __base_ = _VSTD::move(__other.__base_);
+      __count_ = _VSTD::move(__other.__count_);
+      return *this;
+    }
+
+    constexpr _View base() const& requires copy_constructible<_View> { return __base_; }
+    constexpr _View base() && { return _VSTD::move(__base_); }
+
+    constexpr auto begin()
+      requires (!(__simple_view<_View> &&
+                  random_access_range<const _View> && sized_range<const _View>))
+    {
+      if constexpr (_UseCache)
+        if (__cached_begin_)
+          return *__cached_begin_;
+
+      auto __tmp = ranges::next(ranges::begin(__base_), __count_, ranges::end(__base_));
+      if constexpr (_UseCache)
+        __cached_begin_ = __tmp;
+      return __tmp;
+    }
+
+    constexpr auto begin() const
+      requires random_access_range<const _View> && sized_range<const _View>
+    {
+      return ranges::next(ranges::begin(__base_), __count_, ranges::end(__base_));
+    }
+
+    constexpr auto end()
+      requires (!__simple_view<_View>)
+    { return ranges::end(__base_); }
+
+    constexpr auto end() const
+      requires range<const _View>
+    { return ranges::end(__base_); }
+
+    static constexpr auto __size(auto& __self) {
+      const auto __s = ranges::size(__self.__base_);
+      const auto __c = static_cast<decltype(__s)>(__self.__count_);
+      return __s < __c ? 0 : __s - __c;
+    }
+
+    constexpr auto size()
+      requires sized_range<_View>
+    { return __size(*this); }
+
+    constexpr auto size() const
+      requires sized_range<const _View>
+    { return __size(*this); }
+  };
+
+  template<class _Range>
+  drop_view(_Range&&, range_difference_t<_Range>)
+  // TODO: this is just recreating all_t.
+    -> drop_view<decltype(views::all(std::declval<_Range>()))>;
+
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___RANGES_DROP_VIEW_H

libcxx/include/ranges

 
 */
 
 #include <__config>
 #include <__ranges/access.h>
 #include <__ranges/all.h>
 #include <__ranges/concepts.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.adaptors/range.drop/base.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
+
+// constexpr V base() const& requires copy_constructible<V> { return base_; }
+// constexpr V base() && { return std::move(base_); }
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "types.h"
+
+constexpr bool test() {
+  std::ranges::drop_view<ContiguousView> dropView1;
+  auto base1 = std::move(dropView1).base();
+  assert(std::ranges::begin(base1) == globalBuff);
+
+  // Note: we should *not* drop two elements here.
+  std::ranges::drop_view<ContiguousView> dropView2(ContiguousView{4}, 2);
+  auto base2 = std::move(dropView2).base();
+  assert(std::ranges::begin(base2) == globalBuff + 4);
+
+  std::ranges::drop_view<CopyableView> dropView3;
+  auto base3 = dropView3.base();
+  assert(std::ranges::begin(base3) == globalBuff);
+  auto base4 = std::move(dropView3).base();
+  assert(std::ranges::begin(base4) == globalBuff);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.drop/begin.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
+
+// constexpr auto begin()
+//   requires (!(simple-view<V> &&
+//               random_access_range<const V> && sized_range<const V>));
+// constexpr auto begin() const
+//   requires random_access_range<const V> && sized_range<const V>;
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "types.h"
+
+template<class T>
+concept BeginInvocable = requires(std::ranges::drop_view<T> t) { t.begin(); };
+
+constexpr bool test() {
+  // random_access_range<const V> && sized_range<const V>
+  std::ranges::drop_view dropView1(ContiguousView(), 4);
+  assert(dropView1.begin() == globalBuff + 4);
+
+  // !random_access_range<const V>
+  std::ranges::drop_view dropView2(ForwardView(), 4);
+  assert(dropView2.begin().base() == globalBuff + 4);
+
+  // !random_access_range<const V>
+  std::ranges::drop_view dropView3(InputView(), 4);
+  assert(dropView3.begin().base() == globalBuff + 4);
+
+  // random_access_range<const V> && sized_range<const V>
+  std::ranges::drop_view dropView4(ContiguousView(), 8);
+  assert(dropView4.begin() == globalBuff + 8);
+
+  // random_access_range<const V> && sized_range<const V>
+  std::ranges::drop_view dropView5(ContiguousView(), 0);
+  assert(dropView5.begin() == globalBuff);
+
+  // random_access_range<const V> && sized_range<const V>
+  const std::ranges::drop_view dropView6(ContiguousView(), 0);
+  assert(dropView6.begin() == globalBuff);
+
+  // random_access_range<const V> && sized_range<const V>
+  std::ranges::drop_view dropView7(ContiguousView(), 10);
+  assert(dropView7.begin() == globalBuff + 8);
+
+  CountedView view8;
+  std::ranges::drop_view dropView8(view8, 5);
+  assert(dropView8.begin().base().base() == globalBuff + 5);
+  assert(dropView8.begin().stride_count() == 5);
+  assert(dropView8.begin().base().base() == globalBuff + 5);
+  assert(dropView8.begin().stride_count() == 5);
+
+  static_assert(!BeginInvocable<const ForwardView>);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.drop/ctad.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
+
+// template<class R>
+// drop_view(R&&, range_difference_t<R>) -> drop_view<views::all_t<R>>;
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "types.h"
+
+namespace ranges = std::ranges;
+
+static_assert(std::same_as<decltype(ranges::drop_view(ContiguousView(), 0)), ranges::drop_view<ContiguousView>>);
+static_assert(std::same_as<decltype(ranges::drop_view(CopyableView(), 0)), ranges::drop_view<CopyableView>>);
+static_assert(std::same_as<decltype(ranges::drop_view(ForwardView(), 0)), ranges::drop_view<ForwardView>>);
+static_assert(std::same_as<decltype(ranges::drop_view(InputView(), 0)), ranges::drop_view<InputView>>);
+
+static_assert(std::same_as<decltype(ranges::drop_view(std::declval<ForwardRange&>(), 0)),
+                           ranges::drop_view<ranges::ref_view<ForwardRange>>>);
+
+static_assert(std::same_as<decltype(ranges::drop_view(BorrowableRange(), 0)),
+                           ranges::drop_view<ranges::subrange<int*>>>);

libcxx/test/std/ranges/range.adaptors/range.drop/ctor.default.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
+
+// drop_view() requires default_initializable<V> = default;
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "types.h"
+
+constexpr bool test() {
+  std::ranges::drop_view<ContiguousView> dropView1;
+  assert(std::ranges::begin(dropView1) == globalBuff);
+
+  static_assert( std::is_default_constructible_v<std::ranges::drop_view<ForwardView>>);
+  static_assert(!std::is_default_constructible_v<std::ranges::drop_view<NoDefaultCtorForwardView>>);
+
+  static_assert( std::is_nothrow_default_constructible_v<std::ranges::drop_view<ForwardView>>);
+  static_assert(!std::is_nothrow_default_constructible_v<ThrowingDefaultCtorForwardView>);
+  static_assert(!std::is_nothrow_default_constructible_v<std::ranges::drop_view<ThrowingDefaultCtorForwardView>>);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.drop/ctor.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
+
+// constexpr drop_view(V base, range_difference_t<V> count);
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "types.h"
+
+constexpr bool test() {
+  std::ranges::drop_view dropView1(ContiguousView(), 4);
+  assert(dropView1.size() == 4);
+  assert(dropView1.begin() == globalBuff + 4);
+
+  std::ranges::drop_view dropView2(ForwardView(), 4);
+  assert(dropView2.begin().base() == globalBuff + 4);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.drop/dangling.cache.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
+
+// If we have a copy-propagating cache, when we copy ZeroOnDestroy, we will get a
+// dangling reference to the copied-from object. This test ensures that we do not
+// propagate the cache on copy.
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "types.h"
+
+struct ZeroOnDestroy : std::ranges::view_base {
+  unsigned count = 0;
+  int buff[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  constexpr ForwardIter begin() { return ForwardIter(buff); }
+  constexpr ForwardIter begin() const { return ForwardIter(); }
+  constexpr ForwardIter end() { return ForwardIter(buff + 8); }
+  constexpr ForwardIter end() const { return ForwardIter(); }
+
+  ~ZeroOnDestroy() {
+    memset(buff, 0, sizeof(buff));
+  }
+
+  static auto dropFirstFour() {
+    ZeroOnDestroy zod;
+    std::ranges::drop_view dv(zod, 4);
+    // Make sure we call begin here so the next call to begin will
+    // use the cached iterator.
+    assert(*dv.begin() == 5);
+    // Intentionally invoke the copy ctor here.
+    return std::ranges::drop_view(dv);
+  }
+};
+
+int main(int, char**) {
+  auto noDanlingCache = ZeroOnDestroy::dropFirstFour();
+  // If we use the cached version, it will reference the copied-from view.
+  // Worst case this is a segfault, best case it's an assertion fired.
+  assert(*noDanlingCache.begin() == 5);
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.drop/end.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
+
+// constexpr auto end()
+//   requires (!simple-view<V>)
+// constexpr auto end() const
+//   requires range<const V>
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "types.h"
+
+constexpr bool test() {
+  // range<const V>
+  std::ranges::drop_view dropView1(ContiguousView(), 4);
+  assert(dropView1.end() == globalBuff + 8);
+
+  // !simple-view<V>
+  std::ranges::drop_view dropView2(InputView(), 4);
+  assert(dropView2.end() == globalBuff + 8);
+
+  // range<const V>
+  const std::ranges::drop_view dropView3(ContiguousView(), 0);
+  assert(dropView3.end() == globalBuff + 8);
+
+  // !simple-view<V>
+  const std::ranges::drop_view dropView4(InputView(), 2);
+  assert(dropView4.end() == globalBuff + 8);
+
+  // range<const V>
+  std::ranges::drop_view dropView5(ContiguousView(), 10);
+  assert(dropView5.end() == globalBuff + 8);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.drop/general.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
+
+// Some basic examples of how drop_view might be used in the wild. This is a general
+// collection of sample algorithms and functions that try to mock general usage of
+// this view.
+
+#include <ranges>
+
+#include <vector>
+#include <list>
+#include <string>
+
+#include <cassert>
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "types.h"
+
+template<class T>
+concept ValidDropView = requires { typename std::ranges::drop_view<T>; };
+
+static_assert(ValidDropView<ContiguousView>);
+static_assert(!ValidDropView<Range>);
+
+template<std::ranges::view View>
+bool orderedFibonacci(View v, int n = 1) {
+  if (v.size() < 3)
+    return true;
+
+  if (v[2] != v[0] + v[1])
+    return false;
+
+  return orderedFibonacci(std::ranges::drop_view(v.base(), n), n + 1);
+}
+
+template<std::ranges::view View>
+std::ranges::view auto makeEven(View v) {
+  return std::ranges::drop_view(v, v.size() % 2);
+}
+
+template<std::ranges::view View, class T>
+int indexOf(View v, T element) {
+  int index = 0;
+  for (auto e : v) {
+    if (e == element)
+      return index;
+    index++;
+  }
+  return -1;
+}
+
+template<std::ranges::view View, class T>
+std::ranges::view auto removeBefore(View v, T element) {
+  std::ranges::drop_view out(v, indexOf(v, element) + 1);
+  return View(out.begin(), out.end());
+}
+
+template<>
+constexpr bool std::ranges::enable_view<std::vector<int>> = true;
+
+template<>
+constexpr bool std::ranges::enable_view<std::list<int>> = true;
+
+template<>
+constexpr bool std::ranges::enable_view<std::string> = true;
+
+int main(int, char**) {
+  const std::vector vec = {1,1,2,3,5,8,13};
+  assert(orderedFibonacci(std::ranges::drop_view(vec, 0)));
+  const std::vector vec2 = {1,1,2,3,5,8,14};
+  assert(!orderedFibonacci(std::ranges::drop_view(vec2, 0)));
+
+  const std::list l = {1, 2, 3};
+  auto el = makeEven(l);
+  assert(el.size() == 2);
+  assert(*el.begin() == 2);
+
+  const std::string s = "Hello, World";
+  assert(removeBefore(s, ' ') == "World");
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.drop/size.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
+
+// constexpr auto size()
+//   requires sized_range<V>
+// constexpr auto size() const
+//   requires sized_range<const V>
+
+#include <ranges>
+
+#include "test_macros.h"
+#include "types.h"
+
+template<class T>
+concept SizeInvocable = requires(std::ranges::drop_view<T> t) { t.size(); };
+
+constexpr bool test() {
+  // sized_range<V>
+  std::ranges::drop_view dropView1(ContiguousView(), 4);
+  assert(dropView1.size() == 4);
+
+  // sized_range<V>
+  std::ranges::drop_view dropView2(ContiguousView(), 0);
+  assert(dropView2.size() == 8);
+
+  // sized_range<const V>
+  const std::ranges::drop_view dropView3(ContiguousView(), 8);
+  assert(dropView3.size() == 0);
+
+  // sized_range<const V>
+  const std::ranges::drop_view dropView4(ContiguousView(), 10);
+  assert(dropView4.size() == 0);
+
+  // Because ForwardView is not a sized_range.
+  static_assert(!SizeInvocable<ForwardView>);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.drop/types.h

+//===----------------------------------------------------------------------===//
+//
+// 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 TEST_STD_RANGES_RANGE_ADAPTORS_RANGE_DROP_TYPES_H
+#define TEST_STD_RANGES_RANGE_ADAPTORS_RANGE_DROP_TYPES_H
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+int globalBuff[8];
+
+struct ContiguousView : std::ranges::view_base {
+  int start_;
+  constexpr ContiguousView(int start = 0) : start_(start) {}
+  constexpr ContiguousView(ContiguousView&&) = default;
+  constexpr ContiguousView& operator=(ContiguousView&&) = default;
+  constexpr friend int* begin(ContiguousView& view) { return globalBuff + view.start_; }
+  constexpr friend int* begin(ContiguousView const& view) { return globalBuff + view.start_; }
+  constexpr friend int* end(ContiguousView&) { return globalBuff + 8; }
+  constexpr friend int* end(ContiguousView const&) { return globalBuff + 8; }
+};
+
+struct CopyableView : std::ranges::view_base {
+  int start_;
+  constexpr CopyableView(int start = 0) : start_(start) {}
+  constexpr CopyableView(CopyableView const&) = default;
+  constexpr CopyableView& operator=(CopyableView const&) = default;
+  constexpr friend int* begin(CopyableView& view) { return globalBuff + view.start_; }
+  constexpr friend int* begin(CopyableView const& view) { return globalBuff + view.start_; }
+  constexpr friend int* end(CopyableView&) { return globalBuff + 8; }
+  constexpr friend int* end(CopyableView const&) { return globalBuff + 8; }
+};
+
+using ForwardIter = forward_iterator<int*>;
+struct ForwardView : std::ranges::view_base {
+  constexpr ForwardView() = default;
+  constexpr ForwardView(ForwardView&&) = default;
+  constexpr ForwardView& operator=(ForwardView&&) = default;
+  constexpr friend ForwardIter begin(ForwardView&) { return ForwardIter(globalBuff); }
+  constexpr friend ForwardIter begin(ForwardView const&) { return ForwardIter(globalBuff); }
+  constexpr friend ForwardIter end(ForwardView&) { return ForwardIter(globalBuff + 8); }
+  constexpr friend ForwardIter end(ForwardView const&) { return ForwardIter(globalBuff + 8); }
+};
+
+struct ForwardRange {
+  ForwardIter begin() const;
+  ForwardIter end() const;
+  ForwardIter begin();
+  ForwardIter end();
+};
+
+struct ThrowingDefaultCtorForwardView : std::ranges::view_base {
+  ThrowingDefaultCtorForwardView() noexcept(false);
+  ForwardIter begin() const;
+  ForwardIter end() const;
+  ForwardIter begin();
+  ForwardIter end();
+};
+
+struct NoDefaultCtorForwardView : std::ranges::view_base {
+  NoDefaultCtorForwardView() = delete;
+  ForwardIter begin() const;
+  ForwardIter end() const;
+  ForwardIter begin();
+  ForwardIter end();
+};
+
+struct BorrowableRange {
+  friend int* begin(BorrowableRange const& range);
+  friend int* end(BorrowableRange const&);
+  friend int* begin(BorrowableRange& range);
+  friend int* end(BorrowableRange&);
+};
+
+template<>
+inline constexpr bool std::ranges::enable_borrowed_range<BorrowableRange> = true;
+
+struct InputView : std::ranges::view_base {
+  constexpr cpp20_input_iterator<int*> begin() const { return cpp20_input_iterator<int*>(globalBuff); }
+  constexpr int* end() const { return globalBuff + 8; }
+  constexpr cpp20_input_iterator<int*> begin() { return cpp20_input_iterator<int*>(globalBuff); }
+  constexpr int* end() { return globalBuff + 8; }
+};
+
+constexpr bool operator==(const cpp20_input_iterator<int*> &lhs, int* rhs) { return lhs.base() == rhs; }
+constexpr bool operator==(int* lhs, const cpp20_input_iterator<int*> &rhs) { return rhs.base() == lhs; }
+
+struct Range {
+  friend int* begin(Range const&);
+  friend int* end(Range const&);
+  friend int* begin(Range&);
+  friend int* end(Range&);
+};
+
+using CountedIter = stride_counting_iterator<forward_iterator<int*>>;
+struct CountedView : std::ranges::view_base {
+  constexpr CountedIter begin() { return CountedIter(ForwardIter(globalBuff)); }
+  constexpr CountedIter begin() const { return CountedIter(ForwardIter(globalBuff)); }
+  constexpr CountedIter end() { return CountedIter(ForwardIter(globalBuff + 8)); }
+  constexpr CountedIter end() const { return CountedIter(ForwardIter(globalBuff + 8)); }
+};
+
+#endif // TEST_STD_RANGES_RANGE_ADAPTORS_RANGE_DROP_TYPES_H