[PATCH v2] 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 <-- masterThe 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 <gitster@pobox.com>
---
* This simplifies the handling of TMP_MARK (the contract among the
functions is that this is used only locally and the user is responsible
for cleaning them up after use, so there is no need to clear the mark
upfront), and also makes it responsibility of the caller to free the
"bottom" list.
Interdiff since v1 looks like this.
diff -u b/revision.c b/revision.c
--- b/revision.c
+++ b/revision.c
@@ -660,13 +660,11 @@
int made_progress;
/*
- * Clear TMP_MARK and reverse the list so that it will be likely
- * that we would process parents before children.
+ * Reverse the list so that it will be likely that we would
+ * process parents before children.
*/
- for (p = list; p; p = p->next) {
- p->item->object.flags &= ~TMP_MARK;
+ 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;
@@ -705,20 +703,16 @@
*/
for (p = list; p; p = p->next) {
struct commit *c = p->item;
- if (c->object.flags & TMP_MARK) {
- c->object.flags &= ~TMP_MARK;
+ if (c->object.flags & TMP_MARK)
continue;
- }
c->object.flags |= UNINTERESTING;
}
- /* Release the bottom list */
- while (bottom) {
- p = bottom->next;
- bottom->item->object.flags &= ~TMP_MARK;
- free(bottom);
- bottom = p;
- }
+ /* 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);
}
@@ -794,8 +788,10 @@
if (revs->cherry_pick)
cherry_pick_list(newlist, revs);
- if (bottom)
+ if (bottom) {
limit_to_ancestry(bottom, newlist);
+ free_commit_list(bottom);
+ }
revs->commits = newlist;
return 0; revision.c | 102 +++++++++++++++++++++++++++++++++++++
revision.h | 1 +
t/t6019-rev-list-ancestry-path.sh | 56 ++++++++++++++++++++
3 files changed, 159 insertions(+), 0 deletions(-)
create mode 100755 t/t6019-rev-list-ancestry-path.sh
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
--
1.7.1.rc2.265.g8743f
Johan Herland
