Lab 6: The Parser, Version 1 (Milestone 4)

Background

You will build terminal-protocol: a VT state machine that turns a byte stream into typed actions and knows nothing about screens. It is the most well-specified component in the whole curriculum — which means it is the one where "works" and "correct" can actually be distinguished, by tests.

Why This Lab Matters

• Every screen bug you chase for the rest of the curriculum will start with "is the parser producing the right actions?" If the answer is reliably yes, you halve your debugging surface.
• The split-input property is not optional, and only a state machine has it.
• This crate is the one that compiles to WebAssembly, gets fuzzed, and gets reused. It earns those properties by knowing nothing.

Prerequisites

• The Parser State Machine and UTF-8 and Graphemes read.
• A recording corpus to test against.

Predict First

1. Feed \x1b[31m one byte at a time. How many csi_dispatch calls should result?
2. Feed \x1b[38;5 (truncated) then \x1b[0m. How many dispatches?
3. Feed a 4-byte emoji split across two advance() calls. How many print calls?
4. Feed 100 KB of /dev/urandom. What is the worst thing that could happen?

Step 1: The Crate and the Public API

cargo new --lib crates/terminal-protocol --name terminal-protocol

[package]
name = "terminal-protocol"
version = "0.1.0"
edition = "2021"

[dependencies]
# NOTHING. This crate has no dependencies, and that is the point:
# it compiles for wasm32, for no_std targets with alloc, and everywhere else.

#![allow(unused)]
fn main() {
// crates/terminal-protocol/src/lib.rs
#![deny(missing_docs)]
//! A VT-style escape-sequence parser. Bytes in, structured actions out.
//!
//! This crate knows nothing about screens, cursors, colors, terminals, or I/O.
//! It reports that a CSI sequence with parameters `[2]` and final byte `J`
//! occurred; what that *means* is the consumer's business.

pub struct Parser { /* ... */ }

/// The consumer of parsed actions.
pub trait Perform {
    /// A printable character. Already UTF-8 decoded.
    fn print(&mut self, c: char);
    /// A C0 control byte to execute (LF, CR, BS, HT, BEL, ...).
    fn execute(&mut self, byte: u8);
    /// `CSI <params> <intermediates> <final>`.
    fn csi_dispatch(&mut self, params: &Params, intermediates: &[u8],
                    private: Option<u8>, action: char);
    /// `ESC <intermediates> <byte>`.
    fn esc_dispatch(&mut self, intermediates: &[u8], byte: u8);
    /// `OSC <params separated by ';'> ST`. Params are raw bytes: OSC payloads
    /// are not guaranteed to be valid UTF-8 (base64, URIs, binary).
    fn osc_dispatch(&mut self, params: &[&[u8]], bell_terminated: bool);
    /// DCS start. Payload arrives via `put`, then `unhook`.
    fn hook(&mut self, params: &Params, intermediates: &[u8],
            private: Option<u8>, action: char);
    /// One byte of a DCS payload.
    fn put(&mut self, byte: u8);
    /// End of a DCS payload.
    fn unhook(&mut self);
}

impl Parser {
    pub fn new() -> Self { /* ... */ }
    /// Feed bytes. May be called with any chunking, including one byte at a time.
    pub fn advance(&mut self, bytes: &[u8], perform: &mut impl Perform) {
        for &b in bytes { self.advance_byte(b, perform); }
    }
}
}

Why Perform is a trait rather than an enum-returning iterator: a trait lets the consumer own its state and mutate it directly, with no intermediate allocation. It is also what makes the tracing wrapper (Step 5) a five-line type. vte made the same choice, for the same reasons.

Step 2: States and Bounds

#![allow(unused)]
fn main() {
#[derive(Copy, Clone, PartialEq, Eq, Debug, Default)]
enum State {
    #[default] Ground,
    Escape,
    EscapeIntermediate,
    CsiEntry,
    CsiParam,
    CsiIntermediate,
    CsiIgnore,
    DcsEntry,
    DcsParam,
    DcsIntermediate,
    DcsPassthrough,
    DcsIgnore,
    OscString,
    /// Saw ESC inside a string state: if the next byte is '\', this is ST.
    StringEscape,
    SosPmApcString,
}

impl State {
    /// String states swallow C0 controls rather than executing them.
    fn is_string(self) -> bool {
        matches!(self, State::OscString | State::DcsPassthrough
                     | State::DcsIgnore | State::SosPmApcString)
    }
}

// Every bound here exists because a terminal parses UNTRUSTED input.
const MAX_PARAMS: usize = 16;
const MAX_SUBPARAMS: usize = 6;
const MAX_INTERMEDIATES: usize = 2;
const MAX_OSC_LEN: usize = 4096;
const MAX_OSC_PARAMS: usize = 16;
}

Step 3: The Transition Function

#![allow(unused)]
fn main() {
fn advance_byte(&mut self, byte: u8, perform: &mut impl Perform) {
    // ── Global rules. These apply from ANY state and give the parser its
    //    self-healing property on corrupt input. ─────────────────────────
    match byte {
        // ESC inside a string state might begin ST; that is handled by the
        // StringEscape state, so check it before the global rule.
        0x1b if self.state == State::StringEscape => {
            // ESC ESC: stay waiting for the terminator's second byte.
            return;
        }
        0x1b if self.state.is_string() => {
            self.state = State::StringEscape;
            return;
        }
        0x1b => {
            self.state = State::Escape;
            self.clear();
            return;
        }
        0x18 | 0x1a => {                 // CAN, SUB: abort to Ground
            self.state = State::Ground;
            self.clear();
            perform.execute(byte);
            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::EscapeIntermediate => self.escape_intermediate(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 => {
            // Swallow until a final byte, then return to Ground with no dispatch.
            if (0x40..=0x7e).contains(&byte) { self.state = State::Ground; }
        }
        State::OscString => self.osc_string(byte),
        State::StringEscape => {
            if byte == b'\\' {
                self.finish_string(perform);          // ESC \ = ST
            } else {
                // Not ST: the global ESC rule already fired conceptually.
                // Restart parsing from Escape with this byte.
                self.state = State::Escape;
                self.clear();
                self.advance_byte(byte, perform);
            }
        }
        State::DcsEntry | State::DcsParam | State::DcsIntermediate =>
            self.dcs_prefix(byte, perform),
        State::DcsPassthrough => perform.put(byte),
        State::DcsIgnore | State::SosPmApcString => { /* swallow */ }
    }
}

fn ground(&mut self, byte: u8, perform: &mut impl Perform) {
    // UTF-8 decoding lives HERE, inside Ground, and nowhere else. Putting it in
    // front of the state machine corrupts escape sequences and binary payloads.
    match self.utf8.feed(byte) {
        DecodeResult::Char(c) => perform.print(c),
        DecodeResult::Incomplete => {}                       // wait for more bytes
        DecodeResult::Invalid { resume_with } => {
            perform.print('\u{FFFD}');
            // The Unicode "maximal subpart" rule: the offending byte may start a
            // new valid sequence and must be reprocessed, not swallowed.
            if let Some(b) = resume_with {
                if let DecodeResult::Char(c) = self.utf8.feed(b) { perform.print(c); }
            }
        }
    }
}

fn csi_entry(&mut self, byte: u8, perform: &mut impl Perform) {
    match byte {
        // Private markers are ONLY valid as the first byte after CSI.
        0x3c..=0x3f => { self.private = Some(byte); self.state = State::CsiParam; }
        0x30..=0x39 | 0x3a | 0x3b => { self.param_byte(byte); self.state = State::CsiParam; }
        0x20..=0x2f => { self.push_intermediate(byte); self.state = State::CsiIntermediate; }
        0x40..=0x7e => { self.csi_dispatch(byte, perform); self.state = State::Ground; }
        0x7f => {}                                           // DEL: ignored
        _ => self.state = State::CsiIgnore,
    }
}

fn csi_param(&mut self, byte: u8, perform: &mut impl Perform) {
    match byte {
        0x30..=0x39 | 0x3a | 0x3b => self.param_byte(byte),
        0x20..=0x2f => { self.push_intermediate(byte); self.state = State::CsiIntermediate; }
        0x40..=0x7e => { self.csi_dispatch(byte, perform); self.state = State::Ground; }
        // A private marker AFTER a parameter is malformed: swallow the sequence.
        0x3c..=0x3f => self.state = State::CsiIgnore,
        0x7f => {}
        _ => self.state = State::CsiIgnore,
    }
}
}

Two implementation notes worth reading twice:

• param_byte must saturate. self.value = self.value.saturating_mul(10).saturating_add(d). A u16 multiply on 99999999999999 overflows and panics in debug, wraps in release. Both are wrong.
• Exceeding MAX_PARAMS sends you to CsiIgnore, not "silently drop the extras and dispatch." A sequence with 100 parameters is malformed; dispatching a truncated version of it is worse than ignoring it.

Step 4: Parameters with Sub-parameters

#![allow(unused)]
fn main() {
/// Bounded parameter storage supporting the colon sub-parameter form.
/// `38:5:196` is ONE parameter with three sub-parameters; `38;5;196` is three
/// parameters. Flattening the colon form breaks SGR 4:3 (curly underline).
#[derive(Default, Clone, PartialEq, Eq, Debug)]
pub struct Params {
    values: [u16; MAX_PARAMS * MAX_SUBPARAMS],
    /// Sub-parameter count for each parameter (>= 1 for a present parameter).
    counts: [u8; MAX_PARAMS],
    /// Whether each parameter slot was written at all (vs. empty → default).
    present: [bool; MAX_PARAMS],
    len: usize,
}

impl Params {
    pub fn len(&self) -> usize { self.len }
    pub fn is_empty(&self) -> bool { self.len == 0 }

    /// Parameter `i`, or `default` when absent or written empty.
    /// The "missing means DEFAULT, not 0" rule is enforced HERE so no caller
    /// can forget it. Never index the storage directly.
    pub fn get_or(&self, i: usize, default: u16) -> u16 {
        if i >= self.len || !self.present[i] { return default; }
        self.values[i * MAX_SUBPARAMS]
    }

    pub fn subparams(&self, i: usize) -> &[u16] {
        if i >= self.len { return &[]; }
        let start = i * MAX_SUBPARAMS;
        &self.values[start..start + self.counts[i] as usize]
    }
}
}

Step 5: The Tracing Wrapper (Instrumentation)

#![allow(unused)]
fn main() {
/// Wraps any Perform and logs every call before forwarding it.
/// This is `--debug-actions`, and it is how you will debug every screen bug for
/// the rest of the curriculum.
pub struct TracingPerform<'a, P: Perform, W: std::io::Write> {
    inner: &'a mut P,
    out: W,
}

impl<P: Perform, W: std::io::Write> Perform for TracingPerform<'_, P, W> {
    fn print(&mut self, c: char) {
        let _ = writeln!(self.out, "PRINT   {:?}  U+{:04X}", c, c as u32);
        self.inner.print(c);
    }
    fn execute(&mut self, byte: u8) {
        let _ = writeln!(self.out, "EXECUTE {:#04x}  {}", byte, c0_name(byte));
        self.inner.execute(byte);
    }
    fn csi_dispatch(&mut self, params: &Params, intermediates: &[u8],
                    private: Option<u8>, action: char) {
        let _ = writeln!(self.out, "CSI     private={:?} params={:?} inter={:?} final={:?}",
                         private.map(|b| b as char), params, intermediates, action);
        self.inner.csi_dispatch(params, intermediates, private, action);
    }
    // ... the rest, identically.
}
}

Tip: Write this in the same session as the parser, not later. Debugging a state machine without a trace of its transitions is a waste of an afternoon, every single time.

Step 6: Run It

# Trace a real program's output:
pty-runner --record ls.cast -- ls --color=always
terminal-debugger actions ls.cast | head -40

Expected Output

$ terminal-debugger actions ls.cast | head -20
CSI     private=None params=[0] inter=[] final='m'
PRINT   'C'  U+0043
PRINT   'a'  U+0061
PRINT   'r'  U+0072
PRINT   'g'  U+0067
PRINT   'o'  U+006F
PRINT   '.'  U+002E
PRINT   't'  U+0074
...
EXECUTE 0x0d  CR
EXECUTE 0x0a  LF
CSI     private=None params=[1, 34] inter=[] final='m'
PRINT   's'  U+0073
PRINT   'r'  U+0073
PRINT   'c'  U+0063
CSI     private=None params=[0] inter=[] final='m'
EXECUTE 0x0d  CR
EXECUTE 0x0a  LF

Debugging Steps

The split-input test fails

You are accumulating state somewhere that resets on the advance() boundary rather than persisting across calls. Usual suspects: the UTF-8 partial buffer, or the parameter accumulator being cleared at the start of advance rather than on ESC.

An emoji shows as two replacement characters

The UTF-8 decoder is emitting U+FFFD for an incomplete sequence at the end of a chunk instead of buffering it. See UTF-8 and Graphemes.

\x1b[38:5:196m gives three parameters

You are treating : like ;. Colons build sub-parameters within the current parameter.

A recording hangs the parser

An unterminated OSC or DCS with no length cap. Add the bound.

Fuzzing finds a panic

Almost always one of: parameter overflow (saturating_*), a slice index out of bounds in subparams, or a char::from_u32().unwrap() in the UTF-8 path.

Experiment

CLAIM. A starts_with-based parser passes all naïve tests and fails on real input, because real input splits.

METHOD. Write a deliberately naïve parser (30 lines, matching \x1b[ prefixes on a buffer), run your golden corpus through it in one chunk — it will pass — then run the same corpus in replay_output_bytewise mode.

PREDICTION. Before running: what fraction of the corpus produces different output in bytewise mode? Which sequence type fails first?

RESULT. Record it. Then delete the naïve parser; you have made the point.

Test

#![allow(unused)]
fn main() {
#[test]
fn split_input_equivalence_over_the_whole_corpus() {
    // THE test. Every recording, both chunkings, identical action streams.
    for case in golden_corpus() {
        let whole = collect_actions_chunked(&case.bytes, usize::MAX);
        let single = collect_actions_chunked(&case.bytes, 1);
        assert_eq!(whole, single, "split mismatch in {}", case.name);
        // Also test a few awkward chunk sizes — 3 and 7 catch different bugs
        // than 1 does, because they land mid-parameter rather than mid-sequence.
        for n in [2usize, 3, 7, 13] {
            assert_eq!(whole, collect_actions_chunked(&case.bytes, n),
                       "chunk size {n} mismatch in {}", case.name);
        }
    }
}

#[test]
fn ground_state_utf8_does_not_consume_escape_bytes() {
    // If the decoder sat in front of the parser, 0x1b would be swallowed as
    // part of a decode attempt after an invalid lead byte.
    let actions = collect_actions(&[&[0xC3, 0x1b, b'[', b'3', b'1', b'm']]);
    assert!(matches!(actions[0], Action::Print('\u{FFFD}')));
    assert!(matches!(actions[1], Action::Csi { .. }),
            "the escape sequence must survive an invalid UTF-8 lead byte");
}

#[test]
fn csi_ignore_swallows_the_whole_malformed_sequence() {
    let actions = collect_actions(&[b"\x1b[1\x3fHX"]);
    assert_eq!(actions, vec![Action::Print('X')]);
}

#[test]
fn parser_state_is_bounded_regardless_of_input() {
    // Memory must not grow with input size. Feed 10 MB of adversarial input and
    // check the parser's own footprint is unchanged.
    let before = std::mem::size_of::<Parser>();
    let mut p = Parser::new();
    let mut sink = NullPerform;
    for _ in 0..100_000 {
        p.advance(b"\x1b[1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20", &mut sink);
        p.advance(b"\x1b]0;", &mut sink);
        p.advance(&[b'A'; 100], &mut sink);
    }
    assert_eq!(std::mem::size_of::<Parser>(), before);
}
}

cargo test -p terminal-protocol

Fuzzing (Required, Not Optional)

cargo install cargo-fuzz
cargo fuzz init -p terminal-protocol

#![allow(unused)]
fn main() {
// fuzz/fuzz_targets/parse.rs
#![no_main]
use libfuzzer_sys::fuzz_target;

fuzz_target!(|data: &[u8]| {
    let mut parser = terminal_protocol::Parser::new();
    let mut sink = NullPerform;
    // Feed in adversarial chunkings, not just one slice — chunk boundaries are
    // where state-machine bugs hide.
    for chunk in data.chunks(1) { parser.advance(chunk, &mut sink); }
    let mut parser2 = terminal_protocol::Parser::new();
    parser2.advance(data, &mut sink);
});
}

cargo fuzz run parse -- -max_total_time=600

The fuzz target asserts only three things: no panic, no hang, no unbounded memory. It is not checking correctness — it is checking that a terminal fed hostile bytes does not become a liability. Commit the corpus.

Challenge Extensions

1. Add the split-input assertion to the fuzz target itself: collect actions both ways and assert equality. Now the fuzzer hunts for chunking bugs directly.
2. Port to a transition table and benchmark on 10 MB. Report the speedup and whether the readability cost was worth it.
3. Differential-test against vte. Same corpus, compare action streams. Document every difference as either your bug or a deliberate divergence.
4. no_std + alloc. Make the crate build without std, proving it has no hidden OS dependencies.
5. Compile to wasm32-unknown-unknown and run the test suite under wasm-pack test. This is the Milestone 13 criterion, arriving early.

Deliverables

• terminal-protocol with zero dependencies, implementing the full state machine.
• The split-input test passing over the whole golden corpus at chunk sizes 1, 2, 3, 7, 13, and ∞.
• All bounds enforced (params, sub-params, intermediates, OSC length, OSC params).
• TracingPerform implemented and wired to terminal-debugger actions.
• A fuzz target that has run ≥10 minutes clean, with the corpus committed.
• Every sequence in the CSI catalog produces the correct dispatch, with a test each.
• cargo build --target wasm32-unknown-unknown -p terminal-protocol succeeds.

Validation / Self-check

1. Name every state and the byte that enters it.
2. Why does Perform take a char in print and &[u8] in osc_dispatch?
3. Where does UTF-8 decoding happen, and what breaks if it happens earlier?
4. What is the split-input property, and what chunk sizes should you test?
5. Why does exceeding MAX_PARAMS go to CsiIgnore rather than dispatching a truncated sequence?
6. Why must parameter accumulation saturate?
7. Why is get_or the only way to read a parameter?
8. What three things does the fuzz target assert, and what does it deliberately not check?
9. \x1b[1?H arrives. Trace the state transitions.
10. Why does this crate have no dependencies, and what capability does that buy?

Next: Lab 7 — The Screen Grid.