讨论下链表的 Drop 引申出的关于原理，语法，编码的几个问题，应该可以作为面试题。

viruscamp 发表于 2021-10-08 22:27

相信大家都看过 Learn Rust With Entirely Too Many Linked Lists ，其中 An Ok Stack 的 Drop 如下：

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

为什么要写 impl Drop ？不写能编译过吗？不写会出什么问题吗？
在同样的 List<T> 上，实现第二种 Drop (空的drop函数)，使得不同的 T 类型可以选择不同的 Drop。
能不能编写代码并运行，来证明问题1的答案？如果要求程序不能 panic 呢？只需要提出思路就可以。
在下面测试函数模版基础上，写两个测试函数，实现问题3的答案。

#[test]
fn test_drop() {
    struct Item(i32);
    // 写点啥来选择 Drop 实现
    // 写点其他帮助代码
    let mut list = List::new();
    list.push(Item(1));
    list.push(Item(2));
    drop(list);
    // 写点 assert 来证明你说的
}

评论区

写评论

uno 2021-10-12 09:27

哪用那么麻烦，直接asm打印栈指针不就行了嘛

--
👇

应该没有人能够脱离 IDE 写出来吧。用到了 crate backtrace ， thread_local 的 Vec 等。

作者 viruscamp 2021-10-11 19:55

我来说下自己的答案:

为什么要写 impl Drop ？不写能编译过吗？不写会出什么问题吗？
1.1 写循环实现的impl Drop是为了不用自动实现的递归 drop
1.2 不写这个循环的 drop 编译通过是没问题的
1.3 递归 drop 在 List 元素少的情况下运行也没问题。但元素较多时，很容易因为递归调用层次过深，导致调用栈爆栈，即 stackoverflow 。简单的说调用栈最大占用，等比于元素数量。
在同样的 List<T> 上，实现第二种 Drop (空的drop函数)，使得不同的 T 类型可以选择不同的 Drop。

#![feature(specialization)]
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}
pub trait LinkedStackRecursionDrop {}
impl<T: LinkedStackRecursionDrop> Drop for LinkedStack<T> {
    fn drop(&mut self) {}
}

这题问的是 rust 语法, 偏特化。目前 stable 还不能用。

能不能编写代码并运行，来证明问题1的答案？如果要求程序不能 panic 呢？只需要提出思路就可以。
3.1 简单的证明方法，就是选择空的Drop实现，创建List然后Drop，逐渐增大元素数量

#[test]
//#[should_panic] // STATUS_STACK_OVERFLOW 用 should_panic 抓不到
#[ignore] // 只能忽略，手动单独指定运行来演示
fn recursion_drop_stackoverflow() {
    struct I(usize);
    impl LinkedStackRecursionDrop for I {}

    fn test(n: usize) {
        let mut list = List::new();
        for i in 0..n {
            list.push(I(i))
        }
        println!("List size={} created ok", n);
    }

    let mut n: usize = 512;
    loop {
        test(n);
        println!("List size={} dropped ok", n);
        n = n * 2;
    }
}

结果如下

......
List size=8192 created ok
List size=8192 dropped ok
List size=16384 created ok

thread 'linked_stack::test::recursion_drop_stackoverflow' has overflowed its stack
error: test failed, to rerun pass '-p too-many-linked-list --bin too-many-linked-list'

Caused by:
  process didn't exit successfully: `too_many_linked_list-4dd1e07ffe057a64.exe linked_stack::test::recursion_drop_stackoverflow --exact --nocapture --ignored` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)

3.2 证明对于 recursion_drop 函数调用最大层次会随着元素数量增多而增加
证明对于 non_recursion_drop 函数调用最大层次不管元素数量始终不变
对我们的元素类型 struct I(i32); 对其

impl Drop for I {
    fn drop(&mut self) {
        //记录函数调用层次
    }
}

然后我们只需要 push 两个元素，再 drop(list) ，比较记录下的两个函数调用层次

应该没有人能够脱离 IDE 写出来吧。用到了 crate backtrace ， thread_local 的 Vec 等。

Bai-Jinlin 2021-10-09 18:35

不写drop元素一多drop准保stack overflow

--
👇
Grobycn: 不写也可以编译，并且没有什么问题，因为用的是Box。

Grobycn 2021-10-09 17:35

不写也可以编译，并且没有什么问题，因为用的是Box。

Bai-Jinlin 2021-10-09 13:24

没看懂你在问什么，说到底这不就是不自己实现drop默认情况下链表就会递归drop爆栈的问题吗？

1 共 5 条评论, 1 页