globset

Active contributors: Andrew Gallant

Purpose

crates/globset is a high-performance glob matcher. It supports both single-glob matching and the more interesting glob-set matching: testing a single path against many globs simultaneously, returning all that match. The set form is what makes ripgrep's .gitignore parsing fast even on node_modules-sized rule sets.

The crate is independent of the rest of the workspace. Cargo and several other Rust projects depend on globset directly.

Directory layout

crates/globset/src/
├── lib.rs           # Public API: Glob, GlobSet, GlobBuilder, GlobSetBuilder, Candidate, GlobMatcher (~36K)
├── glob.rs          # Glob compiler: parse glob → AST → regex → matcher (~60K, the largest file in the crate)
├── pathutil.rs      # Path normalisation helpers
├── fnv.rs           # The FNV-1a hash used to bucket glob candidates by basename / extension
└── serde_impl.rs    # serde Serialize/Deserialize for Glob (gated behind the `serde` feature)

Key abstractions

Type	File	Description
Glob	crates/globset/src/glob.rs	A parsed (but not compiled) single glob. Built via Glob::new(pattern).
GlobBuilder	crates/globset/src/glob.rs	Configures match semantics for a single glob: case_insensitive, literal_separator, backslash_escape, empty_alternates.
GlobMatcher	crates/globset/src/glob.rs	A compiled, ready-to-match single glob. Returned from Glob::compile_matcher.
GlobSet	crates/globset/src/lib.rs	A set of globs that match in parallel. GlobSet::matches(path) returns the indices of all matching globs.
GlobSetBuilder	crates/globset/src/lib.rs	Builder for a GlobSet. Add Globs, then call build.
Candidate	crates/globset/src/lib.rs	A path pre-processed for matching: normalised, with cached basename and extension. Reuse across many matches calls amortises path-parsing cost.
Error / ErrorKind	crates/globset/src/lib.rs	Parse / compile errors.

Glob syntax

Standard Unix glob syntax with extensions:

• ? — any single character (not / if literal_separator is enabled).
• * — zero or more characters (not / if literal_separator is enabled).
• ** — recursive directory wildcard, only legal in three positions: leading **/, trailing /**, or middle /**/.
• [...] — character class, supports negation [!...].
• {a,b,c} — alternation.
• Nested braces (added in 15.0.0): {a,b{c,d}} works.
• ! at the start of a pattern is not negation in this crate. (The ignore crate handles negation when reading .gitignore files.)

The full grammar is in the crate-level docs in lib.rs.

How a GlobSet works

GlobSet::matches does not iterate every glob. It uses three indexing strategies derived from the patterns at build time:

graph TD
    Path[Candidate path] --> Bucket{decompose}
    Bucket --> ExtIndex["extension index<br/>{*.rs} → bucket by 'rs'"]
    Bucket --> BaseIndex["basename literal index<br/>{Cargo.toml} → bucket by 'Cargo.toml'"]
    Bucket --> RegexIndex["everything else<br/>compiled into a single RegexSet"]
    ExtIndex --> Match[matched globs]
    BaseIndex --> Match
    RegexIndex --> Match

Concretely, the build-time pipeline:

1. Each Glob is parsed into a small AST (Tokens).
2. The compiler classifies each glob into one of:
   • Extension-only (*.rs): goes into a hash map keyed by extension.
   • Basename literal (Cargo.toml, *.tar.gz): goes into a hash map keyed by basename or basename suffix.
   • General: compiled into the regex crate's RegexSet for parallel evaluation.
3. At match time, Candidate provides the basename and extension, the matcher does O(1) hash lookups in the first two indexes, then runs the RegexSet for whatever remains.

This is what allows .gitignore rule sets with thousands of rules to be matched at speed — the vast majority of rules are extension-only and never enter the regex engine.

Single-glob matching

For one-off cases, Glob::new(pattern)?.compile_matcher().is_match(path) is enough. The matcher is just the regex form, no hashing optimisations.

Integration points

• Used by: ignore (every Gitignore and Override is a GlobSet); crates/cli (DecompressionMatcher uses GlobSet for extension lookup); crates/core/flags/hiargs.rs for the --pre-glob flag.
• Depends on: regex-automata, regex-syntax, bstr, aho-corasick, log, optional serde.
• Re-exported by: nothing in the workspace — it is consumed directly.

Notable bug history

The 15.0.0 release fixed:

• BUG #2990: globs ending with . were mishandled.
• FEATURE #3048: nested alternates ({a,b{c,d}}) were added.

Glob compilation, like regex literal extraction, has subtle correctness pitfalls. Tests in crates/globset/src/glob.rs (in-file unit tests) and crates/globset/src/lib.rs cover a wide grid of patterns.

Entry points for modification

• New glob syntax: edit crates/globset/src/glob.rs (the parser and the AST → regex translator).
• New GlobSet strategy: changes go in crates/globset/src/lib.rs. Note that the three-strategy split above is performance-critical; benchmark before changing.
• New GlobBuilder option: a method in glob.rs that toggles a Config field, then thread it through the regex synthesis.