Zero-copy tokenizer: `Parser<'a>`

The flagship problem of this track. It is the one that separates people who can write real Rust from people who can make the compiler stop shouting.

Build a whitespace tokenizer that allocates nothing per token — every token is a slice of the original input.

pub struct Parser<'a> { /* ... */ }

impl<'a> Parser<'a> {
    pub fn new(src: &'a str) -> Self;
    pub fn next_token(&mut self) -> Option<&'a str>;   // <- look hard at this
}

pub fn tokenize(src: &str) -> Vec<&str>;

tokenize splits on runs of whitespace (spaces, tabs, \n, \r), skipping leading and trailing whitespace, and returns the tokens in order. It must do so by driving a Parser — creating one, pulling tokens until None, and returning the collected Vec after the parser is gone.

The mistake, in full

Write next_token the natural way and elision rule 3 fills the return lifetime in for you from the receiver:

pub fn next_token(&mut self) -> Option<&str>
// means: fn next_token<'s>(&'s mut self) -> Option<&'s str>

That compiles. If you tested it by printing one token at a time, it would pass. And it is wrong, because it says every token is borrowed from the parser, which is a mutable borrow — so as long as you hold a token, the parser is frozen. Try to write the loop:

while let Some(token) = parser.next_token() {
    out.push(token);      // out now holds a borrow of `parser`
}                         // ...so the next call cannot borrow it again

error[E0499]: cannot borrow `parser` as mutable more than once at a time

You cannot even collect two tokens, let alone outlive the parser. The truth is that a token points into src, not into the parser — the parser is merely the thing holding the cursor. Saying so requires naming the struct’s own lifetime:

pub fn next_token(&mut self) -> Option<&'a str>

Now the borrow of self ends the moment the call returns (that is NLL doing its job), and the token’s lifetime is 'a — the lifetime of the text, which outlives everything.

The diagnostic question, worth memorising

Does this returned reference point into self, or through self into something self merely borrows?

If it points into self — a field owned by the struct, say a String the struct allocated — rule 3 is correct and you should let it elide. If it points through self, rule 3 under-promises and you must name the struct’s lifetime. Most methods are the first kind, which is why naming 'a everywhere is its own smell. This one is the second kind.

The pins

const _: () = {
    fn _pin<'a>(p: &mut Parser<'a>) -> Option<&'a str> { p.next_token() }
};
const _: for<'a> fn(&'a str) -> Vec<&'a str> = tokenize;

The first is a method pin. It asks: given a parser borrowed for some anonymous short region, can I get out a token that lives for 'a? Only the 'a-returning signature can answer yes. The elided version fails with E0621: explicit lifetime required in the type of p.

The second pins tokenize to returning borrowed slices, so “just clone everything into Strings” is not available. Note that clippy::redundant_clone is a nursery lint and is not part of this gate — clippy will not catch copy-everywhere cheating in a zero-copy problem. The pins are the only enforcement. Do not edit or delete them; a submission without them is a failed submission.

Implementation notes

• Keep one field: the unconsumed remainder, rest: &'a str.
• Advancing the cursor while returning a slice of the old cursor needs care. Bind the trimmed slice to a local first, split it, then assign the tail back to self.rest. Doing it in the other order fights the borrow checker for no reason — a small but real NLL lesson.
• str::find accepts char::is_whitespace as a pattern; str::split_at gives you both halves at once; trim_start skips a whitespace run.
• The method is called next_token, not next, on purpose: clippy::should_implement_trait fires on an inherent next and would distract from the actual lesson.
• The tests include tabs, \r\n, whitespace-only input, empty input, and multibyte tokens that must come back byte-exact.

  Loading visualization…