natural-xml-diff 0.2.0

Natural diffing between XML documents
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

use std::ops::Range;

use crate::comparison::{Comparison, EqualPair};

pub(crate) type Overlap = (Range<usize>, Range<usize>);

impl Comparison {
    /// Partition the vtrees into equal and non-equal nodes
    /// Return the ranges of equal nodes
    ///
    /// This is a low-level API in order to get insight into the
    /// workings of the diff algorithm.
    pub(crate) fn partition(&self) -> Vec<(Range<usize>, Range<usize>)> {
        self.partition_in_range(0..self.vtree_a.nodes.len(), 0..self.vtree_b.nodes.len())
    }

    fn partition_in_range(
        &self,
        range_a: Range<usize>,
        range_b: Range<usize>,
    ) -> Vec<(Range<usize>, Range<usize>)> {
        let mut ranges = vec![(range_a, range_b)];
        let mut result = Vec::new();
        while !ranges.is_empty() {
            let (range_a, range_b) = ranges.pop().unwrap();
            let overlap = self.lcss_in_range(range_a.clone(), range_b.clone());
            let (overlap_a, overlap_b) = overlap.clone();
            if overlap_a.is_empty() {
                // if overlap_a is empty then overlap_b will be empty too
                continue;
            }
            result.push(overlap);
            let before_range_a = range_a.start..overlap_a.start;
            let after_range_a = overlap_a.end..range_a.end;
            let before_range_b = range_b.start..overlap_b.start;
            let after_range_b = overlap_b.end..range_b.end;
            ranges.push((before_range_a, before_range_b));
            ranges.push((after_range_a, after_range_b));
        }
        result.sort_by_key(|(range_a, _)| range_a.start);
        result
    }
}

pub(crate) fn equal_pairs(overlaps: &[Overlap]) -> Vec<EqualPair> {
    overlaps
        .iter()
        .flat_map(|(a_range, b_range)| a_range.clone().into_iter().zip(b_range.clone().into_iter()))
        .map(|(a, b)| EqualPair(a, b))
        .collect::<Vec<_>>()
}

#[cfg(test)]
mod tests {
    use super::*;
    use xot::Xot;

    #[test]
    fn test_partition() {
        let mut xot = Xot::new();
        let doc_a = xot.parse("<container><a/><b/></container>").unwrap();
        let doc_b = xot
            .parse("<container><x/><a/><b/><c/></container>")
            .unwrap();

        let comparison = Comparison::new(&xot, doc_a, doc_b);
        let result = comparison.partition();
        assert_eq!(result, vec![(2..4, 3..5)]);
    }

    #[test]
    fn test_partition_multiple_overlaps() {
        let mut xot = Xot::new();
        let doc_a = xot
            .parse("<container><a/><b/><x/><c/><d/></container>")
            .unwrap();
        let doc_b = xot
            .parse("<container><x/><a/><b/><c/><d/></container>")
            .unwrap();

        let comparison = Comparison::new(&xot, doc_a, doc_b);
        let result = comparison.partition();
        assert_eq!(result, vec![(2..4, 3..5), (5..7, 5..7)]);
    }

    #[test]
    fn test_partition_longer() {
        let mut xot = Xot::new();
        // example taken from the jndiff paper, page 11
        let doc_a = xot
            .parse(concat!(
                "<book><chapter><title>Text 1</title><para>Text 2</para></chapter>",
                "<chapter><title>Text 4</title><para>Text 5</para></chapter>",
                "<chapter><title>Text 6</title><para>Text 7<img/>Text 8</para></chapter>",
                "<chapter><title>Text 9</title><para>Text 10</para></chapter>",
                "<chapter><para>Text 11</para><para>Text 12</para></chapter></book>"
            ))
            .unwrap();
        let doc_b = xot
            .parse(concat!(
                "
            <book><chapter><para>Text 2</para></chapter>",
                "<chapter><title>Text 4</title><para>Text 25</para><para>Text 11</para></chapter>",
                "<chapter><title>Text 6</title><para>Text 7<img/>Text 8</para></chapter>",
                "<chapter><title>Text 9</title><para>Text 10</para></chapter>",
                "<chapter><para>Text 12</para></chapter></book>"
            ))
            .unwrap();

        let comparison = Comparison::new(&xot, doc_a, doc_b);
        let result = comparison.partition();
        assert_eq!(
            result,
            vec![
                (5..7, 3..5),
                (8..10, 6..8),
                (12..24, 12..24),
                (27..29, 25..27)
            ]
        );
    }

    #[test]
    fn test_partition_problematic() {
        let mut xot = Xot::new();
        let xml_a = r#"<section>
    <title>Section title</title>
    <para>Compare documents with different root element</para>

    <section>
        <title>Sit Ipsum Consectetur Sem Ligula</title>
        <para>Etiam porta sem malesuada <phrase>magna mollis euismod</phrase>. Lorem ipsum dolor sit amet, consectetur adipiscing elit.</para>
    </section>

    <section>
        <title>Ultricies Mollis Mattis Ullamcorper Ridiculus</title>
        <para>Morbi leo <code>porta ac consectetur</code>risus,  ac, vestibulum at eros. Cras mattis consectetur purus sit amet fermentum. Donec id elit non mi porta gravida at eget metus. <phrase>magna mollis euismod</phrase>. Lorem ipsum dolor sit amet, consectetur adipiscing elit.</para>
    </section>
</section>"#;
        let xml_b = r#"<section>
    <title>Section title</title>
    <para>Compare documents with different root element</para>

    <section>
        <title>Ultricies Mollis Mattis Ullamcorper Ridiculus</title>
        <para>Morbi leo <code>porta ac consectetur</code>risus,  ac, vestibulum at eros. Cras mattis consectetur purus sit amet fermentum. Donec id elit non mi porta gravida at eget metus. <phrase>magna mollis euismod</phrase>. Lorem ipsum dolor sit amet, consectetur adipiscing elit.</para>
    </section>

    <section>
        <title>Sit Ipsum Consectetur Sem Ligula</title>
        <para>Etiam porta sem malesuada <phrase>magna mollis euismod</phrase>. Lorem ipsum dolor sit amet, consectetur adipiscing elit.</para>
    </section>
</section>"#;
        let doc_a = xot.parse(xml_a).unwrap();
        let doc_b = xot.parse(xml_b).unwrap();
        let comparison = Comparison::new(&xot, doc_a, doc_b);
        let result = comparison.partition();
        assert_eq!(
            result,
            vec![(2..8, 2..8), (20..35, 8..23), (35..36, 35..36)]
        );
    }
}