This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::to`.
ClosedPublic

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

Details

Reviewers
jdoerfert
philnik
ldionne
Group Reviewers
Restricted Project
Commits
rGc3648f37d0ed: [libc++][ranges] Implement `ranges::to`.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
var-const added inline comments.Apr 12 2023, 12:38 AM
libcxx/include/string
1932–1933

Doing so breaks string tests.

libcxx/test/std/ranges/range.utility/range.utility.conv/to_std_containers.pass.cpp
222

Sorry about that!

var-const updated this revision to Diff 512951.Apr 12 2023, 1:17 PM
var-const marked an inline comment as done.

Rebase

var-const marked 6 inline comments as done.

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.

var-const updated this revision to Diff 513391.Apr 13 2023, 5:04 PM

Finish tests, mark new tests as requiring C++23.

var-const updated this revision to Diff 513413.Apr 13 2023, 7:30 PM

Fix tests (WIP).

var-const updated this revision to Diff 513421.Apr 13 2023, 8:05 PM

clang-format.

var-const marked an inline comment as done.Apr 13 2023, 10:31 PM

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
612

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. :)

var-const updated this revision to Diff 513950.Apr 15 2023, 5:05 PM
var-const marked an inline comment as done.

Implement all the insert_range-like functions (no tests yet).

philnik requested changes to this revision.Apr 16 2023, 12:35 PM

Did you upload the wrong patch?

libcxx/include/deque
70

throughout

661–667

IMO it would be better to do this optimization in __assign_whatever to avoid having slightly different versions of this in different places.

770

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.

915

Why not _Iter and _Sent like we use elsewhere?

This revision now requires changes to proceed.Apr 16 2023, 12:35 PM
var-const marked 3 inline comments as done.

Mostly finish tests for sequence containers.

Still TODO for sequence containers:

  • test basic_string::replace_with_range;
  • test vector with and without reallocation.

Fix the upload.

@philnik Sorry, I uploaded just the last commit from my local branch last time. Should be fixed now.

libcxx/include/deque
70

This file uses this style, without since. I deliberately keep it consistent.

661–667

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.

770

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.

var-const retitled this revision from [libc++][ranges] Partially implement `ranges::to`. to [libc++][ranges] Implement `ranges::to`..Apr 20 2023, 12:21 PM
var-const edited the summary of this revision. (Show Details)
ldionne added inline comments.Apr 20 2023, 1:33 PM
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
788

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.

1194–1195

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());
1197
__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.

1708

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
852

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
480

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.

Finish testing sequence containers, maps and sets WIP.

ldionne added inline comments.Apr 25 2023, 1:17 PM
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.

Finish tests (including container adaptor tests).

var-const added inline comments.Apr 27 2023, 12:51 AM
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.

Fixing tests wip.

philnik added inline comments.Apr 28 2023, 10:32 AM
libcxx/include/__iterator/ranges_iterator_traits.h
29
libcxx/include/__ranges/from_range.h
25

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
770

IDK. I must have been misremembering something wrong.

libcxx/include/map
66

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
734
ldionne added inline comments.Apr 28 2023, 10:38 AM
libcxx/include/list
904

Can you remove std::forward here and confirm that the tests fail? Edit: Confirmed it fails.

1504

It feels to me like this check should be in __insert_with_sentinel?

libcxx/include/string
1270

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?

1930

Let's try to reduce the diff, this seems like it's only moved around.

libcxx/include/vector
1400

You need to retain the fact that this is at least a forward iterator, otherwise this method doesn't work properly.

1405–1406

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.

1850

This should be in __insert_with_sentinel, I think.

1895

Same, should be in __insert_with_size.

var-const updated this revision to Diff 519123.May 3 2023, 9:35 AM
var-const marked 8 inline comments as done.

Minimize delta in containers (don't move code around where avoidable), address a few comments.

var-const marked an inline comment as done.May 3 2023, 9:36 AM
var-const added inline comments.
libcxx/include/__ranges/from_range.h
25

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

var-const added inline comments.May 3 2023, 12:03 PM
libcxx/include/vector
1405–1406

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.

ldionne added inline comments.May 3 2023, 12:28 PM
libcxx/include/vector
1405–1406
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!

var-const marked 13 inline comments as done.May 4 2023, 1:54 AM
var-const added inline comments.
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
1708

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
1405–1406

Note: still need to fix the testing part.

1850

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.

var-const updated this revision to Diff 519387.May 4 2023, 1:54 AM
var-const marked 4 inline comments as done.

Address more feedback.

ldionne added inline comments.May 4 2023, 10:05 AM
libcxx/include/vector
1405–1406

I am moving this comment thread to D149826, feel free to mark as resolved.

var-const marked 2 inline comments as done.May 4 2023, 4:25 PM
var-const added inline comments.
libcxx/include/deque
915

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.

var-const marked an inline comment as done.May 16 2023, 12:31 AM
var-const marked 2 inline comments as done.May 16 2023, 12:41 AM
var-const added inline comments.
libcxx/include/__ranges/to.h
162

Tagging @ldionne

var-const marked 4 inline comments as done.May 17 2023, 12:54 AM
var-const added inline comments.
libcxx/include/string
1270
libcxx/test/std/strings/basic.string/string.modifiers/string_replace/replace_with_range.pass.cpp
13 ↗(On Diff #516693)
34 ↗(On Diff #516693)
700 ↗(On Diff #516693)
var-const updated this revision to Diff 540637.Jul 14 2023, 9:26 PM
var-const marked 4 inline comments as done.

Rebase, update node-based containers according to the current state of D149830.

Fix the CI.

Rebase, fix formatting

ldionne accepted this revision.Jul 18 2023, 1:05 PM

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
1 ↗(On Diff #541646)

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
12 ↗(On Diff #541646)
14–15 ↗(On Diff #541646)

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?

var-const marked 13 inline comments as done.Jul 19 2023, 11:34 AM
var-const added inline comments.
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).

var-const marked 2 inline comments as done.

Address feedback, fix the CI.

var-const updated this revision to Diff 542719.Jul 20 2023, 4:38 PM

Fix CI and rebase.

var-const updated this revision to Diff 542733.Jul 20 2023, 6:09 PM

Fix the CI and rebase.

This revision was not accepted when it landed; it landed in state Needs Review.Jul 20 2023, 10:48 PM
This revision was automatically updated to reflect the committed changes.