Something went wrong. Try again.
Monorepo for Tangled forked from tangled.org/core
Something went wrong. Try again.
21 kB · 572 lines
Rust
at pull2
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573use gix::bstr::ByteSlice as _;use gix::objs::tree::EntryKind;use gix::{Commit, ObjectId};use line_numbers::{LineNumber, SingleLineSpan};use rustc_hash::FxHashSet;use tracing::info;
/// Blobs larger than this are treated as binary (reported by size only, not diffed),/// overriding gix's `core.bigFileThreshold` default of 512 MiB. Scoped to diffing only.const LARGE_FILE_THRESHOLD_BYTES: u64 = 1024 * 1024;
#[derive(Debug)]pub struct FileContent { pub(crate) path: String, pub(crate) oid: String, pub(crate) size: usize, pub(crate) is_binary: bool, /// True when this side is a submodule (gitlink); `oid` is then a commit id pointing into /// the submodule's repository, not a blob in this one. pub(crate) is_submodule: bool,}
/// A hunk represents a series of modified lines that are displayed/// together.#[derive(Debug, Clone)]pub struct Hunk { /// The LHS line numbers that contain novel content. pub(crate) novel_lhs: FxHashSet<LineNumber>, /// The RHS line numbers that contain novel content. pub(crate) novel_rhs: FxHashSet<LineNumber>, /// Line pairs that contain modified lines. This does not include /// padding, so at least one of the two lines has novel content. pub(crate) lines: Vec<(Option<LineNumber>, Option<LineNumber>)>,}
/// A matched token (an atom, a delimiter, or a comment word).#[derive(PartialEq, Eq, Debug, Clone)]enum MatchKind { // TBD}
#[derive(Debug, Clone, PartialEq, Eq)]struct MatchedPos { kind: MatchKind, pos: SingleLineSpan,}
#[derive(Debug)]pub struct Diff { pub(crate) lhs_src: FileContent, pub(crate) rhs_src: FileContent, pub(crate) hunks: Vec<Hunk>,
lhs_positions: Vec<MatchedPos>, rhs_positions: Vec<MatchedPos>,
/// If the two files do not have exactly the same bytes, the /// number of bytes in each file. pub(crate) has_byte_changes: Option<(usize, usize)>, pub(crate) has_syntactic_changes: bool,}
/// Diff two trees, yielding one [`Diff`] per changed file (line-level [`Hunk`]s included).////// Returns an iterator of `anyhow::Result<Diff>`: per-file diffing can fail independently, so/// each item is fallible. The consumer drives it lazily and can stop at any point by dropping/// the iterator (e.g. when the gRPC client hangs up).pub fn diff<'repo>( repo: &'repo gix::Repository, old_tree: &gix::Tree<'_>, new_tree: &gix::Tree<'_>,) -> anyhow::Result<DiffIter<'repo>> { let changes = repo.diff_tree_to_tree(Some(old_tree), Some(new_tree), None)?; let mut cache = repo.diff_resource_cache_for_tree_diff()?; cache.filter.options.large_file_threshold_bytes = LARGE_FILE_THRESHOLD_BYTES; Ok(DiffIter { repo, changes: changes.into_iter(), cache, })}
/// Lazy iterator over per-file [`Diff`]s. Created by [`diff`].pub struct DiffIter<'repo> { repo: &'repo gix::Repository, changes: std::vec::IntoIter<gix::object::tree::diff::ChangeDetached>, cache: gix::diff::blob::Platform,}
impl Iterator for DiffIter<'_> { type Item = anyhow::Result<Diff>;
fn next(&mut self) -> Option<Self::Item> { loop { let change = self.changes.next()?; let (old, new) = change_sides(&change); // Trees are recursed into by gix and never diffed directly; skip defensively. if old.is_kind(EntryKind::Tree) || new.is_kind(EntryKind::Tree) { continue; } // Submodules (gitlinks) can't go through the blob pipeline — their commit lives in // another repo. Emit the commit oids directly for the caller to compare. if old.is_kind(EntryKind::Commit) || new.is_kind(EntryKind::Commit) { return Some(Ok(submodule_diff(self.repo, &change, old, new))); } let result = build_diff(self.repo, &change, &mut self.cache); self.cache.clear_resource_cache_keep_allocation(); return Some(result); } }}
/// One side (old or new) of a change.enum Side { Absent, Present { oid: ObjectId, kind: EntryKind },}
impl Side { fn is_kind(&self, wanted: EntryKind) -> bool { matches!(self, Side::Present { kind, .. } if *kind == wanted) }}
/// Decompose a change into its `(old, new)` sides regardless of variant.fn change_sides(change: &gix::object::tree::diff::ChangeDetached) -> (Side, Side) { use gix::object::tree::diff::ChangeDetached as C; let present = |oid, mode: gix::object::tree::EntryMode| Side::Present { oid, kind: mode.kind(), }; match change { C::Addition { id, entry_mode, .. } => (Side::Absent, present(*id, *entry_mode)), C::Deletion { id, entry_mode, .. } => (present(*id, *entry_mode), Side::Absent), C::Modification { previous_id, previous_entry_mode, id, entry_mode, .. } => ( present(*previous_id, *previous_entry_mode), present(*id, *entry_mode), ), C::Rewrite { source_id, source_entry_mode, id, entry_mode, .. } => ( present(*source_id, *source_entry_mode), present(*id, *entry_mode), ), }}
/// Build a [`Diff`] for a submodule (gitlink) change: no hunks, both sides carry their commit/// oid with `is_submodule` set. The caller compares the oids as submodule pointers.fn submodule_diff( repo: &gix::Repository, change: &gix::object::tree::diff::ChangeDetached, old: Side, new: Side,) -> Diff { let path = change.location().to_string(); let side = |s: Side| FileContent { path: path.clone(), oid: match s { Side::Absent => ObjectId::null(repo.object_hash()).to_string(), Side::Present { oid, .. } => oid.to_string(), }, size: 0, is_binary: false, is_submodule: true, }; Diff { lhs_src: side(old), rhs_src: side(new), hunks: Vec::new(), lhs_positions: Vec::new(), rhs_positions: Vec::new(), has_byte_changes: None, has_syntactic_changes: false, }}
/// Build the [`Diff`] for a single changed file.fn build_diff( repo: &gix::Repository, change: &gix::object::tree::diff::ChangeDetached, cache: &mut gix::diff::blob::Platform,) -> anyhow::Result<Diff> { use gix::diff::blob::platform::prepare_diff::Operation; use gix::diff::blob::platform::resource::Data; use gix::diff::blob::{Diff as BlobDiff, InternedInput}; use gix::prelude::TreeDiffChangeExt as _;
let change = change.attach(repo, repo); let blob = change.diff(cache)?; let out = blob.resource_cache.prepare_diff()?;
// Per-side file metadata, derived from the prepared resources. let side = |res: &gix::diff::blob::platform::Resource<'_>| -> FileContent { let (size, is_binary) = match res.data { Data::Buffer { buf, .. } => (buf.len(), false), Data::Binary { size } => (size as usize, true), Data::Missing => (0, false), }; FileContent { path: res.rela_path.to_string(), oid: res.id.to_string(), size, is_binary, is_submodule: false, } }; let mut lhs_src = side(&out.old); let mut rhs_src = side(&out.new);
let has_byte_changes = if lhs_src.size == rhs_src.size && out.old.id == out.new.id { None } else { Some((lhs_src.size, rhs_src.size)) };
let hunks = match out.operation { Operation::InternalDiff { algorithm } => { let input = InternedInput::new(out.old.intern_source(), out.new.intern_source()); let mut d = BlobDiff::compute(algorithm, &input); d.postprocess_lines(&input); d.hunks() .map(|h| { let before: Vec<LineNumber> = h.before.clone().map(LineNumber).collect(); let after: Vec<LineNumber> = h.after.clone().map(LineNumber).collect(); let n = before.len().max(after.len()); let lines = (0..n) .map(|i| (before.get(i).copied(), after.get(i).copied())) .collect(); Hunk { novel_lhs: before.iter().copied().collect(), novel_rhs: after.iter().copied().collect(), lines, } }) .collect() } Operation::SourceOrDestinationIsBinary => { lhs_src.is_binary = true; rhs_src.is_binary = true; Vec::new() } Operation::ExternalCommand { .. } => unreachable!("we disabled that"), };
Ok(Diff { lhs_src, rhs_src, hunks, lhs_positions: Vec::new(), rhs_positions: Vec::new(), has_byte_changes, has_syntactic_changes: false, })}
/// Compute the two trees whose diff is the *interdiff* between an old patch/// version (`from_base..from_head`) and a new one (`to_base..to_head`).////// We rebase the old patch onto the new base so both versions share `to_base`,/// then the caller diffs the returned trees (step 4):////// ```text/// from_base -- from_head (old patch)/// \/// `-- to_base -- to_head (new patch)/// ```////// 1. Rebase `from` onto `to_base` via a 3-way tree merge./// Replay the patch diff `from_base.tree -> from_head.tree` on top of `to_base.tree`./// 2. Return `(rebased_from_tree, to_head.tree)`, both rooted at `to_base`.////// `from_base` / `to_base` default to the respective head commit's first parent.////// `repo` is borrowed so the returned trees can reference it; resolving a/// `repo_did` to an on-disk repository is out of scope here.pub fn prepare_interdiff<'repo>( repo: &'repo gix::Repository, from: (Option<ObjectId>, ObjectId), to: (Option<ObjectId>, ObjectId),) -> anyhow::Result<(gix::Tree<'repo>, gix::Tree<'repo>)> { let (from_base_id, from_head_id) = from; let (to_base_id, to_head_id) = to;
let from_head = repo.find_commit(from_head_id)?; let to_head = repo.find_commit(to_head_id)?;
let from_base_id = from_base_id.unwrap_or_else(|| resolve_base(&from_head).unwrap()); let to_base_id = to_base_id.unwrap_or_else(|| resolve_base(&to_head).unwrap());
let from_base = repo.find_commit(from_base_id)?; let to_base = repo.find_commit(to_base_id)?;
// Endpoint trees for the 3-way merge. let from_base_tree = from_base.tree_id()?.detach(); let from_head_tree = from_head.tree_id()?.detach(); let to_base_tree = to_base.tree_id()?.detach();
// Rebase = replay (from_base_tree -> from_head_tree) onto to_base_tree: // ancestor = from_base_tree, ours = to_base_tree, theirs = from_head_tree. let options = repo.tree_merge_options()?; let labels = gix::merge::blob::builtin_driver::text::Labels { ancestor: Some("from.base".as_bytes().as_bstr()), current: Some("to.base".as_bytes().as_bstr()), other: Some("from.head".as_bytes().as_bstr()), }; let mut outcome = repo.merge_trees( from_base_tree, to_base_tree, from_head_tree, labels, options, )?;
// Interdiff tolerates conflicts: the merged tree carries conflict markers // (blob driver keeps them); surface them rather than failing. if !outcome.conflicts.is_empty() { info!( conflicts = outcome.conflicts.len(), "interdiff rebase produced conflicts; tree contains conflict markers" ); }
let rebased_id = outcome.tree.write()?.detach(); let rebased_tree = repo.find_tree(rebased_id)?; let to_head_tree = to_head.tree()?; Ok((rebased_tree, to_head_tree))}
fn resolve_base(commit: &Commit) -> anyhow::Result<ObjectId> { commit .parent_ids() .next() .map(|id| id.detach()) .ok_or_else(|| anyhow::anyhow!("commit {0} has no parent to use as base", commit.id))}
#[cfg(test)]mod tests { use super::*;
/// A fresh bare repo in a tempdir. The `TempDir` is returned so it outlives the repo. fn repo() -> (tempfile::TempDir, gix::Repository) { let dir = tempfile::tempdir().unwrap(); let repo = gix::init_bare(dir.path()).unwrap(); (dir, repo) }
/// Build a tree from `(path, content)` pairs and return its oid. fn tree(repo: &gix::Repository, files: &[(&str, &[u8])]) -> ObjectId { let empty = repo.empty_tree().id; let mut editor = repo.edit_tree(empty).unwrap(); for (path, content) in files { let blob = repo.write_blob(content).unwrap().detach(); editor.upsert(*path, EntryKind::Blob, blob).unwrap(); } editor.write().unwrap().detach() }
/// Build a tree with a single submodule (gitlink) entry at `path` pointing at `commit_oid`. fn tree_with_gitlink(repo: &gix::Repository, path: &str, commit_oid: ObjectId) -> ObjectId { let empty = repo.empty_tree().id; let mut editor = repo.edit_tree(empty).unwrap(); editor.upsert(path, EntryKind::Commit, commit_oid).unwrap(); editor.write().unwrap().detach() }
/// Commit `tree_oid` with the given parents. Uses an explicit signature because a fresh /// `init_bare` repo has no user config (config-reading `commit` would fail AuthorMissing). fn commit(repo: &gix::Repository, tree_oid: ObjectId, parents: &[ObjectId]) -> ObjectId { let sig = gix::actor::SignatureRef { name: b"t".as_bstr(), email: b"t@t".as_bstr(), time: "0 +0000", }; repo.new_commit_as(sig, sig, "msg", tree_oid, parents.iter().copied()) .unwrap() .id }
/// Collect all diffs between two tree oids. fn diffs(repo: &gix::Repository, old: ObjectId, new: ObjectId) -> Vec<Diff> { let old = repo.find_tree(old).unwrap(); let new = repo.find_tree(new).unwrap(); diff(repo, &old, &new) .unwrap() .collect::<anyhow::Result<Vec<_>>>() .unwrap() }
#[test] fn modification() { let (_dir, repo) = repo(); let old = tree(&repo, &[("a", b"x\n")]); let new = tree(&repo, &[("a", b"y\n")]);
let got = diffs(&repo, old, new); assert_eq!(got.len(), 1); let d = &got[0]; assert_eq!(d.lhs_src.path, "a"); assert_eq!(d.rhs_src.path, "a"); assert!(!d.lhs_src.is_binary && !d.rhs_src.is_binary); assert_eq!(d.has_byte_changes, Some((2, 2))); assert_eq!(d.hunks.len(), 1); let h = &d.hunks[0]; assert!(h.novel_lhs.contains(&LineNumber(0))); assert!(h.novel_rhs.contains(&LineNumber(0))); }
#[test] fn addition() { let (_dir, repo) = repo(); let old = tree(&repo, &[]); let new = tree(&repo, &[("a", b"hello\n")]);
let got = diffs(&repo, old, new); assert_eq!(got.len(), 1); let d = &got[0]; assert_eq!(d.lhs_src.size, 0); // old side missing assert_eq!(d.rhs_src.size, 6); assert_eq!(d.rhs_src.path, "a"); assert!(d.has_byte_changes.is_some()); }
#[test] fn deletion() { let (_dir, repo) = repo(); let old = tree(&repo, &[("a", b"hello\n")]); let new = tree(&repo, &[]);
let got = diffs(&repo, old, new); assert_eq!(got.len(), 1); let d = &got[0]; assert_eq!(d.lhs_src.size, 6); assert_eq!(d.rhs_src.size, 0); // new side missing assert_eq!(d.lhs_src.path, "a"); }
#[test] fn binary() { let (_dir, repo) = repo(); let old = tree(&repo, &[("a", b"\x00\x01bin\n")]); let new = tree(&repo, &[("a", b"\x00\x01BIN\n")]);
let got = diffs(&repo, old, new); assert_eq!(got.len(), 1); let d = &got[0]; assert!(d.lhs_src.is_binary && d.rhs_src.is_binary); assert!(d.hunks.is_empty()); }
#[test] fn multiple_files_and_laziness() { let (_dir, repo) = repo(); let old = tree(&repo, &[("a", b"1\n"), ("b", b"1\n")]); let new = tree(&repo, &[("a", b"2\n"), ("b", b"2\n")]);
let old_t = repo.find_tree(old).unwrap(); let new_t = repo.find_tree(new).unwrap();
// Lazy: pulling one item yields exactly one without consuming the rest. let mut it = diff(&repo, &old_t, &new_t).unwrap(); assert!(it.next().is_some());
let all = diffs(&repo, old, new); assert_eq!(all.len(), 2); let mut paths: Vec<_> = all.iter().map(|d| d.rhs_src.path.clone()).collect(); paths.sort(); assert_eq!(paths, vec!["a".to_string(), "b".to_string()]); }
#[test] fn directory_addition_yields_inner_blobs() { let (_dir, repo) = repo(); let old = tree(&repo, &[]); // A whole new directory: gix emits a Tree change for `dir/` plus blob changes for the // files inside. We must skip the tree and yield only the blobs (no error). let new = tree(&repo, &[("dir/a", b"x\n"), ("dir/b", b"y\n")]);
let got = diffs(&repo, old, new); let mut paths: Vec<_> = got.iter().map(|d| d.rhs_src.path.clone()).collect(); paths.sort(); assert_eq!(paths, vec!["dir/a".to_string(), "dir/b".to_string()]); }
#[test] fn interdiff_equal_patches_is_empty() { let (_dir, repo) = repo(); // Shared base content B; patch P turns a's "1\n" into "2\n". let base = commit(&repo, tree(&repo, &[("a", b"1\n")]), &[]); let patched = tree(&repo, &[("a", b"2\n")]); // `from` and `to` both apply the same patch P on top of the same base. let from_head = commit(&repo, patched, &[base]); let to_head = commit(&repo, patched, &[base]);
let (rebased, to_head_tree) = prepare_interdiff(&repo, (Some(base), from_head), (Some(base), to_head)).unwrap();
// Same patch ⇒ interdiff (diff of rebased vs to_head) is empty. let got = diff(&repo, &rebased, &to_head_tree) .unwrap() .collect::<anyhow::Result<Vec<_>>>() .unwrap(); assert!(got.is_empty(), "expected empty interdiff, got {got:?}"); }
#[test] fn interdiff_divergent_shows_delta() { let (_dir, repo) = repo(); let base = commit(&repo, tree(&repo, &[("a", b"1\n")]), &[]); // `from` applies patch P (a: 1->2). let from_head = commit(&repo, tree(&repo, &[("a", b"2\n")]), &[base]); // `to` applies P plus a new file `c`. let to_head = commit(&repo, tree(&repo, &[("a", b"2\n"), ("c", b"new\n")]), &[base]);
let (rebased, to_head_tree) = prepare_interdiff(&repo, (Some(base), from_head), (Some(base), to_head)).unwrap();
let got = diff(&repo, &rebased, &to_head_tree) .unwrap() .collect::<anyhow::Result<Vec<_>>>() .unwrap(); assert_eq!(got.len(), 1); assert_eq!(got[0].rhs_src.path, "c"); }
#[test] fn submodule_modification() { let (_dir, repo) = repo(); // Two distinct commit oids for the gitlink to point at (need not be real submodules). let a = commit(&repo, tree(&repo, &[("x", b"1\n")]), &[]); let b = commit(&repo, tree(&repo, &[("x", b"2\n")]), &[]); let old = tree_with_gitlink(&repo, "sub", a); let new = tree_with_gitlink(&repo, "sub", b);
let got = diffs(&repo, old, new); assert_eq!(got.len(), 1); let d = &got[0]; assert!(d.lhs_src.is_submodule && d.rhs_src.is_submodule); assert!(d.hunks.is_empty()); assert_eq!(d.lhs_src.path, "sub"); assert_eq!(d.lhs_src.oid, a.to_string()); assert_eq!(d.rhs_src.oid, b.to_string()); }
#[test] fn submodule_addition() { let (_dir, repo) = repo(); let b = commit(&repo, tree(&repo, &[("x", b"1\n")]), &[]); let old = tree(&repo, &[]); let new = tree_with_gitlink(&repo, "sub", b);
let got = diffs(&repo, old, new); assert_eq!(got.len(), 1); let d = &got[0]; assert!(d.rhs_src.is_submodule); assert!(d.hunks.is_empty()); assert_eq!(d.rhs_src.oid, b.to_string()); // Absent old side reported as the null oid. assert_eq!(d.lhs_src.oid, ObjectId::null(repo.object_hash()).to_string()); }}