Rejected merges

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Sorry for taking so long to respond to this.  Every time I read the
merge scenario, my stack overflowed.

David Allouche wrote:
> 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.

I don't like calling it "application of changesets", because it states a
particular mechanism for merging.

> The problem is the restoration of alice at 3.

I disagree that this is a problem.  You're treating "merge" as though it
should be "update".  Update is an operation that applies the changes
that have happened in OTHER since the last update, to THIS.

Merge simply tries to make THIS into a copy of OTHER, minus those
changes in THIS that OTHER is unaware of.  It does a fine job of that,
but it's not the right tool to use for diverged trees, because it tries
to turn them into nearly the same thing.

> 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}

You mean the same scenario, except that the patchlogs are retained, I think.

> 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.

In this scenario, I would pick bob at 4, since it is the last common merge.
  This would cause the textual changes introduced by alice at 3 to be
restored, which is what a merge tool is supposed to do.

> 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.

That's terrible.  What if alice at 3 were unacceptable for another reason?
 Then we'd have unmergeable trees.

BTW, this section doesn't seem to have shown a difference between
rejection and merge plus revsersal.

> 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.

Sure.

> [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.

I think calling three-way-merging 'delta-based' is either misleading, or
extrodiarily vague, depending on what you mean by 'delta'.  Three-way
merging does compare lines, but it's a three-way operation, not a
two-way operation.

> [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.

I disagree.  If OTHER lacks a patch that is present in BASE, that patch
should be removed from THIS.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCohmw0F+nu1YWqI0RAvpiAJ4wLrv3/AdiZUXQ9MVjrEj8mrhDRgCfbZ2t
QToS3qgjKPOhvrBkIDX7y6c=
=tW6K
-----END PGP SIGNATURE-----