Puppeteering the Shell: Inside dvorka/hstr
How a pure C utility uses radix sort, custom UTF-8 parsing, and a controversial system call to turn terminal history into a 60fps database.
HSTR (HiSToRy) is a command line utility that brings improved bash/zsh command completion from the history. It aims to make completion easier and more efficient than Ctrl-r.
- HSTR bypasses subshell limitations by using the `TIOCSTI` system call to inject characters directly into the terminal's input buffer.
- To maintain zero-latency filtering over massive history files, the tool implements a custom Radix sort rather than relying on standard C library sorting functions.
- A specialized logarithmic formula—balancing frequency, recency, and complexity—replaces raw chronological searching to present the most relevant commands first.
- Unlike generalist tools like fzf or heavy database replacements like Atuin, HSTR acts as a hyper-optimized client sitting directly on top of the standard shell history text file.
The standard terminal reverse search, invoked via Ctrl-r, is a blind, linear crawl backward through time. It is a functional tool for finding the command you typed five minutes ago, but it fails spectacularly as a mechanism for managing a decade of complex shell interactions. When a user needs to find a specific, multi-line awk script they ran last year, the standard search is simply inadequate.
HSTR (History) is a dedicated C utility designed to replace Ctrl-r entirely. It transforms the passive, chronological shell history file into an interactive, 60fps "suggest box." It is not a general-purpose fuzzy finder, nor is it a heavy database replacement. It is a razor-sharp, hyper-optimized client that sits perfectly on top of the existing Bash or Zsh history architecture.
The Kernel Puppeteer
The fundamental challenge of building a terminal history tool is the handoff. When a user selects a command in a child process (like HSTR), how does that command get placed onto the prompt of the parent process (the shell) ready for execution or editing? A naive approach might copy the text to the clipboard, requiring the user to manually paste it. HSTR takes a much more aggressive, low-level approach.
In src/hstr_utils.c, the function fill_terminal_input leverages the ioctl system call, specifically targeting TIOCSTI (Terminal Input Out Control). This is a controversial and powerful feature of Unix-like systems. It allows a process to push characters directly into the terminal's input buffer. From the perspective of the parent shell, it appears exactly as if the user had rapidly typed the characters on the keyboard.
This "puppeteering" eliminates the need for subshell hacks or complex environment variable passing. The child process literally dictates the input to the parent. However, because TIOCSTI can be used maliciously to inject commands, modern kernels often restrict it. HSTR's codebase includes explicit fallbacks, such as checking for WSL (Windows Subsystem for Linux) environments where the call is unsupported, gracefully degrading to fprintf(stderr) when necessary.
60 Frames Per Second in the Junk Drawer
A responsive "search-as-you-type" interface requires absolute zero-latency. When a user types a character, the UI must filter and re-render instantly. If the history file contains 20,000 entries, standard qsort implementations begin to stutter, breaking the illusion of a fluid interface.
To guarantee performance, HSTR bypasses standard library sorting for large datasets. When optionBigKeys is triggered, the engine switches to a custom Radix Sort implementation (src/radixsort.c). Instead of comparing full strings, Radix sort groups items by individual character positions, processing massive lists in linear time relative to the key length. This algorithmic choice ensures that the UI remains locked at 60fps, regardless of the history file's size.
Furthermore, writing a TUI in pure C requires meticulous handling of text rendering. The ncurses library is powerful but assumes a rigid grid. UTF-8 multi-byte characters, such as emojis or complex prompt symbols, can misalign the layout or break the selection highlight bar. In hstr_utils.c, a custom hstr_strlen function manually checks the high bits (1<<7) of each byte to accurately determine the display width of characters, ensuring the UI remains pristine across diverse terminal configurations.
The Logarithmic Brain
Filtering out noise is only half the battle; presenting the best result first is the other. Chronological sorting is rarely optimal for history search. The command you ran 100 times last month is often more relevant than the typo you made five seconds ago.
The "brain" of HSTR resides in src/hstr_history.c. The history_ranking_function evaluates every matching command using a specific formula: RANK + (log(ORDER) * 10.0) + LENGTH. This equation elegantly balances three competing metrics.
The RANK represents raw frequency—how often the command has been used overall. The log(ORDER) applies a logarithmic curve to recency, providing a significant boost to commands used recently, but tapering off quickly so that a command from yesterday doesn't automatically bury a highly frequent command from last week. Finally, LENGTH provides a linear bump to longer, more complex commands, assuming that a 50-character sed pipeline is inherently more valuable to retrieve than a simple ls -l.
The Dedicated Engine vs. The Generalists
The modern terminal ecosystem offers multiple approaches to history management. General-purpose fuzzy finders like fzf are incredibly versatile, capable of filtering everything from files to git branches. Database-backed replacements like Atuin offer synchronization across machines and complex querying capabilities.
HSTR deliberately chooses a different path. It is neither a generalist tool requiring complex shell aliases to function as a history manager, nor a heavy daemon requiring a database schema. It is a dedicated client that treats the existing flat text file (.bash_history or .zsh_history) as its single source of truth.
| Feature | HSTR | fzf | Atuin | McFly |
|---|---|---|---|---|
| Primary Language | C | Go | Rust | Rust |
| Core Approach | Dedicated UI | General Filter | Database & Sync | Neural Net |
| Requires Daemon/DB | No | No | Yes | No |
| Built-in History Mgmt | Yes | No | Yes | No |
This targeted approach allows for features that generalist tools lack by default, such as a built-in "Favorites" list (managed via an internal hashset) and the ability to selectively delete sensitive commands directly from the UI. By focusing exclusively on the history problem, HSTR delivers a frictionless experience that feels like a native extension of the shell itself.