Debian Codegraph @

url_matcher/matcher.py

raw
1 """
2 The matcher module contains the UrlMatcher class.
3 """
4
5 from __future__ import annotations
6
7 from collections.abc import Iterable, Iterator, Mapping
8 from dataclasses import dataclass, field
9 from itertools import chain
10 from typing import Any
11
12 from url_matcher.patterns import PatternMatcher, get_pattern_domain, hierarchical_str
13 from url_matcher.util import get_domain
14
15
16 @dataclass(init=False, frozen=True)
17 class Patterns:
18 include: tuple[str, ...]
19 exclude: tuple[str, ...]
20 priority: int
21
22 def __init__(self, include: list[str], exclude: list[str] | None = None, priority: int = 500):
23 # The initialization is manually set so that we can support an API of
24 # accepting and returning lists. However, tuples are being used underneath
25 # that class so that the attributes are truly immutable, in addition to
26 # being frozen=True.
27 # Using lists are far less likely to have human typing mistakes compared to
28 # tuples since the trailing `,` char can easily be missed out. For
29 # example:
30 # * ("element") is not the same as ("element",) which is a tuple.
31 # Lastly, the manner of how we set the attribute values below is in line
32 # with how Python's own `dataclasses` library assign attributes to frozen
33 # classes. Here's a reference:
34 # * https://github.com/python/cpython/blob/v3.10.2/Lib/dataclasses.py#L1117-L1120
35 object.__setattr__(self, "include", tuple(include))
36 object.__setattr__(self, "exclude", tuple(exclude or []))
37 object.__setattr__(self, "priority", priority)
38
39 def get_domains(self) -> list[str]:
40 domains = [get_pattern_domain(pattern) for pattern in self.include]
41 # remove duplicate domains preserving the order
42 return list(dict.fromkeys(domain for domain in domains if domain))
43
44 def get_includes_without_domain(self) -> list[str]:
45 return [pattern for pattern in self.include if get_pattern_domain(pattern) is None]
46
47 def all_includes_have_domain(self) -> bool:
48 """Return true if all the include patterns have a domain"""
49 return not self.get_includes_without_domain()
50
51 def is_universal_pattern(self) -> bool:
52 """Return true if there are no include patterns or they are empty. A universal pattern matches any domain"""
53 return not any(pattern for pattern in self.include)
54
55 def get_includes_for(self, domain: str) -> list[str]:
56 return [pattern for pattern in self.include if get_pattern_domain(pattern) == domain]
57
58
59 @dataclass
60 class PatternsMatcher:
61 identifier: Any
62 patterns: Patterns
63 include_matchers: list[PatternMatcher] = field(init=False)
64 exclude_matchers: list[PatternMatcher] = field(init=False)
65
66 def __post_init__(self) -> None:
67 self.include_matchers = [PatternMatcher(pattern) for pattern in self.patterns.include]
68 self.exclude_matchers = [PatternMatcher(pattern) for pattern in self.patterns.exclude]
69
70 def match(self, url: str) -> bool:
71 if self.include_matchers:
72 for include in self.include_matchers:
73 if include.match(url):
74 break
75 else:
76 return False
77 return not any(exclude.match(url) for exclude in self.exclude_matchers)
78
79
80 class IncludePatternsWithoutDomainError(ValueError):
81 def __init__(self, *args: Any, identifier: Any, patterns: Patterns, wrong_patterns: list[str]):
82 super().__init__(*args)
83 self.id = identifier
84 self.patterns = patterns
85 self.wrong_patterns = wrong_patterns
86
87
88 class URLMatcher:
89 def __init__(self, data: Mapping[Any, Patterns] | Iterable[tuple[Any, Patterns]] | None = None):
90 """
91 A class that matches URLs against a list of patterns, returning
92 the identifier of the rule that matched the URL.
93
94 Example usage::
95
96 matcher = URLMatcher()
97 matcher.add_or_update(1, Patterns(include=["example.com/product"]))
98 matcher.add_or_update(2, Patterns(include=["other.com"]))
99
100 assert matcher.match("http://example.com/product/a_product.html") == 1
101 assert matcher.match("http://other.com/a_different_page") == 2
102
103 :param data: A map or a list of tuples with identifier, patterns pairs to
104 initialize the object from
105 """
106 self.matchers_by_domain: dict[str, list[PatternsMatcher]] = {}
107 self.matchers_universal: list[PatternsMatcher] = []
108 self.patterns: dict[Any, Patterns] = {}
109
110 if data:
111 items = data.items() if isinstance(data, Mapping) else data
112 for identifier, patterns in items:
113 self.add_or_update(identifier, patterns)
114
115 def add_or_update(self, identifier: Any, patterns: Patterns) -> None:
116 if not patterns.all_includes_have_domain() and not patterns.is_universal_pattern():
117 wrong_patterns = [p for p in patterns.get_includes_without_domain() if p]
118 raise IncludePatternsWithoutDomainError(
119 f"All include patterns must belong to a domain "
120 f"but the patterns {wrong_patterns} doesn't. "
121 f"For example, the include pattern '/product/* "
122 f"is invalid whereas the pattern 'example.com/product/*' isn't. "
123 f"The only exception is the empty pattern which matches everything "
124 f"and it is allowed. "
125 f"identifier: {identifier}.",
126 identifier=identifier,
127 patterns=patterns,
128 wrong_patterns=wrong_patterns,
129 )
130 if identifier in self.patterns:
131 self.remove(identifier)
132 self.patterns[identifier] = patterns
133 matcher = PatternsMatcher(identifier, patterns)
134 for domain in patterns.get_domains():
135 self._add_matcher(domain, matcher)
136 if patterns.is_universal_pattern():
137 self._add_matcher("", matcher)
138
139 def remove(self, identifier: Any) -> None:
140 patterns = self.patterns.get(identifier)
141 if not patterns:
142 return
143 del self.patterns[identifier]
144 for domain in patterns.get_domains():
145 self._del_matcher(domain, identifier)
146 if patterns.is_universal_pattern():
147 self._del_matcher("", identifier)
148
149 def get(self, identifier: Any) -> Patterns | None:
150 return self.patterns.get(identifier)
151
152 def match(self, url: str, *, include_universal: bool = True) -> Any | None:
153 return next(self.match_all(url, include_universal=include_universal), None)
154
155 def match_all(self, url: str, *, include_universal: bool = True) -> Iterator[Any]:
156 domain = get_domain(url)
157 matchers: Iterable[PatternsMatcher] = self.matchers_by_domain.get(domain) or []
158 if include_universal:
159 matchers = chain(matchers, self.matchers_universal)
160 for matcher in matchers:
161 if matcher.match(url):
162 yield matcher.identifier
163
164 def match_universal(self) -> Iterator[Any]:
165 return (m.identifier for m in self.matchers_universal)
166
167 def _sort_domain(self, domain: str) -> None:
168 """
169 Sort all the rules within a domain so that the matching can be done in sequence:
170 the first rule matching wins.
171
172 A total ordering is defined. This is ensured by using including
173 the identifier in the sorting criteria
174
175 Sorting criteria:
176 * Priority (descending)
177 * Sorted list of includes for this domain (descending)
178 * Rule identifier (descending)
179 """
180
181 def sort_key(matcher: PatternsMatcher) -> tuple[int, list[str], Any]:
182 sorted_includes = sorted(map(hierarchical_str, matcher.patterns.get_includes_for(domain)))
183 return (matcher.patterns.priority, sorted_includes, matcher.identifier)
184
185 self.matchers_by_domain[domain].sort(key=sort_key, reverse=True)
186 self.matchers_universal.sort(key=sort_key, reverse=True)
187
188 def _del_matcher(self, domain: str, identifier: Any) -> None:
189 matchers = self.matchers_by_domain[domain]
190 for idx in range(len(matchers)):
191 if matchers[idx].identifier == identifier:
192 del matchers[idx]
193 break
194 if not matchers:
195 del self.matchers_by_domain[domain]
196 for idx in range(len(self.matchers_universal)):
197 if self.matchers_universal[idx].identifier == identifier:
198 del self.matchers_universal[idx]
199 break
200
201 def _add_matcher(self, domain: str, matcher: PatternsMatcher) -> None:
202 # FIXME: This can be made much more efficient if we insert the data directly in order instead of resorting.
203 # The bisect module could be used for this purpose.
204 # I'm leaving it for the future as insertion time is not critical.
205 self.matchers_by_domain.setdefault(domain, []).append(matcher)
206 if domain == "":
207 self.matchers_universal.append(matcher)
208 self._sort_domain(domain)