[PATCH 12/13] packfile: allow looking up compat object IDs in packs

[Christian Couder <christian.couder@gmail.com>]

From: "brian m. carlson" <sandals@crustytoothpaste.net>

Now that we have the ability to store compatibility object IDs in pack
index v3, we also want to be able to look up these object IDs.  Our
disambiguation code can work with a particular hash algorithm or with
any hash algorithm, the most notable instance of the latter case being
when git rev-parse is invoked with --output-object-format.

We already handle the single algorithm case just fine, but we don't
gracefully handle resolving an object ID in any algorithm.  Solve this
by iterating through the algorithms and, if the algorithm is both one of
the desired ones and one our repository supports, then try looking up
the object IDs for that algorithm.  Use an intermediate variable so that
we can pass the correct algorithm in the object ID's algo member, which
will cause the correct tables to be looked up.

Write this check as two if statements because the logic is complex and
it is easier to understand as two statements.  The compiler will
optimize it appropriately.

When looking up an object ID, we find positions in the table sorted by
that object ID's algorithm. So read the object IDs there for that
algorithm with nth_packed_object_id_algop(), and add
nth_packed_object_offset_algop() to get their offsets.

Skip the compatibility algorithm for packs with an index older than v3,
as these only store object IDs in the main algorithm.

Add a test that looks up an abbreviated compatibility object ID of a
packed object.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
Signed-off-by: Christian Couder <christian.couder@gmail.com>
---
 odb/source-packed.c           | 83 +++++++++++++++++++++++------------
 packfile.c                    | 13 +++++-
 packfile.h                    |  7 +++
 t/t1016-compatObjectFormat.sh | 30 +++++++++++++
 4 files changed, 104 insertions(+), 29 deletions(-)

diff --git a/odb/source-packed.c b/odb/source-packed.c
index 4ecc2de818..8b16e8da29 100644
--- a/odb/source-packed.c
+++ b/odb/source-packed.c
@@ -295,37 +295,64 @@ static int for_each_prefixed_object_in_pack(
 	int len = opts->prefix_hex_len > p->repo->hash_algo->hexsz ?
 		p->repo->hash_algo->hexsz : opts->prefix_hex_len;
 	int ret;
+	struct object_id wanted;
 
 	num = p->num_objects;
-	bsearch_pack(opts->prefix, p, &first);
 
-	/*
-	 * At this point, "first" is the location of the lowest object
-	 * with an object name that could match "bin_pfx".  See if we have
-	 * 0, 1 or more objects that actually match(es).
-	 */
-	for (i = first; i < num; i++) {
-		struct object_id oid;
-
-		nth_packed_object_id(&oid, p, i);
-		if (!match_hash(len, opts->prefix->hash, oid.hash))
-			break;
-
-		if (data->request) {
-			struct object_info oi = *data->request;
-			off_t offset = nth_packed_object_offset(p, i);
-
-			ret = packed_object_info(source, p, offset, &oi);
-			if (ret)
-				goto out;
-
-			ret = data->cb(&oid, &oi, data->cb_data);
-			if (ret)
-				goto out;
-		} else {
-			ret = data->cb(&oid, NULL, data->cb_data);
-			if (ret)
-				goto out;
+	for (uint32_t algo = 1; algo < GIT_HASH_NALGOS; algo++) {
+		const struct git_hash_algo *algop = &hash_algos[algo];
+
+		/*
+		 * Skip this algorithm unless it's the desired one or we've
+		 * asked for any algorithm.
+		 */
+		if (opts->prefix->algo != GIT_HASH_UNKNOWN &&
+		    opts->prefix->algo != algo)
+			continue;
+		/*
+		 * Skip this algorithm unless it's the main algorithm or we have
+		 * a compatibility algorithm and it's that algorithm.
+		 */
+		if (algop != p->repo->hash_algo &&
+		    (!p->repo->compat_hash_algo ||
+		     algop != p->repo->compat_hash_algo))
+			continue;
+		if (p->index_version < 3 && algop != p->repo->hash_algo)
+			continue;
+
+		oidcpy(&wanted, opts->prefix);
+		wanted.algo = algo;
+
+		bsearch_pack(&wanted, p, &first);
+
+		/*
+		 * At this point, "first" is the location of the lowest object
+		 * with an object name that could match "bin_pfx".  See if we have
+		 * 0, 1 or more objects that actually match(es).
+		 */
+		for (i = first; i < num; i++) {
+			struct object_id oid;
+
+			if (nth_packed_object_id_algop(&oid, p, i, algop, algop) ||
+			    !match_hash(len, opts->prefix->hash, oid.hash))
+				break;
+
+			if (data->request) {
+				struct object_info oi = *data->request;
+				off_t offset = nth_packed_object_offset_algop(p, i, algop);
+
+				ret = packed_object_info(source, p, offset, &oi);
+				if (ret)
+					goto out;
+
+				ret = data->cb(&oid, &oi, data->cb_data);
+				if (ret)
+					goto out;
+			} else {
+				ret = data->cb(&oid, NULL, data->cb_data);
+				if (ret)
+					goto out;
+			}
 		}
 	}
 
diff --git a/packfile.c b/packfile.c
index 3bfd427c6c..3f3eb27e42 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1919,16 +1919,27 @@ void check_pack_index_ptr(const struct packed_git *p, const void *vptr)
 }
 
 off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)
+{
+	return nth_packed_object_offset_algop(p, n, p->repo->hash_algo);
+}
+
+off_t nth_packed_object_offset_algop(const struct packed_git *p, uint32_t n,
+				     const struct git_hash_algo *algop)
 {
 	const unsigned char *index = p->index_data;
 	const unsigned int hashsz = p->repo->hash_algo->rawsz;
+
+	if (p->index_version < 3 && algop != p->repo->hash_algo)
+		BUG("pack index v%d only stores main object IDs",
+		    p->index_version);
+
 	if (p->index_version == 1) {
 		index += 4 * 256;
 		return ntohl(*((uint32_t *)(index + st_mult(hashsz + 4, n))));
 	} else {
 		uint32_t off;
 		if (p->index_version == 3)
-			n = nth_packed_object_pack_order_algop(p, n, p->repo->hash_algo);
+			n = nth_packed_object_pack_order_algop(p, n, algop);
 		index += st_add(p->crc_offset, st_mult(p->num_objects, 4));
 		off = ntohl(*((uint32_t *)(index + st_mult(4, n))));
 		if (!(off & 0x80000000))
diff --git a/packfile.h b/packfile.h
index 73452b2a43..40760295ee 100644
--- a/packfile.h
+++ b/packfile.h
@@ -303,6 +303,13 @@ int nth_packed_object_id_algop(struct object_id *, struct packed_git *,
  */
 off_t nth_packed_object_offset(const struct packed_git *, uint32_t n);
 
+/*
+ * The same as nth_packed_object_offset, but the nth object is counted in
+ * algop. For indices older than v3, algop must be the main algorithm.
+ */
+off_t nth_packed_object_offset_algop(const struct packed_git *, uint32_t n,
+				     const struct git_hash_algo *algop);
+
 /*
  * Return the index into pack order of the nth object within the specified
  * packfile.  The index must already be opened and it must be a v3 index.
diff --git a/t/t1016-compatObjectFormat.sh b/t/t1016-compatObjectFormat.sh
index 030d6000b5..97a299f088 100755
--- a/t/t1016-compatObjectFormat.sh
+++ b/t/t1016-compatObjectFormat.sh
@@ -269,6 +269,36 @@ do
 		git -C map-repo rev-parse --output-object-format=$(compat_hash $hash) "$oid" >actual &&
 		test_cmp expect actual
 	'
+
+	test_expect_success 'abbreviated compat object IDs are found using pack index v3' '
+		test_when_finished "rm -rf abbrev-repo v3.idx" &&
+		create_compat_repo $hash abbrev-repo &&
+		echo content >abbrev-repo/file &&
+		git -C abbrev-repo add file &&
+		git -C abbrev-repo commit --message A &&
+		compat_oid=$(git -C abbrev-repo rev-parse --output-object-format=$(compat_hash $hash) HEAD) &&
+		abbrev=$(echo $compat_oid | cut -c 1-12) &&
+
+		# A multi-pack-index only stores object IDs in the main
+		# algorithm.
+		GIT_TEST_MULTI_PACK_INDEX=0 git -C abbrev-repo repack -a -d &&
+		pack=$(echo abbrev-repo/.git/objects/pack/pack-*.pack) &&
+		git -C abbrev-repo index-pack --index-version=3 \
+			-o "$(pwd)/v3.idx" "$(pwd)/$pack" &&
+		rm abbrev-repo/.git/objects/loose-object-idx &&
+
+		# A v2 index only has object IDs in the main algorithm.
+		test_must_fail git -C abbrev-repo cat-file -t $abbrev &&
+
+		rm -f "${pack%.pack}.idx" "${pack%.pack}.rev" &&
+		mv v3.idx "${pack%.pack}.idx" &&
+		echo commit >expect &&
+		git -C abbrev-repo cat-file -t $abbrev >actual &&
+		test_cmp expect actual &&
+		echo $compat_oid >expect &&
+		git -C abbrev-repo rev-parse --output-object-format=$(compat_hash $hash) $abbrev >actual &&
+		test_cmp expect actual
+	'
 done
 cd "$base"
 
-- 
2.56.0.215.g47fdf2208c