Page MenuHomePhabricator

[libc++][ranges] Implement `ranges::to`.
Needs ReviewPublic

Authored by var-const on Jan 23 2023, 1:46 AM.


Group Reviewers
Restricted Project

Diff Detail

Event Timeline

var-const created this revision.Jan 23 2023, 1:46 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 23 2023, 1:46 AM
Herald added a subscriber: arichardson. · View Herald Transcript
var-const updated this revision to Diff 491670.Jan 24 2023, 1:48 AM

Implement the from_range_t constructor in vector properly.

Fix debug-only stuff

ldionne added inline comments.

I think this will miss the deadline for LLVM 16, and it'll be too large to cherry-pick, so I'd suggest aiming it for LLVM 17.

1 ↗(On Diff #491670)

I think I would suggest moving this to __ranges, or even to __concepts.

28–29 ↗(On Diff #491670)

I think there's no better way of doing it except for checking that all the things that std::insert_iterator would use in its implementation are well-formed. I suspect the standard is aware of that and they just decided not to go down that route.


I wouldn't be surprised if some system headers somewhere already defined __false, so I think we might want to steer clear of that.

We may actually already have something like that using a constexpr bool variable.


If that makes sense, it may be useful to make these changes in a separate patch prior to this patch. Just suggesting in case it makes things simpler.

ldionne added inline comments.Feb 2 2023, 1:14 PM

Maybe __does_not_require_recursive_conversion? Or __try_non_recursive_conversion? Or maybe just inline that in the function below and use an inline requires?


Can you double-check that this is the right concept? And we should also move it outside of that detail namespace -- that's an unusual way to implement an exposition-only concept, but this comes from the very beginning of our ranges implementation. Basically let's clean up all those concepts in __iterator_traits_detail.


Can you add tests that would fail if this didn't short-circuit properly? TBH I think those tests would fail right now.


I think those should be qualified calls.

Mordante added inline comments.

Yesterday we voted in. So maybe it would be good to directly implement the resolution for that fix in this patch.

var-const updated this revision to Diff 501774.Thu, Mar 2, 12:32 AM
var-const marked 9 inline comments as done.

Partially address feedback, add more tests, fix deduce-expr.

var-const added inline comments.Thu, Mar 2, 10:18 AM

Thanks for the heads-up! Done.


Went with __try_non_recursive_conversion (unless you feel strongly about inlining it).


I thought so too but couldn't find it.

ldionne added inline comments.Tue, Mar 7, 1:36 PM

Did you intend to have ADL here?


I think this part of the patch is also NFC and could easily be extracted, since you're mainly hoisting the __n computation to outside of __construct_at_end.


I think this is technically ill-formed according to the spec. I wonder whether it makes sense to test the exact way in which it is ill-formed as we do here (probably not).

Also note that if that's correct and this is ill-formed, then technically we could also be SFINAE friendly as a QOI matter. I don't think we should unless it's simple and other implementations are doing it as well.


Can we use std::move or std::move_backward here?


Here and everywhere else -- this is going to become an error once we have C++20 modules.


It would be nice to templatize the tests on the iterator category, and to run them with our various iterator archetypes.


Nothing in this test seems to rely on the contents of in, so I think it would also be nice to run it on a couple of different inputs:

  • Empty sequence
  • One element sequence
  • Two elements
  • etc

Could we get one test that does something like:

auto closure = std::ranges::to<C>();
std::same_as<C> decltype(auto) result = in | closure;
assert(result == the-result-you-would-get-with-ranges::to-applied-directly);

No need to test it for all the constructor choices, but I think checking it once it useful.


Are there other constructors that can be tested here?


It would be nice to check the contents too. To avoid this being too unwieldy, what about this?

int x = 0;
for (auto& a : in)
  for (auto& b : a)
    for (auto& c : b)
      c = x++;

I'm happy with any way that makes this not unwieldy to check. One thing we could also do is check the content for a 2 or 3 dimensional array, not a 4 dimensional array.


Reminder to remove

61 ↗(On Diff #501774)

I think you can make this change and the one below as a NFC before this patch, no review needed.

var-const updated this revision to Diff 503872.Thu, Mar 9, 11:57 AM

from_range_t constructors and testing WIP

ldionne added inline comments.Thu, Mar 9, 12:53 PM

In the case of deque, it's not clear to me that we gain much from using __append_n. In both cases, we end up performing N / CHUNK_SIZE allocations and then copying the whole input range into these allocations. Maybe worth measuring? I think looking at how __add_back_capacity(size_type __n) and __add_back_capacity() differ will provide some additional insights here.

Also, if we end up keeping this optimization, the if constexpr condition seems a bit off. What should we do for a forward_range that is not a sized_range? We'll have to determine whether we want to take the hit to compute distance(rng) and then call __append_n, or not.


I think is_permutation might be a good candidate to use here.


Here's a suggestion that would avoid having to define is_equal with a bit of magic:

template <class T>
using sequence_containers = types::type_list<std::vector<T>, std::deque<T>, std::list<T>, std::forward_list<T>>;

template <class T>
using set_like_associative_containers = types::type_list<std::set<T>, std::multiset<T>, std::unordered_set<T>, std::unordered_multiset<T>>;

template <class Key, class Value>
using map_like_associative_containers = types::type_list<std::map<Key, Value>, std::multimap<Key, Value>, std::unordered_map<Key, Value>, std::unordered_multimap<Key, Value>>;

void test() {
  // Sequence = Sequence
  types::for_each(sequence_containers<int>{}, []<class To>() {
    types::for_each(sequence_containers<int>{}, []<class From>() {
      test_conversion<From, To>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::equal(a, b); });
  // Set-like = Set-like
  types::for_each(set_like_containers<int>{}, []<class To>() {
    types::for_each(set_like_containers<int>{}, []<class From>() {
      test_conversion<From, To>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::is_permutation(a, b); });
  // Map-like = Map-like
  types::for_each(map_like_containers <int, int>{}, []<class To>() {
    types::for_each(map_like_containers<int, int>{}, []<class From>() {
      test_conversion<From, To>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::is_permutation(a, b); });

  // Sequence = Set-like and Set-like = Sequence
  types::for_each(sequence_containers<int>{}, []<class To>() {
    types::for_each(set_like_associative_containers<int>{}, []<class From>() {
      test_conversion<From, To>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::is_permutation(a, b); });
      test_conversion<To, From>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::is_permutation(a, b); });
  // Sequence = Map-like and Map-like = Sequence
  types::for_each(sequence_containers<std::pair<int, int>>{}, []<class To>() {
    types::for_each(map_like_associative_containers<int, int>{}, []<class From>() {
      test_conversion<From, To>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::is_permutation(a, b); });
      test_conversion<To, From>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::is_permutation(a, b); });
  // Set-like = Map-like and Map-like = Set-like
  types::for_each(set_like_containers<std::pair<int, int>>{}, []<class To>() {
    types::for_each(map_like_containers<int, int>{}, []<class From>() {
      test_conversion<From, To>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::is_permutation(a, b); });
      test_conversion<To, From>(/* equal = */[](auto const& a, auto const& b) { return std::ranges::is_permutation(a, b); });
var-const updated this revision to Diff 505752.Thu, Mar 16, 3:20 AM

Add from_range_t constructors to all containers except sets and maps.

Add the from_range_t constructors to map.

ldionne added inline comments.Thu, Mar 16, 1:04 PM

Testing: We should make sure that we do the right thing if we throw halfway through the construction. Do we destroy the elements constructed so far? Do we do that in reverse construction order?

I think the answer right now is "no" to both of these questions. If so, and if that's a pre-existing issue for other constructors of deque, and if the standard requires us to do that, let's at least file a bug report so we can remember to fix that.


Does the Standard specify whether we should be forwarding elements from the input range into the container being constructed? For example, let's say we have this:

std::vector<std::string> v{"hello", "world", "something long"};
std::list<std::string> list(std::from_range, std::move(v));

We have an expiring vector<string> here and we could technically move the strings from it and into the std::list being constructed, however is that something we're allowed to do?

This probably applies elsewhere too.

Edit: I don't think we are allowed to do that, cause no standard API would allow us to achieve this. We'd need to use a move_iterator on the input vector<string> to get that effect, and there's really no way to do that naturally (e.g. std::forward(v).begin() won't give you back a move_iterator). So I think your code is fine as-is.


I think this actually raises another interesting question. What happens if you do:

std::vector<std::string> v{"hello", "world", "something long"};
std::ranges::subrange r(std::move_iterator(v.begin()), std::move_iterator(v.end()));

std::list<std::string> list(std::from_range, r);

Right now, this will do the right thing and it will move elements out of the subrange (aka the vector's elements), since you use std::forward. But if you didn't use std::forward, it wouldn't move the strings out. For std::string that's only an optimization, but if you have a move-only type, then that becomes a matter of conformance, I think. I think the Standard probably implicitly mandates that this needs to work. So I would test with something like:

struct MoveOnly { ... };
MoveOnly data[...] = {...};
std::ranges::subrange subrange(std::move_iterator(data.begin()), std::move_iterator(data.end()));
std::list<MoveOnly> list(std::from_range, subrange);



Please mark as done once you have tests for these CTAD guides (for all containers).


Nitpick but I would not put a blank line between those, it seems a bit superfluous and in this case a bit inconsistent with surrounding code. But I don't care strongly.


This should also have tests for the MoveOnly behavior.


This is nitpicky but let's make sure we have a test that the constructor is explicit.


Maybe call __default_init() here unconditionally for consistency with above?

var-const updated this revision to Diff 507270.Wed, Mar 22, 2:08 AM

Finish adding from_range_t constructors to containers.

var-const updated this revision to Diff 507651.Thu, Mar 23, 1:51 AM

Testing WIP.

var-const published this revision for review.Tue, Mar 28, 11:57 AM
var-const retitled this revision from DRAFT [libc++][ranges] Implement `ranges::to`. to [libc++][ranges] Implement `ranges::to`..

The tests are still WIP.


Not sure if this SFINAE is actually needed (I followed the existing pattern). Concepts and the from_range_t should work to distinguish these from existing CTAD "overloads", and there is no ambiguity between the 2 and 3 argument versions.

Herald added a project: Restricted Project. · View Herald TranscriptTue, Mar 28, 11:58 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Tests for from_range_t constructors (WIP).

ldionne added inline comments.Tue, Mar 28, 12:25 PM

Comment here


Here I think it would be good to add

[](const auto&) {
  // no additional validation needed for std::list

Otherwise it looks like an oversight.

for_all_iterators_and_allocators<bool>([]<class Iter, class Sent, class Alloc>() {
  // ...

Seems like this can be removed.


Same comment about different sizes. Also would be nice to cover the SSO and the long string representation.


That's more explicit and makes the test easier to read IMO


We should test with an empty range and also a couple of non-zero sizes.


Let's test on an empty array, a 1-sized array, etc.

ldionne added inline comments.Tue, Mar 28, 12:27 PM

Do we want to put that file under libcxx/test/std/containers/sequences instead? Or would that mess up how we need to include the header too much?

Could you split this up into multiple patches? This could be a lot easier to review if all the container changes were in separate patches. Also, is this still WIP? It looks like large parts of the paper are not implemented.