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].

# 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:

# 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:

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.