in backend/new.js [1028:1268]
function mergeDocChangeOps(patches, newBlock, outCols, changeState, docState, listIndex, blockIndex) {
const firstOp = changeState.nextOp, insert = firstOp[insertIdx]
const objActor = firstOp[objActorIdx], objCtr = firstOp[objCtrIdx]
const objectId = objActor === null ? '_root' : `${objCtr}@${docState.actorIds[objActor]}`
const idActorIndex = changeState.actorIndex, idActor = docState.actorIds[idActorIndex]
let foundListElem = false, elemVisible = false, propState = {}, docOp
;({ docOp, blockIndex } = readNextDocOp(docState, blockIndex))
let docOpsConsumed = (docOp === null ? 0 : 1)
let docOpOldSuccNum = (docOp === null ? 0 : docOp[succNumIdx])
let changeOp = null, changeOps = [], changeCols = [], predSeen = [], lastChangeKey = null
changeState.objectIds.add(objectId)
// Merge the two inputs: the sequence of ops in the doc, and the sequence of ops in the change.
// At each iteration, we either output the doc's op (possibly updated based on the change's ops)
// or output an op from the change.
while (true) {
// The array `changeOps` contains operations from the change(s) we're applying. When the array
// is empty, we load changes from the change. Typically we load only a single operation at a
// time, with two exceptions: 1. all operations that update the same key or list element in the
// same object are put into changeOps at the same time (this is needed so that we can update the
// succ columns of the document ops correctly); 2. a run of consecutive insertions is also
// placed into changeOps in one go.
//
// When we have processed all the ops in changeOps we try to see whether there are further
// operations that we can also process while we're at it. Those operations must be for the same
// object, they must be for a key or list element that appears later in the document, they must
// either all be insertions or all be non-insertions, and if insertions, they must be
// consecutive. If these conditions are satisfied, that means the operations can be processed in
// the same pass. If we encounter an operation that does not meet these conditions, we leave
// changeOps empty, and this function returns after having processed any remaining document ops.
//
// Any operations that could not be processed in a single pass remain in changeState; applyOps
// will seek to the appropriate position and then call mergeDocChangeOps again.
if (changeOps.length === 0) {
foundListElem = false
let nextOp = changeState.nextOp
while (!changeState.done && nextOp[idActorIdx] === idActorIndex && nextOp[insertIdx] === insert &&
nextOp[objActorIdx] === firstOp[objActorIdx] && nextOp[objCtrIdx] === firstOp[objCtrIdx]) {
// Check if the operation's pred references a previous operation in changeOps
const lastOp = (changeOps.length > 0) ? changeOps[changeOps.length - 1] : null
let isOverwrite = false
for (let i = 0; i < nextOp[predNumIdx]; i++) {
for (let prevOp of changeOps) {
if (nextOp[predActorIdx][i] === prevOp[idActorIdx] && nextOp[predCtrIdx][i] === prevOp[idCtrIdx]) {
isOverwrite = true
}
}
}
// If any of the following `if` statements is true, we add `nextOp` to `changeOps`. If they
// are all false, we break out of the loop and stop adding to `changeOps`.
if (nextOp === firstOp) {
// First change operation in a mergeDocChangeOps call is always used
} else if (insert && lastOp !== null && nextOp[keyStrIdx] === null &&
nextOp[keyActorIdx] === lastOp[idActorIdx] &&
nextOp[keyCtrIdx] === lastOp[idCtrIdx]) {
// Collect consecutive insertions
} else if (!insert && lastOp !== null && nextOp[keyStrIdx] !== null &&
nextOp[keyStrIdx] === lastOp[keyStrIdx] && !isOverwrite) {
// Collect several updates to the same key
} else if (!insert && lastOp !== null &&
nextOp[keyStrIdx] === null && lastOp[keyStrIdx] === null &&
nextOp[keyActorIdx] === lastOp[keyActorIdx] &&
nextOp[keyCtrIdx] === lastOp[keyCtrIdx] && !isOverwrite) {
// Collect several updates to the same list element
} else if (!insert && lastOp === null && nextOp[keyStrIdx] === null &&
docOp && docOp[insertIdx] && docOp[keyStrIdx] === null &&
docOp[idActorIdx] === nextOp[keyActorIdx] &&
docOp[idCtrIdx] === nextOp[keyCtrIdx]) {
// When updating/deleting list elements, keep going if the next elemId in the change
// equals the next elemId in the doc (i.e. we're updating several consecutive elements)
} else if (!insert && lastOp === null && nextOp[keyStrIdx] !== null &&
lastChangeKey !== null && lastChangeKey < nextOp[keyStrIdx]) {
// Allow a single mergeDocChangeOps call to process changes to several keys in the same
// object, provided that they appear in ascending order
} else break
lastChangeKey = (nextOp !== null) ? nextOp[keyStrIdx] : null
changeOps.push(changeState.nextOp)
changeCols.push(changeState.columns)
predSeen.push(new Array(changeState.nextOp[predNumIdx]))
readNextChangeOp(docState, changeState)
nextOp = changeState.nextOp
}
}
if (changeOps.length > 0) changeOp = changeOps[0]
const inCorrectObject = docOp && docOp[objActorIdx] === changeOp[objActorIdx] && docOp[objCtrIdx] === changeOp[objCtrIdx]
const keyMatches = docOp && docOp[keyStrIdx] !== null && docOp[keyStrIdx] === changeOp[keyStrIdx]
const listElemMatches = docOp && docOp[keyStrIdx] === null && changeOp[keyStrIdx] === null &&
((!docOp[insertIdx] && docOp[keyActorIdx] === changeOp[keyActorIdx] && docOp[keyCtrIdx] === changeOp[keyCtrIdx]) ||
(docOp[insertIdx] && docOp[idActorIdx] === changeOp[keyActorIdx] && docOp[idCtrIdx] === changeOp[keyCtrIdx]))
// We keep going until we run out of ops in the change, except that even when we run out, we
// keep going until we have processed all doc ops for the current key/list element.
if (changeOps.length === 0 && !(inCorrectObject && (keyMatches || listElemMatches))) break
let takeDocOp = false, takeChangeOps = 0
// The change operations come first if we are inserting list elements (seekToOp already
// determines the correct insertion position), if there is no document operation, if the next
// document operation is for a different object, or if the change op's string key is
// lexicographically first (TODO check ordering of keys beyond the basic multilingual plane).
if (insert || !inCorrectObject ||
(docOp[keyStrIdx] === null && changeOp[keyStrIdx] !== null) ||
(docOp[keyStrIdx] !== null && changeOp[keyStrIdx] !== null && changeOp[keyStrIdx] < docOp[keyStrIdx])) {
// Take the operations from the change
takeChangeOps = changeOps.length
if (!inCorrectObject && !foundListElem && changeOp[keyStrIdx] === null && !changeOp[insertIdx]) {
// This can happen if we first update one list element, then another one earlier in the
// list. That is not allowed: list element updates must occur in ascending order.
throw new RangeError("could not find list element with ID: " +
`${changeOp[keyCtrIdx]}@${docState.actorIds[changeOp[keyActorIdx]]}`)
}
} else if (keyMatches || listElemMatches || foundListElem) {
// The doc operation is for the same key or list element in the same object as the change
// ops, so we merge them. First, if any of the change ops' `pred` matches the opId of the
// document operation, we update the document operation's `succ` accordingly.
for (let opIndex = 0; opIndex < changeOps.length; opIndex++) {
const op = changeOps[opIndex]
for (let i = 0; i < op[predNumIdx]; i++) {
if (op[predActorIdx][i] === docOp[idActorIdx] && op[predCtrIdx][i] === docOp[idCtrIdx]) {
// Insert into the doc op's succ list such that the lists remains sorted
let j = 0
while (j < docOp[succNumIdx] && (docOp[succCtrIdx][j] < op[idCtrIdx] ||
docOp[succCtrIdx][j] === op[idCtrIdx] && docState.actorIds[docOp[succActorIdx][j]] < idActor)) j++
docOp[succCtrIdx].splice(j, 0, op[idCtrIdx])
docOp[succActorIdx].splice(j, 0, idActorIndex)
docOp[succNumIdx]++
predSeen[opIndex][i] = true
break
}
}
}
if (listElemMatches) foundListElem = true
if (foundListElem && !listElemMatches) {
// If the previous docOp was for the correct list element, and the current docOp is for
// the wrong list element, then place the current changeOp before the docOp.
takeChangeOps = changeOps.length
} else if (changeOps.length === 0 || docOp[idCtrIdx] < changeOp[idCtrIdx] ||
(docOp[idCtrIdx] === changeOp[idCtrIdx] && docState.actorIds[docOp[idActorIdx]] < idActor)) {
// When we have several operations for the same object and the same key, we want to keep
// them sorted in ascending order by opId. Here we have docOp with a lower opId, so we
// output it first.
takeDocOp = true
updatePatchProperty(patches, newBlock, objectId, docOp, docState, propState, listIndex, docOpOldSuccNum)
// A deletion op in the change is represented in the document only by its entries in the
// succ list of the operations it overwrites; it has no separate row in the set of ops.
for (let i = changeOps.length - 1; i >= 0; i--) {
let deleted = true
for (let j = 0; j < changeOps[i][predNumIdx]; j++) {
if (!predSeen[i][j]) deleted = false
}
if (ACTIONS[changeOps[i][actionIdx]] === 'del' && deleted) {
changeOps.splice(i, 1)
changeCols.splice(i, 1)
predSeen.splice(i, 1)
}
}
} else if (docOp[idCtrIdx] === changeOp[idCtrIdx] && docState.actorIds[docOp[idActorIdx]] === idActor) {
throw new RangeError(`duplicate operation ID: ${changeOp[idCtrIdx]}@${idActor}`)
} else {
// The changeOp has the lower opId, so we output it first.
takeChangeOps = 1
}
} else {
// The document operation comes first if its string key is lexicographically first, or if
// we're using opId keys and the keys don't match (i.e. we scan the document until we find a
// matching key).
takeDocOp = true
}
if (takeDocOp) {
appendOperation(outCols, docState.blocks[blockIndex].columns, docOp)
addBlockOperation(newBlock, docOp, objectId, docState.actorIds, false)
if (docOp[insertIdx] && elemVisible) {
elemVisible = false
listIndex++
}
if (docOp[succNumIdx] === 0) elemVisible = true
newBlock.numOps++
;({ docOp, blockIndex } = readNextDocOp(docState, blockIndex))
if (docOp !== null) {
docOpsConsumed++
docOpOldSuccNum = docOp[succNumIdx]
}
}
if (takeChangeOps > 0) {
for (let i = 0; i < takeChangeOps; i++) {
let op = changeOps[i]
// Check that we've seen all ops mentioned in `pred` (they must all have lower opIds than
// the change op's own opId, so we must have seen them already)
for (let j = 0; j < op[predNumIdx]; j++) {
if (!predSeen[i][j]) {
throw new RangeError(`no matching operation for pred: ${op[predCtrIdx][j]}@${docState.actorIds[op[predActorIdx][j]]}`)
}
}
updatePatchProperty(patches, newBlock, objectId, op, docState, propState, listIndex)
appendOperation(outCols, changeCols[i], op)
addBlockOperation(newBlock, op, objectId, docState.actorIds, true)
if (op[insertIdx]) {
elemVisible = false
listIndex++
} else {
elemVisible = true
}
}
if (takeChangeOps === changeOps.length) {
changeOps.length = 0
changeCols.length = 0
predSeen.length = 0
} else {
changeOps.splice(0, takeChangeOps)
changeCols.splice(0, takeChangeOps)
predSeen.splice(0, takeChangeOps)
}
newBlock.numOps += takeChangeOps
}
}
if (docOp) {
appendOperation(outCols, docState.blocks[blockIndex].columns, docOp)
newBlock.numOps++
if (docOp[objActorIdx] === objActor && docOp[objCtrIdx] === objCtr) {
addBlockOperation(newBlock, docOp, objectId, docState.actorIds, false)
}
}
return {docOpsConsumed, blockIndex}
}