Case-insensitive search without allocating

Two small functions over a slice of strings, both case-insensitive, both expected to allocate essentially nothing.

pub fn find_all_ci(haystack: &[String], needle: &str) -> Vec<usize>
pub fn any_contains_ci(haystack: &[String], needle: &str) -> bool

• find_all_ci returns the indices of the entries that equal the needle, ignoring ASCII case. Order ascending.
• any_contains_ci returns whether any entry contains the needle as a substring, ignoring ASCII case. The empty string is a substring of every string, so ["ab"] with needle "" is true. An empty haystack with a non-empty needle is false — there is nothing there to contain it.

The hidden case runs both over a 200 000-string haystack and asserts find_all_ci performs at most 2 heap allocations and any_contains_ci performs zero.

The whole lesson in one number

The obvious way to compare two strings without caring about case is to lowercase both and use ==. It is correct. It also allocates a fresh String for every comparison, and to_lowercase has to walk the input applying Unicode case-folding tables.

Measured over the same workload:

s.to_lowercase() == n.to_lowercase()     2.4550 ms
s.eq_ignore_ascii_case(n)                0.0755 ms      <-- 32.5x

and the fast one allocates nothing, because it compares byte by byte in place. That is the same shape as the needless-clone lesson: the cost is not the comparison, it is the temporary you built in order to do the comparison.

Separately, for substring search: s.chars().collect::<String>().contains(n) takes 3.49 ms where s.contains(n) takes 0.331 ms — 10.6×. Collecting a string into a string to search it is a real thing people write.

But read the small print, because 32× is not free

eq_ignore_ascii_case does exactly what it says: it folds A–Z against a–z and nothing else. Ä and ä are different strings to it. İ is different from i̇. If your data is international text and you use it for a user-facing “same name?” check, you have not optimised anything — you have introduced a correctness bug that will be reported as “search doesn’t work in Turkish”.

So the rule is not “always use the ASCII one”. The rule is: know which question you are asking. Protocol tokens, file extensions, HTTP header names, hex digits, identifiers in an ASCII grammar — ASCII folding is not just faster there, it is more correct, because Content-Length should match content-length and should not match some Unicode homoglyph.

One more trap worth carrying with you: to_lowercase() can change the number of characters. '\u{130}' (Latin capital I with dot above) lowercases to two chars. So byte offsets computed on a lowercased copy do not map back onto the original — which is a second, quieter reason not to lowercase a string just to search it.

::: question One of the test cases is ["straße", "STRASSE"] searched for "STRASSE". Why is the answer [1] and not [0, 1]? Because ß uppercases to SS under full Unicode case folding, so a truly locale-aware comparison would call those equal — but eq_ignore_ascii_case only maps A–Z to a–z, and ß is not in that range. The lengths do not even match (7 bytes versus 7… but 6 chars versus 7), so the byte comparison fails immediately.

The test exists so that the semantics you are implementing are written down rather than assumed. “Case-insensitive” is not one operation; it is at least three, and the standard library makes you pick. :::

What clippy will and will not do for you

clippy has manual_ignore_case_cmp in the default set, and it is one of the few default-on lints that teaches exactly the right thing:

error: manual case-insensitive ASCII comparison
help: consider using `.eq_ignore_ascii_case()` instead

Be precise about when it fires, though — verified against clippy 0.1.95:

a.to_ascii_lowercase() == b.to_ascii_lowercase()   // lint fires
a.to_lowercase()       == b.to_lowercase()         // lint stays SILENT

It only recognises the ASCII spelling, because only there can it prove the rewrite preserves meaning. The Unicode spelling — the one most beginners actually write, the one that costs 32× — sails straight through the gate. That is why this problem measures allocations instead of trusting the lint.

Building the substring search

str::contains is case-sensitive, and there is no contains_ignore_ascii_case in std. You need one comparison primitive that does exist: <[u8]>::eq_ignore_ascii_case, which compares two byte slices with ASCII folding and no allocation. Combine it with windows(n) over the haystack’s bytes and the whole thing is three lines and zero allocations.

let n = needle.as_bytes();
s.as_bytes().windows(n.len()).any(|w| w.eq_ignore_ascii_case(n))

Two things to be careful about: windows(0) panics, so guard the empty needle before you get there; and windows is a slice method, not an iterator adapter — you will meet that boundary properly later in this track.

Remember the grade is compile + tests + clippy -D warnings.