That's very cool! I didn't know there were algorithms that could do that, I assumed mark and sweep was the only viable option. Do you know how it works?
It seems like a very interesting project and I'll keep it on my radar. However, the documentation leaves me with the impression, that it is not quite ready yet for usage beyond experimentation.
Rccan detect and deallocate cycles of
Rcs through the use of
Adopt. Cycle detection is a zero-cost abstraction.
I doubt, that zero-cost abstraction is the correct term here. If a manually written doubly-linked list is really not better than using
Rc, then it needs to be backed up with a proof, e.g. comparing the resulting assembly and checking for equality. For a scoped GC, it might be the best possible implementation, but that is trivially true without a competing alternative implementation. Calling it a low-cost abstraction seems more fitting and honest.
CactusRef depends on several unstable Rust features and can only be built on a nightly toolchain. CactusRef reimplements several compiler internals from alloc, which means it is only safe to build CactusRef with the same nightly compiler as the one pinned in its
While requiring nightly by itself isn't necessarily that bad, pinning the project to a single nightly version is very restrictive. I hope this restriction can be lifted in the near future, moving to a range of working nightly versions.
CactusRefrelies on proper use of
Adopt::unadoptto maintain bookkeeping about the object graph for breaking cycles. These functions are unsafe because improperly managing the bookkeeping can cause the
Rcdrop implementation to deallocate cycles while they are still externally reachable. Failure to uphold
Adopt’s safety invariants will result in undefined behavior and held
Rcs that point to members of the now deallocated cycle may dangle.
unsafe is unfortunate. The immediate question popping up in my mind is, why does it require
unsafe (could this be changed in the future, either through an optional API with additional runtime checks or a macro enforcing and emitting correct usage of unsafe?) and what kind of
unsafe does it protect me from writing myself (if the user has to take of every safety invariant, its usage seems unattractive to me)?
Hi @Phlopsi thanks for the feedback.
I've made some changes to the documentation and README to clarify CactusRef's experimental status and cleaned up the copy around "zero-cost abstractions". A better way to say what I meant is that cycle detection is opt-in; in the absence of adoptions, there is no runtime cost.
I've published a new version that has these documentation changes: https://crates.io/crates/cactusref/0.1.1.
box_free from alloc. It may be the case that CactusRef works on newer nightlies, but until the pinned compiler version is updated, I haven't verified that this function is implemented the same way.
The unsafe here is similar in shape to
NonZeroUsize::new_unchecked. CactusRef relies on and exploits the ownership annotations implied by calls to
unadopt. Failure to use these APIs correctly will result in unsoundness, just like
Some(NonZeroUsize::new_unchecked(0)) will. The type of
unsafe the adoption API encapsulates for you is a 400+ line
Adopt::adopt has two safety invariants which I don't think are particularly onerous: Adopt in cactusref - Rust
Thanks again for your feedback and I'm glad you find CactusRef interesting.
You're guaranteed to be able to free a
Box<T> produced pointer using
std::alloc::dealloc, and to allocate a pointer later used as a
std::alloc::alloc, so long as the pointer is de/alloc'd with the correct layout for
Ooo! Thanks for letting me know this. I've merged a PR that re-implements the deallocation using
alloc::alloc::dealloc and unpinned the nightly toolchain. CI will now run with the latest nightly.
I've put together a WIP PR that experiments with a safe adoption API: [WIP] Experiment with a safe adoption API by lopopolo · Pull Request #47 · artichoke/cactusref · GitHub