rust - 有没有办法将递归与索引箱的品牌索引一起使用来创建树？

Question

我正在尝试使用 indexing crate 构建一棵树:

use indexing::{Container, Index, scope, container::OnlyIndex};

struct Tree<'id>(Option<(Index<'id>, Index<'id>)>);

fn tree<'a>(c: &mut Container<'a, &mut Vec<Tree<'a>>, OnlyIndex>, depth: usize) -> Index<'a> {
    if depth == 0 {
        c.push(Tree(None))
    } else {
        let left = tree(c, depth - 1);
        let right = tree(c, depth - 1);
        c.push(Tree(Some((left, right))))
    }
}

fn main() {
    let mut v = vec![];
    scope(&mut v, |v| {
        let mut v = v.only_index();
        tree(&mut v, 3);
        assert_eq!(v.len(), 1 + 2 + 4 + 8);
    });
}

这会导致生命周期错误:

error: borrowed data cannot be stored outside of its closure
  --> src/main.rs:18:23
   |
16 |     let mut v = vec![];
   |         ----- borrowed data cannot be stored into here...
17 |     scope(&mut v, |v| {
   |                   --- ...because it cannot outlive this closure
18 |         let mut v = v.only_index();
   |                       ^^^^^^^^^^ cannot be stored outside of its closure

有没有办法正确定义 tree 以在索引范围内工作？

Answer 1

正如评论所指出的，这对于索引箱来说确实是不可能的。但是，这并不意味着通常不可能存储品牌索引。事实上，去掉闭包就可以了，如下代码所示:

use std::marker::PhantomData;
use std::ops::Index;

#[derive(Copy, Clone)]
struct InvariantLifetime<'a>(PhantomData<fn(&'a ()) -> &'a ()>);
pub struct Arena<'b, T>(Vec<T>, InvariantLifetime<'b>);
pub struct Idx<'b>(usize, InvariantLifetime<'b>);

impl<'b, T> Arena<'b, T> {
    pub unsafe fn new(_: &'b mut ()) -> Self {
        Arena(vec![], InvariantLifetime(PhantomData))
    }

    pub fn add(&mut self, t: T) -> Idx<'b> {
        let i = self.0.len();
        self.0.push(t);
        Idx(i, self.1)
    }
}

impl<'b, T> Index<Idx<'b>> for Arena<'b, T> {
    type Output = T;

    fn index(&self, i: Idx<'b>) -> &T {
        unsafe { &self.0.get_unchecked(i.0) }
    }
}

macro_rules! mk_arena {
    ($arena:ident) => {
        let mut tag = ();
        let mut $arena = unsafe { Arena::new(&mut tag) };
    };
}

struct Tree<'b>(Option<(Idx<'b>, Idx<'b>)>);
fn tree<'b>(a: &mut Arena<'b, Tree<'b>>, d: usize) -> Idx<'b> {
    if d > 0 {
        a.add(Tree(Some((tree(a, d - 1), tree(a, d - 1)))))
    } else {
        a.add(Tree(None))
    }
}

pub fn main() {
    mk_arena!(arena);
    let _ = tree(&mut arena, 3);
}

compact_arena crate 有相同的解决方案，有更好的文档。