< 返回版块

linsinn 发表于 2021-03-25 19:22

Tags:borrow check

在解决leetcode problem这个问题时。很疑惑编译器为什么会报错。

报了个重复borrow tail的错,但是在if let Some语句块之后,tail不是没有被borrow了吗?

impl Solution {
	pub fn delete_duplicates(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
		let mut nil = Box::new(ListNode::new(-1));
		if let Some(mut node) = head.take() {
			// 添加第一个节点
			head = node.next.take();
			nil.next = Some(node);
		}

		let mut tail = &mut nil.next;
		while let Some(mut node) = head.take() {
			head = node.next.take();
			if let Some(elem) = tail {
				// 如果与尾节点值不同,则添加
				if elem.val != node.val {
					elem.next = Some(node);
					tail = &mut elem.next;
				}
			}
		}
		nil.next
	}
}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

评论区

写评论
johnmave126 2021-03-26 22:39

我说的是修正时会出的问题。你这个编译不了的主要原因是,tail = &mut elem.next是条件性的。目前的borrow checker还不完善,有这样的认知

  1. let mut tail = &mut nil.next;: nil.next有一个mutable borrow
  2. if let Some(elem) = tail: tail也被mutable borrow了
  3. if elem.val != node.val {}: borrow checker不完善,tail = &mut elem.next;是条件性执行的,borrow checker无法判断第2步的borrow的生命周期,只能延长到第1步borrow的生命周期,于是覆盖了整个while,造成了错误。

当然,这code没有任何问题,只是borrow checker不够好

在修正的时候,最直观的想法是:

let mut tail = &mut nil.next;
while let Some(mut node) = head.take() {
    head = node.next.take();
    let tail_ = tail;
    if let Some(elem) = tail_ {
        if elem.val != node.val {
            elem.next = Some(node);
            tail = &mut elem.next;
        } else {
            // cannot borrow
            tail = tail_;
        }
    } else {
        tail = tail_;
    }
}

这就到了我说的NLL不够完善,在标注cannot borrow那里无法判断elem已经使用完毕,所以这个修法不太行。

--
👇
linsinn: 你不是说elem会一直借到if结束吗,那之后tail不是没有被任何变量引用,为何在while的下一轮会报错?如果把while改成if则编译通过,但如果在之后引用tail则也会报错。

作者 linsinn 2021-03-26 12:19

你不是说elem会一直借到if结束吗,那之后tail不是没有被任何变量引用,为何在while的下一轮会报错?如果把while改成if则编译通过,但如果在之后引用tail则也会报错。

		if let Some(mut node) = head.take() {
			head = node.next.take();
			if let Some(ref mut elem) = tail {
				// update the tail if the current node val not equals to the tail val
				if elem.val != node.val {
					elem.next = Some(node);
					tail = &mut elem.next;
				}
			}
		}
		println!("{:?}", tail);

--
👇
johnmave126

johnmave126 2021-03-26 08:51

目前borrow checker无法断言在条件性重新bind一个mutable reference的时候,前一个mutable reference的borrow会被释放

几个例子: stackoverflow 1

stackoverflow 2

解决方法就是在重新bind之前把ownership转移走

let mut tail = nil.next.as_mut();
while let Some(mut node) = head.take() {
    head = node.next.take();
    if let Some(elem) = tail.take() {
        if elem.val != node.val {
            elem.next = Some(node);
            tail.replace(elem.next.as_mut().unwrap());
        } else {
            tail.replace(elem);
        }
    }
}

目前borrow checker还不支持NLL所以直接把&mut转来转去的很多操作不可行,主要是if let Some(elem) = tail这里的elem会一直借到if结束。等以后有NLL了这个代码会好写很多。

1 共 3 条评论, 1 页