Open and answer this issue on GitHub.
language, compiler, ready · opened 2026-10-11 · updated 2026-11-03 · 4 comments
In the self-hosting runs (#125, #558) the builders write BTreeMap/BTreeSet in every tools/*.nika file, because a collections::HashMap field did not keep its Rust type: docs/lowering-defects.md D6, docs/mitigation-hurdles.md §3, docs/import-rust-design.md decision D (#579). The owner’s direction (October 11, 2026): the compiler should be clever enough to fix the type only once all the information is there, and, for the package boundary, as with generics, both variants must be possible.
What decides a map’s Rust type today (emit_exprs.nika map_name, emit/mod.rs trusted_input/trusted_lets, contracts/trust.rs): the provenance of the unit being lowered. A trusted unit writes TrustedMap (Fx, fixed seed) for every HashMap it mentions, types and constructors alike; an untrusted unit writes std’s keyed HashMap, except a let map that never leaves its function and is filled only from trusted values (#431). Which unit’s provenance is used:
modules.rs emit_reading): the entry file’s analysis, for every file of the package. Probe: main.nika reads nothing, serve.nika reads net::Connection::read and fills a map from it. The map lowers to TrustedMap (fixed seed, attacker keys), while --trust prints untrusted, keyed for serve.nika. A hash-flooding hole, and the report and the code disagree (D7).sysroot.rs lower_tools_at → emit_std_items_against_at): each file’s own analysis, against that file alone. A method call on a value whose type another file declares cannot be resolved there, and an unresolved call counts as untrusted (D1). Probe: hm_a.nika declares pub struct HmNames { seen: HashSet[String], ids: HashMap[String, i64] } → TrustedSet/TrustedMap; hm_b.nika builds it and calls n.seen.insert("a") → HashSet::new(): rustc E0308. Without the insert, both are TrustedMap. This is D6: not whether the file builds one, but whether that file reads anything it cannot resolve.fields = ["pub counts: collections::HashMap[String, i64]"] says nothing about the hasher. Probe 1: a trusted lib with pub struct Tally, an app that reads a socket and writes lib::Tally { counts: collections::HashMap() } → a rustc error reaches the user (Expected struct HashMap<String, i64> found HashMap<_, _, RandomState>; Part III C.1). Probe 2: the same app passes socket bytes to lib::count_in(t, key) → compiles, attacker keys in a fixed-seed map.HashMap/HashSet type positions in tools/*.nika (BTreeMap/BTreeSet everywhere), 32 mentions left in the Rust of check/ and emit/, 9 TrustedMap/TrustedSet in package.rs.Rc/Arc per class of values by union-find and puts the atomic floor at every public signature, because a published artifact has already chosen. The owner’s boundary answer differs on purpose: a Nikaia package is lowered and compiled with its consumer, so Rust monomorphises a hidden parameter there. Whether Shared should follow is not decided here.ADR-010 D9, Part III 17.1 std::collections - and where keys come from, the maps row of Part III 13.5, NK1246 in C.3, one sentence in Part I 3.x (maps).
if/match) are one class and get one Rust type. A class is keyed if any key that reaches any value of it is untrusted, or it touches a barrier; otherwise fast. Decided after every file of the package is read; the order of files and which file builds or fills a map change nothing.pub function’s signature or in a pub type is a hidden type parameter of that item, one per position in declaration order. Each use fills it, inside the package and outside, as a generic’s use does.maps key per pub function: which positions are one class, and what the body puts in: either, from(p, ...), keyed. The caller joins it. Absent = keyed. It is a permission key (a wrong either lets a caller pick the fast hash for attacker keys), written by the compiler from the body only.nikaia_std::hash::Fast, nikaia_std::hash::Keyed; a pub type’s parameters default to Keyed, so Rust code that names none gets the safe map.hasher: (ADR-316 D4, not built) can fix a class to something else; two different named hashers in one class are refused, NK1246.Tests first, each in crates/nikaia/tests/map_trust.rs unless named:
main.nika reads nothing, serve.nika fills a map from net::Connection::read) lowers that map keyed, and --trust and the code agree. Replace the entry-only analysis in modules.rs emit_reading and the per-file one in sysroot.rs lower_tools_at with one analysis over all units; method calls resolve against the whole package.hm_a/hm_b) through nikaia lower-std on a scratch sysroot.fn count(m: ref HashMap[String, i64]) called with a map from a file and one from a socket: both keyed; without the socket call: both fast.trusted_input and trusted_lets in EmitState with a per-position answer; --trust lists the classes.contracts_across.rs does: lib with pub struct Tally { counts: HashMap[String, i64] }, pub fn tally_new() -> Tally, pub fn count_in(mut t: Tally, word: ref String); an app that fills it from a file gets Fast, one that fills it from a socket gets Keyed; an app that writes lib::Tally { counts: collections::HashMap() } compiles in both. Then build it: hidden parameters S: nikaia_std::hash::Seed (trait over BuildHasher + Default + Clone), default Keyed, maps made at such a position with S::default().nikaia.contracts of lib carries maps = ["t.counts: from(word)"] for count_in and maps = ["<result>.counts: either"] for tally_new; a lib function that inserts socket bytes says keyed, and the app’s map becomes keyed through it. Then write the key (Part III 13.5), sorted (ADR-005 D8).&HashMap<K, V> makes its class keyed.HmNames (default) and HmNames<nikaia_std::hash::Fast, nikaia_std::hash::Fast> compiles against the lowered tools package, whatever the other files of the package do.package.rs with its files read in reverse order.benches/brc/brc.sh) must stay at its table’s count; nikaia lower crates/nikaia-std/src/tools/ty.nika before and after one moved module switches a BTreeMap to HashMap. Record both in the benches README and here.HashMap/HashSet again where step 10 shows it counts fewer instructions and nothing iterates the map into output (ADR-005 D8). Update docs/lowering-defects.md D6 and docs/mitigation-hurdles.md §3.NK1246 is specified ahead of hasher: (ADR-316 D4); its reproduction test belongs to the commit that builds hasher:. The last commit of steps 1-11 says Fixes #N for this issue.Not decided here: whether Shared’s count (ADR-037 D8) should become a type parameter at the boundary the same way.
Related: #125, #558, #579, #431.
Generated by Claude Code
The decision is written in 943e6286 (0.0.838): ADR-010 D9, Part III 17.1 (the two paragraphs after the hasher paragraph), the maps row of Part III 13.5, NK1246 in C.3, and one sentence in Part I 4.5 (not 3.x as the body says). Notes updated: docs/mitigation-hurdles.md §3 and its ranking row, docs/import-rust-design.md decision D and its table row, docs/lowering-defects.md D6.
Corrections to the body: the last commit of steps 1-11 says Fixes #581. Step 1 is a security fix of its own (a socket read outside the entry file gets the fixed seed today) and can ship before the rest.
Generated by Claude Code
Status at 8505a0fc (0.0.848): steps 1-7 are built (package-wide trust, classes, hidden parameters, the maps ledger key, barriers). Measured (callgrind --branch-sim=yes, 200,000 rows, benches/brc/brc.sh): 1BRC 310.9 instructions and 1.70 mispredictions per row; a pub struct with a map costs the same as a private one (310.8 / 1.70); a keyed map costs 480.4 / 2.83 (+54 % instructions, +1.1 mispredictions); a pub function used with both Fast and Keyed adds 4.8 KB of text (+0.65 %). A technical review found no cheaper mechanism at run time (a keyed floor at every pub position, a run-time hasher branch, a random-seed fast hash for all maps, one answer per package each break a goal).
Still to build:
HmNames, determinism with the files read in reverse order, callgrind on lower before/after one BTreeMap to HashMap switch in the tools, then the tools use HashMap again where it counts fewer instructions and nothing iterates it into output).handle(state, request) has separate ledger lines per position (state.config: from(), state.sessions: from(request)), but an app that itself reads a socket keys state.config too. Keeping state.config Fast inside such an app needs the class-wise fill at use sites (steps 4/5 do not do it). A non-pub mention of a pub struct is filled from the package-wide answer, not its class (an untrusted package keys every pub struct’s maps; not measured how much slower).fs::map(...; trusted: false) is not implemented (NK1109), so a keyed program is made untrusted by a socket read in a test.NK1246 has no test until hasher: (ADR-316 D4) is built.Shared (ADR-037 D8) should also be a boundary type parameter is not decided.bfad5449 is not green on its own (the test a_map_the_library_hands_on_keys_the_callers_map needs 8505a0fc); the tip is.Generated by Claude Code
Status at 86db135 (0.0.970): steps 8-10 are built. Step 11 is still open, and step 12 waits for hasher:.
map_trust.rs a_rust_adapter_names_a_tools_struct_with_and_without_its_hashers lowers hm_a/hm_b (and the same with a socket file hm_c) through lower_tools_at. It checks that HmNames declares __S0/__S1: Seed = Keyed, then compiles a Rust adapter with rustc that names both tools::HmNames and tools::HmNames<Fast, Fast>.sysroot::lower_tools_files lowers the files in the order given (lower_tools_at sorts them and calls it). There are two tests. In the first, the scratch package read in reverse lowers to the same per-file sections. In the second, the compiler’s own tools package, read backwards, lowers to the same sections as read forwards (about 260 s). Only the order of the sections and the facade modules follows the order the files are read in.--branch-sim=yes, counts only):
benches/brc/brc.sh, 1,000,000 rows): 300.2 instructions and 1.58 mispredictions per row, against 300.1 / 1.61 in the old table. Every other row is within 0.8 instructions. The README table is replaced.crates/nikaia-std/src/tools/ty.nika: 593,145,538 instructions and 4,988,219 mispredictions before. After switching CheckComparable’s seen (check_compare.nika, only contains/insert) from BTreeSet to HashSet: 593,726,065 instructions (+0.10 %) and 5,020,284 mispredictions. The reason: in the tools package that set lowers to std’s keyed HashSet, not TrustedSet, because its class leaves its function (a mut parameter of a private method), so it gets the package-wide answer. The same shape in a stand-alone program lowers to TrustedSet. The switch was not committed.HashMap is fast only after the open item from the last status comment is built: the fill per class at use sites (today the package-wide flag decides a class that leaves its function). Until then the tools keep BTreeMap/BTreeSet. docs/lowering-defects.md D6 is marked built and says this.net’s io::IoError without use std::io lowers Thrown<io::IoError> with no io in scope (rustc E0433). Programs are not affected because they get the prelude. I did not fix it. It is recorded as D42 in docs/lowering-defects.md, and the test file writes use std::io.Still to build: the fill per class at use sites, then step 11 (re-measure against a fast HashSet, and update docs/mitigation-hurdles.md §3). Also step 12 (NK1246 with hasher:) and the commit with Fixes #581.
Generated by Claude Code
Step 13 added (owner, 2026-10-18): every lowered map on hashbrown directly (#434).
#434 measured TrustedMap on hashbrown instead of std’s HashMap: −3 instructions a row on 1BRC, −3.2 % on an insert-heavy program, no loss found. Std converts hashbrown’s rustc_entry into its own Entry on every entry call. Since steps 1-7 the hasher is a type parameter (Fast/Keyed), so this is one base type for every map, not a second type; ADR-327 D4 already puts Map on hashbrown. The steps and tests are in #434 (base type, everything that names std’s HashMap for a lowered map, barriers keep std’s type, measure 1BRC, insert-heavy and a Keyed map).
13 does not depend on the fill per class at use sites or on step 11, and can be built before them. Its commit says Fixes #434; Fixes #581 stays with the last of steps 1-12.
Generated by Claude Code