tirea_state/
conflict.rs

1//! Touched path computation and conflict detection.
2//!
3//! This module provides utilities for analyzing patches to determine
4//! which paths are modified and detecting conflicts between patches.
5
6use crate::{LatticeRegistry, Op, Patch, Path};
7use std::collections::BTreeSet;
8
9/// Conflict information between two patches.
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub struct Conflict {
12    /// The path where the conflict occurs.
13    pub path: Path,
14    /// The type of conflict.
15    pub kind: ConflictKind,
16}
17
18/// Types of conflicts that can occur between patches.
19#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub enum ConflictKind {
21    /// Both patches modify the exact same path.
22    ExactMatch,
23    /// One patch modifies a parent of the other's path.
24    /// E.g., patch A modifies "user" while patch B modifies "user.name".
25    PrefixConflict,
26}
27
28/// Compute the set of paths touched by a patch.
29///
30/// # Arguments
31///
32/// * `patch` - The patch to analyze
33/// * `include_parents` - If true, include all parent paths. For example,
34///   if the patch modifies "a.b.c", the result will include "a", "a.b", and "a.b.c".
35///
36/// # Examples
37///
38/// ```
39/// use tirea_state::{Patch, Op, path, compute_touched};
40///
41/// let patch = Patch::new()
42///     .with_op(Op::set(path!("user", "name"), serde_json::json!("Alice")))
43///     .with_op(Op::set(path!("user", "age"), serde_json::json!(30)));
44///
45/// // Without parents
46/// let touched = compute_touched(&patch, false);
47/// assert!(touched.contains(&path!("user", "name")));
48/// assert!(touched.contains(&path!("user", "age")));
49/// assert!(!touched.contains(&path!("user")));
50///
51/// // With parents
52/// let touched_with_parents = compute_touched(&patch, true);
53/// assert!(touched_with_parents.contains(&path!("user")));
54/// assert!(touched_with_parents.contains(&path!("user", "name")));
55/// ```
56pub fn compute_touched(patch: &Patch, include_parents: bool) -> BTreeSet<Path> {
57    let mut touched = BTreeSet::new();
58
59    for op in patch.ops() {
60        let path = op.path();
61
62        if include_parents {
63            // Add all parent paths
64            let mut current = Path::root();
65            for seg in path.segments() {
66                current = current.with_segment(seg.clone());
67                touched.insert(current.clone());
68            }
69        } else {
70            touched.insert(path.clone());
71        }
72    }
73
74    touched
75}
76
77/// Detect conflicts between two sets of touched paths.
78///
79/// A conflict occurs when:
80/// - Both sets contain the exact same path (ExactMatch)
81/// - One path is a prefix of another (PrefixConflict)
82///
83/// # Examples
84///
85/// ```
86/// use tirea_state::{path, compute_touched, detect_conflicts, Patch, Op, ConflictKind};
87/// use serde_json::json;
88///
89/// let patch_a = Patch::new()
90///     .with_op(Op::set(path!("user"), json!({"name": "Alice"})));
91///
92/// let patch_b = Patch::new()
93///     .with_op(Op::set(path!("user", "name"), json!("Bob")));
94///
95/// let touched_a = compute_touched(&patch_a, false);
96/// let touched_b = compute_touched(&patch_b, false);
97///
98/// let conflicts = detect_conflicts(&touched_a, &touched_b);
99/// assert!(!conflicts.is_empty());
100/// assert!(conflicts.iter().any(|c| c.kind == ConflictKind::PrefixConflict));
101/// ```
102pub fn detect_conflicts(a: &BTreeSet<Path>, b: &BTreeSet<Path>) -> Vec<Conflict> {
103    let mut conflicts = Vec::new();
104
105    for path_a in a {
106        for path_b in b {
107            if path_a == path_b {
108                conflicts.push(Conflict {
109                    path: path_a.clone(),
110                    kind: ConflictKind::ExactMatch,
111                });
112            } else if path_a.is_prefix_of(path_b) || path_b.is_prefix_of(path_a) {
113                // Use the shorter path (the prefix) as the conflict path
114                let conflict_path = if path_a.len() < path_b.len() {
115                    path_a.clone()
116                } else {
117                    path_b.clone()
118                };
119                conflicts.push(Conflict {
120                    path: conflict_path,
121                    kind: ConflictKind::PrefixConflict,
122                });
123            }
124        }
125    }
126
127    conflicts
128}
129
130/// Check whether all ops in `patch` that touch `path` are `LatticeMerge`.
131fn is_lattice_only_at(patch: &Patch, path: &Path) -> bool {
132    patch
133        .ops()
134        .iter()
135        .filter(|op| op.path() == path)
136        .all(|op| matches!(op, Op::LatticeMerge { .. }))
137}
138
139/// Registry-aware conflict detection between two patches.
140///
141/// Behaves like [`PatchExt::conflicts_with`], but suppresses conflicts
142/// at paths where both patches use only `LatticeMerge` ops AND the
143/// path is registered in the [`LatticeRegistry`].
144pub fn conflicts_with_registry(a: &Patch, b: &Patch, registry: &LatticeRegistry) -> Vec<Conflict> {
145    let touched_a = compute_touched(a, false);
146    let touched_b = compute_touched(b, false);
147    detect_conflicts(&touched_a, &touched_b)
148        .into_iter()
149        .filter(|conflict| {
150            !(registry.get(&conflict.path).is_some()
151                && is_lattice_only_at(a, &conflict.path)
152                && is_lattice_only_at(b, &conflict.path))
153        })
154        .collect()
155}
156
157/// Extension trait for Patch to compute touched paths.
158pub trait PatchExt {
159    /// Compute the paths touched by this patch.
160    fn touched(&self, include_parents: bool) -> BTreeSet<Path>;
161
162    /// Check if this patch conflicts with another patch.
163    fn conflicts_with(&self, other: &Patch) -> Vec<Conflict>;
164}
165
166impl PatchExt for Patch {
167    fn touched(&self, include_parents: bool) -> BTreeSet<Path> {
168        compute_touched(self, include_parents)
169    }
170
171    fn conflicts_with(&self, other: &Patch) -> Vec<Conflict> {
172        let touched_self = compute_touched(self, false);
173        let touched_other = compute_touched(other, false);
174        detect_conflicts(&touched_self, &touched_other)
175    }
176}
177
178#[cfg(test)]
179mod tests {
180    use super::*;
181    use crate::{path, GSet, Op};
182    use serde_json::json;
183
184    #[test]
185    fn test_compute_touched_without_parents() {
186        let patch = Patch::new()
187            .with_op(Op::set(path!("a", "b"), json!(1)))
188            .with_op(Op::set(path!("x", "y", "z"), json!(2)));
189
190        let touched = compute_touched(&patch, false);
191
192        assert_eq!(touched.len(), 2);
193        assert!(touched.contains(&path!("a", "b")));
194        assert!(touched.contains(&path!("x", "y", "z")));
195        assert!(!touched.contains(&path!("a")));
196    }
197
198    #[test]
199    fn test_compute_touched_with_parents() {
200        let patch = Patch::new().with_op(Op::set(path!("a", "b", "c"), json!(1)));
201
202        let touched = compute_touched(&patch, true);
203
204        assert_eq!(touched.len(), 3);
205        assert!(touched.contains(&path!("a")));
206        assert!(touched.contains(&path!("a", "b")));
207        assert!(touched.contains(&path!("a", "b", "c")));
208    }
209
210    #[test]
211    fn test_detect_exact_conflict() {
212        let mut a = BTreeSet::new();
213        a.insert(path!("user", "name"));
214
215        let mut b = BTreeSet::new();
216        b.insert(path!("user", "name"));
217
218        let conflicts = detect_conflicts(&a, &b);
219
220        assert_eq!(conflicts.len(), 1);
221        assert_eq!(conflicts[0].kind, ConflictKind::ExactMatch);
222        assert_eq!(conflicts[0].path, path!("user", "name"));
223    }
224
225    #[test]
226    fn test_detect_prefix_conflict() {
227        let mut a = BTreeSet::new();
228        a.insert(path!("user"));
229
230        let mut b = BTreeSet::new();
231        b.insert(path!("user", "name"));
232
233        let conflicts = detect_conflicts(&a, &b);
234
235        assert_eq!(conflicts.len(), 1);
236        assert_eq!(conflicts[0].kind, ConflictKind::PrefixConflict);
237        assert_eq!(conflicts[0].path, path!("user"));
238    }
239
240    #[test]
241    fn test_no_conflict() {
242        let mut a = BTreeSet::new();
243        a.insert(path!("user", "name"));
244
245        let mut b = BTreeSet::new();
246        b.insert(path!("user", "age"));
247
248        let conflicts = detect_conflicts(&a, &b);
249
250        assert!(conflicts.is_empty());
251    }
252
253    #[test]
254    fn test_patch_ext_conflicts_with() {
255        let patch_a = Patch::new().with_op(Op::set(path!("user"), json!({})));
256        let patch_b = Patch::new().with_op(Op::set(path!("user", "name"), json!("Alice")));
257
258        let conflicts = patch_a.conflicts_with(&patch_b);
259
260        assert!(!conflicts.is_empty());
261    }
262
263    #[test]
264    fn test_conflicts_with_registry_suppresses_lattice_only() {
265        let mut registry = LatticeRegistry::new();
266        registry.register::<GSet<String>>(path!("tags"));
267
268        let patch_a = Patch::new().with_op(Op::lattice_merge(path!("tags"), json!(["a"])));
269        let patch_b = Patch::new().with_op(Op::lattice_merge(path!("tags"), json!(["b"])));
270
271        // Without registry: conflict detected
272        let conflicts = patch_a.conflicts_with(&patch_b);
273        assert!(!conflicts.is_empty());
274
275        // With registry: conflict suppressed
276        let conflicts = conflicts_with_registry(&patch_a, &patch_b, &registry);
277        assert!(conflicts.is_empty());
278    }
279
280    #[test]
281    fn test_conflicts_with_registry_mixed_ops_still_conflict() {
282        let mut registry = LatticeRegistry::new();
283        registry.register::<GSet<String>>(path!("tags"));
284
285        let patch_a = Patch::new()
286            .with_op(Op::lattice_merge(path!("tags"), json!(["a"])))
287            .with_op(Op::set(path!("tags"), json!(["override"])));
288        let patch_b = Patch::new().with_op(Op::lattice_merge(path!("tags"), json!(["b"])));
289
290        let conflicts = conflicts_with_registry(&patch_a, &patch_b, &registry);
291        assert!(!conflicts.is_empty(), "mixed ops should still conflict");
292    }
293
294    #[test]
295    fn test_conflicts_with_registry_unregistered_path_still_conflicts() {
296        let registry = LatticeRegistry::new(); // empty registry
297
298        let patch_a = Patch::new().with_op(Op::lattice_merge(path!("tags"), json!(["a"])));
299        let patch_b = Patch::new().with_op(Op::lattice_merge(path!("tags"), json!(["b"])));
300
301        let conflicts = conflicts_with_registry(&patch_a, &patch_b, &registry);
302        assert!(
303            !conflicts.is_empty(),
304            "unregistered path should still conflict"
305        );
306    }
307
308    #[test]
309    fn test_conflicts_with_registry_disjoint_paths_no_conflict() {
310        let registry = LatticeRegistry::new();
311
312        let patch_a = Patch::new().with_op(Op::set(path!("alpha"), json!(1)));
313        let patch_b = Patch::new().with_op(Op::set(path!("beta"), json!(2)));
314
315        let conflicts = conflicts_with_registry(&patch_a, &patch_b, &registry);
316        assert!(conflicts.is_empty());
317    }
318}
tirea_state/conflict.rs

tirea_state/
conflict.rs
