Merging submodules - best merge-base

Merging submodules - best merge-base

[Daniel Bratell]

I can phrase this in two ways and I'll start with the short way:

Why does a merge of a git submodule use as merge-base the commit that was  
active in the merge-base of the parent repo, rather than the merge-base of  
the two commits that are being merged?

The long question is:

A submodule change can be merged, but only if the merge is a  
"fast-forward" which I think is a fair demand, but currently it checks if  
it's a fast-forward from a commit that might not be very interesting  
anymore.

If two branches A and B split at a point when they used submodule commit  
S1 (based on S), and both then switched to S2 (also based on S) and B then  
switched to S21, then it's today not possible to merge B into A, despite  
S21 being a descendant of S2 and you get a conflict and this warning:

warning: Failed to merge submodule S (commits don't follow merge-base)

(attempt at ASCII gfx:

Submodule tree:

S ---- S1
   \
    \ - S2 -- S21

Main tree:

A' (uses S1) --- A (uses S2)
   \
    \ --- B' (uses S2) -- B (uses S21)


I would like it to end up as:

A' (uses S1) --- A (uses S2) ------------ A+ (uses S21)
   \                                     /
    \ --- B' (uses S2) -- B (uses S21)- /

And that should be legal since S21 is a descendant of S2.

/Daniel

Re: Merging submodules - best merge-base

[Heiko Voigt]

On Mon, Feb 25, 2013 at 05:44:05PM +0100, Daniel Bratell wrote:
> I can phrase this in two ways and I'll start with the short way:
> 
> Why does a merge of a git submodule use as merge-base the commit that was  
> active in the merge-base of the parent repo, rather than the merge-base of  
> the two commits that are being merged?
> 
> The long question is:
> 
> A submodule change can be merged, but only if the merge is a  
> "fast-forward" which I think is a fair demand, but currently it checks if  
> it's a fast-forward from a commit that might not be very interesting  
> anymore.
> 
> If two branches A and B split at a point when they used submodule commit  
> S1 (based on S), and both then switched to S2 (also based on S) and B then  
> switched to S21, then it's today not possible to merge B into A, despite  
> S21 being a descendant of S2 and you get a conflict and this warning:
> 
> warning: Failed to merge submodule S (commits don't follow merge-base)
> 
> (attempt at ASCII gfx:
> 
> Submodule tree:
> 
> S ---- S1
>    \
>     \ - S2 -- S21
> 
> Main tree:
> 
> A' (uses S1) --- A (uses S2)
>    \
>     \ --- B' (uses S2) -- B (uses S21)
> 
> 
> I would like it to end up as:
> 
> A' (uses S1) --- A (uses S2) ------------ A+ (uses S21)
>    \                                     /
>     \ --- B' (uses S2) -- B (uses S21)- /
> 
> And that should be legal since S21 is a descendant of S2.

So to summarize what you are requesting: You want a submodule merge be
two way in the view of the superproject and calculate the merge base
in the submodule from the two commits that are going to be merged?

It currently sounds logical but I have to think about it further and
whether that might break other use cases.

Cheers Heiko

Re: Merging submodules - best merge-base

[Daniel Bratell]

Den 2013-03-06 19:12:05 skrev Heiko Voigt <hvoigt@hvoigt.net>:

> On Mon, Feb 25, 2013 at 05:44:05PM +0100, Daniel Bratell wrote:
>> I can phrase this in two ways and I'll start with the short way:
>>
>> Why does a merge of a git submodule use as merge-base the commit that  
>> was
>> active in the merge-base of the parent repo, rather than the merge-base  
>> of
>> the two commits that are being merged?
>>
>> The long question is:
>>
>> A submodule change can be merged, but only if the merge is a
>> "fast-forward" which I think is a fair demand, but currently it checks  
>> if
>> it's a fast-forward from a commit that might not be very interesting
>> anymore.
>>
>> If two branches A and B split at a point when they used submodule commit
>> S1 (based on S), and both then switched to S2 (also based on S) and B  
>> then
>> switched to S21, then it's today not possible to merge B into A, despite
>> S21 being a descendant of S2 and you get a conflict and this warning:
>>
>> warning: Failed to merge submodule S (commits don't follow merge-base)
>>
>> (attempt at ASCII gfx:
>>
>> Submodule tree:
>>
>> S ---- S1
>>    \
>>     \ - S2 -- S21
>>
>> Main tree:
>>
>> A' (uses S1) --- A (uses S2)
>>    \
>>     \ --- B' (uses S2) -- B (uses S21)
>>
>>
>> I would like it to end up as:
>>
>> A' (uses S1) --- A (uses S2) ------------ A+ (uses S21)
>>    \                                     /
>>     \ --- B' (uses S2) -- B (uses S21)- /
>>
>> And that should be legal since S21 is a descendant of S2.
>
> So to summarize what you are requesting: You want a submodule merge be
> two way in the view of the superproject and calculate the merge base
> in the submodule from the two commits that are going to be merged?
>
> It currently sounds logical but I have to think about it further and
> whether that might break other use cases.

Maybe both could be legal even. The current code can't be all wrong, and  
this case also seems to be straightforward.

/Daniel

Re: Merging submodules - best merge-base

[Heiko Voigt]

On Thu, Mar 07, 2013 at 10:49:09AM +0100, Daniel Bratell wrote:
> Den 2013-03-06 19:12:05 skrev Heiko Voigt <hvoigt@hvoigt.net>:
> 
> >On Mon, Feb 25, 2013 at 05:44:05PM +0100, Daniel Bratell wrote:
> >>A submodule change can be merged, but only if the merge is a
> >>"fast-forward" which I think is a fair demand, but currently it
> >>checks if
> >>it's a fast-forward from a commit that might not be very interesting
> >>anymore.
> >>
> >>If two branches A and B split at a point when they used submodule commit
> >>S1 (based on S), and both then switched to S2 (also based on S)
> >>and B then
> >>switched to S21, then it's today not possible to merge B into A, despite
> >>S21 being a descendant of S2 and you get a conflict and this warning:
> >>
> >>warning: Failed to merge submodule S (commits don't follow merge-base)
> >>
> >>(attempt at ASCII gfx:
> >>
> >>Submodule tree:
> >>
> >>S ---- S1
> >>   \
> >>    \ - S2 -- S21
> >>
> >>Main tree:
> >>
> >>A' (uses S1) --- A (uses S2)
> >>   \
> >>    \ --- B' (uses S2) -- B (uses S21)
> >>
> >>
> >>I would like it to end up as:
> >>
> >>A' (uses S1) --- A (uses S2) ------------ A+ (uses S21)
> >>   \                                     /
> >>    \ --- B' (uses S2) -- B (uses S21)- /
> >>
> >>And that should be legal since S21 is a descendant of S2.
> >
> >So to summarize what you are requesting: You want a submodule merge be
> >two way in the view of the superproject and calculate the merge base
> >in the submodule from the two commits that are going to be merged?
> >
> >It currently sounds logical but I have to think about it further and
> >whether that might break other use cases.
> 
> Maybe both could be legal even. The current code can't be all wrong,
> and this case also seems to be straightforward.

Ok I have thought about it further and I did not come up with a simple
(and stable) enough strategy that would allow your use case to merge
cleanly without user interaction.

The problem is that your are actually doing a rewind from base to both
tips. The fact that a rewind is there makes git suspicious and we simply
give up. IMO, thats the right thing to do in such a situation.

What should a merge strategy do? It infers from two changes what the
final intention might be. For submodules we can do that when the changes
on both sides point forward. Since thats the typical progress of
development. If not there is some reason for it we do not know about. So
the merge gives up.

Please see this post about why we need to forbid rewinds from the
initial design discussion:

http://article.gmane.org/gmane.comp.version-control.git/149003

I am not saying that the current behavior is perfect but I think a merge
containing a rewind needs user support. We could give the user a hint
and say: "Hey I gave up but the two sides are contained in each other
and this is the commit containing both". Then the user can choose to use
that suggested solution. We already do the same for the merge commit
search.

Cheers Heiko

Re: Merging submodules - best merge-base

[Jens Lehmann]

Am 07.03.2013 19:59, schrieb Heiko Voigt:
> On Thu, Mar 07, 2013 at 10:49:09AM +0100, Daniel Bratell wrote:
>> Den 2013-03-06 19:12:05 skrev Heiko Voigt <hvoigt@hvoigt.net>:
>>
>>> On Mon, Feb 25, 2013 at 05:44:05PM +0100, Daniel Bratell wrote:
>>>> A submodule change can be merged, but only if the merge is a
>>>> "fast-forward" which I think is a fair demand, but currently it
>>>> checks if
>>>> it's a fast-forward from a commit that might not be very interesting
>>>> anymore.
>>>>
>>>> If two branches A and B split at a point when they used submodule commit
>>>> S1 (based on S), and both then switched to S2 (also based on S)
>>>> and B then
>>>> switched to S21, then it's today not possible to merge B into A, despite
>>>> S21 being a descendant of S2 and you get a conflict and this warning:
>>>>
>>>> warning: Failed to merge submodule S (commits don't follow merge-base)
>>>>
>>>> (attempt at ASCII gfx:
>>>>
>>>> Submodule tree:
>>>>
>>>> S ---- S1
>>>>   \
>>>>    \ - S2 -- S21
>>>>
>>>> Main tree:
>>>>
>>>> A' (uses S1) --- A (uses S2)
>>>>   \
>>>>    \ --- B' (uses S2) -- B (uses S21)
>>>>
>>>>
>>>> I would like it to end up as:
>>>>
>>>> A' (uses S1) --- A (uses S2) ------------ A+ (uses S21)
>>>>   \                                     /
>>>>    \ --- B' (uses S2) -- B (uses S21)- /
>>>>
>>>> And that should be legal since S21 is a descendant of S2.
>>>
>>> So to summarize what you are requesting: You want a submodule merge be
>>> two way in the view of the superproject and calculate the merge base
>>> in the submodule from the two commits that are going to be merged?
>>>
>>> It currently sounds logical but I have to think about it further and
>>> whether that might break other use cases.
>>
>> Maybe both could be legal even. The current code can't be all wrong,
>> and this case also seems to be straightforward.
> 
> Ok I have thought about it further and I did not come up with a simple
> (and stable) enough strategy that would allow your use case to merge
> cleanly without user interaction.
> 
> The problem is that your are actually doing a rewind from base to both
> tips. The fact that a rewind is there makes git suspicious and we simply
> give up. IMO, thats the right thing to do in such a situation.
> 
> What should a merge strategy do? It infers from two changes what the
> final intention might be. For submodules we can do that when the changes
> on both sides point forward. Since thats the typical progress of
> development. If not there is some reason for it we do not know about. So
> the merge gives up.
> 
> Please see this post about why we need to forbid rewinds from the
> initial design discussion:
> 
> http://article.gmane.org/gmane.comp.version-control.git/149003

I agree that rewinds are a very good reason not merge two branches using
a fast-forward strategy, but I believe Daniel's use case is a (and maybe
the only) valid exception to that rule: both branches contain *exactly*
the same rewind. In that case I don't see any problem to just do a fast
forward to S21, as both agree on the commits to rewind.

Re: Merging submodules - best merge-base

[Heiko Voigt]

On Sat, Mar 09, 2013 at 06:45:56PM +0100, Jens Lehmann wrote:
> Am 07.03.2013 19:59, schrieb Heiko Voigt:
> > On Thu, Mar 07, 2013 at 10:49:09AM +0100, Daniel Bratell wrote:
> >> Den 2013-03-06 19:12:05 skrev Heiko Voigt <hvoigt@hvoigt.net>:
> >>> So to summarize what you are requesting: You want a submodule merge be
> >>> two way in the view of the superproject and calculate the merge base
> >>> in the submodule from the two commits that are going to be merged?
> >>>
> >>> It currently sounds logical but I have to think about it further and
> >>> whether that might break other use cases.
> >>
> >> Maybe both could be legal even. The current code can't be all wrong,
> >> and this case also seems to be straightforward.
> > 
> > Ok I have thought about it further and I did not come up with a simple
> > (and stable) enough strategy that would allow your use case to merge
> > cleanly without user interaction.
> > 
> > The problem is that your are actually doing a rewind from base to both
> > tips. The fact that a rewind is there makes git suspicious and we simply
> > give up. IMO, thats the right thing to do in such a situation.
> > 
> > What should a merge strategy do? It infers from two changes what the
> > final intention might be. For submodules we can do that when the changes
> > on both sides point forward. Since thats the typical progress of
> > development. If not there is some reason for it we do not know about. So
> > the merge gives up.
> > 
> > Please see this post about why we need to forbid rewinds from the
> > initial design discussion:
> > 
> > http://article.gmane.org/gmane.comp.version-control.git/149003
> 
> I agree that rewinds are a very good reason not merge two branches using
> a fast-forward strategy, but I believe Daniel's use case is a (and maybe
> the only) valid exception to that rule: both branches contain *exactly*
> the same rewind. In that case I don't see any problem to just do a fast
> forward to S21, as both agree on the commits to rewind.

That is different than using the merge base of the two commits needing
merge. I agree that rewinding to exactly the same commits is probably a
valid exception. Will have a look into extending the submodule merge
strategy to include this case.

Cheers Heiko

[RFC/PATCH] submodule: allow common rewind when merging submodules

[Heiko Voigt]

Allow merge of two commits that are contained in each other and do the
same rewind. The rewind is calculated using the commit recorded in the
merge base of the superproject.

Signed-off-by: Heiko Voigt <hvoigt@hvoigt.net>
---

On Sun, Mar 10, 2013 at 06:09:53PM +0100, Heiko Voigt wrote:
> On Sat, Mar 09, 2013 at 06:45:56PM +0100, Jens Lehmann wrote:
> > I agree that rewinds are a very good reason not merge two branches using
> > a fast-forward strategy, but I believe Daniel's use case is a (and maybe
> > the only) valid exception to that rule: both branches contain *exactly*
> > the same rewind. In that case I don't see any problem to just do a fast
> > forward to S21, as both agree on the commits to rewind.
> 
> That is different than using the merge base of the two commits needing
> merge. I agree that rewinding to exactly the same commits is probably a
> valid exception. Will have a look into extending the submodule merge
> strategy to include this case.

So here is the patch that implements this case. I am still a little bit
unsure about the user experience.

I had to extend the merge test setup to include a loose commit h because
otherwise we get a different merge case.

E.g. if you have this in the subproject

	a---b---d
	 \     /
          --c-+----h

And the superproject records

	BASE(b)---A(d)
	 \
	  ---B(c)

When you merge A and B the change from b to d can either be represented
as a forward change or as a rewind to a and then adding c, d. Since we
calculate the rewind using merge bases we find a forward change here. So
here we fail to merge as before.

If the superproject records

	BASE(b)---A(h)
	 \
	  ---B(c)

We will now find a rewind to a for both sides and merge cleanly since b
is not contained in h.

So the problem with the user experience here is:

Imagine a project does this kind of rewind because a bug is discovered
in b and then adds some other things using commits like c, h and so on. Then
there are more commits after b which will eventually fix it. Now the
project merges the b line into the h line in the submodule and can get a
merge conflict in the superproject like explained in the first case.

This might feel strange to them since the step to h (moving b -> c)
resolved cleanly but then a merge which *looks like* it just involves a
fast-forward in the submodule will fail.

Anyway its nothing technically wrong with our merge strategy just that
we can not decide which way the user went and so the merge fails.

One step I have in mind but not yet taken: If I see this correctly we
could simplify the code by just doing the is_common_rewind() check and
drop the commits_follow_merge_base() check since it is already contained
in the former.

The testsuite passes with this commit. You can also find this on github:

https://github.com/hvoigt/git/commits/hv/submodule-merge-bases-series1

Cheers Heiko

 submodule.c                | 42 +++++++++++++++++++++++++++++++++++++++---
 t/t7405-submodule-merge.sh | 39 +++++++++++++++++++++++++++++++++++++--
 2 files changed, 76 insertions(+), 5 deletions(-)

diff --git a/submodule.c b/submodule.c
index 9ba1496..e24d630 100644
--- a/submodule.c
+++ b/submodule.c
@@ -911,6 +911,44 @@ static void print_commit(struct commit *commit)
 #define MERGE_WARNING(path, msg) \
 	warning("Failed to merge submodule %s (%s)", path, msg);
 
+static int is_common_rewind(struct commit *base, struct commit *a, struct commit *b)
+{
+	struct commit_list *merge_bases_a, *merge_bases_b;
+	int result;
+
+	/* find single rewind commit for a */
+	merge_bases_a = get_merge_bases(a, base, 1);
+	if (!merge_bases_a || commit_list_count(merge_bases_a) != 1)
+		return 0;
+
+	/* find single rewind commit for b */
+	merge_bases_b = get_merge_bases(b, base, 1);
+	if (!merge_bases_b || commit_list_count(merge_bases_b) != 1)
+		return 0;
+
+	/* see if we rewind to the same commit */
+	result = !hashcmp(merge_bases_a->item->object.sha1,
+			  merge_bases_b->item->object.sha1);
+	free_commit_list(merge_bases_a);
+	free_commit_list(merge_bases_b);
+
+	return result;
+}
+
+static int commits_follow_merge_base(struct commit *commit_base,
+		struct commit *commit_a, struct commit *commit_b)
+{
+	/* check whether both changes are forward */
+	if (in_merge_bases(commit_base, commit_a) &&
+	    in_merge_bases(commit_base, commit_b))
+		return 1;
+
+	if (is_common_rewind(commit_base, commit_a, commit_b))
+		return 1;
+
+	return 0;
+}
+
 int merge_submodule(unsigned char result[20], const char *path,
 		    const unsigned char base[20], const unsigned char a[20],
 		    const unsigned char b[20], int search)
@@ -944,9 +982,7 @@ int merge_submodule(unsigned char result[20], const char *path,
 		return 0;
 	}
 
-	/* check whether both changes are forward */
-	if (!in_merge_bases(commit_base, commit_a) ||
-	    !in_merge_bases(commit_base, commit_b)) {
+	if (!commits_follow_merge_base(commit_base, commit_a, commit_b)) {
 		MERGE_WARNING(path, "commits don't follow merge-base");
 		return 0;
 	}
diff --git a/t/t7405-submodule-merge.sh b/t/t7405-submodule-merge.sh
index 0d5b42a..66520c6 100755
--- a/t/t7405-submodule-merge.sh
+++ b/t/t7405-submodule-merge.sh
@@ -60,7 +60,7 @@ test_expect_success setup '
 #           /   \
 #  init -- a     d
 #    \      \   /
-#     g       c
+#     g       c---h
 #
 # a in the main repository records to sub-a in the submodule and
 # analogous b and c. d should be automatically found by merging c into
@@ -109,7 +109,17 @@ test_expect_success 'setup for merge search' '
 	(cd sub &&
 	 git checkout -b sub-g sub-c) &&
 	git add sub &&
-	git commit -a -m "g")
+	git commit -a -m "g" &&
+
+	git checkout -b h c &&
+	(cd sub &&
+	 git checkout -b sub-h sub-c &&
+	 echo "file-h" >file-h &&
+	 git add file-h &&
+	 git commit -m "sub-h") &&
+	git add sub &&
+	git commit -a -m "h"
+	)
 '
 
 test_expect_success 'merge with one side as a fast-forward of the other' '
@@ -146,6 +156,31 @@ test_expect_success 'merging should fail for ambiguous common parent' '
 	git reset --hard)
 '
 
+test_expect_success 'merging should succeed with common rewind' '
+	(cd merge-search &&
+		git checkout -b common-rewind-base init &&
+		(cd sub &&
+			git checkout sub-b
+		) &&
+		git add sub &&
+		git commit -m "common-rewind-base" &&
+		git checkout -b common-rewind-a common-rewind-base &&
+		(cd sub &&
+			git checkout sub-c
+		) &&
+		git add sub &&
+		git commit -m "common-rewind-a" &&
+		git checkout -b common-rewind-b common-rewind-base &&
+		(cd sub &&
+			git checkout sub-h
+		) &&
+		git add sub &&
+		git commit -m "common-rewind-b" &&
+		git checkout -b common-rewind-merge common-rewind-a &&
+		git merge common-rewind-b
+	)
+'
+
 # in a situation like this
 #
 # submodule tree:
-- 
1.8.2.rc2.5.gab0ecbc