"""Stdlib-only tests (no pytest): plain asserts in functions called from a
__main__ block. Run: `python3 test_regex.py`.

Two jobs. First, pin the exact step counts the commentary quotes, so the
numbers on that page cannot rot silently. Second -- and this is the one that
makes the headline mean anything -- prove the two engines agree. A matcher
that is 16,000x faster and wrong is not a faster matcher, so
`test_the_engines_agree_with_each_other_and_with_cpython` brute-forces every
string up to length 6 over a 4-letter alphabet against 28 patterns and checks
all three verdicts, ours and CPython's, against each other.

That check is ~153k (pattern, text) pairs and dominates the runtime (about
half a minute). `test_the_headline_is_thirteen_million` is the slow one after
it: 58 million backtracking steps at n=22.
"""

import itertools
import re as cpython_re

from demo import pathological, thompson_steps_charging_rescans
from regex import (
    GAVE_UP,
    MATCH,
    compile_nfa,
    fullmatch,
    match_backtrack,
    match_thompson,
    nfa_states,
    to_postfix,
    CONCAT,
)

# Patterns whose semantics CPython's `re` shares exactly, so `re.fullmatch`
# can referee. `(a*)*b` is excluded and gets its own test -- not because we
# disagree with `re` about it, but because the backtracker cannot answer.
AGREEMENT_PATTERNS = (
    "a", "ab", "abc", "a|b", "ab|cd", "a*", "a+", "a?", "(a|b)*",
    "(ab)*c", "a*b*", "a(b|c)*d", ".", ".*", "a.c", ".*b.*",
    "(a|b)(c|d)", "a?b?c?", "(ab|a)*b", "(a|ab)(c|bcd)",
    "a(b(c|d)e)*f", "((a))", "x(y|z)?w", "(a|b)*abb", "a?a?a?aaa",
    ".a.", "ab*a", "(.|a)*b",
)
ALPHABET = "abcd"
MAX_LEN = 6


def test_the_engines_agree_with_each_other_and_with_cpython():
    """Brute force. The whole headline rests on this test."""
    pairs = 0
    for pattern in AGREEMENT_PATTERNS:
        nfa = compile_nfa(pattern)
        reference = cpython_re.compile(pattern)
        for length in range(MAX_LEN + 1):
            for letters in itertools.product(ALPHABET, repeat=length):
                text = "".join(letters)
                back, _ = match_backtrack(nfa, text, budget=1_000_000)
                thom, _ = match_thompson(nfa, text)
                expected = reference.fullmatch(text) is not None
                assert back == thom == expected, (pattern, text, back, thom, expected)
                pairs += 1
    assert pairs == 152_908, pairs


def test_the_headline_is_thirteen_million():
    """n=20: 13,631,486 backtracking steps against 841, same graph, same answer."""
    nfa = compile_nfa(pathological(20))
    text = "a" * 20

    assert len(nfa_states(nfa)) == 61
    back_verdict, back_steps = match_backtrack(nfa, text)
    thom_verdict, thom_steps = match_thompson(nfa, text)

    assert back_verdict is thom_verdict is True
    assert (back_steps, thom_steps) == (13_631_486, 841)
    assert back_steps // thom_steps == 16_208  # 16,208.7 -> "16,209x"


def test_the_closed_forms_reproduce_every_measured_row():
    """backtrack = (n/2+3)*2^n - 2 ; thompson = 2n(n+1) + 1.

    These are the derivations the commentary quotes instead of asserting a
    number. If they ever stop reproducing the real counts, the arithmetic in
    section 6 is wrong and this test says so.
    """
    for n in (1, 2, 3, 4, 5, 8, 10, 12, 15, 18, 20, 22):
        nfa = compile_nfa(pathological(n))
        _, back_steps = match_backtrack(nfa, "a" * n)
        _, thom_steps = match_thompson(nfa, "a" * n)
        assert back_steps == int((n / 2 + 3) * 2**n - 2), (n, back_steps)
        assert thom_steps == 2 * n * (n + 1) + 1, (n, thom_steps)

    # The simulator's bound is (states x positions): 61 x 21 = 1281, and 841
    # is comfortably under it. The backtracker respects no such bound.
    assert 841 < 61 * 21


def test_the_stricter_meter_tells_the_same_story():
    """Charging the simulator for re-reading live states costs it 420 steps.

    The disclosure in section 6: pick the harsher accounting and the ratio
    falls from 16,209x to 10,810x, which is not a different result.
    """
    nfa = compile_nfa(pathological(20))
    strict = thompson_steps_charging_rescans(nfa, "a" * 20)
    assert strict == 1_261
    assert strict - 841 == 420  # 20 characters x 21 live states rescanned
    assert 13_631_486 // strict == 10_810


def test_the_simulator_counts_arrivals_it_throws_away():
    """`add_state` ticks before the `seen` check, so dedup does not hide cost.

    `(a|a)b` on 'ab': the two branches of the alternation both arrive at the
    same `a` state, and the second arrival is discarded -- but charged.
    """
    nfa = compile_nfa("(a|a)b")
    assert len(nfa_states(nfa)) == 5
    verdict, steps = match_thompson(nfa, "ab")
    assert verdict is True
    # Five states, six arrivals: the duplicate is charged. Moving the tick
    # below the `seen` check would report 5 and quietly flatter the simulator.
    assert steps == 6


def test_backtracking_wins_on_ordinary_patterns():
    """The negative result, kept: carrying a state set is not free."""
    for pattern, text in (("a*b", "a" * 200 + "b"), (".*b", "a" * 200 + "b")):
        nfa = compile_nfa(pattern)
        _, back_steps = match_backtrack(nfa, text)
        _, thom_steps = match_thompson(nfa, text)
        assert back_steps < thom_steps, pattern
    assert fullmatch("a*b", "a" * 200 + "b", match_backtrack) == (True, 404)
    assert fullmatch("a*b", "a" * 200 + "b", match_thompson) == (True, 604)
    assert fullmatch("(a|b)*abb", "ab" * 100 + "abb", match_backtrack) == (True, 723)
    assert fullmatch("(a|b)*abb", "ab" * 100 + "abb", match_thompson) == (True, 1_223)


def test_a_pathological_pattern_needs_pathological_input():
    """One wrong character at position 0 and the exponent disappears."""
    nfa = compile_nfa(pathological(20))
    assert match_backtrack(nfa, "b" + "a" * 19) == (False, 41)
    assert match_thompson(nfa, "b" + "a" * 19) == (False, 41)
    # ...but a wrong character at the END is no help at all: every prefix
    # branch is explored before the failure is reached.
    assert match_backtrack(nfa, "a" * 19 + "b") == (False, 12_582_910)
    assert match_thompson(nfa, "a" * 19 + "b") == (False, 820)


def test_an_epsilon_cycle_defeats_backtracking_entirely():
    """`(a*)*b` has a loop that consumes nothing. Depth-first never leaves it.

    The simulator's `seen` set closes the loop after one pass, so it answers
    in single-digit steps -- and agrees with CPython, which the backtracker
    never gets the chance to do.
    """
    nfa = compile_nfa("(a*)*b")
    for text in ("", "b", "ab", "aaab", "aaac"):
        back_verdict, back_steps = match_backtrack(nfa, text, budget=50_000)
        thom_verdict, _ = match_thompson(nfa, text)
        expected = cpython_re.fullmatch("(a*)*b", text) is not None
        assert back_verdict == GAVE_UP, (text, back_verdict)
        assert back_steps == 50_001
        assert thom_verdict == expected, (text, thom_verdict, expected)


def test_the_budget_is_the_only_thing_that_stops_the_backtracker():
    """A larger budget buys strictly more steps and no more answers."""
    nfa = compile_nfa("(a*)*b")
    for budget in (10, 1_000, 250_000):
        verdict, steps = match_backtrack(nfa, "aaab", budget=budget)
        assert (verdict, steps) == (GAVE_UP, budget + 1)


def test_postfix_conversion():
    """Concatenation is invisible in the source syntax; make it visible."""
    assert to_postfix("ab") == ["a", "b", CONCAT]
    assert to_postfix("a|b") == ["a", "b", "|"]
    assert to_postfix("a*") == ["a", "*"]
    assert to_postfix("a(b|c)*d") == ["a", "b", "c", "|", "*", CONCAT, "d", CONCAT]
    # `|` binds looser than concatenation, so `ab|cd` is (ab)|(cd).
    assert to_postfix("ab|cd") == ["a", "b", CONCAT, "c", "d", CONCAT, "|"]
    # Postfix operators bind tighter than concatenation: `ab*` is a(b*).
    assert to_postfix("ab*") == ["a", "b", "*", CONCAT]


def test_construction_produces_the_expected_graph():
    """Each operator adds a fixed number of states, independent of its body."""
    assert len(nfa_states(compile_nfa("abc"))) == 4  # 3 chars + MATCH
    assert len(nfa_states(compile_nfa("a?"))) == 3  # char + SPLIT + MATCH
    assert len(nfa_states(compile_nfa("a*"))) == 3
    assert len(nfa_states(compile_nfa("a+"))) == 3
    assert len(nfa_states(compile_nfa("a|b"))) == 4  # 2 chars + SPLIT + MATCH
    # Hence the pathological family: 3 states per n, plus MATCH.
    for n in (1, 5, 20):
        assert len(nfa_states(compile_nfa(pathological(n)))) == 3 * n + 1

    # `+` reuses its body's start as the entry point; `*` does not. That one
    # difference is what makes `a+` require an `a` and `a*` not.
    assert match_thompson(compile_nfa("a+"), "")[0] is False
    assert match_thompson(compile_nfa("a*"), "")[0] is True


def test_matching_is_anchored_at_both_ends():
    """These are fullmatch semantics: a match must consume the whole input."""
    for engine in (match_backtrack, match_thompson):
        assert fullmatch("abc", "abc", engine)[0] is True
        assert fullmatch("abc", "abcd", engine)[0] is False
        assert fullmatch("abc", "xabc", engine)[0] is False
        assert fullmatch("a", "", engine)[0] is False
        # The empty pattern compiles to a bare MATCH state.
        assert fullmatch("", "", engine)[0] is True
        assert fullmatch("", "a", engine)[0] is False
    assert compile_nfa("").kind == MATCH


def test_dot_matches_any_single_character_but_only_one():
    for engine in (match_backtrack, match_thompson):
        for char in "abcXZ9 ?*|":
            assert fullmatch(".", char, engine)[0] is True, char
        assert fullmatch(".", "", engine)[0] is False
        assert fullmatch(".", "ab", engine)[0] is False
        assert fullmatch("a.c", "abc", engine)[0] is True
        assert fullmatch("a.c", "ac", engine)[0] is False


def test_the_exponent_is_made_of_branch_ORDER_not_of_backtracking():
    """Swap the two `stack.append` lines and n=20 costs 41 steps, not 13.6M.

    This is the load-bearing counterfactual. Backtracking is not exponential
    here because it backtracks; it is exponential because it tries the wrong
    arrow of every SPLIT first. Every `a?` must decline, and greedy order
    proposes "take it" 20 times before it will consider declining once.
    """
    for n, greedy_steps, lazy_steps in (
        (5, 174, 11), (10, 8_190, 21), (15, 344_062, 31), (20, 13_631_486, 41)
    ):
        nfa = compile_nfa(pathological(n))
        assert match_backtrack(nfa, "a" * n) == (True, greedy_steps)
        assert match_backtrack(nfa, "a" * n, greedy=False) == (True, lazy_steps)
    assert 13_631_486 // 41 == 332_475

    # Lazy order is not a fix, it is a different guess. On input that does NOT
    # match, no order helps: every branch has to be refuted either way.
    nfa = compile_nfa(pathological(20))
    dead = "a" * 19 + "b"
    assert match_backtrack(nfa, dead) == (False, 12_582_910)
    assert match_backtrack(nfa, dead, greedy=False) == (False, 12_582_910)


def test_branch_order_never_changes_an_answer():
    """`greedy=False` reorders the search; it cannot re-decide it."""
    pairs = 0
    for pattern in ("a?b", "(a|b)*abb", "a?a?a?aaa", "(ab|a)*b", "a*b*", "a(b|c)*d"):
        nfa = compile_nfa(pattern)
        for length in range(7):
            for letters in itertools.product("ab", repeat=length):
                text = "".join(letters)
                assert (
                    match_backtrack(nfa, text)[0]
                    == match_backtrack(nfa, text, greedy=False)[0]
                ), (pattern, text)
                pairs += 1
    assert pairs == 762


TESTS = [
    test_the_headline_is_thirteen_million,
    test_the_closed_forms_reproduce_every_measured_row,
    test_the_stricter_meter_tells_the_same_story,
    test_the_simulator_counts_arrivals_it_throws_away,
    test_backtracking_wins_on_ordinary_patterns,
    test_a_pathological_pattern_needs_pathological_input,
    test_an_epsilon_cycle_defeats_backtracking_entirely,
    test_the_budget_is_the_only_thing_that_stops_the_backtracker,
    test_postfix_conversion,
    test_construction_produces_the_expected_graph,
    test_matching_is_anchored_at_both_ends,
    test_dot_matches_any_single_character_but_only_one,
    test_the_exponent_is_made_of_branch_ORDER_not_of_backtracking,
    test_branch_order_never_changes_an_answer,
    test_the_engines_agree_with_each_other_and_with_cpython,
]


if __name__ == "__main__":
    failed = 0
    for test in TESTS:
        try:
            test()
        except AssertionError as exc:
            failed += 1
            print(f"FAIL  {test.__name__}: {exc}")
        else:
            print(f"PASS  {test.__name__}")
    if failed:
        print(f"\n{failed} of {len(TESTS)} tests FAILED")
        raise SystemExit(1)
    print(f"\nAll {len(TESTS)} tests PASSED")