Description
`Element.findall()` and fully-consumed `Element.iterfind()` exhibit `O(n^2)` time complexity when using XPath index predicates (e.g. `[1]`, `[last()]`, `[last()-N]`) on XML documents with many same-tag siblings. `Element.find()` is only affected when the first match is near the end of the sibling list, such as with `[last()]` or `[last()-N]`; `.//item[1]` short-circuits after the first match.
Affected products
Version statuses are supplied by the assigning organization. Consult the original record for detailed ranges and platform conditions.
Python Software Foundation CPython
Default version status: unaffected
0 to < 3.10.21affected3.11.0 to < 3.11.16affected3.12.0 to < 3.12.14affected3.13.0 to < 3.13.15affected3.14.0 to < 3.14.7affected3.15.0a1 to < 3.15.0rc1affected
References
- https://github.com/python/cpython/pull/152676 ↗
- https://github.com/python/cpython/issues/152674 ↗
- https://mail.python.org/archives/list/security-announce@python.org/thread/7YMZ6DDZVR26TJJBVO3RDNBAVGHNYAKR/ ↗
- https://github.com/python/cpython/commit/2ffab083782968a4d732738f4f1dff6bbd69d2b0 ↗
- https://github.com/python/cpython/commit/02c08e6b747ac43d0d866a4ffa916bedf3423f81 ↗
- https://github.com/python/cpython/commit/390337b8ba1658833fdef379e1739c9f9533a8db ↗
- https://github.com/python/cpython/commit/cb409342a19f25656f62e679f8bac265fe1442c3 ↗
- https://github.com/python/cpython/commit/96510a3758f4a075f43223afdee3b6ee1a7a7f02 ↗
- https://github.com/python/cpython/commit/037965c00a427cba5c05447efadc67c51a492e85 ↗
- https://github.com/python/cpython/commit/0583f24ae678993e3f7939f51ad5bcae5ad9dc70 ↗