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.
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.
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.
pub instance [BOrd K, BEq V] BEq (BTreeMap K V) {
def beq (a b : BTreeMap K V) : Bool := BTreeMap.beq a b
}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.
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.
pub def HashMap.bucket_of (hash : U64) : U64Compute 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.
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.
pub type HashMap K V {
map (Bucket16 (Bucket16 (List (Pair K V))))
}Hash map type: 256-bucket chaining hash table, as 16x16.
pub def HashMap.empty_buckets {K V : Type} : Bucket16 (Bucket16 (List (Pair K V)))16 empty buckets.
pub def HashMap.get_bucket {K V : Type} (b : Bucket16 (Bucket16 (List (Pair K V)))) (idx : U64) : List (Pair K V)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)))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).
pub def HashMap.bucket_lookup_str {V : Type} (key : String) (bucket : List (Pair String V)) : Option Vbucket_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_*.
pub def HashMap.bucket_insert_str {V : Type} (key : String) (val : V) (bucket : List (Pair String V)) : List (Pair String V)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).
pub def HashMap.is_empty {K V : Type} (m : HashMap K V) : Boolpub def HashMap.merge_buckets {K V : Type} (m1 : HashMap K V) (m2 : HashMap K V) : HashMap K VMerge 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.