A Shifty Riddle

11 April 2018

When I finally implemented opportunistic mutations in mutagen, everything seemed fine until my co-maintainer gnieto found a problem. Code failed to compile with the mutagen plugin, something that should never happen as long as the code in question compiles without the plugin. We not only broke the code – we broke the build.

I was stumped. We did nothing obviously wrong (which, alas, is not the same as obviously doing nothing wrong), and the error was less than helpful.

At least I managed to reduce his failing example to the following: ::std::ops::Shl::shl(1u32, 2) * 3, which fails with a type error because it tries to multiply u32 and i32. This code is just an expansion of (1u32 << 2) * 3 which compiles flawlessly. At this point I had at least ruled out specialization and our op traits as possible root of our troubles.

Perhaps changing our opportunistic mutation implementation to implement the original traits for some newtype that wraps the left-hand-side expression and the mutation count could solve it?

use std::ops::*;

struct MutOp<T>(T);

impl<T, Rhs> Shl<Rhs> for MutOp<T> where T: Shl<Rhs> {
    type Output = <T as Shl<Rhs>>::Output;
    fn shl(self, r: Rhs) -> Self::Output {
        self.0 << r
    }
}

fn main() { (MutOp(1u32) << 2) * 3; }

No, that fails with the same error. Worst of all, I did not know the actual cause. In my frustration, I asked StackOverflow. I got some positive votes, but no answer. Time to dig in the Rust source code:

librustc_typeck/check/op.rs has some special handling for binary operations including && and || (which require their arguments to be bools and always return bool, but also << and >>. The comments note that there are many implementations for various right-hand-side types. For integer types, the special case kicks in, and the result type is set to the type of the left-hand expression.

This handling obviously doesn’t apply to method calls, so there we have the difference between 1u32 << 2 and 1u32.shl(2). It also only appears to apply to integer types, which rules out our wrapper. So how do we fix this?

I found the solution while eating lunch. The reason our compilation fails is that typeck cannot look through the impls to see that the result type of the shift equals the left-hand-side argument’s type. Therefore, when looking for the type of the right-hand-side of the multiplication, it applies the i32 default for integers without specific type information. Later when it has found the Shl impl, it sets the type of the left-hand-side argument to u32, which leads to the error. So we need to fix the type of the shift without knowing it or needlessly executing it.

One way to unify the types of two expressions in code is to use an if:

(if false { 1u32 << 2 } else { ::mutagen::ShlShr::shl(1u32, 2, 42) }) * 3

This works, and perhaps surprisingly doesn’t trigger the dead-code lint, even when not issued by a macro (I’m going to add a macro check should this ever change). Note that we only need a copy of the original expression and of the operands to make this work, so we neither need to know the types nor execute the original expression.

When I implemented this, I also ran against a problem where quote_expr! would mis-insert $ sub-expressions if they were used more than once. I fixed this by creating local bindings. Now shifts are mutated as they should be and we can go on mutating other stuff.

Moral of the story: Shifts happen.