: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
import { parseMarkdownNotebook, serializeMarkdownNotebook, serializeNode } from './markdown'
import { getStableComponentKey, reconcileNotebookDocuments } from './reconcile'
import { applyTextChanges, getTextChanges, transformTextChanges, tryApplyTextChanges } from './textChanges'
import {
NotebookBlockNode,
NotebookCollaborationConflict,
NotebookComponentBlockNode,
NotebookDocument,
NotebookPropValue,
} from './types'
import { cloneNotebookNode, getNodeFingerprint, getNodeSignature } from './utils'
export type { TextChange } from './textChanges'
export { tryApplyTextChanges } from './textChanges'
export type NotebookMarkdownMergeInput = {
baseMarkdown: string
localMarkdown: string
remoteMarkdown: string
}
export type NotebookMarkdownMergeResult = {
mergedMarkdown: string
document: NotebookDocument
conflicts: NotebookCollaborationConflict[]
}
export function mergeNotebookMarkdownChanges({
baseMarkdown,
localMarkdown,
remoteMarkdown,
}: NotebookMarkdownMergeInput): NotebookMarkdownMergeResult {
const baseDocument = parseMarkdownNotebook(baseMarkdown)
const localDocument = reconcileNotebookDocuments(baseDocument, parseMarkdownNotebook(localMarkdown)).document
const remoteDocument = reconcileNotebookDocuments(baseDocument, parseMarkdownNotebook(remoteMarkdown)).document
const baseById = new Map(baseDocument.nodes.map((node) => [node.id, node]))
const localById = new Map(localDocument.nodes.map((node) => [node.id, node]))
const remoteById = new Map(remoteDocument.nodes.map((node) => [node.id, node]))
const remoteIndexById = new Map(remoteDocument.nodes.map((node, index) => [node.id, index]))
const outputNodes: NotebookBlockNode[] = []
const outputIds = new Set<string>()
const conflicts: NotebookCollaborationConflict[] = []
remoteDocument.nodes.forEach((remoteNode) => {
const baseNode = baseById.get(remoteNode.id)
const localNode = localById.get(remoteNode.id)
if (!baseNode) {
pushOutputNode(outputNodes, outputIds, remoteNode)
return
}
if (!localNode) {
if (getNodeFingerprint(baseNode) !== getNodeFingerprint(remoteNode)) {
conflicts.push({
nodeId: remoteNode.id,
reason: 'Remote changed a block that was deleted locally',
localMarkdown: '',
remoteMarkdown: serializeNode(remoteNode),
})
}
return
}
const baseFingerprint = getNodeFingerprint(baseNode)
const localFingerprint = getNodeFingerprint(localNode)
const remoteFingerprint = getNodeFingerprint(remoteNode)
const localChanged = localFingerprint !== baseFingerprint
const remoteChanged = remoteFingerprint !== baseFingerprint
const pushMergedNode = (node: NotebookBlockNode): void =>
pushOutputNode(outputNodes, outputIds, withMergedGroupStart(baseNode, localNode, remoteNode, node))
if (localChanged && remoteChanged && localFingerprint !== remoteFingerprint) {
const mergedComponentNode = mergeNotebookComponentNodes(baseNode, localNode, remoteNode)
if (mergedComponentNode) {
pushMergedNode(mergedComponentNode)
return
}
const mergedNode = mergeNotebookBlockNodeText(baseNode, localNode, remoteNode)
if (mergedNode) {
pushMergedNode(mergedNode)
return
}
conflicts.push({
nodeId: remoteNode.id,
reason: 'Local and remote edited the same block',
localMarkdown: serializeNode(localNode),
remoteMarkdown: serializeNode(remoteNode),
})
pushMergedNode(localNode)
return
}
pushMergedNode(localChanged ? localNode : remoteNode)
})
// The deletion still wins (re-adding would resurrect deleted blocks on every merge),
// but the user must hear about their edit being discarded.
baseDocument.nodes.forEach((baseNode) => {
if (remoteById.has(baseNode.id)) {
return
}
const localNode = localById.get(baseNode.id)
if (localNode && getNodeFingerprint(localNode) !== getNodeFingerprint(baseNode)) {
conflicts.push({
nodeId: baseNode.id,
reason: 'Remote deleted a block that was edited locally',
localMarkdown: serializeNode(localNode),
remoteMarkdown: '',
})
}
})
localDocument.nodes.forEach((localNode, localIndex) => {
if (!baseById.has(localNode.id) && !remoteById.has(localNode.id)) {
if (
mergeLocalOnlyNodeWithRemoteOnlyOutput(
outputNodes,
outputIds,
baseById,
localById,
remoteIndexById,
localDocument.nodes,
remoteDocument.nodes,
localIndex,
localNode
)
) {
return
}
insertLocalOnlyNode(outputNodes, outputIds, localDocument.nodes, localIndex, localNode)
}
})
const document: NotebookDocument = {
type: 'doc',
nodes: outputNodes,
errors: [...localDocument.errors, ...remoteDocument.errors],
}
return {
document,
mergedMarkdown: serializeMarkdownNotebook(document),
conflicts,
}
}
// `startsGroup` is deliberately outside a node's fingerprint — folding it in would churn the
// content-derived node id every time a card is split — so it merges on its own three-way rule:
// whichever side moved the card boundary away from base wins.
function withMergedGroupStart(
baseNode: NotebookBlockNode,
localNode: NotebookBlockNode,
remoteNode: NotebookBlockNode,
mergedNode: NotebookBlockNode
): NotebookBlockNode {
const startsGroup = baseNode.startsGroup === localNode.startsGroup ? remoteNode.startsGroup : localNode.startsGroup
return startsGroup === mergedNode.startsGroup ? mergedNode : { ...mergedNode, startsGroup }
}
function pushOutputNode(nodes: NotebookBlockNode[], outputIds: Set<string>, node: NotebookBlockNode): void {
if (outputIds.has(node.id)) {
return
}
nodes.push(cloneNotebookNode(node))
outputIds.add(node.id)
}
function insertLocalOnlyNode(
nodes: NotebookBlockNode[],
outputIds: Set<string>,
localNodes: NotebookBlockNode[],
localIndex: number,
node: NotebookBlockNode
): void {
if (outputIds.has(node.id)) {
return
}
const clonedNode = cloneNotebookNode(node)
const previousAnchor = localNodes
.slice(0, localIndex)
.reverse()
.find((candidate) => outputIds.has(candidate.id))
if (previousAnchor) {
const previousOutputIndex = nodes.findIndex((candidate) => candidate.id === previousAnchor.id)
if (previousOutputIndex !== -1) {
nodes.splice(previousOutputIndex + 1, 0, clonedNode)
outputIds.add(clonedNode.id)
return
}
}
const nextAnchor = localNodes.slice(localIndex + 1).find((candidate) => outputIds.has(candidate.id))
if (nextAnchor) {
const nextOutputIndex = nodes.findIndex((candidate) => candidate.id === nextAnchor.id)
if (nextOutputIndex !== -1) {
nodes.splice(nextOutputIndex, 0, clonedNode)
outputIds.add(clonedNode.id)
return
}
}
nodes.push(clonedNode)
outputIds.add(clonedNode.id)
}
type SharedAnchorIds = {
previousId?: string
nextId?: string
}
function mergeLocalOnlyNodeWithRemoteOnlyOutput(
nodes: NotebookBlockNode[],
outputIds: Set<string>,
baseById: Map<string, NotebookBlockNode>,
localById: Map<string, NotebookBlockNode>,
remoteIndexById: Map<string, number>,
localNodes: NotebookBlockNode[],
remoteNodes: NotebookBlockNode[],
localIndex: number,
localNode: NotebookBlockNode
): boolean {
const localAnchors = getSharedAnchorIds(localNodes, localIndex, baseById)
for (let outputIndex = 0; outputIndex < nodes.length; outputIndex++) {
const remoteOnlyNode = nodes[outputIndex]
if (baseById.has(remoteOnlyNode.id) || localById.has(remoteOnlyNode.id)) {
continue
}
const remoteIndex = remoteIndexById.get(remoteOnlyNode.id)
if (remoteIndex === undefined) {
continue
}
const remoteAnchors = getSharedAnchorIds(remoteNodes, remoteIndex, baseById)
if (!areSharedAnchorIdsEqual(localAnchors, remoteAnchors)) {
continue
}
const mergedNode = mergeInsertedNotebookBlockNodes(localNode, remoteOnlyNode)
if (!mergedNode) {
continue
}
if (outputIds.has(mergedNode.id) && mergedNode.id !== remoteOnlyNode.id) {
return false
}
nodes[outputIndex] = mergedNode
outputIds.delete(remoteOnlyNode.id)
outputIds.add(mergedNode.id)
return true
}
return false
}
function getSharedAnchorIds(
nodes: NotebookBlockNode[],
index: number,
baseById: Map<string, NotebookBlockNode>
): SharedAnchorIds {
let previousId: string | undefined
for (let previousIndex = index - 1; previousIndex >= 0; previousIndex--) {
const candidate = nodes[previousIndex]
if (baseById.has(candidate.id)) {
previousId = candidate.id
break
}
}
let nextId: string | undefined
for (let nextIndex = index + 1; nextIndex < nodes.length; nextIndex++) {
const candidate = nodes[nextIndex]
if (baseById.has(candidate.id)) {
nextId = candidate.id
break
}
}
return { previousId, nextId }
}
function areSharedAnchorIdsEqual(left: SharedAnchorIds, right: SharedAnchorIds): boolean {
return left.previousId === right.previousId && left.nextId === right.nextId
}
function mergeInsertedNotebookBlockNodes(
localNode: NotebookBlockNode,
remoteNode: NotebookBlockNode
): NotebookBlockNode | null {
// The same component inserted on both sides (typically a block racing its own save
// echo) must collapse to one node, with the local side's prop values winning.
if (localNode.type === 'component' && remoteNode.type === 'component') {
if (localNode.tagName !== remoteNode.tagName) {
return null
}
const localKey = getStableComponentKey(localNode)
if (
(localKey !== null && localKey === getStableComponentKey(remoteNode)) ||
getNodeFingerprint(localNode) === getNodeFingerprint(remoteNode)
) {
return {
...cloneNotebookNode(localNode),
props: { ...remoteNode.props, ...localNode.props },
}
}
return null
}
if (!isMergeableInsertedTextNode(localNode) || !isMergeableInsertedTextNode(remoteNode)) {
return null
}
if (getNodeSignature(localNode) !== getNodeSignature(remoteNode)) {
return null
}
const localMarkdown = serializeNode(localNode)
const remoteMarkdown = serializeNode(remoteNode)
if (localMarkdown === remoteMarkdown || isInsertedNodeMarkdownPrefix(localNode, remoteMarkdown, localMarkdown)) {
return cloneNotebookNode(localNode)
}
if (isInsertedNodeMarkdownPrefix(remoteNode, localMarkdown, remoteMarkdown)) {
return {
...cloneNotebookNode(remoteNode),
id: localNode.id,
}
}
// Nearly identical versions of one new block are the same block racing its own save
// (a typo fixed mid-word before the save response landed): keep the local, newer
// lineage. The threshold is deliberately tight — genuinely different content written
// by two people at the same spot must stay separate.
const changes = getTextChanges(remoteMarkdown, localMarkdown)
const changedUnits = changes.reduce(
(total, change) => total + Math.max(change.end - change.start, change.text.length),
0
)
if (changedUnits * 5 <= Math.max(localMarkdown.length, remoteMarkdown.length)) {
return cloneNotebookNode(localNode)
}
return null
}
function isMergeableInsertedTextNode(node: NotebookBlockNode): boolean {
return (
node.type === 'paragraph' ||
node.type === 'heading' ||
node.type === 'blockquote' ||
node.type === 'list' ||
node.type === 'code'
)
}
function isInsertedNodeMarkdownPrefix(node: NotebookBlockNode, shorter: string, longer: string): boolean {
if (node.type === 'list') {
return longer === shorter || longer.startsWith(`${shorter}\n`)
}
return longer.startsWith(shorter)
}
/**
* Per-prop three-way merge for two edits of the same component node, instead of treating
* the whole tag as one atomic value. Props changed by only one side merge cleanly; string
* props changed by both sides merge at the text level (so concurrent typing into a prompt
* question, or a streaming AI answer racing a save echo, composes instead of conflicting).
* Returns null when any prop genuinely conflicts — the caller falls back to its conflict
* handling.
*/
function mergeNotebookComponentNodes(
baseNode: NotebookBlockNode,
localNode: NotebookBlockNode,
remoteNode: NotebookBlockNode
): NotebookBlockNode | null {
if (
baseNode.type !== 'component' ||
localNode.type !== 'component' ||
remoteNode.type !== 'component' ||
baseNode.tagName !== localNode.tagName ||
localNode.tagName !== remoteNode.tagName
) {
return null
}
const propKeys = new Set([
...Object.keys(baseNode.props),
...Object.keys(localNode.props),
...Object.keys(remoteNode.props),
])
const mergedProps: NotebookComponentBlockNode['props'] = {}
for (const key of propKeys) {
const baseValue = baseNode.props[key]
const localValue = localNode.props[key]
const remoteValue = remoteNode.props[key]
const localChanged = !arePropValuesEqual(localValue, baseValue)
const remoteChanged = !arePropValuesEqual(remoteValue, baseValue)
let mergedValue: NotebookComponentBlockNode['props'][string] | undefined
const idArrayMerge = !localChanged
? null
: mergeIdKeyedArrayPropValues(baseValue ?? [], localValue, remoteValue)
if (!localChanged) {
mergedValue = remoteValue
} else if (!remoteChanged || arePropValuesEqual(localValue, remoteValue)) {
mergedValue = localValue
} else if (idArrayMerge) {
mergedValue = idArrayMerge
} else if (typeof baseValue === 'string' && typeof localValue === 'string' && typeof remoteValue === 'string') {
const textMerge = mergeTextChanges(baseValue, localValue, remoteValue)
if (textMerge.conflicted) {
return null
}
mergedValue = textMerge.text
} else {
return null
}
if (mergedValue !== undefined) {
mergedProps[key] = mergedValue
}
}
return {
...cloneNotebookNode(localNode),
props: mergedProps,
// The merged props no longer match either side's source tag
raw: undefined,
errors: undefined,
}
}
type IdKeyedEntry = { [key: string]: NotebookPropValue } & { id: string }
/**
* Three-way merge for array props whose entries are objects keyed by a unique string `id`
* (component-level lists being the motivating case). Entries added on either side survive,
* entries deleted on one side stay deleted, and an entry edited on one side takes that side's
* version. Returns null when the shape doesn't qualify — the caller falls back to its other
* strategies.
*/
function mergeIdKeyedArrayPropValues(
baseValue: NotebookPropValue | undefined,
localValue: NotebookPropValue | undefined,
remoteValue: NotebookPropValue | undefined
): NotebookPropValue[] | null {
const base = asIdKeyedArray(baseValue)
const local = asIdKeyedArray(localValue)
const remote = asIdKeyedArray(remoteValue)
if (!base || !local || !remote) {
return null
}
const baseById = new Map(base.map((entry) => [entry.id, entry]))
const localById = new Map(local.map((entry) => [entry.id, entry]))
const merged: IdKeyedEntry[] = []
const mergedIds = new Set<string>()
const push = (entry: IdKeyedEntry): void => {
if (!mergedIds.has(entry.id)) {
merged.push(entry)
mergedIds.add(entry.id)
}
}
for (const localEntry of local) {
const baseEntry = baseById.get(localEntry.id)
const remoteEntry = remote.find((entry) => entry.id === localEntry.id)
if (baseEntry && !remoteEntry) {
// Deleted remotely; a concurrent deletion must not resurrect on every merge.
continue
}
if (remoteEntry && baseEntry && arePropValuesEqual(localEntry, baseEntry)) {
push(remoteEntry)
continue
}
push(localEntry)
}
// Entries the remote side added (or that local deleted but remote edited) are inserted
// after their closest surviving remote predecessor, keeping both sides' ordering intact.
remote.forEach((remoteEntry, remoteIndex) => {
if (mergedIds.has(remoteEntry.id)) {
return
}
const baseEntry = baseById.get(remoteEntry.id)
if (baseEntry && !localById.has(remoteEntry.id) && arePropValuesEqual(remoteEntry, baseEntry)) {
// Deleted locally and untouched remotely: the deletion wins.
return
}
let insertIndex = merged.length
for (let previousIndex = remoteIndex - 1; previousIndex >= 0; previousIndex--) {
const anchorPosition = merged.findIndex((entry) => entry.id === remote[previousIndex].id)
if (anchorPosition !== -1) {
insertIndex = anchorPosition + 1
break
}
}
merged.splice(insertIndex, 0, remoteEntry)
mergedIds.add(remoteEntry.id)
})
return merged
}
function asIdKeyedArray(value: NotebookPropValue | undefined): IdKeyedEntry[] | null {
if (!Array.isArray(value)) {
return null
}
const ids = new Set<string>()
for (const entry of value) {
if (!entry || typeof entry !== 'object' || Array.isArray(entry)) {
return null
}
const id = entry.id
if (typeof id !== 'string' || !id || ids.has(id)) {
return null
}
ids.add(id)
}
return value as IdKeyedEntry[]
}
function arePropValuesEqual(
left: NotebookComponentBlockNode['props'][string] | undefined,
right: NotebookComponentBlockNode['props'][string] | undefined
): boolean {
if (left === undefined || right === undefined) {
return left === right
}
return JSON.stringify(left) === JSON.stringify(right)
}
function mergeNotebookBlockNodeText(
baseNode: NotebookBlockNode,
localNode: NotebookBlockNode,
remoteNode: NotebookBlockNode
): NotebookBlockNode | null {
const baseMarkdown = serializeNode(baseNode)
const localMarkdown = serializeNode(localNode)
const remoteMarkdown = serializeNode(remoteNode)
const mergeResult = mergeTextChanges(baseMarkdown, localMarkdown, remoteMarkdown)
if (mergeResult.conflicted) {
return null
}
const mergedDocument = parseMarkdownNotebook(mergeResult.text)
if (mergedDocument.nodes.length !== 1) {
return null
}
const reconciledMergedDocument = reconcileNotebookDocuments(
{ type: 'doc', nodes: [localNode], errors: [] },
mergedDocument
).document
const mergedNode = reconciledMergedDocument.nodes[0]
if (!mergedNode) {
return null
}
return {
...mergedNode,
id: localNode.id,
}
}
const CRC32_TABLE = ((): Uint32Array => {
const table = new Uint32Array(256)
for (let i = 0; i < 256; i++) {
let value = i
for (let bit = 0; bit < 8; bit++) {
value = value & 1 ? 0xedb88320 ^ (value >>> 1) : value >>> 1
}
table[i] = value >>> 0
}
return table
})()
/** CRC-32 of the string's UTF-16-LE bytes. Mirrors `markdown_crc` in collab.py (zlib.crc32). */
export function markdownCrc(text: string): number {
let crc = 0xffffffff
for (let i = 0; i < text.length; i++) {
const unit = text.charCodeAt(i)
crc = (crc >>> 8) ^ CRC32_TABLE[(crc ^ (unit & 0xff)) & 0xff]
crc = (crc >>> 8) ^ CRC32_TABLE[(crc ^ ((unit >>> 8) & 0xff)) & 0xff]
}
return (crc ^ 0xffffffff) >>> 0
}
type TextMergeResult = {
text: string
conflicted: boolean
}
/**
* Three-way merge of concurrent edits to one block's markdown, ProseMirror-rebase style:
* the remote changes are already committed, so local changes are transformed to apply on
* top of them. Insertions always survive and deletions union, so neither side's typing
* is ever discarded — at worst both replacements of the same words end up side by side
* (remote first) and the next save round-trips the result to everyone.
*/
function mergeTextChanges(baseText: string, localText: string, remoteText: string): TextMergeResult {
if (localText === remoteText) {
return { text: localText, conflicted: false }
}
if (baseText === localText) {
return { text: remoteText, conflicted: false }
}
if (baseText === remoteText) {
return { text: localText, conflicted: false }
}
const localChanges = getTextChanges(baseText, localText)
const remoteChanges = getTextChanges(baseText, remoteText)
const rebasedLocalChanges = transformTextChanges(localChanges, remoteChanges, 'against-first')
if (rebasedLocalChanges === null) {
return { text: localText, conflicted: true }
}
const mergedText = tryApplyTextChanges(applyTextChanges(baseText, remoteChanges), rebasedLocalChanges)
if (mergedText === null) {
return { text: localText, conflicted: true }
}
return { text: mergedText, conflicted: false }
}