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