Merge branch 'ma/asciidoctor-fixes'
[git] / t / t5318-commit-graph.sh
1 #!/bin/sh
2
3 test_description='commit graph'
4 . ./test-lib.sh
5
6 test_expect_success 'setup full repo' '
7         mkdir full &&
8         cd "$TRASH_DIRECTORY/full" &&
9         git init &&
10         git config core.commitGraph true &&
11         objdir=".git/objects" &&
12         test_oid_init
13 '
14
15 test_expect_success 'verify graph with no graph file' '
16         cd "$TRASH_DIRECTORY/full" &&
17         git commit-graph verify
18 '
19
20 test_expect_success 'write graph with no packs' '
21         cd "$TRASH_DIRECTORY/full" &&
22         git commit-graph write --object-dir . &&
23         test_path_is_file info/commit-graph
24 '
25
26 test_expect_success 'create commits and repack' '
27         cd "$TRASH_DIRECTORY/full" &&
28         for i in $(test_seq 3)
29         do
30                 test_commit $i &&
31                 git branch commits/$i
32         done &&
33         git repack
34 '
35
36 graph_git_two_modes() {
37         git -c core.commitGraph=true $1 >output
38         git -c core.commitGraph=false $1 >expect
39         test_cmp expect output
40 }
41
42 graph_git_behavior() {
43         MSG=$1
44         DIR=$2
45         BRANCH=$3
46         COMPARE=$4
47         test_expect_success "check normal git operations: $MSG" '
48                 cd "$TRASH_DIRECTORY/$DIR" &&
49                 graph_git_two_modes "log --oneline $BRANCH" &&
50                 graph_git_two_modes "log --topo-order $BRANCH" &&
51                 graph_git_two_modes "log --graph $COMPARE..$BRANCH" &&
52                 graph_git_two_modes "branch -vv" &&
53                 graph_git_two_modes "merge-base -a $BRANCH $COMPARE"
54         '
55 }
56
57 graph_git_behavior 'no graph' full commits/3 commits/1
58
59 graph_read_expect() {
60         OPTIONAL=""
61         NUM_CHUNKS=3
62         if test ! -z $2
63         then
64                 OPTIONAL=" $2"
65                 NUM_CHUNKS=$((3 + $(echo "$2" | wc -w)))
66         fi
67         cat >expect <<- EOF
68         header: 43475048 1 1 $NUM_CHUNKS 0
69         num_commits: $1
70         chunks: oid_fanout oid_lookup commit_metadata$OPTIONAL
71         EOF
72         git commit-graph read >output &&
73         test_cmp expect output
74 }
75
76 test_expect_success 'write graph' '
77         cd "$TRASH_DIRECTORY/full" &&
78         graph1=$(git commit-graph write) &&
79         test_path_is_file $objdir/info/commit-graph &&
80         graph_read_expect "3"
81 '
82
83 graph_git_behavior 'graph exists' full commits/3 commits/1
84
85 test_expect_success 'Add more commits' '
86         cd "$TRASH_DIRECTORY/full" &&
87         git reset --hard commits/1 &&
88         for i in $(test_seq 4 5)
89         do
90                 test_commit $i &&
91                 git branch commits/$i
92         done &&
93         git reset --hard commits/2 &&
94         for i in $(test_seq 6 7)
95         do
96                 test_commit $i &&
97                 git branch commits/$i
98         done &&
99         git reset --hard commits/2 &&
100         git merge commits/4 &&
101         git branch merge/1 &&
102         git reset --hard commits/4 &&
103         git merge commits/6 &&
104         git branch merge/2 &&
105         git reset --hard commits/3 &&
106         git merge commits/5 commits/7 &&
107         git branch merge/3 &&
108         git repack
109 '
110
111 # Current graph structure:
112 #
113 #   __M3___
114 #  /   |   \
115 # 3 M1 5 M2 7
116 # |/  \|/  \|
117 # 2    4    6
118 # |___/____/
119 # 1
120
121 test_expect_success 'write graph with merges' '
122         cd "$TRASH_DIRECTORY/full" &&
123         git commit-graph write &&
124         test_path_is_file $objdir/info/commit-graph &&
125         graph_read_expect "10" "extra_edges"
126 '
127
128 graph_git_behavior 'merge 1 vs 2' full merge/1 merge/2
129 graph_git_behavior 'merge 1 vs 3' full merge/1 merge/3
130 graph_git_behavior 'merge 2 vs 3' full merge/2 merge/3
131
132 test_expect_success 'Add one more commit' '
133         cd "$TRASH_DIRECTORY/full" &&
134         test_commit 8 &&
135         git branch commits/8 &&
136         ls $objdir/pack | grep idx >existing-idx &&
137         git repack &&
138         ls $objdir/pack| grep idx | grep -v -f existing-idx >new-idx
139 '
140
141 # Current graph structure:
142 #
143 #      8
144 #      |
145 #   __M3___
146 #  /   |   \
147 # 3 M1 5 M2 7
148 # |/  \|/  \|
149 # 2    4    6
150 # |___/____/
151 # 1
152
153 graph_git_behavior 'mixed mode, commit 8 vs merge 1' full commits/8 merge/1
154 graph_git_behavior 'mixed mode, commit 8 vs merge 2' full commits/8 merge/2
155
156 test_expect_success 'write graph with new commit' '
157         cd "$TRASH_DIRECTORY/full" &&
158         git commit-graph write &&
159         test_path_is_file $objdir/info/commit-graph &&
160         graph_read_expect "11" "extra_edges"
161 '
162
163 graph_git_behavior 'full graph, commit 8 vs merge 1' full commits/8 merge/1
164 graph_git_behavior 'full graph, commit 8 vs merge 2' full commits/8 merge/2
165
166 test_expect_success 'write graph with nothing new' '
167         cd "$TRASH_DIRECTORY/full" &&
168         git commit-graph write &&
169         test_path_is_file $objdir/info/commit-graph &&
170         graph_read_expect "11" "extra_edges"
171 '
172
173 graph_git_behavior 'cleared graph, commit 8 vs merge 1' full commits/8 merge/1
174 graph_git_behavior 'cleared graph, commit 8 vs merge 2' full commits/8 merge/2
175
176 test_expect_success 'build graph from latest pack with closure' '
177         cd "$TRASH_DIRECTORY/full" &&
178         cat new-idx | git commit-graph write --stdin-packs &&
179         test_path_is_file $objdir/info/commit-graph &&
180         graph_read_expect "9" "extra_edges"
181 '
182
183 graph_git_behavior 'graph from pack, commit 8 vs merge 1' full commits/8 merge/1
184 graph_git_behavior 'graph from pack, commit 8 vs merge 2' full commits/8 merge/2
185
186 test_expect_success 'build graph from commits with closure' '
187         cd "$TRASH_DIRECTORY/full" &&
188         git tag -a -m "merge" tag/merge merge/2 &&
189         git rev-parse tag/merge >commits-in &&
190         git rev-parse merge/1 >>commits-in &&
191         cat commits-in | git commit-graph write --stdin-commits &&
192         test_path_is_file $objdir/info/commit-graph &&
193         graph_read_expect "6"
194 '
195
196 graph_git_behavior 'graph from commits, commit 8 vs merge 1' full commits/8 merge/1
197 graph_git_behavior 'graph from commits, commit 8 vs merge 2' full commits/8 merge/2
198
199 test_expect_success 'build graph from commits with append' '
200         cd "$TRASH_DIRECTORY/full" &&
201         git rev-parse merge/3 | git commit-graph write --stdin-commits --append &&
202         test_path_is_file $objdir/info/commit-graph &&
203         graph_read_expect "10" "extra_edges"
204 '
205
206 graph_git_behavior 'append graph, commit 8 vs merge 1' full commits/8 merge/1
207 graph_git_behavior 'append graph, commit 8 vs merge 2' full commits/8 merge/2
208
209 test_expect_success 'build graph using --reachable' '
210         cd "$TRASH_DIRECTORY/full" &&
211         git commit-graph write --reachable &&
212         test_path_is_file $objdir/info/commit-graph &&
213         graph_read_expect "11" "extra_edges"
214 '
215
216 graph_git_behavior 'append graph, commit 8 vs merge 1' full commits/8 merge/1
217 graph_git_behavior 'append graph, commit 8 vs merge 2' full commits/8 merge/2
218
219 test_expect_success 'setup bare repo' '
220         cd "$TRASH_DIRECTORY" &&
221         git clone --bare --no-local full bare &&
222         cd bare &&
223         git config core.commitGraph true &&
224         baredir="./objects"
225 '
226
227 graph_git_behavior 'bare repo, commit 8 vs merge 1' bare commits/8 merge/1
228 graph_git_behavior 'bare repo, commit 8 vs merge 2' bare commits/8 merge/2
229
230 test_expect_success 'write graph in bare repo' '
231         cd "$TRASH_DIRECTORY/bare" &&
232         git commit-graph write &&
233         test_path_is_file $baredir/info/commit-graph &&
234         graph_read_expect "11" "extra_edges"
235 '
236
237 graph_git_behavior 'bare repo with graph, commit 8 vs merge 1' bare commits/8 merge/1
238 graph_git_behavior 'bare repo with graph, commit 8 vs merge 2' bare commits/8 merge/2
239
240 test_expect_success 'perform fast-forward merge in full repo' '
241         cd "$TRASH_DIRECTORY/full" &&
242         git checkout -b merge-5-to-8 commits/5 &&
243         git merge commits/8 &&
244         git show-ref -s merge-5-to-8 >output &&
245         git show-ref -s commits/8 >expect &&
246         test_cmp expect output
247 '
248
249 test_expect_success 'check that gc computes commit-graph' '
250         cd "$TRASH_DIRECTORY/full" &&
251         git commit --allow-empty -m "blank" &&
252         git commit-graph write --reachable &&
253         cp $objdir/info/commit-graph commit-graph-before-gc &&
254         git reset --hard HEAD~1 &&
255         git config gc.writeCommitGraph true &&
256         git gc &&
257         cp $objdir/info/commit-graph commit-graph-after-gc &&
258         ! test_cmp_bin commit-graph-before-gc commit-graph-after-gc &&
259         git commit-graph write --reachable &&
260         test_cmp_bin commit-graph-after-gc $objdir/info/commit-graph
261 '
262
263 test_expect_success 'replace-objects invalidates commit-graph' '
264         cd "$TRASH_DIRECTORY" &&
265         test_when_finished rm -rf replace &&
266         git clone full replace &&
267         (
268                 cd replace &&
269                 git commit-graph write --reachable &&
270                 test_path_is_file .git/objects/info/commit-graph &&
271                 git replace HEAD~1 HEAD~2 &&
272                 git -c core.commitGraph=false log >expect &&
273                 git -c core.commitGraph=true log >actual &&
274                 test_cmp expect actual &&
275                 git commit-graph write --reachable &&
276                 git -c core.commitGraph=false --no-replace-objects log >expect &&
277                 git -c core.commitGraph=true --no-replace-objects log >actual &&
278                 test_cmp expect actual &&
279                 rm -rf .git/objects/info/commit-graph &&
280                 git commit-graph write --reachable &&
281                 test_path_is_file .git/objects/info/commit-graph
282         )
283 '
284
285 test_expect_success 'commit grafts invalidate commit-graph' '
286         cd "$TRASH_DIRECTORY" &&
287         test_when_finished rm -rf graft &&
288         git clone full graft &&
289         (
290                 cd graft &&
291                 git commit-graph write --reachable &&
292                 test_path_is_file .git/objects/info/commit-graph &&
293                 H1=$(git rev-parse --verify HEAD~1) &&
294                 H3=$(git rev-parse --verify HEAD~3) &&
295                 echo "$H1 $H3" >.git/info/grafts &&
296                 git -c core.commitGraph=false log >expect &&
297                 git -c core.commitGraph=true log >actual &&
298                 test_cmp expect actual &&
299                 git commit-graph write --reachable &&
300                 git -c core.commitGraph=false --no-replace-objects log >expect &&
301                 git -c core.commitGraph=true --no-replace-objects log >actual &&
302                 test_cmp expect actual &&
303                 rm -rf .git/objects/info/commit-graph &&
304                 git commit-graph write --reachable &&
305                 test_path_is_missing .git/objects/info/commit-graph
306         )
307 '
308
309 test_expect_success 'replace-objects invalidates commit-graph' '
310         cd "$TRASH_DIRECTORY" &&
311         test_when_finished rm -rf shallow &&
312         git clone --depth 2 "file://$TRASH_DIRECTORY/full" shallow &&
313         (
314                 cd shallow &&
315                 git commit-graph write --reachable &&
316                 test_path_is_missing .git/objects/info/commit-graph &&
317                 git fetch origin --unshallow &&
318                 git commit-graph write --reachable &&
319                 test_path_is_file .git/objects/info/commit-graph
320         )
321 '
322
323 # the verify tests below expect the commit-graph to contain
324 # exactly the commits reachable from the commits/8 branch.
325 # If the file changes the set of commits in the list, then the
326 # offsets into the binary file will result in different edits
327 # and the tests will likely break.
328
329 test_expect_success 'git commit-graph verify' '
330         cd "$TRASH_DIRECTORY/full" &&
331         git rev-parse commits/8 | git commit-graph write --stdin-commits &&
332         git commit-graph verify >output
333 '
334
335 NUM_COMMITS=9
336 NUM_OCTOPUS_EDGES=2
337 HASH_LEN="$(test_oid rawsz)"
338 GRAPH_BYTE_VERSION=4
339 GRAPH_BYTE_HASH=5
340 GRAPH_BYTE_CHUNK_COUNT=6
341 GRAPH_CHUNK_LOOKUP_OFFSET=8
342 GRAPH_CHUNK_LOOKUP_WIDTH=12
343 GRAPH_CHUNK_LOOKUP_ROWS=5
344 GRAPH_BYTE_OID_FANOUT_ID=$GRAPH_CHUNK_LOOKUP_OFFSET
345 GRAPH_BYTE_OID_LOOKUP_ID=$(($GRAPH_CHUNK_LOOKUP_OFFSET + \
346                             1 * $GRAPH_CHUNK_LOOKUP_WIDTH))
347 GRAPH_BYTE_COMMIT_DATA_ID=$(($GRAPH_CHUNK_LOOKUP_OFFSET + \
348                              2 * $GRAPH_CHUNK_LOOKUP_WIDTH))
349 GRAPH_FANOUT_OFFSET=$(($GRAPH_CHUNK_LOOKUP_OFFSET + \
350                        $GRAPH_CHUNK_LOOKUP_WIDTH * $GRAPH_CHUNK_LOOKUP_ROWS))
351 GRAPH_BYTE_FANOUT1=$(($GRAPH_FANOUT_OFFSET + 4 * 4))
352 GRAPH_BYTE_FANOUT2=$(($GRAPH_FANOUT_OFFSET + 4 * 255))
353 GRAPH_OID_LOOKUP_OFFSET=$(($GRAPH_FANOUT_OFFSET + 4 * 256))
354 GRAPH_BYTE_OID_LOOKUP_ORDER=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN * 8))
355 GRAPH_BYTE_OID_LOOKUP_MISSING=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN * 4 + 10))
356 GRAPH_COMMIT_DATA_OFFSET=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN * $NUM_COMMITS))
357 GRAPH_BYTE_COMMIT_TREE=$GRAPH_COMMIT_DATA_OFFSET
358 GRAPH_BYTE_COMMIT_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN))
359 GRAPH_BYTE_COMMIT_EXTRA_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 4))
360 GRAPH_BYTE_COMMIT_WRONG_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 3))
361 GRAPH_BYTE_COMMIT_GENERATION=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 11))
362 GRAPH_BYTE_COMMIT_DATE=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 12))
363 GRAPH_COMMIT_DATA_WIDTH=$(($HASH_LEN + 16))
364 GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
365                              $GRAPH_COMMIT_DATA_WIDTH * $NUM_COMMITS))
366 GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
367 GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES))
368
369 # usage: corrupt_graph_and_verify <position> <data> <string> [<zero_pos>]
370 # Manipulates the commit-graph file at the position
371 # by inserting the data, optionally zeroing the file
372 # starting at <zero_pos>, then runs 'git commit-graph verify'
373 # and places the output in the file 'err'. Test 'err' for
374 # the given string.
375 corrupt_graph_and_verify() {
376         pos=$1
377         data="${2:-\0}"
378         grepstr=$3
379         cd "$TRASH_DIRECTORY/full" &&
380         orig_size=$(wc -c < $objdir/info/commit-graph) &&
381         zero_pos=${4:-${orig_size}} &&
382         test_when_finished mv commit-graph-backup $objdir/info/commit-graph &&
383         cp $objdir/info/commit-graph commit-graph-backup &&
384         printf "$data" | dd of="$objdir/info/commit-graph" bs=1 seek="$pos" conv=notrunc &&
385         dd of="$objdir/info/commit-graph" bs=1 seek="$zero_pos" if=/dev/null &&
386         generate_zero_bytes $(($orig_size - $zero_pos)) >>"$objdir/info/commit-graph" &&
387         test_must_fail git commit-graph verify 2>test_err &&
388         grep -v "^+" test_err >err &&
389         test_i18ngrep "$grepstr" err
390 }
391
392 test_expect_success 'detect bad signature' '
393         corrupt_graph_and_verify 0 "\0" \
394                 "graph signature"
395 '
396
397 test_expect_success 'detect bad version' '
398         corrupt_graph_and_verify $GRAPH_BYTE_VERSION "\02" \
399                 "graph version"
400 '
401
402 test_expect_success 'detect bad hash version' '
403         corrupt_graph_and_verify $GRAPH_BYTE_HASH "\02" \
404                 "hash version"
405 '
406
407 test_expect_success 'detect low chunk count' '
408         corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\02" \
409                 "missing the .* chunk"
410 '
411
412 test_expect_success 'detect missing OID fanout chunk' '
413         corrupt_graph_and_verify $GRAPH_BYTE_OID_FANOUT_ID "\0" \
414                 "missing the OID Fanout chunk"
415 '
416
417 test_expect_success 'detect missing OID lookup chunk' '
418         corrupt_graph_and_verify $GRAPH_BYTE_OID_LOOKUP_ID "\0" \
419                 "missing the OID Lookup chunk"
420 '
421
422 test_expect_success 'detect missing commit data chunk' '
423         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_DATA_ID "\0" \
424                 "missing the Commit Data chunk"
425 '
426
427 test_expect_success 'detect incorrect fanout' '
428         corrupt_graph_and_verify $GRAPH_BYTE_FANOUT1 "\01" \
429                 "fanout value"
430 '
431
432 test_expect_success 'detect incorrect fanout final value' '
433         corrupt_graph_and_verify $GRAPH_BYTE_FANOUT2 "\01" \
434                 "fanout value"
435 '
436
437 test_expect_success 'detect incorrect OID order' '
438         corrupt_graph_and_verify $GRAPH_BYTE_OID_LOOKUP_ORDER "\01" \
439                 "incorrect OID order"
440 '
441
442 test_expect_success 'detect OID not in object database' '
443         corrupt_graph_and_verify $GRAPH_BYTE_OID_LOOKUP_MISSING "\01" \
444                 "from object database"
445 '
446
447 test_expect_success 'detect incorrect tree OID' '
448         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_TREE "\01" \
449                 "root tree OID for commit"
450 '
451
452 test_expect_success 'detect incorrect parent int-id' '
453         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_PARENT "\01" \
454                 "invalid parent"
455 '
456
457 test_expect_success 'detect extra parent int-id' '
458         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_EXTRA_PARENT "\00" \
459                 "is too long"
460 '
461
462 test_expect_success 'detect wrong parent' '
463         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_WRONG_PARENT "\01" \
464                 "commit-graph parent for"
465 '
466
467 test_expect_success 'detect incorrect generation number' '
468         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\070" \
469                 "generation for commit"
470 '
471
472 test_expect_success 'detect incorrect generation number' '
473         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\01" \
474                 "non-zero generation number"
475 '
476
477 test_expect_success 'detect incorrect commit date' '
478         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_DATE "\01" \
479                 "commit date"
480 '
481
482 test_expect_success 'detect incorrect parent for octopus merge' '
483         corrupt_graph_and_verify $GRAPH_BYTE_OCTOPUS "\01" \
484                 "invalid parent"
485 '
486
487 test_expect_success 'detect invalid checksum hash' '
488         corrupt_graph_and_verify $GRAPH_BYTE_FOOTER "\00" \
489                 "incorrect checksum"
490 '
491
492 test_expect_success 'detect incorrect chunk count' '
493         corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\377" \
494                 "chunk lookup table entry missing" $GRAPH_CHUNK_LOOKUP_OFFSET
495 '
496
497 test_expect_success 'git fsck (checks commit-graph)' '
498         cd "$TRASH_DIRECTORY/full" &&
499         git fsck &&
500         corrupt_graph_and_verify $GRAPH_BYTE_FOOTER "\00" \
501                 "incorrect checksum" &&
502         test_must_fail git fsck
503 '
504
505 test_expect_success 'setup non-the_repository tests' '
506         rm -rf repo &&
507         git init repo &&
508         test_commit -C repo one &&
509         test_commit -C repo two &&
510         git -C repo config core.commitGraph true &&
511         git -C repo rev-parse two | \
512                 git -C repo commit-graph write --stdin-commits
513 '
514
515 test_expect_success 'parse_commit_in_graph works for non-the_repository' '
516         test-tool repository parse_commit_in_graph \
517                 repo/.git repo "$(git -C repo rev-parse two)" >actual &&
518         {
519                 git -C repo log --pretty=format:"%ct " -1 &&
520                 git -C repo rev-parse one
521         } >expect &&
522         test_cmp expect actual &&
523
524         test-tool repository parse_commit_in_graph \
525                 repo/.git repo "$(git -C repo rev-parse one)" >actual &&
526         git -C repo log --pretty="%ct" -1 one >expect &&
527         test_cmp expect actual
528 '
529
530 test_expect_success 'get_commit_tree_in_graph works for non-the_repository' '
531         test-tool repository get_commit_tree_in_graph \
532                 repo/.git repo "$(git -C repo rev-parse two)" >actual &&
533         git -C repo rev-parse two^{tree} >expect &&
534         test_cmp expect actual &&
535
536         test-tool repository get_commit_tree_in_graph \
537                 repo/.git repo "$(git -C repo rev-parse one)" >actual &&
538         git -C repo rev-parse one^{tree} >expect &&
539         test_cmp expect actual
540 '
541
542 test_done