This is an archive of the discontinued LLVM Phabricator instance.

[libcxx] adds `std::ranges::iter_move` and `std::iter_rvalue_reference_t`
ClosedPublic

Authored by ldionne on Apr 4 2021, 11:41 PM.

Details

Summary

Implements parts of:

  • P0896R4 The One Ranges Proposal`

Depends on D99863.

Diff Detail

Event Timeline

cjdb requested review of this revision.Apr 4 2021, 11:41 PM
cjdb created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptApr 4 2021, 11:41 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
cjdb updated this revision to Diff 335733.Apr 6 2021, 11:48 PM

rebases to activate CI

miscco added inline comments.Apr 7 2021, 5:25 AM
libcxx/include/iterator
1894

I am slightly concerned about the number of overloads that are introduced and the instantiation cost, which is quite high on clang right now due to lack of memoization of concepts.

I would rather put everything in a single operator() and then use if constexpr to return the right thing.

That would enable us to simplify the concept definitions, as we do not need to exclude the previous concepts

cjdb added inline comments.Apr 7 2021, 8:47 AM
libcxx/include/iterator
1894

which is quite high on clang right now due to lack of memoization of concepts.

How long ago did Clang disable memoisation?

I would rather put everything in a single operator() and then use if constexpr to return the right thing.

I'm aware of this optimisation from GCC Concepts TS days, but I'd like to see evidence that Clang will get a significant performance boost from this too.
It'll also mean that we can't have conditional noexcept, something I'm reluctant to give up.

I can only speak from experience working on the MSVC ranges machinery. The join_view tests take about 5 min to compile.

I think we would need to call in @saar.raz or @rsmith

tcanens added a subscriber: tcanens.Apr 7 2021, 6:24 PM
tcanens added inline comments.
libcxx/include/iterator
1857

This doesn't match the standard. The "poison pill" that doesn't poison anything is there solely to clarify that we only do ADL.

1860

This is missing the "E has class or enumeration type" part of the spec. In particular, we don't want to do ADL for pointers.

1861

This is not in the spec?

1863

nor is the __can_reference here.

1878

__dereferenceable is stronger than the spec, which only requires *E to be well-formed, not that it returns something referenceable.

1894

Conditional noexcept is required for conformance since the wording uses expression-equivalent.

cjdb updated this revision to Diff 336006.Apr 7 2021, 11:00 PM
cjdb marked an inline comment as done.

fixes iter_move per @tcanens' feedback
moves __class_or_enum out of __swap scope since it's useful elsewhere

miscco added inline comments.Apr 7 2021, 11:08 PM
libcxx/include/iterator
1894

Note that we do have conditional noexcept with MSVC and I believe libstdc++

You have have a look at the _Choice machinery @CaseyCarter build. It is super helpful

1916

What is it with those strange !

cjdb marked 4 inline comments as done.Apr 8 2021, 8:31 AM
cjdb added inline comments.
libcxx/include/iterator
1894

I think it would be best to benchmark before adopting a more complex solution in the name of optimisation.

cjdb added inline comments.Apr 8 2021, 8:49 AM
libcxx/include/iterator
1916

They indicate there are non-visible code points in the text (e.g. zero-width joiners). I think it's a part of the LaTeX translation process for the standard. I'm committed to hunting all of these down, so thanks for the heads up.

cjdb updated this revision to Diff 336697.Apr 11 2021, 2:36 PM

rebases to activate CI

Just some super small things. But LGTM!

libcxx/include/concepts
451

Can't this just be = is_lvalue_reference_v<_Tp>;?

454

Same as above but for rvalue reference. Then we could get rid of __core_reference.

456

Nit: want to use your new macro here ;) ?

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
25

Given the discussion about unions and enums, want to add a super simple type traits test for unqualified lookup on both an enum and union?

96

I'm OK with this implementation. You might consider a static global to track this stuff in the future, though. Especially if you need more than a boolean. As I said, though, I'm OK with this implementation here.

139

I think this is a really good test!

187

No need to call assert here.

cjdb updated this revision to Diff 337807.Apr 15 2021, 9:53 AM

rebases to activate CI

cjdb updated this revision to Diff 337979.Apr 15 2021, 9:22 PM
cjdb marked 3 inline comments as done.
cjdb retitled this revision from [libcxx] adds `std::ranges::iter_move` and `std::iter_rvalue_reference_t to [libcxx] adds `std::ranges::iter_move` and `std::iter_rvalue_reference_t`.

@miscco's suggestion has been gnawing at me for a little while, so I checked it out with someone extremely knowledgeable about both core C++ and Clang. They encouraged benchmarking to be sure, but said they expect if constexpr to be faster than an overload set. They also said it isn't unlikely that the speed boost would be significant, and that there's a good chance the memory usage would be lower too.

With all that in mind, I think the added complexity is justified.

libcxx/include/concepts
454

Subsumption means that we need to have all three if we plan to use both __lvalue_reference and __rvalue_reference (see integral, signed_integral, and unsigned_integral). I can technically get away with just introducing __lvalue_reference, but I'd rather hedge that __rvalue_reference will be necessary down the line and get it right on the first go.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
187

Don't we want to check the run-time value as well?

With all that in mind, I think the added complexity is justified.

I actually think this if-constexpr implementation isn't too bad. While it does add some complexity, it is still readable, and much better than I expected, tbh. But please add a comment above the operator() explaining why we're using this implementation.

cjdb added a comment.Apr 15 2021, 11:55 PM

But please add a comment above the operator() explaining why we're using this implementation.

I think the explanation should go elsewhere, with a small comment directing people to that. This way we don't need to repeat the explanation for every CPO and niebloid in the library.
I'm thinking at the bottom of the doc you created; WDYT?

cjdb updated this revision to Diff 338005.Apr 15 2021, 11:56 PM

s/std/_VSTD/
s/is_noexcept/__is_noexcept/

ldionne requested changes to this revision.Apr 16 2021, 8:06 AM

I disagree with the choice to use if constexpr over overload resolution for compile-time performance reasons. I think we should continue to strive to keep the code simple. No offense, but the latest revision of this patch with if constexpr is *significantly* more complicated than a naive implementation like this (which is similar to what Chris suggested originally, but a bit simpler IMO):

namespace ranges::__iter_move {
void iter_move();

template<class _Ip>
concept __unqualified_iter_move = requires(_Ip&& __i) {
    iter_move(_VSTD::forward<_Ip>(__i));
};

// [iterator.cust.move]/1
// The name ranges​::​iter_­move denotes a customization point object. 
// The expression ranges​::​iter_­move(E) for a subexpression E is 
// expression-equivalent to:
struct __fn {
  // [iterator.cust.move]/1.1
  // iter_­move(E), if E has class or enumeration type and iter_­move(E) is a 
  // well-formed expression when treated as an unevaluated operand, [...]
  template<class _Ip>
    requires __class_or_enum<remove_cvref_t<_Ip>> && __unqualified_iter_move<_Ip>
  constexpr decltype(auto) operator()(_Ip&& __i) const 
    noexcept(iter_move(_VSTD::forward<_Ip>(__i))) 
  {
    return iter_move(_VSTD::forward<_Ip>(__i));
  }

  // [iterator.cust.move]/1.2
  // Otherwise, if the expression *E is well-formed:
  //  1.2.1 if *E is an lvalue, std​::​move(*E);
  //  1.2.2 otherwise, *E.
  template<class _Ip>
    requires !(__class_or_enum<remove_cvref_t<_Ip>> && __unqualified_iter_move<_Ip>) &&
    requires(_Ip&& __i) { *_VSTD::forward<_Ip>(__i); }
  constexpr decltype(auto) operator()(_Ip&& __i) const 
    noexcept(*_VSTD::forward<_Ip>(__i))
  {
    if constexpr (is_lvalue_reference_v<decltype(*_VSTD::forward<_Ip>(__i))>) {
      return _VSTD::move(*_VSTD::forward<_Ip>(__i));
    } else {
      return *_VSTD::forward<_Ip>(__i);
    }
  }

  // [iterator.cust.move]/1.3
  // Otherwise, ranges​::​iter_­move(E) is ill-formed.
};
} // namespace ranges::__iter_move

Bending the implementation backwards to improve compilation times when the problem is actually at the language level (overload resolution being so expensive) and at the specification level (they could have decided to go for much simpler rules with a lot less expensive SFINAE) is not the right way to go. If we want to improve the compile-times of Ranges in libc++, I'm all for finding ways to do that, but not by making our implementation significantly more complex and working around the language. Also, complexifying the implementation is not only a matter of "oh but it's hard to read". It's primarily about shipping a correct implementation, which I think is more important than shipping one that compiles fast.

Don't get me wrong, I spent like 3 years of my life trying to improve the compilation times in the C++ ecosystem by doing things like Boost.Hana and http://metaben.ch. I'm very sensitive to that problem. I just think that throwing if constexpr at the problem here is too little too late.

libcxx/include/concepts
250–253

I really think the remove_cvref_t doesn't belong here. It belongs to the callers of this concept.

Even though this concept is just a private helper, I think we should strive to make it meaningful on its own.

libcxx/include/iterator
48

Missing // Since C++20

1853

Would it make sense to add this in __ranges/iter_move.h?

1875

This is redundant since it's already included in the check for !__lvalue_iter_move<_Ip>.

1881

Not used anywhere.

1931

More strange !s

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
2

Can you please add a test with an iterator that can't be iter_moved to confirm that ranges::iter_move(E) SFINAEs away? With the if constexpr implementation, I don't think that's the case.

This revision now requires changes to proceed.Apr 16 2021, 8:06 AM
ldionne added inline comments.Apr 16 2021, 8:30 AM
libcxx/include/concepts
252

Why are we checking for union here? Is it because the spec says has class or enumeration type, and a union is technically a class type even though is_class returns false for it? @tcanens Do you know what the intent of the spec is in that regard?

Quuxplusone added inline comments.
libcxx/include/concepts
250–253

Re this and your above comment pinging @tcanens: I believe the intent of the spec is that "class [including struct and union] or enumeration types" are exactly the set of types which are allowed to...

(in the case of iter_move) ...have their own overloaded operator*. (Enums can have a free-function operator* found by ADL. Primitive types cannot have an overloaded operator* at all.)

(in the case of swap) ...have their own free-function swap that might reasonably do something different from the normal swap. (Pointer types can have associated namespaces which end up producing associated swap functions, but those swap functions aren't semantically allowed to do anything except swap the pointers. If this weren't true, our strategy of specializing std::sort for pointer types would be non-conforming. https://godbolt.org/z/G8d6GKbME )

It might be reasonable to rename this concept/trait to something like __causes_adl — but I think __class_or_enum is reasonable too, in that it matches the Standardese term-of-art for "the kind of thing that suffers from ADL." I also think, under this rationale, it makes perfect sense to want to move the cvref-dequalification into the concept/trait itself, because the cvref-qualification of a type doesn't have any effect on whether it suffers from ADL.

Regarding if constexpr-with-a-single-overload vs normally written code: I just spoke to Chris offline and I'm going to try and chat with Casey about his previous experience with that. I don't want us to make our implementation super complex unless we know for sure it will be a serious problem, and that using if constexpr is going to make a significant difference. I think it is also possible to try to be conscious about reducing the number of overloads and the complexity of the implementation without necessarily going all the way and enforcing a single overload all the time. Let's put this on standby for a few hours until I've gotten more information.

ldionne commandeered this revision.Apr 16 2021, 11:58 AM
ldionne edited reviewers, added: cjdb; removed: ldionne.

After talking to Chris, Casey and Richard offline, I believe the following approach is the most sensible:

  1. Write things as simply as possible, without purposefully pessimizing compile-times upfront
  2. Try to be cognizant of the fact that overloads are not cheap, especially in the presence of complicated SFINAE (which is pretty much all the time with concepts)
  3. Go back with more field experience and optimize the compile-time of the implementation based on what we see is truly slowing things down

That way, we're not going to cargo-cult one way of doing things before we have actual data to justify an approach. We'll also be able to optimize just the things that matter in practice, which is far from clear at this early stage.

Based on offline discussion with Chris, I'm going to commandeer this now to go back to the pre constexpr if approach.

ldionne updated this revision to Diff 338215.Apr 16 2021, 1:32 PM
ldionne marked 11 inline comments as done.

Apply reviewer's comments.

ldionne added inline comments.Apr 16 2021, 1:32 PM
libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
187

Yes, I think we do. I'm leaving the assert in place.

zoecarver added inline comments.Apr 16 2021, 3:28 PM
libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
187

Why do we want to check the runtime value? The end of check_iter_move is return true; we're not "checking" anything.

cjdb requested changes to this revision.Apr 17 2021, 5:25 PM
cjdb added inline comments.
libcxx/include/__iterator/iter_move.h
60

This noexcept specifier doesn't account for a throwing move.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
187

Sure, but the contents of check_iter_move need to be evaluated at both compile-time and run-time.

This revision now requires changes to proceed.Apr 17 2021, 5:25 PM
zoecarver added inline comments.Apr 17 2021, 5:36 PM
libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
187

I agree. But why can't you just call check_iter_move normally? Why do you need the assert?

libcxx/include/__iterator/iter_move.h
60

"move doesn't move," and this function returns decltype(auto), so I think we're okay here. This function either returns an rvalue reference in the if, or URVOs a prvalue in the else.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
187
cjdb added inline comments.Apr 17 2021, 7:15 PM
libcxx/include/__iterator/iter_move.h
60

@rsmith is the one who pointed it out to me, so I'm not so sure. Granted, the tests cover seem to be passing, but a looking over them again makes me realise I only tested noexcept specifiers in one direction. We'll need to plug those holes at the very least.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
187

Oh, you're talking about literally removing assert, not what's inside it. I'm okay with that!

tcanens added inline comments.Apr 17 2021, 8:33 PM
libcxx/include/concepts
252

More or less what Arthur said below. There is no reason to treat unions differently from other classes in the contexts at issue.

ldionne marked 8 inline comments as done.Apr 19 2021, 7:31 AM
ldionne added inline comments.
libcxx/include/__iterator/iter_move.h
60

This function either returns an rvalue reference in the if, or URVOs a prvalue in the else.

That was my reasoning when writing that.

but a looking over them again makes me realise I only tested noexcept specifiers in one direction. We'll need to plug those holes at the very least.

Sorry, I'm not quite following, what do you mean by testing noexcept specifiers only in one direction? I'll add the test coverage, but I'd like to understand what's missing.

cjdb added inline comments.Apr 19 2021, 10:08 AM
libcxx/include/__iterator/iter_move.h
60

The tests in this commit exclusively assume noexcept(std::ranges::iter_move(lvalue)) == false and noexcept(std::ranges::iter_move(rvalue)) == true. That was an oversight in my design testing (and what I get for not knowing how to do TDD properly in 2019).

cjdb accepted this revision.Apr 19 2021, 2:11 PM

LGTM pending test update

This revision now requires review to proceed.Apr 19 2021, 2:11 PM
cjdb added inline comments.Apr 20 2021, 8:49 AM
libcxx/include/__iterator/iter_move.h
46

Please make sure all overloads are [[nodiscard]] before submitting too.

ldionne updated this revision to Diff 338994.Apr 20 2021, 2:06 PM
ldionne marked 3 inline comments as done.

Address review comments.

ldionne updated this revision to Diff 338995.Apr 20 2021, 2:06 PM

Fix stray comment.

ldionne accepted this revision as: Restricted Project.Apr 20 2021, 2:07 PM

Will ship it once CI is green per agreement with reviewers.

This revision is now accepted and ready to land.Apr 20 2021, 2:07 PM
cjdb accepted this revision.Apr 20 2021, 2:08 PM

🚢

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.nodiscard.verify.cpp
36

This is nice :-)

A few comments, sorry. Nothing blocking, though, so feel free to commit.

libcxx/include/__iterator/iter_move.h
16

Why are these (or at least why does it appear that these) are both importing __class_or_enum? (I think only the latter should have the comment.)

50

Non blocking nit: _LIBCPP_NOEXCEPT_RETURN?

libcxx/include/concepts
445

Non blocking, nit: _LIBCPP_HAS_NO_RANGES

libcxx/include/iterator
439

I'd rather have this be such that we can import any libc++ header and it will guard against the correct stdlib version, etc. internally. This is how we do it for other "versioning" features, I think we should do it with this, too.

In other words, I'd rather have the _LIBCPP_HAS_NO_RANGES check inside of iter_move.h.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
24

This header is only used in one place, right? At least, I'd like to see it in this directory and not the parent one. But I don't see any reason it can't just be inlined into this file, if nothing else is using it.

187

Heh, sorry I wan't clear. Yes, that's what I mean :)

cjdb added inline comments.Apr 20 2021, 2:47 PM
libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
24

The intention is for it to be shared with iter_swap tests.

zoecarver added inline comments.Apr 20 2021, 3:06 PM
libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.move/iter_move.pass.cpp
24

Fair enough. In that case, disregard my comment.

cjdb added inline comments.Apr 20 2021, 8:51 PM
libcxx/include/iterator
439

+10. This is already causing me issues downstream where I only import headers that expose the necessary names.

ldionne marked 10 inline comments as done.Apr 21 2021, 8:12 AM
ldionne added inline comments.
libcxx/include/__iterator/iter_move.h
16

It was a typo, fixed.

50

I'm really not a big fan of that macro, and it's only defined locally when defining __apply_tuple_impl. Not doing.

libcxx/include/concepts
445

Actually, this line isn't touched anymore after rebase, so not changing anything.

This revision was landed with ongoing or failed builds.Apr 21 2021, 8:32 AM
This revision was automatically updated to reflect the committed changes.
ldionne marked 3 inline comments as done.