{"thread":{"id":"4760","subject":"[PATCH] Additional merge-base tests","startedAt":"2006-07-04T03:55:26Z","lastAt":"2006-07-05T17:04:55Z","messageCount":26,"participants":["A Large Angry SCM","Junio C Hamano","Johannes Schindelin","Jakub Narebski","Josef Weidendorfer"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"23174","messageId":"44A9E6AE.10508@gmail.com","threadId":"4760","inReplyTo":null,"subject":"[PATCH] Additional merge-base tests","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-07-04T03:55:26Z","receivedAt":"2006-07-04T03:55:26Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Signed-off-by: A Large Angry SCM <gitzilla@gmail.com>\n---\nThis demonstrates a problem with git-merge-base.\n\n t6010-merge-base.sh |   33 +++++++++++++++++++++++++++++++++\n 1 files changed, 33 insertions(+)\n\ndiff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh\nindex 1dce123..9a815bd 100755\n--- a/t/t6010-merge-base.sh\n+++ b/t/t6010-merge-base.sh\n@@ -44,6 +44,31 @@ A=$(doit 1 A $B)\n G=$(doit 7 G $B $E)\n H=$(doit 8 H $A $F)\n \n+# Setup for second test set\n+#\n+#   PL  PR\n+#  /  \\/  \\\n+# L2  C2  R2\n+# |   |   |\n+# L1  C1  R1\n+# |   |   |\n+# L0  C0  R0\n+#   \\ |  /\n+#     S\n+\n+S=$(doit  0 S)\n+C0=$(doit -3 C0 $S)\n+L0=$(doit  2 L0 $S)\n+R0=$(doit  2 R0 $S)\n+C1=$(doit -2 C1 $C0)\n+L1=$(doit  3 L1 $L0)\n+R1=$(doit  3 R1 $R0)\n+C2=$(doit -1 C2 $C1)\n+L2=$(doit  4 L2 $L1)\n+R2=$(doit  4 R2 $R1)\n+PL=$(doit  1 PL $L2 $C2)\n+PR=$(doit  1 PR $C2 $R2)\n+\n test_expect_success 'compute merge-base (single)' \\\n     'MB=$(git-merge-base G H) &&\n      expr \"$(git-name-rev \"$MB\")\" : \"[0-9a-f]* tags/B\"'\n@@ -56,4 +81,12 @@ test_expect_success 'compute merge-base \n     'MB=$(git-show-branch --merge-base G H) &&\n      expr \"$(git-name-rev \"$MB\")\" : \"[0-9a-f]* tags/B\"'\n \n+test_expect_success 'compute merge-base (single)' \\\n+    'MB=$(git-merge-base PL PR) &&\n+     expr \"$(git-name-rev \"$MB\")\" : \"[0-9a-f]* tags/C2\"'\n+\n+test_expect_success 'compute merge-base (all)' \\\n+    'MB=$(git-merge-base --all PL PR) &&\n+     expr \"$(git-name-rev \"$MB\")\" : \"[0-9a-f]* tags/C2\"'\n+\n test_done\n"},{"id":"23182","messageId":"7v3bdhoraa.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"44A9E6AE.10508@gmail.com","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-04T05:47:09Z","receivedAt":"2006-07-04T05:47:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"A Large Angry SCM <gitzilla@gmail.com> writes:\n\n> This demonstrates a problem with git-merge-base.\n>  \n> +# Setup for second test set\n> +#\n> +#   PL  PR\n> +#  /  \\/  \\\n> +# L2  C2  R2\n> +# |   |   |\n> +# L1  C1  R1\n> +# |   |   |\n> +# L0  C0  R0\n> +#   \\ |  /\n> +#     S\n\nCute.\n\nThis is a good demonstration that merge-base may not give you\nminimal set for pathological cases.  If you want to be through\nyou could traverse everything to make sure we do not say 'S' is\nrelevant, but that is quite expensive, so I think there will\nalways be artifacts of horizon effect like this no matter how\nyou try to catch it (didn't I keep saying that already?).\n\nHowever, I do not think it is really a \"problem\".  At least what\n\"merge-base --all\" did not miss any, that should be OK.\n\nI think the practical way to proceed is to say that the test\ncondition should really check that we do not _omit_ C2 in the\nmerge-base --all output.\n"},{"id":"23188","messageId":"44AA0DAE.1060308@gmail.com","threadId":"4760","inReplyTo":"7v3bdhoraa.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Additional merge-base tests","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-07-04T06:41:50Z","receivedAt":"2006-07-04T06:41:50Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Junio C Hamano wrote:\n> A Large Angry SCM <gitzilla@gmail.com> writes:\n> \n>> This demonstrates a problem with git-merge-base.\n>>  \n>> +# Setup for second test set\n>> +#\n>> +#   PL  PR\n>> +#  /  \\/  \\\n>> +# L2  C2  R2\n>> +# |   |   |\n>> +# L1  C1  R1\n>> +# |   |   |\n>> +# L0  C0  R0\n>> +#   \\ |  /\n>> +#     S\n> \n> Cute.\n> \n> This is a good demonstration that merge-base may not give you\n> minimal set for pathological cases.  If you want to be through\n> you could traverse everything to make sure we do not say 'S' is\n> relevant, but that is quite expensive, so I think there will\n> always be artifacts of horizon effect like this no matter how\n> you try to catch it (didn't I keep saying that already?).\n\nNot _that_ pathological in practice, given that you can't really depend \non the timestamps in a distributed SCM.\n\nThe problem is in mark_reachable_commits(); it is either superfluous or \nit needs to parse_commit() those commits that haven't been parsed yet \nthat it needs to traverse.\n\n> However, I do not think it is really a \"problem\".  At least what\n> \"merge-base --all\" did not miss any, that should be OK.\n\nThe degree of the problem is, admittedly, situational.\n\n> I think the practical way to proceed is to say that the test\n> condition should really check that we do not _omit_ C2 in the\n> merge-base --all output.\n\nI do not believe that the (current) code will miss any bases but it can \ncertainly return bases that are reachable from other bases.\n"},{"id":"23192","messageId":"7vd5cln8ji.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"44AA0DAE.1060308@gmail.com","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-04T07:17:21Z","receivedAt":"2006-07-04T07:17:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"A Large Angry SCM <gitzilla@gmail.com> writes:\n\n> Junio C Hamano wrote:\n>> A Large Angry SCM <gitzilla@gmail.com> writes:\n>>\n>>> This demonstrates a problem with git-merge-base.\n>>>  +# Setup for second test set\n>>> +#\n>>> +#   PL  PR\n>>> +#  /  \\/  \\\n>>> +# L2  C2  R2\n>>> +# |   |   |\n>>> +# L1  C1  R1\n>>> +# |   |   |\n>>> +# L0  C0  R0\n>>> +#   \\ |  /\n>>> +#     S\n>>...\n> Not _that_ pathological in practice, given that you can't really\n> depend on the timestamps in a distributed SCM.\n\nAfter I looked at the timestamps you assigned to these sequences\nI fully agree they are not pathological at all.  For each\n\"repository owner\" who makes a single strand of pearls, time\nseems to be flowing monotonically.\n\n   1   1\n  /  \\/  \\\n 4  -1   4\n |   |   |\n 3  -2   3\n |   |   |\n 2  -3   2\n   \\ |  /\n     0\n"},{"id":"23193","messageId":"7vpsgllsnp.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"44AA0DAE.1060308@gmail.com","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-04T07:45:46Z","receivedAt":"2006-07-04T07:45:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"A Large Angry SCM <gitzilla@gmail.com> writes:\n\n>> This is a good demonstration that merge-base may not give you\n>> minimal set for pathological cases.  If you want to be through\n>> you could traverse everything to make sure we do not say 'S' is\n>> relevant, but that is quite expensive, so I think there will\n>> always be artifacts of horizon effect like this no matter how\n>> you try to catch it (didn't I keep saying that already?).\n>\n> The problem is in mark_reachable_commits(); it is either superfluous\n> or it needs to parse_commit() those commits that haven't been parsed\n> yet that it needs to traverse.\n\nYes, you could traverse everything.  But that is not practical.\nWe have known that the clean-up pass has this horizon effect,\nand it is a compromise.\n\nIf you apply this testing patch on top of yours, you will see\nthat parsing more commits at that point makes the clean-up\npass go all the way down to the root commit.\n\nWe may alternatively not use the clean-up pass at all, but I\nsuspect that might give us many false positives.  I don't\nremember the details but I think we added it while fixing\nmerge-base in the real life situation.\n\nIt may be interesting to run tests on real merges (I believe the\nkernel repository has a handful merges that have more than one\nmerge bases) to see how effective the current clean-up pass is.\nIt may turn out to be ineffective in practice, in which case we\ncould kill it off.\n\n\ndiff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh\nindex 9a815bd..4c6ed5c 100755\n--- a/t/t6010-merge-base.sh\n+++ b/t/t6010-merge-base.sh\n@@ -89,4 +89,33 @@ test_expect_success 'compute merge-base \n     'MB=$(git-merge-base --all PL PR) &&\n      expr \"$(git-name-rev \"$MB\")\" : \"[0-9a-f]* tags/C2\"'\n \n+# Setup third set\n+# \n+# S-U0-U1-U2-U3-U4\n+#  \\           X\n+#   D0-D1-D2-D3-D4\n+\n+U0=$(doit 1 U0 $S)\n+D0=$(doit 1 D0 $S)\n+U1=$(doit 2 U1 $U0)\n+D1=$(doit 2 D1 $D0)\n+U2=$(doit 3 U2 $U1)\n+D2=$(doit 3 D2 $D1)\n+U3=$(doit 4 U3 $U2)\n+D3=$(doit 4 D3 $D2)\n+U4=$(doit 5 U4 $U3 $D3)\n+D4=$(doit 5 D4 $D3 $U3)\n+\n+test_expect_success 'compute merge-base' '\n+\n+\tgit merge-base --all U4 D4 >out 2>err \n+\tif grep tags/S err\n+\tthen\n+\t\techo \"went all the way down to S -- very unhappy\"\n+\t\tfalse\n+\telse\n+\t\techo \"stopped before going too far\"\n+\tfi\n+'\n+\n test_done\ndiff --git a/merge-base.c b/merge-base.c\nindex 4856ca0..daab296 100644\n--- a/merge-base.c\n+++ b/merge-base.c\n@@ -6,8 +6,35 @@ #define PARENT1 1\n #define PARENT2 2\n #define UNINTERESTING 4\n \n+static void debug_list(struct commit_list *l, const char *msg)\n+{\n+\tfprintf(stderr, \"%s\\n\", msg);\n+\twhile (l) {\n+\t\tchar buf[1024];\n+\t\tint parsed;\n+\t\tstruct commit *commit = l->item;\n+\t\tl = l->next;\n+\t\tparsed = commit->object.parsed;\n+\n+\t\tif (parsed) {\n+\t\t\tpretty_print_commit(CMIT_FMT_ONELINE, commit,\n+\t\t\t\t\t    ~0UL, buf, sizeof(buf), 7,\n+\t\t\t\t\t    NULL, NULL);\n+\t\t}\n+\t\telse {\n+\t\t\tsprintf(buf, \"git-name-rev %s 1>&2\",\n+\t\t\t\tsha1_to_hex(commit->object.sha1));\n+\t\t\tsystem(buf);\n+\t\t\tstrcpy(buf, sha1_to_hex(commit->object.sha1));\n+\t\t}\n+\t\tfprintf(stderr, \"%d %d %s\\n\", commit->object.flags,\n+\t\t\tparsed, buf);\n+\t}\n+}\n+\n static struct commit *interesting(struct commit_list *list)\n {\n+\tdebug_list(list, \"in interesting()\");\n \twhile (list) {\n \t\tstruct commit *commit = list->item;\n \t\tlist = list->next;\n@@ -134,6 +161,9 @@ static void mark_reachable_commits(struc\n \t/*\n \t * Postprocess to fully contaminate the well.\n \t */\n+\tdebug_list(list, \"list at top of mark-reachable\");\n+\tdebug_list(result, \"result at top of mark-reachable\");\n+\n \tfor (tmp = result; tmp; tmp = tmp->next) {\n \t\tstruct commit *c = tmp->item;\n \t\t/* Reinject uninteresting ones to list,\n@@ -142,10 +172,12 @@ static void mark_reachable_commits(struc\n \t\tif (c->object.flags & UNINTERESTING)\n \t\t\tcommit_list_insert(c, &list);\n \t}\n+\n \twhile (list) {\n \t\tstruct commit *c = list->item;\n \t\tstruct commit_list *parents;\n \n+\t\tdebug_list(list, \"list in mark-reachable postprocessing\");\n \t\ttmp = list;\n \t\tlist = list->next;\n \t\tfree(tmp);\n@@ -155,6 +187,15 @@ static void mark_reachable_commits(struc\n \t\t * parse new ones (we already parsed all the relevant\n \t\t * ones).\n \t\t */\n+\t\t\n+\t\t/* Parsing object here which is a disaster;\n+\t\t * let's demonstrate it.\n+\t\t */\n+#if 1\n+\t\tif (!c->object.parsed)\n+\t\t\tparse_commit(c);\n+#endif\n+\n \t\tparents = c->parents;\n \t\twhile (parents) {\n \t\t\tstruct commit *p = parents->item;\n@@ -164,6 +205,7 @@ static void mark_reachable_commits(struc\n \t\t\t\tcommit_list_insert(p, &list);\n \t\t\t}\n \t\t}\n+\t\tdebug_list(result, \"result in mark-reachable postprocessing\");\n \t}\n }\n \n@@ -196,6 +238,7 @@ static int merge_base(struct commit *rev\n \t\tfree(tmp);\n \t\tif (flags == 3) {\n \t\t\tinsert_by_date(commit, &result);\n+\t\t\tdebug_list(result, \"a new result\");\n \n \t\t\t/* Mark parents of a found merge uninteresting */\n \t\t\tflags |= UNINTERESTING;\n@@ -218,6 +261,7 @@ static int merge_base(struct commit *rev\n \tif (result->next && list)\n \t\tmark_reachable_commits(result, list);\n \n+\tdebug_list(result, \"final result\");\n \twhile (result) {\n \t\tstruct commit *commit = result->item;\n \t\tresult = result->next;\n"},{"id":"23201","messageId":"Pine.LNX.4.63.0607041019580.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4760","inReplyTo":"7vpsgllsnp.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-04T08:23:09Z","receivedAt":"2006-07-04T08:23:09Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Jul 2006, Junio C Hamano wrote:\n\n> A Large Angry SCM <gitzilla@gmail.com> writes:\n> \n> >> This is a good demonstration that merge-base may not give you\n> >> minimal set for pathological cases.  If you want to be through\n> >> you could traverse everything to make sure we do not say 'S' is\n> >> relevant, but that is quite expensive, so I think there will\n> >> always be artifacts of horizon effect like this no matter how\n> >> you try to catch it (didn't I keep saying that already?).\n> >\n> > The problem is in mark_reachable_commits(); it is either superfluous\n> > or it needs to parse_commit() those commits that haven't been parsed\n> > yet that it needs to traverse.\n> \n> Yes, you could traverse everything.  But that is not practical.\n> We have known that the clean-up pass has this horizon effect,\n> and it is a compromise.\n\nWe could introduce a time.maximumSkew variable, and just walk only \nthat much further when traversing the commits.\n\nSo, if you do not trust your clients to have a proper ntp setup, just say \n\"I trust my peers to be off at most 1 day\". That would save lots vs \ntraverse-everything.\n\nCiao,\nDscho\n"},{"id":"23207","messageId":"7vsllhhcxr.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"Pine.LNX.4.63.0607041019580.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-04T10:38:56Z","receivedAt":"2006-07-04T10:38:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> We could introduce a time.maximumSkew variable, and just walk only \n> that much further when traversing the commits.\n>\n> So, if you do not trust your clients to have a proper ntp setup, just say \n> \"I trust my peers to be off at most 1 day\". That would save lots vs \n> traverse-everything.\n\nThe problem ALASCM's example demonstrates does rely on clock\nskews.  The timestamps used in the example looked like this:\n\n\n   1   1\n  /  \\/  \\\n 4  -1   4\n |   |   |\n 3  -2   3\n |   |   |\n 2  -3   2\n   \\ |  /\n     0\n\nThe crucial clock skew the case relies on is that the tip of the\nmiddle branch (-1) is older than the common commit (0).  But the\ntopmost commits with timestamp 1 could be with timestamp 5 to\ncorrect the clock skew and still make the example \"fail\".\n\n   5   5\n  /  \\/  \\\n 4  -1   4\n |   |   |\n 3  -2   3\n |   |   |\n 2  -3   2\n   \\ |  /\n     0\n\nHowever, I am not sure how you are going to use that maximumSkew\nvariable.  The evil owner of the middle branch may have started\nrunning a \"git am\" to commit 4-patch series just when the\nmachine's clock jumped back by 3 seconds, at the pace of 1 patch\na second.  Then he pushes '0' out on \"master\" branch, and the\nthree commits on top of that on \"next\" branch.\n\nTwo days later, two friends build left and right strands of\npearls based on the \"master\" branch of the evil owner of the\nmiddle branch.  Maybe they do that one patch a day.  On the\nfifth day, they both merge the \"next\" branch.\n\nThe point is that it does not require a very large clock skew to\ntrigger this.\n"},{"id":"23212","messageId":"e8dim7$8cm$1@sea.gmane.org","threadId":"4760","inReplyTo":"7vsllhhcxr.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-07-04T11:16:22Z","receivedAt":"2006-07-04T11:16:22Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n\n> The problem ALASCM's example demonstrates does rely on clock\n> skews.  The timestamps used in the example looked like this:\n> \n> \n>    1   1\n>   /  \\/  \\\n>  4  -1   4\n>  |   |   |\n>  3  -2   3\n>  |   |   |\n>  2  -3   2\n>    \\ |  /\n>      0\n> \n> The crucial clock skew the case relies on is that the tip of the\n> middle branch (-1) is older than the common commit (0).  But the\n> topmost commits with timestamp 1 could be with timestamp 5 to\n> correct the clock skew and still make the example \"fail\".\n> \n>    5   5\n>   /  \\/  \\\n>  4  -1   4\n>  |   |   |\n>  3  -2   3\n>  |   |   |\n>  2  -3   2\n>    \\ |  /\n>      0\n\nSo would putting timestamp for merge be MAX(now, parents timestamps)\nsolve the problem?\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"23218","messageId":"Pine.LNX.4.63.0607041334070.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4760","inReplyTo":"e8dim7$8cm$1@sea.gmane.org","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-04T11:35:04Z","receivedAt":"2006-07-04T11:35:04Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Jul 2006, Jakub Narebski wrote:\n\n> Junio C Hamano wrote:\n> \n> \n> > The problem ALASCM's example demonstrates does rely on clock\n> > skews.  The timestamps used in the example looked like this:\n> > \n> > \n> >    1   1\n> >   /  \\/  \\\n> >  4  -1   4\n> >  |   |   |\n> >  3  -2   3\n> >  |   |   |\n> >  2  -3   2\n> >    \\ |  /\n> >      0\n> > \n> > The crucial clock skew the case relies on is that the tip of the\n> > middle branch (-1) is older than the common commit (0).  But the\n> > topmost commits with timestamp 1 could be with timestamp 5 to\n> > correct the clock skew and still make the example \"fail\".\n> > \n> >    5   5\n> >   /  \\/  \\\n> >  4  -1   4\n> >  |   |   |\n> >  3  -2   3\n> >  |   |   |\n> >  2  -3   2\n> >    \\ |  /\n> >      0\n> \n> So would putting timestamp for merge be MAX(now, parents timestamps)\n> solve the problem?\n\nIf there is an evil committer, the parents could have bogus timestamps, \ntoo. But then, I would not pull from such an evil person...\n\nCiao,\nDscho\n"},{"id":"23219","messageId":"Pine.LNX.4.63.0607041336220.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4760","inReplyTo":"7vsllhhcxr.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-04T11:40:13Z","receivedAt":"2006-07-04T11:40:13Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Jul 2006, Junio C Hamano wrote:\n\n> However, I am not sure how you are going to use that maximumSkew\n> variable.\n\nMy idea was to continue traversing the merge base's ancestors, marking \nthem UNINTERESTING, until hitting a commit which is maximumSkew older than \nthe merge base (and not just stop at the merge base, as is the case right \nnow, and neither continue traversing in eternity like suggested).\n\nThis would not help _evil_ cases (i.e. intentional), but most certainly \nyour regular clock skew in a Microsoft network.\n\nCiao,\nDscho\n"},{"id":"23242","messageId":"44AACAAA.1030708@gmail.com","threadId":"4760","inReplyTo":"7vpsgllsnp.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Additional merge-base tests","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-07-04T20:08:10Z","receivedAt":"2006-07-04T20:08:10Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Junio C Hamano wrote:\n> A Large Angry SCM <gitzilla@gmail.com> writes:\n> \n>>> This is a good demonstration that merge-base may not give you\n>>> minimal set for pathological cases.  If you want to be through\n>>> you could traverse everything to make sure we do not say 'S' is\n>>> relevant, but that is quite expensive, so I think there will\n>>> always be artifacts of horizon effect like this no matter how\n>>> you try to catch it (didn't I keep saying that already?).\n>> The problem is in mark_reachable_commits(); it is either superfluous\n>> or it needs to parse_commit() those commits that haven't been parsed\n>> yet that it needs to traverse.\n> \n> Yes, you could traverse everything.  But that is not practical.\n> We have known that the clean-up pass has this horizon effect,\n> and it is a compromise.\n\nThe clean-up pass was devised to eliminate bases that are reachable from \nother bases. It just doesn't look hard enough.\n\n> If you apply this testing patch on top of yours, you will see\n> that parsing more commits at that point makes the clean-up\n> pass go all the way down to the root commit.\n\nYes, I was aware of graphs that would have that behavior.\n\nThe root of the problem is that the heuristic, that attempts to use \ntimestamps to detect that a commit is _not_ reachable from a given \ncommit, relies on the timestamps of commits with a reachability \nrelationship to have a relationship that matches the graph.\n\n> We may alternatively not use the clean-up pass at all, but I\n> suspect that might give us many false positives.  I don't\n> remember the details but I think we added it while fixing\n> merge-base in the real life situation.\n\nThe history of the clean-up pass is that before it was added, \ngit-merge-base was returning a base reachable from another base, and the \nbase returned was, in some significant way, worse for merging. My \nconstruct demonstrates that the clean-up pass only deals with special case.\n\n> It may be interesting to run tests on real merges (I believe the\n> kernel repository has a handful merges that have more than one\n> merge bases) to see how effective the current clean-up pass is.\n> It may turn out to be ineffective in practice, in which case we\n> could kill it off.\n\nAlthough a very important set of repositories to Git, the linux kernel \nrepositories may no longer be representative of the diversity of Git \nuse. Still, it would be interesting to know the outcome.\n"},{"id":"23243","messageId":"44AACD31.70702@gmail.com","threadId":"4760","inReplyTo":"Pine.LNX.4.63.0607041019580.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Additional merge-base tests","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-07-04T20:18:57Z","receivedAt":"2006-07-04T20:18:57Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> Hi,\n> \n> On Tue, 4 Jul 2006, Junio C Hamano wrote:\n> \n>> A Large Angry SCM <gitzilla@gmail.com> writes:\n>>\n>>>> This is a good demonstration that merge-base may not give you\n>>>> minimal set for pathological cases.  If you want to be through\n>>>> you could traverse everything to make sure we do not say 'S' is\n>>>> relevant, but that is quite expensive, so I think there will\n>>>> always be artifacts of horizon effect like this no matter how\n>>>> you try to catch it (didn't I keep saying that already?).\n>>> The problem is in mark_reachable_commits(); it is either superfluous\n>>> or it needs to parse_commit() those commits that haven't been parsed\n>>> yet that it needs to traverse.\n>> Yes, you could traverse everything.  But that is not practical.\n>> We have known that the clean-up pass has this horizon effect,\n>> and it is a compromise.\n> \n> We could introduce a time.maximumSkew variable, and just walk only \n> that much further when traversing the commits.\n> \n> So, if you do not trust your clients to have a proper ntp setup, just say \n> \"I trust my peers to be off at most 1 day\". That would save lots vs \n> traverse-everything.\n\nThe fuzz would only serve to mask, even more, that the heuristic is \nbroken. But, it would also allow the (broken) heuristic to be used _and_ \nlet the user decide how much effort may be used to find the correct bases.\n\nIf this happens, it should be (yet another) user configurable; either, \nper repository, command line, or both.\n"},{"id":"23246","messageId":"7v8xn9gjh5.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"Pine.LNX.4.63.0607041019580.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-04T21:15:18Z","receivedAt":"2006-07-04T21:15:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> We could introduce a time.maximumSkew variable, and just walk only \n> that much further when traversing the commits.\n\nWe could have had \"commit generation number\" in the commit\nobject header, and use that instead of commit timestamps for\nthese traversal purposes.  The generation number for a commit is\ndefined to be max(generation number of its parents)+1 and we\nprime the recursive this definition by defining the generation\nnumber for the root commit to be one.  A moral equivalent\nalternative would be to notice that the commit timestamp we are\ngoing to use to create for a new commit is smaller than one of\nthe commit timestamps of its parent commits and adjust the\ncommit timestamp in such a case by git-commit-tree, perhaps with\na warning.\n\nThese are pretty much water under the bridge by now, for two\nreasons.  One is that I think it is better to make the tools\nthat use get_merge_bases() prepared for the case the function\nincludes suboptimal bases anyway, and the other is once we do\nthat this is not a strong enough justification to modify the\ncommit object format.\n"},{"id":"23250","messageId":"Pine.LNX.4.63.0607050021330.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4760","inReplyTo":"7v8xn9gjh5.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-04T22:25:04Z","receivedAt":"2006-07-04T22:25:04Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Jul 2006, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > We could introduce a time.maximumSkew variable, and just walk only \n> > that much further when traversing the commits.\n> \n> We could have had \"commit generation number\" in the commit\n> object header, and use that instead of commit timestamps for\n> these traversal purposes.  The generation number for a commit is\n> defined to be max(generation number of its parents)+1 and we\n> prime the recursive this definition by defining the generation\n> number for the root commit to be one.\n\nAre you really, really sure this is a remedy? I, for one, am quite sure of \nthe opposite. What you propose is just another time scale, only this time, \nit is not universally true (not even minus local incompetence to keep the \nclock accurate).\n\nIf that should be not true, you always could rely on topo order. Which \ndoes not seem to solve the problem for you.\n\nCiao,\nDscho\n"},{"id":"23253","messageId":"7vzmfpf0w2.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"Pine.LNX.4.63.0607050021330.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-04T22:42:05Z","receivedAt":"2006-07-04T22:42:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> If that should be not true, you always could rely on topo order. Which \n> does not seem to solve the problem for you.\n\nThe computation of merge-base is about computing topo order\ncheaply, so that is a recursive definition of the problem, not a\nsolution, I am afraid.  \n\nWith the generation counter, we know the clean-up phase needs to\nparse and traverse unparsed parents with the same or higher\ngeneration counter than the lowest we have in the result list,\nwhich would limit our clean-up traversal.  In order to look at\nthe generation number of parent, we would need to parse it, so\nwe would end up parsing one level more than needed at the edge,\nthough.\n"},{"id":"23257","messageId":"44AAF49F.6090008@gmail.com","threadId":"4760","inReplyTo":"Pine.LNX.4.63.0607050021330.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Additional merge-base tests","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-07-04T23:07:11Z","receivedAt":"2006-07-04T23:07:11Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> Hi,\n> \n> On Tue, 4 Jul 2006, Junio C Hamano wrote:\n> \n>> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n>>\n>>> We could introduce a time.maximumSkew variable, and just walk only \n>>> that much further when traversing the commits.\n>> We could have had \"commit generation number\" in the commit\n>> object header, and use that instead of commit timestamps for\n>> these traversal purposes.  The generation number for a commit is\n>> defined to be max(generation number of its parents)+1 and we\n>> prime the recursive this definition by defining the generation\n>> number for the root commit to be one.\n> \n> Are you really, really sure this is a remedy? I, for one, am quite sure of \n> the opposite. What you propose is just another time scale, only this time, \n> it is not universally true (not even minus local incompetence to keep the \n> clock accurate).\n\nIt works[*] and it does what using the timestamp was trying to do. \nNamely, work from \"more recent\" (or \"closer\") commits toward \"older\" (or \n\"farther\") commits until you've gone past the point you care about.\n\nIt's a little late to be changing the structure of a commit and you'd \nhave to deal with some size/scale issues, but it's do-able. A better \nidea may be to generate and keep the generation number on a per \nrepository basis, and you'd be able to work around changing grafts.\n\n[*] Grafts do _really_ nasty things to this. Just like clock skew does now.\n"},{"id":"23258","messageId":"e8esnn$mb5$1@sea.gmane.org","threadId":"4760","inReplyTo":"44AAF49F.6090008@gmail.com","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-07-04T23:14:01Z","receivedAt":"2006-07-04T23:14:01Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"A Large Angry SCM wrote:\n\n> It works[*] and it does what using the timestamp was trying to do. \n> Namely, work from \"more recent\" (or \"closer\") commits toward \"older\" (or \n> \"farther\") commits until you've gone past the point you care about.\n> \n> It's a little late to be changing the structure of a commit and you'd \n> have to deal with some size/scale issues, but it's do-able. A better \n> idea may be to generate and keep the generation number on a per \n> repository basis, and you'd be able to work around changing grafts.\n\nWhat about timestamp = MAX(now(), timestamps of parents) idea, which\ndoesn't need changing the structure of a commit?\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"23259","messageId":"7v64idey84.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"e8esnn$mb5$1@sea.gmane.org","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-04T23:39:39Z","receivedAt":"2006-07-04T23:39:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jakub Narebski <jnareb@gmail.com> writes:\n\n> What about timestamp = MAX(now(), timestamps of parents) idea, which\n> doesn't need changing the structure of a commit?\n\nIt changes the semantics without change syntax, which is not any\nbetter (and in fact I think it is worse).\n"},{"id":"23260","messageId":"7v1wt0gapq.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"44AAF49F.6090008@gmail.com","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-05T00:24:33Z","receivedAt":"2006-07-05T00:24:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"A Large Angry SCM <gitzilla@gmail.com> writes:\n\n>\n> It works[*] and it does what using the timestamp was trying to\n> do. Namely, work from \"more recent\" (or \"closer\") commits toward\n> \"older\" (or \"farther\") commits until you've gone past the point you\n> care about.\n\nIf you really really care, now we have clear_commit_marks() with\nget_merge_bases() infrastructure in, you _could_ run another\nround of get_merge_bases() on the commit on the result list to\nsee which ones are reachable from others by performing an\nequivalent of fast-forward/already-up-to-date check.\n"},{"id":"23261","messageId":"44AB073A.9040301@gmail.com","threadId":"4760","inReplyTo":"e8esnn$mb5$1@sea.gmane.org","subject":"Re: [PATCH] Additional merge-base tests","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-07-05T00:26:34Z","receivedAt":"2006-07-05T00:26:34Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Jakub Narebski wrote:\n> A Large Angry SCM wrote:\n> \n>> It works[*] and it does what using the timestamp was trying to do. \n>> Namely, work from \"more recent\" (or \"closer\") commits toward \"older\" (or \n>> \"farther\") commits until you've gone past the point you care about.\n>>\n>> It's a little late to be changing the structure of a commit and you'd \n>> have to deal with some size/scale issues, but it's do-able. A better \n>> idea may be to generate and keep the generation number on a per \n>> repository basis, and you'd be able to work around changing grafts.\n> \n> What about timestamp = MAX(now(), timestamps of parents) idea, which\n> doesn't need changing the structure of a commit?\n> \n\nSo, do you really want your name as committer on a commit with a date \n300 years in the future because one of the parents had a bad date?\n"},{"id":"23263","messageId":"7vhd1weujg.fsf@assigned-by-dhcp.cox.net","threadId":"4760","inReplyTo":"7vpsgllsnp.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-05T00:59:15Z","receivedAt":"2006-07-05T00:59:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> It may be interesting to run tests on real merges (I believe the\n> kernel repository has a handful merges that have more than one\n> merge bases) to see how effective the current clean-up pass is.\n> It may turn out to be ineffective in practice, in which case we\n> could kill it off.\n\nSo I counted.\n\nThere are 23 commits in the kernel history that have more than\none merge-bases.  The current merge-base code tells us that all\nof them have two merge-bases.\n\nNone of them suffers from the horizon effect; the two bases\nare not ancestor/descendant of each other.\n\nA good news is that get_merge_bases() gives the same answer\nwithout the clean-up pass mark_reachable_commits().\n\nd0e5f39f1ee2e55d140064bb6d74c8bad25d71d0\n361ea93cbff0e42cbc6a0f3c7a8238db9ed15648\n4b2d9cf00962d0a0e697f887f3ecaa155cbde555\nba9b28d19a3251bb1dfe6a6f8cc89b96fb85f683\ndb21e578e551421d76641d72cb3f8296ed3f9e61\nb425c8c5922562c562dc55a636c3c8d758ed6d17\n2e9ff56efbc005ab2b92b68df65940c7459446c6\n75e47b36004d136edff68295420424cba3a5ccd0\nc45ae87ec9d03c9adfc466a6b560cb38b154813a\n09e4f9029da1b53e835555c353a89c36b71233b0\n0b310f36d7d96e27f6941ec0f9b95e15142f1e78\ndb9ace7083dbdcc3d02bdd6a1d26132c80b5b726\n80c7af4074cbb4cb6be5d35c443ea6d5e8838a84\n701db69d6647f61e4660c9102d7f2fd5dffc203d\n5e3c2b95dd560baa41b08c8f5f00bbd6fbeebdcb\nc7fb577e2a6cb04732541f2dc402bd46747f7558\nba9b543d5bec0a7605952e2ba501fb8b0f3b6407\n84ffa747520edd4556b136bdfc9df9eb1673ce12\nda28c12089dfcfb8695b6b555cdb8e03dda2b690\n3190186362466658f01b2e354e639378ce07e1a9\n0c168775709faa74c1b87f1e61046e0c51ade7f3\n0e396ee43e445cb7c215a98da4e76d0ce354d9d7\n467ca22d3371f132ee225a5591a1ed0cd518cb3d\n"},{"id":"23269","messageId":"Pine.LNX.4.63.0607050952140.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4760","inReplyTo":"44AAF49F.6090008@gmail.com","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-05T07:56:07Z","receivedAt":"2006-07-05T07:56:07Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Jul 2006, A Large Angry SCM wrote:\n\n> Johannes Schindelin wrote:\n> > Hi,\n> > \n> > On Tue, 4 Jul 2006, Junio C Hamano wrote:\n> > \n> > > Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> > > \n> > > > We could introduce a time.maximumSkew variable, and just walk only that\n> > > > much further when traversing the commits.\n> > > We could have had \"commit generation number\" in the commit\n> > > object header, and use that instead of commit timestamps for\n> > > these traversal purposes.  The generation number for a commit is\n> > > defined to be max(generation number of its parents)+1 and we\n> > > prime the recursive this definition by defining the generation\n> > > number for the root commit to be one.\n> > \n> > Are you really, really sure this is a remedy? I, for one, am quite sure of\n> > the opposite. What you propose is just another time scale, only this time,\n> > it is not universally true (not even minus local incompetence to keep the\n> > clock accurate).\n> \n> It works[*] and it does what using the timestamp was trying to do. Namely,\n> work from \"more recent\" (or \"closer\") commits toward \"older\" (or \"farther\")\n> commits until you've gone past the point you care about.\n> \n> It's a little late to be changing the structure of a commit and you'd have to\n> deal with some size/scale issues, but it's do-able. A better idea may be to\n> generate and keep the generation number on a per repository basis, and you'd\n> be able to work around changing grafts.\n\nLike, inside the cache? I dunno. IMHO it is way too late to change the \nstructure of a commit in that particular manner, _plus_ you would get \noverflow issues.\n\n> [*] Grafts do _really_ nasty things to this. Just like clock skew does now.\n\nGrafts can do much nastier things to you, for example having a circular \nhistory. _But_ they cannot do that nasty thing outside of your repo. Clock \nskews can.\n\nCiao,\nDscho\n"},{"id":"23271","messageId":"200607051039.53288.Josef.Weidendorfer@gmx.de","threadId":"4760","inReplyTo":"7v8xn9gjh5.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Josef Weidendorfer","fromEmail":"josef.weidendorfer@gmx.de","sentAt":"2006-07-05T08:39:53Z","receivedAt":"2006-07-05T08:39:53Z","isPatch":true,"sender":{"key":"josef.weidendorfer@gmx.de","avatar":null},"body":"On Tuesday 04 July 2006 23:15, Junio C Hamano wrote:\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > We could introduce a time.maximumSkew variable, and just walk only \n> > that much further when traversing the commits.\n> \n> We could have had \"commit generation number\" in the commit\n> object header, and use that instead of commit timestamps for\n> these traversal purposes.\n\nIsn't this \"commit generation number\" information that can be\nregenerated on the fly, i.e. a perfect fit for data to be stored\nin a persistant cache, e.g. in \".git/tmp/virtual-commit-timestamps\"?\n\nJosef\n"},{"id":"23278","messageId":"44ABCC89.2090003@gmail.com","threadId":"4760","inReplyTo":"200607051039.53288.Josef.Weidendorfer@gmx.de","subject":"Re: [PATCH] Additional merge-base tests","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-07-05T14:28:25Z","receivedAt":"2006-07-05T14:28:25Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Josef Weidendorfer wrote:\n> On Tuesday 04 July 2006 23:15, Junio C Hamano wrote:\n>> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n>>\n>>> We could introduce a time.maximumSkew variable, and just walk only \n>>> that much further when traversing the commits.\n>> We could have had \"commit generation number\" in the commit\n>> object header, and use that instead of commit timestamps for\n>> these traversal purposes.\n> \n> Isn't this \"commit generation number\" information that can be\n> regenerated on the fly, i.e. a perfect fit for data to be stored\n> in a persistant cache, e.g. in \".git/tmp/virtual-commit-timestamps\"?\n\nYes\n"},{"id":"23280","messageId":"44ABE596.40103@gmail.com","threadId":"4760","inReplyTo":"Pine.LNX.4.63.0607050952140.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Additional merge-base tests","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-07-05T16:15:18Z","receivedAt":"2006-07-05T16:15:18Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> Hi,\n> \n> On Tue, 4 Jul 2006, A Large Angry SCM wrote:\n> \n>> Johannes Schindelin wrote:\n>>> Hi,\n>>>\n>>> On Tue, 4 Jul 2006, Junio C Hamano wrote:\n>>>\n>>>> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n>>>>\n>>>>> We could introduce a time.maximumSkew variable, and just walk only that\n>>>>> much further when traversing the commits.\n>>>> We could have had \"commit generation number\" in the commit\n>>>> object header, and use that instead of commit timestamps for\n>>>> these traversal purposes.  The generation number for a commit is\n>>>> defined to be max(generation number of its parents)+1 and we\n>>>> prime the recursive this definition by defining the generation\n>>>> number for the root commit to be one.\n>>> Are you really, really sure this is a remedy? I, for one, am quite sure of\n>>> the opposite. What you propose is just another time scale, only this time,\n>>> it is not universally true (not even minus local incompetence to keep the\n>>> clock accurate).\n>> It works[*] and it does what using the timestamp was trying to do. Namely,\n>> work from \"more recent\" (or \"closer\") commits toward \"older\" (or \"farther\")\n>> commits until you've gone past the point you care about.\n>>\n>> It's a little late to be changing the structure of a commit and you'd have to\n>> deal with some size/scale issues, but it's do-able. A better idea may be to\n>> generate and keep the generation number on a per repository basis, and you'd\n>> be able to work around changing grafts.\n> \n> Like, inside the cache? I dunno. IMHO it is way too late to change the \n> structure of a commit in that particular manner, _plus_ you would get \n> overflow issues.\n\nYour don't need to change the commit object, create some repository \nspecific, local, auxiliary information. Overflow should not be a problem \nuntil a path length to a root commit exceeds the machine word size.\n\nBut is it really worth the work? Does it help anything other than \nmerge-base?\n\n>> [*] Grafts do _really_ nasty things to this. Just like clock skew does now.\n> \n> Grafts can do much nastier things to you, for example having a circular \n> history. _But_ they cannot do that nasty thing outside of your repo. Clock \n> skews can.\n\nIf grafts in your repository create a cycle, the misbehavior of \nmerge-base should be among the least of your concerns.\n"},{"id":"23285","messageId":"Pine.LNX.4.63.0607051900200.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4760","inReplyTo":"44ABE596.40103@gmail.com","subject":"Re: [PATCH] Additional merge-base tests","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-05T17:04:55Z","receivedAt":"2006-07-05T17:04:55Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 5 Jul 2006, A Large Angry SCM wrote:\n\n> If grafts in your repository create a cycle, the misbehavior of merge-base\n> should be among the least of your concerns.\n\nRight. BUT grafts can be very helpful to connect branches which were \nindependently imported into git. And in these cases, the clockSkew really \nis no clockSkew. But in that case, the generation number would have to be \nrecalculated also.\n\nAnyway, I think that it should be a configurable, which defaults to off, \ni.e. in the normal case merge-base should behave as it does now. And if we \nhave that configurable, we might as well take the safe but dumb approach \nto just traverse _everything_.\n\nCiao,\nDscho\n"}]}