Sharing a massive distributed merge

Sharing a massive distributed merge

[Joshua Jensen]

We have two codelines that diverged quite a while back, and we are now 
bringing them back together.  More than 800 files are in conflict, but 
it is very possible that the automatic non-conflicting merge is not 
correcting.  This means thousands of files need to be examined.

Git doesn't support distribution of a merge (although that would be 
extraordinarily cool), so the next best thing seemed to be force adding 
all files with conflict markers and then committing the merge.  We then 
publish the conflicting branch and have each person fix their files.  
Given that the conflict markers are already in place, they can't use 
their favorite graphical merge tool.

What I want to be able to do is have each person perform the merge 
locally, stage only the files they care about in that session, reset all 
other files, and commit as a regular commit, not a merge commit.  The 
user can take advantage of whatever tools they want in the in progress 
merge.  When everyone has finished this process, we run git merge and 
keep our local changes.

I have had no success in doing the above.  Is there a fancy way to pull 
this off with Git?

Thanks.

Josh

Re: Sharing a massive distributed merge

[Jay Soffian]

On Wed, Mar 16, 2011 at 4:12 PM, Joshua Jensen
<jjensen@workspacewhiz.com> wrote:
> We have two codelines that diverged quite a while back, and we are now
> bringing them back together.  More than 800 files are in conflict, but it is
> very possible that the automatic non-conflicting merge is not correcting.
>  This means thousands of files need to be examined.

Have you considered breaking this up into multiple merges, so that
each merge deals with only a subset of the conflicts? This may mean
more work overall, but makes reviewing each individual merge much more
tenable.

IOW, given a history like:

 a--b--c--d--e...z
  \
   1--2--3--4...25

Instead of trying to merge z into 25, first merge b, then c, etc. I'd
try a divide and conquer approach - merge half way back to the common
ancestor, it that's too big, go half way back again, etc.

This obviously doesn't parallelize the effort.

> Git doesn't support distribution of a merge (although that would be
> extraordinarily cool), so the next best thing seemed to be force adding all
> files with conflict markers and then committing the merge.  We then publish
> the conflicting branch and have each person fix their files.  Given that the
> conflict markers are already in place, they can't use their favorite
> graphical merge tool.

Well, this is awful, but you could do something like:

for x in conflicted_files:
   git show :1:$x > $x.base
   git show :3:$x > $x.theirs
   git checkout --ours $x
   git add $x.base $x.theirs $x

Commit that, then folks can use their favorite merge tools, commit the
result, and remove the .base and .theirs.

Notes:

- I'd do all this work on its own branch. When all the files have been
resolved, then do a real merge, but consult the branch for the
conflict resolution, e.g. "git merge ...; git checkout
merge_resolution -- ."

- See git-mergetool.sh for how to use checkout-index instead of "show
:<stage>:..."

- This only handles modify/modify conflicts.

- You might want to use "merge.conflictstyle diff3" and commit that
file too so that there's a reference file with the conflict markers --
I find the diff3 style very helpful in addition to GUI mergetools, for
which I've not found one that does a good presentation of theirs,
ours, base, and resolved.

> What I want to be able to do is have each person perform the merge locally,
> stage only the files they care about in that session, reset all other files,
> and commit as a regular commit, not a merge commit.  The user can take
> advantage of whatever tools they want in the in progress merge.  When
> everyone has finished this process, we run git merge and keep our local
> changes.

$ git merge --squash other_branch
# resolve foo
$ git commit -m "resolved foo" -- foo
$ git reset --hard

Though I think the "awful" solution above might prove less error prone
and do a better job of keeping track of the remaining work.

j.

Re: Sharing a massive distributed merge

[Jeff King]

On Thu, Mar 17, 2011 at 01:21:19AM -0400, Jay Soffian wrote:

> > Git doesn't support distribution of a merge (although that would be
> > extraordinarily cool), so the next best thing seemed to be force adding all
> > files with conflict markers and then committing the merge.  We then publish
> > the conflicting branch and have each person fix their files.  Given that the
> > conflict markers are already in place, they can't use their favorite
> > graphical merge tool.
> 
> Well, this is awful, but you could do something like:
> 
> for x in conflicted_files:
>    git show :1:$x > $x.base
>    git show :3:$x > $x.theirs
>    git checkout --ours $x
>    git add $x.base $x.theirs $x
> 
> Commit that, then folks can use their favorite merge tools, commit the
> result, and remove the .base and .theirs.

I don't think you need to do anything so drastic. You can just have
everybody do the partial merge, commit, and then push their result.  And
then as you suggest below, one person does the real merge, uses checkout
to install the desired result state from each person's partial tree, and
then everybody throws away their partial merges.

The trick is that each person will resolve some conflicts and commit,
but you need to know which ones they resolved. They can't leave things
unmerged in the final commit. So they would have to provide such a list
to you; one way is in the commit message[1].

So let's say you have three devs, Alice, Bob, and Charlie, and one
integrator, Matt, who will do the merge. Each of the developers does:

  git checkout -b partial-merge
  git merge old-topic
  git mergetool ;# or manually resolve and git add

Eventually they get tired of the conflicts and give up. So they record
the list of resolved paths, either manually or with something like[2]:

  {
    echo 'partial merge result'
    echo

    git status --porcelain | perl -ne '
      next if /^U|\?/;
      s/^\S+\s+//;
      print;
    '

  } >msg

And then they stage the rest of it (knowing it will be ignored by Matt)
and commit:

  git add -u
  git commit -F msg
  git push wherever partial-merge

Then Matt does the actual merge:

  git merge old-topic

which of course results in lots of conflicts. So he pulls resolved
versions from each person's tree:

  for i in alice bob charlie; do
    git fetch $i
    git checkout $i/partial-merge -- \
      `git log -1 --format:%b $i/partial-merge`
  done

And then fixes up whatever's left manually or with git-mergetool, and
commits the end result.

Take all of my scripting there as illustrative of the concept, but not
necessarily a good idea. In particular, it doesn't handle quoting of
filenames at all, and it probably doesn't handle files whose resolution
was to be deleted (since the checkout will fail).

-Peff

[1] I also considered that instead of noting the resolved files in the
commit message, the developers could just remove anything they didn't
resolve. After all, their tree is going to be thrown away eventually.
Then Matt could just script around "git ls-tree" to pull their files
out. The downside is that there is no way for the developers to say "the
resolution is to delete this file", since it just looks like something
they didn't resolve.

[2] It really seems like the right command to get the list of resolved
files would be "git diff-index" with either a diff-filter, or grepping
the output of --name-status. But I couldn't convince it to show me
unmerged files; the unmerged entries always just appeared as
modifications (actually, deletions in --raw), which made them
indistinguishable from modified resolutions.

Re: Sharing a massive distributed merge

[Jay Soffian]

On Thu, Mar 17, 2011 at 2:38 AM, Jeff King <peff@peff.net> wrote:
> [2] It really seems like the right command to get the list of resolved
> files would be "git diff-index" with either a diff-filter, or grepping
> the output of --name-status. But I couldn't convince it to show me
> unmerged files; the unmerged entries always just appeared as
> modifications (actually, deletions in --raw), which made them
> indistinguishable from modified resolutions.

I use this alias for getting unmerged files:

$ git help unmerged
`git unmerged' is aliased to `!git ls-files --unmerged | cut -f2 | uniq'

j.

Re: Sharing a massive distributed merge

[Jeff King]

On Thu, Mar 17, 2011 at 03:04:14AM -0400, Jay Soffian wrote:

> On Thu, Mar 17, 2011 at 2:38 AM, Jeff King <peff@peff.net> wrote:
> > [2] It really seems like the right command to get the list of resolved
> > files would be "git diff-index" with either a diff-filter, or grepping
> > the output of --name-status. But I couldn't convince it to show me
> > unmerged files; the unmerged entries always just appeared as
> > modifications (actually, deletions in --raw), which made them
> > indistinguishable from modified resolutions.
> 
> I use this alias for getting unmerged files:
> 
> $ git help unmerged
> `git unmerged' is aliased to `!git ls-files --unmerged | cut -f2 | uniq'

Yeah, that would work. Though we really want the list of _resolved_
files. So you'd have to do something like:

  git ls-files --unmerged | cut -f2 | uniq >unmerged
  git diff-index HEAD >all
  comm -23 all unmerged

which is why I was hoping to do it with diff-index in the first place.

-Peff

Re: Sharing a massive distributed merge

[Jeff King]

On Thu, Mar 17, 2011 at 03:30:53AM -0400, Jeff King wrote:

> On Thu, Mar 17, 2011 at 03:04:14AM -0400, Jay Soffian wrote:
> 
> > On Thu, Mar 17, 2011 at 2:38 AM, Jeff King <peff@peff.net> wrote:
> > > [2] It really seems like the right command to get the list of resolved
> > > files would be "git diff-index" with either a diff-filter, or grepping
> > > the output of --name-status. But I couldn't convince it to show me
> > > unmerged files; the unmerged entries always just appeared as
> > > modifications (actually, deletions in --raw), which made them
> > > indistinguishable from modified resolutions.
> > 
> > I use this alias for getting unmerged files:
> > 
> > $ git help unmerged
> > `git unmerged' is aliased to `!git ls-files --unmerged | cut -f2 | uniq'
> 
> Yeah, that would work. Though we really want the list of _resolved_
> files. So you'd have to do something like:
> 
>   git ls-files --unmerged | cut -f2 | uniq >unmerged
>   git diff-index HEAD >all
>   comm -23 all unmerged
> 
> which is why I was hoping to do it with diff-index in the first place.

Hmph. An unrelated thread just contained the answer I wanted. It's:

  git diff-index --cached --name-status

which properly produces "U" entries. How's that for user-friendly?

-Peff

Re: Sharing a massive distributed merge

[Joshua Jensen]

Thank you, everyone, for all the feedback.  It still isn't clear to me 
how we can only resolve part of a merge and easily throw away all the 
other files, but we moved forward by just committing the conflict 
markers and resolving from there.

Josh

Re: Sharing a massive distributed merge

[Alex Riesen]

On Thu, Mar 17, 2011 at 07:38, Jeff King <peff@peff.net> wrote:
> I don't think you need to do anything so drastic. You can just have
> everybody do the partial merge, commit, and then push their result.  And
> then as you suggest below, one person does the real merge, uses checkout
> to install the desired result state from each person's partial tree, and
> then everybody throws away their partial merges.
>
> The trick is that each person will resolve some conflicts and commit,
> but you need to know which ones they resolved. They can't leave things
> unmerged in the final commit. So they would have to provide such a list
> to you; one way is in the commit message[1].
>
> So let's say you have three devs, Alice, Bob, and Charlie, and one
> integrator, Matt, who will do the merge. Each of the developers does:
>
>  git checkout -b partial-merge
>  git merge old-topic
>  git mergetool ;# or manually resolve and git add
>
> Eventually they get tired of the conflicts and give up. So they record
> the list of resolved paths, either manually or with something like[2]:
>
...
>
> And then they stage the rest of it (knowing it will be ignored by Matt)
> and commit:
>

What if they just revert the rest? Reset the files to their states before
merge. Than Matt can just collect the partial merges with a merge on
his side and take care of the conflicts left, which should be fewer.

Re: Sharing a massive distributed merge

[Jay Soffian]

On Thu, Mar 17, 2011 at 4:53 AM, Alex Riesen <raa.lkml@gmail.com> wrote:
> What if they just revert the rest? Reset the files to their states before
> merge.

That's the same as checkout --ours which is sometimes a valid
resolution for a file. So I think "I resolved this file" needs to be
recorded either way.

j.

Re: Sharing a massive distributed merge

[Alex Riesen]

On Thu, Mar 17, 2011 at 15:10, Jay Soffian <jaysoffian@gmail.com> wrote:
> On Thu, Mar 17, 2011 at 4:53 AM, Alex Riesen <raa.lkml@gmail.com> wrote:
>> What if they just revert the rest? Reset the files to their states before
>> merge.
>
> That's the same as checkout --ours which is sometimes a valid
> resolution for a file. So I think "I resolved this file" needs to be
> recorded either way.

But it is recorded: the file is different now!

Re: Sharing a massive distributed merge

[Jay Soffian]

On Thu, Mar 17, 2011 at 10:54 AM, Alex Riesen <raa.lkml@gmail.com> wrote:
> On Thu, Mar 17, 2011 at 15:10, Jay Soffian <jaysoffian@gmail.com> wrote:
>> On Thu, Mar 17, 2011 at 4:53 AM, Alex Riesen <raa.lkml@gmail.com> wrote:
>>> What if they just revert the rest? Reset the files to their states before
>>> merge.
>>
>> That's the same as checkout --ours which is sometimes a valid
>> resolution for a file. So I think "I resolved this file" needs to be
>> recorded either way.
>
> But it is recorded: the file is different now!

Let's say we have:

  a---b---c
   \
    d---e

$ git checkout c
$ git merge e  # files "foo" and "bar" conflict
$ git checkout --ours foo  # correct resolution for foo
$ git checkout HEAD bar    # "revert" bar to its pre-merge state
$ git add foo
$ git commit

In the merge commit, both "foo" and "bar" are identical to their
pre-merge state. There's no effective difference between the "checkout
--ours" and "reset the files to their states before the merge".

So again, how do you tell the difference here?

j.

Re: Sharing a massive distributed merge

[Alex Riesen]

On Thu, Mar 17, 2011 at 18:58, Jay Soffian <jaysoffian@gmail.com> wrote:
> On Thu, Mar 17, 2011 at 10:54 AM, Alex Riesen <raa.lkml@gmail.com> wrote:
>> On Thu, Mar 17, 2011 at 15:10, Jay Soffian <jaysoffian@gmail.com> wrote:
>>> On Thu, Mar 17, 2011 at 4:53 AM, Alex Riesen <raa.lkml@gmail.com> wrote:
>>>> What if they just revert the rest? Reset the files to their states before
>>>> merge.
>>>
>>> That's the same as checkout --ours which is sometimes a valid
>>> resolution for a file. So I think "I resolved this file" needs to be
>>> recorded either way.
>>
>> But it is recorded: the file is different now!
>
> Let's say we have:
>
>  a---b---c
>   \
>    d---e
>
> $ git checkout c
> $ git merge e  # files "foo" and "bar" conflict
> $ git checkout --ours foo  # correct resolution for foo

I doubt that'll be a correct resolution. Someone have to look
at the conflict markers, right?

> $ git checkout HEAD bar    # "revert" bar to its pre-merge state
> $ git add foo
> $ git commit
>
> In the merge commit, both "foo" and "bar" are identical to their
> pre-merge state. There's no effective difference between the "checkout
> --ours" and "reset the files to their states before the merge".
>
> So again, how do you tell the difference here?
>

The difference may be simple (git diff --name-status c^..),
it just does not help. The merge commit will record the
branches as merged and an attempt by the maintainer to merge
this partial merge commit will just fast-forward. So it was
a stupid idea either way.

How about not to record the merge as a merge commit, but
just resolve as much as possible, commit _only_ what was
resolved, and revert everything else. Including files merged
cleanly, as the last merge by maintainer will have to clean
merge them anyway. And of course, commit as normal:

  $ git merge --squash --no-commit e

The maintainer will have to collect the branches with resolved
conflicts, and fix up the conflicts left.

Could be less work, given good coordination of who resolves what...

Re: Sharing a massive distributed merge

[Jeff King]

On Thu, Mar 17, 2011 at 07:48:54PM +0100, Alex Riesen wrote:

> How about not to record the merge as a merge commit, but
> just resolve as much as possible, commit _only_ what was
> resolved, and revert everything else. Including files merged
> cleanly, as the last merge by maintainer will have to clean
> merge them anyway. And of course, commit as normal:

But that still has the same problem. You've reverted unresolved files
back to the pre-merge state, which is the tip of one of the merged
branches. How does the integrator differentiate that from the case that
your resolution happened to take one side of a file?

For example, try this:

    git init repo && cd repo

    echo base >file1
    echo base >file2
    git add .
    git commit -m base

    echo master >>file1
    echo master >>file2
    git commit -a -m master

    git checkout -b topic HEAD^
    echo topic >>file1
    echo topic >>file2
    git commit -a -m topic

    git merge master

    # now we have a conflict. Both files are identically conflicted.
    # Let's resolve one in favor of topic.
    cat >file1 <<'EOF'
    base
    topic
    EOF
    git add file1

    # Now let's mark the other as unresolved. The proposal is to revert
    # it back to the pre-merge state.
    git checkout HEAD -- file2

    # And commit the partial result.
    git commit -m 'partial result'

It should be easy to see that the two cases are indistinguishable: both
files contain the exact same content in the reuslting partial result
(and obviously the fact that they are identical is contrived, but the
point is that for any given file, you don't know which thing happened
during the partial merge).

Which is why I suggested deletion as an option, but that also conflicts
with a possible resolution (it's just a less likely one). I think every
tree state that you could commit to mark "this isn't resolved" is going
to overlap with some possible actual resolution state. So you need an
external list.

It would be neat if the tree could somehow mark a bit for "this is
unresolved". I guess we could shove it into a mode bit. But that seems
like a waste of a mode bit for this one use case that doesn't come up
all that often, and which doesn't _need_ to represent that information
in-tree. The commit-message solution would work perfectly fine.

-Peff

Re: Sharing a massive distributed merge

[Alex Riesen]

On Thu, Mar 17, 2011 at 20:15, Jeff King <peff@peff.net> wrote:
> On Thu, Mar 17, 2011 at 07:48:54PM +0100, Alex Riesen wrote:
>
>> How about not to record the merge as a merge commit, but
>> just resolve as much as possible, commit _only_ what was
>> resolved, and revert everything else. Including files merged
>> cleanly, as the last merge by maintainer will have to clean
>> merge them anyway. And of course, commit as normal:
>
> But that still has the same problem. You've reverted unresolved files
> back to the pre-merge state, which is the tip of one of the merged
> branches. How does the integrator differentiate that from the case that
> your resolution happened to take one side of a file?

Maybe they're lucky and it just never happens? But yes, of course...

Re: Sharing a massive distributed merge

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> It would be neat if the tree could somehow mark a bit for "this is
> unresolved". I guess we could shove it into a mode bit. But that seems
> like a waste of a mode bit for this one use case that doesn't come up
> all that often, and which doesn't _need_ to represent that information
> in-tree. The commit-message solution would work perfectly fine.

Just adding the blob with the whole glory of <<</>>> markers would be
better than recording --ours or --theirs.  Deleting might be a workaround
that would work better in practice as somebody already mentioned, though.

I agree that message is an essential part of the communication medium to
coordinate this kind of workflow.  It is not like the downstream is a dumb
machinery that blindly grab and overlay the partial merge results that can
only read from tree objects and not commit messages.

Where do all the tips go? (Was: Re: Sharing a massive distributed merge)

[Victor Engmark]

On 03/17/2011 07:38 AM, Jeff King wrote:
> On Thu, Mar 17, 2011 at 01:21:19AM -0400, Jay Soffian wrote:
> 
>>> Git doesn't support distribution of a merge (although that would be
>>> extraordinarily cool), so the next best thing seemed to be force adding all
>>> files with conflict markers and then committing the merge.  We then publish
>>> the conflicting branch and have each person fix their files.  Given that the
>>> conflict markers are already in place, they can't use their favorite
>>> graphical merge tool.
>>
>> Well, this is awful, but you could do something like:
>>
>> for x in conflicted_files:
>>    git show :1:$x > $x.base
>>    git show :3:$x > $x.theirs
>>    git checkout --ours $x
>>    git add $x.base $x.theirs $x
>>
>> Commit that, then folks can use their favorite merge tools, commit the
>> result, and remove the .base and .theirs.
> 
> I don't think you need to do anything so drastic. You can just have
> everybody do the partial merge, commit, and then push their result.  And
> then as you suggest below, one person does the real merge, uses checkout
> to install the desired result state from each person's partial tree, and
> then everybody throws away their partial merges.
> 
> The trick is that each person will resolve some conflicts and commit,
> but you need to know which ones they resolved. They can't leave things
> unmerged in the final commit. So they would have to provide such a list
> to you; one way is in the commit message[1].
> 
> So let's say you have three devs, Alice, Bob, and Charlie, and one
> integrator, Matt, who will do the merge. Each of the developers does:
> 
>   git checkout -b partial-merge
>   git merge old-topic
>   git mergetool ;# or manually resolve and git add
> 
> Eventually they get tired of the conflicts and give up. So they record
> the list of resolved paths, either manually or with something like[2]:
> 
>   {
>     echo 'partial merge result'
>     echo
> 
>     git status --porcelain | perl -ne '
>       next if /^U|\?/;
>       s/^\S+\s+//;
>       print;
>     '
> 
>   } >msg
> 
> And then they stage the rest of it (knowing it will be ignored by Matt)
> and commit:
> 
>   git add -u
>   git commit -F msg
>   git push wherever partial-merge
> 
> Then Matt does the actual merge:
> 
>   git merge old-topic
> 
> which of course results in lots of conflicts. So he pulls resolved
> versions from each person's tree:
> 
>   for i in alice bob charlie; do
>     git fetch $i
>     git checkout $i/partial-merge -- \
>       `git log -1 --format:%b $i/partial-merge`
>   done
> 
> And then fixes up whatever's left manually or with git-mergetool, and
> commits the end result.
> 
> Take all of my scripting there as illustrative of the concept, but not
> necessarily a good idea. In particular, it doesn't handle quoting of
> filenames at all, and it probably doesn't handle files whose resolution
> was to be deleted (since the checkout will fail).

This discussion is great! Is there some place where this sort of a thing
usually ends up, such as a wiki or the Git Community Book
<http://book.git-scm.com/>?

Cheers,
-- 
Victor Engmark

Re: Where do all the tips go? (Was: Re: Sharing a massive distributed merge)

[Jeff King]

On Thu, Mar 17, 2011 at 08:51:58AM +0100, Victor Engmark wrote:

> > Take all of my scripting there as illustrative of the concept, but not
> > necessarily a good idea. In particular, it doesn't handle quoting of
> > filenames at all, and it probably doesn't handle files whose resolution
> > was to be deleted (since the checkout will fail).
> 
> This discussion is great! Is there some place where this sort of a thing
> usually ends up, such as a wiki or the Git Community Book
> <http://book.git-scm.com/>?

There's an FAQ section on the wiki:

  https://git.wiki.kernel.org/index.php/GitFaq

though I am not sure this is frequently asked. The Git Community Book
seems pretty inactive these days. The last work on it is about 2 years
old:

  https://github.com/schacon/gitbook

These days Pro Git is freely available and seems much more active:

  https://github.com/progit/progit

I know Scott is collecting random advanced topics like this for an
eventual second edition. Maybe this topic would be of interest.

-Peff