{"thread":{"id":"11998","subject":"Add \"--show-all\" revision walker flag for debugging","startedAt":"2008-02-09T22:02:07Z","lastAt":"2008-02-11T16:39:16Z","messageCount":20,"participants":["Linus Torvalds","Johannes Schindelin","Nicolas Pitre","Junio C Hamano","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"68127","messageId":"alpine.LFD.1.00.0802091341210.2896@woody.linux-foundation.org","threadId":"11998","inReplyTo":null,"subject":"Add \"--show-all\" revision walker flag for debugging","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-09T22:02:07Z","receivedAt":"2008-02-09T22:02:07Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nSo the kernel merge window for 2.6.25 is closing today (or possibly \ntomorrow if I feel like it), and I've already mentally closed it, so I'm \nstarting to free up some resources to look at the interesting problem with \nscrewed-up commit dates confusing our commit walker into thinking that \nsome uninteresting commit isn't actually uninteresting due to not \ntraversing the uninteresting chain deep enough.\n\nBut one of the things I noticed is that it's really not very easy to \nvisualize the commit walker, because - on purpose - it obvously doesn't \nshow the uninteresting commits!\n\nSo here's a patch that adds a \"--show-all\" flag to the revision walker, \nwhich will make it show uninteresting commits too, and they'll have a '*' \nin front of them (it also fixes a logic error for !verbose_header for \nboundary commits - we should show the '-' even if left_right isn't shown).\n\nIt also updates 'gitk' to show those negative commits in gray. Whether \nthat's the right color choice or not, I'll leave to bikeshedders, but it \nlooks fairly neutral, and shows the differences pretty well.\n\nIt actually is interesting even for the cases that git doesn't have any \nproblems with, ie for the kernel you can do\n\n\tgitk -d --show-all v2.6.24..\n\nand you see just how far down it has to parse things to see it all. The \nuse of \"-d\" is a good idea, since the date-ordered toposort is much better \nat showing why it goes deep down (ie the date of some of those commits \nafter 2.6.24 is much older, because they were merged from trees that \nweren't rebased).\n\nSo I think this is a useful feature even for non-debugging - just to \nvisualize what git does internally more.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nHeh. Amusingly, the changes to gitk were much bigger than the trivial \nchanges to core git routines themselves. The log-tree.c diffstat is a bit \nbigger just because of the logic fix (making it more than just another \nadded \"else if ()\" statement), while much of the revision.c patch is just \nthe argument parsing ;)\n\n builtin-rev-list.c |    2 ++\n gitk-git/gitk      |   15 ++++++++-------\n log-tree.c         |   12 ++++++++----\n revision.c         |    9 ++++++++-\n revision.h         |    1 +\n 5 files changed, 27 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex de80158..5966199 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -60,6 +60,8 @@ static void show_commit(struct commit *commit)\n \t\tfputs(header_prefix, stdout);\n \tif (commit->object.flags & BOUNDARY)\n \t\tputchar('-');\n+\telse if (commit->object.flags & UNINTERESTING)\n+\t\tputchar('^');\n \telse if (revs.left_right) {\n \t\tif (commit->object.flags & SYMMETRIC_LEFT)\n \t\t\tputchar('<');\ndiff --git a/gitk-git/gitk b/gitk-git/gitk\nindex 5560e4d..90d9b61 100644\n--- a/gitk-git/gitk\n+++ b/gitk-git/gitk\n@@ -240,11 +240,12 @@ proc getcommitlines {fd view}  {\n \tset listed 1\n \tif {$j >= 0 && [string match \"commit *\" $cmit]} {\n \t    set ids [string range $cmit 7 [expr {$j - 1}]]\n-\t    if {[string match {[-<>]*} $ids]} {\n+\t    if {[string match {[-^<>]*} $ids]} {\n \t\tswitch -- [string index $ids 0] {\n \t\t    \"-\" {set listed 0}\n-\t\t    \"<\" {set listed 2}\n-\t\t    \">\" {set listed 3}\n+\t\t    \"^\" {set listed 2}\n+\t\t    \"<\" {set listed 3}\n+\t\t    \">\" {set listed 4}\n \t\t}\n \t\tset ids [string range $ids 1 end]\n \t    }\n@@ -3627,23 +3628,23 @@ proc drawcmittext {id row col} {\n     global linehtag linentag linedtag selectedline\n     global canvxmax boldrows boldnamerows fgcolor nullid nullid2\n \n-    # listed is 0 for boundary, 1 for normal, 2 for left, 3 for right\n+    # listed is 0 for boundary, 1 for normal, 2 for negative, 3 for left, 4 for right\n     set listed [lindex $commitlisted $row]\n     if {$id eq $nullid} {\n \tset ofill red\n     } elseif {$id eq $nullid2} {\n \tset ofill green\n     } else {\n-\tset ofill [expr {$listed != 0? \"blue\": \"white\"}]\n+\tset ofill [expr {$listed != 0 ? $listed == 2 ? \"gray\" : \"blue\" : \"white\"}]\n     }\n     set x [xc $row $col]\n     set y [yc $row]\n     set orad [expr {$linespc / 3}]\n-    if {$listed <= 1} {\n+    if {$listed <= 2} {\n \tset t [$canv create oval [expr {$x - $orad}] [expr {$y - $orad}] \\\n \t\t   [expr {$x + $orad - 1}] [expr {$y + $orad - 1}] \\\n \t\t   -fill $ofill -outline $fgcolor -width 1 -tags circle]\n-    } elseif {$listed == 2} {\n+    } elseif {$listed == 3} {\n \t# triangle pointing left for left-side commits\n \tset t [$canv create polygon \\\n \t\t   [expr {$x - $orad}] $y \\\ndiff --git a/log-tree.c b/log-tree.c\nindex 1f3fcf1..dd110ca 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -149,10 +149,12 @@ void show_log(struct rev_info *opt, const char *sep)\n \n \topt->loginfo = NULL;\n \tif (!opt->verbose_header) {\n-\t\tif (opt->left_right) {\n-\t\t\tif (commit->object.flags & BOUNDARY)\n-\t\t\t\tputchar('-');\n-\t\t\telse if (commit->object.flags & SYMMETRIC_LEFT)\n+\t\tif (commit->object.flags & BOUNDARY)\n+\t\t\tputchar('-');\n+\t\telse if (commit->object.flags & UNINTERESTING)\n+\t\t\tputchar('^');\n+\t\telse if (opt->left_right) {\n+\t\t\tif (commit->object.flags & SYMMETRIC_LEFT)\n \t\t\t\tputchar('<');\n \t\t\telse\n \t\t\t\tputchar('>');\n@@ -250,6 +252,8 @@ void show_log(struct rev_info *opt, const char *sep)\n \t\t\tfputs(\"commit \", stdout);\n \t\tif (commit->object.flags & BOUNDARY)\n \t\t\tputchar('-');\n+\t\telse if (commit->object.flags & UNINTERESTING)\n+\t\t\tputchar('^');\n \t\telse if (opt->left_right) {\n \t\t\tif (commit->object.flags & SYMMETRIC_LEFT)\n \t\t\t\tputchar('<');\ndiff --git a/revision.c b/revision.c\nindex 6e85aaa..158727c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -581,7 +581,8 @@ static int limit_list(struct rev_info *revs)\n \t\t\tmark_parents_uninteresting(commit);\n \t\t\tif (everybody_uninteresting(list))\n \t\t\t\tbreak;\n-\t\t\tcontinue;\n+\t\t\tif (!revs->show_all)\n+\t\t\t\tcontinue;\n \t\t}\n \t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n \t\t\tcontinue;\n@@ -1055,6 +1056,10 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \t\t\t\trevs->dense = 0;\n \t\t\t\tcontinue;\n \t\t\t}\n+\t\t\tif (!strcmp(arg, \"--show-all\")) {\n+\t\t\t\trevs->show_all = 1;\n+\t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tif (!strcmp(arg, \"--remove-empty\")) {\n \t\t\t\trevs->remove_empty_trees = 1;\n \t\t\t\tcontinue;\n@@ -1438,6 +1443,8 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\treturn commit_ignore;\n \tif (revs->unpacked && has_sha1_pack(commit->object.sha1, revs->ignore_packed))\n \t\treturn commit_ignore;\n+\tif (revs->show_all)\n+\t\treturn commit_show;\n \tif (commit->object.flags & UNINTERESTING)\n \t\treturn commit_ignore;\n \tif (revs->min_age != -1 && (commit->date > revs->min_age))\ndiff --git a/revision.h b/revision.h\nindex 8572315..b5f01f8 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -33,6 +33,7 @@ struct rev_info {\n \t\t\tprune:1,\n \t\t\tno_merges:1,\n \t\t\tno_walk:1,\n+\t\t\tshow_all:1,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n \t\t\tlifo:1,\n"},{"id":"68135","messageId":"alpine.LFD.1.00.0802091531220.2896@woody.linux-foundation.org","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802091341210.2896@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-09T23:52:12Z","receivedAt":"2008-02-09T23:52:12Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Feb 2008, Linus Torvalds wrote:\n> \n> So here's a patch that adds a \"--show-all\" flag to the revision walker, \n> which will make it show uninteresting commits too, and they'll have a '*' \n> in front of them (it also fixes a logic error for !verbose_header for \n> boundary commits - we should show the '-' even if left_right isn't shown).\n\nAnd here's a slight expansion patch on top of the above\n\nIt does:\n\n - when it actually breaks out due to the \"everybody_uninteresting()\" \n   case, it adds the uninteresting commits (both the one it's looking at \n   now, and the list of pending ones) to the list\n\n   This way, we really list *all* the commits we've looked at\n\n - Because we now end up listing commits we may not even have been parsed \n   at all \"show_log\" and \"show_commit\" need to protect against commits \n   that don't have a commit buffer entry.\n\nThat second part is debatable just how it should work. Maybe we shouldn't \nshow such entries at all (with this patch those entries do get shown, they \njust don't get any message shown with them). But I think this is a useful \ncase.\n\n\t\tLinus\n\n---\n builtin-rev-list.c |    2 +-\n log-tree.c         |    3 +++\n revision.c         |   11 ++++++++++-\n 3 files changed, 14 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 5966199..7163116 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -86,7 +86,7 @@ static void show_commit(struct commit *commit)\n \telse\n \t\tputchar('\\n');\n \n-\tif (revs.verbose_header) {\n+\tif (revs.verbose_header && commit->buffer) {\n \t\tstruct strbuf buf;\n \t\tstrbuf_init(&buf, 0);\n \t\tpretty_print_commit(revs.commit_format, commit,\ndiff --git a/log-tree.c b/log-tree.c\nindex dd110ca..e9ba6df 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -282,6 +282,9 @@ void show_log(struct rev_info *opt, const char *sep)\n \t\t}\n \t}\n \n+\tif (!commit->buffer)\n+\t\treturn;\n+\n \t/*\n \t * And then the pretty-printed message itself\n \t */\ndiff --git a/revision.c b/revision.c\nindex 158727c..76faf4b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -558,6 +558,12 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n \tfree_patch_ids(&ids);\n }\n \n+static void add_to_list(struct commit_list **p, struct commit *commit, struct commit_list *n)\n+{\n+\tp = &commit_list_insert(commit, p)->next;\n+\t*p = n;\n+}\n+\n static int limit_list(struct rev_info *revs)\n {\n \tstruct commit_list *list = revs->commits;\n@@ -579,8 +585,11 @@ static int limit_list(struct rev_info *revs)\n \t\t\treturn -1;\n \t\tif (obj->flags & UNINTERESTING) {\n \t\t\tmark_parents_uninteresting(commit);\n-\t\t\tif (everybody_uninteresting(list))\n+\t\t\tif (everybody_uninteresting(list)) {\n+\t\t\t\tif (revs->show_all)\n+\t\t\t\t\tadd_to_list(p, commit, list);\n \t\t\t\tbreak;\n+\t\t\t}\n \t\t\tif (!revs->show_all)\n \t\t\t\tcontinue;\n \t\t}\n"},{"id":"68139","messageId":"alpine.LSU.1.00.0802100110450.11591@racer.site","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802091341210.2896@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-02-10T01:12:42Z","receivedAt":"2008-02-10T01:12:42Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 9 Feb 2008, Linus Torvalds wrote:\n\n> I'm starting to free up some resources to look at the interesting \n> problem with screwed-up commit dates confusing our commit walker into \n> thinking that some uninteresting commit isn't actually uninteresting due \n> to not traversing the uninteresting chain deep enough.\n\nI was thinking the other night why I did not like the generation header.  \nAnd I found out why: it is redundant information.\n\nSo why not have some local \"cache\" which maintains the generation numbers \nfor the commits?  (Much like the \"notes\" cache I showed last year?)\n\nHmm?\n\nCiao,\nDscho\n"},{"id":"68140","messageId":"alpine.LFD.1.00.0802091720010.2896@woody.linux-foundation.org","threadId":"11998","inReplyTo":"alpine.LSU.1.00.0802100110450.11591@racer.site","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-10T01:22:20Z","receivedAt":"2008-02-10T01:22:20Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 10 Feb 2008, Johannes Schindelin wrote:\n> \n> I was thinking the other night why I did not like the generation header.  \n> And I found out why: it is redundant information.\n\nActually, that's not the real issue.\n\nThe real issue is that it doesn't work. I thought about it, and with \nmultiple roots (which _can_ get merged together) it just isn't something \nthat actually helps.\n\nIf you couldn't merge across roots, you could have a \"uuid+generation \nheader\", but the moment you have multiple roots it actually gets quite \ncomplex.\n\nSo scratch the generation header.  It's not the answer.\n\nAnd I do think that we can do it without it. I'm still thinking about how \nto do it efficiently, but I think I can get there. I just haven't had the \ntime to sit down and really think it through and try out my ideas yet.\n\n\t\tLinus\n"},{"id":"68142","messageId":"alpine.LFD.1.00.0802092016540.2732@xanadu.home","threadId":"11998","inReplyTo":"alpine.LSU.1.00.0802100110450.11591@racer.site","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-02-10T01:28:59Z","receivedAt":"2008-02-10T01:28:59Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 10 Feb 2008, Johannes Schindelin wrote:\n\n> Hi,\n> \n> On Sat, 9 Feb 2008, Linus Torvalds wrote:\n> \n> > I'm starting to free up some resources to look at the interesting \n> > problem with screwed-up commit dates confusing our commit walker into \n> > thinking that some uninteresting commit isn't actually uninteresting due \n> > to not traversing the uninteresting chain deep enough.\n> \n> I was thinking the other night why I did not like the generation header.  \n> And I found out why: it is redundant information.\n> \n> So why not have some local \"cache\" which maintains the generation numbers \n> for the commits?  (Much like the \"notes\" cache I showed last year?)\n\nAbsolutely.\n\nI, too, have some reservations about adding any kind of generation \nheader to commit objects.  First because it can be generated and \nmaintained locally, just like the pack index.  But also because its \nusefulness has not been proven in all possible graph topologies, and \nadding it to the commit header pretty much deny any further \nmodifications/improvements on it, if for example some other kind of \ngeneration notation becomes advantageous to use.\n\nSo please don't put it into the commit object format.  The object \ndatabase should ultimately contain only data that cannot be regenerated.\n\n\nNicolas\n"},{"id":"68143","messageId":"alpine.LSU.1.00.0802100127160.11591@racer.site","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802091720010.2896@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-02-10T01:29:30Z","receivedAt":"2008-02-10T01:29:30Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 9 Feb 2008, Linus Torvalds wrote:\n\n> On Sun, 10 Feb 2008, Johannes Schindelin wrote:\n> > \n> > I was thinking the other night why I did not like the generation \n> > header.  And I found out why: it is redundant information.\n> \n> Actually, that's not the real issue.\n> \n> The real issue is that it doesn't work. I thought about it, and with \n> multiple roots (which _can_ get merged together) it just isn't something \n> that actually helps.\n\nI don't see it.  If G(c) >= 1 + max(G(c^) | c^ is a parent of c), then it \n_should_ work.  And then, I think it is _much_ better to just cache it \nlocally (if you care enough about it, i.e. if you set a certain config \noption that triggers possibly expensive one-shot caching) than have it in \nthe commit object (where the information could be just plain wrong).\n\nCiao,\nDscho\n"},{"id":"68144","messageId":"alpine.LSU.1.00.0802100130090.11591@racer.site","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802092016540.2732@xanadu.home","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-02-10T01:30:30Z","receivedAt":"2008-02-10T01:30:30Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 9 Feb 2008, Nicolas Pitre wrote:\n\n> I, too, have some reservations about adding any kind of generation \n> header to commit objects.  First because it can be generated and \n> maintained locally, just like the pack index.  But also because its \n> usefulness has not been proven in all possible graph topologies, and \n> adding it to the commit header pretty much deny any further \n> modifications/improvements on it, if for example some other kind of \n> generation notation becomes advantageous to use.\n\nI fully agree.\n\nCiao,\nDscho\n"},{"id":"68165","messageId":"7vy79t4fld.fsf@gitster.siamese.dyndns.org","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802091720010.2896@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-10T04:09:50Z","receivedAt":"2008-02-10T04:09:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> The real issue is that it doesn't work. I thought about it, and with \n> multiple roots (which _can_ get merged together) it just isn't something \n> that actually helps.\n>\n> If you couldn't merge across roots, you could have a \"uuid+generation \n> header\", but the moment you have multiple roots it actually gets quite \n> complex.\n>\n> So scratch the generation header.  It's not the answer.\n\nI do not think multiple roots can be helped without going all\nthe way down to the roots, and I think it can be proven.\n\n> And I do think that we can do it without it. I'm still thinking about how \n> to do it efficiently, but I think I can get there. I just haven't had the \n> time to sit down and really think it through and try out my ideas yet.\n\nGeneration number would on the other hand eliminate the issue of\nclock skew if heads are connected, and I think it also can be\nproven.\n\nBoth proofs need the axiom \"there is no loop in the commit\nancestry graph\", but that is something we already rely on in the\nmerge-base computation.\n"},{"id":"68168","messageId":"7vd4r54f1d.fsf@gitster.siamese.dyndns.org","threadId":"11998","inReplyTo":"7vy79t4fld.fsf@gitster.siamese.dyndns.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-10T04:21:50Z","receivedAt":"2008-02-10T04:21:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n>\n>> The real issue is that it doesn't work. I thought about it, and with \n>> multiple roots (which _can_ get merged together) it just isn't something \n>> that actually helps.\n>>\n>> If you couldn't merge across roots, you could have a \"uuid+generation \n>> header\", but the moment you have multiple roots it actually gets quite \n>> complex.\n>>\n>> So scratch the generation header.  It's not the answer.\n>\n> I do not think multiple roots can be helped without going all\n> the way down to the roots, and I think it can be proven.\n\nAh, please scratch that comment.  I was puzzled but did not\nunderstand what you meant by uuid+generation.\n\nYou are right.  If we cannot tell if we are dealing with\ndisconnected history, we would always need to play safe and do\nthe clean-up like what I suggested earlier using merge-base\ntraversal, which could be costly, and we do not want to pay that\npenalty in a connected history, which should be the normal case.\n\nGeneration header does not help us detect that case, so it is\nnot useful.\n"},{"id":"68169","messageId":"7v63wx4dzk.fsf@gitster.siamese.dyndns.org","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802091531220.2896@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-10T04:44:31Z","receivedAt":"2008-02-10T04:44:31Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> And here's a slight expansion patch on top of the above\n>\n> It does:\n>\n>  - when it actually breaks out due to the \"everybody_uninteresting()\" \n>    case, it adds the uninteresting commits (both the one it's looking at \n>    now, and the list of pending ones) to the list\n>\n>    This way, we really list *all* the commits we've looked at\n>\n>  - Because we now end up listing commits we may not even have been parsed \n>    at all \"show_log\" and \"show_commit\" need to protect against commits \n>    that don't have a commit buffer entry.\n>\n> That second part is debatable just how it should work. Maybe we shouldn't \n> show such entries at all (with this patch those entries do get shown, they \n> just don't get any message shown with them). But I think this is a useful \n> case.\n\nShowing them would probably be useful (definitely for\ndebugging), but I do not think it is useful not to show the\nbuffer contents (i.e. adding without parsing).\n\nIt _might_ mean that the excess uninteresting ones we take out\nfrom \"list\" can be distinguished from the ones that we did look\nat (and once thought they were worth keeping), but I do not\nthink it is reliable information.  The command line parser may\nhave caused them to be parsed independent from what the revision\ntraversal did.\n\nSo I think it would make more sense to parse them while we add\nthem to the \"newlist\", and if we really want to distinguish them\nfrom others we would want to mark them separately with another\nflag bit.\n\nOr unparse them when we add them to the \"newlist\".\n"},{"id":"68255","messageId":"m3myq8fwdx.fsf@localhost.localdomain","threadId":"11998","inReplyTo":"alpine.LSU.1.00.0802100130090.11591@racer.site","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-02-10T20:17:21Z","receivedAt":"2008-02-10T20:17:21Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> On Sat, 9 Feb 2008, Nicolas Pitre wrote:\n> \n> > I, too, have some reservations about adding any kind of generation \n> > header to commit objects.  First because it can be generated and \n> > maintained locally, just like the pack index.  But also because its \n> > usefulness has not been proven in all possible graph topologies, and \n> > adding it to the commit header pretty much deny any further \n> > modifications/improvements on it, if for example some other kind of \n> > generation notation becomes advantageous to use.\n> \n> I fully agree.\n\nI think I'd agree, also because without 'generation' (and 'roots')\ncommit object header being there from beginning it is not clear when\nto calculate it: the first few commits with it would be costly.\nBesides graft and shallow information is local, and it affect commit\ntraversal.\n\nI was thinking about pack-index like file, either directly mapping\n\"sha1 -> generation + roots\", or indirectly \"sha1 -> offset\", \n\"offset -> generation + roots\".\n\n\nP.S. Would having generation + roots be enough?\n\n  gen(rev) = max_i { gen(i) + 1 : i in parents(rev) } || 1\n\n  roots(rev) = { rev  if rev is a root (parentless) commit \n               { union of roots of parents of a commit otherwise\n\nUnion in the sense of set sum.\n\nNote that if roots was to be saved in commit header, then it couldn't\nbe as simple as commit-id for root commits: no self links. It would\nhave to be empty for root commits, and the \"union of roots\" would have\nto be modified to \"union of roots or commit ids for root commits, of\neach of parents of a commit\".\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"68270","messageId":"alpine.LFD.1.00.0802101241590.2896@woody.linux-foundation.org","threadId":"11998","inReplyTo":"m3myq8fwdx.fsf@localhost.localdomain","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-10T20:50:17Z","receivedAt":"2008-02-10T20:50:17Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 10 Feb 2008, Jakub Narebski wrote:\n> \n> P.S. Would having generation + roots be enough?\n\nI'm wavering here. Maybe just \"generation\" works (the longest path from \nany root), because what we are looking for is essentially \"guarantee that \nthis commit cannot possibly be reached from that other commit\", and I \nguess a simple generation count actually does work for that (if the \ngeneration of \"x\" is smaller than the generation of \"y\", we definitely \ncannot reach y from x).\n\nAt the same time, I'm still not really convinced we need to add the \nredundant info. I do think I *should* have designed it that way to start \nwith (and I thought so two years ago - blaah), so the strongest reason for \n\"we should add generation numbers\" at least for me is that I actually \nthink it's a GoodThing(tm) to have.\n\nBut adding it is a pretty invasive thing, and would force people to \nupgrade (it really isn't backwards compatible - old versions of git would \nimmediately refuse to touch archives with even just a single top commit \nthat has a generation number in it, unless we'd hide it at the end of the \nbuffer and just uglify things in general).\n\nSo even if it does work, the advantage isn't big enough for me to think \nit's really worth it. I'd *really* prefer to not have a flag day here, and \nthe fact is, it's redundant information _and_ it fundamentally doesn't \nwork with grafting anyway, so even if we were able to start from scratch, \nwe'd then have to seriously consider dropping grafts.\n\nSo let's work at not needing it, rather than argue whether we could use it \nor not ;)\n\n\t\tLinus\n"},{"id":"68272","messageId":"alpine.LFD.1.00.0802101558200.2732@xanadu.home","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802101241590.2896@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-02-10T21:04:59Z","receivedAt":"2008-02-10T21:04:59Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 10 Feb 2008, Linus Torvalds wrote:\n\n> At the same time, I'm still not really convinced we need to add the \n> redundant info. I do think I *should* have designed it that way to start \n> with (and I thought so two years ago - blaah), so the strongest reason for \n> \"we should add generation numbers\" at least for me is that I actually \n> think it's a GoodThing(tm) to have.\n> \n> But adding it is a pretty invasive thing, and would force people to \n> upgrade (it really isn't backwards compatible - old versions of git would \n> immediately refuse to touch archives with even just a single top commit \n> that has a generation number in it, unless we'd hide it at the end of the \n> buffer and just uglify things in general).\n\nRepeating myself: for one, I'm rather against any such generation \nheaders in the commit object, and so is Dscho.\n\nWhy?  Because it doesn't have to live in the commit object at all.\n\nJust like we have a locally managed pack index file, we can have a \nlocally managed \"index of generations\" file just fine.\n\n\nNicolas\n"},{"id":"68288","messageId":"200802102353.40230.jnareb@gmail.com","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802101241590.2896@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-02-10T22:53:39Z","receivedAt":"2008-02-10T22:53:39Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Sat, 10 Feb 2008, Linus Torvalds wrote:\n> \n> On Sun, 10 Feb 2008, Jakub Narebski wrote:\n> > \n> > P.S. Would having generation + roots be enough?\n>\n> I'm wavering here. Maybe just \"generation\" works (the longest path from \n> any root), because what we are looking for is essentially \"guarantee that \n> this commit cannot possibly be reached from that other commit\", and I \n> guess a simple generation count actually does work for that (if the \n> generation of \"x\" is smaller than the generation of \"y\", we definitely \n> cannot reach y from x).\n\nWell, \"generation\" number alone would work quote well as an exclusion\nmechanism; generation + roots would work better, I think.\n\nLets take for an example the following revision graph:\n\nroots: a    a    a    aA   aA\ngen:   1    2    3    4    5\n\n       a----b----c----d----e\n                     /\n            A----B--/\n\ngen:        1    2\nroots:      A    A\n\nFor example lone generation number is enough to decide that 'c'\n(generation 3) cannot be reached from 'a' (generation 1 < 3), and\nthat 'c' (generation 3) cannot be reached from 'B' (generation 2 < 3).\nRoots allow for easy check that 'B' (gen: 2, roots: A) cannot be\nreached from 'c' (roots: a, and A \\not\\in a), but can be reached\nfrom 'e' (gen: 5 > 2, roots: aA \\ni a).\n\nWhat I don't know if generation number would be enough to avoid\n\"going to root\" or \"going to common ancestor\" costly case when\ncalculating excluded commits.\n\n> At the same time, I'm still not really convinced we need to add the \n> redundant info. I do think I *should* have designed it that way to start \n> with (and I thought so two years ago - blaah), so the strongest reason for \n> \"we should add generation numbers\" at least for me is that I actually \n> think it's a GoodThing(tm) to have.\n\nWhile this information can be calculated from revision graph it is\nI think costly enough that it truly would be better to have it in\ncommit object.\n\nWell, we could always start using core.repositoryFormatVersion ;-)\n\n> But adding it is a pretty invasive thing, and would force people to \n> upgrade (it really isn't backwards compatible - old versions of git would \n> immediately refuse to touch archives with even just a single top commit \n> that has a generation number in it, unless we'd hide it at the end of the \n> buffer and just uglify things in general).\n\nWell, we could always add it as a local (per repository) \"cache\".\nWith only generation numbers we could use pack-index-like format\nto store a mapping \"commit sha-1 => generation number\", just like\nnow pack index stores mapping \"object sha-1 => offset in pack\".\n\nIf we want to store also roots, we could either map \n\"commit sha-1 => generation number, roots set offset / id\" (constant\nlength value)[*1*], or have gen-*.gen file with generation numbers\nand roots, and gen-*.idx as index to that file.\n\n\n[*1*] If I understand math correctly it would limit us in theory to\nup to 64 roots (git.git has 8 roots IIRC).\n-- \nJakub Narebski\nPoland\n"},{"id":"68290","messageId":"alpine.LFD.1.00.0802101507100.2896@woody.linux-foundation.org","threadId":"11998","inReplyTo":"200802102353.40230.jnareb@gmail.com","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-10T23:11:10Z","receivedAt":"2008-02-10T23:11:10Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 10 Feb 2008, Jakub Narebski wrote:\n> \n> Well, we could always add it as a local (per repository) \"cache\".\n> With only generation numbers we could use pack-index-like format\n> to store a mapping \"commit sha-1 => generation number\", just like\n> now pack index stores mapping \"object sha-1 => offset in pack\".\n\nYes, and even embedding this in the pack-file (or perhaps, the index, as a \nnew index extension) is probably a good idea.\n\n> If we want to store also roots, we could either map \n> \"commit sha-1 => generation number, roots set offset / id\" (constant\n> length value)[*1*], or have gen-*.gen file with generation numbers\n> and roots, and gen-*.idx as index to that file.\n\nThe thing is, the roots are almost never actually interesting. Very seldom \ndo you have any issue with different commits having different roots. So I \nreally don't think it's worth it, considering that it's also much more \ncomplicated than just adding a sequence number to each commit.\n\n\t\tLinus\n"},{"id":"68305","messageId":"200802110224.48790.jnareb@gmail.com","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802101507100.2896@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-02-11T01:24:48Z","receivedAt":"2008-02-11T01:24:48Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Linus Torvalds wrote:\n> On Sun, 10 Feb 2008, Jakub Narebski wrote:\n> > \n> > Well, we could always add it as a local (per repository) \"cache\".\n> > With only generation numbers we could use pack-index-like format\n> > to store a mapping \"commit sha-1 => generation number\", just like\n> > now pack index stores mapping \"object sha-1 => offset in pack\".\n> \n> Yes, and even embedding this in the pack-file (or perhaps, the index, as a \n> new index extension) is probably a good idea.\n\nErrr... index is per workarea (per checkout), and this information\nis per repository, so IMHO storing this info in an index (dircache)\nis a layering violation. Unless you were talking about pack-file-index.\n\nI think that separate file is better idea, this way we can update\ngeneration info lazily: when we went to the root or project whose\nall parents have generatrion number, then we save gen numbers to\nsuch \"cache\" file. If we had to calculate it (even accidentally),\nsave it.\n\n> > If we want to store also roots, we could either map \n> > \"commit sha-1 => generation number, roots set offset / id\" (constant\n> > length value)[*1*], or have gen-*.gen file with generation numbers\n> > and roots, and gen-*.idx as index to that file.\n> \n> The thing is, the roots are almost never actually interesting. Very seldom \n> do you have any issue with different commits having different roots. So I \n> really don't think it's worth it, considering that it's also much more \n> complicated than just adding a sequence number to each commit.\n\nWeren't the cases of multiple roots that were difficult? Storing roots\nwould help with 'hard' (if seldom happening) cases then.\n\n-- \nJakub Narebski\nPoland\n"},{"id":"68310","messageId":"alpine.LFD.1.00.0802102053090.2732@xanadu.home","threadId":"11998","inReplyTo":"200802110224.48790.jnareb@gmail.com","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-02-11T01:59:14Z","receivedAt":"2008-02-11T01:59:14Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 11 Feb 2008, Jakub Narebski wrote:\n\n> Linus Torvalds wrote:\n> > On Sun, 10 Feb 2008, Jakub Narebski wrote:\n> > > \n> > > Well, we could always add it as a local (per repository) \"cache\".\n> > > With only generation numbers we could use pack-index-like format\n> > > to store a mapping \"commit sha-1 => generation number\", just like\n> > > now pack index stores mapping \"object sha-1 => offset in pack\".\n> > \n> > Yes, and even embedding this in the pack-file (or perhaps, the index, as a \n> > new index extension) is probably a good idea.\n> \n> Errr... index is per workarea (per checkout), and this information\n> is per repository, so IMHO storing this info in an index (dircache)\n> is a layering violation. Unless you were talking about pack-file-index.\n\nThe pack index isn't a good idea since one pack doesn't necessarily \ncover the whole of the repository.  A separate new file is the only \nsensible thing to do, if done at all.\n\n\nNicolas\n"},{"id":"68404","messageId":"alpine.LFD.1.00.0802110748370.2920@woody.linux-foundation.org","threadId":"11998","inReplyTo":"200802110224.48790.jnareb@gmail.com","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-11T15:59:33Z","receivedAt":"2008-02-11T15:59:33Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 11 Feb 2008, Jakub Narebski wrote:\n> \n> Errr... index is per workarea (per checkout), and this information\n> is per repository, so IMHO storing this info in an index (dircache)\n> is a layering violation. Unless you were talking about pack-file-index.\n\nI did mean the pack-file index, not the \"cache\" index.\n\n> Weren't the cases of multiple roots that were difficult? Storing roots\n> would help with 'hard' (if seldom happening) cases then.\n\nIt's not that they aren't difficult, it's that they are so rare (ie having \nranges that really *are* separate never happens in practice). So it's not \nworth worrying about from a performance angle.\n\nThe thing that worried me about multiple roots was that they make the \ngeneration numbers essentially \"meaningless\" when compared across totally \nunrelated commits, and might give incorrect results for generation number \ncomparisons as a result.\n\nHowever, I decided that if two commits really *are* totally unrelated and \ndon't share a commit, then:\n\n - yes, the generation number comparison is \"meaningless\"\n\n - BUT: we don't actually care if it's correct or not, because it will \n   never matter: whatever we choose to do, it's correct. Because there are \n   just two choices:\n\n    (a) stop early because everything we have left is uninteresting\n\n        This is correct, because if they have two separate roots, they'll \n        never meet anyway, so from a correctness standpoint they will \n        never change a interesting commit into an uninteresting one.\n\n    (b) continue to the root because we think we might turn something \n        interesting into an uninteresting commit. This may be wasteful \n        (because the generation numbers happened to fool us into thinking \n        we migth care and one is older than the other), but it's still \n        technically _correct_.\n\n        And we really don't need to care about the performance issues \n        since continuing down to the root is what we'd have had to do even \n        without the generation numbers anyway, but more importantly \n        because we simply don't care - if people start doing comparisons \n        across truly independent commits, they are doing something wrong.\n\nSo that's why a generation number is sufficient.\n\nAnd yes, just generating the generation number when repacking is fine. It \nwould mean that unpacked objects don't have generation numbers, but of you \nhave tons and tons of unpacked objects, you have more serious problems \nanyway!\n\n\t\t\tLinus\n"},{"id":"68408","messageId":"200802111726.28001.jnareb@gmail.com","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802110748370.2920@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-02-11T16:26:26Z","receivedAt":"2008-02-11T16:26:26Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Mon, 11 Feb 2008, Linus Torvalds wrote:\n> On Mon, 11 Feb 2008, Jakub Narebski wrote:\n>> \n>> Errr... index is per workarea (per checkout), and this information\n>> is per repository, so IMHO storing this info in an index (dircache)\n>> is a layering violation. Unless you were talking about pack-file-index.\n> \n> I did mean the pack-file index, not the \"cache\" index.\n\n> And yes, just generating the generation number when repacking is fine. It \n> would mean that unpacked objects don't have generation numbers, but of you \n> have tons and tons of unpacked objects, you have more serious problems \n> anyway!\n\nWith generation number info in pack index, we could generate them\non repack (adding some time to repack).\n\nWith generation number info in separate pack-index like file, we\ncould add generation info whenever during browsing history we get\nto root or to commit with generation number, saving generation\nnumbers in the by-the-way way, generating them lazily.\n\n>> Weren't the cases of multiple roots that were difficult? Storing roots\n>> would help with 'hard' (if seldom happening) cases then.\n\n> The thing that worried me about multiple roots was that they make the \n> generation numbers essentially \"meaningless\" when compared across totally \n> unrelated commits, and might give incorrect results for generation number \n> comparisons as a result.\n> \n> However, I decided that if two commits really *are* totally unrelated and \n> don't share a commit, then:\n> \n>  - yes, the generation number comparison is \"meaningless\"\n> \n>  - BUT: we don't actually care if it's correct or not, because it will \n>    never matter: whatever we choose to do, it's correct. Because there are \n>    just two choices:\n> \n>     (a) stop early because everything we have left is uninteresting\n> \n>     (b) continue to the root because we think we might turn something \n>         interesting into an uninteresting commit.\n\nBy the way, with generation number we can always limit walk length\nto difference between generation numbers, or distance to root if\nit is smaller.\n\n-- \nJakub Narebski\nPoland\n"},{"id":"68409","messageId":"alpine.LFD.1.00.0802111112420.2732@xanadu.home","threadId":"11998","inReplyTo":"alpine.LFD.1.00.0802110748370.2920@woody.linux-foundation.org","subject":"Re: Add \"--show-all\" revision walker flag for debugging","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-02-11T16:39:16Z","receivedAt":"2008-02-11T16:39:16Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 11 Feb 2008, Linus Torvalds wrote:\n\n> On Mon, 11 Feb 2008, Jakub Narebski wrote:\n> > \n> > Errr... index is per workarea (per checkout), and this information\n> > is per repository, so IMHO storing this info in an index (dircache)\n> > is a layering violation. Unless you were talking about pack-file-index.\n> \n> I did mean the pack-file index, not the \"cache\" index.\n\nI think this has nothing to do with pack index either.  Your repo may \nhave one pack, or multiple packs, or even no pack at all.  They may or \nmay not contain commit objects, etc.\n\nThe generation indexing is OTOH a repo wide issue, completely orthogonal \nto object packing. It has to be centralized in a single global file, or \npossibly one file per branch, and updated whenever new commits are added \nto the repository.  I think the best format is to have a list of \n(generation_nr, commit_sha1) tuples in assending order, so whenever a \nfetch or a commit is performed then updating this file is only a matter \nof appending to it.\n\nAnd optimizing it even further, only merge commits (or rather merge \ndirect parents as well as branch heads) should have their generation \nnumber cached in a file since the linear commits are trivially deduced \nfrom there.\n\nAnd regenerating this generation cache should not take longer than a \nfull history walk.\n\n\nNicolas\n"}]}