t/t5333-pseudo-merge-bitmaps.sh - git - Git at Google

 #!/bin/sh

 test_description='pseudo-merge bitmaps'

 GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP=0

 . ./test-lib.sh

 test_pseudo_merges () {
 	test-tool bitmap dump-pseudo-merges
 }

 test_pseudo_merge_commits () {
 	test-tool bitmap dump-pseudo-merge-commits "$1"
 }

 test_pseudo_merges_satisfied () {
 	test_trace2_data bitmap pseudo_merges_satisfied "$1"
 }

 test_pseudo_merges_cascades () {
 	test_trace2_data bitmap pseudo_merges_cascades "$1"
 }

 test_pseudo_merges_reused () {
 	test_trace2_data pack-bitmap-write building_bitmaps_pseudo_merge_reused "$1"
 }

 tag_everything () {
 	git rev-list --all --no-object-names >in &&
 	sed 's|\(.*\)|create refs/tags/\1 \1|' in |
 	git update-ref --stdin
 }

 test_expect_success 'setup' '
 	test_commit_bulk 512 &&
 	tag_everything
 '

 test_expect_success 'bitmap traversal without pseudo-merges' '
 	git repack -adb &&

 	git rev-list --count --all --objects >expect &&

 	: >trace2.txt &&
 	GIT_TRACE2_EVENT=$PWD/trace2.txt \
 		git rev-list --count --all --objects --use-bitmap-index >actual &&

 	test_pseudo_merges_satisfied 0 <trace2.txt &&
 	test_pseudo_merges_cascades 0 <trace2.txt &&
 	test_pseudo_merges >merges &&
 	test_must_be_empty merges &&
 	test_cmp expect actual
 '

 test_expect_success 'pseudo-merges accurately represent their objects' '
 	test_config bitmapPseudoMerge.test.pattern "refs/tags/" &&
 	test_config bitmapPseudoMerge.test.maxMerges 8 &&
 	test_config bitmapPseudoMerge.test.stableThreshold never &&

 	git repack -adb &&

 	test_pseudo_merges >merges &&
 	test_line_count = 8 merges &&

 	for i in $(test_seq 0 $(($(wc -l <merges)-1)))
 	do
 		test-tool bitmap dump-pseudo-merge-commits $i >commits &&

 		git rev-list --objects --no-object-names --stdin <commits >expect.raw &&
 		test-tool bitmap dump-pseudo-merge-objects $i >actual.raw &&

 		sort -u <expect.raw >expect &&
 		sort -u <actual.raw >actual &&

 		test_cmp expect actual || return 1
 	done
 '

 test_expect_success 'bitmap traversal with pseudo-merges' '
 	: >trace2.txt &&
 	GIT_TRACE2_EVENT=$PWD/trace2.txt \
 		git rev-list --count --all --objects --use-bitmap-index >actual &&
 	git rev-list --count --all --objects >expect &&

 	test_pseudo_merges_satisfied 8 <trace2.txt &&
 	test_pseudo_merges_cascades 1 <trace2.txt &&
 	test_cmp expect actual
 '

 test_expect_success 'stale bitmap traversal with pseudo-merges' '
 	test_commit other &&

 	: >trace2.txt &&
 	GIT_TRACE2_EVENT=$PWD/trace2.txt \
 		git rev-list --count --all --objects --use-bitmap-index >actual &&
 	git rev-list --count --all --objects >expect &&

 	test_pseudo_merges_satisfied 8 <trace2.txt &&
 	test_pseudo_merges_cascades 1 <trace2.txt &&
 	test_cmp expect actual
 '

 test_expect_success PERL_TEST_HELPERS 'bitmapPseudoMerge.sampleRate adjusts commit selection rate' '
 	test_config bitmapPseudoMerge.test.pattern "refs/tags/" &&
 	test_config bitmapPseudoMerge.test.maxMerges 1 &&
 	test_config bitmapPseudoMerge.test.stableThreshold never &&

 	commits_nr=$(git rev-list --all --count) &&

 	for rate in 1.0 0.5 0.25
 	do
 		git -c bitmapPseudoMerge.test.sampleRate=$rate repack -adb &&

 		test_pseudo_merges >merges &&
 		test_line_count = 1 merges &&
 		test_pseudo_merge_commits 0 >commits &&

 		test-tool bitmap list-commits >bitmaps &&
 		bitmaps_nr="$(wc -l <bitmaps)" &&

 		perl -MPOSIX -e "print ceil(\$ARGV[0]*(\$ARGV[1]-\$ARGV[2]))" \
 			"$rate" "$commits_nr" "$bitmaps_nr" >expect &&

 		test $(cat expect) -eq $(wc -l <commits) || return 1
 	done
 '

 test_expect_success 'bitmapPseudoMerge.threshold excludes newer commits' '
 	git init pseudo-merge-threshold &&
 	(
 		cd pseudo-merge-threshold &&

 		new="1672549200" && # 2023-01-01
 		old="1641013200" && # 2022-01-01

 		GIT_COMMITTER_DATE="$new +0000" &&
 		export GIT_COMMITTER_DATE &&
 		test_commit_bulk --message="new" --notick 128 &&

 		GIT_COMMITTER_DATE="$old +0000" &&
 		export GIT_COMMITTER_DATE &&
 		test_commit_bulk --message="old" --notick 128 &&

 		tag_everything &&

 		git \
 			-c bitmapPseudoMerge.test.pattern="refs/tags/" \
 			-c bitmapPseudoMerge.test.maxMerges=1 \
 			-c bitmapPseudoMerge.test.threshold=$(($new - 1)) \
 			-c bitmapPseudoMerge.test.stableThreshold=never \
 			repack -adb &&

 		test_pseudo_merges >merges &&
 		test_line_count = 1 merges &&

 		test_pseudo_merge_commits 0 >oids &&
 		git cat-file --batch <oids >commits &&

 		test $(wc -l <oids) = $(grep -c "^committer.*$old +0000$" commits)
 	)
 '

 test_expect_success 'bitmapPseudoMerge.stableThreshold creates stable groups' '
 	(
 		cd pseudo-merge-threshold &&

 		new="1672549200" && # 2023-01-01
 		mid="1654059600" && # 2022-06-01
 		old="1641013200" && # 2022-01-01

 		GIT_COMMITTER_DATE="$mid +0000" &&
 		export GIT_COMMITTER_DATE &&
 		test_commit_bulk --message="mid" --notick 128 &&

 		git for-each-ref --format="delete %(refname)" refs/tags >in &&
 		git update-ref --stdin <in &&

 		tag_everything &&

 		git \
 			-c bitmapPseudoMerge.test.pattern="refs/tags/" \
 			-c bitmapPseudoMerge.test.maxMerges=1 \
 			-c bitmapPseudoMerge.test.threshold=$(($new - 1)) \
 			-c bitmapPseudoMerge.test.stableThreshold=$(($mid - 1)) \
 			-c bitmapPseudoMerge.test.stableSize=10 \
 			repack -adb &&

 		test_pseudo_merges >merges &&
 		merges_nr="$(wc -l <merges)" &&

 		for i in $(test_seq $(($merges_nr - 1)))
 		do
 			test_pseudo_merge_commits 0 >oids &&
 			git cat-file --batch <oids >commits &&

 			expect="$(grep -c "^committer.*$old +0000$" commits)" &&
 			actual="$(wc -l <oids)" &&

 			test $expect = $actual || return 1
 		done &&

 		test_pseudo_merge_commits $(($merges_nr - 1)) >oids &&
 		git cat-file --batch <oids >commits &&
 		test $(wc -l <oids) = $(grep -c "^committer.*$mid +0000$" commits)
 	)
 '

 test_expect_success 'out of order thresholds are rejected' '
 	# Disable the test var to remove a stderr message.
 	test_must_fail env GIT_TEST_NAME_HASH_VERSION=1 git \
 		-c bitmapPseudoMerge.test.pattern="refs/*" \
 		-c bitmapPseudoMerge.test.threshold=1.month.ago \
 		-c bitmapPseudoMerge.test.stableThreshold=1.week.ago \
 		repack -adb 2>err &&

 	cat >expect <<-EOF &&
 	fatal: pseudo-merge group ${SQ}test${SQ} has unstable threshold before stable one
 	EOF

 	test_cmp expect err
 '

 test_expect_success 'pseudo-merge pattern with capture groups' '
 	git init pseudo-merge-captures &&
 	(
 		cd pseudo-merge-captures &&

 		test_commit_bulk 128 &&
 		tag_everything &&

 		for r in $(test_seq 8)
 		do
 			test_commit_bulk 16 &&

 			git rev-list HEAD~16.. >in &&
 			sed "s|\(.*\)|create refs/remotes/$r/tags/\1 \1|" in >refs &&
 			git update-ref --stdin <refs || return 1
 		done &&

 		git \
 			-c bitmapPseudoMerge.tags.pattern="refs/remotes/([0-9]+)/tags/" \
 			-c bitmapPseudoMerge.tags.maxMerges=1 \
 			repack -adb &&

 		git for-each-ref --format="%(objectname) %(refname)" >refs &&

 		test_pseudo_merges >merges &&
 		for m in $(test_seq 0 $(($(wc -l <merges) - 1)))
 		do
 			test_pseudo_merge_commits $m >oids &&
 			grep -f oids refs |
 			sed -n "s|refs/remotes/\([0-9][0-9]*\)/|\1|p" &&
 			sort -u || return 1
 		done >remotes &&

 		test $(wc -l <remotes) -eq $(sort -u <remotes | wc -l)
 	)
 '

 test_expect_success 'pseudo-merge overlap setup' '
 	git init pseudo-merge-overlap &&
 	(
 		cd pseudo-merge-overlap &&

 		test_commit_bulk 256 &&
 		tag_everything &&

 		git \
 			-c bitmapPseudoMerge.all.pattern="refs/" \
 			-c bitmapPseudoMerge.all.maxMerges=1 \
 			-c bitmapPseudoMerge.all.stableThreshold=never \
 			-c bitmapPseudoMerge.tags.pattern="refs/tags/" \
 			-c bitmapPseudoMerge.tags.maxMerges=1 \
 			-c bitmapPseudoMerge.tags.stableThreshold=never \
 			repack -adb
 	)
 '

 test_expect_success 'pseudo-merge overlap generates overlapping groups' '
 	(
 		cd pseudo-merge-overlap &&

 		test_pseudo_merges >merges &&
 		test_line_count = 2 merges &&

 		test_pseudo_merge_commits 0 >commits-0.raw &&
 		test_pseudo_merge_commits 1 >commits-1.raw &&

 		sort commits-0.raw >commits-0 &&
 		sort commits-1.raw >commits-1 &&

 		comm -12 commits-0 commits-1 >overlap &&

 		test_line_count -gt 0 overlap
 	)
 '

 test_expect_success 'pseudo-merge overlap traversal' '
 	(
 		cd pseudo-merge-overlap &&

 		: >trace2.txt &&
 		GIT_TRACE2_EVENT=$PWD/trace2.txt \
 			git rev-list --count --all --objects --use-bitmap-index >actual &&
 		git rev-list --count --all --objects >expect &&

 		test_pseudo_merges_satisfied 2 <trace2.txt &&
 		test_pseudo_merges_cascades 1 <trace2.txt &&
 		test_cmp expect actual
 	)
 '

 test_expect_success 'pseudo-merge overlap stale traversal' '
 	(
 		cd pseudo-merge-overlap &&

 		test_commit other &&

 		: >trace2.txt &&
 		GIT_TRACE2_EVENT=$PWD/trace2.txt \
 			git rev-list --count --all --objects --use-bitmap-index >actual &&
 		git rev-list --count --all --objects >expect &&

 		test_pseudo_merges_satisfied 2 <trace2.txt &&
 		test_pseudo_merges_cascades 1 <trace2.txt &&
 		test_cmp expect actual
 	)
 '

 test_expect_success 'pseudo-merge reuse' '
 	git init pseudo-merge-reuse &&
 	(
 		cd pseudo-merge-reuse &&

 		stable="1641013200" && # 2022-01-01
 		unstable="1672549200" && # 2023-01-01

 		GIT_COMMITTER_DATE="$stable +0000" &&
 		export GIT_COMMITTER_DATE &&
 		test_commit_bulk --notick 128 &&
 		GIT_COMMITTER_DATE="$unstable +0000" &&
 		export GIT_COMMITTER_DATE &&
 		test_commit_bulk --notick 128 &&

 		tag_everything &&

 		git \
 			-c bitmapPseudoMerge.test.pattern="refs/tags/" \
 			-c bitmapPseudoMerge.test.maxMerges=1 \
 			-c bitmapPseudoMerge.test.threshold=now \
 			-c bitmapPseudoMerge.test.stableThreshold=$(($unstable - 1)) \
 			-c bitmapPseudoMerge.test.stableSize=512 \
 			repack -adb &&

 		test_pseudo_merges >merges &&
 		test_line_count = 2 merges &&

 		test_pseudo_merge_commits 0 >stable-oids.before &&
 		test_pseudo_merge_commits 1 >unstable-oids.before &&

 		: >trace2.txt &&
 		GIT_TRACE2_EVENT=$PWD/trace2.txt git \
 			-c bitmapPseudoMerge.test.pattern="refs/tags/" \
 			-c bitmapPseudoMerge.test.maxMerges=2 \
 			-c bitmapPseudoMerge.test.threshold=now \
 			-c bitmapPseudoMerge.test.stableThreshold=$(($unstable - 1)) \
 			-c bitmapPseudoMerge.test.stableSize=512 \
 			repack -adb &&

 		test_pseudo_merges_reused 1 <trace2.txt &&

 		test_pseudo_merges >merges &&
 		test_line_count = 3 merges &&

 		test_pseudo_merge_commits 0 >stable-oids.after &&
 		for i in 1 2
 		do
 			test_pseudo_merge_commits $i || return 1
 		done >unstable-oids.after &&

 		sort -u <stable-oids.before >expect &&
 		sort -u <stable-oids.after >actual &&
 		test_cmp expect actual &&

 		sort -u <unstable-oids.before >expect &&
 		sort -u <unstable-oids.after >actual &&
 		test_cmp expect actual
 	)
 '

 test_expect_success 'empty pseudo-merge group' '
 	git init pseudo-merge-empty-group &&
 	(
 		cd pseudo-merge-empty-group &&

 		# Ensure that a pseudo-merge group with no unstable
 		# commits does not generate an empty pseudo-merge
 		# bitmap.
 		git config bitmapPseudoMerge.empty.pattern refs/ &&

 		test_commit base &&
 		git repack -adb &&

 		test-tool bitmap dump-pseudo-merges >merges &&
 		test_line_count = 1 merges &&

 		test 0 -eq "$(grep -c commits=0 <merges)"
 	)
 '

 test_expect_success 'pseudo-merge closure' '
 	git init pseudo-merge-closure &&
 	(
 		cd pseudo-merge-closure &&

 		test_commit A &&
 		git repack -d &&

 		test_commit B &&

 		# Note that the contents of A is packed, but B is not. A
 		# (and the objects reachable from it) are thus visible
 		# to the MIDX, but the same is not true for B and its
 		# objects.
 		#
 		# Ensure that we do not attempt to create a pseudo-merge
 		# for B, depsite it matching the below pseudo-merge
 		# group pattern, as doing so would result in a failure
 		# to write a non-closed bitmap.
 		git config bitmapPseudoMerge.test.pattern refs/ &&
 		git config bitmapPseudoMerge.test.threshold now &&

 		git multi-pack-index write --bitmap &&

 		test-tool bitmap dump-pseudo-merges >pseudo-merges &&
 		test_line_count = 1 pseudo-merges &&

 		git rev-parse A >expect &&

 		test-tool bitmap list-commits >actual &&
 		test_cmp expect actual &&
 		test-tool bitmap dump-pseudo-merge-commits 0 >actual &&
 		test_cmp expect actual
 	)
 '

 test_expect_success 'use pseudo-merge in boundary traversal' '
 	git init pseudo-merge-boundary-traversal &&
 	(
 		cd pseudo-merge-boundary-traversal &&

 		git config bitmapPseudoMerge.test.pattern refs/ &&
 		git config pack.useBitmapBoundaryTraversal true &&

 		test_commit A &&
 		git repack -adb &&
 		test_commit B &&

 		nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
 		test 1 -eq "$nr"
 	)
 '

 test_expect_success 'apply pseudo-merges during fill-in traversal' '
 	test_when_finished "rm -fr pseudo-merge-fill-in-traversal" &&
 	git init pseudo-merge-fill-in-traversal &&
 	(
 		cd pseudo-merge-fill-in-traversal &&

 		git config bitmapPseudoMerge.test.pattern refs/tags/ &&
 		git config bitmapPseudoMerge.test.maxMerges 1 &&
 		git config bitmapPseudoMerge.test.stableThreshold never &&

 		test_commit_bulk 64 &&
 		tag_everything &&
 		git repack -ad &&

 		pack=$(ls .git/objects/pack/pack-*.pack) &&
 		git rev-parse HEAD~63 >in &&
 		test-tool bitmap write "$(basename $pack)" <in &&

 		test_pseudo_merges >merges &&
 		test_line_count = 1 merges &&

 		test_commit stale &&

 		git rev-list --count --objects HEAD >expect &&

 		: >trace2.txt &&
 		GIT_TRACE2_EVENT=$PWD/trace2.txt \
 			git rev-list --count --objects --use-bitmap-index HEAD >actual &&
 		test_pseudo_merges_satisfied 1 <trace2.txt &&

 		test_cmp expect actual
 	)
 '

 test_expect_success 'apply pseudo-merges from multiple groups during fill-in' '
 	test_when_finished "rm -fr pseudo-merge-fill-in-multi" &&
 	git init pseudo-merge-fill-in-multi &&
 	(
 		cd pseudo-merge-fill-in-multi &&

 		test_commit base &&
 		base=$(git rev-parse HEAD) &&

 		for side in left right
 		do
 			git checkout -B $side base &&

 			test_commit_bulk --id=$side 64 &&
 			git rev-list --no-object-names HEAD --not $base >in &&
 			while read oid
 			do
 				echo "create refs/group-$side/$oid $oid" || return 1
 			done <in | git update-ref --stdin || return 1
 		done &&

 		git checkout left &&
 		git merge right &&
 		git repack -ad &&

 		git config bitmapPseudoMerge.left.pattern "refs/group-left/" &&
 		git config bitmapPseudoMerge.left.maxMerges 1 &&
 		git config bitmapPseudoMerge.left.stableThreshold never &&

 		git config bitmapPseudoMerge.right.pattern "refs/group-right/" &&
 		git config bitmapPseudoMerge.right.maxMerges 1 &&
 		git config bitmapPseudoMerge.right.stableThreshold never &&

 		pack="$(ls .git/objects/pack/pack-*.pack)" &&
 		git rev-parse "$base" >in &&
 		test-tool bitmap write "$(basename $pack)" <in &&

 		test_pseudo_merges >merges &&
 		test_line_count = 2 merges &&

 		test_commit stale &&

 		git rev-list --count --objects HEAD >expect &&

 		: >trace2.txt &&
 		GIT_TRACE2_EVENT=$PWD/trace2.txt \
 			git rev-list --count --objects --use-bitmap-index HEAD >actual &&
 		test_pseudo_merges_satisfied 2 <trace2.txt &&

 		test_cmp expect actual
 	)
 '

 test_expect_success 'apply pseudo-merges with overlapping groups during fill-in' '
 	test_when_finished "rm -fr pseudo-merge-fill-in-overlap" &&
 	git init pseudo-merge-fill-in-overlap &&
 	(
 		cd pseudo-merge-fill-in-overlap &&

 		test_commit_bulk 64 &&
 		tag_everything &&
 		git repack -ad &&

 		pack="$(ls .git/objects/pack/pack-*.pack)" &&

 		# Use two pseudo-merge group patterns that both match
 		# refs/tags/, so every tagged commit belongs to both
 		# groups. This exercises the extended lookup table
 		# path in apply_pseudo_merges_for_commit().
 		git config bitmapPseudoMerge.all.pattern "refs/tags/" &&
 		git config bitmapPseudoMerge.all.maxMerges 1 &&
 		git config bitmapPseudoMerge.all.stableThreshold never &&

 		git config bitmapPseudoMerge.tags.pattern "refs/tags/" &&
 		git config bitmapPseudoMerge.tags.maxMerges 1 &&
 		git config bitmapPseudoMerge.tags.stableThreshold never &&

 		git rev-parse HEAD~63 >in &&
 		test-tool bitmap write "$(basename $pack)" <in &&

 		test_pseudo_merges >merges &&
 		test_line_count = 2 merges &&

 		test_commit stale &&

 		git rev-list --count --objects HEAD >expect &&

 		: >trace2.txt &&
 		GIT_TRACE2_EVENT=$PWD/trace2.txt \
 			git rev-list --count --objects --use-bitmap-index HEAD >actual &&
 		test_pseudo_merges_satisfied 2 <trace2.txt &&

 		test_cmp expect actual
 	)
 '

 test_expect_success 'pseudo-merge commits are correctly classified by date' '
 	test_when_finished "rm -fr pseudo-merge-date-classification" &&
 	git init pseudo-merge-date-classification &&
 	(
 		cd pseudo-merge-date-classification &&

 		test_commit_bulk 64 &&

 		tag_everything &&
 		git repack -ad &&

 		pack="$(ls .git/objects/pack/pack-*.pack)" &&

 		# Configure two pseudo-merge groups: one that only
 		# matches "stable" refs (older than one month), and
 		# one that matches all refs. With 64 tags whose
 		# commits are all younger than one month, the
 		# "stable" group should have zero pseudo-merges and
 		# the "all" group should have one.
 		#
 		# Use GIT_TEST_DATE_NOW to align "now" (and therefore
 		# "1.month.ago") with the test_tick timestamps so that
 		# the commits are within the last month.
 		#
 		# Without parsing the commit, its date field would
 		# be zero, causing it to satisfy date <= threshold
 		# for the "stable" group as well, and both groups
 		# would produce pseudo-merges.
 		git config bitmapPseudoMerge.stable.pattern "refs/tags/" &&
 		git config bitmapPseudoMerge.stable.maxMerges 64 &&
 		git config bitmapPseudoMerge.stable.stableThreshold never &&
 		git config bitmapPseudoMerge.stable.threshold 1.month.ago &&

 		git config bitmapPseudoMerge.all.pattern "refs/tags/" &&
 		git config bitmapPseudoMerge.all.maxMerges 1 &&
 		git config bitmapPseudoMerge.all.stableThreshold never &&
 		git config bitmapPseudoMerge.all.threshold now &&

 		git rev-parse HEAD~63 >in &&
 		GIT_TEST_DATE_NOW=$test_tick \
 			test-tool bitmap write "$(basename $pack)" <in &&

 		test_pseudo_merges >merges &&
 		test_line_count = 1 merges
 	)
 '

 test_expect_success 'sampleRate=0 does not cause division by zero' '
 	test_when_finished "rm -fr pseudo-merge-sample-rate-zero" &&
 	git init pseudo-merge-sample-rate-zero &&
 	(
 		cd pseudo-merge-sample-rate-zero &&

 		test_commit_bulk 64 &&
 		tag_everything &&
 		git repack -ad &&

 		pack="$(ls .git/objects/pack/pack-*.pack)" &&

 		git config bitmapPseudoMerge.test.pattern "refs/tags/" &&
 		git config bitmapPseudoMerge.test.maxMerges 1 &&
 		git config bitmapPseudoMerge.test.sampleRate 0 &&
 		git config bitmapPseudoMerge.test.threshold now &&
 		git config bitmapPseudoMerge.test.stableThreshold never &&

 		git rev-parse HEAD~63 >in &&
 		test-tool bitmap write "$(basename $pack)" <in
 	)
 '

 test_expect_success 'duplicate pseudo-merge pattern does not leak' '
 	test_when_finished "rm -fr pseudo-merge-dup-pattern" &&
 	git init pseudo-merge-dup-pattern &&
 	(
 		cd pseudo-merge-dup-pattern &&

 		test_commit_bulk 64 &&
 		tag_everything &&
 		git repack -ad &&

 		pack=$(ls .git/objects/pack/pack-*.pack) &&

 		# Set the same group'\''s pattern twice. The second
 		# assignment should cleanly release the compiled regex
 		# from the first without leaking.
 		git config bitmapPseudoMerge.test.pattern "refs/tags/" &&
 		git config --add bitmapPseudoMerge.test.pattern "refs/tags/" &&
 		git config bitmapPseudoMerge.test.maxMerges 1 &&
 		git config bitmapPseudoMerge.test.threshold now &&
 		git config bitmapPseudoMerge.test.stableThreshold never &&

 		git rev-parse HEAD~63 >in &&
 		test-tool bitmap write "$(basename $pack)" <in &&

 		test_pseudo_merges >merges &&
 		test_line_count = 1 merges
 	)
 '

 test_done
	#!/bin/sh

	test_description='pseudo-merge bitmaps'

	GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP=0

	. ./test-lib.sh

	test_pseudo_merges () {
	test-tool bitmap dump-pseudo-merges
	}

	test_pseudo_merge_commits () {
	test-tool bitmap dump-pseudo-merge-commits "$1"
	}

	test_pseudo_merges_satisfied () {
	test_trace2_data bitmap pseudo_merges_satisfied "$1"
	}

	test_pseudo_merges_cascades () {
	test_trace2_data bitmap pseudo_merges_cascades "$1"
	}

	test_pseudo_merges_reused () {
	test_trace2_data pack-bitmap-write building_bitmaps_pseudo_merge_reused "$1"
	}

	tag_everything () {
	git rev-list --all --no-object-names >in &&
	sed 's\|\(.*\)\|create refs/tags/\1 \1\|' in \|
	git update-ref --stdin
	}

	test_expect_success 'setup' '
	test_commit_bulk 512 &&
	tag_everything
	'

	test_expect_success 'bitmap traversal without pseudo-merges' '
	git repack -adb &&

	git rev-list --count --all --objects >expect &&

	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt \
	git rev-list --count --all --objects --use-bitmap-index >actual &&

	test_pseudo_merges_satisfied 0 <trace2.txt &&
	test_pseudo_merges_cascades 0 <trace2.txt &&
	test_pseudo_merges >merges &&
	test_must_be_empty merges &&
	test_cmp expect actual
	'

	test_expect_success 'pseudo-merges accurately represent their objects' '
	test_config bitmapPseudoMerge.test.pattern "refs/tags/" &&
	test_config bitmapPseudoMerge.test.maxMerges 8 &&
	test_config bitmapPseudoMerge.test.stableThreshold never &&

	git repack -adb &&

	test_pseudo_merges >merges &&
	test_line_count = 8 merges &&

	for i in $(test_seq 0 $(($(wc -l <merges)-1)))
	do
	test-tool bitmap dump-pseudo-merge-commits $i >commits &&

	git rev-list --objects --no-object-names --stdin <commits >expect.raw &&
	test-tool bitmap dump-pseudo-merge-objects $i >actual.raw &&

	sort -u <expect.raw >expect &&
	sort -u <actual.raw >actual &&

	test_cmp expect actual \|\| return 1
	done
	'

	test_expect_success 'bitmap traversal with pseudo-merges' '
	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt \
	git rev-list --count --all --objects --use-bitmap-index >actual &&
	git rev-list --count --all --objects >expect &&

	test_pseudo_merges_satisfied 8 <trace2.txt &&
	test_pseudo_merges_cascades 1 <trace2.txt &&
	test_cmp expect actual
	'

	test_expect_success 'stale bitmap traversal with pseudo-merges' '
	test_commit other &&

	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt \
	git rev-list --count --all --objects --use-bitmap-index >actual &&
	git rev-list --count --all --objects >expect &&

	test_pseudo_merges_satisfied 8 <trace2.txt &&
	test_pseudo_merges_cascades 1 <trace2.txt &&
	test_cmp expect actual
	'

	test_expect_success PERL_TEST_HELPERS 'bitmapPseudoMerge.sampleRate adjusts commit selection rate' '
	test_config bitmapPseudoMerge.test.pattern "refs/tags/" &&
	test_config bitmapPseudoMerge.test.maxMerges 1 &&
	test_config bitmapPseudoMerge.test.stableThreshold never &&

	commits_nr=$(git rev-list --all --count) &&

	for rate in 1.0 0.5 0.25
	do
	git -c bitmapPseudoMerge.test.sampleRate=$rate repack -adb &&

	test_pseudo_merges >merges &&
	test_line_count = 1 merges &&
	test_pseudo_merge_commits 0 >commits &&

	test-tool bitmap list-commits >bitmaps &&
	bitmaps_nr="$(wc -l <bitmaps)" &&

	perl -MPOSIX -e "print ceil(\$ARGV[0]*(\$ARGV[1]-\$ARGV[2]))" \
	"$rate" "$commits_nr" "$bitmaps_nr" >expect &&

	test $(cat expect) -eq $(wc -l <commits) \|\| return 1
	done
	'

	test_expect_success 'bitmapPseudoMerge.threshold excludes newer commits' '
	git init pseudo-merge-threshold &&
	(
	cd pseudo-merge-threshold &&

	new="1672549200" && # 2023-01-01
	old="1641013200" && # 2022-01-01

	GIT_COMMITTER_DATE="$new +0000" &&
	export GIT_COMMITTER_DATE &&
	test_commit_bulk --message="new" --notick 128 &&

	GIT_COMMITTER_DATE="$old +0000" &&
	export GIT_COMMITTER_DATE &&
	test_commit_bulk --message="old" --notick 128 &&

	tag_everything &&

	git \
	-c bitmapPseudoMerge.test.pattern="refs/tags/" \
	-c bitmapPseudoMerge.test.maxMerges=1 \
	-c bitmapPseudoMerge.test.threshold=$(($new - 1)) \
	-c bitmapPseudoMerge.test.stableThreshold=never \
	repack -adb &&

	test_pseudo_merges >merges &&
	test_line_count = 1 merges &&

	test_pseudo_merge_commits 0 >oids &&
	git cat-file --batch <oids >commits &&

	test $(wc -l <oids) = $(grep -c "^committer.*$old +0000$" commits)
	)
	'

	test_expect_success 'bitmapPseudoMerge.stableThreshold creates stable groups' '
	(
	cd pseudo-merge-threshold &&

	new="1672549200" && # 2023-01-01
	mid="1654059600" && # 2022-06-01
	old="1641013200" && # 2022-01-01

	GIT_COMMITTER_DATE="$mid +0000" &&
	export GIT_COMMITTER_DATE &&
	test_commit_bulk --message="mid" --notick 128 &&

	git for-each-ref --format="delete %(refname)" refs/tags >in &&
	git update-ref --stdin <in &&

	tag_everything &&

	git \
	-c bitmapPseudoMerge.test.pattern="refs/tags/" \
	-c bitmapPseudoMerge.test.maxMerges=1 \
	-c bitmapPseudoMerge.test.threshold=$(($new - 1)) \
	-c bitmapPseudoMerge.test.stableThreshold=$(($mid - 1)) \
	-c bitmapPseudoMerge.test.stableSize=10 \
	repack -adb &&

	test_pseudo_merges >merges &&
	merges_nr="$(wc -l <merges)" &&

	for i in $(test_seq $(($merges_nr - 1)))
	do
	test_pseudo_merge_commits 0 >oids &&
	git cat-file --batch <oids >commits &&

	expect="$(grep -c "^committer.*$old +0000$" commits)" &&
	actual="$(wc -l <oids)" &&

	test $expect = $actual \|\| return 1
	done &&

	test_pseudo_merge_commits $(($merges_nr - 1)) >oids &&
	git cat-file --batch <oids >commits &&
	test $(wc -l <oids) = $(grep -c "^committer.*$mid +0000$" commits)
	)
	'

	test_expect_success 'out of order thresholds are rejected' '
	# Disable the test var to remove a stderr message.
	test_must_fail env GIT_TEST_NAME_HASH_VERSION=1 git \
	-c bitmapPseudoMerge.test.pattern="refs/*" \
	-c bitmapPseudoMerge.test.threshold=1.month.ago \
	-c bitmapPseudoMerge.test.stableThreshold=1.week.ago \
	repack -adb 2>err &&

	cat >expect <<-EOF &&
	fatal: pseudo-merge group ${SQ}test${SQ} has unstable threshold before stable one
	EOF

	test_cmp expect err
	'

	test_expect_success 'pseudo-merge pattern with capture groups' '
	git init pseudo-merge-captures &&
	(
	cd pseudo-merge-captures &&

	test_commit_bulk 128 &&
	tag_everything &&

	for r in $(test_seq 8)
	do
	test_commit_bulk 16 &&

	git rev-list HEAD~16.. >in &&
	sed "s\|\(.*\)\|create refs/remotes/$r/tags/\1 \1\|" in >refs &&
	git update-ref --stdin <refs \|\| return 1
	done &&

	git \
	-c bitmapPseudoMerge.tags.pattern="refs/remotes/([0-9]+)/tags/" \
	-c bitmapPseudoMerge.tags.maxMerges=1 \
	repack -adb &&

	git for-each-ref --format="%(objectname) %(refname)" >refs &&

	test_pseudo_merges >merges &&
	for m in $(test_seq 0 $(($(wc -l <merges) - 1)))
	do
	test_pseudo_merge_commits $m >oids &&
	grep -f oids refs \|
	sed -n "s\|refs/remotes/\([0-9][0-9]*\)/\|\1\|p" &&
	sort -u \|\| return 1
	done >remotes &&

	test $(wc -l <remotes) -eq $(sort -u <remotes \| wc -l)
	)
	'

	test_expect_success 'pseudo-merge overlap setup' '
	git init pseudo-merge-overlap &&
	(
	cd pseudo-merge-overlap &&

	test_commit_bulk 256 &&
	tag_everything &&

	git \
	-c bitmapPseudoMerge.all.pattern="refs/" \
	-c bitmapPseudoMerge.all.maxMerges=1 \
	-c bitmapPseudoMerge.all.stableThreshold=never \
	-c bitmapPseudoMerge.tags.pattern="refs/tags/" \
	-c bitmapPseudoMerge.tags.maxMerges=1 \
	-c bitmapPseudoMerge.tags.stableThreshold=never \
	repack -adb
	)
	'

	test_expect_success 'pseudo-merge overlap generates overlapping groups' '
	(
	cd pseudo-merge-overlap &&

	test_pseudo_merges >merges &&
	test_line_count = 2 merges &&

	test_pseudo_merge_commits 0 >commits-0.raw &&
	test_pseudo_merge_commits 1 >commits-1.raw &&

	sort commits-0.raw >commits-0 &&
	sort commits-1.raw >commits-1 &&

	comm -12 commits-0 commits-1 >overlap &&

	test_line_count -gt 0 overlap
	)
	'

	test_expect_success 'pseudo-merge overlap traversal' '
	(
	cd pseudo-merge-overlap &&

	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt \
	git rev-list --count --all --objects --use-bitmap-index >actual &&
	git rev-list --count --all --objects >expect &&

	test_pseudo_merges_satisfied 2 <trace2.txt &&
	test_pseudo_merges_cascades 1 <trace2.txt &&
	test_cmp expect actual
	)
	'

	test_expect_success 'pseudo-merge overlap stale traversal' '
	(
	cd pseudo-merge-overlap &&

	test_commit other &&

	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt \
	git rev-list --count --all --objects --use-bitmap-index >actual &&
	git rev-list --count --all --objects >expect &&

	test_pseudo_merges_satisfied 2 <trace2.txt &&
	test_pseudo_merges_cascades 1 <trace2.txt &&
	test_cmp expect actual
	)
	'

	test_expect_success 'pseudo-merge reuse' '
	git init pseudo-merge-reuse &&
	(
	cd pseudo-merge-reuse &&

	stable="1641013200" && # 2022-01-01
	unstable="1672549200" && # 2023-01-01

	GIT_COMMITTER_DATE="$stable +0000" &&
	export GIT_COMMITTER_DATE &&
	test_commit_bulk --notick 128 &&
	GIT_COMMITTER_DATE="$unstable +0000" &&
	export GIT_COMMITTER_DATE &&
	test_commit_bulk --notick 128 &&

	tag_everything &&

	git \
	-c bitmapPseudoMerge.test.pattern="refs/tags/" \
	-c bitmapPseudoMerge.test.maxMerges=1 \
	-c bitmapPseudoMerge.test.threshold=now \
	-c bitmapPseudoMerge.test.stableThreshold=$(($unstable - 1)) \
	-c bitmapPseudoMerge.test.stableSize=512 \
	repack -adb &&

	test_pseudo_merges >merges &&
	test_line_count = 2 merges &&

	test_pseudo_merge_commits 0 >stable-oids.before &&
	test_pseudo_merge_commits 1 >unstable-oids.before &&

	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt git \
	-c bitmapPseudoMerge.test.pattern="refs/tags/" \
	-c bitmapPseudoMerge.test.maxMerges=2 \
	-c bitmapPseudoMerge.test.threshold=now \
	-c bitmapPseudoMerge.test.stableThreshold=$(($unstable - 1)) \
	-c bitmapPseudoMerge.test.stableSize=512 \
	repack -adb &&

	test_pseudo_merges_reused 1 <trace2.txt &&

	test_pseudo_merges >merges &&
	test_line_count = 3 merges &&

	test_pseudo_merge_commits 0 >stable-oids.after &&
	for i in 1 2
	do
	test_pseudo_merge_commits $i \|\| return 1
	done >unstable-oids.after &&

	sort -u <stable-oids.before >expect &&
	sort -u <stable-oids.after >actual &&
	test_cmp expect actual &&

	sort -u <unstable-oids.before >expect &&
	sort -u <unstable-oids.after >actual &&
	test_cmp expect actual
	)
	'

	test_expect_success 'empty pseudo-merge group' '
	git init pseudo-merge-empty-group &&
	(
	cd pseudo-merge-empty-group &&

	# Ensure that a pseudo-merge group with no unstable
	# commits does not generate an empty pseudo-merge
	# bitmap.
	git config bitmapPseudoMerge.empty.pattern refs/ &&

	test_commit base &&
	git repack -adb &&

	test-tool bitmap dump-pseudo-merges >merges &&
	test_line_count = 1 merges &&

	test 0 -eq "$(grep -c commits=0 <merges)"
	)
	'

	test_expect_success 'pseudo-merge closure' '
	git init pseudo-merge-closure &&
	(
	cd pseudo-merge-closure &&

	test_commit A &&
	git repack -d &&

	test_commit B &&

	# Note that the contents of A is packed, but B is not. A
	# (and the objects reachable from it) are thus visible
	# to the MIDX, but the same is not true for B and its
	# objects.
	#
	# Ensure that we do not attempt to create a pseudo-merge
	# for B, depsite it matching the below pseudo-merge
	# group pattern, as doing so would result in a failure
	# to write a non-closed bitmap.
	git config bitmapPseudoMerge.test.pattern refs/ &&
	git config bitmapPseudoMerge.test.threshold now &&

	git multi-pack-index write --bitmap &&

	test-tool bitmap dump-pseudo-merges >pseudo-merges &&
	test_line_count = 1 pseudo-merges &&

	git rev-parse A >expect &&

	test-tool bitmap list-commits >actual &&
	test_cmp expect actual &&
	test-tool bitmap dump-pseudo-merge-commits 0 >actual &&
	test_cmp expect actual
	)
	'

	test_expect_success 'use pseudo-merge in boundary traversal' '
	git init pseudo-merge-boundary-traversal &&
	(
	cd pseudo-merge-boundary-traversal &&

	git config bitmapPseudoMerge.test.pattern refs/ &&
	git config pack.useBitmapBoundaryTraversal true &&

	test_commit A &&
	git repack -adb &&
	test_commit B &&

	nr=$(git rev-list --count --use-bitmap-index HEAD~1..HEAD) &&
	test 1 -eq "$nr"
	)
	'

	test_expect_success 'apply pseudo-merges during fill-in traversal' '
	test_when_finished "rm -fr pseudo-merge-fill-in-traversal" &&
	git init pseudo-merge-fill-in-traversal &&
	(
	cd pseudo-merge-fill-in-traversal &&

	git config bitmapPseudoMerge.test.pattern refs/tags/ &&
	git config bitmapPseudoMerge.test.maxMerges 1 &&
	git config bitmapPseudoMerge.test.stableThreshold never &&

	test_commit_bulk 64 &&
	tag_everything &&
	git repack -ad &&

	pack=$(ls .git/objects/pack/pack-*.pack) &&
	git rev-parse HEAD~63 >in &&
	test-tool bitmap write "$(basename $pack)" <in &&

	test_pseudo_merges >merges &&
	test_line_count = 1 merges &&

	test_commit stale &&

	git rev-list --count --objects HEAD >expect &&

	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt \
	git rev-list --count --objects --use-bitmap-index HEAD >actual &&
	test_pseudo_merges_satisfied 1 <trace2.txt &&

	test_cmp expect actual
	)
	'

	test_expect_success 'apply pseudo-merges from multiple groups during fill-in' '
	test_when_finished "rm -fr pseudo-merge-fill-in-multi" &&
	git init pseudo-merge-fill-in-multi &&
	(
	cd pseudo-merge-fill-in-multi &&

	test_commit base &&
	base=$(git rev-parse HEAD) &&

	for side in left right
	do
	git checkout -B $side base &&

	test_commit_bulk --id=$side 64 &&
	git rev-list --no-object-names HEAD --not $base >in &&
	while read oid
	do
	echo "create refs/group-$side/$oid $oid" \|\| return 1
	done <in \| git update-ref --stdin \|\| return 1
	done &&

	git checkout left &&
	git merge right &&
	git repack -ad &&

	git config bitmapPseudoMerge.left.pattern "refs/group-left/" &&
	git config bitmapPseudoMerge.left.maxMerges 1 &&
	git config bitmapPseudoMerge.left.stableThreshold never &&

	git config bitmapPseudoMerge.right.pattern "refs/group-right/" &&
	git config bitmapPseudoMerge.right.maxMerges 1 &&
	git config bitmapPseudoMerge.right.stableThreshold never &&

	pack="$(ls .git/objects/pack/pack-*.pack)" &&
	git rev-parse "$base" >in &&
	test-tool bitmap write "$(basename $pack)" <in &&

	test_pseudo_merges >merges &&
	test_line_count = 2 merges &&

	test_commit stale &&

	git rev-list --count --objects HEAD >expect &&

	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt \
	git rev-list --count --objects --use-bitmap-index HEAD >actual &&
	test_pseudo_merges_satisfied 2 <trace2.txt &&

	test_cmp expect actual
	)
	'

	test_expect_success 'apply pseudo-merges with overlapping groups during fill-in' '
	test_when_finished "rm -fr pseudo-merge-fill-in-overlap" &&
	git init pseudo-merge-fill-in-overlap &&
	(
	cd pseudo-merge-fill-in-overlap &&

	test_commit_bulk 64 &&
	tag_everything &&
	git repack -ad &&

	pack="$(ls .git/objects/pack/pack-*.pack)" &&

	# Use two pseudo-merge group patterns that both match
	# refs/tags/, so every tagged commit belongs to both
	# groups. This exercises the extended lookup table
	# path in apply_pseudo_merges_for_commit().
	git config bitmapPseudoMerge.all.pattern "refs/tags/" &&
	git config bitmapPseudoMerge.all.maxMerges 1 &&
	git config bitmapPseudoMerge.all.stableThreshold never &&

	git config bitmapPseudoMerge.tags.pattern "refs/tags/" &&
	git config bitmapPseudoMerge.tags.maxMerges 1 &&
	git config bitmapPseudoMerge.tags.stableThreshold never &&

	git rev-parse HEAD~63 >in &&
	test-tool bitmap write "$(basename $pack)" <in &&

	test_pseudo_merges >merges &&
	test_line_count = 2 merges &&

	test_commit stale &&

	git rev-list --count --objects HEAD >expect &&

	: >trace2.txt &&
	GIT_TRACE2_EVENT=$PWD/trace2.txt \
	git rev-list --count --objects --use-bitmap-index HEAD >actual &&
	test_pseudo_merges_satisfied 2 <trace2.txt &&

	test_cmp expect actual
	)
	'

	test_expect_success 'pseudo-merge commits are correctly classified by date' '
	test_when_finished "rm -fr pseudo-merge-date-classification" &&
	git init pseudo-merge-date-classification &&
	(
	cd pseudo-merge-date-classification &&

	test_commit_bulk 64 &&

	tag_everything &&
	git repack -ad &&

	pack="$(ls .git/objects/pack/pack-*.pack)" &&

	# Configure two pseudo-merge groups: one that only
	# matches "stable" refs (older than one month), and
	# one that matches all refs. With 64 tags whose
	# commits are all younger than one month, the
	# "stable" group should have zero pseudo-merges and
	# the "all" group should have one.
	#
	# Use GIT_TEST_DATE_NOW to align "now" (and therefore
	# "1.month.ago") with the test_tick timestamps so that
	# the commits are within the last month.
	#
	# Without parsing the commit, its date field would
	# be zero, causing it to satisfy date <= threshold
	# for the "stable" group as well, and both groups
	# would produce pseudo-merges.
	git config bitmapPseudoMerge.stable.pattern "refs/tags/" &&
	git config bitmapPseudoMerge.stable.maxMerges 64 &&
	git config bitmapPseudoMerge.stable.stableThreshold never &&
	git config bitmapPseudoMerge.stable.threshold 1.month.ago &&

	git config bitmapPseudoMerge.all.pattern "refs/tags/" &&
	git config bitmapPseudoMerge.all.maxMerges 1 &&
	git config bitmapPseudoMerge.all.stableThreshold never &&
	git config bitmapPseudoMerge.all.threshold now &&

	git rev-parse HEAD~63 >in &&
	GIT_TEST_DATE_NOW=$test_tick \
	test-tool bitmap write "$(basename $pack)" <in &&

	test_pseudo_merges >merges &&
	test_line_count = 1 merges
	)
	'

	test_expect_success 'sampleRate=0 does not cause division by zero' '
	test_when_finished "rm -fr pseudo-merge-sample-rate-zero" &&
	git init pseudo-merge-sample-rate-zero &&
	(
	cd pseudo-merge-sample-rate-zero &&

	test_commit_bulk 64 &&
	tag_everything &&
	git repack -ad &&

	pack="$(ls .git/objects/pack/pack-*.pack)" &&

	git config bitmapPseudoMerge.test.pattern "refs/tags/" &&
	git config bitmapPseudoMerge.test.maxMerges 1 &&
	git config bitmapPseudoMerge.test.sampleRate 0 &&
	git config bitmapPseudoMerge.test.threshold now &&
	git config bitmapPseudoMerge.test.stableThreshold never &&

	git rev-parse HEAD~63 >in &&
	test-tool bitmap write "$(basename $pack)" <in
	)
	'

	test_expect_success 'duplicate pseudo-merge pattern does not leak' '
	test_when_finished "rm -fr pseudo-merge-dup-pattern" &&
	git init pseudo-merge-dup-pattern &&
	(
	cd pseudo-merge-dup-pattern &&

	test_commit_bulk 64 &&
	tag_everything &&
	git repack -ad &&

	pack=$(ls .git/objects/pack/pack-*.pack) &&

	# Set the same group'\''s pattern twice. The second
	# assignment should cleanly release the compiled regex
	# from the first without leaking.
	git config bitmapPseudoMerge.test.pattern "refs/tags/" &&
	git config --add bitmapPseudoMerge.test.pattern "refs/tags/" &&
	git config bitmapPseudoMerge.test.maxMerges 1 &&
	git config bitmapPseudoMerge.test.threshold now &&
	git config bitmapPseudoMerge.test.stableThreshold never &&

	git rev-parse HEAD~63 >in &&
	test-tool bitmap write "$(basename $pack)" <in &&

	test_pseudo_merges >merges &&
	test_line_count = 1 merges
	)
	'

	test_done