Changes between Version 5 and Version 6 of AnnotatedObbySession

Timestamp:

08/08/06 15:04:43 (7 years ago)

Author:

armin (IP: 217.227.155.33)

Comment:

Notes about transformations, noop and split operations

AnnotatedObbySession

@@ -123 +123 @@
 This process is called inclusion transformation: We include the effect of the operation "insert a at position 0" (lets call it ins(a@0)) to the operation "insert b at position 1" (ins(b@1)). This resulted in "insert b at position 2" (ins(b@2)). So we have to cache every operation that we sent to the server in some kind of list with the local operation count included. Whenever we get an operation from the server we remove all operations from that list that have a smaller local operation count as the server's remote operation count (because these are operations the server already knows about). If some operations remain, we have to perform an inclusion transformation of every operation that is still in the list with the operation the server sent us before applying it to the document.
 
-TODO: Explain why we also must transform the existing operations against the incoming operation.
+Now, imagine the above scenario the other way around. We send
 
-TODO: Explain possible transformation cases including the need of SplitOperation and NoOperation.
+''obby_document:1 1:record:0:0:ins:2:a''
+
+and get
+
+{{{obby_document:1 1:record:0:0:ins:0:bar}}}
+
+This time, we must include the effect of ins(a@2) into ins(bar@0). Since 'a' was inserted behind 'bar', nothing has to be done. But imagine we now get a second record:
+
+{{{obby_document:1 1:record:1:0:ins:3:baz}}}
+
+The remote operation count is still zero, so when the server wrote 'baz', he did still not get our 'a' and intended to insert 'baz' right behind the 'bar' he inserted beforehand. But when we include the effect of ins(a@2) into ins(baz@3), we get ins(baz@4). So, when the document's initial content was 'foo', we first made 'foao' out of it, then ins(bar@0) is applied resulting in 'barfoao' and after this ins(baz@4), leading to a final content of 'barfbazao'. It is easy to see that this is not what the server intended since it inserted 'baz' right after 'bar' without the 'f' inbetween. So what went wrong here?
+
+So, when the server sent the first record ins(bar@0), we did not transform anything, which was right, because our 'a' has been inserted behind the server's 'bar'. However, this caused the 'a' to move 3 characters forward. So we also should have included the effect of ins(bar@0) into ins(a@2), and not only the other way around. This way, ins(a@2) turns into ins(a@5). As soon as the second record ins(baz@3) arrives and we include the effect of ins(a@5) into ins(baz@3), it still remains ins(baz@3) because ins(a@5) is now behind it. But notice that, again, we have also to include the effect of ins(baz@3) into ins(a@5), resulting in ins(a@8), to be prepared for the case when the server sends a third record with a zero remote operation count.
+
+=== Why ins and del is not enough ===
+
+In fact, ins and del are not the only required operations. There are two other operations known as NoOperation (noop) and SplitOperation (split). These are not generated directly in response of user input but might result from inclusion transformations. A NoOperation is just an operation that does nothing and therefore has no parameters. A SplitOperation is simply a wrapper around two operations.
+
+Obviously the NoOperation is the simpler case, so I will begin to explain this one. Let's say, we have a document whose content is 'foobar'. We now delete some characters to make 'far' out of it by sending
+
+''obby_document:1 1:record:0:0:del:1:3''
+
+to the server. The server decided to delete only 'oo' and sent
+
+{{{obby_document:1 1:record:0:0:del:1:2''
+
+When we get this operation we notice that the server deleted 'oo' before he got our deletion of 'oob'. Therefore, we have to include the effect of del(1,3) into del(1,2). When we delete three characters starting at index 1, the first to characters starting at index 1 are already deleted, so we have to do nothing, because we already deleted ourselves what the server deleted. The result of this transformation is therefore a noop. This happens every time when we receive a delete operation that deletes a range that is already deleted.
+
+The SplitOperation is required when one inserts text into a range of text that has to deleted. Consider the following example (again, the initial content is 'foobar'):
+
+''obby_doucment:1 1:record:0:0:ins:3:bal''
+{{{obby_document:1 1:record:0:0:del:0:6}}}
+
+so the server deletes all six characters in the document, resulting in an empty document while we inserted 'bal' at position 3 which turns to 'foobalbar'. Now we receive the delete record from the server. Obviously the server wants to delete 'foobar', so we cannot just perform del(0,6) because it would be 'bar' what remains and not 'bal'. When transforming the incoming operation, it has to be splitted up into two delete operations: del(0,3) and del(6,9) which deletes the original 'foobar'.
 
 === Disconnecting ===