Hello Brett, I don't understand your example. I take the collection of comments owned by the chatroom to be like the set of blips that belong to a wavelet - there is not such merging problems in this case.
What your example needs is some intention preservation :) Each user intended to insert a comment into the collection. The OT functions must preserve this intention. Dan On Dec 2, 9:26 am, Brett Morgan <[email protected]> wrote: > Dan, > > Let us say we are modelling a conversation using IRC semantics. We > have a structure in the document, say <chatroom>, that contains a > series of <comment>s, each with a <user> and a <data>. So a chat > session would wind up with a document that looks like this: > > <chatroom> > <comment> > <user>bill</user> > <data>Morning...</data> > </comment> > <comment> > <user>bob</user> > <data>It's evening here!</data> > </comment> > </chatroom> > > Each client is going to send an edit like the following when they > start a new comment in the conversation: > > retain(X) > startElement("comment") > startElement("user") > characters("<user>") > endElement("user") > startElement("data") > endElement("data") > endElement("comment") > > If we collapse the startElement calls on a pair of co-occuring comment > initiation edits, then the document structure would show the two > user's comments merged like something out of a cheesy 80s scifi > classic. > > brett > > On Dec 2, 10:43 am, Daniel Paull <[email protected]> wrote: > > > > > Brett, > > > Can you please list a few cases from the bunch that you can think of? > > > Dan > > > On Dec 2, 3:46 am, Brett Morgan <[email protected]> wrote: > > > > I can think of a bunch of use cases that don't require intention > > > preserving, > > > but in fact fail in when intention preserving is introduced. Intention > > > preserving only makes sense when the content being merged is purely text, > > > once you introduce structure (wave's xml like entities for example), > > > intention preserving suddenly invites structural damage. > > > > brett > > > > On Tue, Dec 1, 2009 at 10:42 PM, Daniel Paull <[email protected]> wrote: > > > > > The example provided by the OP is perfectly valid and will happen in > > > > reality, especially in high latency conditions or when users can work > > > > off line. > > > > > The whole point of transforming one operation past the other is to > > > > account for the way they interfere with each other. In the case in > > > > question, both operations try to delete the same characters. The > > > > inclusion transform accounts for this by detecting the overlapping > > > > range of delete characters and will make the transformed operation > > > > delete no characters. > > > > > It should be noted that the OT Functions shown on the Wikipedia page > > > > are vastly simplified compared to any serious OT implementation as > > > > they only deal with single character inserts (and does not tackle > > > > deletes at all!). Once you start to deal with ranges, the way inserts > > > > and deletes interact gets quite complex. > > > > > BTW, I find it very strange that the API has functions like > > > > deleteCharacters("15"). I would have expected something like > > > > deleteCharacters( int i1, int i2 ) where [i1, i2) defines a half open > > > > interval of characters to be deleted. > > > > > Cheers, > > > > > Dan > > > > > On Dec 1, 6:36 pm, Brett Morgan <[email protected]> wrote: > > > > > All, > > > > > > I've been thinking some more about this code, and I've realised that > > > > > it > > > > > probably should have thrown an exception when I applied the second > > > > > edit > > > > > against the untransformed intermediate document. The code is faced > > > > > with > > > > the > > > > > fact that the current document has "16", while the inbound edit's > > > > > delete > > > > has > > > > > "15" in it, and yet it still composes. I can see in > > > > > Composer.CharactersPostTaget#deleteCharacters(String) where it should > > > > error > > > > > out, but it doesn't compare the inbound characters to be deleted > > > > > against > > > > the > > > > > characters in the document. > > > > > > I understand this shouldn't be a problem in proper usage of Composer, > > > > > but > > > > > given the fact that there are people who aren't aware of the > > > > preconditions > > > > > now attempting to integrate this code, maybe we should increase the > > > > > defensive protections in this code base. Or is the run time cost of > > > > > these > > > > > protections in the inner code loops too high? > > > > > > brett > > > > > > On Mon, Nov 30, 2009 at 7:10 PM, Brett Morgan <[email protected] > > > > >wrote: > > > > > > > Jelke, > > > > > > > Here's my attempt at implementing your situation using the base wave > > > > > > primitives - BufferedDocOp, Composer and Transformer: > > > > > > > public class Main { > > > > > > > public static void main(String[] args) throws > > > > > > OperationException { > > > > > > // A server document. It contains "15" > > > > > > final BufferedDocOp serverInitial = new > > > > > > DocOpBuilder().characters("15").build(); > > > > > > dump("server initial state", serverInitial); > > > > > > > // First client submits an edit against "15", replacing it > > > > > > with > > > > > > "16" > > > > > > final BufferedDocOp client1edit = new > > > > > > DocOpBuilder().deleteCharacters("15").characters("16").build(); > > > > > > dump("client 1's edit", client1edit); > > > > > > > // As this is the first edit against "15" the server has > > > > > > seen, > > > > it > > > > > > will > > > > > > // compose without issue > > > > > > final BufferedDocOp serverIntermediate = > > > > > > Composer.compose(serverInitial, client1edit); > > > > > > dump("server intermediate state", serverIntermediate); > > > > > > > // Second client submits an edit against "15", replacing it > > > > with > > > > > > "17" > > > > > > final BufferedDocOp client2edit = new > > > > > > DocOpBuilder().deleteCharacters("15").characters("17").build(); > > > > > > > // Composing directly, without transformation > > > > > > BufferedDocOp untransformedServerState = > > > > > > Composer.compose(serverIntermediate, client2edit); > > > > > > dump("untransformed server state", > > > > > > untransformedServerState); > > > > > > > // Transforming the server history stack (which contains > > > > > > client1edit) against the new edit > > > > > > final OperationPair<BufferedDocOp> transformed = > > > > > > Transformer.transform(client2edit, client1edit); > > > > > > dump("transformed client state", transformed.clientOp()); > > > > > > dump("transformed server state", transformed.serverOp()); > > > > > > > final BufferedDocOp serverFinal = > > > > > > Composer.compose(serverIntermediate, transformed.clientOp()); > > > > > > dump("transformed + composed server final state", > > > > > > serverFinal); > > > > > > > } > > > > > > > private static void dump(String context, BufferedDocOp op) { > > > > > > System.out.println(context + ": " + > > > > DocOpUtil.toConciseString(op)); > > > > > > } > > > > > > > } > > > > > > > Here is the resulting output: > > > > > > > server initial state: ++"15"; > > > > > > client 1's edit: --"15"; ++"16"; > > > > > > server intermediate state: ++"16"; > > > > > > untransformed server state: ++"17"; > > > > > > transformed client state: ++"17"; __2; > > > > > > transformed server state: __2; ++"16"; > > > > > > transformed + composed server final state: ++"1716"; > > > > > > > Transforming the second edit against the history stack is required > > > > > > so > > > > that > > > > > > the deletes of the two deletes are merged. > > > > > > > hth, > > > > > > > brett > > > > > > > On Mon, Nov 30, 2009 at 12:05 AM, Jelke J. van Hoorn < > > > > [email protected]>wrote: > > > > > > >> Hi, > > > > > > >> I was looking the "under the hood" vidieo of Google IO 2009. And > > > > > >> I'm > > > > > >> wondering what happens in the following situation: > > > > > > >> On the server a piece of text is lets say "15" and two clients > > > > > >> alter > > > > > >> the same piece in "16" and "17" respectively. > > > > > >> What would be the outcome of the transforms? There is no > > > > > >> unambigeous > > > > > >> way to cope with this edit I think. > > > > > > >> Grtz Jelke > > > > > > >> -- > > > > > > >> 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%2bunsubscr...@goog > > > > > >> legroups.com> > > > > <wave-protocol%2bunsubscr...@goog legroups.com> > > > > > >> . > > > > > >> For more options, visit this group at > > > > > >>http://groups.google.com/group/wave-protocol?hl=en. > > > > > > > -- > > > > > > Brett Morganhttp://domesticmouse.livejournal.com/ > > > > > > -- > > > > > Brett Morganhttp://domesticmouse.livejournal.com/ > > > > > -- > > > > > 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%2bunsubscr...@goog > > > > legroups.com> > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/wave-protocol?hl=en. > > > > -- > > > Brett Morganhttp://domesticmouse.livejournal.com/ -- 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.
