Something went wrong. Try again.
A Zig library that reads git repositories without running git, with log, show and diff output byte-identical to git's.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! How alike two files are, as git's rename, copy and break detection//! measure it: the amount of one file's material found again in the//! other, counted on chunks rather than lines.//!//! gitdiffcore(7) gives the idea in prose; the details were found by//! asking git, scoring hundreds of designed pairs of files and finding//! which distinct chunks it counts as the same://!//! - A file is cut into chunks, each ending after a newline or on//! reaching 64 bytes. In a text file (no NUL in its first 8000 bytes) a//! carriage return directly before a newline is passed over: it is not//! part of the chunk and does not count toward its 64 bytes.//! - Each chunk is reduced to one of 107927 buckets: a 64-bit value//! rotated left seven bits before each byte is added, folded to 32 bits//! by adding 97 times its upper half to its lower half, then taken//! modulo 107927. Different chunks falling in one bucket count as the//! same, which is why a large file seems a little more like another//! than its lines say.//! - A file's signature is the number of bytes in each bucket. The//! material copied from one file to another is, summed over the//! buckets, the smaller of the two counts.//! - The score is the material copied, scaled to 60000 for the whole of//! the larger file. A percentage shown is the score's hundredths of//! 60000, rounded down.
const std = @import("std");const Allocator = std.mem.Allocator;
/// The score of two identical files.pub const max_score: u32 = 60000;
/// `-M`'s default minimum score, 50%.pub const default_min_score: u32 = max_score / 2;
/// The number of buckets chunks fall in.const buckets: u32 = 107927;
/// The longest chunk.const max_chunk: usize = 64;
/// The bytes of one bucket.pub const Entry = struct { bucket: u32, bytes: u64,};
/// A file's chunks, counted by bucket.pub const Signature = struct { /// Sorted by bucket, one entry each. entries: []Entry, /// The file's size in bytes, carriage returns included. size: u64, /// The bytes of all its chunks: `size` less the carriage returns /// passed over before newlines in a text file. chunked: u64,
/// Frees the entries. pub fn deinit(s: *Signature, gpa: Allocator) void { gpa.free(s.entries); s.* = undefined; }};
/// Whether `contents` is text for the chunking: no NUL in its first 8000/// bytes.pub fn isText(contents: []const u8) bool { return std.mem.findScalar(u8, contents[0..@min(contents.len, 8000)], 0) == null;}
fn bucketOf(v: u64) u32 { const folded: u32 = @truncate((v & 0xffff_ffff) +% 97 *% (v >> 32)); return folded % buckets;}
/// Calls `chunk(context, bucket, bytes)` for each of `contents`' chunks.fn eachChunk(contents: []const u8, context: anytype, comptime chunk: fn (@TypeOf(context), u32, u64) Allocator.Error!void) Allocator.Error!void { const text = isText(contents); var v: u64 = 0; var n: usize = 0; var i: usize = 0; while (i < contents.len) : (i += 1) { const c = contents[i]; if (text and c == '\r' and i + 1 < contents.len and contents[i + 1] == '\n') continue; v = std.math.rotl(u64, v, 7) +% c; n += 1; if (c == '\n' or n == max_chunk) { try chunk(context, bucketOf(v), n); v = 0; n = 0; } } if (n != 0) try chunk(context, bucketOf(v), n);}
const Counter = struct { map: *std.AutoHashMapUnmanaged(u32, u64), gpa: Allocator,
fn add(c: Counter, bucket: u32, bytes: u64) Allocator.Error!void { const gop = try c.map.getOrPut(c.gpa, bucket); if (!gop.found_existing) gop.value_ptr.* = 0; gop.value_ptr.* += bytes; }};
fn lessThan(_: void, a: Entry, b: Entry) bool { return a.bucket < b.bucket;}
/// The signature of `contents`. Free it with `Signature.deinit`.pub fn signature(gpa: Allocator, contents: []const u8) Allocator.Error!Signature { var map: std.AutoHashMapUnmanaged(u32, u64) = .empty; defer map.deinit(gpa); try eachChunk(contents, Counter{ .map = &map, .gpa = gpa }, Counter.add); const entries = try gpa.alloc(Entry, map.count()); var it = map.iterator(); var k: usize = 0; while (it.next()) |e| : (k += 1) entries[k] = .{ .bucket = e.key_ptr.*, .bytes = e.value_ptr.* }; std.mem.sortUnstable(Entry, entries, {}, lessThan); var chunked: u64 = 0; for (entries) |e| chunked += e.bytes; return .{ .entries = entries, .size = contents.len, .chunked = chunked };}
/// The material of `a` found again in `b`: over the buckets, the smaller/// of the two counts.pub fn copied(a: Signature, b: Signature) u64 { var i: usize = 0; var j: usize = 0; var total: u64 = 0; while (i < a.entries.len and j < b.entries.len) { const x = a.entries[i]; const y = b.entries[j]; if (x.bucket < y.bucket) { i += 1; } else if (x.bucket > y.bucket) { j += 1; } else { total += @min(x.bytes, y.bytes); i += 1; j += 1; } } return total;}
/// The score of `copied` bytes shared by files of `a_size` and `b_size`/// bytes: out of `max_score` for the whole of the larger. Two empty files/// score in full.pub fn score(a_size: u64, b_size: u64, copied_bytes: u64) u32 { const larger = @max(a_size, b_size); if (larger == 0) return max_score; const s = @as(u128, copied_bytes) * max_score / larger; return @intCast(@min(s, max_score));}
/// Whether two files of these sizes could reach `min_score` at all: when/// the smaller is too small a part of the larger, git does not compare/// them, and the pair scores nothing.pub fn sizesCanReach(a_size: u64, b_size: u64, min_score: u32) bool { const larger = @max(a_size, b_size); const smaller = @min(a_size, b_size); return @as(u128, smaller) * max_score >= @as(u128, min_score) * larger;}
/// The percentage git shows for `s`: its hundredths of `max_score`,/// rounded down.pub fn percent(s: u32) u32 { return s * 100 / max_score;}
/// Reads the number after `-M`, `-C` or `-B` (or after the slash of/// `-B<n>/<m>`) as git does, returning a score out of `max_score`: zero/// for an empty or zero number, which stands for the option's default,/// and null for text git refuses.////// Found by asking git: digits after a `.` are a fraction, as are all the/// digits of a number with neither a `.` nor a `%` (`-M5` is 50%); fraction digits are/// read while their scale stays below 100000, so at most five count;/// a `%` at the end divides by 100 more; a number of one or more is the/// whole score.pub fn parseScore(text: []const u8) ?u32 { const has_dot = std.mem.findScalar(u8, text, '.') != null; const has_percent = text.len != 0 and text[text.len - 1] == '%'; var num: u128 = 0; var scale: u128 = 1; var in_fraction = !has_dot and !has_percent; var i: usize = 0; while (i < text.len) : (i += 1) { const c = text[i]; if (c >= '0' and c <= '9') { if (in_fraction) { if (scale < 100000) { num = num * 10 + (c - '0'); scale *= 10; } } else { num = @min(num * 10 + (c - '0'), std.math.maxInt(u64)); } } else if (c == '.' and !in_fraction) { in_fraction = true; } else if (c == '%' and i + 1 == text.len) { scale *= 100; } else return null; } if (num >= scale) return max_score; return @intCast(num * max_score / scale);}
test "chunks and buckets" { const gpa = std.testing.allocator; // Values git was seen to give, as residues of the bucket count. var s = try signature(gpa, "!mm\n"); defer s.deinit(gpa); try std.testing.expectEqual(@as(usize, 1), s.entries.len); try std.testing.expectEqual(@as(u32, 97795), s.entries[0].bucket); var t = try signature(gpa, "@mmmmmm\n"); defer t.deinit(gpa); try std.testing.expectEqual(@as(u32, 54761), t.entries[0].bucket);}
test "scores" { const gpa = std.testing.allocator; const cases = [_]struct { a: []const u8, b: []const u8, percent: u32 }{ .{ .a = "a\nb\nc\nd\n", .b = "a\nb\nc\ne\n", .percent = 75 }, .{ .a = "x\nx\nx\nx\nx\nx\nx\nx\nx\nx\n", .b = "x\nx\nx\nx\nx\nx\nx\nx\nx\nx\ny\n", .percent = 90 }, // A carriage return before a newline is passed over in text... .{ .a = "aaaa\r\nbbbb\r\n", .b = "aaaa\r\ncccc\r\n", .percent = 41 }, // ...and kept where there is a NUL. .{ .a = "a\r\na\r\na\r\na\r\na\r\na\r\na\r\na\r\na\r\na\r\n\x00", .b = "a\r\na\r\na\r\na\r\na\r\na\r\na\r\na\r\na\r\na\r\nb\n\x00", .percent = 93 }, }; for (cases) |c| { var a = try signature(gpa, c.a); defer a.deinit(gpa); var b = try signature(gpa, c.b); defer b.deinit(gpa); try std.testing.expectEqual(c.percent, percent(score(a.size, b.size, copied(a, b)))); }}
test "parseScore" { try std.testing.expectEqual(@as(?u32, 30000), parseScore("5")); try std.testing.expectEqual(@as(?u32, 30000), parseScore("50%")); try std.testing.expectEqual(@as(?u32, 7380), parseScore("123")); try std.testing.expectEqual(@as(?u32, 7407), parseScore("12345678")); try std.testing.expectEqual(@as(?u32, 19980), parseScore("33.3%")); try std.testing.expectEqual(@as(?u32, 30000), parseScore(".5")); try std.testing.expectEqual(@as(?u32, max_score), parseScore("5.")); try std.testing.expectEqual(@as(?u32, max_score), parseScore("150%")); try std.testing.expectEqual(@as(?u32, 0), parseScore("")); try std.testing.expectEqual(@as(?u32, 0), parseScore("%")); try std.testing.expectEqual(@as(?u32, 0), parseScore("0000199")); try std.testing.expectEqual(@as(?u32, 1), parseScore("00002")); try std.testing.expectEqual(@as(?u32, null), parseScore("x")); try std.testing.expectEqual(@as(?u32, null), parseScore("5x")); try std.testing.expectEqual(@as(?u32, null), parseScore("-1"));}
const fuzz_input = @import("../testing/fuzz.zig");
/// Two files from fuzzed input, split at the first 0xff: their score is/// symmetric, within range, and full for a file and itself.fn fuzzScore(_: void, smith: *std.testing.Smith) anyerror!void { const gpa = std.testing.allocator; var buffer: [4096]u8 = undefined; const input = fuzz_input.bytes(smith, &buffer); const cut = std.mem.findScalar(u8, input, 0xff) orelse input.len; const a_bytes = input[0..cut]; const b_bytes = if (cut < input.len) input[cut + 1 ..] else ""; var a = try signature(gpa, a_bytes); defer a.deinit(gpa); var b = try signature(gpa, b_bytes); defer b.deinit(gpa); const ab = copied(a, b); try std.testing.expectEqual(ab, copied(b, a)); try std.testing.expect(ab <= @min(a.size, b.size)); const s = score(a.size, b.size, ab); try std.testing.expect(s <= max_score); try std.testing.expectEqual(s, score(b.size, a.size, ab)); // A file copies all of itself but the carriage returns passed over. const self = copied(a, a); try std.testing.expect(self <= a.size); var total: u64 = 0; for (a.entries) |e| total += e.bytes; try std.testing.expectEqual(total, self); _ = parseScore(a_bytes);}
test "fuzz: similarity score" { try fuzz_input.fuzz({}, fuzzScore, .{ .corpus = &.{ @embedFile("../fuzz/similarity-pair"), @embedFile("../fuzz/similarity-crlf"), } });}