crates/oxy-core/src/diff.rs at 3faccd90ddfa · andymccall/oxygen

# 3faccd90ddfa oxygen / crates / oxy-core / src / diff.rs

7.2 KiB · Rust · last changed Unbound hosted repositories adopt the first pusher's id 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::{capture_diff_slices, Algorithm, 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);
    let ops = capture_diff_slices(Algorithm::Myers, &old_lines, &new_lines);

    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])
    }

    #[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::{capture_diff_slices, Algorithm, 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	let ops = capture_diff_slices(Algorithm::Myers, &old_lines, &new_lines);
49
50	let anchor = \|i: usize\| -> (AtomRef, AtomRef) {
51	let after = if i == 0 {
52	AtomRef::Start
53	} else {
54	AtomRef::Atom {
55	change: old[i - 1].0 .0,
56	index: old[i - 1].0 .1,
57	}
58	};
59	let before = if i >= old.len() {
60	AtomRef::End
61	} else {
62	AtomRef::Atom {
63	change: old[i].0 .0,
64	index: old[i].0 .1,
65	}
66	};
67	(after, before)
68	};
69
70	let mut deleted: Vec<AtomKey> = Vec::new();
71	let mut inserts: Vec<Edit> = Vec::new();
72	for op in ops {
73	match op {
74	DiffOp::Equal { .. } => {}
75	DiffOp::Delete {
76	old_index, old_len, ..
77	} => {
78	deleted.extend(old[old_index..old_index + old_len].iter().map(\|(k, _)\| *k));
79	}
80	DiffOp::Insert {
81	old_index,
82	new_index,
83	new_len,
84	} => {
85	let (after, before) = anchor(old_index);
86	inserts.push(Edit::Insert {
87	node,
88	after,
89	before,
90	lines: new_lines[new_index..new_index + new_len]
91	.iter()
92	.map(\|l\| l.to_vec())
93	.collect(),
94	});
95	}
96	DiffOp::Replace {
97	old_index,
98	old_len,
99	new_index,
100	new_len,
101	} => {
102	deleted.extend(old[old_index..old_index + old_len].iter().map(\|(k, _)\| *k));
103	let (after, before) = anchor(old_index);
104	inserts.push(Edit::Insert {
105	node,
106	after,
107	before,
108	lines: new_lines[new_index..new_index + new_len]
109	.iter()
110	.map(\|l\| l.to_vec())
111	.collect(),
112	});
113	}
114	}
115	}
116	let mut edits = Vec::new();
117	if !deleted.is_empty() {
118	edits.push(Edit::Delete {
119	node,
120	atoms: ranges(&deleted),
121	});
122	}
123	edits.extend(inserts);
124	edits
125	}
126
127	#[cfg(test)]
128	mod tests {
129	use super::*;
130	use crate::hash::ObjectRef;
131
132	fn h(n: u8) -> ObjectRef {
133	ObjectRef([n; 32])
134	}
135
136	#[test]
137	fn split_keeps_terminators() {
138	assert_eq!(split_lines(b"a\nb\n"), vec![&b"a\n"[..], &b"b\n"[..]]);
139	assert_eq!(split_lines(b"a\nb"), vec![&b"a\n"[..], &b"b"[..]]);
140	assert_eq!(split_lines(b""), Vec::<&[u8]>::new());
141	assert_eq!(split_lines(b"\n\n"), vec![&b"\n"[..], &b"\n"[..]]);
142	}
143
144	#[test]
145	fn ranges_coalesce() {
146	let r = ranges(&[(h(1), 0), (h(1), 1), (h(1), 3), (h(2), 0)]);
147	assert_eq!(
148	r,
149	vec![
150	AtomRange {
151	change: h(1),
152	from: 0,
153	to: 2
154	},
155	AtomRange {
156	change: h(1),
157	from: 3,
158	to: 4
159	},
160	AtomRange {
161	change: h(2),
162	from: 0,
163	to: 1
164	}
165	]
166	);
167	}
168
169	#[test]
170	fn edits_for_typical_changes() {
171	let node = NodeId::random();
172	let old: Vec<(AtomKey, Vec<u8>)> = ["a\n", "b\n", "c\n"]
173	.iter()
174	.enumerate()
175	.map(\|(i, l)\| ((h(1), i as u32), l.as_bytes().to_vec()))
176	.collect();
177	// No change.
178	assert!(text_edits(node, &old, b"a\nb\nc\n").is_empty());
179	// Replace middle line.
180	let e = text_edits(node, &old, b"a\nB\nc\n");
181	assert_eq!(
182	e,
183	vec![
184	Edit::Delete {
185	node,
186	atoms: vec![AtomRange {
187	change: h(1),
188	from: 1,
189	to: 2
190	}]
191	},
192	Edit::Insert {
193	node,
194	after: AtomRef::Atom {
195	change: h(1),
196	index: 0
197	},
198	before: AtomRef::Atom {
199	change: h(1),
200	index: 1
201	},
202	lines: vec![b"B\n".to_vec()]
203	},
204	]
205	);
206	// Prepend and append.
207	let e = text_edits(node, &old, b"top\na\nb\nc\nend\n");
208	assert_eq!(e.len(), 2);
209	assert!(matches!(
210	&e[0],
211	Edit::Insert {
212	after: AtomRef::Start,
213	before: AtomRef::Atom { index: 0, .. },
214	..
215	}
216	));
217	assert!(matches!(
218	&e[1],
219	Edit::Insert {
220	after: AtomRef::Atom { index: 2, .. },
221	before: AtomRef::End,
222	..
223	}
224	));
225	// Delete everything.
226	let e = text_edits(node, &old, b"");
227	assert_eq!(
228	e,
229	vec![Edit::Delete {
230	node,
231	atoms: vec![AtomRange {
232	change: h(1),
233	from: 0,
234	to: 3
235	}]
236	}]
237	);
238	// From empty.
239	let e = text_edits(node, &[], b"x\n");
240	assert_eq!(
241	e,
242	vec![Edit::Insert {
243	node,
244	after: AtomRef::Start,
245	before: AtomRef::End,
246	lines: vec![b"x\n".to_vec()]
247	}]
248	);
249	}
250	}

Keyboard