20024290994

Committed 08 Dec 2025 10:08AM UTC coverage: 58.613% (+0.01%) from 58.6%

Build # 20024290994

Build Type

push

github

Committed by

fasterthanlime

Commit Message

feat: compute variance automatically from field types

This implements automatic variance computation for derived types:

- Change `Shape.variance` from `fn() -> Variance` to `fn(&'static Shape) -> Variance`
  to allow variance functions to walk type structure without capturing generics

- Add `Shape::computed_variance()` that walks struct fields, enum variants,
  and inner shapes (for Box, Vec, Option, etc.) to compute variance

- Use thread-local cycle detection to prevent stack overflow with recursive types.
  When a cycle is detected, returns `Covariant` (identity for `combine`)

- Update derive macros to use `.variance(Shape::computed_variance)`
  instead of generating per-type variance computation code

- Update `Box<T>` to use computed variance (depends on T's variance)
  instead of hardcoded `Invariant`

- Add variance tests for recursive types

Closes #1171

Run Details

44 of 60 new or added lines in 3 files covered. (73.33%)

487 existing lines in 23 files now uncovered.

24730 of 42192 relevant lines covered (58.61%)

544.95 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.93

/facet-core/src/impls_std/hashset.rs

use crate::Variance;
use core::hash::BuildHasher;
use core::ptr::NonNull;
use std::collections::HashSet;

use crate::ptr::{PtrConst, PtrMut};

use crate::{
    Def, Facet, IterVTable, SetDef, SetVTable, Shape, Type, TypeParam, UserType, ValueVTable,
};

type HashSetIterator<'mem, T> = std::collections::hash_set::Iter<'mem, T>;

unsafe impl<'a, T, S> Facet<'a> for HashSet<T, S>
where
    T: Facet<'a> + core::cmp::Eq + core::hash::Hash,
    S: Facet<'a> + Default + BuildHasher,
{
    const SHAPE: &'static Shape = &const {
        Shape {
            id: Shape::id_of::<Self>(),
            layout: Shape::layout_of::<Self>(),
            vtable: ValueVTable {
                type_name: |f, opts| {
                    write!(f, "{}<", Self::SHAPE.type_identifier)?;
                    if let Some(opts) = opts.for_children() {
                        (T::SHAPE.vtable.type_name())(f, opts)?;
                    } else {
                        write!(f, "…")?;
                    }
                    write!(f, ">")
                },
                drop_in_place: ValueVTable::drop_in_place_for::<Self>(),
                default_in_place: Some(|target| unsafe { target.put(Self::default()) }),
                ..ValueVTable::new(|_, _| Ok(()))
            },
            ty: Type::User(UserType::Opaque),
            def: Def::Set(SetDef::new(
                &const {
                    SetVTable::new(
                        |uninit, capacity| unsafe {
                            uninit.put(Self::with_capacity_and_hasher(capacity, S::default()))
                        },
                        |ptr, item| unsafe {
                            let set = ptr.as_mut::<HashSet<T>>();
                            let item = item.read::<T>();
                            set.insert(item)
                        },
                        |ptr| unsafe {
                            let set = ptr.get::<HashSet<T>>();
                            set.len()
                        },
                        |ptr, item| unsafe {
                            let set = ptr.get::<HashSet<T>>();
                            set.contains(item.get())
                        },
                        IterVTable {
                            init_with_value: Some(|ptr| unsafe {
                                let set = ptr.get::<HashSet<T>>();
                                let iter: HashSetIterator<'_, T> = set.iter();
                                let iter_state = Box::new(iter);
                                PtrMut::new(NonNull::new_unchecked(
                                    Box::into_raw(iter_state) as *mut u8
                                ))
                            }),
                            next: |iter_ptr| unsafe {
                                let state = iter_ptr.as_mut::<HashSetIterator<'_, T>>();
                                state
                                    .next()
                                    .map(|value| PtrConst::new(NonNull::from(value)))
                            },
                            next_back: None,
                            size_hint: None,
                            dealloc: |iter_ptr| unsafe {
                                drop(Box::from_raw(iter_ptr.as_ptr::<HashSetIterator<'_, T>>()
                                    as *mut HashSetIterator<'_, T>));
                            },
                        },
                    )
                },
                T::SHAPE,
            )),
            type_identifier: "HashSet",
            type_params: &[
                TypeParam {
                    name: "T",
                    shape: T::SHAPE,
                },
                TypeParam {
                    name: "S",
                    shape: S::SHAPE,
                },
            ],
            doc: &[],
            attributes: &[],
            type_tag: None,
            inner: None,
            proxy: None,
            // HashSet<T, S> is covariant in T, but we use INVARIANT as a safe
            // conservative default since computed_variance doesn't yet support
            // multiple type parameters
            variance: Variance::INVARIANT,
        }
    };
}

#[cfg(test)]
mod tests {
    use alloc::string::String;
    use core::ptr::NonNull;
    use std::collections::HashSet;
    use std::hash::RandomState;

    use super::*;

    #[test]
    fn test_hashset_type_params() {
        // HashSet should have a type param for both its value type
        // and its hasher state
        let [type_param_1, type_param_2] = <HashSet<i32>>::SHAPE.type_params else {
            panic!("HashSet<T> should have 2 type params")
        };
        assert_eq!(type_param_1.shape(), i32::SHAPE);
        assert_eq!(type_param_2.shape(), RandomState::SHAPE);
    }

    #[test]
    fn test_hashset_vtable_1_new_insert_iter_drop() {
        facet_testhelpers::setup();

        let hashset_shape = <HashSet<String>>::SHAPE;
        let hashset_def = hashset_shape
            .def
            .into_set()
            .expect("HashSet<T> should have a set definition");

        // Allocate memory for the HashSet
        let hashset_uninit_ptr = hashset_shape.allocate().unwrap();

        // Create the HashSet with a capacity of 3
        let hashset_ptr =
            unsafe { (hashset_def.vtable.init_in_place_with_capacity_fn)(hashset_uninit_ptr, 3) };

        // The HashSet is empty, so ensure its length is 0
        let hashset_actual_length = unsafe { (hashset_def.vtable.len_fn)(hashset_ptr.as_const()) };
        assert_eq!(hashset_actual_length, 0);

        // 5 sample values to insert
        let strings = ["foo", "bar", "bazz", "fizzbuzz", "fifth thing"];

        // Insert the 5 values into the HashSet
        let mut hashset_length = 0;
        for string in strings {
            // Create the value
            let mut new_value = core::mem::ManuallyDrop::new(string.to_string());

            // Insert the value
            let did_insert = unsafe {
                (hashset_def.vtable.insert_fn)(
                    hashset_ptr,
                    PtrMut::new(NonNull::from(&mut new_value)),
                )
            };

            assert!(did_insert, "expected value to be inserted in the HashSet");

            // Ensure the HashSet's length increased by 1
            hashset_length += 1;
            let hashset_actual_length =
                unsafe { (hashset_def.vtable.len_fn)(hashset_ptr.as_const()) };
            assert_eq!(hashset_actual_length, hashset_length);
        }

        // Insert the same 5 values again, ensuring they are deduplicated
        for string in strings {
            // Create the value
            let mut new_value = core::mem::ManuallyDrop::new(string.to_string());

            // Try to insert the value
            let did_insert = unsafe {
                (hashset_def.vtable.insert_fn)(
                    hashset_ptr,
                    PtrMut::new(NonNull::from(&mut new_value)),
                )
            };

            assert!(
                !did_insert,
                "expected value to not be inserted in the HashSet"
            );

            // Ensure the HashSet's length did not increase
            let hashset_actual_length =
                unsafe { (hashset_def.vtable.len_fn)(hashset_ptr.as_const()) };
            assert_eq!(hashset_actual_length, hashset_length);
        }

        // Create a new iterator over the HashSet
        let iter_init_with_value_fn = hashset_def.vtable.iter_vtable.init_with_value.unwrap();
        let hashset_iter_ptr = unsafe { iter_init_with_value_fn(hashset_ptr.as_const()) };

        // Collect all the items from the HashSet's iterator
        let mut iter_items = HashSet::<&str>::new();
        loop {
            // Get the next item from the iterator
            let item_ptr = unsafe { (hashset_def.vtable.iter_vtable.next)(hashset_iter_ptr) };
            let Some(item_ptr) = item_ptr else {
                break;
            };

            let item = unsafe { item_ptr.get::<String>() };

            // Insert the item into the set of items returned from the iterator
            let did_insert = iter_items.insert(&**item);

            assert!(did_insert, "HashSet iterator returned duplicate item");
        }

        // Deallocate the iterator
        unsafe {
            (hashset_def.vtable.iter_vtable.dealloc)(hashset_iter_ptr);
        }

        // Ensure the iterator returned all of the strings
        assert_eq!(iter_items, strings.iter().copied().collect::<HashSet<_>>());

        // Get the function pointer for dropping the HashSet
        let drop_fn = hashset_shape
            .vtable
            .drop_in_place
            .expect("HashSet<T> should have drop_in_place");

        // Drop the HashSet in place
        unsafe { drop_fn(hashset_ptr) };

        // Deallocate the memory
        unsafe { hashset_shape.deallocate_mut(hashset_ptr).unwrap() };
    }
}

1	use crate::Variance;
2	use core::hash::BuildHasher;
3	use core::ptr::NonNull;
4	use std::collections::HashSet;
5
6	use crate::ptr::{PtrConst, PtrMut};
7
8	use crate::{
9	Def, Facet, IterVTable, SetDef, SetVTable, Shape, Type, TypeParam, UserType, ValueVTable,
10	};
11
12	type HashSetIterator<'mem, T> = std::collections::hash_set::Iter<'mem, T>;
13
14	unsafe impl<'a, T, S> Facet<'a> for HashSet<T, S>
15	where
16	T: Facet<'a> + core::cmp::Eq + core::hash::Hash,
17	S: Facet<'a> + Default + BuildHasher,
18	{
19	const SHAPE: &'static Shape = &const {
20	Shape {
21	id: Shape::id_of::<Self>(),
22	layout: Shape::layout_of::<Self>(),
23	vtable: ValueVTable {
24	type_name: \|f, opts\| {	6✔
25	write!(f, "{}<", Self::SHAPE.type_identifier)?;	6✔
26	if let Some(opts) = opts.for_children() {	6✔
27	(T::SHAPE.vtable.type_name())(f, opts)?;	6✔
28	} else {
UNCOV 29	write!(f, "…")?;	×
30	}
31	write!(f, ">")	6✔
32	},	6✔
33	drop_in_place: ValueVTable::drop_in_place_for::<Self>(),
34	default_in_place: Some(\|target\| unsafe { target.put(Self::default()) }),	×
UNCOV 35	..ValueVTable::new(\|_, _\| Ok(()))	×
36	},
37	ty: Type::User(UserType::Opaque),
38	def: Def::Set(SetDef::new(
39	&const {
40	SetVTable::new(
41	\|uninit, capacity\| unsafe {
42	uninit.put(Self::with_capacity_and_hasher(capacity, S::default()))	12✔
43	},	12✔
44	\|ptr, item\| unsafe {
45	let set = ptr.as_mut::<HashSet<T>>();	37✔
46	let item = item.read::<T>();	37✔
47	set.insert(item)	37✔
48	},	37✔
49	\|ptr\| unsafe {
50	let set = ptr.get::<HashSet<T>>();	13✔
51	set.len()	13✔
52	},	13✔
53	\|ptr, item\| unsafe {
54	let set = ptr.get::<HashSet<T>>();	×
55	set.contains(item.get())	×
UNCOV 56	},	×
57	IterVTable {
58	init_with_value: Some(\|ptr\| unsafe {
59	let set = ptr.get::<HashSet<T>>();	6✔
60	let iter: HashSetIterator<'_, T> = set.iter();	6✔
61	let iter_state = Box::new(iter);	6✔
62	PtrMut::new(NonNull::new_unchecked(	6✔
63	Box::into_raw(iter_state) as *mut u8	6✔
64	))
65	}),	6✔
66	next: \|iter_ptr\| unsafe {
67	let state = iter_ptr.as_mut::<HashSetIterator<'_, T>>();	19✔
68	state	19✔
69	.next()	19✔
70	.map(\|value\| PtrConst::new(NonNull::from(value)))	19✔
71	},	19✔
72	next_back: None,
73	size_hint: None,
74	dealloc: \|iter_ptr\| unsafe {
75	drop(Box::from_raw(iter_ptr.as_ptr::<HashSetIterator<'_, T>>()	6✔
76	as *mut HashSetIterator<'_, T>));	6✔
77	},	6✔
78	},
79	)
80	},
81	T::SHAPE,
82	)),
83	type_identifier: "HashSet",
84	type_params: &[
85	TypeParam {
86	name: "T",
87	shape: T::SHAPE,
88	},
89	TypeParam {
90	name: "S",
91	shape: S::SHAPE,
92	},
93	],
94	doc: &[],
95	attributes: &[],
96	type_tag: None,
97	inner: None,
98	proxy: None,
99	// HashSet<T, S> is covariant in T, but we use INVARIANT as a safe
100	// conservative default since computed_variance doesn't yet support
101	// multiple type parameters
102	variance: Variance::INVARIANT,
103	}
104	};
105	}
106
107	#[cfg(test)]
108	mod tests {
109	use alloc::string::String;
110	use core::ptr::NonNull;
111	use std::collections::HashSet;
112	use std::hash::RandomState;
113
114	use super::*;
115
116	#[test]
117	fn test_hashset_type_params() {	1✔
118	// HashSet should have a type param for both its value type
119	// and its hasher state
120	let [type_param_1, type_param_2] = <HashSet<i32>>::SHAPE.type_params else {	1✔
UNCOV 121	panic!("HashSet<T> should have 2 type params")	×
122	};
123	assert_eq!(type_param_1.shape(), i32::SHAPE);	1✔
124	assert_eq!(type_param_2.shape(), RandomState::SHAPE);	1✔
125	}	1✔
126
127	#[test]
128	fn test_hashset_vtable_1_new_insert_iter_drop() {	1✔
129	facet_testhelpers::setup();	1✔
130
131	let hashset_shape = <HashSet<String>>::SHAPE;	1✔
132	let hashset_def = hashset_shape	1✔
133	.def	1✔
134	.into_set()	1✔
135	.expect("HashSet<T> should have a set definition");	1✔
136
137	// Allocate memory for the HashSet
138	let hashset_uninit_ptr = hashset_shape.allocate().unwrap();	1✔
139
140	// Create the HashSet with a capacity of 3
141	let hashset_ptr =	1✔
142	unsafe { (hashset_def.vtable.init_in_place_with_capacity_fn)(hashset_uninit_ptr, 3) };	1✔
143
144	// The HashSet is empty, so ensure its length is 0
145	let hashset_actual_length = unsafe { (hashset_def.vtable.len_fn)(hashset_ptr.as_const()) };	1✔
146	assert_eq!(hashset_actual_length, 0);	1✔
147
148	// 5 sample values to insert
149	let strings = ["foo", "bar", "bazz", "fizzbuzz", "fifth thing"];	1✔
150
151	// Insert the 5 values into the HashSet
152	let mut hashset_length = 0;	1✔
153	for string in strings {	5✔
154	// Create the value
155	let mut new_value = core::mem::ManuallyDrop::new(string.to_string());	5✔
156
157	// Insert the value
158	let did_insert = unsafe {	5✔
159	(hashset_def.vtable.insert_fn)(	5✔
160	hashset_ptr,	5✔
161	PtrMut::new(NonNull::from(&mut new_value)),	5✔
162	)	5✔
163	};
164
165	assert!(did_insert, "expected value to be inserted in the HashSet");	5✔
166
167	// Ensure the HashSet's length increased by 1
168	hashset_length += 1;	5✔
169	let hashset_actual_length =	5✔
170	unsafe { (hashset_def.vtable.len_fn)(hashset_ptr.as_const()) };	5✔
171	assert_eq!(hashset_actual_length, hashset_length);	5✔
172	}
173
174	// Insert the same 5 values again, ensuring they are deduplicated
175	for string in strings {	5✔
176	// Create the value
177	let mut new_value = core::mem::ManuallyDrop::new(string.to_string());	5✔
178
179	// Try to insert the value
180	let did_insert = unsafe {	5✔
181	(hashset_def.vtable.insert_fn)(	5✔
182	hashset_ptr,	5✔
183	PtrMut::new(NonNull::from(&mut new_value)),	5✔
184	)	5✔
185	};
186
187	assert!(	5✔
188	!did_insert,	5✔
189	"expected value to not be inserted in the HashSet"
190	);
191
192	// Ensure the HashSet's length did not increase
193	let hashset_actual_length =	5✔
194	unsafe { (hashset_def.vtable.len_fn)(hashset_ptr.as_const()) };	5✔
195	assert_eq!(hashset_actual_length, hashset_length);	5✔
196	}
197
198	// Create a new iterator over the HashSet
199	let iter_init_with_value_fn = hashset_def.vtable.iter_vtable.init_with_value.unwrap();	1✔
200	let hashset_iter_ptr = unsafe { iter_init_with_value_fn(hashset_ptr.as_const()) };	1✔
201
202	// Collect all the items from the HashSet's iterator
203	let mut iter_items = HashSet::<&str>::new();	1✔
204	loop {
205	// Get the next item from the iterator
206	let item_ptr = unsafe { (hashset_def.vtable.iter_vtable.next)(hashset_iter_ptr) };	6✔
207	let Some(item_ptr) = item_ptr else {	6✔
208	break;	1✔
209	};
210
211	let item = unsafe { item_ptr.get::<String>() };	5✔
212
213	// Insert the item into the set of items returned from the iterator
214	let did_insert = iter_items.insert(&**item);	5✔
215
216	assert!(did_insert, "HashSet iterator returned duplicate item");	5✔
217	}
218
219	// Deallocate the iterator
220	unsafe {	1✔
221	(hashset_def.vtable.iter_vtable.dealloc)(hashset_iter_ptr);	1✔
222	}	1✔
223
224	// Ensure the iterator returned all of the strings
225	assert_eq!(iter_items, strings.iter().copied().collect::<HashSet<_>>());	1✔
226
227	// Get the function pointer for dropping the HashSet
228	let drop_fn = hashset_shape	1✔
229	.vtable	1✔
230	.drop_in_place	1✔
231	.expect("HashSet<T> should have drop_in_place");	1✔
232
233	// Drop the HashSet in place
234	unsafe { drop_fn(hashset_ptr) };	1✔
235
236	// Deallocate the memory
237	unsafe { hashset_shape.deallocate_mut(hashset_ptr).unwrap() };	1✔
238	}	1✔
239	}

facet-rs / facet / 20024290994

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous