@repo/datadata/utils

Utilities shared across datadata and its consumers: JSON Patch application, prototype-safe own-key access, and fractional indexing for ordered lists.

Functions

applyJsonPatch

export declare function applyJsonPatch<T>(doc: T, ops: readonly Operation[]): T;

Apply ops — a patch already accepted once: from the log, from the server, or this client's own — to doc, returning the new document. doc is never modified.

Copy-on-write: the result shares with doc every container the patch did not change or pass through, so treat both as immutable — the client's cached documents are frozen, and a caller that means to mutate a result deep-copies it first (cloneJson). The result shares nothing with ops.

All or nothing, and total: a patch that does not apply throws a JsonPatchError — for ANY ops the wire's shape check lets through — and leaves nothing half-applied. Callers that race patches against a moving base classify it with isPatchTestFailure / isPatchDriftError.

deleteOwn

export declare function deleteOwn(table: {
    [key: string]: unknown;
}, key: string): void;

Remove the own property key from table. Equivalent to delete table[key], which never touches an inherited member; it exists so computed-key access goes through one seam.

detectIndexCollisions

export declare function detectIndexCollisions<T extends IndexedItem>(items: Record<string, T>): Array<{
    index: string;
    ids: string[];
}>;

Detects index collisions in an ordered collection.

This utility function identifies groups of items that share the same fractional index value. While the tie-breaker mechanism in getOrderedItems() ensures deterministic ordering using record keys (IDs), index collisions can cause issues with operations like moveOrderedItem().

**When Do Collisions Occur?** - Multiple clients concurrently insert items at the same position - Both clients calculate the same index before synchronizing - The fractional indexing algorithm is deterministic, so identical before/after contexts produce identical indices

**Use Cases:** - Debugging: Identify problematic indices in development - Monitoring: Track collision frequency in production - Validation: Check for collisions before attempting move operations - Repair: Find indices that need to be spread out

Parameters

• items

  Record of items with string index properties

Returns

Array of collision groups, each containing the shared index and affected item IDs

Example

const items = {
  a: { id: 'a', index: 'a1' },
  b: { id: 'b', index: 'a1' },  // Collision with 'a'
  c: { id: 'c', index: 'a2' },
  d: { id: 'd', index: 'a1' },  // Collision with 'a' and 'b'
};

const collisions = detectIndexCollisions(items);
// Returns: [{ index: 'a1', ids: ['a', 'b', 'd'] }]

fillAutoIndices

export declare function fillAutoIndices(existingIndices: readonly string[], count: number, mode: "append" | "prepend"): string[];

Generate count fresh fractional indices that place new items relative to a set of already-present ones — the engine behind a schema's autoIndex field (see the validator's record case). existingIndices is the indices already carried by the record's entries; only the structurally valid ones bound the generation (a corrupt neighbour is ignored here and reported by the per-entry format check instead). The returned keys are ascending, so assigning them to the new entries in insertion order preserves that order: - "append" → all keys sort *after* the current maximum (new items land at the end, in the order they were added); - "prepend" → all keys sort *before* the current minimum (new items land at the front, still in the order they were added).

Pure and deterministic in its inputs, so the client's optimistic fill and the server's authoritative fill converge on the same keys.

generateIndices

export declare function generateIndices(count: number): string[];

Generates a sequence of N fractional indices for migration purposes.

This helper function is useful when migrating existing unordered records to use fractional indexing. It generates a deterministic sequence of indices that can be assigned to existing items.

**Important:** The caller is responsible for mapping the generated indices to their existing record keys. This provides maximum flexibility for different migration scenarios.

Parameters

• count

  Number of indices to generate (must be non-negative)

Returns

Array of fractional index strings in ascending order

Example

// Migrate an existing record
const existingItems = { a: { name: 'First' }, b: { name: 'Second' } };
const indices = generateIndices(Object.keys(existingItems).length);
// indices = ['a0', 'a1']

// Apply to existing keys
const keys = Object.keys(existingItems);
keys.forEach((key, i) => {
  existingItems[key].index = indices[i];
});

getIndexForAppend

export declare function getIndexForAppend<TItem extends IndexedItem>(items: Record<string, TItem>): string;

Calculates the fractional index for a new item to be appended at the end of the list.

This is a pure function that returns the calculated index without mutating anything. Use this when creating new items that should appear at the end of an ordered collection.

Parameters

• items

  Record of items with string index properties

Returns

A fractional index string that sorts after all existing items

Example

const items = { a: { id: 'a', index: 'a0' }, b: { id: 'b', index: 'a1' } };

// Create a new item with the correct index from the start
const newItem = { id: 'c', index: getIndexForAppend(items) };
// newItem.index is 'a2' (after 'a1')

getIndexForInsertAt

export declare function getIndexForInsertAt<TItem extends IndexedItem>(items: Record<string, TItem>, position: number): string;

Calculates the fractional index for a new item to be inserted at a specific position.

This is a pure function that returns the calculated index without mutating anything. Use this when creating new items that should appear at a specific position in an ordered collection.

Parameters

• items

  Record of items with string index properties

• position

  The target position (0-based index) where the new item should appear

Returns

A fractional index string that places the item at the specified position

Throws

An Error if position is out of range (valid: 0 to the item count, inclusive)

Throws

An Error if the neighbouring items carry identical (collided) indices

Example

const items = { a: { id: 'a', index: 'a0' }, b: { id: 'b', index: 'a2' } };

// Insert a new item between positions 0 and 1
const newItem = { id: 'c', index: getIndexForInsertAt(items, 1) };
// newItem.index is 'a1' (between 'a0' and 'a2')

getIndexForPrepend

export declare function getIndexForPrepend<TItem extends IndexedItem>(items: Record<string, TItem>): string;

Calculates the fractional index for a new item to be prepended at the start of the list.

This is a pure function that returns the calculated index without mutating anything. Use this when creating new items that should appear at the beginning of an ordered collection.

Parameters

• items

  Record of items with string index properties

Returns

A fractional index string that sorts before all existing items

Example

const items = { a: { id: 'a', index: 'a0' }, b: { id: 'b', index: 'a1' } };

// Create a new item at the start
const newItem = { id: 'c', index: getIndexForPrepend(items) };
// newItem.index is 'Zz' (before 'a0')

getOrderedIds

export declare function getOrderedIds<K extends string, T extends IndexedItem>(items: Record<K, T>): K[];

Extracts the IDs (record keys) in sorted order based on fractional indices.

This is a convenience function for when you only need the ordered IDs rather than the full items. Useful for rendering sorted lists or iterating over items in a specific order.

Parameters

• items

  Record of items with string index properties

Returns

Sorted array of record keys (IDs) ordered by their index values

Example

const items = {
  a: { id: 'a', index: 'a1', name: 'Second' },
  b: { id: 'b', index: 'a0', name: 'First' },
  c: { id: 'c', index: 'a2', name: 'Third' }
};
const orderedIds = getOrderedIds(items);
// Returns: ['b', 'a', 'c']

getOrderedItems

export declare function getOrderedItems<T extends IndexedItem>(items: Record<string, T>): T[];

Sorts items by their fractional index property using lexicographic comparison.

Parameters

• items

  Record of items with string index properties

Returns

Sorted array of items ordered by their index values

Example

const items = {
  a: { index: 'a1', name: 'Second' },
  b: { index: 'a0', name: 'First' },
  c: { index: 'a2', name: 'Third' }
};
const sorted = getOrderedItems(items);
// Returns: [{ index: 'a1' ... }, { index: 'a0' ... }, { index: 'a2' ... }]

getOwn

export declare function getOwn<V>(table: {
    readonly [key: string]: V;
} | undefined, key: string): V | undefined;

The value stored under key as an own property of table, or undefined (also for an inherited member such as "constructor"). Takes an optional table so an entry?.[kind] read keeps its shape.

indexBetween

export declare function indexBetween(before: string | null, after: string | null): string;

The fractional index that sorts strictly between before and after, where a null bound means "open" (no neighbour on that side). This is the single primitive every placement reduces to: appending is indexBetween(max, null), prepending is indexBetween(null, min), and inserting between two siblings is indexBetween(a, b).

Unlike the IndexedItem helpers below it carries no opinion about where the key lives — the caller passes the neighbouring key values directly — so a consumer whose order key is a field other than index (e.g. the document editor reading an arbitrary format: "fractionalIndex" field) can compute placements without reshaping its data into { index } items first. Deterministic in its inputs.

Throws

if before and after are the same non-null string (the library rejects a zero gap) — callers placing between possibly-colliding neighbours should guard for equal bounds. Two null bounds are the open "insert anywhere" case and yield a valid first key. Reversed bounds (before > after) are *not* rejected: v4 normalises them to a midpoint rather than throwing, so this cannot be relied on to catch a caller that swapped its arguments.

isInheritedKey

export declare function isInheritedKey(obj: object, key: string): boolean;

Whether key resolves on obj only through its prototype chain: an inherited member, not an entry. Tells a path that escapes through the prototype apart from one that does not resolve.

isValidFractionalIndex

export declare function isValidFractionalIndex(key: unknown): key is string;

Whether key is a structurally valid fractional index — i.e. a string generateKeyBetween could have produced and will accept back as a neighbour.

This is the gate behind the schema's { type: "string", format: "fractionalIndex" }: an index that fails here would break ordering (a bad head makes getIntegerPart throw, a non-base-62 digit makes the midpoint math produce garbage, a trailing zero violates the no-trailing-zero invariant the algorithm relies on). It reconstructs the package's validateOrderKey (which the library does not export) and additionally enforces the base-62 alphabet, so every key the library *generates* passes and the obvious corruptions don't.

Rules, in order: - non-empty string; - not the reserved smallest key A + twenty-six 0s (the library forbids it); - a legal head whose encoded integer-part length fits within the key; - every character is a base-62 digit; - the fractional part (everything after the integer part) has no trailing 0.

lookup

export declare function lookup<T extends object, K extends keyof T & string>(table: T, key: string extends K ? never : K): T[K];

The entry of a table keyed by a closed union (a constant lookup table, or a schema-shaped entry read by an operation kind), where the type system already names every key. The key parameter refuses a value of type string, so a wire-controlled key cannot reach a table through here; use getOwn for that. A key the type names but the table lacks answers undefined, as for a Partial table. For plain-object tables only: a class instance keeps its methods on the prototype, where this does not look.

moveOrderedItem

export declare function moveOrderedItem<TItem extends IndexedItem>(items: Record<string, TItem>, item: TItem, from: number, to: number): void;

Moves an item from one position to another using fractional indexing.

This function calculates a new fractional index for the item based on the indices of neighboring items. The algorithm generates a deterministic midpoint between the before and after indices.

**Important:** This function mutates the item.index property directly. In a real-time collaboration context, this mutation should be wrapped in an appropriate transaction or update operation.

**Index Collision Handling:** If the target position is between two items with identical indices, this function will throw an error. This scenario can occur when multiple clients concurrently insert items at the same position. To resolve this, consider: 1. Using detectIndexCollisions() to identify problematic indices 2. Declaring healCollisions on the index field, so validation re-spreads settled collisions at the write boundary on client and server alike 3. Retrying the operation after synchronization

Parameters

• items

  Record of items with string index properties

• item

  The item to move (must be in the record)

• from

  Current index position in the sorted order

• to

  Target index position in the sorted order

Throws

An Error if attempting to move between items with identical indices

Example

const items = { a: { id: 'a', index: 'a0' }, b: { id: 'b', index: 'a1' } };

// Move item from position 1 to position 0
moveOrderedItem(items, items.b, 1, 0);
// items.b.index is now between null and 'a0' (e.g., 'Zz')

moveOrderedItemToEnd

export declare function moveOrderedItemToEnd<TItem extends IndexedItem>(items: Record<string, TItem>, item: TItem): void;

Moves an existing item to the end of the ordered list by mutating its index.

**Important:** This function mutates the item.index property directly. For creating new items, prefer using getIndexForAppend() which is a pure function that returns the index without mutation.

Parameters

• items

  Record of items with string index properties

• item

  The existing item to move to the end

Example

const items = { a: { id: 'a', index: 'a0' }, b: { id: 'b', index: 'a1' } };

// Move an existing item to the end
moveOrderedItemToEnd(items, items.a);
// items.a.index is now 'a2' (after 'a1')

recordEntries

export declare function recordEntries<K extends string, V>(record: Readonly<Record<K, V>>): [K, V][];

Object.entries that preserves the record's key type. TypeScript pins Object.entries / Object.keys to plain-string keys, so iterating a record with BRANDED keys (a schema record field with keyBrand) silently discards the brand and every consumer re-adds it with a cast. This is the one place that cast lives instead — sound for records whose key type is exact, like a schema's inferred Record<BrandedId, V>, where a key can hold nothing but the brand.

setOwn

export declare function setOwn<V>(table: {
    [key: string]: V;
}, key: string, value: V): void;

Store value as an own, enumerable property of table under key, including "__proto__", which a plain assignment would treat as a prototype swap.

Interfaces

IndexedItem

export interface IndexedItem

A value in an ordered record: anything with a fractional index.

index?: string;

The item's fractional index; items sort by it in ascending order. Optional because a format: "fractionalIndex" field with autoIndex may arrive without one until the validator fills it in. The helpers treat an absent index as unplaced: it sorts ahead of every real key and bounds nothing.