pub const COLLECTIONS: &str = "//! Growable vectors, hash maps and hash sets.\n//!\n//! `Vec` is a list of values that grows as they are pushed, and `VecIter`\n//! walks one in order. `Map` maps keys to values, and `Set` holds values\n//! without repeats; both need a key or value type that implements `Hash` and\n//! `Eq`. Every module sees these types without an import, and a module\'s own\n//! definition of one of these names shadows the one here.\n//!\n//! The three collections are shared, not copied: assigning one to another\n//! binding, or passing it to a function, gives a second name for the same\n//! collection, and a change made through either is seen through both. A\n//! method that changes a collection takes `mut self`, and needs a mutable\n//! receiver, such as one held in a `mut` binding.\n//!\n//! A `Vec`, a `Map` and a `Set` in use:\n//!\n//! ```\n//! let mut scores: Vec<Int> = Vec::new()\n//! scores.push(90)\n//! scores.push(75)\n//! assert_eq(scores.len(), 2)\n//! assert(scores.get(5).is_none(), \"an index past the end gives None\")\n//!\n//! let mut ages: Map<String, Int> = Map::new()\n//! ages.insert(\"ada\", 36)\n//! assert_eq(ages.get(\"ada\").unwrap(), 36)\n//! assert(!ages.contains_key(\"alan\"), \"alan was never inserted\")\n//!\n//! let mut seen: Set<String> = Set::new()\n//! assert(seen.insert(\"nova\"), \"the first insert adds the value\")\n//! assert(!seen.insert(\"nova\"), \"a repeat is not added again\")\n//! assert_eq(seen.len(), 1)\n//! ```\n\n// Nova standard library \u{2014} collections.\n//\n// Compiled as an implicit module and glob-imported into every user module, so\n// these names need no `import`. A user definition of the same name shadows the\n// one here (see docs/adr/0004-stdlib-compile-model.md).\n//\n// `Vec` grows by allocating a larger `[T]` and reassigning the field: the record\n// object\'s address never changes and the array\'s only referent is that field, so\n// the conservative non-moving collector needs no special handling.\n\n/// A list of values of type `T`, indexed from 0, that grows as values are\n/// pushed.\n///\n/// `get` returns `None` for an index out of range, where `set` panics.\n/// Assigning a `Vec`, or passing it to a function, shares it rather than\n/// copying it.\n///\n/// A `Vec` is shared, not copied, when it is assigned:\n///\n/// ```\n/// let mut a: Vec<Int> = Vec::new()\n/// a.push(1)\n///\n/// // Assigning a Vec shares it: `b` is a second name for the same vector.\n/// let mut b = a\n/// b.push(2)\n/// assert_eq(a.len(), 2)\n///\n/// // For an independent copy, build a new Vec from the values.\n/// let mut copy: Vec<Int> = Vec::new()\n/// for x in a.iter() { copy.push(x) }\n/// copy.push(3)\n/// assert_eq(a.len(), 2)\n/// assert_eq(copy.len(), 3)\n/// ```\npub record Vec<T> { len: Int, data: [T] }\n\nimpl<T> Vec<T> {\n // An empty vector. No storage is allocated until the first `push`.\n /// Returns an empty vector.\n pub fn new() -> Vec<T> { Vec { len: 0, data: [] } }\n\n /// Returns the number of values in the vector.\n pub fn len(self) -> Int { self.len }\n\n /// Returns `true` if the vector holds no values.\n pub fn is_empty(self) -> Bool { self.len == 0 }\n\n // Append `x`, growing if full.\n //\n // Growth allocates `[x; newcap]` \u{2014} using the pushed element as the filler,\n // so no slot is ever uninitialized and no `Default` bound is needed \u{2014} then\n // copies the existing elements back. Slot `self.len` is then already `x`,\n // so the append needs no further store on the growth path.\n /// Appends `x` to the end of the vector, growing its storage when it is\n /// full.\n pub fn push(mut self, x: T) {\n if self.len == self.data.len() {\n let newcap = if self.len == 0 { 4 } else { self.len * 2 }\n let mut grown = [x; newcap]\n for i in 0..self.len { grown[i] = self.data[i] }\n self.data = grown\n } else {\n self.data[self.len] = x\n }\n self.len = self.len + 1\n }\n\n /// Removes the last value and returns it, or returns `None` if the vector\n /// is empty.\n pub fn pop(mut self) -> Option<T> {\n if self.len == 0 {\n None\n } else {\n let last = self.data[self.len - 1]\n self.len = self.len - 1\n Some(last)\n }\n }\n\n /// Returns the value at index `i`, or `None` if `i` is negative or not\n /// less than `len()`.\n pub fn get(self, i: Int) -> Option<T> {\n if i < 0 { None } else { if i >= self.len { None } else { Some(self.data[i]) } }\n }\n\n /// Replaces the value at index `i` with `v`.\n ///\n /// Panics if `i` is negative or not less than `len()`: `set` never adds a\n /// value, as `push` does.\n pub fn set(mut self, i: Int, v: T) {\n if i < 0 { panic(\"Vec::set index out of range\") }\n if i >= self.len { panic(\"Vec::set index out of range\") }\n self.data[i] = v\n }\n\n /// Removes every value, leaving the vector empty. It keeps its storage for\n /// the values pushed next.\n pub fn clear(mut self) { self.len = 0 }\n\n // A cursor over this vector\'s elements, starting at index 0. See `VecIter`\n // below for what the cursor shares with this vector.\n //\n // Deliberately in this existing `impl<T> Vec<T>` block rather than a second\n // inherent impl on `Vec<T>`: two inherent impls on one type is a\n // configuration nothing in std or the test suite exercises, and `std/strings`\n // avoided it for the same reason.\n /// Returns an iterator over the vector\'s values, from index 0 up.\n ///\n /// The iterator shares the vector rather than copying it, so it sees\n /// changes made while it runs: a value pushed onto the vector is yielded\n /// too, even one pushed after the iterator has returned `None`.\n pub fn iter(self) -> VecIter<T> { VecIter { v: self, i: 0 } }\n}\n\n// A cursor over a `Vec<T>`: the vector, plus the next index to yield.\n//\n// The vector is held by value, but records are heap objects passed by pointer,\n// so this **shares** the caller\'s storage rather than copying it \u{2014} a `push`\n// during iteration is visible to the iterator, and an element appended after\n// the iterator has already answered `None` is still yielded by the next call.\n// That is the same alias-visibility the whole module has (see the header); it is\n// documented rather than prevented, because preventing it needs borrow tracking\n// the language does not have. `an_exhausted_vec_iterator_does_not_advance_its_cursor`\n// in `crates/nova-cli/tests/run_tests.rs` pins it, so it is a property and not\n// an accident.\n//\n// As with `Map` and `Set` above, the `Iterator` contract lives on the `impl`\n// below, not on this record\'s generic parameter. A bound in that position is no\n// longer `E0900` \u{2014} Phase 2.2d accepts it as a **resolution scope** so a field\n// type may name a projection on the parameter (ADR 0007 \u{a7}1) \u{2014} but it would buy\n// nothing here: `v: Vec<T>` and `i: Int` name no projection, so `T` needs no\n// bound to be convertible, and a bound in that position is not enforced at\n// construction. `std/core`\'s `MapIter`/`FilterIter` are the records that do\n// need one.\n/// An iterator over a `Vec`\'s values, in order.\n///\n/// `Vec::iter` returns one. It shares the vector rather than copying it, so a\n/// value pushed onto the vector is yielded too, even after the iterator has\n/// returned `None`.\npub record VecIter<T> { v: Vec<T>, i: Int }\n\nimpl<T> Iterator for VecIter<T> {\n // Bound to the impl\'s **own** parameter, not to a primitive. That is what\n // makes every projection through this impl go through `subst`, and so what\n // makes `VecIter<Int>` and `VecIter<String>` resolve `Item` differently\n // instead of sharing one cached answer.\n type Item = T\n\n // Written `Option<T>` rather than echoing the trait\'s `Option<Self::Item>`.\n // Both spellings are accepted (conformance normalizes each side before\n // comparing); the concrete one is chosen here because it reads as the\n // answer to \"what does this yield\" rather than restating the question.\n fn next(mut self) -> Option<T> {\n // Not a bounds check \u{2014} `Vec::get` already returns `None` out of range,\n // so this guard is redundant for safety. What it buys is that `i` stops\n // at `len` instead of running away past it, which is why relaxing `>=`\n // to `>` is not the equivalent mutation it looks like.\n if self.i >= self.v.len() { return None }\n let x = self.v.get(self.i)\n self.i = self.i + 1\n x\n }\n}\n\n// A hash map with open addressing and linear probing.\n//\n// Capacity is a power of two, so a bucket index is `hash & (cap - 1)` \u{2014} never\n// `hash % cap`. A hash may be negative (`mix64` spans the whole `Int` range and\n// `str_hash` reinterprets an unsigned 64-bit result), and `%` inherits that\n// sign while `&` with a positive mask does not. The high bits are not read at\n// all: Nova\'s `>>` is arithmetic with no `>>>`, so a negative hash\n// sign-extends. See the masking rule on `pub trait Hash` in std/core.\n//\n// A `String`, `Int`, `Bool` or `Char` key\'s hash is SEEDED ONCE PER PROCESS \u{2014}\n// `String` from `nova_rt_str_hash`\'s draw and the other three from\n// `nova_rt_int_hash_seed`\'s, which is a separate draw \u{2014} so which bucket a given\n// key lands in is not a property of the program text: two runs of the same\n// program, inserting the same keys in the same order, build different tables.\n// Lookup and `len` do not change \u{2014} every probe in a run uses the run\'s own\n// seed, and `len` counts live entries whatever the layout \u{2014} but what a caller\n// can OBSERVE about layout can vary run to run. `keys()` order is the channel\n// a caller is most likely to notice (see its own note below); the `keys`,\n// `vals` and `state` fields are reachable directly and carry the same\n// variation, which is what a fixture reading them is reading.\n//\n// GROWTH IS NOT ON THAT UNCHANGED LIST. The trigger in `insert` reads `used`,\n// which counts tombstones as well as occupied slots, and an insert that reuses a\n// tombstone leaves `used` where it was while one taking a fresh slot raises it\n// (see \"A reused tombstone was already counted in `used`\" below). Which of the\n// two happens depends on the probe path, so a map with a seeded key type that\n// holds tombstones can reach a different capacity on different runs of the same\n// program. Checked in `tests/runtime/collections.nova`, which a grep for\n// `state.len()` across `tests/runtime/*.nova` matches and no sibling does: its\n// `String`-keyed maps `sm` and `sb` never remove anything, so `sb`\'s printed\n// `cap=64` follows from its 30 insertions alone; every `.remove(` in that file\n// passes an `Int` or a `Key`; and its `Key` impl is `self.id`, which reaches no\n// seeded hash. Re-run that grep rather than trusting this sentence.\n//\n// The `Int` case there survives for a narrower reason than the `Key` one, and\n// it is worth stating because the reason is not \"`Int` is unseeded\" any more.\n// Its `Map<Int, Int>` removes one key and then reinserts that same key while\n// printing a capacity. The table holds exactly one tombstone at that point \u{2014}\n// the removed key\'s own former slot, which lies on that key\'s own probe path \u{2014}\n// so `insert`\'s `first_free` is that slot at every seed, the reinsert reuses\n// it, and `used` and the capacity cannot move. A fixture that removed one key\n// and then inserted a DIFFERENT one before printing a capacity would have no\n// such argument.\n//\n// A key of a user type is stable only while its own `Hash` impl reaches no\n// seeded hash: one `str_hash` call, or one `.hash()` on an `Int`, `Bool` or\n// `Char` field, anywhere inside that impl carries a per-process seed into the\n// result, and the layout varies with it. The seeding lives in the runtime at\n// `nova_rt_str_hash` and `nova_rt_int_hash_seed`, which document what it buys\n// and what it does not; neither hash is collision-resistant either way.\n//\n// The three arrays are allocated together on the first insert, using the\n// inserted key and value as fillers, so no slot is ever uninitialized and no\n// `Default` bound is needed. `state` is filled with 0, which is exactly the\n// \"empty\" tag, so a fresh table is empty by construction. Slot states are\n// `0` empty, `1` occupied, `2` tombstone.\n//\n// `len` counts live entries only. `used` counts occupied *plus* tombstones and\n// is what the load threshold reads, so a remove-heavy workload cannot degrade\n// into an all-tombstone scan.\n//\n// The `K: Hash + Eq` contract lives on the `impl` below, not on this record\'s\n// own generic parameters. `record Map<K: Hash + Eq, V>` does compile as of\n// Phase 2.2d \u{2014} a bound on a *record*\'s type parameter is accepted as a\n// **resolution scope**, so that a field type may name a projection on the\n// parameter (ADR 0007 \u{a7}1). What it is not is a **constraint**: it is not\n// checked when the record is built, because `nova-hir`\'s `RecordType` keeps\n// only a generic count and `nova-mir`\'s `mono` checks bounds solely against a\n// function\'s own `bounds`, so that position has no way to enforce anything.\n// (That mechanism is exactly what ADR 0007\'s \"why it is not enforced\" cites.)\n// Writing the bound here would therefore be decoration: no field of `Map`\n// names a projection, so nothing needs resolving, and the bound would promise\n// a check it does not perform. On the impl it is real: instantiating any\n// method with a key that is not `Hash + Eq` is E0013 at monomorphization,\n// which is pinned by `map_key_without_hash_reports_e0013` in nova-mir\'s\n// lowering tests.\n/// A hash map from keys of type `K` to values of type `V`.\n///\n/// Its methods need a key type that implements `Hash` and `Eq`, and keys\n/// equal by `eq` must have the same hash. Assigning a `Map`, or passing it to\n/// a function, shares it rather than copying it.\npub record Map<K, V> { len: Int, used: Int, keys: [K], vals: [V], state: [Int] }\n\nimpl<K: Hash + Eq, V> Map<K, V> {\n // An empty map. No storage is allocated until the first `insert`.\n /// Returns an empty map.\n pub fn new() -> Map<K, V> { Map { len: 0, used: 0, keys: [], vals: [], state: [] } }\n\n // Number of live entries; unaffected by tombstones.\n /// Returns the number of entries in the map.\n pub fn len(self) -> Int { self.len }\n\n /// Returns `true` if the map holds no entries.\n pub fn is_empty(self) -> Bool { self.len == 0 }\n\n // Bucket for `k` in a table of capacity `cap` (a power of two). `cap` must\n // be positive: at `cap == 0` the mask would be `-1` and the result the raw\n // hash, so every caller checks for the unallocated table first.\n fn slot_of(self, k: K, cap: Int) -> Int { k.hash() & (cap - 1) }\n\n // Insert, returning the previous value for `k` if there was one.\n //\n // The probe never stops at a tombstone: it runs on to either `k` itself (a\n // replacement) or an empty slot (a genuine absence), and only then stores\n // into the *first* tombstone it passed. Stopping early would let a second\n // copy of `k` appear behind the tombstone; not reusing the tombstone at all\n // would let a churn workload grow without bound.\n /// Maps `k` to `v`, and returns the value `k` mapped to before, or `None`\n /// if `k` was not in the map.\n ///\n /// If `k` was in the map, its entry keeps the key it had and takes `v`.\n pub fn insert(mut self, k: K, v: V) -> Option<V> {\n if self.state.len() == 0 {\n self.keys = [k; 8]\n self.vals = [v; 8]\n self.state = [0; 8]\n } else {\n // Grow above 3/4 load, counting tombstones.\n if (self.used + 1) * 4 > self.state.len() * 3 { self.grow(k, v) }\n }\n // After that check `used + 1 <= cap * 3 / 4 < cap`, so at least one slot\n // is still empty and the scan below always terminates at `st == 0`\n // before `probes` runs out. The `panic` is unreachable.\n let cap = self.state.len()\n let mut i = self.slot_of(k, cap)\n let mut first_free = -1\n let mut probes = 0\n while probes < cap {\n let st = self.state[i]\n if st == 0 {\n let at = if first_free >= 0 { first_free } else { i }\n self.keys[at] = k\n self.vals[at] = v\n self.state[at] = 1\n self.len = self.len + 1\n // A reused tombstone was already counted in `used`.\n if first_free < 0 { self.used = self.used + 1 }\n return None\n }\n if st == 1 {\n if self.keys[i].eq(k) {\n let old = self.vals[i]\n self.vals[i] = v\n return Some(old)\n }\n } else {\n if first_free < 0 { first_free = i }\n }\n i = (i + 1) & (cap - 1)\n probes = probes + 1\n }\n panic(\"Map::insert found no free slot\")\n }\n\n // The slot index of a live entry for `k`, or `-1` if there is none. Shared\n // by `get` and `remove`, which differ only in what they do with the slot\n // once found \u{2014} `get` reads it, `remove` writes a tombstone into it \u{2014} so\n // this scan now lives in one place instead of the two separate copies\n // `get` and `remove` used to carry. `insert` (above) cannot share it: it\n // has to track the first tombstone it passes (`first_free`) so a fresh\n // key reuses that slot, and must keep scanning past a tombstone to tell a\n // replacement (the key turns up further on) from a genuine insertion (an\n // empty slot reached with no match) \u{2014} a plain lookup needs neither.\n //\n // Only an empty slot ends the chain; a tombstone is walked past, so a key\n // inserted past a tombstone stays reachable \u{2014} removing from the middle of\n // a chain must not break the chain for keys further along it.\n fn find(self, k: K) -> Int {\n let cap = self.state.len()\n // Not what keeps this safe from indexing anything bad \u{2014} at `cap == 0`\n // the loop below never executes regardless, since `probes < cap` is\n // false from the start. What this guard keeps true is `slot_of`\'s own\n // precondition (see its comment above): every caller checks for the\n // unallocated table first, and without this line `find` would call\n // `slot_of(k, 0)` and break that contract, even though nothing\n // downstream happens to depend on it today.\n if cap == 0 { return -1 }\n let mut i = self.slot_of(k, cap)\n let mut probes = 0\n while probes < cap {\n let st = self.state[i]\n if st == 0 { return -1 }\n if st == 1 { if self.keys[i].eq(k) { return i } }\n i = (i + 1) & (cap - 1)\n probes = probes + 1\n }\n // Unreachable, for the same reason `insert`\'s trailing `panic` is\n // (see its comment above): the 3/4 load threshold caps `used` at 6 of\n // 8 (or the equivalent fraction at any capacity), so at least two\n // slots are always empty and the scan above always returns at\n // `st == 0` before `probes` runs out. Kept as `return -1` rather than\n // a `panic` \u{2014} unlike `insert`, `find` has a safe fallback: an absent\n // key is an ordinary result, not a corrupted table.\n //\n // Not a bare trailing `-1`: a line starting with `-` right after a\n // `}`-closed block is absorbed as binary subtraction against the\n // `while` above (which types `Unit`), not read as a fresh statement \u{2014}\n // the same trap `tests/runtime/collections.nova` binds `miss` to\n // avoid. `return` makes this an unambiguous statement.\n return -1\n }\n\n /// Returns the value `k` maps to, or `None` if `k` is not in the map.\n ///\n /// Telling a missing key from a present one:\n ///\n /// ```\n /// let mut stock: Map<String, Int> = Map::new()\n /// stock.insert(\"apples\", 3)\n ///\n /// // `get` returns an `Option`: `None` for a key that is not in the map.\n /// let pears = match stock.get(\"pears\") {\n /// Some(n) => n\n /// None => 0\n /// }\n /// assert_eq(pears, 0)\n /// assert_eq(stock.get(\"apples\").unwrap_or(0), 3)\n ///\n /// // `insert` returns the value the key had before, if any.\n /// assert_eq(stock.insert(\"apples\", 5).unwrap(), 3)\n /// assert(stock.insert(\"pears\", 1).is_none(), \"pears is new\")\n /// assert_eq(stock.len(), 2)\n /// ```\n pub fn get(self, k: K) -> Option<V> {\n let i = self.find(k)\n if i < 0 { None } else { Some(self.vals[i]) }\n }\n\n /// Returns `true` if `k` is in the map.\n pub fn contains_key(self, k: K) -> Bool {\n match self.get(k) {\n Some(_) => true\n None => false\n }\n }\n\n // Remove `k`, leaving a tombstone so later probes still reach entries that\n // were inserted past this slot. `len` drops; `used` does not, because the\n // slot is still unusable to a probe walking through it.\n /// Removes the entry for `k` and returns its value, or returns `None` if\n /// `k` was not in the map.\n pub fn remove(mut self, k: K) -> Option<V> {\n let i = self.find(k)\n if i < 0 {\n None\n } else {\n let old = self.vals[i]\n self.state[i] = 2\n self.len = self.len - 1\n Some(old)\n }\n }\n\n // The live keys, in table order. `state[j]` is 1 for occupied, 2 for a\n // tombstone and 0 for empty, so this is the same walk `grow` already does\n // to find the entries worth reinserting.\n //\n // The `[fill; n]` FORM is forced rather than stylistic: the AST has\n // exactly two array-construction nodes, and a length known only at run\n // time needs the repeat form, which needs a value in hand -- Nova has no\n // null. `Vec::push` grows by the same manoeuvre.\n //\n // The five-line SEARCH for a live slot below is NOT forced, and this\n // comment used to read as if it were. No slot is ever uninitialized --\n // the record\'s own header note and `grow` below both state that\n // invariant -- so `self.keys[0]` would seed the array just as well, live\n // or not, and the collecting walk overwrites all `self.len` slots either\n // way. The search is removable with no behaviour any test can observe;\n // it is kept so the seed is visibly a value this map actually holds.\n //\n // Table order is deliberately NOT insertion order, and no caller should\n // assume it is. The strongest true statement is that KEYS() ORDER IS NOT A\n // FUNCTION OF THE KEY SET ALONE. Hash order alone reverses insertion order\n // with NO GROWTH AT ALL -- measured: inserting `\"a\"`, `\"c\"`, `\"e\"` into a\n // fresh map returns `\"e\"`, `\"c\"`, `\"a\"`, three entries in a cap-8 table\n // that never reaches the 3/4 threshold -- and a `grow` then reinserts every\n // entry and can reorder them again on top of that. Naming only `grow`\n // would let a reader infer that a map which never grows preserves\n // insertion order, and that inference is false.\n //\n // FOR A SEEDED KEY TYPE THERE IS NOW A STRONGER STATEMENT, and it is a\n // change in observable behaviour rather than a restatement of the above.\n // The order used to be fixed by the key set and the insertion sequence\n // together, so one unchanged binary run twice returned the same order both\n // times; the per-process hash seed (see the record header above) means it\n // CAN DIFFER BETWEEN RUNS of that same binary. Not must: a different seed\n // may land on the same layout, and a one-key map has only one order to\n // return. So a caller must not treat one observed order as reproducible,\n // and a test or a golden that pins more than one key\'s order is pinning a\n // seed it does not control -- sort, or assert per key. This covers `String`\n // keys and, since `int_hash_seed` reached the primitive impls, `Int`, `Bool`\n // and `Char` keys as well. What is left outside it is a user `Hash` impl\n // that reaches no seeded hash, for which the paragraph above covers the\n // whole of it.\n //\n // One consequence for the paragraph above: its `\"e\"`, `\"c\"`, `\"a\"` was\n // measured when the hash was unseeded. What it demonstrates is intact and\n // is the reason it is there -- no growth is needed to reorder, so a\n // never-growing map does not preserve insertion order -- but that exact\n // sequence is not reproducible now. Read it as an instance of the property,\n // not as an order to expect from those three keys.\n /// Returns the map\'s keys, as an array with one element per entry.\n ///\n /// Their order is unspecified: it need not be the order the keys were\n /// inserted in, and it can change from one run of a program to the next.\n pub fn keys(self) -> [K] {\n if self.len == 0 { return [] }\n let cap = self.state.len()\n let mut seed = 0\n let mut i = 0\n while i < cap {\n if self.state[i] == 1 {\n seed = i\n i = cap\n } else {\n i = i + 1\n }\n }\n let mut out = [self.keys[seed]; self.len]\n let mut w = 0\n let mut j = 0\n while j < cap {\n if self.state[j] == 1 {\n out[w] = self.keys[j]\n w = w + 1\n }\n j = j + 1\n }\n out\n }\n\n // Double the capacity and reinsert the live entries, which is also what\n // clears the tombstones. `fk`/`fv` are fillers for the fresh arrays, so no\n // slot is uninitialized; `state`\'s 0 filler makes the new table empty.\n //\n // Reached only from `insert`\'s pre-check, and the reinserts cannot re-enter\n // it: `used` is reset to 0 and at most `oldcap` live entries go back in,\n // while the new threshold needs `used + 1 > newcap * 3 / 4`, i.e. more than\n // `1.5 * oldcap`. So the nesting is exactly one level deep.\n //\n // GC: this is *not* safe for the reason `Vec::push` is. `push` finishes the\n // new array before reassigning the field, so the old one stays reachable\n // through the record the whole time. Here `self.keys` is reassigned on the\n // very next line, and from then on `oldkeys` is live only in this frame\'s\n // locals while two more `[_; newcap]` allocations and one allocation per\n // reinsert all run \u{2014} every one of them a collection point. It is safe\n // because the collector scans the stack from the allocating frame up to the\n // thread base *plus* the callee-saved registers `gc_stack.c` spills\n // there, and the ABI leaves anything live across a call in one of those two\n // places; marking is range-based, so a derived element pointer counts too.\n // That is a property of the calling convention, not of the record/buffer\n // shape, which is why this window is what makes `NOVA_GC_STRESS=1`\n // load-bearing on `tests/runtime/collections.nova` rather than\n // belt-and-braces \u{2014} a missed root here loses entries silently instead of\n // crashing.\n fn grow(mut self, fk: K, fv: V) {\n let oldcap = self.state.len()\n let newcap = oldcap * 2\n let oldkeys = self.keys\n let oldvals = self.vals\n let oldstate = self.state\n self.keys = [fk; newcap]\n self.vals = [fv; newcap]\n self.state = [0; newcap]\n self.len = 0\n self.used = 0\n for j in 0..oldcap {\n if oldstate[j] == 1 {\n // Reinserting a key the fresh table cannot already hold always\n // returns `None`, so the result is discarded.\n let _ = self.insert(oldkeys[j], oldvals[j])\n }\n }\n }\n}\n\n// A hash set, backed by a `Map` with a placeholder value. Reusing `Map` keeps\n// the probing, tombstone and growth logic in exactly one place.\n//\n// As with `Map` (see the note above it), the `T: Hash + Eq` contract lives on\n// the `impl`, not on this record\'s generic parameter. A bound there is legal as\n// of Phase 2.2d but is a resolution scope rather than a constraint (ADR 0007\n// \u{a7}1), and `map: Map<T, Bool>` names no projection, so it would resolve nothing\n// and enforce nothing.\n/// A hash set of values of type `T`, each held once.\n///\n/// Its methods need a value type that implements `Hash` and `Eq`, and values\n/// equal by `eq` must have the same hash. Assigning a `Set`, or passing it to\n/// a function, shares it rather than copying it.\npub record Set<T> { map: Map<T, Bool> }\n\nimpl<T: Hash + Eq> Set<T> {\n // An empty set. No storage is allocated until the first `insert`.\n /// Returns an empty set.\n pub fn new() -> Set<T> { Set { map: Map::new() } }\n\n // Number of elements; unaffected by tombstones (see `Map::len`).\n /// Returns the number of values in the set.\n pub fn len(self) -> Int { self.map.len() }\n\n /// Returns `true` if the set holds no values.\n pub fn is_empty(self) -> Bool { self.map.is_empty() }\n\n // Add `v`, returning whether it was newly added. `Map::insert` returns\n // `Some(old)` when `v` was already a key, so \"newly added\" is exactly the\n // `None` case \u{2014} the inverse of what `Map::insert` reports.\n /// Adds `v` to the set, and returns `true` if it was not there before.\n ///\n /// If an equal value was there, the set keeps that one and returns\n /// `false`.\n pub fn insert(mut self, v: T) -> Bool {\n match self.map.insert(v, true) {\n Some(_) => false\n None => true\n }\n }\n\n /// Returns `true` if `v` is in the set.\n pub fn contains(self, v: T) -> Bool { self.map.contains_key(v) }\n\n // Remove `v`, returning whether it was present. `Map::remove` returns\n // `Some(old)` when `v` was there, so \"was present\" is exactly the\n // `Some` case \u{2014} the inverse of what `Map::remove` reports.\n /// Removes `v` from the set, and returns `true` if it was there.\n pub fn remove(mut self, v: T) -> Bool {\n match self.map.remove(v) {\n Some(_) => true\n None => false\n }\n }\n}\n";Expand description
std/collections/lib.nova.