More precisely, Wave's composition and transformation functions do not
commute. Transformation of the composition of two ops does not always
produce the same op as the successive transformations of those two ops:
Ts (Ts (s, c1), c2) != Ts (s, c1 ; c2)
where Ts is one side of the transform function (i.e., the side that produces
the transformed server op), s is a server op, and c1, c2 are client ops.
This is why in Wave there are restrictions on when composition can be
performed. Basically, composition only ever occurs in the client, in its
queue of outgoing ops, before any transform is done. The server does not
compose ops.
If you're wondering what it would take to make them commute, I do not have a
good answer. I do not know whether the obvious transform and composition
functions for more trivial data types usually commute or not, but I suspect
that they would.
-Dave
On Mon, Mar 7, 2011 at 3:11 AM, Daniel Danilatos <danila...@google.com>wrote:
> Yes, compose and transform are not compatible with eachother.
>
> Dan
>
> Στις 5 Μαρτίου 2011 12:45 π.μ., ο χρήστης Joseph Gentle
> <jose...@gmail.com>έγραψε:
>
> > I've just found a surprising bug of sorts in my OT code. It turns out
> > compose has peculiar side effects in terms of information loss / gain.
> >
> > Imagine you have a compose function '+', infix transform function 'T',
> > server op 's' and client ops 'c1' and 'c2', its possible that:
> > s T c1 T c2 != s T (c1 + c2)
> >
> > Wave's concurrency control algorithms never do this, so its not a
> > problem in practice. Is this normal? It never occurred to me that this
> > would be the case...
> >
> > If anyone is curious, I've reproduced this behaviour using WIAB's
> > docops (below).
> >
> > -J
> >
> >
> > ... Basically, it happens if
> > s = insert: 's', skip: 1
> > c1 = delete: 'x'
> > c2 = insert: 'c'
> >
> >
> > // Make println() usable.
> > DocOpScrub.setShouldScrubByDefault(false);
> >
> > DocOp s = new DocOpBuilder().characters("s").retain(1).build();
> >
> > DocOp c1 = new DocOpBuilder().deleteCharacters("x").build();
> > DocOp c2 = new DocOpBuilder().characters("c").build();
> >
> > DocOp cc = Composer.compose(c1, c2);
> >
> > // s_ = s T c1
> > DocOp s_ = Transformer.transform(c1, s).serverOp();
> > // s__ = s T c1 T c2
> > DocOp s__ = Transformer.transform(c2, s_).serverOp();
> >
> > // cc = c1 + c2
> > System.out.println("cc: " + cc);
> > // scc_ = s T (c1 + c2)
> > DocOp scc_ = Transformer.transform(cc, s).serverOp();
> >
> > // s__ and scc_ are different!
> > System.out.println("s__: " + s__);
> > System.out.println("scc_: " + scc_);
> > System.out.println();
> >
> > // ... And not just different syntactically. They're different
> > semantically.
> > DocOp doc1 = Composer.compose(ImmutableList.of(new
> > DocOpBuilder().characters("x").build(), c1, c2, s__));
> > System.out.println("doc1: " + doc1);
> >
> > DocOp doc2 = Composer.compose(ImmutableList.of(new
> > DocOpBuilder().characters("x").build(), cc, scc_));
> > System.out.println("doc2: " + doc2);
> >
>
