codemod_core/transform/
conflict.rs

1//! Conflict detection for overlapping or incompatible matches.
2//!
3//! When multiple pattern matches are found in a single file their byte ranges
4//! may overlap. Applying overlapping replacements can corrupt the source.
5//! This module detects such conflicts *before* any transformation is applied
6//! so that the user or the engine can decide how to resolve them.
7
8use crate::pattern::matcher::Match;
9
10// ---------------------------------------------------------------------------
11// Public types
12// ---------------------------------------------------------------------------
13
14/// Describes a conflict between two or more matches.
15#[derive(Debug, Clone)]
16pub struct Conflict {
17    /// Index of the match (in the original matches slice) that caused the
18    /// conflict.
19    pub match_index: usize,
20    /// Index of the other match that this one overlaps with.
21    pub other_index: usize,
22    /// Human-readable description of the conflict.
23    pub description: String,
24    /// Suggested resolution strategies.
25    pub suggestions: Vec<String>,
26}
27
28/// How to resolve a detected conflict.
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub enum ConflictResolution {
31    /// Apply the conflicting match anyway.
32    Apply,
33    /// Skip the conflicting match.
34    Skip,
35    /// Apply all remaining matches regardless of conflicts.
36    ApplyAll,
37    /// Skip all remaining conflicting matches.
38    SkipAll,
39}
40
41// ---------------------------------------------------------------------------
42// ConflictResolver
43// ---------------------------------------------------------------------------
44
45/// Detects overlapping or otherwise conflicting matches within a single file.
46pub struct ConflictResolver;
47
48impl ConflictResolver {
49    /// Detect conflicts among a set of matches.
50    ///
51    /// Two matches conflict if their byte ranges overlap. The returned
52    /// [`Conflict`] entries reference the *indices* into the input `matches`
53    /// slice.
54    pub fn detect_conflicts(matches: &[Match]) -> Vec<Conflict> {
55        let mut conflicts = Vec::new();
56
57        if matches.len() < 2 {
58            return conflicts;
59        }
60
61        // Build a list of (index, start, end) sorted by start offset.
62        let mut sorted: Vec<(usize, usize, usize)> = matches
63            .iter()
64            .enumerate()
65            .map(|(i, m)| (i, m.byte_range.start, m.byte_range.end))
66            .collect();
67        sorted.sort_by_key(|&(_, start, _)| start);
68
69        // Sweep-line: check each pair of adjacent sorted entries for overlap.
70        for window in sorted.windows(2) {
71            let (idx_a, _start_a, end_a) = window[0];
72            let (idx_b, start_b, _end_b) = window[1];
73
74            if start_b < end_a {
75                conflicts.push(Conflict {
76                    match_index: idx_b,
77                    other_index: idx_a,
78                    description: format!(
79                        "Match at byte offset {} overlaps with match at byte offset {} (overlap starts at byte {})",
80                        matches[idx_b].byte_range.start,
81                        matches[idx_a].byte_range.start,
82                        start_b,
83                    ),
84                    suggestions: vec![
85                        "Skip the later match".into(),
86                        "Skip the earlier match".into(),
87                        "Manually resolve the overlap".into(),
88                    ],
89                });
90            }
91        }
92
93        conflicts
94    }
95
96    /// Filter out conflicting matches, keeping only non-overlapping ones.
97    ///
98    /// Uses a greedy strategy: iterate matches sorted by start offset and
99    /// keep a match only if it does not overlap with the previously kept one.
100    pub fn resolve_greedy(matches: &[Match]) -> Vec<usize> {
101        if matches.is_empty() {
102            return Vec::new();
103        }
104
105        let mut indexed: Vec<(usize, usize, usize)> = matches
106            .iter()
107            .enumerate()
108            .map(|(i, m)| (i, m.byte_range.start, m.byte_range.end))
109            .collect();
110        indexed.sort_by_key(|&(_, start, _)| start);
111
112        let mut kept = Vec::new();
113        let mut last_end: usize = 0;
114
115        for (idx, start, end) in indexed {
116            if start >= last_end {
117                kept.push(idx);
118                last_end = end;
119            }
120        }
121
122        kept
123    }
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129    use crate::pattern::matcher::{Match, Position};
130    use std::collections::HashMap;
131
132    fn make_match(start: usize, end: usize) -> Match {
133        Match {
134            byte_range: start..end,
135            start_position: Position {
136                line: 0,
137                column: start,
138            },
139            end_position: Position {
140                line: 0,
141                column: end,
142            },
143            matched_text: String::new(),
144            bindings: HashMap::new(),
145        }
146    }
147
148    #[test]
149    fn test_no_conflicts() {
150        let matches = vec![make_match(0, 5), make_match(10, 15)];
151        let conflicts = ConflictResolver::detect_conflicts(&matches);
152        assert!(conflicts.is_empty());
153    }
154
155    #[test]
156    fn test_overlapping_conflicts() {
157        let matches = vec![make_match(0, 10), make_match(5, 15)];
158        let conflicts = ConflictResolver::detect_conflicts(&matches);
159        assert_eq!(conflicts.len(), 1);
160        assert_eq!(conflicts[0].match_index, 1);
161        assert_eq!(conflicts[0].other_index, 0);
162    }
163
164    #[test]
165    fn test_adjacent_no_conflict() {
166        let matches = vec![make_match(0, 5), make_match(5, 10)];
167        let conflicts = ConflictResolver::detect_conflicts(&matches);
168        assert!(conflicts.is_empty());
169    }
170
171    #[test]
172    fn test_resolve_greedy() {
173        let matches = vec![make_match(0, 10), make_match(5, 15), make_match(15, 20)];
174        let kept = ConflictResolver::resolve_greedy(&matches);
175        assert_eq!(kept, vec![0, 2]);
176    }
177
178    #[test]
179    fn test_single_match() {
180        let matches = vec![make_match(0, 5)];
181        let conflicts = ConflictResolver::detect_conflicts(&matches);
182        assert!(conflicts.is_empty());
183        let kept = ConflictResolver::resolve_greedy(&matches);
184        assert_eq!(kept, vec![0]);
185    }
186}
codemod_core/transform/conflict.rs

codemod_core/transform/
conflict.rs
