"Overflow evaluating requirement", but such recursion should not occur at all

Question

Here is a long example, because I could not reduce it. 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 get overflow evaluating the requirement <_ as Pixel>::ScalarType in this code snippet?

I am confused because:

• If the Add implementation on line 44 is removed, the code compiles fine. But this implementation should not be used at all => main() uses only Gray , not Image
• The recursion seems to be in the nested structures Image<Image<...>> , but this 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 the part of the image processing library that I want to create. The idea is to have different pixel formats (gray, RGB, Bayer, ...) that you can use for images. Therefore, for the grayscale image you have Image<Gray> . Different Pixel implementations can implement different operators, so you can perform calculations with them (for example, gray_a = gray_b + gray_c ). It is also possible to use scalar values ​​in these implementations, for example, gray_a = gray_b + ScalarVal(42) . Since I want to have ScalarVal as the right - and left argument, there must be two implementations ( impl Add<Gray<...>> for ScalarVal<...> and impl Add<ScalarVal<...>> for Gray<...> ).

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

Hope this makes sense.

Answer 1

ScalarVal(1) + a allows basically <ScalarVal(1) as Add>.add(a) , which is looking for an Add implementation on ScalarVal .

For some reason, this 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 not confirmed at this point, therefore PixelP: Pixel cannot be verified. So we get

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

Let it simplify. Since PixelP unknown right now, <PixelP as Pixel>::ScalarType unknown. The actual information known to the compiler is more like

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

So ScalarVal<_> looking for Add<T, Output = T> . This means that we must look for a suitable T Obviously, this means a search in ScalarVal Add impl s. Looking at the same, we get

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

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

Obviously, then T2 == Image<T3> , T3 == Image<T4> , etc. This leads to overflow and general sadness. Rust never detects intelligibility, so it can never guarantee that it is going the wrong way.