Ev2 as a move-aware editor

For move tracking we need a move-aware editor.  svn_editor_t ("Ev2") is designed to support moves.  However, I'm not clear how its move support is meant to work, on a fairly basic level:

  * What are the ordering rules for moves?

  * Are the move operations to be interprested in series or in parallel?

  * When an operation refers to a node that is involved in a move, how are the paths to be interpreted?

From conversations with other devs I know I'm not the only one.  There are a number of rules written down in <svn_editor.h> but to my reading they didn't seem to explain the overall scheme, and they contain inconsistencies, some of which I have posted as queries to this list in the past but remain unresolved [1].

Having failed to grok what is intended, I have deliberately put off trying to dig further into Ev2's version of move support, until now, in order to think freely about the theory and to focus more evenly on all the areas of move tracking.  (That's why I started using Ev1 in my experimental branch [2] and in my notes [3].)  But now we should tackle this.

So, please could somebody help to elucidate how Ev2 move support works or should work?

== Basic Theory ==

I can imagine two possible extremes for the overall mode of operation to which such an editor *could* be designed: parallel and sequential.  I'll mention some essential characteristics of each.

== Sequential ==

Edits are described sequentially, incrementally.  The consumer maintains a state that describes the 'current' tree shape, starting with the initialtree shape, and being changed incrementally by each edit operation.

Each edit operation refers to paths that exist in the 'current' tree state and/or that will exist in the next state.

== Parallel ==

The producer sends all changes in parallel or in an unspecified order.  Each change is described independently of all other changes: it refers to paths (or nodes) in a way that doesn't depend on the other changes being sent.  In fact, rather than talking about 'operations' or 'changes', the semantics required here is to describe the final state in any compact way, not necessarily in terms of changes against the initial state.

(One case that may seem difficult to parallelize is adding a new parent directory and its children.  How can the consumer accept a child node before the creation of the parent directory?  The answer is simply that the consumer would be designed to operate this way, storing the children either in their final form or in a temporary form, and linking them into the parent once all necessary information has been received.)

== Hybrid ==

We could mix these and have a scheme that is partly parallel, partly sequential, according to some additional rules.  That is fine, but more complex to describe and understand.

Note that while Ev1 is mostly sequential, the copy-from field of a copy (when used for a move) is more like the parallel scheme, since it refers to a path in the initial tree state and not a path in the current tree state.

== Cyclic moves ==

We need to accommodate arbitrary sets of moves, including cycles.  For an example, we'll use a simple cycle, swapping two siblings A and B.  This ability is needed for two reasons:

  * Ev1 supports this (del A, copy A from B_at_OLD, del B, copy B from A_at_OLD).

  * A single edit must be able to represent the combination of any series of edits, and a series of moves can result in a cycle even if each individual edit only supports non-cyclic moves.  (1: mv B C.  2: mv A B.  3: mv C A.)

In a parallel scheme, no special treatment is necessary:

    A -> B
    B -> A

In a sequential scheme, there are two ways to accommodate cyclic moves:

  * Allow moving to a temporary path and then later to the final path:
    mv A tmp; mv B A; mv tmp B

  * Allow a 'swap A B' or 'rotate A B ...' operation:
    rotate A B

== Swap or Rotate ==

swap(A,B) == { A->B || B->A }

is a primitive operation.  ('||' indicates 'in parallel'.)

rotate(A,B,...N) == { A->B || B->... || ...->N || N->A }

is non-primitive, since any rotate can be composed from multiple sequential swaps.  For example, rotate(A,B,C) == { swap(B,C); swap(A,B) }.  It is no more useful to rotate more than two paths in one operation (rotate(A,B,C)) than to move more than two paths  in one operation (move(A,B,C) == { A->B || B->C }).

So if we have a sequential scheme and we don't want to use temporary paths, we should include the 'swap' primitive rather than a 'rotate'.

== Ev2 ==

One of Ev2's goals is to parallelize text modifications, in order to take advantage of Serf's parallelism.  What about tree changes, and specifically what are the semantics of the 'move' operation?  The Ev2 documentation indicates sequential requirements for the 'add' operation (parent before children), and also in this rule:

 * - The ancestor of an added, copied-here, moved-here, rotated, or
 *   modified node may not be deleted. The ancestor may not be moved
 *   (instead: perform the move, *then* the edits).

The doc string for 'svn_editor_move' says:

 * Move the node at @a src_relpath to @a dst_relpath.
 *
 * @a src_revision specifies the revision at which the receiver should
 * expect to find this node.  That is, @a src_relpath at the start of
 * the whole edit and @a src_relpath at @a src_revision must lie within
 * the same node-rev (aka history-segment).  This is just like the
 * revisions specified to svn_editor_delete() and svn_editor_rotate().
 * ...

The discussion implies that "the node at src_relpath" refers to a node in the initial tree state.  In that respect, it's a parallel operation: the source reference doesn't depend on previous moves.  But look at the 'move_cb' implementation in libsvn_fs/editor.c:

  # src_root == *initial* tree state

  svn_fs_copy(src_root, src_fspath, root, dst_fspath, scratch_pool)
  /* Notice: we're deleting the src repos path from the dst root. */
  # root == *current* tree state (txn)
  svn_fs_delete(root, src_fspath, scratch_pool)

The delete of src_relpath within the current tree state is potentially at odds with the copy from src_relpath relative to the initial state.  The delete would delete the wrong thing if the original node at this path has already been replaced, or would try to delete a non-existent node if it had already been deleted or moved away.  Could it have been replaced or deleted or moved away, if not itself then perhaps by a copy/move/add/delete of a parent directory?

Let's try the following scenario:

  A->A2 || A/B->B2  # move a child of a moved parent

Try with Ev2:

  move(src_relpath='A', src_rev=100, dst_relpath='A2', replaces_rev=-1)
  move(src_relpath='A/B', src_rev=100, dst_relpath='B2', replaces_rev=-1)

The implementation shown above would fail in the second move when trying to delete 'A/B', because that path no longer exists in the transaction after the first move deleted the whole subtree at 'A'.

The other way works fine:

  move(src_relpath='A/B', src_rev=100, dst_relpath='B2', replaces_rev=-1)
  move(src_relpath='A', src_rev=100, dst_relpath='A2', replaces_rev=-1)

So these moves are not parallelizable with this implementation.  (Is that implementation wrong?)

Ev2 also documents (as the first Driving Order Restriction) that there must be an alter_directory call for the parent of moved-away node 'A/B'.  What does this look like?

  alter_dir('A', ...)

or

  alter_dir('A2', ...)

?  Can the alter_dir come before or after the move of 'A' to 'A2'?  Is the path it references 'A' in either case, or 'A2' in either case, or 'A' if it comes before the move and 'A2' if it comes after the move?

Can we start with a clear consensus of whether we're trying to deliver a sequential or a parallel editor?

- Julian

[1] For example, email subject "Re: Ev2 -- Driving Order Restrictions" from Julian Foad on 2012-07-18, <http://svn.haxx.se/dev/archive-2012-07/0247.shtml>.

[2] 'move-tracking-1' branch, <http://svn.apache.org/repos/asf/subversion/branches/move-tracking-1/>.

[3] Wiki page 'MoveDev/MoveDev', <https://wiki.apache.org/subversion/MoveDev/MoveDev>.

--
Join WANdisco's free daily demo sessions on Scaling Subversion for the Enterprise
<http://www.wandisco.com/training/webinars>