Merge, undetected tree conflict when source tree moves directory

[Paolo Compieta <pa...@gmail.com>]

Hi,
this is a first post, hope it's well written and clear. I've found this
(candidate-)bug while at work, and it's a big problem for my company.
I'm posting this to ask if it's a known bug (i haven't found anything
similar in the issue tracker, hope i did the right searches) or if it's
some stupid practice we're using that impairs us from handling "svn
move on dirs" properly.

--- Details:

OS: Ubuntu 10.04, Windows Vista
Subversion: 1.6.16

Bug: while merging, svn doesn't detect a tree conflict when:
  source branch has "svn moved" (i.e. deleted) a folder
  destination branch has modified a file inside the same folder

Step to reproduce:
- trunk has folder A and file A/iota, branch is copied from this
- trunk moves (deletes) folder A, branch modifies A/iota
- branch merges from trunk

Actual behavior:
  svn doesn't rise any conflict or warning, discarding all
  modifications in the branch
Expected behavior:
  TREE CONFLICT: the directory being deleted in the branch
  has changed from the merge's initial revision (see "Use
  Case 5" and "Equality of directories" in
  http://svn.apache.org/repos/asf/subversion/trunk/notes/tree-conflicts/detection.txt)


Cheers,
Paolo Compieta

Re: Merge, undetected tree conflict when source tree moves directory

[Paolo Compieta <pa...@gmail.com>]

Attaching also the complete script for Win7.
(i already sent the template to the dev list)

Paolo

On Sat, Apr 30, 2011 at 6:36 PM, Paolo Compieta <pa...@gmail.com> wrote:
> Please find attached the repro-template(s) to reproduce the case in Ubuntu and Win7.
>
> Cheers,
> Paolo Compieta
>
>
> On Sat, Apr 30, 2011 at 6:29 PM, Paolo Compieta <pa...@gmail.com> wrote:
>> Hi,
>> this is a first post, hope it's well written and clear. I've found this
>> (candidate-)bug while at work, and it's a big problem for my company.
>> I'm posting this to ask if it's a known bug (i haven't found anything
>> similar in the issue tracker, hope i did the right searches) or if it's
>> some stupid practice we're using that impairs us from handling "svn
>> move on dirs" properly.
>>
>> --- Details:
>>
>> OS: Ubuntu 10.04, Windows Vista
>> Subversion: 1.6.16
>>
>> Bug: while merging, svn doesn't detect a tree conflict when:
>>  source branch has "svn moved" (i.e. deleted) a folder
>>  destination branch has modified a file inside the same folder
>>
>> Step to reproduce:
>> - trunk has folder A and file A/iota, branch is copied from this
>> - trunk moves (deletes) folder A, branch modifies A/iota
>> - branch merges from trunk
>>
>> Actual behavior:
>>  svn doesn't rise any conflict or warning, discarding all
>>  modifications in the branch
>> Expected behavior:
>>  TREE CONFLICT: the directory being deleted in the branch
>>  has changed from the merge's initial revision (see "Use
>>  Case 5" and "Equality of directories" in
>>  http://svn.apache.org/repos/asf/subversion/trunk/notes/tree-conflicts/detection.txt)
>>
>>
>> Cheers,
>> Paolo Compieta
>>
>
>

Re: Merge, undetected tree conflict when source tree moves directory

[Paolo Compieta <pa...@gmail.com>]

Please find attached the repro-template(s) to reproduce the case in
Ubuntu and Win7.

Cheers,
Paolo Compieta


On Sat, Apr 30, 2011 at 6:29 PM, Paolo Compieta <pa...@gmail.com> wrote:
> Hi,
> this is a first post, hope it's well written and clear. I've found this
> (candidate-)bug while at work, and it's a big problem for my company.
> I'm posting this to ask if it's a known bug (i haven't found anything
> similar in the issue tracker, hope i did the right searches) or if it's
> some stupid practice we're using that impairs us from handling "svn
> move on dirs" properly.
>
> --- Details:
>
> OS: Ubuntu 10.04, Windows Vista
> Subversion: 1.6.16
>
> Bug: while merging, svn doesn't detect a tree conflict when:
>  source branch has "svn moved" (i.e. deleted) a folder
>  destination branch has modified a file inside the same folder
>
> Step to reproduce:
> - trunk has folder A and file A/iota, branch is copied from this
> - trunk moves (deletes) folder A, branch modifies A/iota
> - branch merges from trunk
>
> Actual behavior:
>  svn doesn't rise any conflict or warning, discarding all
>  modifications in the branch
> Expected behavior:
>  TREE CONFLICT: the directory being deleted in the branch
>  has changed from the merge's initial revision (see "Use
>  Case 5" and "Equality of directories" in
>  http://svn.apache.org/repos/asf/subversion/trunk/notes/tree-conflicts/detection.txt)
>
>
> Cheers,
> Paolo Compieta
>

Re: Merge, undetected tree conflict when source tree moves directory

[Stefan Sperling <st...@elego.de>]

On Sun, May 15, 2011 at 07:01:55PM +0200, Paolo Compieta wrote:
> (perhaps we should move to the dev-list? i'm not expert of this, i'll follow
> the thread)

Feel free to start a new thread on the dev list if you have a design
proposal or a patch.

> Said that rename=deletion++, i'd concentrate only on the following 2:
> 
> 1.a) incoming delete vs local delete: i'd consider this a normal conflict:
> both trees could have moved that dir (that would look exactly the same
> before deletion): in this case, we should help to avoid duplicates.
> 
> 1.b) incoming delete vs local edit: could we try something simplier
> than a tree-compare? I imagine (but i haven't studied apis, yet) that
> "checking for commits in a working copy tree" be cheaper than
> tree-comparing with the repository tree; 99% of times local commits
> actually mean the "local edit" we were searching, don't they? (I can
> only see a false positive if a file or a dir is first modified and then
> restored exactly equals in the wc branch)
> 
> So we could check the following
>   "has any local edit (commit) happened in the destination tree since
>   last time they were OK?" (see below for "OK" definition)
>   NO) ok to delete
>   YES) tree conflict
> 
> OK: branch copy/creation; or last successfull merge (i.e. a commit in the
> destination/wc tree) in which they had been successfully integrated,
> even if different/modified.

Interesting ideas. But I think that comparing trees will be much more
straightforward than this. You would have to use the log APIs and also
evaluate mergeinfo. And as you've noted this gives you no information about
how the changes local to the branch actually affect the local version of
the tree. Which is valuable information when making decisions about conflicts.

Re: Merge, undetected tree conflict when source tree moves directory

[Paolo Compieta <pa...@gmail.com>]

(perhaps we should move to the dev-list? i'm not expert of this, i'll follow
the thread)

I've removed code references cause i'm asking a few more "conceptual"
questions here, to understand if we can simplify the detection avoiding the
diff. Fire me if i become trivial.

On Wed, May 4, 2011 at 12:03 PM, Stefan Sperling <st...@elego.de> wrote:
>
>
> To determine whether the deletion of a directory causes a tree conflict,
> we need to know whether the directory that has been deleted in the merge
> source had the same content as the corresponding deleted directory in
> the merge target. If it did, there is no conflict so it can be safely
> deleted. If it did not, a tree conflict needs to be flagged.
>
> The problems we were facing are as follows:
>
> 1) At present, it is impossible to tell apart a rename from a deletion.

You seem to be concerned mostly about reliably detecting the following
> situations:
>  incoming delete vs. local edit
>  incoming delete vs. local rename
>  incoming rename vs. local rename
>  incoming rename vs. local delete
> It helps to keep in mind that all of the following cases look the same
> to Subversion at the moment:
>  incoming delete vs. local rename
>  incoming rename vs. local delete
>  incoming rename vs. local rename
>  incoming delete vs. local delete
> The last case is not really a conflict but needs to be flagged as such
> because it looks the same as the former three possibilities.
> So you would still have to check each reported tree conflict for validity.
> This behaviour already applies for files in 1.6.x though, so it's a
> problem that isn't unique to directories. It is nevertheless annoying.
> But maybe less annoying than the current situation.
>

Said that rename=deletion++, i'd concentrate only on the following 2:

1.a) incoming delete vs local delete: i'd consider this a normal conflict:
both trees could have moved that dir (that would look exactly the same
before deletion): in this case, we should help to avoid duplicates.

1.b) incoming delete vs local edit: could we try something simplier
than a tree-compare? I imagine (but i haven't studied apis, yet) that
"checking for commits in a working copy tree" be cheaper than
tree-comparing with the repository tree; 99% of times local commits
actually mean the "local edit" we were searching, don't they? (I can
only see a false positive if a file or a dir is first modified and then
restored exactly equals in the wc branch)

So we could check the following
  "has any local edit (commit) happened in the destination tree since
  last time they were OK?" (see below for "OK" definition)
  NO) ok to delete
  YES) tree conflict

OK: branch copy/creation; or last successfull merge (i.e. a commit in the
destination/wc tree) in which they had been successfully integrated,
even if different/modified.

next days i'll start to have a look at the code; if there are no
good/feasible
ideas above, i also think tree compare is the clean solution.

2) Comparing a mixed-revision working copy to a tree in the repository
> (which is always at a single revision) can produce spurious differences.
> However, as of 1.7, merges into mixed-revision working copies are
> disallowed
> by default. So this problem is now less of a concern than it used to be.
>

ok to leave this out from the rest of the thread

3) Comparing a local tree to some tree in the repository usually implies
> quite a bit of network and server-side processing overhead. It will be
> quite noticeable in most environments. This comparison would need to be
> performed for every incoming deletion of a directory. It's already being
> done
> for files but comparing entire directory trees will in general take longer.
> Having some kind of optimisation in place for this purpose would be good.
> However, I'd favour correctness over performance.
>
> 4) We need the above comparison to be reliable. I don't remember the
> details, but I think we found problems with the diff implementation
> while trying to compare a working copy tree to a repository tree.
> These problems may have been due to corner-case bugs since this kind
> of operation is rarely tested in practice. But it might also have been
> due to the mixed-revision working copy problem, which we can now ignore.
> There is some research left to be done here.
>

I'm for reliability, too. I'd only (eventually) welcome some false positives
in favour of big optimization (waiting for the real rework in 1.8).

Re: Merge, undetected tree conflict when source tree moves directory

[Stefan Sperling <st...@elego.de>]

On Wed, May 04, 2011 at 01:32:02AM +0200, Paolo Compieta wrote:
> Thanks for the reply, your decision not to block the release makes sense.
> Also, i was thinking of a temporary workaround for marking directories in
> destination branches to inhibit their deletion.. but it seems there isn't
> any.

No, there isn't. You'll have to rely on manual audits right now.

> May i help somehow to make this land in 1.7.x? Writing tests or analyzing
> code for the solution? Do you have already a clear list of shortcomings to
> be fixed before starting to implement this kind of detection?

Sure, help is always welcome!

To determine whether the deletion of a directory causes a tree conflict,
we need to know whether the directory that has been deleted in the merge
source had the same content as the corresponding deleted directory in
the merge target. If it did, there is no conflict so it can be safely
deleted. If it did not, a tree conflict needs to be flagged.

The problems we were facing are as follows:

1) At present, it is impossible to tell apart a rename from a deletion.
You seem to be concerned mostly about reliably detecting the following
situations:
  incoming delete vs. local edit
  incoming delete vs. local rename
  incoming rename vs. local rename
  incoming rename vs. local delete
It helps to keep in mind that all of the following cases look the same
to Subversion at the moment:
  incoming delete vs. local rename
  incoming rename vs. local delete
  incoming rename vs. local rename
  incoming delete vs. local delete
The last case is not really a conflict but needs to be flagged as such
because it looks the same as the former three possibilities.
So you would still have to check each reported tree conflict for validity.
This behaviour already applies for files in 1.6.x though, so it's a
problem that isn't unique to directories. It is nevertheless annoying.
But maybe less annoying than the current situation.

2) Comparing a mixed-revision working copy to a tree in the repository
(which is always at a single revision) can produce spurious differences.
However, as of 1.7, merges into mixed-revision working copies are disallowed
by default. So this problem is now less of a concern than it used to be.

3) Comparing a local tree to some tree in the repository usually implies
quite a bit of network and server-side processing overhead. It will be
quite noticeable in most environments. This comparison would need to be
performed for every incoming deletion of a directory. It's already being done
for files but comparing entire directory trees will in general take longer.
Having some kind of optimisation in place for this purpose would be good.
However, I'd favour correctness over performance.

4) We need the above comparison to be reliable. I don't remember the
details, but I think we found problems with the diff implementation
while trying to compare a working copy tree to a repository tree.
These problems may have been due to corner-case bugs since this kind
of operation is rarely tested in practice. But it might also have been
due to the mixed-revision working copy problem, which we can now ignore.
There is some research left to be done here.


I think a good start would be trying to get the code to catch the
"incoming delete vs. local edit" situation by performing a comparison
with the corresponding tree in the repository at the merge-left revision,
using the existing diff APIs (see subversion/include/svn_diff.h).

The point to start off at is in subversion/libsvn_client/merge.c,
inside the merge_dir_deleted() function, at the following TODO comment
currently at line 2222:

/* An svn_wc_diff_callbacks4_t function. */
static svn_error_t *
merge_dir_deleted(svn_wc_notify_state_t *state,
                  svn_boolean_t *tree_conflicted,
                  const char *local_abspath,
                  void *baton,
                  apr_pool_t *scratch_pool)
{

[...]

    case svn_node_dir:
      {
        if (is_versioned && !is_deleted)
          {
            /* ### TODO: Before deleting, we should ensure that this dir
               tree is equal to the one we're being asked to delete.
               If not, mark this directory as a tree conflict victim,
               because this could be use case 5 as described in
               notes/tree-conflicts/detection.txt.
             */


There is code detecting various other tree conflict situations in that file.
See the function make_tree_conflict() and its callers for examples.

Re: Merge, undetected tree conflict when source tree moves directory

[Paolo Compieta <pa...@gmail.com>]

Thanks for the reply, your decision not to block the release makes sense.
Also, i was thinking of a temporary workaround for marking directories in
destination branches to inhibit their deletion.. but it seems there isn't
any.

May i help somehow to make this land in 1.7.x? Writing tests or analyzing
code for the solution? Do you have already a clear list of shortcomings to
be fixed before starting to implement this kind of detection?
On Sun, May 1, 2011 at 3:22 PM, Stefan Sperling <st...@elego.de> wrote:

> On Sun, May 01, 2011 at 01:13:14PM +0200, Paolo Compieta wrote:
> > On Sat, Apr 30, 2011 at 8:56 PM, Stefan Sperling <st...@elego.de> wrote:
> >
> > > This is a remaining task tracked in this issue:
> > > http://subversion.tigris.org/issues/show_bug.cgi?id=3150#desc4
> > >
> > > I would expect this feature to appear in the 1.8 or a later release.
> > >
> >
> >
> > +1 to put this in 1.7, or one more 1.6.x
> >
> > In my company, we've been talking about this incident for a day and a
> half,
> > and we'll be working for a few other days trying to recall all recent
> "svn
> > move on dirs" and double-check all of them to see if we've lost things:
> it's
> > really scaring to know that svn could have removed modified things
> without
> > saying anything. I'd classify this as blocker, cause it seriously impairs
> > merge operations for weeks, even after simple refactoring tasks (we have
> > many different branches and sub-branches, thus modifications take time to
> > spread and reach all branches).
>
> I know this seriously sucks and I would love to see it fixed, too.
> But it's not a simple problem to fix, unfortunately.
>
> We did what we could for 1.6.x with tree conflict detection but several
> problems remain that aren't feasible to fix quickly. We need to rewrite
> some parts of the software to get this to work. 1.7 will already bring
> us a step closer (all code managing working copies has been rewritten)
> but it's not quite there yet.
>
> It should not be considered a blocker because it is not a regression from
> a previous release. 1.7.x already has a vast amount of other improvements.
> Keeping those on hold because of this problem would not be a wise decision.
>
> For now, if you do refactoring, you should merge them ASAP to branches that
> you know will also need them. Subversion's current merge algorithm assumes
> that tree structures in the merge sources and target match up.
> It needs manual help if they don't.
>

Re: Merge, undetected tree conflict when source tree moves directory

[Stefan Sperling <st...@elego.de>]

On Sun, May 01, 2011 at 01:13:14PM +0200, Paolo Compieta wrote:
> On Sat, Apr 30, 2011 at 8:56 PM, Stefan Sperling <st...@elego.de> wrote:
> 
> > This is a remaining task tracked in this issue:
> > http://subversion.tigris.org/issues/show_bug.cgi?id=3150#desc4
> >
> > I would expect this feature to appear in the 1.8 or a later release.
> >
> 
> 
> +1 to put this in 1.7, or one more 1.6.x
> 
> In my company, we've been talking about this incident for a day and a half,
> and we'll be working for a few other days trying to recall all recent "svn
> move on dirs" and double-check all of them to see if we've lost things: it's
> really scaring to know that svn could have removed modified things without
> saying anything. I'd classify this as blocker, cause it seriously impairs
> merge operations for weeks, even after simple refactoring tasks (we have
> many different branches and sub-branches, thus modifications take time to
> spread and reach all branches).

I know this seriously sucks and I would love to see it fixed, too.
But it's not a simple problem to fix, unfortunately.

We did what we could for 1.6.x with tree conflict detection but several
problems remain that aren't feasible to fix quickly. We need to rewrite
some parts of the software to get this to work. 1.7 will already bring
us a step closer (all code managing working copies has been rewritten)
but it's not quite there yet.

It should not be considered a blocker because it is not a regression from
a previous release. 1.7.x already has a vast amount of other improvements.
Keeping those on hold because of this problem would not be a wise decision.

For now, if you do refactoring, you should merge them ASAP to branches that
you know will also need them. Subversion's current merge algorithm assumes
that tree structures in the merge sources and target match up.
It needs manual help if they don't.

Re: Merge, undetected tree conflict when source tree moves directory

[Paolo Compieta <pa...@gmail.com>]

On Sat, Apr 30, 2011 at 8:56 PM, Stefan Sperling <st...@elego.de> wrote:

> This is a remaining task tracked in this issue:
> http://subversion.tigris.org/issues/show_bug.cgi?id=3150#desc4
>
> I would expect this feature to appear in the 1.8 or a later release.
>


+1 to put this in 1.7, or one more 1.6.x

In my company, we've been talking about this incident for a day and a half,
and we'll be working for a few other days trying to recall all recent "svn
move on dirs" and double-check all of them to see if we've lost things: it's
really scaring to know that svn could have removed modified things without
saying anything. I'd classify this as blocker, cause it seriously impairs
merge operations for weeks, even after simple refactoring tasks (we have
many different branches and sub-branches, thus modifications take time to
spread and reach all branches).

Thanks
Paolo

Re: Merge, undetected tree conflict when source tree moves directory

[Stefan Sperling <st...@elego.de>]

On Sat, Apr 30, 2011 at 06:29:19PM +0200, Paolo Compieta wrote:
> Hi,
> this is a first post, hope it's well written and clear. I've found this
> (candidate-)bug while at work, and it's a big problem for my company.
> I'm posting this to ask if it's a known bug (i haven't found anything
> similar in the issue tracker, hope i did the right searches) or if it's
> some stupid practice we're using that impairs us from handling "svn
> move on dirs" properly.

This is a remaining task tracked in this issue:
http://subversion.tigris.org/issues/show_bug.cgi?id=3150#desc4

I would expect this feature to appear in the 1.8 or a later release.

> 
> --- Details:
> 
> OS: Ubuntu 10.04, Windows Vista
> Subversion: 1.6.16
> 
> Bug: while merging, svn doesn't detect a tree conflict when:
>   source branch has "svn moved" (i.e. deleted) a folder
>   destination branch has modified a file inside the same folder
> 
> Step to reproduce:
> - trunk has folder A and file A/iota, branch is copied from this
> - trunk moves (deletes) folder A, branch modifies A/iota
> - branch merges from trunk
> 
> Actual behavior:
>   svn doesn't rise any conflict or warning, discarding all
>   modifications in the branch
> Expected behavior:
>   TREE CONFLICT: the directory being deleted in the branch
>   has changed from the merge's initial revision (see "Use
>   Case 5" and "Equality of directories" in
>   http://svn.apache.org/repos/asf/subversion/trunk/notes/tree-conflicts/detection.txt)
> 
> 
> Cheers,
> Paolo Compieta