Compiling Rust is NP-hard July 7, 2021 · 11 minute read ...though it's not the flagship borrow checking that's at fault. What I noticed, and would like to share with you today, is that the exhaustiveness checking performed by the Rust compiler on match patterns is a superset of the SAT problem. Exhaustiveness checking Consider the following code (playground): fn update_thing(old_thing: Option<Thin