How Sway Implements Pattern Matching Exhaustiveness Checking: The Maranget Algorithm Explained

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, 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.

// 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, the compiler assembles the Matrix structure as a Vec<PatStack>, 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.

// From matrix.rs
pub(crate) fn compute_sigma(&self) -> Vec<Constructor>

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, 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.

// 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, specifically the is_useful function implementing U(P, q)—the usefulness test that determines if pattern q adds any new witnesses to matrix P.

// From usefulness.rs
pub(crate) fn is_useful(
    handler: &Handler,
    engines: &Engines,
    factory: &ConstructorFactory,
    matrix: &Matrix,
    pat_stack: &PatStack,
    span: &Span,
) -> Result<WitnessReport, ErrorEmitted>

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.

// 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 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:

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:

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:

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.

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. 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.

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. 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}