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

Re: Analysis of the 30 test cases (for tree conflicts)

From: Julian Foad <julianfoad_at_btopenworld.com>
Date: Mon, 21 Apr 2008 12:55:47 +0100

Nico Schellingerhout wrote:
> Stefan Sperling <stsp_at_elego.de> wrote on 04/20/2008 09:56:56 AM:
> > On Sun, Apr 20, 2008 at 01:32:17AM +0200, Nico Schellingerhout wrote:
> > > Hi tree-conflict-crew,
> > >
> > > Piet-Hein and I looked at the 30 test cases that Julian defined, and
> > > talking through it, we found cases missing, and we saw the number of
> > > cases blowing up even further. I therefore tried to come up with a
> > > simpler model (see analysis below).
> > >
> > > Tree conflict case analysis:
> > > ============================
> > >
> > > Let's start by enumerating all the cases:
> > >
> > > target \ source | mod add del rep
> > > ----------------+-----------------
> > > mod | M X C C
> > > add | X C X X
> > > del | C X C C
> > > rep | C X C C
> > >
> > > Legend:
> > > M = merge (=text merge for files, dir merge for dirs)
> > > X = can't happen


First, thank you for considering this.

Re. your observation that my test cases 9-16 are testing the same scenarios as
17-24 because we don't care whether a change is in the target branch or
uncommitted: Yes, I agree. It's easier to read the test suite if I combine
these. Done in r30729.

Your 9 distinct conflicts are all covered by my 4 primary scenarios, as I
combined "del" and "rep" together. However, your suggestion to save files in
the working copy in some cases is not yet covered by my tests. I'll address
that in a separate email.

> > Could you elaborate on the cases that can't happen?
> >
> > For example, it might well be that during a merge,
> > the source of the merge defines a delete on a file,
> > yet the target working copy has the same file locally
> > added.
> I'm not sure I understand that case: if the source deletes
> a file, the target must have the file as well, unless it
> has been deleted as well or is replaced by another file.
> I don't see how you could add a file if the file is
> already there.

Here are the big differences between update/switch and merge:

1. For update/switch, the source was identical to the target before the two
operations mentioned in the table; for "merge", a source item can be the same
as or similar to or completely different from the item at the same path in the
target. Differences can be due to changes in the target branch (or WC) and/or a
change in the source branch that occurred before the merge, if this is a
cherry-picked merge.

2. update/switch can tell whether the target item has the same object identity
as the source item, regardless whether its content is identical; merge can't.

Therefore we have to define the "merge" semantics differently: rather than
considering an "operation" that happened, we look at the "state" of the target
(relative to the source-left):

   - an item is there and identical
   - an item is there and differs (in content or properties)
   - an item of a different kind is there (file vs. directory)
   - an item is not there

So, for merge, the table should be:

target \ source | mod del rep
identical | mod del rep
different | M C C
diff-kind | C C C
not-there | C C C

target \ source | add
not-there | add
anything-there | C

(For "add" and "replace", a more sophisticated conflict resolver could take
into account what the target looks like compared with the source-right, i.e.
the to-be-added item, but just looking at source-left is enough for us at the

The four types of test I have currently defined for "merge" cover all of the
conflicts in this pair of tables:

   9 merge file: modify onto not-file
  10 merge file: del/rpl/mv onto not-same
  11 merge file: del/rpl/mv onto not-file
  12 merge file: add onto not-none

as follows:

target \ source | mod del rep
identical | - - -
different | - 10 10
diff-kind | 9 11 11
not-there | 9 11 11

target \ source | add
not-there | -
anything-there | 12

(similarly for test cases 13-16 for directories)

> In my table I tried to indicate "the full set of changes
> unique to the source/target branch", which includes possibly
> local modifications on a working copy. In other words, I
> considered the full history of the two branches, in which
> case I don't see how this can happen.
> > Same goes for replace/delete and the other way
> > around, where the merge wants to add a file to a path
> > which is scheduled for deletion in the working copy.
> Ok. If I understand you correctly, a use case could be:
> source:
> r1001 A foo.txt
> target:
> r1002 A foo.txt
> r1003 D foo.txt (or, perhaps just a local mod, not yet committed)
> after which the user tries to merge r1001 from source to target.
> Now the question is: is this a valid merge or is this a tree
> conflict? Naively, the fact that foo.txt has been deleted makes
> the path available for the add from the source again, so the merge
> is safe. However, If the merge had taken place after r1002, there
> would have been a tree conflict.
> Looking at the complete history on target, this would trigger a
> tree conflict because of the add in r1002, according to the table,
> and that would probably also be the safest approach.

I don't know about "safest". Anyway, this (looking through the history at what
changes have been made) isn't how the concept of "merge" behaves in Subversion,
and I don't know if it would ever make sense or be possible to behave like this.

As long as the above makes sense to you, I think we've now defined the
combinations that we need to detect.

- 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-04-22 07:51:17 CEST

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

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.