{"thread":{"id":"33729","subject":"[PATCH v3 3/9] t6111: new TREESAME test set","startedAt":"2013-05-05T15:32:48Z","lastAt":"2013-05-07T16:28:14Z","messageCount":20,"participants":["Kevin Bracey","Junio C Hamano"],"isPatch":true,"patchVersion":3,"patchTotal":9},"messages":[{"id":"216449","messageId":"1367767977-14513-1-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":null,"subject":"[PATCH v3 0/9] History traversal refinements","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-05T15:32:48Z","receivedAt":"2013-05-05T15:32:48Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"New version - nothing much changed since v2.2, except the new test\nset to illustrate and prove the changes. Not sure about the t6111\nnumbering - there wasn't space where I really wanted to put it.\nAnd maybe it should be appended to one of the existing tests.\n\nYou will note that I'm floundering for the name for the commits I care\nabout in part 9. Currently at \"priority\", but that's horrible, not least\nbecause it isn't an adjective. I think the word I really want is\n\"interesting\", but that's already taken... \"Relevant\", \"important\"?\n\nJunio C Hamano (1):\n t6012: update test for tweaked full-history traversal\n\nKevin Bracey (8):\n decorate.c: compact table when growing\n t6019: test file dropped in -s ours merge\n t6111: new TREESAME test set\n rev-list-options.txt: correct TREESAME for P\n revision.c: Make --full-history consider more merges\n simplify-merges: never remove all TREESAME parents\n simplify-merges: drop merge from irrelevant side branch\n revision.c: discount side branches when computing TREESAME\n\n Documentation/rev-list-options.txt | 38 +--\n decorate.c | 2 +-\n revision.c | 511 +++++++++++++++++++++++++++++++++----\n revision.h | 4 +-\n t/t6012-rev-list-simplify.sh | 31 ++-\n t/t6019-rev-list-ancestry-path.sh | 29 ++-\n t/t6111-rev-list-treesame.sh | 180 +++++++++++++\n 7 files changed, 723 insertions(+), 72 deletions(-)\n create mode 100755 t/t6111-rev-list-treesame.sh\n\n-- \n1.8.3.rc0.28.g682c2d9\n"},{"id":"216452","messageId":"1367767977-14513-2-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":"1367767977-14513-1-git-send-email-kevin@bracey.fi","subject":"[PATCH v3 1/9] decorate.c: compact table when growing","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-05T15:32:49Z","receivedAt":"2013-05-05T15:32:49Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"When growing the table, take the opportunity to \"compact\" it by removing\nentries with NULL decoration.\n\nUsers may have \"removed\" decorations by passing NULL to\ninsert_decoration. An object's table entry can't actually be removed\nduring normal operation, as it would break the linear hash collision\nsearch. But we can remove NULL decoration entries when rebuilding the\ntable.\n\nSigned-off-by: Kevin Bracey \n---\n decorate.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/decorate.c b/decorate.c\nindex 2f8a63e..7cb5d29 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -49,7 +49,7 @@ static void grow_decoration(struct decoration *n)\n \t\tconst struct object *base = old_hash[i].base;\n \t\tvoid *decoration = old_hash[i].decoration;\n \n-\t\tif (!base)\n+\t\tif (!decoration)\n \t\t\tcontinue;\n \t\tinsert_decoration(n, base, decoration);\n \t}\n-- \n1.8.3.rc0.28.g682c2d9\n"},{"id":"216454","messageId":"1367767977-14513-3-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":"1367767977-14513-1-git-send-email-kevin@bracey.fi","subject":"[PATCH v3 2/9] t6019: test file dropped in -s ours merge","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-05T15:32:50Z","receivedAt":"2013-05-05T15:32:50Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"In preparation for upcoming TREESAME work, check the result for G.t,\nwhich is dropped in \"-s ours\" merge L. The default rev-list is empty, as\nexpected - it follows the first parent path where it never existed.\n\nUnfortunately, --ancestry-path is also empty. Merges H J and L are all\nTREESAME to 1 parent, so are treated as TREESAME and not shown. This is\nclearly undesirable in the case of merge L, which dropped our G.t by\ntaking the non-ancestry-path version. Document this as a known failure,\nand expect \"H J L\", the 3 merges along the path that had to chose G.t\nversions.\n\nSigned-off-by: Kevin Bracey \n---\n t/t6019-rev-list-ancestry-path.sh | 21 ++++++++++++++++++++-\n 1 file changed, 20 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh\nindex 39b4cb0..86ef908 100755\n--- a/t/t6019-rev-list-ancestry-path.sh\n+++ b/t/t6019-rev-list-ancestry-path.sh\n@@ -13,6 +13,9 @@ test_description='--ancestry-path'\n #\n # D..M -- M.t == M\n # --ancestry-path D..M -- M.t == M\n+#\n+# G..M -- G.t == [nothing - was dropped in \"-s ours\" merge L]\n+# --ancestry-path G..M -- G.t == H J L\n \n . ./test-lib.sh\n \n@@ -63,13 +66,29 @@ test_expect_success 'rev-list D..M -- M.t' '\n \ttest_cmp expect actual\n '\n \n-test_expect_success 'rev-list --ancestry-patch D..M -- M.t' '\n+test_expect_success 'rev-list --ancestry-path D..M -- M.t' '\n \techo M >expect &&\n \tgit rev-list --ancestry-path --format=%s D..M -- M.t |\n \tsed -e \"/^commit /d\" >actual &&\n \ttest_cmp expect actual\n '\n \n+# G.t is dropped in an \"-s ours\" merge\n+test_expect_success 'rev-list G..M -- G.t' '\n+\t>expect &&\n+\tgit rev-list --format=%s G..M -- G.t |\n+\tsed -e \"/^commit /d\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_failure 'rev-list --ancestry-path G..M -- G.t' '\n+\tfor c in H J L; do echo $c; done >expect &&\n+\tgit rev-list --ancestry-path --format=%s G..M -- G.t |\n+\tsed -e \"/^commit /d\" |\n+\tsort >actual &&\n+\ttest_cmp expect actual\n+'\n+\n # b---bc\n # / \\ /\n # a X\n-- \n1.8.3.rc0.28.g682c2d9\n"},{"id":"216446","messageId":"1367767977-14513-4-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":"1367767977-14513-1-git-send-email-kevin@bracey.fi","subject":"[PATCH v3 3/9] t6111: new TREESAME test set","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-05T15:32:51Z","receivedAt":"2013-05-05T15:32:51Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"Some side branching and odd merging to illustrate various flaws in\nrevision list scans, particularly when limiting the list.\n\nMany expected failures, which will be gone by the end of the \"history\ntraversal refinements\" series.\n\nSigned-off-by: Kevin Bracey \n---\n t/t6111-rev-list-treesame.sh | 180 +++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 180 insertions(+)\n create mode 100755 t/t6111-rev-list-treesame.sh\n\ndiff --git a/t/t6111-rev-list-treesame.sh b/t/t6111-rev-list-treesame.sh\nnew file mode 100755\nindex 0000000..602c02d\n--- /dev/null\n+++ b/t/t6111-rev-list-treesame.sh\n@@ -0,0 +1,180 @@\n+#!/bin/sh\n+#\n+# ,---E--. *H----------. * marks !TREESAME parent paths\n+# / \\ / \\*\n+# *A--*B---D--*F-*G---------K-*L-*M\n+# \\ /* \\ /\n+# `-C-' `-*I-*J\n+#\n+# A creates \"file\", B and F change it.\n+# Odd merge G takes the old version from B.\n+# I changes it, but J reverts it.\n+# H and L both change it, and M merges those changes.\n+\n+test_description='TREESAME and limiting'\n+\n+. ./test-lib.sh\n+\n+note () {\n+\tgit tag \"$1\"\n+}\n+\n+unnote () {\n+\tgit name-rev --tags --stdin | sed -e \"s|$_x40 (tags/\\([^)]*\\)) |\\1 |g\"\n+}\n+\n+test_expect_success setup '\n+\ttest_commit \"Initial file\" file \"Hi there\" A &&\n+\tgit branch other-branch &&\n+\n+\ttest_commit \"file=Hello\" file \"Hello\" B &&\n+\tgit branch third-branch &&\n+\n+\tgit checkout other-branch &&\n+\ttest_commit \"Added other\" other \"Hello\" C &&\n+\n+\tgit checkout master &&\n+\ttest_merge D other-branch &&\n+\n+\tgit checkout third-branch &&\n+\ttest_commit \"Third file\" third \"Nothing\" E &&\n+\n+\tgit checkout master &&\n+\ttest_commit \"file=Blah\" file \"Blah\" F &&\n+\n+\ttest_tick && git merge --no-commit third-branch &&\n+\tgit checkout third-branch file &&\n+\tgit commit &&\n+\tnote G &&\n+\tgit branch fiddler-branch &&\n+\n+\tgit checkout -b part2-branch &&\n+\ttest_commit \"file=Part 2\" file \"Part 2\" H &&\n+\n+\tgit checkout fiddler-branch &&\n+\ttest_commit \"Bad commit\" file \"Silly\" I &&\n+\n+\ttest_tick && git revert I && note J &&\n+\n+\tgit checkout master &&\n+\ttest_tick && git merge --no-ff fiddler-branch &&\n+\tnote K\n+\n+\ttest_commit \"file=Part 1\" file \"Part 1\" L &&\n+\n+\ttest_tick && test_must_fail git merge part2-branch &&\n+\ttest_commit M file \"Parts 1+2\"\n+'\n+\n+FMT='tformat:%P \t%H | %s'\n+\n+# could we soup this up to optionally check parents? So \"(BA)C\" would check\n+# that C is shown and has parents B A.\n+check_outcome () {\n+\toutcome=$1\n+\tshift\n+\tfor c in $1\n+\tdo\n+\t\techo \"$c\"\n+\tdone >expect &&\n+\tshift &&\n+\tparam=\"$*\" &&\n+\ttest_expect_$outcome \"log $param\" '\n+\t\tgit log --format=\"$FMT\" $param |\n+\t\tunnote >actual &&\n+\t\tsed -e \"s/^.*\t\\([^ ]*\\) .*/\\1/\" >check \n---\n Documentation/rev-list-options.txt | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 3bdbf5e..50bbff7 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -367,8 +367,7 @@ each merge. The commits are:\n `N` and `D` to \"foobarbaz\"; i.e., it is not TREESAME to any parent.\n \n * `E` changes `quux` to \"xyzzy\", and its merge `P` combines the\n- strings to \"quux xyzzy\". Despite appearing interesting, `P` is\n- TREESAME to all parents.\n+ strings to \"quux xyzzy\". `P` is TREESAME to `O`, but not to `E`.\n \n 'rev-list' walks backwards through history, including or excluding\n commits based on whether '\\--full-history' and/or parent rewriting\n-- \n1.8.3.rc0.28.g682c2d9\n"},{"id":"216456","messageId":"1367767977-14513-6-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":"1367767977-14513-1-git-send-email-kevin@bracey.fi","subject":"[PATCH v3 5/9] revision.c: Make --full-history consider more merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-05T15:32:53Z","receivedAt":"2013-05-05T15:32:53Z","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 this was consistent with the default behaviour, this could be\nextremely unhelpful when searching detailed history, and could not be\noverridden. For example, if a merge had ignored a change, as if by \"-s\nours\", 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\nFuther, 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\nNow redefine a commit's TREESAME flag to be true only if a commit is\nTREESAME to _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. The clearest\ndifference is that --full-history will show more merges - sufficient to\nensure that -m -p --full-history log searches can really explain every\nchange to the file, including those changes' ultimate fate in merges.\n\nAlso modify 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\nThis fixes some t6111 failures, but creates a couple of new ones -\nwe are now showing some merges that don't need to be shown.\n\nSigned-off-by: Kevin Bracey \n---\n Documentation/rev-list-options.txt | 6 +-\n revision.c | 241 ++++++++++++++++++++++++++++++++-----\n revision.h | 1 +\n t/t6019-rev-list-ancestry-path.sh | 2 +-\n t/t6111-rev-list-treesame.sh | 20 +--\n 5 files changed, 226 insertions(+), 44 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 50bbff7..1dad341 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -409,10 +409,10 @@ parent lines.\n \tthe example, we get\n +\n -----------------------------------------------------------------------\n-\tI A B N D O\n+\tI A B N D O P\n -----------------------------------------------------------------------\n +\n-`P` and `M` were excluded because they are TREESAME to a parent. `E`,\n+`M` was excluded because it is 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@@ -440,7 +440,7 @@ 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`.\n \n In addition to the above settings, you can change whether TREESAME\n affects inclusion:\ndiff --git a/revision.c b/revision.c\nindex a67b615..c88ded8 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -429,10 +429,100 @@ 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+/*\n+ * Must be called immediately after removing the nth_parent from a commit's\n+ * parent list, if we are maintaining the per-parent treesame[] decoration.\n+ * This does not recalculate the master TREESAME flag - update_treesame()\n+ * should be called to update it after a sequence of treesame[] modifications\n+ * that may have affected it.\n+ */\n+static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned nth_parent)\n+{\n+\tstruct treesame_state *st;\n+\tint old_same;\n+\n+\tif (!commit->parents) {\n+\t\t/*\n+\t\t * Have just removed the only parent from a non-merge.\n+\t\t * Different handling, as we lack decoration.\n+\t\t */\n+\t\tif (nth_parent != 0)\n+\t\t\tdie(\"compact_treesame %u\", nth_parent);\n+\t\told_same = !!(commit->object.flags & TREESAME);\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\treturn old_same;\n+\t}\n+\n+\tst = lookup_decoration(&revs->treesame, &commit->object);\n+\tif (!st || nth_parent >= st->nparents)\n+\t\tdie(\"compact_treesame %u\", nth_parent);\n+\n+\told_same = st->treesame[nth_parent];\n+\tmemmove(st->treesame + nth_parent,\n+\t\tst->treesame + nth_parent + 1,\n+\t\tst->nparents - nth_parent - 1);\n+\n+\t/*\n+\t * If we've just become a non-merge commit, update TREESAME\n+\t * immediately, and remove the no-longer-needed decoration.\n+\t * If still a merge, defer update until update_treesame().\n+\t */\n+\tif (--st->nparents == 1) {\n+\t\tif (commit->parents->next)\n+\t\t\tdie(\"compact_treesame parents mismatch\");\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\tfree(add_decoration(&revs->treesame, &commit->object, NULL));\n+\t}\n+\n+\treturn old_same;\n+}\n+\n+static unsigned update_treesame(struct rev_info *revs, struct commit *commit)\n+{\n+\tif (commit->parents && commit->parents->next) {\n+\t\tunsigned n;\n+\t\tstruct treesame_state *st;\n+\n+\t\tst = lookup_decoration(&revs->treesame, &commit->object);\n+\t\tif (!st)\n+\t\t\tdie(\"update_treesame %s\", sha1_to_hex(commit->object.sha1));\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;\n \n \t/*\n \t * If we don't do pruning, everything is interesting\n@@ -456,25 +546,43 @@ 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, nth_parent = 0;\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 * This our second loop iteration - so we now know\n+\t\t\t * we're dealing with a merge.\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 will remain a potentially-simplifiable\n+\t\t\t * merge, remember per-parent treesame if needed.\n+\t\t\t * Initialise the array with the comparison from our\n+\t\t\t * first iteration.\n+\t\t\t */\n+\t\t\tif (revs->treesame.name &&\n+\t\t\t !revs->simplify_history &&\n+\t\t\t !(commit->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+\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 +590,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 +620,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@@ -1930,28 +2038,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 +2083,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-checking only */\n+\tint orig_cnt = commit_list_count(commit->parents);\n+\tint cnt = commit_list_count(h);\n+\n+\t/*\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} else {\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 commit_list **pp, *p;\n+\tint nth_parent, removed = 0;\n+\n+\tpp = &commit->parents;\n+\tnth_parent = 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\t*pp = p->next;\n+\t\t\tfree(p);\n+\t\t\tremoved++;\n+\t\t\tcompact_treesame(revs, commit, nth_parent);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tpp = &p->next;\n+\t\tnth_parent++;\n+\t}\n+\n+\t/* Removing parents can only increase TREESAMEness */\n+\tif (removed && !(commit->object.flags & TREESAME))\n+\t\tupdate_treesame(revs, commit);\n+\n+\treturn nth_parent;\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 +2191,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 any way - 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 +2205,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\tcnt = remove_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@@ -2159,6 +2336,10 @@ int prepare_revision_walk(struct rev_info *revs)\n \tif (!revs->leak_pending)\n \t\tfree(list);\n \n+\t/* Signal whether we need per-parent treesame decoration */\n+\tif (revs->simplify_merges)\n+\t\trevs->treesame.name = \"treesame\";\n+\n \tif (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)\n \t\tcommit_list_sort_by_date(&revs->commits);\n \tif (revs->no_walk)\n@@ -2218,7 +2399,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;\ndiff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh\nindex 86ef908..ebe79ac 100755\n--- a/t/t6019-rev-list-ancestry-path.sh\n+++ b/t/t6019-rev-list-ancestry-path.sh\n@@ -81,7 +81,7 @@ test_expect_success 'rev-list G..M -- G.t' '\n \ttest_cmp expect actual\n '\n \n-test_expect_failure 'rev-list --ancestry-path G..M -- G.t' '\n+test_expect_success 'rev-list --ancestry-path G..M -- G.t' '\n \tfor c in H J L; do echo $c; done >expect &&\n \tgit rev-list --ancestry-path --format=%s G..M -- G.t |\n \tsed -e \"/^commit /d\" |\ndiff --git a/t/t6111-rev-list-treesame.sh b/t/t6111-rev-list-treesame.sh\nindex 602c02d..efc2442 100755\n--- a/t/t6111-rev-list-treesame.sh\n+++ b/t/t6111-rev-list-treesame.sh\n@@ -102,9 +102,9 @@ check_result 'M L K J I H G F E D C B A'\n check_result 'M H L K J I G E F D C B A' --topo-order\n check_result 'M L H B A' -- file\n check_result 'M L H B A' --parents -- file\n-check_outcome failure 'M L J I H G F D B A' --full-history -- file # drops G\n+check_result 'M L J I H G F D B A' --full-history -- file\n check_result 'M L K J I H G F D B A' --full-history --parents -- file\n-check_outcome failure 'M H L J I G F B A' --simplify-merges -- file # drops G\n+check_result 'M H L J I G F B A' --simplify-merges -- file\n check_result 'M L K G F D B A' --first-parent\n check_result 'M L G F B A' --first-parent -- file\n \n@@ -113,11 +113,11 @@ check_result 'M L K J I H G E' F..M\n check_result 'M H L K J I G E' F..M --topo-order\n check_result 'M L H' F..M -- file\n check_result 'M L H' F..M --parents -- file # L+H's parents rewritten to B, so more useful than it may seem\n-check_outcome failure 'M L J I H G' F..M --full-history -- file # drops G\n+check_result 'M L J I H G' F..M --full-history -- file\n check_result 'M L K J I H G' F..M --full-history --parents -- file\n-check_outcome failure 'M H L J I G' F..M --simplify-merges -- file # drops G\n+check_result 'M H L J I G' F..M --simplify-merges -- file\n check_result 'M L K J I H G' F..M --ancestry-path\n-check_outcome failure 'M L J I H G' F..M --ancestry-path -- file # drops G\n+check_result 'M L J I H G' F..M --ancestry-path -- file\n check_result 'M L K J I H G' F..M --ancestry-path --parents -- file\n check_result 'M H L J I G' F..M --ancestry-path --simplify-merges -- file\n check_result 'M L K G' F..M --first-parent\n@@ -126,7 +126,7 @@ check_result 'M L G' F..M --first-parent -- file\n # Note that G is pruned when E is the bottom, even if it's the same commit list\n # If we want history since E, then we're quite happy to ignore G that took E.\n check_result 'M L K J I H G' E..M --ancestry-path\n-check_result 'M L J I H' E..M --ancestry-path -- file\n+check_outcome failure 'M L J I H' E..M --ancestry-path -- file # includes G\n check_outcome failure 'M L K J I H' E..M --ancestry-path --parents -- file\n check_outcome failure 'M H L J I' E..M --ancestry-path --simplify-merges -- file # includes G\n \n@@ -149,13 +149,13 @@ check_result 'M H L J I' G..M --ancestry-path --simplify-merges -- file\n # But --full-history shouldn't drop D on its own - without simplification,\n # we can't decide if the merge from INTERESTING commit C was sensible.\n check_result 'F D C' B..F\n-check_result 'F' B..F -- file\n+check_outcome failure 'F' B..F -- file # includes D\n check_outcome failure 'F' B..F --parents -- file # includes D\n-check_outcome failure 'F D' B..F --full-history -- file # drops D prematurely\n+check_result 'F D' B..F --full-history -- file\n check_result 'F D' B..F --full-history --parents -- file\n check_result 'F' B..F --simplify-merges -- file\n check_result 'F D' B..F --ancestry-path\n-check_result 'F' B..F --ancestry-path -- file\n+check_outcome failure 'F' B..F --ancestry-path -- file # includes D\n check_outcome failure 'F' B..F --ancestry-path --parents -- file # includes D\n check_outcome failure 'F' B..F --ancestry-path --simplify-merges -- file # includes D\n check_result 'F D' B..F --first-parent\n@@ -170,7 +170,7 @@ check_outcome failure 'F D B' C..F --full-history -- file # drops D\n check_result 'F D B' C..F --full-history --parents -- file\n check_result 'F D B' C..F --simplify-merges -- file\n check_result 'F D' C..F --ancestry-path\n-check_outcome failure 'F D' C..F --ancestry-path -- file # drops D\n+check_result 'F D' C..F --ancestry-path -- file\n check_result 'F D' C..F --ancestry-path --parents -- file\n check_result 'F D' C..F --ancestry-path --simplify-merges -- file\n check_result 'F D B' C..F --first-parent\n-- \n1.8.3.rc0.28.g682c2d9\n"},{"id":"216448","messageId":"1367767977-14513-7-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":"1367767977-14513-1-git-send-email-kevin@bracey.fi","subject":"[PATCH v3 6/9] t6012: update test for tweaked full-history traversal","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-05T15:32:54Z","receivedAt":"2013-05-05T15:32:54Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"From: Junio C Hamano \n\nSigned-off-by: Junio C Hamano \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 \n---\n Documentation/rev-list-options.txt | 3 +-\n revision.c | 69 ++++++++++++++++++++++++++++++++++++++\n t/t6111-rev-list-treesame.sh | 2 +-\n 3 files changed, 72 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 1dad341..e23bdb0 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -471,7 +471,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 c88ded8..7535757 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2119,6 +2119,73 @@ static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)\n \treturn marked;\n }\n \n+/*\n+ * Awkward naming - this means one parent we are TREESAME to.\n+ * cf mark_treesame_root_parents: root parents that are TREESAME (to an\n+ * empty tree). Better name suggestions?\n+ */\n+static int leave_one_treesame_to_parent(struct rev_info *revs, struct commit *commit)\n+{\n+\tstruct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);\n+\tstruct commit *unmarked = NULL, *marked = NULL;\n+\tstruct commit_list *p;\n+\tunsigned n;\n+\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 (!marked)\n+\t\t\t\t\tmarked = p->item;\n+\t\t\t} else {\n+\t\t\t\tif (!unmarked) {\n+\t\t\t\t\tunmarked = 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/*\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. This is the\n+\t * parent that the default simplify_history==1 scan would have followed,\n+\t * and it doesn't make sense to omit that path when asking for a\n+\t * simplified full history. Retaining it improves the chances of\n+\t * understanding odd missed merges that took an old version of a file.\n+\t *\n+\t * Example:\n+\t *\n+\t * I---------X A modified the file, but mainline merge X used\n+\t * \\ / \"-s ours\", so took the version from I. X is\n+\t * `--A--' TREESAME to I and !TREESAME to A.\n+\t *\n+\t * Default log from X would produce \"I\". Without this check,\n+\t * --full-history --simplify-merges would produce \"I-A-X\", showing\n+\t * the merge commit X and that it changed A, but not making clear that\n+\t * it had just taken the I version. With this check, the topology above\n+\t * is retained.\n+\t *\n+\t * Note that it is possible that the simplification chooses a different\n+\t * TREESAME parent from the default, in which case this test doesn't\n+\t * activate, and we _do_ drop the default parent. Example:\n+\t *\n+\t * I------X A modified the file, but it was reverted in B,\n+\t * \\ / meaning mainline merge X is TREESAME to both\n+\t * A--B parents.\n+\t *\n+\t * Default log would produce \"I\" by following the first parent;\n+\t * --full-history --simplify-merges will produce \"I-A-B\". But this is a\n+\t * reasonable result - it presents a logical full history leading from\n+\t * I to X, and X is not an important merge.\n+\t */\n+\tif (!unmarked && marked) {\n+\t\tmarked->object.flags &= ~TMP_MARK;\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int remove_marked_parents(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list **pp, *p;\n@@ -2222,6 +2289,8 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\n \tif (1 < cnt) {\n \t\tint marked = mark_redundant_parents(revs, commit);\n \t\tif (marked)\n+\t\t\tmarked -= leave_one_treesame_to_parent(revs, commit);\n+\t\tif (marked)\n \t\t\tcnt = remove_marked_parents(revs, commit);\n \t}\n \ndiff --git a/t/t6111-rev-list-treesame.sh b/t/t6111-rev-list-treesame.sh\nindex efc2442..5cc0c34 100755\n--- a/t/t6111-rev-list-treesame.sh\n+++ b/t/t6111-rev-list-treesame.sh\n@@ -104,7 +104,7 @@ check_result 'M L H B A' -- file\n check_result 'M L H B A' --parents -- file\n check_result 'M L J I H G F D B A' --full-history -- file\n check_result 'M L K J I H G F D B A' --full-history --parents -- file\n-check_result 'M H L J I G F B A' --simplify-merges -- file\n+check_result 'M H L J I G F B A' --simplify-merges -- file # should check that G has parent B\n check_result 'M L K G F D B A' --first-parent\n check_result 'M L G F B A' --first-parent -- file\n \n-- \n1.8.3.rc0.28.g682c2d9\n"},{"id":"216453","messageId":"1367767977-14513-9-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":"1367767977-14513-1-git-send-email-kevin@bracey.fi","subject":"[PATCH v3 8/9] simplify-merges: drop merge from irrelevant side branch","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-05T15:32:56Z","receivedAt":"2013-05-05T15:32:56Z","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 | 34 +++++++++++++++++++++-------------\n revision.c | 26 +++++++++++++++++++++++++-\n t/t6012-rev-list-simplify.sh | 2 +-\n 3 files changed, 47 insertions(+), 15 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex e23bdb0..b7fbc80 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@@ -369,6 +369,10 @@ each merge. The commits are:\n * `E` changes `quux` to \"xyzzy\", and its merge `P` combines the\n strings to \"quux xyzzy\". `P` is TREESAME to `O`, but not to `E`.\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 `P`, but not to `Y`.\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@@ -409,7 +413,7 @@ parent lines.\n \tthe example, we get\n +\n -----------------------------------------------------------------------\n-\tI A B N D O P\n+\tI A B N D O P Q\n -----------------------------------------------------------------------\n +\n `M` was excluded because it is TREESAME to both parents. `E`,\n@@ -430,7 +434,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@@ -440,7 +444,7 @@ 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`.\n+`N`, and `X`, `Y` and `Q`.\n \n In addition to the above settings, you can change whether TREESAME\n affects inclusion:\n@@ -470,9 +474,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@@ -490,7 +494,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@@ -498,6 +502,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 7535757..20c7058 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2119,6 +2119,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 /*\n * Awkward naming - this means one parent we are TREESAME to.\n * cf mark_treesame_root_parents: root parents that are TREESAME (to an\n@@ -2284,10 +2300,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\tmarked -= leave_one_treesame_to_parent(revs, commit);\n \t\tif (marked)\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.3.rc0.28.g682c2d9\n"},{"id":"216455","messageId":"1367767977-14513-10-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":"1367767977-14513-1-git-send-email-kevin@bracey.fi","subject":"[PATCH v3 9/9] revision.c: discount side branches when computing TREESAME","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-05T15:32:57Z","receivedAt":"2013-05-05T15:32:57Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"Add a BOTTOM flag to commit objects, and use it to define priority for\npruning. Priority commits are those that are !UNINTERESTING or BOTTOM,\nand this allows us to identify irrelevant side branches (UNINTERESTING\n&& !BOTTOM).\n\nIf a merge has priority parents, and it is TREESAME to them, then do\nnot let non-priority parents cause the merge to be treated as\n!TREESAME.\n\nWhen considering simplification, don't always include all merges -\nmerges with exactly 1 priority parent can be simplified, if TREESAME\naccording to the above rule.\n\nThese two changes greatly increase simplification in limited revision\nlists - irrelevant merges from unlisted commits can be omitted.\n\nSigned-off-by: Kevin Bracey \n---\n revision.c | 201 ++++++++++++++++++++++++++++++++------\n revision.h | 3 +-\n t/t6019-rev-list-ancestry-path.sh | 12 ++-\n t/t6111-rev-list-treesame.sh | 22 ++---\n 4 files changed, 195 insertions(+), 43 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 20c7058..99a3432 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -333,6 +333,76 @@ static int everybody_uninteresting(struct commit_list *orig)\n }\n \n /*\n+ * A definition of \"priority\" commit that we can use to simplify limited graphs\n+ * by eliminating side branches.\n+ *\n+ * A \"priority\" commit is one that is !UNINTERESTING (ie we are including it\n+ * in our list), or that is a specified BOTTOM commit. Then after computing\n+ * a limited list, during processing we can generally ignore boundary merges\n+ * coming from outside the graph, (ie from non-priority parents), and treat\n+ * those merges as if they were single-parent. TREESAME is defined to consider\n+ * only priority parents, if any. If we are TREESAME to our on-graph parents,\n+ * we don't care if we were !TREESAME to non-graph parents.\n+ *\n+ * Including bottom commits in \"priority\" ensures that a limited graph's\n+ * connection to the actual bottom commit is not viewed as an uninteresting\n+ * side branch, but treated as part of the graph. For example:\n+ *\n+ * ....Z...A---X---o---o---B\n+ * . /\n+ * W---Y\n+ *\n+ * When computing \"A..B\", the A-X connection is at least as important as\n+ * Y-X, despite A being flagged UNINTERESTING.\n+ *\n+ * And when computing --ancestry-path \"A..B\", the A-X connection is more\n+ * important than Y-X, despite both A and Y being flagged UNINTERESTING.\n+ */\n+static inline int priority_commit(struct commit *commit)\n+{\n+\treturn (commit->object.flags & (UNINTERESTING | BOTTOM)) != UNINTERESTING;\n+}\n+\n+/*\n+ * Return a single priority commit from a parent list. If we are a TREESAME\n+ * commit, and this selects one of our parents, then we can safely simplify to\n+ * that parent.\n+ *\n+ * For 1-parent commits, or if first-parent-only, then this returns the only\n+ * parent. TREESAME will have been set purely on that parent.\n+ *\n+ * For multi-parent commits, identify a sole priority parent, if any.\n+ * If we have only one priority parent, then TREESAME will be set purely\n+ * with regard to that parent, and we can choose simplification appropriately.\n+ *\n+ * If we have more than one priority parent, or no priority parents\n+ * (and multiple non-priority ones), then we can't select a parent here and\n+ * return NULL.\n+ */\n+static struct commit *priority_select_parent(struct rev_info *revs, struct commit_list *orig)\n+{\n+\tstruct commit_list *list = orig;\n+\tstruct commit *priority = NULL;\n+\n+\tif (!orig)\n+\t\treturn NULL;\n+\n+\tif (revs->first_parent_only || !orig->next)\n+\t\treturn orig->item;\n+\n+\twhile (list) {\n+\t\tstruct commit *commit = list->item;\n+\t\tlist = list->next;\n+\t\tif (priority_commit(commit)) {\n+\t\t\tif (priority)\n+\t\t\t\treturn NULL;\n+\t\t\tpriority = commit;\n+\t\t}\n+\t}\n+\treturn priority;\n+}\n+\n+/*\n * The goal is to get REV_TREE_NEW as the result only if the\n * diff consists of all '+' (and no other changes), REV_TREE_OLD\n * if the whole diff is removal of old data, and otherwise\n@@ -502,27 +572,52 @@ static unsigned update_treesame(struct rev_info *revs, struct commit *commit)\n \tif (commit->parents && commit->parents->next) {\n \t\tunsigned n;\n \t\tstruct treesame_state *st;\n+\t\tstruct commit_list *p;\n+\t\tunsigned priority_parents;\n+\t\tunsigned priority_change, nonpriority_change;\n \n \t\tst = lookup_decoration(&revs->treesame, &commit->object);\n \t\tif (!st)\n \t\t\tdie(\"update_treesame %s\", sha1_to_hex(commit->object.sha1));\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\tpriority_parents = 0;\n+\t\tpriority_change = nonpriority_change = 0;\n+\t\tfor (p = commit->parents, n = 0; p; n++, p = p->next) {\n+\t\t\tif (priority_commit(p->item)) {\n+\t\t\t\tpriority_change |= !st->treesame[n];\n+\t\t\t\tpriority_parents++;\n+\t\t\t} else\n+\t\t\t\tnonpriority_change |= !st->treesame[n];\n \t\t}\n+\t\tif (priority_parents ? priority_change : nonpriority_change)\n+\t\t\tcommit->object.flags &= ~TREESAME;\n+\t\telse\n+\t\t\tcommit->object.flags |= TREESAME;\n \t}\n \n \treturn commit->object.flags & TREESAME;\n }\n \n+static inline int limiting_can_increase_treesame(const struct rev_info *revs)\n+{\n+\t/*\n+\t * TREESAME is irrelevant unless prune && dense;\n+\t * if simplify_history is set, we can't have a mixture of TREESAME and\n+\t * !TREESAME INTERESTING parents (and we don't have treesame[]\n+\t * decoration anyway);\n+\t * if first_parent_only is set, then the TREESAME flag is locked\n+\t * against the first parent (and again we lack treesame[] decoration).\n+\t */\n+\treturn revs->prune && revs->dense &&\n+\t !revs->simplify_history &&\n+\t !revs->first_parent_only;\n+}\n+\n static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list **pp, *parent;\n \tstruct treesame_state *ts = NULL;\n-\tint tree_changed = 0, nth_parent;\n+\tint priority_change = 0, nonpriority_change = 0;\n+\tint priority_parents, nth_parent;\n \n \t/*\n \t * If we don't do pruning, everything is interesting\n@@ -546,10 +641,12 @@ 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-\tfor (pp = &commit->parents, nth_parent = 0;\n+\tfor (pp = &commit->parents, nth_parent = 0, priority_parents = 0;\n \t (parent = *pp) != NULL;\n \t pp = &parent->next, nth_parent++) {\n \t\tstruct commit *p = parent->item;\n+\t\tif (priority_commit(p))\n+\t\t\tpriority_parents++;\n \n \t\tif (nth_parent == 1) {\n \t\t\t/*\n@@ -573,7 +670,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t\t !revs->simplify_history &&\n \t\t\t !(commit->object.flags & UNINTERESTING)) {\n \t\t\t\tts = initialise_treesame(revs, commit);\n-\t\t\t\tif (!tree_changed)\n+\t\t\t\tif (!(nonpriority_change || priority_change))\n \t\t\t\t\tts->treesame[0] = 1;\n \t\t\t}\n \t\t}\n@@ -583,7 +680,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\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\tif (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {\n+\t\t\tif (!revs->simplify_history || !priority_commit(p)) {\n \t\t\t\t/* Even if a merge with an uninteresting\n \t\t\t\t * side branch brought the entire change\n \t\t\t\t * we are interested in, we do not want\n@@ -619,14 +716,27 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t/* fallthrough */\n \t\tcase REV_TREE_OLD:\n \t\tcase REV_TREE_DIFFERENT:\n-\t\t\ttree_changed = 1;\n+\t\t\tif (priority_commit(p))\n+\t\t\t\tpriority_change = 1;\n+\t\t\telse\n+\t\t\t\tnonpriority_change = 1;\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)\n-\t\treturn;\n-\tcommit->object.flags |= TREESAME;\n+\n+\t/*\n+\t * TREESAME is straightforward for single-parent commits. For merge\n+\t * commits, it is most useful to define it so that \"non-priority\"\n+\t * parents cannot make us !TREESAME - if we have any priority\n+\t * parents, then we only consider TREESAMEness with respect to them,\n+\t * allowing irrelevant merges from uninteresting branches to be\n+\t * simplified away. Only if we have only nonpriority parents do we\n+\t * base TREESAME on them. Note that this logic is replicated in\n+\t * update_treesame, which should be kept in sync.\n+\t */\n+\tif (priority_parents ? !priority_change : !nonpriority_change)\n+\t\tcommit->object.flags |= TREESAME;\n }\n \n static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head,\n@@ -1002,6 +1112,18 @@ static int limit_list(struct rev_info *revs)\n \t\tfree_commit_list(bottom);\n \t}\n \n+\t/*\n+\t * Check if any commits have become TREESAME by some of their parents\n+\t * becoming UNINTERESTING.\n+\t */\n+\tif (limiting_can_increase_treesame(revs))\n+\t\tfor (list = newlist; list; list = list->next) {\n+\t\t\tstruct commit *c = list->item;\n+\t\t\tif (c->object.flags & (UNINTERESTING | TREESAME))\n+\t\t\t\tcontinue;\n+\t\t\tupdate_treesame(revs, c);\n+\t\t}\n+\n \trevs->commits = newlist;\n \treturn 0;\n }\n@@ -1015,6 +1137,16 @@ static void add_rev_cmdline(struct rev_info *revs,\n \tstruct rev_cmdline_info *info = &revs->cmdline;\n \tint nr = info->nr;\n \n+\t/*\n+\t * Total hack, but at least doing it here means we're consistent\n+\t * with collect_bottom_commits(). But if we just flagged BOTTOM\n+\t * commits before this, could we ditch this entire function?\n+\t */\n+\tif (item->type == OBJ_COMMIT && (flags & UNINTERESTING)) {\n+\t\titem->flags |= BOTTOM;\n+\t\tflags |= BOTTOM;\n+\t}\n+\n \tALLOC_GROW(info->rev, nr + 1, info->alloc);\n \tinfo->rev[nr].item = item;\n \tinfo->rev[nr].name = name;\n@@ -2233,6 +2365,7 @@ static int remove_marked_parents(struct rev_info *revs, struct commit *commit)\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+\tstruct commit *parent;\n \tstruct merge_simplify_state *st, *pst;\n \tint cnt;\n \n@@ -2321,19 +2454,20 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c\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 simplify to more than one commit\n+\t * merge and its parents don't simplify to one priority commit\n \t * (the first two cases are already handled at the beginning of\n \t * this function).\n \t *\n-\t * Otherwise, it simplifies to what its sole parent simplifies to.\n+\t * Otherwise, it simplifies to what its sole priority parent\n+\t * simplifies to.\n \t */\n \tif (!cnt ||\n \t (commit->object.flags & UNINTERESTING) ||\n \t !(commit->object.flags & TREESAME) ||\n-\t (1 < cnt))\n+\t (parent = priority_select_parent(revs, commit->parents)) == NULL)\n \t\tst->simplified = commit;\n \telse {\n-\t\tpst = locate_simplify_state(revs, commit->parents->item);\n+\t\tpst = locate_simplify_state(revs, parent);\n \t\tst->simplified = pst->simplified;\n \t}\n \treturn tail;\n@@ -2430,7 +2564,8 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tfree(list);\n \n \t/* Signal whether we need per-parent treesame decoration */\n-\tif (revs->simplify_merges)\n+\tif (revs->simplify_merges ||\n+\t (revs->limited && limiting_can_increase_treesame(revs)))\n \t\trevs->treesame.name = \"treesame\";\n \n \tif (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)\n@@ -2464,15 +2599,15 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t\tif (!revs->limited)\n \t\t\tif (add_parents_to_list(revs, p, &revs->commits, &cache) < 0)\n \t\t\t\treturn rewrite_one_error;\n-\t\tif (p->parents && p->parents->next)\n-\t\t\treturn rewrite_one_ok;\n \t\tif (p->object.flags & UNINTERESTING)\n \t\t\treturn rewrite_one_ok;\n \t\tif (!(p->object.flags & TREESAME))\n \t\t\treturn rewrite_one_ok;\n \t\tif (!p->parents)\n \t\t\treturn rewrite_one_noparents;\n-\t\t*pp = p->parents->item;\n+\t\tif ((p = priority_select_parent(revs, p->parents)) == NULL)\n+\t\t\treturn rewrite_one_ok;\n+\t\t*pp = p;\n \t}\n }\n \n@@ -2616,10 +2751,7 @@ enum commit_action get_commit_action(struct rev_info *revs, struct commit *commi\n \tif (revs->min_age != -1 && (commit->date > revs->min_age))\n \t\treturn commit_ignore;\n \tif (revs->min_parents || (revs->max_parents >= 0)) {\n-\t\tint n = 0;\n-\t\tstruct commit_list *p;\n-\t\tfor (p = commit->parents; p; p = p->next)\n-\t\t\tn++;\n+\t\tint n = commit_list_count(commit->parents);\n \t\tif ((n < revs->min_parents) ||\n \t\t ((revs->max_parents >= 0) && (n > revs->max_parents)))\n \t\t\treturn commit_ignore;\n@@ -2629,12 +2761,23 @@ enum commit_action get_commit_action(struct rev_info *revs, struct commit *commi\n \tif (revs->prune && revs->dense) {\n \t\t/* Commit without changes? */\n \t\tif (commit->object.flags & TREESAME) {\n+\t\t\tint n;\n+\t\t\tstruct commit_list *p;\n \t\t\t/* drop merges unless we want parenthood */\n \t\t\tif (!want_ancestry(revs))\n \t\t\t\treturn commit_ignore;\n-\t\t\t/* non-merge - always ignore it */\n-\t\t\tif (!commit->parents || !commit->parents->next)\n-\t\t\t\treturn commit_ignore;\n+\t\t\t/*\n+\t\t\t * If we want ancestry, then need to keep any merges\n+\t\t\t * between priority commits to tie together topology.\n+\t\t\t * For consistency with TREESAME and simplification.\n+\t\t\t * use \"priority\" here rather than just INTERESTING,\n+\t\t\t * to treat bottom commit(s) as part of the topology.\n+\t\t\t */\n+\t\t\tfor (n = 0, p = commit->parents; p; p = p->next)\n+\t\t\t\tif (priority_commit(p->item))\n+\t\t\t\t\tif (++n >= 2)\n+\t\t\t\t\t\treturn commit_show;\n+\t\t\treturn commit_ignore;\n \t\t}\n \t}\n \treturn commit_show;\ndiff --git a/revision.h b/revision.h\nindex 1abe57b..765630a 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -15,7 +15,8 @@\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n #define PATCHSAME\t(1u<<9)\n-#define ALL_REV_FLAGS\t((1u<<10)-1)\n+#define BOTTOM\t\t(1u<<10)\n+#define ALL_REV_FLAGS\t((1u<<11)-1)\n \n #define DECORATE_SHORT_REFS\t1\n #define DECORATE_FULL_REFS\t2\ndiff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh\nindex ebe79ac..c5a412c 100755\n--- a/t/t6019-rev-list-ancestry-path.sh\n+++ b/t/t6019-rev-list-ancestry-path.sh\n@@ -15,7 +15,8 @@ test_description='--ancestry-path'\n # --ancestry-path D..M -- M.t == M\n #\n # G..M -- G.t == [nothing - was dropped in \"-s ours\" merge L]\n-# --ancestry-path G..M -- G.t == H J L\n+# --ancestry-path G..M -- G.t == L\n+# --ancestry-path --simplify-merges G^..M -- G.t == G L\n \n . ./test-lib.sh\n \n@@ -82,8 +83,15 @@ test_expect_success 'rev-list G..M -- G.t' '\n '\n \n test_expect_success 'rev-list --ancestry-path G..M -- G.t' '\n-\tfor c in H J L; do echo $c; done >expect &&\n+\techo L >expect &&\n \tgit rev-list --ancestry-path --format=%s G..M -- G.t |\n+\tsed -e \"/^commit /d\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'rev-list --ancestry-path --simplify-merges G^..M -- G.t' '\n+\tfor c in G L; do echo $c; done >expect &&\n+\tgit rev-list --ancestry-path --simplify-merges --format=%s G^..M -- G.t |\n \tsed -e \"/^commit /d\" |\n \tsort >actual &&\n \ttest_cmp expect actual\ndiff --git a/t/t6111-rev-list-treesame.sh b/t/t6111-rev-list-treesame.sh\nindex 5cc0c34..689d357 100755\n--- a/t/t6111-rev-list-treesame.sh\n+++ b/t/t6111-rev-list-treesame.sh\n@@ -126,16 +126,16 @@ check_result 'M L G' F..M --first-parent -- file\n # Note that G is pruned when E is the bottom, even if it's the same commit list\n # If we want history since E, then we're quite happy to ignore G that took E.\n check_result 'M L K J I H G' E..M --ancestry-path\n-check_outcome failure 'M L J I H' E..M --ancestry-path -- file # includes G\n-check_outcome failure 'M L K J I H' E..M --ancestry-path --parents -- file\n-check_outcome failure 'M H L J I' E..M --ancestry-path --simplify-merges -- file # includes G\n+check_result 'M L J I H' E..M --ancestry-path -- file\n+check_result 'M L K J I H' E..M --ancestry-path --parents -- file\n+check_result 'M H L J I' E..M --ancestry-path --simplify-merges -- file\n \n # Should still be able to ignore I-J branch in simple log, despite limiting\n # to G.\n check_result 'M L K J I H' G..M\n check_result 'M H L K J I' G..M --topo-order\n-check_outcome failure 'M L H' G..M -- file # includes J I\n-check_outcome failure 'M L H' G..M --parents -- file # includes J I\n+check_result 'M L H' G..M -- file\n+check_result 'M L H' G..M --parents -- file\n check_result 'M L J I H' G..M --full-history -- file\n check_result 'M L K J I H' G..M --full-history --parents -- file\n check_result 'M H L J I' G..M --simplify-merges -- file\n@@ -149,15 +149,15 @@ check_result 'M H L J I' G..M --ancestry-path --simplify-merges -- file\n # But --full-history shouldn't drop D on its own - without simplification,\n # we can't decide if the merge from INTERESTING commit C was sensible.\n check_result 'F D C' B..F\n-check_outcome failure 'F' B..F -- file # includes D\n-check_outcome failure 'F' B..F --parents -- file # includes D\n+check_result 'F' B..F -- file\n+check_result 'F' B..F --parents -- file\n check_result 'F D' B..F --full-history -- file\n check_result 'F D' B..F --full-history --parents -- file\n check_result 'F' B..F --simplify-merges -- file\n check_result 'F D' B..F --ancestry-path\n-check_outcome failure 'F' B..F --ancestry-path -- file # includes D\n-check_outcome failure 'F' B..F --ancestry-path --parents -- file # includes D\n-check_outcome failure 'F' B..F --ancestry-path --simplify-merges -- file # includes D\n+check_result 'F' B..F --ancestry-path -- file\n+check_result 'F' B..F --ancestry-path --parents -- file\n+check_result 'F' B..F --ancestry-path --simplify-merges -- file\n check_result 'F D' B..F --first-parent\n check_result 'F' B..F --first-parent -- file\n \n@@ -166,7 +166,7 @@ check_result 'F' B..F --first-parent -- file\n check_result 'F D B' C..F\n check_result 'F B' C..F -- file\n check_result 'F B' C..F --parents -- file\n-check_outcome failure 'F D B' C..F --full-history -- file # drops D\n+check_result 'F D B' C..F --full-history -- file\n check_result 'F D B' C..F --full-history --parents -- file\n check_result 'F D B' C..F --simplify-merges -- file\n check_result 'F D' C..F --ancestry-path\n-- \n1.8.3.rc0.28.g682c2d9\n"},{"id":"216541","messageId":"1367859096-25909-1-git-send-email-kevin@bracey.fi","threadId":"33729","inReplyTo":"1367767977-14513-1-git-send-email-kevin@bracey.fi","subject":"[PATCH v3 10/9] revision.c: treat A...B merge bases as if manually specified","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-06T16:51:36Z","receivedAt":"2013-05-06T16:51:36Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"The documentation assures users that \"A...B\" is defined as 'r1 r2 --not\n$(git merge-base --all r1 r2)'. This isn't in fact quite true, because\nthe calculated merge bases are not sent to add_rev_cmdline().\n\nPreviously, the effect was pretty minor - all that I can think of is\nthat \"git rev-list --ancestry-path A B ^AB_base\" works, but \"git\nrev-list --ancestry-path A...B\" fails with a \"no bottom commits\" error.\n\nBut now that all history walking cares about bottom commits, this\nfailure to note the merge bases as bottoms can lead to worse results for\n\"A...B\" compared to \"A B ^AB_base\".\n\nSo ensure that the calculated merge bases are sent to add_rev_cmdline(),\nflagged as 'REV_CMD_MERGE_BASE'.\n\nSigned-off-by: Kevin Bracey \n---\n revision.c | 9 +++++++--\n revision.h | 2 ++\n t/t6111-rev-list-treesame.sh | 4 ++++\n 3 files changed, 13 insertions(+), 2 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 99a3432..aad16a6 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1305,12 +1305,16 @@ void init_revisions(struct rev_info *revs, const char *prefix)\n \n static void add_pending_commit_list(struct rev_info *revs,\n struct commit_list *commit_list,\n+ int whence,\n unsigned int flags)\n {\n \twhile (commit_list) {\n \t\tstruct object *object = &commit_list->item->object;\n+\t\tconst char *sha1 = sha1_to_hex(object->sha1);\n \t\tobject->flags |= flags;\n-\t\tadd_pending_object(revs, object, sha1_to_hex(object->sha1));\n+\t\tif (whence != REV_CMD_NONE)\n+\t\t\tadd_rev_cmdline(revs, object, sha1, whence, flags);\n+\t\tadd_pending_object(revs, object, sha1);\n \t\tcommit_list = commit_list->next;\n \t}\n }\n@@ -1332,7 +1336,7 @@ static void prepare_show_merge(struct rev_info *revs)\n \tadd_pending_object(revs, &head->object, \"HEAD\");\n \tadd_pending_object(revs, &other->object, \"MERGE_HEAD\");\n \tbases = get_merge_bases(head, other, 1);\n-\tadd_pending_commit_list(revs, bases, UNINTERESTING);\n+\tadd_pending_commit_list(revs, bases, REV_CMD_MERGE_BASE, UNINTERESTING);\n \tfree_commit_list(bases);\n \thead->object.flags |= SYMMETRIC_LEFT;\n \n@@ -1420,6 +1424,7 @@ int handle_revision_arg(const char *arg_, struct rev_info *revs, int flags, unsi\n \t\t\tif (symmetric) {\n \t\t\t\texclude = get_merge_bases(a, b, 1);\n \t\t\t\tadd_pending_commit_list(revs, exclude,\n+\t\t\t\t\t\t\tREV_CMD_MERGE_BASE,\n \t\t\t\t\t\t\tflags_exclude);\n \t\t\t\tfree_commit_list(exclude);\n \t\t\t\ta_flags = flags | SYMMETRIC_LEFT;\ndiff --git a/revision.h b/revision.h\nindex 765630a..b2ac5a3 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -32,10 +32,12 @@ struct rev_cmdline_info {\n \t\tstruct object *item;\n \t\tconst char *name;\n \t\tenum {\n+\t\t\tREV_CMD_NONE,\n \t\t\tREV_CMD_REF,\n \t\t\tREV_CMD_PARENTS_ONLY,\n \t\t\tREV_CMD_LEFT,\n \t\t\tREV_CMD_RIGHT,\n+\t\t\tREV_CMD_MERGE_BASE,\n \t\t\tREV_CMD_REV\n \t\t} whence;\n \t\tunsigned flags;\ndiff --git a/t/t6111-rev-list-treesame.sh b/t/t6111-rev-list-treesame.sh\nindex 689d357..ded0b1a 100755\n--- a/t/t6111-rev-list-treesame.sh\n+++ b/t/t6111-rev-list-treesame.sh\n@@ -161,6 +161,10 @@ check_result 'F' B..F --ancestry-path --simplify-merges -- file\n check_result 'F D' B..F --first-parent\n check_result 'F' B..F --first-parent -- file\n \n+# E...F should be equivalent to E F ^B, and be able to drop D as above.\n+check_result 'F' E F ^B -- file\n+check_result 'F' E...F -- file\n+\n # Any sort of full history of C..F should show D, as it's the connection to C,\n # and it differs from it.\n check_result 'F D B' C..F\n-- \n1.8.3.rc0.28.g4b02ef5\n"},{"id":"216546","messageId":"7vmws7rjat.fsf@alter.siamese.dyndns.org","threadId":"33729","inReplyTo":"1367767977-14513-4-git-send-email-kevin@bracey.fi","subject":"Re: [PATCH v3 3/9] t6111: new TREESAME test set","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-06T19:37:46Z","receivedAt":"2013-05-06T19:37:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> Some side branching and odd merging to illustrate various flaws in\n> revision list scans, particularly when limiting the list.\n>\n> Many expected failures, which will be gone by the end of the \"history\n> traversal refinements\" series.\n>\n> Signed-off-by: Kevin Bracey \n> ---\n> t/t6111-rev-list-treesame.sh | 180 +++++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 180 insertions(+)\n> create mode 100755 t/t6111-rev-list-treesame.sh\n>\n> diff --git a/t/t6111-rev-list-treesame.sh b/t/t6111-rev-list-treesame.sh\n> new file mode 100755\n> index 0000000..602c02d\n> --- /dev/null\n> +++ b/t/t6111-rev-list-treesame.sh\n> @@ -0,0 +1,180 @@\n> +#!/bin/sh\n> +#\n> +# ,---E--. *H----------. * marks !TREESAME parent paths\n> +# / \\ / \\*\n> +# *A--*B---D--*F-*G---------K-*L-*M\n> +# \\ /* \\ /\n> +# `-C-' `-*I-*J\n> +#\n> +# A creates \"file\", B and F change it.\n> +# Odd merge G takes the old version from B.\n> +# I changes it, but J reverts it.\n> +# H and L both change it, and M merges those changes.\n\n... and because J is a revert of I, K ends up merging the same and\nbeing the same with both G and J.\n\n> +test_description='TREESAME and limiting'\n> +\n> +. ./test-lib.sh\n> +\n> +note () {\n> +\tgit tag \"$1\"\n> +}\n> +\n> +unnote () {\n> +\tgit name-rev --tags --stdin | sed -e \"s|$_x40 (tags/\\([^)]*\\)) |\\1 |g\"\n> +}\n> +\n> +test_expect_success setup '\n> +\ttest_commit \"Initial file\" file \"Hi there\" A &&\n> +\tgit branch other-branch &&\n> +\n> +\ttest_commit \"file=Hello\" file \"Hello\" B &&\n> +\tgit branch third-branch &&\n> +\n> +\tgit checkout other-branch &&\n> +\ttest_commit \"Added other\" other \"Hello\" C &&\n> +\n> +\tgit checkout master &&\n> +\ttest_merge D other-branch &&\n> +\n> +\tgit checkout third-branch &&\n> +\ttest_commit \"Third file\" third \"Nothing\" E &&\n> +\n> +\tgit checkout master &&\n> +\ttest_commit \"file=Blah\" file \"Blah\" F &&\n> +\n> +\ttest_tick && git merge --no-commit third-branch &&\n> +\tgit checkout third-branch file &&\n> +\tgit commit &&\n> +\tnote G &&\n> +\tgit branch fiddler-branch &&\n> +\n> +\tgit checkout -b part2-branch &&\n> +\ttest_commit \"file=Part 2\" file \"Part 2\" H &&\n> +\n> +\tgit checkout fiddler-branch &&\n> +\ttest_commit \"Bad commit\" file \"Silly\" I &&\n> +\n> +\ttest_tick && git revert I && note J &&\n> +\n> +\tgit checkout master &&\n> +\ttest_tick && git merge --no-ff fiddler-branch &&\n> +\tnote K\n> +\n> +\ttest_commit \"file=Part 1\" file \"Part 1\" L &&\n> +\n> +\ttest_tick && test_must_fail git merge part2-branch &&\n> +\ttest_commit M file \"Parts 1+2\"\n> +'\n> +\n> +FMT='tformat:%P \t%H | %s'\n> +\n> +# could we soup this up to optionally check parents? So \"(BA)C\" would check\n> +# that C is shown and has parents B A.\n\nSounds like a good thing to do, especially given that some of the\nearlier issues you brought up triggered only when --parents is not\nused, so...\n\nPerhaps something like the attached.\n\n> +check_outcome () {\n> +\toutcome=$1\n> +\tshift\n> +\tfor c in $1\n> +\tdo\n> +\t\techo \"$c\"\n> +\tdone >expect &&\n\nMaybe\n\n\tprintf \"%s\\n\" $1 >expect\n\nis more fashionable these days?\n\n> +# Odd merge G drops a change in F. Important that G is listed in all\n> +# except the most basic list. Achieving this means normal merge D will also be\n> +# shown in normal full-history, as we can't distinguish unless we do a\n> +# simplification pass. After simplification, D is dropped but G remains.\n> +check_result 'M L K J I H G F E D C B A'\n\nI'll read the expectation and comment on them in a separate message.\n\n t/t6111-rev-list-treesame.sh | 30 +++++++++++++++++++++---------\n 1 file changed, 21 insertions(+), 9 deletions(-)\n\ndiff --git a/t/t6111-rev-list-treesame.sh b/t/t6111-rev-list-treesame.sh\nindex 602c02d..f4c9cac 100755\n--- a/t/t6111-rev-list-treesame.sh\n+++ b/t/t6111-rev-list-treesame.sh\n@@ -20,7 +20,7 @@ note () {\n }\n \n unnote () {\n-\tgit name-rev --tags --stdin | sed -e \"s|$_x40 (tags/\\([^)]*\\)) |\\1 |g\"\n+\tgit name-rev --tags --stdin | sed -e \"s|$_x40 (tags/\\([^)]*\\))\\([ \t]\\)|\\1\\2|g\"\n }\n \n test_expect_success setup '\n@@ -66,23 +66,34 @@ test_expect_success setup '\n \ttest_commit M file \"Parts 1+2\"\n '\n \n-FMT='tformat:%P \t%H | %s'\n-\n # could we soup this up to optionally check parents? So \"(BA)C\" would check\n # that C is shown and has parents B A.\n check_outcome () {\n \toutcome=$1\n \tshift\n-\tfor c in $1\n-\tdo\n-\t\techo \"$c\"\n-\tdone >expect &&\n-\tshift &&\n+\n+\tcase \"$1\" in\n+\t*\"(\"*)\n+\t\tFMT=\"%P\t%H | %s\"\n+\t\tmunge_actual=\"\n+\t\t\ts/^\\([^\t]*\\)\t\\([^ ]*\\) .*/(\\1)\\2/\n+\t\t\ts/ //g\n+\t\t\ts/()//\n+\t\t\"\n+\t\t;;\n+\t*)\n+\t\tFMT=\"%H | %s\"\n+\t\tmunge_actual=\"s/^\\([^ ]*\\) .*/\\1/\"\n+\t\t;;\n+\tesac &&\n+\tprintf \"%s\\n\" $1 >expect &&\n+\tshift\n+\n \tparam=\"$*\" &&\n \ttest_expect_$outcome \"log $param\" '\n \t\tgit log --format=\"$FMT\" $param |\n \t\tunnote >actual &&\n-\t\tsed -e \"s/^.*\t\\([^ ]*\\) .*/\\1/\" >check check &&\n \t\ttest_cmp expect check || {\n \t\t\tcat actual\n \t\t\tfalse\n@@ -99,6 +110,7 @@ check_result () {\n # shown in normal full-history, as we can't distinguish unless we do a\n # simplification pass. After simplification, D is dropped but G remains.\n check_result 'M L K J I H G F E D C B A'\n+check_result '(LH)M (K)L (GJ)K (I)J (G)I (G)H (FE)G (D)F (B)E (BC)D (A)C (A)B A'\n check_result 'M H L K J I G E F D C B A' --topo-order\n check_result 'M L H B A' -- file\n check_result 'M L H B A' --parents -- file\n"},{"id":"216548","messageId":"7v1u9jrgl4.fsf@alter.siamese.dyndns.org","threadId":"33729","inReplyTo":"1367767977-14513-4-git-send-email-kevin@bracey.fi","subject":"Re: [PATCH v3 3/9] t6111: new TREESAME test set","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-06T20:36:23Z","receivedAt":"2013-05-06T20:36:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> +# ,---E--. *H----------. * marks !TREESAME parent paths\n> +# / \\ / \\*\n> +# *A--*B---D--*F-*G---------K-*L-*M\n> +# \\ /* \\ /\n> +# `-C-' `-*I-*J\n> +#\n> +# A creates \"file\", B and F change it.\n> +# Odd merge G takes the old version from B.\n> +# I changes it, but J reverts it.\n> +# H and L both change it, and M merges those changes.\n> + ...\n> +# Odd merge G drops a change in F. Important that G is listed in all\n> +# except the most basic list. Achieving this means normal merge D will also be\n> +# shown in normal full-history, as we can't distinguish unless we do a\n> +# simplification pass. After simplification, D is dropped but G remains.\n> +check_result 'M L K J I H G F E D C B A'\n\nOK.\n\n> +check_result 'M H L K J I G E F D C B A' --topo-order\n\nOK.\n\n> +check_result 'M L H B A' -- file\n\nOK.\n\n> +check_result 'M L H B A' --parents -- file\n\nOK.\n\n> +check_outcome failure 'M L J I H G F D B A' --full-history -- file # drops G\n\nThis breaks the promise that full history at least gives a connected\ngraph.\n\n> +check_result 'M L K J I H G F D B A' --full-history --parents -- file\n\nAnd it is saved by --parents; the \"(parents)commit\" notation may\nmake it easier to read the above two tests.\n\n> +check_outcome failure 'M H L J I G F B A' --simplify-merges -- file # drops G\n\nThe hsitory simplify merges gives ought to be a full history that\nkeeps any commit that locally touches the specified path, so keeping\nI and J even though they do not contribute to the end result is\ncorrect. The path in question is the same between G and B, but\nagain, F should be shown because it should be in the full history.\n\nEven though E simplifies down to B, making G a merge between B and F\n(the former is an ancestor of the latter), G is kept, because...?\n\nBecause the path at B and F are different?\n\nI have to wonder what should happen if D makes path different from B,\nand then F makes path the same as B. B and F should still be kept.\n\nSo \"because the path at B and F are different\" is not the reason why\nwe keep G. How do we decide why G must be kept?\n\n> +check_result 'M L K G F D B A' --first-parent\n> +check_result 'M L G F B A' --first-parent -- file\n\nOK.\n\n> +# Check that odd merge G remains shown when F is the bottom.\n\nI did not have a chance to say this when you responded in the\nprevious round with that \"bottom\" thing before you sent this new\nround, but I am not sure if it is a good idea to pay special\nattention to the \"bottom\"-ness. Very often, instead of running \"git\nlog -- path\" and stopping when seeing enough by killing the pager,\npeople run \"git log HEAD~200.. -- path\" to pick \"recent enough\"\ncommits, but the number 200 is very much arbitrary.\n\n> +check_result 'M L K J I H G E' F..M\n\nOK.\n\n> +check_result 'M H L K J I G E' F..M --topo-order\n\nOK. But a note about style: options should come before revision\nranges.\n\n> +check_result 'M L H' F..M -- file\n\nOK. It is still one possible history to explain what we have in the\npath at the end.\n\n> +check_result 'M L H' F..M --parents -- file # L+H's parents rewritten to B, so more useful than it may seem\n\nOK.\n\n> +check_outcome failure 'M L J I H G' F..M --full-history -- file # drops G\n\nG is same as E which is in the graph (F and B are the boundaries of\nthe history, and F is no special than B in that regard). You want\nto show a merge that is different from at least one parent (as\nopposed to showing only when it is different from all parents), so\nyou want to show G. OK.\n\n> +check_result 'M L K J I H G' F..M --full-history --parents -- file\n\nOK.\n\nIt almost makes me suspect that the --full-history option should\nflip revs->rewrite_parents on (but not revs->print_parents, unless\nthe --parents option asks us to) when the option is parsed.\n\n> +check_outcome failure 'M H L J I G' F..M --simplify-merges -- file # drops G\n\nThe same as the \"--full-history without --parents\" before.\n\n> +check_result 'M L K J I H G' F..M --ancestry-path\n> +check_outcome failure 'M L J I H G' F..M --ancestry-path -- file # drops G\n\nWith --ancestry-path, what G does relative to E becomes irrelevant,\nbecause E is not in the F..M graph. G changes path relative to its\nremaining parent F, so it should be shown. OK.\n\n> +check_result 'M L K J I H G' F..M --ancestry-path --parents -- file\n\nOK. Again this makes me suspect --ancestry-path should flip\nrevs->rewrite_parents on.\n\n> +check_result 'M H L J I G' F..M --ancestry-path --simplify-merges -- file\n\n> +check_result 'M L K G' F..M --first-parent\n> +check_result 'M L G' F..M --first-parent -- file\n> +\n> +# Note that G is pruned when E is the bottom, even if it's the same commit list\n> +# If we want history since E, then we're quite happy to ignore G that took E.\n> +check_result 'M L K J I H G' E..M --ancestry-path\n\nOK.\n\n> +check_result 'M L J I H' E..M --ancestry-path -- file\n\nBecause F is outside our graph with --ancestry-path, G does not\nbring anything new to path relative to its remaining parent E and\nshould not be shown. OK.\n\n> +check_outcome failure 'M L K J I H' E..M --ancestry-path --parents -- file\n\nThis fails in what way? G is shown, because the !treesame with now\nirrelevant F comes into play?\n\n> +check_outcome failure 'M H L J I' E..M --ancestry-path --simplify-merges -- file # includes G\n\nMakes me wonder how \"--ancestry-path --full-history\" would work with\nthis range and with/without the pathspec.\n\n> +# Should still be able to ignore I-J branch in simple log, despite limiting\n> +# to G.\n> +check_result 'M L K J I H' G..M\n> +check_result 'M H L K J I' G..M --topo-order\n\nOK.\n\n> +check_outcome failure 'M L H' G..M -- file # includes J I\n> +check_outcome failure 'M L H' G..M --parents -- file # includes J I\n\nI am not sure if it should be a failure or your expectation is\nwrong. G is outside the graph, so as far as the remainder of the\ngraph is concerned, J is the sole remaining parent of K and I and J\ndid change the path in question. \n\nWhat makes you think I and J should be excluded in these cases?\n\nShouldn't the same logic as \"--ancestry-path [EF]..M\" we saw earlier\napply here? That is, \"-a-p E..M\" makes F the sole remaining parent\nof G and G does change the path from F so it should be shown, while\n\"-a-p F..M\" makes E the sole parent of G, and G does not change the\npath from E, so it should not be shown.\n\n> +check_result 'M L J I H' G..M --full-history -- file\n> +check_result 'M L K J I H' G..M --full-history --parents -- file\n> +check_result 'M H L J I' G..M --simplify-merges -- file\n> +check_result 'M L K J I H' G..M --ancestry-path\n> +check_result 'M L J I H' G..M --ancestry-path -- file\n> +check_result 'M L K J I H' G..M --ancestry-path --parents -- file\n> +check_result 'M H L J I' G..M --ancestry-path --simplify-merges -- file\n> +\n> +# B..F should be able to simplify the merge D from irrelevant side branch C.\n> +# Default log should also be free to follow B-D, and ignore C.\n> +# But --full-history shouldn't drop D on its own - without simplification,\n> +# we can't decide if the merge from INTERESTING commit C was sensible.\n> +check_result 'F D C' B..F\n> +check_result 'F' B..F -- file\n> +check_outcome failure 'F' B..F --parents -- file # includes D\n\nOK. --parents should not affect the outcome.\n\n> +check_outcome failure 'F D' B..F --full-history -- file # drops D prematurely\n\nOK.\n\n> +check_result 'F D' B..F --full-history --parents -- file\n\nAgain, OK.\n\n> +check_result 'F' B..F --simplify-merges -- file\n> +check_result 'F D' B..F --ancestry-path\n> +check_result 'F' B..F --ancestry-path -- file\n\nOK.\n\n> +check_outcome failure 'F' B..F --ancestry-path --parents -- file # includes D\n> +check_outcome failure 'F' B..F --ancestry-path --simplify-merges -- file # includes D\n\nOK. \"-a-p B..F\" makes C outside our graph, and D does not change\nthe path relative to its sole remaining parent B, so it should not\nappear in the result.\n\n> +check_result 'F D' B..F --first-parent\n> +check_result 'F' B..F --first-parent -- file\n\nOK.\n\n> +# Any sort of full history of C..F should show D, as it's the connection to C,\n> +# and it differs from it.\n> +check_result 'F D B' C..F\n> +check_result 'F B' C..F -- file\n\nOK, as A is a boundary and its child B changes the path from it.\n\n> +check_result 'F B' C..F --parents -- file\n\nOK.\n\n> +check_outcome failure 'F D B' C..F --full-history -- file # drops D\n\nOK.\n\n> +check_result 'F D B' C..F --full-history --parents -- file\n> +check_result 'F D B' C..F --simplify-merges -- file\n> +check_result 'F D' C..F --ancestry-path\n> +check_outcome failure 'F D' C..F --ancestry-path -- file # drops D\n\nOK. D should not be dropped merely because it is the same with B,\nwhich is now outside our graph \"-a-p C..F\".\n\n> +check_result 'F D' C..F --ancestry-path --parents -- file\n> +check_result 'F D' C..F --ancestry-path --simplify-merges -- file\n\nOK.\n\n> +check_result 'F D B' C..F --first-parent\n> +check_result 'F B' C..F --first-parent -- file\n\nOK. \"-f-p C..F\" is the same as \"-f-p A..F\", and C is outside our\ngraph, so these expectations look sensible.\n"},{"id":"216549","messageId":"7vtxmfq1ll.fsf@alter.siamese.dyndns.org","threadId":"33729","inReplyTo":"1367767977-14513-6-git-send-email-kevin@bracey.fi","subject":"Re: [PATCH v3 5/9] revision.c: Make --full-history consider more merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-06T20:45:26Z","receivedAt":"2013-05-06T20:45:26Z","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 a67b615..c88ded8 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -429,10 +429,100 @@ 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\nI have been wondering if we want to do one-bit (not one-byte) per\nparent but no biggie ;-)\n\n> @@ -1971,6 +2083,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> +...\n> +\t\tpo=po->next;\n\n\tpo = po->next;\n\n> +\t}\n\nThis seems to be identical (modulo tests) from the previous round,\nwhich I found a reasonable thing to do.\n"},{"id":"216554","messageId":"7vli7rpzt0.fsf@alter.siamese.dyndns.org","threadId":"33729","inReplyTo":"1367859096-25909-1-git-send-email-kevin@bracey.fi","subject":"Re: [PATCH v3 10/9] revision.c: treat A...B merge bases as if manually specified","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-06T21:24:11Z","receivedAt":"2013-05-06T21:24:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> The documentation assures users that \"A...B\" is defined as 'r1 r2 --not\n> $(git merge-base --all r1 r2)'. This isn't in fact quite true, because\n> the calculated merge bases are not sent to add_rev_cmdline().\n\nWe want the commands to be able to tell which ones in revs->pending\nand revs->commits were specified by the end user and how. While I\nthink it makes sense to mark these negative merge bases with \"These\ncame from the command line with A...B syntax\", I am not sure if it\nis the best way to do so in add_pending_commit_list().\n\nBy the way, why does this have anything to do with the history\ntraversal series in the first place?\n\nWhen there is anythning marked UNINTERESTING on the rev->pending\nbefore calling prepare_revision_walk(), you have a history with some\nbottom boundaries, and when there isn't, your bottom boundaries are\nroot commits. If you want to behave differently depending on how\nthe user gave us the revision range from the command line, e.g.\nacting differently between \"A ^B\" and \"B..A\", cmdline is a good\nplace to learn the exact form, but at the history traversal level, I\ndo not think you should even care. Why does the code even look at\nthe cmdline, and not rev->pending?\n"},{"id":"216617","messageId":"518913B8.5080302@bracey.fi","threadId":"33729","inReplyTo":"7vtxmfq1ll.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 5/9] revision.c: Make --full-history consider more merges","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-07T14:46:16Z","receivedAt":"2013-05-07T14:46:16Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 06/05/2013 23:45, Junio C Hamano wrote:\n> Kevin Bracey writes:\n>\n>> +struct treesame_state {\n>> +\tunsigned int nparents;\n>> +\tunsigned char treesame[FLEX_ARRAY];\n>> +};\n> I have been wondering if we want to do one-bit (not one-byte) per\n> parent but no biggie ;-)\n\nI did start down that path, because I felt bad about bloat.\n\nBut then I realised how much I would be complicating and slowing the \ncode down to only save a few bytes each time we walk a merge with at \nleast 5 parents, and I came to my senses. :)\n\nKevin\n"},{"id":"216621","messageId":"51891B9C.5040608@bracey.fi","threadId":"33729","inReplyTo":"7v1u9jrgl4.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 3/9] t6111: new TREESAME test set","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-07T15:19:56Z","receivedAt":"2013-05-07T15:19:56Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 06/05/2013 23:36, Junio C Hamano wrote:\n> Kevin Bracey writes:\n>\n>> +# ,---E--. *H----------. * marks !TREESAME parent paths\n>> +# / \\ / \\*\n>> +# *A--*B---D--*F-*G---------K-*L-*M\n>> +# \\ /* \\ /\n>> +# `-C-' `-*I-*J\n>> +#\n>> +# A creates \"file\", B and F change it.\n>> +# Odd merge G takes the old version from B.\n>> +# I changes it, but J reverts it.\n>> +# H and L both change it, and M merges those changes.\n>> + ...\n>>\n>> +check_outcome failure 'M H L J I G F B A' --simplify-merges -- file # drops G\n> Even though E simplifies down to B, making G a merge between B and F (the former is an ancestor of the latter), G is kept, because...?\n>\n> Because the path at B and F are different?\n\nG's simplified parent B is marked for deletion by the redundant parent scan; it would be redundant in any normal merge scenario. But here, because of the odd merge, it gets a reprieve from the \"don't drop all TREESAME parents\" rule. So merge G remains with 2 parents: B (its \"content\" parent) and F (its \"topological\" parent).\n\n> I have to wonder what should happen if D makes path different from B, and then F makes path the same as B. B and F should still be kept.\n\nThat would happen. G would be TREESAME to F, so the \"keep 1 TREESAME\" rule wouldn't need to kick in, parent B would be dropped from G, and G would simplify to F.\n\n\n> +# Check that odd merge G remains shown when F is the bottom.\n> I did not have a chance to say this when you responded in the\n> previous round with that \"bottom\" thing before you sent this new round,\n> but I am not sure if it is a good idea to pay special attention to the\n> \"bottom\"-ness. Very often, instead of running \"git log -- path\" and\n> stopping when seeing enough by killing the pager, people run\n> \"git log HEAD~200.. -- path\" to pick \"recent enough\"\n> commits, but the number 200 is very much arbitrary.\n\nTrue, the bottom can be arbitrary. But that actually turns out to be the key argument in favour of what I'm doing. The reason for treating the bottom \"specially\" is actually to prevent side branches that are immediately above the bottom from being treated specially. In early tests of the side branch logic, it became clear that whether a side branch was displayed or not depended on whether it was exactly adjacent to the bottom. The behaviour was arbitrary and annoying.\n\nConsidering your arbitrary bottom example, observe what happens if there's an irrelevant topic merge coming in at HEAD~199, and you try various bottoms around that point, without treating the bottom \"specially\". You get a transient simplification failure as the bottom passes:\n\n* Bottom=HEAD~300 - below the topic branch point:\n\nNormal simplification will work fine for the topic branch; it is unaffected by limiting, so the entire topic branch and merge is simplified away. This worked fine before this patch series (assuming a normal merge).\n\nNow we move forward to put the bottom between the topic branch point and merge.\n\n* Bottom=HEAD~201: (B=bottom, o=other UNINTERESTING, x=INTERESTING, *=!TREESAME)\n\n B--*x---x--*x simplifies to B--*x---x--*x\n /* /*\n o---x---x o\n\n New rules reduce to B--*x--*x (1 TREESAME INTERESTING parent,\n so ignore UNINTERESTING side)\n\n* Move bottom up one to HEAD~200:\n\n B---x--*x simplifies to B---x--*x\n /* /*\n o---x---x o\n\n (Merge can't be dropped -\n 2 UNINTERESTING parents that differ)\n\nIf I can't treat bottoms specially, then I can't distinguish between the merge's two UNINTERESTING parents, so I have to show the merge.\n\n* Move bottom up one again to HEAD~199, and the branch is excluded by the path-spec anyway:\n\n B--*x\n\nSo the net effect there is that we have a side branch merge that is shown for _exactly_ one choice of bottom commit on the mainline. It's not shown for 'HEAD~5000..' to 'HEAD~201..', and it's not shown for 'HEAD~199..' to 'HEAD..'. But it pops up in 'HEAD~200..'. Something's wrong with that picture, and treating the bottom as interesting removes the effect. Fuller discussion below.\n\n>> +check_result 'M L H' F..M -- file\n> OK. It is still one possible history to explain what we have in the path at the end.\n\nYes, but I don't really like it much. It's not clear that we came from an ancestor of F, not F itself. But there's nothing you can do about that in this most basic of commands, and at least adding any option does reveal the truth that we're not based on F. Even just \"--parents\" (implied in gitk) reveals that H came from B.\n\n>> +check_result 'M L K J I H G' F..M --full-history --parents -- file\n> OK.\n>\n> It almost makes me suspect that the --full-history option should flip\n> revs->rewrite_parents on (but not revs->print_parents, unless the --parents\n> option asks us to) when the option is parsed.\n\nI don't think so. Why do we want to show K unless we have to? It would just be a lot of noise in a normal \"git log\" - this tree isn't typical. In a normal tree, most merges will be more like K - so when requesting a log of a specific file, the mainline won't have modified the relevant file during the life of most irrelevant topic branches, so those branches' merges will be fully TREESAME and can be omitted.\n\nI assume --simplify-merges had to be invented to get rid of the noise of all the pointless fully-TREESAME merges from \"--full-history --parents\", which keeps all merges. But without --parents, a file-specific --full-history isn't currently that bad.\n\n\n>> +check_result 'M L J I H' E..M --ancestry-path -- file\n> Because F is outside our graph with --ancestry-path, G does not bring\n> anything new to path relative to its remaining parent E and should not be shown. OK.\n\nYep. And this works because we treat bottom E as a parent of G for TREESAME, despite it being UNINTERESTING. If we didn't, then E and F would be \"equals\", and G would have to be shown.\n\n>> +check_outcome failure 'M L K J I H' E..M --ancestry-path --parents --\n>> +file\n> This fails in what way? G is shown, because the !treesame with now irrelevant F comes into play?\n\nYes, that's right. Sorry, missing comment.\n\n>> +check_outcome failure 'M H L J I' E..M --ancestry-path\n>> +--simplify-merges -- file # includes G\n> Makes me wonder how \"--ancestry-path --full-history\" would work with this range and with/without the pathspec.\n\n--ancestry-path implies full-history, as far as I can see.\n\n>> +check_outcome failure 'M L H' G..M -- file # includes J I\n>> +check_outcome failure 'M L H' G..M --parents -- file # includes J I\n> I am not sure if it should be a failure or your expectation is wrong.\n> G is outside the graph, so as far as the remainder of the graph is concerned,\n> J is the sole remaining parent of K and I and J did change the path in question.\n>\n> What makes you think I and J should be excluded in these cases?\n\nBecause it's the simplest answer to the question \"what happened in M since G\", which is what \"G..M\" is supposed to mean. And because I J _would_ have been excluded and we would have got 'M L H' if we added an extra null commit G1 between G and K. That suggests an instability in our logic. Why should adding a totally irrelevant commit affect whether I-J is hidden? I J is hidden in every case apart from when you specify K^ as bottom. Why is K^ a special bottom?\n\nGraph theory time!\n\nThis all comes about because the formal graph definition doesn't match the user interface. The question \"B..C\" currently generates a graph of all commits in C since B, and the connections between those commits. It turns out to be problematic that the graph doesn't include the connection to B itself. It would be fine if only worrying about nodes in the graph. But it's not fine when you start doing graph operations that care about edge connections to parents.\n\nThinking linearly, consider:\n\nA..C: o--o--B--o--o--C\n\nThe two queries \"A..B\" and \"B..C\" should, between them, cover \"A..C\", surely? But with the current logic, they don't:\n\nA..B: o--o--B\nB..C: o--o--C\n\nWherever you place B, the following edge gets \"deleted\" from consideration. Not a problem for A..B, because we never consider graph commits' children. But it's a problem for B..C - it affects the graph operations on the first commit of the graph. Which is what triggers this G..M problem here. In all normal circumstances, the default graph following would always choose to take K's first TREESAME parent, and ignore IJ. But when the bottom is specifically K^, it breaks, because that mainline TREESAME edge is removed from consideration. K is handled differently because it's still on the graph, but it's lost its mainline parent.\n\nLooking at the graph above, with my proposed addition of G1:\n\nK~3..M:\n\n *G---G1--<-K-*L-*M\n \\ /\n `-*I-*J\n\nK~2..M:\n\n G1--<-K-*L-*M\n /\n *I-*J\n\nK^..M:\n\n K-*L-*M - whoops. Get diverted onto IJ\n /\n *I-*J\n\nK..M:\n\n L-*M\n\nSo for exactly one position of bottom along the mainline, we \"forget\" the path of our mainline, and get diverted, because we're not including the bottom in the graph. This is just like the HEAD~200 example - different graph optimisation, but same symptom and root cause. Include the bottom in the graph, but unprinted, and it works:\n\nK~3..M:\n\n (F)---*G---G1--<-K-*L-*M\n \\ /\n `-*I-*J\n\nK~2..M:\n\n (G)---G1--<-K-*L-*M\n \\ /\n `-*I-*J\nK^..M:\n\n (G1)-<-K-*L-*M\n /\n *I-*J\n\nK..M:\n\n L-*M\n\nWhat I'm effectively doing is extending the graph to actually include the unshown bottom. I think it just makes more sense. We connect up the linear history:\n\nA..B: (A)--o--o--B\nB..C: (B)--o--o--C\n\nThe two are now connected, with every commit and edge considered once between them. The A..B and B..C graphs are now really connected at B. In the second range, we don't print B, but do treat it as if it was part of the graph for graph-edge-based operations that want to distinguish between relevant and irrelevant parents. Which then means that the choice of split point B on the mainline between A and C doesn't perturb the side branch logic, because we always consider the same edges, regardless of where B is. B doesn't \"delete\" its following edge. And \"B..C\" now really is \"how did we get from B to C\" - it includes that first step.\n\n(In a non-linear graph, in this scheme, A..B and B..C aren't fully connected - all other commit boundaries between the sets are disjoint, and they only connect at B. But that's what makes the \"side branch\" logic work out - we can tell which path the user cares about at the bottom boundary, and hence which paths are the sides. Anything UNINTERESTING && !BOTTOM will be an ancestor of a bottom, and thus can be candidate for side-branch simplification, which is what we want to happen with 'HEAD~200..' above).\n\n> Shouldn't the same logic as \"--ancestry-path [EF]..M\" we saw earlier apply here?\n> That is, \"-a-p E..M\" makes F the sole remaining parent of G and G does change the\n> path from F so it should be shown, while \"-a-p F..M\" makes E the sole parent of G,\n> and G does not change the path from E, so it should not be shown.\n\nThat's muddled. I assume you mean:\n\n> That is, \"-a-p F..M\" makes F the sole remaining parent of G and G does change the\n> path from F so it should be shown, while \"-a-p E..M\" makes E the sole parent of G,\n> and G does not change the path from E, so it should not be shown.\n\nWhich is the way the logic works - we treat F and E as interesting/priority parents when they're specified as a bottom in each case. Without doing that, G would have 2 differing and equally (un)important parents in each case, and thus would be shown in both cases.\n\nIn this case, the same logic says that G is treated as an interesting parent of K because it is the specified bottom. Which then enables the default following to follow that path direct to G, rather than having to go down the IJ path (which leads to G anyway).\n\nKevin\n"},{"id":"216619","messageId":"7vip2ulssy.fsf@alter.siamese.dyndns.org","threadId":"33729","inReplyTo":"518913B8.5080302@bracey.fi","subject":"Re: [PATCH v3 5/9] revision.c: Make --full-history consider more merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-07T15:21:17Z","receivedAt":"2013-05-07T15:21:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> On 06/05/2013 23:45, Junio C Hamano wrote:\n>> Kevin Bracey writes:\n>>\n>>> +struct treesame_state {\n>>> +\tunsigned int nparents;\n>>> +\tunsigned char treesame[FLEX_ARRAY];\n>>> +};\n>> I have been wondering if we want to do one-bit (not one-byte) per\n>> parent but no biggie ;-)\n>\n> I did start down that path, because I felt bad about bloat.\n>\n> But then I realised how much I would be complicating and slowing the\n> code down to only save a few bytes each time we walk a merge with at\n> least 5 parents, and I came to my senses. :)\n\n;-)\n"},{"id":"216624","messageId":"5189232D.4060305@bracey.fi","threadId":"33729","inReplyTo":"7vli7rpzt0.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 10/9] revision.c: treat A...B merge bases as if manually specified","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2013-05-07T15:52:13Z","receivedAt":"2013-05-07T15:52:13Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 07/05/2013 00:24, Junio C Hamano wrote:\n> Kevin Bracey writes:\n>\n>> The documentation assures users that \"A...B\" is defined as 'r1 r2 --not\n>> $(git merge-base --all r1 r2)'. This isn't in fact quite true, because\n>> the calculated merge bases are not sent to add_rev_cmdline().\n> We want the commands to be able to tell which ones in revs->pending\n> and revs->commits were specified by the end user and how. While I\n> think it makes sense to mark these negative merge bases with \"These\n> came from the command line with A...B syntax\", I am not sure if it\n> is the best way to do so in add_pending_commit_list().\nLayering violation? The callers of add_pending_commit_list() should be \ndoing it themselves? Yes, I suppose it was a bit of a convenience hack, \nhaving add_pending_commit_list do it.\n>\n> By the way, why does this have anything to do with the history\n> traversal series in the first place?\n\nThe answer's in the test, but it's not that clear in this series \naddendum, with the test newly appearing and passing. The next version of \nthe series will have the test in initially as a failure.\n\nWithout this patch, \"git log E...F file\" will unnecessarily show D, as \nit has 2 differing non-priority parents B and C.\n\nWhereas \"git log E F ^B file\" doesn't show D. So we have a behaviour \ndifference between two allegedly equivalent commands.\n\nWhen querying E...F, C is a side branch between the merge base B and F, \nso D should be removable, just as for \"B..F\" or \"E F ^B\". So we need to \ngive B the BOTTOM marker to make that work, as if it had been specified \n\"E F ^B\".\n\n\n>\n> When there is anythning marked UNINTERESTING on the rev->pending\n> before calling prepare_revision_walk(), you have a history with some\n> bottom boundaries, and when there isn't, your bottom boundaries are\n> root commits. If you want to behave differently depending on how\n> the user gave us the revision range from the command line, e.g.\n> acting differently between \"A ^B\" and \"B..A\", cmdline is a good\n> place to learn the exact form, but at the history traversal level, I\n> do not think you should even care. Why does the code even look at\n> the cmdline, and not rev->pending?\n>\n\nWell, on this first pass I wanted to be sure I was using the same \ndefinition of \"bottom\" as ancestry-path, so I hacked the flag setting in \nthere, and I believe the answer to \"why not just look at UNINTERESTING\" \nlies in commit 281eee4. If I understand that correctly, it goes wrong \nwhen you have multiple negative specifications - some initial walking is \ndone, meaning we can't distinguish between specified bottoms and other \nwalk results.\n\nNow, the current structure of the code is clearly silly, and my \"hack\" \ncomment acknowledged that - if we have the BOTTOM flag, we could just \nset that immediately during command parsing, and neither this nor \nancestry-path would need to look back at the command line to identify \nwhat the bottom commits were. But I didn't want to start work on that \nwithout further discussion about the merits of the BOTTOM flag.\n\n(Actually, no, I'm not looking back at the command line, I just know \nthat ancestry-path does, so I make sure I arrange it so that my \ninspection of rev->pending shows the same bottom commits as its \ninspection of the command line).\n\nKevin\n"},{"id":"216627","messageId":"7vwqrakb4x.fsf@alter.siamese.dyndns.org","threadId":"33729","inReplyTo":"51891B9C.5040608@bracey.fi","subject":"Re: [PATCH v3 3/9] t6111: new TREESAME test set","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-07T16:28:14Z","receivedAt":"2013-05-07T16:28:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Bracey writes:\n\n> On 06/05/2013 23:36, Junio C Hamano wrote:\n>> Kevin Bracey writes:\n>>\n>>> +# ,---E--. *H----------. * marks !TREESAME parent paths\n>>> +# / \\ / \\*\n>>> +# *A--*B---D--*F-*G---------K-*L-*M\n>>> +# \\ /* \\ /\n>>> +# `-C-' `-*I-*J\n>>> +#\n>>> +# A creates \"file\", B and F change it.\n>>> +# Odd merge G takes the old version from B.\n>>> +# I changes it, but J reverts it.\n>>> +# H and L both change it, and M merges those changes.\n>>> + ...\n> ...\n>>> +check_outcome failure 'M L H' G..M -- file # includes J I\n>>> +check_outcome failure 'M L H' G..M --parents -- file # includes J I\n>> I am not sure if it should be a failure or your expectation is wrong.\n>> G is outside the graph, so as far as the remainder of the graph is concerned,\n>> J is the sole remaining parent of K and I and J did change the path in question.\n>>\n>> What makes you think I and J should be excluded in these cases?\n>\n> Because it's the simplest answer to the question \"what happened in\n> M since G\", which is what \"G..M\" is supposed to mean. ...\n> \n> This all comes about because the formal graph definition doesn't\n> match the user interface. The question \"B..C\" currently generates\n> a graph of all commits in C since B, and the connections between\n> those commits. It turns out to be problematic that the graph\n> doesn't include the connection to B itself. It would be fine if\n> only worrying about nodes in the graph. But it's not fine when you\n> start doing graph operations that care about edge connections to\n> parents.\n\nOK, that makes sense.\n\n> ...\n> What I'm effectively doing is extending the graph to actually\n> include the unshown bottom. I think it just makes more sense.\n\nYup, and this is a good summary.\n\n\n> ... I assume you mean:\n>\n>> That is, \"-a-p F..M\" makes F the sole remaining parent of G and G does change the\n>> path from F so it should be shown, while \"-a-p E..M\" makes E the sole parent of G,\n>> and G does not change the path from E, so it should not be shown.\n\nYes.\n\n> Which is the way the logic works - we treat F and E as\n> interesting/priority parents when they're specified as a bottom in\n> each case. Without doing that, G would have 2 differing and\n> equally (un)important parents in each case, and thus would be\n> shown in both cases.\n>\n> In this case, the same logic says that G is treated as an\n> interesting parent of K because it is the specified bottom. Which\n> then enables the default following to follow that path direct to\n> G, rather than having to go down the IJ path (which leads to G\n> anyway).\n\nOK.\n"}]}