{"thread":{"id":"31378","subject":"Funny 'git describe --contains' output","startedAt":"2012-08-29T04:48:40Z","lastAt":"2012-08-30T15:59:52Z","messageCount":19,"participants":["Greg KH","Junio C Hamano","Jeff King","Philip Oakley"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"198023","messageId":"20120829044840.GA25869@kroah.com","threadId":"31378","inReplyTo":null,"subject":"Funny 'git describe --contains' output","fromName":"Greg KH","fromEmail":"gregkh@linuxfoundation.org","sentAt":"2012-08-29T04:48:40Z","receivedAt":"2012-08-29T04:48:40Z","isPatch":false,"sender":{"key":"gregkh@linuxfoundation.org","avatar":"https://gravatar.com/avatar/e6d9136f6e3bdcb59f0e5fd15565f382da42523d273824958b9e23e73cf38e04?d=mp&s=160"},"body":"Hi,\n\nIn the Linux kernel tree, commit 0136db586c028f71e7cc21cc183064ff0d5919\nis a bit \"odd\".\n\nIf I go to look to see what release it was in, I normally do:\n\t$ git describe --contains 0136db586c028f71e7cc21cc183064ff0d5919\n\tv3.6-rc1~59^2~56^2~76\n\nHowever, it really showed up first in the 3.5-rc1 kernel release, as can\nbe seen by doing the following:\n\t$ git tag --contains 0136db586c028f71e7cc21cc183064ff0d5919\n\tv3.5\n\tv3.5-rc1\n\tv3.5-rc2\n\tv3.5-rc3\n\tv3.5-rc4\n\tv3.5-rc5\n\tv3.5-rc6\n\tv3.5-rc7\n\tv3.6-rc1\n\tv3.6-rc2\n\tv3.6-rc3\n\nThis commit ended up coming into Linus's tree in two different places,\nboth in 3.5-rc1 and in 3.6-rc1, through different merge requests, so it\nseems to be tricky to figure out when it \"first\" went in.\n\nAsking Linus about this, he tried the following:\n\n\t$ git name-rev --tags 0136db586c028f71e7cc21cc183064ff0d5919\n\t0136db586c028f71e7cc21cc183064ff0d5919 tags/v3.6-rc1~59^2~56^2~76\n\t$ git rev-list 0136db586c028f71e7cc21cc183064ff0d5919..v3.5-rc1 | wc\n\t  11415   11415  468015\n\t$ git rev-list 0136db586c028f71e7cc21cc183064ff0d5919..v3.4-rc1 | wc\n\t  0       0       0\n\t$ git rev-list 0136db586c028f71e7cc21cc183064ff0d5919..v3.6-rc1 | wc\n\t  22279   22279  913439\n\nwhich shows that there are \"less\" commits to get from this commit to\nv3.5-rc1 instead of v3.6-rc1, so something odd is going on here.\n\nAny ideas?\n\nI can reproduce this right now with git version 1.7.12.116.g31e0100\n\nthanks,\n\ngreg k-h\n"},{"id":"198024","messageId":"7vr4qqxmt8.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"20120829044840.GA25869@kroah.com","subject":"Re: Funny 'git describe --contains' output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T05:57:23Z","receivedAt":"2012-08-29T05:57:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Greg KH <gregkh@linuxfoundation.org> writes:\n\n> In the Linux kernel tree, commit 0136db586c028f71e7cc21cc183064ff0d5919\n> is a bit \"odd\".\n>\n> If I go to look to see what release it was in, I normally do:\n> \t$ git describe --contains 0136db586c028f71e7cc21cc183064ff0d5919\n> \tv3.6-rc1~59^2~56^2~76\n> ...\n> Any ideas?\n\nThat is 59 + 1 + 56 + 1 + 76 = 193 steps away from the tag v3.6-rc1.\n\n$ git name-rev --refs=refs/tags/v3.5-rc1 0136db58\n0136db58 tags/v3.5-rc1~83^2~81^2~76\n\nwhich is 83 + 1 + 81 + 1 + 76 = 242 steps away from that tag.\n\nSo it _is_ odd that the newly tagged tip merged a branch that had\nsmaller development since it merged the commit, but name-rev seems\nto be measuring the steps it takes from the tags to reach the commit\nand giving us the one that gives the shortest path correctly.\n\nObviously, that is not the same as \"which tag is the oldest one\namong the ones that can reach this commit?\"\n"},{"id":"198030","messageId":"7vharmxkzl.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"7vr4qqxmt8.fsf@alter.siamese.dyndns.org","subject":"Re: Funny 'git describe --contains' output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T06:36:46Z","receivedAt":"2012-08-29T06:36:46Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Greg KH <gregkh@linuxfoundation.org> writes:\n>\n>> In the Linux kernel tree, commit 0136db586c028f71e7cc21cc183064ff0d5919\n>> is a bit \"odd\".\n>>\n>> If I go to look to see what release it was in, I normally do:\n>> \t$ git describe --contains 0136db586c028f71e7cc21cc183064ff0d5919\n>> \tv3.6-rc1~59^2~56^2~76\n>> ...\n>> Any ideas?\n>\n> That is 59 + 1 + 56 + 1 + 76 = 193 steps away from the tag v3.6-rc1.\n>\n> $ git name-rev --refs=refs/tags/v3.5-rc1 0136db58\n> 0136db58 tags/v3.5-rc1~83^2~81^2~76\n>\n> which is 83 + 1 + 81 + 1 + 76 = 242 steps away from that tag.\n>\n> So it _is_ odd that the newly tagged tip merged a branch that had\n> smaller development since it merged the commit, but name-rev seems\n> to be measuring the steps it takes from the tags to reach the commit\n> and giving us the one that gives the shortest path correctly.\n>\n> Obviously, that is not the same as \"which tag is the oldest one\n> among the ones that can reach this commit?\"\n\nAs is usual for what I say, the above is an explanation of what we\nare seeing, not necessarily a justification.\n\nGiven a history of this shape:\n\n        o---o---o---o TONS!!!\n                     \\\n ---o--o--o--o--o--Y--o---o---Z\n     \\   /               /\n      \\ /               /\n       X---------------o\n\nwhere Y is v3.5-rc1 and Z is v3.6-rc1, \"name-rev X\" measures the\ndistance of the shortest path between Z and X (Z^^2^ = 3 steps away)\nand between Y and X (Y~3^2 = 4 steps away), and uses the tag with\nthe shortest path.\n\nBut in order to answer \"which is the earlier tag that merges X\",\nwhat \"name-rev\" measures is not very interesting.\n\nWhat we want to see is the tag whose \"weight\" (imagine these commits\nare beads on strings, and you hold the tag between your fingers and\nlift it, pulling all the commits behind it on the history) is the\nsmallest and reaches the commit X in question.  The distance on the\nshortest path to X totally ignores tons of merges that went into the\nmainline between Y and Z.  That is what makes name-rev not useful\nfor this purpose.\n\nThat \"weight\" is what Linus's \"rev-list | wc -l\" showed, but it is\nfairly expensive to compute.  We do have a code that computes such\nweight in the history bisection code (it computes this exact weight\nfor each and every commit that is still suspect, and picks the one\nthat is half-way).  We know how to compute it, but I suspect that\napplying that code naively to name-rev would make it unusably slow.\n"},{"id":"198053","messageId":"20120829181731.GD3906@kroah.com","threadId":"31378","inReplyTo":"7vharmxkzl.fsf@alter.siamese.dyndns.org","subject":"Re: Funny 'git describe --contains' output","fromName":"Greg KH","fromEmail":"gregkh@linuxfoundation.org","sentAt":"2012-08-29T18:17:32Z","receivedAt":"2012-08-29T18:17:32Z","isPatch":false,"sender":{"key":"gregkh@linuxfoundation.org","avatar":"https://gravatar.com/avatar/e6d9136f6e3bdcb59f0e5fd15565f382da42523d273824958b9e23e73cf38e04?d=mp&s=160"},"body":"On Tue, Aug 28, 2012 at 11:36:46PM -0700, Junio C Hamano wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> > Greg KH <gregkh@linuxfoundation.org> writes:\n> >\n> >> In the Linux kernel tree, commit 0136db586c028f71e7cc21cc183064ff0d5919\n> >> is a bit \"odd\".\n> >>\n> >> If I go to look to see what release it was in, I normally do:\n> >> \t$ git describe --contains 0136db586c028f71e7cc21cc183064ff0d5919\n> >> \tv3.6-rc1~59^2~56^2~76\n> >> ...\n> >> Any ideas?\n> >\n> > That is 59 + 1 + 56 + 1 + 76 = 193 steps away from the tag v3.6-rc1.\n> >\n> > $ git name-rev --refs=refs/tags/v3.5-rc1 0136db58\n> > 0136db58 tags/v3.5-rc1~83^2~81^2~76\n> >\n> > which is 83 + 1 + 81 + 1 + 76 = 242 steps away from that tag.\n> >\n> > So it _is_ odd that the newly tagged tip merged a branch that had\n> > smaller development since it merged the commit, but name-rev seems\n> > to be measuring the steps it takes from the tags to reach the commit\n> > and giving us the one that gives the shortest path correctly.\n> >\n> > Obviously, that is not the same as \"which tag is the oldest one\n> > among the ones that can reach this commit?\"\n> \n> As is usual for what I say, the above is an explanation of what we\n> are seeing, not necessarily a justification.\n> \n> Given a history of this shape:\n> \n>         o---o---o---o TONS!!!\n>                      \\\n>  ---o--o--o--o--o--Y--o---o---Z\n>      \\   /               /\n>       \\ /               /\n>        X---------------o\n> \n> where Y is v3.5-rc1 and Z is v3.6-rc1, \"name-rev X\" measures the\n> distance of the shortest path between Z and X (Z^^2^ = 3 steps away)\n> and between Y and X (Y~3^2 = 4 steps away), and uses the tag with\n> the shortest path.\n> \n> But in order to answer \"which is the earlier tag that merges X\",\n> what \"name-rev\" measures is not very interesting.\n> \n> What we want to see is the tag whose \"weight\" (imagine these commits\n> are beads on strings, and you hold the tag between your fingers and\n> lift it, pulling all the commits behind it on the history) is the\n> smallest and reaches the commit X in question.  The distance on the\n> shortest path to X totally ignores tons of merges that went into the\n> mainline between Y and Z.  That is what makes name-rev not useful\n> for this purpose.\n> \n> That \"weight\" is what Linus's \"rev-list | wc -l\" showed, but it is\n> fairly expensive to compute.  We do have a code that computes such\n> weight in the history bisection code (it computes this exact weight\n> for each and every commit that is still suspect, and picks the one\n> that is half-way).  We know how to compute it, but I suspect that\n> applying that code naively to name-rev would make it unusably slow.\n\nThanks for the full explaination.  \"Normally\" this never is an issue for\nme, as this is the first time, in the history of Linux stable kernel\nreleases, that I've ever noticed this.  And I agree, it's probably not\nsomething that can easily be resolved in git, given how it's calculated.\n\nthanks,\n\ngreg k-h\n"},{"id":"198067","messageId":"1346275044-10171-1-git-send-email-gitster@pobox.com","threadId":"31378","inReplyTo":"7vharmxkzl.fsf@alter.siamese.dyndns.org","subject":"[PATCH 0/3] \"git name-rev --weight\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T21:17:21Z","receivedAt":"2012-08-29T21:17:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"So here is an attempt to teach \"name-rev\" a mode that tries to base\nits name on oldest tag that can reach the commit.  It needs the\nreset_revision_walk() call recently added to the revision traversal\nAPI, and applies to bcc0a3e (v1.7.11-rc0~111^2~2) or newer.\n\nNote that this can benefit from caching, as the \"weight\" of the tag\n(rather, the commit that is tagged) will never change once a history\nis made, but that part is left as an exercise to the reader.\n\nIt correctly names 0136db586c in the kernel history as based on\nv3.5-rc1 as tags/v3.5-rc1~83^2~81^2~76, not on v3.6-rc1, as we saw\non the list recently.\n\nOnce it is verified to operate correctly and updated to perform\nproperly, we can start passing --weight when \"describe --contains\"\nruns the command.\n\nJunio C Hamano (3):\n  name-rev: lose unnecessary typedef\n  name_rev: clarify when a new tip-name is assigned to a commit\n  name-rev: --weight option (WIP)\n\n builtin/name-rev.c | 142 ++++++++++++++++++++++++++++++++++++++++++++---------\n 1 file changed, 120 insertions(+), 22 deletions(-)\n\n-- \n1.7.12.285.ga3d5fc0\n"},{"id":"198065","messageId":"1346275044-10171-2-git-send-email-gitster@pobox.com","threadId":"31378","inReplyTo":"1346275044-10171-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/3] name-rev: lose unnecessary typedef","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T21:17:22Z","receivedAt":"2012-08-29T21:17:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Just spell it \"struct rev_name\"; it makes it more clear what is\ngoing on.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/name-rev.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 1b37458..8af2cfa 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -7,11 +7,11 @@\n \n #define CUTOFF_DATE_SLOP 86400 /* one day */\n \n-typedef struct rev_name {\n+struct rev_name {\n \tconst char *tip_name;\n \tint generation;\n \tint distance;\n-} rev_name;\n+};\n \n static long cutoff = LONG_MAX;\n \n@@ -43,7 +43,7 @@ static void name_rev(struct commit *commit,\n \t}\n \n \tif (name == NULL) {\n-\t\tname = xmalloc(sizeof(rev_name));\n+\t\tname = xmalloc(sizeof(struct rev_name));\n \t\tcommit->util = name;\n \t\tgoto copy_data;\n \t} else if (name->distance > distance) {\n-- \n1.7.12.285.ga3d5fc0\n"},{"id":"198064","messageId":"1346275044-10171-3-git-send-email-gitster@pobox.com","threadId":"31378","inReplyTo":"1346275044-10171-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/3] name_rev: clarify when a new tip-name is assigned to a commit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T21:17:23Z","receivedAt":"2012-08-29T21:17:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In preparation for the later changes, restructure the logic a little\nbit to separate how the code decides to use the new \"tip\" for naming\na particular commit, and what happens based on the decision.\n\nAlso re-indent and correct style of this function while we are at it.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/name-rev.c | 45 +++++++++++++++++++++++++--------------------\n 1 file changed, 25 insertions(+), 20 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 8af2cfa..ebbf541 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -19,12 +19,13 @@ static long cutoff = LONG_MAX;\n #define MERGE_TRAVERSAL_WEIGHT 65535\n \n static void name_rev(struct commit *commit,\n-\t\tconst char *tip_name, int generation, int distance,\n-\t\tint deref)\n+\t\t     const char *tip_name, int generation, int distance,\n+\t\t     int deref)\n {\n \tstruct rev_name *name = (struct rev_name *)commit->util;\n \tstruct commit_list *parents;\n-\tint parent_number = 1;\n+\tint parent_number;\n+\tint use_this_tip = 0;\n \n \tif (!commit->object.parsed)\n \t\tparse_commit(commit);\n@@ -42,21 +43,26 @@ static void name_rev(struct commit *commit,\n \t\t\tdie(\"generation: %d, but deref?\", generation);\n \t}\n \n-\tif (name == NULL) {\n-\t\tname = xmalloc(sizeof(struct rev_name));\n+\tif (!name) {\n+\t\tname = xcalloc(1, sizeof(struct rev_name));\n \t\tcommit->util = name;\n-\t\tgoto copy_data;\n-\t} else if (name->distance > distance) {\n-copy_data:\n-\t\tname->tip_name = tip_name;\n-\t\tname->generation = generation;\n-\t\tname->distance = distance;\n-\t} else\n+\t\tuse_this_tip = 1;\n+\t}\n+\n+\tif (distance < name->distance)\n+\t\tuse_this_tip = 1;\n+\n+\tif (!use_this_tip)\n \t\treturn;\n \n-\tfor (parents = commit->parents;\n-\t\t\tparents;\n-\t\t\tparents = parents->next, parent_number++) {\n+\tname->tip_name = tip_name;\n+\tname->generation = generation;\n+\tname->distance = distance;\n+\n+\t/* Propagate our name to our parents */\n+\tfor (parents = commit->parents, parent_number = 1;\n+\t     parents;\n+\t     parents = parents->next, parent_number++) {\n \t\tif (parent_number > 1) {\n \t\t\tint len = strlen(tip_name);\n \t\t\tchar *new_name = xmalloc(len +\n@@ -68,16 +74,15 @@ copy_data:\n \t\t\t\tlen -= 2;\n \t\t\tif (generation > 0)\n \t\t\t\tsprintf(new_name, \"%.*s~%d^%d\", len, tip_name,\n-\t\t\t\t\t\tgeneration, parent_number);\n+\t\t\t\t\tgeneration, parent_number);\n \t\t\telse\n \t\t\t\tsprintf(new_name, \"%.*s^%d\", len, tip_name,\n-\t\t\t\t\t\tparent_number);\n-\n+\t\t\t\t\tparent_number);\n \t\t\tname_rev(parents->item, new_name, 0,\n-\t\t\t\tdistance + MERGE_TRAVERSAL_WEIGHT, 0);\n+\t\t\t\t distance + MERGE_TRAVERSAL_WEIGHT, 0);\n \t\t} else {\n \t\t\tname_rev(parents->item, tip_name, generation + 1,\n-\t\t\t\tdistance + 1, 0);\n+\t\t\t\t distance + 1, 0);\n \t\t}\n \t}\n }\n-- \n1.7.12.285.ga3d5fc0\n"},{"id":"198063","messageId":"1346275044-10171-4-git-send-email-gitster@pobox.com","threadId":"31378","inReplyTo":"1346275044-10171-1-git-send-email-gitster@pobox.com","subject":"[PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T21:17:24Z","receivedAt":"2012-08-29T21:17:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Instead of naming a rev after a tip that is topologically closest,\nuse the tip that is the oldest one among those which contain the\nrev.\n\nThe semantics \"name-rev --weight\" would give is closer to what\npeople expect from \"describe --contains\".\n\nNote that this is fairly expensive (see NEEDSWORK comment in the\ncode).\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/name-rev.c | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 95 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex ebbf541..69da41d 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -4,6 +4,8 @@\n #include \"tag.h\"\n #include \"refs.h\"\n #include \"parse-options.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n \n #define CUTOFF_DATE_SLOP 86400 /* one day */\n \n@@ -11,8 +13,85 @@ struct rev_name {\n \tconst char *tip_name;\n \tint generation;\n \tint distance;\n+\tint weight;\n };\n \n+/*\n+ * Historically, \"name-rev\" named a rev based on the tip that is\n+ * closest to it.\n+ *\n+ * It does not give a good answer to \"what is the earliest tag that\n+ * contains the commit?\", however, because you can build a new commit\n+ * on top of an ancient commit X, merge it to the tip and tag the\n+ * result, which would make X reachable from the new tag in two hops,\n+ * even though it appears in the part of the history that is contained\n+ * in other ancient tags.\n+ *\n+ * In order to answer that question, \"name-rev\" can be told to name a\n+ * rev based on the tip that has smallest number of commits behind it.\n+ */\n+static int use_weight;\n+\n+/*\n+ * NEEDSWORK: the result of this computation must be cached to\n+ * a dedicated notes tree, keyed by the commit object name.\n+ */\n+static int compute_tip_weight(struct commit *commit)\n+{\n+\tstruct rev_info revs;\n+\tint weight = 1; /* give root the weight of 1 */\n+\n+\treset_revision_walk();\n+\tinit_revisions(&revs, NULL);\n+\tadd_pending_object(&revs, (struct object *)commit, NULL);\n+\tprepare_revision_walk(&revs);\n+\twhile (get_revision(&revs))\n+\t\tweight++;\n+\treturn weight;\n+}\n+\n+static int tip_weight(const char *tip, size_t reflen)\n+{\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tunsigned char sha1[20];\n+\tstruct commit *commit;\n+\tstruct rev_name *name;\n+\n+\tstrbuf_add(&buf, tip, reflen);\n+\tif (get_sha1(buf.buf, sha1))\n+\t\tdie(\"Internal error: cannot parse tip '%s'\", tip);\n+\tstrbuf_release(&buf);\n+\n+\tcommit = lookup_commit_reference_gently(sha1, 0);\n+\tif (!commit)\n+\t\tdie(\"Internal error: cannot look up commit '%s'\", tip);\n+\tname = commit->util;\n+\tif (!name)\n+\t\tdie(\"Internal error: a tip without name '%s'\", tip);\n+\tif (!name->weight)\n+\t\tname->weight = compute_tip_weight(commit);\n+\treturn name->weight;\n+}\n+\n+static int tip_weight_cmp(const char *a, const char *b)\n+{\n+\tsize_t reflen_a, reflen_b;\n+\tstatic const char traversal[] = \"^~\";\n+\n+\t/*\n+\t * A \"tip\" may look like <refname> followed by traversal\n+\t * instruction (e.g. ^2~74).  We only are interested in\n+\t * the weight of the ref part.\n+\t */\n+\treflen_a = strcspn(a, traversal);\n+\treflen_b = strcspn(b, traversal);\n+\n+\tif (reflen_a == reflen_b && !memcmp(a, b, reflen_a))\n+\t\treturn 0;\n+\n+\treturn tip_weight(a, reflen_a) - tip_weight(b, reflen_b);\n+}\n+\n static long cutoff = LONG_MAX;\n \n /* How many generations are maximally preferred over _one_ merge traversal? */\n@@ -49,8 +128,20 @@ static void name_rev(struct commit *commit,\n \t\tuse_this_tip = 1;\n \t}\n \n-\tif (distance < name->distance)\n-\t\tuse_this_tip = 1;\n+\tif (!use_weight) {\n+\t\tif (distance < name->distance)\n+\t\t\tuse_this_tip = 1;\n+\t} else {\n+\t\tif (!name->tip_name)\n+\t\t\tuse_this_tip = 1;\n+\t\telse {\n+\t\t\tint cmp = tip_weight_cmp(name->tip_name, tip_name);\n+\t\t\tif (0 < cmp)\n+\t\t\t\tuse_this_tip = 1;\n+\t\t\telse if (!cmp && distance < name->distance)\n+\t\t\t\tuse_this_tip = 1;\n+\t\t}\n+\t}\n \n \tif (!use_this_tip)\n \t\treturn;\n@@ -241,6 +332,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\tOPT_BOOLEAN(0, \"undefined\", &allow_undefined, \"allow to print `undefined` names\"),\n \t\tOPT_BOOLEAN(0, \"always\",     &always,\n \t\t\t   \"show abbreviated commit object as fallback\"),\n+\t\tOPT_BOOLEAN(0, \"weight\", &use_weight,\n+\t\t\t    \"name revs based on the oldest tip that contain them\"),\n \t\tOPT_END(),\n \t};\n \n-- \n1.7.12.285.ga3d5fc0\n"},{"id":"198069","messageId":"7vligxuv6l.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"1346275044-10171-4-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-29T23:37:06Z","receivedAt":"2012-08-29T23:37:06Z","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> Note that this is fairly expensive (see NEEDSWORK comment in the\n> code).\n\nAnd this is with the \"notes-cache\".\n\n    (priming the cache from scratch)\n    $ rm .git/refs/notes/name-rev-weight \n    $ /usr/bin/time ../git.git/git-name-rev --weight --tags 0136db586c\n    0136db586c tags/v3.5-rc1~83^2~81^2~76\n    6.06user 0.46system 0:06.54elapsed 99%CPU (0avgtext+0avgdata 1861456maxresident)k\n    8inputs+16outputs (0major+128576minor)pagefaults 0swaps\n\n    (with valid cache)\n    $ /usr/bin/time ../git.git/git-name-rev --weight --tags 0136db586c\n    0136db586c tags/v3.5-rc1~83^2~81^2~76\n    0.50user 0.22system 0:00.72elapsed 100%CPU (0avgtext+0avgdata 244224maxresident)k\n    0inputs+0outputs (0major+16062minor)pagefaults 0swaps\n\n    (the old \"shortest path\" version)\n    $ /usr/bin/time git name-rev --tags 0136db586c\n    0136db586c tags/v3.6-rc1~59^2~56^2~76\n    0.31user 0.01system 0:00.32elapsed 100%CPU (0avgtext+0avgdata 243488maxresident)k\n    0inputs+0outputs (0major+16000minor)pagefaults 0swaps\n\n\n builtin/name-rev.c | 38 +++++++++++++++++++++++++++++++++-----\n 1 file changed, 33 insertions(+), 5 deletions(-)\n\ndiff --git c/builtin/name-rev.c w/builtin/name-rev.c\nindex 69da41d..fdd087c 100644\n--- c/builtin/name-rev.c\n+++ w/builtin/name-rev.c\n@@ -6,6 +6,7 @@\n #include \"parse-options.h\"\n #include \"diff.h\"\n #include \"revision.h\"\n+#include \"notes-cache.h\"\n \n #define CUTOFF_DATE_SLOP 86400 /* one day */\n \n@@ -32,10 +33,6 @@ struct rev_name {\n  */\n static int use_weight;\n \n-/*\n- * NEEDSWORK: the result of this computation must be cached to\n- * a dedicated notes tree, keyed by the commit object name.\n- */\n static int compute_tip_weight(struct commit *commit)\n {\n \tstruct rev_info revs;\n@@ -50,6 +47,31 @@ static int compute_tip_weight(struct commit *commit)\n \treturn weight;\n }\n \n+static struct notes_cache weight_cache;\n+static int weight_cache_updated;\n+\n+static int get_tip_weight(struct commit *commit)\n+{\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tsize_t sz;\n+\tint weight;\n+\tchar *note = notes_cache_get(&weight_cache, commit->object.sha1, &sz);\n+\n+\tif (note && !strtol_i(note, 10, &weight)) {\n+\t\tfree(note);\n+\t\treturn weight;\n+\t}\n+\tfree(note);\n+\n+\tweight = compute_tip_weight(commit);\n+\tstrbuf_addf(&buf, \"%d\", weight);\n+\tnotes_cache_put(&weight_cache, commit->object.sha1,\n+\t\t\tbuf.buf, buf.len);\n+\tstrbuf_release(&buf);\n+\tweight_cache_updated = 1;\n+\treturn weight;\n+}\n+\n static int tip_weight(const char *tip, size_t reflen)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -69,7 +91,7 @@ static int tip_weight(const char *tip, size_t reflen)\n \tif (!name)\n \t\tdie(\"Internal error: a tip without name '%s'\", tip);\n \tif (!name->weight)\n-\t\tname->weight = compute_tip_weight(commit);\n+\t\tname->weight = get_tip_weight(commit);\n \treturn name->weight;\n }\n \n@@ -346,6 +368,9 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \tif (all || transform_stdin)\n \t\tcutoff = 0;\n \n+\tif (use_weight)\n+\t\tnotes_cache_init(&weight_cache, \"name-rev-weight\", \"2012-08-29\");\n+\n \tfor (; argc; argc--, argv++) {\n \t\tunsigned char sha1[20];\n \t\tstruct object *o;\n@@ -401,5 +426,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\t\t\t  always, allow_undefined, data.name_only);\n \t}\n \n+\tif (use_weight && weight_cache_updated)\n+\t\tnotes_cache_write(&weight_cache);\n+\n \treturn 0;\n }\n"},{"id":"198070","messageId":"20120830033611.GA32268@sigill.intra.peff.net","threadId":"31378","inReplyTo":"7vligxuv6l.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-30T03:36:11Z","receivedAt":"2012-08-30T03:36:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2012 at 04:37:06PM -0700, Junio C Hamano wrote:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> > Note that this is fairly expensive (see NEEDSWORK comment in the\n> > code).\n> \n> And this is with the \"notes-cache\".\n> [...]\n> +static int get_tip_weight(struct commit *commit)\n> +{\n> +\tstruct strbuf buf = STRBUF_INIT;\n> +\tsize_t sz;\n> +\tint weight;\n> +\tchar *note = notes_cache_get(&weight_cache, commit->object.sha1, &sz);\n> +\n> +\tif (note && !strtol_i(note, 10, &weight)) {\n> +\t\tfree(note);\n> +\t\treturn weight;\n> +\t}\n> +\tfree(note);\n> +\n> +\tweight = compute_tip_weight(commit);\n> +\tstrbuf_addf(&buf, \"%d\", weight);\n> +\tnotes_cache_put(&weight_cache, commit->object.sha1,\n> +\t\t\tbuf.buf, buf.len);\n> +\tstrbuf_release(&buf);\n> +\tweight_cache_updated = 1;\n> +\treturn weight;\n> +}\n\nIt looks like you didn't update compute_tip_weight at all, so it will\nstill do the full traversal down to the roots. I wonder if you can\ndefine the weight as a recursive function of the parents. Using the sum\nof the weights of the parents is not right, because you would\ndouble-count in this situation:\n\n  A--B--C--D---M\n      \\       /\n       E--F--G\n\nThat would double-count \"A\" and \"B\" in this example. But maybe there is\na clever way to define it that avoids that.\n\nThe advantage would be that you could cheaply find the weights of new\ncommits by only traversing back to the last cached one. I did something\nsimilar with the generation number cache (but the recursive definition\nis easier there).\n\n> +\tif (use_weight)\n> +\t\tnotes_cache_init(&weight_cache, \"name-rev-weight\", \"2012-08-29\");\n\nIs that a sufficient validity field? What about grafts or replace\nobjects? For the generation cache, I used a hash of the graft and\nreplace fields.\n\n-Peff\n"},{"id":"198075","messageId":"20120830035127.GB32268@sigill.intra.peff.net","threadId":"31378","inReplyTo":"1346275044-10171-4-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-30T03:51:27Z","receivedAt":"2012-08-30T03:51:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2012 at 02:17:24PM -0700, Junio C Hamano wrote:\n\n> Instead of naming a rev after a tip that is topologically closest,\n> use the tip that is the oldest one among those which contain the\n> rev.\n\nWhen you wrote \"oldest\" here, I thought that meant you would do a\ncomparison on the taggerdate. But reading the implementation, you really\nmean \"topologically oldest\".\n\nI wonder, though, if the former would be sufficient for most people. Or\neven just sorting based on the tag name. For example, taking Greg's\noriginal example:\n\n  $ commit=0136db586c028f71e7cc21cc183064ff0d5919\n  $ oldest_tag=`git tag --contains $commit | sort -V | head -1`\n  $ git name-rev --refs=\"refs/tags/$oldest_tag\" $commit\n  0136db586c028f71e7cc21cc183064ff0d5919 tags/v3.5~335^2~81^2~76\n\nOf course \"sort -V\" is not portable, and it actually places -rc tags\nafter release tags (note that we found v3.5 here, not v3.5-rc1). But\nthat is an implementation detail that could be solved (either by a\nbetter comparison function, or by just using taggerdate instead).\n\nIn some ways it is not as elegant (clock skew in your tag dates would be\nrelevant), but it is simple and performs well without needing to manage\na cache.\n\n-Peff\n"},{"id":"198079","messageId":"7vharlujaq.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"20120830033611.GA32268@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T03:53:49Z","receivedAt":"2012-08-30T03:53:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> I wonder if you can\n> define the weight as a recursive function of the parents.\n\nI do not think we can.  A merge Z between X (that has N commits\nbehind it) and Y (that has M commits behind it) has at most N+M+1\ncommits behind it (counting itself), but we cannot tell how many\namong these N and M are shared.\n\n> That would double-count \"A\" and \"B\" in this example. But maybe there is\n> a clever way to define it that avoids that.\n\nWe've dealt with this issue long time ago when we optimized the\nbisection count, which involves exactly the same issue.\n"},{"id":"198080","messageId":"20120830035552.GC32268@sigill.intra.peff.net","threadId":"31378","inReplyTo":"7vharlujaq.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-30T03:55:52Z","receivedAt":"2012-08-30T03:55:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2012 at 08:53:49PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > I wonder if you can\n> > define the weight as a recursive function of the parents.\n> \n> I do not think we can.  A merge Z between X (that has N commits\n> behind it) and Y (that has M commits behind it) has at most N+M+1\n> commits behind it (counting itself), but we cannot tell how many\n> among these N and M are shared.\n> \n> > That would double-count \"A\" and \"B\" in this example. But maybe there is\n> > a clever way to define it that avoids that.\n> \n> We've dealt with this issue long time ago when we optimized the\n> bisection count, which involves exactly the same issue.\n\nOK. I didn't think too hard about it, so I'll trust you that it is not\neasy. I wonder if using the generation number would be another way of\ndefining \"oldest\" that would be easier to calculate.\n\n-Peff\n"},{"id":"198081","messageId":"7vd329uiko.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"20120830035127.GB32268@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T04:09:27Z","receivedAt":"2012-08-30T04:09:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> When you wrote \"oldest\" here, I thought that meant you would do a\n> comparison on the taggerdate. But reading the implementation, you really\n> mean \"topologically oldest\".\n>\n> I wonder, though, if the former would be sufficient for most people.\n\nEven without clock skew, timestamps are inappropriate measure for\nthe purpose of measuring \"this dates back to...\", unless you are\nlimiting yourself to very linear history.  Even in our own history,\nv1.7.6.6 is 4 months newer than v1.7.7, for example.  The same holds\ntrue between v1.7.6.6^0 and v1.7.7^0, so the story does not change\nwhether you use tagger date or committer date.\n\nBasing this based on tag names is an attractive idea, but we would\nneed to devise a way for people to pass project specific tagname\ncomparison function from outside.  v3.2 is newer than v3.2-rc1 but\nv3.2-bis may probably be newer than v3.2 and I do not think we want\nto collect the rules and cast the logic in our code in stone.\n"},{"id":"198082","messageId":"7v8vcxuiil.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"20120830035552.GC32268@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T04:10:42Z","receivedAt":"2012-08-30T04:10:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> OK. I didn't think too hard about it, so I'll trust you that it is not\n> easy. I wonder if using the generation number would be another way of\n> defining \"oldest\" that would be easier to calculate.\n\nGo back to my illustration to Greg and think about the implication\nof \"TONS!\" side branch in the picture has on the generation numbers.\n"},{"id":"198083","messageId":"7v4nnluibd.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"7v8vcxuiil.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T04:15:02Z","receivedAt":"2012-08-30T04:15:02Z","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> Jeff King <peff@peff.net> writes:\n>\n>> OK. I didn't think too hard about it, so I'll trust you that it is not\n>> easy. I wonder if using the generation number would be another way of\n>> defining \"oldest\" that would be easier to calculate.\n>\n> Go back to my illustration to Greg and think about the implication\n> of \"TONS!\" side branch in the picture has on the generation numbers.\n\nThat is, we want some number (I called it \"weight\") that grows when\n\"TONS!\" side branch is heavy.  Generation numbers are about giving\nlarger numbers for _longer_ chains, but a long and thin side branch\ndoes not contribute as much as a medium length but a very fat side\nbranch when merged.\n\nSo generation numbers might be a candidate for approximation, but I\ndo not think it will give us a _good_ approximation.\n"},{"id":"198086","messageId":"068F712399864538B59054590881E19C@PhilipOakley","threadId":"31378","inReplyTo":"1346275044-10171-1-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 0/3] \"git name-rev --weight\"","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":"2012-08-30T07:06:33Z","receivedAt":"2012-08-30T07:06:33Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Junio C Hamano\" <gitster@pobox.com>\nSent: Wednesday, August 29, 2012 10:17 PM\n> So here is an attempt to teach \"name-rev\" a mode that tries to base\n> its name on oldest tag that can reach the commit.  It needs the\n> reset_revision_walk() call recently added to the revision traversal\n> API, and applies to bcc0a3e (v1.7.11-rc0~111^2~2) or newer.\n>\n> Note that this can benefit from caching, as the \"weight\" of the tag\n> (rather, the commit that is tagged) will never change once a history\n> is made, but that part is left as an exercise to the reader.\n\nIs \"--weight\" the right term to use for the user (cli) interface? \nWouldn't '--oldest' (or similar) be a better statement of what is \ndesired (absent clock skew).\n\nWhile 'weight' may be a good internal technical description it didn't \nconvey to me what was being sought (maybe -- deepest'?).\n\n>\n> It correctly names 0136db586c in the kernel history as based on\n> v3.5-rc1 as tags/v3.5-rc1~83^2~81^2~76, not on v3.6-rc1, as we saw\n> on the list recently.\n>\n> Once it is verified to operate correctly and updated to perform\n> properly, we can start passing --weight when \"describe --contains\"\n> runs the command.\n>\n> Junio C Hamano (3):\n>  name-rev: lose unnecessary typedef\n>  name_rev: clarify when a new tip-name is assigned to a commit\n>  name-rev: --weight option (WIP)\n>\n> builtin/name-rev.c | 142 \n> ++++++++++++++++++++++++++++++++++++++++++++---------\n> 1 file changed, 120 insertions(+), 22 deletions(-)\n>\n> -- \n> 1.7.12.285.ga3d5fc0\n>\n"},{"id":"198102","messageId":"7vk3wgtlxb.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"068F712399864538B59054590881E19C@PhilipOakley","subject":"Re: [PATCH 0/3] \"git name-rev --weight\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T15:54:40Z","receivedAt":"2012-08-30T15:54:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Philip Oakley\" <philipoakley@iee.org> writes:\n\n> Is \"--weight\" the right term to use for the user (cli) interface?\n> Wouldn't '--oldest' (or similar) be a better statement of what is\n> desired (absent clock skew).\n>\n> While 'weight' may be a good internal technical description it didn't\n> convey to me what was being sought (maybe -- deepest'?).\n\nI agree with you that weight represents what it internally does.  I\nhowever think that \"oldest\" is not quite good, as it still leaves\nthe source of possible confusion.  It has at least 3 (or 4,\ndepending on how you count) possible meanings.\n\n - Is it the one with the oldest timestamp (and if so, do we use the\n   committer date, or do we use the tagger date that may be much\n   newer than the committer date)?\n\n - Is it the one with its longest path down to the root is the\n   shortest (i.e. with smallest generation number)?\n\n - Is it the one with the smallest number of ancestor commits?\n\nFor the purpose of \"oldest tag that contains this commit\", I think\nthe last one would give the most intuitive answer, but depending on\nyour use case, you may want to enhance the command to support other\ndefinition of \"oldest\"; it does not feel quite right to have this\nparticular definition (the last one) squat on the generic \"--oldest\"\nname.\n\nWe could punt to tautology and call it \"--contains\", meaning that is\nthe logic used to implement \"describe --contains\" ;-) but that is\nnot satisfactory, either.\n\nI dunno.\n"},{"id":"198103","messageId":"7vfw74tlon.fsf@alter.siamese.dyndns.org","threadId":"31378","inReplyTo":"7vharlujaq.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/3] name-rev: --weight option (WIP)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-30T15:59:52Z","receivedAt":"2012-08-30T15:59:52Z","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> Jeff King <peff@peff.net> writes:\n>\n>> I wonder if you can\n>> define the weight as a recursive function of the parents.\n>\n> I do not think we can.  A merge Z between X (that has N commits\n> behind it) and Y (that has M commits behind it) has at most N+M+1\n> commits behind it (counting itself), but we cannot tell how many\n> among these N and M are shared.\n\nYou can theoretically take all the merge bases between X and Y,\nmagically come up with the \"weight\" of a fictitious merge across\nthese merge bases, and subtract that number from N+M to arrive at\nthe weight of Z, I suppose, but it is not clear what an efficient\nimplementation of that \"magically\" part looks like.  I think that is\nwhere we stopped when we tried to optimize the \"rev-list --bisect\"\nnode weighting logic; it punts handling the merges, and only\noptimizes single strand of pearls on top of a merge with a known\nweight.\n"}]}