rec_cell 0.1.0

Zero-cost borrow-checking of aliased references supporting cyclic construction.

Overview

Some collections, such as linked lists or trees, are most easily implemented with aliasing pointers. GhostCell is a proven alternative to runtime borrow checking, and the branding idea has been (re)implemented in several crates.

This crate provides RecCell and RecToken, corresponding to GhostCell and GhostToken, then extends the API by introducing cyclic construction:

impl<'t, T> RecCell<'t, T>> {
    pub fn new_cyclic<'a R>(
        uninit: &'a mut MaybeUninit<T>,
        token: RecToken<'t>,
        scope: impl FnOnce(&'a Self) -> (R, T),
    ) -> (R, RecToken<'t>);
}

This gives you a reference to the not-yet-constructed cell to construct your potentially cyclic cell. In exchange, it takes away the token entirely such that it is impossible to access the uninitialized cell within the scope. There are some subtleties to this; see the docs for more details.

Safety

There is yet to be a formal proof of the correctness of this mechanism. All tests currently pass Miri.

Some parts are bot-drafted and might be of dubious quality. I might eventually rewrite those parts by hand.

Acknowledgements

This is heavily based on and inspired by the ghost-cell crate and similar implementations.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.