7.2 栈上分配的链表
原文链接: https://rust-unofficial.github.io/too-many-lists/infinity-stack-allocated.html
本书 largely 聚焦堆分配链表，因为最常见实用，但不必须堆分配。堆分配 nice 因为动态分配内存容易。栈分配在这方面 less friendly——像 C 的 alloca widely regarded 为 Very Cursed And Problematic。
所以用简单办法在栈上分配：调函数拿更大栈帧！Very silly 但也 genuinely practical。经常做，可能甚至没当成链表！
递归时，把当前步 state 的指针传给下一步。若指针本身是 state 的一部分，就创建了栈分配链表！
当然我们在书silly部分，要 silly 地做：让链表当 star，用户代码 活在 callback 沼泽。Everybody loves nested callbacks！
List 类型只是带另一个 Node 引用的 Node：
1
2
3
4
| pub struct List<'a, T> {
pub data: T,
pub prev: Option<&'a List<'a, T>>,
}
|
只有一个操作 push：拿旧链表、当前节点 state、callback。新链表在 callback 里产生。也允许 callback 返回任意值，push 完成时返回：
1
2
3
4
5
6
7
8
9
10
| impl<'a, T> List<'a, T> {
pub fn push<U>(
prev: Option<&'a List<'a, T>>,
data: T,
callback: impl FnOnce(&List<'a, T>) -> U,
) -> U {
let list = List { data, prev };
callback(&list)
}
}
|
就这些！可以这样用：
1
2
3
4
5
6
7
8
9
| List::push(None, 3, |list| {
println!("{}", list.data);
List::push(Some(list), 5, |list| {
println!("{}", list.data);
List::push(Some(list), 13, |list| {
println!("{}", list.data);
})
})
})
|
Beautiful。😿
用户已能用 while-let 沿 prev 遍历，但 for fun 实现 iterator，usual 那种：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| impl<'a, T> List<'a, T> {
pub fn iter(&'a self) -> Iter<'a, T> {
Iter { next: Some(self) }
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.prev;
&node.data
})
}
}
|
测一下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #[cfg(test)]
mod test {
use super::List;
#[test]
fn elegance() {
List::push(None, 3, |list| {
assert_eq!(list.iter().copied().sum::<i32>(), 3);
List::push(Some(list), 5, |list| {
assert_eq!(list.iter().copied().sum::<i32>(), 5 + 3);
List::push(Some(list), 13, |list| {
assert_eq!(list.iter().copied().sum::<i32>(), 13 + 5 + 3);
})
})
})
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| > cargo test
running 18 tests
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::basics ... ok
test fifth::test::miri_food ... ok
test first::test::basics ... ok
test second::test::into_iter ... ok
test fourth::test::peek ... ok
test fourth::test::into_iter ... ok
test second::test::iter_mut ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok
test silly1::test::walk_aboot ... ok
test silly2::test::elegance ... ok
test second::test::peek ... ok
test third::test::iter ... ok
test result: ok. 18 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out;
|
这时你可能 wonder「hey 能 mutate 节点里的 data 吗？」。Maybe！试试让链表用可变引用而非共享：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| pub struct List<'a, T> {
pub data: T,
pub prev: Option<&'a mut List<'a, T>>,
}
pub struct Iter<'a, T> {
next: Option<&'a List<'a, T>>,
}
impl<'a, T> List<'a, T> {
pub fn push<U>(
prev: Option<&'a mut List<'a, T>>,
data: T,
callback: impl FnOnce(&mut List<'a, T>) -> U,
) -> U {
let mut list = List { data, prev };
callback(&mut list)
}
pub fn iter(&'a self) -> Iter<'a, T> {
Iter { next: Some(self) }
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.prev.as_ref().map(|prev| &**prev);
&node.data
})
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| > cargo test
error[E0521]: borrowed data escapes outside of closure
--> src\silly2.rs:47:32
|
46 | List::push(Some(list), 13, |list| {
| ----
| |
| `list` declared here, outside of the closure body
| `list` is a reference that is only valid in the closure body
47 | assert_eq!(list.iter().copied().sum::<i32>(), 13 + 5 + 3);
| ^^^^^^^^^^^ `list` escapes the closure body here
error[E0521]: borrowed data escapes outside of closure
--> src\silly2.rs:45:28
|
44 | List::push(Some(list), 5, |list| {
| ----
| |
| `list` declared here, outside of the closure body
| `list` is a reference that is only valid in the closure body
45 | assert_eq!(list.iter().copied().sum::<i32>(), 5 + 3);
| ^^^^^^^^^^^ `list` escapes the closure body here
<ad infinitum>
|
Whelp。似乎不喜欢我们的 iterator。也许我们搞砸了？简化测试：
1
2
3
4
5
6
7
8
9
10
11
12
| #[test]
fn elegance() {
List::push(None, 3, |list| {
assert_eq!(list.data, 3);
List::push(Some(list), 5, |list| {
assert_eq!(list.data, 5);
List::push(Some(list), 13, |list| {
assert_eq!(list.data, 13);
})
})
})
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| > cargo test
error[E0521]: borrowed data escapes outside of closure
--> src\silly2.rs:46:17
|
44 | List::push(Some(list), 5, |list| {
| ----
| |
| `list` declared here, outside of the closure body
| `list` is a reference that is only valid in the closure body
45 | assert_eq!(list.data, 5);
46 | / List::push(Some(list), 13, |list| {
47 | | assert_eq!(list.data, 13);
48 | | })
| |______^ `list` escapes the closure body here
error[E0521]: borrowed data escapes outside of closure
--> src\silly2.rs:44:13
|
42 | List::push(None, 3, |list| {
| ----
| |
| `list` declared here, outside of the closure body
| `list` is a reference that is only valid in the closure body
43 | assert_eq!(list.data, 3);
44 | / List::push(Some(list), 5, |list| {
45 | | assert_eq!(list.data, 5);
46 | | List::push(Some(list), 13, |list| {
47 | | assert_eq!(list.data, 13);
48 | | })
49 | | })
| |______________^ `list` escapes the closure body here
|
Hmm 还是 hot garbage。
问题是链表 accidentally(😉) 依赖* variance*。Variance 很复杂，简化看：
每个链表包含指向与自己完全相同类型的 List 的引用。从最内层看，所有链表都用与它相同 lifetime，但这* objectively* 错：每个节点严格比下一个活得更长，因为 literally 在嵌套 scope 里！
那……为什么共享引用时编译过？因为很多情况下编译器知道「活太久」也 safe！把 list 的引用塞进下一个时，编译器 quietly「缩小」lifetime 以 fit 新 list 期望。这种 lifetime 缩小就是 variance。
和有继承的语言里把 Cat 传 Animal（Cat 的超类型）预期位置一样。直觉上 Cat 当 Animal fine，因为 Cat 只是 Animal and more。暂时忘记「and more」 fine，对吧？
Similarly，更大 lifetime 只是更小 lifetime and more。这里忘记「and more」也 fine！
但你现在在 wonder：那可变引用版为什么不行！？
Well，variance 不总 safe。若代码能编译，可以写 use-after-free：
1
2
3
4
5
6
7
8
9
10
| List::push(None, 3, |list| {
List::push(Some(list), 5, |list| {
List::push(Some(list), 13, |list| {
// 哈哈所有 lifetime 相同，编译器会
// 让我重写 parent 持有对自己的可变引用！
// 我要制造所有 use-after-free！！
*list.prev.as_mut().unwrap().prev = Some(list);
})
})
})
|
忘记细节的问题是别处可能记得并 expect 仍为真。引入mutation 后这是 very big problem。不小心的话，不记得「and more」的代码可能以为能往「记得」并expect「and more」还在的地方写。
用继承说：这代码必须 illegal：
1
2
3
4
| let mut my_kitty = Cat; // 造一只 Cat（长 lifetime）
let animal: &mut Animal = &mut my_kitty; // 忘记它是 Cat（缩短 lifetime）
*animal = Dog; // 写一只 Dog（短 lifetime）
my_kitty.meow(); // 会喵喵的狗！（Use After Free）
|
所以可以缩短可变引用 lifetime，但开始nesting 就变「invariant」，不能再缩短。
具体 &mut &'big mut T 不能转成 &mut &'small mut T，'big 大于 'small。更形式化，&'a mut T 对 'a covariant，对 T invariant。
Fun fact：Java specifically 允许这类事，但运行时检查防止会喵喵的狗。
那怎么 mutate data？用 interior mutability！告诉编译器只想 mutate data、不动引用。
revert 共享引用版，新测试用 Cell：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #[test]
fn cell() {
use std::cell::Cell;
List::push(None, Cell::new(3), |list| {
List::push(Some(list), Cell::new(5), |list| {
List::push(Some(list), Cell::new(13), |list| {
// 把链表中每个值乘以 10
for val in list.iter() {
val.set(val.get() * 10)
}
let mut vals = list.iter();
assert_eq!(vals.next().unwrap().get(), 130);
assert_eq!(vals.next().unwrap().get(), 50);
assert_eq!(vals.next().unwrap().get(), 30);
assert_eq!(vals.next(), None);
assert_eq!(vals.next(), None);
})
})
})
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| > cargo test
running 19 tests
test fifth::test::into_iter ... ok
test fifth::test::basics ... ok
test fifth::test::iter_mut ... ok
test fifth::test::iter ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test second::test::into_iter ... ok
test first::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fifth::test::miri_food ... ok
test silly2::test::cell ... ok
test third::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test silly1::test::walk_aboot ... ok
test silly2::test::elegance ... ok
test third::test::basics ... ok
test second::test::iter ... ok
test result: ok. 19 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out;
|
Easy as recursive pie! ✨