use std::collections::HashSet;
use std::fs::File;
use std::io::Read as _;
use std::num::NonZeroU32;
use std::os::unix::fs::FileExt as _;
use std::path::{Path, PathBuf};
use anyhow::Context as _;
use gix::hash::ObjectId;
use knot_types::ObjectFormat;
use crate::git_export::{git_command, pkt_line, run_cmd, stdin_bytes, write_unlinked_making};
use crate::reply_pack::BLOCK;
/// a shared run is charged 2.5 blocks of padding.
const RUN_PADDING: u64 = 5 * BLOCK / 2;
/// a reply drops its padding once that is over 1/20 of the pack.
const PADDING: u64 = 20;
/// runs shorter than this cost more in padding and edges than they save.
pub(super) const SHARED_AT_LEAST: u64 = 4 * BLOCK;
pub(crate) fn map_path(reply: &Path) -> PathBuf {
let mut name = reply.file_name().unwrap_or_default().to_owned();
name.push(".map");
reply.with_file_name(name)
}
pub(crate) fn reply(
export_dir: &Path,
format: ObjectFormat,
tip: &ObjectId,
path: &Path,
like: &[PathBuf],
) -> anyhow::Result<u64> {
let repo = knot_git::Repo::open(export_dir).context("open the export")?;
for like in like {
let Some((reply, map)) = Map::of(like, format) else {
continue;
};
let Some((runs, added)) = diff(repo.git(), &map, tip)? else {
continue;
};
let run_ranges: Vec<(usize, usize)> = runs.iter().map(|&(run, _)| run).collect();
let added_ids: Vec<ObjectId> = added.iter().map(|(oid, _)| *oid).collect();
if !worth_building(repo.git(), &map, &run_ranges, &added_ids)? {
continue;
}
let built = write_reply(path, tip, |file| {
rebuild(repo.git(), &reply, &map, &runs, &added, tip, file)
});
match built {
Ok(len) => return Ok(len),
Err(error) => crate::git_export::ExportTrace::new().note(format_args!(
"export: {} cut afresh, not built from {}: {error:#}",
path.display(),
like.display()
)),
}
}
let objects = depth_one(export_dir, tip)?;
let counts = tree_counts(repo.git(), tip)?;
write_reply(path, tip, |file| {
cut(export_dir, format, tip, &objects, &counts, path, file)
})
}
fn write_reply(
path: &Path,
tip: &ObjectId,
fill: impl FnOnce(&File) -> anyhow::Result<Map>,
) -> anyhow::Result<u64> {
let (mut len, mut map) = write_unlinked_making(path, |file| fill(file))?;
if map.padding > map.pack_len / PADDING {
let reply = File::open(path).with_context(|| format!("open {}", path.display()))?;
(len, map) = write_unlinked_making(path, |file| {
let mut writer = Writer::new(file, map.format, &prefix(tip))?;
map.stream(&reply, 0, map.body(), &mut |bytes| writer.pack(bytes))?;
writer.entries = map.entries.clone();
writer.total_size = map.total_size;
writer.finish()
})?;
}
crate::git_export::write_unlinked(&map_path(path), &map.bytes())?;
Ok(len)
}
fn depth_one(export_dir: &Path, tip: &ObjectId) -> anyhow::Result<Vec<ObjectId>> {
let mut walk = git_command(export_dir);
walk.args(["rev-list", "--objects", "--no-object-names", "--no-walk"]);
walk.arg(tip.to_string());
let listed = run_cmd(walk, "git rev-list --objects")?.stdout;
(listed.split(|byte| *byte == b'\n'))
.filter(|line| !line.is_empty())
.map(|line| {
ObjectId::from_hex(line)
.with_context(|| format!("rev-list line {:?}", String::from_utf8_lossy(line)))
})
.collect()
}
fn tree_counts(
repo: &gix::Repository,
tip: &ObjectId,
) -> anyhow::Result<std::collections::HashMap<ObjectId, NonZeroU32>> {
let kind = repo.object_hash();
let commit = repo
.find_object(*tip)
.with_context(|| format!("read {tip}"))?;
let root = gix::objs::CommitRefIter::from_bytes(&commit.data, kind)
.tree_id()
.with_context(|| format!("parse commit {tip}"))?;
let mut deltas = std::collections::HashMap::from([(*tip, 1i64)]);
let mut added = Vec::new();
let mut seen = HashSet::new();
walk_delta(
repo,
kind,
true,
root,
1,
&mut deltas,
&mut added,
&mut seen,
)?;
deltas
.into_iter()
.map(|(oid, n)| {
let count = u32::try_from(n)
.ok()
.and_then(NonZeroU32::new)
.context("path count out of u32 range")?;
Ok((oid, count))
})
.collect()
}
type DiffResult = (
Vec<((usize, usize), Vec<NonZeroU32>)>,
Vec<(ObjectId, NonZeroU32)>,
);
fn diff(repo: &gix::Repository, map: &Map, tip: &ObjectId) -> anyhow::Result<Option<DiffResult>> {
let kind = repo.object_hash();
let old_tip = [map.entries.last(), map.entries.first()]
.into_iter()
.flatten()
.map(|entry| entry.oid)
.find(|oid| {
repo.find_header(*oid)
.is_ok_and(|h| h.kind() == gix::object::Kind::Commit)
});
let Some(old_tip) = old_tip else {
return Ok(None);
};
let Ok(old_commit) = repo.find_object(old_tip) else {
return Ok(None);
};
let new_commit = repo
.find_object(*tip)
.with_context(|| format!("read {tip}"))?;
if old_commit.kind != gix::object::Kind::Commit || new_commit.kind != gix::object::Kind::Commit
{
return Ok(None);
}
let old_root = gix::objs::CommitRefIter::from_bytes(&old_commit.data, kind).tree_id()?;
let new_root = gix::objs::CommitRefIter::from_bytes(&new_commit.data, kind).tree_id()?;
let mut deltas: std::collections::HashMap<ObjectId, i64> = std::collections::HashMap::new();
let mut added_candidates: Vec<ObjectId> = Vec::new();
let mut seen_added: HashSet<ObjectId> = HashSet::new();
if old_tip != *tip {
*deltas.entry(old_tip).or_default() -= 1;
*deltas.entry(*tip).or_default() += 1;
}
if old_root != new_root {
diff_trees(
repo,
kind,
old_root,
new_root,
&mut deltas,
&mut added_candidates,
&mut seen_added,
)?;
}
if old_tip != *tip && seen_added.insert(*tip) {
added_candidates.push(*tip);
}
let mut prior_set: HashSet<ObjectId> = HashSet::with_capacity(map.entries.len());
let mut runs: Vec<((usize, usize), Vec<NonZeroU32>)> = Vec::new();
for (at, entry) in map.entries.iter().enumerate() {
prior_set.insert(entry.oid);
let next = i64::from(entry.paths.get()) + deltas.get(&entry.oid).copied().unwrap_or(0);
if next < 0 {
return Ok(None);
}
let Ok(next) = u32::try_from(next) else {
return Ok(None);
};
let Some(next) = NonZeroU32::new(next) else {
continue;
};
match runs.last_mut() {
Some(((_, end), counts)) if *end == at => {
*end = at + 1;
counts.push(next);
}
_ => runs.push(((at, at + 1), vec![next])),
}
}
let mut added: Vec<(ObjectId, NonZeroU32)> = Vec::new();
for oid in added_candidates {
if prior_set.contains(&oid) {
continue;
}
let next = deltas.get(&oid).copied().unwrap_or(0);
if next > 0 {
let paths = u32::try_from(next)
.ok()
.and_then(NonZeroU32::new)
.context("too many paths")?;
added.push((oid, paths));
}
}
Ok(Some((runs, added)))
}
fn diff_trees(
repo: &gix::Repository,
kind: gix::hash::Kind,
old_tree: ObjectId,
new_tree: ObjectId,
counts: &mut std::collections::HashMap<ObjectId, i64>,
added: &mut Vec<ObjectId>,
seen_added: &mut HashSet<ObjectId>,
) -> anyhow::Result<()> {
*counts.entry(old_tree).or_default() -= 1;
*counts.entry(new_tree).or_default() += 1;
if seen_added.insert(new_tree) {
added.push(new_tree);
}
let old_obj = repo.find_object(old_tree)?;
let new_obj = repo.find_object(new_tree)?;
let old_entries: std::collections::BTreeMap<
&gix::bstr::BStr,
(gix::objs::tree::EntryMode, ObjectId),
> = gix::objs::TreeRefIter::from_bytes(&old_obj.data, kind)
.map(|e| e.map(|e| (e.filename, (e.mode, e.oid.to_owned()))))
.collect::<Result<_, _>>()?;
let new_entries: std::collections::BTreeMap<
&gix::bstr::BStr,
(gix::objs::tree::EntryMode, ObjectId),
> = gix::objs::TreeRefIter::from_bytes(&new_obj.data, kind)
.map(|e| e.map(|e| (e.filename, (e.mode, e.oid.to_owned()))))
.collect::<Result<_, _>>()?;
for (name, &(old_mode, old_oid)) in &old_entries {
if old_mode.is_commit() {
continue;
}
match new_entries.get(name) {
Some(&(new_mode, new_oid))
if !new_mode.is_commit()
&& old_oid == new_oid
&& old_mode.is_tree() == new_mode.is_tree() => {}
Some(&(new_mode, new_oid)) if old_mode.is_tree() && new_mode.is_tree() => {
diff_trees(repo, kind, old_oid, new_oid, counts, added, seen_added)?;
}
_ => {
walk_delta(
repo,
kind,
old_mode.is_tree(),
old_oid,
-1,
counts,
added,
seen_added,
)?;
}
}
}
for (name, &(new_mode, new_oid)) in &new_entries {
if new_mode.is_commit() {
continue;
}
match old_entries.get(name) {
Some(&(old_mode, old_oid))
if !old_mode.is_commit()
&& old_oid == new_oid
&& old_mode.is_tree() == new_mode.is_tree() => {}
Some(&(old_mode, _)) if old_mode.is_tree() && new_mode.is_tree() => {}
_ => {
walk_delta(
repo,
kind,
new_mode.is_tree(),
new_oid,
1,
counts,
added,
seen_added,
)?;
}
}
}
Ok(())
}
fn walk_delta(
repo: &gix::Repository,
kind: gix::hash::Kind,
is_tree: bool,
oid: ObjectId,
sign: i64,
counts: &mut std::collections::HashMap<ObjectId, i64>,
added: &mut Vec<ObjectId>,
seen_added: &mut HashSet<ObjectId>,
) -> anyhow::Result<()> {
*counts.entry(oid).or_default() += sign;
if sign > 0 && seen_added.insert(oid) {
added.push(oid);
}
if is_tree {
let obj = repo.find_object(oid)?;
for entry in gix::objs::TreeRefIter::from_bytes(&obj.data, kind) {
let entry = entry?;
if !entry.mode.is_commit() {
walk_delta(
repo,
kind,
entry.mode.is_tree(),
entry.oid.to_owned(),
sign,
counts,
added,
seen_added,
)?;
}
}
}
Ok(())
}
pub(super) fn prefix(tip: &ObjectId) -> Vec<u8> {
let mut prefix = pkt_line(b"shallow-info\n");
prefix.extend(pkt_line(format!("shallow {tip}").as_bytes()));
prefix.extend_from_slice(b"0001");
prefix.extend(pkt_line(b"packfile\n"));
prefix
}
/// no deltas, because a later build shares entries as whole bytes.
fn cut(
export_dir: &Path,
format: ObjectFormat,
tip: &ObjectId,
objects: &[ObjectId],
counts: &std::collections::HashMap<ObjectId, NonZeroU32>,
path: &Path,
file: &File,
) -> anyhow::Result<Map> {
let staging = tempfile::Builder::new()
.prefix(".depth-one-cut")
.tempdir_in(path.parent().context("a reply outside a directory")?)?;
let base = std::path::absolute(staging.path().join("pack"))?;
let listed: String = objects.iter().map(|oid| format!("{oid}\n")).collect();
let mut pack = git_command(export_dir);
pack.args(["pack-objects", "-q", "--window=0", "--depth=0"]);
pack.args(["--no-reuse-delta"]).arg(&base);
pack.stdin(stdin_bytes(listed.as_bytes())?);
let name = String::from_utf8(run_cmd(pack, "git pack-objects")?.stdout)?;
let pack = staging.path().join(format!("pack-{}.pack", name.trim()));
let index = gix::odb::pack::index::File::at(pack.with_extension("idx"), format.kind())
.context("open the cut's index")?;
let one = NonZeroU32::new(1).expect("nonzero");
let mut entries: Vec<MapEntry> = (index.iter())
.map(|entry| MapEntry {
oid: entry.oid,
offset: entry.pack_offset,
paths: counts.get(&entry.oid).copied().unwrap_or(one),
})
.collect();
entries.sort_unstable_by_key(|entry| entry.offset);
let mut source = File::open(&pack).context("open the cut")?;
let total_size = entries
.iter()
.map(|entry| entry_uncompressed_size(&source, entry.offset))
.sum::<anyhow::Result<u64>>()?;
let mut writer = Writer::new(file, format, &prefix(tip))?;
let body = (source.metadata()?.len())
.checked_sub(format.kind().len_in_bytes() as u64)
.context("a cut too short for a pack")?;
let mut chunk = vec![0; 1 << 20];
let mut left = body;
while left > 0 {
let now = &mut chunk[..left.min(1 << 20) as usize];
source.read_exact(now).context("read the cut")?;
writer.pack(now)?;
left -= now.len() as u64;
}
writer.entries = entries;
writer.total_size = total_size;
writer.finish()
}
fn entry_uncompressed_size(pack: &File, offset: u64) -> anyhow::Result<u64> {
let mut header = [0u8; 10];
let n = pack
.read_at(&mut header, offset)
.context("read pack entry header")?;
anyhow::ensure!(n > 0, "pack entry header cut short");
let mut size = u64::from(header[0] & 0x0f);
let mut shift = 4u32;
let mut at = 0usize;
while header[at] & 0x80 != 0 {
at += 1;
let byte = *header.get(at).context("pack entry header too long")?;
size |= u64::from(byte & 0x7f) << shift;
shift += 7;
}
Ok(size)
}
/// many short runs cost about as much as a cut, since each one is written whole.
fn worth_building(
repo: &gix::Repository,
map: &Map,
runs: &[(usize, usize)],
added: &[ObjectId],
) -> anyhow::Result<bool> {
let size = |oid: &ObjectId| -> anyhow::Result<u64> {
Ok(repo
.find_header(*oid)
.with_context(|| format!("read {oid}"))?
.size())
};
let (kept_bytes, written) = runs_cost(map, runs);
let dropped_size = dropped_size(repo, map, runs)?;
let kept_size = map.total_size.saturating_sub(dropped_size);
let added_size = added.iter().map(size).sum::<anyhow::Result<u64>>()?;
if kept_size == 0 {
return Ok(false);
}
let added_bytes = (added_size as f64 * kept_bytes as f64 / kept_size as f64) as u64;
Ok(2 * (written + added_bytes) < kept_bytes + added_bytes)
}
fn dropped_size(repo: &gix::Repository, map: &Map, runs: &[(usize, usize)]) -> anyhow::Result<u64> {
let mut size = 0u64;
let mut at = 0usize;
for &(start, end) in runs {
for entry in &map.entries[at..start] {
size += repo
.find_header(entry.oid)
.with_context(|| format!("read {}", entry.oid))?
.size();
}
at = end;
}
for entry in &map.entries[at..] {
size += repo
.find_header(entry.oid)
.with_context(|| format!("read {}", entry.oid))?
.size();
}
Ok(size)
}
fn runs_cost(map: &Map, runs: &[(usize, usize)]) -> (u64, u64) {
let (mut kept, mut written) = (0u64, 0u64);
for &run in runs {
let (from, to) = map.span(run);
kept += to - from;
written += match map.share(from, to) {
Some(share) => {
let packets = &map.packets[share.packets];
let (a, b) = (packets[0], packets[packets.len() - 1]);
let edges = (share.end - share.start) - (share.high - share.low);
(a.pack - from) + (to - b.end()) + edges + RUN_PADDING
}
None => to - from,
};
}
(kept, written)
}
fn rebuild(
repo: &gix::Repository,
reply: &File,
map: &Map,
runs: &[((usize, usize), Vec<NonZeroU32>)],
added: &[(ObjectId, NonZeroU32)],
tip: &ObjectId,
file: &File,
) -> anyhow::Result<Map> {
let kept: usize = runs.iter().map(|((start, end), _)| end - start).sum();
let count = u32::try_from(kept + added.len()).context("too many objects")?;
let run_ranges: Vec<(usize, usize)> = runs.iter().map(|&(run, _)| run).collect();
let mut total_size = map
.total_size
.checked_sub(dropped_size(repo, map, &run_ranges)?)
.context("a map's total size is smaller than its dropped entries")?;
let mut writer = Writer::new(file, map.format, &prefix(tip))?;
writer.pack(&crate::reply_pack::pack_header(count))?;
for ((start, end), counts) in runs {
let (from, to) = map.span((*start, *end));
for (entry, &paths) in map.entries[*start..*end].iter().zip(counts) {
let at = entry.offset - from + writer.position();
writer.entries.push(MapEntry {
oid: entry.oid,
offset: at,
paths,
});
}
writer.copy(reply, map, from, to)?;
}
for &(oid, paths) in added {
let object = (repo.find_object(oid)).with_context(|| format!("read {oid}"))?;
total_size += object.data.len() as u64;
writer.entries.push(MapEntry {
oid,
offset: writer.position(),
paths,
});
writer.pack(&crate::packfile::whole_entry(object.kind, &object.data)?)?;
}
writer.total_size = total_size;
writer.finish()
}
pub(crate) use super::depth_one_map::{Map, MapEntry, Writer};
#[cfg(any(test, feature = "bench"))]
mod benches {
use super::*;
use crate::bench_fixture::repo;
struct Prior {
dir: tempfile::TempDir,
reply: File,
map: Map,
map_bytes: Vec<u8>,
tip: ObjectId,
}
fn prior(files: usize) -> Prior {
let dir = tempfile::tempdir().unwrap();
let export = dir.path().join("export");
let (base, tip) = repo(&export, files, 256, 4);
let path = dir.path().join("prior");
reply(&export, ObjectFormat::SHA1, &base, &path, &[]).unwrap();
let (reply, map) = Map::of(&path, ObjectFormat::SHA1).unwrap();
let map_bytes = std::fs::read(map_path(&path)).unwrap();
Prior {
dir,
reply,
map,
map_bytes,
tip,
}
}
fn opened(prior: &Prior) -> knot_git::Repo {
knot_git::Repo::open(prior.dir.path().join("export")).unwrap()
}
#[divan::bench(args = [100, 5_000])]
fn map_parse(bencher: divan::Bencher, files: usize) {
let prior = prior(files);
bencher.bench_local(|| {
divan::black_box(Map::parse(
divan::black_box(&prior.map_bytes),
ObjectFormat::SHA1,
))
});
}
#[divan::bench(args = [100, 5_000])]
fn tree_diff(bencher: divan::Bencher, files: usize) {
let prior = prior(files);
let repo = opened(&prior);
bencher.bench_local(|| divan::black_box(diff(repo.git(), &prior.map, &prior.tip).unwrap()));
}
#[divan::bench(args = [100, 5_000])]
fn worth_building(bencher: divan::Bencher, files: usize) {
let prior = prior(files);
let repo = opened(&prior);
let (runs, added) = diff(repo.git(), &prior.map, &prior.tip).unwrap().unwrap();
let runs: Vec<(usize, usize)> = runs.iter().map(|&(run, _)| run).collect();
let added: Vec<ObjectId> = added.iter().map(|(oid, _)| *oid).collect();
bencher.bench_local(|| {
divan::black_box(super::worth_building(repo.git(), &prior.map, &runs, &added).unwrap())
});
}
#[divan::bench(args = [100, 5_000])]
fn rebuild(bencher: divan::Bencher, files: usize) {
let prior = prior(files);
let repo = opened(&prior);
let (runs, added) = diff(repo.git(), &prior.map, &prior.tip).unwrap().unwrap();
bencher
.with_inputs(|| tempfile::tempfile_in(prior.dir.path()).unwrap())
.bench_local_values(|file| {
let map = super::rebuild(
repo.git(),
&prior.reply,
&prior.map,
&runs,
&added,
&prior.tip,
&file,
)
.unwrap();
(divan::black_box(map), file)
});
}
}
#[cfg(test)]
#[path = "tests/depth_one_unit.rs"]
pub(crate) mod tests;