Merge branch 'en/dir-nonbare-embedded'
[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 'is_descendant_of:hit' '
114         cat >input <<-\EOF &&
115         A:commit-5-7
116         X:commit-4-8
117         X:commit-6-6
118         X:commit-1-1
119         EOF
120         echo "is_descendant_of(A,X):1" >expect &&
121         test_three_modes is_descendant_of
122 '
123
124 test_expect_success 'is_descendant_of:miss' '
125         cat >input <<-\EOF &&
126         A:commit-6-8
127         X:commit-5-9
128         X:commit-4-10
129         X:commit-7-6
130         EOF
131         echo "is_descendant_of(A,X):0" >expect &&
132         test_three_modes is_descendant_of
133 '
134
135 test_expect_success 'get_merge_bases_many' '
136         cat >input <<-\EOF &&
137         A:commit-5-7
138         X:commit-4-8
139         X:commit-6-6
140         X:commit-8-3
141         EOF
142         {
143                 echo "get_merge_bases_many(A,X):" &&
144                 git rev-parse commit-5-6 \
145                               commit-4-7 | sort
146         } >expect &&
147         test_three_modes get_merge_bases_many
148 '
149
150 test_expect_success 'reduce_heads' '
151         cat >input <<-\EOF &&
152         X:commit-1-10
153         X:commit-2-8
154         X:commit-3-6
155         X:commit-4-4
156         X:commit-1-7
157         X:commit-2-5
158         X:commit-3-3
159         X:commit-5-1
160         EOF
161         {
162                 echo "reduce_heads(X):" &&
163                 git rev-parse commit-5-1 \
164                               commit-4-4 \
165                               commit-3-6 \
166                               commit-2-8 \
167                               commit-1-10 | sort
168         } >expect &&
169         test_three_modes reduce_heads
170 '
171
172 test_expect_success 'can_all_from_reach:hit' '
173         cat >input <<-\EOF &&
174         X:commit-2-10
175         X:commit-3-9
176         X:commit-4-8
177         X:commit-5-7
178         X:commit-6-6
179         X:commit-7-5
180         X:commit-8-4
181         X:commit-9-3
182         Y:commit-1-9
183         Y:commit-2-8
184         Y:commit-3-7
185         Y:commit-4-6
186         Y:commit-5-5
187         Y:commit-6-4
188         Y:commit-7-3
189         Y:commit-8-1
190         EOF
191         echo "can_all_from_reach(X,Y):1" >expect &&
192         test_three_modes can_all_from_reach
193 '
194
195 test_expect_success 'can_all_from_reach:miss' '
196         cat >input <<-\EOF &&
197         X:commit-2-10
198         X:commit-3-9
199         X:commit-4-8
200         X:commit-5-7
201         X:commit-6-6
202         X:commit-7-5
203         X:commit-8-4
204         X:commit-9-3
205         Y:commit-1-9
206         Y:commit-2-8
207         Y:commit-3-7
208         Y:commit-4-6
209         Y:commit-5-5
210         Y:commit-6-4
211         Y:commit-8-5
212         EOF
213         echo "can_all_from_reach(X,Y):0" >expect &&
214         test_three_modes can_all_from_reach
215 '
216
217 test_expect_success 'can_all_from_reach_with_flag: tags case' '
218         cat >input <<-\EOF &&
219         X:tag-2-10
220         X:tag-3-9
221         X:tag-4-8
222         X:commit-5-7
223         X:commit-6-6
224         X:commit-7-5
225         X:commit-8-4
226         X:commit-9-3
227         Y:tag-1-9
228         Y:tag-2-8
229         Y:tag-3-7
230         Y:commit-4-6
231         Y:commit-5-5
232         Y:commit-6-4
233         Y:commit-7-3
234         Y:commit-8-1
235         EOF
236         echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
237         test_three_modes can_all_from_reach_with_flag
238 '
239
240 test_expect_success 'commit_contains:hit' '
241         cat >input <<-\EOF &&
242         A:commit-7-7
243         X:commit-2-10
244         X:commit-3-9
245         X:commit-4-8
246         X:commit-5-7
247         X:commit-6-6
248         X:commit-7-5
249         X:commit-8-4
250         X:commit-9-3
251         EOF
252         echo "commit_contains(_,A,X,_):1" >expect &&
253         test_three_modes commit_contains &&
254         test_three_modes commit_contains --tag
255 '
256
257 test_expect_success 'commit_contains:miss' '
258         cat >input <<-\EOF &&
259         A:commit-6-5
260         X:commit-2-10
261         X:commit-3-9
262         X:commit-4-8
263         X:commit-5-7
264         X:commit-6-6
265         X:commit-7-5
266         X:commit-8-4
267         X:commit-9-3
268         EOF
269         echo "commit_contains(_,A,X,_):0" >expect &&
270         test_three_modes commit_contains &&
271         test_three_modes commit_contains --tag
272 '
273
274 test_expect_success 'rev-list: basic topo-order' '
275         git rev-parse \
276                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
277                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
278                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
279                 commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
280                 commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
281                 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
282         >expect &&
283         run_three_modes git rev-list --topo-order commit-6-6
284 '
285
286 test_expect_success 'rev-list: first-parent topo-order' '
287         git rev-parse \
288                 commit-6-6 \
289                 commit-6-5 \
290                 commit-6-4 \
291                 commit-6-3 \
292                 commit-6-2 \
293                 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
294         >expect &&
295         run_three_modes git rev-list --first-parent --topo-order commit-6-6
296 '
297
298 test_expect_success 'rev-list: range topo-order' '
299         git rev-parse \
300                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
301                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
302                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
303                 commit-6-3 commit-5-3 commit-4-3 \
304                 commit-6-2 commit-5-2 commit-4-2 \
305                 commit-6-1 commit-5-1 commit-4-1 \
306         >expect &&
307         run_three_modes git rev-list --topo-order commit-3-3..commit-6-6
308 '
309
310 test_expect_success 'rev-list: range topo-order' '
311         git rev-parse \
312                 commit-6-6 commit-5-6 commit-4-6 \
313                 commit-6-5 commit-5-5 commit-4-5 \
314                 commit-6-4 commit-5-4 commit-4-4 \
315                 commit-6-3 commit-5-3 commit-4-3 \
316                 commit-6-2 commit-5-2 commit-4-2 \
317                 commit-6-1 commit-5-1 commit-4-1 \
318         >expect &&
319         run_three_modes git rev-list --topo-order commit-3-8..commit-6-6
320 '
321
322 test_expect_success 'rev-list: first-parent range topo-order' '
323         git rev-parse \
324                 commit-6-6 \
325                 commit-6-5 \
326                 commit-6-4 \
327                 commit-6-3 \
328                 commit-6-2 \
329                 commit-6-1 commit-5-1 commit-4-1 \
330         >expect &&
331         run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
332 '
333
334 test_expect_success 'rev-list: ancestry-path topo-order' '
335         git rev-parse \
336                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
337                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
338                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
339                 commit-6-3 commit-5-3 commit-4-3 \
340         >expect &&
341         run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
342 '
343
344 test_expect_success 'rev-list: symmetric difference topo-order' '
345         git rev-parse \
346                 commit-6-6 commit-5-6 commit-4-6 \
347                 commit-6-5 commit-5-5 commit-4-5 \
348                 commit-6-4 commit-5-4 commit-4-4 \
349                 commit-6-3 commit-5-3 commit-4-3 \
350                 commit-6-2 commit-5-2 commit-4-2 \
351                 commit-6-1 commit-5-1 commit-4-1 \
352                 commit-3-8 commit-2-8 commit-1-8 \
353                 commit-3-7 commit-2-7 commit-1-7 \
354         >expect &&
355         run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
356 '
357
358 test_expect_success 'get_reachable_subset:all' '
359         cat >input <<-\EOF &&
360         X:commit-9-1
361         X:commit-8-3
362         X:commit-7-5
363         X:commit-6-6
364         X:commit-1-7
365         Y:commit-3-3
366         Y:commit-1-7
367         Y:commit-5-6
368         EOF
369         (
370                 echo "get_reachable_subset(X,Y)" &&
371                 git rev-parse commit-3-3 \
372                               commit-1-7 \
373                               commit-5-6 | sort
374         ) >expect &&
375         test_three_modes get_reachable_subset
376 '
377
378 test_expect_success 'get_reachable_subset:some' '
379         cat >input <<-\EOF &&
380         X:commit-9-1
381         X:commit-8-3
382         X:commit-7-5
383         X:commit-1-7
384         Y:commit-3-3
385         Y:commit-1-7
386         Y:commit-5-6
387         EOF
388         (
389                 echo "get_reachable_subset(X,Y)" &&
390                 git rev-parse commit-3-3 \
391                               commit-1-7 | sort
392         ) >expect &&
393         test_three_modes get_reachable_subset
394 '
395
396 test_expect_success 'get_reachable_subset:none' '
397         cat >input <<-\EOF &&
398         X:commit-9-1
399         X:commit-8-3
400         X:commit-7-5
401         X:commit-1-7
402         Y:commit-9-3
403         Y:commit-7-6
404         Y:commit-2-8
405         EOF
406         echo "get_reachable_subset(X,Y)" >expect &&
407         test_three_modes get_reachable_subset
408 '
409
410 test_done