xml_3dm/matching/
tri.rs

1//! Three-way matching between a base and two branch trees.
2//!
3//! `TriMatching` coordinates matching between a base tree and two branch trees
4//! (left and right). It uses a `Matching` implementation (typically `HeuristicMatching`)
5//! to establish correspondences, then sets up the partner relationships between
6//! nodes in the two branches via their common base matches.
7
8use crate::node::base::BaseNode;
9use crate::node::branch::BranchNode;
10use crate::node::NodeRef;
11
12use super::{HeuristicMatching, Matching};
13
14/// Matching between a base and two branch trees.
15///
16/// This struct coordinates the matching process for 3-way merge:
17/// 1. Matches the right branch against the base tree
18/// 2. Swaps left/right matchings in base nodes (so right matchings become "right")
19/// 3. Matches the left branch against the base tree
20/// 4. Sets up partner relationships so each branch node knows its partners in the other branch
21pub struct TriMatching {
22    left_root: NodeRef,
23    right_root: NodeRef,
24    base_root: NodeRef,
25}
26
27impl TriMatching {
28    /// Creates a new TriMatching using the default HeuristicMatching algorithm.
29    pub fn new(left: NodeRef, base: NodeRef, right: NodeRef) -> Self {
30        Self::with_matching::<HeuristicMatching, HeuristicMatching>(left, base, right)
31    }
32
33    /// Creates a new TriMatching with a custom copy threshold.
34    ///
35    /// The copy threshold determines the minimum size (in info bytes) for a
36    /// subtree to be considered a copy. Smaller subtrees are treated as separate
37    /// insertions. Use 0 to disable copy detection.
38    pub fn with_copy_threshold(
39        left: NodeRef,
40        base: NodeRef,
41        right: NodeRef,
42        copy_threshold: i32,
43    ) -> Self {
44        // Match right branch first
45        let mut right_matcher = HeuristicMatching::with_copy_threshold(copy_threshold);
46        right_matcher.build_matching(&base, &right);
47
48        // Swap left/right matchings in base tree
49        Self::swap_left_right(&base);
50
51        // Match left branch
52        let mut left_matcher = HeuristicMatching::with_copy_threshold(copy_threshold);
53        left_matcher.build_matching(&base, &left);
54
55        // Set partner fields in both branches
56        Self::set_partners(&left, false);
57        Self::set_partners(&right, true);
58
59        TriMatching {
60            left_root: left,
61            right_root: right,
62            base_root: base,
63        }
64    }
65
66    /// Creates a new TriMatching with custom matching algorithms.
67    ///
68    /// This allows using different matching strategies for left and right branches.
69    /// For example, DiffMatching could be used for one branch if needed.
70    pub fn with_matching<L: Matching + Default, R: Matching + Default>(
71        left: NodeRef,
72        base: NodeRef,
73        right: NodeRef,
74    ) -> Self {
75        // Match right branch first
76        let mut right_matcher = R::default();
77        right_matcher.build_matching(&base, &right);
78
79        // Swap left/right matchings in base tree
80        // The matcher always populates "left" matches, so we need to swap
81        // to put right matchings in the right field
82        Self::swap_left_right(&base);
83
84        // Match left branch
85        let mut left_matcher = L::default();
86        left_matcher.build_matching(&base, &left);
87
88        // Set partner fields in both branches
89        Self::set_partners(&left, false);
90        Self::set_partners(&right, true);
91
92        TriMatching {
93            left_root: left,
94            right_root: right,
95            base_root: base,
96        }
97    }
98
99    /// Recursively swaps left and right matching fields in base nodes.
100    ///
101    /// The HeuristicMatching always fills in the "left" matching field,
102    /// so we call this after matching the right branch to move those
103    /// matchings to the "right" field before matching the left branch.
104    fn swap_left_right(base: &NodeRef) {
105        BaseNode::swap_left_right_matchings(base);
106
107        let children: Vec<NodeRef> = base.borrow().children().to_vec();
108        for child in children {
109            Self::swap_left_right(&child);
110        }
111    }
112
113    /// Sets the partner fields of branch nodes.
114    ///
115    /// For each branch node with a base match, sets its partners to be
116    /// the nodes from the other branch that match the same base node.
117    ///
118    /// # Arguments
119    /// * `node` - The branch node to set partners for
120    /// * `partner_in_left` - If true, partners are in the left tree; otherwise in the right tree
121    fn set_partners(node: &NodeRef, partner_in_left: bool) {
122        if let Some(base_match) = BranchNode::base_match(node) {
123            // Get the partners from the other branch
124            let partners = if partner_in_left {
125                Some(BaseNode::left(&base_match))
126            } else {
127                Some(BaseNode::right(&base_match))
128            };
129            BranchNode::set_partners(node, partners);
130        } else {
131            BranchNode::set_partners(node, None);
132        }
133
134        // Recurse to children
135        let children: Vec<NodeRef> = node.borrow().children().to_vec();
136        for child in children {
137            Self::set_partners(&child, partner_in_left);
138        }
139    }
140
141    /// Returns a reference to the left branch root.
142    pub fn left_root(&self) -> &NodeRef {
143        &self.left_root
144    }
145
146    /// Returns a reference to the right branch root.
147    pub fn right_root(&self) -> &NodeRef {
148        &self.right_root
149    }
150
151    /// Returns a reference to the base tree root.
152    pub fn base_root(&self) -> &NodeRef {
153        &self.base_root
154    }
155}
156
157#[cfg(test)]
158mod tests {
159    use super::*;
160    use crate::node::{new_base_node, new_branch_node, NodeInner, XmlContent, XmlElement, XmlText};
161    use std::collections::HashMap;
162
163    fn make_element(name: &str) -> XmlContent {
164        XmlContent::Element(XmlElement::new(name.to_string(), HashMap::new()))
165    }
166
167    fn make_text(text: &str) -> XmlContent {
168        XmlContent::Text(XmlText::new(text))
169    }
170
171    #[test]
172    fn test_tri_matching_simple() {
173        // Create matching trees:
174        // Base:  <root><a/></root>
175        // Left:  <root><a/></root>
176        // Right: <root><a/></root>
177
178        let base_root = new_base_node(Some(make_element("root")));
179        let base_a = new_base_node(Some(make_element("a")));
180        NodeInner::add_child_to_ref(&base_root, base_a);
181
182        let left_root = new_branch_node(Some(make_element("root")));
183        let left_a = new_branch_node(Some(make_element("a")));
184        NodeInner::add_child_to_ref(&left_root, left_a.clone());
185
186        let right_root = new_branch_node(Some(make_element("root")));
187        let right_a = new_branch_node(Some(make_element("a")));
188        NodeInner::add_child_to_ref(&right_root, right_a.clone());
189
190        let matching = TriMatching::new(left_root.clone(), base_root.clone(), right_root.clone());
191
192        // Both branches should be matched
193        assert!(BranchNode::has_base_match(&left_a));
194        assert!(BranchNode::has_base_match(&right_a));
195
196        // They should be partners (via base match)
197        let left_partners = BranchNode::partners(&left_a);
198        assert!(left_partners.is_some());
199        let partners_borrowed = left_partners.unwrap();
200        assert_eq!(partners_borrowed.borrow().match_count(), 1);
201
202        // Verify tri-matching accessors
203        assert_eq!(matching.left_root().borrow().id(), left_root.borrow().id());
204        assert_eq!(
205            matching.right_root().borrow().id(),
206            right_root.borrow().id()
207        );
208        assert_eq!(matching.base_root().borrow().id(), base_root.borrow().id());
209    }
210
211    #[test]
212    fn test_tri_matching_with_modifications() {
213        // Base:  <root><a>text</a></root>
214        // Left:  <root><a>modified</a></root>
215        // Right: <root><a>text</a></root>
216
217        let base_root = new_base_node(Some(make_element("root")));
218        let base_a = new_base_node(Some(make_element("a")));
219        let base_text = new_base_node(Some(make_text("text")));
220        NodeInner::add_child_to_ref(&base_root, base_a.clone());
221        NodeInner::add_child_to_ref(&base_a, base_text);
222
223        let left_root = new_branch_node(Some(make_element("root")));
224        let left_a = new_branch_node(Some(make_element("a")));
225        let left_text = new_branch_node(Some(make_text("modified")));
226        NodeInner::add_child_to_ref(&left_root, left_a.clone());
227        NodeInner::add_child_to_ref(&left_a, left_text.clone());
228
229        let right_root = new_branch_node(Some(make_element("root")));
230        let right_a = new_branch_node(Some(make_element("a")));
231        let right_text = new_branch_node(Some(make_text("text")));
232        NodeInner::add_child_to_ref(&right_root, right_a.clone());
233        NodeInner::add_child_to_ref(&right_a, right_text.clone());
234
235        let _matching = TriMatching::new(left_root, base_root, right_root);
236
237        // Element 'a' should be matched in both branches
238        assert!(BranchNode::has_base_match(&left_a));
239        assert!(BranchNode::has_base_match(&right_a));
240
241        // Right text should match (identical)
242        assert!(BranchNode::has_base_match(&right_text));
243
244        // Left text might not match (different content) - depends on fuzzy matching
245        // The actual result depends on the matching algorithm
246    }
247
248    #[test]
249    fn test_tri_matching_unmatched_nodes() {
250        // Base:  <root><a/></root>
251        // Left:  <root><a/><b/></root>  (b is new)
252        // Right: <root><a/></root>
253
254        let base_root = new_base_node(Some(make_element("root")));
255        let base_a = new_base_node(Some(make_element("a")));
256        NodeInner::add_child_to_ref(&base_root, base_a);
257
258        let left_root = new_branch_node(Some(make_element("root")));
259        let left_a = new_branch_node(Some(make_element("a")));
260        let left_b = new_branch_node(Some(make_element("b")));
261        NodeInner::add_child_to_ref(&left_root, left_a.clone());
262        NodeInner::add_child_to_ref(&left_root, left_b.clone());
263
264        let right_root = new_branch_node(Some(make_element("root")));
265        let right_a = new_branch_node(Some(make_element("a")));
266        NodeInner::add_child_to_ref(&right_root, right_a.clone());
267
268        let _matching = TriMatching::new(left_root, base_root, right_root);
269
270        // 'a' should be matched in both
271        assert!(BranchNode::has_base_match(&left_a));
272        assert!(BranchNode::has_base_match(&right_a));
273
274        // 'b' is new and should not have a base match
275        assert!(!BranchNode::has_base_match(&left_b));
276
277        // 'b' should have no partners
278        assert!(BranchNode::partners(&left_b).is_none());
279    }
280}
xml_3dm/matching/tri.rs

xml_3dm/matching/
tri.rs
