std/src/testing/property.nv - main - nv-lang/nova

std/src/testing/property.nv
382 строки14 KB
Evgeniy Golovin
merge: comment-hygiene-2 — чистка комментариев std (batch 1-20) + линт-свип 330→13
01 авг 2026, 18:13
01 авг 2026, 18:13bb8b33d
// std/testing/property.nv — property-based testing для Nova.
//
// Аналог QuickCheck (Haskell) / Hypothesis (Python) / proptest (Rust),
// но реализованный через handler-substitution Random/Fail эффектов —
// без mock-библиотек, без macros, без monkey-patching. Это
// AI-first демонстрация: то что в других языках требует обхода
// type-system, в Nova естественно через эффекты.
//
// Использование:
//
//   import std.testing.property
//
//   test "list reverse twice = identity" {
//       property[[]int]() { xs =>
//           assert_prop(xs.reverse().reverse() == xs)
//       }
//   }
//
// При запуске prop-runner:
//   1. Генерирует N (default 100) случайных []int через Random handler.
//   2. Прогоняет body с каждым.
//   3. Если body упал через assert_prop — runner ловит Fail и
//      делает shrinking (бисекция к меньшим вариантам), репортит
//      минимальный failing input.
//   4. Деteminизм через `with Random = th.seeded(seed) { ... }` — тот же
//      seed даёт тот же набор входов, удобно для CI.

module testing.property

// ──────────────────────────────────────────────────────────────────────────
// Конфигурация
// ──────────────────────────────────────────────────────────────────────────

/// Property-based test config. Defaults: 100 cases, 1000 shrink steps, seed=0
/// (use ambient Random handler).
#stable(since = "0.1")
export type PropertyConfig {
    ro num_tests int
    ro max_shrink_steps int
    ro seed u64
}

/// Default PropertyConfig (100 cases, 1000 shrink, seed=0).
#stable(since = "0.1")
export fn PropertyConfig.default() -> PropertyConfig =>
    {
        num_tests: 100,
        max_shrink_steps: 1000,
        seed: 0,
    }

/// Thrown from `assert_prop` on failure. The runner catches it and starts shrinking.
#stable(since = "0.1")
export type PropertyFailed {
    ro message str
    ro context str
}

/// Create PropertyFailed with a message. The context is filled in by the runner.
#stable(since = "0.1")
export fn PropertyFailed.new(msg str) -> PropertyFailed =>
    { message: msg, context: "" }

/// Property-test assertion. Throws PropertyFailed on false — the runner catches it +
/// shrinks it (vs. a plain `assert(...)` which panics without shrinking).
#stable(since = "0.1")
export fn assert_prop(cond bool) Fail[PropertyFailed] -> () { // [M-lint-findings-fail-public-signature]
    if !cond {
        throw PropertyFailed.new("property predicate failed")
    }
}

/// Like `assert_prop` but with a custom message.
#stable(since = "0.1")
export fn assert_prop_msg(cond bool, msg str) Fail[PropertyFailed] -> () { // [M-lint-findings-fail-public-signature]
    if !cond {
        throw PropertyFailed.new(msg)
    }
}

/// Generator[T] structural protocol — for property-based testing.
///
/// `generate()` — a pure function from the ambient Random → a value `T`.
/// `shrink(v)` — an iterator of "smaller" variants for bisection on failure.
#stable(since = "0.1")
export type Generator[T] protocol {
    @generate() Random -> T
    @shrink(value T) -> []T
}

// ──────────────────────────────────────────────────────────────────────────
// Встроенные генераторы для примитивов
// ──────────────────────────────────────────────────────────────────────────

/// Uniform int generator in the range `[min, max]`. Shrinks toward 0 / the bounds.
#stable(since = "0.1")
export type IntGen {
    ro min int
    ro max int
}

/// Create IntGen with a custom range.
#stable(since = "0.1")
export fn IntGen.new(min int, max int) -> IntGen =>
    { min, max }

/// Default IntGen — `[-1000, 1000]` (typical for tests).
#stable(since = "0.1")
export fn IntGen.default() -> IntGen =>
    IntGen.new(-1000, 1000)

/// Generate a uniform int in `[min, max]`.
#stable(since = "0.1")
export fn IntGen @generate() Random -> int {
    ro range = @max - @min + 1
    ro raw = (Random.u64() as int)
    @min + (raw.abs() % range)
}

/// Shrink int — towards 0, half, value±1.
#stable(since = "0.1")
export fn IntGen @shrink(value int) -> []int {
    // Шринкаем к 0 — стандартная стратегия для интов
    mut steps []int = []
    if value > 0 {
        steps.push(0)
        if value > 1 { steps.push(value / 2) }
        if value > 2 { steps.push(value - 1) }
    } else if value < 0 {
        steps.push(0)
        if value < -1 { steps.push(value / 2) }
        if value < -2 { steps.push(value + 1) }
    }
    steps
}

/// Bool generator: `p_percent`% true (default 50/50). Shrinks toward false.
///
/// [2026-07-08, batch 3 172.13]: it was `type BoolGen { }` (no fields) — but the
/// EMPTY record literal (`{ }` / `BoolGen { }`) is not supported by the grammar
/// in any position (parses as an empty block → unit); this was the
/// only empty record in the whole std. The `p_percent` field is an honest
/// degree of freedom following the neighbors' pattern (IntGen min/max, StrGen max_len),
/// an analogue of QuickCheck frequency.
#stable(since = "0.1")
export type BoolGen {
    ro p_percent int
}

/// Create BoolGen — 50/50 true/false.
#stable(since = "0.1")
export fn BoolGen.new() -> BoolGen => { p_percent: 50 }

/// Create BoolGen with a given probability of true (in percent, 0..100).
#stable(since = "0.1")
export fn BoolGen.with_percent(p int) -> BoolGen => { p_percent: p }

/// Generate random bool (`p_percent`% true).
#stable(since = "0.1")
export fn BoolGen @generate() Random -> bool =>
    (Random.u64() % 100) < (@p_percent as u64)

/// Shrink bool — `true` → `false`, `false` → nothing.
#stable(since = "0.1")
export fn BoolGen @shrink(value bool) -> []bool {
    mut steps []bool = []
    if value { steps.push(false) }
    steps
}

/// Str generator — printable ASCII of length `[0, max_len]`. Shrinks toward "" / short prefixes.
#stable(since = "0.1")
export type StrGen {
    ro max_len int
}

/// Create StrGen with a custom max length.
#stable(since = "0.1")
export fn StrGen.new(max_len int) -> StrGen =>
    { max_len }

/// Default StrGen — max 64 chars.
#stable(since = "0.1")
export fn StrGen.default() -> StrGen =>
    StrGen.new(64)

/// Generate random ASCII string `[0..max_len]`.
#stable(since = "0.1")
export fn StrGen @generate() Random -> str {
    ro len = (Random.u64() as int).abs() % (@max_len + 1)
    consume buf = StringBuilder.new()
    for i in 0..len {
        // Печатные ASCII: 32..126 — каждый valid 1-byte UTF-8 char.
        // Plan 34 Ф.5.2: `int as char` запрещён D54.
        ro code = 32 + ((Random.u64() as int).abs() % 95)
        ro c = code.to_char() ?? '?'
        buf.append(c)
    }
    buf
}

/// Shrink string — "" / half / one shorter.
#stable(since = "0.1")
export fn StrGen @shrink(value str) -> []str {
    mut steps []str = []
    ro len = value.byte_len()
    if len > 0 {
        steps.push("")                                  // пустая строка
        if len > 1 { steps.push(value[..len / 2]) }    // половина
        if len > 1 { steps.push(value[..len - 1]) }    // на 1 короче
    }
    steps
}

/// Array generator — `[]T` of length `[0, max_len]`. Each element via the `elem` generator.
/// Shrinks toward the empty array / smaller ones.
///
/// [2026-07-08, batch 3 172.13]: it was `ro elem Generator[T]` (a protocol as a
/// FIELD/PARAMETER TYPE) — but Nova protocols are compile-time-only (D53), and
/// protocol-typed values have NO runtime dispatch: `@elem.generate()`
/// was emitted as NULL. The canon is a bounded generic (`G Generator[T]`, static
/// dispatch on the concrete generator type, like `Vec@extend[S Iter[T]]`).
#stable(since = "0.1")
export type ArrayGen[G Generator[T], T] {
    ro elem G
    ro max_len int
}

/// Create ArrayGen with a custom elem generator + max length.
#stable(since = "0.1")
export fn ArrayGen[G, T].new(elem G, max_len int) -> ArrayGen[G, T] =>
    { elem, max_len }

/// Default ArrayGen — max 32 elements.
#stable(since = "0.1")
export fn ArrayGen[G, T].default(elem G) -> ArrayGen[G, T] =>
    ArrayGen[G, T].new(elem, 32)

/// Generate a random `[]T` of length `[0, max_len]` (each elem via a nested generator).
#stable(since = "0.1")
export fn ArrayGen[G, T] @generate() Random -> []T {
    ro len = (Random.u64() as int).abs() % (@max_len + 1)
    mut result []T = []
    for i in 0..len {
        result.push(@elem.generate())
    }
    result
}

/// Shrink array — empty / halves / without the last.
#stable(since = "0.1")
export fn ArrayGen[G, T] @shrink(value []T) -> [][]T {
    mut steps [][]T = []
    ro len = value.len()
    if len > 0 {
        // Пустой массив
        steps.push([])
        // Половина (первая)
        if len > 1 {
            mut half []T = []
            half.append(value[..len / 2])
            steps.push(half)
        }
        // Без последнего элемента
        if len > 1 {
            mut shorter []T = []
            shorter.append(value[..len - 1])
            steps.push(shorter)
        }
    }
    steps
}

// ──────────────────────────────────────────────────────────────────────────
// Property runner
// ──────────────────────────────────────────────────────────────────────────

// Внутренний результат прогона одного case'а.
type RunResult enum
    | Pass
    | Fail(PropertyFailed)

// Прогнать body один раз, поймав Fail.
fn run_once[T](body fn(T) Fail[PropertyFailed] -> (), value T) -> RunResult {
    with Fail[PropertyFailed] = |e| interrupt Fail(e) {
        body(value)
        Pass
    }
}

// Поиск минимального failing input через bisection. Шринкаем
// рекурсивно: на каждом шаге пробуем все shrink-варианты, берём
// первый который тоже падает, и шринкаем его дальше. Останавливаемся
// когда варианты исчерпаны или достигли лимита.
// [2026-07-08, батч 3 172.13]: `gen Generator[T]` (протокол как тип
// параметра) → bounded generic `[G Generator[T], T]` — см. ArrayGen выше
// (D53: у протокольных ЗНАЧЕНИЙ нет runtime-диспетча; bounded generic =
// статический диспетч через мономорфизацию по конкретному G).
// D246-амендмент ([M-ro-launder-via-mut-binding], Ф.2 миграция, 2026-07-23):
// `initial`/`initial_failure` — `mut` (in-out; D326-ревизия §Р3) — `T`
// генерик не статически value-safe, `PropertyFailed` — heap record; тело
// делает `mut current = initial` затем чисто reassign (`current = candidate`),
// требуя mut-content-view источника.
fn shrink_loop[G Generator[T], T](gen G,
                  body fn(T) Fail[PropertyFailed] -> (),
                  mut initial T,
                  mut initial_failure PropertyFailed,
                  max_steps int) -> (T, PropertyFailed) {
    mut current = initial
    mut current_failure = initial_failure
    mut steps = 0

    loop {
        if steps >= max_steps { break }

        mut found_smaller = false
        for candidate in gen.shrink(current) {
            if steps >= max_steps { break }
            steps += 1

            match run_once(body, candidate) {
                Pass => ()
                Fail(e) => {
                    current = candidate
                    current_failure = e
                    found_smaller = true
                    break
                }
            }
        }

        if !found_smaller { break }
    }

    (current, current_failure)
}

// Главный API: прогнать property-test.
//
/// Run a property test — `num_tests` cases via the generator + body. On failure —
/// shrinking → throw `PropertyFailed` with the minimal example.
///
/// Uses the ambient Random → deterministic under `with Random = th.seeded(...)`.
///
/// # Examples
/// ```nova
/// with Random = th.seeded(42) {
///     property(IntGen.default(), |n| {
///         assert_prop(n + 0 == n)
///     })
/// }
/// ```
#stable(since = "0.1")
export fn property[G Generator[T], T](gen G,
                      body fn(T) Fail[PropertyFailed] -> ()) Random Fail[PropertyFailed] -> () {
    property_with(gen, body, PropertyConfig.default())
}

/// Like `property` but with a custom `PropertyConfig` (num_tests/shrink_steps/seed).
#stable(since = "0.1")
export fn property_with[G Generator[T], T](gen G,
                            body fn(T) Fail[PropertyFailed] -> (),
                            cfg PropertyConfig) Random Fail[PropertyFailed] -> () {
    for i in 0..cfg.num_tests {
        // D246-амендмент ([M-ro-launder-via-mut-binding], Ф.2 миграция,
        // 2026-07-23): `value`/`e` — `mut`, чтобы дойти до shrink_loop'а
        // теперь-mut параметров без coercion-ошибки (in-out, D326-ревизия §Р3).
        mut value = gen.generate()
        match run_once(body, value) {
            Pass => ()
            Fail(mut e) => {
                ro (minimal, final_failure) = shrink_loop(
                    gen, body, value, e, cfg.max_shrink_steps,
                )
                throw PropertyFailed {
                    message: final_failure.message,
                    context: "minimal failing input found after shrinking",
                }
            }
        }
    }
}