<commit_before># Iter

Alright, let's try to implement Iter. This time we won't be able to rely on
List giving us all the features we want. We'll need to roll our own. The
basic logic we want is to hold a pointer to the current node we want to yield
next. Because that node may not exist (the list is empty or we're otherwise
done iterating), we want that reference to be an Option. When we yield an
element, we want to proceed to the current node's `next` node.

Alright, let's try that:

```rust ,ignore
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
        })
    }
}
```

```text
> 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
```

Oh god. Lifetimes. I've heard of these things. I hear they're a nightmare.

Let's try something new: see that `error[E0106]` thing? That's a compiler error
code. We can ask rustc to explain those with, well, `--explain`:

```text
> 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
...

```

That uh... that didn't really clarify much (these docs assume we understand
Rust better than we currently do). But it looks like we should add
those `'a` things to our struct? Let's try that.

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

```text
> 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
```

Alright I'm starting to see a pattern here... let's just add these little guys
to everything we can:

```rust ,ignore
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
        })
    }
}
```

```text
> 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`
```

Oh god. We broke Rust.

Maybe we should actually figure out what the heck this `'a` lifetime stuff
even means.

Lifetimes can scare off a lot of people because
they're a change to something we've known and loved since the dawn of
programming. We've actually managed to dodge lifetimes so far, even though
they've been tangled throughout our programs this whole time.

Lifetimes are unnecessary in garbage collected languages because the garbage
collector ensures that everything magically lives as long as it needs to. Most
data in Rust is *manually* managed, so that data needs another solution. C and
C++ give us a clear example what happens if you just let people take pointers
to random data on the stack: pervasive unmanageable unsafety. This can be
roughly separated into two classes of error:

* Holding a pointer to something that went out of scope
* Holding a pointer to something that got mutated away

Lifetimes solve both of these problems, and 99% of the time, they do this in
a totally transparent way.

So what's a lifetime?

Quite simply, a lifetime is the name of a region (\~block/scope) of code somewhere in a program.
That's it. When a reference is tagged with a lifetime, we're saying that it
has to be valid for that *entire* region. Different things place requirements on
how long a reference must and can be valid for. The entire lifetime system is in
turn just a constraint-solving system that tries to minimize the region of every
reference. If it sucessfully finds a set of lifetimes that satisfies all the
constraints, your program compiles! Otherwise you get an error back saying that
something didn't live long enough.

Within a function body you generally can't talk about lifetimes, and wouldn't
want to *anyway*. The compiler has full information and can infer all the
contraints to find the minimum lifetimes. However at the type and API-level,
the compiler *doesn't* have all the information. It requires you to tell it
about the relationship between different lifetimes so it can figure out what
you're doing.
<commit_msg>Fix typo<commit_after># Iter

Alright, let's try to implement Iter. This time we won't be able to rely on
List giving us all the features we want. We'll need to roll our own. The
basic logic we want is to hold a pointer to the current node we want to yield
next. Because that node may not exist (the list is empty or we're otherwise
done iterating), we want that reference to be an Option. When we yield an
element, we want to proceed to the current node's `next` node.

Alright, let's try that:

```rust ,ignore
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
        })
    }
}
```

```text
> 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
```

Oh god. Lifetimes. I've heard of these things. I hear they're a nightmare.

Let's try something new: see that `error[E0106]` thing? That's a compiler error
code. We can ask rustc to explain those with, well, `--explain`:

```text
> 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
...

```

That uh... that didn't really clarify much (these docs assume we understand
Rust better than we currently do). But it looks like we should add
those `'a` things to our struct? Let's try that.

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

```text
> 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
```

Alright I'm starting to see a pattern here... let's just add these little guys
to everything we can:

```rust ,ignore
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
        })
    }
}
```

```text
> 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`
```

Oh god. We broke Rust.

Maybe we should actually figure out what the heck this `'a` lifetime stuff
even means.

Lifetimes can scare off a lot of people because
they're a change to something we've known and loved since the dawn of
programming. We've actually managed to dodge lifetimes so far, even though
they've been tangled throughout our programs this whole time.

Lifetimes are unnecessary in garbage collected languages because the garbage
collector ensures that everything magically lives as long as it needs to. Most
data in Rust is *manually* managed, so that data needs another solution. C and
C++ give us a clear example what happens if you just let people take pointers
to random data on the stack: pervasive unmanageable unsafety. This can be
roughly separated into two classes of error:

* Holding a pointer to something that went out of scope
* Holding a pointer to something that got mutated away

Lifetimes solve both of these problems, and 99% of the time, they do this in
a totally transparent way.

So what's a lifetime?

Quite simply, a lifetime is the name of a region (\~block/scope) of code somewhere in a program.
That's it. When a reference is tagged with a lifetime, we're saying that it
has to be valid for that *entire* region. Different things place requirements on
how long a reference must and can be valid for. The entire lifetime system is in
turn just a constraint-solving system that tries to minimize the region of every
reference. If it successfully finds a set of lifetimes that satisfies all the
constraints, your program compiles! Otherwise you get an error back saying that
something didn't live long enough.

Within a function body you generally can't talk about lifetimes, and wouldn't
want to *anyway*. The compiler has full information and can infer all the
contraints to find the minimum lifetimes. However at the type and API-level,
the compiler *doesn't* have all the information. It requires you to tell it
about the relationship between different lifetimes so it can figure out what
you're doing.

{'fraction_non_alphanumeric': 0.10648777173913043, 'fraction_numerical': 0.012567934782608696, 'mean_word_length': 2.967991913746631, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 91, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7276390', 'n_tokens_mistral': 3685, 'n_tokens_neox': 3446, 'n_words': 1595}