不安全Rust中的引用堆栈，但确保不安全性不会泄露出堆栈？

Question

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

为了说明：

// 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引用，以及给管理器的闭包。get_str（）仅提供非mutstr。请注意，传递到闭包中的非mutstr只能在get_str（）实现中构造，因此我们不能假设所有

我相当确定，如果不将str复制到拥有的Strings中，RefStack就无法在安全的Rust中实现，所以我的问题是如何在不安全的Rust中做到这一点。感觉我可能会得到一个解决方案：

• 不安全性仅限于RefStack

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

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




Answer 1

免责声明：不同的答案；有不同的权衡。

与我的另一个答案相比，这个答案给出了一个解决方案：

• 不安全：它是封装的，但很微妙
• 使用起来更简单
• 代码更简单，可能更快

其想法是仍然使用堆栈来绑定引用的生存期，同时将所有生存期存储在单个Vec中，以进行O（1）随机访问。所以我们在堆栈上构建一个堆栈，但不在堆栈上存储引用本身。好吧

这里有完整的代码。

堆栈本身很容易定义：

struct StackRoot<T: ?Sized>(Vec<*const T>);

struct Stack<'a, T: ?Sized>{
    len: usize,
    stack: &'a mut Vec<*const T>,
}

impl<T: ?Sized> StackRoot<T> {
    fn new() -> Self { Self(vec!()) }

    fn stack(&mut self) -> Stack<'_, T> { Stack { len: 0, stack: &mut self.0 } }
}

Stack的实现更棘手，当涉及不安全时总是这样：

impl<'a, T: ?Sized> Stack<'a, T> {
    fn len(&self) -> usize { self.len }

    fn get(&self, index: usize) -> Option<&'a T> {
        if index < self.len {
            //  Safety:
            //  -   Index is bounds as per above branch.
            //  -   Lifetime of reference is guaranteed to be at least 'a (see push).
            Some(unsafe { &**self.stack.get_unchecked(index) })
        } else {
            None
        }
    }

    fn push<'b>(&'b mut self, element: &'b T) -> Stack<'b, T>
        where
            'a: 'b
    {
        //  Stacks could have been built and forgotten, resulting in `self.stack`
        //  containing references to further elements, so that the newly pushed
        //  element would not be at index `self.len`, as expected.
        //
        //  Note that on top of being functionally important, it's also a safety
        //  requirement: `self` should never be able to access elements that are
        //  not guaranteed to have a lifetime longer than `'a`.
        self.stack.truncate(self.len);

        self.stack.push(element as *const _);
        Stack { len: self.len + 1, stack: &mut *self.stack }
    }
}

impl<'a, T: ?Sized> Drop for Stack<'a, T> {
    fn drop(&mut self) {
        self.stack.truncate(self.len);
    }
}

注意这里的不安全；不变量是，“一个参数总是比目前为止推入堆栈的元素的寿命更严格。

通过拒绝访问其他成员推送的元素，我们可以保证返回引用的生存期是有效的。

它确实需要do_recursion的通用定义，但是在代码生成时会删除通用生命周期参数，因此不涉及代码膨胀：

fn do_recursion<'a, 'b>(nodes: &[&'a str], stack: &mut Stack<'b, str>) 
    where
        'a: 'b
{
    let tmp: &str = stack.get(stack.len() - 1).expect("Not empty");
    println!("{:?}", tmp);

    if let [head, tail @ ..] = nodes {
        let mut new = stack.push(head);
        do_recursion(tail, &mut new);
    }
}

一个简单的main来展示它：

fn main() {
    let nodes = ["Hello", ",", "World", "!"];
    let mut root = StackRoot::new();
    let mut stack = root.stack();
    let mut stack = stack.push(nodes[0]);

    do_recursion(&nodes[1..], &mut stack);
}

导致：

"Hello"
","
"World"
"!"

Answer 2

免责声明：这个答案最初使用的是特征，这是一场噩梦；弗朗西斯·加涅（Francis Gagne）正确地指出，在尾部使用选项是一个更好的选择，因此答案大大简化。

根据您的使用结构，使用RefStack中的堆栈跟踪堆栈框架的使用，您可以简单地将元素放在堆栈框架上，并从中构建堆栈。

这种方法的主要优点是完全安全。您可以在这里查看整个代码，或者按照下面的详细描述进行操作。

关键是想法是建立一个所谓的缺点列表。

#[derive(Debug)]
struct Stack<'a, T> {
    element: &'a T,
    tail: Option<&'a Stack<'a, T>>,
}

impl<'a, T> Stack<'a, T> {
    fn new(element: &'a T) -> Self { Stack { element, tail: None } }

    fn top(&self) -> &T { self.element }

    fn get(&self, index: usize) -> Option<&T> {
        if index == 0 {
            Some(self.element)
        } else {
            self.tail.and_then(|tail| tail.get(index - 1))
        }
    }

    fn tail(&self) -> Option<&'a Stack<'a, T>> { self.tail }

    fn push<'b>(&'b self, element: &'b T) -> Stack<'b, T> { Stack { element, tail: Some(self) } }
}

一个简单的用法示例是：

fn immediate() {
    let (a, b, c) = (0, 1, 2);

    let root = Stack::new(&a);
    let middle = root.push(&b);
    let top = middle.push(&c);
    
    println!("{:?}", top);
}

它只打印堆栈，产生：

Stack { element: 2, tail: Some(Stack { element: 1, tail: Some(Stack { element: 0, tail: None }) }) }

以及更详细的递归版本：

fn recursive(n: usize) {
    fn inner(n: usize, stack: &Stack<'_, i32>) {
        if n == 0 {
            print!("{:?}", stack);
            return;
        }

        let element = n as i32;
        let stacked = stack.push(&element);
        inner(n - 1, &stacked);
    }

    if n == 0 {
        println!("()");
        return;
    }

    let element = n as i32;
    let root = Stack::new(&element);
    inner(n - 1, &root);
}

哪些打印：

Stack { element: 1, tail: Some(Stack { element: 2, tail: Some(Stack { element: 3, tail: None }) }) }

一个缺点是get性能可能不太好；它具有线性复杂性。另一方面，以缓存方式粘贴堆栈帧非常好。如果你基本上都能接触到前几个元素，我想这就足够了。

Answer 3

我认为存储原始指针是一种方法。您需要一个PhantomData来存储生存期并获得适当的协方差：

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

（游乐场）

唯一不安全的代码是将指针转换回引用。

棘手的部分是正确使用_元素。我认为are'a:'t是隐式的，因为整个impl依赖于它（但安全总比抱歉好）。

最后一个问题是如何转换RefStack

您可能认为实际上不需要这个'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);
}

在做这些不安全的事情时，尤其是在调用用户代码时，就像我们现在在使用_element的中所做的那样，我们必须考虑如果出现恐慌会发生什么。在操作代码中，最后一个对象不会弹出，当堆栈展开时，任何drop实现都可以看到现在悬空的引用。如果恐慌，我的代码是可以的，因为如果f(