{"thread":{"id":"24000","subject":"[PATCH 0/5] revision: --ancestry-path, take 2","startedAt":"2010-06-03T23:17:32Z","lastAt":"2010-06-03T23:17:37Z","messageCount":6,"participants":["Johan Herland"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"142933","messageId":"1275607057-26645-1-git-send-email-johan@herland.net","threadId":"24000","inReplyTo":null,"subject":"[PATCH 0/5] revision: --ancestry-path, take 2","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-06-03T23:17:32Z","receivedAt":"2010-06-03T23:17:32Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Hi,\n\nThis is an attempt to resurrect the --ancestry-path patch that Junio\nprovided on 2010-04-21. In addition to his original patch, I've added\na fix for the interaction between --ancestry-path and history\nsimplification, plus documentation and a couple of other small fixes.\n\nI'm unsure if there are more bugs/problems in the interaction between\n--ancestry-path and other rev-list options that I'm not yet aware of.\n\n\nHave fun! :)\n\n...Johan\n\n\nJohan Herland (4):\n  Documentation/rev-list-options.txt: Fix missing line in example history graph\n  Documentation/rev-list-options.txt: Explain --ancestry-path\n  revision: Fix typo in --ancestry-path error message\n  revision: Turn off history simplification in --ancestry-path mode\n\nJunio C Hamano (1):\n  revision: --ancestry-path\n\n Documentation/rev-list-options.txt |   52 ++++++++++++++++-\n revision.c                         |  107 ++++++++++++++++++++++++++++++++++++\n revision.h                         |    1 +\n t/t6019-rev-list-ancestry-path.sh  |   73 ++++++++++++++++++++++++\n 4 files changed, 230 insertions(+), 3 deletions(-)\n create mode 100755 t/t6019-rev-list-ancestry-path.sh\n"},{"id":"142935","messageId":"1275607057-26645-2-git-send-email-johan@herland.net","threadId":"24000","inReplyTo":"1275607057-26645-1-git-send-email-johan@herland.net","subject":"[PATCH 1/5] Documentation/rev-list-options.txt: Fix missing line in example history graph","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-06-03T23:17:33Z","receivedAt":"2010-06-03T23:17:33Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"In the detailed explanation of how the revision machinery does history\nsimplification, the current text presents an example history and explains\nhow various options of the revision machinery affect the resulting list\nof commits. The first simplification mode mentioned is the default mode,\nin which a number of commits is omitted from the example graph according\nto the history simplification rules. The text states (among other things)\nthat commit \"C was considered via N, but is TREESAME\", and therefore\nomitted. However, the accompanying graph does not list the effect on the\nimplicit parentage, i.e. that commit I takes C's place as a parent of N.\n\nRunning 'git rev-list --parents P' does indeed list I as a second parent\nof N, and the accompanying graph should therefore also show this line.\n\nSigned-off-by: Johan Herland <johan@herland.net>\nCc: Thomas Rast <trast@student.ethz.ch>\n---\n Documentation/rev-list-options.txt |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex b9fb7a8..81815e1 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -440,7 +440,7 @@ This results in:\n +\n -----------------------------------------------------------------------\n \t  .-A---N---O\n-\t /         /\n+\t /     /   /\n \tI---------D\n -----------------------------------------------------------------------\n +\n--\n1.7.0.4\n"},{"id":"142934","messageId":"1275607057-26645-3-git-send-email-johan@herland.net","threadId":"24000","inReplyTo":"1275607057-26645-1-git-send-email-johan@herland.net","subject":"[PATCH 2/5] revision: --ancestry-path","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-06-03T23:17:34Z","receivedAt":"2010-06-03T23:17:34Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Junio C Hamano <gitster@pobox.com>\n\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               x---x---A---B---C  <-- topic\n              /                 \\\n     x---x---x---o---o---o---o---M---D---E---F---G  <-- dev\n    /                                             \\\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>\nSigned-off-by: Johan Herland <johan@herland.net>\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.0.4\n"},{"id":"142937","messageId":"1275607057-26645-4-git-send-email-johan@herland.net","threadId":"24000","inReplyTo":"1275607057-26645-1-git-send-email-johan@herland.net","subject":"[PATCH 3/5] Documentation/rev-list-options.txt: Explain --ancestry-path","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-06-03T23:17:35Z","receivedAt":"2010-06-03T23:17:35Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Add a short paragraph explaining --ancestry-path, followed by a more\ndetailed example. This mirrors how the other history simplification options\nare documented.\n\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n Documentation/rev-list-options.txt |   50 ++++++++++++++++++++++++++++++++++-\n 1 files changed, 48 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 81815e1..a33dd00 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -384,6 +384,14 @@ Default mode::\n \tmerges from the resulting history, as there are no selected\n \tcommits contributing to this merge.\n\n+--ancestry-path::\n+\n+\tWhen given a range of commits to display (e.g. 'commit1..commit2'\n+\tor 'commit2 {caret}commit1'), only display commits that exist\n+\tdirectly on the ancestry chain between the 'commit1' and\n+\t'commit2', i.e. commits that are both descendants of 'commit1',\n+\tand ancestors of 'commit2'.\n+\n A more detailed explanation follows.\n\n Suppose you specified `foo` as the <paths>.  We shall call commits\n@@ -511,8 +519,6 @@ Note that without '\\--full-history', this still simplifies merges: if\n one of the parents is TREESAME, we follow only that one, so the other\n sides of the merge are never walked.\n\n-Finally, there is a fourth simplification mode available:\n-\n --simplify-merges::\n\n \tFirst, build a history graph in the same way that\n@@ -554,6 +560,46 @@ Note the major differences in `N` and `P` over '\\--full-history':\n   removed completely, because it had one parent and is TREESAME.\n --\n\n+Finally, there is a fifth simplification mode available:\n+\n+--ancestry-path::\n+\n+\tLimit the displayed commits to those directly on the ancestry\n+\tchain between the \"from\" and \"to\" commits in the given commit\n+\trange. I.e. only display commits that are ancestor of the \"to\"\n+\tcommit, and descendants of the \"from\" commit.\n++\n+As an example use case, consider the following commit history:\n++\n+-----------------------------------------------------------------------\n+\t    D---E-------F\n+\t   /     \\       \\\n+\t  B---C---G---H---I---J\n+\t /                     \\\n+\tA-------K---------------L--M\n+-----------------------------------------------------------------------\n++\n+A regular 'D..M' computes the set of commits that are ancestors of `M`,\n+but excludes the ones that are ancestors of `D`. This is useful to see\n+what happened to the history leading to `M` since `D`, in the sense\n+that \"what does `M` have that did not exist in `D`\". The result in this\n+example would be all the commits, except `A` and `B` (and `D` itself,\n+of course).\n++\n+When we want to find out what commits in `M` are contaminated with the\n+bug introduced by `D` and need fixing, however, we might want to view\n+only the subset of 'D..M' that are actually descendants of `D`, i.e.\n+excluding `C` and `K`. This is exactly what the '\\--ancestry-path'\n+option does. Applied to the 'D..M' range, it results in:\n++\n+-----------------------------------------------------------------------\n+\t        E-------F\n+\t         \\       \\\n+\t          G---H---I---J\n+\t                       \\\n+\t                        L--M\n+-----------------------------------------------------------------------\n+\n The '\\--simplify-by-decoration' option allows you to view only the\n big picture of the topology of the history, by omitting commits\n that are not referenced by tags.  Commits are marked as !TREESAME\n--\n1.7.0.4\n"},{"id":"142936","messageId":"1275607057-26645-5-git-send-email-johan@herland.net","threadId":"24000","inReplyTo":"1275607057-26645-1-git-send-email-johan@herland.net","subject":"[PATCH 4/5] revision: Fix typo in --ancestry-path error message","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-06-03T23:17:36Z","receivedAt":"2010-06-03T23:17:36Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Signed-off-by: Johan Herland <johan@herland.net>\n---\n revision.c |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex cb91094..7eeadb4 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -751,7 +751,7 @@ static int limit_list(struct rev_info *revs)\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\t\tdie(\"--ancestry-path given but there are no bottom commits\");\n \t}\n\n \twhile (list) {\n--\n1.7.0.4\n"},{"id":"142938","messageId":"1275607057-26645-6-git-send-email-johan@herland.net","threadId":"24000","inReplyTo":"1275607057-26645-1-git-send-email-johan@herland.net","subject":"[PATCH 5/5] revision: Turn off history simplification in --ancestry-path mode","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-06-03T23:17:37Z","receivedAt":"2010-06-03T23:17:37Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"When using --ancestry-path together with history simplification (typically\ntriggered by path limiting), history simplification would get in the way of\n--ancestry-path by prematurely removing the parent links between commits on\nwhich the ancestry path calculations are made.\n\nThis patch disables this history simplification when --ancestry-path is\nenabled. This is similar to what e.g. --full-history already does.\n\nThe patch also includes a simple testcase verifying that --ancestry-path\nworks together with path limiting.\n\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n revision.c                        |    1 +\n t/t6019-rev-list-ancestry-path.sh |   17 +++++++++++++++++\n 2 files changed, 18 insertions(+), 0 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 7eeadb4..3f95680 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1194,6 +1194,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->first_parent_only = 1;\n \t} else if (!strcmp(arg, \"--ancestry-path\")) {\n \t\trevs->ancestry_path = 1;\n+\t\trevs->simplify_history = 0;\n \t\trevs->limited = 1;\n \t} else if (!strcmp(arg, \"-g\") || !strcmp(arg, \"--walk-reflogs\")) {\n \t\tinit_reflog_walk(&revs->reflog_info);\ndiff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh\nindex 0230724..7641029 100755\n--- a/t/t6019-rev-list-ancestry-path.sh\n+++ b/t/t6019-rev-list-ancestry-path.sh\n@@ -10,6 +10,9 @@ test_description='--ancestry-path'\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+#  D..M -- M.t                 == M\n+#  --ancestry-path D..M -- M.t == M\n\n . ./test-lib.sh\n\n@@ -53,4 +56,18 @@ test_expect_success 'rev-list --ancestry-path D..M' '\n \ttest_cmp expect actual\n '\n\n+test_expect_success 'rev-list D..M -- M.t' '\n+\techo M >expect &&\n+\tgit rev-list --format=%s D..M -- M.t |\n+\tsed -e \"/^commit /d\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'rev-list --ancestry-patch 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 test_done\n--\n1.7.0.4\n"}]}