可变切片的树形结构

Question

一些算法通过递归地将数组划分为较小的部分。你可以构建一个明确的二叉树，该树来自这样的过程，其中每个叶子节点都保存数组的不相交片段。如果需要更改或重新排序叶子中的元素，则必须使其片段可变。

enum Tree<'a> {
    Branch(Box<[Tree<'a>; 2]>),
    Leaf(&'a mut[f32]),
}

假设我需要分割所有大于某个阈值的叶子节点。很简单：从根节点开始递归地遍历整棵树；当我找到一个足够长的叶子节点时，将其分成两半，将它们包装成一个有两个叶子节点的子树，并替换原来的叶子节点。

impl<'a> Tree<'a> {
    fn split(&mut self, max: usize) {
        match self {
            &mut Tree::Branch(ref mut trees) => {
                trees[0].split(max);
                trees[1].split(max);
            },
            &mut Tree::Leaf(ref mut leaf) if leaf.len() > max => {
                let mid = leaf.len() / 2;
                let (l, r) = leaf.split_at_mut(mid);
                let trees = [Tree::Leaf(l), Tree::Leaf(r)];
                *self = Tree::Branch(Box::new(trees));
            },
        }
    }
}

很遗憾，借用检查器无法为ref mut leaf模式找到合适的生命周期。它想在允许对*self进行赋值之前将其销毁，但我不知道如何使匹配分支外的赋值生效。

如何解决这个问题？

- Valéry

---

这可能会有用：https://doc.rust-lang.org/nightly/nomicon/borrow-splitting.html。我没有详细查看您的要求，但`slice.split_at_mut()`可能是您需要的。 - Peter Hall

确实，我在第二个匹配分支中使用它！ - Valéry

哦！那会教训我不要仅仅扫描和做出假设！ - Peter Hall

Answer 1

你可以使用两个技巧来使其工作，这些技巧在代码中有解释。

use std::mem;

enum Tree<'a> {
    Branch(Box<[Tree<'a>; 2]>),
    Leaf(&'a mut[f32]),
    Placeholder, // it's not very nice hack, but it's required for mem::replace
}

impl<'a> Tree<'a> {
    fn split(&mut self, max: usize) {
        let mut needs_split = false;
        match self {
            &mut Tree::Branch(ref mut trees) => {
                trees[0].split(max);
                trees[1].split(max);
            },
            &mut Tree::Leaf(ref mut leaf) if leaf.len() > max => {
                // Postpone modification of *self. We can't do it now while
                // a part of *self is borrowed
                needs_split = true;
            },
            _ => {}
        }
        if needs_split {
            // move *self into cself, to be able to
            // deconstruct content, while keeping *self not borrowed
            let cself = mem::replace(self, Tree::Placeholder);
            if let Tree::Leaf(leaf) = cself {
                let mid = leaf.len() / 2;
                let (l, r) = leaf.split_at_mut(mid);
                let trees = [Tree::Leaf(l), Tree::Leaf(r)];
                *self = Tree::Branch(Box::new(trees));
            } else {
                unreachable!()
            }
        }
    }
}

- red75prime

---

感谢您提供有用（且安全！）的技术。 - Valéry

Answer 2

我不确定如何修复整个案例，但我可能能够指导您正确的方向。首先，您需要明确self的生命周期：

fn split(&'a mut self, max: usize)

下一个问题是非穷尽匹配；目前可以轻松避免这种情况，使用以下基本情况即可：

_ => unimplemented!()

现在的问题是，在第一个匹配分支中，你可变地借用了trees两次；这可以通过使用循环来解决：

&mut Tree::Branch(ref mut trees) => {
    for tree in trees.iter_mut() {
        tree.split(max);
    }
}

现在你有：

error[E0506]: cannot assign to `*self` because it is borrowed
  --> <anon>:18:17
   |
14 |             &mut Tree::Leaf(ref mut leaf) if leaf.len() > max => {
   |                             ------------ borrow of `*self` occurs here
...
18 |                 *self = Tree::Branch(Box::new(trees));
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `*self` occurs here

这可以通过不在匹配分支中解构Leaf并使用一个辅助函数来避免：

impl<'a> Tree<'a> {
    fn get_trees(&'a mut self, max: usize) -> Option<[Tree<'a>; 2]> {
        if let &mut Tree::Leaf(ref mut leaf) = self {
            if leaf.len() > max {
                let mid = leaf.len() / 2;
                let (l, r) = leaf.split_at_mut(mid);
                Some([Tree::Leaf(l), Tree::Leaf(r)])
            } else {
                None
            }
        } else {
            None
        }
    }
}

并且

&mut Tree::Leaf(_) => {
    let trees = self.get_trees(max).unwrap(); // safe (under a valid match arm)
    *self = Tree::Branch(Box::new(trees));
}

现在出现了一个更大的问题，因为在借用时无法对 self 进行赋值。我会考虑使其可 Clone（并基于 self 的副本创建 trees），但在你的情况下它无法自动派生；也许其他人会有更好的想法。

在 Rust playground 中查看完整代码

- ljedrz