# How Zed's Command Palette Fuzzy Search Works: A Deep Dive into the Rust Implementation

> Explore Zed's command palette fuzzy search. Discover how its multi-threaded Rust implementation uses pre-filtering, dynamic programming, and scoring to quickly find your commands.

- Repository: [Zed Industries/zed](https://github.com/zed-industries/zed)
- Tags: deep-dive
- Published: 2026-03-01

---

**Zed's command palette uses a multi-threaded fuzzy matcher that pre-filters candidates by character bag, scores matches with a dynamic programming algorithm applying distance and case penalties, and returns top results in milliseconds even with thousands of commands.**

The Zed editor's command palette delivers instant fuzzy search results through a highly optimized Rust implementation in the `zed-industries/zed` repository. Its fuzzy search engine is built on the standalone **`fuzzy`** crate, which provides a parallelized matcher capable of handling large command sets without blocking the UI. This architecture separates the command gathering and query normalization logic from the heavy computational work of scoring matches across multiple CPU cores.

## Architecture Overview

The fuzzy search pipeline operates in five distinct phases orchestrated by the `CommandPaletteDelegate` in [`crates/command_palette/src/command_palette.rs`](https://github.com/zed-industries/zed/blob/main/crates/command_palette/src/command_palette.rs). When a user opens the palette with `cmd-shift-p`, the system first collects all available window actions, normalizes the user query, builds lightweight candidate objects, distributes the matching work across threads, and finally renders the scored results.

The heavy computation happens inside the `fuzzy` crate's `match_strings` function in [`crates/fuzzy/src/strings.rs`](https://github.com/zed-industries/zed/blob/main/crates/fuzzy/src/strings.rs). This function segments the candidate list across available CPU cores and delegates actual scoring to the `Matcher` struct in [`crates/fuzzy/src/matcher.rs`](https://github.com/zed-industries/zed/blob/main/crates/fuzzy/src/matcher.rs). The `Matcher` implements a recursive dynamic programming algorithm that calculates match quality based on character positions, case sensitivity, and path separator context.

## Collecting and Normalizing Input

The search process begins in `CommandPalette::toggle` (lines 99-114), which gathers every action available to the current window:

```rust
let commands = window
    .available_actions(cx)
    .into_iter()
    .filter_map(|action| {
        if filter.is_some_and(|f| f.is_hidden(&*action)) {
            None
        } else {
            Some(Command {
                name: humanize_action_name(action.name()),
                action,
            })
        }
    })
    .collect();

```

Once the user types a query, `update_matches` (lines 44-61) normalizes the input through `normalize_action_query`. This function trims whitespace and collapses double colons, making the search tolerant of formatting variations in command names.

## Candidate Preparation with StringMatchCandidate

Before fuzzy matching begins, each command is converted into a **`StringMatchCandidate`** (lines 62-70). This lightweight struct pre-computes a **`CharBag`**—a bit-set representation of the candidate's characters used for rapid pre-filtering:

```rust
let candidates = commands
    .iter()
    .enumerate()
    .map(|(ix, command)| StringMatchCandidate::new(ix, &command.name))
    .collect::<Vec<_>>();

```

The `StringMatchCandidate` implements the `MatchCandidate` trait, exposing `has_chars` for O(1) superset tests. This allows the matcher to instantly discard candidates that cannot possibly contain all query characters before running the expensive scoring algorithm.

## Parallel Fuzzy Matching Engine

The core matching logic resides in `fuzzy::match_strings` (lines 462-474), which executes the search across CPU cores asynchronously:

```rust
let matches = fuzzy::match_strings(
    &candidates,
    &query,
    true,                 // smart_case
    true,                 // penalize_length
    10_000,               // max_results
    &Default::default(),
    executor,
).await;

```

### Work Distribution Across CPU Cores

The `match_strings` function (lines 51-66 in [`strings.rs`](https://github.com/zed-industries/zed/blob/main/strings.rs)) calculates the optimal segment size by dividing the candidate count by the number of available CPUs:

```rust
let num_cpus = executor.num_cpus().min(candidates.len());
let segment_size = candidates.len().div_ceil(num_cpus);
for (segment_idx, results) in segment_results.iter_mut().enumerate() {
    // spawn per-segment task on BackgroundExecutor
}

```

Each segment runs in its own async task on the UI's `BackgroundExecutor`, allowing the matcher to saturate all cores without blocking the main thread.

### The Matcher Algorithm and Scoring Logic

Every segment task instantiates a **`Matcher`** (lines 63-70) with both the original and lowercased query, plus the query's `CharBag`:

```rust
let mut matcher = Matcher::new(
    query,
    lowercase_query,
    query_char_bag,
    smart_case,
    penalize_length,
);

```

The `Matcher::match_candidates` method performs a three-phase evaluation on each candidate:

1. **Pre-filtering**: Validates that the candidate's `CharBag` contains all query characters via `has_chars`.
2. **Position verification**: Calls `find_last_positions` to confirm every query character appears in order.
3. **Recursive scoring**: Builds dynamic programming matrices (`score_matrix`, `best_position_matrix`) and evaluates matches via `recursive_score_match` (lines 95-138 and 240-327).

The scoring algorithm applies several penalties and bonuses:
- **Base distance penalty**: `0.6` for gaps between matched characters
- **Additional distance penalty**: `0.05` per extra character of gap distance  
- **Smart-case penalty**: `*0.001` multiplier when case differs (if `smart_case` is enabled)
- **Length penalty**: Division by remaining path length for first-character matches when `penalize_length` is true
- **Contextual bonuses**: Higher scores for matches following separators (`/`, `-`, `_`, space) or capital-to-lowercase transitions

The recursion memoizes scores to prevent exponential blow-up, returning a final floating-point score multiplied by `query.len()` to prioritize longer contiguous matches.

## Rendering Results in the UI

After all segments complete, `match_strings` concatenates the results vectors, truncates to `max_results` while preserving highest scores, and returns a sorted `Vec<StringMatch>`. The `CommandPaletteDelegate::matches_updated` method (lines 300-330) receives these matches, storing the `StringMatch.positions` vector which `HighlightedLabel` uses to colorize matching characters in the UI.

## Code Example: Using the Fuzzy Matcher Directly

Developers can leverage the same API outside the command palette for custom fuzzy search implementations:

```rust
use fuzzy::{StringMatchCandidate, match_strings};
use gpui::BackgroundExecutor;
use std::sync::atomic::AtomicBool;

// Prepare candidates
let candidates = vec![
    StringMatchCandidate::new(0, "Open File"),
    StringMatchCandidate::new(1, "Close Buffer"),
    StringMatchCandidate::new(2, "Toggle Sidebar"),
];

let query = "op fl";
let cancel = AtomicBool::new(false);
let executor = BackgroundExecutor::new();

// Run async matcher
let matches = smol::block_on(match_strings(
    &candidates,
    query,
    true,          // smart_case
    true,          // penalize_length
    10,            // max_results
    &cancel,
    executor,
));

if let Some(best) = matches.first() {
    println!("Best match: {}", best.string); // → "Open File"
}

```

This identical API powers the command palette's internal implementation (see [`command_palette.rs`](https://github.com/zed-industries/zed/blob/main/command_palette.rs) lines 462-474).

## Summary

- **Zed's command palette** gathers available actions and normalizes user queries before initiating the fuzzy search.
- **`StringMatchCandidate`** objects with pre-computed `CharBag` bit-sets enable O(1) pre-filtering of impossible matches.
- **`match_strings`** parallelizes work across all CPU cores by segmenting candidates and spawning tasks on a `BackgroundExecutor`.
- The **`Matcher`** uses dynamic programming with recursive memoization to calculate scores based on character proximity, case sensitivity, and separator context.
- The system handles thousands of commands with sub-millisecond latency by combining pre-filtering, parallelization, and algorithmic optimization.

## Frequently Asked Questions

### What algorithm does Zed use for fuzzy matching?

Zed implements a **dynamic programming-based fuzzy matcher** with recursive memoization. The algorithm in [`crates/fuzzy/src/matcher.rs`](https://github.com/zed-industries/zed/blob/main/crates/fuzzy/src/matcher.rs) builds score and position matrices to evaluate every possible character alignment, applying penalties for character gaps and bonuses for matches after separators or camelCase transitions.

### How does Zed make fuzzy search so fast with thousands of commands?

The fuzzy matcher achieves speed through three optimizations: **`CharBag` pre-filtering** instantly eliminates candidates missing query characters; **parallel segmentation** distributes work across all CPU cores; and **early truncation** limits results to the top N scores before returning to the UI. This architecture prevents exponential scoring work on irrelevant candidates.

### What is "smart case" in Zed's fuzzy search?

**Smart case** is a scoring mode (enabled by default) that applies a `0.001` penalty multiplier when a query character matches a candidate character with differing case. If the query contains uppercase letters, the matcher becomes case-sensitive; if all lowercase, it matches case-insensitively but penalizes case mismatches slightly, prioritizing exact case matches without requiring strict case adherence.

### Can I use Zed's fuzzy matcher in my own Rust project?

Yes. The `fuzzy` crate is designed as a standalone library within the Zed repository. You can import `fuzzy::{match_strings, StringMatchCandidate}` and call `match_strings` with your own candidate strings, query, and concurrency configuration. The API requires a `gpui::BackgroundExecutor` for async execution and returns scored matches with character position data for highlighting.