You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Julian Foad <ju...@btopenworld.com> on 2013/09/02 15:06:19 UTC
Re: Move Tracking in the Update Editor
Philip Martin wrote:
>> On 30.08.2013 17:18, Julian Foad wrote:
>>> The client *does* need to know that B is in fact being moved to C, so
>>> that it can offer to transfer my local modifications from B to C.
>
> Allowing multiple moves to the same destination doesn't really fit with
> Ev2 but I can imagine an enhanced Ev1 editor drive that does
>
> move away A
> move to C (original A)
> del A
> move away B
> move to C (original B)
> del B
> add C
>
> The deletes lead to tree-conflicts on A and B due to local mods. The
> add creates a pristine C with no local mods. The user resolves the
> tree-conflicts post-update and gets to choose which local mods are
> merged to C, possibly both but one before the other, which may in turn
> raise text/prop/tree-conflicts on C.
This is good as far as local mods are concerned. The decision of how to combine A and B, or raise a conflict, is left to the WC client code as it should be, and sufficient information is provided about the nature of the changes.
Functionally, this would work as you've shown. Regarding updating the base tree, however, note that the plain "add" in Ev1 is a node-by-node add of the whole subtree, which could be arbitrarily large. For performance, we must not use a plain add, as a move should be designed to execute in O(1) time.[1]
So, one of the base trees (at A or B) should be deleted, while the other should be moved over to 'C' and updated. The edit producer must therefore make a decision between A and B, and send either
[move-info...]
del A // but WC shall not delete the base tree
del B
add C (copy-from A@10) // WC shall move the base tree from A
modify... C/... // diff A@10:C@30
or
[move-info...]
del A
del B // but WC shall not delete the base tree
add C (copy-from B@20) // WC shall move the base tree from B
modify... C/... // diff B@20:C@30
(The ideal choice of which base-tree to move would be the one with the smaller delta to C@30, but that is hard to determine efficiently. The one with the closer revision number, in this case B, would often be a good choice. However, each of A and B could be a mixed-rev subtree. A good choosing algorithm is far from obvious. That this problem exists at all might be a clue that something deeper is wrong.)
But notice how we're really trying to send a combination of two different messages:
* The incoming logical change, that must be merged with any local mods, is:
- mv(A,C) && modify-tree(diff(A10:C30))
- mv(B,C) && modify-tree(diff(B20:C30))
* To produce the new base tree, one reasonably efficient way is:
- rm(A)
- mv(B,C)
- modify-tree(C, diff(B20:C30))
What we've been striving for above is a kind of hybrid of those two messages.
But let's try to take a step back and look at how we got into this surprisingly ugly case in the first place. The real problem stems from an "impedance mismatch" between the path-centric semantics of the existing WC and the line-of-history semantics that "moves" introduces.
Why do we start off with the expectation that this update (A@10 and B@20 -> C@30) should resolve smoothly into C@30? Because, in our old-fashioned thinking, this was a "normal" mixed-revision WC, and any "normal" WC should update smoothly. But what if we instead started off with this WC (and the same repository):
old_B->A@10
B@20
Then we would say that 'old_B' is 'switched' and we would not expect an update to bring this WC to contain just a child 'C'. We might expect the child named 'old_B' to be deleted (if we're still clinging to the old copy-and-delete ideas about how a move should be handled), or in a move-aware world we might expect 'old_B' to remain present but end up pointing at '^/C@30'.
So, back to the original example, I'm thinking that the child 'A@10' should be treated as a switched child. In a move-aware world, that child should not be found in the WC at all at the same time as 'B@20' unless somebody did a deliberate kind of move-defeating update.
But the WC doesn't know 'A@10' and 'B@20' are the same repository node. The WC doesn't know about node-ids or node-history relationships. This is the problem. Maybe the WC needs to know.
If the WC doesn't know about node-id relationships, then it cannot prevent the following silly situations from arising:
(1) Start from:
A@10
B@20
Then move A to B/A, and try to commit. The commit will fail because
you cannot move the same node into a child of itself. The detection
occurs only at commit time, where the system knows about node ids,
rather than at the time the invalid operation was performed.
(2) Start from:
A@10
B@20
Then modify A, and modify B, and try to commit. The commit will fail
because the two changes to the same repository node conflict. The WC
contains logic to detect this kind of problem before commit in the
specific case where a switched WC node is pointing to the same URL as
another node, but it does not know how to detect when two WC paths
pointing to *different* URLs are in fact pointing to the same repository node.
I think the answer is that in order to make a properly move-aware system, the WC needs to know about node-id relationships [2].
It may be advantageous to come up with an implementation plan whereby move-awareness is introduced first to the repository side, with just enough support in the WC to make typical move scenarios work much better than they do today, and then as a second phase extend the WC to know about node-id relationships and complete the WC-side awareness (so that scenarios like the above commit-time failures are instead detected within the WC, and whatever else goes along with that).
- Julian
[1] The current WC DB schema requires O(nodes in subtree) time for a
move internally, but that's an implementation detail and is often not
the dominant factor.
[2] It could either know the actual node-copy-ids, or just know which pairs of nodes have the same node-copy-id; either would suffice.
Re: Move Tracking in the Update Editor
Posted by Philip Martin <ph...@wandisco.com>.
Julian Foad <ju...@btopenworld.com> writes:
> Philip Martin wrote:
>
>> A current Ev1 drive would be:
>>
>> delete A
>> open B
>> change_prop B
>> close B
>
> Right. Note that here the changes in B are expressed relative to the
> pre-existing 'B' base state.
>
>> For the Ev1+ drive we add move and drop the "delete A" and "open
>> B":
>>
>> move away A id=1
>> move here id=1 B
>> change prop B
>> close B
>
> Well, now, are you thinking that the "move here" operation just
> conveys a semantic intent but does not actually do anything to B, and
> then editor expresses the necessary changes in B relative to the
> existing base state at path B (^/B@20); or that the "move here"
> executes a move (or copy) of the base state in the WC and expresses
> the changes relative to that state (^/A@10)? It matters -- they're
> different sets of changes.
For the update editor it would be best if the B changes were based on
B@20 rather than A@10. I don't think the commit editor has to handle
this case since it always starts with a single revision and the move
source always has to be identical to HEAD.
We start with
base A@10, working file/dir A' with mods
base B@20, working file/dir B' with mods
We update to r30 and receive a move
move away A, id=1
move here id=1, B
change B, ref B@20
close B
The move away raises a tree-conflict on A due to local mods, and copies
A@10 into a working node and removes the base A@10. We can still
identify the local mods by comparing the working A@10 and A'.
The move here actions depend on whether B is a directory or a file.
For a directory the move here causes B to become B@30/incomplete. At
this stage we can still identify the local mods because the incomplete
base hasn't received any changes. As changes arrive they have to be
merged with the local mods B' possibly causing a conflict. After
receiving all the changes the close causes the base to be marked B@30
complete. There may be a conflict.
For a file the move here doesn't change wc.db, the text/property changes
accumulate until close. At close we create a workqueue item to merge
the changes, possibly raising a conflict, and update the base to B@30.
The user can then choose to resolve the tree-conflict on A by merging
the A@20-A' diff into B'.
>> However if B did not exist in the initial working copy the Ev1 drive
>> would be different:
>>
>> delete A
>> add B
>> change_prop B
>> close B
>
> Agreed.
>
>> but with Ev1+ we would get the same sequence. So it appears that "move
>> here" is somehow replacing both open and add. The driver can
>> distinguish these cases and I think it should be telling the receiver.
In this case the B changes have to be based on A@10.
move away A, id=1
move here id=1, B
change B, ref A@10
close B
The driver can distinguish these two cases because it has been told
whether or not B@20 is present. I don't know whether we need to have
the driver explicitly communicate it to the receiver, as with the
current add/open.
Another case is A-to-B-to-C:
We start with
base A@10, working A' file/dir with mods
base B@20, working B' file/dir with mods
We update to r30 and receive two moves:
move away A, id=1
move here id=1, C
change C
close C
move away B, id=2
move here id=2, C
close C
Here the driver chooses to move one of A or B first, I've picked A.
After the first move here the driver sends changes based on A@10 since
there is no previous C. For the second move there is already a C@30 and
the driver has no changes to send. The driver knows all this.
For the user there will be tree-conflicts on A and B, there will be
working nodes A@10 and B@20, and the local mods can be determined by
comparing A@10-A' and B@20-B'.
--
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*
Re: Move Tracking in the Update Editor
Posted by Julian Foad <ju...@btopenworld.com>.
Philip Martin wrote:
> Julian Foad <ju...@btopenworld.com> writes:
>> Philip Martin wrote:
>>> There is a related issue with mixed-revision working copies. Suppose A
>>> gets moved to B in some commit. A mixed-revision working copy could
>>> contain both A and B so what does the update that includes that commit
>>> do? I suppose the server still sends some sort of "move A B" operation
>>
>> Yes. That's this scenario:
>>
>> <https://wiki.apache.org/subversion/MoveDev/MoveTrackingUpdateEditor#One_Move.2C_One_Non-Move>.
>>
>> WC: (A@10, B@20); repo: (r10: mkdir A; r20: mv A B)
>> Update to r20; A moves to B, and also the existing B is updated.
Oops, that should be update to r30, and assume that there are changes in each commit as well as the move, because I want to demonstrate that there are two different sets of incoming changes when we update.
>> and the steps would be:
>>
>> move away A; move to B (original A)
>> delete B # move-away
>> add B (copy-from ... A) # move-here: it conflicts
>
> Not sure I follow that, we don't want to delete B as it may have local
> mods and the final B is the same node so those mods should be preserved.
Notation. I was using the notation of sending the move info in a separate prefix and then using the existing "delete" and "add-with-copy" instructions to actually execute the "move-away" and "move-here" operations respectively.
Nevertheless, you bring up a good problem. I agree "we" (the client) quite likely do not want to delete B in such a case; the most likely conflict resolution we'd choose would be to merge the local mods from A into those in B. But I was trying to envision an edit driver in the server that does not make that decision but rather sends commands for each of the two original paths separately and lets the receiver (client) decide how to handle the conflict.
However, I see the problem with that. There is no sane way for the driver to describe both the move from A to B and the update to the original B in the same edit drive.
Switching to Ev1.5 notation with "move-away" and "move-here" as first class operations, as described in <http://wiki.apache.org/subversion/MoveDev/Ev15MovesDesign#Specification>, the move from A to B would be:
rename(A,B)
[edits in B, relative to original *A*]
close-directory(B)
and the update to the original B would be:
open-directory(B)
[edits in B, relative to original *B*]
close-directory(B)
I suppose the edit driver *could* just send both sets of instructions, one after the other, but that's pretty severely overloading the editor definition. It likely would not play nicely with lazy/late closing of the directories, which I think we do these days.
The alternative is for the merging (and conflict resolution?) to happen earlier. Is that feasible? In the server where it receives a report of the WC base state and drives the editor, perhaps?
> A current Ev1 drive would be:
>
> delete A
> open B
> change_prop B
> close B
Right. Note that here the changes in B are expressed relative to the pre-existing 'B' base state.
> For the Ev1+ drive we add move and drop the "delete A" and "open
> B":
>
> move away A id=1
> move here id=1 B
> change prop B
> close B
Well, now, are you thinking that the "move here" operation just conveys a semantic intent but does not actually do anything to B, and then editor expresses the necessary changes in B relative to the existing base state at path B (^/B@20); or that the "move here" executes a move (or copy) of the base state in the WC and expresses the changes relative to that state (^/A@10)? It matters -- they're different sets of changes.
> However if B did not exist in the initial working copy the Ev1 drive
> would be different:
>
> delete A
> add B
> change_prop B
> close B
Agreed.
> but with Ev1+ we would get the same sequence. So it appears that "move
> here" is somehow replacing both open and add. The driver can
> distinguish these cases and I think it should be telling the receiver.
My definition in the Wiki has "move-here" meaning to actually move the referenced base state to the target path, and any following edits will be based on that new state.
(I can't usefully respond to the remainder below until we get more precise in our notation.)
- Julian
>>> but we may want the server to tell the client that B is not being
>>> replaced.
>>
>> That happens naturally. If B is being replaced by the moved A:
>>
>> WC: (A@10, B@10); repo: (r10: mkdir A B; r20: delete B; mv A B)
>> Update to r20; A moves to B, replacing the previous B.
>>
>> then the server would include an additional "delete A" step:
>>
>> move away A; move to B (original A)
>> delete B # move-away
>> delete A
>> add B (copy-from ... A) # move-here: it conflicts
>
> There are 3 cases:
>
> 1) A moved to B where B does not exist
> 2) A moved to B where B exists and is the same node
> 3) A moved to B where B exists but is a different node
>
> 1 and 2 are the cases above. For 3 the current Ev1 drive would be:
>
> delete A
> delete B
> add B
> change prop B
> close B
>
> I suppose the Ev1+ drive might be something like:
>
> move away A id=1
> delete B
> move here id=1 B
> change prop B
> close B
>
> In this case local mods to B would cause a tree-conflict due to the
> delete/replace.
>
> It might be interesting to see how Ev2 would handle these 3 cases.
>
> 1) A moved to B where B does not exist
>
> alter dir ., children=A,B
> move A B, replaces_rev=-1
> alter B
>
> 2) A moved to B where B exists and is the same node
>
> alter dir ., children=A,B
> move A B, replaces_rev=-1
> alter B
>
> 3) A moved to B where B exists and is a different node
>
> alter dir ., children=A,B
> move A B, replaces_rev=N
> alter B
>
> Ev2 distinguishes between add and replace via the replaces_rev flag but
> as with Ev1+ the driver knows about the difference between 1 and 2 but
> doesn't communicate it to the receiver.
Re: Move Tracking in the Update Editor
Posted by Philip Martin <ph...@wandisco.com>.
Julian Foad <ju...@btopenworld.com> writes:
> Philip Martin wrote:
>> There is a related issue with mixed-revision working copies. Suppose A
>> gets moved to B in some commit. A mixed-revision working copy could
>> contain both A and B so what does the update that includes that commit
>> do? I suppose the server still sends some sort of "move A B" operation
>
> Yes. That's this scenario:
> <https://wiki.apache.org/subversion/MoveDev/MoveTrackingUpdateEditor#One_Move.2C_One_Non-Move>.
>
> WC: (A@10, B@20); repo: (r10: mkdir A; r20: mv A B)
> Update to r20; A moves to B, and also the existing B is updated.
>
> and the steps would be:
>
> move away A; move to B (original A)
> delete B # move-away
> add B (copy-from ... A) # move-here: it conflicts
Not sure I follow that, we don't want to delete B as it may have local
mods and the final B is the same node so those mods should be preserved.
A current Ev1 drive would be:
delete A
open B
change_prop B
close B
For the Ev1+ drive we add move and drop the "delete A" and "open B":
move away A id=1
move here id=1 B
change prop B
close B
However if B did not exist in the initial working copy the Ev1 drive
would be different:
delete A
add B
change_prop B
close B
but with Ev1+ we would get the same sequence. So it appears that "move
here" is somehow replacing both open and add. The driver can
distinguish these cases and I think it should be telling the receiver.
>> but we may want the server to tell the client that B is not being
>> replaced.
>
> That happens naturally. If B is being replaced by the moved A:
>
> WC: (A@10, B@10); repo: (r10: mkdir A B; r20: delete B; mv A B)
> Update to r20; A moves to B, replacing the previous B.
>
> then the server would include an additional "delete A" step:
>
> move away A; move to B (original A)
> delete B # move-away
> delete A
> add B (copy-from ... A) # move-here: it conflicts
There are 3 cases:
1) A moved to B where B does not exist
2) A moved to B where B exists and is the same node
3) A moved to B where B exists but is a different node
1 and 2 are the cases above. For 3 the current Ev1 drive would be:
delete A
delete B
add B
change prop B
close B
I suppose the Ev1+ drive might be something like:
move away A id=1
delete B
move here id=1 B
change prop B
close B
In this case local mods to B would cause a tree-conflict due to the
delete/replace.
It might be interesting to see how Ev2 would handle these 3 cases.
1) A moved to B where B does not exist
alter dir ., children=A,B
move A B, replaces_rev=-1
alter B
2) A moved to B where B exists and is the same node
alter dir ., children=A,B
move A B, replaces_rev=-1
alter B
3) A moved to B where B exists and is a different node
alter dir ., children=A,B
move A B, replaces_rev=N
alter B
Ev2 distinguishes between add and replace via the replaces_rev flag but
as with Ev1+ the driver knows about the difference between 1 and 2 but
doesn't communicate it to the receiver.
--
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*
Re: Move Tracking in the Update Editor
Posted by Julian Foad <ju...@btopenworld.com>.
Philip Martin wrote:
> Julian Foad <ju...@btopenworld.com> writes:
>> Julian Foad wrote:
>>> Philip Martin wrote:
>>>> [...] I can imagine an enhanced Ev1 editor drive that does
>>>>
>>>> move away A
>>>> move to C (original A)
>>>> del A
>>>> move away B
>>>> move to C (original B)
>>>> del B
>>>> add C
>>>>
>>>> The deletes lead to tree-conflicts on A and B due to local mods. The
>>>> add creates a pristine C with no local mods. The user resolves the
>>>> tree-conflicts post-update and gets to choose which local mods are
>>>> merged to C, possibly both but one before the other, which may in
>>>> turn raise text/prop/tree-conflicts on C.
>>>
>>> This is good as far as local mods are concerned. The decision of how
>>> to combine A and B, or raise a conflict, is left to the WC client code
>>> as it should be, and sufficient information is provided about the
>>> nature of the changes.
[...]
> There is a related issue with mixed-revision working copies. Suppose A
> gets moved to B in some commit. A mixed-revision working copy could
> contain both A and B so what does the update that includes that commit
> do? I suppose the server still sends some sort of "move A B" operation
Yes. That's this scenario: <https://wiki.apache.org/subversion/MoveDev/MoveTrackingUpdateEditor#One_Move.2C_One_Non-Move>.
WC: (A@10, B@20); repo: (r10: mkdir A; r20: mv A B)
Update to r20; A moves to B, and also the existing B is updated.
and the steps would be:
move away A; move to B (original A)
delete B # move-away
add B (copy-from ... A) # move-here: it conflicts
> but we may want the server to tell the client that B is not being
> replaced.
That happens naturally. If B is being replaced by the moved A:
WC: (A@10, B@10); repo: (r10: mkdir A B; r20: delete B; mv A B)
Update to r20; A moves to B, replacing the previous B.
then the server would include an additional "delete A" step:
move away A; move to B (original A)
delete B # move-away
delete A
add B (copy-from ... A) # move-here: it conflicts
- Julian
Re: Move Tracking in the Update Editor
Posted by Philip Martin <ph...@wandisco.com>.
Julian Foad <ju...@btopenworld.com> writes:
> Julian Foad wrote:
>
>> Philip Martin wrote:
>>> [...] I can imagine an enhanced Ev1 editor drive that does
>>>
>>> move away A
>>> move to C (original A)
>>> del A
>>> move away B
>>> move to C (original B)
>>> del B
>>> add C
>>>
>>> The deletes lead to tree-conflicts on A and B due to local mods. The
>>> add creates a pristine C with no local mods. The user resolves the
>>> tree-conflicts post-update and gets to choose which local mods are
>>> merged to C, possibly both but one before the other, which may in turn
>>> raise text/prop/tree-conflicts on C.
>>
>> This is good as far as local mods are concerned. The decision of how to combine
>> A and B, or raise a conflict, is left to the WC client code as it should be, and
>> sufficient information is provided about the nature of the changes.
>>
>> Functionally, this would work as you've shown. Regarding updating the base
>> tree, however, note that the plain "add" in Ev1 is a node-by-node add
>> of the whole subtree, which could be arbitrarily large. For performance, we
>> must not use a plain add, as a move should be designed to execute in O(1)
>> time. [...]
>
> Philip pointed out to me that this would still be an improvement over
> what we have today. If we're going to get anything into a release
> cycle it must be broken down into manageable stages, so perhaps this
> is a good place to draw the line for a first stage.
>
> I'm fairly well persuaded by this view.
There is a related issue with mixed-revision working copies. Suppose A
gets moved to B in some commit. A mixed-revision working copy could
contain both A and B so what does the update that includes that commit
do? I suppose the server still sends some sort of "move A B" operation
but we may want the server to tell the client that B is not being
replaced.
--
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*
Re: Move Tracking in the Update Editor
Posted by Julian Foad <ju...@btopenworld.com>.
Julian Foad wrote:
> Philip Martin wrote:
>> [...] I can imagine an enhanced Ev1 editor drive that does
>>
>> move away A
>> move to C (original A)
>> del A
>> move away B
>> move to C (original B)
>> del B
>> add C
>>
>> The deletes lead to tree-conflicts on A and B due to local mods. The
>> add creates a pristine C with no local mods. The user resolves the
>> tree-conflicts post-update and gets to choose which local mods are
>> merged to C, possibly both but one before the other, which may in turn
>> raise text/prop/tree-conflicts on C.
>
> This is good as far as local mods are concerned. The decision of how to combine
> A and B, or raise a conflict, is left to the WC client code as it should be, and
> sufficient information is provided about the nature of the changes.
>
> Functionally, this would work as you've shown. Regarding updating the base
> tree, however, note that the plain "add" in Ev1 is a node-by-node add
> of the whole subtree, which could be arbitrarily large. For performance, we
> must not use a plain add, as a move should be designed to execute in O(1)
> time. [...]
Philip pointed out to me that this would still be an improvement over what we have today. If we're going to get anything into a release cycle it must be broken down into manageable stages, so perhaps this is a good place to draw the line for a first stage.
I'm fairly well persuaded by this view.
- Julian
> It may be advantageous to come up with an implementation plan whereby
> move-awareness is introduced first to the repository side, with just enough
> support in the WC to make typical move scenarios work much better than they do
> today, and then as a second phase extend the WC to know about node-id
> relationships and complete the WC-side awareness (so that scenarios like the
> above commit-time failures are instead detected within the WC, and whatever else
> goes along with that).
Re: Move Tracking in the Update Editor
Posted by Julian Foad <ju...@btopenworld.com>.
Julian Foad wrote:
> Philip Martin wrote:
>> [...] I can imagine an enhanced Ev1 editor drive that does
>>
>> move away A
>> move to C (original A)
>> del A
>> move away B
>> move to C (original B)
>> del B
>> add C
>>
>> The deletes lead to tree-conflicts on A and B due to local mods. The
>> add creates a pristine C with no local mods. The user resolves the
>> tree-conflicts post-update and gets to choose which local mods are
>> merged to C, possibly both but one before the other, which may in turn
>> raise text/prop/tree-conflicts on C.
>
> This is good as far as local mods are concerned. The decision of how to combine
> A and B, or raise a conflict, is left to the WC client code as it should be, and
> sufficient information is provided about the nature of the changes.
>
> Functionally, this would work as you've shown. Regarding updating the base
> tree, however, note that the plain "add" in Ev1 is a node-by-node add
> of the whole subtree, which could be arbitrarily large. For performance, we
> must not use a plain add, as a move should be designed to execute in O(1)
> time. [...]
Philip pointed out to me that this would still be an improvement over what we have today. If we're going to get anything into a release cycle it must be broken down into manageable stages, so perhaps this is a good place to draw the line for a first stage.
I'm fairly well persuaded by this view.
- Julian
> It may be advantageous to come up with an implementation plan whereby
> move-awareness is introduced first to the repository side, with just enough
> support in the WC to make typical move scenarios work much better than they do
> today, and then as a second phase extend the WC to know about node-id
> relationships and complete the WC-side awareness (so that scenarios like the
> above commit-time failures are instead detected within the WC, and whatever else
> goes along with that).