:hedgehog: PostHog is the leading platform for building self-driving products. Our developer tools – AI observability, analytics, session replay, flags, experiments, error tracking, logs, and more – capture all the context agents need to diagnose problems, uncover opportunities, and ship fixes. Steer it all from Slack, web, desktop, or the MCP.
Python ab-testingai-analyticsanalyticscdpdata-warehouseexperimentsfeature-flagsjavascriptproduct-analyticspythonreactsession-replaysurveystypescriptweb-analytics
/**
* Operation layer over NotebookDocument, inspired by ProseMirror steps and React's vdom
* diffing: editing code keeps producing whole documents, and operations are derived after
* the fact by diffing two documents that share node ids. Operations are invertible
* (apply returns the inverse) and transformable (rebase over concurrent operations),
* which is what per-user undo and remote-merge survival are built on. The markdown
* string stays the source of truth — operations are ephemeral, in-memory currency.
*/
import { isTextBlockNode } from './documentModel'
import { parseMarkdownNotebook, serializeNode } from './markdown'
import { reconcileNotebookDocuments } from './reconcile'
import { TextChange, getTextChanges, invertTextChanges, transformTextChanges, tryApplyTextChanges } from './textChanges'
import { NotebookBlockNode, NotebookDocument } from './types'
import { cloneNotebookNode, getNodeFingerprint } from './utils'
export type NotebookTextOperation = {
type: 'text'
nodeId: string
/** Span replacements over the node's serialized markdown. */
changes: TextChange[]
}
export type NotebookInsertBlockOperation = {
type: 'insert_block'
/** Insert after this node; null inserts at the start of the document. */
afterId: string | null
node: NotebookBlockNode
}
export type NotebookDeleteBlockOperation = {
type: 'delete_block'
nodeId: string
}
export type NotebookReplaceBlockOperation = {
type: 'replace_block'
nodeId: string
node: NotebookBlockNode
}
export type NotebookMoveBlockOperation = {
type: 'move_block'
nodeId: string
/** Move after this node; null moves to the start of the document. */
afterId: string | null
}
export type NotebookSetGroupStartOperation = {
type: 'set_group_start'
nodeId: string
startsGroup: boolean
}
export type NotebookOperation =
| NotebookTextOperation
| NotebookInsertBlockOperation
| NotebookDeleteBlockOperation
| NotebookReplaceBlockOperation
| NotebookMoveBlockOperation
| NotebookSetGroupStartOperation
export type NotebookOperationApplyResult = {
document: NotebookDocument
/** Operations that revert the applied ones, ready to apply to the result document. */
inverted: NotebookOperation[]
}
/** Block types whose edits are expressed as text changes over their serialized markdown. */
function isTextDiffableNode(node: NotebookBlockNode): boolean {
return isTextBlockNode(node) || node.type === 'list' || node.type === 'code' || node.type === 'table'
}
/**
* Derive the operations transforming `fromDocument` into `toDocument`. Nodes are matched
* by id, so both documents must come from the same editing session (or a reconcile pass).
*/
export function diffNotebookDocuments(
fromDocument: NotebookDocument,
toDocument: NotebookDocument
): NotebookOperation[] {
const operations: NotebookOperation[] = []
const fromById = new Map(fromDocument.nodes.map((node) => [node.id, node]))
const toById = new Map(toDocument.nodes.map((node) => [node.id, node]))
for (const node of fromDocument.nodes) {
if (!toById.has(node.id)) {
operations.push({ type: 'delete_block', nodeId: node.id })
}
}
// Surviving nodes that fall outside the longest increasing subsequence of original
// positions are the minimal set of moves; anchored moves in target order are stable.
const survivingNodes = toDocument.nodes.filter((node) => fromById.has(node.id))
const fromIndexById = new Map(fromDocument.nodes.map((node, index) => [node.id, index]))
const stableIds = getStableNodeIds(survivingNodes.map((node) => fromIndexById.get(node.id) ?? 0))
survivingNodes.forEach((node, index) => {
if (stableIds.has(index)) {
return
}
operations.push({
type: 'move_block',
nodeId: node.id,
afterId: index === 0 ? null : survivingNodes[index - 1].id,
})
})
toDocument.nodes.forEach((node, index) => {
if (fromById.has(node.id)) {
return
}
operations.push({
type: 'insert_block',
afterId: index === 0 ? null : toDocument.nodes[index - 1].id,
node: cloneNotebookNode(node),
})
})
for (const node of toDocument.nodes) {
const fromNode = fromById.get(node.id)
if (!fromNode) {
continue
}
// A card boundary is outside the node fingerprint (see `startsGroup` in types.ts) and a
// text change can't carry it either, so moving one needs an operation of its own. Undo
// depends on it: without it, reverting a block inserted from the boundary would leave the
// block below stranded in the card the insert gave it.
if (!!fromNode.startsGroup !== !!node.startsGroup) {
operations.push({ type: 'set_group_start', nodeId: node.id, startsGroup: !!node.startsGroup })
}
if (getNodeFingerprint(fromNode) === getNodeFingerprint(node)) {
continue
}
if (isTextDiffableNode(fromNode) && isTextDiffableNode(node)) {
const fromMarkdown = serializeNode(fromNode)
const toMarkdown = serializeNode(node)
if (fromMarkdown !== toMarkdown) {
operations.push({ type: 'text', nodeId: node.id, changes: getTextChanges(fromMarkdown, toMarkdown) })
continue
}
}
operations.push({ type: 'replace_block', nodeId: node.id, node: cloneNotebookNode(node) })
}
return operations
}
/** Indexes (into the sequence) of the longest strictly increasing subsequence. */
function getStableNodeIds(sequence: number[]): Set<number> {
const tailIndexes: number[] = []
const predecessors = new Array<number>(sequence.length).fill(-1)
sequence.forEach((value, index) => {
let low = 0
let high = tailIndexes.length
while (low < high) {
const middle = (low + high) >> 1
if (sequence[tailIndexes[middle]] < value) {
low = middle + 1
} else {
high = middle
}
}
predecessors[index] = low > 0 ? tailIndexes[low - 1] : -1
tailIndexes[low] = index
})
const stable = new Set<number>()
let cursor = tailIndexes.length ? tailIndexes[tailIndexes.length - 1] : -1
while (cursor !== -1) {
stable.add(cursor)
cursor = predecessors[cursor]
}
return stable
}
/**
* Apply operations to a document, returning the result and the inverse operations.
* Returns null when any operation no longer fits the document (stale anchors, spans
* that don't apply, markdown that no longer parses to a single block) — callers treat
* that as "this history entry is stale" rather than guessing.
*/
export function applyNotebookOperations(
document: NotebookDocument,
operations: NotebookOperation[]
): NotebookOperationApplyResult | null {
const nodes = [...document.nodes]
const inverted: NotebookOperation[] = []
for (const operation of operations) {
if (operation.type === 'insert_block') {
if (nodes.some((node) => node.id === operation.node.id)) {
return null
}
const index = getAnchoredIndex(nodes, operation.afterId)
if (index === null) {
return null
}
nodes.splice(index, 0, cloneNotebookNode(operation.node))
inverted.push({ type: 'delete_block', nodeId: operation.node.id })
continue
}
if (operation.type === 'delete_block') {
const index = nodes.findIndex((node) => node.id === operation.nodeId)
if (index === -1) {
return null
}
const [removed] = nodes.splice(index, 1)
inverted.push({
type: 'insert_block',
afterId: index === 0 ? null : nodes[index - 1].id,
node: removed,
})
continue
}
if (operation.type === 'replace_block') {
const index = nodes.findIndex((node) => node.id === operation.nodeId)
if (index === -1) {
return null
}
const previous = nodes[index]
nodes[index] = { ...cloneNotebookNode(operation.node), id: operation.nodeId }
inverted.push({ type: 'replace_block', nodeId: operation.nodeId, node: previous })
continue
}
if (operation.type === 'move_block') {
const index = nodes.findIndex((node) => node.id === operation.nodeId)
if (index === -1) {
return null
}
const previousAfterId = index === 0 ? null : nodes[index - 1].id
const [moved] = nodes.splice(index, 1)
const targetIndex = getAnchoredIndex(nodes, operation.afterId)
if (targetIndex === null) {
return null
}
nodes.splice(targetIndex, 0, moved)
inverted.push({ type: 'move_block', nodeId: operation.nodeId, afterId: previousAfterId })
continue
}
if (operation.type === 'set_group_start') {
const index = nodes.findIndex((node) => node.id === operation.nodeId)
if (index === -1) {
return null
}
const previous = nodes[index]
nodes[index] = { ...previous, startsGroup: operation.startsGroup ? true : undefined }
inverted.push({
type: 'set_group_start',
nodeId: operation.nodeId,
startsGroup: !!previous.startsGroup,
})
continue
}
const index = nodes.findIndex((node) => node.id === operation.nodeId)
if (index === -1) {
return null
}
const baseNode = nodes[index]
const baseMarkdown = serializeNode(baseNode)
const nextMarkdown = tryApplyTextChanges(baseMarkdown, operation.changes)
if (nextMarkdown === null) {
return null
}
const nextNode = parseNodeMarkdownPreservingIdentity(baseNode, nextMarkdown)
if (!nextNode) {
return null
}
nodes[index] = nextNode
inverted.push({
type: 'text',
nodeId: operation.nodeId,
changes: invertTextChanges(baseMarkdown, operation.changes),
})
continue
}
return {
document: { ...document, nodes },
inverted: inverted.reverse(),
}
}
function getAnchoredIndex(nodes: NotebookBlockNode[], afterId: string | null): number | null {
if (afterId === null) {
return 0
}
const anchorIndex = nodes.findIndex((node) => node.id === afterId)
return anchorIndex === -1 ? null : anchorIndex + 1
}
function parseNodeMarkdownPreservingIdentity(
previousNode: NotebookBlockNode,
markdown: string
): NotebookBlockNode | null {
const parsed = parseMarkdownNotebook(markdown)
if (parsed.nodes.length === 0) {
return { id: previousNode.id, type: 'paragraph', children: [] }
}
if (parsed.nodes.length > 1) {
return null
}
// Reconcile against the previous node so list item ids survive the re-parse.
const reconciled = reconcileNotebookDocuments({ type: 'doc', nodes: [previousNode], errors: [] }, parsed).document
const node = reconciled.nodes[0]
return node ? { ...node, id: previousNode.id } : null
}
type NotebookOperationPair = {
/** `a` rebased to apply after `b`; null when it became a no-op. */
a: NotebookOperation | null
/** `b` rebased to apply after `a`; null when it became a no-op. */
b: NotebookOperation | null
}
/**
* Transform two concurrent operations (both rooted at the same document state) past each
* other. Returns null on a genuine conflict that has no coherent resolution — callers
* drop the affected history entries rather than apply garbage.
*/
function transformNotebookOperationPair(a: NotebookOperation, b: NotebookOperation): NotebookOperationPair | null {
const aNodeId = a.type === 'insert_block' ? a.node.id : a.nodeId
const bNodeId = b.type === 'insert_block' ? b.node.id : b.nodeId
if (a.type === 'insert_block' || b.type === 'insert_block') {
if (aNodeId === bNodeId) {
return null
}
if (a.type === 'insert_block' && b.type === 'delete_block' && a.afterId === b.nodeId) {
return null
}
if (b.type === 'insert_block' && a.type === 'delete_block' && b.afterId === a.nodeId) {
return null
}
return { a, b }
}
if (aNodeId !== bNodeId) {
if (a.type === 'move_block' && b.type === 'delete_block' && a.afterId === b.nodeId) {
return null
}
if (b.type === 'move_block' && a.type === 'delete_block' && b.afterId === a.nodeId) {
return null
}
return { a, b }
}
if (a.type === 'text' && b.type === 'text') {
const aChanges = transformTextChanges(a.changes, b.changes, 'against-first')
const bChanges = transformTextChanges(b.changes, a.changes, 'changes-first')
if (aChanges === null || bChanges === null) {
return null
}
return {
a: { ...a, changes: aChanges },
b: { ...b, changes: bChanges },
}
}
if (a.type === 'set_group_start' && b.type === 'set_group_start') {
// Both sides moved the same card boundary: matching values make each side a no-op for
// the other, while opposite values have no resolution that respects both.
return a.startsGroup === b.startsGroup ? { a: null, b: null } : null
}
if (a.type === 'delete_block') {
// After a deletes the node, b has nothing to act on; a survives any change b made.
return { a: b.type === 'delete_block' ? null : a, b: null }
}
if (b.type === 'delete_block') {
return { a: null, b }
}
if (a.type === 'replace_block') {
// A wholesale replace overrides text edits and other replaces on the same node.
return { a, b: b.type === 'move_block' ? b : null }
}
if (b.type === 'replace_block') {
return { a: a.type === 'move_block' ? a : null, b }
}
if (a.type === 'move_block' && b.type === 'move_block') {
return null
}
// What's left touches independent concerns of the same node: a move, a text edit, or a card
// boundary, none of which invalidates the others.
return { a, b }
}
export type NotebookOperationListsPair = {
a: NotebookOperation[]
b: NotebookOperation[]
}
/**
* Transform two concurrent operation lists (both rooted at the same document state) past
* each other: `a` becomes applicable after `b`, and vice versa. Null means conflict.
*/
export function transformNotebookOperationLists(
a: NotebookOperation[],
b: NotebookOperation[]
): NotebookOperationListsPair | null {
let bCurrent = b
const aTransformed: NotebookOperation[] = []
for (const aOperation of a) {
let aCurrent: NotebookOperation | null = aOperation
const bNext: NotebookOperation[] = []
for (const bOperation of bCurrent) {
if (!aCurrent) {
bNext.push(bOperation)
continue
}
const pair = transformNotebookOperationPair(aCurrent, bOperation)
if (!pair) {
return null
}
aCurrent = pair.a
if (pair.b) {
bNext.push(pair.b)
}
}
if (aCurrent) {
aTransformed.push(aCurrent)
}
bCurrent = bNext
}
return { a: aTransformed, b: bCurrent }
}
/**
* Rebase a history stack over operations that just changed the document (a remote merge
* or an external value update). `entries[length - 1]` is the entry that applies to the
* current document; deeper entries apply after the ones above them. Entries that
* genuinely conflict with the incoming operations are dropped along with everything
* older — never the whole stack unless everything conflicts.
*/
export function rebaseNotebookOperationStack<T extends { ops: NotebookOperation[] }>(
entries: T[],
operations: NotebookOperation[]
): T[] {
const rebased: T[] = []
let against = operations
for (let index = entries.length - 1; index >= 0; index--) {
const pair = transformNotebookOperationLists(entries[index].ops, against)
if (!pair) {
break
}
against = pair.b
if (pair.a.length) {
rebased.unshift({ ...entries[index], ops: pair.a })
}
}
return rebased
}