{"thread":{"id":"31246","subject":"[PATCH] rev-list docs: clarify --topo-order description","startedAt":"2012-08-13T22:21:09Z","lastAt":"2012-08-17T18:11:52Z","messageCount":26,"participants":["Junio C Hamano","Martin von Zweigbergk","Michael Haggerty","Thomas Rast"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"196945","messageId":"7vsjbqbfhm.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":null,"subject":"[PATCH] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-13T22:21:09Z","receivedAt":"2012-08-13T22:21:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"We said \"--date-order\" still does not violate the topology, but it\nwas still not clear enough.\n\nReword the description for both \"--date-order\" and \"--topo-order\",\nand add an illustration to it.\n\nSigned-off-by: Junio C Hamano \n---\n\n * Let's do this before I forget...; came up in discussion $gmane/203370\n\n Documentation/rev-list-options.txt | 29 +++++++++++++++++++++++------\n 1 file changed, 23 insertions(+), 6 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 6a4b635..dc501ee 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -579,15 +579,32 @@ Commit Ordering\n By default, the commits are shown in reverse chronological order.\n \n --topo-order::\n-\n-\tThis option makes them appear in topological order (i.e.\n-\tdescendant commits are shown before their parents).\n+\tThis option makes them appear in topological order. Even\n+\twithout this option, descendant commits are shown before\n+\ttheir parents, but this tries to avoid showing commits on\n+\tmultiple lines of history intermixed.\n \n --date-order::\n \n-\tThis option is similar to '--topo-order' in the sense that no\n-\tparent comes before all of its children, but otherwise things\n-\tare still ordered in the commit timestamp order.\n+\tShow no parents before all of its children, but otherwise\n+\tshow commits in the commit timestamp order.\n++\n+For example, in a commit history like this:\n++\n+----------------------------------------------------------------\n+\n+ ---1----2----4----7\n+\t\\\t \\\n+\t 3----5----6----8---\n+\n+----------------------------------------------------------------\n++\n+where the numbers denote the order of commit timestamps, `git\n+rev-list` and friends with `--date-order` show the commits in the\n+timestamp order: 8 7 6 5 4 3 2 1.\n++\n+With `--topo-order`, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5\n+3 1), to avoid commits from two branches mixed together.\n \n --reverse::\n \n-- \n1.7.12.rc2.85.g1de7134\n"},{"id":"196946","messageId":"CAOeW2eGoNvgpbQ9iM0xHpSD1Z4XyC-J8VNVW0bVw3p9qOeijjg@mail.gmail.com","threadId":"31246","inReplyTo":"7vsjbqbfhm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2012-08-13T22:46:08Z","receivedAt":"2012-08-13T22:46:08Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Mon, Aug 13, 2012 at 3:21 PM, Junio C Hamano wrote:\n> * Let's do this before I forget...; came up in discussion $gmane/203370\n\nThanks! That definitely confused me (and I suppose I stupidly didn't\ntest with a proper range).\n\n>\n> Documentation/rev-list-options.txt | 29 +++++++++++++++++++++++------\n> 1 file changed, 23 insertions(+), 6 deletions(-)\n>\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index 6a4b635..dc501ee 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -579,15 +579,32 @@ Commit Ordering\n> By default, the commits are shown in reverse chronological order.\n\nIt seems likely that those reading the above sentence will continue on\nto read about --topo-order, but still, do you think the \"descendant\ncommits are shown before parents\" part belong here instead?\n\n> --topo-order::\n> -\n> - This option makes them appear in topological order (i.e.\n> - descendant commits are shown before their parents).\n> + This option makes them appear in topological order. Even\n> + without this option, descendant commits are shown before\n> + their parents, but this tries to avoid showing commits on\n> + multiple lines of history intermixed.\n>\n> --date-order::\n>\n> - This option is similar to '--topo-order' in the sense that no\n> - parent comes before all of its children, but otherwise things\n> - are still ordered in the commit timestamp order.\n> + Show no parents before all of its children, but otherwise\n> + show commits in the commit timestamp order.\n> ++\n> +For example, in a commit history like this:\n> ++\n> +----------------------------------------------------------------\n> +\n> + ---1----2----4----7\n> + \\ \\\n> + 3----5----6----8---\n> +\n> +----------------------------------------------------------------\n> ++\n> +where the numbers denote the order of commit timestamps, `git\n> +rev-list` and friends with `--date-order` show the commits in the\n> +timestamp order: 8 7 6 5 4 3 2 1.\n> ++\n> +With `--topo-order`, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5\n> +3 1), to avoid commits from two branches mixed together.\n\nIt would help at least me to also know what the output would be\nwithout either of --date-order or --topo-order. (Does the default\norder have a name, by the way?)\n"},{"id":"196947","messageId":"7vobmebdfc.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"CAOeW2eGoNvgpbQ9iM0xHpSD1Z4XyC-J8VNVW0bVw3p9qOeijjg@mail.gmail.com","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-13T23:05:43Z","receivedAt":"2012-08-13T23:05:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin von Zweigbergk writes:\n\n>> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n>> index 6a4b635..dc501ee 100644\n>> --- a/Documentation/rev-list-options.txt\n>> +++ b/Documentation/rev-list-options.txt\n>> @@ -579,15 +579,32 @@ Commit Ordering\n>> By default, the commits are shown in reverse chronological order.\n>\n> It seems likely that those reading the above sentence will continue on\n> to read about --topo-order, but still, do you think the \"descendant\n> commits are shown before parents\" part belong here instead?\n\nI do not think so. When you are not limited (i.e. limit_list() is\nnot called), you could do something like \"git rev-list 4 5\" in a\nhistory like this:\n\n\t--1---5---2---3---4\n\nand get end up getting \"5 4 3 2 1\", and \"2\" certainly doesn't get\nshown before \"5\" does.\n\nIn your series where cherry-pick runs prepare_revision_walk() and\nmakes the outcome sort in reverse, the list has to be limited, so\nthe above is a non-issue, but in the context of this document, we\ncannot assume that.\n"},{"id":"196957","messageId":"CAOeW2eE63JQbo+x7ZTDupt=auvo2_4Df790TPOtTEynCBK6z5g@mail.gmail.com","threadId":"31246","inReplyTo":"7vobmebdfc.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2012-08-14T05:33:22Z","receivedAt":"2012-08-14T05:33:22Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Mon, Aug 13, 2012 at 4:05 PM, Junio C Hamano wrote:\n> Martin von Zweigbergk writes:\n>\n>>> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n>>> index 6a4b635..dc501ee 100644\n>>> --- a/Documentation/rev-list-options.txt\n>>> +++ b/Documentation/rev-list-options.txt\n>>> @@ -579,15 +579,32 @@ Commit Ordering\n>>> By default, the commits are shown in reverse chronological order.\n>>\n>> It seems likely that those reading the above sentence will continue on\n>> to read about --topo-order, but still, do you think the \"descendant\n>> commits are shown before parents\" part belong here instead?\n>\n> I do not think so. When you are not limited (i.e. limit_list() is\n> not called), you could do something like \"git rev-list 4 5\" in a\n> history like this:\n>\n> --1---5---2---3---4\n>\n> and get end up getting \"5 4 3 2 1\", and \"2\" certainly doesn't get\n> shown before \"5\" does.\n\nOh, interesting. I had no idea, although that does make sense. Thanks.\n\nStill, the \"Even without this option\" strongly suggests to me that\nwhat follows (\"descendant commits are shown before parents\") applies\nto the \"By default\" case. Would it be correct to say something like\n\"By default, the commits are shown in reverse chronological order.\nWhen commit limiting is in effect, descendant commits are shown before\nparents.\"? I'm not sure the \"commit limiting\" section in the man page\ninvolves the same options as \"limit_list\" (I rather think they don't),\nbut I don't know if there's a better term to use in the documentation\neither.\n"},{"id":"196963","messageId":"502A0AC1.4060800@alum.mit.edu","threadId":"31246","inReplyTo":"7vsjbqbfhm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-08-14T08:22:25Z","receivedAt":"2012-08-14T08:22:25Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 08/14/2012 12:21 AM, Junio C Hamano wrote:\n> We said \"--date-order\" still does not violate the topology, but it\n> was still not clear enough.\n>\n> Reword the description for both \"--date-order\" and \"--topo-order\",\n> and add an illustration to it.\n>\n> Signed-off-by: Junio C Hamano \n\nThanks for this change. I was recently trying to figure out the meaning \nof these ordering options myself, and found the old text confusing.\n\n> ---\n>\n> * Let's do this before I forget...; came up in discussion $gmane/203370\n>\n> Documentation/rev-list-options.txt | 29 +++++++++++++++++++++++------\n> 1 file changed, 23 insertions(+), 6 deletions(-)\n>\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index 6a4b635..dc501ee 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -579,15 +579,32 @@ Commit Ordering\n> By default, the commits are shown in reverse chronological order.\n>\n> --topo-order::\n> -\n> -\tThis option makes them appear in topological order (i.e.\n> -\tdescendant commits are shown before their parents).\n> +\tThis option makes them appear in topological order. Even\n> +\twithout this option, descendant commits are shown before\n> +\ttheir parents, but this tries to avoid showing commits on\n> +\tmultiple lines of history intermixed.\n>\n> --date-order::\n>\n> -\tThis option is similar to '--topo-order' in the sense that no\n> -\tparent comes before all of its children, but otherwise things\n> -\tare still ordered in the commit timestamp order.\n> +\tShow no parents before all of its children, but otherwise\n> +\tshow commits in the commit timestamp order.\n> ++\n> +For example, in a commit history like this:\n> ++\n> +----------------------------------------------------------------\n> +\n> + ---1----2----4----7\n> +\t\\\t \\\n> +\t 3----5----6----8---\n> +\n> +----------------------------------------------------------------\n> ++\n> +where the numbers denote the order of commit timestamps, `git\n> +rev-list` and friends with `--date-order` show the commits in the\n> +timestamp order: 8 7 6 5 4 3 2 1.\n> ++\n> +With `--topo-order`, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5\n> +3 1), to avoid commits from two branches mixed together.\n\nIs it possible to predict which of the two orders would be taken here? \nIt would be nice for the results to be deterministic. For example, \ntopology \"ties\" could be broken by choosing the commit with the most \nrecent timestamp.\n\n> --reverse::\n>\n>\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"196964","messageId":"877gt16ewe.fsf@thomas.inf.ethz.ch","threadId":"31246","inReplyTo":"7vsjbqbfhm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-14T08:45:05Z","receivedAt":"2012-08-14T08:45:05Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> --topo-order::\n> -\n> -\tThis option makes them appear in topological order (i.e.\n> -\tdescendant commits are shown before their parents).\n> +\tThis option makes them appear in topological order. Even\n> +\twithout this option, descendant commits are shown before\n> +\ttheir parents, but this tries to avoid showing commits on\n> +\tmultiple lines of history intermixed.\n\nI don't think that is true in general. Without any -order options, we\nprocess commits in date order, which *usually* means topological order,\nbut not always. You can easily verify this:\n\n $ git init\n $ date\n Tue Aug 14 10:39:49 CEST 2012\n $ echo initial >file\n $ git add file\n $ GIT_COMMITTER_DATE=\"Tue Aug 14 11:39:49 2012\" git commit\n $ echo foo >file\n $ git commit -mfoo file\n $ git checkout -bside HEAD^\n $ echo bar >file\n $ git commit -mbar file\n $ git log --all --oneline\n 8c71325 bar\n e5072d7 initial\n 1be702c foo\n\nSo the --topo-order switch *ensures* that we process commits in\ntopological order even in the face of skewed clocks.\n\nI suspect that\n\n> +\ttheir parents, but this tries to avoid showing commits on\n> +\tmultiple lines of history intermixed.\n\nis just a fortunate side effect of the topological sort.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"196971","messageId":"7vzk5x8s1q.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"877gt16ewe.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-14T14:30:25Z","receivedAt":"2012-08-14T14:30:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> So the --topo-order switch *ensures* that we process commits in\n> topological order even in the face of skewed clocks.\n\nYes, I *think* that I attempted to show with the illustration.\n\n> I suspect that\n>\n>> +\ttheir parents, but this tries to avoid showing commits on\n>> +\tmultiple lines of history intermixed.\n>\n> is just a fortunate side effect of the topological sort.\n\nI am not sure if it is \"side effect\"; I *think* it was the \"primary\nobjective\" we added topo-order in the first place.\n"},{"id":"196972","messageId":"87sjbpa5m8.fsf@thomas.inf.ethz.ch","threadId":"31246","inReplyTo":"7vzk5x8s1q.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-14T14:51:59Z","receivedAt":"2012-08-14T14:51:59Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> So the --topo-order switch *ensures* that we process commits in\n>> topological order even in the face of skewed clocks.\n>\n> Yes, I *think* that I attempted to show with the illustration.\n\nBut then the new description is wrong. It claims that children are\nalways before parents, which is not true in the face of clock skew. Or\nam I missing something?\n\n>> I suspect that\n>>\n>>> +\ttheir parents, but this tries to avoid showing commits on\n>>> +\tmultiple lines of history intermixed.\n>>\n>> is just a fortunate side effect of the topological sort.\n>\n> I am not sure if it is \"side effect\"; I *think* it was the \"primary\n> objective\" we added topo-order in the first place.\n\nI won't judge that, since it's waaaay before my time :-)\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"196973","messageId":"7vmx1x8qxo.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"CAOeW2eE63JQbo+x7ZTDupt=auvo2_4Df790TPOtTEynCBK6z5g@mail.gmail.com","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-14T14:54:27Z","receivedAt":"2012-08-14T14:54:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin von Zweigbergk writes:\n\n> Still, the \"Even without this option\" strongly suggests to me that\n> what follows (\"descendant commits are shown before parents\") applies\n> to the \"By default\" case. Would it be correct to say something like\n> \"By default, the commits are shown in reverse chronological order.\n> When commit limiting is in effect, descendant commits are shown before\n> parents.\"?\n\nI wonder if spelling out that level of detail is unnecessarily\noverspecifying the behaviour.\n\nIn general, I'd prefer to keep the insn to end users to the minimum:\ni.e. use the default when you do not care too deeply about the order\nbut you want to get commits in the range in reverse time order in\ngeneral and let the default take care of the detail, and use one of\nthe --foo-order options if a script wants to be more specific about\nthe order. That way we do not have to get our hands tied to an\nunnecessary degree and keep the door open for us to improve the\nimplementation.\n"},{"id":"196976","messageId":"7va9xx8ohz.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"87sjbpa5m8.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-14T15:47:04Z","receivedAt":"2012-08-14T15:47:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Junio C Hamano writes:\n>\n>> Thomas Rast writes:\n>>\n>>> So the --topo-order switch *ensures* that we process commits in\n>>> topological order even in the face of skewed clocks.\n>>\n>> Yes, I *think* that I attempted to show with the illustration.\n>\n> But then the new description is wrong. It claims that children are\n> always before parents, which is not true in the face of clock skew.\n\nAh, you are talking about the \"even without this option\" part.\nYeah, that does not hold true.\n"},{"id":"197063","messageId":"7vmx1v53fb.fsf_-_@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"87sjbpa5m8.fsf@thomas.inf.ethz.ch","subject":"[PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-15T20:02:48Z","receivedAt":"2012-08-15T20:02:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"It was unclear what \"--topo-order\" was really about in the\ndocumentation. It is not just about \"children before parent\", but\nalso about \"don't mix lineages\".\n\nReword the description for both \"--date-order\" and \"--topo-order\",\nand add an illustration to it.\n\nSigned-off-by: Junio C Hamano \n---\n Thomas Rast writes:\n\n > But then the new description is wrong. It claims that children are\n > always before parents, which is not true in the face of clock skew.\n\n Thanks for sanity-check. Here is an updated one.\n\n Documentation/rev-list-options.txt | 31 ++++++++++++++++++++++++-------\n 1 file changed, 24 insertions(+), 7 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 6a4b635..9404d08 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -578,16 +578,33 @@ Commit Ordering\n \n By default, the commits are shown in reverse chronological order.\n \n---topo-order::\n+--date-order::\n+\tShow no parents before all of its children are shown, but\n+\totherwise show commits in the commit timestamp order.\n \n-\tThis option makes them appear in topological order (i.e.\n-\tdescendant commits are shown before their parents).\n+--topo-order::\n+\tShow no parents before all of its children are shown, and\n+\tavoid showing commits on multiple lines of history\n+\tintermixed.\n++\n+For example, in a commit history like this:\n++\n+----------------------------------------------------------------\n \n---date-order::\n+ ---1----2----4----7\n+\t\\\t \\\n+\t 3----5----6----8---\n \n-\tThis option is similar to '--topo-order' in the sense that no\n-\tparent comes before all of its children, but otherwise things\n-\tare still ordered in the commit timestamp order.\n+----------------------------------------------------------------\n++\n+where the numbers denote the order of commit timestamps, `git\n+rev-list` and friends with `--date-order` show the commits in the\n+timestamp order: 8 7 6 5 4 3 2 1.\n++\n+With `--topo-order`, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5\n+3 1); some older commits are shown before newer ones in order to\n+avoid showing the commits from two parallel development track mixed\n+together.\n \n --reverse::\n \n-- \n1.7.12.rc2.85.g1de7134\n"},{"id":"197077","messageId":"CAOeW2eFZNuM_8bFB2cXGVRT0FpDC86fH=XMj9kviXs-UCo1fAA@mail.gmail.com","threadId":"31246","inReplyTo":"7vmx1v53fb.fsf_-_@alter.siamese.dyndns.org","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2012-08-16T06:06:24Z","receivedAt":"2012-08-16T06:06:24Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Wed, Aug 15, 2012 at 1:02 PM, Junio C Hamano wrote:\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index 6a4b635..9404d08 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -578,16 +578,33 @@ Commit Ordering\n>\n> By default, the commits are shown in reverse chronological order.\n\nAs I said before, this led me to believe that \"the commits are shown\nin reverse chronological order\" when neither of --topo-order or\n--date-order is passed. I agree that we should avoid specifying more\nthan necessary about the default case. But in this case, what is\nspecified is not exactly true (in the face of clock skew). Or am I\nmisunderstanding or misinterpreting something? I still don't\nunderstand the revision walker well enough to be able to provide a\nbetter wording, but I think even the rather crude \"By default, the\norder is unspecified.\" would at least not be as easy to misinterpret\n(if that's what I did) and is definitely not over-specified. Of\ncourse, if someone can think of something better, I'm all for it.\n\nRegardless of the above comment about the patch context, what your\npatch actually changes looks good. Thanks again.\n"},{"id":"197078","messageId":"7vipcj2w9f.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"CAOeW2eFZNuM_8bFB2cXGVRT0FpDC86fH=XMj9kviXs-UCo1fAA@mail.gmail.com","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-16T06:20:28Z","receivedAt":"2012-08-16T06:20:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin von Zweigbergk writes:\n\n> On Wed, Aug 15, 2012 at 1:02 PM, Junio C Hamano wrote:\n>> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n>> index 6a4b635..9404d08 100644\n>> --- a/Documentation/rev-list-options.txt\n>> +++ b/Documentation/rev-list-options.txt\n>> @@ -578,16 +578,33 @@ Commit Ordering\n>>\n>> By default, the commits are shown in reverse chronological order.\n>\n> As I said before, this led me to believe that \"the commits are shown\n> in reverse chronological order\" when neither of --topo-order or\n> --date-order is passed. I agree that we should avoid specifying more\n> than necessary about the default case. But in this case, what is\n> specified is not exactly true (in the face of clock skew). Or am I\n> misunderstanding or misinterpreting something? I still don't\n> understand the revision walker well enough to be able to provide a\n> better wording, but I think even the rather crude \"By default, the\n> order is unspecified.\" would at least not be as easy to misinterpret\n> (if that's what I did) and is definitely not over-specified. Of\n> course, if someone can think of something better, I'm all for it.\n>\n> Regardless of the above comment about the patch context, what your\n> patch actually changes looks good. Thanks again.\n\nWe could remove it if you find it confusing.\n\nI think the original motivation that line was added was to help\npeople who see \"git log\" (without any frills) output for the first\ntime not to be alarmed when they see newer things first: \"In\ngeneral, the \"time\" flows from bottom to top\", but the \"time\" in\nthat sentence is not necessarily the timestamp of either committer\nnor author field.\n"},{"id":"197079","messageId":"7vehn72vyl.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"7vipcj2w9f.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-16T06:26:58Z","receivedAt":"2012-08-16T06:26:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> We could remove it if you find it confusing.\n>\n> I think the original motivation that line was added was to help\n> people who see \"git log\" (without any frills) output for the first\n> time not to be alarmed when they see newer things first: \"In\n> general, the \"time\" flows from bottom to top\", but the \"time\" in\n> that sentence is not necessarily the timestamp of either committer\n> nor author field.\n\nJust to clarify, I am not defending the current wording that I did\nnot touch in my patch with the above. I am just giving historical\nbackground to help _other_ people (including you) to come up with a\nbetter wording, as I do not think of a better replacement myself.\n"},{"id":"197081","messageId":"87k3wzxm6e.fsf@thomas.inf.ethz.ch","threadId":"31246","inReplyTo":"7vmx1v53fb.fsf_-_@alter.siamese.dyndns.org","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-16T08:42:33Z","receivedAt":"2012-08-16T08:42:33Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n> > But then the new description is wrong. It claims that children are\n> > always before parents, which is not true in the face of clock skew.\n>\n> Thanks for sanity-check. Here is an updated one.\n[...]\n> ---topo-order::\n> +--date-order::\n> +\tShow no parents before all of its children are shown, but\n> +\totherwise show commits in the commit timestamp order.\n> \n> -\tThis option makes them appear in topological order (i.e.\n> -\tdescendant commits are shown before their parents).\n> +--topo-order::\n> +\tShow no parents before all of its children are shown, and\n> +\tavoid showing commits on multiple lines of history\n> +\tintermixed.\n\nAck, thanks.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197082","messageId":"87pq6rw77l.fsf@thomas.inf.ethz.ch","threadId":"31246","inReplyTo":"7vehn72vyl.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-16T08:51:10Z","receivedAt":"2012-08-16T08:51:10Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Junio C Hamano writes:\n>\n>> We could remove it if you find it confusing.\n>>\n>> I think the original motivation that line was added was to help\n>> people who see \"git log\" (without any frills) output for the first\n>> time not to be alarmed when they see newer things first: \"In\n>> general, the \"time\" flows from bottom to top\", but the \"time\" in\n>> that sentence is not necessarily the timestamp of either committer\n>> nor author field.\n>\n> Just to clarify, I am not defending the current wording that I did\n> not touch in my patch with the above. I am just giving historical\n> background to help _other_ people (including you) to come up with a\n> better wording, as I do not think of a better replacement myself.\n\nI tend to agree with Martin, the existing header for the list\n\n>>> By default, the commits are shown in reverse chronological order.\n\nis misleading. I suppose the real problem is that the \"true\" ordering\nis completely obvious as the one ordering that does not require\npreprocessing, but ugly to specify in words. Perhaps we can bikeshed a\nlittle? How about\n\n By default, commits are shown in an order that coincides with\n `--date-order` on well-behaved history, but is faster to compute.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197098","messageId":"502CC4E7.5060508@alum.mit.edu","threadId":"31246","inReplyTo":"87pq6rw77l.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-08-16T10:01:11Z","receivedAt":"2012-08-16T10:01:11Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 08/16/2012 10:51 AM, Thomas Rast wrote:\n> [...]\n> is misleading. I suppose the real problem is that the \"true\" ordering\n> is completely obvious as the one ordering that does not require\n> preprocessing, but ugly to specify in words. Perhaps we can bikeshed a\n> little? How about\n>\n> By default, commits are shown in an order that coincides with\n> `--date-order` on well-behaved history, but is faster to compute.\n\nMaybe the problem is not the description of the options, but the options \nthemselves. Why does the behavior default to some mysterious order that \nwe don't even want to document? Only for the sake of computational \nefficiency. This is the tail wagging the dog.\n\nWhy not turn the behavior on its head:\n\n* Change the default behavior to be something well-defined, easy to \ndocument, and convenient for humans, such as \"topological order with \nties broken by timestamp\" or \"approximate timestamp order, but \nrespecting dependencies\".\n\n* Add a new option, --arbitrary-order, that explicitly chooses \nefficiency instead of a defined order.\n\nThat way the easiest thing to type is also the most convenient, whereas \nwhen you care about efficiency and *don't* care about order (i.e., \nmainly in scripts) you can explicitly request the high-performance option.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"197099","messageId":"87k3wzujuy.fsf@thomas.inf.ethz.ch","threadId":"31246","inReplyTo":"502CC4E7.5060508@alum.mit.edu","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-16T12:00:53Z","receivedAt":"2012-08-16T12:00:53Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Michael Haggerty writes:\n\n> On 08/16/2012 10:51 AM, Thomas Rast wrote:\n>> I suppose the real problem is that the \"true\" ordering\n>> is completely obvious as the one ordering that does not require\n>> preprocessing, but ugly to specify in words. Perhaps we can bikeshed a\n>> little? How about\n>>\n>> By default, commits are shown in an order that coincides with\n>> `--date-order` on well-behaved history, but is faster to compute.\n>\n> Maybe the problem is not the description of the options, but the\n> options themselves. Why does the behavior default to some mysterious\n> order that we don't even want to document? Only for the sake of\n> computational efficiency. This is the tail wagging the dog.\n>\n> Why not turn the behavior on its head:\n>\n> * Change the default behavior to be something well-defined, easy to\n> document, and convenient for humans, such as \"topological order with\n> ties broken by timestamp\" or \"approximate timestamp order, but\n> respecting dependencies\".\n>\n> * Add a new option, --arbitrary-order, that explicitly chooses\n> efficiency instead of a defined order.\n\nI think that would be a rather bad decision, largely because (taking my\ngit.git as an example):\n\n $ time git log | head -1\n commit e5e6172f9060c958e3f0d679cd7049d4007eed2c\n\n real 0m0.033s\n user 0m0.026s\n sys 0m0.007s\n\n $ time git log --date-order | head -1\n commit e5e6172f9060c958e3f0d679cd7049d4007eed2c\n\n real 0m0.429s\n user 0m0.359s\n sys 0m0.031s\n\nThat is, even in medium-sized projects like git.git, any -order option\nincurs a significant preprocessing time until git-log can show the first\ncommit. It scales linearly with the number of commits in the range, and\nin a linux.git lying around here is already around 3.9s for the same\ncommand.\n\nSo if --date-order or --topo-order were the default, you'd have a\nsignificant delay even if you just use 'git log' to quickly see the last\nfew commits. At least to me, the optimization makes perfect sense.\n\nThe right fix would be to dig up Peff's work on generation number\ncaching, and modify the algorithm to take generation numbers into\naccount. Then the default order would magically become the same as\n--date-order at no speed loss, *and* we'd get a huge speed boost to 'git\nlog --graph' startup times.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197103","messageId":"7v628i3jiu.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"87k3wzujuy.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-16T16:10:17Z","receivedAt":"2012-08-16T16:10:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n>> Why not turn the behavior on its head:\n>>\n>> * Change the default behavior to be something well-defined, easy to\n>> document, and convenient for humans, such as \"topological order with\n>> ties broken by timestamp\" or \"approximate timestamp order, but\n>> respecting dependencies\".\n>>\n>> * Add a new option, --arbitrary-order, that explicitly chooses\n>> efficiency instead of a defined order.\n>\n> I think that would be a rather bad decision, largely because (taking my\n> git.git as an example):\n>\n> $ time git log | head -1\n> $ time git log --date-order | head -1\n\nYou are correct to point out that introducing \"--arbitrary-order\"\nand force sorting by default is stupid for one reason, but forgot to\nstress the other equally important reason, I think. Even though you\ncame close to it here:\n\n> ... if you just use 'git log' to quickly see the last\n> few commits. At least to me, the optimization makes perfect sense.\n\nyou may not have fully internalized that other reason yourself, I\nsuspect, for the reason I mention in my last two paragraphs below.\n\nWhen you run \"git log\", you are asking only to see \"the last few\"\ncommits. The size of \"few\" actually depends on the occasion and the\nuser, but the important thing to notice is that the definition of\n\"the last\" is fuzzily defined. In such a request over a history\nlike this:\n\n ---A---B---C---D\n \\\n ---1---2---3---4---* = HEAD\n\nthe user does not care the exact order, as long as the ones \"closer\"\n(again, a fuzzy definition) to HEAD come out earlier than the ones\n\"farther\" (and all of them have to come out eventually but that goes\nwithout saying).\n\nIn the case of the above sample history, even with clock skews, the\nones labeled with alphabets appear in the expected order among\nthemselves, and the ones labeled with numbers also do, with or\nwithout sorting. And all three orders match the use case of \"git\nlog\" to view \"the last few\" commits just fine. When we have the\ndefault, topo and date orders, all of which would give us output\nsuitable for the purpose of showing \"the last few\", picking the one\nwith the least latency is the right thing to do.\n\nIn other words, latency is important, but a short-latency solution\nis acceptable and preferred only if it gives a reasonable result.\nGiving useless output with small latency is not what we are aiming\nto do.\n\n> The right fix would be to dig up Peff's work on generation number\n> caching, and modify the algorithm to take generation numbers into\n> account.\n\nI think you are totally wrong here, unless you are talking about a\ngeneration number that is different from what I recall from the\nolder discussion. Think of the sample history above, and imagine\nthat the numbered ones are based on the current 'master', but that\nthe alphabet ones are based on an ancient maintenance release that\nis 1000 generations behind (think of me running the command after\nfinishing the day's integration cycle, sitting at the tip of 'pu',\nwhere the last topic merged is meant to be eventually merged to\nmaint-1.7.9). All of the commits depicted in the picture will have\nthe commit timestamps in the past few hours. Ancestors of A and 1,\nnot drawn in the picture, were made yesterday or before.\n\nThe current \"default\" output will give all of the depicted commits\nbefore showing the older commits that are not in the picture, and\nthat is absolutely the right thing to do when you ask \"git log\" to\nview \"the last few\" commits. Imagine what you will see if you used\ngeneration numbers instead of the commit timestamp. You will see\ncommits on the maintenance topic that can later be merged to an\nolder codebase, only after you saw all the development history on\nthe master branch since 1.7.9 release. I do not think we want to\ncall such an output \"the right fix\".\n"},{"id":"197109","messageId":"502D2137.9000504@alum.mit.edu","threadId":"31246","inReplyTo":"87k3wzujuy.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-08-16T16:35:03Z","receivedAt":"2012-08-16T16:35:03Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 08/16/2012 02:00 PM, Thomas Rast wrote:\n> Michael Haggerty writes:\n>\n>> On 08/16/2012 10:51 AM, Thomas Rast wrote:\n>>> I suppose the real problem is that the \"true\" ordering\n>>> is completely obvious as the one ordering that does not require\n>>> preprocessing, but ugly to specify in words. Perhaps we can bikeshed a\n>>> little? How about\n>>>\n>>> By default, commits are shown in an order that coincides with\n>>> `--date-order` on well-behaved history, but is faster to compute.\n>>\n>> Maybe the problem is not the description of the options, but the\n>> options themselves. Why does the behavior default to some mysterious\n>> order that we don't even want to document? Only for the sake of\n>> computational efficiency. This is the tail wagging the dog.\n>>\n>> Why not turn the behavior on its head:\n>>\n>> * Change the default behavior to be something well-defined, easy to\n>> document, and convenient for humans, such as \"topological order with\n>> ties broken by timestamp\" or \"approximate timestamp order, but\n>> respecting dependencies\".\n>>\n>> * Add a new option, --arbitrary-order, that explicitly chooses\n>> efficiency instead of a defined order.\n>\n> I think that would be a rather bad decision, largely because (taking my\n> git.git as an example):\n>\n> $ time git log | head -1\n> commit e5e6172f9060c958e3f0d679cd7049d4007eed2c\n>\n> real 0m0.033s\n> user 0m0.026s\n> sys 0m0.007s\n>\n> $ time git log --date-order | head -1\n> commit e5e6172f9060c958e3f0d679cd7049d4007eed2c\n>\n> real 0m0.429s\n> user 0m0.359s\n> sys 0m0.031s\n>\n> That is, even in medium-sized projects like git.git, any -order option\n> incurs a significant preprocessing time until git-log can show the first\n> commit. It scales linearly with the number of commits in the range, and\n> in a linux.git lying around here is already around 3.9s for the same\n> command.\n\nThanks for timing this; I didn't realize how costly this would be. Just \nto make it even more obvious that this performance regression would bite \nin daily life, consider\n\n $ time git log -1\n\n real 0m0.013s\n user 0m0.000s\n sys 0m0.004s\n\n $ time git log -1 --topo-order\n\n real 0m0.334s\n user 0m0.316s\n sys 0m0.012s\n\nOuch.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"197174","messageId":"874no1hnfg.fsf@thomas.inf.ethz.ch","threadId":"31246","inReplyTo":"7v628i3jiu.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-08-17T09:34:27Z","receivedAt":"2012-08-17T09:34:27Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> The right fix would be to dig up Peff's work on generation number\n>> caching, and modify the algorithm to take generation numbers into\n>> account.\n>\n> I think you are totally wrong here, unless you are talking about a\n> generation number that is different from what I recall from the\n> older discussion.\n\nHrm, now you're making me feel like I missed something. But my\nreasoning goes roughly like this.\n\nConsider the commit graph as a DAG, where the parent pointers are\ndirected edges from child to parent. Thus, tip commits are sources and\nroot commits are sinks. One way to get a valid topo ordering, knowing\nthe complete DAG, is:\n\n while there are vertices left:\n remove any source and emit it\n\n(You can also generate it from the sinks instead; I haven't actually\nchecked what the code currently does. But for the following, we need to\nstart from the sources.)\n\nTo implement this efficiently, one usually keeps track of the set S of\nsources, and inserts vertices that (by removal of their last\nin-neighbour) have become a source.\n\nThe distinction between topo-order and date-order is the preference\ngiven in the choice of source. IIUC, date-order prefers the newest\nsource by committer date (using a priority queue or such for S), and\ntopo-order prefers the source(s) which were parents of the vertex\nremoved in the previous iteration (using a stack for S).\n\nThe problem with this algorithm is that it requires knowledge of the\nDAG[1]. So with --topo-order, git dutifully loads the whole commit\ngraph, and then runs the algorithm, leading to the discussed startup\ndelay.\n\nHowever, suppose we knew generation numbers. I haven't actually looked\ninto the old threads again, but my understanding was that they are\nnumbers g(C) attached to each commit C such that\n\n g(C) = 1 + max(g(P) for P a parent of C) for non-root commits\n\n g(C) = 0 for root commits\n\nThey are invariant given the commit, so they can be cached. And they\nallow us to infer something about ancestry: if g(C)<=g(D), then C cannot\npossibly be a descendant of D.\n\nThe topo order algorithm can be modified to take advantage of them, in\norder to provide incremental processing:\n\n Let S be the set of tentative sources\n\n Let U be the set of vertices whose out-edges are no known yet\n (i.e., the set of commits which haven't been loaded yet)\n\n Let max g(U) denote \"max g(C) taken over all C in U\".\n\n Fill S and U from the revisions given:\n load all positive revisions, let's call this set P\n put all zero-indegree members of P in S\n put all parents of members of P in U (as far as they are not also\n members of P, and therefore loaded already)\n\n while there are any vertices left:\n\n pick any tentative source C from S that we \"want to emit\"\n\n # Ascertain that no unknown commit (from U or further beyond) can be\n # a descendant of C\n while there is a D in U such that g(D) > g(C):\n load D\n remove D from U\n add the parents of D to U if they were not already loaded\n possibly remove some elements of S if their indegree became nonzero\n\n if C was removed from S:\n continue\n\n remove C from the graph and emit it\n\nI hope I got that right. The order of commits is still entirely\ndetermined by the choice of \"any tentative source\", but the algorithm\nshould now stream nicely once the generation numbers are known.\n\n\nFootnotes: \n\n[1] If there are any parent pointers not yet followed, they may in fact\nwind up (over at least one more commit) pointing to the commit you\nwanted to emit next, making that an invalid choice.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197175","messageId":"87sjbletjt.fsf@thomas.inf.ethz.ch","threadId":"31246","inReplyTo":"874no1hnfg.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-17T09:50:30Z","receivedAt":"2012-08-17T09:50:30Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Rast writes:\n\n> Junio C Hamano writes:\n>\n> The topo order algorithm can be modified to take advantage of\n> [generation numbers], in order to provide incremental processing:\n>\n> Let S be the set of tentative sources\n>\n> Let U be the set of vertices whose out-edges are no known yet\n> (i.e., the set of commits which haven't been loaded yet)\n[...]\n> while there are any vertices left:\n>\n> pick any tentative source C from S that we \"want to emit\"\n>\n> # Ascertain that no unknown commit (from U or further beyond) can be\n> # a descendant of C\n> while there is a D in U such that g(D) > g(C):\n> load D\n> remove D from U\n> add the parents of D to U if they were not already loaded\n> possibly remove some elements of S if their indegree became nonzero\n>\n> if C was removed from S:\n> continue\n>\n> remove C from the graph and emit it\n\nBy the way, this does bump the runtime of the algorithm a bit, depending\non the data structure used for U. Recall that ordinary topo-sort with a\nstack for S (i.e., --topo-order) runs linearly with the number of\nvertices.\n\nIf we use a priority queue for U, which lets us get at the\nhighest-generation unknown commits easily, it potentially goes to n log n \nif U reaches linear size at some point.\n\nThat shouldn't hurt too much of course, since on the one hand it should\nrarely actually get that big, and OTOH --date-order has n log n runtime\nanyway (using a priority queue for S).\n\nThanks for challenging me on my \"it should work\" feeling. It was quite\ninteresting to actually think it through and write down a workable\nalgorithm.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197192","messageId":"7v1uj5wi72.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"874no1hnfg.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-17T17:18:25Z","receivedAt":"2012-08-17T17:18:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> However, suppose we knew generation numbers. I haven't actually looked\n> into the old threads again, but my understanding was that they are\n> numbers g(C) attached to each commit C such that\n>\n> g(C) = 1 + max(g(P) for P a parent of C) for non-root commits\n>\n> g(C) = 0 for root commits\n>\n> They are invariant given the commit, so they can be cached.\n> ...\n> I hope I got that right. The order of commits is still entirely\n> determined by the choice of \"any tentative source\", but the algorithm\n> should now stream nicely once the generation numbers are known.\n\nThat matches the definition of generation number I remember from the\nold discussion. Now look at the illustration in this discussion\nagain:\n\n ---A---B---C---D\n \\\n ---1---2---3---4---* = HEAD\n\nand an excerpt from the message you are respoding to:\n\n Think of the sample history above, and imagine\n that the numbered ones are based on the current 'master', but that\n the alphabet ones are based on an ancient maintenance release that\n is 1000 generations behind (think of me running the command after\n finishing the day's integration cycle, sitting at the tip of 'pu',\n where the last topic merged is meant to be eventually merged to\n maint-1.7.9). All of the commits depicted in the picture will have\n the commit timestamps in the past few hours. Ancestors of A and 1,\n not drawn in the picture, were made yesterday or before.\n\nThe numbered commits 1 2 3 4 are building on top of recent \"master\",\nwhile alphabetized A B C D are building on aged maintenance track.\nThe difference in generation numbers between 1 and 2, 2 and 3,... A\nand B, B and C, C and D are all one, and HEAD (the tip of 'pu') would\nhave generation number of commit 4 plus 1, as commit 4's generation\nnumber would be a thousand or more ahead of that of commit D. And\nthere are a thousand ancestors of '1' with larger generation numbers\nthan 'D'.\n\nWhen the user runs \"git log\" (i.e. the casual \"the last few commit\"\nmacthes), the expectation of the user is \"I want to see what I did\nrecently\". If you substituted the commit timestamp with such a\ngeneration number, how would that expectation satisified?\n\nGeneration numbers is a clean solution to avoid giving an incorrect\nrange result when there are clock skews (cf. the use of SLOP in\nrevision.c::still_interesting()), but it is not a good substitute\nwhen the user is more interested in absolutely correct topology (in\nother words, the user is more interested in both rougly wallclock\ntime order and seeing the result soon --- which brings us back to\nthe original \"short latency is vastly preferred _as long as_ it\nproduces the result the user wants to see\").\n"},{"id":"197196","messageId":"87obm9a07z.fsf@thomas.inf.ethz.ch","threadId":"31246","inReplyTo":"7v1uj5wi72.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-17T17:37:36Z","receivedAt":"2012-08-17T17:37:36Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> However, suppose we knew generation numbers. I haven't actually looked\n>> into the old threads again, but my understanding was that they are\n>> numbers g(C) attached to each commit C such that\n>>\n>> g(C) = 1 + max(g(P) for P a parent of C) for non-root commits\n>>\n>> g(C) = 0 for root commits\n>>\n>> They are invariant given the commit, so they can be cached.\n>> ...\n>> I hope I got that right. The order of commits is still entirely\n>> determined by the choice of \"any tentative source\", but the algorithm\n>> should now stream nicely once the generation numbers are known.\n>\n> That matches the definition of generation number I remember from the\n> old discussion. Now look at the illustration in this discussion\n> again:\n>\n> ---A---B---C---D\n> \\\n> ---1---2---3---4---* = HEAD\n[...]\n> The numbered commits 1 2 3 4 are building on top of recent \"master\",\n> while alphabetized A B C D are building on aged maintenance track.\n> The difference in generation numbers between 1 and 2, 2 and 3,... A\n> and B, B and C, C and D are all one, and HEAD (the tip of 'pu') would\n> have generation number of commit 4 plus 1, as commit 4's generation\n> number would be a thousand or more ahead of that of commit D. And\n> there are a thousand ancestors of '1' with larger generation numbers\n> than 'D'.\n>\n> When the user runs \"git log\" (i.e. the casual \"the last few commit\"\n> macthes), the expectation of the user is \"I want to see what I did\n> recently\". If you substituted the commit timestamp with such a\n> generation number, how would that expectation satisified?\n\nUmm, have you looked at the algorithm I proposed?\n\nIt does not substitute the generation numbers for anything, let alone\nthe date. It merely uses them to determine a point where it knows\n\"enough\" of the history to be able to emit the next commit; that is,\nwhere it can use the generation numbers to prove that no unknown commit\ncan be a descendant of what it wants to emit next.\n\nIt does *not* have to use the generation numbers in the final ordering\nof the commits. That final order is determined by how the algorithm\nchooses the next candidate commit. If you use a stack, it winds up\nbeing --topo-order. If you use a date-ordered priority queue, it\nbecomes --date-order.\n\nSo really, this is only about modifying the algorithm that generates the\nexisting order to allow for streaming output as it reads through\nhistory.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197198","messageId":"7vk3wxv2lo.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"874no1hnfg.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-17T17:40:35Z","receivedAt":"2012-08-17T17:40:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> I hope I got that right. The order of commits is still entirely\n> determined by the choice of \"any tentative source\", but the algorithm\n> should now stream nicely once the generation numbers are known.\n\nThanks for an intereseting read.\n\nEven though generation numbers are not always a good subsitute for\ntimestamps depending on the use (see the other message), the algorithm\nto compute \"topo-order\" can take advantage of the generation numbers\nwhen they are available, as you illustrated in your message.\n\nWe may want to think about adding a new field to the commit object,\nwith a fallback mechanism to an external \"cache\" that is generated\non-demand.\n\nOnce the mechanism is in place so that any caller of parse_commit()\ncan depend on having a reliable .generation field in the commit\nobject it receives from the function, we can start updating various\ntraversal algorithms to take advantage of this new information.\n"},{"id":"197204","messageId":"7vr4r5tml3.fsf@alter.siamese.dyndns.org","threadId":"31246","inReplyTo":"87obm9a07z.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2] rev-list docs: clarify --topo-order description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-17T18:11:52Z","receivedAt":"2012-08-17T18:11:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Umm, have you looked at the algorithm I proposed?\n> ...\n> So really, this is only about modifying the algorithm that generates the\n> existing order to allow for streaming output as it reads through\n> history.\n\nSorry, I thought you were optimizing sort_in_topological_order()\nfound in commit.c, not the callchain that forms get_revision()\nin revision.c.\n"}]}