tur/map

(defstruct Map :heap [K V] (hamt :ptr<void>))

parameterized persistent map with key type K and value type V.

Map[K V] is a non-transparent :heap struct holding a single ptr<void> to its backing HAMT. The field is never accessed structurally (every operation is inline-C or delegates to one); it monomorphizes to a real Map__K__V so typed consumers receive a (Map__K__V *) by value.

Since: Phase TM0

(map-new [K V])

create a new empty typed map.

map-new is generic and nullary, so its K/V cannot be inferred from arguments. Annotate it at the binding site when the type is otherwise unconstrained:

(let [m (:: (map-new) (Map cstr int))] ...)

In a function whose declared return type fixes K/V, a bare (map-new) tail is enough (the return annotation pins K/V) -- see map-empty-for.

(:: (map-new) (Map int int))  ; => empty Map[int int]

Since: Phase TM0

(map-empty-for [^Hash K ^MapKey K V])

internal: an empty Map[K V] whose K/V are pinned by a sample key/value pair. Used by the hamt-of / #map{...} literal lowering, where the key/value types are known from the first literal pair but cannot be written as an annotation by the expanding macro. The k/v arguments are consumed only for type inference; the returned map is empty.

Since: Phase TMS3

(map-hamt [K V])

internal accessor for the HAMT backing store.

(map-wrap [K V])

internal constructor from a HAMT pointer.

(map-assoc-eq-o [K V])

============================================================================ Raw runtime bridges (#fx{Unsafe}-style, internal).

These carry the key already boxed into the int64 carrier (a :int, not :K) and an explicit comparator/ownership flag. They are the thin C layer the public Hash/MapKey-dispatched accessors below delegate to. The handle is typed (Map K V) so the public accessors thread K/V through them, but the carrier key is always :int. ============================================================================ map-assoc-eq-o -- raw insert/update: explicit hash, boxed carrier key, comparator and ownership flag.

(map-get-eq-o [K V])

raw lookup: explicit hash, boxed carrier key, comparator.

(map-has-eq-o? [K V])

raw existence test: explicit hash, boxed carrier key.

(map-dissoc-eq-o [K V])

raw removal: explicit hash, boxed carrier key, comparator.

(map-assoc-eq [K V])

---------------------------------------------------------------------------- Explicit hash + key-equality content API (TCE4).

Like the -eq-o family but with the key passed RAW (as :K, not a boxed carrier) and no ownership flag (owned == 0). These give direct control of the hash word, which is what a forced-collision test needs (two distinct keys sharing hash 0 stay distinct under the comparator). The public map-assoc/map-get accessors are preferred for ordinary use. ---------------------------------------------------------------------------- map-assoc-eq -- insert/update with an explicit hash and key-equality fn.

(map-assoc-eq m (cstr-hash k) k v tur-cstr-key-eq?)

Since: TCE4

(map-get-eq [K V])

look up a key using an explicit hash and key-equality fn.

(map-get-eq m (cstr-hash k) k tur-cstr-key-eq?)

Since: TCE4

(map-has-eq? [K V])

key-existence test using an explicit hash and equality fn.

(map-has-eq? m (cstr-hash k) k tur-cstr-key-eq?)  ; => true or false

Since: TCE4

(map-dissoc-eq [K V])

remove a key using an explicit hash and equality fn.

(map-dissoc-eq m (cstr-hash k) k tur-cstr-key-eq?)

Since: TCE4

(cstr-hash [s :cstr] :int)

xxHash64 of a NUL-terminated string's contents.

(cstr-hash "key")  ; => <stable content hash>

Since: TCE4

(tur-cstr-key-eq? [a :cstr b :cstr] :bool)

internal: content equality of two string keys.

(tur-int-carrier-eq? [a :int b :int] :bool)

float32-map-key-carrier-plan)

The runtime *-eq HAMT carries a key as a single int64_t word and calls the comparator through bool(*)(int64_t,int64_t). For a one-word key (:int, :bool, :cstr) the value rides that word losslessly. A :float32 / :float key does NOT: binding it to the int64_t carrier numerically converts it (1.5 -> 1), and a bool(float,float) comparator invoked through the int64_t ABI reads the wrong registers. Both bugs predate generic dispatch -- they are properties of the one-word carrier itself.

MapKey fixes the carrier per key type, at the only place that knows K concretely -- a typeclass dispatched on a K-typed argument:

mk-box : K -> int64 carrier.  One-word keys: identity.  Float keys:
         a *bit* reinterpret (memcpy of raw bytes via a union), never a
         numeric conversion, so 1.5 survives intact.
mk-cmp : K -> a carrier-ABI comparator bool(int64,int64) (returned as a
         raw function pointer).  Float comparators reinterpret each
         carrier word back to the float and compare by value, so the
         runtime's int64_t ABI is honored.

(hash key) still runs on the unboxed K via Hash[K], so the hash word is unaffected. The boxed form (mk-box) and the unbox in the comparator (mk-cmp) are chosen by the same K, so they always agree. Dispatch is resolved at compile time and the float reinterprets are inlinable, so a one-word map keeps today's representation and cost.

Scope: this covers inline scalar keys (one-word + float32 + float64). Multi-word struct/ADT keys would need a heap-boxed carrier owned by the map (a runtime-ownership change); that remains a separate follow-up. ============================================================================ tur-int-carrier-eq? -- carrier comparator for one-word integral keys.

Used for :int and :bool keys, whose carrier word IS the value, so plain integer equality on the two carrier words is the key equality.

(tur-f32-carrier-eq? [a :int b :int] :bool)

carrier comparator for :float32 keys.

Reinterprets each int64 carrier word's low 32 bits back to a float and compares by value (NaN never matches, as with =).

(tur-f64-carrier-eq? [a :int b :int] :bool)

carrier comparator for :float (float64) keys.

Reinterprets each int64 carrier word back to a double and compares by value.

(defclass MapKey [a])

key types a typed Map can carry: how to box a key and compare it.

Since: WKC (float32-map-key-carrier-plan)

(definstance MapKey [int])

one-word identity carrier; integer-equality comparator.

(definstance MapKey [bool])

one-word 0/1 carrier; integer-equality comparator.

(definstance MapKey [cstr])

pointer carrier; content-equality comparator.

(definstance MapKey [float32])

bit-reinterpret carrier; float-value comparator.

(definstance MapKey [float])

bit-reinterpret carrier (float64); double-value comparator.

(definstance MapKey [Sym])

key a map or set by a dynamically-typed value.

set-of-element-type-is-not-checked / saffron-lang-plan S6: the twin of Hash[any]. Each is? arm narrows x to its payload type and delegates to THAT type's MapKey, so an any holding "two" is boxed and compared exactly as a bare "two" (content-keyed), and an any holding 7.1 as a bare 7.1 (bit-reinterpret, value comparator). The runtime HAMT keeps a comparator PER ENTRY, which is what makes mixing them in one set sound: this is precisely how a heterogeneous set-of already behaved before it had an honest type. An unrecognised payload keys by its type name, like its hash. The Sym arm keeps keyword keys apart (pointer identity, as MapKey[Sym]); without it every keyword collapsed onto the name "Sym" (saffron-dynamic-surface-pass H4). The arms use the .mk-box method spelling on purpose: a bare mk-box resolves in the VALUE namespace, where a user (defn mk-box ...) -- a common name for a Box constructor helper -- legitimately shadows the method (TUR-W0039), and this body is elaborated in the user's program.

Since: saffron-lang-plan S6 (MapKey[any])

(definstance MapKey [any])

(tur-map-kcheck [K V])

============================================================================ The typed Map[K V] accessor surface (TMS3).

One family of accessors -- map-assoc / map-get / map-has? / map-dissoc -- works for ANY scalar key type via (Hash K) + (MapKey K): (hash key) selects the per-K hash, (mk-box key) boxes the key into the int64 carrier (a bit reinterpret for float keys, identity for one-word keys, the pointer for cstr), and (mk-cmp key) supplies a carrier-ABI comparator threaded into the runtime *-eq HAMT. For :int keys mk-box is identity and the comparator is integer =, matching an identity-keyed map; for :cstr keys distinct pointers with equal text collapse to one entry; for :float32 / :float keys the key round-trips by value. Dispatch is resolved at compile time per monomorphization.

The handle is typed Map[K V], so the type checker enforces that the key has type K and the value type V; a key/value-type mismatch is a TUR-E0001.

The accessors are MACROS, not functions. This is deliberate: a value of ANY type V (a :float that must keep its bits, a heap handle like Vec[A] or another Map, a user struct) must ride the map on the single int64 carrier word. A pure-Turmeric generic *function* would ABI-specialize its value parameter to V's concrete C type (e.g. double, Vec__int) and then clash with the int64-carrier runtime bridge. By expanding at the use site, the value flows straight into the inline-C bridge (which carries it as int64, bit-reinterpreting floats and pointers correctly), while a typed key-check (tur-map-kcheck) still enforces that the key has type K against the map's Map[K V] -- so a wrong-typed key is a TUR-E0001. Because they are macros they cannot be passed as first-class function values. ============================================================================ tur-map-kcheck -- internal: enforce key type K against a Map[K V]; returns m.

A typed identity on the map that unifies the key's type with the map's key type K. The accessor macros wrap their map argument in this so a wrong-typed key is rejected (TUR-E0001) even though the runtime dispatch goes through the type-erased int64 carrier.

(tur-wide-byval? [V])

insert or update a key/value pair; returns a new map.

(map-assoc (:: (map-new) (Map cstr int)) "name" 1)  ; => Map {"name" -> 1}
(map-assoc (:: (map-new) (Map int int)) 42 100)     ; => Map {42 -> 100}

Since: multiword-value-box-lifecycle

(tur-rc-value? [V])

1 if V is an rc<T>, else 0. The refcount-side twin of tur-wide-byval?: the compiled backend folds it to a constant per monomorphization (emit_expr.c), and this pure-Turmeric fallback body returns 0 for the interpreter (where an rc value is not carrier-erased) and for any call the backend does not intercept. map-assoc threads it as bit 2 of the owned flag so a Map[K rc<T>] takes a strong reference on insert and releases it when the entry dies. Bits 1 and 2 are mutually exclusive -- a value is either a by-value box or an rc handle, never both.

Since: collections-cannot-hold-rc-values (map side, step c)

(map-assoc [m k v])

(map-get [m k])

look up a key; returns the value or 0 (none) if absent.

(map-get m "name")  ; => value or 0

Since: Phase TMS3 (macro accessor; was map-get-g; GHE3)

(map-has? [m k])

check whether a key exists in the map.

(map-has? m "name")  ; => true or false

Since: Phase TMS3 (macro accessor; was map-has-g?; GHE3)

(map-dissoc [m k])

remove a key from the map; returns a new map.

(map-dissoc m "name")  ; => map without "name"

Since: Phase TMS3 (macro accessor; was map-dissoc-g; GHE3)

(map-count [K V])

return the number of entries in the map.

(map-count my-map)  ; => 3

Since: Phase TM0

(map-merge [K V])

merge two maps; values from b win on key collision.

(map-merge map-a map-b)  ; => merged map

Since: Phase TM0

(map-free [K V])

free the Map wrapper (does not free HAMT; use map-free-all for that).

(map-free my-map)

Since: Phase TM0

(map-eq-raw? [V])

compare two maps for structural equality using a value comparator.

(map-eq? ma mb (fn [a b] (= a b)))  ; => true

Since: Phase TM0

(map-eq? [K V W])

typed structural equality over Map[K V] (delegates to map-eq-raw?).

Since: Phase TM0 (typed surface: TMS3)

(map-eq-raw-k? [V])

like map-eq-raw? but compares keys with an explicit carrier comparator (tur_hamt_get_eq) instead of identity. Threading the MapKey[K] comparator here is what makes structural equality content-correct for :cstr keys (distinct pointers with equal text match).

(map-eq-k? [K V W])

structural equality over Map[K V] with an explicit key comparator (and value comparator). This is the target of the compiler's content-keyed .eq? dispatch synthesis: at a concrete call site it threads the MapKey[K] comparator resolved for the concrete key type -- for :cstr keys via (mk-cmp (:: 0 K)), for all-:int-field struct keys via (mk-cmp (make-struct K 0 ...)) -- so keys equal by content but stored under distinct pointers/boxes compare equal.

(map-eq-dynamic [V])

structural equality using the value type's Eq instance. map-eq-dynamic -- internal: structural equality using each map's stamped key comparator (GDE3). val-cmp compares values as int64 carriers.

The key comparator is read from the first map's runtime stamp (set by map-assoc / map-dissoc via tur_hamt_set_eq). For maps built without an explicit comparator (identity keys) the stamp is NULL and pointer identity is used -- which is correct for :int keys.

(map-iter-cur-val-as [V])

typed read of an iter box's current value.

The HAMT iter API hands out ptr<void> for values; this typed accessor bridges that pointer back to V at the carrier level (a single inline-C ascription, no work). Mirrors mutmap-slot-value's shape so the pure-Turmeric map-eq-loop body can compare V-typed values directly.

(map-get-dynamic-as [V])

typed lookup against m2's hamt, threading m1's stamped key comparator so content-keyed maps (e.g. cstr keys) stay content-correct. Returns V (cast at the carrier level). The pure-Turmeric loop calls this *after* hamt/has-dynamic? has confirmed the key is present, so the result is always a live value.

(map-eq-loop [K V])

pure-Turmeric structural-equality walk over m1's HAMT.

Path A specializes this per (K V) at the Eq [Map] dispatch site; the self-tail-recursive spec lowers to a goto loop (TCO-in-ABI-specs, same gate as vec-eq-loop / mutmap-eq-loop), so deep iteration over large maps runs in constant stack. For each live (h, k, v) of m1 the matching key is looked up in m2's hamt (via hamt/has-dynamic? / map-get-dynamic-as V, threading m1's stamped key comparator so cstr and other content-keyed maps stay content-correct) and the values are compared by val-cmp.

Since: Phase TCO-Eq-MapSet

(map-eq-driver [K V])

allocate the iter box, run map-eq-loop, free.

Split out from the Eq [Map] instance so the instance body is a single expression and the (alloc, loop, destroy) sequence is reused.

Since: Phase TCO-Eq-MapSet

(definstance Eq [Map])

(map-assoc-consuming__ [m k v])

internal: assoc, then free the map assoc'd INTO.

map-literal-leaks-its-intermediate-maps. A HAMT is persistent, so every map-assoc mallocs a fresh {void* hamt} carrier box and returns it. In an N-entry literal that is N+1 boxes of which the author holds only the LAST, so #map{:a 1 :b 2 :c 3} leaked 3 boxes and the generations they retain -- 1080 bytes in 11 allocations -- with map-free called.

This is safe ONLY where the input map is owned by the expression that produced it, which is why it lives here and not in map-assoc: the caller of map-assoc generally holds its argument and must keep it. hamt-of seeds the chain with a fresh (map-empty-for ...) and every later input is a previous step's result, so every generation in the chain is the chain's own.

Freeing the previous generation does not disturb the new one: tur_hamt_free is refcount-safe under structural sharing (it decrements each node and frees only at zero), which is the same guarantee map-free's own body documents.

(hamt-assoc-each__ [^syntax m & ^syntax kvs])

internal helper for the hamt-of macro.

Threads (map-assoc m k v) over the kv-pairs in xs, returning the final map. Recursive: each step wraps the accumulator in one more map-assoc, so the last pair wins on duplicate keys. Each step also FREES the map it assoc'd into -- see map-assoc-consuming__ for why that is sound here and not in map-assoc itself.

Every parameter of this family (hamt-of, hamt-homog-chain__, this one) is ^syntax: bound as the raw argument form. A plain parameter is substituted into the body before the compile-time evaluation, so m (or a spliced kvs) holding an unannotated lambda value was EVALUATED at compile time and #map{"add" (fn [a b] (+ a b))} failed "compile-time macro evaluation expected a form value".

(tur-map-homog__ [A])

internal: compile-time homogeneity check (see vec.tur).

Both parameters share one type variable, so a call with two differently-typed arguments is a TUR-E0001 at elaboration. No-op body, fixed arity (no allocation).

(hamt-homog-chain__ [& ^syntax kvs])

internal: enforce homogeneous keys and values.

kvs is k0 v0 k1 v1 ... Chains tur-map-homog__ over adjacent keys and adjacent values so all keys unify to one type and all values to another.

(hamt-of [& ^syntax kvs])

variadic Map literal: alternating key/value arguments.

(hamt-of)              ; => empty Map (annotate at the binding site)
(hamt-of 1 10 2 20)    ; => Map {1 -> 10, 2 -> 20}
(hamt-of "a" 1 "b" 2)  ; => Map {"a" -> 1, "b" -> 2}, content-keyed

(-Xdata-literals).  Writing #map{:a 1 :b 2} is preferred over calling
hamt-of directly.  A non-empty literal is seeded from a value-pinned
empty (map-empty-for) so the key/value types flow from the first pair;
an empty (hamt-of) yields a bare (map-new) that must be annotated by the
surrounding context.

Since: DL1 (data-literals-plan); typed surface: TMS3