| 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) |