Merge with Linus' current tree
[git] / t / t6001-rev-list-merge-order.sh
1 #!/bin/sh
2 #
3 # Copyright (c) 2005 Jon Seymour
4 #
5
6 test_description='Tests git-rev-list --merge-order functionality'
7
8 . ./test-lib.sh
9
10 #
11 # TODO: move the following block (upto --- end ...) into testlib.sh
12 #
13 [ -d .git/refs/tags ] || mkdir -p .git/refs/tags
14
15 sed_script="";
16
17 # Answer the sha1 has associated with the tag. The tag must exist in .git or .git/refs/tags
18 tag()
19 {
20         _tag=$1
21         [ -f .git/refs/tags/$_tag ] || error "tag: \"$_tag\" does not exist"
22         cat .git/refs/tags/$_tag
23 }
24
25 # Generate a commit using the text specified to make it unique and the tree
26 # named by the tag specified.
27 unique_commit()
28 {
29         _text=$1
30         _tree=$2
31         shift 2
32         echo $_text | git-commit-tree $(tag $_tree) "$@"
33 }
34
35 # Save the output of a command into the tag specified. Prepend
36 # a substitution script for the tag onto the front of $sed_script
37 save_tag()
38 {
39         _tag=$1 
40         [ -n "$_tag" ] || error "usage: save_tag tag commit-args ..."
41         shift 1
42         "$@" >.git/refs/tags/$_tag
43         sed_script="s/$(tag $_tag)/$_tag/g${sed_script+;}$sed_script"
44 }
45
46 # Replace unhelpful sha1 hashses with their symbolic equivalents 
47 entag()
48 {
49         sed "$sed_script"
50 }
51
52 # Execute a command after first saving, then setting the GIT_AUTHOR_EMAIL
53 # tag to a specified value. Restore the original value on return.
54 as_author()
55 {
56         _author=$1
57         shift 1
58         _save=$GIT_AUTHOR_EMAIL
59
60         export GIT_AUTHOR_EMAIL="$_author"
61         "$@"
62         export GIT_AUTHOR_EMAIL="$_save"
63 }
64
65 commit_date()
66 {
67         _commit=$1
68         git-cat-file commit $_commit | sed -n "s/^committer .*> \([0-9]*\) .*/\1/p" 
69 }
70
71 on_committer_date()
72 {
73     _date=$1
74     shift 1
75     GIT_COMMITTER_DATE=$_date "$@"
76 }
77
78 # Execute a command and suppress any error output.
79 hide_error()
80 {
81         "$@" 2>/dev/null
82 }
83
84 check_output()
85 {
86         _name=$1
87         shift 1
88         if eval "$*" | entag > $_name.actual
89         then
90                 diff $_name.expected $_name.actual
91         else
92                 return 1;
93         fi
94 }
95
96 # Turn a reasonable test description into a reasonable test name.
97 # All alphanums translated into -'s which are then compressed and stripped
98 # from front and back.
99 name_from_description()
100 {
101         tr "'" '-' | tr '~`!@#$%^&*()_+={}[]|\;:"<>,/? ' '-' | tr -s '-' | tr '[A-Z]' '[a-z]' | sed "s/^-*//;s/-*\$//"
102 }
103
104
105 # Execute the test described by the first argument, by eval'ing
106 # command line specified in the 2nd argument. Check the status code
107 # is zero and that the output matches the stream read from 
108 # stdin.
109 test_output_expect_success()
110 {       
111         _description=$1
112         _test=$2
113         [ $# -eq 2 ] || error "usage: test_output_expect_success description test <<EOF ... EOF"
114         _name=$(echo $_description | name_from_description)
115         cat > $_name.expected
116         test_expect_success "$_description" "check_output $_name \"$_test\"" 
117 }
118
119 # --- end of stuff to move ---
120
121 # test-case specific test function
122 check_adjacency()
123 {
124     read previous
125     echo "= $previous"
126     while read next
127     do
128         if ! (git-cat-file commit $previous | grep "^parent $next" >/dev/null)
129         then
130             echo "^ $next"
131         else
132             echo "| $next"
133         fi
134         previous=$next
135     done
136 }
137
138 list_duplicates()
139 {
140     "$@" | sort | uniq -d
141 }
142
143 grep_stderr()
144 {
145     args=$1
146     shift 1
147     "$@" 2>&1 | grep "$args"
148 }
149
150 date >path0
151 git-update-cache --add path0
152 save_tag tree git-write-tree
153 on_committer_date "1971-08-16 00:00:00" hide_error save_tag root unique_commit root tree
154 on_committer_date "1971-08-16 00:00:01" save_tag l0 unique_commit l0 tree -p root
155 on_committer_date "1971-08-16 00:00:02" save_tag l1 unique_commit l1 tree -p l0
156 on_committer_date "1971-08-16 00:00:03" save_tag l2 unique_commit l2 tree -p l1
157 on_committer_date "1971-08-16 00:00:04" save_tag a0 unique_commit a0 tree -p l2
158 on_committer_date "1971-08-16 00:00:05" save_tag a1 unique_commit a1 tree -p a0
159 on_committer_date "1971-08-16 00:00:06" save_tag b1 unique_commit b1 tree -p a0
160 on_committer_date "1971-08-16 00:00:07" save_tag c1 unique_commit c1 tree -p b1
161 on_committer_date "1971-08-16 00:00:08" as_author foobar@example.com save_tag b2 unique_commit b2 tree -p b1
162 on_committer_date "1971-08-16 00:00:09" save_tag b3 unique_commit b2 tree -p b2
163 on_committer_date "1971-08-16 00:00:10" save_tag c2 unique_commit c2 tree -p c1 -p b2
164 on_committer_date "1971-08-16 00:00:11" save_tag c3 unique_commit c3 tree -p c2
165 on_committer_date "1971-08-16 00:00:12" save_tag a2 unique_commit a2 tree -p a1
166 on_committer_date "1971-08-16 00:00:13" save_tag a3 unique_commit a3 tree -p a2
167 on_committer_date "1971-08-16 00:00:14" save_tag b4 unique_commit b4 tree -p b3 -p a3
168 on_committer_date "1971-08-16 00:00:15" save_tag a4 unique_commit a4 tree -p a3 -p b4 -p c3
169 on_committer_date "1971-08-16 00:00:16" save_tag l3 unique_commit l3 tree -p a4
170 on_committer_date "1971-08-16 00:00:17" save_tag l4 unique_commit l4 tree -p l3
171 on_committer_date "1971-08-16 00:00:18" save_tag l5 unique_commit l5 tree -p l4
172 on_committer_date "1971-08-16 00:00:19" save_tag m1 unique_commit m1 tree -p a4 -p c3
173 on_committer_date "1971-08-16 00:00:20" save_tag m2 unique_commit m2 tree -p c3 -p a4
174 on_committer_date "1971-08-16 00:00:21" hide_error save_tag alt_root unique_commit alt_root tree
175 on_committer_date "1971-08-16 00:00:22" save_tag r0 unique_commit r0 tree -p alt_root
176 on_committer_date "1971-08-16 00:00:23" save_tag r1 unique_commit r1 tree -p r0
177 on_committer_date "1971-08-16 00:00:24" save_tag l5r1 unique_commit l5r1 tree -p l5 -p r1
178 on_committer_date "1971-08-16 00:00:25" save_tag r1l5 unique_commit r1l5 tree -p r1 -p l5
179
180
181 #
182 # note: as of 20/6, it isn't possible to create duplicate parents, so this
183 # can't be tested.
184 #
185 #on_committer_date "1971-08-16 00:00:20" save_tag m3 unique_commit m3 tree -p c3 -p a4 -p c3
186 hide_error save_tag e1 as_author e@example.com unique_commit e1 tree
187 save_tag e2 as_author e@example.com unique_commit e2 tree -p e1
188 save_tag f1 as_author f@example.com unique_commit f1 tree -p e1
189 save_tag e3 as_author e@example.com unique_commit e3 tree -p e2
190 save_tag f2 as_author f@example.com unique_commit f2 tree -p f1
191 save_tag e4 as_author e@example.com unique_commit e4 tree -p e3 -p f2
192 save_tag e5 as_author e@example.com unique_commit e5 tree -p e4
193 save_tag f3 as_author f@example.com unique_commit f3 tree -p f2
194 save_tag f4 as_author f@example.com unique_commit f4 tree -p f3
195 save_tag e6 as_author e@example.com unique_commit e6 tree -p e5 -p f4
196 save_tag f5 as_author f@example.com unique_commit f5 tree -p f4
197 save_tag f6 as_author f@example.com unique_commit f6 tree -p f5 -p e6
198 save_tag e7 as_author e@example.com unique_commit e7 tree -p e6
199 save_tag e8 as_author e@example.com unique_commit e8 tree -p e7
200 save_tag e9 as_author e@example.com unique_commit e9 tree -p e8
201 save_tag f7 as_author f@example.com unique_commit f7 tree -p f6
202 save_tag f8 as_author f@example.com unique_commit f8 tree -p f7
203 save_tag f9 as_author f@example.com unique_commit f9 tree -p f8
204 save_tag e10 as_author e@example.com unique_commit e1 tree -p e9 -p f8
205
206 hide_error save_tag g0 unique_commit g0 tree
207 save_tag g1 unique_commit g1 tree -p g0
208 save_tag h1 unique_commit g2 tree -p g0
209 save_tag g2 unique_commit g3 tree -p g1 -p h1
210 save_tag h2 unique_commit g4 tree -p g2
211 save_tag g3 unique_commit g5 tree -p g2
212 save_tag g4 unique_commit g6 tree -p g3 -p h2
213
214 tag l5 > .git/HEAD
215
216 #
217 # cd to t/trash and use 
218 #
219 #    git-rev-list ... 2>&1 | sed "$(cat sed.script)" 
220 #
221 # if you ever want to manually debug the operation of git-rev-list
222 #
223 echo $sed_script > sed.script
224
225 test_expect_success 'rev-list has correct number of entries' 'git-rev-list HEAD | wc -l | tr -s " "' <<EOF
226 19
227 EOF
228
229 normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
230 merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
231 test_expect_success '--merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
232 test_output_expect_success 'simple merge order' 'git-rev-list --merge-order --show-breaks HEAD' <<EOF
233 = l5
234 | l4
235 | l3
236 = a4
237 | c3
238 | c2
239 | c1
240 ^ b4
241 | b3
242 | b2
243 | b1
244 ^ a3
245 | a2
246 | a1
247 = a0
248 | l2
249 | l1
250 | l0
251 = root
252 EOF
253
254 test_output_expect_success 'two diamonds merge order (g6)' 'git-rev-list --merge-order --show-breaks g4' <<EOF
255 = g4
256 | h2
257 ^ g3
258 = g2
259 | h1
260 ^ g1
261 = g0
262 EOF
263
264 test_output_expect_success 'multiple heads' 'git-rev-list --merge-order a3 b3 c3' <<EOF
265 c3
266 c2
267 c1
268 b3
269 b2
270 b1
271 a3
272 a2
273 a1
274 a0
275 l2
276 l1
277 l0
278 root
279 EOF
280
281 test_output_expect_success 'multiple heads, prune at a1' 'git-rev-list --merge-order a3 b3 c3 ^a1' <<EOF
282 c3
283 c2
284 c1
285 b3
286 b2
287 b1
288 a3
289 a2
290 EOF
291
292 test_output_expect_success 'multiple heads, prune at l1' 'git-rev-list --merge-order a3 b3 c3 ^l1' <<EOF
293 c3
294 c2
295 c1
296 b3
297 b2
298 b1
299 a3
300 a2
301 a1
302 a0
303 l2
304 EOF
305
306 test_output_expect_success 'cross-epoch, head at l5, prune at l1' 'git-rev-list --merge-order l5 ^l1' <<EOF
307 l5
308 l4
309 l3
310 a4
311 c3
312 c2
313 c1
314 b4
315 b3
316 b2
317 b1
318 a3
319 a2
320 a1
321 a0
322 l2
323 EOF
324
325 test_output_expect_success 'duplicated head arguments' 'git-rev-list --merge-order l5 l5 ^l1' <<EOF
326 l5
327 l4
328 l3
329 a4
330 c3
331 c2
332 c1
333 b4
334 b3
335 b2
336 b1
337 a3
338 a2
339 a1
340 a0
341 l2
342 EOF
343
344 test_output_expect_success 'prune near merge' 'git-rev-list --merge-order a4 ^c3' <<EOF
345 a4
346 b4
347 b3
348 a3
349 a2
350 a1
351 EOF
352
353 test_output_expect_success "head has no parent" 'git-rev-list --merge-order --show-breaks root' <<EOF
354 = root
355 EOF
356
357 test_output_expect_success "two nodes - one head, one base" 'git-rev-list --merge-order --show-breaks l0' <<EOF
358 = l0
359 = root
360 EOF
361
362 test_output_expect_success "three nodes one head, one internal, one base" 'git-rev-list --merge-order --show-breaks l1' <<EOF
363 = l1
364 | l0
365 = root
366 EOF
367
368 test_output_expect_success "linear prune l2 ^root" 'git-rev-list --merge-order --show-breaks l2 ^root' <<EOF
369 ^ l2
370 | l1
371 | l0
372 EOF
373
374 test_output_expect_success "linear prune l2 ^l0" 'git-rev-list --merge-order --show-breaks l2 ^l0' <<EOF
375 ^ l2
376 | l1
377 EOF
378
379 test_output_expect_success "linear prune l2 ^l1" 'git-rev-list --merge-order --show-breaks l2 ^l1' <<EOF
380 ^ l2
381 EOF
382
383 test_output_expect_success "linear prune l5 ^a4" 'git-rev-list --merge-order --show-breaks l5 ^a4' <<EOF
384 ^ l5
385 | l4
386 | l3
387 EOF
388
389 test_output_expect_success "linear prune l5 ^l3" 'git-rev-list --merge-order --show-breaks l5 ^l3' <<EOF
390 ^ l5
391 | l4
392 EOF
393
394 test_output_expect_success "linear prune l5 ^l4" 'git-rev-list --merge-order --show-breaks l5 ^l4' <<EOF
395 ^ l5
396 EOF
397
398 test_output_expect_success "max-count 10 - merge order" 'git-rev-list --merge-order --show-breaks --max-count=10 l5' <<EOF
399 = l5
400 | l4
401 | l3
402 = a4
403 | c3
404 | c2
405 | c1
406 ^ b4
407 | b3
408 | b2
409 EOF
410
411 test_output_expect_success "max-count 10 - non merge order" 'git-rev-list --max-count=10 l5' <<EOF
412 l5
413 l4
414 l3
415 a4
416 b4
417 a3
418 a2
419 c3
420 c2
421 b3
422 EOF
423
424 test_output_expect_success '--max-age=c3, no --merge-order' "git-rev-list --max-age=$(commit_date c3) l5" <<EOF
425 l5
426 l4
427 l3
428 a4
429 b4
430 a3
431 a2
432 c3
433 EOF
434
435 test_output_expect_success '--max-age=c3, --merge-order' "git-rev-list --merge-order --max-age=$(commit_date c3) l5" <<EOF
436 l5
437 l4
438 l3
439 a4
440 c3
441 b4
442 a3
443 a2
444 EOF
445
446 test_output_expect_success 'one specified head reachable from another a4, c3, --merge-order' "list_duplicates git-rev-list --merge-order a4 c3" <<EOF
447 EOF
448
449 test_output_expect_success 'one specified head reachable from another c3, a4, --merge-order' "list_duplicates git-rev-list --merge-order c3 a4" <<EOF
450 EOF
451
452 test_output_expect_success 'one specified head reachable from another a4, c3, no --merge-order' "list_duplicates git-rev-list a4 c3" <<EOF
453 EOF
454
455 test_output_expect_success 'one specified head reachable from another c3, a4, no --merge-order' "list_duplicates git-rev-list c3 a4" <<EOF
456 EOF
457
458 test_output_expect_success 'graph with c3 and a4 parents of head' "list_duplicates git-rev-list m1" <<EOF
459 EOF
460
461 test_output_expect_success 'graph with a4 and c3 parents of head' "list_duplicates git-rev-list m2" <<EOF
462 EOF
463
464 test_expect_success "head ^head --merge-order" 'git-rev-list --merge-order --show-breaks a3 ^a3' <<EOF
465 EOF
466
467 #
468 # can't test this now - duplicate parents can't be created
469 #
470 #test_output_expect_success 'duplicate parents' 'git-rev-list --parents --merge-order --show-breaks m3' <<EOF
471 #= m3 c3 a4 c3
472 #| a4 c3 b4 a3
473 #| b4 a3 b3
474 #| b3 b2
475 #^ a3 a2
476 #| a2 a1
477 #| a1 a0
478 #^ c3 c2
479 #| c2 b2 c1
480 #| b2 b1
481 #^ c1 b1
482 #| b1 a0
483 #= a0 l2
484 #| l2 l1
485 #| l1 l0
486 #| l0 root
487 #= root
488 #EOF
489
490 test_expect_success "head ^head no --merge-order" 'git-rev-list a3 ^a3' <<EOF
491 EOF
492
493 test_output_expect_success 'simple merge order (l5r1)' 'git-rev-list --merge-order --show-breaks l5r1' <<EOF
494 = l5r1
495 | r1
496 | r0
497 | alt_root
498 ^ l5
499 | l4
500 | l3
501 | a4
502 | c3
503 | c2
504 | c1
505 ^ b4
506 | b3
507 | b2
508 | b1
509 ^ a3
510 | a2
511 | a1
512 | a0
513 | l2
514 | l1
515 | l0
516 = root
517 EOF
518
519 test_output_expect_success 'simple merge order (r1l5)' 'git-rev-list --merge-order --show-breaks r1l5' <<EOF
520 = r1l5
521 | l5
522 | l4
523 | l3
524 | a4
525 | c3
526 | c2
527 | c1
528 ^ b4
529 | b3
530 | b2
531 | b1
532 ^ a3
533 | a2
534 | a1
535 | a0
536 | l2
537 | l1
538 | l0
539 | root
540 ^ r1
541 | r0
542 = alt_root
543 EOF
544
545 test_output_expect_success "don't print things unreachable from one branch" "git-rev-list a3 ^b3 --merge-order" <<EOF
546 a3
547 a2
548 a1
549 EOF
550
551 #
552 #
553
554 test_done