Regex and search

Purpose

Two regex engines coexist in src/nvim/regexp.c — the legacy NFA-based "Vim regex" and the older backtracker. Both implement Vim's regex dialect (which is similar to but not identical to PCRE: \v, \<word\>, \zs, \ze, look-behind, etc.). The runtime picks one via the 'regexpengine' option ('re'); most of the editor's substring searching, completion, and :substitute go through this layer.

Directory layout

src/nvim/
├── regexp.c (~456k bytes / 16,309 lines)   Both engines, fold-aware matching
├── regexp.h, regexp_defs.h
├── search.c (~118k bytes)                   :/ ?, * , #, n, N
├── search.h
├── fuzzy.c (~29k bytes)                     fuzzy matching for cmdline/wildmenu
├── fuzzy.h
└── api/private/.../                         (API regex helpers)

regexp.c is the largest single source file in the repository. Its size is owed to: two complete regex engines (NFA and backtracker), Vim-specific extensions (\<, \>, \zs, \ze, atom classes), multibyte handling, and the substitute-replacement parser.

Key abstractions

Type / function	File	Description
regprog_T	regexp_defs.h	A compiled regex. Tagged with the engine.
regmatch_T	regexp_defs.h	A match result: prog + start positions + multi-line offsets.
regmmatch_T	regexp_defs.h	Multi-line variant.
vim_regcomp	regexp.c	Compile a pattern into a regprog_T. Picks an engine based on 're'.
vim_regexec / vim_regexec_multi	regexp.c	Execute a compiled regex against a string or buffer range.
searchit	search.c	The workhorse for / and ? — incremental search with options.
do_sub	ex_cmds.c	:substitute. Calls into vim_regexec_multi.

The two engines

Both engines compile the user's pattern to an internal program form and run it against input. They diverge in how they execute:

Backtracking engine (legacy)

regexp_bt.c is concatenated into regexp.c at compile time. It is the original Vim engine: a recursive descent that tries each alternative in order. It supports every Vim feature including back-references and look-behind, but suffers catastrophic backtracking on adversarial patterns.

NFA engine

regexp_nfa.c is also #included into regexp.c. It compiles to an NFA and runs Thompson-style — every state is advanced in lockstep, so worst-case complexity is O(n × m) for input length n and pattern length m. The NFA engine handles most but not all Vim features; for unsupported features the compile falls back to the backtracker.

The user picks via :set regexpengine=:

• 0 (default) — try NFA, fall back to backtracker on compile failure.
• 1 — backtracker only.
• 2 — NFA only.

Search

src/nvim/search.c implements the user-facing search commands:

• /pattern and ?pattern (forward/backward, normal-mode n and N).
• * and # (search for word under cursor).
• gd, gD (local/global declaration jump).
• [i, ]i, etc. (include-file search — uses the 'include' option).
• searchpos(), search(), searchpair() — Vimscript and Lua surfaces.

The hot loop is searchit(). It walks the buffer line by line (ml_get), runs vim_regexec_multi against each line, and tracks position. Highlighting of matches ('hlsearch') is wired through the same compiled regex but as a match_T per window.

Smart case ('smartcase'), 'magic'/'nomagic', 'ignorecase', and the \c/\C flags interact in non-obvious ways. Read the pat_has_* helpers near the top of search.c if you're tracing a "case-sensitivity is wrong" bug.

Fuzzy matching

src/nvim/fuzzy.c implements the fuzzy match used by:

• The wildmenu ('wildoptions=fuzzy').
• :lua autocomplete.
• vim.fn.matchfuzzy and matchfuzzypos.
• Some Lua plugins via vim.fn.matchfuzzy().

It is a small Smith-Waterman variant tuned for short patterns. The scoring rewards initials, consecutive matches, and word boundaries. The implementation is straightforward; the match function is called once per candidate and produces a (score, positions[]) pair.

Substitute

:substitute/old/new/flags is implemented in src/nvim/ex_cmds.c#ex_substitute. The flow:

1. Parse the delimiter, the pattern, the replacement, and the flags.
2. Compile the pattern via vim_regcomp.
3. Walk lines in the range; on each line, repeatedly call vim_regexec_multi.
4. For each match, parse the replacement (\0, \1, &, \=expr, \,r/\,l, etc.).
5. Build the new line via regtilde() and vim_regsub().
6. Apply via ml_replace (with u_save first).
7. With c flag: prompt; with g flag: continue past the first match per line.

The \=expr form runs an arbitrary Vimscript expression for the replacement, which is what makes :s/foo/\=submatch(0).get_count()/g work. That path goes through eval in src/nvim/eval/.

Integration points

• Vimscript — match(), search(), searchpos(), searchpair(), =~, =~#, =~? operators in src/nvim/eval.c.
• Lua — vim.regex(pattern) returns a wrapper. The compile and exec are the same C code; only the binding differs.
• Treesitter queries — not this engine. Tree-sitter has its own pattern language, with C bindings in src/nvim/lua/treesitter.c.
• Syntax — old-style :syntax match and :syntax region use this engine for their patterns.
• Subsitute on a yank — :s works on getreg() content because vim_regexec operates on strings, not just buffers.

Entry points for modification

• Bug in match behavior. Step into vim_regexec_multi, then dispatch to either regexp_bt.c (backtracker) or regexp_nfa.c (NFA) inside the same translation unit. Both have extensive comments at the top.
• New regex feature. Almost always means adding a parser case in both engines — that, plus updating the test corpus in test/old/testdir/test_regexp_* and test/functional/.
• New search command. Most live in search.c. The pattern is parse-flags + call searchit with the right options.
• Replacement syntax. regtilde and vim_regsub in regexp.c.

Key source files

File	Purpose
src/nvim/regexp.c	Both engines, compile + exec, replacement substitution
src/nvim/regexp_defs.h	regprog_T, regmatch_T, related types
src/nvim/search.c	/, ?, n, N, *, #, searchpair, searchpos
src/nvim/fuzzy.c	Fuzzy matching for cmdline and wildmenu
src/nvim/ex_cmds.c#ex_substitute	:substitute
runtime/doc/pattern.txt	User-facing pattern reference