= How Subversion's conflict resolver handles incoming moves = Given a victim of a tree conflict which may involve an incoming move, the conflict resolver must solve these problems: 1) Find all moves in the log within the operative revision range recorded in conflict meta data. Move detection is based on changed-paths data in the revision log. 2) If the conflict victim is not in the working copy, find a path in the working copy which corresponds to the current repository location of the conflict victim. 3) Find the conflict victim's counterpart and its path-wise history. 4) Determine which, if any, moves apply to the conflict victim's counterpart. The result of incoming move detection describes all moves affecting the conflict victim's counterpart, and by extension the victim itself, within the operative revision range recorded in conflict data. The result allows the conflict resolver to offer options which resolve the tree conflict by merging appropriate changes from the victim's counterpart to a node in the working copy which represents the conflict victim. == Node == A node is a versioned file or a directory as represented in an SVN repository. == Node relatedness == Given a node at path A at revision rX, and a node at path B at revision rY, the two nodes are related if the history of both nodes can be traced back to a single path C at revision rZ. == Finding moves in a given revision == In the revision log, moves are represented by disjoint copy and delete operations. Since Subversion 1.8, SVN clients enforce that after 'svn move A B', the deletion of A and the addition of B (as a copy of A) must be committed in the same revision. Move detection in the conflict resolver relies on this enforcement. === "Direct" moves === Direct moves appear with the following pattern: - A changed path P is deleted in rN. - A changed path Q appears in rN and is a copy of P at or after the last-changed revision of P@r{N-1}. - There is no other changed path R which is also a copy of P at or after the last-changed revison of P@r{N-1}. Example: In the most simple case, a file '^/trunk/alpha' moved in r3 would appear in the output of 'svn log -v' as: Changed paths: D /trunk/alpha A /trunk/alpha-moved (from /trunk/alpha:2) This same pattern would also be recognized as a move if it appeared in, say, r6, provided that the last-changed revision of ^/trunk/alpha@5 is still smaller or equal r2. === "Ambiguous" moves === Ambiguous moves appear with the following pattern: - A changed path P is deleted in rN. - A changed path Q1 appears in rN and is a copy of P at or after the last-changed revision of P@r{N-1}. - One or more changed paths Q[2,3,4,...] appear in rN as a copy of P at or after the last-changed revision of P@r{N-1}. Example: If a file '^/trunk/alpha' was copied twice and then moved in r3, this would appear in the output of 'svn log -v' as: Changed paths: D /trunk/alpha A /trunk/alpha-copied1 (from /trunk/alpha:2) A /trunk/alpha-copied2 (from /trunk/alpha:2) A /trunk/alpha-moved (from /trunk/alpha:2) In such situations, SVN cannot tell whether any of alpha's copies should in fact be treated as a move. Ambiguous moves require user interaction. During conflict resolution the user must pick the move destination from a set of candidates. === "Nested" moves === Nested moves appear with the following pattern: - A direct or ambiguous move M appears in rN. - A path P is deleted and P is a path-wise child of the copied path which belongs to move M. - A new path Q is added which was copied from the location P would have had in absence of the move M, at or after the last-changed revision of P@{N-1}. Examples: If a directory 'gamma' was moved in r3 and the child 'gamma/delta' was also moved in r3, this would appear in the output of 'svn log -v' as: Changed paths: D /trunk/gamma A /trunk/gamma-moved (from /trunk/gamma:2) D /trunk/gamma-moved/delta A /trunk/gamma-moved/delta-moved (from /trunk/gamma/delta:2) If the child was moved outside its parent instead of within its parent, the output might look like: Changed paths: A /trunk/epsilon/delta-moved (from /trunk/gamma/delta:2) D /trunk/gamma A /trunk/gamma-moved (from /trunk/gamma:2) D /trunk/gamma-moved/delta Nested moves inside nested moves are also possible. Again, added nodes appear as copied from locations they would have had in the absence of any other moves: Changed paths: D /trunk/gamma A /trunk/gamma-moved (from /trunk/gamma:4) D /trunk/gamma-moved/psi A /trunk/gamma-moved/psi-moved (from /trunk/gamma/psi:4) D /trunk/gamma-moved/psi-moved/omega A /trunk/omega-moved (from /trunk/gamma/psi/omega:4) == Finding a particular move == Repository nodes the update/merge/switch editor was working with are recorded in conflict meta data: - path@old-rev, old-node-kind - path@new-rev, new-node-kind The repos-path@rev is for the conflict victim is also available, as it appeared in the working copy at the time the conflict was flagged. To determine whether path@old-rev was moved to another path-moved@new-rev, SVN must look for a chain of moves which starts at path@old-rev and ends at new-rev. If a single such chain is found, then the final path-moved@new-rev is known. To do this, SVN scans all revisions between old-rev and new-rev and detects any moves within them. Moves of the same node are linked together and form move chains. If ambiguous moves are found in a revision, move chains may diverge into several directions at that revision. If nested moves are found in a revision, they end up being represented the same way as direct moves are (so they are no longer a special case from this point onwards). == Finding missing conflict victims == The repository location of the conflict victim is unkown if the victim cannot be found in the working copy ("local missing"). To find such missing nodes, SVN must first find all moves in the entire history of the parent directory of the conflict victim. Additionally, in the case of a merge operation, SVN must also find all moves in the history of the parent directory of path@old-rev, all the way up to the common ancestor of the root of the merge operation. This is because such moves might not have been applied to the target branch (working copy), for instance when cherry-picking a file modification, after the file has been moved on the source branch (see example at the end of this section). ### jcorvel: Maybe this additional search for moves on the source branch (in case of a merge operation) can be optional? Only do it if the moves found in the first search don't suffice? For each such move it checks whether the moved node is related to the known node at path@old-rev, or, if that does not exist, path@new-rev, by tracing backwards in history from path@old-rev/new-rev if the move's revision is smaller than old-rev/new-rev, or by tracing backwards in history from the moved path if the move's revision is larger than old-rev/new-rev. For any such related node's repository path at revision new-rev recorded in the conflict, a local path in the working copy is searched which is related to this repository path. Any such nodes found in the working copy are candidates for the missing conflict victim's current location, unless the node is inside a switched subtree or is itself a switched node or is an external. If multiple matches are found the user must be given a choice with a default suggestion. To avoid choosing bad default suggestions in cases where multiple branches are checked out into a working copy (such as in SVN's own test suite), a path-wise closest node to the conflict victim is the preferred suggestion. If no such node can be found, SVN assumes that the conflict victim was deleted instead of moved. === Missing conflict victim due to skipped move in merge source history === This can typically happen when cherry-picking a revision with a file modification, where this file has been moved on the source branch of the merge (and this move was not applied to the target branch): In r1, create directory A with file mu: Changed paths: A /A A /A/mu In r2, directory A is copied to A1 (branched): Changed paths: A /A1 (from /A:1) In r3, A/mu is moved: Changed paths: D /A/mu A /A/mu-moved (from /A/mu:2) In r4, A/mu-moved is edited: Changed paths: M /A/mu-moved If we now want to cherry-pick r4 from /A to a working copy of /A1, we get a tree conflict because mu-moved is missing. The relevant move we need to resolve this happened on /A, in r3. == Determining which, if any, moves apply == Next, SVN must determine whether any moves found between old-rev and new-rev link path@old-rev to an path-moved@new-rev, and whether path-moved@new-rev is related to the conflict victim. A move of path A to path B in rN applies to a path P@N if P is a path-wise child of, or equal to, A. == Special considerations for reverse operations == ... TODO talk about reverse-updates and -merges, and switches to older revs ...