[Subversion Wiki] Update of "MoveDev/Ev2MovesDesign" by JulianFoad

[Apache subversion Wiki <co...@subversion.apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Subversion Wiki" for change notification.

The "MoveDev/Ev2MovesDesign" page has been changed by JulianFoad:
https://wiki.apache.org/subversion/MoveDev/Ev2MovesDesign

Comment:
Part of a new page; the rest to come in a subsequent update

New page:
'''Ev2 Representation of Moves '''

<<TableOfContents(3)>>

== Summary ==
Ev2 was designed with an intention to support “move” semantics, but the current design of its move() method does not satisfy the requirements. Here I explain why, and present a solution.

The following principles constrain or guide Ev2 design:

 * An edit must be able to express any change that can be       constructed in a WC and committed.
 * An edit must be able to express any change that can be       constructed in a repo across multiple revisions.
 * Ev2 uses sequential description: a succession of incremental         edits applied to an initial state gives a final state.
 * Each node should be changed only once.

Given these constraints, not all combinations of moves can be expressed using a “move source to destination” operation, with or without a “rotate” operation, without using temporary paths.

Moves can be expressed, in general, using separate move-away and move-here operations.  The shape of this design is:

 * The “move away” end of a move is (or can be) a separate      operation from the corresponding “move here”.
 * While a subtree is “in limbo” after being “moved away”       from its source location and before being “moved here” at its   destination, the behaviour is as if it has been moved to a temporary    path.  The temporary path is in a different name-space so that it       cannot conflict with any real path, even a real path outside the        scope of the edit.

== Why is This Necessary? ==
=== Express Any Change ===
Since the purpose of the editor is to communicate a change originating in a WC when it is committed, and a change originating in a repository when the WC is updated, then it must be able to express any such change.  This includes updates across multiple revisions, and from a mixed-revision state to a single revision.

Through a series of simple steps of the form “move X to Y”, some quite funky overall changes can be created.  For example, starting from this state*:

{{{
|
+-- A
    |
    +-- B
}}}
the following sequence:

{{{
move /A/B /X
move /A /X/B
move /X /A
}}}
results in swapping the nodes at paths A and B:

{{{
|                       |
+-- A      mv--\ /-->   +-- A
    |           X           |
    +-- B  mv--/ \-->       +-- B
}}}
If those steps are performed in a WC and the result committed all at once, the editor needs to be able to handle it.  If those steps are committed separately, and then a working copy is updated, the editor needs to be able to handle it.

More examples are given later, some of which involve other operations such as “make directory” as well as moves.  All of this emergent complexity results from the introduction of a simple “move” primitive, and there does not seem to be any acceptable way to further constrain the basic move that would simplify the derived complexity.

'''* Notation:''' In the diagrams, a capital letter represents the name of a node; the node's identity (its node-copy-id) is not shown.  In sequential instructions of the form “move /A/B /X”, the “/A/B” represents the source path of a node in the tree state that is being incrementally modified, and “/X” represents the destination path that it will have in the new state after this instruction.

=== Temporary Paths ===
Paths in the Ev2 editor operations refer to the current state of the tree being edited, at that moment in the sequence of edit operations.  (The sole exception is the copy-from path, which is relative to a given committed revision.)

A natural and compact way of expressing moves would be as a mapping from original-state paths to final-state paths.  However, that paradigm does not fit well with the desire to express the edit as a sequence of incremental steps.  If we are going to include move functionality as steps in a sequence of edit operations, it makes sense to use paths that are relative to the current state.

Ev2 should not require the driver to express a change as a sequence of operations that can include moving a node to a temporary path and then later moving it again to the final path.  The end result of the edit is the important part, and there are unlimited potential sequences that lead to that result, and it does not make sense to require an edit driver to construct such a sequence arbitrarily, if there is an alternative method that specifies the result uniquely.  The receiver may in fact need to employ temporary paths in its implementation, but then it knows this and it is in a better position to construct such paths when needed, and it will know that they are temporary which may be important.

There are advantages to placing a node in its final position exactly once.  It was claimed that Google's BigTable implementation of Svn's back-end would have benefited from knowing that once a node has been edited then it is in its final state.  Ev2 aims to provide that guarantee, where Ev1 could not.

=== Sequential Description ===
Ev2 (svn_editor_t) intends to express a new state in terms of an old state and a description of the parts of the new state that differ from the old state, or, in other words, a description of the changes against the old state.  It uses a sequential, incremental description: for example, “add directory X, then copy file X/Y from somewhere, then edit the contents and properties of file X/Y”.

Only certain parts of the description are incremental.  Ev2 aims to allow nodes to be visited in arbitrary order, subject to a small number of restrictions.  The parts where ordering matters are:

 * tree changes before content changes
 * alter/add/copy a directory (if required) before touching its         (immediate) children

=== A Move Event is Not Adequate ===
Moves, in general, cannot be expressed as “move from path X to path Y” events in such a sequential description without introducing temporary paths.  This is because some cases require the source path of the move to be moved away, then some other steps, and then the destination path of the move can be populated.  Some classic examples are:

==== Example 1: Insert a directory level ====
{{{
|                     |
+--A  mv--\     (add) +--A
           \             |
            \-->         +--B
}}}
The add cannot happen before the move-away, but must happen before the move-here.

==== Example 2: Swap two siblings ====
{{{
|                     |
+--A     mv--\ /-->   +--A
|             X       |
+--B     mv--/ \-->   +--B
}}}
Neither of the moves can be completed before doing the move-away part of the other one.

==== Example 3: Swap two directory levels ====
{{{
|                     |
+--A     mv--\ /-->   +--A
   |          X          |
   +--B  mv--/ \-->      +--B
}}}
Neither of the moves can be completed before doing the move-away part of the other one.

=== A Rotate Event is Not Adequate ===
At one time there was an idea that the addition of a “rotate PATH1 PATH2 … PATHn” event would complete the semantics and allow arbitrary moves to be supported.

While this does enable Example 2 (swap two siblings) and Example 3 (swap two directory levels) and many other cases, it does not help with inserting a directory level (Example 1), and it has been shown [1] to be incapable of resolving other more involved cases involving swapping or rotation.  One specific example is swapping A with A/B/C [2]:

{{{
|                            |
+-- A          mv--\   /-->  +-- A
    |               \ /          |
    +-- B      mv--- X --->      +-- B
        |           / \              |
        +-- C  mv--/   \-->          +-- C
}}}
[1] Email thread on dev@, “Ev2 as a move-aware editor”, started on 2013-06-24, e.g. <http://svn.haxx.se/dev/archive-2013-06/0560.shtml> or <[[...@web186101.mail.ir2.yahoo.com>|http://mail-archives.apache.org/mod_mbox/subversion-dev/201306.mbox/%3C1372087321.76009.YahooMailNeo%40web186101.mail.ir2.yahoo.com%3E]]>.

[2] An example problem in thread [1], of swapping A with A/B/C: <http://svn.haxx.se/dev/archive-2013-06/0684.shtml> or <[[...@ntlworld.com>|http://mail-archives.apache.org/mod_mbox/subversion-dev/201306.mbox/%3C87bo6rewwp.fsf%40ntlworld.com%3E]]>.