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.
> And both __n and __diff are or iter_different_t, so there is no chance of
> signed->unsigned promotion.
Yeah.
