How Sway Type System Performs Type Unification: A Deep Dive into the Compiler

Sway's type system performs type unification through a two-stage process involving UnifyCheck to verify compatibility and Unifier to perform actual type substitution in the TypeEngine, both implemented in the sway-core crate.

Type unification is the core algorithm that enables Sway's Hindley-Milner-style type inference, allowing the compiler to resolve generic types into concrete ones and verify that expressions match their expected types. In the FuelLabs/sway repository, this critical functionality resides in sway-core/src/type_system/unify/, where the compiler separates the feasibility check from the destructive update operation.

The Two-Stage Type Unification Architecture

Sway employs a strict separation of concerns when resolving type compatibility:

1. UnifyCheck – A read-only utility that answers "Can these types be made equal?" without modifying the TypeEngine.
2. Unifier – A write-capable struct that performs "Make these types equal" by updating type variables and generic parameters.

This design prevents partial mutations when unification fails halfway through complex structural types like structs or enums.

Stage 1: Type Compatibility Checking with UnifyCheck

Located in sway-core/src/type_system/unify/unify_check.rs, the UnifyCheck utility implements the classic occurs-check and structural comparison logic required for sound type inference.

UnifyCheck Modes and Semantics

UnifyCheck operates in three distinct modes via the UnifyCheckMode enum:

• Coercion – The most permissive check, asking "Can left be coerced into right?" Used during standard type inference when flexibility is required.
• ConstraintSubset – Validates that left is a subset of right, used for generic constraint checking.
• NonDynamicEquality – Enforces that two concrete types are definitely equal, used when the compiler must reject ambiguous matches.

The UnifyCheck Algorithm

The public entry point UnifyCheck::check(left, right) executes the following steps:

1. Fast-path equality – Returns true immediately if both TypeIds are identical.
2. Top-level generic shortcut – In NonGenericConstraintSubset mode, a generic on the right side matches any left side that satisfies its underlying TypeInfo.
3. Recursive structural walk – check_inner recurses over arrays, slices, tuples, structs, enums, custom types, references, and generic parameters.
4. Mode-specific rules – In Coercion mode, Placeholder or Unknown types unify with any type, while NonDynamicEquality rejects these flexible types.

Preventing Infinite Types with OccursCheck

Before unifying a generic type variable with a concrete type, Sway performs an occurs-check via sway-core/src/type_system/unify/occurs_check.rs to prevent infinite recursive types like T = &[T]. The OccursCheck::new(...).check(generic, other) method traverses the prospective replacement type to ensure the generic variable does not appear within its own definition.

Stage 2: Type Substitution with Unifier

Once compatibility is confirmed, the Unifier struct in sway-core/src/type_system/unify/unifier.rs performs the actual type merging by updating the TypeEngine.

Unifier Structure and Configuration

The Unifier carries three critical pieces of state:

pub(crate) struct Unifier<'a> {
    engines: &'a Engines,      // Access to TypeEngine and DeclEngine
    help_text: String,         // User-facing error message context
    unify_kind: UnifyKind,     // Default / WithSelf / WithGeneric
}

UnifyKind determines which side may be more informative:

• Default – Standard bidirectional unification.
• WithSelf – Prefers replacing the expected side when the self-type appears on the right (used in impl blocks).
• WithGeneric – Allows generic parameters on the expected side to be inferred from the received side.

The Unification Process

The Unifier::unify method follows this control flow:

1. Record unification – Optionally logs the step for diagnostic purposes.
2. Early exit – Returns immediately if received and expected TypeIds are identical.
3. TypeInfo dispatch – Matches on the concrete TypeInfo variants of both sides.

When one side is flexible (Unknown, Placeholder, or UnknownGeneric), the unifier calls replacement helpers:

fn replace_received_with_expected(&self, received: TypeId, expected_type_info: &TypeInfo, span: &Span) {
    self.engines.te().replace_with_new_source_id(
        self.engines,
        received,
        expected_type_info.clone(),
        span.source_id().copied(),
    );
}

Handling Complex Types

For structural types, unify delegates to specialized helpers:

• Structs – unify_structs verifies that call paths and generic parameters match, then recurses on fields (lines 139-202 in unifier.rs).
• Enums – Similar to structs but handles variant unification.
• Arrays – Checks element type unification and length compatibility.
• References – Handles mutability subtyping where &mut T can coerce to &T.
• Aliases – Re-enters unify on the underlying aliased type.
• Never – The Never type coerces to any type without error.

When structural mismatches occur, the unifier emits a MismatchedType error through the Handler, incorporating the help_text provided at construction.

Code Examples: Type Unification in Practice

Example 1: Primitive Type Checking

let engines = Engines::default();
let handler = Handler::default();
let span = Span::dummy();

let u8_id   = engines.te().id_of_u8();
let u16_id  = engines.te().id_of_u16();

let check = UnifyCheck::coercion(&engines);
assert!(!check.check(u8_id, u16_id));          // u8 cannot coerce to u16

let unifier = Unifier::new(&engines, "type mismatch", UnifyKind::Default);
unifier.unify(&handler, u8_id, u8_id, &span, true); // succeeds, no change

Source: unify_check.rs lines 38-45 (mode creation) and unifier.rs lines 19-31 (constructor) & 92-106 (early-exit).

Example 2: Generic to Concrete Unification

// Assume we have a generic type variable `T` (an UnknownGeneric) and a concrete `u64`.
let generic_t = engines.te().insert_unknown_generic(
    Ident::new_with_override("T".into(), Span::dummy()),
    VecSet::default(),
    None,
    false,
);
let u64_id = engines.te().id_of_u64();

let check = UnifyCheck::coercion(&engines);
assert!(check.check(generic_t, u64_id)); // generic can be coerced to concrete

let unifier = Unifier::new(&engines, "cannot infer generic", UnifyKind::Default);
unifier.unify(&handler, generic_t, u64_id, &span, true);
// The generic `T` is now replaced in the TypeEngine with `u64`.

Source: unify_check.rs lines 46-70 (generic coercion rule).
unifier.rs lines 101-108 (record unification) and 123-130 (replace unknown with expected).

Example 3: Struct Unification with Generics

// struct Pair<T, U> { a: T, b: U }
let pair_decl = engines.de().insert_struct(
    CallPath { prefixes: vec![], suffix: Ident::new_with_override("Pair".into(), Span::dummy()), callpath_type: CallPathType::Full },
    vec![
        // fields
        TyStructField { name: Ident::new_with_override("a".into(), Span::dummy()), type_argument: GenericTypeArgument { type_id: generic_t, .. } },
        TyStructField { name: Ident::new_with_override("b".into(), Span::dummy()), type_argument: GenericTypeArgument { type_id: generic_u, .. } },
    ],
    // generic parameters
    vec![
        TypeParameter::Type(generic_t_param),
        TypeParameter::Type(generic_u_param),
    ],
);
let pair_type_id = engines.te().insert_struct(pair_decl, ...);

// Another concrete instance `Pair<u8, u64>`
let concrete_pair = ... // similar but with concrete type IDs for `u8` and `u64`.

let check = UnifyCheck::coercion(&engines);
assert!(check.check(pair_type_id, concrete_pair));

let unifier = Unifier::new(&engines, "struct mismatch", UnifyKind::Default);
unifier.unify(&handler, pair_type_id, concrete_pair, &span, true);
// The generic parameters inside the first struct are now bound to `u8` and `u64`.

Source:

• Struct unification logic – unifier.rs lines 93-102 (Struct arm) → unify_structs (lines 139-202).
• Generic handling inside unify_structs – lines 166-190 (field-wise recursion).

Key Source Files and Implementation Details

File	Purpose	Link
sway-core/src/type_system/unify/unify_check.rs	Boolean feasibility check for unification (coercion, constraint subset, non-dynamic equality).	view
sway-core/src/type_system/unify/unifier.rs	Performs the actual type substitution in the TypeEngine. Handles all concrete cases (primitives, structs, enums, arrays, refs, placeholders, generics, etc.).	view
sway-core/src/type_system/unify/occurs_check.rs	Prevents infinite recursive types (T occurring inside its own definition).	view
sway-core/src/type_system/info.rs	Definition of TypeInfo, the enum that represents every possible type in Sway.	view
sway-core/src/type_system/mod.rs	Re-exports the unifier utilities for the rest of the compiler.	view

These files collectively implement a Hindley-Milner-style unification algorithm extended for Sway's specific concepts (placeholders, const generics, contract callers, and trait-constraint subtyping).

Summary

• Sway type system type unification operates through a strict two-phase architecture: UnifyCheck for read-only feasibility testing and Unifier for write-enabled type substitution.
• Three checking modes—Coercion, ConstraintSubset, and NonDynamicEquality—provide different levels of strictness for various compiler phases.
• Structural recursion handles complex types including structs, enums, arrays, and references, with special logic for generic parameter binding.
• Occurs-check protection prevents infinite recursive type definitions like T = &[T] before unification commits to a substitution.
• UnifyKind configuration (Default, WithSelf, WithGeneric) controls directional preferences when unifying self-types or generic constraints.

Frequently Asked Questions

What is the difference between UnifyCheck and Unifier in Sway?

UnifyCheck is a read-only utility that returns a boolean indicating whether two types can be unified without modifying the TypeEngine. It implements the occurs-check and structural comparison logic. In contrast, Unifier is a write-capable struct that actually performs the substitution, updating type variables and generic parameters in the TypeEngine when the compiler commits to a unification decision.

How does Sway prevent infinite recursive types during unification?

Sway implements an occurs-check via sway-core/src/type_system/unify/occurs_check.rs before performing any substitution. This check traverses the prospective replacement type to ensure that the generic type variable being unified does not occur within its own definition, preventing infinite types such as T = &[T] from being constructed.

What are the different modes of type checking in Sway's UnifyCheck?

UnifyCheck supports three distinct modes via UnifyCheckMode: Coercion (the most permissive, allowing flexible type inference), ConstraintSubset (validating that one type satisfies the constraints of another for generic bounds), and NonDynamicEquality (strict equality for concrete types where ambiguity must be rejected). Each mode activates different rules for handling placeholders, unknown generics, and structural types.

How does Sway handle generic type parameters during unification?

When unifying types containing generic parameters, Sway's Unifier recursively processes the generic arguments alongside the main type structure. For struct and enum unification, the compiler verifies that call paths match and then calls unify on each generic parameter, effectively binding unknown generics to concrete types (such as replacing T with u64) through the replace_received_with_expected helper in unifier.rs.

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