lock-db 1.0.0

# lock-db v0.4.0 — Deadlock Detection & Feature Freeze

**The last feature.** v0.4.0 adds wait-for deadlock detection — a wait-for graph
with cycle detection and victim selection, and a deadlock-aware acquisition path
on the lock manager — and with it the 1.0 feature set is complete. The public
API is frozen as of this release; everything from here to 1.0 is hardening and
soak testing.

## What is lock-db?

The lock manager for a transactional database: the component that lets many
transactions touch shared data at once without corrupting it. It hands out locks
on resources in compatible modes across multiple granularities, locks key ranges
to stop phantoms, and — as of this release — detects when transactions have
deadlocked and names one to abort. It assigns no identities and persists nothing;
it is the in-memory lock table a transaction layer drives.

## What's new in 0.4.0

### `WaitForGraph` — wait-for graph, cycle detection, victim selection

When a transaction cannot get a lock because another holds it, the first *waits
for* the second. Those edges form a wait-for graph; a cycle in it is a deadlock.
`WaitForGraph` holds the edges and finds cycles with an iterative depth-first
search (no recursion, so a long wait chain cannot overflow the stack), and
`pick_victim` chooses which member of a cycle to abort:

```rust
use lock_db::{TxnId, VictimPolicy, WaitForGraph};

let mut g = WaitForGraph::new();
g.add_wait(TxnId::new(1), TxnId::new(2));
g.add_wait(TxnId::new(2), TxnId::new(3));
g.add_wait(TxnId::new(3), TxnId::new(1)); // closes the loop

let cycle = g.detect_cycle().expect("a deadlock");
assert_eq!(cycle.len(), 3);
assert_eq!(WaitForGraph::pick_victim(&cycle, VictimPolicy::Youngest), Some(TxnId::new(3)));
```

The graph is pure data — no locks, no threads — which keeps the detection logic
small enough to test exhaustively. It is public for direct use, and a property
test cross-checks `detect_cycle` against Kahn's topological sort over thousands
of random graphs: it reports a cycle if and only if one exists, and the cycle it
returns is always a real one.

### `LockManager::request` — deadlock-aware acquisition

`try_acquire` never blocks and never tracks anything, so it cannot tell a
transient conflict from a deadlock. `request` is the deadlock-aware path. On
conflict it records the wait and reports one of three outcomes:

```rust
use lock_db::prelude::*;

let lm = LockManager::new();
let (a, b) = (ResourceId::new(1), ResourceId::new(2));
let (t1, t2) = (TxnId::new(1), TxnId::new(2));

lm.request(t1, a, LockMode::Exclusive); // Granted
lm.request(t2, b, LockMode::Exclusive); // Granted
lm.request(t1, b, LockMode::Exclusive); // Waiting (T1 waits for T2)

// T2 waiting for A closes the cycle.
match lm.request(t2, a, LockMode::Exclusive) {
    Acquisition::Deadlock(d) => {
        assert_eq!(d.victim, t2);  // youngest in the cycle
        lm.release_all(d.victim);  // abort to break the deadlock
    }
    other => panic!("expected a deadlock, got {other:?}"),
}
```

lock-db does not park threads: the transaction layer owns suspension and retry.
`request` returns `Granted`, `Waiting` (suspend and retry later), or `Deadlock`
(abort the named victim). Detection is **exact** — the graph is rebuilt from the
current lock table on every check, so a wait left over from a since-released lock
contributes no edge, and a transaction is never reported as deadlocked unless it
genuinely is. This is the invariant the directives call out ("never falsely abort
a non-deadlocked transaction"), and it is what the `no_false_deadlock_after_release`
test pins down.

`find_deadlock` is the periodic-detection counterpart for a background detector
that scans the whole wait set on an interval; `cancel_wait` drops a wait when a
transaction gives up without acquiring.

### Lock ordering, verified by loom

`request` takes a single global wait-registry mutex as the outer lock, then a
shard mutex; nothing ever takes them in the other order, and `release_all` clears
its wait in a separate critical section that never nests with a shard lock. A new
`loom` model check runs the classic two-transaction deadlock under every
interleaving and asserts no cycle ever survives detection — which also means loom
would flag a lock-ordering deadlock inside the manager itself if one existed. It
does not.

## Breaking changes

`request` and the deadlock types are additive. The only behavioural change is
that `release_all` now also clears a transaction's pending wait, which is
strictly correct for the new feature and invisible to code that does not use
`request`. No existing method signatures changed.

This is the **feature-freeze** release: the public API is stable from here to
1.0.

## Verification

Run on Windows x86_64 (Rust stable 1.95) and Linux via WSL2 Ubuntu (Rust stable
1.95); MSRV verified on Rust 1.85. All commands below pass on both platforms:

```bash
cargo fmt --all -- --check
cargo clippy --all-targets -- -D warnings
cargo clippy --all-targets --all-features -- -D warnings
cargo clippy --no-default-features --all-targets -- -D warnings
cargo test
cargo test --all-features
cargo build --examples
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
cargo deny check
cargo audit

# concurrency model checks (slow; not part of the default run)
RUSTFLAGS="--cfg loom" cargo test --test loom --release
```

Test counts at this tag:

- Default features: 90 unit + 38 doctests.
- `--all-features`: 90 unit + 38 doctests + 4 property tests.
- `--no-default-features`: 26 unit tests (the `no_std` core).
- Loom: 4 model checks.

Indicative single-threaded numbers on the development workstation: an uncontended
point acquire+release around 110 ns through the sharded `try_acquire`, and around
117 ns through the deadlock-aware `request` (the cost of the global wait lock on
the granted path), flat as the wait set grows.

## What's next

- **v0.5.0 — adversarial contention and deadlock-storm tests, then the formal
  API freeze**, with `cargo audit` and `cargo deny` clean.
- **0.6.0 → 1.0.0** — alpha / beta / rc / stable: integrate against real
  consumers, capture final benchmarks, and publish.

## Installation

```toml
[dependencies]
lock-db = "0.4"

# with serde derives on the public types
lock-db = { version = "0.4", features = ["serde"] }
```

MSRV: Rust 1.85 (2024 edition).

## Documentation

- [README](https://github.com/jamesgober/lock-db/blob/main/README.md)
- [API Reference](https://github.com/jamesgober/lock-db/blob/main/docs/API.md)
- [CHANGELOG](https://github.com/jamesgober/lock-db/blob/main/CHANGELOG.md)

---

**Full diff:** [`v0.3.0...v0.4.0`](https://github.com/jamesgober/lock-db/compare/v0.3.0...v0.4.0).
**Changelog:** [`CHANGELOG.md`](https://github.com/jamesgober/lock-db/blob/main/CHANGELOG.md#040---2026-06-05).