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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! The pickaxe: changed paths kept only where they change what is looked//! for, as gitdiffcore(7) describes `-S`, `-G` and `--find-object`, and//! `--pickaxe-all` keeping every path of a diff where one is kept.//!//! What the documentation leaves out was found by asking git 2.56, one//! commit at a time, whether it kept a change between two texts chosen//! to tell rules apart (the probes are in the notes of the change that//! brought this in)://!//! - `-S<string>` counts the string's occurrences in each side without//! letting them overlap (`aaaa` holds `aa` twice), and keeps a path whose//! two counts differ; an absent side holds none. NUL bytes are searched//! over like any other, so binary files are searched too. `-i` makes the//! comparison ignore the case of ASCII letters.//! - With `--pickaxe-regex` the string is an extended regular expression,//! compiled as `REG_NEWLINE` compiles it (`.` and `^`, `$` keep to a line)//! and with GNU's escapes, `.` matching no NUL. Its matches are counted//! by searching again where the last one ended, the rest of the text//! taken as a new text that does not begin a line (`REG_NOTBOL`: `^`//! does not match at its start, even just after a newline, while `\<`,//! `\b` and `` \` `` do, seeing nothing before it). A match that is empty//! counts, and the search goes on one byte further. Searching stops at//! the end of the text, so an empty match there is not counted unless it//! is the first search's.//! - `-G<regex>` keeps a path whose line diff adds or deletes a line the//! expression (extended, `REG_NEWLINE`, GNU's escapes) matches. Each//! line is matched alone, with its newline (one is added to a last line//! that has none, so `^$` matches every changed line); the `+` or `-`//! of the patch is not part of it, and context lines are not looked at.//! The line diff is the plain one, whatever the whitespace options say;//! a type change is compared as the two sides' contents, not as the//! deletion and addition the patch shows. A binary file is passed over//! unless `--text` is given.//! - `--find-object=<object>` keeps a path whose old or new side is that//! object, whatever its mode or path (a rename of it is kept, and so is a//! change of its mode alone).//! - `--pickaxe-all` keeps every path when any is kept, and nothing//! otherwise. `--diff-filter` applies afterwards.
const std = @import("std");const Allocator = std.mem.Allocator;
const object = @import("../object.zig");const regex = @import("../regex.zig");const LineDiff = @import("LineDiff.zig");const output = @import("output.zig");
const Pickaxe = @This();
/// What is looked for.pub const Kind = enum { /// `-S<string>`: a fixed string, counted. string, /// `-S<regex> --pickaxe-regex`: an extended regular expression, /// counted. counted_regex, /// `-G<regex>`: an extended regular expression, matched against the /// lines a diff adds and deletes. lines, /// `--find-object=<object>`. object,};
kind: Kind,/// The string for `string`.needle: []const u8 = "",/// The compiled pattern for `counted_regex` and `lines`.pattern: ?regex.Regex = null,/// The objects for `object`: `--find-object` may be given more than/// once, and a side that is any of them is kept.ids: []const object.Id = &.{},/// `-i`, `--regexp-ignore-case`.ignore_case: bool = false,/// `--pickaxe-all`.all: bool = false,
/// Why a pickaxe's pattern was not compiled.pub const CompileError = regex.Error;
/// A pickaxe looking for `text` as `kind` says (any but `object`); on/// `InvalidPattern` or `Unsupported`, `failure` says why. `text` must/// outlive it.pub fn init(gpa: Allocator, kind: Kind, text: []const u8, ignore_case: bool, failure: ?*regex.Failure) CompileError!Pickaxe { switch (kind) { .string => return .{ .kind = .string, .needle = text, .ignore_case = ignore_case }, .counted_regex, .lines => { const r = try regex.Regex.compileWith(gpa, text, .{ .syntax = .extended, .newline = true, .gnu = true, .ignore_case = ignore_case, .dot_excludes_nul = true, }, failure); return .{ .kind = kind, .pattern = r, .ignore_case = ignore_case }; }, .object => unreachable, }}
/// A pickaxe looking for the objects `ids`, which must outlive it.pub fn initObjects(ids: []const object.Id) Pickaxe { return .{ .kind = .object, .ids = ids };}
/// Frees the pattern.pub fn deinit(p: *Pickaxe) void { if (p.pattern) |*r| r.deinit(); p.* = undefined;}
/// How many times `-S` finds what it looks for in `text`.pub fn count(p: *const Pickaxe, gpa: Allocator, text: []const u8) Allocator.Error!usize { switch (p.kind) { .string => return countString(p.needle, text, p.ignore_case), .counted_regex => { const r = &p.pattern.?; var n: usize = 0; var pos: usize = 0; while (pos < text.len) { const m = try r.search(gpa, text[pos..], pos != 0) orelse break; n += 1; pos += if (m.end == m.start) m.start + 1 else m.end; } return n; }, .lines, .object => unreachable, }}
fn countString(needle: []const u8, text: []const u8, ignore_case: bool) usize { if (needle.len == 0) return 0; var n: usize = 0; var pos: usize = 0; while (pos + needle.len <= text.len) { const here = text[pos .. pos + needle.len]; const same = if (ignore_case) std.ascii.eqlIgnoreCase(here, needle) else std.mem.eql(u8, here, needle); if (same) { n += 1; pos += needle.len; } else pos += 1; } return n;}
/// Whether `-G` finds a line it matches among those the line diff of/// `old` and `new` adds or deletes, compared with `algorithm`.pub fn changesLines(p: *const Pickaxe, gpa: Allocator, old: []const u8, new: []const u8, algorithm: LineDiff.Algorithm) LineDiff.Error!bool { var d = try LineDiff.compute(gpa, old, new, .{ .algorithm = algorithm, .indent_heuristic = false }); defer d.deinit(gpa); var line: std.ArrayList(u8) = .empty; defer line.deinit(gpa); for ([_]LineDiff.Lines{ d.a, d.b }, [_][]const bool{ d.a_changed, d.b_changed }) |lines, changed| { for (changed, 0..) |c, i| { if (!c) continue; const text = lines.line(i); if (text.len != 0 and text[text.len - 1] == '\n') { if (try p.pattern.?.matches(gpa, text)) return true; continue; } line.clearRetainingCapacity(); try line.appendSlice(gpa, text); try line.append(gpa, '\n'); if (try p.pattern.?.matches(gpa, line.items)) return true; } } return false;}
/// What filtering can fail with.pub const Error = output.Error || error{ /// `-S` or `-G` met a tree's pair (`-t`), whose sides git cannot /// read as files to diff. TreeContents,};
/// Whether pair `p` changes what is looked for. `options` are the/// formats' options: their `--text` and binary rules decide which files/// `-G` passes over, and their algorithm is the line diff's.pub fn keeps(pk: *const Pickaxe, gpa: Allocator, p: *const output.Pair, source: output.Source, drivers: output.Drivers, options: output.Options) Error!bool { if (pk.kind == .object) { for (pk.ids) |id| { if (p.old.present() and p.old.id_known and p.old.id.eql(id)) return true; if (p.new.present() and p.new.id_known and p.new.id.eql(id)) return true; } return false; } if (output.isTree(p)) return error.TreeContents; var ob: [64 + object.max_hex_length]u8 = undefined; var nb: [64 + object.max_hex_length]u8 = undefined; const old: output.Contents = if (p.old.present()) try output.load(gpa, p, p.old, true, source, &ob) else .{ .bytes = "" }; defer output.free(gpa, old); const new: output.Contents = if (p.new.present()) try output.load(gpa, p, p.new, false, source, &nb) else .{ .bytes = "" }; defer output.free(gpa, new); switch (pk.kind) { .string, .counted_regex => return try pk.count(gpa, old.bytes) != try pk.count(gpa, new.bytes), .lines => { const driver = try drivers.get(drivers.context, p.path); if (output.binaryPair(p, old.bytes, new.bytes, driver, options)) return false; return pk.changesLines(gpa, old.bytes, new.bytes, options.patch.lines.algorithm); }, .object => unreachable, }}
/// The pairs of `pairs` the pickaxe keeps: those it finds a change in,/// or with `--pickaxe-all` every one if it finds any. The caller frees/// the list.pub fn filter(pk: *const Pickaxe, gpa: Allocator, pairs: []const output.Pair, source: output.Source, drivers: output.Drivers, options: output.Options) Error![]output.Pair { var kept: std.ArrayList(output.Pair) = .empty; errdefer kept.deinit(gpa); for (pairs) |*p| { if (!try pk.keeps(gpa, p, source, drivers, options)) continue; if (pk.all) { kept.clearRetainingCapacity(); try kept.appendSlice(gpa, pairs); break; } try kept.append(gpa, p.*); } return kept.toOwnedSlice(gpa);}
test "fixed strings are counted without overlapping" { try std.testing.expectEqual(@as(usize, 2), countString("aa", "aaaa", false)); try std.testing.expectEqual(@as(usize, 2), countString("aa", "aaaaa", false)); try std.testing.expectEqual(@as(usize, 2), countString("a", "a\x00a", false)); try std.testing.expectEqual(@as(usize, 2), countString("a", "aA", true)); try std.testing.expectEqual(@as(usize, 0), countString("abc", "ab", false));}
test "a pattern's matches are counted as git counts them" { const gpa = std.testing.allocator; const cases = [_]struct { []const u8, []const u8, usize }{ // Empty matches count, one byte at a time, but not at the end. .{ "a*", "x\n", 2 }, .{ "a*", "aaa\n", 2 }, .{ "a*", "aa aa\n", 4 }, .{ "a*", "", 0 }, // `^` keeps to lines, and not where a search resumes. .{ "^a", "aa", 1 }, .{ "^a", "a\na\n", 2 }, .{ "^a*", "\na", 1 }, .{ "^a*", "x\na", 2 }, // `\<` and `` \` `` see nothing before where a search resumes. .{ "\\<a", "aa", 2 }, .{ "\\`a", "aa", 2 }, // `.` matches no NUL or newline. .{ "a.b", "a\x00b", 0 }, .{ "a.", "a\nb", 0 }, .{ "a[^x]b", "a\x00b", 1 }, }; for (cases) |c| { var p = try Pickaxe.init(gpa, .counted_regex, c[0], false, null); defer p.deinit(); std.testing.expectEqual(c[2], try p.count(gpa, c[1])) catch |err| { std.debug.print("pattern '{s}' text '{s}'\n", .{ c[0], c[1] }); return err; }; }}
test "-G matches each changed line with its newline" { const gpa = std.testing.allocator; const cases = [_]struct { []const u8, []const u8, []const u8, bool }{ .{ "^y", "x\n", "y\n", true }, .{ "^\\+", "x\n", "y\n", false }, .{ "y\n", "x\ny\n", "y", true }, .{ "y\\'", "x\ny\n", "y", false }, .{ "^$", "x\n", "x\nq", true }, .{ "a", "a\nb\nc\n", "a\nB\nc\n", false }, .{ "x\ny", "z\n", "x\ny\n", false }, .{ "\\`y", "z\n", "x\ny\n", true }, .{ "b", "x\n", "a\x00b\n", true }, .{ "a.b", "x\n", "a\x00b\n", false }, }; for (cases) |c| { var p = try Pickaxe.init(gpa, .lines, c[0], false, null); defer p.deinit(); std.testing.expectEqual(c[3], try p.changesLines(gpa, c[1], c[2], .myers)) catch |err| { std.debug.print("pattern '{s}'\n", .{c[0]}); return err; }; }}
const fuzz_input = @import("../testing/fuzz.zig");
/// A pattern line, then a text: its `--pickaxe-regex` count must not run/// past the text, and a fixed string's count must not exceed what fits.fn fuzzCount(_: void, smith: *std.testing.Smith) anyerror!void { const gpa = std.testing.allocator; var buffer: [512]u8 = undefined; const input = fuzz_input.bytes(smith, &buffer); const nl = std.mem.findScalar(u8, input, '\n') orelse return; const pattern = input[0..nl]; const text = input[nl + 1 ..]; if (pattern.len != 0) { const n = countString(pattern, text, false); try std.testing.expect(n * pattern.len <= text.len); } var p = Pickaxe.init(gpa, .counted_regex, pattern, false, null) catch return; defer p.deinit(); try std.testing.expect(try p.count(gpa, text) <= text.len + 1);}
test "fuzz: pickaxe counts" { try fuzz_input.fuzz({}, fuzzCount, .{ .corpus = &.{@embedFile("../fuzz/pickaxe-count")} });}