FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

[3.13] gh-152674: Avoid quadratic behavior in xml.etree.ElementPath index predicates (GH-152676) by miss-islington · Pull Request #154811 · python/cpython · GitHub

/ cpython Public
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension .py  (2) .rst  (1) All 2 file types selected
Viewed files
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Unified
Split
Hide whitespace
Diff view
Unified
Split
Hide whitespace
31 changes: 31 additions & 0 deletions Lib/test/test_xml_etree.py
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Original file line number Diff line number Diff line change
Expand Up @@ -3352,6 +3352,37 @@ def test_find_xpath(self):
self.assertRaisesRegex(SyntaxError, 'XPath', e.find, './tag[last()-0]')
self.assertRaisesRegex(SyntaxError, 'XPath', e.find, './tag[last()+1]')

def test_find_xpath_index_no_quadratic_complexity(self):
class CountingElement(ET.Element):
findall_calls = 0
def findall(self, *args, **kwargs):
type(self).findall_calls += 1
return super().findall(*args, **kwargs)

def work(n, pattern):
root = CountingElement("root")
for _ in range(n):
ET.SubElement(root, "a")
CountingElement.findall_calls = 0
root.findall(pattern)
return CountingElement.findall_calls

for pattern in [".//a[1]", ".//a[last()]"]:
w1 = work(1024, pattern)
w2 = work(2048, pattern)
w3 = work(4096, pattern)

self.assertGreater(w1, 0)
r1 = w2 / w1
r2 = w3 / w2
# Doubling N must not ~double the parent.findall calls.
# Linear-in-N call counts indicate the cache is missing.
self.assertLess(
max(r1, r2), 1.5,
msg=f"Possible quadratic behavior on {pattern!r}: "
f"calls={w1, w2, w3} ratios={r1, r2}",
)

def test_findall(self):
e = ET.XML(SAMPLE_XML)
e[2] = ET.XML(SAMPLE_SECTION)
Expand Down
17 changes: 12 additions & 5 deletions Lib/xml/etree/ElementPath.py
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Original file line number Diff line number Diff line change
Expand Up @@ -324,15 +324,22 @@ def select_negated(context, result):
index = -1
def select(context, result):
parent_map = get_parent_map(context)
cache = {}
for elem in result:
try:
parent = parent_map[elem]
except KeyError:
continue
key = (parent, elem.tag)
if key not in cache:
# FIXME: what if the selector is "*" ?
elems = list(parent.findall(elem.tag))
if elems[index] is elem:
yield elem
except (IndexError, KeyError):
pass
elems = parent.findall(elem.tag)
try:
cache[key] = elems[index]
except IndexError:
cache[key] = None
if cache[key] is elem:
yield elem
return select
raise SyntaxError("invalid predicate")

Expand Down
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Original file line number Diff line number Diff line change
@@ -0,0 +1,6 @@
The :class:`xml.etree.ElementTree.Element` methods
:meth:`~xml.etree.ElementTree.Element.findall`,
:meth:`~xml.etree.ElementTree.Element.iterfind` and
:meth:`~xml.etree.ElementTree.Element.find` avoid quadratic behavior when
using XPath index predicates (``[1]``, ``[last()]``, ``[last()-N]``) on XML
documents with many same-tag siblings.
Loading

Back | FazBrowse Home | New Git URL