Type erasure for consuming trait

help
#1

I have a transaction system based on revertable operations. Each operation, in addition to its primary function, produces an UndoLog that knows how to back out the change that was made:

trait UndoLog<T> {
    fn revert(self, _:&mut T);
}

Semantically, this should be a consuming function: Once an operation has been reverted, attempting to revert it again is an error. I have also defined several combinators that can compose UndoLogs:

  • () is a no-op log
  • (A,B) reverts A and then B
  • Vec<T> reverts each T in reverse order
  • Option<T> and Either<A,B> revert whichever variant is present

The transaction object holds an exclusive reference to the object being modified and uses these combinators to maintain an overall undo log. Because the type of the undo log changes with every operation, the type of the transaction object itself also changes with every operation.

In most cases this is fine, but sometimes it would be useful to have a unified type for the UndoLogs (and therefore the transactions that hold them). For example, it’s not feasible in my current setup to have a vector of transactions and apply an operation to just one of them.

To make this possible, I’d like to add a type-erasing combinator to the list above. It will obviously need to Box the UndoLog or otherwise store it on the heap. I can’t use Box<dyn UndoLog<T>>, though, because UndoLog isn’t object safe. I don’t want to change the function signature to self: Box<Self> because that would force lots of unnecessary heap allocations.

There is some precedent for this: FnOnce manages to be callable via a Box despite taking an owned self parameter, but I suspect it has special compiler support.

#2

I think I’ve got this figured out; maybe the same approach will be useful to others in the future:


trait UndoLog<T>: Sized {
    fn revert(self, _:&mut T);
    fn into_box(self)->ErasedLog<T> where Self:Any {
        ErasedLog {
            log: Box::new(self),
            revert_fn: unbox_and_revert::<T,Self>
        }
    }
}

fn unbox_and_revert<T, U: Any + UndoLog<T>>(box_any: Box<dyn Any>, obj:&mut T) {
    let box_u: Box<U> = box_any.downcast().unwrap();
    box_u.revert(obj);
}

pub struct ErasedLog<T> {
    log: Box<dyn Any>,
    revert_fn: fn(Box<dyn Any>, &mut T),
}

impl<T> UndoLog<T> for ErasedLog<T> {
    fn revert(self, obj: &mut T) {
        (self.revert_fn)(self.log, obj);
    }
    fn into_box(self)->Self { self }
}

(Playground)

1 Like
#3

Maybe something like

#![feature(specialization)]

trait UndoLog<T: ?Sized> {
    fn revert(self, x: &mut T)
    where
        Self: Sized;
    fn revert_boxed(self: Box<Self>, x: &mut T);
}
default impl<S, T: ?Sized> UndoLog<T> for S {
    fn revert_boxed(self: Box<Self>, x: &mut T) {
        (*self).revert(x)
    }
}
impl<T: ?Sized> UndoLog<T> for Box<dyn UndoLog<T>> {
    fn revert(self, x: &mut T) {
        self.revert_boxed(x)
    }
}

or—avoiding nightly features—something like

trait UndoLogImpl<T: ?Sized> {
    fn revert(this: Self, x: &mut T);
}
impl<S, T: ?Sized> UndoLog<T> for S
where S: UndoLogImpl<T> {
    fn revert(self, x: &mut T) {
        <Self as UndoLogImpl<T>>::revert(self, x)
    }
    fn revert_boxed(self: Box<Self>, x: &mut T) {
        (*self).revert(x)
    }
}

trait UndoLog<T: ?Sized> {
    fn revert(self, x: &mut T)
    where
        Self: Sized;
    fn revert_boxed(self: Box<Self>, x: &mut T);
}
impl<T: ?Sized> UndoLogImpl<T> for Box<dyn UndoLog<T>> {
    fn revert(this: Self, x: &mut T) {
        this.revert_boxed(x)
    }
}

can work for you, too. (The UndoLogImpl trait would be just to simplify trait implementation, since you don’t have to provide a separate revert_boxed implementation this way. Unfortunately there is no other way to provide a default implementation without specialization AFAICT.)

1 Like
#4

Hmm, or perhaps this is more clean:

trait UndoLog<T: ?Sized> {
    fn revert(self, x: &mut T)
    where
        Self: Sized;
}
trait UndoLogBoxed<T: ?Sized>: UndoLog<T> {
    fn revert_boxed(self: Box<Self>, x: &mut T);
}

impl<S, T: ?Sized> UndoLogBoxed<T> for S
where
    S: UndoLog<T>,
{
    fn revert_boxed(self: Box<Self>, x: &mut T) {
        (*self).revert(x)
    }
}

type ErasedLog<T> = Box<dyn UndoLogBoxed<T>>;

impl<T: ?Sized> UndoLog<T> for ErasedLog<T> {
    fn revert(self, x: &mut T) {
        self.revert_boxed(x)
    }
}

EDIT... to give a more generic Box<S> implementation:

trait UndoLog<T: ?Sized> {
    fn revert(self, x: &mut T)
    where
        Self: Sized;
}
trait UndoLogBoxed<T: ?Sized>: UndoLog<T> {
    fn revert_boxed(self: Box<Self>, x: &mut T);
}

impl<S, T: ?Sized> UndoLogBoxed<T> for S
where
    S: UndoLog<T>,
{
    fn revert_boxed(self: Box<Self>, x: &mut T) {
        (*self).revert(x)
    }
}

impl<S: ?Sized, T: ?Sized> UndoLog<T> for Box<S>
where
    S: UndoLogBoxed<T>,
{
    fn revert(self, x: &mut T) {
        self.revert_boxed(x)
    }
}

type ErasedLog<T> = Box<dyn UndoLogBoxed<T>>;
4 Likes
#5

If you are on nightly, you can just use unsized_fn_params (which is the "lite" version of unsized_locals):

#![feature(unsized_fn_params)]

trait UndoLog<T: ?Sized> {
    fn revert(self, x: &mut T);
}

impl<S: ?Sized, T: ?Sized> UndoLog<T> for Box<S>
where
    S: UndoLog<T>,
{
    fn revert(self, x: &mut T) {
        (*self).revert(x)
    }
}
2 Likes
#6

I personally like to invert the trait hierarchy so that only one trait needs to be in scope:

trait UndoLog<T> : RevertBoxed<T> {
    fn revert(self, _: &'_ mut T)
    where
        Self : Sized,
    ;
}

trait RevertBoxed<T> {
    fn revert_boxed (self: Box<Self>, _: &'_ mut T)
    ;
}

impl<T, Self_ : UndoLog<T>> RevertBoxed<T> for Self_ {
    fn revert_boxed (self: Box<Self>, it: &'_ mut T)
    {
        (*self).revert(it)
    }
}
  • With the optional ergonomic impl for Box 
    //                         this could indeed be a generic 
//                        `impl ?Sized + UndoLog<T>` param
//                              vvvvvvvvvvvvvvvvvvvv
impl<'__, T> UndoLog<T> for Box<dyn '__ + UndoLog<T>> {
    fn revert (self: Box<dyn '__ + UndoLog<T>>, it: &'_ mut T)
    {
        self.revert_boxed(it)
    }
}

  • Playground

3 Likes
#7

I’m pleasantly surprised that doesn’t throw the trait solver into an infinite loop. I never would have thought of writing a blanket impl for the supertrait conditioned on the subtrait.

2 Likes