Page MenuHomePhabricator

[libc++][ranges] implement `std::ranges::set_intersection`
ClosedPublic

Authored by huixie90 on Jul 6 2022, 3:20 PM.

Details

Summary

implement std::ranges::set_intersection by reusing the classic std::set_intersection
added unit tests

Diff Detail

Event Timeline

huixie90 created this revision.Jul 6 2022, 3:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 6 2022, 3:20 PM
Herald added a subscriber: mgorny. · View Herald Transcript
huixie90 updated this revision to Diff 442700.Jul 6 2022, 3:22 PM

update review link

huixie90 updated this revision to Diff 442701.Jul 6 2022, 3:25 PM

added newline at the end of the file

huixie90 published this revision for review.Jul 6 2022, 3:25 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const requested changes to this revision.Jul 7 2022, 5:33 PM
var-const added inline comments.
libcxx/docs/Status/RangesAlgorithms.csv
57

Nit: s/set_intersenction/set_intersection/ in the patch description.

libcxx/include/__algorithm/set_intersection.h
31

I'd suggest defining a simple struct to hold the return values instead. It would be more readable than a tuple (the meaning of e.g. ret.first1 is a lot more obvious than std::get<0>(ret)) and would avoid the need for the conditional macros.

63

Instead of returning __first1 and __first2 and putting the responsibility to convert sentinels to iterators on the caller, I'd suggest calling next here and returning only __first1 (advanced to the last position), __first2 (same) and __result. I think iterator_operations.h would be a good place to hide the difference between std::next and std::ranges::next.

This revision now requires changes to proceed.Jul 7 2022, 5:33 PM
var-const added inline comments.Jul 7 2022, 5:43 PM
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp
229

This class should probably also be moved to the utility header.

273

Unused?

585

You probably need to make this function return bool and add a static assertion here, similar to how test is invoked twice above. If there's a reason not to, please add it as a comment.

huixie90 added inline comments.Jul 7 2022, 5:56 PM
libcxx/include/__algorithm/set_intersection.h
31

That was my first attempt. it turns out that in c++03 , initialising an aggregate is so hard. I can’t just return myStrucr{a,b}; I have to declare a variable and then return it. And by declaring a variable , it might be copied (NRVO is not guaranteed ). So I have to define a proper constructor for it to work for c++03

That is too much effort and I gave up and use tuple

But I still like the idea and struct with named members. what about only use struct for c++11 onward and for 03 just guard with macro

63

I did consider that. But for claasic algorithm, there is no need to call next since the iterators are discarded. std::next can be a linear complexity operation and it is wasteful to compute it when the result is not needed at all.

That is why I used this approach so that only ranges overload computes the next

What do you think?

var-const added inline comments.Jul 7 2022, 6:16 PM
libcxx/include/__algorithm/set_intersection.h
31

I'd prefer to have a three-element constructor -- it is a bit of boilerplate, but I think it's vastly preferable over the downsides of using a tuple.

63

I'd avoid using macros if at all possible. I think you could achieve a similar result by passing a template type as a tag to distinguish whether the function is invoked by the classic algorithm or the ranges algorithm (the return type would be decltype(auto) and the function could use if constexpr to return different types).

However, I think it's more trouble than it's worth. For the classic algorithm, the compiler should be able to optimize away the unused variables and their computation. In cases like this, IMO a simpler and more obviously correct implementation is higher priority than the minor performance difference (which should be optimized away in any optimized build).

huixie90 updated this revision to Diff 443184.Jul 8 2022, 2:59 AM
huixie90 marked 3 inline comments as done.

addressing feedback

libcxx/include/__algorithm/set_intersection.h
31

I used a slightly different approach now. It is combined with the other suggestion of using a "Tag" type. The "Tag" type specify what the return type should be.
So with that, I can avoid using tuple or any temporary struct at all. The "ClassicOperation" can specify the return type is just the iterator and the "RangeOperation" specifies that the return type is the set_intersection_result directly, without the need of creating any intermediate data type.

63

The macro is removed. and now the algorithm take the additional "tag" type. but with slightly different approach. the tag type dictates how to make the result. so the "classic tag" simply returns the output iterator and the "ranges tag" creates the set_intersection_result.

The benefit is to avoid writing intermediate struct (or avoid using tuple which isn't very readable). also it avoids writing the code that converts the intermediate result (temporary struct or tuple) to the final set_intersection_result

What do you think?

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp
273

it is used. see the function body of runAllIteratorPermutationsTests contains static_assert

585

Unfortunately that does not work because it exceeds the constexpr execution step limit, due to the large number of combination of types of iterators (it is a 3-dimentional cartesian product)

The workaround here is instead of having one single static_assert that tests all the combinations, in the runAllIteratorPermutationsTests function, it has lots of smaller static_assert and each of them test 2-dimentional cartesian product which is less than the step limit.
And this explains the other comment you have, where I have return true in the second layer test function.

huixie90 edited the summary of this revision. (Show Details)Jul 8 2022, 3:00 AM
var-const added inline comments.Jul 8 2022, 11:50 AM
libcxx/include/__algorithm/set_intersection.h
63

I definitely prefer this to the previous state, but I still think it's a minor optimization that isn't worth its cost in extra complexity. If these extra copies ever come up as a performance issue, we can always do the optimization later. I don't see a strong reason to avoid writing an intermediate struct -- it seems like it should be just ~6 lines of very straightforward boilerplate, mostly confined to a single internal header (but perhaps I'm missing something?).

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp
585

Thanks for explaining! Please add this rationale as a comment here.

huixie90 updated this revision to Diff 443338.Jul 8 2022, 1:23 PM
huixie90 marked 7 inline comments as done.

address feedback

var-const accepted this revision.Jul 8 2022, 2:08 PM

Thanks for addressing the feedback!

libcxx/include/__algorithm/set_intersection.h
69

Nit: move the iterators?

This revision is now accepted and ready to land.Jul 8 2022, 2:08 PM
This revision was automatically updated to reflect the committed changes.
huixie90 marked an inline comment as done.
gulfem added a subscriber: gulfem.Jul 11 2022, 8:49 AM

We started seeing a test failure in libcxx/clang_tidy.sh.cpp after this patch:

FAIL: llvm-libc++-static.cfg.in :: libcxx/clang_tidy.sh.cpp (6983 of 12107)
******************** TEST 'llvm-libc++-static.cfg.in :: libcxx/clang_tidy.sh.cpp' FAILED ********************
Script:
--
: 'RUN: at line 12';   clang-tidy /b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/libcxx/clang_tidy.sh.cpp --warnings-as-errors=* -header-filter=.* -- -Wweak-vtables -Wno-unknown-warning-option -nostdinc++ -I /b/s/w/ir/x/w/staging/llvm_build/include/c++/v1 -I /b/s/w/ir/x/w/staging/llvm_build/include/x86_64-unknown-linux-gnu/c++/v1 -I /b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/support -std=c++2b -Werror -Wall -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-noexcept-type -Wno-atomic-alignment -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings  -fno-modules
--
Exit Code: 1

Command Output (stdout):
--
$ ":" "RUN: at line 12"
$ "clang-tidy" "/b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/libcxx/clang_tidy.sh.cpp" "--warnings-as-errors=*" "-header-filter=.*" "--" "-Wweak-vtables" "-Wno-unknown-warning-option" "-nostdinc++" "-I" "/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1" "-I" "/b/s/w/ir/x/w/staging/llvm_build/include/x86_64-unknown-linux-gnu/c++/v1" "-I" "/b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/support" "-std=c++2b" "-Werror" "-Wall" "-Wextra" "-Wshadow" "-Wundef" "-Wno-unused-command-line-argument" "-Wno-attributes" "-Wno-pessimizing-move" "-Wno-c++11-extensions" "-Wno-noexcept-type" "-Wno-atomic-alignment" "-Wno-user-defined-literals" "-Wno-tautological-compare" "-Wsign-compare" "-Wunused-variable" "-Wunused-parameter" "-Wunreachable-code" "-Wno-unused-local-typedef" "-D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER" "-D_LIBCPP_ENABLE_EXPERIMENTAL" "-D_LIBCPP_DISABLE_AVAILABILITY" "-fcoroutines-ts" "-Werror=thread-safety" "-Wuser-defined-warnings" "-fno-modules"
# command output:
/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:40: error: invalid case style for parameter '__inIter1' [readability-identifier-naming,-warnings-as-errors]
  __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter)
                                       ^~~~~~~~~
                                       __in_iter1
/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:62: error: invalid case style for parameter '__inIter2' [readability-identifier-naming,-warnings-as-errors]
  __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter)
                                                             ^~~~~~~~~
                                                             __in_iter2
/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:84: error: invalid case style for parameter '__outIter' [readability-identifier-naming,-warnings-as-errors]
  __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter)
                                                                                   ^~~~~~~~~
                                                                                   __out_iter

https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8808958512552378161/overview

Thanks for the report. D129503 is tested in the CI and should fix your build failure.

Thanks for the report. D129503 is tested in the CI and should fix your build failure.

Thanks @Mordante, D129503 fixed the build issue that we were seeing about variable names.