crates/gunnar-delta/src/name_hash.rs
//! The **path hash**: the sort key that decides which objects the window ever
//! sees each other at all.
//!
//! # Why this is here and not left to the caller
//!
//! [`crate::deltify`] compares each object against the `window` objects nearest
//! it in sort order. Sort order is therefore not a detail of the search — it
//! *is* the search, because a base that never shares a window with its target
//! can never be found no matter how good the encoder is. git has known this
//! since 2006: `type_size_sort` in `builtin/pack-objects.c` sorts by
//! `(type, name hash, preferred base, size descending)`, and the name hash is
//! what puts "the same file across history" next to each other.
//!
//! Two published measurements say what the key alone is worth, both `git repack
//! -adf` against the same repository with only the ordering changed:
//!
//! | change | repository | before | after |
//! |---|---|---:|---:|
//! | `--name-hash-version=2` | microsoft/fluentui | 439 MiB | **160 MiB** (and 96 s → 34 s) |
//! | `--path-walk` | microsoft/fluentui | 438 MB | **148 MB** |
//! | `--path-walk` | a private monorepo | 130 049 MB | **4 432 MB** |
//!
//! MEASURED BY Derrick Stolee and Jonathan Blau respectively, quoted at second
//! hand from their write-ups; not reproduced here. What *is* reproduced here is
//! the function, from git's own documentation of it.
//!
//! # The two versions, and why v1 is not enough
//!
//! [`v1`] is git's original. Its own documentation says it "effectively just
//! creates a sortable number from the last sixteen non-whitespace characters",
//! because each character is shifted two bits further right than the one after
//! it, so anything more than sixteen characters from the end of the path falls
//! out of a 32-bit word entirely. In a repository with one `index.ts` per
//! directory that is a catastrophic collision: every one of them hashes
//! identically, the window fills with unrelated files that merely share a
//! filename, and the actual previous version of the file is nowhere near.
//!
//! [`v2`] (git 2.49) hashes each path *component* separately and folds the
//! parent directories back in with a shift, so `src/a/index.ts` and
//! `src/b/index.ts` differ while `src/a/index.ts` at two revisions still agree.
//!
//! # It is a `u32` and nothing else
//!
//! [`crate::Object`] carries the result, not the path. That keeps this crate's
//! input free of anything resembling a repository — no tree walk, no filesystem,
//! no `gix-object` tree decoding — and it lets a caller that has something
//! better than a hash (a dense id per distinct path, which is what git's
//! `--path-walk` amounts to) supply that instead. The sort does not care where
//! the number came from; it only cares that equal numbers mean "likely alike".
/// C's `isspace` over the C locale, which is what git's loop tests.
///
/// Spelled out rather than reached for as `u8::is_ascii_whitespace`, because
/// that one omits the vertical tab (`0x0B`) and this one must not: the value of
/// these functions is that they agree with git's, and a difference that shows up
/// only on a path containing a vertical tab is a difference nobody would ever
/// find by testing.
#[inline]
fn is_space(c: u8) -> bool {
matches!(c, b' ' | b'\t' | b'\n' | 0x0B | 0x0C | b'\r')
}
/// git's original name hash (`pack_name_hash`, `builtin/pack-objects.c`).
///
/// Whitespace is skipped, every other byte is folded in with a two-bit right
/// shift, so the **last sixteen non-whitespace bytes dominate** and everything
/// before them is shifted out of the word. That is deliberate — paths that end
/// the same way sort together — and it is also the collision that [`v2`] exists
/// to fix.
///
/// An empty path (an object whose path is unknown, or a commit or tag, which
/// has none) hashes to `0`, which is what the caller should pass for "no
/// grouping information": it puts every such object in one group and leaves the
/// size ordering to decide, which is exactly the behaviour of a search with no
/// path hash at all.
pub fn v1(path: &[u8]) -> u32 {
let mut hash: u32 = 0;
for &c in path {
if is_space(c) {
continue;
}
hash = (hash >> 2).wrapping_add((c as u32) << 24);
}
hash
}
/// git 2.49's `pack_name_hash_v2`.
///
/// Identical to [`v1`] within one path component, but a `/` folds the component
/// hash accumulated so far into a separate `base` accumulator with a six-bit
/// shift and starts the component hash again. The result is
/// `(base >> 6) ^ hash`, so the **final component still dominates** — two
/// revisions of the same file agree — while the directories above it perturb
/// the low bits enough that two different `index.ts` no longer collide.
///
/// git will not use this while writing a `.bitmap` (it silently falls back to
/// v1 there); that restriction is git's own, about the name-hash cache it
/// stores inside the bitmap, and does not apply to this crate, which stores
/// nothing.
pub fn v2(path: &[u8]) -> u32 {
let mut hash: u32 = 0;
let mut base: u32 = 0;
for &c in path {
if is_space(c) {
continue;
}
if c == b'/' {
base = (base >> 6) ^ hash;
hash = 0;
} else {
hash = (hash >> 2).wrapping_add((c as u32) << 24);
}
}
(base >> 6) ^ hash
}
#[cfg(test)]
mod tests {
use super::*;
/// The property v1 is *documented* to have, stated as a test so that a
/// rewrite of the arithmetic cannot quietly lose it: only the tail matters.
#[test]
fn v1_sees_only_the_last_sixteen_bytes() {
// Sixteen is exact, and it is arithmetic rather than a rule of thumb:
// a byte enters at bit 24 and moves two bits right per later byte, so
// the seventeenth from the end has been shifted past bit 0 and
// contributes nothing at all.
assert_eq!(v1(b"X0123456789abcdef"), v1(b"Y0123456789abcdef"));
// The sixteenth from the end does still count — but only its top two
// bits survive the fifteen shifts, so `X` and `Y` would compare equal
// here too and prove nothing. These two differ in bit 6.
assert_ne!(v1(b"a123456789abcdef"), v1(b"!123456789abcdef"));
}
/// The whole reason v2 exists, and the assertion that would have to fail
/// for the change to be pointless.
///
/// The two paths share their last sixteen bytes — `aaa/src/index.ts` — so
/// v1 cannot tell them apart at all, and every `index.ts` in the repository
/// lands in one window together with files it has nothing to do with.
#[test]
fn v2_separates_what_v1_collides() {
let a = b"one/pkg/aaaa/src/index.ts";
let b = b"two/pkg/aaaa/src/index.ts";
assert_eq!(v1(a), v1(b), "the premise: v1 collides on these");
assert_ne!(v2(a), v2(b), "and v2 is what does not");
}
/// …and still agrees with itself, which is the half that makes it useful:
/// the same path at two revisions must land in the same window.
#[test]
fn v2_is_a_function_of_the_path_alone() {
assert_eq!(v2(b"src/a/index.ts"), v2(b"src/a/index.ts"));
// The final component still dominates: two files in the same directory
// are not forced apart by the directory, only by their own names.
assert_ne!(v2(b"src/a/index.ts"), v2(b"src/a/other.ts"));
}
/// **What v2 does not fix**, recorded because a limit nobody wrote down is
/// a limit somebody later reports as a bug.
///
/// Each `/` folds the accumulated directory hash six bits further right, so
/// the fifth ancestor up contributes at most two bits and the sixth
/// contributes none. Two paths that differ only that far from the file, and
/// whose last sixteen bytes agree, collide under **both** versions. Only a
/// full path-walk grouping separates those, which is the second half of
/// this lever and not this function's job.
#[test]
fn v2_decays_after_about_five_directories() {
let a = b"a/b/c/d/e/index.ts";
let b = b"z/b/c/d/e/index.ts";
assert_eq!(v1(a), v1(b));
assert_eq!(v2(a), v2(b), "v2's directory salt has decayed to nothing");
}
#[test]
fn whitespace_is_skipped_by_both() {
assert_eq!(v1(b"a b.txt"), v1(b"ab.txt"));
assert_eq!(v2(b"dir/a b.txt"), v2(b"dir/ab.txt"));
}
/// No path is `0` in both, which is the value that means "ungrouped".
#[test]
fn the_empty_path_is_zero() {
assert_eq!(v1(b""), 0);
assert_eq!(v2(b""), 0);
}
/// A long path must not panic in a debug build, which is what an unchecked
/// `+` would do the moment two shifted bytes carried.
#[test]
fn long_paths_do_not_overflow() {
let deep: Vec<u8> = std::iter::repeat_n(b"\xff\xffdir/".as_slice(), 4096)
.flatten()
.copied()
.collect();
let _ = v1(&deep);
let _ = v2(&deep);
}
}