Issue 25873: Faster ElementTree iterating

Proposed patch refactors and optimize the code for iterating ElementTree. Refactoring and minor optimization makes the code about 30 lines smaller and 2-3% faster. Using a continuous array instead of linked list makes the code up to 40% faster (lxml benchmark was used to measurement).

In addition the patch fixes possible issue with owning references.

Looks technically correct as far as my knowledge of the malloc routines goes. What was the problem with references that you fixed? Maybe with parent_stack_push_new() failure?

The main reference counting bug that sticks out to me is with the text and tail elements, because element_get_text() etc return a borrowed reference. It might be good to fix this while you are at it:

>>> element = Element("tag")
>>> class Text:
...     def __bool__(self):
...         element.text = "changed"
...         return True
... 
>>> element.text = Text()
>>> i = element.itertext()
>>> next(i)
Segmentation fault (core dumped)
[Exit 139]

Good catch Martin. I missed this case. Following patch fixes it.

Other bugs look similar. They presumably can be triggered when remove the element itself during executing the __next__() method. I have no a reproducer though.

I don't know wherever it is worth to fix these bugs in maintained releases.

The new changes look good.

I see these kind of reference counting bugs as fairly low priority. I suspect there are plenty more in this module, at least Issue 24103 and Issue 24104.

Thank you for your review Martin. I have opened a separate issue25902 for refcount bugs in iteration. Its patch is purposed for all versions, while this issue is for developer version only.

New changeset 5a5d5268afd5 by Serhiy Storchaka in branch 'default':
Issue #25873: Optimized iterating ElementTree.
https://hg.python.org/cpython/rev/5a5d5268afd5

messages: + msg256502