1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "context"
7 "errors"
8 "fmt"
9 "iter"
10 "maps"
11 "slices"
12)
13
14// This file implements history walks that match "git log" exactly.
15//
16// Order. Git's default walk keeps the commits to visit in a list sorted by
17// committer date, newest first; a parent is inserted after every queued
18// commit that has the same date or a newer one (commit_list_insert_by_date),
19// and the initial list is sorted by a stable sort. The result is a priority
20// queue by (date descending, insertion order ascending), which is what
21// queue implements. A commit is queued the first time it is seen as a parent
22// and never again. The commit-graph is not needed for the order; it only
23// makes parents, dates and root trees cheap to read.
24//
25// Path history (git's default simplification). When a path is given, a
26// commit is compared with its parents in order. The first parent that has
27// the same content at the path makes the commit TREESAME: the commit is not
28// shown and only that parent is followed. A commit that differs from every
29// parent is shown and all its parents are followed. A root commit is shown
30// when the path exists in it. The rewriting of parents that git does when
31// printing does not change which commits are shown, so it is not done.
32//
33// The Bloom filter of a commit answers "did the path change relative to the
34// first parent"; when the answer is a definite no, the commit is TREESAME to
35// its first parent without reading any tree.
36
37// WalkOptions selects what Walk yields.
38type WalkOptions struct {
39 // Skip is the number of commits to leave out, counted after path
40 // simplification, like "git log --skip".
41 Skip int
42 // Limit is the number of commits to yield, like "git log -n". Zero or
43 // less means no limit.
44 Limit int
45 // Path restricts the history like "git log -- <path>": a file, a
46 // directory or a submodule, written relative to the root of the
47 // repository, taken literally (no globs). The empty path means no
48 // restriction. "." and "dir/" are accepted; a path outside the
49 // repository gives ErrInvalidPath.
50 Path string
51 // IDOnly makes Walk fill only ID, Tree, Parents and Committer.Time when
52 // the commit-graph has the commit, which then costs no object read.
53 // Without it every field is filled.
54 IDOnly bool
55}
56
57// walkCheckEvery is the number of visited commits between two checks of the
58// context.
59const walkCheckEvery = 64
60
61// Walk yields the commits reachable from start in the order of "git log
62// <start>", restricted as opts says. The yielded *Commit is reused: it and
63// the bytes it points to are valid until the next iteration. On failure the
64// sequence yields (nil, err) once and ends. start must be a commit id; use
65// PeelToCommit first for a tag.
66//
67// A Walk uses the commit-graph (parents, dates, root trees, changed-path
68// Bloom filters) when the repository has one, and reads the objects for the
69// commits it does not cover. The graph in use when the walk starts is kept
70// for its whole duration, even if Refresh replaces it.
71func (r *Repo) Walk(ctx context.Context, start ObjectID, opts WalkOptions) iter.Seq2[*Commit, error] {
72 return func(yield func(*Commit, error) bool) {
73 w, err := r.newWalker(ctx, start, opts)
74 if err != nil {
75 yield(nil, err)
76 return
77 }
78 defer w.close()
79 if err := w.run(yield); err != nil {
80 yield(nil, err)
81 }
82 }
83}
84
85// node designates a commit: by position when the graph has it, else by id.
86type node struct {
87 id ObjectID
88 pos uint32
89 ing bool // in the graph: pos is valid and id is not set
90}
91
92type qent struct {
93 time int64
94 seq uint64
95 n node
96}
97
98// walkState is the part of a walk that decides its order: the queue of
99// commits to visit and the set of those already queued.
100type walkState struct {
101 q []qent
102 seq uint64
103 seen seenSet
104}
105
106func (s *walkState) clone() walkState {
107 return walkState{q: slices.Clone(s.q), seq: s.seq, seen: s.seen.clone()}
108}
109
110type walker struct {
111 r *Repo
112 g *commitGraph // retained, may be nil
113 ctx context.Context
114 opts WalkOptions
115
116 walkState
117
118 path *pathDiffer // nil without a path
119 key bloomKey
120 // useBloom is set when the path is spelled the way Git inserts it.
121 useBloom bool
122
123 cm Commit // scratch for commits read to follow history
124 out Commit // what is yielded
125 pbuf []uint32
126 parents []node
127}
128
129func (r *Repo) newWalker(ctx context.Context, start ObjectID, opts WalkOptions) (*walker, error) {
130 if ctx == nil {
131 ctx = context.Background()
132 }
133 w := &walker{r: r, ctx: ctx, opts: opts}
134 if opts.Skip < 0 {
135 w.opts.Skip = 0
136 }
137 if opts.Path != "" {
138 spec, err := parsePathSpec(opts.Path)
139 if err != nil {
140 return nil, err
141 }
142 w.path = newPathDiffer(r, spec)
143 if spec.bloom {
144 w.key = newBloomKey([]byte(spec.String()))
145 w.useBloom = w.key.usable
146 }
147 }
148 g, err := r.acquireGraph()
149 if err != nil {
150 return nil, err
151 }
152 w.g = g
153 w.seen.init(g)
154 n, err := w.nodeOf(start)
155 if err != nil {
156 w.close()
157 return nil, err
158 }
159 t, err := w.timeOf(n)
160 if err != nil {
161 w.close()
162 return nil, err
163 }
164 w.seen.add(n)
165 w.push(t, n)
166 return w, nil
167}
168
169func (w *walker) close() {
170 if w.g != nil {
171 _ = w.g.release()
172 w.g = nil
173 }
174}
175
176// nodeOf resolves an id to a node, preferring the graph.
177func (w *walker) nodeOf(id ObjectID) (node, error) {
178 if w.g != nil {
179 if pos, ok := w.g.lookup(id); ok {
180 return node{pos: pos, ing: true}, nil
181 }
182 }
183 return node{id: id}, nil
184}
185
186// idOf returns the object id of n.
187func (w *walker) idOf(n node) (ObjectID, error) {
188 if !n.ing {
189 return n.id, nil
190 }
191 id, err := w.g.commitID(n.pos)
192 return ObjectID(id), err
193}
194
195// timeOf returns the committer date of n.
196func (w *walker) timeOf(n node) (int64, error) {
197 if n.ing {
198 return w.g.commitTime(n.pos)
199 }
200 if err := w.r.ReadCommit(n.id, &w.cm); err != nil {
201 return 0, err
202 }
203 return w.cm.Committer.Time, nil
204}
205
206// treeOf returns the root tree of n.
207func (w *walker) treeOf(n node) (ObjectID, error) {
208 if n.ing {
209 t, err := w.g.rootTree(n.pos)
210 return ObjectID(t), err
211 }
212 if err := w.r.ReadCommit(n.id, &w.cm); err != nil {
213 return ObjectID{}, err
214 }
215 return w.cm.Tree, nil
216}
217
218// load returns the root tree of n and appends its parents to dst.
219func (w *walker) load(n node, dst []node) (tree ObjectID, out []node, err error) {
220 if n.ing {
221 t, err := w.g.rootTree(n.pos)
222 if err != nil {
223 return tree, dst, err
224 }
225 w.pbuf, err = w.g.appendParents(w.pbuf[:0], n.pos)
226 if err != nil {
227 return tree, dst, err
228 }
229 for _, p := range w.pbuf {
230 dst = append(dst, node{pos: p, ing: true})
231 }
232 return ObjectID(t), dst, nil
233 }
234 if err := w.r.ReadCommit(n.id, &w.cm); err != nil {
235 return tree, dst, err
236 }
237 for _, p := range w.cm.Parents {
238 pn, _ := w.nodeOf(p)
239 dst = append(dst, pn)
240 }
241 return w.cm.Tree, dst, nil
242}
243
244// run drives the walk.
245func (w *walker) run(yield func(*Commit, error) bool) error {
246 skip, limit := w.opts.Skip, w.opts.Limit
247 for visited := 0; len(w.q) > 0; visited++ {
248 if visited%walkCheckEvery == 0 {
249 if err := w.ctx.Err(); err != nil {
250 return err
251 }
252 }
253 n := w.pop().n
254 tree, parents, err := w.load(n, w.parents[:0])
255 w.parents = parents
256 if err != nil {
257 return err
258 }
259 show := true
260 if w.path != nil {
261 same, followed, err := w.simplify(n, tree, parents)
262 if err != nil {
263 return err
264 }
265 show = !same
266 parents = followed
267 }
268 if show {
269 if skip > 0 {
270 skip--
271 } else {
272 c, err := w.fill(n)
273 if err != nil {
274 return err
275 }
276 if !yield(c, nil) {
277 return nil
278 }
279 if limit > 0 {
280 if limit--; limit == 0 {
281 return nil
282 }
283 }
284 }
285 }
286 for _, p := range parents {
287 if !w.seen.add(p) {
288 continue
289 }
290 t, err := w.timeOf(p)
291 if err != nil {
292 return err
293 }
294 w.push(t, p)
295 }
296 }
297 return nil
298}
299
300// simplify applies git's default history simplification to n. It reports
301// whether n is TREESAME and returns the parents to follow.
302func (w *walker) simplify(n node, tree ObjectID, parents []node) (same bool, follow []node, err error) {
303 if len(parents) == 0 {
304 if w.useBloom && n.ing {
305 if maybe, ok := w.g.maybeChangedKey(n.pos, &w.key); ok && !maybe {
306 return true, parents, nil
307 }
308 }
309 ex, err := w.path.exists(tree)
310 return !ex, parents, err
311 }
312 for i, p := range parents {
313 if i == 0 && w.useBloom && n.ing {
314 if maybe, ok := w.g.maybeChangedKey(n.pos, &w.key); ok && !maybe {
315 return true, parents[:1], nil
316 }
317 }
318 pt, err := w.treeOf(p)
319 if err != nil {
320 return false, nil, err
321 }
322 s, err := w.path.same(pt, tree)
323 if err != nil {
324 return false, nil, err
325 }
326 if s {
327 return true, parents[i : i+1], nil
328 }
329 }
330 return false, parents, nil
331}
332
333// fill prepares the commit to yield.
334func (w *walker) fill(n node) (*Commit, error) {
335 id, err := w.idOf(n)
336 if err != nil {
337 return nil, err
338 }
339 c := &w.out
340 if w.opts.IDOnly && n.ing {
341 tree, err := w.g.rootTree(n.pos)
342 if err != nil {
343 return nil, err
344 }
345 t, err := w.g.commitTime(n.pos)
346 if err != nil {
347 return nil, err
348 }
349 w.pbuf, err = w.g.appendParents(w.pbuf[:0], n.pos)
350 if err != nil {
351 return nil, err
352 }
353 *c = Commit{buf: c.buf, Parents: c.Parents[:0]}
354 c.ID, c.Tree = id, ObjectID(tree)
355 c.Committer.Time = t
356 for _, p := range w.pbuf {
357 pid, err := w.g.commitID(p)
358 if err != nil {
359 return nil, err
360 }
361 c.Parents = append(c.Parents, ObjectID(pid))
362 }
363 return c, nil
364 }
365 if err := w.r.ReadCommit(id, c); err != nil {
366 return nil, err
367 }
368 return c, nil
369}
370
371// push adds a commit to the queue.
372func (w *walkState) push(t int64, n node) {
373 w.seq++
374 w.q = append(w.q, qent{time: t, seq: w.seq, n: n})
375 i := len(w.q) - 1
376 for i > 0 {
377 p := (i - 1) / 2
378 if !qless(&w.q[i], &w.q[p]) {
379 break
380 }
381 w.q[i], w.q[p] = w.q[p], w.q[i]
382 i = p
383 }
384}
385
386// pop removes the first commit of the queue.
387func (w *walkState) pop() qent {
388 top := w.q[0]
389 last := len(w.q) - 1
390 w.q[0] = w.q[last]
391 w.q = w.q[:last]
392 i := 0
393 for {
394 l := 2*i + 1
395 if l >= last {
396 break
397 }
398 m := l
399 if r := l + 1; r < last && qless(&w.q[r], &w.q[l]) {
400 m = r
401 }
402 if !qless(&w.q[m], &w.q[i]) {
403 break
404 }
405 w.q[i], w.q[m] = w.q[m], w.q[i]
406 i = m
407 }
408 return top
409}
410
411// qless orders by date, newest first, then by insertion.
412func qless(a, b *qent) bool {
413 if a.time != b.time {
414 return a.time > b.time
415 }
416 return a.seq < b.seq
417}
418
419// seenSet records the commits already queued: a bitset by graph position and
420// a map for the commits outside the graph. A commit is never queued twice,
421// so a walk ends even on a graph whose parents form a cycle.
422type seenSet struct {
423 bits []uint64
424 ids map[ObjectID]struct{}
425}
426
427func (s *seenSet) init(g *commitGraph) {
428 if g != nil {
429 s.bits = make([]uint64, (uint64(g.numCommits())+63)/64)
430 }
431}
432
433func (s *seenSet) clone() seenSet {
434 c := seenSet{bits: slices.Clone(s.bits)}
435 if s.ids != nil {
436 c.ids = maps.Clone(s.ids)
437 }
438 return c
439}
440
441// add marks n and reports whether it was not marked yet.
442func (s *seenSet) add(n node) bool {
443 if n.ing {
444 w, b := n.pos/64, uint64(1)<<(n.pos%64)
445 if int(w) >= len(s.bits) {
446 return false
447 }
448 if s.bits[w]&b != 0 {
449 return false
450 }
451 s.bits[w] |= b
452 return true
453 }
454 if _, ok := s.ids[n.id]; ok {
455 return false
456 }
457 if s.ids == nil {
458 s.ids = make(map[ObjectID]struct{})
459 }
460 s.ids[n.id] = struct{}{}
461 return true
462}
463
464// graphState is the commit-graph of a Repo as of the last load.
465type graphState struct {
466 g *commitGraph // owner's reference; nil when there is none
467 stamp graphStamp
468 err error // corruption found when opening, reported by walks
469 at int64 // unix nanoseconds: when the stamp was taken, before the load
470}
471
472// acquireGraph returns the current commit-graph with a reference the caller
473// must release, nil if there is none. Only a corrupt graph is an error: a
474// graph that cannot be opened for another reason (a layer removed by a
475// concurrent write, an unsupported version) is as good as absent.
476func (r *Repo) acquireGraph() (*commitGraph, error) {
477 for {
478 s := r.graph.Load()
479 if s == nil {
480 if err := r.refreshGraph(false); err != nil {
481 return nil, err
482 }
483 if s = r.graph.Load(); s == nil {
484 return nil, ErrClosed
485 }
486 }
487 if s.err != nil {
488 return nil, s.err
489 }
490 if s.g == nil {
491 return nil, nil
492 }
493 if s.g.retain() {
494 return s.g, nil
495 }
496 // Replaced and closed between the load and the retain.
497 }
498}
499
500// refreshGraph reloads the commit-graph when its files changed, or always
501// with force. The old graph stays alive for the walks that retained it.
502func (r *Repo) refreshGraph(force bool) error {
503 r.gmu.Lock()
504 defer r.gmu.Unlock()
505 cur := r.graph.Load()
506 if cur != nil && cur.err == ErrClosed {
507 return ErrClosed
508 }
509 // Take the time before the stat data and the content, so that a write
510 // that follows is never mistaken for the version that was loaded.
511 at := r.now().UnixNano()
512 stamp := r.paths.graph.stamp()
513 if cur != nil && !force && cur.stamp == stamp && cur.stamp.trusted(cur.at) {
514 return nil
515 }
516 st := &graphState{stamp: stamp, at: at}
517 g, err := openCommitGraph(r.dir + "/objects")
518 switch {
519 case err == nil:
520 st.g = g
521 case errors.Is(err, errGraphCorrupt):
522 st.err = fmt.Errorf("%w: %w", ErrCorrupt, err)
523 }
524 // Any other error (no graph, vanished layer, unsupported) means no graph.
525 old := r.graph.Swap(st)
526 if old != nil && old.g != nil {
527 _ = old.g.close()
528 }
529 return nil
530}
531
532func (r *Repo) closeGraph() {
533 r.gmu.Lock()
534 defer r.gmu.Unlock()
535 if old := r.graph.Swap(&graphState{err: ErrClosed}); old != nil && old.g != nil {
536 _ = old.g.close()
537 }
538}