cycle_ptr 0.1.0

//! Smart pointers that allow for cycles in their data.
//!
//! This library:
//! - has both local-thread and multi-thread implementations
//! - permits control over how and when GC runs
//! - follows RAII by ensuring `drop` gets run
//!
//! # Example
//!
//! ```
//! use cycle_ptr::prelude::*;
//! use cycle_ptr::{GcMemberPtr, Metadata, GcPtr};
//! use std::cell::RefCell;
//!
//! struct Child {
//!     parent: RefCell<Option<GcMemberPtr<Parent>>>,
//!     metadata: Metadata,
//! }
//!
//! struct Parent {
//!     child: RefCell<Option<GcMemberPtr<Child>>>,
//!     metadata: Metadata,
//! }
//!
//! impl Parent {
//!     fn assign_child(&self, child: GcPtr<Child>) {
//!         self.child
//!             .borrow_mut()
//!             .insert(self.metadata.new_pointer(child));
//!     }
//! }
//!
//! let parent = GcPtr::new(|metadata| Parent {
//!     child: RefCell::new(None),
//!     metadata,
//! });
//! let child = GcPtr::new(|metadata| Child {
//!     parent: RefCell::new(Some(metadata.new_pointer(parent.clone()))),
//!     metadata,
//! });
//! parent.assign_child(child.clone());
//! ```
//!
//! # When To Use
//!
//! If you have a cyclic reference like this in your code:
//! ```
//! # use std::rc::Rc;
//! # use std::cell::RefCell;
//! #[derive(Default)]
//! struct S {
//!   p: RefCell<Option<Rc<S>>>,
//! }
//!
//! let a_ptr = Rc::new(S::default());
//! let b_ptr = Rc::new(S::default());
//!
//! // Create a circular reference.
//! *a_ptr.p.borrow_mut() = Some(b_ptr.clone());
//! *b_ptr.p.borrow_mut() = Some(a_ptr.clone());
//!
//! // And now introduce a memory leak.
//! drop(a_ptr);
//! drop(b_ptr);
//! ```
//! The code will cause a memory leak, because the two pointers keep references to eachother live.
//!
//! In that case, this library may help you:
//! ```
//! use cycle_ptr::prelude::*;
//! use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! use std::cell::RefCell;
//!
//! struct S {
//!   gc_metadata: Metadata,
//!   p: RefCell<Option<GcMemberPtr<S>>>,
//! }
//!
//! let a_ptr = GcPtr::new(|gc_metadata| S {
//!   gc_metadata,
//!   p: None.into(),
//! });
//! let b_ptr = GcPtr::new(|gc_metadata| S {
//!   gc_metadata,
//!   p: None.into(),
//! });
//!
//! // Create a circular reference.
//! *a_ptr.p.borrow_mut() = Some(a_ptr.gc_metadata.new_pointer(b_ptr.clone()));
//! *b_ptr.p.borrow_mut() = Some(a_ptr.gc_metadata.new_pointer(a_ptr.clone()));
//!
//! // And now there's no memory leak!
//! drop(a_ptr);
//! drop(b_ptr);
//! ```
//!
//! ## Pointers and cycles
//!
//! The pointers keep track of a directed acyclic graph (DAG) of pointers,
//! and uses a mark-sweep algorithm on this DAG.
//! - [GcPtr] and [GcMtPtr][crate::sync::GcMtPtr] are pointers that are always considered reachable.
//!   You should use those inside functions, as global variables,
//!   and on any objects which don't participate in cycles.
//! - [GcMemberPtr] and [GcMtMemberPtr][crate::sync::GcMtMemberPtr] are pointers that connect objects in the DAG.
//!   They should be placed on any objects that may participate in cycles.
//!
//! ## Examples of Correct and Incorrect Usage
//!
//! Consider:
//! ```
//! use cycle_ptr::prelude::*;
//! use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! use std::cell::RefCell;
//! use std::rc::Rc;
//!
//! struct S {
//!   gc_metadata: Metadata,
//!   mp: RefCell<Option<GcMemberPtr<S>>>,
//! }
//! ```
//!
//! ------------------------------------------------------------------------
//! Then,
//! ```
//! # use cycle_ptr::prelude::*;
//! # use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! # use std::cell::RefCell;
//! #
//! # struct S {
//! #   gc_metadata: Metadata,
//! #   mp: RefCell<Option<GcMemberPtr<S>>>,
//! # }
//! #
//! let ptr = GcPtr::new(|gc_metadata| S {
//!   gc_metadata,
//!   mp: RefCell::new(None),
//! });
//! ```
//! is *correct*: `S` has a [member pointer][GcMemberPtr] (`mp`), thus is part of the DAG, and is kept live by a [pointer][GcPtr].
//!
//! ------------------------------------------------------------------------
//! ```no_run
//! # use cycle_ptr::prelude::*;
//! # use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! # use std::cell::RefCell;
//! # use std::rc::Rc;
//! #
//! # struct S {
//! #   gc_metadata: Metadata,
//! #   mp: RefCell<Option<GcMemberPtr<S>>>,
//! # }
//! #
//! # fn unrelated_metadata() -> Metadata {
//! #   unimplemented!()
//! # }
//! #
//! let ptr = Rc::new(S {
//!   gc_metadata: unrelated_metadata(),
//!   mp: RefCell::new(None),
//! });
//! ```
//! is *bad*: `S` has a [member pointer][GcMemberPtr] (`mp`), thus is part of the DAG, but is not kept live by a [pointer][GcPtr].
//!
//! ------------------------------------------------------------------------
//! ```
//! # use cycle_ptr::prelude::*;
//! # use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! # use std::cell::RefCell;
//! # use std::rc::Rc;
//! #
//! # struct S {
//! #   gc_metadata: Metadata,
//! #   mp: RefCell<Option<GcMemberPtr<S>>>,
//! # }
//! #
//! struct T {
//!   mp: Rc<S>,
//! }
//!
//! let extra_s = GcPtr::new(|gc_metadata| S {
//!   gc_metadata,
//!   mp: RefCell::new(None),
//! });
//! let ptr = GcPtr::new(|gc_metadata| {
//!   let extra_s = gc_metadata.new_pointer(extra_s);
//!   T {
//!     mp: Rc::new(S {
//!       gc_metadata,
//!       mp: RefCell::new(Some(extra_s)),
//!     }),
//!   }
//! });
//! ```
//! is *correct*, as long as `S` and `T` remain connected like this.
//!
//! But if you try to disconnect them
//! ```
//! # use cycle_ptr::prelude::*;
//! # use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! # use std::cell::RefCell;
//! # use std::rc::Rc;
//! #
//! # struct S {
//! #   gc_metadata: Metadata,
//! #   mp: RefCell<Option<GcMemberPtr<S>>>,
//! # }
//! #
//! # struct T {
//! #   mp: Rc<S>,
//! # }
//! #
//! # let ptr = GcPtr::new(|gc_metadata| {
//! #   T {
//! #     mp: Rc::new(S {
//! #       gc_metadata,
//! #       mp: RefCell::new(None),
//! #     }),
//! #   }
//! # });
//! #
//! let rc_ptr: Rc<S> = ptr.mp.clone();
//! ```
//! usage is no longer valid (because `S::mp` may now outlive `T`).
//!
//! And trying to dereference it will result in a panic:
//! ```should_panic
//! # use cycle_ptr::prelude::*;
//! # use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! # use std::cell::RefCell;
//! # use std::rc::Rc;
//! #
//! # struct S {
//! #   gc_metadata: Metadata,
//! #   mp: RefCell<Option<GcMemberPtr<S>>>,
//! # }
//! #
//! # struct T {
//! #   mp: Rc<S>,
//! # }
//! #
//! # let ptr = GcPtr::new(|gc_metadata| {
//! #   T {
//! #     mp: Rc::new(S {
//! #       gc_metadata,
//! #       mp: RefCell::new(None),
//! #     }),
//! #   }
//! # });
//! #
//! # let rc_ptr: Rc<S> = ptr.mp.clone();
//! #
//! # fn use_s(_: &S) {}
//! #
//! drop(ptr); // `S` is no longer valid.
//!
//! let mp_refcell = rc_ptr.mp.borrow();
//! let mp_to_s: &GcMemberPtr<S> = mp_refcell.as_ref().unwrap();
//! use_s(&*mp_to_s);
//! ```
//! Dereferencing the member pointer `rc_ptr.mp` gets checked against the liveness of the owner (`ptr`).
//! But because it was dropped, and garbage collected, `mp` is no longer valid, and thus dereference is not permitted.
//!
//! ------------------------------------------------------------------------
//! ```
//! # use cycle_ptr::prelude::*;
//! # use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! # use std::cell::RefCell;
//! # use std::rc::Rc;
//! #
//! # struct S {
//! #   gc_metadata: Metadata,
//! #   mp: RefCell<Option<GcMemberPtr<S>>>,
//! # }
//! #
//! fn make_s_gcptr() -> GcPtr<S> {
//!   GcPtr::new(|gc_metadata| S {
//!     gc_metadata,
//!     mp: None.into(),
//!   })
//! }
//!
//! struct X {
//!   s_ptr: GcPtr<S>,
//! }
//!
//! let x = Rc::new(X {
//!   s_ptr: make_s_gcptr(),
//! });
//! ```
//! is *correct*, because `X` is not part of the DAG.
//!
//! But
//! ```
//! # use cycle_ptr::prelude::*;
//! # use cycle_ptr::{GcPtr, GcMemberPtr, Metadata};
//! # use std::cell::RefCell;
//! # use std::rc::Rc;
//! #
//! # struct S {
//! #   gc_metadata: Metadata,
//! #   mp: RefCell<Option<GcMemberPtr<S>>>,
//! # }
//! #
//! # fn make_s_gcptr() -> GcPtr<S> {
//! #   GcPtr::new(|gc_metadata| S {
//! #     gc_metadata,
//! #     mp: None.into(),
//! #   })
//! # }
//! #
//! # struct X {
//! #   s_ptr: GcPtr<S>,
//! # }
//! #
//! let x = GcPtr::new(|gc_metadata| X {
//!   s_ptr: make_s_gcptr(),
//! });
//! ```
//! is *bad*, because `X` is now being part of the DAG (a [GcPtr] points at it).
//! But the member-variable `s_ptr` can't be tracked, it should have been a `GcMemberPtr` instead.
//!
//! # Helping the Library be Fast
//!
//! The library maintains an invariant, that for any circular reference,
//! the objects in that circular reference all share the same generation.
//! In addition, objects in different generations,
//! must always use an origin that's on an older generation than the destination.
//!
//! This means a lot of work on the constructor of [GcMemberPtr].
//! Whenever a link gets established that would violate these invariants,
//! the code will fold the two generations together into a single generation.
//! This is a potentially expensive operation, but there's ways to avoid it.
//!
//! ## Circular References
//!
//! If you know a group of objects will all point back at eachother, then creating them in the same generation
//! will avoid the folding together of two generations.
//! This is done using a [GenerationRef]:
//! ```
//! use cycle_ptr::prelude::*;
//! use cycle_ptr::{GcMemberPtr, GenerationRef, Metadata};
//! use std::cell::RefCell;
//!
//! struct X {
//!     y: GcMemberPtr<Y>,
//! }
//!
//! struct Y {
//!     gc_metadata: Metadata,
//!     x: RefCell<Option<GcMemberPtr<X>>>,
//! }
//!
//! let generation = GenerationRef::default(); // create a new generation
//!
//! let y_ptr = generation.make(|gc_metadata| Y {
//!     gc_metadata,
//!     x: None.into(),
//! });
//! let x_ptr = generation.make(|gc_metadata| X {
//!     y: gc_metadata.new_pointer(y_ptr.clone()),
//! });
//! *y_ptr.x.borrow_mut() = Some(y_ptr.gc_metadata.new_pointer(x_ptr.clone()));
//! ```
//!
//! Note that generations can get folded together, and this changes the generation that an object is part of.
//! The way to get the generation reliably, is to request it from the [Metadata] of the object.
//!
//! ## Freeing Many Pointers
//!
//! Whenever a pointer gets dropped, it may start a garbage collection.
//! The code tries to minimize them, but it cannot defer them.
//!
//! So when a large number of pointers gets dropped (or a single object that may contain many pointers)
//! this could cause many GCs.
//!
//! For example a `Vec<GcPtr<MyType>>` of len=1000, when dropped, would start a GC for each of the pointers,
//! one at a time. That would create 1000 GCs.
//!
//! But by wrapping the drop inside a [DeferGc::run], the GC gets deferred, and run at the end of the [drop].
//!
//! # Features
//!
//! By default thread-safe ([Send] and [Sync]) versions of pointers, and weak pointer, are disabled.
//! Please use features to enabled them.
//!
//! Enabling features comes with a performance drawback,
//! so it's best to only enable the feature you require.
//!
//! ## weak_pointer
//!
//! `cycle_ptr = { features = ["weak_pointer"] }`
//!
//! Enable weak pointers.
//!
//! ## multi_thread
//!
//! `cycle_ptr = { features = ["multi_thread"] }`
//!
//! Enable thread-safe pointers (located in the `cycle_ptr::sync` package).
//!
//! ## single_generation
//!
//! `cycle_ptr = { features = ["single_generation"] }`
//!
//! For per-thread pointers ([GcPtr] or [GcMemberPtr]), use a single generation,
//! instead of trying to maximize the number of generations.
//!
//! Normally, this library uses multiple generations, which speeds up garbage collection
//! (because each mark-sweep run only evaluates a small set of objects).
//! But the cost is paid in [GcMemberPtr] operations: an invariant is to be maintained,
//! which may increase the cost of creating these [GcMemberPtr].
//!
//! By enabling this feature, a single generation per thread is used,
//! thus eliminating the extra work done in member pointers.
//! But the cost is moved to the garbage collection cycle.
//!
//! If you enable this feature, it's recommended to submit garbage collection tasks to a job queue,
//! to move them out of the function path.
//!
//! Note: this feature flag only controls same-thread pointers.
//! Multi-thread pointers are controlled using the `single_generation_mt` feature.
//!
//! ## single_generation_mt
//!
//! `cycle_ptr = { features = ["multi_thread", "single_generation_mt"] }`
//!
//! Thread-safe pointers normally use multiple generations,
//! attempting to keep the garbage collection cycle as short as possible, and parallellizable.
//! (This is achieved by keeping the size of the generation small.)
//!
//! The cost for this is payed in the member pointers:
//! constructing those must maintain an invariant which takes time.
//!
//! Turning on this feature reduces the number of generations to one, thereby making the invariant trivial.
//! But the cost is paid for, by increasing garbage collection times.
//! It is therefore recommended to make garbage collection happen on a separate thread, if you enable this feature.
//!
//! Note: this feature flag only controls thread-safe pointers, which are only enabled when enabling the `multi_thread` feature.
//! If you don't enable the `multi_thread` feature, this feature won't do anything.
//!
//! ## linked_list_reachability_assert
//!
//! This feature enables `debug_assert!` for the linked-list, to confirm an element is actually present in the list.
//! It increases complexity (O(1) → O(n), and O(n) → O(n²)), so it'll make your code really slow.
//! If it trips the assertions, please let me know.
//!
//! # Bugs
//!
//! ## dyn Pointers
//!
//! `GcPtr<dyn Trait>` does not work properly, so a program like:
//! ```ignore
//! let p: GcPtr<String> = GcPtr::new(|_| "foo".to_owned());
//! let q: GcPtr<dyn Debug> = p;
//! ```
//! does not work.
//!
//! I think the language does something internally for [Rc][std::rc::Rc] and [Arc][std::sync::Arc] to make that work.
//! But replicating that does not bring me success.

#![cfg_attr(docsrs, feature(doc_cfg))]

mod errors;
mod generation;
#[cfg(not(all(
    feature = "single_generation",
    any(feature = "single_generation_mt", not(feature = "multi_thread"))
)))]
mod generation_id;
mod list;
mod object;
mod pointer;
pub mod prelude;
pub(crate) mod util;

pub use errors::Error;
pub use generation::defer_gc::DeferGc;
pub use generation::r#ref::GenerationRef;
pub use generation::stats::GcStats;
pub use generation::task::{GcTask, GcTaskCallback};
pub use object::metadata::Metadata;
#[cfg(feature = "weak_pointer")]
pub use pointer::Weak;
pub use pointer::{GcMemberPtr, GcPtr};

/// All the pointers used in multi-thread contexts are here.
#[cfg(feature = "multi_thread")]
pub mod sync {
    pub use super::generation::r#ref::sync::GenerationRef;
    pub use super::generation::sync_task::{GcTask, GcTaskCallback, GcThread};
    pub use super::object::metadata::sync::Metadata;
    #[cfg(feature = "weak_pointer")]
    pub use super::pointer::sync::Weak;
    pub use super::pointer::sync::{GcMtMemberPtr, GcMtPtr};
}