GitHub open-sources Rust crate for high-speed case folding in code search

Optimizing Case Folding for Code Search

GitHub has released a new open-source Rust crate called `casefold`, designed to perform case folding operations at memory speed. This crate is a result of optimizations made for Blackbird, GitHub's code search engine, which indexes over 180 million repositories. Case folding is crucial for matching text where case distinctions should be ignored, such as in search queries, regular expressions, and identifiers like usernames or hostnames.

Distinguishing Case Folding from Lowercasing

The crate highlights the difference between case folding and lowercasing. Lowercasing is intended for display and is locale- and context-sensitive, while case folding is for comparison and is deliberately context-free and locale-independent. Using lowercasing for comparison can lead to incorrect matches due to variations in characters like 'ß', 'İ', or the Greek final sigma. The `casefold` crate implements simple (1-to-1) folds as defined in the Unicode Character Database's CaseFolding.txt, consistent with other tools like ripgrep.

Performance Improvements

A key optimization in the `casefold` crate involves a counterintuitive approach for ASCII text. Instead of stopping early at the first non-ASCII byte, the crate sweeps the entire buffer with no branches. This method was found to be faster for the predominantly ASCII source code processed by GitHub's search engine, significantly improving performance for a fundamental operation that is executed billions of times.