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