Hi, I read the spec back and forth and my conclusion is that all document operations must repeat all annotations of the document.
To build a worst case: A document consists of 1000 characters, each with different annotations. When deleting 1000 characters I have to repeat the annotation for each deleted character in the mutation operation (this is what the spec says and complies with the solution suggested by Joseph). So delete can be expensive, I accept this. According to the specs, the same is true for the retain operation. Quote: "For update components (retain is one), the old values in the annotations update match the annotation values of each item in the input document that the component processes. The generated items in the output document will have the same annotations as the corresponding input items, except for the annotation keys in the annotations update; for those keys, the generated items will have the new values." This means when I want to insert a single new character, the mutation operation contains 1000 annotation updates, because I must "retain" all 1000 characters and therefore I must provide their annotation. This is quite costly. One might argue that this is an unlikely scenario. But remember that cursors are realized with annotations. If 100 users have edited in a public wave, then there are at least 100 annotation boundaries in the document which have to be repeated in every operation. Even worse, each new session creates a new annotation ... Is there any garbage collection on the server side that removes old annotations to clear up the mess? I must admit that annotations & OT are quite mind twisting when it comes to the corner cases. Greetings Torben 2010/8/6 Joseph Gentle <[email protected]> > In this case, the delete op must also delete the annotation. If it didn't, > the op wouldn't be invertable (if you apply the op then apply its inverse, > you'll end up removing the annotation). > > Your example should look like: > mutation1 := anno('bold': 'true' -> NULL), delete 'ab', anno(end 'bold'), > retain 2 > mutation2 := retain 2, insert 'x', retain 2 > > After transform, mutation1_t is the same as you suggested, but > > mutation2_t := anno ('bold': NULL -> true) insert 'x', anno (end 'bold'), > retain 2 > > ... and you get the correct behaviour. > > -J > > > On Fri, Aug 6, 2010 at 11:14 AM, Torben Weis <[email protected]>wrote: > >> Hi, >> >> I encountered a problem while unit testing my OT code. Either I just found >> a major flaw in the OT algorithm (i.e. a flaw that is almost impossible to >> repair) or I am too tired to see the solution. Here is the problem: >> >> Let "A, B ,C" be BOLD letters, and "a, b, c" denote the same letters, but >> not in bold. >> Now imagine a simple document with the content >> >> doc := ABcd >> >> i.e. "ab" in bold and "cd" not in bold. Now two users edit the document >> concurrently. >> >> mutation1 := delete:2, retain:2 >> mutation2 := retain:2, insert:"x", retain:2 >> >> i.e. user1 sees "cd" and user2 sees "ABXcd". Notice that the "x" is bold >> -> "X", because in word processors you inherit the style from the left. This >> is important here! >> >> Now I transform both mutations and I get: >> >> mutation1_t := delete:2 retain:3 // I skip the inserted "x" -> >> therefore retain2 >> mutation2_t := insert"x", retain:2 // No need to skip "AB", because >> they are already deleted >> >> Now user1 one applies mutation2_t and user2 applies mutation1_t. They >> should end up in the same state. >> >> However, in the end user1 sees "xcd" and user2 sees "Xcd". The difference >> is that x is not consistently annotated. >> >> As far as can see right now, the transformation function cannot do >> anything because it needs style annotation that is only in the document but >> not in the mutations. >> >> I hope that someone can enlighten me here, because otherwise the OT >> algorithm is broken. >> >> Greetings >> Torben >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Wave Protocol" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<wave-protocol%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/wave-protocol?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Wave Protocol" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<wave-protocol%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/wave-protocol?hl=en. > -- --------------------------- Prof. Torben Weis Universitaet Duisburg-Essen [email protected] -- You received this message because you are subscribed to the Google Groups "Wave Protocol" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
