6

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.

  • 1
    "I was not able to reduce it further" → You don't seem to have tried very hard then. I got it down to this before I called it good enough. That makes the error pretty clear. – Veedrac Sep 9 '16 at 0:43
  • Likewise, I got it down to this. – Shepmaster Sep 9 '16 at 1:05
6

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.

  • Thanks for your answer! That clears things up a bit. I still have a question though: Why is PixelP unknown? Isn't this a type checking problem at the point where ScalarVal(1) + a is executed? So it is already known that a is Gray<...>?! Is there a way to solve this issue? – Daniel Sep 9 '16 at 13:26
  • 1
    @Daniel PixelP is unknown because Rust is still checking the where clause; it hasn't yet gotten to the add method. I don't see any obvious way to solve this, but it's probably solvable with enough work. – Veedrac Sep 9 '16 at 20:21

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.