[PATCH] rev-parse: compute object names in another hash algorithm

[Dimitri John Ledkov <dimitri.ledkov@chainguard.dev>]

"git rev-parse --output-object-format=sha256 HEAD^{tree}" could not
answer in a SHA-1 repository.  And vice-versa.  Without
extensions.compatObjectFormat the option was rejected outright, and with
it the answer was wrong: the extension records a mapping only for objects
written while it is enabled, so for the objects a repository already
contained the lookup missed, repo_oid_to_algop() left the object ID
untouched, and rev-parse printed the SHA-1 name with a zero exit code.

The machinery to convert object contents between algorithms is already
here.  convert_tree_object() and friends rewrite the object IDs a tree,
commit or tag refers to, calling repo_oid_to_algop() for each one, so the
recursion is written; what is missing is a base case.  Give
repo_oid_to_algop() one: on a lookup miss, read the object, convert its
contents, and hash the result.  A blob needs no conversion at all, as its
contents are the same either way, only a rehash.

Names computed this way are remembered during the process execution,
so that a tree that reaches the same subtree by several paths pays for
it once.  These are not stored permamently.  In the future a side-car
cache could be added for these results, or eventual dual-format v3
could be used to lazy compute/convert and store these.

Commits are refused rather than computed.  A commit names its parents, so
converting one converts the entire history behind it; that is a repository
conversion, not an answer about a single object, and recursing over it
here would be bounded only by the length of the history.  A tree holding a
submodule is refused for the same reason, and now says which entry is at
fault instead of reporting an unreadable object.

Since names can now be computed, accept any algorithm git knows rather
than only the configured compatibility one, and check what
repo_oid_to_algop() returns so that a name we cannot produce is an error
instead of the storage name.

On git.git's tree at 9936c1b52a (3089 files, 26MB) this names the tree
in 0.26s, against 0.25s for reading and hashing that content by hand,
so close to the floor for the work involved. On linux.git tree of
1.6GiB it takes 8s to compute.

Initially, I have implemented contrib git-sha256-tree.sh script using
a temporary git repo and perform fast-export/fast-import of a single
commit and its tree.  It is a lot slower due to needless work of
fast-import that is discarded.  However, a contrib script carries less
maintainance and is more portable to existing installations.  If there
is interest, I can publish that implementation as well.  The goal is
to help with interop, and have the ability to record tree names in
either format today; to check again later if and when a given project
switches to sha256 format.

Assisted-by: Claude Opus 5 xHigh
Signed-off-by: Dimitri John Ledkov <dimitri.ledkov@chainguard.dev>
---
 Documentation/git-rev-parse.adoc |  13 +++
 builtin/rev-parse.c              |  23 ++++-
 object-file-convert.c            | 145 +++++++++++++++++++++++++++++--
 object-file-convert.h            |   6 ++
 repository.c                     |   3 +
 repository.h                     |   8 ++
 t/meson.build                    |   1 +
 t/t1018-output-object-format.sh  | 118 +++++++++++++++++++++++++
 8 files changed, 308 insertions(+), 9 deletions(-)
 create mode 100755 t/t1018-output-object-format.sh

diff --git a/Documentation/git-rev-parse.adoc b/Documentation/git-rev-parse.adoc
index 5398691f3f..c18ae9ca81 100644
--- a/Documentation/git-rev-parse.adoc
+++ b/Documentation/git-rev-parse.adoc
@@ -181,6 +181,19 @@ Specifying "sha256" translates if necessary and returns a sha256 oid.
 +
 Specifying "storage" translates if necessary and returns an oid in
 encoded in the storage hash algorithm.
++
+A translation that `extensions.compatObjectFormat` did not record, which is
+every object a repository already contained when that extension was turned
+on, is computed on demand.  Since an object's name in another algorithm is
+defined over the names of the objects it refers to, this reads everything
+reachable from the object, and so costs time proportional to the total size
+of that content.
++
+Commits cannot be named this way.  A commit refers to its parents, so naming
+one would mean converting the whole history behind it, which is a repository
+conversion rather than a question about a single object.  For the same
+reason a tree containing a submodule cannot be named, as its gitlink refers
+to a commit in another repository.
 
 Options for Objects
 ~~~~~~~~~~~~~~~~~~~
diff --git a/builtin/rev-parse.c b/builtin/rev-parse.c
index 43693454d5..7dd06f324e 100644
--- a/builtin/rev-parse.c
+++ b/builtin/rev-parse.c
@@ -876,8 +876,21 @@ int cmd_rev_parse(int argc,
 					flags |= GET_OID_HASH_ANY;
 					output_algo = compat;
 					continue;
+				} else {
+					/*
+					 * Names in another algorithm can be
+					 * computed on demand, so accept any
+					 * algorithm we know rather than only
+					 * the configured compatibility one.
+					 */
+					uint32_t algo = hash_algo_by_name(arg);
+
+					if (algo == GIT_HASH_UNKNOWN)
+						die(_("unsupported object format: %s"), arg);
+					flags |= GET_OID_HASH_ANY;
+					output_algo = &hash_algos[algo];
+					continue;
 				}
-				else die(_("unsupported object format: %s"), arg);
 			}
 			if (opt_with_value(arg, "--short", &arg)) {
 				filter &= ~(DO_FLAGS|DO_NOREV);
@@ -1162,9 +1175,11 @@ int cmd_rev_parse(int argc,
 		}
 		if (!repo_get_oid_with_flags(the_repository, name, &oid,
 					     flags)) {
-			if (output_algo)
-				repo_oid_to_algop(the_repository, &oid,
-						  output_algo, &oid);
+			if (output_algo &&
+			    repo_oid_to_algop(the_repository, &oid,
+					      output_algo, &oid))
+				die(_("cannot express %s as a %s object name"),
+				    name, output_algo->name);
 			if (verify)
 				revs_count++;
 			else
diff --git a/object-file-convert.c b/object-file-convert.c
index 63ee18630b..1f0475b5a0 100644
--- a/object-file-convert.c
+++ b/object-file-convert.c
@@ -10,7 +10,120 @@
 #include "loose.h"
 #include "commit.h"
 #include "gpg-interface.h"
+#include "object-file.h"
 #include "object-file-convert.h"
+#include "odb.h"
+#include "oidmap.h"
+
+struct compat_oid_cache_entry {
+	struct oidmap_entry entry;
+	struct object_id compat_oid;
+};
+
+void repo_clear_compat_oid_cache(struct repository *repo)
+{
+	if (!repo->compat_oid_cache)
+		return;
+	oidmap_clear(repo->compat_oid_cache, 1);
+	FREE_AND_NULL(repo->compat_oid_cache);
+}
+
+static int lookup_computed_oid(struct repository *repo,
+			       const struct object_id *src,
+			       struct object_id *dest)
+{
+	struct compat_oid_cache_entry *found;
+
+	if (!repo->compat_oid_cache)
+		return -1;
+	found = oidmap_get(repo->compat_oid_cache, src);
+	if (!found)
+		return -1;
+	oidcpy(dest, &found->compat_oid);
+	return 0;
+}
+
+static void remember_computed_oid(struct repository *repo,
+				  const struct object_id *src,
+				  const struct object_id *dest)
+{
+	struct compat_oid_cache_entry *added;
+
+	if (!repo->compat_oid_cache) {
+		CALLOC_ARRAY(repo->compat_oid_cache, 1);
+		oidmap_init(repo->compat_oid_cache, 0);
+	}
+	CALLOC_ARRAY(added, 1);
+	oidcpy(&added->entry.oid, src);
+	oidcpy(&added->compat_oid, dest);
+	oidmap_put(repo->compat_oid_cache, added);
+}
+
+/*
+ * Compute the name an object has under another hash algorithm, by converting
+ * its contents and hashing the result.  Objects the contents refer to are
+ * resolved by recursing through repo_oid_to_algop(), so a tree costs a walk
+ * of everything reachable from it.
+ *
+ * Commits are deliberately not handled.  A commit names its parents, so
+ * converting one converts the whole history behind it; that is a repository
+ * conversion rather than something a caller asking for a single object name
+ * should trigger, and recursing over it here would also be unbounded.
+ */
+static int compute_oid_to_algop(struct repository *repo,
+				const struct object_id *src,
+				const struct git_hash_algo *from,
+				const struct git_hash_algo *to,
+				struct object_id *dest)
+{
+	struct strbuf converted = STRBUF_INIT;
+	enum object_type type;
+	size_t size;
+	void *buf;
+	int ret = -1;
+
+	/* We can only read objects that are stored the way the repo stores them. */
+	if (from != repo->hash_algo)
+		return -1;
+
+	buf = odb_read_object(repo->objects, src, &type, &size);
+	if (!buf)
+		return error(_("unable to read %s"), oid_to_hex(src));
+
+	switch (type) {
+	case OBJ_BLOB:
+		/*
+		 * A blob's contents are the same under either algorithm, so
+		 * there is nothing to convert, only to rehash.
+		 */
+		hash_object_file(to, buf, size, OBJ_BLOB, dest);
+		ret = 0;
+		break;
+	case OBJ_TREE:
+	case OBJ_TAG:
+		if (!convert_object_file(repo, &converted, from, to, buf, size,
+					 type, 1)) {
+			hash_object_file(to, converted.buf, converted.len, type,
+					 dest);
+			ret = 0;
+		}
+		break;
+	case OBJ_COMMIT:
+		error(_("cannot compute the %s name of commit %s"),
+		      to->name, oid_to_hex(src));
+		break;
+	default:
+		error(_("unknown type for object %s"), oid_to_hex(src));
+		break;
+	}
+
+	free(buf);
+	strbuf_release(&converted);
+
+	if (!ret)
+		remember_computed_oid(repo, src, dest);
+	return ret;
+}
 
 int repo_oid_to_algop(struct repository *repo, const struct object_id *srcoid,
 		      const struct git_hash_algo *to, struct object_id *dest)
@@ -43,14 +156,25 @@ int repo_oid_to_algop(struct repository *repo, const struct object_id *srcoid,
 		 * let's reload the map to see if the object has appeared.
 		 */
 		repo_read_loose_object_map(repo);
-		if (repo_loose_object_map_oid(repo, src, to, dest))
-			return -1;
+		if (repo_loose_object_map_oid(repo, src, to, dest)) {
+			/*
+			 * The map only covers objects written while
+			 * extensions.compatObjectFormat was in effect, so it
+			 * cannot answer for objects a repository already had.
+			 * Compute the name instead, remembering it so that
+			 * trees sharing a subtree only pay for it once.
+			 */
+			if (!lookup_computed_oid(repo, src, dest))
+				return 0;
+			return compute_oid_to_algop(repo, src, from, to, dest);
+		}
 	}
 	return 0;
 }
 
 static int decode_tree_entry_raw(struct object_id *oid, const char **path,
-				 size_t *len, const struct git_hash_algo *algo,
+				 size_t *len, uint16_t *modep,
+				 const struct git_hash_algo *algo,
 				 const char *buf, unsigned long size)
 {
 	uint16_t mode;
@@ -64,6 +188,7 @@ static int decode_tree_entry_raw(struct object_id *oid, const char **path,
 	if (!*path || !**path)
 		return -1;
 	*len = strlen(*path) + 1;
+	*modep = mode;
 
 	oidread(oid, (const unsigned char *)*path + *len, algo);
 	return 0;
@@ -81,10 +206,20 @@ static int convert_tree_object(struct repository *repo,
 		struct object_id entry_oid, mapped_oid;
 		const char *path = NULL;
 		size_t pathlen;
+		uint16_t mode;
 
-		if (decode_tree_entry_raw(&entry_oid, &path, &pathlen, from, p,
-					  end - p))
+		if (decode_tree_entry_raw(&entry_oid, &path, &pathlen, &mode,
+					  from, p, end - p))
 			return error(_("failed to decode tree entry"));
+		/*
+		 * A gitlink names a commit in the submodule's repository,
+		 * which we cannot read, so say so rather than complaining
+		 * about a missing object.
+		 */
+		if (S_ISGITLINK(mode))
+			return error(_("cannot map submodule entry '%s'; convert "
+				       "commit %s in the submodule repository first"),
+				     path, oid_to_hex(&entry_oid));
 		if (repo_oid_to_algop(repo, &entry_oid, to, &mapped_oid))
 			return error(_("failed to map tree entry for %s"), oid_to_hex(&entry_oid));
 		strbuf_add(out, p, path - p);
diff --git a/object-file-convert.h b/object-file-convert.h
index 9b3cc5e533..af384c362b 100644
--- a/object-file-convert.h
+++ b/object-file-convert.h
@@ -10,6 +10,12 @@ struct strbuf;
 int repo_oid_to_algop(struct repository *repo, const struct object_id *src,
 		      const struct git_hash_algo *to, struct object_id *dest);
 
+/*
+ * Release the object names repo_oid_to_algop() computed on demand.  Called
+ * from repo_clear().
+ */
+void repo_clear_compat_oid_cache(struct repository *repo);
+
 /*
  * Convert an object file from one hash algorithm to another algorithm.
  * Return -1 on failure, 0 on success.
diff --git a/repository.c b/repository.c
index 651b0f6933..16201ec5ea 100644
--- a/repository.c
+++ b/repository.c
@@ -7,6 +7,7 @@
 #include "config.h"
 #include "gettext.h"
 #include "object.h"
+#include "object-file-convert.h"
 #include "lockfile.h"
 #include "path.h"
 #include "read-cache-ll.h"
@@ -386,6 +387,8 @@ void repo_clear(struct repository *repo)
 	odb_free(repo->objects);
 	repo->objects = NULL;
 
+	repo_clear_compat_oid_cache(repo);
+
 	parsed_object_pool_clear(repo->parsed_objects);
 	FREE_AND_NULL(repo->parsed_objects);
 
diff --git a/repository.h b/repository.h
index 3b467a2513..1a89559cd5 100644
--- a/repository.h
+++ b/repository.h
@@ -12,6 +12,7 @@ struct index_state;
 struct lock_file;
 struct pathspec;
 struct object_database;
+struct oidmap;
 struct submodule_cache;
 struct promisor_remote_config;
 struct remote_state;
@@ -167,6 +168,13 @@ struct repository {
 	/* Repository's compatibility hash algorithm. */
 	const struct git_hash_algo *compat_hash_algo;
 
+	/*
+	 * Object names computed in another hash algorithm on demand, keyed by
+	 * the name the object has in this repository.  Owned and populated by
+	 * repo_oid_to_algop().
+	 */
+	struct oidmap *compat_oid_cache;
+
 	/* Repository-specific configuration values. */
 	struct repo_config_values config_values_private_;
 
diff --git a/t/meson.build b/t/meson.build
index a25f37d2f5..bc3e644709 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -172,6 +172,7 @@ integration_tests = [
   't1015-read-index-unmerged.sh',
   't1016-compatObjectFormat.sh',
   't1017-cat-file-remote-object-info.sh',
+  't1018-output-object-format.sh',
   't1020-subdirectory.sh',
   't1022-read-tree-partial-clone.sh',
   't1050-large.sh',
diff --git a/t/t1018-output-object-format.sh b/t/t1018-output-object-format.sh
new file mode 100755
index 0000000000..45ddc510dd
--- /dev/null
+++ b/t/t1018-output-object-format.sh
@@ -0,0 +1,118 @@
+#!/bin/sh
+
+test_description='rev-parse --output-object-format names objects in another algorithm
+
+The repositories here do not set extensions.compatObjectFormat, so nothing
+is recorded in the loose object map and every name has to be computed.
+'
+
+TEST_PASSES_SANITIZE_LEAK=true
+. ./test-lib.sh
+
+# The object formats are pinned rather than left to the default so that
+# these tests behave the same under GIT_TEST_DEFAULT_HASH=sha256.
+test_expect_success 'setup' '
+	for fmt in sha1 sha256
+	do
+		git init --object-format=$fmt ${fmt}repo &&
+		mkdir -p ${fmt}repo/sub &&
+		test_write_lines hello >${fmt}repo/a.txt &&
+		test_write_lines world >${fmt}repo/sub/b.txt &&
+		test_write_lines exec >${fmt}repo/sub/run.sh &&
+		chmod +x ${fmt}repo/sub/run.sh &&
+		test_write_lines dup >${fmt}repo/sub/dup1 &&
+		test_write_lines dup >${fmt}repo/dup2 &&
+		git -C ${fmt}repo add -A &&
+		git -C ${fmt}repo commit -m initial || return 1
+	done
+'
+
+test_expect_success 'name a tree in the other algorithm' '
+	git -C sha256repo rev-parse HEAD^{tree} >expect &&
+	git -C sha1repo rev-parse --output-object-format=sha256 HEAD^{tree} >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'name a subtree given as <rev>:<path>' '
+	git -C sha256repo rev-parse HEAD:sub >expect &&
+	git -C sha1repo rev-parse --output-object-format=sha256 HEAD:sub >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'name a blob in the other algorithm' '
+	git -C sha256repo rev-parse HEAD:a.txt >expect &&
+	git -C sha1repo rev-parse --output-object-format=sha256 HEAD:a.txt >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'name the empty tree' '
+	empty1=$(git -C sha1repo hash-object -t tree /dev/null) &&
+	git -C sha256repo hash-object -t tree /dev/null >expect &&
+	git -C sha1repo rev-parse --output-object-format=sha256 "$empty1" >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'the conversion runs in both directions' '
+	git -C sha1repo rev-parse HEAD^{tree} >expect &&
+	git -C sha256repo rev-parse --output-object-format=sha1 HEAD^{tree} >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'asking for the storage algorithm is a no-op' '
+	git -C sha1repo rev-parse HEAD^{tree} >expect &&
+	git -C sha1repo rev-parse --output-object-format=storage HEAD^{tree} >actual &&
+	test_cmp expect actual &&
+	git -C sha1repo rev-parse --output-object-format=sha1 HEAD^{tree} >actual &&
+	test_cmp expect actual
+'
+
+# Before the names could be computed, a lookup miss left the object ID
+# untouched and rev-parse printed the storage name with a zero exit code.
+test_expect_success 'a name that cannot be computed is an error, not a wrong answer' '
+	test_must_fail git -C sha1repo rev-parse --output-object-format=sha256 \
+		HEAD >actual 2>err &&
+	test_grep "cannot compute the sha256 name of commit" err &&
+	test_grep "cannot express HEAD as a sha256 object name" err &&
+	test_must_be_empty actual
+'
+
+test_expect_success 'a tree containing a submodule reports the submodule' '
+	git init --object-format=sha1 withsub &&
+	gitlink=$(git -C sha1repo rev-parse HEAD) &&
+	(
+		cd withsub &&
+		test_write_lines x >f &&
+		git add f &&
+		git update-index --add --cacheinfo 160000,$gitlink,modpath &&
+		git commit -m withsub
+	) &&
+	test_must_fail git -C withsub rev-parse --output-object-format=sha256 \
+		HEAD^{tree} 2>err &&
+	test_grep "cannot map submodule entry .modpath." err
+'
+
+test_expect_success 'an unknown algorithm is rejected' '
+	test_must_fail git -C sha1repo rev-parse --output-object-format=md5 \
+		HEAD^{tree} 2>err &&
+	test_grep "unsupported object format: md5" err
+'
+
+test_expect_success 'a missing algorithm is rejected' '
+	test_must_fail git -C sha1repo rev-parse --output-object-format \
+		HEAD^{tree} 2>err &&
+	test_grep "no object format specified" err &&
+	test_must_fail git -C sha1repo rev-parse --output-object-format= \
+		HEAD^{tree} 2>err &&
+	test_grep "unsupported object format:" err
+'
+
+test_expect_success 'names computed here match a real conversion' '
+	git -C sha1repo fast-export --full-tree HEAD >stream &&
+	git init --bare --object-format=sha256 converted.git &&
+	git -C converted.git fast-import --quiet <stream &&
+	git -C converted.git rev-parse HEAD^{tree} >expect &&
+	git -C sha1repo rev-parse --output-object-format=sha256 HEAD^{tree} >actual &&
+	test_cmp expect actual
+'
+
+test_done
-- 
2.53.0