Skip to content

Implement nth_back for Zip iterator#152652

Open
veeceey wants to merge 1 commit intorust-lang:mainfrom
veeceey:feat/issue-54054-zip-nth-back
Open

Implement nth_back for Zip iterator#152652
veeceey wants to merge 1 commit intorust-lang:mainfrom
veeceey:feat/issue-54054-zip-nth-back

Conversation

@veeceey
Copy link

@veeceey veeceey commented Feb 15, 2026

Resolves the remaining Zip items from the tracking list in #54054.

The Zip iterator was missing a nth_back specialization, so calling .rev().step_by(n) (or any other pattern that ends up calling nth_back) on a zipped iterator would fall through to the default DoubleEndedIterator::nth_back, which just loops over next_back(). For TrustedRandomAccess iterators like slices, this turns what should be O(1) into O(n).

This adds nth_back at all three specialization levels in ZipImpl:

  • Default (zip_impl_general_defaults macro): delegates to a super_nth_back helper that calls next_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_unchecked indexing, with proper length-equalization on first backward call, side-effect execution for skipped elements (as required by the MAY_HAVE_SIDE_EFFECT contract), and panic-safe self.len updates before each unchecked access.

The implementation mirrors the existing nth specialization and next_back backward-trimming logic.

Test plan

  • Added test_zip_nth_back covering basic nth_back, exhaustion, and unequal-length iterators
  • Added test_zip_nth_back_after_next covering interleaved forward/backward iteration
  • Added test_zip_rev_nth_uses_nth_back covering the motivating use case (zip(..).rev().step_by(..))
  • All existing zip tests pass (including the side-effect and panic-safety tests)

Resolves remaining items from #54054.

@rustbot rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-libs Relevant to the library team, which will review and decide on the PR/issue. labels Feb 15, 2026
@rustbot
Copy link
Collaborator

rustbot commented Feb 15, 2026

r? @Mark-Simulacrum

rustbot has assigned @Mark-Simulacrum.
They will have a look at your PR within the next two weeks and either review your PR or reassign to another reviewer.

Use r? to explicitly pick a reviewer

Why was this reviewer chosen?

The reviewer was selected based on:

  • Owners of files modified in this PR: @scottmcm, libs
  • @scottmcm, libs expanded to 8 candidates
  • Random selection from Mark-Simulacrum, jhpratt, joboet, scottmcm

@rustbot

This comment has been minimized.

@rust-log-analyzer

This comment has been minimized.

@veeceey veeceey force-pushed the feat/issue-54054-zip-nth-back branch 2 times, most recently from d749dea to 3eb5fc4 Compare February 17, 2026 08:52
@rustbot

This comment has been minimized.

@rustbot

This comment has been minimized.

@rustbot rustbot added has-merge-commits PR has merge commits, merge with caution. S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. labels Feb 19, 2026
@veeceey
Copy link
Author

veeceey commented Feb 20, 2026

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`.
@veeceey veeceey force-pushed the feat/issue-54054-zip-nth-back branch from adbf42e to 001762e Compare February 20, 2026 05:59
@veeceey
Copy link
Author

veeceey commented Feb 20, 2026

Rebased to remove the merge commits. Should be clean now — sorry about that!

@rustbot
Copy link
Collaborator

rustbot commented Feb 20, 2026

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.

@rustbot rustbot removed S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. has-merge-commits PR has merge commits, merge with caution. labels Feb 20, 2026
@Mark-Simulacrum
Copy link
Member

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

@the8472 the8472 assigned the8472 and unassigned Mark-Simulacrum Feb 23, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-libs Relevant to the library team, which will review and decide on the PR/issue.

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants