Skip to main content

nerdbank_gitversioning/
filter_path.rs

1// Copyright (c) .NET Foundation and Contributors. All rights reserved.
2// Licensed under the MIT license. See LICENSE file in the project root for full license information.
3
4use std::fmt;
5
6use serde::{Deserialize, Deserializer, Serialize, Serializer};
7
8use crate::{Error, Result};
9
10/// A filter (include or exclude) representing a repository-relative path.
11#[derive(Clone, Debug, Eq, PartialEq)]
12pub struct FilterPath {
13    repo_relative_path: String,
14    is_exclude: bool,
15    is_relative: bool,
16    wildcard_segments: Option<Vec<String>>,
17}
18
19impl FilterPath {
20    /// Creates a filter from a pathspec-like string and a relative path within the repository.
21    ///
22    /// `path_spec` may be relative (`../included.txt`), absolute (`:/included.txt`),
23    /// excluded (`:!excluded.txt` or `:^excluded.txt`), or contain wildcards. `*` matches
24    /// zero or more characters in one path segment, `?` matches one character in a segment,
25    /// and a segment consisting of `**` matches zero or more path segments.
26    ///
27    /// `relative_to` is relative to the repository root; an empty string means the root.
28    pub fn new(path_spec: &str, relative_to: &str) -> Result<Self> {
29        if path_spec.is_empty() {
30            return Err(Error::InvalidFormat(
31                "A pathspec may not be empty.".to_owned(),
32            ));
33        }
34
35        let (is_exclude, is_relative, path) = if let Some(magic) = path_spec.strip_prefix(':') {
36            if let Some(path) = magic.strip_prefix(['^', '!']) {
37                let (is_relative, path) = Self::normalize(path, relative_to)?;
38                (true, is_relative, path)
39            } else if let Some(path) = magic.strip_prefix(['/', '\\']) {
40                (false, false, path.to_owned())
41            } else {
42                return Err(Error::InvalidFormat(format!(
43                    "Unrecognized path spec '{path_spec}'"
44                )));
45            }
46        } else {
47            let (is_relative, path) = Self::normalize(path_spec, relative_to)?;
48            (false, is_relative, path)
49        };
50
51        let repo_relative_path = path.replace('\\', "/").trim_end_matches('/').to_owned();
52        let wildcard_segments = repo_relative_path.contains(['*', '?']).then(|| {
53            repo_relative_path
54                .split('/')
55                .filter(|segment| !segment.is_empty())
56                .map(str::to_owned)
57                .collect()
58        });
59
60        Ok(Self {
61            repo_relative_path,
62            is_exclude,
63            is_relative,
64            wildcard_segments,
65        })
66    }
67
68    /// Gets whether this is an exclude filter.
69    pub fn is_exclude(&self) -> bool {
70        self.is_exclude
71    }
72
73    /// Gets whether this is an include filter.
74    pub fn is_include(&self) -> bool {
75        !self.is_exclude
76    }
77
78    /// Gets the represented path relative to the repository root.
79    ///
80    /// Directory separators are forward slashes.
81    pub fn repo_relative_path(&self) -> &str {
82        &self.repo_relative_path
83    }
84
85    /// Gets whether this filter represents the repository root.
86    pub fn is_root(&self) -> bool {
87        self.repo_relative_path.is_empty()
88    }
89
90    /// Gets whether the original pathspec was parsed as relative.
91    pub fn is_relative(&self) -> bool {
92        self.is_relative
93    }
94
95    /// Gets whether this filter contains wildcard characters.
96    pub fn has_wildcard(&self) -> bool {
97        self.wildcard_segments.is_some()
98    }
99
100    /// Determines whether this excluding filter matches `repo_relative_path`.
101    ///
102    /// Set `ignore_case` to the repository's `core.ignorecase` value.
103    pub fn excludes(&self, repo_relative_path: &str, ignore_case: bool) -> bool {
104        self.is_exclude
105            && if self.has_wildcard() {
106                self.matches_wildcard(repo_relative_path, ignore_case, false)
107            } else {
108                Self::matches_path_or_child(
109                    &self.repo_relative_path,
110                    repo_relative_path,
111                    ignore_case,
112                )
113            }
114    }
115
116    /// Determines whether this including filter matches `repo_relative_path`.
117    ///
118    /// Set `ignore_case` to the repository's `core.ignorecase` value.
119    pub fn includes(&self, repo_relative_path: &str, ignore_case: bool) -> bool {
120        self.is_include()
121            && (self.is_root()
122                || if self.has_wildcard() {
123                    self.matches_wildcard(repo_relative_path, ignore_case, false)
124                } else {
125                    Self::matches_path_or_child(
126                        &self.repo_relative_path,
127                        repo_relative_path,
128                        ignore_case,
129                    )
130                })
131    }
132
133    /// Determines whether this including filter may match children of
134    /// `repo_relative_path`.
135    pub fn includes_children(&self, repo_relative_path: &str, ignore_case: bool) -> bool {
136        if !self.is_include() {
137            return false;
138        }
139        if self.is_root() {
140            return true;
141        }
142        if self.has_wildcard() {
143            return self.matches_wildcard(repo_relative_path, ignore_case, true);
144        }
145
146        let prefix = format!("{repo_relative_path}/");
147        Self::starts_with(&self.repo_relative_path, &prefix, ignore_case)
148    }
149
150    /// Converts this filter to a pathspec.
151    ///
152    /// `repo_relative_base_directory` is the repository-relative directory from which
153    /// relative pathspecs should be expressed. An empty string means the repository root.
154    pub fn to_path_spec(&self, repo_relative_base_directory: &str) -> Result<String> {
155        let (_, normalized_base) = Self::normalize(
156            if repo_relative_base_directory.is_empty() {
157                "."
158            } else {
159                repo_relative_base_directory
160            },
161            "",
162        )?;
163        let mut path_spec = if self.is_exclude {
164            ":!".to_owned()
165        } else {
166            String::new()
167        };
168
169        if self.is_relative {
170            let (dirs_ascended, relative_path) =
171                Self::get_relative_path(&self.repo_relative_path, &normalized_base);
172            if dirs_ascended == 0 && !self.is_exclude {
173                path_spec.push_str("./");
174            }
175            path_spec.push_str(&relative_path);
176        } else {
177            path_spec.push('/');
178            path_spec.push_str(&self.repo_relative_path);
179        }
180
181        Ok(path_spec)
182    }
183
184    fn normalize(path: &str, relative_to: &str) -> Result<(bool, String)> {
185        if path.is_empty() {
186            return Err(Error::InvalidFormat("A path may not be empty.".to_owned()));
187        }
188        if let Some(path) = path.strip_prefix(['/', '\\']) {
189            return Ok((false, path.to_owned()));
190        }
191
192        let combined = if relative_to.is_empty() {
193            path.to_owned()
194        } else {
195            format!("{relative_to}/{path}")
196        };
197        let mut parts = Vec::new();
198        for segment in combined.split(['/', '\\']).filter(|part| !part.is_empty()) {
199            match segment {
200                "." => {}
201                ".." => {
202                    if parts.pop().is_none() {
203                        return Err(Error::InvalidFormat(format!(
204                            "Too many '..' in path '{combined}' - would escape the root of the repository."
205                        )));
206                    }
207                }
208                _ => parts.push(segment),
209            }
210        }
211
212        Ok((true, parts.join("/")))
213    }
214
215    fn get_relative_path(path: &str, relative_to: &str) -> (usize, String) {
216        let path_parts: Vec<_> = path.split('/').collect();
217        let base_parts: Vec<_> = relative_to
218            .split('/')
219            .filter(|part| !part.is_empty())
220            .collect();
221        let common_parts = path_parts
222            .iter()
223            .zip(&base_parts)
224            .take_while(|(left, right)| Self::strings_equal(left, right, true))
225            .count();
226        let dirs_to_ascend = base_parts.len() - common_parts;
227        let mut result = "../".repeat(dirs_to_ascend);
228        result.push_str(&path_parts[common_parts..].join("/"));
229        (dirs_to_ascend, result)
230    }
231
232    fn matches_path_or_child(filter: &str, candidate: &str, ignore_case: bool) -> bool {
233        Self::strings_equal(filter, candidate, ignore_case)
234            || Self::starts_with(candidate, &format!("{filter}/"), ignore_case)
235    }
236
237    fn starts_with(value: &str, prefix: &str, ignore_case: bool) -> bool {
238        if !ignore_case {
239            return value.starts_with(prefix);
240        }
241        let mut value = value.chars();
242        prefix.chars().all(|expected| {
243            value
244                .next()
245                .is_some_and(|actual| Self::characters_equal(expected, actual, true))
246        })
247    }
248
249    fn strings_equal(left: &str, right: &str, ignore_case: bool) -> bool {
250        if ignore_case {
251            left.chars().count() == right.chars().count()
252                && left
253                    .chars()
254                    .zip(right.chars())
255                    .all(|(left, right)| Self::characters_equal(left, right, true))
256        } else {
257            left == right
258        }
259    }
260
261    fn matches_segment(pattern: &str, value: &str, ignore_case: bool) -> bool {
262        let pattern: Vec<_> = pattern.chars().collect();
263        let value: Vec<_> = value.chars().collect();
264        let mut matches = vec![vec![false; value.len() + 1]; pattern.len() + 1];
265        matches[pattern.len()][value.len()] = true;
266
267        for pattern_index in (0..pattern.len()).rev() {
268            if pattern[pattern_index] == '*' {
269                matches[pattern_index][value.len()] = matches[pattern_index + 1][value.len()];
270            }
271            for value_index in (0..value.len()).rev() {
272                matches[pattern_index][value_index] = if pattern[pattern_index] == '*' {
273                    matches[pattern_index + 1][value_index]
274                        || matches[pattern_index][value_index + 1]
275                } else if pattern[pattern_index] == '?'
276                    || Self::characters_equal(
277                        pattern[pattern_index],
278                        value[value_index],
279                        ignore_case,
280                    )
281                {
282                    matches[pattern_index + 1][value_index + 1]
283                } else {
284                    false
285                };
286            }
287        }
288
289        matches[0][0]
290    }
291
292    fn characters_equal(left: char, right: char, ignore_case: bool) -> bool {
293        left == right || (ignore_case && left.to_uppercase().eq(right.to_uppercase()))
294    }
295
296    fn matches_wildcard(
297        &self,
298        repo_relative_path: &str,
299        ignore_case: bool,
300        match_descendants: bool,
301    ) -> bool {
302        let candidate = repo_relative_path.replace('\\', "/");
303        let candidate_segments: Vec<_> = candidate
304            .split('/')
305            .filter(|segment| !segment.is_empty())
306            .collect();
307        let filter_segments = self.wildcard_segments.as_ref().expect("wildcard segments");
308        let mut matches =
309            vec![vec![false; candidate_segments.len() + 1]; filter_segments.len() + 1];
310
311        matches[filter_segments.len()].fill(true);
312        for filter_index in (0..filter_segments.len()).rev() {
313            let recursive = filter_segments[filter_index] == "**";
314            matches[filter_index][candidate_segments.len()] = match_descendants
315                || (recursive && matches[filter_index + 1][candidate_segments.len()]);
316            for candidate_index in (0..candidate_segments.len()).rev() {
317                matches[filter_index][candidate_index] = if recursive {
318                    matches[filter_index + 1][candidate_index]
319                        || matches[filter_index][candidate_index + 1]
320                } else {
321                    Self::matches_segment(
322                        &filter_segments[filter_index],
323                        candidate_segments[candidate_index],
324                        ignore_case,
325                    ) && matches[filter_index + 1][candidate_index + 1]
326                };
327            }
328        }
329
330        matches[0][0]
331    }
332}
333
334impl fmt::Display for FilterPath {
335    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
336        formatter.write_str(&self.repo_relative_path)
337    }
338}
339
340impl Serialize for FilterPath {
341    fn serialize<S>(&self, serializer: S) -> std::result::Result<S::Ok, S::Error>
342    where
343        S: Serializer,
344    {
345        self.to_path_spec("")
346            .map_err(serde::ser::Error::custom)?
347            .serialize(serializer)
348    }
349}
350
351impl<'de> Deserialize<'de> for FilterPath {
352    fn deserialize<D>(deserializer: D) -> std::result::Result<Self, D::Error>
353    where
354        D: Deserializer<'de>,
355    {
356        let path_spec = String::deserialize(deserializer)?;
357        Self::new(&path_spec, "").map_err(serde::de::Error::custom)
358    }
359}
360
361#[cfg(test)]
362mod tests {
363    use super::*;
364
365    #[test]
366    fn parses_to_repo_relative_path() {
367        let cases = [
368            ("./", "foo", "foo"),
369            ("../relative-dir", "foo", "relative-dir"),
370            ("relative-dir", "some/dir/../zany", "some/zany/relative-dir"),
371            ("../../some/dir/here", "foo/multi/wow", "foo/some/dir/here"),
372            (":^relativepath.txt", "foo", "foo/relativepath.txt"),
373            (":!/absolutepath.txt", "foo", "absolutepath.txt"),
374            ("/", "foo", ""),
375            (":/", "foo", ""),
376            (":/bar/absolutepath.txt", "foo", "bar/absolutepath.txt"),
377            (":/loc/*/MyProduct.*", "foo", "loc/*/MyProduct.*"),
378            ("../**/generated?.cs", "foo/bar", "foo/**/generated?.cs"),
379            (r".\dir\file.txt", "foo", "foo/dir/file.txt"),
380            (r":!\absolute.txt", "foo", "absolute.txt"),
381        ];
382        for (path_spec, relative_to, expected) in cases {
383            assert_eq!(
384                expected,
385                FilterPath::new(path_spec, relative_to)
386                    .unwrap()
387                    .repo_relative_path()
388            );
389        }
390    }
391
392    #[test]
393    fn rejects_invalid_pathspecs() {
394        for (path_spec, relative_to) in [
395            ("", ""),
396            (":?", ""),
397            ("../foo.txt", ""),
398            (".././a/../../foo.txt", "foo"),
399            (":!", ""),
400        ] {
401            assert!(FilterPath::new(path_spec, relative_to).is_err());
402        }
403    }
404
405    #[test]
406    fn includes_and_excludes_paths() {
407        let exclude = FilterPath::new(":^../bar", "foo").unwrap();
408        assert!(exclude.is_exclude());
409        assert!(exclude.excludes("bar", false));
410        assert!(exclude.excludes("bar/somefile.txt", false));
411        assert!(!exclude.excludes("barista", false));
412        assert!(!exclude.includes("bar", false));
413
414        let include = FilterPath::new("../root.txt", "foo").unwrap();
415        assert!(include.is_include());
416        assert!(include.includes("root.txt", false));
417        assert!(include.includes("root.txt/child", false));
418        assert!(!include.excludes("root.txt", false));
419        assert!(
420            FilterPath::new("/", "foo")
421                .unwrap()
422                .includes("anything", false)
423        );
424    }
425
426    #[test]
427    fn comparisons_honor_case_setting() {
428        let exclude = FilterPath::new(":!RelativePath.txt", "foo").unwrap();
429        assert!(exclude.excludes("foo/relativepath.txt", true));
430        assert!(!exclude.excludes("foo/relativepath.txt", false));
431
432        let wildcard = FilterPath::new(":/loc/*/MyProduct.*", "").unwrap();
433        assert!(wildcard.includes("LOC/en/myproduct.resx", true));
434        assert!(!wildcard.includes("LOC/en/myproduct.resx", false));
435    }
436
437    #[test]
438    fn wildcard_dp_matches_segments_and_descendants() {
439        let matching = [
440            (":/loc/*/MyProduct.*", "loc/en/MyProduct.resx"),
441            (":/loc/*/MyProduct.*", "loc/en/MyProduct."),
442            (":/loc/?/MyProduct.*", "loc/e/MyProduct.resx"),
443            (":/loc/**/MyProduct.*", "loc/MyProduct.resx"),
444            (":/loc/**/MyProduct.*", "loc/en/subdir/MyProduct.resx"),
445            (":/**/MyProduct.*", "MyProduct.resx"),
446            (":/eng/*", "eng/product/src/file.cs"),
447        ];
448        for (path_spec, candidate) in matching {
449            assert!(
450                FilterPath::new(path_spec, "")
451                    .unwrap()
452                    .includes(candidate, false)
453            );
454        }
455
456        let not_matching = [
457            (":/loc/*/MyProduct.*", "loc/en/subdir/MyProduct.resx"),
458            (":/loc/?/MyProduct.*", "loc/en/MyProduct.resx"),
459            (":/loc/*/MyProduct.*", "loc/en/OtherProduct.resx"),
460        ];
461        for (path_spec, candidate) in not_matching {
462            assert!(
463                !FilterPath::new(path_spec, "")
464                    .unwrap()
465                    .includes(candidate, false)
466            );
467        }
468
469        let exclude = FilterPath::new(":^/loc/**/generated?.cs", "").unwrap();
470        assert!(exclude.excludes("loc/generated1.cs", false));
471        assert!(exclude.excludes("loc/en/subdir/generatedA.cs", false));
472        assert!(!exclude.excludes("loc/en/generated.cs", false));
473    }
474
475    #[test]
476    fn wildcard_filter_may_include_children() {
477        let filter = FilterPath::new(":/loc/*/MyProduct.*", "").unwrap();
478        for candidate in ["loc", "loc/en", "loc/en/MyProduct.resources"] {
479            assert!(filter.includes_children(candidate, false));
480        }
481        for candidate in ["localization", "docs"] {
482            assert!(!filter.includes_children(candidate, false));
483        }
484        assert!(
485            !FilterPath::new(":!/loc/*", "")
486                .unwrap()
487                .includes_children("loc", false)
488        );
489    }
490
491    #[test]
492    fn converts_to_pathspec() {
493        let cases = [
494            (":/abc/def", "", "/abc/def"),
495            (":/abc/def", ".", "/abc/def"),
496            ("abc", ".", "./abc"),
497            (".", ".", "./"),
498            ("./", "", "./"),
499            ("abc/def", "./foo", "./abc/def"),
500            (
501                "../Directory.Build.props",
502                "./foo",
503                "../Directory.Build.props",
504            ),
505            (
506                ":!/Directory.Build.props",
507                "./foo",
508                ":!/Directory.Build.props",
509            ),
510            (":!relative.txt", "./foo", ":!relative.txt"),
511            (":/loc/*/MyProduct.*", "./foo", "/loc/*/MyProduct.*"),
512            ("../**/generated?.cs", "./foo", "../**/generated?.cs"),
513        ];
514        for (path_spec, relative_to, expected) in cases {
515            assert_eq!(
516                expected,
517                FilterPath::new(path_spec, relative_to)
518                    .unwrap()
519                    .to_path_spec(relative_to)
520                    .unwrap()
521            );
522        }
523
524        for relative_to in ["foo", "FOO"] {
525            assert_eq!(
526                "./bar",
527                FilterPath::new("foo/bar", ".")
528                    .unwrap()
529                    .to_path_spec(relative_to)
530                    .unwrap()
531            );
532        }
533    }
534
535    #[test]
536    fn serde_uses_a_pathspec_string_and_round_trips() {
537        for filter in [
538            FilterPath::new(":/abc/*", "elsewhere").unwrap(),
539            FilterPath::new(":!foo/?.txt", "").unwrap(),
540            FilterPath::new("./foo", "").unwrap(),
541        ] {
542            let json = serde_json::to_string(&filter).unwrap();
543            assert!(json.starts_with('"'));
544            assert_eq!(filter, serde_json::from_str(&json).unwrap());
545        }
546    }
547}