从ZOJ的PokerHands谈到Rust的生命周期 | Peanuts' Blog

从ZOJ的PokerHands谈到Rust的生命周期

前言

在本篇博客分为两个部分:你将会看到关于Rust生命周期(lifetime)的讨论,对于ZOJ1111.PokerHands的解答将会尽可能的缩短(毕竟不是ACM选手解答也不那么全面就不献丑了)

解题

起因

昨天在交流群里闲聊的时候,看到有人有偿求助这道题CPS506 - Assignment的Rust实现,简单的搜了一下题,发现和ZOJ的1111.PokerHands基本类似,部分条件更改之后加大了点难度,在网上搜索对应的题解,发现有思路,也不是太难(感觉自己飘了),就是模拟题,分九种情况,然后最后加以辅助判断。假如用普通的语言,问题当然是不大的,但是在Rust里面还是有点小坑的。

题解

简单说下解题思路:

题目描述:这道题要求比较两手牌的大小。每手牌都有5张牌组成,牌的大小的定义如下,首先确定这组牌的所属种类是下面哪一种(若同属同一种类,则根据该分类后面的比较规则继续比较,所属种类越靠后牌越大)。
● High Card:杂牌(不属于下面任何一种)。根据牌从大到小的顺序依次比较。
● Pair:有一对,加3张杂牌组成。先比较对的大小,再从大到小的顺序比较杂牌。
● Two Pairs:有两对,加1帐杂牌。先从大到小比较对的大小,再比较杂牌。
● Three of a Kind:有3张值相同的牌。比较这个值即可。
● Straingt:一条龙。即5张牌连续。比较最大的一张牌即可。
● Flush:清一色。即5张牌花色相同。和杂牌一样比较。
● Full House:3张值相同的牌,加上一对。比较三张相同的值即可。
● Four of a kind:有4张牌相同,即相当于一副“炸弹”。
● Straight flush:同花顺。即5张牌花色相同,并且连续。例如同花色的34567

简单模拟即可,加以辅助数组判断,这里给出参考题解,这些问题都很正常,但是Rust部分题目要求却有点问题:

Rust requirements
In a single Rust file called Poker.rs, write a function called deal that accepts an array of integers as an argument and returns the winning hand. In Rust, the typing of the input argument and the return value are very important. Rust will NOT implicitly convert anything for you, so pay extra attention to this. The usage of the deal function must be as follows:

let perm:[u32;10] = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
let winner:[&str;5] = deal(perm);

Your deal function should accept an array of 10 unsigned integers, and your deal function
should return an array of five string slices. The strings should be formatted in the same way
as all previous assignments.

Your submission should not include a main() function. Our tester will implement main().

注意这里的返回值[&str;5],和普通的String不同,这里要求返回一个引用类型的str,但是在Rust中会有一个生命周期的检查,假如你要在deal()内构建临时字符串,最后返回对应的引用,熟悉Rust的应该知道这是不可能的,所以只能采取别的措施,对,就是unsafe

生命周期和引用有效性

注:以下部分内容来自《The Rust Programming Language》

借用检查器

因为borrow checker的存在,它会检查引用两端的作用域从而保证所有的引用都是有效的,就像下面一样:

1
2
3
4
5
6
7
8
9
10
{
let r; // ---------+-- 'a
// |
{ // |
let x = 5; // -+-- 'b |
r = &x; // | |
} // -+ |
// |
println!("r: {}", r); // |
} // ---------+

在上述的代码中因为x的存活作用域小于r,在释放掉x之后,r便成为了垂悬引用,Rust为了杜绝这种情况,在编译器便拒绝,并给出提示,这极大地保证了运行时的安全性。

生命周期注解

1
2
3
4
5
6
7
fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
if x.len() > y.len() {
x
} else {
y
}
}

在上面的代码中,形如'a的标识即为生命周期注解。

现在函数签名表明对于某些生命周期 ‘a,函数会获取两个参数,他们都是与生命周期 ‘a 存在的一样长的字符串 slice。函数会返回一个同样也与生命周期 ‘a 存在的一样长的字符串 slice。这就是我们告诉 Rust 需要其保证的契约。记住通过在函数签名中指定生命周期参数时,我们并没有改变任何传入后返回的值的生命周期。而是指出任何不遵守这个协议的传入值都将被借用检查器拒绝。注意 longest 函数并不需要知道 x 和 y 具体会存在多久,而只需要知道有某个可以被 ‘a 替代的作用域将会满足这个签名。

当在函数中使用生命周期注解时,这些注解出现在函数签名中,而不存在于函数体中的任何代码中。这是因为 Rust 能够分析函数中代码而不需要任何协助,不过当函数引用或被函数之外的代码引用时,让 Rust 自身分析出参数或返回值的生命周期几乎是不可能的。这些生命周期在每次函数被调用时都可能不同。这也就是为什么我们需要手动标记生命周期。

当具体的引用被传递给 longest 时,被 ‘a 所替代的具体生命周期是 x 的作用域与 y 的作用域相重叠的那一部分。换一种说法就是泛型生命周期 ‘a 的具体生命周期等同于 x 和 y 的生命周期中较小的那一个。因为我们用相同的生命周期参数 ‘a 标注了返回的引用值,所以返回的引用值就能保证在 x 和 y 中较短的那个生命周期结束之前保持有效。

回到PokerHands

题目中需要我们构建一个deal()函数:

1
2
3
fn deal(perm: [u32;10]) -> [&str;5] {
/*code*/
}

但在这里会报一个错误:

1
2
3
4
5
6
7
error[E0106]: missing lifetime specifier
--> src/main.rs:198:26
|
198 | fn deal(perm:[u32;10])->[&str;5]{
| ^ help: consider giving it an explicit bounded or 'static lifetime: `&'static`
|
= help: this function's return type contains a borrowed value with an elided lifetime, but the lifetime cannot be derived from the arguments

加上'static很简单,但是要如何构建出一个生命周期为'staticstr呢,这在一个局部函数空间里显然是不可能的。除非:

  • 直接打表,列举出52种常量字符串
  • 使用Box::leak()

Box::leak():Consumes and leaks the Box, returning a mutable reference, &’a mut T. Note that the type T must outlive the chosen lifetime ‘a. If the type has only static references, or none at all, then this may be chosen to be ‘static.

使用第一种方法容易理解,但是操作有点麻烦,也许可以使用macros优化代替,但是这并不是一个聪明的方法。第二种方法,符合我们预期“构造字符串并返回”的初衷,但是还隐含了一个问题,那就是内存回收问题,为了避免泄露,必须使用Box::from_raw()处理对应的引用,然而,这个方法却是unsafe的,关于unsafe在社区引起的轩然大波想必不用多说,actix的作者就因为大量的unsafe操作被社区诟病,最终弃坑。之前在Rust的标准库中也发现了使用unsafe的操作,这些都动摇了Rust的安全性。突然想起来个趣事,刘雨培昨天又因为double free问题嘲讽了Rust。

附录

CPS506 - Assignment