1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "context"
7 "fmt"
8 "strings"
9 "unsafe"
10)
11
12// LastCommits finds, in one walk, the last commit that touched each entry of
13// a directory: for every name, the same commit as
14//
15// git log -n 1 <start> -- <dir>/<name>
16//
17// with the same history simplification. The result has one id per name, in
18// the order of names; the zero ObjectID means that no commit reachable from
19// start has the entry (it never existed). Read the commits you need with
20// ReadCommit; many names share the same commit.
21//
22// dir is relative to the root of the repository ("" or "." for the root
23// itself). Each name is one path component, taken literally.
24//
25// Algorithm. The history of one path is a walk where a merge that is
26// TREESAME to a parent follows only the first such parent, so two paths can
27// follow different parents at the same merge and then visit commits in
28// different orders. A single shared walk would therefore not give the
29// per-path answers. Instead the names travel as groups. All names start in
30// one group, which owns the queue and the set of seen commits of their (so
31// far identical) walks. For each popped commit the group computes, per name,
32// the first parent whose entry is identical to the commit's; a name with no
33// such parent is changed by the commit: it is resolved and leaves the group.
34// The other names follow exactly the parent they matched (the only parent
35// for a commit that has one). When the names of a group match different
36// parents of a merge, the group splits: the queue and the seen set are
37// cloned, each part follows its parent. Every group therefore holds the
38// exact state of the individual walk of each of its names, and the answers
39// are those of N separate walks, but a commit is loaded and compared once
40// per group instead of once per name. The walk ends when every name has an
41// answer. A directory that did not change (same tree id, or a Bloom filter
42// that says so) settles all the names of a group at once.
43func (r *Repo) LastCommits(ctx context.Context, start ObjectID, dir string, names []string) ([]ObjectID, error) {
44 res := make([]ObjectID, len(names))
45 if len(names) == 0 {
46 return res, nil
47 }
48 spec, err := parsePathSpec(dir)
49 if err != nil {
50 return nil, err
51 }
52 spec.dirOnly = false
53 // Distinct names; duplicates copy their answer at the end.
54 idx := make(map[string]int32, len(names))
55 uniq := make([]string, 0, len(names))
56 for _, n := range names {
57 if n == "" || n == "." || n == ".." || strings.ContainsAny(n, "/\x00") {
58 return nil, fmt.Errorf("%w: entry name %q", ErrInvalidPath, n)
59 }
60 if _, ok := idx[n]; !ok {
61 idx[n] = int32(len(uniq))
62 uniq = append(uniq, n)
63 }
64 }
65 w, err := r.newWalker(ctx, start, WalkOptions{})
66 if err != nil {
67 return nil, err
68 }
69 defer w.close()
70 s := &lastState{
71 w: w, d: newPathDiffer(r, spec), idx: idx, n: len(uniq),
72 found: make([]ObjectID, len(uniq)),
73 remaining: len(uniq),
74 }
75 if spec.bloom {
76 s.key = newBloomKey([]byte(spec.String()))
77 s.useBloom = s.key.usable
78 }
79 // The cache holds at most about 1 MiB of entries, 16 trees at least.
80 s.slots = min(256, max(16, (1<<20)/(len(uniq)*int(unsafe.Sizeof(pathEntry{})))))
81 s.absent = make([]pathEntry, len(uniq))
82 if err := s.run(); err != nil {
83 return nil, err
84 }
85 for i, n := range names {
86 res[i] = s.found[idx[n]]
87 }
88 return res, nil
89}
90
91// LastCommit returns the first commit of Walk with the given path and Limit
92// 1, that is the answer of "git log -n 1 <start> -- <path>". The boolean is
93// false when no commit has the path.
94func (r *Repo) LastCommit(ctx context.Context, start ObjectID, path string) (ObjectID, bool, error) {
95 for c, err := range r.Walk(ctx, start, WalkOptions{Path: path, Limit: 1, IDOnly: true}) {
96 if err != nil {
97 return ObjectID{}, false, err
98 }
99 return c.ID, true, nil
100 }
101 return ObjectID{}, false, nil
102}
103
104// lastGroup is a set of names whose individual walks are in the same state.
105type lastGroup struct {
106 walkState
107 active []int32
108}
109
110type lastState struct {
111 w *walker
112 d *pathDiffer // resolves the directory
113 // useBloom is set when the directory is spelled the way Git inserts it.
114 useBloom bool
115 key bloomKey
116
117 idx map[string]int32
118 n int
119 found []ObjectID
120 remaining int
121
122 // A cache of the entries of the names in directory trees, 4-way
123 // associative, backed by one slab so that it never allocates per tree.
124 slots int
125 cache []entrySlot
126 slab []pathEntry
127 tick uint64 // counts steps; the slots used by the current step are kept
128 absent []pathEntry // all names missing
129 buf []byte
130
131 // scratch
132 ks []int8
133}
134
135type entrySlot struct {
136 tree ObjectID
137 used uint64 // step that last used the slot, 0 when empty
138}
139
140// dirOf finds the directory in a root tree.
141func (s *lastState) dirOf(root ObjectID) (ObjectID, bool, error) {
142 if len(s.d.comps) == 0 {
143 return root, true, nil
144 }
145 e, err := s.d.resolve(root)
146 if err != nil {
147 return ObjectID{}, false, err
148 }
149 return e.id, e.found && e.mode.IsTree(), nil
150}
151
152// entries returns what the directory tree holds for each name; absent
153// directories hold nothing. The slice is shared: do not modify it.
154func (s *lastState) entries(dir ObjectID, ok bool) ([]pathEntry, error) {
155 if !ok || dir == emptyTreeID {
156 return s.absent, nil
157 }
158 if s.cache == nil {
159 s.cache = make([]entrySlot, s.slots)
160 s.slab = make([]pathEntry, s.slots*s.n)
161 }
162 base := (int(dir[0]) | int(dir[1])<<8) % s.slots
163 victim := -1
164 for j := 0; j < 4 && j < s.slots; j++ {
165 k := (base + j) % s.slots
166 c := &s.cache[k]
167 if c.used != 0 && c.tree == dir {
168 c.used = s.tick
169 return s.slab[k*s.n : (k+1)*s.n], nil
170 }
171 // Slots used by this step still back slices in use: keep them.
172 if c.used != s.tick && (victim < 0 || c.used < s.cache[victim].used) {
173 victim = k
174 }
175 }
176 typ, data, err := s.w.r.ReadObject(dir, s.buf)
177 if err != nil {
178 return nil, err
179 }
180 s.buf = data
181 if typ != TypeTree {
182 return nil, wrongType(dir, typ, TypeTree)
183 }
184 var ents []pathEntry
185 if victim >= 0 {
186 ents = s.slab[victim*s.n : (victim+1)*s.n]
187 clear(ents)
188 } else {
189 ents = make([]pathEntry, s.n) // every slot is in use by this step
190 }
191 if err := ParseTree(data, func(e Entry) bool {
192 if i, hit := s.idx[string(e.Name)]; hit {
193 ents[i] = pathEntry{id: e.ID, mode: e.Mode, found: true}
194 }
195 return true
196 }); err != nil {
197 return nil, wrapObj(dir, err)
198 }
199 if victim >= 0 {
200 s.cache[victim] = entrySlot{tree: dir, used: s.tick}
201 }
202 return ents, nil
203}
204
205func (s *lastState) run() error {
206 root := &lastGroup{walkState: s.w.walkState, active: make([]int32, s.n)}
207 for i := range root.active {
208 root.active[i] = int32(i)
209 }
210 stack := []*lastGroup{root}
211 visited := 0
212 for len(stack) > 0 && s.remaining > 0 {
213 g := stack[len(stack)-1]
214 stack = stack[:len(stack)-1]
215 for len(g.q) > 0 && len(g.active) > 0 && s.remaining > 0 {
216 if visited++; visited%walkCheckEvery == 0 {
217 if err := s.w.ctx.Err(); err != nil {
218 return err
219 }
220 }
221 extra, err := s.step(g)
222 if err != nil {
223 return err
224 }
225 stack = append(stack, extra...)
226 }
227 }
228 return nil
229}
230
231// step processes the next commit of the group. It returns the groups split
232// off from g.
233func (s *lastState) step(g *lastGroup) ([]*lastGroup, error) {
234 w := s.w
235 s.tick++
236 n := g.pop().n
237 tree, parents, err := w.load(n, w.parents[:0])
238 w.parents = parents
239 if err != nil {
240 return nil, err
241 }
242 if len(parents) == 0 {
243 dir, ok, err := s.dirOf(tree)
244 if err != nil {
245 return nil, err
246 }
247 ents, err := s.entries(dir, ok)
248 if err != nil {
249 return nil, err
250 }
251 return nil, s.resolve(g, n, func(i int32) bool { return ents[i].found })
252 }
253
254 // Fast path: the directory is unchanged against the first parent.
255 if s.useBloom && n.ing {
256 if maybe, ok := w.g.maybeChangedKey(n.pos, &s.key); ok && !maybe {
257 return nil, s.follow(g, parents[0])
258 }
259 }
260 dir, ok, err := s.dirOf(tree)
261 if err != nil {
262 return nil, err
263 }
264 p0tree, err := w.treeOf(parents[0])
265 if err != nil {
266 return nil, err
267 }
268 pdir, pok, err := s.dirOf(p0tree)
269 if err != nil {
270 return nil, err
271 }
272 if ok == pok && (!ok || dir == pdir) {
273 return nil, s.follow(g, parents[0])
274 }
275
276 ec, err := s.entries(dir, ok)
277 if err != nil {
278 return nil, err
279 }
280 if cap(s.ks) < s.n {
281 s.ks = make([]int8, s.n)
282 }
283 ks := s.ks[:s.n]
284 // The first parent each active name is identical in, -1 if none.
285 for _, i := range g.active {
286 ks[i] = -1
287 }
288 for pi, p := range parents {
289 var pe []pathEntry
290 if pi == 0 {
291 pe, err = s.entries(pdir, pok)
292 } else {
293 var pt ObjectID
294 if pt, err = w.treeOf(p); err == nil {
295 var d2 ObjectID
296 var ok2 bool
297 if d2, ok2, err = s.dirOf(pt); err == nil {
298 pe, err = s.entries(d2, ok2)
299 }
300 }
301 }
302 if err != nil {
303 return nil, err
304 }
305 for _, i := range g.active {
306 if ks[i] < 0 && pe[i] == ec[i] {
307 ks[i] = int8(pi)
308 }
309 }
310 }
311 // Names changed against every parent are resolved here.
312 live := g.active[:0]
313 for _, i := range g.active {
314 if ks[i] < 0 {
315 id, err := w.idOf(n)
316 if err != nil {
317 return nil, err
318 }
319 s.found[i] = id
320 s.remaining--
321 continue
322 }
323 live = append(live, i)
324 }
325 g.active = live
326 if len(live) == 0 {
327 return nil, nil
328 }
329 // All the names follow the same parent: no split.
330 same := true
331 for _, i := range live[1:] {
332 if ks[i] != ks[live[0]] {
333 same = false
334 break
335 }
336 }
337 if same {
338 return nil, s.follow(g, parents[ks[live[0]]])
339 }
340 // Split the group by the parent each remaining name follows.
341 var extra []*lastGroup
342 first := true
343 var firstParent node
344 for pi := range parents {
345 var part []int32
346 for _, i := range live {
347 if int(ks[i]) == pi {
348 part = append(part, i)
349 }
350 }
351 if len(part) == 0 {
352 continue
353 }
354 if first {
355 first, firstParent = false, parents[pi]
356 g.active = part
357 continue
358 }
359 ng := &lastGroup{walkState: g.clone(), active: part}
360 if err := s.follow(ng, parents[pi]); err != nil {
361 return nil, err
362 }
363 extra = append(extra, ng)
364 }
365 // g is still in the state before inserting the parent; the clones were
366 // made before g follows its own.
367 return extra, s.follow(g, firstParent)
368}
369
370// resolve settles the active names for which changed is true at commit n
371// (a root commit), and keeps the others.
372func (s *lastState) resolve(g *lastGroup, n node, changed func(int32) bool) error {
373 id, err := s.w.idOf(n)
374 if err != nil {
375 return err
376 }
377 live := g.active[:0]
378 for _, i := range g.active {
379 if changed(i) {
380 s.found[i] = id
381 s.remaining--
382 continue
383 }
384 live = append(live, i)
385 }
386 g.active = live
387 return nil
388}
389
390// follow queues p in the walk of g unless it was already seen.
391func (s *lastState) follow(g *lastGroup, p node) error {
392 if !g.seen.add(p) {
393 return nil
394 }
395 t, err := s.w.timeOf(p)
396 if err != nil {
397 return err
398 }
399 g.push(t, p)
400 return nil
401}