Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/dulwich/wildmatch.py: 10%
Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# wildmatch.py -- Git's wildmatch() pattern language
2# Copyright (C) 2026 Vincent Gao <gaobing1230@gmail.com>
3#
4# SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
5# Dulwich is dual-licensed under the Apache License, Version 2.0 and the GNU
6# General Public License as published by the Free Software Foundation; version 2.0
7# or (at your option) any later version. You can redistribute it and/or
8# modify it under the terms of either of these two licenses.
9#
10# Unless required by applicable law or agreed to in writing, software
11# distributed under the License is distributed on an "AS IS" BASIS,
12# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13# See the License for the specific language governing permissions and
14# limitations under the License.
15#
16# You should have received a copy of the licenses; if not, see
17# <http://www.gnu.org/licenses/> for a copy of the GNU General Public License
18# and <http://www.apache.org/licenses/LICENSE-2.0> for a copy of the Apache
19# License, Version 2.0.
20#
22r"""Git's wildmatch() pattern language.
24Git matches ``.gitignore`` and ``.gitattributes`` patterns with the same
25``wildmatch()`` (``wildmatch.c``) under ``WM_PATHNAME``, so the grammar is
26shared between :mod:`dulwich.ignore` and :mod:`dulwich.attrs`. It is not
27:mod:`fnmatch`, whose semantics neither file follows:
29* ``*`` and ``?`` never match ``/``; only a whole ``**`` component does.
30* ``^`` negates a bracket class exactly like ``!`` (``NEGATE_CLASS2``).
31* ``[:alpha:]`` and the eleven other POSIX classes are supported.
32* A backslash escapes the following member, so ``[a\-c]`` is ``a``, ``-``, ``c``
33 rather than the range ``\`` to ``c``.
34* A bracket expression never matches ``/``, not even a negated one.
35* A malformed bracket expression raises :exc:`MalformedPattern`; callers that
36 read a whole file of patterns should catch it per pattern and warn, rather
37 than let one bad line abort the load.
38"""
40__all__ = [
41 "MalformedPattern",
42 "translate",
43 "translate_bracket_expression",
44]
46import re
47from collections.abc import Sequence
49_SLASH = 0x2F
51# Git's character classes come from sane-ctype.h and are ASCII-only; the
52# sane_ctype[] table has no entries in the 128.. range. '/' is left out of
53# every class because a bracket expression can never match it.
54_POSIX_CLASSES = {
55 b"alnum": rb"0-9A-Za-z",
56 b"alpha": rb"A-Za-z",
57 b"blank": b"\\t ",
58 b"cntrl": b"\\x00-\\x1f\\x7f",
59 b"digit": rb"0-9",
60 b"graph": rb"!-.0-~",
61 b"lower": rb"a-z",
62 b"print": rb" -.0-~",
63 b"punct": rb"!-.:-@\[-`{-~",
64 b"space": b"\\t\\n\\r ",
65 b"upper": rb"A-Z",
66 b"xdigit": rb"0-9A-Fa-f",
67}
70class MalformedPattern(Exception):
71 """A pattern Git's wildmatch() gives up on (WM_ABORT_ALL).
73 Such a pattern matches nothing at all, not even literally.
74 """
77def _render(members: list[tuple[int, int]]) -> bytes:
78 """Render member ranges, dropping '/' and ranges that cannot match."""
79 out = []
80 for low, high in members:
81 for a, b in ((low, min(high, _SLASH - 1)), (max(low, _SLASH + 1), high)):
82 if a > b:
83 continue
84 piece = re.escape(bytes([a]))
85 if a != b:
86 piece += b"-" + re.escape(bytes([b]))
87 out.append(piece)
88 return b"".join(out)
91def _posix_class(
92 pattern: bytes, i: int, members: list[tuple[int, int]], classes: list[bytes]
93) -> tuple[int, int | None]:
94 """Consume a ``[:name:]`` starting at ``pattern[i]``."""
95 start = i + 2
96 j = start
97 while j < len(pattern) and pattern[j : j + 1] != b"]":
98 j += 1
99 if j >= len(pattern):
100 raise MalformedPattern(pattern)
101 if j == start or pattern[j - 1 : j] != b":":
102 # No closing ":]", so wildmatch() backs up and takes '[' as a member.
103 members.append((0x5B, 0x5B))
104 return start - 2, 0x5B
105 try:
106 classes.append(_POSIX_CLASSES[pattern[start : j - 1]])
107 except KeyError:
108 raise MalformedPattern(pattern) from None
109 return j, None
112def translate_bracket_expression(pattern: bytes, i: int) -> tuple[int, bytes]:
113 """Translate the bracket expression opened by ``pattern[i - 1]``.
115 Args:
116 pattern: Pattern being translated
117 i: Index just past the opening ``[``
118 Returns:
119 Tuple of the index just past the closing ``]`` and the regex fragment
120 Raises:
121 MalformedPattern: if wildmatch() would refuse the pattern outright
122 """
123 n = len(pattern)
124 negated = pattern[i : i + 1] in (b"!", b"^")
125 if negated:
126 i += 1
127 members: list[tuple[int, int]] = []
128 classes: list[bytes] = []
129 prev: int | None = None
130 first = True
131 while True:
132 if i >= n:
133 raise MalformedPattern(pattern)
134 c = pattern[i : i + 1]
135 if c == b"]" and not first:
136 break
137 first = False
138 if c == b"\\":
139 i += 1
140 if i >= n:
141 raise MalformedPattern(pattern)
142 prev = pattern[i]
143 members.append((prev, prev))
144 elif (
145 c == b"-"
146 and prev is not None
147 and i + 1 < n
148 and pattern[i + 1 : i + 2] != b"]"
149 ):
150 i += 1
151 if pattern[i : i + 1] == b"\\":
152 i += 1
153 if i >= n:
154 raise MalformedPattern(pattern)
155 if prev <= pattern[i]:
156 members[-1] = (prev, pattern[i])
157 # An inverted range matches nothing, but wildmatch() has already
158 # taken the low end as a plain member by the time it sees the '-',
159 # so "[z-a]" still matches "z"; leave that member in place.
160 prev = None
161 elif c == b"[" and pattern[i + 1 : i + 2] == b":":
162 i, prev = _posix_class(pattern, i, members, classes)
163 else:
164 prev = pattern[i]
165 members.append((prev, prev))
166 i += 1
167 body = _render(members) + b"".join(classes)
168 if negated:
169 return i + 1, b"[^/" + body + b"]"
170 if not body:
171 # Well-formed but unmatchable, e.g. [z-a] or [/].
172 return i + 1, b"(?!)"
173 return i + 1, b"[" + body + b"]"
176def _translate_segment(segment: bytes) -> bytes:
177 """Translate a single path segment to regex, following Git rules exactly."""
178 if segment == b"*":
179 return b"[^/]+"
181 res = b""
182 i, n = 0, len(segment)
183 while i < n:
184 c = segment[i : i + 1]
185 i += 1
186 match c:
187 case b"*":
188 # Collapse a run of consecutive '*' into a single quantifier.
189 # Within a segment repeated '*' are redundant ([^/]*[^/]* is
190 # equivalent to [^/]*), and emitting one quantifier per star
191 # builds a regex with adjacent unbounded quantifiers that
192 # backtracks catastrophically on non-matching input (ReDoS).
193 while i < n and segment[i : i + 1] == b"*":
194 i += 1
195 res += b"[^/]*"
196 case b"?":
197 res += b"[^/]"
198 case b"\\":
199 if i < n:
200 res += re.escape(segment[i : i + 1])
201 i += 1
202 else:
203 res += re.escape(c)
204 case b"[":
205 i, bracket = translate_bracket_expression(segment, i)
206 res += bracket
207 case _:
208 res += re.escape(c)
209 return res
212def _split_segments(pat: bytes) -> list[bytes]:
213 """Split a pattern into path segments, skipping slashes inside brackets.
215 wildmatch() itself walks the whole pattern in one pass rather than
216 splitting it, so a bracket expression may span a ``/`` (it just can
217 never match one). This function exists only so :func:`_translate` can
218 special-case ``**`` per segment; it must respect the same bracket
219 boundaries a one-pass walk would, which is why it can't just call
220 ``pat.split(b"/")``.
221 """
222 if b"[" not in pat:
223 return pat.split(b"/")
224 segments = []
225 start = i = 0
226 while i < len(pat):
227 c = pat[i : i + 1]
228 if c == b"\\" and i + 1 < len(pat):
229 i += 2
230 elif c == b"[":
231 i, _bracket = translate_bracket_expression(pat, i + 1)
232 else:
233 if c == b"/":
234 segments.append(pat[start:i])
235 start = i + 1
236 i += 1
237 segments.append(pat[start:])
238 return segments
241def _translate_double_asterisk(segments: Sequence[bytes], i: int) -> bytes:
242 """Handle ** segment processing, returns the regex part.
244 A run of consecutive ``**`` segments is collapsed to one by
245 :func:`_translate` before this is called, so each ``**`` is handled on
246 its own here.
247 """
248 # Check if ** is at end
249 remaining = segments[i + 1 :]
250 if all(s == b"" for s in remaining):
251 if remaining:
252 # Trailing "**/" is a directory pattern, so it has to consume at
253 # least one directory and end in a slash. Without this, "abc/**/"
254 # also matches "abc/" itself and every file directly inside it,
255 # while Git only ignores the directories below "abc".
256 return b".*/"
257 # ** at end - matches everything
258 return b".*"
260 # ** in middle - handle differently depending on what follows
261 if i == 0:
262 # ** at start - any prefix
263 return b"(?:.*/)??"
264 # ** in middle - match zero or more complete directory segments
265 return b"(?:[^/]+/)*"
268def _collapse_double_asterisks(segments: list[bytes]) -> list[bytes]:
269 """Collapse a run of consecutive ``**`` segments into a single one.
271 In Git a run of directory-spanning ``**`` segments is equivalent to a
272 single ``**``. Emitting one quantifier per segment builds a regex with
273 adjacent unbounded quantifiers (e.g. ``(?:[^/]+/)*(?:[^/]+/)*``) that
274 backtracks catastrophically on non-matching input (ReDoS), so a pattern
275 such as ``a/**/**/**/z`` from an untrusted ``.gitignore`` or
276 ``.gitattributes`` must be normalized before translation.
277 """
278 collapsed: list[bytes] = []
279 for segment in segments:
280 if segment == b"**" and collapsed and collapsed[-1] == b"**":
281 continue
282 collapsed.append(segment)
283 return collapsed
286def _translate(pat: bytes) -> bytes:
287 if pat == b"**":
288 return b".*"
289 res = b""
290 segments = _collapse_double_asterisks(_split_segments(pat))
291 i = 0
292 while i < len(segments):
293 segment = segments[i]
295 # Add slash separator (except for first segment)
296 if i > 0 and segments[i - 1] != b"**":
297 res += re.escape(b"/")
299 if segment == b"**":
300 regex_part = _translate_double_asterisk(segments, i)
301 res += regex_part
302 if regex_part == b".*": # End of pattern
303 break
304 else:
305 res += _translate_segment(segment)
307 i += 1
308 return res
311def translate(pattern: bytes) -> bytes:
312 """Translate a wildmatch() pattern to a regular expression.
314 Args:
315 pattern: Pattern in Git's wildmatch() language (``WM_PATHNAME``)
317 Returns:
318 An unanchored regular expression.
320 Raises:
321 MalformedPattern: if wildmatch() would abort on this pattern outright
322 (``WM_ABORT_ALL``, e.g. an unterminated or unknown bracket
323 expression). Callers reading a file of patterns should catch this
324 per pattern and warn rather than let one bad line fail the load;
325 see :meth:`dulwich.ignore.IgnoreFilter.append_pattern`.
326 """
327 return _translate(pattern)