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         git show-ref -s commit-5-5 | git commit-graph write --stdin-commits &&
  55         mv .git/objects/info/commit-graph commit-graph-half &&
  56         git config core.commitGraph true
  57 '
  58
  59 run_three_modes () {
  60         test_when_finished rm -rf .git/objects/info/commit-graph &&
  61         "$@" <input >actual &&
  62         test_cmp expect actual &&
  63         cp commit-graph-full .git/objects/info/commit-graph &&
  64         "$@" <input >actual &&
  65         test_cmp expect actual &&
  66         cp commit-graph-half .git/objects/info/commit-graph &&
  67         "$@" <input >actual &&
  68         test_cmp expect actual
  69 }
  70
  71 test_three_modes () {
  72         run_three_modes test-tool reach "$@"
  73 }
  74
  75 test_expect_success 'ref_newer:miss' '
  76         cat >input <<-\EOF &&
  77         A:commit-5-7
  78         B:commit-4-9
  79         EOF
  80         echo "ref_newer(A,B):0" >expect &&
  81         test_three_modes ref_newer
  82 '
  83
  84 test_expect_success 'ref_newer:hit' '
  85         cat >input <<-\EOF &&
  86         A:commit-5-7
  87         B:commit-2-3
  88         EOF
  89         echo "ref_newer(A,B):1" >expect &&
  90         test_three_modes ref_newer
  91 '
  92
  93 test_expect_success 'in_merge_bases:hit' '
  94         cat >input <<-\EOF &&
  95         A:commit-5-7
  96         B:commit-8-8
  97         EOF
  98         echo "in_merge_bases(A,B):1" >expect &&
  99         test_three_modes in_merge_bases
 100 '
 101
 102 test_expect_success 'in_merge_bases:miss' '
 103         cat >input <<-\EOF &&
 104         A:commit-6-8
 105         B:commit-5-9
 106         EOF
 107         echo "in_merge_bases(A,B):0" >expect &&
 108         test_three_modes in_merge_bases
 109 '
 110
 111 test_expect_success 'is_descendant_of:hit' '
 112         cat >input <<-\EOF &&
 113         A:commit-5-7
 114         X:commit-4-8
 115         X:commit-6-6
 116         X:commit-1-1
 117         EOF
 118         echo "is_descendant_of(A,X):1" >expect &&
 119         test_three_modes is_descendant_of
 120 '
 121
 122 test_expect_success 'is_descendant_of:miss' '
 123         cat >input <<-\EOF &&
 124         A:commit-6-8
 125         X:commit-5-9
 126         X:commit-4-10
 127         X:commit-7-6
 128         EOF
 129         echo "is_descendant_of(A,X):0" >expect &&
 130         test_three_modes is_descendant_of
 131 '
 132
 133 test_expect_success 'get_merge_bases_many' '
 134         cat >input <<-\EOF &&
 135         A:commit-5-7
 136         X:commit-4-8
 137         X:commit-6-6
 138         X:commit-8-3
 139         EOF
 140         {
 141                 echo "get_merge_bases_many(A,X):" &&
 142                 git rev-parse commit-5-6 \
 143                               commit-4-7 | sort
 144         } >expect &&
 145         test_three_modes get_merge_bases_many
 146 '
 147
 148 test_expect_success 'reduce_heads' '
 149         cat >input <<-\EOF &&
 150         X:commit-1-10
 151         X:commit-2-8
 152         X:commit-3-6
 153         X:commit-4-4
 154         X:commit-1-7
 155         X:commit-2-5
 156         X:commit-3-3
 157         X:commit-5-1
 158         EOF
 159         {
 160                 echo "reduce_heads(X):" &&
 161                 git rev-parse commit-5-1 \
 162                               commit-4-4 \
 163                               commit-3-6 \
 164                               commit-2-8 \
 165                               commit-1-10 | sort
 166         } >expect &&
 167         test_three_modes reduce_heads
 168 '
 169
 170 test_expect_success 'can_all_from_reach:hit' '
 171         cat >input <<-\EOF &&
 172         X:commit-2-10
 173         X:commit-3-9
 174         X:commit-4-8
 175         X:commit-5-7
 176         X:commit-6-6
 177         X:commit-7-5
 178         X:commit-8-4
 179         X:commit-9-3
 180         Y:commit-1-9
 181         Y:commit-2-8
 182         Y:commit-3-7
 183         Y:commit-4-6
 184         Y:commit-5-5
 185         Y:commit-6-4
 186         Y:commit-7-3
 187         Y:commit-8-1
 188         EOF
 189         echo "can_all_from_reach(X,Y):1" >expect &&
 190         test_three_modes can_all_from_reach
 191 '
 192
 193 test_expect_success 'can_all_from_reach:miss' '
 194         cat >input <<-\EOF &&
 195         X:commit-2-10
 196         X:commit-3-9
 197         X:commit-4-8
 198         X:commit-5-7
 199         X:commit-6-6
 200         X:commit-7-5
 201         X:commit-8-4
 202         X:commit-9-3
 203         Y:commit-1-9
 204         Y:commit-2-8
 205         Y:commit-3-7
 206         Y:commit-4-6
 207         Y:commit-5-5
 208         Y:commit-6-4
 209         Y:commit-8-5
 210         EOF
 211         echo "can_all_from_reach(X,Y):0" >expect &&
 212         test_three_modes can_all_from_reach
 213 '
 214
 215 test_expect_success 'can_all_from_reach_with_flag: tags case' '
 216         cat >input <<-\EOF &&
 217         X:tag-2-10
 218         X:tag-3-9
 219         X:tag-4-8
 220         X:commit-5-7
 221         X:commit-6-6
 222         X:commit-7-5
 223         X:commit-8-4
 224         X:commit-9-3
 225         Y:tag-1-9
 226         Y:tag-2-8
 227         Y:tag-3-7
 228         Y:commit-4-6
 229         Y:commit-5-5
 230         Y:commit-6-4
 231         Y:commit-7-3
 232         Y:commit-8-1
 233         EOF
 234         echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
 235         test_three_modes can_all_from_reach_with_flag
 236 '
 237
 238 test_expect_success 'commit_contains:hit' '
 239         cat >input <<-\EOF &&
 240         A:commit-7-7
 241         X:commit-2-10
 242         X:commit-3-9
 243         X:commit-4-8
 244         X:commit-5-7
 245         X:commit-6-6
 246         X:commit-7-5
 247         X:commit-8-4
 248         X:commit-9-3
 249         EOF
 250         echo "commit_contains(_,A,X,_):1" >expect &&
 251         test_three_modes commit_contains &&
 252         test_three_modes commit_contains --tag
 253 '
 254
 255 test_expect_success 'commit_contains:miss' '
 256         cat >input <<-\EOF &&
 257         A:commit-6-5
 258         X:commit-2-10
 259         X:commit-3-9
 260         X:commit-4-8
 261         X:commit-5-7
 262         X:commit-6-6
 263         X:commit-7-5
 264         X:commit-8-4
 265         X:commit-9-3
 266         EOF
 267         echo "commit_contains(_,A,X,_):0" >expect &&
 268         test_three_modes commit_contains &&
 269         test_three_modes commit_contains --tag
 270 '
 271
 272 test_expect_success 'rev-list: basic topo-order' '
 273         git rev-parse \
 274                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
 275                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
 276                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
 277                 commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
 278                 commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
 279                 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
 280         >expect &&
 281         run_three_modes git rev-list --topo-order commit-6-6
 282 '
 283
 284 test_expect_success 'rev-list: first-parent topo-order' '
 285         git rev-parse \
 286                 commit-6-6 \
 287                 commit-6-5 \
 288                 commit-6-4 \
 289                 commit-6-3 \
 290                 commit-6-2 \
 291                 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
 292         >expect &&
 293         run_three_modes git rev-list --first-parent --topo-order commit-6-6
 294 '
 295
 296 test_expect_success 'rev-list: range topo-order' '
 297         git rev-parse \
 298                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
 299                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
 300                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
 301                 commit-6-3 commit-5-3 commit-4-3 \
 302                 commit-6-2 commit-5-2 commit-4-2 \
 303                 commit-6-1 commit-5-1 commit-4-1 \
 304         >expect &&
 305         run_three_modes git rev-list --topo-order commit-3-3..commit-6-6
 306 '
 307
 308 test_expect_success 'rev-list: range topo-order' '
 309         git rev-parse \
 310                 commit-6-6 commit-5-6 commit-4-6 \
 311                 commit-6-5 commit-5-5 commit-4-5 \
 312                 commit-6-4 commit-5-4 commit-4-4 \
 313                 commit-6-3 commit-5-3 commit-4-3 \
 314                 commit-6-2 commit-5-2 commit-4-2 \
 315                 commit-6-1 commit-5-1 commit-4-1 \
 316         >expect &&
 317         run_three_modes git rev-list --topo-order commit-3-8..commit-6-6
 318 '
 319
 320 test_expect_success 'rev-list: first-parent range topo-order' '
 321         git rev-parse \
 322                 commit-6-6 \
 323                 commit-6-5 \
 324                 commit-6-4 \
 325                 commit-6-3 \
 326                 commit-6-2 \
 327                 commit-6-1 commit-5-1 commit-4-1 \
 328         >expect &&
 329         run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
 330 '
 331
 332 test_expect_success 'rev-list: ancestry-path topo-order' '
 333         git rev-parse \
 334                 commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
 335                 commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
 336                 commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
 337                 commit-6-3 commit-5-3 commit-4-3 \
 338         >expect &&
 339         run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
 340 '
 341
 342 test_expect_success 'rev-list: symmetric difference topo-order' '
 343         git rev-parse \
 344                 commit-6-6 commit-5-6 commit-4-6 \
 345                 commit-6-5 commit-5-5 commit-4-5 \
 346                 commit-6-4 commit-5-4 commit-4-4 \
 347                 commit-6-3 commit-5-3 commit-4-3 \
 348                 commit-6-2 commit-5-2 commit-4-2 \
 349                 commit-6-1 commit-5-1 commit-4-1 \
 350                 commit-3-8 commit-2-8 commit-1-8 \
 351                 commit-3-7 commit-2-7 commit-1-7 \
 352         >expect &&
 353         run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
 354 '
 355
 356 test_expect_success 'get_reachable_subset:all' '
 357         cat >input <<-\EOF &&
 358         X:commit-9-1
 359         X:commit-8-3
 360         X:commit-7-5
 361         X:commit-6-6
 362         X:commit-1-7
 363         Y:commit-3-3
 364         Y:commit-1-7
 365         Y:commit-5-6
 366         EOF
 367         (
 368                 echo "get_reachable_subset(X,Y)" &&
 369                 git rev-parse commit-3-3 \
 370                               commit-1-7 \
 371                               commit-5-6 | sort
 372         ) >expect &&
 373         test_three_modes get_reachable_subset
 374 '
 375
 376 test_expect_success 'get_reachable_subset:some' '
 377         cat >input <<-\EOF &&
 378         X:commit-9-1
 379         X:commit-8-3
 380         X:commit-7-5
 381         X:commit-1-7
 382         Y:commit-3-3
 383         Y:commit-1-7
 384         Y:commit-5-6
 385         EOF
 386         (
 387                 echo "get_reachable_subset(X,Y)" &&
 388                 git rev-parse commit-3-3 \
 389                               commit-1-7 | sort
 390         ) >expect &&
 391         test_three_modes get_reachable_subset
 392 '
 393
 394 test_expect_success 'get_reachable_subset:none' '
 395         cat >input <<-\EOF &&
 396         X:commit-9-1
 397         X:commit-8-3
 398         X:commit-7-5
 399         X:commit-1-7
 400         Y:commit-9-3
 401         Y:commit-7-6
 402         Y:commit-2-8
 403         EOF
 404         echo "get_reachable_subset(X,Y)" >expect &&
 405         test_three_modes get_reachable_subset
 406 '
 407
 408 test_done