Hoes of Tech

Conceptualization of Technology

Dive into Rust(1) - Iterator

大概三个月之前,这三个月,我一直在使用Rust。回想起来,在离开Object Pascal家族之后,过去五六年里也已经尝试了很多的新语言,不管是D,还是因为谷歌的名头而开始用的Go,又或者是Nim,Crystal或者Zimbu,都没能让我真正的满意,而OOC虽然在语法上让人十分舒服,但它使用了libGC,并且对多线程和Closure的支持并不到位。其实,在改进OOC的过程中,有人提出过给OOC加入RAII,并且尝试把一部分内容分配在了栈上,不过很可惜,OOC的编译器在设计当初并没有考虑这些事情,不到几个小时这种改进就遇到了问题。

在刚刚接触Rust的时候曾经写过一篇关于Rust的文章,里面阐述了我对Rust的第一印象——省心。把代码写出来,编译器就会指出所有的错误,在这几十天里,我明显感觉到在调试程序时莫名其妙的错误少多了——我还清楚的记得之前在OOC里因为一个Generics的bug导致ArrayList<T>里的元素过早被回收,结果就是程序有时候正常,有时候乱码,有时候Segmentation Fault,而这种问题在Rust里几乎不会出现。

当然,Rust这么做的代价就是语法上的繁杂。Rust的语法并不算复杂,大部分关键词的意义都很明确,也没有存在歧义的设计,然而说它繁杂却不为过,一个简单的例子就是在声明一个用到了Borrow的Struct时,编译器要求必须指明所有Borrow的Lifetime,因此定义和声明中就出现了大量的Lifetime标识符,同时,对于一个类型和它的Borrow,Trait是不能通用的,也就是说就算对一个类型实现了某个Trait,如果需要用到它的Borrow,那么还需要重新实现一次,然而在绝大多数情况下,Borrow的声明不过是对应类型的复制粘贴而已。虽然从安全性的角度来看,这么做是理所当然的,但至于为了安全性是不是值得作出这点牺牲就因人而异了。

好吧,对于Rust这种做法的争论已经够多了,这里也不需要再来一次,因此让我们结束这个话题,来看看Rust的方方面面。

An Easy Start

让我们先从一个尽可能简单的例子开始,假设有一个struct储存了一些数据,现在需要对它实现一个Iterator,不过这个Iterator有点特殊,struct里的数据需要按照一个函数index(t+1) = f(index(t))的顺序取出来。用代码来说,就像是这个样子:

struct MyIter<'a> {
    data: &'a [u8],
}

fn main() {
    let rdata = [10, 20, 1, 3, 9, 1, 1, 1, 1];
    let data = MyIter { data: &rdata };
    for i in data {
        println!("{}", i);
    }
}

下面需要对MyIter实现Iterator了,当然,为了实现Iterator我们需要一个Index来指示当前的位置。最直接的做法就是在MyIter里记录当前位置:

struct MyIter<'a> {
    data: &'a [u8],
    position: usize,
}

不过这么做是非常危险的,原因很简单,如果把position放进MyIter里,我们很难保证position总是正确的。position可以被除了Iterator之外的函数修改,并且在一次遍历完成之后还要想法法把position置0——这些都会导致Bug出现,因此在大部分程序里直接针对MyIter声明position并不是一个好办法。很自然的,我们可以把二者分开:

struct MyIter<'a> {
    data: &'a [u8],
}

struct Iter <'a>{
    iter: MyIter<'a>,
    position: usize,
}

impl<'a> IntoIterator for MyIter<'a>{
    type Item = u8;
    type IntoIter = Iter<'a>;

    fn into_iter(self) -> Self::IntoIter {
        MyIterIntoIterator {
            iter: self,
            position: 0,
        }
    }
}

impl<'a> Iterator for Iter<'a> {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        self.positoion = self.f(self.position);
        if self.position < self.iter.data.len() {
            Some(self.iter.data[self.position])
        } else {
            None
        }
    }
}

在这里,我们新定义了一个Iter,然后我们仅对Iter实现Iterator,这样,在每次遍历MyIter时,其实是对新创建的Iter进行遍历,这样就不需要担心position不够安全了。同时,在Rust中,for i in data这种类新的循环不但会被自动unwrap成基于Iterator.next的循环,如果data实现了IntoIteratorTrait那么编译器还会自动把data转换成data.into_iter()。因此,我们需要做的就是对MyIter实现IntoIterator,然后对Iter实现Iterator就够了。

到这里,最初的程序就已经可以运行了。不过这里还残留着一个问题,对比vec,对于一个vecfor each循环可以这么写:

let data = vec![0, 1, 3, 2, 5];
for i in data {
    // do your work
}

这种写法会消耗掉data,如果在循环之后试图使用data,则会出现use of moved variable错误。当我们不打算消耗掉data的时候,可以对data的borrow进行循环:

let data = vec![0, 1, 3, 2, 5];
for i in &data {
}

这样data仅仅是一个borrow,在循环结束后依然可以对data进行别的操作。返回到最初的MyIter例子中,现在没法对MyIter的borrow进行循环,因为&MyIter并没有实现IntoIteroter,也没有Iteroter。为了实现这个功能,我们还需要实现一个对Borrow的版本:

impl<'a> IntoIterator for &'a MyIter<'a> {
    type Item = u8;
    type IntoIter = MyIterIntoIteratorRef<'a>;

    fn into_iter(self) -> Self::IntoIter {
        MyIterIntoIteratorRef {
            iter: self,
            position: 0,
        }
    }
}

struct MyIterIntoIteratorRef<'a> {
    iter: &'a MyIter<'a>,
    position: usize,
}

impl<'a> Iterator for MyIterIntoIteratorRef<'a> {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        self.positoion = self.f(self.position);
        if self.position < self.iter.data.len() {
            Some(self.iter.data[self.position1])
        } else {
            None
        }
    }
}

在这里,仅仅是再之前的类型前面加上一个&而已,但很可惜,由于二者被当做不同的类型,所有相关的函数都得重新实现一遍,里面包括用于获得下一个index的self.f。再仔细考虑一下,如果我们还打算对&mut MyIter做循环的话,还要实现一个&mut MyIter的版本,然而这三个版本的代码几乎是相同的,但因为种种限制,我们却几乎无法作出更好的抽象。实际上,在标准库里每一个支持for each的类型也都实现了这三种Iterator。不过,需要注意的是,这里的例子仅仅是为了展示Iterator而有意采用了类似libstd里的写法,在实际应用当中,绝大多数情况下都没有必要自行实现这些内容,比如实际上&[T]已经实现了iter(&self),因此我们只需要在into_iter里直接调用iter()就足够了。