What is the algorithm git uses to find a commit by a partial sha-1 (at least first 4 characters)?

Question

What is the algorithm git uses to find a commit by a partial sha-1 (at least first 4 characters). Are there any implementations of such algorithm out there?

Answer 1

One very simple way (but ineffective) to find the full SHA1 given a partial "01234" one (a "short SHA1")is:

git rev-list --all --objects | grep ^01234

The actual way is:

git rev-parse --verify 01234

It is illustrated in commit 6269b6b

Teach get_describe_name() to pass the disambiguation hint down the callchain to get_short_sha1().

So you can see the algorithm in sha1_name.c#get_short_sha1() function, which will looks in:

• objects: find_short_object_filename(len, hex_pfx, &ds);
• and in pack files: find_short_packed_object(len, bin_pfx, &ds);
  (See "Git Internals - Packfiles")