crates/oxy-core/src/diff.rs at 7ba155f20aa0 · andymccall/oxygen

# 7ba155f20aa0 oxygen / crates / oxy-core / src / diff.rs

10.6 KiB · Rust · last changed Diffs no longer anchor a block of new lines one line early 1 month ago source blame history raw

//! Turn a working-copy file into edits against the live atoms of a node.
//! Anchors follow the convention in spec §7.4: an insertion at old position
//! `i` is anchored after `old[i-1]` and before `old[i]`, both of which are
//! adjacent in the author's view.

use crate::graph::AtomKey;
use crate::ids::NodeId;
use crate::objects::{AtomRange, AtomRef, Edit};
use similar::DiffOp;

/// Split into lines, each keeping its terminator; a final unterminated line
/// is its own atom.
pub fn split_lines(b: &[u8]) -> Vec<&[u8]> {
    let mut out = Vec::new();
    let mut start = 0;
    for (i, &c) in b.iter().enumerate() {
        if c == b'\n' {
            out.push(&b[start..=i]);
            start = i + 1;
        }
    }
    if start < b.len() {
        out.push(&b[start..]);
    }
    out
}

/// Coalesce atom keys into half-open ranges of consecutive indices per change.
pub fn ranges(keys: &[AtomKey]) -> Vec<AtomRange> {
    let mut out: Vec<AtomRange> = Vec::new();
    for &(c, i) in keys {
        match out.last_mut() {
            Some(r) if r.change == c && r.to == i => r.to = i + 1,
            _ => out.push(AtomRange {
                change: c,
                from: i,
                to: i + 1,
            }),
        }
    }
    out
}

/// Edits that transform the live lines `old` of `node` into `new`.
pub fn text_edits(node: NodeId, old: &[(AtomKey, Vec<u8>)], new: &[u8]) -> Vec<Edit> {
    let old_lines: Vec<&[u8]> = old.iter().map(|(_, l)| l.as_slice()).collect();
    let new_lines = split_lines(new);
    // Myers ops in file order. `capture_diff_slices` also runs the `Compact`
    // hook, which slides deletions along runs of equal lines and can leave
    // an insertion with the old index of a line before an equal one: the
    // insertion was then anchored a line too early and landed on the wrong
    // side of it (found by verifying a real Git import commit by commit).
    let mut hook = similar::algorithms::Replace::new(similar::algorithms::Capture::new());
    let _ = similar::algorithms::diff_deadline(
        similar::Algorithm::Myers,
        &mut hook,
        &old_lines,
        0..old_lines.len(),
        &new_lines,
        0..new_lines.len(),
        None,
    );
    let ops = hook.into_inner().into_ops();

    let anchor = |i: usize| -> (AtomRef, AtomRef) {
        let after = if i == 0 {
            AtomRef::Start
        } else {
            AtomRef::Atom {
                change: old[i - 1].0 .0,
                index: old[i - 1].0 .1,
            }
        };
        let before = if i >= old.len() {
            AtomRef::End
        } else {
            AtomRef::Atom {
                change: old[i].0 .0,
                index: old[i].0 .1,
            }
        };
        (after, before)
    };

    let mut deleted: Vec<AtomKey> = Vec::new();
    let mut inserts: Vec<Edit> = Vec::new();
    for op in ops {
        match op {
            DiffOp::Equal { .. } => {}
            DiffOp::Delete {
                old_index, old_len, ..
            } => {
                deleted.extend(old[old_index..old_index + old_len].iter().map(|(k, _)| *k));
            }
            DiffOp::Insert {
                old_index,
                new_index,
                new_len,
            } => {
                let (after, before) = anchor(old_index);
                inserts.push(Edit::Insert {
                    node,
                    after,
                    before,
                    lines: new_lines[new_index..new_index + new_len]
                        .iter()
                        .map(|l| l.to_vec())
                        .collect(),
                });
            }
            DiffOp::Replace {
                old_index,
                old_len,
                new_index,
                new_len,
            } => {
                deleted.extend(old[old_index..old_index + old_len].iter().map(|(k, _)| *k));
                let (after, before) = anchor(old_index);
                inserts.push(Edit::Insert {
                    node,
                    after,
                    before,
                    lines: new_lines[new_index..new_index + new_len]
                        .iter()
                        .map(|l| l.to_vec())
                        .collect(),
                });
            }
        }
    }
    let mut edits = Vec::new();
    if !deleted.is_empty() {
        edits.push(Edit::Delete {
            node,
            atoms: ranges(&deleted),
        });
    }
    edits.extend(inserts);
    edits
}

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

    fn h(n: u8) -> ObjectRef {
        ObjectRef([n; 32])
    }

    /// Replaying `text_edits` by position must give the new text, on files
    /// full of repeated lines, where a diff has many equally good
    /// alignments to choose between.
    #[test]
    fn edits_replay_to_the_new_text_on_repetitive_files() {
        use rand::{Rng, SeedableRng};
        let words: [&[u8]; 5] = [b"}\n", b"    }\n", b"\n", b"a\n", b"    b\n"];
        let mut rng = rand::rngs::StdRng::seed_from_u64(11);
        for _ in 0..2000 {
            let old: Vec<Vec<u8>> = (0..rng.gen_range(0..30))
                .map(|_| words[rng.gen_range(0..5)].to_vec())
                .collect();
            let new: Vec<u8> = (0..rng.gen_range(0..30))
                .flat_map(|_| words[rng.gen_range(0..5)].to_vec())
                .collect();
            let keyed: Vec<(AtomKey, Vec<u8>)> = old
                .iter()
                .enumerate()
                .map(|(i, l)| ((h(1), i as u32), l.clone()))
                .collect();
            let edits = text_edits(NodeId::ROOT, &keyed, &new);
            let mut dead = vec![false; old.len()];
            let mut after: std::collections::BTreeMap<i64, Vec<u8>> = Default::default();
            for e in &edits {
                match e {
                    Edit::Delete { atoms, .. } => atoms
                        .iter()
                        .for_each(|r| (r.from..r.to).for_each(|i| dead[i as usize] = true)),
                    Edit::Insert {
                        after: a,
                        before: b,
                        lines,
                        ..
                    } => {
                        let at = match a {
                            AtomRef::Start => -1,
                            AtomRef::Atom { index, .. } => *index as i64,
                            AtomRef::End => unreachable!(),
                        };
                        let next = match b {
                            AtomRef::End => old.len() as i64,
                            AtomRef::Atom { index, .. } => *index as i64,
                            AtomRef::Start => unreachable!(),
                        };
                        assert_eq!(next, at + 1, "anchors adjacent");
                        after.entry(at).or_default().extend(lines.iter().flatten());
                    }
                    _ => {}
                }
            }
            let mut out = after.get(&-1).cloned().unwrap_or_default();
            for (i, l) in old.iter().enumerate() {
                if !dead[i] {
                    out.extend(l);
                }
                out.extend(after.get(&(i as i64)).cloned().unwrap_or_default());
            }
            assert_eq!(
                String::from_utf8_lossy(&out),
                String::from_utf8_lossy(&new),
                "old {old:?}"
            );
        }
    }

    #[test]
    fn split_keeps_terminators() {
        assert_eq!(split_lines(b"a\nb\n"), vec![&b"a\n"[..], &b"b\n"[..]]);
        assert_eq!(split_lines(b"a\nb"), vec![&b"a\n"[..], &b"b"[..]]);
        assert_eq!(split_lines(b""), Vec::<&[u8]>::new());
        assert_eq!(split_lines(b"\n\n"), vec![&b"\n"[..], &b"\n"[..]]);
    }

    #[test]
    fn ranges_coalesce() {
        let r = ranges(&[(h(1), 0), (h(1), 1), (h(1), 3), (h(2), 0)]);
        assert_eq!(
            r,
            vec![
                AtomRange {
                    change: h(1),
                    from: 0,
                    to: 2
                },
                AtomRange {
                    change: h(1),
                    from: 3,
                    to: 4
                },
                AtomRange {
                    change: h(2),
                    from: 0,
                    to: 1
                }
            ]
        );
    }

    #[test]
    fn edits_for_typical_changes() {
        let node = NodeId::random();
        let old: Vec<(AtomKey, Vec<u8>)> = ["a\n", "b\n", "c\n"]
            .iter()
            .enumerate()
            .map(|(i, l)| ((h(1), i as u32), l.as_bytes().to_vec()))
            .collect();
        // No change.
        assert!(text_edits(node, &old, b"a\nb\nc\n").is_empty());
        // Replace middle line.
        let e = text_edits(node, &old, b"a\nB\nc\n");
        assert_eq!(
            e,
            vec![
                Edit::Delete {
                    node,
                    atoms: vec![AtomRange {
                        change: h(1),
                        from: 1,
                        to: 2
                    }]
                },
                Edit::Insert {
                    node,
                    after: AtomRef::Atom {
                        change: h(1),
                        index: 0
                    },
                    before: AtomRef::Atom {
                        change: h(1),
                        index: 1
                    },
                    lines: vec![b"B\n".to_vec()]
                },
            ]
        );
        // Prepend and append.
        let e = text_edits(node, &old, b"top\na\nb\nc\nend\n");
        assert_eq!(e.len(), 2);
        assert!(matches!(
            &e[0],
            Edit::Insert {
                after: AtomRef::Start,
                before: AtomRef::Atom { index: 0, .. },
                ..
            }
        ));
        assert!(matches!(
            &e[1],
            Edit::Insert {
                after: AtomRef::Atom { index: 2, .. },
                before: AtomRef::End,
                ..
            }
        ));
        // Delete everything.
        let e = text_edits(node, &old, b"");
        assert_eq!(
            e,
            vec![Edit::Delete {
                node,
                atoms: vec![AtomRange {
                    change: h(1),
                    from: 0,
                    to: 3
                }]
            }]
        );
        // From empty.
        let e = text_edits(node, &[], b"x\n");
        assert_eq!(
            e,
            vec![Edit::Insert {
                node,
                after: AtomRef::Start,
                before: AtomRef::End,
                lines: vec![b"x\n".to_vec()]
            }]
        );
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	//! Turn a working-copy file into edits against the live atoms of a node.
2	//! Anchors follow the convention in spec §7.4: an insertion at old position
3	//! `i` is anchored after `old[i-1]` and before `old[i]`, both of which are
4	//! adjacent in the author's view.
5
6	use crate::graph::AtomKey;
7	use crate::ids::NodeId;
8	use crate::objects::{AtomRange, AtomRef, Edit};
9	use similar::DiffOp;
10
11	/// Split into lines, each keeping its terminator; a final unterminated line
12	/// is its own atom.
13	pub fn split_lines(b: &[u8]) -> Vec<&[u8]> {
14	let mut out = Vec::new();
15	let mut start = 0;
16	for (i, &c) in b.iter().enumerate() {
17	if c == b'\n' {
18	out.push(&b[start..=i]);
19	start = i + 1;
20	}
21	}
22	if start < b.len() {
23	out.push(&b[start..]);
24	}
25	out
26	}
27
28	/// Coalesce atom keys into half-open ranges of consecutive indices per change.
29	pub fn ranges(keys: &[AtomKey]) -> Vec<AtomRange> {
30	let mut out: Vec<AtomRange> = Vec::new();
31	for &(c, i) in keys {
32	match out.last_mut() {
33	Some(r) if r.change == c && r.to == i => r.to = i + 1,
34	_ => out.push(AtomRange {
35	change: c,
36	from: i,
37	to: i + 1,
38	}),
39	}
40	}
41	out
42	}
43
44	/// Edits that transform the live lines `old` of `node` into `new`.
45	pub fn text_edits(node: NodeId, old: &[(AtomKey, Vec<u8>)], new: &[u8]) -> Vec<Edit> {
46	let old_lines: Vec<&[u8]> = old.iter().map(\|(_, l)\| l.as_slice()).collect();
47	let new_lines = split_lines(new);
48	// Myers ops in file order. `capture_diff_slices` also runs the `Compact`
49	// hook, which slides deletions along runs of equal lines and can leave
50	// an insertion with the old index of a line before an equal one: the
51	// insertion was then anchored a line too early and landed on the wrong
52	// side of it (found by verifying a real Git import commit by commit).
53	let mut hook = similar::algorithms::Replace::new(similar::algorithms::Capture::new());
54	let _ = similar::algorithms::diff_deadline(
55	similar::Algorithm::Myers,
56	&mut hook,
57	&old_lines,
58	0..old_lines.len(),
59	&new_lines,
60	0..new_lines.len(),
61	None,
62	);
63	let ops = hook.into_inner().into_ops();
64
65	let anchor = \|i: usize\| -> (AtomRef, AtomRef) {
66	let after = if i == 0 {
67	AtomRef::Start
68	} else {
69	AtomRef::Atom {
70	change: old[i - 1].0 .0,
71	index: old[i - 1].0 .1,
72	}
73	};
74	let before = if i >= old.len() {
75	AtomRef::End
76	} else {
77	AtomRef::Atom {
78	change: old[i].0 .0,
79	index: old[i].0 .1,
80	}
81	};
82	(after, before)
83	};
84
85	let mut deleted: Vec<AtomKey> = Vec::new();
86	let mut inserts: Vec<Edit> = Vec::new();
87	for op in ops {
88	match op {
89	DiffOp::Equal { .. } => {}
90	DiffOp::Delete {
91	old_index, old_len, ..
92	} => {
93	deleted.extend(old[old_index..old_index + old_len].iter().map(\|(k, _)\| *k));
94	}
95	DiffOp::Insert {
96	old_index,
97	new_index,
98	new_len,
99	} => {
100	let (after, before) = anchor(old_index);
101	inserts.push(Edit::Insert {
102	node,
103	after,
104	before,
105	lines: new_lines[new_index..new_index + new_len]
106	.iter()
107	.map(\|l\| l.to_vec())
108	.collect(),
109	});
110	}
111	DiffOp::Replace {
112	old_index,
113	old_len,
114	new_index,
115	new_len,
116	} => {
117	deleted.extend(old[old_index..old_index + old_len].iter().map(\|(k, _)\| *k));
118	let (after, before) = anchor(old_index);
119	inserts.push(Edit::Insert {
120	node,
121	after,
122	before,
123	lines: new_lines[new_index..new_index + new_len]
124	.iter()
125	.map(\|l\| l.to_vec())
126	.collect(),
127	});
128	}
129	}
130	}
131	let mut edits = Vec::new();
132	if !deleted.is_empty() {
133	edits.push(Edit::Delete {
134	node,
135	atoms: ranges(&deleted),
136	});
137	}
138	edits.extend(inserts);
139	edits
140	}
141
142	#[cfg(test)]
143	mod tests {
144	use super::*;
145	use crate::hash::ObjectRef;
146
147	fn h(n: u8) -> ObjectRef {
148	ObjectRef([n; 32])
149	}
150
151	/// Replaying `text_edits` by position must give the new text, on files
152	/// full of repeated lines, where a diff has many equally good
153	/// alignments to choose between.
154	#[test]
155	fn edits_replay_to_the_new_text_on_repetitive_files() {
156	use rand::{Rng, SeedableRng};
157	let words: [&[u8]; 5] = [b"}\n", b" }\n", b"\n", b"a\n", b" b\n"];
158	let mut rng = rand::rngs::StdRng::seed_from_u64(11);
159	for _ in 0..2000 {
160	let old: Vec<Vec<u8>> = (0..rng.gen_range(0..30))
161	.map(\|_\| words[rng.gen_range(0..5)].to_vec())
162	.collect();
163	let new: Vec<u8> = (0..rng.gen_range(0..30))
164	.flat_map(\|_\| words[rng.gen_range(0..5)].to_vec())
165	.collect();
166	let keyed: Vec<(AtomKey, Vec<u8>)> = old
167	.iter()
168	.enumerate()
169	.map(\|(i, l)\| ((h(1), i as u32), l.clone()))
170	.collect();
171	let edits = text_edits(NodeId::ROOT, &keyed, &new);
172	let mut dead = vec![false; old.len()];
173	let mut after: std::collections::BTreeMap<i64, Vec<u8>> = Default::default();
174	for e in &edits {
175	match e {
176	Edit::Delete { atoms, .. } => atoms
177	.iter()
178	.for_each(\|r\| (r.from..r.to).for_each(\|i\| dead[i as usize] = true)),
179	Edit::Insert {
180	after: a,
181	before: b,
182	lines,
183	..
184	} => {
185	let at = match a {
186	AtomRef::Start => -1,
187	AtomRef::Atom { index, .. } => *index as i64,
188	AtomRef::End => unreachable!(),
189	};
190	let next = match b {
191	AtomRef::End => old.len() as i64,
192	AtomRef::Atom { index, .. } => *index as i64,
193	AtomRef::Start => unreachable!(),
194	};
195	assert_eq!(next, at + 1, "anchors adjacent");
196	after.entry(at).or_default().extend(lines.iter().flatten());
197	}
198	_ => {}
199	}
200	}
201	let mut out = after.get(&-1).cloned().unwrap_or_default();
202	for (i, l) in old.iter().enumerate() {
203	if !dead[i] {
204	out.extend(l);
205	}
206	out.extend(after.get(&(i as i64)).cloned().unwrap_or_default());
207	}
208	assert_eq!(
209	String::from_utf8_lossy(&out),
210	String::from_utf8_lossy(&new),
211	"old {old:?}"
212	);
213	}
214	}
215
216	#[test]
217	fn split_keeps_terminators() {
218	assert_eq!(split_lines(b"a\nb\n"), vec![&b"a\n"[..], &b"b\n"[..]]);
219	assert_eq!(split_lines(b"a\nb"), vec![&b"a\n"[..], &b"b"[..]]);
220	assert_eq!(split_lines(b""), Vec::<&[u8]>::new());
221	assert_eq!(split_lines(b"\n\n"), vec![&b"\n"[..], &b"\n"[..]]);
222	}
223
224	#[test]
225	fn ranges_coalesce() {
226	let r = ranges(&[(h(1), 0), (h(1), 1), (h(1), 3), (h(2), 0)]);
227	assert_eq!(
228	r,
229	vec![
230	AtomRange {
231	change: h(1),
232	from: 0,
233	to: 2
234	},
235	AtomRange {
236	change: h(1),
237	from: 3,
238	to: 4
239	},
240	AtomRange {
241	change: h(2),
242	from: 0,
243	to: 1
244	}
245	]
246	);
247	}
248
249	#[test]
250	fn edits_for_typical_changes() {
251	let node = NodeId::random();
252	let old: Vec<(AtomKey, Vec<u8>)> = ["a\n", "b\n", "c\n"]
253	.iter()
254	.enumerate()
255	.map(\|(i, l)\| ((h(1), i as u32), l.as_bytes().to_vec()))
256	.collect();
257	// No change.
258	assert!(text_edits(node, &old, b"a\nb\nc\n").is_empty());
259	// Replace middle line.
260	let e = text_edits(node, &old, b"a\nB\nc\n");
261	assert_eq!(
262	e,
263	vec![
264	Edit::Delete {
265	node,
266	atoms: vec![AtomRange {
267	change: h(1),
268	from: 1,
269	to: 2
270	}]
271	},
272	Edit::Insert {
273	node,
274	after: AtomRef::Atom {
275	change: h(1),
276	index: 0
277	},
278	before: AtomRef::Atom {
279	change: h(1),
280	index: 1
281	},
282	lines: vec![b"B\n".to_vec()]
283	},
284	]
285	);
286	// Prepend and append.
287	let e = text_edits(node, &old, b"top\na\nb\nc\nend\n");
288	assert_eq!(e.len(), 2);
289	assert!(matches!(
290	&e[0],
291	Edit::Insert {
292	after: AtomRef::Start,
293	before: AtomRef::Atom { index: 0, .. },
294	..
295	}
296	));
297	assert!(matches!(
298	&e[1],
299	Edit::Insert {
300	after: AtomRef::Atom { index: 2, .. },
301	before: AtomRef::End,
302	..
303	}
304	));
305	// Delete everything.
306	let e = text_edits(node, &old, b"");
307	assert_eq!(
308	e,
309	vec![Edit::Delete {
310	node,
311	atoms: vec![AtomRange {
312	change: h(1),
313	from: 0,
314	to: 3
315	}]
316	}]
317	);
318	// From empty.
319	let e = text_edits(node, &[], b"x\n");
320	assert_eq!(
321	e,
322	vec![Edit::Insert {
323	node,
324	after: AtomRef::Start,
325	before: AtomRef::End,
326	lines: vec![b"x\n".to_vec()]
327	}]
328	);
329	}
330	}

Keyboard