Idempotency & Determinism

Relevant source files

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

• src/merge.ts
• src/reconcile.ts
• test/laws.test.ts
• test/merge.test.ts
• README.md
• AGENTS.md

Idempotency and determinism are core architectural invariants of the keyfold library. These properties ensure that folding a partial delta into a state tree produces predictable results and that repeated applications of the same delta are side-effect-free, specifically regarding memory references. By maintaining these laws, the library allows external stores to efficiently drop duplicate frames using simple equality checks.

Sources: README.md:104-106, AGENTS.md:21-22, test/laws.test.ts:133-145

Core Principles

The merging logic is designed to be purely functional and idempotent. Determinism ensures that for any given base and delta, the resulting state tree is always identical. Idempotency goes a step further in keyfold: re-applying a delta to its own result returns the exact same object reference.

Technical Definitions

Property	Definition in Keyfold
Determinism	Given the same base and delta, the output is always deep-equal.
Value Idempotency	Applying a delta multiple times results in the same value: merge(merge(base, d), d) == merge(base, d).
Reference Idempotency	Applying a delta to its own result returns the previous result by reference (Object.is).
Structural Sharing	Untouched branches of the state tree retain their original memory references.

Sources: test/laws.test.ts:124-145, README.md:104-107

Implementation of Reference Idempotency

Reference idempotency is achieved through "lazy copying." The merger traverses the delta and compares proposed changes against the current values in the base. A new object or array container is only created if at least one property or item within that branch has actually changed.

The following flowchart illustrates the decision logic for maintaining reference integrity during a fold:

Lazy Copying Logic

In src/merge.ts, the foldObject function iterates through delta keys. It keeps a next variable as undefined until a change is detected. Only upon the first detected difference is copyPlainObject called to create a new reference.

// src/merge.ts:89-92
if (!Object.is(folded, baseValue)) {
  next ??= copyPlainObject(base) as Record<PropertyKey, unknown>;
  next[key] = folded;
}

Sources: src/merge.ts:89-92

Keyed List Reconciliation

Determinism in lists is maintained through identity-keyed reconciliation rather than index-based merging. This prevents the "corruption" common in libraries like lodash.merge where mismatched indices lead to duplicate or overwritten data.

1. Stable Order: Suriviving items from the base retain their original relative order.
2. Append Inserts: New items found in the delta that do not exist in the base are appended to the end in the order they appear in the delta.
3. Strict Matching: Identities (strings or numbers) are matched without coercion (e.g., 1 and "1" are distinct).

Algebraic Laws and Validation

The library uses property-based testing (via fast-check) to enforce these laws across arbitrary data structures. This ensures that the implementation remains deterministic and idempotent regardless of nesting depth or data complexity.

Law: No-Op Preservation

If a delta is empty or merely restates values already present in the base, the merger MUST return the base by reference.

// test/merge.test.ts:117-126
test("returns base itself when a delta restates current values", () => {
  const base = profile();
  const next = merge(base, {
    name: "Ada",
    address: { city: "Aarhus" },
  });
  expect(next).toBe(base);
});

Sources: test/merge.test.ts:117-126, test/laws.test.ts:154-158

Law: Failure Safety

A merge that throws due to invalid data (like duplicate identities) must not leave the base tree in a partially mutated state. Since the library is strictly immutable, the base reference is never touched during the reconciliation process.

Sources: src/reconcile.ts:24-27, AGENTS.md:23-24, test/laws.test.ts:172-179

Summary

Idempotency and determinism in keyfold provide a reliable foundation for state management. By ensuring that merge(base, delta) is deterministic and reference-idempotent, the system optimizes performance in reactive environments (like React or Redux) where identity changes trigger re-renders or expensive computations. The architectural choice to use O(delta) traversal combined with O(list) keyed-list scanning ensures these properties are maintained efficiently.

Sources: README.md:104-110, AGENTS.md:39-40 assistant