diff options
| -rw-r--r-- | Documentation/rev-list-options.txt | 52 | ||||
| -rw-r--r-- | revision.c | 103 | ||||
| -rw-r--r-- | revision.h | 1 | ||||
| -rwxr-xr-x | t/t6019-rev-list-ancestry-path.sh | 73 |
4 files changed, 226 insertions, 3 deletions
diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt index b9fb7a86bd..73569c073e 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 <paths>. We shall call commits @@ -440,7 +448,7 @@ This results in: + ----------------------------------------------------------------------- .-A---N---O - / / + / / / I---------D ----------------------------------------------------------------------- + @@ -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 diff --git a/revision.c b/revision.c index b209d493e1..7847921658 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 are 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,10 @@ 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->simplify_history = 0; + 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 568f1c98de..855464f144 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 0000000000..76410293b3 --- /dev/null +++ b/t/t6019-rev-list-ancestry-path.sh @@ -0,0 +1,73 @@ +#!/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 +# +# D..M -- M.t == M +# --ancestry-path D..M -- M.t == 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_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 |