{"thread":{"id":"23537","subject":"Getting 'git log' (or something else) to show me the relevant sub-graph?","startedAt":"2010-04-20T14:49:30Z","lastAt":"2010-04-21T09:04:37Z","messageCount":11,"participants":["Johan Herland","Michael J Gruber","Junio C Hamano","Johannes Sixt"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"139979","messageId":"201004201649.31084.johan@herland.net","threadId":"23537","inReplyTo":null,"subject":"Getting 'git log' (or something else) to show me the relevant sub-graph?","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-04-20T14:49:30Z","receivedAt":"2010-04-20T14:49:30Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Hi,\n\nConsider the following (simplified) history:\n\n---O---O---O---O---O---O---O---O---O---O---O---O---M2--H  <-- mainline\n    \\                                             /\n     O---O---O---O---O---O---O---M1--D---E---F---G  <-- dev-branch\n              \\                 /\n               O---O---A---B---C  <-- topic-branch\n\nNow, assume that I have bisected my way through to 'A', and found that \nit introduces some bug. Now, I'm interested in visualizing the path \nthat this bug \"travelled\" to get into \"mainline\", i.e. the following \nsub-graph:\n\n                          --M2--H  <-- mainline\n                           /\n        --M1--D---E---F---G  <-- dev-branch\n         /\nA---B---C  <-- topic-branch\n\nIn other words, I'm interested in the following log (with decorations):\n\nH (mainline)\nM2\nG (dev-branch)\nF\nE\nD\nM1\nC (topic-branch)\nB\nA\n\nI have unsuccessfully dug through the 'git log' documentation to figure \nout if it can produce this log, so I'm now throwing the question to the \nalmighty knowledge of the mailing list...\n\nHere are some of my closest attempts, so far:\n\n- git branch --contains A\n\tgives me \"topic-branch\", \"dev-branch\" and \"mainline\", which is\n\trelevant, but incomplete.\n\n- git log --oneline --decorate --graph A^..mainline\n\tgives me a log/graph where I can search for A and then use the graph\n\tto trace the way back up to \"mainline\", but it still displays a lot of\n\tuninteresting commits (ancestors of M1 and M2) that I have to\n\tdisregard. Although this is ok once in a while, the problem is common\n\tenough (and the real-world graphs complicated enough), that I'd like a\n\tbetter solution, if possible.\n\nI guess what I'm looking for is something similar to --first-parent, \nexcept instead of the _first_ parent, it should follow the _relevant_ \nparent, as far as the relationship between A and \"mainline\" is \nconcerned.\n\nIn set-theory terms I guess what I want is \"that which is both an \nancestor of H, and a descendant of A (inclusive)\", but I don't know how \nto explain this to 'git log'.\n\n\nThanks for any help,\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"139983","messageId":"4BCDC5B9.1000705@drmicha.warpmail.net","threadId":"23537","inReplyTo":"201004201649.31084.johan@herland.net","subject":"Re: Getting 'git log' (or something else) to show me the relevant sub-graph?","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2010-04-20T15:18:17Z","receivedAt":"2010-04-20T15:18:17Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Johan Herland venit, vidit, dixit 20.04.2010 16:49:\n> Hi,\n> \n> Consider the following (simplified) history:\n> \n> ---O---O---O---O---O---O---O---O---O---O---O---O---M2--H  <-- mainline\n>     \\                                             /\n>      O---O---O---O---O---O---O---M1--D---E---F---G  <-- dev-branch\n>               \\                 /\n>                O---O---A---B---C  <-- topic-branch\n> \n> Now, assume that I have bisected my way through to 'A', and found that \n> it introduces some bug. Now, I'm interested in visualizing the path \n> that this bug \"travelled\" to get into \"mainline\", i.e. the following \n> sub-graph:\n> \n>                           --M2--H  <-- mainline\n>                            /\n>         --M1--D---E---F---G  <-- dev-branch\n>          /\n> A---B---C  <-- topic-branch\n> \n> In other words, I'm interested in the following log (with decorations):\n> \n> H (mainline)\n> M2\n> G (dev-branch)\n> F\n> E\n> D\n> M1\n> C (topic-branch)\n> B\n> A\n> \n> I have unsuccessfully dug through the 'git log' documentation to figure \n> out if it can produce this log, so I'm now throwing the question to the \n> almighty knowledge of the mailing list...\n> \n> Here are some of my closest attempts, so far:\n> \n> - git branch --contains A\n> \tgives me \"topic-branch\", \"dev-branch\" and \"mainline\", which is\n> \trelevant, but incomplete.\n> \n> - git log --oneline --decorate --graph A^..mainline\n> \tgives me a log/graph where I can search for A and then use the graph\n> \tto trace the way back up to \"mainline\", but it still displays a lot of\n> \tuninteresting commits (ancestors of M1 and M2) that I have to\n> \tdisregard. Although this is ok once in a while, the problem is common\n> \tenough (and the real-world graphs complicated enough), that I'd like a\n> \tbetter solution, if possible.\n> \n> I guess what I'm looking for is something similar to --first-parent, \n> except instead of the _first_ parent, it should follow the _relevant_ \n> parent, as far as the relationship between A and \"mainline\" is \n> concerned.\n> \n> In set-theory terms I guess what I want is \"that which is both an \n> ancestor of H, and a descendant of A (inclusive)\", but I don't know how \n> to explain this to 'git log'.\n\nThis would require a reverse tree walker for the first half of that set\nintersection. It would come in handy in many situations, but we don't\nhave it.\n\nMathematically speaking it is trivial to associate to a directed graph\nthe graph with opposite orientation. Then we could walk as usual...\n\nBut, in fact, we do not \"walk then intersect\", but the walker implements\nthe intersection, so having that other dag would not even help.\n\nMaybe we can teach the walker to mark commits as uninteresting which do\nnot have A in their ancestry?\n\nMichael\n"},{"id":"139994","messageId":"7viq7lg8f2.fsf@alter.siamese.dyndns.org","threadId":"23537","inReplyTo":"201004201649.31084.johan@herland.net","subject":"Re: Getting 'git log' (or something else) to show me the relevant sub-graph?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-20T20:45:21Z","receivedAt":"2010-04-20T20:45:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland <johan@herland.net> writes:\n\n> Now, assume that I have bisected my way through to 'A', and found that \n> it introduces some bug. Now, I'm interested in visualizing the path \n> that this bug \"travelled\" to get into \"mainline\", i.e. the following \n> sub-graph:\n>\n>                           --M2--H  <-- mainline\n>                            /\n>         --M1--D---E---F---G  <-- dev-branch\n>          /\n> A---B---C  <-- topic-branch\n\nInteresting.  I am looking into it ;-)\n"},{"id":"140000","messageId":"7v39ypg4gm.fsf_-_@alter.siamese.dyndns.org","threadId":"23537","inReplyTo":"7viq7lg8f2.fsf@alter.siamese.dyndns.org","subject":"[PATCH] revision: --ancestry-path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-20T22:10:49Z","receivedAt":"2010-04-20T22:10:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is somewhat a rough-cut, as I haven't thought through possible\ninteractions this new option may have with \"rev-list --parents\" and\n\"rev-list --graph\" (see \"NEEDSWORK\" in revision.c), but I'll leave that to\npeople who are more interested in this topic than myself ;-).\n\n-- >8 --\n\"rev-list A..H\" computes the set of commits that are ancestors of H, but\nexcludes the ones that are ancestors of A.  This is useful to see what\nhappened to the history leading to H since A, in the sense that \"what does\nH have that did not exist in A\" (e.g. when you have a choice to update to\nH from A).\n\n\t       x---x---A---B---C  <-- topic\n\t      /\t\t\t\\\n     x---x---x---o---o---o---o---M---D---E---F---G  <-- dev\n    /\t\t\t\t\t\t  \\\n   x---o---o---o---o---o---o---o---o---o---o---o---N---H  <-- master\n\nThe result in the above example would be the commits marked with caps\nletters (except for A itself, of course), and the ones marked with 'o'.\n\nWhen you want to find out what commits in H are contaminated with the bug\nintroduced by A and need fixing, however, you might want to view only the\nsubset of \"A..B\" that are actually descendants of A, i.e. excluding the\nones marked with 'o'.  Introduce a new option --ancestry-path to compute\nthis set with \"rev-list --ancestry-path A..B\".\n\nNote that in practice, you would build a fix immediately on top of A and\n\"git branch --contains A\" will give the names of branches that you would\nneed to merge the fix into (i.e. topic, dev and master), so this may not\nbe worth paying the extra cost of postprocessing.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n revision.c                        |  106 +++++++++++++++++++++++++++++++++++++\n revision.h                        |    1 +\n t/t6019-rev-list-ancestry-path.sh |   56 +++++++++++++++++++\n 3 files changed, 163 insertions(+), 0 deletions(-)\n create mode 100755 t/t6019-rev-list-ancestry-path.sh\n\ndiff --git a/revision.c b/revision.c\nindex f4b8b38..cb91094 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -646,6 +646,99 @@ static int still_interesting(struct commit_list *src, unsigned long date, int sl\n \treturn slop-1;\n }\n \n+/*\n+ * \"rev-list --ancestry-path A..B\" computes commits that are ancestors\n+ * of B but not ancestors of A but further limits the result to those\n+ * that are descendants of A.  This takes the list of bottom commits and\n+ * the result of \"A..B\" without --ancestry-path, and limits the latter\n+ * further to the ones that can reach one of the commits in \"bottom\".\n+ */\n+static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *list)\n+{\n+\tstruct commit_list *p;\n+\tstruct commit_list *rlist = NULL;\n+\tint made_progress;\n+\n+\t/*\n+\t * Clear TMP_MARK and reverse the list so that it will be likely\n+\t * that we would process parents before children.\n+\t */\n+\tfor (p = list; p; p = p->next) {\n+\t\tp->item->object.flags &= ~TMP_MARK;\n+\t\tcommit_list_insert(p->item, &rlist);\n+\t}\n+\n+\tfor (p = bottom; p; p = p->next)\n+\t\tp->item->object.flags |= TMP_MARK;\n+\n+\t/*\n+\t * Mark the ones that can reach bottom commits in \"list\",\n+\t * in a bottom-up fashion.\n+\t */\n+\tdo {\n+\t\tmade_progress = 0;\n+\t\tfor (p = rlist; p; p = p->next) {\n+\t\t\tstruct commit *c = p->item;\n+\t\t\tstruct commit_list *parents;\n+\t\t\tif (c->object.flags & (TMP_MARK | UNINTERESTING))\n+\t\t\t\tcontinue;\n+\t\t\tfor (parents = c->parents;\n+\t\t\t     parents;\n+\t\t\t     parents = parents->next) {\n+\t\t\t\tif (!(parents->item->object.flags & TMP_MARK))\n+\t\t\t\t\tcontinue;\n+\t\t\t\tc->object.flags |= TMP_MARK;\n+\t\t\t\tmade_progress = 1;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t} while (made_progress);\n+\n+\t/*\n+\t * NEEDSWORK: decide if we want to remove parents that are\n+\t * not marked with TMP_MARK from commit->parents for commits\n+\t * in the resulting list.  We may not want to do that, though.\n+\t */\n+\n+\t/*\n+\t * The ones that are not marked with TMP_MARK are uninteresting\n+\t */\n+\tfor (p = list; p; p = p->next) {\n+\t\tstruct commit *c = p->item;\n+\t\tif (c->object.flags & TMP_MARK) {\n+\t\t\tc->object.flags &= ~TMP_MARK;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tc->object.flags |= UNINTERESTING;\n+\t}\n+\n+\t/* Release the bottom list */\n+\twhile (bottom) {\n+\t\tp = bottom->next;\n+\t\tbottom->item->object.flags &= ~TMP_MARK;\n+\t\tfree(bottom);\n+\t\tbottom = p;\n+\t}\n+\tfree_commit_list(rlist);\n+}\n+\n+/*\n+ * Before walking the history, keep the set of \"negative\" refs the\n+ * caller has asked to exclude.\n+ *\n+ * This is used to compute \"rev-list --ancestry-path A..B\", as we need\n+ * to filter the result of \"A..B\" further to the ones that can actually\n+ * reach A.\n+ */\n+static struct commit_list *collect_bottom_commits(struct commit_list *list)\n+{\n+\tstruct commit_list *elem, *bottom = NULL;\n+\tfor (elem = list; elem; elem = elem->next)\n+\t\tif (elem->item->object.flags & UNINTERESTING)\n+\t\t\tcommit_list_insert(elem->item, &bottom);\n+\treturn bottom;\n+}\n+\n static int limit_list(struct rev_info *revs)\n {\n \tint slop = SLOP;\n@@ -653,6 +746,13 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n+\tstruct commit_list *bottom = NULL;\n+\n+\tif (revs->ancestry_path) {\n+\t\tbottom = collect_bottom_commits(list);\n+\t\tif (!bottom)\n+\t\t\tdie(\"--ancestry-path given but there is no bottom commits\");\n+\t}\n \n \twhile (list) {\n \t\tstruct commit_list *entry = list;\n@@ -694,6 +794,9 @@ static int limit_list(struct rev_info *revs)\n \tif (revs->cherry_pick)\n \t\tcherry_pick_list(newlist, revs);\n \n+\tif (bottom)\n+\t\tlimit_to_ancestry(bottom, newlist);\n+\n \trevs->commits = newlist;\n \treturn 0;\n }\n@@ -1089,6 +1192,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->min_age = approxidate(arg + 8);\n \t} else if (!strcmp(arg, \"--first-parent\")) {\n \t\trevs->first_parent_only = 1;\n+\t} else if (!strcmp(arg, \"--ancestry-path\")) {\n+\t\trevs->ancestry_path = 1;\n+\t\trevs->limited = 1;\n \t} else if (!strcmp(arg, \"-g\") || !strcmp(arg, \"--walk-reflogs\")) {\n \t\tinit_reflog_walk(&revs->reflog_info);\n \t} else if (!strcmp(arg, \"--default\")) {\ndiff --git a/revision.h b/revision.h\nindex 568f1c9..855464f 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -66,6 +66,7 @@ struct rev_info {\n \t\t\treverse_output_stage:1,\n \t\t\tcherry_pick:1,\n \t\t\tbisect:1,\n+\t\t\tancestry_path:1,\n \t\t\tfirst_parent_only:1;\n \n \t/* Diff flags */\ndiff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh\nnew file mode 100755\nindex 0000000..0230724\n--- /dev/null\n+++ b/t/t6019-rev-list-ancestry-path.sh\n@@ -0,0 +1,56 @@\n+#!/bin/sh\n+\n+test_description='--ancestry-path'\n+\n+#          D---E-------F\n+#         /     \\       \\\n+#    B---C---G---H---I---J\n+#   /                     \\\n+#  A-------K---------------L--M\n+#\n+#  D..M                 == E F G H I J K L M\n+#  --ancestry-path D..M == E F H I J L M\n+\n+. ./test-lib.sh\n+\n+test_merge () {\n+\ttest_tick &&\n+\tgit merge -s ours -m \"$2\" \"$1\" &&\n+\tgit tag \"$2\"\n+}\n+\n+test_expect_success setup '\n+\ttest_commit A &&\n+\ttest_commit B &&\n+\ttest_commit C &&\n+\ttest_commit D &&\n+\ttest_commit E &&\n+\ttest_commit F &&\n+\tgit reset --hard C &&\n+\ttest_commit G &&\n+\ttest_merge E H &&\n+\ttest_commit I &&\n+\ttest_merge F J &&\n+\tgit reset --hard A &&\n+\ttest_commit K &&\n+\ttest_merge J L &&\n+\ttest_commit M\n+'\n+\n+test_expect_success 'rev-list D..M' '\n+\tfor c in E F G H I J K L M; do echo $c; done >expect &&\n+\tgit rev-list --format=%s D..M |\n+\tsed -e \"/^commit /d\" |\n+\tsort >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'rev-list --ancestry-path D..M' '\n+\tfor c in E F H I J L M; do echo $c; done >expect &&\n+\tgit rev-list --ancestry-path --format=%s D..M |\n+\tsed -e \"/^commit /d\" |\n+\tsort >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n1.7.1.rc2.265.g8743f\n"},{"id":"140012","messageId":"201004210934.30226.johan@herland.net","threadId":"23537","inReplyTo":"7v39ypg4gm.fsf_-_@alter.siamese.dyndns.org","subject":"Re: [PATCH] revision: --ancestry-path","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-04-21T07:34:30Z","receivedAt":"2010-04-21T07:34:30Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 21 April 2010, Junio C Hamano wrote:\n> This is somewhat a rough-cut, as I haven't thought through possible\n> interactions this new option may have with \"rev-list --parents\" and\n> \"rev-list --graph\" (see \"NEEDSWORK\" in revision.c), but I'll leave that\n> to people who are more interested in this topic than myself ;-).\n\nThanks! :)\n\nI can confirm that this patch works with my original (more complicated) \nscenario. I've also played around with combinations of --ancestry-path, --\ngraph and --parents (and even --boundary), and AFAICS, the new option does \nnot clobber the other options, and (IMHO) it all behaves correctly in the \nscenarios I've tested. Consider it:\n\nTested-by: Johan Herland <johan@herland.net>\n\nI've also reviewed the patch, and it all looks good to me (i.e. \"Acked-by\", \nexcept I'm not super-familiar in the relevant area of the code).\n\nWhat more should I do to push this forwards towards 'next'?\n\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"140013","messageId":"4BCEADA3.7090504@viscovery.net","threadId":"23537","inReplyTo":"201004210934.30226.johan@herland.net","subject":"Re: [PATCH] revision: --ancestry-path","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2010-04-21T07:47:47Z","receivedAt":"2010-04-21T07:47:47Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 4/21/2010 9:34, schrieb Johan Herland:\n> I can confirm that this patch works with my original (more complicated) \n> scenario. I've also played around with combinations of --ancestry-path, --\n> graph and --parents (and even --boundary), and AFAICS, the new option does \n> not clobber the other options, and (IMHO) it all behaves correctly in the \n> scenarios I've tested.\n\nHow about possible interactions with --reverse; --date-order/--topo-order,\n--parents (important for gitk); --simplify-by-decoration (useful for your\nproblem that triggered this); --full-history and --simplify-merges with\npath limiting?\n\n-- Hannes\n"},{"id":"140015","messageId":"7vochdcjz5.fsf@alter.siamese.dyndns.org","threadId":"23537","inReplyTo":"4BCEADA3.7090504@viscovery.net","subject":"Re: [PATCH] revision: --ancestry-path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-21T08:01:34Z","receivedAt":"2010-04-21T08:01:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt <j.sixt@viscovery.net> writes:\n\n> Am 4/21/2010 9:34, schrieb Johan Herland:\n>> I can confirm that this patch works with my original (more complicated) \n>> scenario. I've also played around with combinations of --ancestry-path, --\n>> graph and --parents (and even --boundary), and AFAICS, the new option does \n>> not clobber the other options, and (IMHO) it all behaves correctly in the \n>> scenarios I've tested.\n>\n> How about possible interactions with --reverse; --date-order/--topo-order,\n> --parents (important for gitk); --simplify-by-decoration (useful for your\n> problem that triggered this); --full-history and --simplify-merges with\n> path limiting?\n\nThese are all good points.\n\nI am reasonably sure that parents (specifically, \"rewrite_parents\") is\nbroken.  The new function should cull parents that do not appear on the\nancestry path from merges (that is what \"NEEDSWORK\" is about).  It may or\nmay not break gitk, though---these off-path parents are shown as parents\nof an on-path merge but will be marked as UNINTERESTING.\n\nI do not think reverse/date-order/topo-order would be affected by this\nchange, as they only change the presentation order of what limit_list()\nreturns;\n\nAlso simplify-merges and full-history should be Ok, as they control what\nis done in the current logic in limit_list(), which is an input to the new\nlogic, meaning that the new logic will work on already simplified history.\n\nThis is not a new problem, but I strongly suspect that cherry-pick is\nbroken the same way wrt \"rewrite_parents\".\n"},{"id":"140016","messageId":"7vhbn5cj5y.fsf_-_@alter.siamese.dyndns.org","threadId":"23537","inReplyTo":"7vochdcjz5.fsf@alter.siamese.dyndns.org","subject":"[PATCH v2] revision: --ancestry-path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-21T08:19:05Z","receivedAt":"2010-04-21T08:19:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"rev-list A..H\" computes the set of commits that are ancestors of H, but\nexcludes the ones that are ancestors of A.  This is useful to see what\nhappened to the history leading to H since A, in the sense that \"what does\nH have that did not exist in A\" (e.g. when you have a choice to update to\nH from A).\n\n\t       x---x---A---B---C  <-- topic\n\t      /\t\t\t\\\n     x---x---x---o---o---o---o---M---D---E---F---G  <-- dev\n    /\t\t\t\t\t\t  \\\n   x---o---o---o---o---o---o---o---o---o---o---o---N---H  <-- master\n\nThe result in the above example would be the commits marked with caps\nletters (except for A itself, of course), and the ones marked with 'o'.\n\nWhen you want to find out what commits in H are contaminated with the bug\nintroduced by A and need fixing, however, you might want to view only the\nsubset of \"A..B\" that are actually descendants of A, i.e. excluding the\nones marked with 'o'.  Introduce a new option --ancestry-path to compute\nthis set with \"rev-list --ancestry-path A..B\".\n\nNote that in practice, you would build a fix immediately on top of A and\n\"git branch --contains A\" will give the names of branches that you would\nneed to merge the fix into (i.e. topic, dev and master), so this may not\nbe worth paying the extra cost of postprocessing.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n * This simplifies the handling of TMP_MARK (the contract among the\n   functions is that this is used only locally and the user is responsible\n   for cleaning them up after use, so there is no need to clear the mark\n   upfront), and also makes it responsibility of the caller to free the\n   \"bottom\" list.\n\n   Interdiff since v1 looks like this.\n\n    diff -u b/revision.c b/revision.c\n    --- b/revision.c\n    +++ b/revision.c\n    @@ -660,13 +660,11 @@\n     \tint made_progress;\n     \n     \t/*\n    -\t * Clear TMP_MARK and reverse the list so that it will be likely\n    -\t * that we would process parents before children.\n    +\t * Reverse the list so that it will be likely that we would\n    +\t * process parents before children.\n     \t */\n    -\tfor (p = list; p; p = p->next) {\n    -\t\tp->item->object.flags &= ~TMP_MARK;\n    +\tfor (p = list; p; p = p->next)\n     \t\tcommit_list_insert(p->item, &rlist);\n    -\t}\n     \n     \tfor (p = bottom; p; p = p->next)\n     \t\tp->item->object.flags |= TMP_MARK;\n    @@ -705,20 +703,16 @@\n     \t */\n     \tfor (p = list; p; p = p->next) {\n     \t\tstruct commit *c = p->item;\n    -\t\tif (c->object.flags & TMP_MARK) {\n    -\t\t\tc->object.flags &= ~TMP_MARK;\n    +\t\tif (c->object.flags & TMP_MARK)\n     \t\t\tcontinue;\n    -\t\t}\n     \t\tc->object.flags |= UNINTERESTING;\n     \t}\n     \n    -\t/* Release the bottom list */\n    -\twhile (bottom) {\n    -\t\tp = bottom->next;\n    -\t\tbottom->item->object.flags &= ~TMP_MARK;\n    -\t\tfree(bottom);\n    -\t\tbottom = p;\n    -\t}\n    +\t/* We are done with the TMP_MARK */\n    +\tfor (p = list; p; p = p->next)\n    +\t\tp->item->object.flags &= ~TMP_MARK;\n    +\tfor (p = bottom; p; p = p->next)\n    +\t\tp->item->object.flags &= ~TMP_MARK;\n     \tfree_commit_list(rlist);\n     }\n     \n    @@ -794,8 +788,10 @@\n     \tif (revs->cherry_pick)\n     \t\tcherry_pick_list(newlist, revs);\n     \n    -\tif (bottom)\n    +\tif (bottom) {\n     \t\tlimit_to_ancestry(bottom, newlist);\n    +\t\tfree_commit_list(bottom);\n    +\t}\n     \n     \trevs->commits = newlist;\n     \treturn 0;\n\n revision.c                        |  102 +++++++++++++++++++++++++++++++++++++\n revision.h                        |    1 +\n t/t6019-rev-list-ancestry-path.sh |   56 ++++++++++++++++++++\n 3 files changed, 159 insertions(+), 0 deletions(-)\n create mode 100755 t/t6019-rev-list-ancestry-path.sh\n\ndiff --git a/revision.c b/revision.c\nindex f4b8b38..71fec3c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -646,6 +646,93 @@ static int still_interesting(struct commit_list *src, unsigned long date, int sl\n \treturn slop-1;\n }\n \n+/*\n+ * \"rev-list --ancestry-path A..B\" computes commits that are ancestors\n+ * of B but not ancestors of A but further limits the result to those\n+ * that are descendants of A.  This takes the list of bottom commits and\n+ * the result of \"A..B\" without --ancestry-path, and limits the latter\n+ * further to the ones that can reach one of the commits in \"bottom\".\n+ */\n+static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *list)\n+{\n+\tstruct commit_list *p;\n+\tstruct commit_list *rlist = NULL;\n+\tint made_progress;\n+\n+\t/*\n+\t * Reverse the list so that it will be likely that we would\n+\t * process parents before children.\n+\t */\n+\tfor (p = list; p; p = p->next)\n+\t\tcommit_list_insert(p->item, &rlist);\n+\n+\tfor (p = bottom; p; p = p->next)\n+\t\tp->item->object.flags |= TMP_MARK;\n+\n+\t/*\n+\t * Mark the ones that can reach bottom commits in \"list\",\n+\t * in a bottom-up fashion.\n+\t */\n+\tdo {\n+\t\tmade_progress = 0;\n+\t\tfor (p = rlist; p; p = p->next) {\n+\t\t\tstruct commit *c = p->item;\n+\t\t\tstruct commit_list *parents;\n+\t\t\tif (c->object.flags & (TMP_MARK | UNINTERESTING))\n+\t\t\t\tcontinue;\n+\t\t\tfor (parents = c->parents;\n+\t\t\t     parents;\n+\t\t\t     parents = parents->next) {\n+\t\t\t\tif (!(parents->item->object.flags & TMP_MARK))\n+\t\t\t\t\tcontinue;\n+\t\t\t\tc->object.flags |= TMP_MARK;\n+\t\t\t\tmade_progress = 1;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t} while (made_progress);\n+\n+\t/*\n+\t * NEEDSWORK: decide if we want to remove parents that are\n+\t * not marked with TMP_MARK from commit->parents for commits\n+\t * in the resulting list.  We may not want to do that, though.\n+\t */\n+\n+\t/*\n+\t * The ones that are not marked with TMP_MARK are uninteresting\n+\t */\n+\tfor (p = list; p; p = p->next) {\n+\t\tstruct commit *c = p->item;\n+\t\tif (c->object.flags & TMP_MARK)\n+\t\t\tcontinue;\n+\t\tc->object.flags |= UNINTERESTING;\n+\t}\n+\n+\t/* We are done with the TMP_MARK */\n+\tfor (p = list; p; p = p->next)\n+\t\tp->item->object.flags &= ~TMP_MARK;\n+\tfor (p = bottom; p; p = p->next)\n+\t\tp->item->object.flags &= ~TMP_MARK;\n+\tfree_commit_list(rlist);\n+}\n+\n+/*\n+ * Before walking the history, keep the set of \"negative\" refs the\n+ * caller has asked to exclude.\n+ *\n+ * This is used to compute \"rev-list --ancestry-path A..B\", as we need\n+ * to filter the result of \"A..B\" further to the ones that can actually\n+ * reach A.\n+ */\n+static struct commit_list *collect_bottom_commits(struct commit_list *list)\n+{\n+\tstruct commit_list *elem, *bottom = NULL;\n+\tfor (elem = list; elem; elem = elem->next)\n+\t\tif (elem->item->object.flags & UNINTERESTING)\n+\t\t\tcommit_list_insert(elem->item, &bottom);\n+\treturn bottom;\n+}\n+\n static int limit_list(struct rev_info *revs)\n {\n \tint slop = SLOP;\n@@ -653,6 +740,13 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *list = revs->commits;\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n+\tstruct commit_list *bottom = NULL;\n+\n+\tif (revs->ancestry_path) {\n+\t\tbottom = collect_bottom_commits(list);\n+\t\tif (!bottom)\n+\t\t\tdie(\"--ancestry-path given but there is no bottom commits\");\n+\t}\n \n \twhile (list) {\n \t\tstruct commit_list *entry = list;\n@@ -694,6 +788,11 @@ static int limit_list(struct rev_info *revs)\n \tif (revs->cherry_pick)\n \t\tcherry_pick_list(newlist, revs);\n \n+\tif (bottom) {\n+\t\tlimit_to_ancestry(bottom, newlist);\n+\t\tfree_commit_list(bottom);\n+\t}\n+\n \trevs->commits = newlist;\n \treturn 0;\n }\n@@ -1089,6 +1188,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->min_age = approxidate(arg + 8);\n \t} else if (!strcmp(arg, \"--first-parent\")) {\n \t\trevs->first_parent_only = 1;\n+\t} else if (!strcmp(arg, \"--ancestry-path\")) {\n+\t\trevs->ancestry_path = 1;\n+\t\trevs->limited = 1;\n \t} else if (!strcmp(arg, \"-g\") || !strcmp(arg, \"--walk-reflogs\")) {\n \t\tinit_reflog_walk(&revs->reflog_info);\n \t} else if (!strcmp(arg, \"--default\")) {\ndiff --git a/revision.h b/revision.h\nindex 568f1c9..855464f 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -66,6 +66,7 @@ struct rev_info {\n \t\t\treverse_output_stage:1,\n \t\t\tcherry_pick:1,\n \t\t\tbisect:1,\n+\t\t\tancestry_path:1,\n \t\t\tfirst_parent_only:1;\n \n \t/* Diff flags */\ndiff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh\nnew file mode 100755\nindex 0000000..0230724\n--- /dev/null\n+++ b/t/t6019-rev-list-ancestry-path.sh\n@@ -0,0 +1,56 @@\n+#!/bin/sh\n+\n+test_description='--ancestry-path'\n+\n+#          D---E-------F\n+#         /     \\       \\\n+#    B---C---G---H---I---J\n+#   /                     \\\n+#  A-------K---------------L--M\n+#\n+#  D..M                 == E F G H I J K L M\n+#  --ancestry-path D..M == E F H I J L M\n+\n+. ./test-lib.sh\n+\n+test_merge () {\n+\ttest_tick &&\n+\tgit merge -s ours -m \"$2\" \"$1\" &&\n+\tgit tag \"$2\"\n+}\n+\n+test_expect_success setup '\n+\ttest_commit A &&\n+\ttest_commit B &&\n+\ttest_commit C &&\n+\ttest_commit D &&\n+\ttest_commit E &&\n+\ttest_commit F &&\n+\tgit reset --hard C &&\n+\ttest_commit G &&\n+\ttest_merge E H &&\n+\ttest_commit I &&\n+\ttest_merge F J &&\n+\tgit reset --hard A &&\n+\ttest_commit K &&\n+\ttest_merge J L &&\n+\ttest_commit M\n+'\n+\n+test_expect_success 'rev-list D..M' '\n+\tfor c in E F G H I J K L M; do echo $c; done >expect &&\n+\tgit rev-list --format=%s D..M |\n+\tsed -e \"/^commit /d\" |\n+\tsort >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'rev-list --ancestry-path D..M' '\n+\tfor c in E F H I J L M; do echo $c; done >expect &&\n+\tgit rev-list --ancestry-path --format=%s D..M |\n+\tsed -e \"/^commit /d\" |\n+\tsort >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n1.7.1.rc2.265.g8743f\n"},{"id":"140017","messageId":"201004211046.22643.johan@herland.net","threadId":"23537","inReplyTo":"7vochdcjz5.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] revision: --ancestry-path","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-04-21T08:46:22Z","receivedAt":"2010-04-21T08:46:22Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 21 April 2010, Junio C Hamano wrote:\n> Johannes Sixt <j.sixt@viscovery.net> writes:\n> > Am 4/21/2010 9:34, schrieb Johan Herland:\n> >> I can confirm that this patch works with my original (more\n> >> complicated) scenario. I've also played around with combinations of\n> >> --ancestry-path, -- graph and --parents (and even --boundary), and\n> >> AFAICS, the new option does not clobber the other options, and (IMHO)\n> >> it all behaves correctly in the scenarios I've tested.\n> > \n> > How about possible interactions with --reverse;\n> > --date-order/--topo-order, --parents (important for gitk);\n> > --simplify-by-decoration (useful for your problem that triggered\n> > this); --full-history and --simplify-merges with path limiting?\n> \n> These are all good points.\n> \n> I am reasonably sure that parents (specifically, \"rewrite_parents\") is\n> broken.  The new function should cull parents that do not appear on the\n> ancestry path from merges (that is what \"NEEDSWORK\" is about).  It may or\n> may not break gitk, though---these off-path parents are shown as parents\n> of an on-path merge but will be marked as UNINTERESTING.\n\nFWIW, I added the following patch to 'gitk', and then ran it against the \nt6019 test repo as follows:\n\n\tgitk --ancestry-path D..M\n\n...and the resulting graph is exactly what I'd expect; showing the \nuninteresting parents (D, G and K) as \"hollow\" nodes.\n\n\ndiff --git a/gitk-git/gitk b/gitk-git/gitk\nindex 1b0e09a..7749d2a 100644\n--- a/gitk-git/gitk\n+++ b/gitk-git/gitk\n@@ -190,7 +190,7 @@ proc parseviewargs {n arglist} {\n            \"--author=*\" - \"--committer=*\" - \"--grep=*\" - \"-[iE]\" -\n            \"--remove-empty\" - \"--first-parent\" - \"--cherry-pick\" -\n            \"-S*\" - \"--pickaxe-all\" - \"--pickaxe-regex\" -\n-           \"--simplify-by-decoration\" {\n+           \"--simplify-by-decoration\" - \"--ancestry-path\" {\n                # These mean that we get a subset of the commits\n                set filtered 1\n                lappend glflags $arg\n\n\n> I do not think reverse/date-order/topo-order would be affected by this\n> change, as they only change the presentation order of what limit_list()\n> returns;\n> \n> Also simplify-merges and full-history should be Ok, as they control what\n> is done in the current logic in limit_list(), which is an input to the\n> new logic, meaning that the new logic will work on already simplified\n> history.\n> \n> This is not a new problem, but I strongly suspect that cherry-pick is\n> broken the same way wrt \"rewrite_parents\".\n\nI'm not very familiar with \"rewrite_parents\", nor do I know exactly how it \nshould affect/interoperate with --ancestry-path in all cases, but running\n\n\tgit rev-list D..M -- M.t\n\nproduces one commit (M), whereas\n\n\tgit rev-list --ancestry-path D..M -- M.t\n\nproduces nothing, so I suspect there is something not quite right here.\n\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"140019","messageId":"7v8w8hchrv.fsf@alter.siamese.dyndns.org","threadId":"23537","inReplyTo":"7vochdcjz5.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] revision: --ancestry-path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-21T08:49:08Z","receivedAt":"2010-04-21T08:49:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> I am reasonably sure that parents (specifically, \"rewrite_parents\") is\n> broken.  The new function should cull parents that do not appear on the\n> ancestry path from merges (that is what \"NEEDSWORK\" is about).  It may or\n> may not break gitk, though---these off-path parents are shown as parents\n> of an on-path merge but will be marked as UNINTERESTING.\n\nThinking about it a bit more, I think this is Ok, as all the ancestors on\na side branch that is off-path are marked uninteresting, and we do show\nuninteresting parents in the output of an interesting commit.  In fact, if\nyou do \"rev-list --parents HEAD^..HEAD -- .\", on a non-merge non-empty\ncommit, you will see uninteresting HEAD^ shown as the parent of HEAD.\n\n> This is not a new problem, but I strongly suspect that cherry-pick is\n> broken the same way wrt \"rewrite_parents\".\n\nThis is a different and a real issue.  By marking ones that are duplicate\nof commits from the other side as SHOWN, we will spit out a disconnected\nhistory.  It should rewrite the parent list so that children of a commit\nthat is removed due to being a duplicate from the other side point at an\nancestor of that removed commit to keep the history connected.\n"},{"id":"140021","messageId":"7vy6ghb2hm.fsf@alter.siamese.dyndns.org","threadId":"23537","inReplyTo":"201004211046.22643.johan@herland.net","subject":"Re: [PATCH] revision: --ancestry-path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-04-21T09:04:37Z","receivedAt":"2010-04-21T09:04:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland <johan@herland.net> writes:\n\n> I'm not very familiar with \"rewrite_parents\", nor do I know exactly how it \n> should affect/interoperate with --ancestry-path in all cases, but running\n>\n> \tgit rev-list D..M -- M.t\n>\n> produces one commit (M), whereas\n>\n> \tgit rev-list --ancestry-path D..M -- M.t\n>\n> produces nothing, so I suspect there is something not quite right here.\n\nMerge simplification gets in our way big time.\n\n          D---E-------F\n         /     \\       \\\n    B---C---G---H---I---J\n   /                     \\\n  A-------K---------------L--M\n\nWhile traversing the history from M, we notice that M's parent is L, and\nthen further we notice that neither the transition between J to L nor\nbetween K to L change the named path M.t, so we simplify the merge L to\nhave K as its sole parent.  This makes M appear disconnected from D's\ndecendant chain, and causes the TMP_MARK reverse traversal not to work as\nintended.\n"}]}