CODEWITHSUNDEEP
recursionrust
Hannes Landeholm
Hannes Landeholm

Reputation: 1629

Idiomatic ownership management of mutating state during arbitrary recursion in Rust

I've just started playing around with Rust. I find it's ownership system really useful but I have a hard time understanding how to use it with arbitrary recursion, especially since Rust lacks guaranteed tail call optimisation.

Consider a function apply with the signature apply(&str) -> (String, bool). It takes a string and deterministically returns a new string. For the purpose of this question we leave the implementation undefined. The function also returns a bool indicating "completion". We need to keep calling the function with the string it returns until the bool indicates completion. It is undefined how many calls it takes for us to get to completion. It could be 1, it could also be 1000000.

Since Rust does not have tail calls, doing this recursively would allocate an O(n) stack which could cause OOM. Since we can throw away the old string after the function has returned the new string, we only need constant memory. Therefore we need to do it in a loop:

fn apply(s: &str) -> (String, bool) {
    return ("xyz".to_string(), true); // Undefined implementation.
}

fn transform(s: &str) -> String {
    let mut im = s;
    loop {
        let (im_s, done) = apply(im);
        if done {
            return im_s;
        }
        im = &im_s
    }
}

However, compiling this will give the error im_s does not live long enough. Do I need to use some sort of runtime ownership checking or heap allocation mechanism to make this compile?

Upvotes: 3

Views: 212

Answers (1)

Shepmaster
Shepmaster

Reputation: 431489

Check your method, and ask "who owns the string when the loop iteration ends?":

fn transform(s: &str) -> String {
    let mut im = s;
    loop {
        let (im_s, done) = apply(im);
        if done {
            return im_s;
        }
        im = &im_s
    }
}

im_s owns the string, and then you take a reference to it. When the loop ends - nothing owns the string. That means that it will be dropped, which makes all existing references invalid. Since a dangling reference would allow you to break Rust memory safety guarantees, it's not allowed and you get the error you see.

The simplest fix is to simply always promote the input to a String:

fn transform(s: &str) -> String {
    let mut im = s.to_string();
    loop {
        let (im_new, done) = apply(&im);
        im = im_new;
        if done {
            return im;
        }
    }
}

Another fix is to use the delightfully-named Cow enum. This allows you to have either an owned or borrowed type:

use std::borrow::Cow;

fn transform(s: &str) -> String {
    let mut im = Cow::Borrowed(s);
    loop {
        let (im_new, done) = apply(&im);
        im = Cow::Owned(im_new);
        if done { break }
    }
    im.into_owned()
}

Upvotes: 4

Related Questions