Array Item Tombstones

Relevant source files

The following files were used as context for generating this wiki page:

• src/reconcile.ts
• src/sentinels.ts
• src/merge.ts
• src/types.ts
• README.md
• test/reconcile.test.ts

Array Item Tombstones are a specialized mechanism within keyfold used to explicitly remove items from keyed lists during a state merge operation. Unlike standard JSON Merge Patch, which treats arrays as opaque values to be replaced, keyfold utilizes these tombstones to perform granular reconciliation of list items based on their unique identities.

A tombstone is represented by a partial object containing the item's identity field and a reserved $delete property set to true. When the reconciler encounters this structure in a delta, it removes the corresponding item from the base state while preserving the order of other surviving elements.

Sources: README.md:16-24, src/reconcile.ts:133-149

Core Mechanism

The reconciliation process identifies tombstones during the indexing phase of a delta list. An item is classified as a tombstone if it contains the $delete key. The library enforces strict rules on the structure of these objects to prevent ambiguity and ensure deterministic behavior.

Tombstone Definition and Validation

A valid tombstone must meet the following criteria:

1. It must be a plain object.
2. It must contain the identity field (e.g., id or sku) configured via keyBy.
3. It must contain the property $delete set exactly to true.
4. It must not contain any other fields (except the identity and $delete).

Sources: src/reconcile.ts:133-149, test/reconcile.test.ts:153-165

Data Flow for Tombstones

The following diagram illustrates how the reconcile function processes tombstones compared to standard item patches.

The reconciler iterates through the base list, checking if each item's identity exists in the indexed delta patches. If a match is found and it is marked as a tombstone, the item is omitted from the resulting array. Sources: src/reconcile.ts:36-64

Implementation Details

The $delete Reserved Key

The $delete field is a reserved keyword for keyed list reconciliation. It cannot be used as a legitimate data field within items belonging to a keyed list. If a base state item is found to contain $delete, the merger will throw a KeyfoldMergeError.

Sources: src/reconcile.ts:42-46, test/reconcile.test.ts:210-214

Reconcile Function Logic

The reconcile function in src/reconcile.ts manages the lifecycle of a tombstone:

// src/reconcile.ts:54-57
if (patch.tombstone) {
  changed = true;
  continue; // Skip adding to the 'next' array
}

If a tombstone refers to an identity that does not exist in the base list, it is treated as a no-op. This ensures that delete operations are idempotent; applying the same tombstone multiple times results in the same state without error.

Sources: src/reconcile.ts:68-75, AGENTS.md:50-51

Comparison of Deletion Types

keyfold distinguishes between three types of deletions depending on the context of the data structure.

Operation	Syntax	Scope	Result
Field Delete	DELETE (Symbol)	Object Properties	Removes the key from the object.
Item Tombstone	{$delete: true}	Keyed List Items	Removes the entire item from the array.
Wire Delete	DELETE_TOKEN	JSON Transport	Maps to DELETE symbol if wireDeletes is enabled.

Sources: src/types.ts:46-52, README.md:92-101, src/sentinels.ts:2-5

Constraints and Error Handling

To maintain structural integrity, the library enforces several constraints regarding tombstones. Violation of these rules results in a KeyfoldMergeError.

• Mixed Tombstones: A tombstone cannot carry additional patch fields. For example, { id: "a", $delete: true, quantity: 5 } is invalid.
• Non-Boolean Values: The $delete key must be strictly true. Values like false, null, or 1 will cause a throw.
• Duplicate Identities: A delta cannot contain a tombstone and a patch for the same ID.
• Base Data Integrity: The base state is checked for the reserved $delete key to ensure the reconciler doesn't misinterpret existing data as an operator.

Sources: src/reconcile.ts:133-149, test/reconcile.test.ts:153-165, test/reconcile.test.ts:210-214

Summary

Array Item Tombstones provide a deterministic way to manage removals in keyed collections without requiring a full array replacement. By utilizing the $delete: true convention, keyfold maintains immutable state updates while preserving the original ordering of unmentioned items and ensuring that deletions are idempotent across multiple merge cycles.

Sources: README.md:144-150, AGENTS.md:32-34