Lifetimes: storing a Vec of data and a Vec of references to that data side-by-side not working

I'm obviosly missing some fundimental concept with rust. I'm pretty experienced with c++ and maybe that's whats throwing me. I've implemented this code several times now. The only time it was truely successful was when I used an index in the Tile struct rather than a refererence. I just don't like the idea of using a index when I should be able to use a reference. In C++ this would be no problem but in rust it really hates the idea of storing a reference in a struct.
The error I get is:

error[E0502]: cannot borrow `tiler` as immutable because it is also borrowed as mutable
   --> src\main.rs:139:5
    |
138 |     if tiler.calc((768,768)){
    |        --------------------- mutable borrow occurs here
139 |     tiler.write_image(PathBuf::from("out.png"));
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |     |
    |     immutable borrow occurs here
    |     mutable borrow later used here

and here's the code:

use std::path::PathBuf;

use std::collections::BTreeSet;

type Position=(u32,u32);

type Extent=(u32,u32);

type Bound=(u32,u32,u32,u32);

#[derive(Debug)]

struct Image {

    file: PathBuf,

    dimension: Extent,

}

#[derive(Debug)]

struct Tile <'a>{

    image: &'a Image,

    bound: Bound

}

struct Tiler <'a>{

    images: Vec<Image>,

    tiles: Vec<Tile<'a>>,

    dimension: Extent,

}

fn bound(pos:Position,sze:Extent)->Bound{

    (pos.0,pos.1,pos.0+sze.0,pos.1+sze.1)

}

impl<'a> Tiler <'a>{

    fn new() -> Self {

        Tiler {

            images: Vec::new(),

            tiles: Vec::new(),

            dimension: (0, 0),

        }

    }

    fn set_files(&mut self, files: &[PathBuf]) {

        for file in files {

            match imagesize::size(file) {

                Ok(d) => self.images.push(Image {

                    file: file.to_path_buf(),

                    dimension: (d.width as u32, d.height as u32),

                }),

                Err(why) => {

                    println!("{}", why)

                }

            }

        }

        self.images.sort_by(|a, b| {

            (b.dimension.0 * b.dimension.0 / b.dimension.1)

                .cmp(&(a.dimension.0 * a.dimension.0 / a.dimension.1))

        });

    }

    fn calc(&'a mut self, dimension: (u32, u32)) -> bool {

        self.dimension = dimension;

        let mut xset = BTreeSet::new();

        let mut yset = BTreeSet::new();

        xset.insert(0u32);

        yset.insert(0u32);

        self.images.iter().all(|image| {

            let mut want = (0u32, 0u32, 0u32, 0u32);

            let found = yset.iter().any(|y| {

                xset.iter().any(|x| {

                    want = bound((*x,*y),image.dimension);

                    if want.2>dimension.0 {return false;}

                    if want.3>dimension.1 {return false;}

                    self.tiles.iter().all(|t| {

                        want.0 >= t.bound.2

                            || want.1 >= t.bound.3

                            || want.2 <= t.bound.0

                            || want.3 <= t.bound.1

                    })

                })

            });

            self.tiles.push(Tile {

                image,

                bound:want

            });

            xset.insert(want.2);

            yset.insert(want.3);

            found

        })

    }

    fn as_ratios(&self)->Vec<(f32,f32,f32,f32)>{

        let mut out=Vec::new();

        let full=(self.dimension.0 as f32,self.dimension.1 as f32);

        for tile in &self.tiles{

            out.push((tile.bound.0 as f32/full.0,

                tile.bound.1 as f32/full.1,

                tile.bound.2 as f32/full.0,

                tile.bound.3 as f32/full.1,))

        }

        out

    }

    fn write_image(&self, out:PathBuf) {

        let out_image = &mut image::RgbaImage::new(self.dimension.0, self.dimension.1);

        for tile in &self.tiles {

            let in_image = &image::io::Reader::open(tile.image.file.as_path())

                .unwrap()

                .decode()

                .unwrap();

            image::imageops::overlay(

                out_image,

                in_image,

                tile.bound.0 as i64,

                tile.bound.1 as i64,

            );

        }

        match image::save_buffer(

            out,

            out_image,

            self.dimension.0,

            self.dimension.1,

            image::ColorType::Rgba8,

        ) {

            Ok(_) => {}

            Err(e) => {

                println!("Failed to save file. {}", e);

            }

        }

    }

}

fn main(){

    let paths = [

        PathBuf::from("a.png"),

        PathBuf::from("R.png"),

        PathBuf::from("b.png"),

        PathBuf::from("s.png"),

        PathBuf::from("t.png"),

        PathBuf::from("c.png"),

        PathBuf::from("d.png"),

        PathBuf::from("a.png"),

        PathBuf::from("R.png"),

        PathBuf::from("b.png"),

    ];

    let mut tiler = Tiler::new();

    tiler.set_files(paths.as_slice());

    if tiler.calc((768,768)){

    tiler.write_image(PathBuf::from("out.png"));

    }

}

I'm not expert with lifetimes. But I think fn calc(&'a mut self means that any call to tiler.calc will require the mutable reference last for all the tiler's lifetime, so it won't be borrowable anymore. (because you cannot borrow something that is already mutably borrowed)

Here is an example that doesn't compile:

use std::marker::PhantomData;

struct A<'a> {
        p: PhantomData<&'a ()>
}

impl<'a> A<'a> {
        fn foo(&'a mut self) {}
        fn bar(&self) {}
}

fn main() {
        let mut a = A {p: Default::default()};
        a.foo();
        a.bar();// error[E0502]: cannot borrow `a` as immutable because it is also borrowed as mutable
}

Here, removing the 'a in foo solves the problem.

It looks like you are trying to construct a self-referential struct, this is not something you can do with references in safe rust. You really should consider the indices approach or if there is another architecture you could employ.

2 Likes

The immediate error is caused by the signature of calc, which conflates the lifetime of the &mut self borrow with the 'a parameter of Tiler:

-    fn calc(&'a mut self, dimension: (u32, u32)) -> bool {
+    fn calc(&mut self, dimension: (u32, u32)) -> bool {

However, this still does not allow the code to compile. This is due to the general error: the lifetime 'a on Tiler implies that tiles is borrowing from somewhere outside the struct, but you're attempting to borrow data inside the struct. The reason this doesn't work is because images (the field being borrowed from) could be moved or dropped, leaving tiles with dangling references. As an example of how this causes safety issues, suppose that the compiler allowed this struct, and consider this usage:

fn main() {
    let mut tiler = Tiler::new();
    let path = PathBuf::from("a.png");
    tiler.set_files(&[path.clone()]);
    tiler.calc((1, 1));
    tiler.set_files(&vec![path.clone(); 32]);
    tiler.write_image(PathBuf::from("b.png"));
}

The first call to set_files() adds an Image to the images vector, and calc() adds a Tile with a reference to it. Then, the second call to set_files() adds 32 more elements to images. To accommodate the extra space, the vector must reallocate, moving the previous Image to another location on the heap. Then, when write_image() reads the Tile, it attempts to access the deallocated Image, resulting in a segmentation fault.

There are three solutions to this issue. The first solution, as you mentioned, is to remove the &'a Image reference from Tile, and effectively use it as an index into an Image. The second solution is to have Tiler borrow its images, instead of owning them:

use std::collections::BTreeSet;
use std::path::{Path, PathBuf};

type Position = (u32, u32);
type Extent = (u32, u32);
type Bound = (u32, u32, u32, u32);

#[derive(Debug)]
struct Image {
    file: PathBuf,
    dimension: Extent,
}

impl Image {
    fn new(file: impl Into<PathBuf>) -> imagesize::ImageResult<Image> {
        let file = file.into();
        let d = imagesize::size(&file)?;
        Ok(Image {
            file,
            dimension: (d.width as u32, d.height as u32),
        })
    }
}

#[derive(Debug)]
struct Tile<'a> {
    image: &'a Image,
    bound: Bound,
}

struct Tiler<'a> {
    images: &'a [Image],
    tiles: Vec<Tile<'a>>,
    dimension: Extent,
}

fn bound(pos: Position, sze: Extent) -> Bound {
    (pos.0, pos.1, pos.0 + sze.0, pos.1 + sze.1)
}

impl<'a> Tiler<'a> {
    fn new(images: &'a [Image]) -> Self {
        Tiler {
            images,
            tiles: Vec::new(),
            dimension: (0, 0),
        }
    }

    fn calc(&mut self, dimension: (u32, u32)) -> bool {
        self.dimension = dimension;
        let mut images: Vec<_> = self.images.iter().collect();
        images.sort_by(|a, b| {
            (b.dimension.0 * b.dimension.0 / b.dimension.1)
                .cmp(&(a.dimension.0 * a.dimension.0 / a.dimension.1))
        });
        let mut xset = BTreeSet::new();
        let mut yset = BTreeSet::new();
        xset.insert(0u32);
        yset.insert(0u32);
        images.into_iter().all(|image| {
            let mut want = (0u32, 0u32, 0u32, 0u32);
            let found = yset.iter().any(|y| {
                xset.iter().any(|x| {
                    want = bound((*x, *y), image.dimension);
                    if want.2 > dimension.0 {
                        return false;
                    }
                    if want.3 > dimension.1 {
                        return false;
                    }
                    self.tiles.iter().all(|t| {
                        want.0 >= t.bound.2
                            || want.1 >= t.bound.3
                            || want.2 <= t.bound.0
                            || want.3 <= t.bound.1
                    })
                })
            });
            self.tiles.push(Tile { image, bound: want });
            xset.insert(want.2);
            yset.insert(want.3);
            found
        })
    }

    fn as_ratios(&self) -> Vec<(f32, f32, f32, f32)> {
        let full = (self.dimension.0 as f32, self.dimension.1 as f32);
        self.tiles
            .iter()
            .map(|tile| {
                (
                    tile.bound.0 as f32 / full.0,
                    tile.bound.1 as f32 / full.1,
                    tile.bound.2 as f32 / full.0,
                    tile.bound.3 as f32 / full.1,
                )
            })
            .collect()
    }

    fn write_image(&self, out: impl AsRef<Path>) {
        let out_image = &mut image::RgbaImage::new(self.dimension.0, self.dimension.1);
        for tile in &self.tiles {
            let in_image = image::open(&tile.image.file).unwrap();
            image::imageops::overlay(
                out_image,
                &in_image,
                tile.bound.0 as i64,
                tile.bound.1 as i64,
            );
        }
        if let Err(e) = image::save_buffer(
            out,
            out_image,
            self.dimension.0,
            self.dimension.1,
            image::ColorType::Rgba8,
        ) {
            println!("Failed to save file. {}", e);
        }
    }
}

fn main() {
    let images: Vec<_> = ["a.png", "a.png", "a.png"]
        .into_iter()
        .map(|file| Image::new(file.to_owned()).unwrap())
        .collect();
    let mut tiler = Tiler::new(&images);
    tiler.calc((3, 1));
    tiler.write_image("b.png");
}

(I also cleaned up some other parts of the implementation here.) Finally, a third solution is to add an additional type that stores an Image alongside a Tile borrowing it. This can be done with a crate such as ouroboros or self_cell, but it's generally considered less idiomatic.

1 Like

In C++ it would also be "no problem" to call set_files another time (which pushes new images to the images vector) after calc has been called (which created some Tiles that contain pointers to elements of the images vector). Pushing to a vector can grow it and reallocate, then all the references in the existing tiles become dangling. And other methods like write_image can access those references, which means use-after-free is possible through that API.

Rust prevents any situation that comes even close to accessing dangling references / use-after-free errors. It's a trade-off; it's a bit too restrictive even in cases that "ought to be safe", but you win the safety.

Storing indices is no more expensive anyways.

There's also other alternatives that might be more ergonomic than using indices into the Vec; for example, you could make it images: Vec<Rc<Image>> in the Tiler, and store copies of these reference-counter / shared-ownership pointers in the tiles, which become struct Tile { image: Rc<Image>, bound: Bound }.

3 Likes

Let's look a little closer at this:

impl<'a> Tiler<'a> {
    fn calc(&'a mut self, dimension: (u32, u32)) -> bool {

You're taking a &'a mut Tiler<'a>. This pattern of the same lifetime nested behind a &mut is an anti-pattern, as it means that the Tiler is borrowed for its entire lifetime. You won't be able to use it any more after calling calc, except perhaps via some return value of calc.

If we remove the lifetime:

    fn calc(&mut self, dimension: (u32, u32)) -> bool {

We get a slew of errors that are probably the reason you put the lifetime on their in the first place. And in fact, using the anti-pattern is likely the only way to resolve those errors without changing to a new approach, because as @geeklint pointed out, you're creating a self-referencial struct. It's necessary to borrow yourself (&'a mut self) for as long as you're going to be storing references to your self (Tiler<'a>) in order to complete the creation.

The fact that the struct is no longer usable afterwards [1] is why people say "self-referential (using references) structs are not possible in safe Rust"; it's a useful approximation. The struct remaining borrowed for its remaining lifetime prevents things like the Vec reallocation @steffahn mentions.

Others have already shown alternative approaches, so I won't go into those.


  1. except possibly partially via a return value ↩ī¸Ž

2 Likes

Another alternative to a self-referencing struct in Rust is using multiple structs where one references (parts of) the other. (FYI, this is the intended use-case for lifetime arguments in struct definitions.) You can split it up into

struct TilerContext {
    images: Vec<Image>
}
struct Tiler<'a> {
    context: &'a TilerContext,
    tiles: Vec<Tile<'a>>,
    dimension: Extent,
}

and the methods accordingly

impl TilerContext {
    fn new() -> Self { ... }
    fn set_files(&mut self, files: &[PathBuf]) { ... }
    fn build_tiler(&self) -> Tiler<'_> {
        Tiler {
            context: self,
            tiles: Vec::new(),
            dimension: (0, 0),
        }
    }
}
impl Tiler<'_> {
    fn calc(&mut self, dimension: (u32, u32)) -> bool { ... }
    fn as_ratios(&self) -> Vec<(f32, f32, f32, f32)> { ... }
    fn write_image(&self, out: PathBuf) { ... }
}

Main becomes something like

fn main() {
    let paths = [
        PathBuf::from("a.png"),
        PathBuf::from("R.png"),
        PathBuf::from("b.png"),
        PathBuf::from("s.png"),
        PathBuf::from("t.png"),
        PathBuf::from("c.png"),
        PathBuf::from("d.png"),
        PathBuf::from("a.png"),
        PathBuf::from("R.png"),
        PathBuf::from("b.png"),
    ];

    let mut tiler_context = TilerContext::new();

    tiler_context.set_files(paths.as_slice());

    let mut tiler = tiler_context.build_tiler();

    if tiler.calc((768, 768)) {
        tiler.write_image(PathBuf::from("out.png"));
    }
}

(all the code is untested, and mainly for illustration of the overall idea, so there might be small mistakes)

The conversion that borrows the TilertContext and creates the Tiler serves as a kind of transition-point in the API usage, after which the contained images vector cannot be modified (until the Tiler is dropped, in which case the context can technically be reused). This way the possible problematic cases where otherwise dangling references could be created are prevented.

4 Likes

Thank you @steffahn, I've adjusted my code based on your suggestion. Only difference being I made the container for Image a boxed slice as the data is immutable anyway. I've learn't a lot from this and I must say I'm quite impressed with how rust forces you to think completely differently and make sure that your code is bulletproof with regard to dangling pointers and memory leaks. Thanks again.

6 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.