natural-xml-diff 0.2.0

use xot::{Node, Value, Xot};

use crate::comparison::Comparison;
use crate::edits::{AttributeChange, Edit, InsertContent, TextChange};

pub(crate) const DIFF_NS_URI: &str = "http://paligo.net/nxd";

impl Comparison {
    /// Returns a diff document for this comparison.
    ///
    /// This diff document contains information on how to change document A
    /// into document B. If this diff document is applied using `apply_diff`,
    /// the result should be semantically equivalent to document B.
    pub fn diff(&mut self, xot: &mut Xot) -> Node {
        let edits = self.edits(xot);
        let diff_doc = xot.clone(self.doc_a);
        apply_edits(xot, diff_doc, &edits);
        diff_doc
    }
}

pub(crate) fn apply_edits(xot: &mut Xot, root: Node, edits: &[Edit]) {
    let id_to_node = xot.descendants(root).collect::<Vec<_>>();

    let diff_ns = xot.add_namespace(DIFF_NS_URI);
    let diff_prefix = xot.add_prefix("diff");
    let delete_name = xot.add_name_ns("delete", diff_ns);
    let insert_name = xot.add_name_ns("insert", diff_ns);
    let text_delete_name = xot.add_name_ns("text-delete", diff_ns);
    let text_insert_name = xot.add_name_ns("text-insert", diff_ns);
    let text_update_name = xot.add_name_ns("text-update", diff_ns);
    let attr_delete_name = xot.add_name_ns("attr-delete", diff_ns);
    let attr_insert_name = xot.add_name_ns("attr-insert", diff_ns);
    let attr_update_name = xot.add_name_ns("attr-update", diff_ns);
    let attributes_name = xot.add_name_ns("attributes", diff_ns);
    let diff_root_name = xot.add_name_ns("root", diff_ns);
    let pi_delete_name = xot.add_name_ns("pi-delete", diff_ns);
    let pi_insert_name = xot.add_name_ns("pi-insert", diff_ns);
    let comment_delete_name = xot.add_name_ns("comment-delete", diff_ns);
    let comment_insert_name = xot.add_name_ns("comment-insert", diff_ns);

    let mut update_nodes = Vec::new();

    let mut attribute_changes = Vec::new();

    for edit in edits {
        match edit {
            Edit::Delete(id) => {
                let node = id_to_node[*id];
                match xot.value_mut(node) {
                    Value::Element(element) => {
                        element.set_attribute(delete_name, "");
                    }
                    Value::Text(_text) => {
                        xot.element_wrap(node, text_delete_name).unwrap();
                    }
                    Value::ProcessingInstruction(_pi) => {
                        xot.element_wrap(node, pi_delete_name).unwrap();
                    }
                    Value::Comment(_comment) => {
                        xot.element_wrap(node, comment_delete_name).unwrap();
                    }
                    Value::Root => {
                        panic!("unexpected root node value: {:?}", xot.value(node))
                    }
                }
            }
            Edit::Insert(position, content) => {
                let insert_node = match content {
                    InsertContent::XmlNode(insert_node) => {
                        let insert_node = xot.clone(*insert_node);
                        match xot.value_mut(insert_node) {
                            Value::Element(element) => {
                                element.set_attribute(insert_name, "");
                                insert_node
                            }
                            Value::ProcessingInstruction(_) => {
                                xot.element_wrap(insert_node, pi_insert_name).unwrap()
                            }
                            Value::Comment(_) => {
                                xot.element_wrap(insert_node, comment_insert_name).unwrap()
                            }
                            _ => {
                                panic!("unexpected insert node value: {:?}", xot.value(insert_node))
                            }
                        }
                    }
                    InsertContent::Text(text) => {
                        let text_insert_node = xot.new_element(text_insert_name);
                        xot.append_text(text_insert_node, text).unwrap();
                        text_insert_node
                    }
                };

                let parent = id_to_node[position.parent_node_id];
                if xot.is_root(parent) && xot.is_element(insert_node) {
                    // if we are about to insert into the root and what we insert is a element
                    // then we must be replacing the document element
                    let doc_el = xot.document_element(root).unwrap();
                    // wrap the document element into a new diff:root first
                    let root_wrapper = xot.element_wrap(doc_el, diff_root_name).unwrap();
                    // now insert the new element next to the deleted one
                    xot.append(root_wrapper, insert_node).unwrap();
                    continue;
                }
                let child_position = position.child_position as usize;

                if xot.first_child(parent).is_some() {
                    let child_node = get_child_by_index(xot, parent, child_position);
                    if let Some(child_node) = child_node {
                        xot.insert_before(child_node, insert_node).unwrap();
                    } else {
                        // add at the end
                        xot.append(parent, insert_node).unwrap();
                    }
                } else {
                    xot.append(parent, insert_node).unwrap();
                }
            }
            Edit::TextUpdate(id, updates) => {
                let node = id_to_node[*id];
                if !xot.is_text(node) {
                    panic!("Text update can only be applied to text nodes");
                }
                // we create a node for the update in order not to disturb the
                // position of nodes in the tree. In the end we can element unwrap them
                // XXX is it really needed not to disturb the position? after all we look up
                // the id
                let update_text_node = xot.new_element(text_update_name);
                update_nodes.push(update_text_node);
                for text_change in updates {
                    let node = match text_change {
                        TextChange::Equal(text) => xot.new_text(text),
                        TextChange::Delete(text) => {
                            let text_delete_node = xot.new_element(text_delete_name);
                            xot.append_text(text_delete_node, text).unwrap();
                            text_delete_node
                        }
                        TextChange::Insert(text) => {
                            let text_insert_node = xot.new_element(text_insert_name);
                            xot.append_text(text_insert_node, text).unwrap();
                            text_insert_node
                        }
                    };
                    xot.append(update_text_node, node).unwrap();
                }

                xot.replace(node, update_text_node).unwrap();
            }
            Edit::AttributeUpdate(id, updates) => {
                let node = id_to_node[*id];
                if !xot.is_element(node) {
                    panic!("Attribute update can only be applied to element nodes");
                }
                let attributes_node = xot.new_element(attributes_name);
                for update in updates {
                    let node = match update {
                        AttributeChange::Update(name, value) => {
                            let update = xot.new_element(*name);
                            xot.element_mut(update)
                                .unwrap()
                                .set_attribute(attr_update_name, "");
                            xot.append_text(update, value).unwrap();
                            update
                        }
                        AttributeChange::Insert(name, value) => {
                            let insert = xot.new_element(*name);
                            xot.element_mut(insert)
                                .unwrap()
                                .set_attribute(attr_insert_name, "");
                            xot.append_text(insert, value).unwrap();
                            insert
                        }
                        AttributeChange::Delete(name) => {
                            let delete = xot.new_element(*name);
                            xot.element_mut(delete)
                                .unwrap()
                                .set_attribute(attr_delete_name, "");
                            delete
                        }
                    };
                    xot.append(attributes_node, node).unwrap();
                }
                attribute_changes.push((node, attributes_node));
            }
        }
    }

    // insert attribute nodes; we do this at the end so we don't get
    // disturbed by other edits which can insert nodes
    for (node, attributes_node) in attribute_changes {
        xot.prepend(node, attributes_node).unwrap();
    }

    // remove temporary update nodes
    for update_node in update_nodes {
        xot.element_unwrap(update_node).unwrap();
    }

    // add diff namespace to document element
    // we do this at the end as a new root could be inserted if the root
    // is replaced
    let doc_el = xot.document_element(root).unwrap();
    let element = xot.element_mut(doc_el).unwrap();
    element.set_prefix(diff_prefix, diff_ns);

    // inserting the parsed XML will have created new nodes and
    // their namespace definition is possibly duplicate
    xot.deduplicate_namespaces(root);
}

fn get_child_by_index(xot: &Xot, node: Node, index: usize) -> Option<Node> {
    let mut child = xot.first_child(node);
    let mut i = 0;
    loop {
        // get next non-deleted sibling
        while is_deleted(xot, child) {
            child = child.and_then(|n| xot.next_sibling(n));
        }
        if i == index {
            return child;
        }
        i += 1;
        child = child.and_then(|n| xot.next_sibling(n));
    }
}

fn is_deleted(xot: &Xot, node: Option<Node>) -> bool {
    if let Some(node) = node {
        // deleted element node
        if let Some(element) = xot.element(node) {
            // XXX would be nice to be able to share these
            let diff_ns = xot.namespace(DIFF_NS_URI).unwrap();
            let delete_name = xot.name_ns("delete", diff_ns).unwrap();
            let delete_text_name = xot.name_ns("text-delete", diff_ns).unwrap();
            if element.get_attribute(delete_name).is_some() || element.name() == delete_text_name {
                return true;
            }
        }
    }
    false
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::edits::InsertPosition;

    #[test]
    fn test_simple_delete() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><b><c/></b></a>").unwrap();
        let edits = [Edit::Delete(3)];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><b><c diff:delete=""/></b></a>"#
        );
    }

    #[test]
    fn test_simple_insert_element() {
        let mut xot = Xot::new();
        let root = xot.parse("<a></a>").unwrap();
        let to_insert = xot.parse("<b/>").unwrap();
        let to_insert = xot.document_element(to_insert).unwrap();
        let edits = [Edit::Insert(
            InsertPosition {
                parent_node_id: 1,
                child_position: 0,
                descendant_count: 0,
            },
            InsertContent::XmlNode(to_insert),
        )];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><b diff:insert=""/></a>"#
        );
    }

    #[test]
    fn test_simple_insert_text() {
        let mut xot = Xot::new();
        let root = xot.parse("<a></a>").unwrap();
        let edits = [Edit::Insert(
            InsertPosition {
                parent_node_id: 1,
                child_position: 0,
                descendant_count: 0,
            },
            InsertContent::Text("Text!".to_owned()),
        )];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><diff:text-insert>Text!</diff:text-insert></a>"#
        );
    }

    #[test]
    fn test_text_delete() {
        let mut xot = Xot::new();
        let root = xot.parse("<a>text</a>").unwrap();
        let edits = [Edit::Delete(2)];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><diff:text-delete>text</diff:text-delete></a>"#
        );
    }

    #[test]
    fn test_insert_beginning() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><two/><three/></a>").unwrap();
        let to_insert = xot.parse("<one/>").unwrap();
        let to_insert = xot.document_element(to_insert).unwrap();
        let edits = [Edit::Insert(
            InsertPosition {
                parent_node_id: 1,
                child_position: 0,
                descendant_count: 0,
            },
            InsertContent::XmlNode(to_insert),
        )];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><one diff:insert=""/><two/><three/></a>"#
        );
    }

    #[test]
    fn test_insert_middle() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><one/><three/></a>").unwrap();
        let to_insert = xot.parse("<two/>").unwrap();
        let to_insert = xot.document_element(to_insert).unwrap();
        let edits = [Edit::Insert(
            InsertPosition {
                parent_node_id: 1,
                child_position: 1,
                descendant_count: 0,
            },
            InsertContent::XmlNode(to_insert),
        )];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><one/><two diff:insert=""/><three/></a>"#
        );
    }

    #[test]
    fn test_delete_insert_middle_twice() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><one/><x/><three/></a>").unwrap();
        let to_insert_two = xot.parse("<two/>").unwrap();
        let to_insert_two = xot.document_element(to_insert_two).unwrap();
        let to_insert_extra = xot.parse("<extra/>").unwrap();
        let to_insert_extra = xot.document_element(to_insert_extra).unwrap();
        let edits = [
            Edit::Delete(3),
            Edit::Insert(
                InsertPosition {
                    parent_node_id: 1,
                    child_position: 1,
                    descendant_count: 0,
                },
                InsertContent::XmlNode(to_insert_two),
            ),
            Edit::Insert(
                InsertPosition {
                    parent_node_id: 1,
                    child_position: 2,
                    descendant_count: 0,
                },
                InsertContent::XmlNode(to_insert_extra),
            ),
        ];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><one/><x diff:delete=""/><two diff:insert=""/><extra diff:insert=""/><three/></a>"#
        );
    }

    #[test]
    fn test_insert_end() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><one/><two/></a>").unwrap();
        let to_insert = xot.parse("<three/>").unwrap();
        let to_insert = xot.document_element(to_insert).unwrap();
        let edits = [Edit::Insert(
            InsertPosition {
                parent_node_id: 1,
                child_position: 2,
                descendant_count: 2,
            },
            InsertContent::XmlNode(to_insert),
        )];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><one/><two/><three diff:insert=""/></a>"#
        );
    }

    #[test]
    fn test_insert_text_beginning() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><two/><three/></a>").unwrap();
        let edits = [Edit::Insert(
            InsertPosition {
                parent_node_id: 1,
                child_position: 0,
                descendant_count: 0,
            },
            InsertContent::Text("One".to_owned()),
        )];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><diff:text-insert>One</diff:text-insert><two/><three/></a>"#
        );
    }

    #[test]
    fn test_insert_text_middle() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><one/><three/></a>").unwrap();
        let edits = [Edit::Insert(
            InsertPosition {
                parent_node_id: 1,
                child_position: 1,
                descendant_count: 1,
            },
            InsertContent::Text("Two".to_owned()),
        )];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><one/><diff:text-insert>Two</diff:text-insert><three/></a>"#
        );
    }

    #[test]
    fn test_insert_text_end() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><one/><two/></a>").unwrap();
        let edits = [Edit::Insert(
            InsertPosition {
                parent_node_id: 1,
                child_position: 2,
                descendant_count: 2,
            },
            InsertContent::Text("Three".to_owned()),
        )];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><one/><two/><diff:text-insert>Three</diff:text-insert></a>"#
        );
    }

    #[test]
    fn test_delete_then_insert() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><b/><c/></a>").unwrap();
        let to_insert = xot.parse("<d/>").unwrap();
        let to_insert = xot.document_element(to_insert).unwrap();

        let edits = [
            Edit::Delete(2),
            Edit::Insert(
                InsertPosition {
                    parent_node_id: 1,
                    child_position: 0,
                    descendant_count: 0,
                },
                InsertContent::XmlNode(to_insert),
            ),
        ];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><b diff:delete=""/><d diff:insert=""/><c/></a>"#
        );
    }

    #[test]
    fn test_text_delete_then_insert() {
        let mut xot = Xot::new();
        let root = xot.parse("<a> <c/></a>").unwrap();
        let to_insert = xot.parse("<d/>").unwrap();
        let to_insert = xot.document_element(to_insert).unwrap();

        let edits = [
            Edit::Delete(2),
            Edit::Insert(
                InsertPosition {
                    parent_node_id: 1,
                    child_position: 0,
                    descendant_count: 0,
                },
                InsertContent::XmlNode(to_insert),
            ),
        ];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><diff:text-delete> </diff:text-delete><d diff:insert=""/><c/></a>"#
        );
    }

    #[test]
    fn test_delete_then_insert_after() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><b/><c/><d/></a>").unwrap();
        let to_insert = xot.parse("<x/>").unwrap();
        let to_insert = xot.document_element(to_insert).unwrap();

        let edits = [
            Edit::Delete(2),
            Edit::Insert(
                InsertPosition {
                    parent_node_id: 1,
                    child_position: 1,
                    descendant_count: 0,
                },
                InsertContent::XmlNode(to_insert),
            ),
        ];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><b diff:delete=""/><c/><x diff:insert=""/><d/></a>"#
        );
    }

    #[test]
    fn test_delete_then_insert_end() {
        let mut xot = Xot::new();
        let root = xot.parse("<a><b/><c/><d/></a>").unwrap();
        let to_insert = xot.parse("<x/>").unwrap();
        let to_insert = xot.document_element(to_insert).unwrap();

        let edits = [
            Edit::Delete(2),
            Edit::Insert(
                InsertPosition {
                    parent_node_id: 1,
                    child_position: 2,
                    descendant_count: 0,
                },
                InsertContent::XmlNode(to_insert),
            ),
        ];
        apply_edits(&mut xot, root, &edits);
        assert_eq!(
            xot.serialize_to_string(root),
            r#"<a xmlns:diff="http://paligo.net/nxd"><b diff:delete=""/><c/><d/><x diff:insert=""/></a>"#
        );
    }

    #[test]
    fn test_root_no_update_detected() -> Result<(), xot::Error> {
        let mut xot = Xot::new();
        // this is not detected as a text update, and it's the root element
        let xml_a = r#"<p>Hello</p>"#;
        let xml_b = r#"<p>Bye</p>"#;
        let doc_a = xot.parse(xml_a)?;
        let doc_b = xot.parse(xml_b)?;

        let mut comparison = Comparison::new(&xot, doc_a, doc_b);
        let diff_doc = comparison.diff(&mut xot);
        assert_eq!(
            xot.serialize_to_string(diff_doc),
            r#"<diff:root xmlns:diff="http://paligo.net/nxd"><p diff:delete="">Hello</p><p diff:insert="">Bye</p></diff:root>"#
        );
        Ok(())
    }

    #[test]
    fn test_inconsistent_propagation() -> Result<(), xot::Error> {
        let mut xot = Xot::new();
        // these are structurally different though the values are the same
        // we still want to detect updates even though propagation can erase them
        let xml_a = r#"<doc><a>A<b>B</b></a></doc>"#;
        let xml_b = r#"<doc><a>A</a><b>B</b></doc>"#;
        let doc_a = xot.parse(xml_a)?;
        let doc_b = xot.parse(xml_b)?;

        let mut comparison = Comparison::new(&xot, doc_a, doc_b);
        let diff_doc = comparison.diff(&mut xot);
        assert_eq!(
            xot.serialize_to_string(diff_doc),
            r#"<doc xmlns:diff="http://paligo.net/nxd"><a>A<b diff:delete="">B</b></a><b diff:insert="">B</b></doc>"#
        );
        Ok(())
    }
}