Re: [Gnu-arch-users] pure-merge is impossible (was Re: Star merging with 3 branches)

[Tom Lord]

    > From: Andrew Suffield <address@hidden>

    > [Technically, pure-merge *is* a different tack. The whole pure
    > changeset thing is really the solution to this problem:

    > "If I want to construct all the permutations of a group of changesets
    > applied sequentially, how can I do this without consuming ridiculous
    > amounts of disk space?"

    > And the trick about splitting out conflicts is an offshoot of
    > that. 

I don't know if we're just talking past each other or not.   _That_
problem (the one in quotes) seems to me like:

        a) a really good problem to solve
        b) very tractable
        c) separate from the idea of making a `pure-merge' command
           that magically factors out a user's banal from important
           by-hand conflict resolutions
        d) not separate from the idea of making a (weaker but
           non-magic) `pure-merge' command that, yes, throws up its
           arms and gives up if it can't avoid conflicts but, also,
           works really hard to avoid conflicts

And, additionally, the problem you described (in quotes) is one that
Linus called out many months ago as something he'd really like.  The
idea being (and I suspect I'm not telling you anything you haven't
thought of here -- just trying to re-sync the discussion):
mr. gatekeeper gets a bunch of changes to merge, he passes them
through this ``explore the permutations'' tool, and he gets as output
a bunch of suggestions for paths through the changes that either avoid
or minimize conflicts and thus speed up the review/integration
process.  (And, in some cases, mr. gatekeeper can just be an automated
queue manager that seeks to maximize automatic merging throughput,
leaving "acceptence criteria" to some other stage in the process.)

Yes, it'd be sweet.  It seems straightforward but tedious for text
changes: just keep track of regions modified in various changesets and
the before & after file contents they expect.  Use that to partition
the changesets into several maximal sets of non-conflicting
changesets.  The before&after of overlapping regions in each set of
non-conflicting changesets gives you a partial order.  The set of
topological sorts of each set of non-conflicting changsets gives you
all the possible merge paths.  Add partial-order-relaxation fanciness
if you simply want to minimize rather than avoid conflicts.

As usual, it's also then necessary to think about how to extend that
for tree deltas.

Is that what you're talking about?  Yes, I'd agree that _that_ is
possible.   But the changeset factoring stuff you were displaying
(Rpre, Rmid, etc.) -- I don't think that that particular idea is
likely to add up to anything useful and (unsurprisingly) it doesn't
yield a magic (aka impossible) pure-merge command.


    > This question arose while sketching out some complicated patch
    > queue manager ideas. The idea is to precompute possible merges so we
    > can dispatch them in constant time on demand. Imagine an interface
    > that showed you the list of changesets that are pending for merge, and
    > could tell you which combinations work and which don't, all the way
    > down to the test suite results - I think it's actually computationally
    > feasible.

So do I.   The only obstacles I see are:

        a) someone needs to sit down and work out the algorithms
           to puzzle out tree-delta conflicts from changesets

        b) the core of the total set of merge-planning algorithms 
           could easilly wind up being ~10Kloc

        c) needs a nice interface and "context" (e.g., patch queue 
           manager) around that core

All solvable, of course.


    > Back to the subject at hand.]

    > > If we skip all of those when idempotently merging, then we have relied
    > > on the user who made R2 by resolving-by-hand conflicts in C1[R1] to
    > > have not made any other changes at the same time which _should_ be
    > > merged.

    > > In other words, the perfect pure merge command is supposed to spare
    > > users from having to make very disciplined by-hand resolutions -- but
    > > you proposal doesn't achieve that.

    > Not quite. It's supposed to shift the burden from the person applying
    > the changeset to the person committing the changeset. Obviously
    > *somebody* is going to have to put the boundaries in the right place,
    > or idempotent merges are impossible. The idea is to make it as
    > painless as possible.

I don't see how your proposal does any "burden shifting".   I still
see no need for the C2 and C3 changesets, especially since later
merges are going to just ignore them.


    > > In fact we might as well forget about C2, C3, R2pre, and R2mid
    > > entirely and just let the user commit R2 as the successor to R1 using
    > > an ordinary commit (perhaps adding a log header to assert "yes, I was
    > > really careful -- this is a pure merge").  Those intermediate
    > > revisions don't buy anything here at all.

    > What they buy you is simplicity in the rest of the code, more or
    > less. Assuming that conflicts are rare, this reduces them to a problem
    > that we can easily solve (and have already solved). There are plenty
    > of other approaches that will have the same effect - the point about
    > this one is that it's easy.

I just don't see how C2 and C3 simplify anything or reduce the problem
of dealing with conflicts.   You create these things and then never
use them for anything.   Why bother with them at all?


    > We're already pretty sure that no merge operator can handle every
    > possible case. The trick is to detect the cases you can't handle and
    > fail neatly, and pure-merge should be able to detect such problems
    > automatically.

Well, sure -- that'd be "weak pure-merge".   But I again don't see how
C2 and C3 bring even weak pure-merge any closer.


    > You still have the problem of "When I am doing a second-degree merge
    > =66rom two branches which have both merged the same changeset *and
    > resolved the conflicts differently*, what do I do?". Your example
    > appears to be a close variation on that problem.

    > My current answer is "stop and throw a conflict". I can't think of
    > anything that any merge operator could usefully do here; the nice
    > thing about pure merge is that it always knows when to stop, and it
    > can tell you precisely what is wrong.

Sure, weak pure-merge sometimes throws up its hands and says "can't be
done -- try some other technique".    Still don't see what C2 and C3
are for :-)

-t