[PATCH 0/5] revision: --ancestry-path, take 2

[PATCH 0/5] revision: --ancestry-path, take 2

[Johan Herland]

Hi,

This is an attempt to resurrect the --ancestry-path patch that Junio
provided on 2010-04-21. In addition to his original patch, I've added
a fix for the interaction between --ancestry-path and history
simplification, plus documentation and a couple of other small fixes.

I'm unsure if there are more bugs/problems in the interaction between
--ancestry-path and other rev-list options that I'm not yet aware of.


Have fun! :)

...Johan


Johan Herland (4):
  Documentation/rev-list-options.txt: Fix missing line in example history graph
  Documentation/rev-list-options.txt: Explain --ancestry-path
  revision: Fix typo in --ancestry-path error message
  revision: Turn off history simplification in --ancestry-path mode

Junio C Hamano (1):
  revision: --ancestry-path

 Documentation/rev-list-options.txt |   52 ++++++++++++++++-
 revision.c                         |  107 ++++++++++++++++++++++++++++++++++++
 revision.h                         |    1 +
 t/t6019-rev-list-ancestry-path.sh  |   73 ++++++++++++++++++++++++
 4 files changed, 230 insertions(+), 3 deletions(-)
 create mode 100755 t/t6019-rev-list-ancestry-path.sh

[PATCH 1/5] Documentation/rev-list-options.txt: Fix missing line in example history graph

[Johan Herland]

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 <johan@herland.net>
Cc: Thomas Rast <trast@student.ethz.ch>
---
 Documentation/rev-list-options.txt |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

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
 -----------------------------------------------------------------------
 +
--
1.7.0.4

[PATCH 2/5] revision: --ancestry-path

[Johan Herland]

From: Junio C Hamano <gitster@pobox.com>

"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 <gitster@pobox.com>
Signed-off-by: Johan Herland <johan@herland.net>
---
 revision.c                        |  106 +++++++++++++++++++++++++++++++++++++
 revision.h                        |    1 +
 t/t6019-rev-list-ancestry-path.sh |   56 +++++++++++++++++++
 3 files changed, 163 insertions(+), 0 deletions(-)
 create mode 100755 t/t6019-rev-list-ancestry-path.sh

diff --git a/revision.c b/revision.c
index f4b8b38..cb91094 100644
--- a/revision.c
+++ b/revision.c
@@ -646,6 +646,99 @@ 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;
+
+	/*
+	 * Clear TMP_MARK and 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;
+		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) {
+			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;
+	}
+	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 +746,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 +794,9 @@ static int limit_list(struct rev_info *revs)
 	if (revs->cherry_pick)
 		cherry_pick_list(newlist, revs);

+	if (bottom)
+		limit_to_ancestry(bottom, newlist);
+
 	revs->commits = newlist;
 	return 0;
 }
@@ -1089,6 +1192,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.0.4

[PATCH 3/5] Documentation/rev-list-options.txt: Explain --ancestry-path

[Johan Herland]

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 <johan@herland.net>
---
 Documentation/rev-list-options.txt |   50 ++++++++++++++++++++++++++++++++++-
 1 files changed, 48 insertions(+), 2 deletions(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 81815e1..a33dd00 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
@@ -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
--
1.7.0.4

[PATCH 4/5] revision: Fix typo in --ancestry-path error message

[Johan Herland]

Signed-off-by: Johan Herland <johan@herland.net>
---
 revision.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/revision.c b/revision.c
index cb91094..7eeadb4 100644
--- a/revision.c
+++ b/revision.c
@@ -751,7 +751,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) {
--
1.7.0.4

[PATCH 5/5] revision: Turn off history simplification in --ancestry-path mode

[Johan Herland]

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 <johan@herland.net>
---
 revision.c                        |    1 +
 t/t6019-rev-list-ancestry-path.sh |   17 +++++++++++++++++
 2 files changed, 18 insertions(+), 0 deletions(-)

diff --git a/revision.c b/revision.c
index 7eeadb4..3f95680 100644
--- a/revision.c
+++ b/revision.c
@@ -1194,6 +1194,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
--
1.7.0.4