{"thread":{"id":"25580","subject":"Minimum git commit abbrev length (Was Re: -tip: origin tree build failure (was: [GIT PULL] ext4 update) for 2.6.37)","startedAt":"2010-10-28T17:27:25Z","lastAt":"2011-03-19T16:24:33Z","messageCount":18,"participants":["Ted Ts'o","Linus Torvalds","Brandon Casey","Junio C Hamano","Jeff King","Namhyung Kim","Jay Soffian"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"154642","messageId":"20101028172725.GA6814@thunk.org","threadId":"25580","inReplyTo":"20101028171701.GA18368@elte.hu","subject":"Minimum git commit abbrev length (Was Re: -tip: origin tree build failure (was: [GIT PULL] ext4 update) for 2.6.37)","fromName":"Ted Ts'o","fromEmail":"tytso@mit.edu","sentAt":"2010-10-28T17:27:25Z","receivedAt":"2010-10-28T17:27:25Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Thu, Oct 28, 2010 at 07:17:01PM +0200, Ingo Molnar wrote:\n> > Linus Torvalds <torvalds@linux-foundation.org> wrote:\n> > Yes. Except for the kernel the default git commit abbreviation is\n> > borderline too short. Seven hex-chars can easily alias with a few\n> > more pulls from me: git will not give aliases at the time it gives\n> > a shorthand, but a month or two later the abbreviated commit may\n> > no longer be unique.\n> > \n> > So I suggest using --abbrev=12 or similar.\n> \n> ok. A helper script i use does this:\n> \n>    git log --pretty=format:\"%h: %s\" $@\n> \n> I have added --abbrev=12. Might make sense to lengthen the %h\n> default in upstream Git as well?\n\nMaybe the right thing to do is add a git config option which allows\nfor a configurable minimum git commit abbreviation length?\n\n      \t\t   \t       \t      - Ted\n"},{"id":"154655","messageId":"AANLkTi=8tq1zu_RWjmk5rLOWvP_KPH5UQioQ6wEkc0Ob@mail.gmail.com","threadId":"25580","inReplyTo":"20101028172725.GA6814@thunk.org","subject":"Re: Minimum git commit abbrev length (Was Re: -tip: origin tree build failure (was: [GIT PULL] ext4 update) for 2.6.37)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2010-10-28T18:28:04Z","receivedAt":"2010-10-28T18:28:04Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Thu, Oct 28, 2010 at 10:27 AM, Ted Ts'o <tytso@mit.edu> wrote:\n> On Thu, Oct 28, 2010 at 07:17:01PM +0200, Ingo Molnar wrote:\n>> > Linus Torvalds <torvalds@linux-foundation.org> wrote:\n>> > Yes. Except for the kernel the default git commit abbreviation is\n>> > borderline too short. Seven hex-chars can easily alias with a few\n>> > more pulls from me: git will not give aliases at the time it gives\n>> > a shorthand, but a month or two later the abbreviated commit may\n>> > no longer be unique.\n>> >\n>> > So I suggest using --abbrev=12 or similar.\n>>\n>> ok. A helper script i use does this:\n>>\n>>    git log --pretty=format:\"%h: %s\" $@\n>>\n>> I have added --abbrev=12. Might make sense to lengthen the %h\n>> default in upstream Git as well?\n>\n> Maybe the right thing to do is add a git config option which allows\n> for a configurable minimum git commit abbreviation length?\n\nYes. The default of 7 (I think) comes from fairly early in git\ndevelopment, when seven hex digits was a lot (it covers about 250+\nmillion hash values). Back then I thought that 65k revisions was a lot\n(it was what we were about to hit in BK), and each revision tends to\nbe about 5-10 new objects or so, so a million objects was a big\nnumber.\n\nThese days, the kernel isn't even the largest git project, and even\nthe kernel has about 220k revisions (_much_ bigger than the BK tree\never was) and we are approaching two million objects. At that point,\nseven hex digits is still unique for a lot of them, but when we're\ntalking about just two orders of magnitude difference between number\nof objects and the hash size, there _will_ be hash collisions. It's no\nlonger even close to unrealistic - it happens all the time.\n\nSo I suspect we should both increase the default abbrev that was\nunrealistically small, _and_ add a way for people to set their own\ndefault per-project in the git config file.\n\nMaybe something like the attached (not necessarily well-thought-out or\nwell-tested: I also didn't actually change the default, although I\nsuspect we should up it from 7 to at least 10).\n\n                        Linus\n\n\n builtin/describe.c |    2 +-\n cache.h            |    5 +++--\n config.c           |    8 ++++++++\n environment.c      |    1 +\n 4 files changed, 13 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 43caff2..2d98702 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -20,7 +20,7 @@ static int debug;\t/* Display lots of verbose info */\n static int all;\t/* Any valid ref can be used */\n static int tags;\t/* Allow lightweight tags */\n static int longformat;\n-static int abbrev = DEFAULT_ABBREV;\n+static int abbrev = 7;\t/* NOTE! Not DEFAULT_ABBREV */\n static int max_candidates = 10;\n static int found_names;\n static const char *pattern;\ndiff --git a/cache.h b/cache.h\nindex 33decd9..6c28a81 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -540,6 +540,7 @@ extern int trust_executable_bit;\n extern int trust_ctime;\n extern int quote_path_fully;\n extern int has_symlinks;\n+extern int minimum_abbrev, default_abbrev;\n extern int ignore_case;\n extern int assume_unchanged;\n extern int prefer_symlink_refs;\n@@ -757,8 +758,8 @@ static inline unsigned int hexval(unsigned char c)\n }\n \n /* Convert to/from hex/sha1 representation */\n-#define MINIMUM_ABBREV 4\n-#define DEFAULT_ABBREV 7\n+#define MINIMUM_ABBREV minimum_abbrev\n+#define DEFAULT_ABBREV default_abbrev\n \n struct object_context {\n \tunsigned char tree[20];\ndiff --git a/config.c b/config.c\nindex 4b0a820..474361c 100644\n--- a/config.c\n+++ b/config.c\n@@ -514,6 +514,14 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.abbrev\")) {\n+\t\tint abbrev = git_config_int(var, value);\n+\t\tif (abbrev < minimum_abbrev || abbrev > 40)\n+\t\t\treturn -1;\n+\t\tdefault_abbrev = abbrev;\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.loosecompression\")) {\n \t\tint level = git_config_int(var, value);\n \t\tif (level == -1)\ndiff --git a/environment.c b/environment.c\nindex de5581f..b98003c 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -15,6 +15,7 @@ int user_ident_explicitly_given;\n int trust_executable_bit = 1;\n int trust_ctime = 1;\n int has_symlinks = 1;\n+int minimum_abbrev = 4, default_abbrev = 7;\n int ignore_case;\n int assume_unchanged;\n int prefer_symlink_refs;\n"},{"id":"154662","messageId":"AANLkTin=EeQx4pEPk9ST27kcRpDP65NQvL1c1m8UcRmO@mail.gmail.com","threadId":"25580","inReplyTo":"AANLkTi=8tq1zu_RWjmk5rLOWvP_KPH5UQioQ6wEkc0Ob@mail.gmail.com","subject":"Re: Minimum git commit abbrev length (Was Re: -tip: origin tree build failure (was: [GIT PULL] ext4 update) for 2.6.37)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2010-10-28T18:54:55Z","receivedAt":"2010-10-28T18:54:55Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Thu, Oct 28, 2010 at 11:28 AM, Linus Torvalds\n<torvalds@linux-foundation.org> wrote:\n>\n> Yes. The default of 7 (I think) comes from fairly early in git\n> development, when seven hex digits was a lot (it covers about 250+\n> million hash values). Back then I thought that 65k revisions was a lot\n> (it was what we were about to hit in BK), and each revision tends to\n> be about 5-10 new objects or so, so a million objects was a big\n> number.\n>\n> These days, the kernel isn't even the largest git project, and even\n> the kernel has about 220k revisions (_much_ bigger than the BK tree\n> ever was) and we are approaching two million objects. At that point,\n> seven hex digits is still unique for a lot of them, but when we're\n> talking about just two orders of magnitude difference between number\n> of objects and the hash size, there _will_ be hash collisions. It's no\n> longer even close to unrealistic - it happens all the time.\n\nHmm. In fact, in the kernel, we currently have about twelve thousand\nobjects that end up having collisions in 7 hex digits. Even in the old\nhistorical BK kernel tree, we have over a thousand objects that\ncollide (each bucket in both cases gets just two objects, there are as\nof yet no multiple collisions, which is what you'd expect with a good\nhash). See with\n\n  git rev-list --objects --all | cut -c1-7 | sort | uniq -dc\n\nand in fact git itself has a few collisions (but currently just 44\nobjects ending up sharing 22 SHA1 buckets in 7 digits).\n\nWith each digit, you'd expect the collisions to decrease by a factor\nof 16, and that is indeed exactly what happens. For my current kernel\ntree I get:\n\n - 7 digits: 5823 buckets with duplicates (ie 11646 objects that aren't unique)\n - 8: 406\n - 9: 30\n - 10: 1\n - 11: 0\n\nso 12 hex digits is indeed pretty safe for the kernel, and is likely\nto remain so until the kernel history grows by a factor of 16.\n\n                        Linus\n"},{"id":"154706","messageId":"hLlFGy1hpSTOvcrpvhJQRcAUG1VZkpE60VKEYdmOahsCx20NXHe-iEJGidVS1iD1R38bnTIIrwU@cipher.nrlssc.navy.mil","threadId":"25580","inReplyTo":"AANLkTin=EeQx4pEPk9ST27kcRpDP65NQvL1c1m8UcRmO@mail.gmail.com","subject":"Re: Minimum git commit abbrev length (Was Re: -tip: origin tree build failure","fromName":"Brandon Casey","fromEmail":"casey@nrlssc.navy.mil","sentAt":"2010-10-29T00:14:47Z","receivedAt":"2010-10-29T00:14:47Z","isPatch":false,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"From: Brandon Casey <drafnel@gmail.com>\n\n[dropped linux-kernel list from discussion]\n\nOn 10/28/2010 01:54 PM, Linus Torvalds wrote:\n\n> and in fact git itself has a few collisions (but currently just 44\n> objects ending up sharing 22 SHA1 buckets in 7 digits).\n> \n> With each digit, you'd expect the collisions to decrease by a factor\n> of 16, and that is indeed exactly what happens. For my current kernel\n> tree I get:\n> \n>  - 7 digits: 5823 buckets with duplicates (ie 11646 objects that aren't unique)\n>  - 8: 406\n>  - 9: 30\n>  - 10: 1\n>  - 11: 0\n> \n> so 12 hex digits is indeed pretty safe for the kernel, and is likely\n> to remain so until the kernel history grows by a factor of 16.\n\n\nPerhaps we should calculate DEFAULT_ABBREV dynamically?\n\nSomething like the code down below would use 11 digits for the current\nkernel repo, and would bump up to 12 digits once it hit 4M objects.\n\nIt would use 9 digits for git.git.\n\nThe digits of abbrev are bumped up for each factor of 4 objects.\nThis seems to produce a desirable number for the git.git and\nlinux-2.6.git repos.\n\nestimate_loose_objects() quickly estimates the number of loose\nobjects using Junio's code extracted from gc.c.\n\ndefault_abbrev() estimates the loose objects, counts the number of\npacked objects, and calculates a default abbreviation width.\nSubsequent calls to default_abbrev() return the previously calculated\nvalue.\n\nThis is obviously not a patch meant for inclusion, just an example.\n\n---\n builtin/describe.c |    4 ++-\n cache.h            |    3 +-\n sha1_name.c        |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 66 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 43caff2..551b491 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -20,7 +20,7 @@ static int debug;\t/* Display lots of verbose info */\n static int all;\t/* Any valid ref can be used */\n static int tags;\t/* Allow lightweight tags */\n static int longformat;\n-static int abbrev = DEFAULT_ABBREV;\n+static int abbrev;\n static int max_candidates = 10;\n static int found_names;\n static const char *pattern;\n@@ -386,6 +386,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\tOPT_END(),\n \t};\n \n+\tabbrev = DEFAULT_ABBREV;\n+\n \targc = parse_options(argc, argv, prefix, options, describe_usage, 0);\n \tif (max_candidates < 0)\n \t\tmax_candidates = 0;\ndiff --git a/cache.h b/cache.h\nindex 33decd9..049ef2b 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -758,7 +758,7 @@ static inline unsigned int hexval(unsigned char c)\n \n /* Convert to/from hex/sha1 representation */\n #define MINIMUM_ABBREV 4\n-#define DEFAULT_ABBREV 7\n+#define DEFAULT_ABBREV default_abbrev()\n \n struct object_context {\n \tunsigned char tree[20];\n@@ -766,6 +766,7 @@ struct object_context {\n \tunsigned mode;\n };\n \n+extern int default_abbrev(void);\n extern int get_sha1(const char *str, unsigned char *sha1);\n extern int get_sha1_with_mode_1(const char *str, unsigned char *sha1, unsigned *mode, int gently, const char *prefix);\n static inline int get_sha1_with_mode(const char *str, unsigned char *sha1, unsigned *mode)\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 484081d..8d622fe 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -7,6 +7,67 @@\n #include \"refs.h\"\n #include \"remote.h\"\n \n+static unsigned long estimate_loose_objects(unsigned threshold)\n+{\n+\t/*\n+\t * Quickly estimate how many loose objects there are.\n+\t * Because SHA-1 is evenly distributed, we can check\n+\t * only one and get a reasonable estimate.\n+\t */\n+\tchar path[PATH_MAX];\n+\tconst char *objdir = get_object_directory();\n+\tDIR *dir;\n+\tstruct dirent *ent;\n+\tunsigned long num_loose = 0;\n+\n+\tif (sizeof(path) <= snprintf(path, sizeof(path), \"%s/17\", objdir)) {\n+\t\twarning(\"insanely long object directory %.*s\", 50, objdir);\n+\t\treturn 0;\n+\t}\n+\n+\tdir = opendir(path);\n+\tif (!dir)\n+\t\treturn 0;\n+\n+\tthreshold = (threshold + 255) / 256;\n+\twhile ((ent = readdir(dir)) != NULL) {\n+\t\tif (strspn(ent->d_name, \"0123456789abcdef\") != 38 ||\n+\t\t    ent->d_name[38] != '\\0')\n+\t\t\tcontinue;\n+\t\tnum_loose++;\n+\t\tif (threshold && num_loose > threshold)\n+\t\t\tbreak;\n+\t}\n+\tclosedir(dir);\n+\treturn num_loose * 256;\n+}\n+\n+int default_abbrev(void)\n+{\n+\tstatic int default_abbrev;\n+\tunsigned long count;\n+\tstruct packed_git *p;\n+\n+\tif (default_abbrev)\n+\t\treturn default_abbrev;\n+\n+\tcount = estimate_loose_objects(0);\n+\n+\tprepare_packed_git();\n+\tfor (p = packed_git; p; p = p->next)\n+\t\tif (!open_pack_index(p))\n+\t\t\tcount += p->num_objects;\n+\n+\tdefault_abbrev = 1;\n+\twhile ((count >>= 2))\n+\t\tdefault_abbrev++;\n+\n+\tif (default_abbrev < MINIMUM_ABBREV)\n+\t\tdefault_abbrev = MINIMUM_ABBREV;\n+\n+\treturn default_abbrev;\n+}\n+\n static int find_short_object_filename(int len, const char *name, unsigned char *sha1)\n {\n \tstruct alternate_object_database *alt;\n-- \n1.7.3.1\n"},{"id":"163180","messageId":"7vhbba38mm.fsf_-_@alter.siamese.dyndns.org","threadId":"25580","inReplyTo":"7veiba9ev2.fsf@alter.siamese.dyndns.org","subject":"[PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-10T22:37:05Z","receivedAt":"2011-03-10T22:37:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The caller of this function wants to ensure that the returned string is a\nunique abbreviation of the object name, and at least \"len\" characters\nlong.  When \"len\" is too short to ensure uniqueness with only that many\ncharacters, it returns minimally unique prefix (i.e. if you dropped the\nlast character, there would be two or more objects that share that same\nprefix as their names in the repository).\n\nAn earlier change introduced core.abbrevguard configuration with a\nrealization that a short prefix that is unique today may not stay unique\nforever, as new objects are added to the repository. When \"len\" is shorter\nthan the length necessary to ensure uniqueness today, instead of returning\na string that is only one character longer than the longest ambiguous\nprefix, we want to add that many extra characters (in addition to the \"one\ncharacter that is absolutely needed to make it unique today\") to ensure\nuniqueness for longer time.\n\nThe code however forgot that the function may be called with a \"len\" that\nis long enough.  If an object is uniquely identifiable with only 4 leading\ncharacters today, and if the caller gives 7 as len and the guard is set to\n3, it returned 10 hexdigits, which was 3 characters longer than necessary.\nWe should instead return 7 leading characters in such a case, as that is\nin line with the original intention of using 3 characters more than\nabsolutely necessary to give the disambiguation we find today a better\nchance to survive.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * A three-line patch, with 35 new comment lines and four paragraph commit\n   log message, to fix a stupid thinko that I noticed during a separate\n   discussion with Namhyung-ssi, who wanted to add an option to ensure\n   uniqueness of the truncated commit name in the human-readable blame\n   output.\n\n sha1_name.c |   38 ++++++++++++++++++++++++++++++++++++++\n 1 files changed, 38 insertions(+), 0 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 4a226ad..62950aa 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -191,6 +191,26 @@ static int get_short_sha1(const char *name, int len, unsigned char *sha1,\n \treturn status;\n }\n \n+/*\n+ * The caller wants a unique abbreviation of the full object name in\n+ * \"sha1\" that is at least \"len\" characters long.  A string is a unique\n+ * abbrevation of the full object name when:\n+ *\n+ * (1) there is no other object that shares the returned string as the\n+ *     prefix of its name, if sha1 identifies an existing object; or\n+ *\n+ * (2) there is no object that has the returned string as the prefix\n+ *     of its name, if sha1 does not identify any existing object.\n+ *\n+ * If there exist two or more objects that share the same N characters\n+ * at the beginning of their object names, N+1 leading characters is\n+ * sufficient to make the abbreviation unique today.  As the number of\n+ * objects in the repository grows, however, such an abbreviation\n+ * won't stay unique forever.  core.abbrevguard configuration variable\n+ * can be used to add extra G characters when ensuring the uniqueness\n+ * of the abbreviation, i.e. making N+1+G characters the minimum in\n+ * order to keep the result unique a bit longer, instead of just N+1.\n+ */\n const char *find_unique_abbrev(const unsigned char *sha1, int len)\n {\n \tint status, exists;\n@@ -200,6 +220,24 @@ const char *find_unique_abbrev(const unsigned char *sha1, int len)\n \tmemcpy(hex, sha1_to_hex(sha1), 40);\n \tif (len == 40 || !len)\n \t\treturn hex;\n+\t/*\n+\t * Try to see how short a prefix we can feed to get a unique\n+\t * hit.  When len is sufficiently long, we may find the\n+\t * absolute minimum abbreviation that is a lot shorter than\n+\t * len, so we try from (len - unique_abbrev_extra_length), to\n+\t * avoid the final addition of u_a_e_l to the result getting\n+\t * longer than necessary.  E.g. an object that is ambiguous\n+\t * today with only 3 but is unique with 4 leading characters,\n+\t * it should yield 7 character result if the caller called us\n+\t * with len=7 with u_a_e_l=3 (or shorter), so we start from 4\n+\t * in such a case.  When len is shorter than the minimum\n+\t * required to make the result unique, the loop counts up and\n+\t * finds the absolute minimum (just one character longer than\n+\t * ambiguous truncation) and then we add u_a_e_l to it.\n+\t */\n+\tlen -= unique_abbrev_extra_length;\n+\tif (len <= 0)\n+\t\tlen = 1;\n \twhile (len < 40) {\n \t\tunsigned char sha1_ret[20];\n \t\tstatus = get_short_sha1(hex, len, sha1_ret, 1);\n-- \n1.7.4.1.373.g37629\n"},{"id":"163187","messageId":"AANLkTimH9=OWD4+dPsdYaL2VPdDkTsUG_N3GBf168XqD@mail.gmail.com","threadId":"25580","inReplyTo":"7vhbba38mm.fsf_-_@alter.siamese.dyndns.org","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-03-10T23:07:59Z","receivedAt":"2011-03-10T23:07:59Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Thu, Mar 10, 2011 at 2:37 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>\n> The code however forgot that the function may be called with a \"len\" that\n> is long enough.  If an object is uniquely identifiable with only 4 leading\n> characters today, and if the caller gives 7 as len and the guard is set to\n> 3, it returned 10 hexdigits, which was 3 characters longer than necessary.\n> We should instead return 7 leading characters in such a case, as that is\n> in line with the original intention of using 3 characters more than\n> absolutely necessary to give the disambiguation we find today a better\n> chance to survive.\n\nThe thing is, that just makes the notion of \"abbrevguard\" pointless.\nWhy have it?\n\nWhen you pass in 6 as a len, and that isn't sufficient, it expands it\nto (say) 10. And then you pass in 7 as a length, and now it's\nsufficient, so it keeps it at 7.\n\nThat's just stupid. You gave it a bigger length suggestion, and you\ngot a smaller end result. That's crazy.\n\nHowever, I think the _real_ problem is not whether that behavior is\nreally stupid or not. I think the real problem is that abbrevguard\nreally isn't a well-defined, and you get this kind of crazy semantics.\n\nSo I think the REAL problem is different:\n\n (a) DEFAULT_ABBREV is just too damn small. 7 made sense as a random\nnumber back when we did this, but we're talking over 5 years ago. The\nseven comes from commit 47dd0d595d04e. Back then, a million objects\nwas a really almost inconceivably big number.  Even the BK tree (that\nI was going by as a target) was just 65k revisions for Linux, so with\nmost changes only touching a few files, \"million\" was \"long time in\nthe future\". Now we're close to 2 million.\n\nIt turns out 640kB isn't enough for everybody. For the kernel, we have\nseveral objects that need 10 digits just for uniqeness right NOW.. 12\ndigits is a _somewhat_ reasonable safe value for the forseeable\nfuture. But 11 would be too short. And I don't think the kernel is the\nbiggest repo.\n\n (b) You can't change DEFAULT_ABBREV except with the command line option.\n\n (c) Even there it's unnecessarily hard.  Want to see your commit\nnumbers abbreviated appropriately too? Oh, you have to use\n\"--abbrev=12 --abbrev-commit\". We didn't think the interface through.\n\n (d) some places don't even take the command line option. Grep for\nDEFAULT_ABBREV, and notice how often it's just used as-is.\n\nSo I would suggest ditching 'unique_abbrev_extra_length' entirely. I\ndoubt anybody uses it, and the whole concept is simply badly designed\nwith crazy semantics as per your patch.\n\n                              Linus\n"},{"id":"163192","messageId":"7vzkp21ocm.fsf@alter.siamese.dyndns.org","threadId":"25580","inReplyTo":"AANLkTimH9=OWD4+dPsdYaL2VPdDkTsUG_N3GBf168XqD@mail.gmail.com","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-11T00:40:25Z","receivedAt":"2011-03-11T00:40:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> When you pass in 6 as a len, and that isn't sufficient, it expands it\n> to (say) 10. And then you pass in 7 as a length, and now it's\n> sufficient, so it keeps it at 7.\n\nHmph, that is not the way I wanted to do things.  If len is 6 and the\nresult needs to be 10 to be sufficient, it should still yield 10 if the\nlen you give is 7 (or 8 or 9 or 10).  Of course it would be stupid if you\ndon't do it that way.\n\nI thought the code should work that way already (unless of course there is\nan implementation bug).\n\nHow many characters do we need to name master uniquely today?\n\n    $ ./git -c core.abbrevguard=0 rev-parse --short=1 master\n    83c3c\n\nOk, so there are more than one object with 83c3 and 83c3c is the absolute\nminimum.  We can ask for extra for futureproofing.\n\n    $ ./git -c core.abbrevguard=3 rev-parse --short=1 master\n    83c3c622\n\nAnd we get three extra and the result is 8 characters long.  What if we\ngive len=7 that is still short?\n\n    $ ./git -c core.abbrevguard=3 rev-parse --short=7 master\n    83c3c622\n\nOf course we allow the limit 7 to be busted to keep the futureproofing.\n\n    $ ./git -c core.abbrevguard=3 rev-parse --short=8 master\n    83c3c622\n\nObeying 8 doesn't hurt the futureproofing so the output remains the same.\nBut if you say len=9, you get 9\n\n    $ ./git -c core.abbrevguard=3 rev-parse --short=9 master\n    83c3c6222\n\neven though we know 8 is plenty futureproof, but you get 9 because you\nasked for 9.\n\nWhat am I missing to be called \"just stupid\" and \"crazy\"?\n\nThe earlier code was adding the three extra over what was asked for.  With\nguard=3 and len=7, you would have got 10 for this object that only needs 5\nas absolute minimum today, and giving 8 would have been enough to stay\nunique with room for 3 extra characters to grow.  That is what I was\nfixing.\n\n>  (b) You can't change DEFAULT_ABBREV except with the command line option.\n\nI would agree that would need changing, but I think that is more or less\nan independent issue.\n\nI thought I took your patch to introduce the configuration when I sent the\nabbrevguard as a companion patch, but apparently I didn't.  That would fix\nthe \"grep DEFAULT_ABBREV\" issue.\n"},{"id":"163196","messageId":"AANLkTikPxSspRFQWke4=u55cmmHw8NsyizeH2gL1kD0y@mail.gmail.com","threadId":"25580","inReplyTo":"7vzkp21ocm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-03-11T01:16:25Z","receivedAt":"2011-03-11T01:16:25Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Thu, Mar 10, 2011 at 4:40 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>\n> How many characters do we need to name master uniquely today?\n>\n>    $ ./git -c core.abbrevguard=0 rev-parse --short=1 master\n>    83c3c\n>\n> Ok, so there are more than one object with 83c3 and 83c3c is the absolute\n> minimum.\n\nActually, that's just lucky.\n\nDo this:\n\n  git rev-list --abbrev=4 --abbrev-commit --all --objects | grep '^.........*$'\n\nand you'll see several commits in the git tree that need eight\ncharacters to be unique. The fact that your current 'master' isn't one\nof them, and in fact happens to be one that only needs five, is just\npure luck.\n\nSo even in the (much smaller) git repo, 7 is not a sufficient unique\nminimum even today. Never mind any future guarding.\n\nAnd your argument fails for exactly that reason: yes, for an\n_individual_ SHA1, you may think that \"five characters is sufficient\",\nand when you then use that random number (5) as a basis for forming\nyour \"max 8 character\" logic, it fails miserably for other cases.\n\nNow, if the \"abbrevguard\" was based not one one random data-point, but\non the _whole_ current state of the repository, things would be\ndifferent.  Then it would actually become a \"let's pick a good default\nabbreviation length for this repo\". But that's now that it does. The\nabbrevguard depends on the one particular SHA1 you're looking at, so\nyou can actually be asking for a longer abbreviation, but still get a\n_shorter_ end result than when you asked for a shorter abbreviation.\n\nIOW, try your example thing not just with \"master\", but with two\nextreme commits. For example, try\n\n  git -c core.abbrevguard=2 rev-parse --short=5 83c3c622\n  git -c core.abbrevguard=2 rev-parse --short=4 979f7929\n\nand tell me what you get. I _think_ you should get 7 digits for the\nfirst case, and 8 digits for the second one. Even though you \"asked\"\nfor a longer name in the first case, and you had the same abbrevguard.\n\nSee what I'm saying? I think that's just insane. And it comes exactly\nfrom the fact that abbreviation ends up being a \"local\" thing.\n\n                          Linus\n"},{"id":"163198","messageId":"7vmxl21lwr.fsf@alter.siamese.dyndns.org","threadId":"25580","inReplyTo":"AANLkTikPxSspRFQWke4=u55cmmHw8NsyizeH2gL1kD0y@mail.gmail.com","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-11T01:33:08Z","receivedAt":"2011-03-11T01:33:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> IOW, try your example thing not just with \"master\", but with two\n> extreme commits. For example, try\n>\n>   git -c core.abbrevguard=2 rev-parse --short=5 83c3c622\n>   git -c core.abbrevguard=2 rev-parse --short=4 979f7929\n>\n> and tell me what you get. I _think_ you should get 7 digits for the\n> first case, and 8 digits for the second one. Even though you \"asked\"\n> for a longer name in the first case, and you had the same abbrevguard.\n>\n> See what I'm saying? I think that's just insane.\n\nHmph, why?\n\nThat 979f79 one already have enough other objects with similar names, so\ncompared to 83c3c that doesn't, it is natural that you would need more\ndigits to protect its uniqueness, no?  The result shouldn't be affected by\nthe value of \"short\" as long as it is not long enough, as that is merely\nspecifying \"at least this many letters\".\n\nAnother thing to realize is that without abbrevguard with the code before\nthe configuration was introduced, you would get very similar results.\nWith --short=5, you would get 5 letters for 83c3c622 and with --short=4,\nyou would still need 8 letters for 979f7929.  Because either of these\nvalues are not long enough and it is merely a way to specify \"at least\nthis many letters\".\n\nIf we don't care about uniqueness, we can just truncate at the number of\ncharacters specified by the \"len\" without doing anything else.  That would\ngive us an output of uniform length without the uniqueness guarantee, and\n\"git describe\" output cannot even be fed back to git running in the same\nrepository immediately after it is obtained.  I don't think that is what\nwe want.\n"},{"id":"163199","messageId":"AANLkTinHCsyN4TLBAxzxOn_QAK67VkT1pLgcu7XB0JCD@mail.gmail.com","threadId":"25580","inReplyTo":"7vmxl21lwr.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-03-11T02:21:36Z","receivedAt":"2011-03-11T02:21:36Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Thu, Mar 10, 2011 at 5:33 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>\n> That 979f79 one already have enough other objects with similar names, so\n> compared to 83c3c that doesn't, it is natural that you would need more\n> digits to protect its uniqueness, no?  The result shouldn't be affected by\n> the value of \"short\" as long as it is not long enough, as that is merely\n> specifying \"at least this many letters\"\n\nYes, uniqueness in that sense is sane and has a good definition.\n\nBut that's _not_ the case when you then randomly add extra <n> digits to it.\n\nWhy? Because that <n> is meaningless, because what <n> means depends\non what the base number was. And the base number is different for\ndifferent objects.\n\nThe case of n=0 is special, because it is the \"current state\". But\nwhat does \"n=1\" mean?\n\nLet me make it more explicit by making an extreme example about this.\nIt's extreme just because I'm going to assume that the shortest\nabbreviation is 1 (in reality it's 4) but that doesn't really change\nthe math, it just makes the numbers smaller/easier.\n\nSo let's say that we have a repository with just 100 objects. What\ndoes that mean? In practical terms, it means that it is not impossible\nthat you will have some object that is unique in a single digit (yes,\nit may be a bit unlikely, but it's not unreasonable), while you'll\nhave other objects that need three digits. And most will be unique in\ntwo.\n\nShortening the numbers that way has a _meaning_: the notion of\n\"unique\" is clearly meaningful. Sure, different objects get different\nlengths, but the different lengths have a very real reason for them.\n\nSo then (again, to make the numbers small, and the math simple), let's\nassume abbrevguard=1. What does that MEAN?\n\nAnd I claim that it means something totally _different_ for the\ndifferent objects, and that's the crazy thing. Because now we're\ntalking about possible _future_ objects, but the likely _future_\nuniqueness of \"unique in one digit\" is TOTALLY DIFFERENT from the\nfuture uniqueness of \"unique in three digits\"!\n\nThe single-digit uniqueness is going to be gone _long long_ before the\nthree-digit uniqueness is gone. Adding a single digit to the object\nthat currently happens to need only a single-digit unique id will\n_not_ do a whole lot of future-proofing - if you add another one\nhundred objects, that object may well need three digits to be unique.\nBut if you add a single digit to the one that currently already needed\nthree digits, you're likely to need to add an order of magnitude more\nobjects to need to extend the three digits to four.\n\nSee what I'm trying to say? This is why I think abbrevguard is a\nbroken concept, when it is relative to \"how unique is the object now\".\n\nIf the abbrevguard was related to the maximum number of digits\nrequired for _any_ object in the current repository, it would be\nmeaningful - it would actually be about the _size_ of the current\nrepository, and thus indirectly about the size of a future one. But it\nisn't. It's always relative to the \"local uniqueness\", which is only\nvalid for the *current* state, and has very little to do with future\ngrowth.\n\nNow, to put things in terms of a real repository (\"git\" itself), and\ntwo extreme cases from it:\n\n - commit 1dae(0d38b8119de2b67f87e800c860ed958bbed6) currently unique\nin four digits\n\n - commit 979f7929(51913d75f992f87022b75610303a614f) currently unique\nin eight digits\n\nand think about what \"abbrevguard\" means for those two commits.\n\nLet's pick an abbrev-guard of two digits. For the first one, it means\nthat you use six digits total, and for the second one, you'd use 10\ndigits total.\n\nWhat does that mean for future work? How many objects do we need to\nadd for clashes to start happening?\n\nFor the first commit, it's _almost certain_ that if you double the\nsize of the repository, those six digits will no longer be unique. For\nthe second case? I can pretty much guarantee that EVEN IF you didn't\nhave any abbrev-guard at all, and you doubled the size of the git\nrepository, the thing would still be unique in eight digits.\n\nWhy? It's simply *much*much* less likely that you'll get future\nclashes from new objects in the eight digits. The likelihood of a\nclash with the currently unique 4-digit object is 16^4=65536 times\nhigher than a clash with the currently 8-digit unique shortening.\n\nSo it's senseless to add an equal number of digits to the two objects.\nThey simply don't have the same likelihood of future collisions.\n\nSo what is mathematically the sensible thing? It's actually to extend\nboth objects to the _same_ number of digits. It's _more_ sensible to\nextend the current four-digit number to eight digits, than it is to\nextend the currently unique in eight digits by even a single digit. It\nwould future-proof things a fair amount, exactly because the\nlikelihood of future objects clashing with the two objects are totally\ndifferent.\n\nThat's why I said that it would be sensible to make the abbrevguard be\nrelative to the current worst-case uniqueness. Because THAT actually\nis what is probable. If we currently have a maximum uniqueness\nrequirement of 8 characters, it is _probable_ that by the time the\nproject has grown by a factor of 4, we'll need 9 characters (I think,\nI may have gotten the math wrong).\n\nBut it is somewhat expensive to calculate \"max current uniqueness\", so\nI would suggest ditching the whole notion of \"how many extra numbers\ndo I need for futureproofing\", and go for just setting the absolute\nvalue of DEFAULT_ABBREV.\n\n                               Linus\n"},{"id":"163200","messageId":"7vipvq1hpw.fsf@alter.siamese.dyndns.org","threadId":"25580","inReplyTo":"7vmxl21lwr.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-11T03:03:39Z","receivedAt":"2011-03-11T03:03:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Hmph, why?\n>\n> That 979f79 one already have enough other objects with similar names, so\n> compared to 83c3c that doesn't, it is natural that you would need more\n> digits to protect its uniqueness, no?\n\nYuck, this is showing my total non-understanding of statistics and secure\nhashing.  The example does not mean the next object we will create in\ngit.git project somehow magically is more likely to have 979 prefix than\n83c prefix.  In other words, 979f7929 is much less likely to collide with\nnew objects than 83c3c, simply because it has 4 more digits in it (making\nthe likelyhood of collision with the next one by four orders of magnitude\nin base-16), the likelyhood does not depend on what other objects happen\nto share the same prefix right now, and adding one digits to each would\nmake it 1/16 less likely to have collision relative to the likelyhood with\ntheir current length.\n\nIn any case, if we want to protect abbreviations we generate today from\nfuture collisions, the only sane thing to do is to give sufficiently long\n\"len\" that is computed globally by taking the total number of objects into\naccount.  We should consider the loop in find_unique_abbrev that makes\nsure that prefix truncated to len is unique, and increments until the\nresult becomes unique, merely a last-ditch thing, not contributing to\nfutureproofing.  Even though adding 1 to make it minimally unique as we\nhave always did before the abbrevguard patch has the same \"that 1 extra\nhas different effectiveness for protecting against future collisions,\ndepending on how long the base string is\" issue, we cannot get away by\nadding less than 1 character, and adding more doesn't make it better.\n\nSo let's scrap the abbrevguard thing.  I somehow thought that I already\ntook your \"make DEFAULT_ABBREV tweakable\" patch, but apparently I didn't.\nThat one is the real fix to the issue of futureproofing.\n"},{"id":"163201","messageId":"7vei6e1hg4.fsf@alter.siamese.dyndns.org","threadId":"25580","inReplyTo":"AANLkTinHCsyN4TLBAxzxOn_QAK67VkT1pLgcu7XB0JCD@mail.gmail.com","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-11T03:09:31Z","receivedAt":"2011-03-11T03:09:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> But it is somewhat expensive to calculate \"max current uniqueness\", so\n> I would suggest ditching the whole notion of \"how many extra numbers\n> do I need for futureproofing\", and go for just setting the absolute\n> value of DEFAULT_ABBREV.\n\nThanks; apparently our mails crossed...\n\nI suspect that in a sane repository with set of reasonably packed objects,\nwe can cheaply get a rough estimate of the number of objects to about an\norder of magnitude (e.g. \"likely to have 10k to 100k objects\"), and we\nmight able to come up with a way to automatically raise the default\nlength.\n"},{"id":"163202","messageId":"20110311052235.GA16605@sigill.intra.peff.net","threadId":"25580","inReplyTo":"7vipvq1hpw.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-11T05:22:35Z","receivedAt":"2011-03-11T05:22:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 10, 2011 at 07:03:39PM -0800, Junio C Hamano wrote:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> > Hmph, why?\n> >\n> > That 979f79 one already have enough other objects with similar names, so\n> > compared to 83c3c that doesn't, it is natural that you would need more\n> > digits to protect its uniqueness, no?\n> \n> Yuck, this is showing my total non-understanding of statistics and secure\n> hashing.  The example does not mean the next object we will create in\n> git.git project somehow magically is more likely to have 979 prefix than\n> 83c prefix.  In other words, 979f7929 is much less likely to collide with\n> new objects than 83c3c, simply because it has 4 more digits in it (making\n> the likelyhood of collision with the next one by four orders of magnitude\n> in base-16), the likelyhood does not depend on what other objects happen\n> to share the same prefix right now, and adding one digits to each would\n> make it 1/16 less likely to have collision relative to the likelyhood with\n> their current length.\n\nThis is basically the birthday problem used in hash collision analysis.\nWhich means that if we decide on some acceptable probability of\ncollision, we can figure out the hash-length required to keep the\nprobability of collision below that acceptable level for a repository\nwith objects.\n\nYou can find the formulas here:\n\n  http://en.wikipedia.org/wiki/Birthday_problem\n\nThe closest version to what we want is:\n\n  n(p,d) ~ sqrt(2d * ln(1/(1-p)))\n\nwhere \"n\" is the number of objects in the repository, \"p\" is the\nprobability of a collision, and \"d\" is the size of the distribution\nspace. In our case, for sha1 subset with \"l\" hex characters, it is\n2^(4l). And note that this is an approximation, but it should be close\nenough for our purposes.\n\nWe can arrange the formula into:\n\n  d(n,p) = n^2 / 2 / ln(1/(1-p))\n\nand rearrange our length relationship into:\n\n  l(d) = log2(d) / 4\n\nThen we just pick an acceptable probability of collision. Let's say one\nin a million, 10^-6.\n\nSo for a repository with 175,000 objects (close to git.git), to keep the\nprobability of collision at 10^-6, we get d(n,p) = 1.5e16, or 53 bits,\nor 13 hex characters.\n\nWhich is obviously a lot more than we're doing now. But remember that\nthis is for _any_ collision. So it's not likely to be for one of the few\nnumbers you write down for reference later. So we could probably get by\nwith a much higher collision probability. At one-in-a-thousand, it's 43\nbits or 10 characters.\n\nOr we could just take it all the way down to 50%: we are likely to have\nae collision, but that's probably OK since it's unlikely to be one of\nthe n out of 175,000 that we actually remember and care about. That's 34\nbits, or 8.5 hex characters.\n\nFor the kernel repository, there are 1.8 million objects. So to hit 50%,\nwe're talking about 41 bits or about 10 characters. Which, as a quick\nsanity check, matches what Linus said earlier: they are seeing\ncollisions around the 10-character mark now in the kernel repo.\n\nSo all of this is more or less what Linus has been saying, but with\nnumbers and formulas to back it up.\n\nOne observation I should note are that these probabilities are what we\nwould guess knowing _nothing_ about what is in the repo. That is, if you\ngave me an empty repo and told me you were going to populate it with N\nobjects, these are the probabilities I would calculate. But of course\nthe problem we actually have is that we already have N objects, and we\nexpect to have N+M at some point in the future; we already know which\ncollisions we have in the first N, and we want to future proof against\nthe next M.\n\nSo in theory we could say \"we currently are unique at 8 characters; we\nanticipate 50,000 new objects per year and want to future proof for 4\nyears (so M=200,000). What is the length we need to keep the probability\nof collision for just this _one_ sha1 below some acceptable level?\"\n\nWhich I think is just:\n\n  p(M) = 1 - d^-M\n\nbut when I tried solving for d, I ended up with nonsensical numbers.\nWhich means I'm either wrong or I'm way too sleepy to be doing algebra.\n\nAnyway, point being if we wanted to make a table of reasonable lengths\nfor repos with N objects, it would look like this (for p=0.5):\n\n   N  | bits | hex\n  ------------------\n  1e2 |  13  |  3\n  1e3 |  19  |  5\n  1e4 |  26  |  7\n  1e5 |  33  |  8\n  1e6 |  39  | 10\n  2e6 |  41  | 10\n  5e6 |  44  | 11\n  1e7 |  46  | 12\n\nSo '11' would take the kernel repo to 5 million objects, which is more\nthan doubling. 12 would take it to 10 million. Most smaller projects are\nprobably fine at 8 or 9.\n\nBut you can see that it takes quite a lot of objects to require a bump\nin the hex length, meaning we don't need to re-check it very often. If\nwe really wanted to tweak it automatically, we could probably just set\ncore.defaultAbbrev (or whatever) during git-gc based on the number of\nobjects in the repository. We could do the formula, or even just have a\nprecomputed table (it would be the inverse of the table above, mapping\nthe switch points for hex characters to numbers of objects).\n\n-Peff\n"},{"id":"163204","messageId":"20110311053312.GC16605@sigill.intra.peff.net","threadId":"25580","inReplyTo":"20110311052235.GA16605@sigill.intra.peff.net","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-11T05:33:12Z","receivedAt":"2011-03-11T05:33:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 11, 2011 at 12:22:35AM -0500, Jeff King wrote:\n\n> This is basically the birthday problem used in hash collision analysis.\n> Which means that if we decide on some acceptable probability of\n> collision, we can figure out the hash-length required to keep the\n> probability of collision below that acceptable level for a repository\n> with objects.\n\nUrgh, that was supposed to be \"...for a repository with _n_ objects\".\nBut hopefully that became clear as you read on.\n\n-Peff\n"},{"id":"163251","messageId":"7vvczpff89.fsf@alter.siamese.dyndns.org","threadId":"25580","inReplyTo":"7vipvq1hpw.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-11T22:45:58Z","receivedAt":"2011-03-11T22:45:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> So let's scrap the abbrevguard thing.  I somehow thought that I already\n> took your \"make DEFAULT_ABBREV tweakable\" patch, but apparently I didn't.\n> That one is the real fix to the issue of futureproofing.\n\nIn return for a free education last night, I now owe you your patch from\nOctober last year, resurrected from the list archive, and here it is.\n\nWith a forged sign-off from you, as I know that everything you write is\nsupposed to be open source.\n\n - I do not think making minimum configurable is worth it, but I left it in\n   (there is no UI to tweak it anyway).\n\n - I somewhat tweaked \"describe\" and \"describe --abbrev\" implementation.\n   OPT__ABBREV() uses DEFAULT_ABBREV in its callback, so we need to read\n   from the configuration before calling parse_options().  As it won't\n   make any sense to call \"git describe\" outside repository where you\n   cannot get to your configuration, I think it is safe to add a call to\n   git_config() in this codepath. Other users of OPT__ABBREV() may need to\n   be audited.\n\nBy the way, I've already reverted the abbrevguard thing away.\n\n-- >8 --\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nDate: Thu, 28 Oct 2010 11:28:04 -0700\nSubject: [PATCH] Make the default abbrev length configurable\n\nThe default of 7 comes from fairly early in git development, when\nseven hex digits was a lot (it covers about 250+ million hash\nvalues). Back then I thought that 65k revisions was a lot (it was what\nwe were about to hit in BK), and each revision tends to be about 5-10\nnew objects or so, so a million objects was a big number.\n\nThese days, the kernel isn't even the largest git project, and even\nthe kernel has about 220k revisions (_much_ bigger than the BK tree\never was) and we are approaching two million objects. At that point,\nseven hex digits is still unique for a lot of them, but when we're\ntalking about just two orders of magnitude difference between number\nof objects and the hash size, there _will_ be collisions in truncated\nhash values. It's no longer even close to unrealistic - it happens all\nthe time.\n\nWe should both increase the default abbrev that was unrealistically\nsmall, _and_ add a way for people to set their own default per-project\nin the git config file.\n\nThis is the first step to first make it configurable; the default of 7\nis not raised yet.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n Documentation/config.txt |    6 ++++++\n builtin/describe.c       |    6 +++++-\n cache.h                  |    5 +++--\n config.c                 |    8 ++++++++\n environment.c            |    1 +\n 5 files changed, 23 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex c5e1835..30afde9 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -567,6 +567,12 @@ core.sparseCheckout::\n \tEnable \"sparse checkout\" feature. See section \"Sparse checkout\" in\n \tlinkgit:git-read-tree[1] for more information.\n \n+core.abbrevLength::\n+\tSet the length object names are abbreviated to.  If unspecified,\n+\tmany commands abbreviate to 7 hexdigits, which may not be enough\n+\tfor abbreviated object names to stay unique for sufficiently long\n+\ttime.\n+\n add.ignore-errors::\n add.ignoreErrors::\n \tTells 'git add' to continue adding files when some files cannot be\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 342129f..9591596 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -21,7 +21,7 @@ static int debug;\t/* Display lots of verbose info */\n static int all;\t/* Any valid ref can be used */\n static int tags;\t/* Allow lightweight tags */\n static int longformat;\n-static int abbrev = DEFAULT_ABBREV;\n+static int abbrev = -1; /* unspecified */\n static int max_candidates = 10;\n static struct hash_table names;\n static int have_util;\n@@ -420,7 +420,11 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\tOPT_END(),\n \t};\n \n+\tgit_config(git_default_config, NULL);\n \targc = parse_options(argc, argv, prefix, options, describe_usage, 0);\n+\tif (abbrev < 0)\n+\t\tabbrev = DEFAULT_ABBREV;\n+\n \tif (max_candidates < 0)\n \t\tmax_candidates = 0;\n \telse if (max_candidates > MAX_TAGS)\ndiff --git a/cache.h b/cache.h\nindex d83d68c..8d73d88 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -540,6 +540,7 @@ extern int trust_executable_bit;\n extern int trust_ctime;\n extern int quote_path_fully;\n extern int has_symlinks;\n+extern int minimum_abbrev, default_abbrev;\n extern int ignore_case;\n extern int assume_unchanged;\n extern int prefer_symlink_refs;\n@@ -758,8 +759,8 @@ static inline unsigned int hexval(unsigned char c)\n }\n \n /* Convert to/from hex/sha1 representation */\n-#define MINIMUM_ABBREV 4\n-#define DEFAULT_ABBREV 7\n+#define MINIMUM_ABBREV minimum_abbrev\n+#define DEFAULT_ABBREV default_abbrev\n \n struct object_context {\n \tunsigned char tree[20];\ndiff --git a/config.c b/config.c\nindex 625e051..e8a6e56 100644\n--- a/config.c\n+++ b/config.c\n@@ -531,6 +531,14 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.abbrevlength\")) {\n+\t\tint abbrev = git_config_int(var, value);\n+\t\tif (abbrev < minimum_abbrev || abbrev > 40)\n+\t\t\treturn -1;\n+\t\tdefault_abbrev = abbrev;\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.loosecompression\")) {\n \t\tint level = git_config_int(var, value);\n \t\tif (level == -1)\ndiff --git a/environment.c b/environment.c\nindex 9564475..f2d90a8 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -15,6 +15,7 @@ int user_ident_explicitly_given;\n int trust_executable_bit = 1;\n int trust_ctime = 1;\n int has_symlinks = 1;\n+int minimum_abbrev = 4, default_abbrev = 7;\n int ignore_case;\n int assume_unchanged;\n int prefer_symlink_refs;\n-- \n1.7.4.1.404.g62d316\n"},{"id":"163286","messageId":"1300023026.1450.1.camel@leonhard","threadId":"25580","inReplyTo":"7vvczpff89.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Namhyung Kim","fromEmail":"namhyung@gmail.com","sentAt":"2011-03-13T13:30:26Z","receivedAt":"2011-03-13T13:30:26Z","isPatch":true,"sender":{"key":"namhyung@gmail.com","avatar":"https://avatars.githubusercontent.com/u/48503?v=4"},"body":"2011-03-11 (금), 14:45 -0800, Junio C Hamano:\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> > So let's scrap the abbrevguard thing.  I somehow thought that I already\n> > took your \"make DEFAULT_ABBREV tweakable\" patch, but apparently I didn't.\n> > That one is the real fix to the issue of futureproofing.\n> \n> In return for a free education last night, I now owe you your patch from\n> October last year, resurrected from the list archive, and here it is.\n> \n> With a forged sign-off from you, as I know that everything you write is\n> supposed to be open source.\n> \n>  - I do not think making minimum configurable is worth it, but I left it in\n>    (there is no UI to tweak it anyway).\n> \n>  - I somewhat tweaked \"describe\" and \"describe --abbrev\" implementation.\n>    OPT__ABBREV() uses DEFAULT_ABBREV in its callback, so we need to read\n>    from the configuration before calling parse_options().  As it won't\n>    make any sense to call \"git describe\" outside repository where you\n>    cannot get to your configuration, I think it is safe to add a call to\n>    git_config() in this codepath. Other users of OPT__ABBREV() may need to\n>    be audited.\n> \n> By the way, I've already reverted the abbrevguard thing away.\n> \n> -- >8 --\n> From: Linus Torvalds <torvalds@linux-foundation.org>\n> Date: Thu, 28 Oct 2010 11:28:04 -0700\n> Subject: [PATCH] Make the default abbrev length configurable\n> \n> The default of 7 comes from fairly early in git development, when\n> seven hex digits was a lot (it covers about 250+ million hash\n> values). Back then I thought that 65k revisions was a lot (it was what\n> we were about to hit in BK), and each revision tends to be about 5-10\n> new objects or so, so a million objects was a big number.\n> \n> These days, the kernel isn't even the largest git project, and even\n> the kernel has about 220k revisions (_much_ bigger than the BK tree\n> ever was) and we are approaching two million objects. At that point,\n> seven hex digits is still unique for a lot of them, but when we're\n> talking about just two orders of magnitude difference between number\n> of objects and the hash size, there _will_ be collisions in truncated\n> hash values. It's no longer even close to unrealistic - it happens all\n> the time.\n> \n> We should both increase the default abbrev that was unrealistically\n> small, _and_ add a way for people to set their own default per-project\n> in the git config file.\n> \n> This is the first step to first make it configurable; the default of 7\n> is not raised yet.\n> \n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> ---\n\nReviewed-by: Namhyung Kim <namhyung@gmail.com>\n\nThanks.\n\n\n-- \nRegards,\nNamhyung Kim\n"},{"id":"163697","messageId":"AANLkTimH6ZKkTZ0MiJWzHpZywSy6Hk3caLQ5S+rE0uqg@mail.gmail.com","threadId":"25580","inReplyTo":"7vvczpff89.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Jay Soffian","fromEmail":"jaysoffian@gmail.com","sentAt":"2011-03-19T01:22:30Z","receivedAt":"2011-03-19T01:22:30Z","isPatch":true,"sender":{"key":"jaysoffian@gmail.com","avatar":"https://avatars.githubusercontent.com/u/155970?v=4"},"body":"On Fri, Mar 11, 2011 at 5:45 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> +core.abbrevLength::\n> +       Set the length object names are abbreviated to.  If unspecified,\n> +       many commands abbreviate to 7 hexdigits, which may not be enough\n> +       for abbreviated object names to stay unique for sufficiently long\n> +       time.\n> +\n\nIsn't this the minimum length though? i.e. a longer length is used as\nneeded for uniqueness. If so, at least the description is misleading,\nand I'd argue the option name too. Perhaps core.abbrevMinLength?\n\nj.\n"},{"id":"163761","messageId":"1300551873.1462.8.camel@leonhard","threadId":"25580","inReplyTo":"AANLkTimH6ZKkTZ0MiJWzHpZywSy6Hk3caLQ5S+rE0uqg@mail.gmail.com","subject":"Re: [PATCH] find_unique_abbrev(): honor caller-supplied \"len\" better","fromName":"Namhyung Kim","fromEmail":"namhyung@gmail.com","sentAt":"2011-03-19T16:24:33Z","receivedAt":"2011-03-19T16:24:33Z","isPatch":true,"sender":{"key":"namhyung@gmail.com","avatar":"https://avatars.githubusercontent.com/u/48503?v=4"},"body":"2011-03-18 (금), 21:22 -0400, Jay Soffian:\n> On Fri, Mar 11, 2011 at 5:45 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> > +core.abbrevLength::\n> > +       Set the length object names are abbreviated to.  If unspecified,\n> > +       many commands abbreviate to 7 hexdigits, which may not be enough\n> > +       for abbreviated object names to stay unique for sufficiently long\n> > +       time.\n> > +\n> \n> Isn't this the minimum length though? i.e. a longer length is used as\n> needed for uniqueness. If so, at least the description is misleading,\n> and I'd argue the option name too. Perhaps core.abbrevMinLength?\n> \n> j.\n\nIt could confuse what it points is the default length or the minimum.\nI'd like to suggest core.defaultAbbrev or core.abbrevDefault.\n\n\n-- \nRegards,\nNamhyung Kim\n"}]}