Programming Language Source Lexer

Question

I have a lexer (program that turns source code into tokens) written in Go that I am re-writing in Rust.

The lexer should take in a sequence of tokens, generally different special characters, integers, or string sequences (identifiers) and output tokens representing those 'types'.

I'd like to write more idiomatic Rust, using non-mutable data wherever possible, but the current 'design' is akin to OOP with a struct mutating itself in most methods. I am struggling to come up with a better design that is more idiomatic Rust, so input would be highly appreciated.

As you can see in the code below, the Lexer struct holds different position counters that are mutated in most methods, meaning that the entire struct is passed as mutable. This seems to be a specific code smell to me, and I would like to refactor that out if nothing else.

use crate::token::{match_keyword, Token};

/// A lexer contains a vector of characters as well as various pointers to read and peek characters
/// in the input.
pub struct Lexer {
    input: Vec<char>,
    position: usize,      // current reading position
    peek_position: usize, // current peeking position
    ch: char,             // current char under examination
}

impl Lexer {
    pub fn new(input: String) -> Self {
        let in_vec: Vec<char> = input.chars().collect();
        let c = in_vec[0];
        Self {
            input: in_vec,
            position: 0,
            peek_position: 1,
            ch: c,
        }
    }

    pub fn next_token(&mut self) -> Option<Token> {
        self.skip_whitespace();

        let tok = match self.ch {
            '+' => Token::PLUS,
            '-' => Token::MINUS,
            '*' => Token::ASTERISK,
            '!' => {
                if self.peek_char()? == '=' {
                    self.read_char(); // advance past '='
                    Token::NEQ
                } else {
                    Token::BANG
                }
            }
            '?' => Token::QUESTION,
            '>' => Token::GT,
            '<' => Token::LT,
            ',' => Token::COMMA,
            ';' => Token::SEMICOLON,
            '(' => Token::LPAREN,
            ')' => Token::RPAREN,
            '{' => Token::LBRACE,
            '}' => Token::RBRACE,
            '|' => {
                if self.peek_char()? == '>' {
                    self.read_char();
                    Token::PIPE
                } else if self.peek_char()? == '|' {
                    self.read_char();
                    Token::LOR
                } else {
                    // FIXME is there a way around this?
                    Token::ILLEGAL(String::from(self.ch))
                }
            }
            '/' => {
                // TODO add comment support aka skip anything from double // to newline
                if self.peek_char()? == '/' {
                    // need to skip to newline
                    while self.ch != '\n' {
                        self.read_char();
                    }
                    Token::COMMENT // this will be discarded in parsing. maybe keep it for reflection
                } else {
                    Token::SLASH
                }
            }
            '"' => {
                while self.peek_char()? != '"' {
                    self.peek_position += 1;
                }
                self.position = self.peek_position; // catch current pos up to the peek
                Token::STRING(
                    self.input[self.position..self.peek_position]
                        .into_iter()
                        .collect(),
                )
            }

            _ => {
                if self.ch.is_alphabetic() {
                    let mut lit = String::from(self.read_char());
                    while self.input.get(self.position)?.is_alphabetic() {
                        lit.push(self.read_char());
                    }
                    match_keyword(lit.as_str())
                } else if self.ch.is_digit(10) {
                    let mut lit = String::from(self.read_char());
                    while self.input.get(self.position)?.is_digit(10) {
                        lit.push(self.read_char());
                    }
                    Token::INT(lit.parse::<i32>().unwrap()) // FIXME better error handling
                } else {
                    Token::ILLEGAL(self.ch.to_string())
                }
            }
        };
        self.read_char();
        Some(tok)
    }

    fn read_char(&mut self) -> char {
        self.ch = *self.input.get(self.position).unwrap_or(&'\0'); // FIXME
        self.position += 1;
        self.ch
    }

    fn peek_char(&self) -> Option<char> {
        // if self.peek_position >= self.input.len() {
        //     '\0'
        // } else {
        //     self.input[l.readPosition]
        // }
        if let Some(ch) = self.input.get(self.peek_position) {
            Some(*ch)
        } else {
            None
        }
    }

    fn skip_whitespace(&mut self) {
        while self.ch == ' ' || self.ch == '\t' || self.ch == '\n' || self.ch == '\r' {
            self.read_char();
        }
    }
}

Answer 1

At a high-level, I would say there are two potential roads for improvement in this code:

1. The side-effect methods. You noted yourself that struct is passed mutably; that's not a problem, really, since a lexer will keep track of state. The real issue is that some methods are invoked only for their side-effect of changing the state, not returning anything.
2. Performance wise, that's a lot of memory allocations.

Performance: memory allocations

Your code doesn't, for the most part, require to allocate anything, so all those allocations are superfluous.

This can be handled by borrowing, instead:

struct Lexer<'a> {
    content: &'a str,
    iterable: Peekable<Chars<'a>>,
}

impl<'a> Lexer<'a> {
    pub fn new(content: &'a str) -> Self {
        let iterable = content.chars().peekable();

        Self { content, iterable }
    }
}

And we can change the tokens to match:

enum Token<'a> {
    String(Cow<'a, str>), // Allocation may be necessary with escape characters.
    ...
}

Note that I also eliminated the manual cursors here:

• content now points to the not-yet-parsed slice.
• iterable points to the not-yet-parsed char view of the slice.

There's thus no need to keep a "current" index, and we should aim at eliminating the "peek" index.

Mutation: eliminate side-effects

One of the issues you are facing is the side-effect only read_char method, which is a bit awkward.

Instead, what we can have is a method that combines moving the cursor, and returning what was covered for use. Or two, one by index -- efficient -- and one by predicate -- for flexible needs.

impl<'a> Lexer<'a> {
    //  Advances by n chars, and returns a reference to the characters skipped.
    fn advance_by(&mut self, n: usize) -> &'a str {
        let n: usize = self.iterable
            .take(n)
            .map(|c| c.len_utf8())
            .sum();

        let (head, tail) = self.content.split_at(n);
        self.content = tail;

        head
    }

    //  Advances as long as the predicate returns true, and returns a reference
    //  to the characters skipped.
    fn advance_while<F>(&mut self, predicate: F) -> &'a str
    where
        F: FnMut(char) -> bool,
    {
        let n: usize = self.iterable
            .take_while(predicate)
            .map(|c| c.len_utf8())
            .sum();

        let (head, tail) = self.content.split_at(n);
        self.content = tail;

        head
    }
}

Note: if you wish to keep track of the position, which I'd encourage you to track as byte offset, you'd augment the advance_xxx methods to return both strings and starting position.

I'll also split the next_token method. The checks will look a bit redundant, but your next_token is just too damn big -- and prone to get bigger as you handle escape sequences, etc...

    /// Returns the next Token, or None if no such Token exist.
    pub fn next_token(&mut self) -> Option<Token<'a>> {
        self.skip_whitespace();

        let next = self.iterable.peek()?; // short-circuit execution if `None`.

        match next {
            '+' | '-' | '*' | '/' => self.next_arithmetic(),
            '<' | '>' | '=' | '!' => self.next_comparator(),
            '(' | ')' | '[' | ']' | '{' | '}' => self.next_bracket(),
            '.' | ',' | ';' | '?' => self.next_punctuation(),
            '"' | '\'' => self.next_string(),
            '0'..='9' => self.next_digit(),
            'a'..='z' | 'A'..='Z' => self.next_identifier_or_keyword(),
            _ => todo!("Handle weird characters..."),
        }
    }

    fn skip_whitespace(&mut self) {
        self.advance_while(|c| c.is_whitespace());
    }

All the "simple" methods can advance by 1 character only.

impl<'a> Lexer<'a> {
    fn next_arithmetic(&mut self) -> Option<Token<'a>> {
        let next = self.advance_by(1)[0];

        match next {
           b'+' => Some(Token::Plus),
           b'-' => Some(Token::Dash),
           b'*' => Some(Token::Star),
           b'/' => Some(Token::Slash),
           _ => unreachable!(),
       }
    }
}

Comparisons are trickier, involving either 1 or 2 characters:

impl<'a> Lexer<'a> {
    fn next_comparison(&mut self) -> Option<Token<'a>> {
        let current = self.advance_by(1)[0];
        let next = self.advance_while(|c| c == '=');

        match (current, next) {
            ('<', "") => Some(Token::LessThan),
            ('<', "=") => Some(Token::LessThanOrEqual),
            ('>', "") => Some(Token::GreaterThan),
            ('>', "=") => Some(Token::GreaterThanOrEqual),
            ('=', "") => Some(Token::Assign),
            ('=', "=") => Some(Token::Equal),
            ('!', "") => Some(Token::Bang),
            ('!', "=") => Some(Token::Different),
            (_, _) => todo!("Handle lexing errors gracefully"),
        }
    }
}

For strings, it gets a bit more complicated but that's encapsulated:

impl<'a> Lexer<'a> {
    fn next_string(&mut self) -> Option<Token<'a>> {
        let content = self.content;

        let open = self.advance_by(1)[0];

        let n = self.advance_while(|c| c != open).len();

        let close = self.advance_by(1).get(0).expect("Lexer errors to be handled");

        Some(Token::String(Cow::Borrowed(&content[(n + 2)..])))
    }
}
```

Answer 2

Disclaimer

I've NEVER written Rust, used Rust anywhere, or done anything with/about Rust.

However, I do have to say that, what you have there, is extremely easy to read and understand, even for a beginner like myself.

---

---

next_token()

This function has a bad bug: It doesn't handle escape sequences.
In fact, it makes it impossible to have strings with double-quotes inside, which is bad!

This is the relevant code:

while self.peek_char()? != '"' {
    self.peek_position += 1;
}
self.position = self.peek_position; // catch current pos up to the peek
Token::STRING(
    self.input[self.position..self.peek_position]
        .into_iter()
        .collect(),
)

In this block, you could do something like this instead:

let mut stop = false;
while !stop {
    let cur_char = self.peek_char()?;
    
    if(cur_char == '"') {
        stop = true;
    } else if(cur_char == '\\') {
        self.peek_position += 2;
    } else {
        self.peek_position += 1;
    }
}

The idea is to jump 2 positions when you find a backwards slash (\).
You can do proper validation to allow other escape sequences, and to validate the current escape sequence.

As I'm not a Rust developer, I have no idea if this works, but the idea is to show the intent, not a working code.

---

Still in next_token()

You have this piece here:

Token::COMMENT // this will be discarded in parsing. maybe keep it for reflection

I can tell you, with confidence, that you should keep comments, even in the parser.

If you transpile/compile this code into another language, having this comment there could actually be very useful, if you intend to make the output human-readable.

---

More next_token()...

You have the following code to handle the asterisk:

'*' => Token::ASTERISK,

This code doesn't handle the power syntax (**).

If the tokenizer you're using doesn't have a way to handle the power syntax, you will have to find a way to handle it somehow - I can't find the crate you're using.

---

peek_char()

Please avoid keeping comments with useless stuff in them.
For example:

// if self.peek_position >= self.input.len() {
//     '\0'
// } else {
//     self.input[l.readPosition]
// }

These comments provide no value at all for the existing code, and should be removed.

---

skip_whitespace()

This function is kinda unnecessary, but I understand why it is separated.

But, it can be better written anyway.

Instead of doing this:

while self.ch == ' ' || self.ch == '\t' || self.ch == '\n' || self.ch == '\r' {
    self.read_char();
}

You can use the char::is_ascii_whitespace() method instead:

while self.ch.is_ascii_whitespace()
{
    self.read_char();
}

However, it doesn't consider all UTF-8 white-space.
For example, a non-breaking space (  in HTML) is a white-space.

You may want to use the char::is_whitespace method instead, to handle those:

while self.ch.is_whitespace()
{
    self.read_char();
}