Command History

History is the shell feature with the best effort-to-love ratio: a list of what you've typed, an index into it, and a tiny expansion language (!!, !42, !grep) — an afternoon of implementation that users touch hundreds of times a day. It's also this course's cleanest exercise in stateful text processing, after chapters of stateless parsing.

The data structure

An append-only, numbered list:

  1  ls -la
  2  cat notes.txt
  3  grep TODO src/main.c

Every executed line appends (the history built-in prints exactly the view above). Real shells bound it (HISTSIZE, dropping oldest — a ring buffer in spirit) and persist it across sessions (~/.bash_history, loaded at startup, appended at exit — why your commands survive reboots). Two authenticity details that tests love and users rely on:

• Failed commands are still history. You'll want to recall-and-fix that typo'd command — history records attempts, not successes.
• The expansion isn't history; its result is. Type !! and history records the command !! expanded to — so !! twice runs the same thing twice, rather than recursively meaning "the line that said !!". Expansion happens before recording; pin that ordering.

Bang expansion: the mini-language

History earns its keyboard shortcuts through ! expansion, applied to the line before any other processing:

!!        the previous command                 (sudo !! — the classic)
!42       history entry number 42
!grep     the MOST RECENT command starting with "grep"
!?TODO    most recent command CONTAINING "TODO"   (bonus form)

The algorithm is lookup-and-substitute: scan the line for ! sequences, resolve each against the history list, splice the text in, then hand the expanded line to the tokenizer (stage order: history expansion runs first of all — even before quotes are parsed, with the one mercy that ! inside single quotes is protected). Resolution failures are errors, not silence: !999 with 3 entries → event not found — and crucially, an errored line is not executed and not recorded.

Prefix search (!grep) walks the list backward — most recent match wins; that's the whole reason the feature is useful (you want your latest grep, not your first). It's also the same backward-search instinct as Ctrl-R (interactive incremental search), which is the same data structure with a fancier UI — implement !prefix and you've implemented Ctrl-R's core.

Where it sits in your shell's loop

read line
line = history_expand(line)     ← may error: report, skip, don't record
if line non-empty: append to history
tokenize → parse → execute       (everything you've already built)

Two lines added to the loop; the feature set of a real shell's recall system. Note what stays untouched: every stage downstream sees ordinary text and neither knows nor cares that a human typed four characters instead of forty. Stage separation, one more time, with feeling.

Your exercise: History & Bang Expansion

Process a session's worth of lines: maintain the numbered list, expand !! / !n / !prefix, output per the spec (expanded lines, history listings, event-not-found errors). The graded corners are the ordering rules above — expanded-text-gets-recorded (not the bang), failed expansion records nothing, backward search for prefixes, and numbering that never reuses IDs even as entries scroll away. All bookkeeping, zero algorithms — which, one lesson from your shell's capstone, is its own advertisement: most of a real shell isn't clever; it's a hundred small contracts kept precisely. You now keep them.