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"""
2This module provides the :module:`re2` backend for :class:`~pathspec.gitignore.GitIgnoreSpec`.
4WARNING: The *pathspec._backends.re2* package is not part of the public API. Its
5contents and structure are likely to change.
6"""
7from __future__ import annotations
9from typing import (
10 Callable, # Replaced by `collections.abc.Callable` in 3.9.2.
11 Optional, # Replaced by `X | None` in 3.10.
12 Union) # Replaced by `X | Y` in 3.10.
14try:
15 import re2
16except ModuleNotFoundError:
17 re2 = None # type: ignore[assignment]
19from pathspec.pattern import (
20 RegexPattern)
21from pathspec.patterns.gitignore.spec import (
22 GitIgnoreSpecPattern,
23 _BYTES_ENCODING,
24 _DIR_MARK_CG,
25 _DIR_MARK_OPT)
26from pathspec._typing import (
27 override) # Added in 3.12.
29from .._utils import (
30 get_regex_flags,
31 translate_end_anchor,
32 translate_regex_flags)
34from ._base import (
35 Re2RegexDat,
36 Re2RegexDebug)
37from .pathspec import (
38 Re2PsBackend)
41class Re2GiBackend(Re2PsBackend):
42 """
43 The :class:`Re2GiBackend` class is the :module:`re2` implementation used by
44 :class:`~pathspec.gitignore.GitIgnoreSpec` for matching files.
45 """
47 @override
48 @staticmethod
49 def _init_set(
50 debug: bool,
51 patterns: dict[int, RegexPattern],
52 regex_set: re2.Set, # type: ignore
53 sort_indices: Optional[Callable[[list[int]], None]],
54 ) -> list[Re2RegexDat]:
55 """
56 Create the re2 regex set.
58 *debug* (:class:`bool`) is whether to include additional debugging
59 information for the regular expressions.
61 *patterns* (:class:`dict`) maps pattern index (:class:`int`) to pattern
62 (:class:`.RegexPattern`).
64 *regex_set* (:class:`re2.Set`) is the regex set.
66 *sort_indices* (:class:`callable` or :data:`None`) is a function used to
67 sort the patterns by index. This is used during testing to ensure the order
68 of patterns is not accidentally relied on.
70 Returns a :class:`list` indexed by regex id (:class:`int`) to its data
71 (:class:`Re2RegexDat`).
72 """
73 # Sort patterns.
74 indices = list(patterns.keys())
75 if sort_indices is not None:
76 sort_indices(indices)
78 # Prepare patterns.
79 regex_data: list[Re2RegexDat] = []
80 for pattern_index in indices:
81 pattern = patterns[pattern_index]
82 pattern_include = pattern.include
83 if pattern_include is None:
84 continue
86 assert pattern.regex is not None, pattern
87 assert isinstance(pattern, RegexPattern), pattern
88 regex = pattern.regex.pattern
90 use_regexes: list[tuple[Union[str, bytes], bool]] = []
91 if isinstance(pattern, GitIgnoreSpecPattern):
92 # GitIgnoreSpecPattern uses capture groups for its directory marker. Re2
93 # supports capture groups, but they cannot be utilized when using
94 # `re2.Set`. Handle this scenario.
95 regex_str: str
96 if isinstance(regex, str):
97 regex_str = regex
98 else:
99 assert isinstance(regex, bytes), regex
100 regex_str = regex.decode(_BYTES_ENCODING)
102 if _DIR_MARK_CG in regex_str:
103 # Found directory marker.
104 if regex_str.endswith(_DIR_MARK_OPT):
105 # Regex has optional directory marker. Split regex into directory
106 # and file variants. The directory variant must require a child
107 # segment: without one the query *is* that directory, which is a
108 # direct match and not an excluded ancestor.
109 base_regex = regex_str[:-len(_DIR_MARK_OPT)]
110 use_regexes.append((f'{base_regex}/(?s:.)', True))
111 use_regexes.append((rf'{base_regex}/?\z', False))
112 else:
113 # Remove capture group.
114 base_regex = regex_str.replace(_DIR_MARK_CG, '/')
115 use_regexes.append((f'{base_regex}(?s:.)', True))
116 use_regexes.append((rf'{base_regex}\z', False))
118 if not use_regexes:
119 # No special case for regex.
120 use_regexes.append((regex, False))
122 for regex, is_dir_pattern in use_regexes:
123 regex = translate_end_anchor(regex)
124 regex = translate_regex_flags(
125 regex,
126 get_regex_flags(pattern.regex),
127 )
128 if debug:
129 regex_data.append(Re2RegexDebug(
130 include=pattern_include,
131 index=pattern_index,
132 is_dir_pattern=is_dir_pattern,
133 regex=regex,
134 ))
135 else:
136 regex_data.append(Re2RegexDat(
137 include=pattern_include,
138 index=pattern_index,
139 is_dir_pattern=is_dir_pattern,
140 ))
142 regex_set.Add(regex) # type: ignore[type-var]
144 # Compile patterns.
145 regex_set.Compile()
146 return regex_data
148 @override
149 def match_file(self, file: str) -> tuple[Optional[bool], Optional[int]]:
150 """
151 Check the file against the patterns.
153 *file* (:class:`str`) is the normalized file path to check.
155 Returns a :class:`tuple` containing whether to include *file* (:class:`bool`
156 or :data:`None`), and the index of the last matched pattern (:class:`int` or
157 :data:`None`).
158 """
159 return self._match(file, check_ancestors=True)
161 def _match(
162 self, file: str, check_ancestors: bool,
163 ) -> tuple[Optional[bool], Optional[int]]:
164 """
165 Implements :meth:`match_file`. *check_ancestors* (:class:`bool`) is
166 whether to ask if an ancestor directory of *file* is excluded; see
167 :meth:`_match_ancestor` for why it can be skipped.
168 """
169 # Find best match.
170 match_ids: Optional[list[int]] = self._set.Match(file) # type: ignore[assignment]
171 if not match_ids:
172 return (None, None)
174 # Resolve the ancestor directory and the file separately: a file negation
175 # only applies while no ancestor directory is excluded.
176 dir_include: Optional[bool] = None
177 dir_index: int = -1
178 file_include: Optional[bool] = None
179 file_index: int = -1
181 regex_data = self._regex_data
182 for regex_id in match_ids:
183 regex_dat = regex_data[regex_id]
185 # WARNING: According to the documentation on `RE2::Set::Match()`, there is
186 # no guarantee matches will be produced in order!
187 include = regex_dat.include
188 index = regex_dat.index
189 if regex_dat.is_dir_pattern:
190 # Pattern matched by a directory pattern.
191 if index > dir_index:
192 dir_include = include
193 dir_index = index
194 elif index > file_index:
195 # Pattern matched by a file pattern.
196 file_include = include
197 file_index = index
199 assert dir_index != -1 or file_index != -1, (dir_index, file_index)
200 if check_ancestors and (dir_include is not None or file_include is not None):
201 # Neither file nor directory negations override an excluded ancestor.
202 # Some patterns (e.g. "a/**") match without a directory marker.
203 ancestor_index = self._match_ancestor(file)
204 if ancestor_index is not None:
205 return (True, ancestor_index)
207 if file_include is not None:
208 return (file_include, file_index)
209 elif dir_include:
210 # An ancestor matched an exclude pattern, but the spec as a whole
211 # re-includes that ancestor, so the rule does not apply.
212 return (None, None)
213 else:
214 return (dir_include, dir_index)
216 def _match_ancestor(self, file: str) -> Optional[int]:
217 """
218 Return the excluding pattern index for a strict ancestor, or :data:`None`.
219 Git stops descending at the first excluded directory, so the ancestors are
220 asked outermost first, each as a directory query (trailing slash included).
221 By the time an ancestor is asked, every ancestor above it is known not to
222 be excluded, so it is matched without checking its own ancestors again;
223 otherwise each level re-asks all the levels above it and the work grows
224 exponentially with depth.
225 """
226 index = file.find('/')
227 while index != -1 and index + 1 < len(file):
228 ancestor_include, ancestor_index = self._match(
229 file[:index + 1], check_ancestors=False,
230 )
231 if ancestor_include:
232 return ancestor_index
233 index = file.find('/', index + 1)
235 return None