oxedyne/fe2o3 — fe2o3_ore/src/diff.rs

62.8 KiB, 278 runs

created by r1870400018:18774, 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	//! What has to be done to one version of a file's bytes to obtain another.
2	//!
3	//! The operation vocabulary records intent, and an author working in an editor
4	//! supplies it directly. An author working in a filesystem does not: what is
5	//! available is the file as it stood and the file as it now stands, and the
6	//! edit between them has to be recovered. That recovery is this module, and it
7	//! is the one place in the crate where a diff is a guess rather than a record.
8	//!
9	//! # Division of labour
10	//!
11	//! The splices returned here are positional, and every position is an
12	//! offset into the old bytes. That is deliberate. Content anchors are minted
13	//! from a render, and the module that holds the render --
14	//! [`crate::seq::render::Rendered`] -- already knows how to turn an offset into
15	//! the names of the bytes around it. So the split is:
16	//!
17	//! - here: old bytes and new bytes in, an ordered list of positional splices
18	//! out, with no knowledge of operation identifiers, anchors or history;
19	//! - the caller: for each splice in turn, `rendered.splice(at, delete, insert)`,
20	//! which resolves the offsets against the render and yields a content
21	//! anchored [`crate::op::Op`].
22	//!
23	//! Because every offset is in the old bytes, and the render the caller holds is
24	//! the old bytes, the whole list is resolved against that one render. The
25	//! splices are ascending and non-overlapping, and consecutive splices are
26	//! separated by at least [`MIN_SPLICE_GAP`] unchanged bytes, so no splice
27	//! anchors itself on content another one removes.
28	//!
29	//! # How the diff is found
30	//!
31	//! Two levels, over pieces and then over bytes.
32	//!
33	//! Pieces first. The bytes are cut into pieces, each distinct piece is given
34	//! a number, and Myers' O(ND) algorithm runs over the numbers. This is what keeps
35	//! a large file affordable, since the sequences it compares are as long as the
36	//! file has pieces rather than bytes, and the cost is driven by the size of the
37	//! difference rather than the size of the file.
38	//!
39	//! Bytes second. Each run of changed pieces is trimmed of the bytes its two
40	//! sides share at either end, and, where what remains is small, Myers runs again
41	//! over those bytes. A one character change in the middle of a line therefore
42	//! stores one character, not the line and not the file.
43	//!
44	//! # Where the pieces come from
45	//!
46	//! There are two ways of cutting, and which is used is [`Route`].
47	//!
48	//! For text, a piece is a line: the bytes are cut at every `\n`. That is the
49	//! right unit for anything a person edits a line at a time, and it costs one pass
50	//! to find.
51	//!
52	//! For everything else, a piece is a content-defined chunk. A gear rolling
53	//! hash reads the bytes, and a boundary is declared wherever the hash of the last
54	//! few dozen bytes hits a mask, so a boundary follows the content rather than an
55	//! offset: an edit perturbs only the chunks around it, and every chunk beyond the
56	//! disturbance re-synchronises on the same bytes and keeps the number it had.
57	//! That is what makes a small edit to a large binary cost the region it touched
58	//! rather than everything between the first edit and the last. Boundaries are
59	//! held between [`MIN_CHUNK`] and [`MAX_CHUNK`] and steered towards [`AVG_CHUNK`]
60	//! by normalised chunking, all three tuned well below what a storage layer would
61	//! use: a diff wants to localise an edit to a few kilobytes, not to a quarter of
62	//! a megabyte.
63	//!
64	//! The route is chosen by asking whether the line pass has anything to work with.
65	//! Content whose average line is longer than [`MAX_TEXT_LINE`] is one long line as
66	//! far as that pass is concerned, and where such content is also longer than
67	//! [`MIN_CHUNKED_LEN`] the line pass is skipped and the chunk pass runs instead.
68	//! Below that length nothing is chunked, because a single splice over so few bytes
69	//! costs less than the operations that would replace it.
70	//!
71	//! # The bound on cost
72	//!
73	//! Myers costs O(ND) in time and, as written here, O(D²) in memory, where D is
74	//! the length of the edit script. Both are fine while D is small and neither is
75	//! acceptable when it is not, so D is capped at [`MAX_PIECE_SCRIPT`] insertions
76	//! and deletions over pieces, and [`MAX_BYTE_SCRIPT`] within a refined run. A
77	//! piece script that would exceed its cap means the two versions have little left
78	//! in common. The line pass then hands over to the chunk pass where the content is
79	//! long enough to chunk, and beyond that the answer falls back to a single splice
80	//! covering everything between the shared prefix and the shared suffix -- which is
81	//! the whole of what a diff-free frontend would have recorded anyway, arrived at
82	//! in linear time. The cap on the piece script bounds the working memory at
83	//! roughly four megabytes.
84	//!
85	//! # Bytes, not text
86	//!
87	//! Nothing here decodes. A piece is compared to another by its bytes, so an
88	//! encoding this module has never heard of costs it nothing, and no route is
89	//! chosen by guessing what the content is: the question asked is only whether the
90	//! newlines are frequent enough to cut on, which is a fact about the bytes.
91	//!
92	//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
93	//! Anthropic Claude
94
95	use oxedyne_fe2o3_core::prelude::*;
96
97	use std::collections::HashMap;
98	use std::ops::Range;
99
100
101	// Greatest piece level edit script the diff will compute on one route before
102	// handing on to the next. A piece is a line on one route and a content-defined
103	// chunk on the other, and the cap is the same for both: what it bounds is the
104	// working memory of the Myers pass, which does not care what it is comparing.
105	pub const MAX_PIECE_SCRIPT: usize = 1024;
106
107	// Greatest byte level edit script the refinement of one changed run will
108	// compute before leaving the run as a single splice.
109	pub const MAX_BYTE_SCRIPT: usize = 256;
110
111	// Greatest changed run, in bytes on either side, the byte level refinement is
112	// attempted on at all.
113	pub const MAX_REFINE_LEN: usize = 4096;
114
115	// Fewest unchanged bytes that may separate two splices. Two operations each
116	// carry their own identity, parents and origins, which costs more than a
117	// handful of bytes that did not change; splices closer together than this are
118	// merged into one. Keeping the gap non-zero is also what stops one splice
119	// anchoring on content that another removes.
120	pub const MIN_SPLICE_GAP: usize = 16;
121
122	// A floor stops a run of unlucky hash hits producing a swarm of tiny pieces,
123	// each of which costs an entry in the sequence Myers runs over.
124	pub const MIN_CHUNK: usize = 2 * 1024;
125
126	// The granularity at which an edit is localised before the byte level
127	// refinement narrows it further, so it is the bound on what a diff re-stores
128	// when the refinement declines. A storage layer chunks an order of magnitude
129	// larger, because its cost is one address per chunk in every manifest; here the
130	// cost is one integer per chunk in one comparison, which buys the finer cut.
131	pub const AVG_CHUNK: usize = 8 * 1024;
132
133	// A ceiling bounds the damage where the hash finds no boundary at all, which is
134	// what a long run of identical bytes does to it.
135	pub const MAX_CHUNK: usize = 64 * 1024;
136
137	// Shortest input the chunk route is used on. Below this a single splice
138	// covering everything between the shared prefix and the shared suffix stores at
139	// most sixteen kilobytes, which is of the same order as the operations that
140	// would replace it, so there is nothing to win.
141	pub const MIN_CHUNKED_LEN: usize = 16 * 1024;
142
143	// Longest average line at which the line route is still worth taking. Above it
144	// the newlines are too sparse to cut on: the pieces are so long that a changed
145	// piece is most of the file, which is the trimmed splice with extra steps.
146	pub const MAX_TEXT_LINE: usize = 1024;
147
148	// Seed for the gear table's generator. The table has to be the same in every
149	// build, because a changed table changes every boundary and so which bytes a
150	// diff decides to re-store. Nothing here is content-addressed, so a changed
151	// table would cost efficiency rather than correctness -- the applier checks the
152	// answer either way -- but a diff that depends on which binary produced it is
153	// not a diff anyone can reason about. Fixing the seed here, and deriving the
154	// table from it rather than shipping a literal, is what pins it. The value is
155	// the golden-ratio constant splitmix64 conventionally uses.
156	const GEAR_SEED: u64 = 0x9e37_79b9_7f4a_7c15;
157
158	// Normalisation level: how many bits the mask tightens below the average chunk
159	// size and loosens above it. Plain gear chunking gives an exponential spread of
160	// chunk sizes, so short chunks dominate and the tail is long. Cutting less
161	// readily before the average and more readily after it pulls the spread in
162	// towards the average without forcing boundaries at fixed offsets. Two is the
163	// level the FastCDC paper settles on.
164	const NORM_LEVEL: u32 = 2;
165
166	// The 256-entry gear table, one pseudorandom `u64` per byte value, generated at
167	// compile time from `GEAR_SEED` by splitmix64 so there is no dependency to pull
168	// in and no table to keep in the source.
169	static GEAR: [u64; 256] = gear_table();
170
171	// The masks a boundary must hit: the stricter below the average chunk size, the
172	// looser at and above it.
173	const MASK_S: u64 = high_mask(log2_floor(AVG_CHUNK) + NORM_LEVEL);
174	const MASK_L: u64 = high_mask(log2_floor(AVG_CHUNK) - NORM_LEVEL);
175
176
177	/// Which of the routes through the diff was taken.
178	///
179	/// Returned by [`diff_routed`] so that a caller measuring what a diff cost, or a
180	/// test asserting which pass ran, does not have to infer it from the shape of the
181	/// answer.
182	#[derive(Clone, Copy, Debug, Eq, PartialEq)]
183	pub enum Route {
184	Same, // the two versions are the same bytes and there is nothing to do
185	Line, // pieces cut at the newlines, then bytes within each changed run
186	Chunk, // pieces cut where a gear hash says the content changes, then bytes
187	Whole, // between the shared prefix and the shared suffix, where both give up
188	}
189
190	impl Route {
191	pub fn name(&self) -> &'static str {
192	match self {
193	Self::Same => "Same",
194	Self::Line => "Line",
195	Self::Chunk => "Chunk",
196	Self::Whole => "Whole",
197	}
198	}
199	}
200
201
202	/// One positional edit against the old bytes: remove `delete` bytes at `at`,
203	/// and put `insert` in their place.
204	///
205	/// The three fields are independent -- any offset, any length and any payload
206	/// name an edit, even where the file cannot supply them -- so there is no
207	/// invariant here for a struct literal to break. What the offsets have to agree
208	/// with is the file, and [`apply`] is what says whether they do.
209	#[derive(Clone, Debug, Default, Eq, PartialEq)]
210	pub struct Splice {
211	pub at: usize,
212	pub delete: usize,
213	pub insert: Vec<u8>,
214	}
215
216	impl Splice {
217	pub fn insert_len(&self) -> usize {
218	self.insert.len()
219	}
220	}
221
222
223	/// The list is ascending by offset and non-overlapping, and is empty when the
224	/// two are already the same.
225	pub fn diff(old: &[u8], new: &[u8]) -> Vec<Splice> {
226	diff_with_budget(old, new, MAX_PIECE_SCRIPT)
227	}
228
229	/// As [`diff`], with the piece level edit script capped at `budget` rather than
230	/// at [`MAX_PIECE_SCRIPT`].
231	///
232	/// A budget of zero forces the single trimmed splice: no piece route can produce
233	/// a script of no steps for two versions that differ, so both give up and the
234	/// fallback is what is left.
235	pub fn diff_with_budget(old: &[u8], new: &[u8], budget: usize) -> Vec<Splice> {
236	diff_routed(old, new, budget).0
237	}
238
239	/// The routes are tried in the order the content deserves. Where the newlines
240	/// are frequent enough to cut on, lines are tried first, because a line is the
241	/// unit an author edits in and cutting there gives the finest changed runs. Where
242	/// they are not, and the content is long enough for it to be worth the pass,
243	/// content-defined chunks are tried instead, and are tried anyway when the line
244	/// route exhausts its budget. What is left is the single trimmed splice.
245	pub fn diff_routed(old: &[u8], new: &[u8], budget: usize)
246	-> (Vec<Splice>, Route)
247	{
248	if old == new {
249	return (Vec::new(), Route::Same);
250	}
251	let old_lines = line_starts(old);
252	let new_lines = line_starts(new);
253	// Long enough that chunking has room to localise an edit within it.
254	let chunkable = old.len().max(new.len()) >= MIN_CHUNKED_LEN;
255	// The line route is skipped only where it has nothing to work with and
256	// there is a chunk route to skip it in favour of.
257	let texty = texty(old, &old_lines) && texty(new, &new_lines);
258	if texty \|\| !chunkable {
259	if let Some(sp) = diff_over(old, new, &old_lines, &new_lines, budget) {
260	return (sp, Route::Line);
261	}
262	}
263	if chunkable {
264	let old_chunks = chunk_starts(old);
265	let new_chunks = chunk_starts(new);
266	if let Some(sp) = diff_over(old, new, &old_chunks, &new_chunks, budget) {
267	return (sp, Route::Chunk);
268	}
269	}
270	(vec![trimmed_splice(old, new)], Route::Whole)
271	}
272
273	/// Fails where the list is not ascending, where two splices overlap, or where
274	/// one reaches past the end of the file: all three mean the list was not
275	/// produced against these bytes, and a caller had better hear so rather than
276	/// receive a plausible wrong answer.
277	pub fn apply(old: &[u8], splices: &[Splice])
278	-> Outcome<Vec<u8>>
279	{
280	let mut out: Vec<u8> = Vec::with_capacity(old.len());
281	let mut at = 0usize;
282	for (i, sp) in splices.iter().enumerate() {
283	if sp.at < at {
284	return Err(err!(
285	"Splice {} begins at {}, behind the {} bytes of the old file already \
286	consumed; splices must ascend and may not overlap.", i, sp.at, at;
287	Invalid, Input, Order));
288	}
289	let end = match sp.at.checked_add(sp.delete) {
290	Some(e) if e <= old.len() => e,
291	_ => return Err(err!(
292	"Splice {} removes {} bytes at {}, reaching past the {} bytes the old \
293	file holds.", i, sp.delete, sp.at, old.len();
294	Invalid, Input, Range)),
295	};
296	out.extend_from_slice(&old[at..sp.at]);
297	out.extend_from_slice(&sp.insert);
298	at = end;
299	}
300	out.extend_from_slice(&old[at..]);
301	Ok(out)
302	}
303
304
305	// ┌───────────────────────────────────────────────────────────────┐
306	// │ Stored patches │
307	// └───────────────────────────────────────────────────────────────┘
308	//
309	// A splice list is only worth storing if the bytes it was made against can be
310	// named again months later. `apply` refuses a list that is structurally
311	// impossible against the bytes in hand -- one that overlaps itself, or reaches
312	// past the end -- and that is as far as offsets alone can go: a list made
313	// against a DIFFERENT old file of a compatible shape applies perfectly well and
314	// returns something nobody wrote. So a stored patch carries the length and the
315	// checksum of both sides, and the reader is told which side is wrong rather
316	// than handed a plausible answer.
317
318	// Leading bytes of a stored patch, so a reader given some other file says so
319	// instead of decoding whatever it was given.
320	pub const PATCH_MAGIC: [u8; 4] = *b"ORDF";
321
322	// The only layout understood here. A later one takes the next number, and a
323	// reader that does not know a number refuses rather than guesses at it.
324	pub const PATCH_FORMAT: u32 = 1;
325
326	// Magic, format, the two lengths, the two checksums and the splice count.
327	pub const PATCH_HEADER: usize = 28;
328
329	// Offset, deletion count and insertion length, ahead of the inserted bytes.
330	const SPLICE_HEADER: usize = 12;
331
332
333	/// The splices from `old` to `new`, encoded as bytes that carry what they were
334	/// made against.
335	///
336	/// **What comes back has already been decoded and applied again, and the result
337	/// compared with `new`.** Nothing else here can promise that. `diff` is a guess
338	/// by construction, and `apply` sees only whether a list fits the bytes it is
339	/// given, so a caller who stores a patch and reads it back a year later has
340	/// nobody to appeal to. One `apply` at record time is what turns a silent
341	/// reconstruction failure into a refusal at the one moment the correct bytes
342	/// are still in hand -- and it runs over the ENCODED form, through the same
343	/// door a reader comes in by, so an encoder fault is caught here too.
344	pub fn make_patch(old: &[u8], new: &[u8])
345	-> Outcome<Vec<u8>>
346	{
347	if old.len() > u32::MAX as usize \|\| new.len() > u32::MAX as usize {
348	return Err(err!(
349	"A patch addresses its bytes with 32 bit offsets, so neither side may be \
350	longer than {} bytes; the old side is {} and the new side {}.",
351	u32::MAX, old.len(), new.len(); Invalid, Input, Size));
352	}
353	let splices = diff(old, new);
354	let patch = encode_patch(old, new, &splices);
355	let back = res!(apply_patch(old, &patch), Invalid, Data);
356	if back != new {
357	return Err(err!(
358	"A patch from {} bytes to {} reconstructed {} bytes that are not them, so it \
359	is refused rather than stored.", old.len(), new.len(), back.len();
360	Invalid, Data, Mismatch));
361	}
362	Ok(patch)
363	}
364
365	/// The bytes a patch was made towards, given the bytes it was made from.
366	///
367	/// Four things are checked before a single splice is applied: that this is a
368	/// patch at all, that its layout is one this build knows, and that `old` is the
369	/// length and the checksum the patch was made against. The last is what stops a
370	/// patch recorded against a different parent from returning a wrong file
371	/// quietly; the checksum of the result is then confirmed as well, which catches
372	/// a patch whose own bytes have decayed on disk.
373	pub fn apply_patch(old: &[u8], patch: &[u8])
374	-> Outcome<Vec<u8>>
375	{
376	if patch.len() < PATCH_HEADER {
377	return Err(err!(
378	"A patch is at least {} bytes of header; this one is {}.",
379	PATCH_HEADER, patch.len(); Invalid, Input, Decode));
380	}
381	if patch[0..4] != PATCH_MAGIC {
382	return Err(err!(
383	"These {} bytes do not begin with a patch's mark {:?}, so they are some other \
384	file.", patch.len(), PATCH_MAGIC; Invalid, Input, Decode));
385	}
386	let format = u32_at(patch, 4);
387	if format != PATCH_FORMAT {
388	return Err(err!(
389	"This patch is written in format {}, and this build reads format {}.",
390	format, PATCH_FORMAT; Invalid, Input, Decode));
391	}
392	let old_len = u32_at(patch, 8) as usize;
393	let old_sum = u32_at(patch, 12);
394	let new_len = u32_at(patch, 16) as usize;
395	let new_sum = u32_at(patch, 20);
396	let count = u32_at(patch, 24) as usize;
397	if old.len() != old_len {
398	return Err(err!(
399	"This patch was made against {} bytes and has been given {}, so it is not this \
400	file's patch.", old_len, old.len(); Invalid, Input, Mismatch));
401	}
402	let sum = checksum(old);
403	if sum != old_sum {
404	return Err(err!(
405	"This patch was made against bytes checksumming {:08x}, and the {} bytes given \
406	checksum {:08x}, so it is not this file's patch.", old_sum, old.len(), sum;
407	Invalid, Input, Checksum));
408	}
409	let splices = res!(decode_splices(patch, count));
410	let out = res!(apply(old, &splices));
411	if out.len() != new_len {
412	return Err(err!(
413	"This patch says it makes {} bytes and made {}.", new_len, out.len();
414	Invalid, Data, Mismatch));
415	}
416	let sum = checksum(&out);
417	if sum != new_sum {
418	return Err(err!(
419	"This patch says it makes bytes checksumming {:08x} and made {} bytes \
420	checksumming {:08x}.", new_sum, out.len(), sum; Invalid, Data, Checksum));
421	}
422	Ok(out)
423	}
424
425	/// The length of the bytes a patch was made from, and of the bytes it makes,
426	/// read from its header without applying it.
427	///
428	/// For a caller weighing a patch against a full copy before it has either file
429	/// in hand.
430	pub fn patch_lengths(patch: &[u8])
431	-> Outcome<(usize, usize)>
432	{
433	if patch.len() < PATCH_HEADER \|\| patch[0..4] != PATCH_MAGIC {
434	return Err(err!(
435	"These {} bytes are not a patch.", patch.len(); Invalid, Input, Decode));
436	}
437	Ok((u32_at(patch, 8) as usize, u32_at(patch, 16) as usize))
438	}
439
440	fn encode_patch(old: &[u8], new: &[u8], splices: &[Splice])
441	-> Vec<u8>
442	{
443	let body: usize = splices.iter().map(\|s\| SPLICE_HEADER + s.insert.len()).sum();
444	let mut out = Vec::with_capacity(PATCH_HEADER + body);
445	out.extend_from_slice(&PATCH_MAGIC);
446	out.extend_from_slice(&PATCH_FORMAT.to_le_bytes());
447	out.extend_from_slice(&(old.len() as u32).to_le_bytes());
448	out.extend_from_slice(&checksum(old).to_le_bytes());
449	out.extend_from_slice(&(new.len() as u32).to_le_bytes());
450	out.extend_from_slice(&checksum(new).to_le_bytes());
451	out.extend_from_slice(&(splices.len() as u32).to_le_bytes());
452	for sp in splices {
453	out.extend_from_slice(&(sp.at as u32).to_le_bytes());
454	out.extend_from_slice(&(sp.delete as u32).to_le_bytes());
455	out.extend_from_slice(&(sp.insert.len() as u32).to_le_bytes());
456	out.extend_from_slice(&sp.insert);
457	}
458	out
459	}
460
461	/// Every length is read before it is trusted, so a truncated or corrupted patch
462	/// is a refusal rather than a panic on a slice.
463	fn decode_splices(patch: &[u8], count: usize)
464	-> Outcome<Vec<Splice>>
465	{
466	let mut out = Vec::with_capacity(count.min(1024));
467	let mut at = PATCH_HEADER;
468	for i in 0..count {
469	if at + SPLICE_HEADER > patch.len() {
470	return Err(err!(
471	"Splice {} of {} begins at byte {} of a patch {} bytes long, so the patch is \
472	truncated.", i, count, at, patch.len(); Invalid, Input, Decode));
473	}
474	let off = u32_at(patch, at) as usize;
475	let del = u32_at(patch, at + 4) as usize;
476	let ins = u32_at(patch, at + 8) as usize;
477	at += SPLICE_HEADER;
478	let end = match at.checked_add(ins) {
479	Some(e) if e <= patch.len() => e,
480	_ => return Err(err!(
481	"Splice {} of {} inserts {} bytes from byte {} of a patch {} bytes long, so \
482	the patch is truncated.", i, count, ins, at, patch.len();
483	Invalid, Input, Decode)),
484	};
485	out.push(Splice { at: off, delete: del, insert: patch[at..end].to_vec() });
486	at = end;
487	}
488	if at != patch.len() {
489	return Err(err!(
490	"A patch of {} splices ends at byte {} of {}, so it carries {} bytes nothing \
491	accounts for.", count, at, patch.len(), patch.len() - at; Invalid, Input, Decode));
492	}
493	Ok(out)
494	}
495
496	/// CRC-32, from the one already in the dependency graph for the deflate the
497	/// packed record kind uses. It is here to catch a patch meeting bytes it was not
498	/// made against and a patch that has decayed on disk, neither of which is an
499	/// adversary, and a second hash implementation would be two to keep in step.
500	fn checksum(buf: &[u8]) -> u32 {
501	let mut crc = flate2::Crc::new();
502	crc.update(buf);
503	crc.sum()
504	}
505
506	fn u32_at(buf: &[u8], at: usize) -> u32 {
507	u32::from_le_bytes([buf[at], buf[at + 1], buf[at + 2], buf[at + 3]])
508	}
509
510
511
512
513	fn common_prefix(a: &[u8], b: &[u8]) -> usize {
514	let limit = a.len().min(b.len());
515	let mut n = 0;
516	while n < limit && a[n] == b[n] {
517	n += 1;
518	}
519	n
520	}
521
522	/// The `floor` bytes already accounted for at the front are never run back past.
523	fn common_suffix(a: &[u8], b: &[u8], floor: usize) -> usize {
524	let limit = (a.len() - floor).min(b.len() - floor);
525	let mut n = 0;
526	while n < limit && a[a.len() - 1 - n] == b[b.len() - 1 - n] {
527	n += 1;
528	}
529	n
530	}
531
532	/// The single splice covering everything between the shared prefix and the
533	/// shared suffix, which is what a frontend with no diff at all records.
534	fn trimmed_splice(old: &[u8], new: &[u8]) -> Splice {
535	let front = common_prefix(old, new);
536	let back = common_suffix(old, new, front);
537	Splice {
538	at: front,
539	delete: old.len() - front - back,
540	insert: new[front..new.len() - back].to_vec().into(),
541	}
542	}
543
544	/// Runs one piece level pass and the byte level refinement beneath it, or gives
545	/// `None` where the edit script over the pieces would exceed `budget`.
546	///
547	/// Both routes are this function with different cut points, which is the whole of
548	/// what separates them: what a piece is changes, and nothing else does.
549	fn diff_over(
550	old: &[u8],
551	new: &[u8],
552	old_starts: &[usize],
553	new_starts: &[usize],
554	budget: usize,
555	)
556	-> Option<Vec<Splice>>
557	{
558	let mut names: HashMap<&[u8], u32> = HashMap::new();
559	let old_ids = piece_ids(old, old_starts, &mut names);
560	let new_ids = piece_ids(new, new_starts, &mut names);
561	let changes = match changed_runs(&old_ids, &new_ids, budget) {
562	Some(c) => c,
563	None => return None,
564	};
565	let mut out: Vec<Splice> = Vec::with_capacity(changes.len());
566	for c in &changes {
567	refine(
568	old,
569	new,
570	old_starts[c.a.start]..old_starts[c.a.end],
571	new_starts[c.b.start]..new_starts[c.b.end],
572	&mut out,
573	);
574	}
575	coalesce(old, &mut out);
576	Some(out)
577	}
578
579	/// Are the newlines frequent enough for the line route to have anything to cut
580	/// on?
581	///
582	/// An empty side is no obstacle: it has no lines, and it is the other side that
583	/// decides. A side of one line has nothing for the pass to match against, and a
584	/// side whose lines average more than [`MAX_TEXT_LINE`] bytes has pieces so
585	/// coarse that a changed piece is most of the file.
586	fn texty(bytes: &[u8], starts: &[usize]) -> bool {
587	if bytes.is_empty() {
588	return true;
589	}
590	let lines = starts.len() - 1;
591	if lines < 2 {
592	return false;
593	}
594	bytes.len() / lines <= MAX_TEXT_LINE
595	}
596
597	/// Returns the offset at which each line begins, with the length of the input
598	/// as a final entry, so that line `i` occupies `starts[i]..starts[i + 1]`.
599	///
600	/// A line carries its own terminating newline. A file whose last line has none
601	/// still ends in a line, and an empty file has no lines at all.
602	fn line_starts(bytes: &[u8]) -> Vec<usize> {
603	let mut starts = vec![0usize];
604	for (i, b) in bytes.iter().enumerate() {
605	if *b == b'\n' {
606	starts.push(i + 1);
607	}
608	}
609	if starts[starts.len() - 1] != bytes.len() {
610	starts.push(bytes.len());
611	}
612	starts
613	}
614
615	/// Returns the offset at which each content-defined chunk begins, under the same
616	/// contract [`line_starts`] keeps: the length of the input is the final entry,
617	/// and an empty input has no chunks.
618	fn chunk_starts(bytes: &[u8]) -> Vec<usize> {
619	let mut starts = vec![0usize];
620	let mut at = 0usize;
621	while at < bytes.len() {
622	at += cut(&bytes[at..]);
623	starts.push(at);
624	}
625	starts
626	}
627
628	/// Returns the length of the first chunk of `data`, always at least one byte so
629	/// that [`chunk_starts`] terminates.
630	///
631	/// The gear hash reads one byte at a time, keeping a value that depends only on
632	/// the last few dozen bytes, and a boundary is declared where that value hits the
633	/// mask. The bytes before [`MIN_CHUNK`] are not hashed at all, no boundary being
634	/// acceptable there, which is the cut-point skipping that makes the scan cheap.
635	/// The mask is the stricter of the two below [`AVG_CHUNK`] and the looser at and
636	/// above it, which pulls the spread of chunk sizes in towards the average.
637	fn cut(data: &[u8]) -> usize {
638	let n = data.len();
639	if n <= MIN_CHUNK {
640	return n; // too short to cut: the whole remainder is one chunk
641	}
642	let end = MAX_CHUNK.min(n); // forced boundary
643	let mid = AVG_CHUNK.min(end); // where the mask loosens
644	let mut fp = 0u64; // the rolling gear hash
645	let mut i = MIN_CHUNK; // skip: no boundary may land below
646	while i < mid {
647	fp = (fp << 1).wrapping_add(GEAR[data[i] as usize]);
648	if fp & MASK_S == 0 {
649	return i + 1;
650	}
651	i += 1;
652	}
653	while i < end {
654	fp = (fp << 1).wrapping_add(GEAR[data[i] as usize]);
655	if fp & MASK_L == 0 {
656	return i + 1;
657	}
658	i += 1;
659	}
660	end
661	}
662
663	/// Splitmix64 is a handful of multiplies and shifts, which is why it can run in
664	/// a `const` context and save the crate a dependency and a 2 KiB literal.
665	const fn gear_table() -> [u64; 256] {
666	let mut table = [0u64; 256];
667	let mut state = GEAR_SEED;
668	let mut i = 0;
669	while i < 256 {
670	state = state.wrapping_add(GEAR_SEED);
671	let mut z = state;
672	z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
673	z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
674	table[i] = z ^ (z >> 31);
675	i += 1;
676	}
677	table
678	}
679
680	/// Builds a mask over the top `bits` bits of a `u64`, for `1 <= bits <= 63`.
681	///
682	/// The top bits are the ones to test. A gear hash shifts left by one per byte,
683	/// so bit `k` of the hash depends on the last `k + 1` bytes; testing the high
684	/// bits therefore tests a window dozens of bytes wide, while testing the low bits
685	/// would decide a boundary on almost nothing.
686	const fn high_mask(bits: u32) -> u64 {
687	((1u64 << bits) - 1) << (64 - bits)
688	}
689
690	/// Floor of the base-2 logarithm of a non-zero value.
691	const fn log2_floor(n: usize) -> u32 {
692	(usize::BITS - 1) - n.leading_zeros()
693	}
694
695	/// Numbers the pieces, giving equal pieces equal numbers across both files.
696	///
697	/// The numbering is what the piece level pass compares, so that a comparison
698	/// costs one integer rather than the length of a piece. Equality is over the
699	/// bytes themselves rather than over a digest of them, so two pieces that differ
700	/// can never be given one number and no route can be led into a wrong answer by
701	/// a collision.
702	fn piece_ids<'a>(bytes: &'a [u8], starts: &[usize], names: &mut HashMap<&'a [u8], u32>)
703	-> Vec<u32>
704	{
705	let mut out = Vec::with_capacity(starts.len() - 1);
706	for w in starts.windows(2) {
707	let next = names.len() as u32;
708	out.push(*names.entry(&bytes[w[0]..w[1]]).or_insert(next));
709	}
710	out
711	}
712
713
714	/// A run of `a` that has become a run of `b`. At least one of the two is
715	/// non-empty.
716	#[derive(Clone, Debug, Eq, PartialEq)]
717	struct Change {
718	a: Range<usize>, // what the run was, in the old sequence
719	b: Range<usize>, // what it has become, in the new sequence
720	}
721
722
723	/// Returns the changed runs turning `a` into `b`, or `None` where the edit
724	/// script would exceed `budget`.
725	///
726	/// The shared head and tail are taken off first, since neither costs anything
727	/// to find and both shrink what Myers is asked to do.
728	fn changed_runs<T: PartialEq>(a: &[T], b: &[T], budget: usize)
729	-> Option<Vec<Change>>
730	{
731	let limit = a.len().min(b.len());
732	let mut head = 0;
733	while head < limit && a[head] == b[head] {
734	head += 1;
735	}
736	let mut tail = 0;
737	while tail < limit - head
738	&& a[a.len() - 1 - tail] == b[b.len() - 1 - tail]
739	{
740	tail += 1;
741	}
742	let (an, bn) = (a.len() - tail, b.len() - tail);
743	if head == an && head == bn {
744	return Some(Vec::new());
745	}
746	// Where one side has nothing left, every remaining element of the other is
747	// the whole of the change and Myers has nothing to decide.
748	if head == an \|\| head == bn {
749	return Some(vec![Change { a: head..an, b: head..bn }]);
750	}
751	let matched = match myers(&a[head..an], &b[head..bn], budget) {
752	Some(m) => m,
753	None => return None,
754	};
755	Some(runs_between(&matched, an - head, bn - head, head))
756	}
757
758	fn runs_between(matched: &[(usize, usize)], n: usize, m: usize, off: usize)
759	-> Vec<Change>
760	{
761	let mut out: Vec<Change> = Vec::new();
762	let (mut i, mut j) = (0usize, 0usize);
763	for (mi, mj) in matched {
764	if mi > i \|\| mj > j {
765	out.push(Change {
766	a: off + i..off + mi,
767	b: off + j..off + mj,
768	});
769	}
770	i = mi + 1;
771	j = mj + 1;
772	}
773	if i < n \|\| j < m {
774	out.push(Change {
775	a: off + i..off + n,
776	b: off + j..off + m,
777	});
778	}
779	out
780	}
781
782	/// Returns the pairs of positions a shortest edit script leaves matched,
783	/// ascending, or `None` where that script would be longer than `budget`.
784	///
785	/// This is Myers' greedy algorithm: for each script length `d` in turn, the
786	/// furthest point reachable on each diagonal is extended along whatever run of
787	/// equal elements follows it, and the first `d` that reaches the far corner is
788	/// the length of a shortest script. Keeping the furthest points of every `d`
789	/// makes the path itself recoverable by walking back through them, which is
790	/// where the matched pairs come from, and is also what costs O(D²) memory and
791	/// so what the budget is bounding.
792	fn myers<T: PartialEq>(a: &[T], b: &[T], budget: usize)
793	-> Option<Vec<(usize, usize)>>
794	{
795	let (n, m) = (a.len() as isize, b.len() as isize);
796	let max = (a.len() + b.len()) as isize;
797	let cap = budget.min(a.len() + b.len());
798	// Furthest x reached on each diagonal k, shifted so that k = 0 sits at max.
799	let mut v: Vec<isize> = vec![0; (2 * max + 1) as usize];
800	let mut trace: Vec<Vec<isize>> = Vec::with_capacity(cap + 1);
801	for d in 0..=cap {
802	let dd = d as isize;
803	// The state before this step, which is what the walk back reads.
804	trace.push(v[(max - dd) as usize..=(max + dd) as usize].to_vec());
805	let mut k = -dd;
806	while k <= dd {
807	let mut x = if k == -dd
808	\|\| (k != dd && v[(max + k - 1) as usize] < v[(max + k + 1) as usize])
809	{
810	v[(max + k + 1) as usize]
811	} else {
812	v[(max + k - 1) as usize] + 1
813	};
814	let mut y = x - k;
815	while x < n && y < m && a[x as usize] == b[y as usize] {
816	x += 1;
817	y += 1;
818	}
819	v[(max + k) as usize] = x;
820	if x >= n && y >= m {
821	return Some(walk_back(&trace, n, m, d));
822	}
823	k += 2;
824	}
825	}
826	None
827	}
828
829	/// Walks the furthest points back from the far corner, collecting the pairs
830	/// matched on the way.
831	fn walk_back(trace: &[Vec<isize>], n: isize, m: isize, found: usize)
832	-> Vec<(usize, usize)>
833	{
834	let mut matched: Vec<(usize, usize)> = Vec::new();
835	let (mut x, mut y) = (n, m);
836	for d in (0..=found).rev() {
837	let (prev_x, prev_y) = if d == 0 {
838	(0, 0)
839	} else {
840	let dd = d as isize;
841	let w = &trace[d];
842	let at = \|k: isize\| w[(k + dd) as usize];
843	let k = x - y;
844	let prev_k = if k == -dd \|\| (k != dd && at(k - 1) < at(k + 1)) {
845	k + 1
846	} else {
847	k - 1
848	};
849	let px = at(prev_k);
850	(px, px - prev_k)
851	};
852	while x > prev_x && y > prev_y {
853	x -= 1;
854	y -= 1;
855	matched.push((x as usize, y as usize));
856	}
857	x = prev_x;
858	y = prev_y;
859	}
860	matched.reverse();
861	matched
862	}
863
864	/// Turns one changed run of lines into the splices that describe it, trimming
865	/// what its two sides share and, where the remainder is small enough to be
866	/// worth the second pass, splitting it further at the byte level.
867	fn refine(
868	old: &[u8],
869	new: &[u8],
870	o: Range<usize>,
871	n: Range<usize>,
872	out: &mut Vec<Splice>,
873	) {
874	let front = common_prefix(&old[o.clone()], &new[n.clone()]);
875	let back = common_suffix(&old[o.clone()], &new[n.clone()], front);
876	let (oa, ob) = (o.start + front, o.end - back);
877	let (na, nb) = (n.start + front, n.end - back);
878	if oa == ob && na == nb {
879	return;
880	}
881	if oa < ob && na < nb
882	&& ob - oa <= MAX_REFINE_LEN
883	&& nb - na <= MAX_REFINE_LEN
884	{
885	if let Some(inner) = changed_runs(&old[oa..ob], &new[na..nb], MAX_BYTE_SCRIPT) {
886	for c in inner {
887	out.push(Splice {
888	at: oa + c.a.start,
889	delete: c.a.end - c.a.start,
890	insert: new[na + c.b.start..na + c.b.end].to_vec().into(),
891	});
892	}
893	return;
894	}
895	}
896	out.push(Splice {
897	at: oa,
898	delete: ob - oa,
899	insert: new[na..nb].to_vec().into(),
900	});
901	}
902
903	/// Merges splices lying closer together than [`MIN_SPLICE_GAP`], carrying the
904	/// unchanged bytes between them into the payload.
905	fn coalesce(old: &[u8], splices: &mut Vec<Splice>) {
906	if splices.len() < 2 {
907	return;
908	}
909	let mut out: Vec<Splice> = Vec::with_capacity(splices.len());
910	for sp in splices.drain(..) {
911	let near = match out.last() {
912	Some(prev) => sp.at - (prev.at + prev.delete) < MIN_SPLICE_GAP,
913	None => false,
914	};
915	match out.last_mut() {
916	Some(prev) if near => {
917	let end = prev.at + prev.delete;
918	prev.insert.extend_from_slice(&old[end..sp.at]);
919	prev.insert.extend_from_slice(&sp.insert);
920	prev.delete = sp.at + sp.delete - prev.at;
921	},
922	_ => out.push(sp),
923	}
924	}
925	*splices = out;
926	}
927
928
929	#[cfg(test)]
930	mod tests {
931	use super::*;
932
933	/// Asserts the property everything else here rests on: the splices, applied
934	/// to the old bytes, produce the new bytes exactly.
935	fn diffed(old: &[u8], new: &[u8])
936	-> Outcome<Vec<Splice>>
937	{
938	let splices = diff(old, new);
939	let got = res!(apply(old, &splices));
940	assert_eq!(
941	got, new,
942	"applying {} splices to {:?} gave {:?}",
943	splices.len(), Bytes(old), Bytes(&got),
944	);
945	Ok(splices)
946	}
947
948	/// A readable form for the byte strings in a failure message.
949	struct Bytes<'a>(&'a [u8]);
950
951	impl std::fmt::Debug for Bytes<'_> {
952	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
953	match std::str::from_utf8(self.0) {
954	Ok(s) => write!(f, "{:?}", s),
955	Err(_) => write!(f, "{:?}", self.0),
956	}
957	}
958	}
959
960	fn inserted(splices: &[Splice]) -> usize {
961	splices.iter().map(\|s\| s.insert_len()).sum()
962	}
963
964	fn deleted(splices: &[Splice]) -> usize {
965	splices.iter().map(\|s\| s.delete).sum()
966	}
967
968	#[test]
969	fn identical_inputs_diff_to_nothing() -> Outcome<()> {
970	for s in [&b""[..], b"a", b"a\n", b"one\ntwo\nthree\n", b"no trailing newline"] {
971	assert!(res!(diffed(s, s)).is_empty(), "{:?}", Bytes(s));
972	}
973	Ok(())
974	}
975
976	#[test]
977	fn empty_sides_are_one_splice() -> Outcome<()> {
978	let text = b"one\ntwo\nthree\n";
979	let born = res!(diffed(b"", text));
980	assert_eq!(born.len(), 1);
981	assert_eq!(born[0].at, 0);
982	assert_eq!(born[0].delete, 0);
983	assert_eq!(born[0].insert, text.to_vec());
984	let died = res!(diffed(text, b""));
985	assert_eq!(died.len(), 1);
986	assert_eq!(died[0].at, 0);
987	assert_eq!(died[0].delete, text.len());
988	assert!(died[0].insert.is_empty());
989	// Two empty files are the same file.
990	assert!(res!(diffed(b"", b"")).is_empty());
991	Ok(())
992	}
993
994	#[test]
995	fn an_inserted_line_costs_one_line() -> Outcome<()> {
996	let old = b"alpha\nbeta\ngamma\n";
997	let new = b"alpha\nbeta\ndelta\ngamma\n";
998	let sp = res!(diffed(old, new));
999	assert_eq!(sp.len(), 1);
1000	assert_eq!(sp[0].at, 11, "the gap before gamma");
1001	assert_eq!(sp[0].delete, 0);
1002	assert_eq!(sp[0].insert, b"delta\n".to_vec());
1003	Ok(())
1004	}
1005
1006	#[test]
1007	fn a_deleted_line_costs_one_line() -> Outcome<()> {
1008	let old = b"alpha\nbeta\ngamma\n";
1009	let new = b"alpha\ngamma\n";
1010	let sp = res!(diffed(old, new));
1011	assert_eq!(sp.len(), 1);
1012	assert_eq!(sp[0].at, 6, "the start of beta");
1013	assert_eq!(sp[0].delete, 5, "beta and its newline");
1014	assert!(sp[0].insert.is_empty());
1015	Ok(())
1016	}
1017
1018	#[test]
1019	fn an_edit_within_a_line_costs_the_changed_bytes() -> Outcome<()> {
1020	let old = b"alpha\nthe quick brown fox\ngamma\n";
1021	let new = b"alpha\nthe quick brawn fox\ngamma\n";
1022	let sp = res!(diffed(old, new));
1023	assert_eq!(sp.len(), 1);
1024	assert_eq!(sp[0].delete, 1);
1025	assert_eq!(sp[0].insert, b"a".to_vec());
1026	Ok(())
1027	}
1028
1029	#[test]
1030	fn nearby_changes_merge_and_distant_ones_do_not() -> Outcome<()> {
1031	let old = b"X-------------------------X\n";
1032	let new = b"Y-------------------------Y\n";
1033	let apart = res!(diffed(old, new));
1034	assert_eq!(apart.len(), 2, "twenty five unchanged bytes keep them apart");
1035	assert_eq!(inserted(&apart), 2);
1036	let old = b"X---X\n";
1037	let new = b"Y---Y\n";
1038	let close = res!(diffed(old, new));
1039	assert_eq!(close.len(), 1, "three unchanged bytes do not");
1040	assert_eq!(close[0].insert, b"Y---Y".to_vec());
1041	Ok(())
1042	}
1043
1044	/// The module makes no claim to notice a move; the operation vocabulary has
1045	/// one, and finding it is not this module's business.
1046	#[test]
1047	fn a_move_shaped_edit_becomes_a_delete_and_an_insert() -> Outcome<()> {
1048	let old = b"moved\nalpha\nbeta\ngamma\ndelta\nepsilon\n";
1049	let new = b"alpha\nbeta\ngamma\ndelta\nepsilon\nmoved\n";
1050	let sp = res!(diffed(old, new));
1051	assert_eq!(sp.len(), 2);
1052	assert_eq!(sp[0].at, 0);
1053	assert_eq!(sp[0].delete, 6);
1054	assert!(sp[0].insert.is_empty());
1055	assert_eq!(sp[1].delete, 0);
1056	assert_eq!(sp[1].insert, b"moved\n".to_vec());
1057	Ok(())
1058	}
1059
1060	#[test]
1061	fn a_whole_file_rewrite_is_one_splice() -> Outcome<()> {
1062	let old = b"alpha\nbeta\ngamma\n";
1063	let new = b"one\ntwo\nthree\n";
1064	let sp = res!(diffed(old, new));
1065	assert_eq!(sp.len(), 1);
1066	assert_eq!(sp[0].at, 0);
1067	// The final newline is the one thing the two versions still share.
1068	assert_eq!(sp[0].delete, old.len() - 1);
1069	assert_eq!(sp[0].insert, new[..new.len() - 1].to_vec());
1070	Ok(())
1071	}
1072
1073	#[test]
1074	fn a_trailing_newline_is_one_byte() -> Outcome<()> {
1075	let bare = b"alpha\nbeta";
1076	let ended = b"alpha\nbeta\n";
1077	let gained = res!(diffed(bare, ended));
1078	assert_eq!(gained.len(), 1);
1079	assert_eq!(gained[0].at, bare.len());
1080	assert_eq!(gained[0].delete, 0);
1081	assert_eq!(gained[0].insert, b"\n".to_vec());
1082	let lost = res!(diffed(ended, bare));
1083	assert_eq!(lost.len(), 1);
1084	assert_eq!(lost[0].at, bare.len());
1085	assert_eq!(lost[0].delete, 1);
1086	assert!(lost[0].insert.is_empty());
1087	Ok(())
1088	}
1089
1090	#[test]
1091	fn newline_free_content_is_one_trimmed_splice() -> Outcome<()> {
1092	let old: Vec<u8> = (0u8..=255).chain(0u8..=255).collect();
1093	let mut new = old.clone();
1094	new[300] = 0xff;
1095	new[301] = 0xff;
1096	let sp = res!(diffed(&old, &new));
1097	assert_eq!(sp.len(), 1);
1098	assert_eq!(sp[0].at, 300);
1099	assert_eq!(sp[0].delete, 2);
1100	assert_eq!(sp[0].insert, vec![0xff, 0xff]);
1101	Ok(())
1102	}
1103
1104	/// Two distant edits in a large file cost the two edits, which is the whole
1105	/// point of the exercise: a single trimmed splice would have stored
1106	/// everything between them.
1107	#[test]
1108	fn two_distant_edits_in_a_large_file_cost_two_edits() -> Outcome<()> {
1109	let mut lines: Vec<String> = Vec::with_capacity(1000);
1110	for i in 0..1000 {
1111	lines.push(fmt!("line {} of the file, with some words on it\n", i));
1112	}
1113	let old: Vec<u8> = lines.concat().into_bytes();
1114	lines[99] = fmt!("line 99 has been rewritten entirely\n");
1115	lines[899] = fmt!("line 899 of the file, with other words on it\n");
1116	let new: Vec<u8> = lines.concat().into_bytes();
1117	let sp = res!(diffed(&old, &new));
1118	assert_eq!(sp.len(), 2, "one splice per changed line");
1119	// One line was rewritten, so it is stored; the other lost a word, so
1120	// only the word is. Neither is anywhere near the size of the file.
1121	assert!(inserted(&sp) <= 40, "inserted {} bytes", inserted(&sp));
1122	assert!(deleted(&sp) <= 40, "deleted {} bytes", deleted(&sp));
1123	// What the frontend does without a diff, for comparison: everything
1124	// between the first change and the last.
1125	let bare = trimmed_splice(&old, &new);
1126	assert!(bare.insert.len() > 30_000, "the whole point of the exercise");
1127	Ok(())
1128	}
1129
1130	#[test]
1131	fn an_exhausted_budget_falls_back_to_one_splice() -> Outcome<()> {
1132	let mut old = String::new();
1133	let mut new = String::new();
1134	for i in 0..200 {
1135	// Every other line changes, so the edit script is two hundred long
1136	// and the changes are spread across two hundred runs.
1137	if i % 2 == 0 {
1138	old.push_str(&fmt!("old line {}, with words after it\n", i));
1139	new.push_str(&fmt!("new line {}, with words after it\n", i));
1140	} else {
1141	let same = fmt!("line {} is left exactly as it was\n", i);
1142	old.push_str(&same);
1143	new.push_str(&same);
1144	}
1145	}
1146	let (old, new) = (old.into_bytes(), new.into_bytes());
1147	assert!(diff_with_budget(&old, &new, 512).len() > 1, "a full budget diffs");
1148	for budget in [0usize, 1, 8, 64] {
1149	let sp = diff_with_budget(&old, &new, budget);
1150	assert_eq!(sp.len(), 1, "budget {}", budget);
1151	assert_eq!(res!(apply(&old, &sp)), new, "budget {}", budget);
1152	assert_eq!(sp[0], trimmed_splice(&old, &new), "budget {}", budget);
1153	}
1154	Ok(())
1155	}
1156
1157	#[test]
1158	fn a_long_changed_run_is_left_whole() -> Outcome<()> {
1159	// One line, longer than the refinement limit, differing in two places
1160	// far apart.
1161	let mut old = vec![b'-'; MAX_REFINE_LEN * 2];
1162	old.push(b'\n');
1163	let mut new = old.clone();
1164	new[10] = b'X';
1165	new[MAX_REFINE_LEN * 2 - 10] = b'X';
1166	let sp = res!(diffed(&old, &new));
1167	assert_eq!(sp.len(), 1, "the run is too long to refine");
1168	assert!(sp[0].insert.len() > MAX_REFINE_LEN);
1169	Ok(())
1170	}
1171
1172	#[test]
1173	fn apply_refuses_a_list_that_does_not_fit() -> Outcome<()> {
1174	let old = b"alpha\nbeta\n";
1175	assert!(apply(old, &[Splice { at: 12, delete: 0, insert: Vec::new() }]).is_err());
1176	assert!(apply(old, &[Splice { at: 0, delete: 12, insert: Vec::new() }]).is_err());
1177	assert!(apply(old, &[
1178	Splice { at: 6, delete: 1, insert: Vec::new() }.into(),
1179	Splice { at: 2, delete: 1, insert: Vec::new() }.into(),
1180	]).is_err());
1181	assert!(apply(old, &[
1182	Splice { at: 0, delete: 4, insert: Vec::new() }.into(),
1183	Splice { at: 2, delete: 1, insert: Vec::new() }.into(),
1184	]).is_err(), "overlapping splices");
1185	assert!(apply(old, &[
1186	Splice { at: usize::MAX, delete: usize::MAX, insert: Vec::new() }.into(),
1187	]).is_err(), "an offset that would overflow");
1188	Ok(())
1189	}
1190
1191	/// Whatever the diff returns is ascending, non-overlapping, and separated
1192	/// by at least the minimum gap.
1193	fn assert_well_formed(old: &[u8], splices: &[Splice]) {
1194	let mut at = 0usize;
1195	let mut first = true;
1196	for sp in splices {
1197	assert!(sp.at + sp.delete <= old.len(), "a splice reaches past the file");
1198	if first {
1199	first = false;
1200	} else {
1201	assert!(sp.at >= at + MIN_SPLICE_GAP,
1202	"splices at {} and {} are less than {} bytes apart",
1203	at, sp.at, MIN_SPLICE_GAP);
1204	}
1205	assert!(sp.delete > 0 \|\| !sp.insert.is_empty(), "a splice does nothing");
1206	at = sp.at + sp.delete;
1207	}
1208	}
1209
1210	/// Two hundred random pairs of files, all of them applied back: the oracle
1211	/// is that the result is the new bytes exactly, every time.
1212	#[test]
1213	fn random_pairs_apply_back_to_the_new_bytes() -> Outcome<()> {
1214	// A small linear congruential generator, so a failure can be reproduced.
1215	let mut state = 0x2545_F491_4F6C_DD1Du64;
1216	let mut next = move \|\| {
1217	state = state
1218	.wrapping_mul(6_364_136_223_846_793_005)
1219	.wrapping_add(1_442_695_040_888_963_407);
1220	(state >> 33) as usize
1221	};
1222	// A small alphabet of lines, so that lines repeat and the line level
1223	// pass has real matching to do.
1224	let words = ["alpha", "beta", "gamma", "delta", "epsilon", "zeta", "", "x"];
1225	for trial in 0..220 {
1226	let mut old: Vec<u8> = Vec::new();
1227	for _ in 0..(next() % 40) {
1228	old.extend_from_slice(words[next() % words.len()].as_bytes());
1229	// Most lines end; some do not, which is how a file ends up with
1230	// a fragment on the end and how two lines end up joined.
1231	if next() % 8 != 0 {
1232	old.push(b'\n');
1233	}
1234	}
1235	// The new file is the old one put through a handful of edits, so
1236	// that the two are usually related, and occasionally not at all.
1237	let mut new = old.clone();
1238	for _ in 0..(next() % 6) {
1239	match next() % 4 {
1240	0 if !new.is_empty() => {
1241	// Delete a run.
1242	let at = next() % new.len();
1243	let len = (next() % 12).min(new.len() - at);
1244	new.drain(at..at + len);
1245	},
1246	1 => {
1247	// Insert a line.
1248	let at = if new.is_empty() { 0 } else { next() % new.len() };
1249	let mut ins = words[next() % words.len()].as_bytes().to_vec();
1250	ins.push(b'\n');
1251	let tail = new.split_off(at);
1252	new.extend_from_slice(&ins);
1253	new.extend_from_slice(&tail);
1254	},
1255	2 if !new.is_empty() => {
1256	// Change one byte.
1257	let at = next() % new.len();
1258	new[at] = b'a' + (next() % 26) as u8;
1259	},
1260	_ => {
1261	// Move a run to the front.
1262	if new.len() > 4 {
1263	let at = next() % (new.len() - 2);
1264	let len = (next() % 10).min(new.len() - at);
1265	let run: Vec<u8> = new.drain(at..at + len).collect();
1266	let to = if new.is_empty() { 0 } else { next() % new.len() };
1267	let tail = new.split_off(to);
1268	new.extend_from_slice(&run);
1269	new.extend_from_slice(&tail);
1270	}
1271	},
1272	}
1273	}
1274	let splices = diff(&old, &new);
1275	let got = res!(apply(&old, &splices));
1276	assert_eq!(
1277	got, new,
1278	"trial {}: {:?} -> {:?} gave {:?}",
1279	trial, Bytes(&old), Bytes(&new), Bytes(&got),
1280	);
1281	assert_well_formed(&old, &splices);
1282	// The same pair under a budget that forces the fallback still
1283	// applies back.
1284	let bare = diff_with_budget(&old, &new, 0);
1285	assert_eq!(res!(apply(&old, &bare)), new, "trial {} under fallback", trial);
1286	}
1287	Ok(())
1288	}
1289
1290	/// Random byte soup, where the line level pass has almost nothing to work
1291	/// with, still applies back.
1292	#[test]
1293	fn random_binary_pairs_apply_back() -> Outcome<()> {
1294	let mut state = 0x9E37_79B9_7F4A_7C15u64;
1295	let mut next = move \|\| {
1296	state = state
1297	.wrapping_mul(6_364_136_223_846_793_005)
1298	.wrapping_add(1_442_695_040_888_963_407);
1299	(state >> 33) as usize
1300	};
1301	for trial in 0..60 {
1302	let n = next() % 500;
1303	let old: Vec<u8> = (0..n).map(\|_\| (next() % 256) as u8).collect();
1304	let mut new = old.clone();
1305	for _ in 0..(next() % 8) {
1306	if new.is_empty() {
1307	new.push((next() % 256) as u8);
1308	continue;
1309	}
1310	let at = next() % new.len();
1311	match next() % 3 {
1312	0 => { new[at] = (next() % 256) as u8; },
1313	1 => { new.insert(at, (next() % 256) as u8); },
1314	_ => { new.remove(at); },
1315	}
1316	}
1317	let splices = diff(&old, &new);
1318	assert_eq!(res!(apply(&old, &splices)), new, "trial {}", trial);
1319	assert_well_formed(&old, &splices);
1320	}
1321	Ok(())
1322	}
1323
1324	/// Lines are cut where the newlines are, the last one carrying whatever is
1325	/// left, and an empty file has none.
1326	#[test]
1327	fn lines_are_cut_at_the_newlines() -> Outcome<()> {
1328	assert_eq!(line_starts(b""), vec![0]);
1329	assert_eq!(line_starts(b"\n"), vec![0, 1]);
1330	assert_eq!(line_starts(b"a"), vec![0, 1]);
1331	assert_eq!(line_starts(b"a\nb\n"), vec![0, 2, 4]);
1332	assert_eq!(line_starts(b"a\nb"), vec![0, 2, 3]);
1333	Ok(())
1334	}
1335
1336	/// A pseudorandom byte string of `n` bytes with no newline in it, which is
1337	/// what a compressed or otherwise structureless payload looks like to the
1338	/// line pass: one enormous line.
1339	fn binary(n: usize, seed: u64) -> Vec<u8> {
1340	let mut state = seed;
1341	let mut next = move \|\| {
1342	state = state
1343	.wrapping_mul(6_364_136_223_846_793_005)
1344	.wrapping_add(1_442_695_040_888_963_407);
1345	(state >> 33) as usize
1346	};
1347	(0..n).map(\|_\| {
1348	let b = (next() % 255) as u8;
1349	if b >= b'\n' { b + 1 } else { b }
1350	}).collect()
1351	}
1352
1353	/// The route is chosen by what the content is, not by what it is called.
1354	#[test]
1355	fn the_route_follows_the_content() -> Outcome<()> {
1356	// Nothing to do.
1357	assert_eq!(diff_routed(b"same", b"same", MAX_PIECE_SCRIPT).1, Route::Same);
1358	// Text, of any size, cuts at the newlines.
1359	let mut lines = String::new();
1360	for i in 0..4000 {
1361	lines.push_str(&fmt!("line {} of a perfectly ordinary text file\n", i));
1362	}
1363	let old = lines.clone().into_bytes();
1364	let new = lines.replace("line 2000 ", "line 2000! ").into_bytes();
1365	assert!(old.len() > MIN_CHUNKED_LEN, "large enough to have a choice");
1366	assert_eq!(diff_routed(&old, &new, MAX_PIECE_SCRIPT).1, Route::Line);
1367	// Newline-poor content long enough to chunk takes the chunk route.
1368	let old = binary(MIN_CHUNKED_LEN * 4, 0x2545_F491_4F6C_DD1D);
1369	let mut new = old.clone();
1370	new[MIN_CHUNKED_LEN] ^= 0xff;
1371	assert_eq!(diff_routed(&old, &new, MAX_PIECE_SCRIPT).1, Route::Chunk);
1372	// The same content, too short to be worth chunking, falls to one splice.
1373	let short = &old[..MIN_CHUNKED_LEN - 1];
1374	let mut new = short.to_vec();
1375	new[10] ^= 0xff;
1376	new[MIN_CHUNKED_LEN - 100] ^= 0xff;
1377	let (sp, route) = diff_routed(short, &new, MAX_PIECE_SCRIPT);
1378	assert_eq!(route, Route::Line, "one line, refined by the byte pass");
1379	assert_eq!(res!(apply(short, &sp)), new);
1380	// And a budget no piece route can meet falls through both of them.
1381	assert_eq!(diff_routed(&old, &new, 0).1, Route::Whole);
1382	Ok(())
1383	}
1384
1385	#[test]
1386	fn an_exhausted_line_budget_hands_on_to_the_chunks() -> Outcome<()> {
1387	// Every other line changes, over enough lines that a small budget cannot
1388	// describe it, in a file long enough to chunk.
1389	let mut old = String::new();
1390	let mut new = String::new();
1391	for i in 0..900 {
1392	if i % 2 == 0 {
1393	old.push_str(&fmt!("old line {}, with a few words after it\n", i));
1394	new.push_str(&fmt!("new line {}, with a few words after it\n", i));
1395	} else {
1396	let same = fmt!("line {} is left exactly as it was, unchanged\n", i);
1397	old.push_str(&same);
1398	new.push_str(&same);
1399	}
1400	}
1401	let (old, new) = (old.into_bytes(), new.into_bytes());
1402	assert!(old.len() > MIN_CHUNKED_LEN);
1403	assert_eq!(diff_routed(&old, &new, MAX_PIECE_SCRIPT).1, Route::Line,
1404	"a full budget stays on the line route");
1405	let (sp, route) = diff_routed(&old, &new, 16);
1406	assert_eq!(route, Route::Chunk, "a starved line pass is not the end of it");
1407	assert_eq!(res!(apply(&old, &sp)), new);
1408	assert_well_formed(&old, &sp);
1409	Ok(())
1410	}
1411
1412	/// This is the property the whole route rests on, and it is the one thing a
1413	/// fixed-size chunker cannot do: there, one inserted byte shifts every
1414	/// boundary after it and nothing downstream matches anything.
1415	#[test]
1416	fn a_chunk_boundary_follows_the_content() -> Outcome<()> {
1417	let old = binary(1 << 20, 0x9E37_79B9_7F4A_7C15);
1418	let mut new = old.clone();
1419	new.insert(1000, 0x42);
1420	let before = chunk_starts(&old);
1421	let after = chunk_starts(&new);
1422	assert!(before.len() > 40, "a megabyte should cut into many chunks");
1423	// Every boundary beyond the disturbance is one byte along from where it
1424	// was, which is to say it is the same place in the content.
1425	let shifted: Vec<usize> = after.iter()
1426	.filter(\|b\| **b > MAX_CHUNK)
1427	.map(\|b\| b - 1)
1428	.collect();
1429	let kept = before.iter().filter(\|b\| shifted.contains(b)).count();
1430	assert!(
1431	kept as f64 > 0.9 * shifted.len() as f64,
1432	"only {} of {} boundaries re-synchronised", kept, shifted.len(),
1433	);
1434	Ok(())
1435	}
1436
1437	/// This is the claim the feature table makes, measured. The comparison is
1438	/// against what the same pair costs without the chunk route, which is the
1439	/// whole span between the outermost edits.
1440	#[test]
1441	fn scattered_edits_in_a_large_binary_cost_their_regions() -> Outcome<()> {
1442	let old = binary(4 << 20, 0x0f1e_2d3c_4b5a_6978);
1443	let mut new = old.clone();
1444	for at in [100_000usize, 2_000_000, 4_000_000] {
1445	new[at] ^= 0xff;
1446	}
1447	let (sp, route) = diff_routed(&old, &new, MAX_PIECE_SCRIPT);
1448	assert_eq!(route, Route::Chunk);
1449	assert_eq!(res!(apply(&old, &sp)), new);
1450	assert_well_formed(&old, &sp);
1451	assert_eq!(sp.len(), 3, "one region per edit");
1452	let cost = inserted(&sp) + deleted(&sp);
1453	// The bound the route guarantees is three refined regions, so at worst
1454	// three chunks; a few hundred kilobytes was the claim.
1455	assert!(
1456	cost < 3 * AVG_CHUNK,
1457	"three edits in four megabytes cost {} bytes", cost,
1458	);
1459	// What it actually costs is the three bytes, because trimming what the
1460	// two sides of a changed chunk share finds the edit exactly. Frozen,
1461	// because a change to the chunker that quietly stopped doing this is
1462	// precisely what this test is for.
1463	assert_eq!(cost, 6, "three bytes replaced by three bytes");
1464	// What the same pair costs with no piece route at all: everything between
1465	// the first change and the last.
1466	let bare = trimmed_splice(&old, &new);
1467	assert!(bare.insert.len() > 3_800_000, "the whole point of the exercise");
1468	Ok(())
1469	}
1470
1471	/// Randomised binary pairs with edits scattered through them, all applied
1472	/// back: the oracle is that the result is the new bytes exactly, on the route
1473	/// that produced them.
1474	#[test]
1475	fn random_binary_pairs_on_the_chunk_route_apply_back() -> Outcome<()> {
1476	let mut state = 0x1234_5678_9abc_def0u64;
1477	let mut next = move \|\| {
1478	state = state
1479	.wrapping_mul(6_364_136_223_846_793_005)
1480	.wrapping_add(1_442_695_040_888_963_407);
1481	(state >> 33) as usize
1482	};
1483	let mut chunked = 0;
1484	for trial in 0..24 {
1485	let n = MIN_CHUNKED_LEN + next() % (200 * 1024);
1486	let old = binary(n, 0xdead_beef_0000_0000 + trial as u64);
1487	let mut new = old.clone();
1488	// A handful of edits at unrelated offsets, of every kind.
1489	for _ in 0..1 + next() % 8 {
1490	if new.is_empty() {
1491	break;
1492	}
1493	let at = next() % new.len();
1494	match next() % 4 {
1495	0 => { new[at] ^= 0xff; },
1496	1 => {
1497	let run: Vec<u8> = (0..1 + next() % 900)
1498	.map(\|k\| (at + k) as u8 \| 1)
1499	.collect();
1500	let tail = new.split_off(at);
1501	new.extend_from_slice(&run);
1502	new.extend_from_slice(&tail);
1503	},
1504	2 => {
1505	let len = (next() % 3000).min(new.len() - at);
1506	new.drain(at..at + len);
1507	},
1508	_ => {
1509	// Move a run to another offset, which the diff has no verb
1510	// for and must describe as a deletion and an insertion.
1511	let len = (next() % 1500).min(new.len() - at);
1512	let run: Vec<u8> = new.drain(at..at + len).collect();
1513	let to = if new.is_empty() { 0 } else { next() % new.len() };
1514	let tail = new.split_off(to);
1515	new.extend_from_slice(&run);
1516	new.extend_from_slice(&tail);
1517	},
1518	}
1519	}
1520	let (sp, route) = diff_routed(&old, &new, MAX_PIECE_SCRIPT);
1521	assert_eq!(res!(apply(&old, &sp)), new, "trial {} on {}", trial, route.name());
1522	assert_well_formed(&old, &sp);
1523	if route == Route::Chunk {
1524	chunked += 1;
1525	}
1526	// And under a budget that forces the fallback, it still applies back.
1527	let (bare, route) = diff_routed(&old, &new, 0);
1528	assert_eq!(route, Route::Whole);
1529	assert_eq!(res!(apply(&old, &bare)), new, "trial {} under fallback", trial);
1530	}
1531	assert_eq!(chunked, 24, "every one of these is newline-free and large");
1532	Ok(())
1533	}
1534
1535	/// Chunks are cut where the content says, the last one carrying whatever is
1536	/// left, and an empty input has none.
1537	#[test]
1538	fn chunks_are_cut_within_their_bounds() -> Outcome<()> {
1539	assert_eq!(chunk_starts(b""), vec![0]);
1540	assert_eq!(chunk_starts(b"short"), vec![0, 5]);
1541	let bytes = binary(1 << 20, 0xabcd_ef01_2345_6789);
1542	let starts = chunk_starts(&bytes);
1543	assert_eq!(starts[0], 0);
1544	assert_eq!(starts[starts.len() - 1], bytes.len());
1545	for (i, w) in starts.windows(2).enumerate() {
1546	let len = w[1] - w[0];
1547	assert!(len > 0, "chunk {} is empty", i);
1548	assert!(len <= MAX_CHUNK, "chunk {} is {} bytes", i, len);
1549	// Every chunk but the last reaches the minimum.
1550	if i + 2 < starts.len() {
1551	assert!(len > MIN_CHUNK, "chunk {} is {} bytes", i, len);
1552	}
1553	}
1554	// A run of identical bytes offers the hash nothing, so the ceiling is
1555	// what cuts it.
1556	let flat = vec![0x5au8; 5 * MAX_CHUNK];
1557	let starts = chunk_starts(&flat);
1558	assert_eq!(starts.len(), 6);
1559	assert_eq!(starts[1], MAX_CHUNK);
1560	Ok(())
1561	}
1562
1563	// ── Stored patches ──
1564
1565	/// This module's own source: real text, with real indentation, real comment
1566	/// prose and real repeated tokens, rather than a fixture shaped to flatter
1567	/// the diff.
1568	const SOURCE: &str = include_str!("diff.rs");
1569
1570	/// One line changed in the middle of a real file must cost the line and not
1571	/// the file, and must come back exactly.
1572	#[test]
1573	fn a_patch_of_one_line_costs_the_line_and_not_the_file() -> Outcome<()> {
1574	let old = SOURCE.as_bytes();
1575	let mut lines: Vec<&str> = SOURCE.split('\n').collect();
1576	let at = lines.len() / 2;
1577	lines[at] = "\t// one line, changed.";
1578	let new_text = lines.join("\n");
1579	let new = new_text.as_bytes();
1580	let patch = res!(make_patch(old, new));
1581	assert!(
1582	patch.len() * 20 < old.len(),
1583	"a one line change cost {} bytes against a file of {}",
1584	patch.len(), old.len(),
1585	);
1586	assert_eq!(res!(apply_patch(old, &patch)), new);
1587	Ok(())
1588	}
1589
1590	/// The header says what it was made from and what it makes, without either
1591	/// file being present.
1592	#[test]
1593	fn a_patch_names_both_lengths_in_its_header() -> Outcome<()> {
1594	let old = b"one\ntwo\nthree\n";
1595	let new = b"one\ntwo\nthree\nfour\n";
1596	let patch = res!(make_patch(old, new));
1597	assert_eq!(res!(patch_lengths(&patch)), (old.len(), new.len()));
1598	Ok(())
1599	}
1600
1601	/// The break this whole encoding exists for. A splice list made against
1602	/// one parent, applied to a different parent OF THE SAME LENGTH, is
1603	/// structurally valid: `apply` cannot see anything wrong with it and returns
1604	/// bytes nobody ever wrote. The patch must refuse instead.
1605	///
1606	/// The refusal is required to blame the INPUT and not the result. The
1607	/// checksum of the reconstruction would catch this too, and would say the
1608	/// patch made the wrong bytes -- true, useless, and pointing at the one
1609	/// thing that is not at fault. So the old side's checksum is what decides;
1610	/// the length beside it is the plainer message for the common case and is
1611	/// not load bearing on its own.
1612	#[test]
1613	fn a_patch_refuses_a_parent_it_was_not_made_against() -> Outcome<()> {
1614	let old = b"alpha\nbravo\ncharlie\ndelta\n";
1615	let new = b"alpha\nBRAVO\ncharlie\ndelta\n";
1616	// Same length, different bytes: a length check alone would pass this.
1617	let other = b"alpha\nbravo\ncharlie\nDELTA\n";
1618	assert_eq!(old.len(), other.len());
1619	let patch = res!(make_patch(old, new));
1620	// The bare splice list would have applied without complaint.
1621	let splices = diff(old, new);
1622	let wrong = res!(apply(other, &splices));
1623	assert_ne!(wrong, new.to_vec(), "the wrong parent gives bytes nobody wrote");
1624	// And one byte shorter, so the length is wrong as well as the content.
1625	let shorter = b"alpha\nbravo\ncharlie\ndelt\n";
1626	for parent in [&other[..], &shorter[..]] {
1627	match apply_patch(parent, &patch) {
1628	Ok(got) => panic!(
1629	"a patch applied to a parent it was not made against returned {} bytes",
1630	got.len()),
1631	Err(e) => {
1632	let tags = e.tags();
1633	assert!(
1634	tags.contains(&ErrTag::Input),
1635	"the refusal must blame the parent it was given; it said {:?}", tags);
1636	assert!(
1637	!tags.contains(&ErrTag::Data),
1638	"blaming the reconstruction points at the one thing not at fault; \
1639	it said {:?}", tags);
1640	},
1641	}
1642	}
1643	Ok(())
1644	}
1645
1646	/// A patch a byte short, and a patch a byte long, are both refused: nothing
1647	/// is decoded from a length the file does not carry, and nothing is left
1648	/// over unaccounted for.
1649	#[test]
1650	fn a_patch_that_is_not_its_own_length_is_refused() -> Outcome<()> {
1651	let old = SOURCE.as_bytes();
1652	let new_text = SOURCE.replace("Myers", "MYERS");
1653	let patch = res!(make_patch(old, new_text.as_bytes()));
1654	// Every truncation, not a few: the decode reads a length out of the
1655	// file and then indexes with it, so a bound it does not check is a
1656	// panic rather than a refusal -- and a panic in a browser takes the tab.
1657	for cut in 1..patch.len() {
1658	let short = &patch[..patch.len() - cut];
1659	assert!(apply_patch(old, short).is_err(), "a patch {} bytes short was read", cut);
1660	}
1661	let mut long = patch.clone();
1662	long.push(0);
1663	assert!(apply_patch(old, &long).is_err(), "a patch with a trailing byte was read");
1664	Ok(())
1665	}
1666
1667	/// A bit rotted anywhere in the payload is caught by the checksum of the
1668	/// result, which is the only check that can see it: the splices still fit
1669	/// the old bytes, so `apply` is happy.
1670	#[test]
1671	fn a_patch_whose_bytes_have_decayed_is_refused() -> Outcome<()> {
1672	let old = b"alpha\nbravo\ncharlie\ndelta\necho\n";
1673	let new = b"alpha\nbravo\nCHARLIE THE LONGER\ndelta\necho\n";
1674	let patch = res!(make_patch(old, new));
1675	let mut caught = 0;
1676	let mut passed = 0;
1677	for i in PATCH_HEADER..patch.len() {
1678	let mut bent = patch.clone();
1679	bent[i] ^= 0x20;
1680	match apply_patch(old, &bent) {
1681	Ok(got) => {
1682	passed += 1;
1683	assert_eq!(got, new.to_vec(), "byte {} bent and the answer was wrong", i);
1684	},
1685	Err(_) => caught += 1,
1686	}
1687	}
1688	assert_eq!(passed, 0, "{} bent patches were accepted", passed);
1689	assert!(caught > 0);
1690	// A bent patch blames neither the caller nor the parent: what is wrong
1691	// is the patch itself, and a reader has to be able to tell the two
1692	// apart to know which file to go and find.
1693	let mut bent = patch.clone();
1694	bent[patch.len() - 1] ^= 0x20;
1695	match apply_patch(old, &bent) {
1696	Ok(_) => panic!("a bent patch was applied"),
1697	Err(e) => assert!(
1698	e.tags().contains(&ErrTag::Data),
1699	"a bent patch must blame itself; it said {:?}", e.tags()),
1700	}
1701	Ok(())
1702	}
1703
1704	/// Handed a file that is not a patch, the reader says so rather than
1705	/// decoding whatever it was given.
1706	#[test]
1707	fn what_is_not_a_patch_is_not_read_as_one() -> Outcome<()> {
1708	let old = b"alpha\nbravo\n";
1709	for bytes in [&b""[..], b"{}", b"<html></html>", &[0u8; PATCH_HEADER][..]] {
1710	assert!(apply_patch(old, bytes).is_err(), "{:?} was read as a patch", Bytes(bytes));
1711	assert!(patch_lengths(bytes).is_err(), "{:?} was measured as a patch", Bytes(bytes));
1712	}
1713	// The right mark, an unknown layout.
1714	let mut future = res!(make_patch(old, b"alpha\nBRAVO\n"));
1715	future[4] = 0xff;
1716	assert!(apply_patch(old, &future).is_err(), "a patch from the future was read");
1717	// A whole valid patch with the mark alone spoilt. Nothing else in it is
1718	// wrong, so this is the one case where the mark is what has to catch it.
1719	let mut unmarked = res!(make_patch(old, b"alpha\nBRAVO\n"));
1720	unmarked[0] = b'X';
1721	assert!(apply_patch(old, &unmarked).is_err(), "a patch with the wrong mark was read");
1722	assert!(patch_lengths(&unmarked).is_err(), "a patch with the wrong mark was measured");
1723	Ok(())
1724	}
1725
1726	/// Both empty sides, and a patch that changes nothing, still round-trip.
1727	#[test]
1728	fn the_empty_cases_still_round_trip() -> Outcome<()> {
1729	let text = SOURCE.as_bytes();
1730	for (old, new) in [
1731	(&b""[..], &b""[..]),
1732	(&b""[..], text),
1733	(text, &b""[..]),
1734	(text, text),
1735	] {
1736	let patch = res!(make_patch(old, new));
1737	assert_eq!(res!(apply_patch(old, &patch)), new.to_vec());
1738	}
1739	Ok(())
1740	}
1741
1742	}