@@ -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 )
0 commit comments