[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
|
RE: [stellation-res] Text merge test case: an analysis update
|
> >-----Original Message-----
> >From: stellation-res-admin@xxxxxxxxxxxxxxx
> >[mailto:stellation-res-admin@xxxxxxxxxxxxxxx]On Behalf Of Mark C.
> >Chu-Carroll
> >Sent: October 27, 2002 10:09 PM
> >To: stellation-res@xxxxxxxxxxxxxxx
> >Subject: RE: [stellation-res] Text merge test case: an analysis update
> >
> >
> >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
> >--
I think you will find that many programmers will have the folllowing
perspective when dealing with simultaneous sets of changes by two
developers. They will be unhappy with any algorithm that silently changes a
modification made by the other developer. Unfortunately, every SCM I have
seen does this all too often. In our shop we do not allow merges to happen
because the results simply cannot be relied on. Fortunately, we only have 7
developers so we can manage to keep from stepping on other peoples toes
pretty much, but I agree that this practice does not scale well. The bottom
line on this is that if we were to use Stellation in practice we would want
to be able to prevent the need for merging which would imply some kind of
artifact locking mechanism which is also undesirable. I think you may
underestimate just how sensitive an issue merging is. Most people I have
worked with are not prepared to tolerate a perceptable mis-merge rate.
That's been my experience but I would be happy if you can show me where I am
wrong.
Things that could go a long way to mitigate this would be support in
Eclipse/Stellation using a visual display to allow interactive trial merge
and correction of problem files. Even though I just ranted on, I do know
that the problem files and situations are rare and a good toolset, including
the ability to backup and re-merge using an interactive visual process would
shut up all my objections.
I do have some ideas on how to produce an algorithm that can do what I am
after and I am about 75% through an initial impplementation. Anything new
like this is going to require very thorough analysis before it can go into a
production version. I do not think that you should even consider this until
after we have the alpha release out the door.
Regards
Jonathan
Personal Email
jgossage@xxxxxxxx
Business Email
jonathan@xxxxxxxxxxxxxx
