Skip to content

Commit ff1a5ce

Browse files
authored
Cache ancestor matches in the descendant combinator (#351)
1 parent 144deae commit ff1a5ce

3 files changed

Lines changed: 67 additions & 3 deletions

File tree

‎docs/src/markdown/about/changelog.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,8 @@ icon: lucide/scroll-text
9797
- **FIX**: Fix `:enabled` and `:disabled` never matching `input` elements with `type="hidden"`.
9898
- **FIX**: `:required` no longer matches `input` elements of types the `required` attribute does not apply to
9999
(`hidden`, `range`, `color`, `submit`, `image`, `reset` and `button`). Like in browsers, they match `:optional`.
100+
- **FIX**: Cache whether an element is or has a matching ancestor when matching the descendant combinator (`a b`) to
101+
avoid time that grows with the depth of the document to the power of the number of combinators.
100102

101103
## 3.0.4
102104

‎soupsieve/css_match.py‎

Lines changed: 33 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -614,6 +614,7 @@ def __init__(
614614
self.enable_cache = not bool(self.flags & util.NOCACHE)
615615
self.nth_cache: dict[Hashable, list[int]] = {}
616616
self.sib_cache: dict[Hashable, int] = {}
617+
self.anc_cache: dict[tuple[int, int], bool] = {}
617618
self.dir_cache: dict[int, int] = {}
618619
self.index_cache: dict[int, dict[int, int]] = {}
619620

@@ -648,6 +649,7 @@ def reset(self) -> None: # pragma: no cover
648649

649650
self.nth_cache.clear()
650651
self.sib_cache.clear()
652+
self.anc_cache.clear()
651653
self.dir_cache.clear()
652654
self.index_cache.clear()
653655

@@ -989,6 +991,31 @@ def match_general_sibling(self, el: bs4.Tag, relation: ct.SelectorList) -> Match
989991

990992
return found
991993

994+
def match_ancestor(self, el: bs4.Tag, relation: ct.SelectorList) -> MatchGenerator:
995+
"""
996+
Match descendant combinator.
997+
998+
A selector with several descendant combinators tries every ancestor for each one, which is
999+
a polynomial of the depth with a degree of the number of combinators. Every element visited
1000+
on the walk shares the result, so cache whether each one is or has a matching ancestor.
1001+
"""
1002+
1003+
found = False
1004+
visited: list[tuple[int, int]] = []
1005+
parent: bs4.Tag | None = el
1006+
while not found and parent and (parent := self.get_parent(parent)):
1007+
key = (id(parent), id(relation))
1008+
if key in self.anc_cache:
1009+
found = self.anc_cache[key]
1010+
break
1011+
visited.append(key)
1012+
found = yield parent, relation
1013+
1014+
for key in visited:
1015+
self.anc_cache[key] = found
1016+
1017+
return found
1018+
9921019
def match_past_relations(self, el: bs4.Tag, relation: ct.SelectorList) -> MatchGenerator:
9931020
"""Match past relationship."""
9941021

@@ -998,9 +1025,12 @@ def match_past_relations(self, el: bs4.Tag, relation: ct.SelectorList) -> MatchG
9981025
return found
9991026

10001027
if relation[0].rel_type == REL_PARENT:
1001-
parent: bs4.Tag | None = el
1002-
while not found and parent and (parent := self.get_parent(parent)):
1003-
found = parent is not None and (yield parent, relation)
1028+
if self.enable_cache:
1029+
found = yield from self.match_ancestor(el, relation)
1030+
else:
1031+
parent: bs4.Tag | None = el
1032+
while not found and parent and (parent := self.get_parent(parent)):
1033+
found = parent is not None and (yield parent, relation)
10041034
elif relation[0].rel_type == REL_CLOSE_PARENT:
10051035
parent = self.get_parent(el)
10061036
found = parent is not None and (yield parent, relation)

‎tests/test_level1/test_descendant.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,3 +28,35 @@ def test_long_duplicate_tag_case(self):
2828

2929
for n in (1000, 2000, 4000, 8000):
3030
self.assertEqual(sv.compile("a" + " " * n + "b").selectors.count, 2)
31+
32+
def test_shared_ancestors(self):
33+
"""Test that the result for an ancestor does not leak into elements that have other ancestors."""
34+
35+
markup = """
36+
<section id="1">
37+
<div id="2"><p id="3"><span id="4"></span></p></div>
38+
<p id="5"></p>
39+
</section>
40+
<div id="6"><p id="7"><span id="8"></span></p></div>
41+
<div id="9"><section id="10"><p id="11"><span id="12"></span></p></section></div>
42+
"""
43+
44+
self.assert_selector(markup, "section div p", ["3"], flags=util.HTML | util.NOCACHE)
45+
self.assert_selector(markup, "section p span", ["4", "12"], flags=util.HTML | util.NOCACHE)
46+
self.assert_selector(markup, "div p, section span", ["3", "4", "7", "11", "12"], flags=util.HTML | util.NOCACHE)
47+
self.assert_selector(markup, "div section p span", ["12"], flags=util.HTML | util.NOCACHE)
48+
self.assert_selector(markup, "section :not(div p)", ["2", "4", "5", "12"], flags=util.HTML | util.NOCACHE)
49+
50+
def test_many_descendant_combinators(self):
51+
"""Test that every combinator tries each ancestor once in a deeply nested document."""
52+
53+
import soupsieve as sv
54+
from bs4 import BeautifulSoup
55+
from unittest import mock
56+
57+
n = 32
58+
soup = BeautifulSoup("<div>" * n, "html.parser")
59+
match = sv.css_match.CSSMatch._match_selectors
60+
with mock.patch.object(sv.css_match.CSSMatch, "_match_selectors", autospec=True, side_effect=match) as patched:
61+
self.assertEqual(len(sv.select("section div div div div", soup)), 0)
62+
self.assertLessEqual(patched.call_count, 5 * n)

0 commit comments

Comments
 (0)