# Proposal: Counted Reversible Overlay Diffs

## Summary

Use **per-key change counts carried by both overlay state and diffs**, together
with distinct operations for confirming a prefix and reverting a suffix. Keep
`phantom_removals` to distinguish cancellation from deletion of an existing
value.

This is a design proposal. The complete design has not been implemented in the
repository.

The required behavior is:

- Apply diffs oldest-first and revert them newest-first.
- Replay diffs on other overlays with a compatible logical starting state.
- Preserve later pending changes when an earlier prefix reaches the database.
- Clear all pending state when all represented changes have been applied.
- Support empty values, cancellations, repeated values, and tree lifecycle
  changes on both Fjall and Sled.
- Avoid rebuilding the entire remaining sequence during cleanup or rollback.

## 1. The information missing from the current state

Consider:

```text
D0: insert k, remove k
D1: insert k=v
D2: remove k
```

The final raw overlay state contains `removed[k]`. D0's diff contains a phantom
removal for the same key.

The current state-cleanup loop removes that marker unconditionally:

```rust
for k in diff.removed.keys().chain(diff.phantom_removals.iter()) {
    self.removed.remove(k);
}
```

Two histories require different results:

| Pending history | Current raw state | Required state after confirming D0 |
| --- | --- | --- |
| D0 alone | `removed = {k}` | Empty |
| D0, D1, D2 | `removed = {k}` | Keep `removed[k]` for D2 |

The flattened state and D0 alone cannot distinguish these cases. Value equality
does not solve the equivalent problem for repeated writes either:

```text
D0: insert k=v
D1: remove k
D2: insert k=v
```

Clearing the cached value merely because it matches D0 would erase D2's pending
insertion.

## 2. Count recorded changes, not captured diff objects

For each key:

- The overlay stores the total number of outstanding recorded edits.
- A diff stores how many of those edits it represents.
- A new recorded edit increments the overlay's count.
- Replaying a diff adds **that diff's count**, rather than incrementing once.

Conceptually, each key's diff is:

```text
(before, after, change_count)
```

The existing value representation can remain:

- `cache`: insertion or replacement, including the previous value.
- `removed`: deletion of an existing value, including that value.
- `phantom_removals`: absent-to-absent cancellation.

Counts are additional metadata. An absent key remains distinct from an existing
key whose value is empty.

These counts are relative contributions, **not global IDs or timestamps**. A
diff carries its own contribution, not the source overlay's entire cumulative
count.

### Required invariants

- Calling `diff()` repeatedly does not change counts.
- Uncaptured edits are already counted and therefore protected.
- `inverse()` swaps the value transition and preserves the count.
- Combining diffs adds their contributions.
- No-op value transitions retain their counted metadata until consumed.
- Zero-count pending entries are removed.
- All mutation paths preserve the accounting, including replay, clear,
  checkpoints, and clones.

Counting registered diff objects instead would require a separate registration
lifecycle, special handling for uncaptured edits, and additional handling for
diffs that aggregate several blocks.

## 3. Confirmation and reversion are different operations

### Confirm an applied prefix

After successfully writing a diff to the database:

1. Subtract its count from each affected key.
2. If the remaining count is positive, preserve the current overlay entry.
3. If the count reaches zero, clear the entry and counter.

Do not compare values to decide whether a later change exists. A phantom-only
diff still requires confirmation even though it produces no database writes.

Confirmation is valid only for a prefix represented in that overlay. Counts do
not establish that an arbitrary incoming diff belongs to its pending history.

### Revert a pending suffix

When undoing the newest pending diff:

1. Subtract its counts.
2. Where earlier changes remain, restore the diff's **before-value** into the
   overlay.
3. Where no changes remain, remove the overlay entry and inherit from the
   backend.

The diff already carries the previous values needed for ordered rollback. This
does not require last-touch history or replay of the entire remaining sequence.
The operation must undo a suffix; newer edits must be reverted first.

### Stage an inverse as new work

This is distinct from removing a pending suffix:

```rust
overlay.add_diff(&diff.inverse())?;
```

Staging an inverse **adds** its counts. It does not implicitly unregister the
original diff. This distinction is particularly important because a phantom-only
diff equals its own inverse.

Reverting an already-applied database change uses the inverse transition. Its
original pending contribution has already been consumed and must not be
subtracted again.

## 4. Worked example

```text
D0: insert k, remove k   -> count 2
D1: insert k=v          -> count 1
D2: remove k            -> count 1
```

The final live state contains:

```text
removed[k]
change_count[k] = 4
```

Confirmation proceeds as follows:

| Applied diff | Remaining count | Overlay action |
| --- | ---: | --- |
| D0 | 2 | Preserve `removed[k]` |
| D1 | 1 | Preserve `removed[k]`, hiding the backend's `v` |
| D2 | 0 | Clear the marker and counter |

For **D0 alone**, the count starts at 2. Applying D0 subtracts 2 and clears
everything.

For `insert v -> remove -> insert v`, the later insertion remains represented
until its own contribution is consumed. Identical values no longer confuse
cleanup.

## 5. Diff subtraction must account for counts

For one key, subtracting a prefix means:

```text
Current: B -> C, representing n edits
Prefix:  B -> A, representing m edits

Result:  A -> C, representing n-m edits
```

This assumes the prefix belongs to the represented history and shares the
starting state. If edits remain, retain the resulting entry even when its
before-value and after-value are equal.

For the cancellation example:

```text
Combined snapshot: absent -> absent, count 4
Subtract D0:       absent -> absent, count 2
Subtract D1:       v      -> absent, count 1
```

D2 becomes a real removal with previous value `v`.

Subtracting D0 no longer makes the intermediate diff empty: it still represents
two outstanding edits. This also prevents the database layer from prematurely
dropping this tree entry.

Relevant emptiness and equality checks must respect the remaining change
metadata. Batch generation can omit transitions requiring no database writes,
while retaining their metadata for cleanup.

## 6. Replay on another overlay

When overlay B imports a diff from A:

1. Apply its value transitions to B's pending state.
2. Add its count contributions to B's existing counts.

No source-overlay IDs or source-global counters are copied.

### Starting-state compatibility

Portability has an essential semantic condition:

```text
Source diff: A -> B
Destination currently contains C
```

Applying that diff's inverse restores **A**, not **C**. Therefore, replay must
start from the expected logical before-state. Deliberately applying it to a
different state requires producing a rebased diff with the destination's actual
previous values.

### Keep the operations explicit

- Append a diff to an overlay.
- Write a diff to the database.
- Confirm a known pending prefix after it was written.
- Revert a pending suffix.

Writing an incoming diff must not automatically consume unrelated pending
changes merely because their keys, values, or counts match.

For overlays sharing a backend, one writer can write a common prefix and the
other overlays can confirm that same prefix locally. Each overlay updates its
own accounting exactly once.

## 7. Tree lifecycle needs separate reversible state

A complete database-level fix cannot stop at key counters.

Creation, dropping, and restoration must carry explicit reversible lifecycle
information, including:

- Whether the tree existed before and after the change.
- The logical contents needed to undo a drop.
- Pending overlay state preserved while the tree is hidden.
- The structural change's outstanding contribution.

In particular:

- An empty tree is different from a nonexistent tree.
- A drop's undo image must reflect the logical state **before that diff**,
  including earlier pending changes.
- That image must remain separate from mutable pending-state bookkeeping.
- Whole-tree cleanup must respect later key and lifecycle changes.
- Restoration must correctly update initial/new/dropped-tree bookkeeping.
- Double inversion must preserve the lifecycle transition and its metadata.

The existing dropped-tree issue needs its dedicated fix. Key counters alone
cannot repair it.

## 8. Cost

Confirmation and pending rollback are proportional to the keys in the affected
diff, with normal map-lookup costs. They do not clone all remaining values or
replay the entire sequence.

Counts add per-key numeric metadata in state and diffs, plus any associated map
overhead. They do not require another copy of all value history.

The existing `diff(&sequence)` calculation still has its sequence-subtraction
cost. This design does not eliminate that cost.

## 9. Validation

The counted key-transition rules were exercised in a bounded single-key model
covering **18,489 configurations and 53,838 transitions**, including:

- Uncaptured edits.
- Cancellation and identical-value writes.
- Prefix confirmation and suffix rollback.
- Empty values.
- Aggregated diffs.
- Forward and inverse replay on another overlay.

This validates the key-level rules within that model. It is not validation of a
complete backend or tree-lifecycle implementation.

Implementation regressions must cover both Fjall and Sled, including:

- Full cleanup after cancellation-only and mixed diffs.
- Preservation of later writes and removals during prefix confirmation.
- Reverting a suffix after an earlier prefix has already been confirmed.
- Branch replacement and replay on another compatible overlay.
- Repeated read-only diff capture and aggregate application.
- Inverse and double-inverse behavior.
- Tree creation, dropping, restoration, and same-block edits followed by a drop.
- Checkpoint consistency and backend failure handling.

## Recommendation

Implement **counted reversible deltas**, explicit **confirm-versus-revert
semantics**, and separate **reversible tree-lifecycle state**.

This supplies the information missing from the current flattened state while
preserving portable diffs and avoiding full-sequence rebuilding during cleanup
or rollback.