frontend/apply_patch.js (204 lines of code) (raw):
const { isObject, copyObject, parseOpId } = require('../src/common')
const { OBJECT_ID, CONFLICTS, ELEM_IDS } = require('./constants')
const { instantiateText } = require('./text')
const { instantiateTable } = require('./table')
const { Counter } = require('./counter')
/**
* Reconstructs the value from the patch object `patch`.
*/
function getValue(patch, object, updated) {
if (patch.objectId) {
// If the objectId of the existing object does not match the objectId in the patch,
// that means the patch is replacing the object with a new one made from scratch
if (object && object[OBJECT_ID] !== patch.objectId) {
object = undefined
}
return interpretPatch(patch, object, updated)
} else if (patch.datatype === 'timestamp') {
// Timestamp: value is milliseconds since 1970 epoch
return new Date(patch.value)
} else if (patch.datatype === 'counter') {
return new Counter(patch.value)
} else {
// Primitive value (int, uint, float64, string, boolean, or null)
return patch.value
}
}
/**
* Compares two strings, interpreted as Lamport timestamps of the form
* 'counter@actorId'. Returns 1 if ts1 is greater, or -1 if ts2 is greater.
*/
function lamportCompare(ts1, ts2) {
const regex = /^(\d+)@(.*)$/
const time1 = regex.test(ts1) ? parseOpId(ts1) : {counter: 0, actorId: ts1}
const time2 = regex.test(ts2) ? parseOpId(ts2) : {counter: 0, actorId: ts2}
if (time1.counter < time2.counter) return -1
if (time1.counter > time2.counter) return 1
if (time1.actorId < time2.actorId) return -1
if (time1.actorId > time2.actorId) return 1
return 0
}
/**
* `props` is an object of the form:
* `{key1: {opId1: {...}, opId2: {...}}, key2: {opId3: {...}}}`
* where the outer object is a mapping from property names to inner objects,
* and the inner objects are a mapping from operation ID to sub-patch.
* This function interprets that structure and updates the objects `object` and
* `conflicts` to reflect it. For each key, the greatest opId (by Lamport TS
* order) is chosen as the default resolution; that op's value is assigned
* to `object[key]`. Moreover, all the opIds and values are packed into a
* conflicts object of the form `{opId1: value1, opId2: value2}` and assigned
* to `conflicts[key]`. If there is no conflict, the conflicts object contains
* just a single opId-value mapping.
*/
function applyProperties(props, object, conflicts, updated) {
if (!props) return
for (let key of Object.keys(props)) {
const values = {}, opIds = Object.keys(props[key]).sort(lamportCompare).reverse()
for (let opId of opIds) {
const subpatch = props[key][opId]
if (conflicts[key] && conflicts[key][opId]) {
values[opId] = getValue(subpatch, conflicts[key][opId], updated)
} else {
values[opId] = getValue(subpatch, undefined, updated)
}
}
if (opIds.length === 0) {
delete object[key]
delete conflicts[key]
} else {
object[key] = values[opIds[0]]
conflicts[key] = values
}
}
}
/**
* Creates a writable copy of an immutable map object. If `originalObject`
* is undefined, creates an empty object with ID `objectId`.
*/
function cloneMapObject(originalObject, objectId) {
const object = copyObject(originalObject)
const conflicts = copyObject(originalObject ? originalObject[CONFLICTS] : undefined)
Object.defineProperty(object, OBJECT_ID, {value: objectId})
Object.defineProperty(object, CONFLICTS, {value: conflicts})
return object
}
/**
* Updates the map object `obj` according to the modifications described in
* `patch`, or creates a new object if `obj` is undefined. Mutates `updated`
* to map the objectId to the new object, and returns the new object.
*/
function updateMapObject(patch, obj, updated) {
const objectId = patch.objectId
if (!updated[objectId]) {
updated[objectId] = cloneMapObject(obj, objectId)
}
const object = updated[objectId]
applyProperties(patch.props, object, object[CONFLICTS], updated)
return object
}
/**
* Updates the table object `obj` according to the modifications described in
* `patch`, or creates a new object if `obj` is undefined. Mutates `updated`
* to map the objectId to the new object, and returns the new object.
*/
function updateTableObject(patch, obj, updated) {
const objectId = patch.objectId
if (!updated[objectId]) {
updated[objectId] = obj ? obj._clone() : instantiateTable(objectId)
}
const object = updated[objectId]
for (let key of Object.keys(patch.props || {})) {
const opIds = Object.keys(patch.props[key])
if (opIds.length === 0) {
object.remove(key)
} else if (opIds.length === 1) {
const subpatch = patch.props[key][opIds[0]]
object._set(key, getValue(subpatch, object.byId(key), updated), opIds[0])
} else {
throw new RangeError('Conflicts are not supported on properties of a table')
}
}
return object
}
/**
* Creates a writable copy of an immutable list object. If `originalList` is
* undefined, creates an empty list with ID `objectId`.
*/
function cloneListObject(originalList, objectId) {
const list = originalList ? originalList.slice() : [] // slice() makes a shallow clone
const conflicts = (originalList && originalList[CONFLICTS]) ? originalList[CONFLICTS].slice() : []
const elemIds = (originalList && originalList[ELEM_IDS]) ? originalList[ELEM_IDS].slice() : []
Object.defineProperty(list, OBJECT_ID, {value: objectId})
Object.defineProperty(list, CONFLICTS, {value: conflicts})
Object.defineProperty(list, ELEM_IDS, {value: elemIds})
return list
}
/**
* Updates the list object `obj` according to the modifications described in
* `patch`, or creates a new object if `obj` is undefined. Mutates `updated`
* to map the objectId to the new object, and returns the new object.
*/
function updateListObject(patch, obj, updated) {
const objectId = patch.objectId
if (!updated[objectId]) {
updated[objectId] = cloneListObject(obj, objectId)
}
const list = updated[objectId], conflicts = list[CONFLICTS], elemIds = list[ELEM_IDS]
for (let i = 0; i < patch.edits.length; i++) {
const edit = patch.edits[i]
if (edit.action === 'insert' || edit.action === 'update') {
const oldValue = conflicts[edit.index] && conflicts[edit.index][edit.opId]
let lastValue = getValue(edit.value, oldValue, updated)
let values = {[edit.opId]: lastValue}
// Successive updates for the same index are an indication of a conflict on that list element.
// Edits are sorted in increasing order by Lamport timestamp, so the last value (with the
// greatest timestamp) is the default resolution of the conflict.
while (i < patch.edits.length - 1 && patch.edits[i + 1].index === edit.index &&
patch.edits[i + 1].action === 'update') {
i++
const conflict = patch.edits[i]
const oldValue2 = conflicts[conflict.index] && conflicts[conflict.index][conflict.opId]
lastValue = getValue(conflict.value, oldValue2, updated)
values[conflict.opId] = lastValue
}
if (edit.action === 'insert') {
list.splice(edit.index, 0, lastValue)
conflicts.splice(edit.index, 0, values)
elemIds.splice(edit.index, 0, edit.elemId)
} else {
list[edit.index] = lastValue
conflicts[edit.index] = values
}
} else if (edit.action === 'multi-insert') {
const startElemId = parseOpId(edit.elemId), newElems = [], newValues = [], newConflicts = []
const datatype = edit.datatype
edit.values.forEach((value, index) => {
const elemId = `${startElemId.counter + index}@${startElemId.actorId}`
value = getValue({ value, datatype }, undefined, updated)
newValues.push(value)
newConflicts.push({[elemId]: {value, datatype, type: 'value'}})
newElems.push(elemId)
})
list.splice(edit.index, 0, ...newValues)
conflicts.splice(edit.index, 0, ...newConflicts)
elemIds.splice(edit.index, 0, ...newElems)
} else if (edit.action === 'remove') {
list.splice(edit.index, edit.count)
conflicts.splice(edit.index, edit.count)
elemIds.splice(edit.index, edit.count)
}
}
return list
}
/**
* Updates the text object `obj` according to the modifications described in
* `patch`, or creates a new object if `obj` is undefined. Mutates `updated`
* to map the objectId to the new object, and returns the new object.
*/
function updateTextObject(patch, obj, updated) {
const objectId = patch.objectId
let elems
if (updated[objectId]) {
elems = updated[objectId].elems
} else if (obj) {
elems = obj.elems.slice()
} else {
elems = []
}
for (const edit of patch.edits) {
if (edit.action === 'insert') {
const value = getValue(edit.value, undefined, updated)
const elem = {elemId: edit.elemId, pred: [edit.opId], value}
elems.splice(edit.index, 0, elem)
} else if (edit.action === 'multi-insert') {
const startElemId = parseOpId(edit.elemId)
const datatype = edit.datatype
const newElems = edit.values.map((value, index) => {
value = getValue({ datatype, value }, undefined, updated)
const elemId = `${startElemId.counter + index}@${startElemId.actorId}`
return {elemId, pred: [elemId], value}
})
elems.splice(edit.index, 0, ...newElems)
} else if (edit.action === 'update') {
const elemId = elems[edit.index].elemId
const value = getValue(edit.value, elems[edit.index].value, updated)
elems[edit.index] = {elemId, pred: [edit.opId], value}
} else if (edit.action === 'remove') {
elems.splice(edit.index, edit.count)
}
}
updated[objectId] = instantiateText(objectId, elems)
return updated[objectId]
}
/**
* Applies the patch object `patch` to the read-only document object `obj`.
* Clones a writable copy of `obj` and places it in `updated` (indexed by
* objectId), if that has not already been done. Returns the updated object.
*/
function interpretPatch(patch, obj, updated) {
// Return original object if it already exists and isn't being modified
if (isObject(obj) && (!patch.props || Object.keys(patch.props).length === 0) &&
(!patch.edits || patch.edits.length === 0) && !updated[patch.objectId]) {
return obj
}
if (patch.type === 'map') {
return updateMapObject(patch, obj, updated)
} else if (patch.type === 'table') {
return updateTableObject(patch, obj, updated)
} else if (patch.type === 'list') {
return updateListObject(patch, obj, updated)
} else if (patch.type === 'text') {
return updateTextObject(patch, obj, updated)
} else {
throw new TypeError(`Unknown object type: ${patch.type}`)
}
}
/**
* Creates a writable copy of the immutable document root object `root`.
*/
function cloneRootObject(root) {
if (root[OBJECT_ID] !== '_root') {
throw new RangeError(`Not the root object: ${root[OBJECT_ID]}`)
}
return cloneMapObject(root, '_root')
}
module.exports = {
interpretPatch, cloneRootObject
}