GeezerVison

# Code Search

Code Search is a high-performance tool for indexing and searching large bodies of source code using regular expressions backed by an n-gram (trigram) index.

Originally authored by Russ Cox for searching multi-gigabyte codebases, Code Search decomposes regular expressions into boolean queries over trigram posting lists. This enables instantaneous candidate file identification, reducing search time over hundreds of thousands of files to milliseconds.

For architectural and algorithmic background, see [Regular Expression Search with Trigrams](https://swtch.com/~rsc/regexp/regexp4.html).

## Quick start

With Go 1.23 or later, from this checkout:

```bash
go install ./cmd/codesearch
codesearch index -git .
codesearch status -git
codesearch search -git --line-number 'func main'
codesearch search -git --fixed-strings 'http.HandleFunc('
```

Run these commands from the repository you want to search after installation.
Set `"git": true` in your configuration to omit `-git` on later commands.
`make build` also provides the short alias at `bin/cs`; `go install` installs
only `codesearch`. Put the installation directory on your `PATH`.

Use `--help` for command help. Flags precede the pattern and paths; combined
short flags remain unsupported (`-i -n`, not `-in`). To search for a command
name, use `codesearch search index`; for patterns beginning with a dash, use
`codesearch search -- '-pattern'`.

`--index /path/to/index` selects an index for one invocation and overrides both
`CSEARCHINDEX` and configuration. `codesearch status` reports the selected
index, selection source, roots, modification time, and size statistics. It does
not verify freshness: refresh existing roots with `codesearch index` after
source files change.

---

## How It Works

1. **Trigram Indexing (`index/`)**:
   - Files are parsed into overlapping 3-byte sequences (trigrams). With 256 possible bytes, there are $2^{24}$ (16,777,216) possible trigrams.
   - For each trigram, the index stores a compressed posting list recording every file ID that contains that trigram.
   - File IDs in posting lists are Elias $\gamma$-encoded and chunked into 256-byte blocks on disk for rapid seek and decode performance.
   - Binary files (containing NUL bytes) and non-text files are automatically excluded.

2. **Query Planning & Search (`regexp/`, `cmd/codesearch/search.go`)**:
   - The user's regular expression is parsed into an abstract syntax tree using the RE2 syntax.
   - The query planner extracts required trigrams from the syntax tree to build a boolean query tree ($\text{AND}$, $\text{OR}$, or $\text{ALL}$). For example, `func.*main` requires both `"fun"` and `"mai"`.
   - The posting lists for those trigrams are intersected to find the small subset of files guaranteed to contain all required trigrams.
   - Finally, Code Search runs an exact regular expression search only on matching candidate files.

3. **Fast Line Counting & Context Extraction**:
   - Matches are extracted with byte offsets and line numbers.
   - Pre- and post-match context (`-A`, `-B`, `-C`) can be extracted with common prefix indentation preserved.

---

## Building & Installation

### Standard Build (Go 1.23+)

Build all binaries into `bin/` using `make`:

```bash
make build
```

This compiles:
- `bin/codesearch` (unified CLI)
- `bin/cs` (symlink to `codesearch`)
- `bin/cindex` (legacy index wrapper)
- `bin/csearch` (legacy search wrapper)
- `bin/cgrep` (legacy grep wrapper)
- `bin/csweb` (legacy web UI wrapper)

Run the test suite:

```bash
make test
```

Run tests and static analysis together with `make check`; use `make check-simd`
for the experimental SIMD build.

Clean build artifacts:

```bash
make clean
```

To install `codesearch` directly into your `$GOPATH/bin` or `$GOBIN`:

```bash
go install ./cmd/codesearch
```

---

## SIMD Optimizations (`GOEXPERIMENT=simd`)

Code Search includes vectorized SIMD optimizations targeting modern 64-bit architectures (ARM64 NEON and AMD64 AVX2) using Go's experimental SIMD intrinsics package (`simd/archsimd`).

### What SIMD Accelerates

1. **Vectorized Newline Counting (`regexp/nl_simd.go`)**:
   - Scans 16-byte vectors per iteration to count `\n` delimiters during match line number calculation and context extraction.
   - Batches vector comparisons in chunks of up to 250 iterations (4,000 bytes) into 16-lane `Uint8x16` accumulators without integer overflow or memory allocations.
   - Outperforms scalar loops by up to $4\times$ on large files.

2. **SIMD File Ingestion & ASCII Scanning (`index/scan_simd.go`)**:
   - Evaluates 16 bytes per vector operation to detect NUL bytes (for instant binary file filtering) and checks high bits (`0x80`) to identify pure ASCII chunks.
   - Files with pure ASCII chunks bypass multibyte UTF-8 validation and stream directly into trigram extraction.

3. **Pure Go Fallback (`regexp/nl_purego.go`, `index/scan_purego.go`)**:
   - When built without `GOEXPERIMENT=simd`, Go build tags (`!goexperiment.simd`) automatically select pure Go implementations, ensuring seamless builds across all supported Go platforms and architectures.

### Building with SIMD

To build Code Search with SIMD intrinsics enabled:

```bash
# Using Makefile
make build-simd

# Or using go build directly
GOEXPERIMENT=simd go build -o bin/codesearch ./cmd/codesearch
```

### Testing with SIMD

Run the test suite with SIMD enabled:

```bash
# Using Makefile
make test-simd

# Or using go test directly
GOEXPERIMENT=simd go test -v ./...
```

### Benchmarks

Run benchmarks comparing scalar and SIMD routines:

```bash
# Benchmark newline counting
go test -bench=BenchmarkCountNL ./regexp
GOEXPERIMENT=simd go test -bench=BenchmarkCountNL ./regexp

# Benchmark ASCII scanning & ingestion
go test -bench=BenchmarkScanASCIIChunk ./index
GOEXPERIMENT=simd go test -bench=BenchmarkScanASCIIChunk ./index
```

---

## CLI Usage

`codesearch` (or short alias `cs`) provides a single unified interface with subcommands.

### 1. Indexing (`codesearch index`)

Before searching, create an index of the source code tree:

```bash
# Build an initial index over one or more directories
codesearch index /path/to/repo /path/to/another/repo

# Reindex all previously indexed roots
codesearch index

# Discard existing index and build a fresh one
codesearch index -reset /path/to/repo

# List currently indexed directory roots
codesearch index -list

# View index size statistics (or use 'codesearch index stats')
codesearch index -stats

# Validate the index without rebuilding it
codesearch index check
```

`index stats`, `index check`, and `index list` are read-only and accept no paths.
The flag forms `-stats` and `-check` are also read-only when no paths are given.
With explicit paths, the flags report or validate the resulting update.
Use `codesearch index ./stats` to index a directory named `stats`.

Updates build and validate a staging index before replacement and reject
concurrent writers using `<index>.lock`. After a forcibly terminated process,
remove a leftover lock only after verifying no writer is still running.
Input failures abort the update and preserve the previous index.

**Index Flags:**
- `-reset`: Replace the index with the supplied roots; without paths, remove it.
- `-list`: List indexed directory roots and exit without re-indexing.
- `-stats`: Print index size statistics (path list, name list, posting lists, name index, posting index).
- `-zip`: Index the contents of `.zip` files.
- `-check`: Verify that the existing index format and postings are well-formed.
- `-verbose`: Print progress details during indexing.
- `-cpuprofile <file>`: Write CPU profile to the specified file.

### 2. Searching (`codesearch search` or `codesearch <regexp>`)

Search indexed code using regular expressions. If no subcommand is specified, `codesearch` defaults to `search`:

```bash
# Search using explicit subcommand
codesearch search 'func main\('

# Default search fallback (omit 'search')
codesearch 'func main\('

# Case-insensitive search
codesearch search -i 'parse.*config'
codesearch -i 'parse.*config'

# Filter matches by file path regular expression
codesearch -f '\.go$' 'type [A-Z]'

# Show line numbers
codesearch -n 'TODO'

# List matching files only
codesearch -l 'panic\('

# Print match counts per file
codesearch -c 'deprecated'

# Print context lines around matches
codesearch -C 2 'HandleRequest'     # 2 lines before and after
codesearch -B 1 -A 3 'NewServer'    # 1 line before, 3 lines after

# Output formatted HTML links
codesearch -html 'ErrNotFound'

# Brute-force search (search every file in the index, bypassing trigrams)
codesearch -brute 'regexp'
```

**Search Flags:**
- `-F`, `--fixed-strings`: Treat the pattern as a literal string.
- `-i`: Case-insensitive search.
- `-f <regexp>`: Limit search to files whose path matches `<regexp>`.
- `-n`: Prefix each matching line with its line number.
- `-l`: List file paths only (stop scanning after the first match in each file).
- `-c`: Print count of matching lines per file instead of line contents.
- `-A <n>`: Print `<n>` lines of trailing context after each match.
- `-B <n>`: Print `<n>` lines of leading context before each match.
- `-C <n>`: Print `<n>` lines of context before and after each match.
- `-h`: Suppress file path prefix in output.
- `-html`: Format matches with clickable HTML links for the web viewer.
- `-brute`: Brute-force scan across all indexed files.
- `-verbose`: Print query planning and candidate file count details.

Search and grep also accept `--ignore-case`, `--line-number`,
`--files-with-matches`, `--count`, `--no-filename`, `--context`,
`--before-context`, and `--after-context`. Search accepts `--path-regexp`;
grep accepts `--invert-match`. These aliases have the same configuration
precedence as their short forms. Exit status is 0 for selected lines, 1 for
no selected lines, and 2 for input failures, even when other files matched.

### 3. Direct Grep (`codesearch grep`)

Search files or standard input directly with regular expressions without needing or using an index:

```bash
# Search specific files
codesearch grep 'pattern' main.go utils.go

# Case-insensitive search with line numbers
codesearch grep -i -n 'error' server.go

# Invert match (print non-matching lines)
codesearch grep -v 'debug' log.txt

# Print context around matches
codesearch grep -C 2 'critical' error.log

# Search from standard input
cat log.txt | codesearch grep 'FATAL'
codesearch grep 'pattern' - < input.txt
```

### 4. Web UI (`codesearch web`)

Start a local search web server with interactive results and file browsing:

```bash
# Start on default address (http://localhost:2473)
codesearch web

# Start on custom address
codesearch web -addr localhost:8080
codesearch web -http :3000
```

Features:
- Instant query evaluation against the local trigram index.
- Search result linking directly into source file views with line numbers and anchors (`#L123`).
- Syntax-highlighted code inspection supporting both Unix (`\n`) and Windows CRLF (`\r\n`) line endings.
- Breadcrumb navigation across repository directories.

### 5. Help & Version

```bash
codesearch version
codesearch help
codesearch help index
codesearch help search
codesearch help grep
codesearch help web
```

---

## Configuration

`codesearch` reads defaults from a single per-user JSON file:

```
$XDG_CONFIG_HOME/codesearch/config.json
$HOME/.config/codesearch/config.json      # when XDG_CONFIG_HOME is unset
```

The file is optional. Every key is optional too, and each corresponds to the
flag of the same name; a key you omit keeps the flag's built-in default, and a
flag you pass on the command line always wins over the file.

```json
{
  "git": true,
  "index": "",
  "n": true,
  "i": false,
  "l": false,
  "c": false,
  "h": false,
  "A": 0,
  "B": 0,
  "C": 0,
  "f": ""
}
```

- **`git`**: keep the index at the root of the enclosing git repository
  (see below). Also available per-run as `-git` / `-git=false`.
- **`index`**: use this index file instead of `$HOME/.csearchindex`.
- The rest are search and grep flag defaults. `C` sets both sides of the match
  context, so an explicit `A` or `B` in the file overrides its side.

A malformed file or an unrecognized key is reported as an error rather than
ignored, so typos do not silently do nothing.

### Repository-level indexes (`git`)

With `git` enabled, `codesearch` walks up from the working directory looking for
a `.git` entry — a directory in an ordinary clone, a file in a worktree or
submodule — and uses `<repo root>/.csearchindex`. Each repository then gets its
own index, and `index`, `search`, and `web` all agree on which one to use from
anywhere inside the tree. Outside any repository, the usual
`$HOME/.csearchindex` applies. Add `.csearchindex` to your `.gitignore` (or
`$HOME/.config/git/ignore`).

With `git` disabled — the default — nothing is searched for on disk and
behavior is unchanged.

The index file is resolved in this order:

1. `$CSEARCHINDEX`
2. `index` from the config file
3. `<git repo root>/.csearchindex`, when `git` is enabled and a repository is found
4. `$HOME/.csearchindex`

An explicit `--index` flag takes precedence over all four sources.

## Environment Variables

- **`CSEARCHINDEX`**: Path to the index file. Overrides the config file.
  Defaults to `$HOME/.csearchindex` if unset.
- **`XDG_CONFIG_HOME`**: Base directory for the config file described above.

---

## Legacy Tool Compatibility

For backward compatibility with existing workflows and scripts, standalone command binaries remain supported and compile alongside `codesearch`:

- `cindex` $\rightarrow$ `codesearch index`
- `csearch` $\rightarrow$ `codesearch search`
- `cgrep` $\rightarrow$ `codesearch grep`
- `csweb` $\rightarrow$ `codesearch web`
- `cs` $\rightarrow$ alias symlink to `codesearch`

---

## License

Code Search is distributed under a BSD-style license. See the `LICENSE` file for details.