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 -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_done