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 || return 1
  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 || return 1
  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 -c commitGraph.generationVersion=1 commit-graph write --reachable &&
  59         mv .git/objects/info/commit-graph commit-graph-no-gdat &&
  60         chmod u+w commit-graph-no-gdat &&
  61         git config core.commitGraph true
  62 '
  63
  64 run_all_modes () {
  65         test_when_finished rm -rf .git/objects/info/commit-graph &&
  66         "$@" <input >actual &&
  67         test_cmp expect actual &&
  68         cp commit-graph-full .git/objects/info/commit-graph &&
  69         "$@" <input >actual &&
  70         test_cmp expect actual &&
  71         cp commit-graph-half .git/objects/info/commit-graph &&
  72         "$@" <input >actual &&
  73         test_cmp expect actual &&
  74         cp commit-graph-no-gdat .git/objects/info/commit-graph &&
  75         "$@" <input >actual &&
  76         test_cmp expect actual
  77 }
  78
  79 test_all_modes () {
  80         run_all_modes test-tool reach "$@"
  81 }
  82
  83 test_expect_success 'ref_newer:miss' '
  84         cat >input <<-\EOF &&
  85         A:commit-5-7
  86         B:commit-4-9
  87         EOF
  88         echo "ref_newer(A,B):0" >expect &&
  89         test_all_modes ref_newer
  90 '
  91
  92 test_expect_success 'ref_newer:hit' '
  93         cat >input <<-\EOF &&
  94         A:commit-5-7
  95         B:commit-2-3
  96         EOF
  97         echo "ref_newer(A,B):1" >expect &&
  98         test_all_modes ref_newer
  99 '
 100
 101 test_expect_success 'in_merge_bases:hit' '
 102         cat >input <<-\EOF &&
 103         A:commit-5-7
 104         B:commit-8-8
 105         EOF
 106         echo "in_merge_bases(A,B):1" >expect &&
 107         test_all_modes in_merge_bases
 108 '
 109
 110 test_expect_success 'in_merge_bases:miss' '
 111         cat >input <<-\EOF &&
 112         A:commit-6-8
 113         B:commit-5-9
 114         EOF
 115         echo "in_merge_bases(A,B):0" >expect &&
 116         test_all_modes in_merge_bases
 117 '
 118
 119 test_expect_success 'in_merge_bases_many:hit' '
 120         cat >input <<-\EOF &&
 121         A:commit-6-8
 122         X:commit-6-9
 123         X:commit-5-7
 124         EOF
 125         echo "in_merge_bases_many(A,X):1" >expect &&
 126         test_all_modes in_merge_bases_many
 127 '
 128
 129 test_expect_success 'in_merge_bases_many:miss' '
 130         cat >input <<-\EOF &&
 131         A:commit-6-8
 132         X:commit-7-7
 133         X:commit-8-6
 134         EOF
 135         echo "in_merge_bases_many(A,X):0" >expect &&
 136         test_all_modes in_merge_bases_many
 137 '
 138
 139 test_expect_success 'in_merge_bases_many:miss-heuristic' '
 140         cat >input <<-\EOF &&
 141         A:commit-6-8
 142         X:commit-7-5
 143         X:commit-6-6
 144         EOF
 145         echo "in_merge_bases_many(A,X):0" >expect &&
 146         test_all_modes in_merge_bases_many
 147 '
 148
 149 test_expect_success 'is_descendant_of:hit' '
 150         cat >input <<-\EOF &&
 151         A:commit-5-7
 152         X:commit-4-8
 153         X:commit-6-6
 154         X:commit-1-1
 155         EOF
 156         echo "is_descendant_of(A,X):1" >expect &&
 157         test_all_modes is_descendant_of
 158 '
 159
 160 test_expect_success 'is_descendant_of:miss' '
 161         cat >input <<-\EOF &&
 162         A:commit-6-8
 163         X:commit-5-9
 164         X:commit-4-10
 165         X:commit-7-6
 166         EOF
 167         echo "is_descendant_of(A,X):0" >expect &&
 168         test_all_modes is_descendant_of
 169 '
 170
 171 test_expect_success 'get_merge_bases_many' '
 172         cat >input <<-\EOF &&
 173         A:commit-5-7
 174         X:commit-4-8
 175         X:commit-6-6
 176         X:commit-8-3
 177         EOF
 178         {
 179                 echo "get_merge_bases_many(A,X):" &&
 180                 git rev-parse commit-5-6 \
 181                               commit-4-7 | sort
 182         } >expect &&
 183         test_all_modes get_merge_bases_many
 184 '
 185
 186 test_expect_success 'reduce_heads' '
 187         cat >input <<-\EOF &&
 188         X:commit-1-10
 189         X:commit-2-8
 190         X:commit-3-6
 191         X:commit-4-4
 192         X:commit-1-7
 193         X:commit-2-5
 194         X:commit-3-3
 195         X:commit-5-1
 196         EOF
 197         {
 198                 echo "reduce_heads(X):" &&
 199                 git rev-parse commit-5-1 \
 200                               commit-4-4 \
 201                               commit-3-6 \
 202                               commit-2-8 \
 203                               commit-1-10 | sort
 204         } >expect &&
 205         test_all_modes reduce_heads
 206 '
 207
 208 test_expect_success 'can_all_from_reach:hit' '
 209         cat >input <<-\EOF &&
 210         X:commit-2-10
 211         X:commit-3-9
 212         X:commit-4-8
 213         X:commit-5-7
 214         X:commit-6-6
 215         X:commit-7-5
 216         X:commit-8-4
 217         X:commit-9-3
 218         Y:commit-1-9
 219         Y:commit-2-8
 220         Y:commit-3-7
 221         Y:commit-4-6
 222         Y:commit-5-5
 223         Y:commit-6-4
 224         Y:commit-7-3
 225         Y:commit-8-1
 226         EOF
 227         echo "can_all_from_reach(X,Y):1" >expect &&
 228         test_all_modes can_all_from_reach
 229 '
 230
 231 test_expect_success 'can_all_from_reach:miss' '
 232         cat >input <<-\EOF &&
 233         X:commit-2-10
 234         X:commit-3-9
 235         X:commit-4-8
 236         X:commit-5-7
 237         X:commit-6-6
 238         X:commit-7-5
 239         X:commit-8-4
 240         X:commit-9-3
 241         Y:commit-1-9
 242         Y:commit-2-8
 243         Y:commit-3-7
 244         Y:commit-4-6
 245         Y:commit-5-5
 246         Y:commit-6-4
 247         Y:commit-8-5
 248         EOF
 249         echo "can_all_from_reach(X,Y):0" >expect &&
 250         test_all_modes can_all_from_reach
 251 '
 252
 253 test_expect_success 'can_all_from_reach_with_flag: tags case' '
 254         cat >input <<-\EOF &&
 255         X:tag-2-10
 256         X:tag-3-9
 257         X:tag-4-8
 258         X:commit-5-7
 259         X:commit-6-6
 260         X:commit-7-5
 261         X:commit-8-4
 262         X:commit-9-3
 263         Y:tag-1-9
 264         Y:tag-2-8
 265         Y:tag-3-7
 266         Y:commit-4-6
 267         Y:commit-5-5
 268         Y:commit-6-4
 269         Y:commit-7-3
 270         Y:commit-8-1
 271         EOF
 272         echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
 273         test_all_modes can_all_from_reach_with_flag
 274 '
 275
 276 test_expect_success 'commit_contains:hit' '
 277         cat >input <<-\EOF &&
 278         A:commit-7-7
 279         X:commit-2-10
 280         X:commit-3-9
 281         X:commit-4-8
 282         X:commit-5-7
 283         X:commit-6-6
 284         X:commit-7-5
 285         X:commit-8-4
 286         X:commit-9-3
 287         EOF
 288         echo "commit_contains(_,A,X,_):1" >expect &&
 289         test_all_modes commit_contains &&
 290         test_all_modes commit_contains --tag
 291 '
 292
 293 test_expect_success 'commit_contains:miss' '
 294         cat >input <<-\EOF &&
 295         A:commit-6-5
 296         X:commit-2-10
 297         X:commit-3-9
 298         X:commit-4-8
 299         X:commit-5-7
 300         X:commit-6-6
 301         X:commit-7-5
 302         X:commit-8-4
 303         X:commit-9-3
 304         EOF
 305         echo "commit_contains(_,A,X,_):0" >expect &&
 306         test_all_modes commit_contains &&
 307         test_all_modes commit_contains --tag
 308 '
 309
 310 test_expect_success 'rev-list: basic topo-order' '
 311         git rev-parse \
 312                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
 313                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
 314                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
 315                 commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
 316                 commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
 317                 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
 318         >expect &&
 319         run_all_modes git rev-list --topo-order commit-6-6
 320 '
 321
 322 test_expect_success 'rev-list: first-parent 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 commit-3-1 commit-2-1 commit-1-1 \
 330         >expect &&
 331         run_all_modes git rev-list --first-parent --topo-order commit-6-6
 332 '
 333
 334 test_expect_success 'rev-list: range topo-order' '
 335         git rev-parse \
 336                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
 337                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
 338                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
 339                 commit-6-3 commit-5-3 commit-4-3 \
 340                 commit-6-2 commit-5-2 commit-4-2 \
 341                 commit-6-1 commit-5-1 commit-4-1 \
 342         >expect &&
 343         run_all_modes git rev-list --topo-order commit-3-3..commit-6-6
 344 '
 345
 346 test_expect_success 'rev-list: range topo-order' '
 347         git rev-parse \
 348                 commit-6-6 commit-5-6 commit-4-6 \
 349                 commit-6-5 commit-5-5 commit-4-5 \
 350                 commit-6-4 commit-5-4 commit-4-4 \
 351                 commit-6-3 commit-5-3 commit-4-3 \
 352                 commit-6-2 commit-5-2 commit-4-2 \
 353                 commit-6-1 commit-5-1 commit-4-1 \
 354         >expect &&
 355         run_all_modes git rev-list --topo-order commit-3-8..commit-6-6
 356 '
 357
 358 test_expect_success 'rev-list: first-parent range topo-order' '
 359         git rev-parse \
 360                 commit-6-6 \
 361                 commit-6-5 \
 362                 commit-6-4 \
 363                 commit-6-3 \
 364                 commit-6-2 \
 365                 commit-6-1 commit-5-1 commit-4-1 \
 366         >expect &&
 367         run_all_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
 368 '
 369
 370 test_expect_success 'rev-list: ancestry-path topo-order' '
 371         git rev-parse \
 372                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
 373                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
 374                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
 375                 commit-6-3 commit-5-3 commit-4-3 \
 376         >expect &&
 377         run_all_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
 378 '
 379
 380 test_expect_success 'rev-list: symmetric difference topo-order' '
 381         git rev-parse \
 382                 commit-6-6 commit-5-6 commit-4-6 \
 383                 commit-6-5 commit-5-5 commit-4-5 \
 384                 commit-6-4 commit-5-4 commit-4-4 \
 385                 commit-6-3 commit-5-3 commit-4-3 \
 386                 commit-6-2 commit-5-2 commit-4-2 \
 387                 commit-6-1 commit-5-1 commit-4-1 \
 388                 commit-3-8 commit-2-8 commit-1-8 \
 389                 commit-3-7 commit-2-7 commit-1-7 \
 390         >expect &&
 391         run_all_modes git rev-list --topo-order commit-3-8...commit-6-6
 392 '
 393
 394 test_expect_success 'get_reachable_subset:all' '
 395         cat >input <<-\EOF &&
 396         X:commit-9-1
 397         X:commit-8-3
 398         X:commit-7-5
 399         X:commit-6-6
 400         X:commit-1-7
 401         Y:commit-3-3
 402         Y:commit-1-7
 403         Y:commit-5-6
 404         EOF
 405         (
 406                 echo "get_reachable_subset(X,Y)" &&
 407                 git rev-parse commit-3-3 \
 408                               commit-1-7 \
 409                               commit-5-6 | sort
 410         ) >expect &&
 411         test_all_modes get_reachable_subset
 412 '
 413
 414 test_expect_success 'get_reachable_subset:some' '
 415         cat >input <<-\EOF &&
 416         X:commit-9-1
 417         X:commit-8-3
 418         X:commit-7-5
 419         X:commit-1-7
 420         Y:commit-3-3
 421         Y:commit-1-7
 422         Y:commit-5-6
 423         EOF
 424         (
 425                 echo "get_reachable_subset(X,Y)" &&
 426                 git rev-parse commit-3-3 \
 427                               commit-1-7 | sort
 428         ) >expect &&
 429         test_all_modes get_reachable_subset
 430 '
 431
 432 test_expect_success 'get_reachable_subset:none' '
 433         cat >input <<-\EOF &&
 434         X:commit-9-1
 435         X:commit-8-3
 436         X:commit-7-5
 437         X:commit-1-7
 438         Y:commit-9-3
 439         Y:commit-7-6
 440         Y:commit-2-8
 441         EOF
 442         echo "get_reachable_subset(X,Y)" >expect &&
 443         test_all_modes get_reachable_subset
 444 '
 445
 446 test_expect_success 'for-each-ref ahead-behind:linear' '
 447         cat >input <<-\EOF &&
 448         refs/heads/commit-1-1
 449         refs/heads/commit-1-3
 450         refs/heads/commit-1-5
 451         refs/heads/commit-1-8
 452         EOF
 453         cat >expect <<-\EOF &&
 454         refs/heads/commit-1-1 0 8
 455         refs/heads/commit-1-3 0 6
 456         refs/heads/commit-1-5 0 4
 457         refs/heads/commit-1-8 0 1
 458         EOF
 459         run_all_modes git for-each-ref \
 460                 --format="%(refname) %(ahead-behind:commit-1-9)" --stdin
 461 '
 462
 463 test_expect_success 'for-each-ref ahead-behind:all' '
 464         cat >input <<-\EOF &&
 465         refs/heads/commit-1-1
 466         refs/heads/commit-2-4
 467         refs/heads/commit-4-2
 468         refs/heads/commit-4-4
 469         EOF
 470         cat >expect <<-\EOF &&
 471         refs/heads/commit-1-1 0 24
 472         refs/heads/commit-2-4 0 17
 473         refs/heads/commit-4-2 0 17
 474         refs/heads/commit-4-4 0 9
 475         EOF
 476         run_all_modes git for-each-ref \
 477                 --format="%(refname) %(ahead-behind:commit-5-5)" --stdin
 478 '
 479
 480 test_expect_success 'for-each-ref ahead-behind:some' '
 481         cat >input <<-\EOF &&
 482         refs/heads/commit-1-1
 483         refs/heads/commit-5-3
 484         refs/heads/commit-4-8
 485         refs/heads/commit-9-9
 486         EOF
 487         cat >expect <<-\EOF &&
 488         refs/heads/commit-1-1 0 53
 489         refs/heads/commit-4-8 8 30
 490         refs/heads/commit-5-3 0 39
 491         refs/heads/commit-9-9 27 0
 492         EOF
 493         run_all_modes git for-each-ref \
 494                 --format="%(refname) %(ahead-behind:commit-9-6)" --stdin
 495 '
 496
 497 test_expect_success 'for-each-ref ahead-behind:some, multibase' '
 498         cat >input <<-\EOF &&
 499         refs/heads/commit-1-1
 500         refs/heads/commit-5-3
 501         refs/heads/commit-7-8
 502         refs/heads/commit-4-8
 503         refs/heads/commit-9-9
 504         EOF
 505         cat >expect <<-\EOF &&
 506         refs/heads/commit-1-1 0 53 0 53
 507         refs/heads/commit-4-8 8 30 0 22
 508         refs/heads/commit-5-3 0 39 0 39
 509         refs/heads/commit-7-8 14 12 8 6
 510         refs/heads/commit-9-9 27 0 27 0
 511         EOF
 512         run_all_modes git for-each-ref \
 513                 --format="%(refname) %(ahead-behind:commit-9-6) %(ahead-behind:commit-6-9)" \
 514                 --stdin
 515 '
 516
 517 test_expect_success 'for-each-ref ahead-behind:none' '
 518         cat >input <<-\EOF &&
 519         refs/heads/commit-7-5
 520         refs/heads/commit-4-8
 521         refs/heads/commit-9-9
 522         EOF
 523         cat >expect <<-\EOF &&
 524         refs/heads/commit-4-8 16 16
 525         refs/heads/commit-7-5 7 4
 526         refs/heads/commit-9-9 49 0
 527         EOF
 528         run_all_modes git for-each-ref \
 529                 --format="%(refname) %(ahead-behind:commit-8-4)" --stdin
 530 '
 531
 532 test_expect_success 'for-each-ref merged:linear' '
 533         cat >input <<-\EOF &&
 534         refs/heads/commit-1-1
 535         refs/heads/commit-1-3
 536         refs/heads/commit-1-5
 537         refs/heads/commit-1-8
 538         refs/heads/commit-2-1
 539         refs/heads/commit-5-1
 540         refs/heads/commit-9-1
 541         EOF
 542         cat >expect <<-\EOF &&
 543         refs/heads/commit-1-1
 544         refs/heads/commit-1-3
 545         refs/heads/commit-1-5
 546         refs/heads/commit-1-8
 547         EOF
 548         run_all_modes git for-each-ref --merged=commit-1-9 \
 549                 --format="%(refname)" --stdin
 550 '
 551
 552 test_expect_success 'for-each-ref merged:all' '
 553         cat >input <<-\EOF &&
 554         refs/heads/commit-1-1
 555         refs/heads/commit-2-4
 556         refs/heads/commit-4-2
 557         refs/heads/commit-4-4
 558         EOF
 559         cat >expect <<-\EOF &&
 560         refs/heads/commit-1-1
 561         refs/heads/commit-2-4
 562         refs/heads/commit-4-2
 563         refs/heads/commit-4-4
 564         EOF
 565         run_all_modes git for-each-ref --merged=commit-5-5 \
 566                 --format="%(refname)" --stdin
 567 '
 568
 569 test_expect_success 'for-each-ref ahead-behind:some' '
 570         cat >input <<-\EOF &&
 571         refs/heads/commit-1-1
 572         refs/heads/commit-5-3
 573         refs/heads/commit-4-8
 574         refs/heads/commit-9-9
 575         EOF
 576         cat >expect <<-\EOF &&
 577         refs/heads/commit-1-1
 578         refs/heads/commit-5-3
 579         EOF
 580         run_all_modes git for-each-ref --merged=commit-9-6 \
 581                 --format="%(refname)" --stdin
 582 '
 583
 584 test_expect_success 'for-each-ref merged:some, multibase' '
 585         cat >input <<-\EOF &&
 586         refs/heads/commit-1-1
 587         refs/heads/commit-5-3
 588         refs/heads/commit-7-8
 589         refs/heads/commit-4-8
 590         refs/heads/commit-9-9
 591         EOF
 592         cat >expect <<-\EOF &&
 593         refs/heads/commit-1-1
 594         refs/heads/commit-4-8
 595         refs/heads/commit-5-3
 596         EOF
 597         run_all_modes git for-each-ref \
 598                 --merged=commit-5-8 \
 599                 --merged=commit-8-5 \
 600                 --format="%(refname)" \
 601                 --stdin
 602 '
 603
 604 test_expect_success 'for-each-ref merged:none' '
 605         cat >input <<-\EOF &&
 606         refs/heads/commit-7-5
 607         refs/heads/commit-4-8
 608         refs/heads/commit-9-9
 609         EOF
 610         >expect &&
 611         run_all_modes git for-each-ref --merged=commit-8-4 \
 612                 --format="%(refname)" --stdin
 613 '
 614
 615 test_done