use super::super::depth_one_map::Packet;
use super::*;
use crate::reply_pack::PACKET_DATA;
pub(crate) fn map_of(path: &Path, format: ObjectFormat) -> Option<(Vec<String>, u64)> {
let (_, map) = Map::of(path, format)?;
let entries = map
.entries
.iter()
.map(|entry| entry.oid.to_string())
.collect();
Some((entries, map.padding))
}
#[test]
fn a_run_costs_what_it_cant_share() {
let data = PACKET_DATA as u64;
let packet = |n: u64, len: usize| Packet {
file: 100 + n * (data + 5),
pack: n * data,
len: len as u32,
};
let null = ObjectId::null(gix::hash::Kind::Sha1);
let one = NonZeroU32::new(1).unwrap();
let map = Map {
format: ObjectFormat::SHA1,
entries: [12, 100, 200]
.map(|offset| MapEntry {
oid: null,
offset,
paths: one,
})
.to_vec(),
packets: vec![
packet(0, PACKET_DATA),
packet(1, PACKET_DATA),
packet(2, PACKET_DATA),
packet(3, 1000),
],
pack_len: 3 * data + 1000,
padding: 0,
total_size: 1000,
trailer: null,
};
assert_eq!(runs_cost(&map, &[(1, 2)]), (100, 100));
// the shares below come from packets 1 and 2 at file bytes 65,620..196,660.
assert_eq!(
runs_cost(&map, &[(2, 3)]),
(197_325, 65_315 + 980 + 4_064 + 10_240)
);
assert_eq!(
runs_cost(&map, &[(1, 2), (2, 3)]),
(197_425, 100 + 65_315 + 980 + 4_064 + 10_240)
);
}
fn git(repo: &Path, args: &[&str], stdin: &[u8]) -> String {
let mut command = crate::test_git();
command.current_dir(repo).args(args);
command
.env("GIT_AUTHOR_NAME", "t")
.env("GIT_AUTHOR_EMAIL", "t@t");
command
.env("GIT_COMMITTER_NAME", "t")
.env("GIT_COMMITTER_EMAIL", "t@t");
command.stdin(stdin_bytes(stdin).unwrap());
let output = command.output().unwrap();
assert!(
output.status.success(),
"git {args:?}: {}",
String::from_utf8_lossy(&output.stderr)
);
String::from_utf8(output.stdout).unwrap().trim().to_string()
}
fn commit(repo: &Path, files: &[(Vec<u8>, String)]) -> ObjectId {
let mut tree = Vec::new();
for (name, text) in files {
let blob = git(repo, &["hash-object", "-w", "--stdin"], text.as_bytes());
tree.extend_from_slice(format!("100644 blob {blob}\t").as_bytes());
tree.extend_from_slice(name);
tree.push(b'\n');
}
let tree = git(repo, &["mktree"], &tree);
let commit = git(repo, &["commit-tree", &tree, "-m", "c"], b"");
ObjectId::from_hex(commit.as_bytes()).unwrap()
}
fn noise(seed: u64, len: usize) -> String {
let mut state = seed.wrapping_add(1);
(0..len)
.map(|_| {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
char::from(b'a' + (state >> 59) as u8 % 26)
})
.collect()
}
fn files(range: std::ops::Range<u64>, len: usize) -> Vec<(Vec<u8>, String)> {
range
.map(|n| (format!("f-{n:03}").into_bytes(), noise(n, len)))
.collect()
}
fn assert_reply(repo: &Path, format: ObjectFormat, path: &Path, tip: &ObjectId) {
let (reply, map) = Map::of(path, format).expect("a map");
let mut pack = Vec::new();
map.stream(&reply, 0, map.pack_len, &mut |bytes| {
pack.extend_from_slice(bytes);
Ok(())
})
.unwrap();
let check = tempfile::tempdir().unwrap();
let object_format = format!("--object-format={}", format.capability());
git(check.path(), &["init", "-q", "--bare", &object_format], b"");
git(check.path(), &["index-pack", "--strict", "--stdin"], &pack);
let all = [
"cat-file",
"--batch-all-objects",
"--batch-check=%(objectname)",
];
let mut packed: Vec<String> = git(check.path(), &all, b"")
.lines()
.map(str::to_string)
.collect();
let mut reached: Vec<String> = (depth_one(repo, tip).unwrap().iter())
.map(ObjectId::to_string)
.collect();
packed.sort();
reached.sort();
assert_eq!(packed, reached);
}
fn repo(format: &str) -> tempfile::TempDir {
let dir = tempfile::tempdir().unwrap();
let object_format = format!("--object-format={format}");
git(dir.path(), &["init", "-q", "--bare", &object_format], b"");
dir
}
#[test]
fn a_tree_of_names_that_arent_utf8_is_cut_and_built() {
let repo = repo("sha1");
let format = ObjectFormat::SHA1;
let mut tree = files(0..40, 2048);
tree.push((b"bad\xffname".to_vec(), "bad\n".into()));
let first = commit(repo.path(), &tree);
let out = tempfile::tempdir().unwrap();
let cut = out.path().join("cut");
reply(repo.path(), format, &first, &cut, &[]).unwrap();
assert_reply(repo.path(), format, &cut, &first);
tree[0].1 = "changed\n".into();
let second = commit(repo.path(), &tree);
let built = out.path().join("built");
reply(repo.path(), format, &second, &built, &[cut]).unwrap();
assert_reply(repo.path(), format, &built, &second);
}
#[test]
fn a_sha256_reply_is_built_and_framed_again() {
let repo = repo("sha256");
let format = ObjectFormat::from_capability("sha256").unwrap();
let mut tree = files(0..60, 128 * 1024);
let out = tempfile::tempdir().unwrap();
let mut prior = out.path().join("reply-0");
let tip = commit(repo.path(), &tree);
reply(repo.path(), format, &tip, &prior, &[]).unwrap();
let mut paddings = Vec::new();
for step in 1..60 {
// changing two files half a tree apart splits the kept runs.
for at in [step * 7 % 60, (step * 7 + 30) % 60] {
tree[at].1 = noise((100 + step * 60 + at) as u64, 128 * 1024);
}
let tip = commit(repo.path(), &tree);
let path = out.path().join(format!("reply-{step}"));
reply(repo.path(), format, &tip, &path, &[prior]).unwrap();
assert_reply(repo.path(), format, &path, &tip);
let (entries, padding) = map_of(&path, format).unwrap();
assert_ne!(entries[0], tip.to_string(), "built");
paddings.push(padding);
prior = path;
if paddings.len() > 1 && padding == 0 {
return;
}
}
panic!("never framed again: {paddings:?}");
}
#[test]
fn a_corrupt_map_is_none() {
let repo = repo("sha1");
let format = ObjectFormat::SHA1;
let tip = commit(repo.path(), &files(0..20, 3000));
let out = tempfile::tempdir().unwrap();
let path = out.path().join("reply");
reply(repo.path(), format, &tip, &path, &[]).unwrap();
let good = std::fs::read(map_path(&path)).unwrap();
assert!(Map::of(&path, format).is_some());
let write = |bytes: &[u8]| {
std::fs::remove_file(map_path(&path)).unwrap();
std::fs::write(map_path(&path), bytes).unwrap();
};
for at in 0..good.len() {
for flip in [0x01, 0x80, 0xff] {
let mut bad = good.clone();
bad[at] ^= flip;
write(&bad);
assert!(Map::of(&path, format).is_none(), "byte {at} ^ {flip:#x}");
}
}
write(&good[..good.len() / 2]);
assert!(Map::of(&path, format).is_none());
let wrong: [&dyn Fn(&mut Map); 9] = [
&|map| map.pack_len = 3,
&|map| map.pack_len = u64::MAX,
&|map| map.padding += 5,
&|map| map.packets[0].file += 5,
&|map| map.packets[0].file = u64::MAX - 2,
&|map| map.packets[0].len = 0,
&|map| map.entries[1].oid = map.entries[0].oid,
&|map| map.entries[0].offset = 13,
&|map| map.entries.truncate(3),
];
for (n, wrong) in wrong.iter().enumerate() {
let (_, mut map) = {
write(&good);
Map::of(&path, format).unwrap()
};
wrong(&mut map);
write(&map.bytes());
assert!(Map::of(&path, format).is_none(), "change {n}");
reply(
repo.path(),
format,
&tip,
&out.path().join("next"),
std::slice::from_ref(&path),
)
.unwrap();
}
}
#[test]
fn a_short_run_is_copied_without_padding() -> anyhow::Result<()> {
let dir = tempfile::tempdir()?;
let format = ObjectFormat::SHA1;
for (len, padded) in [(2 * BLOCK as usize, false), (8 * BLOCK as usize, true)] {
let source = File::options()
.read(true)
.write(true)
.create(true)
.truncate(true)
.open(dir.path().join("source"))?;
let mut writer = Writer::new(&source, format, &[b'x'; 100])?;
writer.pack(&crate::reply_pack::pack_header(1))?;
writer.packet(12)?;
writer.pack(&vec![7; len])?;
writer.packet(len)?;
let map = writer.finish()?;
let target = File::options()
.read(true)
.write(true)
.create(true)
.truncate(true)
.open(dir.path().join("target"))?;
let mut writer = Writer::new(&target, format, &[b'y'; 333])?;
writer.copy(&source, &map, 12, 12 + len as u64)?;
assert_eq!(writer.padding > 0, padded, "{len} bytes");
}
Ok(())
}
#[test]
fn a_reply_whose_packets_or_padding_disagree_with_its_map_is_cut_afresh() -> anyhow::Result<()> {
use std::os::unix::fs::FileExt as _;
let repo = repo("sha1");
let format = ObjectFormat::SHA1;
let mut tree = files(0..40, 64 * 1024);
let first = commit(repo.path(), &tree);
let out = tempfile::tempdir()?;
let cut_reply = out.path().join("cut");
reply(repo.path(), format, &first, &cut_reply, &[])?;
tree[10].1 = "changed-10\n".into();
let second = commit(repo.path(), &tree);
let padded = out.path().join("padded");
reply(repo.path(), format, &second, &padded, &[cut_reply])?;
let (_, map) = Map::of(&padded, format).expect("a map");
assert!(map.packets.len() >= 4 && map.padding > 0);
tree[20].1 = "changed-20\n".into();
let third = commit(repo.path(), &tree);
// the header of packet 2, which Map::of never reads.
let bad_header = out.path().join("bad-header");
std::fs::copy(&padded, &bad_header)?;
std::fs::copy(map_path(&padded), map_path(&bad_header))?;
let file = File::options().write(true).open(&bad_header)?;
file.write_all_at(b"0005\x02", map.packets[2].file)?;
drop(file);
assert!(
Map::of(&bad_header, format).is_some(),
"Map::of doesn't read every interior packet header"
);
let after_header = out.path().join("after-header");
reply(repo.path(), format, &third, &after_header, &[bad_header])?;
assert_reply(repo.path(), format, &after_header, &third);
let (entries, _) = map_of(&after_header, format).unwrap();
assert_eq!(
entries[0],
third.to_string(),
"cut afresh on bad packet header"
);
let gap_at = map
.packets
.windows(2)
.filter_map(|pair| (pair[1].file > pair[0].file_end()).then_some(pair[0].file_end()))
.nth(1)
.expect("padding before the second shared run");
let bad_pad = out.path().join("bad-pad");
std::fs::copy(&padded, &bad_pad)?;
std::fs::copy(map_path(&padded), map_path(&bad_pad))?;
let file = File::options().write(true).open(&bad_pad)?;
file.write_all_at(b"0005\x01", gap_at)?;
drop(file);
let after_pad = out.path().join("after-pad");
reply(repo.path(), format, &third, &after_pad, &[bad_pad])?;
assert_reply(repo.path(), format, &after_pad, &third);
let (entries, _) = map_of(&after_pad, format).unwrap();
assert_eq!(entries[0], third.to_string(), "cut afresh on bad padding");
Ok(())
}
#[test]
fn worth_building_scales_by_kept_size_without_reading_kept_headers() -> anyhow::Result<()> {
let full = repo("sha1");
let format = ObjectFormat::SHA1;
let mut tree = files(0..20, 64 * 1024);
tree.push((b"tiny".to_vec(), "x".into()));
let first = commit(full.path(), &tree);
let out = tempfile::tempdir()?;
let prior = out.path().join("prior");
reply(full.path(), format, &first, &prior, &[])?;
let (_, map) = Map::of(&prior, format).expect("a map");
// scaling by the dropped ratio would exceed kept bytes and falsely cut afresh.
tree.pop();
tree.push((b"added".to_vec(), noise(777, 600 * 1024)));
let second = commit(full.path(), &tree);
let next = out.path().join("next");
reply(
full.path(),
format,
&second,
&next,
std::slice::from_ref(&prior),
)?;
assert_reply(full.path(), format, &next, &second);
let (entries, _) = map_of(&next, format).unwrap();
assert_ne!(
entries[0],
second.to_string(),
"built when dropping a 1-byte blob"
);
let sparse = repo("sha1");
let dropped_oid = map.entries[0].oid;
let full_repo = knot_git::Repo::open(full.path())?;
let dropped_obj = full_repo.git().find_object(dropped_oid)?;
let kind_name = match dropped_obj.kind {
gix::object::Kind::Commit => "commit",
gix::object::Kind::Tree => "tree",
gix::object::Kind::Blob => "blob",
gix::object::Kind::Tag => "tag",
};
git(
sparse.path(),
&["hash-object", "-w", "-t", kind_name, "--stdin"],
&dropped_obj.data,
);
let added_hex = git(
sparse.path(),
&["hash-object", "-w", "--stdin"],
noise(999, 1024).as_bytes(),
);
let added = [ObjectId::from_hex(added_hex.as_bytes())?];
let sparse_repo = knot_git::Repo::open(sparse.path())?;
let runs = [(1, map.entries.len())];
assert!(worth_building(sparse_repo.git(), &map, &runs, &added)?);
Ok(())
}
#[test]
fn tree_diff_matches_rev_list_across_moves_duplicates_submodules_and_modes() -> anyhow::Result<()> {
let repo = repo("sha1");
let format = ObjectFormat::SHA1;
let out = tempfile::tempdir()?;
let write_blob = |text: &str| {
git(
repo.path(),
&["hash-object", "-w", "--stdin"],
text.as_bytes(),
)
};
let mk_tree = |lines: &[String]| git(repo.path(), &["mktree"], lines.join("\n").as_bytes());
let mk_commit = |tree: &str, msg: &str| {
let hex = git(repo.path(), &["commit-tree", tree, "-m", msg], b"");
ObjectId::from_hex(hex.as_bytes()).unwrap()
};
// the big unchanged subtree keeps each step worth building from the prior.
let mut big_lines = Vec::new();
for n in 0..40 {
let b = write_blob(&noise(n, 64 * 1024));
big_lines.push(format!("100644 blob {b}\tbig-{n:02}"));
}
let shared_blob = write_blob(&noise(500, 4096));
let moved_blob = write_blob(&noise(501, 4096));
let mode_blob = write_blob(&noise(502, 4096));
let sub_oid = "1111111111111111111111111111111111111111";
let keep_sub = mk_tree(&[format!("100644 blob {shared_blob}\tstay")]);
let mut big_with_keep = big_lines.clone();
big_with_keep.push(format!("040000 tree {keep_sub}\tkeep"));
let unchanged_dir = mk_tree(&big_with_keep);
let sub_a = mk_tree(&[format!("100644 blob {moved_blob}\ta")]);
let work_1 = mk_tree(&[
format!("100644 blob {shared_blob}\tdup"),
format!("100644 blob {mode_blob}\texec"),
format!("040000 tree {sub_a}\tleft"),
format!("160000 commit {sub_oid}\tsubmod"),
]);
let root_1 = mk_tree(&[
format!("040000 tree {unchanged_dir}\tunchanged"),
format!("040000 tree {work_1}\twork"),
]);
let tip_1 = mk_commit(&root_1, "step-1");
let reply_1 = out.path().join("reply-1");
reply(repo.path(), format, &tip_1, &reply_1, &[])?;
assert_reply(repo.path(), format, &reply_1, &tip_1);
let sub_b = mk_tree(&[format!("100644 blob {moved_blob}\tb")]);
let sub_oid_2 = "2222222222222222222222222222222222222222";
let work_2 = mk_tree(&[
format!("100755 blob {mode_blob}\texec"),
format!("040000 tree {sub_b}\tright"),
format!("160000 commit {sub_oid_2}\tsubmod"),
]);
let root_2 = mk_tree(&[
format!("040000 tree {unchanged_dir}\tunchanged"),
format!("040000 tree {work_2}\twork"),
]);
let tip_2 = mk_commit(&root_2, "step-2");
let reply_2 = out.path().join("reply-2");
reply(
repo.path(),
format,
&tip_2,
&reply_2,
std::slice::from_ref(&reply_1),
)?;
assert_reply(repo.path(), format, &reply_2, &tip_2);
let (entries_2, _) = map_of(&reply_2, format).unwrap();
assert_ne!(entries_2[0], tip_2.to_string(), "built via tree diff");
let empty_keep = mk_tree(&[format!("100644 blob {mode_blob}\treplaced")]);
let mut big_no_dup = big_lines.clone();
big_no_dup.push(format!("040000 tree {empty_keep}\tkeep"));
let unchanged_dir_3 = mk_tree(&big_no_dup);
let root_3 = mk_tree(&[
format!("040000 tree {unchanged_dir_3}\tunchanged"),
format!("040000 tree {work_2}\twork"),
]);
let tip_3 = mk_commit(&root_3, "step-3");
let reply_3 = out.path().join("reply-3");
reply(repo.path(), format, &tip_3, &reply_3, &[reply_2])?;
assert_reply(repo.path(), format, &reply_3, &tip_3);
let (entries_3, _) = map_of(&reply_3, format).unwrap();
assert_ne!(entries_3[0], tip_3.to_string(), "built via tree diff");
assert!(
!entries_3.contains(&shared_blob),
"dropped once last path is gone"
);
// the sparse repo has no `unchanged_dir` or its blobs.
// diff must not read them or fall back to `git rev-list`.
let sparse = super::tests::repo("sha1");
let full_repo = knot_git::Repo::open(repo.path())?;
for hex in [
tip_1.to_string(),
root_1,
work_1,
sub_a,
tip_2.to_string(),
root_2,
work_2,
sub_b,
] {
let oid = ObjectId::from_hex(hex.as_bytes())?;
let obj = full_repo.git().find_object(oid)?;
let kind_name = match obj.kind {
gix::object::Kind::Commit => "commit",
gix::object::Kind::Tree => "tree",
gix::object::Kind::Blob => "blob",
gix::object::Kind::Tag => "tag",
};
git(
sparse.path(),
&["hash-object", "-w", "-t", kind_name, "--stdin"],
&obj.data,
);
}
let (_, map_1) = Map::of(&reply_1, format).expect("a map");
let sparse_repo = knot_git::Repo::open(sparse.path())?;
let (runs, added) = diff(sparse_repo.git(), &map_1, &tip_2)?.expect("tree diff");
let mut built_set: HashSet<String> = runs
.iter()
.flat_map(|&((start, end), _)| {
map_1.entries[start..end]
.iter()
.map(|entry| entry.oid.to_string())
})
.chain(added.iter().map(|(oid, _)| oid.to_string()))
.collect();
let expected_set: HashSet<String> = depth_one(repo.path(), &tip_2)?
.into_iter()
.map(|oid| oid.to_string())
.collect();
assert_eq!(built_set.drain().collect::<HashSet<_>>(), expected_set);
Ok(())
}