Recursive Types without Box<T> mysteriously possible although the book says they aren't?

Hello dear helpful Rustaceans,

I am currently battling my way through the official book and there is one thing I apparently do not understand yet.

In the book, it is explained why cons-lists aren't possible by just declaring an enum with a tuple containing the initial enum as one of its variants (and Nil as the other). The solution presented is using the Box-Type.

Later in the book, it is stated that using normal references with & is not possible for cons-lists, because "we would have to specify lifetime parameters". It is further stated that

let a = Cons(10, &Nil);

would not be possible, because "the temporary Nil value would be dropped before a could take a reference to it.".

I fully understand the reasoning, but after I tried to use simple & anyway, the code mysteriously worked. Here is what I mean:

#[derive(Debug)]
enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil
}
fn main() {
    let liste = List::Cons(10, &List::Nil);
    println!("{:?}", liste);
}

How is this possible? I am quite tired at the moment, so I am fully prepared for it to be an insanely stupid thinking bug from myself.

Thank you in advance,
Arnanas

1 Like

There are a few lifetime extension rules (I don’t know the details) that allow temporaries to implicitly be made into values alive for the entire scope they’re defined in. This allows statements such as

let x = &1;

or

let x = &String::from("123");

to compile.

My best guess is that those have been extended over time and the book is giving an outdated example.


Interesting, even this compiles:

fn main() {
    let mut liste = List::Cons(10, &List::Nil);
    {
        liste = List::Cons(20, &List::Nil);
    }
    println!("{:?}", liste);
}

so it appear the extension is to the scope the variable assigned to lives in or something...


THIS ONE ALSO COMPILES :sweat_smile:

fn main() {
    let mut liste = List::Cons(10, &List::Nil);
    {
        let other_list = List::Cons(20, &List::Nil);
        liste = other_list;
    }
    println!("{:?}", liste);
}

okay, now my best guess is that the lifetime is extended to as long as the borrow checker deems necessary. But it can’t live longer than the containing function, so this won’t work:

fn main() {
    let mut liste = List::Cons(10, &List::Nil);
    (|| {
        let other_list = List::Cons(20, &List::Nil);
        liste = other_list;
    })();
    println!("{:?}", liste);
}

it ... what?!? ...it compiles.........

Last chance, this doesn’t work for sure:

#[derive(Debug)]
enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil
}
fn main() {
    let mut liste = List::Cons(10, &List::Nil);
    foo(&mut liste);
    println!("{:?}", liste);
}

fn foo(l: &mut List<'_>) {
    *l = List::Cons(20, &List::Cons(20, &List::Nil));
}

(How can this possibly?? I thought I knew Rust :cry:)

It’s 3:30 am here, I’ll go to sleep, too.

4 Likes

This is rvalue static promotion, added in Rust 1.21.

9 Likes

Gosh, thank you, stupid static stuff.. I got as far as to notice that it doesn’t work anymore if the list’s content has destructors before your explanation arrived.

@Arninius to put my comment on lifetime extension into context, it apparently does not cover anything where the reference is passed to any function or constructor. Just when you directly assign the reference. Or reference of reference... I wonder what the exact rules are.

Some examples, so let’s kill this static monstrosity stuff by not using List::Nil directly anymore, but

fn nil<'a>() -> List<'a> { List::Nil }

then we can see that

let liste_ref = &nil();

or even

let liste_ref_ref = &&nil();

do still compile, however

let liste = List::Cons(10, &nil());

doesn’t.

1 Like

Also, you might want to open an issue on https://github.com/rust-lang/book as the example they claim doesn't compile does compile.

1 Like

To put it simply: Nil behaves like a constant for the purposes of construction and lifetime analysis, just like literal numbers or strings, so it's possible to realize it as if it were a single global thing that you can take the address of, just like a static global, and the compiler politely performs this transformation automatically for your convenience.

3 Likes

Thank you all for your help, I am going to open an issue at the github-book-page now.

1 Like

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.