xml_3dm/merge/

mod.rs

//! 3-way merge algorithm.
//!
//! This module implements the core 3-way merge algorithm that combines
//! two branch trees relative to a common base tree. The algorithm handles
//! insert, delete, update, move, and copy operations on subtrees.
//!
//! # Algorithm Overview
//!
//! The merge proceeds recursively through the matched trees:
//! 1. Create MergeLists for each branch's children
//! 2. Remove deleted/moved nodes and resolve conflicts
//! 3. Merge the lists into MergePairs
//! 4. For each pair, merge node content and recurse for children

mod conflict_log;
mod edit_log;
mod merge_list;
mod merge_pair;

pub use conflict_log::{ConflictLog, ConflictType};
pub use edit_log::{EditLog, EditType};
pub use merge_list::{MergeEntry, MergeList};
pub use merge_pair::{MergePair, MergePairList};

use std::io::Write;

use crate::matching::TriMatching;
use crate::node::base::BaseNode;
use crate::node::branch::BranchNode;
use crate::node::{new_node_ref, MatchType, NodeInner, NodeRef, XmlContent, XmlElement};
use crate::xml::XmlPrinter;

/// Operation codes for merge list processing.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Operation {
    /// No operation - node unchanged.
    Nop,
    /// Move inside child list.
    MoveI,
    /// Move far (to different parent).
    MoveF,
    /// Node deleted.
    Delete,
}

/// The main merge struct that orchestrates the 3-way merge.
pub struct Merge {
    /// The tri-matching with base, left, and right trees.
    matching: TriMatching,
    /// Log of conflicts encountered during merge.
    pub conflict_log: ConflictLog,
    /// Log of edit operations performed.
    pub edit_log: EditLog,
}

impl Merge {
    /// Creates a new Merge from a TriMatching.
    pub fn new(matching: TriMatching) -> Self {
        Merge {
            matching,
            conflict_log: ConflictLog::new(),
            edit_log: EditLog::new(),
        }
    }

    /// Returns a reference to the tri-matching.
    pub fn matching(&self) -> &TriMatching {
        &self.matching
    }

    /// Runs the 3-way merge and writes the result.
    ///
    /// The output is written as XML to the provided writer.
    pub fn merge<W: Write>(&mut self, writer: &mut W) -> std::io::Result<()> {
        // Build the merged tree
        let tree = self.merge_to_tree();

        // Use XmlPrinter for proper text content handling
        let mut printer = XmlPrinter::new(writer);
        printer.print(&tree)
    }

    /// Runs the 3-way merge and returns the merged tree.
    ///
    /// This is useful when you need to programmatically inspect or
    /// further modify the merge result before output.
    pub fn merge_to_tree(&mut self) -> NodeRef {
        // Create synthetic root node
        let root_content = XmlContent::Element(XmlElement::new(
            "$ROOT$".to_string(),
            std::collections::HashMap::new(),
        ));
        let root = new_node_ref(NodeInner::new_base(Some(root_content)));

        // Build children recursively
        self.tree_merge_to_node(
            Some(self.matching.left_root().clone()),
            Some(self.matching.right_root().clone()),
            &root,
        );

        root
    }

    /// Recursive tree merge that builds nodes instead of writing output.
    fn tree_merge_to_node(&mut self, a: Option<NodeRef>, b: Option<NodeRef>, parent: &NodeRef) {
        // Create merge lists for each branch
        let mlist_a = a.as_ref().map(|node| self.make_merge_list(node));
        let mlist_b = b.as_ref().map(|node| self.make_merge_list(node));

        // Generate merge pair list
        let merged = match (&mlist_a, &mlist_b) {
            (Some(ma), Some(mb)) => self.make_merge_pair_list(ma.clone(), mb.clone()),
            (Some(ma), None) => self.merge_list_to_pair_list(ma, None),
            (None, Some(mb)) => self.merge_list_to_pair_list(mb, None),
            (None, None) => MergePairList::new(),
        };

        // Process each merge pair
        for pair in merged.pairs() {
            let merged_content = self.merge_node_content(pair);

            if let Some(content) = merged_content {
                match &content {
                    XmlContent::Element(elem) if elem.qname() == "$ROOT$" => {
                        // Skip synthetic root but process children
                        let partners = self.get_recursion_partners(pair);
                        self.tree_merge_to_node(partners.first, partners.second, parent);
                    }
                    _ => {
                        // Create new node with merged content
                        let child = new_node_ref(NodeInner::new_base(Some(content.clone())));

                        // Add to parent
                        NodeInner::add_child_to_ref(parent, child.clone());

                        // Recurse for element children
                        if let XmlContent::Element(_) = content {
                            let partners = self.get_recursion_partners(pair);
                            self.tree_merge_to_node(partners.first, partners.second, &child);
                        }
                    }
                }
            }
        }
    }

    /// Creates a merge list from the children of a branch node.
    fn make_merge_list(&mut self, parent: &NodeRef) -> MergeList {
        MergeList::from_branch(parent, &mut self.edit_log)
    }

    /// Merges two merge lists into a merge pair list.
    fn make_merge_pair_list(&mut self, mlist_a: MergeList, mlist_b: MergeList) -> MergePairList {
        let mut mlist_a = mlist_a;
        let mut mlist_b = mlist_b;

        // Remove deleted or far-moved nodes
        self.remove_deleted_or_moved(&mut mlist_a, &mut mlist_b);

        // Checkpoint for potential rollback
        self.edit_log.checkpoint();

        // Lists should now have the same entries
        if mlist_a.entry_count() != mlist_b.entry_count() {
            // Fallback to simpler merge
            self.edit_log.rewind();
            let is_left = mlist_a
                .entry_parent()
                .map(|p| BranchNode::is_left_tree(&p))
                .unwrap_or(true);
            return if is_left {
                self.merge_list_to_pair_list(&mlist_a, Some(&mlist_b))
            } else {
                self.merge_list_to_pair_list(&mlist_b, Some(&mlist_a))
            };
        }

        let mut merged = MergePairList::new();
        let mut pos_a = 0usize;
        let mut pos_b = 0usize;

        loop {
            let ea = mlist_a.entry(pos_a);
            let eb = mlist_b.entry(pos_b);

            if ea.is_none() || eb.is_none() {
                break;
            }

            let ea = ea.unwrap();
            let eb = eb.unwrap();

            // Add hangons from ea
            for hangon in ea.hangons() {
                let partner = hangon.borrow().first_partner(MatchType::FULL);
                merged.append(Some(hangon.clone()), partner);
                self.log_hangon_struct_ops(hangon);
            }

            // Add hangons from eb (if not equal to ea's hangons)
            if !self.check_hangon_combine(ea, eb) {
                for hangon in eb.hangons() {
                    let partner = hangon.borrow().first_partner(MatchType::FULL);
                    merged.append(Some(hangon.clone()), partner);
                    self.log_hangon_struct_ops(hangon);
                }
            }

            // Determine next positions
            let next_a: Option<usize>;
            let next_b: Option<usize>;

            let ea_locked = ea.locked && mlist_a.entry(pos_a + 1).is_some_and(|e| e.locked);
            let eb_locked = eb.locked && mlist_b.entry(pos_b + 1).is_some_and(|e| e.locked);

            if !ea_locked && !eb_locked {
                // No locking, both advance
                next_a = Some(pos_a + 1);
                next_b = Some(pos_b + 1);
            } else if ea_locked && !eb_locked {
                next_a = Some(pos_a + 1);
                next_b = mlist_b.find_partner_index(mlist_a.entry(pos_a + 1));
            } else if !ea_locked && eb_locked {
                next_b = Some(pos_b + 1);
                next_a = mlist_a.find_partner_index(mlist_b.entry(pos_b + 1));
            } else {
                // Both locked - check for conflict
                let partner_b = mlist_b.find_partner_index(mlist_a.entry(pos_a + 1));
                if partner_b != Some(pos_b + 1) {
                    // Conflict - fallback
                    self.conflict_log.add_list_conflict(
                        ConflictType::Move,
                        "Conflicting moves inside child list",
                        ea.node().and_then(|n| BranchNode::base_match(&n)),
                        ea.node(),
                        eb.node(),
                    );
                    self.edit_log.rewind();
                    let is_left = mlist_a
                        .entry_parent()
                        .map(|p| BranchNode::is_left_tree(&p))
                        .unwrap_or(true);
                    return if is_left {
                        self.merge_list_to_pair_list(&mlist_a, Some(&mlist_b))
                    } else {
                        self.merge_list_to_pair_list(&mlist_b, Some(&mlist_a))
                    };
                }
                next_a = Some(pos_a + 1);
                next_b = partner_b;
            }

            pos_a = next_a.unwrap_or(pos_a + 1);
            pos_b = next_b.unwrap_or(pos_b + 1);

            // Check if done (at END marker)
            if mlist_a.is_end(pos_a) || mlist_b.is_end(pos_b) {
                break;
            }

            // Add the main entry pair
            let ea = mlist_a.entry(pos_a);
            let eb = mlist_b.entry(pos_b);
            if let (Some(ea), Some(eb)) = (ea, eb) {
                merged.append(ea.node(), eb.node());
                self.log_entry_struct_ops(ea, eb);
            }
        }

        self.edit_log.commit();
        merged
    }

    /// Converts a single merge list to a pair list.
    fn merge_list_to_pair_list(
        &mut self,
        mlist_a: &MergeList,
        mlist_b: Option<&MergeList>,
    ) -> MergePairList {
        let mut merged = MergePairList::new();

        for (i, entry) in mlist_a.entries().iter().enumerate() {
            // Skip START marker but process its hangons
            if i > 0 && !mlist_a.is_end(i) {
                let node = entry.node();
                let partner = node
                    .as_ref()
                    .and_then(|n| n.borrow().first_partner(MatchType::FULL));
                merged.append(node, partner);
                if let Some(n) = entry.node() {
                    self.log_hangon_struct_ops(&n);
                }
            }

            // Add hangons
            for hangon in entry.hangons() {
                let partner = hangon.borrow().first_partner(MatchType::FULL);
                merged.append(Some(hangon.clone()), partner);
                self.log_hangon_struct_ops(hangon);
            }

            // Add hangons from mlist_b if present
            if let Some(mb) = mlist_b {
                if let Some(partner_entry) = mb.find_partner(entry) {
                    if !self.check_hangon_combine(entry, partner_entry) {
                        for hangon in partner_entry.hangons() {
                            let partner = hangon.borrow().first_partner(MatchType::FULL);
                            merged.append(Some(hangon.clone()), partner);
                            self.log_hangon_struct_ops(hangon);
                        }
                    }
                }
            }
        }

        merged
    }

    /// Removes deleted or far-moved nodes from merge lists.
    fn remove_deleted_or_moved(&mut self, mlist_a: &mut MergeList, mlist_b: &mut MergeList) {
        let base_parent = mlist_a
            .entry_parent()
            .and_then(|p| BranchNode::base_match(&p));

        if base_parent.is_none() {
            return;
        }

        let base_parent = base_parent.unwrap();
        let child_count = base_parent.borrow().child_count();

        for i in 0..child_count {
            let bn = base_parent.borrow().child(i).cloned();
            if bn.is_none() {
                continue;
            }
            let bn = bn.unwrap();

            let op1 = self.get_operation(&bn, mlist_a);
            let op2 = self.get_operation(&bn, mlist_b);

            // Handle based on which operation is smaller
            // The table is symmetric in terms of which list we apply actions to
            if op1 <= op2 {
                self.handle_operation_pair(op1, op2, &bn, mlist_a, mlist_b);
            } else {
                self.handle_operation_pair(op2, op1, &bn, mlist_b, mlist_a);
            }
        }
    }

    /// Handles a pair of operations on a base node.
    fn handle_operation_pair(
        &mut self,
        op1: Operation,
        op2: Operation,
        bn: &NodeRef,
        ml1: &mut MergeList,
        _ml2: &mut MergeList,
    ) {
        use Operation::*;

        match (op1, op2) {
            (Nop, Nop) | (Nop, MoveI) | (MoveI, MoveI) | (Delete, Delete) => {
                // OK cases - no action needed
            }
            (Nop, MoveF) | (Nop, Delete) => {
                // Delete the node from ml1
                if let Some(ix) = ml1.match_in_list(bn) {
                    if op2 == Delete {
                        // Check for modifications in deleted subtree
                        if let Some(entry) = ml1.entry(ix) {
                            if let Some(node) = entry.node() {
                                if self.is_deletia_modified(&node, ml1) {
                                    self.conflict_log.add_list_warning(
                                        ConflictType::Delete,
                                        "Modifications in deleted subtree",
                                        Some(bn.clone()),
                                        entry.node(),
                                        None,
                                    );
                                }
                            }
                        }
                        self.edit_log.delete(Some(bn.clone()));

                        // Check if the deleted entry was locked (involved in
                        // a move or copy) — thesis section 7.1.2
                        if let Some(entry) = ml1.entry(ix) {
                            if entry.locked {
                                self.conflict_log.add_list_conflict(
                                    ConflictType::Delete,
                                    "Moved or copied node deleted",
                                    Some(bn.clone()),
                                    entry.node(),
                                    None,
                                );
                            }
                        }
                    }

                    // Move hangons to predecessor
                    ml1.move_hangons_to_predecessor(ix);
                    ml1.remove_entry_at(ix);
                }
            }
            (MoveI, MoveF) => {
                // Conflict: node moved to different locations
                if let Some(ix) = ml1.match_in_list(bn) {
                    let node = ml1.entry(ix).and_then(|e| e.node());
                    let partner = node
                        .as_ref()
                        .and_then(|n| n.borrow().first_partner(MatchType::FULL));
                    self.conflict_log.add_list_conflict(
                        ConflictType::Move,
                        "Node moved to different locations",
                        Some(bn.clone()),
                        node,
                        partner,
                    );
                    ml1.remove_entry_at(ix);
                }
            }
            (MoveI, Delete) => {
                // Conflict: node moved and deleted
                if let Some(ix) = ml1.match_in_list(bn) {
                    let node = ml1.entry(ix).and_then(|e| e.node());
                    self.conflict_log.add_list_conflict(
                        ConflictType::Move,
                        "Node moved and deleted",
                        Some(bn.clone()),
                        node,
                        None,
                    );
                    self.edit_log.delete(Some(bn.clone()));
                    ml1.remove_entry_at(ix);
                }
            }
            (MoveF, MoveF) => {
                // Check for movef-movef conflict
                if self.is_movef_movef_conflict(bn) {
                    self.conflict_log.add_list_conflict(
                        ConflictType::Move,
                        "Node moved to different locations",
                        Some(bn.clone()),
                        BaseNode::left(bn).borrow().full_match(),
                        BaseNode::right(bn).borrow().full_match(),
                    );
                }
            }
            (MoveF, Delete) => {
                // Conflict: moved and deleted - keep the move
                self.conflict_log.add_list_conflict(
                    ConflictType::Move,
                    "Node moved and deleted",
                    Some(bn.clone()),
                    BaseNode::left(bn).borrow().full_match(),
                    BaseNode::right(bn).borrow().full_match(),
                );
            }
            _ => {}
        }
    }

    /// Gets the operation on a base node in a merge list.
    fn get_operation(&self, bn: &NodeRef, ml: &MergeList) -> Operation {
        if let Some(pos) = ml.match_in_list(bn) {
            if ml.entry(pos).is_some_and(|e| e.moved) {
                Operation::MoveI
            } else {
                Operation::Nop
            }
        } else {
            // Check if moved far or deleted
            let is_left = ml
                .entry_parent()
                .map(|p| BranchNode::is_left_tree(&p))
                .unwrap_or(true);

            let copies = if is_left {
                BaseNode::left(bn)
            } else {
                BaseNode::right(bn)
            };

            if copies.borrow().match_count() == 0 {
                Operation::Delete
            } else {
                Operation::MoveF
            }
        }
    }

    /// Checks if a deleted subtree has modifications.
    ///
    /// Recursively checks children with per-level merge lists, matching the
    /// thesis algorithm (Section 7.1.1, Listing 5).
    fn is_deletia_modified(&mut self, n: &NodeRef, ml: &MergeList) -> bool {
        let base_match = BranchNode::base_match(n);
        if base_match.is_none() {
            return true; // Inserted node
        }

        let base_match = base_match.unwrap();
        if self.get_operation(&base_match, ml) != Operation::Nop {
            return true; // Node was moved
        }

        if BranchNode::base_match_type(n) != MatchType::FULL {
            return true; // Structural or content modification
        }

        // Check if deleted in other branch
        if let Some(partners) = BranchNode::partners(n) {
            if partners.borrow().match_count() == 0 {
                if !self.matches(n, &base_match) {
                    return true; // Updated
                }
                // Recursively check children with a child-level merge list
                let child_ml = self.make_merge_list(n);
                for i in 0..n.borrow().child_count() {
                    if let Some(child) = n.borrow().child(i).cloned() {
                        if self.is_deletia_modified(&child, &child_ml) {
                            return true;
                        }
                    }
                }
            }
        }

        false
    }

    /// Checks for movef-movef conflict.
    ///
    /// A MoveF-MoveF conflict occurs when both branches move the same base node
    /// to different parent locations. Returns true if the parents differ (conflict).
    fn is_movef_movef_conflict(&self, bn: &NodeRef) -> bool {
        // Get left/right branch copies of base node
        let left_node = BaseNode::left(bn).borrow().full_match();
        let right_node = BaseNode::right(bn).borrow().full_match();

        let (left_node, right_node) = match (left_node, right_node) {
            (Some(l), Some(r)) => (l, r),
            _ => return false,
        };

        // Get parents
        let left_parent = BranchNode::parent(&left_node);
        let right_parent = BranchNode::parent(&right_node);

        match (left_parent, right_parent) {
            (Some(lp), Some(rp)) => {
                let lp_base = BranchNode::base_match(&lp);
                let rp_base = BranchNode::base_match(&rp);
                match (lp_base, rp_base) {
                    (Some(lb), Some(rb)) => lb.borrow().id() != rb.borrow().id(),
                    _ => true, // Inserted parent = conflict
                }
            }
            (None, None) => false, // Both at root
            _ => true,             // One at root, one not
        }
    }

    /// Merges the content of nodes in a merge pair.
    fn merge_node_content(&mut self, pair: &MergePair) -> Option<XmlContent> {
        let n1 = pair.first.as_ref();
        let n2 = pair.second.as_ref();

        match (n1, n2) {
            (None, None) => None,
            (Some(n), None) | (None, Some(n)) => n.borrow().content().cloned(),
            (Some(n1), Some(n2)) => {
                let n1_content = n1.borrow().is_match(MatchType::CONTENT);
                let n2_content = n2.borrow().is_match(MatchType::CONTENT);

                if n1_content {
                    if !n2_content {
                        self.edit_log.update(Some(n2.clone()));
                        n2.borrow().content().cloned()
                    } else {
                        self.content_merge(n1, n2)
                    }
                } else if n2_content {
                    self.edit_log.update(Some(n1.clone()));
                    n1.borrow().content().cloned()
                } else {
                    // Neither matches content - forced merge
                    self.content_merge(n1, n2)
                }
            }
        }
    }

    /// Merges content of two nodes.
    fn content_merge(&mut self, a: &NodeRef, b: &NodeRef) -> Option<XmlContent> {
        let base_a = BranchNode::base_match(a);
        let base_b = BranchNode::base_match(b);

        let a_updated = base_a.as_ref().is_none_or(|ba| !self.matches(a, ba));
        let b_updated = base_b.as_ref().is_none_or(|bb| !self.matches(b, bb));

        if a_updated && b_updated {
            // Both updated - check if same update
            if self.matches(a, b) {
                self.conflict_log.add_node_warning(
                    ConflictType::Update,
                    "Node updated in both branches, but updates are equal",
                    base_a.clone(),
                    Some(a.clone()),
                    Some(b.clone()),
                );
                self.edit_log.update(Some(a.clone()));
                return a.borrow().content().cloned();
            }

            // Try element merge
            if let Some(merged) = self.merge_elements(base_a.as_ref(), a, b) {
                return Some(merged);
            }

            // Conflict - use first branch
            self.conflict_log.add_node_conflict(
                ConflictType::Update,
                "Node updated in both branches, using branch 1",
                base_a,
                Some(a.clone()),
                Some(b.clone()),
            );
            self.edit_log.update(Some(a.clone()));
            a.borrow().content().cloned()
        } else if b_updated {
            // Check if a has namespace declaration changes that need merging
            if self.has_namespace_changes(a, base_a.as_ref()) {
                if let Some(merged) = self.merge_elements(base_a.as_ref(), a, b) {
                    return Some(merged);
                }
                // Namespace conflict
                self.conflict_log.add_node_conflict(
                    ConflictType::Update,
                    "Namespace declaration conflict between branches, using branch 2",
                    base_a,
                    Some(a.clone()),
                    Some(b.clone()),
                );
            }
            self.edit_log.update(Some(b.clone()));
            b.borrow().content().cloned()
        } else if a_updated {
            // Check if b has namespace declaration changes that need merging
            if self.has_namespace_changes(b, base_b.as_ref()) {
                if let Some(merged) = self.merge_elements(base_a.as_ref(), a, b) {
                    return Some(merged);
                }
                // Namespace conflict
                self.conflict_log.add_node_conflict(
                    ConflictType::Update,
                    "Namespace declaration conflict between branches, using branch 1",
                    base_a,
                    Some(a.clone()),
                    Some(b.clone()),
                );
            }
            self.edit_log.update(Some(a.clone()));
            a.borrow().content().cloned()
        } else {
            // Neither content updated, but check for namespace-only changes
            if self.has_namespace_changes(a, base_a.as_ref())
                || self.has_namespace_changes(b, base_b.as_ref())
            {
                if let Some(merged) = self.merge_elements(base_a.as_ref(), a, b) {
                    return Some(merged);
                }
                // Namespace conflict
                self.conflict_log.add_node_conflict(
                    ConflictType::Update,
                    "Namespace declaration conflict between branches, using branch 1",
                    base_a.clone(),
                    Some(a.clone()),
                    Some(b.clone()),
                );
            }
            a.borrow().content().cloned()
        }
    }

    /// Attempts to merge two element nodes.
    fn merge_elements(
        &self,
        base: Option<&NodeRef>,
        a: &NodeRef,
        b: &NodeRef,
    ) -> Option<XmlContent> {
        let base_content = base.and_then(|n| n.borrow().content().cloned());
        let a_content = a.borrow().content().cloned();
        let b_content = b.borrow().content().cloned();

        match (&base_content, &a_content, &b_content) {
            (
                Some(XmlContent::Element(base_elem)),
                Some(XmlContent::Element(a_elem)),
                Some(XmlContent::Element(b_elem)),
            ) => {
                // Determine tag name
                let tag_name = if base_elem.names_match(b_elem) {
                    a_elem.qname().to_string()
                } else if base_elem.names_match(a_elem) {
                    b_elem.qname().to_string()
                } else {
                    return None; // Both changed tag name
                };

                // Merge attributes
                self.merge_attributes(
                    base_elem.attributes(),
                    a_elem.attributes(),
                    b_elem.attributes(),
                )
                .and_then(|merged_attrs| {
                    let merged_ns = self.merge_namespace_decls(
                        base_elem.namespace_decls(),
                        a_elem.namespace_decls(),
                        b_elem.namespace_decls(),
                    )?;
                    // Use the winning element's expanded name
                    let expanded = if base_elem.names_match(b_elem) {
                        a_elem.expanded_name().cloned()
                    } else {
                        b_elem.expanded_name().cloned()
                    };
                    Some(XmlContent::Element(XmlElement::new_with_namespace(
                        tag_name,
                        expanded,
                        merged_ns,
                        merged_attrs,
                    )))
                })
            }
            _ => None,
        }
    }

    /// Merges attributes from base, a, and b.
    fn merge_attributes(
        &self,
        base: &std::collections::HashMap<String, String>,
        a: &std::collections::HashMap<String, String>,
        b: &std::collections::HashMap<String, String>,
    ) -> Option<std::collections::HashMap<String, String>> {
        let mut merged = std::collections::HashMap::new();
        let mut deletia = std::collections::HashSet::new();

        // Check for deleted attributes with conflicts
        for (key, base_val) in base {
            let in_a = a.get(key);
            let in_b = b.get(key);

            match (in_a, in_b) {
                (None, Some(b_val)) if base_val != b_val => return None, // Deleted and changed
                (Some(a_val), None) if base_val != a_val => return None, // Deleted and changed
                (None, _) | (_, None) => {
                    deletia.insert(key.clone());
                }
                _ => {}
            }
        }

        // Build merged attributes from a
        for (key, a_val) in a {
            if deletia.contains(key) {
                continue;
            }

            if let Some(b_val) = b.get(key) {
                let base_val = base.get(key);
                if base_val == Some(b_val) {
                    // A possibly updated
                    merged.insert(key.clone(), a_val.clone());
                } else if base_val == Some(a_val) {
                    // B possibly updated
                    merged.insert(key.clone(), b_val.clone());
                } else if a_val != b_val {
                    // Both changed differently
                    return None;
                } else {
                    merged.insert(key.clone(), a_val.clone());
                }
            } else {
                // Insert from a
                merged.insert(key.clone(), a_val.clone());
            }
        }

        // Add inserts from b
        for (key, b_val) in b {
            if !deletia.contains(key) && !a.contains_key(key) {
                merged.insert(key.clone(), b_val.clone());
            }
        }

        Some(merged)
    }

    /// Merges namespace declarations from base, a, and b using 3-way merge.
    /// Returns None on conflict (deleted in one branch, changed in the other).
    fn merge_namespace_decls(
        &self,
        base: &std::collections::HashMap<String, String>,
        a: &std::collections::HashMap<String, String>,
        b: &std::collections::HashMap<String, String>,
    ) -> Option<std::collections::HashMap<String, String>> {
        let mut merged = std::collections::HashMap::new();
        let mut deletia = std::collections::HashSet::new();

        // Detect deletions and deletion-vs-change conflicts
        for (prefix, base_uri) in base {
            let in_a = a.get(prefix);
            let in_b = b.get(prefix);

            match (in_a, in_b) {
                (None, Some(b_uri)) if base_uri != b_uri => return None,
                (Some(a_uri), None) if base_uri != a_uri => return None,
                (None, _) | (_, None) => {
                    deletia.insert(prefix.clone());
                }
                _ => {}
            }
        }

        // Build merged from a
        for (prefix, a_uri) in a {
            if deletia.contains(prefix) {
                continue;
            }
            if let Some(b_uri) = b.get(prefix) {
                let base_uri = base.get(prefix);
                if base_uri == Some(b_uri) {
                    merged.insert(prefix.clone(), a_uri.clone());
                } else if base_uri == Some(a_uri) {
                    merged.insert(prefix.clone(), b_uri.clone());
                } else if a_uri != b_uri {
                    return None;
                } else {
                    merged.insert(prefix.clone(), a_uri.clone());
                }
            } else {
                merged.insert(prefix.clone(), a_uri.clone());
            }
        }

        // Add new declarations from b
        for (prefix, b_uri) in b {
            if !deletia.contains(prefix) && !a.contains_key(prefix) {
                merged.insert(prefix.clone(), b_uri.clone());
            }
        }

        Some(merged)
    }

    /// Gets partners for recursion.
    fn get_recursion_partners(&self, pair: &MergePair) -> RecursionPartners {
        let n1 = pair.first.as_ref();
        let n2 = pair.second.as_ref();

        match (n1, n2) {
            (None, _) | (_, None) => RecursionPartners {
                first: pair.first.clone(),
                second: pair.second.clone(),
            },
            (Some(n1), Some(n2)) => {
                let n1_children = n1.borrow().is_match(MatchType::CHILDREN);
                let n2_children = n2.borrow().is_match(MatchType::CHILDREN);

                if n1_children && n2_children {
                    RecursionPartners {
                        first: Some(n1.clone()),
                        second: Some(n2.clone()),
                    }
                } else if n1_children && n2.borrow().is_match(MatchType::CONTENT) {
                    RecursionPartners {
                        first: None,
                        second: Some(n2.clone()),
                    }
                } else if n1.borrow().is_match(MatchType::CONTENT) && n2_children {
                    RecursionPartners {
                        first: Some(n1.clone()),
                        second: None,
                    }
                } else {
                    RecursionPartners {
                        first: Some(n1.clone()),
                        second: Some(n2.clone()),
                    }
                }
            }
        }
    }

    /// Checks if a node has namespace declaration changes relative to its base.
    fn has_namespace_changes(&self, node: &NodeRef, base: Option<&NodeRef>) -> bool {
        let Some(base) = base else { return false };
        let node_borrowed = node.borrow();
        let base_borrowed = base.borrow();
        match (node_borrowed.content(), base_borrowed.content()) {
            (Some(XmlContent::Element(ne)), Some(XmlContent::Element(be))) => {
                !ne.namespace_decls_equal(be)
            }
            _ => false,
        }
    }

    /// Checks if two nodes have equal content.
    fn matches(&self, a: &NodeRef, b: &NodeRef) -> bool {
        let a_borrowed = a.borrow();
        let b_borrowed = b.borrow();
        let a_content = a_borrowed.content();
        let b_content = b_borrowed.content();

        match (a_content, b_content) {
            (Some(ac), Some(bc)) => ac.content_equals(bc),
            _ => false,
        }
    }

    /// Logs structural operations for a hangon node.
    fn log_hangon_struct_ops(&mut self, n: &NodeRef) {
        if !BranchNode::has_base_match(n) {
            self.edit_log.insert(Some(n.clone()));
        } else {
            let base = BranchNode::base_match(n).unwrap();
            let is_left = BranchNode::is_left_tree(n);

            let copies = if is_left {
                BaseNode::left(&base)
            } else {
                BaseNode::right(&base)
            };

            if copies.borrow().match_count() > 1 {
                self.edit_log.copy(Some(n.clone()));
            } else {
                self.edit_log.r#move(Some(n.clone()));
            }
        }
    }

    /// Logs structural operations for merge entries.
    fn log_entry_struct_ops(&mut self, e1: &MergeEntry, e2: &MergeEntry) {
        if e1.moved {
            if let Some(n) = e1.node() {
                self.edit_log.r#move(Some(n));
            }
        } else if e2.moved {
            if let Some(n) = e2.node() {
                self.edit_log.r#move(Some(n));
            }
        }
    }

    /// Checks if hangons from two entries are equal.
    /// Returns true only if hangons match exactly (same count and content).
    /// When false, the caller should add eb's hangons to the merge list.
    fn check_hangon_combine(&mut self, ea: &MergeEntry, eb: &MergeEntry) -> bool {
        // If ea has no hangons, return false so eb's hangons are added
        if ea.hangons().is_empty() {
            return false;
        }

        if ea.hangons().len() != eb.hangons().len() {
            if !ea.hangons().is_empty() && !eb.hangons().is_empty() {
                self.conflict_log.add_list_warning(
                    ConflictType::Insert,
                    "Insertions/copies in both branches",
                    ea.node().and_then(|n| BranchNode::base_match(&n)),
                    ea.node(),
                    eb.node(),
                );
            }
            return false;
        }

        // Check if hangons match exactly
        let mut equal = true;
        for (ha, hb) in ea.hangons().iter().zip(eb.hangons().iter()) {
            if !self.tree_matches(ha, hb) {
                equal = false;
                break;
            }
        }

        if equal {
            self.conflict_log.add_list_warning(
                ConflictType::Insert,
                "Equal insertions/copies in both branches",
                ea.node().and_then(|n| BranchNode::base_match(&n)),
                ea.node(),
                eb.node(),
            );
        } else if !ea.hangons().is_empty() {
            self.conflict_log.add_list_warning(
                ConflictType::Insert,
                "Insertions/copies in both branches, sequencing",
                ea.node().and_then(|n| BranchNode::base_match(&n)),
                ea.node(),
                eb.node(),
            );
        }

        equal
    }

    /// Checks if entire subtrees match exactly.
    fn tree_matches(&self, a: &NodeRef, b: &NodeRef) -> bool {
        if !self.matches(a, b) {
            return false;
        }

        let a_count = a.borrow().child_count();
        let b_count = b.borrow().child_count();

        if a_count != b_count {
            return false;
        }

        for i in 0..a_count {
            let a_child = a.borrow().child(i).cloned();
            let b_child = b.borrow().child(i).cloned();

            match (a_child, b_child) {
                (Some(ac), Some(bc)) => {
                    if !self.tree_matches(&ac, &bc) {
                        return false;
                    }
                }
                _ => return false,
            }
        }

        true
    }
}

/// Partners for recursion.
struct RecursionPartners {
    first: Option<NodeRef>,
    second: Option<NodeRef>,
}

impl crate::node::NodeInner {
    /// Returns the first partner that matches the given type.
    pub fn first_partner(&self, type_flags: MatchType) -> Option<NodeRef> {
        if let crate::node::NodeKind::Branch {
            match_type,
            partners,
            ..
        } = self.kind()
        {
            if !match_type.intersects(type_flags) {
                return None;
            }

            if let Some(partners) = partners {
                let borrowed = partners.borrow();
                for candidate in borrowed.matches() {
                    if BranchNode::base_match_type(candidate).intersects(type_flags) {
                        return Some(candidate.clone());
                    }
                }
            }
        }
        None
    }

    /// Returns true if the match type includes the given flags.
    pub fn is_match(&self, type_flags: MatchType) -> bool {
        if let crate::node::NodeKind::Branch { match_type, .. } = self.kind() {
            match_type.intersects(type_flags)
        } else {
            false
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::matching::TriMatching;
    use crate::xml::{BaseNodeFactory, BranchNodeFactory, XmlParser};
    use std::collections::HashMap;

    /// Helper: run a 3-way merge from XML strings, return (output_xml, conflict_count).
    fn merge_xml(base: &str, a: &str, b: &str) -> (String, usize) {
        let base_tree = XmlParser::new(BaseNodeFactory)
            .parse_str(base)
            .expect("parse base");
        let a_tree = XmlParser::new(BranchNodeFactory)
            .parse_str(a)
            .expect("parse a");
        let b_tree = XmlParser::new(BranchNodeFactory)
            .parse_str(b)
            .expect("parse b");
        let matching = TriMatching::new(a_tree, base_tree, b_tree);
        let mut merge = Merge::new(matching);
        let mut output = Vec::new();
        merge.merge(&mut output).expect("merge");
        let conflicts = merge.conflict_log.conflicts().len();
        (String::from_utf8(output).expect("utf8"), conflicts)
    }

    #[test]
    fn test_merge_namespace_decls_deletion() {
        // Branch B removes xmlns:foo, A unchanged
        let base = r#"<?xml version="1.0"?><root xmlns:foo="http://foo.com" xmlns:bar="http://bar.com"><child/></root>"#;
        let a = base;
        let b = r#"<?xml version="1.0"?><root xmlns:bar="http://bar.com"><child/></root>"#;
        let (output, conflicts) = merge_xml(base, a, b);
        assert!(!output.contains("xmlns:foo"), "xmlns:foo should be removed");
        assert!(output.contains("xmlns:bar"), "xmlns:bar should remain");
        assert_eq!(conflicts, 0);
    }

    #[test]
    fn test_merge_namespace_decls_addition() {
        // A adds xmlns:b, B adds xmlns:c
        let base = r#"<?xml version="1.0"?><root xmlns:a="http://a.com"><child/></root>"#;
        let a = r#"<?xml version="1.0"?><root xmlns:a="http://a.com" xmlns:b="http://b.com"><child/></root>"#;
        let b = r#"<?xml version="1.0"?><root xmlns:a="http://a.com" xmlns:c="http://c.com"><child/></root>"#;
        let (output, conflicts) = merge_xml(base, a, b);
        assert!(output.contains("xmlns:b"), "xmlns:b should be present");
        assert!(output.contains("xmlns:c"), "xmlns:c should be present");
        assert_eq!(conflicts, 0);
    }

    #[test]
    fn test_merge_namespace_decls_delete_vs_change_conflict() {
        // A deletes xmlns:foo, B changes its URI → conflict
        let base = r#"<?xml version="1.0"?><root xmlns:foo="http://foo.com" xmlns:bar="http://bar.com"><child/></root>"#;
        let a = r#"<?xml version="1.0"?><root xmlns:bar="http://bar.com"><child/></root>"#;
        let b = r#"<?xml version="1.0"?><root xmlns:foo="http://foo-v2.com" xmlns:bar="http://bar.com"><child/></root>"#;
        let (_output, conflicts) = merge_xml(base, a, b);
        assert_eq!(conflicts, 1, "delete-vs-change should produce a conflict");
    }

    #[test]
    fn test_merge_namespace_decls_both_change_same_prefix_conflict() {
        // A and B both change xmlns:foo to different URIs → conflict
        let base = r#"<?xml version="1.0"?><root xmlns:foo="http://foo.com"><child/></root>"#;
        let a = r#"<?xml version="1.0"?><root xmlns:foo="http://foo-a.com"><child/></root>"#;
        let b = r#"<?xml version="1.0"?><root xmlns:foo="http://foo-b.com"><child/></root>"#;
        let (_output, conflicts) = merge_xml(base, a, b);
        assert_eq!(
            conflicts, 1,
            "both changing same prefix differently should conflict"
        );
    }

    #[test]
    fn test_merge_namespace_decls_both_change_same_value() {
        // A and B both change xmlns:foo to the SAME URI → no conflict
        let base = r#"<?xml version="1.0"?><root xmlns:foo="http://foo.com"><child/></root>"#;
        let a = r#"<?xml version="1.0"?><root xmlns:foo="http://foo-v2.com"><child/></root>"#;
        let b = r#"<?xml version="1.0"?><root xmlns:foo="http://foo-v2.com"><child/></root>"#;
        let (output, conflicts) = merge_xml(base, a, b);
        assert!(
            output.contains("http://foo-v2.com"),
            "merged URI should be the new value"
        );
        assert_eq!(conflicts, 0);
    }

    #[test]
    fn test_merge_namespace_decls_unit() {
        // Direct unit test of merge_namespace_decls
        let matching = {
            let base = XmlParser::new(BaseNodeFactory)
                .parse_str("<root/>")
                .unwrap();
            let a = XmlParser::new(BranchNodeFactory)
                .parse_str("<root/>")
                .unwrap();
            let b = XmlParser::new(BranchNodeFactory)
                .parse_str("<root/>")
                .unwrap();
            TriMatching::new(a, base, b)
        };
        let merge = Merge::new(matching);

        let mut base = HashMap::new();
        base.insert("foo".into(), "http://foo.com".into());
        base.insert("bar".into(), "http://bar.com".into());

        // Deletion: a removes foo
        let mut a = HashMap::new();
        a.insert("bar".into(), "http://bar.com".into());
        let b = base.clone();

        let result = merge.merge_namespace_decls(&base, &a, &b).unwrap();
        assert!(!result.contains_key("foo"));
        assert!(result.contains_key("bar"));

        // Conflict: a removes foo, b changes foo
        let mut b_changed = HashMap::new();
        b_changed.insert("foo".into(), "http://foo-v2.com".into());
        b_changed.insert("bar".into(), "http://bar.com".into());

        let result = merge.merge_namespace_decls(&base, &a, &b_changed);
        assert!(result.is_none(), "delete-vs-change should return None");
    }
}