CODEWITHSUNDEEP
methodstypesrust
Elf Sternberg
Elf Sternberg

Reputation: 16381

A Rust Type Mystery: Convert a function to a method, and calling function's signatures break compilation

A Mystery about Rust Types that I don't quite get.

I was recently refactoring code for a project and ran into a typing mystery that has me puzzled, and I hope someone here can clarify what's going on.

I've been writing a program to implement the Seam Carving algorithm. "Seam Carving" is a way of reducing an image's dimensions automatically by finding, for each pixel in a first row, the meandering path of pixels from top-to-bottom or left-to-right that would do the least damage to the image, and then removing that "seam." The path is calculated from the energy of each pixel: the distance between the colors of that pixel's two neighbors is calculated, and then the seam with the lowest total delta is identified.

So, Image → Energy Map → Seam → Reduced Image.

In memory, an image is a collection of rows concatenated together. Scanning for a vertical seam means scanning rows (left and right neighbors form the delta), but scanning for a horizontal seam means scanning columns. Adjacent pixels in columns are not adjacent in memory, and this makes multi-threading with rayon or crossbeam difficult.

The good news is that each source is read-only. Generating the energy map requires write access only to the energy map. For columns, if I could rotate the energy map I could multi-thread horizontal scanning. That turns out to be easy, and all I need is a proxy object to map the (x, y) to (y, x) when reading the image. Let's call that proxy object a Pivot.

Let me show some code (AviShaOne is the first seam carving algorithm, from Avidan & Shamir, "Seam Carving," 2007):

fn calculate_energy<I, P, S>(image: &I) -> TwoDimensionalMap<u32>
where
    I: GenericImageView<Pixel = P>,
    P: Pixel<Subpixel = S> + 'static,
    S: Primitive + 'static,
{
   ...
}

impl<'a, I, P, S> AviShaOne<'a, I, P, S>
where
    I: GenericImageView<Pixel = P>,
    P: Pixel<Subpixel = S> + 'static,
    S: Primitive + 'static,
{
    fn find_vertical_seam(&self) -> Vec<u32> {
        energy_to_seam(&calculate_energy(self.image))
    }
    fn find_horizontal_seam(&self) -> Vec<u32> {
        energy_to_seam(&calculate_energy(&Pivot::new(self.image)))
    }
}

Let me emphasize: The above code works. The Pivot remaps the coordinates, and now the internal functions can work with thread-capable memory objects.

If I want to reduce an image by more than one seam, I have to run this calculation repeatedly. It would be nice if I could cache the energy map. (Since the seam meanders, and removing that seam would damage seams that cross it, the column removed would be fairly large, but it would still be less bad than recalculating it for every seam.) I want to add the energy map to the struct, and bring calculate_energy into the the impl.

This is where things get weird:

impl<'a, I, P, S>  AviShaOne<'a, I, P, S>
where
    I: GenericImageView<Pixel = P>,
    P: Pixel<Subpixel = S> + 'static,
    S: Primitive + 'static,
{
    fn calculate_energy(&self, image: &I) -> TwoDimensionalMap<u32>
    {
        ...
    }

    fn find_horizontal_seam(&self) -> Vec<u32> {
        energy_to_seam(&self.calculate_energy(&Pivot::new(self.image)))
    }
}

All I did was move calculate_energy into the implementation. No other code was changed. Pivot has the same type signature as AviShaOne, as they're both handling these GenericImageView objects. And now it won't compile:

176 |         energy_to_seam(&self.calculate_energy(&Pivot::new(self.image)))
    |                                               ^^^^^^ expected type parameter, found struct `pivot::Pivot`

This is the mystery. The functions are literally the same. The type signatures are, as far as I can tell, congruent, literally copied & pasted for consistency. I have not added energy as a field yet! It worked fine when the function was just a function, but now that it's a member of the implementation, the compiler wants something else, but I have no idea what.

What does the compiler want?

Upvotes: 0

Views: 122

Answers (1)

orlp
orlp

Reputation: 118016

There is a very important change, calculate_energy is no longer a generic function for all types I such that I: Gener... etc, etc. Instead it is a regular function expecting a very specific type I.

Which type I? Well, whichever I AviShaOne uses, which I'll assume is the same type as self.image. So calling calculate_energy(self.image) is fine.

However, Pivot::new(self.image) has an entirely different type, it is Pivot, not I. And since calculate_energy is no longer a generic function it can not deal with this.

Upvotes: 2

Related Questions