function mergeDocChangeOps()

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}
}