Project 6: Scrollback Buffer Implementation

Build a scrollback buffer that stores terminal history efficiently and supports fast scrolling, search, and redraw.

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 2: Open Source Builder
Prerequisites Screen model, basic data structures
Key Topics scrollback, ring buffers, viewport

1. Learning Objectives

By completing this project, you will:

  1. Design a scrollback buffer that stores lines and attributes efficiently.
  2. Implement a viewport that can scroll independently of the live screen.
  3. Preserve correct behavior when new output arrives while scrolled back.
  4. Support fast redraws with minimal copying.
  5. Add deterministic tests for scrollback invariants.

2. All Theory Needed (Per-Concept Breakdown)

Concept 1: Scrollback Data Structures and Ring Buffers

Fundamentals

Scrollback is the history of lines that have scrolled off the visible screen. A naive implementation stores every line in a growing list, but that wastes memory and slows down scrolling. A ring buffer (circular buffer) is a common solution: it stores a fixed maximum number of lines and overwrites the oldest when full. This gives predictable memory usage and fast insertion.

Deep Dive into the Concept

A scrollback buffer stores complete rows of cells, including attributes. Each time the screen scrolls, the top line moves into the scrollback and a new blank line appears at the bottom. If scrollback capacity is fixed (e.g., 10,000 lines), the buffer can be implemented as a circular array of line pointers. You maintain a head index (oldest line) and a count. When adding a new line and the buffer is full, you overwrite the oldest and advance the head.

The ring buffer must store not just text but attributes and possibly metadata (timestamp, wrapped-line markers). A common approach is to store a Line struct with an array of cells and a flag indicating whether the line is “wrapped” from the previous line. Wrapped flags matter for text selection and search: a long line that wrapped should be treated as a single logical line.

Scrollback integration introduces invariants. When the user scrolls back, the viewport should display lines from scrollback instead of the live screen. When new output arrives while the user is scrolled back, you have two choices: (1) keep the viewport at the same scroll offset (“freeze” view) and show a notification, or (2) snap back to bottom. Most terminals freeze the view and show a “new output” indicator. This means your rendering pipeline must know whether the viewport is attached to the live screen or to a historical offset.

Efficiency matters. Copying large buffers on every scroll is too slow. Instead, you can implement scroll by moving pointers or indices. For example, the screen grid can be stored as a ring of lines too, so scrolling is just incrementing an index. This reduces copying and makes scrollback integration easier: lines can be moved between live grid and scrollback by swapping references, not copying memory.

Finally, scrollback interacts with selection and search. If you plan to add those features later, your data structure should preserve line boundaries and attributes. This project focuses on a minimal scrollback, but you should design the API so future features can be added without rewriting the core buffer.

How this fits on projects

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

Definitions & Key Terms

  • Scrollback -> history of lines that have scrolled off screen.
  • Ring buffer -> fixed-size circular buffer.
  • Viewport -> the currently visible window into history.
  • Wrapped line -> line that continues onto the next row.

Mental Model Diagram (ASCII)

[scrollback ring] <--- old lines
[screen grid]     <--- live lines (visible when at bottom)

How It Works (Step-by-Step)

  1. When screen scrolls, move top line into scrollback buffer.
  2. Insert a new blank line at bottom of screen grid.
  3. If scrollback buffer full, overwrite oldest line.
  4. Viewport determines whether to show scrollback or live grid.

Invariants:

  • Scrollback capacity is fixed and bounded.
  • Viewport offset never exceeds available history.

Failure modes:

  • Losing attributes when storing lines.
  • Incorrect wrap markers causing broken selection.

Minimal Concrete Example

void push_scrollback(Line *line) {
    if (count == capacity) {
        free(lines[head]);
        head = (head + 1) % capacity;
        count--;
    }
    int idx = (head + count) % capacity;
    lines[idx] = line;
    count++;
}

Common Misconceptions

  • “Scrollback is just text.” -> Attributes and wrap flags matter.
  • “Copying lines is fine.” -> It becomes slow at scale.
  • “Viewport always shows latest output.” -> Users can scroll back.

Check-Your-Understanding Questions

  1. Why use a ring buffer instead of a vector?
  2. What happens when the buffer is full?
  3. Why store wrap markers?

Check-Your-Understanding Answers

  1. Predictable memory and O(1) insert/overwrite.
  2. Overwrite the oldest line and advance head.
  3. To reconstruct logical lines for selection/search.

Real-World Applications

  • Terminal emulators with large scrollback
  • Log viewers and monitoring dashboards

Where You’ll Apply It

References

  • Terminal emulator design notes (xterm, vte)
  • Data structures texts on circular buffers

Key Insight

A ring buffer gives you bounded memory and O(1) scrolling for free.

Summary

Scrollback is a data structure problem: efficient storage with correct line semantics.

Homework/Exercises to Practice the Concept

  1. Implement a ring buffer and test wrap-around behavior.
  2. Add wrap markers and verify logical line reconstruction.
  3. Benchmark scrolling 10,000 lines.

Solutions to the Homework/Exercises

  1. Insert more than capacity and confirm oldest lines disappear.
  2. Simulate a long line and ensure it reconstructs correctly.
  3. Time scroll operations and confirm O(1) behavior.

Concept 2: Viewport, Scrolling, and New Output Behavior

Fundamentals

The viewport is the portion of the history that is currently visible. When at the bottom, the viewport shows the live screen. When the user scrolls up, the viewport moves into the scrollback history. New output arriving while the user is scrolled up should not jerk the view; it should either keep the view fixed and show an indicator or automatically jump back to bottom depending on policy.

Deep Dive into the Concept

A terminal’s screen is not always what the user sees. The user can scroll up to inspect history. This creates a split between the “live” screen and the “view”. The viewport can be described by an offset: 0 means showing live content; positive values mean showing older lines from scrollback. When the user scrolls up, the offset increases. When the user scrolls down, it decreases toward 0.

When new output arrives, if the offset is 0, you append to the live screen and scrollback as usual. If the offset is >0, you should keep the viewport fixed and set a “has_new_output” flag. This allows the user to continue reading while new output arrives. Many terminals also display a marker such as “(new output)” or a small indicator. Implementing this requires the renderer to know whether it should draw from scrollback or live screen.

Scrolling behavior interacts with selections. If the user has selected text while scrolled back, new output should not invalidate that selection. This suggests that your model should treat scrollback lines as immutable once stored. Copying or modifying them should be avoided. Instead, new output should be appended to scrollback, and the viewport offset should remain stable.

Another subtlety is alternate screen mode. Full-screen apps often enable the alternate screen, which should not affect scrollback. The scrollback buffer is typically disabled or separate during alternate screen usage. For a minimal scrollback project, you can ignore alternate screen, but note this behavior in your design to avoid surprises later.

How this fits on projects

This concept is needed here and in P13/P15.

Definitions & Key Terms

  • Viewport offset -> distance from live bottom into history.
  • Live screen -> the current active grid.
  • New output flag -> indicator when output arrives during scrollback view.

Mental Model Diagram (ASCII)

[oldest] ... [scrollback] ... [live screen]
                 ^
             viewport

How It Works (Step-by-Step)

  1. Maintain a scroll_offset (0 means bottom).
  2. When user scrolls up, increment offset (clamp to history).
  3. When new output arrives and offset > 0, set has_new_output.
  4. Renderer draws from history at the current offset.

Invariants:

  • Offset never exceeds available scrollback.
  • Live output always updates screen grid.

Failure modes:

  • Jumping the viewport when new output arrives.
  • Inconsistent redraw between scrollback and live screen.

Minimal Concrete Example

if (scroll_offset == 0) {
    apply_output_to_screen();
} else {
    apply_output_to_screen();
    has_new_output = true;
}

Common Misconceptions

  • “Scrollback is just an append-only log.” -> The viewport can detach.
  • “New output should always be visible.” -> Users expect freeze behavior.

Check-Your-Understanding Questions

  1. What should happen when output arrives while scrolled back?
  2. Why keep scrollback lines immutable?
  3. How do you determine the maximum scroll offset?

Check-Your-Understanding Answers

  1. Keep the view fixed and set a new-output indicator.
  2. To preserve selections and consistency.
  3. It is the number of scrollback lines available.

Real-World Applications

  • Terminal history navigation
  • Log monitoring tools

Where You’ll Apply It

References

  • xterm scrollback documentation
  • GUI UI patterns for history panes

Key Insight

The viewport is a window into history, not a live feed.

Summary

Correct scrollback behavior depends on decoupling the viewport from the live screen.

Homework/Exercises to Practice the Concept

  1. Implement scroll up/down with a fixed offset.
  2. Add a “new output” indicator.
  3. Verify that scrolling does not change live output.

Solutions to the Homework/Exercises

  1. Clamp the offset between 0 and max history.
  2. Set a boolean when output arrives with offset > 0.
  3. Always update the live screen, not the viewport.

3. Project Specification

3.1 What You Will Build

A scrollback subsystem that:

  • Stores a fixed number of historical lines with attributes.
  • Tracks a viewport offset for user scrolling.
  • Integrates with a live screen model.
  • Supports deterministic scrolling tests.

Intentionally excluded:

  • Full selection and search UI (you will design the data layout for them).

3.2 Functional Requirements

  1. Ring buffer: fixed capacity with overwrite of oldest line.
  2. Line storage: store chars and attributes per line.
  3. Viewport offset: scroll up/down within history.
  4. New output flag: set when output arrives while scrolled back.
  5. Rendering: draw either live screen or scrollback view.

3.3 Non-Functional Requirements

  • Memory bound: constant max memory usage.
  • Performance: O(1) scroll operations.
  • Determinism: fixed test logs and expected output.

3.4 Example Usage / Output

$ ./scrollback_demo --lines 1000
[scroll] stored 1000 lines
[view] offset=120
[new output] yes

3.5 Data Formats / Schemas / Protocols

  • Line struct: {cells[], wrapped}
  • Scrollback index: head, count, capacity

3.6 Edge Cases

  • Scrollback capacity smaller than screen height.
  • Scrolling beyond available history.
  • Output arrives during scrollback view.

3.7 Real World Outcome

A scrollback buffer that behaves like a real terminal’s history.

3.7.1 How to Run (Copy/Paste)

cc -O2 -o scrollback_demo scrollback_demo.c
TZ=UTC LC_ALL=C ./scrollback_demo --lines 200 --demo-log samples/output.log

3.7.2 Golden Path Demo (Deterministic)

  1. Replay a fixed log of 300 lines.
  2. Verify scrollback size caps at 200 and oldest lines drop.

3.7.3 Failure Demo (Deterministic)

$ ./scrollback_demo --lines 0
error: scrollback capacity must be > 0
exit status: 64

3.7.4 If TUI: ASCII layout

+------------------------------+
| Scrollback Demo              |
| (new output)                 |
| line 180                     |
| line 181                     |
| ...                          |
+------------------------------+

4. Solution Architecture

4.1 High-Level Design

Screen scroll -> push line -> scrollback ring
Viewport offset -> renderer selects live or history

4.2 Key Components

Component Responsibility Key Decisions
Scrollback Ring Store old lines Fixed capacity ring
Viewport Track scroll position Offset from bottom
Renderer Display lines Choose source based on offset

4.3 Data Structures (No Full Code)

struct Line { struct Cell cells[MAX_COLS]; bool wrapped; };
struct Scrollback { struct Line *lines; int head; int count; int cap; };

4.4 Algorithm Overview

Key Algorithm: Scroll Up

  1. On scroll, push top line into scrollback.
  2. Shift screen lines up (or rotate pointers).
  3. Insert blank line at bottom.

Complexity Analysis:

  • Time: O(1) if using pointer rotation
  • Space: O(capacity * cols)

5. Implementation Guide

5.1 Development Environment Setup

cc --version

5.2 Project Structure

scrollback/
|-- src/
|   |-- scrollback.c
|   |-- viewport.c
|   `-- demo.c
|-- tests/
|   `-- scrollback_tests.c
|-- samples/
|   `-- output.log
|-- Makefile
`-- README.md

5.3 The Core Question You’re Answering

“How do you store and view terminal history without unbounded memory or slow scrolling?”

5.4 Concepts You Must Understand First

  1. Ring buffer mechanics.
  2. Screen vs viewport distinction.
  3. Line wrap semantics.

5.5 Questions to Guide Your Design

  1. How will you represent wrapped lines?
  2. What happens when new output arrives while scrolled back?
  3. How will you avoid copying entire lines on scroll?

5.6 Thinking Exercise

Design a data structure that stores 10,000 lines of 120 columns and estimate memory usage.

5.7 The Interview Questions They’ll Ask

  1. Why use a ring buffer for scrollback?
  2. How do you keep scrolling O(1)?
  3. How do you handle new output while scrolled back?

5.8 Hints in Layers

Hint 1: Start with a fixed array A ring buffer makes overwrites easy.

Hint 2: Use line pointers Avoid copying full lines on scroll.

Hint 3: Separate viewport from live screen Decouple viewing from updates.

Hint 4: Add wrap flags Future features depend on them.

5.9 Books That Will Help

Topic Book Chapter
Data structures “Algorithms in C” Part 1
Terminal design “The Linux Programming Interface” Ch. 62-64

5.10 Implementation Phases

Phase 1: Ring buffer (2-3 days)

Goals: store lines with fixed capacity. Tasks:

  1. Implement ring insert/overwrite.
  2. Add tests for wrap-around. Checkpoint: Old lines drop when full.

Phase 2: Viewport (2-3 days)

Goals: scroll up/down. Tasks:

  1. Add scroll offset and clamp.
  2. Render lines from history. Checkpoint: Scrolling shows old lines.

Phase 3: Integration (2-3 days)

Goals: integrate with screen model. Tasks:

  1. Push lines on scroll.
  2. Add new-output indicator. Checkpoint: Output continues while scrolled back.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Storage Copy lines vs pointer swap Pointer swap O(1) scroll
View behavior Auto-jump vs freeze Freeze with indicator Matches common terminals
Capacity Dynamic vs fixed Fixed Predictable memory

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Ring buffer wrap Capacity overflow
Integration Tests Scroll behavior Scroll 50 lines
Edge Case Tests Small capacity 1 line

6.2 Critical Test Cases

  1. Overwrite: adding capacity+1 lines drops oldest.
  2. Viewport clamp: offset never exceeds history.
  3. New output: flag set when output arrives while scrolled back.

6.3 Test Data

Input: lines 1..300, capacity=200
Expected: first visible line = 101

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Copying lines on scroll Slow performance Use pointer rotation
Dropping attributes Colors lost Store full cells
Wrong viewport offset Jumps or gaps Clamp correctly

7.2 Debugging Strategies

  • Add a debug print of head/count/offset after each scroll.
  • Render line numbers for easier verification.

7.3 Performance Traps

Copying full screen buffers per scroll becomes expensive at large sizes.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add simple search across scrollback.
  • Add a “jump to bottom” command.

8.2 Intermediate Extensions

  • Add selection and copy of scrollback text.
  • Add timestamps per line.

8.3 Advanced Extensions

  • Persistent scrollback on disk.
  • Compressed scrollback storage.

9. Real-World Connections

9.1 Industry Applications

  • Terminal history navigation
  • Log analysis tools
  • kitty: advanced scrollback features
  • wezterm: searchable scrollback

9.3 Interview Relevance

  • Ring buffers and bounded memory
  • UI view vs model separation

10. Resources

10.1 Essential Reading

  • Data structures textbooks on circular buffers
  • Terminal emulator architecture notes

10.2 Video Resources

  • Talks on terminal emulator design

10.3 Tools & Documentation

  • less and more for scroll behavior reference

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain why a ring buffer is used.
  • I can describe viewport vs live screen.
  • I understand wrap markers.

11.2 Implementation

  • Scrollback capacity is enforced.
  • Scrolling behaves like a real terminal.
  • New output indicator works.

11.3 Growth

  • I can extend this to support search.
  • I can explain design trade-offs.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Fixed-capacity scrollback buffer with viewport scrolling.
  • Attributes preserved for historical lines.

Full Completion:

  • Deterministic tests and new-output indicator.
  • O(1) scrolling behavior.

Excellence (Going Above & Beyond):

  • Searchable or persistent scrollback.
  • Compression and memory profiling.