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 if c == b"*":
187 # Collapse a run of consecutive '*' into a single quantifier.
188 # Within a segment repeated '*' are redundant ([^/]*[^/]* is
189 # equivalent to [^/]*), and emitting one quantifier per star
190 # builds a regex with adjacent unbounded quantifiers that
191 # backtracks catastrophically on non-matching input (ReDoS).
192 while i < n and segment[i : i + 1] == b"*":
193 i += 1
194 res += b"[^/]*"
195 elif c == b"?":
196 res += b"[^/]"
197 elif c == b"\\":
198 if i < n:
199 res += re.escape(segment[i : i + 1])
200 i += 1
201 else:
202 res += re.escape(c)
203 elif c == b"[":
204 i, bracket = translate_bracket_expression(segment, i)
205 res += bracket
206 else:
207 res += re.escape(c)
208 return res
211def _split_segments(pat: bytes) -> list[bytes]:
212 """Split a pattern into path segments, skipping slashes inside brackets.
214 wildmatch() itself walks the whole pattern in one pass rather than
215 splitting it, so a bracket expression may span a ``/`` (it just can
216 never match one). This function exists only so :func:`_translate` can
217 special-case ``**`` per segment; it must respect the same bracket
218 boundaries a one-pass walk would, which is why it can't just call
219 ``pat.split(b"/")``.
220 """
221 if b"[" not in pat:
222 return pat.split(b"/")
223 segments = []
224 start = i = 0
225 while i < len(pat):
226 c = pat[i : i + 1]
227 if c == b"\\" and i + 1 < len(pat):
228 i += 2
229 elif c == b"[":
230 i, _bracket = translate_bracket_expression(pat, i + 1)
231 else:
232 if c == b"/":
233 segments.append(pat[start:i])
234 start = i + 1
235 i += 1
236 segments.append(pat[start:])
237 return segments
240def _translate_double_asterisk(segments: Sequence[bytes], i: int) -> bytes:
241 """Handle ** segment processing, returns the regex part.
243 A run of consecutive ``**`` segments is collapsed to one by
244 :func:`_translate` before this is called, so each ``**`` is handled on
245 its own here.
246 """
247 # Check if ** is at end
248 remaining = segments[i + 1 :]
249 if all(s == b"" for s in remaining):
250 if remaining:
251 # Trailing "**/" is a directory pattern, so it has to consume at
252 # least one directory and end in a slash. Without this, "abc/**/"
253 # also matches "abc/" itself and every file directly inside it,
254 # while Git only ignores the directories below "abc".
255 return b".*/"
256 # ** at end - matches everything
257 return b".*"
259 # ** in middle - handle differently depending on what follows
260 if i == 0:
261 # ** at start - any prefix
262 return b"(?:.*/)??"
263 # ** in middle - match zero or more complete directory segments
264 return b"(?:[^/]+/)*"
267def _collapse_double_asterisks(segments: list[bytes]) -> list[bytes]:
268 """Collapse a run of consecutive ``**`` segments into a single one.
270 In Git a run of directory-spanning ``**`` segments is equivalent to a
271 single ``**``. Emitting one quantifier per segment builds a regex with
272 adjacent unbounded quantifiers (e.g. ``(?:[^/]+/)*(?:[^/]+/)*``) that
273 backtracks catastrophically on non-matching input (ReDoS), so a pattern
274 such as ``a/**/**/**/z`` from an untrusted ``.gitignore`` or
275 ``.gitattributes`` must be normalized before translation.
276 """
277 collapsed: list[bytes] = []
278 for segment in segments:
279 if segment == b"**" and collapsed and collapsed[-1] == b"**":
280 continue
281 collapsed.append(segment)
282 return collapsed
285def _translate(pat: bytes) -> bytes:
286 if pat == b"**":
287 return b".*"
288 res = b""
289 segments = _collapse_double_asterisks(_split_segments(pat))
290 i = 0
291 while i < len(segments):
292 segment = segments[i]
294 # Add slash separator (except for first segment)
295 if i > 0 and segments[i - 1] != b"**":
296 res += re.escape(b"/")
298 if segment == b"**":
299 regex_part = _translate_double_asterisk(segments, i)
300 res += regex_part
301 if regex_part == b".*": # End of pattern
302 break
303 else:
304 res += _translate_segment(segment)
306 i += 1
307 return res
310def translate(pattern: bytes) -> bytes:
311 """Translate a wildmatch() pattern to a regular expression.
313 Args:
314 pattern: Pattern in Git's wildmatch() language (``WM_PATHNAME``)
316 Returns:
317 An unanchored regular expression.
319 Raises:
320 MalformedPattern: if wildmatch() would abort on this pattern outright
321 (``WM_ABORT_ALL``, e.g. an unterminated or unknown bracket
322 expression). Callers reading a file of patterns should catch this
323 per pattern and warn rather than let one bad line fail the load;
324 see :meth:`dulwich.ignore.IgnoreFilter.append_pattern`.
325 """
326 return _translate(pattern)