Implement nth_back for Zip iterator#152652
Conversation
|
rustbot has assigned @Mark-Simulacrum. Use Why was this reviewer chosen?The reviewer was selected based on:
|
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
d749dea to
3eb5fc4
Compare
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
|
Working on cleaning up the merge commits - will rebase properly to follow the no-merge policy. Sorry about that! |
The `Zip` iterator was missing a specialized `nth_back` implementation, causing it to fall back to the default `DoubleEndedIterator::nth_back` which calls `next_back()` in a loop. This is O(n) even for iterators that support efficient random access. This adds `nth_back` to all three `ZipImpl` specialization levels: - Default: delegates to `super_nth_back` (calls `next_back` in a loop, same as the trait default but going through the Zip dispatch) - TrustedRandomAccessNoCoerce: uses the default - TrustedRandomAccess: uses direct index-based access with proper side-effect handling and panic safety This completes the last three unchecked items from the tracking list (Zip, Zip in ZipImpl default fn, Zip in ZipImpl where TrustedRandomAccess). The performance impact is most visible when using patterns like `iter_a.zip(iter_b).rev().step_by(n)`, since `step_by` calls `nth` on the underlying iterator, and `Rev::nth` delegates to `nth_back`.
adbf42e to
001762e
Compare
|
Rebased to remove the merge commits. Should be clean now — sorry about that! |
|
This PR was rebased onto a different main commit. Here's a range-diff highlighting what actually changed. Rebasing is a normal part of keeping PRs up to date, so no action is needed—this note is just to help reviewers. |
|
@the8472 do you have bandwidth to take a look at this? I think you're our best (only?) domain owner for the unsafe iterator extension traits... |
Resolves the remaining Zip items from the tracking list in #54054.
The
Zipiterator was missing anth_backspecialization, so calling.rev().step_by(n)(or any other pattern that ends up callingnth_back) on a zipped iterator would fall through to the defaultDoubleEndedIterator::nth_back, which just loops overnext_back(). ForTrustedRandomAccessiterators like slices, this turns what should be O(1) into O(n).This adds
nth_backat all three specialization levels inZipImpl:zip_impl_general_defaultsmacro): delegates to asuper_nth_backhelper that callsnext_back()in a loop, same as the trait default but properly routed through the Zip dispatch.TrustedRandomAccessNoCoerce: inherits the default.TrustedRandomAccess: O(1) via direct__iterator_get_uncheckedindexing, with proper length-equalization on first backward call, side-effect execution for skipped elements (as required by theMAY_HAVE_SIDE_EFFECTcontract), and panic-safeself.lenupdates before each unchecked access.The implementation mirrors the existing
nthspecialization andnext_backbackward-trimming logic.Test plan
test_zip_nth_backcovering basic nth_back, exhaustion, and unequal-length iteratorstest_zip_nth_back_after_nextcovering interleaved forward/backward iterationtest_zip_rev_nth_uses_nth_backcovering the motivating use case (zip(..).rev().step_by(..))Resolves remaining items from #54054.