recursion - Rust 中任意递归期间变异状态的惯用所有权管理

Question

我刚刚开始使用 Rust。我发现它的所有权系统非常有用，但我很难理解如何通过任意递归使用它，尤其是因为 Rust 缺乏有保证的尾调用优化。

考虑一个带有签名 apply(&str) -> (String, bool) 的函数 apply。它接受一个字符串并确定性地返回一个新字符串。出于这个问题的目的，我们未定义实现。该函数还返回一个指示“完成”的 bool 值。我们需要使用它返回的字符串继续调用该函数，直到 bool 指示完成。我们需要多少次调用才能完成是不确定的。可以是1，也可以是1000000。

由于 Rust 没有尾调用，递归地执行此操作会分配 O(n) 堆栈，这可能会导致 OOM。由于我们可以在函数返回新字符串后丢弃旧字符串，因此我们只需要常量内存。因此我们需要循环执行:

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
    }
}

但是，编译它会给出错误 im_s does not live long enough。我是否需要使用某种运行时所有权检查或堆分配机制来进行编译？

Answer 1

检查你的方法，并询问“当循环迭代结束时谁拥有字符串？”:

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 拥有该字符串，然后您引用它。当循环结束时 - 没有任何东西拥有该字符串。这意味着它将被删除，这使得所有现有引用都无效。由于悬挂引用会破坏 Rust 内存安全保证，因此这是不允许的，并且您会看到错误。

最简单的解决方法是始终将输入提升为 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;
        }
    }
}

另一个修复方法是使用名字漂亮的 Cow枚举。这允许您拥有或借用类型:

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()
}