Page MenuHomePhabricator

[libcxx][iterator] adds `std::ranges::advance`
ClosedPublic

Authored by cjdb on May 5 2021, 9:43 AM.

Details

Summary

Implements part of P0896 'The One Ranges Proposal'.
Implements [range.iter.op.advance].

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Mordante added inline comments.May 5 2021, 10:45 AM
libcxx/include/__iterator/primitives.h
129 ↗(On Diff #343090)

If we violate the preconditions we leave the function without returning a value, resulting in UB. Can you add _LIBCPP_UNREACHABLE() instead.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/advance.pass.cpp
16

Please use

// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1                                  
// UNSUPPORTED: libcxx-no-debug-mode

instead.
I wonder whether we still need to use this at all now we have a CI build with debug mode enabled. I will probably remove them from my format patches.

cjdb marked an inline comment as done.May 5 2021, 12:49 PM
cjdb added inline comments.
libcxx/include/__iterator/functionish.h
31 ↗(On Diff #343090)

__function_like wfm. There's more going on here than just ADL inhibition, so we'd need a very good replacement.

libcxx/include/__iterator/primitives.h
56 ↗(On Diff #343090)

This is an if constexpr else, which prunes the false case from the codegen when the true path is generated.

112 ↗(On Diff #343090)

See above.

129 ↗(On Diff #343090)

Oooooh thanks for this! I was sad that _LIBCPP_ASSERT was so... relaxed.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/advance.pass.cpp
16

That's just something I forgot to delete. I was trying to get my _LIBCPP_ASSERT to fire since I was sure a precondition was bad and forgot to delete it. _LIBCPP_UNREACHABLE will render the debug stuff unnecessary anyway, I hope.

Quuxplusone added inline comments.May 5 2021, 1:57 PM
libcxx/include/CMakeLists.txt
20–21

Both of these filenames violate my continuing-to-devolve-but-still-fairly-conservative rules about helper header naming. Looking at these names I have no idea what these headers contain or for what purpose they exist as separate entities.

libcxx/include/__iterator/functionish.h
31 ↗(On Diff #343090)

I believe the traditional name is "niebloid"; could we use "niebloid"? (Or point to a technical difficulty with "niebloid"?)
In that case, this class would be niebloid_base, and the filename would be __ranges/niebloid_base.h (__iterator/? __algorithm/?)

But at a higher level, I don't see why we'd want all of our niebloids to inherit from a common base class at all. This seems like the sort of thing that should be handled via a macro, so that we could just write, like,

class __advance_fn {
    _LIBCPP_NIEBLOID_SPECIAL_MEMBERS(__advance_fn);
public:
    void operator()(...) const...
    etc...
};

You're also trying to command the tides a little bit here; e.g. you're going out of your way to make __advance_fn "not default constructible," but that doesn't actually stop anyone from writing e.g. decltype(std::ranges::advance) ha = {};.
We also need people to be able to pass these objects around like functions, right? I mean,

std::vector<int*> v = ...;
std::transform(v.begin(), v.end(), std::ranges::next);

is supposed to work? (Right?) If we need that to work, then making these objects immovable is actually counterproductive: we want them to be copyable just like function pointers and lambdas would be.

cjdb marked an inline comment as done.May 5 2021, 2:31 PM
cjdb added inline comments.
libcxx/include/CMakeLists.txt
20–21
  • I'll admit __iterator/functionish.h should probably have been just __functionish.h.
  • __iterator/primitives.h on the other hand corresponds to the stable name [iterator.primitives]. We could always do __iterator/primitives/advance.h, etc.
libcxx/include/__iterator/functionish.h
31 ↗(On Diff #343090)

I believe the traditional name is "niebloid"; could we use "niebloid"? (Or point to a technical difficulty with "niebloid"?)

advance is a "niebloid", but this __function_like has no relationship with niebloids. I'm just getting back the functionality of functions here. Also, "niebloid" is a cute name, but it's about as informative as "Koenig" lookup (so I'd prefer a more boring name). As for where this file lives, I have zero opinion.

But at a higher level, I don't see why we'd want all of our niebloids to inherit from a common base class at all. This seems like the sort of thing that should be handled via a macro, so that we could just write, like,

I'm certainly not married to the current implementation: whatever's most readable is probably best (readable for the user getting a diagnostic, that is). Lemme experiment when I am working on this next.

You're also trying to command the tides a little bit here; e.g. you're going out of your way to make __advance_fn "not default constructible," but that doesn't actually stop anyone from writing e.g. decltype(std::ranges::advance) ha = {};.

Is that because it's an aggregate? Ugh.

We also need people to be able to pass these objects around like functions, right? I mean,

std::vector<int*> v = ...;
std::transform(v.begin(), v.end(), std::ranges::next);

is supposed to work? (Right?) If we need that to work, then making these objects immovable is actually counterproductive: we want them to be copyable just like function pointers and lambdas would be.

Should it work? Morally, yes. Unless this is an addressable function (and I don't see that it is), the standard goes out of its way to say that this is not possible (grep for "addressable" in http://wg21.link/library). Try doing the above with std::next, for example. Niebloids are not function objects: it's just the easiest (and only portable) way we can do them presently.

Quuxplusone added inline comments.May 5 2021, 2:45 PM
libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/advance.verify.cpp
39 ↗(On Diff #343094)

I don't think we can have tests in test/std/ that depend on the internals of libc++ in this way.
You could do this as a SFINAE test, like,

template<class T>
concept HasADLAdvance = requires(T x) { advance(x, 0); }
    || requires(T x) { advance(x, x); }
    || requires(T x) { advance(x, 0, x); };
template<class T>
concept IsAddressable = requires(T x) { &x; } || std::movable<T>;
static_assert(!HasADLAdvance<std::ranges::dangling*>);
static_assert(!IsAddressable<decltype(std::ranges::advance)>);

(I also recommend using std::ranges::dangling* or something like that, because it's way lighter-weight than std::ranges::forward_iterator and also does not require you to reopen namespace std in this test file.)

Mordante added inline comments.May 6 2021, 8:15 AM
libcxx/include/__iterator/primitives.h
56 ↗(On Diff #343090)

Good point. I'm too used commenting on a 'return else' sequence ;-)

cjdb added inline comments.May 6 2021, 9:17 AM
libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/advance.verify.cpp
39 ↗(On Diff #343094)

I don't think we can have tests in test/std/ that depend on the internals of libc++ in this way.

Is this in regard to avoiding just // expected-error@*:*{{no matching function for call to '__convert_to_integral'}}? That's an instantiation error I didn't try too hard to fix, so I could revisit it.

You could do this as a SFINAE test, like,

template<class T>
concept HasADLAdvance = requires(T x) { advance(x, 0); }
    || requires(T x) { advance(x, x); }
    || requires(T x) { advance(x, 0, x); };
template<class T>
concept IsAddressable = requires(T x) { &x; } || std::movable<T>;
static_assert(!HasADLAdvance<std::ranges::dangling*>);
static_assert(!IsAddressable<decltype(std::ranges::advance)>);

Why is IsAddressable a disjunction instead of a conjunction? (Also, why is movability involved at all?).

(I also recommend using std::ranges::dangling* or something like that, because it's way lighter-weight than std::ranges::forward_iterator and also does not require you to reopen namespace std in this test file.)

std::ranges::view_base is already in, so I'll use that instead.

cjdb updated this revision to Diff 343446.May 6 2021, 10:11 AM
cjdb marked 4 inline comments as done.

responds to comments from @Mordante

  • renames __functionish to __function_like
  • adds synopsis
  • changes __abs to return an unsigned
  • adds _LIBCPP_UNREACHABLE()
  • removes _LIBCPP_DEBUG_LEVEL

responds to comments from @Quuxplusone

  • moves __iterator/function_like.h to __function_like.h
  • SFINAEs out std::advance when _Distance isn't convertible to an integral
    • fixes expected error in verification test
  • adds missing _LIBCPP_POP_MACROS

miscellaneous fixes:

  • moves certain verification tests into test_standard_function.h so they can be put in advance.pass.cpp
cjdb added a comment.May 6 2021, 10:11 AM

Is the synopsis up to date?

It is now :-)

libcxx/include/__iterator/functionish.h
31 ↗(On Diff #343090)

You're also trying to command the tides a little bit here; e.g. you're going out of your way to make __advance_fn "not default constructible," but that doesn't actually stop anyone from writing e.g. decltype(std::ranges::advance) ha = {};.

I just tried this and it's not valid. Are there any other ways it can be written?

libcxx/include/__iterator/primitives.h
39 ↗(On Diff #343090)

I suppose we could. I don't like treating unsigned ints as "non-negative whole numbers", but I don't think we've got a choice here.

cjdb updated this revision to Diff 343448.May 6 2021, 10:14 AM

removes 0wcp

Mordante accepted this revision as: Mordante.May 6 2021, 12:00 PM

LGTM modulo some small nits.

libcxx/include/__function_like.h
11

Please also rename the include guard.

libcxx/include/__iterator/primitives.h
39 ↗(On Diff #343090)

In general I also dislike this way to treat unsigned values. But I think it's better than disallowing one value.

41 ↗(On Diff #343448)

I'm not too fond of negating unsigned values. How do you feel about method/approach used in <charconv>?
Here the code I'm referring to, mainly __complement, but some added context.

template <typename _Tp>
inline _LIBCPP_INLINE_VISIBILITY _Tp
__complement(_Tp __x)
{
    static_assert(is_unsigned<_Tp>::value, "cast to unsigned first");
    return _Tp(~__x + 1);
}

template <typename _Tp>
inline _LIBCPP_INLINE_VISIBILITY typename make_unsigned<_Tp>::type
__to_unsigned(_Tp __x)
{
    return static_cast<typename make_unsigned<_Tp>::type>(__x);
}

template <typename _Tp>
_LIBCPP_AVAILABILITY_TO_CHARS
inline _LIBCPP_INLINE_VISIBILITY to_chars_result
__to_chars_itoa(char* __first, char* __last, _Tp __value, true_type)
{
    auto __x = __to_unsigned(__value);
    if (__value < 0 && __first != __last)
    {
        *__first++ = '-';
        __x = __complement(__x);
    }

    return __to_chars_itoa(__first, __last, __x, false_type());
}
zoecarver added inline comments.May 6 2021, 5:16 PM
libcxx/include/__iterator/primitives.h
99 ↗(On Diff #343448)

This is a value we likely actually do want to discard.

cjdb added inline comments.May 6 2021, 9:38 PM
libcxx/include/__iterator/primitives.h
99 ↗(On Diff #343448)

Please elaborate?

cjdb updated this revision to Diff 343579.May 6 2021, 10:27 PM
cjdb marked 3 inline comments as done.

applies feedback from @Mordante:

  • replaces leftover instances of "functionish" with "function_like"
  • changes -__n to explicit two's complement

applies self-feedback (not listed):

  • adds output_iterator tests
  • replaces conversion to unsigned int with __to_unsigned_like
zoecarver added inline comments.May 7 2021, 9:37 AM
libcxx/include/__iterator/primitives.h
99 ↗(On Diff #343448)

If we did the thing I wish we did in C++ and functions were nodiscard by default, there would be a [[discardable_result]] attribute instead.

If that were the case, this function would be one of the ones that's marked with [[discardable_result]], because there are valid reasons to use this function and discard the result. That's probably the most common use, in fact.

In other words, this function is one of the ones where we don't actually need the nodiscard attribute.

cjdb added inline comments.May 7 2021, 9:38 AM
libcxx/include/__iterator/primitives.h
99 ↗(On Diff #343448)

In other words, this function is one of the ones where we don't actually need the nodiscard attribute.

What I meant was "please elaborate on why you feel this function's result should be considered discardable".

zoecarver added inline comments.May 7 2021, 9:43 AM
libcxx/include/__iterator/primitives.h
99 ↗(On Diff #343448)

Because it has side effects: advancing the iterator. It's possible, and even likely, that users would only care about the side effects. One example of this is in the implementation of ranges::next another is in my drop_view patch.

Quuxplusone added inline comments.May 7 2021, 9:45 AM
libcxx/include/__iterator/primitives.h
99 ↗(On Diff #343448)

std::ranges::advance(i, s); // advance i to s
This is the normal and expected use of the function: for its side effect. It's just like std::advance. When we get to std::ranges::next, you'll have a stronger case for _LIBCPP_NODISCARD_EXT.

Also, again, please make sure to use _LIBCPP_NODISCARD_EXT for things that are non-nodiscard according to the Standard Itself. We can mark them, but we need to be clear that it's a libc++ extension. libc++ uses raw [[nodiscard]] only in places that the Standard Itself uses [[nodiscard]] — a rare occurrence.

zoecarver added inline comments.May 7 2021, 10:47 AM
libcxx/test/support/test_iterators.h
783

Maybe we should have a operations_count too. I feel like these should be += n but that's not very helpful for testing complexity.

ldionne added inline comments.May 8 2021, 9:36 AM
libcxx/include/__iterator/primitives.h
10 ↗(On Diff #343579)

Why is this header named that way? Shouldn't this be __iterator/advance.h to be consistent with what we've done so far? We've never named headers after the section of the standard that they roughly represent, and I don't think we should start doing that. Section names can change, they don't necessarily best represent what's in the file, and it goes against what we've started doing consistently.

39 ↗(On Diff #343579)

Drop [[nodiscard]] (as discussed offline). Also applies to most other places where you use it.

Also, should this be promoted to a more general utility?

And also, this may be obvious to you, but why don't we simply use std::abs? Is it because http://eel.is/c++draft/iterator.primitives#range.iter.op.advance-6.1.1 uses absolute value in math notation (which is well-defined for all inputs), whereas std::abs is UB if the absolute value can't be represented in the return type?

60–70 ↗(On Diff #343579)

I understand why this works, but I find it's a slightly confusing way to write this. Instead, Maybe else if constexpr (is_bidirectional_iterator<_Ip>) { handle bidirectional case } else { handle-forward-only-case }.

It's not as clever, but maybe easier to understand?

libcxx/include/iterator
550

What's the rationale for this change? I remember playing around the same area here: https://reviews.llvm.org/D81425, it might be useful to read that again for context. I don't have enough time to form an opinion again right now unfortunately.

If we decide to keep it, we should add a test. IIUC that would be considered a libc++ extension at this point based on glancing at https://reviews.llvm.org/D81425 again quickly.

libcxx/test/support/test_iterators.h
727

s/[[nodiscard]]//g

cjdb added inline comments.May 8 2021, 10:35 AM
libcxx/include/__iterator/primitives.h
10 ↗(On Diff #343579)

Same reason we have __ranges/access.h. I can split it up, but it feels weird to do two different things here.

39 ↗(On Diff #343579)

Drop [[nodiscard]] (as discussed offline). Also applies to most other places where you use it.

Also, should this be promoted to a more general utility?

And also, this may be obvious to you, but why don't we simply use std::abs? Is it because http://eel.is/c++draft/iterator.primitives#range.iter.op.advance-6.1.1 uses absolute value in math notation (which is well-defined for all inputs), whereas std::abs is UB if the absolute value can't be represented in the return type?

std::abs isn't constexpr, so that's a no-go. I can promote it to a general utility. Which header would you like it in?

60–70 ↗(On Diff #343579)

I can do that, but it results in code duplication.

else if constexpr (bidirectional_iterator<_Ip>) {
  while (__n > 0) {
    --__n;
    ++_i;
  }
  while (__n < 0) {
    ++__n;
    --__i;
  }
}
else {
  while (__n > 0) {
    --__n;
    ++_i;
  }
}

I suppose I could put the forward case into an __advance_forward and call that twice. WDYT?

else if constexpr (bidirectional_iterator<_Ip>) {
  __advance_forward(__i, __n);
  __advance_backward(__i, __n);
}
else {
  __advance_forward(__i, __n);
}
99 ↗(On Diff #343448)

Also, again, please make sure to use _LIBCPP_NODISCARD_EXT for things that are non-nodiscard according to the Standard Itself. We can mark them, but we need to be clear that it's a libc++ extension.

Also, again, why do we need to be clear that it's an extension? What does _LIBCPP_NODISCARD_EXT offer us over using [[nodiscard]] and the user disabling the extension?

libc++ uses raw [[nodiscard]] only in places that the Standard Itself uses [[nodiscard]] — a rare occurrence.

That's because no one has gone to the effort of adding [[nodiscard]] to everything that should have it. I tried to change this for ranges in C++20, but LEWG felt the effort at the NB comment stage was to much when we had scores (if not hundreds) of other comments to look into and forward to LWG, so they asked me to defer to C++23. That's a paper I should revisit.

Because it has side effects: advancing the iterator. It's possible, and even likely, that users would only care about the side effects.

I still feel that this is information that the user shouldn't be implicitly discarding, but it looks like I've got @ldionne, @zoecarver, and @Quuxplusone against, so I'm going to remove it.

libcxx/include/iterator
550

Making an unqualified call to advance(i, s) will yield no matching function for call to '__convert_to_integral' otherwise. That's definitely an implementation detail leaking out of the interface, and suppresses what I think is the more natural diagnostic: no matching function for call to 'advance'.

If we decide to keep it, we should add a test. IIUC that would be considered a libc++ extension at this point based on glancing at https://reviews.llvm.org/D81425 again quickly.

I'll have a read and report my opinions here. I'm actually surprised that std::advance doesn't constrain this function on Distance being convertible to the iterator's distance type! That's probably an LWG defect there.

libcxx/test/support/test_iterators.h
783

Hmm that's a better name. I'm not really tracking the distance: I'm tracking the number of forward and backward operations. WDYT about

  • s/distance_traversed/operation_count/g
  • s/displacement/operation_displacement/g

With the exception of input iterators, tracking distance isn't useful since we'll very soon have std::ranges::distance. For the input iterator case, operation_count is synonymous.

cjdb added inline comments.
libcxx/include/iterator
550

After looking at D81425, I think the goals are different. D81425 takes a not-to-spec std::advance that has iterator_traits<I>::difference_type as its parameter and makes it to-spec by changing it to _Distance. As much as I don't like that, it's to-spec and so is a Good Thing.

What I'm doing here is constraining when std::advance can participate in overload resolution, which prevents this unfortunate diagnostic spew. There's always a diagnostic, but I'm changing what's presented to a user.

Yes, it's an extension, but I believe it's a conforming one, since the wording implies that n is convertible to an integral. See std::for_each_n, for an example (all the _n algorithms already do this), which @mclow.lists points out. I've also now sent off an LWG defect asking for a mandates paragraph to be applied retroactively all the way back to C++98, so hopefully this won't be an extension come year-end.

I may have a few more comments later.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/advance.pass.cpp
34

Nit: I think abs would make this clearer.

41

When would this not be exactly one?

41

Maybe i.distance_traversed() == 1 || n & i.distance_traversed() == 0.

78

Might as well test them all with N == 0.

113

I feel like there've been a few times where I could have used a type like this. Maybe move it into the test_iterators.h header?

128

What is the "assignable case"?

156

Why is 2 missing? If you're going to have seven, might as well have them all.

Edit: I see, maybe make a comment about why we can't use cpp20_iterator.

163

This suggestion might not actually be helpful, so feel free to just ignore it. But I was thinking, maybe we don't always want to test input iterator with N == 1, so maybe make this go 7, 6, 5, ...

192

If you dereference this, it should always be n, right? Maybe that's simpler and then we can get rid of expected_t.

cjdb updated this revision to Diff 345490.May 14 2021, 10:45 AM
cjdb marked 16 inline comments as done.

Applies feedback from @ldionne:

  • renames __iterator/primitives.h to __iterator/advance.h
  • adds __advance_forward and __advance_backward to simplify advance(i, s) overload
  • removes some [[nodiscard]]

Applies feedback from @zoecarver:

  • removes [[nodiscard]] from advance(i, n, s) overload
  • moves sentinel_wrapper into test_iterators.h
  • adds comment explaining why cpp20_input_iterator is missing
  • reverses the distance in some cases
cjdb added inline comments.May 14 2021, 10:47 AM
libcxx/include/__iterator/primitives.h
60–70 ↗(On Diff #343579)

PTAL.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/advance.pass.cpp
34

abs is not constexpr.

41

In the case where assignment happens, which has distance_traversed == 0.

128
192

The point of these tests is to confirm that?

libcxx/test/support/test_iterators.h
727

I've removed it for some areas, but kept it where I think calling and not using is error-prone.

cjdb updated this revision to Diff 345657.May 15 2021, 5:58 PM

rebases to activate CI

cjdb added inline comments.Fri, May 21, 10:36 AM
libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/advance.pass.cpp
41

That's really unclear. There are only two states: 0 or 1. I can see the case for wanting an explicit i.stride_count() == 0 || i.stride_count() == 1, but n & i.stride_count() == 0 is a strange way to word that.

cjdb updated this revision to Diff 347722.Tue, May 25, 10:37 AM

Changes requested by @zoecarver:

  • Replaces x <= 0 check with x == 0 or x == 1 check.

Changes requested by @Quuxplusone:

  • Replaces verify test with compile-time test.
  • Adds comment explaining why something non-standard has been added to std::ranges in the test file.

Changes requested by @ldionne:

  • Removes more [[nodiscard]] (still keeps a few that I think could result in bugginess).
ldionne accepted this revision.Tue, May 25, 12:26 PM
ldionne added inline comments.
libcxx/include/__iterator/advance.h
11

Needs the correct header guard.

This revision is now accepted and ready to land.Tue, May 25, 12:26 PM
This revision was automatically updated to reflect the committed changes.