Project 13: Tab Completion Engine

Build a tab completion engine for commands and file paths.

Quick Reference

Attribute Value
Difficulty Level 3: Advanced (The Engineer)
Time Estimate 1-2 weeks
Main Programming Language C
Alternative Programming Languages Rust, Go
Coolness Level Level 4: Hardcore Tech Flex
Business Potential 1. The “Resume Gold” (Educational/Personal Brand)
Prerequisites PATH lookup, directory traversal, line editor integration
Key Topics prefix matching, LCP, UI rendering

1. Learning Objectives

By completing this project, you will:

  1. Explain and implement prefix matching in the context of a shell.
  2. Build a working tab completion engine that matches the project specification.
  3. Design tests that validate correctness and edge cases.
  4. Document design decisions, trade-offs, and limitations.

2. All Theory Needed (Per-Concept Breakdown)

Completion, Prefix Matching, and UI Display

Fundamentals Tab completion predicts what the user intends to type and fills in the rest. A completion engine must detect context (command position vs argument), gather candidate matches (from PATH or filesystem), compute the longest common prefix, and display choices when multiple matches exist. The UI must integrate with the line editor so that the user’s input line is redrawn cleanly after displaying suggestions. Completion is one of the most visible usability features of a shell.

Deep Dive into the concept The first step in completion is context detection. If the cursor is in the first word of the line, completion should search for executable names in PATH. If the cursor is in later words, completion should search the filesystem relative to the current directory or a provided path prefix. This requires the completion engine to parse the current buffer up to the cursor, understand quoting, and identify the “fragment” to complete. A simple heuristic is to treat whitespace as separators, but a robust engine must respect quotes so that paths with spaces are handled correctly.

Once you have the fragment, you gather matches. For command completion, you scan each PATH directory and collect executable names that start with the fragment. For file completion, you list directory entries and match by prefix. You should consider hidden files (dotfiles) and decide whether to include them based on the fragment (many shells only show dotfiles if the fragment starts with .). Performance matters: scanning large directories on every tab can feel slow, so consider caching or limiting results.

If there is a single match, you can complete it immediately, adding a trailing slash for directories or a space for completed commands. If there are multiple matches, you compute the longest common prefix (LCP) across all candidates and extend the buffer to that prefix if it adds characters. If multiple matches still remain, you must display them in columns. Column rendering should respect terminal width and avoid disrupting the input line. The standard trick is to print a newline, render the list, and then redraw the prompt and the input buffer. This makes the completion UI feel smooth.

Completing within quoted strings adds complexity. If the fragment is inside quotes, you should not insert unescaped spaces or special characters. Some shells insert escaped spaces; others keep the quotes. For a minimal system, you can limit support to simple cases and document it, but a robust engine should preserve quotes correctly.

Finally, completion is an extensibility point. Many shells allow programmable completion based on command-specific rules (e.g., git checkout suggests branch names). Even if you do not implement programmable completion, you should structure your engine so you can add rule-based completions later: e.g., a completion registry keyed by command name.

How this fits on projects Completion integrates lexing, PATH lookup, filesystem traversal, and line editing, making it a capstone for interactive UX.

Definitions & key terms

  • Fragment: The partial word under the cursor.
  • LCP (Longest Common Prefix): The shared prefix among matches.
  • Context: Whether the fragment is a command or an argument.
  • Programmable completion: Command-specific completion rules.

Mental model diagram

buffer -> fragment -> candidates -> LCP -> insert -> render choices

How it works (step-by-step)

  1. Parse buffer up to cursor to identify fragment and context.
  2. Collect candidate matches from PATH or filesystem.
  3. Compute LCP and extend buffer if possible.
  4. If multiple matches remain, render list in columns.
  5. Redraw prompt and buffer with updated cursor position.

Minimal concrete example

Input:  git che<TAB>
Matches: checkout, cherry-pick
LCP:    che
Result: git che + list of matches

Common misconceptions

  • “Completion is just prefix search” -> context and UI matter.
  • “Listing matches is enough” -> you must redraw the input line.
  • “Spaces can be inserted freely” -> not inside quoted paths.

Check-your-understanding questions

  1. Why does completion need to parse the current buffer?
  2. What should happen when multiple matches share a longer prefix?
  3. How do you keep the input line intact after printing matches?

Check-your-understanding answers

  1. To detect command vs argument context and handle quoting.
  2. Extend the buffer to the LCP and show the match list.
  3. Redraw the prompt and buffer after listing candidates.

Real-world applications

  • Shells (bash, zsh, fish) and CLI tools.
  • IDEs and REPLs with autocompletion.

Where you’ll apply it

  • In this project: see §4.1 High-Level Design and §5.10 Phase 2.
  • Also used in: None

References

  • GNU Readline completion documentation.
  • “Effective Shell” (completion UX).

Key insights Completion is a synthesis of parsing, matching, and UI rendering.

Summary A good completion engine is fast, context-aware, and integrates cleanly with line editing to feel seamless.

Homework/Exercises to practice the concept

  1. Implement filename completion for the current directory.
  2. Add PATH-based command completion.
  3. Render matches in columns with correct spacing.

Solutions to the homework/exercises

  1. Use readdir and prefix filtering.
  2. Scan each PATH entry and test executability.
  3. Compute column widths and print in rows.

Line Editing, Termios, and Interactive Input

Fundamentals Interactive shells do more than read lines; they allow users to edit input with arrow keys, delete characters, and navigate history. This requires switching the terminal into raw or non-canonical mode using termios, reading input byte-by-byte, and interpreting escape sequences. A line editor maintains a buffer, a cursor position, and a render strategy so that the screen stays consistent with the buffer. Without proper line editing, a shell feels primitive and frustrating to use.

Deep Dive into the concept Terminals typically operate in canonical mode by default: the kernel buffers input until the user presses Enter, and it handles editing locally. For a custom line editor, the shell must disable canonical mode and echoing, then implement editing itself. Using tcgetattr() and tcsetattr(), you can toggle flags like ICANON and ECHO. In raw or “cbreak” mode, every keypress is delivered to the program immediately, allowing the shell to implement custom behavior. This also means the shell must handle Ctrl+C, Ctrl+D, and other control keys explicitly.

Arrow keys and other special keys arrive as escape sequences, typically beginning with . For example, the left arrow often sends . A line editor must parse these sequences and translate them into cursor movement. This is usually implemented as a small state machine: when  is seen, the editor reads subsequent bytes to identify the full sequence. The complexity grows as you support more keys (Home, End, Delete, Alt combinations).

Rendering is another challenge. The shell must redraw the current line after any edit without leaving artifacts. A common approach is to print ` ` to return to the beginning of the line, print the prompt and the buffer, then clear to end-of-line with , and finally reposition the cursor if it is not at the end. This must work even when the line wraps across terminal rows. Handling multi-line input and dynamic terminal resizing (SIGWINCH) are advanced topics but valuable for a robust editor.

History integration ties into editing. When the user presses the up arrow, the editor must replace the current buffer with a previous entry while preserving any partially typed text (often called the “history scratch buffer”). A good editor supports incremental search (Ctrl+R), but even basic navigation requires careful buffer management. This is why many shells use libraries like GNU Readline; in this project you will implement a minimal version to understand the mechanics.

Finally, input editing must be resilient. If the user sends EOF (Ctrl+D) on an empty line, the shell typically exits. If Ctrl+D is pressed with non-empty input, many shells delete the character under the cursor. These rules should be documented and tested so your editor feels consistent with user expectations.

How this fits on projects Line editing is the foundation of the interactive experience and integrates with history and completion systems.

Definitions & key terms

  • Canonical mode: Terminal mode where input is line-buffered by the kernel.
  • Raw mode: Terminal mode where input is delivered immediately.
  • Escape sequence: Multi-byte sequence for special keys.
  • Cursor: Position in the input buffer.

Mental model diagram

[terminal bytes] -> [editor state machine] -> [buffer + cursor] -> [render]

How it works (step-by-step)

  1. Switch terminal to raw/cbreak mode.
  2. Read bytes one at a time.
  3. Decode printable chars vs control/escape sequences.
  4. Update buffer and cursor accordingly.
  5. Re-render the line and restore cursor position.

Minimal concrete example

Input:  a b <left> X
Buffer: a X b
Cursor: between X and space

Common misconceptions

  • “Arrow keys are single bytes” -> they are escape sequences.
  • “Rendering is just printing the buffer” -> you must clear and reposition.
  • “Ctrl+D always exits” -> only when buffer is empty.

Check-your-understanding questions

  1. Why must canonical mode be disabled for custom line editing?
  2. How do you detect an arrow key press?
  3. What is the purpose of clearing to end-of-line?

Check-your-understanding answers

  1. Canonical mode buffers input and handles editing in the kernel.
  2. Parse escape sequences that begin with .
  3. To remove leftover characters from previous renders.

Real-world applications

  • Shells and REPLs.
  • Text-mode interfaces and TUIs.
  • CLI tools with interactive prompts.

Where you’ll apply it

References

  • GNU Readline documentation.
  • POSIX termios interfaces.

Key insights Line editing is a mini text editor running inside a terminal stream.

Summary A usable shell requires raw-mode input, escape-sequence parsing, and careful re-rendering to keep the display consistent.

Homework/Exercises to practice the concept

  1. Build a raw-mode reader that echoes characters manually.
  2. Add left/right arrow support.
  3. Implement delete and backspace with correct cursor motion.

Solutions to the homework/exercises

  1. Use termios to disable ICANON and ECHO, then print bytes yourself.
  2. Detect [ sequences and update the cursor.
  3. Modify the buffer and re-render from the prompt.

Argument Vector Construction and PATH Lookup

Fundamentals Before a shell can execute a command, it must convert a line of text into an argument vector (argv) and locate the program on disk. This seems simple, but it is the glue between parsing and execution. The first word becomes the command name, and the remaining words become arguments passed to the program. For external commands without a slash, the shell must search each directory in the PATH environment variable, build candidate paths, and test whether they are executable. A correct implementation handles empty path elements, . in PATH, and permission errors. Even minimal shells depend on correct argv construction and path resolution.

Deep Dive into the concept The execve() system call expects two critical inputs: argv, an array of strings where argv[0] is the program name, and envp, an array of environment variables. Building argv is easy only if you ignore quoting, escaping, and expansions; for a minimal executor, you may split on whitespace, but the code should still produce a valid, NULL-terminated array. In a full shell, argv construction happens after expansions, quote removal, and field splitting. The order matters: for example, quoted strings should not be split by whitespace, and globbing should expand to multiple argv entries. Even in a minimal shell, you should treat consecutive spaces as a single separator and preserve the token order exactly.

PATH lookup is equally subtle. If the command contains a /, the shell must treat it as a path and attempt to execute directly. If it does not, the shell searches the colon-separated list in PATH. Each element can be empty; an empty element means “current directory.” When you iterate over PATH, you must build dir + "/" + cmd carefully, handle trailing slashes, and check execute permissions with access(path, X_OK) or by attempting execve and checking errno. The shell should distinguish between “not found” and “not executable”: POSIX uses exit status 127 for missing commands and 126 for found but non-executable commands. For errors like ENOEXEC (text file without shebang), the shell may choose to run it with /bin/sh or return an error, depending on your design scope.

Another detail is the difference between execvp() and manual PATH search. execvp() searches PATH for you, but you still need to handle error mapping and messaging. If you implement the search manually, you can produce more informative diagnostics, record the resolved path, and implement hashing to cache results. Shells like bash maintain a hash table of command lookups to avoid repeated directory scans, invalidating the cache when PATH changes. While your minimal executor may skip hashing, you should structure the code so it can be added later.

Finally, argument vector construction is not just string splitting; it is a data-structure problem. You must allocate storage for each token, store them in a contiguous char* array, and ensure the array is NULL-terminated. You also need to decide ownership and lifetimes: who frees the strings after exec or built-in handling? A consistent memory strategy will prevent leaks and double frees. Even a small shell benefits from a “command struct” that owns argv, the original line, and any metadata such as redirections.

How this fits on projects This concept connects tokenization to execution and appears in every project that launches commands or resolves filenames.

Definitions & key terms

  • argv: Argument vector passed to execve().
  • PATH: Colon-separated list of directories used for command lookup.
  • Shebang: #! line that selects an interpreter for a script.
  • X_OK: Permission check for executability.

Mental model diagram

"ls -l /tmp" -> tokens -> argv[] -> PATH search -> /bin/ls -> execve

How it works (step-by-step)

  1. Tokenize line into words.
  2. Build argv array and append NULL terminator.
  3. If command contains /, attempt direct execve.
  4. Else iterate PATH entries, build candidate paths, test execute.
  5. On success, execve the resolved path; on failure, map errno.

Minimal concrete example

char *argv[] = {"ls", "-l", NULL};
execvp(argv[0], argv); // uses PATH automatically

Common misconceptions

  • “argv[0] doesn’t matter” -> many programs read argv[0] for mode.
  • “PATH search is simple” -> empty elements mean current directory.
  • “execvp handles errors” -> you must map errno to shell status.

Check-your-understanding questions

  1. When should the shell skip PATH search?
  2. What is the meaning of an empty PATH element?
  3. Why is argv required to be NULL-terminated?

Check-your-understanding answers

  1. When the command contains a / path separator.
  2. It refers to the current directory.
  3. execve uses NULL to know where the argument list ends.

Real-world applications

  • Any CLI launcher or shell.
  • Build systems and process managers.
  • Scripting environments that run external tools.

Where you’ll apply it

References

  • POSIX Shell Command Language (command search).
  • “Advanced Programming in the UNIX Environment” (exec family).

Key insights Correct argv construction and PATH lookup prevent confusing “command not found” failures.

Summary Tokenization and PATH search are the bridge from text input to executable code.

Homework/Exercises to practice the concept

  1. Implement a manual PATH search and print the resolved path.
  2. Test how empty PATH entries behave with . directories.
  3. Create a command with a slash and confirm PATH is ignored.

Solutions to the homework/exercises

  1. Split PATH on : and join with / and the command name.
  2. Insert empty elements and confirm lookup uses current directory.
  3. Use ./program to verify direct execution is attempted.

3. Project Specification

3.1 What You Will Build

A tab completion system that suggests commands and files and updates the input buffer.

Included:

  • Core feature set described above
  • Deterministic CLI behavior and exit codes

Excluded:

  • Programmable completion optional.

3.2 Functional Requirements

  1. Requirement 1: Detect completion context (command vs argument).
  2. Requirement 2: Complete commands using PATH lookup.
  3. Requirement 3: Complete files and directories by prefix.
  4. Requirement 4: Compute longest common prefix for multiple matches.
  5. Requirement 5: Render match lists without breaking input line.

3.3 Non-Functional Requirements

  • Performance: Interactive latency under 50ms for typical inputs; pipeline setup should scale linearly.
  • Reliability: No crashes on malformed input; errors reported clearly with non-zero status.
  • Usability: Clear prompts, deterministic behavior, and predictable error messages.

3.4 Example Usage / Output

$ ./mysh
mysh> git che<TAB>
mysh> git checkout
mysh> ls /usr/lo<TAB>
mysh> ls /usr/local/

3.5 Data Formats / Schemas / Protocols

  • Completion candidates list and current fragment.

3.6 Edge Cases

  • Huge directories
  • Spaces in paths
  • Quoted fragments

3.7 Real World Outcome

This is the exact behavior you should be able to demonstrate.

3.7.1 How to Run (Copy/Paste)

  • make
  • ./mysh

3.7.2 Golden Path Demo (Deterministic)

$ ./mysh
mysh> git che<TAB>
mysh> git checkout
mysh> ls /usr/lo<TAB>
mysh> ls /usr/local/

3.7.3 Failure Demo (Deterministic)

$ ./mysh
mysh> not_a_command
mysh> echo $?
127

4. Solution Architecture

4.1 High-Level Design

[Input] -> [Parser/Lexer] -> [Core Engine] -> [Executor/Output]

4.2 Key Components

Component Responsibility Key Decisions
Context Detector Find fragment at cursor Respects quoting.
Candidate Finder Scan PATH or directory Prefix filtering.
Renderer Print matches and redraw line Column layout.

4.4 Data Structures (No Full Code)

struct Completion { char **candidates; size_t count; };

4.4 Algorithm Overview

Key Algorithm: LCP

  1. Compare candidates char-by-char

Complexity Analysis:

  • Time: O(n*m) for n candidates
  • Space: O(n*m) for n candidates

5. Implementation Guide

5.1 Development Environment Setup

# install dependencies (if any)
# build
make

5.2 Project Structure

project-root/
├── src/
│   ├── main.c
│   ├── lexer.c
│   └── executor.c
├── tests/
│   └── test_basic.sh
├── Makefile
└── README.md

5.3 The Core Question You’re Answering

How does a shell predict what the user wants to type next?

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. PATH lookup
  2. Directory traversal
  3. Terminal rendering

5.5 Questions to Guide Your Design

5.6 Thinking Exercise

The “Multiple Matches” Problem

Given matches git, gist, gimp, what should happen after one tab?

5.7 The Interview Questions They’ll Ask

5.8 Hints in Layers

Hint 1: Split on cursor position Determine the word fragment to complete.

Hint 2: Use PATH for command completion Scan each PATH directory for executables.

Hint 3: Use directory listing for file completion Filter by prefix and sort results.

Hint 4: Compute LCP If multiple matches, extend to longest common prefix.

5.9 Books That Will Help

Topic Book Chapter
Shell UX “Effective Shell” Ch. 7
PATH lookup “Advanced Programming in the UNIX Environment” Ch. 4
Completion UX GNU Readline Manual Completion section

5.10 Implementation Phases

Phase 1: Foundation (2-3 days)

Goals:

  • Define data structures and interfaces
  • Build a minimal end-to-end demo

Tasks:

  1. Implement the core data structures
  2. Build a tiny CLI or harness for manual tests

Checkpoint: A demo command runs end-to-end with clear logging.

Phase 2: Core Functionality (1 week)

Goals:

  • Implement full feature set
  • Validate with unit tests

Tasks:

  1. Implement core requirements
  2. Add error handling and edge cases

Checkpoint: All functional requirements pass basic tests.

Phase 3: Polish & Edge Cases (2-4 days)

Goals:

  • Harden for weird inputs
  • Improve UX and documentation

Tasks:

  1. Add edge-case tests
  2. Document design decisions

Checkpoint: Deterministic golden demo and clean error output.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Parsing depth Minimal vs full Incremental Start small, expand safely
Error policy Silent vs verbose Verbose Debuggability for learners

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Test individual components Tokenizer, matcher, env builder
Integration Tests Test component interactions Full command lines
Edge Case Tests Handle boundary conditions Empty input, bad args

6.2 Critical Test Cases

  1. Golden Path: Run the canonical demo and verify output.
  2. Failure Path: Provide invalid input and confirm error status.
  3. Stress Path: Run repeated commands to detect leaks or state corruption.

6.3 Test Data

input: echo hello
output: hello

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Misordered redirection Output goes to wrong place Apply redirections left-to-right
Leaked file descriptors Commands hang waiting for EOF Close unused fds in parent/child
Incorrect exit status &&/|| behave wrong Use waitpid macros correctly

7.2 Debugging Strategies

  • Trace syscalls: Use strace/dtruss to verify fork/exec/dup2 order.
  • Log state transitions: Print parser states and job table changes in debug mode.
  • Compare with dash: Run the same input in a reference shell.

7.3 Performance Traps

  • Avoid O(n^2) behavior in hot paths like line editing.
  • Minimize allocations inside the REPL loop.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a help built-in with usage docs.
  • Add colored prompt themes.

8.2 Intermediate Extensions

  • Add a simple profiling mode for command timing.
  • Implement a which built-in using PATH lookup.

8.3 Advanced Extensions

  • Add programmable completion or plugin system.
  • Add a scriptable test harness with golden outputs.

9. Real-World Connections

9.1 Industry Applications

  • Build systems: shells orchestrate compilation and test pipelines.
  • DevOps automation: scripts manage deployments and infrastructure.
  • bash: The most common interactive shell.
  • dash: Minimal POSIX shell often used as /bin/sh.
  • zsh: Feature-rich interactive shell.

9.3 Interview Relevance

  • Process creation and lifecycle questions.
  • Parsing and system programming design trade-offs.

10. Resources

10.1 Essential Reading

  • “Effective Shell” by Dave Kerr - focus on the chapters relevant to this project.
  • “Advanced Programming in the UNIX Environment” - process control and pipes.

10.2 Video Resources

  • Unix process model lectures (any OS course).
  • Compiler front-end videos for lexing/parsing projects.

10.3 Tools & Documentation

  • strace/dtruss: inspect syscalls.
  • man pages: fork, execve, waitpid, pipe, dup2.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain the core concept without notes.
  • I can trace a command through my subsystem.
  • I understand at least one key design trade-off.

11.2 Implementation

  • All functional requirements are met.
  • All critical tests pass.
  • Edge cases are handled cleanly.

11.3 Growth

  • I documented lessons learned.
  • I can explain this project in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Core feature works for the golden demo.
  • Errors are handled with non-zero status.
  • Code is readable and buildable.

Full Completion:

  • All functional requirements met.
  • Tests cover edge cases and failures.

Excellence (Going Above & Beyond):

  • Performance benchmarks and clear documentation.
  • Behavior compared against a reference shell.