时间戳

首页 > 解决方案 > 不安全的 Rust 中的堆栈引用，但确保不安全不会从堆栈中泄漏？

recursion - 不安全的 Rust 中的堆栈引用，但确保不安全不会从堆栈中泄漏？

问题描述

我正在实现一些递归代码，其中调用堆栈中更深的函数实例可能需要引用来自先前帧的数据。但是，我只能对这些数据进行非 mut 访问，因此我将这些数据作为参考接收。因此，我需要将这些数据的引用保存在可以从更深的实例访问的堆栈数据结构中。

为了显示：

// I would like to implement this RefStack class properly, without per-item memory allocations
struct RefStack<T: ?Sized> {
    content: Vec<&T>,
}
impl<T: ?Sized> RefStack<T> {
    fn new() -> Self { Self{ content: Vec::new() } }
    fn get(&self, index: usize) -> &T { self.content[index] }
    fn len(&self) -> usize { self.content.len() }
    fn with_element<F: FnOnce(&mut Self)>(&mut self, el: &T, f: F) {
        self.content.push(el);
        f(self);
        self.content.pop();
    }
}

// This is just an example demonstrating how I would need to use the RefStack class
fn do_recursion(n: usize, node: &LinkedListNode, st: &mut RefStack<str>) {
    // get references to one or more items in the stack
    // the references should be allowed to live until the end of this function, but shouldn't prevent me from calling with_element() later
    let tmp: &str = st.get(rng.gen_range(0, st.len()));
    // do stuff with those references (println is just an example)
    println!("Item: {}", tmp);
    // recurse deeper if necessary
    if n > 0 {
        let (head, tail): (_, &LinkedListNode) = node.get_parts();
        manager.get_str(head, |s: &str| // the actual string is a local variable somewhere in the implementation details of get_str()
            st.with_element(s, |st| do_recursion(n - 1, tail, st))
        );
    }
    // do more stuff with those references (println is just an example)
    println!("Item: {}", tmp);
}

fn main() {
    do_recursion(100, list /* gotten from somewhere else */, &mut RefStack::new());
}

在上面的示例中，我关心如何在RefStack没有任何每个项目内存分配的情况下实现。偶尔的分配Vec是可以接受的——那些很少而且介于两者之间。这LinkedListNode只是一个例子——实际上它是一些复杂的图形数据结构，但同样适用——我只有一个对它的非 mut 引用，而给定的闭包manager.get_str()只提供了一个 non-mut str。请注意，传入闭包的非 mutstr只能在get_str()实现中构造，因此我们不能假设所有的&str都具有相同的生命周期。

我相当肯定如果不复制intoownedRefStack就无法在安全的 Rust 中实现，所以我的问题是如何在不安全的 Rust 中完成。感觉我可能能够得到这样的解决方案：strString

如何在（不安全的）Rust 中实现这样的结构？

感觉我可以将元素引用转换为指针并将它们存储为指针，但是在将它们转换回引用时，我仍然会遇到表达上述第二个要点中的要求的困难。还是有更好的方法（或者这种结构可以在安全的 Rust 中实现，或者已经在某个库中）？

标签： recursionruststacklifetimeunsafe

解决方案

我认为存储原始指针是要走的路。您需要 aPhantomData来存储生命周期并获得适当的协方差：

use std::marker::PhantomData;

struct RefStack<'a, T: ?Sized> {
    content: Vec<*const T>,
    _pd: PhantomData<&'a T>,
}

impl<'a, T: ?Sized> RefStack<'a, T> {
    fn new() -> Self {
        RefStack {
            content: Vec::new(),_pd: PhantomData
        }
    }
    fn get(&self, index: usize) -> &'a T {
        unsafe { &*self.content[index] }
    }
    fn len(&self) -> usize {
        self.content.len()
    }
    fn with_element<'t, F: FnOnce(&mut RefStack<'t, T>)>(&mut self, el: &'t T, f: F)
        where 'a: 't,
    {
        self.content.push(el);
        let mut tmp = RefStack {
            content: std::mem::take(&mut self.content),
            _pd: PhantomData,
        };
        f(&mut tmp);
        self.content = tmp.content;
        self.content.pop();
    }
}

（游乐场）

唯一的unsafe代码是将指针转换回引用。

棘手的部分是with_element正确的。我认为这were 'a: 't是隐含的，因为整体impl取决于它（但比抱歉更安全）。

最后一个问题是如何将 aRefStack<'a, T>转换为RefStack<'t, T>. 我很确定我能std::transmute做到。但这需要额外unsafe注意，并且创建一个新的临时堆栈非常简单。

关于't一生

您可能认为't实际上不需要此生命周期，但不添加它可能会导致微妙的不健全，因为回调可能会调用get()并获取生命周期'a实际上比插入值更长的值。

例如，此代码不应编译。如果't它正确失败，但没有它它会编译并导致未定义的行为：

fn breaking<'a, 's, 'x>(st: &'s mut RefStack<'a, i32>, v: &'x mut Vec<&'a i32>) {
    v.push(st.get(0));
}
fn main() {
    let mut st = RefStack::<i32>::new();
    let mut y = Vec::new();
    {
        let i = 42;
        st.with_element(&i, |stack| breaking(stack, &mut y));
    }
    println!("{:?}", y);
}

关于panic!.

当做这些不安全的事情时，特别是当你调用用户代码时，就像我们现在在做的那样with_element，我们必须考虑如果它发生恐慌会发生什么。在 OP 代码中，不会弹出最后一个对象，当堆栈展开时，任何drop实现都可以看到现在悬空的引用。如果发生恐慌，我的代码是可以的，因为如果f(&mut tmp);悬空引用在本地临时死掉，tmp而self.content为空。

推荐阅读