merge-base: add --merge-child option

This is helpful when examining branches with disjoint roots, for example because one is periodically merged into a subtree of the other.

With the --merge-child option, "git merge-base" will print a first-parent ancestor of the first revision given, where the commit printed is either a merge-base of the supplied revisions or a merge for which one of its parents (not the first) is a merge-base.

For example, given the history:

        A---C---G
             \
        B-----D---F
         \
          E

we have:

        $ git merge-base F E
        B

        $ git merge-base --merge-child F E
        D

	$ git merge-base F G
	C

	$ git merge-base --merge-child F G
	C

        $ git log --left-right F...E
        < F
        < D
        < C
        < A
        > E

        $ git log --left-right F...E --not $(git merge-base --merge-child F E)
        < F
        > E

The git-log case is useful because it allows us to limit the range of commits that we are examining for patch-identical changes when using --cherry. For example with git-gui in git.git I know that anything before the last merge of git-gui is not interesting:

        $ time git log --cherry master...git-gui/master >/dev/null
        real    0m32.731s
        user    0m31.956s
        sys     0m0.664s

        $ time git log --cherry master...git-gui/master --not \
                $(git merge-base --merge-child master git-gui/master) \
                >/dev/null
        real    0m2.296s
        user    0m2.193s
        sys     0m0.092s

The first commit is a small prerequisite to extract a useful function from builtin/tag.c to commit.c. The second is the main change (the commit message is identical to the text before this paragraph).

I'm not convinced that '--merge-child' is the right name for this but I think the functionality itself is useful.

John Keeping (2):
commit: add commit_list_contains function
merge-base: add --merge-child option

 Documentation/git-merge-base.txt |  6 ++++
 builtin/merge-base.c             | 61 ++++++++++++++++++++++++++++++++++++++--
 builtin/tag.c                    | 10 +------
 commit.c                         |  8 ++++++
 commit.h                         |  1 +
 t/t6010-merge-base.sh            | 25 ++++++++++++++--
 6 files changed, 98 insertions(+), 13 deletions(-)

1.8.3.rc1.289.gcb3647f

Wouldn't "--left-right --ancestry-path F...E" do the job? I can't immediately see how that differs.

Unfortunately, that syntax doesn't currently work - I just stumbled across this problem, and my "history traversal refinements" series in pu fixes it, somewhat incidentally to the main subject in there.

However, without that patch, the alternative way of expressing it:

"--left-right --ancestry path F E --not $(git merge-base --all F E)"

should still work. Unless --left-right is magic for "..."? If it is, then my patch is more significant than I thought.

My series will also be better at optimising away D too, through a combination of my and Junio's efforts. Try it out.

On this subject, is there any way to exclude a path from a log query? Is there a "not" operator for paths? Might be another way of doing this - disjoint histories probably have disjoint paths...

Kevin

You're right (and I was wrong in my reply to Junio's parallel message) ancestry path does seem to be what I want:

    $ git rev-list --left-right --count master...git-gui/master
    31959   5

    $ git rev-list --ancestry-path --left-right --count \
            master...git-gui/master
    2056    5

    $ git rev-list --ancestry-path --left-right --count \
            master...git-gui/master \
            --not $(git merge-base --all master git-gui/master)
    2056    5

However, this doesn't seem to make a difference to the time taken when I add in --cherry-mark (which is why I was partially correct in the parallel thread - it doesn't have the effect on cherry-mark that I want it to):

    $ time git rev-list --ancestry-path --left-right --count --cherry-mark \
            origin/master...git-gui/master 
    2056    5       0

    real    0m32.266s
    user    0m31.522s
    sys     0m0.749s

    $ time git rev-list  --left-right --count --cherry-mark \
            origin/master...git-gui/master
    31959   5       0

    real    0m32.140s
    user    0m31.337s
    sys     0m0.807s

This seems to be caused by the code in revision.c::limit_list() which does the cherry detection then limits to left/right and only then applies the ancestry path. I haven't looked further than that, but is there any reason not to apply the ancestry path restriction before looking for patch-identical commits?

Yes, --left-right only applies to symmetric differences ("..."). But I get the results above both on master and on pu.

That relates to another idea I had about optimizing the detection of patch-identical commits. If the smaller side of a symmetric difference is quite small (as it is likely to be if it's a topic branch), would it be a good idea to calculate the set of paths touched by commits on that side and then skip calculating the patch ID for any commits that touch paths outside that set. The tree comparison is a lot cheaper than doing a diff on all of the files.

No I didn't. I forgot to update my $PATH when I built on master - those results are from pu. master says:

fatal: --ancestry-path given but there are no bottom commits

That certainly sounds like it's doing it the wrong way round. At first sight, it seems obviously suboptimal.

Well, then it looks like we have a user for that particular syntax. Seemed a bit esoteric to me :) Although I realised after sending my mail you could also use

git log --ancestry-path --left-right E...F --not $(git merge-base
--all E F)

which looks like we're having to repeat ourselves because it's not paying attention...

I hit it because one of my optimisations relies on knowing the bottom commits, and I made absolutely sure I was using the exactly same definition of "bottom" as --ancestry-path. And then I found that my optimisations didn't work properly with "..."

I suggest we pull my patch out from the more complex optimisation series so it can proceed to next faster. It shouldn't have to wait for all my new fancy stuff - it's fixing something that appears to be a clear bug.

Although Junio did have a comment about the implementation - I'll revisit it tomorrow and send a revised version separately, if everyone thinks that's sensible.

Sounds cute. Go for it :)

Kevin

You are half wrong; "--left-right" is about "do we show the </>/= marker in the output?", so it is true that it does not make sense without "...", but the reverse is not true: A...B does not and should not imply --left-right.

The repetition I meant is that by the definition of ancestry-path, the above would seem to be equivalent to

  git log --ancestry-path --left-right E F --not $(git merge-base --all E F) $(git merge-base --all E F)

Anyway, revised separated-out version of the patch follows.

Kevin

This patch is a revised form of the one in my "history traversal refinements" series. Pulled out to allow it to proceed faster, given that John Keeping has found a use for the command.

I suggest this is placed onto pu ahead of the existing series, dropping the equivalent final commit there. And then hopefully this can proceed to next faster.

(Dropping that commit will drop the only --ancestry-path A...B test in t6111, meaning no immediate dependencies. But the next version of that series will be sent with t6111 testing and expecting a pass due to this fix being in.)

Kevin Bracey (2):
t6019: demonstrate --ancestry-path A...B breakage revision.c: treat A...B merge bases as if manually specified

 revision.c                        | 17 +++++++++++++++++
 revision.h                        |  1 +
 t/t6019-rev-list-ancestry-path.sh | 21 ++++++++++++++++++++-
 3 files changed, 38 insertions(+), 1 deletion(-)

1.8.3.rc0.28.g4b02ef5

---
 t/t6019-rev-list-ancestry-path.sh | 21 ++++++++++++++++++++-
 1 file changed, 20 insertions(+), 1 deletion(-)

index 39b4cb0..5287f6a 100755
@@ -13,6 +13,9 @@ test_description='--ancestry-path'
 #
 #  D..M -- M.t                 == M
 #  --ancestry-path D..M -- M.t == M
+#
+#  F...I                 == F G H I
+#  --ancestry-path F...I == F H I
 
 . ./test-lib.sh
 

@@ -63,13 +66,29 @@ test_expect_success 'rev-list D..M -- M.t' '
 	test_cmp expect actual
 '
 
-test_expect_success 'rev-list --ancestry-patch D..M -- M.t' '
+test_expect_success 'rev-list --ancestry-path 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_expect_success 'rev-list F...I' '
+	for c in F G H I; do echo $c; done >expect &&
+	git rev-list --format=%s F...I |
+	sed -e "/^commit /d" |
+	sort >actual &&
+	test_cmp expect actual
+'
+
+test_expect_failure 'rev-list --ancestry-path F...I' '
+	for c in F H I; do echo $c; done >expect &&
+	git rev-list --ancestry-path --format=%s F...I |
+	sed -e "/^commit /d" |
+	sort >actual &&
+	test_cmp expect actual
+'
+
 #   b---bc
 #  / \ /
 # a   X

1.8.3.rc0.28.g4b02ef5

The documentation assures users that "A...B" is defined as "A B --not $(git merge-base --all A B)". This wasn't in fact quite true, because the calculated merge bases were not sent to add_rev_cmdline().

The main effect of this was that although

  git rev-list --ancestry-path A B --not $(git merge-base --all A B)

worked, the simpler form

  git rev-list --ancestry-path A...B

failed with a "no bottom commits" error.

Other potential users of bottom commits could also be affected by this problem, if they examine revs->cmdline_info; I came across the issue in my proposed history traversal refinements series.

So ensure that the calculated merge bases are sent to add_rev_cmdline(), flagged with new 'whence' enum value REV_CMD_MERGE_BASE.

---
 revision.c                        | 17 +++++++++++++++++
 revision.h                        |  1 +
 t/t6019-rev-list-ancestry-path.sh |  2 +-
 3 files changed, 19 insertions(+), 1 deletion(-)

index a67b615..7f7a8ab 100644
@@ -915,6 +915,19 @@ static void add_rev_cmdline(struct rev_info *revs,
 	info->nr++;
 }
 
+static void add_rev_cmdline_list(struct rev_info *revs,
+				 struct commit_list *commit_list,
+				 int whence,
+				 unsigned flags)
+{
+	while (commit_list) {
+		struct object *object = &commit_list->item->object;
+		add_rev_cmdline(revs, object, sha1_to_hex(object->sha1),
+				whence, flags);
+		commit_list = commit_list->next;
+	}
+}
+
 struct all_refs_cb {
 	int all_flags;
 	int warned_bad_reflog;

@@ -1092,6 +1105,7 @@ static void prepare_show_merge(struct rev_info *revs)
 	add_pending_object(revs, &head->object, "HEAD");
 	add_pending_object(revs, &other->object, "MERGE_HEAD");
 	bases = get_merge_bases(head, other, 1);
+	add_rev_cmdline_list(revs, bases, REV_CMD_MERGE_BASE, UNINTERESTING);
 	add_pending_commit_list(revs, bases, UNINTERESTING);
 	free_commit_list(bases);
 	head->object.flags |= SYMMETRIC_LEFT;

@@ -1179,6 +1193,9 @@ int handle_revision_arg(const char *arg_, struct rev_info *revs, int flags, unsi
 
 			if (symmetric) {
 				exclude = get_merge_bases(a, b, 1);
+				add_rev_cmdline_list(revs, exclude,
+						     REV_CMD_MERGE_BASE,
+						     flags_exclude);
 				add_pending_commit_list(revs, exclude,
 							flags_exclude);
 				free_commit_list(exclude);

index 01bd2b7..878a555 100644
@@ -35,6 +35,7 @@ struct rev_cmdline_info {
 			REV_CMD_PARENTS_ONLY,
 			REV_CMD_LEFT,
 			REV_CMD_RIGHT,
+			REV_CMD_MERGE_BASE,
 			REV_CMD_REV
 		} whence;
 		unsigned flags;

index 5287f6a..dd5b0e5 100755
@@ -81,7 +81,7 @@ test_expect_success 'rev-list F...I' '
 	test_cmp expect actual
 '
 
-test_expect_failure 'rev-list --ancestry-path F...I' '
+test_expect_success 'rev-list --ancestry-path F...I' '
 	for c in F H I; do echo $c; done >expect &&
 	git rev-list --ancestry-path --format=%s F...I |
 	sed -e "/^commit /d" |

1.8.3.rc0.28.g4b02ef5

Looks good. Thanks.

Kevin Bracey venit, vidit, dixit 13.05.2013 16:26:

It is certainly true that "git log --cherry" needs much less information than what the merge base machinery provides. I've been experimenting with that in order to get the speedup which is necessary for replacing the "git cherry" code with calls into the revision walker using "--cherry".

But I can't wrap my head around the feature proposed here, sorry.

Michael

I think the revision machinery is the same speed as the "git cherry" code, it's just that "git cherry" ignores merges and the cherry code in revision.c doesn't.

Since the patch ID of a merge is just being calculated to its first parent, I don't think it's meaningful to consider merges for "log --cherry" but I can't quite convince myself that there's no corner case where it is.

The following patch makes the revision cherry machinery ignore merges unconditionally. With it applied, there's not noticeable difference in speed between "git cherry" and "git log --cherry".

-- >8 --

index a67b615..19d0683 100644
@@ -640,6 +640,11 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 
 		if (flags & BOUNDARY)
 			continue;
+
+		/* Patch ID is meaningless for merges. */
+		if (commit->parents && commit->parents->next)
+			continue;
+
 		/*
 		 * If we have fewer left, left_first is set and we omit
 		 * commits on the right branch in this loop.  If we have

@@ -661,6 +666,11 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 
 		if (flags & BOUNDARY)
 			continue;
+
+		/* Patch ID is meaningless for merges. */
+		if (commit->parents && commit->parents->next)
+			continue;
+
 		/*
 		 * If we have fewer left, left_first is set and we omit
 		 * commits on the left branch in this loop.

1.8.3.rc3.372.g721bad8

With the patch below, the --ancestry-path version drops to under 2 seconds.

I'm not sure if this is a good idea though. It helps me say "I know nothing that isn't on the ancestry path can be patch-identical, so don't bother checking if it is" but it regresses users who want the full cherry-pick check while only limiting the output.

Perhaps we need --cherry-no-uninteresting to apply the first 3 hunks of the patch at runtime :-S

-- >8 --

index de3b058..d721d83 100644
@@ -837,7 +837,7 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 	for (p = list; p; p = p->next) {
 		struct commit *commit = p->item;
 		unsigned flags = commit->object.flags;
-		if (flags & BOUNDARY)
+		if (flags & (BOUNDARY | UNINTERESTING))
 			;
 		else if (flags & SYMMETRIC_LEFT)
 			left_count++;

@@ -858,7 +858,7 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 		struct commit *commit = p->item;
 		unsigned flags = commit->object.flags;
 
-		if (flags & BOUNDARY)
+		if (flags & (BOUNDARY | UNINTERESTING))
 			continue;
 		/*
 		 * If we have fewer left, left_first is set and we omit

@@ -879,7 +879,7 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 		struct patch_id *id;
 		unsigned flags = commit->object.flags;
 
-		if (flags & BOUNDARY)
+		if (flags & (BOUNDARY | UNINTERESTING))
 			continue;
 		/*
 		 * If we have fewer left, left_first is set and we omit

@@ -1103,17 +1103,18 @@ static int limit_list(struct rev_info *revs)
 		show(revs, newlist);
 		show_early_output = NULL;
 	}
-	if (revs->cherry_pick || revs->cherry_mark)
-		cherry_pick_list(newlist, revs);
-
-	if (revs->left_only || revs->right_only)
-		limit_left_right(newlist, revs);
 
 	if (bottom) {
 		limit_to_ancestry(bottom, newlist);
 		free_commit_list(bottom);
 	}
 
+	if (revs->cherry_pick || revs->cherry_mark)
+		cherry_pick_list(newlist, revs);
+
+	if (revs->left_only || revs->right_only)
+		limit_left_right(newlist, revs);
+
 	/*
 	 * Check if any commits have become TREESAME by some of their parents
 	 * becoming UNINTERESTING.

Hmm. Should an excluded commit be a valid comparator? Is it sensible/correct to show a left commit as "=" to a right commit that has been excluded by the revision specifiers? Doesn't sound right to me.

I'm not convinced that there's a valid use-case that you're regressing here. If --ancestry-path is being misused (the user's assertion that non-ancestry doesn't matter is wrong) the "error" of not noting culled patch-identical commits is nothing compared to the fact we're already totally omitting the non-identical ones.

Kevin

Neither to me.

OK. I'll add some tests and send a proper patch once 1.8.3 is out of the way.

The above two doe snot connect at least to me. The second paragraph seems to describe how this mysterious mode decides its output to a sufficient detail, but what the output _means_, and it is unclear how it relates to gitk/git-gui style merges.

Hmph, is this reinventing ancestry-path in a different way? At the low level machinery, you are finding D to show only F and E, and your goal seems to be to ignore the side ancestry A--C--G, but it is not clear if you prefer "E D F"(which would be what F...E would give in a history limited to ancestry-path, ignoring C) over "E F".

Can this be extended to find the second last such merge? Or is the last one always special?

Still skeptical, but I'll let people discuss it during the feature freeze ;-).

I hadn't considered ancestry-path, but I don't think it does what I want. What I want if for LEFT to be B--D--F and RIGHT to be B--E, ignoring A--C--G because I know that none of those are patch identical to anything in B--E.

So what I want is more descendant-path than ancestry path in that I don't want anything that isn't a descendant of the merge base of the supplied arguments.

In this implementation it only finds the last one because that's where the merge base is.

I'm not convinced this is easy to explain myself, which may make it a bad idea. Perhaps a --descendant-path argument to git-log is a better way to help with this case.

This is the same as the in_commit_list function already in builtin/tag.c so we also replace that by the new commit_list_contains function.

---
 builtin/tag.c | 10 +---------
 commit.c      |  8 ++++++++
 commit.h      |  1 +
 3 files changed, 10 insertions(+), 9 deletions(-)

index af3af3f..1c24772 100644
@@ -65,14 +65,6 @@ static const unsigned char *match_points_at(const char *refname,
 	return NULL;
 }
 
-static int in_commit_list(const struct commit_list *want, struct commit *c)
-{
-	for (; want; want = want->next)
-		if (!hashcmp(want->item->object.sha1, c->object.sha1))
-			return 1;
-	return 0;
-}
-
 static int contains_recurse(struct commit *candidate,
 			    const struct commit_list *want)
 {

@@ -85,7 +77,7 @@ static int contains_recurse(struct commit *candidate,
 	if (candidate->object.flags & UNINTERESTING)
 		return 0;
 	/* or are we it? */
-	if (in_commit_list(want, candidate))
+	if (commit_list_contains(want, candidate))
 		return 1;
 
 	if (parse_commit(candidate) < 0)

index 888e02a..a8263c3 100644
@@ -420,6 +420,14 @@ void commit_list_sort_by_date(struct commit_list **list)
 				commit_list_compare_by_date);
 }
 
+int commit_list_contains(const struct commit_list *list, const struct commit *item)
+{
+	for (; list; list = list->next)
+		if (!hashcmp(list->item->object.sha1, item->object.sha1))
+			return 1;
+	return 0;
+}
+
 struct commit *pop_most_recent_commit(struct commit_list **list,
 				      unsigned int mark)
 {

index 67bd509..d686ea8 100644
@@ -60,6 +60,7 @@ unsigned commit_list_count(const struct commit_list *l);
 struct commit_list *commit_list_insert_by_date(struct commit *item,
 				    struct commit_list **list);
 void commit_list_sort_by_date(struct commit_list **list);
+int commit_list_contains(const struct commit_list *list, const struct commit *item);
 
 void free_commit_list(struct commit_list *list);
 

1.8.3.rc1.289.gcb3647f

This is helpful when examining branches with disjoint roots, for example because one is periodically merged into a subtree of the other.

With the --merge-child option, "git merge-base" will print a first-parent ancestor of the first revision given, where the commit printed is either a merge-base of the supplied revisions or a merge for which one of its parents (not the first) is a merge-base.

For example, given the history:

	A---C---G
	     \
	B-----D---F
	 \
	  E

we have:

	$ git merge-base F E
	B

	$ git merge-base --merge-child F E
	D

	$ git merge-base F G
	C

	$ git merge-base --merge-child F G
	C

	$ git log --left-right F...E
	< F
	< D
	< C
	< A
	> E

	$ git log --left-right F...E --not $(git merge-base --merge-child F E)
	< F
	> E

The git-log case is useful because it allows us to limit the range of commits that we are examining for patch-identical changes when using --cherry. For example with git-gui in git.git I know that anything before the last merge of git-gui is not interesting:

	$ time git log --cherry master...git-gui/master >/dev/null
	real    0m32.731s
	user    0m31.956s
	sys     0m0.664s

	$ time git log --cherry master...git-gui/master --not \
		$(git merge-base --merge-child master git-gui/master) \
		>/dev/null
	real    0m2.296s
	user    0m2.193s
	sys     0m0.092s

---
 Documentation/git-merge-base.txt |  6 ++++
 builtin/merge-base.c             | 61 ++++++++++++++++++++++++++++++++++++++--
 t/t6010-merge-base.sh            | 25 ++++++++++++++--
 3 files changed, 88 insertions(+), 4 deletions(-)

index 87842e3..a1404e1 100644
@@ -10,6 +10,7 @@ SYNOPSIS
 --------
 [verse]
 'git merge-base' [-a|--all] <commit> <commit>...
+'git merge-base' [-a|--all] --merge-child <commit>...
 'git merge-base' [-a|--all] --octopus <commit>...
 'git merge-base' --is-ancestor <commit> <commit>
 'git merge-base' --independent <commit>...

@@ -39,6 +40,11 @@ As a consequence, the 'merge base' is not necessarily contained in each of the
 commit arguments if more than two commits are specified. This is different
 from linkgit:git-show-branch[1] when used with the `--merge-base` option.
 
+--merge-child::
+	Find the first-parent ancestor of the first commit that is either
+	reachable from all of the supplied commits or which has a parent that
+	is.
+
 --octopus::
 	Compute the best common ancestors of all supplied commits,
 	in preparation for an n-way merge.  This mimics the behavior

index f80bba8..454577e 100755
@@ -42,12 +42,16 @@ test_expect_success 'setup' '
 	T=$(git mktree </dev/null)
 '
 
-test_expect_success 'set up G and H' '
+test_expect_success 'set up G, H and L' '
 	# E---D---C---B---A
 	# \"-_         \   \
 	#  \  `---------G   \
 	#   \                \
 	#    F----------------H
+	#                      \
+	# I---------------------J---K
+	#  \
+	#   L
 	E=$(doit 5 E) &&
 	D=$(doit 4 D $E) &&
 	F=$(doit 6 F $E) &&

@@ -55,7 +59,11 @@ test_expect_success 'set up G and H' '
 	B=$(doit 2 B $C) &&
 	A=$(doit 1 A $B) &&
 	G=$(doit 7 G $B $E) &&
-	H=$(doit 8 H $A $F)
+	H=$(doit 8 H $A $F) &&
+	I=$(doit 9 I) &&
+	J=$(doit 10 J $H $I) &&
+	K=$(doit 11 K $J) &&
+	L=$(doit 12 L $I)
 '
 
 test_expect_success 'merge-base G H' '

@@ -64,6 +72,9 @@ test_expect_success 'merge-base G H' '
 	MB=$(git merge-base G H) &&
 	git name-rev "$MB" >actual.single &&
 
+	MB=$(git merge-base --merge-child G H) &&
+	git name-rev "$MB" >actual.merge_child &&
+
 	MB=$(git merge-base --all G H) &&
 	git name-rev "$MB" >actual.all &&
 

@@ -71,6 +82,7 @@ test_expect_success 'merge-base G H' '
 	git name-rev "$MB" >actual.sb &&
 
 	test_cmp expected actual.single &&
+	test_cmp expected actual.merge_child &&
 	test_cmp expected actual.all &&
 	test_cmp expected actual.sb
 '

@@ -95,6 +107,15 @@ test_expect_success 'merge-base/show-branch --independent' '
 	test_cmp expected2 actual2.sb
 '
 
+test_expect_success 'merge-base --merge-child K L' '
+	git name-rev "$J" >expected &&
+
+	MB=$(git merge-base --merge-child K L) &&
+	git name-rev "$MB" >actual &&
+
+	test_cmp expected actual
+'
+
 test_expect_success 'unsynchronized clocks' '
 	# This test is to demonstrate that relying on timestamps in a distributed
 	# SCM to provide a _consistent_ partial ordering of commits leads to

1.8.3.rc1.289.gcb3647f