//! `zit grep`: search a file's historic versions, and the pickaxe search
//! over diffs.
const std = @import("std");
const zit = @import("zit");
const cli = @import("zit").cli;
const logstore = @import("zit").logstore;
const Repository = @import("zit").Repository;
const repostate = zit.repostate;
const diagnostics = @import("../diagnostics.zig");
const help_pages = @import("../help.zig");
const stateOom = diagnostics.stateOom;
const repoOpenFail = diagnostics.repoOpenFail;
const openRepo = diagnostics.openRepo;
const grep_help = help_pages.grep_help;
// The PATH walk is the library core's, shared with the daemon's `log`.
const filelog = zit.filelog;
const NameTable = filelog.NameTable;
// The annotation gather is the library core's, shared with the daemon.
const core_blame = zit.blame;
const annotateTouchedFromCache = core_blame.annotateTouchedFromCache;
/// `zit grep PATTERN PATH...` — search a file's HISTORY for a literal.
///
/// The gap this closes is that zit had no content search at all: not `git log
/// -S`'s pickaxe, and not `fossil grep`'s file-scoped walk. Working-tree search
/// is deliberately NOT here — ripgrep does that faster than zit would, and the
/// bytes are on disk for it to read. What only zit can do is search content
/// that is not on disk at all, because it lives as delta chains inside `.zit`.
///
/// Semantics are `fossil grep`'s: walk the named file's historic versions
/// newest-first and report each DISTINCT version whose content matches. A run
/// of check-ins that left the file untouched reports once, not once per
/// check-in, because they share one blob.
pub fn runGrep(
gpa: std.mem.Allocator,
io: std.Io,
arena: std.mem.Allocator,
verb_args: []const []const u8,
streams: cli.Streams,
amb: cli.Ambient,
) cli.Exit {
const parsed = switch (cli.parseGrepArgs(verb_args)) {
.ok => |p| p,
.unknown_option => |tok| return cli.usageError(streams, "grep", .unknown_option, tok),
.extra_argument => |tok| return cli.usageError(streams, "grep", .extra_argument, tok),
.bad_limit => |tok| return cli.usageError(streams, "grep", .bad_limit, tok),
.no_name => return cli.usageError(streams, "grep", .no_name, ""),
.no_paths => return cli.usageError(streams, "grep", .no_paths, ""),
.both_pickaxes => {
streams.err.writeAll("zit grep: -S and -G ask different questions; give one\n") catch {};
return .usage;
},
};
if (parsed.help) {
streams.out.writeAll(grep_help) catch {};
return .ok;
}
const pattern = parsed.pattern.?;
if (pattern.len == 0) {
streams.err.writeAll("zit grep: PATTERN must not be empty\n") catch {};
return .failure;
}
var repo: Repository = undefined;
var root_dir: std.Io.Dir = undefined;
const rc = openRepo(gpa, io, arena, streams, "grep", amb.repo_override, parsed.no_cache, false, &repo, &root_dir);
if (rc != .ok) return rc;
defer root_dir.close(io);
defer repo.deinit(gpa);
const log = repo.logStore(gpa) catch |e| return repoOpenFail(streams, "grep", e);
if (parsed.pickaxe or parsed.diff_match) {
const exit = runPickaxe(gpa, arena, &repo, log, parsed, streams);
cli.horizonHistoryNote(gpa, io, root_dir, streams, "grep");
return exit;
}
// The plaintext memo: successive check-ins share delta bases, and this walk reads
// one blob per file per version. Without it each read re-resolves the same
// base chain.
var plaintext: logstore.PlaintextCache = .{};
defer plaintext.deinit(gpa);
// Newest-first and totally ordered, which is the order `fossil grep`
// reports and the order an operator reads history in.
const rids = repo.state().checkinsByMtime(gpa) catch return stateOom(streams, "grep");
defer gpa.free(rids);
var matched: usize = 0;
var unreadable: usize = 0;
for (parsed.paths[0..parsed.path_count]) |path| {
// The cache's records name the check-ins that changed PATH
// against their primary parent, so a manifest is read only there — the
// same scan annotate makes — instead of once per check-in in the
// store. Without a cache every check-in is read, as before.
var grep_names = NameTable.init(gpa);
defer grep_names.deinit(gpa);
const grep_name = grep_names.intern(gpa, path) catch return stateOom(streams, "grep");
var touched = annotateTouchedFromCache(gpa, io, &repo, &grep_names, path, false);
defer if (touched) |*t| t.deinit(gpa);
// `fossil grep`'s shape: each distinct version once, under the OLDEST
// check-in that introduced it, versions ordered by that check-in's
// time newest-first. A merge that carries a branch's version to trunk,
// or a revert, introduces nothing. Walking oldest-first and keeping
// the first sighting of each blob yields exactly that list, reversed.
var versions: std.ArrayList(struct { rid: repostate.Rid, hash: []const u8 }) = .empty;
defer versions.deinit(gpa);
var seen = std.StringHashMapUnmanaged(void).empty;
defer seen.deinit(gpa);
var i: usize = rids.len;
while (i > 0) {
i -= 1;
const rid = rids[i];
if (touched) |*t| {
if (t.covered.contains(rid) and !t.touched.contains(.{ .rid = rid, .name = grep_name })) continue;
}
const card = (repo.fileAt(gpa, rid, path) catch continue) orelse continue; // absent here
defer Repository.freeFileCard(gpa, card);
// Dupe: the card is freed at the loop's end.
const h = arena.dupe(u8, card.hash.?) catch return stateOom(streams, "grep"); // §4.7.6: no delete markers
const gop = seen.getOrPut(gpa, h) catch return stateOom(streams, "grep");
if (gop.found_existing) continue;
versions.append(gpa, .{ .rid = rid, .hash = h }) catch return stateOom(streams, "grep");
}
var v = versions.items.len;
while (v > 0) {
v -= 1;
if (parsed.limit) |n| if (n != 0 and matched >= n) break;
const rid = versions.items[v].rid;
const h = versions.items[v].hash;
const bytes = grepBlobBytes(gpa, log, &plaintext, h) orelse {
// Elided by a sparse store, shunned, or a phantom. Counted and
// reported at the end rather than skipped in silence: a search
// that quietly examined less than it claimed is the failure
// mode that looks exactly like "no matches".
unreadable += 1;
continue;
};
defer gpa.free(bytes);
if (zit.textdiff.isBinary(bytes)) continue; // a NUL-bearing blob has no lines
if (grepReport(streams.out, repo.hashOf(rid), path, bytes, pattern, GrepMode.fromArgs(parsed))) matched += 1;
}
}
if (unreadable != 0) {
streams.err.print(
"zit grep: {d} version(s) could not be read (sparse, shunned, or phantom) and were not searched\n",
.{unreadable},
) catch {};
_ = cli.horizonContentNote(gpa, repo.io, repo.root_dir, streams, "grep");
}
cli.horizonHistoryNote(gpa, io, root_dir, streams, "grep");
// `0` found something, `1` found nothing — the shell convention every grep
// follows, so this composes in a conditional.
return if (matched != 0) .ok else .failure;
}
/// The pickaxe: report the check-ins where the NUMBER OF
/// OCCURRENCES of PATTERN changed, which is `git log -S`.
///
/// The distinction from slice 1 is the question, not the mechanism. `zit grep`
/// answers "which versions contain this", and a string that sat unchanged
/// through two hundred check-ins is reported for each version that held it.
/// The pickaxe answers "when did this appear, and when did it go" — for that
/// same string, exactly two lines.
///
/// THE FEARED COST IS AVOIDABLE. The naive reading is that this "needs a diff per
/// revision rather than a match per revision". It does not: a path whose blob
/// hash is IDENTICAL in a check-in and its parent cannot have changed the
/// count, so the walk compares F-card hashes first and reads blobs only for the
/// paths that actually differ. On ordinary history that is a handful of files
/// per check-in rather than the whole tree, and it is the same observation that
/// lets slice 1 share one blob across a run of untouching check-ins.
///
/// MERGES are compared against the PRIMARY parent only, so content arriving
/// through a merge is attributed to the merge check-in. `git log -S` does the
/// same under its default history simplification, and the alternative — a
/// check-in counted against every parent — reports one appearance twice.
fn runPickaxe(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
repo: *Repository,
log: *logstore.LogStore,
parsed: cli.GrepArgs,
streams: cli.Streams,
) cli.Exit {
const pattern = parsed.pattern.?;
var plaintext: logstore.PlaintextCache = .{};
defer plaintext.deinit(gpa);
const rids = repo.state().checkinsByMtime(gpa) catch return stateOom(streams, "grep");
defer gpa.free(rids);
var matched: usize = 0;
var unreadable: usize = 0;
for (rids) |rid| {
if (parsed.limit) |n| if (n != 0 and matched >= n) break;
// The parent's path -> blob-hash map, which is what makes "did this
// path change" a string comparison instead of a blob read.
var parent_of: std.StringHashMapUnmanaged([]const u8) = .empty;
defer parent_of.deinit(gpa);
var parent_list: ?Repository.FileList = null;
defer if (parent_list) |*pl| pl.deinit(gpa);
if (repo.state().primaryParentOf(rid)) |prid| {
if (repo.files(gpa, prid) catch null) |pl| {
parent_list = pl;
var pit = parent_list.?.iterator();
while (pit.next()) |f| {
const h = f.hash orelse continue;
parent_of.put(gpa, f.filename, h) catch return stateOom(streams, "grep");
}
}
}
var list = (repo.files(gpa, rid) catch continue) orelse continue;
defer list.deinit(gpa);
// Signed, because the two directions are the whole point: a check-in
// that adds two occurrences and removes two has not changed the count
// and is not a hit, exactly as `git log -S` treats it. Under `-G` this
// instead counts the changed LINES that mention the pattern, which is
// why that case is unsigned and reported with a different marker.
var delta: isize = 0;
var hit_path: ?[]const u8 = null;
var it = list.iterator();
while (it.next()) |f| {
const h = f.hash orelse continue;
if (!pathWanted(parsed, f.filename)) continue;
const before = parent_of.get(f.filename);
if (before) |b| if (std.mem.eql(u8, b, h)) continue; // untouched: neither answer can move
if (parsed.diff_match) {
const n = diffMentions(gpa, log, &plaintext, before, h, pattern) orelse {
unreadable += 1;
continue;
};
if (n != 0) {
delta += @intCast(n);
if (hit_path == null) hit_path = arena.dupe(u8, f.filename) catch null;
}
continue;
}
const now = pickaxeCount(gpa, log, &plaintext, h, pattern) orelse {
unreadable += 1;
continue;
};
const was = if (before) |b|
pickaxeCount(gpa, log, &plaintext, b, pattern) orelse blk: {
unreadable += 1;
break :blk 0;
}
else
0;
if (now != was) {
delta += @as(isize, @intCast(now)) - @as(isize, @intCast(was));
if (hit_path == null) hit_path = arena.dupe(u8, f.filename) catch null;
}
}
// A path the parent had and this check-in does not: its occurrences are
// gone, and a deletion is the half of "when did it go" that a walk over
// only the child's files would miss entirely.
var pit = parent_of.iterator();
while (pit.next()) |e| {
const name = e.key_ptr.*;
if (!pathWanted(parsed, name)) continue;
if (listHolds(&list, name)) continue;
if (parsed.diff_match) {
// The file is gone, so every line it had is a removed line.
const n = diffMentions(gpa, log, &plaintext, e.value_ptr.*, null, pattern) orelse {
unreadable += 1;
continue;
};
if (n != 0) {
delta += @intCast(n);
if (hit_path == null) hit_path = arena.dupe(u8, name) catch null;
}
continue;
}
const was = pickaxeCount(gpa, log, &plaintext, e.value_ptr.*, pattern) orelse {
unreadable += 1;
continue;
};
if (was != 0) {
delta -= @as(isize, @intCast(was));
if (hit_path == null) hit_path = arena.dupe(u8, name) catch null;
}
}
if (delta == 0) continue;
const id = repo.hashOf(rid);
// Data only, one line per check-in: id, signed delta, and the first
// path that moved. The machine-verb shape, because quarry indexes
// this repository and a search it cannot parse is a search it cannot use.
streams.out.print("{s} {s}{d} {s}\n", .{
id[0..@min(id.len, 12)],
if (parsed.diff_match) "~" else if (delta > 0) "+" else "-",
@abs(delta),
hit_path orelse "",
}) catch {};
matched += 1;
}
if (unreadable != 0) {
streams.err.print(
"zit grep: {d} version(s) could not be read (sparse, shunned, or phantom) and were not searched\n",
.{unreadable},
) catch {};
_ = cli.horizonContentNote(gpa, repo.io, repo.root_dir, streams, "grep");
}
return if (matched != 0) .ok else .failure;
}
/// Under `-S`, PATH operands narrow the walk rather than drive it; with none
/// given every path is wanted.
fn pathWanted(parsed: cli.GrepArgs, name: []const u8) bool {
if (parsed.path_count == 0) return true;
for (parsed.paths[0..parsed.path_count]) |p| {
if (std.mem.eql(u8, p, name)) return true;
// A directory operand covers its subtree, on the segment boundary so
// `src` never matches `src-vendor`.
if (name.len > p.len and name[p.len] == '/' and std.mem.startsWith(u8, name, p)) return true;
}
return false;
}
fn listHolds(list: anytype, name: []const u8) bool {
var it = list.iterator();
while (it.next()) |f| {
if (std.mem.eql(u8, f.filename, name)) return true;
}
return false;
}
/// `-G`: how many CHANGED lines between two versions of one path mention
/// `pattern`. Null when either blob is unreadable. A null `to` means the path
/// was deleted, so every line it had is a removed line.
///
/// This is where `-G` earns its existence. Renaming `x = SECRET` to
/// `y = SECRET` leaves the occurrence count at one, so `-S` reports nothing —
/// correctly, by its own definition — while the line plainly changed. Asking
/// the diff rather than the counts is the only way to see that, and it is why
/// this half is the expensive one: it runs the diff engine per changed path
/// instead of two substring scans.
fn diffMentions(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
cache: *logstore.PlaintextCache,
from: ?[]const u8,
to: ?[]const u8,
pattern: []const u8,
) ?usize {
const a = if (from) |h| grepBlobBytes(gpa, log, cache, h) orelse return null else null;
defer if (a) |bytes| gpa.free(bytes);
const b = if (to) |h| grepBlobBytes(gpa, log, cache, h) orelse return null else null;
defer if (b) |bytes| gpa.free(bytes);
const a_bytes: []const u8 = a orelse "";
const b_bytes: []const u8 = b orelse "";
// A NUL-bearing version has no lines to change, matching the rule the rest
// of this verb applies.
if (zit.textdiff.isBinary(a_bytes) or zit.textdiff.isBinary(b_bytes)) return 0;
var buf: std.ArrayList(u8) = .empty;
defer buf.deinit(gpa);
// Context 0: only the lines that actually changed are candidates, so no
// unchanged neighbour can be mistaken for one.
zit.textdiff.unified(gpa, a_bytes, b_bytes, .{ .context = 0 }, &buf) catch return null;
var n: usize = 0;
var rest: []const u8 = buf.items;
while (rest.len != 0) {
const nl = std.mem.indexOfScalar(u8, rest, '\n') orelse rest.len;
const line = rest[0..nl];
if (nl == rest.len) rest = "" else rest = rest[nl + 1 ..];
if (line.len == 0) continue;
// `+`/`-` are changed lines; `+++`/`---` are the file headers and
// carry the PATH, which would match a pattern naming a filename and
// report every check-in that touched it.
if (line[0] != '+' and line[0] != '-') continue;
if (std.mem.startsWith(u8, line, "+++") or std.mem.startsWith(u8, line, "---")) continue;
if (std.mem.indexOf(u8, line[1..], pattern) != null) n += 1;
}
return n;
}
/// Non-overlapping occurrences of `pattern` in one blob, or null when the store
/// cannot produce it. A binary blob counts zero rather than being skipped: for
/// the pickaxe "it is not there" and "we did not look" must not be the same
/// answer, and a NUL-bearing blob has no lines to report anyway.
fn pickaxeCount(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
cache: *logstore.PlaintextCache,
hash: []const u8,
pattern: []const u8,
) ?usize {
const bytes = grepBlobBytes(gpa, log, cache, hash) orelse return null;
defer gpa.free(bytes);
if (zit.textdiff.isBinary(bytes)) return 0;
var n: usize = 0;
var at: usize = 0;
while (std.mem.indexOfPos(u8, bytes, at, pattern)) |i| {
n += 1;
at = i + pattern.len;
}
return n;
}
/// Print every matching line of one version. Returns whether any matched, so
/// the caller counts VERSIONS rather than lines.
/// How grep selects and prints lines (-i -c -l -v --once).
const GrepMode = struct {
ignore_case: bool = false,
count_only: bool = false,
files_only: bool = false,
invert: bool = false,
once: bool = false,
fn fromArgs(a: cli.GrepArgs) GrepMode {
return .{ .ignore_case = a.ignore_case, .count_only = a.count_only, .files_only = a.files_only, .invert = a.invert, .once = a.once };
}
};
fn grepLineMatches(line: []const u8, pattern: []const u8, ignore_case: bool) bool {
if (!ignore_case) return std.mem.indexOf(u8, line, pattern) != null;
if (pattern.len == 0) return true;
if (line.len < pattern.len) return false;
var i: usize = 0;
while (i + pattern.len <= line.len) : (i += 1) {
if (std.ascii.eqlIgnoreCase(line[i..][0..pattern.len], pattern)) return true;
}
return false;
}
fn grepReport(out: *std.Io.Writer, checkin: []const u8, path: []const u8, bytes: []const u8, pattern: []const u8, mode: GrepMode) bool {
var hits: usize = 0;
var lineno: usize = 1;
var rest = bytes;
while (rest.len != 0) {
const nl = std.mem.indexOfScalar(u8, rest, '\n') orelse rest.len;
const line = rest[0..nl];
if (grepLineMatches(line, pattern, mode.ignore_case) != mode.invert) {
hits += 1;
if (!mode.count_only and !mode.files_only) {
out.print("{s} {s}:{d}: {s}\n", .{ checkin[0..@min(checkin.len, 12)], path, lineno, line }) catch {};
}
if (mode.once or mode.files_only) break;
}
if (nl == rest.len) break;
rest = rest[nl + 1 ..];
lineno += 1;
}
if (hits != 0 and mode.files_only) {
out.print("{s} {s}\n", .{ checkin[0..@min(checkin.len, 12)], path }) catch {};
} else if (mode.count_only) {
out.print("{s} {s}:{d}\n", .{ checkin[0..@min(checkin.len, 12)], path, hits }) catch {};
}
return hits != 0;
}
/// One blob's plaintext, or null when the store cannot produce it.
fn grepBlobBytes(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
cache: *logstore.PlaintextCache,
hash: []const u8,
) ?[]u8 {
const rid = (log.resolveHexPrefix(hash) catch return null) orelse return null;
return (log.contentCached(gpa, rid, cache) catch return null) orelse null;
}