Consequences of using graft in Mercurial

Question

There've been several questions recently about skipping changes when maintaining release branches in Mercurial. For example:

• Mercurial: Branch specific changes keep coming back after dummy merge
• Why are Mercurial backouts in one branch affecting other branches?

Since it was introduced in 2.0, I've wondered about using graft to avoid this problem. Given a revision tree like this:

A---B---C---D---E---F---G---H---I---J

Suppose we need to create a release branch that skips the Evil change E.

hg update -r D
hg graft "F::J"

giving us:

A---B---C---D---E---F---G---H---I---J
             \
              --F'--G'--H'--I'--J'

• Q1: What just happened here? I can understand that transplant would have generated patches out of F::J, and then applied them onto D, but graft is said to use the 3-way merge rather than patches. So....... how does that work? Why is it better?

Lets say I now fix E, and merge that into my release branch.

                  --E2-----------------
                 /                     \
A---B---C---D---E---F---G---H---I---J---M1
             \                            \
              --F'--G'--H'--I'--J'---------M2--

M1 is a straight merge; nothing special there. M2 is merging branches which have "the same" (or at least equivalent) changes on.

• Q2: Is this merge just a normal 3-way merge using D, J' and M1?
• Q3: Has mercurial stored/used extra information about the graft operation to help it with the merge?

And finally...

• Q4: What are the potential problems with a flow like this?

Solution 1

When you update to D and graft F::J, Mercurial runs a number of merges. It will start with this merge:

M = three_way_merge(local=D, other=F, base=E)

If we write +d for the delta between the states C and D, then we start with:

        +d     +e     +f
---- C ---- D ---- E ---- F ----

Turn the graph 90 degrees clockwise and the above three-way merge looks like this:

    -e  
  .---- D
 /
E
 \
  '---- F
    +f

That is, we pretend that we started with E and applied the opposite of -e to get to D. I think of as the reverse patch of +e. Starting in E we also went to state F with the normal delta +f. There's nothing strange here — we have all the states (D, E, and F) in the repository already. So seen like this, it's clear that we can merge D and F.

Merging is a matter of "completing the diamond". So we find a new state M that is a mix of D and F and where the difference from D to M is similar to +f and the difference from F to M is similar to -e. It looks like this:

    -e     +f'
  .---- D ----.
 /             \
E               M
 \             /
  '---- F ----'
    +f     -e'

The +f delta became +f' and the -e delta became -e'. This is just a normal three-way merge, but the effect is interesting: we've applied F onto D instead of E!

After the merge, the second parent of M to F is dropped:

    -e     +f'
  .---- D ----.
 /             \
E               M
 \
  '---- F
    +f

To reiterate: We have copied the "effect" of F onto D, that is, we have found a delta (+f') that applied to D give the same effect as when +f was applied to E. We can straighten the graph a bit to get:

       +f'
--- D ---- M
     \
      '---- E ---- F
        +e     +f

The result is that F is grafted onto D using the full three-way machinery.

• Q1: What just happened here? So....... how does that work? Why is it better?

  A1: Using merges is better than patches since the merge machinery takes things like renames into account.

• Q2: Is this merge just a normal 3-way merge using D, J' and M1?

  A2: Yes, grafting does not alter the topology of the graph.

• Q3: Has mercurial stored/used extra information about the graft operation to help it with the merge?

  A3: No.

• Q4: What are the potential problems with a flow like this?

  A4: From a merge perspective it should work okay. It will duplicate some history which might be confusing for people.

Solution 2

Q1: It helps when there are conflicts. You can use your usual merge tool then (for me it's inline conflict markers, which I edit with Emacs' smerge-mode).

Q2: It's a normal merge.

Q3: No.

Q4: I think it's ugly to have two almost identical branches.

Comments

[Laurens Holst]

Great question, great answer :). +1 to both!

[Paul S]

Thanks Martin. That's some pretty funky thinking by whoever came up with that. I've got the idea, but need to work out the general case. I'm guessing it holds no matter the path between nodes you're grafting to/from?

[Martin Geisler]

@PaulS: I think all you need to know is that graft can copy changesets around in a more robust way than transplant can. Robust in the sense that renames are handled and that you can resolve conflicts in a merge tool. The details are in the strange merges it does, but that's hopefully not essential to understand for everyday use of graft! :-)

[Paul S]

No, but I'm a sucker for trying to understand stuff I don't need to ;-) I worked through a more general example using your one as a base anyway.

[Martin Geisler]

@PaulS If so, then I'm almost afraid to mentioning this to you... but you can look up Darcs and its patch theory. The trick above about rotating the graph 90 degrees reminds me a lot of how they talk about commuting patches when merging. Pretty hairy stuff :-)

[cbehanna]

Martin, could you write briefly (or not, if it's impossible) about how this differs from using hg export/import to do the cherrypicking (e.g., as shown in the help for "export" on the hg man page)?

[Afriza N. Arief]

So seen like this, it's clear that we can merge D and E. -> shouldn't this be D and F? So we find a new state M that is a mix of D and E -> shouldn't this be D and F as well?

[shredding]

So what will happen if we merge J' with E? J' is E "aware" and it wants to exclude all the changes from E. Will this make the merge do nothing?