[Resolved] Self-referential struct case

Hi,

Given this simple snippet:

struct SomeType(u32);

struct App<'a> {
    flags: Vec<SomeType>,
    graph: Vec<&'a SomeType>,
}

impl<'a> App<'a> {
    fn build(&mut self) -> &mut Self {
        for some_type in &self.flags {
            // this does not compile
            self.graph.push(&some_type)
        }
        self
    }
}

fn main() {
    let mut app = App {
        flags: vec![SomeType(1), SomeType(2), SomeType(3)],
        graph: vec![],
    };

    for some_type in &app.flags {
        // but this works
        app.graph.push(&some_type)
    }
}

I got the following error when I try to compile:

   Compiling rust v0.1.0 (/home/pierre/Documents/test)
error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:10:26
   |
10 |         for some_type in &self.flags {
   |                          ^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 9:5...

Someone told me that I encountered a "self-referential struct" case and that it's not allowed to implement this pattern in Rust due to the

ownership/borrowing system just does not allows the struct fields to reference other fields from the same struct

I'm okay with that. But if this is not possible, why the line of code in the main function compiles and works well ?

In this case, what I think is happening is that, because you've defined your data to last through the entirety of main, none of your references are ever going to be invalidated within the scope of main. Rust doesn't explicitly check for self-referential data, what it looks for is dangling references via lifetime analysis, and there's nothing invalid about what you've got there. But you'll notice there's a problem if you try to move your app into a function, because you can't move a self-referential struct. You'll get an error saying you can't move the struct because it is currently borrowed. (You also won't be able to borrow it mutably.)

1 Like

If you store the to-be-referenced data in a vector, the second vector containing the references should contain the indices to the location in the data vector, instead. This'll prevent use-after-free bugs when growing the data vector.

The compiler is sometimes able to reason about individual fields in a struct as if they were distinct variables. That's what happening here. The reason it works is that graph is borrowing from flags, so flags cannot be modified or moved, which makes having the references okay.

The code in main works because it can borrow app.flags for the whole lifetime of the app binding, but in your impl block, the .build() method is required to borrow for an anonymous lifetime that csn be smaller than 'a, but since your struct is self-referential you need to borrow it for at least 'a. So by slightly changing the signature of .build(), the code compiles.

That being said, once you start using it, you will quickly notice how impractical it is to require such a long-lived borrow, and how unusable your struct ends up being. You should use indexing or rc::Weak<SomeType> as your reference type, or if you persist into using Rust compile-time handled borrows, have the graph main allocation be handled from within an outer arena that outlives your main program logic.

4 Likes

One way of looking at it is to suppose that build is unsound, and main is sound, and try to figure out why. In this case it's because, if build worked the way you want it to, you could use it to create a dangling reference:

let foo = SomeType(10);      // longer lifetime
let graph = { 
    let bar = SomeType(20);  // shorter lifetime
    let mut app = App {
        flags: vec![bar],
        graph: vec![&foo],
    };
    app.build();
    app.graph
    // app.flags gets dropped here, but app.graph is allowed to "escape" to
    // the outer scope because its lifetime parameter only references long-
    // lived data. If app.build() worked, you could use it to smuggle a
    // short-lived reference to bar into a vector of long-lived references,
};
// ... which would be dereferenced when the following line was executed:
println!("{:?}", graph);

If I comment out the body of build, this compiles and runs. The compiler is right to reject the build that you wrote because, if it were allowed, this code would have undefined behavior.

If you change the signature of build to the one @Yandros suggested, the compiler rejects this code because the new signature forces build to borrow app for the entire lifetime of foo, which is longer than the lifetime of app.

Your original main is sound because, being all in one function, the compiler can reason about it from start to finish and ascribe whatever lifetimes make it work. This isn't true of build because the signature of build defines some lifetime relationships that it must uphold.

2 Likes

Ok thanks all for your many answers !
Especially @Yandros and @trentj for your explanation and your examples !
It helps me a lot to understand exactly what's going on and that's all I need !