Hi, this is John with this week’s Coding Challenge.
🙏 Thank you for being a subscriber, I’m honoured to have you as a reader. 🎉
If there is a Coding Challenge you’d like to see, please let me know by replying to this email📧
This challenge is to build your own version of fzf, the command-line fuzzy finder.
fzf is one of those tools that changes how you use a terminal. You pipe a list of things into it, start typing a few letters, and it narrows a list of a million items down to the one you wanted before you have finished typing. It is used for finding files, checking out git branches, searching shell history, killing processes, and about a hundred other things.
Underneath the friendly interface there is a surprising amount of interesting engineering: a scoring algorithm that ranks matches the way a human would, a terminal user interface built from raw escape sequences, and a design that is responsive while a huge stream of input. Building your own fzf is a great way to learn all three.
In this challenge you’re going to build your own fuzzy finder. It will read a list of items, take over the terminal, and let the user type a query that filters and re-ranks the list on every keystroke. By the end you’ll have a tool you can drop into your own shell aliases and scripts in place of the real fzf.
In this introductory step you’re going to set your environment up ready to begin developing and testing your solution.
Choose your target platform and programming language. You’ll be reading key presses one at a time and drawing directly to the terminal, so look for a language that lets you put the terminal into raw mode and write escape sequences, either from its standard library or from a small terminal library. Avoid anything that hides the terminal from you completely.
Before you write any code, spend time with the real thing. Install fzf if you don’t already have it, then read the fzf man page and the project README. Pipe some things into it and watch how it behaves as you type:
find . -type f | fzf
git ls-files | fzf
history | fzf
Pay attention to the small details, like what happens to the screen when you quit, what the counter above the prompt shows, and which items float to the top when you type a few letters.
You’ll also want some test data. A big list of lines is ideal, so grab a word list and generate a large file of paths to use throughout the challenge:
wc -l /usr/share/dict/words
find / -type f 2>/dev/null | head -1000000 > /tmp/paths.txt
wc -l /tmp/paths.txt
Keep both files handy, you’ll use the small one for correctness and the large one for performance.
In this step your goal is to build the skeleton of the finder: read items, show them, and let the user pick one.
Your tool should read newline-delimited items from standard input and display them in an interactive full-screen list, with a prompt where the user’s query will eventually go. Pressing Enter should accept the item the cursor is on and print it to standard output. Pressing Ctrl-C, Ctrl-G or Esc should abort without printing anything.
The finder should draw itself on the alternate screen buffer, so when it exits the user’s original terminal contents and cursor position are exactly as they were before. It should exit with the right status code, because scripts depend on these: 0 when an item was selected, 1 when there was no match, 2 on error, and 130 when the finder was interrupted.
Testing: Run your finder against a small list and select an item:
printf "apple\nbanana\ncherry\n" | ccfzf
You should get a full screen list of the three items, and after pressing Enter you should be back at your normal shell prompt with your previous screen contents intact, and the chosen item printed. Check the exit codes:
printf "apple\nbanana\n" | ccfzf; echo "exit: $?"
Selecting an item should report exit: 0, and pressing Esc should report exit: 130. Try it with a much larger input to make sure nothing falls over:
ccfzf < /tmp/paths.txt
In this step your goal is to make the finder filter as the user types.
Your finder should accept typed characters into the query and narrow the list to the items that match. A match is a fuzzy match: the query characters must appear in the item in order, but they do not have to be next to each other. So abc matches a_big_cat and alphabetacharlie, but not acb.
Matching should use smart case by default, which means the query is matched case-insensitively unless it contains an uppercase letter, in which case it becomes case-sensitive. The user should be able to override this with -i or --ignore-case to force case-insensitive matching, and +i or --no-ignore-case to force case-sensitive matching.
Now that there is a query, the rest of the default key bindings should work too. Ctrl-K, Ctrl-P and Up should move the cursor up the screen, and Ctrl-J, Ctrl-N and Down should move it back down. Remember that the default layout draws the list upwards from the prompt with the best match at the bottom, so moving up the screen walks further down the results, and the cursor starts on the best match with nowhere below it to go. Backspace should delete the character before the cursor, Ctrl-W should delete the word before it, Ctrl-U should clear the query, and Ctrl-A and Ctrl-E should jump the cursor to the start and end of the query.
Finally, add -q or --query=STR so the finder can be started with a query already typed. It saves a lot of typing when you are testing the steps that follow.
Testing: Filter the word list and watch the results change on every keystroke:
ccfzf < /usr/share/dict/words
Type fxf and confirm every remaining item contains an f, then a x, then an f, in that order. Type README against a file list and check that smart case has made the match case-sensitive, then try the same query with -i and confirm lower case matches come back:
git ls-files | ccfzf -i
Move up and down with the arrow keys and with the control keys and confirm both work, then check each editing key does what it should. Check that -q starts you off with the list already narrowed:
git ls-files | ccfzf -q readme
In this step your goal is to rank the matches so the best one is at the top.
A fuzzy match on its own is not much use when a query matches ten thousand items. Your finder should score every match and sort the results best first. A good score rewards the things a we care about: characters that matched next to each other, characters that matched at the start of a word (after a space, /, -, _ or .), characters that matched at a camelCase transition, and matches that start nearer the beginning of the item.
Your finder should support --algo=v1|v2 and default to v2, which finds the best possible alignment of the query within the item. The v1 algorithm should be a faster option that is not guaranteed to find the best match.
When two items score the same, --tiebreak=CRI[,..] should decide the order, supporting the criteria length, begin, end and index, and defaulting to length. Finally, the list should show its work: highlight the characters of each item that the query matched.
Have a read of the fzf algorithm notes if you want to see how the original approaches this, but try it yourself first.
Testing: Check that the obvious best match wins:
printf "src/app/main.go\nsrc/main_test.go\nmain.go\ndocs/domain.md\n" | ccfzf -q main
main.go should sort above docs/domain.md, and the matched characters in each line should be highlighted. Compare the two algorithms on the same query:
ccfzf --algo=v1 < /tmp/paths.txt
ccfzf --algo=v2 < /tmp/paths.txt
Type the same query into both and confirm v2 gives at least as good a top result. Then check tiebreaking:
printf "abc\nabcdef\nabcd\n" | ccfzf -q abc --tiebreak=length
The shortest item should be first. Run it again with --tiebreak=index and confirm the input order is used instead.
In this step your goal is to make the finder start instantly and stay responsive, no matter how much input is coming.
Right now your finder probably reads all of its input before it draws anything. Real fzf starts up immediately and keeps reading in the background, so the user can begin typing while items are still arriving. Your finder should do the same: show the interface as soon as it starts, then update the item list, the match count and the result list as more input arrives, without ever blocking the keyboard.
To show what is happening, add an info line that displays how many items currently match out of the total number read so far. It should support --info=default|inline|hidden so the user can move it onto the prompt line or turn it off.
Two flags change the order items are considered in: --tac reverses the input, and --no-sort leaves matches in input order instead of score order.
The real test of this step is scale. Your finder should stay interactive with an input of at least one million items, filtering and re-sorting on every keystroke with no pause you can feel.
Testing: Check that the finder appears before the input has finished:
find / -type f 2>/dev/null | ccfzf
The interface should appear immediately and the counter should climb while you type. Try a deliberately slow producer:
(for i in $(seq 1 20); do echo "item $i"; sleep 0.5; done) | ccfzf
You should be able to type and move around while new items keep appearing. Then test at scale:
ccfzf < /tmp/paths.txt
Type a query one character at a time and confirm each keystroke feels instant. Check the info line with --info=inline and --info=hidden, and confirm --tac and --no-sort change the order as expected:
ccfzf --tac < /tmp/paths.txt
ccfzf --no-sort < /tmp/paths.txt
In this step your goal is to support extended-search mode, which turns the query box into a small search language.
Extended-search mode is enabled by default. In it, the query is split on spaces and each term must match, so src go finds items containing a fuzzy match for src and a fuzzy match for go. Individual terms can change how they match:
'wild matches items that contain wild exactly, not fuzzily.
^music matches items that start with music.
.mp3$ matches items that end with .mp3.
!fire matches items that do not contain a fuzzy match for fire.
a | b | c matches items that match any one of the terms.
Two flags change the rules. +x or --no-extended turns the mode off so the whole query is treated as one fuzzy term. -e or --exact makes every term an exact match, and in that mode a leading ' means the opposite, a fuzzy term.
Testing: Build a small list you can reason about:
printf "music/song.mp3\nmusic/song.wav\nvideo/clip.mp4\nfirewall.md\nsrc/main.go\n" > /tmp/ext.txt
Then check each form of term:
ccfzf -q "^music .mp3$" < /tmp/ext.txt
ccfzf -q "'song" < /tmp/ext.txt
ccfzf -q "!fire" < /tmp/ext.txt
ccfzf -q "mp3 | mp4" < /tmp/ext.txt
The first should leave only music/song.mp3, and the last should leave the two media files. Confirm +x treats a query with spaces as a single fuzzy term, and that -e makes song an exact match while 'song becomes fuzzy again.
In this step your goal is to let the user pick more than one item, and to control the query and the output from the command line.
Your finder should support -m or --multi for multi-select. Tab should mark the item under the cursor and move on, Shift-Tab should unmark it, marked items should be visibly different in the list, and accepting should print all of the marked items rather than just the one under the cursor. --multi=MAX should limit how many items can be marked.
Alongside that, add the options that make the finder easy to drive from a script:
-print-query prints the final query as the first line of output.
f or -filter=STR skips the interface completely and prints the matching items to standard output in score order.
1 or -select-1 accepts immediately when exactly one item matches, and 0 or -exit-0 exits immediately when nothing matches.
Testing: Mark a few items and check they all come out:
git ls-files | ccfzf -m
Press Tab on three items, then Enter, and confirm all three are printed. Check the limit is enforced with --multi=2. Then check the scripting options:
git ls-files | ccfzf -f go
git ls-files | ccfzf -q main --print-query
printf "only-one\n" | ccfzf -1 -q only; echo "exit: $?"
printf "apple\n" | ccfzf -0 -q zzz; echo "exit: $?"
The filter run should print matches in the same order the interactive list would show them, without ever clearing the screen. The -1 run should print only-one without you pressing anything, and the -0 run should exit straight away with exit: 1.
In this step your goal is to make your finder a good citizen of the shell.
So far your finder always takes over the whole screen. Add --height=[~]HEIGHT[%] so it can instead draw in a window below the cursor, leaving the rest of the terminal visible, with ~ meaning the window should shrink to fit the content. This is how most people use fzf day to day.
The list arrangement should be configurable too, with --layout=default|reverse|reverse-list. The default puts the list above a prompt at the bottom, reverse puts the prompt at the top with the list below it, and reverse-list puts the list at the top with the prompt at the bottom. --reverse should be a shorthand for --layout=reverse.
Then add the features that let it slot into pipelines and key bindings:
-ansi should interpret ANSI colour codes in the input, rendering the colours in the list and matching against the text rather than the escape sequences.
-read0 should read NUL-delimited input and -print0 should write NUL-delimited output, so your finder is safe with filenames containing newlines.
-expect=KEYS should accept on any of the listed keys as well as Enter, and print the name of the key that was pressed as the first line of output.
When standard input is a terminal, your finder should run $FZF_DEFAULT_COMMAND to produce the item list, and it should read default options from $FZF_DEFAULT_OPTS before the ones on the command line.
Testing: Check the window and layouts:
git ls-files | ccfzf --height=40%
git ls-files | ccfzf --height=~40% --reverse
Your shell prompt and previous output should still be visible above the finder, and the second command should shrink the window when few items match. Then check the rest:
grep --color=always -r "func" . | ccfzf --ansi
find . -type f -print0 | ccfzf --read0 --print0 | xargs -0 ls -l
git ls-files | ccfzf --expect=ctrl-o,ctrl-e
export FZF_DEFAULT_COMMAND='find . -type f'
export FZF_DEFAULT_OPTS='--reverse --height=40%'
ccfzf
With --ansi the colours from grep should appear in the list and typing an escape sequence like [0m should match nothing. The --expect run should print ctrl-o on its own line before the selected item. The last run should start the finder with no input piped in, using the command and options from the environment.
In this step your goal is to add the two features that make fzf genuinely powerful: matching on part of an item, and previewing what is under the cursor.
First, fields. -d or --delimiter=REGEX should split each item into fields, defaulting to AWK-style whitespace splitting. -n or --nth=N[,..] should restrict matching to the given fields, so the user can search on one column and ignore the rest. --with-nth=N[,..] should change which fields are displayed. Both should accept the field index expressions 1, -1, 3..5, 2.., ..-3 and ...
Second, previews. --preview=COMMAND should run a command each time the cursor moves and show its output in a preview window beside the list. Inside the command, {} should be replaced with the current item single quoted, {1}, {2} and so on with its fields, {n} with its zero-based index, and {+} with the selected items. --preview-window=[POSITION][,SIZE[%]] should place the window up, down, left or right, defaulting to right,50%.
Testing: Search on a single column of a table:
ps aux | ccfzf -n 11.. --with-nth 11..
You should be matching and seeing only the command, not the process statistics. Try a different delimiter:
ccfzf -d : -n 1 < /etc/passwd
Typing a user name should match, but typing part of a home directory path should not. Then check the previews:
git ls-files | ccfzf --preview 'head -50 {}'
git ls-files | ccfzf --preview 'head -50 {}' --preview-window=up,30%
git log --oneline | ccfzf --preview 'git show {1}'
The preview should update as you move the cursor, the window should move where you asked it to, and the git log example should show the full commit for the hash in the first field.
Once you have the core finder working, here are some ideas to take it further:
Add -prompt, -pointer and -marker so the interface can be styled.
Add -color to support custom colour schemes, including the built-in dark, light and 16 themes.
Add -bind so users can attach their own actions to their own keys.
Add -header and -header-lines to keep a fixed header above the list.
Add -cycle so moving past the end of the list wraps around to the start.
Add -history so queries are saved between runs and can be recalled with Ctrl-P and Ctrl-N.
Add the reload action so the item list can be regenerated from a new command while the finder is running.
Add -listen so a running finder can be controlled over HTTP.
Write the shell integration: Ctrl-T to insert a file path, Ctrl-R to search history, and *<Tab> completion.
Benchmark your finder against the real fzf on a list of ten million items and see how close you can get.
If you think your solution is an example other developers can learn from please share it, put it on GitHub, GitLab or elsewhere. Then let me know via Bluesky or LinkedIn or just post about it there and tag me. Alternately please add a link to it in the Coding Challenges Shared Solutions Github repo
I’m writing these challenges to help you develop your skills as a software engineer based on how I’ve approached my own personal learning and development. What works for me, might not be the best way for you - so if you have suggestions for how I can make these challenges more useful to you and others, please get in touch and let me know. All feedback is greatly appreciated.
You can reach me on Bluesky, LinkedIn or through SubStack
Thanks and happy coding!
John
Comments
Post a Comment