pub enum TokenType {
Star,
String,
Whitespace,
impl fmt::Display for TokenType {
Self::Star => "STAR",
Self::String => "STRING",
Self::Whitespace => "WHITESPACE",Their codes have grown increasingly complex.
In the last four stages we will add functions to the scanner to recognise strings, numbers, identifiers, and reserved words. All these tokens have no fixed length, so the code that extracts them needs to be a bit more sophisticated than what we have done so far. In general, however, we will follow a simple pattern: we will detect the beginning of the token and continue to collect characters until we detect the end.
String literals are, from the scanning point of view, an evolution of comments. Comments start with two slashes and end at the newline, while strings begin and end with the same single character ", but everything else between start and end becomes part of the token.
Strings are marginally more complicated because of termination. Comments cannot be left "open" because they terminate automatically when we reach the newline or the end of the file, and one of those conditions will always occur. Strings must end with double quotes, and if the character cannot be found the string is considered unterminated. This is a condition we have to detect and flag as an error.
Let's start by adding a token type for strings.
src/token.rs pub enum TokenType {
Star,
String,
Whitespace,
impl fmt::Display for TokenType {
Self::Star => "STAR",
Self::String => "STRING",
Self::Whitespace => "WHITESPACE",We can then add the following function to Tokenizer.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
// Test the current characters and
// try to match the beginning of a string.
// Returns an error if the string is unterminated.
fn string(&mut self) -> Option<TokenResult> {
// If the current character is None return None.
let c = self.current_character?;
// If this is not double quotes this is not the beginning of a string.
if c != '"' {
return None;
}
let mut s = String::from(c);
loop {
// We already know the current character
// is part of the string, so let's start
// from the next one.
self.advance();
match self.current_character {
Some(v) => {
s.push(v);
if v == '"' {
// We just captured the last character of the
// string. Return the token using the full string
// with quotes as lexemes (this is what we processed)
// and the string without quotes as literal value.
return Some(Ok(Token {
ttype: TokenType::String,
lexeme: s.clone(),
literal: s.trim_matches('"').to_owned(),
}));
}
}
None => {
// No need to advance. If we reach this point
// there is nothing left to read in the file
// and the string hasn't been terminated.
// Goodbye.
self.errors = true;
return Some(Err(TokenError {
message: String::from("Unterminated string."),
line: self.current_line,
}));
}
}
}
}Let's have a look at the function a bit more in detail:
src/tokenizer.rs impl<'a> Tokenizer<'a> {
// Test the current characters and
// try to match the beginning of a string.
// Returns an error if the string is unterminated.
fn string(&mut self) -> Option<TokenResult> {
// If the current character is None return None.
let c = self.current_character?; 1
// If this is not double quotes this is not the beginning of a string.
if c != '"' { 2
return None;
}
let mut s = String::from(c);
loop { 3
...
}
}The function starts just like single_character_token and multi_character_token, extracting the current character and stopping the process if its value is None 1. The strategy implemented by the scanner is to try a set of functions in sequence, which means that in each function we can always exit immediately as soon as we encounter a value that doesn't match what we are expecting. In this case, the first check is that the current character must be the opening " 2. If the current character is " we loop on the remaining characters 3 adding them to a Rust string.
The code inside the loop requires a couple of clarifications.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
fn string(&mut self) -> Option<TokenResult> {
loop {
// We already know the current character
// is part of the string, so let's start
// from the next one.
self.advance(); 1
match self.current_character { 2
Some(v) => {
s.push(v); 3
if v == '"' {
// We just captured the last character of the
// string. Return the token using the full string
// with quotes as lexemes (this is what we processed)
// and the string without quotes as literal value.
return Some(Ok(Token { 4
ttype: TokenType::String,
lexeme: s.clone(),
literal: s.trim_matches('"').to_owned(),
}));
}
}
None => {
// No need to advance. If we reach this point
// there is nothing left to read in the file
// and the string hasn't been terminated.
// Goodbye.
self.errors = true;
return Some(Err(TokenError { 5
message: String::from("Unterminated string."),
line: self.current_line,
}));
}
}
}Some(v) or None 2.Some, we add the character to the Rust string 3. If the character is the closing " we return the token with the whole string 4.None, we reached the end of the file without detecting the closing ", so we have to create an error telling the user that the string is unterminated 5.The last part of this stage is to call the method string during the iterator loop.
src/tokenizer.rs impl<'a> Iterator for Tokenizer<'a> {
fn next(&mut self) -> Option<Self::Item> {
// Advance the current token and
// return if we reached the end
// of the input file.
let current = self.advance()?;
// Try to match a string.
if let Some(t) = self.string() {
return Some(t);
}
// Try to match a multi-character token.
if let Some(t) = self.multi_character_token() {
return Some(t);
}There are several tests that we can add for the new code. The following four tests target the function Tokenizer::string. They check the behaviour of the function when there is no current character (end of file), when the current character is not the opening double quotes, when the string is valid, and when the string is unterminated.
src/tokenizer.rs mod tests {
#[test]
// Test that the method string
// behaves correctly when the tokeniser is not
// initialised and there is no current
// character.
fn test_string_no_current_character() {
let mut t = Tokenizer {
iter: "characters".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
assert_eq!(t.string(), None);
}
#[test]
// Test that the method string
// behaves correctly when the tokeniser is
// initialised and there is a current
// character, but the character is
// not the opening double quotes.
fn test_string_no_double_quotes() {
let mut t = Tokenizer {
iter: "characters".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(t.string(), None);
}
#[test]
// Test that the method string
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// a string with both opening and
// closing double quotes.
fn test_string_valid_string() {
let mut t = Tokenizer {
iter: "\"some string\"".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.string(),
Some(Ok(Token {
ttype: TokenType::String,
lexeme: String::from("\"some string\""),
literal: String::from("some string"),
}))
);
}
#[test]
// Test that the method string
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// a string with only the
// opening double quotes.
fn test_string_unterminated() {
let mut t = Tokenizer {
iter: "\"some string".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.string(),
Some(Err(TokenError {
message: String::from("Unterminated string."),
line: 1
}))
);
}It is useful to have a test on the whole iterator to check that Tokenizer::next calls the method Tokenizer::string.
src/tokenizer.rs mod iterator_tests {
#[test]
// Test the iterator end-to-end on
// a well-defined string.
fn test_string() {
let mut t = Tokenizer {
iter: "\"a string\"".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
let mut result = Vec::<TokenResult>::new();
for token in &mut t {
result.push(token);
}
assert_eq!(
result,
[Ok(Token {
ttype: TokenType::String,
lexeme: String::from("\"a string\""),
literal: String::from("a string"),
})]
);
}Stage 12 - Scanning: String literals
This version of the code passes Stage 12 of the base CodeCrafters challenge.
The current implementation of the scanner contains a relevant asymmetry that can make writing processing functions harder than necessary.
The method next starts with a call to advance, which means that the first processing function expects the pointer to be on the character that hasn't been processed yet. This in turn means that every processing function, if unsuccessful, must do the same to allow the next function to work properly. At the same time, a successful processing must leave the current character pointer on the character that has been processed, so that the next loop can move to the next character.
It is worth trying to make things consistent so that we have only one rule to remember when we create processing functions for our scanner. This is mostly a matter of personal preference, and you can have a perfectly working scanner that contains this asymmetry. Some might even consider it more logical!
To make the system coherent, we need to leave the pointer on the first unprocessed character whether the scanning function is successful or not. This means that the loop won't automatically advance the pointer, as that will be done by the processing functions.
First of all, the three functions single_character_token, multi_character_token, and string must be changed to reflect the new strategy: advance when you are successful.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
fn multi_character_token(&mut self) -> Option<TokenResult> {
// We read the current character and transformed
// it into a token, so we need to make sure
// the iterator is ready to parse the next character.
self.advance();
Some(Ok(Token {
ttype,
lexeme: full,
literal: String::from("null"),
}))
fn single_character_token(&mut self) -> Option<TokenResult> {
// We read the current character and transformed
// it into a token, so we need to make sure
// the iterator is ready to parse the next character.
self.advance();
Some(Ok(Token {
ttype,
lexeme: String::from(c),
literal: String::from("null"),
}))
fn string(&mut self) -> Option<TokenResult> {
match self.current_character {
if v == '"' {
// We just captured the last character of the
// string. Return the token using the full string
// string (the closing quotes) so we make sure
// the iterator is ready to parse the next character.
self.advance();
// Return the token using the full string
// with quotes as lexemes (this is what we processed)
// and the string without quotes as literal value.
return Some(Ok(Token {
ttype: TokenType::String,
lexeme: s.clone(),
literal: s.trim_matches('"').to_owned(),
}));
}As we said, the iterator must not advance automatically. We only need to extract the current character from the Option. However, we need to advance if the current character ends up being an error.
src/tokenizer.rs impl<'a> Iterator for Tokenizer<'a> {
fn next(&mut self) -> Option<Self::Item> {
// Advance the current token and
// return if we reached the end
// of the input file.
let current = self.advance()?;
// If the current character is None return None.
let current = self.current_character?;
...
// If we reach this point we couldn't
// match the current character with
// any lexeme, so this is an error.
self.errors = true;
// We detected an error, so we advance
// the iterator to continue processing
// the input.
self.advance();
Some(Err(TokenError {
message: format!("Unexpected character: {}", current),
line: self.current_line,
}))Clearly, we need to adjust all the tests that check the behaviour of the iterator.
src/tokenizer.rs mod iterator_tests {
fn test_valid_characters() {
let t = Tokenizer {
let mut t = Tokenizer {
iter: ",(+".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: build_lexemes_map(LEXEMES),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
fn test_invalid_characters() {
let mut t = Tokenizer {
iter: ",@+".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: build_lexemes_map(LEXEMES),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
fn test_empty_input() {
let t = Tokenizer {
let mut t = Tokenizer {
iter: "".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: build_lexemes_map(&[]),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
fn test_comment() {
let mut t = Tokenizer {
iter: "// Comment".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: build_lexemes_map(SINGLE_LEXEMES),
mc_lexemes: build_lexemes_map(MULTI_LEXEMES),
};
// This advances the iterator to the initial character
t.advance();
fn test_newline() {
let mut t = Tokenizer {
iter: "\n".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: build_lexemes_map(SINGLE_LEXEMES),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
fn test_string() {
let mut t = Tokenizer {
iter: "\"a string\"".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();Last, we need to initialise the iterator by manually advancing to the first unprocessed character. To be able to do this the method Tokenizer::advance must be public:
src/tokenizer.rs impl<'a> Tokenizer<'a> {
// Advance the iterator and
// return the current character.
fn advance(&mut self) -> Option<char> {
pub fn advance(&mut self) -> Option<char> {
// Advance the iterator and store
// the current character for future
// retrieval.
self.current_character = self.iter.next();
// Return the current character.
self.current_character
}and we need to call it in main just after we initialise Tokenizer.
src/main.rs fn main() {
match command.as_str() {
// Create a new tokenizer and
// instantiate it with the content
// of the input file.
let mut t = Tokenizer {
iter: file_contents.chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: build_lexemes_map(SINGLE_CHARACTER_LEXEMES),
mc_lexemes: build_lexemes_map(MULTI_CHARACTER_LEXEMES),
};
// Initialise the iterator
t.advance();
// Iterate on the tokenizer
// and process each result.
for token in &mut t {
match token {
Ok(token) => match token.ttype {
TokenType::Comment => continue,
TokenType::Whitespace => continue,
TokenType::Newline => continue,
_ => println!("{}", token),
},
Err(e) => {
eprintln!("{}", e);
}
}
}With numbers, we face a challenge similar to the one presented by strings. Numbers are multi-character lexemes, and their size is not known in advance. Furthermore, numbers can contain a dot that separates the decimal part, but the dot is not always part of the number. There is an interesting discussion in Nystrom's book that highlights the issues with numbers as objects, where you might have expressions like 123.sqrt().
The CodeCrafters challenge doesn't require this level of complexity, but for the sake of completeness we will implement it here.
There is, however, another concern. So far, the literal value of a token has been captured as a String, and we accepted to give tokens without a literal the value String::from("null"). In this step, however, we are going to tokenise numbers, and part of this operation will involve parsing a string (the source code) into a number (the actual literal). Given that the number represented by the token will be used during evaluation it would be a pity to throw away the result of the conversion and to store the literal as a string, just to be forced to convert it once again during evaluation.
For this reason, it's reasonable to give the field literal a dedicated type before we implement the new method to tokenise numbers.
src/token.rs #[derive(Debug, PartialEq, Eq)]
pub enum TokenLiteral {
Null,
String(String),
}
impl fmt::Display for TokenLiteral {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::Null => write!(f, "null"),
Self::String(s) => write!(f, "{s}"),
}
}
}
#[derive(Debug, PartialEq, Eq)]
pub struct Token {
pub ttype: TokenType,
pub lexeme: String,
pub literal: String,
pub literal: TokenLiteral,
}Currently, TokenLiteral can be Eq to support the #[derive(Eq)] given to Token. Later, we will introduce a variant with a float, which doesn't support Eq and therefore we will have to remove the trait. This change affects some of the code written for the tokeniser:
src/tokenizer.rs use crate::token::{Token, TokenError, TokenResult, TokenType};
use crate::token::{Token, TokenError, TokenLiteral, TokenResult, TokenType};
impl<'a> Tokenizer<'a> {
fn multi_character_token(&mut self) -> Option<TokenResult> {
// We read the current character and transformed
// it into a token, so we need to make sure
// the iterator is ready to parse the next character.
self.advance();
Some(Ok(Token {
ttype,
lexeme: full,
literal: String::from("null"),
literal: TokenLiteral::Null,
}))
fn single_character_token(&mut self) -> Option<TokenResult> {
// We read the current character and transformed
// it into a token, so we need to make sure
// the iterator is ready to parse the next character.
self.advance();
Some(Ok(Token {
ttype,
lexeme: String::from(c),
literal: String::from("null"),
literal: TokenLiteral::Null,
}))
fn string(&mut self) -> Option<TokenResult> {
// Return the token using the full string
// with quotes as lexemes (this is what we processed)
// and the string without quotes as literal value.
return Some(Ok(Token {
ttype: TokenType::String,
lexeme: s.clone(),
literal: s.trim_matches('"').to_owned(),
literal: TokenLiteral::String(s.trim_matches('"').to_owned()),
}));
mod tests {
fn test_tokenize_valid_character() {
assert_eq!(
token,
Some(Ok(Token {
ttype: TokenType::Comma,
lexeme: String::from(","),
literal: String::from("null"),
literal: TokenLiteral::Null,
}))
);
fn test_multi_character_valid_character() {
assert_eq!(
token,
Some(Ok(Token {
ttype: TokenType::EqualEqual,
lexeme: String::from("=="),
literal: String::from("null"),
literal: TokenLiteral::Null,
}))
);
fn test_string_valid_string() {
assert_eq!(
t.string(),
Some(Ok(Token {
ttype: TokenType::String,
lexeme: String::from("\"some string\""),
literal: String::from("some string"),
literal: TokenLiteral::String(String::from("some string")),
}))
);
fn test_valid_characters() {
assert_eq!(
result,
[
Ok(Token {
ttype: TokenType::Comma,
lexeme: String::from(","),
literal: String::from("null")
literal: TokenLiteral::Null
}),
Ok(Token {
ttype: TokenType::LParen,
lexeme: String::from("("),
literal: String::from("null")
literal: TokenLiteral::Null
}),
Ok(Token {
ttype: TokenType::Plus,
lexeme: String::from("+"),
literal: String::from("null")
literal: TokenLiteral::Null
}),
]
);
fn test_invalid_characters() {
assert_eq!(
result,
[
Ok(Token {
ttype: TokenType::Comma,
lexeme: String::from(","),
literal: String::from("null")
literal: TokenLiteral::Null
}),
Err(TokenError {
message: String::from("Unexpected character: @"),
line: 1,
}),
Ok(Token {
ttype: TokenType::Plus,
lexeme: String::from("+"),
literal: String::from("null")
literal: TokenLiteral::Null
}),
]
);
fn test_comment() {
assert_eq!(
result,
[Ok(Token {
ttype: TokenType::Comment,
lexeme: String::from("//"),
literal: String::from("null"),
literal: TokenLiteral::Null,
})]
);
fn test_newline() {
assert_eq!(
result,
[Ok(Token {
ttype: TokenType::Newline,
lexeme: String::from("\n"),
literal: String::from("null"),
literal: TokenLiteral::Null,
})]
);
fn test_string() {
assert_eq!(
result,
[Ok(Token {
ttype: TokenType::String,
lexeme: String::from("\"a string\""),
literal: String::from("a string"),
literal: TokenLiteral::String(String::from("a string")),
})]
);We can now add the logic to tokenise numbers. As we did many times, the first thing is to add a variant of TokenType that represents the lexeme we are implementing.
src/token.rs pub enum TokenType {
Newline,
Number,
Plus,
impl fmt::Display for TokenType {
Self::Newline => "NEWLINE",
Self::Number => "NUMBER",
Self::Plus => "PLUS",We should also add a new variant to TokenLiteral. As mentioned before, the introduction of an f64 forces us to remove the trait Eq from TokenLiteral and therefore from Token.
src/token.rs #[derive(Debug, PartialEq, Eq)]
#[derive(Debug, PartialEq)]
pub enum TokenLiteral {
Null,
Number(f64),
String(String),
}
impl fmt::Display for TokenLiteral {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::Null => write!(f, "null"),
Self::Number(n) => write!(f, "{n}"),
Self::String(s) => write!(f, "{s}"),
}
}
}
#[derive(Debug, PartialEq, Eq)]
#[derive(Debug, PartialEq)]
pub struct Token {
pub ttype: TokenType,
pub lexeme: String,
pub literal: TokenLiteral,
}To tokenise numbers we need to create a processing function similar to Tokenizer::string. Since numbers are more complicated, there are more corner cases to take into account.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
// Test the current characters and
// try to match the beginning of a number,
// with or without decimals.
fn number(&mut self) -> Option<TokenResult> {
// If the current character is None return None.
let c = self.current_character?;
// If the current character is not a digit return None.
if !c.is_ascii_digit() {
return None;
}
// Prepare the string with the initial digit.
let mut s = c.to_string();
loop {
// We already know the current character
// is part of the number, so let's start
// from the next one.
self.advance();
match self.current_character {
Some(v) => {
// The current character is a digit.
// We can store it and move on to
// the next character.
if v.is_ascii_digit() {
s.push(v);
continue;
}
// The current character is a dot.
// We should consider it only if the
// resulting string doesn't already
// contain a dot. Then we should check
// if it's followed by other numbers.
// If not, we stop here.
if v == '.' && !s.contains('.') {
match self.iter.peek() {
Some(p) if p.is_ascii_digit() => {
// The dot is part of the number
s.push(v);
continue;
}
_ => {
// The character after the dot is
// not a digit or there is nothing
// else to read. We can stop here.
break;
}
}
}
// The current character is neither a
// digit nor a dot followed by a digit,
// so we can stop here.
break;
}
None => {
// There is nothing left to read.
// We can stop here.
break;
}
}
}
// This removes multiple zeros after the dot.
let literal = TokenLiteral::Number(
s.parse::<f64>()
.expect("tokenizer produced an invalid number lexeme"),
);
// We don't need to advance as the current
// character is already something that doesn't
// belong to the number.
Some(Ok(Token {
ttype: TokenType::Number,
lexeme: s.clone(),
literal,
}))
}Let's have a look at it in detail as we did for Tokenizer::string.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
// Test the current characters and
// try to match the beginning of a number,
// with or without decimals.
fn number(&mut self) -> Option<TokenResult> {
// If the current character is None return None.
let c = self.current_character?; 1
// If the current character is not a digit return None.
if !c.is_ascii_digit() { 2
return None;
}
// Prepare the string with the initial digit.
let mut s = c.to_string();
loop { 3
...
}Once again, the function reads the current character, returning if it's None 1. It also checks if the character is a digit 2 with char::is_ascii_digit [docs] and returns if this is not the case. If none of those conditions are true the function starts a loop to collect all parts of the number.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
fn number(&mut self) -> Option<TokenResult> {
loop {
// We already know the current character
// is part of the number, so let's start
// from the next one.
self.advance();
match self.current_character {
Some(v) => { 1
// The current character is a digit.
// We can store it and move on to
// the next character.
if v.is_ascii_digit() { 2
s.push(v);
continue;
}
// The current character is a dot.
// We should consider it only if the
// resulting string doesn't already
// contain a dot. Then we should check
// if it's followed by other numbers.
// If not, we stop here.
if v == '.' && !s.contains('.') {
match self.iter.peek() { 3
Some(p) if p.is_ascii_digit() => { 4
// The dot is part of the number
s.push(v);
continue;
}
_ => { 5
// The character after the dot is
// not a digit or there is nothing
// else to read. We can stop here.
break;
}
}
}
// The current character is neither a
// digit nor a dot followed by a digit,
// so we can stop here.
break; 6
}
None => { 7
// There is nothing left to read.
// We can stop here.
break;
}
}
}The loop is similar to the one we implemented in Tokenizer::string, but with two important differences.
First of all, when we reach the character None 7 we can safely exit as a number doesn't have any closing character like a string. Second, processing a character 1 is more complicated.
If the character is a digit we add it to the number 2, no questions asked. If the character is a dot we need to call self.iter.peek() 3 to check what comes after it and decide if we must continue or stop. Please note that we must also check that the resulting string doesn't already contain a dot. If the character after the dot is a digit 4 we store the dot and continue, but in any other case 5 we should stop without considering the dot as part of the number. Likewise, if the character is neither a digit nor a dot we should stop 6.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
fn number(&mut self) -> Option<TokenResult> {
loop {
...
}
// This removes multiple zeros after the dot.
let literal = TokenLiteral::Number(
s.parse::<f64>()
.expect("tokenizer produced an invalid number lexeme"),
);
// We don't need to advance as the current
// character is already something that doesn't
// belong to the number.
Some(Ok(Token {
ttype: TokenType::Number,
lexeme: s.clone(),
literal,
}))
}The part after the loop is straightforward. Once we have all the characters of the number in a string we just need to make sure that the format is correct. In this case we just have a couple of rules to follow, enforced by the CodeCrafters tests:
42.000, the literal value of the token must have only one zero, e.g. 42.0.42 the literal value of the token must contain a decimal part, e.g. 42.0.Both requirements are satisfied by storing the literal as an actual f64 and by displaying TokenLiteral::Number in a specific way:
src/token.rs impl fmt::Display for TokenLiteral {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::Null => write!(f, "null"),
Self::Number(n) if n.fract() == 0.0 => write!(f, "{n:.1}"),
Self::Number(n) => write!(f, "{n}"),
Self::String(s) => write!(f, "{s}"),
}
}
}Since it's one of the requirements of the challenge, it is worth writing a test to check that the behaviour is correct:
src/token.rs #[cfg(test)]
mod tests {
use super::*;
#[test]
// Test that TokenLiteral::Number is
// displayed correctly when it contains
// an integer (the decimal part is zero).
fn test_token_literal_number_integer() {
let literal = TokenLiteral::Number(42.0);
assert_eq!(literal.to_string(), "42.0");
}
#[test]
// Test that TokenLiteral::Number is
// displayed correctly when it contains
// a float (the decimal part is not zero).
fn test_token_literal_number_float() {
let literal = TokenLiteral::Number(42.42);
assert_eq!(literal.to_string(), "42.42");
}
}We can write several tests to check the behaviour of the method Tokenizer::number. Namely, we can test what happens when there is no current character, when the current character is not a digit, and several combinations of digits, dots, and decimals.
src/tokenizer.rs mod tests {
#[test]
// Test that the method number
// behaves correctly when the tokeniser is not
// initialised and there is no current
// character.
fn test_number_no_current_character() {
let mut t = Tokenizer {
iter: "123".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
assert_eq!(t.number(), None);
}
#[test]
// Test that the method number
// behaves correctly when the tokeniser is
// initialised and there is a current
// character, but the character is
// not a digit.
fn test_number_no_digit() {
let mut t = Tokenizer {
iter: "characters".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(t.number(), None);
}
#[test]
// Test that the method number
// behaves correctly when the tokeniser is
// initialised and there is a current
// character, and the character is
// a single digit.
fn test_number_single_digit() {
let mut t = Tokenizer {
iter: "4".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.number(),
Some(Ok(Token {
ttype: TokenType::Number,
lexeme: String::from("4"),
literal: TokenLiteral::Number(4.0),
}))
);
}
#[test]
// Test that the method number
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// digits without a dot.
fn test_number_multiple_digits_without_dot() {
let mut t = Tokenizer {
iter: "4242".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.number(),
Some(Ok(Token {
ttype: TokenType::Number,
lexeme: String::from("4242"),
literal: TokenLiteral::Number(4242.0),
}))
);
}
#[test]
// Test that the method number
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// digits with a dot followed
// by non-digits.
fn test_number_multiple_digits_with_dot_without_decimals() {
let mut t = Tokenizer {
iter: "4242.characters".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.number(),
Some(Ok(Token {
ttype: TokenType::Number,
lexeme: String::from("4242"),
literal: TokenLiteral::Number(4242.0),
}))
);
}
#[test]
// Test that the method number
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// digits with a dot followed
// by other digits.
fn test_number_multiple_digits_with_dot_and_decimals() {
let mut t = Tokenizer {
iter: "4242.42".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.number(),
Some(Ok(Token {
ttype: TokenType::Number,
lexeme: String::from("4242.42"),
literal: TokenLiteral::Number(4242.42),
}))
);
}
#[test]
// Test that the method number
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// digits with multiple dots.
fn test_number_multiple_dots() {
let mut t = Tokenizer {
iter: "1.2.3".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.number(),
Some(Ok(Token {
ttype: TokenType::Number,
lexeme: String::from("1.2"),
literal: TokenLiteral::Number(1.2),
}))
);
}As we did before, we also want to test the behaviour of the iterator as a whole. Please note that we have an end-to-end test for the case of multiple dots as well.
src/tokenizer.rs mod iterator_tests {
#[test]
// Test the iterator end-to-end on
// a number with decimals.
fn test_number() {
let mut t = Tokenizer {
iter: "4242.42".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// Initialise the iterator
t.advance();
let mut result = Vec::<TokenResult>::new();
for token in &mut t {
result.push(token);
}
assert_eq!(
result,
[Ok(Token {
ttype: TokenType::Number,
lexeme: String::from("4242.42"),
literal: TokenLiteral::Number(4242.42),
})]
);
}
#[test]
// Test the iterator end-to-end on
// a number with multiple dots.
fn test_number_multiple_dots() {
let mut t = Tokenizer {
iter: "1.2.3".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// Initialise the iterator
t.advance();
let mut result = Vec::<TokenResult>::new();
for token in &mut t {
result.push(token);
}
assert_eq!(
result,
[
Ok(Token {
ttype: TokenType::Number,
lexeme: String::from("1.2"),
literal: TokenLiteral::Number(1.2),
}),
Err(TokenError {
message: "Unexpected character: .".to_string(),
line: 1
}),
Ok(Token {
ttype: TokenType::Number,
lexeme: String::from("3"),
literal: TokenLiteral::Number(3.0),
}),
]
);
}To complete the stage, we need to call number in Tokenizer::next.
src/tokenizer.rs impl<'a> Iterator for Tokenizer<'a> {
fn next(&mut self) -> Option<Self::Item> {
// If the current character is None return None.
let current = self.current_character?;
// Try to match a number.
if let Some(t) = self.number() {
return Some(t);
}
// Try to match a string.
if let Some(t) = self.string() {
return Some(t);
}The order of the processing functions is not important, as long as we call multi_character_token before single_character_token. The functions string and number can be called before or after them and in any order. This shows that in general the order of scanning functions matters, and unsurprisingly that the more specialised ones should be called first.
Stage 13 - Scanning: Number literals
This version of the code passes Stage 13 of the base CodeCrafters challenge.
We are approaching the end of our work on the scanner. In this stage we need to be able to create tokens for identifiers (variable names). Lox rules are those of many other programming languages: it accepts letters, numbers, and underscores in an identifier, but numbers cannot be the first character.
To create a processing function for identifiers we are going to closely follow what we did for strings and numbers. First of all, we need to create a new variant of TokenType.
src/token.rs pub enum TokenType {
GreaterEqual,
Identifier,
LBrace,
impl fmt::Display for TokenType {
Self::GreaterEqual => "GREATER_EQUAL",
Self::Identifier => "IDENTIFIER",
Self::LBrace => "LEFT_BRACE",Then we can add the following function to Tokenizer.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
// Test the current characters and
// try to match an identifier.
fn identifier(&mut self) -> Option<TokenResult> {
// If the current character is None return None.
let c = self.current_character?;
// If the current character is not a letter
// or an underscore return None.
if !c.is_ascii_alphabetic() && c != '_' {
return None;
}
let mut s = c.to_string();
loop {
// We already know the current character
// is part of the identifier, so let's start
// from the next one.
self.advance();
match self.current_character {
Some(v) => {
// After the first character (a letter
// or an underscore) we accept more letters,
// underscores, or numbers.
// If the character matches we can store it and
// move on to the next character.
if v.is_ascii_alphanumeric() || v == '_' {
s.push(v);
continue;
}
// The current character is neither a
// letter nor an underscore, so we can stop here.
break;
}
None => {
// There is nothing left to read.
// We can stop here.
break;
}
}
}
// We don't need to advance as the current
// character is already something that doesn't
// belong to the identifier
Some(Ok(Token {
ttype: TokenType::Identifier,
lexeme: s.clone(),
literal: TokenLiteral::Null,
}))
}As you can see, the structure is extremely similar to Tokenizer::string and Tokenizer::number. The first character is checked against ASCII alphabetic characters (char::is_ascii_alphabetic [docs]) and the underscore, according to the requirements, but for the remaining characters we can use char::is_ascii_alphanumeric [docs].
Once again, it's not important at which point we call Tokenizer::identifier in Tokenizer::next as there is no possible ambiguity.
src/tokenizer.rs impl<'a> Iterator for Tokenizer<'a> {
fn next(&mut self) -> Option<Self::Item> {
// If the current character is None return None.
let current = self.current_character?;
// Try to match an identifier.
if let Some(t) = self.identifier() {
return Some(t);
}
// Try to match a number.
if let Some(t) = self.number() {
return Some(t);
}As we did before, we can write tests for both the method identifier and for next. The logic behind identifier names produces several use cases, each corresponding to a test.
src/tokenizer.rs mod tests {
#[test]
// Test that the method identifier
// behaves correctly when the tokeniser is not
// initialised and there is no current
// character.
fn test_identifier_no_current_character() {
let mut t = Tokenizer {
iter: "foo".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
assert_eq!(t.identifier(), None);
}
#[test]
// Test that the method identifier
// behaves correctly when the tokeniser is
// initialised and there is a current
// character, but the character is
// not a letter or an underscore.
fn test_identifier_no_letter_or_underscore() {
let mut t = Tokenizer {
iter: "(".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(t.identifier(), None);
}
#[test]
// Test that the method identifier
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// an identifier that starts with
// a digit.
fn test_identifier_cannot_start_with_digit() {
let mut t = Tokenizer {
iter: "8foo".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(t.identifier(), None);
}
#[test]
// Test that the method identifier
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// an identifier that is made only
// of letters.
fn test_identifier_all_letters() {
let mut t = Tokenizer {
iter: "foo".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.identifier(),
Some(Ok(Token {
ttype: TokenType::Identifier,
lexeme: String::from("foo"),
literal: TokenLiteral::Null,
}))
);
}
#[test]
// Test that the method identifier
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// an identifier that starts with
// an underscore.
fn test_identifier_start_with_underscore() {
let mut t = Tokenizer {
iter: "_foo".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.identifier(),
Some(Ok(Token {
ttype: TokenType::Identifier,
lexeme: String::from("_foo"),
literal: TokenLiteral::Null,
}))
);
}
#[test]
// Test that the method identifier
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// an identifier that starts with a letter
// and is made of letters and digits.
fn test_identifier_can_contain_digits() {
let mut t = Tokenizer {
iter: "foo8".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.identifier(),
Some(Ok(Token {
ttype: TokenType::Identifier,
lexeme: String::from("foo8"),
literal: TokenLiteral::Null,
}))
);
}
mod iterator_tests {
#[test]
// Test the iterator end-to-end on
// an identifier.
fn test_identifier() {
let mut t = Tokenizer {
iter: "foo".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// Initialise the iterator
t.advance();
let mut result = Vec::<TokenResult>::new();
for token in &mut t {
result.push(token);
}
assert_eq!(
result,
[Ok(Token {
ttype: TokenType::Identifier,
lexeme: String::from("foo"),
literal: TokenLiteral::Null,
})]
);
}Stage 14 - Scanning: Identifiers
This version of the code passes Stage 14 of the base CodeCrafters challenge.
The final stage of the base challenge wants us to identify reserved words of the language. The challenge provides the full list, which is and, class, else, false, for, fun, if, nil, or, print, return, super, this, true, var, and while.
In principle this is almost a trivial change, as the only thing we need to do is to compare an identifier to a list of reserved words and emit the right type of token if there is a match. Keeping a list of reserved words is however a short-sighted choice.
Consider for example the following solution:
src/token.rs pub enum TokenType {
RParen,
Reserved(String),
Semicolon,This would easily lead to code like the following:
src/token.rs match &self.current_token().ttype {
TokenType::Reserved(s) => match s.as_str() {
"PRINT" => ...,
...
},
}As you can see, with this strategy our interpreter might have to match incoming tokens (source code) against the hardcoded copy of the reserved words.
This can be avoided using enums, so we are going to implement a solution that uses them. We will quickly run into a problem of code duplication and we will see a simple way to solve that as well.
Let's start by creating an enum for keywords and add a new variant to TokenType:
src/token.rs #[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Keyword {
And,
Class,
Else,
False,
For,
Fun,
If,
Nil,
Or,
Print,
Return,
Super,
This,
True,
Var,
While,
}
pub enum TokenType {
RBrace,
RParen,
Reserved(Keyword),
Semicolon,
Slash,The new variant of TokenType must of course be added to the implementation of fmt::Display. Here, we need to keep in mind that the string representation of a reserved word is the uppercase version of it, e.g. PRINT or WHILE. We can do that by implementing fmt::Display for Keyword:
src/token.rs impl fmt::Display for Keyword {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let name = match self {
Self::And => "and",
Self::Class => "class",
Self::Else => "else",
Self::False => "false",
Self::For => "for",
Self::Fun => "fun",
Self::If => "if",
Self::Nil => "nil",
Self::Or => "or",
Self::Print => "print",
Self::Return => "return",
Self::Super => "super",
Self::This => "this",
Self::True => "true",
Self::Var => "var",
Self::While => "while",
};
write!(f, "{}", name.to_uppercase())
}
}With this, Keyword receives to_string that we can use when representing a TokenType:
src/token.rs impl fmt::Display for TokenType {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
Self::RBrace => "RIGHT_BRACE",
Self::RParen => "RIGHT_PAREN",
Self::Reserved(s) => &s.to_string(),
Self::Semicolon => "SEMICOLON",
Self::Slash => "SLASH",With those changes in place, we can write the code that creates reserved word tokens. Reserved words are identifiers, so we need to detect them in the method Tokenizer::identifier. The problem we have, however, is how we can go from a string of text taken from the source code to a keyword. This can be easily solved by implementing FromStr [docs] for the enum:
src/token.rs use std::collections::HashMap;
use std::fmt;
use std::str::FromStr;
impl FromStr for Keyword {
type Err = ();
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"and" => Ok(Self::And),
"class" => Ok(Self::Class),
"else" => Ok(Self::Else),
"false" => Ok(Self::False),
"for" => Ok(Self::For),
"fun" => Ok(Self::Fun),
"if" => Ok(Self::If),
"nil" => Ok(Self::Nil),
"or" => Ok(Self::Or),
"print" => Ok(Self::Print),
"return" => Ok(Self::Return),
"super" => Ok(Self::Super),
"this" => Ok(Self::This),
"true" => Ok(Self::True),
"var" => Ok(Self::Var),
"while" => Ok(Self::While),
_ => Err(()),
}
}
}We can add tests for Keyword::from_str:
src/token.rs mod tests {
#[test]
// Test that a valid keyword string
// is converted into the corresponding
// Keyword variant.
fn test_keyword_from_str_valid() {
assert_eq!("while".parse::<Keyword>(), Ok(Keyword::While));
}
#[test]
// Test that a string that is not
// a keyword returns an error.
fn test_keyword_from_str_unknown() {
assert_eq!("foo".parse::<Keyword>(), Err(()));
}
#[test]
// Test that the conversion is
// case-sensitive, so the uppercase
// version of a keyword is not valid.
fn test_keyword_from_str_case_sensitive() {
assert_eq!("WHILE".parse::<Keyword>(), Err(()));
}
#[test]
// Test that an empty string
// returns an error.
fn test_keyword_from_str_empty() {
assert_eq!("".parse::<Keyword>(), Err(()));
}The trait FromStr that we implemented above is a bit different from other traits like fmt::Display because it has an explicit type declaration at the top. That declaration is called an associated type [docs] in Rust and is a convenient way to defer the choice of data types for method definitions.
In this case, the definition of FromStr taken from the source code is:
// SIMPLIFIED VERSION WITHOUT COMMENTS AND ATTRIBUTES
pub trait FromStr: Sized {
type Err;
fn from_str(s: &str) -> Result<Self, Self::Err>;
}The signature of from_str uses the associated type Err which is however not known at this time. When we implement the trait we therefore need to specify what concrete type to use.
The reason for associated types is that they become part of the trait implementation and do not have to be specified further. For example, let's have a look at the signature of str::parse [docs] which is the reason why we implemented FromStr in the first place:
pub fn parse<F>(&self) -> Result<F, <F as FromStr>::Err>
where
F: FromStr,which is the fully qualified version of:
pub fn parse<F: FromStr>(&self) -> Result<F, F::Err>As you can see, the function needs only a single parameter F, and F::Err is part of the type itself. If Err was a generic parameter we would have to specify that as well.
This has an important consequence: when a trait is given an associated type, the trait cannot be implemented multiple times for the same type. There will be only one implementation, with the given associated type, contrary to generics where the trait can be implemented multiple times with different types. In our case, Keyword is meant to receive only one implementation of FromStr with an associated type Err = ().
A good example of the generic type definition approach, instead, is the trait From [docs] that contains the generic type <T> and is supposed to be implemented multiple times. For example, we might implement From<String> and From<f64> for the same type.
Given what we said about generics, it is worth discussing why FromStr exists in the first place. Why not implement TryFrom<&str> [docs], which is the fallible equivalent of the trait From?
First of all, there are historical reasons. FromStr and str::parse have been present in Rust since version 1.0.0 (2015), while TryFrom was stabilised in 1.34.0 (2019). This means that for a long time FromStr was the only option and this is still considered idiomatic nowadays. Several Rust coders point out a difference in semantics, with FromStr explicitly meaning that a type can be parsed from text, and several libraries still explicitly use that trait for this purpose.
A very practical difference between FromStr::from_str and TryFrom<T>::try_from, moreover, is the way they deal with lifetimes. TryFrom accepts a generic type T, and this makes it possible to specify a lifetime (e.g. TryFrom<&'a str>) while FromStr doesn't allow it. This means that the result of TryFrom can be linked to the lifetime of the input, which ultimately means that the result can borrow the input, and thus be created with a zero-copy strategy.
This difference can be spotted in three different ways in the documentation, and it's useful to become used to such details in Rust:
Implementors of TryFrom lists several types that contain the same lifetime in input and output (e.g. impl<'a, T, const N: usize> TryFrom<&'a [T]> for &'a [T; N]), while the implementors of FromStr mention only owned types in their output.FromStr, look for does not have a lifetime parameter.You can immediately spot a duplication problem in the code above. It's clear that if we want to add a new keyword in the future we need to change both the implementation of FromStr and that of fmt::Display. In the next step we will implement a solution for this problem. With from_str, we can call str::parse::<Keyword> to go from the source code string to the enum variant:
src/tokenizer.rs use crate::token::{Token, TokenError, TokenLiteral, TokenResult, TokenType};
use crate::token::{Keyword, Token, TokenError, TokenLiteral, TokenResult, TokenType};
impl<'a> Tokenizer<'a> {
// Test the current characters and
// try to match an identifier.
// try to match an identifier or
// a reserved word.
fn identifier(&mut self) -> Option<TokenResult> {
// Check if this is a reserved word.
if let Ok(k) = s.parse::<Keyword>() {
return Some(Ok(Token {
ttype: TokenType::Reserved(k),
lexeme: s.clone(),
literal: TokenLiteral::Null,
}));
}
// We don't need to advance as the current
// character is already something that doesn't
// belong to the identifier
Some(Ok(Token {
ttype: TokenType::Identifier,
lexeme: s.clone(),
literal: TokenLiteral::Null,
}))We can also add two tests to check the new code. One test for the logic in the function Tokenizer::identifier and one for the iterator as a whole.
src/tokenizer.rs mod tests {
#[test]
// Test that the method number
// behaves correctly when the tokeniser is
// initialised, there is a current
// character, and the code contains
// an identifier that is a
// reserved word.
fn test_identifier_reserved_word() {
let mut t = Tokenizer {
iter: "while".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// This advances the iterator to the initial character
t.advance();
assert_eq!(
t.identifier(),
Some(Ok(Token {
ttype: TokenType::Reserved(Keyword::While),
lexeme: Keyword::While.to_string().to_lowercase(),
literal: TokenLiteral::Null,
}))
);
}
mod iterator_tests {
#[test]
// Test the iterator end-to-end on
// a reserved word.
fn test_reserved_word() {
let mut t = Tokenizer {
iter: "while".chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: HashMap::new(),
mc_lexemes: HashMap::new(),
};
// Initialise the iterator
t.advance();
let mut result = Vec::<TokenResult>::new();
for token in &mut t {
result.push(token);
}
assert_eq!(
result,
[Ok(Token {
ttype: TokenType::Reserved(Keyword::While),
lexeme: Keyword::While.to_string().to_lowercase(),
literal: TokenLiteral::Null,
})]
);
}Please note that we had to explicitly lowercase the string representation in the field lexeme of the Token. This problem will be solved in the next step as well.
Stage 15 - Scanning: Reserved words
This version of the code passes Stage 15 of the base CodeCrafters challenge.
While the code that we wrote in the previous step passes the challenge tests, there are a couple of improvements that can be made to it. The first problem is the duplication of the reserved words in string form, that are kept both in the implementation of FromStr and of fmt::Display, the second is the duplication of the lowercase logic in two tests (and potentially in other places in the future).
The first problem can be solved by moving the mapping between strings and variants in a const:
src/token.rs pub const KEYWORDS: &[(&str, Keyword)] = &[
("and", Keyword::And),
("class", Keyword::Class),
("else", Keyword::Else),
("false", Keyword::False),
("for", Keyword::For),
("fun", Keyword::Fun),
("if", Keyword::If),
("nil", Keyword::Nil),
("or", Keyword::Or),
("print", Keyword::Print),
("return", Keyword::Return),
("super", Keyword::Super),
("this", Keyword::This),
("true", Keyword::True),
("var", Keyword::Var),
("while", Keyword::While),
];We can at this point use the list to provide functions to perform the conversion between keywords and strings:
src/token.rs impl Keyword {
// This is the string representation of
// a keyword, that is how a keyword appears
// in the source code.
pub fn as_str(&self) -> &'static str {
KEYWORDS
// Iterate through all keywords.
.iter()
// Find the element that corresponds
// to the current variant.
.find(|(_, k)| k == self)
// Map the value we found,
// dereferencing the &str.
.map(|(s, _)| *s)
// Return the Some value or crash.
.expect("Keyword missing from KEYWORDS list")
}
}
impl FromStr for Keyword {
type Err = ();
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"and" => Ok(Self::And),
...
_ => Err(()),
}
KEYWORDS
// Iterate through all keywords.
.iter()
// Find the element that corresponds
// to the current string.
.find(|(name, _)| *name == s)
// Map the value we found,
// dereferencing the &Keyword.
.map(|(_, k)| *k)
// Convert the Option into a Result.
.ok_or(())
}
}
impl fmt::Display for Keyword {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let name = match self {
Self::And => "and",
...
Self::While => "while",
};
write!(f, "{}", name.to_uppercase())
write!(f, "{}", self.as_str().to_uppercase())
}
}Please note that the implementations of as_str and from_str are still mirroring each other, with the first mapping the string and the second mapping the keyword.
We can write a test for as_str:
src/token.rs mod tests {
#[test]
// Test that a keyword is converted
// into the corresponding string.
fn test_keyword_as_str() {
assert_eq!(Keyword::While.as_str(), "while");
}At this point, the second problem can be solved directly with a call to as_str() followed by a call to to_string(), but this might look a bit cumbersome, so we can create a test helper:
src/token.rs impl Keyword {
#[cfg(test)]
// Output the lexeme corresponding
// to the variant.
pub fn lexeme(&self) -> String {
self.as_str().to_string()
}And use it in the two tests that need access to the keyword's lexeme.
src/tokenizer.rs mod tests {
fn test_identifier_reserved_word() {
assert_eq!(
t.identifier(),
Some(Ok(Token {
ttype: TokenType::Reserved(Keyword::While),
lexeme: Keyword::While.to_string().to_lowercase(),
lexeme: Keyword::While.lexeme(),
literal: TokenLiteral::Null,
}))
);
mod iterator_tests {
fn test_reserved_word() {
assert_eq!(
result,
[Ok(Token {
ttype: TokenType::Reserved(Keyword::While),
lexeme: Keyword::While.to_string().to_lowercase(),
lexeme: Keyword::While.lexeme(),
literal: TokenLiteral::Null,
})]
);We are at the end of the scanning challenge. We created a tool that can analyse a text file and split it into tokens, and we are ready for the next part, where we will implement the parser.
Before we start working on a different component of the interpreter, it's useful to review the code we have written so far and make sure it's tidy. One thing that stands out is that main contains a lot of code and that there are no tests for it. Currently, the code reads a file, instantiates and initialises Tokenizer, collects all tokens and prints them. Definitely a lot of work for a single arm in a match construct.
Moreover, as mentioned before, there are no tests that verify that the code correctly removes certain tokens like comments. Last, EOF is not a token yet, but simply a printed string.
Let's start from this and create a variant of TokenType for it.
src/token.rs pub enum TokenType {
Equal,
EqualEqual,
Eof,
Greater,
GreaterEqual,
impl fmt::Display for TokenType {
Self::Equal => "EQUAL",
Self::EqualEqual => "EQUAL_EQUAL",
Self::Eof => "EOF",
Self::Greater => "GREATER",
Self::GreaterEqual => "GREATER_EQUAL",We can then move most of the code we wrote for the command tokenize in main into a new function.
src/tokenizer.rs use crate::token::{Keyword, Token, TokenError, TokenLiteral, TokenResult, TokenType};
use crate::token::{
build_lexemes_map, Keyword, Token, TokenError, TokenLiteral, TokenResult, TokenType,
MULTI_CHARACTER_LEXEMES, SINGLE_CHARACTER_LEXEMES,
};
pub fn tokenize(chars: Peekable<Chars>) -> Vec<TokenResult> {
// Create a new tokenizer and
// instantiate it with the content
// of the input file.
let mut t = Tokenizer {
iter: chars,
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: build_lexemes_map(SINGLE_CHARACTER_LEXEMES),
mc_lexemes: build_lexemes_map(MULTI_CHARACTER_LEXEMES),
};
// Initialise the iterator
t.advance();
// Filter out comments, whitespaces, and newlines
let filtered = t.filter(|i| {
i.as_ref().map_or(true, |token| {
!matches!(
token.ttype,
TokenType::Comment | TokenType::Whitespace | TokenType::Newline
)
})
});
// Collect the results in a vector
let mut results: Vec<TokenResult> = filtered.collect();
// Make sure the last token is the End Of File
results.push(Ok(Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
}));
results
}The function instantiates Tokenizer, initialises it, runs the iterator and collects filtered tokens into a vector, adding EOF as the final token.
The filter code deserves an explanation as it's not the most straightforward Rust code, at least for beginners like me. The problem is the following: we have an iterator that allows us to scan elements, and we want to keep only those that match a given condition. A natural way to write this is the following:
src/tokenizer.rs // Filter out comments, whitespaces, and newlines
let filtered = t.filter(|i| match i {
Ok(token) => match token.ttype {
TokenType::Comment => false,
TokenType::Whitespace => false,
TokenType::Newline => false,
_ => true,
},
Err(_) => true,
});We use Iterator::filter [docs] to create a new iterator that exposes only certain elements. The method receives a closure, so we define one that contains a match statement to return either true (expose the element) or false (hide the element). We want to keep all errors and all tokens whose ttype is not Comment, Whitespace, or Newline.
We can replace the external match statement with the method Result::map_or [docs]. The idea is simple: each element of the iterator is a TokenResult, we know this from the definition of Tokenizer:
src/tokenizer.rs impl<'a> Iterator for Tokenizer<'a> {
type Item = TokenResult;Since TokenResult is a Result we can call the method map_or that either applies a function to the value of the result if Ok or returns the default if Err.
src/tokenizer.rs let filtered = t.filter(|i| {
i.map_or(true, FUNCTION)
});Here, according to the documentation of Iterator::filter, i is a reference to an item (&Self::Item).
The function passed to map_or must therefore return true when the element must be kept and false if it has to be excluded. The Ok content of TokenResult is a Token, and we want to exclude the item if the field ttype is in a given list of values. This is a perfect job for the macro matches! [docs], so the function can be a simple closure.
src/tokenizer.rs let filtered = t.filter(|i| {
i.map_or(true, |token| {
!matches!(
...
)
})
});Please note that, since we want to exclude values, we use !matches! to negate the output of the macro. However, this syntax won't work, because map_or takes ownership of self, and so a move would occur. The problem is easily solved by working on a reference to the value instead of the value itself, and this can be created with Result::as_ref [docs], which is available because the variable i is &Self::Item, as stated before.
src/tokenizer.rs let filtered = t.filter(|i| {
i.as_ref().map_or(true, |token| {
!matches!(
...
)
})
});Now it's just a matter of coming up with the correct test for matches!. Internally, the macro uses a match statement roughly equivalent to the following:
src/tokenizer.rs macro_rules! matches {
($expression:expr, $pattern:pat) => {
match $expression {
$pattern => true,
_ => false
}
};
}You can see the actual implementation of the macro in the language source code [docs]. As for our function, we can extract the field ttype and compare it with a simple pattern:
src/tokenizer.rs pub fn tokenize(chars: Peekable<Chars>) -> Vec<TokenResult> {
// Initialise the iterator
t.advance();
// Filter out comments, whitespaces, and newlines
let filtered = t.filter(|i| {
i.as_ref().map_or(true, |token| {
!matches!(
token.ttype,
TokenType::Comment | TokenType::Whitespace | TokenType::Newline
)
})
});We can write a test for the logic implemented in tokenize.
src/tokenizer.rs #[cfg(test)]
mod tokenize_tests {
use super::*;
#[test]
// Test the function tokenize end-to-end.
fn test_tokenize() {
let results: Vec<TokenResult> = tokenize("for(==)".chars().peekable());
assert_eq!(
results,
[
Ok(Token {
ttype: TokenType::Reserved(Keyword::For),
lexeme: String::from("for"),
literal: TokenLiteral::Null,
}),
Ok(Token {
ttype: TokenType::LParen,
lexeme: String::from("("),
literal: TokenLiteral::Null,
}),
Ok(Token {
ttype: TokenType::EqualEqual,
lexeme: String::from("=="),
literal: TokenLiteral::Null,
}),
Ok(Token {
ttype: TokenType::RParen,
lexeme: String::from(")"),
literal: TokenLiteral::Null,
}),
Ok(Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
}),
]
);
}
}The code in main is going to reflect the changes done above. At this point we just need to call the function tokenize and to print the results. As we do not have an instance of Tokenizer available any more, we need to keep track of errors with a dedicated flag.
src/main.rs use crate::token::TokenType;
use crate::token::{build_lexemes_map, MULTI_CHARACTER_LEXEMES, SINGLE_CHARACTER_LEXEMES};
use crate::tokenizer::Tokenizer;
use crate::token::TokenResult;
use crate::tokenizer::tokenize;
fn main() {
match command.as_str() {
"tokenize" => {
// Open the input file and read the content.
let file_contents = fs::read_to_string(filename).unwrap_or_else(|_| {
eprintln!("Failed to read file {}", filename);
String::new()
});
// Create a new tokenizer and
// instantiate it with the content
// of the input file.
let mut t = Tokenizer {
iter: file_contents.chars().peekable(),
current_character: None,
current_line: 1,
errors: false,
sc_lexemes: build_lexemes_map(SINGLE_CHARACTER_LEXEMES),
mc_lexemes: build_lexemes_map(MULTI_CHARACTER_LEXEMES),
};
// Initialise the iterator
t.advance();
// Initialise the error flag.
let mut errors: bool = false;
// Process the file and extract the
// token results.
let results: Vec<TokenResult> = tokenize(file_contents.chars().peekable());
// Iterate on the tokenizer
// and process each result.
for token in &mut t {
match token {
Ok(token) => match token.ttype {
TokenType::Comment => continue,
TokenType::Whitespace => continue,
TokenType::Newline => continue,
_ => println!("{}", token),
},
Err(e) => {
eprintln!("{}", e);
}
}
}
// Iterate through the results and print
// them accordingly on the stdout or the
// stderr. Record if there are errors.
for result in results {
match result {
Ok(token) => println!("{}", token),
Err(e) => {
eprintln!("{}", e);
errors = true;
}
}
}
println!("EOF null");
if t.errors {
// In case there were errors
// exit with a specific code.
if errors {
process::exit(65);
}
}
_ => {
eprintln!("Unknown command: {}", command);
}
}
}Stage 15 - Scanning: Reserved words
As this was a pure refactoring, the code still passes Stage 15 of the base CodeCrafters challenge.