遍历

好吧,让我们试着实现Iter。这一次,我们将不能依靠List提供我们想要的所有功能。我 们需要靠我们自己。我们想要的基本逻辑是持有一个指向当前节点的指针,我们想要产生 下一个节点。因为这个节点可能不存在(列表是空的或者我们已经完成了迭代),我们希 望这个引用是一个 Option。当我们产出一个元素时,我们希望继续到当前节点的下一个 节点。

好吧,我们来试试:

pub struct Iter<T> {
    next: Option<&Node<T>>,
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.map(|node| &node) }
    }
}

impl<T> Iterator for Iter<T> {
    type Item = &T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &node);
            &node.elem
        })
    }
}
> cargo build

error[E0106]: missing lifetime specifier
  --> src/second.rs:72:18
   |
72 |     next: Option<&Node<T>>,
   |                  ^ expected lifetime parameter

error[E0106]: missing lifetime specifier
  --> src/second.rs:82:17
   |
82 |     type Item = &T;
   |                 ^ expected lifetime parameter

哦,上帝。生命周期。我听说过这些事情。我听说它们是一场恶梦。

让我们试试新的东西:看到那个error[E0106]的东西吗?那是一个编译器错误代码。我们可 以让rustc用--explain来解释这些:

> rustc --explain E0106
This error indicates that a lifetime is missing from a type. If it is an error
inside a function signature, the problem may be with failing to adhere to the
lifetime elision rules (see below).

Here are some simple examples of where you'll run into this error:

struct Foo { x: &bool }        // error
struct Foo<'a> { x: &'a bool } // correct

enum Bar { A(u8), B(&bool), }        // error
enum Bar<'a> { A(u8), B(&'a bool), } // correct

type MyStr = &str;        // error
type MyStr<'a> = &'a str; //correct
...

这......这并没有真正说明什么(这些文档假设我们比现在更了解Rust)。但看起来我们应该把 这些'a添加到我们的结构中去?让我们试试吧。

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}
> cargo build

error[E0106]: missing lifetime specifier
  --> src/second.rs:83:22
   |
83 | impl<T> Iterator for Iter<T> {
   |                      ^^^^^^^ expected lifetime parameter

error[E0106]: missing lifetime specifier
  --> src/second.rs:84:17
   |
84 |     type Item = &T;
   |                 ^ expected lifetime parameter

error: aborting due to 2 previous errors

好吧,我开始看到一个模式......让我们把这些小家伙添加到我们能做的所有事情中:

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> List<T> {
    pub fn iter(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &'a node) }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&'a mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &'a node);
            &'a node.elem
        })
    }
}
> cargo build

error: expected `:`, found `node`
  --> src/second.rs:77:47
   |
77 |         Iter { next: self.head.map(|node| &'a node) }
   |         ---- while parsing this struct        ^^^^ expected `:`

error: expected `:`, found `node`
  --> src/second.rs:85:50
   |
85 |             self.next = node.next.map(|node| &'a node);
   |                                                  ^^^^ expected `:`

error[E0063]: missing field `next` in initializer of `second::Iter<'_, _>`
  --> src/second.rs:77:9
   |
77 |         Iter { next: self.head.map(|node| &'a node) }
   |         ^^^^ missing `next`

哦,上帝。我们搞坏了Rust。

也许我们应该搞清楚这个'a生命周期到底是什么意思。

生命期会吓跑很多人,因为它是对我们从编程之初就知道并喜爱的东西的改变。到目前为止, 我们实际上已经成功地避开了生命期,尽管它们一直在我们的程序中纠缠不清。

生命期在垃圾收集语言中是不必要的,因为垃圾收集器会确保所有的东西都能神奇地活到它需 要的时间。Rust中的大多数数据都是人工管理的,所以这些数据需要另一种解决方案。C和 C++给了我们一个清晰的例子,如果你只是让人们在堆栈上拿指针去随机数据会发生什么:普 遍的不可管理的不安全。这可以粗略地分为两类错误:

  • 持有一个超出范围的东西的指针
  • 持有一个指向被改变的东西的指针

生命期可以解决这两个问题,而且99%的情况下,它们是以一种完全透明的方式进行的。

那么什么是生命期呢?

很简单,生命期是程序中某个区域(~块/范围)代码的名称。就是这样。当一个引用被标记为生 命期时,我们是说它必须对整个区域有效。不同的东西对一个引用必须和可以在多长时间内有 效提出了要求。整个生命期系统又只是一个约束解决系统,它试图最小化每个引用的区域。如果 它成功地找到了一组满足所有约束条件的生命期,你的程序就可以编译了!否则你就会得到一个 错误反馈,说什么东西的生命期不够长。

在一个函数体中,你一般不能谈论生命期,而且也不想谈论。编译器有完整的信息,可以推断出 所有的限制条件来找到最小的生命期。然而在类型和API层面,编译器并没有所有的信息。它需 要你告诉它不同生命期之间的关系,这样它才能弄清楚你在做什么。

原则上说,这些生命期也可以不写,但这样一来,检查所有的借用将是一个巨大的全程序分析 ,会产生令人难以置信的非本地错误。Rust的系统意味着所有的借用检查都可以在每个函数体中 独立完成,你的所有错误都应该是相当局部的(或者你的类型有错误的签名)。

但是我们以前也在函数签名中写过引用,而且很好!为什么?这是因为有一些情况非常普遍, Rust会自动为你挑选生命期。这就是寿命消除

特别地:

// Only one reference in input, so the output must be derived from that input
fn foo(&A) -> &B; // sugar for:
fn foo<'a>(&'a A) -> &'a B;

// Many inputs, assume they're all independent
fn foo(&A, &B, &C); // sugar for:
fn foo<'a, 'b, 'c>(&'a A, &'b B, &'c C);

// Methods, assume all output lifetimes are derived from `self`
fn foo(&self, &B, &C) -> &D; // sugar for:
fn foo<'a, 'b, 'c>(&'a self, &'b B, &'c C) -> &'a D;

那么,fn foo<'a>(&'a A)->&'a B是什么意思?在实践中,它的意思是,输入必须至少活得 与输出一样长。因此,如果你把输出保留很长一段时间,这将扩大输入必须有效的区域。一旦你 停止使用输出,编译器就会知道输入也可以变得无效了。

由于这个系统的设置,Rust可以确保没有东西会在释放之后被使用,而且在未完成的引用存在时 没有任何东西被改变。它只是确保这些约束条件都能得到解决。

好的。那么。Iter。

让我们回到没有生命期的状态:

pub struct Iter<T> {
    next: Option<&Node<T>>,
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.map(|node| &node) }
    }
}

impl<T> Iterator for Iter<T> {
    type Item = &T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &node);
            &node.elem
        })
    }
}

我们只需要在函数和类型的签名中添加生命期:

// Iter is generic over *some* lifetime, it doesn't care
pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

// No lifetime here, List doesn't have any associated lifetimes
impl<T> List<T> {
    // We declare a fresh lifetime here for the *exact* borrow that
    // creates the iter. Now &self needs to be valid as long as the
    // Iter is around.
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &node) }
    }
}

// We *do* have a lifetime here, because Iter has one that we need to define
impl<'a, T> Iterator for Iter<'a, T> {
    // Need it here too, this is a type declaration
    type Item = &'a T;

    // None of this needs to change, handled by the above.
    // Self continues to be incredibly hype and amazing
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &node);
            &node.elem
        })
    }
}

好吧,我想这次我们得到了它,你们都。

cargo build

error[E0308]: mismatched types
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.map(|node| &node) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

error[E0308]: mismatched types
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.map(|node| &node);
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&'a second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

(╯°□°)╯︵ ┻━┻

好的。所以。我们修复了我们的生命期错误,但现在我们得到了一些新的类型错误。

我们想存储&Node的,但我们得到的是&Box<Node>的。好吧,这很容易,我们只需 要在引用之前取消对Box的引用:

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &*node) }
    }
}

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.next.map(|node| &*node);
            &node.elem
        })
    }
}
cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0515]: cannot return reference to local data `*node`
  --> src/second.rs:77:43
   |
77 |         Iter { next: self.head.map(|node| &*node) }
   |                                           ^^^^^^ returns a reference to data owned by the current function

error[E0507]: cannot move out of borrowed content
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.map(|node| &*node) }
   |                      ^^^^^^^^^ cannot move out of borrowed content

error[E0515]: cannot return reference to local data `*node`
  --> src/second.rs:85:46
   |
85 |             self.next = node.next.map(|node| &*node);
   |                                              ^^^^^^ returns a reference to data owned by the current function

error[E0507]: cannot move out of borrowed content
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.map(|node| &*node);
   |                         ^^^^^^^^^ cannot move out of borrowed content

(ノಥ益ಥ)ノ ┻━┻

我们忘记了要as_ref,所以我们要把盒子移到map里,这意味着它将被丢弃,这意味着 我们的引用将被悬空:

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_ref().map(|node| &*node) }
    }
}

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.next.as_ref().map(|node| &*node);
            &node.elem
        })
    }
}
cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0308]: mismatched types
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.as_ref().map(|node| &*node) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

error[E0308]: mismatched types
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.as_ref().map(|node| &*node);
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&'a second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

😭

as_ref又增加了一层我们需要去除的间接性:

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_deref() }
    }
}

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.next.as_deref();
            &node.elem
        })
    }
}
cargo build

🎉 🎉 🎉

as_deref和as_deref_mut函数在Rust 1.40中已经稳定。在此之前,你需要做map(|node| &**node)map(|node| &mut**node)。你可能会想"哇,那个&**的东西真的很古怪",你没有错,但就像美 酒一样,Rust会随着时间的推移变得更好,我们不再需要这样做。通常情况下,Rust非常善于隐式地进 行这种转换,通过一个叫做解引用强制转换的过程,基本上它可以在你的代码中插入*,使其进行类 型检查。它可以做到这一点,因为我们有借用检查器来确保我们不会弄乱指针!

但是闭包同时结合了我们有一个Option<&T>而不是&T的情况,对它来说有点太复杂了,所以我们需 要通过显式的方式来帮助它。值得庆幸的是,根据我的经验,这种情况相当少见。

为了完整起见,我们可以涡轮鱼给它一个不同的提示:

    self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);

看,map是一个泛型函数:

pub fn map<U, F>(self, f: F) -> Option<U>

涡轮鱼,:<>,让我们告诉编译器我们认为这些泛型的类型应该是什么。在这个例子中 ::<&Node<T>, _>说 "它应该返回一个&Node<T>,而我不知道/不关心其他类型"。

这反过来又让编译器知道&node应该被应用于解引用强制转换,所以我们不需要手动应用所有这 些*!

但在这种情况下,我不认为这真的是一种改进,这只是一个薄薄的借口,来展示解引用强制转换和 有时有用的涡轮鱼。😅

让我们写一个测试,以确定我们没有拒绝它或任何东西:

#[test]
fn iter() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), Some(&1));
}
> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 5 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::peek ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured

全对。

最后,应该指出的是,我们实际上可以在这里应用生命期消除:

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_deref() }
    }
}

等同于:

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.as_deref() }
    }
}

更少的生命期!

或者,如果你不愿意"隐藏"一个结构包含一个生命期,你可以使用Rust 2018的“ 显式省略生命期”语法,'_

impl<T> List<T> {
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_deref() }
    }
}