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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Naming a commit by the nearest tag it descends from, as `git describe`//! does. git-describe(1)'s "Search Strategy" describes it; the rest was//! found by comparing with git over generated histories://!//! - **Names** (`Names`): by default the annotated tags, with `tags` every//! tag, with `all` every ref, peeled to commits; a tag of something that//! is not a commit names nothing. With `match` and `exclude`, only those//! whose name below `refs/tags/` (and with `all`, `refs/heads/` or//! `refs/remotes/`, refs of other kinds never) a `match` glob matches//! and no `exclude` glob does.//! - **One commit, several names**: an annotated tag beats a lightweight//! one, which beats any other ref; a later tagger date an earlier one;//! and otherwise the first in ref order wins.//! - **The search**: a commit with a name is named by it. Otherwise the//! commits it descends from are visited newest commit date first (only//! first parents with `first_parent`), and the first `candidates` with a//! name are candidates; the one with the smallest depth wins, the first//! found among equals. The depth is counted as `search` says, which is//! not always what `git log <tag>..<commit>` would list.
const std = @import("std");const Allocator = std.mem.Allocator;const Io = std.Io;
const object = @import("object.zig");const Id = object.Id;const Diagnostics = @import("Diagnostics.zig");const ObjectDatabase = @import("ObjectDatabase.zig");const RefStore = @import("RefStore.zig");const Commits = @import("Commits.zig");const Index = Commits.Index;const Tag = @import("tag.zig").Tag;const wildmatch = @import("wildmatch.zig");
/// Which refs name commits.pub const Options = struct { /// `--tags`: lightweight tags too. tags: bool = false, /// `--all`: every ref. all: bool = false, /// `--match`, each. match: []const []const u8 = &.{}, /// `--exclude`, each. exclude: []const []const u8 = &.{},};
/// A name for a commit.pub const Name = struct { /// The ref's whole name. ref: []const u8, /// As `git describe` writes it: below `refs/tags/`, or with `all` /// below `refs/`. shown: []const u8, /// Whether the ref points at an annotated tag. annotated: bool, /// The outer tag's tagger date, for an annotated tag. date: i64 = 0, /// What the ref points at, or for an annotated tag what the tag /// does: the object `--long` abbreviates for a commit named by it. target: Id,};
/// Every commit that has a name, and its best one.pub const Names = struct { arena: std.heap.ArenaAllocator, map: std.AutoHashMapUnmanaged([object.max_byte_length]u8, Name) = .empty, /// The commits lightweight tags point at, when only annotated tags /// name commits, for git's hint to try `--tags`. light: std.AutoHashMapUnmanaged([object.max_byte_length]u8, void) = .empty,
/// Frees everything. pub fn deinit(n: *Names) void { n.arena.deinit(); n.* = undefined; }
/// The best name of `commit`, if it has one. pub fn of(n: *const Names, commit: Id) ?Name { return n.map.get(commit.bytes); }
/// Whether nothing has a name. pub fn isEmpty(n: *const Names) bool { return n.map.count() == 0; }};
/// Whether `a` names a commit better than `b`: an annotated tag before a/// lightweight one before any other ref, then the later tagger date.fn better(a: Name, b: Name) bool { if (kindOf(a) != kindOf(b)) return kindOf(a) < kindOf(b); return a.date > b.date;}
/// The name a ref is matched by, or null for a ref that cannot match.fn matchName(name: []const u8, all: bool) ?[]const u8 { if (std.mem.startsWith(u8, name, "refs/tags/")) return name["refs/tags/".len..]; if (!all) return null; for ([_][]const u8{ "refs/heads/", "refs/remotes/" }) |p| if (std.mem.startsWith(u8, name, p)) return name[p.len..]; return null;}
/// Finds the names in `refs`, reading tags from `db`.pub fn loadNames(gpa: Allocator, io: Io, refs: RefStore, db: ObjectDatabase, options: Options, diag: ?*Diagnostics) RefStore.ReadError!Names { var n: Names = .{ .arena = .init(gpa) }; errdefer n.deinit(); const a = n.arena.allocator(); var list = try refs.list(io, gpa, if (options.all) "refs/" else "refs/tags/", diag); defer list.deinit(); for (list.entries) |e| { if (options.match.len != 0 or options.exclude.len != 0) { const m = matchName(e.name, options.all) orelse continue; if (options.match.len != 0) { const any = for (options.match) |p| { if (wildmatch.match(p, m, .{})) break true; } else false; if (!any) continue; } const excluded = for (options.exclude) |p| { if (wildmatch.match(p, m, .{})) break true; } else false; if (excluded) continue; } const id = switch (e.value) { .direct => |d| d.id, .symbolic => blk: { var r = refs.resolve(io, gpa, e.name, null) catch continue; defer r.deinit(gpa); break :blk switch (r.outcome) { .direct => |d| d.id, else => continue, }; }, .broken => continue, }; // Peel, keeping the outer tag's date. var current = id; var annotated = false; var date: i64 = 0; var target = id; var kind: object.Kind = .commit; for (0..RefStore.max_peel_depth) |_| { const header = db.readHeader(io, current, null) catch break; kind = header.kind; if (kind != .tag) break; var o = db.read(io, gpa, current, null) catch break; defer o.deinit(gpa); const t = Tag.parse(current.object_format, o.data, null) catch break; if (!annotated) { annotated = true; target = t.target; if (t.tagger()) |who| if (who.date()) |d| { date = d.seconds; }; } current = t.target; } if (kind != .commit) continue; const is_tag = std.mem.startsWith(u8, e.name, "refs/tags/"); if (!options.all and !options.tags and !annotated) { if (is_tag) try n.light.put(a, current.bytes, {}); continue; } const full = try a.dupe(u8, e.name); const name: Name = .{ .ref = full, .shown = if (options.all) full["refs/".len..] else full["refs/tags/".len..], .annotated = annotated, .date = date, .target = target, }; const gop = try n.map.getOrPut(a, current.bytes); if (!gop.found_existing or better(name, gop.value_ptr.*)) gop.value_ptr.* = name; } return n;}
/// What describing a commit found.pub const Found = struct { name: Name, /// The depth git counts: 0 for the name's own commit. depth: u64,};
/// How the search goes.pub const SearchOptions = struct { /// `--candidates`: how many named commits are weighed; 0 for only /// the commit's own name. candidates: usize = 10, /// `--first-parent`. first_parent: bool = false,};
/// What a search came to.pub const Outcome = union(enum) { found: Found, /// Nothing named the commit; `unannotated` says whether the search /// met a lightweight tag that `tags` would have taken, for git's hint. none: struct { unannotated: bool }, /// The candidates were of more than one kind — annotated tags, /// lightweight tags, other refs — among which git's choice was not /// matched: it does not always take the candidate the rule above /// says, and not always one kind over another. mixed,};
fn kindOf(n: Name) u2 { if (n.annotated) return 0; if (std.mem.startsWith(u8, n.ref, "refs/tags/")) return 1; return 2;}
const max_candidates = 64;
/// Describes `commit`, reading commits through `store`.////// The depth is the one git counts, which git-describe(1) calls the/// number of commits `git log <tag>..<commit>` lists but which was found/// to be counted as git walks: commits are visited newest commit date/// first, each passing on to its parents which candidates reach it; every/// commit visited adds one to the depth of each candidate found so far/// that has not reached it, and a candidate starts with the number of/// commits visited before it. The walk stops once every commit queued is/// reached by every candidate, or when one more candidate is met than/// `candidates`; then the best so far is finished by walking on until/// everything queued is reached by it.pub fn search(gpa: Allocator, names: *const Names, store: *Commits, commit: Index, options: SearchOptions, diag: ?*Diagnostics) Commits.Error!Outcome { if (names.of(store.id(commit))) |n| return .{ .found = .{ .name = n, .depth = 0 } }; var unannotated = false; if (options.candidates == 0) return .{ .none = .{ .unannotated = false } }; const limit = @min(options.candidates, max_candidates);
const Candidate = struct { commit: Index, depth: u64, flag: u64 }; var candidates: std.ArrayList(Candidate) = .empty; defer candidates.deinit(gpa); var flags: std.AutoHashMapUnmanaged(Index, u64) = .empty; defer flags.deinit(gpa); var queue: std.ArrayList(Queued) = .empty; defer queue.deinit(gpa); var sequence: u64 = 0; try store.load(commit, diag); try flags.put(gpa, commit, 0); try pushQueued(gpa, &queue, .{ .time = store.time(commit), .sequence = sequence, .commit = commit }); var visited: u64 = 0; var gave_up = false; while (popQueued(&queue)) |c| { visited += 1; if (names.light.contains(store.id(c).bytes)) unannotated = true; if (c != commit) { const id = store.id(c); if (names.of(id) != null) { if (candidates.items.len < limit) { const flag = @as(u64, 1) << @intCast(candidates.items.len); try candidates.append(gpa, .{ .commit = c, .depth = visited - 1, .flag = flag }); flags.getPtr(c).?.* |= flag; } else { gave_up = true; sequence += 1; try pushQueued(gpa, &queue, .{ .time = store.time(c), .sequence = sequence, .commit = c }); break; } } } const mine = flags.get(c).?; for (candidates.items) |*cand| { if (mine & cand.flag == 0) cand.depth += 1; } try passOn(gpa, store, c, mine, options.first_parent, &flags, &queue, &sequence, diag); if (candidates.items.len != 0) { var all: u64 = 0; for (candidates.items) |cand| all |= cand.flag; if (everyQueuedHas(&queue, &flags, all)) break; } } if (candidates.items.len == 0) return .{ .none = .{ .unannotated = unannotated } }; const first_kind = kindOf(names.of(store.id(candidates.items[0].commit)).?); for (candidates.items[1..]) |cand| { if (kindOf(names.of(store.id(cand.commit)).?) != first_kind) return .mixed; } var best = &candidates.items[0]; for (candidates.items[1..]) |*cand| { if (cand.depth < best.depth) best = cand; } if (gave_up) { while (!everyQueuedHas(&queue, &flags, best.flag)) { const c = popQueued(&queue) orelse break; const mine = flags.get(c).?; if (mine & best.flag == 0) best.depth += 1; try passOn(gpa, store, c, mine, options.first_parent, &flags, &queue, &sequence, diag); } } return .{ .found = .{ .name = names.of(store.id(best.commit)).?, .depth = best.depth } };}
fn passOn( gpa: Allocator, store: *Commits, c: Index, mine: u64, first_parent: bool, flags: *std.AutoHashMapUnmanaged(Index, u64), queue: *std.ArrayList(Queued), sequence: *u64, diag: ?*Diagnostics,) Commits.Error!void { const n = if (first_parent) @min(store.parents(c).len, 1) else store.parents(c).len; for (0..n) |i| { const p = store.parents(c)[i]; const gop = try flags.getOrPut(gpa, p); if (!gop.found_existing) { gop.value_ptr.* = 0; try store.load(p, diag); sequence.* += 1; try pushQueued(gpa, queue, .{ .time = store.time(p), .sequence = sequence.*, .commit = p }); } flags.getPtr(p).?.* |= mine; }}
fn everyQueuedHas(queue: *const std.ArrayList(Queued), flags: *const std.AutoHashMapUnmanaged(Index, u64), want: u64) bool { for (queue.items) |q| { if (flags.get(q.commit).? & want != want) return false; } return true;}
const Queued = struct { time: i64, sequence: u64, commit: Index };
fn newer(a: Queued, b: Queued) bool { if (a.time != b.time) return a.time > b.time; return a.sequence < b.sequence;}
fn pushQueued(gpa: Allocator, queue: *std.ArrayList(Queued), q: Queued) Allocator.Error!void { try queue.append(gpa, q); var i = queue.items.len - 1; while (i > 0) { const parent = (i - 1) / 2; if (!newer(queue.items[i], queue.items[parent])) break; std.mem.swap(Queued, &queue.items[i], &queue.items[parent]); i = parent; }}
fn popQueued(queue: *std.ArrayList(Queued)) ?Index { const items = queue.items; if (items.len == 0) return null; const top = items[0].commit; items[0] = items[items.len - 1]; queue.items.len -= 1; var i: usize = 0; const n = queue.items.len; while (true) { const l = 2 * i + 1; if (l >= n) break; var best = l; if (l + 1 < n and newer(queue.items[l + 1], queue.items[l])) best = l + 1; if (!newer(queue.items[best], queue.items[i])) break; std.mem.swap(Queued, &queue.items[i], &queue.items[best]); i = best; } return top;}