TL;DR, please try to find potential soundness holes in this API, or confirm if you think that it should be sound
use std::{
marker::PhantomData,
mem::{self, ManuallyDrop},
};
pub trait TyConFor<'a> {
type Applied;
}
pub type Apply<'a, C> = <C as TyConFor<'a>>::Applied;
pub trait TyCon: for<'a> TyConFor<'a> {}
impl<C: ?Sized> TyCon for C where C: for<'a> TyConFor<'a> {}
pub struct Existential<'lower_bound, C>
where
C: TyCon,
{
marker: PhantomData<&'lower_bound ()>,
inner: Apply<'static, C>,
}
impl<'lower_bound, C> Existential<'lower_bound, C>
where
C: TyCon,
{
pub fn new<'a: 'lower_bound>(inner: Apply<'a, C>) -> Existential<'lower_bound, C> {
let inner = ManuallyDrop::new(inner);
unsafe {
Self {
marker: PhantomData,
inner: mem::transmute_copy::<Apply<'a, C>, Apply<'static, C>>(&inner),
}
}
}
pub fn with<'s, F, O>(&'s self, f: F) -> O
where
F: for<'a> FnOnce(&'s Apply<'a, C>, PhantomData<&'lower_bound &'a ()>) -> O,
{
f(&self.inner, PhantomData)
}
pub fn with_mut<'s, F, O>(&'s mut self, f: F) -> O
where
F: for<'a> FnOnce(&'s mut Apply<'a, C>, PhantomData<&'lower_bound &'a ()>) -> O,
{
f(&mut self.inner, PhantomData)
}
pub fn with_owned<F, O>(self, f: F) -> O
where
F: for<'a> FnOnce(Apply<'a, C>, PhantomData<&'lower_bound &'a ()>) -> O,
{
f(self.inner, PhantomData)
}
}
(code above contains one unsafe
block that uses mem::transmute_copy
)
(the same code in the playground, in case you don’t like copying stuff yourself)
By the way, I haven’t seen something like this anywhere else. If you have, please tell me
Context / example use case
I managed to use this abstraction in an arena-based self-referential struct. If you have something like
#[ouroboros::self_referencing]
struct Tree<T: 'static> {
dummy: (),
#[borrows(dummy)]
#[not_covariant]
arena: typed_arena::Arena<Node<'this, T>>,
#[borrows(arena)]
#[not_covariant]
root: &'this Node<'this, T>,
}
struct Node<'this, T> {
element: T,
children: std::cell::RefCell<Vec<&'this Node<'this, T>>>,
}
(this is somewhat simplified from a more practical use-case)
then it’s hard to write a by-reference iterator over all the T
’s. The problem is that you cannot store any copies of the &'this Node<'this, T>
references outside of Tree
, because such a type would need to mention the internal “'this
” lifetime of the self-referential struct. In particular, Node
is not covariant (otherwise you could get rid of the 'this
lifetime for such an iterator by subtype coercion). However, if you can create an existential type using the API above, it becomes possible:
impl<'s, T: 'static> IntoIterator for &'s Tree<T> {
type Item = &'s T;
type IntoIter = Iter<'s, T>;
fn into_iter(self) -> Self::IntoIter {
fn help_out_type_inference<'s, T: 'static, F, O>(f: F) -> F
where
F: for<'this> FnOnce(&'s &'this Node<'this, T>) -> O,
{
f
}
self.with_root(help_out_type_inference::<'s, T, _, _>(|root| Iter {
marker: PhantomData,
inner: Existential::new(IterInner { stack: vec![*root] }),
}))
}
}
struct IterInner<'this, T> {
stack: Vec<&'this Node<'this, T>>,
}
struct IterInnerCon<T>(PhantomData<T>);
impl<'this, T: 'static> TyConFor<'this> for IterInnerCon<T> {
type Applied = IterInner<'this, T>;
}
pub struct Iter<'s, T: 'static> {
marker: PhantomData<&'s T>,
inner: Existential<'s, IterInnerCon<T>>,
}
impl<'s, T: 'static> Iterator for Iter<'s, T> {
type Item = &'s T;
fn next<'a>(&'a mut self) -> Option<Self::Item> {
fn help_out_type_inference<'s, T: 'static, F, O>(f: F) -> F
where
F: for<'this> FnOnce(&mut IterInner<'this, T>, PhantomData<&'s &'this ()>) -> O,
{
f
}
self.inner
.with_mut(help_out_type_inference::<'s, T, _, _>(|inner, _| {
inner.stack.pop().map(|i| {
inner.stack.extend(i.children.borrow().iter().rev());
&i.element
})
}))
}
}
(only compiles on 1.56
or newer!)
dependencies of the example use case:
[dependencies]
ouroboros = "0.10.1"
typed-arena = "2.0.1"