1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249
//! A simple garbage collector for use in Rust. //! //! The goal is to help you quickly build a VM in Rust. //! So this GC is designed for: //! //! * Safety //! //! * No dependency on linters or compiler plugins //! //! * An API that's consistent with a high-performance implementation //! (though right now cell-gc is not speedy) //! //! * Fun //! //! //! # Caveats //! //! **cell-gc is for use in VMs.** So the assumption is that the data the GC is //! managing is not really *your* data; it's your end user's data. If you don't //! want every field of every GC-managed object to be public and mutable, cell-gc //! is not the GC for your project! //! //! **The API is completely unstable.** I promise I will change it in ways //! that will break code; you'll just have to keep up until things stabilize. //! //! cell-gc is not designed to support multithread access to a single heap (like Java). //! Instead, you can create one heap per thread (like JavaScript). //! //! Currently it does not support lots of small heaps with random lifetimes (like Erlang), //! but I have some ideas on how to get there. //! [See issue #7.](https://github.com/jorendorff/rust-toy-gc/issues/7) //! //! //! # How to use it //! //! There are two parts to using `cell_gc`: GC types and GC heaps. //! //! ## Declaring GC types //! //! Declaring GC types is actually super easy. Just add `#[derive(IntoHeap)]` //! to any struct: //! //! ```rust //! extern crate cell_gc; //! #[macro_use] extern crate cell_gc_derive; //! //! /// A linked list of numbers that lives in the GC heap. //! /// The `#[derive(IntoHeap)]` here causes Rust to define an additional //! /// type, `IntListRef`. //! #[derive(IntoHeap)] //! struct IntList<'h> { //! head: i64, //! tail: Option<IntListRef<'h>> //! } //! # fn main(){} //! ``` //! //! `cell_gc` does several things: //! //! * Behind the scenes, it generates some code used for garbage collection, //! such as marking code. You never need to worry about that stuff. //! //! * It checks that `IntList`'s fields are all GC-safe. //! //! Not every type is safe to use as a field of a heap struct or enum. //! Here are the allowed field types: //! //! * primitive types, like `i32` //! * types declared with `#[derive(IntoHeap)]`, like `IntList<'h>` and `IntListRef<'h>` //! * `Box<T>` where `T` has `'static` lifetime //! * `Rc<T>` where `T` has `'static` lifetime //! * `Option<T>` where `T` is any of these types //! //! If you try to use anything else, you'll get bizarre error messages //! from `rustc`. //! //! * It declare a `Ref` type for you, in this case `IntListRef`. //! `cell_gc` names this type by gluing `Ref` to the end of the struct //! name. `IntListRef` is a smart pointer to a GC-managed `IntList`. You //! need this because `cell_gc` doesn't let you have normal Rust references //! to stuff in the GC heap. //! //! `IntListRef` values keep in-heap `IntList` values alive; once the last //! `IntListRef` pointing at an object is gone, it becomes available for //! garbage collection, and eventually it'll be recycled. //! //! `IntListRef` is like `std::rc::Rc`: it's `Clone` but not `Copy`, and //! calling `.clone()` copies the Ref, not the object it points to. //! //! `Ref` types have accessor methods for getting and setting each //! field of the struct. For example, `IntList` has methods `.head()`, `.tail()`, //! `.set_head(i64)`, and `.set_tail(Option<IntListRef>)`. //! //! You can also derive `IntoHeap` for an enum, but support is incomplete: no //! `Ref` type is generated for enums. Tuple structs are not supported. //! //! ## Understanding heaps //! //! This part isn't documented well yet. But here's an example, //! using the `IntList` from above: //! //! ```rust //! # #[macro_use] extern crate cell_gc; //! # #[macro_use] extern crate cell_gc_derive; //! # #[derive(IntoHeap)] //! # struct IntList<'h> { //! # head: i64, //! # tail: Option<IntListRef<'h>> //! # } //! use cell_gc::Heap; //! //! fn main() { //! // Create a heap (you'll only do this once in your whole program) //! let mut heap = Heap::new(); //! //! heap.enter(|hs| { //! // Allocate an object (returns an IntListRef) //! let obj1 = hs.alloc(IntList { head: 17, tail: None }); //! assert_eq!(obj1.head(), 17); //! assert_eq!(obj1.tail(), None); //! //! // Allocate another object //! let obj2 = hs.alloc(IntList { head: 33, tail: Some(obj1) }); //! assert_eq!(obj2.head(), 33); //! assert_eq!(obj2.tail().unwrap().head(), 17); //! }); //! } //! ``` //! //! Use `Heap::new()` in your `main()` function to create a heap. //! Use `heap.enter()` to gain access to the heap (opening a "heap session", `hs`). //! Use `hs.alloc(v)` to allocate values in the heap. //! //! # Vectors in the GC heap //! //! A very simple "object" type for a text adventure game: //! //! ```rust //! #[macro_use] extern crate cell_gc; //! #[macro_use] extern crate cell_gc_derive; //! //! use cell_gc::collections::VecRef; //! //! #[derive(IntoHeap)] //! struct Object<'h> { //! name: String, //! description: String, //! children: VecRef<'h, ObjectRef<'h>> //! } //! # fn main() {} //! ``` //! //! Note that `children` is a `VecRef<'h, ObjectRef<'h>>`; that is, it is //! a reference to a separately GC-allocated `Vec<ObjectRef<'h>>`, which is //! a vector of references to other objects. In other words, this is exactly //! what you would have in Java for a field declared like this: //! //! ```java //! public ArrayList<Object> children; //! ``` //! //! The API generated by this macro looks like this: //! //! ```rust //! # struct VecRef<'h, T: 'h>(&'h T); // hack to make this compile //! struct Object<'h> { //! name: String, //! description: String, //! children: VecRef<'h, ObjectRef<'h>> //! } //! //! struct ObjectRef<'h> { //! /* all fields private */ //! # target: &'h Object<'h> // hack to make this compile //! } //! //! impl<'h> ObjectRef<'h> { //! fn name(&self) -> String //! # { unimplemented!(); } //! fn set_name(&self, name: String) //! # { unimplemented!(); } //! fn description(&self) -> String //! # { unimplemented!(); } //! fn set_description(&self, description: String) //! # { unimplemented!(); } //! fn children(&self) -> VecRef<'h, ObjectRef<'h>> //! # { unimplemented!(); } //! fn set_children(&self, children: VecRef<'h, ObjectRef<'h>>) //! # { unimplemented!(); } //! } //! ``` //! //! (You might never actually use that `set_children()` method. //! Instead, you'll initialize the `children` field with a vector when you //! create the object, and then you'll most likely mutate that existing vector //! rather than ever creating a new one.) //! //! You can allocate `Object`s in the heap using `hs.alloc(Object { ... })`, //! and make one `Object` a child of another by using `obj1.children().push(obj2)`. //! //! # Safety //! //! As long as you don't type the keyword `unsafe` in your code, //! this GC is safe.<sup>[citation needed]</sup> //! //! Still, there's one weird rule to be aware of: //! **Don't implement `Drop` or `Clone` //! for any type declared using `derive(IntoHeap)`.** //! It's safe in the full Rust sense of that word //! (it won't cause crashes or undefined behavior, //! as long as your `.drop()` or `.clone()` method does nothing `unsafe`), //! but it won't do what you want. //! Your `.drop()` and `.clone()` methods simply will not be called when you expect; //! and they'll be called at other times that make no sense. //! //! So don't do that! //! The safe alternative is to put a `Box` or `Rc` around your value //! (the one that implements `Drop` or `Clone`) //! and use that as a field of a GC heap struct. //! //! //! # Why is it called "cell-gc"? //! //! In cell-gc, every field of every GC-managed object is mutable. //! You can't get *direct* references to the data; //! instead you use methods to get and set values. //! //! It's as though every field were a [Cell](http://doc.rust-lang.org/std/cell/struct.Cell.html). extern crate bit_vec; pub mod traits; mod pages; mod heap; mod gcref; mod gcleaf; pub mod collections; pub mod ptr; mod marking; pub use heap::{Heap, HeapSession, with_heap}; pub use gcref::GcRef; pub use gcleaf::GCLeaf; /// Return the number of allocations of a given type that fit in a "page". /// (Unstable. This is a temporary hack for testing.) pub fn page_capacity<'h, T: traits::IntoHeapAllocation<'h>>() -> usize { pages::TypedPage::<T::In>::capacity() }