ottypes / rich-text Goto Github PK

Format for representing rich text documents and changes

License: MIT License

JavaScript 100.00%

rich-text's Introduction

Standard operational transform types

We have a lovely buffet of operational transform types. Each type has many fine features, including thorough testing, browser support and documentation. Each type has its own project in this github organization.

These types have been finely aged in ShareJS's type labs, and now they're ready to enter the world and be used by everyone. We are rather proud of them.

Each type defines a set of standard methods for programatic use. You should be able to define a type using the spec then plug it directly into ShareJS (or other compatible collaborative editing systems) and use it immediately. The type defines how operations and documents are stored and manipulated, while a system like sharejs can decide where the data should be stored on disk, network protocols and all that jazz.

Available OT types

This repository contained three OT types. They were split to separate repositories:

ot-text-unicode

This is the type you should use for normal plain-text editing. It can tranform operation with complexity N against operation with complexity M in O(N+M) time. This makes it much faster than ot-text-tp2 implementation.

ot-text-tp2

This implementation features Transform Property 2 which makes it a good suit for peer-to-peer communication. Unfortunately the extra (unnecessary) complexity kills v8's optimizer and as a result ot-text-tp2 goes about 20x slower than the ot-text type. If you're using client-server library like ShareJS, you don't need TP2 property, so you should use simpler ot-text implementation,

ot-json1

This implementation is capable of transforming not only text but also JSON structures. It supports arbitrary inserts, deletes, and reparenting through the tree of a JSON object.

rich-text

This is an OT implementation for collaboratively editing rich text documents. It was designed alongside QuillJS for editing those documents.

Javascript 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.

There is a simple example of a working type in example.js. For a more thorough example, take a look at the text type.

If you're publishing your library in npm (and you should!), the module should expose an object with a .type property (containing your type). So for example, require('ot-text').type.name contains the text type's name.

Standard properties

name: A user-readable name for the type. This is not guaranteed to be unique.
uri: (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 Berners-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(apply(snapshot, 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

invertWithDoc(op, doc) -> op': (optional, RECOMMENDED) Invert the given operation using context from the document to which it can be applied. This method should generally be added to every type as a way to create undo operations. Formally given apply(snapshot, op) is valid, this creates an operation such that apply(apply(snapshot, op), invert(op, snapshot)) == snapshot. If invert(op) exists, invertWithDoc(op, _) == invert(op). 💣 NOTE: The document passed to invertWithDoc should be the document state before the operation is applied. Not after the operation has been applied.
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, so that the cursor moves forward or backward as content is added or removed before (or at) the cursor position. isOwnOp defines how the cursor should be transformed against content inserted at the cursor position. If isOwnOp is true, the cursor is moved after the content inserted at the original cursor position. If isOwnOp is false, the cursor remains before the content inserted at the original cursor position.
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.

CRDTs

Technically, CRDT types are a subset of OT types. Which is to say, they are OT types that don't need a transform function. As a result, anything that can handle these OT types should also be able to consume CRDTs. But I haven't tested it. If anyone wants to work with me to add CRDT support here, email me.

License

All code contributed to this repository is licensed under the standard MIT license:

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following condition:

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

rich-text's People

Contributors

Stargazers

Watchers

rich-text's Issues

NPM package rename to 'ot-rich-text'?

Noticed that the other type NPM package names follow ot-* (eg. ot-text), and rich-text seems like a very generic name given that it's mostly related to OT, no?

Should a package rename to ot-rich-text be considered?

Implement fuzzer generateRandomOp without compose

Currently potentially hides a bug in compose

Presence

Would an implementation of presence be welcome in this repo?

Here are two implementations that already exist in forks:

Get rid of package.json import in type.js

https://github.com/ottypes/rich-text/blob/master/lib/type.js#L2

There is no need for importing package.json anymore. It was used for pulling version number here: 7d2c20b but that line has since been hardcoded.

Ran into a webpack issue where in order to use this package, I had to add .json type in webpack.

Implement diff(delta, index)

Given a.compose(b) == c, a.diff(c) == b

We'd also like to take an optional index argument to indicate a suggested index for change. This is useful for example when diffing two documents with all newlines, it is useful to know where the insertion/deletion occurred besides assuming it was the first or last character.

clarify if TP2 is supported

I haven't been able to find any info on whether the rich-text type supports or not the Transformation Property 2. I'd be great to add this to the README.

compose with { retain: 0 } does not work correctly

x = new Delta([{insert: "x"}]);
retain_0_delete_1 = new Delta([{retain: 0}, {delete: 1}]);
result = x.compose(retain_0_delete_1);

The result is [{insert: "x"}, {delete: 1}]. It should be just [], right?

{ retain: 0 } can happen with programmatically generated deltas.

Small documentation nit in Quick Example

Thought I'd point out a small documentation nit that might confuse some folks.

The Quick Example section shows the following:

delta.compose(death);
// delta is now:
// {
//   ops: [
//     { insert: 'Gandalf ', attributes: { bold: true } },
//     { insert: 'the ' },
//     { insert: 'White', attributes: { color: '#fff' } }
//   ]
// }

It suggests that the existing delta object has changed. But in fact the semantics of compose don't edit the delta itself, but simply return a new composed delta. A more accurate documentation to reflect this might be the following:

var composed = delta.compose(death);
// composed is:
// {
//   ops: [
//     { insert: 'Gandalf ', attributes: { bold: true } },
//     { insert: 'the ' },
//     { insert: 'White', attributes: { color: '#fff' } }
//   ]
// }

Question: Are operations invertable?

I can't seem to find an invert method on the operations. If this is not available, I wonder how and if Quill.js supports proper "collaborative" undo?

How this implementation relates to ot-text and ot-text-tp2?

Could explain shortly how this implementation relates to ot-text and ot-text-tp2?

What's better, what's worse, what's different? Is this implementation more stable? Why to use it?

Thanks :)

Python port of the rich-text

I hope it's a right place to ask such a questions. I've starter porting rich-text library to Python 2.7 and it's already quite usable (although with no test coverage yet). Now I'm not sure whether you'd find it fine if I published it under MIT licence. I'd also want to know, what kind of credits would you like me to provide for you and whether rich-text-py is a fair name for my repo and package. May I publish it to PyPI once it's polished enough?

How to get a standalone browser client js?

I need to work this without require dependencies
How to export a standalone client js version?

diff() not working as expected

Here's the issue.

If there are two deltas:

var oldDelta = new Delta().insert('ab', {bold: true}).insert('cd');
var newDelta = new Delta().insert('abz', {bold: true}).insert('cd');

And the diff function is applied like so:

var diffedDelta = oldDelta.diff(newDelta);

Than diffedDelta's operations will look like:

{
  ops: [
    {
      retain: 2
    },
    {
      attributes: {
        bold: true
      },
      insert: 'z'
    }
  ]
}

But, if newDelta is changed to:

var newDelta = new Delta().insert('abc', {bold: true}).insert('cd');

Notice that instead of inserting abz we insert abc.

Than diffedDelta's operations will look like:

{
  ops: [
    {
      retain: 2
    },
    {
      retain: 1,
      attributes: {
        bold: true
      }
    },
    {
      insert: 'c'
    }
  ]
}

Which is not the same as before when we inserted abz. There is an extra operation.

In the first case the text is abzcd and in the second case it's abccd, so the issue is if the newly inserted character between ab and cd is the same as the first character from cd than it behaves differently.

After digging through the code, I found that the issue is in the function diff_commonPrefix inside the fast-diff library, mainly in the binary search code.

clone() implementation in op.js

I was reviewing your reference implementation as I'm porting the rich-text ottype to Python and wanted to check-in on something.

The implementation of clone() in op.js is the following:

clone: function (op) {
    var newOp = this.attributes.clone(op);
    if (typeof newOp.attributes === 'object') {
      newOp.attributes = this.attributes.clone(newOp.attributes, true);
    }
    return newOp;
  },

I think your intention is to effectively perform a deep copy of the op. It seems to accomplish this by doing a shallow copy and then special-casing attributes since it knows it is an object and does a separate shallow-copy on it's contents.

While this mostly works, seems like you could run into issues when copying an op that represents a new Quill 1.0-style insert embed operation. Since in this case the value of the insert key is itself an object, like the attributes case, you currently would end up just copying the reference but not deep-copying the individual object keys. Am I correct?

How to build?

Hi, the rich-text ot type doesn't seem available in sharejs and I can't for the life of me work out how the the files in webclient are built.

Any hints on how the build process should work?

Bower package

Ohai! Needed to use this OT document type to register it as a valid ShareJS type on the browser/client side and found that there wasn't a Bower package for it.

Is it possible to add support for Bower?

transform insert at the same position - incorrect result

As I understand, when the side param to transform is "left", the first operation should "happen" first. However, the logic here seems to be reversed.

> require('rich-text').type.transform([ { insert: 'a' } ], [ {insert: 'b'} ], 'left')
Delta { ops: [ { retain: 1 }, { insert: 'a' } ] } // I'd expect Delta { ops: [ { insert: 'a' } ] }

For comparison:

> require('ot-text').type.transform([ 'a' ], [ 'b' ], 'left')
[ 'a' ] // as expected

I think this line should be changed to return delta2.transform(delta1, side === 'right');

delta.length() is wrong when you have implied retain at the end

rich-text might drop retain if it's the last op.
In that case, delta.length() might return the wrong value.
https://github.com/ottypes/rich-text/blob/master/lib/delta.js#L88

Previously we had baseLength and targetLength but now with implied retains there is no way to know if two deltas are composable.

Insert Embed Operation

Jason,

Under the Insert Operation section of the README, you mention the following syntax for embeds:

// Insert an embed
{
  insert: { image: 'https://octodex.github.com/images/labtocat.png' },
  attributes: { alt: "Lab Octocat" }
}

However based on what I've read on Deltas - Quill Documentation it looks like what QuillJS generates for embeds is this:

// Insert an image
{
  insert: 1,
  attributes: {
    image: 'https://octodex.github.com/images/labtocat.png'
  }
}

It looks like your rich-text ottype implementation supports both. Is it correct that we need to support the insert key value being a string (for text) and both a number or a dict for an embed? Are you planning on using both in Quill?

Uncaught Error: diff() called on non-document

Hey,
I experience the issue with Quill on bookmarklet script. After running it on http://www.dwr.com/ initialisation of quill fails with Uncaught Error: diff() called on non-document. I found, that it happens, because clone method of the op returns string instead of object.
After replacing original clone method from https://github.com/ottypes/rich-text/blob/master/lib/op.js#L6,
with

clone: function (attributes, keepNull) {
      if (!is.object(attributes)) return {};
      var memo = {};
      Object.keys(attributes).forEach(function(key) {
        if (attributes[key] !== undefined && (attributes[key] !== null || keepNull)) {
          memo[key] = attributes[key];
        }
      });
      return memo;
    },

everything goes normal. I think it could happen, because original website using some polyfil script. Any thoughts, how to fix or avoid this would be appreciate.

Operation transformation apply deltas to server side

I'm using Quill.js together with socket.io/nodejs on backend. Quill has events for deltas, so I can send the deltas to all clients and create Collaborative editor.

I'm using https://github.com/ottypes/rich-text plugin for backend and my question is how I can apply deltas to backend document.
I can do this in Quill by doing editor.updateContents(deltas_array) and current content will be updated with the incoming deltas.

I've searched through whole rich-text plugin documentation, but I couldn't find a feature to apply deltas to a document.

Implement transform(index)

Useful for transforming cursor positions