Page MenuHomePhabricator

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

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

Details

Reviewers
None
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.
libcxx/docs/Status/Cxx2bPapers.csv
44

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.

libcxx/include/__memory/container_compatible_range.h
1 ↗(On Diff #491670)

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

28–29 ↗(On Diff #491670)
libcxx/include/__ranges/to.h
54

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.

73

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.

libcxx/include/vector
734–762

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
libcxx/include/__ranges/to.h
68–70

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?

98

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.

99

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

124–125

I think those should be qualified calls.

162
186
Mordante added inline comments.
libcxx/docs/Status/Cxx2bPapers.csv
45

Yesterday we voted https://cplusplus.github.io/LWG/issue3847 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
libcxx/docs/Status/Cxx2bPapers.csv
45

Thanks for the heads-up! Done.

libcxx/include/__ranges/to.h
68–70

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

73

I thought so too but couldn't find it.

ldionne added inline comments.Tue, Mar 7, 1:36 PM
libcxx/include/__ranges/to.h
197

Did you intend to have ADL here?

libcxx/include/vector
2438

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.

libcxx/test/std/ranges/range.utility/range.utility.conv/to.pass.cpp
49

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.

160–162

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

179

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

187

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

189

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
198

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.

319

Are there other constructors that can be tested here?

356

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.

485

Reminder to remove

libcxx/test/support/almost_satisfies_types.h
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
libcxx/include/deque
612

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.

libcxx/test/std/ranges/range.utility/range.utility.conv/to_std_containers.pass.cpp
54–56

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

70–90

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
libcxx/include/deque
609

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.

libcxx/include/list
899–906

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.

904

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);

(pseudo-code)

1177

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

libcxx/include/map
1117–1119

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.

1344

This should also have tests for the MoveOnly behavior.

libcxx/include/ranges
353

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

libcxx/include/string
1932–1933

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.

libcxx/include/queue
480

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
libcxx/test/std/containers/sequences/forwardlist/forwardlist.cons/from_range.pass.cpp
12

Comment here

libcxx/test/std/containers/sequences/list/list.cons/from_range.pass.cpp
13

Here I think it would be good to add

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

Otherwise it looks like an oversight.

libcxx/test/std/containers/sequences/vector.bool/construct_from_range.pass.cpp
21
for_all_iterators_and_allocators<bool>([]<class Iter, class Sent, class Alloc>() {
  // ...
});
libcxx/test/std/ranges/range.utility/range.utility.conv/to.ctrs.pass.cpp
1

Seems like this can be removed.

libcxx/test/std/strings/basic.string/string.cons/from_range.pass.cpp
12

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

libcxx/test/support/from_range_associative_containers.h
44

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

46

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

libcxx/test/support/from_range_helpers.h
81–105
libcxx/test/support/from_range_sequence_containers.h
33

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

ldionne added inline comments.Tue, Mar 28, 12:27 PM
libcxx/test/support/from_range_sequence_containers.h
1

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.