@leroysheep / Socializer
Code Commits Pulls CI/CD 81,972
jch
bisect jch maint master next seen test todo
sh 1,011 lines 24.5 KB
Raw
1 #!/bin/sh
2
3 test_description='basic commit reachability tests'
4
5 . ./test-lib.sh
6
7 # Construct a grid-like commit graph with points (x,y)
8 # with 1 <= x <= 10, 1 <= y <= 10, where (x,y) has
9 # parents (x-1, y) and (x, y-1), keeping in mind that
10 # we drop a parent if a coordinate is nonpositive.
11 #
12 # (10,10)
13 # / \
14 # (10,9) (9,10)
15 # / \ / \
16 # (10,8) (9,9) (8,10)
17 # / \ / \ / \
18 # ( continued...)
19 # \ / \ / \ /
20 # (3,1) (2,2) (1,3)
21 # \ / \ /
22 # (2,1) (2,1)
23 # \ /
24 # (1,1)
25 #
26 # We use branch 'commit-x-y' to refer to (x,y).
27 # This grid allows interesting reachability and
28 # non-reachability queries: (x,y) can reach (x',y')
29 # if and only if x' <= x and y' <= y.
30 test_expect_success 'setup' '
31 for i in $(test_seq 1 10)
32 do
33 test_commit "1-$i" &&
34 git branch -f commit-1-$i &&
35 git tag -a -m "1-$i" tag-1-$i commit-1-$i || return 1
36 done &&
37 for j in $(test_seq 1 9)
38 do
39 git reset --hard commit-$j-1 &&
40 x=$(($j + 1)) &&
41 test_commit "$x-1" &&
42 git branch -f commit-$x-1 &&
43 git tag -a -m "$x-1" tag-$x-1 commit-$x-1 &&
44
45 for i in $(test_seq 2 10)
46 do
47 git merge commit-$j-$i -m "$x-$i" &&
48 git branch -f commit-$x-$i &&
49 git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i || return 1
50 done
51 done &&
52 # Build a topology with clock skew to test the !FIND_ALL early
53 # exit in paint_down_to_common(). M2 is the correct merge base
54 # of P1 and P2, but its ancestor M1 has a higher committer date
55 # due to clock skew. With date-only ordering (v1 commit graph
56 # without corrected commit dates), M1 pops from the queue first,
57 # gets both paint sides, and the early exit fires before M2 is
58 # ever visited.
59 #
60 # P1 P2 @7000
61 # | / \
62 # A B D @6000
63 # / \ | |
64 # | M2--+ | @2000 (correct merge base)
65 # \ | |
66 # M1--------+ @5000 (clock skew: date > M2)
67 # |
68 # root @1000
69 #
70 git checkout --orphan skew-orphan &&
71 skew_tree=$(git mktree </dev/null) &&
72 skew_commit () {
73 GIT_COMMITTER_DATE="@$1 +0000" GIT_AUTHOR_DATE="@$1 +0000" \
74 git commit-tree -m "$2" "$skew_tree" $3 $4 $5 $6
75 } &&
76 skew_root=$(skew_commit 1000 root) &&
77 skew_M1=$(skew_commit 5000 M1 -p "$skew_root") &&
78 skew_M2=$(skew_commit 2000 M2 -p "$skew_M1") &&
79 skew_A=$(skew_commit 6000 A -p "$skew_M1" -p "$skew_M2") &&
80 skew_B=$(skew_commit 6000 B -p "$skew_M2") &&
81 skew_D=$(skew_commit 6000 D -p "$skew_M1") &&
82 skew_P1=$(skew_commit 7000 P1 -p "$skew_A") &&
83 skew_P2=$(skew_commit 7000 P2 -p "$skew_B" -p "$skew_D") &&
84 git branch -f skew-P1 "$skew_P1" &&
85 git branch -f skew-P2 "$skew_P2" &&
86 git tag skew-M2 "$skew_M2" &&
87
88 git commit-graph write --reachable &&
89 mv .git/objects/info/commit-graph commit-graph-full &&
90 chmod u+w commit-graph-full &&
91 git show-ref -s commit-5-5 | git commit-graph write --stdin-commits &&
92 mv .git/objects/info/commit-graph commit-graph-half &&
93 chmod u+w commit-graph-half &&
94 git -c commitGraph.generationVersion=1 commit-graph write --reachable &&
95 mv .git/objects/info/commit-graph commit-graph-no-gdat &&
96 chmod u+w commit-graph-no-gdat &&
97 git config core.commitGraph true
98 '
99
100 run_all_modes () {
101 test_when_finished rm -rf .git/objects/info/commit-graph &&
102 "$@" <input >actual &&
103 test_cmp expect actual &&
104 cp commit-graph-full .git/objects/info/commit-graph &&
105 "$@" <input >actual &&
106 test_cmp expect actual &&
107 cp commit-graph-half .git/objects/info/commit-graph &&
108 "$@" <input >actual &&
109 test_cmp expect actual &&
110 cp commit-graph-no-gdat .git/objects/info/commit-graph &&
111 "$@" <input >actual &&
112 test_cmp expect actual
113 }
114
115 test_all_modes () {
116 run_all_modes test-tool reach "$@"
117 }
118
119 test_expect_success 'ref_newer:miss' '
120 cat >input <<-\EOF &&
121 A:commit-5-7
122 B:commit-4-9
123 EOF
124 echo "ref_newer(A,B):0" >expect &&
125 test_all_modes ref_newer
126 '
127
128 test_expect_success 'ref_newer:hit' '
129 cat >input <<-\EOF &&
130 A:commit-5-7
131 B:commit-2-3
132 EOF
133 echo "ref_newer(A,B):1" >expect &&
134 test_all_modes ref_newer
135 '
136
137 test_expect_success 'in_merge_bases:hit' '
138 cat >input <<-\EOF &&
139 A:commit-5-7
140 B:commit-8-8
141 EOF
142 echo "in_merge_bases(A,B):1" >expect &&
143 test_all_modes in_merge_bases
144 '
145
146 test_expect_success 'in_merge_bases:miss' '
147 cat >input <<-\EOF &&
148 A:commit-6-8
149 B:commit-5-9
150 EOF
151 echo "in_merge_bases(A,B):0" >expect &&
152 test_all_modes in_merge_bases
153 '
154
155 test_expect_success 'in_merge_bases_many:hit' '
156 cat >input <<-\EOF &&
157 A:commit-6-8
158 X:commit-6-9
159 X:commit-5-7
160 EOF
161 echo "in_merge_bases_many(A,X):1" >expect &&
162 test_all_modes in_merge_bases_many
163 '
164
165 test_expect_success 'in_merge_bases_many:miss' '
166 cat >input <<-\EOF &&
167 A:commit-6-8
168 X:commit-7-7
169 X:commit-8-6
170 EOF
171 echo "in_merge_bases_many(A,X):0" >expect &&
172 test_all_modes in_merge_bases_many
173 '
174
175 test_expect_success 'in_merge_bases_many:miss-heuristic' '
176 cat >input <<-\EOF &&
177 A:commit-6-8
178 X:commit-7-5
179 X:commit-6-6
180 EOF
181 echo "in_merge_bases_many(A,X):0" >expect &&
182 test_all_modes in_merge_bases_many
183 '
184
185 test_expect_success 'is_descendant_of:hit' '
186 cat >input <<-\EOF &&
187 A:commit-5-7
188 X:commit-4-8
189 X:commit-6-6
190 X:commit-1-1
191 EOF
192 echo "is_descendant_of(A,X):1" >expect &&
193 test_all_modes is_descendant_of
194 '
195
196 test_expect_success 'is_descendant_of:miss' '
197 cat >input <<-\EOF &&
198 A:commit-6-8
199 X:commit-5-9
200 X:commit-4-10
201 X:commit-7-6
202 EOF
203 echo "is_descendant_of(A,X):0" >expect &&
204 test_all_modes is_descendant_of
205 '
206
207 test_expect_success 'get_merge_bases_many' '
208 cat >input <<-\EOF &&
209 A:commit-5-7
210 X:commit-4-8
211 X:commit-6-6
212 X:commit-8-3
213 EOF
214 {
215 echo "get_merge_bases_many(A,X):" &&
216 git rev-parse commit-5-6 \
217 commit-4-7 | sort
218 } >expect &&
219 test_all_modes get_merge_bases_many
220 '
221
222 test_expect_success 'reduce_heads' '
223 cat >input <<-\EOF &&
224 X:commit-1-10
225 X:commit-2-8
226 X:commit-3-6
227 X:commit-4-4
228 X:commit-1-7
229 X:commit-2-5
230 X:commit-3-3
231 X:commit-5-1
232 EOF
233 {
234 echo "reduce_heads(X):" &&
235 git rev-parse commit-5-1 \
236 commit-4-4 \
237 commit-3-6 \
238 commit-2-8 \
239 commit-1-10 | sort
240 } >expect &&
241 test_all_modes reduce_heads
242 '
243
244 test_expect_success 'can_all_from_reach:hit' '
245 cat >input <<-\EOF &&
246 X:commit-2-10
247 X:commit-3-9
248 X:commit-4-8
249 X:commit-5-7
250 X:commit-6-6
251 X:commit-7-5
252 X:commit-8-4
253 X:commit-9-3
254 Y:commit-1-9
255 Y:commit-2-8
256 Y:commit-3-7
257 Y:commit-4-6
258 Y:commit-5-5
259 Y:commit-6-4
260 Y:commit-7-3
261 Y:commit-8-1
262 EOF
263 echo "can_all_from_reach(X,Y):1" >expect &&
264 test_all_modes can_all_from_reach
265 '
266
267 test_expect_success 'can_all_from_reach:miss' '
268 cat >input <<-\EOF &&
269 X:commit-2-10
270 X:commit-3-9
271 X:commit-4-8
272 X:commit-5-7
273 X:commit-6-6
274 X:commit-7-5
275 X:commit-8-4
276 X:commit-9-3
277 Y:commit-1-9
278 Y:commit-2-8
279 Y:commit-3-7
280 Y:commit-4-6
281 Y:commit-5-5
282 Y:commit-6-4
283 Y:commit-8-5
284 EOF
285 echo "can_all_from_reach(X,Y):0" >expect &&
286 test_all_modes can_all_from_reach
287 '
288
289 test_expect_success 'can_all_from_reach_with_flag: tags case' '
290 cat >input <<-\EOF &&
291 X:tag-2-10
292 X:tag-3-9
293 X:tag-4-8
294 X:commit-5-7
295 X:commit-6-6
296 X:commit-7-5
297 X:commit-8-4
298 X:commit-9-3
299 Y:tag-1-9
300 Y:tag-2-8
301 Y:tag-3-7
302 Y:commit-4-6
303 Y:commit-5-5
304 Y:commit-6-4
305 Y:commit-7-3
306 Y:commit-8-1
307 EOF
308 echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
309 test_all_modes can_all_from_reach_with_flag
310 '
311
312 test_expect_success 'commit_contains:hit' '
313 cat >input <<-\EOF &&
314 A:commit-7-7
315 X:commit-2-10
316 X:commit-3-9
317 X:commit-4-8
318 X:commit-5-7
319 X:commit-6-6
320 X:commit-7-5
321 X:commit-8-4
322 X:commit-9-3
323 EOF
324 echo "commit_contains(_,A,X,_):1" >expect &&
325 test_all_modes commit_contains &&
326 test_all_modes commit_contains --tag
327 '
328
329 test_expect_success 'commit_contains:miss' '
330 cat >input <<-\EOF &&
331 A:commit-6-5
332 X:commit-2-10
333 X:commit-3-9
334 X:commit-4-8
335 X:commit-5-7
336 X:commit-6-6
337 X:commit-7-5
338 X:commit-8-4
339 X:commit-9-3
340 EOF
341 echo "commit_contains(_,A,X,_):0" >expect &&
342 test_all_modes commit_contains &&
343 test_all_modes commit_contains --tag
344 '
345
346 test_expect_success 'rev-list: basic topo-order' '
347 git rev-parse \
348 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
349 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
350 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
351 commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
352 commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
353 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
354 >expect &&
355 run_all_modes git rev-list --topo-order commit-6-6
356 '
357
358 test_expect_success 'rev-list: first-parent topo-order' '
359 git rev-parse \
360 commit-6-6 \
361 commit-6-5 \
362 commit-6-4 \
363 commit-6-3 \
364 commit-6-2 \
365 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
366 >expect &&
367 run_all_modes git rev-list --first-parent --topo-order commit-6-6
368 '
369
370 test_expect_success 'rev-list: range topo-order' '
371 git rev-parse \
372 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
373 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
374 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
375 commit-6-3 commit-5-3 commit-4-3 \
376 commit-6-2 commit-5-2 commit-4-2 \
377 commit-6-1 commit-5-1 commit-4-1 \
378 >expect &&
379 run_all_modes git rev-list --topo-order commit-3-3..commit-6-6
380 '
381
382 test_expect_success 'rev-list: range topo-order' '
383 git rev-parse \
384 commit-6-6 commit-5-6 commit-4-6 \
385 commit-6-5 commit-5-5 commit-4-5 \
386 commit-6-4 commit-5-4 commit-4-4 \
387 commit-6-3 commit-5-3 commit-4-3 \
388 commit-6-2 commit-5-2 commit-4-2 \
389 commit-6-1 commit-5-1 commit-4-1 \
390 >expect &&
391 run_all_modes git rev-list --topo-order commit-3-8..commit-6-6
392 '
393
394 test_expect_success 'rev-list: first-parent range topo-order' '
395 git rev-parse \
396 commit-6-6 \
397 commit-6-5 \
398 commit-6-4 \
399 commit-6-3 \
400 commit-6-2 \
401 commit-6-1 commit-5-1 commit-4-1 \
402 >expect &&
403 run_all_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
404 '
405
406 test_expect_success 'rev-list: ancestry-path topo-order' '
407 git rev-parse \
408 commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
409 commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
410 commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
411 commit-6-3 commit-5-3 commit-4-3 \
412 >expect &&
413 run_all_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
414 '
415
416 test_expect_success 'rev-list: symmetric difference topo-order' '
417 git rev-parse \
418 commit-6-6 commit-5-6 commit-4-6 \
419 commit-6-5 commit-5-5 commit-4-5 \
420 commit-6-4 commit-5-4 commit-4-4 \
421 commit-6-3 commit-5-3 commit-4-3 \
422 commit-6-2 commit-5-2 commit-4-2 \
423 commit-6-1 commit-5-1 commit-4-1 \
424 commit-3-8 commit-2-8 commit-1-8 \
425 commit-3-7 commit-2-7 commit-1-7 \
426 >expect &&
427 run_all_modes git rev-list --topo-order commit-3-8...commit-6-6
428 '
429
430 test_expect_success 'get_reachable_subset:all' '
431 cat >input <<-\EOF &&
432 X:commit-9-1
433 X:commit-8-3
434 X:commit-7-5
435 X:commit-6-6
436 X:commit-1-7
437 Y:commit-3-3
438 Y:commit-1-7
439 Y:commit-5-6
440 EOF
441 (
442 echo "get_reachable_subset(X,Y)" &&
443 git rev-parse commit-3-3 \
444 commit-1-7 \
445 commit-5-6 | sort
446 ) >expect &&
447 test_all_modes get_reachable_subset
448 '
449
450 test_expect_success 'get_reachable_subset:some' '
451 cat >input <<-\EOF &&
452 X:commit-9-1
453 X:commit-8-3
454 X:commit-7-5
455 X:commit-1-7
456 Y:commit-3-3
457 Y:commit-1-7
458 Y:commit-5-6
459 EOF
460 (
461 echo "get_reachable_subset(X,Y)" &&
462 git rev-parse commit-3-3 \
463 commit-1-7 | sort
464 ) >expect &&
465 test_all_modes get_reachable_subset
466 '
467
468 test_expect_success 'get_reachable_subset:none' '
469 cat >input <<-\EOF &&
470 X:commit-9-1
471 X:commit-8-3
472 X:commit-7-5
473 X:commit-1-7
474 Y:commit-9-3
475 Y:commit-7-6
476 Y:commit-2-8
477 EOF
478 echo "get_reachable_subset(X,Y)" >expect &&
479 test_all_modes get_reachable_subset
480 '
481
482 test_expect_success 'for-each-ref ahead-behind:linear' '
483 cat >input <<-\EOF &&
484 refs/heads/commit-1-1
485 refs/heads/commit-1-3
486 refs/heads/commit-1-5
487 refs/heads/commit-1-8
488 EOF
489 cat >expect <<-\EOF &&
490 refs/heads/commit-1-1 0 8
491 refs/heads/commit-1-3 0 6
492 refs/heads/commit-1-5 0 4
493 refs/heads/commit-1-8 0 1
494 EOF
495 run_all_modes git for-each-ref \
496 --format="%(refname) %(ahead-behind:commit-1-9)" --stdin
497 '
498
499 test_expect_success 'for-each-ref ahead-behind:all' '
500 cat >input <<-\EOF &&
501 refs/heads/commit-1-1
502 refs/heads/commit-2-4
503 refs/heads/commit-4-2
504 refs/heads/commit-4-4
505 EOF
506 cat >expect <<-\EOF &&
507 refs/heads/commit-1-1 0 24
508 refs/heads/commit-2-4 0 17
509 refs/heads/commit-4-2 0 17
510 refs/heads/commit-4-4 0 9
511 EOF
512 run_all_modes git for-each-ref \
513 --format="%(refname) %(ahead-behind:commit-5-5)" --stdin
514 '
515
516 test_expect_success 'for-each-ref ahead-behind:some' '
517 cat >input <<-\EOF &&
518 refs/heads/commit-1-1
519 refs/heads/commit-5-3
520 refs/heads/commit-4-8
521 refs/heads/commit-9-9
522 EOF
523 cat >expect <<-\EOF &&
524 refs/heads/commit-1-1 0 53
525 refs/heads/commit-4-8 8 30
526 refs/heads/commit-5-3 0 39
527 refs/heads/commit-9-9 27 0
528 EOF
529 run_all_modes git for-each-ref \
530 --format="%(refname) %(ahead-behind:commit-9-6)" --stdin
531 '
532
533 test_expect_success 'for-each-ref ahead-behind:some, multibase' '
534 cat >input <<-\EOF &&
535 refs/heads/commit-1-1
536 refs/heads/commit-5-3
537 refs/heads/commit-7-8
538 refs/heads/commit-4-8
539 refs/heads/commit-9-9
540 EOF
541 cat >expect <<-\EOF &&
542 refs/heads/commit-1-1 0 53 0 53
543 refs/heads/commit-4-8 8 30 0 22
544 refs/heads/commit-5-3 0 39 0 39
545 refs/heads/commit-7-8 14 12 8 6
546 refs/heads/commit-9-9 27 0 27 0
547 EOF
548 run_all_modes git for-each-ref \
549 --format="%(refname) %(ahead-behind:commit-9-6) %(ahead-behind:commit-6-9)" \
550 --stdin
551 '
552
553 test_expect_success 'for-each-ref ahead-behind:none' '
554 cat >input <<-\EOF &&
555 refs/heads/commit-7-5
556 refs/heads/commit-4-8
557 refs/heads/commit-9-9
558 EOF
559 cat >expect <<-\EOF &&
560 refs/heads/commit-4-8 16 16
561 refs/heads/commit-7-5 7 4
562 refs/heads/commit-9-9 49 0
563 EOF
564 run_all_modes git for-each-ref \
565 --format="%(refname) %(ahead-behind:commit-8-4)" --stdin
566 '
567
568 test_expect_success 'for-each-ref merged:linear' '
569 cat >input <<-\EOF &&
570 refs/heads/commit-1-1
571 refs/heads/commit-1-3
572 refs/heads/commit-1-5
573 refs/heads/commit-1-8
574 refs/heads/commit-2-1
575 refs/heads/commit-5-1
576 refs/heads/commit-9-1
577 EOF
578 cat >expect <<-\EOF &&
579 refs/heads/commit-1-1
580 refs/heads/commit-1-3
581 refs/heads/commit-1-5
582 refs/heads/commit-1-8
583 EOF
584 run_all_modes git for-each-ref --merged=commit-1-9 \
585 --format="%(refname)" --stdin
586 '
587
588 test_expect_success 'for-each-ref merged:all' '
589 cat >input <<-\EOF &&
590 refs/heads/commit-1-1
591 refs/heads/commit-2-4
592 refs/heads/commit-4-2
593 refs/heads/commit-4-4
594 EOF
595 cat >expect <<-\EOF &&
596 refs/heads/commit-1-1
597 refs/heads/commit-2-4
598 refs/heads/commit-4-2
599 refs/heads/commit-4-4
600 EOF
601 run_all_modes git for-each-ref --merged=commit-5-5 \
602 --format="%(refname)" --stdin
603 '
604
605 test_expect_success 'for-each-ref ahead-behind:some' '
606 cat >input <<-\EOF &&
607 refs/heads/commit-1-1
608 refs/heads/commit-5-3
609 refs/heads/commit-4-8
610 refs/heads/commit-9-9
611 EOF
612 cat >expect <<-\EOF &&
613 refs/heads/commit-1-1
614 refs/heads/commit-5-3
615 EOF
616 run_all_modes git for-each-ref --merged=commit-9-6 \
617 --format="%(refname)" --stdin
618 '
619
620 test_expect_success 'for-each-ref merged:some, multibase' '
621 cat >input <<-\EOF &&
622 refs/heads/commit-1-1
623 refs/heads/commit-5-3
624 refs/heads/commit-7-8
625 refs/heads/commit-4-8
626 refs/heads/commit-9-9
627 EOF
628 cat >expect <<-\EOF &&
629 refs/heads/commit-1-1
630 refs/heads/commit-4-8
631 refs/heads/commit-5-3
632 EOF
633 run_all_modes git for-each-ref \
634 --merged=commit-5-8 \
635 --merged=commit-8-5 \
636 --format="%(refname)" \
637 --stdin
638 '
639
640 test_expect_success 'for-each-ref merged:none' '
641 cat >input <<-\EOF &&
642 refs/heads/commit-7-5
643 refs/heads/commit-4-8
644 refs/heads/commit-9-9
645 EOF
646 >expect &&
647 run_all_modes git for-each-ref --merged=commit-8-4 \
648 --format="%(refname)" --stdin
649 '
650
651 test_expect_success 'for-each-ref merged:duplicate, all reachable' '
652 git branch dup-a commit-3-3 &&
653 git branch dup-b commit-3-3 &&
654 cat >input <<-\EOF &&
655 refs/heads/commit-1-1
656 refs/heads/dup-a
657 refs/heads/dup-b
658 EOF
659 cat >expect <<-\EOF &&
660 refs/heads/commit-1-1
661 refs/heads/dup-a
662 refs/heads/dup-b
663 EOF
664 run_all_modes git for-each-ref --merged=commit-5-5 \
665 --format="%(refname)" --stdin
666 '
667
668 test_expect_success 'for-each-ref merged:duplicate, none reachable' '
669 cat >input <<-\EOF &&
670 refs/heads/dup-a
671 refs/heads/dup-b
672 refs/heads/commit-9-9
673 EOF
674 >expect &&
675 run_all_modes git for-each-ref --merged=commit-2-2 \
676 --format="%(refname)" --stdin
677 '
678
679 test_expect_success 'for-each-ref merged:duplicate at min generation' '
680 git branch dup-c commit-1-1 &&
681 git branch dup-d commit-1-1 &&
682 cat >input <<-\EOF &&
683 refs/heads/dup-c
684 refs/heads/dup-d
685 refs/heads/commit-5-5
686 EOF
687 cat >expect <<-\EOF &&
688 refs/heads/commit-5-5
689 refs/heads/dup-c
690 refs/heads/dup-d
691 EOF
692 run_all_modes git for-each-ref --merged=commit-5-5 \
693 --format="%(refname)" --stdin
694 '
695
696 # For get_branch_base_for_tip, we only care about
697 # first-parent history. Here is the test graph with
698 # second parents removed:
699 #
700 # (10,10)
701 # /
702 # (10,9) (9,10)
703 # / /
704 # (10,8) (9,9) (8,10)
705 # / / /
706 # ( continued...)
707 # \ / / /
708 # (3,1) (2,2) (1,3)
709 # \ / /
710 # (2,1) (1,2)
711 # \ /
712 # (1,1)
713 #
714 # In short, for a commit (i,j), the first-parent history
715 # walks all commits (i, k) with k from j to 1, then the
716 # commits (l, 1) with l from i to 1.
717
718 test_expect_success 'get_branch_base_for_tip: none reach' '
719 # (2,3) branched from the first tip (i,4) in X with i > 2
720 cat >input <<-\EOF &&
721 A:commit-2-3
722 X:commit-1-2
723 X:commit-1-4
724 X:commit-4-4
725 X:commit-8-4
726 X:commit-10-4
727 EOF
728 echo "get_branch_base_for_tip(A,X):2" >expect &&
729 test_all_modes get_branch_base_for_tip
730 '
731
732 test_expect_success 'get_branch_base_for_tip: equal to tip' '
733 # (2,3) branched from the first tip (i,4) in X with i > 2
734 cat >input <<-\EOF &&
735 A:commit-8-4
736 X:commit-1-2
737 X:commit-1-4
738 X:commit-4-4
739 X:commit-8-4
740 X:commit-10-4
741 EOF
742 echo "get_branch_base_for_tip(A,X):3" >expect &&
743 test_all_modes get_branch_base_for_tip
744 '
745
746 test_expect_success 'get_branch_base_for_tip: all reach tip' '
747 # (2,3) branched from the first tip (i,4) in X with i > 2
748 cat >input <<-\EOF &&
749 A:commit-4-1
750 X:commit-4-2
751 X:commit-5-1
752 EOF
753 echo "get_branch_base_for_tip(A,X):0" >expect &&
754 test_all_modes get_branch_base_for_tip
755 '
756
757 test_expect_success 'for-each-ref is-base: none reach' '
758 cat >input <<-\EOF &&
759 refs/heads/commit-1-1
760 refs/heads/commit-4-2
761 refs/heads/commit-4-4
762 refs/heads/commit-8-4
763 EOF
764 cat >expect <<-\EOF &&
765 refs/heads/commit-1-1:
766 refs/heads/commit-4-2:(commit-2-3)
767 refs/heads/commit-4-4:
768 refs/heads/commit-8-4:
769 EOF
770 run_all_modes git for-each-ref \
771 --format="%(refname):%(is-base:commit-2-3)" --stdin
772 '
773
774 test_expect_success 'for-each-ref is-base: all reach' '
775 cat >input <<-\EOF &&
776 refs/heads/commit-4-2
777 refs/heads/commit-5-1
778 EOF
779 cat >expect <<-\EOF &&
780 refs/heads/commit-4-2:(commit-4-1)
781 refs/heads/commit-5-1:
782 EOF
783 run_all_modes git for-each-ref \
784 --format="%(refname):%(is-base:commit-4-1)" --stdin
785 '
786
787 test_expect_success 'for-each-ref is-base: equal to tip' '
788 cat >input <<-\EOF &&
789 refs/heads/commit-4-2
790 refs/heads/commit-5-1
791 EOF
792 cat >expect <<-\EOF &&
793 refs/heads/commit-4-2:(commit-4-2)
794 refs/heads/commit-5-1:
795 EOF
796 run_all_modes git for-each-ref \
797 --format="%(refname):%(is-base:commit-4-2)" --stdin
798 '
799
800 test_expect_success 'for-each-ref is-base:multiple' '
801 cat >input <<-\EOF &&
802 refs/heads/commit-1-1
803 refs/heads/commit-4-2
804 refs/heads/commit-4-4
805 refs/heads/commit-8-4
806 EOF
807 cat >expect <<-\EOF &&
808 refs/heads/commit-1-1[-]
809 refs/heads/commit-4-2[(commit-2-3)-]
810 refs/heads/commit-4-4[-]
811 refs/heads/commit-8-4[-(commit-6-5)]
812 EOF
813 run_all_modes git for-each-ref \
814 --format="%(refname)[%(is-base:commit-2-3)-%(is-base:commit-6-5)]" --stdin
815 '
816
817 test_expect_success 'for-each-ref is-base: --sort' '
818 cat >input <<-\EOF &&
819 refs/heads/commit-1-1
820 refs/heads/commit-4-2
821 refs/heads/commit-4-4
822 refs/heads/commit-8-4
823 EOF
824
825 cat >expect <<-\EOF &&
826 refs/heads/commit-1-1
827 refs/heads/commit-4-4
828 refs/heads/commit-8-4
829 refs/heads/commit-4-2
830 EOF
831 run_all_modes git for-each-ref \
832 --format="%(refname)" --stdin \
833 --sort=refname --sort=is-base:commit-2-3 &&
834
835 cat >expect <<-\EOF &&
836 refs/heads/commit-4-2
837 refs/heads/commit-1-1
838 refs/heads/commit-4-4
839 refs/heads/commit-8-4
840 EOF
841 run_all_modes git for-each-ref \
842 --format="%(refname)" --stdin \
843 --sort=refname --sort=-is-base:commit-2-3
844 '
845
846 test_expect_success 'rev-list --maximal-only (all positive)' '
847 # Only one maximal.
848 cat >input <<-\EOF &&
849 refs/heads/commit-1-1
850 refs/heads/commit-4-2
851 refs/heads/commit-4-4
852 refs/heads/commit-8-4
853 EOF
854
855 cat >expect <<-EOF &&
856 $(git rev-parse refs/heads/commit-8-4)
857 EOF
858 run_all_modes git rev-list --maximal-only --stdin &&
859
860 # All maximal.
861 cat >input <<-\EOF &&
862 refs/heads/commit-5-2
863 refs/heads/commit-4-3
864 refs/heads/commit-3-4
865 refs/heads/commit-2-5
866 EOF
867
868 cat >expect <<-EOF &&
869 $(git rev-parse refs/heads/commit-5-2)
870 $(git rev-parse refs/heads/commit-4-3)
871 $(git rev-parse refs/heads/commit-3-4)
872 $(git rev-parse refs/heads/commit-2-5)
873 EOF
874 run_all_modes git rev-list --maximal-only --stdin &&
875
876 # Mix of both.
877 cat >input <<-\EOF &&
878 refs/heads/commit-5-2
879 refs/heads/commit-3-2
880 refs/heads/commit-2-5
881 EOF
882
883 cat >expect <<-EOF &&
884 $(git rev-parse refs/heads/commit-5-2)
885 $(git rev-parse refs/heads/commit-2-5)
886 EOF
887 run_all_modes git rev-list --maximal-only --stdin
888 '
889
890 test_expect_success 'rev-list --maximal-only (range)' '
891 cat >input <<-\EOF &&
892 refs/heads/commit-1-1
893 refs/heads/commit-2-5
894 refs/heads/commit-6-4
895 ^refs/heads/commit-4-5
896 EOF
897
898 cat >expect <<-EOF &&
899 $(git rev-parse refs/heads/commit-6-4)
900 EOF
901 run_all_modes git rev-list --maximal-only --stdin &&
902
903 # first-parent changes reachability: the first parent
904 # reduces the second coordinate to 1 before reducing the
905 # first coordinate.
906 cat >input <<-\EOF &&
907 refs/heads/commit-1-1
908 refs/heads/commit-2-5
909 refs/heads/commit-6-4
910 ^refs/heads/commit-4-5
911 EOF
912
913 cat >expect <<-EOF &&
914 $(git rev-parse refs/heads/commit-6-4)
915 $(git rev-parse refs/heads/commit-2-5)
916 EOF
917 run_all_modes git rev-list --maximal-only --stdin \
918 --first-parent --exclude-first-parent-only
919 '
920
921 test_expect_success 'rev-list --maximal-only matches merge-base --independent' '
922 # Mix of independent and dependent
923 git merge-base --independent \
924 refs/heads/commit-5-2 \
925 refs/heads/commit-3-2 \
926 refs/heads/commit-2-5 >expect &&
927 sort expect >expect.sorted &&
928 git rev-list --maximal-only \
929 refs/heads/commit-5-2 \
930 refs/heads/commit-3-2 \
931 refs/heads/commit-2-5 >actual &&
932 sort actual >actual.sorted &&
933 test_cmp expect.sorted actual.sorted &&
934
935 # All independent commits.
936 git merge-base --independent \
937 refs/heads/commit-5-2 \
938 refs/heads/commit-4-3 \
939 refs/heads/commit-3-4 \
940 refs/heads/commit-2-5 >expect &&
941 sort expect >expect.sorted &&
942 git rev-list --maximal-only \
943 refs/heads/commit-5-2 \
944 refs/heads/commit-4-3 \
945 refs/heads/commit-3-4 \
946 refs/heads/commit-2-5 >actual &&
947 sort actual >actual.sorted &&
948 test_cmp expect.sorted actual.sorted &&
949
950 # Only one independent.
951 git merge-base --independent \
952 refs/heads/commit-1-1 \
953 refs/heads/commit-4-2 \
954 refs/heads/commit-4-4 \
955 refs/heads/commit-8-4 >expect &&
956 sort expect >expect.sorted &&
957 git rev-list --maximal-only \
958 refs/heads/commit-1-1 \
959 refs/heads/commit-4-2 \
960 refs/heads/commit-4-4 \
961 refs/heads/commit-8-4 >actual &&
962 sort actual >actual.sorted &&
963 test_cmp expect.sorted actual.sorted
964 '
965
966 # The following tests verify the early-exit optimisation in
967 # paint_down_to_common when merge-base is invoked without --all.
968 # Each test checks all four commit-graph configurations.
969
970 merge_base_all_modes () {
971 test_when_finished rm -rf .git/objects/info/commit-graph &&
972 git merge-base "$@" >actual &&
973 test_cmp expect actual &&
974 cp commit-graph-full .git/objects/info/commit-graph &&
975 git merge-base "$@" >actual &&
976 test_cmp expect actual &&
977 cp commit-graph-half .git/objects/info/commit-graph &&
978 git merge-base "$@" >actual &&
979 test_cmp expect actual &&
980 cp commit-graph-no-gdat .git/objects/info/commit-graph &&
981 git merge-base "$@" >actual &&
982 test_cmp expect actual
983 }
984
985 test_expect_success 'merge-base without --all (unique base)' '
986 git rev-parse commit-5-3 >expect &&
987 merge_base_all_modes commit-5-7 commit-8-3
988 '
989
990 test_expect_success 'merge-base without --all is one of --all results' '
991 test_when_finished rm -rf .git/objects/info/commit-graph &&
992
993 cp commit-graph-full .git/objects/info/commit-graph &&
994 git merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&
995 git merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&
996 test_line_count = 1 single &&
997 test_grep -F -f single all &&
998
999 cp commit-graph-half .git/objects/info/commit-graph &&
1000 git merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&
1001 git merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&
1002 test_line_count = 1 single &&
1003 test_grep -F -f single all
1004 '
1005
1006 test_expect_success 'merge-base without --all, clock skew, v1 commit-graph' '
1007 git rev-parse skew-M2 >expect &&
1008 merge_base_all_modes skew-P1 skew-P2
1009 '
1010
1011 test_done