[PATCH] Improved named branch support when pushing changesets

[Henrik Stuart]

Henrik Stuart skrev:
> Matt Mackall wrote:
>> On Thu, 2009-03-26 at 22:13 +0100, Sune Foldager wrote:
>>> On 26/03/2009, at 20.15, Matt Mackall wrote:
>>>
>>>> Very interesting.
>>> Thanks :-)
>>>
>>>> Did you consider using lookup to lookup individual heads?
>>> Yes, we did consider using the already available information, as well  
>>> as already available wire-commands to get the desired information  
>>> across. The problem is that a branch head isn't necessarily a head in  
>>> the graph, so remote.heads() won't always return it. Even if it could  
>>> work with lookup, we would get quite a few roundtrips for complex  
>>> repositories. Extending with a 'branchmap' command, we get all the  
>>> information (all heads on all branches) in a single chunk :-).
>> The idea would be to lookup the remote revisions for local new branch
>> heads. ie I push stable which is inactive in the remote repo, so I
>> detect push would add one new head, namely my 'stable' head. I look up
>> remote 'stable' and discover that it's an ancestor of my local 'stable'
>> head, so everything's copacetic.
>>
>> Not terribly expensive and works with servers going back quite some
>> time. Not sure it's sufficient to do everything right though.

This is a follow-up mail to the one we sent in March, in an effort to
get the named branch support into crew.

BACKGROUND

This mail tries to explain some alternative solutions to considering
named branches when determining whether it is OK to push changesets to a
remote repository.

The algorithm currently implemented in Mercurial only considers the
graph theoretical heads when determining whether new heads are created,
rather than using the branch heads as a count (the algorithm considers a
branch head effectively closed when it is merged into another branch or
a new named branch is started from that point onward).

Our particular problem with the algorithm is that we'd like to see the
following case working without forcing a push:

  Upsteam has:

    (0:dev) ---- (1:dev)
            \--- (2:stable)

  Someone merges stable into dev:

    (0:dev) ---- (1:dev) ------(3:dev)
            \--- (2:stable) --/

  This can be pushed without --force (as it should).
  Now someone else does some coding on stable (a bug fix, say):

    (0:dev) ---- (1:dev) ------(3:dev)
            \--- (2:stable) --/---------(4:stable)

  This time we need --force to push.

We allow this to be pushed without using --force by getting all the
remote branch heads (by extending the wire protocol with a new function).

We would, furthermore, also prefer if it is impossible to push a new
branch without --force (or a later --newbranch option so --force isn't
shoe-horned into too many disparate functions, if need be), except of
course in the case where the remote repository is empty.

This is what our patch accomplishes.


ALTERNATIVES

We have, of course, considered some alternatives to reconstructing
enough information to decide whether we are creating new remote branch
heads, before we added the new wire protocol command.


LOOKUP ON REMOTE

The main alternative is to use the information from remote.heads() and
remote.lookup() to try to reconstruct enough graph information to decide
whether we are creating new heads. This is not adequate as illustrated
below.

Remember that each lookup is typically a request-response pair over SSH
or HTTP(S).

If we have a simple repository at the remote end like this:

  (0:dev) ---- (1:dev) ---- (3:stable)
         \
          `--- (2:dev)

then remote.heads() will yield [2, 3]. Assume we have nodes [0, 1, 2]
locally and want to create a new node, 4:dev, as a descendant from
(1:dev), which should be OK as 1:dev is a branch head.

If we do remote.lookup('dev') we will get [2]. Thus, we can get
information about whether a branch exists on the remote server or not,
but this does not solve our problem of figuring out whether we are
creating new heads or not.

Pushing 4:dev ought to be OK, since after the push, we still only have
two heads on branch a.

Using remote.lookup() and remote.heads() is thus not adequate to
consistently decide whether we are creating new remote heads (e.g. in
this situation the latter would never return 1:dev).


USING INCOMING TO RECONSTRUCT THE GRAPH

An alternative would be to use information equivalent to hg incoming to
get the full remote graph in addition to the local graph.

To do this, we would have to get a changegroup(subset) bundle
representing the remote end (which may be a substantial amount of data),
getting the branch heads from an instantiated bundlerepository, deleting
the bundle, and finally, we can compute the prepush logic.

While this is backwards compatible, it will cause a possibly substantial
slowdown of the push command as it first needs to pull in all changes.


FURTHER ARGUMENTS IN FAVOUR OF THE BRANCHMAP WIRE-PROTOCOL EXTENSION

Currently, the commands incoming and pull, work based on the tip of a
given branch if used with "-r branchname", making it hard to get all
revisions of a certain branch only (if it has multiple heads). This can
be solved by requesting the remote's branchheads and letting the
revisions to be used with the command be these heads. This can be done
by extending the commands with a new option, e.g.:

  hg pull -b branchname

which will be turned into the equivalent of:

  hg pull -r branchhead1 -r branchhead2 -r branchhead3

We have a simple follow-up patch that can do this ready as well
(although not submitted yet as it is pending the acceptance of the
branch patch).


WRAP-UP

We generally find that the branchmap wire protocol extension can provide
better named branch support to Mercurial. Currently, some things, like
the initial push scenario in this mail, are fairly counter-intuitive,
and the more often you have to force push, the more it is likely you
will get a lot of spurious and unnecessary merge nodes. Also,
restricting incoming and pull to all changes on a branch rather than
changes on the tip-most head would be a sensible extension to making
named branches a first class citizen in Mercurial. Currently, named
branches feel like a late-coming unwanted step-child.

We have run it in a production environment for a while, with fewer
multiple heads occurring in our repositories as a result.

Also, it fixes the long-standing issue 736.

Dirkjan and Benoit have furthermore discussed the possibility of
changing the wire protocol to being JSON-based, but for simplicity's
sake, we have not considered this in our patch.

The latest version is available as push-namedbranches (guard
+namedbranch) from bitbucket at http://bitbucket.org/cyanite/hg-crew-mq/
and it applies to crew as of this moment. If you want a mailed, updated
patch instead, let us know and it will be forthcoming.

--
Kind regards,
 Sune Foldager and Henrik Stuart
Edlund A/S