t/lib-bitmap.sh

   1 # Helpers for scripts testing bitmap functionality; see t5310 for
   2 # example usage.
   3
   4 objdir=.git/objects
   5 midx=$objdir/pack/multi-pack-index
   6
   7 # Compare a file containing rev-list bitmap traversal output to its non-bitmap
   8 # counterpart. You can't just use test_cmp for this, because the two produce
   9 # subtly different output:
  10 #
  11 #   - regular output is in traversal order, whereas bitmap is split by type,
  12 #     with non-packed objects at the end
  13 #
  14 #   - regular output has a space and the pathname appended to non-commit
  15 #     objects; bitmap output omits this
  16 #
  17 # This function normalizes and compares the two. The second file should
  18 # always be the bitmap output.
  19 test_bitmap_traversal () {
  20         if test "$1" = "--no-confirm-bitmaps"
  21         then
  22                 shift
  23         elif cmp "$1" "$2"
  24         then
  25                 echo >&2 "identical raw outputs; are you sure bitmaps were used?"
  26                 return 1
  27         fi &&
  28         cut -d' ' -f1 "$1" | sort >"$1.normalized" &&
  29         sort "$2" >"$2.normalized" &&
  30         test_cmp "$1.normalized" "$2.normalized" &&
  31         rm -f "$1.normalized" "$2.normalized"
  32 }
  33
  34 # To ensure the logic for "maximal commits" is exercised, make
  35 # the repository a bit more complicated.
  36 #
  37 #    other                         second
  38 #      *                             *
  39 # (99 commits)                  (99 commits)
  40 #      *                             *
  41 #      |\                           /|
  42 #      | * octo-other  octo-second * |
  43 #      |/|\_________  ____________/|\|
  44 #      | \          \/  __________/  |
  45 #      |  | ________/\ /             |
  46 #      *  |/          * merge-right  *
  47 #      | _|__________/ \____________ |
  48 #      |/ |                         \|
  49 # (l1) *  * merge-left               * (r1)
  50 #      | / \________________________ |
  51 #      |/                           \|
  52 # (l2) *                             * (r2)
  53 #       \___________________________ |
  54 #                                   \|
  55 #                                    * (base)
  56 #
  57 # We only push bits down the first-parent history, which
  58 # makes some of these commits unimportant!
  59 #
  60 # The important part for the maximal commit algorithm is how
  61 # the bitmasks are extended. Assuming starting bit positions
  62 # for second (bit 0) and other (bit 1), the bitmasks at the
  63 # end should be:
  64 #
  65 #      second: 1       (maximal, selected)
  66 #       other: 01      (maximal, selected)
  67 #      (base): 11 (maximal)
  68 #
  69 # This complicated history was important for a previous
  70 # version of the walk that guarantees never walking a
  71 # commit multiple times. That goal might be important
  72 # again, so preserve this complicated case. For now, this
  73 # test will guarantee that the bitmaps are computed
  74 # correctly, even with the repeat calculations.
  75 setup_bitmap_history() {
  76         test_expect_success 'setup repo with moderate-sized history' '
  77                 test_commit_bulk --id=file 10 &&
  78                 git branch -M second &&
  79                 git checkout -b other HEAD~5 &&
  80                 test_commit_bulk --id=side 10 &&
  81
  82                 # add complicated history setup, including merges and
  83                 # ambiguous merge-bases
  84
  85                 git checkout -b merge-left other~2 &&
  86                 git merge second~2 -m "merge-left" &&
  87
  88                 git checkout -b merge-right second~1 &&
  89                 git merge other~1 -m "merge-right" &&
  90
  91                 git checkout -b octo-second second &&
  92                 git merge merge-left merge-right -m "octopus-second" &&
  93
  94                 git checkout -b octo-other other &&
  95                 git merge merge-left merge-right -m "octopus-other" &&
  96
  97                 git checkout other &&
  98                 git merge octo-other -m "pull octopus" &&
  99
 100                 git checkout second &&
 101                 git merge octo-second -m "pull octopus" &&
 102
 103                 # Remove these branches so they are not selected
 104                 # as bitmap tips
 105                 git branch -D merge-left &&
 106                 git branch -D merge-right &&
 107                 git branch -D octo-other &&
 108                 git branch -D octo-second &&
 109
 110                 # add padding to make these merges less interesting
 111                 # and avoid having them selected for bitmaps
 112                 test_commit_bulk --id=file 100 &&
 113                 git checkout other &&
 114                 test_commit_bulk --id=side 100 &&
 115                 git checkout second &&
 116
 117                 bitmaptip=$(git rev-parse second) &&
 118                 blob=$(echo tagged-blob | git hash-object -w --stdin) &&
 119                 git tag tagged-blob $blob
 120         '
 121 }
 122
 123 rev_list_tests_head () {
 124         test_expect_success "counting commits via bitmap ($state, $branch)" '
 125                 git rev-list --count $branch >expect &&
 126                 git rev-list --use-bitmap-index --count $branch >actual &&
 127                 test_cmp expect actual
 128         '
 129
 130         test_expect_success "counting partial commits via bitmap ($state, $branch)" '
 131                 git rev-list --count $branch~5..$branch >expect &&
 132                 git rev-list --use-bitmap-index --count $branch~5..$branch >actual &&
 133                 test_cmp expect actual
 134         '
 135
 136         test_expect_success "counting commits with limit ($state, $branch)" '
 137                 git rev-list --count -n 1 $branch >expect &&
 138                 git rev-list --use-bitmap-index --count -n 1 $branch >actual &&
 139                 test_cmp expect actual
 140         '
 141
 142         test_expect_success "counting non-linear history ($state, $branch)" '
 143                 git rev-list --count other...second >expect &&
 144                 git rev-list --use-bitmap-index --count other...second >actual &&
 145                 test_cmp expect actual
 146         '
 147
 148         test_expect_success "counting commits with limiting ($state, $branch)" '
 149                 git rev-list --count $branch -- 1.t >expect &&
 150                 git rev-list --use-bitmap-index --count $branch -- 1.t >actual &&
 151                 test_cmp expect actual
 152         '
 153
 154         test_expect_success "counting objects via bitmap ($state, $branch)" '
 155                 git rev-list --count --objects $branch >expect &&
 156                 git rev-list --use-bitmap-index --count --objects $branch >actual &&
 157                 test_cmp expect actual
 158         '
 159
 160         test_expect_success "enumerate commits ($state, $branch)" '
 161                 git rev-list --use-bitmap-index $branch >actual &&
 162                 git rev-list $branch >expect &&
 163                 test_bitmap_traversal --no-confirm-bitmaps expect actual
 164         '
 165
 166         test_expect_success "enumerate --objects ($state, $branch)" '
 167                 git rev-list --objects --use-bitmap-index $branch >actual &&
 168                 git rev-list --objects $branch >expect &&
 169                 test_bitmap_traversal expect actual
 170         '
 171
 172         test_expect_success "bitmap --objects handles non-commit objects ($state, $branch)" '
 173                 git rev-list --objects --use-bitmap-index $branch tagged-blob >actual &&
 174                 grep $blob actual
 175         '
 176 }
 177
 178 rev_list_tests () {
 179         state=$1
 180
 181         for branch in "second" "other"
 182         do
 183                 rev_list_tests_head
 184         done
 185 }
 186
 187 basic_bitmap_tests () {
 188         tip="$1"
 189         test_expect_success 'rev-list --test-bitmap verifies bitmaps' "
 190                 git rev-list --test-bitmap "${tip:-HEAD}"
 191         "
 192
 193         rev_list_tests 'full bitmap'
 194
 195         test_expect_success 'clone from bitmapped repository' '
 196                 rm -fr clone.git &&
 197                 git clone --no-local --bare . clone.git &&
 198                 git rev-parse HEAD >expect &&
 199                 git --git-dir=clone.git rev-parse HEAD >actual &&
 200                 test_cmp expect actual
 201         '
 202
 203         test_expect_success 'partial clone from bitmapped repository' '
 204                 test_config uploadpack.allowfilter true &&
 205                 rm -fr partial-clone.git &&
 206                 git clone --no-local --bare --filter=blob:none . partial-clone.git &&
 207                 (
 208                         cd partial-clone.git &&
 209                         pack=$(echo objects/pack/*.pack) &&
 210                         git verify-pack -v "$pack" >have &&
 211                         awk "/blob/ { print \$1 }" <have >blobs &&
 212                         # we expect this single blob because of the direct ref
 213                         git rev-parse refs/tags/tagged-blob >expect &&
 214                         test_cmp expect blobs
 215                 )
 216         '
 217
 218         test_expect_success 'setup further non-bitmapped commits' '
 219                 test_commit_bulk --id=further 10
 220         '
 221
 222         rev_list_tests 'partial bitmap'
 223
 224         test_expect_success 'fetch (partial bitmap)' '
 225                 git --git-dir=clone.git fetch origin second:second &&
 226                 git rev-parse HEAD >expect &&
 227                 git --git-dir=clone.git rev-parse HEAD >actual &&
 228                 test_cmp expect actual
 229         '
 230
 231         test_expect_success 'enumerating progress counts pack-reused objects' '
 232                 count=$(git rev-list --objects --all --count) &&
 233                 git repack -adb &&
 234
 235                 # check first with only reused objects; confirm that our
 236                 # progress showed the right number, and also that we did
 237                 # pack-reuse as expected.  Check only the final "done"
 238                 # line of the meter (there may be an arbitrary number of
 239                 # intermediate lines ending with CR).
 240                 GIT_PROGRESS_DELAY=0 \
 241                         git pack-objects --all --stdout --progress \
 242                         </dev/null >/dev/null 2>stderr &&
 243                 grep "Enumerating objects: $count, done" stderr &&
 244                 grep "pack-reused $count" stderr &&
 245
 246                 # now the same but with one non-reused object
 247                 git commit --allow-empty -m "an extra commit object" &&
 248                 GIT_PROGRESS_DELAY=0 \
 249                         git pack-objects --all --stdout --progress \
 250                         </dev/null >/dev/null 2>stderr &&
 251                 grep "Enumerating objects: $((count+1)), done" stderr &&
 252                 grep "pack-reused $count" stderr
 253         '
 254 }
 255
 256 # have_delta <obj> <expected_base>
 257 #
 258 # Note that because this relies on cat-file, it might find _any_ copy of an
 259 # object in the repository. The caller is responsible for making sure
 260 # there's only one (e.g., via "repack -ad", or having just fetched a copy).
 261 have_delta () {
 262         echo $2 >expect &&
 263         echo $1 | git cat-file --batch-check="%(deltabase)" >actual &&
 264         test_cmp expect actual
 265 }
 266
 267 midx_checksum () {
 268         test-tool read-midx --checksum "$1"
 269 }
 270
 271 # midx_pack_source <obj>
 272 midx_pack_source () {
 273         test-tool read-midx --show-objects .git/objects | grep "^$1 " | cut -f2
 274 }
 275
 276 test_rev_exists () {
 277         commit="$1"
 278         kind="$2"
 279
 280         test_expect_success "reverse index exists ($kind)" '
 281                 GIT_TRACE2_EVENT=$(pwd)/event.trace \
 282                         git rev-list --test-bitmap "$commit" &&
 283
 284                 if test "rev" = "$kind"
 285                 then
 286                         test_path_is_file $midx-$(midx_checksum $objdir).rev
 287                 fi &&
 288                 grep "\"category\":\"load_midx_revindex\",\"key\":\"source\",\"value\":\"$kind\"" event.trace
 289         '
 290 }
 291
 292 midx_bitmap_core () {
 293         rev_kind="${1:-midx}"
 294
 295         setup_bitmap_history
 296
 297         test_expect_success 'create single-pack midx with bitmaps' '
 298                 git repack -ad &&
 299                 git multi-pack-index write --bitmap &&
 300                 test_path_is_file $midx &&
 301                 test_path_is_file $midx-$(midx_checksum $objdir).bitmap
 302         '
 303
 304         test_rev_exists HEAD "$rev_kind"
 305
 306         basic_bitmap_tests
 307
 308         test_expect_success 'create new additional packs' '
 309                 for i in $(test_seq 1 16)
 310                 do
 311                         test_commit "$i" &&
 312                         git repack -d || return 1
 313                 done &&
 314
 315                 git checkout -b other2 HEAD~8 &&
 316                 for i in $(test_seq 1 8)
 317                 do
 318                         test_commit "side-$i" &&
 319                         git repack -d || return 1
 320                 done &&
 321                 git checkout second
 322         '
 323
 324         test_expect_success 'create multi-pack midx with bitmaps' '
 325                 git multi-pack-index write --bitmap &&
 326
 327                 ls $objdir/pack/pack-*.pack >packs &&
 328                 test_line_count = 25 packs &&
 329
 330                 test_path_is_file $midx &&
 331                 test_path_is_file $midx-$(midx_checksum $objdir).bitmap
 332         '
 333
 334         test_rev_exists HEAD "$rev_kind"
 335
 336         basic_bitmap_tests
 337
 338         test_expect_success '--no-bitmap is respected when bitmaps exist' '
 339                 git multi-pack-index write --bitmap &&
 340
 341                 test_commit respect--no-bitmap &&
 342                 git repack -d &&
 343
 344                 test_path_is_file $midx &&
 345                 test_path_is_file $midx-$(midx_checksum $objdir).bitmap &&
 346
 347                 git multi-pack-index write --no-bitmap &&
 348
 349                 test_path_is_file $midx &&
 350                 test_path_is_missing $midx-$(midx_checksum $objdir).bitmap &&
 351                 test_path_is_missing $midx-$(midx_checksum $objdir).rev
 352         '
 353
 354         test_expect_success 'setup midx with base from later pack' '
 355                 # Write a and b so that "a" is a delta on top of base "b", since Git
 356                 # prefers to delete contents out of a base rather than add to a shorter
 357                 # object.
 358                 test_seq 1 128 >a &&
 359                 test_seq 1 130 >b &&
 360
 361                 git add a b &&
 362                 git commit -m "initial commit" &&
 363
 364                 a=$(git rev-parse HEAD:a) &&
 365                 b=$(git rev-parse HEAD:b) &&
 366
 367                 # In the first pack, "a" is stored as a delta to "b".
 368                 p1=$(git pack-objects .git/objects/pack/pack <<-EOF
 369                 $a
 370                 $b
 371                 EOF
 372                 ) &&
 373
 374                 # In the second pack, "a" is missing, and "b" is not a delta nor base to
 375                 # any other object.
 376                 p2=$(git pack-objects .git/objects/pack/pack <<-EOF
 377                 $b
 378                 $(git rev-parse HEAD)
 379                 $(git rev-parse HEAD^{tree})
 380                 EOF
 381                 ) &&
 382
 383                 git prune-packed &&
 384                 # Use the second pack as the preferred source, so that "b" occurs
 385                 # earlier in the MIDX object order, rendering "a" unusable for pack
 386                 # reuse.
 387                 git multi-pack-index write --bitmap --preferred-pack=pack-$p2.idx &&
 388
 389                 have_delta $a $b &&
 390                 test $(midx_pack_source $a) != $(midx_pack_source $b)
 391         '
 392
 393         rev_list_tests 'full bitmap with backwards delta'
 394
 395         test_expect_success 'clone with bitmaps enabled' '
 396                 git clone --no-local --bare . clone-reverse-delta.git &&
 397                 test_when_finished "rm -fr clone-reverse-delta.git" &&
 398
 399                 git rev-parse HEAD >expect &&
 400                 git --git-dir=clone-reverse-delta.git rev-parse HEAD >actual &&
 401                 test_cmp expect actual
 402         '
 403
 404         test_expect_success 'changing the preferred pack does not corrupt bitmaps' '
 405                 rm -fr repo &&
 406                 git init repo &&
 407                 test_when_finished "rm -fr repo" &&
 408                 (
 409                         cd repo &&
 410
 411                         test_commit A &&
 412                         test_commit B &&
 413
 414                         git rev-list --objects --no-object-names HEAD^ >A.objects &&
 415                         git rev-list --objects --no-object-names HEAD^.. >B.objects &&
 416
 417                         A=$(git pack-objects $objdir/pack/pack <A.objects) &&
 418                         B=$(git pack-objects $objdir/pack/pack <B.objects) &&
 419
 420                         cat >indexes <<-EOF &&
 421                         pack-$A.idx
 422                         pack-$B.idx
 423                         EOF
 424
 425                         git multi-pack-index write --bitmap --stdin-packs \
 426                                 --preferred-pack=pack-$A.pack <indexes &&
 427                         git rev-list --test-bitmap A &&
 428
 429                         git multi-pack-index write --bitmap --stdin-packs \
 430                                 --preferred-pack=pack-$B.pack <indexes &&
 431                         git rev-list --test-bitmap A
 432                 )
 433         '
 434 }
 435
 436 midx_bitmap_partial_tests () {
 437         rev_kind="${1:-midx}"
 438
 439         test_expect_success 'setup partial bitmaps' '
 440                 test_commit packed &&
 441                 git repack &&
 442                 test_commit loose &&
 443                 git multi-pack-index write --bitmap &&
 444                 test_path_is_file $midx &&
 445                 test_path_is_file $midx-$(midx_checksum $objdir).bitmap
 446         '
 447
 448         test_rev_exists HEAD~ "$rev_kind"
 449
 450         basic_bitmap_tests HEAD~
 451 }