David, Again thanks. One more question from this set of answers. In your descriptions you mention the OT v3 protocol, along with the possibility of having more than one operations in flight as well as NACKS. None of these concepts seem to exist in WiaB. Is this something that was implemented later or in another project?
~Michael On Jan 8, 2012, at 6:12 PM, David Hearnden wrote: > Hi Michael, > > Torben gave a nice general description of the relationship between retain > and composition. I'll try to concretize that to your specific questions > below. > > On Wed, Dec 28, 2011 at 3:24 AM, Michael MacFadden < > [email protected]> wrote: > >> >> 1) In order to compose operations I assume they don't have to have the >> same document width (how could they for successive inserts for example), >> but I assume they would need to span the same line? Is that right? In >> other words you wouldn't compose operations from one paragraph with >> operations from another? Is the desire to compose one of the driving >> reasons for the retain operation? >> > > Yes, no, no, no, kind-of. > > An operation has two document widths/lengths: the length of the document > before the op, and the length of the document after the op. The only > constraint for composition is that, for op2 o op1 to make sense, the > after-length of op1 must be equal to before-length of op2. These might or > might not be equal > > There is no relationship between lines and composition. Two ops that > modify different lines can be (and are) composed into one op. Line > elements are an application-level abstraction used by the editor to give > good concurrent behaviour of rich text. The underlying OT code is lower > level, and has no association with line elements. > > Finally, retain is necessary without regard to composition. A trailing > retain, however, is probably mainly for conceptual satisfaction rather than > being fundamentally necessary. It might make the composition code a bit > simpler, but I'm not sure. Abstractly though, an operation implements a > function from documents of length N to documents of length M. Those > lengths are part of that operation's functional type signature. An > operation that inserts an 'x' at position 30 in a document of total size 50 > is considered a completely distinct operation to one that inserts 'x' at > position 30 in a document of total size 60. This is just like mathematical > functions, where the doubling function (\x -> 2*x) from the Integers to the > Integers is considered to be a different function to the doubling function > from the Integers to the Even Integers, since their codomains are different > (even though their domains and ranges are equal). Having the trailing > retain means that the concrete representation of an operation conforms to > that abstraction. > > 2) When we send out "first" operation over to the server and we are in a >> holding pattern buffering client operations, are these operations always >> composed together and then sent over as a single operation when we get the >> ACK from the server. It seems like we can only send one operation to the >> server at a time, however the on line material implies that when we get and >> ACK we send over ALL buffered operations. This seems to be contradictory. >> If we have buffered 4 operations, it seems like we can send all of them as >> four individual operations. >> > > There is at least one constraint that can cause the client not to compose > its buffer of outgoing operations. While a list of operations is in > transit to the server, subsequent client operations are not composed with > that list. This is so that if an ACK is received, that preserved list of > operations reflects the exact form that the server received, not some other > form that was subsequently modified by composition with more ops. > > Another cause for why the client might not compose its outgoing operation > buffer is that in Wave's OT, transformation and composition do not > necessarily commute: > Ts (Ts (s, c1), c2) = Ts (s, c1 ; c2) > is not always true. This cause might not affect the current CC protocol > though - it may only be an issue for the OT v3 protocol where a client > might have several ops in flight that get separately acknowledged. In that > case, once a client has sent an op to the server, it can no longer compose > that op with any others, unless it gets NACKed. > > So, in general, the client will have a list of operations that are yet to > be ACKed by the server, and some subset of those operations will be in > flight. Operations in that in-flight subset can not be composed with > anything. Operations that have not yet been sent, however, are free to be > composed together, but the client is not obliged to do so. In particular, > while DocOps can always be composed, WaveOps can not always be composed, so > it is important that client-side composition is treated as an optional > behaviour rather than required. > > 3) Is there a run down of how the CurrencyControl class does point #2 >> anywhere. I see the unacknowledged, the inferredServerPath, and the >> clientOperationsQueue objects and get a lose impression of how these are >> managed but any help with regard to incoming server operations while we >> have an operation in flight would be appreciated. Specifically what >> transformations are performed on which object structures when we get a new >> operation form there server, and where / when is composition happening. >> > > I can't recall where this happens in the code. IIRC, composing buffered > operations is not implemented in the core CC class, but is rather done by a > specific subclass of an OperationQueue (BufferedOperationQueue?). I think > its behaviour was just to attempt composition of any incoming ops with the > last op in the buffer, so long as that op is not in flight waiting for an > ACK or NACK. > > >> 4) How exactly are the hashed versions designed? There seems to be a >> monotonic scalar version number and a hash? I want to make sure I >> understand how both are generated and how both are used. >> > > I'll defer this to Alex. > > If any of this is well documented, please let me know where I could find >> it. If it is not, I would volunteer to document this as I work through it. >> Thanks in advance. >> > > I think some of the detailed design intents for the op stuff is littered > throughout various mailing threads, but not in any written document that I > can recall. Thankyou for offering to collate these answers into a cohesive > document. It's always easier to answer specific questions like these in > email than it is to curate a single document over time that should explain > it all! > > -Dave
