Details
- Reviewers
jdoerfert philnik ldionne - Group Reviewers
Restricted Project - Commits
- rGc3648f37d0ed: [libc++][ranges] Implement `ranges::to`.
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
| libcxx/include/string | ||
|---|---|---|
| 1932–1933 ↗ | (On Diff #505896) | Doing so breaks string tests. |
| libcxx/test/std/ranges/range.utility/range.utility.conv/to_std_containers.pass.cpp | ||
| 222 | Sorry about that! | |
Address more feedback.
| libcxx/include/__ranges/to.h | ||
|---|---|---|
| 98 | Interestingly enough, LWG 3733 (https://cplusplus.github.io/LWG/issue3733) has changed this condition since the original paper to not use the cpp17-input-iterator concept. Updated. | |
| libcxx/test/std/containers/associative/from_range_associative_containers.h | ||
| 208–210 ↗ | (On Diff #512487) | .data() would return a const pointer, so the iterator types would have to be parametrized on const T* instead of just T*. It's doable but I don't think it will be better than the current state. |
| 259 ↗ | (On Diff #512487) | Added simple tests. I made a separate test for each set class and each map class -- all my attempts to generalize turned out to be more trouble than they were worth. |
| libcxx/test/std/ranges/range.utility/range.utility.conv/to.pass.cpp | ||
| 49 | Sorry, but at this point I need a reminder on why this is ill-formed. | |
| libcxx/test/std/ranges/range.utility/range.utility.conv/to_std_containers.pass.cpp | ||
| 154 | There's a test below (the one that uses all_containers) that uses std::pair to be able to convert between map and non-map containers. The specialization is necessary to be able to use std::pair with unordered_set/multiset. Added a comment to that effect. | |
Note: I finished the tests (at least in the amount that I had planned originally). I still need to fix the CI.
| libcxx/include/__ranges/to.h | ||
|---|---|---|
| 99 | Thanks for pointing this out! Added tests. | |
| libcxx/include/deque | ||
| 604 ↗ | (On Diff #503872) | I did a very quick benchmark: template <class Container, class GenInputs>
void BM_ConstructFromRangeT(benchmark::State& st, Container, GenInputs gen) {
auto in = gen(st.range(0));
benchmark::DoNotOptimize(&in);
while (st.KeepRunning()) {
Container c(std::from_range, in);
DoNotOptimizeData(c);
}
}
BENCHMARK_CAPTURE(BM_ConstructFromRangeT,
deque_int,
std::deque<int>{},
getRandomIntegerInputs<int>)->Arg(5140480 * 10);
BENCHMARK_CAPTURE(BM_ConstructFromRangeT,
deque_string,
std::deque<std::string>{},
getRandomStringInputs)->Arg(1024 * 10);
BENCHMARK_MAIN();I ran it with and without the optimization 5 times and took the average (going by the wall time but the difference with CPU time is negligible): Test Time, ns ints, with optimization 34045820 ints, no optimization 67872734 strings, with optimization 2057941 strings, no optimization 2000087 So for strings, the difference is negligible, presumably because the timings are dominated by copying (in fact, the optimized version is 3% slower, but I'd chalk it up to random fluctuations), but for ints the optimized version is 2x faster, making it worthwhile to keep. |
| libcxx/test/std/ranges/range.utility/range.utility.conv/to.pass.cpp | ||
| 49 | @ldionne Tagging this comment so that it doesn't get drowned out among the many other comments. :) | |
Did you upload the wrong patch?
| libcxx/include/deque | ||
|---|---|---|
| 70 ↗ | (On Diff #513950) | throughout |
| 668–674 ↗ | (On Diff #513950) | IMO it would be better to do this optimization in __assign_whatever to avoid having slightly different versions of this in different places. |
| 792 ↗ | (On Diff #513950) | This looks completely wrong. Did you mean to use insert_range? I'm also not convinced this can be implemented this way. prepend_range has much stronger exception guarantees than insert. If we provide strong enough exception guarantees inside insert (which I don't think is the case), please add a comment. |
| 970 ↗ | (On Diff #513950) | Why not _Iter and _Sent like we use elsewhere? |
Mostly finish tests for sequence containers.
Still TODO for sequence containers:
- test basic_string::replace_with_range;
- test vector with and without reallocation.
@philnik Sorry, I uploaded just the last commit from my local branch last time. Should be fixed now.
| libcxx/include/deque | ||
|---|---|---|
| 70 ↗ | (On Diff #513950) | This file uses this style, without since. I deliberately keep it consistent. |
| 668–674 ↗ | (On Diff #513950) | The internal __assign functions don't have access to the range, only the iterators. It's possible to have a range where size takes constant time while distance is linear. |
| 792 ↗ | (On Diff #513950) | Yes, it should be insert_range. Where are the exception guarantees you're referring to specified? I was looking at https://eel.is/c++draft/deque.modifiers where insert, insert_range and prepend_range are grouped together and share the same remarks about exception safety. |
| libcxx/include/__ranges/to.h | ||
|---|---|---|
| 72 | Re __always_false: I don't think so, unless we have similar uses for the same thing. I would move it to a separate header when/if we have other use cases. | |
| libcxx/include/deque | ||
| 825 ↗ | (On Diff #515224) | Here, you basically want to compute the distance, but also the last iterator (not sentinel) as you're doing it. Then you can pass down that information to __insert_bidirectional to avoid having to ever re-compute the end iterator, which would require re-walking the whole range. It strikes me that template< std::input_or_output_iterator I, std::sentinel_for<I> S > constexpr void advance( I& i, S bound ); should really return std::iter_difference_t representing the number of times it incremented the iterator to get to the bound. Then you'd do something like: auto __last = ranges::begin(__range); auto __n = std::advance(__last, std::end(__range)); // now you have an iterator representation of your sentinel AND the knowledge of the size of the range, which you can pass down to the function Edit: Scratch everything above. There's a good reason why std::ranges::advance doesn't return the iter_difference_t: it would prevent the assignment optimization from happening when the sentinel is an iterator. I guess I don't have a great solution for this then. If you can think of one, good, otherwise I guess we can settle for computing the distance twice in some cases. |
| 1292–1294 ↗ | (On Diff #515224) | I think we want this here: // no need to compute `__m` here anymore auto __rest = std::__copy_n<_ClassicAlgPolicy>(__f, size(), begin()).first; __append_with_size(__rest, __n - size()); |
| 1297 ↗ | (On Diff #515224) | __erase_to_end(std::__copy_n<_ClassicAlgPolicy>(__f, __n, begin()).second); And then you don't need to take _Sentinel __l as an input anymore, and that saves you from having to compute std::next above. |
| 1823 ↗ | (On Diff #515224) | This does have the same problem that we're re-walking the whole input sequence again in some cases, let's see if there's a solution for that. |
| libcxx/include/forward_list | ||
| 873 ↗ | (On Diff #515224) | You could consider moving this back below to minimize the diff, but I can see what you did here and I think it's fine too. |
| libcxx/include/queue | ||
| 478 ↗ | (On Diff #503872) | What does the spec say? I think there's blanket wording based on the name of the template parameters that mean that something called Allocator needs to be a valid allocator. IDK whether it applies to this specific CTAD. I think it is https://eel.is/c++draft/container.requirements#container.reqmts-69. I suspect it is needed. If so, we almost certainly have tests for this in e.g. std::vector, and we should mirror that here. |
| libcxx/test/std/ranges/range.utility/range.utility.conv/to.pass.cpp | ||
| 49 | This comment was originally attached to using ContainerT = int; static_assert(!std::ranges::view<ContainerT>); static_assert(HasTo<ContainerT, InputRange>); but Phabricator kind of messed things up. I think https://eel.is/c++draft/range.utility.conv#to-2.3 makes that ill-formed. Personally, I feel like we could simply drop that test. The similar test for HasTo<test_view<...>> is relevant though, cause it tests the requires (!view<C>) on ranges::to (but we might want to add a comment on that test saying what we are testing). | |
- Add tests for basic_string::replace_with_range;
- For vector, test both the case when reallocation happens due to insertion/assignment and when it doesn't;
- Nicer syntax for char buffers in insert_range_sequence_containers.h.
| libcxx/test/std/containers/insert_range_helpers.h | ||
|---|---|---|
| 31 ↗ | (On Diff #516693) | I think you don't need this class if you don't store your test cases in global variables. Then you could simply use std::string and it would work in constexpr too. IMO that would be better since this class is very specific. |
| libcxx/test/std/containers/sequences/insert_range_sequence_containers.h | ||
| 433 ↗ | (On Diff #516693) | I think it makes sense to use a lambda to avoid repeating here like you do in the replace_range_whatever test for string. |
| libcxx/test/std/strings/basic.string/string.modifiers/string_replace/replace_with_range.pass.cpp | ||
| 13 ↗ | (On Diff #516693) | We don't seem to be testing that the range is taken as Rng&&, are we? |
| 31 ↗ | (On Diff #516693) | Maybe? |
| 34 ↗ | (On Diff #516693) | |
| 491 ↗ | (On Diff #516693) | We should really be returning a reference to the same object! |
| 700 ↗ | (On Diff #516693) | You are also missing a SFINAE test for the constraints of the method. |
| libcxx/test/support/unwrap_container_adaptor.h | ||
|---|---|---|
| 14 ↗ | (On Diff #517468) | This could probably be useful in some of the existing adaptor tests as well. See e.g. test/std/containers/container.adaptors/stack/stack.cons/deduct.pass.cpp, lines 62-63: // I'd like to assert that we've gotten the right allocator in the stack, but // I don't know how to get at the underlying container. |
| libcxx/include/__iterator/ranges_iterator_traits.h | ||
|---|---|---|
| 28 ↗ | (On Diff #517821) | |
| libcxx/include/__ranges/from_range.h | ||
| 24 ↗ | (On Diff #517821) | I think with the current HIDE_FROM_ABI rules this shouldn't be marked. |
| libcxx/include/__ranges/to.h | ||
| 48 | Do you know whether GCC 13 fixes that bug? If yes, maybe make this a TODO, since we will switch very soon? | |
| 91–94 | Why not is_const and is_volatile? | |
| 128 | Is this the only use for __always_false? If yes, good news: static_assert(false) gets accepted by clang 17 and GCC 13, so this can soon just be what it was always supposed to be. | |
| 162 | I think adding and removing a pointer is actually more efficient thann using type_identity, since adding a pointer and removing it avoids instantiating a new type every time. | |
| 241 | ||
| libcxx/include/deque | ||
| 792 ↗ | (On Diff #513950) | IDK. I must have been misremembering something wrong. |
| libcxx/include/map | ||
| 66 ↗ | (On Diff #517821) | Note to self: continue here |
Can you address outstanding feedback on this review and then split it up as:
- vector
- deque
- string
- node-based containers
- container adaptors
- ranges::to (that could be this patch)
I'd like to do the final review on something more focused to make sure we don't miss anything, and also it'll allow staging the check-ins to avoid having to revert 11kLOC in case of issues.
| libcxx/include/forward_list | ||
|---|---|---|
| 738 ↗ | (On Diff #517821) | |
| libcxx/include/list | ||
|---|---|---|
| 912 ↗ | (On Diff #517821) | Can you remove std::forward here and confirm that the tests fail? Edit: Confirmed it fails. |
| 1556 ↗ | (On Diff #517821) | It feels to me like this check should be in __insert_with_sentinel? |
| libcxx/include/string | ||
| 1326 ↗ | (On Diff #517821) | This one can be more efficient. If we have an input range, then we do need to make a temporary string and append it. But if we have e.g. a forward_range or a sized_range, we don't need to make a copy of the input range, and I think we should really avoid doing it. I think simply using insert_range(end(), ...) here would solve that problem? |
| 1973 ↗ | (On Diff #517821) | Let's try to reduce the diff, this seems like it's only moved around. |
| libcxx/include/vector | ||
| 1470 ↗ | (On Diff #517821) | You need to retain the fact that this is at least a forward iterator, otherwise this method doesn't work properly. |
| 1478–1479 ↗ | (On Diff #517821) | This doesn't seem to work, I think we're consuming the first size() elements from __first and then copying the rest into the vector only. I think this also means there's a gap in the testing. |
| 1921 ↗ | (On Diff #517821) | This should be in __insert_with_sentinel, I think. |
| 1975 ↗ | (On Diff #517821) | Same, should be in __insert_with_size. |
Minimize delta in containers (don't move code around where avoidable), address a few comments.
| libcxx/include/__ranges/from_range.h | ||
|---|---|---|
| 24 ↗ | (On Diff #517821) | Can you elaborate? |
| libcxx/include/__ranges/to.h | ||
| 128 | This is the only use that I could find (although I'm a little skeptical -- perhaps this is done in a more ad-hoc way somewhere). And yes, I can't wait to be able to use static_assert(false). | |
| 241 | We don't implement bind_back officially yet, but the internal version is used in the implementation of ranges (and was added for that purpose). | |
| libcxx/include/vector | ||
|---|---|---|
| 1478–1479 ↗ | (On Diff #517821) | Thanks! I think this is the right form: if (__new_size <= capacity()) {
if (__new_size > size()) {
_ForwardIterator __mid = __first;
std::advance(__mid, size());
std::copy(__first, __mid, this->__begin_);
__construct_at_end(__mid, __last, __new_size - size());
} else {
pointer __m = std::copy(__first, __last, this->__begin_);
this->__destruct_at_end(__m);
}
}I think it's actually more readable without the __growing variable. |
| libcxx/include/vector | ||
|---|---|---|
| 1478–1479 ↗ | (On Diff #517821) | if (__new_size <= capacity()) {
if (__new_size > size()) {
_ForwardIterator __mid = std::next(__first, size());
std::copy(__first, __mid, this->__begin_);
__construct_at_end(__mid, __last, __new_size - size());
} else {
pointer __m = std::copy(__first, __last, this->__begin_);
this->__destruct_at_end(__m);
}
}Yeah, I think that works! |
| libcxx/include/__ranges/to.h | ||
|---|---|---|
| 48 | Hmm, this was a while ago, but looking up my notes, it looks like I was conflating two issues here. The compiler with a bug in this case was Clang 15: https://godbolt.org/z/aGrE1oP1v. I'll switch back to using a constexpr bool variable for consistency with the Standard and see if anything breaks on the CI. Thanks for calling the attention to this! | |
| libcxx/include/deque | ||
| 1823 ↗ | (On Diff #515224) | Hmm, how about using two overloads, one where the type of __l is an exact match for _BiIter and one when it's a different sentinel type? That way, we can only call next when the types differ (and thus next cannot be reduced to simply return __sent). |
| libcxx/include/vector | ||
| 1478–1479 ↗ | (On Diff #517821) | Note: still need to fix the testing part. |
| 1921 ↗ | (On Diff #517821) | I think I originally left it there due to the way the error message is written (referring to the exact name of the invoking function). But I don't think we lose much by making it slightly more generic, not to mention that the debug mode is effectively non-operational anyway. |
| libcxx/test/std/containers/insert_range_helpers.h | ||
| 31 ↗ | (On Diff #516693) | I tried changing this but not sure it's worth it. constexpr variables have a very nice property that if one of them is accidentally unused (i.e. a test case is omitted), the compiler produces an error. The class is pretty small and I don't think it adds that much maintenance burden. I remember implementing something similar before to work around some other limitations of vector and string which makes me suspect that having full control over the class's implementation has some value. |
Split into multiple patches:
- https://reviews.llvm.org/D149826 (vector);
- https://reviews.llvm.org/D149827 (deque);
- https://reviews.llvm.org/D149832 (string);
- https://reviews.llvm.org/D149830 (node-based containers);
- https://reviews.llvm.org/D149829 (container adaptors).
| libcxx/include/vector | ||
|---|---|---|
| 1478–1479 ↗ | (On Diff #517821) | I am moving this comment thread to D149826, feel free to mark as resolved. |
| libcxx/include/deque | ||
|---|---|---|
| 970 ↗ | (On Diff #513950) | I find it impossible to be consistent here because the existing code is inconsistent (across different headers, at the very least), so I just went with my personal preference. I find abbreviations a necessary evil when dealing with numerous template parameters but avoid them when possible. |
| libcxx/include/string | ||
|---|---|---|
| 1326 ↗ | (On Diff #517821) | Addressed in https://reviews.llvm.org/D149832. |
| libcxx/test/std/strings/basic.string/string.modifiers/string_replace/replace_with_range.pass.cpp | ||
| 13 ↗ | (On Diff #516693) | Addressed in https://reviews.llvm.org/D149832. |
| 34 ↗ | (On Diff #516693) | Addressed in https://reviews.llvm.org/D149832. |
| 700 ↗ | (On Diff #516693) | Addressed in https://reviews.llvm.org/D149832. |
LGTM with comments. Thanks, I think this is great!
| libcxx/include/__ranges/to.h | ||
|---|---|---|
| 68–70 | Re-reading it, I think it would be a lot more readable to inline, especially since there's an else if with the input_range<_Container> constraint. | |
| 162 | IMO type_identity is a lot more explicit about what we're doing. Between instantiating type_identity and remove_pointer_t, I think the difference is negligible. | |
| 165 | IMO this would fit nicely on a single line. Same below. Or make sure they line up with the if constexpr condition. | |
| 221–222 | Would it be reasonable to try using a lambda here? Something like auto __to_func = []<input_range _Range, class... _Args>(_Range&& __range, _Args&&... __args) -> _Container
requires requires { ranges::to<_Container>(std::forward<_Range>(__range), std::forward<_Args>(__args)...) }
{ return ranges::to<_Container>(std::forward<_Range>(__range), std::forward<_Args>(__args)...); };
return __range_adaptor_closure_t(std::__bind_back(__to_func, std::forward<_Args>(__args)...));It's more compact and a bit more localized. Your call. | |
| libcxx/test/std/ranges/range.utility/range.utility.conv/container.h | ||
| 2 | Did you clang-format this? | |
| libcxx/test/std/ranges/range.utility/range.utility.conv/to.pass.cpp | ||
| 14–15 | I think this should be removed now. | |
| 48 | ||
| 514 | Ok I love this! I was looking for something like it. | |
| libcxx/test/std/ranges/range.utility/range.utility.conv/to_deduction.pass.cpp | ||
| 13 | ||
| 15–16 | I think this should be removed now. | |
| libcxx/test/std/ranges/range.utility/range.utility.conv/to_std_containers.pass.cpp | ||
| 12–15 | Let's update this comment to explain that we are testing general interoperation between std containers. That's what we're doing right? | |
| libcxx/include/__ranges/to.h | ||
|---|---|---|
| 68–70 | Making this a concept is necessary to "short-circuit" the second condition (e.g. an optional satisfies the first condition, i.e., !input_range, but attempting to instantiate the second condition would fail since range_value_t<optional<T>> is ill-formed). Added a comment to that effect. | |
| 221–222 | I tried it out and I think I like it better (though it looks like clang-format has trouble with a constrained lambda). | |
Do you know whether GCC 13 fixes that bug? If yes, maybe make this a TODO, since we will switch very soon?