Skip to content
zit Artifact [b3cba2d357]
Login

Artifact [b3cba2d357]

Artifact b3cba2d357230dc12fcd7d4e9f4be7752c07b8cf07c4bdaf4ebf1e607767b99d:


//! `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("../cli/diagnostics.zig");
const help_pages = @import("../cli/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;
}