6
\$\begingroup\$

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();
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Are you interested in keeping track of the position? Typically, lexers are able to indicate where the token started (a byte offset at least, line/column being more expensive). \$\endgroup\$ Feb 9, 2023 at 12:54

2 Answers 2

3
\$\begingroup\$

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)..])))
    }
}
```
\$\endgroup\$
4
  • \$\begingroup\$ I wonder if all the lifetimes there are needed, as reading code with them can be really hard, if you know barely anything about rust. I do like how you made everything a lot more readable overall anyway. \$\endgroup\$ Feb 9, 2023 at 18:56
  • 1
    \$\begingroup\$ @IsmaelMiguel: Lifetimes on impl blocks themselves cannot be elided, and eliding the lifetime on -> Option<Token<'_>> would tie the lifetime of Token to that of &mut self (ie, the Lexer's lifetime) which would not work. So I am afraid they are needed if performance is a goal. As you get more used to Rust, you'll soon skip over them :) \$\endgroup\$ Feb 10, 2023 at 8:05
  • \$\begingroup\$ That does make a lot of sense. I do need to read a little more of rust. Also, on the (_, _) => todo!([...]), wouldn't it make sense to keep using Token::ILLEGAL(self.ch.to_string()) (or some variation) to handle the errors? \$\endgroup\$ Feb 10, 2023 at 20:26
  • 2
    \$\begingroup\$ @IsmaelMiguel: As a starter, yes indeed. I missed it. You should use &'a str to reference the issue, and I would suggest adding some "error-code", to denote the nature of the issue. If your lexer matures, you may want to switch to a separate system to track errors -- allowing you to include more details without bloating the Token enum. \$\endgroup\$ Feb 11, 2023 at 11:23
7
\$\begingroup\$

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 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 (&nbsp; 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();
}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ For someone who has never written Rust, you've made spot-on comments on the use of built-in std methods that even Rust developers regularly skip! Kudos! \$\endgroup\$ Feb 9, 2023 at 12:49
  • 1
    \$\begingroup\$ @MatthieuM. Thank you. I did take time to check up on this, before I wrote my review. I always check this type of stuff when reviewing any code I know nothing about. There's no need to re-invent the wheel for this type of basic stuff if this is already (better) implemented by someone/something else. \$\endgroup\$ Feb 9, 2023 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.