Project 4: Undo/Redo Engine for a Drawing Application

Build a deterministic undo/redo engine with branching history, snapshots, and crash-safe persistence.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1-2 weeks
Main Programming Language C (Alternatives: Rust, C++)
Alternative Programming Languages Rust, C++, Java
Coolness Level Level 3: Genuinely Clever
Business Potential Level 2: Micro-SaaS / Pro Tool
Prerequisites Data structures, serialization, file I/O
Key Topics Command history, temporal state, persistence, invariants

1. Learning Objectives

By completing this project, you will:

  1. Model undo/redo as a state machine with a cursor in history.
  2. Implement a command log with reversible operations.
  3. Handle branching history deterministically.
  4. Add snapshots and crash-safe persistence to recover state.
  5. Validate correctness with golden path and failure transcripts.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Command History and Temporal State

Fundamentals

Undo/redo is a temporal correctness problem. Each user action changes state, and undo/redo must move backward or forward through the exact same states without corruption. The cleanest model is a command history with a cursor: commands before the cursor are applied, commands after are not. Undo moves the cursor backward and applies an inverse operation; redo moves it forward and reapplies the command. This is a state machine where each command defines a legal transition. If you delete a command or branch, you must do it explicitly, because the history itself is part of the system state.

This model also makes the user’s timeline explicit. The cursor tells you not only where you are, but what future exists. That future must be either preserved as a separate branch or discarded deterministically. The choice is a design decision that directly affects correctness and user trust.

Deep Dive into the concept

Undo/redo is deceptively hard because it is a time machine. The system must be able to replay state changes in a consistent and reversible manner. The most reliable model is the command pattern: every operation is an object or struct with do() and undo() functions. This ensures reversibility by design. For example, a “draw line” command stores its endpoints, color, and ID. Its do() draws the line; its undo() removes the line by ID. The key rule is that the undo must be deterministic and idempotent given the state at the time of the command. If it depends on external state, undo will fail.

The command history is a linear list plus a cursor. The cursor points to the last applied command. When you undo, you move the cursor backward and call undo() on that command. When you redo, you move forward and call do(). If you create a new command while not at the end of history, you must discard the “redo” branch, because the future no longer matches the new timeline. This is an explicit state transition: from a partially undone state, a new command transitions the history into a new branch and invalidates the old future.

A subtle but critical detail is that commands must capture enough information to undo accurately. For example, a “move shape” command must store both the old and new positions. A “delete shape” command must store the full shape data so that undo can restore it. This is a resource ownership issue: the command history owns the data needed for undo, so you must ensure its lifetime is correct. If you store pointers to mutable objects, those objects may change and make the undo incorrect. This is why command objects often store copies or IDs with snapshots.

Temporal invariants are also important. The canvas state after applying commands 1..N must always be identical to the state you’d get by loading from disk or replaying commands. That means commands must be deterministic and order-dependent in a well-defined way. If a command depends on randomness (e.g., random brush stroke), the random seed must be stored in the command. If a command depends on time (e.g., timestamps), the timestamp must be stored. Otherwise redo will produce a different state and violate the invariant “redo returns you to the exact previous state.”

Branching history is often simplified away, but in professional tools it is essential. If you undo and then perform a new operation, you create a new branch. The old branch should either be discarded or preserved as an alternate branch. For this project, we choose deterministic behavior: discard the old redo branch. This is a state machine policy that prevents confusion. To implement it, you simply truncate the history list beyond the cursor when a new command is appended. That deletion must be safe: free command resources and ensure the history invariants still hold.

Testing undo/redo requires deterministic sequences. Use fixed command sequences and compare resulting state hashes. For example, after applying commands [A, B, C], undo twice, redo once, and then compare the canvas state with a known expected snapshot. The result must be identical every time, which proves your history model is correct.

How this fit on projects

Undo/redo defines the temporal state machine at the heart of the project. The history cursor, command objects, and branch truncation are the core logic you will implement.

Definitions & key terms

  • Command pattern: Encapsulate an operation and its inverse.
  • History cursor: Index of the last applied command.
  • Redo branch: Commands after the cursor that are no longer applied.
  • Idempotent undo: Undo produces the same state every time.

Mental model diagram (ASCII)

History: [A] [B] [C] [D]
Cursor:           ^ (after C)
Undo -> cursor moves left
Redo -> cursor moves right
New command at cursor -> truncate [D]

How it works (step-by-step)

  1. Execute command, append to history, move cursor.
  2. Undo: move cursor left, call undo on that command.
  3. Redo: move cursor right, call do on that command.
  4. New command while not at end: truncate redo branch, append new command.

Failure modes: missing data for undo, incorrect cursor movement, redo not invalidated after new command.

Minimal concrete example

typedef struct Command {
    void (*do)(void *ctx);
    void (*undo)(void *ctx);
    void *payload;
} Command;

int cursor = -1;
Command history[MAX];

Common misconceptions

  • “Undo just means reverse the last change.” It must be deterministic and reversible.
  • “Redo can be preserved after new edits.” That breaks the timeline invariant.

Check-your-understanding questions

  1. What happens to redo history after a new command is executed?
  2. Why must commands store all data needed to undo?
  3. How do you ensure redo returns to the exact same state?

Check-your-understanding answers

  1. It must be discarded or branched; in this project, it is truncated.
  2. Because the original objects may have changed or been deleted.
  3. Store deterministic parameters (including seeds/time) inside the command.

Real-world applications

  • Graphics editors (Photoshop, Figma)
  • Code editors with undo history
  • Database transaction logs

Where you’ll apply it

References

  • “Design Patterns” by Gamma et al. (Command pattern)
  • “Refactoring” by Martin Fowler (undoable operations)

Key insights

Undo/redo is a state machine over time; a history cursor makes it explicit.

Summary

If commands are deterministic and history is explicit, undo/redo becomes reliable.

Homework/Exercises to practice the concept

  1. Implement a command history for a counter with increment/decrement.
  2. Add undo/redo and verify state after sequences.

Solutions to the homework/exercises

  1. Store each increment as a command with do/undo.
  2. Simulate sequences and assert the counter matches expected values.

2.2 Persistence, Snapshots, and Crash-Safe History

Fundamentals

Undo history must survive crashes if you want professional-grade behavior. That requires persistence. Two common strategies are snapshots (periodic full state saves) and journals (append-only logs of commands). A robust system combines both: a snapshot provides a base state, and a journal replays recent commands. Crash safety requires atomic writes and careful ordering: write data first, then update pointers. If the system crashes halfway, recovery must detect the incomplete write and roll back cleanly.

Persistence is not just about saving state; it is about preserving the undo timeline itself. If you restart and lose the history cursor, you may restore the canvas but lose the user’s ability to undo. Therefore, durable metadata (cursor position, log offsets, snapshot version) is part of the required state, not optional bookkeeping.

Deep Dive into the concept

Persistence for undo/redo is a miniature version of database durability. The simplest approach is to serialize the entire canvas state after each command, but this is slow and large. A better approach uses snapshots and a journal. A snapshot captures the full state occasionally; between snapshots, each command is appended to a log. On restart, the system loads the latest snapshot and replays the log. This is how many editors and databases implement durability.

Crash safety is about ordering and atomicity. Consider writing the journal entry for a command. If you write the entry and then update a pointer to indicate “journal committed,” you must ensure the entry is fully flushed to disk first. The order is: write entry -> fsync -> update metadata -> fsync. This is the same principle as atomic commit in a VCS: write objects first, update refs last. If the process crashes after writing but before updating metadata, recovery can detect that the entry exists but was not committed and can ignore or replay it depending on your policy.

Snapshots add another layer. A snapshot should be written to a temporary file, fsynced, then renamed atomically. Only after the new snapshot is safely in place should you discard older logs. This ensures that a crash does not leave you without any valid snapshot. The snapshot file should include a version number and a checksum so you can detect corruption. The journal should also be checksummed per entry to detect partial writes.

The undo history itself must be persisted alongside the canvas state. If you only store the current state, undo cannot reconstruct history. The simplest approach is to store the command log, which can recreate both the state and the history cursor. The cursor position must be stored explicitly: if a crash happens while you are in the middle of undo operations, you need to restore the cursor to the correct position to preserve the user’s timeline. This is another state machine issue: the undo cursor is part of the durable state.

Determinism is crucial. If your commands depend on randomness or time, the command log must store the exact parameters used. Otherwise, replay will generate different results. This is why professional graphics editors store full command data, not just “draw brush stroke.” They store the path, pressure, color, and a timestamp if necessary. For this project, you can keep it simpler: define commands that are deterministic and store all parameters explicitly.

Testing crash safety requires controlled failure. You can simulate crashes by killing the process mid-write or by injecting a failure after writing the log but before updating metadata. Recovery must detect the incomplete state and choose a deterministic recovery path. For example, you might ignore the last partial command if its checksum fails. The key is that the system must always recover to a consistent state; it is acceptable to lose the last command, but not acceptable to load a corrupted canvas.

This persistence model generalizes beyond editors. It is the same approach used by databases, version control, and journaling filesystems. That is why mastering it here strengthens your understanding of durable state transitions across systems programming.

How this fit on projects

Persistence is the second half of the undo engine. You will implement snapshots, logs, and crash-safe ordering to make history durable.

Definitions & key terms

  • Snapshot: Full serialized state at a point in time.
  • Journal/Log: Append-only list of commands.
  • Atomic rename: Swap in a file only when it is fully written.
  • Checksum: Integrity check for detecting partial writes.

Mental model diagram (ASCII)

[Snapshot S0] + [Log: C1 C2 C3] -> Rebuild State
Write order: write -> fsync -> update metadata -> fsync

How it works (step-by-step)

  1. Append command to log and fsync.
  2. Update cursor metadata and fsync.
  3. Periodically write snapshot to temp and rename.
  4. On startup, load latest snapshot, replay log.

Failure modes: partial log write, corrupted snapshot, missing cursor metadata.

Minimal concrete example

// Append command entry with checksum
write(log_fd, &entry, sizeof(entry));
fsync(log_fd);

Common misconceptions

  • “Snapshots alone are enough.” You lose undo history.
  • “fsync is optional.” Without it, a crash can lose recent commands.

Check-your-understanding questions

  1. Why is atomic rename used for snapshots?
  2. What must be stored to restore undo history?
  3. How do you detect a partial log entry?

Check-your-understanding answers

  1. It ensures the snapshot is either fully old or fully new.
  2. The command log and the history cursor position.
  3. Use checksums or length fields to validate entries.

Real-world applications

  • Editor autosave systems
  • Database write-ahead logs
  • Filesystem journals

Where you’ll apply it

References

  • “Designing Data-Intensive Applications” by Kleppmann (durability)
  • “The Linux Programming Interface” (fsync, rename)

Key insights

Durable undo/redo is a mini-transaction system: write data first, update pointers last.

Summary

Persistence transforms undo/redo from a memory feature into a reliable system feature.

Homework/Exercises to practice the concept

  1. Write a log file with a checksum per entry.
  2. Simulate a crash by truncating the log and ensure recovery ignores partial entries.

Solutions to the homework/exercises

  1. Store a CRC32 with each entry and verify on load.
  2. If checksum fails, stop replay at the last valid entry.

3. Project Specification

3.1 What You Will Build

A standalone undo/redo engine with a CLI simulator for a drawing app. It supports a sequence of draw commands, undo/redo, and persistence to disk with snapshots and logs.

Included:

  • Command history with cursor
  • Branch truncation on new edits
  • Snapshot + log persistence
  • Deterministic replay

Excluded:

  • Full GUI drawing app

3.2 Functional Requirements

  1. Command objects: do() and undo() for each command.
  2. History cursor: explicit index of last applied command.
  3. Undo/redo: correct state restoration.
  4. Branch truncation: redo history discarded after new edits.
  5. Persistence: snapshot + log with fsync.
  6. Recovery: detect partial logs and restore last valid state.

3.3 Non-Functional Requirements

  • Performance: O(1) per undo/redo operation.
  • Reliability: deterministic replay, no corruption on crash.
  • Usability: clear error messages.

3.4 Example Usage / Output

$ ./undo_demo
> draw line 0 0 10 10
> draw rect 5 5 20 20
> undo
> redo

3.5 Data Formats / Schemas / Protocols

  • Log entry: command type + parameters + checksum.
  • Snapshot: serialized canvas state with version number.

JSON error shape (if --json):

{ "error": { "code": "INVALID_COMMAND", "message": "unknown command" } }

3.6 Edge Cases

  • Undo at history start
  • Redo at history end
  • New command after undo (truncate redo)
  • Crash during snapshot write

3.7 Real World Outcome

Deterministic demo uses fixed command sequence.

3.7.1 How to Run (Copy/Paste)

cc -std=c11 -O2 -o undo_demo src/undo_demo.c
./undo_demo --script samples/script.txt

3.7.2 Golden Path Demo (Deterministic)

samples/script.txt:

draw line 0 0 10 10
draw rect 5 5 20 20
undo
redo

Expected result: canvas contains both line and rectangle.

3.7.3 CLI Transcript (Success + Failure)

$ ./undo_demo --script samples/script.txt
APPLY draw line
APPLY draw rect
UNDO draw rect
REDO draw rect
$ echo $?
0

$ ./undo_demo --script samples/bad.txt
ERROR: INVALID_COMMAND (unknown command)
$ echo $?
1

Exit codes:

  • 0 success
  • 1 user error
  • 2 system error

4. Solution Architecture

4.1 High-Level Design

[Commands] -> [History List + Cursor] -> [Canvas State]
                     |
                     v
            [Snapshot + Log]

4.2 Key Components

| Component | Responsibility | Key Decisions | |———–|—————-|—————| | Command Objects | Encapsulate do/undo | Store full parameters | | History | List of commands + cursor | Truncate redo on new edit | | Persistence | Snapshot + log | fsync + atomic rename |

4.3 Data Structures (No Full Code)

typedef struct {
    int type;
    int params[8];
} Cmd;

typedef struct {
    Cmd cmds[MAX];
    int cursor;
    int count;
} History;

4.4 Algorithm Overview

Key Algorithm: Undo/Redo

  1. Undo: if cursor >= 0, call undo on cmds[cursor], decrement cursor.
  2. Redo: if cursor+1 < count, increment cursor, call do.

Complexity Analysis:

  • Time: O(1) per undo/redo
  • Space: O(n) for history

5. Implementation Guide

5.1 Development Environment Setup

cc --version

5.2 Project Structure

project-root/
├── src/
│   ├── history.c
│   ├── history.h
│   ├── persistence.c
│   └── undo_demo.c
├── tests/
│   └── test_history.c
└── Makefile

5.3 The Core Question You’re Answering

“How do I make time reversible in a system without corrupting state?”

5.4 Concepts You Must Understand First

  1. Command pattern with do/undo
  2. Snapshot + log persistence
  3. Determinism and replay

5.5 Questions to Guide Your Design

  1. What data does each command need to undo correctly?
  2. How will you truncate redo history safely?
  3. How will you detect partial log writes?

5.6 Thinking Exercise

Apply commands A, B, C. Undo twice. Add D. What is the valid history now?

5.7 The Interview Questions They’ll Ask

  1. “Why must redo history be discarded after new edits?”
  2. “How do you make undo deterministic?”
  3. “What order do you fsync in a crash-safe log?”

5.8 Hints in Layers

Hint 1: Start with an in-memory history only.

Hint 2: Add persistence after undo/redo works.

Hint 3: Use checksums to detect partial writes.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | Command pattern | “Design Patterns” | Command | | Durability | “Designing Data-Intensive Applications” | Ch. 7 | | Error handling | “Effective C” | Ch. 8 |

5.10 Implementation Phases

Phase 1: In-memory History (3-4 days)

  • Implement commands and cursor logic.
  • Add undo/redo to simulator.

Phase 2: Branching + Validation (3-4 days)

  • Truncate redo branch on new command.
  • Add state hash for validation.

Phase 3: Persistence (4-5 days)

  • Add snapshot and log.
  • Implement recovery on startup.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |———-|———|—————-|———–| | History storage | Array, linked list | Array | Simple indexing and cursor | | Persistence | Snapshot only, log only, both | Snapshot + log | Balanced durability and performance |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———-|———|———-| | Unit Tests | Command do/undo | move, delete | | Integration Tests | History sequences | A,B,C undo redo | | Crash Tests | Log recovery | truncated log |

6.2 Critical Test Cases

  1. Undo at history start does nothing.
  2. Redo at history end does nothing.
  3. New command after undo truncates redo branch.

6.3 Test Data

Commands: draw line, draw rect, undo, redo

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |——–|———|———-| | Missing undo data | Cannot restore state | Store full parameters | | Non-deterministic commands | Redo differs | Store seeds/timestamps | | Snapshot corruption | Crash recovery fails | temp file + rename |

7.2 Debugging Strategies

  • Hash the canvas state after each command.
  • Compare replayed state with original.

7.3 Performance Traps

Serializing full snapshots too frequently can be expensive; use periodic snapshots.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a redo limit and display history length.
  • Add a history command to list commands.

8.2 Intermediate Extensions

  • Implement branching history instead of truncation.
  • Compress log entries.

8.3 Advanced Extensions

  • Multi-user collaborative history with conflict resolution.
  • Real-time persistence with incremental snapshots.

9. Real-World Connections

9.1 Industry Applications

  • Graphics editors, IDEs, and CAD tools all rely on undo/redo.
  • Inkscape (history stack)
  • GIMP (undo engine)

9.3 Interview Relevance

  • Temporal correctness and history models are common in systems interviews.

10. Resources

10.1 Essential Reading

  • “Design Patterns” (Command pattern)
  • “Designing Data-Intensive Applications” (durability)

10.2 Video Resources

  • Undo/redo system design tutorials

10.3 Tools & Documentation

  • fsync and rename manpages

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain the history cursor model.
  • I can explain why redo is truncated.
  • I can explain crash-safe log ordering.

11.2 Implementation

  • Undo/redo works for all commands.
  • Persistence restores exact state.
  • Recovery ignores partial logs.

11.3 Growth

  • I can describe how I made commands deterministic.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Command history with undo/redo works.
  • Deterministic tests pass.

Full Completion:

  • Persistence with snapshot + log and crash recovery.

Excellence (Going Above & Beyond):

  • Branching history and visualization of branches.

13. Additional Content Rules (Compliance)

  • Deterministic demos in §3.7.
  • Failure demo with exit codes included.
  • Cross-links included in §2.1 and §2.2.