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

pub fn merge(ancestor: &str, incoming_edit: &str, current: &str) -> Option<String> {
    if ancestor == current {
        // if there have been no changes between the proposal and now, no need to merge
        return Some(incoming_edit.to_string());
    }

    let mut incoming = diff::chars(ancestor, incoming_edit).into_iter().peekable();
    let mut existing = diff::chars(ancestor, current).into_iter().peekable();

    let mut result = String::new();
    'outer: loop {
        match incoming.next() {
            // char was unchanged in the incoming update, accept whatever changes exist in current
            Some(diff::Result::Both(inc_left, _)) => loop {
                match existing.next() {
                    // char was also unchanged in the existing changes, push the char to result
                    Some(diff::Result::Both(..)) => {
                        result.push(inc_left);
                        break;
                    }
                    // char was removed in the existing update, skip over it in the result
                    Some(diff::Result::Left(_)) => break,
                    // a char was added in the existing update, add it to the result and keep reading the existing changes
                    Some(diff::Result::Right(right)) => result.push(right),
                    // unexpectedly ran out of existing changes, fail merge
                    None => return None,
                }
            },
            // char was removed in the incoming update
            Some(diff::Result::Left(_)) => match existing.next() {
                // char was unchanged in the existing changes, skip over it in the result
                Some(diff::Result::Both(..)) => continue,
                // char was also removed in the existing changes, skip over it in the result
                Some(diff::Result::Left(_)) => continue,
                // a char was added in existing changes, hard to say what should be done here
                // ignoring the addition seems to produce the best results
                Some(diff::Result::Right(_)) => continue,
                // unexpectedly ran out of existing changes, fail merge
                None => return None,
            },
            // char was added in the incoming update
            Some(diff::Result::Right(inc_right)) => {
                // check the next diff in existing to avoid duplicate additions
                if let Some(diff::Result::Right(next_existing)) = existing.peek() {
                    // same character added in both updates, skip over it in existing
                    if next_existing == &inc_right {
                        existing.next();
                    }
                }
                result.push(inc_right)
            }
            // end of incoming changes
            None => loop {
                match existing.next() {
                    // unchanged in the existing changes
                    Some(diff::Result::Both(..)) => continue,
                    // removed in the existing changes
                    Some(diff::Result::Left(_)) => continue,
                    // new in the existing changes
                    Some(diff::Result::Right(right)) => result.push(right),
                    // end of changes
                    None => break 'outer,
                }
            },
        }
    }
    Some(result)
}

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

    #[test]
    fn typo_and_append() {
        let ancestor = "This is the original, uneditd text.";
        let incoming =
            "This is the original, uneditd text, with more information written at the end.";
        let current = "This is the original, unedited text.";
        assert_eq!(
            merge(ancestor, incoming, current).unwrap(),
            "This is the original, unedited text, with more information written at the end."
        );
    }

    #[test]
    fn typo_and_prepend() {
        let ancestor = "This is the original, uneditd text.";
        let incoming = "I added some things, but this is the original, uneditd text.";
        let current = "This is the original, unedited text.";
        assert_eq!(
            merge(ancestor, incoming, current).unwrap(),
            "I added some things, but this is the original, unedited text."
        );
    }

    #[test]
    fn typo_and_middle() {
        let ancestor = "This is the original, uneditd text.";
        let incoming = "This is the original, completely uneditd text.";
        let current = "This is the original, unedited text.";
        assert_eq!(
            merge(ancestor, incoming, current).unwrap(),
            "This is the original, completely unedited text."
        );
    }

    #[test]
    fn rewrite() {
        let ancestor = "This is the original, uneditd text.";
        let incoming = "I decided to rewrite this paragraph!";
        let current = "This is the original, unedited text.";
        assert_eq!(
            merge(ancestor, incoming, current).unwrap(),
            "I decided to rewrite this paragraph!"
        );
    }

    #[test]
    fn same_edit_applied_twice() {
        let ancestor = "This is the original, uneditd text.";
        let incoming = "This is the original, unedited text.";
        let current = "This is the original, unedited text.";
        assert_eq!(
            merge(ancestor, incoming, current).unwrap(),
            "This is the original, unedited text."
        );
    }

    #[test]
    fn regression_test() {
        let ancestor = "paragraphs.";
        let incoming = "pgraphs.";
        let current = "paragraphs!";
        assert_eq!(merge(ancestor, incoming, current).unwrap(), "pgraphs!");
    }
}