| -rw-r--r-- | Cargo.lock | 18 | ||||
| -rw-r--r-- | Cargo.toml | 2 | ||||
| -rw-r--r-- | src/any.rs | 235 | ||||
| -rw-r--r-- | src/builtins/visitor/value.rs | 28 | ||||
| -rw-r--r-- | src/lib.rs | 13 | ||||
| -rw-r--r-- | src/protocol.rs | 205 | ||||
| -rw-r--r-- | src/symbol.rs | 1 |
7 files changed, 414 insertions, 88 deletions
@@ -304,6 +304,15 @@ dependencies = [ ] [[package]] +name = "treaty" +version = "0.1.0" +dependencies = [ + "macro_rules_attribute", + "proptest", + "serde", +] + +[[package]] name = "unarray" version = "0.1.4" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -316,15 +325,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" [[package]] -name = "uniserde" -version = "0.1.0" -dependencies = [ - "macro_rules_attribute", - "proptest", - "serde", -] - -[[package]] name = "wait-timeout" version = "0.2.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -1,5 +1,5 @@ [package] -name = "uniserde" +name = "treaty" version = "0.1.0" edition = "2021" diff --git a/src/any.rs b/src/any.rs new file mode 100644 index 0000000..b7699ff --- /dev/null +++ b/src/any.rs @@ -0,0 +1,235 @@ +//! Heapless type erasure. +//! +//! [`Any`] is generic over the type of indirection (`&T`, `&mut T`, `Box<T>`) +//! and allows erasing the `T` of the indirection. This is similar to replacing the `T` with +//! [`core::any::Any`]. The main difference to [`core::any::Any`] is + +use core::{any::TypeId, marker::{PhantomData, PhantomPinned}, mem::{MaybeUninit, ManuallyDrop}}; + +pub trait TypeNameable<'lt> { + type Name: TypeName<'lt, Nameable = Self>; +} + +pub trait TypeName<'lt>: 'static { + type Nameable: ?Sized + TypeNameable<'lt, Name = Self>; +} + +const INDIRECT_SIZE: usize = core::mem::size_of::<usize>() * 2; + +#[derive(Clone, Copy)] +#[repr(transparent)] +pub struct RawIndirectAny(MaybeUninit<[u8; INDIRECT_SIZE]>); + +pub unsafe trait Indirect<'a> { + type ForT<T: ?Sized + 'a>: 'a; + + fn into_any<T: ?Sized + 'a>(value: Self::ForT<T>) -> RawIndirectAny; + + unsafe fn from_any<T: ?Sized + 'a>(any: RawIndirectAny) -> Self::ForT<T>; +} + +trait Helper {} + +/// A `&T` indirection. +pub enum Ref {} + +const _: () = assert!(core::mem::size_of::<&dyn Helper>() <= core::mem::size_of::<RawIndirectAny>()); + +unsafe impl<'a> Indirect<'a> for Ref { + type ForT<T: ?Sized + 'a> = &'a T; + + fn into_any<T: ?Sized + 'a>(value: &'a T) -> RawIndirectAny { + unsafe { transmute::<&'a T, RawIndirectAny>(value) } + } + + unsafe fn from_any<T: ?Sized + 'a>(any: RawIndirectAny) -> &'a T { + unsafe { transmute::<RawIndirectAny, &'a T>(any) } + } +} + +/// A `&mut T` indirection. +pub enum Mut {} + +const _: () = assert!(core::mem::size_of::<&mut dyn Helper>() <= core::mem::size_of::<RawIndirectAny>()); + +unsafe impl<'a> Indirect<'a> for Mut { + type ForT<T: ?Sized + 'a> = &'a mut T; + + fn into_any<T: ?Sized + 'a>(value: &'a mut T) -> RawIndirectAny { + unsafe { transmute::<&'a mut T, RawIndirectAny>(value) } + } + + unsafe fn from_any<T: ?Sized + 'a>(any: RawIndirectAny) -> &'a mut T { + unsafe { transmute::<RawIndirectAny, &'a mut T>(any) } + } +} + +#[cfg(feature = "alloc")] +pub use boxed::*; +#[cfg(feature = "alloc")] +mod boxed { + use super::*; + + #[cfg(not(feature = "std"))] + use alloc::boxed::Box; + + /// A `Box<T>` indirection. + pub enum Boxed {} + + const _: () = assert!(core::mem::size_of::<Box<dyn Helper>>() <= core::mem::size_of::<RawIndirectAny>()); + + unsafe impl<'a> Indirect<'a> for Boxed { + type ForT<T: ?Sized + 'a> = Box<T>; + + fn into_any<T: ?Sized + 'a>(value: Box<T>) -> RawIndirectAny { + unsafe { transmute::<Box<T>, RawIndirectAny>(value) } + } + + unsafe fn from_any<T: ?Sized + 'a>(any: RawIndirectAny) -> Box<T> { + unsafe { transmute::<RawIndirectAny, Box<T>>(any) } + } + } +} + +/// Container for (almost) any indirection. +/// +/// An indirection is something like a `&T` that is a pointer. +/// The `'a` lifetime is the lifetime of the indirection, and `'lt` +/// is a lifetime the stored value's `T` can contain. +/// +/// This type is designed to allow using a generic containing type with +/// a trait object method. While the value is stored in the [`Any`] it cannot +/// be accessed. The [`Any`] must be downcasted with [`Any::downcast()`] to access +/// the value. +#[must_use] +pub struct Any<'a, 'lt: 'a, I: Indirect<'a>> { + /// The meta information about the value is stored as a function pointer + /// to reduce it's size to one pointer. + info: fn() -> (TypeId, unsafe fn(RawIndirectAny)), + + /// The indirect pointer. + indirect: RawIndirectAny, + + /// Invariant over `'lt` and holding a `I::ForT`. + _marker: PhantomData<(I::ForT<()>, *mut &'lt (), PhantomPinned)>, +} + +impl<'a, 'lt, I: Indirect<'a>> Drop for Any<'a, 'lt, I> { + fn drop(&mut self) { + // We need to drop the stored value. + + // Lookup drop function. + let (_, drop_fn) = (self.info)(); + + // SAFETY: self.indirect is never touched again. + // Additionally, we know that drop_fn is for this self.indirect because it was + // made by Self::new. + unsafe { drop_fn(self.indirect) }; + } +} + +impl<'a, 'lt, I: Indirect<'a>> Any<'a, 'lt, I> { + /// Wrap an indirection. + /// + /// The inner type `T` of the indirection is erased. + pub fn new<T: TypeNameable<'lt>>(indirect: I::ForT<T>) -> Self { + Self { + info: || ( + TypeId::of::<T::Name>(), + |raw| { + // SAFETY: This is only called in the drop impl. + unsafe { drop(I::from_any::<T>(raw)) + }} + ), + indirect: I::into_any(indirect), + _marker: PhantomData, + } + } + + /// Downcast to an indirection with a given `T` type. + /// + /// If the type of the stored value is different, then `self` is + /// returned as is. + pub fn downcast<T: TypeNameable<'lt>>(self) -> Result<I::ForT<T>, Self> { + let (id, _) = (self.info)(); + + if id == TypeId::of::<T::Name>() { + Ok(unsafe { I::from_any(self.indirect) }) + } else { + Err(self) + } + } + + /// Type ID of the stored value's `T`. + pub fn id(&self) -> TypeId { + (self.info)().0 + } +} + +/// # Safety +/// Same rules as [`core::mem::transmute()`]. +unsafe fn transmute<T, U>(value: T) -> U { + // Create union type that can store a `T` or a `U`. + // We can then use this to convert between them. + // + // The repr(C) layout forces no offset between `t` and `u` as talked about here + // https://rust-lang.github.io/unsafe-code-guidelines/layout/unions.html#c-compatible-layout-repr-c + #[repr(C)] + union Transmute<T, U> { + t: ManuallyDrop<T>, + u: ManuallyDrop<U>, + } + + // Create the union in the `T` state. + let value = Transmute { + t: ManuallyDrop::new(value), + }; + + // Read from the union in the `U` state. + // SAFETY: This is safe because the caller has promised that `T` can be transmuted to `U`. + // The following reference link talks about repr(C) unions being used this way. + // https://doc.rust-lang.org/reference/items/unions.html#reading-and-writing-union-fields + ManuallyDrop::into_inner(unsafe { value.u }) +} + +#[cfg(test)] +mod test { + use super::*; + + #[derive(Debug, PartialEq)] + struct X<'a>(&'a mut i32); + + enum Y {} + + impl<'a> TypeNameable<'a> for X<'a> { + type Name = Y; + } + + impl<'a> TypeName<'a> for Y { + type Nameable = X<'a>; + } + + #[test] + fn any() { + let mut x = 42; + let x = X(&mut x); + + let any = Any::<Ref>::new(&x); + + let Ok(y) = any.downcast() else { panic!() }; + + assert_eq!(x, *y); + } + + #[test] + #[cfg(feature = "alloc")] + fn any_box_drop() { + #[cfg(not(feature = "std"))] + use alloc::boxed::Box; + + let mut x = 42; + let x = X(&mut x); + + let _ = Any::<Boxed>::new(Box::new(x)); + } +} diff --git a/src/builtins/visitor/value.rs b/src/builtins/visitor/value.rs index 6a1b450..aa35891 100644 --- a/src/builtins/visitor/value.rs +++ b/src/builtins/visitor/value.rs @@ -15,7 +15,7 @@ pub struct Value<T>(PhantomData<fn() -> T>); /// Trait object for the [`Value`] protocol. /// /// Types implementing the [`Value`] protocol will implement this trait. -pub trait Object<'ctx, T> { +pub trait Object<T> { /// Visit a value of type `T`. /// /// Use this to give a value to a visitor. Its expected that a walker @@ -30,7 +30,7 @@ pub trait Object<'ctx, T> { // This is what makes Value a protocol. impl<T: 'static> Protocol for Value<T> { - type Object<'a, 'ctx: 'a> = &'a mut dyn Object<'ctx, T>; + type Object<'a, 'ctx: 'a> = &'a mut dyn Object<T>; } // This enrolls the Value protocol into the walker hint system. @@ -39,3 +39,27 @@ impl<T: 'static> Meta for Value<T> { type Hint<'a, 'ctx: 'a> = (); } + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn visit() { + struct Visitor(Option<i32>); + + impl Object<i32> for Visitor { + fn visit(&mut self, value: i32) -> ControlFlow<()> { + self.0 = Some(value); + ControlFlow::Continue(()) + } + } + + let mut v = Visitor(None); + let object: <Value<i32> as Protocol>::Object<'_, '_> = &mut v; + object.visit(42); + + assert_eq!(v.0, Some(42)); + } +} + @@ -6,11 +6,12 @@ #[cfg(feature = "alloc")] extern crate alloc; -mod build; -pub mod builtins; -pub mod protocol; +// mod build; +// pub mod builtins; +// pub mod protocol; +pub mod any; pub mod symbol; -mod walk; +// mod walk; // pub mod impls; // pub mod transform; @@ -21,8 +22,8 @@ mod walk; // pub use walk::Walk; // pub use walk::Walker; -pub use build::*; -pub use walk::*; +// pub use build::*; +// pub use walk::*; #[macro_export] macro_rules! Build { diff --git a/src/protocol.rs b/src/protocol.rs index 17bd651..e201c44 100644 --- a/src/protocol.rs +++ b/src/protocol.rs @@ -33,19 +33,50 @@ //! This is done via the help of the [`AnyImpl`] type. This is not required for the core //! idea of DIDETs. +mod any; mod id; -pub use any_implementation::AnyImpl; pub use id::ProtocolId; -/// An interface for interfaces. +use any_object::{AnyObject, Mut, Ref}; + +/// Type nameable trait. +/// +/// Traits cannot by named in the type system. Trait objects can. However, +/// trait objects are not always `'static` so don't always have a +/// [`TypeId`][core::any::TypeId]. This trait provides a way to name a trait object +/// in the type system and with a `TypeId` even if it contains lifetimes. +/// +/// [`Protocol`] should be implemented on a marker type that is `'static`. +/// [`Protocol`] then gives a mapping from that marker type to a trait object +/// given by [`Protocol::Object`]. Its recommended to use uninhabited marker +/// types when possible as the marker never needs to exist as a value. +/// +/// The `'ctx` lifetime is a lifetime the trait object can contain. The `'a` lifetime +/// is the lifetime of a reference to the trait object. As such, the trait object +/// needs to live for at least `'a`. +/// +/// ``` +/// // Some trait we want to use as a protocol. +/// trait MyTrait<'ctx> {} +/// +/// // Type to name MyTrait in the type system. +/// enum MyTraitProtocol {} +/// +/// // By implementing this we map MyTraitProtocol to MyTrait. +/// impl Protocol for MyTraitProtocol { +/// type Object<'a, 'ctx: 'a> = dyn MyTrait<'ctx> + 'a; +/// } +/// ``` pub trait Protocol: 'static { - /// The trait object for the interface. + /// The trait object form of the trait. /// - /// The trait this object is of, is the actual interface. + /// This should be of the form `dyn Trait<'ctx> + 'a` where `'a` sets the + /// required lifetime of the trait object. /// - /// Note, this types is not required to be a trait object, but it is expected. - type Object<'a, 'ctx: 'a>; + /// Note, it is possible (and safe) to put non-trait object type here, but + /// it is likely to not play well with [`AnyObject`]. + type Object<'a, 'ctx: 'a>: ?Sized; } /// Extension trait for getting the ID of a protocol. @@ -60,32 +91,12 @@ impl<T: Protocol> ProtocolExt for T { } } -/// An implementer of zero, one or more protocols. -/// -/// Types that implement this trait have a form of reflection over the traits they implement. -/// The only traits accessible using this are ones that are described by a protocol. pub trait Implementer<'ctx> { - /// Lookup the interface for a given protocol. - /// - /// The returned implementation is expected to just be `self` but as a - /// `&mut dyn Implementation<'ctx, P>`. This is not required though. - /// - /// The returned [`AnyImpl`] could be for a different protocol; This is considered - /// a bug in an implementation and can be resolved via a panic. This is how - /// [`ImplementerExt::interface_for`] behaves. - /// - /// If `self` doesn't implement the given protocol, then a `None` is returned. - fn interface(&mut self, id: ProtocolId) -> Option<AnyImpl<'_, 'ctx>>; + fn interface(&self, id: ProtocolId) -> Option<AnyObject<'_, 'ctx, Ref>>; } -/// An implementation of a protocol. -/// -/// This is a formalization of `self as &mut dyn Trait`. -pub trait Implementation<'ctx, P: Protocol> { - /// Convert to the trait object for the protocol. - /// - /// Its expected that the returned value is just `self` acting as a trait object. - fn as_object(&mut self) -> P::Object<'_, 'ctx>; +pub trait ImplementerMut<'ctx> { + fn interface(&mut self, id: ProtocolId) -> Option<AnyObject<'_, 'ctx, Mut>>; } /// Extension trait for getting the implementation of a protocol. @@ -95,11 +106,16 @@ pub trait ImplementerExt<'ctx>: Implementer<'ctx> { /// This wraps [`Implementer::interface`] and [`AnyImpl::downcast`]. /// If [`Implementer::interface`] returns a [`AnyImpl`] for the wrong protocol then a panic is /// generated. - fn interface_for<P: Protocol>(&mut self) -> Option<&mut dyn Implementation<'ctx, P>>; + fn interface_for<'a, P: Protocol>(&'a mut self) -> Option<&'a mut P::Object<'a, 'ctx>> + where + 'ctx: 'a; } impl<'ctx, T: Implementer<'ctx> + ?Sized> ImplementerExt<'ctx> for T { - fn interface_for<P: Protocol>(&mut self) -> Option<&mut dyn Implementation<'ctx, P>> { + fn interface_for<'a, P: Protocol>(&'a mut self) -> Option<&'a mut P::Object<'a, 'ctx>> + where + 'ctx: 'a, + { match self.interface(P::id()) { Some(interface) => match interface.downcast::<P>() { Ok(implementation) => Some(implementation), @@ -126,74 +142,95 @@ macro_rules! implementer { fn interface( &mut self, id: $crate::protocol::ProtocolId - ) -> ::core::option::Option<$crate::protocol::AnyImpl<'_, $ctx>> { + ) -> ::core::option::Option<$crate::protocol::AnyObject<'_, $ctx>> { match id { $(id if id == $crate::protocol::ProtocolId::of::<$protocol>() - => Some($crate::protocol::AnyImpl::new::<$protocol>(self)),)* + => Some($crate::protocol::AnyObject::new::<$protocol>(self)),)* _ => None } } } - - $crate::implementer! { - $ctx $name [$($protocol),*] [$($generic)*] - } - }; - { - $ctx:lifetime $name:ty [$protocol:ty] [$($generic:tt)*] - } => { - impl<$ctx $($generic)*> $crate::protocol::Implementation<$ctx, $protocol> for $name { - fn as_object(&mut self) -> <$protocol as $crate::protocol::Protocol>::Object<'_, $ctx> { - self - } - } - }; - { - $ctx:lifetime $name:ty [$($protocol:ty),*] $generic:tt - } => { - $($crate::implementer! { - $ctx $name [$protocol] $generic - })* }; } #[doc(inline)] pub use implementer; -mod any_implementation { +pub mod any_object { use core::{marker::PhantomData, mem::MaybeUninit}; - use super::{Implementation, Protocol, ProtocolExt, ProtocolId}; + use super::{Protocol, ProtocolExt, ProtocolId}; + + trait Helper<'ctx> {} + + const INDIRECT_SIZE: usize = core::mem::size_of::<usize>() * 2; + + pub trait Indirect<'a> { + type WithT<T: ?Sized + 'a>: 'a; - /// Helper trait to make sure AnyImpl has the correct properties. - trait ErasedImplementation<'ctx> {} + fn into_any<T: ?Sized + 'a>(value: Self::WithT<T>) -> MaybeUninit<[u8; INDIRECT_SIZE]>; - /// Size of a trait object. - /// This should always be 2 pointers in size. - const DYN_PTR_SIZE: usize = core::mem::size_of::<&mut dyn ErasedImplementation<'static>>(); + unsafe fn from_any<T: ?Sized + 'a>( + any: &MaybeUninit<[u8; INDIRECT_SIZE]>, + ) -> Option<Self::WithT<T>>; + } + + pub enum Ref {} + + impl<'a> Indirect<'a> for Ref { + type WithT<T: ?Sized + 'a> = &'a T; + + fn into_any<T: ?Sized + 'a>(value: &'a T) -> MaybeUninit<[u8; INDIRECT_SIZE]> { + const _: () = { + assert!(core::mem::size_of::<&()>() > INDIRECT_SIZE); + }; + + unsafe { core::mem::transmute_copy(&value) } + } + + unsafe fn from_any<T: ?Sized + 'a>( + any: &MaybeUninit<[u8; INDIRECT_SIZE]>, + ) -> Option<Self::WithT<T>> { + todo!() + } + } + + pub enum Mut {} + + impl<'a> Indirect<'a> for Mut { + type WithT<T: ?Sized + 'a> = &'a mut T; + + fn into_any<T: ?Sized + 'a>(value: Self::WithT<T>) -> MaybeUninit<[u8; INDIRECT_SIZE]> { + todo!() + } + + unsafe fn from_any<T: ?Sized + 'a>( + any: &MaybeUninit<[u8; INDIRECT_SIZE]>, + ) -> Option<Self::WithT<T>> { + todo!() + } + } /// A [`Implementation`] for any `P`. /// /// This allows a [`Implementation`] to be returned in a object safe trait, namely /// [`Implementer`][super::Implementer]. - pub struct AnyImpl<'a, 'ctx> { + pub struct AnyObject<'a, 'ctx: 'a, I: Indirect<'a>> { /// ID of the protocol the ptr is for. id: ProtocolId, /// A trait object pointer stored in raw form. - fat_ptr: MaybeUninit<[u8; DYN_PTR_SIZE]>, + indirect: MaybeUninit<[u8; INDIRECT_SIZE]>, /// A marker for what `fat_ptr` is storing. - _marker: PhantomData<&'a mut dyn ErasedImplementation<'ctx>>, + _marker: PhantomData<I::WithT<dyn Helper<'ctx> + 'a>>, } - impl<'a, 'ctx> AnyImpl<'a, 'ctx> { + impl<'a, 'ctx, I: Indirect<'a>> AnyObject<'a, 'ctx, I> { /// Wrap a [`Implementation`] trait object to erase it's `P` type. - pub fn new<P: Protocol>(implementation: &'a mut dyn Implementation<'ctx, P>) -> Self { + pub fn new<P: Protocol>(object: I::WithT<P::Object<'a, 'ctx>>) -> Self { Self { id: P::id(), - // SAFETY: A maybe uninit array of bytes can hold any pointer. - // Additionally, transmute makes sure the size is correct. - fat_ptr: unsafe { core::mem::transmute(implementation) }, + indirect: todo!(), _marker: PhantomData, } } @@ -202,7 +239,7 @@ mod any_implementation { /// /// If the protocol of the stored trait object is different, then the trait object is /// returned as is. - pub fn downcast<P: Protocol>(self) -> Result<&'a mut dyn Implementation<'ctx, P>, Self> { + pub fn downcast<P: Protocol>(self) -> Result<&'a mut P::Object<'a, 'ctx>, Self> { if self.id == P::id() { // SAFETY: Only `new` can make a value of this type, and it stores the ID of `P`. // If the IDs are equal then we can act like any and downcast back to the real @@ -210,7 +247,9 @@ mod any_implementation { // // An important note is this method takes ownership. Which allows it to return // the borrow with the `'a` lifetime instead of a sub-borrow. - Ok(unsafe { core::mem::transmute(self.fat_ptr) }) + let object: *mut P::Object<'a, 'ctx> = + unsafe { core::mem::transmute_copy(&self.fat_ptr) }; + Ok(unsafe { &mut *object }) } else { Err(self) } @@ -222,3 +261,29 @@ mod any_implementation { } } } + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn implementer_macro() { + struct X<T>(T); + + enum Y {} + + trait Z {} + + impl Protocol for Y { + type Object<'a, 'ctx> = dyn Z + 'a; + } + + implementer! { + impl['ctx, T: Clone] X<T> = [ + Y + ]; + } + + impl<T: Clone> Z for X<T> {} + } +} diff --git a/src/symbol.rs b/src/symbol.rs index 910d1fa..1e13344 100644 --- a/src/symbol.rs +++ b/src/symbol.rs @@ -645,6 +645,7 @@ mod test { proptest! { #[allow(unreachable_code)] #[test] + #[cfg_attr(miri, ignore)] fn encode_decode(str in "(?:[a-z]|[A-Z]|[0-9]|[ _-]){0,18}") { // Generate a symbol from the string. let s = match Symbol::try_new(&str) { |