Re: [RFC PATCH 1/4] tree-sha256: hash the contents of a tree with SHA-256

[Junio C Hamano <gitster@pobox.com>]

Scott Chacon <scott@gitbutler.net> writes:

> Add a way to compute a SHA-256 digest of the contents of a tree that
> doesn't depend on the object format, so that it can be put in the
> signed payload. Each blob in the tree, recursively, becomes one record, 
> and the digest is SHA-256 over the records sorted by path:
>
>   <hex sha256 of content> SP <path> NUL

Would three trees, one records a blob with a single word "hello" at
a path as an executable regular file, another records the same blob
at the same path but as a non-executable regular file, and the third
records a symbolic link whose target is "hello", hash to the same
result?  Should they?

> +static int hash_tree(struct repository *r, const struct object_id *oid,
> +		     const char *prefix, struct oid_array *chain,
> +		     struct walk *walk, unsigned char *digest)
> +{
> +	const struct git_hash_algo *sha256 = &hash_algos[GIT_HASH_SHA256];
> +	struct git_hash_ctx outer;
> +	struct collect c = { 0 };
> +	struct pathspec pathspec = { 0 };
> +	struct strbuf value = STRBUF_INIT;
> +	struct tree *tree;
> +	int ret = 0;
> +
> +	tree = repo_parse_tree_indirect(r, oid);
> +	if (!tree)
> +		return error(_("unable to read tree for %s in %s"),
> +			     oid_to_hex(oid), *prefix ? prefix : ".");
> +	if (read_tree(r, tree, &pathspec, collect_entry, &c))
> +		return error(_("unable to read tree %s"),
> +			     oid_to_hex(&tree->object.oid));
> +	QSORT(c.items, c.nr, record_cmp);

I am somewhat torn but moderately against this sorting there.  If
we have two tree objects that would result in the same checkout,
but one is corrupt in such a way that whose entries are not sorted
correctly, we want them to hash to a different value to signal that,
don't we?

> +	git_hash_init(&outer, sha256);
> +	for (size_t i = 0; i < c.nr; i++) {
> +		struct record *rec = &c.items[i];
> +
> +		strbuf_reset(&value);
> +		if (!rec->submodule) {
> +			struct git_hash_ctx ctx;
> +			unsigned char blob_digest[GIT_MAX_RAWSZ];
> +			enum object_type type;
> +			size_t size;
> +			void *data;
> +
> +			data = odb_read_object(r->objects, &rec->oid, &type, &size);
> +			if (!data || type != OBJ_BLOB) {
> +				free(data);
> +				ret = error(_("unable to read blob %s for %s%s"),
> +					    oid_to_hex(&rec->oid), prefix, rec->path);
> +				break;
> +			}
> +			git_hash_init(&ctx, sha256);
> +			git_hash_update(&ctx, data, size);
> +			git_hash_final(blob_digest, &ctx);
> +			free(data);
> +			strbuf_addstr(&value, hash_to_hex_algop(blob_digest, sha256));

This forces us to read the inflated blob contents as a whole in-core
before we hash.  I wonder if we can use the streaming interface like
how archive-{tar,zip}.c uses odb_stream_from_object() to read the
contents in smaller chunks?  Instead of writing the contents out
like they do, we would instead hash the bytes here.