// @pdsjs/core/mst - Merkle Search Tree implementation for AT Protocol
// MST for repository structure with proper depth-based layering

import {
  CID,
  cborDecode,
  cborEncodeDagCbor,
  cidToBytes,
  cidToString,
  createCid,
  getKeyDepth,
} from './repo.js';

/**
 * Compute common prefix length between two byte arrays
 * @param {Uint8Array} a
 * @param {Uint8Array} b
 * @returns {number}
 */
function commonPrefixLen(a, b) {
  const minLen = Math.min(a.length, b.length);
  for (let i = 0; i < minLen; i++) {
    if (a[i] !== b[i]) return i;
  }
  return minLen;
}

/**
 * @typedef {Object} MstEntry
 * @property {string} key - Full key (collection/rkey)
 * @property {Uint8Array} keyBytes - UTF-8 encoded key bytes
 * @property {string} cid - Record CID string
 * @property {number} depth - MST depth from key hash
 */

/**
 * Build MST from sorted records
 * @param {Array<{key: string, cid: string}>} records - Records sorted by key
 * @param {(cid: string, data: Uint8Array) => Promise<void>} putBlock - Storage function
 * @returns {Promise<string|null>} Root CID or null if empty
 */
export async function buildMst(records, putBlock) {
  if (records.length === 0) {
    return null;
  }

  // Build entries with pre-computed depths
  /** @type {MstEntry[]} */
  const entries = [];
  let maxDepth = 0;

  for (const r of records) {
    const depth = await getKeyDepth(r.key);
    maxDepth = Math.max(maxDepth, depth);
    entries.push({
      key: r.key,
      keyBytes: new TextEncoder().encode(r.key),
      cid: r.cid,
      depth,
    });
  }

  // Build tree from root (highest layer) down to layer 0
  return buildMstLayer(entries, maxDepth, putBlock);
}

/**
 * Build MST layer recursively
 * @param {MstEntry[]} entries - Entries for this subtree
 * @param {number} layer - Current layer (starts at max, goes to 0)
 * @param {(cid: string, data: Uint8Array) => Promise<void>} putBlock
 * @returns {Promise<string|null>}
 */
async function buildMstLayer(entries, layer, putBlock) {
  if (entries.length === 0) return null;

  // Separate entries: depth == layer stays here, depth < layer goes to subtrees
  /** @type {Array<{type: 'subtree', cid: string|null} | {type: 'entry', entry: MstEntry}>} */
  const thisLayer = [];
  /** @type {MstEntry[]} */
  let leftSubtree = [];

  for (const entry of entries) {
    if (entry.depth < layer) {
      // Belongs to lower layer
      leftSubtree.push(entry);
    } else {
      // Belongs at current layer
      if (leftSubtree.length > 0) {
        const leftCid = await buildMstLayer(leftSubtree, layer - 1, putBlock);
        thisLayer.push({ type: 'subtree', cid: leftCid });
        leftSubtree = [];
      }
      thisLayer.push({ type: 'entry', entry });
    }
  }

  // Handle remaining subtree
  if (leftSubtree.length > 0) {
    const leftCid = await buildMstLayer(leftSubtree, layer - 1, putBlock);
    thisLayer.push({ type: 'subtree', cid: leftCid });
  }

  // Build node in ATProto format
  /** @type {{ e: Array<{p: number, k: Uint8Array, v: CID, t: CID|null}>, l: CID|null }} */
  const node = { e: [], l: null };
  /** @type {string|null} */
  let leftCid = null;
  /** @type {Uint8Array} */
  let prevKeyBytes = new Uint8Array(0);

  for (const item of thisLayer) {
    if (item.type === 'subtree') {
      if (node.e.length === 0) {
        leftCid = item.cid;
      } else if (item.cid !== null) {
        // Attach to previous entry's 't' field
        node.e[node.e.length - 1].t = new CID(cidToBytes(item.cid));
      }
    } else {
      const keyBytes = item.entry.keyBytes;
      const prefixLen = commonPrefixLen(prevKeyBytes, keyBytes);
      const keySuffix = new Uint8Array(
        keyBytes.buffer,
        keyBytes.byteOffset + prefixLen,
        keyBytes.length - prefixLen,
      );

      node.e.push({
        p: prefixLen,
        k: keySuffix,
        v: new CID(cidToBytes(item.entry.cid)),
        t: null,
      });
      prevKeyBytes = new Uint8Array(keyBytes);
    }
  }

  // Set left subtree
  node.l = leftCid ? new CID(cidToBytes(leftCid)) : null;

  // Encode and store
  const nodeBytes = cborEncodeDagCbor(node);
  const nodeCid = await createCid(nodeBytes);
  const cidStr = cidToString(nodeCid);

  await putBlock(cidStr, nodeBytes);

  return cidStr;
}

/**
 * Walk MST and yield all entries in key order
 * @param {string} rootCid - Root CID string
 * @param {(cid: string) => Promise<Uint8Array|null>} getBlock - Block retrieval function
 * @yields {{key: string, cid: string}}
 */
export async function* walkMst(rootCid, getBlock) {
  /** @type {string[]} */
  const keyStack = [];

  /**
   * @param {string} nodeCid
   * @returns {AsyncGenerator<{key: string, cid: string}, void, unknown>}
   */
  async function* walkNode(nodeCid) {
    const data = await getBlock(nodeCid);
    if (!data) return;

    const node = cborDecode(data);

    // Process left subtree first
    if (node.l) {
      yield* walkNode(cidToString(node.l));
    }

    // Process entries
    for (const entry of node.e || []) {
      // Reconstruct key from prefix compression
      const prevKey = keyStack.length > 0 ? keyStack[keyStack.length - 1] : '';
      const prefix = prevKey.slice(0, entry.p);
      const suffix = new TextDecoder().decode(entry.k);
      const key = prefix + suffix;
      keyStack.push(key);

      yield { key, cid: cidToString(entry.v) };

      // Process subtree after this entry
      if (entry.t) {
        yield* walkNode(cidToString(entry.t));
      }
    }
  }

  yield* walkNode(rootCid);
}

/**
 * Collect all MST node blocks (for building CAR files)
 * @param {string} rootCid - Root CID string
 * @param {(cid: string) => Promise<Uint8Array|null>} getBlock - Block retrieval function
 * @returns {Promise<Array<{cid: string, data: Uint8Array}>>}
 */
export async function collectMstBlocks(rootCid, getBlock) {
  /** @type {Array<{cid: string, data: Uint8Array}>} */
  const blocks = [];
  const visited = new Set();

  /**
   * @param {string} cidStr
   */
  async function collect(cidStr) {
    if (visited.has(cidStr)) return;
    visited.add(cidStr);

    const data = await getBlock(cidStr);
    if (!data) return;

    blocks.push({ cid: cidStr, data });

    // Follow child CIDs
    try {
      const node = cborDecode(data);
      if (node.l) {
        await collect(cidToString(node.l));
      }
      if (node.e) {
        for (const entry of node.e) {
          if (entry.t) {
            await collect(cidToString(entry.t));
          }
        }
      }
    } catch {
      // Not an MST node, ignore
    }
  }

  await collect(rootCid);
  return blocks;
}

/**
 * Those of `read`, nodes of the old tree a change read, that the tree at
 * `root` no longer reaches.
 *
 * A changed tree is the nodes the change made and subtrees of the old one.
 * An old node still in it hangs off a made node, or off an old node the
 * change read on its way down, since a change reads every node on the path
 * to what it changes. So a walk from `root` through only those two sets
 * reaches every read node still in the tree.
 * @param {string|null} root
 * @param {Map<string, Uint8Array>} made - Nodes the change made, by CID
 * @param {Map<string, Uint8Array>} read
 * @returns {string[]}
 */
export function unreachedNodes(root, made, read) {
  const reached = new Set();
  const next = root ? [root] : [];
  while (next.length) {
    const cid = /** @type {string} */ (next.pop());
    if (reached.has(cid)) continue;
    reached.add(cid);
    const data = made.get(cid) ?? read.get(cid);
    if (!data) continue;
    const node = cborDecode(data);
    if (node.l) next.push(cidToString(node.l));
    for (const entry of node.e || []) {
      if (entry.t) next.push(cidToString(entry.t));
    }
  }
  return [...read.keys()].filter((cid) => !reached.has(cid));
}

/**
 * Get MST proof blocks for a specific record
 * Returns all blocks needed to verify the record exists in the MST
 * @param {string} rootCid - MST root CID
 * @param {string} targetKey - Key to find (collection/rkey)
 * @param {(cid: string) => Promise<Uint8Array|null>} getBlock
 * @returns {Promise<Array<{cid: string, data: Uint8Array}>>}
 */
export async function getMstProof(rootCid, targetKey, getBlock) {
  /** @type {Array<{cid: string, data: Uint8Array}>} */
  const proofBlocks = [];
  const _targetKeyBytes = new TextEncoder().encode(targetKey);

  /**
   * @param {string} nodeCid
   * @param {Uint8Array} prevKeyBytes
   * @returns {Promise<boolean>} - true if found
   */
  async function findPath(nodeCid, prevKeyBytes) {
    const data = await getBlock(nodeCid);
    if (!data) return false;

    proofBlocks.push({ cid: nodeCid, data });
    const node = cborDecode(data);

    // Check left subtree
    if (node.l) {
      // We need to check if target might be in left subtree
      // For now, include the path - a proper implementation would check bounds
      const found = await findPath(cidToString(node.l), prevKeyBytes);
      if (found) return true;
    }

    // Check entries
    let currentKeyBytes = prevKeyBytes;
    for (const entry of node.e || []) {
      // Reconstruct key
      const prefix = currentKeyBytes.slice(0, entry.p);
      const suffix = entry.k;
      const keyBytes = new Uint8Array(prefix.length + suffix.length);
      keyBytes.set(prefix);
      keyBytes.set(suffix, prefix.length);
      currentKeyBytes = keyBytes;

      const key = new TextDecoder().decode(keyBytes);
      if (key === targetKey) {
        return true;
      }

      // Check subtree
      if (entry.t) {
        const found = await findPath(cidToString(entry.t), currentKeyBytes);
        if (found) return true;
      }
    }

    return false;
  }

  await findPath(rootCid, new Uint8Array(0));
  return proofBlocks;
}

// ────────────────────────────────────────────────────────────────────────────
// Incremental updates
//
// buildMst above rebuilds the whole tree, which costs O(n) per commit. These
// operations touch only the nodes on one root-to-key path, relying on content
// addressing for structural sharing: an untouched child keeps its CID, so it
// needs no rewrite. They must produce byte-identical trees to buildMst —
// packages/core/test/mst-incremental.test.js asserts that against it.
//
// Layers are dense: a child sits exactly one layer below its parent, and a
// skipped layer is represented by an entry-less node carrying only `l`. The
// algorithm follows the AT Protocol MST spec, as implemented by
// bluesky-social/atproto (dual MIT/Apache-2.0).
// ────────────────────────────────────────────────────────────────────────────

/**
 * @typedef {Object} MstNodeEntry
 * @property {string} key - Full key
 * @property {string} value - Record CID
 * @property {string|null} right - Subtree covering keys after this entry
 */

/**
 * @typedef {Object} MstNode
 * @property {string|null} left - Subtree covering keys before the first entry
 * @property {MstNodeEntry[]} entries
 */

/**
 * @typedef {Object} MstStore
 * @property {(cid: string) => Promise<Uint8Array|null>} getBlock
 * @property {(cid: string, data: Uint8Array) => Promise<void>} putBlock
 */

/**
 * Decode a stored MST node, undoing prefix compression.
 * @param {Uint8Array} bytes
 * @returns {MstNode}
 */
function decodeMstNode(bytes) {
  const raw = cborDecode(bytes);
  /** @type {MstNodeEntry[]} */
  const entries = [];
  let prevBytes = new Uint8Array(0);

  for (const e of raw.e || []) {
    const keyBytes = new Uint8Array(e.p + e.k.length);
    keyBytes.set(prevBytes.subarray(0, e.p));
    keyBytes.set(e.k, e.p);
    entries.push({
      key: new TextDecoder().decode(keyBytes),
      value: cidToString(e.v),
      right: e.t ? cidToString(e.t) : null,
    });
    prevBytes = keyBytes;
  }

  return { left: raw.l ? cidToString(raw.l) : null, entries };
}

/**
 * Store a node, re-applying prefix compression. Returns null for a node with
 * nothing in it, which the parent records as an absent subtree.
 * @param {MstNode} node
 * @param {MstStore} store
 * @returns {Promise<string|null>}
 */
async function storeMstNode(node, store) {
  if (node.entries.length === 0 && !node.left) return null;

  /** @type {Array<{p: number, k: Uint8Array, v: CID, t: CID|null}>} */
  const e = [];
  let prevBytes = new Uint8Array(0);

  for (const entry of node.entries) {
    const keyBytes = new TextEncoder().encode(entry.key);
    const p = commonPrefixLen(prevBytes, keyBytes);
    e.push({
      p,
      k: keyBytes.slice(p),
      v: new CID(cidToBytes(entry.value)),
      t: entry.right ? new CID(cidToBytes(entry.right)) : null,
    });
    prevBytes = keyBytes;
  }

  const bytes = cborEncodeDagCbor({
    e,
    l: node.left ? new CID(cidToBytes(node.left)) : null,
  });
  const cid = cidToString(await createCid(bytes));
  await store.putBlock(cid, bytes);
  return cid;
}

/**
 * @param {string} cid
 * @param {MstStore} store
 * @returns {Promise<MstNode>}
 */
async function loadMstNode(cid, store) {
  const bytes = await store.getBlock(cid);
  if (!bytes) throw new Error(`Missing MST node: ${cid}`);
  return decodeMstNode(bytes);
}

/**
 * Index at which `key` belongs among sorted entries.
 * @param {MstNodeEntry[]} entries
 * @param {string} key
 * @returns {number}
 */
function indexFor(entries, key) {
  let i = 0;
  while (i < entries.length && entries[i].key < key) i++;
  return i;
}

/**
 * Layer of the tree rooted at `cid`, derived from the depth of a key it holds.
 * @param {string|null} cid
 * @param {MstStore} store
 * @returns {Promise<number|null>}
 */
async function treeLayer(cid, store) {
  if (!cid) return null;
  const node = await loadMstNode(cid, store);
  if (node.entries.length > 0) return getKeyDepth(node.entries[0].key);
  if (node.left) {
    const below = await treeLayer(node.left, store);
    return below === null ? null : below + 1;
  }
  return null;
}

/**
 * Split a subtree into the parts holding keys below and above `key`.
 * @param {string|null} cid
 * @param {number} layer
 * @param {string} key
 * @param {MstStore} store
 * @returns {Promise<[string|null, string|null]>}
 */
async function splitAround(cid, layer, key, store) {
  if (!cid) return [null, null];
  const node = await loadMstNode(cid, store);
  const i = indexFor(node.entries, key);

  // The subtree spanning the split point has to be divided as well
  const straddling = i === 0 ? node.left : node.entries[i - 1].right;
  const [innerLeft, innerRight] = straddling
    ? await splitAround(straddling, layer - 1, key, store)
    : [null, null];

  const leftEntries = node.entries.slice(0, i).map((e) => ({ ...e }));
  if (i > 0) leftEntries[i - 1].right = innerLeft;

  const left = await storeMstNode(
    { left: i === 0 ? innerLeft : node.left, entries: leftEntries },
    store,
  );
  const right = await storeMstNode(
    { left: innerRight, entries: node.entries.slice(i).map((e) => ({ ...e })) },
    store,
  );
  return [left, right];
}

/**
 * Join two subtrees covering adjacent key ranges.
 * @param {string|null} leftCid
 * @param {string|null} rightCid
 * @param {number} layer
 * @param {MstStore} store
 * @returns {Promise<string|null>}
 */
async function mergeTrees(leftCid, rightCid, layer, store) {
  if (!leftCid) return rightCid;
  if (!rightCid) return leftCid;

  const left = await loadMstNode(leftCid, store);
  const right = await loadMstNode(rightCid, store);

  if (left.entries.length === 0) {
    // Nothing at this layer on the left: its subtree joins the right's
    const merged = await mergeTrees(left.left, right.left, layer - 1, store);
    return storeMstNode(
      { left: merged, entries: right.entries.map((e) => ({ ...e })) },
      store,
    );
  }

  const entries = [
    ...left.entries.map((e) => ({ ...e })),
    ...right.entries.map((e) => ({ ...e })),
  ];
  const seam = left.entries.length - 1;
  entries[seam].right = await mergeTrees(
    left.entries[seam].right,
    right.left,
    layer - 1,
    store,
  );
  return storeMstNode({ left: left.left, entries }, store);
}

/**
 * @param {string|null} cid
 * @param {number} layer
 * @param {string} key
 * @param {number} depth
 * @param {string} value
 * @param {MstStore} store
 * @returns {Promise<string|null>}
 */
async function addRecurse(cid, layer, key, depth, value, store) {
  const node = cid
    ? await loadMstNode(cid, store)
    : /** @type {MstNode} */ ({ left: null, entries: [] });
  const i = indexFor(node.entries, key);

  if (depth === layer) {
    // A key already sitting at this position takes the new value in place.
    // Splicing beside it would leave two entries sharing a key, which breaks
    // the strict ordering every verifier checks: the repo stops being
    // provable, and consumers that require proofs drop it entirely.
    if (node.entries[i]?.key === key) {
      const entries = node.entries.map((e) => ({ ...e }));
      entries[i].value = value;
      return storeMstNode({ left: node.left, entries }, store);
    }

    // Belongs in this node; anything spanning its position splits around it
    const straddling = i === 0 ? node.left : node.entries[i - 1].right;
    const [innerLeft, innerRight] = straddling
      ? await splitAround(straddling, layer - 1, key, store)
      : [null, null];

    const entries = node.entries.map((e) => ({ ...e }));
    entries.splice(i, 0, { key, value, right: innerRight });
    if (i > 0) entries[i - 1].right = innerLeft;

    return storeMstNode(
      { left: i === 0 ? innerLeft : node.left, entries },
      store,
    );
  }

  // Belongs further down; descend into the subtree covering its position
  const target = i === 0 ? node.left : node.entries[i - 1].right;
  const child = await addRecurse(target, layer - 1, key, depth, value, store);
  const entries = node.entries.map((e) => ({ ...e }));
  if (i > 0) entries[i - 1].right = child;

  return storeMstNode({ left: i === 0 ? child : node.left, entries }, store);
}

/**
 * Add a key to the tree, returning the new root CID.
 * @param {string|null} rootCid - Existing root, or null for an empty tree
 * @param {string} key - Full key (collection/rkey)
 * @param {string} value - Record CID
 * @param {MstStore} store
 * @returns {Promise<string|null>}
 */
export async function mstAdd(rootCid, key, value, store) {
  const depth = await getKeyDepth(key);
  if (!rootCid) {
    return storeMstNode(
      { left: null, entries: [{ key, value, right: null }] },
      store,
    );
  }

  const layer = /** @type {number} */ (await treeLayer(rootCid, store));
  if (depth <= layer) {
    return addRecurse(rootCid, layer, key, depth, value, store);
  }

  // Deeper than the current root: the existing tree splits and sinks beneath a
  // new root, with entry-less nodes filling any layers the key skips over.
  let [left, right] = await splitAround(rootCid, layer, key, store);
  for (let i = 0; i < depth - layer - 1; i++) {
    if (left) left = await storeMstNode({ left, entries: [] }, store);
    if (right) right = await storeMstNode({ left: right, entries: [] }, store);
  }
  return storeMstNode({ left, entries: [{ key, value, right }] }, store);
}

/**
 * @param {string|null} cid
 * @param {number} layer
 * @param {string} key
 * @param {number} depth
 * @param {MstStore} store
 * @returns {Promise<string|null>}
 */
async function deleteRecurse(cid, layer, key, depth, store) {
  if (!cid) return null;
  const node = await loadMstNode(cid, store);

  if (depth === layer) {
    const idx = node.entries.findIndex((e) => e.key === key);
    if (idx === -1) return cid;

    // The subtrees on either side of the removed entry become adjacent
    const before = idx === 0 ? node.left : node.entries[idx - 1].right;
    const merged = await mergeTrees(
      before,
      node.entries[idx].right,
      layer - 1,
      store,
    );
    const entries = node.entries
      .filter((_, i) => i !== idx)
      .map((e) => ({ ...e }));
    if (idx > 0) entries[idx - 1].right = merged;

    return storeMstNode(
      { left: idx === 0 ? merged : node.left, entries },
      store,
    );
  }

  const i = indexFor(node.entries, key);
  const target = i === 0 ? node.left : node.entries[i - 1].right;
  const child = await deleteRecurse(target, layer - 1, key, depth, store);
  const entries = node.entries.map((e) => ({ ...e }));
  if (i > 0) entries[i - 1].right = child;

  return storeMstNode({ left: i === 0 ? child : node.left, entries }, store);
}

/**
 * Remove a key from the tree, returning the new root CID (null when empty).
 * @param {string|null} rootCid
 * @param {string} key
 * @param {MstStore} store
 * @returns {Promise<string|null>}
 */
export async function mstDelete(rootCid, key, store) {
  if (!rootCid) return null;
  const depth = await getKeyDepth(key);
  const layer = /** @type {number} */ (await treeLayer(rootCid, store));
  if (depth > layer) return rootCid;

  let root = await deleteRecurse(rootCid, layer, key, depth, store);

  // Removing the deepest key can leave entry-less layers on top
  while (root) {
    const node = await loadMstNode(root, store);
    if (node.entries.length > 0 || !node.left) break;
    root = node.left;
  }
  return root;
}

/**
 * @param {string} cid
 * @param {number} layer
 * @param {string} key
 * @param {number} depth
 * @param {string} value
 * @param {MstStore} store
 * @returns {Promise<string|null>} New CID, or null if the key was absent
 */
async function updateRecurse(cid, layer, key, depth, value, store) {
  const node = await loadMstNode(cid, store);

  if (depth === layer) {
    const idx = node.entries.findIndex((e) => e.key === key);
    if (idx === -1) return null;
    const entries = node.entries.map((e) => ({ ...e }));
    entries[idx].value = value;
    return storeMstNode({ left: node.left, entries }, store);
  }

  const i = indexFor(node.entries, key);
  const target = i === 0 ? node.left : node.entries[i - 1].right;
  if (!target) return null;
  const child = await updateRecurse(
    target,
    layer - 1,
    key,
    depth,
    value,
    store,
  );
  if (child === null) return null;

  const entries = node.entries.map((e) => ({ ...e }));
  if (i > 0) entries[i - 1].right = child;
  return storeMstNode({ left: i === 0 ? child : node.left, entries }, store);
}

/**
 * The record CID stored at `key`, or null if the tree does not hold it.
 * @param {string|null} rootCid
 * @param {string} key
 * @param {MstStore} store
 * @returns {Promise<string|null>}
 */
export async function mstGet(rootCid, key, store) {
  let cid = rootCid;
  while (cid) {
    const node = await loadMstNode(cid, store);
    const i = indexFor(node.entries, key);
    if (node.entries[i]?.key === key) return node.entries[i].value;
    cid = i === 0 ? node.left : node.entries[i - 1].right;
  }
  return null;
}

/**
 * Replace the value at an existing key. The key set is unchanged, so the tree
 * keeps its shape. Returns the root unchanged if the key is absent.
 * @param {string|null} rootCid
 * @param {string} key
 * @param {string} value - New record CID
 * @param {MstStore} store
 * @returns {Promise<string|null>}
 */
export async function mstUpdate(rootCid, key, value, store) {
  if (!rootCid) return null;
  const depth = await getKeyDepth(key);
  const layer = /** @type {number} */ (await treeLayer(rootCid, store));
  if (depth > layer) return rootCid;
  const updated = await updateRecurse(rootCid, layer, key, depth, value, store);
  return updated ?? rootCid;
}

/**
 * Undo `ops` on the tree rooted at `rootCid`, as a sync 1.1 consumer checks a
 * commit: a create is deleted, an update and a delete put back the CID they
 * replaced (`prev`). Returns the root that leaves, which for a sound commit
 * is the previous one, and every block undoing read from `getBlock`, by CID.
 * Nodes undoing makes are kept apart, and not counted as read.
 * @param {string|null} rootCid
 * @param {Array<{action: string, key: string, prev?: string}>} ops - In the order applied
 * @param {(cid: string) => Promise<Uint8Array|null>} getBlock
 * @returns {Promise<{root: string|null, read: Map<string, Uint8Array>}>}
 */
export async function mstInvert(rootCid, ops, getBlock) {
  /** @type {Map<string, Uint8Array>} */
  const made = new Map();
  /** @type {Map<string, Uint8Array>} */
  const read = new Map();
  /** @type {MstStore} */
  const store = {
    async getBlock(cid) {
      const ours = made.get(cid);
      if (ours) return ours;
      const data = await getBlock(cid);
      if (data) read.set(cid, data);
      return data;
    },
    async putBlock(cid, data) {
      made.set(cid, data);
    },
  };
  let root = rootCid;
  for (const op of [...ops].reverse()) {
    if (op.action === 'create') {
      root = await mstDelete(root, op.key, store);
    } else if (op.prev && op.action === 'update') {
      root = await mstUpdate(root, op.key, op.prev, store);
    } else if (op.prev && op.action === 'delete') {
      root = await mstAdd(root, op.key, op.prev, store);
    }
  }
  return { root, read };
}