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

std/src/collections/vec/access.nv
266 строк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 (access) — element access: index/get/first/last/as_ptr.
//
// `v[i]` (panic on OOB) and `v.get(i)` (safe `Option`) are the read pair.
// In-place element mutation is `v[i] = val` (`MutIndex`). There is NO
// `first_mut`/`get_mut`: Nova's value model has no borrow to hand back —
// mutate through `v[i] = x`, `mut @index`, or a `mut []T` view (slice.nv).
#prelude(core, runtime, collections, protocols)
module collections.vec

// ──────────────────────────────────────────────────────────────────────────
// Access
// ──────────────────────────────────────────────────────────────────────────

/// Element at `i` by value — panics on OOB. Powers `v[i]` (`@index` magic).
///
/// The bounds check is a `requires` contract: Z3-proven `v[i]` sites elide it
/// (zero-cost), unproven sites keep a runtime check in debug AND release. This
/// also covers DIRECT `v.index(i)` calls now that contract-enforcement IS
/// emitted for generic-type monomorphized bodies — so the transitional
/// hand-written `if…panic` guard is removed; the custom message keeps the panic
/// text.
///
/// # Examples
///
/// ```nova
/// let v = Vec[int].of(10, 20, 30)
/// assert(v[0] == 10)
/// assert(v[2] == 30)
/// ```
export fn Vec[T] @index(i int) -> T
    requires 0 <= i && i < @len
{
    unsafe { @data.read_at(i) }
}

/// Element at `i` by value, or `None` if out of bounds.
export fn Vec[T] @get(i int) -> Option[T] {
    if 0 <= i && i < @len {
        return Some(unsafe { @data.read_at(i) })
    }
    None
}

/// Write `v[i] = val` — panics on OOB. Powers `v[i] = val` (`MutIndex` magic).
///
/// NAMING: this is the third `@index` overload — a `mut @index(key, val)` write
/// that coexists with the scalar read `@index(i) -> T` and the range read
/// `@index(r Range) -> Vec` (slice.nv). Full-signature overload mangling for
/// generic-type methods gives each overload a distinct C symbol, so the prior
/// collision is resolved. `v[i] = val` is still codegen-inlined
/// (`Stmt::Assign` + `ExprKind::Index`) and does not dispatch through this
/// method, but the name conforms to the `a.@index(key, val)` protocol contract.
export fn Vec[T] mut @index(i int, val T) -> ()
    requires 0 <= i && i < @len
{
    unsafe {
        @data.write_at(i, val)
    }
}

/// First element by value, or `None` if empty.
export fn Vec[T] @first() -> Option[T] => @get(0)

/// Last element by value, or `None` if empty (`@get` guards OOB, incl. `-1` on empty).
export fn Vec[T] @last() -> Option[T] => @get(@len - 1)

/// `true` if any element equals `v` — a linear O(n) scan via `==`. Works for any
/// element type with `==` defined (all primitives + `Equal` types); opaque types
/// degrade to reference identity, exactly like `@equal` (protocols.nv). A faster
/// sorted `binary_search` is a future followup.
///
/// ```nova
/// let v = Vec[int].of(10, 20, 30)
/// assert(v.contains(20))
/// assert(!v.contains(99))
/// ```
export fn Vec[T] @contains(v T) -> bool {
    // Typed local so `==` dispatches on element type `T`; a method/operator kept
    // *inside* the `unsafe` deref misresolves in codegen (same idiom as @equal).
    for i in 0..@len {
        ro e = unsafe { @data.read_at(i) }
        if e == v {
            return true
        }
    }
    false
}

// ─── Search & query (read-only) ───────────────────────────────────────

/// First index whose element equals `v`, or `None`. Linear O(n) `==` scan
/// (same dispatch rules as `@contains`). For sorted data prefer `@binary_search`.
///
/// ```nova
/// let v = Vec[int].of(10, 20, 30, 20)
/// assert(v.index_of(20) == Some(1))
/// assert(v.index_of(99) == None)
/// ```
export fn Vec[T] @index_of(v T) -> Option[int] {
    for i in 0..@len {
        ro e = unsafe { @data.read_at(i) }
        if e == v {
            return Some(i)
        }
    }
    None
}

/// First index whose element satisfies `pred`, or `None`. Linear O(n).
export fn Vec[T] @position(pred fn(T) -> bool) -> Option[int] {
    for i in 0..@len {
        ro e = unsafe { @data.read_at(i) }
        if pred(e) {
            return Some(i)
        }
    }
    None
}

/// **Last** index whose element satisfies `pred`, or `None`. Scans from the
/// back, O(n).
export fn Vec[T] @rposition(pred fn(T) -> bool) -> Option[int] {
    mut i = @len
    while i > 0 {
        i -= 1
        ro e = unsafe { @data.read_at(i) }
        if pred(e) {
            return Some(i)
        }
    }
    None
}

/// `true` if elements are in non-decreasing order by the element's own
/// `Compare` (`a.compare(b) <= 0` for every adjacent pair). Empty / single
/// element are sorted. O(n).
export fn Vec[T Compare] @is_sorted() -> bool {
    if @len < 2 {
        return true
    }
    for i in 1..@len {
        ro a = unsafe { @data.read_at(i - 1) }
        ro b = unsafe { @data.read_at(i) }
        if a.compare(b) > 0 {
            return false
        }
    }
    true
}

/// `true` if non-decreasing under `cmp` (`cmp(a, b) <= 0` for every adjacent
/// pair). `cmp` returns `<0` / `0` / `>0` (no `Ordering` type). O(n).
export fn Vec[T] @is_sorted_by(cmp fn(T, T) -> int) -> bool {
    if @len < 2 {
        return true
    }
    for i in 1..@len {
        ro a = unsafe { @data.read_at(i - 1) }
        ro b = unsafe { @data.read_at(i) }
        if cmp(a, b) > 0 {
            return false
        }
    }
    true
}

/// Binary search a **sorted** `Vec` for `x` (element's own `Compare`). Returns
/// `Ok(i)` if found (`i` = an index of a match), else `Err(i)` where `i` is the
/// insertion point keeping order. O(log n). Unspecified result if not sorted.
///
/// ```nova
/// let v = Vec[int].of(1, 3, 5, 7)
/// assert(v.binary_search(5) == Ok(2))
/// assert(v.binary_search(4) == Err(2))   // would insert at index 2
/// ```
export fn Vec[T Compare] @binary_search(x T) -> Result[int, int] {
    mut lo = 0
    mut hi = @len
    while lo < hi {
        ro mid = lo + (hi - lo) / 2
        ro e = unsafe { @data.read_at(mid) }
        ro c = e.compare(x)
        if c == 0 {
            return Ok(mid)
        }
        if c < 0 {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    Err(lo)
}

/// Binary search with a comparator: `cmp(elem)` returns the order of `elem`
/// **relative to the target** (`<0` elem before target, `>0` after, `0` match).
/// `Ok(i)` / `Err(insertion_point)`. O(log n).
export fn Vec[T] @binary_search_by(cmp fn(T) -> int) -> Result[int, int] {
    mut lo = 0
    mut hi = @len
    while lo < hi {
        ro mid = lo + (hi - lo) / 2
        ro e = unsafe { @data.read_at(mid) }
        ro c = cmp(e)
        if c == 0 {
            return Ok(mid)
        }
        if c < 0 {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    Err(lo)
}

/// Binary search by a projected key: compares `key(elem)` against `k` via the
/// key type's own `Compare`. `Ok(i)` / `Err(insertion_point)`. O(log n) plus the
/// `key` cost per probe.
export fn Vec[T] @binary_search_by_key[K Compare](key fn(T) -> K, k K) -> Result[int, int] {
    mut lo = 0
    mut hi = @len
    while lo < hi {
        ro mid = lo + (hi - lo) / 2
        ro e = unsafe { @data.read_at(mid) }
        ro ek = key(e)
        ro c = ek.compare(k)
        if c == 0 {
            return Ok(mid)
        }
        if c < 0 {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    Err(lo)
}

/// Raw read-only pointer to the element buffer, for FFI / interop with C
/// `(ptr, len)` APIs. The `ro` receiver yields a `*T` (canonical ro pointer,
/// `*T ≡ *ro T`; ABI `const T*`).
///
/// SAFE to call — extracting the pointer *value* is not a dereference.
/// Dereferencing the returned pointer (`*p`, `p.read()`, `p + i`) needs an
/// `unsafe { }` block, and the caller owns these invariants:
///   - Only `[0, len())` element slots are live; never read past `len()`.
///   - The pointer is INVALIDATED by any reallocating mutation
///     (`push`/`reserve`/`insert`/`new().cap(n)` growth). Re-fetch after such.
///   - On an empty `Vec` (`cap == 0`) `@data` is the 1-slot placeholder (ex-null_buf) —
///     non-null but a single never-live slot; do not dereference it.
///
/// The recv-mut companion `mut @ptr() -> *mut T` (below) yields a writable
/// `*mut T` when called on a `mut`-bound receiver (recv-mut overload dispatch).
// Vec[T] implements AsSlice[T]: exposes @ptr() + @len() pair for
// bulk RawMem.copy operations (used by @append).
#impl(AsSlice[T])
export fn Vec[T] @ptr() -> *T => @data

/// Raw mutable pointer to the element buffer — the writable recv-mut overload
/// of `@as_ptr`. Selected when the receiver is `mut`-bound; yields `*mut T`
/// (ABI `T*`) so a `p.write(v)` / `*p = v` store is permitted under `unsafe`.
///
/// SAFE to call; same dereference-needs-unsafe and reachability-invalidation /
/// empty-`Vec` caveats as the `ro` overload above.
export fn Vec[T] mut @ptr() -> *mut T => @data