Rejected merges

[David Allouche]

Now that merge is merged, we can start with the really fun stuff :)

As I was looking into the design notes for information about how to represent
merge history, I stumbled upon this bit in ./doc/merge.txt:

        ddaa says perhaps we should have three states: with respect to a branch
        any foreign revision can be *merged*, *not-merged*, or *rejected*. The
        difference between *not-merged* and *rejected* is that not-merged
        patches will try to merge in when you next sync from their branch,
        whereas rejected changes will not.

        'rejected' seems technically equivalent to it merged with the text
        changes not present.  But perhaps there should be something more?

Rejected is not technically equivalent to "merged with text changes not
present". Actually, I prefer to phrase the latter as "merged with additional
changes reversing the text changes".

The most important difference is that it sets additional constraints to
delta-based merge algorithms[0]. But rejection is also significant for
reporting.

Rejection is different from removal
===================================

Consider the following scenario:

     1. alice at 1: Alice has a tree.
     2. bob at 3: Bob branches from Alice and commits 2 revisions.
     3. alice at 2: Alice merges bob at 2-3.
     4. alice at 3: Alice does not want to integrate bob at 2, and reverses it.
     5. bob at 4: Bob merges alice at 2-3.
     6. bob at 5: Bob insists on keeping bob at 2 and reverses alice at 3.
     7. alice at 4: Alice does some new work.
     8. Bob wants to merge Alice.

Alice's merge history is:
        alice at 1
        alice at 2 +bob at 2 +bob at 3
        alice at 3 -bob at 2
        alice at 4

And patchset(alice at 4) [1] would be {alice at 1-4, bob at 3}

Bob's merge history is:
        alice at 1
        bob at 2
        bob at 3
        bob at 4 +alice at 2 +alice at 3
        bob at 5 -alice at 3

And patchset(bob at 5) would be {alice at 1-2, bob at 2-5}.

A delta-based merge algorithm would have to pick a merge BASE that is in
patchset(bob at 5) inter patchset(alice at 4) [2], that is {alice at 1-2, bob at 3}.

patchset(alice at 1) = {alice at 1}
patchset(alice at 2) = {alice at 1-2}
patchset(bob at 3) = {alice at 1, bob at 2-3}

Since the patchset of none of those revisions includes alice at 3, using any of
them as merge BASE when THIS=bob at 5 and OTHER=alice at 4 would restore alice at 3,
that is the reversal of the changes in bob at 2.

Such a merge would cause the redundant applications of some changesets (for
example alice at 4) but diff3 logic can often handle such situations gracefully
and perform the merge without causing any conflict.

The problem is the restoration of alice at 3. Considering rejection as removal
does not give enough information to delta-based merge operators to do any
better.

Rejection is different from merge plus reversal
===============================================

Consider the same scenario:
patchset(alice at 4) = {alice at 1-4, bob at 2-3}
patchset(bob at 5) = {alice at 1-3, bob at 2-5}

patchset(alice at 4) inter patchset(bob at 5) = {alice at 1-3, bob at 2-3}

According to our definitions so far, any of those revisions would be an
acceptable BASE for the merge, and the BASE-selection algorithm will try to
pick one that will not cause conflicts that cannot be resolved by the textual
merge operator.

However, we want to prevent redundant application of alice at 3 in Bob's branch.
There is not enough information in the model to offer best-effort in the
satisfaction of this constraint.

Let us extend the model to include rejects:
rejects(bob at 5) = alice at 3

The set of acceptable BASE is the subset of {patchset(THIS) inter
patchset(OTHER)} where the patchset includes rejects(THIS).

According to this definition, the only acceptable BASE is alice at 3.

Changeset states for reporting
==============================

Even outside of the context of delta-based merge algorithms, there is a value
in considering rejects as different from merged and not-merged revisions.

There are several use cases that involve reporting based on the mapping of a
branch to a set of revisions.

Bob wants to know what are the outstanding changes in Alice branch, he needs a
tool that will classify Alice revisions as pending and processed.

Charlie wants to integrate changes from Bob and Alice, he needs a tool that
will classify Alice revisions as present and not-present in Bob's tree.

With these two properties you can make a little table, relative to a given
branch, a revision could be:

      * Merged: that is present in all senses.

      * New: the semantic change associated to the revision is not present and
        will be reported to Bob.

      * Rejected: the semantic change associated to the revision is not
        present, but will not be reported to Bob.

      * No change may be reported as "new" to Bob, but not present to Charlie.


Implementation
==============

Each revision is associated to a patchset and a rejectset. The patchset of
branch at N always include branch at N.

A delta between two revisions can denote additions and removal of items to the
patchset and the rejectset.

There is no special case for the delta between a revision and its ancestor.
Unlike Arch, bzr records ancestry independently of the patchset, so removals
from the patchset do not affect the record of ancestry.

Footnotes
=========

[0] delta-based merge algorithms: All common merge algorithms are delta-based,
    in the sense that merge is performed by applying delta(BASE, OTHER) on THIS
    tree, or to put it in a different perspective, by computing diff3(THIS,
    OTHER, BASE), where THIS, OTHER and BASE are either working trees or
    revisions. The only exception I know of is Codeville merge, where BASE is
    generally not a working or revision and is never exhibited.

[1] patchset: I call "patchset" the set of all revisions that are accounted for
    in a tree, from the perspective of history-sensitive merge operators. I
    denote the patcheset of tree or revision X as "patchset(X)".

[2] BASE must be in patchset(THIS) inter patchset(OTHER): that is a corollary
    of what I call the "delta-based merge principle", a delta-based merge
    algorithm must produce a tree whose patchset is the union of the patchsets
    of THIS and OTHER.

-- 
                                                            -- ddaa
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20050515/8fde63c3/attachment.pgp