function seekToOp()

in backend/new.js [224:309]

• 56 lines of code
• 26 McCabe index (conditional complexity)

function seekToOp(docState, ops) {
  const { objActor, objCtr, keyActor, keyCtr, keyStr } = ops
  let blockIndex = 0, totalVisible = 0

  // Skip any blocks that contain only objects with lower objectIds
  if (objCtr !== null) {
    while (blockIndex < docState.blocks.length - 1) {
      const blockActor = docState.blocks[blockIndex].lastObjectActor === undefined ? undefined
        : docState.actorIds[docState.blocks[blockIndex].lastObjectActor]
      const blockCtr = docState.blocks[blockIndex].lastObjectCtr
      if (blockCtr === undefined || blockCtr < objCtr || (blockCtr === objCtr && blockActor < objActor)) {
        blockIndex++
      } else {
        break
      }
    }
  }

  if (keyStr !== null) {
    // String key is used. First skip any blocks that contain only lower keys
    while (blockIndex < docState.blocks.length - 1) {
      const blockLastKey = docState.blocks[blockIndex].lastKey[ops.objId]
      if (blockLastKey !== undefined && blockLastKey < keyStr) blockIndex++; else break
    }

    // When we have a candidate block, decode it to find the exact insertion position
    const {skipCount} = seekWithinBlock(ops, docState.blocks[blockIndex].columns, docState.actorIds, false)
    return {blockIndex, skipCount, visibleCount: 0}

  } else {
    // List operation
    const insertAtHead = keyCtr === null || keyCtr === 0 || keyActor === null
    const keyActorNum = keyActor === null ? null : docState.actorIds.indexOf(keyActor)
    let resumeInsertion = false

    while (true) {
      // Search for the reference element, skipping any blocks whose Bloom filter does not contain
      // the reference element. We only do this if not inserting at the head (in which case there is
      // no reference element), or if we already found the reference element in an earlier block (in
      // which case we have resumeInsertion === true). The latter case arises with concurrent
      // insertions at the same position, and so we have to scan beyond the reference element to
      // find the actual insertion position, and that further scan crosses a block boundary.
      if (!insertAtHead && !resumeInsertion) {
        while (blockIndex < docState.blocks.length - 1 &&
               !bloomFilterContains(docState.blocks[blockIndex].bloom, keyActorNum, keyCtr)) {
          // If we reach the end of the list object without a Bloom filter hit, the reference element
          // doesn't exist
          if (docState.blocks[blockIndex].lastObjectCtr > objCtr) {
            throw new RangeError(`Reference element not found: ${keyCtr}@${keyActor}`)
          }

          // Add up number of visible list elements in any blocks we skip, for list index computation
          totalVisible += visibleListElements(docState, blockIndex, ops.objId)
          blockIndex++
        }
      }

      // We have a candidate block. Decode it to see whether it really contains the reference element
      const {found, skipCount, visibleCount} = seekWithinBlock(ops,
                                                               docState.blocks[blockIndex].columns,
                                                               docState.actorIds,
                                                               resumeInsertion)

      if (blockIndex === docState.blocks.length - 1) {
        // Last block: if we haven't found the reference element by now, it's an error
        if (found) {
          return {blockIndex, skipCount, visibleCount: totalVisible + visibleCount}
        } else {
          throw new RangeError(`Reference element not found: ${keyCtr}@${keyActor}`)
        }

      } else if (found && skipCount < docState.blocks[blockIndex].numOps) {
        // The insertion position lies within the current block
        return {blockIndex, skipCount, visibleCount: totalVisible + visibleCount}
      }

      // Reference element not found and there are still blocks left ==> it was probably a false positive.
      // Reference element found, but we skipped all the way to the end of the block ==> we need to
      // continue scanning the next block to find the actual insertion position.
      // Either way, go back round the loop again to skip blocks until the next Bloom filter hit.
      resumeInsertion = found && ops.insert
      totalVisible += visibleListElements(docState, blockIndex, ops.objId)
      blockIndex++
    }
  }
}