Page MenuHomePhabricator

[libc++] Implement ranges::find_end, ranges::search{, _n}
Needs ReviewPublic

Authored by philnik on Apr 20 2022, 2:52 AM.

Details

Reviewers
Mordante
var-const
ldionne
huixie90
Group Reviewers
Restricted Project

Diff Detail

Unit TestsFailed

TimeTest
1,650 mslibcxx CI C++2b > llvm-libc++-shared-cfg-in.libcxx/algorithms::robust_against_cpp20_hostile_iterators.compile.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/c++ /home/libcxx-builder/.buildkite-agent/builds/a86d4e2e972a-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/robust_against_cpp20_hostile_iterators.compile.pass.cpp --target=x86_64-unknown-linux-gnu -nostdinc++ -I /home/libcxx-builder/.buildkite-agent/builds/a86d4e2e972a-1/llvm-project/libcxx-ci/build/generic-cxx2b/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a86d4e2e972a-1/llvm-project/libcxx-ci/build/generic-cxx2b/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a86d4e2e972a-1/llvm-project/libcxx-ci/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_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -Wno-ambiguous-reversed-operator -fsyntax-only
90 mslibcxx CI Modular build > llvm-libc++-shared-cfg-in.libcxx::private_headers.verify.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/c++ /home/libcxx-builder/.buildkite-agent/builds/086c1df23e80-1/llvm-project/libcxx-ci/libcxx/test/libcxx/private_headers.verify.cpp --target=x86_64-unknown-linux-gnu -nostdinc++ -I /home/libcxx-builder/.buildkite-agent/builds/086c1df23e80-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/086c1df23e80-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/086c1df23e80-1/llvm-project/libcxx-ci/libcxx/test/support -std=c++2b -fmodules -fcxx-modules -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_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -fsyntax-only -Wno-error -Xclang -verify -Xclang -verify-ignore-unexpected=note -ferror-limit=0
3,110 mslibcxx CI Modular build > llvm-libc++-shared-cfg-in.libcxx/algorithms::robust_against_cpp20_hostile_iterators.compile.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/c++ /home/libcxx-builder/.buildkite-agent/builds/086c1df23e80-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/robust_against_cpp20_hostile_iterators.compile.pass.cpp --target=x86_64-unknown-linux-gnu -nostdinc++ -I /home/libcxx-builder/.buildkite-agent/builds/086c1df23e80-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/086c1df23e80-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/086c1df23e80-1/llvm-project/libcxx-ci/libcxx/test/support -std=c++2b -fmodules -fcxx-modules -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_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -Wno-ambiguous-reversed-operator -fsyntax-only

Event Timeline

philnik created this revision.Apr 20 2022, 2:52 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 20 2022, 2:52 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Apr 20 2022, 2:52 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 20 2022, 2:52 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik updated this revision to Diff 423861.Apr 20 2022, 3:22 AM
  • Fix some pre-C++20 code
philnik updated this revision to Diff 424157.Apr 21 2022, 5:07 AM
  • run file generation
philnik updated this revision to Diff 424569.Apr 22 2022, 12:18 PM
  • Try to fix CI

(Note: this is on my radar but I'll probably won't be able to get to it for a few days)

Is there a reason to combine these two algorithms in a single patch? Even on their own, each one is sizable, and they don't seem to be dependent on each other or even too closely related.

(Note: this is on my radar but I'll probably won't be able to get to it for a few days)

Is there a reason to combine these two algorithms in a single patch? Even on their own, each one is sizable, and they don't seem to be dependent on each other or even too closely related.

Which two do you mean? search and find_end are very similar. I'm even using the random access search implementation in find_end. If you mean search_n and the other two, they are relatively closely related still. Most of the algorithm is almost identical, although they don't share any code in the current implementation. But if you want I can put search_n into it's own PR.

philnik updated this revision to Diff 431172.May 21 2022, 12:51 PM
  • Next try
var-const requested changes to this revision.Fri, Jun 10, 3:53 PM

I apologize this review took so long. Generally looks good but there are a few missing parts to address.

libcxx/include/__algorithm/ranges_find_end.h
46

Nit: move?

47

Same optional nit re. moving here.

libcxx/include/__algorithm/ranges_search.h
66

Question: would it be possible/worthwhile to do a similar optimization for the iterator + sentinel overload? It seems it should be possible to use std::size for the case where the sentinel is the same type as the iterator, or perhaps use subrange (presuming the overhead is negligible and easily optimizable).

69

Hmm, I'd like to double-check this. IIUC, the relevant section is

{i, i + (last2 - first2)}, where i is the first iterator in the range [first1, last1 - (last2 - first2)) such that for every non-negative integer n less than last2 - first2 the condition

bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n)))) is true.

However, if last2 - first2 is zero, there exists no non-negative integer n less than that. It seems like it would mean that no such iterator i can exist and thus the algorithm should go to the next clause and return {last1, last1}.

79

Should this be in an else block of the if constexpr?

libcxx/include/__algorithm/search.h
34

Hide from ABI?

58–64

Question: why is __m1 incremented? It was not incremented in the original.

149–151

Does this need to be in an else branch for this code to be guaranteed to be eliminated? Perhaps you might need to add another if constexpr (sized_sentinel_for<_Sent1, _Iter1> || sized_sentinel_for<_Sent2, _Iter2>) { condition to wrap up the optimizations?

186

Nit: consider moving the iterators.

libcxx/include/__algorithm/search_n.h
76

Can you remove the trailing underscore from the name? (I know it's a preexistent thing)

80

Can you use using?

151

Same comment as in search.h regarding whether this should be an else branch of the if constexpr.

170

Nit: unnecessary blank line.

libcxx/include/__iterator/advance.h
203

Should this work if _Sent is a different type from _Iter? If not, perhaps static assert?

libcxx/include/__iterator/next.h
90 ↗(On Diff #431172)

Same question re. static_assert here.

libcxx/include/__iterator/reverse_iterator.h
334

I think I'd rather avoid adding these two functions. __make_begin_reverse_iterator seems to exist only for symmetry, but more importantly, the difference between language versions that is being abstracted away by __make_end_reverse_iterator is not specific to reverse iterators. How about something like

template <class _Iter, class _Sent>
decltype(auto) __end_iterator(const _Iter& __first, _Sent& __last) {
#if _LIBCPP_STD_VER > 17
    return ranges::next(__first, __last);
#else
    static_assert(is_same<_Iter, _Sent>::value, "Iterator and Sentinel have to be the same type pre-C++20");
    return __last;
#endif
}

and then use this function when creating the reverse iterators at the call site?

libcxx/include/algorithm
1300

Please update the synopsis.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp
10

Missing synopsis.

20

Please check SFINAE as well.

25

Consider a helper function to take care of both the iterator overload and the range overload (can be done in a follow-up if you prefer).

283

Should be find_end.

297

Nit: decltype(auto).

libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp
250

Should be search_n.

This revision now requires changes to proceed.Fri, Jun 10, 3:53 PM
philnik updated this revision to Diff 439724.Fri, Jun 24, 6:17 AM
philnik marked 22 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_search.h
66

This was already done in search.h. I've moved it now here, since it would have broken the classic algorithms, as I now know.

69

Yes, the non-negative integers less than zero is the empty set. Normally "all of an empty set" is trivially true.

79

No. The stuff inside the if constexpr just checks if there even can be a match or if it's trivial because the size of __range2 is zero, which means the beginning is always a match.

libcxx/include/__algorithm/search.h
58–64

Yes, that was a bug in the original. The second element of pair was never used anywhere. I don't know why __search ever returned a pair.

149–151

An else branch would be required for the guarantee, but it makes the code a lot more complicated and clang eliminated dead code even at -O0, so I don't se much of an upside.

186

I would avoid moving anything in the classic algorithm parts. It probably doesn't do much and might be a portability pit-fall.

libcxx/include/__algorithm/search_n.h
151

Answer is also the same.

libcxx/include/__iterator/advance.h
203

Doesn't apply anymore because I'm now using _IterOps.

libcxx/include/__iterator/next.h
90 ↗(On Diff #431172)

Again, doesn't apply anymore because of _IterOps.

libcxx/include/__iterator/reverse_iterator.h
334

Doesn't apply anymore, since we can't use reverse_iterator in classic algos.

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp
25

I'll do it in a follow-up.

huixie90 requested changes to this revision.Sun, Jun 26, 5:02 PM
huixie90 added a subscriber: huixie90.
huixie90 added inline comments.
libcxx/include/__algorithm/ranges_find_end.h
55–56

This looks a bug to me.

In general iterator_traits<_Iter1>::iterator_concept() doesn't exist. (this probably indicates lack of tests in this change)
There is a util in the spec ITER_CONCEPT https://eel.is/c++draft/iterator.concepts.general
but that is not even meant to use for checking the exact concept. It is only meant to be used as part of the real iterator concepts together with all syntactic constraints. Note the default is std::random_access_iterator_tag

In general, for c++20 code, use the real concepts instead of these tags.

https://godbolt.org/z/3b4hGo8h7

This revision now requires changes to proceed.Sun, Jun 26, 5:02 PM
philnik updated this revision to Diff 442520.Wed, Jul 6, 4:59 AM
philnik marked an inline comment as done.
  • Rebased
  • Address comments
huixie90 added inline comments.Wed, Jul 6, 1:41 PM
libcxx/include/__algorithm/ranges_search.h
99

why <=? as the size is unsigned, is it just ==0?

libcxx/include/__iterator/advance.h
200

does it need to check _LIBCPP_HAS_NO_INCOMPLETE_RANGES too?

201

What if this line is called on C++20 mode with the classic algorithm/classic iterator?

C++20 sentinel_for requires the sentinel to be semiregular. But C++ 17's iterator are not required to be default constructible.

what happens if you call the classic algorithm with a classic iterator that is not default constructible?

var-const accepted this revision as: var-const.Wed, Jul 6, 2:55 PM

LGTM with one remaining question.

libcxx/include/__algorithm/ranges_search.h
69

Hmm, I might be missing something (I wrote the original comment a while ago), but it seems that if last2 - first2 == 0, the current implementation would return {first1, first1}, whereas it should return {last1, last1} (assuming I'm correct that the "if no such iterator exists" cause applies). first1 isn't necessarily equal to last1 in this case, so returning {first1, first1} isn't equivalent to returning {last1, last1}, even if both are empty sets.