[RFC/PATCH 0/2] merge-base: add --merge-child option

[RFC/PATCH 0/2] merge-base: add --merge-child option

[John Keeping]

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

[RFC/PATCH 1/2] commit: add commit_list_contains function

[John Keeping]

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.

Signed-off-by: John Keeping <john@keeping.me.uk>
---
 builtin/tag.c | 10 +---------
 commit.c      |  8 ++++++++
 commit.h      |  1 +
 3 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/builtin/tag.c b/builtin/tag.c
index af3af3f..1c24772 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -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)
diff --git a/commit.c b/commit.c
index 888e02a..a8263c3 100644
--- a/commit.c
+++ b/commit.c
@@ -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)
 {
diff --git a/commit.h b/commit.h
index 67bd509..d686ea8 100644
--- a/commit.h
+++ b/commit.h
@@ -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

[RFC/PATCH 2/2] merge-base: add --merge-child option

[John Keeping]

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

Signed-off-by: John Keeping <john@keeping.me.uk>
---
 Documentation/git-merge-base.txt |  6 ++++
 builtin/merge-base.c             | 61 ++++++++++++++++++++++++++++++++++++++--
 t/t6010-merge-base.sh            | 25 ++++++++++++++--
 3 files changed, 88 insertions(+), 4 deletions(-)

diff --git a/Documentation/git-merge-base.txt b/Documentation/git-merge-base.txt
index 87842e3..a1404e1 100644
--- a/Documentation/git-merge-base.txt
+++ b/Documentation/git-merge-base.txt
@@ -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
diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index 1bc7991..0bf9f6d 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -1,7 +1,9 @@
 #include "builtin.h"
 #include "cache.h"
 #include "commit.h"
+#include "diff.h"
 #include "parse-options.h"
+#include "revision.h"
 
 static int show_merge_base(struct commit **rev, int rev_nr, int show_all)
 {
@@ -24,12 +26,61 @@ static int show_merge_base(struct commit **rev, int rev_nr, int show_all)
 
 static const char * const merge_base_usage[] = {
 	N_("git merge-base [-a|--all] <commit> <commit>..."),
+	N_("git merge-base [-a|--all] --merge-child <commit>..."),
 	N_("git merge-base [-a|--all] --octopus <commit>..."),
 	N_("git merge-base --independent <commit>..."),
 	N_("git merge-base --is-ancestor <commit> <commit>"),
 	NULL
 };
 
+static int handle_merge_child(struct commit **rev, int rev_nr, const char *prefix, int show_all)
+{
+	struct commit_list *merge_bases;
+	struct rev_info revs;
+	struct commit *commit;
+
+	merge_bases = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1, 0);
+
+	if (!merge_bases)
+		return 1;
+
+	init_revisions(&revs, prefix);
+	revs.first_parent_only = 1;
+
+	clear_commit_marks(rev[0], SEEN | UNINTERESTING | SHOWN | ADDED);
+	add_pending_object(&revs, &rev[0]->object, "rev0");
+	if (prepare_revision_walk(&revs))
+		die(_("revision walk setup failed"));
+
+	while ((commit = get_revision(&revs)) != NULL) {
+		/*
+		 * If a merge base is a first-parent ancestor of rev[0] then
+		 * we print the commit itself instead of a merge which is its
+		 * child.
+		 */
+		if (commit_list_contains(merge_bases, commit)) {
+			printf("%s\n", sha1_to_hex(commit->object.sha1));
+			if (!show_all)
+				return 0;
+		}
+
+		struct commit_list *parent;
+		for (parent = commit->parents; parent; parent = parent->next) {
+			/* Skip the first parent */
+			if (parent == commit->parents)
+				continue;
+
+			if (commit_list_contains(merge_bases, parent->item)) {
+				printf("%s\n", sha1_to_hex(commit->object.sha1));
+				if (!show_all)
+					return 0;
+			}
+		}
+	}
+
+	return 0;
+}
+
 static struct commit *get_commit_reference(const char *arg)
 {
 	unsigned char revkey[20];
@@ -93,9 +144,12 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	int octopus = 0;
 	int reduce = 0;
 	int is_ancestor = 0;
+	int merge_child = 0;
 
 	struct option options[] = {
 		OPT_BOOLEAN('a', "all", &show_all, N_("output all common ancestors")),
+		OPT_BOOLEAN(0, "merge-child", &merge_child,
+			    N_("find a merge with a parent reachable from others")),
 		OPT_BOOLEAN(0, "octopus", &octopus, N_("find ancestors for a single n-way merge")),
 		OPT_BOOLEAN(0, "independent", &reduce, N_("list revs not reachable from others")),
 		OPT_BOOLEAN(0, "is-ancestor", &is_ancestor,
@@ -107,11 +161,11 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	argc = parse_options(argc, argv, prefix, options, merge_base_usage, 0);
 	if (!octopus && !reduce && argc < 2)
 		usage_with_options(merge_base_usage, options);
-	if (is_ancestor && (show_all | octopus | reduce))
+	if (is_ancestor && (show_all | octopus | reduce | merge_child))
 		die("--is-ancestor cannot be used with other options");
 	if (is_ancestor)
 		return handle_is_ancestor(argc, argv);
-	if (reduce && (show_all || octopus))
+	if (reduce && (show_all || octopus || merge_child))
 		die("--independent cannot be used with other options");
 
 	if (octopus || reduce)
@@ -120,5 +174,8 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	rev = xmalloc(argc * sizeof(*rev));
 	while (argc-- > 0)
 		rev[rev_nr++] = get_commit_reference(*argv++);
+
+	if (merge_child)
+		return handle_merge_child(rev, rev_nr, prefix, show_all);
 	return show_merge_base(rev, rev_nr, show_all);
 }
diff --git a/t/t6010-merge-base.sh b/t/t6010-merge-base.sh
index f80bba8..454577e 100755
--- a/t/t6010-merge-base.sh
+++ b/t/t6010-merge-base.sh
@@ -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

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[Junio C Hamano]

John Keeping <john@keeping.me.uk> writes:

> 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.

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.

> For example, given the history:
>
>         A---C---G
>              \
>         B-----D---F
>          \
>           E
>
> we have:
> ...
>         $ 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.

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".

> For example with git-gui in git.git I know that anything
> before the last merge of git-gui is not interesting:

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 ;-).

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[John Keeping]

On Sat, May 11, 2013 at 10:54:12AM -0700, Junio C Hamano wrote:
> John Keeping <john@keeping.me.uk> writes:
> 
> > 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.
> 
> 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.
> 
> > For example, given the history:
> >
> >         A---C---G
> >              \
> >         B-----D---F
> >          \
> >           E
> >
> > we have:
> > ...
> >         $ 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.
> 
> 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".

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.

> > For example with git-gui in git.git I know that anything
> > before the last merge of git-gui is not interesting:
> 
> Can this be extended to find the second last such merge?  Or is the
> last one always special?

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

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

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.

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[Kevin Bracey]

On 11/05/2013 15:23, John Keeping wrote:
> This is helpful when examining branches with disjoint roots, for example
> because one is periodically merged into a subtree of the other.
>
>
>
>          $ git log --left-right F...E --not $(git merge-base --merge-child F E)
>          < F
>          > E
>

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

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[John Keeping]

On Sun, May 12, 2013 at 06:44:30PM +0300, Kevin Bracey wrote:
> On 11/05/2013 15:23, John Keeping wrote:
> > This is helpful when examining branches with disjoint roots, for example
> > because one is periodically merged into a subtree of the other.
> >
> >
> >
> >          $ git log --left-right F...E --not $(git merge-base --merge-child F E)
> >          < F
> >          > E
> >
> 
> 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.

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?

> 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.

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

> 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...

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.

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[John Keeping]

On Sun, May 12, 2013 at 05:28:24PM +0100, John Keeping wrote:
> On Sun, May 12, 2013 at 06:44:30PM +0300, Kevin Bracey wrote:
> > On 11/05/2013 15:23, John Keeping wrote:
> > > This is helpful when examining branches with disjoint roots, for example
> > > because one is periodically merged into a subtree of the other.
> > >
> > >
> > >
> > >          $ git log --left-right F...E --not $(git merge-base --merge-child F E)
> > >          < F
> > >          > E
> > >
> > 
> > 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.
> 
> 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?
> 
> > 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.
> 
> Yes, --left-right only applies to symmetric differences ("...").  But I
> get the results above both on master and on pu.

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

> > 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...
> 
> 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.

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[Kevin Bracey]

On 12/05/2013 19:33, John Keeping wrote:
> On Sun, May 12, 2013 at 05:28:24PM +0100, John Keeping wrote:
>> 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 --ancestry-path --left-right --count \
>>              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):
>>
>> 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?

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

> 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

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.

>
>>> 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...
>> 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.
>>
Sounds cute. Go for it :)

Kevin

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> 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...

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.

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[Kevin Bracey]

On 13/05/2013 01:22, Junio C Hamano wrote:
> Kevin Bracey <kevin@bracey.fi> writes:
>
>>     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...
> 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

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[Michael J Gruber]

Kevin Bracey venit, vidit, dixit 13.05.2013 16:26:
> On 13/05/2013 01:22, Junio C Hamano wrote:
>> Kevin Bracey <kevin@bracey.fi> writes:
>>
>>>     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...
>> 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

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

log --cherry and merges (was [RFC/PATCH 0/2] merge-base: add --merge-child option)

[John Keeping]

On Mon, May 13, 2013 at 04:45:43PM +0200, Michael J Gruber wrote:
> Kevin Bracey venit, vidit, dixit 13.05.2013 16:26:
> > On 13/05/2013 01:22, Junio C Hamano wrote:
> >> Kevin Bracey <kevin@bracey.fi> writes:
> >>
> >>>     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...
> >> 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
> 
> 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".

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 --
diff --git a/revision.c b/revision.c
index a67b615..19d0683 100644
--- a/revision.c
+++ b/revision.c
@@ -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

Re: log --cherry and merges (was [RFC/PATCH 0/2] merge-base: add --merge-child option)

[Jonathan Nieder]

John Keeping wrote:

> 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 --
> diff --git a/revision.c b/revision.c
> index a67b615..19d0683 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -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;
> +

I guess merges should be skipped in the left-vs-right tally earlier,
too?

		if (flags & BOUNDARY)
			;
		else if (commit->parents && commit->parents->next)
			;
		else if (flags & SYMMETRIC_LEFT)
			left_count++;
		else
			right_count++;

With that tweak (or without it --- a sloppy count is fine), this
patch makes sense to me.  I guess some tests would be useful to
demonstrate that --cherry doesn't notice duplicate first-parent
diffs in merges.

Thanks,
Jonathan

[PATCH 0/2] Make --ancestry-path A...B work

[Kevin Bracey]

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

[PATCH 1/2] t6019: demonstrate --ancestry-path A...B breakage

[Kevin Bracey]

Signed-off-by: Kevin Bracey <kevin@bracey.fi>
---
 t/t6019-rev-list-ancestry-path.sh | 21 ++++++++++++++++++++-
 1 file changed, 20 insertions(+), 1 deletion(-)

diff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh
index 39b4cb0..5287f6a 100755
--- a/t/t6019-rev-list-ancestry-path.sh
+++ b/t/t6019-rev-list-ancestry-path.sh
@@ -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

[PATCH 2/2] revision.c: treat A...B merge bases as if manually specified

[Kevin Bracey]

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.

Signed-off-by: Kevin Bracey <kevin@bracey.fi>
---
 revision.c                        | 17 +++++++++++++++++
 revision.h                        |  1 +
 t/t6019-rev-list-ancestry-path.sh |  2 +-
 3 files changed, 19 insertions(+), 1 deletion(-)

diff --git a/revision.c b/revision.c
index a67b615..7f7a8ab 100644
--- a/revision.c
+++ b/revision.c
@@ -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);
diff --git a/revision.h b/revision.h
index 01bd2b7..878a555 100644
--- a/revision.h
+++ b/revision.h
@@ -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;
diff --git a/t/t6019-rev-list-ancestry-path.sh b/t/t6019-rev-list-ancestry-path.sh
index 5287f6a..dd5b0e5 100755
--- a/t/t6019-rev-list-ancestry-path.sh
+++ b/t/t6019-rev-list-ancestry-path.sh
@@ -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

Re: [PATCH 2/2] revision.c: treat A...B merge bases as if manually specified

[Junio C Hamano]

Looks good.  Thanks.

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[John Keeping]

On Sun, May 12, 2013 at 05:28:24PM +0100, John Keeping wrote:
> 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?

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 --
diff --git a/revision.c b/revision.c
index de3b058..d721d83 100644
--- a/revision.c
+++ b/revision.c
@@ -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.

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[Kevin Bracey]

On 12/05/2013 19:58, John Keeping wrote:
>
> 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.

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

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> On 12/05/2013 19:58, John Keeping wrote:
>>
>> 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.
>
> 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.

Neither to me.

Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[John Keeping]

On Sun, May 12, 2013 at 10:02:39PM -0700, Junio C Hamano wrote:
> Kevin Bracey <kevin@bracey.fi> writes:
> 
> > On 12/05/2013 19:58, John Keeping wrote:
> >>
> >> 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.
> >
> > 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.
> 
> Neither to me.

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