[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

34

Could we constrain this further?

35

Indent.

38

This name should be mangled.

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

20

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

34

Why should we constrain this further?

38

__uglified?

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

20

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

35

@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

34

Not sure what I was thinking here, sorry.

38

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

50 ↗

(On Diff #360154)

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

50 ↗

(On Diff #360154)

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

50 ↗

(On Diff #360154)

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

libcxx/include/CMakeLists.txt

set(files
   __memory/uninitialized_algorithms.h
   __memory/unique_ptr.h
   __mutex_base
   __node_handle
   __nullptr
   __ranges/access.h
   __ranges/concepts.h
   __ranges/enable_borrowed_range.h
+  __ranges/non_propagating_cache.h
   __ranges/view.h
   __ranges/size.h
   __split_buffer
   __std_stream
   __string
   __threading_support
   __tree
   __tuple

libcxx/include/__ranges/non_propagating_cache.h

+// -*- C++ -*-
+//===--------------------- __ranges/concepts.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 _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 <concepts>                     // constructible_from
+#include <memory>
+#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 {
+  template<class _Tp, bool __enable_cache>
+  requires is_object_v<_Tp>
+  struct __non_propagating_cache : optional<_Tp> {
+    using optional<_Tp>::optional;
+    inline static constexpr bool cache_enabled = true;
+
+    constexpr __non_propagating_cache(const __non_propagating_cache&) noexcept {}
+
+    constexpr __non_propagating_cache(__non_propagating_cache&& __other) noexcept {
+      __other.reset();
+    }
+
+    constexpr __non_propagating_cache& operator=(const __non_propagating_cache& __other) noexcept {
+      if (_VSTD::addressof(__other) != this) {
+        optional<_Tp>::reset();
+      }
+
+      return *this;
+    }
+
+    constexpr __non_propagating_cache& operator=(__non_propagating_cache&& __other) noexcept {
+      optional<_Tp>::reset();
+      __other.reset();
+      return *this;
+    }
+  };
+
+  template<class _Tp>
+  requires is_object_v<_Tp>
+  struct __non_propagating_cache<_Tp, false> {
+    inline static constexpr bool cache_enabled = false;
+  };
+} // 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/test/libcxx/ranges/range.nonprop.cache/cache_disabled.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
+
+// std::ranges::__non_propagating_cache<T, false>
+
+#include <__ranges/non_propagating_cache.h>
+
+#include <array>
+#include <type_traits>
+
+static_assert(std::is_empty_v<std::ranges::__non_propagating_cache<std::array<int, 10>, false> >);
+static_assert(std::is_empty_v<std::ranges::__non_propagating_cache<std::array<int, 10>::iterator, false> >);

libcxx/test/libcxx/ranges/range.nonprop.cache/copy_assign.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::operator=(__non_propagating_cache const&);
+
+#include <__ranges/non_propagating_cache.h>
+
+#include <array>
+#include <cassert>
+
+#include "test_macros.h"
+
+constexpr bool check_copy_assign() {
+  auto x = std::ranges::__non_propagating_cache<std::array<int, 5>, true>({0, 1, 2, 3, 4});
+  auto y = std::ranges::__non_propagating_cache<std::array<int, 5>, true>({5, 6, 7, 8, 9});
+  x = y;
+  assert(!x.has_value());
+  assert(y.has_value());
+  assert((y.value() == std::array<int, 5>{5, 6, 7, 8, 9}));
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(std::is_nothrow_copy_assignable_v<std::ranges::__non_propagating_cache<std::array<int, 10>, true> >);
+  static_assert(check_copy_assign());
+  check_copy_assign();
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/copy_ctor.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/non_propagating_cache.h>
+
+#include <array>
+#include <cassert>
+
+#include "test_macros.h"
+
+constexpr bool check_copy_ctor() {
+  auto x = std::ranges::__non_propagating_cache<std::array<int, 5>, true>({0, 1, 2, 3, 4});
+  auto y = x;
+  assert(x.has_value());
+  assert((x.value() == std::array<int, 5>{0, 1, 2, 3, 4}));
+  assert(!y.has_value());
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(std::is_nothrow_copy_constructible_v<std::ranges::__non_propagating_cache<std::array<int, 10>, true> >);
+  static_assert(check_copy_ctor());
+  check_copy_ctor();
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/move_assign.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::operator=(__non_propagating_cache&&);
+
+#include <__ranges/non_propagating_cache.h>
+
+#include <array>
+#include <cassert>
+#include <utility>
+
+#include "test_macros.h"
+
+constexpr bool check_move_assign() {
+  auto x = std::ranges::__non_propagating_cache<std::array<int, 5>, true>({0, 1, 2, 3, 4});
+  auto y = std::ranges::__non_propagating_cache<std::array<int, 5>, true>({5, 6, 7, 8, 9});
+  x = std::move(y);
+  return !x && !y;
+}
+
+int main(int, char**) {
+  static_assert(std::is_nothrow_move_assignable_v<std::ranges::__non_propagating_cache<std::array<int, 10>, true> >);
+  static_assert(check_move_assign());
+  assert(check_move_assign());
+  return 0;
+}

libcxx/test/libcxx/ranges/range.nonprop.cache/move_ctor.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/non_propagating_cache.h>
+
+#include <array>
+#include <cassert>
+#include <utility>
+
+#include "test_macros.h"
+
+constexpr bool check_move_ctor() {
+  auto x = std::ranges::__non_propagating_cache<std::array<int, 5>, true>({0, 1, 2, 3, 4});
+  auto y = std::move(x);
+  return !x && !y;
+}
+
+int main(int, char**) {
+  static_assert(std::is_nothrow_move_constructible_v<std::ranges::__non_propagating_cache<std::array<int, 10>, true> >);
+  static_assert(check_move_ctor());
+  assert(check_move_ctor());
+  return 0;
+}