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