On Tue, Jul 15, 2025 at 11:56 AM Jonathan Wakely <jwak...@redhat.com> wrote:
> On Tue, 15 Jul 2025 at 09:25, Tomasz Kaminski <tkami...@redhat.com> wrote:
> >
> >
> >
> > On Mon, Jul 14, 2025 at 10:43 PM Jonathan Wakely <jwak...@redhat.com>
> wrote:
> >>
> >> The standard specifies some of the effects of ranges::advance in terms
> >> of "Equivalent to:" and it's observable that our current implementation
> >> deviates from the precise specification in the standard. This was
> >> causing some failures in the libc++ testsuite.
> >>
> >> For the sized_sentinel_for<I, S> case I optimized our implementation to
> >> avoid redundant calls when we have already checked that there's nothing
> >> to do. We were eliding `advance(i, bound)` when the iterator already
> >> equals the sentinel, and eliding `advance(i, n)` when `n` is zero. In
> >> both cases, removing the seemingly redundant calls is not equivalent to
> >> the spec because `i = std::move(bound)` or `i += 0` operations can be
> >> observed by program-defined iterators. This patch inlines the observable
> >> side effects of advance(i, bound) or advance(i, 0) without actually
> >> calling those functions.
> >>
> >> For the non-sized sentinel case, `if (i == bound || n == 0)` is
> >> different from `if (n == 0 || i == bound)` for the case where n is zero
> >> and a program-defined iterator observes the number of comparisons.
> >> This patch changes it to do `n == 0` first. I don't think this is
> >> required by the standard, as this condition is not "Equivalent to:" any
> >> observable sequence of operations, but testing `n == 0` first is
> >> probably cheaper anyway.
> >>
> >> libstdc++-v3/ChangeLog:
> >>
> >> * include/bits/ranges_base.h (ranges::advance(i, n, bound)):
> >> Ensure that observable side effects on iterators match what is
> >> specified in the standard.
> >> ---
> >>
> >> For most iterator types, I assume the compiler will inline these extra
> >> redundant operations, so they'll only make a difference for iterators
> >> that do actually observe the number of operations.
> >>
> >> Tested powerpc64le-linux.
> >
> > LGTM
> >>
> >>
> >> libstdc++-v3/include/bits/ranges_base.h | 18 +++++++++++++++---
> >> 1 file changed, 15 insertions(+), 3 deletions(-)
> >>
> >> diff --git a/libstdc++-v3/include/bits/ranges_base.h
> b/libstdc++-v3/include/bits/ranges_base.h
> >> index 0251e5d0928a..4a0b9e2f5ec3 100644
> >> --- a/libstdc++-v3/include/bits/ranges_base.h
> >> +++ b/libstdc++-v3/include/bits/ranges_base.h
> >> @@ -882,7 +882,14 @@ namespace ranges
> >> const auto __diff = __bound - __it;
> >
> > Would you mind changing this iter_difference_t<_It>, this is required to
> be exactly that type,
>
> Yes, if that helps with reading the code, let's be explicit about the
> type. I've made that change.
>
> > but I think it would help me with understanding (see comment below)
> >>
> >>
> >> if (__diff == 0)
> >> - return __n;
> >> + {
> >> + // inline any possible side effects of advance(it,
> bound)
> >> + if constexpr (assignable_from<_It&, _Sent>)
> >> + __it = std::move(__bound);
> >> + else if constexpr (random_access_iterator<_It>)
> >> + __it += 0;
> >> + return __n;
> >> + }
> >> else if (__diff > 0 ? __n >= __diff : __n <= __diff)
> >
> > I was wondering if we should check precondition __glibcxx_assert((__n <
> 0) == (__diff < 0)),
> > but then I realized that we never enter this branch, if __n and __diff
> disagree on direction.
>
> Right. The standard says to check |n| >= |diff| and if we did that,
> then we would need to check that the directions agree. But that would
> mean abs(n) >= abs(diff) which would be three comparisons and we'd
> also need to check the directions agree. The way I implemented it only
> does two, and implicitly checks the directions agree. If they don't
> agree then we take the next branch and fail the assertion there.
>
> It's not necessarily better code the way I did the comparisons, at
> least not with GCC:
> https://godbolt.org/z/P6cc7s3WP
> But it avoids needing two assertions, so that should be less code for
> the entire function.
>
> If assertions are disabled then we take the "wrong" branch and do
> advance(i, n) instead of advance(i, bound), but that case is UB anyway
> so there is no "wrong" outcome. However, now that I think about it,
> maybe advance(i, bound) would be safer for the UB case, if we assume
> that the sentinel is the correct bound. Advancing by an incorrect
> value of n (in the wrong direction) might take us out of bounds,
> whereas advance(i, bound) will not, assuming a correct bound.
>
I am not sure, if one direction disagrees, then I am not sure if betting on
sentinel
being correct is any more likely than n being correct. So I am fine with
leaving this as is.
>
> > And both __n and __diff are or iter_different_t, so there is no chance
> of signed->unsigned promotion.
>
> Yeah.
>
>
