[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: Tree conflict detection in 'svn merge'

From: Julian Foad <julianfoad_at_btopenworld.com>
Date: Tue, 25 Mar 2008 17:38:05 +0000

Stefan Sperling wrote:
> On Wed, Mar 19, 2008 at 11:11:59PM +0000, Julian Foad wrote:
>>If we accept this principle that the basic algorithm should report all such
>>conflicts, then some of the complexities that have been mentioned
>>disappear. For example, looking at UC5 (rename onto a modified file), we
>>wondered about a modified version of this use case in which the
>>merge-source included not just a rename but a modification followed by a
>>rename. We wondered whether we should try to follow the history of
>>Merge-Left (Foo.c) forward in the source branch to find what it looked like
>>at the point it was finally deleted. This is unnecessary, as we have no
>>reason to want the merge to succeed if the target isn't similar to the
>>merge-left source.
> I can't recall this discussion properly, I'm afraid.
> What do you mean by "the target isn't similar to the merge-left source"?
> If you mean a text-comparison, how do you define "similar"?

When merging textual changes into a file, we already have a merge algorithm
that succeeds if the target file is "similar enough" to the merge-left source
that the merge algorithm can find matching hunks of text in it. (I'm not sure
of the details. I think it has to find the hunks in the correct order, and it
may require some "context" or "overlap" at the edge of each hunk being changed.
The details are not important right now.)

For merging tree changes, our new algorithm should succeed if the target tree
is "similar to" the merge-left source tree in the sense that each object that
we want to delete or modify is there in the expected place in the target, and
each object that we want to create is not already there. We are not yet sure
about the precise definition of these rules, but they will be something like
that. If the source-left and the target are not "similar enough" to meet these
conditions, then the merge should raise a tree conflict.

I define "similar" as both of these things: the text being similar enough for
the text-merge algorithm to succeed, and the tree being similar enough for the
tree-merge algorithm to succeed.

When we apply a modify-plus-delete onto an existing target file, my main point
was that we should not try to see if the textual modification has already been
done without our knowing it, and ignore that part if so; instead, we should
assume that the whole requested change is supposed to apply cleanly, and if it
doesn't then we should signal a conflict. Now, I don't know whether we would
want to compare the text in this case to determine whether we should allow the
deletion; that isn't the issue I was debating. I'm saying that if we do decide
to compare the text, it should be strictly the merge-left text that we examine,
and not some intermediate text that may have existed after merge-left and
before the deletion.

> Is the decrease in complexity you mention already covered in detection.txt,
> with or without your patch?

Yes, the current version of "detection.txt" doesn't say anything about needing
to follow ancestry for any of the use cases.

> I approve your version of the patch to detection.txt, by the way,
> and will commit it. Thanks for improving my wording in several places
> by an order of magnitude :)
>>I expect a similar simplification can be made for UC5, but I haven't done that yet.
> You must mean a different use case, because you talked about UC5
> above already :)

I meant that, now I have simplified the text on detecting UC4 and 6, I expect
we can simplify the text on detecting UC5 in a similar way. It looks like you
have already done so, which is fine.

- Julian

To unsubscribe, e-mail: dev-unsubscribe_at_subversion.tigris.org
For additional commands, e-mail: dev-help_at_subversion.tigris.org
Received on 2008-03-25 18:38:21 CET

This is an archived mail posted to the Subversion Dev mailing list.