[Solved] Question about "lifespan" and "moving"


#1

Hi all, I’m new to Rust and, I’m trying to learn it by solving the problems on exercism.io. I’ve come to the problem name “proverb”.

I have this code:

pub fn build_proverb(list: Vec<&str>) -> String {
    let mut proverb: Vec<&str> = vec![];
    let mut counter: usize = 0;
    while counter < list.len() {
        if counter == list.len() - 1 {
            proverb.push(format!("All for the want of a {}", list[0]));
            break;
        } else {
            proverb.push(format!("For want of a {} the {} was lost", list[counter], list[counter + 1]));
        }
        counter += 1;
    }
    proverb.join("\n")
}

The compiler says I need to borrow the String returned by the call to format macro. If I do borrow it (adding &) then the compiler says that “temporary value does not live long enough” for the referenced String.

Isn’t the string returned by format macro being “moved” into the proverb vector? That should change the lifetime of this String right?

What am I misunderstanding?

Thanks in advance


#2

I made a smaller(?) example that illustrates the issue maybe more clearly.

fn main() {
    let str = format!("Number {} is the answer", 42);
    
    let mut arr : Vec<&str> = Vec::new();
    
    arr.push("abcd"); // okay cause constant strings are 'static
    
    arr.push(&str);   // okay cause str lives longer than arr
    
    let str2 = format!("Number {} is better actually", 43);
    
    arr.push(&str2); // not okay cause str2 lives shorter than arr
    
    // not okay cause the string is dropped after the expression completes
    arr.push(&format!("What about this number {}", 44));
}

link to playground

Bascially since references must always be valid, if you have a container that stores some references, then Rust must be certain that the references stored inside outlives the container.

Otherwise your container may contain invalid references at some point.

EDIT :
More clarifications

  • "abcd" is of type and lifetime &'static str(constant strings are always references to str)
  • Lifetime of str2 being shorter than arr may not be obvious due to them being in the same scope, but dropping happens in reverse order, so things introduced last will be dropped first, things introduced earliest will be dropped last.

#3

Thanks for the reply @darrenldl!

More doubts (I have a background on loosely typed/Scripting languages: JS & Python),
When you say: “str2 lives shorter than arr”: How does it work in detail? Both declarations are at the same scope. How can one “live more” than the other? Does it have to do with the declaration order (str2 being declared after arr)?
And:

Thanks again!


#4

Hi, your code is not optimal, you have got to store the formattings somewhere, cloning the strings. But optimizatin comes second :wink:
The commented code below will compile.

 pub fn build_proverb(list: Vec<&str>) -> String {
        let mut proverb: Vec<String> = vec![]; // store the string-formats
        let mut counter: usize = 0;
        while counter < list.len() {
            if counter == list.len() - 1 {
               // store a clone of the formatting, surviving while-loop-scope
                proverb.push(format!("All for the want of a {}", list[0]).clone()); 
                break;
            } else {
               // store a clone of the formatting, surviving while-loop-scope
                proverb.push(format!("For want of a {} the {} was lost", list[counter], list[counter + 1]).clone()); 
            }
            counter += 1;
            
            // end of the while-scope the temporary variables are dropped
        }
        proverb.join("\n")
    }

#5

So the following is a version of the above code with visualisation of lifetime added

fn main() {
    --let str = format!("Number {} is the answer", 42);
    |
    | --let mut arr : Vec<&str> = Vec::new();
    | |
    | | arr.push("abcd"); // okay cause constant strings are 'static
    | |
    | | arr.push(&str);   // okay cause str lives longer than arr
    | |
    | | --let str2 = format!("Number {} is better actually", 43);
    | | |
    | | | arr.push(&str2); // not okay cause str2 lives shorter than arr
    | | |
    | | | // not okay cause the string is dropped after the expression completes
    | | | arr.push(&format!("What about this number {}", 44));
    | | v -- end of life for str2
    | v -- end of life for arr
    v -- end of life for str
}

So from purely theoretical point of view, or even when trying to formalise the lifetime system in logic, there doesn’t seem to be any need for enforcing the ordering when things are in the same scope, and this would be right if we are in a managed language(e.g. OCaml, JS, Python).

But since Rust is not a managed language, and since we are allocating things on stack[1], this means the first delcared object will be allocated on stack first, and intuitively must have a longer lifetime than whatever follows, and so on.

[1] Actually this is a bit tricky here, since the content of String and Vec are heap allocated, but the handles(the values that arr, str and str2 actually hold) are still stack allocated, but they share the same lifetime. Think of a 2-layered struct, where one struct is stack allocated and points to the other struct which is heap allocated, but the lifetime of both struct are tied together, i.e. when the handle is dropped, the heap allocated struct is dropped as well.
TL;DR the heap content shares the exact same lifetime as the stack allocated content, so we may as well just look at the stack exclusively.

The stack view(assuming the stack builds upwards, doesn’t matter in practice, but clarifying just for the visualisation) would look like

|-----------------|
|      str2       |
|-----------------|
|      arr        |
|-----------------|
|      str        |
|-----------------|
|      ...        |

So intuitively, when we pop the stack content, we pop str2 first, then arr, then str(reverse order of allocation), and thus str2 has shorter lifetime than arr.


#6

Thanks @darrenldl!
I was completely ignoring the Stack/Heap allocation aspect of the assignments!
Now it makes sense!


#7

Thanks for your reply @frehberg. As I’m currently learning the fundamentals of Rust, I’m not concerned about optimization yet. But, I would love to hear/learn about the optimal/idiomatic way to solve this kind of problems.

Regards


#8

the following code will do less costly String cloning and memory allocation. It will create a string-buffer with estimated capacity and writing into the formatted string directly.

use std::fmt::Write;

pub fn build_proverb(list: Vec<&str>) -> String {
    let estimated_buf_size = 1000;
    let mut proverb: String = String::with_capacity(estimated_buf_size);
    
    let mut counter: usize = 0;
    while counter < list.len() {
        if counter == list.len() - 1 {
           // append te formatted string directly to buffer
            proverb.write_fmt(format_args!("All for the want of a {}", list[0])).unwrap(); 
            break;
        } else {
           // append te formatted string directly to buffer
            proverb.write_fmt(format_args!("For want of a {} the {} was lost\n", list[counter], list[counter + 1])).unwrap(); 
        }
        counter += 1;
        
        // end of the while-scope the temporary variables are dropped
    }
    proverb
}
    
fn main() {
    let list = vec!{"Foo", "Bar" };
    
    println!("{}", build_proverb(list))
}

#9

Here’s a similar approach but a bit more concise (IMO):

fn build_proverb(list: Vec<&str>) -> String {
    list.chunks(2)
        .fold(String::with_capacity(1000), |mut s, chunk| {
            if chunk.len() < 2 {
                write!(&mut s, "All for the want of a {}", list[0]).unwrap();
            } else {
                writeln!(
                    &mut s,
                    "For want of a {} the {} was lost",
                    chunk[0], chunk[1]
                ).unwrap();
            }
            s
        })
}

#10

This is beautiful and idiomatic I guess. Didn’t know about the chunks method on vectors nor the fold method on iterators.

Thanks!


#11

I get the optimization part!
Any tips on estimating buffer sizes?

Thanks again.


#12

chunks is the wrong function for the algorithm. windows is one that should of been used. (or zip can do it too.)
Not using counter is idiomatic. Personally would likely use for loop instead of fold.

You could work out exact size but even setting size is an excessive optimisation. Half way would be something like 50*list.len()


#13

Thanks @jonh!
I think that avoiding counter variables and less “;” make better/idiomatic code in general (IMHO).
Will check at the window and zip methods.

Thanks for the buffer estimation tip too.

Regards


#14

The required. buf size depends on the length of each line. I think this would be a nice exercise for u to practice iterators :wink:

In worst case, If the capacity is exceeded, the string-type will re-alloc/grow on its own.


#15

Indeed - I didn’t pay attention! So here’s how a windows() version might look like (I’m ignoring preallocating the string):

fn build_proverb(list: Vec<&str>) -> String {
    let mut s = list.windows(2).fold(String::new(), |mut s, window| {
        writeln!(
            &mut s,
            "For want of a {} the {} was lost.",
            window[0], window[1]
        ).unwrap();
        s
    });
    list.first().map(|x| write!(&mut s, "And all for the want of a {}.", x));
    s
}

But the point is to show some functional approaches, rather than solving the actual problem :crazy_face: