{"thread":{"id":"46673","subject":"git describe and \"the smallest number of commits possible\"","startedAt":"2017-08-26T14:47:39Z","lastAt":"2017-08-29T13:34:22Z","messageCount":3,"participants":["Kévin Le Gouguec","Stefan Beller","Michael J Gruber"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"327245","messageId":"CAOAAw7WsiwzQYhiU9xxcoteaEWgaXRQkiVb0Xa2WckR4=m-bFw@mail.gmail.com","threadId":"46673","inReplyTo":null,"subject":"git describe and \"the smallest number of commits possible\"","fromName":"Kévin Le Gouguec","fromEmail":"kevin.legouguec@gmail.com","sentAt":"2017-08-26T14:47:17Z","receivedAt":"2017-08-26T14:47:39Z","isPatch":false,"sender":{"key":"kevin.legouguec@gmail.com","avatar":null},"body":"Hi,\n\nI've asked this question on the git-users Google Groups list[1], and\nwhile the answers there were interesting, I still cannot figure\nwhether my problem comes from an actual bug, a misleading manpage, my\ninability to understand the code and/or the manpage, or a combination\nof the three.\n\nI noticed this problem on 2.1.4 (Debian oldstable); I can reproduce it\non next (7ef03bb281b2220d0f2414365e4949beb2337042). Quoting\ngit-describe(1)'s SEARCH STRATEGY section:\n\n> If multiple tags were found during the walk then the tag which has\n> the fewest commits different from the input commit-ish will be\n> selected and output. Here fewest commits different is defined as the\n> number of commits which would be shown by `git log tag..input` will\n> be the smallest number of commits possible.\n\nTo put it shortly, after cloning GNU Emacs's repository[2]:\n\n    $ git describe --tags\n    emacs-25.1-129847-gdcc3ef3ee7\n    $ git log --oneline emacs-25.1.. | wc -l\n    5126\n    $ git log --oneline emacs-25.2.. | wc -l\n    4793\n\nIf I am reading it correctly, the manpage suggests that emacs-25.2\nshould be picked in this situation (\"log emacs-25.2..\" shows fewer\ncommits than \"log emacs-25.1..\").\n\nOnce more with --debug:\n\n    $ git describe --debug --tags\n    searching to describe HEAD\n     lightweight   129847 emacs-25.1\n     lightweight     4086 emacs-25.1-rc2\n     lightweight     4126 emacs-25.1-rc1\n     annotated       4185 emacs-25.2\n     annotated       4220 emacs-25.2-rc2\n     lightweight     4226 emacs-25.0.95\n     annotated       4236 emacs-25.2-rc1\n     annotated       4280 emacs-25.1.91\n     lightweight     4305 emacs-25.0.94\n     lightweight     4329 emacs-25.1.90\n    traversed 130257 commits\n    more than 10 tags found; listed 10 most recent\n    gave up search at 5c587fdff164e8b90beb47f6da64b4884290e40a\n    emacs-25.1-129847-gdcc3ef3ee7\n\nI tried to get a sense of what builtin/describe.c is doing (see [1]\nfor some debug printfs); to summarize what I figured:\n\n- When QSORT() is called in describe(), emacs-25.1's depth is smaller\n  than emacs-25.2's.\n\n- finish_depth_computation() updates the best candidate's depth; AFAIU\n  this update's only purpose is to make the displayed suffix more\n  accurate.\n\nThat is all I have right now. I apologize for failing to come up with\na simpler test case (I tried to make toy repositories with a similar\ntopology to reproduce the issue, to no avail). To conclude, as far as\nI can tell, one of the following holds:\n\n- something about this repository[3] causes git-describe(1) to not\n  work as advertised;\n\n- I fail at reading manuals.\n\n\n\n[1]: https://groups.google.com/forum/?fromgroups#!topic/git-users/tSnX-O-3aNI\n\n[2]: https://git.savannah.gnu.org/git/emacs.git\n\n[3]: The project's workflow sounds straightforward:\n\n- development happens mainly on the master branch;\n- the emacs-25 branch receives maintenance fixes and release tags; it\n  is periodically merged back into master;\n- experimental work can happen on scratch branches; these may\n  eventually be merged back into master.\n\nThere are some complications (e.g. pull-induced merges) but if\nI --simplify-by-decoration I find that the repository's topology\nmatches this description.\n"},{"id":"327286","messageId":"CAGZ79kZSmJBnfcU=WWmq3VEHJBJLQJzzri07hSU-uA-VgT0t3Q@mail.gmail.com","threadId":"46673","inReplyTo":"CAOAAw7WsiwzQYhiU9xxcoteaEWgaXRQkiVb0Xa2WckR4=m-bFw@mail.gmail.com","subject":"Re: git describe and \"the smallest number of commits possible\"","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-08-28T18:24:19Z","receivedAt":"2017-08-28T18:24:25Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sat, Aug 26, 2017 at 7:47 AM, Kévin Le Gouguec\n<kevin.legouguec@gmail.com> wrote:\n> Hi,\n>\n> I've asked this question on the git-users Google Groups list[1], and\n> while the answers there were interesting, I still cannot figure\n> whether my problem comes from an actual bug, a misleading manpage, my\n> inability to understand the code and/or the manpage, or a combination\n> of the three.\n>\n> I noticed this problem on 2.1.4 (Debian oldstable); I can reproduce it\n> on next (7ef03bb281b2220d0f2414365e4949beb2337042). Quoting\n> git-describe(1)'s SEARCH STRATEGY section:\n>\n>> If multiple tags were found during the walk then the tag which has\n>> the fewest commits different from the input commit-ish will be\n>> selected and output. Here fewest commits different is defined as the\n>> number of commits which would be shown by `git log tag..input` will\n>> be the smallest number of commits possible.\n\nMaybe relevant\nhttps://public-inbox.org/git/20160421113004.GA3140@aepfle.de/\n(specifically the discussion after this patch, it sheds light on the\nheuristics used, though your case here doesn't use these heuristics)\n"},{"id":"327321","messageId":"f90ddec3-1bef-0b2f-b98b-e65247655b8a@grubix.eu","threadId":"46673","inReplyTo":"CAGZ79kZSmJBnfcU=WWmq3VEHJBJLQJzzri07hSU-uA-VgT0t3Q@mail.gmail.com","subject":"Re: git describe and \"the smallest number of commits possible\"","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-08-29T13:34:09Z","receivedAt":"2017-08-29T13:34:22Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Stefan Beller venit, vidit, dixit 28.08.2017 20:24:\n> On Sat, Aug 26, 2017 at 7:47 AM, Kévin Le Gouguec\n> <kevin.legouguec@gmail.com> wrote:\n>> Hi,\n>>\n>> I've asked this question on the git-users Google Groups list[1], and\n>> while the answers there were interesting, I still cannot figure\n>> whether my problem comes from an actual bug, a misleading manpage, my\n>> inability to understand the code and/or the manpage, or a combination\n>> of the three.\n>>\n>> I noticed this problem on 2.1.4 (Debian oldstable); I can reproduce it\n>> on next (7ef03bb281b2220d0f2414365e4949beb2337042). Quoting\n>> git-describe(1)'s SEARCH STRATEGY section:\n>>\n>>> If multiple tags were found during the walk then the tag which has\n>>> the fewest commits different from the input commit-ish will be\n>>> selected and output. Here fewest commits different is defined as the\n>>> number of commits which would be shown by `git log tag..input` will\n>>> be the smallest number of commits possible.\n> \n> Maybe relevant\n> https://public-inbox.org/git/20160421113004.GA3140@aepfle.de/\n> (specifically the discussion after this patch, it sheds light on the\n> heuristics used, though your case here doesn't use these heuristics)\n\ngit describe is driving my crazy sometimes, too - both the results and\nthe code ;)\n\n[long read with lot's of debug output follows, sorry]\n\nWhat is going on here is the following:\ngit describe --tags decides based on \"depth\".\n\ngit tag --merged dcc3ef3ee7 lists both emacs-25.1 and emac-25.2 (among\nmany others).\n\ngit rev-list --count emacs-25.1..dcc3ef3ee7\n5126\n\ngit rev-list --count emacs-25.2..dcc3ef3ee7\n\n4793\n\nSo, you would rightly expect 25.2 to be preferred over 25.1.\n\nNow, \"git describe\" does not do a \"rev-list --count\" for each tag but,\ninstead, walks back from dcc3ef3ee7 and notes when it reaches a tagged\ncommit, and how many steps it takes to get there. The information\n\"reachable by the i-th tag that I encountered\" is kept by a field of\nwidth 27, which limits the --candidates values. Once the walk passes\nmore tags it is aborted.\n\nThen the possible matches are sorted.\n\nThen the depth calculation is finished.\n\nFunny order of actions, isn't it? Smells like BUG.\nAt least it makes the debug output meaningless.\n\nHere's the debug output before and after finish_depth_calculation():\n\nsearching to describe HEAD\n lightweight     4069 emacs-25.1\n lightweight     4086 emacs-25.1-rc2\n lightweight     4126 emacs-25.1-rc1\n annotated       4185 emacs-25.2\n annotated       4220 emacs-25.2-rc2\n lightweight     4226 emacs-25.0.95\n annotated       4236 emacs-25.2-rc1\n annotated       4280 emacs-25.1.91\n lightweight     4305 emacs-25.0.94\n lightweight     4329 emacs-25.1.90\ntraversed 4462 commits\nmore than 10 tags found; listed 10 most recent\ngave up search at 5c587fdff164e8b90beb47f6da64b4884290e40a\n[finish_depth_calculation()]\n lightweight   129847 emacs-25.1\n lightweight     4086 emacs-25.1-rc2\n lightweight     4126 emacs-25.1-rc1\n annotated       4185 emacs-25.2\n annotated       4220 emacs-25.2-rc2\n lightweight     4226 emacs-25.0.95\n annotated       4236 emacs-25.2-rc1\n annotated       4280 emacs-25.1.91\n lightweight     4305 emacs-25.0.94\n lightweight     4329 emacs-25.1.90\ntraversed 130257 commits\nmore than 10 tags found; listed 10 most recent\ngave up search at 5c587fdff164e8b90beb47f6da64b4884290e40a\nemacs-25.1-129847-gdcc3ef3ee7\n\nNow, I can't claim that I can wrap my head around\nfinish_depth_calculation() and the way depth is calculated here, let\nalone those huge numbers (probably per not-contained tag or so), but\nthat order of operations is clearly wrong.\n\nNow, if we fix finish_depth_calculation() to actually do the work for\nall possible candidates, and the sort afterwards, the result is:\n\nLANG=C devgit describe --tags --debug --candidates=10\nsearching to describe HEAD\n lightweight   129847 emacs-25.1\n lightweight   129864 emacs-25.1-rc2\n lightweight   129904 emacs-25.1-rc1\n annotated     129981 emacs-25.2\n lightweight   130004 emacs-25.0.95\n annotated     130016 emacs-25.2-rc2\n annotated     130032 emacs-25.2-rc1\n annotated     130076 emacs-25.1.91\n lightweight   130083 emacs-25.0.94\n lightweight   130125 emacs-25.1.90\ntraversed 130257 commits\nmore than 10 tags found; listed 10 most recent\ngave up search at 5c587fdff164e8b90beb47f6da64b4884290e40a\nemacs-25.1-129847-gdcc3ef3ee7\n\nLANG=C devgit describe --tags --debug --candidates=100\n\nsearching to describe HEAD\n annotated      13470 emacs-24.5-rc3-fixed\n lightweight    13471 emacs-24.5-rc3\n lightweight    13476 emacs-24.5-rc2\n lightweight    13482 emacs-24.5-rc1\n lightweight    13511 emacs-24.4.91\n lightweight    13554 emacs-24.4.90\n lightweight    13899 emacs-24.4\n lightweight    13902 emacs-24.4-rc1\n lightweight    13959 emacs-24.3.94\n annotated      13972 mh-e-8.6\n lightweight    14049 emacs-24.3.93\n lightweight    14176 emacs-24.3.92\n lightweight   129847 emacs-25.1\n lightweight   129864 emacs-25.1-rc2\n lightweight   129904 emacs-25.1-rc1\n lightweight   129971 emacs-25.0.92\n annotated     129981 emacs-25.2\n lightweight   130004 emacs-25.0.95\n annotated     130016 emacs-25.2-rc2\n annotated     130032 emacs-25.2-rc1\n annotated     130076 emacs-25.1.91\n lightweight   130083 emacs-25.0.94\n lightweight   130099 emacs-25.0.91\n lightweight   130125 emacs-25.1.90\n lightweight   130239 emacs-25.0.93\n lightweight   130255 emacs-25.0.90\ntraversed 130257 commits\nmore than 26 tags found; listed 26 most recent\ngave up search at 96b894717caa773aa6d98ff57385f1c7537e8972\nemacs-24.5-rc3-fixed-13470-gdcc3ef3ee7\n\nAt least the latter kind of makes sense:\ngit rev-list --count emacs-24.5-rc3-fixed..dcc3ef3ee7\n13470\n\nIn short, I think that depth calculation is heavily problematic. First,\ncommit_list_insert_by_date() influences which tags are considered at all.\nSecond, and worse, the code for \"describe cmt\" clearly tries to\ncalculate the number of commits in cmt that are not in t (for each\ncandidate t), which ought to be \"rev-list --count t..cmt\", but fails\nspectacularly.\n\nI kind of suspect the priming of the tag depth on first encounter\n(\"t->depth = seen_commits - 1;\") to be the culprit because that depends\non the way we walk, not the topology, but I wouldn't know how to do better.\n\nMichael\n"}]}