packages/store/src/lib/RecordsDiff.ts - main - githubmirror/tldraw

packages/store/src/lib/RecordsDiff.ts
329 строк10 KB
Steve Ruiz
refactor(store): share filtered history squashing (#9869)
05 авг 2026, 11:31
05 авг 2026, 11:31d95237b
import { objectMapValues } from '@tldraw/utils'
import { IdOf, UnknownRecord } from './BaseRecord'

/**
 * A diff describing the changes to records, containing collections of records that were added,
 * updated, or removed. This is the fundamental data structure used throughout the store system
 * to track and communicate changes.
 *
 * @example
 * ```ts
 * const diff: RecordsDiff<Book> = {
 *   added: {
 *     'book:1': { id: 'book:1', typeName: 'book', title: 'New Book' }
 *   },
 *   updated: {
 *     'book:2': [
 *       { id: 'book:2', typeName: 'book', title: 'Old Title' }, // from
 *       { id: 'book:2', typeName: 'book', title: 'New Title' }  // to
 *     ]
 *   },
 *   removed: {
 *     'book:3': { id: 'book:3', typeName: 'book', title: 'Deleted Book' }
 *   }
 * }
 * ```
 *
 * @public
 */
export interface RecordsDiff<R extends UnknownRecord> {
	/** Records that were created, keyed by their ID */
	added: Record<IdOf<R>, R>
	/** Records that were modified, keyed by their ID. Each entry contains [from, to] tuple */
	updated: Record<IdOf<R>, [from: R, to: R]>
	/** Records that were deleted, keyed by their ID */
	removed: Record<IdOf<R>, R>
}

/**
 * Creates an empty RecordsDiff with no added, updated, or removed records.
 * This is useful as a starting point when building diffs programmatically.
 *
 * @returns An empty RecordsDiff with all collections initialized to empty objects
 * @example
 * ```ts
 * const emptyDiff = createEmptyRecordsDiff<Book>()
 * // Result: { added: {}, updated: {}, removed: {} }
 * ```
 *
 * @internal
 */
export function createEmptyRecordsDiff<R extends UnknownRecord>(): RecordsDiff<R> {
	return { added: {}, updated: {}, removed: {} } as RecordsDiff<R>
}

/**
 * Creates the inverse of a RecordsDiff, effectively reversing all changes.
 * Added records become removed, removed records become added, and updated records
 * have their from/to values swapped. This is useful for implementing undo operations.
 *
 * @param diff - The diff to reverse
 * @returns A new RecordsDiff that represents the inverse of the input diff
 * @example
 * ```ts
 * const originalDiff: RecordsDiff<Book> = {
 *   added: { 'book:1': newBook },
 *   updated: { 'book:2': [oldBook, updatedBook] },
 *   removed: { 'book:3': deletedBook }
 * }
 *
 * const reversedDiff = reverseRecordsDiff(originalDiff)
 * // Result: {
 * //   added: { 'book:3': deletedBook },
 * //   updated: { 'book:2': [updatedBook, oldBook] },
 * //   removed: { 'book:1': newBook }
 * // }
 * ```
 *
 * @public
 */
export function reverseRecordsDiff(diff: RecordsDiff<any>) {
	const result: RecordsDiff<any> = { added: diff.removed, removed: diff.added, updated: {} }
	for (const [from, to] of objectMapValues(diff.updated)) {
		result.updated[from.id] = [to, from]
	}
	return result
}

/**
 * Checks whether a RecordsDiff contains any changes. A diff is considered empty
 * if it has no added, updated, or removed records.
 *
 * @param diff - The diff to check
 * @returns True if the diff contains no changes, false otherwise
 * @example
 * ```ts
 * const emptyDiff = createEmptyRecordsDiff<Book>()
 * console.log(isRecordsDiffEmpty(emptyDiff)) // true
 *
 * const nonEmptyDiff: RecordsDiff<Book> = {
 *   added: { 'book:1': someBook },
 *   updated: {},
 *   removed: {}
 * }
 * console.log(isRecordsDiffEmpty(nonEmptyDiff)) // false
 * ```
 *
 * @public
 */
export function isRecordsDiffEmpty<T extends UnknownRecord>(diff: RecordsDiff<T>) {
	return !hasAnyKey(diff.added) && !hasAnyKey(diff.updated) && !hasAnyKey(diff.removed)
}

// Cheaper than Object.keys().length, but note that for-in still pays an O(N)
// key-collection prologue on dictionary-mode objects (which diffs become once keys
// are deleted from them) — avoid calling this on large diffs in per-frame hot paths.
/** @internal */
export function hasAnyKey(obj: object) {
	for (const _ in obj) return true
	return false
}

/**
 * Combines multiple RecordsDiff objects into a single consolidated diff.
 * This function intelligently merges changes, handling cases where the same record
 * is modified multiple times across different diffs. For example, if a record is
 * added in one diff and then updated in another, the result will show it as added
 * with the final state.
 *
 * @param diffs - An array of diffs to combine into a single diff
 * @param options - Configuration options for the squashing operation
 *   - mutateFirstDiff - If true, modifies the first diff in place instead of creating a new one
 * @returns A single diff that represents the cumulative effect of all input diffs
 * @example
 * ```ts
 * const diff1: RecordsDiff<Book> = {
 *   added: { 'book:1': { id: 'book:1', title: 'New Book' } },
 *   updated: {},
 *   removed: {}
 * }
 *
 * const diff2: RecordsDiff<Book> = {
 *   added: {},
 *   updated: { 'book:1': [{ id: 'book:1', title: 'New Book' }, { id: 'book:1', title: 'Updated Title' }] },
 *   removed: {}
 * }
 *
 * const squashed = squashRecordDiffs([diff1, diff2])
 * // Result: {
 * //   added: { 'book:1': { id: 'book:1', title: 'Updated Title' } },
 * //   updated: {},
 * //   removed: {}
 * // }
 * ```
 *
 * @public
 */
export function squashRecordDiffs<T extends UnknownRecord>(
	diffs: RecordsDiff<T>[],
	options?: {
		mutateFirstDiff?: boolean
	}
): RecordsDiff<T> {
	if (options?.mutateFirstDiff) {
		const result = diffs[0]
		squashRecordDiffsMutable(result, diffs, 1)
		return result
	}

	const result = { added: {}, removed: {}, updated: {} } as RecordsDiff<T>
	squashRecordDiffsMutable(result, diffs)
	return result
}

/**
 * Applies an array of diffs to a target diff by mutating the target in-place.
 * This is the core implementation used by squashRecordDiffs. It handles complex
 * scenarios where records move between added/updated/removed states across multiple diffs.
 *
 * The function processes each diff sequentially, applying the following logic:
 * - Added records: If the record was previously removed, convert to an update; otherwise add it
 * - Updated records: Chain updates together, preserving the original 'from' state
 * - Removed records: If the record was added in this sequence, cancel both operations
 *
 * @param target - The diff to modify in-place (will be mutated)
 * @param diffs - Array of diffs to apply to the target
 * @example
 * ```ts
 * const targetDiff: RecordsDiff<Book> = {
 *   added: {},
 *   updated: {},
 *   removed: { 'book:1': oldBook }
 * }
 *
 * const newDiffs = [{
 *   added: { 'book:1': newBook },
 *   updated: {},
 *   removed: {}
 * }]
 *
 * squashRecordDiffsMutable(targetDiff, newDiffs)
 * // targetDiff is now: {
 * //   added: {},
 * //   updated: { 'book:1': [oldBook, newBook] },
 * //   removed: {}
 * // }
 * ```
 *
 * @internal
 */
export function squashRecordDiffsMutable<T extends UnknownRecord>(
	target: RecordsDiff<T>,
	diffs: RecordsDiff<T>[],
	fromIndex = 0
): void {
	squashRecordDiffsMutableImpl(target, diffs, fromIndex)
}

/**
 * Applies only records of a given type from an array of diffs to a target diff. Returns the net
 * change in the number of entries in the target.
 *
 * @internal
 */
export function squashRecordDiffsMutableByType<
	T extends UnknownRecord,
	TypeName extends T['typeName'],
>(
	target: RecordsDiff<Extract<T, { typeName: TypeName }>>,
	diffs: RecordsDiff<T>[],
	typeName: TypeName
): number {
	return squashRecordDiffsMutableImpl(target, diffs, 0, typeName)
}

function squashRecordDiffsMutableImpl<T extends UnknownRecord>(
	target: RecordsDiff<T>,
	diffs: RecordsDiff<T>[],
	fromIndex: number,
	typeName?: T['typeName']
): number {
	let sizeChange = 0
	const trackSize = typeName !== undefined

	// This runs on every history interceptor call — e.g. once per input tick while
	// resizing N shapes, with N entries in diff.updated — so the updated loop must not
	// allocate per entry. We use for-in instead of Object.entries, mutate the target's
	// existing [from, to] tuples in place, and skip delete calls against collections we
	// know are empty. In-place tuple mutation is safe because the target exclusively
	// owns its updated tuples: they are always created here (never shared with a source
	// diff), and sources are never mutated.
	for (let i = fromIndex; i < diffs.length; i++) {
		const diff = diffs[i]
		// target.removed can only lose entries before the removed loop below, so a
		// stale `true` is harmless (extra no-op deletes).
		const targetHasRemoved = hasAnyKey(target.removed)

		for (const _id in diff.added) {
			const id = _id as IdOf<T>
			const value = diff.added[id]
			if (typeName !== undefined && value.typeName !== typeName) continue
			if (targetHasRemoved && target.removed[id]) {
				const original = target.removed[id]
				delete target.removed[id]
				if (trackSize) sizeChange--
				if (original !== value) {
					target.updated[id] = [original, value]
					if (trackSize) sizeChange++
				}
			} else {
				if (trackSize && !target.added[id]) sizeChange++
				target.added[id] = value
			}
		}

		// the added loop above may have inserted into target.added
		const targetHasAdded = hasAnyKey(target.added)

		for (const _id in diff.updated) {
			const id = _id as IdOf<T>
			const to = diff.updated[id][1]
			if (typeName !== undefined && to.typeName !== typeName) continue
			if (targetHasAdded && target.added[id]) {
				target.added[id] = to
				if (trackSize && target.updated[id]) sizeChange--
				delete target.updated[id]
				if (targetHasRemoved) {
					if (trackSize && target.removed[id]) sizeChange--
					delete target.removed[id]
				}
				continue
			}
			const existing = target.updated[id]
			if (existing) {
				existing[1] = to
				if (targetHasRemoved) {
					if (trackSize && target.removed[id]) sizeChange--
					delete target.removed[id]
				}
				continue
			}

			// copy the tuple so the target owns it and can mutate it in place later
			target.updated[id] = [diff.updated[id][0], to]
			if (trackSize) sizeChange++
			if (targetHasRemoved) {
				if (trackSize && target.removed[id]) sizeChange--
				delete target.removed[id]
			}
		}

		for (const _id in diff.removed) {
			const id = _id as IdOf<T>
			if (typeName !== undefined && diff.removed[id].typeName !== typeName) continue
			// the same record was added in this diff sequence, just drop it
			if (target.added[id]) {
				delete target.added[id]
				if (trackSize) sizeChange--
			} else if (target.updated[id]) {
				target.removed[id] = target.updated[id][0]
				delete target.updated[id]
			} else {
				if (trackSize && !target.removed[id]) sizeChange++
				target.removed[id] = diff.removed[id]
			}
		}
	}

	return sizeChange
}