arborist/tests/test_pi_star_combinatorics.py

"""combinatorics@v1 π* tests (ticket #000032).

Pure-integer counting kernel that fails closed on symbolic /
negative / non-integer outputs. Whole file skips when SymPy is
absent.
"""

from __future__ import annotations

import pytest

sympy = pytest.importorskip("sympy")  # entire file skipped if absent

from arborist.pi_star import compose, get  # noqa: E402
from arborist.pi_star.protocol import (  # noqa: E402
    PiStarError,
    assert_round_trip,
    equivalence_class_id,
)


@pytest.fixture
def ps():
    return get("combinatorics@v1")


# --- registry presence ------------------------------------------------


def test_registry_contains_combinatorics():
    ps = get("combinatorics@v1")
    assert ps.name == "combinatorics"
    assert ps.version == "v1"
    assert ps.domain == "combinatorics"


# --- positive cases — integer collapse -------------------------------


@pytest.mark.parametrize(
    "input_str,expected_int",
    [
        ("binomial(5,2)", 10),
        ("binomial(10,3)", 120),
        ("factorial(0)", 1),
        ("factorial(1)", 1),
        ("factorial(7)", 5040),
        ("binomial(0,0)", 1),
        ("binomial(7,0)", 1),
        ("binomial(7,7)", 1),
        ("binomial(5,7)", 0),  # k > n → 0
        ("catalan(0)", 1),
        ("catalan(5)", 42),
        ("bell(5)", 52),
        ("partition(7)", 15),
        # Arithmetic compositions over integer primitives.
        ("3*binomial(5,2) + factorial(4)", 54),
        ("2**10", 1024),
        ("100", 100),
    ],
)
def test_integer_collapse(ps, input_str, expected_int):
    assert ps.canonicalize(input_str.encode()) == str(expected_int).encode()


def test_byte_format_is_plain_decimal(ps):
    """Output must be the bare decimal literal — no quotes, no
    Integer(...) wrapper, no fraction-form denominator."""
    out = ps.canonicalize(b"binomial(5,2)")
    assert out == b"10"
    assert b"/" not in out
    assert b"Integer" not in out


# --- equivalence classes preserved -----------------------------------


def test_binomial_symmetry_collapses(ps):
    """C(n, k) = C(n, n-k) — same canonical bytes."""
    assert ps.canonicalize(b"binomial(7, 3)") == ps.canonicalize(b"binomial(7, 4)")
    assert (
        equivalence_class_id(ps, b"binomial(7, 3)")
        == equivalence_class_id(ps, b"binomial(7, 4)")
    )


def test_pascals_rule_holds(ps):
    """Pascal's rule: C(n,k) = C(n-1,k-1) + C(n-1,k)."""
    lhs = ps.canonicalize(b"binomial(7, 3)")
    rhs = ps.canonicalize(b"binomial(6, 2) + binomial(6, 3)")
    assert lhs == rhs


# --- distinct counts stay distinct -----------------------------------


@pytest.mark.parametrize(
    "left,right",
    [
        # Note: binomial(5,2) = binomial(5,3) by symmetry — pick a pair
        # that's actually distinct.
        ("binomial(5, 2)", "binomial(7, 2)"),
        ("factorial(5)", "factorial(6)"),
        ("catalan(5)", "catalan(6)"),
        ("partition(5)", "partition(7)"),
    ],
)
def test_distinct_counts_distinct(ps, left, right):
    assert ps.canonicalize(left.encode()) != ps.canonicalize(right.encode())


# --- round-trip / idempotence ----------------------------------------


@pytest.mark.parametrize(
    "expr",
    [
        "binomial(5, 2)",
        "factorial(7)",
        "100",
        "2**10",
        "3*binomial(5, 2) + factorial(4)",
    ],
)
def test_round_trip_idempotent(ps, expr):
    assert_round_trip(ps, expr.encode())


# --- fail-closed: symbolic results -----------------------------------


@pytest.mark.parametrize(
    "expr",
    [
        "binomial(n, k)",       # both symbolic
        "factorial(n)",         # symbolic
        "factorial(n + 1)",     # symbolic
        "binomial(5, k)",       # one symbolic
        "x + 1",                # not combinatorial at all, still symbolic
    ],
)
def test_symbolic_input_rejected(ps, expr):
    with pytest.raises(PiStarError, match="not a concrete integer"):
        ps.canonicalize(expr.encode())


# --- fail-closed: non-integer / generalized inputs -------------------


def test_negative_result_rejected(ps):
    """Hand-crafted: factorial(4) - 100 = -76 → counting domain rejects."""
    with pytest.raises(PiStarError, match="negative"):
        ps.canonicalize(b"factorial(4) - 100")


def test_generalized_binomial_non_integer_rejected(ps):
    """binomial(Rational(1,2), 3) = 1/16 — SymPy supports the
    generalized binomial via Gamma; combinatorics@v1 rejects
    non-integer outputs."""
    with pytest.raises(PiStarError, match="not a concrete integer"):
        ps.canonicalize(b"binomial(Rational(1,2), 3)")


def test_rational_arithmetic_rejected(ps):
    """1/2 reduces to a Rational — not an Integer, rejected."""
    with pytest.raises(PiStarError, match="not a concrete integer"):
        ps.canonicalize(b"1/2")


def test_generalized_binomial_negative_args_accepted_when_integer(ps):
    """SymPy's binomial extends to negative integers via Gamma; the
    output of binomial(-3, 2) is the integer 6. Counting-domain
    semantics would arguably reject negative-argument binomials, but
    the kernel's fail-closed rule is on the OUTPUT shape (integer
    vs. not), not input. Document the boundary explicitly."""
    # binomial(-3, 2) = 6 as an integer — the kernel accepts.
    out = ps.canonicalize(b"binomial(-3, 2)")
    assert out == b"6"


# --- fail-closed: parse / shape errors -------------------------------


def test_empty_input_raises(ps):
    with pytest.raises(PiStarError, match="empty"):
        ps.canonicalize(b"")
    with pytest.raises(PiStarError, match="empty"):
        ps.canonicalize(b"   \n\t  ")


def test_unparseable_input_raises(ps):
    with pytest.raises(PiStarError, match="cannot parse"):
        ps.canonicalize(b"$$$ % nope")


def test_non_bytes_input_raises(ps):
    with pytest.raises(PiStarError, match="expects bytes"):
        ps.canonicalize("not bytes")  # type: ignore[arg-type]


def test_relational_input_rejected(ps):
    with pytest.raises(PiStarError, match="boolean/relational"):
        ps.canonicalize(b"x > 0")


# --- composition -----------------------------------------------------


def test_composes_with_arithmetic_for_byte_identical_witness():
    """combinatorics@v1 ∘ arithmetic@v1 — counting output (b"10")
    becomes arithmetic-route bytes (b"10/1") so the multi-modality
    witness can pin equivalence-class agreement when both routes
    fire on the same question."""
    chain = compose("combinatorics@v1", "arithmetic@v1")
    assert chain.canonicalize(b"binomial(5, 2)") == b"10/1"
    assert chain.canonicalize(b"factorial(7)") == b"5040/1"
    assert chain.canonicalize(b"binomial(0, 0)") == b"1/1"