首页 文章

Rust任意递归过程中变异状态的惯用所有权管理

提问于
浏览
3

我刚刚开始玩Rust . 我发现它的所有权系统非常有用但我很难理解如何将它与任意递归一起使用,特别是因为Rust缺乏有保证的尾调用优化 .

考虑使用签名 apply(&str) -> (String, bool) 的函数apply . 它需要一个字符串并确定性地返回一个新字符串 . 出于这个问题的目的,我们不确定实现 . 该函数还返回一个bool,表示"completion" . 我们需要继续使用它返回的字符串调用函数,直到bool指示完成 . 未定义我们完成所需的调用次数 . 它可能是1,也可能是1000000 .

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

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 . 我是否需要使用某种运行时所有权检查或堆分配机制来进行编译?

1 回答

  • 4

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

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

相关问题