abbrev: auto size the default abbreviation

In fairly early days we somehow decided to abbreviate object names
down to 7-hexdigits, but as projects grow, it is becoming more and
more likely to see such a short object names made in earlier days
and recorded in the log messages no longer unique.

Currently the Linux kernel project needs 11 to 12 hexdigits, while
Git itself needs 10 hexdigits to uniquely identify the objects they
have, while many smaller projects may still be fine with the
original 7-hexdigit default.  One-size does not fit all projects.

Introduce a mechanism, where we estimate the number of objects in
the repository upon the first request to abbreviate an object name
with the default setting and come up with a sane default for the
repository.  Based on the expectation that we would see collision in
a repository with 2^(2N) objects when using object names shortened
to first N bits, use sufficient number of hexdigits to cover the
number of objects in the repository.  Each hexdigit (4-bits) we add
to the shortened name allows us to have four times (2-bits) as many
objects in the repository.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/cache.h b/cache.h
index 5a651b8435ec60b17846302d02c270083ee563fb..0e2a0595e516445e833b24d8a2acd47dc07f5b49 100644 (file)
--- a/cache.h
+++ b/cache.h
@@ -1204,6 +1204,7 @@ struct object_context {
 #define GET_SHA1_TREEISH          020
 #define GET_SHA1_BLOB             040
 #define GET_SHA1_FOLLOW_SYMLINKS 0100
 #define GET_SHA1_TREEISH          020
 #define GET_SHA1_BLOB             040
 #define GET_SHA1_FOLLOW_SYMLINKS 0100

+#define GET_SHA1_AUTOMATIC      0200

 #define GET_SHA1_ONLY_TO_DIE    04000
 
 #define GET_SHA1_DISAMBIGUATORS \
 #define GET_SHA1_ONLY_TO_DIE    04000
 
 #define GET_SHA1_DISAMBIGUATORS \

diff --git a/environment.c b/environment.c
index 44fb107b8a7c8546f6e782cd9d1b97704b494696..6f9d2905634359d2ebf5d8835e7d9f09920968e8 100644 (file)
--- a/environment.c
+++ b/environment.c
@@ -16,7 +16,7 @@ int trust_executable_bit = 1;
 int trust_ctime = 1;
 int check_stat = 1;
 int has_symlinks = 1;
 int trust_ctime = 1;
 int check_stat = 1;
 int has_symlinks = 1;

-int minimum_abbrev = 4, default_abbrev = FALLBACK_DEFAULT_ABBREV;
+int minimum_abbrev = 4, default_abbrev = -1;

 int ignore_case;
 int assume_unchanged;
 int prefer_symlink_refs;
 int ignore_case;
 int assume_unchanged;
 int prefer_symlink_refs;

diff --git a/sha1_name.c b/sha1_name.c
index 3b647fd7cf79127cfa6f684836e387568a87c310..beb7ab588b4da529080301576447762a17e4da11 100644 (file)
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -15,6 +15,7 @@ typedef int (*disambiguate_hint_fn)(const unsigned char *, void *);
 
 struct disambiguate_state {
        int len; /* length of prefix in hex chars */
 
 struct disambiguate_state {
        int len; /* length of prefix in hex chars */

+       unsigned int nrobjects;

        char hex_pfx[GIT_SHA1_HEXSZ + 1];
        unsigned char bin_pfx[GIT_SHA1_RAWSZ];
 
        char hex_pfx[GIT_SHA1_HEXSZ + 1];
        unsigned char bin_pfx[GIT_SHA1_RAWSZ];
 


@@ -118,6 +119,14 @@ static void find_short_object_filename(struct disambiguate_state *ds)
 
                        if (strlen(de->d_name) != 38)
                                continue;
 
                        if (strlen(de->d_name) != 38)
                                continue;

+
+                       /*
+                        * We only look at the one subdirectory, and we assume
+                        * each subdirectory is roughly similar, so each
+                        * object we find probably has 255 other objects in
+                        * the other fan-out directories.
+                        */
+                       ds->nrobjects += 256;

                        if (memcmp(de->d_name, ds->hex_pfx + 2, ds->len - 2))
                                continue;
                        memcpy(hex + 2, de->d_name, 38);
                        if (memcmp(de->d_name, ds->hex_pfx + 2, ds->len - 2))
                                continue;
                        memcpy(hex + 2, de->d_name, 38);


@@ -151,6 +160,7 @@ static void unique_in_pack(struct packed_git *p,
 
        open_pack_index(p);
        num = p->num_objects;
 
        open_pack_index(p);
        num = p->num_objects;

+       ds->nrobjects += num;

        last = num;
        while (first < last) {
                uint32_t mid = (first + last) / 2;
        last = num;
        while (first < last) {
                uint32_t mid = (first + last) / 2;


@@ -380,6 +390,9 @@ static int show_ambiguous_object(const unsigned char *sha1, void *data)
        return 0;
 }
 
        return 0;
 }
 

+/* start from our historical default before the automatic abbreviation */
+static int default_automatic_abbrev = FALLBACK_DEFAULT_ABBREV;
+

 static int get_short_sha1(const char *name, int len, unsigned char *sha1,
                          unsigned flags)
 {
 static int get_short_sha1(const char *name, int len, unsigned char *sha1,
                          unsigned flags)
 {


@@ -426,6 +439,14 @@ static int get_short_sha1(const char *name, int len, unsigned char *sha1,
                for_each_abbrev(ds.hex_pfx, show_ambiguous_object, &ds);
        }
 
                for_each_abbrev(ds.hex_pfx, show_ambiguous_object, &ds);
        }
 

+       if (len < 16 && !status && (flags & GET_SHA1_AUTOMATIC)) {
+               unsigned int expect_collision = 1 << (len * 2);
+               if (ds.nrobjects > expect_collision) {
+                       default_automatic_abbrev = len+1;
+                       return SHORT_NAME_AMBIGUOUS;
+               }
+       }
+

        return status;
 }
 
        return status;
 }
 


@@ -458,14 +479,19 @@ int for_each_abbrev(const char *prefix, each_abbrev_fn fn, void *cb_data)
 int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 {
        int status, exists;
 int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 {
        int status, exists;

+       int flags = GET_SHA1_QUIETLY;

 
 

+       if (len < 0) {
+               flags |= GET_SHA1_AUTOMATIC;
+               len = default_automatic_abbrev;
+       }

        sha1_to_hex_r(hex, sha1);
        if (len == 40 || !len)
                return 40;
        exists = has_sha1_file(sha1);
        while (len < 40) {
                unsigned char sha1_ret[20];
        sha1_to_hex_r(hex, sha1);
        if (len == 40 || !len)
                return 40;
        exists = has_sha1_file(sha1);
        while (len < 40) {
                unsigned char sha1_ret[20];

-               status = get_short_sha1(hex, len, sha1_ret, GET_SHA1_QUIETLY);
+               status = get_short_sha1(hex, len, sha1_ret, flags);

                if (exists
                    ? !status
                    : status == SHORT_NAME_NOT_FOUND) {
                if (exists
                    ? !status
                    : status == SHORT_NAME_NOT_FOUND) {