1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "encoding/binary"
7 "fmt"
8 "os"
9 "path/filepath"
10 "strconv"
11 "strings"
12 "testing"
13)
14
15func TestMurmur3Vectors(t *testing.T) {
16 // Reference values of MurmurHash3_x86_32 (same vectors as git t0095).
17 for _, c := range []struct {
18 in string
19 seed uint32
20 want uint32
21 }{
22 {"", 0, 0},
23 {"", 1, 0x514e28b7},
24 {"", 0xffffffff, 0x81f16f39},
25 {"test", 0, 0xba6bd213},
26 {"test", 0x9747b28c, 0x704b81dc},
27 {"Hello, world!", 0, 0xc0363e43},
28 {"Hello, world!", 0x9747b28c, 0x24884cba},
29 {"The quick brown fox jumps over the lazy dog", 0, 0x2e4ff723},
30 {"The quick brown fox jumps over the lazy dog", 0x9747b28c, 0x2fa826cd},
31 {"aaaa", 0x9747b28c, 0x5a97808a},
32 {"aaa", 0x9747b28c, 0x283e0130},
33 {"aa", 0x9747b28c, 0x5d211726},
34 {"a", 0x9747b28c, 0x7fa09ea6},
35 } {
36 if got := murmur3Seeded(c.seed, []byte(c.in), false); got != c.want {
37 t.Errorf("murmur3(%q, %#x) = %#x, want %#x", c.in, c.seed, got, c.want)
38 }
39 // ASCII input is identical in both versions.
40 if got := murmur3Seeded(c.seed, []byte(c.in), true); got != c.want {
41 t.Errorf("signed murmur3(%q, %#x) = %#x, want %#x", c.in, c.seed, got, c.want)
42 }
43 }
44}
45
46func TestBloomKeyVersions(t *testing.T) {
47 a := newBloomKey([]byte("src/main.go"))
48 if a.v1 != a.v2 {
49 t.Error("ASCII path must hash identically in v1 and v2")
50 }
51 b := newBloomKey([]byte("caf\xc3\xa9/men\xc3\xbc.txt"))
52 if b.v1 == b.v2 {
53 t.Error("high-bit path must hash differently in v1 and v2")
54 }
55 if newBloomKeyString("x") != newBloomKey([]byte("x")) {
56 t.Error("string and bytes keys differ")
57 }
58}
59
60// bloomPaths returns the keys git inserts for a changed path: the path and
61// every leading directory.
62func bloomPaths(p string) []string {
63 out := []string{p}
64 for i := len(p) - 1; i > 0; i-- {
65 if p[i] == '/' {
66 out = append(out, p[:i])
67 }
68 }
69 return out
70}
71
72// changedPaths lists the paths that differ between c and its first parent
73// (the empty tree for a root commit), as git sees them.
74func changedPaths(t testing.TB, dir string, c *refCommit) []string {
75 t.Helper()
76 var out string
77 if len(c.parents) == 0 {
78 out = graphGit(t, dir, 0, "diff-tree", "-r", "-z", "--root", "--name-only", "--no-commit-id", fmt.Sprintf("%x", c.id))
79 } else {
80 out = graphGit(t, dir, 0, "diff-tree", "-r", "-z", "--name-only", "--no-commit-id", fmt.Sprintf("%x", c.parents[0]), fmt.Sprintf("%x", c.id))
81 }
82 var paths []string
83 for _, p := range strings.Split(out, "\x00") {
84 if p != "" {
85 paths = append(paths, p)
86 }
87 }
88 return paths
89}
90
91// checkBloomAgainstGit verifies the Bloom filters of every commit of g for
92// the changed paths reported by git: no false negatives for the path or any
93// leading directory, and unchanged paths mostly rejected.
94func checkBloomAgainstGit(t *testing.T, dir string, g *commitGraph, cs []refCommit, c gcase) {
95 t.Helper()
96 checkBloomSample(t, dir, g, cs, c.bloom, c.bloomVer, 1)
97}
98
99// checkBloomSample is checkBloomAgainstGit for every step-th commit. wantVer
100// is the BDAT version expected when bloom is true.
101func checkBloomSample(t *testing.T, dir string, g *commitGraph, cs []refCommit, bloom bool, wantVer uint32, step int) {
102 t.Helper()
103 var checked, queries, unchangedQueries, falsePositives, unknown int
104 for i := 0; i < len(cs); i += step {
105 cm := &cs[i]
106 pos, ok := g.lookup(cm.id)
107 if !ok {
108 t.Fatalf("lookup(%x)", cm.id)
109 }
110 paths := changedPaths(t, dir, cm)
111 if !bloom {
112 if g.hasBloom(pos) {
113 t.Fatalf("commit %x has a Bloom filter in a graph written without --changed-paths", cm.id)
114 }
115 for _, p := range paths {
116 if maybe, ok := g.maybeChanged(pos, []byte(p)); ok || maybe {
117 t.Fatalf("maybeChanged = %v,%v without filters", maybe, ok)
118 }
119 }
120 continue
121 }
122 l, _ := g.layerOf(pos)
123 if !l.hasBloom || l.bloomVersion != wantVer {
124 t.Fatalf("layer bloom = %v version %d, want version %d", l.hasBloom, l.bloomVersion, wantVer)
125 }
126 if len(paths) > 512 {
127 if _, ok := g.maybeChanged(pos, []byte(paths[0])); ok {
128 t.Fatalf("commit with %d changes should be unknown", len(paths))
129 }
130 continue
131 }
132 set := map[string]bool{}
133 for _, p := range paths {
134 for _, k := range bloomPaths(p) {
135 set[k] = true
136 }
137 }
138 if len(paths) == 0 {
139 // git writes the one-byte all-zero filter for "nothing changed".
140 if maybe, ok := g.maybeChanged(pos, []byte("README")); !ok || maybe {
141 t.Fatalf("empty change set: maybe=%v ok=%v", maybe, ok)
142 }
143 }
144 for k := range set {
145 key := newBloomKey([]byte(k))
146 maybe, ok := g.maybeChangedKey(pos, &key)
147 if !ok {
148 unknown++
149 continue
150 }
151 if !maybe {
152 t.Fatalf("commit %x: false negative for %q (changed: %q)", cm.id, k, paths)
153 }
154 queries++
155 }
156 // Unchanged paths: names that cannot be in the set.
157 for j := range 40 {
158 p := fmt.Sprintf("no/such/dir%d/file-%d.txt", j, j*7+i)
159 if set[p] {
160 continue
161 }
162 for _, q := range bloomPaths(p) {
163 if set[q] {
164 continue
165 }
166 key := newBloomKey([]byte(q))
167 maybe, ok := g.maybeChangedKey(pos, &key)
168 if !ok {
169 continue
170 }
171 unchangedQueries++
172 if maybe {
173 falsePositives++
174 }
175 }
176 }
177 checked++
178 }
179 if !bloom {
180 return
181 }
182 if checked == 0 || queries == 0 {
183 t.Fatalf("no Bloom queries ran (checked %d commits)", checked)
184 }
185 rate := float64(falsePositives) / float64(max(unchangedQueries, 1))
186 t.Logf("bloom v%d: %d commits, %d positive queries (%d unknown), false positives %d/%d = %.2f%%",
187 wantVer, checked, queries, unknown, falsePositives, unchangedQueries, rate*100)
188 if rate > 0.10 {
189 t.Errorf("false positive rate %.1f%% is too high for 10 bits per entry", rate*100)
190 }
191}
192
193// With a v1 graph, the v2 hash must not be used for high-bit paths (that is
194// the bug v2 fixes); with v2, both agree on being negative-free.
195func TestBloomHighBitVersions(t *testing.T) {
196 for _, ver := range []uint32{1, 2} {
197 t.Run(fmt.Sprintf("v%d", ver), func(t *testing.T) {
198 r := newGTRepo(t)
199 for i := range 30 {
200 p := fmt.Sprintf("d\xe9\xff%d/\xc3\xa9\xfe%d.txt", i, i)
201 r.commit(p, "x\n")
202 }
203 r.git("-c", fmt.Sprintf("commitGraph.changedPathsVersion=%d", ver),
204 "commit-graph", "write", "--reachable", "--changed-paths")
205 g, err := openCommitGraph(r.objects())
206 if err != nil {
207 t.Fatal(err)
208 }
209 defer func() { _ = g.close() }()
210 cs := gitCommits(t, r.dir)
211 wrong := 0
212 for _, cm := range cs {
213 pos, _ := g.lookup(cm.id)
214 for _, p := range changedPaths(t, r.dir, &cm) {
215 for _, k := range bloomPaths(p) {
216 if maybe, ok := g.maybeChanged(pos, []byte(k)); !ok || !maybe {
217 t.Fatalf("v%d: %q not found (maybe=%v ok=%v)", ver, k, maybe, ok)
218 }
219 // Probe with the other version's hash.
220 key := newBloomKey([]byte(k))
221 other := key
222 other.v1, other.v2 = key.v2, key.v1
223 // A v1 layer tries both hashes: test one only.
224 other.high = false
225 if maybe, ok := g.maybeChangedKey(pos, &other); ok && !maybe {
226 wrong++
227 }
228 }
229 }
230 }
231 if wrong == 0 {
232 t.Errorf("using the other hash version never failed: v%d not distinguished", ver)
233 }
234 })
235 }
236}
237
238// ---- synthetic filters ----------------------------------------------------
239
240// synthBloom builds a graph with the given filters (nil entry: empty).
241func synthBloom(t testing.TB, version, hashes, bitsPer uint32, filters [][]byte) *commitGraph {
242 n := len(filters)
243 s := &synthLayer{ids: synthIDs(n)}
244 hdr := binary.BigEndian.AppendUint32(nil, version)
245 hdr = binary.BigEndian.AppendUint32(hdr, hashes)
246 hdr = binary.BigEndian.AppendUint32(hdr, bitsPer)
247 var total uint32
248 s.bdat = hdr
249 for _, f := range filters {
250 total += uint32(len(f))
251 s.bidx = append(s.bidx, total)
252 s.bdat = append(s.bdat, f...)
253 }
254 return mustParseSynth(t, s.bytes())
255}
256
257// setBloomBits sets the bits of path in filter f.
258func setBloomBits(f []byte, hashes uint32, k bloomKey, v1 bool) {
259 h := k.v2
260 if v1 {
261 h = k.v1
262 }
263 for i := uint32(0); i < hashes; i++ {
264 bit := uint64(h[0]+i*h[1]) % uint64(len(f)*8)
265 f[bit>>3] |= 1 << (bit & 7)
266 }
267}
268
269func TestBloomSynthetic(t *testing.T) {
270 const hashes = 7
271 f := make([]byte, 16)
272 setBloomBits(f, hashes, newBloomKey([]byte("a/b/c.go")), false)
273 setBloomBits(f, hashes, newBloomKey([]byte("a/b")), false)
274 setBloomBits(f, hashes, newBloomKey([]byte("a")), false)
275 filters := [][]byte{
276 f,
277 {0x00}, // nothing changed
278 {0xff}, // too many changes
279 nil, // no data
280 f[:8], // different size: still a valid filter
281 {0x01, 0x02}, // random garbage filter
282 }
283 g := synthBloom(t, 2, hashes, 10, filters)
284 defer func() { _ = g.close() }()
285 if maybe, ok := g.maybeChanged(0, []byte("a/b/c.go")); !maybe || !ok {
286 t.Errorf("filter 0: %v %v", maybe, ok)
287 }
288 if maybe, ok := g.maybeChanged(0, []byte("zzz")); maybe || !ok {
289 t.Errorf("filter 0 unrelated: %v %v", maybe, ok)
290 }
291 if maybe, ok := g.maybeChanged(1, []byte("a")); maybe || !ok {
292 t.Errorf("zero filter: %v %v", maybe, ok)
293 }
294 if _, ok := g.maybeChanged(2, []byte("a")); ok {
295 t.Error("0xff filter must be unknown")
296 }
297 if _, ok := g.maybeChanged(3, []byte("a")); ok {
298 t.Error("empty filter must be unknown")
299 }
300 if _, ok := g.maybeChanged(g.numCommits(), []byte("a")); ok {
301 t.Error("bad position must be unknown")
302 }
303 if g.hasBloom(2) || !g.hasBloom(1) {
304 t.Error("hasBloom")
305 }
306}
307
308func TestBloomTruncated(t *testing.T) {
309 // BIDX claims more bytes than BDAT holds: unknown, no panic.
310 s := &synthLayer{ids: synthIDs(3)}
311 hdr := binary.BigEndian.AppendUint32(nil, 2)
312 hdr = binary.BigEndian.AppendUint32(hdr, 7)
313 hdr = binary.BigEndian.AppendUint32(hdr, 10)
314 s.bdat = append(hdr, 1, 2, 3, 4)
315 s.bidx = []uint32{4, 4000, 0xffffffff}
316 g := mustParseSynth(t, s.bytes())
317 defer func() { _ = g.close() }()
318 for pos := range uint32(3) {
319 if _, ok := g.maybeChanged(pos, []byte("x")); pos > 0 && ok {
320 t.Errorf("pos %d: truncated filter reported known", pos)
321 }
322 }
323 // Non-monotonic offsets.
324 s.bidx = []uint32{4, 2, 3}
325 g2 := mustParseSynth(t, s.bytes())
326 for pos := range uint32(3) {
327 g2.maybeChanged(pos, []byte("x"))
328 }
329}
330
331func TestBloomIgnoredSettings(t *testing.T) {
332 for _, c := range []struct{ version, hashes uint32 }{{3, 7}, {0, 7}, {2, 0}, {2, bloomMaxHashes + 1}, {2, 1 << 31}} {
333 g := synthBloom(t, c.version, c.hashes, 10, [][]byte{{0x00}, {0x00}})
334 if g.hasBloom(0) {
335 t.Errorf("version %d hashes %d should be ignored", c.version, c.hashes)
336 }
337 if _, ok := g.maybeChanged(0, []byte("a")); ok {
338 t.Errorf("version %d hashes %d should be unknown", c.version, c.hashes)
339 }
340 }
341}
342
343// A wrongly sized BIDX or a BDAT shorter than its header disables the Bloom
344// filters of the layer only, like git; the rest of the layer stays usable.
345func TestBloomBadChunkDisablesFeature(t *testing.T) {
346 hdr := binary.BigEndian.AppendUint32(nil, 2)
347 hdr = binary.BigEndian.AppendUint32(hdr, 7)
348 hdr = binary.BigEndian.AppendUint32(hdr, 10)
349 for name, s := range map[string]*synthLayer{
350 "short BDAT": {ids: synthIDs(2), bidx: []uint32{1, 2}, bdat: []byte{0, 0, 0, 2}},
351 "empty BDAT": {ids: synthIDs(2), bidx: []uint32{1, 2}, bdat: []byte{}},
352 "BIDX too few": {ids: synthIDs(3), bidx: []uint32{1, 2}, bdat: append(hdr[:12:12], 0, 0)},
353 "BIDX too many": {ids: synthIDs(2), bidx: []uint32{1, 2, 2}, bdat: append(hdr[:12:12], 0, 0)},
354 } {
355 t.Run(name, func(t *testing.T) {
356 g := mustParseSynth(t, s.bytes())
357 defer func() { _ = g.close() }()
358 if g.layers[0].hasBloom {
359 t.Fatal("hasBloom")
360 }
361 for pos := range g.numCommits() {
362 if g.hasBloom(pos) {
363 t.Errorf("pos %d: hasBloom", pos)
364 }
365 if _, ok := g.maybeChanged(pos, []byte("a")); ok {
366 t.Errorf("pos %d: answer without filter", pos)
367 }
368 id, err := g.commitID(pos)
369 if err != nil {
370 t.Fatal(err)
371 }
372 if got, ok := g.lookup(id); !ok || got != pos {
373 t.Errorf("lookup(%d) = %d, %v", pos, got, ok)
374 }
375 }
376 })
377 }
378}
379
380// A v1 filter written where char is unsigned (Linux arm64, ppc64, s390x) holds
381// the same bits as a v2 one. It must be found as well as one written with
382// signed chars.
383func TestBloomV1UnsignedWriter(t *testing.T) {
384 const hashes = 7
385 path := []byte("d\xe9\xff/\xc3\xa9.txt")
386 k := newBloomKey(path)
387 if !k.high || k.v1 == k.v2 {
388 t.Fatal("test path does not distinguish the hashes")
389 }
390 signed := make([]byte, 64)
391 setBloomBits(signed, hashes, k, true)
392 unsigned := make([]byte, 64)
393 setBloomBits(unsigned, hashes, k, false)
394 other := make([]byte, 64)
395 setBloomBits(other, hashes, newBloomKey([]byte("zz/other")), false)
396 g := synthBloom(t, 1, hashes, 10, [][]byte{signed, unsigned, other})
397 defer func() { _ = g.close() }()
398 for pos, want := range []bool{true, true, false} {
399 if maybe, ok := g.maybeChanged(uint32(pos), path); !ok || maybe != want {
400 t.Errorf("v1 filter %d: maybe=%v ok=%v, want %v", pos, maybe, ok, want)
401 }
402 }
403 // A v2 layer must not accept the signed hash.
404 g2 := synthBloom(t, 2, hashes, 10, [][]byte{signed, unsigned})
405 defer func() { _ = g2.close() }()
406 if maybe, _ := g2.maybeChanged(0, path); maybe {
407 t.Error("v2 layer matched a signed-char filter")
408 }
409 if maybe, _ := g2.maybeChanged(1, path); !maybe {
410 t.Error("v2 layer missed an unsigned filter")
411 }
412}
413
414// Keys git never inserts are unknown, not "unchanged".
415func TestBloomUnusableKeys(t *testing.T) {
416 const hashes = 7
417 f := make([]byte, 64)
418 for _, p := range []string{"a/b", "a", ".hidden", "..x", "a/.b"} {
419 setBloomBits(f, hashes, newBloomKey([]byte(p)), false)
420 }
421 g := synthBloom(t, 2, hashes, 10, [][]byte{f, {0x00}})
422 defer func() { _ = g.close() }()
423
424 for _, p := range []string{"", "/", "//", "/a", "/a/b", "a//b", "a/b//", "./a", "a/./b", "a/.", ".", "..",
425 "../a", "a/../b", "a/..", "a\x00b"} {
426 for pos := range uint32(2) {
427 if maybe, ok := g.maybeChanged(pos, []byte(p)); ok || maybe {
428 t.Errorf("%q at %d: maybe=%v ok=%v, want unknown", p, pos, maybe, ok)
429 }
430 }
431 if k := newBloomKey([]byte(p)); k.usable {
432 t.Errorf("%q: key usable", p)
433 }
434 }
435 // One trailing slash is dropped, like git does.
436 for _, p := range []string{"a/b", "a/b/", "a", "a/", ".hidden", "..x", "a/.b/"} {
437 if maybe, ok := g.maybeChanged(0, []byte(p)); !ok || !maybe {
438 t.Errorf("%q: maybe=%v ok=%v, want found", p, maybe, ok)
439 }
440 if maybe, ok := g.maybeChanged(1, []byte(p)); !ok || maybe {
441 t.Errorf("%q in empty filter: maybe=%v ok=%v", p, maybe, ok)
442 }
443 }
444 if newBloomKey([]byte("a/b/")) != newBloomKey([]byte("a/b")) {
445 t.Error("trailing slash changes the key")
446 }
447 var zero bloomKey
448 if _, ok := g.maybeChangedKey(0, &zero); ok {
449 t.Error("zero key must be unknown")
450 }
451}
452
453// ---- allocation and fuzz --------------------------------------------------
454
455func TestBloomNoAllocs(t *testing.T) {
456 const hashes = 7
457 f := make([]byte, 16)
458 setBloomBits(f, hashes, newBloomKey([]byte("a/b")), false)
459 g := synthBloom(t, 2, hashes, 10, [][]byte{f, f})
460 path := []byte("a/b/ünï.go")
461 var sink bool
462 if n := testing.AllocsPerRun(100, func() {
463 k := newBloomKey(path)
464 m, _ := g.maybeChangedKey(0, &k)
465 m2, _ := g.maybeChanged(1, path)
466 sink = sink || m || m2
467 }); n != 0 {
468 t.Errorf("allocs = %v", n)
469 }
470 _ = sink
471}
472
473func FuzzBloomLookup(f *testing.F) {
474 f.Add([]byte{0x00}, []byte("a"), uint32(2), uint32(7))
475 f.Add([]byte{0xff}, []byte("a/b"), uint32(1), uint32(7))
476 f.Add([]byte{0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0}, []byte("caf\xc3\xa9/x"), uint32(1), uint32(3))
477 f.Add([]byte{}, []byte{}, uint32(2), uint32(7))
478 f.Add([]byte{0x80, 0x01}, []byte("\xff\xfe\xfd\xfc\xfb"), uint32(9), uint32(1<<31))
479 f.Fuzz(func(t *testing.T, filter, path []byte, version, hashes uint32) {
480 hdr := binary.BigEndian.AppendUint32(nil, version)
481 hdr = binary.BigEndian.AppendUint32(hdr, hashes)
482 hdr = binary.BigEndian.AppendUint32(hdr, 10)
483 s := &synthLayer{ids: synthIDs(2)}
484 s.bdat = append(hdr, filter...)
485 // Second filter claims the rest; the first is cut anywhere.
486 s.bidx = []uint32{uint32(len(filter) / 2), uint32(len(filter))}
487 l, err := parseGraphLayer(s.bytes())
488 if err != nil {
489 return
490 }
491 g := &commitGraph{layers: []graphLayer{*l}, total: l.n}
492 k := newBloomKey(path)
493 for pos := range uint32(3) {
494 maybe, ok := g.maybeChangedKey(pos, &k)
495 if maybe && !ok {
496 t.Fatal("maybe without ok")
497 }
498 if ok && !k.usable {
499 t.Fatal("answer for an unusable key")
500 }
501 }
502 if !k.usable {
503 return
504 }
505 // A path inserted into a valid filter is always found.
506 half := len(filter) / 2
507 if (version == 1 || version == 2) && hashes >= 1 && hashes <= bloomMaxHashes && len(filter)-half >= 1 {
508 second := append([]byte(nil), filter[half:]...)
509 setBloomBits(second, hashes, k, version == 1)
510 s.bdat = append(append(hdr[:12:12], filter[:half]...), second...)
511 l2, err := parseGraphLayer(s.bytes())
512 if err != nil {
513 t.Fatal(err)
514 }
515 g2 := &commitGraph{layers: []graphLayer{*l2}, total: l2.n}
516 if maybe, ok := g2.maybeChangedKey(1, &k); ok && !maybe {
517 t.Fatal("false negative after insertion")
518 }
519 if version == 1 {
520 // The same filter written with the unsigned hash.
521 third := append([]byte(nil), filter[half:]...)
522 setBloomBits(third, hashes, k, false)
523 s.bdat = append(append(hdr[:12:12], filter[:half]...), third...)
524 l3, err := parseGraphLayer(s.bytes())
525 if err != nil {
526 t.Fatal(err)
527 }
528 g3 := &commitGraph{layers: []graphLayer{*l3}, total: l3.n}
529 if maybe, ok := g3.maybeChangedKey(1, &k); ok && !maybe {
530 t.Fatal("false negative with an unsigned v1 writer")
531 }
532 }
533 }
534 })
535}
536
537// ---- benchmarks -----------------------------------------------------------
538
539func BenchmarkBloomMaybeChanged(b *testing.B) {
540 g, _ := benchGraph(b)
541 n := g.numCommits()
542 key := newBloomKey([]byte("pkg3/sub1/g1234.go"))
543 b.ReportAllocs()
544 var pos uint32
545 var hits int
546 for b.Loop() {
547 if maybe, ok := g.maybeChangedKey(pos, &key); ok && maybe {
548 hits++
549 }
550 if pos++; pos == n {
551 pos = 0
552 }
553 }
554 _ = hits
555}
556
557func BenchmarkBloomMaybeChangedPath(b *testing.B) {
558 g, _ := benchGraph(b)
559 n := g.numCommits()
560 path := []byte("pkg3/sub1/g1234.go")
561 b.ReportAllocs()
562 var pos uint32
563 for b.Loop() {
564 g.maybeChanged(pos, path)
565 if pos++; pos == n {
566 pos = 0
567 }
568 }
569}
570
571func BenchmarkBloomNewKey(b *testing.B) {
572 path := []byte("internal/adapters/gitcli/repos.go")
573 b.ReportAllocs()
574 for b.Loop() {
575 _ = newBloomKey(path)
576 }
577}
578
579// ---- real repository ------------------------------------------------------
580
581// TestGraphBenchRepo checks a large real repository (ERMITE_GIT_BENCH_REPO).
582// The repository is never modified: its objects are copied into a bare clone
583// where the split graph is written.
584func TestGraphBenchRepo(t *testing.T) {
585 src := os.Getenv("ERMITE_GIT_BENCH_REPO")
586 if src == "" {
587 t.Skip("ERMITE_GIT_BENCH_REPO not set")
588 }
589 requireGit(t)
590 for _, tc := range []struct {
591 ver uint32
592 multi bool
593 }{{2, false}, {1, false}, {2, true}, {1, true}} {
594 ver, multi := tc.ver, tc.multi
595 t.Run(fmt.Sprintf("bloom-v%d-multi=%v", ver, multi), func(t *testing.T) {
596 dst := filepath.Join(t.TempDir(), "clone.git")
597 graphGit(t, "", 0, "clone", "--bare", "--no-local", "-q", src, dst)
598 cfg := fmt.Sprintf("commitGraph.changedPathsVersion=%d", ver)
599 if multi {
600 // Several layers, like successive pushes would produce.
601 all := strings.Fields(graphGit(t, dst, 0, "rev-list", "--all"))
602 for _, back := range []int{5000, 2500, 500} {
603 tip := all[min(back, len(all)-1)]
604 graphGitStdin(t, dst, tip+"\n", "-c", cfg,
605 "commit-graph", "write", "--stdin-commits", "--changed-paths", "--split=no-merge")
606 }
607 graphGit(t, dst, 0, "-c", cfg, "commit-graph", "write", "--reachable", "--changed-paths", "--split=no-merge")
608 } else {
609 graphGit(t, dst, 0, "-c", cfg, "commit-graph", "write", "--reachable", "--changed-paths", "--split")
610 }
611 g, err := openCommitGraph(filepath.Join(dst, "objects"))
612 if err != nil {
613 t.Fatal(err)
614 }
615 defer func() { _ = g.close() }()
616 out := graphGit(t, dst, 0, "log", "--all", "--format=%H %T %P|%ct")
617 var cs []refCommit
618 for _, line := range strings.Split(strings.TrimSpace(out), "\n") {
619 left, ct, _ := strings.Cut(line, "|")
620 f := strings.Fields(left)
621 c := refCommit{id: graphTestHex(f[0]), tree: graphTestHex(f[1])}
622 for _, p := range f[2:] {
623 c.parents = append(c.parents, graphTestHex(p))
624 }
625 c.ctime, _ = strconv.ParseInt(ct, 10, 64)
626 cs = append(cs, c)
627 }
628 if int(g.numCommits()) != len(cs) {
629 t.Fatalf("numCommits = %d, git log has %d", g.numCommits(), len(cs))
630 }
631 t.Logf("%d commits, %d layers, generation v2 = %v", len(cs), g.numLayers(), g.hasGenerationV2())
632 if multi && g.numLayers() < 4 {
633 t.Fatalf("expected a multi-layer chain, got %d layers", g.numLayers())
634 }
635 var buf [16]uint32
636 for i := range cs {
637 c := &cs[i]
638 pos, ok := g.lookup(c.id)
639 if !ok {
640 t.Fatalf("lookup(%x)", c.id)
641 }
642 if id, _ := g.commitID(pos); id != c.id {
643 t.Fatalf("commitID(%d)", pos)
644 }
645 if tr, _ := g.rootTree(pos); tr != c.tree {
646 t.Fatalf("rootTree of %x = %x, want %x", c.id, tr, c.tree)
647 }
648 if ct, _ := g.commitTime(pos); ct != c.ctime {
649 t.Fatalf("commitTime of %x = %d, want %d", c.id, ct, c.ctime)
650 }
651 ps, err := g.appendParents(buf[:0], pos)
652 if err != nil || len(ps) != len(c.parents) {
653 t.Fatalf("parents of %x: %v, %v; want %d", c.id, ps, err, len(c.parents))
654 }
655 for j, p := range ps {
656 if pid, _ := g.commitID(p); pid != c.parents[j] {
657 t.Fatalf("parent %d of %x", j, c.id)
658 }
659 }
660 gen, err := g.generation(pos)
661 if err != nil {
662 t.Fatal(err)
663 }
664 for _, p := range ps {
665 if pg, _ := g.generation(p); pg >= gen {
666 t.Fatalf("generation(%x) = %d not above parent %d", c.id, gen, pg)
667 }
668 }
669 }
670 checkBloomSample(t, dst, g, cs, true, ver, 25)
671 })
672 }
673}