patch, 3 partsadd missing && to submodule-merge testcase

The following patch series is a work in progress. The idea is whenever you need to merge two SHA1's of a submodule we search for a ref in the submodule which already contains both. If one such ref exists the resulting SHA1 is the one pointed at by that ref.

The implementation currently searches through all refs and if one (and only one) ref exists which contains both sides it merges. In all other cases it fails.

Future Plans:

  * Only search stable branches. E.g. by default only master and
    */master. The stable branch list will be configurable.

  * Use read_gitfile_gently for submodule .git handling

  * Use strbuf in git_path_submodule

Further comments or ideas?

The series can also be found on github:

http://github.com/hvoigt/git/tree/hv/submodule_merge

cheers Heiko

Heiko Voigt (3):
  extend ref iteration for submodules
  add missing && to submodule-merge testcase
  implement automatic fast forward merge for submodules

 cache.h                    |    3 +
 merge-recursive.c          |    9 ++-
 path.c                     |   21 ++++++++
 refs.c                     |   89 +++++++++++++++++++++++---------
 refs.h                     |    2 +
 submodule.c                |  121 ++++++++++++++++++++++++++++++++++++++++++++
 submodule.h                |    2 +
 t/t7405-submodule-merge.sh |  117 ++++++++++++++++++++++++++++++++++++++++---
 8 files changed, 328 insertions(+), 36 deletions(-)

This is useful to interrogate a submodule from the main repository.

Signed-off-by: Heiko Voigt <hvoigt@hvoigt.net>
---
 cache.h |    3 ++
 path.c  |   21 +++++++++++++++
 refs.c  |   89 ++++++++++++++++++++++++++++++++++++++++++++------------------
 refs.h  |    2 +
 4 files changed, 89 insertions(+), 26 deletions(-)

Signed-off-by: Heiko Voigt <hvoigt@hvoigt.net>
---
 t/t7405-submodule-merge.sh |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

This implements a simple merge strategy for submodule hashes. We look whether a single ref that contains both hashes exist. In case it does and the changes on both sides point forward in the direction of that ref we return the refs revision as the merge result.

It is useful for a workflow in which the developers can publish topic branches in submodules. Once the topic branch has been merged into a stable branch the developer can simply merge his branch in the main repository even when other developers have merged their submodule changes before them.

Signed-off-by: Heiko Voigt <hvoigt@hvoigt.net>
---
 merge-recursive.c          |    9 ++-
 submodule.c                |  121 ++++++++++++++++++++++++++++++++++++++++++++
 submodule.h                |    2 +
 t/t7405-submodule-merge.sh |  115 +++++++++++++++++++++++++++++++++++++++--
 4 files changed, 238 insertions(+), 9 deletions(-)

On Friday 11 June 2010, Heiko Voigt wrote:

I appreciate the effort to improve submodule handling, but I'm not sure I like this approach. Even though you try to apply it as conservatively as possible, it still smells a little like trying to make Git too clever for its own good.

E.g. say we have the following commit history in the submodule:

  A---B---C---D  <-- master

Now, say that your merge conflict comes from one branch updating the submodule from B to C, while the other branch reverts the submodule from B to A. In your proposed scheme, Git would auto-resolve the conflict to D.

In this case Git has no way of knowing whether the update from B to C is "better" than the revert from B to A. Maybe the revert to A happened because there is a showstopper bug in B that has not yet been fixed, and the best solution is to revert to A until a fix can be made. Or maybe C fixes that showstopper bug, so C is safe after all.

In any case, fast-forwarding to D seems irresponsible, since we have no concept of how well D is tested. Maybe it introduces another showstopper bug, and that is why neither branch has upgraded to it yet?

This whole idea is somewhat similar to branch-tracking submodules (recently discussed in another thread), except that it only applies on _merge_ in the superproject, and you don't get to choose _which_ branch it's tracking. That's _way_ too arbitrary for my tastes.

Still doesn't solve the fundamental A---B---C---D problem I demonstrated above.

What is this "stable" branch of which you speak? "Stable" is a very relative concept, depending on which repo you're working in, and which branch you're working on. In any case, master is often not the most stable branch in a given repo. In git.git for example, maint is more stable than master. Also, I have many repos where master should not be considered "stable" at all...

...Johan

Hi,

On Sat, Jun 12, 2010 at 12:12:50PM +0200, Johan Herland wrote:

You are right. I did forget to mention this in my topic letter: Both changes need to point forward. This exact case is also tested in the testcases and results in a merge conflict which needs to be resolved by hand.

The difference to branch-tracking submodules is, if I understand it correctly, that with a merge you get an explicit SHA1 which is recorded. Whereras with branch-tracking you never know on which revision on the tracked branch the submodule was.

Thats why I only want to search through stable branches further down. I mean stable in the git sense that they never get rewound and of course should contain the most stable part of development. To ease the configuration we would default to master which we could assume as stable. But if we want to be on the safe side we could also say that automatic submodule merging only works when the user has configured some stable branches.

See above.

cheers Heiko

On Saturday 12 June 2010, Heiko Voigt wrote:

Still doesn't solve one of the cases I gave in the last email: Say one branch updates the submodule from A to B, and the other updates from A to C. Your proposal resolves the merge by fast-forwarding to D, which seems irresponsible, since we have no concept of how well D is tested. Maybe it introduces another showstopper bug, and that is why neither branch has upgraded to it yet?

A better solution would be, to put it generally: Given a submodule being part of a superproject conflict, if one of the candidate submodule SHA1s is is a descendant of _all_ the other submodule SHA1 candidates, then choose that SHA1 as the proposed resolution (but please leave the index entry "unmerged", so that the resolution must be confirmed by the user).

This removes all the "stable" branch magic from your patch. All you need to look at are the candidate SHA1s and their relationship in the commit graph. No refs involved.

In the A->B vs. A->C case above, we would see that C is a descendant of B, and we would therefore choose C as a suggested conflict resolution, which IMHO is a much better choice than D.

I still don't want to add a lot of auto-resolving cleverness to Git, as it inevitably _will_ choose incorrectly sometimes, and in those situations it will be much more confusing than if it didn't choose at all.

Technically you may be right, but my point is that in your original proposal I don't get to _choose_ which submodule SHA1 is explicitly recorded for the merge resolution, but instead your patch chooses whatever SHA1 happens to be at the tip of some branch considered "stable". Although technically different, this is similar in _spirit_ to what branch-tracking submodules is about.

Ok, so you can configure exactly which branch(es) you consider stable. I'd still much rather prefer the approach I outlined above, which does away with all the "stable" branch magic, and only considers the commit ancestry directly.

Hope this helps,

...Johan

Hi,

On Sun, Jun 13, 2010 at 07:59:43PM +0200, Johan Herland wrote:

Is there currently any logic to support a "suggested" merge resolution in git.git? I am not that familiar with code base yet and I do not think that I have seen something like that. Is it done somewhere already?

I see your point. But nevertheless there is a specific workflow I target to support which is not supported by your approach:

Lets assume Alice creates a feature branch feature_a for her development and needs to modify the submodule and creates a branch there as well. At the same time Bob develops feature_b and also needs changes in the submodule and so he creates a feature branch there as well.

Assume we now have the following history in the submodule:

  B---C---D         [feature_a]
 /         \
A---E---F---G---K   [master]
     \         /
      H---I---J     [feature_b]

Now during the development of her branch Alice would link D in the superproject as it is the tip of her branch. Bob would do the same and link to J as his tip. Now Alice sends out her branch to the reviewers and after everybody is happy with it the maintainer merges her branch first. The superproject links to D. Now Bob does the same and the maintainer wants to merge his branch and gets a merge conflict because D and J do not have a parent/children relationship.

I think this is a fairly natural pattern which evolves from the use of feature branches in git. So I would like to make git behave naturally for this workflow and automatically merge.

Now your point is that master could be wrong and you are right, but normal merges can go wrong in a similar way. Just imagine this:

Alice adds a parameter to the static function somefunc() and changes all callsites of it in her branch. Independently Bob writes new code in his branch that uses somefunc() with the old signature. When both branches are merged git has no chance of doing it right and the code will not compile. So even normal merging is always a little heuristic. Question is: How well does the heuristic perform in practise.

Ok what do you think about combining both approaches: If no stable branches are configured we default to your strategy and if the user wants some magic (I mean isn't that what git is all about: magic) configuring stable branches will enable git to resolve conflicts like the ones I described above.

My feeling is that in practise automatic merging into stable branches will work well and the cases of failure will be neglectable to not happening at all. So my approach would be to go ahead, implement the strategy and let people play around with it so we can collect some real life data whether it is helping or making matters worse.

cheers Heiko

On Monday 14 June 2010, Heiko Voigt wrote:

In the case of a regular file, you can replace the default working tree version (the one with conflict markers) by a version containing your suggested merge resolution, but NOT add that version to the index, so the index still thinks the file is unmerged. You then 'git add' the file to acknowledge the suggested resolution.

In the case of submodules, you would check out the suggested version of the submodule, but not add its SHA1 to the superproject index. Again, the user acknowledges the suggested resolution by 'git add'ing the submodule.

My point is that when Git tries to suggest merge resolutions, it should purposefully NOT add these to the index, so that the user HAS to acknowledge them. This is similar to the default behaviour of 'git rerere' which resolves your conflicts automatically, but does not touch the corresponding "unmerged" index entries, so that you manually have to 'git add' the result.

No. The superproject would get a conflict between the A->D and A->F updates of the submodule. The correct resolution would be to go into the submodule, do the merge to produce G, and then record this as the correct merge resolution in the superproject.

You want Git to do this automatically for you, whereas I think that Git should not be that "clever", because there are situations (as I've demonstrated previously in this thread) where the "cleverness" would do The Wrong Thing.

Well, s/D/G/, but your point still stands. And the correct resolution is, of course, to merge G and J to produce K, and then record K in the superproject as the correct merge resolution.

Again, the question is whether Git should do these submodule merges automatically, or not.

Please keep in mind that your workflow is but one, and Git has to support a wide variety of different workflows without breaking down.

It actually seems to me that - in your workflow scenario, where the submodule seems to be fairly tightly coupled to the superproject - you would be better off using branch-tracking submodules (recently discussed in the thread called 'RFC: Making submodules "track" branches').

When using branch-tracking submodules, Alice would configure the submodule to track the "feature_a" branch, while Bob would configure the submodule to track the "feature_b" branch. When merging these branches, the correct merge resolution would be (after having merged the submodule feature branches back into the submodule "master") to track the "master" branch in the submodule.

When merging the two feature branches back into "master" there would (in addition to the conflicted submodule entry) be conflicts in the .gitmodules file on which submodule branch to track (I'm following Ævar's proposal here), and the resolution of _that_ conflict would specify which submodule branch/version to use in the resolved merge.

Now, in your proposal, you would have an _additional_ config variable for controlling which submodule branch is equivalent to "master" in the above example. If this branch were to be different from the "tracked" branch (as defined in Ævar's proposal), you would be in the deeply confusing situation of having the merge resolved to the tip of one branch, while you've told the submodule to track a _different_ branch. The only thing that makes sense would be for these two variables to always be identical, at which point you should simply eliminate one of them.

I guess what I'm getting at (sorry for taking a while to get here) is that you could maybe solve your problem by a combination of what I suggested in my previous mail, plus the use of branch-tracking submodules. There are still some things to be worked out here, but I don't believe adding an almost-but-not-quite-submodule-branch-tracking option is the best way to go.

True, but I don't necessarily accept that one sometimes-wrong heuristic justifies another sometimes-wrong heuristic. Follow that logic, and we can pile on heuristics until we almost always get something wrong...

FWIW, IMHO Git is NOT about magic at all. It even says so at the top of the git(1) manual page: "git - the stupid content tracker". And both Junio and Linus have repeatedly argued how Git purposefully only auto-resolves the _simple_ cases, and leaves the _hard_ cases to the user, since trying to be clever about the hard cases inevitably leads to more confusion and insanity.

In this case, your scenario/proposal just about crosses into what I consider the _hard_ space, which is why I'm critical of the cleverness.

As for combining both approaches (subject to some config option), I guess that could work, but I'd certainly like to see a significant amount of support for your proposal before we go there.

Feel free to post the patches, if you can spend the time making them. So far, there's been no other feedback in this thread, so maybe I'm alone in my worries...

Cheers,

...Johan

Am 15.06.2010 01:59, schrieb Johan Herland:

I like that idea, as it avoids having unintended submodule commits added silently to the superprojects index by the merge.

But as far as I understood this patch this merge has already been done inside the submodule (at least this is what the setup of the test case seems to do at a quick glance).

Hm, maybe I am missing something here, but isn't the question whether Git should /use/ these submodule merges already done by a human being instead of /doing them itself/? So isn't it just about making Git so clever it proposes a merge already present in the submodule for recording in the superproject when merging there?

I fully understand your worries concerning automagic merges inside a submodule. But I really would like to see Git assisting me when merging submodule commits in the superproject that have already been merged in the submodule repo. And for me the first commit containing the others is the one I would like to see then.

On Tuesday 15 June 2010, Jens Lehmann wrote:

Ok, let's look at a sequence of events:

0. There is a master branch in the superproject which points to commit A (on 
the master branch) in the submodule.

1. Alice creates feature_a branch in both superproject and submodule, 
creates commits B, C & D in the submodule and updates the superproject to 
point to D

2. Someone creates E in the submodule, and updates the master branch in the 
superproject to point to E.

3. Bob creates feature_b branch in both superproject and submodule, creates 
commits H, I & J in the submodule and updates the superproject to point to J

4. Someone creates F in the submodule, and updates the master branch in the 
superproject to point to F.

5. Maintainer starts integrating feature_a into master in superproject, and 
discovers the conflict between A->D and A->F. Mantainer then descends into 
submodule to create the merge G. Maintainer can now 'git add' the submodule 
in the superproject to record A->G as the merge resolution of the A->D vs. 
A->F conflict.

(6. Same as step #5, but replace Alice/A/D/F/G with Bob/E/J/G/K)

I assume here that nobody has made the merge commit G before Git produces the A->D vs. A->F conflict in step #5 (which prompts Maintainer to make G in order to resolve the conflict). I believe this would be the most common case.

If the merge commit G for some reason _already_ exists in the submodule before step #5, the maintainer's job is to simply recognize it as the correct resolution of the conflict, and check it out (and finally 'git add' it to the superproject index). But I don't see this happening very often: For one, who has the incentive to create G before it is needed in step #5? Both Alice and Bob are content with pointing to their respective submodule branches, and the only person who cares about doing the submodule merges is Maintainer who has to tie everything together into a coherent whole.

However, we should not require clairvoyance from the Maintainer as to which submodules have been modified by each feature branch, and hence which of them require preparatory submodule merges to be performed before the main superproject merge can be started. To the contrary, I believe the typical Maintainer will start the superproject merge, and then respond to the submodule conflicts that Git produces by descending into the submodule and merging submodules (or whatever else is required to reach a satisfactory submodule state).

Thus, if the purpose of Heiko's patches is to simply recognize merges that have already happened before step #5, then I'm afraid they will seldom or never be useful in practice (since these merges typically happen _after_ the superproject merge has been started).

Ah, yes, sorry, I confused the concepts at this point. Still:

- If the purpose is to re-use existing submodule merges then I'm afraid (as 
I've argued above) that this would happen too seldom to be useful in 
practice (and even then you would already have had to set up the appropriate 
config for your branch, to enable Git to find this pre-existing merge at 
all).

- If the purpose is to create new submodule merges to resolve the conflicts 
(which, granted, the patches currently don't do, but that I'm afraid they 
would _have_ to do in order to be useful in practice), then there is too 
much cleverness/magic for my liking.

As I've argued above, I'm afraid this situation would seldom/never arise in practice.

Taking a step back and comparing the merging of submodules vs. the merging of regular files:

Git's rules are simple and straightforward for regular files: If both sides/branches have changed the same area of code (and the changes don't exactly coincide), you get a conflict. There's no magic/cleverness applied to try to figure out what a good resolution would look like; it's a conflict, and the user must resolve it. Simple as that.

I'd argue that the submodule case should be the same: If both sides/branches change the submodule (and the SHA1s don't exactly match), you get a conflict, and it's up to the user to resolve it.

We may to make an exception for the case where one SHA1 is a descendant of the other (i.e. a fast-forward situation), since that seems like a safe choice in most situations, but I don't feel safe doing much beyond that.

In that case you will have to modify Heiko's patches, because (I believe) they currently choose the _latest_ commit containing the others...

Cheers,

...Johan

Am 16.06.2010 02:05, schrieb Johan Herland:

That this is all but happening seldom for us is the reason for this WIP patch from Heiko. And other use cases won't be harmed by this change, no? And if some are, we can add a config option to .gitmodules to control that.

Yes, I would like to see that fast-forward case silently handled by a merge in the superproject.

And if it is no fast-forward but you find a unique merge where both of these SHA1s are included, you could advertise it as a possible solution but not automagically add it to the index. So you give the maintainer of the superproject the opportunity to assess a possible solution but spare him the chore of trying to find the reason why the merge failed and what he can do about it by showing him the right direction. He might then decide to take a later commit of the submodule or resolve the whole issue differently, but that is up to him.

Yes, but IMHO that is a bit too much forwarding.

On Wednesday 16 June 2010, Jens Lehmann wrote:

Ok. I'm still not sure I see how this can happen frequently in practice, but since you both probably use submodules more heavily than I do, I will not stand in the way of progress.

I still particularily don't like the added config variable for specifying which branch(es) are considered "stable". Would it be possible to instead search all submodule branches for the earliest commits that reconcile the two commits, and then inform the user that these may be interesting to look at when trying to find a resolution? Something like:

  Cannot auto-resolve conflict between $a_sha1 and $b_sha1 in submodule
  $foo. The following merge commits in submodule $foo may help you resolve
  this conflict:
    - $sha1 (present in branches $a, $b, $c)
    - $sha2 (present in branches $c, $d)
    - $sha3 (present in branches $e, $f)

Thus the user/maintainer gets the full picture, and are given as many alternatives as possible to help resolve the conflict, instead of automatically getting one (possibly wrong) resolution, just because the "stable" config was unset or incorrect.

...Johan

Johan Herland <johan@herland.net> writes:

At least it would be useful to learn how they manage to often produce the submodule merge G. Your scenario description was very clearly written and in that particular workflow I didn't think it would be plausible to have such a merge before it is needed. IOW, their workflow must be quite different from your scenario description, and I would like to see a plausible scenario description that is as clearly written as yours; perhaps that workflow can even be advertised as one of the BCP.

One possibility that comes to mind is perhaps Alice notices the presence of F after she recorded D, merges D and F in the submodule to produce G in the submodule repository, but does _not_ update the superproject to point at it yet, for some reason. Perhaps she hasn't tested the superproject with the merged submodule yet. Whatever the reason is, the tip of her branch in the submodule would be ahead of what her superproject commit D points at, but the commit is available to the maintainer to fetch.

Then the maintainer would see G in the submodule (after fetching both superproject and submodule from Alice) already prepared to be used in a merge between D and F.

I dunno.

On Thursday 17 June 2010, Junio C Hamano wrote:

Dubious. If Alice's merge of D and F hasn't been properly tested yet, I don't see why it should exist on the submodule's master branch, and if it doesn't, it simply isn't considered, due to Heiko's "stable" branch magic.

Me neither, but after some more thinking I have another alternative as to why the merge G might exist (on the submodule master branch) before the superproject merge is started:

If the submodule happens to be maintained as a truly separate project (with its own maintainer), then the maintainer of that submodule may have decided to merge Alice's feature_a branch on its own merits, without looking at the superproject at all. When the superproject maintainer later performs the superproject merge he can just pick up the submodule merge done by the submodule maintainer.

But this is pure speculation, and as you say, I'd like to see what workflows Jens and Heiko are actually using.

...Johan

Am 17.06.2010 02:39, schrieb Johan Herland:

Ok, here we go. And as I have difficulties thinking about that when looking at a single graph, I'll draw two: The upper for the superproject and the lower for the submodule.

Superproject:
  -----2         [Alice's branch]
 /      \
1--3-----4---5   [master]
    \       /
     ------6     [Bob's branch]

       ^   ^
       |   |     [commits of the submodule committed in the superproject]

Submodule:
  ---B           [feature_a]
 /    \
A--C---D---E     [master]
    \     /
     ----F       [feature_b]

Alice hacks away on her feature branch and notices she has to make changes to a submodule. She creates the "feature_a" branch there with commit 'B' and asks the maintainer of the submodule to review and merge her change. Our policy is to never commit submodule commits that are not merged yet, as they could just vanish (e.g. by rebasing; imagine having git as a submodule and committing a SHA1 from the "pu" branch in the superproject ... a later bisect might get really frustrating). So the submodule maintainer merges 'B' into 'D' and tells Alice that. She commits 'D' for the submodule in her '2' commit and asks the maintainer of the superproject to review and merge that. The moment he merges that into '4', 'D' gets recorded in the master branch of the superproject for the submodule.

Meanwhile Bob also needs a change in the submodule for his work in the superproject and adds commit 'F' on the "feature_b" branch there. He waits for the submodule maintainer to merge that into 'E' so he can do commit '6'.

But now the submodule commit 'D' in the superproject commit '4' has become an obstacle for him and the superprojects maintainer. Bob can't rebase or cherrypick beyond or up to '4' because he will get a merge conflict. If he asks to merge his branch into '5', the superprojects maintainer will get a merge conflict and tells to him to resolve that.

This situation would disappear when git merge would do fast-forwards for submodule commits. And I argue that this is The Right Thing, because just as commit '5' contains /all/ changes from both branches to the files it should also contain /all/ changes to the submodules files that happened during these branches. And that means merge should resolve the submodule to commit 'E'.

This is somehow similar to merging binary files. But for submodules Git has a chance to tell the combined version of both changes in the fast-forward case, whereas it can't know that for binary files. And yes, merge conflicts could happen for the same reasons they may happen to files: The changes in Bob's branch could break something in Alice's branch. But that applies for files just like it does for submodule commits, no?

And the non-fast-forward case happens e.g. when Alice and Bob do not wait for the submodule maintainer to merge their changes:

Superproject:
  ---2         [Alice's branch]
 /    \
1--3---4---5   [master]
    \     /
     ----6     [Bob's branch]

     ^   ^
     |   |       [commits of the submodule committed in the superproject]

Submodule:
  ---B           [feature_a]
 /    \
A--C---D---E     [master]
    \     /
     ----F       [feature_b]

In this case submodule commit 'B' is recorded in '2' and thus '4', while commit 'F' will be recorded in '6'. So when '4' and '6' are merged, a valid guess for '5' would be to use submodule commit 'E', as it is the first one based on both 'B' and 'F'.

But in this case it is not so clear that 'E' is the right commit, as there might be other commits present in the paths 'B'->'E' and 'F'->'E'. So 'E' is just a probable solution for the merge, but not one I would like to see automatically merged. But it should be proposed to the person doing the merge as a probable resolution of the conflict, so that she can decide if that is the case.

And no 'special' branch is used here. But I think this approach will solve a lot of the problems we - and maybe others - have with submodule merges without doing any harm to other workflows.

On Thursday 17 June 2010, Jens Lehmann wrote:

Just verifying here: The superproject graph (with referenced submodule commits in parentheses) looks like this:

   --------2(D)            [Alice's branch]
  /         \
 1(A)--3(A)--4(D)---5(?)   [master]
        \          /
         ---------6(E)     [Bob's branch]

...and the conflict that causes problems when merging '4' and '6', is the 'A'->'D' vs. 'A'->'E' submodule updates.

I agree, and this is in line with my counter-proposal to Heiko: <quote> Given a submodule being part of a superproject conflict, if one of the candidate submodule SHA1s is a descendant of all the other submodule SHA1 candidates, then choose that SHA1 as the proposed resolution</quote>.

Correct. I guess this means that - for the fast-forward case - Git can automatically record this resolution in the index, hence not requiring the user to "confirm" the resolution with 'git add'.

Again, to verify: The superproject graph (with referenced submodule commits in parentheses) looks like this:

   --------2(B)            [Alice's branch]
  /         \
 1(A)--3(A)--4(B)---5(?)   [master]
        \          /
         ---------6(F)     [Bob's branch]

(Note that the situation would be different if '3' recorded 'C', as then '4' should record 'D' instead of 'B', IMHO.)

In this case, the conflict that causes problems when merging '4' and '6', is the 'A'->'B' vs. 'A'->'F' submodule updates.

And, indeed, in the scenario you present 'E' is probably the best guess '5'.

(Here, you still assume that although the submodule merges 'D'/'E' may not be done by the time Alice/Bob records '2'/'6', they are definitely done by the time the superproject maintainer gets around to creating '5'. Although this apparently works well for your case, I'm sure there are other scenarios where this is not the case, and are neither helped, nor hurt, by this effort.)

Agreed. Automatic resolving in this case is evil.

Well, you need to traverse _some_ submodule ref(s) in order to find 'E' at all. My argument is that there may also be _other_ submodule refs that contain merges of 'B' and 'F' as well, and they should _also_ be considered as valid candidates for the resolution in '5'. I would in fact argue that you should traverse _all_ submodule refs (maybe even including remote- tracking refs) to look for merges of 'B' and 'F' [1], and present them all as equal alternatives.

Consider for example this submodule scenario:

        -----------G      [maint]
       /          /
   ---B--------  /        [feature_a]
  /    \       \/
 A--C---D---E  /\         [master]
     \     /  /  \
      ----F---    \       [feature_b]
              \    \
               --H--I--J  [next]

If there exist multiple merges that resolve 'B' and 'F' (in this case: 'G', 'E' and 'I'), then all of those should be presented as equal alternatives to the user.

For the fast-forward case, I fully agree.

For the non-fast-forward case, I would suggest to search for submodule merges that contain both submodule commits (as described in [1]), and then:

- If there are no merges, do nothing (leave a conflict).

- If there is exactly one merge, then check it out (but do not record it as 
resolved in the index).

- If there are more merge alternatives, present them as equal alternatives, 
but do nothing (leave a conflict).

Have fun! :)

...Johan

[1]: To put the search in general terms: Find all merge commits that has _both_ (or in the case of octopus; _all_) of the candidate commits (but none of the other merges) somewhere in its ancestry. You could implement this by first intersecting the sets returned from these commands (run in the submodule):

  git rev-list --merges --ancestry-path --all ^B
  git rev-list --merges --ancestry-path --all ^F

to get the set of merges descending from both 'B' and 'F', and then prune each member in the remaining set that has another set member in its ancestry.

Am 18.06.2010 11:40, schrieb Johan Herland:

That's correct.

Yup, I think we agree here and I just wanted to explain our regular workflow and show that such a strategy would help us very much.

Correct.

Nice summary. Heiko, would you please post a new patch implementing this approach?

On Fri, Jun 18, 2010 at 03:55:10PM +0200, Jens Lehmann wrote:

Yes sure. I agree with the proposed scheme.

As Jens is working on the automatically checkout submodules extension I will base the merge patch on your branch. Is the checkout_submodule() function already stable enough to be used?

cheers Heiko

Am 19.06.2010 11:43, schrieb Heiko Voigt:

Thank you very much!

Unfortunately not (the checkout itself is working fine, but the test if the checkout would overwrite local changes in the submodules is still missing, so be warned!).

Hi,

On Fri, Jun 18, 2010 at 11:40:16AM +0200, Johan Herland wrote:

Is the --ancestry-path option already implemented? Because on my git 1.7.1 it does not seem to. What does it do?

cheers Heiko

On Saturday 19 June 2010, Heiko Voigt wrote:

It was recently merged to 'next'.

When given a commit range ("$from..$to", or "$to ^$from"), it shows commit that are in $to but not in $from (i.e. the usual), but additionally limits the list to those commits that descend from $from. Another use case for this functionality is, given a bug introduced in commit $foo, you can list the commit in the master branch that are potentially "contaminated" with the bug, with the following command:

  git log --ancestry-path $foo..master

See the --ancestry-path documentation in the jc/rev-list-ancestry-path series for more info.

...Johan

This implements a simple merge strategy for submodule hashes. We check whether one side of the merge candidates is already contained in the other and then merge automatically.

If both sides contain changes we search for a merge in the submodule. In case a single one exists we check that out and suggest it as the merge resolution. A list of candidates is returned when we find multiple merges that contain both sides of the changes.

This is useful for a workflow in which the developers can publish topic branches in submodules and a seperate maintainer merges them. In case the developers always wait until their branch gets merged before tracking them in the superproject all merges of branches that contain submodule changes will be resolved automatically. If developers choose to track their feature branch the maintainer might get a conflict but git will search the submodule for a merge and suggest it/them as a resolution.

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

This patch replaces the last one of the previously discussed series. It is still work in progress but already implements the scheme discussed. I have not had the time to adjust the tests so they fail currently. The extension to setup_revisions() is still very hackyish which I will also cleanup in a later iteration.

The whole series can also be found on:

http://github.com/hvoigt/git/tree/submodule_merge_v2

 merge-recursive.c          |    9 ++-
 refs.c                     |    6 ++
 refs.h                     |    1 +
 revision.c                 |   29 ++++++---
 revision.h                 |    1 +
 submodule.c                |  155 ++++++++++++++++++++++++++++++++++++++++++++
 submodule.h                |    2 +
 t/t7405-submodule-merge.sh |  115 +++++++++++++++++++++++++++++++--
 8 files changed, 300 insertions(+), 18 deletions(-)

Johan Herland <johan@herland.net> writes:

You lost me completely here.

I thought you were going to argue that it would be an utterly wrong thing to suggest E or I as a probably resolution if the superproject merge that needs to merge superproject commits that binds B and F as its submodules is being done in the context of advance 'maint' track of the superproject.

Think of 'D' as a commit that corresponds to a major version bump point of the superproject; i.e. it introduces a major change to the submodule. In the 'maintenance track' of the superproject for maintaining the previous version, you don't want to have any commit that has 'D' as an ancestor.

For an "automated" heuristics based on "find common descendants" to make sense, the branches you are merging have to share the common purpose, and you need to limit the common descendants you find to the ones that are compatible with the shared purpose. The purpose of 'maintenance track' may be to maintain the previous version without dragging newer and more exciting things that happened in the later development. In the above picture, G (that has nothing but B and F) is the only commit that can be safely assumed that two commits in the superproject space that bind B and F respectively can use as the submodule as their merge result. E and I are contaminated with D and H whose purpose in the superproject space is unknown without further hint.

On Sunday 20 June 2010, Junio C Hamano wrote:

Yes, from a 'maint'-perspective, using G in the superproject probably makes more sense than using E or I. From a different superproject perspective, though, using E or I might make more sense. If, say, the superproject customarily follows the commits on the 'master' branch in the submodule, but the superproject has not yet gotten around to updating from A to C, D or E, then, by the time we do the superproject merge of Alice and Bob's branches, I would still say that using E is better than using G.

My argument is that without knowing the purpose of the superproject merge (which Git by itself _cannot_ know), Git should not prefer _any_ of these merges over the other, but must present them all as equal alternatives to the user.

Of course, the user has other alternatives as well, like creating a whole new merge in the submodule, or doing something completely different. But if existing submodule merges are to be considered valid alternatives, Git cannot pretend to know which of those merges are more suitable. It can only present them to the user, and then the user (after having examined the merges and their history relative to B and F) may choose the merge that matches the purpose of the superproject merge.

...Johan

Johan Herland <johan@herland.net> writes:

Actually, what I was alluding to was that 'G' would be the _only_ commit that may make sense (note that G may not necessarily make sense, but the point is that we can say that others do _not_ make sense as alternatives) if we know that the context of making the superproject merge is that it is doing the 'maintenance track' merge. Similarly, if we know that the merge being done in the superproject is in the 'master' context, 'E' would be the _only_ plausible candidate, similarly for 'I' in 'next' context.

It is further plausible to imagine that the .gitmodules file tracked in the superproject's 'maint' branch can be used to express that 'maint' branch of the submodule should be used.

If we revisit the Alice and Bob example with such an arrangement, if they were working on their branches so that their results would be included in the 'maint' track of the superproject, there won't be a merge conflict in the .gitmodules file at the superproject level when their branch tips are merged; we will know that the merged .gitmodules file will tell us that we would want to follow 'maint' branch of the submodule.

Similarly if Alice were fixing a bug in 'maint' but Bob were advancing features in 'master', then merging .gitmodules at the superproject level will fast-forward at the path level (i.e. Alice didn't touch, but Bob changed, so we take Bob's change), instructing us to follow 'master' branch from the submodule automatically.

On Monday 21 June 2010, Junio C Hamano wrote:

Ah, so Git should automatically _eliminate_ other alternatives based on the fact that they are not compatible with the purpose of the superproject merge. Still, that requires Git to know the purpose of the superproject merge. Which it doesn't, AFAICS.

Ok, so you want to create some kind of relationship between the superproject's 'maint' branch and the submodule's 'maint' branch. At this point we're almost back to the (magic IMHO) "stable" branch setting that Heiko alluded to in his initial patch series. Except, possibly, that instead of using the tip of that branch you'd use the first merge of B and F on that branch.

I still don't like this, as IMHO it's too subtle, and possibly conflicts with explicitly tracking submodule branches (which, to me, is a more important feature).

Or are you talking about outright tracking submodule branches (as proposed by Ævar in a different thread)? In that case, the issue changes completely:

If you're explicitly tracking the 'maint' branch in the submodule, then IMHO Git should always propose the tip of the submodule's 'maint' branch as the merge resolution in the superproject (possibly with a warning printed if that tip does not descend from both B and F).

Ok, so these are similar to Ævar's proposal (and its subsequent discussion) for explicitly tracking submodule branches. Still not sure if we're actually talking about the same thing, though.

...Johan

Johan Herland <johan@herland.net> writes:

If you mean, by "explicitly tracking", to say "I don't care which commit from the submodule appears at this path, as long as it is at the tip of this branch", I still don't think it makes much sense, but what I outlined is not _incompatible_ with such a scheme. In fact I think it would rather fit naturally as a sanity/safety measure.

I presume that in your "explicitly tracked" world, if the user tries to commit at the superproject level with a submodule commit that is inconsistent with that "explicitly tracked" branch (e.g. the commit is not reachable from the tip of that branch), you would issue a warning of some sort, using that knowledge. What I outlined uses the exact same knowledge of which branch in the submodule the superproject branch is tied to to reject irrelevant existing merges as resolution candidates.

Of course, this ".gitmodule in superproject can tell you which branch of submodule it follows" is optional; the user needs to take responsibility of picking the right one among I, E and G, of course, if the information does not exist or is not available.

On Monday 21 June 2010, Junio C Hamano wrote:

I'll first try to explain where I'm coming from, to hopefully eliminate any confusion about my position:

IMHO, there should be 2 primary modes for submodules in Git:

A. Explicitly tracking submodule commits. This is the existing submodule behaviour. The superproject refers directly (in its tree) to a submodule commit. The .gitmodules file contains associated information (submodule.<name>.path, .url and .update).

B. Explicitly tracking submodule branches. An extra setting (submodule.<name>.branch) is added to the .gitmodules file, to determine which submodule branch to checkout. This setting overrides whatever submodule commit, if any, is stored in the superproject tree. There are two sub-modes for this mode:

B.1. There is no submodule entry at all in the superproject tree. This indicates that you are not at all interested in tracking the history of the submodule relative to the superproject. You are always interested in checking out the tip of submodule.<name>.branch in the submodule, even when digging into the superproject's history.

B.2. There is a submodule entry in the superproject tree. This "hybrid" approach indicates that although you primarily want to track a branch in the submodule (i.e. you mostly want the latest version of the submodule's branch), you still want a record of where your submodule has been pointing, in your superproject's history. Exactly when (or how often) the superproject's submodule entry should be updated is yet TBD. So is when to check out according to .branch, and when to use the recorded submodule commit. In the end, it'll probably be a policy decision for the projects that choose this approach.

Ok, that hopefully explains the basic idea of tracking submodule commits (A) vs. tracking submodule branches (B). Now, how would this apply to merging submodules?

In case of B, I'd argue that the submodule merging should _only_ look at the value of submodule.<name>.branch from the superproject's .gitmodules. If this setting is ambiguous (because of merge conflicts in .gitmodules), Git should not touch the submodule at all (until .gitmodules is resolved). Otherwise, Git's only task is to checkout whatever branch is specified by .gitmodules. If the commit that is checked out does not descend from all of the merge alternatives, a warning should be printed.

With that in mind, I enter this discussion because it might provide insight on how to solve the problem of merging submodules in scenario A.

In mode A there is no submodule.<name>.branch setting, and I would not like to add an additional setting (let's call it submodule.<name>.merge_branch for now) that is "weaker" than submodule.<name>.branch (meaning that it does not trigger the transition from mode A to mode B). There are two major reasons for this:

1. submodule.<name>.merge_branch would add semantics to the case of merging 
submodules that would be similar in spirit to what submodule.<name>.branch 
does (the "spirit" here is the special relationship to a submodule branch 
that we're establishing), but still the .merge_branch setting would be 
different in practice, by (a) only applying to the case of merging 
submodules (while .branch changes the semantics of almost all submodule 
operations), and (b) not even in the case of merging submodules would the 
options do the same thing. I fear the semantics of the .merge_branch option 
would be too complicated for an average user, and that its similarity to 
.branch would cause confusion.

2. What would happen if you enabled _both_ .merge_branch and .branch? In the 
case of merging submodules which setting will "win"? Even worse, if you set 
.merge_branch to "foo", and .branch to "bar", what will then happen?

Ok, so if I oppose adding .merge_branch, what do I propose instead?

Currently, not much, I'm afraid. But I have a gut feeling that the use case presented by Heiko and Jens is best solved EITHER by having no special branch relationships between the superproject and submodule (which AFAICS is what we currently agree on in this thread, and Heiko has already submitted a patch to this effect), OR by employing a conservative version of mode B.2 in which we use .branch to track a submodule branch, but still keep a close look at the recorded submodule commit, and, if necessary, maybe introduce some other options to tell Git when to use the recorded commit, and when to use the branch tip.

In other words, I think we should explore the .branch direction before we add complexity and potential confusion by prematurely adding another option that it somewhat similar to .branch in some contexts.

Yes.

True, but as I've argued above, I'm not sure that adding another setting (aka. .merge_branch) for this special/limited kind of branch tracking is worth it.

Yes, of course. And this corresponds to what I've proposed for scenario A, when there is no branch-related setting specified for the submodule.

Hope this helps,

...Johan

Johan Herland <johan@herland.net> writes:

I don't think .merge_branch is necessary nor even desired. In fact, I think your use of .branch, especially in the variant that does not have any submodule entry in the superproject tree, of your version (B) does not have conceptual advantage. You checkout the superproject first (which would be the natural thing to do, as you may get update to its .gitmodules there), and checkout the then-tip of the named branch of the submodule, you would immediately get a stale checkout when you then go fetch the updates to the submodule.

And the worst part is that you wouldn't even _notice_ that your checkout is stale, as there is no record in the superproject which commit you were supposed to be using to be consistent with the version the committer of the superproject commit used to record it.

I on the other hand think what you called "hybrid" makes sense (and I don't even think it is hybrid but rather is a natural way to do this). With the submodule.*.branch entry, you can:

 - make sure that your checkout is consistent; if your submodule checks
   out a different commit or branch from what the superproject records in
   its tree or in its .gitmodules (e.g. you forgot to update the submodule
   when you switched superproject branch), git can notice the situation
   and can help you implement policy decisions;

 - record a commit that is different from the tip of the submodule branch
   when making a superproject commit; git can notice the situation and can
   help you implement policy decisions (e.g. you could choose to reject
   and tell the user to advance the submodule branch first before making
   the commit in the superproject);

 - use it as an advisory "existing merge commit selector", as discussed in
   this thread.

Thinking about what would happen in your (B) that doesn't record the exact commit, I think that it doesn't have any advantage over the "hybrid" one. The "hybrid" one can help you to make sure that what you commit in the superproject's .gitmodules and submodule's branch tip are kept consistent. When they are kept consistent, then switching branches in the superproject should always flip between the tips of branches, no?

On Tuesday 22 June 2010, Junio C Hamano wrote:

Good.

Not if the initial checkout of the submodule included an implicit fetch/pull within the submodule (exact behaviour probably to be controlled with some config).

The idea (in B.1.) is that if you _truly_ don't care which version of the submodule you're checking out, then there should be no submodule entry in the superproject that would "pollute" your status/diffs.

Note that I'm not in this camp myself, as I would very much like to keep track of where my submodule is (and has been) checked out. So I'll stop trying to argue for a use case that I'm not going to use. At the time, it seemed like a logical conclusion of the tracking-submodule-branches debate, but if it's not going to be used in practice, there's no point in keeping it alive.

Agreed. I too believe that the "hybrid" is much more useful in practice than the extreme version (without a gitlink entry in the superproject).

But I also believe that Git shouldn't enforce specific workflows, so that if people actually want to track submodule branches in the non-"hybrid" (haphazard) manner, then Git should not stand in their way.

On the other hand, if nobody's gonna do this, there's no point in implementing support for it.

Ah, I see. IINM you indeed prefer to use the same setting (aka. submodule.<name>.branch) for controlling both the merging of submodules (as discussed in this thread), and the other aspects of the submodule branch tracking feature. We agree here.

However, it seems you would like the .branch setting to be more advisory in nature: Instead of blindly checking out whatever .branch specifies, you'd rather have a more careful interplay where the .branch option should only check whether it is consistent with what happens to be checked out in the submodule, and warn when this is not the case.

This may be better than what I suggested, but it's hard to say anything for sure until the various alternatives are tested in practice.

Yes, if branch "foo" in the superproject records "branch = subfoo" in .gitmodules, and the current tip of "subfoo" as a gitlink, and branch "bar" in the superproject records "branch = subbar" in .gitmodules and the current tip of "subbar" as a gitlink, then, indeed, switching between these two branches should auto-flip between the branch tips.

One of the remaining questions is what happens when the superproject does not change, but commits are added to the submodule branches. Now, when switching between branches in the superproject, should Git:

1. Do nothing (this is the current behaviour, the user is forced to 'git 
submodule update' after 'git checkout' in the superproject)

2. Only checkout the recorded gitlink (this defeats the purpose of 
branch-tracking, IMO)

3. Checkout the recorded gitlink, but warn about the updated branch tip 
(a valid behaviour IMO)

4. Checkout the updated branch tip of the submodule, and warn about the 
out-of-date gitlink entry (also a valid behaviour IMO)

5. Checkout the updated branch tip AND stage a new gitlink in the 
superproject (this is a bit to "magic", IMO)

...Johan

On Mon, Jun 21, 2010 at 12:19:02PM +0200, Johan Herland wrote:

This appears to be a good time to resuscitate an idea we had a while ago:

Why not make merging recursive wrt submodules?

I have been trying for some time to figure out how to use git for some huge projects that consist of hundreds of more or less tightly coupled modules. Some of these modules are used for multiple projects, and taken together they are too large to fit well into a single repository.

I wouuld like to be able to use submodules to achieve several things:

1. Partial clones/checkouts - clone only the modules you need
2. Make git behave for projects that are too large for a single repo
3. Bonus: share some modules between muptiple projects

Now - for each superproject I would like this to behave as closely as possible to working with a single repo, so for merging this would mean that any merge from toplevel would automatically do the merge in all affected submodules as well. Just merge the sha1's directly, don't try to be clever - merge as if it was a subdirectory.

- Finn Arne