Merge branch 'hx/push-atomic-with-cert'
[git] / t / t6600-test-reach.sh
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
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
50                 done
51         done &&
52         git commit-graph write --reachable &&
53         mv .git/objects/info/commit-graph commit-graph-full &&
54         chmod u+w commit-graph-full &&
55         git show-ref -s commit-5-5 | git commit-graph write --stdin-commits &&
56         mv .git/objects/info/commit-graph commit-graph-half &&
57         chmod u+w commit-graph-half &&
58         git config core.commitGraph true
59 '
60
61 run_three_modes () {
62         test_when_finished rm -rf .git/objects/info/commit-graph &&
63         "$@" <input >actual &&
64         test_cmp expect actual &&
65         cp commit-graph-full .git/objects/info/commit-graph &&
66         "$@" <input >actual &&
67         test_cmp expect actual &&
68         cp commit-graph-half .git/objects/info/commit-graph &&
69         "$@" <input >actual &&
70         test_cmp expect actual
71 }
72
73 test_three_modes () {
74         run_three_modes test-tool reach "$@"
75 }
76
77 test_expect_success 'ref_newer:miss' '
78         cat >input <<-\EOF &&
79         A:commit-5-7
80         B:commit-4-9
81         EOF
82         echo "ref_newer(A,B):0" >expect &&
83         test_three_modes ref_newer
84 '
85
86 test_expect_success 'ref_newer:hit' '
87         cat >input <<-\EOF &&
88         A:commit-5-7
89         B:commit-2-3
90         EOF
91         echo "ref_newer(A,B):1" >expect &&
92         test_three_modes ref_newer
93 '
94
95 test_expect_success 'in_merge_bases:hit' '
96         cat >input <<-\EOF &&
97         A:commit-5-7
98         B:commit-8-8
99         EOF
100         echo "in_merge_bases(A,B):1" >expect &&
101         test_three_modes in_merge_bases
102 '
103
104 test_expect_success 'in_merge_bases:miss' '
105         cat >input <<-\EOF &&
106         A:commit-6-8
107         B:commit-5-9
108         EOF
109         echo "in_merge_bases(A,B):0" >expect &&
110         test_three_modes in_merge_bases
111 '
112
113 test_expect_success 'in_merge_bases_many:hit' '
114         cat >input <<-\EOF &&
115         A:commit-6-8
116         X:commit-6-9
117         X:commit-5-7
118         EOF
119         echo "in_merge_bases_many(A,X):1" >expect &&
120         test_three_modes in_merge_bases_many
121 '
122
123 test_expect_success 'in_merge_bases_many:miss' '
124         cat >input <<-\EOF &&
125         A:commit-6-8
126         X:commit-7-7
127         X:commit-8-6
128         EOF
129         echo "in_merge_bases_many(A,X):0" >expect &&
130         test_three_modes in_merge_bases_many
131 '
132
133 test_expect_success 'in_merge_bases_many:miss-heuristic' '
134         cat >input <<-\EOF &&
135         A:commit-6-8
136         X:commit-7-5
137         X:commit-6-6
138         EOF
139         echo "in_merge_bases_many(A,X):0" >expect &&
140         test_three_modes in_merge_bases_many
141 '
142
143 test_expect_success 'is_descendant_of:hit' '
144         cat >input <<-\EOF &&
145         A:commit-5-7
146         X:commit-4-8
147         X:commit-6-6
148         X:commit-1-1
149         EOF
150         echo "is_descendant_of(A,X):1" >expect &&
151         test_three_modes is_descendant_of
152 '
153
154 test_expect_success 'is_descendant_of:miss' '
155         cat >input <<-\EOF &&
156         A:commit-6-8
157         X:commit-5-9
158         X:commit-4-10
159         X:commit-7-6
160         EOF
161         echo "is_descendant_of(A,X):0" >expect &&
162         test_three_modes is_descendant_of
163 '
164
165 test_expect_success 'get_merge_bases_many' '
166         cat >input <<-\EOF &&
167         A:commit-5-7
168         X:commit-4-8
169         X:commit-6-6
170         X:commit-8-3
171         EOF
172         {
173                 echo "get_merge_bases_many(A,X):" &&
174                 git rev-parse commit-5-6 \
175                               commit-4-7 | sort
176         } >expect &&
177         test_three_modes get_merge_bases_many
178 '
179
180 test_expect_success 'reduce_heads' '
181         cat >input <<-\EOF &&
182         X:commit-1-10
183         X:commit-2-8
184         X:commit-3-6
185         X:commit-4-4
186         X:commit-1-7
187         X:commit-2-5
188         X:commit-3-3
189         X:commit-5-1
190         EOF
191         {
192                 echo "reduce_heads(X):" &&
193                 git rev-parse commit-5-1 \
194                               commit-4-4 \
195                               commit-3-6 \
196                               commit-2-8 \
197                               commit-1-10 | sort
198         } >expect &&
199         test_three_modes reduce_heads
200 '
201
202 test_expect_success 'can_all_from_reach:hit' '
203         cat >input <<-\EOF &&
204         X:commit-2-10
205         X:commit-3-9
206         X:commit-4-8
207         X:commit-5-7
208         X:commit-6-6
209         X:commit-7-5
210         X:commit-8-4
211         X:commit-9-3
212         Y:commit-1-9
213         Y:commit-2-8
214         Y:commit-3-7
215         Y:commit-4-6
216         Y:commit-5-5
217         Y:commit-6-4
218         Y:commit-7-3
219         Y:commit-8-1
220         EOF
221         echo "can_all_from_reach(X,Y):1" >expect &&
222         test_three_modes can_all_from_reach
223 '
224
225 test_expect_success 'can_all_from_reach:miss' '
226         cat >input <<-\EOF &&
227         X:commit-2-10
228         X:commit-3-9
229         X:commit-4-8
230         X:commit-5-7
231         X:commit-6-6
232         X:commit-7-5
233         X:commit-8-4
234         X:commit-9-3
235         Y:commit-1-9
236         Y:commit-2-8
237         Y:commit-3-7
238         Y:commit-4-6
239         Y:commit-5-5
240         Y:commit-6-4
241         Y:commit-8-5
242         EOF
243         echo "can_all_from_reach(X,Y):0" >expect &&
244         test_three_modes can_all_from_reach
245 '
246
247 test_expect_success 'can_all_from_reach_with_flag: tags case' '
248         cat >input <<-\EOF &&
249         X:tag-2-10
250         X:tag-3-9
251         X:tag-4-8
252         X:commit-5-7
253         X:commit-6-6
254         X:commit-7-5
255         X:commit-8-4
256         X:commit-9-3
257         Y:tag-1-9
258         Y:tag-2-8
259         Y:tag-3-7
260         Y:commit-4-6
261         Y:commit-5-5
262         Y:commit-6-4
263         Y:commit-7-3
264         Y:commit-8-1
265         EOF
266         echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
267         test_three_modes can_all_from_reach_with_flag
268 '
269
270 test_expect_success 'commit_contains:hit' '
271         cat >input <<-\EOF &&
272         A:commit-7-7
273         X:commit-2-10
274         X:commit-3-9
275         X:commit-4-8
276         X:commit-5-7
277         X:commit-6-6
278         X:commit-7-5
279         X:commit-8-4
280         X:commit-9-3
281         EOF
282         echo "commit_contains(_,A,X,_):1" >expect &&
283         test_three_modes commit_contains &&
284         test_three_modes commit_contains --tag
285 '
286
287 test_expect_success 'commit_contains:miss' '
288         cat >input <<-\EOF &&
289         A:commit-6-5
290         X:commit-2-10
291         X:commit-3-9
292         X:commit-4-8
293         X:commit-5-7
294         X:commit-6-6
295         X:commit-7-5
296         X:commit-8-4
297         X:commit-9-3
298         EOF
299         echo "commit_contains(_,A,X,_):0" >expect &&
300         test_three_modes commit_contains &&
301         test_three_modes commit_contains --tag
302 '
303
304 test_expect_success 'rev-list: basic topo-order' '
305         git rev-parse \
306                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
307                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
308                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
309                 commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
310                 commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
311                 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
312         >expect &&
313         run_three_modes git rev-list --topo-order commit-6-6
314 '
315
316 test_expect_success 'rev-list: first-parent topo-order' '
317         git rev-parse \
318                 commit-6-6 \
319                 commit-6-5 \
320                 commit-6-4 \
321                 commit-6-3 \
322                 commit-6-2 \
323                 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
324         >expect &&
325         run_three_modes git rev-list --first-parent --topo-order commit-6-6
326 '
327
328 test_expect_success 'rev-list: range topo-order' '
329         git rev-parse \
330                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
331                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
332                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
333                 commit-6-3 commit-5-3 commit-4-3 \
334                 commit-6-2 commit-5-2 commit-4-2 \
335                 commit-6-1 commit-5-1 commit-4-1 \
336         >expect &&
337         run_three_modes git rev-list --topo-order commit-3-3..commit-6-6
338 '
339
340 test_expect_success 'rev-list: range topo-order' '
341         git rev-parse \
342                 commit-6-6 commit-5-6 commit-4-6 \
343                 commit-6-5 commit-5-5 commit-4-5 \
344                 commit-6-4 commit-5-4 commit-4-4 \
345                 commit-6-3 commit-5-3 commit-4-3 \
346                 commit-6-2 commit-5-2 commit-4-2 \
347                 commit-6-1 commit-5-1 commit-4-1 \
348         >expect &&
349         run_three_modes git rev-list --topo-order commit-3-8..commit-6-6
350 '
351
352 test_expect_success 'rev-list: first-parent range topo-order' '
353         git rev-parse \
354                 commit-6-6 \
355                 commit-6-5 \
356                 commit-6-4 \
357                 commit-6-3 \
358                 commit-6-2 \
359                 commit-6-1 commit-5-1 commit-4-1 \
360         >expect &&
361         run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
362 '
363
364 test_expect_success 'rev-list: ancestry-path topo-order' '
365         git rev-parse \
366                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
367                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
368                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
369                 commit-6-3 commit-5-3 commit-4-3 \
370         >expect &&
371         run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
372 '
373
374 test_expect_success 'rev-list: symmetric difference topo-order' '
375         git rev-parse \
376                 commit-6-6 commit-5-6 commit-4-6 \
377                 commit-6-5 commit-5-5 commit-4-5 \
378                 commit-6-4 commit-5-4 commit-4-4 \
379                 commit-6-3 commit-5-3 commit-4-3 \
380                 commit-6-2 commit-5-2 commit-4-2 \
381                 commit-6-1 commit-5-1 commit-4-1 \
382                 commit-3-8 commit-2-8 commit-1-8 \
383                 commit-3-7 commit-2-7 commit-1-7 \
384         >expect &&
385         run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
386 '
387
388 test_expect_success 'get_reachable_subset:all' '
389         cat >input <<-\EOF &&
390         X:commit-9-1
391         X:commit-8-3
392         X:commit-7-5
393         X:commit-6-6
394         X:commit-1-7
395         Y:commit-3-3
396         Y:commit-1-7
397         Y:commit-5-6
398         EOF
399         (
400                 echo "get_reachable_subset(X,Y)" &&
401                 git rev-parse commit-3-3 \
402                               commit-1-7 \
403                               commit-5-6 | sort
404         ) >expect &&
405         test_three_modes get_reachable_subset
406 '
407
408 test_expect_success 'get_reachable_subset:some' '
409         cat >input <<-\EOF &&
410         X:commit-9-1
411         X:commit-8-3
412         X:commit-7-5
413         X:commit-1-7
414         Y:commit-3-3
415         Y:commit-1-7
416         Y:commit-5-6
417         EOF
418         (
419                 echo "get_reachable_subset(X,Y)" &&
420                 git rev-parse commit-3-3 \
421                               commit-1-7 | sort
422         ) >expect &&
423         test_three_modes get_reachable_subset
424 '
425
426 test_expect_success 'get_reachable_subset:none' '
427         cat >input <<-\EOF &&
428         X:commit-9-1
429         X:commit-8-3
430         X:commit-7-5
431         X:commit-1-7
432         Y:commit-9-3
433         Y:commit-7-6
434         Y:commit-2-8
435         EOF
436         echo "get_reachable_subset(X,Y)" >expect &&
437         test_three_modes get_reachable_subset
438 '
439
440 test_done