{"thread":{"id":"33450","subject":"Locating merge that dropped a change","startedAt":"2013-04-09T18:00:41Z","lastAt":"2013-04-29T18:11:32Z","messageCount":25,"participants":["Kevin Bracey","Junio C Hamano","David Aguilar"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"213709","messageId":"51645749.8090402@bracey.fi","threadId":"33450","inReplyTo":null,"subject":"Locating merge that dropped a change","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-09T18:00:41Z","receivedAt":"2013-04-09T18:00:41Z","isPatch":false,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"This morning, I was struggling (not for the first time) to produce a Git \ncommand that would identify a merge commit that dropped a change. I \ncould see where it was added, but couldn't automate finding out why it \nwasn't any longer in HEAD.\n\nAll the permutations of \"--full-history\", \"-m\", \"-S\", \"-G\" on \"git log\" \nI could think of did not get me anywhere. As long as I had \n\"--full-history\", they could find the original commit that had added the \nchange, but not the merge commit that had dropped it by taking the other \nparent.\n\nSo, how to automatically find a merge that ignored a known change?\n\nAnd then for visualisation purposes, how do you persuade gitk's diff \ndisplay to actually show that that merge commit removed the change from \none of its parents? Again, \"-m\" didn't seem to work.\n\nHelp appreciated!\n\nKevin\n"},{"id":"213976","messageId":"5166F2C5.4020803@bracey.fi","threadId":"33450","inReplyTo":"51645749.8090402@bracey.fi","subject":"Re: Locating merge that dropped a change","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-11T17:28:37Z","receivedAt":"2013-04-11T17:28:37Z","isPatch":false,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 09/04/2013 21:00, Kevin Bracey wrote:\n>\n> So, how to automatically find a merge that ignored a known change?\n\nI think I've found the problem. It only doesn't work _if you specify the \nfile_.\n\nSpecifically, if I was missing an addition, my first attempt to find it \nwould be\n\n git log -p -m -S \n\nIf the addition was lost in a merge, that doesn't even show the \naddition, which is surprising, but intentional. The addition isn't part \nof the HEAD version of , so no point going down that path of the \nmerge. Fine. However, I expected this to work:\n\n git log --full-history -p -m -S \n\nBut it doesn't. It finds the addition, but _not_ the loss in the merge \ncommit.\n\nBut this does work:\n\n git log -p -m -S\n\nThat really feels like a bug to me. By specifying a file, I've made it \nmiss the change, and I can see no way to get the change without making \nit a full-tree operation.\n\nLooking at try_to_simplify_commit() it appears the merge that removed \nthe addition is excluded because it's TREESAME to its _other_ parent. \nBut with --full-history, we should only be eliminating a merge if its \nTREESAME to all parents, surely? Otherwise we have this case that we \nshow a commit but not its reversion.\n\nAnd the code doing this looks broken, or at least illogical - the parent \nloop sets \"tree_same\" for a same parent in --full-history, rather than \nimmediately setting the TREESAME flag, so maybe previous authors were \nthinking about this. But setting tree_same guarantees that TREESAME is \nalways set on exit anyway, so it's pointless (unless I'm missing something).\n\nIt does appear this is documented behaviour in the manual: \"full-history \nwithout parent rewriting\" .. \"P and M were excluded because they are \nTREESAME to _a_ parent.\" I would say that they should have been excluded \ndue to being TREESAME to _all_ parents. I really don't want a merge \nwhere one version of my file was chosen over another excluded from its \nso-called \"full history\".\n\nNow, obviously in a sane environment, most merges won't be that \ninteresting, as they'll just be propagating wanted patches from the real \ncommits already in the log. But I'd like some way to find merges that \ndrop code in a specified file, and surely \"--full-history\" is it?\n\nKevin\n"},{"id":"213997","messageId":"7v4nfcj2kq.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"5166F2C5.4020803@bracey.fi","subject":"Re: Locating merge that dropped a change","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-11T19:21:25Z","receivedAt":"2013-04-11T19:21:25Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> I think I've found the problem. It only doesn't work _if you specify\n> the file_.\n>\n> Specifically, if I was missing an addition, my first attempt to find\n> it would be\n>\n> git log -p -m -S \n>\n> If the addition was lost in a merge, that doesn't even show the\n> addition, which is surprising, but intentional. The addition isn't\n> part of the HEAD version of , so no point going down that path\n> of the merge. Fine. However, I expected this to work:\n>\n> git log --full-history -p -m -S \n>\n> But it doesn't. It finds the addition, but _not_ the loss in the merge\n> commit.\n>\n> But this does work:\n>\n> git log -p -m -S\n>\n> That really feels like a bug to me. By specifying a file, I've made it\n> miss the change, and I can see no way to get the change without making\n> it a full-tree operation.\n> ... But I'd like some way to find merges\n> that drop code in a specified file, and surely \"--full-history\" is it?\n\nYeah, I think that is a bug.\n\n $ echo first >file\n $ git add file && git commit -m initial\n $ git checkout -b side\n $ echo second >file && git commit -a -m side\n $ git checkout - && >file && git add file && git commit -m lose\n $ git merge -s ours -m lost side\n $ git log -p -m --full-history -Ssecond -1 file\n\ndoes not seem to find the commit that lost the line.\n"},{"id":"215111","messageId":"1366658602-12254-1-git-send-email-kevin@bracey.fi","threadId":"33450","inReplyTo":"7v4nfcj2kq.fsf@alter.siamese.dyndns.org","subject":"[RFC/PATCH] Make --full-history consider more merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-22T19:23:22Z","receivedAt":"2013-04-22T19:23:22Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"History simplification previously always treated merges as TREESAME\nif they were TREESAME to any parent.\n\nWhile the desired default behaviour, this could be extremely unhelpful\nwhen searching detailed history, and could not be overridden. For\nexample, if a merge had ignored a change, as if by \"-s ours\", then:\n\n git log -m -p --full-history -Schange file\n\nwould successfully locate \"change\"'s addition but would not locate the\nmerge that resolved against it.\n\nThis patch changes the simplification so that when --full-history is\nspecified, a merge is treated as TREESAME only if it is TREESAME to\n_all_ parents. This means the command above locates a merge that dropped\n\"change\".\n\nSigned-off-by: Kevin Bracey \n---\nThis would address my problem case - it passes existing tests, and covers\nmy (all-too-common) problem. But it would also need documentation changes and\na new test.\n\n revision.c | 10 ++++++++--\n 1 file changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex eb98128..96fe3f5 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -516,8 +516,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t}\n \t\tdie(\"bad tree compare for commit %s\", sha1_to_hex(commit->object.sha1));\n \t}\n-\tif (tree_changed && !tree_same)\n-\t\treturn;\n+\n+\tif (tree_changed) {\n+\t\tif (!tree_same)\n+\t\t\treturn;\n+\n+\t\tif (!revs->simplify_history && !revs->simplify_merges)\n+\t\t\treturn;\n+\t}\n \tcommit->object.flags |= TREESAME;\n }\n \n-- \n1.8.2.255.g39c5835\n"},{"id":"215112","messageId":"7vzjwqny64.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"1366658602-12254-1-git-send-email-kevin@bracey.fi","subject":"Re: [RFC/PATCH] Make --full-history consider more merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-22T19:49:23Z","receivedAt":"2013-04-22T19:49:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> diff --git a/revision.c b/revision.c\n> index eb98128..96fe3f5 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -516,8 +516,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n> \t\t}\n> \t\tdie(\"bad tree compare for commit %s\", sha1_to_hex(commit->object.sha1));\n> \t}\n> -\tif (tree_changed && !tree_same)\n> -\t\treturn;\n> +\n> +\tif (tree_changed) {\n> +\t\tif (!tree_same)\n> +\t\t\treturn;\n> +\n> +\t\tif (!revs->simplify_history && !revs->simplify_merges)\n> +\t\t\treturn;\n\nSo in addition to \"have some change and there is no same parent\"\ncase, under _some_ condition we avoid marking a merge not worth\nshowing (i.e. TREESAME) if there is any change.\n\nAnd the condition is !simplify_history and !simplify_merges, which\nwould cover --full-history, but I am not sure if requiring\n!simplify_merges is correct.\n\nDo you need it and if so why? The --simplify-merges option is\ndefined as a post-processing operation over what full-history\nproduces in the list limiting code (which involves the logic the\npatch is touching). The --ancestry-path option works the same way\nbut its post-processing is done inside the limit_list() function.\n\nSo it feels more natural if the patch were ignoring simplify_merges\nand paid attention only to simplify_history.\n\n> +\t}\n> \tcommit->object.flags |= TREESAME;\n> }\n"},{"id":"215250","messageId":"5176B854.2000707@bracey.fi","threadId":"33450","inReplyTo":"7vzjwqny64.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH] Make --full-history consider more merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-23T16:35:32Z","receivedAt":"2013-04-23T16:35:32Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 22/04/2013 22:49, Junio C Hamano wrote:\n>\n> So in addition to \"have some change and there is no same parent\"\n> case, under _some_ condition we avoid marking a merge not worth\n> showing (i.e. TREESAME) if there is any change.\n>\n> And the condition is !simplify_history and !simplify_merges, which\n> would cover --full-history, but I am not sure if requiring\n> !simplify_merges is correct.\n\nYou're right, it isn't correct. Logically, the test should be for\nsimplify_history. The original patch was overly cautious about\nlimiting it to --full-history. And it avoided breaking a test -\nspecifically t6016.7. simplify_merges() should just be post-\nprocessing \"full history with parents\" as you say, not changing its\nbehaviour.\n\nI've dug into this more, and am now fairly confident about my analysis.\nI believe the problem arises because TREESAME's definition was\nconflated with the default simplification behaviour, unnecessarily.\nMerges were defined as TREESAME if they matched ANY parent.\n\nThat's fine if simplify_history is set, but then in that case a merge\nwhich is TREESAME to any parent is turned into a normal commit based\non that parent anyway, and that simplified commit is inherently\nTREESAME, regardless of how we define TREESAME for merges.\n\nIf simplify_history isn't set, and we don't want ancestry, then that\nTREESAME definition is problematic. It avoids showing merges that\ndon't have anything actually new, but does lead to this issue that\n\"git log -Sxxx --full-history\" can't locate a dropped change.\n\nIf simplify_history is set, and we do want ancestry, then it doesn't\nmatter about the TREESAME definition because it shows all merges,\nregardless of the TREESAME flag. Thus adding \"--parents\" to the above\ncommand means it can find it, but only because it drags _every_ merge\ninto consideration. Should that be necessary?\n\nFuther, if we add simplify_merges, then TREESAME becomes a problem.\nAfter merge simplification, we can be left with a single-parent\ncommit that doesn't match its parent but is skipped due to its\nTREESAME flag being set: it was TREESAME to a parent that got dropped.\n\nI think the correction is that TREESAME for a commit needs to be\nredefined to be \"this commit matches all its (remaining) parents\",\nrather than \"this commit matches at least 1 of its (remaining)\nparents\". And when we eliminate parents, we have to check for the\nflag changing, but we should have been doing that anyway.\n\nNow, what effect does post-processing have on TREESAME? Parent\nrewriting due to elimination of duplicates, and making dense has no\neffect, as there we're always replacing a commit with something it\nwas TREESAME to, so that doesn't affect TREESAMEness of its children.\n\nBut reduce_heads() in simplify_merges() can have an effect. In the\nexample shown in the comment, X may or may not be TREESAME to its\nremaining single parent. And test 6016.7 covers one instance of\nthat - reduce_heads() eliminates branches B and C, because they\ndidn't touch bar.txt, and the rewritten parents were then ancestors\nof the A path. But that that \"drop ancestor paths\" logic totally\nignores TREESAMEness, and we don't know whether the merge kept\nthe bar.txt from A, or eliminated it by an \"-s ours\" take of B.\n\nIn the 6016.7 case, the merge was originally marked TREESAME, as it\nmatched A. When B and C were eliminated, it remained TREESAME, and\nthis wasn't recalculated. And that happened to be correct in this\ncase, because the merge was \"normal\".\n\nIf on the other hand, the merge had taken the \"old\" version B with\n\"-s ours\", or if there had been some other semantic change arising\nin the merge, then simplify_merges would still have eliminated\nB and C, and left a normal commit differing from parent A, but still\nmarked TREESAME from having matched B. So that would have wrongly\nhidden the merge. Recalculation is already necessary to spot the\n\"odd\" case.\n\nIf we redefine TREESAME, then recalculation becomes necessary to\nhandle the \"normal\" case - the merge will not initially be TREESAME,\nas it differs from B and C. But once B and C are eliminated, we\nshould then determine that the commit is TREESAME from matching\nits remaining parent A. Simplification should only ever \"increase\"\nthe sameness, so we can avoid recalculation if TREESAME is already\nset. Without this recalculation, 6016.7 fails.\n\nSo I believe that if reduce_heads() does eliminate any parents, and\nTREESAME wasn't set, then we have to recalculate TREESAME, by\nrunning over the remaining parents. A call to\ntry_to_simplify_commit() does the job, but it feels hacky, and\nobviously it's slow. It would be nice if we could remember\n\"per-parent TREESAME\" flags, and shuffle them when we change\nparents, but that could be fiddly.\n\nAlso if limit_to_ancestry() did eliminate parents from outside the\nancestry, as per the NEEDSWORK comment, then that would also want\nto do the TREESAME recalculation. (And it could conceivably be very\nuseful, helping pick up only the merges that went against your base\ncommit).\n\nSo, given all that, revised patch below:\n\n---\n revision.c | 15 ++++++++++++---\n 1 file changed, 12 insertions(+), 3 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex eb98128..15d2f3b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -432,7 +432,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n {\n struct commit_list **pp, *parent;\n- int tree_changed = 0, tree_same = 0, nth_parent = 0;\n+ int tree_changed = 0, nth_parent = 0;\n\n /*\n * If we don't do pruning, everything is interesting\n@@ -474,7 +474,6 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n sha1_to_hex(p->object.sha1));\n switch (rev_compare_tree(revs, p, commit)) {\n case REV_TREE_SAME:\n- tree_same = 1;\n if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {\n /* Even if a merge with an uninteresting\n * side branch brought the entire change\n@@ -516,7 +515,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n }\n die(\"bad tree compare for commit %s\", sha1_to_hex(commit->object.sha1));\n }\n- if (tree_changed && !tree_same)\n+ if (tree_changed)\n return;\n commit->object.flags |= TREESAME;\n }\n@@ -2042,9 +2041,19 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\n */\n if (1 < cnt) {\n struct commit_list *h = reduce_heads(commit->parents);\n+ int orig_cnt = commit_list_count(commit->parents);\n cnt = commit_list_count(h);\n free_commit_list(commit->parents);\n commit->parents = h;\n+ if (cnt < orig_cnt && !(commit->object.flags & TREESAME)) {\n+ /* Rewrite will likely change the TREESAME state. Eg in\n+ * example above, X could be TREESAME or not to its\n+ * remaining single parent, depending on how the merge\n+ * was resolved - most likely it is now TREESAME, but\n+ * it may not be.\n+ */\n+ try_to_simplify_commit(revs, commit);\n+ }\n }\n\n /*\n-- \n1.8.2.255.g39c5835\n"},{"id":"215394","messageId":"7va9ona77d.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"5176B854.2000707@bracey.fi","subject":"Re: [RFC/PATCH] Make --full-history consider more merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-24T22:34:46Z","receivedAt":"2013-04-24T22:34:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> If simplify_history is set, and we do want ancestry, then it doesn't\n> matter about the TREESAME definition because it shows all merges,\n> regardless of the TREESAME flag. Thus adding \"--parents\" to the above\n> command means it can find it, but only because it drags _every_ merge\n> into consideration. Should that be necessary?\n>\n> Futher, if we add simplify_merges, then TREESAME becomes a problem.\n> After merge simplification, we can be left with a single-parent\n> commit that doesn't match its parent but is skipped due to its\n> TREESAME flag being set: it was TREESAME to a parent that got dropped.\n>\n> I think the correction is that TREESAME for a commit needs to be\n> redefined to be \"this commit matches all its (remaining) parents\",\n> rather than \"this commit matches at least 1 of its (remaining)\n> parents\". And when we eliminate parents, we have to check for the\n> flag changing, but we should have been doing that anyway.\n\nThanks, I think this analysis is quite correct. Marking a commit\nwith TREESAME means the commit is not worth showing. If we are\nsimplifying side branches away, remaining parents may be reduced to\n1 and \"all its remaining parents\" would be the same as \"at least 1\nof its remaining parents\", but if we want to keep side branches that\nmatter in explaining the history, we do not want to paint the merge\nwith TREESAME unless it matches with all its remaining parents.\n\n> If we redefine TREESAME, then recalculation becomes necessary to\n> handle the \"normal\" case - the merge will not initially be TREESAME,\n> as it differs from B and C. But once B and C are eliminated, we\n> should then determine that the commit is TREESAME from matching\n> its remaining parent A. Simplification should only ever \"increase\"\n> the sameness, so we can avoid recalculation if TREESAME is already\n> set. Without this recalculation, 6016.7 fails.\n>\n> So I believe that if reduce_heads() does eliminate any parents, and\n> TREESAME wasn't set, then we have to recalculate TREESAME, by\n> running over the remaining parents. A call to\n> try_to_simplify_commit() does the job, but it feels hacky, and\n> obviously it's slow. It would be nice if we could remember\n> \"per-parent TREESAME\" flags, and shuffle them when we change\n> parents, but that could be fiddly.\n>\n> Also if limit_to_ancestry() did eliminate parents from outside the\n> ancestry, as per the NEEDSWORK comment, then that would also want\n> to do the TREESAME recalculation. (And it could conceivably be very\n> useful, helping pick up only the merges that went against your base\n> commit).\n\nYeah, I agree to that.\n\n>\n> So, given all that, revised patch below:\n>\n> ---\n\n\n> revision.c | 15 ++++++++++++---\n> 1 file changed, 12 insertions(+), 3 deletions(-)\n>\n> diff --git a/revision.c b/revision.c\n> index eb98128..15d2f3b 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -432,7 +432,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n> static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n> {\n> struct commit_list **pp, *parent;\n> - int tree_changed = 0, tree_same = 0, nth_parent = 0;\n> + int tree_changed = 0, nth_parent = 0;\n>\n> /*\n> * If we don't do pruning, everything is interesting\n> @@ -474,7 +474,6 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n> sha1_to_hex(p->object.sha1));\n> switch (rev_compare_tree(revs, p, commit)) {\n> case REV_TREE_SAME:\n> - tree_same = 1;\n> if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {\n> /* Even if a merge with an uninteresting\n> * side branch brought the entire change\n> @@ -516,7 +515,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n> }\n> die(\"bad tree compare for commit %s\", sha1_to_hex(commit->object.sha1));\n> }\n> - if (tree_changed && !tree_same)\n> + if (tree_changed)\n> return;\n> commit->object.flags |= TREESAME;\n> }\n> @@ -2042,9 +2041,19 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\n> */\n> if (1 < cnt) {\n> struct commit_list *h = reduce_heads(commit->parents);\n> + int orig_cnt = commit_list_count(commit->parents);\n> cnt = commit_list_count(h);\n> free_commit_list(commit->parents);\n> commit->parents = h;\n> + if (cnt < orig_cnt && !(commit->object.flags & TREESAME)) {\n> + /* Rewrite will likely change the TREESAME state. Eg in\n> + * example above, X could be TREESAME or not to its\n> + * remaining single parent, depending on how the merge\n> + * was resolved - most likely it is now TREESAME, but\n> + * it may not be.\n> + */\n> + try_to_simplify_commit(revs, commit);\n> + }\n> }\n>\n> /*\n"},{"id":"215400","messageId":"7v61zb8j5d.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"7va9ona77d.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH] Make --full-history consider more merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-25T01:59:42Z","receivedAt":"2013-04-25T01:59:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n>> So, given all that, revised patch below:\n\nI tried to squeeze the minimum test I sent $gmane/220919 to the test\nsuite. I think the \"do not use --parents option for this test\"\nswitch needs to be cleaned up a bit more, but it fails without your\npatch and does pass with your patch.\n\nI somehow was hoping that your fix to TREESAME semantics would also\ncorrect the known breakage documented in that test, but it seems\nthat I was too greedy ;-)\n\nThanks.\n\n t/t6012-rev-list-simplify.sh | 29 +++++++++++++++++++++++------\n 1 file changed, 23 insertions(+), 6 deletions(-)\n\ndiff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\nindex dd6dc84..4e55872 100755\n--- a/t/t6012-rev-list-simplify.sh\n+++ b/t/t6012-rev-list-simplify.sh\n@@ -14,21 +14,24 @@ unnote () {\n \n test_expect_success setup '\n \techo \"Hi there\" >file &&\n-\tgit add file &&\n-\ttest_tick && git commit -m \"Initial file\" &&\n+\techo \"initial\" >lost &&\n+\tgit add file lost &&\n+\ttest_tick && git commit -m \"Initial file and lost\" &&\n \tnote A &&\n \n \tgit branch other-branch &&\n \n \techo \"Hello\" >file &&\n-\tgit add file &&\n-\ttest_tick && git commit -m \"Modified file\" &&\n+\techo \"second\" >lost &&\n+\tgit add file lost &&\n+\ttest_tick && git commit -m \"Modified file and lost\" &&\n \tnote B &&\n \n \tgit checkout other-branch &&\n \n \techo \"Hello\" >file &&\n-\tgit add file &&\n+\t>lost &&\n+\tgit add file lost &&\n \ttest_tick && git commit -m \"Modified the file identically\" &&\n \tnote C &&\n \n@@ -37,7 +40,9 @@ test_expect_success setup '\n \ttest_tick && git commit -m \"Add another file\" &&\n \tnote D &&\n \n-\ttest_tick && git merge -m \"merge\" master &&\n+\ttest_tick &&\n+\ttest_must_fail git merge -m \"merge\" master &&\n+\t>lost && git commit -a -m \"merge\" &&\n \tnote E &&\n \n \techo \"Yet another\" >elif &&\n@@ -110,4 +115,16 @@ check_result 'I B A' -- file\n check_result 'I B A' --topo-order -- file\n check_result 'H' --first-parent -- another-file\n \n+check_result 'E C B A' --full-history E -- lost\n+test_expect_success 'full history simplification without parent' '\n+\tprintf \"%s\\n\" E C B A >expect &&\n+\tgit log --pretty=\"$FMT\" --full-history E -- lost |\n+\tunnote >actual &&\n+\tsed -e \"s/^.*\t\\([^ ]*\\) .*/\\1/\" >check Junio C Hamano writes:\n>\n>>> So, given all that, revised patch below:\n> I tried to squeeze the minimum test I sent $gmane/220919 to the test\n> suite. I think the \"do not use --parents option for this test\"\n> switch needs to be cleaned up a bit more, but it fails without your\n> patch and does pass with your patch.\n>\n> I somehow was hoping that your fix to TREESAME semantics would also\n> correct the known breakage documented in that test, but it seems\n> that I was too greedy ;-)\nThanks for the test addition. Maybe we will be able to satisfy your \ngreed in this series. There could be more worth doing here, and I think \ngetting TREESAME precise is key.\n\nI think I do want to take the step of storing \"treesame per parent\". And \nonce we do that, as well as avoiding the expensive re-diff, we have much \nricher information readily available as a simplification input (and output).\n\nI'm working on a patch that does this - filling in an initial treesame[] \narray as a decoration in try_to_simplify_commit() is easy, and \nmaintaining the array through later parent rewrites isn't as onerous as \nI feared - there are only a few places that rewrite parents after the \ninitial scan. With a couple of helper functions to do things like \n\"delete nth\", I think it'll be quite tidy.\n\nI believe that simplify_merges itself needs at least one addition, and \ncould use the treesame[] array to do it: if after doing reduce_heads, a \ncommit is now different to all remaining parents, but there was a \nTREESAME parent eliminated, that parent should be reinstated. That would \nclearly highlight missed merges, showing both that \"older\" TREESAME \nparent and the newer !TREESAME parent that would have been taken in a \nnormal merge.\n\nAnd maybe there's more simplify_merges could do, if it had this full \nTREESAME information available.\n\n(But even after you do all this stuff to get the right commits out, we \nthen hit a niggle of mine that gitk forces --cc diffs - even if it shows \nshows the offending merge commit, you can't get it to do a diff...)\n\nKevin\n"},{"id":"215454","messageId":"7vtxmu4kq2.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"5179505F.2000108@bracey.fi","subject":"Re: [RFC/PATCH] Make --full-history consider more merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-25T16:51:33Z","receivedAt":"2013-04-25T16:51:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> On 25/04/2013 04:59, Junio C Hamano wrote:\n>> Junio C Hamano writes:\n>>\n>>>> So, given all that, revised patch below:\n>> I tried to squeeze the minimum test I sent $gmane/220919 to the test\n>> suite. I think the \"do not use --parents option for this test\"\n>> switch needs to be cleaned up a bit more, but it fails without your\n>> patch and does pass with your patch.\n>>\n>> I somehow was hoping that your fix to TREESAME semantics would also\n>> correct the known breakage documented in that test, but it seems\n>> that I was too greedy ;-)\n> Thanks for the test addition. Maybe we will be able to satisfy your\n> greed in this series. There could be more worth doing here, and I\n> think getting TREESAME precise is key.\n\nIt is perfectly fine to do things one step at a time. Let's get\nthe --full-history change into a good shape first and worry about\nthe more complex case after we are done.\n"},{"id":"215460","messageId":"517963B4.30801@bracey.fi","threadId":"33450","inReplyTo":"7vtxmu4kq2.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH] Make --full-history consider more merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-25T17:11:16Z","receivedAt":"2013-04-25T17:11:16Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 25/04/2013 19:51, Junio C Hamano wrote:\n> Kevin Bracey writes:\n>\n>> Thanks for the test addition. Maybe we will be able to satisfy your\n>> greed in this series. There could be more worth doing here, and I\n>> think getting TREESAME precise is key.\n> It is perfectly fine to do things one step at a time. Let's get\n> the --full-history change into a good shape first and worry about\n> the more complex case after we are done.\n\nSo do you see the rerun of try_to_simplify_commit() as acceptable? I'm \nreally not happy with it - it was fine for an initial proof-of-concept, \nbut it's an obvious waste of CPU cycles to recompute something we \nalready figured out, and I'm uncomfortable with the fact that the \nfunction potentially does more than just compute TREESAME; by inspection \nit seems safe given the known context inside simplify_merges(), but it \nfeels like something waiting to trip us up. The latter could be dealt \nwith by breaking try_to_simplify_commit() up, but that feels like a \ndiversion. I'd rather just get on and make this first patch store and \nuse the per-parent-treesame flags if feasible.\n\nKevin\n"},{"id":"215464","messageId":"7v1u9y4gnq.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"517963B4.30801@bracey.fi","subject":"Re: [RFC/PATCH] Make --full-history consider more merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-25T18:19:21Z","receivedAt":"2013-04-25T18:19:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> On 25/04/2013 19:51, Junio C Hamano wrote:\n>> Kevin Bracey writes:\n>>\n>>> Thanks for the test addition. Maybe we will be able to satisfy your\n>>> greed in this series. There could be more worth doing here, and I\n>>> think getting TREESAME precise is key.\n>> It is perfectly fine to do things one step at a time. Let's get\n>> the --full-history change into a good shape first and worry about\n>> the more complex case after we are done.\n>\n> So do you see the rerun of try_to_simplify_commit() as acceptable? I'm\n> really not happy with it - it was fine for an initial\n> proof-of-concept, but it's an obvious waste of CPU cycles to recompute\n> something we already figured out, and I'm uncomfortable with the fact\n> that the function potentially does more than just compute TREESAME; by\n> inspection it seems safe given the known context inside\n> simplify_merges(), but it feels like something waiting to trip us\n> up.\n\nTrue.\n\n> The latter could be dealt with by breaking\n> try_to_simplify_commit() up, but that feels like a diversion. I'd\n> rather just get on and make this first patch store and use the\n> per-parent-treesame flags if feasible.\n\nOK. We have survived with this corner case glitch for more than 6\nyears, so a fix is not ultra-urgent. Let's try to see if we can get\nit right.\n\nHow many decorations are we talking about here? One for each merge\ncommit in the entire history? Do we have a cue that can tell us\nwhen we are really done with a commit that lets us discard the\nassociated data as we go on digging, keeping the size of our working\nset somewhat bounded, perhaps proportional to the number of commits\nin our rev_info->commits queue?\n"},{"id":"215619","messageId":"517AD304.6020807@bracey.fi","threadId":"33450","inReplyTo":"7v1u9y4gnq.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH] Make --full-history consider more merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-26T19:18:28Z","receivedAt":"2013-04-26T19:18:28Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 25/04/2013 21:19, Junio C Hamano wrote:\n> How many decorations are we talking about here? One for each merge \n> commit in the entire history? Do we have a cue that can tell us when \n> we are really done with a commit that lets us discard the associated \n> data as we go on digging, keeping the size of our working set somewhat \n> bounded, perhaps proportional to the number of commits in our \n> rev_info->commits queue? \n\nAs it stands, it's one decoration per interesting merge commit that's \nprocessed by try_to_simplify_commit(), if simplify_merges is set. (Only \nsimplify_merges needs the information at present - conceivably \nlimit_to_ancestry could use it too). I don't know how to go about \ndiscarding the data, or when it could be done - I'm not clear enough on \nthe wider sequencing machinery in revision.c yet.\n\nI have a first draft of a set of patches, which will follow this message.\n\n1/3 addresses the initial \"get simplify_merges right\", passing your \ntest. That patch is written to make it easy to extend with the next two, \nwhich add a \"never eliminate all our TREESAME parents\" rule, and \nreinstate your reverted\"eliminate irrelevant side branches\". The error I \nspotted in that was that you weren't checking that you were eliminating \nroot commits - with that fixed it seems sound to me.\n\nI need to create a new test for patch 2, but this version passes the \nfull test suite, including fixing the known failure in t6012, and it \nalso gets the examples in the manual right. (I've extended the examples \nto include the irrelevant side branch - not sure this is worthwhile, as \nit's such an unusual case, and I think that section is confusing enough \nfor newbies...)\n\nKevin\n"},{"id":"215621","messageId":"1367004718-30048-1-git-send-email-kevin@bracey.fi","threadId":"33450","inReplyTo":"517AD304.6020807@bracey.fi","subject":"[RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-26T19:31:56Z","receivedAt":"2013-04-26T19:31:56Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"Historically TREESAME was set on a commit if it was TREESAME to _any_ of\nits parents. This is not optimal, as such a merge could still be worth\nshowing, particularly if it is an odd \"-s ours\" merge that (possibly\naccidentally) dropped a change. And the problem is further compounded by\nthe fact that simplify_merges could drop the actual parent that a commit\nwas TREESAME to, leaving it as a normal commit marked TREESAME that\nisn't actually TREESAME to its remaining parent.\n\nThis commit redefines TREESAME to be true only if a commit is TREESAME to\n_all_ of its parents. This doesn't affect either the default\nsimplify_history behaviour (because partially TREESAME merges are turned\ninto normal commits), or full-history with parent rewriting (because all\nmerges are output). But it does affect other modes.\n\nIt also modifies simplify_merges to recalculate TREESAME after removing\na parent. This is achieved by storing per-parent TREESAME flags on the\ninitial scan, so the combined flag can be easily recomputed.\n\nSigned-off-by: Kevin Bracey \n---\n Documentation/rev-list-options.txt | 2 +-\n revision.c | 220 ++++++++++++++++++++++++++++++++-----\n revision.h | 1 +\n 3 files changed, 192 insertions(+), 31 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 3bdbf5e..380db48 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -413,7 +413,7 @@ parent lines.\n \tI A B N D O\n -----------------------------------------------------------------------\n +\n-`P` and `M` were excluded because they are TREESAME to a parent. `E`,\n+`P` and `M` were excluded because they are TREESAME to both parents. `E`,\n `C` and `B` were all walked, but only `B` was !TREESAME, so the others\n do not appear.\n +\ndiff --git a/revision.c b/revision.c\nindex a67b615..176eb7b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -429,10 +429,85 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n \treturn retval >= 0 && (tree_difference == REV_TREE_SAME);\n }\n \n+struct treesame_state {\n+\tunsigned int nparents;\n+\tunsigned char treesame[FLEX_ARRAY];\n+};\n+\n+static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit)\n+{\n+\tunsigned n = commit_list_count(commit->parents);\n+\tstruct treesame_state *st = xcalloc(1, sizeof(*st) + n);\n+\tst->nparents = n;\n+\tadd_decoration(&revs->treesame, &commit->object, st);\n+\treturn st;\n+}\n+\n+static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned parent)\n+{\n+\tstruct treesame_state *st = lookup_decoration(&revs->treesame, &commit->object);\n+\tint old_same;\n+\n+\tif (!st || parent >= st->nparents)\n+\t\tdie(\"compact_treesame %u\", parent);\n+\n+\t/* Can be useful to indicate sameness of removed parent */\n+\told_same = st->treesame[parent];\n+\n+\tmemmove(st->treesame + parent,\n+\t\tst->treesame + parent + 1,\n+\t\tst->nparents - parent - 1);\n+\n+\t/* If we've just become a non-merge commit, update TREESAME\n+\t * immediately, in case we trigger an early-exit optimisation.\n+\t * (Note that there may be a mismatch between commit->parents and the\n+\t * treesame_state at this stage, as we may be in mid-rewrite).\n+\t * If still a merge, defer update until update_treesame().\n+\t */\n+\tswitch (--st->nparents) {\n+\tcase 0:\n+\t\tif (rev_same_tree_as_empty(revs, commit))\n+\t\t\tcommit->object.flags |= TREESAME;\n+\t\telse\n+\t\t\tcommit->object.flags &= ~TREESAME;\n+\t\tbreak;\n+\tcase 1:\n+\t\tif (st->treesame[0] && revs->dense)\n+\t\t\tcommit->object.flags |= TREESAME;\n+\t\telse\n+\t\t\tcommit->object.flags &= ~TREESAME;\n+\t\tbreak;\n+\t}\n+\n+\treturn old_same;\n+}\n+\n+static unsigned update_treesame(struct rev_info *revs, struct commit *commit)\n+{\n+\t/* If 0 or 1 parents, TREESAME should be valid already */\n+\tif (commit->parents && commit->parents->next) {\n+\t\tint n = 0;\n+\t\tstruct treesame_state *st;\n+\n+\t\tst = lookup_decoration(&revs->treesame, &commit->object);\n+\t\tif (!st) die(\"update_treesame\");\n+\t\tcommit->object.flags |= TREESAME;\n+\t\tfor (n = 0; n < st->nparents; n++) {\n+\t\t\tif (!st->treesame[n]) {\n+\t\t\t\tcommit->object.flags &= ~TREESAME;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\treturn commit->object.flags & TREESAME;\n+}\n+\n static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list **pp, *parent;\n-\tint tree_changed = 0, tree_same = 0, nth_parent = 0;\n+\tstruct treesame_state *ts = NULL;\n+\tint tree_changed = 0, nth_parent = 0;\n \n \t/*\n \t * If we don't do pruning, everything is interesting\n@@ -456,25 +531,38 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tif (!revs->dense && !commit->parents->next)\n \t\treturn;\n \n-\tpp = &commit->parents;\n-\twhile ((parent = *pp) != NULL) {\n+\tfor (pp = &commit->parents;\n+\t (parent = *pp) != NULL;\n+\t pp = &parent->next, nth_parent++) {\n \t\tstruct commit *p = parent->item;\n \n-\t\t/*\n-\t\t * Do not compare with later parents when we care only about\n-\t\t * the first parent chain, in order to avoid derailing the\n-\t\t * traversal to follow a side branch that brought everything\n-\t\t * in the path we are limited to by the pathspec.\n-\t\t */\n-\t\tif (revs->first_parent_only && nth_parent++)\n-\t\t\tbreak;\n+\t\tif (nth_parent == 1) {\n+\t\t\t/*\n+\t\t\t * Do not compare with later parents when we care only about\n+\t\t\t * the first parent chain, in order to avoid derailing the\n+\t\t\t * traversal to follow a side branch that brought everything\n+\t\t\t * in the path we are limited to by the pathspec.\n+\t\t\t */\n+\t\t\tif (revs->first_parent_only)\n+\t\t\t\tbreak;\n+\t\t\t/*\n+\t\t\t * If this is going to remain a merge, and it's\n+\t\t\t * interesting, remember per-parent treesame for\n+\t\t\t * simplify_merges().\n+\t\t\t */\n+\t\t\tif (revs->simplify_merges && !(p->object.flags & UNINTERESTING)) {\n+\t\t\t\tts = initialise_treesame(revs, commit);\n+\t\t\t\tif (!tree_changed)\n+\t\t\t\t\tts->treesame[0] = 1;\n+\n+\t\t\t}\n+\t\t}\n \t\tif (parse_commit(p) < 0)\n \t\t\tdie(\"cannot simplify commit %s (because of %s)\",\n \t\t\t sha1_to_hex(commit->object.sha1),\n \t\t\t sha1_to_hex(p->object.sha1));\n \t\tswitch (rev_compare_tree(revs, p, commit)) {\n \t\tcase REV_TREE_SAME:\n-\t\t\ttree_same = 1;\n \t\t\tif (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {\n \t\t\t\t/* Even if a merge with an uninteresting\n \t\t\t\t * side branch brought the entire change\n@@ -482,7 +570,8 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t\t\t * to lose the other branches of this\n \t\t\t\t * merge, so we just keep going.\n \t\t\t\t */\n-\t\t\t\tpp = &parent->next;\n+\t\t\t\tif (ts)\n+\t\t\t\t\tts->treesame[nth_parent] = 1;\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tparent->next = NULL;\n@@ -511,12 +600,11 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\tcase REV_TREE_OLD:\n \t\tcase REV_TREE_DIFFERENT:\n \t\t\ttree_changed = 1;\n-\t\t\tpp = &parent->next;\n \t\t\tcontinue;\n \t\t}\n \t\tdie(\"bad tree compare for commit %s\", sha1_to_hex(commit->object.sha1));\n \t}\n-\tif (tree_changed && !tree_same)\n+\tif (tree_changed)\n \t\treturn;\n \tcommit->object.flags |= TREESAME;\n }\n@@ -773,6 +861,9 @@ static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *li\n \t * NEEDSWORK: decide if we want to remove parents that are\n \t * not marked with TMP_MARK from commit->parents for commits\n \t * in the resulting list. We may not want to do that, though.\n+\t *\n+\t * Maybe it should be considered if we are TREESAME to such\n+\t * parents - now possible with stored per-parent flags.\n \t */\n \n \t/*\n@@ -1930,28 +2021,32 @@ static void add_child(struct rev_info *revs, struct commit *parent, struct commi\n \tl->next = add_decoration(&revs->children, &parent->object, l);\n }\n \n-static int remove_duplicate_parents(struct commit *commit)\n+static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit)\n {\n+\tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n \tstruct commit_list **pp, *p;\n \tint surviving_parents;\n \n \t/* Examine existing parents while marking ones we have seen... */\n \tpp = &commit->parents;\n+\tsurviving_parents = 0;\n \twhile ((p = *pp) != NULL) {\n \t\tstruct commit *parent = p->item;\n \t\tif (parent->object.flags & TMP_MARK) {\n \t\t\t*pp = p->next;\n+\t\t\tif (ts)\n+\t\t\t\tcompact_treesame(revs, commit, surviving_parents);\n \t\t\tcontinue;\n \t\t}\n \t\tparent->object.flags |= TMP_MARK;\n+\t\tsurviving_parents++;\n \t\tpp = &p->next;\n \t}\n-\t/* count them while clearing the temporary mark */\n-\tsurviving_parents = 0;\n+\t/* clear the temporary mark */\n \tfor (p = commit->parents; p; p = p->next) {\n \t\tp->item->object.flags &= ~TMP_MARK;\n-\t\tsurviving_parents++;\n \t}\n+\t/* no update_treesame() - removing duplicates can't affect TREESAME */\n \treturn surviving_parents;\n }\n \n@@ -1971,6 +2066,70 @@ static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs,\n \treturn st;\n }\n \n+static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)\n+{\n+\tstruct commit_list *h = reduce_heads(commit->parents);\n+\tint i = 0, marked = 0;\n+\tstruct commit_list *po, *pn;\n+\n+\t/* Want these for sanity only */\n+\tint orig_cnt = commit_list_count(commit->parents);\n+\tint cnt = commit_list_count(h);\n+\n+\t/* Not ready to remove items yet, just mark them for now, based\n+\t * on the output of reduce_heads(). reduce_heads outputs the reduced\n+\t * set in its original order, so this isn't too hard.\n+\t */\n+\tpo = commit->parents;\n+\tpn = h;\n+\twhile (po) {\n+\t\tif (pn && po->item == pn->item) {\n+\t\t\tpn=pn->next;\n+\t\t\ti++;\n+\t\t}\n+\t\telse {\n+\t\t\tpo->item->object.flags |= TMP_MARK;\n+\t\t\tmarked++;\n+\t\t}\n+\t\tpo=po->next;\n+\t}\n+\n+\tif (i != cnt || cnt+marked != orig_cnt)\n+\t\tdie(\"mark_redundant_parents %d %d %d %d\", orig_cnt, cnt, i, marked);\n+\n+\tfree_commit_list(h);\n+\n+\treturn marked;\n+}\n+\n+static int remove_marked_parents(struct rev_info *revs, struct commit *commit)\n+{\n+\tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n+\tstruct commit_list **pp, *p;\n+\tint n, removed = 0;\n+\n+\tpp = &commit->parents;\n+\tn = 0;\n+\twhile ((p = *pp) != NULL) {\n+\t\tstruct commit *parent = p->item;\n+\t\tif (parent->object.flags & TMP_MARK) {\n+\t\t\tparent->object.flags &= ~TMP_MARK;\n+\t\t\tcompact_treesame(revs, commit, n);\n+\t\t\t*pp = p->next;\n+\t\t\tfree(p);\n+\t\t\tremoved++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tpp = &p->next;\n+\t\tn++;\n+\t}\n+\n+\tif (removed)\n+\t\tupdate_treesame(revs, commit);\n+\n+\treturn removed;\n+}\n+\n static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)\n {\n \tstruct commit_list *p;\n@@ -2015,7 +2174,9 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\n \t}\n \n \t/*\n-\t * Rewrite our list of parents.\n+\t * Rewrite our list of parents. Note that this cannot\n+\t * affect our TREESAME flags in anyway - a commit is\n+\t * always TREESAME to its simplification.\n \t */\n \tfor (p = commit->parents; p; p = p->next) {\n \t\tpst = locate_simplify_state(revs, p->item);\n@@ -2027,31 +2188,30 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\n \tif (revs->first_parent_only)\n \t\tcnt = 1;\n \telse\n-\t\tcnt = remove_duplicate_parents(commit);\n+\t\tcnt = remove_duplicate_parents(revs, commit);\n \n \t/*\n \t * It is possible that we are a merge and one side branch\n \t * does not have any commit that touches the given paths;\n-\t * in such a case, the immediate parents will be rewritten\n-\t * to different commits.\n+\t * in such a case, the immediate parent from that branch\n+\t * will be rewritten to be the merge base.\n \t *\n \t * o----X\t\tX: the commit we are looking at;\n \t * / /\t\to: a commit that touches the paths;\n \t * ---o----'\n \t *\n-\t * Further reduce the parents by removing redundant parents.\n+\t * Detect and simplify this case.\n \t */\n \tif (1 < cnt) {\n-\t\tstruct commit_list *h = reduce_heads(commit->parents);\n-\t\tcnt = commit_list_count(h);\n-\t\tfree_commit_list(commit->parents);\n-\t\tcommit->parents = h;\n+\t\tint marked = mark_redundant_parents(revs, commit);\n+\t\tif (marked)\n+\t\t\tremove_marked_parents(revs, commit);\n \t}\n \n \t/*\n \t * A commit simplifies to itself if it is a root, if it is\n \t * UNINTERESTING, if it touches the given paths, or if it is a\n-\t * merge and its parents simplifies to more than one commits\n+\t * merge and its parents simplify to more than one commit\n \t * (the first two cases are already handled at the beginning of\n \t * this function).\n \t *\n@@ -2218,7 +2378,7 @@ static int rewrite_parents(struct rev_info *revs, struct commit *commit)\n \t\t}\n \t\tpp = &parent->next;\n \t}\n-\tremove_duplicate_parents(commit);\n+\tremove_duplicate_parents(revs, commit);\n \treturn 0;\n }\n \ndiff --git a/revision.h b/revision.h\nindex 01bd2b7..1abe57b 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -167,6 +167,7 @@ struct rev_info {\n \tstruct reflog_walk_info *reflog_info;\n \tstruct decoration children;\n \tstruct decoration merge_simplification;\n+\tstruct decoration treesame;\n \n \t/* notes-specific options: which refs to show */\n \tstruct display_notes_opt notes_opt;\n-- \n1.8.2.1.632.gd2b1879\n"},{"id":"215624","messageId":"1367004718-30048-2-git-send-email-kevin@bracey.fi","threadId":"33450","inReplyTo":"1367004718-30048-1-git-send-email-kevin@bracey.fi","subject":"[RFC/PATCH 2/3] simplify-merges: never remove all TREESAME parents","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-26T19:31:57Z","receivedAt":"2013-04-26T19:31:57Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"In the event of an odd merge, we may find ourselves TREESAME to\napparently redundant parents. Prevent simplify_merges() from removing\nevery TREESAME parent - in the event of such a merge it's useful to see\nwhere we came actually from came.\n\nSigned-off-by: Kevin Bracey \n---\n Documentation/rev-list-options.txt | 3 ++-\n revision.c | 24 ++++++++++++++++++++++++\n 2 files changed, 26 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 380db48..0832004 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -472,7 +472,8 @@ history according to the following rules:\n +\n * Replace each parent `P` of `C'` with its simplification `P'`. In\n the process, drop parents that are ancestors of other parents, and\n- remove duplicates.\n+ remove duplicates, but take care to never drop all parents that\n+ we are TREESAME to.\n +\n * If after this parent rewriting, `C'` is a root or merge commit (has\n zero or >1 parents), a boundary commit, or !TREESAME, it remains.\ndiff --git a/revision.c b/revision.c\nindex 176eb7b..4e27c9a 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2106,8 +2106,32 @@ static int remove_marked_parents(struct rev_info *revs, struct commit *commit)\n {\n \tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n \tstruct commit_list **pp, *p;\n+\tstruct commit *su = NULL, *sm = NULL;\n \tint n, removed = 0;\n \n+\t/* Prescan - look for both marked and unmarked TREESAME parents */\n+\tfor (p = commit->parents, n = 0; p; p = p->next, n++) {\n+\t\tif (ts->treesame[n]) {\n+\t\t\tif (p->item->object.flags & TMP_MARK) {\n+\t\t\t\tif (!sm) sm = p->item;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tif (!su) {\n+\t\t\t\t\tsu = p->item;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/* If we are TREESAME to a marked-for-deletion parent, but not to any\n+\t * unmarked parents, unmark the first TREESAME parent. We don't want\n+\t * to remove our \"real\" parent in the event of an \"-s ours\" type\n+\t * merge.\n+\t */\n+\tif (!su && sm)\n+\t\tsm->object.flags &= ~TMP_MARK;\n+\n \tpp = &commit->parents;\n \tn = 0;\n \twhile ((p = *pp) != NULL) {\n-- \n1.8.2.1.632.gd2b1879\n"},{"id":"215626","messageId":"1367004718-30048-3-git-send-email-kevin@bracey.fi","threadId":"33450","inReplyTo":"1367004718-30048-1-git-send-email-kevin@bracey.fi","subject":"[RFC/PATCH 3/3] simplify-merges: drop merge from irrelevant side branch","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-26T19:31:58Z","receivedAt":"2013-04-26T19:31:58Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"Reimplement commit 4b7f53da on top of the new simplify-merges\ninfrastructure, tightening the condition to only consider root parents;\nthe original version incorrectly dropped parents that were TREESAME to\nanything.\n\nOriginal log message follows.\n\nThe merge simplification rule stated in 6546b59 (revision traversal:\nshow full history with merge simplification, 2008-07-31) still\ntreated merge commits too specially. Namely, in a history with this\nshape:\n\n\t---o---o---M\n\t /\n x---x---x\n\nwhere three 'x' were on a history completely unrelated to the main\nhistory 'o' and do not touch any of the paths we are following, we\nstill said that after simplifying all of the parents of M, 'x'\n(which is the leftmost 'x' that rightmost 'x simplifies down to) and\n'o' (which would be the last commit on the main history that touches\nthe paths we are following) are independent from each other, and\nboth need to be kept.\n\nThat is incorrect; when the side branch 'x' never touches the paths,\nit should be removed to allow M to simplify down to the last commit\non the main history that touches the paths.\n\nSuggested-by: Junio C Hamano \nSigned-off-by: Kevin Bracey \n---\n Documentation/rev-list-options.txt | 35 ++++++++++++++++++++++-------------\n revision.c | 26 +++++++++++++++++++++++++-\n t/t6012-rev-list-simplify.sh | 2 +-\n 3 files changed, 48 insertions(+), 15 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 0832004..db45401 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -342,13 +342,13 @@ In the following, we will always refer to the same example history to\n illustrate the differences between simplification settings. We assume\n that you are filtering for a file `foo` in this commit graph:\n -----------------------------------------------------------------------\n-\t .-A---M---N---O---P\n-\t / / / / /\n-\tI B C D E\n-\t \\ / / / /\n-\t `-------------'\n+\t .-A---M---N---O---P---Q\n+\t / / / / / /\n+\tI B C D E Y\n+\t \\ / / / / /\n+\t `-------------' X\n -----------------------------------------------------------------------\n-The horizontal line of history A---P is taken to be the first parent of\n+The horizontal line of history A---Q is taken to be the first parent of\n each merge. The commits are:\n \n * `I` is the initial commit, in which `foo` exists with contents\n@@ -370,6 +370,10 @@ each merge. The commits are:\n strings to \"quux xyzzy\". Despite appearing interesting, `P` is\n TREESAME to all parents.\n \n+* `X` is an indpendent root commit that added a new file `side`, and `Y`\n+ modified it. `Y` is TREESAME to `X`. Its merge `Q` added `side` to `P`, and\n+ `Q` is TREESAME to all parents.\n+\n 'rev-list' walks backwards through history, including or excluding\n commits based on whether '\\--full-history' and/or parent rewriting\n (via '\\--parents' or '\\--children') are used. The following settings\n@@ -413,7 +417,7 @@ parent lines.\n \tI A B N D O\n -----------------------------------------------------------------------\n +\n-`P` and `M` were excluded because they are TREESAME to both parents. `E`,\n+`Q`, `P` and `M` were excluded because they are TREESAME to both parents. `E`,\n `C` and `B` were all walked, but only `B` was !TREESAME, so the others\n do not appear.\n +\n@@ -431,7 +435,7 @@ Along each parent, prune away commits that are not included\n themselves. This results in\n +\n -----------------------------------------------------------------------\n-\t .-A---M---N---O---P\n+\t .-A---M---N---O---P---Q\n \t / / / / /\n \tI B / D /\n \t \\ / / / /\n@@ -441,7 +445,8 @@ themselves. This results in\n Compare to '\\--full-history' without rewriting above. Note that `E`\n was pruned away because it is TREESAME, but the parent list of P was\n rewritten to contain `E`'s parent `I`. The same happened for `C` and\n-`N`. Note also that `P` was included despite being TREESAME.\n+`N`, and `X`, `Y` and `Q`. Note also that `P` and `Q` were included despite\n+being TREESAME.\n \n In addition to the above settings, you can change whether TREESAME\n affects inclusion:\n@@ -471,9 +476,9 @@ history according to the following rules:\n * Set `C'` to `C`.\n +\n * Replace each parent `P` of `C'` with its simplification `P'`. In\n- the process, drop parents that are ancestors of other parents, and\n- remove duplicates, but take care to never drop all parents that\n- we are TREESAME to.\n+ the process, drop parents that are ancestors of other parents or that are\n+ root commits TREESAME to an empty tree, and remove duplicates, but take care\n+ to never drop all parents that we are TREESAME to.\n +\n * If after this parent rewriting, `C'` is a root or merge commit (has\n zero or >1 parents), a boundary commit, or !TREESAME, it remains.\n@@ -491,7 +496,7 @@ The effect of this is best shown by way of comparing to\n \t `---------'\n -----------------------------------------------------------------------\n +\n-Note the major differences in `N` and `P` over '--full-history':\n+Note the major differences in `N`, `P` and `Q` over '--full-history':\n +\n --\n * `N`'s parent list had `I` removed, because it is an ancestor of the\n@@ -499,6 +504,10 @@ Note the major differences in `N` and `P` over '--full-history':\n +\n * `P`'s parent list similarly had `I` removed. `P` was then\n removed completely, because it had one parent and is TREESAME.\n++\n+* `Q`'s parent list had `Y` simplified to `X`. `X` was then removed, because it\n+ was a TREESAME root. `Q` was then removed completely, because it had one\n+ parent and is TREESAME.\n --\n \n Finally, there is a fifth simplification mode available:\ndiff --git a/revision.c b/revision.c\nindex 4e27c9a..67608e0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2102,6 +2102,22 @@ static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)\n \treturn marked;\n }\n \n+static int mark_treesame_root_parents(struct rev_info *revs, struct commit *commit)\n+{\n+\tstruct commit_list *p;\n+\tint marked = 0;\n+\n+\tfor (p = commit->parents; p; p = p->next) {\n+\t\tstruct commit *parent = p->item;\n+\t\tif (!parent->parents && (parent->object.flags & TREESAME)) {\n+\t\t\tparent->object.flags |= TMP_MARK;\n+\t\t\tmarked++;\n+\t\t}\n+\t}\n+\n+\treturn marked;\n+}\n+\n static int remove_marked_parents(struct rev_info *revs, struct commit *commit)\n {\n \tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n@@ -2224,10 +2240,18 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\n \t * / /\t\to: a commit that touches the paths;\n \t * ---o----'\n \t *\n-\t * Detect and simplify this case.\n+\t * Further, a merge of an independent branch that doesn't\n+\t * touch the path will reduce to a treesame root parent:\n+\t *\n+\t * ----o----X\t\tX: the commit we are looking at;\n+\t * /\t\to: a commit that touches the paths;\n+\t * r\t\tr: a root commit not touching the paths\n+\t *\n+\t * Detect and simplify both cases.\n \t */\n \tif (1 < cnt) {\n \t\tint marked = mark_redundant_parents(revs, commit);\n+\t\tmarked += mark_treesame_root_parents(revs, commit);\n \t\tif (marked)\n \t\t\tremove_marked_parents(revs, commit);\n \t}\ndiff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\nindex 4e55872..57ce239 100755\n--- a/t/t6012-rev-list-simplify.sh\n+++ b/t/t6012-rev-list-simplify.sh\n@@ -110,7 +110,7 @@ check_result 'L K J I H G F E D C B A' --full-history\n check_result 'K I H E C B A' --full-history -- file\n check_result 'K I H E C B A' --full-history --topo-order -- file\n check_result 'K I H E C B A' --full-history --date-order -- file\n-check_outcome failure 'I E C B A' --simplify-merges -- file\n+check_result 'I E C B A' --simplify-merges -- file\n check_result 'I B A' -- file\n check_result 'I B A' --topo-order -- file\n check_result 'H' --first-parent -- another-file\n-- \n1.8.2.1.632.gd2b1879\n"},{"id":"215768","messageId":"7vppxfsirl.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"1367004718-30048-1-git-send-email-kevin@bracey.fi","subject":"Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-27T22:36:46Z","receivedAt":"2013-04-27T22:36:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> Historically TREESAME was set on a commit if it was TREESAME to _any_ of\n> its parents. This is not optimal, as such a merge could still be worth\n> showing, particularly if it is an odd \"-s ours\" merge that (possibly\n> accidentally) dropped a change.\n\n\"... and with options like --full-history or --simplify-merges are\nused to get more complete history\", I think. \"git log path\" without\nthese options is a tool to get one version of simplified history\nthat explains the end result, and by definition, the side branch\nmerged by \"-s ours\" did _not_ contribute anything to the end result.\n\n> And the problem is further compounded by\n> the fact that simplify_merges could drop the actual parent that a commit\n> was TREESAME to, leaving it as a normal commit marked TREESAME that\n> isn't actually TREESAME to its remaining parent.\n>\n> This commit redefines TREESAME to be true only if a commit is TREESAME to\n> _all_ of its parents. This doesn't affect either the default\n> simplify_history behaviour (because partially TREESAME merges are turned\n> into normal commits), or full-history with parent rewriting (because all\n> merges are output). But it does affect other modes.\n\nYes.\n\n> It also modifies simplify_merges to recalculate TREESAME after removing\n> a parent. This is achieved by storing per-parent TREESAME flags on the\n> initial scan, so the combined flag can be easily recomputed.\n\nThis is a very deep core part of the system, so let me summon/cc\nLinus for an extra set of eyes.\n\n> Signed-off-by: Kevin Bracey \n> ---\n> Documentation/rev-list-options.txt | 2 +-\n> revision.c | 220 ++++++++++++++++++++++++++++++++-----\n> revision.h | 1 +\n> 3 files changed, 192 insertions(+), 31 deletions(-)\n>\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index 3bdbf5e..380db48 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -413,7 +413,7 @@ parent lines.\n> \tI A B N D O\n> -----------------------------------------------------------------------\n> +\n> -`P` and `M` were excluded because they are TREESAME to a parent. `E`,\n> +`P` and `M` were excluded because they are TREESAME to both parents. `E`,\n> `C` and `B` were all walked, but only `B` was !TREESAME, so the others\n> do not appear.\n> +\n> diff --git a/revision.c b/revision.c\n> index a67b615..176eb7b 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -429,10 +429,85 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n> \treturn retval >= 0 && (tree_difference == REV_TREE_SAME);\n> }\n> \n> +struct treesame_state {\n> +\tunsigned int nparents;\n> +\tunsigned char treesame[FLEX_ARRAY];\n> +};\n> +\n> +static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit)\n> +{\n> +\tunsigned n = commit_list_count(commit->parents);\n> +\tstruct treesame_state *st = xcalloc(1, sizeof(*st) + n);\n> +\tst->nparents = n;\n> +\tadd_decoration(&revs->treesame, &commit->object, st);\n> +\treturn st;\n> +}\n> +\n> +static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned parent)\n> +{\n> +\tstruct treesame_state *st = lookup_decoration(&revs->treesame, &commit->object);\n> +\tint old_same;\n> +\n> +\tif (!st || parent >= st->nparents)\n> +\t\tdie(\"compact_treesame %u\", parent);\n> +\n> +\t/* Can be useful to indicate sameness of removed parent */\n> +\told_same = st->treesame[parent];\n\n(mental note) \"Can\" may refer to the fact that this value is not yet\nused in this series; my gut feeling is that returning old value is a\ngood API design even if there is no current user.\n\n> +\tmemmove(st->treesame + parent,\n> +\t\tst->treesame + parent + 1,\n> +\t\tst->nparents - parent - 1);\n> +\n> +\t/* If we've just become a non-merge commit, update TREESAME\n\n(style) \"/*\" occupies its own line.\n\n> +\t * immediately, in case we trigger an early-exit optimisation.\n> +\t * (Note that there may be a mismatch between commit->parents and the\n> +\t * treesame_state at this stage, as we may be in mid-rewrite).\n> +\t * If still a merge, defer update until update_treesame().\n> +\t */\n> +\tswitch (--st->nparents) {\n> +\tcase 0:\n> +\t\tif (rev_same_tree_as_empty(revs, commit))\n> +\t\t\tcommit->object.flags |= TREESAME;\n> +\t\telse\n> +\t\t\tcommit->object.flags &= ~TREESAME;\n> +\t\tbreak;\n> +\tcase 1:\n> +\t\tif (st->treesame[0] && revs->dense)\n> +\t\t\tcommit->object.flags |= TREESAME;\n> +\t\telse\n> +\t\t\tcommit->object.flags &= ~TREESAME;\n> +\t\tbreak;\n> +\t}\n\nDo we want to discard the decoration data when the commit becomes a\nnon-merge?\n\n> +\treturn old_same;\n> +}\n\n(mental note) compact_treesame() is not to \"compact\" after\neverything is done, but as we remove one parent we call it to remove\nthe treesame[] record for that parent. A commit can only lose parents\nand never gain a new one, so we will never have to reallocate flex\narray part.\n\n> +static unsigned update_treesame(struct rev_info *revs, struct commit *commit)\n> +{\n> +\t/* If 0 or 1 parents, TREESAME should be valid already */\n> +\tif (commit->parents && commit->parents->next) {\n> +\t\tint n = 0;\n\n\"compact\" counted parents from 0 upwards with \"unsigned\", here it is\n\"int\". It wouldn't make practical difference (nobody will create a\nmerge of 2 billion side branches), but we may want to be consistent.\n\n> +\t\tstruct treesame_state *st;\n> +\n> +\t\tst = lookup_decoration(&revs->treesame, &commit->object);\n> +\t\tif (!st) die(\"update_treesame\");\n\n(style) put this on two lines.\n\n> +\t\tcommit->object.flags |= TREESAME;\n> +\t\tfor (n = 0; n < st->nparents; n++) {\n> +\t\t\tif (!st->treesame[n]) {\n> +\t\t\t\tcommit->object.flags &= ~TREESAME;\n> +\t\t\t\tbreak;\n> +\t\t\t}\n> +\t\t}\n\nCan a commit that earlier was marked as TREESAME become not TREESAME?\nWouldn't simplification only increase sameness, never decrease?\n\n> +\t}\n> +\n> +\treturn commit->object.flags & TREESAME;\n> +}\n> +\n> static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n> {\n> \tstruct commit_list **pp, *parent;\n> -\tint tree_changed = 0, tree_same = 0, nth_parent = 0;\n> +\tstruct treesame_state *ts = NULL;\n> +\tint tree_changed = 0, nth_parent = 0;\n> \n> \t/*\n> \t * If we don't do pruning, everything is interesting\n> @@ -456,25 +531,38 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n> \tif (!revs->dense && !commit->parents->next)\n> \t\treturn;\n> \n> -\tpp = &commit->parents;\n> -\twhile ((parent = *pp) != NULL) {\n> +\tfor (pp = &commit->parents;\n> +\t (parent = *pp) != NULL;\n> +\t pp = &parent->next, nth_parent++) {\n\nI see the reason to change from while to for is because you wanted\nto count, and I think it makes sense; but it is more readable to\ninitialise the counter here, too, if that is the case. I.e.\n\n\tfor (pp = &commit->parents, nth_parent = 0;\n\t !(parent = *pp);\n\t pp = &parent->next, nth_parent++) {\n\n> \t\tstruct commit *p = parent->item;\n> \n> +\t\tif (nth_parent == 1) {\n> +\t\t\t/*\n> +\t\t\t * Do not compare with later parents when we care only about\n> +\t\t\t * the first parent chain, in order to avoid derailing the\n> +\t\t\t * traversal to follow a side branch that brought everything\n> +\t\t\t * in the path we are limited to by the pathspec.\n> +\t\t\t */\n> +\t\t\tif (revs->first_parent_only)\n> +\t\t\t\tbreak;\n> +\t\t\t/*\n> +\t\t\t * If this is going to remain a merge, and it's\n> +\t\t\t * interesting, remember per-parent treesame for\n> +\t\t\t * simplify_merges().\n> +\t\t\t */\n> +\t\t\tif (revs->simplify_merges && !(p->object.flags & UNINTERESTING)) {\n> +\t\t\t\tts = initialise_treesame(revs, commit);\n> +\t\t\t\tif (!tree_changed)\n> +\t\t\t\t\tts->treesame[0] = 1;\n\nHave we made any two tree comparison at this point to set this one?\nAhh, this is tricky. You do this in the _second_ iteration of the\nloop, so tree_changed here is from inspecting the first parent, not\nthe one we are looking at (i.e. *p).\n\n> +\n\n(style) unnecessary new blank line?\n\n> +\t\t\t}\n> +\t\t}\n> \t\tif (parse_commit(p) < 0)\n> \t\t\tdie(\"cannot simplify commit %s (because of %s)\",\n> \t\t\t sha1_to_hex(commit->object.sha1),\n> \t\t\t sha1_to_hex(p->object.sha1));\n> \t\tswitch (rev_compare_tree(revs, p, commit)) {\n> \t\tcase REV_TREE_SAME:\n> -\t\t\ttree_same = 1;\n> \t\t\tif (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {\n> \t\t\t\t/* Even if a merge with an uninteresting\n> \t\t\t\t * side branch brought the entire change\n> @@ -482,7 +570,8 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n> \t\t\t\t * to lose the other branches of this\n> \t\t\t\t * merge, so we just keep going.\n> \t\t\t\t */\n> -\t\t\t\tpp = &parent->next;\n> +\t\t\t\tif (ts)\n> +\t\t\t\t\tts->treesame[nth_parent] = 1;\n\nAgain, tricky but correct. ts->treesame[0] is filled during the\nsecond iteration above, and the same iteration fills ts-tree>same[1]\nhere.\n\nI am starting to like this code ;-).\n\n> \t\t\t\tcontinue;\n> \t\t\t}\n> \t\t\tparent->next = NULL;\n> @@ -511,12 +600,11 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n> \t\tcase REV_TREE_OLD:\n> \t\tcase REV_TREE_DIFFERENT:\n> \t\t\ttree_changed = 1;\n> -\t\t\tpp = &parent->next;\n> \t\t\tcontinue;\n> \t\t}\n> \t\tdie(\"bad tree compare for commit %s\", sha1_to_hex(commit->object.sha1));\n> \t}\n> -\tif (tree_changed && !tree_same)\n> +\tif (tree_changed)\n> \t\treturn;\n> \tcommit->object.flags |= TREESAME;\n> }\n> @@ -773,6 +861,9 @@ static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *li\n> \t * NEEDSWORK: decide if we want to remove parents that are\n> \t * not marked with TMP_MARK from commit->parents for commits\n> \t * in the resulting list. We may not want to do that, though.\n> +\t *\n> +\t * Maybe it should be considered if we are TREESAME to such\n> +\t * parents - now possible with stored per-parent flags.\n> \t */\n\nHmm, that is certainly a thought.\n\n> @@ -1930,28 +2021,32 @@ static void add_child(struct rev_info *revs, struct commit *parent, struct commi\n> \tl->next = add_decoration(&revs->children, &parent->object, l);\n> }\n> \n> -static int remove_duplicate_parents(struct commit *commit)\n> +static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit)\n> {\n> +\tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n> \tstruct commit_list **pp, *p;\n> \tint surviving_parents;\n> \n> \t/* Examine existing parents while marking ones we have seen... */\n> \tpp = &commit->parents;\n> +\tsurviving_parents = 0;\n> \twhile ((p = *pp) != NULL) {\n> \t\tstruct commit *parent = p->item;\n> \t\tif (parent->object.flags & TMP_MARK) {\n> \t\t\t*pp = p->next;\n> +\t\t\tif (ts)\n> +\t\t\t\tcompact_treesame(revs, commit, surviving_parents);\n> \t\t\tcontinue;\n> \t\t}\n> \t\tparent->object.flags |= TMP_MARK;\n> +\t\tsurviving_parents++;\n> \t\tpp = &p->next;\n> \t}\n> -\t/* count them while clearing the temporary mark */\n> -\tsurviving_parents = 0;\n> +\t/* clear the temporary mark */\n> \tfor (p = commit->parents; p; p = p->next) {\n> \t\tp->item->object.flags &= ~TMP_MARK;\n> -\t\tsurviving_parents++;\n> \t}\n> +\t/* no update_treesame() - removing duplicates can't affect TREESAME */\n> \treturn surviving_parents;\n> }\n\nOK.\n\n> @@ -1971,6 +2066,70 @@ static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs,\n> \treturn st;\n> }\n> \n> +static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)\n> +{\n> +\tstruct commit_list *h = reduce_heads(commit->parents);\n> +\tint i = 0, marked = 0;\n> +\tstruct commit_list *po, *pn;\n> +\n> +\t/* Want these for sanity only */\n> +\tint orig_cnt = commit_list_count(commit->parents);\n> +\tint cnt = commit_list_count(h);\n> +\n> +\t/* Not ready to remove items yet, just mark them for now, based\n\n(same style on \"/*\")\n\n> +\t * on the output of reduce_heads(). reduce_heads outputs the reduced\n> +\t * set in its original order, so this isn't too hard.\n> +\t */\n> +\tpo = commit->parents;\n> +\tpn = h;\n> +\twhile (po) {\n> +\t\tif (pn && po->item == pn->item) {\n> +\t\t\tpn=pn->next;\n\n(style) SPs before and after '='.\n\n> +\t\t\ti++;\n> +\t\t}\n> +\t\telse {\n> +\t\t\tpo->item->object.flags |= TMP_MARK;\n> +\t\t\tmarked++;\n> +\t\t}\n> +\t\tpo=po->next;\n> +\t}\n> +\n> +\tif (i != cnt || cnt+marked != orig_cnt)\n> +\t\tdie(\"mark_redundant_parents %d %d %d %d\", orig_cnt, cnt, i, marked);\n> +\n> +\tfree_commit_list(h);\n> +\n> +\treturn marked;\n> +}\n> +\n> +static int remove_marked_parents(struct rev_info *revs, struct commit *commit)\n> +{\n> +\tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n> +\tstruct commit_list **pp, *p;\n> +\tint n, removed = 0;\n> +\n> +\tpp = &commit->parents;\n> +\tn = 0;\n> +\twhile ((p = *pp) != NULL) {\n> +\t\tstruct commit *parent = p->item;\n> +\t\tif (parent->object.flags & TMP_MARK) {\n> +\t\t\tparent->object.flags &= ~TMP_MARK;\n> +\t\t\tcompact_treesame(revs, commit, n);\n> +\t\t\t*pp = p->next;\n> +\t\t\tfree(p);\n> +\t\t\tremoved++;\n> +\t\t\tcontinue;\n> +\t\t}\n> +\t\tpp = &p->next;\n> +\t\tn++;\n> +\t}\n> +\n> +\tif (removed)\n> +\t\tupdate_treesame(revs, commit);\n> +\n> +\treturn removed;\n> +}\n\nOK, even though the use of TMP_MARK (meant to be very localized)\nacross two functions feel somewhat yucky, they are file scope\nstatics next to each other and hopefully are called back to back.\n\n> static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)\n> {\n> \tstruct commit_list *p;\n> @@ -2015,7 +2174,9 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\n> \t}\n> \n> \t/*\n> -\t * Rewrite our list of parents.\n> +\t * Rewrite our list of parents. Note that this cannot\n> +\t * affect our TREESAME flags in anyway - a commit is\n> +\t * always TREESAME to its simplification.\n> \t */\n> \tfor (p = commit->parents; p; p = p->next) {\n> \t\tpst = locate_simplify_state(revs, p->item);\n> @@ -2027,31 +2188,30 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\n> \tif (revs->first_parent_only)\n> \t\tcnt = 1;\n> \telse\n> -\t\tcnt = remove_duplicate_parents(commit);\n> +\t\tcnt = remove_duplicate_parents(revs, commit);\n> \n> \t/*\n> \t * It is possible that we are a merge and one side branch\n> \t * does not have any commit that touches the given paths;\n> -\t * in such a case, the immediate parents will be rewritten\n> -\t * to different commits.\n> +\t * in such a case, the immediate parent from that branch\n> +\t * will be rewritten to be the merge base.\n> \t *\n> \t * o----X\t\tX: the commit we are looking at;\n> \t * / /\t\to: a commit that touches the paths;\n> \t * ---o----'\n> \t *\n> -\t * Further reduce the parents by removing redundant parents.\n> +\t * Detect and simplify this case.\n> \t */\n> \tif (1 < cnt) {\n> -\t\tstruct commit_list *h = reduce_heads(commit->parents);\n> -\t\tcnt = commit_list_count(h);\n> -\t\tfree_commit_list(commit->parents);\n> -\t\tcommit->parents = h;\n> +\t\tint marked = mark_redundant_parents(revs, commit);\n> +\t\tif (marked)\n> +\t\t\tremove_marked_parents(revs, commit);\n> \t}\n\nOK.\n\n> \t/*\n> \t * A commit simplifies to itself if it is a root, if it is\n> \t * UNINTERESTING, if it touches the given paths, or if it is a\n> -\t * merge and its parents simplifies to more than one commits\n> +\t * merge and its parents simplify to more than one commit\n> \t * (the first two cases are already handled at the beginning of\n> \t * this function).\n> \t *\n> @@ -2218,7 +2378,7 @@ static int rewrite_parents(struct rev_info *revs, struct commit *commit)\n> \t\t}\n> \t\tpp = &parent->next;\n> \t}\n> -\tremove_duplicate_parents(commit);\n> +\tremove_duplicate_parents(revs, commit);\n> \treturn 0;\n> }\n> \n> diff --git a/revision.h b/revision.h\n> index 01bd2b7..1abe57b 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -167,6 +167,7 @@ struct rev_info {\n> \tstruct reflog_walk_info *reflog_info;\n> \tstruct decoration children;\n> \tstruct decoration merge_simplification;\n> +\tstruct decoration treesame;\n> \n> \t/* notes-specific options: which refs to show */\n> \tstruct display_notes_opt notes_opt;\n\nNicely done.\n"},{"id":"215769","messageId":"CAJDDKr7-cOz2R31Gq_45Wu70YXiHQOcCTwVVGDjQK3np2+53og@mail.gmail.com","threadId":"33450","inReplyTo":"7vppxfsirl.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges","fromName":"David Aguilar","fromEmail":"davvid@gmail.com","sentAt":"2013-04-27T22:57:41Z","receivedAt":"2013-04-27T22:57:41Z","isPatch":true,"sender":{"key":"davvid@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13196?v=4"},"body":"On Sat, Apr 27, 2013 at 3:36 PM, Junio C Hamano wrote:\n> Kevin Bracey writes:\n>> diff --git a/revision.c b/revision.c\n>> index a67b615..176eb7b 100644\n>> --- a/revision.c\n>> +++ b/revision.c\n>> @@ -1971,6 +2066,70 @@ static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs,\n>> return st;\n>> }\n>>\n>> +static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)\n>> +{\n>> + struct commit_list *h = reduce_heads(commit->parents);\n>> + int i = 0, marked = 0;\n>> + struct commit_list *po, *pn;\n>> +\n>> + /* Want these for sanity only */\n>> + int orig_cnt = commit_list_count(commit->parents);\n>> + int cnt = commit_list_count(h);\n>> +\n>> + /* Not ready to remove items yet, just mark them for now, based\n>\n> (same style on \"/*\")\n>\n>> + * on the output of reduce_heads(). reduce_heads outputs the reduced\n>> + * set in its original order, so this isn't too hard.\n>> + */\n>> + po = commit->parents;\n>> + pn = h;\n>> + while (po) {\n>> + if (pn && po->item == pn->item) {\n>> + pn=pn->next;\n>\n> (style) SPs before and after '='.\n>\n>> + i++;\n>> + }\n>> + else {\n\n(style) cuddle this } else { block.\n--\nDavid\n"},{"id":"215770","messageId":"7vli83shk0.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"1367004718-30048-2-git-send-email-kevin@bracey.fi","subject":"Re: [RFC/PATCH 2/3] simplify-merges: never remove all TREESAME parents","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-27T23:02:55Z","receivedAt":"2013-04-27T23:02:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> In the event of an odd merge, we may find ourselves TREESAME to\n> apparently redundant parents. Prevent simplify_merges() from removing\n> every TREESAME parent - in the event of such a merge it's useful to see\n> where we came actually from came.\n>\n> Signed-off-by: Kevin Bracey \n> ---\n> Documentation/rev-list-options.txt | 3 ++-\n> revision.c | 24 ++++++++++++++++++++++++\n> 2 files changed, 26 insertions(+), 1 deletion(-)\n>\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index 380db48..0832004 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -472,7 +472,8 @@ history according to the following rules:\n> +\n> * Replace each parent `P` of `C'` with its simplification `P'`. In\n> the process, drop parents that are ancestors of other parents, and\n> - remove duplicates.\n> + remove duplicates, but take care to never drop all parents that\n> + we are TREESAME to.\n> +\n> * If after this parent rewriting, `C'` is a root or merge commit (has\n> zero or >1 parents), a boundary commit, or !TREESAME, it remains.\n> diff --git a/revision.c b/revision.c\n> index 176eb7b..4e27c9a 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -2106,8 +2106,32 @@ static int remove_marked_parents(struct rev_info *revs, struct commit *commit)\n> {\n> \tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n> \tstruct commit_list **pp, *p;\n> +\tstruct commit *su = NULL, *sm = NULL;\n\nWhat do \"su\" and \"sm\" stand for?\n\n> \tint n, removed = 0;\n> \n> +\t/* Prescan - look for both marked and unmarked TREESAME parents */\n> +\tfor (p = commit->parents, n = 0; p; p = p->next, n++) {\n> +\t\tif (ts->treesame[n]) {\n> +\t\t\tif (p->item->object.flags & TMP_MARK) {\n> +\t\t\t\tif (!sm) sm = p->item;\n> +\t\t\t}\n> +\t\t\telse {\n> +\t\t\t\tif (!su) {\n> +\t\t\t\t\tsu = p->item;\n> +\t\t\t\t\tbreak;\n> +\t\t\t\t}\n> +\t\t\t}\n> +\t\t}\n> +\t}\n> +\n> +\t/* If we are TREESAME to a marked-for-deletion parent, but not to any\n> +\t * unmarked parents, unmark the first TREESAME parent. We don't want\n> +\t * to remove our \"real\" parent in the event of an \"-s ours\" type\n> +\t * merge.\n\nCould you explain here a bit more the reason why we do not want to\nremove them and why \"-s ours\" is so significant that it deserves to\nbe singled out? And why randomly picking one that is redundant\n(because it is an ancestor of some other parent) is an improvement?\n\nThe \"remove-redundant\" logic first marks commits that are ancestors\nof other commits in the original set, without taking treesame[] into\naccount at all. If the final objective of the code is to keep paths\nthat consists of non-treesame[] commits, perhaps the logic needs to\nbe changed to reject non-treesame[] commits that are ancestors of\nother non-treesame[] commits, or something?\n\n> +\t */\n> +\tif (!su && sm)\n> +\t\tsm->object.flags &= ~TMP_MARK;\n> +\n> \tpp = &commit->parents;\n> \tn = 0;\n> \twhile ((p = *pp) != NULL) {\n"},{"id":"215786","messageId":"517CC9AE.30407@bracey.fi","threadId":"33450","inReplyTo":"7vppxfsirl.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-28T07:03:10Z","receivedAt":"2013-04-28T07:03:10Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 28/04/2013 01:36, Junio C Hamano wrote:\n> Kevin Bracey writes:\n>\n>> Historically TREESAME was set on a commit if it was TREESAME to _any_ of\n>> its parents. This is not optimal, as such a merge could still be worth\n>> showing, particularly if it is an odd \"-s ours\" merge that (possibly\n>> accidentally) dropped a change.\n> \"... and with options like --full-history or --simplify-merges are\n> used to get more complete history\", I think. \"git log path\" without\n> these options is a tool to get one version of simplified history\n> that explains the end result, and by definition, the side branch\n> merged by \"-s ours\" did _not_ contribute anything to the end result.\n\nYeah, I'm not happy with this commit message - I knocked it up \nseparately from my first pass, which I didn't have to hand. Next version \nwill combine it with the original, which better distinguished the \ndefault mode, and specifically addressed the \"--full-history -S\" search \nproblem.\n\nThat's key - that I really want such searches to be able to track the \nentire life of a change on a side branch, not potentially showing just \nits birth as now, but also always including any ultimate merge death. (I \nthink that we may be able to refine --ancestry-path to give an even \ntighter pinpoint, but --full-history should definitely include the \ninformation, as per its name).\n\n>\n> Do we want to discard the decoration data when the commit becomes a\n> non-merge?\n\nWould seem reasonable, and would also help make concrete why we update \nTREESAME immediately, and not in update_treesame(), but I didn't spot a \nmechanism to discard decoration. I'll recheck.\n\n>\n>> +\t\tcommit->object.flags |= TREESAME;\n>> +\t\tfor (n = 0; n < st->nparents; n++) {\n>> +\t\t\tif (!st->treesame[n]) {\n>> +\t\t\t\tcommit->object.flags &= ~TREESAME;\n>> +\t\t\t\tbreak;\n>> +\t\t\t}\n>> +\t\t}\n> Can a commit that earlier was marked as TREESAME become not TREESAME?\n> Wouldn't simplification only increase sameness, never decrease?\n\nThat's true - I paid attention to that earlier when it really mattered \ndue to the cost of recalculating it with try_to_simplify_commit(). Not \nsure that it matters so much any more, and I don't see how we can use \nthat information to change this \"scan for !treesame\" loop.\n\nI could insert an \"if (!commit->object.flags & TREESAME)\" test to skip \nthe entire update. I'd be inclined to do that as the caller of \nupdate_treesame(). I think update_treesame() itself should be \ngeneral-purpose without assumptions about what changes have been made, \nso it's a pure treesame[]->TREESAME calculation, without TREESAME as an \ninput.\n\n(Aside - just occurred to me we could swap the loop for \n\"strlen(st->treesame) == st->nparents\", if we kept a zero terminator in \nthe array. Maybe a bit too smart-ass?)\n\n\n>\n>> +\tfor (pp = &commit->parents;\n>> +\t (parent = *pp) != NULL;\n>> +\t pp = &parent->next, nth_parent++) {\n> I see the reason to change from while to for is because you wanted\n> to count, and I think it makes sense; but it is more readable to\n> initialise the counter here, too, if that is the case. I.e.\n>\n> \tfor (pp = &commit->parents, nth_parent = 0;\n> \t !(parent = *pp);\n> \t pp = &parent->next, nth_parent++) {\n\nAgree on nth_parent, but \"!(parent = *pp)\" isn't \"(parent = *pp) != \nNULL\", mind. Did you mean \"!!\"? In which case I still prefer it my way.\n\n>\n> +\t\t\t\tif (!tree_changed)\n> +\t\t\t\t\tts->treesame[0] = 1;\n> Have we made any two tree comparison at this point to set this one?\n> Ahh, this is tricky. You do this in the _second_ iteration of the\n> loop, so tree_changed here is from inspecting the first parent, not\n> the one we are looking at (i.e. *p).\n\nYes, this is the \"we've reached our second iteration, so from now on \nwe're dealing a merge\" if {} block. I'll clarify this in the comment at \nthe top, and note that we're populating the newly-allocated treesame[] \nfrom our first iteration.\n\n>\n>> \n>> @@ -773,6 +861,9 @@ static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *li\n>> \t * NEEDSWORK: decide if we want to remove parents that are\n>> \t * not marked with TMP_MARK from commit->parents for commits\n>> \t * in the resulting list. We may not want to do that, though.\n>> +\t *\n>> +\t * Maybe it should be considered if we are TREESAME to such\n>> +\t * parents - now possible with stored per-parent flags.\n>> \t */\n> Hmm, that is certainly a thought.\n\nMy comment's wrong though. Reconsidering, what I think needs removing is \nactually off-ancestry parents that we are !TREESAME to, when we are \nTREESAME on the ancestry path.\n\nI've realised while testing this that there's been one thing that's \nconfused me repeatedly, and I think this comment was an example of it. \nThe example in the rev-list-options manual is wrong.\n\n .-A---M---N---O---P\n / / / / /\n I B C D E\n \\ / / / /\n `-------------'\n\nContrary to the manual, merge P is !TREESAME to E (or I). E's base is \nold enough that E isn't up-to-date w.r.t. \"foo\". Thus merge \"P\" is no \nlonger TREESAME and does become subject to display with the new \n--full-history:\n\n I A B N D O P\n\nI believe this is correct, because P is a merge that determined the fate \nof \"foo\", so merits --full-history inspection. (--simplify-merges \nobviously knocks P back out again: --simplify-merges becomes more \nimportant if --full-history gets fuller).\n\nGiven this error, and this change, I think this example may want a \nslight rethink. Do we want a proper \"messing with other paths but \nTREESAME merge\" example? Say if E's parent was O, P would not be \nTREESAME and not included in --full-history.\n\n>\n> OK, even though the use of TMP_MARK (meant to be very localized)\n> across two functions feel somewhat yucky, they are file scope\n> statics next to each other and hopefully are called back to back.\n\nWell, by the end of the series you've got two functions setting it, in \npreparation for later input to this function. And what's the upper bound \non complexity of functions that may want to mark removal? They may need \nTMP_MARK to do the job. I'm beginning to think that it should be a \ndedicated REMOVE bit.\n\nKevin\n"},{"id":"215785","messageId":"517CCB57.3060807@bracey.fi","threadId":"33450","inReplyTo":"7vli83shk0.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 2/3] simplify-merges: never remove all TREESAME parents","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-28T07:10:15Z","receivedAt":"2013-04-28T07:10:15Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 28/04/2013 02:02, Junio C Hamano wrote:\n> Kevin Bracey writes:\n>\n>> In the event of an odd merge, we may find ourselves TREESAME to\n>> apparently redundant parents. Prevent simplify_merges() from removing\n>> every TREESAME parent - in the event of such a merge it's useful to see\n>> where we came actually from came.\n\n\"came from\" :)\n\n>>\n>> @@ -2106,8 +2106,32 @@ static int remove_marked_parents(struct rev_info *revs, struct commit *commit)\n>> {\n>> \tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n>> \tstruct commit_list **pp, *p;\n>> +\tstruct commit *su = NULL, *sm = NULL;\n> What do \"su\" and \"sm\" stand for?\n\n\"same, unmarked\" and \"same, marked\" were what was in my head.\n\n\n> Could you explain here a bit more the reason why we do not want to\n> remove them and why \"-s ours\" is so significant that it deserves to\n> be singled out? And why randomly picking one that is redundant\n> (because it is an ancestor of some other parent) is an improvement?\n\nI feel it's consistent with the default non-full-history behaviour. The \nparent that we choose not to remove is the same one that the default \nlog with \"simplify_history==1\" would have followed: the first parent we \nare TREESAME to. Or at least that's the intent. So this parent would \nnormally be singled out, and it's not an arbitrary (or \"random\") choice.\n\nIt feels wrong to me that --full-history --simplify-merges could produce \na disjoint history from the default. I think it should include the \ndefault simple history. If this code triggered, it should produce \nsomething quite distinctive in a graphical view, which will help find \nodd/broken merges.\n\n\n> The \"remove-redundant\" logic first marks commits that are ancestors\n> of other commits in the original set, without taking treesame[] into\n> account at all. If the final objective of the code is to keep paths\n> that consists of non-treesame[] commits, perhaps the logic needs to\n> be changed to reject non-treesame[] commits that are ancestors of\n> other non-treesame[] commits, or something?\n\nMaybe - the main simplify_merges machinery could certainly make use of \nthe treesame[] information, and one of the motivations for introducing \nit was to open up the possibility of richer analysis. I'll spend a \nlittle time to think about whether we want a more fundamental change to \nthe original scan.\n\nBut this patch as it stands was an \"easy\" change to make with clearly \nlimited scope and relatively little risk - I specifically wanted just to \ninclude our default \"simple\" parent.\n\nKevin\n"},{"id":"215794","messageId":"7va9oisf1k.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"517CCB57.3060807@bracey.fi","subject":"Re: [RFC/PATCH 2/3] simplify-merges: never remove all TREESAME parents","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-28T18:09:27Z","receivedAt":"2013-04-28T18:09:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n>> Could you explain here a bit more the reason why we do not want to\n>> remove them and why \"-s ours\" is so significant that it deserves to\n>> be singled out? And why randomly picking one that is redundant\n>> (because it is an ancestor of some other parent) is an improvement?\n>\n> I feel it's consistent with the default non-full-history\n> behaviour. The parent that we choose not to remove is the same one\n> that the default log with \"simplify_history==1\" would have followed:\n> the first parent we are TREESAME to. Or at least that's the intent. So\n> this parent would normally be singled out, and it's not an arbitrary\n> (or \"random\") choice.\n>\n> It feels wrong to me that --full-history --simplify-merges could\n> produce a disjoint history from the default.\n\nFinally ;-) That \"avoid creating a disjoint history\" is the \"why we\ndo not want to remove them\" I wanted to see in the same comment.\n\n> But this patch as it stands was an \"easy\" change to make with clearly\n> limited scope and relatively little risk - I specifically wanted just\n> to include our default \"simple\" parent.\n\nYeah, I think it all makes sense.\n"},{"id":"215795","messageId":"7v61z6sdpz.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"517CC9AE.30407@bracey.fi","subject":"Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-28T18:38:00Z","receivedAt":"2013-04-28T18:38:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n>> Do we want to discard the decoration data when the commit becomes a\n>> non-merge?\n>\n> Would seem reasonable, and would also help make concrete why we update\n> TREESAME immediately, and not in update_treesame(), but I didn't spot\n> a mechanism to discard decoration. I'll recheck.\n\nWhat I meant was a simple \"free(it)\" and a call to add_decoration()\nto register a NULL for the object whose treesame[] we no longer\nneed.\n\n> I could insert an \"if (!commit->object.flags & TREESAME)\" test to skip\n> the entire update. I'd be inclined to do that as the caller of\n> update_treesame(). I think update_treesame() itself should be\n> general-purpose without assumptions about what changes have been made,\n> so it's a pure treesame[]->TREESAME calculation, without TREESAME as\n> an input.\n\nMakes sense.\n\n> (Aside - just occurred to me we could swap the loop for\n> \"strlen(st->treesame) == st->nparents\", if we kept a zero terminator\n> in the array. Maybe a bit too smart-ass?)\n\nProbably ;-)\n\n>>> +\tfor (pp = &commit->parents;\n>>> +\t (parent = *pp) != NULL;\n>>> +\t pp = &parent->next, nth_parent++) {\n>> I see the reason to change from while to for is because you wanted\n>> to count, and I think it makes sense; but it is more readable to\n>> initialise the counter here, too, if that is the case. I.e.\n>>\n>> \tfor (pp = &commit->parents, nth_parent = 0;\n>> \t !(parent = *pp);\n>> \t pp = &parent->next, nth_parent++) {\n>\n> Agree on nth_parent, but \"!(parent = *pp)\" isn't \"(parent = *pp) !=\n> NULL\", mind. Did you mean \"!!\"? In which case I still prefer it my\n> way.\n\nDroppage of NULL check was a typo. I only meant A part of for(A;B;C).\n\n>>> @@ -773,6 +861,9 @@ static void limit_to_ancestry(struct\n>>> commit_list *bottom, struct commit_list *li\n>>> \t * NEEDSWORK: decide if we want to remove parents that are\n>>> \t * not marked with TMP_MARK from commit->parents for commits\n>>> \t * in the resulting list. We may not want to do that, though.\n>>> +\t *\n>>> +\t * Maybe it should be considered if we are TREESAME to such\n>>> +\t * parents - now possible with stored per-parent flags.\n>>> \t */\n>> Hmm, that is certainly a thought.\n>\n> My comment's wrong though. Reconsidering, what I think needs removing\n> is actually off-ancestry parents that we are !TREESAME to, when we are\n> TREESAME on the ancestry path.\n\nI thought I read you meant exactly that, i.e. !TREESAME, but now I\nre-read what is quoted, you did say \"we are TREESAME\" ;-). I think\nI agree with you that we do not want any side branch that is not on\nthe ancestry path we are interested in to affect the sameness\nassigned to the merge commit.\n\n> I've realised while testing this that there's been one thing that's\n> confused me repeatedly, and I think this comment was an example of\n> it. The example in the rev-list-options manual is wrong.\n>\n> * *\n> .-A---M---N---O---P\n> /* / /* /* /*\n> I B C D E\n> \\ /* / /* /\n> `-------------'\n\nI've added '*' next to each arc between a commit-pair whose contents\nat 'foo' are different to the illustration, following the set-up the\nmanual describes. E is the same as I for 'foo' and P would resolve\n'foo' to be the same as O.\n\n> Contrary to the manual, merge P is !TREESAME to E (or I). E's base is\n> old enough that E isn't up-to-date w.r.t. \"foo\". Thus merge \"P\" is no\n> longer TREESAME and does become subject to display with the new\n> --full-history:\n>\n> I A B N D O P\n\nAssuming N's parents-list is rewritten to be A and B, this sounds\nsensible.\n\n> I believe this is correct, because P is a merge that determined the\n> fate of \"foo\", so merits --full-history inspection. (--simplify-merges\n> obviously knocks P back out again: --simplify-merges becomes more\n> important if --full-history gets fuller).\n\nE simplifies to I which is already an ancestor of O and is redundant\nwhen inspecting P, hence P becomes a single-parent child of O and\nfurther simplifies to O because it has the same 'foo'. Makes sense.\n\n> Given this error, and this change, I think this example may want a\n> slight rethink. Do we want a proper \"messing with other paths but\n> TREESAME merge\" example? Say if E's parent was O, P would not be\n> TREESAME and not included in --full-history.\n\nI am not sure if I follow your last sentence. \n\nDo you mean this topology, where E's sole parent is O, i.e.\n\n E\n / \\\n\tN---O---P\n /*\n D\n\nand E does not change 'foo' from O? Then P is TREESAME to all its\nparents and would not have to appear in the full history for the\nsame reason M does not appear in your earlier IABNDOP output, no?\n\n>> OK, even though the use of TMP_MARK (meant to be very localized)\n>> across two functions feel somewhat yucky, they are file scope\n>> statics next to each other and hopefully are called back to back.\n>\n> Well, by the end of the series you've got two functions setting it, in\n> preparation for later input to this function.\n\nAs long as \"setting\" and \"using and then cleaning after done\" are\nlocalized enough so that nobody will be tempted to insert another\ncomplex processing in between that might need TMP_MARK we should be\nOK.\n"},{"id":"215882","messageId":"517EB205.6090804@bracey.fi","threadId":"33450","inReplyTo":"7v61z6sdpz.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-04-29T17:46:45Z","receivedAt":"2013-04-29T17:46:45Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 28/04/2013 21:38, Junio C Hamano wrote:\n>\n>>>> @@ -773,6 +861,9 @@ static void limit_to_ancestry(struct\n>>>> commit_list *bottom, struct commit_list *li\n>>>> \t * NEEDSWORK: decide if we want to remove parents that are\n>>>> \t * not marked with TMP_MARK from commit->parents for commits\n>>>> \t * in the resulting list. We may not want to do that, though.\n>>>> +\t *\n>>>> +\t * Maybe it should be considered if we are TREESAME to such\n>>>> +\t * parents - now possible with stored per-parent flags.\n>>>> \t */\n>>> Hmm, that is certainly a thought.\n>> My comment's wrong though. Reconsidering, what I think needs removing\n>> is actually off-ancestry parents that we are !TREESAME to, when we are\n>> TREESAME on the ancestry path.\n> I thought I read you meant exactly that, i.e. !TREESAME, but now I\n> re-read what is quoted, you did say \"we are TREESAME\" ;-). I think\n> I agree with you that we do not want any side branch that is not on\n> the ancestry path we are interested in to affect the sameness\n> assigned to the merge commit.\n\nI did a trial implementation of this in limit_to_ancestry(), and the \nresult was lovely, but in the end I decided it's not actually the right \nplace to do it. The logic is more general than that; this isn't just an \nancestry-path issue, and I think \"hiding\" parents isn't the right way to \ngo about it anyway.\n\nTo slightly generalise your own wording: I think the rule is \"we do not \nwant any side branch that is UNINTERESTING to affect the sameness \nassigned to the merge commit\". I think that rule applies to all dense, \npruned modes.\n\nHaving experimented with some of the annoyingly complex merge paths that \noriginally prompted this series, it seems this rule makes a huge \ndifference, and it's useful whether asking \"--simplify-merges A..B \n\" or \"--ancestry-path A..B \".\n\nAt present, either query will show lots of really boring merge commits \nof topic branches at the boundary, with 1 INTERESTING parent that \nthey're TREESAME too, and 1 UNINTERESTING parent that they may or may \nnot be TREESAME to, depending on how old the base of that topic branch \nwas. Most such commits are of no relevance to our history whatsoever. In \nthe case of \"--simplify-merges\", the fact that they're UNINTERESTING \nactually _prevented_ their simplification - if it had been allowed to \nfollow the UNINTERESTING path back further, it would have reached an \nancestor, and been found redundant. So limiting the rev-list actually \nincreases the number of merges shown.\n\nWe can lose all those boring commits with these two changes:\n\n1) Previously TREESAME was defined as \"this commit matches at least 1 \nparent\". My first patch changes it to \"this commit matches all parents\". \nIt should be refined further to \"this commit matches all INTERESTING \nparents, if it has any, else all (UNINTERESTING) parents\". (Can we word \nthat better?) Note that this fancy rule collapses to the same \nstraightforward TREESAME check as ever for 0- or 1-parent commits.\n\n2) simplify_merges currently will not simplify commits unless they have \nexactly 1 parent. That's not what we want. We only need to preserve \ncommits that don't have exactly 1 INTERESTING parent.\n\nThose 2 rules produce the desirable result: if we have a merge commit \nwith exactly 1 INTERESTING parent it is TREESAME to, it is always \nsimplified away - any other UNINTERESTING parents it may have did not \naffect our code, so we don't care about whether we were TREESAME to them \nor not, and as we don't want to see any of the UNINTERESTING parents \nthemselves, the merge is not worth showing.\n\nThis makes a massive difference on some of my searches, reducing the \ntotal commits shown by a factor of 5 to 10, greatly improving the \nsignal-to-noise ratio.\n\nI'll put together a trial patch at the end of the next iteration of the \nseries that implements this logic. I need to think a bit more - I think \n\"get_commit_action\" needs a similar INTERESTING check for merges too, to \nget the same sort of effect without relying on simplify_merges. Parent \nrewriting shouldn't necessitate keeping all merges - only merges with 2+ \nINTERESTING parents.\n\n>>\n>> * *\n>> .-A---M---N---O---P\n>> /* / /* /* /*\n>> I B C D E\n>> \\ /* / /* /\n>> `-------------'\n> I've added '*' next to each arc between a commit-pair whose contents\n> at 'foo' are different to the illustration, following the set-up the\n> manual describes. E is the same as I for 'foo' and P would resolve\n> 'foo' to be the same as O.\n\nI think that sort of thing could be a useful patch to the docs.\n>\n>> Given this error, and this change, I think this example may want a\n>> slight rethink. Do we want a proper \"messing with other paths but\n>> TREESAME merge\" example? Say if E's parent was O, P would not be\n>> TREESAME and not included in --full-history.\n> I am not sure if I follow your last sentence.\n>\n> Do you mean this topology, where E's sole parent is O, i.e.\n>\n> E\n> / \\\n> \tN---O---P\n> /*\n> D\n>\n> and E does not change 'foo' from O? Then P is TREESAME to all its\n> parents and would not have to appear in the full history for the\n> same reason M does not appear in your earlier IABNDOP output, no?\n\nThat's the topology I was thinking of. Yes, P is then \"full-TREESAME\" \nlike M, but it's just a more typical example of a real merge and why \nTREESAMEness arises than M is. M didn't appear in full-history because \nboth parents made the same change to foo - indeed both parents were \nidentical. Whereas P wouldn't appear because E is different, but changed \nsomething other than foo.\n\nKevin\n"},{"id":"215889","messageId":"7v1u9tjjfv.fsf@alter.siamese.dyndns.org","threadId":"33450","inReplyTo":"517EB205.6090804@bracey.fi","subject":"Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-29T18:11:32Z","receivedAt":"2013-04-29T18:11:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> At present, either query will show lots of really boring merge commits\n> of topic branches at the boundary, with 1 INTERESTING parent that\n> they're TREESAME too, and 1 UNINTERESTING parent that they may or may\n> not be TREESAME to, depending on how old the base of that topic branch\n> was. Most such commits are of no relevance to our history\n> whatsoever. In the case of \"--simplify-merges\", the fact that they're\n> UNINTERESTING actually _prevented_ their simplification - if it had\n> been allowed to follow the UNINTERESTING path back further, it would\n> have reached an ancestor, and been found redundant. So limiting the\n> rev-list actually increases the number of merges shown.\n>\n> We can lose all those boring commits with these two changes:\n>\n> 1) Previously TREESAME was defined as \"this commit matches at least 1\n> parent\". My first patch changes it to \"this commit matches all\n> parents\". It should be refined further to \"this commit matches all\n> INTERESTING parents, if it has any, else all (UNINTERESTING)\n> parents\". (Can we word that better?) Note that this fancy rule\n> collapses to the same straightforward TREESAME check as ever for 0- or\n> 1-parent commits.\n>\n> 2) simplify_merges currently will not simplify commits unless they\n> have exactly 1 parent. That's not what we want. We only need to\n> preserve commits that don't have exactly 1 INTERESTING parent.\n>\n> Those 2 rules produce the desirable result: if we have a merge commit\n> with exactly 1 INTERESTING parent it is TREESAME to, it is always\n> simplified away - any other UNINTERESTING parents it may have did not\n> affect our code, so we don't care about whether we were TREESAME to\n> them or not, and as we don't want to see any of the UNINTERESTING\n> parents themselves, the merge is not worth showing.\n>\n> This makes a massive difference on some of my searches, reducing the\n> total commits shown by a factor of 5 to 10, greatly improving the\n> signal-to-noise ratio.\n>\n> I'll put together a trial patch at the end of the next iteration of\n> the series that implements this logic. I need to think a bit more - I\n> think \"get_commit_action\" needs a similar INTERESTING check for merges\n> too, to get the same sort of effect without relying on\n> simplify_merges. Parent rewriting shouldn't necessitate keeping all\n> merges - only merges with 2+ INTERESTING parents.\n\nEverything you wrote above makes tons of sense.\n\nOne small worry is how this new simplification interacts with the\nfirst parent mode. For the purpose of showing the merge commit\nitself, the second and subsequent parents are treated as \"not\nINTERESTING\" in the above discussion, but that should not propagate\nback to their parents like the normal UNINTERESTING-ness does.\n"}]}