From ebdc94f3bec7ec54babb21b1d785af0cd75b21e6 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 20 Apr 2010 13:48:39 -0700 Subject: revision: --ancestry-path "rev-list A..H" computes the set of commits that are ancestors of H, but excludes the ones that are ancestors of A. This is useful to see what happened to the history leading to H since A, in the sense that "what does H have that did not exist in A" (e.g. when you have a choice to update to H from A). x---x---A---B---C <-- topic / \ x---x---x---o---o---o---o---M---D---E---F---G <-- dev / \ x---o---o---o---o---o---o---o---o---o---o---o---N---H <-- master The result in the above example would be the commits marked with caps letters (except for A itself, of course), and the ones marked with 'o'. When you want to find out what commits in H are contaminated with the bug introduced by A and need fixing, however, you might want to view only the subset of "A..B" that are actually descendants of A, i.e. excluding the ones marked with 'o'. Introduce a new option --ancestry-path to compute this set with "rev-list --ancestry-path A..B". Note that in practice, you would build a fix immediately on top of A and "git branch --contains A" will give the names of branches that you would need to merge the fix into (i.e. topic, dev and master), so this may not be worth paying the extra cost of postprocessing. Signed-off-by: Junio C Hamano diff --git a/revision.c b/revision.c index f4b8b38..71fec3c 100644 --- a/revision.c +++ b/revision.c @@ -646,6 +646,93 @@ static int still_interesting(struct commit_list *src, unsigned long date, int sl return slop-1; } +/* + * "rev-list --ancestry-path A..B" computes commits that are ancestors + * of B but not ancestors of A but further limits the result to those + * that are descendants of A. This takes the list of bottom commits and + * the result of "A..B" without --ancestry-path, and limits the latter + * further to the ones that can reach one of the commits in "bottom". + */ +static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *list) +{ + struct commit_list *p; + struct commit_list *rlist = NULL; + int made_progress; + + /* + * Reverse the list so that it will be likely that we would + * process parents before children. + */ + for (p = list; p; p = p->next) + commit_list_insert(p->item, &rlist); + + for (p = bottom; p; p = p->next) + p->item->object.flags |= TMP_MARK; + + /* + * Mark the ones that can reach bottom commits in "list", + * in a bottom-up fashion. + */ + do { + made_progress = 0; + for (p = rlist; p; p = p->next) { + struct commit *c = p->item; + struct commit_list *parents; + if (c->object.flags & (TMP_MARK | UNINTERESTING)) + continue; + for (parents = c->parents; + parents; + parents = parents->next) { + if (!(parents->item->object.flags & TMP_MARK)) + continue; + c->object.flags |= TMP_MARK; + made_progress = 1; + break; + } + } + } while (made_progress); + + /* + * NEEDSWORK: decide if we want to remove parents that are + * not marked with TMP_MARK from commit->parents for commits + * in the resulting list. We may not want to do that, though. + */ + + /* + * The ones that are not marked with TMP_MARK are uninteresting + */ + for (p = list; p; p = p->next) { + struct commit *c = p->item; + if (c->object.flags & TMP_MARK) + continue; + c->object.flags |= UNINTERESTING; + } + + /* We are done with the TMP_MARK */ + for (p = list; p; p = p->next) + p->item->object.flags &= ~TMP_MARK; + for (p = bottom; p; p = p->next) + p->item->object.flags &= ~TMP_MARK; + free_commit_list(rlist); +} + +/* + * Before walking the history, keep the set of "negative" refs the + * caller has asked to exclude. + * + * This is used to compute "rev-list --ancestry-path A..B", as we need + * to filter the result of "A..B" further to the ones that can actually + * reach A. + */ +static struct commit_list *collect_bottom_commits(struct commit_list *list) +{ + struct commit_list *elem, *bottom = NULL; + for (elem = list; elem; elem = elem->next) + if (elem->item->object.flags & UNINTERESTING) + commit_list_insert(elem->item, &bottom); + return bottom; +} + static int limit_list(struct rev_info *revs) { int slop = SLOP; @@ -653,6 +740,13 @@ static int limit_list(struct rev_info *revs) struct commit_list *list = revs->commits; struct commit_list *newlist = NULL; struct commit_list **p = &newlist; + struct commit_list *bottom = NULL; + + if (revs->ancestry_path) { + bottom = collect_bottom_commits(list); + if (!bottom) + die("--ancestry-path given but there is no bottom commits"); + } while (list) { struct commit_list *entry = list; @@ -694,6 +788,11 @@ static int limit_list(struct rev_info *revs) if (revs->cherry_pick) cherry_pick_list(newlist, revs); + if (bottom) { + limit_to_ancestry(bottom, newlist); + free_commit_list(bottom); + } + revs->commits = newlist; return 0; } @@ -1089,6 +1188,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg revs->min_age = approxidate(arg + 8); } else if (!strcmp(arg, "--first-parent")) { revs->first_parent_only = 1; + } else if (!strcmp(arg, "--ancestry-path")) { + revs->ancestry_path = 1; + revs->limited = 1; } else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) { init_reflog_walk(&revs->reflog_info); } else if (!strcmp(arg, "--default")) { diff --git a/revision.h b/revision.h index 568f1c9..855464f 100644 --- a/revision.h +++ b/revision.h @@ -66,6 +66,7 @@ struct rev_info { reverse_output_stage:1, cherry_pick:1, bisect:1, + ancestry_path:1, first_parent_only:1; /* Diff flags */ diff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh new file mode 100755 index 0000000..0230724 --- /dev/null +++ b/t/t6019-rev-list-ancestry-path.sh @@ -0,0 +1,56 @@ +#!/bin/sh + +test_description='--ancestry-path' + +# D---E-------F +# / \ \ +# B---C---G---H---I---J +# / \ +# A-------K---------------L--M +# +# D..M == E F G H I J K L M +# --ancestry-path D..M == E F H I J L M + +. ./test-lib.sh + +test_merge () { + test_tick && + git merge -s ours -m "$2" "$1" && + git tag "$2" +} + +test_expect_success setup ' + test_commit A && + test_commit B && + test_commit C && + test_commit D && + test_commit E && + test_commit F && + git reset --hard C && + test_commit G && + test_merge E H && + test_commit I && + test_merge F J && + git reset --hard A && + test_commit K && + test_merge J L && + test_commit M +' + +test_expect_success 'rev-list D..M' ' + for c in E F G H I J K L M; do echo $c; done >expect && + git rev-list --format=%s D..M | + sed -e "/^commit /d" | + sort >actual && + test_cmp expect actual +' + +test_expect_success 'rev-list --ancestry-path D..M' ' + for c in E F H I J L M; do echo $c; done >expect && + git rev-list --ancestry-path --format=%s D..M | + sed -e "/^commit /d" | + sort >actual && + test_cmp expect actual +' + +test_done -- cgit v0.10.2-6-g49f6 From f70d0586d68c41304e7ff95c7fa2a06b74896e77 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Fri, 4 Jun 2010 01:17:33 +0200 Subject: Documentation/rev-list-options.txt: Fix missing line in example history graph In the detailed explanation of how the revision machinery does history simplification, the current text presents an example history and explains how various options of the revision machinery affect the resulting list of commits. The first simplification mode mentioned is the default mode, in which a number of commits is omitted from the example graph according to the history simplification rules. The text states (among other things) that commit "C was considered via N, but is TREESAME", and therefore omitted. However, the accompanying graph does not list the effect on the implicit parentage, i.e. that commit I takes C's place as a parent of N. Running 'git rev-list --parents P' does indeed list I as a second parent of N, and the accompanying graph should therefore also show this line. Signed-off-by: Johan Herland Cc: Thomas Rast Signed-off-by: Junio C Hamano diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt index b9fb7a8..81815e1 100644 --- a/Documentation/rev-list-options.txt +++ b/Documentation/rev-list-options.txt @@ -440,7 +440,7 @@ This results in: + ----------------------------------------------------------------------- .-A---N---O - / / + / / / I---------D ----------------------------------------------------------------------- + -- cgit v0.10.2-6-g49f6 From 57456ef459f137cf81c1875f771ab9485b1fa810 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Fri, 4 Jun 2010 01:17:35 +0200 Subject: Documentation/rev-list-options.txt: Explain --ancestry-path Add a short paragraph explaining --ancestry-path, followed by a more detailed example. This mirrors how the other history simplification options are documented. Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt index 81815e1..73569c0 100644 --- a/Documentation/rev-list-options.txt +++ b/Documentation/rev-list-options.txt @@ -384,6 +384,14 @@ Default mode:: merges from the resulting history, as there are no selected commits contributing to this merge. +--ancestry-path:: + + When given a range of commits to display (e.g. 'commit1..commit2' + or 'commit2 {caret}commit1'), only display commits that exist + directly on the ancestry chain between the 'commit1' and + 'commit2', i.e. commits that are both descendants of 'commit1', + and ancestors of 'commit2'. + A more detailed explanation follows. Suppose you specified `foo` as the . We shall call commits @@ -511,8 +519,6 @@ Note that without '\--full-history', this still simplifies merges: if one of the parents is TREESAME, we follow only that one, so the other sides of the merge are never walked. -Finally, there is a fourth simplification mode available: - --simplify-merges:: First, build a history graph in the same way that @@ -554,6 +560,46 @@ Note the major differences in `N` and `P` over '\--full-history': removed completely, because it had one parent and is TREESAME. -- +Finally, there is a fifth simplification mode available: + +--ancestry-path:: + + Limit the displayed commits to those directly on the ancestry + chain between the "from" and "to" commits in the given commit + range. I.e. only display commits that are ancestor of the "to" + commit, and descendants of the "from" commit. ++ +As an example use case, consider the following commit history: ++ +----------------------------------------------------------------------- + D---E-------F + / \ \ + B---C---G---H---I---J + / \ + A-------K---------------L--M +----------------------------------------------------------------------- ++ +A regular 'D..M' computes the set of commits that are ancestors of `M`, +but excludes the ones that are ancestors of `D`. This is useful to see +what happened to the history leading to `M` since `D`, in the sense +that "what does `M` have that did not exist in `D`". The result in this +example would be all the commits, except `A` and `B` (and `D` itself, +of course). ++ +When we want to find out what commits in `M` are contaminated with the +bug introduced by `D` and need fixing, however, we might want to view +only the subset of 'D..M' that are actually descendants of `D`, i.e. +excluding `C` and `K`. This is exactly what the '\--ancestry-path' +option does. Applied to the 'D..M' range, it results in: ++ +----------------------------------------------------------------------- + E-------F + \ \ + G---H---I---J + \ + L--M +----------------------------------------------------------------------- + The '\--simplify-by-decoration' option allows you to view only the big picture of the topology of the history, by omitting commits that are not referenced by tags. Commits are marked as !TREESAME -- cgit v0.10.2-6-g49f6 From 97b03c353856602a3c30b01baae1efb8dfe4243e Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Fri, 4 Jun 2010 01:17:36 +0200 Subject: revision: Fix typo in --ancestry-path error message Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano diff --git a/revision.c b/revision.c index 71fec3c..eb6f849 100644 --- a/revision.c +++ b/revision.c @@ -745,7 +745,7 @@ static int limit_list(struct rev_info *revs) if (revs->ancestry_path) { bottom = collect_bottom_commits(list); if (!bottom) - die("--ancestry-path given but there is no bottom commits"); + die("--ancestry-path given but there are no bottom commits"); } while (list) { -- cgit v0.10.2-6-g49f6 From cb7529e13bce186f8b883c9fbb08602cd3a0795f Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Fri, 4 Jun 2010 01:17:37 +0200 Subject: revision: Turn off history simplification in --ancestry-path mode When using --ancestry-path together with history simplification (typically triggered by path limiting), history simplification would get in the way of --ancestry-path by prematurely removing the parent links between commits on which the ancestry path calculations are made. This patch disables this history simplification when --ancestry-path is enabled. This is similar to what e.g. --full-history already does. The patch also includes a simple testcase verifying that --ancestry-path works together with path limiting. Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano diff --git a/revision.c b/revision.c index eb6f849..96d7fa7 100644 --- a/revision.c +++ b/revision.c @@ -1190,6 +1190,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg revs->first_parent_only = 1; } else if (!strcmp(arg, "--ancestry-path")) { revs->ancestry_path = 1; + revs->simplify_history = 0; revs->limited = 1; } else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) { init_reflog_walk(&revs->reflog_info); diff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh index 0230724..7641029 100755 --- a/t/t6019-rev-list-ancestry-path.sh +++ b/t/t6019-rev-list-ancestry-path.sh @@ -10,6 +10,9 @@ test_description='--ancestry-path' # # D..M == E F G H I J K L M # --ancestry-path D..M == E F H I J L M +# +# D..M -- M.t == M +# --ancestry-path D..M -- M.t == M . ./test-lib.sh @@ -53,4 +56,18 @@ test_expect_success 'rev-list --ancestry-path D..M' ' test_cmp expect actual ' +test_expect_success 'rev-list D..M -- M.t' ' + echo M >expect && + git rev-list --format=%s D..M -- M.t | + sed -e "/^commit /d" >actual && + test_cmp expect actual +' + +test_expect_success 'rev-list --ancestry-patch D..M -- M.t' ' + echo M >expect && + git rev-list --ancestry-path --format=%s D..M -- M.t | + sed -e "/^commit /d" >actual && + test_cmp expect actual +' + test_done -- cgit v0.10.2-6-g49f6