I am still quite new to the advanced topics in rust, but for context, I am trying to implement a generic quadtree in rust.
With the method find_mut(&mut self,x,y) I want to traverse the quadtree to find the lowermost subtree containing that coordinate and return a mutable reference of it.

四叉树 struct

pub struct QuadTree<T> {
    x: i32,
    y: i32,
    dx: i32,
    dy: i32,
    leaf: bool,
    subtrees: [Option<Box<Self>>; 4],
    value: Option<T>,
}

方法和函数

fn find_mut(&mut self, x: i32, y: i32) -> Result<&mut Self, &mut Self> {
    let mut current = self;
    loop {
        // If we've arrived at a leaf return it as Ok
        if current.leaf { // First borrow occurs here for some reason
            return Ok(current);
        }
        // Getting the subtree that contains our coordinate
        match current.mut_subtree_at(x, y) {
            // Go a level deeper
            Some(child) => current = child,
            // Return an Err containing the lowest subtree that is sadly not a leaf
            None => return Err(current),
        }
    }
}

fn subtree_id<'a>(&'a self, x: i32, y: i32) -> usize {
    let mut child_id = 0;
    if x >= self.x {
        child_id += 1;
    }
    if y >= self.y {
        child_id += 2;
    }
    child_id
}

#[inline(always)]
fn mut_subtree_at(&mut self, x: i32, y: i32) -> Option<&mut Self> {
    self.subtrees[self.subtree_id(x, y)].as_deref_mut()
}

误差率

error[E0499]: cannot borrow `*current` as mutable more than once at a time
   --> src/quadtree.rs:128:36
    |
115 |     fn find_mut(&mut self, x: i32, y: i32) -> Result<&mut Self, &mut Self> {
    |                 - let's call the lifetime of this reference `'1`
...
121 |                 return Ok(current);
    |                        ----------- returning this value requires that `*current` is borrowed for `'1`
...
124 |             match current.mut_subtree_at(x, y) {
    |                   ---------------------------- first mutable borrow occurs here
...
128 |                 None => return Err(current),
    |                                    ^^^^^^^ second mutable borrow occurs here

你将如何处理这个问题.我错过了borrow 可变引用和生命周期的方式吗?

推荐答案

虽然不是很理想,但下面是一个可以编译的递归版本,但需要查询mut_subtree_at两次:

pub struct QuadTree<T> {
    x: i32,
    y: i32,
    dx: i32,
    dy: i32,
    leaf: bool,
    subtrees: [Option<Box<Self>>; 4],
    value: Option<T>,
}

impl<T> QuadTree<T> {
    fn find_mut(&mut self, x: i32, y: i32) -> Result<&mut Self, &mut Self> {
        if self.leaf {
            Ok(self)
        } else {
            if self.mut_subtree_at(x, y).is_some() {
                // Go a level deeper
                self.mut_subtree_at(x, y).unwrap().find_mut(x, y)
            } else {
                // Return an Err containing the lowest subtree that is sadly not a leaf
                Err(self)
            }
        }
    }

    fn subtree_id<'a>(&'a self, x: i32, y: i32) -> usize {
        let mut child_id = 0;
        if x >= self.x {
            child_id += 1;
        }
        if y >= self.y {
            child_id += 2;
        }
        child_id
    }

    #[inline(always)]
    fn mut_subtree_at(&mut self, x: i32, y: i32) -> Option<&mut Self> {
        self.subtrees[self.subtree_id(x, y)].as_deref_mut()
    }
}

根据我的理解,这是可行的,因为.is_some()返回bool,这是一个拥有的值,因此Rust可以证明,在Err(self)的时候,不再有对self的引用.

似乎同样的原则也适用于迭代解决方案:

pub struct QuadTree<T> {
    x: i32,
    y: i32,
    dx: i32,
    dy: i32,
    leaf: bool,
    subtrees: [Option<Box<Self>>; 4],
    value: Option<T>,
}

impl<T> QuadTree<T> {
    fn find_mut(&mut self, x: i32, y: i32) -> Result<&mut Self, &mut Self> {
        let mut current = self;
        loop {
            // If we've arrived at a leaf return it as Ok
            if current.leaf {
                return Ok(current);
            }
            // Getting the subtree that contains our coordinate
            if current.mut_subtree_at(x, y).is_some() {
                // Go a level deeper
                current = current.mut_subtree_at(x, y).unwrap()
            } else {
                // Return an Err containing the lowest subtree that is sadly not a leaf
                return Err(current);
            }
        }
    }

    fn subtree_id<'a>(&'a self, x: i32, y: i32) -> usize {
        let mut child_id = 0;
        if x >= self.x {
            child_id += 1;
        }
        if y >= self.y {
            child_id += 2;
        }
        child_id
    }

    #[inline(always)]
    fn mut_subtree_at(&mut self, x: i32, y: i32) -> Option<&mut Self> {
        self.subtrees[self.subtree_id(x, y)].as_deref_mut()
    }
}

为了获得更好的性能(也就是说,如果您不想调用mut_subtree_at两次),您必须覆盖borrow 判断器,因为这显然是一个误报.

幸运的是,有专门针对您遇到的问题编写的polonius-the-crab箱,它以安全可靠的方式隐藏了不安全的代码.

以下是我使用polonius-the-crab的第一个工作版本:

use ::polonius_the_crab::prelude::*;
use polonius_the_crab::WithLifetime;

pub struct QuadTree<T> {
    x: i32,
    y: i32,
    dx: i32,
    dy: i32,
    leaf: bool,
    subtrees: [Option<Box<Self>>; 4],
    value: Option<T>,
}

impl<T> QuadTree<T> {
    fn find_mut(&mut self, x: i32, y: i32) -> Result<&mut Self, &mut Self> {
        type SelfRef<K> = dyn for<'lt> WithLifetime<'lt, T = &'lt mut QuadTree<K>>;

        let mut current = self;
        loop {
            // If we've arrived at a leaf return it as Ok
            if current.leaf {
                return Ok(current);
            }
            // Getting the subtree that contains our coordinate
            match polonius::<SelfRef<T>, _, _, _>(current, |current| {
                current.mut_subtree_at(x, y).ok_or(())
            }) {
                Ok(child) => {
                    // Go a level deeper
                    current = child;
                }
                Err((current, ())) => {
                    // Return an Err containing the lowest subtree that is sadly not a leaf
                    return Err(current);
                }
            }
        }
    }

    fn subtree_id<'a>(&'a self, x: i32, y: i32) -> usize {
        let mut child_id = 0;
        if x >= self.x {
            child_id += 1;
        }
        if y >= self.y {
            child_id += 2;
        }
        child_id
    }

    #[inline(always)]
    fn mut_subtree_at(&mut self, x: i32, y: i32) -> Option<&mut Self> {
        self.subtrees[self.subtree_id(x, y)].as_deref_mut()
    }
}

或者这个版本,因为它使用了Polonius的宏,所以更容易理解:

use ::polonius_the_crab::prelude::*;

pub struct QuadTree<T> {
    x: i32,
    y: i32,
    dx: i32,
    dy: i32,
    leaf: bool,
    subtrees: [Option<Box<Self>>; 4],
    value: Option<T>,
}

impl<T> QuadTree<T> {
    pub fn find_mut(&mut self, x: i32, y: i32) -> Result<&mut Self, &mut Self> {
        let mut current = self;
        while !current.leaf {
            // Getting the subtree that contains our coordinate.
            // If no subtree exists, return Err(current).
            current = current.mut_subtree_at(x, y)?;
        }
        // If we are at a leaf node with the coordinate, success!
        Ok(current)
    }

    fn subtree_id<'a>(&'a self, x: i32, y: i32) -> usize {
        let mut child_id = 0;
        if x >= self.x {
            child_id += 1;
        }
        if y >= self.y {
            child_id += 2;
        }
        child_id
    }

    #[inline(always)]
    fn mut_subtree_at(&mut self, x: i32, y: i32) -> Result<&mut Self, &mut Self> {
        let mut current = self;

        polonius!(
            |current| -> Result<&'polonius mut Self, &'polonius mut Self> {
                if let Some(child) = current.subtrees[current.subtree_id(x, y)].as_deref_mut() {
                    polonius_return!(Ok(child))
                }
            }
        );

        // Return the ownership of `self` back through the `Err()` value.
        // This in conjunction with the `polonius!()` macro resolves the
        // ownership problem.
        Err(current)
    }
}

Rust相关问答推荐

为什么要在WASM库中查看Rust函数需要`#[no_mangle]`?

什么是Rust惯用的方式来使特征向量具有单个向量项的别名?

限制未使用的泛型导致编译错误

当第二个`let`依赖于第一个`let()`时,如何在一行中有多个`let()`?

如何计算迭代器适配器链中过滤的元素的数量

如何将单个 struct 实例与插入器一起传递到Rust中的映射

将一个泛型类型转换为另一个泛型类型

完全匹配包含大小写的整数范围(&Q;)

根据掩码将 simd 通道设置为 0 的惯用方法?

如何使用 Bincode 在 Rust 中序列化 Enum,同时保留 Enum 判别式而不是索引?

Rust 中指向自身的引用如何工作?

我可以在 Rust 中 serde struct camel_case 和 deserde PascalCase

在 Bevy 项目中为 TextureAtlas 精灵实施 NearestNeighbor 的正确方法是什么?

当 T 不是副本时,为什么取消引用 Box 不会抱怨移出共享引用?

更好的方法来模式匹配带有 Rust 的窥视孔装配说明窗口?

从函数返回 u32 的数组/切片

为实现特征的所有类型实现显示

Rust 内联 asm 中的向量寄存器:不能将 `Simd` 类型的值用于内联汇编

如何在不设置精度的情况下打印浮点数时保持尾随零?

翻转布尔值的最快方法