For the record, to make it easier to understand our current position in retrospect, I'll try to summarize our findings about the 'rotate' operation so far.
We started with a requirement:
* Represent with 'true moves' any combination of moves that can already be represented using the copy-and-delete model in Ev1.
We assumed some constraints:
* A sequential model with operations including 'move' and 'rotate'.
* Don't touch a path more than once.
* Don't use temporary names/paths.
We found:
* Examples with no solution that fits the constraints.
But:
* We did not define 'rotate'.
* We did not define 'touch'.
* We did not define 'path' in the context of 'touch a path'.
* We have only hinted at the rationale for these constraints.
== Definition of Rotate ==
Let's now try to be somewhat rigorous.
I
think most of us have been assuming a definition something like this:
'rotate A B ...' means to move the subtree found at path A to path B,
and the subtree found at path B to path ..., and the subtree found at
path ... to path A, in any way that produces the same result as if those
moves were performed in parallel.
That
definition works where none of the paths is an ancestor of another.
Then, the destination path of each of these moves is, by definition,
occupied before and after the rotate but available as a destination path
for one of the moves within the rotation.
Where one path is an ancestor of another, we have to deal with the special child name 'B' in this example:
"A" | => "A" |
(A) (B)
"B" | "B" |
(B) (A)
The case where node (B) has no child named "B" is easy:
"A" | => "A" |
(A) (B)
"B" | \ "B" | \
(B) [...] (A) [(B)'s original children]
| |
| [(A)'s original children minus the one named "B"]
|
[(B)'s original children do not include any named "B"]
Node (B) moves to path "A", and node (A) moves to path "A/B" where it becomes a child named "B" of node (B).
What
if (B) has a child named "B" already? Two possible options are the
rotation is not allowed or the child gets deleted and replaced. These
options both impose an additional ordering constraint: if we want to
keep that node and move it to somewhere else, we have to do it *before*
this rotation. But there are cases where we cannot do that. Perhaps
the simplest is swapping 'A' with 'A/B' while keeping 'A/B/B' in place:
"A" | -- -> "A" |
(A) \/ (B)
"B" | /\ "B" |
(B) -- -> (A)
"B" | "B" |
(B2) -----> (B2)
Note
that node (B2) needs to be 'moved' although it remains at the same
absolute path, because our definition of 'move' says that it would
otherwise go with its parent. In this case, we cannot move A/B/B before
the rotate because it would need to go to A/B which is already
occupied. If we try to do it after the rotate, we find it has already
been deleted and replaced, as explained in the previous paragraph.
Thus the model does not satify the constraints.
== Rotate Without Children ==
There
is alternatively a completely different definition of rotate: move the
nodes themselves but leave their children behind. That is, when the
directory object *A* (initially at path 'A') moves to path 'B', let it
then have the children that the directory object *B* (initially at path
'B') initially had. That definition is sometimes used in graph theory,
although usually expressed in more primitive 'add' and 'delete'
operations
rather than 'move'. I think *that* is the definition with which one
can express any rearrangement as a sequence of in-place rotations and
moves.
I don't think we want to define rotate as leaving the children behind,
as it feels like a bad fit for the rest Subversion's model.
However,
from a theoretical perspective it is sufficient, sinceit is fairly easy
to see that any rotation with children can be expressed in terms of
rotation without children and moves. (For each child name that exists
in all N top nodes, we need one N-way rotation with children (which can
be recursively decomposed); and for each child name that exists in only M
< N of the top nodes, we needaseries of M moves.)
==
Does the summary above sound right?
I agree that expressing move sources in terms of the initial state is the most appealing option. I haven't totally ruled out the possibility of relaxing one of the other constraints instead. And I want to examine the destination path ordering a bit more closely as well.
In a separate email I also want to study the precise intent of the "Once" rule. That affects how we deal with destination paths.
- Julian
Received on 2013-06-27 19:43:12 CEST