std/src/runtime/string/search.nv - main - nv-lang/nova

std/src/runtime/string/search.nv
277 строк10 KB
Evgeniy Golovin
style(std): D452 — migrate to canonical match-arm/statement separators
10 авг 2026, 03:57
10 авг 2026, 03:57685589a
// Co-equal file of module `runtime.string` (folder = one module).
// Role: search + split (byte-offset).
//
// `str` Nova-body methods. #no_prelude breaks the prelude->string->prelude
// import cycle.

#no_prelude
module runtime.string

import std.prelude.core.{Option, Some, None}
import std.collections.vec.{Vec}
import std.runtime.raw_mem.{RawMem}

// `SplitIter`/`RSplitIter`: the TYPES + `#impl(Next[str])` live in
// `std.collections.vec_iter` (a sibling opt-in module), NOT here — this
// module is `#no_prelude` and links into every compiled program, so it must
// not drag `Next`/the generic-over-source adapter family (with its closure-
// carrying siblings `MapIter`/`FilterIter`/…) into every program's merged
// compilation unit. Cross-module cycles are resolver-legal; this is a plain
// forward reference to a type name. See vec_iter.nv's header for the full
// rationale.
import std.collections.vec_iter.{SplitIter, RSplitIter}

// True если строка начинается с prefix. Byte-compare через RawMem.compare
// (memcmp) вместо byte-loop. `@ptr`/`prefix.ptr` — priv `*ro u8`
// (type-method privacy; ptr — не size-accessor).
export fn str @starts_with(prefix str) -> bool {
    ro (sn, pn) = (@byte_len(), prefix.byte_len())
    if pn > sn { return false }
    unsafe { RawMem.compare(@ptr, prefix.ptr, pn) == 0 }
}

// True если строка заканчивается на suffix. RawMem.compare последних
// `fn_len` байт (`@ptr.offset(base)`).
export fn str @ends_with(suffix str) -> bool {
    ro (sn, fn_len) = (@byte_len(), suffix.byte_len())
    if fn_len > sn { return false }
    unsafe { RawMem.compare(@ptr.offset((sn - fn_len)), suffix.ptr, fn_len) == 0 }
}

// True если needle встречается в строке. Per-position RawMem.compare
// (memcmp) вместо вложенного byte-loop. Пустой needle → true.
export fn str @contains(needle str) -> bool {
    ro nn = needle.byte_len()
    if nn == 0 { return true }
    ro sn = @byte_len()
    if nn > sn { return false }
    mut i = 0
    while i + nn <= sn {
        if unsafe { RawMem.compare(@ptr.offset(i), needle.ptr, nn) == 0 } { return true }
        i += 1
    }
    false
}

// БАЙТОВЫЙ offset первого вхождения needle. None если нет. Возвращает
// byte-offset (композируется с `s[k..]` за O(1) — cp-offset был несоставим со
// slice; для ASCII byte-offset == прежний cp-offset). Haystack и needle —
// валидный UTF-8, поэтому совпадение на byte-позиции i всегда на
// codepoint-границе → byte-by-byte скан корректен.
export fn str @find(needle str) -> Option[int] {
    ro nn = needle.byte_len()
    if nn == 0 { return Some(0) }
    ro sn = @byte_len()
    if nn > sn { return None }
    mut i = 0
    while i + nn <= sn {
        if unsafe { RawMem.compare(@ptr.offset(i), needle.ptr, nn) == 0 } { return Some(i) }
        i += 1
    }
    None
}

// БАЙТОВЫЙ offset последнего вхождения needle. Byte-offset (как @find).
// Пустой needle → byte-длина (Rust-parity `"abc".rfind("")==Some(3)`).
// Backward scan: O(n) with early exit on first (rightmost) match.
export fn str @rfind(needle str) -> Option[int] {
    ro (sn, nn) = (@byte_len(), needle.byte_len())
    if nn == 0 { return Some(sn) }
    if nn > sn { return None }
    mut i = sn - nn
    while i >= 0 {
        if unsafe { RawMem.compare(@ptr.offset(i), needle.ptr, nn) == 0 } { return Some(i) }
        i -= 1
    }
    None
}

// Split по separator — LAZY (Rust `str::split` parity). Returns a
// `SplitIter` (zero-copy, zero-heap value iterator; see vec_iter.nv) instead
// of a materialized `Vec[str]` — drive it with `for`/`.next()`, or
// `.collect()` for the old eager `Vec[str]`. Semantics unchanged from the
// retired eager body: empty `sep` → one element (the whole string); else
// non-overlapping matches (N matches ⇒ N+1 segments, trailing segment always
// yielded — even if empty).
export fn str @split(sep str) -> SplitIter =>
    { src: @, sep, start: 0, done: false, limit: -1, splits: 0, terminator: false }

// Module-private: ASCII whitespace (space + \t\n\v\f\r). These bytes are < 0x80,
// so they never appear as UTF-8 continuation bytes — a byte-scan is codepoint-safe.
fn is_ascii_ws(b int) -> bool => b == 32 || (b >= 9 && b <= 13)

// Split into AT MOST `n` parts; the last part is the unsplit remainder (Rust
// `splitn`). `n == 0` → empty iterator; `n == 1` / empty sep → whole string
// (one element). `n < 0` — contract violation: negative part-count is a
// caller bug, not a graceful degenerate case.
export fn str @splitn(n int, sep str) -> SplitIter
    requires n >= 0
    => { src: @, sep, start: 0, done: false, limit: n.max(0), splits: 0, terminator: false }

// Split from the RIGHT, parts in REVERSE order (Rust `rsplit`). Empty sep →
// whole (one element).
export fn str @rsplit(sep str) -> RSplitIter =>
    { src: @, sep, end: @byte_len(), done: false, limit: -1, splits: 0 }

// `rsplit` into AT MOST `n` parts (reverse order). `n == 0` → empty iterator;
// `n == 1` / empty sep → whole. `n < 0` — contract violation.
export fn str @rsplitn(n int, sep str) -> RSplitIter
    requires n >= 0
    => { src: @, sep, end: @byte_len(), done: false, limit: n.max(0), splits: 0 }

// Split at the FIRST occurrence of `sep` → `Some((before, after))`, `None` if
// not found. Byte-offsets, zero-copy views (Rust `split_once`).
export fn str @split_once(sep str) -> Option[(str, str)] {
    match @find(sep) {
        Some(k) => Some((@[..k], @[k + sep.byte_len() ..]))
        None    => None
    }
}

// Split at the LAST occurrence of `sep` → `Some((before, after))`, `None` if
// not found (Rust `rsplit_once`).
export fn str @rsplit_once(sep str) -> Option[(str, str)] {
    match @rfind(sep) {
        Some(k) => Some((@[..k], @[k + sep.byte_len() ..]))
        None    => None
    }
}

// Substring BEFORE the first occurrence of `sep`
// (whole string if not found). Convenience pair with `@after` — unlike
// `@split_once` (which returns `None` on a miss), both stay TOTAL: a missing
// separator means "no split happened", so `@until` returns the whole string
// and `@after` returns `""`.
export fn str @until(sep str) -> str {
    match @find(sep) {
        Some(k) => @[..k]
        None    => @
    }
}

// Substring AFTER the first occurrence of `sep` (`""` if not found). See `@until`.
export fn str @after(sep str) -> str {
    match @find(sep) {
        Some(k) => @[k + sep.byte_len() ..]
        None    => ""
    }
}

// Like `split`, but a trailing empty segment (when the string ends with `sep`)
// is omitted (Rust `split_terminator`).
// `"a,b,".split_terminator(",").collect() == ["a","b"]`.
export fn str @split_terminator(sep str) -> SplitIter =>
    { src: @, sep, start: 0, done: false, limit: -1, splits: 0, terminator: true }

// Split on runs of ASCII whitespace, skipping empty segments (leading/trailing WS
// ignored). Rust/Go `Fields`/`split_ascii_whitespace`. Non-ASCII Unicode
// whitespace — Phase B (delegates to std/unicode).
export fn str @split_ascii_whitespace() -> ro []str {
    mut out = []str.new()
    ro (bytes, sn) = (@bytes(), @byte_len())
    mut i = 0
    while i < sn {
        while i < sn && is_ascii_ws(bytes[i] as int) { i += 1 }
        if i >= sn { break }
        ro start = i
        while i < sn && !is_ascii_ws(bytes[i] as int) { i += 1 }
        out.push(@[start..i])
    }
    out
}

// Split into lines, each WITHOUT its terminator. Handles `\n` and `\r\n` (the
// trailing `\r` is stripped). A final line without a trailing newline is included;
// the empty string yields no lines (Rust `lines`).
export fn str @lines() -> ro []str {
    mut out = []str.new()
    ro (bytes, sn) = (@bytes(), @byte_len())
    if sn == 0 { return out }
    mut start = 0
    mut i = 0
    while i < sn {
        if (bytes[i] as int) == 10 {
            mut end = i
            if end > start && (bytes[end - 1] as int) == 13 { end -= 1 }
            out.push(@[start..end])
            i += 1
            start = i
        } else {
            i += 1
        }
    }
    if start < sn { out.push(@[start..sn]) }
    out
}

// Байтовые offset'ы всех non-overlapping вхождений `needle` (Rust `match_indices`,
// но только offset'ы). Пустой needle → пусто. Композируется со slice.
export fn str @match_indices(needle str) -> []int {
    mut out = []int.new()
    ro nn = needle.byte_len()
    if nn == 0 { return out }
    ro sn = @byte_len()
    mut i = 0
    while i + nn <= sn {
        if unsafe { RawMem.compare(@ptr.offset(i), needle.ptr, nn) == 0 } {
            out.push(i)
            i += nn
        } else {
            i += 1
        }
    }
    out
}

// Char overloads for @contains/@starts_with/@ends_with.
// decode_utf8 — peer-fn from chars.nv (same runtime.string folder module).

// True if string contains codepoint `c` — UTF-8 scan.
export fn str @contains(c char) -> bool {
    ro (bytes, n) = (@bytes(), @byte_len())
    ro cp = c as int
    mut i = 0
    while i < n {
        ro (decoded, step) = decode_utf8(bytes, i, n)
        if decoded == cp { return true }
        i += step
    }
    false
}

// True if string starts with codepoint `c`.
export fn str @starts_with(c char) -> bool {
    if @is_empty() { return false }
    ro bytes = @bytes()
    ro (first_cp, _) = decode_utf8(bytes, 0, @byte_len())
    first_cp == (c as int)
}

// True if string ends with codepoint `c`.
export fn str @ends_with(c char) -> bool {
    if @is_empty() { return false }
    ro (bytes, n) = (@bytes(), @byte_len())
    mut i = n - 1
    while i > 0 && ((bytes[i] as int) & 0xC0) == 0x80 { i -= 1 }
    ro (last_cp, _) = decode_utf8(bytes, i, n)
    last_cp == (c as int)
}

// Все вхождения `needle` как подстроки (zero-copy views) — Rust `matches`.
// Пустой needle → пусто.
export fn str @matches(needle str) -> ro []str {
    mut out = []str.new()
    ro nn = needle.byte_len()
    if nn == 0 { return out }
    ro sn = @byte_len()
    mut i = 0
    while i + nn <= sn {
        if unsafe { RawMem.compare(@ptr.offset(i), needle.ptr, nn) == 0 } {
            out.push(@[i..i + nn])
            i += nn
        } else {
            i += 1
        }
    }
    out
}