"Overflow evaluating the requirement" but that kind of recursion should not happen at all

Question

Here is a kind of lengthy example because I was not able to reduce it further. Rust Playground

use std::marker::PhantomData;
use std::ops::{Add, Sub, Mul, Div};

pub trait Scalar
    : Sized + Copy + Add<Self, Output = Self> + Sub<Self, Output = Self> + Mul<Self, Output = Self> + Div<Self, Output = Self>
    {}
impl Scalar for u32 {}

pub struct ScalarVal<T>(T) where T: Scalar;

pub trait Pixel: Sized {
    type ScalarType: Scalar;
}

#[derive(Debug, Copy, Clone, PartialEq)]
pub struct Gray<BaseTypeP>
    where BaseTypeP: Scalar
{
    intensity: BaseTypeP,
}

impl<BaseTypeP> Pixel for Gray<BaseTypeP>
    where BaseTypeP: Scalar
{
    type ScalarType = BaseTypeP;
}

impl<BaseTypeP> Add<Gray<BaseTypeP>> for ScalarVal<BaseTypeP>
    where BaseTypeP: Scalar
{
    type Output = Gray<BaseTypeP>;
    fn add(self, rhs: Gray<BaseTypeP>) -> Gray<BaseTypeP> {
        unimplemented!()
    }
}

pub struct Image<PixelP>
    where PixelP: Pixel
{
    _marker: PhantomData<PixelP>,
}

impl<PixelP> Add<Image<PixelP>> for ScalarVal<<PixelP as Pixel>::ScalarType>
    where PixelP: Pixel,
          ScalarVal<<PixelP as Pixel>::ScalarType>: Add<PixelP, Output = PixelP>
{
    type Output = Image<PixelP>;
    fn add(self, rhs: Image<PixelP>) -> Image<PixelP> {
        unimplemented!()
    }
}

fn main() {
    let a = Gray::<u32> { intensity: 41 };
    let b = ScalarVal(1) + a;
}

Can someone explain why I am getting overflow evaluating the requirement <_ as Pixel>::ScalarType in that code snippet?

I am confused because:

• If the Add implementation in line 44 is removed the code compiles fine. But that implementation should not be used at all => main() only uses Gray and not Image
• The recursion seems to be in nested Image<Image<...>> structs but that should not happen at all?!
• If line 46 is changed to ScalarVal<<PixelP as Pixel>::ScalarType>: Add it compiles fine - But why?

Some context

This is part of an image processing library I want to build. The idea is to have different pixel formats (Gray, RGB, Bayer, ...) which can be used for images. Therefore you have Image<Gray> for a grayscale image. Different Pixel implementations can implement different operators, so you can do calculations (e.g. gray_a = gray_b + gray_c) with them. It is also possible to use scalar values in those implementations to do e.g. gray_a = gray_b + ScalarVal(42). Because I want to make it possible to have ScalarVal as right- and left-hand-argument there need to be two implementations (impl Add<Gray<...>> for ScalarVal<...> and impl Add<ScalarVal<...>> for Gray<...>).

Ok and now the Image type should implement all operators which are supported by the used Pixel type. If it is possible to do gray_pixel + Scalar(42) it should also be possible to do gray_image + Scalar(42).

Hope this kind of makes sense.

Answer 1

ScalarVal(1) + a resolves basically to <ScalarVal(1) as Add>.add(a), which looks for an Add implementation on ScalarVal.

For whatever reason, this one is checked first:

impl<PixelP> Add<Image<PixelP>> for ScalarVal<<PixelP as Pixel>::ScalarType>
    where PixelP: Pixel,
          ScalarVal<<PixelP as Pixel>::ScalarType>: Add<PixelP, Output = PixelP>

PixelP is uninstantiated at this point, so PixelP: Pixel can't be checked. Thus we get to

ScalarVal<<PixelP as Pixel>::ScalarType>: Add<PixelP, Output = PixelP>

Let's simplify this. Since PixelP is unknown right now, <PixelP as Pixel>::ScalarType is unknown. The actual information known by the compiler looks more like

impl<T> Add<Image<T>> for ScalarVal<_>
    where ScalarVal<_>: Add<T, Output = T>

So ScalarVal<_> looks for an Add<T, Output = T>. This means we should look for an appropriate T. Obviously this means looking in ScalarVal's Add impls. Looking at the same one, we get

impl<T2> Add<Image<T2>> for ScalarVal<_>
    where ScalarVal<_>: Add<T2, Output = T2>

which means that if this one matches, T == Image<T2>.

Obviously then T2 == Image<T3>, T3 == Image<T4>, etc. This results in an overflow and general sadness. Rust never finds a disproof, so can't ever guarantee it's going down the wrong path.