CONTRIBUTING.md

Contributing to rust-cc

Feel free to open issues or pull requests. Feature requests can be done opening an issue, the enhancement tag will be applied by maintainers.

For pull requests, use rustftm to format your files and make sure to allow edits by maintainers.
Also, remember to open the pull requests toward the dev branch. The main branch is only for releases!

The collection algorithm

The core idea behind the algorithm is the same as the one presented by Lins in "Cyclic Reference Counting With Lazy Mark-Scan" and by Bacon and Rajan in "Concurrent Cycle Collection in Reference Counted Systems".
However, the implementation differs in order to make the collector faster and more resilient to panics and failures.

Important

rust-cc is not strictly an implementation of the algorithm shown in the linked papers and it's never been intended as such. Feel free to propose any kind of improvement!

The following is a summarized version of the collection algorithm:
When a Cc smart pointer is dropped, the reference count (RC) is decreased by 1. If it reaches 0, then the allocated object pointed by the Cc (called CcBox) is dropped, otherwise the Cc is put into the POSSIBLE_CYCLES list.
The POSSIBLE_CYCLES is an (intrusive) list which contains the possible roots of cyclic garbage.
Sometimes (see crate::trigger_collection), when creating a new Cc or when collect_cycles is called, the objects inside the POSSIBLE_CYCLES list are checked to see if they are part of a garbage cycle.

Therefore, they undergo two tracing phases:

• Trace Counting: during this phase, a breadth-first traversal of the heap is performed starting from the elements inside POSSIBLE_CYCLES to count the number of pointers to each CcBox that is reachable from the list's Ccs.
  The tracing_counter "field" (see the counter_marker module for more info) is used to keep track of this number.
  About tracing_counter

  In the papers, Lins, Bacon and Rajan decrement the RC itself instead of using another counter. However, if during tracing there was a panic, it would be hard for `rust-cc` to restore the RC correctly. This is the reason for the choice of having another counter. The invariant regarding this second counter is that it must always be between 0 and RC (inclusively).

• Trace Roots: now, every CcBox which has the RC strictly greater than tracing_counter can be considered a root, since it must exist a Cc pointer which points at it that hasn't been traced in the previous phase. Thus, a trace is started from these roots, and all objects not reached during this trace are finalized/deallocated (this is actually more complex due to possible object resurrections, see the comments in lib.rs).
  Note that this second phase is correct only if the graph formed by the pointers is not changed between the two phases. Thus, this is a key requirement of the Trace trait and one of the reasons it is marked unsafe.

Using lists and queues

When debug assertions are enabled, the add method may panic before actually updating the list to contain the added object. Similarly, the remove method may panic after having removed the object from the list.

Thus, marking should be done only:

• after the call to the add method
• before the call to the remove method.

Writing tests

Every unit test (which makes use of a part of the collector) should start with a call to tests::reset_state() to make sure errors in other tests don't impact the current one.

Writing documentation

Docs are always built with every feature enabled. This makes it easier to write and maintain the documentation.

However, this also makes it more difficult to write examples, as those must pass CI even when a features they require is disabled. As such, examples are marked as ignored if a feature they need is missing:

#![cfg_attr(
    feature = "derive",
    doc = r"```rust"
)]
#![cfg_attr(
    not(feature = "derive"),
    doc = r"```rust,ignore"
)]
#![doc = r"# use rust_cc::*;
# use rust_cc_derive::*;

// Example code

```"]