RE: [stellation-res] Text merge test case: an analysis update

["Mark C. Chu-Carroll" <mcc@xxxxxxxxxxxxxx>]

On Sun, 2002-10-27 at 13:30, Jonathan Gossage wrote:
> > >
> > >I've done a detailed analysis of test16, and concluded
> > >that it's doing the right thing, but the predicted results
> > >in the test file are wrong. Here's what the test
> > >file has for 16:
> > >
> > >:test16
> > ># Tests for conflicts in first and last lines
> > ># Base sequence     Delta Sequence    Target Sequence   Expected
> > >Sequence
> > >  abc               xyz               abc               abc
> > >  abc               abc               abc               abc
> > >  abc               abc               abc               abc
> > >  xyz               abc               abc               abc
> > >  abc               abc               abc               abc
> > >  abc               abc               abc               abc
> > >  abc               abc               xyz               xyz
> > >
> > >To the stellation merge algorithm, what's going on here is:
> > >both delta and target deleted the xyz in the fourth line of
> > >base; delta inserted xyz in the first position, and target
> > >inserted xyz in the last. The correct result is thus:
> > >xyz
> > >abc
> > >abc
> > >abc
> > >abc
> > >abc
> > >xyz
> > >
> > >This is what my current code generates. So test 16 works
> > >in the version of the system that I'm running.
> 
> I agree that this is the correct output from the algorithm. However the
> intent here was almost certainly to move xyz from one place to another
> rather than to create two copies of it. With this perspective, a move
> conflict would be a more appropriate response.

I've got two responses here...

First: I always hesitate about believing that I can infer
someones intentions. I've had some very bad experiences
on a previous project where we tried to do things like that,
and our experiences were almost universally awful. No one
liked *any* of our inferences. Our user community (admittedly
a small, and not particularly typical group of hackers)
strongly preferred a comprehensible algorithm that they
could predict, rather than having the system try to 
predict them. What we're doing here is looking at two
parallel sets of changes, made by two different people,
and trying to guess what those two people meant by this
change, to infer that they conflict because it looks like
they each moved the same thing to different places.

Second: I don't know of any algorithm that can run in a 
reasonable time that can discover things like this. What
we would need to be able to detect this is something that
goes through and compares what the current algorithm detects
and inserts and deletions, and then tries to infer from
that whether a given delete/insert pair was probably
intended to be a move; and then further, to detect pairs
of inferred moves, connect them up, and recognize them
as a potential conflict.

If you can come up with an algorithm that can do this 
without dramatically impacting the performance of merge,
I will happily support including it as an option, and
see how it works. (That phrasing may sound snide, but it isn't intended
that way at all. I'm very serious here. I'd
like to see a good algorithm for doing that, and I'd really
like to see how well it works in practice. So I really would
be delighted if you can figure out how to do it.)

	-Mark
-- 
Mark Craig Chu-Carroll,  IBM T.J. Watson Research Center  
*** The Stellation project: Advanced SCM for Collaboration
***		http://www.eclipse.org/stellation
*** Work Email: mcc@xxxxxxxxxxxxxx  ------- Personal Email: markcc@xxxxxxxxxxx