{"thread":{"id":"13655","subject":"rev-list --parents --full-history + path: something's fishy","startedAt":"2008-05-24T20:16:54Z","lastAt":"2008-05-28T05:25:10Z","messageCount":9,"participants":["Johannes Sixt","Linus Torvalds","David Tweed","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"77668","messageId":"1211660214.483877b69a107@webmail.nextra.at","threadId":"13655","inReplyTo":"e1dab3980805230808s59798351r9ed702c7d0dedd2a@mail.gmail.com","subject":"rev-list --parents --full-history + path: something's fishy","fromName":"Johannes Sixt","fromEmail":"johannes.sixt@telecom.at","sentAt":"2008-05-24T20:16:54Z","receivedAt":"2008-05-24T20:16:54Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"This script creates this history:\n\n    C--M\n   /  /\n  A--B\n\nCommits A and B modify file a.\n\ngit init\necho a > a\ngit add a\ngit commit -m A\necho 1 > a\ngit commit -m B -a\ngit checkout -b side master~1\necho b > b\ngit add b\ngit commit -m C\ngit merge master\n\nAt this point, this command returns the expected output (SHA1s rewritten to\nA,B,C,M as above):\n\n$ git rev-list --full-history HEAD -- a\nB\nA\n\nbut this does not:\n\n$ git rev-list --full-history --parents HEAD -- a\nM A B\nB A\nA\n\nOf course, I'd expected to see this:\n\n$ git rev-list --full-history --parents HEAD -- a\nB A\nA\n\nJust as a heads-up, I've also seen a case (in David's repository) where a\n\ngit rev-list --full-history --parents --reverse HEAD -- some/path\n\nincorrectly prints a commit somewhere in the middle *without* a parent where it\ndefinitely should have printed a parent. I don't have a repeatable small\ntest-case, yet.\n\n-- Hannes\n"},{"id":"77686","messageId":"alpine.LFD.1.10.0805241817500.3081@woody.linux-foundation.org","threadId":"13655","inReplyTo":"1211660214.483877b69a107@webmail.nextra.at","subject":"Re: rev-list --parents --full-history + path: something's fishy","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-05-25T01:21:54Z","receivedAt":"2008-05-25T01:21:54Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 24 May 2008, Johannes Sixt wrote:\n> \n> but this does not:\n> \n> $ git rev-list --full-history --parents HEAD -- a\n> M A B\n> B A\n> A\n\nThat is the \"correct\" output.\n\nThat's what \"--full-history\" means: do not simplify merges away when all \nthe data comes from just one branch (in this case from \"B\").\n\nSo it shows you commit 'M' because you asked for full-history.\n\nCommit 'M' has parents 'C' and 'B', but since 'C' doesn't actually modify \nthe file at all, the regular commit simplification will simplify 'C' away, \nso now that parent 'C' will become 'A'. So 'M' has the _simplified_ \nparent's 'A' and 'B'.\n\nThen it shows 'B' (parent 'A') and 'A' (no parent).\n\n> Of course, I'd expected to see this:\n> \n> $ git rev-list --full-history --parents HEAD -- a\n> B A\n> A\n\nWhy did you ask for --full-history, if you're not interested in merges \nthat are irrelevant? To get what you wanted, just do\n\n\tgit rev-list --parents HEAD -- a\n\nand it should give you exactly that output.\n\n\t\tLinus\n"},{"id":"77703","messageId":"200805251426.54755.johannes.sixt@telecom.at","threadId":"13655","inReplyTo":"alpine.LFD.1.10.0805241817500.3081@woody.linux-foundation.org","subject":"Re: rev-list --parents --full-history + path: something's fishy","fromName":"Johannes Sixt","fromEmail":"johannes.sixt@telecom.at","sentAt":"2008-05-25T12:26:53Z","receivedAt":"2008-05-25T12:26:53Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"On Sunday 25 May 2008 03:21, Linus Torvalds wrote:\n> On Sat, 24 May 2008, Johannes Sixt wrote:\n> > but this does not:\n> >\n> > $ git rev-list --full-history --parents HEAD -- a\n> > M A B\n> > B A\n> > A\n>\n> That is the \"correct\" output.\n>\n> That's what \"--full-history\" means: do not simplify merges away when all\n> the data comes from just one branch (in this case from \"B\").\n>\n> So it shows you commit 'M' because you asked for full-history.\n>\n> Commit 'M' has parents 'C' and 'B', but since 'C' doesn't actually modify\n> the file at all, the regular commit simplification will simplify 'C' away,\n> so now that parent 'C' will become 'A'. So 'M' has the _simplified_\n> parent's 'A' and 'B'.\n>\n> Then it shows 'B' (parent 'A') and 'A' (no parent).\n\nThe history was this:\n\n   C--M\n  /  /\n A--B\n\nNow assume that both B and C change a, but so that it is identical in both B \nand C. I thought that --full-history makes a difference *only* for this case, \nbecause without --full-history the revision walk would choose either B or C \n(not quite at random, but in an unspecified manner), but not both; but \nwith --full-history the revision walk would go both paths.\n\nThis makes a difference in git-filter-branch --subdirectory-filter: We do want \nto simplify history to those commits that touch a path, but we don't want to \nsimplify away the case outlined in the previous paragraph.\n\n> > Of course, I'd expected to see this:\n> >\n> > $ git rev-list --full-history --parents HEAD -- a\n> > B A\n> > A\n>\n> Why did you ask for --full-history, if you're not interested in merges\n> that are irrelevant? To get what you wanted, just do\n>\n> \tgit rev-list --parents HEAD -- a\n>\n> and it should give you exactly that output.\n\nIn the case at hand this would be sufficient, but in git-filter-branch we \ndon't want to prune branches whose modifications to a path make the path \nidentical.\n\nWhat shall we do in git-filter-branch --subdirectory-filter?\n\n-- Hannes\n"},{"id":"77719","messageId":"200805252158.22514.johannes.sixt@telecom.at","threadId":"13655","inReplyTo":"alpine.LFD.1.10.0805241817500.3081@woody.linux-foundation.org","subject":"Re: rev-list --parents --full-history + path: something's fishy","fromName":"Johannes Sixt","fromEmail":"johannes.sixt@telecom.at","sentAt":"2008-05-25T19:58:22Z","receivedAt":"2008-05-25T19:58:22Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"On Sunday 25 May 2008 03:21, Linus Torvalds wrote:\n> On Sat, 24 May 2008, Johannes Sixt wrote:\n> > but this does not:\n> >\n> > $ git rev-list --full-history --parents HEAD -- a\n> > M A B\n> > B A\n> > A\n>\n> That is the \"correct\" output.\n\nBut why does this:\n\n$ git rev-list --full-history HEAD -- a\nB\nA\n\nnot list M (note the lack of --parents)?\n\n-- Hannes\n"},{"id":"77721","messageId":"alpine.LFD.1.10.0805251359290.3081@woody.linux-foundation.org","threadId":"13655","inReplyTo":"200805251426.54755.johannes.sixt@telecom.at","subject":"Re: rev-list --parents --full-history + path: something's fishy","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-05-25T21:23:48Z","receivedAt":"2008-05-25T21:23:48Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 25 May 2008, Johannes Sixt wrote:\n> \n> The history was this:\n> \n>    C--M\n>   /  /\n>  A--B\n> \n> Now assume that both B and C change a, but so that it is identical in both B \n> and C. I thought that --full-history makes a difference *only* for this case, \n> because without --full-history the revision walk would choose either B or C \n> (not quite at random, but in an unspecified manner), but not both; but \n> with --full-history the revision walk would go both paths.\n\nYou mis-understood what --full history does.\n\nIt literally just means \"walk all paths\". The fact that *also* means that \nit often cannot simplify away merges at all is unfortunate, but there you \nhave it.\n\nIn other words, it will now leave the merge alone, even if it can see that \neverything we care about (file 'a') came from just one side.\n\n> This makes a difference in git-filter-branch --subdirectory-filter: We do want \n> to simplify history to those commits that touch a path, but we don't want to \n> simplify away the case outlined in the previous paragraph.\n\nIf so, you need to expand on the history simplification a *lot*. \n\nIt currently does two things:\n\n - simplify away merges when it can see that one parent is identical in \n   content to the end result - it then removes the merge entirely, and \n   replaces it with the identical parent.\n\n   This is the thing that would normally take the merge 'M', and just \n   replace it with 'B', because it sees that the contents all come from B. \n   But if 'C' _also_ changed the file, and 'M' was actually a data merge, \n   then it will be left alone (because the merge 'M' really is meaningful \n   as far as the data is concerned)\n\n   This is what \"--full-history\" disables.\n\n   So when you say \"--full-history\", all merges are left alone.\n\n - The *other* simplification is the non-merge case, where it simplifies \n   away commits that don't change the files. This is the one that then \n   removes 'C' in your original example.\n\n   You can disable this simplification with \"--sparse\". Not that anybody \n   ever wants to.\n\nWhat you seem to want in a *third* level of simplification, which is to \nremove merges that turn out to be pointless, because all parents end up \nbeing directly related. We don't do that simplification, and we never \nhave.\n\nI'd love to do it, but it's somewhat costly and very much more complicated \nthan the simplifications we do do.\n\n> What shall we do in git-filter-branch --subdirectory-filter?\n\nSee above. I can tell you _where_ you'd need to add the logic. See the \nfile revision.c: remove_duplicate_parents(). You'd could \"just\" extend \nthat to remove not just 100% duplicates, but also remove parents that are \ndirect ancestors of each other. I say \"just\" in quotes, because that's not \ntrivial to do efficiently.\n\nBut it gets worse. If that removal of parents then turns the commit into a \nregular one, *and* it didn't actually change the files you are interested \nin, you'd need to remove it entirely, which in turn means that you'd also \nneed to rewrite the parent information of the children. Which means that \nsimplify_commit() is actually too late, because that one happens when you \nprint things out, and the children have already been returned (with what \nnow is stale parenthood!).\n\nSo the _obvious_ place to do that simplification is actually too late. \n\nBut doing it earlier is also hard, because that \"simplify_commit()\" is \nwhat removes the trivial linear ones.\n\nSo you'd actually need to add a whole new phase that removes the trivial \nlinear cases *before* we are in the whole get_revision() phase, and then \ndoes the commit simplification. It's nasty and quite complicated. Which is \nwhy we don't do it.\n\nThe \"revision.c\" commit history simplification is already arguably some of \nthe most complicated and subtle code in all of git. The code needs to be \nable to handle the \"normal\" case (which is to stream the commits without \npre-computing the whole DAG) efficiently, but then there are those \ncomplicated cases that need the whole DAG. And they have to live \nside-by-side.\n\n\t\t\tLinus\n"},{"id":"77723","messageId":"alpine.LFD.1.10.0805251424040.3081@woody.linux-foundation.org","threadId":"13655","inReplyTo":"200805252158.22514.johannes.sixt@telecom.at","subject":"Re: rev-list --parents --full-history + path: something's fishy","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-05-25T21:30:28Z","receivedAt":"2008-05-25T21:30:28Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 25 May 2008, Johannes Sixt wrote:\n> \n> But why does this:\n> \n> $ git rev-list --full-history HEAD -- a\n> B\n> A\n> \n> not list M (note the lack of --parents)?\n\nBecause when we don't ask for --parents, the whole problem is *much* \nsimpler. The parent rewriting means that the history has to all \"fit \ntogether\". But when you don't need parenthood, then suddenly that doesn't \nmatter at all - who cares if it fits together or not, when you can't *see* \nthat it doesn't fit together anyway?\n\nIn this case, it's \"simplify_commit()\", and this piece of code in \nparticular (note how it's even commented!):\n\n\t\t...\n                /* Commit without changes? */\n                if (commit->object.flags & TREESAME) {\n                        /* drop merges unless we want parenthood */\n                        if (!revs->rewrite_parents)\n                                return commit_ignore;\n\t\t...\n\nie if we're looking at a commit that doesn't actually introduce any \nchanges of its own (it took all the changes from at least _one_ of its \nparents - ie it got TREESAME set because the tree was identical to one of \nthe parents), then if we don't have 'rewrite_parents' set, we just drop \nthat commit, because it is uninteresting.\n\nIOW, we dropped 'M' because there was no point in showing it: we know \nnobody refers to it (because no other commit will list it as a parent!), \nand the commit itself didn't actually introduce any changes (because all \nthe changes came from 'B').\n\nBut we can *not* drop that merge commit when we do the parenthood \ntracking, because if we did so, we'd just have an \"empty spot\" in history \n(we have other commits that point to that emrge and list it as a parent).\n\nOf course, in your trivial example, that didn't actually happen (because \n'M' was the top commit), but try it with something more complex.\n\n\t\t\tLinus\n"},{"id":"77788","messageId":"200805262109.19015.johannes.sixt@telecom.at","threadId":"13655","inReplyTo":"alpine.LFD.1.10.0805251359290.3081@woody.linux-foundation.org","subject":"[PATCH/RFC] Revert \"filter-branch: subdirectory filter needs --full-history\"","fromName":"Johannes Sixt","fromEmail":"johannes.sixt@telecom.at","sentAt":"2008-05-26T19:09:18Z","receivedAt":"2008-05-26T19:09:18Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"This reverts commit cfabd6eee1745cfec58cfcb794ce8847e43b888a. I had\nimplemented it without understanding what --full-history does. Consider\nthis history:\n\n    C--M--N\n   /  /  /\n  A--B  /\n   \\   /\n    D-/\n\nwhere B and C modify a path, X, in the same way so that the result is\nidentical, and D does not modify it at all. With the path limiter X and\nwithout --full-history this is simplified to\n\n   A--B\n\ni.e. only one of the paths via B or C is chosen. I had assumed that\n--full-history would keep both paths like this\n\n    C--M\n   /  /\n  A--B\n\nremoving the path via D; but in fact it keeps the entire history.\n\nCurrently, git does not have the capability to simplify to this\nintermediary case. However, the other extreme to keep the entire history\nis not wanted either in usual cases. I think we can expect that histories\nlike the above are rare, and in the usual cases we want a simplified\nhistory. So let's remove --full-history again.\n\n(Concerning t7003, subsequent tests depend on what the test case sets up,\nso we can't just back out the entire test case.)\n\nSigned-off-by: Johannes Sixt <johannes.sixt@telecom.at>\n---\n\nOn Sunday 25 May 2008 23:23, Linus Torvalds wrote:\n> On Sun, 25 May 2008, Johannes Sixt wrote:\n> > The history was this:\n> >\n> >    C--M\n> >   /  /\n> >  A--B\n> >\n> > Now assume that both B and C change a, but so that it is identical in\n> > both B and C. I thought that --full-history makes a difference *only* for\n> > this case, because without --full-history the revision walk would choose\n> > either B or C (not quite at random, but in an unspecified manner), but\n> > not both; but with --full-history the revision walk would go both paths.\n>\n> You mis-understood what --full history does.\n\nYes, indeed. Thank you for your explanations. I'm not prepared to dive into\nthe revision walk manchinery, so I instead propose to just remove\n--full-history from git-filter-branch.\n\n-- Hannes\n\n git-filter-branch.sh     |    2 +-\n t/t7003-filter-branch.sh |   13 ++-----------\n 2 files changed, 3 insertions(+), 12 deletions(-)\n\ndiff --git a/git-filter-branch.sh b/git-filter-branch.sh\nindex 80e99e5..d04c346 100755\n--- a/git-filter-branch.sh\n+++ b/git-filter-branch.sh\n@@ -234,7 +234,7 @@ case \"$filter_subdir\" in\n \t;;\n *)\n \tgit rev-list --reverse --topo-order --default HEAD \\\n-\t\t--parents --full-history \"$@\" -- \"$filter_subdir\"\n+\t\t--parents \"$@\" -- \"$filter_subdir\"\n esac > ../revs || die \"Could not get the commits\"\n commits=$(wc -l <../revs | tr -d \" \")\n \ndiff --git a/t/t7003-filter-branch.sh b/t/t7003-filter-branch.sh\nindex 1639c7a..3577aa6 100755\n--- a/t/t7003-filter-branch.sh\n+++ b/t/t7003-filter-branch.sh\n@@ -97,7 +97,7 @@ test_expect_success 'subdirectory filter result looks okay' '\n \ttest_must_fail git show sub:subdir\n '\n \n-test_expect_success 'setup and filter history that requires --full-history' '\n+test_expect_success 'more setup' '\n \tgit checkout master &&\n \tmkdir subdir &&\n \techo A > subdir/new &&\n@@ -107,16 +107,7 @@ test_expect_success 'setup and filter history that requires --full-history' '\n \tgit rm a &&\n \ttest_tick &&\n \tgit commit -m \"again subdir on master\" &&\n-\tgit merge branch &&\n-\tgit branch sub-master &&\n-\tgit-filter-branch -f --subdirectory-filter subdir sub-master\n-'\n-\n-test_expect_success 'subdirectory filter result looks okay' '\n-\ttest 3 = $(git rev-list -1 --parents sub-master | wc -w) &&\n-\tgit show sub-master^:new &&\n-\tgit show sub-master^2:new &&\n-\ttest_must_fail git show sub:subdir\n+\tgit merge branch\n '\n \n test_expect_success 'use index-filter to move into a subdirectory' '\n-- \n1.5.6.rc0.17.gbc20\n"},{"id":"77846","messageId":"e1dab3980805270355n6121ee9ehc285497b20b70a15@mail.gmail.com","threadId":"13655","inReplyTo":"200805262109.19015.johannes.sixt@telecom.at","subject":"Re: [PATCH/RFC] Revert \"filter-branch: subdirectory filter needs --full-history\"","fromName":"David Tweed","fromEmail":"david.tweed@gmail.com","sentAt":"2008-05-27T10:55:46Z","receivedAt":"2008-05-27T10:55:46Z","isPatch":true,"sender":{"key":"david.tweed@gmail.com","avatar":null},"body":"On Mon, May 26, 2008 at 8:09 PM, Johannes Sixt <johannes.sixt@telecom.at> wrote:\n> This reverts commit cfabd6eee1745cfec58cfcb794ce8847e43b888a. I had\n\nFWIW, applying this patch (getting 1.5.6.rc0.29.g3beb5.dirty) it now\nfilters the case I was trying successfully (although I understand\nJohannes' point that this fix only works because my commit graph is\nonly \"quite messy\" and it wouldn't work if it was \"extremely messy\":-)\n).\n\nThanks to Johannes for his time looking at this.\n\n-- \ncheers, dave tweed__________________________\ndavid.tweed@gmail.com\nRm 124, School of Systems Engineering, University of Reading.\n\"while having code so boring anyone can maintain it, use Python.\" --\nattempted insult seen on slashdot\n"},{"id":"77912","messageId":"7vbq2rxao9.fsf@gitster.siamese.dyndns.org","threadId":"13655","inReplyTo":"200805262109.19015.johannes.sixt@telecom.at","subject":"Re: [PATCH/RFC] Revert \"filter-branch: subdirectory filter needs --full-history\"","fromName":"Junio C Hamano","fromEmail":"junio@pobox.com","sentAt":"2008-05-28T05:25:10Z","receivedAt":"2008-05-28T05:25:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt <johannes.sixt@telecom.at> writes:\n\n> ... I'm not prepared to dive into\n> the revision walk manchinery, so I instead propose to just remove\n> --full-history from git-filter-branch.\n\nOk, let's punt for now and rethink this in the next cycle for 1.6.0.\n"}]}