// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>
// SPDX-License-Identifier: MIT

//! A commit walk: the commits reachable from some starting points and not
//! from others, in git's orders, limited as `git rev-list` limits them,
//! with the boundary commits and the sides of a symmetric difference that
//! `--boundary` and `--left-right` show.
//!
//! Every rule here was found by building histories with `git fast-import`
//! — merges, octopus merges, equal timestamps, clocks that run backwards —
//! and comparing what a model of the rule listed with what `git rev-list`
//! listed, until they agreed on every range and option tried:
//!
//! - **The queue** holds commits by commit date, newest first; among
//!   commits of one date, the one put in first comes out first. Starting
//!   points go in in the order given.
//! - **Without exclusions** (and without an ordering or `--children` or
//!   `--ancestry-path`), commits are listed as they come out of the queue,
//!   their parents going in as each comes out, and the walk stops as soon
//!   as it has listed enough for `--max-count`, or meets a commit older
//!   than `--since`.
//! - **With exclusions**, the walk first works out the whole list. An
//!   excluded commit's parents are excluded as it comes out, and so is
//!   every commit already read that they reach; so are the parents of an
//!   excluded starting point before anything comes out, and the parents of
//!   every parent of an excluded commit, through every commit read so far,
//!   since reading a commit tells git its parents. A commit that comes out
//!   included is listed, and dropped again if it is excluded later. The
//!   walk stops when the queue is empty, or after the fifth excluded commit
//!   in a row to come out while every commit queued is excluded and none
//!   is newer than the last commit listed; any other excluded commit
//!   coming out starts the count again. That is how git tolerates clocks
//!   that run backwards, and it can list a commit that an excluded one
//!   reaches through commits dated far out of order, as git does. A commit
//!   older than `--since` is excluded as it comes out.
//! - **`--topo-order`** lists, from the commits no listed commit names as
//!   a parent, last first, each commit and then its parents depth first,
//!   a parent only once every commit naming it has been listed;
//!   **`--date-order`** and **`--author-date-order`** take the newest such
//!   commit by commit or author date instead. All three count every parent,
//!   even with `--first-parent`, and sort the list with the commits later
//!   excluded still in it.
//! - **`--boundary`** lists, after the rest, the parents of listed commits
//!   that were not listed — excluded, filtered out or past `--max-count`
//!   — found in the order listed and taken last first, then sorted as the
//!   list is (depth first unless the order is by date), knowing only the
//!   parents of commits that have been read.
//! - **`--children`** names, for each commit, the commits in the sorted
//!   list, the later-excluded ones included, that name it as a parent,
//!   the last in the list first.
//! - **`--max-parents`**, **`--min-parents`**, **`--left-only`** and
//!   **`--right-only`** filter what is listed without changing the walk;
//!   **`--until`** and **`--since-as-filter`** keep a commit out of the
//!   list of a walk with exclusions or an ordering before it is sorted,
//!   and out of what is listed otherwise; **`--skip`** and
//!   **`--max-count`** come after them, and **`--reverse`** after all of
//!   it, boundary commits included.
//!
//! With a commit-graph, git walks `--topo-order`, `--date-order` and
//! `--author-date-order` by generation number, unless `--children`,
//! `--left-only`, `--right-only`, `--ancestry-path`, `--simplify-merges`
//! or `--simplify-by-decoration` makes it work out the whole list first
//! (then the rules above apply, except that a walk with exclusions goes
//! on until no queued commit could reach a listed one by generation
//! number, the stop rule not being needed). The walk by generation
//! number was found the same way, counting alongside the output how many
//! commits each of its three walks took, as git's trace2 `topo_walk`
//! statistics report them:
//!
//! - **The explore walk** takes commits from a queue ordered by
//!   generation number, then commit date, highest first, then first
//!   queued. It reads each commit, excludes it if it is older than
//!   `--since`, processes it as the walk without a graph does (excluding
//!   an excluded commit's parents, simplifying it when limited to paths)
//!   and queues every parent it has then that it has not queued before.
//!   A commit not yet read is compared as one of infinite generation
//!   number and no date, and is not moved when it is read while it
//!   waits; taking the first entry leaves it in place until the queue is
//!   next used, when a push takes its place. A commit the graph does not
//!   list has an infinite generation number.
//! - **The indegree walk** takes commits from a queue ordered the same
//!   way, explores down to each one's generation number, and counts it
//!   as a child of its parents — of its first parent only, with
//!   `--first-parent` — queueing each parent the first time.
//! - **The topological walk** starts once children have been counted down
//!   to the lowest generation number of the starting points, from those
//!   no other reached: newest first with `--topo-order` (the first given
//!   first among equal dates), into a queue by commit or author date
//!   otherwise. It takes a commit, processes it, and for each parent not
//!   excluded by then — with `--first-parent`, the first such parent
//!   only, a later one when the first is excluded — counts children down
//!   to that parent's generation number and counts the commit out; a
//!   parent left waiting for no child is queued, on a stack with
//!   `--topo-order` and newest first, first in first out, by date
//!   otherwise. git reads an author date as it explores a commit (or
//!   reads a starting point); a commit queued by author date before that
//!   is ordered otherwise, by a rule not matched, and is refused. A
//!   commit older than `--since` is never queued.
//! - A commit taken is listed unless it is excluded or older than
//!   `--since` by then, or the filters keep it out; `--skip`,
//!   `--max-count`, `--boundary` and `--reverse` then work as above.
//!
//! So nothing an excluded commit reaches is listed, as its generation
//! numbers make sure the exclusion arrives first; but a commit older than
//! `--since` excludes what it reaches only once explored, and the walk
//! goes only as deep as it needs to. With paths, a commit is simplified
//! as it is explored, or earlier when rewriting reaches it, TREESAME
//! being decided once with the exclusions known then, and the relevant
//! parents that `--full-history` counts are counted as it is listed.
//!
//! **History simplification**, for a walk limited to paths, was found the
//! same way, over histories whose commits change files, and agrees with
//! git-rev-list(1)'s "History Simplification" where it speaks:
//!
//! - A commit is simplified as it is processed, which is once, when it
//!   comes out of the queue or earlier when rewriting reaches it. A root
//!   is TREESAME when the pathspec matches nothing in its tree; an
//!   excluded commit is never simplified. A commit simplified before it
//!   is excluded passes the exclusion on only to the parents
//!   simplification left it, as git has replaced the rest.
//! - A merge's parents are **relevant** when they are not excluded, or are
//!   excluded starting points; a commit with one parent always counts it,
//!   and relevance is counted over every parent even with
//!   `--first-parent`, which compares the first alone and keeps the
//!   others unless the merge is TREESAME to it. By default the walk
//!   follows only the first relevant parent a merge is TREESAME to, and
//!   the merge is TREESAME. Otherwise it follows every parent, and the
//!   commit is TREESAME when it is TREESAME to every relevant parent — or,
//!   with none, to every parent. A walk with exclusions decides again once
//!   it has them all, counting only the parents still relevant and keeping
//!   what it had when none is.
//! - A commit is listed unless it is TREESAME, with `--sparse`, or with
//!   `--full-history` and rewritten parents when it has more than one
//!   relevant parent, counted as it is listed. `--sparse` compares no
//!   commit with one parent, and compares merges as the rest does.
//! - **Rewriting** (`--parents`, `--children`, `--simplify-merges`, never
//!   with `--sparse`) happens as each commit is listed, before `--skip`
//!   counts it: each parent, every one even with `--first-parent`, is
//!   followed, processing what it reaches, until
//!   one is excluded, not TREESAME, a pull, or a merge — through which it
//!   goes on when the merge has exactly one relevant parent — and a root
//!   that is TREESAME is dropped. git lets go of a commit's parents once it
//!   has printed it, so that walking through it later finds none, except
//!   with `--reverse`, which prints only at the end.
//! - **`--show-pulls`** lists a merge TREESAME to a later relevant parent
//!   and not to a relevant first one.
//! - **`--remove-empty`**: a commit that differs from a parent holding
//!   nothing the pathspec matches, while it holds something, makes that
//!   parent a root.
//! - **`--simplify-merges`** sorts as `--topo-order` does, replacing each
//!   commit by its only parent when, with its parents replaced in turn,
//!   duplicates gone, TREESAME roots dropped (unless the commit is
//!   TREESAME and they are all it is TREESAME to) and parents that real
//!   ancestry says are ancestors of others dropped (never all it is
//!   TREESAME to), it has one and is TREESAME to it.
//! - The sorts, `--children` and the parent counts use the parents
//!   simplification left; `--boundary` the rewritten ones.
//! - Before comparing a commit with its first parent, or a root with the
//!   empty tree, the commit's
//!   changed-path Bloom filter is asked when the pathspec has neither
//!   wildcards nor `icase` nor `exclude`: each item is ruled out when the
//!   filter lacks the key of its path or of a leading directory, and the
//!   comparison is skipped when every item is.

const std = @import("std");
const Allocator = std.mem.Allocator;

const Commits = @import("Commits.zig");
const Index = Commits.Index;
const Diagnostics = @import("Diagnostics.zig");
const Pathspec = @import("Pathspec.zig");
const TreeDiff = @import("TreeDiff.zig");
const bloom = @import("bloom.zig");
const object = @import("object.zig");

const RevWalk = @This();

gpa: Allocator,
store: *Commits,
options: Options,
starts: std.ArrayList(Start) = .empty,
flags: std.ArrayList(u8) = .empty,
queue: std.ArrayList(Queued) = .empty,
sequence: u64 = 0,
/// For each commit, the commits naming it as a parent, when `children`
/// is asked for.
child_lists: std.AutoHashMapUnmanaged(Index, std.ArrayList(Index)) = .empty,
/// What `next` hands out, when it has been worked out whole.
output: std.ArrayList(Entry) = .empty,
/// The commits `--ancestry-path` took out of the list that are not
/// excluded, which `--simplify-merges` passes over as parents.
off_path: std.AutoHashMapUnmanaged(Index, void) = .empty,
output_at: usize = 0,
/// How the walk is going.
state: enum { new, streaming, listed, done } = .new,
shown: u64 = 0,
skipped: u64 = 0,
/// The commit whose parent could not be read, when reading one failed.
failed_child: ?Index = null,
/// What history simplification knows of each commit, by commit number.
sim: std.ArrayList(SimState) = .empty,
/// The parent lists `sim` points into.
pool: std.ArrayList(Index) = .empty,
/// Comparing trees, made when first needed.
diff: ?TreeDiff = null,
/// The pathspec's changed-path Bloom filter keys, by hash version, made
/// when first needed.
bloom_keys: [2]?[]bloom.Key = .{ null, null },
/// How many keys each pathspec item has, in order.
bloom_key_counts: []u32 = &.{},
/// How often the changed-path Bloom filters were asked, and what they
/// said.
bloom_statistics: BloomStatistics = .{},
/// What the generation walk counted, as git's trace2 `topo_walk`
/// statistics count it; null when the walk was not by generation number.
topo_statistics: ?TopoStatistics = null,
/// Each commit's source, by commit number; `no_source` for none.
sources: std.ArrayList(u32) = .empty,

const no_source = std.math.maxInt(u32);

const seen_flag: u8 = 1;
const excluded_flag: u8 = 2;
const left_flag: u8 = 4;
const right_flag: u8 = 8;
/// Queued for the generation walk's exploring.
const explored_flag: u8 = 16;
const shown_flag: u8 = 32;
/// An excluded starting point, which git counts as a relevant parent.
const bottom_flag: u8 = 64;
/// Processed: simplified and its parents queued.
const added_flag: u8 = 128;

/// How the commits are ordered.
pub const Order = enum {
    /// By commit date, as they come out of the queue.
    default,
    /// `--date-order`.
    date,
    /// `--author-date-order`.
    author_date,
    /// `--topo-order`.
    topo,
};

/// Which side of a symmetric difference a commit is reachable from.
pub const Side = enum { none, left, right };

/// What the walk lists, besides its starting points.
pub const Options = struct {
    order: Order = .default,
    reverse: bool = false,
    /// `--max-count`.
    max_count: ?u64 = null,
    /// `--skip`.
    skip: u64 = 0,
    /// `--min-parents`.
    min_parents: u32 = 0,
    /// `--max-parents`; null for no limit.
    max_parents: ?u32 = null,
    /// `--first-parent`: included commits' first parents only.
    first_parent: bool = false,
    /// `--ancestry-path`: only commits descended from the excluded
    /// starting points, or related to `ancestry_commits`.
    ancestry_path: bool = false,
    /// `--ancestry-path=<commit>`: commits that are these, their
    /// ancestors or their descendants.
    ancestry_commits: []const Index = &.{},
    /// `--since`: commits older than this stop the walk.
    since: ?i64 = null,
    /// `--until`: commits newer than this are not listed.
    until: ?i64 = null,
    /// `--since-as-filter`: commits older than this are not listed.
    since_filter: ?i64 = null,
    /// `--boundary`.
    boundary: bool = false,
    /// `--left-only`.
    left_only: bool = false,
    /// `--right-only`.
    right_only: bool = false,
    /// `--children`: keep each commit's children.
    children: bool = false,
    /// Path limiting and history simplification; null for neither.
    simplify: ?Simplify = null,
    /// Whether to list each commit that the rest would list, as
    /// `--grep`, `--author` and `--committer` decide; after every other
    /// filter, and before `--skip` and `--max-count` count it.
    filter: ?Filter = null,
};

/// A question asked of each commit about to be listed.
pub const Filter = struct {
    context: *anyopaque,
    /// Whether to list `commit`. On `FilterFailed` the filter keeps what
    /// went wrong itself.
    keep: *const fn (context: *anyopaque, commit: Index) error{FilterFailed}!bool,
};

/// How a walk limited to paths is simplified, as git-rev-list(1)'s
/// "History Simplification" describes and the top of this file adds to.
pub const Simplify = struct {
    /// The paths; a walk with an empty pathspec is not limited, and its
    /// other settings change nothing but the order `simplify_merges`
    /// implies.
    pathspec: *const Pathspec,
    /// `--full-history`: follow every parent of a merge.
    full_history: bool = false,
    /// `--sparse`: list every commit walked, TREESAME or not.
    sparse: bool = false,
    /// `--simplify-merges`.
    simplify_merges: bool = false,
    /// `--show-pulls`.
    show_pulls: bool = false,
    /// `--remove-empty`.
    remove_empty: bool = false,
    /// `--parents` or `--children`: rewrite each listed commit's parents
    /// to the nearest listed ancestors.
    rewrite_parents: bool = false,
    /// Whether changed-path Bloom filters may be asked before comparing
    /// trees. Answers are the same either way.
    bloom: bool = true,
    /// `--simplify-by-decoration`: a commit with decorations differs
    /// from its parents whatever its tree, and without paths one without
    /// them is TREESAME, as git-rev-list(1) says.
    decorated: ?Decorated = null,
};

/// Whether a commit has decorations, for `--simplify-by-decoration`.
pub const Decorated = struct {
    context: *const anyopaque,
    has: *const fn (context: *const anyopaque, commit: Index) bool,
};

/// What the changed-path Bloom filters were asked and answered, counted
/// as git's trace2 `bloom` statistics count them.
pub const BloomStatistics = struct {
    /// Comparisons where the commit had no filter to ask.
    not_present: u64 = 0,
    /// Comparisons the filter could not rule out.
    maybe: u64 = 0,
    /// Comparisons the filter ruled out, so that no trees were read.
    definitely_not: u64 = 0,
    /// Comparisons the filter could not rule out and the trees showed
    /// nothing had changed.
    false_positive: u64 = 0,
};

/// How many commits each of the generation walk's three walks took.
pub const TopoStatistics = struct {
    explored: u64,
    counted: u64,
    walked: u64,
};

const SimState = struct {
    simplified: bool = false,
    treesame: bool = false,
    pull: bool = false,
    cleared: bool = false,
    freed: bool = false,
    rewritten: bool = false,
    /// Kept whole by `--simplify-merges`, rather than replaced.
    remains: bool = true,
    relevant_count: u32 = 0,
    parents: Span = .{},
    relevant: Span = .{},
    /// The parents compared, when all were, and in `same` whether each
    /// was TREESAME, for deciding again once the walk knows which
    /// parents are excluded.
    compared: Span = .{},
    same: Span = .{},
    rewritten_parents: Span = .{},
    /// What `--simplify-merges` replaces the commit with.
    replacement: Index = 0,
    replaced: bool = false,
};

const Span = struct { at: u32 = 0, len: u32 = 0 };

/// A starting point.
pub const Start = struct {
    commit: Index,
    /// Whether what it reaches is excluded, as `^<rev>` says.
    excluded: bool = false,
    /// The side of a symmetric difference it is.
    side: Side = .none,
    /// What `--source` and `%S` say the commits it reaches first were
    /// reached from: a number of the caller's, such as the position of
    /// the name it was given by.
    source: ?u32 = null,
};

/// One commit listed.
pub const Entry = struct {
    commit: Index,
    /// Whether it is a boundary commit.
    boundary: bool = false,
    /// The side of a symmetric difference it was reached from.
    side: Side = .none,
};

/// What walking can fail with: reading a commit failed, and when a parent
/// could not be read, `failed_child` names the commit that named it; or
/// `UnsupportedGraphOrdering`: an ordering with `--first-parent`,
/// `--since`, `--until` or `--since-as-filter` together with
/// `--children`, `--left-only`, `--right-only`, `--ancestry-path`,
/// `--simplify-merges` or `--simplify-by-decoration`, in a repository with a
/// commit-graph, where git's list was not matched; or
/// `UnsupportedAuthorDateOrdering`: `--author-date-order` walked by
/// generation number, when a commit is queued before git has read its
/// author date, which git then orders as if it had none, not matched.
///
/// With paths, comparing trees can fail with `TreeDiff.Error`; and
/// `UnsupportedParentRewrite` is rewritten parents with paths and
/// `--first-parent`, or `--full-history` with `--reverse` or `--skip`, in
/// a walk without exclusions or an ordering, where git rewrites some
/// parents in ways not matched and, with `--first-parent`, stops walking
/// part-way.
pub const Error = Commits.Error || TreeDiff.Error || error{ UnsupportedGraphOrdering, UnsupportedAuthorDateOrdering, UnsupportedParentRewrite, FilterFailed };

const Queued = struct { time: i64, sequence: u64, commit: Index };

/// A walk over the commits of `store`, which must outlive it.
pub fn init(gpa: Allocator, store: *Commits, options: Options) RevWalk {
    return .{ .gpa = gpa, .store = store, .options = options };
}

/// Frees everything.
pub fn deinit(w: *RevWalk) void {
    w.sources.deinit(w.gpa);
    w.sim.deinit(w.gpa);
    w.pool.deinit(w.gpa);
    if (w.diff) |*d| d.deinit();
    for (w.bloom_keys) |k| if (k) |keys| w.gpa.free(keys);
    w.gpa.free(w.bloom_key_counts);
    w.starts.deinit(w.gpa);
    w.flags.deinit(w.gpa);
    w.queue.deinit(w.gpa);
    var it = w.child_lists.valueIterator();
    while (it.next()) |l| l.deinit(w.gpa);
    w.child_lists.deinit(w.gpa);
    w.output.deinit(w.gpa);
    w.off_path.deinit(w.gpa);
    w.* = undefined;
}

/// Adds a starting point, before the first `next`.
pub fn addStart(w: *RevWalk, start: Start) Allocator.Error!void {
    try w.starts.append(w.gpa, start);
}

/// The children of `commit` among the commits walked, when `children` was
/// asked for.
pub fn childrenOf(w: *const RevWalk, commit: Index) []const Index {
    const l = w.child_lists.getPtr(commit) orelse return &.{};
    return l.items;
}

/// What `commit` was reached from, as `--source` shows it: the source of
/// the starting point it was first reached from, each commit taking the
/// source of the first commit seen to name it as a parent.
pub fn sourceOf(w: *const RevWalk, commit: Index) ?u32 {
    if (commit >= w.sources.items.len) return null;
    const v = w.sources.items[commit];
    return if (v == no_source) null else v;
}

fn giveSource(w: *RevWalk, c: Index, source: ?u32) Allocator.Error!void {
    const v = source orelse return;
    const n = w.store.count();
    if (w.sources.items.len < n) try w.sources.appendNTimes(w.gpa, no_source, n - w.sources.items.len);
    if (w.sources.items[c] == no_source) w.sources.items[c] = v;
}

/// Whether `commit` was reached from the left side of a symmetric
/// difference.
pub fn isLeft(w: *RevWalk, commit: Index) bool {
    return w.flag(commit) & left_flag != 0;
}

// -- flags and the queue -----------------------------------------------------------

fn ensure(w: *RevWalk) Allocator.Error!void {
    const n = w.store.count();
    if (w.flags.items.len < n) try w.flags.appendNTimes(w.gpa, 0, n - w.flags.items.len);
}

fn flag(w: *const RevWalk, c: Index) u8 {
    if (c >= w.flags.items.len) return 0;
    return w.flags.items[c];
}

fn set(w: *RevWalk, c: Index, f: u8) Allocator.Error!void {
    try w.ensure();
    w.flags.items[c] |= f;
}

fn excluded(w: *const RevWalk, c: Index) bool {
    return w.flag(c) & excluded_flag != 0;
}

fn sideOf(w: *RevWalk, c: Index) Side {
    const f = w.flag(c);
    if (f & left_flag != 0) return .left;
    if (f & right_flag != 0) return .right;
    return .none;
}

fn newer(a: Queued, b: Queued) bool {
    if (a.time != b.time) return a.time > b.time;
    return a.sequence < b.sequence;
}

fn push(w: *RevWalk, c: Index) Allocator.Error!void {
    const q: Queued = .{ .time = w.store.time(c), .sequence = w.sequence, .commit = c };
    w.sequence += 1;
    try w.queue.append(w.gpa, q);
    var i = w.queue.items.len - 1;
    while (i > 0) {
        const parent = (i - 1) / 2;
        if (!newer(w.queue.items[i], w.queue.items[parent])) break;
        std.mem.swap(Queued, &w.queue.items[i], &w.queue.items[parent]);
        i = parent;
    }
}

fn pop(w: *RevWalk) ?Index {
    const items = w.queue.items;
    if (items.len == 0) return null;
    const top = items[0].commit;
    items[0] = items[items.len - 1];
    w.queue.items.len -= 1;
    var i: usize = 0;
    const n = w.queue.items.len;
    while (true) {
        const l = 2 * i + 1;
        if (l >= n) break;
        var best = l;
        if (l + 1 < n and newer(w.queue.items[l + 1], w.queue.items[l])) best = l + 1;
        if (!newer(w.queue.items[best], w.queue.items[i])) break;
        std.mem.swap(Queued, &w.queue.items[i], &w.queue.items[best]);
        i = best;
    }
    return top;
}

fn newestQueued(w: *const RevWalk) ?i64 {
    if (w.queue.items.len == 0) return null;
    return w.queue.items[0].time;
}

fn everyQueuedExcluded(w: *RevWalk) bool {
    for (w.queue.items) |q| if (!w.excluded(q.commit)) return false;
    return true;
}

// -- walking -------------------------------------------------------------------

fn loadParent(w: *RevWalk, child: Index, p: Index, diag: ?*Diagnostics) Error!void {
    w.store.load(p, diag) catch |err| {
        w.failed_child = child;
        return err;
    };
}

/// Excludes everything `c`'s parents reach among the commits read.
fn excludeParents(w: *RevWalk, c: Index) Allocator.Error!void {
    var stack: std.ArrayList(Index) = .empty;
    defer stack.deinit(w.gpa);
    try stack.append(w.gpa, c);
    while (stack.pop()) |x| {
        // The parents simplification left, as git has replaced them.
        for (w.heldParents(x)) |p| {
            if (w.excluded(p)) continue;
            try w.set(p, excluded_flag);
            if (w.store.isLoaded(p)) try stack.append(w.gpa, p);
        }
    }
}

/// A commit's parents as git holds them: what simplification left once it
/// has been simplified (the parents past the first included with
/// `--first-parent` unless it is TREESAME to the first), all of them
/// otherwise. Excluding goes through these, so that a commit simplified
/// before it was excluded passes the exclusion only to the parents it
/// kept.
fn heldParents(w: *const RevWalk, c: Index) []const Index {
    if (w.pruning()) return w.simplifiedParents(c);
    return w.store.parents(c);
}

/// Takes a commit out of the queue's hands: its parents read, excluded if
/// it is, given its sides, simplified, and queued. A commit is processed
/// once, which may be before it comes out of the queue when its parents
/// are rewritten.
fn process(w: *RevWalk, c: Index, diag: ?*Diagnostics) Error!void {
    if (w.flag(c) & added_flag != 0) return;
    try w.set(c, added_flag);
    if (w.pruning()) try w.simplifyCommit(c, diag);
    const is_excluded = w.excluded(c);
    const sides = w.flag(c) & (left_flag | right_flag);
    const n = if (is_excluded) w.store.parents(c).len else w.walkParents(c).len;
    var i: usize = 0;
    while (i < n) : (i += 1) {
        // Reading a parent may move the parent pools.
        const p = if (is_excluded) w.store.parents(c)[i] else w.walkParents(c)[i];
        if (is_excluded) try w.set(p, excluded_flag);
        try w.loadParent(c, p, diag);
        if (is_excluded) try w.excludeParents(p);
        if (sides != 0) try w.set(p, sides);
        try w.giveSource(p, w.sourceOf(c));
        if (w.flag(p) & seen_flag == 0) {
            try w.set(p, seen_flag);
            try w.push(p);
        }
    }
}

// -- history simplification ------------------------------------------------------

fn pruning(w: *const RevWalk) bool {
    const s = w.options.simplify orelse return false;
    return s.pathspec.items.len != 0 or s.decorated != null;
}

/// Whether listed commits' parents are rewritten.
fn rewriting(w: *const RevWalk) bool {
    const s = w.options.simplify orelse return false;
    return w.pruning() and !s.sparse and (s.rewrite_parents or s.simplify_merges);
}

fn simState(w: *RevWalk, c: Index) Allocator.Error!*SimState {
    const n = w.store.count();
    if (w.sim.items.len < n) try w.sim.appendNTimes(w.gpa, .{}, n - w.sim.items.len);
    return &w.sim.items[c];
}

fn peekState(w: *const RevWalk, c: Index) SimState {
    if (c >= w.sim.items.len) return .{};
    return w.sim.items[c];
}

fn span(w: *const RevWalk, sp: Span) []const Index {
    return w.pool.items[sp.at..][0..sp.len];
}

fn storeSpan(w: *RevWalk, items: []const Index) Allocator.Error!Span {
    const at: u32 = @intCast(w.pool.items.len);
    try w.pool.appendSlice(w.gpa, items);
    return .{ .at = at, .len = @intCast(items.len) };
}

/// A commit's parents as simplification left them: all of them before it
/// is simplified, or without paths.
fn simplifiedParents(w: *const RevWalk, c: Index) []const Index {
    const st = w.peekState(c);
    if (!st.simplified) return w.store.parents(c);
    return w.span(st.parents);
}

/// The parents the walk follows from an included commit.
fn walkParents(w: *const RevWalk, c: Index) []const Index {
    const ps = if (w.pruning()) w.simplifiedParents(c) else w.store.parents(c);
    if (w.options.first_parent and ps.len > 1) return ps[0..1];
    return ps;
}

fn isBottom(w: *const RevWalk, c: Index) bool {
    return w.flag(c) & bottom_flag != 0;
}

/// Whether a parent counts in deciding TREESAME: included, or an
/// excluded starting point.
fn relevant(w: *const RevWalk, p: Index) bool {
    return !w.excluded(p) or w.isBottom(p);
}

fn treeDiff(w: *RevWalk) *TreeDiff {
    if (w.diff == null) w.diff = TreeDiff.init(w.gpa, w.store.io, w.store.db, w.store.format, w.options.simplify.?.pathspec);
    return &w.diff.?;
}

/// Whether anything the pathspec matches differs between the trees of
/// `parent` (or the empty tree) and `c`.
fn differs(w: *RevWalk, parent: ?Index, c: Index, diag: ?*Diagnostics) Error!bool {
    const s = w.options.simplify.?;
    if (s.decorated) |d| {
        if (d.has(d.context, c)) return true;
        // A root is compared with the empty tree, the whole tree matching.
        if (s.pathspec.items.len == 0 and parent != null) return false;
    }
    const old = if (parent) |p| w.store.tree(p) else null;
    return w.treeDiff().differs(old, w.store.tree(c), diag);
}

/// Whether `c`'s tree holds nothing the pathspec matches.
fn isEmpty(w: *RevWalk, c: Index, diag: ?*Diagnostics) Error!bool {
    return !try w.differs(null, c, diag);
}

/// `differs` for a commit and its first parent, asking the commit's
/// changed-path Bloom filter first when it has one.
fn differsFromFirst(w: *RevWalk, p: Index, c: Index, diag: ?*Diagnostics) Error!bool {
    return w.differsWithFilter(p, c, diag);
}

fn differsWithFilter(w: *RevWalk, p: ?Index, c: Index, diag: ?*Diagnostics) Error!bool {
    const s = w.options.simplify.?;
    if (s.bloom and s.decorated == null and w.store.graph.layers.len != 0) {
        if (w.bloomSays(c)) |may| {
            if (!may) {
                w.bloom_statistics.definitely_not += 1;
                return false;
            }
            w.bloom_statistics.maybe += 1;
            const d = try w.differs(p, c, diag);
            if (!d) w.bloom_statistics.false_positive += 1;
            return d;
        }
    }
    return w.differs(p, c, diag);
}

/// What `c`'s filter says of the pathspec: false if no item can have
/// changed, true if one may have, and null if git would not ask it.
fn bloomSays(w: *RevWalk, c: Index) ?bool {
    const ps = w.options.simplify.?.pathspec;
    if (!ps.bloomKeys()) return null;
    const pos = w.store.graph.find(w.store.id(c)) orelse return null;
    const f = w.store.graph.bloomFilter(pos);
    const settings = f.settings orelse {
        w.bloom_statistics.not_present += 1;
        return null;
    };
    const bytes = switch (f.filter) {
        .bytes => |b| b,
        else => {
            w.bloom_statistics.not_present += 1;
            return null;
        },
    };
    if (bytes.len == 0) {
        w.bloom_statistics.not_present += 1;
        return null;
    }
    const keys = w.keysFor(settings.version) catch return null;
    var at: usize = 0;
    for (w.bloom_key_counts) |n| {
        const item = keys[at..][0..n];
        at += n;
        const all = for (item) |k| {
            if (!bloom.mayContain(bytes, settings.hashes, k)) break false;
        } else true;
        if (all) return true;
    }
    return false;
}

/// The keys of every pathspec item's path and its leading directories.
fn keysFor(w: *RevWalk, version: bloom.Version) Allocator.Error![]const bloom.Key {
    const slot: usize = if (version == .v1) 0 else 1;
    if (w.bloom_keys[slot]) |k| return k;
    const ps = w.options.simplify.?.pathspec;
    var keys: std.ArrayList(bloom.Key) = .empty;
    errdefer keys.deinit(w.gpa);
    var counts: std.ArrayList(u32) = .empty;
    errdefer counts.deinit(w.gpa);
    for (ps.items) |it| {
        const path = std.mem.trimEnd(u8, it.pattern, "/");
        var n: u32 = 0;
        var end = path.len;
        while (true) {
            if (end != 0) {
                try keys.append(w.gpa, .init(version, path[0..end]));
                n += 1;
            }
            end = std.mem.findScalarLast(u8, path[0..end], '/') orelse break;
        }
        try counts.append(w.gpa, n);
    }
    const owned = try keys.toOwnedSlice(w.gpa);
    w.bloom_keys[slot] = owned;
    if (w.bloom_key_counts.len == 0) {
        w.bloom_key_counts = try counts.toOwnedSlice(w.gpa);
    } else counts.deinit(w.gpa);
    return owned;
}

/// Decides whether `c` is TREESAME, and which of its parents the walk
/// follows, as the top of this file describes.
fn simplifyCommit(w: *RevWalk, c: Index, diag: ?*Diagnostics) Error!void {
    if ((try w.simState(c)).simplified) return;
    const s = w.options.simplify.?;
    var real_list: std.ArrayList(Index) = .empty;
    defer real_list.deinit(w.gpa);
    try real_list.appendSlice(w.gpa, w.store.parents(c));
    const real = real_list.items;
    var parents: std.ArrayList(Index) = .empty;
    defer parents.deinit(w.gpa);
    if (!(try w.simState(c)).cleared) try parents.appendSlice(w.gpa, real);
    const excluded_commit = w.excluded(c);
    if (!excluded_commit and w.options.first_parent and parents.items.len > 1) parents.shrinkRetainingCapacity(1);
    var chosen: std.ArrayList(Index) = .empty;
    defer chosen.deinit(w.gpa);
    var treesame = false;
    var pull = false;
    var relevant_list: std.ArrayList(Index) = .empty;
    defer relevant_list.deinit(w.gpa);
    var same_bits: std.ArrayList(Index) = .empty;
    defer same_bits.deinit(w.gpa);
    var compared = false;
    // Whether the commit was found TREESAME to the one parent it follows,
    // which then is its only parent.
    var followed_one = false;
    decide: {
        if (excluded_commit) {
            try chosen.appendSlice(w.gpa, parents.items);
            break :decide;
        }
        if (parents.items.len == 0) {
            // A root's filter is of what it adds to the empty tree, and
            // git asks it too.
            treesame = !try w.differsWithFilter(null, c, diag);
            break :decide;
        }
        // Relevance is counted over every parent, even with --first-parent,
        // where only the first is compared.
        const single = real.len == 1;
        if (s.sparse and real.len == 1 and parents.items.len == 1) {
            try chosen.appendSlice(w.gpa, parents.items);
            break :decide;
        }
        for (real) |p| if (single or w.relevant(p)) try relevant_list.append(w.gpa, p);
        const has_relevant = relevant_list.items.len != 0;
        var all_relevant_same = true;
        var all_same = true;
        var first_same: ?bool = null;
        var later_same = false;
        for (parents.items, 0..) |p, i| {
            try w.loadParent(c, p, diag);
            const d = if (i == 0 and real.len != 0 and p == real[0])
                try w.differsFromFirst(p, c, diag)
            else
                try w.differs(p, c, diag);
            const is_relevant = single or w.relevant(p);
            if (!d and !s.full_history and is_relevant) {
                chosen.clearRetainingCapacity();
                try chosen.append(w.gpa, p);
                treesame = true;
                if (s.show_pulls and i > 0 and first_same == false) pull = true;
                relevant_list.clearRetainingCapacity();
                try relevant_list.append(w.gpa, p);
                followed_one = true;
                break :decide;
            }
            if (d and s.remove_empty and try w.isEmpty(p, diag) and !try w.isEmpty(c, diag)) {
                // The commit adds every path from nothing: git takes the
                // parent to be a root.
                const ps = try w.simState(p);
                ps.cleared = true;
                if (ps.simplified) ps.parents = .{};
            }
            // An irrelevant parent is never marked TREESAME, so a merge
            // TREESAME to one is not counted as pulling from it.
            if (i == 0) first_same = !d and is_relevant else if (!d and is_relevant) later_same = true;
            if (is_relevant and d) all_relevant_same = false;
            if (d) all_same = false;
            try same_bits.append(w.gpa, @intFromBool(!d));
        }
        compared = true;
        try chosen.appendSlice(w.gpa, parents.items);
        if (s.show_pulls and parents.items.len > 1 and first_same == false and later_same) pull = true;
        // A merge whose compared parents are all irrelevant, while it has
        // relevant ones, is TREESAME to all it compared: none.
        treesame = if (has_relevant) all_relevant_same else all_same;
    }
    // With --first-parent the other parents stay as they are, unless the
    // commit is TREESAME to its first.
    if (w.options.first_parent and real.len > 1 and !excluded_commit and !followed_one and !(try w.simState(c)).cleared) {
        try chosen.appendSlice(w.gpa, real[1..]);
    }
    const parents_span = try w.storeSpan(chosen.items);
    const relevant_span = try w.storeSpan(relevant_list.items);
    const compared_span: Span = if (compared) try w.storeSpan(parents.items) else .{};
    const same_span: Span = if (compared) try w.storeSpan(same_bits.items) else .{};
    const st = try w.simState(c);
    st.compared = compared_span;
    st.same = same_span;
    st.simplified = true;
    st.treesame = treesame;
    st.pull = pull;
    st.parents = parents_span;
    st.relevant = relevant_span;
    st.relevant_count = relevant_span.len;
}

/// Decides TREESAME again for the commits `list` holds, now that the
/// walk knows which commits are excluded: git counts only the parents
/// still relevant, and keeps what it had decided when none is. Which
/// parents the walk followed does not change.
fn reconsider(w: *RevWalk, list: []const Index) Allocator.Error!void {
    var rel: std.ArrayList(Index) = .empty;
    defer rel.deinit(w.gpa);
    for (list) |c| {
        if (w.excluded(c)) continue;
        const st = w.peekState(c);
        if (!st.simplified or st.compared.len == 0) continue;
        const real = w.store.parents(c);
        const single = real.len == 1;
        rel.clearRetainingCapacity();
        for (real) |p| if (single or w.relevant(p)) try rel.append(w.gpa, p);
        var all_same = true;
        for (w.span(st.compared), w.span(st.same)) |p, same| {
            if ((single or w.relevant(p)) and same == 0) all_same = false;
        }
        const sp = try w.storeSpan(rel.items);
        const s2 = try w.simState(c);
        if (rel.items.len != 0) s2.treesame = all_same;
        s2.relevant = sp;
        s2.relevant_count = sp.len;
    }
}

/// How many of a commit's parents are relevant now; a single parent
/// always is.
fn relevantNow(w: *const RevWalk, c: Index) usize {
    const real = w.store.parents(c);
    if (real.len == 1) return 1;
    var n: usize = 0;
    for (real) |p| {
        if (w.relevant(p)) n += 1;
    }
    return n;
}

/// Whether a commit the walk reached is listed, as far as simplification
/// is concerned.
fn shownBySimplification(w: *const RevWalk, c: Index) bool {
    if (!w.pruning()) return true;
    const s = w.options.simplify.?;
    const st = w.peekState(c);
    if (s.simplify_merges and !s.sparse and !st.remains) return false;
    if (!st.treesame or st.pull) return true;
    if (s.sparse) return true;
    // Counted as the commit is listed: in a walk by generation number,
    // the exclusions known by then.
    if (w.rewriting() and s.full_history and w.relevantNow(c) > 1) return true;
    return false;
}

/// The parents of listed commit `c` rewritten to the nearest commits that
/// are listed or excluded, as `--parents` shows them, every parent even
/// with `--first-parent`. Reading ahead may
/// process commits before they come out of the queue, as git does.
fn rewriteParents(w: *RevWalk, c: Index, diag: ?*Diagnostics) Error!void {
    if ((try w.simState(c)).rewritten) return;
    var out: std.ArrayList(Index) = .empty;
    defer out.deinit(w.gpa);
    const s = w.options.simplify.?;
    if (s.simplify_merges) {
        try out.appendSlice(w.gpa, w.simplifiedParents(c));
    } else {
        // Every parent is rewritten, even with `--first-parent`.
        const n = w.simplifiedParents(c).len;
        var i: usize = 0;
        while (i < n) : (i += 1) {
            var p = w.simplifiedParents(c)[i];
            while (true) {
                try w.loadParent(c, p, diag);
                try w.process(p, diag);
                const ps = w.peekState(p);
                if (w.excluded(p) or !ps.treesame or ps.pull) {
                    try out.append(w.gpa, p);
                    break;
                }
                var q = if (ps.freed) &[_]Index{} else w.simplifiedParents(p);
                if (w.options.first_parent and q.len > 1) q = q[0..1];
                if (q.len > 1) {
                    const rel = w.span(ps.relevant);
                    if (rel.len == 1) {
                        p = rel[0];
                        continue;
                    }
                    try out.append(w.gpa, p);
                    break;
                }
                if (q.len == 0) break;
                p = q[0];
            }
        }
    }
    var kept: usize = 0;
    for (out.items, 0..) |p, i| {
        if (std.mem.findScalar(Index, out.items[0..i], p) != null) continue;
        out.items[kept] = p;
        kept += 1;
    }
    const sp = try w.storeSpan(out.items[0..kept]);
    const st = try w.simState(c);
    st.rewritten = true;
    st.rewritten_parents = sp;
}

/// git lets go of a commit's parents once it has printed it, which with
/// `--reverse` is only after the walk; walking through it later finds
/// none.
fn printed(w: *RevWalk, c: Index) Allocator.Error!void {
    if (!w.rewriting() or w.options.reverse) return;
    (try w.simState(c)).freed = true;
}

/// The parents `--parents` shows for a listed or boundary commit.
pub fn parentsOf(w: *const RevWalk, e: Entry) []const Index {
    if (!w.pruning()) return w.store.parents(e.commit);
    const st = w.peekState(e.commit);
    if (st.rewritten) return w.span(st.rewritten_parents);
    return w.simplifiedParents(e.commit);
}

/// `--simplify-merges`, over the walk's included commits in `list`: each
/// commit replaced by its only parent when, its parents simplified in
/// turn, it has one and is TREESAME to it.
fn simplifyMerges(w: *RevWalk, list: []const Index) Error!void {
    var in_list: std.AutoHashMapUnmanaged(Index, void) = .empty;
    defer in_list.deinit(w.gpa);
    for (list) |c| if (!w.excluded(c)) try in_list.put(w.gpa, c, {});
    var stack: std.ArrayList(Index) = .empty;
    defer stack.deinit(w.gpa);
    var reach: std.AutoHashMapUnmanaged(Index, std.AutoHashMapUnmanaged(Index, void)) = .empty;
    defer {
        var it = reach.valueIterator();
        while (it.next()) |v| v.deinit(w.gpa);
        reach.deinit(w.gpa);
    }
    for (list) |top| {
        if (!in_list.contains(top)) continue;
        try stack.append(w.gpa, top);
        while (stack.items.len != 0) {
            const x = stack.items[stack.items.len - 1];
            if ((try w.simState(x)).replaced) {
                _ = stack.pop();
                continue;
            }
            var pending = false;
            const ps = w.simplifiedParents(x);
            var i = ps.len;
            while (i > 0) {
                i -= 1;
                const p = ps[i];
                if (in_list.contains(p) and !w.peekState(p).replaced) {
                    try stack.append(w.gpa, p);
                    pending = true;
                }
            }
            if (pending) continue;
            try w.simplifyOneMerge(x, &in_list, &reach);
            _ = stack.pop();
        }
    }
}

fn replacementOf(w: *const RevWalk, c: Index, in_list: *const std.AutoHashMapUnmanaged(Index, void)) Index {
    if (!in_list.contains(c)) return c;
    return w.peekState(c).replacement;
}

fn simplifyOneMerge(
    w: *RevWalk,
    c: Index,
    in_list: *const std.AutoHashMapUnmanaged(Index, void),
    reach: *std.AutoHashMapUnmanaged(Index, std.AutoHashMapUnmanaged(Index, void)),
) Error!void {
    const Parent = struct { commit: Index, same: bool };
    var list: std.ArrayList(Parent) = .empty;
    defer list.deinit(w.gpa);
    const ps = w.simplifiedParents(c);
    const treesame_commit = w.peekState(c).treesame;
    for (ps) |p0| {
        const same = !try w.differs(p0, c, null);
        const p = w.replacementOf(p0, in_list);
        var dup = false;
        for (list.items) |*e| if (e.commit == p) {
            e.same = e.same or same;
            dup = true;
        };
        if (!dup) try list.append(w.gpa, .{ .commit = p, .same = same });
    }
    const st_treesame = w.peekState(c).treesame;
    // Roots TREESAME to the empty tree go, unless the commit is TREESAME
    // and they are all it is TREESAME to.
    var step1: std.ArrayList(Parent) = .empty;
    defer step1.deinit(w.gpa);
    for (list.items) |e| {
        const st = w.peekState(e.commit);
        const ts_root = in_list.contains(e.commit) and w.store.parents(e.commit).len == 0 and st.treesame;
        if (!ts_root) try step1.append(w.gpa, e);
    }
    try protect(w.gpa, list.items, &step1, st_treesame);
    // Parents that are ancestors of other parents go, but never all the
    // parents it is TREESAME to.
    var step2: std.ArrayList(Parent) = .empty;
    defer step2.deinit(w.gpa);
    for (step1.items) |e| {
        const is_ancestor = for (step1.items) |o| {
            if (o.commit != e.commit and try w.reaches(o.commit, e.commit, in_list, reach)) break true;
        } else false;
        if (!is_ancestor) try step2.append(w.gpa, e);
    }
    try protect(w.gpa, step1.items, &step2, true);
    // A commit TREESAME to its parents with one parent left on the
    // ancestry path is replaced by it, whatever parents it has off the
    // path; with more, it keeps those too.
    var on_path: ?Parent = null;
    var on_path_count: usize = 0;
    for (step2.items) |e| if (!w.off_path.contains(e.commit)) {
        on_path = e;
        on_path_count += 1;
    };
    if (treesame_commit and on_path_count == 1 and on_path_count != step2.items.len) {
        step2.clearRetainingCapacity();
        try step2.append(w.gpa, on_path.?);
    }
    const st = try w.simState(c);
    st.replaced = true;
    if (step2.items.len != 1 or !step2.items[0].same or st.pull) {
        st.replacement = c;
        st.remains = true;
        var commits: std.ArrayList(Index) = .empty;
        defer commits.deinit(w.gpa);
        for (step2.items) |e| try commits.append(w.gpa, e.commit);
        const sp = try w.storeSpan(commits.items);
        const st2 = try w.simState(c);
        st2.rewritten_parents = sp;
        st2.rewritten = true;
    } else {
        st.replacement = step2.items[0].commit;
        st.remains = false;
    }
}

/// Puts back the first parent of `before` the commit is TREESAME to, when
/// `after` has lost them all and `condition` holds.
fn protect(gpa: Allocator, before: anytype, after: anytype, condition: bool) Allocator.Error!void {
    if (!condition) return;
    var any_before = false;
    for (before) |e| any_before = any_before or e.same;
    if (!any_before) return;
    for (after.items) |e| if (e.same) return;
    const first = for (before) |e| {
        if (e.same) break e;
    } else unreachable;
    // Keep the order `before` had.
    var rebuilt: @TypeOf(after.*) = .empty;
    defer rebuilt.deinit(gpa);
    for (before) |e| {
        const kept = for (after.items) |a| {
            if (a.commit == e.commit) break true;
        } else false;
        if (kept or e.commit == first.commit) try rebuilt.append(gpa, e);
    }
    after.clearRetainingCapacity();
    try after.appendSlice(gpa, rebuilt.items);
}

/// Whether `ancestor` is reachable from `from` through real parents.
///
/// With `--ancestry-path` it is ancestry as simplification has left it:
/// through the parents each listed commit was simplified to, the real
/// parents of excluded commits, and none of a commit off the path, as
/// git was seen to reckon it.
fn reaches(
    w: *RevWalk,
    from: Index,
    ancestor: Index,
    in_list: *const std.AutoHashMapUnmanaged(Index, void),
    memo: *std.AutoHashMapUnmanaged(Index, std.AutoHashMapUnmanaged(Index, void)),
) Error!bool {
    const simplified = w.off_path.count() != 0;
    const gop = try memo.getOrPut(w.gpa, from);
    if (!gop.found_existing) {
        gop.value_ptr.* = .empty;
        var stack: std.ArrayList(Index) = .empty;
        defer stack.deinit(w.gpa);
        try stack.append(w.gpa, from);
        var one: [1]Index = undefined;
        while (stack.pop()) |x| {
            try w.store.load(x, null);
            const onward: []const Index = if (simplified and in_list.contains(x)) blk: {
                const st = w.peekState(x);
                if (!st.replaced) break :blk w.store.parents(x);
                if (st.remains) break :blk w.span(st.rewritten_parents);
                one[0] = st.replacement;
                break :blk &one;
            } else w.store.parents(x);
            // Reading a parent may move the parent pools; take a copy.
            var copy: std.ArrayList(Index) = .empty;
            defer copy.deinit(w.gpa);
            try copy.appendSlice(w.gpa, onward);
            for (copy.items) |p| {
                const set_ptr = memo.getPtr(from).?;
                if ((try set_ptr.getOrPut(w.gpa, p)).found_existing) continue;
                try stack.append(w.gpa, p);
            }
        }
    }
    return memo.getPtr(from).?.contains(ancestor);
}

fn setUp(w: *RevWalk, diag: ?*Diagnostics) Error!void {
    for (w.starts.items) |s| {
        try w.store.load(s.commit, diag);
        try w.ensure();
        if (s.excluded) try w.set(s.commit, excluded_flag | bottom_flag);
        try w.giveSource(s.commit, s.source);
        switch (s.side) {
            .left => try w.set(s.commit, left_flag),
            .right => try w.set(s.commit, right_flag),
            .none => {},
        }
        if (w.flag(s.commit) & seen_flag == 0) {
            try w.set(s.commit, seen_flag);
            try w.push(s.commit);
        }
    }
    for (w.starts.items) |s| if (s.excluded) try w.excludeParents(s.commit);
}

fn isLimited(w: *const RevWalk) bool {
    const o = w.options;
    if (o.order != .default or o.children or o.ancestry_path or o.ancestry_commits.len != 0) return true;
    if (o.simplify) |s| if (s.simplify_merges) return true;
    for (w.starts.items) |s| if (s.excluded) return true;
    return false;
}

/// Whether a commit that came out of the walk is listed.
fn keep(w: *RevWalk, c: Index) error{FilterFailed}!bool {
    if (!w.shownBySimplification(c)) return false;
    const o = w.options;
    // With paths, the parents counted are those simplification left.
    const n = if (w.pruning()) w.simplifiedParents(c).len else w.store.parents(c).len;
    if (n < o.min_parents) return false;
    if (o.max_parents) |m| if (n > m) return false;
    const t = w.store.time(c);
    if (o.until) |u| if (t > u) return false;
    if (o.since_filter) |s| if (t < s) return false;
    if (o.left_only and w.flag(c) & left_flag == 0) return false;
    if (o.right_only and w.flag(c) & left_flag != 0) return false;
    if (o.filter) |f| return f.keep(f.context, c);
    return true;
}

/// The stop rule's number: how many excluded commits in a row may come
/// out with nothing left that could still exclude what was listed.
const slop = 5;

/// Works out the list of a walk with exclusions, as the top of this file
/// describes.
fn limit(w: *RevWalk, list: *std.ArrayList(Index), diag: ?*Diagnostics) Error!void {
    var last: ?i64 = null;
    var budget: u32 = slop;
    // With an ordering and a commit-graph, git's list is exact: nothing an
    // excluded commit reaches is left in it, however the dates run. The
    // walk goes on until no queued commit could reach a listed one, which
    // the generation numbers tell: a commit reaches only commits of lower
    // generation, and one the graph does not list (whose generation is
    // infinite) may reach anything.
    // With `--children`, `--right-only` or `--simplify-merges` git walks
    // by date as it does without a graph (with `--left-only`,
    // `--left-right`, `--boundary`, `--parents` and the rest, it does
    // not), as it was seen to.
    const simplifying_merges = if (w.options.simplify) |s| s.simplify_merges else false;
    const exact = w.options.order != .default and w.store.graph.layers.len != 0 and
        !w.options.children and !w.options.right_only and !simplifying_merges;
    var lowest_listed: u64 = Commits.infinite_generation;
    while (w.pop()) |c| {
        if (w.options.since) |s| if (w.store.time(c) < s) try w.set(c, excluded_flag);
        try w.process(c, diag);
        if (w.excluded(c)) {
            if (exact) {
                if (w.queue.items.len == 0) break;
                if (!w.everyQueuedExcluded()) continue;
                const unreachable_from_queue = for (w.queue.items) |q| {
                    const g = w.store.generation(q.commit);
                    if (g == Commits.infinite_generation or g > lowest_listed) break false;
                } else true;
                if (unreachable_from_queue) break;
                continue;
            }
            const newest = w.newestQueued() orelse break;
            const listed_older = if (last) |l| l <= newest else false;
            if (listed_older) {
                budget = slop;
            } else if (!w.everyQueuedExcluded()) {
                budget = slop;
            } else {
                budget -= 1;
                if (budget == 0) break;
            }
            continue;
        }
        // `--until` and `--since-as-filter` keep a commit out of the list
        // itself, so that the sort never sees it and the stop rule does
        // not count it.
        if (w.options.until) |u| if (w.store.time(c) > u) continue;
        if (w.options.since_filter) |f| if (w.store.time(c) < f) continue;
        try list.append(w.gpa, c);
        last = w.store.time(c);
        lowest_listed = @min(lowest_listed, w.store.generation(c));
    }
}

/// Keeps the commits related to the ancestry path's commits.
fn limitToAncestry(w: *RevWalk, list: *std.ArrayList(Index)) Allocator.Error!void {
    const n = w.store.count();
    const related = try w.gpa.alloc(u8, n);
    defer w.gpa.free(related);
    @memset(related, 0);
    const descendant: u8 = 1;
    const ancestor: u8 = 2;
    var bottoms: std.ArrayList(Index) = .empty;
    defer bottoms.deinit(w.gpa);
    if (w.options.ancestry_commits.len != 0) {
        try bottoms.appendSlice(w.gpa, w.options.ancestry_commits);
    } else {
        for (w.starts.items) |s| if (s.excluded) try bottoms.append(w.gpa, s.commit);
    }
    for (bottoms.items) |b| related[b] |= descendant;
    // Descendants: the list runs from children to parents, so go round
    // until nothing changes.
    var changed = true;
    while (changed) {
        changed = false;
        for (list.items) |c| {
            if (related[c] & descendant != 0) continue;
            const ps = w.store.parents(c);
            const use = if (w.options.first_parent and ps.len > 1) ps[0..1] else ps;
            for (use) |p| if (related[p] & descendant != 0) {
                related[c] |= descendant;
                changed = true;
                break;
            };
        }
    }
    if (w.options.ancestry_commits.len != 0) {
        var stack: std.ArrayList(Index) = .empty;
        defer stack.deinit(w.gpa);
        try stack.appendSlice(w.gpa, bottoms.items);
        var in_list = try w.gpa.alloc(bool, n);
        defer w.gpa.free(in_list);
        @memset(in_list, false);
        for (list.items) |c| in_list[c] = true;
        while (stack.pop()) |x| {
            if (!w.store.isLoaded(x)) continue;
            for (w.store.parents(x)) |p| {
                if (!in_list[p] or related[p] & ancestor != 0) continue;
                related[p] |= ancestor;
                try stack.append(w.gpa, p);
            }
        }
    }
    var kept: usize = 0;
    for (list.items) |c| {
        if (related[c] != 0) {
            list.items[kept] = c;
            kept += 1;
        } else if (!w.excluded(c)) try w.off_path.put(w.gpa, c, {});
    }
    list.shrinkRetainingCapacity(kept);
}

/// Sorts `list` so that no commit comes before one naming it as a parent,
/// as `order` says; `known` says whose parents may be followed.
fn sortTopologically(w: *RevWalk, list: []Index, order: Order, known_only: bool) Error!void {
    if (list.len < 2) return;
    const gpa = w.gpa;
    var position: std.AutoHashMapUnmanaged(Index, u32) = .empty;
    defer position.deinit(gpa);
    var indegree = try gpa.alloc(u32, list.len);
    defer gpa.free(indegree);
    @memset(indegree, 0);
    for (list, 0..) |c, i| try position.put(gpa, c, @intCast(i));
    for (list) |c| {
        if (known_only and !w.store.isLoaded(c)) continue;
        for (w.sortParents(c)) |p| if (position.get(p)) |at| {
            indegree[at] += 1;
        };
    }
    const sorted = try gpa.alloc(Index, list.len);
    defer gpa.free(sorted);
    var out: usize = 0;
    switch (order) {
        .topo, .default => {
            var stack: std.ArrayList(Index) = .empty;
            defer stack.deinit(gpa);
            var i = list.len;
            while (i > 0) {
                i -= 1;
                if (indegree[i] == 0) try stack.append(gpa, list[i]);
            }
            while (stack.pop()) |c| {
                sorted[out] = c;
                out += 1;
                if (known_only and !w.store.isLoaded(c)) continue;
                for (w.sortParents(c)) |p| if (position.get(p)) |at| {
                    indegree[at] -= 1;
                    if (indegree[at] == 0) try stack.append(gpa, p);
                };
            }
        },
        .date, .author_date => {
            var heap: std.ArrayList(Queued) = .empty;
            defer heap.deinit(gpa);
            var seq: u64 = 0;
            for (list, 0..) |c, i| if (indegree[i] == 0) {
                try heapPush(gpa, &heap, .{ .time = try w.sortTime(c, order), .sequence = seq, .commit = c });
                seq += 1;
            };
            while (heapPop(&heap)) |c| {
                sorted[out] = c;
                out += 1;
                if (known_only and !w.store.isLoaded(c)) continue;
                for (w.sortParents(c)) |p| if (position.get(p)) |at| {
                    indegree[at] -= 1;
                    if (indegree[at] == 0) {
                        try heapPush(gpa, &heap, .{ .time = try w.sortTime(p, order), .sequence = seq, .commit = p });
                        seq += 1;
                    }
                };
            }
        },
    }
    @memcpy(list[0..out], sorted[0..out]);
}

/// The parents a sort follows: as simplification left them, every one.
fn sortParents(w: *const RevWalk, c: Index) []const Index {
    if (w.pruning()) return w.simplifiedParents(c);
    return w.store.parents(c);
}

fn sortTime(w: *RevWalk, c: Index, order: Order) Error!i64 {
    if (order == .author_date) return w.store.authorTime(c, null);
    return w.store.time(c);
}

fn heapPush(gpa: Allocator, heap: *std.ArrayList(Queued), q: Queued) Allocator.Error!void {
    try heap.append(gpa, q);
    var i = heap.items.len - 1;
    while (i > 0) {
        const parent = (i - 1) / 2;
        if (!newer(heap.items[i], heap.items[parent])) break;
        std.mem.swap(Queued, &heap.items[i], &heap.items[parent]);
        i = parent;
    }
}

fn heapPop(heap: *std.ArrayList(Queued)) ?Index {
    if (heap.items.len == 0) return null;
    const top = heap.items[0].commit;
    heap.items[0] = heap.items[heap.items.len - 1];
    heap.items.len -= 1;
    var i: usize = 0;
    const n = heap.items.len;
    while (true) {
        const l = 2 * i + 1;
        if (l >= n) break;
        var best = l;
        if (l + 1 < n and newer(heap.items[l + 1], heap.items[l])) best = l + 1;
        if (!newer(heap.items[best], heap.items[i])) break;
        std.mem.swap(Queued, &heap.items[i], &heap.items[best]);
        i = best;
    }
    return top;
}

fn recordChildren(w: *RevWalk, list: []const Index) Allocator.Error!void {
    for (list) |c| for (if (w.pruning()) w.walkParents(c) else w.store.parents(c)) |p| {
        const gop = try w.child_lists.getOrPut(w.gpa, p);
        if (!gop.found_existing) gop.value_ptr.* = .empty;
        try gop.value_ptr.insert(w.gpa, 0, c);
    };
}

/// Applies `--skip` and `--max-count` to a commit that passed the
/// filters: whether it is shown, and whether the walk is done.
fn admit(w: *RevWalk) enum { skip, show, stop } {
    if (w.options.max_count) |m| if (w.shown >= m) return .stop;
    if (w.skipped < w.options.skip) {
        w.skipped += 1;
        return .skip;
    }
    w.shown += 1;
    return .show;
}

/// Works out everything the walk lists, as a walk with exclusions, an
/// ordering, boundary commits or `--reverse` needs.
fn listAll(w: *RevWalk, diag: ?*Diagnostics) Error!void {
    var list: std.ArrayList(Index) = .empty;
    defer list.deinit(w.gpa);
    if (w.isLimited()) {
        try w.limit(&list, diag);
        if (w.pruning()) try w.reconsider(list.items);
        if (w.options.ancestry_path or w.options.ancestry_commits.len != 0) try w.limitToAncestry(&list);
        var order = w.options.order;
        if (w.options.simplify) |s| if (s.simplify_merges) {
            // --simplify-merges sorts as --topo-order does unless told
            // otherwise.
            if (w.pruning()) try w.simplifyMerges(list.items);
            if (order == .default) order = .topo;
        };
        if (order != .default) try w.sortTopologically(list.items, order, false);
        if (w.options.children) try w.recordChildren(list.items);
        var kept: usize = 0;
        for (list.items) |c| if (!w.excluded(c)) {
            list.items[kept] = c;
            kept += 1;
        };
        list.shrinkRetainingCapacity(kept);
        for (list.items) |c| {
            if (!try w.keep(c)) continue;
            switch (w.admit()) {
                .skip => continue,
                .stop => break,
                .show => {},
            }
            if (w.rewriting()) try w.rewriteParents(c, diag);
            try w.printed(c);
            try w.set(c, shown_flag);
            try w.output.append(w.gpa, .{ .commit = c, .side = w.sideOf(c) });
        }
    } else {
        while (try w.nextStreamed(diag)) |e| try w.output.append(w.gpa, e);
    }
    if (w.options.boundary) try w.addBoundary();
    if (w.options.reverse) std.mem.reverse(Entry, w.output.items);
}

/// The next commit of a walk without exclusions, taken from the queue as
/// it is wanted.
fn nextStreamed(w: *RevWalk, diag: ?*Diagnostics) Error!?Entry {
    if (w.options.max_count) |m| if (w.shown >= m) return null;
    while (w.pop()) |c| {
        if (w.options.since) |s| if (w.store.time(c) < s) {
            w.queue.clearRetainingCapacity();
            return null;
        };
        try w.process(c, diag);
        if (!try w.keep(c)) continue;
        // Skipped commits' parents are rewritten too, as git rewrites
        // them before it counts.
        if (w.rewriting()) try w.rewriteParents(c, diag);
        switch (w.admit()) {
            .skip => continue,
            .stop => return null,
            .show => {},
        }
        try w.printed(c);
        try w.set(c, shown_flag);
        return .{ .commit = c, .side = w.sideOf(c) };
    }
    return null;
}

fn addBoundary(w: *RevWalk) Error!void {
    var found: std.ArrayList(Index) = .empty;
    defer found.deinit(w.gpa);
    var marked: std.AutoHashMapUnmanaged(Index, void) = .empty;
    defer marked.deinit(w.gpa);
    for (w.output.items) |e| for (w.parentsOf(e)) |p| {
        if (w.flag(p) & shown_flag != 0) continue;
        if ((try marked.getOrPut(w.gpa, p)).found_existing) continue;
        try found.append(w.gpa, p);
    };
    std.mem.reverse(Index, found.items);
    try w.sortTopologically(found.items, w.options.order, true);
    for (found.items) |c| try w.output.append(w.gpa, .{ .commit = c, .boundary = true });
}

// -- the generation walk -----------------------------------------------------------

/// What the generation walk keeps: the queues of its three walks and how
/// many children each commit is still waiting on.
const GenWalk = struct {
    explore: GenQueue = .{},
    indegree_queue: GenQueue = .{},
    /// One more than the number of children each commit is waiting on, for
    /// commits the indegree walk has reached; zero for the rest.
    indegree: std.ArrayList(i32) = .empty,
    /// How deep, by generation number, the indegree walk has gone.
    depth: u64 = Commits.infinite_generation,
    topo_stack: std.ArrayList(Index) = .empty,
    topo_heap: std.ArrayList(Queued) = .empty,
    /// With `--author-date-order`, the commits whose author dates git
    /// has read: those explored, and the starting points.
    authors_read: std.AutoHashMapUnmanaged(Index, void) = .empty,
    sequence: u64 = 0,
    /// How many commits each walk took, as git's trace2 `topo_walk`
    /// statistics count them.
    explored: u64 = 0,
    counted: u64 = 0,
    walked: u64 = 0,

    fn deinit(g: *GenWalk, gpa: Allocator) void {
        g.explore.items.deinit(gpa);
        g.indegree_queue.items.deinit(gpa);
        g.indegree.deinit(gpa);
        g.topo_stack.deinit(gpa);
        g.topo_heap.deinit(gpa);
        g.authors_read.deinit(gpa);
    }
};

/// A queue of the explore or indegree walk: a binary heap, highest
/// generation number first, then newest commit date, then first in. A
/// commit's place is decided by what the store knows of it when two
/// entries are compared, and a commit not yet read has an infinite
/// generation number and no date; reading it while it waits changes what
/// it is compared with, not where it is. Taking the first entry leaves it
/// in place until the queue is next used, and a push then takes its place.
const GenQueue = struct {
    items: std.ArrayList(GenEntry) = .empty,
    taken: bool = false,
};

const GenEntry = struct { sequence: u64, commit: Index };

/// A commit's generation number as the generation walk sees it: infinite
/// before it is read, as for a commit the commit-graph does not list.
fn generationNow(w: *const RevWalk, c: Index) u64 {
    if (!w.store.isLoaded(c)) return Commits.infinite_generation;
    return w.store.generation(c);
}

fn genBefore(w: *const RevWalk, q: *const GenQueue, a: GenEntry, b: GenEntry) bool {
    _ = q;
    const ga = w.generationNow(a.commit);
    const gb = w.generationNow(b.commit);
    if (ga != gb) return ga > gb;
    const da: i64 = if (w.store.isLoaded(a.commit)) w.store.time(a.commit) else 0;
    const db: i64 = if (w.store.isLoaded(b.commit)) w.store.time(b.commit) else 0;
    if (da != db) return da > db;
    return a.sequence < b.sequence;
}

fn genSiftDown(w: *const RevWalk, q: *GenQueue, start: usize) void {
    const items = q.items.items;
    var i = start;
    while (true) {
        const l = 2 * i + 1;
        if (l >= items.len) break;
        var best = l;
        if (l + 1 < items.len and w.genBefore(q, items[l + 1], items[l])) best = l + 1;
        if (!w.genBefore(q, items[best], items[i])) break;
        std.mem.swap(GenEntry, &items[i], &items[best]);
        i = best;
    }
}

/// Removes the entry taken last, if it is still in place.
fn genSettle(w: *const RevWalk, q: *GenQueue) void {
    if (!q.taken) return;
    q.taken = false;
    const last = q.items.pop().?;
    if (q.items.items.len == 0) return;
    q.items.items[0] = last;
    w.genSiftDown(q, 0);
}

fn genPush(w: *RevWalk, g: *GenWalk, q: *GenQueue, c: Index) Allocator.Error!void {
    const e: GenEntry = .{ .sequence = g.sequence, .commit = c };
    g.sequence += 1;
    if (q.taken) {
        q.taken = false;
        q.items.items[0] = e;
        w.genSiftDown(q, 0);
        return;
    }
    try q.items.append(w.gpa, e);
    const items = q.items.items;
    var i = items.len - 1;
    while (i > 0) {
        const parent = (i - 1) / 2;
        if (!w.genBefore(q, items[i], items[parent])) break;
        std.mem.swap(GenEntry, &items[i], &items[parent]);
        i = parent;
    }
}

fn genTop(w: *const RevWalk, q: *GenQueue) ?Index {
    w.genSettle(q);
    if (q.items.items.len == 0) return null;
    return q.items.items[0].commit;
}

fn genTake(w: *const RevWalk, q: *GenQueue) ?Index {
    const top = w.genTop(q) orelse return null;
    q.taken = true;
    return top;
}

fn indegreeOf(w: *RevWalk, g: *GenWalk, c: Index) Allocator.Error!*i32 {
    const n = w.store.count();
    if (g.indegree.items.len < n) try g.indegree.appendNTimes(w.gpa, 0, n - g.indegree.items.len);
    return &g.indegree.items[c];
}

/// Explores, as git's explore walk does, every queued commit of
/// generation `depth` or more: reads it, excludes it if it is older than
/// `--since`, processes it and queues every parent it has now.
fn exploreTo(w: *RevWalk, g: *GenWalk, depth: u64, diag: ?*Diagnostics) Error!void {
    while (w.genTop(&g.explore)) |top| {
        if (w.generationNow(top) < depth) break;
        const c = w.genTake(&g.explore).?;
        g.explored += 1;
        try w.store.load(c, diag);
        if (w.options.order == .author_date) try g.authors_read.put(w.gpa, c, {});
        if (w.options.since) |s| if (w.store.time(c) < s) try w.set(c, excluded_flag);
        try w.process(c, diag);
        var i: usize = 0;
        while (i < w.heldParents(c).len) : (i += 1) {
            const p = w.heldParents(c)[i];
            if (w.flag(p) & explored_flag != 0) continue;
            try w.set(p, explored_flag);
            try w.genPush(g, &g.explore, p);
        }
    }
}

/// Counts children, as git's indegree walk does, for every queued commit
/// of generation `depth` or more, exploring as deep as each first.
fn indegreesTo(w: *RevWalk, g: *GenWalk, depth: u64, diag: ?*Diagnostics) Error!void {
    while (w.genTop(&g.indegree_queue)) |top| {
        if (w.generationNow(top) < depth) break;
        const c = w.genTake(&g.indegree_queue).?;
        g.counted += 1;
        try w.exploreTo(g, w.generationNow(c), diag);
        var i: usize = 0;
        while (true) : (i += 1) {
            const ps = w.heldParents(c);
            if (i >= ps.len or (w.options.first_parent and i > 0)) break;
            const p = ps[i];
            try w.loadParent(c, p, diag);
            const d = try w.indegreeOf(g, p);
            if (d.* != 0) {
                d.* += 1;
            } else {
                d.* = 2;
                try w.genPush(g, &g.indegree_queue, p);
            }
        }
    }
    g.depth = depth;
}

fn topoPush(w: *RevWalk, g: *GenWalk, c: Index) Error!void {
    if (w.options.since) |s| if (w.store.time(c) < s) return;
    if (w.options.order == .topo) return g.topo_stack.append(w.gpa, c);
    // git reads a commit's author date as it explores it, and orders one
    // it has not read as if it had none: an order not matched.
    if (w.options.order == .author_date and !g.authors_read.contains(c)) return error.UnsupportedAuthorDateOrdering;
    try heapPush(w.gpa, &g.topo_heap, .{ .time = try w.sortTime(c, w.options.order), .sequence = g.sequence, .commit = c });
    g.sequence += 1;
}

fn topoPop(w: *RevWalk, g: *GenWalk) ?Index {
    if (w.options.order == .topo) return g.topo_stack.pop();
    return heapPop(&g.topo_heap);
}

/// What git does with a commit as it comes out of the topological walk:
/// processes it, and counts it out of the first parent not excluded, or
/// of every parent not excluded without `--first-parent`, queueing the
/// ones no other child is waiting for. That parent is the first one past
/// an excluded first parent, too, even with `--first-parent`, and the
/// indegree walk counted only first parents then.
fn expandTopo(w: *RevWalk, g: *GenWalk, c: Index, diag: ?*Diagnostics) Error!void {
    try w.process(c, diag);
    var i: usize = 0;
    while (i < w.heldParents(c).len) : (i += 1) {
        const p = w.heldParents(c)[i];
        if (w.excluded(p)) continue;
        try w.loadParent(c, p, diag);
        const gp = w.generationNow(p);
        if (gp < g.depth) try w.indegreesTo(g, gp, diag);
        const d = try w.indegreeOf(g, p);
        d.* -= 1;
        if (d.* == 1) try w.topoPush(g, p);
        if (w.options.first_parent) break;
    }
}

/// Whether git walks by generation number, as it does with an ordering in
/// a repository with a commit-graph unless `--children`, `--left-only`,
/// `--right-only`, `--ancestry-path`, `--simplify-merges` or
/// `--simplify-by-decoration` needs the whole list first.
pub fn walksByGeneration(o: Options, has_commit_graph: bool) bool {
    if (o.order == .default or !has_commit_graph) return false;
    if (o.children or o.left_only or o.right_only or o.ancestry_path or o.ancestry_commits.len != 0) return false;
    if (o.simplify) |s| if (s.simplify_merges or s.decorated != null) return false;
    return true;
}

fn usesGenerations(w: *const RevWalk) bool {
    return walksByGeneration(w.options, w.store.graph.layers.len != 0);
}

/// Lists, as git does with generation numbers, what the top of this file
/// describes.
fn generationWalk(w: *RevWalk, diag: ?*Diagnostics) Error!void {
    var g: GenWalk = .{};
    defer g.deinit(w.gpa);

    var starts: std.ArrayList(Index) = .empty;
    defer starts.deinit(w.gpa);
    for (w.starts.items) |s| {
        if (std.mem.findScalar(Index, starts.items, s.commit) == null) try starts.append(w.gpa, s.commit);
    }
    if (starts.items.len == 0) return;
    var lowest: u64 = Commits.infinite_generation;
    for (starts.items) |c| {
        // git has read the starting points' author dates already, in
        // reading the commits it was given.
        if (w.options.order == .author_date) try g.authors_read.put(w.gpa, c, {});
        lowest = @min(lowest, w.generationNow(c));
        if (w.flag(c) & explored_flag == 0) {
            try w.set(c, explored_flag);
            try w.genPush(&g, &g.explore, c);
        }
        (try w.indegreeOf(&g, c)).* = 1;
        try w.genPush(&g, &g.indegree_queue, c);
    }
    try w.indegreesTo(&g, lowest, diag);
    var seeds: std.ArrayList(Index) = .empty;
    defer seeds.deinit(w.gpa);
    for (starts.items) |c| if ((try w.indegreeOf(&g, c)).* == 1) try seeds.append(w.gpa, c);
    if (w.options.order == .topo) {
        // Newest first out of the stack, the first given first among
        // commits of one date.
        const Newest = struct {
            fn lessThan(store: *const Commits, a: Index, b: Index) bool {
                return store.time(a) > store.time(b);
            }
        };
        std.sort.insertion(Index, seeds.items, @as(*const Commits, w.store), Newest.lessThan);
        std.mem.reverse(Index, seeds.items);
    }
    for (seeds.items) |c| try w.topoPush(&g, c);
    while (true) {
        if (w.options.max_count) |m| if (w.shown >= m) break;
        const c = w.topoPop(&g) orelse break;
        g.walked += 1;
        try w.expandTopo(&g, c, diag);
        if (w.excluded(c)) continue;
        if (w.options.since) |s| if (w.store.time(c) < s) continue;
        if (!try w.keep(c)) continue;
        if (w.rewriting()) try w.rewriteParents(c, diag);
        switch (w.admit()) {
            .skip => continue,
            .stop => break,
            .show => {},
        }
        try w.printed(c);
        try w.set(c, shown_flag);
        try w.output.append(w.gpa, .{ .commit = c, .side = w.sideOf(c) });
    }
    w.topo_statistics = .{ .explored = g.explored, .counted = g.counted, .walked = g.walked };
    if (w.options.boundary) try w.addBoundary();
    if (w.options.reverse) std.mem.reverse(Entry, w.output.items);
}

/// The next commit the walk lists, or null after the last.
pub fn next(w: *RevWalk, diag: ?*Diagnostics) Error!?Entry {
    switch (w.state) {
        .new => {
            const o = w.options;
            if (w.usesGenerations()) {
                try w.setUp(diag);
                try w.generationWalk(diag);
                w.state = .listed;
                return w.next(diag);
            }
            if (o.order != .default and w.store.graph.layers.len != 0) {
                // Where git orders by generation number without walking
                // by it, with these, its list was not matched.
                if (o.first_parent or o.since != null or o.until != null or o.since_filter != null)
                    return error.UnsupportedGraphOrdering;
            }
            if (w.rewriting() and !w.isLimited()) {
                const sim = o.simplify.?;
                if (o.first_parent or (sim.full_history and (o.reverse or o.skip != 0))) return error.UnsupportedParentRewrite;
            }
            try w.setUp(diag);
            if (w.isLimited() or w.options.boundary or w.options.reverse) {
                try w.listAll(diag);
                w.state = .listed;
            } else {
                w.state = .streaming;
            }
            return w.next(diag);
        },
        .streaming => {
            const e = try w.nextStreamed(diag) orelse {
                w.state = .done;
                return null;
            };
            return e;
        },
        .listed => {
            if (w.output_at == w.output.items.len) return null;
            w.output_at += 1;
            return w.output.items[w.output_at - 1];
        },
        .done => return null,
    }
}

// -- tests -----------------------------------------------------------------------

const testing = std.testing;
const fixture = @import("testing/fixture.zig");

test "a walk lists what rev-list lists" {
    // The differential tests in tools/walk_tests.zig compare every option;
    // this checks the library on its own.
    const gpa = testing.allocator;
    var repo = try fixture.Repo.init(gpa, testing.io);
    defer repo.deinit();
    try repo.commitFile("a", "1\n", "one");
    try repo.commitFile("a", "2\n", "two");
    try repo.git(&.{ "checkout", "-q", "-b", "side", "HEAD~1" });
    try repo.commitFile("b", "3\n", "three");
    try repo.git(&.{ "checkout", "-q", "main" });
    try repo.git(&.{ "merge", "-q", "--no-edit", "side" });
    try repo.commitFile("a", "4\n", "four");

    const DiskDatabase = @import("DiskDatabase.zig");
    const CommitGraph = @import("CommitGraph.zig");
    var db = try DiskDatabase.open(gpa, repo.io, .{ .objects_path = ".git/objects", .base = repo.tmp.dir, .format = repo.object_format }, null);
    defer db.close(repo.io);
    var graph: CommitGraph = .empty;
    var store = Commits.init(gpa, repo.io, db.database(), &graph, repo.object_format, .{});
    defer store.deinit();

    const ids = struct {
        fn of(r: *fixture.Repo, rev: []const u8) !object.Id {
            const out = try r.output(&.{ "rev-parse", rev });
            defer r.gpa.free(out);
            return object.Id.parseHex(r.object_format, std.mem.trimEnd(u8, out, "\n"));
        }
    };
    for ([_]struct { args: []const []const u8, order: Order }{
        .{ .args = &.{"main"}, .order = .default },
        .{ .args = &.{ "main", "^side" }, .order = .default },
        .{ .args = &.{"main"}, .order = .topo },
    }) |case| {
        var w = init(gpa, &store, .{ .order = case.order });
        defer w.deinit();
        var git_args: std.ArrayList([]const u8) = .empty;
        defer git_args.deinit(gpa);
        try git_args.append(gpa, "rev-list");
        if (case.order == .topo) try git_args.append(gpa, "--topo-order");
        for (case.args) |a| {
            try git_args.append(gpa, a);
            const excl = a[0] == '^';
            try w.addStart(.{ .commit = try store.name(try ids.of(&repo, if (excl) a[1..] else a)), .excluded = excl });
        }
        const out = try repo.output(git_args.items);
        defer gpa.free(out);
        var lines = std.mem.tokenizeScalar(u8, out, '\n');
        while (try w.next(null)) |e| {
            const want = lines.next() orelse return error.TooMany;
            try testing.expect(store.id(e.commit).eql(try .parseHex(repo.object_format, want)));
        }
        try testing.expectEqual(null, lines.next());
    }
}