Details
- Reviewers
Mordante var-const ldionne huixie90 - Group Reviewers
Restricted Project - Commits
- rG101d1e9b3c86: [libc++] Implement ranges::find_end, ranges::search{, _n}
rG76a76518507c: [libc++] Implement ranges::find_end, ranges::search{, _n}
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
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
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}. | |
libcxx/include/__algorithm/search.h | ||
35 | Hide from ABI? | |
60–66 | Question: why is __m1 incremented? It was not incremented in the original. | |
152–154 | 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? | |
189 | 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? | |
152 | Same comment as in search.h regarding whether this should be an else branch of the if constexpr. | |
171 | Nit: unnecessary blank line. | |
libcxx/include/__iterator/advance.h | ||
204 ↗ | (On Diff #431172) | 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 | ||
333 ↗ | (On Diff #431172) | 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 | ||
1438 | 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. |
- 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 | ||
60–66 | 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. | |
152–154 | 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. | |
189 | 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 | ||
152 | Answer is also the same. | |
libcxx/include/__iterator/advance.h | ||
204 ↗ | (On Diff #431172) | 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 | ||
333 ↗ | (On Diff #431172) | 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. |
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) In general, for c++20 code, use the real concepts instead of these tags. |
libcxx/include/__algorithm/ranges_search.h | ||
---|---|---|
100 | why <=? as the size is unsigned, is it just ==0? | |
libcxx/include/__iterator/advance.h | ||
200 ↗ | (On Diff #442520) | does it need to check _LIBCPP_HAS_NO_INCOMPLETE_RANGES too? |
201 ↗ | (On Diff #442520) | 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? |
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. |
- Address comments
libcxx/include/__algorithm/ranges_search.h | ||
---|---|---|
69 | I think you are wrong about the condition. IIUC the condition applies for every non-negative integer, because there are no non-negative integers less than zero. It's the same way that ∀x∈∅. ⊥ is true. | |
libcxx/include/__iterator/advance.h | ||
201 ↗ | (On Diff #442520) | Oops, this shouldn't have been here anymore. |
libcxx/include/__algorithm/ranges_search.h | ||
---|---|---|
48 | nit: I think it might be better to just use operator- since you've already checked it is sized_sentinel_for. If somehow we forgot to check the sized_sentinel_for concept, operator- would result in a compile time error if the type does not model it, but ranges::distance would result in a runtime linear complexity computation | |
libcxx/include/__algorithm/ranges_search_n.h | ||
65–70 | It would be nice if you can restructure the code so that this block of code can be in an else block of if constexpr, in a way that only one of the two __search_n_random_access_impl and __search_n_forward_impl would be instantiated. IIUC, with this setup, even if the code path calls __search_n_random_access_impl, the __search_n_forward_impl has still need to be instantiated because it is not guarded by if constexpr |
- Try to fix CI
libcxx/include/__algorithm/ranges_search.h | ||
---|---|---|
48 | Not necessarily. You can disable_sized_sentinel_for and are still allowed to have operator-. If we forget the check in that case our algorithm wouldn't just be slow, it would be incorrect. | |
libcxx/include/__algorithm/ranges_search_n.h | ||
65–70 | Doing that would mean that I have to either duplicate the __search_n_forward_impl call or the size check. I don't think the added complexity is justified for that potentially small increase in compilation speed. |
libcxx/docs/Status/RangesAlgorithms.csv | ||
---|---|---|
25–26 | This line can be set to done as well... |
This doesn't build over here: http://45.33.8.238/linux/81035/step_4.txt
Do you think that's a problem on my side, or is that a problem in the patch?
Hi @philnik,
This commit breaks std::search_n().
Reproducer:
#include <algorithm> #include <vector> class A { public: A(int x, int y) : x_(x), y_(y) {} int x() const { return x_; } int y() const { return y_; } private: int x_; int y_; }; bool search(const std::vector<A>& a, int value) { return std::search_n(a.begin(), a.end(), 1, value, [](const A& l, int r) { return l.x() == r; }) == a.end(); }
Compile command:
clang -std=gnu++17 -c /tmp/test.cc -o /tmp/a.o
That should compile according to https://en.cppreference.com/w/cpp/algorithm/search_n but it no longer does after this commit.
It compiles correctly with the commit before.
libcxx/include/__algorithm/iterator_operations.h | ||
---|---|---|
40 | question: why do we need another alias for ranges::advance? we could have another overload for classic one with the same name | |
libcxx/include/__algorithm/search_n.h | ||
166 | re @bgraur's bug report. this line should be static_assert(__is_callable<_BinaryPredicate, decltype(*__first), const _Tp&>::value, "BinaryPredicate has to be callable"); |