"""A regex engine built the way Ken Thompson built one in 1968: compile the
pattern to an NFA, then *walk the graph*.

There is only ONE graph here. Both matchers run on the identical NFA that
`compile_nfa` produces; they differ only in the order they walk it.
`match_backtrack` follows one path at a time and reconsiders, which is what
Perl, Java and Python's `re` do. `match_thompson` advances every path at
once, keeping a *set* of live states, which is what awk, grep and RE2 do.

THE STEP UNIT
-------------
One step = one arrival at a (state, position) pair.

Both matchers tick that same counter on that same graph, so their numbers are
directly comparable. `add_state` ticks BEFORE consulting `seen`, so arrivals
the simulator discards are still charged to it: it is not allowed to look
cheap by declining to count. (An arrival is charged once. The simulator is
not separately charged for re-reading a state already in its live list; the
commentary, section 6, prices that alternative too.)

Supported syntax: literals, `.`, `|`, `*`, `+`, `?`, `(`, `)`. Matching is
anchored at both ends -- `fullmatch` semantics, not `search`.

No clock, no randomness, no hashing: every step count here is a function of
(pattern, text) alone.
"""

# --- Parsing: infix -> postfix, so the compiler can be a flat stack machine

CONCAT = "\x01"  # concatenation is invisible in regex syntax; make it a token

BINDS = {"|": 1, CONCAT: 2, "*": 3, "+": 3, "?": 3}


def add_concat(pattern):
    """Insert an explicit CONCAT token wherever juxtaposition means "then".

    A token boundary is a concatenation unless the left side is still open
    (`(`, `|`) or the right side is a closer or a postfix operator.
    """
    out = []
    previous = None
    for char in pattern:
        if previous is not None:
            if previous not in "(|" + CONCAT and char not in ")|*+?":
                out.append(CONCAT)
        out.append(char)
        previous = char
    return "".join(out)


def to_postfix(pattern):
    """Shunting-yard. `a(b|c)*d` -> `a b c | * CONCAT d CONCAT`.

    Postfix rather than an AST because Thompson's construction is naturally a
    stack machine: each operator pops the fragments it needs and pushes one
    back, so the whole compiler below is one flat loop.
    """
    output, operators = [], []
    for char in add_concat(pattern):
        if char == "(":
            operators.append(char)
        elif char == ")":
            while operators[-1] != "(":
                output.append(operators.pop())
            operators.pop()
        elif char in BINDS:
            # `>=`, not `>`: these operators are left-associative.
            while operators and operators[-1] != "(" and BINDS[operators[-1]] >= BINDS[char]:
                output.append(operators.pop())
            operators.append(char)
        else:
            output.append(char)
    while operators:
        output.append(operators.pop())
    return output


# --- Thompson's construction: postfix -> NFA

CHAR, SPLIT, MATCH = "char", "split", "match"


class State:
    """One NFA state, in one of three kinds -- the entire vocabulary.

    CHAR consumes one character and follows `out`. SPLIT consumes nothing and
    offers two ways forward: every bit of branching in the language is this
    one state kind. MATCH accepts. `sid` exists only so the simulator can put
    states in a set cheaply.
    """

    _next_id = 0

    def __init__(self, kind, char=None):
        self.kind = kind
        self.char = char
        self.out = None
        self.out1 = None
        self.sid = State._next_id
        State._next_id += 1

    def accepts(self, char):
        """A CHAR state's test. `.` matches any single character."""
        return self.kind == CHAR and (self.char == "." or self.char == char)


class Fragment:
    """A partly-built NFA: one entry point, plus arrows with no target yet.

    `dangling` holds (state, attribute-name) pairs, not states, because an
    unfinished arrow is a *slot*. Naming the slot lets `patch` fill it later
    without the fragment knowing whether it was an `out` or an `out1`.
    """

    def __init__(self, start, dangling):
        self.start = start
        self.dangling = dangling


def patch(dangling, target):
    """Point every unfinished arrow in `dangling` at `target`."""
    for state, slot in dangling:
        setattr(state, slot, target)


def compile_nfa(pattern):
    """Build the NFA for `pattern`; return its start state.

    Every fragment has exactly one entry point and any number of exits. That
    invariant is the trick: the operators never inspect the fragments they
    combine, so each is two or three lines however large the sub-expression
    is. Note the absence of an epsilon state kind -- an epsilon transition is
    just a SPLIT, which keeps the simulator's inner loop down to two cases.
    """
    stack = []
    for token in to_postfix(pattern):
        if token == CONCAT:
            second, first = stack.pop(), stack.pop()
            patch(first.dangling, second.start)
            stack.append(Fragment(first.start, second.dangling))
        elif token == "|":
            second, first = stack.pop(), stack.pop()
            split = State(SPLIT)
            split.out, split.out1 = first.start, second.start
            stack.append(Fragment(split, first.dangling + second.dangling))
        elif token == "?":
            fragment = stack.pop()
            split = State(SPLIT)
            split.out = fragment.start
            # `out` points at the body and `out1` (the skip) is left dangling.
            # The backtracker tries `out` first, so THIS is where greed lives.
            stack.append(Fragment(split, fragment.dangling + [(split, "out1")]))
        elif token == "*":
            fragment = stack.pop()
            split = State(SPLIT)
            split.out = fragment.start
            patch(fragment.dangling, split)  # loop the body back to the split
            stack.append(Fragment(split, [(split, "out1")]))
        elif token == "+":
            fragment = stack.pop()
            split = State(SPLIT)
            split.out = fragment.start
            patch(fragment.dangling, split)
            # Identical to `*` but for the entry point: the body is traversed
            # once before the split is reached, which is what "one or more" is.
            stack.append(Fragment(fragment.start, [(split, "out1")]))
        else:
            state = State(CHAR, token)
            stack.append(Fragment(state, [(state, "out")]))

    if not stack:
        return State(MATCH)  # the empty pattern matches only the empty string
    fragment = stack.pop()
    assert not stack, f"unbalanced pattern {pattern!r}"
    accept = State(MATCH)
    patch(fragment.dangling, accept)
    return fragment.start


# --- Matcher A: backtracking -- one path at a time, depth first

GAVE_UP = "gave up"  # a third verdict, alongside True and False

DEFAULT_BUDGET = 100_000_000


def match_backtrack(start, text, budget=DEFAULT_BUDGET, greedy=True):
    """Depth-first search of the NFA. Returns (verdict, steps).

    The stack is explicit rather than recursive because that is what PCRE and
    friends actually do, and because it makes `budget` the only thing that can
    stop this function -- a `RecursionError` arriving first would disguise the
    real failure mode.

    `budget` is not a safety belt bolted on for the demo. An unbounded
    backtracker cannot terminate at all on `(a*)*b`, whose NFA holds an
    epsilon cycle it will walk forever. GAVE_UP is the honest verdict, and it
    is exactly the ReDoS timeout a production engine reports.

    `greedy` chooses which arrow of a SPLIT is explored first. It cannot
    change an answer, only the order answers are found in; it exists so the
    demo can price the identical match both ways. A real engine has no such
    freedom -- greedy order is part of what `*` MEANS once submatch capture
    exists.
    """
    steps = 0
    stack = [(start, 0)]
    while stack:
        state, pos = stack.pop()
        steps += 1
        if steps > budget:
            return GAVE_UP, steps
        if state.kind == MATCH:
            if pos == len(text):
                return True, steps
        elif state.kind == SPLIT:
            # LIFO: whichever is pushed second is explored first.
            first, second = (state.out, state.out1) if greedy else (state.out1, state.out)
            stack.append((second, pos))
            stack.append((first, pos))
        elif pos < len(text) and state.accepts(text[pos]):
            stack.append((state.out, pos + 1))
    return False, steps


# --- Matcher B: Thompson simulation -- every path at once, breadth first


def match_thompson(start, text):
    """Simulate the NFA one input character at a time. Returns (verdict, steps).

    The list of live states is the whole idea. A state can be live at a given
    position only once, so surviving arrivals are bounded by
    (states x positions) -- a product where the backtracker's cost is a power.
    That bound is the `seen` set and nothing else: delete it and this function
    reproduces `match_backtrack`'s step counts exactly.
    """
    steps = 0

    def add_state(state, live, seen):
        """Walk the epsilon closure, appending CHAR/MATCH states to `live`."""
        nonlocal steps
        steps += 1  # charged before the `seen` check, on purpose
        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:
            if state.accepts(char):
                add_state(state.out, following, seen)
        live = following
        if not live:
            break  # nothing is live; no later character can revive anything
    return any(state.kind == MATCH for state in live), steps


# --- Convenience


def fullmatch(pattern, text, engine=match_thompson, **kwargs):
    """Compile and match in one call. Returns (verdict, steps)."""
    return engine(compile_nfa(pattern), text, **kwargs)


def nfa_states(start):
    """Every state reachable from `start`, in discovery order."""
    order, seen, stack = [], set(), [start]
    while stack:
        state = stack.pop()
        if state.sid in seen:
            continue
        seen.add(state.sid)
        order.append(state)
        for nxt in (state.out1, state.out):
            if nxt is not None:
                stack.append(nxt)
    return order