This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by ldionne on May 8 2021, 6:58 PM.

Details

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.

Diff Detail

Event Timeline

cjdb created this revision.May 8 2021, 6:58 PM
cjdb requested review of this revision.May 8 2021, 6:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 8 2021, 6:58 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
cjdb added inline comments.May 8 2021, 7:00 PM
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 added inline comments.May 8 2021, 7:07 PM
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 updated this revision to Diff 343887.May 8 2021, 9:42 PM

rebases to activate CI

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 updated this revision to Diff 343935.May 9 2021, 2:05 PM

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.

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

cjdb marked 2 inline comments as done.May 9 2021, 4:11 PM

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 added inline comments.May 10 2021, 9:01 AM
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 added inline comments.May 10 2021, 9:23 AM
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?

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 updated this revision to Diff 351071.Jun 9 2021, 11:01 PM

rebases to activate CI

cjdb updated this revision to Diff 351577.Jun 11 2021, 4:32 PM

rebases to check CI

cjdb updated this revision to Diff 351594.Jun 11 2021, 5:06 PM

adjusts module map

cjdb updated this revision to Diff 352531.Jun 16 2021, 1:11 PM

rebases to activate CI

cjdb updated this revision to Diff 352789.Jun 17 2021, 10:51 AM
  • fixes header
  • ensures that __non_propagating_cache is derived from std::optional when it's in cache mode

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 added inline comments.Jun 19 2021, 10:26 PM
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.

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 requested changes to this revision.Jun 21 2021, 8:45 AM
ldionne added inline comments.
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.

This revision now requires changes to proceed.Jun 21 2021, 8:45 AM
cjdb added inline comments.Jun 21 2021, 9:43 AM
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 commandeered this revision.Jul 19 2021, 12:09 PM
ldionne edited reviewers, added: cjdb; removed: ldionne.

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

ldionne updated this revision to Diff 359954.Jul 19 2021, 4:35 PM

Take over.

ldionne updated this revision to Diff 360140.Jul 20 2021, 8:03 AM

Hopefully fix -Wself-assign issue on GCC and Clang

ldionne updated this revision to Diff 360154.Jul 20 2021, 8:44 AM

Fix typo in ADDITIONAL_COMPILE_FLAGS: markup.

Mordante added inline comments.Jul 20 2021, 12:13 PM
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 __.

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 added inline comments.Jul 20 2021, 1:01 PM
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 marked 15 inline comments as done.Jul 21 2021, 8:57 AM
ldionne added inline comments.
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 updated this revision to Diff 360488.Jul 21 2021, 8:59 AM
ldionne marked 2 inline comments as done.

Address review comments

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 marked an inline comment as done.Jul 21 2021, 9:08 AM
ldionne added inline comments.
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 accepted this revision as: Mordante.Jul 21 2021, 11:32 AM

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.

cjdb accepted this revision.Jul 22 2021, 11:19 AM
ldionne accepted this revision as: Restricted Project.Jul 22 2021, 11:29 AM
ldionne marked an inline comment as done.
This revision is now accepted and ready to land.Jul 22 2021, 11:29 AM
This revision was automatically updated to reflect the committed changes.