Dan,
Ok, my understanding of intention preserving from the literature was around
an instance like the following:
server document contains: "abc"
client 1 sends an edit of the form: retain(3), characters("123")
client 2 sends an edit of the form: retain(3), characters("125")
a resulting document, with intention preserving: "abc1235"
a resulting document, sans intention preserving: "abc123125"
One of the (many) innovations that the google team have introduced into the
OT algorithm is xml like structure. I see that your definition of intention
preserving over the xml structure is not to collapse aligned edits, as was
the case above with the parrallel "12" character additions. This was not my
understanding of what intention preseving means, given my reading of the
literature.
brett
On Thu, Dec 3, 2009 at 12:05 AM, Daniel Paull <[email protected]> wrote:
> 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%[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%[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]<wave-protocol%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/wave-protocol?hl=en.
>
>
>
--
Brett Morgan http://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.
