"""Reference solution — Incremental Tokenizer over a Chunked Stream.

DO NOT READ BEFORE YOU HAVE RUN THE PROBLEM UNDER THE CLOCK.
Teaching text: ../../../WARMUP.md § Chapter 6.

Everything about this problem is the case where a token straddles a chunk
boundary. A regex cannot do it: a regex matches against a COMPLETE string and
has no way to express "no match YET", so given a buffer ending mid-token it
cannot distinguish "not a token" from "not a token so far".

A character-level state machine handles it naturally, because the STATE
SURVIVES between chunks. End a chunk in ESCAPED and you resume the next chunk
in ESCAPED, with no special-casing at all. That property is why every real
streaming parser -- HTTP, JSON, protobuf framing -- is a hand-written state
machine rather than a regex.

Events are 4-tuples: (kind, text, depth, offset). The offset is absolute across
every chunk, because "invalid character" at byte 4,821,993 of a stream is
actionable and "invalid character" is not, and it costs one integer.
"""

from __future__ import annotations

DEFAULT, IN_STRING, ESCAPED, RESYNC = 0, 1, 2, 3

_ESCAPES = {"n": "\n", "t": "\t", "r": "\r"}


class Tokenizer:
    """Chunk-boundary-safe tokenizer: quoting, escapes, nesting, recovery."""

    def __init__(self, delimiters=" \t\n\r,", max_token_bytes=1 << 20,
                 recover=False):
        self._delims = set(delimiters)
        self._max = max_token_bytes
        self._recover = recover
        self._state = DEFAULT
        self._token = []
        self._token_start = 0
        self._depth = 0
        self._offset = 0
        self._closed = False
        self._dropped = False

    # ---- helpers ---------------------------------------------------------
    def _flush_bare(self, out):
        if self._token:
            out.append(("bare", "".join(self._token), self._depth,
                        self._token_start))
            self._token = []

    def _overflow_check(self):
        if len(self._token) > self._max:
            offset = self._offset
            if self._recover:
                self._token = []
                self._state = RESYNC
                self._dropped = True
                return ("error", f"token exceeded {self._max} bytes", self._depth,
                        offset)
            raise ValueError(
                f"token exceeded {self._max} bytes at offset {offset}; a token "
                f"this long is malformed in this grammar")
        return None

    # ---- the state machine ----------------------------------------------
    def feed(self, chunk):
        if self._closed:
            raise RuntimeError("tokenizer is closed")
        out = []
        for ch in chunk:
            self._offset += 1
            here = self._offset - 1

            if self._state == RESYNC:
                # Discard until something that can only be a structural
                # boundary, then resume. Emit a gap so the consumer knows.
                if ch in self._delims or ch in "[]{}":
                    self._state = DEFAULT
                    if self._dropped:
                        out.append(("gap", None, self._depth, here))
                        self._dropped = False
                    if ch in "[{":
                        self._depth += 1
                        out.append(("open", ch, self._depth, here))
                    elif ch in "]}":
                        out.append(("close", ch, self._depth, here))
                        self._depth = max(0, self._depth - 1)
                continue

            if self._state == DEFAULT:
                if ch == '"':
                    self._flush_bare(out)
                    self._state = IN_STRING
                    self._token_start = here
                elif ch in "[{":
                    self._flush_bare(out)
                    self._depth += 1
                    out.append(("open", ch, self._depth, here))
                elif ch in "]}":
                    self._flush_bare(out)
                    out.append(("close", ch, self._depth, here))
                    self._depth = max(0, self._depth - 1)
                elif ch in self._delims:
                    self._flush_bare(out)
                else:
                    if not self._token:
                        self._token_start = here
                    self._token.append(ch)
                    event = self._overflow_check()
                    if event:
                        out.append(event)

            elif self._state == IN_STRING:
                if ch == "\\":
                    self._state = ESCAPED       # the state SURVIVES the chunk
                elif ch == '"':
                    out.append(("string", "".join(self._token), self._depth,
                                self._token_start))
                    self._token = []
                    self._state = DEFAULT
                else:
                    self._token.append(ch)
                    event = self._overflow_check()
                    if event:
                        out.append(event)

            else:                               # ESCAPED
                self._token.append(_ESCAPES.get(ch, ch))
                self._state = IN_STRING
                event = self._overflow_check()
                if event:
                    out.append(event)
        return out

    def close(self):
        if self._closed:
            return []
        self._closed = True
        out = []

        if self._state in (IN_STRING, ESCAPED):
            if not self._recover:
                raise ValueError(
                    f"stream ended mid-string at offset {self._offset}")
            out.append(("error", "unterminated string", self._depth, self._offset))
            self._token = []
            self._state = DEFAULT

        self._flush_bare(out)

        if self._depth:
            if not self._recover:
                raise ValueError(
                    f"stream ended with {self._depth} unclosed container(s) "
                    f"at offset {self._offset}")
            out.append(("error", f"{self._depth} unclosed container(s)",
                        self._depth, self._offset))
        return out

    # ---- introspection ---------------------------------------------------
    @property
    def offset(self):
        return self._offset

    @property
    def depth(self):
        return self._depth