Skip to content

README.md

Latest commit

 

History

History
163 lines (119 loc) · 4.7 KB

README.md

File metadata and controls

163 lines (119 loc) · 4.7 KB

shell

A POSIX-compliant Unix shell written from scratch in C++, built alongside the CodeCrafters "Build Your Own Shell" automated test suite. Implements a full compiler-style frontend — hand-written lexer, recursive descent parser, and AST executor — with pipe chaining, I/O redirection, and GNU Readline tab autocompletion.

Architecture

stdin (readline)
     │
     ▼
  Lexer (tokenize)
     │  ParseResult { tokens[], ParseState }
     ▼
  Parser (recursive descent)
     │  std::unique_ptr<ASTNode>
     ▼
  AST Executor
     ├─ Builtins  → dup/dup2 save-restore in parent
     ├─ External  → fork / execv / waitpid
     └─ Pipeline  → pipe() + fork all stages + waitpid all

Components

Lexer (lexer.cpp)

Single-pass character scanner implementing POSIX quoting rules precisely:

  • Single quotes: all characters literal, no escape processing
  • Double quotes: only ", \, $, `, \n are escapable after a backslash — everything else the backslash passes through literally (POSIX spec)
  • Backslash outside quotes: escapes the next character unconditionally
  • Redirect operators: >, >>, 1>, 2>, 1>>, 2>> recognized as atomic tokens; 1 and 2 merge with a following >/>> in-place
  • Pipe operator: | emitted as its own token

Returns a ParseResult with a ParseState enum:

enum class ParseState {
  COMPLETE,
  NEED_SINGLE_QUOTE,
  NEED_DOUBLE_QUOTE,
  NEED_ESCAPE
};

This drives multi-line continuation in main.cpp — unclosed quotes or escapes prompt > and re-tokenize until COMPLETE.

Parser (parser.cpp)

Recursive descent parser with explicit precedence levels for future extension:

parse()
  └─ parse_list()          // &&, || (logical operators)
       └─ parse_pipeline() // | (pipe chains)
            └─ parse_command()

parse_command() builds a SimpleCommandNode consuming:

Token Effect
> / 1> stdout redirect, truncate
>> / 1>> stdout redirect, append
2> stderr redirect, truncate
2>> stderr redirect, append
< stdin redirect

parse_pipeline() builds a PipelineNode by collecting SimpleCommandNodes separated by |.

All nodes owned by std::unique_ptr<ASTNode> — no manual memory management.

AST / Executor (ast.cpp)

Builtin commands

Run in the parent process. Redirection uses dup/dup2 with explicit save-and-restore so the shell's own file descriptors are not permanently modified:

saved_fd = dup(target_fd)      // save original
dup2(new_fd, target_fd)        // redirect
execute_builtin(args)          // run in parent
dup2(saved_fd, target_fd)      // restore
close(saved_fd)

External commands

Standard POSIX process model:

  1. fork() — child inherits file descriptors
  2. Child sets up redirection via dup2, calls execv() with null-terminated char**
  3. Child uses _exit() on failure (not exit()) to avoid flushing parent stdio buffers
  4. Parent waitpid() + WEXITSTATUS() for exit code

Exit codes: 127 command not found, 126 execv failure.

Pipe chains (cmd1 | cmd2 | cmd3)

All stages forked concurrently. For N commands, N-1 pipe() pairs are created upfront. Each child:

  • Closes the read end of its write-side pipe
  • Closes the write end of its read-side pipe
  • dup2s pipe ends onto stdin/stdout
  • Calls execv

Parent closes all pipe ends and waitpids all children, collecting the last stage's exit code.

Autocompletion (completion.cpp)

Tab completion registered via GNU Readline's rl_completion_entry_function. init_completion() sets up the callback at startup.

REPL (main.cpp)

readline("$ ")
  → tokenize()
  → while state != COMPLETE: prompt "> ", append input, re-tokenize
  → Parser::parse() → unique_ptr<ASTNode>
  → ASTNode::execute()

std::unitbuf on cout/cerr ensures unbuffered output for correct interleaving with Readline.

Building

Requires: cmake, readline, vcpkg

cmake -B build
cmake --build build
./your_program.sh

Features

Feature Status
POSIX quoting (single, double, backslash) ✅
Stdout redirect (>, >>, 1>, 1>>) ✅
Stderr redirect (2>, 2>>) ✅
Stdin redirect (<) ✅
Pipe chaining (|) ✅
Builtin commands (cd, pwd, echo, type, exit) ✅
External command execution (fork/execv) ✅
Tab autocompletion (GNU Readline) ✅
Multi-line input continuation ✅
Logical operators (&&, ||) 🚧 Planned

Validated against the CodeCrafters automated test suite.