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