Struct Substitution 

pub struct Substitution { /* private fields */ }

A substitution mapping type variables to their resolved types.

The substitution is built incrementally during unification. It maps type variable IDs to InferTypes, which may themselves be type variables (requiring transitive lookup via apply).

Performance

Uses a Vec<Option<InferType>> instead of HashMap<TypeVarId, InferType> for O(1) lookups without hashing overhead. This works because TypeVarId is a sequential u32 starting from 0.

Additionally implements path compression: when following a chain of variable references, intermediate links are updated to point directly to the final result, amortizing the cost of chain traversal.

Implementations

impl Substitution

pub fn new() -> Self

Create an empty substitution.

pub fn with_capacity(capacity: usize) -> Self

Create a substitution with pre-allocated capacity.

Use when you know approximately how many type variables will be created.

pub fn insert(&mut self, var: TypeVarId, ty: InferType)

Insert a mapping from a type variable to a type.

If the variable is already mapped, the old mapping is replaced.

pub fn get(&self, var: TypeVarId) -> Option<InferType>

Look up a type variable’s immediate mapping (without following chains).

pub fn apply(&self, ty: &InferType) -> InferType

Apply the substitution to a type, following type variable chains to their ultimate resolution.

• Concrete(ty) → Concrete(ty) (unchanged)
• Var(id) → follows chain until concrete or unbound variable
• IntLiteral → IntLiteral (unchanged, unless we add IntLiteral to variable mappings)
• Array { element, length } → recursively apply to element type

Path Compression

When following a chain like v0 -> v1 -> v2 -> i32, this method updates all intermediate links to point directly to the final result. This amortizes the cost of repeated lookups.

pub fn occurs_in(&self, var: TypeVarId, ty: &InferType) -> bool

Check if a type variable occurs in a type (for occurs check).

This prevents creating infinite types like α = List<α>. Returns true if the variable occurs in the type.

pub fn len(&self) -> usize

Get the number of mappings in the substitution.

Note: This counts all slots that have values, requiring a full scan. For performance-critical code, consider tracking this separately.

pub fn is_empty(&self) -> bool

Check if the substitution is empty.

Trait Implementations

impl Debug for Substitution

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Substitution

fn default() -> Substitution

Returns the “default value” for a type.