Rethink Type Storage

[purefunctor]

Status: Proposal
Author: Justin Garcia, Claude Opus 4.5
Date: 2026-01-17

Author's Note

This is a rough draft based on an exploratory thread in Claude Code.
Do not treat this as a formal design document, more like a thought dump.
Feasibility will be explored at a later time, probably once we have
compiler metrics set up and ready to measure performance concretely.

Update (2026-01-17): The liveness flag design has unresolved safety
issues around module re-checking — when a module is re-checked, stale
TypeRefs from the old check could appear valid again. Potential fixes
(generational counters, SnapshotId threading, Arc<AtomicBool>) each
have trade-offs that need more thought. This design needs to cook longer
and would benefit from input from someone with more compiler experience.

Also worth noting: if the memoisation cache for localize/globalize
proves sufficient, this redesign may not be necessary at all.

Executive Summary

Replace the current index-based dual-interner architecture with a weak pointer model that:

• Makes localisation O(1) (currently O(tree))
• Reduces globalisation to necessary work only
• Eliminates parallelism bottlenecks from per-type locking
• Provides runtime safety for use-after-free bugs

---

Problem Statement

The type checker uses a dual-interner architecture:

• Global interner (QueryStorage.interned.types): Types persisted in CheckedModule
• Local interner (CheckState.storage): Temporary types during checking

Types cross boundaries via transfer operations (transfer.rs):

• localize: Global → Local
• globalize: Local → Global

Current Implementation

Both operations perform full tree traversal, rebuilding every node:

fn traverse<Q: ExternalQueries>(source: &mut TraversalSource<Q>, id: TypeId) -> TypeId {
    let ty = match source.lookup(id) {
        Type::Function(a, b) => {
            let a = traverse(source, a);
            let b = traverse(source, b);
            Type::Function(a, b)
        }
        // ... every variant rebuilt
    };
    source.intern(ty)  // hash, lookup, allocate
}

Problems

1. O(tree) for every transfer - even repeated transfers of identical types
2. No memoisation - same structural types traversed multiple times
3. Same-module round-trip - globalised types need localisation to access locally
4. Per-type locking - intern_type acquires write lock individually:

fn intern_type(&self, t: Type) -> TypeId {
    let mut storage = self.storage.write();  // LOCK per type!
    storage.interned.types.intern(t)
}

This serialises parallel type checking across modules.

---

Survey of Other Approaches

Garbage-Collected Hosts (TypeScript, typescript-go)

Delegate to host GC. Type objects become unreachable and get collected automatically.

Trade-off: Simplest, but dependent on GC heuristics.

Arena + Lifetime Binding (rustc, Swift)

Single arena with types tied to context lifetime ('tcx):

pub struct TyCtxt<'tcx> {
    arena: &'tcx Arena<'tcx>,
}

Trade-off: Requires lifetime threading; memory not reclaimed until compilation ends.

Level-Based Scoping (OCaml, GHC)

Type variables carry integer levels indicating binding depth. GHC uses "zonking" to freeze mutable variables.

Trade-off: Requires mutable types during inference; incompatible with durable LSP types.

Why These Don't Fit

Our types must be:

• Immutable (for interning/caching)
• Durable (persist in CheckedModule across queries)
• Shareable (referenced by dependent modules)

Level-based approaches assume transient, mutable types. Lifetime-based approaches don't fit the query architecture.

---

Why Index-Based Compaction Fails

With TypeId as a direct index:

[Type, Unification, Type]  →  [Type, Type]
                                    ↑
                          TypeId(2) now wrong

Compaction requires remapping every TypeId in:

• Every Type in the interner
• Every CheckedModule in query cache
• Every structure holding TypeIds

That's reconstruction of the universe, not compaction.

---

Proposed Design: Weak Pointer Architecture

Core Insight

Use tagged pointers with liveness flags instead of indices. Local types can reference global types directly. Transfer becomes evacuation rather than reconstruction.

Liveness Flags

Problem with naive approach: If LocalStorage owns an AtomicBool and TypeRef holds NonNull<AtomicBool>, when LocalStorage drops the AtomicBool is deallocated — dereferencing the NonNull is use-after-free.

Solution: Global flag arena indexed by FileId. Flags outlive all TypeRefs.

/// Global flag - always true (global types are always valid)
static GLOBAL_FLAG: AtomicBool = AtomicBool::new(true);

/// Liveness flags indexed by FileId - never deallocated
static FLAGS: OnceLock<RwLock<FxHashMap<FileId, AtomicBool>>> = OnceLock::new();

struct LocalStorage {
    arena: BumpArena,
    file_id: FileId,
}

impl Drop for LocalStorage {
    fn drop(&mut self) {
        // Set our flag to false - TypeRefs will return Poisoned
        let flags = FLAGS.get().unwrap().read();
        flags[&self.file_id].store(false, Ordering::Release);
    }
}

Type Reference

#[derive(Copy, Clone, PartialEq, Eq, Hash)]
struct TypeRef {
    ptr: NonNull<TypeNode>,
    source: Option<FileId>,  // None = global, Some = local
}

struct TypeNode {
    ty: Type,
    hash: u64,  // cached for O(1) hash-cons lookup
}

With FileId as NonZeroU32, Option<FileId> uses niche optimisation — same size as a raw u32. Global refs (None) short-circuit the liveness check entirely.

Type Representation

#[derive(Clone, PartialEq, Eq, Hash)]
pub enum Type {
    Application(TypeRef, TypeRef),
    Constrained(TypeRef, TypeRef),
    Constructor(FileId, TypeItemId),
    Forall(ForallBinder, TypeRef),
    Function(TypeRef, TypeRef),
    Integer(i32),
    KindApplication(TypeRef, TypeRef),
    Kinded(TypeRef, TypeRef),
    Operator(FileId, TypeItemId),
    OperatorApplication(FileId, TypeItemId, TypeRef, TypeRef),
    Row(RowType),  // RowType uses TypeRef
    String(StringKind, SmolStr),
    SynonymApplication(Saturation, FileId, TypeItemId, Arc<[TypeRef]>),
    Unification(u32),
    Variable(Variable),  // Variable kinds use TypeRef
    Unknown,
    /// Stale reference dereferenced - this is always a bug
    Poisoned,
}

Storage Structures

struct GlobalStorage {
    arena: BumpArena,
    table: HashSet<NonNull<TypeNode>>,  // hash-cons deduplication
}

struct LocalStorage {
    arena: BumpArena,
    file_id: FileId,
    table: HashSet<NonNull<TypeNode>>,
}

struct TypeContext<'a> {
    global: &'a GlobalStorage,
    local: Option<&'a LocalStorage>,
}

---

Operations

Dereference

Returns Type by value (~32 bytes shallow copy). No lifetime entanglement.

impl TypeRef {
    pub fn get(self) -> Type {
        // Global refs always valid - skip flag check
        if let Some(file_id) = self.source {
            let flags = FLAGS.get().unwrap().read();
            if !flags[&file_id].load(Ordering::Acquire) {
                return Type::Poisoned;
            }
        }
        unsafe { self.ptr.as_ref().ty.clone() }
    }

    pub fn is_global(self) -> bool {
        self.source.is_none()
    }
}

Allocation

Local:

impl LocalStorage {
    fn intern(&mut self, ty: Type) -> TypeRef {
        let hash = hash_type(&ty);

        if let Some(&existing) = self.table.get_by_hash(hash, |n| n.ty == ty) {
            return TypeRef { ptr: existing, source: Some(self.file_id) };
        }

        let node = self.arena.alloc(TypeNode { ty, hash });
        self.table.insert(node);
        TypeRef { ptr: node, source: Some(self.file_id) }
    }
}

Global:

impl GlobalStorage {
    fn intern(&mut self, ty: Type) -> TypeRef {
        debug_assert!(ty.children().all(|r| r.is_global()), "local children in global intern");

        let hash = hash_type(&ty);

        if let Some(&existing) = self.table.get_by_hash(hash, |n| n.ty == ty) {
            return TypeRef { ptr: existing, source: None };
        }

        let node = self.arena.alloc(TypeNode { ty, hash });
        self.table.insert(node);
        TypeRef { ptr: node, source: None }
    }
}

Localisation: O(1)

fn localise(r: TypeRef) -> TypeRef {
    r  // Just use it. Global refs work directly in local context.
}

No traversal. No copying. Zero cost.

Globalisation: O(local nodes)

fn globalise(
    r: TypeRef,
    global: &mut GlobalStorage,
    cache: &mut FxHashMap<TypeRef, TypeRef>,
) -> TypeRef {
    // Already global? Done.
    if r.is_global() {
        return r;
    }

    // Already processed?
    if let Some(&cached) = cache.get(&r) {
        return cached;
    }

    let ty = r.get();

    let global_ty = match ty {
        Type::Function(a, b) => {
            let a = globalise(a, global, cache);
            let b = globalise(b, global, cache);
            Type::Function(a, b)
        }
        Type::Unification(_) => Type::Unknown,
        Type::Poisoned => Type::Poisoned,
        // ... other variants
        leaf => leaf,  // no TypeRef children
    };

    let global_ref = global.intern(global_ty);
    cache.insert(r, global_ref);
    global_ref
}

Key properties:

• Global subtrees: O(1) immediate return
• Cached local refs: O(1) cache hit
• Hash-consing: structural deduplication preserved
• Unification variables: become Type::Unknown

---

Implicit Garbage Collection

This design is a minimal two-generation collector:

GC Concept	Implementation
Young generation	LocalStorage (per-check arena)
Old generation	GlobalStorage (session lifetime)
Allocation	local.intern() / global.intern()
Minor collection	Drop LocalStorage
Promotion	globalise() - evacuate to old gen
Weak references	TypeRef with liveness flag
Root set	Types stored in CheckedModule

Why This Fits Type Checking

┌─────────────────────────────────────────────────────────────┐
│ Check Module                                                │
│                                                             │
│   1. Allocate in nursery (LocalStorage)                    │
│      - Unification variables                                │
│      - Intermediate types                                   │
│      - Working copies                                       │
│                                                             │
│   2. Reference tenured types directly (GlobalStorage)       │
│      - Types from dependencies (FREE - no localisation!)    │
│      - Prim types                                           │
│      - Already-checked types                                │
│                                                             │
│   3. Promote survivors (globalise)                          │
│      - Final inferred types                                 │
│      - Class instances                                      │
│      - Exported signatures                                  │
│                                                             │
│   4. Minor collection (drop LocalStorage)                   │
│      - Unification variables die                            │
│      - Intermediate garbage freed                           │
│      - Nursery reset for next check                         │
└─────────────────────────────────────────────────────────────┘

Most allocations die young. Survivors are final types. Classic generational hypothesis.

---

Safety Model

Invariants

1. Global TypeRefs always valid - source: None skips flag check entirely
2. Local TypeRefs valid during check - flag is true while LocalStorage exists
3. CheckedModule contains only global TypeRefs - enforced by globalisation
4. Flags outlive all TypeRefs - global arena indexed by FileId, never deallocated

Bug Detection

If globalisation has a bug:

1. Buggy TypeRef still has source: Some(file_id)
2. LocalStorage drops → flag at file_id set to false
3. Next get() → flag check fails → Type::Poisoned

Bugs surface as Poisoned types instead of undefined behavior.

Distinction

• Type::Unknown = legitimately unknown (inference failure, parse error)
• Type::Poisoned = invariant violation, globalisation bug

---

Parallelism

Current Problem

fn intern_type(&self, t: Type) -> TypeId {
    let mut storage = self.storage.write();  // WRITE LOCK per type
    storage.interned.types.intern(t)
}

All threads contend on every type operation.

New Model

Local work is lock-free:

• Each thread owns its LocalStorage
• No contention during type checking

Global contention only at commit:

• Globalisation happens once per module
• Can be batched or use concurrent structures

Parallelism Strategies

Option A: Batch Globalisation

fn globalise_module(local_types: Vec<TypeRef>, global: &GlobalStorage) -> Vec<TypeRef> {
    // Phase 1: Traverse and collect (no lock)
    let batch = collect_types_to_intern(...);

    // Phase 2: Single lock, batch insert
    let mut storage = global.lock();
    batch.iter().map(|ty| storage.intern(ty)).collect()
}

Option B: Sharded Storage

struct GlobalStorage {
    shards: [RwLock<Shard>; 64],
}

fn intern(&self, ty: Type) -> TypeRef {
    let shard_idx = hash_type(&ty) as usize % 64;
    self.shards[shard_idx].write().intern(ty)
}

Option C: Lock-Free Structures

struct GlobalStorage {
    arena: LockFreeArena,
    table: DashMap<u64, NonNull<TypeNode>>,
}

Contention Comparison

Before:

Thread 1: intern→LOCK→unlock→intern→LOCK→unlock→...
Thread 2: intern→LOCK→unlock→intern→LOCK→unlock→...
          ^^^^^^^^ constant contention ^^^^^^^^

After:

Thread 1: [local, local, local] → LOCK → batch → unlock
Thread 2: [local, local, local] → LOCK → batch → unlock
          ^^^ no contention ^^^   ^^^^ brief, batched ^^^^

---

Memory Layout

TypeRef:  16 bytes (8-byte aligned)
  - ptr:    NonNull<TypeNode>  (8 bytes)
  - source: Option<FileId>     (4 bytes, niche-optimised with NonZeroU32)
  - padding                    (4 bytes)

TypeNode: ~48 bytes
  - ty:   Type (~32 bytes, largest variant)
  - hash: u64 (8 bytes)

Type: ~32 bytes (shallow - contains TypeRefs, not nested Types)

Comparison

Aspect	Current (Index)	Proposed (Weak Ptr)
Ref size	4 bytes	16 bytes
Localise	O(tree)	O(1)
Globalise	O(tree) rebuild	O(local) evacuate
Deref	interner[id]	ptr.get() + flag check
Equality	id == id	ptr == ptr
Parallel	per-type lock	per-module lock

---

Alternative: Arc

Instead of a global flag arena, each TypeRef could hold Arc<AtomicBool>:

struct TypeRef {
    ptr: NonNull<TypeNode>,
    alive: Arc<AtomicBool>,
}

Pros:

• Simpler mental model
• No global state
• Flag naturally outlives all refs

Cons:

• Ref-counting overhead on every TypeRef clone
• 8 extra bytes per TypeRef (Arc pointer)
• Atomic increment/decrement on every copy

The FileId-indexed approach avoids this overhead since FileId is already available and flags are long-lived.

---

Migration Path

Phase 1: New Types Module

Create checking::types with new structures alongside existing core.rs.

Phase 2: Dual Support

Support both representations during transition. Convert at boundaries.

Phase 3: Migrate Incrementally

Update algorithm modules one at a time to use new representation.

Phase 4: Remove Old Code

Delete transfer.rs, old TypeId, unused interner code.

---

Open Questions

1. Arena implementation - bumpalo, custom, or typed_arena?
2. Hash function - FxHash, AHash, or custom for Type?
3. Global storage structure - Sharded, lock-free, or simple RwLock with batching?
4. TypeNode layout - Inline small types? Separate hash table?
5. Flag arena cleanup - Do we ever need to reclaim flags for deleted files?

---

References

• rustc Memory Management
• OCaml Type Generalization (Oleg Kiselyov)
• GHC Zonking
• TypeScript Checker Wiki