Illegal tricks with generics

This contains notes, examples and points (we could consider it an article version?) of a draft of a short talk on Rust, suitable for meetups and conferences. This particular talk is inspired by the first workshop, Tooling in Rust

Intro

You are entering the realm which is unusual. Maybe it's magic or contains some kind of monster. The second one. Prepare to enter... The Scary Door.

Working with generics in Rust is great. While the trait model may be a little unfamiliar to newcomers, it usually grows onto developers. With traits, we can model interesting type relations and create effective code while also reducing duplication.

However, it can be better.

Let's examine a couple neat tricks regarding both static dispatch and dynamic dispatch.

Detour - refreshing the two types of generics in Rust

In case you didn't encounter these terms before, static dispatch is generics done via type parameters on methods, traits and others types, and their respective trait bounds, for example:

#![allow(unused)]
fn main() {
trait Hello {}

fn hello<T: Hello>(_: T) {}
}

We call these generics static dispatch because they are resolved at compile-time. The compiler uses a technique called monomorphization, meaning it generates a copy of methods and types for each used combination of type params.

This is great for two reasons:

• You can do more with trait methods when used in static dispatch (ie. call methods that don't take the self parameter, or refer to Self, or require Self: Sized)
• It has better performance because we don't need to go through a vtable, and because static dispatch is a gateway to more optimizations such as inlining

However, the downside is that you can't put together multiple types satisfying the same trait, and static dispatch increases the size of your binary more than dynamic dispatch does

On the other hand, dynamic dispatch uses trait objects, and looks like this:

#![allow(unused)]
fn main() {
trait Hello {}

fn hello(_: &dyn Hello) {}
}

In older examples of Rust, you might have seen this without the dyn keyword. Dynamic dispatch will instead of a concrete type perform type erasure and transform your instance of a concrete type into a so-called trait object.

With trait objects, the caller does not care or need to care about the concrete type. The benefit is that you can, for example, put multiple trait objects created from different types into a collection. You can also put together your own types that contain trait objects in their fields even if they come from different types.

Conversely from the static dispatch case, your binary will be smaller at the cost of some performance.

Choosing the correct type of generics for your use case is a fine art. My rule of thumb is to prefer static dispatch if it works in the given use case and if you can handle the bureaucracy of passing around type parameters.

A couple points to close off this section:

• impl Trait in function return type position is not generics
• You can add impl blocks for trait objects too:

#![allow(unused)]
fn main() {
trait Hello {}

// this function is not part of the trait Hello,
// but instead a method of the trait object itself
impl dyn Hello {
    fn hey(&self) -> {
        println!("Hey");
    }
}
}

Static dispatch trick 1: Two ways of tricking Rust into doing some sort of specialization

One of the most common things we older Rust devs like to complain about is the lack of specialization in stable Rust.

Specialization is the ability to have two overlapping trait implementations, with the compiler choosing the more specific (ie. specialized one).

Consider the following example that does not compile on stable Rust:

#![allow(unused)]
fn main() {
trait Hello {}

// least specialized implementation
impl<T> Hello for T {}

// blanket implementation over options, more specialized
impl<T> Hello for Option<T> {}

// implementation specialized to a concrete type
impl Hello for bool {}
}

TIP: You might notice the standard library has actually been using specialization for quite some time.

There exist two features for specialization, #![feature(specialization, min_specialization)], none of which have been stabilized yet, and it will probably take a long time before they will be. Despite appearances, it is difficult to get specialization right.

While we cannot replicate all three levels, there is two hacks we can use to at least get the "completely" general vs concrete variant.

1) Using autoref

Let's start with the less cursed one. You may have noticed that there are cases where Rust will automatically de-reference or reference your types. While it will not do &T -> T, it is more than fond of doing things like T -> &T or &&T -> T. We can use this to do something which feels like specialization if you squint your eyes hard enough, but actually isn't.

Consider the following example:

#![allow(unused)]
fn main() {
trait Hello {}

struct MyStruct;

impl<T> Hello for &T {}

impl Hello for MyStruct {}
}

This compiles without a hitch because these two impl blocks actually do not overlap. However, if there was a method taking &self, you could just call anything.the_method_that_takes_borrow_self(), and it would just work. You'd have to keep in mind though, that in case of the former, &self would be &&T, whereas for the latter, it would be &T.

Since the compiler will automatically reference variables on method calls, this will work just fine.

However, what if that is not an option?

2) Using a hell curse

What if I told you there is a way to downcast a generic type param into a concrete type without going through dynamic dispatch with Any?

Consider the following:

#![allow(unused)]
fn main() {
use std::any::TypeId;

fn as_type<T: 'static, U: 'static>(x: &T) -> Option<&U> {
    if TypeId::of::<T>() == TypeId::of::<U>() {
        // I am going to do what's called a pro-gamer move
        unsafe { Some(&*(x as *const T as *const U)) }
    } else {
        None
    }
}
}

This code uses a line of unsafe, but it is actually safe.

All Rust types have a unique, opaque TypeId. Usually, TypeId is great to establish the equality of types, but not much more. It is also used in Any to make sure the type you are downcasting to is in fact the correct type. However, the downcasting functions of Any are implemented on dyn Any, so we would definitely need to go through dynamic dispatch, which costs performance and isn't compile-time, and it would also get annoying to have to specify Any as supertrait and provide conversion methods to get the Any trait object we could then downcast. No bueno.

This can be considered safe because of a couple things:

• It is enclosed in a function that requires the generic params to be 'static. This ensures we don't retype references and thus create unsound code (retyping static reference to another static reference is fine, you could still use this to do, eg. &'static T -> &'static str).
• In the if, we establish the equality of the type, so we know the cast we are doing is correct
• We can trust TypeId because due to the blanket implementation and having no specialization, we can be reasonably sure TypeId is correct (of course, one might replace the standard library completely with nightly features like no_core, but that is wild west territory where nothing is safe. This is good enough on)

Now, how can we better fake specialization with it? By making a nice macro out of it and using it in, for example, the default implementation of a trait:

#![allow(unused)]
fn main() {
macro_rules! specialize {
    {
        self: $self:ident,
        $($x:pat if $spec_type:ty => $spec_impl:block),*
        default: $def_impl:block
    } => {
        #[inline]
        fn __as_type<T: 'static, U: 'static>(x: &T) -> Option<&U> {
            if TypeId::of::<T>() == TypeId::of::<U>() {
                // I am going to do what's called a pro-gamer move
                unsafe { Some(&*(x as *const T as *const U)) }
            } else {
                None
            }
        }

        if let Some(()) = None { unreachable!(":)") }
        $(else if let Some($x) = __as_type::<_, $spec_type>($self) $spec_impl)*
        else $def_impl
    }
}
}

We need to do a little life hack with an always false if-let (so that we can repeat else if let), but this is completely fine, the compiler knows this will never be true and just deletes it from the final binary.

Using this macro allows us to create a sort of a match for matching on concrete types:

#![allow(unused)]
fn main() {
trait MyTrait: 'static + Sized {
    fn do_a_thing(&self) -> Option<String> {
        specialize! {
            self: self,
            type1 if Type1 => {
                dbg!(type1);
                Some("Hello".into())
            },
            type2 if Type2 => {
                dbg!(type2);
                Some("World".into())
            }
            default: {
                None
            }
        }
    }
}

impl<T> MyTrait for T where T: 'static {}
}

You could use this macro in different places too, and it allows destructuring (as you can type a pattern instead of type1 or type2 as identifiers).

Debugging with evil specialization

We could write another macro:

#![allow(unused)]
fn main() {
macro_rules! if_type {
    ($x:pat, $spec_type:ty) => {
        #[inline]
        fn __as_type<T: 'static, U: 'static>(x: &T) -> Option<&U> {
            if TypeId::of::<T>() == TypeId::of::<U>() {
                // I am going to do what's called a pro-gamer move
                unsafe { Some(&*(x as *const T as *const U)) }
            } else {
                None
            }
        }

        __as_type::<_, $spec_type>($x)
    }
}
}

And use it for hacky debugging by putting it in generic functions:

#![allow(unused)]
fn main() {
fn hello<T>(t: T) {
    if let Some(yea) = if_type!(t, bool) {
        println!("it's a bool here");
    }
}
}

It can be useful for other things, too.

Pulling apart trait objects

In the detour, we mentioned that trait objects are sort of obscure. What if they weren't?

Let's start by considering the following example:

pub trait What {
    fn what(&self);
}

impl What for i32 {
    fn what(&self) {
        println!("{}", self);
    }
}
impl What for u32 {
    fn what(&self) {
        println!("{}", self);
    }
}

fn whatman(w: &dyn What) {
	w.what()
}

fn main() {
    whatman(&1i32);
    whatman(&1u32);
}

Now imagine that whatman() is a piece of complex machinery, many lines of code and it breaks randomly, and you need to find out which type is causing it without wasting a lot of time writing debugging statements into the code.

Well, to our rescue comes the debugger.

While it should be also possible to do this with lldb, I will be showing this with gdb.

First, compile the project with cargo build. This will produce an un-optimized build with debugging symbols.

Trait objects

Remember (or learn) that trait objects are fat pointers. The actual pointer is composed of two pointers, a pointer to the instance of the type, and a vtable, also known as virtual function table. This table contains pointers to methods, to which the first pointer will be passed, along with whatever arguments the user needs to pass to the method.

The situation with trait objects in debuggers isn't ideal:

• while some DWARF is generated, not all, and neither vtables nor the object pointers are directly identified
• neither GDB nor LLDB can call trait methods

However, we can still work this.

Let's start by priming GDB with our binary:

rust-gdb target/debug/what

TIP: remember to use the rust- wrappers for the debuggers

Now, we can for example add a breakpoint to whatman():

#![allow(unused)]
fn main() {
(gdb) break whatman
Breakpoint 1 at 0x55555555be0e: file src/main.rs, line 17.
}

And let's run it until you encounter the breakpoint:

#![allow(unused)]
fn main() {
(gdb) run
}

GDB should break execution in whatman() and we can inspect the environment there.

We can look at w:

#![allow(unused)]
fn main() {
(gdb) print w
$2 = &dyn what::What {pointer: 0x55555559105c, vtable: 0x5555555a0210}
}

Let's see what the types are according to GDB:

#![allow(unused)]
fn main() {
(gdb) ptype w
type = struct &dyn what::What {
  pointer: *mut dyn what::What,
  vtable: *mut [usize; 3],
}
}

Of course, this is no good. The vtable is definitely not just three usizes. It in fact contains pointers, and it can contain many of them.

You can use either explore or print to print them:

#![allow(unused)]
fn main() {
(gdb) p *w.vtable
$7 = [93824992264080, 4, 4]
}

We don't care much for the 4s, but we can look into the first address, with either x or info symbol:

#![allow(unused)]
fn main() {
(gdb) x (*w.vtable)[0]
0x55555555bf90 <_ZN4core3ptr24drop_in_place$LT$i32$GT$17h64e2a488662dcab3E>:	0x3c894850
}

We can read that i32 in there, but it would be better to have the name de-mangled:

#![allow(unused)]
fn main() {
(gdb) info symbol (*w.vtable)[0]
core::ptr::drop_in_place<i32> in section .text of /root/what/target/debug/what
}

Now that looks better. We can also look at the exact what() implementation starting on the 4th element of the array:

#![allow(unused)]
fn main() {
(gdb) info symbol (*w.vtable)[3]
<i32 as what::What>::what in section .text of /root/what/target/debug/what
}

Should be clear enough from this, haha.

You can try this with the enclosed repository.