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)
I have studied our
BoundListIteratorimplementation as part of #6086. I observed a few ways in which our implementations are subtly wrong / diverge from Python.TLDR:
impl ExactSizeIterator for BoundListIteratorsize_hint()should be forBoundListIteratorDoubleEndedIterator for BoundListIteratorand split the type into separate forward and reverse list iterators.FusedIterator- see comment belowGiven 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:
ExactSizeIteratoris incorrect, as a list cleared partway through iteration will yield fewer elements than thesize_hintpromisessize_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
DoubleEndedIteratorimplementation. 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
DoubleEndedIteratorwe need to snapshot a logical "back" of the list so we can produce values fornth_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)