147. The scanner in Rust

One character, please

The TypeScript scanner’s helpers, from companion/ts/src/vm/scanner.ts:

private advance() {
  return this.source[this.current++];
}
private peek() {
  return this.atEnd()
    ? '\0' : this.source[this.current];
}

this.source[i] hands back a one-character string, and the scanner compares it with '(' or tests c >= '0' && c <= '9'. Write the same thing in Rust and it doesn’t compile (1.97, trimmed):

error[E0277]: the type `str` cannot be
  indexed by `{integer}`
  ^ string indices are ranges of
    `usize`

A str is UTF-8, where a character takes one to four bytes. “The character at index 5” would mean walking from the start to count them, so Rust refuses to pretend it is a cheap lookup^[1]. You can slice a str with a byte range, or you can look at its bytes.

Two views of one text

drip-rs keeps both (from scanner.rs, trimmed):

pub struct Scanner<'src> {
    source: &'src str,
    bytes: &'src [u8],
    start: usize,
    current: usize,
    line: usize,
}

Scanner::new fills bytes with source.as_bytes(). That copies nothing: it is the same memory, typed as a slice of u8^[2]. The scanner reads bytes to decide what each token is, and slices source to make the lexeme. The helpers become:

fn advance(&mut self) -> u8 {
    self.current += 1;
    self.bytes[self.current - 1]
}

fn peek(&self) -> u8 {
    self.bytes.get(self.current)
        .copied()
        .unwrap_or(b'\0')
}

get returns None past the end, so peek needs no separate atEnd test: it turns None into the NUL byte, as the TypeScript version did with '\0'. And b'(' is a byte literal, the u8 40, so the big match in scan_token reads almost like the TypeScript switch:

match c {
    b'(' => self.make(T::LeftParen),
    b'!' => self.make_if_equal(
        T::BangEqual, T::Bang),
    b'"' => self.string(),
    // ...
}

Why bytes are safe

Scanning bytes would be a disaster if a byte of é could look like a quote. UTF-8 was designed so it can’t.

In bits: an ASCII byte is 0xxxxxxx, 0 to 127. A character that needs more bytes starts with a lead byte, 110xxxxx, 1110xxxx or 11110xxx, and every byte after it is a continuation byte, 10xxxxxx. So every byte of a non-ASCII character is 128 or more, and comparing a byte with b'"' or b'\n' can only match a real quote or newline. Step through the scanner on s="é";é:

That is why &self.source[self.start..self.current] never panics. Chapter 126 showed what slicing in the middle of é does. A token starts and ends only just after an ASCII byte, after a whole skipped character (next section), or at the end, and all three are character boundaries. In the middle of a string, current does pass through the inside of é, but nothing is sliced until the closing quote.

The one non-ASCII case

Outside a string, Drip has no use for é. The _ arm of the match reports it:

_ => {
    // Skip the rest of a multi-byte
    // UTF-8 character.
    while is_continuation(self.peek()) {
        self.current += 1;
    }
    self.error("Unexpected character.")
}

and the test is one mask, c & 0b1100_0000 == 0b1000_0000. Why bother? I removed the loop from a copy of the scanner and ran it on é: it gave two error tokens, one for byte 195 and one for byte 169. With the loop it gives one, like the TypeScript scanner, which sees é as a single UTF-16 code unit.

It is not a perfect match. An emoji such as 😀 is four UTF-8 bytes but two UTF-16 code units, so the TypeScript scanner returns two error tokens and drip-rs one. Nobody sees the difference: after the first error the compiler is in panic mode (chapter 34) and stays quiet until the next statement. I ran both VMs on a file with a 😀 on line 2, and both printed [line 2] Error: Unexpected character. and exited with 65.

The rest of the scanner

Everything else is the TypeScript logic with u8s. Numbers, from scanner.rs:

fn number(&mut self) -> Token<'src> {
    while self.peek().is_ascii_digit() {
        self.current += 1;
    }
    // `1.` is `1` then `.`
    if self.peek() == b'.'
        && self.peek_next()
            .is_ascii_digit()
    {
        self.current += 1;
        while self.peek()
            .is_ascii_digit() {
            self.current += 1;
        }
    }
    self.make(TokenKind::Number)
}

Strings loop to the closing b'"', counting b'\n's as they go. Comments run to the next b'\n'. Identifiers continue while bytes are ASCII letters, digits or _, then go through chapter 146’s keyword. Here is a cut-down scanner you can run, with the skip in it:

// A tiny byte scanner, adapted from
// drip-rs's scanner.rs.
struct Scan<'src> {
    src: &'src str,
    b: &'src [u8], // the same text
    st: usize,     // token start
    cur: usize,    // next byte
}

// The 2nd, 3rd or 4th byte of a UTF-8
// character looks like 10xxxxxx.
fn is_cont(c: u8) -> bool {
    c & 0b1100_0000 == 0b1000_0000
}

fn digit(c: u8) -> bool {
    c >= b'0' && c <= b'9'
}

impl<'src> Scan<'src> {
    fn peek(&self) -> u8 {
        let x = self.b.get(self.cur);
        x.copied().unwrap_or(b'\0')
    }

    fn bump(&mut self) -> u8 {
        self.cur += 1;
        self.b[self.cur - 1]
    }

    fn tok(&self, k: &str) -> String {
        let r = self.st..self.cur;
        let t = &self.src[r];
        format!("{k} {t}")
    }

    fn digits(&mut self) {
        while digit(self.peek()) {
            self.cur += 1;
        }
    }

    fn next(&mut self)
        -> Option<String> {
        while self.peek() == b' ' {
            self.cur += 1;
        }
        self.st = self.cur;
        if self.cur >= self.b.len() {
            return None;
        }
        let c = self.bump();
        if digit(c) {
            self.digits();
            let t = self.tok("Num");
            return Some(t);
        }
        if c == b'"' {
            while self.peek() != b'"' {
                self.cur += 1;
            }
            self.cur += 1;
            let t = self.tok("Str");
            return Some(t);
        }
        while is_cont(self.peek()) {
            self.cur += 1;
        }
        let a = self.st;
        let z = self.cur;
        Some(format!("Error {a}..{z}"))
    }
}

fn main() {
    let src = "42 \"é\" é 7";
    println!("{:?}", src.as_bytes());
    let mut s = Scan {
        src,
        b: src.as_bytes(),
        st: 0,
        cur: 0,
    };
    while let Some(t) = s.next() {
        println!("{}", t);
    }
}

Your turn

fn digit(c: u8) -> bool {
    c.is_ascii_digit()
}

struct Scan<'src> {
    src: &'src str,
    b: &'src [u8],
    st: usize,
    cur: usize,
}

impl<'src> Scan<'src> {
    fn new(src: &'src str) -> Self {
        let b = src.as_bytes();
        Scan { src, b, st: 0, cur: 0 }
    }

    /// The next byte (NUL at the end).
    fn peek(&self) -> u8 {
        let x = self.b.get(self.cur);
        x.copied().unwrap_or(b'\0')
    }

    /// The byte after that, or NUL.
    fn peek_next(&self) -> u8 {
        let i = self.cur + 1;
        let x = self.b.get(i);
        x.copied().unwrap_or(b'\0')
    }

    /// Scan the number at `cur`, and
    /// return its lexeme.
    fn number(&mut self) -> &'src str {
        todo!()
    }
}

/// Is `c` a continuation byte, the 2nd,
/// 3rd or 4th byte of a character?
fn is_cont(c: u8) -> bool {
    todo!()
}

/// The index just past the character
/// that starts at byte `i`.
fn char_end(b: &[u8], i: usize)
    -> usize {
    todo!()
}

What you learned

• Rust won’t index a str by integer. drip-rs scans bytes: it keeps bytes: &[u8] (from as_bytes(), free) beside source: &str.
• peek uses get(..).copied().unwrap_or(b'\0'), and the match is on byte literals like b'('.
• In UTF-8 every byte of a non-ASCII character is ≥ 128, and continuation bytes look like 10xxxxxx. So ASCII comparisons are safe, and lexeme slices always land on character boundaries.
• For an unexpected non-ASCII character the scanner skips its continuation bytes, giving one error per character.
• Numbers, strings, comments and identifiers are the TypeScript logic on u8s.