jrsonnet_gcmodule/lib.rs
1#![deny(missing_docs)]
2#![cfg_attr(feature = "nightly", feature(coerce_unsized), feature(unsize))]
3#![cfg_attr(all(feature = "debug", feature = "nightly"), feature(specialization))]
4
5//! Reference cycle garbage collection inspired by
6//! [cpython](https://github.com/python/cpython/).
7//!
8//! The type [`Cc<T>`](type.Cc.html) provides shared ownership of a value of type `T`,
9//! similar to `std::rc::Rc<T>`. Unlike `Rc<T>`, [`collect_thread_cycles`](fn.collect_thread_cycles.html)
10//! can be used to drop unreachable values that form circular references.
11//!
12//! # Examples
13//!
14//! ## Cloning references
15//!
16//! Similar to `Rc<T>`, use `clone()` to get cloned references.
17//!
18//! ```
19//! use jrsonnet_gcmodule::Cc;
20//! let foo = Cc::new(vec![1, 2, 3]);
21//! let foo_cloned = foo.clone();
22//!
23//! // foo and foo_cloned both point to the same `vec![1, 2, 3]`.
24//! assert!(std::ptr::eq(&foo[0], &foo_cloned[0]));
25//! ```
26//!
27//! ## Collecting cycles
28//!
29//! Use [`collect_thread_cycles()`](fn.collect_thread_cycles.html) to collect
30//! thread-local garbage.
31//!
32//! Use [`count_thread_tracked()`](fn.count_thread_tracked.html) to count how
33//! many objects are tracked by the collector.
34//!
35//! ```
36//! use jrsonnet_gcmodule::{Cc, Trace, TraceBox};
37//! use std::cell::RefCell;
38//! {
39//! type List = Cc<RefCell<Vec<TraceBox<dyn Trace>>>>;
40//! let a: List = Default::default();
41//! let b: List = Default::default();
42//! a.borrow_mut().push(TraceBox(Box::new(b.clone())));
43//! b.borrow_mut().push(TraceBox(Box::new(a.clone())));
44//! }
45//!
46//! // a and b form circular references. The objects they point to are not
47//! // dropped automatically, despite both variables run out of scope.
48//!
49//! assert_eq!(jrsonnet_gcmodule::count_thread_tracked(), 2); // 2 values are tracked.
50//! assert_eq!(jrsonnet_gcmodule::collect_thread_cycles(), 2); // This will drop a and b.
51//! assert_eq!(jrsonnet_gcmodule::count_thread_tracked(), 0); // no values are tracked.
52//! ```
53# works fine in a single-thread environment.
58
59There are also [`ThreadedObjectSpace`](struct.ThreadedObjectSpace.html)
60and [`ThreadedCc`](type.ThreadedCc.html) for multi-thread usecases. Beware
61they take more memory, are slower, and a bit harder to use.
62
63```
64use jrsonnet_gcmodule::{ThreadedObjectSpace, ThreadedCc, Trace, TraceBox};
65use std::sync::Mutex;
66
67type List = ThreadedCc<Mutex<Vec<TraceBox<dyn Trace + Send + Sync>>>>;
68let space = ThreadedObjectSpace::default();
69{
70 let list1: List = space.create(Mutex::new(Default::default()));
71 let list2: List = space.create(Mutex::new(Default::default()));
72 let thread = std::thread::spawn(move || {
73 list1.borrow().lock().unwrap().push(TraceBox(Box::new(list2.clone())));
74 list2.borrow().lock().unwrap().push(TraceBox(Box::new(list1.clone())));
75 });
76 thread.join().unwrap();
77}
78assert_eq!(space.count_tracked(), 2);
79assert_eq!(space.collect_cycles(), 2);
80assert_eq!(space.count_tracked(), 0);
81```
82"##)]
83//!
84//! ## Defining new types
85//!
86//! [`Cc<T>`](type.Cc.html) requires [`Trace`](trait.Trace.html) implemented
87//! for `T` so the collector knows how values are referred. That can usually
88//! be done by `#[derive(Trace)]`.
89//!
90//! ### Acyclic types
91//!
92//! If a type is acyclic (cannot form reference circles about [`Cc`](type.Cc.html)),
93//! [`Trace::is_type_tracked()`](trait.Trace.html#method.is_type_tracked) will return `false`.
94//!
95//! ```
96//! use jrsonnet_gcmodule::{Cc, Trace};
97//!
98//! #[derive(Trace)]
99//! struct Foo(String);
100//!
101//! #[derive(Trace)]
102//! struct Bar;
103//!
104//! assert!(!Foo::is_type_tracked()); // Acyclic
105//! assert!(!Bar::is_type_tracked()); // Acyclic
106//!
107//! let foo = Cc::new(Foo("abc".to_string()));
108//! let bar = Cc::new(Bar);
109//! let foo_cloned = foo.clone(); // Share the same `"abc"` with `foo`.
110//! assert_eq!(jrsonnet_gcmodule::count_thread_tracked(), 0); // The collector tracks nothing.
111//! drop(foo); // The ref count of `"abc"` drops from 2 to 1.
112//! drop(foo_cloned); // `"abc"` will be dropped here..
113//! # drop(bar);
114//! ```
115//!
116//! ### Container types
117//!
118//! Whether a container type is acyclic or not depends on its fields. Usually,
119//! types without referring to trait objects or itself are considered acyclic.
120//!
121//! ```
122//! use jrsonnet_gcmodule::{Cc, Trace, TraceBox};
123//!
124//! #[derive(Trace)]
125//! struct Foo<T1: Trace, T2: Trace>(T1, T2, u8);
126//!
127//! // `a` is not tracked - types are acyclic.
128//! let a = Cc::new(Foo(Foo(Cc::new(1), 2, 3), Cc::new("abc"), 10));
129//! assert_eq!(jrsonnet_gcmodule::count_thread_tracked(), 0);
130//!
131//! // `b` is tracked because it contains a trait object.
132//! let b = Cc::new(Foo(TraceBox(Box::new(1) as Box<dyn Trace>), 2, 3));
133//! assert_eq!(jrsonnet_gcmodule::count_thread_tracked(), 1);
134//! ```
135//!
136//! The `#[skip_trace]` attribute can be used to skip tracking specified fields
137//! in a structure.
138//!
139//! ```
140//! use jrsonnet_gcmodule::{Cc, Trace};
141//!
142//! struct AlienStruct; // Does not implement Trace
143//!
144//! #[derive(Trace)]
145//! struct Foo {
146//! field: String,
147//!
148//! #[trace(skip)]
149//! alien: AlienStruct, // Field skipped in Trace implementation.
150//! }
151//! ```
152//!
153//! ### Weak references
154//!
155//! Similar to `std::rc::Rc`, use [`Cc::downgrade`](struct.RawCc.html#method.downgrade)
156//! to create weak references. Use [`Weak::upgrade`](struct.RawWeak.html#method.upgrade)
157//! to test if the value is still alive and to access the value. For example:
158//!
159//! ```
160//! use jrsonnet_gcmodule::{Cc, Weak};
161//!
162//! let value = Cc::new("foo");
163//! let weak: Weak<_> = value.downgrade();
164//! assert_eq!(*weak.upgrade().unwrap(), "foo");
165//! drop(value);
166//! assert!(weak.upgrade().is_none()); // Cannot upgrade after dropping value
167//! ```
168//!
169//! # Technical Details
170//!
171//! ## Memory Layouts
172//!
173//! [`Cc<T>`](type.Cc.html) uses different memory layouts depending on `T`.
174//!
175//! ### Untracked types
176//!
177//! If [`<T as Trace>::is_type_tracked()`](trait.Trace.html#method.is_type_tracked)
178//! returns `false`, the layout is similar to `Rc<T>`:
179//!
180//! ```plain,ignore
181//! Shared T Pointer
182//! +-------------------+ .-- Cc<T>
183//! | ref_count: usize | <--<
184//! | weak_count: usize | '-- Cc<T>::clone()
185//! |-------------------|
186//! | T (shared data) | <--- Cc<T>::deref()
187//! +-------------------+
188//! ```
189//!
190//! ### Tracked types
191//!
192//! If [`<T as Trace>::is_type_tracked()`](trait.Trace.html#method.is_type_tracked)
193//! returns `true`, the layout has an extra `GcHeader` that makes the value visible
194//! in a thread-local linked list:
195//!
196//! ```plain,ignore
197//! Shared T with GcHeader
198//! +-------------------+
199//! | gc_prev: pointer | ---> GcHeader in a linked list.
200//! | gc_next: pointer |
201//! | vptr<T>: pointer | ---> Pointer to the `&T as &dyn Trace` virtual table.
202//! |-------------------|
203//! | ref_count: usize | <--- Cc<T>
204//! | weak_count: usize |
205//! | ----------------- |
206//! | T (shared data) | <--- Cc<T>::deref()
207//! +-------------------+
208//! ```
209//!
210//! ## Incorrect `Trace` implementation
211//!
212//! While most public APIs provided by this library looks safe, incorrectly
213//! implementing the [`Trace`](trait.Trace.html) trait has consequences.
214//!
215//! This library should cause no undefined behaviors (UB) even with incorrect
216//! [`Trace`](trait.Trace.html) implementation on _debug_ build.
217//!
218//! Below are some consequences of a wrong [`Trace`](trait.Trace.html)
219//! implementation.
220//!
221//! ### Memory leak
222//!
223//! If [`Trace::trace`](trait.Trace.html#method.trace) does not visit all
224//! referred values, the collector might fail to detect cycles, and take
225//! no actions on cycles. That causes memory leak.
226//!
227//! Note: there are other ways to cause memory leak unrelated to an incorrect
228//! [`Trace`](trait.Trace.html) implementation. For example, forgetting
229//! to call collect functions can cause memory leak. When using the advanced
230//! [`ObjectSpace`](struct.ObjectSpace.html) APIs, objects in one space
231//! referring to objects in a different space can cause memory leak.
232//!
233//! ### Panic
234//!
235//! If [`Trace::trace`](trait.Trace.html#method.trace) visits more values
236//! than it should (for example, visit indirectly referred values, or visit
237//! a directly referred value multiple times), the collector can detect
238//! such issues and panic the thread with the message:
239//!
240//! ```plain,ignore
241//! bug: unexpected ref-count after dropping cycles
242//! This usually indicates a buggy Trace or Drop implementation.
243//! ```
244//!
245//! ### Undefined behavior (UB)
246//!
247//! After the above panic (`bug: unexpected ref-count after dropping cycles`),
248//! dereferencing a garbage-collected [`Cc<T>`](type.Cc.html) will trigger
249//! `panic!` or UB depending on whether it's a debug build or not.
250//!
251//! On debug build, sanity checks are added at `Cc::<T>::deref()`.
252//! It will panic if `T` was garbage-collected:
253//!
254//! ```plain,ignore
255//! bug: accessing a dropped CcBox detected
256//! ```
257//!
258//! In other words, no UB on debug build.
259//!
260//! On release build the dereference would access dropped values, which is an
261//! undefined behavior. Again, the UB can only happen if the [`Trace::trace`](trait.Trace.html#method.trace)
262//! is implemented wrong, and panic will happen before the UB.
263
264extern crate self as jrsonnet_gcmodule;
265
266mod cc;
267mod cc_impls;
268mod collect;
269#[cfg(test)]
270mod debug;
271mod ref_count;
272#[cfg(feature = "sync")]
273mod sync;
274#[cfg(test)]
275mod tests;
276#[cfg(any(test, feature = "testutil"))]
277pub mod testutil;
278mod trace;
279mod trace_impls;
280
281pub use trace_impls::TraceBox;
282
283pub use cc::{Cc, RawCc, RawWeak, Weak};
284pub use collect::{
285 collect_thread_cycles, count_thread_tracked, with_thread_object_space, ObjectSpace,
286};
287pub use trace::{Trace, Tracer};
288
289#[cfg(feature = "sync")]
290pub use sync::{collect::ThreadedObjectSpace, ThreadedCc, ThreadedCcRef};
291
292/// Derive [`Trace`](trait.Trace.html) implementation for a structure.
293///
294/// # Examples
295///
296/// ```
297/// use jrsonnet_gcmodule::{Cc, Trace};
298///
299/// #[derive(Trace)]
300/// struct S1(u32, String);
301///
302/// #[derive(Trace)]
303/// struct S2<T1: Trace, T2: Trace>(T1, T2, u8);
304///
305/// #[derive(Trace)]
306/// struct S3<T: Trace> {
307/// a: S1,
308/// b: Option<S2<T, u8>>,
309///
310/// #[trace(skip)]
311/// c: AlienStruct, // c is not tracked by the collector.
312/// }
313///
314/// struct AlienStruct;
315/// ```
316#[cfg(feature = "derive")]
317pub use jrsonnet_gcmodule_derive::Trace;
318
319#[cfg(not(test))]
320mod debug {
321 #[cfg(any(feature = "debug", feature = "testutil", test))]
322 thread_local!(pub(crate) static NEXT_DEBUG_NAME: std::cell::Cell<usize> = Default::default());
323 #[cfg(any(feature = "debug", test))]
324 thread_local!(pub(crate) static GC_DROPPING: std::cell::Cell<bool> = Cell::new(false));
325 pub(crate) fn log<S1: ToString, S2: ToString>(func: impl Fn() -> (S1, S2)) {
326 if cfg!(feature = "debug") {
327 let (name, message) = func();
328 eprintln!("[gc] {} {}", name.to_string(), message.to_string());
329 }
330 }
331}
332
333/// Whether the `debug` feature is enabled.
334pub const DEBUG_ENABLED: bool = cfg!(feature = "debug");
335
336/// Jrsonnet golang bindings require that it is possible to move jsonnet
337/// VM between OS threads, and this is not possible due to usage of
338/// `thread_local`. Instead, there is two methods added, one should be
339/// called at the end of current thread work, and one that should be
340/// used when using other thread.
341// It won't be able to preserve debug state.
342#[cfg(not(any(test, feature = "debug")))]
343pub mod interop {
344 use std::mem;
345
346 use crate::collect::{new_gc_list, OwnedGcHeader, THREAD_OBJECT_SPACE};
347
348 /// Type-erased gc object list
349 pub enum GcState {}
350
351 type UnerasedState = OwnedGcHeader;
352
353 /// Dump current interned string pool, to be restored by
354 /// `reenter_thread`
355 ///
356 /// # Safety
357 ///
358 /// Current thread gc becomes broken after this call, you should not use gc after this
359 /// call, and before `reenter_thread` call.
360 pub unsafe fn exit_thread() -> *mut GcState {
361 let object_list: UnerasedState = THREAD_OBJECT_SPACE
362 .with(|space| mem::replace(&mut *space.list.borrow_mut(), new_gc_list()));
363 Box::into_raw(Box::new(object_list)).cast()
364 }
365
366 /// Reenter thread, using state dumped by `exit_thread`.
367 ///
368 /// # Safety
369 ///
370 /// `state` should be acquired from `exit_thread`, it is not allowed
371 /// to reuse state to reenter multiple threads.
372 pub unsafe fn reenter_thread(state: *mut GcState) {
373 let ptr: *mut UnerasedState = state.cast();
374 // SAFETY: ptr is an unique state per method safety requirements.
375 let ptr: Box<UnerasedState> = unsafe { Box::from_raw(ptr) };
376 let ptr: UnerasedState = *ptr;
377 THREAD_OBJECT_SPACE.with(|space| {
378 let _ = mem::replace(&mut *space.list.borrow_mut(), ptr);
379 });
380 }
381}
382
383#[cfg(test)]
384mod dyn_cc {
385 use crate::Trace;
386 use std::fmt::Debug;
387
388 use crate::cc_dyn;
389
390 #[derive(Debug, Trace)]
391 struct Test {
392 a: String,
393 }
394
395 trait DebugAndTrace: Debug + Trace {}
396 impl<T> DebugAndTrace for T where T: Debug + Trace {}
397 cc_dyn!(
398 #[derive(Debug)]
399 CcDebugAndTrace,
400 DebugAndTrace
401 );
402
403 trait BorrowTy<O> {
404 fn borrow_ty(&self) -> &O;
405 }
406 cc_dyn!(CcBorrowTy<O>, BorrowTy<O>);
407 cc_dyn!(
408 CcBorrowTyAlsoDebug<O: Debug>,
409 BorrowTy<O>
410 );
411
412 #[derive(Trace)]
413 struct Borrowable<T: Trace> {
414 v: T,
415 }
416 impl<T: Trace> BorrowTy<T> for Borrowable<T> {
417 fn borrow_ty(&self) -> &T {
418 &self.v
419 }
420 }
421
422 #[test]
423 fn test_dyn() {
424 let test = Test {
425 a: "hello".to_owned(),
426 };
427
428 let dynccgeneric = CcBorrowTy::new(Borrowable { v: 1u32 });
429 let v = dynccgeneric.0.borrow_ty();
430 assert_eq!(*v, 1);
431
432 let dynccgeneric = CcBorrowTyAlsoDebug::new(Borrowable { v: 1u32 });
433 let v = dynccgeneric.0.borrow_ty();
434 assert_eq!(*v, 1);
435
436 let dyncc = CcDebugAndTrace::new(test);
437 assert_eq!(
438 format!("{dyncc:?}"),
439 "CcDebugAndTrace(Cc(Test { a: \"hello\" }))"
440 );
441 let dyncc_is_trace = dyncc;
442 assert_eq!(
443 format!("{dyncc_is_trace:?}"),
444 "CcDebugAndTrace(Cc(Test { a: \"hello\" }))"
445 );
446 let dyncc_is_trace_as_dyn = CcDebugAndTrace::new(dyncc_is_trace);
447 assert_eq!(
448 format!("{dyncc_is_trace_as_dyn:?}"),
449 "CcDebugAndTrace(Cc(CcDebugAndTrace(Cc(Test { a: \"hello\" }))))"
450 );
451 }
452}