rec_cell 0.1.0

Zero-cost borrow-checking of aliased references with cyclic construction
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

[![Crates.io Version](https://img.shields.io/crates/v/rec_cell)](https://crates.io/crates/rec_cell)
[![docs.rs](https://img.shields.io/docsrs/rec_cell)](https://docs.rs/rec_cell)
[![CI Status](https://github.com/ivan-shrimp/rec-cell/actions/workflows/ci.yml/badge.svg)](https://github.com/ivan-shrimp/rec-cell/actions)

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`](https://plv.mpi-sws.org/rustbelt/ghostcell/) is a proven
alternative to runtime borrow checking, and the branding idea has been
(re)implemented [in](https://github.com/matthieu-m/ghost-cell)
[several](https://github.com/uazu/qcell)
[crates](https://github.com/p-avital/token-cell-rs).

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

```rust
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](https://docs.rs/rec_cell) 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.

| Part              | Status                                 |
| ----------------- | -------------------------------------- |
| Library code      | 100% human                             |
| Documentation     | 80% human: `SliceCursor{,Mut}` pending |
| Tests not in docs | 0% human                               |

## Acknowledgements

This is heavily based on and inspired by the
[ghost-cell](https://github.com/matthieu-m/ghost-cell) crate and similar
implementations.

## License

Licensed under either of

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

at your option.