#!/usr/bin/env julia
# Independent OMEGA_NAUGHT/1.0 conformance runner.
# Originating language of the exact companion. No packages beyond Julia stdlib.

using SHA

const EXPECTED_CONTRACT = "OMEGA_NAUGHT/1.0"
const EXPECTED_ALGEBRA = "Q(T)[lambda]/(lambda^2-T*lambda-T^2)"
const EXPECTED_Q = parse(BigInt, "339949771344778")
const EXPECTED_S = parse(BigInt, "1000000000000000")
const EXPECTED_L60 = "339949771344778929576702809321279193551009905014259416689444"
const EXPECTED_U60 = "339949771344778929576702809321279193551009905014259416689445"
const LEDGER_STEPS = 23
const FIRST_MISMATCH = UInt64(42_189_065)
const REQUIRED_KEYS = ("contract", "algebra", "bits", "Q", "S", "L60", "U60")

struct Manifest
    contract::String
    algebra::String
    bits::UInt32
    q::BigInt
    s::BigInt
    l60::String
    u60::String
end

canonical_unsigned(value::AbstractString) =
    !isempty(value) && all(isdigit, value) && (value == "0" || !startswith(value, '0'))

function parse_manifest(text::AbstractString)
    values = Dict{String,String}()
    for (index, raw) in enumerate(eachline(IOBuffer(text)))
        line = strip(raw)
        isempty(line) && startswith(line, '#') && continue
        isempty(line) && continue
        startswith(line, '#') && continue
        '=' in line || error("bad manifest line $(index): $(repr(raw))")
        key, value = strip.(split(line, '=', limit=2))
        (isempty(key) || isempty(value)) && error("empty manifest field on line $(index)")
        key in REQUIRED_KEYS || error("unknown manifest key: $(key)")
        haskey(values, key) && error("duplicate manifest key: $(key)")
        values[key] = value
    end
    for key in REQUIRED_KEYS
        haskey(values, key) || error("missing manifest key: $(key)")
    end
    l60, u60 = values["L60"], values["U60"]
    (canonical_unsigned(l60) && length(l60) == 60) || error("L60 must be a canonical 60-digit unsigned decimal")
    (canonical_unsigned(u60) && length(u60) == 60) || error("U60 must be a canonical 60-digit unsigned decimal")
    q = parse(BigInt, values["Q"])
    s = parse(BigInt, values["S"])
    (q > 0 && s > 0) || error("Q and S must be positive")
    Manifest(values["contract"], values["algebra"], parse(UInt32, values["bits"]), q, s, l60, u60)
end

read_manifest(path::AbstractString) = parse_manifest(read(path, String))

# Integer Laurent polynomial: sum c[e] T^e
struct Laurent
    c::Dict{Int,BigInt}
end
Laurent() = Laurent(Dict{Int,BigInt}())
function Laurent(pairs::Pair{Int,<:Integer}...)
    c = Dict{Int,BigInt}()
    for (e, v) in pairs
        v == 0 && continue
        c[e] = BigInt(v)
    end
    Laurent(c)
end
mono(exp::Int, coeff::Integer=1) = coeff == 0 ? Laurent() : Laurent(exp => coeff)

Base.:+(a::Laurent, b::Laurent) = begin
    d = copy(a.c)
    for (e, v) in b.c
        n = get(d, e, big(0)) + v
        n == 0 ? delete!(d, e) : (d[e] = n)
    end
    Laurent(d)
end
Base.:-(a::Laurent) = Laurent(Dict(e => -v for (e, v) in a.c))
Base.:-(a::Laurent, b::Laurent) = a + (-b)
function Base.:*(a::Laurent, b::Laurent)
    d = Dict{Int,BigInt}()
    for (e, x) in a.c, (f, y) in b.c
        k = e + f
        n = get(d, k, big(0)) + x * y
        n == 0 ? delete!(d, k) : (d[k] = n)
    end
    Laurent(d)
end
shift(p::Laurent, k::Int) = Laurent(Dict(e + k => v for (e, v) in p.c))
is_zero(p::Laurent) = isempty(p.c)
Base.:(==)(a::Laurent, b::Laurent) = a.c == b.c

# A(T) + B(T) lambda in Q(T)[lambda]/(lambda^2 - T lambda - T^2)
struct K
    a::Laurent
    b::Laurent
end
K() = K(Laurent(), Laurent())
oneK() = K(mono(0), Laurent())
T() = K(mono(1), Laurent())
Tinv() = K(mono(-1), Laurent())
lam() = K(Laurent(), mono(0))

Base.:+(x::K, y::K) = K(x.a + y.a, x.b + y.b)
Base.:-(x::K) = K(-x.a, -x.b)
Base.:-(x::K, y::K) = x + (-y)
function Base.:*(x::K, y::K)
    bd = x.b * y.b
    K(x.a * y.a + shift(bd, 2), x.a * y.b + x.b * y.a + shift(bd, 1))
end
is_zero(x::K) = is_zero(x.a) && is_zero(x.b)
Base.:(==)(x::K, y::K) = x.a == y.a && x.b == y.b

decimal_add_one(value::AbstractString) = string(parse(BigInt, value) + 1)

function forward_step(d::BigInt, q::BigInt, s::BigInt)
    y = q * d
    f = div(y, s)
    rho = y - s * f
    (f, rho)
end

function reverse_step(next::BigInt, remainder::BigInt, q::BigInt, s::BigInt)
    remainder < 0 && return nothing
    remainder >= s && return nothing
    num = s * next + remainder
    r = rem(num, q)
    r == 0 || return nothing
    div(num, q)
end

function unsigned_15bit_replay(m::Manifest)
    m.bits == 15 || return false
    limit = BigInt(1) << m.bits
    d = big(0)
    while d < limit
        f, rho = forward_step(d, m.q, m.s)
        (0 <= rho < m.s) || return false
        reverse_step(f, rho, m.q, m.s) == d || return false
        d += 1
    end
    true
end

function build_ledger(seed::BigInt, steps::Int, q::BigInt, s::BigInt)
    state = seed
    remainders = BigInt[]
    for _ in 1:steps
        nxt, rho = forward_step(state, q, s)
        push!(remainders, rho)
        state = nxt
    end
    (state, remainders)
end

function recover_ledger(terminal::BigInt, remainders::Vector{BigInt}, q::BigInt, s::BigInt)
    state = terminal
    for rho in Iterators.reverse(remainders)
        rec = reverse_step(state, rho, q, s)
        rec === nothing && return nothing
        state = rec
    end
    state
end

function ordered_23step_ledgers(m::Manifest)
    m.bits == 15 || return false
    limit = BigInt(1) << m.bits
    d = big(0)
    while d < limit
        terminal, remainders = build_ledger(d, LEDGER_STEPS, m.q, m.s)
        terminal == 0 || return false
        recover_ledger(terminal, remainders, m.q, m.s) == d || return false
        d += 1
    end
    true
end

function fold_bytes(bytes::Vector{UInt8}, bits::Int)
    (1 <= bits <= 16) || return nothing
    mask = (UInt64(1) << bits) - 1
    limbs = UInt16[]
    acc = UInt64(0)
    held = 0
    for byte in bytes
        acc = (acc << 8) | UInt64(byte)
        held += 8
        while held >= bits
            shift = held - bits
            push!(limbs, UInt16((acc >> shift) & mask))
            acc &= shift == 0 ? UInt64(0) : (UInt64(1) << shift) - 1
            held = shift
        end
    end
    pad = held == 0 ? 0 : bits - held
    if held != 0
        push!(limbs, UInt16((acc << pad) & mask))
    end
    (limbs, pad)
end

function unfold_bytes(limbs::Vector{UInt16}, pad_bits::Int, byte_len::Int, bits::Int)
    (1 <= bits <= 16) || return nothing
    data_bits = byte_len * 8
    expected = data_bits == 0 ? 0 : div(data_bits + bits - 1, bits)
    length(limbs) == expected || return nothing
    total_bits = length(limbs) * bits
    pad = total_bits - data_bits
    (pad < bits && pad_bits == pad) || return nothing
    limit = UInt64(1) << bits
    acc = UInt64(0)
    held = 0
    out = UInt8[]
    for limb in limbs
        UInt64(limb) < limit || return nothing
        acc = (acc << bits) | UInt64(limb)
        held += bits
        while held >= 8 && length(out) < byte_len
            shift = held - 8
            push!(out, UInt8((acc >> shift) & 0xff))
            acc &= shift == 0 ? UInt64(0) : (UInt64(1) << shift) - 1
            held = shift
        end
    end
    (length(out) == byte_len && held == pad_bits && acc == 0) || return nothing
    out
end

function canonical_byte_fold(m::Manifest)
    payload = Vector{UInt8}(codeunits("Omega Naught"))
    expected = UInt16[10_166, 22_873, 27_684, 1_254, 2_987, 7_585, 26_624]
    folded = fold_bytes(payload, Int(m.bits))
    folded === nothing && return false
    limbs, pad = folded
    limbs == expected && pad == 9 || return false
    unfolded = unfold_bytes(limbs, pad, length(payload), Int(m.bits))
    unfolded == payload || return false
    for limb in limbs
        terminal, remainders = build_ledger(BigInt(limb), LEDGER_STEPS, m.q, m.s)
        recover_ledger(terminal, remainders, m.q, m.s) == BigInt(limb) || return false
    end
    corrupted = copy(limbs)
    corrupted[end] |= 0x0001
    unfold_bytes(corrupted, pad, length(payload), Int(m.bits)) === nothing
end

function exact_floor_from_open_interval(l60::AbstractString, u60::AbstractString, d::Integer)
    d == 0 && return big(0)
    scale = big(10)^60
    lower = parse(BigInt, l60) * BigInt(d)
    upper = parse(BigInt, u60) * BigInt(d)
    lower_floor = div(lower, scale)
    upper_quot, upper_rem = divrem(upper, scale)
    upper_floor = upper_rem == 0 ? upper_quot - 1 : upper_quot
    lower_floor == upper_floor ? lower_floor : nothing
end

function canonical_hashes()
    vectors = (
        ("{\"a\":{\"den\":[\"1\"],\"num\":[\"0\"]},\"b\":{\"den\":[\"1\"],\"num\":[\"1\"]},\"basis\":\"1,lambda\"}",
         "766659b6211a5bc601f3c88e8ae97614a3fe66abc87965d78efb0af3f59e0a49"),
        ("{\"a\":{\"den\":[\"1\"],\"num\":[\"0\"]},\"b\":{\"den\":[\"0\",\"1\"],\"num\":[\"1\"]},\"basis\":\"1,lambda\"}",
         "9109f2d9f236b283767310a136314656f4b17d38f3bac1c96d4431177d3b586a"),
        ("{\"a\":{\"den\":[\"0\",\"1\"],\"num\":[\"1\"]},\"b\":{\"den\":[\"0\",\"1\"],\"num\":[\"-1\"]},\"basis\":\"1,lambda\"}",
         "815c7dd22e3b7ac29ec67a8f27398baad17dc4bc42c03a3146abb4c73e0ee163"),
    )
    all(bytes2hex(sha256(Vector{UInt8}(codeunits(record)))) == expected for (record, expected) in vectors)
end

function run_checks(m::Manifest)
    checks = Tuple{String,Bool}[]
    push!(checks, ("manifest.contract", m.contract == EXPECTED_CONTRACT))
    push!(checks, ("manifest.algebra", m.algebra == EXPECTED_ALGEBRA))
    push!(checks, ("manifest.expected_L60", m.l60 == EXPECTED_L60))
    push!(checks, ("manifest.expected_U60", m.u60 == EXPECTED_U60))
    push!(checks, ("manifest.expected_Q", m.q == EXPECTED_Q))
    push!(checks, ("manifest.expected_S", m.s == EXPECTED_S))

    one, t, ti, λ = oneK(), T(), Tinv(), lam()
    ω, τ = ti, t
    φ = λ * ti
    μ = one - λ
    πk = ω - φ

    push!(checks, ("exact.omega_tau", ω * τ == one))
    push!(checks, ("exact.lambda_mu", λ + μ == one))
    push!(checks, ("exact.lambda_relation", is_zero(λ * λ - τ * λ - τ * τ)))
    push!(checks, ("exact.phi_quadratic", is_zero(φ * φ - φ - one)))
    push!(checks, ("exact.phi_pi_omega", φ + πk == ω))

    qs = (m.s == BigInt(10)^15 && 0 <= m.q < m.s) ? string("0.", lpad(string(m.q), 15, '0')) : ""
    push!(checks, ("finite.qs_decimal", qs == "0.339949771344778"))
    push!(checks, ("finite.ledger_adjacent", decimal_add_one(m.l60) == m.u60))
    push!(checks, ("finite.qs_below_L60", m.q * BigInt(10)^45 < parse(BigInt, m.l60)))
    push!(checks, ("finite.unsigned_15bit_replay", unsigned_15bit_replay(m)))
    interval_ok = m.bits == 15
    if interval_ok
        d = big(0)
        limit = BigInt(1) << m.bits
        while d < limit
            k = exact_floor_from_open_interval(m.l60, m.u60, d)
            qf = div(m.q * d, m.s)
            if k != qf
                interval_ok = false
                break
            end
            d += 1
        end
    end
    push!(checks, ("finite.interval_floor_15bit", interval_ok))

    max15 = m.q * 32_767
    max16 = m.q * 65_535
    u64max = (BigInt(1) << 64) - 1
    push!(checks, ("finite.unsigned_15bit_u64_bounds", max15 <= u64max && max16 > u64max))
    push!(checks, ("finite.ordered_23step_ledgers", ordered_23step_ledgers(m)))
    push!(checks, ("finite.canonical_byte_fold", canonical_byte_fold(m)))

    before = FIRST_MISMATCH - 1
    exact_before = exact_floor_from_open_interval(m.l60, m.u60, before)
    exact_at = exact_floor_from_open_interval(m.l60, m.u60, FIRST_MISMATCH)
    machine_before = div(m.q * BigInt(before), m.s)
    machine_at = div(m.q * BigInt(FIRST_MISMATCH), m.s)
    push!(checks, ("finite.first_mismatch_boundary",
                   exact_before == machine_before && exact_at == 14_342_163 && machine_at == 14_342_162))
    push!(checks, ("canonical.sha256_records", canonical_hashes()))
    checks
end

function main(args)
    path = length(args) >= 1 ? args[1] : "OMEGA_NAUGHT_1_0.manifest"
    m = read_manifest(path)
    checks = run_checks(m)
    passed = all(ok for (_, ok) in checks)
    for (name, ok) in checks
        println(name, "=", ok ? "PASS" : "FAIL")
    end
    println("RESULT=", passed ? "PASS" : "FAIL")
    passed ? 0 : 1
end

if abspath(PROGRAM_FILE) == @__FILE__
    exit(main(ARGS))
end