//! Line patches between two versions of a text, verified before anyone reads them as a change.
//!
//! A patch is a claim: "apply this to that, and you get this". The claim is checkable, so this
//! module checks it rather than trusting the hunks: [`apply`] must reproduce the target exactly,
//! and a caller that cannot get that result stores the whole text instead. That is why the diff
//! here is deliberately simple - an exact LCS over lines, hunks of changed lines with one line of
//! context - instead of anything cleverer that would be harder to trust.
//!
//! Lines keep their terminators, so applying patches preserves trailing newlines and a text with
//! no final newline stays that way. Byte fidelity is the point: the patched result is compared
//! against the target string, not against a normalized form of it.
use serde::{Deserialize, Serialize};
/// One contiguous change to one source.
#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
pub struct LinePatch {
/// Which source this patch belongs to, as the reader knows it.
pub source: String,
/// 1-based line where the replaced block starts in the base text.
pub start_line: usize,
/// Lines replaced, exactly as they appear in the base text.
pub old_lines: Vec<String>,
/// Lines that take their place.
pub new_lines: Vec<String>,
}
impl LinePatch {
/// How long this patch's own text is, in bytes, when rendered.
#[must_use]
pub fn rendered_len(&self) -> usize {
self.old_lines
.iter()
.map(|line| line.len() + 1)
.sum::<usize>()
+ self
.new_lines
.iter()
.map(|line| line.len() + 1)
.sum::<usize>()
+ self.source.len()
}
}
/// Split a text into lines that keep their terminators, so concatenation is lossless.
fn lines_of(text: &str) -> Vec<&str> {
if text.is_empty() {
return Vec::new();
}
text.split_inclusive('\n').collect()
}
/// Changed regions between `base` and `target`, each with one line of context.
///
/// An empty result means the two texts are identical.
#[must_use]
pub fn patches(base: &str, target: &str, source: &str) -> Vec<LinePatch> {
let base_lines = lines_of(base);
let target_lines = lines_of(target);
if base_lines == target_lines {
return Vec::new();
}
// Longest common subsequence over lines. Instruction texts here are hundreds of lines, so
// the quadratic table is the honest trade: obvious, testable, and no heuristics that would
// need their own evidence.
let n = base_lines.len();
let m = target_lines.len();
let mut lcs = vec![vec![0usize; m + 1]; n + 1];
for i in (0..n).rev() {
for j in (0..m).rev() {
lcs[i][j] = if base_lines[i] == target_lines[j] {
lcs[i + 1][j + 1] + 1
} else {
lcs[i + 1][j].max(lcs[i][j + 1])
};
}
}
// Walk the table into one script step per line: shared, removed, or added.
#[derive(Clone, Copy, Eq, PartialEq)]
enum Step {
Shared,
Removed,
Added,
}
let mut script: Vec<Step> = Vec::with_capacity(n + m);
let (mut i, mut j) = (0usize, 0usize);
while i < n && j < m {
if base_lines[i] == target_lines[j] {
script.push(Step::Shared);
i += 1;
j += 1;
} else if lcs[i + 1][j] >= lcs[i][j + 1] {
script.push(Step::Removed);
i += 1;
} else {
script.push(Step::Added);
j += 1;
}
}
while i < n {
script.push(Step::Removed);
i += 1;
}
while j < m {
script.push(Step::Added);
j += 1;
}
// Group changed steps into hunks, keeping one shared line of context on each side, and
// merging hunks whose context would touch - two patches over the same lines could not be
// applied one after the other.
const CONTEXT: usize = 1;
let mut hunks: Vec<(usize, usize, usize, usize)> = Vec::new(); // base start..end, target start..end
let mut index = 0usize;
let (mut base_at, mut target_at) = (0usize, 0usize);
let mut positions: Vec<(usize, usize)> = Vec::with_capacity(script.len() + 1);
for step in &script {
positions.push((base_at, target_at));
match step {
Step::Shared => {
base_at += 1;
target_at += 1;
}
Step::Removed => base_at += 1,
Step::Added => target_at += 1,
}
}
positions.push((base_at, target_at));
while index < script.len() {
if script[index] == Step::Shared {
index += 1;
continue;
}
let start = index;
let mut end = index;
while end < script.len() {
if script[end] != Step::Shared {
end += 1;
continue;
}
// A shared run shorter than the context on both sides belongs to this hunk.
let shared_start = end;
let mut shared_end = end;
while shared_end < script.len() && script[shared_end] == Step::Shared {
shared_end += 1;
}
if shared_end - shared_start <= 2 * CONTEXT && shared_end < script.len() {
end = shared_end;
continue;
}
end = shared_start;
break;
}
let window_start = start.saturating_sub(CONTEXT);
let window_end = (end + CONTEXT).min(script.len());
let (base_start, target_start) = positions[window_start];
let (base_end, target_end) = positions[window_end];
match hunks.last_mut() {
Some(last) if window_start <= last.1 => {
last.1 = base_end;
last.3 = target_end;
}
_ => hunks.push((base_start, base_end, target_start, target_end)),
}
index = end;
}
hunks
.into_iter()
.map(
|(base_start, base_end, target_start, target_end)| LinePatch {
source: source.to_string(),
start_line: base_start + 1,
old_lines: base_lines[base_start..base_end]
.iter()
.map(|line| (*line).to_string())
.collect(),
new_lines: target_lines[target_start..target_end]
.iter()
.map(|line| (*line).to_string())
.collect(),
},
)
.collect()
}
/// Apply patches to a base text, returning the result only when every patch found its place.
///
/// `None` means the patch did not fit: the caller must treat that as "no patch", never as a
/// reason to guess.
#[must_use]
pub fn apply(base: &str, patches: &[LinePatch]) -> Option<String> {
let mut lines: Vec<String> = lines_of(base)
.iter()
.map(|line| (*line).to_string())
.collect();
let mut cursor = 0usize;
// Where each patch expects to be, tracked as the text moves under it. Text with repeated
// lines has many places a hunk could match, so position is tried before search: a patch that
// lands in the wrong one of forty identical lines would be caught by verification, but it
// would also cost the reader the whole text.
let mut shift: isize = 0;
for patch in patches {
let fits = |lines: &[String], at: usize, patch: &LinePatch| {
at >= cursor
&& at + patch.old_lines.len() <= lines.len()
&& lines[at..at + patch.old_lines.len()] == patch.old_lines[..]
};
let expected = (patch.start_line as isize - 1 + shift).max(0) as usize;
let found = if patch.old_lines.is_empty() {
expected.min(lines.len())
} else if fits(&lines, expected, patch) {
expected
} else {
(cursor..lines.len()).find(|start| fits(&lines, *start, patch))?
};
lines.splice(
found..found + patch.old_lines.len(),
patch.new_lines.iter().cloned(),
);
shift += patch.new_lines.len() as isize - patch.old_lines.len() as isize;
cursor = found + patch.new_lines.len();
}
Some(lines.concat())
}
/// Render patches the way a reader sees them: a hunk header naming the source and line range,
/// then the removed lines, then the lines that replace them.
#[must_use]
pub fn render(patches: &[LinePatch]) -> String {
let mut out = String::new();
for patch in patches {
out.push_str(&format!(
"@@ {} · lines {}-{}\n",
patch.source,
patch.start_line,
patch.start_line + patch.old_lines.len().saturating_sub(1)
));
for line in &patch.old_lines {
out.push('-');
out.push_str(line.trim_end_matches('\n'));
out.push('\n');
}
for line in &patch.new_lines {
out.push('+');
out.push_str(line.trim_end_matches('\n'));
out.push('\n');
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
fn round_trip(base: &str, target: &str) {
let patches = patches(base, target, "instructions");
let applied = apply(base, &patches);
assert_eq!(
applied.as_deref(),
Some(target),
"patches must reproduce the target exactly\nrendered: {}",
render(&patches)
);
}
#[test]
fn an_addition_round_trips() {
round_trip("a\nb\nc\n", "a\nb\nnew\nc\n");
}
#[test]
fn a_deletion_round_trips() {
round_trip("a\nb\nc\n", "a\nc\n");
}
#[test]
fn a_rewrite_round_trips() {
round_trip("a\nb\nc\n", "x\ny\nz\n");
}
#[test]
fn scattered_edits_round_trip() {
let base = "one\ntwo\nthree\nfour\nfive\nsix\nseven\neight\nnine\nten\n";
let target = "one\nTWO\nthree\nfour\nfive\nsix\nseven\neight\nNINE\nten\n";
round_trip(base, target);
}
#[test]
fn a_missing_final_newline_survives() {
round_trip("a\nb", "a\nb\nc");
round_trip("a\nb\n", "a\nb");
}
#[test]
fn identical_texts_produce_no_patches() {
assert!(patches("same\n", "same\n", "s").is_empty());
assert!(patches("", "", "s").is_empty());
}
#[test]
fn an_empty_base_is_expressible() {
round_trip("", "brand new\ntext\n");
}
#[test]
fn a_patch_that_does_not_fit_is_not_applied() {
let patches = patches("a\nb\n", "a\nB\n", "s");
assert!(apply("unrelated\ntext\n", &patches).is_none());
}
#[test]
fn a_small_edit_is_a_small_patch() {
// The whole reason this module exists: an instruction revision should cost the size of
// its change, not the size of the instructions. A real case measured 239 bytes of patch
// against 8145 bytes of contract; the shape here is the same.
let base = (0..60)
.map(|n| format!("line {n}: a paragraph of instructions that does not change\n"))
.collect::<String>();
let mut target_lines: Vec<String> = (0..60)
.map(|n| format!("line {n}: a paragraph of instructions that does not change\n"))
.collect();
target_lines[30] = "line 30: this paragraph is the one that changed\n".into();
let target = target_lines.concat();
let patches = patches(&base, &target, "contract.md");
let rendered = render(&patches);
assert!(patches.len() == 1, "{rendered}");
assert!(
rendered.len() * 5 < target.len(),
"patch {} bytes vs text {} bytes: a patch tracks the change, not the document",
rendered.len(),
target.len()
);
round_trip(&base, &target);
}
#[test]
fn the_real_contract_revision_is_a_two_line_patch() {
// The bytes from the live dogfood session: a pinned header of 7949 bytes, a revision of
// 8145 bytes, and the difference being one paragraph plus a blank line.
let base: String = (0..99)
.map(|n| format!("line {n} of the contract\n"))
.collect::<String>()
+ "\n## skills\n";
let target = base.replace(
"\n## skills\n",
"\nA revision you observe is not a suggestion.\n\n## skills\n",
);
let patches = patches(&base, &target, "runtime-contract.md");
let rendered = render(&patches);
assert!(
rendered.len() < 400,
"an appended paragraph should cost its own bytes, got {}:\n{rendered}",
rendered.len()
);
assert!(
rendered.contains("-\n") && rendered.contains("+A revision you observe"),
"{rendered}"
);
round_trip(&base, &target);
}
#[test]
fn hunks_do_not_overlap_so_they_apply_in_order() {
let base = (0..40).map(|n| format!("line {n}\n")).collect::<String>();
let mut target_lines: Vec<String> = (0..40).map(|n| format!("line {n}\n")).collect();
target_lines[1] = "line 1 changed\n".into();
target_lines[3] = "line 3 changed\n".into();
let target = target_lines.concat();
let patches = patches(&base, &target, "s");
for pair in patches.windows(2) {
let first_end = pair[0].start_line + pair[0].old_lines.len();
assert!(
pair[1].start_line >= first_end,
"hunks must not overlap: {:?} then {:?}",
pair[0],
pair[1]
);
}
round_trip(&base, &target);
}
}