std/src/collections/vec/protocols.nv - main - nv-lang/nova

std/src/collections/vec/protocols.nv
211 строк9 KB
Evgeniy Golovin
docs(std/src): clean comments batch 15 — collections vec/*, set/core, linkedlist
01 авг 2026, 11:56
01 авг 2026, 11:562d0a27f
// std.collections.vec (protocols) — Equal / Clone / Display / Debug.
//
// `Vec[T: Equal]` → Equal, `Vec[T: Compare]` → Compare (lexicographic,
// element-wise), `Vec[T: Clone]` → Clone (deep/recursive),
// `Vec[T: Display]` → Display, `Vec[T: Debug]` → Debug. Bounds on `T` are
// conditional (Rust `impl<T: Ord> Ord for Vec<T>`).
#prelude(core, runtime, collections, protocols)
module collections.vec

// ─── Equal ───────────────────────────────────────────────────────────

/// Element-wise equality — `true` iff both vectors have the same length and
/// every pair of corresponding elements compares equal via `==`.
///
/// This works for any element type `T` for which `==` is defined (all
/// primitives and types that implement `Equal`). For unknown/opaque element
/// types the comparison degrades to reference identity (same C pointer), which
/// may give surprising results — declare `@equal` on the element type to
/// override.
///
/// # Examples
///
/// ```nova
/// let a = Vec[int].of(1, 2, 3)
/// let b = Vec[int].of(1, 2, 3)
/// let c = Vec[int].of(1, 2, 4)
/// assert(a.equal(b))
/// assert(!a.equal(c))
/// ```
export fn Vec[T] @equal(other Vec[T]) -> bool {
    if @len != other.len() {
        return false
    }
    // `i < other.len()` holds (lengths equal), so read both elements raw — no
    // redundant `@index` bounds check; consistent with the module's `other.data`
    // idiom (`@append`/`@splice`/`@copy_from`). Extract to typed locals so the
    // `!=` operands have element type `T` (a method/operator on a raw deref kept
    // *inside* the `unsafe` block misresolves in codegen).
    for i in 0..@len {
        ro a = unsafe { @data.read_at(i) }
        ro b = unsafe { other.data.read_at(i) }
        if a != b {
            return false
        }
    }
    true
}

// ─── Compare ──────────────────────────────────────────────────────────

/// Lexicographic comparison against `other`, returning `-1`/`0`/`+1` — the
/// `Compare` protocol impl. Compares element-wise via each element's own
/// `@compare`, like Rust `Vec<T: Ord>`: the first non-equal pair decides;
/// otherwise the shorter vector is "less".
///
/// Bound `[T Compare]` so the ordering is the **element type's own**, NOT a raw
/// byte compare. This is what makes `Vec[T: Compare]` itself `Compare`:
/// `Vec[Vec[int]]` sorts correctly, `Vec[int]` orders by value (not raw
/// little-endian bytes), `Vec[f64]` uses f64's NaN/-0.0-aware ordering, and a
/// `Vec[Record]` compares element content (not pointer addresses).
///
/// HISTORY: the prior impl was a byte-wise `RawMem.compare` (memcmp) — correct
/// only for `Vec[u8]` (single-byte unsigned elements, where byte order == value
/// order). A `u8`-specialised memcmp fast-path is a perf followup.
///
/// # Examples
///
/// ```nova
/// let a = Vec[int].of(1, 2, 3)
/// let b = Vec[int].of(1, 2, 4)
/// let c = Vec[int].of(1, 2)
/// assert(a.compare(b) == -1)   // 3 < 4 at index 2
/// assert(a.compare(c) == 1)    // a longer, common prefix equal
/// assert(a.compare(a) == 0)
/// ```
export fn Vec[T Compare] @compare(other Vec[T]) -> int {
    ro n = if @len < other.len() { @len } else { other.len() }
    // `i < n <= other.len()`, so read both elements raw — no redundant `@index`
    // bounds check on `other` (module `other.data` idiom). Extract to typed
    // locals so `.compare` dispatches on element type `T`; a method call kept
    // *inside* the `unsafe` block on a raw deref misresolves in codegen.
    for i in 0..n {
        ro a = unsafe { @data.read_at(i) }
        ro b = unsafe { other.data.read_at(i) }
        ro c = a.compare(b)
        if c != 0 {
            return c
        }
    }
    if @len < other.len() { return -1 }
    if @len > other.len() { return 1 }
    0
}

// ─── Clone ────────────────────────────────────────────────────────────

/// Copy — allocate a new `Vec[T]` and copy every element into a fresh buffer.
///
/// `Clone` is a **deep / recursive** protocol — `clone()` recurses
/// element-wise via each element's own `@clone()`, under a conditional bound
/// `[T Clone]` (Rust `impl<T: Clone> Clone for Vec<T>`).
///
/// The per-element generic `@data[i].clone()` dispatches correctly for **every**
/// `T` — primitive `.clone()` resolves to a built-in identity copy, record/sum
/// `T` recurses through `T.@clone()`.
///
/// # Examples
///
/// ```nova
/// let a = Vec[int].of(1, 2, 3)
/// let mut b = a.clone()
/// b.push(4)
/// assert(a.len() == 3)   // original unchanged
/// assert(b.len() == 4)
/// ```
export fn Vec[T Clone] @clone() -> Self {
    mut out = Vec[T].new(cap: @len)
    for i in 0..@len {
        out.push(unsafe { @data.read_at(i) }.clone())
    }
    out
}

// ─── Hash ─────────────────────────────────────────────────────────────

/// Order- and length-sensitive content hash — folds the length and each
/// element's own `@hash()` (bound `[T Hash]`) via FNV-1a (64-bit). This is what
/// makes `Vec[T: Hash]` itself `Hash`, so a `Vec[int]` works
/// as a `HashMap` key or `HashSet` member.
///
/// Consistent with `@equal` (the `Hash`+`Equal` table contract): equal vectors —
/// same length, element-wise `==` — produce equal hashes, because the fold reads
/// the same length then the same per-element `@hash()` sequence.
///
/// FNV mixing is MODULAR (mod 2^64 wraparound) BY DESIGN — that IS the hash
/// step. After the sized-int trap-default, a bare `*`
/// on u64 traps on overflow, so the mixing multiply is expressed via the
/// explicit `.wrapping_mul` opt-out (modular arithmetic). The offset basis is
/// a hex literal because its decimal form exceeds `i64::MAX` (a bare decimal
/// would be parsed as `int` first and overflow).
///
/// # Examples
///
/// ```nova
/// let a = Vec[int].of(1, 2, 3)
/// let b = Vec[int].of(1, 2, 3)
/// assert(a.hash() == b.hash())
/// ```
export fn Vec[T Hash] @hash() -> u64 {
    // FNV-1a (64-bit): offset basis, then `h = (h ^ x) * prime` per step.
    // `.wrapping_mul` — модульное умножение по замыслу (sized-int trap-default
    // не даёт голому `*` переполниться).
    ro prime = 0x100000001b3 as u64
    mut h = 0xcbf29ce484222325 as u64
    h = (h ^ (@len as u64)).wrapping_mul(prime)
    for i in 0..@len {
        // Typed local first — `.hash()` on a raw deref kept *inside* the `unsafe`
        // block misresolves in codegen (same idiom as `@equal`/`@compare`).
        ro e = unsafe { @data.read_at(i) }
        ro eh = e.hash()
        h = (h ^ eh).wrapping_mul(prime)
    }
    h
}

// ─── Display / Debug ───────────────────────────────────────────
//
// `Display`/`Debug` are REQUIRED protocols with the `(mut f Fmt)` signature —
// a bare `Write` is strictly poorer than `Fmt` (no width/precision/align/fill/
// sign/alternate/kind/`@pad`), so `Vec` implements them against `Fmt` only.
// String LITERALS below are passed BARE to `f.write(...)`: a str-literal →
// `[]u8` coercion exists specifically for this shape (a literal argument to a
// call named `write`). `[]T` is a syntactic alias for `Vec[T]`
// (reference-nova-slice-vec-alias), so this single impl covers both.

/// Append a human-readable representation of `self` to `f`.
///
/// Format: `Vec[e0, e1, ..., eN-1]` where each element is formatted via
/// `elem.display(f)` directly (no intermediate string allocation). Display
/// and Debug share this exact shape — a `Vec[T]` has no field names to
/// diverge over (the compact-vs-named split applies to record/sum
/// derive, not to a container's own hand-written impl).
///
/// # Examples
///
/// ```nova
/// let v = Vec[int].of(1, 2, 3)
/// consume sb = StringBuilder.new()
/// v.display(FmtCtx.bare(sb, 0, false))
/// assert(sb.into_str() == "Vec[1, 2, 3]")
/// ```
export fn Vec[T Display] @display(mut f Fmt) -> () {
    f.write("Vec[")
    for i in 0..@len {
        if i > 0 { f.write(", ") }
        unsafe { @data.read_at(i) }.display(f)
    }
    f.write("]")
}

/// Append a debug representation of `self` to `f`.
///
/// Provided so that `${v:?}` interp-string syntax works for `Vec[T]`.
export fn Vec[T Debug] @debug(mut f Fmt) -> () {
    f.write("Vec[")
    for i in 0..@len {
        if i > 0 { f.write(", ") }
        unsafe { @data.read_at(i) }.debug(f)
    }
    f.write("]")
}