//! The types and traits every module sees without an import.
//!
//! `Option` holds a value that may be absent, `Result` the outcome of an
//! operation that can fail, and `Ordering` the result of a comparison. The
//! traits `Display`, `Debug`, `Eq`, `Ord`, `Clone`, `Default` and `Hash`
//! come with impls for `Int`, `Float`, `Bool`, `Char` and `String`, except
//! `Hash` for `Float`. `Iterator` yields values one at a time, and its `map`
//! and `filter` return a `MapIter` and a `FilterIter`. A module's own
//! definition of one of these names shadows the one here.
//!
//! An absent value, a failure, and an iterator's lazy `filter` and `map`,
//! run by `collect`:
//!
//! ```
//! // `Option` holds a value that may be absent.
//! let port: Option<Int> = Some(8080)
//! assert_eq(port.map(|p| p + 1).unwrap_or(80), 8081)
//! let missing: Option<Int> = None
//! assert_eq(missing.unwrap_or(80), 80)
//!
//! // `Result` is the outcome of something that can fail.
//! let checked: Result<Int, String> = missing.ok_or("no port given")
//! assert(checked.is_err(), "None became an Err")
//!
//! // An iterator's `filter` and `map` are lazy; `collect` runs them.
//! let mut nums: Vec<Int> = Vec::new()
//! for n in 1..6 { nums.push(n) }
//! let tens = nums.iter().filter(|n| n % 2 == 0).map(|n| n * 10).collect()
//! assert_eq(tens.len(), 2)
//! assert_eq(tens.get(1).unwrap(), 40)
//! ```
// Nova standard library — core.
//
// Compiled as an implicit module and glob-imported into every user module, so
// these names need no `import`. A user definition of the same name shadows the
// one here (see docs/adr/0004-stdlib-compile-model.md).
/// A value that may be absent: `Some` value, or `None`.
pub type Option<T> =
/// Holds a value.
| Some(T)
/// Holds no value.
| None
/// The outcome of an operation that can fail: `Ok` with a value, or `Err`
/// with an error.
pub type Result<T, E> =
/// Holds the value of a success.
| Ok(T)
/// Holds the error of a failure.
| Err(E)
impl<T> Option<T> {
/// Returns `true` if the option is `Some`.
pub fn is_some(self) -> Bool {
match self {
Some(_) => true
None => false
}
}
/// Returns `true` if the option is `None`.
pub fn is_none(self) -> Bool { !self.is_some() }
/// Applies `f` to the value, if there is one.
///
/// Returns `Some(f(v))` for `Some(v)`, and `None` for `None`.
pub fn map<U>(self, f: fn(T) -> U) -> Option<U> {
match self {
Some(v) => Some(f(v))
None => None
}
}
/// Calls `f` with the value, if there is one, and returns its result.
///
/// Returns `None` for `None`, without calling `f`.
pub fn and_then<U>(self, f: fn(T) -> Option<U>) -> Option<U> {
match self {
Some(v) => f(v)
None => None
}
}
/// Returns the value.
///
/// Panics if the option is `None`.
pub fn unwrap(self) -> T {
match self {
Some(v) => v
None => panic("called `unwrap` on a `None` value")
}
}
/// Returns the value, or `default` if the option is `None`.
pub fn unwrap_or(self, default: T) -> T {
match self {
Some(v) => v
None => default
}
}
/// Converts the option to a `Result`: `Ok(v)` for `Some(v)`, and
/// `Err(err)` for `None`.
pub fn ok_or<E>(self, err: E) -> Result<T, E> {
match self {
Some(v) => Ok(v)
None => Err(err)
}
}
}
impl<T, E> Result<T, E> {
/// Returns `true` if the result is `Ok`.
pub fn is_ok(self) -> Bool {
match self {
Ok(_) => true
Err(_) => false
}
}
/// Returns `true` if the result is `Err`.
pub fn is_err(self) -> Bool { !self.is_ok() }
/// Applies `f` to the value of an `Ok`, leaving an `Err` as it is.
pub fn map<U>(self, f: fn(T) -> U) -> Result<U, E> {
match self {
Ok(v) => Ok(f(v))
Err(e) => Err(e)
}
}
/// Applies `f` to the error of an `Err`, leaving an `Ok` as it is.
pub fn map_err<F>(self, f: fn(E) -> F) -> Result<T, F> {
match self {
Ok(v) => Ok(v)
Err(e) => Err(f(e))
}
}
/// Calls `f` with the value of an `Ok` and returns its result.
///
/// Returns an `Err` as it is, without calling `f`.
pub fn and_then<U>(self, f: fn(T) -> Result<U, E>) -> Result<U, E> {
match self {
Ok(v) => f(v)
Err(e) => Err(e)
}
}
/// Returns the value of an `Ok`.
///
/// Panics if the result is an `Err`.
pub fn unwrap(self) -> T {
match self {
Ok(v) => v
Err(_) => panic("called `unwrap` on an `Err` value")
}
}
/// Returns the value of an `Ok`, or `default` for an `Err`.
pub fn unwrap_or(self, default: T) -> T {
match self {
Ok(v) => v
Err(_) => default
}
}
}
// Core traits, and their impls for the five primitive types.
//
// `Ord` cannot be written uniformly: `<` works for Int/Float/Char but not
// for Bool or String (E0013 for both). Bool is ordered with `if` alone;
// String has neither length nor indexing in Nova, so it goes through
// `str_cmp`, a compiler builtin (see `nova-resolver`'s `Builtin` enum) that
// reaches the runtime's byte-lexicographic `nova_rt_str_cmp` directly: a
// named function, resolved specially by the compiler and lowered straight to
// a runtime call — the same way `println`/`print`/`panic` reach the runtime.
// This is *not* how `==` on `String` reaches `nova_rt_str_eq`: `==` is a
// pure operator lowering (`binary_result_ty` permits `Eq`/`Ne` for
// `Ty::String`; MIR's `lower_binary` intercepts it) that introduces no name
// in any namespace, so it has no "reserved word" concern to begin with.
// `str_cmp` does, and unlike `println`/`print`/`panic` it is not meant to be
// user-visible language surface, so it is seeded only into std modules' own
// scopes (`Builtin::STD_ONLY`), not into every module — a user program
// may freely define its own `str_cmp` (String is not FFI-safe, and
// `nova_`-prefixed extern symbols are reserved by the compiler, so a
// user-visible `extern` was not an option either).
// `Hash` reaches the runtime the same way, through two more std-only
// builtins: `str_hash` (no primitive walks a `String`, so a NAMED operation
// over its bytes needs a builtin -- `==` reaches the runtime as a plain
// operator lowering and introduces no name, so it is not one; an absence
// about the primitive layer, NOT
// about what Nova code can reach, since `std/bytes` and `std/strings` build
// byte and char access on builtins of this kind and this module walks a
// string itself at `impl Debug for String` below; an earlier wording here
// read as the wider claim and was quoted as one, which ADR 0005's 2026-08-27
// amendment records) and `char_to_int` (Nova has no `as` casts and
// no other `Char` -> `Int` conversion). `char_to_int` is the one builtin that
// is *not* a runtime call — `Char` and `Int` are the same machine class, so
// nova-mir lowers it to a register move. See ADR 0005 section 2 for why
// `Hash` is one-shot (`fn hash(self) -> Int`) rather than streaming, and why
// there is deliberately no `Hash for Float`.
/// The result of comparing two values, as `Ord::cmp` returns it.
pub type Ordering =
/// The first value is less than the second.
| Less
/// The two values are equal.
| Equal
/// The first value is greater than the second.
| Greater
/// A type whose values can be shown as text for people to read.
///
/// String interpolation, `"${value}"`, uses it for a value of a type that
/// implements it.
pub trait Display {
/// Returns the value as text.
fn fmt(self) -> String
}
/// A type whose values can be shown as text for debugging.
pub trait Debug {
/// Returns the value as text for debugging.
///
/// For `Int`, `Float` and `Bool` it is the text `Display` gives. A `Char`
/// or `String` comes out as a quoted Nova literal, escaped so that it
/// reads back as the same value.
fn dbg(self) -> String
}
/// A type whose values can be compared for equality.
pub trait Eq {
/// Returns `true` if `self` equals `other`.
///
/// For `Float`, `NaN` equals no value, not even itself.
fn eq(self, other: Self) -> Bool
/// Returns `true` if `self` does not equal `other`.
///
/// By default it is the opposite of `eq`.
fn ne(self, other: Self) -> Bool { !self.eq(other) }
}
/// A type whose values are ordered.
pub trait Ord: Eq {
/// Returns whether `self` is less than, equal to or greater than `other`.
///
/// std orders `false` before `true`, a `Char` by its code point, and a
/// `String` by its UTF-8 bytes. For `Float`, how `NaN` orders is
/// unspecified: today any comparison involving it gives `Greater`, even
/// `NaN` with itself.
fn cmp(self, other: Self) -> Ordering
}
/// A type whose values can be copied.
pub trait Clone {
/// Returns a copy of `self`.
fn clone(self) -> Self
}
/// A type with a default value.
pub trait Default {
/// Returns the type's default value.
///
/// For `Int`, `Float`, `Bool`, `Char` and `String` it is `0`, `0.0`,
/// `false`, `'\0'` and `""`.
fn default() -> Self
}
// One-shot hashing: a value's hash is a single `Int`, not a stream folded into
// a `Hasher` (ADR 0005 section 2). There is no `Hash for Float` on purpose:
// NaN never equals itself, so a NaN key would be unreachable in a hash map,
// and `0.0`/`-0.0` are `==` but would hash differently.
//
// An implementor's contract: if `a.eq(b)` then `a.hash() == b.hash()`.
//
// HOW TO USE A HASH: **mask it. Never shift it, and never read its high
// bits.** `hash & (cap - 1)` over a power-of-two capacity is the only
// supported way to turn a hash into a bucket index, for three separate
// reasons:
//
// - `hash % cap` can be *negative*: `str_hash` reinterprets an unsigned
// 64-bit result as `Int`, and `mix64` spans the full `Int` range too, so a
// remainder inherits the sign. `&` with a positive mask is non-negative
// for every `Int`.
// - The high bits are not a usable second hash. A `hash >> 57`-style tag
// byte is *not* independent of the low bits used for the bucket, and for
// `str_hash` a negative hash sign-extends into any such tag, so the tag
// loses half its range on exactly the keys that need distinguishing.
// - `mix64`'s guarantees are stated over its whole 64-bit result; nothing
// promises that any particular slice of it is uniform on its own.
/// A type whose values can be hashed to an `Int`.
///
/// A `Map`'s keys and a `Set`'s values must implement it, and `Eq`.
/// Two values equal by `eq` must have the same hash. `Float` has no impl:
/// `NaN` equals no value, and `0.0` and `-0.0` are equal though their bits
/// differ.
///
/// A record of your own as a `Map` key, with `Eq` and `Hash` that
/// agree:
///
/// ```
/// record Point { x: Int, y: Int }
///
/// impl Eq for Point {
/// fn eq(self, other: Point) -> Bool { self.x == other.x && self.y == other.y }
/// }
///
/// // Points equal by `eq` must hash alike, so combine the fields' hashes.
/// impl Hash for Point {
/// fn hash(self) -> Int { self.x.hash() * 31 + self.y.hash() }
/// }
///
/// fn main() {
/// let mut names: Map<Point, String> = Map::new()
/// names.insert(Point { x: 0, y: 0 }, "origin")
/// assert_eq(names.get(Point { x: 0, y: 0 }).unwrap(), "origin")
/// assert(!names.contains_key(Point { x: 1, y: 0 }), "a different point")
/// }
/// ```
pub trait Hash {
/// Returns the value's hash.
///
/// A hash can be negative. To pick one of `n` buckets, where `n` is a
/// power of two, mask it, `hash & (n - 1)`, rather than taking a
/// remainder, which can be negative, or using its high bits. std seeds
/// the hashes of `Int`, `Bool`, `Char` and `String` once per run, so they
/// can differ from one run of a program to the next.
fn hash(self) -> Int
}
// The iteration protocol, and the first trait in this file with an associated
// type. `next` advances the iterator and yields the next element, or `None`
// once exhausted; `Item` is what it yields, chosen by the implementor.
//
// `mut self` is load-bearing rather than stylistic: an iterator has to advance,
// which means mutating its own state, so a `next` taking plain `self` would
// either not advance or advance invisibly. It is also the first `mut self` in
// any `impl Trait for Type` in std — closing the trait-method half of the
// mutable-receiver rule was a hard gate before this trait could be declared at
// all (ADR 0005 §1). The consequence for callers: calling `next` itself needs
// the iterator held in a `mut` binding or arriving as a `mut` parameter, or
// the call is `E0060` — true of `next` specifically, and no longer true of
// the four default consumer methods below (see the comment above `fold`).
//
// `Option<Self::Item>` is the projection this whole increment exists to make
// expressible. It is deliberately spelled with `::` and not the `.` that
// nova-spec/20-STDLIB.md used, because `::` is already how Nova reaches into a
// type (`Vec::new`, `T::default`) while `.` is field access everywhere else.
//
// `map`/`filter`/`fold`/`count`/`any`/`collect` are default methods below,
// so a caller reaches `MapIter`/`FilterIter` (see below) through `.map()`/
// `.filter()` and never has to name them directly. Still NOT YET, and still
// deliberately deferred rather than overlooked: `IntoIterator`, so `for x in
// v` does not work — write `v.iter()`. `Map::iter` is not merely unwritten
// but impossible — it would yield a pair and Nova has no tuples. Iterating
// means a hand-written `while` plus a `match` on the `Option`, or `for x in
// it`, or now one of the six methods below.
//
// Unlike the traits above, this one is implemented for **no** primitive, so
// `next` is not taken away from user code on `Int`/`Float`/`Bool`/`Char`/
// `String` the way each of *their* methods is (ADR 0004, "Method names are not
// soft-reserved"). A user `trait Feed { fn next(...) }` stays usable on those
// types.
//
// Deliberately no count and no method list here. Both used to be written out —
// "the **six** traits above" and `fmt`/`eq`/`cmp`/`clone`/`default` — and both
// were wrong by the time anyone read them: `Hash` landing in Phase 2.2a left
// the tally short, and the list silently omitted `dbg` and `hash`. "Six" was
// correct when written, and the list was never complete. A hand-maintained
// tally of "the traits above", in the one file that gains traits, drifts by
// construction; grep `^pub trait` above this line for the current set, and the
// `impl <Trait> for <primitive>` block near the bottom of this file for which
// of their methods each primitive really has.
/// A source of values, yielded one at a time by `next`.
///
/// A `for` loop runs over any iterator: `for x in v.iter()`. `map` and
/// `filter` are lazy, and `fold`, `count`, `any` and `collect` consume the
/// iterator. A record iterator is shared, not copied: the one these methods
/// were called on is the one that advances, even when it is held in a
/// binding that is not `mut`.
///
/// The adapters are lazy; a consumer runs them:
///
/// ```
/// let mut words: Vec<String> = Vec::new()
/// words.push("map")
/// words.push("filter")
/// words.push("fold")
///
/// // `filter` and `map` do nothing until a consumer such as `fold` runs them.
/// // A closure that calls a method on its parameter names the parameter's type.
/// let lengths = words.iter().filter(|w: String| w.starts_with("f")).map(|w: String| w.len())
/// assert_eq(lengths.fold(0, |acc, n| acc + n), 10)
/// assert(words.iter().any(|w| w == "map"), "`any` stops at the first match")
/// ```
pub trait Iterator {
/// The type of the values the iterator yields.
type Item
/// Advances the iterator and returns its next value, or `None` when it
/// has no more.
///
/// Calling it needs a mutable iterator, such as one held in a `mut`
/// binding.
fn next(mut self) -> Option<Self::Item>
// --- adapters (lazy: nothing is consumed until a consumer runs) ---
/// Returns an iterator that yields `f(x)` for each value `x` of this one.
///
/// It is lazy: it calls `f` only as it is advanced.
fn map<U>(self, f: fn(Self::Item) -> U) -> MapIter<Self, U> { MapIter { it: self, f: f } }
/// Returns an iterator that yields the values of this one for which
/// `keep` returns `true`.
///
/// It is lazy: it calls `keep` only as it is advanced.
fn filter(self, keep: fn(Self::Item) -> Bool) -> FilterIter<Self> {
FilterIter { it: self, keep: keep }
}
// --- consumers (each drives the iterator to exhaustion or short-circuits) ---
// Plain `self`, not `mut self`, on all four consumers below — `next` is
// still `mut self` (it is the one method a caller invokes repeatedly on a
// binding they hold), but a consumer runs to exhaustion in one call, so it
// does not need its *own* receiver to already be a mutable place; it only
// needs a mutable place to drive `next` through, and it makes its own with
// `let mut it = self`. Records are heap objects with no copy semantics
// anywhere in this compiler, so for a record `Self` `it` is an alias of
// exactly the storage `self` pointed to, not a copy — advancing `it`
// advances the same iterator the caller passed in.
// `an_iterators_own_storage_still_advances_when_a_consumer_takes_
// plain_self` (`crates/nova-cli/tests/run_tests.rs`) pins the aliasing.
//
// "For a record `Self`" is a real condition, not a hedge: nothing in this
// trait requires one. `impl Iterator for Int` compiles, a primitive is
// passed by value, so the rebind copies and all four consumers **diverge**
// rather than returning a wrong number. Pre-existing (hand-driving such an
// impl loops forever too) and measured — see ADR 0007 §2, "Why it is safe".
//
// This is what lets `v.iter().filter(f).map(g).collect()` — the form this
// feature exists to make possible — compile at all: `.filter()`/`.map()`
// each return a temporary, and only a plain-`self` method can be called on
// one (`place_root` classifies a call result `PlaceRoot::NotAPlace`, and a
// `mut self` receiver requires `PlaceRoot::Mutable`).
//
// Dropping `mut self` relaxes *two* of `place_root`'s classifications, not
// only the one this design needed: `NotAPlace` (the temporary above, the
// actual goal) and, as a side effect, `ImmutableLocal` too — a caller may
// now hold the iterator in a binding that is never declared `mut` at all,
// and one of these four methods still silently advances or fully consumes
// it:
//
// let it = some_record // NOT mut
// it.count() // 3
// it.count() // 0 -- silently advanced, no diagnostic
//
// Under `mut self` the first call alone was `E0060`. This is not a new
// capability, only a wider door to an old one: the compiler's own
// `for x in <expr>` desugar already launders exactly this way
// (`check_for_iterator`, `crates/nova-typeck/src/check.rs`:
// `let mut __it = <expr>`), so `for x in <an immutable local>` already
// advanced that local before this trait had a single default method —
// this is that laundering's first appearance in a *library* API, not a
// new mechanism. Nor does any new iterator *state* become reachable: a
// `mut` binding could always be partially consumed and reused. The only
// thing that changed is which receivers these four methods accept
// syntactically.
// `iterator_any_short_circuits_and_does_not_scan_past_the_first_match`
// (`crates/nova-cli/tests/run_tests.rs`) pins a non-`mut` receiver being
// silently advanced through `any` as accepted, current behavior.
// The fold primitive. `count` and `collect` could be written over it;
// `any` cannot, because `fold` visits every element and `any` must stop.
/// Folds the values into one, calling `f(acc, x)` for each value `x`.
///
/// `acc` starts as `init` and becomes each call's result, and the last
/// result is returned. Returns `init` if there are no values.
fn fold<A>(self, init: A, f: fn(A, Self::Item) -> A) -> A {
let mut it = self
let mut acc = init
while true {
let n = it.next()
if n.is_none() { return acc }
let g = f
acc = g(acc, n.unwrap())
}
acc
}
// `count`, not `len`: this consumes the iterator, where `Vec::len` is cheap
// and non-destructive. Naming it `len` would invite the wrong assumption.
/// Counts the values, consuming the iterator.
fn count(self) -> Int {
let mut it = self
let mut n = 0
while true {
let x = it.next()
if x.is_none() { return n }
n = n + 1
}
n
}
// Short-circuits, which is why it is not written over `fold`.
/// Returns `true` if `p` returns `true` for any value, and `false`
/// otherwise.
///
/// It stops at the first value `p` accepts.
fn any(self, p: fn(Self::Item) -> Bool) -> Bool {
let mut it = self
while true {
let n = it.next()
if n.is_none() { return false }
let q = p
if q(n.unwrap()) { return true }
}
false
}
// Returns a `Vec`, which makes `std/core` depend on `std/collections` for
// the first time. Accepted deliberately: one method, one type, and the
// whole-program merge means there is no layering mechanism to violate, only
// a convention. The alternative was `Vec::from_iter(it)` in
// `std/collections`, which keeps `std/core` free of collections and reads
// worse at the call site.
/// Collects the values into a `Vec`, in order.
fn collect(self) -> Vec<Self::Item> {
let mut it = self
let mut out = Vec::new()
while true {
let n = it.next()
if n.is_none() { return out }
out.push(n.unwrap())
}
out
}
}
// A lazy `map`: yields `f(x)` for each `x` the inner iterator yields.
//
// `f: fn(I::Item) -> U` is why `I` carries a bound. A bound on a record's type
// parameter is a resolution scope, not a constraint (ADR 0007): it lets this
// field name `I::Item` at all, and it is not itself checked when a `MapIter`
// is built — `impl<I: Iterator, U> Iterator for MapIter<I, U>` below is what
// makes a `MapIter` iterable, not this declaration.
//
// That does not make a `MapIter<Int, U>` freely buildable, though: `f`'s own
// field type names `I::Item`, and `Int::Item` has nothing to resolve to (`Int`
// has no `Iterator` impl), so `f`'s declared type never normalizes. What
// happens then depends on the closure and on reachability, and it is ADR 0007
// §1 (case 1, and its routing table) that has the mechanism — read it there
// rather than reconstructing it from here. Two things this comment used to get
// wrong, both measured:
//
// - "no closure — none, for any `f` — can unify against it" is **false**.
// `MapIter { it: 5, f: |x| x }` produces no unification error at all:
// typeck accepts it and monomorphization refuses it with
// `error[E0079]: 'Int::Item' is still an unresolved associated type after
// instantiating 'main'`. A fresh inference variable binds to an
// unnormalized projection just as happily as to a concrete type. Only an
// *annotated* closure fails to unify — `f: |x: Int| x` is
// `error[E0010]: field 'f' expects 'fn(Int::Item) -> ?N' but found
// 'fn(Int) -> Int'`, plus four `E0011`s for the variables it left free.
// - "unconstructible" full stop, and "caught at construction" full stop, are
// **false when the construction is not reachable from `main`**, because the
// mechanism is monomorphization and it inherits monomorphization's reach. A
// `MapIter { it: 5, f: |x| x }` inside a function `main` never calls is
// accepted: `nova check` exits 0 with no diagnostic and the program runs.
// ADR 0007 §1 states the qualifier and shows the measurement.
//
// So: a bad instantiation of these two shapes is refused wherever it is
// actually instantiated, and nowhere else. That is still earlier and stronger
// than the bound itself promises — the bound was meant to leave construction
// unconstrained and block only *use* as an iterator — and it still has nothing
// to do with the bound.
//
// Holds `it` by pointer, like every record, so it SHARES the source iterator
// rather than copying it — advancing this adapter advances the source, and
// mutating the source mid-iteration is observable. Same alias visibility
// `VecIter` documents; preventing it needs borrow tracking Nova lacks.
/// An iterator that yields a function's result for each value of another.
///
/// `Iterator::map` returns one. It shares the iterator it wraps rather than
/// copying it.
pub record MapIter<I: Iterator, U> { it: I, f: fn(I::Item) -> U }
impl<I: Iterator, U> Iterator for MapIter<I, U> {
type Item = U
fn next(mut self) -> Option<U> {
let n = self.it.next()
if n.is_none() {
None
} else {
// Bound to a local first: `(self.f)(x)` is `E0014: no method f`.
let g = self.f
Some(g(n.unwrap()))
}
}
}
// A lazy `filter`: yields only the elements `keep` accepts.
//
// `type Item = I::Item` is a projection-valued binding — the associated type is
// itself a projection — which is the `Assoc { on: Assoc }` shape Phase 2.2c
// could only reach from a hand-built unit test. This is its first appearance in
// real source.
//
// `I`'s bound is a resolution scope here for the same reason it is on `MapIter`
// above — it is what lets `keep` name `I::Item` at all, and it is not checked
// when a `FilterIter` is built. See `MapIter`'s comment and ADR 0007 §1 (case 1
// and its routing table) for the full account, including what actually happens
// to a `FilterIter<Int>`: it is refused wherever it is instantiated — measured,
// `FilterIter { it: 5, keep: |x| true }` in `main` is one `E0079` from
// monomorphization, and `keep: |x: Int| true` is instead one `E0010` naming
// `fn(Int::Item) -> Bool` — but **not** when the construction site is
// unreachable from `main`, since the mechanism is monomorphization. This
// comment previously said "unconstructible" without that qualifier.
/// An iterator that yields the values of another that a predicate accepts.
///
/// `Iterator::filter` returns one. It shares the iterator it wraps rather
/// than copying it.
pub record FilterIter<I: Iterator> { it: I, keep: fn(I::Item) -> Bool }
impl<I: Iterator> Iterator for FilterIter<I> {
type Item = I::Item
fn next(mut self) -> Option<I::Item> {
// `while true`, not `loop`: Nova has no `loop` keyword.
while true {
let n = self.it.next()
if n.is_none() { return None }
let p = self.keep
if p(n.unwrap()) { return Some(n.unwrap()) }
}
None
}
}
impl Display for Int {
fn fmt(self) -> String { "${self}" }
}
impl Display for Float {
fn fmt(self) -> String { "${self}" }
}
impl Display for Bool {
fn fmt(self) -> String { "${self}" }
}
impl Display for Char {
fn fmt(self) -> String { "${self}" }
}
impl Display for String {
fn fmt(self) -> String { self }
}
// `Debug`'s contract is that its output is a *Nova literal* for the value, so
// `Char` and `String` are quoted where `Display` is not. Nova's lexer accepts
// `\n \t \r \\ \0 \u{…}` plus `\"` in a string literal and `\'` in a char
// literal (`nova-lexer`'s string scanner and `lex_char`); `\"` is not valid in
// a char literal, nor `\'` in a string one, so each form escapes the quote
// that delimits it, plus the backslash. `String` also escapes every `$` (as
// `\u{24}`): a string literal, unlike a char literal, opens an interpolation
// hole on `$` immediately followed by `{`, so a literal `$` left in the
// output could silently reopen one when the output is pasted back as
// source. `Char` never interpolates, so it needs no such rule.
impl Debug for Int {
fn dbg(self) -> String { "${self}" }
}
impl Debug for Float {
fn dbg(self) -> String { "${self}" }
}
impl Debug for Bool {
fn dbg(self) -> String { "${self}" }
}
// The escape sequence for `c` inside a string literal, or `None` when `c`
// needs none. Quoting differs between a `Char` literal and a `String`
// literal, so the quote characters are the callers' business: `Debug for
// Char` escapes `'`, `Debug for String` escapes `"`, and both need the rest
// of this identically — shared here rather than duplicated a second time, the
// way `Map::get`/`remove`'s probe scan was in Phase 2.2a.
fn escape_common(c: Char) -> Option<String> {
if c == '\\' { return Some("\\\\") }
if c == '\n' { return Some("\\n") }
if c == '\t' { return Some("\\t") }
if c == '\r' { return Some("\\r") }
if c == '\0' { return Some("\\0") }
None
}
// `'` is the one escape `Char` needs that `escape_common` does not cover
// (mirrored by `"` in `Debug for String` below), so it is handled directly;
// everything else comes from `escape_common`. The escaped set is exactly
// what `lex_char` accepts, so every output here round-trips back through the
// lexer to `self`. A raw newline/tab/NUL does lex inside `'…'`, but emitting
// one would put a control character in the middle of debug output, which
// defeats the purpose.
impl Debug for Char {
fn dbg(self) -> String {
if self == '\'' {
"'\\''"
} else {
match escape_common(self) {
Some(e) => "'${e}'"
None => "'${self}'"
}
}
}
}
// `str_chars` (a `Builtin::STD_ONLY` member added for `std/strings`, so it is
// already visible here with no import and no dependency on `std/strings`)
// lets this inspect the string's contents directly — which turned out to be
// all that closing this ever needed. No dedicated ABI symbol was added: `"`
// is handled the same way `'` is handled above; `$` gets its own arm too,
// escaped unconditionally as `\u{24}` rather than only when immediately
// followed by `{` — a plain per-character rule like every other entry here,
// with no lookahead to get wrong, and it costs nothing since a `$` not
// before `{` was already safe to leave alone. That arm has to live here
// rather than in `escape_common`: `\u{24}` does not lex inside a char
// literal (`'\u{24}'` fails with `unexpected character '`), so routing it
// through the shared helper would make `Debug for Char` emit `'\u{24}'`,
// which does not parse; `\$` is not an escape sequence either. Everything
// else comes from `escape_common`. Building `out` by repeated interpolation
// (rather than `str_from_chars`) is quadratic in the string's length, since
// each `${out}${piece}` copies `out` again; `dbg` is a diagnostic path, not
// a hot one, so that trade is the right one rather than pretending
// otherwise.
impl Debug for String {
fn dbg(self) -> String {
let cs = str_chars(self)
let mut out = "\""
for i in 0..cs.len() {
let c = cs[i]
if c == '"' {
out = "${out}\\\""
} else if c == '$' {
out = "${out}\\u{24}"
} else {
match escape_common(c) {
Some(e) => out = "${out}${e}"
None => out = "${out}${c}"
}
}
}
"${out}\""
}
}
impl Eq for Int {
fn eq(self, other: Int) -> Bool { self == other }
}
// Not reflexive for NaN: `NaN == NaN` is `false`, so `eq(NaN, NaN)` is
// `false` too (NaN is reachable, e.g. via `0.0 / 0.0`). See the `Ord for
// Float` impl below for the related non-total-order caveat.
impl Eq for Float {
fn eq(self, other: Float) -> Bool { self == other }
}
impl Eq for Bool {
fn eq(self, other: Bool) -> Bool { self == other }
}
impl Eq for Char {
fn eq(self, other: Char) -> Bool { self == other }
}
impl Eq for String {
fn eq(self, other: String) -> Bool { self == other }
}
impl Ord for Int {
fn cmp(self, other: Int) -> Ordering {
if self < other { Less } else { if self == other { Equal } else { Greater } }
}
}
impl Ord for Float {
// Not a total order for NaN: `<` and `==` are both `false` whenever
// either operand is NaN, so this falls through to `Greater` for any
// comparison involving NaN — including `cmp(NaN, NaN)`, which is
// `Greater`, not `Equal`. Ordering NaN is unspecified; do not rely on it
// (e.g. for a future sorted collection) until addressed by design.
fn cmp(self, other: Float) -> Ordering {
if self < other { Less } else { if self == other { Equal } else { Greater } }
}
}
impl Ord for Char {
fn cmp(self, other: Char) -> Ordering {
if self < other { Less } else { if self == other { Equal } else { Greater } }
}
}
impl Ord for Bool {
// `<` is not defined for Bool; false sorts before true.
fn cmp(self, other: Bool) -> Ordering {
if self { if other { Equal } else { Greater } } else { if other { Less } else { Equal } }
}
}
impl Ord for String {
// String has neither length nor indexing in Nova, so ordering comes from
// `str_cmp`, a compiler builtin backed by the runtime's byte-lexicographic
// compare (see the module-level note above for why not `extern`).
fn cmp(self, other: String) -> Ordering {
let c = str_cmp(self, other)
if c < 0 { Less } else { if c == 0 { Equal } else { Greater } }
}
}
impl Clone for Int {
fn clone(self) -> Int { self }
}
impl Clone for Float {
fn clone(self) -> Float { self }
}
impl Clone for Bool {
fn clone(self) -> Bool { self }
}
impl Clone for Char {
fn clone(self) -> Char { self }
}
impl Clone for String {
fn clone(self) -> String { self }
}
impl Default for Int {
fn default() -> Int { 0 }
}
impl Default for Float {
fn default() -> Float { 0.0 }
}
impl Default for Bool {
fn default() -> Bool { false }
}
impl Default for Char {
fn default() -> Char { '\0' }
}
impl Default for String {
fn default() -> String { "" }
}
// The splitmix64 finalizer: three xor-shift/multiply rounds. `Map` selects
// buckets with `hash & (cap - 1)`, so it is the *low* bits that must be
// spread; `fn hash(self) -> Int { self }` would send every multiple of the
// capacity to bucket 0. A known-good mixer is used rather than an invented
// one, and this is bit-identical to the canonical splitmix64 finalizer.
//
// Getting there needs two workarounds for what `Int` cannot express, and both
// are load-bearing rather than cosmetic:
//
// - The constants are `0xbf58476d1ce4e5b9` and `0x94d049bb133111eb`, which
// exceed `Int`'s range, so they are written as the two's-complement
// negatives of those bit patterns. Hex is not an option — the lexer's
// `lex_hex_int` parses as `i64`, so `0xbf58…` silently fails to lex — but
// each negative *is* `-` applied to a decimal literal below `i64::MAX`,
// which lexes, and `*` wraps rather than trapping, so the arithmetic
// agrees modulo 2^64.
// - Nova's `>>` is **arithmetic** and there is no `>>>`, so each shift is
// masked to clear the sign extension: `& (2^(64-k) - 1)`, i.e.
// `17179869183` for `>> 30`, `137438953471` for `>> 27`, `8589934591`
// for `>> 31`. The mask is not optional. Without it, arithmetic shift
// commutes with complement (`!(x >> k) == (!x) >> k`) and XOR is
// invariant under complementing both operands, so `x ^ (x >> k)` returns
// the *same value* for `x` and `!x == -1 - x`. Every later stage is a
// function of that output, so the whole finalizer folded 2-to-1 with
// `mix64(x) == mix64(-1 - x)` — identical hashes, not merely congruent
// ones, so each pair shared a bucket at *every* capacity and no resize
// could ever separate them. Pinned by `tests/runtime/hash.nova`.
//
// NOT SEEDED, and that is a decision rather than an oversight. The
// per-process seed is XORed into the *input* by the `Int`, `Bool` and `Char`
// `Hash` impls below, before this function runs, so `mix64` itself stays
// bit-identical to canonical splitmix64's finalizer and the canonical vectors
// in `tests/runtime/hash.nova` keep testing the same function they always
// tested.
//
// The masks stay load-bearing for exactly the reason given above, because
// seeding does not rescue an unmasked finalizer. XOR with a constant commutes
// with complement — `(!k) ^ s == !(k ^ s)` — so an unmasked stage 1 still maps
// `k ^ s` and `!(k ^ s)` to one value, and the pair `k`, `!k` still folds
// together whatever the seed is.
//
// Module-private, and it stays that way: ADR 0005 records the privacy as a
// decision, since this is an implementation detail of the primitive impls
// rather than a published utility and publishing it would make its exact
// definition a compatibility surface, and the same ADR reserves the freedom to
// replace these constants or rounds. So `tests/runtime/hash.nova` cannot call
// this function at all; it recovers the seed from `(0).hash()` and cancels it,
// carrying its own inverse of the arithmetic below. If these constants ever
// change, that inverse changes with them.
fn mix64(x: Int) -> Int {
let a = x ^ ((x >> 30) & 17179869183)
let b = a * -4658895280553007687
let c = b ^ ((b >> 27) & 137438953471)
let d = c * -7723592293110705685
d ^ ((d >> 31) & 8589934591)
}
// The per-process seed goes into `mix64`'s INPUT, not its output, and that is
// load-bearing rather than stylistic. `Map` selects buckets with
// `hash & (cap - 1)`, so post-XOR — `mix64(x) ^ int_hash_seed()` — would leave
// the low bits as `(mix64(x) & mask) XOR (seed & mask)`, which *permutes*
// buckets and leaves every colliding pair still colliding. It would look like
// seeding and buy nothing.
//
// What pre-XOR buys is precomputation resistance: a key set built to collide
// against one process, or offline, does not collide here. What it does not
// claim, and how Nova code can recover the seed in one call, is at
// `int_hash_seed` in the resolver and `nova_rt_int_hash_seed` in the runtime.
// A consequence worth stating where the reader meets it: an `Int`, `Bool` or
// `Char` hashes to one value for the whole of a run and can hash to a
// different one in the next run of the same program.
impl Hash for Int {
fn hash(self) -> Int { mix64(self ^ int_hash_seed()) }
}
impl Hash for Bool {
fn hash(self) -> Int {
if self { mix64(1 ^ int_hash_seed()) } else { mix64(0 ^ int_hash_seed()) }
}
}
// Hashes the Unicode scalar value, so it agrees with `Hash for Int` on that
// codepoint. `char_to_int` is a compiler builtin because Nova has no `as`
// casts and `Char` has no other conversion.
impl Hash for Char {
fn hash(self) -> Int { mix64(char_to_int(self) ^ int_hash_seed()) }
}
// Seeded FNV-1a over the bytes then splitmix64's finalizer, in the runtime
// (see the module note above), with its unsigned result reinterpreted as `Int`
// — so it is the impl most obviously able to return a negative hash. See the
// masking rule on `Hash` above.
//
// The seed is drawn once per process, so a given `String` hashes to one value
// for the whole of a run and can hash to a different one in the next run of the
// same program — not must, since two seeds may agree on one string. What
// that buys and what it does not is documented at `nova_rt_str_hash` in the
// runtime. The `Int`, `Bool` and `Char` impls above are seeded too, from a
// separate draw (`int_hash_seed`), so they are not stable across runs either;
// what stays unseeded is `mix64`, which those impls XOR the seed in *ahead* of.
impl Hash for String {
fn hash(self) -> Int { str_hash(self) }
}