# How Sway Implements Pattern Matching Exhaustiveness Checking: The Maranget Algorithm Explained > Discover how Sway implements pattern matching exhaustiveness checking using the Maranget algorithm. Learn about pattern matrices and recursive usefulness analysis in semantic analysis. - Repository: [Fuel Labs/sway](https://github.com/FuelLabs/sway) - Tags: internals - Published: 2026-03-04 --- **Sway implements pattern matching exhaustiveness checking by porting the Maranget algorithm from Rust, using a pattern matrix and recursive usefulness analysis during the semantic analysis phase.** Pattern matching is a core feature of the Sway language, requiring rigorous exhaustiveness checking to ensure all possible cases are handled at compile time. According to the FuelLabs/sway source code, this critical safety check is implemented as a direct port of the classic Maranget algorithm, operating on a high-level pattern matrix representation during semantic analysis in `sway-core`. ## The Maranget Algorithm and Pattern Matrices The foundation of Sway's exhaustiveness checking lies in the Maranget algorithm, which treats pattern matching as a matrix problem. The compiler builds a **pattern matrix** where each row represents a match arm and each column represents a position in the pattern structure. ### Building Patterns from Scrutinees The process begins in [`sway-core/src/semantic_analysis/ast_node/expression/match_expression/analysis/pattern.rs`](https://github.com/FuelLabs/sway/blob/main/sway-core/src/semantic_analysis/ast_node/expression/match_expression/analysis/pattern.rs), where user-written scrutinees are converted into an internal `Pattern` representation. The `Pattern::from_scrutinee` function transforms each `TyScrutinee` into a `Pattern` enum that records its constructor and arguments. ```rust // From pattern.rs Pattern::from_scrutinee(scrutinee: TyScrutinee) -> Pattern ``` This conversion handles variables, literals, structs, enums, and tuples, creating a uniform representation for the matrix construction. ### Assembling the Matrix and Computing Sigma In [`matrix.rs`](https://github.com/FuelLabs/sway/blob/main/matrix.rs), the compiler assembles the `Matrix` structure as a `Vec`, where each `PatStack` represents a row of patterns. The matrix supports critical operations like computing **Σ (sigma)**, the set of root constructors appearing in the first column. ```rust // From matrix.rs pub(crate) fn compute_sigma(&self) -> Vec ``` The `compute_sigma` function identifies which constructors are already covered by the existing match arms, enabling the algorithm to determine what might be missing. ## Constructor Completeness and the Usefulness Check The core decision logic resides in determining whether the set of constructors Σ is complete for the type being matched. ### Checking Constructor Completeness In [`constructor_factory.rs`](https://github.com/FuelLabs/sway/blob/main/constructor_factory.rs), the `ConstructorFactory::is_complete_signature` method queries the type engine to determine if Σ contains every possible constructor for the matched type. For enums, this means all variants; for numeric types, this means all possible values or ranges. ```rust // From constructor_factory.rs ConstructorFactory::is_complete_signature(constructors: &[Constructor]) -> bool ``` When Σ is incomplete, the factory can synthesize missing patterns via `create_pattern_not_present`, generating concrete examples of uncovered cases for error reporting. ### The is_useful Recursive Algorithm The heart of the Maranget implementation lives in [`usefulness.rs`](https://github.com/FuelLabs/sway/blob/main/usefulness.rs), specifically the `is_useful` function implementing **U(P, q)**—the usefulness test that determines if pattern `q` adds any new witnesses to matrix `P`. ```rust // From usefulness.rs pub(crate) fn is_useful( handler: &Handler, engines: &Engines, factory: &ConstructorFactory, matrix: &Matrix, pat_stack: &PatStack, span: &Span, ) -> Result ``` The function performs a three-way dispatch based on the pattern type: - `Pattern::Wildcard` → `is_useful_wildcard` - `Pattern::Or` → `is_useful_or` - Constructed patterns → `is_useful_constructed` ### Handling Wildcards and Incomplete Signatures When encountering a wildcard with an incomplete Σ, `is_useful_wildcard` computes the *default matrix* (rows where the first pattern is a wildcard) and recurses on the tail of the pattern stack. It then synthesizes a witness pattern using the constructor factory to demonstrate the missing case. This recursive specialization continues until the algorithm either exhausts all possibilities (returning `NoWitnesses`) or finds concrete counter-examples (returning `WitnessReport` with specific missing patterns). ## Error Reporting for Non-Exhaustive Matches When the usefulness check discovers missing patterns, the compiler generates a user-facing error defined in [`sway-error/src/error.rs`](https://github.com/FuelLabs/sway/blob/main/sway-error/src/error.rs). ```rust // From sway-error/src/error.rs #[error("Non-exhaustive match expression. Missing patterns {missing_patterns}")] NonExhaustiveMatchExpression { missing_patterns: String, } ``` The `check_match_expression_usefulness` function in [`usefulness.rs`](https://github.com/FuelLabs/sway/blob/main/usefulness.rs) drives the entire process, iterating over match arms, building the matrix, and finally testing an imaginary wildcard pattern to determine exhaustivity. It returns a `WitnessReport` that either confirms exhaustiveness (`NoWitnesses`) or provides concrete witnesses for error generation. ## Practical Examples of Exhaustiveness Checking ### Exhaustive Match on Enums When all variants of an enum are covered, the compiler accepts the match without error: ```sway enum Color { Red, Green, Blue, } fn main() { let c = Color::Red; match c { Color::Red => 0, Color::Green => 1, Color::Blue => 2, }; } ``` The pattern matrix contains three rows with constructors `Red`, `Green`, and `Blue`. Σ is complete for the `Color` enum, so the final wildcard test returns `NoWitnesses`. ### Non-Exhaustive Match Error Missing variants trigger the exhaustiveness checker to generate specific error messages: ```sway enum Status { Ok, Err, Unknown, } fn foo(s: Status) -> u64 { match s { Status::Ok => 0, } } ``` The algorithm constructs a matrix with only `[Status::Ok]`. Σ is incomplete, so `is_useful_wildcard` synthesizes missing patterns `Status::Err` and `Status::Unknown`, which appear in the compiler error: ``` error: Non-exhaustive match expression. Missing patterns {Status::Err, Status::Unknown} ``` ### Numeric Range Exhaustivity The checker handles numeric types by treating them as constructors with range signatures: ```sway fn test(x: u8) -> u8 { match x { 0 => 0, 1 => 1, } } ``` Because numeric types are treated as enums of all possible values, `ConstructorFactory::create_pattern_not_present` identifies the complement range `2..=255` and reports it as missing. ## Summary - Sway implements **pattern matching exhaustiveness checking** using the **Maranget algorithm**, ported directly from Rust's compiler implementation. - The algorithm operates on a **pattern matrix** constructed during semantic analysis in `sway-core/src/semantic_analysis/ast_node/expression/match_expression/analysis/`. - Key components include `Pattern::from_scrutinee` for building patterns, `Matrix::compute_sigma` for tracking constructors, and `is_useful` for recursive usefulness testing. - `ConstructorFactory` determines constructor completeness and synthesizes missing patterns when Σ is incomplete. - Non-exhaustive matches generate `CompileError::NonExhaustiveMatchExpression` with concrete missing patterns listed in the error message. ## Frequently Asked Questions ### What algorithm does Sway use for exhaustiveness checking? Sway uses the **Maranget algorithm**, the same pattern matching exhaustiveness technique employed by the Rust compiler. This algorithm treats match arms as rows in a pattern matrix and recursively tests whether new patterns add useful coverage via the `U(P,q)` usefulness function implemented in [`usefulness.rs`](https://github.com/FuelLabs/sway/blob/main/usefulness.rs). ### How does Sway represent patterns during semantic analysis? During semantic analysis, Sway converts user-written scrutinees into an internal `Pattern` enum defined in [`pattern.rs`](https://github.com/FuelLabs/sway/blob/main/pattern.rs). The `Pattern::from_scrutinee` function handles literals, variables, structs, enums, and tuples, creating a uniform representation that stores constructors and their arguments for matrix operations in [`matrix.rs`](https://github.com/FuelLabs/sway/blob/main/matrix.rs). ### What happens when a match expression is not exhaustive? When the exhaustiveness checker detects missing patterns, it emits `CompileError::NonExhaustiveMatchExpression` defined in [`sway-error/src/error.rs`](https://github.com/FuelLabs/sway/blob/main/sway-error/src/error.rs). The error message includes the specific missing patterns synthesized by `ConstructorFactory::create_pattern_not_present`, such as `EnumVariant::B` or numeric ranges like `2..=255`, allowing developers to see exactly which cases are unhandled. ### Does Sway support exhaustiveness checking for numeric ranges? Yes, Sway treats numeric types as constructors with complete signatures covering all possible values. The `ConstructorFactory` identifies incomplete coverage of numeric ranges and uses `create_pattern_not_present` to generate witness patterns representing the missing ranges, ensuring exhaustive checking works for `u8`, `u64`, and other numeric types.