std::map

std/src/map.mo

Key-value map type class. Types implementing Map provide ordered key-value storage with insertion, lookup, and deletion.

:= HashMap -- a declared default carrier, matching class FromListLiteral (L : Type -> Type := List)'s own convention -- so a NULLARY call like Map.empty (no args to infer a carrier from at all) can still resolve via resolve_class_method_call_d4_default_carrier (lang/scope.mo) instead of giving up. Confirmed via bootstrap compile cli/src/main.mo monad: lang/module.mo's module_scope_cache_empty's own struct- literal field entries := Map.empty (declared field type HashMap ModulePath ScopeData, ModuleScopeCache) hit exactly this -- that caller has since been deleted as dead code, but the gap it found is real and this default is what closes it -- HashMap is already this codebase's own preferred Map instance (see filter_reachable_decls's own doc comment on why), so it's the correct default here too.

classMap#
pub class Map (M : (K : Type) -> (V : Type) -> Type := HashMap) {
    def empty : M K V
    def insert (key : K) (val : V) (m : M K V) : M K V
    def lookup (key : K) (m : M K V) : Option V
    def delete (key : K) (m : M K V) : M K V
}

Key-value map type class. Types implementing Map provide ordered key-value storage with insertion, lookup, and deletion.

:= HashMap -- a declared default carrier, matching class FromListLiteral (L : Type -> Type := List)'s own convention -- so a NULLARY call like Map.empty (no args to infer a carrier from at all) can still resolve via resolve_class_method_call_d4_default_carrier (lang/scope.mo) instead of giving up. Confirmed via bootstrap compile cli/src/main.mo monad: lang/module.mo's module_scope_cache_empty's own struct- literal field entries := Map.empty (declared field type HashMap ModulePath ScopeData, ModuleScopeCache) hit exactly this -- that caller has since been deleted as dead code, but the gap it found is real and this default is what closes it -- HashMap is already this codebase's own preferred Map instance (see filter_reachable_decls's own doc comment on why), so it's the correct default here too.

typeBTreeMap#
pub type BTreeMap K V {
    empty,
    node (key : K) (val : V) (left : BTreeMap K V) (right : BTreeMap K V) (height : I64)
}

Balanced binary search tree (AVL) key-value map.

instance_#
pub instance [BOrd K, BEq V] BEq (BTreeMap K V) {
    def beq (a b : BTreeMap K V) : Bool := BTreeMap.beq a b
}
defBTreeMap.to_list#
pub def BTreeMap.to_list {K V : Type} (m : BTreeMap K V) : List (Pair K V)

Convert the map to a list of (key, value) pairs in ascending key order.

instance_#
pub instance [BOrd K] Map BTreeMap {
    def empty : BTreeMap K V := BTreeMap.empty

    // The recursive helpers own the recursion; the instance only wraps the
    // key/value/comparators ONCE per operation. `BOrd.lt`/`gt` are bound to
    // locals first: a bare method reference is the accepted shape, while a
    // qualified call is resolved at the call site.
    #[terminating]
    def insert (key : K) (val : V) (m : BTreeMap K V) : BTreeMap K V :=
        let lt : K -> K -> Bool := BOrd.lt in
        let gt : K -> K -> Bool := BOrd.gt in
        BTreeMap.insert_loop (Shared.of lt) (Shared.of gt) (Shared.of key) (Shared.of val) m

    #[terminating]
    def lookup (key : K) (m : BTreeMap K V) : Option V :=
        let lt : K -> K -> Bool := BOrd.lt in
        let gt : K -> K -> Bool := BOrd.gt in
        BTreeMap.lookup_loop (Shared.of lt) (Shared.of gt) (Shared.of key) m

    #[terminating]
    def delete (key : K) (m : BTreeMap K V) : BTreeMap K V :=
        let lt : K -> K -> Bool := BOrd.lt in
        let gt : K -> K -> Bool := BOrd.gt in
        BTreeMap.delete_loop (Shared.of lt) (Shared.of gt) (Shared.of key) m
}

Instance: BTreeMap implements the Map type class.

defHashMap.bucket_of#
pub def HashMap.bucket_of (hash : U64) : U64

Compute bucket index (0-255) from a hash value.

256, not 16. The table is two LEVELS of the same 16-way dispatch (Bucket16 below), so widening cost no new dispatch code -- and the old 16 was badly under-provisioned for how this codebase actually uses HashMap: the compiler keeps ~4,200 def names and ~2,700 reachability entries in one map, which at 16 buckets is ~260 entries per bucket, and bucket_lookup_eq scans a bucket LINEARLY. That made every lookup ~130 key comparisons on the hottest paths in the backend. At 256 the same maps sit at ~16 per bucket.

typeBucket16#
pub type Bucket16 P {
    buckets (
        b0 b1 b2 b3 b4 b5 b6 b7
        b8 b9 b10 b11 b12 b13 b14 b15
        : P)
}

One level of 16-way dispatch, generic in what a slot holds.

Generic in P specifically so it can nest: a HashMap's table is Bucket16 (Bucket16 (List (Pair K V))), which is 256 buckets built from ONE 16-arm dispatch written once, rather than a 256-field constructor and two 256-arm chains.

typeHashMap#
pub type HashMap K V {
    map (Bucket16 (Bucket16 (List (Pair K V))))
}

Hash map type: 256-bucket chaining hash table, as 16x16.

defHashMap.empty_buckets#
pub def HashMap.empty_buckets {K V : Type} : Bucket16 (Bucket16 (List (Pair K V)))

16 empty buckets.

defHashMap.get_bucket#
pub def HashMap.get_bucket {K V : Type} (b : Bucket16 (Bucket16 (List (Pair K V)))) (idx : U64) : List (Pair K V)
defHashMap.set_bucket#
pub def HashMap.set_bucket {K V : Type} (b : Bucket16 (Bucket16 (List (Pair K V)))) (idx : U64) (new_val : List (Pair K V)) : Bucket16 (Bucket16 (List (Pair K V)))
instance_#
pub instance [Hashable K, BOrd K] Map HashMap {
    def empty : HashMap K V := HashMap.map HashMap.empty_buckets

    #[terminating]
    def insert (key : K) (val : V) (m : HashMap K V) : HashMap K V :=
        let lt : K -> K -> Bool := BOrd.lt in
        let gt : K -> K -> Bool := BOrd.gt in
        match m {
            HashMap.map buckets =>
                let s := Shared.of buckets in
                let idx : U64 := HashMap.bucket_of (Hashable.hash key) in
                let bucket : List (Pair K V) := HashMap.get_bucket (Shared.get s) idx in
                let new_bucket : List (Pair K V) :=
                    HashMap.bucket_insert (Shared.of lt) (Shared.of gt) (Shared.of key) (Shared.of val) bucket in
                HashMap.map (HashMap.set_bucket (Shared.get s) idx new_bucket)
        }

    #[terminating]
    def lookup (key : K) (m : HashMap K V) : Option V :=
        let lt : K -> K -> Bool := BOrd.lt in
        let gt : K -> K -> Bool := BOrd.gt in
        match m {
            HashMap.map buckets =>
                let idx : U64 := HashMap.bucket_of (Hashable.hash key) in
                let bucket : List (Pair K V) := HashMap.get_bucket buckets idx in
                HashMap.bucket_lookup (Shared.of lt) (Shared.of gt) (Shared.of key) bucket
        }

    #[terminating]
    def delete (key : K) (m : HashMap K V) : HashMap K V :=
        let lt : K -> K -> Bool := BOrd.lt in
        let gt : K -> K -> Bool := BOrd.gt in
        match m {
            HashMap.map buckets =>
                let s := Shared.of buckets in
                let idx : U64 := HashMap.bucket_of (Hashable.hash key) in
                let bucket : List (Pair K V) := HashMap.get_bucket (Shared.get s) idx in
                let new_bucket : List (Pair K V) :=
                    HashMap.bucket_delete (Shared.of lt) (Shared.of gt) (Shared.of key) bucket in
                HashMap.map (HashMap.set_bucket (Shared.get s) idx new_bucket)
        }
}

Instance: HashMap implements the Map type class using hashing + ordering-based equality. NOTE: uses BOrd K instead of BEq K due to evaluator instance resolution limitation. The evaluator's resolve_class_method_instance picks the first registered instance (BOrd I64 is correctly first for I64 keys, but BEq Bool is first for BEq, producing wrong instance when abstract K is concrete I64 at runtime).

defHashMap.bucket_lookup_str#
pub def HashMap.bucket_lookup_str {V : Type} (key : String) (bucket : List (Pair String V)) : Option V

bucket_lookup_eq/bucket_insert_eq specialised to String keys, calling String.beq directly instead of taking it as a parameter.

Passing a comparator is what a compiled binary pays dearly for. A gdb backtrace from a self-compile stuck in Stage 0c showed every single map probe going str_map_lookup -> alloc_closure -> GC_malloc_kind -> GC_clear_stack to build the String.beq closure, then reaching the comparison itself through apply_closure2 -> apply_closure_dispatch -> String.beq_closure_shim -- one GC allocation and an indirect call per bucket entry, for a function whose identity is known statically. The Rust host pays none of this, which is most of why that pass ran ~20x worse compiled than interpreted rather than the usual ~4x.

String because that is what every hot map in the compiler is keyed by: llvm/src/strmap.mo's str_map_* (re-exported by lang/codegen/util.mo, where they used to live) and lang/scope.mo's alias_map_*.

defHashMap.bucket_insert_str#
pub def HashMap.bucket_insert_str {V : Type} (key : String) (val : V) (bucket : List (Pair String V)) : List (Pair String V)
defHashMap.to_list#
pub def HashMap.to_list {K V : Type} (m : HashMap K V) : List (Pair K V)

Convert the map to a list of (key, value) pairs — unlike BTreeMap.to_list, in NO particular order (buckets are visited 0..15, each bucket's own chain in insertion order, which has no relationship to key order for a hash table).

defHashMap.is_empty#
pub def HashMap.is_empty {K V : Type} (m : HashMap K V) : Bool
defHashMap.merge_buckets#
pub def HashMap.merge_buckets {K V : Type} (m1 : HashMap K V) (m2 : HashMap K V) : HashMap K V

Merge two HashMaps bucket-by-bucket, WITHOUT re-hashing any key — safe specifically because both sides already used the SAME hash function to place their entries, so a key that landed in bucket i on one side always lands in bucket i on the other too. m1's entries come FIRST in each merged bucket's list, so m1 wins over m2 on a duplicate key (matches HashMap.bucket_lookup's own head-first linear scan — same "first argument wins" precedence merge_scope_data/list_append's own callers already rely on). Needs no [Hashable K, BOrd K] constraint (unlike a to_list+ refold merge through Map.insert) since it never calls Hashable.hash/BOrd.lt/BOrd.gt — just 16 List.append calls, one per bucket, however many entries each side holds. Measurably cheaper than the to_list+refold pattern this replaces in lang/module.mo's merge_scope_data (that pattern rebuilds the WHOLE combined map via one Map.insert-equivalent call per entry, re-walking/reallocating a bucket on every single insert; this does a fixed 16 bucket-pair appends regardless of N) — see AGENTS.md's performance section for the measured before/after.