Lib.rs

Packaged for Guix (crates-io)

provides a datastructure implemented using std's Vec. all uses of unsafe are just delegating to the underlying unsafe Vec methods.

Fundamental

• Well maintained?
  • Maintained by the Tokio project
• Well documented?
• Sane dep tree?
  • Build dependency on autocfg and optional dependency on serde :)
• Good test coverage?
  • Good when including the unstable --doctests option
  • 90.7% line coverage with cargo +nightly llvm-cov --doctests
• Tests are passing?
• cargo audit is happy?

Nice to have

• cargo check is happy?
• rustfmt is happy?
• clippy is happy?
  • Happy on 1.66.1 at least
• No outdated deps?

Build scripts

• Build script(s) seem sane?
  • Only used to gate off cfgs for different rust versions

unsafe Review

• Directly uses unsafe?
• Passes miri if using unsafe?
  • unsafe methods are tested and this is enforced with CI

Only uses unsafe to expose three unsafe methods on Slab

Slab::get_unchecked() is just an analog to [T]::get_unchecked() and internally calls [T]::get_unchecked() on the underlying vector. The caller MUST call this method on an occupied entry within the bounds of the underlying vector. Calling it outside of bounds is undefined behavior while calling it on a Vacant entry will panic (hits unreachable!()) although this may be relaxed to unreachable_unchecked() in the future a la https://github.com/tokio-rs/slab/issues/40

Slab::get_unchecked_mut() is the same situation as Slab::get_unchecked(). Also an analog of the slice method and also the same UB and panic behavior

Slab::get2_unchecked_mut() provides a way to get a mutable reference to two elements in the Slab without bounds checking. This has the same invariants as the other two (UB if out of range and panics on Vacant entries) along with the additional invariant that the two elements have to be different to prevent multiple mutable references to the same element. The last invariant is enforced with a debug assert. Because there is no analog for slices this manually implements the addressing in a similar way to [T]::get_unchecked_mut() although it would be nice to have a debug assert that the indices are in range (the standard library uses assert_unsafe_precondition!() to do this on [T]::get_unchecked() and [T]::get_unchecked_mut() which gets picked up by cargo-careful)

General Review

lib.rs

Essentially a Vec where removed elements get replaced by a vacant entry marker instead of shifting down all later values to compact. All vacant entries store an index pointing to some other vacant entry with the last vacant entry pointing to the end of the Slab. The Slab itself then stores a next value pointing to the top of the stack so that it can keep track of where all vacant entries are to efficiently push on new values. These underlying entries are never publicly exposed to prevent users from mangling this stack

Overall everything looks good. The Slab seems to correctly maintain its invariants at all times and there is a nice sprinkling of asserts and debug asserts to handle sanity checking

serde.rs

Contains the optional serde::{Serialize, Deserialize} impls for Slab. It just (de)serializes as a map with the deserialization performing the same operations as the FromIterator implementation

No internal use of unsafe. Only an get_unchecked unsafe api without bounds that translates directly to Vec and does not exploit the possible unsafety in its implementation to the fullest extent (unreachable instead of unreachable_unchecked).