Project 7: VT100 State Machine

Implement a faithful VT100-style state machine that applies parsed actions to a screen model with correct modes and invariants.

Quick Reference

Attribute Value
Difficulty Level 3: Advanced
Time Estimate 2-3 weeks
Main Programming Language C (Alternatives: Rust)
Alternative Programming Languages Rust
Coolness Level Level 4: Hardcore Tech Flex
Business Potential Level 2: Open Source Builder
Prerequisites Parser, screen model, cursor rules
Key Topics VT100 modes, state transitions, invariants

1. Learning Objectives

By completing this project, you will:

  1. Implement a VT100-compatible action state machine.
  2. Handle modes like origin mode, wrap mode, and insert mode.
  3. Maintain invariants for cursor, scrolling region, and tab stops.
  4. Validate behavior with VT100 test suites and logs.
  5. Build a reference model you can reuse in full terminal projects.

2. All Theory Needed (Per-Concept Breakdown)

Concept 1: VT100 Modes and State Invariants

Fundamentals

VT100 terminals maintain internal modes that affect how actions behave. Examples include wrap mode (whether cursor wraps at the end of a line), origin mode (cursor position relative to scrolling region), insert mode (characters insert vs overwrite), and newline mode (LF vs CR+LF). These modes define invariants that must be preserved for correct behavior.

Deep Dive into the Concept

The VT100 is a stateful device. It keeps flags that change how input is interpreted. Wrap mode determines whether writing at the last column moves the cursor to the next line or stays in place. Origin mode changes the coordinate system for cursor positioning: when origin mode is active, cursor positions are relative to the scrolling region instead of the full screen. This is critical for full-screen applications like vi, which set a scrolling region and rely on cursor positions staying within it.

Insert mode changes how characters affect the line. In insert mode, new characters shift existing characters to the right; in overwrite mode, they replace existing characters. Many terminals default to overwrite mode but allow insert mode via CSI 4 h and reset with CSI 4 l. Implementing insert mode requires shifting line contents and preserving attributes, which is a common source of bugs.

Tab stops are another VT100 feature. The terminal maintains a set of tab stop positions (typically every 8 columns by default). The HT control character moves the cursor to the next tab stop. This seems small, but many programs rely on tabs for alignment, so a correct emulator must implement them. Clearing and setting tab stops is also part of the VT100 command set.

The scrolling region defines which rows scroll when content reaches the bottom. VT100 supports setting a top and bottom margin via CSI t;b r. When the cursor moves beyond the bottom of this region, only the region scrolls, not the entire screen. This is subtle and often mishandled; if you ignore the scroll region, full-screen applications will render incorrectly.

How this fits on projects

This concept is central to this project and reused in P13 and P15.

Definitions & Key Terms

  • Wrap mode -> automatic line wrap at end of line.
  • Origin mode -> cursor positioning relative to scrolling region.
  • Insert mode -> insert characters by shifting line content.
  • Scrolling region -> subset of rows affected by scroll.
  • Tab stops -> column positions for horizontal tab.

Mental Model Diagram (ASCII)

Rows 0..24
Scroll region: rows 5..20
Cursor positions are relative to region in origin mode

How It Works (Step-by-Step)

  1. Parse mode-setting sequences (CSI h/l).
  2. Update internal mode flags.
  3. Apply actions according to current modes.
  4. Enforce cursor and scroll region invariants.

Invariants:

  • Cursor stays within scrolling region when origin mode is set.
  • Insert mode shifts characters without losing attributes.

Failure modes:

  • Ignoring origin mode causes incorrect cursor placement.
  • Failing to respect scroll region breaks full-screen apps.

Minimal Concrete Example

if (origin_mode) {
    cursor_r = clamp(top + row - 1, top, bottom);
} else {
    cursor_r = clamp(row - 1, 0, rows-1);
}

Common Misconceptions

  • “Cursor positions are always absolute.” -> Origin mode changes them.
  • “Insert mode is rare.” -> Many editors toggle it.
  • “Scroll region is optional.” -> Full-screen apps rely on it.

Check-Your-Understanding Questions

  1. What does origin mode do to CSI H?
  2. How does insert mode affect line content?
  3. Why are scroll regions needed?

Check-Your-Understanding Answers

  1. Cursor positions are relative to the scrolling region.
  2. Characters shift right instead of overwriting.
  3. They allow apps to scroll only a portion of the screen.

Real-World Applications

  • vim and less fullscreen modes
  • Terminal UI frameworks

Where You’ll Apply It

References

  • DEC VT100 Programmer Reference
  • xterm control sequence reference

Key Insight

Terminal correctness is mostly about modes and invariants, not about parsing alone.

Summary

A VT100 state machine is defined by its mode flags and the rules they impose.

Homework/Exercises to Practice the Concept

  1. Implement origin mode and test with a scroll region.
  2. Add insert mode and verify character shifting.
  3. Implement tab stops and test with \t.

Solutions to the Homework/Exercises

  1. Set scroll region, enable origin mode, and move cursor to row 1.
  2. Insert characters in the middle of a line and verify shifts.
  3. Add default tab stops every 8 columns.

Concept 2: Action Dispatcher and State Machine Design

Fundamentals

Once sequences are parsed into actions, a state machine applies them to the screen model. This dispatcher must be deterministic, ordered, and aware of modes. It is separate from the parser: the parser decides what action to perform, the state machine decides how that action affects the screen given the current modes and state.

Deep Dive into the Concept

A robust terminal emulator separates parsing from execution. The parser emits actions like “CursorUp(2)” or “EraseInDisplay(2)”. The executor (state machine) takes each action and mutates the screen model. This separation makes correctness easier to test: you can feed a sequence of actions to the executor and verify the final screen state.

The executor must maintain multiple pieces of state: cursor position, current attributes, scroll region, tab stops, and mode flags. Each action can depend on multiple state variables. For example, CursorUp should clamp to the top of the scroll region when origin mode is active. InsertChar should shift cells right and preserve attributes. EraseInLine should clear a portion of the line and reset attributes for those cells. These rules are deterministic but complex, and they must be applied in the correct order.

A key design choice is whether to represent actions as enums with parameters or as function pointers. Enums are easier to serialize and test. You can also implement a dispatch table mapping action types to handler functions, which keeps code organized and reduces large switch statements. This is especially useful as the action set grows.

Finally, the executor should enforce invariants and detect impossible states early. If the cursor position becomes negative or exceeds bounds, clamp it or log a warning. If scroll region is invalid (top >= bottom), reset to full screen. These defensive checks prevent subtle bugs from cascading into broken output.

How this fits on projects

This concept is central to this project and reused in P13.

Definitions & Key Terms

  • Action dispatcher -> component that executes parsed actions.
  • Mode flags -> state variables that change behavior.
  • Scroll region -> top/bottom margins for scrolling.

Mental Model Diagram (ASCII)

Parsed action -> dispatcher -> update state + screen

How It Works (Step-by-Step)

  1. Receive an action from the parser.
  2. Look up the handler for the action type.
  3. Apply changes to cursor, screen, and attributes.
  4. Enforce invariants and clamp values.

Invariants:

  • Cursor and scroll region are always valid.
  • Screen cells contain valid attributes.

Failure modes:

  • Incorrect handler order leads to state inconsistencies.
  • Missing clamps cause out-of-bounds writes.

Minimal Concrete Example

switch (act.type) {
case ACT_CURSOR_UP:
    cursor_r = max(top, cursor_r - act.n);
    break;
case ACT_ERASE_DISPLAY:
    clear_region(act.mode);
    break;
}

Common Misconceptions

  • “Parser and executor are the same.” -> Separate them for testability.
  • “VT100 behavior is simple.” -> Mode flags alter behavior widely.

Check-Your-Understanding Questions

  1. Why separate parser and executor?
  2. How do mode flags affect action execution?
  3. Why use clamps instead of crashing?

Check-Your-Understanding Answers

  1. It makes testing and maintenance easier.
  2. They change how actions mutate state.
  3. To prevent invalid states from breaking output.

Real-World Applications

  • Terminal emulator cores
  • TUI frameworks that simulate terminals

Where You’ll Apply It

References

  • DEC VT100 reference manual
  • Terminal emulator source code (xterm, vte)

Key Insight

The executor is where terminal correctness lives; the parser is only the front door.

Summary

A disciplined action dispatcher makes terminal behavior deterministic and testable.

Homework/Exercises to Practice the Concept

  1. Build a small action script and apply it to a blank screen.
  2. Add invariant checks and ensure they never trigger in tests.
  3. Compare results with xterm for the same action script.

Solutions to the Homework/Exercises

  1. Use actions like CursorHome, PrintText(“abc”), EraseLine.
  2. Add asserts and run logs to confirm no violations.
  3. Replay in xterm and compare output.

3. Project Specification

3.1 What You Will Build

A VT100-compatible state machine that:

  • Applies parsed actions to a screen model.
  • Supports key VT100 modes and scroll regions.
  • Maintains cursor, attributes, and tab stops.
  • Produces deterministic screen states for test scripts.

Intentionally excluded:

  • Full graphics or advanced extensions (OSC, Sixel).

3.2 Functional Requirements

  1. Mode handling: wrap, origin, insert, newline.
  2. Scroll region: set top/bottom margins.
  3. Tab stops: default every 8 cols, set/clear.
  4. Action dispatcher: apply actions deterministically.
  5. Invariant checks: clamp cursor and validate regions.

3.3 Non-Functional Requirements

  • Correctness: pass VT100 conformance tests for the supported subset.
  • Determinism: fixed action scripts produce fixed screen states.
  • Maintainability: clear separation between parser and executor.

3.4 Example Usage / Output

$ ./vt100_core --script samples/cursor.script
[ok] cursor moved to 5,10
[ok] region set 5..20

3.5 Data Formats / Schemas / Protocols

  • Action script: JSON lines with {type, params}.

3.6 Edge Cases

  • Scroll region with top >= bottom.
  • Cursor moves beyond region in origin mode.
  • Insert mode at end of line.

3.7 Real World Outcome

A testable VT100 state machine that matches reference behavior for core features.

3.7.1 How to Run (Copy/Paste)

cc -O2 -o vt100_core vt100_core.c
TZ=UTC LC_ALL=C ./vt100_core --script samples/vt100.script

3.7.2 Golden Path Demo (Deterministic)

  1. Run the script that sets region, writes lines, and scrolls.
  2. Compare the resulting screen snapshot to expected output.

3.7.3 Failure Demo (Deterministic)

$ ./vt100_core --set-region 20,10
error: invalid scroll region (top >= bottom)
exit status: 64

4. Solution Architecture

4.1 High-Level Design

Parser Actions -> VT100 Executor -> Screen Model -> Renderer

4.2 Key Components

Component Responsibility Key Decisions
Mode State Track wrap/origin/insert/newline Bitfield flags
Executor Apply actions Dispatch table
Screen Model Store cells and cursor Shared with other projects

4.3 Data Structures (No Full Code)

struct ModeState { bool wrap; bool origin; bool insert; bool newline; };
struct Cursor { int r, c; };
struct ScrollRegion { int top, bottom; };

4.4 Algorithm Overview

Key Algorithm: Apply Action

  1. Select handler based on action type.
  2. Adjust cursor and screen according to mode flags.
  3. Clamp values and enforce scroll region.

Complexity Analysis:

  • Time: O(n) for actions, O(cols) for insert shifts
  • Space: O(rows*cols)

5. Implementation Guide

5.1 Development Environment Setup

cc --version

5.2 Project Structure

vt100-core/
|-- src/
|   |-- executor.c
|   |-- modes.c
|   `-- screen.c
|-- samples/
|   |-- vt100.script
|   `-- vt100.expected
|-- tests/
|   `-- executor_tests.c
|-- Makefile
`-- README.md

5.3 The Core Question You’re Answering

“How do VT100 modes and actions combine to create correct terminal behavior?”

5.4 Concepts You Must Understand First

  1. Origin mode and scroll regions.
  2. Insert vs overwrite behavior.
  3. Tab stop management.

5.5 Questions to Guide Your Design

  1. How will you represent actions for test scripts?
  2. Where do you enforce invariants?
  3. How will you validate against reference behavior?

5.6 Thinking Exercise

Design an action script that reveals whether wrap mode is implemented correctly.

5.7 The Interview Questions They’ll Ask

  1. Why separate parser and executor?
  2. How do scroll regions affect cursor movement?
  3. Why do terminals need insert mode?

5.8 Hints in Layers

Hint 1: Build a minimal executor first Support only cursor moves and printing.

Hint 2: Add mode flags one by one Test each flag with dedicated scripts.

Hint 3: Add invariant checks Clamp cursor and validate scroll region.

Hint 4: Compare with xterm Use vttest for expected behavior.

5.9 Books That Will Help

Topic Book Chapter
Terminal internals “The Linux Programming Interface” Ch. 62
State machines “Language Implementation Patterns” Ch. 3

5.10 Implementation Phases

Phase 1: Core actions (1 week)

Goals: cursor moves, prints, clears. Tasks:

  1. Implement core action handlers.
  2. Create action script tests. Checkpoint: Basic actions match expected output.

Phase 2: Modes (1 week)

Goals: wrap, origin, insert. Tasks:

  1. Add mode flags and setters.
  2. Add tests per mode. Checkpoint: Mode behavior matches reference.

Phase 3: Scroll region and tabs (1 week)

Goals: scroll region, tab stops. Tasks:

  1. Implement scroll region logic.
  2. Add tab stop management. Checkpoint: Tab alignment works.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Action dispatch switch vs table Table Cleaner and extensible
Mode storage bitfield vs struct Struct Clarity
Tests action scripts vs live PTY Action scripts Deterministic

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Action handlers CursorUp, InsertChar
Integration Tests Full scripts vt100.script
Edge Case Tests Invalid regions top >= bottom

6.2 Critical Test Cases

  1. Origin mode: cursor positions relative to region.
  2. Insert mode: characters shift right.
  3. Scroll region: only region scrolls.

6.3 Test Data

Script: set region 5..10, write 8 lines
Expected: only rows 5..10 scroll

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Ignoring origin mode Cursor jumps to wrong row Apply region offset
Failing to shift in insert mode Text overwrites Implement shifting
No tab stops Misaligned text Add default tabs

7.2 Debugging Strategies

  • Render cursor and scroll region in a debug overlay.
  • Replay action scripts and compare with expected screens.

7.3 Performance Traps

Insert mode requires shifting cells; keep it O(cols) and avoid reallocs.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add DEC private modes (CSI ?).
  • Add save/restore cursor.

8.2 Intermediate Extensions

  • Add selective erase and double-width lines.
  • Support 132-column mode.

8.3 Advanced Extensions

  • Implement a full VT220 state table.
  • Add compatibility tests for vttest suite.

9. Real-World Connections

9.1 Industry Applications

  • Terminal emulator cores
  • Compatibility testing tools
  • xterm: reference VT behavior
  • vte: GNOME terminal engine

9.3 Interview Relevance

  • State machines and invariants
  • Emulating legacy protocols

10. Resources

10.1 Essential Reading

  • DEC VT100 Programmer Reference
  • xterm control sequence reference

10.2 Video Resources

  • Talks on terminal emulator internals

10.3 Tools & Documentation

  • vttest conformance tool

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain origin and wrap modes.
  • I can implement insert mode correctly.
  • I can explain scroll regions.

11.2 Implementation

  • VT100 modes behave correctly under tests.
  • Cursor invariants always hold.
  • Action scripts are deterministic.

11.3 Growth

  • I can extend to VT220 modes.
  • I can explain trade-offs in design.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Mode flags implemented and tested.
  • Action dispatcher correct for core VT100 features.

Full Completion:

  • Scroll region and tab stops fully supported.
  • Deterministic test scripts with expected output.

Excellence (Going Above & Beyond):

  • Full VT220/VT320 compatibility.
  • Automated vttest integration.