This is an archive of the discontinued LLVM Phabricator instance.

[libc++][spaceship] Implement `operator<=>` for `vector`
ClosedPublic

Authored by H-G-Hristov on Aug 19 2022, 4:52 PM.

Details

Summary

Implements part of P1614R2 "The Mothership has Landed"

Depends on D150188

Diff Detail

Event Timeline

avogelsgesang created this revision.Aug 19 2022, 4:52 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 19 2022, 4:52 PM
Herald added a subscriber: yaxunl. · View Herald Transcript
avogelsgesang requested review of this revision.Aug 19 2022, 4:52 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 19 2022, 4:52 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript

update review link

improve test cases

avogelsgesang planned changes to this revision.Nov 19 2022, 8:59 PM

needs to be adjusted to use the still-to-be-introduced test utilities from https://reviews.llvm.org/D132312 is done

add missing _LIBCPP_HIDE_FROM_ABI; use new test utility

Incorporate feedback received for similar review (list instead of vector; https://reviews.llvm.org/D132312)

I had a quick look and no real comments. Can you fix the CI? I prefer to review the changes after a CI run.

Remove trailing whitespace (hopefully fixes CI)

Guard against ADL

avogelsgesang planned changes to this revision.Feb 28 2023, 6:15 AM

still need to fix CI

@H-G-Hristov unfortunately, I don't know when I will find time to come back to this (and https://reviews.llvm.org/D132265). Feel free to take this over, if you are blocked by it

@H-G-Hristov unfortunately, I don't know when I will find time to come back to this (and https://reviews.llvm.org/D132265). Feel free to take this over, if you are blocked by it

Thank you. I'll probably take them over then if you haven't finished them before I get the time.

H-G-Hristov commandeered this revision.Apr 23 2023, 4:55 AM
H-G-Hristov added a reviewer: avogelsgesang.
  • [libc++][spaceship] Implement operator<=> for vector
  • Fixes, incl. a change to lexicographical_compare_three_way to fix std::vector<bool> comparision operators support
avogelsgesang added inline comments.Apr 25 2023, 4:40 PM
libcxx/include/__algorithm/lexicographical_compare_three_way.h
106 ↗(On Diff #516185)

I fear the actual issue is that `__three_way_comp_ref_type is currently buggy, and this change here only masks the issue.

I think the changes

   template <class _Tp, class _Up>
-  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y) {
+  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(const _Tp& __x, const _Up& __y) {

and

 // Pass the comparator by lvalue reference. Or in debug mode, using a
 // debugging wrapper that stores a reference.
-#  ifndef _LIBCPP_ENABLE_DEBUG_MODE
+#  ifdef _LIBCPP_ENABLE_DEBUG_MODE

are required. Not sure if sufficient, though

Addressed review comments

H-G-Hristov marked an inline comment as done.Apr 30 2023, 1:42 AM
H-G-Hristov added inline comments.
libcxx/include/__algorithm/lexicographical_compare_three_way.h
106 ↗(On Diff #516185)

I think it's good now. Thank you for the review/tip. I don't understand what's going on with the CI at the moment but build the local build of the latest revision is fine.

Mordante added inline comments.Apr 30 2023, 6:11 AM
libcxx/docs/Status/SpaceshipProjects.csv
38

Did you validate this output looks good?

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp
55 ↗(On Diff #518145)

lx and tx are identical.

H-G-Hristov marked an inline comment as done.
  • Rebased and addressed comments
H-G-Hristov marked an inline comment as done.EditedApr 30 2023, 11:54 PM

@Mordante Thank you for the review.

libcxx/docs/Status/SpaceshipProjects.csv
38

I use a VSCode extension to preview the tables. It looks good. Text is ordered on two separate lines. I can remove myself. I don't care about credit. I was curious how it can be done.
Is there another easy/more correct way to validate?

  • Addressed review comment
philnik added a subscriber: philnik.May 4 2023, 3:49 PM

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

libcxx/include/__algorithm/three_way_comp_ref_type.h
31 ↗(On Diff #519221)

Why is this change needed?

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp
59 ↗(On Diff #519221)

Maybe also test one empty and one with {false}?

H-G-Hristov marked an inline comment as done.
  • Addressed comments
H-G-Hristov marked 2 inline comments as done.May 5 2023, 6:23 AM

@philnik Thank you for the review!

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(
libcxx/include/__algorithm/three_way_comp_ref_type.h
31 ↗(On Diff #519221)

Without it the build fails.

@philnik Thank you for the review!

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

H-G-Hristov marked an inline comment as done.May 5 2023, 9:36 AM

@philnik Thank you for the review!

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

Sorry, I think I confused you. The actual problem is in the compare function, the last parameter of: :

note: candidate template ignored: substitution failure [with _InputIterator1 = std::__bit_iterator<std::vector<bool>, true, 0>, _InputIterator2 = std::__bit_iterator<std::vector<bool>, true, 0>, _Cmp = std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>]: no matching function for call to object of type 'std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>'
_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(

@philnik Thank you for the review!

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

@philnik Thank you for the review!

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

Sorry, I think I confused you. The actual problem is in the compare function, the last parameter of: :

note: candidate template ignored: substitution failure [with _InputIterator1 = std::__bit_iterator<std::vector<bool>, true, 0>, _InputIterator2 = std::__bit_iterator<std::vector<bool>, true, 0>, _Cmp = std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>]: no matching function for call to object of type 'std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>'
_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(

@philnik Thank you for the review!

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

Sorry, I think I confused you. The actual problem is in the compare function, the last parameter of: :

note: candidate template ignored: substitution failure [with _InputIterator1 = std::__bit_iterator<std::vector<bool>, true, 0>, _InputIterator2 = std::__bit_iterator<std::vector<bool>, true, 0>, _Cmp = std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>]: no matching function for call to object of type 'std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>'
_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(

IIUC the problem is that __bit_iterator::operator* returns an object instead of a reference, which can't bind to an lvalue reference. If we use perfect forwarding that should fix the problem?

  • Use std::forward instead of move.
  • Everything &&

IIUC the problem is that __bit_iterator::operator* returns an object instead of a reference, which can't bind to an lvalue reference. If we use perfect forwarding that should fix the problem?

Could you please confirm if I understand correctly: I am supposed to perfectly forward the arguments to std::__lexicographical_compare_three_way_fast_path something like that:

return std::__lexicographical_compare_three_way_fast_path(
    std::forward<_InputIterator1>(__first1),
    std::forward<_InputIterator1>(__last1),
    std::forward<_InputIterator2>(__first2),
    std::forward<_InputIterator2>(__last2),
    __wrapped_comp_ref);

No, that still wasn't enough. The compilation fails without changes to LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y)'s signature. There was ways an issue with the 5th parameter (for the record I tried forward, move).
In the current revision I changed all references to rvalue references and applied forward to the iterators . I admit that I am not quite sure if that's the correct approach.

IIUC the problem is that __bit_iterator::operator* returns an object instead of a reference, which can't bind to an lvalue reference. If we use perfect forwarding that should fix the problem?

Could you please confirm if I understand correctly: I am supposed to perfectly forward the arguments to std::__lexicographical_compare_three_way_fast_path something like that:

return std::__lexicographical_compare_three_way_fast_path(
    std::forward<_InputIterator1>(__first1),
    std::forward<_InputIterator1>(__last1),
    std::forward<_InputIterator2>(__first2),
    std::forward<_InputIterator2>(__last2),
    __wrapped_comp_ref);

No, that still wasn't enough. The compilation fails without changes to LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y)'s signature. There was ways an issue with the 5th parameter (for the record I tried forward, move).
In the current revision I changed all references to rvalue references and applied forward to the iterators . I admit that I am not quite sure if that's the correct approach.

I meant that you should perfect-forward the arguments in __debug_three_way_comp::operator(). i.e. std::forward the arguments to __comp_. The std::forwards you are currently doing in the calls are essentially just std::moves, since the arguments are prvalue types.

A few more comments. I want to have a short look at the final version especially the answers to some of @philnik's remarks.

libcxx/include/__algorithm/lexicographical_compare_three_way.h
37 ↗(On Diff #520053)

I think it would be better to have the changes to this file and the changes directly related to it in a separate commit.

If you feel strongly about not doing that, then mention these changes in the commit message.

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp
12 ↗(On Diff #520053)

The synopsis should use the synopsis for the vector<bool> specialization.

libcxx/test/support/test_container_comparisons.h
65 ↗(On Diff #520053)

All changes in this file are just NFC cleanups right? If so I prefer to remove them from this patch and commit them separately.
(That commit doesn't need a review.)

  • Addressed comments
H-G-Hristov planned changes to this revision.May 8 2023, 11:50 PM
H-G-Hristov marked 2 inline comments as done.May 8 2023, 11:54 PM

@Mordante Thank you for the suggestions!

libcxx/include/__algorithm/lexicographical_compare_three_way.h
37 ↗(On Diff #520053)

I agree. I'll do that.

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp
12 ↗(On Diff #520053)

To my understanding there isn't a synopsis specific to vector<bool> for operator<=>. I added // class vector<bool>. I hope that's what you mean.

H-G-Hristov marked an inline comment as done.
  • Addressed comments
H-G-Hristov edited the summary of this revision. (Show Details)May 20 2023, 8:41 AM

Try to fix CI

Mordante accepted this revision.May 22 2023, 10:36 AM

LGTM when the CI passes.

This revision is now accepted and ready to land.May 22 2023, 10:36 AM

LGTM when the CI passes.

Thank you for the review. This one now passes but it still needs the stacked change to be completed/approved.

H-G-Hristov marked an inline comment as done.May 29 2023, 1:03 AM
This revision was automatically updated to reflect the committed changes.