[libcxx][ranges] adds _`non-propagating-cache`_

[ldionne]

Summary

_`non-propagating-cache`_ is a local cache that doesn't pass its value
on after a move (instead invalidating both caches) or a copy (instead
invalidating the copyer).

Formal wording first appears in P2328, a paper that makes retroactive
changes to C++20, but the type has always been necessary for a correct
implementation of ranges such as std::ranges::drop_view.

Depends on D102119.
Blocks D102037.

[cjdb]

libcxx/include/__ranges/non_propagating_cache.h

61–67

@tcanens I've deliberately not put a cache wrapper here yet, because I'm not sure if the wrapper needs to go inside __emplace_deref or if it goes in optional<__cache_wrapper<_Tp>> (and here), or somewhere else entirely.

[tcanens]

libcxx/include/__ranges/non_propagating_cache.h

61–67

My guess is that you don't need this function at all. If join_view stores a __non_propagating_cache<__cache_wrapper<...>> then emplace-deref can just be implemented with emplace.

[cjdb]

rebases to activate CI

[Mordante]

Our normal policy is not to implement papers before they are accepted. I can understand why you want make an exception in this case. Can you update the status papers documentation and add a warning based on which version of the paper this feature has been implemented? If the wording changes before the paper is accepted we need to update our implementation to match the final wording.

This remark also applies to D102119

libcxx/include/__ranges/non_propagating_cache.h

3

Please update or remove the filename.

62

Remove the std::.

[cjdb]

removes __emplace_deref

Can you update the status papers documentation and add a warning based on which version of the paper this feature has been implemented? If the wording changes before the paper is accepted we need to update our implementation to match the final wording.

Done for D102119. I'm not sure if it's necessary to do it for this patch since the cache is an implementation detail and has always been necessary for C++20 ranges. Tying it to P2328 implies that it's a C++23 addition, which isn't the case here. Regardless of what the committee decides to do with P2328, we need to keep this type.

[tschuett]

Would you mind documenting the state of the paper in the header like in the format header?

[cjdb]

In D102121#2746822, @tschuett wrote:

Would you mind documenting the state of the paper in the header like in the format header?

There is nothing to document. I don't know how else to say that C++20 requires __non_propagating_cache, and it is completely irrelevant to the status of P2328. This cache is still necessary, even if Tim chooses to abandon the paper.

[zoecarver]

libcxx/include/__ranges/non_propagating_cache.h

35

Could we constrain this further?

36

Indent.

39

This name should be mangled.

libcxx/test/libcxx/ranges/range.nonprop.cache/cache_disabled.compile.pass.cpp

20 ↗

(On Diff #343935)

This isn't so much a request for a changes as a question: most of the time do we want to store a whole range or just an iterator. At least for drop_view, I feel like we'd only need an iterator.

In light of that, maybe test this with more than one type (it doesn't have to be a range or an iterator, in fact).

[cjdb]

libcxx/include/__ranges/non_propagating_cache.h

35

Why should we constrain this further?

39

__uglified?

libcxx/test/libcxx/ranges/range.nonprop.cache/cache_disabled.compile.pass.cpp

20 ↗

(On Diff #343935)

Wholly, or just here?

[Mordante]

In D102121#2746815, @cjdb wrote:

Can you update the status papers documentation and add a warning based on which version of the paper this feature has been implemented? If the wording changes before the paper is accepted we need to update our implementation to match the final wording.

Done for D102119. I'm not sure if it's necessary to do it for this patch since the cache is an implementation detail and has always been necessary for C++20 ranges. Tying it to P2328 implies that it's a C++23 addition, which isn't the case here. Regardless of what the committee decides to do with P2328, we need to keep this type.

As discussed on Discord. Since this only adds the exposition only part of the paper I think it's not too important.
Thanks for adding the paper to D102119.

[cjdb]

rebases to activate CI

[cjdb]

rebases to check CI

[cjdb]

adjusts module map

[cjdb]

rebases to activate CI

[cjdb]

• fixes header
• ensures that __non_propagating_cache is derived from std::optional when it's in cache mode

[• Quuxplusone]

Please mention [P2328] in the summary line of the commit.

libcxx/include/__ranges/non_propagating_cache.h

37

It would be vastly more maintainable to make __non_propagating_cache have a data member of type optional<_Tp>, instead of using inheritance here. Please do so. (If you don't, I probably will at some point.)

[cjdb]

libcxx/include/__ranges/non_propagating_cache.h

36

@ldionne left it up to me to decide how libc++ formats requires clauses, and I decided that they shouldn't be indented.

37

(If you don't, I probably will at some point.)

In doing so, you would become responsible for adding all std::optional member functions and free functions, adding tests to make sure they behave the same as the std::optional API, and you'll also be responsible for adding any new functionality that is added to std::optional in future standards (e.g. P0798). If that sounds more maintainable than the current implementation: sure, upload a patch for review after D102121 is merged into main.

[zoecarver]

Other than my nit, this looks good to me.

Note: I think I recall you (or maybe it was someone else) saying that we should name headers like this __non_propagating_cache.h (with two underscores at the beginning). We should decide what we want to do about this and update both patches accordingly.

libcxx/include/__ranges/non_propagating_cache.h

35

Not sure what I was thinking here, sorry.

39

Yes.

[ldionne]

libcxx/include/__ranges/non_propagating_cache.h

35

I don't understand the purpose of this __enable_cache parameter. I believe this type should do what it does unconditionally, and when using it, one could write conditional_t<SOME-CONDITION, __non_propagating_cache<T>, empty> or something along those lines. WDYT?

37

Is non_propagating_cache ever handed out to users? I don't think so, right?

If that's correct, then I believe we don't have to actually implement the exact std::optional API, only what we need. And if that's the case, then I do agree that not inheriting from std::optional is going to make it easier to make changes in the future, so I'd hold it as a member instead.

[cjdb]

libcxx/include/__ranges/non_propagating_cache.h

35

It's too easy to get this wrong on the author's end, and too easy to miss on the reviewer's end. I want to make sure that it's very clear to all parties that a non-propagating cache is only necessary in situations when it is necessary. It may end up being that we often use __non_propagating_cache<T, true>, but that forces the author to think about the situation, and it makes sure that the reviewer sees the author has thought about it.

I think I should add this in light of the above:

inline constexpr bool __always_cache = true;

37

Is non_propagating_cache ever handed out to users? I don't think so, right?

No.

If that's correct, then I believe we don't have to actually implement the exact std::optional API, only what we need. And if that's the case, then I do agree that not inheriting from std::optional is going to make it easier to make changes in the future, so I'd hold it as a member instead.

How is it going to make it easier on us in the future? By inheriting from std::optional, we get exactly what we need at all times. There's zero maintenance here: we don't need to worry about the design, and we don't need to worry about API corner cases that std::optional has already taken into account.

I'd prefer inheriting correctness: that's why we're trying to share code among std/ranges algorithms, right?

[ldionne]

Commandeering per discussion w/ Chris, since I need this for filter_view.

[ldionne]

Take over.

[ldionne]

Hopefully fix -Wself-assign issue on GCC and Clang

[ldionne]

Fix typo in ADDITIONAL_COMPILE_FLAGS: markup.

[Mordante]

libcxx/include/__ranges/non_propagating_cache.h

43

http://eel.is/c++draft/range.nonprop.cache#1.1 non-propagating-cache<T> constrains its type parameter T with is_­object_­v<T>.

44

There's no _LIBCPP_TEMPLATE_VIS.

88

I miss http://eel.is/c++draft/range.nonprop.cache#1.6

non-propagating-cache<T> has an additional member function template specified as follows:

template<class I>
  constexpr T& emplace-deref(const I& i);    // exposition only

Is that intentionally?

libcxx/test/libcxx/ranges/range.nonprop.cache/assign.copy.pass.cpp

51

This tests an implementation detail. Shouldn't this be guarded for usage with the libc++ library?
Other tests also use implementation details, please grep for __.

[• Quuxplusone]

libcxx/include/__ranges/non_propagating_cache.h

43

This is undetectable, and therefore it's cheaper (in terms of compile time and source code simplicity) not to bother with it.

88

Exposition-only members are undetectable, and anyway it looks like emplace-deref is equivalent to this->emplace(*i).
See tcanens' comment https://reviews.llvm.org/D102121#inline-965635

[Mordante]

libcxx/include/__ranges/non_propagating_cache.h

43

Ok. (It just makes me wonder why it's specified in the Standard.)

88

Then it seems it's indeed intentionally.

[ldionne]

libcxx/include/__ranges/non_propagating_cache.h

43

I added it. It is detectable with SFINAE.

libcxx/test/libcxx/ranges/range.nonprop.cache/assign.copy.pass.cpp

51

This test lives in libcxx/test/libcxx, which is for implementation details only.

[ldionne]

Address review comments

[• Quuxplusone]

libcxx/include/__ranges/non_propagating_cache.h

43

@ldionne: can you clarify what you mean? I believe it's undetectable in the sense that libc++'s users are not even allowed to name __non_propagating_cache, and libc++'s own code never attempts to SFINAE on it; therefore the SFINAE doesn't matter. Do you know any place where libc++ is trying to make a decision based on the well-formedness of __non_propagating_cache<T>?

[ldionne]

libcxx/include/__ranges/non_propagating_cache.h

43

Oh. No, indeed, you're right from that perspective. For a second, I put libc++ itself as the user and thought "well, libc++ can technically tell whether it's constrained or not".

In that case, I don't feel strongly about it, but I would rather keep the constraint and invoke the consistency-with-the-spec argument. I originally removed the constraint because I didn't realize it was part of the spec.

[Mordante]

LGTM!

libcxx/test/libcxx/ranges/range.nonprop.cache/assign.copy.pass.cpp

51

TIL. Seems I need to move some tests of my format series.

libcxx/include/CMakeLists.txt

set(files
   __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/non_propagating_cache.h
   __ranges/ref_view.h
   __ranges/size.h
   __ranges/subrange.h
   __ranges/transform_view.h
   __ranges/view_interface.h
   __split_buffer
   __std_stream
   __string

libcxx/include/__ranges/drop_view.h

 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__ranges/access.h>
 #include <__ranges/all.h>
 #include <__ranges/concepts.h>
 #include <__ranges/enable_borrowed_range.h>
+#include <__ranges/non_propagating_cache.h>
 #include <__ranges/size.h>
 #include <__ranges/view_interface.h>
-#include <optional>
+#include <__utility/move.h>
+#include <concepts>
 #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<view _View>
   class drop_view
-    : public view_interface<drop_view<_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_;
+    using _Cache = _If<_UseCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
+    [[no_unique_address]] _Cache __cached_begin_ = _Cache();
     range_difference_t<_View> __count_ = 0;
     _View __base_ = _View();
 
 public:
     drop_view() requires default_initializable<_View> = default;
 
     _LIBCPP_HIDE_FROM_ABI
     constexpr drop_view(_View __base, range_difference_t<_View> __count)
-      : __cached_begin_()
-      , __count_(__count)
+      : __count_(__count)
       , __base_(_VSTD::move(__base))
     {
       _LIBCPP_ASSERT(__count_ >= 0, "count must be greater than or equal to zero.");
     }
 
-    _LIBCPP_HIDE_FROM_ABI
-    constexpr drop_view(drop_view const& __other)
-      : __cached_begin_() // Intentionally not propagating the cached begin iterator.
-      , __count_(__other.__count_)
-      , __base_(__other.__base_)
-    { }
-
-    _LIBCPP_HIDE_FROM_ABI
-    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_))
-    { }
-
-    _LIBCPP_HIDE_FROM_ABI
-    constexpr drop_view& operator=(drop_view const& __other) {
-      if constexpr (_UseCache) {
-        __cached_begin_.reset();
-      }
-      __base_ = __other.__base_;
-      __count_ = __other.__count_;
-      return *this;
-    }
-
-    _LIBCPP_HIDE_FROM_ABI
-    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;
-    }
-
     _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& requires copy_constructible<_View> { return __base_; }
     _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return _VSTD::move(__base_); }
 
     _LIBCPP_HIDE_FROM_ABI
     constexpr auto begin()
       requires (!(__simple_view<_View> &&
                   random_access_range<const _View> && sized_range<const _View>))
     {
       if constexpr (_UseCache)
-        if (__cached_begin_)
+        if (__cached_begin_.__has_value())
           return *__cached_begin_;
 
       auto __tmp = ranges::next(ranges::begin(__base_), __count_, ranges::end(__base_));
       if constexpr (_UseCache)
-        __cached_begin_ = __tmp;
+        __cached_begin_.__set(__tmp);
       return __tmp;
     }
 
     _LIBCPP_HIDE_FROM_ABI
     constexpr auto begin() const
       requires random_access_range<const _View> && sized_range<const _View>
     {
       return ranges::next(ranges::begin(__base_), __count_, ranges::end(__base_));

libcxx/include/__ranges/non_propagating_cache.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_NON_PROPAGATING_CACHE_H
+#define _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H
+
+#include <__config>
+#include <__iterator/concepts.h>        // indirectly_readable
+#include <__iterator/iterator_traits.h> // iter_reference_t
+#include <__memory/addressof.h>
+#include <concepts>                     // constructible_from
+#include <optional>
+#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
+
+// clang-format off
+
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  // __non_propagating_cache is a helper type that allows storing an optional value in it,
+  // but which does not copy the source's value when it is copy constructed/assigned to,
+  // and which resets the source's value when it is moved-from.
+  //
+  // This type is used as an implementation detail of some views that need to cache the
+  // result of `begin()` in order to provide an amortized O(1) begin() method. Typically,
+  // we don't want to propagate the value of the cache upon copy because the cached iterator
+  // may refer to internal details of the source view.
+  template<class _Tp>
+    requires is_object_v<_Tp>
+  class _LIBCPP_TEMPLATE_VIS __non_propagating_cache {
+    optional<_Tp> __value_ = nullopt;
+
+  public:
+    _LIBCPP_HIDE_FROM_ABI __non_propagating_cache() = default;
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr __non_propagating_cache(__non_propagating_cache const&) noexcept
+      : __value_(nullopt)
+    { }
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr __non_propagating_cache(__non_propagating_cache&& __other) noexcept
+      : __value_(nullopt)
+    {
+      __other.__value_.reset();
+    }
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr __non_propagating_cache& operator=(__non_propagating_cache const& __other) noexcept {
+      if (this != _VSTD::addressof(__other)) {
+        __value_.reset();
+      }
+      return *this;
+    }
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr __non_propagating_cache& operator=(__non_propagating_cache&& __other) noexcept {
+      __value_.reset();
+      __other.__value_.reset();
+      return *this;
+    }
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr _Tp& operator*() { return *__value_; }
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr _Tp const& operator*() const { return *__value_; }
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr bool __has_value() const { return __value_.has_value(); }
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr void __set(_Tp const& __value) { __value_.emplace(__value); }
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr void __set(_Tp&& __value) { __value_.emplace(_VSTD::move(__value)); }
+  };
+
+  struct __empty_cache { };
+} // namespace ranges
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H

libcxx/include/module.modulemap

module __ranges {
       module copyable_box           { private header "__ranges/copyable_box.h"          }
       module dangling               { private header "__ranges/dangling.h"              }
       module data                   { private header "__ranges/data.h"                  }
       module drop_view              { private header "__ranges/drop_view.h"             }
       module empty                  { private header "__ranges/empty.h"                 }
       module empty_view             { private header "__ranges/empty_view.h"            }
       module enable_borrowed_range  { private header "__ranges/enable_borrowed_range.h" }
       module enable_view            { private header "__ranges/enable_view.h"           }
+      module non_propagating_cache  { private header "__ranges/non_propagating_cache.h" }
       module ref_view               { private header "__ranges/ref_view.h"              }
       module size                   { private header "__ranges/size.h"                  }
       module subrange               { private header "__ranges/subrange.h"              }
       module transform_view         { private header "__ranges/transform_view.h"        }
       module view_interface         { private header "__ranges/view_interface.h"        }
     }
   }
   module ratio {

libcxx/test/libcxx/diagnostics/detail.headers/ranges/non_propagating_cache.module.verify.cpp

+// -*- 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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__ranges/non_propagating_cache.h'}}
+#include <__ranges/non_propagating_cache.h>

libcxx/test/libcxx/ranges/range.nonprop.cache/assign.copy.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
+
+// __non_propagating_cache& operator=(__non_propagating_cache const&);
+
+// ADDITIONAL_COMPILE_FLAGS: -Wno-self-assign
+
+#include <ranges>
+
+#include <cassert>
+#include <type_traits>
+#include <utility>
+
+template<bool NoexceptCopy>
+struct CopyAssignable {
+  int x;
+  constexpr explicit CopyAssignable(int i) : x(i) { }
+  CopyAssignable(CopyAssignable const&) = default;
+  constexpr CopyAssignable& operator=(CopyAssignable const& other) noexcept(NoexceptCopy) {
+    x = other.x;
+    return *this;
+  }
+  constexpr bool operator==(CopyAssignable const& other) const { return x == other.x; }
+};
+
+struct NotCopyAssignable {
+  int x;
+  constexpr explicit NotCopyAssignable(int i) : x(i) { }
+  NotCopyAssignable(NotCopyAssignable const&) = default;
+  NotCopyAssignable& operator=(NotCopyAssignable const&) = delete;
+  constexpr bool operator==(NotCopyAssignable const& other) const { return x == other.x; }
+};
+
+template <class T>
+constexpr void test() {
+  using Cache = std::ranges::__non_propagating_cache<T>;
+  static_assert(std::is_nothrow_copy_assignable_v<Cache>);
+
+  // Assign to an empty cache
+  {
+    Cache a; a.__set(T{3});
+    Cache b;
+
+    Cache& result = (b = a);
+    assert(&result == &b);
+    assert(!b.__has_value()); // make sure we don't propagate
+
+    assert(a.__has_value()); // make sure we don't "steal" from the source
+    assert(*a == T{3});      //
+  }
+
+  // Assign to a non-empty cache
+  {
+    Cache a; a.__set(T{3});
+    Cache b; b.__set(T{5});
+
+    Cache& result = (b = a);
+    assert(&result == &b);
+    assert(!b.__has_value()); // make sure we don't propagate
+
+    assert(a.__has_value()); // make sure we don't "steal" from the source
+    assert(*a == T{3});      //
+  }
+
+  // Self-assignment should not do anything (case with empty cache)
+  {
+    Cache b;
+    Cache& result = (b = b);
+    assert(&result == &b);
+    assert(!b.__has_value());
+  }
+
+  // Self-assignment should not do anything (case with non-empty cache)
+  {
+    Cache b; b.__set(T{5});
+    Cache& result = (b = b);
+    assert(&result == &b);
+    assert(b.__has_value());
+    assert(*b == T{5});
+  }
+}
+
+constexpr bool tests() {
+  test<CopyAssignable<true>>();
+  test<CopyAssignable<false>>();
+  test<NotCopyAssignable>();
+  test<int>();
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(tests());
+  tests();
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/assign.move.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
+
+// __non_propagating_cache& operator=(__non_propagating_cache&&);
+
+// ADDITIONAL_COMPILE_FLAGS: -Wno-self-assign
+
+#include <ranges>
+
+#include <cassert>
+#include <type_traits>
+#include <utility>
+
+template<bool NoexceptMove>
+struct MoveAssignable {
+  int x;
+  constexpr explicit MoveAssignable(int i) : x(i) { }
+  MoveAssignable(MoveAssignable&&) = default;
+  constexpr MoveAssignable& operator=(MoveAssignable&& other) noexcept(NoexceptMove) {
+    x = other.x;
+    other.x = -1;
+    return *this;
+  }
+};
+
+struct NotMoveAssignable {
+  int x;
+  constexpr explicit NotMoveAssignable(int i) : x(i) { }
+  NotMoveAssignable(NotMoveAssignable&&) = default;
+  NotMoveAssignable& operator=(NotMoveAssignable&&) = delete;
+};
+
+template <class T>
+constexpr void test() {
+  using Cache = std::ranges::__non_propagating_cache<T>;
+  static_assert(std::is_nothrow_move_assignable_v<Cache>);
+
+  // Assign to an empty cache
+  {
+    Cache a; a.__set(T{3});
+    Cache b;
+
+    Cache& result = (b = std::move(a));
+    assert(&result == &b);
+    assert(!b.__has_value()); // make sure we don't propagate
+    assert(!a.__has_value()); // make sure we disengage the source
+  }
+
+  // Assign to a non-empty cache
+  {
+    Cache a; a.__set(T{3});
+    Cache b; b.__set(T{5});
+
+    Cache& result = (b = std::move(a));
+    assert(&result == &b);
+    assert(!b.__has_value()); // make sure we don't propagate
+    assert(!a.__has_value()); // make sure we disengage the source
+  }
+
+  // Self-assignment should clear the cache (case with empty cache)
+  {
+    Cache b;
+
+    Cache& result = (b = std::move(b));
+    assert(&result == &b);
+    assert(!b.__has_value());
+  }
+
+  // Self-assignment should clear the cache (case with non-empty cache)
+  {
+    Cache b; b.__set(T{5});
+
+    Cache& result = (b = std::move(b));
+    assert(&result == &b);
+    assert(!b.__has_value());
+  }
+}
+
+constexpr bool tests() {
+  test<MoveAssignable<true>>();
+  test<MoveAssignable<false>>();
+  test<NotMoveAssignable>();
+  test<int>();
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(tests());
+  tests();
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/constraints.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 T>
+//  requires is_object_v<T>
+// class non-propagating-cache;
+
+#include <ranges>
+
+template<template<class...> class T, class ...Args>
+concept well_formed = requires {
+  typename T<Args...>;
+};
+
+struct T { };
+static_assert( well_formed<std::ranges::__non_propagating_cache, int>);
+static_assert( well_formed<std::ranges::__non_propagating_cache, T>);
+static_assert( well_formed<std::ranges::__non_propagating_cache, void (*)()>);
+static_assert(!well_formed<std::ranges::__non_propagating_cache, void>);
+static_assert(!well_formed<std::ranges::__non_propagating_cache, T&>);
+static_assert(!well_formed<std::ranges::__non_propagating_cache, void()>);

libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.copy.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
+
+// __non_propagating_cache(__non_propagating_cache const&);
+
+#include <ranges>
+
+#include <cassert>
+#include <type_traits>
+
+template<bool NoexceptCopy>
+struct CopyConstructible {
+  int x;
+  constexpr explicit CopyConstructible(int i) : x(i) { }
+  constexpr CopyConstructible(CopyConstructible const& other) noexcept(NoexceptCopy) : x(other.x) { }
+  CopyConstructible& operator=(CopyConstructible const&) = default;
+  constexpr bool operator==(CopyConstructible const& other) const { return x == other.x; }
+};
+
+struct NotCopyConstructible {
+  int x;
+  constexpr explicit NotCopyConstructible(int i) : x(i) { }
+  NotCopyConstructible(NotCopyConstructible const&) = delete;
+  NotCopyConstructible(NotCopyConstructible&&) = default;
+  constexpr bool operator==(NotCopyConstructible const& other) const { return x == other.x; }
+};
+
+template <class T>
+constexpr void test() {
+  using Cache = std::ranges::__non_propagating_cache<T>;
+  static_assert(std::is_nothrow_copy_constructible_v<Cache>);
+  Cache a;
+  a.__set(T{3});
+
+  // Test with direct initialization
+  {
+    Cache b(a);
+    assert(!b.__has_value()); // make sure we don't propagate
+
+    assert(a.__has_value()); // make sure we don't "steal" from the source
+    assert(*a == T{3});      //
+  }
+
+  // Test with copy initialization
+  {
+    Cache b = a;
+    assert(!b.__has_value()); // make sure we don't propagate
+
+    assert(a.__has_value()); // make sure we don't "steal" from the source
+    assert(*a == T{3});      //
+  }
+}
+
+constexpr bool tests() {
+  test<CopyConstructible<true>>();
+  test<CopyConstructible<false>>();
+  test<NotCopyConstructible>();
+  test<int>();
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(tests());
+  tests();
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/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
+
+// __non_propagating_cache();
+
+#include <ranges>
+
+#include <cassert>
+#include <type_traits>
+
+struct HasDefault { HasDefault() = default; };
+struct NoDefault { NoDefault() = delete; };
+
+template <class T>
+constexpr void test() {
+  using Cache = std::ranges::__non_propagating_cache<T>;
+  static_assert(std::is_nothrow_default_constructible_v<Cache>);
+  Cache cache;
+  assert(!cache.__has_value());
+}
+
+constexpr bool tests() {
+  test<HasDefault>();
+  test<NoDefault>();
+  test<int>();
+  test<char*>();
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(tests());
+  tests();
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.move.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
+
+// __non_propagating_cache(__non_propagating_cache&&);
+
+#include <ranges>
+
+#include <cassert>
+#include <type_traits>
+#include <utility>
+
+template<bool NoexceptMove>
+struct MoveConstructible {
+  int x;
+  constexpr explicit MoveConstructible(int i) : x(i) { }
+  constexpr MoveConstructible(MoveConstructible&& other) noexcept(NoexceptMove) : x(other.x) { other.x = -1; }
+  MoveConstructible& operator=(MoveConstructible&&) = default;
+};
+
+template <class T>
+constexpr void test() {
+  using Cache = std::ranges::__non_propagating_cache<T>;
+  static_assert(std::is_nothrow_move_constructible_v<Cache>);
+
+  // Test with direct initialization
+  {
+    Cache a;
+    a.__set(T{3});
+
+    Cache b(std::move(a));
+    assert(!b.__has_value()); // make sure we don't propagate
+    assert(!a.__has_value()); // make sure we disengage the source
+  }
+
+  // Test with copy initialization
+  {
+    Cache a;
+    a.__set(T{3});
+
+    Cache b = std::move(a);
+    assert(!b.__has_value()); // make sure we don't propagate
+    assert(!a.__has_value()); // make sure we disengage the source
+  }
+}
+
+constexpr bool tests() {
+  test<MoveConstructible<true>>();
+  test<MoveConstructible<false>>();
+  test<int>();
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(tests());
+  tests();
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/deref.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 T const& operator*() const;
+// constexpr T& operator*();
+
+#include <ranges>
+
+#include <cassert>
+
+template <class T>
+constexpr void test() {
+  using Cache = std::ranges::__non_propagating_cache<T>;
+
+  // non-const version
+  {
+    Cache cache; cache.__set(T{3});
+    T& result = *cache;
+    assert(result == T{3});
+  }
+
+  // const version
+  {
+    Cache cache; cache.__set(T{3});
+    T const& result = *static_cast<Cache const&>(cache);
+    assert(result == T{3});
+  }
+}
+
+struct T {
+  int x;
+  constexpr explicit T(int i) : x(i) { }
+  constexpr bool operator==(T const& other) const { return x == other.x; }
+};
+
+constexpr bool tests() {
+  test<T>();
+  test<int>();
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(tests());
+  tests();
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/has_value.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 bool __has_value() const;
+
+#include <ranges>
+
+#include <cassert>
+
+template <class T>
+constexpr void test() {
+  using Cache = std::ranges::__non_propagating_cache<T>;
+
+  // __has_value on an empty cache
+  {
+    Cache const cache;
+    assert(!cache.__has_value());
+  }
+
+  // __has_value on a non-empty cache
+  {
+    Cache cache; cache.__set(T{});
+    assert(cache.__has_value());
+  }
+}
+
+struct T { };
+
+constexpr bool tests() {
+  test<T>();
+  test<int>();
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(tests());
+  tests();
+  return 0;
+}