@matheusbsbs / matheus-bagliano
Code Commits Pulls CI/CD 82,128
seen
bisect jch maint master next seen test todo
sh 1,228 lines 31.6 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 # Build a small side topology to exercise the (PARENT1|PARENT2) ->
89 # (PARENT1|PARENT2|STALE) transition in paint_down_to_common(); the
90 # 10x10 grid above does not exercise it because no merge-base candidate
91 # there is a descendant of another, so STALE never reaches a
92 # still-pending candidate.
93 #
94 # ps-X
95 # /|\
96 # / | \
97 # ps-Z ps-B ps-W
98 # | / \ |
99 # | / \ |
100 # |/ \|
101 # ps-T1 ps-T2
102 #
103 # where ps-T1=merge(ps-Z,ps-B), ps-T2=merge(ps-W,ps-B), so
104 # merge-base(ps-T1,ps-T2) = ps-B. During the walk, ps-X transitions
105 # to (PARENT1|PARENT2) via ps-Z and ps-W before ps-B is dequeued;
106 # then the STALE-walk from ps-B transitions ps-X to
107 # (PARENT1|PARENT2|STALE).
108 git checkout --orphan ps-orphan &&
109 test_commit ps-X &&
110 git checkout -b ps-B-br ps-X && test_commit ps-B &&
111 git checkout -b ps-Z-br ps-X && test_commit ps-Z &&
112 git checkout -b ps-W-br ps-X && test_commit ps-W &&
113 git checkout -b ps-T1 ps-Z &&
114 git merge --no-ff -m ps-T1 ps-B &&
115 git checkout -b ps-T2 ps-W &&
116 git merge --no-ff -m ps-T2 ps-B &&
117
118 # Build a side topology that lives entirely outside the half
119 # commit-graph and has non-monotonic commit dates, to exercise the
120 # INFINITY-gate in paint_down_to_common. With both tips outside
121 # the graph, generation is INFINITY and the queue falls back to
122 # commit-date order, which here is non-monotonic.
123 #
124 # pi-X (date 500, PARENT1 tip) --> pi-P, pi-D
125 # pi-D (date 480) --> pi-C
126 # pi-C (date 200) --> pi-B
127 # pi-B (date 100, PARENT2 tip) --> pi-P
128 # pi-P (date 450, root)
129 #
130 # merge-base(pi-X, pi-B) = pi-B (it is an ancestor of pi-X and is
131 # itself one of the queried tips).
132 git checkout --orphan pi-orphan &&
133 test_commit --date "@450 +0000" pi-P &&
134 test_commit --date "@100 +0000" pi-B &&
135 test_commit --date "@200 +0000" pi-C &&
136 test_commit --date "@480 +0000" pi-D &&
137 GIT_AUTHOR_DATE="@500 +0000" GIT_COMMITTER_DATE="@500 +0000" \
138 git commit-tree -p pi-D -p pi-P -m pi-X pi-D^{tree} >pi-X-oid &&
139 pi_x="$(cat pi-X-oid)" &&
140 git branch -f pi-X-br "$pi_x" &&
141 git tag pi-X "$pi_x" &&
142
143 # Clock-skew topology for side-exhaustion testing.
144 # D is the correct merge base but has a higher committer date
145 # than C (its child). With date ordering, D would be dequeued
146 # before C, causing side-exhaustion to fire too early.
147 # Generation ordering prevents this by visiting children
148 # before parents regardless of dates.
149 #
150 # se-A (date 7000) --> se-C (date 3000) --> se-D (date 5000) --> se-root (date 4000)
151 # se-B (date 6000) --> se-D
152 #
153 se_root=$(skew_commit 4000 se-root) &&
154 se_D=$(skew_commit 5000 se-D -p "$se_root") &&
155 se_C=$(skew_commit 3000 se-C -p "$se_D") &&
156 se_A=$(skew_commit 7000 se-A -p "$se_C") &&
157 se_B=$(skew_commit 6000 se-B -p "$se_D") &&
158 git branch -f se-A "$se_A" &&
159 git branch -f se-B "$se_B" &&
160 git tag se-D "$se_D" &&
161
162 # Clock-skew topology with redundant ancestor for
163 # side-exhaustion testing. MB1 is the correct merge base;
164 # MB2 is its parent. A reaches MB2 via E (high date) and
165 # MB1 via C (low date). B reaches MB1 via D. With date
166 # ordering, side-exhaustion would fire before C is dequeued,
167 # missing MB1. Generation ordering ensures both are found.
168 #
169 # se2-A (date 8000) --> se2-C (date 2000) --> se2-MB1 (date 5000) --> se2-MB2 (date 4000) --> se2-root (date 1000)
170 # se2-A --> se2-E (date 6500) --> se2-MB2
171 # se2-B (date 7000) --> se2-D (date 6000) --> se2-MB1
172 #
173 se2_root=$(skew_commit 1000 se2-root) &&
174 se2_MB2=$(skew_commit 4000 se2-MB2 -p "$se2_root") &&
175 se2_MB1=$(skew_commit 5000 se2-MB1 -p "$se2_MB2") &&
176 se2_C=$(skew_commit 2000 se2-C -p "$se2_MB1") &&
177 se2_D=$(skew_commit 6000 se2-D -p "$se2_MB1") &&
178 se2_E=$(skew_commit 6500 se2-E -p "$se2_MB2") &&
179 se2_A=$(skew_commit 8000 se2-A -p "$se2_C" -p "$se2_E") &&
180 se2_B=$(skew_commit 7000 se2-B -p "$se2_D") &&
181 git branch -f se2-A "$se2_A" &&
182 git branch -f se2-B "$se2_B" &&
183 git tag se2-MB1 "$se2_MB1" &&
184
185 git commit-graph write --reachable &&
186 mv .git/objects/info/commit-graph commit-graph-full &&
187 chmod u+w commit-graph-full &&
188 git show-ref -s commit-5-5 | git commit-graph write --stdin-commits &&
189 mv .git/objects/info/commit-graph commit-graph-half &&
190 chmod u+w commit-graph-half &&
191 git -c commitGraph.generationVersion=1 commit-graph write --reachable &&
192 mv .git/objects/info/commit-graph commit-graph-no-gdat &&
193 chmod u+w commit-graph-no-gdat &&
194 git config core.commitGraph true
195 '
196
197 run_all_modes () {
198 graph=.git/objects/info/commit-graph &&
199 test_when_finished rm -rf "$graph" "${graph}s" &&
200 rm -f trace-mode-*.txt &&
201
202 for mode in none full half no-gdat
203 do
204 rm -rf "$graph" "${graph}s" &&
205 cp "commit-graph-${mode}" "$graph" 2>/dev/null ||
206 true &&
207 GIT_TRACE2_EVENT="$(pwd)/trace-mode-${mode}.txt" \
208 "$@" <input >actual &&
209 test_cmp expect actual || return 1
210 done
211 }
212
213 test_all_modes () {
214 run_all_modes test-tool reach "$@"
215 }
216
217 test_paint_down_steps () {
218 for mode in none full half no-gdat
219 do
220 test_trace2_data_singular paint_down_to_common steps "$1" \
221 "mode=$mode" <"trace-mode-${mode}.txt" || return 1
222 shift
223 done
224 }
225
226 test_expect_success 'ref_newer:miss' '
227 cat >input <<-\EOF &&
228 A:commit-5-7
229 B:commit-4-9
230 EOF
231 echo "ref_newer(A,B):0" >expect &&
232 test_all_modes ref_newer
233 '
234
235 test_expect_success 'ref_newer:hit' '
236 cat >input <<-\EOF &&
237 A:commit-5-7
238 B:commit-2-3
239 EOF
240 echo "ref_newer(A,B):1" >expect &&
241 test_all_modes ref_newer
242 '
243
244 test_expect_success 'in_merge_bases:hit' '
245 cat >input <<-\EOF &&
246 A:commit-5-7
247 B:commit-8-8
248 EOF
249 echo "in_merge_bases(A,B):1" >expect &&
250 test_all_modes in_merge_bases
251 '
252
253 test_expect_success 'in_merge_bases:miss' '
254 cat >input <<-\EOF &&
255 A:commit-6-8
256 B:commit-5-9
257 EOF
258 echo "in_merge_bases(A,B):0" >expect &&
259 test_all_modes in_merge_bases
260 '
261
262 test_expect_success 'in_merge_bases_many:hit' '
263 cat >input <<-\EOF &&
264 A:commit-6-8
265 X:commit-6-9
266 X:commit-5-7
267 EOF
268 echo "in_merge_bases_many(A,X):1" >expect &&
269 test_all_modes in_merge_bases_many
270 '
271
272 test_expect_success 'in_merge_bases_many:miss' '
273 cat >input <<-\EOF &&
274 A:commit-6-8
275 X:commit-7-7
276 X:commit-8-6
277 EOF
278 echo "in_merge_bases_many(A,X):0" >expect &&
279 test_all_modes in_merge_bases_many
280 '
281
282 test_expect_success 'in_merge_bases_many:miss-heuristic' '
283 cat >input <<-\EOF &&
284 A:commit-6-8
285 X:commit-7-5
286 X:commit-6-6
287 EOF
288 echo "in_merge_bases_many(A,X):0" >expect &&
289 test_all_modes in_merge_bases_many
290 '
291
292 test_expect_success 'in_merge_bases_many:self' '
293 cat >input <<-\EOF &&
294 A:commit-6-8
295 X:commit-5-9
296 X:commit-6-8
297 EOF
298 echo "in_merge_bases_many(A,X):1" >expect &&
299 test_all_modes in_merge_bases_many &&
300 test_paint_down_steps 45 1 25 1
301 '
302
303 test_expect_success 'is_descendant_of:hit' '
304 cat >input <<-\EOF &&
305 A:commit-5-7
306 X:commit-4-8
307 X:commit-6-6
308 X:commit-1-1
309 EOF
310 echo "is_descendant_of(A,X):1" >expect &&
311 test_all_modes is_descendant_of
312 '
313
314 test_expect_success 'is_descendant_of:miss' '
315 cat >input <<-\EOF &&
316 A:commit-6-8
317 X:commit-5-9
318 X:commit-4-10
319 X:commit-7-6
320 EOF
321 echo "is_descendant_of(A,X):0" >expect &&
322 test_all_modes is_descendant_of
323 '
324
325 test_expect_success 'get_merge_bases_many' '
326 cat >input <<-\EOF &&
327 A:commit-5-7
328 X:commit-4-8
329 X:commit-6-6
330 X:commit-8-3
331 EOF
332 {
333 echo "get_merge_bases_many(A,X):" &&
334 git rev-parse commit-5-6 \
335 commit-4-7 | sort
336 } >expect &&
337 test_all_modes get_merge_bases_many
338 '
339
340 test_expect_success 'get_merge_bases_many:duplicate-twos' '
341 cat >input <<-\EOF &&
342 A:commit-5-7
343 X:commit-4-8
344 X:commit-4-8
345 X:commit-6-6
346 X:commit-6-6
347 X:commit-8-3
348 EOF
349 {
350 echo "get_merge_bases_many(A,X):" &&
351 git rev-parse commit-5-6 \
352 commit-4-7 | sort
353 } >expect &&
354 test_all_modes get_merge_bases_many
355 '
356
357 test_expect_success 'get_merge_bases_many:pending-stale' '
358 # Exercises the (PARENT1|PARENT2) -> (...|STALE) transition path in
359 # paint_down_to_common(). See the topology comment in the setup test.
360 cat >input <<-\EOF &&
361 A:ps-T1
362 X:ps-T2
363 EOF
364 {
365 echo "get_merge_bases_many(A,X):" &&
366 git rev-parse ps-B
367 } >expect &&
368 test_all_modes get_merge_bases_many &&
369 test_paint_down_steps 5 5 5 5
370 '
371
372 test_expect_success 'get_merge_bases_many:infinity-both-sides' '
373 # Exercises the push-time INFINITY-gate in paint_down_to_common(). See
374 # the pi-* topology comment in the setup test.
375 cat >input <<-\EOF &&
376 A:pi-X
377 X:pi-B
378 EOF
379 {
380 echo "get_merge_bases_many(A,X):" &&
381 git rev-parse pi-B
382 } >expect &&
383 test_all_modes get_merge_bases_many &&
384 test_paint_down_steps 5 4 5 4
385 '
386
387 test_expect_success 'setup mixed finite/INFINITY topology' '
388 # Create a commit outside all saved commit-graph files so it always
389 # has INFINITY generation, while its parent (ps-X) is in the graph
390 # with a finite generation. Use the ps-* orphan topology so we do
391 # not pollute the grid-based rev-list tests.
392 git checkout ps-X &&
393 test_env GIT_TEST_COMMIT_GRAPH= test_commit pm-INF
394 '
395
396 test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
397 # One tip (pm-INF) is outside the commit-graph with INFINITY
398 # generation; the other (ps-B) is in the graph with finite
399 # generation. The walk starts in the INFINITY region and crosses
400 # into the finite region where side-exhaustion can fire.
401 cat >input <<-\EOF &&
402 A:pm-INF
403 X:ps-B
404 EOF
405 {
406 echo "get_merge_bases_many(A,X):" &&
407 git rev-parse ps-X
408 } >expect &&
409 test_all_modes get_merge_bases_many &&
410 test_paint_down_steps 3 3 3 3
411 '
412
413 test_expect_success 'merge-base --all commit-walk steps' '
414 >input &&
415 git rev-parse commit-9-1 >expect &&
416 run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
417 test_paint_down_steps 81 9 57 37
418 '
419
420 test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
421 # Verify that the merge base is computed correctly even
422 # when commits have non-monotonic commit dates.
423 >input &&
424 git rev-parse se-D >expect &&
425 run_all_modes git merge-base --all se-A se-B &&
426 test_paint_down_steps 6 4 6 4
427 '
428
429 test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
430 # Verify that the correct merge base is found even when
431 # non-monotonic commit dates could cause a redundant
432 # ancestor to be visited first.
433 >input &&
434 git rev-parse se2-MB1 >expect &&
435 run_all_modes git merge-base --all se2-A se2-B &&
436 test_paint_down_steps 8 6 8 6
437 '
438
439 test_expect_success 'reduce_heads' '
440 cat >input <<-\EOF &&
441 X:commit-1-10
442 X:commit-2-8
443 X:commit-3-6
444 X:commit-4-4
445 X:commit-1-7
446 X:commit-2-5
447 X:commit-3-3
448 X:commit-5-1
449 EOF
450 {
451 echo "reduce_heads(X):" &&
452 git rev-parse commit-5-1 \
453 commit-4-4 \
454 commit-3-6 \
455 commit-2-8 \
456 commit-1-10 | sort
457 } >expect &&
458 test_all_modes reduce_heads
459 '
460
461 test_expect_success 'can_all_from_reach:hit' '
462 cat >input <<-\EOF &&
463 X:commit-2-10
464 X:commit-3-9
465 X:commit-4-8
466 X:commit-5-7
467 X:commit-6-6
468 X:commit-7-5
469 X:commit-8-4
470 X:commit-9-3
471 Y:commit-1-9
472 Y:commit-2-8
473 Y:commit-3-7
474 Y:commit-4-6
475 Y:commit-5-5
476 Y:commit-6-4
477 Y:commit-7-3
478 Y:commit-8-1
479 EOF
480 echo "can_all_from_reach(X,Y):1" >expect &&
481 test_all_modes can_all_from_reach
482 '
483
484 test_expect_success 'can_all_from_reach:miss' '
485 cat >input <<-\EOF &&
486 X:commit-2-10
487 X:commit-3-9
488 X:commit-4-8
489 X:commit-5-7
490 X:commit-6-6
491 X:commit-7-5
492 X:commit-8-4
493 X:commit-9-3
494 Y:commit-1-9
495 Y:commit-2-8
496 Y:commit-3-7
497 Y:commit-4-6
498 Y:commit-5-5
499 Y:commit-6-4
500 Y:commit-8-5
501 EOF
502 echo "can_all_from_reach(X,Y):0" >expect &&
503 test_all_modes can_all_from_reach
504 '
505
506 test_expect_success 'can_all_from_reach_with_flag: tags case' '
507 cat >input <<-\EOF &&
508 X:tag-2-10
509 X:tag-3-9
510 X:tag-4-8
511 X:commit-5-7
512 X:commit-6-6
513 X:commit-7-5
514 X:commit-8-4
515 X:commit-9-3
516 Y:tag-1-9
517 Y:tag-2-8
518 Y:tag-3-7
519 Y:commit-4-6
520 Y:commit-5-5
521 Y:commit-6-4
522 Y:commit-7-3
523 Y:commit-8-1
524 EOF
525 echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
526 test_all_modes can_all_from_reach_with_flag
527 '
528
529 test_expect_success 'commit_contains:hit' '
530 cat >input <<-\EOF &&
531 A:commit-7-7
532 X:commit-2-10
533 X:commit-3-9
534 X:commit-4-8
535 X:commit-5-7
536 X:commit-6-6
537 X:commit-7-5
538 X:commit-8-4
539 X:commit-9-3
540 EOF
541 echo "commit_contains(_,A,X,_):1" >expect &&
542 test_all_modes commit_contains &&
543 test_all_modes commit_contains --tag
544 '
545
546 test_expect_success 'commit_contains:miss' '
547 cat >input <<-\EOF &&
548 A:commit-6-5
549 X:commit-2-10
550 X:commit-3-9
551 X:commit-4-8
552 X:commit-5-7
553 X:commit-6-6
554 X:commit-7-5
555 X:commit-8-4
556 X:commit-9-3
557 EOF
558 echo "commit_contains(_,A,X,_):0" >expect &&
559 test_all_modes commit_contains &&
560 test_all_modes commit_contains --tag
561 '
562
563 test_expect_success 'rev-list: basic topo-order' '
564 git rev-parse \
565 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
566 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
567 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
568 commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
569 commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
570 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
571 >expect &&
572 run_all_modes git rev-list --topo-order commit-6-6
573 '
574
575 test_expect_success 'rev-list: first-parent topo-order' '
576 git rev-parse \
577 commit-6-6 \
578 commit-6-5 \
579 commit-6-4 \
580 commit-6-3 \
581 commit-6-2 \
582 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
583 >expect &&
584 run_all_modes git rev-list --first-parent --topo-order commit-6-6
585 '
586
587 test_expect_success 'rev-list: range topo-order' '
588 git rev-parse \
589 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
590 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
591 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
592 commit-6-3 commit-5-3 commit-4-3 \
593 commit-6-2 commit-5-2 commit-4-2 \
594 commit-6-1 commit-5-1 commit-4-1 \
595 >expect &&
596 run_all_modes git rev-list --topo-order commit-3-3..commit-6-6
597 '
598
599 test_expect_success 'rev-list: range topo-order' '
600 git rev-parse \
601 commit-6-6 commit-5-6 commit-4-6 \
602 commit-6-5 commit-5-5 commit-4-5 \
603 commit-6-4 commit-5-4 commit-4-4 \
604 commit-6-3 commit-5-3 commit-4-3 \
605 commit-6-2 commit-5-2 commit-4-2 \
606 commit-6-1 commit-5-1 commit-4-1 \
607 >expect &&
608 run_all_modes git rev-list --topo-order commit-3-8..commit-6-6
609 '
610
611 test_expect_success 'rev-list: first-parent range topo-order' '
612 git rev-parse \
613 commit-6-6 \
614 commit-6-5 \
615 commit-6-4 \
616 commit-6-3 \
617 commit-6-2 \
618 commit-6-1 commit-5-1 commit-4-1 \
619 >expect &&
620 run_all_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
621 '
622
623 test_expect_success 'rev-list: ancestry-path topo-order' '
624 git rev-parse \
625 commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
626 commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
627 commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
628 commit-6-3 commit-5-3 commit-4-3 \
629 >expect &&
630 run_all_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
631 '
632
633 test_expect_success 'rev-list: symmetric difference topo-order' '
634 git rev-parse \
635 commit-6-6 commit-5-6 commit-4-6 \
636 commit-6-5 commit-5-5 commit-4-5 \
637 commit-6-4 commit-5-4 commit-4-4 \
638 commit-6-3 commit-5-3 commit-4-3 \
639 commit-6-2 commit-5-2 commit-4-2 \
640 commit-6-1 commit-5-1 commit-4-1 \
641 commit-3-8 commit-2-8 commit-1-8 \
642 commit-3-7 commit-2-7 commit-1-7 \
643 >expect &&
644 run_all_modes git rev-list --topo-order commit-3-8...commit-6-6
645 '
646
647 test_expect_success 'get_reachable_subset:all' '
648 cat >input <<-\EOF &&
649 X:commit-9-1
650 X:commit-8-3
651 X:commit-7-5
652 X:commit-6-6
653 X:commit-1-7
654 Y:commit-3-3
655 Y:commit-1-7
656 Y:commit-5-6
657 EOF
658 (
659 echo "get_reachable_subset(X,Y)" &&
660 git rev-parse commit-3-3 \
661 commit-1-7 \
662 commit-5-6 | sort
663 ) >expect &&
664 test_all_modes get_reachable_subset
665 '
666
667 test_expect_success 'get_reachable_subset:some' '
668 cat >input <<-\EOF &&
669 X:commit-9-1
670 X:commit-8-3
671 X:commit-7-5
672 X:commit-1-7
673 Y:commit-3-3
674 Y:commit-1-7
675 Y:commit-5-6
676 EOF
677 (
678 echo "get_reachable_subset(X,Y)" &&
679 git rev-parse commit-3-3 \
680 commit-1-7 | sort
681 ) >expect &&
682 test_all_modes get_reachable_subset
683 '
684
685 test_expect_success 'get_reachable_subset:none' '
686 cat >input <<-\EOF &&
687 X:commit-9-1
688 X:commit-8-3
689 X:commit-7-5
690 X:commit-1-7
691 Y:commit-9-3
692 Y:commit-7-6
693 Y:commit-2-8
694 EOF
695 echo "get_reachable_subset(X,Y)" >expect &&
696 test_all_modes get_reachable_subset
697 '
698
699 test_expect_success 'for-each-ref ahead-behind:linear' '
700 cat >input <<-\EOF &&
701 refs/heads/commit-1-1
702 refs/heads/commit-1-3
703 refs/heads/commit-1-5
704 refs/heads/commit-1-8
705 EOF
706 cat >expect <<-\EOF &&
707 refs/heads/commit-1-1 0 8
708 refs/heads/commit-1-3 0 6
709 refs/heads/commit-1-5 0 4
710 refs/heads/commit-1-8 0 1
711 EOF
712 run_all_modes git for-each-ref \
713 --format="%(refname) %(ahead-behind:commit-1-9)" --stdin
714 '
715
716 test_expect_success 'for-each-ref ahead-behind:all' '
717 cat >input <<-\EOF &&
718 refs/heads/commit-1-1
719 refs/heads/commit-2-4
720 refs/heads/commit-4-2
721 refs/heads/commit-4-4
722 EOF
723 cat >expect <<-\EOF &&
724 refs/heads/commit-1-1 0 24
725 refs/heads/commit-2-4 0 17
726 refs/heads/commit-4-2 0 17
727 refs/heads/commit-4-4 0 9
728 EOF
729 run_all_modes git for-each-ref \
730 --format="%(refname) %(ahead-behind:commit-5-5)" --stdin
731 '
732
733 test_expect_success 'for-each-ref ahead-behind:some' '
734 cat >input <<-\EOF &&
735 refs/heads/commit-1-1
736 refs/heads/commit-5-3
737 refs/heads/commit-4-8
738 refs/heads/commit-9-9
739 EOF
740 cat >expect <<-\EOF &&
741 refs/heads/commit-1-1 0 53
742 refs/heads/commit-4-8 8 30
743 refs/heads/commit-5-3 0 39
744 refs/heads/commit-9-9 27 0
745 EOF
746 run_all_modes git for-each-ref \
747 --format="%(refname) %(ahead-behind:commit-9-6)" --stdin
748 '
749
750 test_expect_success 'for-each-ref ahead-behind:some, multibase' '
751 cat >input <<-\EOF &&
752 refs/heads/commit-1-1
753 refs/heads/commit-5-3
754 refs/heads/commit-7-8
755 refs/heads/commit-4-8
756 refs/heads/commit-9-9
757 EOF
758 cat >expect <<-\EOF &&
759 refs/heads/commit-1-1 0 53 0 53
760 refs/heads/commit-4-8 8 30 0 22
761 refs/heads/commit-5-3 0 39 0 39
762 refs/heads/commit-7-8 14 12 8 6
763 refs/heads/commit-9-9 27 0 27 0
764 EOF
765 run_all_modes git for-each-ref \
766 --format="%(refname) %(ahead-behind:commit-9-6) %(ahead-behind:commit-6-9)" \
767 --stdin
768 '
769
770 test_expect_success 'for-each-ref ahead-behind:none' '
771 cat >input <<-\EOF &&
772 refs/heads/commit-7-5
773 refs/heads/commit-4-8
774 refs/heads/commit-9-9
775 EOF
776 cat >expect <<-\EOF &&
777 refs/heads/commit-4-8 16 16
778 refs/heads/commit-7-5 7 4
779 refs/heads/commit-9-9 49 0
780 EOF
781 run_all_modes git for-each-ref \
782 --format="%(refname) %(ahead-behind:commit-8-4)" --stdin
783 '
784
785 test_expect_success 'for-each-ref merged:linear' '
786 cat >input <<-\EOF &&
787 refs/heads/commit-1-1
788 refs/heads/commit-1-3
789 refs/heads/commit-1-5
790 refs/heads/commit-1-8
791 refs/heads/commit-2-1
792 refs/heads/commit-5-1
793 refs/heads/commit-9-1
794 EOF
795 cat >expect <<-\EOF &&
796 refs/heads/commit-1-1
797 refs/heads/commit-1-3
798 refs/heads/commit-1-5
799 refs/heads/commit-1-8
800 EOF
801 run_all_modes git for-each-ref --merged=commit-1-9 \
802 --format="%(refname)" --stdin
803 '
804
805 test_expect_success 'for-each-ref merged:all' '
806 cat >input <<-\EOF &&
807 refs/heads/commit-1-1
808 refs/heads/commit-2-4
809 refs/heads/commit-4-2
810 refs/heads/commit-4-4
811 EOF
812 cat >expect <<-\EOF &&
813 refs/heads/commit-1-1
814 refs/heads/commit-2-4
815 refs/heads/commit-4-2
816 refs/heads/commit-4-4
817 EOF
818 run_all_modes git for-each-ref --merged=commit-5-5 \
819 --format="%(refname)" --stdin
820 '
821
822 test_expect_success 'for-each-ref ahead-behind:some' '
823 cat >input <<-\EOF &&
824 refs/heads/commit-1-1
825 refs/heads/commit-5-3
826 refs/heads/commit-4-8
827 refs/heads/commit-9-9
828 EOF
829 cat >expect <<-\EOF &&
830 refs/heads/commit-1-1
831 refs/heads/commit-5-3
832 EOF
833 run_all_modes git for-each-ref --merged=commit-9-6 \
834 --format="%(refname)" --stdin
835 '
836
837 test_expect_success 'for-each-ref merged:some, multibase' '
838 cat >input <<-\EOF &&
839 refs/heads/commit-1-1
840 refs/heads/commit-5-3
841 refs/heads/commit-7-8
842 refs/heads/commit-4-8
843 refs/heads/commit-9-9
844 EOF
845 cat >expect <<-\EOF &&
846 refs/heads/commit-1-1
847 refs/heads/commit-4-8
848 refs/heads/commit-5-3
849 EOF
850 run_all_modes git for-each-ref \
851 --merged=commit-5-8 \
852 --merged=commit-8-5 \
853 --format="%(refname)" \
854 --stdin
855 '
856
857 test_expect_success 'for-each-ref merged:none' '
858 cat >input <<-\EOF &&
859 refs/heads/commit-7-5
860 refs/heads/commit-4-8
861 refs/heads/commit-9-9
862 EOF
863 >expect &&
864 run_all_modes git for-each-ref --merged=commit-8-4 \
865 --format="%(refname)" --stdin
866 '
867
868 test_expect_success 'for-each-ref merged:duplicate, all reachable' '
869 git branch dup-a commit-3-3 &&
870 git branch dup-b commit-3-3 &&
871 cat >input <<-\EOF &&
872 refs/heads/commit-1-1
873 refs/heads/dup-a
874 refs/heads/dup-b
875 EOF
876 cat >expect <<-\EOF &&
877 refs/heads/commit-1-1
878 refs/heads/dup-a
879 refs/heads/dup-b
880 EOF
881 run_all_modes git for-each-ref --merged=commit-5-5 \
882 --format="%(refname)" --stdin
883 '
884
885 test_expect_success 'for-each-ref merged:duplicate, none reachable' '
886 cat >input <<-\EOF &&
887 refs/heads/dup-a
888 refs/heads/dup-b
889 refs/heads/commit-9-9
890 EOF
891 >expect &&
892 run_all_modes git for-each-ref --merged=commit-2-2 \
893 --format="%(refname)" --stdin
894 '
895
896 test_expect_success 'for-each-ref merged:duplicate at min generation' '
897 git branch dup-c commit-1-1 &&
898 git branch dup-d commit-1-1 &&
899 cat >input <<-\EOF &&
900 refs/heads/dup-c
901 refs/heads/dup-d
902 refs/heads/commit-5-5
903 EOF
904 cat >expect <<-\EOF &&
905 refs/heads/commit-5-5
906 refs/heads/dup-c
907 refs/heads/dup-d
908 EOF
909 run_all_modes git for-each-ref --merged=commit-5-5 \
910 --format="%(refname)" --stdin
911 '
912
913 # For get_branch_base_for_tip, we only care about
914 # first-parent history. Here is the test graph with
915 # second parents removed:
916 #
917 # (10,10)
918 # /
919 # (10,9) (9,10)
920 # / /
921 # (10,8) (9,9) (8,10)
922 # / / /
923 # ( continued...)
924 # \ / / /
925 # (3,1) (2,2) (1,3)
926 # \ / /
927 # (2,1) (1,2)
928 # \ /
929 # (1,1)
930 #
931 # In short, for a commit (i,j), the first-parent history
932 # walks all commits (i, k) with k from j to 1, then the
933 # commits (l, 1) with l from i to 1.
934
935 test_expect_success 'get_branch_base_for_tip: none reach' '
936 # (2,3) branched from the first tip (i,4) in X with i > 2
937 cat >input <<-\EOF &&
938 A:commit-2-3
939 X:commit-1-2
940 X:commit-1-4
941 X:commit-4-4
942 X:commit-8-4
943 X:commit-10-4
944 EOF
945 echo "get_branch_base_for_tip(A,X):2" >expect &&
946 test_all_modes get_branch_base_for_tip
947 '
948
949 test_expect_success 'get_branch_base_for_tip: equal to tip' '
950 # (2,3) branched from the first tip (i,4) in X with i > 2
951 cat >input <<-\EOF &&
952 A:commit-8-4
953 X:commit-1-2
954 X:commit-1-4
955 X:commit-4-4
956 X:commit-8-4
957 X:commit-10-4
958 EOF
959 echo "get_branch_base_for_tip(A,X):3" >expect &&
960 test_all_modes get_branch_base_for_tip
961 '
962
963 test_expect_success 'get_branch_base_for_tip: all reach tip' '
964 # (2,3) branched from the first tip (i,4) in X with i > 2
965 cat >input <<-\EOF &&
966 A:commit-4-1
967 X:commit-4-2
968 X:commit-5-1
969 EOF
970 echo "get_branch_base_for_tip(A,X):0" >expect &&
971 test_all_modes get_branch_base_for_tip
972 '
973
974 test_expect_success 'for-each-ref is-base: none reach' '
975 cat >input <<-\EOF &&
976 refs/heads/commit-1-1
977 refs/heads/commit-4-2
978 refs/heads/commit-4-4
979 refs/heads/commit-8-4
980 EOF
981 cat >expect <<-\EOF &&
982 refs/heads/commit-1-1:
983 refs/heads/commit-4-2:(commit-2-3)
984 refs/heads/commit-4-4:
985 refs/heads/commit-8-4:
986 EOF
987 run_all_modes git for-each-ref \
988 --format="%(refname):%(is-base:commit-2-3)" --stdin
989 '
990
991 test_expect_success 'for-each-ref is-base: all reach' '
992 cat >input <<-\EOF &&
993 refs/heads/commit-4-2
994 refs/heads/commit-5-1
995 EOF
996 cat >expect <<-\EOF &&
997 refs/heads/commit-4-2:(commit-4-1)
998 refs/heads/commit-5-1:
999 EOF
1000 run_all_modes git for-each-ref \
1001 --format="%(refname):%(is-base:commit-4-1)" --stdin
1002 '
1003
1004 test_expect_success 'for-each-ref is-base: equal to tip' '
1005 cat >input <<-\EOF &&
1006 refs/heads/commit-4-2
1007 refs/heads/commit-5-1
1008 EOF
1009 cat >expect <<-\EOF &&
1010 refs/heads/commit-4-2:(commit-4-2)
1011 refs/heads/commit-5-1:
1012 EOF
1013 run_all_modes git for-each-ref \
1014 --format="%(refname):%(is-base:commit-4-2)" --stdin
1015 '
1016
1017 test_expect_success 'for-each-ref is-base:multiple' '
1018 cat >input <<-\EOF &&
1019 refs/heads/commit-1-1
1020 refs/heads/commit-4-2
1021 refs/heads/commit-4-4
1022 refs/heads/commit-8-4
1023 EOF
1024 cat >expect <<-\EOF &&
1025 refs/heads/commit-1-1[-]
1026 refs/heads/commit-4-2[(commit-2-3)-]
1027 refs/heads/commit-4-4[-]
1028 refs/heads/commit-8-4[-(commit-6-5)]
1029 EOF
1030 run_all_modes git for-each-ref \
1031 --format="%(refname)[%(is-base:commit-2-3)-%(is-base:commit-6-5)]" --stdin
1032 '
1033
1034 test_expect_success 'for-each-ref is-base: --sort' '
1035 cat >input <<-\EOF &&
1036 refs/heads/commit-1-1
1037 refs/heads/commit-4-2
1038 refs/heads/commit-4-4
1039 refs/heads/commit-8-4
1040 EOF
1041
1042 cat >expect <<-\EOF &&
1043 refs/heads/commit-1-1
1044 refs/heads/commit-4-4
1045 refs/heads/commit-8-4
1046 refs/heads/commit-4-2
1047 EOF
1048 run_all_modes git for-each-ref \
1049 --format="%(refname)" --stdin \
1050 --sort=refname --sort=is-base:commit-2-3 &&
1051
1052 cat >expect <<-\EOF &&
1053 refs/heads/commit-4-2
1054 refs/heads/commit-1-1
1055 refs/heads/commit-4-4
1056 refs/heads/commit-8-4
1057 EOF
1058 run_all_modes git for-each-ref \
1059 --format="%(refname)" --stdin \
1060 --sort=refname --sort=-is-base:commit-2-3
1061 '
1062
1063 test_expect_success 'rev-list --maximal-only (all positive)' '
1064 # Only one maximal.
1065 cat >input <<-\EOF &&
1066 refs/heads/commit-1-1
1067 refs/heads/commit-4-2
1068 refs/heads/commit-4-4
1069 refs/heads/commit-8-4
1070 EOF
1071
1072 cat >expect <<-EOF &&
1073 $(git rev-parse refs/heads/commit-8-4)
1074 EOF
1075 run_all_modes git rev-list --maximal-only --stdin &&
1076
1077 # All maximal.
1078 cat >input <<-\EOF &&
1079 refs/heads/commit-5-2
1080 refs/heads/commit-4-3
1081 refs/heads/commit-3-4
1082 refs/heads/commit-2-5
1083 EOF
1084
1085 cat >expect <<-EOF &&
1086 $(git rev-parse refs/heads/commit-5-2)
1087 $(git rev-parse refs/heads/commit-4-3)
1088 $(git rev-parse refs/heads/commit-3-4)
1089 $(git rev-parse refs/heads/commit-2-5)
1090 EOF
1091 run_all_modes git rev-list --maximal-only --stdin &&
1092
1093 # Mix of both.
1094 cat >input <<-\EOF &&
1095 refs/heads/commit-5-2
1096 refs/heads/commit-3-2
1097 refs/heads/commit-2-5
1098 EOF
1099
1100 cat >expect <<-EOF &&
1101 $(git rev-parse refs/heads/commit-5-2)
1102 $(git rev-parse refs/heads/commit-2-5)
1103 EOF
1104 run_all_modes git rev-list --maximal-only --stdin
1105 '
1106
1107 test_expect_success 'rev-list --maximal-only (range)' '
1108 cat >input <<-\EOF &&
1109 refs/heads/commit-1-1
1110 refs/heads/commit-2-5
1111 refs/heads/commit-6-4
1112 ^refs/heads/commit-4-5
1113 EOF
1114
1115 cat >expect <<-EOF &&
1116 $(git rev-parse refs/heads/commit-6-4)
1117 EOF
1118 run_all_modes git rev-list --maximal-only --stdin &&
1119
1120 # first-parent changes reachability: the first parent
1121 # reduces the second coordinate to 1 before reducing the
1122 # first coordinate.
1123 cat >input <<-\EOF &&
1124 refs/heads/commit-1-1
1125 refs/heads/commit-2-5
1126 refs/heads/commit-6-4
1127 ^refs/heads/commit-4-5
1128 EOF
1129
1130 cat >expect <<-EOF &&
1131 $(git rev-parse refs/heads/commit-6-4)
1132 $(git rev-parse refs/heads/commit-2-5)
1133 EOF
1134 run_all_modes git rev-list --maximal-only --stdin \
1135 --first-parent --exclude-first-parent-only
1136 '
1137
1138 test_expect_success 'rev-list --maximal-only matches merge-base --independent' '
1139 # Mix of independent and dependent
1140 git merge-base --independent \
1141 refs/heads/commit-5-2 \
1142 refs/heads/commit-3-2 \
1143 refs/heads/commit-2-5 >expect &&
1144 sort expect >expect.sorted &&
1145 git rev-list --maximal-only \
1146 refs/heads/commit-5-2 \
1147 refs/heads/commit-3-2 \
1148 refs/heads/commit-2-5 >actual &&
1149 sort actual >actual.sorted &&
1150 test_cmp expect.sorted actual.sorted &&
1151
1152 # All independent commits.
1153 git merge-base --independent \
1154 refs/heads/commit-5-2 \
1155 refs/heads/commit-4-3 \
1156 refs/heads/commit-3-4 \
1157 refs/heads/commit-2-5 >expect &&
1158 sort expect >expect.sorted &&
1159 git rev-list --maximal-only \
1160 refs/heads/commit-5-2 \
1161 refs/heads/commit-4-3 \
1162 refs/heads/commit-3-4 \
1163 refs/heads/commit-2-5 >actual &&
1164 sort actual >actual.sorted &&
1165 test_cmp expect.sorted actual.sorted &&
1166
1167 # Only one independent.
1168 git merge-base --independent \
1169 refs/heads/commit-1-1 \
1170 refs/heads/commit-4-2 \
1171 refs/heads/commit-4-4 \
1172 refs/heads/commit-8-4 >expect &&
1173 sort expect >expect.sorted &&
1174 git rev-list --maximal-only \
1175 refs/heads/commit-1-1 \
1176 refs/heads/commit-4-2 \
1177 refs/heads/commit-4-4 \
1178 refs/heads/commit-8-4 >actual &&
1179 sort actual >actual.sorted &&
1180 test_cmp expect.sorted actual.sorted
1181 '
1182
1183 # The following tests verify the early-exit optimisation in
1184 # paint_down_to_common when merge-base is invoked without --all.
1185 # Each test checks all four commit-graph configurations.
1186
1187 merge_base_all_modes () {
1188 test_when_finished rm -rf .git/objects/info/commit-graph &&
1189 git merge-base "$@" >actual &&
1190 test_cmp expect actual &&
1191 cp commit-graph-full .git/objects/info/commit-graph &&
1192 git merge-base "$@" >actual &&
1193 test_cmp expect actual &&
1194 cp commit-graph-half .git/objects/info/commit-graph &&
1195 git merge-base "$@" >actual &&
1196 test_cmp expect actual &&
1197 cp commit-graph-no-gdat .git/objects/info/commit-graph &&
1198 git merge-base "$@" >actual &&
1199 test_cmp expect actual
1200 }
1201
1202 test_expect_success 'merge-base without --all (unique base)' '
1203 git rev-parse commit-5-3 >expect &&
1204 merge_base_all_modes commit-5-7 commit-8-3
1205 '
1206
1207 test_expect_success 'merge-base without --all is one of --all results' '
1208 test_when_finished rm -rf .git/objects/info/commit-graph &&
1209
1210 cp commit-graph-full .git/objects/info/commit-graph &&
1211 git merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&
1212 git merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&
1213 test_line_count = 1 single &&
1214 test_grep -F -f single all &&
1215
1216 cp commit-graph-half .git/objects/info/commit-graph &&
1217 git merge-base --all commit-5-7 commit-4-8 commit-6-6 commit-8-3 >all &&
1218 git merge-base commit-5-7 commit-4-8 commit-6-6 commit-8-3 >single &&
1219 test_line_count = 1 single &&
1220 test_grep -F -f single all
1221 '
1222
1223 test_expect_success 'merge-base without --all, clock skew, v1 commit-graph' '
1224 git rev-parse skew-M2 >expect &&
1225 merge_base_all_modes skew-P1 skew-P2
1226 '
1227
1228 test_done