Re: [PATCH] abbrev: allow extending beyond 20 chars to disambiguate

["brian m. carlson" <sandals@crustytoothpaste.net>]

[-- Attachment #1: Type: text/plain, Size: 1884 bytes --]

On 2025-08-11 at 15:26:32, Junio C Hamano wrote:
> When you have two or more objects with object names that share more
> than half the length of the hash algorithm in use (e.g. 10 bytes for
> SHA-1 that produces 20-byte/160-bit hash), find_unique_abbrev()
> fails to show disambiguation.

Is this really the case?  If the restriction is due to using
GIT_MAX_RAWSZ instead of GIT_MAX_HEXSZ, then that's 32 vs. 64 in our
modern codebase.

> To see how many leading letters of a given full object name is
> sufficiently unambiguous, the algorithm starts from a initial
> length, guessed based on the estimated number of objects in the
> repository, and see if another object that shares the prefix, and
> keeps extending the abbreviation.  The loop stops at GIT_MAX_RAWSZ,
> which is counted as the number of bytes, since 5b20ace6 (sha1_name:
> unroll len loop in find_unique_abbrev_r(), 2017-10-08); before that
> change, it extended up to GIT_MAX_HEXSZ, which is the correct limit
> because the loop is adding one output letter per iteration.

Nicely explained.

>  * No tests added, since I do not think I want to find two valid
>    objects with their object names sharing the same prefix that is
>    more than 20 letters long.  The current abbreviation code happens
>    to ignore validity of the object and takes invalid objects into
>    account when disambiguating, but I do not want to see a test rely
>    on that.

Yes, even if we could efficiently create such a collision with SHA-1
using the best known attacks on it, that would still be 2^63.5, which
was estimated to cost about USD 10,000 in 2025.  I don't think doing
that just to produce a test would be a good use of the project's (or
really, anyone else's) funds.  Using SHA-256, of course, would require
at least 2^80 work.
-- 
brian m. carlson (they/them)
Toronto, Ontario, CA

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 262 bytes --]