Project 2: Escape Sequence Parser

Build a streaming ANSI/VT parser that turns raw bytes into deterministic terminal actions, even when sequences are split across reads.

Quick Reference

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate 1-2 weeks
Main Programming Language C (Alternatives: Rust, Go)
Alternative Programming Languages Rust, Go
Coolness Level Level 3: Genuinely Clever
Business Potential Level 1: Resume Gold
Prerequisites Basic C, byte handling, simple state machines
Key Topics ECMA-48, ANSI/VT, streaming parsing, error recovery

1. Learning Objectives

By completing this project, you will:

  1. Parse ESC/CSI/OSC/DCS sequences incrementally without losing bytes.
  2. Emit structured actions with defaults that match terminal behavior.
  3. Recover from malformed sequences without corrupting the stream.
  4. Design a parser API that is easy to integrate into a terminal emulator.
  5. Build deterministic tests that verify parser output across edge cases.

2. All Theory Needed (Per-Concept Breakdown)

Concept 1: ECMA-48 and ANSI/VT Escape Sequence Structure

Fundamentals

Terminal escape sequences are a compact byte-level protocol. Most begin with ESC (0x1B) and fall into families such as CSI (Control Sequence Introducer), OSC (Operating System Command), and DCS (Device Control String). CSI sequences generally look like ESC [ params intermediates final, where params are digits separated by semicolons, intermediates are optional bytes in the 0x20-0x2F range, and the final byte determines the action. OSC sequences are strings terminated by BEL (0x07) or ST (ESC \). Understanding this grammar is essential because terminals must parse byte streams that mix printable characters with control sequences and still maintain deterministic behavior.

Deep Dive into the Concept

The ECMA-48 standard defines how control functions are encoded in byte streams. The CSI family is the most common: it starts with ESC [ and ends with a final byte in the range 0x40-0x7E. Parameters are optional and default to zero or one depending on the command. For example, CSI J clears the screen with default parameter 0, while CSI 2 J clears the entire screen. Missing parameters are not errors; they are defaults. This makes parsing tricky because you must distinguish between “parameter omitted” and “parameter value 0” semantics.

OSC sequences are even more subtle. They begin with ESC ] followed by a numeric code, a semicolon, and arbitrary string data. They terminate on BEL or ST. This means you can receive arbitrary bytes, including ESC, inside the payload, and you must only treat an ESC as a terminator if it is followed by \. DCS sequences begin with ESC P and terminate with ST as well; they are used for more complex protocols like sixel or device queries. A parser must therefore be aware of multiple termination rules and must avoid premature termination when bytes look like control characters inside a string.

ANSI/VT compatibility adds historical behavior. VT100 and xterm have quirks like private modes (CSI ?), parameter defaults, and nonstandard sequences. For instance, ESC [ ? 25 h shows the cursor, while ESC [ ? 25 l hides it. These are not part of strict ECMA-48 but are widely used. A practical parser must identify these sequences and emit actions that preserve compatibility. This requires a grammar that is flexible enough to accept private prefixes (?, >), intermediates, and unusual final bytes.

Finally, consider printable text. Bytes in the ASCII printable range (0x20-0x7E) should be treated as characters and emitted as text runs for performance, rather than as single-character actions. Many terminal emulators scan for runs of printable bytes and emit them as a single “print” action, which reduces overhead. The parser must therefore handle both control sequences and high-throughput text in the same streaming loop.

How this fits on projects

This concept is essential for this project and is reused in P04, P05, P07, and P13.

Definitions & Key Terms

  • ESC (0x1B) -> escape byte that starts most control sequences.
  • CSI -> Control Sequence Introducer, ESC [.
  • OSC -> Operating System Command, ESC ] … BEL/ST.
  • DCS -> Device Control String, ESC P … ST.
  • ST -> String Terminator, ESC \\.
  • Final byte -> determines the action of a CSI sequence.

Mental Model Diagram (ASCII)

Byte stream:  text text ESC [ 3 1 m text ESC ] 8 ; url ST
                 |        |--- CSI ----|             |-- OSC --|

How It Works (Step-by-Step)

  1. Read bytes from the stream.
  2. If byte is ESC, transition into an escape state.
  3. If next byte is [, parse CSI parameters until final byte.
  4. If next byte is ], parse OSC string until BEL or ST.
  5. If next byte is P, parse DCS until ST.
  6. Otherwise, treat bytes as printable text runs.

Invariants:

  • CSI parsing ends only on a valid final byte.
  • OSC/DCS parsing ends only on BEL or ST.
  • Text runs must not swallow ESC bytes.

Failure modes:

  • Treating ESC inside OSC as terminator when it is payload.
  • Dropping bytes when a sequence spans buffers.
  • Misapplying defaults for missing parameters.

Minimal Concrete Example

// Example: parse "ESC [ 2 J" into {kind: CSI, params:[2], final:'J'}
if (b == 0x1b) state = ESC;
else if (state == ESC && b == '[') state = CSI;
// ... collect params until final in 0x40..0x7E

Common Misconceptions

  • “ESC sequences are single bytes.” -> Most are multi-byte sequences.
  • “Missing params are errors.” -> They default; behavior depends on command.
  • “OSC ends at ESC.” -> It ends at BEL or ST, not a bare ESC.

Check-Your-Understanding Questions

  1. What makes CSI parameters different from intermediates?
  2. How do you detect the end of an OSC sequence?
  3. Why must you treat private mode prefixes (e.g., ?) specially?

Check-Your-Understanding Answers

  1. Parameters are digits and semicolons; intermediates are 0x20-0x2F bytes.
  2. OSC ends at BEL (0x07) or ST (ESC \\).
  3. They indicate vendor-private behavior; the final byte alone is not enough.

Real-World Applications

  • Parsing output from vim, htop, and tmux
  • Terminal testing tools like vttest
  • Web terminals like xterm.js

Where You’ll Apply It

References

  • ECMA-48 standard (control functions)
  • xterm control sequence documentation
  • “Terminal User Guide” (DEC VT100 family)

Key Insight

A terminal parser is a deterministic decoder for a loosely specified byte protocol.

Summary

You must treat escape sequences as a formal grammar with strict termination rules and default parameters.

Homework/Exercises to Practice the Concept

  1. Write a small script that emits CSI and OSC sequences and log them as bytes.
  2. Manually decode ESC [ ? 25 l and explain its effect.
  3. Trace how ESC ] 0 ; title BEL should be parsed.

Solutions to the Homework/Exercises

  1. Use printf with \033 and \007 and inspect with xxd.
  2. It is a private mode CSI that hides the cursor.
  3. It is OSC code 0 with payload “title”, terminated by BEL.

Concept 2: Streaming Parsing, State Machines, and Error Recovery

Fundamentals

Terminal output arrives as a continuous byte stream that can be split across reads arbitrarily. A parser therefore cannot assume it sees complete sequences in one buffer. A streaming parser maintains state across reads and can pause midway through a sequence until more bytes arrive. State machines are the canonical way to model this: each byte transitions the parser to a new state, and when a complete sequence is recognized, the parser emits an action. Error recovery ensures malformed sequences do not permanently corrupt parser state.

Deep Dive into the Concept

A streaming parser must treat input as an infinite sequence rather than discrete messages. In practice, you read from the PTY master in chunks (e.g., 4 KB) and pass the bytes through a parser that can pause in the middle of a CSI or OSC. This requires a state machine that persists between calls. The parser must track: current state, partially parsed parameters, any accumulated string for OSC/DCS, and whether the current sequence has exceeded maximum length. The simplest model uses states like GROUND, ESC, CSI, OSC, and DCS. Transitions are defined by the current byte and the current state.

Error recovery matters because terminal output is not always valid. Programs can emit incomplete or malformed sequences; logs can be truncated; networked terminals can drop bytes. If the parser remains stuck in a bad state, all subsequent output becomes garbage. A robust parser therefore defines timeouts or length caps for string-based sequences, and it defines recovery transitions: for example, if an OSC sequence exceeds a maximum length, you may treat it as text and return to GROUND. For CSI sequences, if you encounter a byte that cannot be part of the sequence, you can emit a “malformed” action and reset to GROUND.

Performance is also important. Most terminal output is printable text, not control sequences. A parser that emits one action per byte wastes CPU. Many terminals use a “fast path” that scans for runs of printable bytes and emits them as a single text action. This can be done by scanning until an ESC or control byte is found. The parser then emits the text run and resumes normal parsing. This hybrid strategy maintains correctness while improving throughput.

Finally, a streaming parser must be deterministic and testable. To do that, you define an action schema (e.g., Action::Print(text), Action::CSI(params, final), Action::OSC(code, payload)), and you ensure that feeding the same byte stream always produces the same action sequence. Your tests should include “split” inputs where sequences are divided across buffers to confirm state continuity.

How this fits on projects

This concept is used in this project and is essential for P04, P07, and P13.

Definitions & Key Terms

  • Streaming parser -> parser that maintains state across input chunks.
  • State machine -> finite set of states with transitions per byte.
  • Recovery transition -> state reset triggered by invalid input.
  • Fast path -> optimized path for printable text runs.

Mental Model Diagram (ASCII)

GROUND --ESC--> ESC --'['--> CSI --final--> emit CSI, back to GROUND
GROUND --ESC--> ESC --']'--> OSC --BEL/ST--> emit OSC, back to GROUND
GROUND --printable--> accumulate text run

How It Works (Step-by-Step)

  1. Maintain a state variable and buffers for params/strings.
  2. For each byte, transition state and update buffers.
  3. When a sequence completes, emit an action and reset state.
  4. If invalid input appears, emit an error action and reset.
  5. Use a fast path to emit long runs of printable text.

Invariants:

  • State persists across reads.
  • Each byte is consumed exactly once.
  • Recovery always returns to GROUND.

Failure modes:

  • Dropping bytes when sequences split across buffers.
  • Never exiting OSC/DCS due to missing terminators.
  • Emitting incorrect defaults for missing parameters.

Minimal Concrete Example

switch (state) {
case GROUND:
    if (b == 0x1b) state = ESC;
    else if (is_printable(b)) append_text(b);
    else emit_control(b);
    break;
case ESC:
    if (b == '[') { state = CSI; reset_params(); }
    else if (b == ']') { state = OSC; reset_string(); }
    else { state = GROUND; emit_esc_dispatch(b); }
    break;
}

Common Misconceptions

  • “You can parse with regex.” -> Streams split sequences; regex needs full buffers.
  • “Malformed sequences are rare.” -> They occur in logs and networked terminals.
  • “One action per byte is fine.” -> It is too slow for large output.

Check-Your-Understanding Questions

  1. How do you handle a CSI sequence split across two reads?
  2. Why should OSC/DCS have a maximum length?
  3. What is the benefit of a fast path for text runs?

Check-Your-Understanding Answers

  1. Store partial state and resume parsing on the next chunk.
  2. To prevent unbounded memory growth on malformed sequences.
  3. It reduces per-byte overhead and improves throughput.

Real-World Applications

  • High-throughput terminals (Alacritty, Kitty)
  • Terminal test harnesses that replay logs
  • Web terminals with network jitter

Where You’ll Apply It

References

  • “Language Implementation Patterns” (Parr), Chapters 1-3
  • xterm.js parser design notes (public docs)

Key Insight

Streaming parsing is a state machine problem with strict termination rules and recovery paths.

Summary

A terminal parser is only correct if it can pause mid-sequence, recover from errors, and still process text efficiently.

Homework/Exercises to Practice the Concept

  1. Feed a parser one byte at a time and verify output equals chunked input.
  2. Create an unterminated OSC sequence and observe recovery.
  3. Benchmark text runs with and without fast-path scanning.

Solutions to the Homework/Exercises

  1. Use a test that splits input at every possible byte boundary.
  2. Add a length cap and reset to GROUND when exceeded.
  3. Compare CPU time for large printable buffers.

3. Project Specification

3.1 What You Will Build

A streaming ANSI/VT parser library with a small CLI demo tool that:

  • Accepts raw bytes and emits structured actions.
  • Handles ESC, CSI, OSC, DCS, and plain text.
  • Supports default parameter rules and private modes.
  • Recovers from malformed sequences without losing sync.

Intentionally excluded:

  • Rendering, screen model, or PTY integration.

3.2 Functional Requirements

  1. Parser core: Incremental parse function that accepts byte buffers.
  2. Action schema: Emit actions for Text, CSI, OSC, DCS, and Control bytes.
  3. Defaults: Apply correct defaults for missing CSI params.
  4. OSC/DCS termination: End on BEL or ST only.
  5. Error recovery: Reset state on invalid bytes or length caps.
  6. CLI demo: Read stdin and print emitted actions deterministically.

3.3 Non-Functional Requirements

  • Performance: Handle 1 MB/s of text with minimal overhead.
  • Reliability: Parser never locks in a bad state.
  • Usability: Clear action output format for debugging.

3.4 Example Usage / Output

$ ./parse_demo < sample.log
TEXT("hello")
CSI([2],'J')
CSI([1;1],'H')
OSC("0","My Title")
TEXT("world")

3.5 Data Formats / Schemas / Protocols

Action JSON (for tests):

{"type":"CSI","params":[2],"final":"J","private":false}

3.6 Edge Cases

  • ESC at end of buffer with no following byte.
  • OSC containing embedded ESC that is not a terminator.
  • CSI with missing parameters (e.g., ESC [ m).

3.7 Real World Outcome

A parser library and CLI that can decode real terminal logs deterministically.

3.7.1 How to Run (Copy/Paste)

cc -O2 -o parse_demo parse_demo.c
TZ=UTC LC_ALL=C ./parse_demo < samples/vim.log

3.7.2 Golden Path Demo (Deterministic)

  1. Feed a fixed log file samples/basic.log.
  2. Verify the emitted action list matches samples/basic.actions exactly.

3.7.3 Failure Demo (Deterministic)

$ printf '\033]0;unterminated' | ./parse_demo
ERROR("OSC unterminated", code=1)
exit status: 65

3.7.6 If Library: minimal usage snippet

Parser p;
parser_init(&p);
parser_feed(&p, buf, len, on_action, ctx);

Expected output: callbacks for Text/CSI/OSC actions in correct order.

4. Solution Architecture

4.1 High-Level Design

+-------------+   bytes   +-------------+   actions   +--------------+
| Input Buffer| --------> | Parser FSM  | --------->  | Action Sink  |
+-------------+           +-------------+             +--------------+

4.2 Key Components

Component Responsibility Key Decisions
Parser FSM State transitions and parameter parsing Table-driven DFA
Action Sink Collect or emit actions Callback interface
CLI Demo Read stdin and print actions Deterministic formatting

4.3 Data Structures (No Full Code)

struct Action {
    enum { ACT_TEXT, ACT_CSI, ACT_OSC, ACT_DCS, ACT_CTRL, ACT_ERROR } type;
    int params[16];
    int param_count;
    char final_byte;
    char *payload; // for OSC/DCS
};

4.4 Algorithm Overview

Key Algorithm: Streaming Parse

  1. Scan for printable runs and emit text actions.
  2. On ESC, switch to escape parsing.
  3. Collect params and intermediates until final byte.
  4. Emit action and reset state.

Complexity Analysis:

  • Time: O(n) for n bytes
  • Space: O(1) + bounded buffers

5. Implementation Guide

5.1 Development Environment Setup

cc --version
make --version

5.2 Project Structure

ansi-parser/
|-- src/
|   |-- parser.c
|   |-- parser.h
|   `-- demo.c
|-- tests/
|   `-- parser_tests.c
|-- samples/
|   |-- basic.log
|   `-- basic.actions
|-- Makefile
`-- README.md

5.3 The Core Question You’re Answering

“How do you turn a raw byte stream into deterministic terminal actions?”

5.4 Concepts You Must Understand First

Stop and verify that you can explain:

  1. CSI parameter parsing and defaults.
  2. OSC termination rules (BEL vs ST).
  3. Why streaming parsing needs persistent state.

5.5 Questions to Guide Your Design

  1. Will you use callbacks or an action queue?
  2. What maximum lengths do you allow for OSC/DCS?
  3. How do you expose private-mode prefixes?

5.6 Thinking Exercise

Split ESC [ 31 m across three buffers and trace state transitions at each byte.

5.7 The Interview Questions They’ll Ask

  1. How do you design a streaming parser?
  2. What is the difference between CSI and OSC?
  3. How do you recover from malformed sequences?

5.8 Hints in Layers

Hint 1: Implement GROUND and ESC first Start with a minimal DFA and grow states.

Hint 2: Keep params in a small fixed array Most CSI sequences use <= 4 params.

Hint 3: Cap OSC length Prevent unbounded memory use on malformed data.

Hint 4: Use a printable fast path Batch text runs for speed.

5.9 Books That Will Help

Topic Book Chapter
Parsing “Language Implementation Patterns” Ch. 1-3
Data structures “Algorithms in C” Part 1

5.10 Implementation Phases

Phase 1: Core DFA (2-3 days)

Goals: Parse ESC and CSI. Tasks:

  1. Implement GROUND and ESC states.
  2. Add CSI param parsing and final byte detection. Checkpoint: Simple sequences parse correctly.

Phase 2: String Sequences (2-3 days)

Goals: Parse OSC and DCS. Tasks:

  1. Implement OSC state with BEL/ST termination.
  2. Implement DCS with length caps. Checkpoint: OSC titles parse correctly.

Phase 3: Robustness (2-3 days)

Goals: Recovery and tests. Tasks:

  1. Add malformed sequence handling.
  2. Build split-buffer tests. Checkpoint: Parser survives invalid input.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Output API Callbacks vs queue Callbacks Streaming friendly
Text handling Per-byte vs run Run scanning Performance
OSC limits Unlimited vs capped Capped Prevent memory abuse

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Validate CSI parsing ESC [ 2 J
Integration Tests Parse real logs vim session capture
Edge Case Tests Unterminated OSC ESC ] 0;title

6.2 Critical Test Cases

  1. Split CSI: ESC [ in one buffer and 2J in the next.
  2. OSC termination: BEL and ST both terminate correctly.
  3. Defaults: ESC [ m defaults to SGR 0.

6.3 Test Data

Input: ESC [ 31 m red ESC [ 0 m
Expected: CSI([31],'m'), TEXT("red"), CSI([0],'m')

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
OSC never terminates Parser stuck in OSC Detect BEL/ST only
Missing default params Wrong colors/modes Apply correct defaults
One-byte text actions Slow parsing Batch printable runs

7.2 Debugging Strategies

  • Log state transitions for a failing sequence.
  • Build a “byte-by-byte” replay mode for deterministic debugging.

7.3 Performance Traps

Allocating a new string for every byte will dominate runtime; use buffered runs.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add support for 8-bit C1 control codes.
  • Implement a JSON output mode for actions.

8.2 Intermediate Extensions

  • Add a grammar-driven parser using tables.
  • Support device status reports (DSR) parsing.

8.3 Advanced Extensions

  • Implement a full VT500 parser state table.
  • Build fuzz tests with corpus minimization.

9. Real-World Connections

9.1 Industry Applications

  • Terminal emulators and multiplexers
  • Web-based terminal frontends
  • xterm.js: streaming ANSI/VT parser in JS
  • vte: GNOME terminal parsing engine

9.3 Interview Relevance

  • State machines and streaming protocols
  • Defensive parsing and recovery

10. Resources

10.1 Essential Reading

  • ECMA-48 standard overview
  • xterm control sequence reference

10.2 Video Resources

  • Parser design talks and compiler lectures

10.3 Tools & Documentation

  • vttest for sequence generation
  • xxd for byte inspection

11. Self-Assessment Checklist

11.1 Understanding

  • I can decode a CSI sequence by hand.
  • I can explain OSC termination rules.
  • I understand why streaming parsing is required.

11.2 Implementation

  • Parser handles split sequences correctly.
  • Malformed sequences do not lock the parser.
  • Performance is acceptable for large logs.

11.3 Growth

  • I can integrate the parser into a screen model.
  • I can explain design trade-offs in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • CSI, OSC, and printable text parse correctly.
  • Parser handles split buffers and defaults.

Full Completion:

  • Robust error recovery and deterministic tests.
  • CLI demo can parse real logs.

Excellence (Going Above & Beyond):

  • Fuzz-tested parser with minimized crash cases.
  • Table-driven DFA implementation.