You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Stephen Butler <sb...@elego.de> on 2008/02/14 15:09:52 UTC

Tree conflict detection in 'svn merge'

Hello tree-conflict fans,

The first phase of tree conflict detection is available in the tree-
conflicts feature branch.  See this post for a recap of the current
functionality implemented by this branch:

   http://svn.haxx.se/dev/archive-2008-01/0296.shtml

In extending the current tree-conflict-detection scheme to cover
'svn merge', we want to avoid presenting the user a lot of apparent
tree conflicts that involve files with no common ancestry.  To weed
out these false positives, we have to query the repository.  Our
current plan is described below, arranged according to use case.
The use cases are described in the recap email above and in
notes/tree-conflicts/use-cases.txt.

We would be grateful for any feedback.

Thanks,
Steve


==========
USE CASE 4
==========

A file modified in the merge diff does not exist at the current URL.
If a file at the current URL has been deleted in the parent dir's
history, then we might have a tree conflict.

A tree conflict exists if all of the following predicates are true:

1. The merge operation is compatible with tree conflict detection:
    We check specific fields of the merge-command baton (of type
    merge_cmd_baton_t).  If all of the following boolean fields have
    the given values, we might have a tree conflict.

    a. (same_repos == TRUE)  Both of the source URLs, merge-left and
        merge-right, must be in the same repository.

    b. (sources_ancestral == TRUE)  The merge-left URL given to the
        merge command must be an ancestor of the merge-right URL.

    c. (ignore_ancestry == FALSE)  The rest of the predicates below
        depend on ancestry queries, so if the user wants to ignore
        ancestry there's not much point in looking for tree conflicts.

    d. (record_only == FALSE)  A record-only merge operation updates
        mergeinfo without touching files.

2. The file at merge-left is an ancestor of the file at merge-right:
    We call svn_client__get_youngest_common_ancestor().  If the YCA
    is the merge-left file, we might have a tree conflict.  Note that
    this is a more specific query than #1b above.

3. In the history of the current directory, a file by this name has
    been deleted:  In the repository, we will call the function
    svn_repos_deleted_rev(), passing a "start" revision in which the
    file existed and receiving a "deleted" revision in which the file
    was deleted.  But first we have to choose a valid "start" revision,
    which is a bit tricky since we don't yet know whether the file
    ever existed in the current directory.

    a. The parent dir and the corresponding dir at merge-left have
       a common ancestor:  We pass the two directories to
       svn_client__get_youngest_common_ancestor().  If a common
       ancestor exists, we might have a tree conflict.

    b. The file existed in the parent dir's common-ancestor revision:
       If svn_ra_check_path() says that a file by that name existed
       in the parent dir at the common-ancestor revision, we might
       have a tree conflict.

    c. The file has been deleted in the parent dir between the
       common-ancestor revision and the working copy's base revision:
       We call svn_ra_get_deleted_revnum(), passing it the common-
       ancestor revision as the "start" revision and the base revision
       as the "end" revision.  Note that this function does not yet
       exist in the remote-access layers.  We'll have to implement it.

4. The file at merge-left and the file deleted in the parent-dir's
    history have a common ancestor:  We pass the merge-left file and
    the "last surviving revision" of the file, derived from #3c above,
    to svn_client__get_youngest_common_ancestor().  If they have a
    common ancestor, we have a tree conflict (finally!).


==========
USE CASE 5
==========

An existing file is deleted by the merge diff.  We don't want to lose
any text changes that are unique to the file at the current URL.

A tree conflict exists if all of the following predicates are true:

1. The merge operation is compatible with tree conflict detection.
    Same as #1 in use case 4.

2. The current file and the file at merge-left have a common
    ancestor:  We can call svn_client__get_youngest_common_ancestor().
    If the ancestor exists, we might have a tree conflict.

3. The text of the current file does not match the text of the
    "last surviving revision" of the file after merge-left:  The last
    survivor is found by passing svn_ra_get_deleted_revnum() the
    merge-left revision as "start" and the merge-right revision as
    "end".  Thankfully, this is simpler than #3 in use case 4.  I
    think we can call svn_client_diff_summarize2() to compare the
    files.  If there is a text difference, we have a tree conflict.


==========
USE CASE 6
==========

A file deleted by the merge diff does not exist at the current URL.
If a file at the current URL has been deleted in the parent dir's
history, then we might have a tree conflict.

A tree conflict exists if all of the following predicates are true:

1. The merge operation is compatible with tree conflict detection.
    Same as #1 in use case 4.

2. In the history of the parent directory, a file by this name has
    been deleted.  Same as #3 in use case 4.

3. The file at merge-left and the file deleted in the parent-dir's
    history have a common ancestor.  Same as #4 in use case 4.

It would be nice to skip the tree conflict if the double-delete is
caused by two rename operations that have the same destination.
But we have to mark this as a tree conflict due to the current lack
of "true rename" support.  See notes/tree-conflicts/detection.txt
for more on this topic.

-- 
Stephen Butler | Software Developer
elego Software Solutions GmbH
Gustav-Meyer-Allee 25 | 13355 Berlin | Germany
fon: +49 30 2345 8696 | mobile: +49 163 25 45 015
fax: +49 30 2345 8695 | http://www.elegosoft.com
Geschäftsführer: Olaf Wagner | Sitz der Gesellschaft: Berlin
Amtsgericht Charlottenburg HRB 77719 | USt-IdNr: DE163214194



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org


Re: Subversion on a large repository

Posted by Blair Zajac <bl...@orcaware.com>.
On Feb 14, 2008, at 9:38 AM, Vishnu Venkatesan wrote:

> Hi,
> I am in the process of evaluating subversion for hosting a  
> repository of about 10,000+ files with a size of 2 GB that can  
> change at least 10% everyday.
> Can anyone please let me know if there are any references of  
> subversion deployment with such large repository with FSFS or  
> Berkeley DB.
> Some of the things that I am looking for
> 1. What would be the advantages of using one over the other (FSFS vs  
> Berkeley DB)
> 2. Any specific limitations
> 3. How much scalable the repository would be -- for about 100-200  
> concurrent commits

Look at the KDE and Apache repositories for large public repositories:

http://websvn.kde.org/
http://svn.apache.org/repos/asf/

I recommend using fsfs.  Check the svn book for the differences  
between fsfs and BDB.

When you say concurrent, you truly mean concurrently?  As in 100-200  
commits per second?

Regards,
Blair

-- 
Blair Zajac, Ph.D.
CTO, OrcaWare Technologies
<bl...@orcaware.com>
Subversion training, consulting and support
http://www.orcaware.com/svn/



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Subversion on a large repository

Posted by Blair Zajac <bl...@orcaware.com>.
On Feb 14, 2008, at 9:38 AM, Vishnu Venkatesan wrote:

> Hi,
> I am in the process of evaluating subversion for hosting a  
> repository of about 10,000+ files with a size of 2 GB that can  
> change at least 10% everyday.
> Can anyone please let me know if there are any references of  
> subversion deployment with such large repository with FSFS or  
> Berkeley DB.
> Some of the things that I am looking for
> 1. What would be the advantages of using one over the other (FSFS vs  
> Berkeley DB)
> 2. Any specific limitations
> 3. How much scalable the repository would be -- for about 100-200  
> concurrent commits

Look at the KDE and Apache repositories for large public repositories:

http://websvn.kde.org/
http://svn.apache.org/repos/asf/

I recommend using fsfs.  Check the svn book for the differences  
between fsfs and BDB.

When you say concurrent, you truly mean concurrently?  As in 100-200  
commits per second?

Regards,
Blair

-- 
Blair Zajac, Ph.D.
CTO, OrcaWare Technologies
<bl...@orcaware.com>
Subversion training, consulting and support
http://www.orcaware.com/svn/



---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org

Re: Subversion on a large repository

Posted by Arfrever Frehtes Taifersar Arahesis <ar...@gmail.com>.
2008-02-14 18:37:55 Vishnu Venkatesan napisał(a):
> Hi,
>   I am in the process of evaluating subversion for hosting a repository 
> of about 10,000+ files with a size of 2 GB that can change at least 10% 
> everyday.
>   Can anyone please let me know if there are any references of 
> subversion deployment with such large repository with FSFS or Berkeley DB.
> Some of the things that I am looking for
> 1. What would be the advantages of using one over the other (FSFS vs 
> Berkeley DB)
> 2. Any specific limitations
> 3. How much scalable the repository would be -- for about 100-200 
> concurrent commits

Don't create new threads by replying to other threads!
This question should be asked only on the users@subversion.tigris.org mailing list.

Read:
http://svnbook.red-bean.com/nightly/en/svn.reposadmin.planning.html#svn.reposadmin.basics.backends


-- 
Arfrever Frehtes Taifersar Arahesis

Re: Subversion on a large repository

Posted by Arfrever Frehtes Taifersar Arahesis <ar...@gmail.com>.
2008-02-14 18:37:55 Vishnu Venkatesan napisał(a):
> Hi,
>   I am in the process of evaluating subversion for hosting a repository 
> of about 10,000+ files with a size of 2 GB that can change at least 10% 
> everyday.
>   Can anyone please let me know if there are any references of 
> subversion deployment with such large repository with FSFS or Berkeley DB.
> Some of the things that I am looking for
> 1. What would be the advantages of using one over the other (FSFS vs 
> Berkeley DB)
> 2. Any specific limitations
> 3. How much scalable the repository would be -- for about 100-200 
> concurrent commits

Don't create new threads by replying to other threads!
This question should be asked only on the users@subversion.tigris.org mailing list.

Read:
http://svnbook.red-bean.com/nightly/en/svn.reposadmin.planning.html#svn.reposadmin.basics.backends


-- 
Arfrever Frehtes Taifersar Arahesis

Subversion on a large repository

Posted by Vishnu Venkatesan <vi...@oracle.com>.
Hi,
  I am in the process of evaluating subversion for hosting a repository 
of about 10,000+ files with a size of 2 GB that can change at least 10% 
everyday.
  Can anyone please let me know if there are any references of 
subversion deployment with such large repository with FSFS or Berkeley DB.
Some of the things that I am looking for
1. What would be the advantages of using one over the other (FSFS vs 
Berkeley DB)
2. Any specific limitations
3. How much scalable the repository would be -- for about 100-200 
concurrent commits

thanks,
Vishnu.

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org

Re: Tree conflict detection in 'svn merge'

Posted by Julian Foad <ju...@btopenworld.com>.
Stephen Butler wrote:
> Hello tree-conflict fans,
> 
> The first phase of tree conflict detection is available in the tree-
> conflicts feature branch.  See this post for a recap of the current
> functionality implemented by this branch:
> 
>   http://svn.haxx.se/dev/archive-2008-01/0296.shtml
> 
> In extending the current tree-conflict-detection scheme to cover
> 'svn merge', we want to avoid presenting the user a lot of apparent
> tree conflicts that involve files with no common ancestry.  To weed
> out these false positives, we have to query the repository. 

Could you elaborate on these "apparent tree conflicts"? I don't know if it's 
important but I just can't see what you mean by that.

> Our current plan is described below, arranged according to use case.
> The use cases are described in the recap email above and in
> notes/tree-conflicts/use-cases.txt.
> 
> We would be grateful for any feedback.

OK, I'm commenting below.

My understanding of merging is very weak so I might have got some things 
completely wrong.


> Thanks,
> Steve
> 
> 
> ==========
> USE CASE 4
> ==========
> 
> A file modified in the merge diff does not exist at the current URL.
> If a file at the current URL has been deleted in the parent dir's
> history, then we might have a tree conflict.
> 
> A tree conflict exists if all of the following predicates are true:
> 
> 1. The merge operation is compatible with tree conflict detection:
>    We check specific fields of the merge-command baton (of type
>    merge_cmd_baton_t).  If all of the following boolean fields have
>    the given values, we might have a tree conflict.
> 
>    a. (same_repos == TRUE)  Both of the source URLs, merge-left and
>        merge-right, must be in the same repository.

That's probably right but I don't understand it.

Firstly, the doc string for this field talks about "source" and "target" being 
in the same repository. Is this what you mean by "source URLs, merge-left and 
merge-right"? I'm not clear on the terminology.

I'm intrigued as to why this condition is considered at all. I wouldn't expect 
this to work in any cross-repository scenario, but that's because I thought we 
didn't support any cross-repository merging. If we can do a cross-repository 
merge, why can't we detect tree conflicts in it?

I don't think you necessarily need to answer this now, but I would like to 
understand it one day when I start thinking about merging.

(More confusion: the doc string for this field talks about a "default" which 
doesn't seem to exist. Is that simply an error?)


>    b. (sources_ancestral == TRUE)  The merge-left URL given to the
>        merge command must be an ancestor of the merge-right URL.

OK.

>    c. (ignore_ancestry == FALSE)  The rest of the predicates below
>        depend on ancestry queries, so if the user wants to ignore
>        ancestry there's not much point in looking for tree conflicts.

That doesn't seem right. Doesn't "ignore ancestry" just mean that files should 
be matched based on their path rather than on their object-identity (following 
renames and copies)? If I merge a modification of a source file named "foo" 
onto a destination in which a file named "foo" does not exist, I would still 
like to be informed that there is a conflict. Any other behaviour would be 
wrong, I think.

So I think there is a separate type of detection needed when ignoring ancestry.

>    d. (record_only == FALSE)  A record-only merge operation updates
>        mergeinfo without touching files.

That doesn't seem right. I think the merge info to be recorded depends on how 
conflicts are resolved. Therefore conflicts must be detected so that the user 
can specify how to resolve them. If interactive conflict resolution is not 
possible, at least the user can run the command again specifying the 
appropriate resolution in advance.

> 2. The file at merge-left is an ancestor of the file at merge-right:
>    We call svn_client__get_youngest_common_ancestor().  If the YCA
>    is the merge-left file, we might have a tree conflict.  Note that
>    this is a more specific query than #1b above.

OK. (Of course this condition doesn't apply in the ignore-ancestry cases.)


I'm going to post this now, before attempting to understand the rest, because I 
may already have made some wrong assumptions!

- Julian


> 3. In the history of the current directory, a file by this name has
>    been deleted:  In the repository, we will call the function
>    svn_repos_deleted_rev(), passing a "start" revision in which the
>    file existed and receiving a "deleted" revision in which the file
>    was deleted.  But first we have to choose a valid "start" revision,
>    which is a bit tricky since we don't yet know whether the file
>    ever existed in the current directory.
> 
>    a. The parent dir and the corresponding dir at merge-left have
>       a common ancestor:  We pass the two directories to
>       svn_client__get_youngest_common_ancestor().  If a common
>       ancestor exists, we might have a tree conflict.
> 
>    b. The file existed in the parent dir's common-ancestor revision:
>       If svn_ra_check_path() says that a file by that name existed
>       in the parent dir at the common-ancestor revision, we might
>       have a tree conflict.
> 
>    c. The file has been deleted in the parent dir between the
>       common-ancestor revision and the working copy's base revision:
>       We call svn_ra_get_deleted_revnum(), passing it the common-
>       ancestor revision as the "start" revision and the base revision
>       as the "end" revision.  Note that this function does not yet
>       exist in the remote-access layers.  We'll have to implement it.
> 
> 4. The file at merge-left and the file deleted in the parent-dir's
>    history have a common ancestor:  We pass the merge-left file and
>    the "last surviving revision" of the file, derived from #3c above,
>    to svn_client__get_youngest_common_ancestor().  If they have a
>    common ancestor, we have a tree conflict (finally!).
> 
> 
> ==========
> USE CASE 5
> ==========
> 
> An existing file is deleted by the merge diff.  We don't want to lose
> any text changes that are unique to the file at the current URL.
> 
> A tree conflict exists if all of the following predicates are true:
> 
> 1. The merge operation is compatible with tree conflict detection.
>    Same as #1 in use case 4.
> 
> 2. The current file and the file at merge-left have a common
>    ancestor:  We can call svn_client__get_youngest_common_ancestor().
>    If the ancestor exists, we might have a tree conflict.
> 
> 3. The text of the current file does not match the text of the
>    "last surviving revision" of the file after merge-left:  The last
>    survivor is found by passing svn_ra_get_deleted_revnum() the
>    merge-left revision as "start" and the merge-right revision as
>    "end".  Thankfully, this is simpler than #3 in use case 4.  I
>    think we can call svn_client_diff_summarize2() to compare the
>    files.  If there is a text difference, we have a tree conflict.
> 
> 
> ==========
> USE CASE 6
> ==========
> 
> A file deleted by the merge diff does not exist at the current URL.
> If a file at the current URL has been deleted in the parent dir's
> history, then we might have a tree conflict.
> 
> A tree conflict exists if all of the following predicates are true:
> 
> 1. The merge operation is compatible with tree conflict detection.
>    Same as #1 in use case 4.
> 
> 2. In the history of the parent directory, a file by this name has
>    been deleted.  Same as #3 in use case 4.
> 
> 3. The file at merge-left and the file deleted in the parent-dir's
>    history have a common ancestor.  Same as #4 in use case 4.
> 
> It would be nice to skip the tree conflict if the double-delete is
> caused by two rename operations that have the same destination.
> But we have to mark this as a tree conflict due to the current lack
> of "true rename" support.  See notes/tree-conflicts/detection.txt
> for more on this topic.
> 


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Tree conflict detection in 'svn merge'

Posted by Julian Foad <ju...@btopenworld.com>.
Stefan Sperling wrote:
[...]
> Steve and I have managed to implement detection as described in detection.txt
> for use cases 4, 5, and 6 over easter, if you haven't noticed yet :)

Yay! I'll start running actual scenarios on it instead of just talking 
theoretically about what should happen.

[...]
> I think we should start filing issues in the svn.tigris.org issue
> tracker for the branch now, both to document the progress more
> transparently and to keep track of what still needs doing on
> the branch.
[...]

OK.

- Julian

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Tree conflict detection in 'svn merge'

Posted by Stefan Sperling <st...@elego.de>.
On Tue, Mar 25, 2008 at 05:38:05PM +0000, Julian Foad wrote:
>> 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.)

OK, I understand that now, thanks. I wasn't aware that there is
already functionality like that. I assumed you were talking about
something that we'd need to implement from scratch.

> 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.

Steve and I have managed to implement detection as described in detection.txt
for use cases 4, 5, and 6 over easter, if you haven't noticed yet :)

Check the latest commits to the branch. The implementation is pretty
much to the letter for all use cases, i.e. the basic stuff is done.
I mean to say there is no special-casing [yet].

Steve still had patches from back when he started working on the merge
use cases that turned out to be just about what we wanted. So we got
this done pretty quickly.

Use case 5 detection currently compares text, via svn_diff_file_diff_2 and
svn_diff_contains_diffs. If that needs to be tweaked, I won't object in
any way.

I think we should start filing issues in the svn.tigris.org issue
tracker for the branch now, both to document the progress more
transparently and to keep track of what still needs doing on
the branch.

Karl suggested putting the branch URL into the URL field of the
issues concerning the tree-conflicts branch. This way we can key
the issues by that field (URL contains "tree-conflicts") to tell
them apart from all the others.

I plan to start filing some issues tomorrow, mainly for the failing tests,
and also for some UI issues I'd like to address.

If you have anything you want to file an issue for (e.g. modify+delete?),
please do so.

Stephen Butler is now a partial committer for the tree-conflicts branch,
so you, him, and I can all commit to it. This should help the work flow :)

>> 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'm glad to hear once again that we really don't need to bother with
ancestry :) :) :)

(I rarely hand out three smilies at once -- I really mean it!)

-- 
Stefan Sperling <st...@elego.de>                 Software Developer
elego Software Solutions GmbH                            HRB 77719
Gustav-Meyer-Allee 25, Gebaeude 12        Tel:  +49 30 23 45 86 96 
13355 Berlin                              Fax:  +49 30 23 45 86 95
http://www.elego.de                 Geschaeftsfuehrer: Olaf Wagner

Re: Tree conflict detection in 'svn merge'

Posted by Julian Foad <ju...@btopenworld.com>.
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@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Tree conflict detection in 'svn merge'

Posted by Stefan Sperling <st...@elego.de>.
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"?

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

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 :)

-- 
Stefan Sperling <st...@elego.de>                 Software Developer
elego Software Solutions GmbH                            HRB 77719
Gustav-Meyer-Allee 25, Gebaeude 12        Tel:  +49 30 23 45 86 96 
13355 Berlin                              Fax:  +49 30 23 45 86 95
http://www.elego.de                 Geschaeftsfuehrer: Olaf Wagner

Re: Tree conflict detection in 'svn merge'

Posted by Julian Foad <ju...@btopenworld.com>.
Hi Stefan.

I have read your changes for UC 4 and 6, and I have modified these sections. 
Please have a look at my attached patch and see if that is better. One thing I 
have done is separated the notes about how users would like to resolve these 
cases from the main text about how we detect a conflict.

First, though, let me explain why I think it is right to always flag a conflict 
in those situations.

When a user asks Subversion to apply a diff (Source-Left -> Source-Right) onto 
a target, either the user expects Subversion to choose and apply only those 
source changes that have not already been merged, using the merge tracking 
feature, or the user has selected the exact source diffs that should be applied 
to the target.

In either case, the libsvn_client merge code expects that it is applying 
changes that have not already been applied to the target branch. When it 
encounters a change that it cannot apply, the fundamentally correct response is 
for it to flag a conflict. If it is deleting a file that has already been 
deleted in the target branch, or renaming a file that has already been renamed 
to the same new name, or modifying a line of text where the same text 
modification has already been made, then these are all strictly conflicts, but 
clearly some users will prefer Subversion to automatically resolve these 
conflicts in the "obvious" way.

Our text-merge algorithm has always auto-resolved two identical modifications 
by silently ignoring one of them, because it is often what users expect, and 
and will continue to do so, but it is easy to show examples where this is the 
wrong result.

The general solution is to use a basic algorithm that detects all such cases as 
potential conflicts and reports them to a higher-level customisable conflict 
handler that can automatically resolve certain cases according to the user's 
preferences. Only the cases that are not resolved would get reported to the 
user as persistent conflicts that need further attention.

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 hope this makes sense.

I expect a similar simplification can be made for UC5, but I haven't done that yet.

- Julian


Stefan Sperling wrote:
> Index: notes/tree-conflicts/detection.txt
> ===================================================================
> --- notes/tree-conflicts/detection.txt	(revision 29943)
> +++ notes/tree-conflicts/detection.txt	(working copy)
[...]
> +target working copy, then the target file is a tree conflict victim.
> +The rationale behind this is that the source diff doesn't cover as
> +many revisions as it should. The file should either be brought in by
> +adding the revision that created the file to the list of revisions
> +to be merged, or changes made to it on the source branch should be
> +omitted from the merge range entirely.
> +
> +We will need to store tree-conflict information in entries about files
> +that may not actually be present in the working copy at all.
> +
> +If a modification to the nonexistent file is part of a larger diff
> +with changes to other files that should be merged, the user will
> +need to be able to manually resolve the tree-conflict while keeping
> +the desired changes.
> +
> +Users must be able to run a second merge command to resolve the
> +tree-conflict, or repeat a previous merge operation, but with
> +additional revisions, without harm.
> +
> +However, the current plan is to disallow merges into tree-conflicted
> +directories. This means that users will first have to mark the
> +tree-conflict around the missing victim as resolved before attempting
> +to merge the file again, this time including the revision that created
> +the file. This may be a bit of an awkward work flow but is required to
> +solve the problem this use case has in the current implementation,
> +namely that missing files may accidentally be overlooked during merging.
>  
>  ==========
>  USE CASE 5
> @@ -211,57 +126,85 @@ victim if its text is different from the
>  source.  We don't want to forget any text changes that are unique to
>  the file at the current URL.
>  
> +To allow uncommitted text modifications in the working copy, we should
> +do any text comparisons against the WORKING revision.
> +
>  A tree conflict exists if all of the following predicates are true:
>  
> -1. The merge operation is compatible with tree conflict detection.
> -   Same as #1 in use case 4.
> +1. We check specific fields of the merge-command baton (of type
> +   merge_cmd_baton_t). If all of the following boolean fields have
> +   the given values, we might have a tree conflict.
> +
> +    a. (same_repos == TRUE) Both of the source URLs, merge-left and
> +        merge-right, must be in the same repository. This is also
> +        a requirement of the current merge-tracking implementation.
> +
> +        Julian Foad said this requirement might be too strict in
> +        case Subversion ever grows support for merging between
> +        different repositories:
> +
> +        "I agree that the source and target must be in the same
> +        repository (unless ancestry is being ignored), but only because
> +        we currently have no way to trace the ancestry across repositories.
> +        I don't see why this same_repos condition flag exists or should
> +        be considered independently from asking whether we can find a
> +        common ancestor."
> +        http://svn.haxx.se/dev/archive-2008-02/0611.shtml
> +
> +    b. (sources_ancestral == TRUE) The merge-left URL given to the
> +        merge command must be an ancestor of the merge-right URL.
> +
> +    c. (ignore_ancestry == FALSE) The rest of the predicates below
> +        depend on ancestry queries, so if the user wants to ignore
> +        ancestry there's not much point in looking for tree conflicts.
> +
> +    d. (record_only == FALSE) A record-only merge operation updates
> +        mergeinfo without touching files. 
>  
>  2. The target file and the source-left file have a common ancestor.
>  
> +   Rationale:
> +   
> +   Otherwise the files are not related, so differences between
> +   them cannot be due to separate lines of history with conflicting
> +   tree-related changes.
> +
>     Implementation:
>  
>     Call svn_client__get_youngest_common_ancestor().  If the ancestor
>     exists, the predicate is TRUE.
>  
> -   Rationale:
> -
> -   Thankfully, the job here is a lot simpler than in use case 4,
> -   because we don't have to search the history to find a possible
> -   target file to serve as the tree conflict victim.
> -
>  3. The text of the target file does not match the text of the
>     "last surviving revision" of the file after merge-left.
>  
> +   Rationale:
> +
> +   We don't want to flag every file deletion as a tree conflict.  We
> +   want to warn the user if the file to be deleted locally is
> +   different from the file deleted in the merge source.  The user then
> +   has a chance to merge these unique changes.
> +
>     Implementation:
>  
> -   Call svn_ra_get_deleted_revnum(), as discussed in #5 in use case 4.
> +   In the repository, call svn_repos_deleted_rev().
>     The "start" revision is the source-left revision, and the "end"
>     revision is the source-right revision.  If the function returns a
>     valid "deleted" revision, decrement it by 1 to derive the "last
>     survivor" revision.
>  
> +   Note that the client library can't call svn_repos_deleted_rev()
> +   directly.  We'll have to add the corresponding function
> +   svn_ra_get_deleted_revnum() to each of the remote-access layers.
> +
>     Call svn_client_diff_summarize2() to compare the target file to the
>     "last survivor" from the merge source.  If there is a text
>     difference, the predicate is TRUE.
>  
> -   Rationale:
> -
> -   We don't want to flag every file deletion as a tree conflict.  We
> -   want to warn the user if the file to be deleted locally is
> -   different from the file deleted in the merge source.  The user then
> -   has a chance to merge these unique changes.
> -
>  ==========
>  USE CASE 6
>  ==========
>  
> -If 'svn merge' tries to delete a file that does not exist in the
> -target working copy, and the history of the target directory includes
> -a file of the same name, and this target file is related to the
> -deleted source file, then the target file is a tree conflict victim.
> -
> -The same predicates are applied as in use case 4, except that #2 is
> -skipped because the file in question does not exist at source-right.
> +The same predicates are applied as in use case 4.
>  
>  It would be nice to skip the tree conflict if the double-delete is
>  caused by two rename operations that have the same destination.
> 
> 


Re: Tree conflict detection in 'svn merge'

Posted by Stefan Sperling <st...@elego.de>.
On Wed, Mar 19, 2008 at 01:19:51PM +0100, Stefan Sperling wrote:
> > Just a brief note on the rest of your questions: I'm not right back into this
> > in detail, but yes I think Nico was right on simplifying that case.
> 
> Good, I will try to update detection.txt accordingly.

Julian,

here is a diff for review.

The diff itself is a bit awkward to read. You might want to apply
it and read the file in one piece and only refer to the diff
to see what I've actually changed.

If you have anything to add or any comments, please let me know.

I will commit this diff only after you've reviewed it, I might
have gotten some details wrong or may have overlooked something
entirely.

Thanks :)

Index: notes/tree-conflicts/detection.txt
===================================================================
--- notes/tree-conflicts/detection.txt	(revision 29943)
+++ notes/tree-conflicts/detection.txt	(working copy)
@@ -90,117 +90,32 @@ USE CASE 4
 ==========
 
 If 'svn merge' tries to modify a file that does not exist in the
-target working copy, and the history of the target directory includes
-a file of the same name, and this target file is related to the source
-file, then the target file is a tree conflict victim.
-
-A tree conflict exists if all of the following predicates are true:
-
-1. The merge operation is compatible with tree conflict detection.
-
-   Implementation:
-
-   We check specific fields of the merge-command baton (of type
-   merge_cmd_baton_t), returning TRUE if all of the following boolean
-   fields have the given values.
-
-   a. (same_repos == TRUE) The sources (the URLs of the left and right
-       sides of the diff) and the target (the URL of the working copy)
-       must be in the same repository.
-
-   b. (sources_ancestral == TRUE)  The merge-left URL given to the
-       merge command must be an ancestor of the merge-right URL.
-
-   c. (record_only == FALSE)  A record-only merge operation updates
-       mergeinfo without touching files.
-
-   Rationale:
-
-   These are conditions under which merge tracking is done.  We check
-   them first because it's cheap to do so (no repository access
-   required).  It's not yet clear how to handle --ignore-ancestry, so
-   its field is not in the list.
-
-2. The source-left file and the source-right file have a common
-   ancestor.
-
-   Implementation:
-
-   Call svn_client__get_youngest_common_ancestor().  If the youngest
-   common ancestor (YCA) is the source-left file, the predicate is
-   TRUE.
-
-   Rationale:
-
-   This is more specific than #1b above.  This predicate applies to a
-   single file, while #1b applies to the full merge sources, which are
-   usually directory trees.
-
-3. The target directory and the corresponding source-left directory
-   have a common ancestor.
-
-   Implementation:
-
-   Call svn_client__get_youngest_common_ancestor(), passing the two
-   dirs as arguments.  If a YCA exists, the predicate is TRUE.
-
-   Rationale:
-
-   The deletion of a file is not part of the history of the file
-   itself.  Rather it is part of the history of its parent directory.
-   If the parent (target) directory has no history in common with the
-   corresponding merge source directory, then no tree conflict is
-   possible.
-
-4. The file existed in the YCA directory.
-
-   Implementation:
-
-   Call svn_ra_check_path(), passing the filename and the revision of
-   the YCA directory.  If the function says there was a file there,
-   the predicate is TRUE.
-
-5. In the history of the target directory, a file by this name has
-   been deleted.
-
-   Implementation:
-
-   In the repository, call svn_repos_deleted_rev().  The "start"
-   revision arg is the revision of the YCA directory.  The "end"
-   revision arg is the HEAD revision.  If the function sets a valid
-   "deleted" revision, then the predicate is TRUE.
-
-   Rationale:
-
-   We already know that the file doesn't exist, so we know it was
-   deleted.  The specific revision is useful in other predicates.
-
-   At first I thought the "end" revision should be the BASE of the
-   target directory.  But that could lead to undetected tree
-   conflicts.  Suppose the user has committed a file deletion and then
-   merged without updating first.  The target directory is out of
-   date, and a search limited to the target directory's BASE would not
-   find the file deletion.
-
-   Note that the client library can't call svn_repos_deleted_rev()
-   directly.  We'll have to add the corresponding function
-   svn_ra_get_deleted_revnum() to each of the remote-access layers.
-
-6. The file at source-left and the file deleted in the target
-   directory's history have a common ancestor.
-
-   Implementation:
-
-   Call svn_client__get_youngest_common_ancestor(), passing the
-   source-left file and the "last surviving revision" of the target
-   file, derived from #5 above.  If they have a common ancestor, the
-   predicate is TRUE.  We can finally declare that we have found a
-   tree conflict!
-
-   Rationale:
-
-   I suppose it would be equivalent to pass the revision at
-   source-left and the revision of the YCA directory.
+target working copy, then the target file is a tree conflict victim.
+The rationale behind this is that the source diff doesn't cover as
+many revisions as it should. The file should either be brought in by
+adding the revision that created the file to the list of revisions
+to be merged, or changes made to it on the source branch should be
+omitted from the merge range entirely.
+
+We will need to store tree-conflict information in entries about files
+that may not actually be present in the working copy at all.
+
+If a modification to the nonexistent file is part of a larger diff
+with changes to other files that should be merged, the user will
+need to be able to manually resolve the tree-conflict while keeping
+the desired changes.
+
+Users must be able to run a second merge command to resolve the
+tree-conflict, or repeat a previous merge operation, but with
+additional revisions, without harm.
+
+However, the current plan is to disallow merges into tree-conflicted
+directories. This means that users will first have to mark the
+tree-conflict around the missing victim as resolved before attempting
+to merge the file again, this time including the revision that created
+the file. This may be a bit of an awkward work flow but is required to
+solve the problem this use case has in the current implementation,
+namely that missing files may accidentally be overlooked during merging.
 
 ==========
 USE CASE 5
@@ -211,57 +126,85 @@ victim if its text is different from the
 source.  We don't want to forget any text changes that are unique to
 the file at the current URL.
 
+To allow uncommitted text modifications in the working copy, we should
+do any text comparisons against the WORKING revision.
+
 A tree conflict exists if all of the following predicates are true:
 
-1. The merge operation is compatible with tree conflict detection.
-   Same as #1 in use case 4.
+1. We check specific fields of the merge-command baton (of type
+   merge_cmd_baton_t). If all of the following boolean fields have
+   the given values, we might have a tree conflict.
+
+    a. (same_repos == TRUE) Both of the source URLs, merge-left and
+        merge-right, must be in the same repository. This is also
+        a requirement of the current merge-tracking implementation.
+
+        Julian Foad said this requirement might be too strict in
+        case Subversion ever grows support for merging between
+        different repositories:
+
+        "I agree that the source and target must be in the same
+        repository (unless ancestry is being ignored), but only because
+        we currently have no way to trace the ancestry across repositories.
+        I don't see why this same_repos condition flag exists or should
+        be considered independently from asking whether we can find a
+        common ancestor."
+        http://svn.haxx.se/dev/archive-2008-02/0611.shtml
+
+    b. (sources_ancestral == TRUE) The merge-left URL given to the
+        merge command must be an ancestor of the merge-right URL.
+
+    c. (ignore_ancestry == FALSE) The rest of the predicates below
+        depend on ancestry queries, so if the user wants to ignore
+        ancestry there's not much point in looking for tree conflicts.
+
+    d. (record_only == FALSE) A record-only merge operation updates
+        mergeinfo without touching files. 
 
 2. The target file and the source-left file have a common ancestor.
 
+   Rationale:
+   
+   Otherwise the files are not related, so differences between
+   them cannot be due to separate lines of history with conflicting
+   tree-related changes.
+
    Implementation:
 
    Call svn_client__get_youngest_common_ancestor().  If the ancestor
    exists, the predicate is TRUE.
 
-   Rationale:
-
-   Thankfully, the job here is a lot simpler than in use case 4,
-   because we don't have to search the history to find a possible
-   target file to serve as the tree conflict victim.
-
 3. The text of the target file does not match the text of the
    "last surviving revision" of the file after merge-left.
 
+   Rationale:
+
+   We don't want to flag every file deletion as a tree conflict.  We
+   want to warn the user if the file to be deleted locally is
+   different from the file deleted in the merge source.  The user then
+   has a chance to merge these unique changes.
+
    Implementation:
 
-   Call svn_ra_get_deleted_revnum(), as discussed in #5 in use case 4.
+   In the repository, call svn_repos_deleted_rev().
    The "start" revision is the source-left revision, and the "end"
    revision is the source-right revision.  If the function returns a
    valid "deleted" revision, decrement it by 1 to derive the "last
    survivor" revision.
 
+   Note that the client library can't call svn_repos_deleted_rev()
+   directly.  We'll have to add the corresponding function
+   svn_ra_get_deleted_revnum() to each of the remote-access layers.
+
    Call svn_client_diff_summarize2() to compare the target file to the
    "last survivor" from the merge source.  If there is a text
    difference, the predicate is TRUE.
 
-   Rationale:
-
-   We don't want to flag every file deletion as a tree conflict.  We
-   want to warn the user if the file to be deleted locally is
-   different from the file deleted in the merge source.  The user then
-   has a chance to merge these unique changes.
-
 ==========
 USE CASE 6
 ==========
 
-If 'svn merge' tries to delete a file that does not exist in the
-target working copy, and the history of the target directory includes
-a file of the same name, and this target file is related to the
-deleted source file, then the target file is a tree conflict victim.
-
-The same predicates are applied as in use case 4, except that #2 is
-skipped because the file in question does not exist at source-right.
+The same predicates are applied as in use case 4.
 
 It would be nice to skip the tree conflict if the double-delete is
 caused by two rename operations that have the same destination.


-- 
stefan
http://stsp.name                                         PGP Key: 0xF59D25F0

Re: Tree conflict detection in 'svn merge'

Posted by Stefan Sperling <st...@elego.de>.
On Wed, Mar 19, 2008 at 02:26:49AM +0000, Julian Foad wrote:
> --- Stefan Sperling <st...@elego.de> wrote:
> > Have you found someone informed about the details of merging
> > who is willing to help us analyze the issue yet?
> > Would anyone on the list reading this volunteer to do so?
> 
> I've just spent a couple of days with Paul and Mike and although we weren't
> specifically discussing tree conflicts I've gained a much better general
> understanding of how merging works in Subversion. I think I can now see how
> far we have to take this conflict detection, and it's not too far.

OK. I am eagerly waiting for details :)

> > It seems that part of Stephen Butler's rather elaborate plan about
> > use cases 4 and 5 in notes/tree-conflicts/detection.txt has been
> > made obsolete by comments made by Nico, stating that at least use
> > case 4 could be detected in much a simpler way. Can you confirm this?
> 
> Just a brief note on the rest of your questions: I'm not right back into this
> in detail, but yes I think Nico was right on simplifying that case.

Good, I will try to update detection.txt accordingly.

> On the subject of renames, yes I think we can and should proceed with detecting
> conflicts to the same degree (or lack) of sophistication that "svn merge"
> already does (or doesn't) cope. I think this is feasible and useful.

Great.

-- 
Stefan Sperling <st...@elego.de>                 Software Developer
elego Software Solutions GmbH                            HRB 77719
Gustav-Meyer-Allee 25, Gebaeude 12        Tel:  +49 30 23 45 86 96 
13355 Berlin                              Fax:  +49 30 23 45 86 95
http://www.elego.de                 Geschaeftsfuehrer: Olaf Wagner

Re: Tree conflict detection in 'svn merge'

Posted by Julian Foad <ju...@btopenworld.com>.
--- Stefan Sperling <st...@elego.de> wrote:
> I'm currently reading through the archives, trying to get an idea about
> the current state of merging and tree-conflicts. I have some comments
> and questions for you and everyone else interested:
> 
> Have you found someone informed about the details of merging
> who is willing to help us analyze the issue yet?
> Would anyone on the list reading this volunteer to do so?

I've just spent a couple of days with Paul and Mike and although we weren't
specifically discussing tree conflicts I've gained a much better general
understanding of how merging works in Subversion. I think I can now see how
far we have to take this conflict detection, and it's not too far.


> It seems that part of Stephen Butler's rather elaborate plan about
> use cases 4 and 5 in notes/tree-conflicts/detection.txt has been
> made obsolete by comments made by Nico, stating that at least use
> case 4 could be detected in much a simpler way. Can you confirm this?

Just a brief note on the rest of your questions: I'm not right back into this
in detail, but yes I think Nico was right on simplifying that case. On the
subject of renames, yes I think we can and should proceed with detecting
conflicts to the same degree (or lack) of sophistication that "svn merge"
already does (or doesn't) cope. I think this is feasible and useful.

- Julian


> 
> If so, I think we should update detection.txt to reflect the current
> status. I could try to modify the document accordingly and post a diff
> for review, also because this would help me getting back into the loop
> again after having been busy with other things than tree-conflicts
> for a while. Should I do that?
> 
> Have you yourself made any advances in analysing the issue?
> If so, would you mind sharing your thoughts on the list?
> 
> Having read some of the comments made by you and Nico, especially
> about relating source items to target items during merging, and the
> new use cases proposed by Nico, I keep thinking "Oh man, if only we had
> true renames, all this would not be such a big issue...".
> Do you feel the same? Do you think it's feasible trying to carry on with
> implementing tree-conflicts detection without true renames?
> I don't want to sound pessimistic here, far from it. I'd just like to
> know whether others had or have similar thoughts on this.
> Obviously, a true-rename implementation would open a whole different can
> of worms and is way outside the scope of the tree-conflicts branch.
> I'd still like to get at least a faint idea about to what degree true
> renames would help in reducing the complexity of the problems the
> tree-conflicts branch has to deal with. I've already written about what
> true renames would mean for our update and switch use cases in
> detection.txt.
> 
> I'll be able to work again full-time on tree-conflicts for the next
> four weeks at least. I hope we can get past the design phase during
> this time and hopefully get some code written. I'm motivated to do so,
> anyway. Oh, and don't worry, I'm not saying that I'd push for writing
> code before the design is solid. I'd just very much like us to get there :)



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Tree conflict detection in 'svn merge'

Posted by Stefan Sperling <st...@elego.de>.
On Fri, Feb 29, 2008 at 12:20:47AM +0000, Julian Foad wrote:
> It sounds like we're trying to define what merging means (with respect to 
> what target corresponds to what source), and I don't know whether we're 
> defining it correctly.
> 
> In fact, this algorithm is a fundamental part of merging.
> 
> I'm afraid my knowledge of merging is not yet up to the task of analysing this.
> 
> I'll see what I can do, but to begin with that mainly means getting help 
> from someone who knows about merging.

Julian,

I'm currently reading through the archives, trying to get an idea about
the current state of merging and tree-conflicts. I have some comments
and questions for you and everyone else interested:

Have you found someone informed about the details of merging
who is willing to help us analyze the issue yet?
Would anyone on the list reading this volunteer to do so?

It seems that part of Stephen Butler's rather elaborate plan about
use cases 4 and 5 in notes/tree-conflicts/detection.txt has been
made obsolete by comments made by Nico, stating that at least use
case 4 could be detected in much a simpler way. Can you confirm this?

If so, I think we should update detection.txt to reflect the current
status. I could try to modify the document accordingly and post a diff
for review, also because this would help me getting back into the loop
again after having been busy with other things than tree-conflicts
for a while. Should I do that?

Have you yourself made any advances in analysing the issue?
If so, would you mind sharing your thoughts on the list?

Having read some of the comments made by you and Nico, especially
about relating source items to target items during merging, and the
new use cases proposed by Nico, I keep thinking "Oh man, if only we had
true renames, all this would not be such a big issue...".
Do you feel the same? Do you think it's feasible trying to carry on with
implementing tree-conflicts detection without true renames?
I don't want to sound pessimistic here, far from it. I'd just like to
know whether others had or have similar thoughts on this.
Obviously, a true-rename implementation would open a whole different can
of worms and is way outside the scope of the tree-conflicts branch.
I'd still like to get at least a faint idea about to what degree true
renames would help in reducing the complexity of the problems the
tree-conflicts branch has to deal with. I've already written about what
true renames would mean for our update and switch use cases in detection.txt.

I'll be able to work again full-time on tree-conflicts for the next
four weeks at least. I hope we can get past the design phase during
this time and hopefully get some code written. I'm motivated to do so,
anyway. Oh, and don't worry, I'm not saying that I'd push for writing
code before the design is solid. I'd just very much like us to get there :)

Thanks,
-- 
Stefan Sperling <st...@elego.de>                 Software Developer
elego Software Solutions GmbH                            HRB 77719
Gustav-Meyer-Allee 25, Gebaeude 12        Tel:  +49 30 23 45 86 96 
13355 Berlin                              Fax:  +49 30 23 45 86 95
http://www.elego.de                 Geschaeftsfuehrer: Olaf Wagner

Re: Tree conflict detection in 'svn merge'

Posted by Stefan Sperling <st...@elego.de>.
On Fri, Feb 29, 2008 at 12:20:47AM +0000, Julian Foad wrote:
> I'm afraid my knowledge of merging is not yet up to the task of analysing this.

Same here.

> I'll see what I can do, but to begin with that mainly means getting help 
> from someone who knows about merging.

Indeed, it would be great if someone who was involved in implementing
all the merge-tracking magic could provide some comments.

Maybe we could even leverage merge-tracking meta data a bit during tree
conflict detection? I don't know enough [yet] about how merging works
to make up my mind about this.

-- 
Stefan Sperling <st...@elego.de>                 Software Developer
elego Software Solutions GmbH                            HRB 77719
Gustav-Meyer-Allee 25, Gebaeude 12        Tel:  +49 30 23 45 86 96 
13355 Berlin                              Fax:  +49 30 23 45 86 95
http://www.elego.de                 Geschaeftsfuehrer: Olaf Wagner

Re: Tree conflict detection in 'svn merge'

Posted by Julian Foad <ju...@btopenworld.com>.
Stephen Butler wrote:
> Quoting Stephen Butler <sb...@elego.de>:
> 
>> Quoting Julian Foad <ju...@btopenworld.com>:
>>
>>> I am having difficulty understanding your proposal in detail because it
>>> is written in terms of the fields of merge_cmd_baton_t, but without
>>> saying exactly where and when you mean to apply these rules. Could you
>>> try to write it primarily in terms of universal truth concepts,
> 
> 
> Hi Julian and all other tree-conflict fans,
> 
> I don't know if I've managed to prove any "universal truth concepts", ;-)

Er, I really did say that didn't I?!

> but I think the following draft excerpt from
> /notes/tree-conflicts/detection.txt makes it clearer how we plan to
> translate the general requirements of tree conflict detction into a
> series of Subversion API calls.
> 
> Feedback from anyone would be warmly appreciated.

I'd appreciate it if someone familiar with merging could check Stephen's and my 
assumptions about merging.


> ======================
> MERGE REQUIRES HISTORY
> ======================
> 
> A note on why tree conflict detection during 'svn merge' is so
> complicated:
[...]

OK

> If the user chooses the --ignore-ancestry option for 'svn merge', then
> we skip the tricky false-positive elimination and simply mark all of the
> potential tree conflicts.  [Is this reasonable?]

This is far from clear.

The first thing we need to get straight is what this "--ignore-ancestry" case 
means. Studying the code, the option appears to mean both "ignore any history 
of copies in the relationship between SOURCE1 and SOURCE2 when diffing them" 
and also "ignore any merge tracking information about what has been merged before".

I previously assumed that "merge --ignore-ancestry" meant "ignore historical 
connections between SOURCE1 and TARGET, and assume relative-pathname 
correspondence between SOURCE1 and TARGET". It is still not clear to me whether 
this is implied as well as the two meanings above.

It is not possible (even in theory) to detect conflicts without tracing the 
ancestral connection between SOURCE1 and TARGET. The whole idea of "conflicts" 
is that one CHANGE conflicts with another CHANGE. The change in SOURCE is 
between SOURCE1 and SOURCE2; the change in TARGET is between TARGET@ancestor 
and TARGET@HEAD where "ancestor" is the time of branching or some more recent 
time when the branch was caught up with the source branch. Without following 
the ancestry of TARGET there is no way to determine what changes have been made 
in TARGET.

Whatever it means exactly, is this "ignore ancestry" case an important one with 
regard to conflict detection? If not, I'll happily ignore it for the time 
being. I would like to figure it out eventually, but my gut feeling is we 
should concentrate on the "proper merge" case first and regard this as a 
special simplification that we can make later.


> Before investigating, we had assumed that it was possible to ask the
> repository a vague question such as "When was the URL '/Foo' most
> recently deleted?"  But there's no such API.  It's now clear that we
> must ask a more specific question: "Given a revision range in which
> the URL '/Foo' exists at the start, when was '/Foo' first deleted?"
> 
> Determining a valid "start" revision is tricky because we don't know
> whether the file ever existed.  File deletions are part of the history
> of a directory, so I think it's reasonable to require that the target
> directory and the source-left directory have a youngest common ancestor
> (YCA).

I'll assume you're talking about the notice-ancestry (normal) case. A common 
ancestor is necessary for proper merging. (If somebody tries to apply a merge 
to a TARGET that doesn't have a common ancestor with SOURCE, then I think there 
are some simple rules for making a "best effort" attempt at merging. I have 
some ideas about what those rules are but I think this is a distraction from 
the main case.)

So, yes, it's OK to require that there is a common ancestor in order to achieve 
conflict detection.


> ==========
> USE CASE 4
> ==========
> 
> If 'svn merge' tries to modify a file that does not exist in the
> target working copy, and the history of the target directory includes
> a file of the same name, and this target file is related to the source
> file, then the target file is a tree conflict victim.

As this so-called "target file" does not exist, could we say more precisely, 
"If ... same name, and this (previously existing) version of the target file is 
related to the source file, then the (nonexistent) target file is a tree 
conflict victim."

It sounds like we're trying to define what merging means (with respect to what 
target corresponds to what source), and I don't know whether we're defining it 
correctly.

In fact, this algorithm is a fundamental part of merging.

I'm afraid my knowledge of merging is not yet up to the task of analysing this.

I'll see what I can do, but to begin with that mainly means getting help from 
someone who knows about merging.

- Julian

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Tree conflict detection in 'svn merge'

Posted by Stephen Butler <sb...@elego.de>.
Quoting Stephen Butler <sb...@elego.de>:
> Quoting Julian Foad <ju...@btopenworld.com>:
>> I am having difficulty understanding your proposal in detail because it
>> is written in terms of the fields of merge_cmd_baton_t, but without
>> saying exactly where and when you mean to apply these rules. Could you
>> try to write it primarily in terms of universal truth concepts,

Hi Julian and all other tree-conflict fans,

I don't know if I've managed to prove any "universal truth concepts", ;-)
but I think the following draft excerpt from
/notes/tree-conflicts/detection.txt makes it clearer how we plan to
translate the general requirements of tree conflict detction into a
series of Subversion API calls.

Feedback from anyone would be warmly appreciated.

Regards,
Steve


======================
MERGE REQUIRES HISTORY
======================

A note on why tree conflict detection during 'svn merge' is so
complicated:

During 'svn update', the local state is easy to check. If any files
are out of date (edited or scheduled for deletion in the working
copy), we mark them as tree conflict victims if the update causes a
delete-vs-update situation (use cases 1 & 2) or a double-delete (use
case 3).

During 'svn merge', the local state is not easy to check.  For use
cases 4 & 6, where the file has been deleted in the working copy's
branch, there's no victim at all in the working copy.  We need to
explore the repository history, seeking the deletion of a file that
corresponds to the file that was edited or deleted in the merge
source.

If we presume the existence of tree conflicts without checking the
history, it's likely that the user will be spammed with "false
positive" tree conflict warnings about files that never existed in the
current branch.  Nobody likes a spammer. :-)

If the user chooses the --ignore-ancestry option for 'svn merge', then
we skip the tricky false-positive elimination and simply mark all of the
potential tree conflicts.  [Is this reasonable?]

Before investigating, we had assumed that it was possible to ask the
repository a vague question such as "When was the URL '/Foo' most
recently deleted?"  But there's no such API.  It's now clear that we
must ask a more specific question: "Given a revision range in which
the URL '/Foo' exists at the start, when was '/Foo' first deleted?"

Determining a valid "start" revision is tricky because we don't know
whether the file ever existed.  File deletions are part of the history
of a directory, so I think it's reasonable to require that the target
directory and the source-left directory have a youngest common ancestor
(YCA).

==========
USE CASE 4
==========

If 'svn merge' tries to modify a file that does not exist in the
target working copy, and the history of the target directory includes
a file of the same name, and this target file is related to the source
file, then the target file is a tree conflict victim.

A tree conflict exists if all of the following predicates are true:

1. The merge operation is compatible with tree conflict detection.

    Implementation:

    We check specific fields of the merge-command baton (of type
    merge_cmd_baton_t), returning TRUE if all of the following boolean
    fields have the given values.

    a. (same_repos == TRUE) The sources (the URLs of the left and right
        sides of the diff) and the target (the URL of the working copy)
        must be in the same repository.

    b. (sources_ancestral == TRUE)  The merge-left URL given to the
        merge command must be an ancestor of the merge-right URL.

    c. (record_only == FALSE)  A record-only merge operation updates
        mergeinfo without touching files.

    Rationale:

    These are conditions under which merge tracking is done.  We check
    them first because it's cheap to do so (no repository access
    required).  It's not yet clear how to handle --ignore-ancestry, so
    its field is not in the list.

2. The source-left file and the source-right file have a common
    ancestor.

    Implementation:

    Call svn_client__get_youngest_common_ancestor().  If the youngest
    common ancestor (YCA) is the source-left file, the predicate is
    TRUE.

    Rationale:

    This is more specific than #1b above.  This predicate applies to a
    single file, while #1b applies to the full merge sources, which are
    usually directory trees.

3. The target directory and the corresponding source-left directory
    have a common ancestor.

    Implementation:

    Call svn_client__get_youngest_common_ancestor(), passing the two
    dirs as arguments.  If a YCA exists, the predicate is TRUE.

    Rationale:

    The deletion of a file is not part of the history of the file
    itself.  Rather it is part of the history of its parent directory.
    If the parent (target) directory has no history in common with the
    corresponding merge source directory, then no tree conflict is
    possible.

4. The file existed in the YCA directory.

    Implementation:

    Call svn_ra_check_path(), passing the filename and the revision of
    the YCA directory.  If the function says there was a file there,
    the predicate is TRUE.

5. In the history of the target directory, a file by this name has
    been deleted.

    Implementation:

    In the repository, call svn_repos_deleted_rev().  The "start"
    revision arg is the revision of the YCA directory.  The "end"
    revision arg is the HEAD revision.  If the function sets a valid
    "deleted" revision, then the predicate is TRUE.

    Rationale:

    We already know that the file doesn't exist, so we know it was
    deleted.  The specific revision is useful in other predicates.

    At first I thought the "end" revision should be the BASE of the
    target directory.  But that could lead to undetected tree
    conflicts.  Suppose the user has committed a file deletion and then
    merged without updating first.  The target directory is out of
    date, and a search limited to the target directory's BASE would not
    find the file deletion.

    Note that the client library can't call svn_repos_deleted_rev()
    directly.  We'll have to add the corresponding function
    svn_ra_get_deleted_revnum() to each of the remote-access layers.

6. The file at source-left and the file deleted in the target
    directory's history have a common ancestor.

    Implementation:

    Call svn_client__get_youngest_common_ancestor(), passing the
    source-left file and the "last surviving revision" of the target
    file, derived from #5 above.  If they have a common ancestor, the
    predicate is TRUE.  We can finally declare that we have found a
    tree conflict!

    Rationale:

    I suppose it would be equivalent to pass the revision at
    source-left and the revision of the YCA directory.

==========
USE CASE 5
==========

If 'svn merge' deletes an existing file, the file is a tree conflict
victim if its text is different from the file deleted in the merge
source.  We don't want to forget any text changes that are unique to
the file at the current URL.

A tree conflict exists if all of the following predicates are true:

1. The merge operation is compatible with tree conflict detection.
    Same as #1 in use case 4.

2. The source-left file and the source-right file have a common
    ancestor.  Same as #2 in use case 4

3. The target file and the source-left file have a common ancestor.

    Implementation:

    Call svn_client__get_youngest_common_ancestor().  If the ancestor
    exists, the predicate is TRUE.

    Rationale:

    Thankfully, the job here is a lot simpler than in use case 4,
    because we don't have to search the history to find a possible
    target file to serve as the tree conflict victim.

5. The text of the target file does not match the text of the
    "last surviving revision" of the file after merge-left.

    Implementation:

    Call svn_ra_get_deleted_revnum(), as discussed in #5 in use case 4.
    The "start" revision is the source-left revision, and the "end"
    revision is the source-right revision.  If the function returns a
    valid "deleted" revision, decrement it by 1 to derive the "last
    survivor" revision.

    Call svn_client_diff_summarize2() to compare the target file to the
    "last survivor" from the merge source.  If there is a text
    difference, the predicate is TRUE.

    Rationale:

    We don't want to flag every file deletion as a tree conflict.  We
    want to warn the user if the file to be deleted locally is
    different from the file deleted in the merge source.  The user then
    has a chance to merge these unique changes.

==========
USE CASE 6
==========

If 'svn merge' tries to delete a file that does not exist in the
target working copy, and the history of the target directory includes
a file of the same name, and this target file is related to the
deleted source file, then the target file is a tree conflict victim.

The same predicates are applied as in use case 4, except that #2 is
skipped because the file in question does not exist at source-right.

It would be nice to skip the tree conflict if the double-delete is
caused by two rename operations that have the same destination.
But we have to mark this as a tree conflict due to the current lack
of "true rename" support.  See notes/tree-conflicts/detection.txt
for more on this topic.


-- 
Stephen Butler | Software Developer
elego Software Solutions GmbH
Gustav-Meyer-Allee 25 | 13355 Berlin | Germany
fon: +49 30 2345 8696 | mobile: +49 163 25 45 015
fax: +49 30 2345 8695 | http://www.elegosoft.com
Geschäftsführer: Olaf Wagner | Sitz der Gesellschaft: Berlin
Amtsgericht Charlottenburg HRB 77719 | USt-IdNr: DE163214194



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org


Re: Tree conflict detection in 'svn merge'

Posted by Stephen Butler <sb...@elego.de>.
Quoting Julian Foad <ju...@btopenworld.com>:
> I am having difficulty understanding your proposal in detail because it
> is written in terms of the fields of merge_cmd_baton_t, but without
> saying exactly where and when you mean to apply these rules. Could you
> try to write it primarily in terms of universal truth concepts, like
>
>   "If it is possible to determine a common ancestor, then ..."
>
> instead of
>
>   "If the 'is_ancestor' field is true, then ...".
>
> That would help me a lot.

Hi Julian,

I'm rewriting the design proposal for clarity (separating the
implementation details from the rationale, for starters).  I'll also
update the parts we've already discussed.

Steve

-- 
Stephen Butler | Software Developer
elego Software Solutions GmbH
Gustav-Meyer-Allee 25 | 13355 Berlin | Germany
fon: +49 30 2345 8696 | mobile: +49 163 25 45 015
fax: +49 30 2345 8695 | http://www.elegosoft.com
Geschäftsführer: Olaf Wagner | Sitz der Gesellschaft: Berlin
Amtsgericht Charlottenburg HRB 77719 | USt-IdNr: DE163214194



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org


Re: Tree conflict detection in 'svn merge'

Posted by Julian Foad <ju...@btopenworld.com>.
Stefan and Stephen,

I have been trying to understand your proposal in detail.

Would you be able to help me by updating this document in the light of the 
comments that followed so far, and with one further consideration which is this:

I am having difficulty understanding your proposal in detail because it is 
written in terms of the fields of merge_cmd_baton_t, but without saying exactly 
where and when you mean to apply these rules. Could you try to write it 
primarily in terms of universal truth concepts, like

   "If it is possible to determine a common ancestor, then ..."

instead of

   "If the 'is_ancestor' field is true, then ...".

That would help me a lot.

Thanks.
- Julian


Stephen Butler wrote:
> Hello tree-conflict fans,
> 
> The first phase of tree conflict detection is available in the tree-
> conflicts feature branch.  See this post for a recap of the current
> functionality implemented by this branch:
> 
>   http://svn.haxx.se/dev/archive-2008-01/0296.shtml
> 
> In extending the current tree-conflict-detection scheme to cover
> 'svn merge', we want to avoid presenting the user a lot of apparent
> tree conflicts that involve files with no common ancestry.  To weed
> out these false positives, we have to query the repository.  Our
> current plan is described below, arranged according to use case.
> The use cases are described in the recap email above and in
> notes/tree-conflicts/use-cases.txt.
> 
> We would be grateful for any feedback.
> 
> Thanks,
> Steve
> 
> 
> ==========
> USE CASE 4
> ==========
> 
> A file modified in the merge diff does not exist at the current URL.
> If a file at the current URL has been deleted in the parent dir's
> history, then we might have a tree conflict.
> 
> A tree conflict exists if all of the following predicates are true:
> 
> 1. The merge operation is compatible with tree conflict detection:
>    We check specific fields of the merge-command baton (of type
>    merge_cmd_baton_t).  If all of the following boolean fields have
>    the given values, we might have a tree conflict.
> 
>    a. (same_repos == TRUE)  Both of the source URLs, merge-left and
>        merge-right, must be in the same repository.
> 
>    b. (sources_ancestral == TRUE)  The merge-left URL given to the
>        merge command must be an ancestor of the merge-right URL.
> 
>    c. (ignore_ancestry == FALSE)  The rest of the predicates below
>        depend on ancestry queries, so if the user wants to ignore
>        ancestry there's not much point in looking for tree conflicts.
> 
>    d. (record_only == FALSE)  A record-only merge operation updates
>        mergeinfo without touching files.
> 
> 2. The file at merge-left is an ancestor of the file at merge-right:
>    We call svn_client__get_youngest_common_ancestor().  If the YCA
>    is the merge-left file, we might have a tree conflict.  Note that
>    this is a more specific query than #1b above.
> 
> 3. In the history of the current directory, a file by this name has
>    been deleted:  In the repository, we will call the function
>    svn_repos_deleted_rev(), passing a "start" revision in which the
>    file existed and receiving a "deleted" revision in which the file
>    was deleted.  But first we have to choose a valid "start" revision,
>    which is a bit tricky since we don't yet know whether the file
>    ever existed in the current directory.
> 
>    a. The parent dir and the corresponding dir at merge-left have
>       a common ancestor:  We pass the two directories to
>       svn_client__get_youngest_common_ancestor().  If a common
>       ancestor exists, we might have a tree conflict.
> 
>    b. The file existed in the parent dir's common-ancestor revision:
>       If svn_ra_check_path() says that a file by that name existed
>       in the parent dir at the common-ancestor revision, we might
>       have a tree conflict.
> 
>    c. The file has been deleted in the parent dir between the
>       common-ancestor revision and the working copy's base revision:
>       We call svn_ra_get_deleted_revnum(), passing it the common-
>       ancestor revision as the "start" revision and the base revision
>       as the "end" revision.  Note that this function does not yet
>       exist in the remote-access layers.  We'll have to implement it.
> 
> 4. The file at merge-left and the file deleted in the parent-dir's
>    history have a common ancestor:  We pass the merge-left file and
>    the "last surviving revision" of the file, derived from #3c above,
>    to svn_client__get_youngest_common_ancestor().  If they have a
>    common ancestor, we have a tree conflict (finally!).
> 
> 
> ==========
> USE CASE 5
> ==========
> 
> An existing file is deleted by the merge diff.  We don't want to lose
> any text changes that are unique to the file at the current URL.
> 
> A tree conflict exists if all of the following predicates are true:
> 
> 1. The merge operation is compatible with tree conflict detection.
>    Same as #1 in use case 4.
> 
> 2. The current file and the file at merge-left have a common
>    ancestor:  We can call svn_client__get_youngest_common_ancestor().
>    If the ancestor exists, we might have a tree conflict.
> 
> 3. The text of the current file does not match the text of the
>    "last surviving revision" of the file after merge-left:  The last
>    survivor is found by passing svn_ra_get_deleted_revnum() the
>    merge-left revision as "start" and the merge-right revision as
>    "end".  Thankfully, this is simpler than #3 in use case 4.  I
>    think we can call svn_client_diff_summarize2() to compare the
>    files.  If there is a text difference, we have a tree conflict.
> 
> 
> ==========
> USE CASE 6
> ==========
> 
> A file deleted by the merge diff does not exist at the current URL.
> If a file at the current URL has been deleted in the parent dir's
> history, then we might have a tree conflict.
> 
> A tree conflict exists if all of the following predicates are true:
> 
> 1. The merge operation is compatible with tree conflict detection.
>    Same as #1 in use case 4.
> 
> 2. In the history of the parent directory, a file by this name has
>    been deleted.  Same as #3 in use case 4.
> 
> 3. The file at merge-left and the file deleted in the parent-dir's
>    history have a common ancestor.  Same as #4 in use case 4.
> 
> It would be nice to skip the tree conflict if the double-delete is
> caused by two rename operations that have the same destination.
> But we have to mark this as a tree conflict due to the current lack
> of "true rename" support.  See notes/tree-conflicts/detection.txt
> for more on this topic.
> 


-- 
http://www.foad.me.uk/

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Subversion on a large repository

Posted by Vishnu Venkatesan <vi...@oracle.com>.
Hi,
  I am in the process of evaluating subversion for hosting a repository 
of about 10,000+ files with a size of 2 GB that can change at least 10% 
everyday.
  Can anyone please let me know if there are any references of 
subversion deployment with such large repository with FSFS or Berkeley DB.
Some of the things that I am looking for
1. What would be the advantages of using one over the other (FSFS vs 
Berkeley DB)
2. Any specific limitations
3. How much scalable the repository would be -- for about 100-200 
concurrent commits

thanks,
Vishnu.

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org