Oregami
Repositories/oxedyne/ore

oxedyne/ore/cli/tests/moves.rs

13.8 KiB, 5 runs

created by r2848102244:31, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Capture-side move detection: a block that leaves one place and arrives in
2//! another, byte for byte, is recorded as the engine's `Op::Move` rather than
3//! as a deletion and an insertion.
4//!
5//! The distinction is not cosmetic. A move relocates the bytes the history
6//! already knows, so everything anchored to them travels: a concurrent edit
7//! inside the block renders inside the block at its new home, and `ore who`
8//! keeps naming the bytes' original authors. A deletion and an insertion mint
9//! fresh bytes, and everything anchored to the old ones dies with them --
10//! which is what round 4 of the two-replica trial showed, and what these tests
11//! close.
12
13mod support;
14
15use support::{
16 ore,
17 read_segment,
18 runs_in,
19 write,
20 Scratch,
21};
22
23use oxedyne_fe2o3_core::prelude::*;
24use oxedyne_fe2o3_ore::op::Op;
25use oxedyne_fe2o3_ore::segment::Entry;
26
27use std::fs;
28use std::path::{
29 Path,
30 PathBuf,
31};
32
33
34/// The top of the utility file: a function that stays put.
35const UTIL_TOP: &str = "fn shout(s: &str) -> String {\n\ts.to_uppercase()\n}\n\n";
36
37/// The block the tests move about: a whole function, comfortably past the
38/// pairing threshold and unique in the tree.
39const BLOCK: &str = "fn is_number(s: &str) -> bool {\n\
40 \tlet t = s.trim();\n\
41 \t!t.is_empty() && t.chars().all(|c| c.is_ascii_digit())\n\
42 }\n";
43
44/// The library file the block moves into.
45const LIB: &str = "pub mod util;\n\nfn double(n: u64) -> u64 {\n\tn * 2\n}\n\n";
46
47/// The line a concurrent editor adds inside the block, after its `trim` line.
48const GUARD: &str = "\tif t.len() > 40 { return false; }\n";
49
50
51/// Returns the block with the guard line inserted after its second line.
52fn edited_block() -> String {
53 let at = match BLOCK.find("\t!t.is_empty()") {
54 Some(i) => i,
55 None => 0,
56 };
57 fmt!("{}{}{}", &BLOCK[..at], GUARD, &BLOCK[at..])
58}
59
60/// Reads every operation of a repository's log, in replay order.
61fn ops_in(root: &Path)
62 -> Outcome<Vec<Op>>
63{
64 let dir = root.join(".ore").join("log");
65 let mut segs: Vec<PathBuf> = Vec::new();
66 for entry in res!(fs::read_dir(&dir)) {
67 let path = res!(entry).path();
68 if path.extension().map(|e| e == "seg").unwrap_or(false) {
69 segs.push(path);
70 }
71 }
72 segs.sort();
73 let mut out: Vec<Op> = Vec::new();
74 for path in segs {
75 let (_, entries) = res!(read_segment(&path));
76 for entry in entries {
77 match entry {
78 Entry::Bare(rec) => out.push(rec.op),
79 Entry::Sealed(env) => out.push(res!(env.peek_record()).op),
80 Entry::Veiled(v) => return Err(err!(
81 "The operation {} is veiled in a working copy's own segments, which \
82 nothing writes there.", v.head.id(); Test, Invalid)),
83 }
84 }
85 }
86 Ok(out)
87}
88
89/// Counts the moves in a list of operations.
90fn moves_in(ops: &[Op]) -> usize {
91 ops.iter().filter(|op| op.is_move()).count()
92}
93
94/// Returns the operation `who` attributes the byte at `offset` of a file to.
95fn author_at(root: &Path, file: &str, offset: usize)
96 -> Outcome<String>
97{
98 let out = res!(ore(root, &["who", file]));
99 let text = fmt!("{}", res!(out.good("who")));
100 let mut found: Option<String> = None;
101 for run in runs_in(&text) {
102 if run.from <= offset {
103 found = Some(run.op);
104 }
105 }
106 match found {
107 Some(op) => Ok(op),
108 None => Err(err!(
109 "No run of {} covers offset {}: {}", file, offset, text;
110 Test, Missing)),
111 }
112}
113
114
115/// A function moved whole from one file to another in one capture is one
116/// `Op::Move` in the log, not a deletion and an insertion, and the bytes keep
117/// their original author.
118#[test]
119fn a_block_moved_between_files_is_one_move_operation() -> Outcome<()> {
120 let scratch = res!(Scratch::new("move_cross"));
121 let root = res!(scratch.sub("work"));
122 res!(res!(ore(&root, &["init"])).good("init"));
123 res!(write(&root, "util.rs", fmt!("{}{}", UTIL_TOP, BLOCK).as_bytes()));
124 res!(write(&root, "lib.rs", LIB.as_bytes()));
125 res!(res!(ore(&root, &["mark", "base"])).good("mark base"));
126 assert_eq!(moves_in(&res!(ops_in(&root))), 0, "nothing has moved yet");
127 let author = res!(author_at(&root, "util.rs", UTIL_TOP.len()));
128
129 // The move, as an editor leaves it on disk: gone here, arrived there.
130 res!(write(&root, "util.rs", UTIL_TOP.as_bytes()));
131 res!(write(&root, "lib.rs", fmt!("{}{}", LIB, BLOCK).as_bytes()));
132 let out = res!(ore(&root, &["mark", "moved"]));
133 let text = fmt!("{}", res!(out.good("mark moved")));
134 assert!(text.contains("1 moved as a block"),
135 "the capture says it recorded a move: {}", text);
136 assert!(text.contains("from util.rs to lib.rs"),
137 "and names both ends of it: {}", text);
138
139 // The log holds the move itself, and no splice re-inserting the block.
140 let ops = res!(ops_in(&root));
141 assert_eq!(moves_in(&ops), 1, "one block moved, one Op::Move");
142 for op in &ops {
143 if let Op::Splice { insert, .. } = op {
144 assert!(&insert[..] != BLOCK.as_bytes(),
145 "the block's bytes were re-minted by a splice");
146 }
147 }
148
149 // The render agrees with the disk, so the very next verb captures nothing.
150 let out = res!(ore(&root, &["flags"]));
151 let text = fmt!("{}", res!(out.good("flags")));
152 assert!(text.contains("captured nothing"),
153 "the move renders exactly what the editor left: {}", text);
154
155 // And the bytes kept their author: `who` names the operation that wrote
156 // them into util.rs, not the move.
157 assert_eq!(res!(author_at(&root, "lib.rs", LIB.len())), author,
158 "a moved block keeps its provenance");
159 Ok(())
160}
161
162/// A block moved to another place in the same file is a move too.
163#[test]
164fn a_block_moved_within_one_file_is_one_move_operation() -> Outcome<()> {
165 let scratch = res!(Scratch::new("move_within"));
166 let root = res!(scratch.sub("work"));
167 res!(res!(ore(&root, &["init"])).good("init"));
168 // The head has more lines than the block, so the shortest edit script for
169 // the rearrangement is the block moving and not the head.
170 let head = fmt!("{}{}", UTIL_TOP, LIB);
171 res!(write(&root, "one.rs", fmt!("{}{}", head, BLOCK).as_bytes()));
172 res!(res!(ore(&root, &["mark", "base"])).good("mark base"));
173 let author = res!(author_at(&root, "one.rs", head.len()));
174
175 res!(write(&root, "one.rs", fmt!("{}{}", BLOCK, head).as_bytes()));
176 let out = res!(ore(&root, &["mark", "rearranged"]));
177 let text = fmt!("{}", res!(out.good("mark rearranged")));
178 assert!(text.contains("1 moved as a block"),
179 "a move within one file is still a move: {}", text);
180 assert!(text.contains("from one.rs to one.rs"),
181 "and both ends are the one file: {}", text);
182 assert_eq!(moves_in(&res!(ops_in(&root))), 1);
183
184 let out = res!(ore(&root, &["flags"]));
185 let text = fmt!("{}", res!(out.good("flags")));
186 assert!(text.contains("captured nothing"),
187 "the move renders exactly what the editor left: {}", text);
188 assert_eq!(res!(author_at(&root, "one.rs", 0)), author,
189 "the rearranged block keeps its provenance");
190 Ok(())
191}
192
193/// THE FLAGSHIP: one replica moves a block across files while another edits
194/// inside it, and after the sync the edit renders inside the block at its new
195/// home -- byte for byte, at both ends.
196///
197/// This is round 4 of the two-replica trial done right. With the move recorded
198/// as delete-plus-insert, the edit stranded as a syntactically broken sliver at
199/// the deletion site and nothing was flagged; recorded as a move, the edit's
200/// anchors name block bytes, the block's bytes keep their identity, and the
201/// engine carries the edit to the block's destination with nothing further
202/// written to make it do so.
203#[test]
204fn an_edit_inside_a_concurrently_moved_block_follows_the_move() -> Outcome<()> {
205 let scratch = res!(Scratch::new("move_follow"));
206 let a = res!(scratch.sub("a"));
207 let b = res!(scratch.sub("b"));
208 res!(res!(ore(&a, &["init"])).good("init a"));
209 res!(write(&a, "util.rs", fmt!("{}{}", UTIL_TOP, BLOCK).as_bytes()));
210 res!(write(&a, "lib.rs", LIB.as_bytes()));
211 res!(res!(ore(&a, &["mark", "base"])).good("mark base"));
212 res!(res!(ore(&b, &["init"])).good("init b"));
213 res!(res!(ore(&b, &["sync", &fmt!("{}", a.display())])).good("clone"));
214
215 // Replica A moves the block from util.rs into lib.rs.
216 res!(write(&a, "util.rs", UTIL_TOP.as_bytes()));
217 res!(write(&a, "lib.rs", fmt!("{}{}", LIB, BLOCK).as_bytes()));
218 let text = fmt!("{}", res!(res!(ore(&a, &["mark", "moved"])).good("mark moved")));
219 assert!(text.contains("1 moved as a block"), "A's capture found the move: {}", text);
220
221 // Replica B, knowing nothing of it, strengthens the block where it was.
222 res!(write(&b, "util.rs", fmt!("{}{}", UTIL_TOP, edited_block()).as_bytes()));
223 res!(res!(ore(&b, &["mark", "guarded"])).good("mark guarded"));
224
225 // One sync converges both logs and writes B's working copy.
226 res!(res!(ore(&b, &["sync", &fmt!("{}", a.display())])).good("sync"));
227
228 // B's edit renders inside the moved block at its new home, byte-verified:
229 // lib.rs is exactly the library plus the *edited* block, and util.rs is
230 // exactly what remains -- no stranded sliver, nothing lost.
231 let want_lib = fmt!("{}{}", LIB, edited_block());
232 assert_eq!(res!(fs::read(b.join("lib.rs"))), want_lib.as_bytes().to_vec(),
233 "the guard line followed the block into lib.rs");
234 assert_eq!(res!(fs::read(b.join("util.rs"))), UTIL_TOP.as_bytes().to_vec(),
235 "and nothing of the block, or of the edit, stranded in util.rs");
236
237 // The other end settles to the same bytes at its next verb.
238 res!(res!(ore(&a, &["log"])).good("settle a"));
239 assert_eq!(res!(fs::read(a.join("lib.rs"))), want_lib.as_bytes().to_vec(),
240 "both replicas render the edit inside the moved block");
241 assert_eq!(res!(fs::read(a.join("util.rs"))), UTIL_TOP.as_bytes().to_vec());
242 Ok(())
243}
244
245/// The same bytes vanishing once and appearing twice is an ambiguity, and the
246/// capture does not guess: every site stays the splice the diff found.
247#[test]
248fn ambiguous_duplicate_content_falls_back_to_delete_plus_insert() -> Outcome<()> {
249 let scratch = res!(Scratch::new("move_ambig"));
250 let root = res!(scratch.sub("work"));
251 res!(res!(ore(&root, &["init"])).good("init"));
252 res!(write(&root, "f1.rs", fmt!("{}{}", UTIL_TOP, BLOCK).as_bytes()));
253 res!(write(&root, "f2.rs", b"const ALPHA: u8 = 1;\n"));
254 res!(write(&root, "f3.rs", b"const BETA: u8 = 2;\n"));
255 res!(res!(ore(&root, &["mark", "base"])).good("mark base"));
256
257 // One removal, two arrivals: no pairing is safe, so none is made.
258 res!(write(&root, "f1.rs", UTIL_TOP.as_bytes()));
259 res!(write(&root, "f2.rs", fmt!("const ALPHA: u8 = 1;\n\n{}", BLOCK).as_bytes()));
260 res!(write(&root, "f3.rs", fmt!("const BETA: u8 = 2;\n\n{}", BLOCK).as_bytes()));
261 let text = fmt!("{}", res!(res!(ore(&root, &["mark", "split"])).good("mark split")));
262 assert!(!text.contains("moved as a block"),
263 "one deletion and two insertions is not a move: {}", text);
264 assert_eq!(moves_in(&res!(ops_in(&root))), 0);
265
266 // Two removals, one arrival: the same rule, in the other direction.
267 res!(write(&root, "f1.rs", fmt!("{}{}", UTIL_TOP, BLOCK).as_bytes()));
268 res!(write(&root, "f2.rs", b"const ALPHA: u8 = 1;\n"));
269 res!(write(&root, "f3.rs", b"const BETA: u8 = 2;\n"));
270 let text = fmt!("{}", res!(res!(ore(&root, &["mark", "gathered"])).good("mark gathered")));
271 assert!(!text.contains("moved as a block"),
272 "two deletions and one insertion is not a move either: {}", text);
273 assert_eq!(moves_in(&res!(ops_in(&root))), 0);
274
275 // And the fallback is correct, if unflagged: the tree renders as the disk.
276 let out = res!(ore(&root, &["flags"]));
277 let text = fmt!("{}", res!(out.good("flags")));
278 assert!(text.contains("captured nothing"), "the fallback still converges: {}", text);
279 Ok(())
280}
281
282/// A fragment below the threshold is not paired, because at that size exact
283/// equality stops being evidence of a move.
284#[test]
285fn a_fragment_below_the_threshold_stays_a_delete_plus_insert() -> Outcome<()> {
286 let scratch = res!(Scratch::new("move_small"));
287 let root = res!(scratch.sub("work"));
288 res!(res!(ore(&root, &["init"])).good("init"));
289 // Well under MIN_MOVE_LEN's 64 bytes.
290 let frag = "const SPAN: usize = 40;\n";
291 res!(write(&root, "f1.rs", fmt!("{}{}", UTIL_TOP, frag).as_bytes()));
292 res!(write(&root, "f2.rs", LIB.as_bytes()));
293 res!(res!(ore(&root, &["mark", "base"])).good("mark base"));
294
295 res!(write(&root, "f1.rs", UTIL_TOP.as_bytes()));
296 res!(write(&root, "f2.rs", fmt!("{}{}", LIB, frag).as_bytes()));
297 let text = fmt!("{}", res!(res!(ore(&root, &["mark", "shifted"])).good("mark shifted")));
298 assert!(!text.contains("moved as a block"),
299 "a {}-byte fragment is below the threshold: {}", frag.len(), text);
300 assert_eq!(moves_in(&res!(ops_in(&root))), 0);
301 Ok(())
302}
303
304/// A block moved and edited in the same capture degrades to delete-plus-insert,
305/// which is what exact-match-only pairing costs and is accepted on purpose:
306/// pairing nearly-equal regions would be guessing which bytes the author meant
307/// to keep. The trade is documented at `MIN_MOVE_LEN` and in the capture
308/// module's rules.
309#[test]
310fn a_block_moved_and_edited_in_one_capture_degrades_to_delete_plus_insert() -> Outcome<()> {
311 let scratch = res!(Scratch::new("move_edited"));
312 let root = res!(scratch.sub("work"));
313 res!(res!(ore(&root, &["init"])).good("init"));
314 res!(write(&root, "util.rs", fmt!("{}{}", UTIL_TOP, BLOCK).as_bytes()));
315 res!(write(&root, "lib.rs", LIB.as_bytes()));
316 res!(res!(ore(&root, &["mark", "base"])).good("mark base"));
317
318 // The refactor a person actually makes: move the function and touch it up
319 // on the way. The removed bytes and the inserted bytes are no longer equal,
320 // so nothing is paired.
321 res!(write(&root, "util.rs", UTIL_TOP.as_bytes()));
322 res!(write(&root, "lib.rs", fmt!("{}{}", LIB, edited_block()).as_bytes()));
323 let text = fmt!("{}", res!(res!(ore(&root, &["mark", "reworked"])).good("mark reworked")));
324 assert!(!text.contains("moved as a block"),
325 "a moved-and-edited block is not an exact match: {}", text);
326 assert_eq!(moves_in(&res!(ops_in(&root))), 0,
327 "it is recorded as the deletion and insertion it literally was");
328
329 // Which still converges to the right bytes; what is lost is only the
330 // anchoring a true move would have kept.
331 let out = res!(ore(&root, &["flags"]));
332 let text = fmt!("{}", res!(out.good("flags")));
333 assert!(text.contains("captured nothing"), "the fallback is correct: {}", text);
334 Ok(())
335}