Operational transform types, sir?

We have a lovely buffet of operational transform types. Each type has many fine features, including thorough testing, browser support and documentation.

These types have been finely aged in ShareJS's type labs. We hope they will meet your needs.

Please port any types you find useful to your favorite languages so we can do operational transform in more places!

Spec

Each OT type exposes a single object with the following properties. Note that only name, create, apply and transform are strictly required, though most types should also include url and compose.

Standard properties

• name: A user-readable name for the type. This is not guaranteed to be unique.
• url: (Optional, will be required soon) A canonical location for this type. The spec for the OT type should be at this address. Remember kids, Tim Burners-Lee says cool URLs don't change.
• create([initialData]) -> snapshot: A function to create the initial document snapshot. Create may accept initial snapshot data as its only argument. Either the return value must be a valid target for JSON.stringify or you must specify serialize and deserialize functions (described below).
• apply(snapshot, op) -> snapshot': Apply an operation to a document snapshot. Returns the changed snapshot. For performance, old document must not be used after this function call, so apply may reuse and return the current snapshot object.
• transform(op1, op2, side) -> op1': Transform op1 by op2. Return the new op1. Side is either 'left' or 'right'. It exists to break ties, for example if two operations insert at the same position in a string. Both op1 and op2 must not be modified by transform. Transform must conform to Transform Property 1. That is, apply(apply(snapshot, op1), transform(op2, op1, 'left')) == apply(apply(snapshot, op2), transform(op1, op2, 'right')).
• compose(op1, op2) -> op: (optional) Compose op1 and op2 to produce a new operation. The new operation must subsume the behaviour of op1 and op2. Specifically, apply(snapshot, apply(op1), op2) == apply(snapshot, compose(op1, op2)). Note: transforming by a composed operation is NOT guaranteed to produce the same result as transforming by each operation in order. This function is optional, but unless you have a good reason to do otherwise, you should provide a compose function for your type.

Optional properties

• invert(op) -> op': (optional) Invert the given operation. The original operation must not be edited in the process. If supplied, apply(apply(snapshot, op), invert(op)) == snapshot.
• normalize(op) -> op': (optional) Normalize an operation, converting it to a canonical representation. normalize(normalize(op)) == normalize(op).
• transformCursor(cursor, op, isOwnOp) -> cursor': (optional) transform the specified cursor by the provided operation. If isOwnOp is true, this function should return the final editing position of the provided operation. If isOwnOp is false, the cursor position should move with the content to its immediate left.
• serialize(snapshot) -> data: (optional) convert the document snapshot data into a form that may be passed to JSON.stringify. If you have a serialize function, you must have a deserialize function.
• deserialize(data) -> snapshot: (optional) convert data generated by serialize back into its internal snapshot format. deserialize(serialize(snapshot)) == snapshot. If you have a deserialize function, you must have a serialize function.

Do I need serialize and deserialize? Maybe JSON.stringify is sufficiently customizable..?

TP2 Properties

If your OT type supports transform property 2, set the tp2 property to true and define a prune function.

Transform property 2 is an additional requirement on your transform function. Specifically, transform(op3, compose(op1, transform(op2, op1)) == transform(op3, compose(op2, transform(op1, op2)).

• tp2: (optional) Boolean property. Make this truthy to declare that the type has tp2 support. Types with TP2 support must define prune.
• prune(op, otherOp): The inverse of transform. Formally, apply(snapshot, op1) == apply(snapshot, prune(transform(op1, op2), op2)). Usually, prune will simply be the inverse of transform and prune(transform(op1, op2), op2) == op1.

Coffeescript, eh?

The types are in coffeescript because its good. But, I've had my zealotry ground away over time. I have no problem with types in this repository existing in any language so long as running make compiles them to javascript.

License

All code contributed to this repository is licensed under the zero clause BSD license:

Redistribution and use in source and binary forms, with or without modification, are permitted.