# Comparison: lock_tree
[`lock_tree`](https://crates.io/crates/lock_tree) (originally from Google's [Fuchsia](https://fuchsia.dev/) project, maintained by Nicholas Bishop, BSD license) is the library that introduced the `LockAfter<A>` trait pattern for compile-time lock ordering in Rust. Surelock's level system descends directly from this insight. This is an elegant design that demonstrated how the Rust type system could encode lock hierarchies statically.
## What lock_tree Does
`lock_tree` prevents deadlocks by encoding a directed acyclic graph (DAG) of lock _categories_ as trait impls. Each lock category is a type (`struct ConfigLock;`). The `LockAfter<A>` trait declares that a lock at level `Self` may be acquired after a lock at level `A`. A `Locked<State, Level>` witness tracks the current position in the DAG. Each `lock_and` call consumes the witness and returns a new one at the next level.
The key insight: the Rust trait system can enforce a static partial order on lock acquisition. If the ordering isn't declared, the code doesn't compile.
## What surelock Borrows
| lock_tree concept | surelock equivalent | Notes |
|--------------------------|--------------------------------|---------------------------------------------------------------------------|
| `LockAfter<A>` trait | `LockAfter<Before>` trait | Same concept, same name |
| `Locked<State, Level>` | `MutexKey<'scope, Lvl>` | Witness consumed and re-emitted (surelock separates key from data access) |
| `lock_and` method | `key.lock()` / `key.lock_with()` | Consumes key, returns new key at next level |
| `impl_lock_after!` macro | Macro-generated impls | Transitive `LockAfter` impls for `Level<N>` |
| Named lock categories | `type Config = Level<0>` | Type aliases for semantic meaning |
## Key Differences
### Dynamic lock sets
`lock_tree` operates on individual, named lock instances. Sibling locks (both children of the same parent in the DAG, e.g., `C` and `D` both after `B`) have _no_ ordering relationship -- neither `C: LockAfter<D>` nor `D: LockAfter<C>`. The `Locked` witness requires `LockBefore<M>` for every acquisition, and with no path between siblings, neither direction compiles. This prevents deadlocks between siblings, but it also means you _cannot hold both simultaneously_ -- if you need both `C` and `D`, you must either declare an explicit ordering between them or restructure to avoid holding both.
surelock's `LockSet` solves this by acquiring multiple locks atomically at the same level, sorted by `LockId`. Siblings (multiple children of the same parent in a `new_higher` chain) share a level and go in a `LockSet`. You _can_ hold both simultaneously, and the sorted acquisition order prevents deadlocks.
### Lock identity
`lock_tree` does not assign unique identifiers to locks. Ordering is determined entirely by the type-level DAG. Two `Mutex<AccountLock>` instances are interchangeable in the ordering -- `lock_tree` has no mechanism to distinguish them.
surelock assigns a unique `LockId` to each mutex. This enables `LockSet`'s sorted acquisition: within a level, locks are ordered by ID, not by type.
### Per-instance vs per-category ordering
`lock_tree`'s ordering is per-_category_: all locks at level `AccountLock` are equivalent. You declare "config locks come before account locks" and this applies to every config lock and every account lock uniformly.
surelock supports both per-category (via `Level<N>` type aliases) and per-_instance_ ordering (via `Mutex::new_higher`). A lock's level is determined at creation time, not at type-definition time.
### Scope uniqueness enforcement
`lock_tree` does not enforce that only one witness exists per thread. `Locked::new(&state)` is infallible and can be called any number of times. Two independent witnesses on the same thread can lock in contradictory orders, defeating the ordering guarantee. The crate relies on programmer discipline to create one witness per call chain.
surelock enforces scope uniqueness on `std` via `thread_local!` (`KeyHandle::try_claim()` returns `None` if a handle already exists). On all targets, `KeyHandle::scope(&mut self)` provides static nesting prevention via the borrow checker.
### DAG vs total order
`lock_tree` supports full DAGs: category A can have multiple successors (A → B, A → C) where B and C are independent. Independent siblings _cannot_ be acquired after each other -- the `Locked` witness enforces this at compile time. This is safe (no deadlock risk between siblings) but restrictive (you cannot hold both B and C simultaneously unless you declare an explicit ordering between them).
surelock uses a total order: `Level<0>` < `Level<1>` < `Level<2>` < ... . There are no independent branches. Siblings share a level and go in a `LockSet` for atomic acquisition. This means you _can_ hold multiple same-level locks simultaneously -- something `lock_tree` cannot express for unordered siblings.
> [!NOTE]
> `lock_tree`'s DAG approach and surelock's total-order approach handle siblings differently but are both deadlock-free. `lock_tree` prevents deadlocks between siblings by making them mutually exclusive (compile error if you try to hold both). surelock prevents deadlocks between siblings by forcing atomic acquisition in a consistent order (`LockSet` sorted by `LockId`). The trade-off: `lock_tree` is safer by default (you can't accidentally hold both), surelock is more flexible (you _can_ hold both when you need to).
### Level declaration
`lock_tree` requires a macro (`impl_lock_after!`) and manually-defined category structs for each level. surelock uses `Level<const N: usize>` -- a const-generic type with macro-generated impls for 16 levels (feature-gated 32 or 64). Users create semantic aliases: `type Config = Level<0>`. No proc macro is needed.
### Backend flexibility
`lock_tree` is not generic over the lock backend. It provides its own `Mutex` and `MutexGuard` types.
surelock's `Mutex<T, Lvl, R>` is generic over any `RawMutex` implementation. The default is `StdMutex` (wrapping `std::sync::Mutex`); `parking_lot`, `spin`, and custom backends are supported via the `lock-api` feature.
## Summary
| Property | lock_tree | surelock |
|-----------------------|------------------------|-----------------------------------------|
| Ordering model | DAG (partial order) | Total order (`Level<N>`) |
| Same-level multi-lock | Not supported | `LockSet` (sorted by `LockId`) |
| Lock identity | None (type-level only) | `LockId` (monotonic `u64`) |
| Per-instance ordering | No (per-category only) | Yes (`Mutex::new_higher`) |
| Scope uniqueness | Not enforced | `thread_local!` on `std`, `&mut` on all |
| Level declaration | Macro + manual structs | `Level<N>` + type aliases |
| Backend flexibility | Fixed | Generic over `RawMutex` |
| `no_std` | Yes | Yes |
| License | BSD (Fuchsia) | MIT OR Apache-2.0 |
`lock_tree` remains the right choice for programs that benefit from DAG ordering (independent subsystems that are never held simultaneously) and don't need same-level multi-lock. Its minimal design and zero-dependency approach make it an excellent tool for its intended use case. surelock extends the `LockAfter` concept with dynamic multi-lock, per-instance ordering, scope uniqueness, and backend flexibility.