{"thread":{"id":"9623","subject":"name-rev does not show the shortest path","startedAt":"2007-08-23T10:38:17Z","lastAt":"2007-08-27T19:27:35Z","messageCount":13,"participants":["Uwe Kleine-König","Julian Phillips","Junio C Hamano","Johannes Schindelin","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"51363","messageId":"20070823103817.GF6573@informatik.uni-freiburg.de","threadId":"9623","inReplyTo":null,"subject":"name-rev does not show the shortest path","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-08-23T10:38:17Z","receivedAt":"2007-08-23T10:38:17Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello,\n\nI want to check to which kernel version I need to upgrade to get a\ncertain feature.  For my case it was introduced in 0567a0c022d5b.\n\n\tzeisberg@cassiopeia:~/gsrc/linux-2.6$ rev=0567a0c022d5b343370a343121f38fd89925de55\n\n\tzeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev\n\t0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22~1686^2~1^3~5\n\n\tzeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev\n\t0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22-rc1~1009^2~1^3~5\n\nI don't now the underlaying algorithm, maybe it's to get a short string?\n\nAnyhow I want to know the earliest tag that includes this patch?  Is\nthere something I missed?\n\nI remember there was a similar discussion regarding describe.\n\nBTW: gitk does the right thing, it says:\n\n\tFollows: v2.6.21-rc7\n\tPrecedes: v2.6.22-rc1\n\n(called with \n\n\tzeisberg@cassiopeia:~/gsrc/linux-2.6$ gitk 0567a0c022d5b343370a343121f38fd89925de55^..0567a0c022d5b343370a343121f38fd89925de55\n)\n\nI didn't check how it does that though.\n\nBest regards\nUwe\n\n-- \nUwe Kleine-König\n\nexit vi, lesson I:\n: q ! <CR>\n"},{"id":"51443","messageId":"Pine.LNX.4.64.0708241253050.8987@reaper.quantumfyre.co.uk","threadId":"9623","inReplyTo":"20070823103817.GF6573@informatik.uni-freiburg.de","subject":"Re: name-rev does not show the shortest path","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-08-24T11:55:19Z","receivedAt":"2007-08-24T11:55:19Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Thu, 23 Aug 2007, Uwe Kleine-König wrote:\n\n> Hello,\n>\n> I want to check to which kernel version I need to upgrade to get a\n> certain feature.  For my case it was introduced in 0567a0c022d5b.\n>\n> \tzeisberg@cassiopeia:~/gsrc/linux-2.6$ rev=0567a0c022d5b343370a343121f38fd89925de55\n>\n> \tzeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev\n> \t0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22~1686^2~1^3~5\n>\n> \tzeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev\n> \t0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22-rc1~1009^2~1^3~5\n>\n> I don't now the underlaying algorithm, maybe it's to get a short string?\n>\n> Anyhow I want to know the earliest tag that includes this patch?  Is\n> there something I missed?\n>\n> I remember there was a similar discussion regarding describe.\n\ngit describe --contains 0567a0c022d5b\n\nprobably a 1.5.3 feature? (certainly doesn't exist in 1.5.2.2)\n\n-- \nJulian\n\n  ---\nMan who sleep in beer keg wake up sticky."},{"id":"51444","messageId":"20070824125230.GA12030@informatik.uni-freiburg.de","threadId":"9623","inReplyTo":"Pine.LNX.4.64.0708241253050.8987@reaper.quantumfyre.co.uk","subject":"Re: name-rev does not show the shortest path","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-08-24T12:52:30Z","receivedAt":"2007-08-24T12:52:30Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello Julian,\n\nJulian Phillips wrote:\n> On Thu, 23 Aug 2007, Uwe Kleine-König wrote:\n> >I want to check to which kernel version I need to upgrade to get a\n> >certain feature.  For my case it was introduced in 0567a0c022d5b.\n> >\n> >\tzeisberg@cassiopeia:~/gsrc/linux-2.6$ \n> >\trev=0567a0c022d5b343370a343121f38fd89925de55\n> >\n> >\tzeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev\n> >\t0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22~1686^2~1^3~5\n> >\n> >\tzeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev\n> >\t0567a0c022d5b343370a343121f38fd89925de55 \n> >\ttags/v2.6.22-rc1~1009^2~1^3~5\n> >\n> >I don't now the underlaying algorithm, maybe it's to get a short string?\n> >\n> >Anyhow I want to know the earliest tag that includes this patch?  Is\n> >there something I missed?\n> >\n> >I remember there was a similar discussion regarding describe.\n> \n> git describe --contains 0567a0c022d5b\n> \n> probably a 1.5.3 feature? (certainly doesn't exist in 1.5.2.2)\nThat command says v2.6.22~1686^2~1^3~5, too.  That is, it doesn't use\nthe \"older\" v2.6.22-rc1 tag as a basis.\n\nBest regards\nUwe\n\n\n-- \nUwe Kleine-König\n\nhttp://www.google.com/search?q=1+degree+celsius+in+kelvin\n"},{"id":"51447","messageId":"Pine.LNX.4.64.0708241615040.7313@reaper.quantumfyre.co.uk","threadId":"9623","inReplyTo":"20070824125230.GA12030@informatik.uni-freiburg.de","subject":"Re: name-rev does not show the shortest path","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-08-24T15:21:46Z","receivedAt":"2007-08-24T15:21:46Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Fri, 24 Aug 2007, Uwe Kleine-König wrote:\n\n> Hello Julian,\n>\n> Julian Phillips wrote:\n>> On Thu, 23 Aug 2007, Uwe Kleine-König wrote:\n>>> I want to check to which kernel version I need to upgrade to get a\n>>> certain feature.  For my case it was introduced in 0567a0c022d5b.\n>>>\n>>> \tzeisberg@cassiopeia:~/gsrc/linux-2.6$\n>>> \trev=0567a0c022d5b343370a343121f38fd89925de55\n>>>\n>>> \tzeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev\n>>> \t0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22~1686^2~1^3~5\n>>>\n>>> \tzeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev\n>>> \t0567a0c022d5b343370a343121f38fd89925de55\n>>> \ttags/v2.6.22-rc1~1009^2~1^3~5\n>>>\n>>> I don't now the underlaying algorithm, maybe it's to get a short string?\n>>>\n>>> Anyhow I want to know the earliest tag that includes this patch?  Is\n>>> there something I missed?\n>>>\n>>> I remember there was a similar discussion regarding describe.\n>>\n>> git describe --contains 0567a0c022d5b\n>>\n>> probably a 1.5.3 feature? (certainly doesn't exist in 1.5.2.2)\n> That command says v2.6.22~1686^2~1^3~5, too.  That is, it doesn't use\n> the \"older\" v2.6.22-rc1 tag as a basis.\n\nFrom a quick look at the code, that's not surprising, it runs \"git \nname-rev --name-only --tags\" under the bonnet - so not helpful at all, \nsorry.\n\nSo now I wonder how useful --contains really is ... I would have expected \nto always get the \"closest\" tag.  ~1009^2~1^3~5 seems closer than \n~1686^2~1^3~5 to me ... ho hum.\n\n-- \nJulian\n\n  ---\nAnd that's the way it is...\n \t\t-- Walter Cronkite"},{"id":"51459","messageId":"7v6434eq9o.fsf@gitster.siamese.dyndns.org","threadId":"9623","inReplyTo":"Pine.LNX.4.64.0708241615040.7313@reaper.quantumfyre.co.uk","subject":"Re: name-rev does not show the shortest path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-24T18:33:39Z","receivedAt":"2007-08-24T18:33:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Julian Phillips <julian@quantumfyre.co.uk> writes:\n\n> From a quick look at the code, that's not surprising, it runs \"git\n> name-rev --name-only --tags\" under the bonnet - so not helpful at all,\n> sorry.\n>\n> So now I wonder how useful --contains really is ... I would have\n> expected to always get the \"closest\" tag.  ~1009^2~1^3~5 seems closer\n> than ~1686^2~1^3~5 to me ... ho hum.\n\nThe usefulness of --contains is only to provide a nicer looking\nshortcut to older name-rev program, as more people are already\nfamiliar with \"git describe\".  It does not improve name-rev.\n\nI _think_ name-rev goes for shorter-to-type tags and does not\nhave any other heuristics.  Dscho?\n"},{"id":"51511","messageId":"Pine.LNX.4.64.0708251701150.16728@wbgn129.biozentrum.uni-wuerzburg.de","threadId":"9623","inReplyTo":"7v6434eq9o.fsf@gitster.siamese.dyndns.org","subject":"Re: name-rev does not show the shortest path","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-08-25T15:04:33Z","receivedAt":"2007-08-25T15:04:33Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 24 Aug 2007, Junio C Hamano wrote:\n\n> I _think_ name-rev goes for shorter-to-type tags and does not have any \n> other heuristics.  Dscho?\n\nI briefly looked into this, and did not find out why it is behaving that \nway.  It _should_ pick the closer one with this code:\n\n        } else if (name->merge_traversals > merge_traversals ||\n                        (name->merge_traversals == merge_traversals &&\n                         name->generation > generation)) {\n\nHowever, it did not even get to that code in my tests.  I'll have to look \nat that problem closer in a quiet moment (which I will not have for at \nleast another 24 hours).\n\nCiao,\nDscho\n"},{"id":"51551","messageId":"20070826092323.GB30474@coredump.intra.peff.net","threadId":"9623","inReplyTo":"Pine.LNX.4.64.0708251701150.16728@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: name-rev does not show the shortest path","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-08-26T09:23:23Z","receivedAt":"2007-08-26T09:23:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 25, 2007 at 05:04:33PM +0200, Johannes Schindelin wrote:\n\n> I briefly looked into this, and did not find out why it is behaving that \n> way.  It _should_ pick the closer one with this code:\n> \n>         } else if (name->merge_traversals > merge_traversals ||\n>                         (name->merge_traversals == merge_traversals &&\n>                          name->generation > generation)) {\n> \n> However, it did not even get to that code in my tests.  I'll have to look \n> at that problem closer in a quiet moment (which I will not have for at \n> least another 24 hours).\n\nIt does execute that code, just not for the rev in question. We hit the\nthird part of that conditional and stop recursing on a different rev, so\nwe only touch our \"interesting\" rev one time.\n\nThat being said, I think this test is totally bogus. You're just looking\nat the generation and merge traversals from some tip. However, the tip\n_isn't_ the actual ref, but instead gets re-written as a string when we\nfollow a merge. That string contains important generational information\nthat is no longer taken into account, so you end up with things like\n\"foo~999\" with generation \"3\" is better than \"bar~10\" with generation\n\"5\".\n\nHere is a patch (below) that tracks an absolute \"distance to ref\" and at\nleast names the rev in question after v2.6.22-rc1. However, because it\nis now preferring \"distance to ref\" strictly over merge traversals, it\nseems to generate some obscenely long names:\n\n0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22-rc1~1^2^2^2~11^2~13^2~8^2~1^3~5\n\nSo perhaps there is a more sane metric, but I'd have to think about it\nmore.\n\n-Peff\n\n---\ndiff --git a/builtin-name-rev.c b/builtin-name-rev.c\nindex 61eba34..c003e20 100644\n--- a/builtin-name-rev.c\n+++ b/builtin-name-rev.c\n@@ -13,13 +13,14 @@ typedef struct rev_name {\n \tconst char *tip_name;\n \tint merge_traversals;\n \tint generation;\n+\tint distance;\n } rev_name;\n \n static long cutoff = LONG_MAX;\n \n static void name_rev(struct commit *commit,\n \t\tconst char *tip_name, int merge_traversals, int generation,\n-\t\tint deref)\n+\t\tint deref, int distance)\n {\n \tstruct rev_name *name = (struct rev_name *)commit->util;\n \tstruct commit_list *parents;\n@@ -45,13 +46,16 @@ static void name_rev(struct commit *commit,\n \t\tname = xmalloc(sizeof(rev_name));\n \t\tcommit->util = name;\n \t\tgoto copy_data;\n-\t} else if (name->merge_traversals > merge_traversals ||\n-\t\t\t(name->merge_traversals == merge_traversals &&\n-\t\t\t name->generation > generation)) {\n+\t} else if (name->distance > distance ||\n+\t\t\t(name->distance == distance &&\n+\t\t\t name->merge_traversals > merge_traversals ||\n+\t\t\t (name->merge_traversals == merge_traversals &&\n+\t\t\t  name->generation > generation))) {\n copy_data:\n \t\tname->tip_name = tip_name;\n \t\tname->merge_traversals = merge_traversals;\n \t\tname->generation = generation;\n+\t\tname->distance = distance;\n \t} else\n \t\treturn;\n \n@@ -75,10 +79,10 @@ copy_data:\n \t\t\t\t\t\tparent_number);\n \n \t\t\tname_rev(parents->item, new_name,\n-\t\t\t\tmerge_traversals + 1 , 0, 0);\n+\t\t\t\tmerge_traversals + 1 , 0, 0, distance + 1);\n \t\t} else {\n \t\t\tname_rev(parents->item, tip_name, merge_traversals,\n-\t\t\t\tgeneration + 1, 0);\n+\t\t\t\tgeneration + 1, 0, distance + 1);\n \t\t}\n \t}\n }\n@@ -120,7 +124,7 @@ static int name_ref(const char *path, const unsigned char *sha1, int flags, void\n \t\telse if (!prefixcmp(path, \"refs/\"))\n \t\t\tpath = path + 5;\n \n-\t\tname_rev(commit, xstrdup(path), 0, 0, deref);\n+\t\tname_rev(commit, xstrdup(path), 0, 0, deref, 0);\n \t}\n \treturn 0;\n }\n"},{"id":"51563","messageId":"Pine.LNX.4.64.0708261733400.16728@wbgn129.biozentrum.uni-wuerzburg.de","threadId":"9623","inReplyTo":"20070826092323.GB30474@coredump.intra.peff.net","subject":"Re: name-rev does not show the shortest path","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-08-26T15:38:22Z","receivedAt":"2007-08-26T15:38:22Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 26 Aug 2007, Jeff King wrote:\n\n> On Sat, Aug 25, 2007 at 05:04:33PM +0200, Johannes Schindelin wrote:\n> \n> > I briefly looked into this, and did not find out why it is behaving that \n> > way.  It _should_ pick the closer one with this code:\n> > \n> >         } else if (name->merge_traversals > merge_traversals ||\n> >                         (name->merge_traversals == merge_traversals &&\n> >                          name->generation > generation)) {\n> > \n> > However, it did not even get to that code in my tests.  I'll have to look \n> > at that problem closer in a quiet moment (which I will not have for at \n> > least another 24 hours).\n> \n> It does execute that code, just not for the rev in question. We hit the\n> third part of that conditional and stop recursing on a different rev, so\n> we only touch our \"interesting\" rev one time.\n\nYes, I guessed as much.\n\n> That being said, I think this test is totally bogus. You're just looking\n> at the generation and merge traversals from some tip. However, the tip\n> _isn't_ the actual ref, but instead gets re-written as a string when we\n> follow a merge. That string contains important generational information\n> that is no longer taken into account, so you end up with things like\n> \"foo~999\" with generation \"3\" is better than \"bar~10\" with generation\n> \"5\".\n\nBut this did not happen here, right?  Just the first part was different...\n\n> Here is a patch (below) that tracks an absolute \"distance to ref\" and at\n> least names the rev in question after v2.6.22-rc1. However, because it\n> is now preferring \"distance to ref\" strictly over merge traversals, it\n> seems to generate some obscenely long names:\n> \n> 0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22-rc1~1^2^2^2~11^2~13^2~8^2~1^3~5\n> \n> So perhaps there is a more sane metric, but I'd have to think about it\n> more.\n\nThe old code _should_ have worked; it is more likely that your different \nmetric just hides the bug.  The old metric tried to favour less merge \ntraversals over more traversals, but at the same time, it favoured smaller \nnumbers over larger ones (but as you found out, only in the last \ncomponent).\n\nI guess there is something else going on, such as the tag v2.6.22-rc1 \nbeing marked uninteresting because v2.6.22 and its ancestors being \ntraversed already.\n\nCiao,\nDscho\n"},{"id":"51664","messageId":"20070827092422.GA20340@coredump.intra.peff.net","threadId":"9623","inReplyTo":"Pine.LNX.4.64.0708261733400.16728@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: name-rev does not show the shortest path","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-08-27T09:24:23Z","receivedAt":"2007-08-27T09:24:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Aug 26, 2007 at 05:38:22PM +0200, Johannes Schindelin wrote:\n\n> > that is no longer taken into account, so you end up with things like\n> > \"foo~999\" with generation \"3\" is better than \"bar~10\" with generation\n> > \"5\".\n> \n> But this did not happen here, right?  Just the first part was different...\n\nYes, in this case, I think the process is stopping because the\ngenerations and merge traversals are the same for two paths, but the\n'tip_name' information is indicating a much larger generational\ndifference from a ref. For example, \"tags/v2.6.22-rc1~1131^2\" loses out\nto \"tags/v2.6.22~1808^2\", which seems very wrong.\n\nI found it informative to instrument the code like this:\n\ndiff --git a/builtin-name-rev.c b/builtin-name-rev.c\nindex 61eba34..9830595 100644\n--- a/builtin-name-rev.c\n+++ b/builtin-name-rev.c\n@@ -41,19 +41,26 @@ static void name_rev(struct commit *commit,\n \t\t\tdie(\"generation: %d, but deref?\", generation);\n \t}\n \n+\tprintf(\"considering %s~%d\\n\", tip_name, generation);\n \tif (name == NULL) {\n \t\tname = xmalloc(sizeof(rev_name));\n \t\tcommit->util = name;\n+\t\tprintf(\"  better than NULL\\n\");\n \t\tgoto copy_data;\n \t} else if (name->merge_traversals > merge_traversals ||\n \t\t\t(name->merge_traversals == merge_traversals &&\n \t\t\t name->generation > generation)) {\n+\t\tprintf(\"  better than %s~%d\\n\",\n+\t\t\t\tname->tip_name, name->generation);\n copy_data:\n \t\tname->tip_name = tip_name;\n \t\tname->merge_traversals = merge_traversals;\n \t\tname->generation = generation;\n-\t} else\n+\t} else {\n+\t\tprintf(\"  not as good as %s~%d\\n\",\n+\t\t\t\tname->tip_name, name->generation);\n \t\treturn;\n+\t}\n \n \tfor (parents = commit->parents;\n \t\t\tparents;\n\n\n> The old code _should_ have worked; it is more likely that your different \n> metric just hides the bug.  The old metric tried to favour less merge \n> traversals over more traversals, but at the same time, it favoured smaller \n> numbers over larger ones (but as you found out, only in the last \n> component).\n\nRight, the problem is that we have effectively _thrown away_ the\n\"smaller numbers over larger ones\" information for components other than\nthe last. I wonder if what we really want is to maintain a list of\ngenerations, one per merge traversal.\n\nSo that foo~500^2~20 and bar~499^2~20 would be represented as:\n\n  [500, 21]\n  [499, 21]\n\nAnd then you could compare names by favoring smaller numbers in earlier\ntraversals (you could still use \"fewer merge traversals\" as a metric\nbefore that, as well).\n\n> I guess there is something else going on, such as the tag v2.6.22-rc1 \n> being marked uninteresting because v2.6.22 and its ancestors being \n> traversed already.\n\nI don't think that is the case; it tries to name quite a few revs based\non v2.6.22-rc1, but they lose out to existing names given when\ntraversing from v2.6.22.\n\n-Peff\n"},{"id":"51671","messageId":"Pine.LNX.4.64.0708271049000.28586@racer.site","threadId":"9623","inReplyTo":"20070827092422.GA20340@coredump.intra.peff.net","subject":"Re: name-rev does not show the shortest path","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-08-27T09:57:22Z","receivedAt":"2007-08-27T09:57:22Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 27 Aug 2007, Jeff King wrote:\n\n> On Sun, Aug 26, 2007 at 05:38:22PM +0200, Johannes Schindelin wrote:\n> \n> > The old code _should_ have worked; it is more likely that your \n> > different metric just hides the bug.  The old metric tried to favour \n> > less merge traversals over more traversals, but at the same time, it \n> > favoured smaller numbers over larger ones (but as you found out, only \n> > in the last component).\n> \n> Right, the problem is that we have effectively _thrown away_ the\n> \"smaller numbers over larger ones\" information for components other than\n> the last.\n\nYou're right.  I misremembered name-rev to use a fifo instead of stupid \nrecursion.\n\nWill fix.\n\nCiao,\nDscho\n"},{"id":"51686","messageId":"Pine.LNX.4.64.0708271216330.28586@racer.site","threadId":"9623","inReplyTo":"Pine.LNX.4.64.0708271049000.28586@racer.site","subject":"Re: name-rev does not show the shortest path","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-08-27T11:18:13Z","receivedAt":"2007-08-27T11:18:13Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 27 Aug 2007, Johannes Schindelin wrote:\n\n> On Mon, 27 Aug 2007, Jeff King wrote:\n> \n> > On Sun, Aug 26, 2007 at 05:38:22PM +0200, Johannes Schindelin wrote:\n> > \n> > > The old code _should_ have worked; it is more likely that your \n> > > different metric just hides the bug.  The old metric tried to favour \n> > > less merge traversals over more traversals, but at the same time, it \n> > > favoured smaller numbers over larger ones (but as you found out, only \n> > > in the last component).\n> > \n> > Right, the problem is that we have effectively _thrown away_ the\n> > \"smaller numbers over larger ones\" information for components other than\n> > the last.\n> \n> You're right.  I misremembered name-rev to use a fifo instead of stupid \n> recursion.\n> \n> Will fix.\n\nSeems that this is not really good (having a fifo):\n\n-- snip --\n builtin-name-rev.c |  108 +++++++++++++++++++++++++++++++---------------------\n 1 files changed, 65 insertions(+), 43 deletions(-)\n\ndiff --git a/builtin-name-rev.c b/builtin-name-rev.c\nindex 61eba34..e42e436 100644\n--- a/builtin-name-rev.c\n+++ b/builtin-name-rev.c\n@@ -11,19 +11,22 @@ static const char name_rev_usage[] =\n \n typedef struct rev_name {\n \tconst char *tip_name;\n-\tint merge_traversals;\n \tint generation;\n } rev_name;\n \n static long cutoff = LONG_MAX;\n \n+/* The parents of these refs are potentially unnamed */\n+static struct commit_list *rev_queue, *rev_queue_end;\n+\n static void name_rev(struct commit *commit,\n-\t\tconst char *tip_name, int merge_traversals, int generation,\n+\t\tconst char *tip_name, int generation,\n \t\tint deref)\n {\n \tstruct rev_name *name = (struct rev_name *)commit->util;\n-\tstruct commit_list *parents;\n-\tint parent_number = 1;\n+\n+\tif (commit->util)\n+\t\treturn;\n \n \tif (!commit->object.parsed)\n \t\tparse_commit(commit);\n@@ -41,46 +44,20 @@ 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(rev_name));\n-\t\tcommit->util = name;\n-\t\tgoto copy_data;\n-\t} else if (name->merge_traversals > merge_traversals ||\n-\t\t\t(name->merge_traversals == merge_traversals &&\n-\t\t\t name->generation > generation)) {\n-copy_data:\n-\t\tname->tip_name = tip_name;\n-\t\tname->merge_traversals = merge_traversals;\n-\t\tname->generation = generation;\n-\t} else\n-\t\treturn;\n-\n-\tfor (parents = commit->parents;\n-\t\t\tparents;\n-\t\t\tparents = 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-\t\t\t\t1 + decimal_length(generation) +  /* ~<n> */\n-\t\t\t\t1 + 2 +\t\t\t\t  /* ^NN */\n-\t\t\t\t1);\n+\tname = xmalloc(sizeof(rev_name));\n+\tcommit->util = name;\n+\tname->tip_name = tip_name;\n+\tname->generation = generation;\n \n-\t\t\tif (len > 2 && !strcmp(tip_name + len - 2, \"^0\"))\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\telse\n-\t\t\t\tsprintf(new_name, \"%.*s^%d\", len, tip_name,\n-\t\t\t\t\t\tparent_number);\n+\tif (rev_queue_end)\n+\t\trev_queue_end = rev_queue_end->next =\n+\t\t\txmalloc(sizeof(struct commit_list));\n+\telse\n+\t\trev_queue = rev_queue_end =\n+\t\t\txmalloc(sizeof(struct commit_list));\n \n-\t\t\tname_rev(parents->item, new_name,\n-\t\t\t\tmerge_traversals + 1 , 0, 0);\n-\t\t} else {\n-\t\t\tname_rev(parents->item, tip_name, merge_traversals,\n-\t\t\t\tgeneration + 1, 0);\n-\t\t}\n-\t}\n+\trev_queue_end->item = commit;\n+\trev_queue_end->next = NULL;\n }\n \n struct name_ref_data {\n@@ -120,11 +97,46 @@ static int name_ref(const char *path, const unsigned char *sha1, int flags, void\n \t\telse if (!prefixcmp(path, \"refs/\"))\n \t\t\tpath = path + 5;\n \n-\t\tname_rev(commit, xstrdup(path), 0, 0, deref);\n+\t\tname_rev(commit, xstrdup(path), 0, deref);\n \t}\n \treturn 0;\n }\n \n+static void name_parents(struct commit *commit)\n+{\n+\tstruct rev_name *n = commit->util;\n+\tint parent_number = 1;\n+\tstruct commit_list *parents;\n+\n+\tif (!n)\n+\t\tdie(\"Huh?\");\n+\tfor (parents = commit->parents;\n+\t\t\tparents;\n+\t\t\tparents = parents->next, parent_number++) {\n+\t\tif (parent_number > 1) {\n+\t\t\tint len = strlen(n->tip_name);\n+\t\t\tchar *new_name = xmalloc(len +\n+\t\t\t\t1 + decimal_length(n->generation) +  /* ~<n> */\n+\t\t\t\t1 + 2 +\t\t\t\t     /* ^NN */\n+\t\t\t\t1);\n+\n+\t\t\tif (len > 2 && !strcmp(n->tip_name + len - 2, \"^0\"))\n+\t\t\t\tlen -= 2;\n+\t\t\tif (n->generation > 0)\n+\t\t\t\tsprintf(new_name, \"%.*s~%d^%d\", len,\n+\t\t\t\t\t\tn->tip_name, n->generation,\n+\t\t\t\t\t\tparent_number);\n+\t\t\telse\n+\t\t\t\tsprintf(new_name, \"%.*s^%d\", len,\n+\t\t\t\t\t\tn->tip_name, parent_number);\n+\n+\t\t\tname_rev(parents->item, new_name, 0, 0);\n+\t\t} else\n+\t\t\tname_rev(parents->item, n->tip_name,\n+\t\t\t\t\tn->generation + 1, 0);\n+\t}\n+}\n+\n /* returns a static buffer */\n static const char* get_rev_name(struct object *o)\n {\n@@ -135,6 +147,16 @@ static const char* get_rev_name(struct object *o)\n \tif (o->type != OBJ_COMMIT)\n \t\treturn \"undefined\";\n \tc = (struct commit *) o;\n+\twhile (c->util == NULL) {\n+\t\tstruct commit_list *current = rev_queue;\n+\n+\t\tname_parents(current->item);\n+\t\trev_queue = current->next;\n+\t\tif (!rev_queue)\n+\t\t\trev_queue_end = NULL;\n+\t\tfree(current);\n+\t}\n+\n \tn = c->util;\n \tif (!n)\n \t\treturn \"undefined\";\n-- snap --\n\nIt outputs this:\n\ngit name-rev --tags 0567a0c022d5b343370a343121f38fd89925de55\n0567a0c[...] tags/v2.6.22-rc1~1^2^2^2~11^2~13^2~8^2~1^3~5\n\nNot really nice.\n\nCiao,\nDscho\n"},{"id":"51689","messageId":"Pine.LNX.4.64.0708231557590.20400@racer.site","threadId":"9623","inReplyTo":"20070823103817.GF6573@informatik.uni-freiburg.de","subject":"[PATCH] name-rev: Fix non-shortest description","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-08-27T11:37:33Z","receivedAt":"2007-08-27T11:37:33Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nUwe Kleine-König noticed that under certain circumstances, name-rev\npicked a non-optimal tag.  Jeff King analyzed that name-rev only\ntakes into account the number of merge traversals, and then the\n_last_ number in the description.\n\nAs an easy way to fix it, use a weighting factor for merge traversals:\nA merge traversal is now made 65535 times more expensive than a\nfirst-parent traversal.\n\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n---\n\n\tOn Thu, 23 Aug 2007, Uwe Kleine-K?nig wrote:\n\n\t> I want to check to which kernel version I need to upgrade to get \n\t> a certain feature.  For my case it was introduced in \n\t> 0567a0c022d5b.\n\t> \n\t> zeisberg@cassiopeia:~/gsrc/linux-2.6$ \n\t> \trev=0567a0c022d5b343370a343121f38fd89925de55\n\t> \n\t> zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev\n\t> 0567a0c02[...] tags/v2.6.22~1686^2~1^3~5\n\t> \n\t> zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev\n\t> 0567a0c02[...] tags/v2.6.22-rc1~1009^2~1^3~5\n\n\tThis fixes it.\n\n builtin-name-rev.c |   21 +++++++++++----------\n 1 files changed, 11 insertions(+), 10 deletions(-)\n\ndiff --git a/builtin-name-rev.c b/builtin-name-rev.c\nindex 61eba34..03083e9 100644\n--- a/builtin-name-rev.c\n+++ b/builtin-name-rev.c\n@@ -11,14 +11,17 @@ static const char name_rev_usage[] =\n \n typedef struct rev_name {\n \tconst char *tip_name;\n-\tint merge_traversals;\n \tint generation;\n+\tint distance;\n } rev_name;\n \n static long cutoff = LONG_MAX;\n \n+/* How many generations are maximally preferred over _one_ merge traversal? */\n+#define MERGE_TRAVERSAL_WEIGHT 65535\n+\n static void name_rev(struct commit *commit,\n-\t\tconst char *tip_name, int merge_traversals, int generation,\n+\t\tconst char *tip_name, int generation, int distance,\n \t\tint deref)\n {\n \tstruct rev_name *name = (struct rev_name *)commit->util;\n@@ -45,13 +48,11 @@ static void name_rev(struct commit *commit,\n \t\tname = xmalloc(sizeof(rev_name));\n \t\tcommit->util = name;\n \t\tgoto copy_data;\n-\t} else if (name->merge_traversals > merge_traversals ||\n-\t\t\t(name->merge_traversals == merge_traversals &&\n-\t\t\t name->generation > generation)) {\n+\t} else if (name->distance > distance) {\n copy_data:\n \t\tname->tip_name = tip_name;\n-\t\tname->merge_traversals = merge_traversals;\n \t\tname->generation = generation;\n+\t\tname->distance = distance;\n \t} else\n \t\treturn;\n \n@@ -74,11 +75,11 @@ copy_data:\n \t\t\t\tsprintf(new_name, \"%.*s^%d\", len, tip_name,\n \t\t\t\t\t\tparent_number);\n \n-\t\t\tname_rev(parents->item, new_name,\n-\t\t\t\tmerge_traversals + 1 , 0, 0);\n+\t\t\tname_rev(parents->item, new_name, 0,\n+\t\t\t\tdistance + MERGE_TRAVERSAL_WEIGHT, 0);\n \t\t} else {\n-\t\t\tname_rev(parents->item, tip_name, merge_traversals,\n-\t\t\t\tgeneration + 1, 0);\n+\t\t\tname_rev(parents->item, tip_name, generation + 1,\n+\t\t\t\tdistance + 1, 0);\n \t\t}\n \t}\n }\n-- \n1.5.3.rc6.52.g5113-dirty\n"},{"id":"51742","messageId":"20070827192735.GB20753@informatik.uni-freiburg.de","threadId":"9623","inReplyTo":"Pine.LNX.4.64.0708231557590.20400@racer.site","subject":"Re: [PATCH] name-rev: Fix non-shortest description","fromName":"Uwe Kleine-König","fromEmail":"ukleinek@informatik.uni-freiburg.de","sentAt":"2007-08-27T19:27:35Z","receivedAt":"2007-08-27T19:27:35Z","isPatch":true,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> \n> Uwe Kleine-König noticed that under certain circumstances, name-rev\n> picked a non-optimal tag.  Jeff King analyzed that name-rev only\n> takes into account the number of merge traversals, and then the\n> _last_ number in the description.\n> \n> As an easy way to fix it, use a weighting factor for merge traversals:\n> A merge traversal is now made 65535 times more expensive than a\n> first-parent traversal.\n> \n> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\nJust from looking at the patch it seems to do what the log says.  It\npasses the test suite and fixed my use case.  So:\n\nAcked-by: Uwe Kleine-König <ukleinek@informatik.uni-freiburg.de>\n\nBut if I'd really prefer to know the \"oldest\" tag that includes the\ngiven rev, I don't want that weighting.  I will try to come up with a\npatch that introduces a flag.\n\nBest regards and thanks to Johannes\nUwe\n\n-- \nUwe Kleine-König\n\nprimes where sieve (p:xs) = [ x | x<-xs, x `rem` p /= 0 ]; \\\nprimes = map head (iterate sieve [2..])\n"}]}