Rust中迭代式树解析的可行实现方案探讨

定义与需求 #

我们定义了如下Tree结构体：

#[derive(Default, Debug, PartialEq, Eq)]
struct Tree {
    children: Vec<Tree>,
}

需要通过bool列表构建该树：true对应XML的开始标签，false对应结束标签，例如[true, true, false, true, false, false]对应指定树形结构。

递归实现（可行但有缺陷） #

递归实现的解析函数可正常工作，但存在递归深度限制、栈溢出风险等固有缺陷：

fn read_tree_recursive<'a>(tags: &mut impl Iterator<Item=&'a bool>) -> Tree {
    let mut tree = Tree::default();
    while let Some(&tag) = tags.next() {
        if tag {
            tree.children.push(read_tree_recursive(tags));
        } else {
            break;
        }
    }
    tree
}

常规迭代实现的问题 #

尝试用栈实现迭代版本时，会触发Rust借用检查器报错：

fn read_tree_iterative(tags: &[bool]) -> Tree {
    let mut root = Tree::default();
    let tree_stack: Vec<&mut Tree> = vec![&mut root];

    for &tag in tags {
        if tag {
            tree_stack.last().unwrap().children.push(Tree::default());
            tree_stack.push(tree_stack.last().unwrap().children.last_mut().unwrap());
        } else {
            tree_stack.pop();
        }
    }
    root
}

报错原因是：代码同时持有对tree_stack的不可变引用（tree_stack.last().unwrap()）和对栈内节点的可变引用（children.last_mut().unwrap()），Rust无法确认这些引用不会产生冲突，因此拒绝编译。

替代解决方案（无需RefCell） #

1. 使用子节点列表的可变引用栈（安全最优解） #

将栈存储的内容从&mut Tree改为&mut Vec<Tree>（即当前节点的子节点列表的可变引用），避免同时持有多个节点的可变引用：

fn read_tree_iterative(tags: &[bool]) -> Tree {
    let mut root = Tree::default();
    let mut stack = vec![&mut root.children];

    for &tag in tags {
        if tag {
            // 向当前子节点列表添加新节点
            stack.last_mut().unwrap().push(Tree::default());
            // 获取新节点的子节点列表，压入栈
            let new_children = &mut stack.last_mut().unwrap().last_mut().unwrap().children;
            stack.push(new_children);
        } else {
            stack.pop();
        }
    }

    root
}

这种方法完全符合Rust的借用规则，无需unsafe操作，是最推荐的方案。

2. 使用原始指针（unsafe方案） #

通过原始指针绕过借用检查器，但需要手动保证内存安全（确保指针有效、无悬垂、无重叠可变引用）：

fn read_tree_iterative_unsafe(tags: &[bool]) -> Tree {
    let mut root = Tree::default();
    let mut stack = vec![&mut root as *mut Tree];

    for &tag in tags {
        if tag {
            let current = unsafe { &mut *stack.last().unwrap() };
            current.children.push(Tree::default());
            let new_node = current.children.last_mut().unwrap() as *mut Tree;
            stack.push(new_node);
        } else {
            stack.pop();
        }
    }

    root
}

此方法需谨慎使用，仅当你能完全保证指针操作的安全性时才考虑。

3. 索引栈结合回溯（效率较低） #

栈中存储从根节点到当前节点的索引路径，每次需要访问当前节点时，从根节点遍历索引路径获取可变引用。这种方法无需unsafe，但每次访问节点都要回溯路径，效率较低，适合小型树：

fn read_tree_iterative_index(tags: &[bool]) -> Tree {
    let mut root = Tree::default();
    let mut index_stack = Vec::new();

    for &tag in tags {
        if tag {
            // 从根节点遍历到当前节点
            let current_node = index_stack.iter().fold(&mut root, |node, &idx| {
                &mut node.children[idx]
            });
            current_node.children.push(Tree::default());
            // 记录新节点的索引
            index_stack.push(current_node.children.len() - 1);
        } else {
            index_stack.pop();
        }
    }

    root
}

内容的提问来源于stack exchange，提问作者Timmmm