Re: easy way to demonstrate length of colliding SHA-1 prefixes?

From: Matthew DeVore <matvore@comcast.net>
Date: Dec 3, 2018, 22:30 UTC
Message-ID: <5d63905a-4a52-0724-90f6-a2b0a7ab0f62@comcast.net>
In-Reply-To: <87y398uknn.fsf@evledraar.gmail.com>

On 12/02/2018 05:23 AM, Ævar Arnfjörð Bjarmason wrote:

Show 15 quoted lines

> 
> On Sun, Dec 02 2018, Robert P. J. Day wrote:
> 
>>    as part of an upcoming git class i'm delivering, i thought it would
>> be amusing to demonstrate the maximum length of colliding SHA-1
>> prefixes in a repository (in my case, i use the linux kernel git repo
>> for most of my examples).
>>
>>    is there a way to display the objects in the object database that
>> clash in the longest object name SHA-1 prefix; i mean, short of
>> manually listing all object names, running that through cut and sort
>> and uniq and ... you get the idea.
>>
>>    is there a cute way to do that? thanks.
>

Here is a one-liner to do it. It is Perl line noise, so it's not very cute, thought that is subjective. The output shown below is for the Git project (not Linux) repository as I've currently synced it:

$ git rev-list --objects HEAD | sort | perl -anE 'BEGIN { $prev = ""; $long = "" } $n = $F[0]; for my $i (reverse 1..40) {last if $i < length($long); if (substr($prev, 0, $i) eq substr($n, 0, $i)) {$long = substr($prev, 0, $i); last} } $prev = $n; END {say $long}'

c68038ef

$ git cat-file -t c68038ef

error: short SHA1 c68038ef is ambiguous hint: The candidates are: hint: c68038effe commit 2012-06-01 - vcs-svn: suppress a signed/unsigned comparison warning hint: c68038ef00 blob fatal: Not a valid object name c68038ef

Show 10 quoted lines

> You'll always need to list them all. It's inherently an operation where
> for each SHA-1 you need to search for other ones with that prefix up to
> a given length.
> 
> Perhaps you've missed that you can use --abbrev=N for this, and just
> grep for things that are loger than that N, e.g. for linux.git:
> 
>      git log --oneline --abbrev=10 --pretty=format:%h |
>      grep -E -v '^.{10}$' |
>      perl -pe 's/^(.{10}).*/$1/'

I think the goal was to search all object hashes, not just commits. And git rev-list --objects will do that.