PyO3 / PyO3/pyo3

`list` iterator implementation doesn't match Python semantics

Open
#6,087 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
16.2k
Forks
1k
Avg merge
2d 6h
Merged PRs (30d)
66

Description

I have studied our BoundListIterator implementation as part of #6086. I observed a few ways in which our implementations are subtly wrong / diverge from Python.

TLDR:

  • I think we need to remove impl ExactSizeIterator for BoundListIterator
  • We might need to reconsider what the size_hint() should be for BoundListIterator
  • I think we might want to remove DoubleEndedIterator for BoundListIterator and split the type into separate forward and reverse list iterators.
  • We need to remove FusedIterator - see comment below

Given this would be somewhat breaking, and it's been wrong for a while, I would prefer we didn't rush this into the 0.29 release and instead consider exactly how we achieve this for the 0.30 release.


First, I'll note that Python lists may legally change size during iteration. We even handle this in many methods by checking the current list length on each iteration. This means that, at a minimum:

  • our implementation of ExactSizeIterator is incorrect, as a list cleared partway through iteration will yield fewer elements than the size_hint promises
  • similarly, we should reconsider what the correct implementation of size_hint should be (e.g. should the lower bound be 0, the upper bound None?)

Secondly, Python lists use separate iterators for forward and reverse iteration. We have a single DoubleEndedIterator implementation. This leads to a key difference in forward iteration: when we start iteration, we snapshot the list length and will never yield more items if the list is appended to during iteration. In Python, a forward iterator will yield additional items if the list is appended during iteration (it's even possible to create infinite loops in Python this way).

I think as long as we support DoubleEndedIterator we need to snapshot a logical "back" of the list so we can produce values for nth_back, so we necessarily diverge from Python here. If we are to make changes to list iterators anyway, I think splitting into separate forward and reverse iterators would allow us to match Python better.

(Note that while #6086 also addresses tuple iterators, they are not relevant here, as tuples are fixed size and so our implementation for tuples is fully correct)

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the BoundListIterator implementation and the Python list iterator behavior described in this issue. Determine the intended size_hint contract and whether forward and reverse iteration should be separate rather than using DoubleEndedIterator. Done means the iterator traits and mutation behavior match the agreed Python semantics, with the breaking changes considered for the 0.30 release.

Written by the indexing model from the issue text.

Assessment

Tech stack
python, rust
Domain
api
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.