# `gc_api`
A trait based `Rust` API for a generic garbage collector. This project currently exists to formulate what such
an API might look like while supporting a wide range of garbage collector types/implementations.

**This crate is still underdevelopment. Any feedback or pull requests would be appreciated.**

## The Safety Issue
How can some pointer `Gc<T>` to an element within the heap be used safely? The problem has two parts:
- Ensure `Gc<T>` either does not outlive or is not used beyond heap lifetime
- ABA problem (How can we know the object we want has not been garbage collected, and we are now pointing to a
  different object at the same location)
    - We must either defer reclamation of an object until no references to it remain or have a means of differentiating
      objects when the contents of the heap changes. Deferring reclamation is not really an option since it would
      require keeping track of how many are taken remain and that would prevent pointer from implementing `Copy`.
    
### Defragmentation
To make defragmentation possible, an indirect pointer is required. Objects hold pointers into an unmoving reference
table with pointers to active objects. Upon defragmentation the reference table is updated to reflect the new locations
of objects. The only alternatives are to either find and update all referencing pointers or use an indexing system which
dynamically resolves the object's location upon access.

### ABA
To solve the ABA problem, we only have a limited number of options at our disposal. Deferred reclamation is not possible
since we have no way to determine if deferral is necessary while keeping the pointer `Copy`. The only option left to us
is to provide some way of distinguishing objects. This leaves us with the option to use tagged states. Practically
speaking, tags would likely take the form of a generation counter. Both the pointers and objects would need to store
this tag. However, placement of the tag can be tricky since depending on the allocation method, pointers to reclaimed
objects may be aligned to the start of whatever now uses that part of the heap. If we want to use direct object pointers
we need a way to determine the offset of the tag. This means we would need to use multiple fixed-object-size heaps so
the tag is always a fixed offset from an object pointer no matter the gc state. The other approach is to use indirect
pointers instead. The reference table could be expanded to hold object tags with data pointers. This does not limit how
data is placed into the heap or increase the size of heap objects.