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