Zero-copy tokenizer: Parser<'a>

Build a whitespace tokenizer whose tokens are slices of the original input. "Zero-copy" here means the token text is never copied: each token is a &str that points into the string you were given. The output Vec itself still allocates; what is ruled out is allocating a new String for each token.

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

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

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

Parser<'a> holds a borrow of some text for the lifetime 'a. next_token returns the next token, or None once only whitespace (or nothing) is left.

The exact contract

• Whitespace means every char for which char::is_whitespace returns true. That is the Unicode White_Space property: space, tab, \n, \r, form feed and vertical tab, plus non-ASCII characters such as U+00A0 (no-break space) and U+3000 (ideographic space).
• A token is a maximal run of non-whitespace characters. Any run of one or more whitespace characters separates tokens, and leading or trailing whitespace produces no empty tokens.
• tokenize returns the tokens in input order, keeping duplicates. Empty input and whitespace-only input both return an empty Vec.
• Each token must be the exact bytes of the input, including multibyte UTF-8 characters such as é or ö. No case folding or normalization.
• tokenize must work by driving a Parser: create one, call next_token until it returns None, and return the collected Vec. The parser is a local variable that is dropped when tokenize returns, so the tokens must not borrow from it.

Examples: "a bb ccc" gives ["a", "bb", "ccc"]; " lead and trail " gives ["lead", "and", "trail"]; "one\ttwo\nthree\r\nfour" gives ["one", "two", "three", "four"]; "" and " \t\n " both give [].

Why the return lifetime matters

Rust lets you leave lifetimes out of many signatures and fills them in by the lifetime elision rules. One of those rules says: if a method takes &self or &mut self, every elided lifetime in the return type gets the lifetime of that self borrow. So the obvious signature

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

means

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

That signature compiles, and so does code that uses one token and discards it before asking for the next. But it says each token is borrowed from the mutable borrow of the parser. As long as you keep a token, the parser stays mutably borrowed, so you cannot call next_token again. The collecting loop is rejected:

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

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

The signature is too restrictive, not the data: a token really points into src, and the parser only stores the cursor. To say that, return the struct's own lifetime parameter:

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

Now the returned token is not tied to the &mut self borrow, so that borrow can end as soon as the call returns, and the token stays valid for 'a, as long as the input text does. That is long enough to outlive the parser and be returned from tokenize.

A useful question when writing such a method: does the returned reference point into data that self owns, or through self into data that self only borrows? If the struct owns the data (for example a String field), the elided self lifetime is the right one. If the struct only holds a borrow, as Parser does, the elided lifetime is shorter than necessary and you usually want to name the struct's lifetime parameter instead.

The pins

The starter code ends with two compile-time checks. Do not edit or delete them: they are part of the exercise, and without them a solution could pass the tests with the wrong signatures.

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 function that borrows a parser for some short, unnamed lifetime and must return a token that lives for 'a. It compiles when next_token returns Option<&'a str>. With the elided signature the compiler reports error E0621, "explicit lifetime required in the type of p".

The second requires tokenize to have exactly the type fn(&'a str) -> Vec<&'a str> for every 'a, so returning Vec<String> fails to compile with a type mismatch (E0308). The pins check signatures only. The tests compare token text, and the default Clippy lints do not flag converting tokens to owned strings, so nothing at runtime detects extra copying.

Implementation notes

• One field is enough: the unconsumed remainder of the input, rest: &'a str.
• trim_start skips a whitespace run, using the same definition of whitespace as char::is_whitespace.
• str::find accepts char::is_whitespace as a pattern and returns the byte index of the first match. That index is always on a character boundary, so str::split_at at that index cannot panic and gives you the token and the new remainder at once.
• Because trimmed, the token and the remainder are all &'a str values copied out of self.rest, the order in which you update self.rest and return the token does not matter to the borrow checker.
• The method is called next_token rather than next because Clippy's default should_implement_trait lint rejects an inherent method named next with this shape (it suggests implementing Iterator instead), and the gate treats Clippy warnings as errors.
• The tests include tabs, \r\n, whitespace-only input, empty input and tokens containing multibyte characters.