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