Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

[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
ldionne added inline comments.Apr 28 2023, 10:38 AM
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.

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

var-const added inline comments.May 3 2023, 12:03 PM
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.

ldionne added inline comments.May 3 2023, 12:28 PM
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!

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

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
1478–1479 ↗(On Diff #517821)

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

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
1326 ↗(On Diff #517821)
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
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?

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.