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

> Discover how Sway type system performs unification with UnifyCheck and Unifier in sway-core for robust type compatibility and substitution.

- Repository: [Fuel Labs/sway](https://github.com/FuelLabs/sway)
- Tags: deep-dive
- Published: 2026-03-04

---

**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`](https://github.com/FuelLabs/sway/blob/main/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 `TypeId`s 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`](https://github.com/FuelLabs/sway/blob/main/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`](https://github.com/FuelLabs/sway/blob/main/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:

```rust
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` `TypeId`s 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:

```rust
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`](https://github.com/FuelLabs/sway/blob/main/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

```rust
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`](https://github.com/FuelLabs/sway/blob/main/unify_check.rs) lines 38-45 (mode creation) and [`unifier.rs`](https://github.com/FuelLabs/sway/blob/main/unifier.rs) lines 19-31 (constructor) & 92-106 (early-exit).

### Example 2: Generic to Concrete Unification

```rust
// 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`](https://github.com/FuelLabs/sway/blob/main/unify_check.rs) lines 46-70 (generic coercion rule).  
[`unifier.rs`](https://github.com/FuelLabs/sway/blob/main/unifier.rs) lines 101-108 (record unification) and 123-130 (replace unknown with expected).

### Example 3: Struct Unification with Generics

```rust
// 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`](https://github.com/FuelLabs/sway/blob/main/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`](https://github.com/FuelLabs/sway/blob/main/sway-core/src/type_system/unify/unify_check.rs) | Boolean feasibility check for unification (coercion, constraint subset, non-dynamic equality). | [view](https://github.com/FuelLabs/sway/blob/master/sway-core/src/type_system/unify/unify_check.rs) |
| [`sway-core/src/type_system/unify/unifier.rs`](https://github.com/FuelLabs/sway/blob/main/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](https://github.com/FuelLabs/sway/blob/master/sway-core/src/type_system/unify/unifier.rs) |
| [`sway-core/src/type_system/unify/occurs_check.rs`](https://github.com/FuelLabs/sway/blob/main/sway-core/src/type_system/unify/occurs_check.rs) | Prevents infinite recursive types (`T` occurring inside its own definition). | [view](https://github.com/FuelLabs/sway/blob/master/sway-core/src/type_system/unify/occurs_check.rs) |
| [`sway-core/src/type_system/info.rs`](https://github.com/FuelLabs/sway/blob/main/sway-core/src/type_system/info.rs) | Definition of `TypeInfo`, the enum that represents every possible type in Sway. | [view](https://github.com/FuelLabs/sway/blob/master/sway-core/src/type_system/info.rs) |
| [`sway-core/src/type_system/mod.rs`](https://github.com/FuelLabs/sway/blob/main/sway-core/src/type_system/mod.rs) | Re-exports the unifier utilities for the rest of the compiler. | [view](https://github.com/FuelLabs/sway/blob/master/sway-core/src/type_system/mod.rs) |

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`](https://github.com/FuelLabs/sway/blob/main/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`](https://github.com/FuelLabs/sway/blob/main/unifier.rs).