`list` iterator implementation doesn't match Python semantics
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 forBoundListIterator - I think we might want to remove
DoubleEndedIterator for BoundListIteratorand 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
ExactSizeIteratoris incorrect, as a list cleared partway through iteration will yield fewer elements than thesize_hintpromises - similarly, we should reconsider what the correct implementation of
size_hintshould be (e.g. should the lower bound be 0, the upper boundNone?)
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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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