Re: Tree conflict detection in 'svn merge'

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