{"thread":{"id":"57413","subject":"[PATCH] name-rev: test showing failure with non-monotonic commit dates","startedAt":"2022-02-14T21:03:13Z","lastAt":"2022-03-09T21:56:53Z","messageCount":10,"participants":["Jacob Keller","Junio C Hamano","Ævar Arnfjörð Bjarmason","Derrick Stolee","Keller, Jacob E","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"448389","messageId":"20220214210136.1532574-1-jacob.e.keller@intel.com","threadId":"57413","inReplyTo":null,"subject":"[PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2022-02-14T21:01:36Z","receivedAt":"2022-02-14T21:03:13Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"From: Jacob Keller <jacob.keller@gmail.com>\n\nIf a commit in a sequence of linear history has a non-monotonically\nincreasing commit timestamp, git name-rev will not properly name the\ncommit.\n\nHowever, if you use --annotate-stdin then the commit does actually get\npicked up and named properly.\n\nAnalyzing the source, it appears to be caused by the cutoff logic which\nis some sort of heuristic which relies on monotonically increasing\ncommit dates.\n\nThis seems like the cutoff using commit date is some sort of heuristic\nwhich reduces the cost of describing something.. but --annotate-stdin\nand --all don't use it.\n\nIn the example setup I could do:\n\necho \"<commit id>\" | git name-rev --annotate-stdin\n\nand get the expected result without the cutoff logic, and it seems at\nleast on small repositories to be as fast as the normal attempt, except\nit produces accurate results.\n\nSigned-off-by: Jacob Keller <jacob.keller@gmail.com>\n---\n t/t6120-describe.sh | 62 +++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 62 insertions(+)\n\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 9781b92aeddf..e9f897e42591 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -488,6 +488,68 @@ test_expect_success 'name-rev covers all conditions while looking at parents' '\n \t)\n '\n \n+# A-B-C-D-E-main\n+#\n+# Where C has a non-monotonically increasing commit timestamp w.r.t. other\n+# commits\n+test_expect_success 'non-monotonic commit dates setup' '\n+\tgit init non-monotonic &&\n+\t(\n+\t\tcd non-monotonic &&\n+\n+\t\techo A >file &&\n+\t\tgit add file &&\n+\t\tGIT_COMMITTER_DATE=\"2020-01-01 18:00\" git commit -m A &&\n+\n+\t\techo B >file &&\n+\t\tgit add file &&\n+\t\tGIT_COMMITTER_DATE=\"2020-01-02 18:00\" git commit -m B &&\n+\n+\t\techo C >file &&\n+\t\tgit add file &&\n+\t\tGIT_COMMITTER_DATE=\"2005-01-01 18:00\" git commit -m C &&\n+\n+\t\techo D >file &&\n+\t\tgit add file &&\n+\t\tGIT_COMMITTER_DATE=\"2020-01-04 18:00\" git commit -m D &&\n+\n+\t\techo E >file &&\n+\t\tgit add file &&\n+\t\tGIT_COMMITTER_DATE=\"2020-01-05 18:00\" git commit -m E\n+\t)\n+'\n+\n+test_expect_failure 'name-rev commit timestamp prevents naming commits' '\n+\t(\n+\t\tcd non-monotonic &&\n+\n+\t\tB=$(git rev-parse main~3) &&\n+\n+\t\techo \"$B main~3\" >expect &&\n+\t\tgit name-rev $B >actual &&\n+\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'name-rev --all works with non-monotonic' '\n+\t(\n+\t\tcd non-monotonic &&\n+\n+\t\tcat >expect <<EOF &&\n+main\n+main~1\n+main~2\n+main~3\n+main~4\n+EOF\n+\n+\t\tgit log --pretty=%H | git name-rev --annotate-stdin --name-only >actual &&\n+\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n #               B\n #               o\n #                \\\n-- \n2.35.1.129.gb80121027d12\n\n"},{"id":"448393","messageId":"xmqqr18515jr.fsf@gitster.g","threadId":"57413","inReplyTo":"20220214210136.1532574-1-jacob.e.keller@intel.com","subject":"Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-02-14T21:50:32Z","receivedAt":"2022-02-14T21:50:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jacob Keller <jacob.e.keller@intel.com> writes:\n\n> From: Jacob Keller <jacob.keller@gmail.com>\n>\n> If a commit in a sequence of linear history has a non-monotonically\n> increasing commit timestamp, git name-rev will not properly name the\n> commit.\n>\n> However, if you use --annotate-stdin then the commit does actually get\n> picked up and named properly.\n\nIIRC, this is to be expected.\n\nWhen preparing to answer --annotate-stdin request, the command has\nto dig down to the root of the history, which would be too expensive\nin some repositories and wants to stop traversal early when it knows\nparticular commits it needs to describe.\n\nDscho?  I think this is pretty much a fundamental part of the\ninitial version added by bd321bcc (Add git-name-rev, 2005-10-26) and\nkept that way to this day, I think.\n\n"},{"id":"448394","messageId":"CA+P7+xrN0zPWfxO1roWzR+MBHntTv8jr9OGdNcN9RPA=ebK24A@mail.gmail.com","threadId":"57413","inReplyTo":"xmqqr18515jr.fsf@gitster.g","subject":"Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2022-02-14T22:07:23Z","receivedAt":"2022-02-14T22:07:36Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Mon, Feb 14, 2022 at 1:50 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Jacob Keller <jacob.e.keller@intel.com> writes:\n>\n> > From: Jacob Keller <jacob.keller@gmail.com>\n> >\n> > If a commit in a sequence of linear history has a non-monotonically\n> > increasing commit timestamp, git name-rev will not properly name the\n> > commit.\n> >\n> > However, if you use --annotate-stdin then the commit does actually get\n> > picked up and named properly.\n>\n> IIRC, this is to be expected.\n>\n\nRight. I figured this is somehow expected behavior...\n\n> When preparing to answer --annotate-stdin request, the command has\n> to dig down to the root of the history, which would be too expensive\n> in some repositories and wants to stop traversal early when it knows\n> particular commits it needs to describe.\n>\n\nAnd this method of cutting the search relies on monotonic commit times right?\n\nIs there any other method we could use (commit graph?) or perhaps to\nadd an option so that you could go \"git name-rev --no-cutoff <commid\nid>\"? That would potentially allow working around this particular\nproblem on repositories where its known to be problematic.\n\nAlternatively is there some other way to apply the cutoff heuristic\nonly in some cases? I get the sense this is intended to allow cutting\noff merged branches? i.e. not applying it when history is linear? I'd\nhave to study it further but the existing algorithm seems to break\nbecause as it goes up the history it has found an \"older\" commit, so\nit stops trying to blame that line...?\n\n> Dscho?  I think this is pretty much a fundamental part of the\n> initial version added by bd321bcc (Add git-name-rev, 2005-10-26) and\n> kept that way to this day, I think.\n>\n\nThe reason we ended up with non-monotonic commit timestamps is a bit\nstrange, and at least going forward I can remove the cause. However\nthe history I deal with already has this, so perhaps a simple\n\"--no-cutoff\" option would be sufficient? This would allow getting the\nequivalent behavior to annotate-stdin without needing to script it\nmyself.\n\nThanks,\nJake\n"},{"id":"448412","messageId":"220215.868rucy4t6.gmgdl@evledraar.gmail.com","threadId":"57413","inReplyTo":"20220214210136.1532574-1-jacob.e.keller@intel.com","subject":"Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-02-15T07:15:58Z","receivedAt":"2022-02-15T07:20:11Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Feb 14 2022, Jacob Keller wrote:\n\n> From: Jacob Keller <jacob.keller@gmail.com>\n>\n> If a commit in a sequence of linear history has a non-monotonically\n> increasing commit timestamp, git name-rev will not properly name the\n> commit.\n>\n> However, if you use --annotate-stdin then the commit does actually get\n> picked up and named properly.\n>\n> Analyzing the source, it appears to be caused by the cutoff logic which\n> is some sort of heuristic which relies on monotonically increasing\n> commit dates.\n>\n> This seems like the cutoff using commit date is some sort of heuristic\n> which reduces the cost of describing something.. but --annotate-stdin\n> and --all don't use it.\n>\n> In the example setup I could do:\n>\n> echo \"<commit id>\" | git name-rev --annotate-stdin\n>\n> and get the expected result without the cutoff logic, and it seems at\n> least on small repositories to be as fast as the normal attempt, except\n> it produces accurate results.\n>\n> Signed-off-by: Jacob Keller <jacob.keller@gmail.com>\n> ---\n>  t/t6120-describe.sh | 62 +++++++++++++++++++++++++++++++++++++++++++++\n>  1 file changed, 62 insertions(+)\n>\n> diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\n> index 9781b92aeddf..e9f897e42591 100755\n> --- a/t/t6120-describe.sh\n> +++ b/t/t6120-describe.sh\n> @@ -488,6 +488,68 @@ test_expect_success 'name-rev covers all conditions while looking at parents' '\n>  \t)\n>  '\n>  \n> +# A-B-C-D-E-main\n> +#\n> +# Where C has a non-monotonically increasing commit timestamp w.r.t. other\n> +# commits\n> +test_expect_success 'non-monotonic commit dates setup' '\n> +\tgit init non-monotonic &&\n> +\t(\n> +\t\tcd non-monotonic &&\n> +\n> +\t\techo A >file &&\n> +\t\tgit add file &&\n> +\t\tGIT_COMMITTER_DATE=\"2020-01-01 18:00\" git commit -m A &&\n> +\n> +\t\techo B >file &&\n> +\t\tgit add file &&\n> +\t\tGIT_COMMITTER_DATE=\"2020-01-02 18:00\" git commit -m B &&\n> +\n> +\t\techo C >file &&\n> +\t\tgit add file &&\n> +\t\tGIT_COMMITTER_DATE=\"2005-01-01 18:00\" git commit -m C &&\n> +\n> +\t\techo D >file &&\n> +\t\tgit add file &&\n> +\t\tGIT_COMMITTER_DATE=\"2020-01-04 18:00\" git commit -m D &&\n> +\n> +\t\techo E >file &&\n> +\t\tgit add file &&\n> +\t\tGIT_COMMITTER_DATE=\"2020-01-05 18:00\" git commit -m E\n> +\t)\n\nShorter & avoids the needless subshell as:\n\n    git init repo &&\n    test_commit -C repo --date=\"2020-01-01 18:00\" A &&\n    test_commit -C repo --date=\"2020-01-02 18:00\" B &&\n    [...]\n\n\n> +test_expect_failure 'name-rev commit timestamp prevents naming commits' '\n> +\t(\n> +\t\tcd non-monotonic &&\n> +\n> +\t\tB=$(git rev-parse main~3) &&\n> +\n> +\t\techo \"$B main~3\" >expect &&\n> +\t\tgit name-rev $B >actual &&\n> +\n> +\t\ttest_cmp expect actual\n> +\t)\n> +'\n\nI haven't checked, but is the explicit peeling to $B really needed here,\nare the results different with a main~3 or main~3^{commit}?\n\nI.e. the first column of the output will of course be, but will the\nresult on the second column? I suspect not, but haven't run this. In any\ncase I tihnk teh test/commit message could do with an explanation.\n\n> +test_expect_success 'name-rev --all works with non-monotonic' '\n> +\t(\n> +\t\tcd non-monotonic &&\n> +\n> +\t\tcat >expect <<EOF &&\n\nYou can use \"<<-\\EOF\" here so you can indent these:\n\n> +main\n> +main~1\n> +main~2\n> +main~3\n> +main~4\n> +EOF\n> +\n> +\t\tgit log --pretty=%H | git name-rev --annotate-stdin --name-only >actual &&\n\nDon't use \"git\" on the LHS of a pipe, in case it segfaults, so:\n\n    git log [...] >revs &&\n    git name-rev [...] <revs >actual\n\n> +\n> +\t\ttest_cmp expect actual\n> +\t)\n> +'\n> +\n>  #               B\n>  #               o\n>  #                \\\n\n"},{"id":"448428","messageId":"42d2a9fe-a3f2-f841-dcd1-27a0440521b6@github.com","threadId":"57413","inReplyTo":"CA+P7+xrN0zPWfxO1roWzR+MBHntTv8jr9OGdNcN9RPA=ebK24A@mail.gmail.com","subject":"Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-02-15T14:48:38Z","receivedAt":"2022-02-15T14:51:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/14/2022 5:07 PM, Jacob Keller wrote:\n> On Mon, Feb 14, 2022 at 1:50 PM Junio C Hamano <gitster@pobox.com> wrote:\n>>\n>> Jacob Keller <jacob.e.keller@intel.com> writes:\n>>\n>>> From: Jacob Keller <jacob.keller@gmail.com>\n>>>\n>>> If a commit in a sequence of linear history has a non-monotonically\n>>> increasing commit timestamp, git name-rev will not properly name the\n>>> commit.\n>>>\n>>> However, if you use --annotate-stdin then the commit does actually get\n>>> picked up and named properly.\n>>\n>> IIRC, this is to be expected.\n>>\n> \n> Right. I figured this is somehow expected behavior...\n> \n>> When preparing to answer --annotate-stdin request, the command has\n>> to dig down to the root of the history, which would be too expensive\n>> in some repositories and wants to stop traversal early when it knows\n>> particular commits it needs to describe.\n>>\n> \n> And this method of cutting the search relies on monotonic commit times right?\n> \n> Is there any other method we could use (commit graph?) or perhaps to\n> add an option so that you could go \"git name-rev --no-cutoff <commid\n> id>\"? That would potentially allow working around this particular\n> problem on repositories where its known to be problematic.\n\nI initially thought that generation numbers could help. The usual way\nis to use a priority queue that explores by generation, not commit\ndate. This approach was immediately stifled by these lines:\n\n\tmemset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */\n\tprio_queue_put(&queue, start_commit);\n\nSo the queue is really a stack.\n \n> Alternatively is there some other way to apply the cutoff heuristic\n> only in some cases? I get the sense this is intended to allow cutting\n> off merged branches? i.e. not applying it when history is linear? I'd\n> have to study it further but the existing algorithm seems to break\n> because as it goes up the history it has found an \"older\" commit, so\n> it stops trying to blame that line...?\n\nIt is still possible that the cutoff could be altered to use generation\nnumbers instead of commit dates, but I haven't looked closely enough to\nbe sure.\n\nHere is a very basic attempt. With GIT_TEST_COMMIT_GRAPH=1, your\ntest_expect_failure turns into a success.\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 138e3c30a2b..f7ad1dd8b4d 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -9,6 +9,7 @@\n #include \"prio-queue.h\"\n #include \"hash-lookup.h\"\n #include \"commit-slab.h\"\n+#include \"commit-graph.h\"\n \n /*\n  * One day.  See the 'name a rev shortly after epoch' test in t6120 when\n@@ -27,6 +28,7 @@ struct rev_name {\n define_commit_slab(commit_rev_name, struct rev_name);\n \n static timestamp_t cutoff = TIME_MAX;\n+static timestamp_t generation_cutoff = 0;\n static struct commit_rev_name rev_names;\n \n /* How many generations are maximally preferred over _one_ merge traversal? */\n@@ -151,7 +153,10 @@ static void name_rev(struct commit *start_commit,\n \tstruct rev_name *start_name;\n \n \tparse_commit(start_commit);\n-\tif (start_commit->date < cutoff)\n+\tif (generation_cutoff && generation_cutoff < GENERATION_NUMBER_INFINITY) {\n+\t\tif (commit_graph_generation(start_commit) < generation_cutoff)\n+\t\t\treturn;\n+\t} else if (start_commit->date < cutoff)\n \t\treturn;\n \n \tstart_name = create_or_update_name(start_commit, taggerdate, 0, 0,\n@@ -599,6 +604,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\tif (commit) {\n \t\t\tif (cutoff > commit->date)\n \t\t\t\tcutoff = commit->date;\n+\t\t\tif (generation_cutoff > commit_graph_generation(commit))\n+\t\t\t\tgeneration_cutoff = commit_graph_generation(commit);\n \t\t}\n \n \t\tif (peel_tag) {\n\nThanks,\n-Stolee\n"},{"id":"448499","messageId":"92fe3661-8025-18a7-a9a3-0fce88da522c@intel.com","threadId":"57413","inReplyTo":"42d2a9fe-a3f2-f841-dcd1-27a0440521b6@github.com","subject":"Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Keller, Jacob E","fromEmail":"jacob.e.keller@intel.com","sentAt":"2022-02-15T23:38:41Z","receivedAt":"2022-02-15T23:39:00Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On 2/15/2022 6:48 AM, Derrick Stolee wrote:\n> On 2/14/2022 5:07 PM, Jacob Keller wrote:\n>> On Mon, Feb 14, 2022 at 1:50 PM Junio C Hamano <gitster@pobox.com> wrote:\n>>>\n>>> Jacob Keller <jacob.e.keller@intel.com> writes:\n>>>\n>>>> From: Jacob Keller <jacob.keller@gmail.com>\n>>>>\n>>>> If a commit in a sequence of linear history has a non-monotonically\n>>>> increasing commit timestamp, git name-rev will not properly name the\n>>>> commit.\n>>>>\n>>>> However, if you use --annotate-stdin then the commit does actually get\n>>>> picked up and named properly.\n>>>\n>>> IIRC, this is to be expected.\n>>>\n>>\n>> Right. I figured this is somehow expected behavior...\n>>\n>>> When preparing to answer --annotate-stdin request, the command has\n>>> to dig down to the root of the history, which would be too expensive\n>>> in some repositories and wants to stop traversal early when it knows\n>>> particular commits it needs to describe.\n>>>\n>>\n>> And this method of cutting the search relies on monotonic commit times right?\n>>\n>> Is there any other method we could use (commit graph?) or perhaps to\n>> add an option so that you could go \"git name-rev --no-cutoff <commid\n>> id>\"? That would potentially allow working around this particular\n>> problem on repositories where its known to be problematic.\n> \n> I initially thought that generation numbers could help. The usual way\n> is to use a priority queue that explores by generation, not commit\n> date. This approach was immediately stifled by these lines:\n> \n> \tmemset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */\n> \tprio_queue_put(&queue, start_commit);\n> \n> So the queue is really a stack.\n> \n\nRight. A closer look at the name-rev algorithm seems to be that it\nstarts looking at each tag and scanning down history to see if it can\nfind the given commit. It uses the commit timestamp as a heuristic to\ndecide whether or not to stop looking. This can speed up the search\nbecause it prevents scanning the entire history.. but it breaks when\nthat heuristic is no longer true such as in the particular setup like\nmine with a funky timestamp.\n\n\n>> Alternatively is there some other way to apply the cutoff heuristic\n>> only in some cases? I get the sense this is intended to allow cutting\n>> off merged branches? i.e. not applying it when history is linear? I'd\n>> have to study it further but the existing algorithm seems to break\n>> because as it goes up the history it has found an \"older\" commit, so\n>> it stops trying to blame that line...?\n> \n> It is still possible that the cutoff could be altered to use generation\n> numbers instead of commit dates, but I haven't looked closely enough to\n> be sure.\n> \n\nRight. Using generation number would work for this I think.. The real\nquestion being if it satisfies the other requirements.\n\nI think it does, but I'm not 100% sure yet.\n\n> Here is a very basic attempt. With GIT_TEST_COMMIT_GRAPH=1, your\n> test_expect_failure turns into a success.\n> \n> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> index 138e3c30a2b..f7ad1dd8b4d 100644\n> --- a/builtin/name-rev.c\n> +++ b/builtin/name-rev.c\n> @@ -9,6 +9,7 @@\n>  #include \"prio-queue.h\"\n>  #include \"hash-lookup.h\"\n>  #include \"commit-slab.h\"\n> +#include \"commit-graph.h\"\n>  \n>  /*\n>   * One day.  See the 'name a rev shortly after epoch' test in t6120 when\n> @@ -27,6 +28,7 @@ struct rev_name {\n>  define_commit_slab(commit_rev_name, struct rev_name);\n>  \n>  static timestamp_t cutoff = TIME_MAX;\n> +static timestamp_t generation_cutoff = 0;\n>  static struct commit_rev_name rev_names;\n>  \n>  /* How many generations are maximally preferred over _one_ merge traversal? */\n> @@ -151,7 +153,10 @@ static void name_rev(struct commit *start_commit,\n>  \tstruct rev_name *start_name;\n>  \n>  \tparse_commit(start_commit);\n> -\tif (start_commit->date < cutoff)\n> +\tif (generation_cutoff && generation_cutoff < GENERATION_NUMBER_INFINITY) {\n> +\t\tif (commit_graph_generation(start_commit) < generation_cutoff)\n> +\t\t\treturn;\n> +\t} else if (start_commit->date < cutoff)\n>  \t\treturn;\n>  \n>  \tstart_name = create_or_update_name(start_commit, taggerdate, 0, 0,\n> @@ -599,6 +604,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n>  \t\tif (commit) {\n>  \t\t\tif (cutoff > commit->date)\n>  \t\t\t\tcutoff = commit->date;\n> +\t\t\tif (generation_cutoff > commit_graph_generation(commit))\n> +\t\t\t\tgeneration_cutoff = commit_graph_generation(commit);\n>  \t\t}\n>  \n>  \t\tif (peel_tag) {\n> \n> Thanks,\n> -Stolee\n\n"},{"id":"448513","messageId":"xmqq1r03zl9z.fsf@gitster.g","threadId":"57413","inReplyTo":"42d2a9fe-a3f2-f841-dcd1-27a0440521b6@github.com","subject":"Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-02-16T00:51:20Z","receivedAt":"2022-02-16T00:51:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n> I initially thought that generation numbers could help. The usual way\n> is to use a priority queue that explores by generation, not commit\n> date. This approach was immediately stifled by these lines:\n>\n> \tmemset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */\n> \tprio_queue_put(&queue, start_commit);\n>\n> So the queue is really a stack.\n\nHmph, I am not sure if stifled is a word, but I agree that this one\nis not solvable by \"we have a priority queue that explores by commit\ndate, and using generation numbers instead of commit date will give\nus a more stable result when clock skews are involved\", because the\ntraversal is not the usual \"we pop the newest commit seen so far to\ndig into older history\".\n\nHowever.\n\n> It is still possible that the cutoff could be altered to use generation\n> numbers instead of commit dates, but I haven't looked closely enough to\n> be sure.\n\nIn \"name-rev [--tags] C\", we look for a tag to use in describing the\ngiven commit C as an ancestry path starting at the tag T (e.g. T~4,\nT~2^2).  There can be multiple such tags (e.g. it is likely that a\ncommit that is v1.0~2 is also reachable from tag v2.0, even though\nit would require more hops).  We try to and find a tag that gives\nthe \"simplest\" path.  For that purpose, it is no use to consider any\ntag that is not a descendant of the given commit, because doing an\nancestry traversal starting from such a tag will never reach the\ncommit.  In a world where everybody's clock is in sync, if commit\nwas made at time X, any tag that was made before time X will not be\na descendant of the commit, so we do not add such a tag to the\ncandidate pool.\n\nI think the idea of \"cutoff\" heuristic is exactly what generation\nnumbers can improve, in an imperfect world where there are imperfect\nclocks.\n"},{"id":"448522","messageId":"CO1PR11MB5089008D502F964AF9425F86D6359@CO1PR11MB5089.namprd11.prod.outlook.com","threadId":"57413","inReplyTo":"220215.868rucy4t6.gmgdl@evledraar.gmail.com","subject":"RE: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Keller, Jacob E","fromEmail":"jacob.e.keller@intel.com","sentAt":"2022-02-16T01:16:30Z","receivedAt":"2022-02-16T01:16:39Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"\n\n> -----Original Message-----\n> From: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n> Sent: Monday, February 14, 2022 11:16 PM\n> To: Keller, Jacob E <jacob.e.keller@intel.com>\n> Cc: git@vger.kernel.org; Jacob Keller <jacob.keller@gmail.com>\n> Subject: Re: [PATCH] name-rev: test showing failure with non-monotonic commit\n> dates\n> \n> \n> Shorter & avoids the needless subshell as:\n> \n>     git init repo &&\n>     test_commit -C repo --date=\"2020-01-01 18:00\" A &&\n>     test_commit -C repo --date=\"2020-01-02 18:00\" B &&\n>     [...]\n> \n>\n\nSure. I can pick these improvements up if if we end up actually wanting the test case. I think we're still discussing the core problem in this thread too.\n\n \n> > +test_expect_failure 'name-rev commit timestamp prevents naming commits' '\n> > +\t(\n> > +\t\tcd non-monotonic &&\n> > +\n> > +\t\tB=$(git rev-parse main~3) &&\n> > +\n> > +\t\techo \"$B main~3\" >expect &&\n> > +\t\tgit name-rev $B >actual &&\n> > +\n> > +\t\ttest_cmp expect actual\n> > +\t)\n> > +'\n> \n> I haven't checked, but is the explicit peeling to $B really needed here,\n> are the results different with a main~3 or main~3^{commit}?\n> \n> I.e. the first column of the output will of course be, but will the\n> result on the second column? I suspect not, but haven't run this. In any\n> case I tihnk teh test/commit message could do with an explanation.\n> \n\nThe first column is the commit id, so we need to get that either way to compare the expected and actual output. As far as I know passing \"main~3\" instead of the commit id to name-rev doesn't change this.\n\nThanks,\nJake\n\n"},{"id":"449717","messageId":"CA+P7+xoaHtHMxE_RVBRyhOqVfuP_1s+2NGpGDo_eKfb25_ty7g@mail.gmail.com","threadId":"57413","inReplyTo":"xmqq1r03zl9z.fsf@gitster.g","subject":"Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2022-02-27T22:05:15Z","receivedAt":"2022-02-27T22:05:30Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Tue, Feb 15, 2022 at 4:51 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> In \"name-rev [--tags] C\", we look for a tag to use in describing the\n> given commit C as an ancestry path starting at the tag T (e.g. T~4,\n> T~2^2).  There can be multiple such tags (e.g. it is likely that a\n> commit that is v1.0~2 is also reachable from tag v2.0, even though\n> it would require more hops).  We try to and find a tag that gives\n> the \"simplest\" path.  For that purpose, it is no use to consider any\n> tag that is not a descendant of the given commit, because doing an\n> ancestry traversal starting from such a tag will never reach the\n> commit.  In a world where everybody's clock is in sync, if commit\n> was made at time X, any tag that was made before time X will not be\n> a descendant of the commit, so we do not add such a tag to the\n> candidate pool.\n>\n> I think the idea of \"cutoff\" heuristic is exactly what generation\n> numbers can improve, in an imperfect world where there are imperfect\n> clocks.\n\nYep. I have a patch that will implement this behavior based on\nDerrick's suggestion.\n\nThanks,\nJake\n"},{"id":"450937","messageId":"nycvar.QRO.7.76.6.2203092256070.357@tvgsbejvaqbjf.bet","threadId":"57413","inReplyTo":"xmqqr18515jr.fsf@gitster.g","subject":"Re: [PATCH] name-rev: test showing failure with non-monotonic commit dates","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2022-03-09T21:56:40Z","receivedAt":"2022-03-09T21:56:53Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Mon, 14 Feb 2022, Junio C Hamano wrote:\n\n> Jacob Keller <jacob.e.keller@intel.com> writes:\n>\n> > From: Jacob Keller <jacob.keller@gmail.com>\n> >\n> > If a commit in a sequence of linear history has a non-monotonically\n> > increasing commit timestamp, git name-rev will not properly name the\n> > commit.\n> >\n> > However, if you use --annotate-stdin then the commit does actually get\n> > picked up and named properly.\n>\n> IIRC, this is to be expected.\n>\n> When preparing to answer --annotate-stdin request, the command has\n> to dig down to the root of the history, which would be too expensive\n> in some repositories and wants to stop traversal early when it knows\n> particular commits it needs to describe.\n>\n> Dscho?  I think this is pretty much a fundamental part of the\n> initial version added by bd321bcc (Add git-name-rev, 2005-10-26) and\n> kept that way to this day, I think.\n\nYes, it was.\n\nLooks like Stolee had great suggestions while I did not find time to catch\nup with the mailing list.\n\nCiao,\nDscho\n"}]}