Adding spec property "setOwnCursor" for Insert/Remove/Split ops
Hi WebODFler, I would like to add a new property to the specs of all insert/remove/split ops: setOwnCursor (or some better name). This property will tell if the cursor of the member which sends the operation should be put after the place/result of the op. Currently this is only done iff the cursor is at the position of the op. But with real OT, where local operations are instantly applied and only then sent to other clients who might have to transform them on conflicts, the transformed operations and positions of cursors can be out-of-sync, breaking the current assumption with UI editing that cursors will always automatically placed behind the places of modification. Example: text:p<cursor memberid="A"><cursor memberid="B"> Both clients A and B type at the same time "a" and "b" and apply it locally, before sending to server/other client: At A: text:p<cursor memberid="B">a<cursor memberid="A"> Unsynced ops: [<insertText pos="0" text="a" memberId="A"/>] At B: text:p<cursor memberid="A">b<cursor memberid="B"> Unsynced ops: [<insertText pos="0" text="b" memberId="B"/>] At server: op stack: [] As this is a case for tiebreaking on conflicting operations, because both insert at the same position and it needs to be decided in which order the insertions will end up in the final document, we assume that * priority is given to ops which are first on the server * priority in this case means insertion will be placed before the other insertion A is quicker with syncing with server: At A: text:p<cursor memberid="B">a<cursor memberid="A"> Unsynced ops: [] At server: op stack: [<insertText pos="0" text="a" memberId="A"/>] Now B tries to sync, but sees that there are conflicting ops, which it first has to resolve locally, by transforming its local unsynced op and the new on the server against each other, so the server op is based on the state of B and the unsynced op is based on the (virtual) state of the server: T(<insertText pos="1" text="b" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/> ) -> (<insertText pos="1" text="b" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/> ) given the tiebreaking rules above. After transformation B then applies the transformed op from the server and sends its own transformed unsynced op to the server At B: text:pa<cursor memberid="A">b<cursor memberid="B"> Unsynced ops: [] At server: op stack: [<insertText pos="0" text="a" memberId="A"/>, <insertText pos="1" text="b" memberId="B"/>] Now A syncs again with the server, fetching the new op. And here we are with the problem: At A the cursor of B is still at the position 0, while the operation says that B inserts at position 1. Still we want to have the cursor of B after the op to be at position 3 (not only for convergence of the 2 clients). I would like to solve that by allowing ops to optionally take the cursor from whereever it was and just move it behind the result of the operation, instead of always only moving it if it is at the position of the operation. This would also allow to explicitely do operations at the current cursor position without moving the cursor, which currently is not possible. Operation creators would specify the cursor movement by setting the new property "setOwnCursor" to "false" or "true". It would be added to all operations where the text structure is changed. Any blockers, counterproposals, comments, icecoffee recipes? Cheers Friedrich -- Friedrich W. H. Kossebau // KO GmbH http://kogmbh.com/legal/
Hi Friedrich, The proposal looks good. Once concern that I did have is that there is potentially not enough flexibility. I'm thinking about table insertion specifically where the desired location of the cursor when inserting a table is actually within the first paragraph in the first cell of the table. There are two potential ways to address this that immediately come to mind: 1. Make the setOwnCursor a little more flexible by allowing specific placement of the cursor at the completion of an operation. As long as the Ops respect the fact that setOwnCursor is RELATIVE to the input position, this should cause no hassles for OT adaption on conflict etc. (e.g., an Op should not set the cursor beyond the bounds of it's known neighbour hood, so for the table, it will insert the cursor within the first paragraph itself). 2. Keep cursor positioning a separate concern from the operation. The expectation here would be that an operation is NOT responsible for managing cursor position, instead, the upper controller (SessionController) is responsible for this. The key advantage of this is that it keeps the notion of cursor positioning entirely in the domain of the SessionController, rather than requiring each OP to find and manage it's own cursor (or even other cursors). I suspect this would help simplify the Ops slightly as they would focus more on doing things to the DOM, and would no longer need to worry about whether insertion is before or after the cursor etc. In the example of a table insertion, approach 2 would generate: OpInsertTable OpMoveCursor (move to first paragraph of new table) I *think* both approaches would work, but I prefer approach 2 as the SessionController seems like the correct place to manage cursor positioning. Especially as more complex OTs are developed :) Cheers, Philip On 17/06/2013, at 8:39 PM, Friedrich W. H. Kossebau wrote:
Hi WebODFler,
I would like to add a new property to the specs of all insert/remove/split ops: setOwnCursor (or some better name). This property will tell if the cursor of the member which sends the operation should be put after the place/result of the op. Currently this is only done iff the cursor is at the position of the op. But with real OT, where local operations are instantly applied and only then sent to other clients who might have to transform them on conflicts, the transformed operations and positions of cursors can be out-of-sync, breaking the current assumption with UI editing that cursors will always automatically placed behind the places of modification.
Example: text:p<cursor memberid="A"><cursor memberid="B"> Both clients A and B type at the same time "a" and "b" and apply it locally, before sending to server/other client: At A: text:p<cursor memberid="B">a<cursor memberid="A"> Unsynced ops: [<insertText pos="0" text="a" memberId="A"/>] At B: text:p<cursor memberid="A">b<cursor memberid="B"> Unsynced ops: [<insertText pos="0" text="b" memberId="B"/>] At server: op stack: [] As this is a case for tiebreaking on conflicting operations, because both insert at the same position and it needs to be decided in which order the insertions will end up in the final document, we assume that * priority is given to ops which are first on the server * priority in this case means insertion will be placed before the other insertion A is quicker with syncing with server: At A: text:p<cursor memberid="B">a<cursor memberid="A"> Unsynced ops: [] At server: op stack: [<insertText pos="0" text="a" memberId="A"/>] Now B tries to sync, but sees that there are conflicting ops, which it first has to resolve locally, by transforming its local unsynced op and the new on the server against each other, so the server op is based on the state of B and the unsynced op is based on the (virtual) state of the server: T(<insertText pos="1" text="b" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/> ) -> (<insertText pos="1" text="b" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/> ) given the tiebreaking rules above. After transformation B then applies the transformed op from the server and sends its own transformed unsynced op to the server At B: text:pa<cursor memberid="A">b<cursor memberid="B"> Unsynced ops: [] At server: op stack: [<insertText pos="0" text="a" memberId="A"/>, <insertText pos="1" text="b" memberId="B"/>] Now A syncs again with the server, fetching the new op. And here we are with the problem: At A the cursor of B is still at the position 0, while the operation says that B inserts at position 1. Still we want to have the cursor of B after the op to be at position 3 (not only for convergence of the 2 clients).
I would like to solve that by allowing ops to optionally take the cursor from whereever it was and just move it behind the result of the operation, instead of always only moving it if it is at the position of the operation. This would also allow to explicitely do operations at the current cursor position without moving the cursor, which currently is not possible.
Operation creators would specify the cursor movement by setting the new property "setOwnCursor" to "false" or "true". It would be added to all operations where the text structure is changed.
Any blockers, counterproposals, comments, icecoffee recipes?
Cheers Friedrich -- Friedrich W. H. Kossebau // KO GmbH http://kogmbh.com/legal/ _______________________________________________ WebODF mailing list WebODF@nlnet.nl https://open.nlnet.nl/mailman/listinfo/webodf
Hi Philip, Am Mittwoch, 19. Juni 2013, 00:34:24 schrieben Sie:
Hi Friedrich,
The proposal looks good.
Once concern that I did have is that there is potentially not enough flexibility. I'm thinking about table insertion specifically where the desired location of the cursor when inserting a table is actually within the first paragraph in the first cell of the table.
There are two potential ways to address this that immediately come to mind:
1. Make the setOwnCursor a little more flexible by allowing specific placement of the cursor at the completion of an operation. As long as the Ops respect the fact that setOwnCursor is RELATIVE to the input position, this should cause no hassles for OT adaption on conflict etc. (e.g., an Op should not set the cursor beyond the bounds of it's known neighbour hood, so for the table, it will insert the cursor within the first paragraph itself).
While for simplicity I would prefer to have a single defined position where the related cursor ends up after insertion (of a table), I do not see any technical reason against having an option where to place it exactly. So no problem to add support for that.
2. Keep cursor positioning a separate concern from the operation. The expectation here would be that an operation is NOT responsible for managing cursor position, instead, the upper controller (SessionController) is responsible for this. The key advantage of this is that it keeps the notion of cursor positioning entirely in the domain of the SessionController, rather than requiring each OP to find and manage it's own cursor (or even other cursors). I suspect this would help simplify the Ops slightly as they would focus more on doing things to the DOM, and would no longer need to worry about whether insertion is before or after the cursor etc.
In the example of a table insertion, approach 2 would generate: OpInsertTable OpMoveCursor (move to first paragraph of new table)
While I would prefer approach 2 as well, due to the less complexity in the semantics of the ops and the work they have to do, it poses me in front of a problem I yet have to solve, i.e. to do proper transformations of the movecursor ops which are intended to put the cursor after the result of the preceding document manipulation. Because I would need to know how the related manipulating op is transformed to also properly adapt the moveCursor op. So this dependency just adds other complexity elsewhere, and here I do not even have a good idea yet. Given the example from my initial email, where both users insert at the first position of an empty document: At A: <insertText pos="0" text="a" memberId="A"/><moveCursor pos="1" memberId="A"/> At B: <insertText pos="0" text="b" memberId="B"/><moveCursor pos="1" memberId="B"/> A first sends to server: Server: <insertText pos="0" text="a" memberId="A"/><moveCursor pos="1" memberId="A"/> Now B tries to sync and has to transform the ops from A and its unsynced own against each other in such a way that the result looks like this when A later fetches the (transformed) ops from B (via the server): A: <insertText pos="0" text="a" memberId="A"/><moveCursor pos="1" memberId="A"/> <insertText pos="1" text="b" memberId="B"/><moveCursor pos="2" memberId="B"/> B: <insertText pos="0" text="b" memberId="B"/><moveCursor pos="1" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/><moveCursor pos="1" memberId="A"/> When transforming a moveCursor op against a insert/remove/split (so position number) changing op, the current transformation logic only changes the position of a moveCursor op by the number of inserted/removed positions before the old position of the moveCursor op. But here it would also depend on the transformation of the preceding document manipulation op, e.g. in the given example the moveCursor op for cursor of member A on client B should stay at position 1 and not be adapted by +1 when transformed against the insertText op of member b at pos 0, because the related insertText op of A was also not adapted by +1, due to "winning" the tiebreaking in whose insertion should end up at position 0. Will think some more about it, just giving a first reply. Cheers Friedrich -- Friedrich W. H. Kossebau // KO GmbH http://kogmbh.com/legal/
Am Mittwoch, 19. Juni 2013, 10:38:13 schrieb Friedrich W. H. Kossebau:
Will think some more about it, just giving a first reply.
Got hinted off-list to infinote protocol, and I could learn that they have two variants per document-modifying op, e.g. <insert/> and <insert-caret/> or <delete/> and <delete-caret/>, where each *-caret variants "additionally places the cursor of the user that made the request". So at least one reference for the "setOwnCursor" property solution :) Cheers Friedrich -- Friedrich W. H. Kossebau // KO GmbH http://kogmbh.com/legal/
Am Montag, 17. Juni 2013, 12:39:46 schrieb Friedrich W. H. Kossebau: [...]
Now B tries to sync, but sees that there are conflicting ops, which it first has to resolve locally, by transforming its local unsynced op and the new on the server against each other, so the server op is based on the state of B and the unsynced op is based on the (virtual) state of the server: T(<insertText pos="1" text="b" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/> ) -> (<insertText pos="1" text="b" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/> ) given the tiebreaking rules above.
Bah, c&p error. In case you read this part and wondered, this should have been: T(<insertText pos="0" text="b" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/> ) -> (<insertText pos="1" text="b" memberId="B"/>, <insertText pos="0" text="a" memberId="A"/> ) Cheers Friedrich -- Friedrich W. H. Kossebau // KO GmbH http://kogmbh.com/legal/
On 06/17/13 12:39, Friedrich W. H. Kossebau wrote:
Hi WebODFler,
I would like to add a new property to the specs of all insert/remove/split ops: setOwnCursor (or some better name). This property will tell if the cursor of the member which sends the operation should be put after the place/result of the op. Currently this is only done iff the cursor is at the position of the op. But with real OT, where local operations are instantly applied and only then sent to other clients who might have to transform them on conflicts, the transformed operations and positions of cursors can be out-of-sync, breaking the current assumption with UI editing that cursors will always automatically placed behind the places of modification.
Ok, I wrote a long email with different scenarios and orders of operations. I have discarded this mail because I came to the conclusion that the problem is not with the occurrence of an out-of-sync with an assumption of how cursors should move upon inserting or deleting text. Here is the original example. I have added a | to show the insertion point. text:p|<cursor memberid="A"/><cursor memberid="B"/> The two participants each insert a character locally: text:p|a|<cursor memberid="A"/><cursor memberid="B"/> text:p|b|<cursor memberid="A"/><cursor memberid="B"/> They do this by sending: <insertText pos="0" text="a" memberId="A"/> <insertText pos="0" text="b" memberId="B"/> This is sent to the server and either 'a' can get there first or 'b' can get there first: text:p|a|b|<cursor memberid="A"/><cursor memberid="B"/> text:p|b|a|<cursor memberid="A"/><cursor memberid="B"/> There is no need to send any command to move a cursor. The two results I show above is not in conformance with "the current assumption with UI editing that cursors will always automatically placed behind the places of modification" and that is fine. The cursor is not actively placed, it just goes with the flow. Sure the cursor for A might not be directly behind the character 'a' or the cursor for B might not be directly behind the character 'b' when these participants start typing on the same location. I do not think this is a problem. The original mail claimed that the result of A typing an 'a' would be text:p<cursor memberid="B"/>a<cursor memberid="A"/> but this is not true, the result should be: text:pa<cursor memberid="A"/><cursor memberid="B"/> because the text should be inserted before the insertion point. I hope this clarifies things. Cheers, Jos
Am Samstag, 22. Juni 2013, 00:10:40 schrieb Jos van den Oever:
On 06/17/13 12:39, Friedrich W. H. Kossebau wrote:
Hi WebODFler,
I would like to add a new property to the specs of all insert/remove/split ops: setOwnCursor (or some better name). This property will tell if the cursor of the member which sends the operation should be put after the place/result of the op. Currently this is only done iff the cursor is at the position of the op. But with real OT, where local operations are instantly applied and only then sent to other clients who might have to transform them on conflicts, the transformed operations and positions of cursors can be out-of-sync, breaking the current assumption with UI editing that cursors will always automatically placed behind the places of modification.
Ok, I wrote a long email with different scenarios and orders of operations. I have discarded this mail because I came to the conclusion that the problem is not with the occurrence of an out-of-sync with an assumption of how cursors should move upon inserting or deleting text.
Here is the original example. I have added a | to show the insertion point. text:p|<cursor memberid="A"/><cursor memberid="B"/>
Why do you put the insertion point before the cursors? How would you argument for this ordering? Why this way do you bound the cursors more to the following and less to the preceding content?
The two participants each insert a character locally: text:p|a|<cursor memberid="A"/><cursor memberid="B"/> text:p|b|<cursor memberid="A"/><cursor memberid="B"/> They do this by sending: <insertText pos="0" text="a" memberId="A"/> <insertText pos="0" text="b" memberId="B"/>
This is sent to the server and either 'a' can get there first or 'b' can get there first: text:p|a|b|<cursor memberid="A"/><cursor memberid="B"/> text:p|b|a|<cursor memberid="A"/><cursor memberid="B"/>
There is no need to send any command to move a cursor.
The two results I show above is not in conformance with "the current assumption with UI editing that cursors will always automatically placed behind the places of modification" and that is fine. The cursor is not actively placed, it just goes with the flow.
Sure the cursor for A might not be directly behind the character 'a' or the cursor for B might not be directly behind the character 'b' when these participants start typing on the same location. I do not think this is a problem.
It is a problem in this case: two clients are connected to the server, thus syncing in real-time, and both users start typing at the same time with their cursors at the same position (like an empty document). Their input will be be interleaved (because the positions of their cursors will not be separated, unless one uses cursor move command), which is surely not what people like and expect. At least this is the reasoning why we (as in: those who talked about that last time) decided to only move the cursor of the member doing the insertion behind the inserted object and leave any other cursors at the point of the insertion. And this is also the behaviour like it is implemented currently.
The original mail claimed that the result of A typing an 'a' would be text:p<cursor memberid="B"/>a<cursor memberid="A"/> but this is not true, the result should be: text:pa<cursor memberid="A"/><cursor memberid="B"/> because the text should be inserted before the insertion point.
Should it? What would be the reasoning? What defines "truth" here? :) For reference, Etherpad, Gobby (infinote protocol) & Google Docs all only move the cursor of the editing person behind the insertion and leave any other cursors at the insertion point in place.
I hope this clarifies things.
Clarifies at least we need to document our (previous/future) decisions and for that add a design document to webodf :) IMHO we should rather stick with the current implementation, where only the cursor of the editing member is placed behind inserted objects (or alternatively also inside, like the first cell of an inserted table). Not only for consistency with the systems mentioned above, but also for this reasoning: The flow in the structure which is edited here (text document) is from beginning towards end, and people usually change this structure by appending more content to other content, rather than prepending. Like I type all the letters to this email by appending, yes, really do :) So if one places a cursor somewhere the cursor more often is put _behind_ content than put _before_ content. Thus on insertion at that point the non-involved cursors should stick to the previous content. And it would also unbreak the interleaved input issue, but that is related to this argueing. Downside is some more complicated code and operations, sure. But well... Other opinions on this? Cheers Friedrich -- Friedrich W. H. Kossebau // KO GmbH http://kogmbh.com/legal/
On 06/24/13 12:19, Friedrich W. H. Kossebau wrote:
Am Samstag, 22. Juni 2013, 00:10:40 schrieb Jos van den Oever:
On 06/17/13 12:39, Friedrich W. H. Kossebau wrote:
Hi WebODFler,
I would like to add a new property to the specs of all insert/remove/split ops: setOwnCursor (or some better name). This property will tell if the cursor of the member which sends the operation should be put after the place/result of the op. Currently this is only done iff the cursor is at the position of the op. But with real OT, where local operations are instantly applied and only then sent to other clients who might have to transform them on conflicts, the transformed operations and positions of cursors can be out-of-sync, breaking the current assumption with UI editing that cursors will always automatically placed behind the places of modification.
Ok, I wrote a long email with different scenarios and orders of operations. I have discarded this mail because I came to the conclusion that the problem is not with the occurrence of an out-of-sync with an assumption of how cursors should move upon inserting or deleting text.
Here is the original example. I have added a | to show the insertion point. text:p|<cursor memberid="A"/><cursor memberid="B"/>
Why do you put the insertion point before the cursors? How would you argument for this ordering? Why this way do you bound the cursors more to the following and less to the preceding content?
A quick reply to only one question. I did read the rest of the mail. (I"m on holiday the whole week and shoudnt even be reading my mail.) The reason I put the insertion point where I put it, is that that is where README_cursorpositions.txt tells me to put it. That document describes cursor positions. Now, <cursor/> is ignored in that reasoning normally, but if it werent, youd get 1) text:p|<cursor memberid="A"/><cursor memberid="B"/> and 2) text:pa|<cursor memberid="A"/><cursor memberid="B"/> Why? because README_cursorpositions.txt says: 1) put | at start of empty paragraph, so before cursor 2) put | directly to right of a character Please consider the solution I wrote initially. It is simple and consistent with our cursor position documentation. Cheers, Jos
Am Montag, 24. Juni 2013, 12:27:46 schrieb Jos van den Oever:
On 06/24/13 12:19, Friedrich W. H. Kossebau wrote:
Am Samstag, 22. Juni 2013, 00:10:40 schrieb Jos van den Oever:
On 06/17/13 12:39, Friedrich W. H. Kossebau wrote:
Hi WebODFler,
I would like to add a new property to the specs of all insert/remove/split ops: setOwnCursor (or some better name). This property will tell if the cursor of the member which sends the operation should be put after the place/result of the op. Currently this is only done iff the cursor is at the position of the op. But with real OT, where local operations are instantly applied and only then sent to other clients who might have to transform them on conflicts, the transformed operations and positions of cursors can be out-of-sync, breaking the current assumption with UI editing that cursors will always automatically placed behind the places of modification.
Ok, I wrote a long email with different scenarios and orders of operations. I have discarded this mail because I came to the conclusion that the problem is not with the occurrence of an out-of-sync with an assumption of how cursors should move upon inserting or deleting text.
Here is the original example. I have added a | to show the insertion point.
text:p|<cursor memberid="A"/><cursor memberid="B"/>
Why do you put the insertion point before the cursors? How would you argument for this ordering? Why this way do you bound the cursors more to the following and less to the preceding content?
A quick reply to only one question. I did read the rest of the mail. (I"m on holiday the whole week and shoudnt even be reading my mail.)
Thanks for the quick reply. Though it was not my intention to pull you out of vacation now, was expecting your reply next week. Was rather hoping for comments from the rest here for now :) And this reply again is only expecting a reply from Jos next week, so resist to read now, Jos (please don't make me feel to spoil your free time) :) Everyone else, please do. The reading.
The reason I put the insertion point where I put it, is that that is where README_cursorpositions.txt tells me to put it. That document describes cursor positions. Now, <cursor/> is ignored in that reasoning normally, but if it werent, youd get 1) text:p|<cursor memberid="A"/><cursor memberid="B"/> and 2) text:pa|<cursor memberid="A"/><cursor memberid="B"/> Why? because README_cursorpositions.txt says: 1) put | at start of empty paragraph, so before cursor 2) put | directly to right of a character
Hm, that seems cyclic reasoning in my after-lunch brain-state: "if it werent [ignored]" it would be|<cursor memberid="A"/>, because "1) put | at start of empty paragraph, so before cursor." But isn't | exactly the place where all the cursors hang around? Like README_cursorpositions.txt says: "The possible cursor positions are indicated with |". And while we surely all imply that cursor position is also the insert position, it does not say something about the inner order at that position. Nor is the order given of all the cursors at that position, neither is it said that inside that position there is a sub-position for inserting, right before the sub-positions of the cursors. So if that was to be supposed to be expressed in the docs, it needs to be done more explicitely, at least I could not read this there. And still would argue against it. "because it's like that in the spec" does not (yet) hold for me. Worse, for my POV I would rather point out to "it's like that in the code" where only the editing cursor is moved behind the inserted object on paragraph split or text insertion.
Please consider the solution I wrote initially. It is simple and consistent with our cursor position documentation.
I am considering it. But as result also questioning :) While it may be simple (but cannot see the consistence with the docs), there are the reasons for another solution, like given in the other email :/ Will see to find enough stuff else to work on this week so I can postpone any big work on this until you, Jos, are back with full concentration so we can sort out the differences we have here and find common ground. Cheers Friedrich -- Friedrich W. H. Kossebau // KO GmbH http://kogmbh.com/legal/
On 06/24/13 15:35, Friedrich W. H. Kossebau wrote:
And this reply again is only expecting a reply from Jos next week, so resist to read now, Jos (please don't make me feel to spoil your free time) :) I can do that :-)
Cheers, Jos
participants (3)
-
Friedrich W. H. Kossebau
-
Jos van den Oever
-
Philip Peitsch