Skip to content

Latest commit

 

History

History
265 lines (231 loc) · 7.5 KB

README.md

File metadata and controls

265 lines (231 loc) · 7.5 KB

json.ot

The json0 typescript version

Notion

Snapshot

Snapshots represents the data structure of a document, which can be understood as a string in Text OT Type, or can be understood as JSON in JSON OT Type. Snapshots are generated by applying a series of operations.

Operation

Operations represent modifications to a document, similar to the diff between two commits in Git operations. An operation includes multiple actions. An action is an atomic operation on a document.

Text OT Type

Action

Operation Description
{n: 'SI', p: number, i: string} inserts the string i at offset p into the string
{n: 'SD', p: number, d: string} deletes the string d at offset p from the string

Method

apply(snapshot, operation)

Applying an operation to a snapshot:

const operation: ITOTAction[] = [
  {
    n: TOTActionName.StringInsert,
    p: 0,
    i: 'hello',
  },
];
const result = tot.apply(' world', operation);
expect(result).toEqual('hello world');

compose(operationA, operationB)

Merging operations which have a linear relationship:

const snapshot = 'AD';
const operationA: ITOTAction[] = [{
  n: TOTActionName.StringInsert,
  p: 1,
  i: 'B',
}];
const operationB: ITOTAction[] = [{
  n: TOTActionName.StringInsert,
  p: 2,
  i: 'C',
}];
const snapshotA = tot.apply(tot.apply(snapshot, operationA), operationB);
const snapshotB = tot.apply(snapshot, tot.compose(operationA, operationB));
expect(snapshotA === snapshotB).toBeTruthy();

invert(operation)

Inverting an action generates the inverse operation of an operation:

const operation: ITOTAction[] = [
  {
    n: TOTActionName.StringInsert,
    p: 0,
    i: 'abc',
  }
];
const reversalAction = tot.invert(operation);
expect(reversalAction[0].n).toEqual(TOTActionName.StringDelete);
expect(reversalAction[0].p).toEqual(0);
expect((reversalAction[0] as IStringDeleteAction).d).toEqual('abc');

transform(operation, otherOperation)

A document is generated by operations, and when multiple people collaborate on the document, it is necessary to transform these operations to ensure the consistency of the final document:

// if init document equals to ' ';
const operation: ITOTAction[] = [
  {
    n: TOTActionName.StringInsert,
    p: 1,
    i: 'world',
  },
];
const otherOperation: ITOTAction[] = [
  {
    n: TOTActionName.StringInsert,
    p: 0,
    i: 'hello',
  },
];
const transformOperation = tot.transform(
  operation,
  otherOperation,
  'right'
);
expect(transformOperation[0].p).toEqual(6);

transformX(operationA, operationB)

When two people collaborate on the same snapshot, they can generate derivative operations for their operations using transformX. The non-linear snapshot applies the derived operations, and the different snapshots converges to the same state:

const snapshot = 'AF';
const serverOperation: ITOTAction[] = [
  {
    n: TOTActionName.StringInsert,
    p: 1,
    i: 'B',
  },
  {
    n: TOTActionName.StringInsert,
    p: 2,
    i: 'C',
  },
];
const clientOperation: ITOTAction[] = [
  {
    n: TOTActionName.StringInsert,
    p: 1,
    i: 'D',
  },
  {
    n: TOTActionName.StringInsert,
    p: 2,
    i: 'E',
  },
];
const serverSnapshot = tot.apply(snapshot, serverOperation);
const clientSnapshot = tot.apply(snapshot, clientOperation);
const [leftOperation, rightOperation] = tot.transformX(
  serverOperation,
  clientOperation,
);
const client = tot.apply(clientSnapshot, leftOperation);
const service = tot.apply(serverSnapshot, rightOperation);
expect(client).toEqual('ABCDEF');
expect(client).toEqual(service);

JSON OT Type

Action

Operation Description
{n: 'NA', p: [path], na: x} adds x to the number at [path].
{n: 'LI', p: [path, idx], li: obj} inserts the object obj before the item at idx in the list at [path].
{n: 'LD', p: [.path, idx], ld: obj} deletes the object obj from the index idx in the list at [path].
{n: 'LR', p:[path,idx], ld:before, li:after} replaces the object before at the index idx in the list at [path] with the object after.
{n: 'LM', p:[path,idx1], lm:idx2} moves the object at idx1 such that the object will be at index idx2 in the list at [path].
{n: 'OI', p:[path,key], oi:obj} inserts the object obj into the object at [path] with key key.
{n: 'OD', p:[path,key], od:obj} deletes the object obj with key key from the object at [path].
{n: 'OR', p:[path,key], od:before, oi:after} replaces the object before with the object after at key key in the object at [path].
{n: 'ST', p: [path], t: subtype, o: subtypeOp} applies the subtype op o of type t to the object at [path]
{n: 'SI', p:[path,offset], si:s} inserts the string s at offset offset into the string at [path] (uses subtypes internally).
{n: 'SD', p:[path,offset], sd:s} deletes the string sat offset offset from the string at [path] (uses subtypes internally).

Scenario

string insert and string delete

const snapshot = {
  cell: {
    text: 'abc',
  },
};
const stringInsertOperation: IJOTAction = {
  n: JOTActionName.TextInsert,
  p: ['cell', 'text', 3],
  si: 'd',
};
const stringDeleteOperation: IJOTAction = {
  n: JOTActionName.TextDelete,
  p: ['cell', 'text', 0],
  sd: 'a',
};
const versionA = jot.apply(snapshot, [stringInsertOperation]);
const versionB = jot.apply(versionA, [stringDeleteOperation]);
expect((versionB.cell as IJson).text).toEqual('bcd');

insert/delete/move/replace element into/ /from/ list

const snapshot = {
  cell: {
    list: [1, 2, 3],
  },
};
const listInsert: IJOTAction = {
  n: JOTActionName.ListInsert,
  p: ['cell', 'list', 0],
  li: 0,
};
const versionA = jot.apply(snapshot, [listInsert]);
expect((versionA.cell as IJson).list).toEqual([0, 1, 2, 3]);
const listDelete: IJOTAction = {
  n: JOTActionName.ListDelete,
  p: ['cell', 'list', 3],
  ld: 3,
};
const versionB = jot.apply(versionA, [listDelete]);
expect((versionB.cell as IJson).list).toEqual([0, 1, 2]);
const listMove: IJOTAction = {
  n: JOTActionName.ListMove,
  p: ['cell', 'list', 0],
  lm: 2,
};
const versionC = jot.apply(versionB, [listMove]);
expect((versionC.cell as IJson).list).toEqual([1, 2, 0]);
const listReplace: IJOTAction = {
  n: JOTActionName.ListReplace,
  p: ['cell', 'list', 2],
  ld: 0,
  li: 3,
};
const versionD = jot.apply(versionC, [listReplace]);
expect((versionD.cell as IJson).list).toEqual([1, 2, 3]);

insert/delete/replace object

const snapshot = {
  row: {
    cell1: 'text',
    cell2: 'text',
  }
};
const objectInsert: IJOTAction = {
  n: JOTActionName.ObjectInsert,
  p: ['row', 'cell0'],
  oi: 'text',
}
const versionA = jot.apply(snapshot, [objectInsert]);
expect((versionA.row as IJson).cell0).toEqual('text');
const objectDelete: IJOTAction = {
  n: JOTActionName.ObjectDelete,
  p: ['row', 'cell2'],
  od: 'text',
};
const versionB = jot.apply(versionA, [objectDelete]);
expect((versionB.row as IJson).cell2).toBeUndefined();
const objectReplace: IJOTAction = {
  n: JOTActionName.ObjectReplace,
  p: ['row', 'cell1'],
  od: 'text',
  oi: {
    text: '1',
  },
};
const versionC = jot.apply(versionA, [objectReplace]);
expect((versionC.row as IJson).cell1).toEqual({text: '1'});