{"thread":{"id":"7093","subject":"[BUG] git-rev-list: --topo-order --boundary and --max-count","startedAt":"2007-03-05T10:02:27Z","lastAt":"2007-03-06T15:52:21Z","messageCount":26,"participants":["Santi Béjar","Junio C Hamano","Linus Torvalds","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"36311","messageId":"8aa486160703050202y5ee159d2i42a2859a00b41679@mail.gmail.com","threadId":"7093","inReplyTo":null,"subject":"[BUG] git-rev-list: --topo-order --boundary and --max-count","fromName":"Santi Béjar","fromEmail":"sbejar@gmail.com","sentAt":"2007-03-05T10:02:27Z","receivedAt":"2007-03-05T10:02:27Z","isPatch":false,"sender":{"key":"santi@agolina.net","avatar":null},"body":"Hi *,\n\n  the --topo-order does not play well with --boundary and --max-count.\n\n$ git-rev-list --boundary --max-count=50 5ced0 | wc -l\n56\n$ git-rev-list --topo-order --boundary --max-count=50 5ced0 | wc -l\n8846\n\n(5ced0 is git.git's master). I think it should be 56 for both. It\npresents this behaviour since c4025103fa, when was added --boundary\nsupport for git-rev-list --max-count and --max-age.\n\nSanti\n"},{"id":"36314","messageId":"7vlkicynwm.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"8aa486160703050202y5ee159d2i42a2859a00b41679@mail.gmail.com","subject":"Re: [BUG] git-rev-list: --topo-order --boundary and --max-count","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-05T10:39:53Z","receivedAt":"2007-03-05T10:39:53Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Santi Béjar\" <sbejar@gmail.com> writes:\n\n>  the --topo-order does not play well with --boundary and --max-count.\n>\n> $ git-rev-list --boundary --max-count=50 5ced0 | wc -l\n> 56\n> $ git-rev-list --topo-order --boundary --max-count=50 5ced0 | wc -l\n> 8846\n>\n> (5ced0 is git.git's master). I think it should be 56 for both. It\n> presents this behaviour since c4025103fa, when was added --boundary\n> support for git-rev-list --max-count and --max-age.\n\nI think the code that does --boundary when the list is limited\nwith --max-count is not quite right, even without topo-order.\nOnly when the traversal is not limited, the code happens to work\ncorrectly because in that case alone we pick up positive commits\none by one up to the specified count, and do not place anything\nother than their immediate parents in the list.\n\nIt needs to find out commits (be they marked as UNINTERESTING or\nnot) still in the revs->commits that are _not_ reachable by any\nother commits in the list, or something like that.\n\nI suspect that would unfortunately be very expensive.  Dscho,\nhave better ideas?\n"},{"id":"36318","messageId":"7vhcszzy1v.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"7vlkicynwm.fsf@assigned-by-dhcp.cox.net","subject":"Re: [BUG] git-rev-list: --topo-order --boundary and --max-count","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-05T12:15:24Z","receivedAt":"2007-03-05T12:15:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> \"Santi Béjar\" <sbejar@gmail.com> writes:\n>\n>>  the --topo-order does not play well with --boundary and --max-count.\n>>\n>> $ git-rev-list --boundary --max-count=50 5ced0 | wc -l\n>> 56\n>> $ git-rev-list --topo-order --boundary --max-count=50 5ced0 | wc -l\n>> 8846\n>>\n>> (5ced0 is git.git's master). I think it should be 56 for both. It\n>> presents this behaviour since c4025103fa, when was added --boundary\n>> support for git-rev-list --max-count and --max-age.\n>\n> I think the code that does --boundary when the list is limited\n> with --max-count is not quite right, even without topo-order.\n> Only when the traversal is not limited, the code happens to work\n> correctly because in that case alone we pick up positive commits\n> one by one up to the specified count, and do not place anything\n> other than their immediate parents in the list.\n\nThis is not even correct.  Let's see an extreme example.\nSuppose you have something like this:\n\n ---o---o---o---x---A\n \n   ---o---o---o---y---B\n\nand think about what \"rev-list --boundary --max-count=1 A B\"\nshould return.  It does not matter how branches A and B are\nrelated in the past because we are showing only one.\n\nWithout --boundary, it is clear we will show B (time flows from\nleft to right).  With --boundary, the current code would show B,\nand show -y and -A as boundaries, and I think that is wrong.\n\nOriginally --boundary was invented for the specific purpose of\nsupporting thin packs.  It worked on the set of commits\nresulting from a limited traversal (that is, you have at least\none negative, iow UNINTERESTING, commit and one or more positive\ncommits), and it showed the negative commit that is a parent of\na positive commit.\n\nThere are two primary users of --boundary right now.  gitk wants\nto show where the partial traversal ends (although it can figure\nit out itself without help from --boundary), and thin pack\ngeneration wants to have it upfront so that it can see which\ntrees and blobs can be used as the bases of delta.  In both\ncases, the semantics desired is to show commits that are _not_\nincluded in the usual (i.e. non --boundary) results that are\nimmediate parents of the commits that are included in the\nresult.\n\nSo with that definition, the above example should show B and\nthen -y as boundary, and should not even talk about A nor -x.\nThis may affect the git-bundle's computation of references\nincluded in the bundle (I think the current code assumes that if\nyou do \"git bundle --max-count=1 A B\" the resulting bundle says\nits set of tips consists of A and B) but if that is broken it\nalso needs to be fixed.\n"},{"id":"36340","messageId":"Pine.LNX.4.64.0703050901370.3998@woody.linux-foundation.org","threadId":"7093","inReplyTo":"7vlkicynwm.fsf@assigned-by-dhcp.cox.net","subject":"Re: [BUG] git-rev-list: --topo-order --boundary and --max-count","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-05T17:05:51Z","receivedAt":"2007-03-05T17:05:51Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 5 Mar 2007, Junio C Hamano wrote:\n> \n> I think the code that does --boundary when the list is limited\n> with --max-count is not quite right, even without topo-order.\n\nYeah. Sadly, this is a really irritating bug, becuase it means that you \ncannot do\n\n\tgitk -50\n\nto see some random collection of 50 recent commits.\n\n(And yes, I've wanted to do that - I know the commit is fairly recent, so \nrather than write \"gitk @{1.hour.ag}..\", I'd rather just be lazy and say \n\"gitk -100\" to get a smaller slider bar and easier to find the recent \nones).\n\nI never cared enough to fix it, but it's a mis-feature. I agree that it's \nprobably not entirely trivial to fix.\n\n\t\tLinus\n"},{"id":"36351","messageId":"Pine.LNX.4.63.0703051951340.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"7vlkicynwm.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] revision walker: Fix --boundary when limited","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-05T18:55:48Z","receivedAt":"2007-03-05T18:55:48Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nIn case revs->limited == 1, the revision walker really reads\neverything into revs->commits. The behaviour introduced in\nc4025103fa does not behave correctly in that case.\n\nIt used to say: everything which is _still_ in the pipeline\nmust be a boundary commit.\n\nSo, in the case that revs->limited == 1, filter out all commits\nwhich are not dangling, in effect marking only the dangling\nones as boundary commits.\n\nThis bug was noticed by Santi Béjar.\n\nSigned-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n---\n\n\tOn Mon, 5 Mar 2007, Junio C Hamano wrote:\n\n\t> \"Santi Béjar\" <sbejar@gmail.com> writes:\n\t> \n\t> > the --topo-order does not play well with --boundary and \n\t> > --max-count.\n\t> >\n\t> > $ git-rev-list --boundary --max-count=50 5ced0 | wc -l\n\t> > 56\n\t> > $ git-rev-list --topo-order --boundary --max-count=50 5ced0 \\\n\t> >   | wc -l\n\t> > 8846\n\t> >\n\t> > (5ced0 is git.git's master). I think it should be 56 for both. \n\t> > It presents this behaviour since c4025103fa, when was added \n\t> > --boundary support for git-rev-list --max-count and --max-age.\n\t> \n\t> I think the code that does --boundary when the list is limited\n\t> with --max-count is not quite right, even without topo-order.\n\n\tRight.\n\n\t> It needs to find out commits (be they marked as UNINTERESTING or\n\t> not) still in the revs->commits that are _not_ reachable by any\n\t> other commits in the list, or something like that.\n\t> \n\t> I suspect that would unfortunately be very expensive.  Dscho,\n\t> have better ideas?\n\n\tUnfortunately not. Fortunately, it is nowhere near as expensive as \n\tI originally thought. It just has to iterate through revs->commits \n\tthree times, which is way cheaper than sorting the commits in the \n\tfirst place.\n\n\tJunio, if you apply this, could you make extra sure that I did not \n\tfsck up Santi's family name (I am running on a peculiar mixture of \n\tUTF-8 and ISO-8859-1 terminals...).\n\n revision.c |   31 +++++++++++++++++++++++++++----\n 1 files changed, 27 insertions(+), 4 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex f5b8ae4..8d47fac 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1294,6 +1294,26 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \treturn NULL;\n }\n \n+static struct commit_list *get_dangling_commits(struct commit_list *list)\n+{\n+\tstruct commit_list *result = NULL, *iter, *parent;\n+\n+\tfor (iter = list; iter; iter = iter->next)\n+\t\tfor (parent = iter->item->parents;\n+\t\t\t\tparent;\n+\t\t\t\tparent = parent->next)\n+\t\t\tparent->item->object.flags |= TMP_MARK;\n+\tfor (iter = list; iter; iter = iter->next)\n+\t\tif (!(iter->item->object.flags & TMP_MARK))\n+\t\t\tcommit_list_insert(iter->item, &result);\n+\tfor (iter = list; iter; iter = iter->next)\n+\t\tfor (parent = iter->item->parents;\n+\t\t\t\tparent;\n+\t\t\t\tparent = parent->next)\n+\t\t\tparent->item->object.flags &= ~TMP_MARK;\n+\treturn result;\n+}\n+\n struct commit *get_revision(struct rev_info *revs)\n {\n \tstruct commit *c = NULL;\n@@ -1345,12 +1365,15 @@ struct commit *get_revision(struct rev_info *revs)\n \t\tbreak;\n \tcase 0:\n \t\tif (revs->boundary) {\n-\t\t\tstruct commit_list *list = revs->commits;\n-\t\t\twhile (list) {\n+\t\t\tstruct commit_list *list;\n+\t\t\tif (revs->limited) {\n+\t\t\t\tlist = get_dangling_commits(revs->commits);\n+\t\t\t\tfree_commit_list(revs->commits);\n+\t\t\t\trevs->commits = list;\n+\t\t\t}\n+\t\t\tfor (list = revs->commits; list; list = list->next)\n \t\t\t\tlist->item->object.flags |=\n \t\t\t\t\tBOUNDARY_SHOW | BOUNDARY;\n-\t\t\t\tlist = list->next;\n-\t\t\t}\n \t\t\t/* all remaining commits are boundary commits */\n \t\t\trevs->max_count = -1;\n \t\t\trevs->limited = 1;\n-- \n1.5.0.3.2518.g2f72-dirty\n"},{"id":"36352","messageId":"Pine.LNX.4.63.0703051957090.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"Pine.LNX.4.63.0703051951340.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-05T19:00:36Z","receivedAt":"2007-03-05T19:00:36Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 5 Mar 2007, Johannes Schindelin wrote:\n\n> \tOn Mon, 5 Mar 2007, Junio C Hamano wrote:\n> \n> \t> \"Santi Béjar\" <sbejar@gmail.com> writes:\n> \t> \n> \t> > the --topo-order does not play well with --boundary and \n> \t> > --max-count.\n> \t> >\n> \t> > $ git-rev-list --boundary --max-count=50 5ced0 | wc -l\n> \t> > 56\n> \t> > $ git-rev-list --topo-order --boundary --max-count=50 5ced0 \\\n> \t> >   | wc -l\n> \t> > 8846\n> \t> >\n> \t> > (5ced0 is git.git's master). I think it should be 56 for both. \n\nSide note: with the patch I am replying to, the latter command returns 51. \nThis is correct, since the only boundary commit it shows (1db8b60b) has \n(all) the other 5 commits as ancestors.\n\nThe behaviour of both is correct: in the former case, there is not enough \ninformation to tell that one of the 6 boundary commits reaches all the \nothers.\n\nCiao,\nDscho\n"},{"id":"36356","messageId":"Pine.LNX.4.64.0703051130090.3998@woody.linux-foundation.org","threadId":"7093","inReplyTo":"Pine.LNX.4.63.0703051951340.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-05T19:39:52Z","receivedAt":"2007-03-05T19:39:52Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 5 Mar 2007, Johannes Schindelin wrote:\n> \n> In case revs->limited == 1, the revision walker really reads\n> everything into revs->commits. The behaviour introduced in\n> c4025103fa does not behave correctly in that case.\n> \n> It used to say: everything which is _still_ in the pipeline\n> must be a boundary commit.\n\nI would suggest this (more invasive) patch instead.\n\nYours is\n\n revision.c |   31 +++++++++++++++++++++++++++----\n 1 files changed, 27 insertions(+), 4 deletions(-)\n\nand mine is\n\n revision.c |   86 ++++++++++++++++++++++++++++++-----------------------------\n 1 files changed, 44 insertions(+), 42 deletions(-)\n\nie I have bigger changes, but on the whole this patch just adds two lines \ntotal, and I *think* the end result is more readable.\n\nNOTE! Our patches aren't really mutually incompatible, and they attack the \nproblem from two different directions. You do the separate phase (which is \nalso correct), and my patch instead tries to clean up the commit walking \nso that the commit number limiter works more like the date limiter (which \nfundamentally has all the same issues! Including the problem with some \ncommits possibly being marked as boundary commits when they aren't really, \nbecause the path-limiting or revision-limiting ended up cutting things off \n*differently* than the date-limiting).\n\nSo I would humbly suggest applying this one first (which makes the \nhandling of the walk-time commit limiter more uniform and less hacky), and \nif we need to, we can *also* add the whole separate phase for the \n\"revs->limited\" case..\n\n\t\tLinus\n\n---\ncommit d3dd7e89c123b644ef199380f4f050226e4df862\nAuthor: Linus Torvalds <torvalds@osdl.org>\nDate:   Mon Mar 5 10:15:20 2007 -0800\n\n    revision list: fix BOUNDARY handling with limiters and commit counts\n    \n    When we limited the number of commits using \"max_count\", we would not\n    correctly handle the combination of various time- and reachability-based\n    limiting and the use of a commit counting.  Everything that was\n    reachable (but overflowed the commit count) would be marked as a\n    BOUNDARY commit, resulting in things like \"gitk\" not being usable\n    together with a numerical limit on the number of commits.\n    \n    This largely fixes it by being more careful about how we mark commits\n    that went over the commit counts.\n    \n    NOTE! Because the numerical limiting happens without a separate phase as\n    we traverse the commit list, we still won't do the boundary handling\n    100% correct when a commit may be reachable from multiple sources, and\n    under those circumstances, some commits will be marked as boundary\n    commits even though they strictly aren't.\n    \n    To fix this, we would need to make rather more invasive changes, with\n    commit counting being an integral part of the limiting (whuch is\n    fundamnetally hard, since limiting itself will change the number of\n    commits!).\n    \n    So this is the \"good enough to be quite usable\" approach.  The problem\n    only affects boundary commits, and programs like 'gitk' that uses\n    boundary commits would be better off just noticing themselves that not\n    all boundary commits are necessarily useful.\n    \n    Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n revision.c |   86 ++++++++++++++++++++++++++++++-----------------------------\n 1 files changed, 44 insertions(+), 42 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex f5b8ae4..f5430d6 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1213,6 +1213,30 @@ static int commit_match(struct commit *commit, struct rev_info *opt)\n \t\t\t   commit->buffer, strlen(commit->buffer));\n }\n \n+enum walk_action {\n+\tWALK_PARENTS,\n+\tWALK_STOP,\n+};\n+\n+/*\n+ * When we do the list limiting at commit-walking time, we\n+ * need to make sure that we stop walking parenthood when\n+ * we hit a commit that isn't interesting any more. This can\n+ * be due to max_count or due to date limiters.\n+ */\n+static enum walk_action walk_commit(struct rev_info *revs, struct commit *commit)\n+{\n+\tif (!revs->max_count)\n+\t\treturn WALK_STOP;\n+\n+\tif (revs->max_age != -1) {\n+\t\tif (commit->date < revs->max_age)\n+\t\t\treturn WALK_STOP;\n+\t}\n+\n+\treturn WALK_PARENTS;\n+}\n+\n static struct commit *get_revision_1(struct rev_info *revs)\n {\n \tif (!revs->commits)\n@@ -1233,17 +1257,19 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t * the parents here. We also need to do the date-based limiting\n \t\t * that we'd otherwise have done in limit_list().\n \t\t */\n-\t\tif (!revs->limited) {\n-\t\t\tif (revs->max_age != -1 &&\n-\t\t\t    (commit->date < revs->max_age)) {\n-\t\t\t\tif (revs->boundary)\n-\t\t\t\t\tcommit->object.flags |=\n-\t\t\t\t\t\tBOUNDARY_SHOW | BOUNDARY;\n-\t\t\t\telse\n-\t\t\t\t\tcontinue;\n-\t\t\t} else\n-\t\t\t\tadd_parents_to_list(revs, commit,\n-\t\t\t\t\t\t&revs->commits);\n+\t\tswitch (walk_commit(revs, commit)) {\n+\t\tcase WALK_PARENTS:\n+\t\t\tif (revs->limited)\n+\t\t\t\tbreak;\n+\t\t\tadd_parents_to_list(revs, commit, &revs->commits);\n+\t\t\tbreak;\n+\t\tcase WALK_STOP:\n+\t\t\tif (!revs->boundary)\n+\t\t\t\tcontinue;\n+\t\t\tif (!(commit->object.flags & UNINTERESTING))\n+\t\t\t\tcommit->object.flags |= BOUNDARY_SHOW | BOUNDARY | UNINTERESTING;\n+\t\t\tmark_parents_uninteresting(commit);\n+\t\t\tbreak;\n \t\t}\n \t\tif (commit->object.flags & SHOWN)\n \t\t\tcontinue;\n@@ -1289,6 +1315,12 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\tif (revs->boundary)\n \t\t\tmark_boundary_to_show(commit);\n \t\tcommit->object.flags |= SHOWN;\n+\t\tif (revs->skip_count > 0) {\n+\t\t\trevs->skip_count--;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (revs->max_count > 0)\n+\t\t\trevs->max_count--;\n \t\treturn commit;\n \t} while (revs->commits);\n \treturn NULL;\n@@ -1296,9 +1328,8 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \n struct commit *get_revision(struct rev_info *revs)\n {\n-\tstruct commit *c = NULL;\n-\n \tif (revs->reverse) {\n+\t\tstruct commit *c;\n \t\tstruct commit_list *list;\n \n \t\t/*\n@@ -1332,34 +1363,5 @@ struct commit *get_revision(struct rev_info *revs)\n \t\treturn c;\n \t}\n \n-\tif (0 < revs->skip_count) {\n-\t\twhile ((c = get_revision_1(revs)) != NULL) {\n-\t\t\tif (revs->skip_count-- <= 0)\n-\t\t\t\tbreak;\n-\t\t}\n-\t}\n-\n-\t/* Check the max_count ... */\n-\tswitch (revs->max_count) {\n-\tcase -1:\n-\t\tbreak;\n-\tcase 0:\n-\t\tif (revs->boundary) {\n-\t\t\tstruct commit_list *list = revs->commits;\n-\t\t\twhile (list) {\n-\t\t\t\tlist->item->object.flags |=\n-\t\t\t\t\tBOUNDARY_SHOW | BOUNDARY;\n-\t\t\t\tlist = list->next;\n-\t\t\t}\n-\t\t\t/* all remaining commits are boundary commits */\n-\t\t\trevs->max_count = -1;\n-\t\t\trevs->limited = 1;\n-\t\t} else\n-\t\t\treturn NULL;\n-\tdefault:\n-\t\trevs->max_count--;\n-\t}\n-\tif (c)\n-\t\treturn c;\n \treturn get_revision_1(revs);\n }\n"},{"id":"36358","messageId":"Pine.LNX.4.64.0703051145210.3998@woody.linux-foundation.org","threadId":"7093","inReplyTo":"Pine.LNX.4.64.0703051130090.3998@woody.linux-foundation.org","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-05T19:57:42Z","receivedAt":"2007-03-05T19:57:42Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 5 Mar 2007, Linus Torvalds wrote:\n> \n> NOTE! Our patches aren't really mutually incompatible, and they attack the \n> problem from two different directions. You do the separate phase (which is \n> also correct), and my patch instead tries to clean up the commit walking \n> so that the commit number limiter works more like the date limiter (which \n> fundamentally has all the same issues! Including the problem with some \n> commits possibly being marked as boundary commits when they aren't really, \n> because the path-limiting or revision-limiting ended up cutting things off \n> *differently* than the date-limiting).\n\nSide note: the reason you don't *notice* it with the date-limiter is \nsimply that the date limiter *also* runs at limit-time, rather than just \nat the incremental \"run at the end\" phase. So the date-limiter is much \nsimpler when done together with other limiters (like path and revision \nlimiters).\n\nHOWEVER. We can't do the same thing for the numerical one, because we need \nto run the other limiters *first*, and the numerical limiter always comes \nat the end. And the path-based \"dense\" limiter actually runs mostly \nincrementally, so you cannot do the numerical limiter until after it has \nrun..\n\nThe way to really clean stuff up would be to:\n\n - first phase: limit by date and revision ranges first (both of those are \n   static and quick, and don't depend on anything else)\n\n   We do this already (limit_list)\n\n - second phase: limit by pathname (we don't do this as a phase at all, we \n   do it incrementally: see \"rewrite_parents()\")\n\n -third phase: limit by number\n\nHOWEVER. There's a damn good reason why we do things the way we do, namely \nsimply the fact that we want to do pathname limiting as much at run-time \nas possible.. But we *could* do the \"rewrite_parents()\" thing both in the\nnon-incremental and in the final phase. However, doing the parent \nrewriting is quite nasty and error-prone, so I've been avoiding it.\n\nAnyway, I *suspect* that Dscho's patch might do the wrong thing for \nsomething like\n\n\tgitk -20 v1.4.4.. t/\n\nexactly because of the subtle interaction between pathname limiting, \nstatic commit limiting *and* commit number limiting. Dscho?\n\n\t\tLinus\n"},{"id":"36365","messageId":"7vejo3xuq9.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"Pine.LNX.4.64.0703051145210.3998@woody.linux-foundation.org","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-05T21:10:06Z","receivedAt":"2007-03-05T21:10:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Mon, 5 Mar 2007, Linus Torvalds wrote:\n>> \n>> NOTE! Our patches aren't really mutually incompatible, and they attack the \n>> problem from two different directions. You do the separate phase (which is \n>> also correct), and my patch instead tries to clean up the commit walking \n>> so that the commit number limiter works more like the date limiter (which \n>> fundamentally has all the same issues! Including the problem with some \n>> commits possibly being marked as boundary commits when they aren't really, \n>> because the path-limiting or revision-limiting ended up cutting things off \n>> *differently* than the date-limiting).\n\nI was working on a different approach, which is:\n\n - rip out the boundary logic from the commit walker. Placing\n   \"negative\" commits in the revs->commits list was Ok if all we\n   cared about \"boundary\" was the UNINTERESTING limiting case,\n   but conceptually it was wrong.\n\n - make get_revision_1() function to walk the commits and return\n   the results as if there is no funny postprocessing flags such\n   as --reverse, --skip nor --max-count.\n\n - make get_revision() function the postprocessing phase:\n\n   If reverse is given, wait for get_revision_1() to give\n   everything that it would normally give, and then reverse it\n   before consuming.\n\n   If skip is given, skip that many before going further.\n\n   If max is given, stop when we gave out that many.\n\n   Now that we are about to return one positive commit, mark\n   the parents of that commit to be potential boundaries\n   before returning, iff we are doing the boundary processing.\n\n   Return the commit.\n\n - After get_revision() finishes giving out all the positive\n   commits, if we are doing the boundary processing, we look at\n   the parents that we marked as potential boundaries earlier,\n   see if they are really boundaries, and give them out.\n\nIt loses more code than it adds, even when the new gc_boundary()\nfunction, which is purely for early optimization, is counted.\n\nNote that this patch is purely for eyeballing and discussion\nonly.  It breaks git-bundle's verify logic because the logic\ndoes not use BOUNDARY_SHOW flag for its internal computation\nanymore.  After we correct it not to attempt to affect the\nboundary processing by setting the BOUNDARY_SHOW flag, we can\nremove BOUNDARY_SHOW from revision.h and use that bit assignment\nfor the new CHILD_SHOWN flag.\n\n---\n revision.c |  208 +++++++++++++++++++++++++++---------------------------------\n revision.h |    8 ++-\n 2 files changed, 100 insertions(+), 116 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex f5b8ae4..5d137ea 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -437,36 +437,6 @@ static void limit_list(struct rev_info *revs)\n \t\t\tcontinue;\n \t\tp = &commit_list_insert(commit, p)->next;\n \t}\n-\tif (revs->boundary) {\n-\t\t/* mark the ones that are on the result list first */\n-\t\tfor (list = newlist; list; list = list->next) {\n-\t\t\tstruct commit *commit = list->item;\n-\t\t\tcommit->object.flags |= TMP_MARK;\n-\t\t}\n-\t\tfor (list = newlist; list; list = list->next) {\n-\t\t\tstruct commit *commit = list->item;\n-\t\t\tstruct object *obj = &commit->object;\n-\t\t\tstruct commit_list *parent;\n-\t\t\tif (obj->flags & UNINTERESTING)\n-\t\t\t\tcontinue;\n-\t\t\tfor (parent = commit->parents;\n-\t\t\t     parent;\n-\t\t\t     parent = parent->next) {\n-\t\t\t\tstruct commit *pcommit = parent->item;\n-\t\t\t\tif (!(pcommit->object.flags & UNINTERESTING))\n-\t\t\t\t\tcontinue;\n-\t\t\t\tpcommit->object.flags |= BOUNDARY;\n-\t\t\t\tif (pcommit->object.flags & TMP_MARK)\n-\t\t\t\t\tcontinue;\n-\t\t\t\tpcommit->object.flags |= TMP_MARK;\n-\t\t\t\tp = &commit_list_insert(pcommit, p)->next;\n-\t\t\t}\n-\t\t}\n-\t\tfor (list = newlist; list; list = list->next) {\n-\t\t\tstruct commit *commit = list->item;\n-\t\t\tcommit->object.flags &= ~TMP_MARK;\n-\t\t}\n-\t}\n \trevs->commits = newlist;\n }\n \n@@ -1193,17 +1163,6 @@ static void rewrite_parents(struct rev_info *revs, struct commit *commit)\n \t}\n }\n \n-static void mark_boundary_to_show(struct commit *commit)\n-{\n-\tstruct commit_list *p = commit->parents;\n-\twhile (p) {\n-\t\tcommit = p->item;\n-\t\tp = p->next;\n-\t\tif (commit->object.flags & BOUNDARY)\n-\t\t\tcommit->object.flags |= BOUNDARY_SHOW;\n-\t}\n-}\n-\n static int commit_match(struct commit *commit, struct rev_info *opt)\n {\n \tif (!opt->grep_filter)\n@@ -1235,15 +1194,9 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t */\n \t\tif (!revs->limited) {\n \t\t\tif (revs->max_age != -1 &&\n-\t\t\t    (commit->date < revs->max_age)) {\n-\t\t\t\tif (revs->boundary)\n-\t\t\t\t\tcommit->object.flags |=\n-\t\t\t\t\t\tBOUNDARY_SHOW | BOUNDARY;\n-\t\t\t\telse\n-\t\t\t\t\tcontinue;\n-\t\t\t} else\n-\t\t\t\tadd_parents_to_list(revs, commit,\n-\t\t\t\t\t\t&revs->commits);\n+\t\t\t    (commit->date < revs->max_age))\n+\t\t\t\tcontinue;\n+\t\t\tadd_parents_to_list(revs, commit, &revs->commits);\n \t\t}\n \t\tif (commit->object.flags & SHOWN)\n \t\t\tcontinue;\n@@ -1252,18 +1205,6 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\t\t\t\t    revs->ignore_packed))\n \t\t    continue;\n \n-\t\t/* We want to show boundary commits only when their\n-\t\t * children are shown.  When path-limiter is in effect,\n-\t\t * rewrite_parents() drops some commits from getting shown,\n-\t\t * and there is no point showing boundary parents that\n-\t\t * are not shown.  After rewrite_parents() rewrites the\n-\t\t * parents of a commit that is shown, we mark the boundary\n-\t\t * parents with BOUNDARY_SHOW.\n-\t\t */\n-\t\tif (commit->object.flags & BOUNDARY_SHOW) {\n-\t\t\tcommit->object.flags |= SHOWN;\n-\t\t\treturn commit;\n-\t\t}\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n \t\tif (revs->min_age != -1 && (commit->date > revs->min_age))\n@@ -1286,80 +1227,119 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->parents)\n \t\t\t\trewrite_parents(revs, commit);\n \t\t}\n-\t\tif (revs->boundary)\n-\t\t\tmark_boundary_to_show(commit);\n \t\tcommit->object.flags |= SHOWN;\n \t\treturn commit;\n \t} while (revs->commits);\n \treturn NULL;\n }\n \n+static void gc_boundary(struct object_array *array)\n+{\n+\tunsigned nr = array->nr;\n+\tunsigned alloc = array->alloc;\n+\tstruct object_array_entry *objects = array->objects;\n+\n+\tif (alloc <= nr) {\n+\t\tunsigned i, j;\n+\t\tfor (i = j = 0; i < nr; i++) {\n+\t\t\tif (objects[i].item->flags & SHOWN)\n+\t\t\t\tcontinue;\n+\t\t\tif (i != j)\n+\t\t\t\tobjects[j] = objects[i];\n+\t\t\tj++;\n+\t\t}\n+\t\tfor (i = j; j < nr; j++)\n+\t\t\tobjects[i].item = NULL;\n+\t\tarray->nr = j;\n+\t}\n+}\n+\n struct commit *get_revision(struct rev_info *revs)\n {\n \tstruct commit *c = NULL;\n-\n-\tif (revs->reverse) {\n-\t\tstruct commit_list *list;\n-\n-\t\t/*\n-\t\t * rev_info.reverse is used to note the fact that we\n-\t\t * want to output the list of revisions in reverse\n-\t\t * order.  To accomplish this goal, reverse can have\n-\t\t * different values:\n-\t\t *\n-\t\t *  0  do nothing\n-\t\t *  1  reverse the list\n-\t\t *  2  internal use:  we have already obtained and\n-\t\t *     reversed the list, now we only need to yield\n-\t\t *     its items.\n-\t\t */\n-\n-\t\tif (revs->reverse == 1) {\n-\t\t\trevs->reverse = 0;\n-\t\t\tlist = NULL;\n-\t\t\twhile ((c = get_revision(revs)))\n-\t\t\t\tcommit_list_insert(c, &list);\n-\t\t\trevs->commits = list;\n-\t\t\trevs->reverse = 2;\n+\tstruct commit_list *l;\n+\n+\tif (revs->boundary == 2) {\n+\t\tunsigned i;\n+\t\tstruct object_array *array = &revs->boundary_commits;\n+\t\tstruct object_array_entry *objects = array->objects;\n+\t\tfor (i = 0; i < array->nr; i++) {\n+\t\t\tc = (struct commit *)(objects[i].item);\n+\t\t\tif (!c)\n+\t\t\t\tcontinue;\n+\t\t\tif (!(c->object.flags & CHILD_SHOWN))\n+\t\t\t\tcontinue;\n+\t\t\tif (!(c->object.flags & SHOWN))\n+\t\t\t\tbreak;\n \t\t}\n-\n-\t\tif (!revs->commits)\n+\t\tif (array->nr <= i)\n \t\t\treturn NULL;\n-\t\tc = revs->commits->item;\n-\t\tlist = revs->commits->next;\n-\t\tfree(revs->commits);\n-\t\trevs->commits = list;\n+\n+\t\tc->object.flags |= SHOWN | BOUNDARY;\n \t\treturn c;\n \t}\n \n-\tif (0 < revs->skip_count) {\n-\t\twhile ((c = get_revision_1(revs)) != NULL) {\n-\t\t\tif (revs->skip_count-- <= 0)\n-\t\t\t\tbreak;\n-\t\t}\n+\tif (revs->reverse) {\n+\t\tl = NULL;\n+\t\twhile ((c = get_revision_1(revs)))\n+\t\t\tcommit_list_insert(c, &l);\n+\t\trevs->commits = l;\n+\t\trevs->reverse = 0;\n \t}\n \n-\t/* Check the max_count ... */\n+\t/*\n+\t * Now pick up what they want to give us\n+\t */\n+\tc = get_revision_1(revs);\n+\twhile (0 < revs->skip_count) {\n+\t\trevs->skip_count--;\n+\t\tc = get_revision_1(revs);\n+\t\tif (!c)\n+\t\t\tbreak;\n+\t}\n+\n+\t/*\n+\t * Check the max_count.\n+\t */\n \tswitch (revs->max_count) {\n \tcase -1:\n \t\tbreak;\n \tcase 0:\n-\t\tif (revs->boundary) {\n-\t\t\tstruct commit_list *list = revs->commits;\n-\t\t\twhile (list) {\n-\t\t\t\tlist->item->object.flags |=\n-\t\t\t\t\tBOUNDARY_SHOW | BOUNDARY;\n-\t\t\t\tlist = list->next;\n-\t\t\t}\n-\t\t\t/* all remaining commits are boundary commits */\n-\t\t\trevs->max_count = -1;\n-\t\t\trevs->limited = 1;\n-\t\t} else\n-\t\t\treturn NULL;\n+\t\tc = NULL;\n+\t\tbreak;\n \tdefault:\n \t\trevs->max_count--;\n \t}\n-\tif (c)\n+\n+\tif (!revs->boundary)\n \t\treturn c;\n-\treturn get_revision_1(revs);\n+\n+\tif (!c) {\n+\t\t/*\n+\t\t * get_revision_1() runs out the commits, and\n+\t\t * we are done computing the boundaries.\n+\t\t * switch to boundary commits output mode.\n+\t\t */\n+\t\trevs->boundary = 2;\n+\t\treturn get_revision(revs);\n+\t}\n+\n+\t/*\n+\t * boundary commits are the commits that are parents of the\n+\t * ones we got from get_revision_1() but they themselves are\n+\t * not returned from get_revision_1().  Before returning\n+\t * 'c', we need to mark its parents that they could be boundaries.\n+\t */\n+\n+\tfor (l = c->parents; l; l = l->next) {\n+\t\tstruct object *p;\n+\t\tp = &(l->item->object);\n+\t\tif (p->flags & CHILD_SHOWN)\n+\t\t\tcontinue;\n+\t\tp->flags |= CHILD_SHOWN;\n+\t\tgc_boundary(&revs->boundary_commits);\n+\t\tadd_object_array(p, NULL, &revs->boundary_commits);\n+\t}\n+\n+\treturn c;\n }\ndiff --git a/revision.h b/revision.h\nindex 5fec184..6579a44 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -10,6 +10,7 @@\n #define BOUNDARY_SHOW\t(1u<<6)\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n+#define CHILD_SHOWN\t(1u<<9)\n \n struct rev_info;\n struct log_info;\n@@ -21,6 +22,9 @@ struct rev_info {\n \tstruct commit_list *commits;\n \tstruct object_array pending;\n \n+\t/* Parents of shown commits */\n+\tstruct object_array boundary_commits;\n+\n \t/* Basic information */\n \tconst char *prefix;\n \tvoid *prune_data;\n@@ -40,10 +44,10 @@ struct rev_info {\n \t\t\tedge_hint:1,\n \t\t\tlimited:1,\n \t\t\tunpacked:1, /* see also ignore_packed below */\n-\t\t\tboundary:1,\n+\t\t\tboundary:2,\n \t\t\tleft_right:1,\n \t\t\tparents:1,\n-\t\t\treverse:2;\n+\t\t\treverse:1;\n \n \t/* Diff flags */\n \tunsigned int\tdiff:1,\n"},{"id":"36366","messageId":"7v7itvxupl.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"Pine.LNX.4.63.0703051951340.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-05T21:10:30Z","receivedAt":"2007-03-05T21:10:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> In case revs->limited == 1, the revision walker really reads\n> everything into revs->commits. The behaviour introduced in\n> c4025103fa does not behave correctly in that case.\n>\n> It used to say: everything which is _still_ in the pipeline\n> must be a boundary commit.\n>\n> So, in the case that revs->limited == 1, filter out all commits\n> which are not dangling, in effect marking only the dangling\n> ones as boundary commits.\n\nThat's what I suggested initially but I think that is wrong.  We\nshould show only unshown immediate parents of shown commits at\nthat stage.\n"},{"id":"36381","messageId":"Pine.LNX.4.63.0703060016020.13683@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"Pine.LNX.4.64.0703051145210.3998@woody.linux-foundation.org","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-05T23:17:14Z","receivedAt":"2007-03-05T23:17:14Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 5 Mar 2007, Linus Torvalds wrote:\n\n> Anyway, I *suspect* that Dscho's patch might do the wrong thing for \n> something like\n> \n> \tgitk -20 v1.4.4.. t/\n> \n> exactly because of the subtle interaction between pathname limiting, \n> static commit limiting *and* commit number limiting. Dscho?\n\nCorrect. I'll have a look at Junio's patch shortly, which hopefully makes \nme forget my shortsighted patch.\n\nCiao,\nDscho\n"},{"id":"36393","messageId":"7vk5xvw6mg.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"Pine.LNX.4.63.0703060016020.13683@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T00:36:07Z","receivedAt":"2007-03-06T00:36:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> On Mon, 5 Mar 2007, Linus Torvalds wrote:\n>\n>> Anyway, I *suspect* that Dscho's patch might do the wrong thing for \n>> something like\n>> \n>> \tgitk -20 v1.4.4.. t/\n>> \n>> exactly because of the subtle interaction between pathname limiting, \n>> static commit limiting *and* commit number limiting. Dscho?\n>\n> Correct. I'll have a look at Junio's patch shortly, which hopefully makes \n> me forget my shortsighted patch.\n\nI have a handful updates, including a few 'git-bundle' patches.\n"},{"id":"36395","messageId":"7vzm6rurst.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"7vk5xvw6mg.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH 2/4] revision traversal: retire BOUNDARY_SHOW","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T00:41:38Z","receivedAt":"2007-03-06T00:41:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This removes the flag internally used by revision traversal to\ndecide which commits are indeed boundaries and renames it to\nCHILD_SHOWN.  builtin-bundle uses the symbol for its\nverification, but I think the logic it uses it is wrong.  The\nflag is still useful but it is local to the git-bundle, so it is\nrenamed to PREREQ_MARK.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n * The earlier one that competed with Johannes's and Linus's is\n   the [1/4] of this series.\n\n builtin-bundle.c |    6 ++++--\n revision.c       |    9 ++++++++-\n revision.h       |    3 +--\n 3 files changed, 13 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin-bundle.c b/builtin-bundle.c\nindex d41a413..0265845 100644\n--- a/builtin-bundle.c\n+++ b/builtin-bundle.c\n@@ -160,6 +160,8 @@ static int fork_with_pipe(const char **argv, int *in, int *out)\n \treturn pid;\n }\n \n+#define PREREQ_MARK (1u<<16)\n+\n static int verify_bundle(struct bundle_header *header)\n {\n \t/*\n@@ -179,7 +181,7 @@ static int verify_bundle(struct bundle_header *header)\n \t\tstruct ref_list_entry *e = p->list + i;\n \t\tstruct object *o = parse_object(e->sha1);\n \t\tif (o) {\n-\t\t\to->flags |= BOUNDARY_SHOW;\n+\t\t\to->flags |= PREREQ_MARK;\n \t\t\tadd_pending_object(&revs, o, e->name);\n \t\t\tcontinue;\n \t\t}\n@@ -202,7 +204,7 @@ static int verify_bundle(struct bundle_header *header)\n \n \ti = req_nr;\n \twhile (i && (commit = get_revision(&revs)))\n-\t\tif (commit->object.flags & BOUNDARY_SHOW)\n+\t\tif (commit->object.flags & PREREQ_MARK)\n \t\t\ti--;\n \n \tfor (i = 0; i < req_nr; i++)\ndiff --git a/revision.c b/revision.c\nindex 5d137ea..2d27ccf 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1285,17 +1285,21 @@ struct commit *get_revision(struct rev_info *revs)\n \t\t\tcommit_list_insert(c, &l);\n \t\trevs->commits = l;\n \t\trevs->reverse = 0;\n+\t\tc = NULL;\n \t}\n \n \t/*\n \t * Now pick up what they want to give us\n \t */\n-\tc = get_revision_1(revs);\n+\tif (!(c = get_revision_1(revs)))\n+\t\treturn NULL;\n \twhile (0 < revs->skip_count) {\n \t\trevs->skip_count--;\n \t\tc = get_revision_1(revs);\n \t\tif (!c)\n \t\t\tbreak;\n+\t\t/* Although we grabbed it, it is not shown. */\n+\t\tc->object.flags &= ~SHOWN;\n \t}\n \n \t/*\n@@ -1305,6 +1309,9 @@ struct commit *get_revision(struct rev_info *revs)\n \tcase -1:\n \t\tbreak;\n \tcase 0:\n+\t\t/* Although we grabbed it, it is not shown. */\n+\t\tif (c)\n+\t\t\tc->object.flags &= ~SHOWN;\n \t\tc = NULL;\n \t\tbreak;\n \tdefault:\ndiff --git a/revision.h b/revision.h\nindex 6579a44..1885f8d 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -7,10 +7,9 @@\n #define SHOWN\t\t(1u<<3)\n #define TMP_MARK\t(1u<<4) /* for isolated cases; clean after use */\n #define BOUNDARY\t(1u<<5)\n-#define BOUNDARY_SHOW\t(1u<<6)\n+#define CHILD_SHOWN\t(1u<<6)\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n-#define CHILD_SHOWN\t(1u<<9)\n \n struct rev_info;\n struct log_info;\n-- \n1.5.0.3.862.g71037\n"},{"id":"36396","messageId":"7vtzwzurss.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"7vk5xvw6mg.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH 3/4] git-bundle: various fixups","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T00:41:39Z","receivedAt":"2007-03-06T00:41:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"verify_bundle() returned with an error early only when all\nprerequisite commits were missing.  It should error out much\nearlier when some are missing.\n\nWhen the rev-list is limited in ways other than revision range\n(e.g. --max-count or --max-age), create_bundle() listed all\npositive refs given from the command line as if they are\navailable, but resulting pack may not have some of them.  Add a\nlogic to make sure all of them are included, and error out\notherwise.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n builtin-bundle.c |   46 +++++++++++++++++++++++++++++++++-------------\n 1 files changed, 33 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin-bundle.c b/builtin-bundle.c\nindex 0265845..9286f3d 100644\n--- a/builtin-bundle.c\n+++ b/builtin-bundle.c\n@@ -189,7 +189,7 @@ static int verify_bundle(struct bundle_header *header)\n \t\t\terror(message);\n \t\terror(\"%s %s\", sha1_to_hex(e->sha1), e->name);\n \t}\n-\tif (revs.pending.nr == 0)\n+\tif (revs.pending.nr != p->nr)\n \t\treturn ret;\n \treq_nr = revs.pending.nr;\n \tsetup_revisions(2, argv, &revs, NULL);\n@@ -274,6 +274,7 @@ static int create_bundle(struct bundle_header *header, const char *path,\n \tint pid, in, out, i, status;\n \tchar buffer[1024];\n \tstruct rev_info revs;\n+\tstruct object_array tips;\n \n \tbundle_fd = (!strcmp(path, \"-\") ? 1 :\n \t\t\topen(path, O_CREAT | O_WRONLY, 0666));\n@@ -311,19 +312,23 @@ static int create_bundle(struct bundle_header *header, const char *path,\n \targc = setup_revisions(argc, argv, &revs, NULL);\n \tif (argc > 1)\n \t\treturn error(\"unrecognized argument: %s'\", argv[1]);\n+\n+\tmemset(&tips, 0, sizeof(tips));\n \tfor (i = 0; i < revs.pending.nr; i++) {\n \t\tstruct object_array_entry *e = revs.pending.objects + i;\n-\t\tif (!(e->item->flags & UNINTERESTING)) {\n-\t\t\tunsigned char sha1[20];\n-\t\t\tchar *ref;\n-\t\t\tif (dwim_ref(e->name, strlen(e->name), sha1, &ref) != 1)\n-\t\t\t\tcontinue;\n-\t\t\twrite_or_die(bundle_fd, sha1_to_hex(e->item->sha1), 40);\n-\t\t\twrite_or_die(bundle_fd, \" \", 1);\n-\t\t\twrite_or_die(bundle_fd, ref, strlen(ref));\n-\t\t\twrite_or_die(bundle_fd, \"\\n\", 1);\n-\t\t\tfree(ref);\n-\t\t}\n+\t\tunsigned char sha1[20];\n+\t\tchar *ref;\n+\n+\t\tif (e->item->flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\tif (dwim_ref(e->name, strlen(e->name), sha1, &ref) != 1)\n+\t\t\tcontinue;\n+\t\twrite_or_die(bundle_fd, sha1_to_hex(e->item->sha1), 40);\n+\t\twrite_or_die(bundle_fd, \" \", 1);\n+\t\twrite_or_die(bundle_fd, ref, strlen(ref));\n+\t\twrite_or_die(bundle_fd, \"\\n\", 1);\n+\t\tadd_object_array(e->item, e->name, &tips);\n+\t\tfree(ref);\n \t}\n \n \t/* end header */\n@@ -350,7 +355,22 @@ static int create_bundle(struct bundle_header *header, const char *path,\n \t\t\treturn -1;\n \tif (!WIFEXITED(status) || WEXITSTATUS(status))\n \t\treturn error (\"pack-objects died\");\n-\treturn 0;\n+\n+\t/*\n+\t * Make sure the refs we wrote out is correct; --max-count and\n+\t * other limiting options could have prevented all the tips\n+\t * from getting output.\n+\t */\n+\tstatus = 0;\n+\tfor (i = 0; i < tips.nr; i++) {\n+\t\tif (!(tips.objects[i].item->flags & SHOWN)) {\n+\t\t\tstatus = 1;\n+\t\t\terror(\"%s: not included in the resulting pack\",\n+\t\t\t      tips.objects[i].name);\n+\t\t}\n+\t}\n+\n+\treturn status;\n }\n \n static int unbundle(struct bundle_header *header, int bundle_fd,\n-- \n1.5.0.3.862.g71037\n"},{"id":"36397","messageId":"7vodn7ursq.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"7vk5xvw6mg.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH 4/4] git-bundle: --list-prereqs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T00:41:41Z","receivedAt":"2007-03-06T00:41:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is primarily of interest while debugging the bundle creation,\nbut there may be other uses.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n * I am not sure if this should be a separate command, but the\n   current command set did not have a way to review prereqs,\n   short of:\n\n\tsed -ne '/^PACK/q' -e 'p' bundle.bdl\n\n   It would make sense to have 'git bundle verify' output the\n   heads and prereqs, maybe with --verbose, but I think doing\n   that always might be even more helpful.\n\n builtin-bundle.c |   18 +++++++++++++++++-\n 1 files changed, 17 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin-bundle.c b/builtin-bundle.c\nindex 9286f3d..4fe74a7 100644\n--- a/builtin-bundle.c\n+++ b/builtin-bundle.c\n@@ -241,6 +241,19 @@ static int list_heads(struct bundle_header *header, int argc, const char **argv)\n \treturn 0;\n }\n \n+static int list_prereqs(struct bundle_header *header, int argc, const char **argv)\n+{\n+\tint i;\n+\n+\tstruct ref_list *p = &header->prerequisites;\n+\tfor (i = 0; i < p->nr; i++) {\n+\t\tprintf(\"%s %s\\n\",\n+\t\t       sha1_to_hex(p->list[i].sha1),\n+\t\t       p->list[i].name);\n+\t}\n+\treturn 0;\n+}\n+\n static void show_commit(struct commit *commit)\n {\n \twrite_or_die(1, sha1_to_hex(commit->object.sha1), 40);\n@@ -432,6 +445,10 @@ int cmd_bundle(int argc, const char **argv, const char *prefix)\n \t\tclose(bundle_fd);\n \t\treturn !!list_heads(&header, argc, argv);\n \t}\n+\tif (!strcmp(cmd, \"list-prereqs\")) {\n+\t\tclose(bundle_fd);\n+\t\treturn !!list_prereqs(&header, argc, argv);\n+\t}\n \tif (!strcmp(cmd, \"create\")) {\n \t\tif (nongit)\n \t\t\tdie(\"Need a repository to create a bundle.\");\n@@ -443,4 +460,3 @@ int cmd_bundle(int argc, const char **argv, const char *prefix)\n \t} else\n \t\tusage(bundle_usage);\n }\n-\n-- \n1.5.0.3.862.g71037\n"},{"id":"36398","messageId":"Pine.LNX.4.63.0703060137210.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"7vejo3xuq9.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-06T01:12:16Z","receivedAt":"2007-03-06T01:12:16Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 5 Mar 2007, Junio C Hamano wrote:\n\n>  - rip out the boundary logic from the commit walker. Placing\n>    \"negative\" commits in the revs->commits list was Ok if all we\n>    cared about \"boundary\" was the UNINTERESTING limiting case,\n>    but conceptually it was wrong.\n\nI agree.\n\n> It loses more code than it adds, even when the new gc_boundary()\n> function, which is purely for early optimization, is counted.\n\nI have the slight suspicion that it might be faster if gc_boundary() was \nnot called at all... But that's probably a subject for later.\n\n> Note that this patch is purely for eyeballing and discussion\n> only.  It breaks git-bundle's verify logic because the logic\n> does not use BOUNDARY_SHOW flag for its internal computation\n> anymore.  After we correct it not to attempt to affect the\n> boundary processing by setting the BOUNDARY_SHOW flag, we can\n> remove BOUNDARY_SHOW from revision.h and use that bit assignment\n> for the new CHILD_SHOWN flag.\n\nYes, git-bundle should be easy enough to fix.\n\n> +\tstruct commit_list *l;\n> +\n> +\tif (revs->boundary == 2) {\n> +\t\tunsigned i;\n> +\t\tstruct object_array *array = &revs->boundary_commits;\n> +\t\tstruct object_array_entry *objects = array->objects;\n> +\t\tfor (i = 0; i < array->nr; i++) {\n\nAn easy optimisation would be iterate in the other direction, resetting \narray->nr after the loop. Of course, this does not preserve the order...\n\n> +\tif (revs->reverse) {\n> +\t\tl = NULL;\n> +\t\twhile ((c = get_revision_1(revs)))\n> +\t\t\tcommit_list_insert(c, &l);\n> +\t\trevs->commits = l;\n> +\t\trevs->reverse = 0;\n>  \t}\n\nClever!\n\n>  \n> -\t/* Check the max_count ... */\n> +\t/*\n> +\t * Now pick up what they want to give us\n> +\t */\n> +\tc = get_revision_1(revs);\n> +\twhile (0 < revs->skip_count) {\n> +\t\trevs->skip_count--;\n> +\t\tc = get_revision_1(revs);\n> +\t\tif (!c)\n> +\t\t\tbreak;\n> +\t}\n> +\n> +\t/*\n> +\t * Check the max_count.\n> +\t */\n>  \tswitch (revs->max_count) {\n>  \tcase -1:\n>  \t\tbreak;\n>  \tcase 0:\n> -\t\tif (revs->boundary) {\n> -\t\t\tstruct commit_list *list = revs->commits;\n> -\t\t\twhile (list) {\n> -\t\t\t\tlist->item->object.flags |=\n> -\t\t\t\t\tBOUNDARY_SHOW | BOUNDARY;\n> -\t\t\t\tlist = list->next;\n> -\t\t\t}\n> -\t\t\t/* all remaining commits are boundary commits */\n> -\t\t\trevs->max_count = -1;\n> -\t\t\trevs->limited = 1;\n> -\t\t} else\n> -\t\t\treturn NULL;\n> +\t\tc = NULL;\n> +\t\tbreak;\n\nI guess that you want to do this instead:\n\n\tcase 0:\n\t\tc = NULL;\n\t\t/* fall through */\n>  \tdefault:\n>  \t\trevs->max_count--;\n\nso that --reverse actually works (otherwise, the while() loop would \ndeplete max_count, and then max_count would be 0, and nothing would be \nreturned).\n\n> +\t/*\n> +\t * boundary commits are the commits that are parents of the\n> +\t * ones we got from get_revision_1() but they themselves are\n> +\t * not returned from get_revision_1().  Before returning\n> +\t * 'c', we need to mark its parents that they could be boundaries.\n> +\t */\n> +\n> +\tfor (l = c->parents; l; l = l->next) {\n\nAFAICT this changes behaviour: c->parents were possibly rewritten. But I \nguess it makes sense showing the rewritten parents as boundary commits, \nnot the real parents.\n\n> +\t\tstruct object *p;\n> +\t\tp = &(l->item->object);\n> +\t\tif (p->flags & CHILD_SHOWN)\n\n... or\n\t\tif (p->flags & (CHILD_SHOWN | SHOWN))\n\n?\n\nCiao,\nDscho\n"},{"id":"36400","messageId":"7vd53nupg9.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"Pine.LNX.4.63.0703060137210.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T01:32:22Z","receivedAt":"2007-03-06T01:32:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n>> +\tif (revs->reverse) {\n>> +\t\tl = NULL;\n>> +\t\twhile ((c = get_revision_1(revs)))\n>> +\t\t\tcommit_list_insert(c, &l);\n>> +\t\trevs->commits = l;\n>> +\t\trevs->reverse = 0;\n>>  \t}\n>\n> Clever!\n\nIt is not clever, but just is stupid and WRONG.  It just shows\nhow little I care about --reverse ;-).\n\nrevision_1() is to get the full list without non limit limiters,\nso the above loop would not even deplete the max_count but\nliterally grabs everything.\n\nArguably, you can do \"rev-list --reverse -2 master\" to get the\nfirst two commits with this, but it was not intended.  We would\nneed to grab (skip + max_count) from get_revision_1() and set\nmax_count to -1 before leaving the if () {} here, or something\nlike that.\n\n> I guess that you want to do this instead:\n>\n> \tcase 0:\n> \t\tc = NULL;\n> \t\t/* fall through */\n>>  \tdefault:\n>>  \t\trevs->max_count--;\n>\n> ...\n\nActually that is not correct either.  The other patch fixes it\n(but not the unintended semantic change to --reverse).\n\n>> +\tfor (l = c->parents; l; l = l->next) {\n>\n> AFAICT this changes behaviour: c->parents were possibly rewritten.\n\nWell, the behaviour of max with boundary in 'master' did the\nsame thing, as what was in revs->commits are rewritten parents\nof commits we already returned, didn't it?\n\n> But I \n> guess it makes sense showing the rewritten parents as boundary commits, \n> not the real parents.\n>\n>> +\t\tstruct object *p;\n>> +\t\tp = &(l->item->object);\n>> +\t\tif (p->flags & CHILD_SHOWN)\n>\n> ... or\n> \t\tif (p->flags & (CHILD_SHOWN | SHOWN))\n\n\"If itself is shown it cannot be a boundary, and if we know we\nmarked it as potential boundary we do not have to mark it\nagain\"...  I think you are right.\n"},{"id":"36403","messageId":"Pine.LNX.4.63.0703060242130.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"7vd53nupg9.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-06T01:44:28Z","receivedAt":"2007-03-06T01:44:28Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 5 Mar 2007, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> >> +\tif (revs->reverse) {\n> >> +\t\tl = NULL;\n> >> +\t\twhile ((c = get_revision_1(revs)))\n> >> +\t\t\tcommit_list_insert(c, &l);\n> >> +\t\trevs->commits = l;\n> >> +\t\trevs->reverse = 0;\n> >>  \t}\n> >\n> > Clever!\n> \n> It is not clever, but just is stupid and WRONG.  It just shows\n> how little I care about --reverse ;-).\n> \n> revision_1() is to get the full list without non limit limiters,\n> so the above loop would not even deplete the max_count but\n> literally grabs everything.\n\nOops. I missed the _1(), _and_ the missing \"revs->reverse = 0\"...\n\n> >> +\tfor (l = c->parents; l; l = l->next) {\n> >\n> > AFAICT this changes behaviour: c->parents were possibly rewritten.\n> \n> Well, the behaviour of max with boundary in 'master' did the same thing, \n> as what was in revs->commits are rewritten parents of commits we already \n> returned, didn't it?\n\nI missed that, too. Maybe I should get more familiar with the revision \nwalker first, before continuing to ask for ridicule.\n\nCiao,\nDscho\n"},{"id":"36404","messageId":"7v8xebuo8t.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"Pine.LNX.4.63.0703060242130.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] revision walker: Fix --boundary when limited","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T01:58:26Z","receivedAt":"2007-03-06T01:58:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> I missed that, too. Maybe I should get more familiar with the revision \n> walker first,...\n\nNo.  You are asking the right questions and helped finding a few\nbugs already.\n"},{"id":"36406","messageId":"Pine.LNX.4.63.0703060253140.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"7vzm6rurst.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 2/4] revision traversal: retire BOUNDARY_SHOW","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-06T02:05:34Z","receivedAt":"2007-03-06T02:05:34Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 5 Mar 2007, Junio C Hamano wrote:\n\n> This removes the flag internally used by revision traversal to\n> decide which commits are indeed boundaries and renames it to\n> CHILD_SHOWN.  builtin-bundle uses the symbol for its\n> verification, but I think the logic it uses it is wrong.  The\n> flag is still useful but it is local to the git-bundle, so it is\n> renamed to PREREQ_MARK.\n\nThe idea was to bail out of revision walking when that prerequisite was \nfound, _even_ if it happened to be uninteresting.\n\nJust marking the parents uninteresting unless they are prerequisites would \nbe better, probably.\n\n>  \n>  \ti = req_nr;\n>  \twhile (i && (commit = get_revision(&revs)))\n> -\t\tif (commit->object.flags & BOUNDARY_SHOW)\n> +\t\tif (commit->object.flags & PREREQ_MARK)\n>  \t\t\ti--;\n\nThe above-mentioned idea, then would be: instead of just i--; do\n\n\t\t{\n\t\t\tstruct commit_list *parent = commit->parents;\n\t\t\ti--;\n\t\t\tfor (; parent; parent = parent->next)\n\t\t\t\tif (!(parent->item->object.flag & \n\t\t\t\t\t\tPREREQ_MARK))\n\t\t\t\t\tparent->item->object.flag |=\n\t\t\t\t\t\tUNINTERESTING;\n\t\t}\n\nThis should help performance, as not all reachable commits are traversed \nany more.\n\n>  \n>  \tfor (i = 0; i < req_nr; i++)\n> diff --git a/revision.c b/revision.c\n> index 5d137ea..2d27ccf 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -1285,17 +1285,21 @@ struct commit *get_revision(struct rev_info *revs)\n>  \t\t\tcommit_list_insert(c, &l);\n>  \t\trevs->commits = l;\n>  \t\trevs->reverse = 0;\n> +\t\tc = NULL;\n\nWhy? It gets assigned here anyway:\n\n>  \t}\n>  \n>  \t/*\n>  \t * Now pick up what they want to give us\n>  \t */\n> -\tc = get_revision_1(revs);\n> +\tif (!(c = get_revision_1(revs)))\n> +\t\treturn NULL;\n\n\n>  \twhile (0 < revs->skip_count) {\n>  \t\trevs->skip_count--;\n>  \t\tc = get_revision_1(revs);\n>  \t\tif (!c)\n>  \t\t\tbreak;\n> +\t\t/* Although we grabbed it, it is not shown. */\n> +\t\tc->object.flags &= ~SHOWN;\n\nWasn't --skip meant for something like gitweb, where you just want to skip \nthe first <n> commits from the list, but do not want to change the list \notherwise?\n\n> @@ -1305,6 +1309,9 @@ struct commit *get_revision(struct rev_info *revs)\n>  \tcase -1:\n>  \t\tbreak;\n>  \tcase 0:\n> +\t\t/* Although we grabbed it, it is not shown. */\n> +\t\tif (c)\n> +\t\t\tc->object.flags &= ~SHOWN;\n>  \t\tc = NULL;\n\nIs this really relevant in practice?\n\nCiao,\nDscho\n"},{"id":"36407","messageId":"Pine.LNX.4.63.0703060310120.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"7vtzwzurss.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/4] git-bundle: various fixups","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-06T02:13:42Z","receivedAt":"2007-03-06T02:13:42Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 5 Mar 2007, Junio C Hamano wrote:\n\n> verify_bundle() returned with an error early only when all\n> prerequisite commits were missing.  It should error out much\n> earlier when some are missing.\n\nThe idea was to list _all_ missing prerequisites so that git-bundle will \nnot complain _again_, about different missing prerequisites, when the \nfirst set of missing prerequisites was obtained.\n\nThe check only prevented looking for _reachable_ commits, when none of the \nprerequisites were found in the object database to begin with.\n\n> When the rev-list is limited in ways other than revision range (e.g. \n> --max-count or --max-age), create_bundle() listed all positive refs \n> given from the command line as if they are available, but resulting pack \n> may not have some of them.  Add a logic to make sure all of them are \n> included, and error out otherwise.\n\nGood catch!\n\nCiao,\nDscho\n"},{"id":"36408","messageId":"7v4pozuncr.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"Pine.LNX.4.63.0703060253140.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH 2/4] revision traversal: retire BOUNDARY_SHOW","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T02:17:40Z","receivedAt":"2007-03-06T02:17:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> On Mon, 5 Mar 2007, Junio C Hamano wrote:\n>\n>> This removes the flag internally used by revision traversal to\n>> decide which commits are indeed boundaries and renames it to\n>> CHILD_SHOWN.  builtin-bundle uses the symbol for its\n>> verification, but I think the logic it uses it is wrong.  The\n>> flag is still useful but it is local to the git-bundle, so it is\n>> renamed to PREREQ_MARK.\n>\n> The idea was to bail out of revision walking when that prerequisite was \n> found, _even_ if it happened to be uninteresting.\n>\n> Just marking the parents uninteresting unless they are prerequisites would \n> be better, probably.\n>\n>>  \n>>  \ti = req_nr;\n>>  \twhile (i && (commit = get_revision(&revs)))\n>> -\t\tif (commit->object.flags & BOUNDARY_SHOW)\n>> +\t\tif (commit->object.flags & PREREQ_MARK)\n>>  \t\t\ti--;\n>\n> The above-mentioned idea, then would be: instead of just i--; do\n\nI explicitly wanted to avoid that.  If the generated bundle had\nprereqs that are not independent of each other, doing that would\nhide some prereqs.\n\n> This should help performance, as not all reachable commits are traversed \n> any more.\n\nYou prevented that with \"while (i &&\" part already, didn't you?\n\n> Wasn't --skip meant for something like gitweb, where you just want to skip \n> the first <n> commits from the list, but do not want to change the list \n> otherwise?\n\nYes, but does the patch change that?\n\n>\n>> @@ -1305,6 +1309,9 @@ struct commit *get_revision(struct rev_info *revs)\n>>  \tcase -1:\n>>  \t\tbreak;\n>>  \tcase 0:\n>> +\t\t/* Although we grabbed it, it is not shown. */\n>> +\t\tif (c)\n>> +\t\t\tc->object.flags &= ~SHOWN;\n>>  \t\tc = NULL;\n>\n> Is this really relevant in practice?\n\nAbsolutely.  But I have further updates on this series.\n"},{"id":"36409","messageId":"7vzm6rt8hu.fsf_-_@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"7v4pozuncr.fsf@assigned-by-dhcp.cox.net","subject":"SHOWN means shown","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T02:23:57Z","receivedAt":"2007-03-06T02:23:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This moves the code to set SHOWN on the commit from get_revision_1() \nback to get_revision(), so that the bit means what it originally\nmeant: this commit has been given back to the caller.\n\nAlso it fixes the --reverse breakage Dscho pointed out.\n\n---\n\n  Junio C Hamano <junkio@cox.net> writes:\n\n  >> Is this really relevant in practice?\n  >\n  > Absolutely.  But I have further updates on this series.\n\n  ... otherwise, \"git-bundle create -3 A B\" when B is A~3 would\n  mistakenly say \"Ah, B is SHOWN so include it\".\n\n revision.c |   26 ++++++++++++++++++--------\n 1 files changed, 18 insertions(+), 8 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 2d27ccf..35a1711 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1227,7 +1227,6 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->parents)\n \t\t\t\trewrite_parents(revs, commit);\n \t\t}\n-\t\tcommit->object.flags |= SHOWN;\n \t\treturn commit;\n \t} while (revs->commits);\n \treturn NULL;\n@@ -1280,11 +1279,22 @@ struct commit *get_revision(struct rev_info *revs)\n \t}\n \n \tif (revs->reverse) {\n+\t\tint limit = -1;\n+\n+\t\tif (0 <= revs->max_count) {\n+\t\t\tlimit = revs->max_count;\n+\t\t\tif (0 < revs->skip_count)\n+\t\t\t\tlimit += revs->skip_count;\n+\t\t}\n \t\tl = NULL;\n-\t\twhile ((c = get_revision_1(revs)))\n+\t\twhile ((c = get_revision_1(revs))) {\n \t\t\tcommit_list_insert(c, &l);\n+\t\t\tif ((0 < limit) && !--limit)\n+\t\t\t\tbreak;\n+\t\t}\n \t\trevs->commits = l;\n \t\trevs->reverse = 0;\n+\t\trevs->max_count = -1;\n \t\tc = NULL;\n \t}\n \n@@ -1298,8 +1308,6 @@ struct commit *get_revision(struct rev_info *revs)\n \t\tc = get_revision_1(revs);\n \t\tif (!c)\n \t\t\tbreak;\n-\t\t/* Although we grabbed it, it is not shown. */\n-\t\tc->object.flags &= ~SHOWN;\n \t}\n \n \t/*\n@@ -1310,16 +1318,18 @@ struct commit *get_revision(struct rev_info *revs)\n \t\tbreak;\n \tcase 0:\n \t\t/* Although we grabbed it, it is not shown. */\n-\t\tif (c)\n-\t\t\tc->object.flags &= ~SHOWN;\n \t\tc = NULL;\n \t\tbreak;\n \tdefault:\n \t\trevs->max_count--;\n \t}\n \n-\tif (!revs->boundary)\n+\tif (c)\n+\t\tc->object.flags |= SHOWN;\n+\n+\tif (!revs->boundary) {\n \t\treturn c;\n+\t}\n \n \tif (!c) {\n \t\t/*\n@@ -1341,7 +1351,7 @@ struct commit *get_revision(struct rev_info *revs)\n \tfor (l = c->parents; l; l = l->next) {\n \t\tstruct object *p;\n \t\tp = &(l->item->object);\n-\t\tif (p->flags & CHILD_SHOWN)\n+\t\tif (p->flags & (CHILD_SHOWN | SHOWN))\n \t\t\tcontinue;\n \t\tp->flags |= CHILD_SHOWN;\n \t\tgc_boundary(&revs->boundary_commits);\n"},{"id":"36410","messageId":"Pine.LNX.4.63.0703060322270.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"7v4pozuncr.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 2/4] revision traversal: retire BOUNDARY_SHOW","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-06T02:29:38Z","receivedAt":"2007-03-06T02:29:38Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 5 Mar 2007, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > Just marking the parents uninteresting unless they are prerequisites \n> > would be better, probably.\n> >\n> >>  \n> >>  \ti = req_nr;\n> >>  \twhile (i && (commit = get_revision(&revs)))\n> >> -\t\tif (commit->object.flags & BOUNDARY_SHOW)\n> >> +\t\tif (commit->object.flags & PREREQ_MARK)\n> >>  \t\t\ti--;\n> >\n> > The above-mentioned idea, then would be: instead of just i--; do\n> \n> I explicitly wanted to avoid that.  If the generated bundle had\n> prereqs that are not independent of each other, doing that would\n> hide some prereqs.\n\nYes. I wanted to say SHOWN instead of UNINTERESTING, but reading the \nsource again, it seems that add_parents_to_list() is called in \nget_revision_1() even if the commit is marked SHOWN.\n\nSo forget about that idea of mine.\n\n> > This should help performance, as not all reachable commits are traversed \n> > any more.\n> \n> You prevented that with \"while (i &&\" part already, didn't you?\n\nWell, yes. I also wanted to prevent going down all paths, though.\n\n> > Wasn't --skip meant for something like gitweb, where you just want to \n> > skip the first <n> commits from the list, but do not want to change \n> > the list otherwise?\n> \n> Yes, but does the patch change that?\n\nI _think_ that yes, it could. If the timestamp of HEAD is older than of \nHEAD^, and you say \"git log HEAD^ HEAD\", then HEAD^ will be actually shown \nfirst, right? If you then say \"--skip 1\", HEAD will be shown first, and \nthen HEAD^...\n\n> >> @@ -1305,6 +1309,9 @@ struct commit *get_revision(struct rev_info *revs)\n> >>  \tcase -1:\n> >>  \t\tbreak;\n> >>  \tcase 0:\n> >> +\t\t/* Although we grabbed it, it is not shown. */\n> >> +\t\tif (c)\n> >> +\t\t\tc->object.flags &= ~SHOWN;\n> >>  \t\tc = NULL;\n> >\n> > Is this really relevant in practice?\n> \n> Absolutely.  But I have further updates on this series.\n\nSorry for interrupting your patch spree :-)\n\nCiao,\nDscho\n"},{"id":"36458","messageId":"7vd53mppvb.fsf@assigned-by-dhcp.cox.net","threadId":"7093","inReplyTo":"Pine.LNX.4.63.0703060322270.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH 2/4] revision traversal: retire BOUNDARY_SHOW","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-06T11:34:32Z","receivedAt":"2007-03-06T11:34:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n>> > This should help performance, as not all reachable commits are traversed \n>> > any more.\n>> \n>> You prevented that with \"while (i &&\" part already, didn't you?\n>\n> Well, yes. I also wanted to prevent going down all paths, though.\n\nIf we wanted to bundle \"-8 A B\", I think we would make 'x' and\n'y' prereqs, as they are the direct parents commits that are\nshown, and that themselves are not shown.\n\n         .---*---*---*---*---* A\n        /\n    ---x---y---*---*---* B\n\nIf we say upon hitting prereq (x and y) we stop traversal by\nmarking the parent UNINTERESTING, I suspected that we may not\nfind out 'x' with get_revision() loop, and that was why I chose\nnot to.  Instead the loop stops by finding y and then x (and by\nsaying \"ok I needed to find two and now I have two\".\n\nBut this probably needs more optimization.\n"},{"id":"36466","messageId":"Pine.LNX.4.63.0703061643490.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7093","inReplyTo":"7vd53mppvb.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 2/4] revision traversal: retire BOUNDARY_SHOW","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-06T15:52:21Z","receivedAt":"2007-03-06T15:52:21Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 6 Mar 2007, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> >> > This should help performance, as not all reachable commits are \n> >> > traversed any more.\n> >> \n> >> You prevented that with \"while (i &&\" part already, didn't you?\n> >\n> > Well, yes. I also wanted to prevent going down all paths, though.\n> \n> If we wanted to bundle \"-8 A B\", I think we would make 'x' and\n> 'y' prereqs, as they are the direct parents commits that are\n> shown, and that themselves are not shown.\n> \n>          .---*---*---*---*---* A\n>         /\n>     ---x---y---*---*---* B\n> \n> If we say upon hitting prereq (x and y) we stop traversal by\n> marking the parent UNINTERESTING, I suspected that we may not\n> find out 'x' with get_revision() loop, and that was why I chose\n> not to.  Instead the loop stops by finding y and then x (and by\n> saying \"ok I needed to find two and now I have two\".\n\nYes, that is correct. What I wanted to optimize for was this:\n\nx--*--*--A\n\ny--*--B\n\nThere is no need to traverse the parents of y to find x. I wanted for the \ntraversal to just stop on paths where a prereq was found.\n\nBut setting the parents to UNINTERESTING or SHOWN was wrong, because that \nwould not stop the traversal: see get_revision_1(). In case revs->limited \nis 0, and the cutoff date is not yet reached, the parents are added \nalways. Even if the current commit is UNINTERESTING or SHOWN. (Which is \ncorrect, of course.)\n\nBTW this behaviour with revs->limited = 1 made me set revs->limited in \ncase of revs->reverse in the first place...\n\nCiao,\nDscho\n"}]}