Mutagen – More opportunities

01 May 2018

Recently I gave a talk at our Rust Meetup about mutagen, and I also showed how our opportunistic mutations work (I however left out that gnarly thing about shifts, but in my defense I was short on time). That got me thinking whether we always do the right thing elsewhere.

The problem with running as a procedural macro is we only get to see the marked subsection of the code without any access to the surrounding context. This is somewhat problematic because paths (e.g. foo, Ok or Option::None::<u32>) are just stated without resolving them, and Rust code can shadow just about everything (e.g. by useing a different type, or by a let binding).

Some source of confusion

So what if someone creates their own enum with a Some variant and uses it? Even if we find a Some, we cannot reliably conclude that the type must be std::option::Option. Take the following examples:

if let Some(x) = wtf_per_mins() { .. }

while let Ok(_) = do_io() { .. }

We cannot be sure that wtf_per_mins() really returns an Option<_>, so how can we mutate this? By wrapping it in an opportunistic mutation function we might call mutagen::some. The method may be implemented like this:

#![feature(specialization)]

trait Somer<T> {
    fn some(self, mutation_count: usize) -> Self;
}

impl<T> Somer for T {
    default fn some(self, _count) -> Self { self }
}

impl<T> Somer for Option<T> {
    fn some(self, mutation_count: usize) -> Self {
        report_coverage(..);
        if now(mutation_count) { None } else { self }
    }
}

pub fn some<T>(t: T, mutation_count: usize) -> T {
    Somer::some(t)
}

The analogiq solution for Ok(_) and Err(_) turns out not to be quite so simple, because we need to differentiate the output type between Result<_, _> and others, but don’t have a valid value of the opposite variant, so if we want to mutate Ok(a) to Err(_) we have nothing to put into the Err(_), despite the value being thrown away by the if let. In other cases, I would use an associated Output type, but the type must simultaneously be Result<T, ()> or Result<(), E>, respectively and Self (where Self is the type of the mutated expression). Associated types cannot be specialized, because it was found this could be used to introduce unsoundness.

A solution to this conundrum may present itself in the future, either through one of my readers who is far more clever than me, or perhaps in the shower or over lunch. For today, let’s leave it at that.

Default

Similarly to optional values, we currently have a whitelist of types that must implement Default, but the matching is by necessity heuristic, as we don’t get the full path. If someone e.g. creates their own Option type that fails to implement Default, we’ll get an error. However, this can be fixed.

Similarly to our MayClone trait, we can add a MayDefault trait. However, there is one crucial difference: With MayClone we can get an actual self parameter because we have a value. But we don’t have the return value of the function. How then can we chose the right type?

Luckily I already know the solution from back in 2015 when I did some really evil Type-Level Shenanigans: PhantomData to the rescue! We just need to create our own type that takes a PhantomData of the function return type and implement our MayDefault trait for that type:

#![feature(specialization)]

use std::marker::PhantomData;

#[derive(Copy, Clone)]
pub struct MayDefaulter<X>(PhantomData<X>);

impl<X> MayDefaulter<X> {
    pub fn new() -> Self { MayDefaulter(PhantomData) }
}

pub trait MayDefault<X> {
    fn is_default(self) -> bool;
    fn get_default(self) -> X;
}

impl<X> MayDefault<X> for MayDefaulter<X> {
    default fn is_default(self) -> bool { false }
    default fn get_default(self) -> X { unimplemented!() }
}

impl<X: Default> MayDefault<X> for MayDefaulter<X> {
    fn is_default(self) -> bool { true }
    fn get_default(self) -> X { Default::default() }
}

Now we can use the following incantation to opportunistically return default: let m = MayDefaulter::new(); if m.is_default() { return m.get_default() } (The actual usage within our plugin will likely use fully qualified syntax as in MayDefault::is_default(m) because that lets us specify the full path).

Voilà – no more default type whitelist wrangling.

Update: Huon Wilson came up with a more elegant formulation of the default specialization:

pub trait MayDefault: Sized {
    fn get_default() -> Option<Self>;
}

impl<X> MayDefault for X {
    default fn get_default() -> Option<X> { None }
}

impl<X: Default> MayDefault for X {
    fn get_default() -> Option<X> { Some(Default::default()) }
}

Thanks!