diff options
| -rw-r--r-- | revision.c | 102 | ||||
| -rw-r--r-- | revision.h | 1 | ||||
| -rwxr-xr-x | t/t6019-rev-list-ancestry-path.sh | 56 |
3 files changed, 159 insertions, 0 deletions
diff --git a/revision.c b/revision.c index f4b8b38315..71fec3c63a 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 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..0230724ca5 --- /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 |