"""Run one NFA two ways and price the walk.

The default output is deterministic: every number below is a step count, and
a step count is a pure function of (pattern, text). Run it twice, diff it,
get nothing.

Wall-clock seconds are deliberately NOT part of that output. They are a
property of a machine, not of an algorithm, so they live behind
`python3 demo.py --timing` and the commentary quotes them only under a
declared hardware banner.
"""

import sys
import time

from regex import (
    CHAR,
    GAVE_UP,
    MATCH,
    SPLIT,
    compile_nfa,
    match_backtrack,
    match_thompson,
    nfa_states,
)


def pathological(n):
    """`a?`x n followed by `a`x n -- the standard ReDoS demonstration pattern.

    Against `a`x n it matches, but only one of the 2^n ways of distributing
    the input over the `a?`s works: every `a?` must decline. A greedy
    backtracker tries them in exactly the wrong order.
    """
    return "a?" * n + "a" * n


def draw_nfa(pattern):
    """Print the compiled graph as an adjacency listing."""
    states = nfa_states(compile_nfa(pattern))
    index = {state.sid: i for i, state in enumerate(states)}
    print(f"  NFA for {pattern!r}  ({len(states)} states)")
    for i, state in enumerate(states):
        if state.kind == MATCH:
            print(f"    {i:>2}  MATCH")
        elif state.kind == CHAR:
            print(f"    {i:>2}  char {state.char!r:>4}  --> {index[state.out.sid]}")
        else:
            print(
                f"    {i:>2}  SPLIT       --> {index[state.out.sid]}"
                f"  (or {index[state.out1.sid]})"
            )


def thompson_steps_charging_rescans(start, text):
    """The alternative accounting, so section 6 can quote it honestly.

    Identical to `match_thompson` except it also charges one step every time
    a state already in the live list is re-read during the character scan.
    This is a *stricter* meter than the one the headline uses; it is here to
    show the headline does not depend on the choice.
    """
    steps = 0

    def add_state(state, live, seen):
        nonlocal steps
        steps += 1
        if state.sid in seen:
            return
        seen.add(state.sid)
        if state.kind == SPLIT:
            add_state(state.out, live, seen)
            add_state(state.out1, live, seen)
        else:
            live.append(state)

    live, seen = [], set()
    add_state(start, live, seen)
    for char in text:
        following, seen = [], set()
        for state in live:
            steps += 1  # <-- the only line that differs
            if state.accepts(char):
                add_state(state.out, following, seen)
        live = following
        if not live:
            break
    return steps


def verdict(value):
    return {True: "match", False: "no match", GAVE_UP: "GAVE UP"}[value]


SWEEP = (1, 2, 3, 4, 5, 8, 10, 12, 15, 18, 20, 22)

# (label, pattern, text) for the boundary table.
ORDINARY = (
    ("a*b", "a" * 200 + "b"),
    (".*b", "a" * 200 + "b"),
    ("(a|b)*abb", "ab" * 100 + "abb"),
    ("a" * 40, "a" * 40),
)


def main():
    print("one NFA, two walks -- step counts only (no clock, no RNG)")
    print("  1 step = one arrival at a (state, position) pair, in BOTH engines")
    print()

    draw_nfa("a?a?aa")
    print("    ...that is pathological(2). The demo below grows n.")
    print()

    print("pathological: ('a?' * n) + ('a' * n)  against  'a' * n  (it MATCHES)")
    print(
        f"  {'n':>3}{'states':>8}{'|text|':>8}{'backtrack':>14}"
        f"{'thompson':>10}{'ratio':>13}  agree"
    )
    rows = []
    for n in SWEEP:
        nfa = compile_nfa(pathological(n))
        text = "a" * n
        back_v, back_s = match_backtrack(nfa, text)
        thom_v, thom_s = match_thompson(nfa, text)
        assert back_v == thom_v, (n, back_v, thom_v)
        rows.append((n, back_s, thom_s))
        print(
            f"  {n:>3}{len(nfa_states(nfa)):>8}{len(text):>8}{back_s:>14,}"
            f"{thom_s:>10,}{back_s / thom_s:>12,.1f}x  {back_v == thom_v}"
        )

    print()
    print("both curves have closed forms, checked against every row above:")
    print("  backtrack = (n/2 + 3) * 2**n - 2      thompson = 2n(n+1) + 1")
    for n, back_s, thom_s in rows:
        b = int((n / 2 + 3) * 2**n - 2)
        t = 2 * n * (n + 1) + 1
        assert (b, t) == (back_s, thom_s), (n, b, t, back_s, thom_s)
    print(f"  all {len(rows)} rows reproduced exactly by the formulas")

    n = 20
    back_s, thom_s = next((b, t) for k, b, t in rows if k == n)
    print()
    print(f"THE HEADLINE, at n={n}:")
    print(f"  backtrack  (n/2+3)*2^n - 2 = 13*1048576 - 2 = {back_s:>12,} steps")
    print(f"  thompson   2*{n}*{n + 1} + 1         =  840 + 1     = {thom_s:>12,} steps")
    print(f"  ratio {back_s / thom_s:,.0f}x, on the same graph, for the same answer")

    strict = thompson_steps_charging_rescans(compile_nfa(pathological(n)), "a" * n)
    print()
    print("  disclosure -- the simulator's meter, charged more harshly:")
    print(f"    also charging for re-reading a live state: {strict:,} steps")
    print(f"    the ratio becomes {back_s / strict:,.0f}x instead of {back_s / thom_s:,.0f}x")

    print()
    print("WHAT THE EXPONENT IS ACTUALLY MADE OF -- swap two lines in the")
    print("backtracker so a SPLIT tries `out1` before `out`, and nothing else:")
    print(f"  {'n':>3}{'greedy (as shipped)':>22}{'skip-first':>14}{'change':>14}")
    for n in (5, 10, 15, 20):
        nfa = compile_nfa(pathological(n))
        text = "a" * n
        greedy_v, greedy_s = match_backtrack(nfa, text)
        lazy_v, lazy_s = match_backtrack(nfa, text, greedy=False)
        assert greedy_v == lazy_v == True
        print(f"  {n:>3}{greedy_s:>22,}{lazy_s:>14,}{greedy_s // lazy_s:>13,}x")
    print("  Same engine, same graph, same verdict. The blow-up is not caused by")
    print("  backtracking -- it is caused by backtracking in the WRONG ORDER.")
    print("  (And that order is not a free choice: greedy is what `*` MEANS")
    print("   once a real engine has to report capture groups.)")

    print()
    print("  ...but reordering is a different guess, not a cure. On input that")
    print("  does NOT match, every branch must be refuted whichever way you go:")
    nfa = compile_nfa(pathological(20))
    dead = "a" * 19 + "b"
    print(f"    n=20, text='a'*19+'b'   greedy={match_backtrack(nfa, dead)[1]:>12,}"
          f"   skip-first={match_backtrack(nfa, dead, greedy=False)[1]:>12,}")

    print()
    print("BOUNDARY 1 -- on ordinary patterns the BACKTRACKER wins:")
    print(f"  {'pattern':<14}{'|text|':>8}{'backtrack':>12}{'thompson':>10}{'bt/th':>9}")
    for pattern, text in ORDINARY:
        nfa = compile_nfa(pattern)
        back_v, back_s = match_backtrack(nfa, text)
        thom_v, thom_s = match_thompson(nfa, text)
        assert back_v == thom_v
        label = pattern if len(pattern) <= 13 else pattern[:8] + f"..({len(pattern)})"
        print(f"  {label:<14}{len(text):>8}{back_s:>12,}{thom_s:>10,}{back_s / thom_s:>8.2f}x")
    print("  ...the set costs more to carry than it saves, when only one path is live.")

    print()
    print("BOUNDARY 2 -- the pathological pattern needs pathological INPUT:")
    nfa = compile_nfa(pathological(20))
    inputs = (
        ("'a'*20         ", "a" * 20),
        ("'b' + 'a'*19   ", "b" + "a" * 19),
        ("'a'*19 + 'b'   ", "a" * 19 + "b"),
    )
    for label, text in inputs:
        back_v, back_s = match_backtrack(nfa, text)
        thom_v, thom_s = match_thompson(nfa, text)
        assert back_v == thom_v
        print(
            f"  text={label} {verdict(back_v):<9}"
            f" backtrack={back_s:>12,}  thompson={thom_s:>6,}"
        )
    print("  a leading 'b' kills every branch at position 0: 41 steps, not 13 million.")

    print()
    print("THE OTHER FAILURE MODE -- an epsilon cycle, `(a*)*b`:")
    nfa = compile_nfa("(a*)*b")
    for text in ("b", "aaab", "aaac"):
        back_v, back_s = match_backtrack(nfa, text, budget=100_000)
        thom_v, thom_s = match_thompson(nfa, text)
        print(
            f"  text={text!r:<7} backtrack={verdict(back_v):<9}({back_s:>7,} steps)"
            f"   thompson={verdict(thom_v):<9}({thom_s:>3} steps)"
        )
    print("  `(a*)*` loops with no input consumed. Depth-first walks that loop")
    print("  forever; the budget is the only reason the first column terminates.")

    if "--timing" in sys.argv:
        timings()


def timings():
    """Wall clock. Machine-dependent, therefore quarantined behind a flag."""
    import re as cpython_re

    print()
    print("--- WALL CLOCK (machine-dependent; declare your hardware) ---")
    print(f"  python {sys.version.split()[0]}  {sys.platform}")
    n = 20
    nfa = compile_nfa(pathological(n))
    text = "a" * n
    start = time.perf_counter()
    match_backtrack(nfa, text)
    back_t = time.perf_counter() - start
    start = time.perf_counter()
    match_thompson(nfa, text)
    thom_t = time.perf_counter() - start
    print(f"  n={n}  backtrack {back_t:>8.3f}s   thompson {thom_t:.6f}s"
          f"   ({back_t / thom_t:,.0f}x)")

    print()
    print("  CPython's own `re` on the same family (it backtracks too):")
    for n in (16, 18, 20, 22, 24):
        pattern, text = pathological(n), "a" * n
        start = time.perf_counter()
        matched = cpython_re.fullmatch(pattern, text)
        elapsed = time.perf_counter() - start
        print(f"    n={n:>2}  re.fullmatch {elapsed:>8.3f}s   match={matched is not None}")
    print("  each +2 in n multiplies the time by ~4. That is 2^n with a fast constant.")


if __name__ == "__main__":
    main()