walker/
compiled_glob.rs

1use path_dedot::{CWD, ParseDot};
2use std::borrow::Cow;
3use std::collections::HashSet;
4use std::ffi::OsStr;
5use std::fmt::Debug;
6use std::io;
7use std::ops::Range;
8use std::path::{MAIN_SEPARATOR, Path, PathBuf};
9use std::sync::Arc;
10use wildmatch::WildMatch;
11
12pub(crate) struct PathInner {
13    pathbase: Arc<String>,
14    range: Range<usize>,
15}
16
17impl PathInner {
18    pub(crate) fn as_str(&self) -> &str {
19        &self.pathbase[self.range.clone()]
20    }
21}
22
23impl Debug for PathInner {
24    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
25        write!(f, "{:?}", self.as_ref())
26    }
27}
28
29impl AsRef<Path> for PathInner {
30    fn as_ref(&self) -> &Path {
31        Path::new(&self.pathbase[self.range.clone()])
32    }
33}
34
35impl Clone for PathInner {
36    fn clone(&self) -> Self {
37        Self {
38            pathbase: Arc::clone(&self.pathbase),
39            range: self.range.clone(),
40        }
41    }
42}
43
44#[allow(dead_code)]
45#[derive(Debug, Clone)]
46pub(crate) enum SegmentMatcher {
47    AnyPath(PathInner),
48    WildMatch { pattern: String, matcher: WildMatch },
49    Descend,
50}
51
52#[derive(Debug, Clone)]
53struct CompiledRule {
54    rule_index: usize,
55    is_exclude: bool,
56    is_absolute: bool,
57    segments: Vec<SegmentMatcher>,
58}
59
60#[allow(dead_code)]
61#[derive(Debug, Default, Clone)]
62struct RuleTerminal {
63    rule_index: usize,
64    is_exclude: bool,
65}
66
67type NodeId = usize;
68
69#[derive(Debug, Clone, Eq, PartialEq)]
70enum WildEdgeKind {
71    Suffix(String),
72    Prefix(String),
73    SingleChar,
74    General,
75}
76
77#[derive(Debug, Default, Clone)]
78struct TrieNode {
79    literal_edges: hashbrown::HashMap<String, NodeId>,
80    wild_edges_general: Vec<(String, WildMatch, NodeId)>,
81    wild_edges_suffix: hashbrown::HashMap<String, Vec<NodeId>>,
82    wild_edges_prefix: hashbrown::HashMap<String, Vec<NodeId>>,
83    wild_edges_exact1: Vec<NodeId>,
84    descend_edge: Option<NodeId>,
85    terminals: Vec<RuleTerminal>,
86}
87
88#[derive(Debug, Clone)]
89struct GlobTrie {
90    nodes: Vec<TrieNode>,
91}
92
93impl GlobTrie {
94    fn new() -> Self {
95        Self {
96            nodes: vec![TrieNode::default()],
97        }
98    }
99
100    fn add_node(&mut self) -> NodeId {
101        self.nodes.push(TrieNode::default());
102        self.nodes.len() - 1
103    }
104
105    fn insert_rule(&mut self, rule: &CompiledRule) {
106        fn any_path_parts(text: &str) -> impl Iterator<Item = &str> {
107            text.split(MAIN_SEPARATOR).filter(|s| !s.is_empty())
108        }
109
110        let mut node = 0usize;
111        for segment in &rule.segments {
112            match segment {
113                SegmentMatcher::AnyPath(inner) => {
114                    for part in any_path_parts(inner.as_str()) {
115                        if part.is_empty() {
116                            continue;
117                        }
118                        let next = if let Some(existing) = self.nodes[node].literal_edges.get(part)
119                        {
120                            *existing
121                        } else {
122                            let created = self.add_node();
123                            self.nodes[node]
124                                .literal_edges
125                                .insert(part.to_string(), created);
126                            created
127                        };
128                        node = next;
129                    }
130                }
131                SegmentMatcher::WildMatch {
132                    pattern,
133                    matcher: _,
134                } => {
135                    let next = self.insert_wild_edge(node, pattern);
136                    node = next;
137                }
138                SegmentMatcher::Descend => {
139                    let next = if let Some(existing) = self.nodes[node].descend_edge {
140                        existing
141                    } else {
142                        let created = self.add_node();
143                        self.nodes[node].descend_edge = Some(created);
144                        created
145                    };
146                    node = next;
147                }
148            }
149        }
150        self.nodes[node].terminals.push(RuleTerminal {
151            rule_index: rule.rule_index,
152            is_exclude: rule.is_exclude,
153        });
154    }
155
156    fn insert_wild_edge(&mut self, node: NodeId, pattern: &str) -> NodeId {
157        match classify_wild_edge(pattern) {
158            WildEdgeKind::Suffix(suffix) => {
159                if let Some(existing) = self.nodes[node]
160                    .wild_edges_suffix
161                    .get(&suffix)
162                    .and_then(|ids| ids.first())
163                {
164                    return *existing;
165                }
166                let created = self.add_node();
167                self.nodes[node]
168                    .wild_edges_suffix
169                    .entry(suffix)
170                    .or_default()
171                    .push(created);
172                created
173            }
174            WildEdgeKind::Prefix(prefix) => {
175                if let Some(existing) = self.nodes[node]
176                    .wild_edges_prefix
177                    .get(&prefix)
178                    .and_then(|ids| ids.first())
179                {
180                    return *existing;
181                }
182                let created = self.add_node();
183                self.nodes[node]
184                    .wild_edges_prefix
185                    .entry(prefix)
186                    .or_default()
187                    .push(created);
188                created
189            }
190            WildEdgeKind::SingleChar => {
191                if let Some(existing) = self.nodes[node].wild_edges_exact1.first() {
192                    return *existing;
193                }
194                let created = self.add_node();
195                self.nodes[node].wild_edges_exact1.push(created);
196                created
197            }
198            WildEdgeKind::General => {
199                for (existing, _, node_id) in &self.nodes[node].wild_edges_general {
200                    if existing == pattern {
201                        return *node_id;
202                    }
203                }
204                let created = self.add_node();
205                self.nodes[node].wild_edges_general.push((
206                    pattern.to_string(),
207                    WildMatch::new(pattern),
208                    created,
209                ));
210                created
211            }
212        }
213    }
214}
215
216#[derive(Debug, Clone)]
217pub struct CompiledGlob {
218    ordered_rules: Vec<CompiledRule>,
219    trie: GlobTrie,
220    epsilon_closures: Vec<Vec<usize>>,
221    node_can_scan: Vec<bool>,
222    node_best_terminal: Vec<Option<(usize, bool)>>,
223}
224
225impl CompiledGlob {
226    /// 文字列をパースしてCompiledGlobを生成します。
227    pub fn new(pattern: &str) -> io::Result<Self> {
228        if pattern.is_empty() {
229            return Err(io::Error::new(
230                io::ErrorKind::InvalidInput,
231                "pattern must not be empty",
232            ));
233        }
234        let is_exclude = pattern.starts_with('!');
235        let pattern_body = if is_exclude { &pattern[1..] } else { pattern };
236        if pattern_body.is_empty() {
237            return Err(io::Error::new(
238                io::ErrorKind::InvalidInput,
239                "exclude pattern must include body after '!'",
240            ));
241        }
242
243        let parsed = Path::new(pattern_body).parse_dot()?;
244        let is_absolute = parsed.is_absolute();
245        let pattern = parsed.to_str().unwrap().to_string();
246        let pattern = Arc::new(pattern);
247        let mut segments = Vec::new();
248
249        let mut seg_start = 0usize;
250        fn push_segment_range(
251            segments: &mut Vec<SegmentMatcher>,
252            pattern: &Arc<String>,
253            range: Range<usize>,
254        ) {
255            if range.is_empty() {
256                return;
257            }
258            let seg = &pattern[range.clone()];
259            if let Some(rel_pos) = seg.find("**") {
260                if seg == "**" {
261                    segments.push(SegmentMatcher::Descend);
262                    return;
263                }
264                let abs_pos = range.start + rel_pos;
265                let pre = range.start..abs_pos;
266                let post = (abs_pos + 2)..range.end;
267                if pre.is_empty() && !post.is_empty() {
268                    segments.push(SegmentMatcher::Descend);
269                    let mut tail = String::from("*");
270                    tail.push_str(&pattern[post]);
271                    segments.push(SegmentMatcher::WildMatch {
272                        pattern: tail.clone(),
273                        matcher: WildMatch::new(&tail),
274                    });
275                    return;
276                }
277                if !pre.is_empty() && post.is_empty() {
278                    let mut head = pattern[pre].to_string();
279                    head.push('*');
280                    segments.push(SegmentMatcher::WildMatch {
281                        pattern: head.clone(),
282                        matcher: WildMatch::new(&head),
283                    });
284                    segments.push(SegmentMatcher::Descend);
285                    return;
286                }
287                if !pre.is_empty() && !post.is_empty() {
288                    let mut head = pattern[pre].to_string();
289                    head.push('*');
290                    segments.push(SegmentMatcher::WildMatch {
291                        pattern: head.clone(),
292                        matcher: WildMatch::new(&head),
293                    });
294                    segments.push(SegmentMatcher::Descend);
295                    let mut tail = String::from("*");
296                    tail.push_str(&pattern[post]);
297                    segments.push(SegmentMatcher::WildMatch {
298                        pattern: tail.clone(),
299                        matcher: WildMatch::new(&tail),
300                    });
301                    return;
302                }
303                return;
304            }
305
306            let has_wild = seg.chars().any(|ch| matches!(ch, '*' | '?'));
307            if has_wild {
308                segments.push(SegmentMatcher::WildMatch {
309                    pattern: seg.to_string(),
310                    matcher: WildMatch::new(seg),
311                });
312            } else if let Some(SegmentMatcher::AnyPath(last)) = segments.last_mut() {
313                last.range.end = range.end;
314            } else {
315                segments.push(SegmentMatcher::AnyPath(PathInner {
316                    pathbase: pattern.clone(),
317                    range,
318                }));
319            }
320        }
321
322        for (idx, ch) in pattern.char_indices() {
323            if ch == MAIN_SEPARATOR {
324                push_segment_range(&mut segments, &pattern, seg_start..idx);
325                seg_start = idx + ch.len_utf8();
326            }
327        }
328        push_segment_range(&mut segments, &pattern, seg_start..pattern.len());
329
330        if !is_absolute {
331            let pathbase = Arc::new(CWD.to_str().unwrap().to_string());
332            let range = 0..pathbase.len();
333            segments.insert(
334                // TODO: This is O(n). Would you have any better idea?
335                0,
336                SegmentMatcher::AnyPath(PathInner { pathbase, range }),
337            );
338        }
339        let mut compiled = CompiledGlob {
340            ordered_rules: Vec::new(),
341            trie: GlobTrie::new(),
342            epsilon_closures: Vec::new(),
343            node_can_scan: Vec::new(),
344            node_best_terminal: Vec::new(),
345        };
346        compiled.push_rule(segments, is_exclude, is_absolute);
347        Ok(compiled)
348    }
349
350    pub fn merge(mut self, other: CompiledGlob) -> CompiledGlob {
351        let base = self.ordered_rules.len();
352        for (offset, mut rule) in other.ordered_rules.into_iter().enumerate() {
353            rule.rule_index = base + offset;
354            self.trie.insert_rule(&rule);
355            self.ordered_rules.push(rule);
356        }
357        self.rebuild_epsilon_closure_cache();
358        self
359    }
360
361    pub fn merge_many(globs: impl IntoIterator<Item = CompiledGlob>) -> io::Result<CompiledGlob> {
362        let mut iter = globs.into_iter();
363        let Some(mut merged) = iter.next() else {
364            return Err(io::Error::new(
365                io::ErrorKind::InvalidInput,
366                "merge_many requires at least one compiled glob",
367            ));
368        };
369        for glob in iter {
370            merged = merged.merge(glob);
371        }
372        Ok(merged)
373    }
374
375    pub(crate) fn initial_states(&self) -> Vec<usize> {
376        self.expand_epsilon_nodes([0usize].as_ref())
377    }
378
379    pub(crate) fn states_for_path(&self, path: &Path) -> Vec<usize> {
380        let mut states = self.initial_states();
381        for part in path
382            .to_string_lossy()
383            .split(MAIN_SEPARATOR)
384            .filter(|s| !s.is_empty())
385        {
386            states = self.advance_states(&states, part);
387            if states.is_empty() {
388                break;
389            }
390        }
391        states
392    }
393
394    pub(crate) fn start_paths(&self) -> Vec<PathBuf> {
395        let mut out = Vec::new();
396        let mut seen = hashbrown::HashSet::new();
397
398        for rule in &self.ordered_rules {
399            if rule.is_exclude {
400                continue;
401            }
402
403            let mut prefix = PathBuf::new();
404            for seg in &rule.segments {
405                match seg {
406                    SegmentMatcher::AnyPath(part) => {
407                        prefix.push(part.as_ref());
408                    }
409                    SegmentMatcher::WildMatch { .. } | SegmentMatcher::Descend => break,
410                }
411            }
412
413            let mut candidate = if prefix.as_os_str().is_empty() {
414                PathBuf::from(MAIN_SEPARATOR.to_string())
415            } else {
416                prefix
417            };
418            if rule.is_absolute && !candidate.is_absolute() {
419                candidate = PathBuf::from(MAIN_SEPARATOR.to_string()).join(candidate);
420            }
421
422            if seen.insert(candidate.clone()) {
423                out.push(candidate);
424            }
425        }
426
427        if out.is_empty() {
428            out.push(PathBuf::from(MAIN_SEPARATOR.to_string()));
429        }
430
431        out
432    }
433
434    pub(crate) fn advance_states(&self, current: &[usize], part: &str) -> Vec<usize> {
435        let mut out = Vec::new();
436        self.advance_states_into(current, part, &mut out);
437        out
438    }
439
440    pub(crate) fn advance_states_into(&self, current: &[usize], part: &str, out: &mut Vec<usize>) {
441        // 2 本の scratch を交互に使い、epsilon 展開ごとの Vec 確保を避ける。
442        let mut scratch_a = Vec::new();
443        let mut scratch_b = Vec::new();
444        self.expand_epsilon_nodes_into(current, &mut scratch_a);
445        out.clear();
446        let single_char = is_single_char(part);
447        let mut overflow_seen: Option<HashSet<usize>> = None;
448        for node_idx in &scratch_a {
449            let node = &self.trie.nodes[*node_idx];
450            if let Some(next_idx) = node.literal_edges.get(part) {
451                push_unique_state(out, &mut overflow_seen, *next_idx);
452            }
453
454            if !node.wild_edges_exact1.is_empty() && single_char {
455                for next_idx in &node.wild_edges_exact1 {
456                    push_unique_state(out, &mut overflow_seen, *next_idx);
457                }
458            }
459
460            for (suffix, ids) in &node.wild_edges_suffix {
461                if part.ends_with(suffix) {
462                    for next_idx in ids {
463                        push_unique_state(out, &mut overflow_seen, *next_idx);
464                    }
465                }
466            }
467
468            for (prefix, ids) in &node.wild_edges_prefix {
469                if part.starts_with(prefix) {
470                    for next_idx in ids {
471                        push_unique_state(out, &mut overflow_seen, *next_idx);
472                    }
473                }
474            }
475
476            for (_, matcher, next_idx) in &node.wild_edges_general {
477                if matcher.matches(part) {
478                    push_unique_state(out, &mut overflow_seen, *next_idx);
479                }
480            }
481            if node.descend_edge.is_some() {
482                push_unique_state(out, &mut overflow_seen, *node_idx);
483            }
484        }
485        // out の epsilon 再展開を scratch_b に書き、swap で out に戻す（再確保なし）。
486        self.expand_epsilon_nodes_into(out, &mut scratch_b);
487        std::mem::swap(out, &mut scratch_b);
488    }
489
490    pub(crate) fn is_match_state(&self, current: &[usize]) -> bool {
491        matches!(self.match_decision(current), Some(true))
492    }
493
494    #[allow(dead_code)]
495    pub(crate) fn literal_candidates(&self, current: &[usize]) -> Vec<String> {
496        let expanded = self.expand_epsilon_nodes_borrowed(current);
497        let mut out = hashbrown::HashSet::new();
498        for node_idx in expanded.iter() {
499            out.extend(self.trie.nodes[*node_idx].literal_edges.keys().cloned());
500        }
501        let mut out = out.into_iter().collect::<Vec<_>>();
502        out.sort_unstable();
503        out
504    }
505
506    pub(crate) fn needs_directory_scan(&self, current: &[usize]) -> bool {
507        self.expand_epsilon_nodes_borrowed(current)
508            .iter()
509            .any(|node_idx| self.node_can_scan.get(*node_idx).copied().unwrap_or(false))
510    }
511
512    fn push_rule(&mut self, segments: Vec<SegmentMatcher>, is_exclude: bool, is_absolute: bool) {
513        let rule = CompiledRule {
514            rule_index: self.ordered_rules.len(),
515            is_exclude,
516            is_absolute,
517            segments,
518        };
519        self.trie.insert_rule(&rule);
520        self.ordered_rules.push(rule);
521        self.rebuild_epsilon_closure_cache();
522    }
523
524    fn expand_epsilon_nodes(&self, current: &[usize]) -> Vec<usize> {
525        let mut out = Vec::new();
526        self.expand_epsilon_nodes_into(current, &mut out);
527        out
528    }
529
530    /// `current` の epsilon 閉包を `out` に書き込む。`out.clear()` から始まる。
531    /// 呼び出し側の scratch を再利用し、`Vec` の再確保を防ぐ。
532    fn expand_epsilon_nodes_into(&self, current: &[usize], out: &mut Vec<usize>) {
533        out.clear();
534        if current.is_empty() {
535            return;
536        }
537        if current.len() == 1 {
538            if let Some(cached) = self.epsilon_closures.get(current[0]) {
539                out.extend_from_slice(cached);
540            }
541            return;
542        }
543
544        let mut overflow_seen: Option<HashSet<usize>> = None;
545        for node_idx in current {
546            let Some(cached) = self.epsilon_closures.get(*node_idx) else {
547                continue;
548            };
549            for value in cached {
550                push_unique_state(out, &mut overflow_seen, *value);
551            }
552        }
553        out.sort_unstable();
554    }
555
556    /// `current` の epsilon 閉包を借用で返す。
557    /// `len == 1` のとき（walker の最頻ケース）は cached closure を直接借用し、
558    /// clone も allocation も発生しない。
559    fn expand_epsilon_nodes_borrowed<'a>(&'a self, current: &[usize]) -> Cow<'a, [usize]> {
560        match current {
561            [] => Cow::Borrowed(&[]),
562            [one] => match self.epsilon_closures.get(*one) {
563                Some(c) => Cow::Borrowed(c.as_slice()),
564                None => Cow::Borrowed(&[]),
565            },
566            _ => {
567                let mut out = Vec::new();
568                self.expand_epsilon_nodes_into(current, &mut out);
569                Cow::Owned(out)
570            }
571        }
572    }
573
574    fn rebuild_epsilon_closure_cache(&mut self) {
575        let node_count = self.trie.nodes.len();
576        self.epsilon_closures = vec![Vec::new(); node_count];
577        self.node_can_scan = vec![false; node_count];
578        self.node_best_terminal = vec![None; node_count];
579        for node_idx in 0..node_count {
580            let mut closure = Vec::new();
581            let mut cursor = Some(node_idx);
582            while let Some(idx) = cursor {
583                closure.push(idx);
584                cursor = self.trie.nodes[idx].descend_edge;
585            }
586            closure.sort_unstable();
587            closure.dedup();
588            self.epsilon_closures[node_idx] = closure;
589
590            let node = &self.trie.nodes[node_idx];
591            self.node_can_scan[node_idx] = !node.wild_edges_general.is_empty()
592                || !node.wild_edges_suffix.is_empty()
593                || !node.wild_edges_prefix.is_empty()
594                || !node.wild_edges_exact1.is_empty()
595                || node.descend_edge.is_some();
596
597            let mut selected: Option<(usize, bool)> = None;
598            for terminal in &node.terminals {
599                if selected
600                    .as_ref()
601                    .is_none_or(|(idx, _)| terminal.rule_index >= *idx)
602                {
603                    selected = Some((terminal.rule_index, !terminal.is_exclude));
604                }
605            }
606            self.node_best_terminal[node_idx] = selected;
607        }
608    }
609
610    fn match_decision(&self, current: &[usize]) -> Option<bool> {
611        let expanded = self.expand_epsilon_nodes_borrowed(current);
612        let mut selected: Option<(usize, bool)> = None;
613        for node_idx in expanded.iter() {
614            if let Some((rule_index, include)) =
615                self.node_best_terminal.get(*node_idx).copied().flatten()
616                && selected.as_ref().is_none_or(|(idx, _)| rule_index >= *idx)
617            {
618                selected = Some((rule_index, include));
619            }
620        }
621        selected.map(|(_, include)| include)
622    }
623
624    /// 固定文字列がマッチするかどうかを判定します。
625    pub fn r#match(&self, path: &OsStr) -> bool {
626        let normalized = match Path::new(path).parse_dot() {
627            Ok(v) => v,
628            Err(_) => return false,
629        };
630        let normalized = match normalized.to_str() {
631            Some(v) => v,
632            None => return false,
633        };
634        let mut states = self.initial_states();
635        for part in normalized.split(MAIN_SEPARATOR).filter(|s| !s.is_empty()) {
636            states = self.advance_states(&states, part);
637            if states.is_empty() {
638                return false;
639            }
640        }
641        self.match_decision(&states).unwrap_or(false)
642    }
643
644    #[allow(dead_code)]
645    pub(crate) fn segments(&self) -> &[SegmentMatcher] {
646        assert!(
647            self.ordered_rules.len() <= 1,
648            "segments() is only available for single-rule CompiledGlob"
649        );
650        self.ordered_rules
651            .first()
652            .map(|rule| rule.segments.as_slice())
653            .unwrap_or(&[])
654    }
655
656    #[allow(dead_code)]
657    pub(crate) fn ordered_rules_segments(&self) -> Vec<&[SegmentMatcher]> {
658        self.ordered_rules
659            .iter()
660            .map(|rule| rule.segments.as_slice())
661            .collect()
662    }
663}
664
665const INLINE_STATE_DEDUP_LIMIT: usize = 16;
666
667fn push_unique_state(
668    out: &mut Vec<usize>,
669    overflow_seen: &mut Option<HashSet<usize>>,
670    value: usize,
671) {
672    if let Some(seen) = overflow_seen.as_mut() {
673        if seen.insert(value) {
674            out.push(value);
675        }
676        return;
677    }
678
679    if out.contains(&value) {
680        return;
681    }
682    out.push(value);
683
684    if out.len() > INLINE_STATE_DEDUP_LIMIT {
685        let mut seen = HashSet::with_capacity(out.len() * 2);
686        for existing in out.iter().copied() {
687            seen.insert(existing);
688        }
689        *overflow_seen = Some(seen);
690    }
691}
692
693/// 文字列がちょうど 1 文字かを判定する。
694/// `s.chars().count() == 1` と等価だが、全文字デコードを避け最大2要素で short-circuit する。
695#[inline]
696fn is_single_char(s: &str) -> bool {
697    let mut it = s.chars();
698    it.next().is_some() && it.next().is_none()
699}
700
701fn classify_wild_edge(pattern: &str) -> WildEdgeKind {
702    if pattern == "?" {
703        return WildEdgeKind::SingleChar;
704    }
705
706    if pattern.starts_with('*')
707        && !pattern[1..].is_empty()
708        && !pattern[1..].contains('*')
709        && !pattern[1..].contains('?')
710    {
711        return WildEdgeKind::Suffix(pattern[1..].to_string());
712    }
713
714    if pattern.ends_with('*')
715        && !pattern[..pattern.len() - 1].is_empty()
716        && !pattern[..pattern.len() - 1].contains('*')
717        && !pattern[..pattern.len() - 1].contains('?')
718    {
719        return WildEdgeKind::Prefix(pattern[..pattern.len() - 1].to_string());
720    }
721
722    WildEdgeKind::General
723}
724
725#[cfg(test)]
726mod tests {
727    use super::{CompiledGlob, SegmentMatcher};
728    use path_dedot::CWD;
729    use std::io;
730    use std::path::Path;
731
732    #[test]
733    fn expands_leading_double_star_in_segment() {
734        let glob = CompiledGlob::new("/tmp/**.rs").expect("glob must parse");
735        assert!(glob.r#match("/tmp/main.rs".as_ref()));
736        assert!(glob.r#match("/tmp/src/lib.rs".as_ref()));
737        assert!(!glob.r#match("/tmp/src/lib.ts".as_ref()));
738    }
739
740    #[test]
741    fn expands_trailing_double_star_in_segment() {
742        let glob = CompiledGlob::new("/tmp/tag-**").expect("glob must parse");
743        assert!(glob.r#match("/tmp/tag-a".as_ref()));
744        assert!(glob.r#match("/tmp/tag-a/b".as_ref()));
745        assert!(!glob.r#match("/tmp/taga".as_ref()));
746    }
747
748    #[test]
749    fn prepends_cwd_when_first_segment_is_not_anypath() {
750        let glob = CompiledGlob::new("*.rs").expect("glob must parse");
751        assert!(matches!(
752            glob.segments().first(),
753            Some(SegmentMatcher::AnyPath(_))
754        ));
755    }
756
757    #[test]
758    fn does_not_prepend_cwd_for_absolute_descend_glob() {
759        let glob = CompiledGlob::new("/**").expect("glob must parse");
760        assert!(!matches!(
761            glob.segments().first(),
762            Some(SegmentMatcher::AnyPath(_))
763        ));
764    }
765
766    #[test]
767    fn does_not_prepend_cwd_for_absolute_wildcard_glob() {
768        let glob = CompiledGlob::new("/*/").expect("glob must parse");
769        assert!(!matches!(
770            glob.segments().first(),
771            Some(SegmentMatcher::AnyPath(_))
772        ));
773    }
774
775    #[test]
776    fn prepends_cwd_for_relative_literal_prefix() {
777        let glob = CompiledGlob::new("target/*").expect("glob must parse");
778        let cwd = CWD.to_str().expect("cwd must be valid utf-8");
779        assert!(matches!(
780            glob.segments().first(),
781            Some(SegmentMatcher::AnyPath(inner)) if inner.as_str() == cwd
782        ));
783
784        let ok = format!("{}/target/file.txt", CWD.display());
785        assert!(glob.r#match(Path::new(&ok).as_os_str()));
786        assert!(!glob.r#match(Path::new("/target/file.txt").as_os_str()));
787    }
788
789    #[test]
790    fn merge_many_or_union_matches() {
791        let one = CompiledGlob::new("/tmp/**/*.rs").expect("glob must parse");
792        let two = CompiledGlob::new("/tmp/**/*.txt").expect("glob must parse");
793        let merged = CompiledGlob::merge_many(vec![one, two]).expect("must merge");
794        assert!(merged.r#match("/tmp/a/b/main.rs".as_ref()));
795        assert!(merged.r#match("/tmp/a/b/readme.txt".as_ref()));
796        assert!(!merged.r#match("/tmp/a/b/readme.md".as_ref()));
797    }
798
799    #[test]
800    fn merge_preserves_rule_order() {
801        let one = CompiledGlob::new("/tmp/**/*.rs").expect("glob must parse");
802        let two = CompiledGlob::new("/tmp/**/*.txt").expect("glob must parse");
803        let merged = one.merge(two);
804        assert_eq!(merged.ordered_rules.len(), 2);
805        assert_eq!(merged.ordered_rules[0].rule_index, 0);
806        assert_eq!(merged.ordered_rules[1].rule_index, 1);
807    }
808
809    #[test]
810    fn descend_dedup_equivalence_under_merge() {
811        let one = CompiledGlob::new("a/**/**/b").expect("glob must parse");
812        let two = CompiledGlob::new("a/**/b").expect("glob must parse");
813        let merged = one.merge(two);
814        let canonical = CompiledGlob::new("a/**/b").expect("glob must parse");
815        for path in ["a/b", "a/x/b", "a/x/y/b", "a/x/y/c"] {
816            assert_eq!(
817                merged.r#match(path.as_ref()),
818                canonical.r#match(path.as_ref())
819            );
820        }
821    }
822
823    #[test]
824    fn empty_merge_many_is_invalid_input() {
825        let merged = CompiledGlob::merge_many(Vec::new());
826        assert!(matches!(
827            merged,
828            Err(err) if err.kind() == io::ErrorKind::InvalidInput
829        ));
830    }
831
832    #[test]
833    fn supports_exclude_with_last_match_wins() {
834        let include = CompiledGlob::new("/tmp/**/*.txt").expect("glob must parse");
835        let exclude = CompiledGlob::new("!/tmp/**/ignore.txt").expect("glob must parse");
836        let reinclude = CompiledGlob::new("/tmp/**/ignore.txt").expect("glob must parse");
837
838        let merged =
839            CompiledGlob::merge_many(vec![include, exclude, reinclude]).expect("must merge");
840        assert!(merged.r#match("/tmp/a/keep.txt".as_ref()));
841        assert!(merged.r#match("/tmp/a/ignore.txt".as_ref()));
842    }
843
844    #[test]
845    fn exclude_can_remove_previous_include() {
846        let include = CompiledGlob::new("/tmp/**/*.txt").expect("glob must parse");
847        let exclude = CompiledGlob::new("!/tmp/**/ignore.txt").expect("glob must parse");
848        let merged = CompiledGlob::merge_many(vec![include, exclude]).expect("must merge");
849        assert!(merged.r#match("/tmp/a/keep.txt".as_ref()));
850        assert!(!merged.r#match("/tmp/a/ignore.txt".as_ref()));
851    }
852
853    #[test]
854    fn reject_empty_pattern_and_bare_exclude() {
855        assert!(matches!(
856            CompiledGlob::new(""),
857            Err(err) if err.kind() == io::ErrorKind::InvalidInput
858        ));
859        assert!(matches!(
860            CompiledGlob::new("!"),
861            Err(err) if err.kind() == io::ErrorKind::InvalidInput
862        ));
863    }
864
865    #[test]
866    fn start_paths_include_static_prefix_of_include_rules() {
867        let glob = CompiledGlob::new("/tmp/root/**.rs").expect("glob must parse");
868        let starts = glob.start_paths();
869        assert!(starts.iter().any(|p| p == Path::new("/tmp/root")));
870    }
871
872    #[test]
873    fn states_for_path_keeps_descend_capability() {
874        let glob = CompiledGlob::new("/tmp/root/**.rs").expect("glob must parse");
875        let states = glob.states_for_path(Path::new("/tmp/root"));
876        assert!(!states.is_empty());
877        let leaf_states = glob.advance_states(&states, "main.rs");
878        assert!(glob.is_match_state(&leaf_states));
879    }
880
881    #[test]
882    fn suffix_lane_matches_extension_pattern() {
883        let glob = CompiledGlob::new("/tmp/**/*.rs").expect("glob must parse");
884        assert!(glob.r#match("/tmp/a/main.rs".as_ref()));
885        assert!(!glob.r#match("/tmp/a/main.ts".as_ref()));
886    }
887
888    #[test]
889    fn prefix_lane_matches_prefix_pattern() {
890        let glob = CompiledGlob::new("/tmp/foo*/bar.txt").expect("glob must parse");
891        assert!(glob.r#match("/tmp/foobar/bar.txt".as_ref()));
892        assert!(glob.r#match("/tmp/foo/bar.txt".as_ref()));
893        assert!(!glob.r#match("/tmp/barfoo/bar.txt".as_ref()));
894    }
895
896    #[test]
897    fn complex_wildcard_falls_back_to_general_lane() {
898        let glob = CompiledGlob::new("/tmp/a*?b/file.txt").expect("glob must parse");
899        assert!(glob.r#match("/tmp/axxb/file.txt".as_ref()));
900        assert!(!glob.r#match("/tmp/ab/file.txt".as_ref()));
901    }
902}
walker/compiled_glob.rs

walker/
compiled_glob.rs
