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

std/src/collections/vec/core.nv
293 строки16 KB
Evgeniy Golovin
merge: comment-hygiene-2 — чистка комментариев std (batch 1-20) + линт-свип 330→13
01 авг 2026, 18:13
01 авг 2026, 18:13bb8b33d
// std.collections.vec (core) — `Vec[T]`, a fully Nova-implemented generic
// growable array backed by a raw `*mut T` heap buffer.
//
// Контекст. `[]T` is the
// built-in slice/dynamic-array primitive; `[]T ≡ Vec[T]`. `Vec[T]` is a
// *library* type implemented entirely in Nova on top of
// `std.runtime.raw_mem.RawMem` — a production growable collection needs no
// compiler magic beyond typed pointers, `size_of[T]()` and
// pointer arithmetic.
//
// Key property: elements are stored *typed* in a contiguous `*mut T` buffer.
// `Vec[Option[int]]`, `Vec[MyRecord]`, `Vec[Vec[int]]` all work with their
// natural per-element C representation — no int64-slot erasure. Pointer
// arithmetic `data + i` is scaled by `sizeof(T)` automatically by the C
// backend (the buffer pointer carries the element stride).
//
// Allocation. `RawMem.alloc(n)` returns 8-byte-aligned zeroed GC-tracked
// memory. The buffer is GC-tracked, so it stays alive while the `Vec`
// (and thus the `data` pointer field) is reachable. Element T values that are
// themselves heap pointers (records / sum-types / arrays) are kept alive by
// the conservative scan over the buffer.
//
// Unsafe model. Every raw-pointer operation (alloc, `data + i`,
// deref read/write) is wrapped in an `unsafe { }` block. The element-access
// API is fully safe — no `unsafe` to *use*; in-place element mutation is the
// safe `v[i] = val` (`MutIndex` write). The lone deliberate escape is the
// FFI accessor `@ptr()` (recv-mut overload: `*T` on a `ro` receiver,
// `*mut T` on a `mut` receiver) — calling it is safe (a pointer-value copy,
// not a deref), but *dereferencing* the returned pointer is the caller's
// `unsafe` obligation.

// `Vec`/`VecIter` are re-exported by
// `std/prelude.nv`. A full auto-import of `std.prelude` here would create a
// cycle (prelude → vec → prelude) and trip the auto-import opt-out for
// every importer. Mirror `range.nv`'s precedent: opt into the minimal prelude
// subset this module's API actually needs (see `_module.nv` for the
// folder-wide directive) —
//   core      → Option/Result/Ordering (return types, `@pop()->Option[T]`),
//   runtime   → kept for other prelude.runtime API surface (`panic`/`assert`
//               themselves are always-on compiler intrinsics),
//   collections→ Next/Iter protocols (VecIter) + StringBuilder (`@display`),
//   protocols → Display/Clone/Index/MutIndex (`@clone`, `@display`, `v[i]`).
// `Range` lives in the prelude facade (`std/collections/range.nv`), imported
// explicitly in `slice.nv` for the `@index(r Range)` zero-copy view.
#prelude(core, runtime, collections, protocols)
module collections.vec

import std.runtime.raw_mem.{RawMem}

// ──────────────────────────────────────────────────────────────────────────
// Type
// ──────────────────────────────────────────────────────────────────────────

/// A contiguous growable array of `T`, heap-backed via a raw `*mut T` buffer.
///
/// Amortised O(1) `push`, O(1) indexed `get`, ×2 growth. Empty `Vec[T].new()`
/// allocates nothing until the first `push` (cap = 0).
///
/// # Examples
///
/// ```nova
/// mut v = Vec[int].new()
/// v.push(1); v.push(2); v.push(3)
/// assert(v.len() == 3)
/// assert(v.get(1) == Some(2))
/// ```
export type Vec[T] priv {
    // Raw element buffer. `cap` elements wide; first `len` are live.
    // Never read/written outside `unsafe` blocks in this module.
    //
    // Declared `mut data *mut T` under the THREE-AXIS pointer model:
    //   - L1 binding-mut (`mut` before the name) makes the *field* reassignable
    //     (`@data = dst` in @cap);
    //   - L3 postfix pointee-mut (`*mut T`) makes the *pointee* writable so
    //     `@data[i] = val` (push / index-set) is a valid store.
    // Both axes are REQUIRED and INDEPENDENT — pointee-mut is NOT inherited
    // from the binding (3-axis forbids it; a bare `*T ≡ *ro T` is a ro pointee
    // regardless of the binding). A writable, reassignable buffer therefore
    // spells out both `mut` (binding) and `*mut` (pointee) explicitly.
    //
    // Codegen lowers `*mut T` to the live element C type `Nova_T*` (no
    // `const`), preserving the generic `T` through monomorphization (no
    // `Nova_any*` pointee erasure).
    mut data *mut T
    // Number of live (initialised) elements.
    mut len int
    // Number of allocated element slots (`data` capacity).
    mut cap int
}

// ──────────────────────────────────────────────────────────────────────────
// Constructors
// ──────────────────────────────────────────────────────────────────────────

/// Create a `Vec[T]` — always a single allocation of `cap.max(1)` element
/// slots (`len == 0`), no rounding. `cap == 0` (default,
/// `Vec[T].new()`): logically empty (`@cap() == 0`) but backed by a 1-slot
/// placeholder buffer — same non-null-pointer-always invariant the old
/// placeholder (ex-null_buf) path gave, just folded into this one expression; the slot is
/// never read/written until the first `@push`/`@reserve` grows it. `cap: n`
/// (`n > 0`): exactly `n` pre-allocated element slots. Equivalent to
/// `Vec[T].new().cap(n)` but one call, one allocation — the canonical
/// pre-sizing spelling (`Vec[T].new(cap: 1024)`, or positionally
/// `Vec[T].new(1024)`).
export fn Vec[T].new(cap int = 0) -> Self
    requires cap >= 0
    => { data: alloc_buf[T](cap.max(1)), len: 0, cap }

/// VIEW-form (owner 2026-07-17): zero-copy read-only view over a foreign
/// buffer — `cap == len` (does not grow), returns `ro Self` (L2: push/index-
/// write = compile error). Arity-sibling of `new(cap)` (0/1-arg) and
/// `new(ptr,len,cap)` (3-arg owned). `unsafe fn` (D216 §8, Rust-parity with
/// `slice::from_raw_parts`): the call site bears the obligation — the source
/// OUTLIVES the view (for a GC buffer the `data` field keeps it reachable), writes
/// through the view are forbidden by the source's contract. The `*T → *mut T` cast is hidden
/// in the body — the `ro` return gives no way to use it.
export unsafe fn Vec[T].new(ptr *T, len int) -> ro Self
    requires len >= 0
    => { data: unsafe { ptr as *mut T }, len, cap: len }

/// Build a `Vec[T]` directly from its three raw components — the element
/// buffer pointer, the live-element count, and the allocated capacity.
///
/// This is the cross-type bridge that lets *other* modules hand a `(ptr, len,
/// cap)` triple to a `Vec` without going through `push`/`extend`. The `data`,
/// `len` and `cap` fields are `priv` (visible only to `Vec` type-methods), so a
/// caller in another module cannot spell `Self { data: …, … }` itself — this
/// public constructor is the only sanctioned entry. It is the inverse of the
/// `@ptr()` / `@len()` / `@cap()` accessors and the analogue of Rust's
/// `Vec::from_raw_parts`.
///
/// # Contract / unsafety
///
/// Calling this is `unsafe`-obligated at the *call site*: the caller asserts
///   - `ptr` points at a live allocation of at least `cap` element slots whose
///     first `len` slots are initialised (`0 <= len <= cap`), and
///   - the pointed-to memory stays alive for the lifetime of the returned
///     `Vec` (for GC-tracked buffers the returned `Vec.data` field keeps it
///     reachable; for a zero-copy *view* over a foreign buffer — e.g.
///     `str.@bytes()` aliasing a string's internal bytes — the originating
///     owner must outlive the view, and the view must be treated read-only).
///
/// The `ptr` param is already `*mut T` (writable pointee) — no
/// reinterpret-cast needed in the body. Whether
/// the resulting buffer is *actually* writable remains the caller's
/// invariant (a `ro` view must not be pushed/index-written; binding the
/// result `ro` enforces this at L2) — passing a genuinely read-only `*T`
/// through the `*mut T` param is itself the caller's `unsafe` obligation,
/// same as before.
export fn Vec[T].new(ptr *mut T, len int, cap int) -> Self
    requires len >= 0 && cap >= len
=> { data: ptr, len, cap }

// (consume-ресивер ПОТРЕБИТЕЛЯ (напр. `[]u8
// consume @into_str_unchecked()`, runtime/string/core.nv), а указатель
// берётся обычным `mut @ptr()` (access.nv) — отдельный consume-посредник
// был лишней сущностью. Обратная операция осталась: `Vec[T].new(ptr, len,
// cap)` — конструктор-поглотитель.)

// `Vec[T].from(items []T)` — RETRACTED: это же просто `items.clone()`.
// Same-T conversion is now spelled `existing.clone()` directly (Clone
// is deep/recursive and element-wise, protocols.nv); a literal element list is
// `of(...)` (below); a width/type-changing conversion (e.g. `Vec[u8]` from a
// `Vec[int]`) is an explicit per-element loop, not a one-call narrow.

/// Ergonomic variadic constructor: `Vec[int].of(1, 2, 3)` — the **canonical**
/// way to build a `Vec` from a literal element list. The call-site variadic args
/// are collected into a single `[]T` (= `Vec[T]`) value and returned **zero-copy**
/// (one allocation): the literal `[1, 2, 3]` argument to `of` is
/// already a `Vec[int]`, and `of` takes its elements directly rather than
/// copying them into a second buffer. `of` narrows exactly like a typed literal
/// (`Vec[u8].of(1, 2, 3)`).
///
/// [M-153-vec-of-variadic-codegen] (resolved): user-defined generic-static
/// variadic collection. The call-site packs `of(1,2,3)`'s args into a single
/// collected `[]T` matching this body's `args` parameter — previously the raw
/// args were passed straight through (`_static_of(1,2,3)` → "too many
/// arguments").
///
/// D259 amend (2026-07-06): `of()` with **zero** arguments is rejected by
/// contract — an empty `.of()` call reads as an accident (did the caller mean
/// `.new()`?). Build an empty vector with `Vec[T].new()` instead.
///
/// **D259 AMEND (2026-07-20, Plan 200 П16, retract):** `Vec[T].from` — the
/// conversion-of-an-existing-collection constructor `of` used to be contrasted
/// with in this doc-comment — is **RETRACTED**: it was exactly `items.clone()`
/// (owner: "it's just items.clone()"). Converting an existing same-`T`
/// collection is now spelled `existing.clone()` directly; a width/type-changing
/// conversion (e.g. building a `Vec[u8]` from a `Vec[int]`) is an explicit
/// per-element loop, not a one-call narrow. `of` remains the sole literal-list
/// constructor.
export fn Vec[T].of(...args []T) -> Self
    requires args.len() > 0
=> args

// ──────────────────────────────────────────────────────────────────────────
// Size / introspection
// ──────────────────────────────────────────────────────────────────────────

/// Number of live elements.
export fn Vec[T] @len() -> int => @len

/// Number of allocated element slots.
export fn Vec[T] @cap() -> int => @cap

/// Set the capacity to **exactly** `n` slots (no ×2 rounding) — the precise,
/// absolute capacity request. The accessor-convention
/// write-setter: a same-name 1-arg overload of the 0-arg `@cap()`
/// getter. Reallocates the buffer, preserving the live `len` elements; `n == 0`
/// (only valid when `len == 0`) frees down to the null buffer.
///
/// Contract `n >= @len`: the capacity can never physically drop below the live
/// element count. A silent truncate/clamp there would be a footgun (it would
/// drop live elements and break the `v.cap(n); v.cap() == n` round-trip), so
/// `n < len` is a **panic**, not a clamp.
///
/// Covers — no separate methods needed:
///   - shrink-to-fit  = `v.cap(v.len())`
///   - room-for-N     = `v.cap(v.len() + n)`
/// Unlike `@reserve` (amortised ×2 growth), this honours `n` exactly, so it also
/// gives a predictable realloc point for slice detach. Returns `@`.
///
/// The getter/setter overload monomorphizes correctly: a mono'd
/// `v.cap(10)` disambiguates to this 1-arg
/// setter (not the 0-arg getter). This accessor-convention form replaced the
/// distinct `@cap_to` helper that held the place during the gap.
export fn Vec[T] mut @cap(n int) -> @
    requires n >= @len
{
    if n == @cap { return }
    if n == 0 {
        // 1-slot non-null placeholder (как в `new(cap=0)`): никогда не
        // разыменовывается — `len`/`cap` гардят каждый доступ.
        @data = alloc_buf[T](1)
        @cap = 0
        return
    }
    ro dst = alloc_buf[T](n)
    // Bulk-copy the live prefix. Source (old `@data`) and destination (fresh
    // `dst`) are distinct GC-tracked buffers, so `copy_nonoverlapping` (memcpy)
    // is safe and faster than a per-element loop. Pointer-valued elements move
    // bitwise; both buffers are reachable during the copy so the GC keeps every
    // referent alive.
    unsafe {
        RawMem.copy_n_nonoverlapping(@data, dst, @len)
    }
    @data = dst
    @cap = n
}

/// `true` if the vector has no live elements.
export fn Vec[T] @is_empty() -> bool => @len == 0

// ──────────────────────────────────────────────────────────────────────────
// Capacity management
// ──────────────────────────────────────────────────────────────────────────

/// Ensure room for at least `additional` more elements beyond the current
/// length. Grows the buffer with a ×2 strategy (initial capacity 8) when the
/// current capacity does not suffice. No-op when `additional <= 0` or capacity
/// already covers `len + additional`. This is the sole *amortised* growth method
/// (rounds the buffer up to a ×2 capacity for O(1)-amortised push); the exact,
/// un-rounded capacity setter is `@cap(n)`.
///
/// Returns `@` (self) for fluent chaining — `v.reserve(10).append(xs).sort()`
/// (fluent convention, precedent `StringBuilder.@append`).
export fn Vec[T] mut @reserve(additional int) -> @ {
    ro needed = @len + additional
    if needed <= @cap {
        return
    }
    mut new_cap = if @cap == 0 { 8 } else { @cap * 2 }
    // KEEP as while: non-unit-step (×2 doubling), not a `0..@len` index loop.
    while new_cap < needed {
        new_cap *= 2
    }
    @cap(new_cap)
}

// ──────────────────────────────────────────────────────────────────────────
// Free helpers — buffer allocation
// ──────────────────────────────────────────────────────────────────────────

// Allocate a zeroed `*mut T` buffer of `n` element slots. `n > 0`.
fn alloc_buf[T](n int) -> *mut T {
    unsafe {
        RawMem.alloc(n * size_of[T]()) as *mut T
    }
}

// (empty-cap
// placeholder = `alloc_buf[T](1)` напрямую: non-null, never-dereferenced,
// `len`/`cap` гардят каждый доступ.)