Project 14: Interactive Fuzzy Finder (Full fzf Clone)

Build a full-screen TUI fuzzy finder with raw input, live updates, worker pools, and a preview pane.

Quick Reference

Attribute	Value
Difficulty	Level 3: Advanced
Time Estimate	3-4 weeks
Main Programming Language	Go (Alternatives: Rust, C++)
Alternative Programming Languages	Rust, C++
Coolness Level	Level 4: Hardcore
Business Potential	Level 2: Dev tooling
Prerequisites	P13, terminal basics, concurrency
Key Topics	TUI rendering, raw mode, worker pools, incremental search

1. Learning Objectives

By completing this project, you will:

Implement raw-mode terminal input and key parsing.
Build a live-updating fuzzy search pipeline.
Use worker pools and cancellation for responsiveness.
Render a flicker-free TUI with a preview pane.
Handle large input streams with low latency.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Responsive TUI Architecture

Fundamentals

A responsive terminal UI must separate input handling, search computation, and rendering. Raw mode enables reading key presses without waiting for Enter. The input loop updates the current query, which triggers a search in background workers. Results are streamed to the renderer, which updates the screen at a fixed rate to avoid flicker. This is a classic producer-consumer pipeline.

The core challenge is latency: the UI must remain responsive even when matching thousands of candidates. That means cancellation of in-flight work and careful scheduling of render updates.

Deep Dive into the concept

The architecture typically consists of four components: input reader, matcher workers, result merger, and renderer. The input reader emits query updates. Each query update increments a version number and cancels previous work. Worker goroutines match chunks of candidates and emit scored results tagged with the query version. The merger discards stale results and keeps the top-K for the current query. The renderer draws the UI based on the latest top-K and cursor position, refreshing at 30-60 FPS.

Rendering uses ANSI escape codes to clear and redraw the screen, move the cursor, and apply color. To avoid flicker, you either do partial updates or render to an off-screen buffer string and write it in one call. The preview pane can be populated by running an external command on the selected item; this must be throttled to avoid blocking the UI.

Handling terminal resizing adds complexity: you need to re-render on SIGWINCH. You also need to restore the terminal state on exit, even if the program crashes, which requires defer-based cleanup or signal handlers.

How this fits on projects

This TUI is the interactive shell of the fuzzy matching engine from P13 and a standalone tool for real-world use.

Definitions & key terms

raw mode -> terminal mode without line buffering
debounce -> wait briefly before acting on rapid input
worker pool -> group of concurrent workers
render loop -> periodic redraw of screen

Mental model diagram (ASCII)

Input -> Query Channel -> Worker Pool -> Result Merger -> Renderer
   ^                                           |
   |-------------------------------------------|
         (cancel stale results by version)

How it works (step-by-step)

Switch terminal into raw mode.
Read key presses and update query.
Spawn workers to match candidates.
Merge results, discard stale versions.
Render UI at fixed frame rate.

Minimal concrete example

queryVer++
queryCh <- Query{Text: q, Version: queryVer}

Common misconceptions

Misconception: Rendering on every keystroke is enough. Correction: You need a render loop to avoid flicker and throttle updates.
Misconception: Worker goroutines can run forever. Correction: They must be cancellable to keep latency low.

Check-your-understanding questions

Why use a query version number?
How do you prevent flickering output?
Why is cancellation important for responsiveness?

Check-your-understanding answers

To discard results from outdated queries.
Render in one buffer or use minimal updates at fixed FPS.
To avoid expensive work on stale queries.

Real-world applications

fzf, skim, peco
interactive pickers in CLIs

Where you’ll apply it

This project: Section 3.2 Functional Requirements and Section 4.4 Algorithm.
Also used in: P13-fuzzy-string-matcher-fzf-style.

References

fzf source code
ANSI terminal control documentation

Key insights

Responsive TUIs require concurrency and careful render scheduling, not just fast algorithms.

Summary

A good fuzzy finder is as much about architecture and UI as it is about scoring.

Homework/Exercises to practice the concept

Build a minimal raw-mode input loop and print keys.
Render a static screen with ANSI escape codes.

Solutions to the homework/exercises

Use termios to disable canonical mode and echo.
Use \x1b[2J to clear screen and \x1b[H to move cursor.

3. Project Specification

3.1 What You Will Build

A CLI tool mini-fzf that reads items from stdin, provides an interactive search UI, supports navigation, selection, and a preview pane. It uses worker goroutines to score matches and updates results as you type.

3.2 Functional Requirements

Raw input: read keystrokes without Enter.
Incremental search: update results on each query change.
Worker pool: parallel scoring of candidates.
Result merging: keep top-K results.
Preview pane: optional external command to preview selected item.
Key bindings: arrows, Enter, Ctrl-C, Backspace.

3.3 Non-Functional Requirements

Latency: <10ms for 100k candidates on query update.
Reliability: clean terminal restore on exit.
Usability: clear UI and help output.

3.4 Example Usage / Output

$ find . -type f | ./mini-fzf
[Interactive UI]
> src/ma
  4/1234
  > src/main.rs
    src/matcher.go
    src/main_test.go

3.5 Data Formats / Schemas / Protocols

Input: newline-separated candidate strings from stdin.

3.6 Edge Cases

No input items
Very long lines
Terminal resize events

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

find . -type f | ./mini-fzf --preview 'sed -n "1,80p" {}'

3.7.2 Golden Path Demo (Deterministic)

Use a fixed input list and disable time-based animations for test output.

3.7.3 CLI Transcript (Success + Failure)

$ printf "a\nb\nc\n" | ./mini-fzf
[Interactive UI]
> b
  1/3
  > b
exit code: 0

$ ./mini-fzf --preview "" 
error: preview command is empty
exit code: 2

4. Solution Architecture

4.1 High-Level Design

+--------+    +-----------+    +-----------+    +-----------+
| Input  | -> | WorkerPool| -> | ResultMerge| ->| Renderer  |
+--------+    +-----------+    +-----------+    +-----------+

4.2 Key Components

4.3 Data Structures (No Full Code)

type Query struct { Text string; Version int }

4.4 Algorithm Overview

Read input list into memory or stream chunks.
On query update, cancel previous workers and start new ones.
Merge results for current query version.
Render UI at fixed FPS.

Complexity Analysis

Matching: O(N * L) per query
UI: O(K) per frame

5. Implementation Guide

5.1 Development Environment Setup

go build -o mini-fzf ./cmd/mini-fzf

5.2 Project Structure

mini-fzf/
├── cmd/
│   └── mini-fzf/
│       └── main.go
├── internal/
│   ├── input.go
│   ├── worker.go
│   ├── merge.go
│   └── render.go
└── fixtures/

5.3 The Core Question You’re Answering

“How do I keep a terminal UI responsive while heavy matching runs in the background?”

5.4 Concepts You Must Understand First

Terminal raw mode and escape sequences.
Worker pool design and cancellation.
Rendering loops and buffering.

5.5 Questions to Guide Your Design

How will you parse arrow keys and control sequences?
How will you cancel stale matching work?
How will you avoid flicker during redraw?

5.6 Thinking Exercise

If matching takes 200ms per query, how can the UI still feel instant?

5.7 The Interview Questions They’ll Ask

How would you design a responsive TUI for large input sets?
How do you cancel in-flight work in a worker pool?

5.8 Hints in Layers

Hint 1: Separate input, matching, and rendering into goroutines. Hint 2: Use a query version counter to discard old results. Hint 3: Render at a fixed FPS rather than on every event.

5.9 Books That Will Help

5.10 Implementation Phases

Phase 1: Raw Input + Basic UI (1 week)

Raw mode input and simple rendering.
Checkpoint: UI updates on keypress.

Phase 2: Matching Pipeline (1 week)

Integrate fuzzy matcher + worker pool.
Checkpoint: results update on query.

Phase 3: Preview + Polish (1 week)

Add preview pane and keybindings.
Checkpoint: stable UX with low latency.

5.11 Key Implementation Decisions

6. Testing Strategy

6.1 Test Categories

6.2 Critical Test Cases

Arrow navigation updates selection correctly.
Query changes cancel old workers.
Preview pane updates for selection.

6.3 Test Data

input: 100k file paths
query: "main"
expected: top results update in <10ms

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

7.2 Debugging Strategies

Add logging of query version and worker outputs.
Temporarily reduce candidate list to debug UI.

8. Extensions & Challenges

8.1 Beginner Extensions

Add custom key bindings.
Add toggle for case sensitivity.

8.2 Intermediate Extensions

Add multiple selection mode.
Add preview caching.

8.3 Advanced Extensions

Add async preview execution with throttling.
Implement GPU-accelerated terminal rendering (experimental).

9. Real-World Connections

9.1 Industry Applications

Developer productivity tools
Interactive pickers in CLIs

fzf, skim, peco
tui-go libraries

9.3 Interview Relevance

Concurrency design and UI responsiveness

10. Resources

10.1 Essential Reading

fzf source and algorithm
ANSI escape code references

10.2 Tools & Documentation

tcell or termui (Go TUI libs)
stty -a for terminal inspection

Previous: P13-fuzzy-string-matcher-fzf-style
Next: P15-build-your-own-ripgrep

11. Self-Assessment Checklist

11.1 Understanding

I can explain raw mode input and key parsing.
I can explain worker pool cancellation.

11.2 Implementation

UI remains responsive under heavy load.
Preview pane updates correctly.

11.3 Growth

I can describe improvements for large datasets.

12. Submission / Completion Criteria

Minimum Viable Completion:

Basic TUI with incremental search

Full Completion:

Worker pool + preview pane

Excellence (Going Above & Beyond):

Multi-select + advanced keybindings
Latency metrics and profiling