Autoderef specialization for public traits implemented by users

I posted here a little while ago... checks calendar, oh a long time ago...

About a difficulty I had specializing default trait methods, and the rather convoluted system of traits I was using in advent_of_code_traits.

Today I published version 0.2.0 with more or less a complete rewrite of the traits because I found a solution using autoderef specialization, blanket implements and marker traits to avoid overlapping impls.

Sound fun? Let's dive in!

To recap, the gist of my problem was:

  • I want downstream users to implement a trait in my crate for their type
  • I want to provide a method impl that uses their impl of the trait
  • I wanted to specialize on that method, if certain types were equal
  • Oh and it was actually 2 traits... well 3 technically!

More specifically the user would do something like this:

impl ParseInput<Day1> for AdventOfCode2020 {
    type Parsed = Vec<u32>;

    fn parse_input(input: &str) -> Self::Parsed {
        vec![1, 2, 3]
    }
}

impl Solution<Day1> for AdventOfCode2020 {
    type Part1Output = usize;
    type Part2Output = String;

    fn part1(input: &Vec<u32>) -> Self::Part1Output {
        input.len()
    }

    fn part2(input: &Vec<u32>) -> Self::Part2Output {
        format!({:?}, input) // yeah the solution isn't the focus here :P
    }

    // fn run(...) - this has a default implementation
}

let input = read_input_from_file();

// PROBLEM: This parses the input twice :(
// Both parts want to share the same input! (a Vec<u32>)
AdventOfCode2020::run(&input);

I managed to use autoderef specialization to overcome this, buckle up here come the changes

  • Solution no longer has the run method
  • A new trait: SolutionRunner - this has the run method now - with no default implementation!
  • I provide a blanket impl of SolutionRunner<DAY> for T: Solution<DAY, Part1> + ParseInput<DAY, Part1> + MissingPartTwo
  • That MissingPartTwo is a marker trait for the user to impl when they haven't got an impl for Part2
    yet (I'd like to avoid this, but couldn't do it - it's needed to avoid overlapping impls, more on that later)
  • I provide another blanket impl of SolutionRunner<DAY>, this time for &T where...
    // solution for both parts
&T: Solution<'a, DAY, 1> + Solution<'a, DAY, 2>

    // parsing for both parts
  + ParseInput<'a, DAY, 1> + ParseInput<'a, DAY, 2>

    // the input types match their (respective) parsed types
  + Solution<'a, DAY, 1, Input = <Self as ParseInput<'a, DAY, 1>>::Parsed>
  + Solution<'a, DAY, 2, Input = <Self as ParseInput<'a, DAY, 2>>::Parsed>,

This lets you run both part 1 and part 2. But we're not done yet.

  • I provide another blanket impl of SolutionRunner<DAY>, this time for &&T where...
     // solution for both parts
&&T: Solution<'a, DAY, 1> + Solution<'a, DAY, 2>

     // parsing for part1 only
   + ParseInput<'a, DAY, 1>

     // the input types both match the one parsed type
   + Solution<'a, DAY, 1, Input = <Self as ParseInput<'a, DAY, 1>>::Parsed>
   + Solution<'a, DAY, 2, Input = <Self as ParseInput<'a, DAY, 1>>::Parsed>,

This lets you run both part 1 and part 2 having only provided an impl to parse part 1. In this impl I can pass the same parsed input into both parts because the compiler knows the types match! :smiley:

That last impl looks like this in full:

// autoderef specialization
impl<'a, T: 'a, const DAY: u32> SolutionRunner<'a, DAY, SHARED_INPUT_FULL> for &'a &'a T
where
    &'a &'a T: Solution<'a, DAY, 1>
        + Solution<'a, DAY, 2>
        + ParseInput<'a, DAY, 1>
        + Solution<'a, DAY, 1, Input = <Self as ParseInput<'a, DAY, 1>>::Parsed>
        + Solution<'a, DAY, 2, Input = <Self as ParseInput<'a, DAY, 1>>::Parsed>,
{
    fn run(&'a self, input: &'a str) {
        let parsed_input = <Self as ParseInput<'a, DAY, 1>>::parse_input(&self, &input);
        let part1_output = <Self as Solution<'a, DAY, 1>>::solve(&self, &parsed_input);
        // sharing the parsed_input, yay! :)
        let part2_output = <Self as Solution<'a, DAY, 2>>::solve(&self, &parsed_input);
        println!("Day {DAY}\npart 1: {part1_output:?}\npart 2: {part2_output:?}");
    }
}

Are we done yet? Well, nearly. At this stage the user ought to be able to run the following:

impl<'a> ParseInput<'a, Day2, Part1> for AdventOfCode2021<Day2> {
    type Parsed = Vec<u32>;
    // ... parse part1 only
}

impl<'a> Solution<'a, Day2, Part1> for AdventOfCode2021<Day2> {
    type Input = Vec<u32>;
    // ... solve part1
}

impl<'a> Solution<'a, Day2, Part2> for AdventOfCode2021<Day2> {
    type Input = Vec<u32>;
    // ... solve part2
}

let input = read_input_from_file();
let problem = AdventOfCode2021::<Day2>;
// 3 & references because we have 3 levels of specialization*
(&&&problem).run(&input);

note the <Day2>, AdventOfCode2021<Day2> will only impl traits for Day2 - this means we don't need to disambiguate which Day's solution to run - if we did have to disambiguate, it would get messy!

* It's actually not quite that simple, this article explains it well - I referred to this a lot.

BUT you might be surprised to run into a compiler error!

the method `run` exists for reference `&&&AdventOfCode2021<2_u32>`, but its trait bounds were not satisfied
the following trait bounds were not satisfied:
`AdventOfCode2021<2_u32>: MissingPartTwo<2_u32>`
which is required by `AdventOfCode2021<2_u32>: SolutionRunner<2_u32, 1_u16>`rustcE0599

Hang on, why do we need to impl MissingPartTwo? We have Solution impl for Part2. And what's that 1_u16?

Well, this is the tricky part. We only have one trait, SolutionRunner, and we are specializing different impls of it. That's not actually possible. See, what we've done is made SolutionRunner generic over another parameter (the u16), 1_u16 is mapped to the "PART_ONE_ONLY" specialization.

The generic parameter makes this one trait look like many to the compiler. In the full impl above

impl<'a, T: 'a, const DAY: u32> SolutionRunner<'a, DAY, SHARED_INPUT_FULL> for &'a &'a T

the constant SHARED_INPUT_FULL=3 is used like a name for that specialization level.

The reason the compiler is asking us to impl MissingPartTwo is because it can only see the PART_ONE_ONLY blanket impl... because it is impl on T with no references.

We had to require &T implement Solution and ParseInput but as a user, I didn't impl Solution and ParseInput on &T. I refuse to force users to impl Solution on &&T, &T or T based on which specialization they want to use.

My solution is to provide a blanket impl Solution for &T where T: Solution. This means that the user provides one impl and gets all the additional impls for &T, &&T, &&&...T for free.

Adding that clears the error and specialization can now occur, hooray!

One important caveat though, since we impl for T and all the &Ts "up the chain" is that any overlap causes the compiler to complain about ambiguity:

consider specifying the const argument: `SolutionRunner::<DAY>`rustcE0283
main.rs(11, 40): original diagnostic
type annotations needed
multiple `impl`s satisfying `&&AdventOfCode2021<2_u32>: SolutionRunner<'_, {_: u32}, {_: u16}>` found in the `year2021_day01` crate:
- impl<'a, T, DAY> SolutionRunner<'a, DAY, {_: u16}> for &'a &'a T
  where <&'a &'a T as Solution<'a, DAY, 1_u8>>::Input == <&'a &'a T as ParseInput<'a, DAY, 1_u8>>::Parsed, <&'a &'a T as Solution<'a, DAY, 2_u8>>::Input == <&'a &'a T as ParseInput<'a, DAY, 1_u8>>::Parsed, &'a &'a T: Solution<'a, DAY, 1_u8>, &'a &'a T: Solution<'a, DAY, 2_u8>, &'a &'a T: ParseInput<'a, DAY, 1_u8>, &'a &'a T: Solution<'a, DAY, 1_u8>, &'a &'a T: Solution<'a, DAY, 2_u8>, T: 'a;
- impl<'a, T, DAY> SolutionRunner<'a, DAY, {_: u16}> for T
  where <T as Solution<'a, DAY, 1_u8>>::Input == <T as ParseInput<'a, DAY, 1_u8>>::Parsed, T: Solution<'a, DAY, 1_u8>, T: ParseInput<'a, DAY, 1_u8>, T: Solution<'a, DAY, 1_u8>;rustcE0283
main.rs(11, 40): consider specifying the const argument: `SolutionRunner::<DAY>`

and that's why I have the MissingPartTwo marker trait and the bound on the PART_ONE_ONLY specialised impl. It means that no specialization level overlaps (not normally something to worry about with autoderef specialization).

If you want to check it out, please do. The source code should be fairly readable, I tried to document it well. And please do ask me any questions :slight_smile:

This isn't the end game for these traits. I want to support error handling (currently the signatures mean you're only option is to panic) and I'd like to make the reporting part of the run method configurable by end users - probably another trait, this time with a default method that can be overwritten.

Time will tell whether this is a useful pattern in general, I wouldn't call it production ready at all yet, please be cautious if you're considering using this technique in your own crate :stuck_out_tongue:

1 Like