A `Box<dyn>` analogue

Goal: call function on pointers of unknown types.

Can be solved with a vtable:

  1. Build translation function that take a pointer and forward to the correct function (below trampoline_*)
  2. Collect these functions in a struct of known layout (below VTable)

See also the standard docs on dyn. In our implementation the vtable is colocated with the object.

fn main() -> () {
    let our_dyns: Vec<BoxDyn> = vec![
        BoxDyn::new(Add40),
        BoxDyn::new(AddMultiple { multiplier: 3 }),
    ];
    
    let std_dyns: Vec<Box<dyn AddConstant>> = vec![
        Box::new(Add40),
        Box::new(AddMultiple { multiplier: 3 }),
    ];
    
    println!("our dyns");
    for (idx, obj) in our_dyns.iter().enumerate() {
        println!("[{idx}] {}", obj.add_constant(2));
    }
    println!();
    
    println!("std dyns");
    for (idx, obj) in std_dyns.iter().enumerate() {
        println!("[{idx}] {}", obj.add_constant(2));
    }
    println!();
}

/// the trait we want to use dynamically
trait AddConstant {
    fn add_constant(&self, value: i64) -> i64;
}

/// implementation 1: always add 40
///
/// Note: this is a zero sized type
struct Add40;

impl AddConstant for Add40 {
    fn add_constant(&self, value: i64) -> i64 {
        value + 40
    }
}

/// implementation 2: add a multiple of the input value
struct AddMultiple {
    multiplier: i64,
}

impl AddConstant for AddMultiple {
    fn add_constant(&self, value: i64) -> i64 {
        (self.multiplier + 1) * value
    }
}

/// the table of operations our object supports
type DropFn = fn(*mut u8);
type AddConstantFn = fn(*const u8, i64) -> i64;

struct VTable {
    drop: DropFn,
    add_constant: AddConstantFn,
}

/// bundle the object with the vtable
struct ConcreteDyn<T> {
    vtable: VTable,
    obj: T,
}

/// A pointer without any type information to the object with vtable
///
/// Since we know how to lookup the vtable, we can perform the operations on the
/// underlying object even without knowing its type. 
struct BoxDyn {
    obj_with_vtable: *mut u8,
}

/// the size of a pointer on the current platform
const PTR_SIZE: isize = std::mem::size_of::<usize>() as isize;

impl BoxDyn {
    fn new<T: AddConstant>(obj: T) -> Self {
        let vtable = VTable {
            add_constant: trampoline_add_constant::<T>,
            drop: trampoline_drop::<T>,
        };
        let obj_with_vtable = ConcreteDyn::<T> {
            vtable,
            obj,
        };
        
        // check the pointer differences, can this be done statically?
        {
            let ptr = as_u8_ptr(&obj_with_vtable);
            let ptr_drop = as_u8_ptr(&obj_with_vtable.vtable.drop);
            let ptr_add_constant = 
                as_u8_ptr(&obj_with_vtable.vtable.add_constant);
            
            unsafe {
                assert_eq!(ptr_drop.offset_from(ptr), 0 * PTR_SIZE);
                assert_eq!(ptr_add_constant.offset_from(ptr), 1 * PTR_SIZE);
            }
        }
        
        let obj_with_vtable = Box::new(obj_with_vtable);
        let obj_with_vtable = Box::into_raw(obj_with_vtable) as *mut u8;
        
        Self { obj_with_vtable }
    }
}

/// Implementation for Drop
impl std::ops::Drop for BoxDyn {
    fn drop(&mut self) {
        // NOTE: we asserted at construction that drop has the same ptr as the dyn 
        let drop_impl: *const DropFn = as_fun(self.obj_with_vtable);
        unsafe { (*drop_impl)(self.obj_with_vtable); }
    }
}

fn trampoline_drop<T>(ptr: *mut u8) {
    let ptr = ptr as *mut ConcreteDyn<T>;
    let obj_with_vtable = unsafe { Box::from_raw(ptr) };
    std::mem::drop(obj_with_vtable);
}

/// Implementation for AddConstant
impl AddConstant for BoxDyn {
    fn add_constant(&self, value: i64) -> i64 {
        unsafe {
            let add_constant_impl: *const AddConstantFn = 
                as_fun(self.obj_with_vtable.offset(PTR_SIZE));
            (*add_constant_impl)(self.obj_with_vtable, value) 
        }
    }
}

fn trampoline_add_constant<T: AddConstant>(ptr: *const u8, value: i64) -> i64 {
    let obj_with_vtable = unsafe { (ptr as *const ConcreteDyn<T>).as_ref() };
    obj_with_vtable.unwrap().obj.add_constant(value)
}

// helper functions
fn as_u8_ptr<T>(obj: &T) -> *const u8 {
    obj as *const T as *const u8
}

fn as_fun<F>(obj_with_vtable: *mut u8) -> *const F {
    obj_with_vtable as *const u8 as *const F
}