Something went wrong. Try again.
A Zig library that reads git repositories without running git, with log, show and diff output byte-identical to git's.
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979// 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()); }}