< 返回版块

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

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

相信大家都看过 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();
        }
    }
}
  1. 为什么要写 impl Drop ? 不写能编译过吗? 不写会出什么问题吗?

  2. 在同样的 List<T> 上,实现第二种 Drop (空的drop函数),使得不同的 T 类型可以选择不同的 Drop。

  3. 能不能编写代码并运行,来证明问题1的答案?如果要求程序不能 panic 呢?只需要提出思路就可以。

  4. 在下面测试函数模版基础上,写两个测试函数,实现问题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打印栈指针不就行了嘛

--
👇

  1. 应该没有人能够脱离 IDE 写出来吧。用到了 crate backtrace , thread_local 的 Vec 等。
作者 viruscamp 2021-10-11 19:55

我来说下自己的答案:

  1. 为什么要写 impl Drop ? 不写能编译过吗? 不写会出什么问题吗?
    1.1 写循环实现的impl Drop是为了不用自动实现的递归 drop
    1.2 不写这个循环的 drop 编译通过是没问题的
    1.3 递归 drop 在 List 元素少的情况下运行也没问题。但元素较多时,很容易因为递归调用层次过深,导致调用栈爆栈,即 stackoverflow 。简单的说调用栈最大占用,等比于元素数量。

  2. 在同样的 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. 能不能编写代码并运行,来证明问题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) ,比较记录下的两个函数调用层次

  1. 应该没有人能够脱离 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 页