[Python-ideas] Mutating while iterating

[Aaron Brady]

On Wed, Aug 13, 2014 at 7:21 AM, Aaron Brady <castironpi at gmail.com> wrote:
> On Sun, Aug 3, 2014 at 12:46 PM, Aaron Brady <castironpi at gmail.com> wrote:
>> On Sat, Jul 26, 2014 at 10:39 PM, Nick Coghlan <ncoghlan at gmail.com> wrote:
[snip]
>>
>> Python is replete with examples of prohibiting structures which are
>> likely bugs but aren't segfaults.  There are also reciprocal-- though
>> not necessarily inverse-- limitations of the unordered collections
>> themselves ("set" and "dict").  The new behavior is transparent for
>> the programmer; no possible programs can /rely/ on the existing
>> behavior.  The new behavior introduces no new objects, possibly except
>> "IterationError", no new syntax, and no new costs.
>>
>> I propose we leave this discussion thread open for the time being.  I
>> also take the issue of /re/-assigning to keys during iteration to be
>> settled as permitted.
>
> Nick, It works by comparing the state of the container, to its state
> when the iterator was opened.  We're ensuring it will always have a
> unique state, up to comparison.  A state can be reused once no
> iterators refer to it, hence needing the reference count.  A full
> "object" is not needed for a memo, only the reference count, but the
> "object" is easier and only twice the size, as "PyBaseObject Type" is
> allocated anyway.
>
> I'll point out that among the additional costs that there aren't,
> garbage collection isn't any slower, as both "tp traverse" and "tp
> clear" are empty in the "PyBaseObject Type" definition, on line
> 3511-3512 in "typeobject.c" at time of writing [1].
>
> [1] http://svn.python.org/view/python/trunk/Objects/typeobject.c?revision=81744&view=markup#l3511

For ordered containers, there are several consistent behaviors if
there's an iterator on the element being removed.

1) Always advance
2) Always retreat
3) Always close
4) Specified in iterator / reverse iter's
5) Specified by "remove" caller

Iterators could define a 3rd method for it, or 4th counting "prev".
Iterators might be invalidated permanently or until the next call to
"Next" in some languages, after the mutating call.  It raises the
issue of when there's an iterator on the first or last item and it's
removed (and others are inserted there).

The same sentinel value can't be used before it's started and after
it's finished.  Either the container or the iterator needs extra
storage to distinguish.  Though the sizes can be kept the same by
changing the semantics slightly.