Projects · about 60 min

Project: A State Machine for CSV

Why this matters

Many programs are naturally described as state machines: a traffic light, a vending machine, a network protocol, a text parser. The program is always in one of a few states, and each input moves it to a next state, possibly doing something along the way. Rust's enums and exhaustive match are an excellent fit: states become variants, transitions become match arms, and the compiler checks that you handled every combination. This project builds a parser for CSV lines with quoted fields, a classic problem where ad-hoc code with flags gets subtly wrong.

The problem

CSV (comma-separated values) looks trivial until a field contains a comma:

name,age,city
"Smith, Jane",42,"New York"
"She said ""hi""",7,

Quoted fields may contain commas, and "" inside quotes means a literal quote. line.split(',') breaks "Smith, Jane" in two, so we need to process the line character by character, remembering where we are: that memory is the state.

Designing the states

Think about what the parser must know at each character:

FieldStart     -- at the beginning of a field (start of line, or just after a comma)
Unquoted       -- inside an unquoted field
Quoted         -- inside a quoted field
QuoteInQuoted  -- inside a quoted field, just saw a quote: either "" (escaped) or the closing quote

The transitions, as a table (input on the left, state across the top):

input   | FieldStart        | Unquoted          | Quoted            | QuoteInQuoted
--------+-------------------+-------------------+-------------------+------------------------
  "     | -> Quoted         | error             | -> QuoteInQuoted  | push '"', -> Quoted
  ,     | end field         | end field         | push ',', stay    | end field
        |  -> FieldStart    |  -> FieldStart    |                   |  -> FieldStart
 other  | push, -> Unquoted | push, stay        | push, stay        | error
end of  | end field (empty) | end field         | error: unterminated | end field
 line   |                   |                   |                   |

Drawing this table before coding is the main design work. Every cell has an answer, including the errors and end of input.

From table to code

#[derive(Debug, Clone, Copy, PartialEq)]
enum State {
    FieldStart,
    Unquoted,
    Quoted,
    QuoteInQuoted,
}

fn parse(line: &str) -> Result<Vec<String>, String> {
    let mut fields = Vec::new();
    let mut field = String::new();
    let mut state = State::FieldStart;
    for (i, c) in line.chars().enumerate() {
        state = match (state, c) {
            (State::FieldStart, '"') => State::Quoted,
            (State::FieldStart | State::Unquoted, ',') => {
                fields.push(std::mem::take(&mut field));
                State::FieldStart
            }
            (State::Unquoted, '"') => return Err(format!("unexpected quote at column {}", i + 1)),
            (State::FieldStart | State::Unquoted, ch) => {
                field.push(ch);
                State::Unquoted
            }
            (State::Quoted, '"') => State::QuoteInQuoted,
            (State::Quoted, ch) => {
                field.push(ch);
                State::Quoted
            }
            (State::QuoteInQuoted, '"') => {
                field.push('"');
                State::Quoted
            }
            (State::QuoteInQuoted, ',') => {
                fields.push(std::mem::take(&mut field));
                State::FieldStart
            }
            (State::QuoteInQuoted, ch) => {
                return Err(format!("unexpected character '{ch}' after closing quote at column {}", i + 1))
            }
        };
    }
    if state == State::Quoted {
        return Err(String::from("unterminated quote"));
    }
    fields.push(field);
    Ok(fields)
}

fn main() {
    for line in ["a,b,c", "\"Smith, Jane\",42", "\"say \"\"hi\"\"\",,x", "ab\"c", "\"oops"] {
        println!("{line:24} -> {:?}", parse(line));
    }
}

a,b,c                    -> Ok(["a", "b", "c"])
"Smith, Jane",42         -> Ok(["Smith, Jane", "42"])
"say ""hi""",,x          -> Ok(["say \"hi\"", "", "x"])
ab"c                     -> Err("unexpected quote at column 3")
"oops                    -> Err("unterminated quote")

Points worth noticing:

match (state, c) matches on a tuple of the current state and the input: each arm is one cell (or a group of cells) of the table. Arm order matters where patterns overlap: (Unquoted, '"') must come before the catch-all (FieldStart | Unquoted, ch).
The match is an expression producing the next state, assigned back to state. Arms that hit an error return immediately.
std::mem::take(&mut field) moves the String out and leaves an empty one behind: no clone, no reallocation of a new buffer for the finished field.
End of input is handled after the loop. It is part of the machine and easy to forget: a line ending in Quoted state is an error; otherwise the last field is pushed (which also makes "", the empty line, one empty field).
Error positions come from enumerate() over chars(), so they count characters, not bytes: correct for non-ASCII text.

Why not booleans?

The same parser could be written with in_quotes: bool and prev_was_quote: bool. Two booleans make four combinations; one of them (!in_quotes && prev_was_quote) is meaningless, yet nothing stops the code from reaching it. Each if must reason about all flags at once. With an enum there are exactly four states, each with a name, and the compiler checks the match for exhaustiveness: remove an arm and you get E0004 listing the missing (state, char) combination.

Testing a parser

Parsers are ideal for unit tests: a string in, a result out. Good cases come straight from the table: one per cell, plus end of input in each state:

""                -> [""]                 empty line: one empty field
"a,"              -> ["a", ""]            trailing comma
"\"\",x"          -> ["", "x"]            empty quoted field
"\"a\"\"b\""      -> ["a\"b"]             escaped quote
"\"ab\"c"         -> error at column 5    junk after closing quote
"é\"x"            -> error at column 2    columns count characters

The exercise's hidden tests use exactly these.

Extensions to try

Support a configurable separator (; or tab) by making it a parameter.
Quoted fields spanning several lines: the state must survive across read_line calls, so the machine becomes a struct with a feed(&mut self, line: &str) method.
Trim spaces around unquoted fields, and decide (and document) what a space before an opening quote means.

Recap

A state machine is a set of states, inputs, and transitions; draw the table first, including errors and end of input.
Represent states with an enum, transitions with match (state, input) returning the next state.
Exhaustive matching makes the compiler check that every combination is handled.
Handle end of input explicitly after the loop.
Each table cell is a test case.

Going further: model a vending machine (states Idle, HasMoney(u32), Vending) with events like Coin(u32), Select(item), Refund, as an enum of events and a fn step(self, event: Event) -> State method.

Exercises

Exercise 1 · write code

Parse CSV with quotes

Write fn parse_line(line: &str) -> Result<Vec<String>, String> as a character-by-character state machine with an enum of states. The rules:

Fields are separated by commas. Empty fields are allowed (a,,b has three fields; an empty line is one empty field).
A field may be quoted with double quotes, if the quote is the first character of the field. Inside quotes, commas are ordinary characters and "" stands for one ".
After a closing quote, only a comma or the end of the line may follow; anything else is an error unexpected character 'C' after closing quote at column N (N is the 1-based character position of C).
A quote appearing in the middle of an unquoted field is an error unexpected quote at column N.
A line ending inside a quoted field is an error unterminated quote.

The given main reads lines from stdin and prints each result as N fields: [...] (Debug of the Vec) or error: MESSAGE:

3 fields: ["name", "age", "city"]
2 fields: ["Smith, Jane", "said \"hi\""]
3 fields: ["a", "", "b"]
error: unexpected quote at column 3
error: unterminated quote

for the lines name,age,city, "Smith, Jane","said ""hi""", a,,b, ab"c, "open.

File: main.rs

Starting point

use std::io;

fn parse_line(line: &str) -> Result<Vec<String>, String> {
    Ok(line.split(',').map(|s| s.to_string()).collect())
}

fn main() {
    for line in io::stdin().lines() {
        let line = line.unwrap();
        match parse_line(&line) {
            Ok(fields) => println!("{} fields: {:?}", fields.len(), fields),
            Err(e) => println!("error: {e}"),
        }
    }
}

Example

input

name,age,city
"Smith, Jane","said ""hi"""
a,,b
ab"c
"open

expected output

3 fields: ["name", "age", "city"]
2 fields: ["Smith, Jane", "said \"hi\""]
3 fields: ["a", "", "b"]
error: unexpected quote at column 3
error: unterminated quote

Hint 1

Four states are enough: FieldStart, Unquoted, Quoted, and QuoteInQuoted (just saw a quote inside a quoted field: it is either an escaped quote or the closing one).

Hint 2

Write the transitions as state = match (state, c) { (State::FieldStart, '"') => State::Quoted, ... }; finishing a field is fields.push(std::mem::take(&mut field)).

Hint 3

After the loop: if the state is Quoted, the quote never closed; otherwise push the last field.

Reference solution

use std::io;

#[derive(Clone, Copy, PartialEq)]
enum State {
    FieldStart,
    Unquoted,
    Quoted,
    QuoteInQuoted,
}

fn parse_line(line: &str) -> Result<Vec<String>, String> {
    let mut fields = Vec::new();
    let mut field = String::new();
    let mut state = State::FieldStart;
    for (i, c) in line.chars().enumerate() {
        let col = i + 1;
        state = match (state, c) {
            (State::FieldStart, '"') => State::Quoted,
            (State::FieldStart, ',') | (State::Unquoted, ',') => {
                fields.push(std::mem::take(&mut field));
                State::FieldStart
            }
            (State::FieldStart, ch) | (State::Unquoted, ch) if ch != '"' => {
                field.push(ch);
                State::Unquoted
            }
            (State::Unquoted, _) => return Err(format!("unexpected quote at column {col}")),
            (State::Quoted, '"') => State::QuoteInQuoted,
            (State::Quoted, ch) => {
                field.push(ch);
                State::Quoted
            }
            (State::QuoteInQuoted, '"') => {
                field.push('"');
                State::Quoted
            }
            (State::QuoteInQuoted, ',') => {
                fields.push(std::mem::take(&mut field));
                State::FieldStart
            }
            (State::QuoteInQuoted, ch) => {
                return Err(format!("unexpected character '{ch}' after closing quote at column {col}"))
            }
            (State::FieldStart, _) => unreachable!(),
        };
    }
    if state == State::Quoted {
        return Err(String::from("unterminated quote"));
    }
    fields.push(field);
    Ok(fields)
}

fn main() {
    for line in io::stdin().lines() {
        let line = line.unwrap();
        match parse_line(&line) {
            Ok(fields) => println!("{} fields: {:?}", fields.len(), fields),
            Err(e) => println!("error: {e}"),
        }
    }
}

Exercise 2 · quiz

Why an explicit state enum?

Compared with a loop full of boolean flags (in_quotes, just_saw_quote, ...), what does an explicit enum State with a match (state, c) give you? Select all that apply.

Impossible combinations (like in_quotes = false and just_saw_quote = true) cannot be represented
The compiler checks that every (state, input) combination is handled
Each transition is visible as one match arm, which reads like the state diagram
It removes the need to handle the end of input

Answer

Impossible combinations (like in_quotes = false and just_saw_quote = true) cannot be represented
The compiler checks that every (state, input) combination is handled
Each transition is visible as one match arm, which reads like the state diagram

With n booleans there are 2^n combinations, most of them meaningless; an enum has exactly the states you named. A match on (state, input) must be exhaustive, so forgetting a case is a compile error. End of input is still a separate step: after the loop you must decide what each final state means (here, Quoted is an error).