suture_core/patch/
commute.rs

1//! Commutativity checking for patches.
2//!
3//! Two patches commute if they can be applied in either order and produce
4//! the same result. In Suture, commutativity is determined by touch-set
5//! disjointness (THM-COMM-001 from YP-ALGEBRA-PATCH-001).
6
7use crate::patch::types::Patch;
8
9/// Result of a commutativity check.
10#[derive(Clone, Debug, PartialEq, Eq)]
11pub enum CommuteResult {
12    /// The two patches commute — they can be applied in any order.
13    Commutes,
14    /// The two patches do NOT commute — their touch sets overlap.
15    DoesNotCommute {
16        /// The addresses where both patches touch (the conflict addresses).
17        conflict_addresses: Vec<String>,
18    },
19}
20
21/// Check if two patches commute.
22///
23/// # Correctness
24///
25/// Per THM-COMM-001 (YP-ALGEBRA-PATCH-001):
26/// If T(P₁) ∩ T(P₂) = ∅, then P₁ ∘ P₂ = P₂ ∘ P₁.
27///
28/// This function implements the sufficient condition: disjoint touch sets.
29/// Note that some patches with overlapping touch sets MAY still commute
30/// (e.g., writing the same value), but we conservatively report them as
31/// non-commuting to guarantee correctness.
32pub fn commute(p1: &Patch, p2: &Patch) -> CommuteResult {
33    // Identity patches commute with everything
34    if p1.is_identity() || p2.is_identity() {
35        return CommuteResult::Commutes;
36    }
37
38    if !p1.touch_set.intersects(&p2.touch_set) {
39        CommuteResult::Commutes
40    } else {
41        let intersection = p1.touch_set.intersection(&p2.touch_set);
42        let conflict_addresses: Vec<String> = intersection.iter().cloned().collect();
43        CommuteResult::DoesNotCommute { conflict_addresses }
44    }
45}
46
47/// Check if a list of patches are pairwise commutative.
48///
49/// Returns `true` only if ALL pairs in the list commute.
50/// This is O(n²) in the number of patches.
51#[allow(dead_code)]
52pub fn all_commute(patches: &[Patch]) -> bool {
53    for i in 0..patches.len() {
54        for j in (i + 1)..patches.len() {
55            if !matches!(commute(&patches[i], &patches[j]), CommuteResult::Commutes) {
56                return false;
57            }
58        }
59    }
60    true
61}
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66    use crate::patch::types::{OperationType, Patch, TouchSet};
67    use suture_common::Hash;
68
69    fn patch_with_touch(addr: &str) -> Patch {
70        Patch::new(
71            OperationType::Modify,
72            TouchSet::single(addr),
73            Some(format!("file_{}", addr)),
74            vec![],
75            vec![],
76            "test".to_string(),
77            format!("edit {}", addr),
78        )
79    }
80
81    fn patch_with_touches(addrs: &[&str]) -> Patch {
82        Patch::new(
83            OperationType::Modify,
84            TouchSet::from_addrs(addrs.iter().copied()),
85            None,
86            vec![],
87            vec![],
88            "test".to_string(),
89            "multi edit".to_string(),
90        )
91    }
92
93    #[test]
94    fn test_disjoint_patches_commute() {
95        let p1 = patch_with_touch("A1");
96        let p2 = patch_with_touch("B1");
97        assert_eq!(commute(&p1, &p2), CommuteResult::Commutes);
98    }
99
100    #[test]
101    fn test_overlapping_patches_do_not_commute() {
102        let p1 = patch_with_touch("A1");
103        let p2 = patch_with_touch("A1");
104        assert_eq!(
105            commute(&p1, &p2),
106            CommuteResult::DoesNotCommute {
107                conflict_addresses: vec!["A1".to_string()]
108            }
109        );
110    }
111
112    #[test]
113    fn test_identity_commutes_with_everything() {
114        let parent = Hash::ZERO;
115        let identity = Patch::identity(parent, "test".to_string());
116        let p = patch_with_touch("A1");
117        assert_eq!(commute(&identity, &p), CommuteResult::Commutes);
118        assert_eq!(commute(&p, &identity), CommuteResult::Commutes);
119    }
120
121    #[test]
122    fn test_partial_overlap() {
123        let p1 = patch_with_touches(&["A1", "B1", "C1"]);
124        let p2 = patch_with_touches(&["C1", "D1", "E1"]);
125
126        match commute(&p1, &p2) {
127            CommuteResult::DoesNotCommute { conflict_addresses } => {
128                assert_eq!(conflict_addresses, vec!["C1".to_string()]);
129            }
130            CommuteResult::Commutes => panic!("Expected DoesNotCommute"),
131        }
132    }
133
134    #[test]
135    fn test_commutativity_is_symmetric() {
136        let p1 = patch_with_touch("A1");
137        let p2 = patch_with_touch("B1");
138        assert_eq!(commute(&p1, &p2), commute(&p2, &p1));
139    }
140
141    #[test]
142    fn test_all_commute_empty() {
143        assert!(all_commute(&[]));
144    }
145
146    #[test]
147    fn test_all_commute_single() {
148        let p = patch_with_touch("A1");
149        assert!(all_commute(&[p]));
150    }
151
152    #[test]
153    fn test_all_commute_disjoint() {
154        let patches = vec![
155            patch_with_touch("A1"),
156            patch_with_touch("B1"),
157            patch_with_touch("C1"),
158        ];
159        assert!(all_commute(&patches));
160    }
161
162    #[test]
163    fn test_all_commute_with_overlap() {
164        let patches = vec![
165            patch_with_touch("A1"),
166            patch_with_touch("B1"),
167            patch_with_touch("A1"), // Overlaps with first
168        ];
169        assert!(!all_commute(&patches));
170    }
171}
suture_core/patch/commute.rs

suture_core/patch/
commute.rs
