{"thread":{"id":"57528","subject":"[PATCH v3] name-rev: use generation numbers if available","startedAt":"2022-03-10T00:06:00Z","lastAt":"2022-03-10T01:32:36Z","messageCount":4,"participants":["Jacob Keller","Junio C Hamano","Keller, Jacob E"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"450960","messageId":"20220310000550.2368737-1-jacob.e.keller@intel.com","threadId":"57528","inReplyTo":null,"subject":"[PATCH v3] name-rev: use generation numbers if available","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2022-03-10T00:05:50Z","receivedAt":"2022-03-10T00:06:00Z","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 might not properly name the\ncommit.\n\nThis occurs because name-rev uses a heuristic of the commit date to\navoid searching down tags which lead to commits that are older than the\nnamed commit. This is intended to avoid work on larger repositories.\n\nThis heuristic impacts git name-rev, and by extension git describe\n--contains which is built on top of name-rev.\n\nFurther more, if --all or --annotate-stdin is used, the heuristic is not\nenabled because the full history has to be analyzed anyways. This\nresults in some confusion if a user sees that --annotate-stdin works but\na normal name-rev does not.\n\nIf the repository has a commit graph, we can use the generation numbers\ninstead of using the commit dates. This is essentially the same check\nexcept that generation numbers make it exact, where the commit date\nheuristic could be incorrect due to clock errors.\n\nSince we're extending the notion of cutoff to more than one variable,\ncreate a series of functions for setting and checking the cutoff. This\navoids duplication and moves access of the global cutoff and\ngeneration_cutoff to as few functions as possible.\n\nAdd several test cases including a test that covers the new commitGraph\nbehavior, as well as tests for --all and --annotate-stdin with and\nwithout commitGraphs.\n\nSigned-off-by: Jacob Keller <jacob.keller@gmail.com>\n---\nChanges since v2:\n* Removed negative test with commit graph disabled\n\nI wanted to add a test that counted number of revisions walked, but I\ncouldn't figure out if we had a method to get this data out using GIT_TRACE\nor GIT_TRACE2...\n\n builtin/name-rev.c  |  71 +++++++++++++++++++++------\n t/t6120-describe.sh | 116 ++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 173 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 929591269ddf..c59b5699fe80 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@@ -26,9 +27,58 @@ struct rev_name {\n \n define_commit_slab(commit_rev_name, struct rev_name);\n \n+static timestamp_t generation_cutoff = GENERATION_NUMBER_INFINITY;\n static timestamp_t cutoff = TIME_MAX;\n static struct commit_rev_name rev_names;\n \n+/* Disable the cutoff checks entirely */\n+static void disable_cutoff(void)\n+{\n+\tgeneration_cutoff = 0;\n+\tcutoff = 0;\n+}\n+\n+/* Cutoff searching any commits older than this one */\n+static void set_commit_cutoff(struct commit *commit)\n+{\n+\n+\tif (cutoff > commit->date)\n+\t\tcutoff = commit->date;\n+\n+\tif (generation_cutoff) {\n+\t\ttimestamp_t generation = commit_graph_generation(commit);\n+\n+\t\tif (generation_cutoff > generation)\n+\t\t\tgeneration_cutoff = generation;\n+\t}\n+}\n+\n+/* adjust the commit date cutoff with a slop to allow for slightly incorrect\n+ * commit timestamps in case of clock skew.\n+ */\n+static void adjust_cutoff_timestamp_for_slop(void)\n+{\n+\tif (cutoff) {\n+\t\t/* check for undeflow */\n+\t\tif (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)\n+\t\t\tcutoff = cutoff - CUTOFF_DATE_SLOP;\n+\t\telse\n+\t\t\tcutoff = TIME_MIN;\n+\t}\n+}\n+\n+/* Check if a commit is before the cutoff. Prioritize generation numbers\n+ * first, but use the commit timestamp if we lack generation data.\n+ */\n+static int commit_is_before_cutoff(struct commit *commit)\n+{\n+\tif (generation_cutoff < GENERATION_NUMBER_INFINITY)\n+\t\treturn generation_cutoff &&\n+\t\t\tcommit_graph_generation(commit) < generation_cutoff;\n+\n+\treturn commit->date < cutoff;\n+}\n+\n /* How many generations are maximally preferred over _one_ merge traversal? */\n #define MERGE_TRAVERSAL_WEIGHT 65535\n \n@@ -151,7 +201,7 @@ 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 (commit_is_before_cutoff(start_commit))\n \t\treturn;\n \n \tstart_name = create_or_update_name(start_commit, taggerdate, 0, 0,\n@@ -181,7 +231,7 @@ static void name_rev(struct commit *start_commit,\n \t\t\tint generation, distance;\n \n \t\t\tparse_commit(parent);\n-\t\t\tif (parent->date < cutoff)\n+\t\t\tif (commit_is_before_cutoff(parent))\n \t\t\t\tcontinue;\n \n \t\t\tif (parent_number > 1) {\n@@ -568,7 +618,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\tusage_with_options(name_rev_usage, opts);\n \t}\n \tif (all || annotate_stdin)\n-\t\tcutoff = 0;\n+\t\tdisable_cutoff();\n \n \tfor (; argc; argc--, argv++) {\n \t\tstruct object_id oid;\n@@ -596,10 +646,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\t\tcontinue;\n \t\t}\n \n-\t\tif (commit) {\n-\t\t\tif (cutoff > commit->date)\n-\t\t\t\tcutoff = commit->date;\n-\t\t}\n+\t\tif (commit)\n+\t\t\tset_commit_cutoff(commit);\n \n \t\tif (peel_tag) {\n \t\t\tif (!commit) {\n@@ -612,13 +660,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\tadd_object_array(object, *argv, &revs);\n \t}\n \n-\tif (cutoff) {\n-\t\t/* check for undeflow */\n-\t\tif (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)\n-\t\t\tcutoff = cutoff - CUTOFF_DATE_SLOP;\n-\t\telse\n-\t\t\tcutoff = TIME_MIN;\n-\t}\n+\tadjust_cutoff_timestamp_for_slop();\n+\n \tfor_each_ref(name_ref, &data);\n \tname_tips();\n \ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 9781b92aeddf..0b18f737794b 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -488,6 +488,122 @@ 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+\tUNIX_EPOCH_ZERO=\"@0 +0000\" &&\n+\tgit init non-monotonic &&\n+\ttest_commit -C non-monotonic A &&\n+\ttest_commit -C non-monotonic --no-tag B &&\n+\ttest_commit -C non-monotonic --no-tag --date \"$UNIX_EPOCH_ZERO\" C &&\n+\ttest_commit -C non-monotonic D &&\n+\ttest_commit -C non-monotonic E\n+'\n+\n+test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '\n+\ttest_config -C non-monotonic core.commitGraph false &&\n+\t(\n+\t\tcd non-monotonic &&\n+\n+\t\techo \"main~3 tags/D~2\" >expect &&\n+\t\tgit name-rev --tags main~3 >actual &&\n+\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'name-rev --all works with non-monotonic timestamps' '\n+\ttest_config -C non-monotonic core.commitGraph false &&\n+\t(\n+\t\tcd non-monotonic &&\n+\n+\t\trm -rf .git/info/commit-graph* &&\n+\n+\t\tcat >tags <<-\\EOF &&\n+\t\ttags/E\n+\t\ttags/D\n+\t\ttags/D~1\n+\t\ttags/D~2\n+\t\ttags/A\n+\t\tEOF\n+\n+\t\tgit log --pretty=%H >revs &&\n+\n+\t\tpaste -d\" \" revs tags | sort >expect &&\n+\n+\t\tgit name-rev --tags --all | sort >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'name-rev --annotate-stdin works with non-monotonic timestamps' '\n+\ttest_config -C non-monotonic core.commitGraph false &&\n+\t(\n+\t\tcd non-monotonic &&\n+\n+\t\trm -rf .git/info/commit-graph* &&\n+\n+\t\tcat >expect <<-\\EOF &&\n+\t\tE\n+\t\tD\n+\t\tD~1\n+\t\tD~2\n+\t\tA\n+\t\tEOF\n+\n+\t\tgit log --pretty=%H >revs &&\n+\t\tgit name-rev --tags --annotate-stdin --name-only <revs >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'name-rev --all works with commitGraph' '\n+\ttest_config -C non-monotonic core.commitGraph true &&\n+\t(\n+\t\tcd non-monotonic &&\n+\n+\t\tgit commit-graph write --reachable &&\n+\n+\t\tcat >tags <<-\\EOF &&\n+\t\ttags/E\n+\t\ttags/D\n+\t\ttags/D~1\n+\t\ttags/D~2\n+\t\ttags/A\n+\t\tEOF\n+\n+\t\tgit log --pretty=%H >revs &&\n+\n+\t\tpaste -d\" \" revs tags | sort >expect &&\n+\n+\t\tgit name-rev --tags --all | sort >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'name-rev --annotate-stdin works with commitGraph' '\n+\ttest_config -C non-monotonic core.commitGraph true &&\n+\t(\n+\t\tcd non-monotonic &&\n+\n+\t\tgit commit-graph write --reachable &&\n+\n+\t\tcat >expect <<-\\EOF &&\n+\t\tE\n+\t\tD\n+\t\tD~1\n+\t\tD~2\n+\t\tA\n+\t\tEOF\n+\n+\t\tgit log --pretty=%H >revs &&\n+\t\tgit name-rev --tags --annotate-stdin --name-only <revs >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n #               B\n #               o\n #                \\\n\nbase-commit: c2162907e9aa884bdb70208389cb99b181620d51\n-- \n2.35.1.355.ge7e302376dd6\n\n"},{"id":"450963","messageId":"xmqqilsmir41.fsf@gitster.g","threadId":"57528","inReplyTo":"20220310000550.2368737-1-jacob.e.keller@intel.com","subject":"Re: [PATCH v3] name-rev: use generation numbers if available","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-03-10T00:33:02Z","receivedAt":"2022-03-10T00:33:10Z","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> +# 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> +\tUNIX_EPOCH_ZERO=\"@0 +0000\" &&\n> +\tgit init non-monotonic &&\n> +\ttest_commit -C non-monotonic A &&\n> +\ttest_commit -C non-monotonic --no-tag B &&\n> +\ttest_commit -C non-monotonic --no-tag --date \"$UNIX_EPOCH_ZERO\" C &&\n> +\ttest_commit -C non-monotonic D &&\n> +\ttest_commit -C non-monotonic E\n> +'\n> +\n> +test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '\n> +\ttest_config -C non-monotonic core.commitGraph false &&\n\nDon't you mean \"true\" here?\n\n> +\t(\n> +\t\tcd non-monotonic &&\n> +\n> +\t\techo \"main~3 tags/D~2\" >expect &&\n> +\t\tgit name-rev --tags main~3 >actual &&\n> +\n> +\t\ttest_cmp expect actual\n> +\t)\n> +'\n\nOther than that there wasn't anything unexpected in this iteration.\n\nThanks.\n\n"},{"id":"450973","messageId":"CO1PR11MB5089439F5FBB755C67049AC5D60B9@CO1PR11MB5089.namprd11.prod.outlook.com","threadId":"57528","inReplyTo":"xmqqilsmir41.fsf@gitster.g","subject":"RE: [PATCH v3] name-rev: use generation numbers if available","fromName":"Keller, Jacob E","fromEmail":"jacob.e.keller@intel.com","sentAt":"2022-03-10T01:25:25Z","receivedAt":"2022-03-10T01:25:51Z","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: Junio C Hamano <gitster@pobox.com>\n> Sent: Wednesday, March 09, 2022 4:33 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 v3] name-rev: use generation numbers if available\n> \n> Jacob Keller <jacob.e.keller@intel.com> writes:\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> > +\tUNIX_EPOCH_ZERO=\"@0 +0000\" &&\n> > +\tgit init non-monotonic &&\n> > +\ttest_commit -C non-monotonic A &&\n> > +\ttest_commit -C non-monotonic --no-tag B &&\n> > +\ttest_commit -C non-monotonic --no-tag --date \"$UNIX_EPOCH_ZERO\" C\n> &&\n> > +\ttest_commit -C non-monotonic D &&\n> > +\ttest_commit -C non-monotonic E\n> > +'\n> > +\n> > +test_expect_success 'name-rev with commitGraph handles non-monotonic\n> timestamps' '\n> > +\ttest_config -C non-monotonic core.commitGraph false &&\n> \n> Don't you mean \"true\" here?\n> \n\nYep. Will fix.\n\n> > +\t(\n> > +\t\tcd non-monotonic &&\n> > +\n> > +\t\techo \"main~3 tags/D~2\" >expect &&\n> > +\t\tgit name-rev --tags main~3 >actual &&\n> > +\n> > +\t\ttest_cmp expect actual\n> > +\t)\n> > +'\n> \n> Other than that there wasn't anything unexpected in this iteration.\n> \n> Thanks.\n\n"},{"id":"450975","messageId":"xmqqa6dyiocy.fsf@gitster.g","threadId":"57528","inReplyTo":"xmqqilsmir41.fsf@gitster.g","subject":"Re: [PATCH v3] name-rev: use generation numbers if available","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-03-10T01:32:29Z","receivedAt":"2022-03-10T01:32:36Z","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>> +test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '\n>> +\ttest_config -C non-monotonic core.commitGraph false &&\n>\n> Don't you mean \"true\" here?\n>\n>> +\t(\n>> +\t\tcd non-monotonic &&\n>> +\n>> +\t\techo \"main~3 tags/D~2\" >expect &&\n>> +\t\tgit name-rev --tags main~3 >actual &&\n>> +\n>> +\t\ttest_cmp expect actual\n>> +\t)\n>> +'\n\nAnd I am not sure if there is anybody _writing_ the graph file in\nthe first place, so perhaps squash this in?\n\n t/t6120-describe.sh | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 0b18f73779..9a35e783a7 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -503,10 +503,12 @@ test_expect_success 'non-monotonic commit dates setup' '\n '\n \n test_expect_success 'name-rev with commitGraph handles non-monotonic timestamps' '\n-\ttest_config -C non-monotonic core.commitGraph false &&\n+\ttest_config -C non-monotonic core.commitGraph true &&\n \t(\n \t\tcd non-monotonic &&\n \n+\t\tgit commit-graph write --reachable &&\n+\n \t\techo \"main~3 tags/D~2\" >expect &&\n \t\tgit name-rev --tags main~3 >actual &&\n \n-- \n2.35.1-744-g1f8f0331bc\n\n"}]}