"""Reference solution — the LLM gateway and model abstraction layer.

The gateway is the platform's choke point, in the good sense: one place to enforce, one
place to observe, one place to change providers. It owns normalization, routing,
budget-aware fallback, caching, rate limiting, quotas, token accounting and cost
attribution — and it is the only component that knows which provider actually ran.

Deterministic: the clock is injected, providers are scripted, and money is integer
micro-USD so accumulated cost is exact. ``python solution.py`` runs a worked session.
"""

from __future__ import annotations

import hashlib
import math
from dataclasses import dataclass, field, replace
from enum import Enum
from typing import Callable, Dict, Iterable, List, Mapping, Optional, Sequence, Tuple

# ======================================================================================
# 1. The normalized request/response — the abstraction layer proper
# ======================================================================================


class TaskClass(str, Enum):
    """What the caller is doing. Routing keys off this, not off a model name."""

    CHAT = "chat"
    EXTRACTION = "extraction"
    SUMMARIZATION = "summarization"
    CLASSIFICATION = "classification"
    REASONING = "reasoning"
    EMBEDDING = "embedding"


@dataclass(frozen=True)
class Message:
    role: str          # "system" | "user" | "assistant" | "tool"
    content: str


@dataclass(frozen=True)
class NormalizedRequest:
    """One request shape for every provider.

    The fields that are NOT about the model — tenant, agent, classification, residency,
    latency budget, side_effecting — are why this type exists. A provider SDK's request
    object cannot carry them, and every one of them is load-bearing for routing, caching
    or safety.
    """

    messages: Tuple[Message, ...]
    task_class: TaskClass
    tenant: str
    agent_id: str
    max_output_tokens: int = 512
    temperature: float = 0.0
    data_classification: str = "internal"
    residency: str = "any"              # "any" | a region the data must stay in
    latency_budget_ms: int = 3000
    side_effecting: bool = False        # this call will trigger a tool that changes state
    cacheable: bool = True

    def __post_init__(self) -> None:
        if not self.messages:
            raise ValueError("a request needs at least one message")
        if self.max_output_tokens <= 0:
            raise ValueError("max_output_tokens must be > 0")
        if not 0.0 <= self.temperature <= 2.0:
            raise ValueError("temperature must be in [0, 2]")
        if self.latency_budget_ms <= 0:
            raise ValueError("latency_budget_ms must be > 0")

    def prompt_text(self) -> str:
        return "\n".join(f"{m.role}: {m.content}" for m in self.messages)

    def stable_prefix(self) -> str:
        """Everything before the last user turn — the cacheable part.

        Prefix caching rewards putting stable content (system prompt, tool schemas)
        first and volatile content last. This method encodes that assumption.
        """
        return "\n".join(f"{m.role}: {m.content}" for m in self.messages[:-1])


class FinishReason(str, Enum):
    """Normalized finish reasons. Providers disagree wildly on the strings; the caller
    must not have to care, and `LENGTH` in particular must be detectable because it means
    the answer is truncated."""

    STOP = "stop"
    LENGTH = "length"
    TOOL_CALL = "tool_call"
    CONTENT_FILTER = "content_filter"


@dataclass(frozen=True)
class Usage:
    input_tokens: int = 0
    cached_input_tokens: int = 0
    output_tokens: int = 0

    def __post_init__(self) -> None:
        if min(self.input_tokens, self.cached_input_tokens, self.output_tokens) < 0:
            raise ValueError("token counts must be >= 0")
        if self.cached_input_tokens > self.input_tokens:
            raise ValueError("cached_input_tokens cannot exceed input_tokens")

    @property
    def total(self) -> int:
        return self.input_tokens + self.output_tokens


@dataclass(frozen=True)
class NormalizedResponse:
    text: str
    finish_reason: FinishReason
    usage: Usage
    deployment: str
    provider: str
    model: str
    latency_ms: int
    cost_micros: int = 0
    cache: str = "miss"                 # "miss" | "exact" | "semantic"
    attempts: Tuple[str, ...] = ()      # deployments tried, in order


# ======================================================================================
# 2. Normalized errors — the hard half of a model abstraction layer
# ======================================================================================


class GatewayError(Exception):
    retryable = False
    fall_over = False       # may we try the NEXT deployment?

    def __init__(self, message: str, *, provider: str = "") -> None:
        super().__init__(message)
        self.message = message
        self.provider = provider


class RateLimited(GatewayError):
    """HTTP 429 from a provider. Retryable, and a reason to move on."""
    retryable = True
    fall_over = True


class ProviderTimeout(GatewayError):
    retryable = True
    fall_over = True


class ProviderUnavailable(GatewayError):
    """5xx."""
    retryable = True
    fall_over = True


class ContentFiltered(GatewayError):
    """The provider's own safety system refused.

    NOT retryable and NOT a reason to fall over: trying another provider until one
    answers is 'shopping for a compliant model', which is exactly the behaviour a
    regulator would ask you about.
    """
    retryable = False
    fall_over = False


class InvalidRequest(GatewayError):
    """4xx that is our fault. Retrying sends the same bad request."""
    retryable = False
    fall_over = False


class QuotaExceeded(GatewayError):
    retryable = False
    fall_over = False


class NoRouteAvailable(GatewayError):
    retryable = False
    fall_over = False


class BudgetExhausted(GatewayError):
    """The latency budget ran out before a fallback could be attempted."""
    retryable = False
    fall_over = False


# ======================================================================================
# 3. Deployments and providers
# ======================================================================================


class Capacity(str, Enum):
    PAYG = "payg"                  # shared pool, per-token billing
    PROVISIONED = "provisioned"    # PTUs / provisioned throughput
    SELF_HOSTED = "self_hosted"    # your GPUs


@dataclass(frozen=True)
class Deployment:
    """One addressable place a request can go.

    A 'model' is not a routing target — a *deployment* is. The same model in two regions
    with two capacity types has two different latencies, two different prices and two
    different residency answers.
    """

    name: str
    provider: str                  # azure | bedrock | openai | anthropic | vertex | cohere
    model: str
    region: str
    capacity: Capacity
    input_micros_per_1k: int
    cached_input_micros_per_1k: int
    output_micros_per_1k: int
    expected_latency_ms: int
    max_classification: str = "restricted"
    weight: int = 1

    def cost_micros(self, usage: Usage) -> int:
        fresh = usage.input_tokens - usage.cached_input_tokens
        total = (fresh * self.input_micros_per_1k
                 + usage.cached_input_tokens * self.cached_input_micros_per_1k
                 + usage.output_tokens * self.output_micros_per_1k)
        return total // 1000


#: A provider adapter: takes the normalized request, returns a normalized response.
#: Raising a GatewayError subclass is how a provider reports failure — normalizing the
#: error taxonomy is the part of an abstraction layer that actually earns its keep.
ProviderAdapter = Callable[[NormalizedRequest, Deployment], NormalizedResponse]


_CLASSIFICATION_ORDER = ("public", "internal", "confidential", "restricted")


def classification_rank(name: str) -> int:
    try:
        return _CLASSIFICATION_ORDER.index(name)
    except ValueError:
        raise ValueError(f"unknown data classification: {name!r}") from None


# ======================================================================================
# 4. Routing
# ======================================================================================


@dataclass(frozen=True)
class RoutingRule:
    """Match on what the caller *is*, not on what model it wants.

    A caller that names a model has hard-coded a vendor decision into an agent, and you
    will find every one of those references the day you need to migrate.
    """

    name: str
    deployments: Tuple[str, ...]        # ordered: primary first, then fallbacks
    task_classes: Tuple[TaskClass, ...] = ()
    tenants: Tuple[str, ...] = ()
    classifications: Tuple[str, ...] = ()   # empty = any; else an exact membership test
    priority: int = 100                 # lower wins

    def __post_init__(self) -> None:
        for name in self.classifications:
            classification_rank(name)   # reject a typo at construction, not at 3 a.m.

    def matches(self, request: NormalizedRequest) -> bool:
        if self.task_classes and request.task_class not in self.task_classes:
            return False
        if self.tenants and request.tenant not in self.tenants:
            return False
        if self.classifications and request.data_classification not in self.classifications:
            return False
        return True


class Router:
    """Turns a request into an ordered list of candidate deployments."""

    def __init__(self, deployments: Mapping[str, Deployment], rules: Sequence[RoutingRule]) -> None:
        self.deployments = dict(deployments)
        for rule in rules:
            unknown = set(rule.deployments) - set(self.deployments)
            if unknown:
                raise ValueError(f"rule {rule.name!r} names unknown deployments: {sorted(unknown)}")
        self.rules = sorted(rules, key=lambda r: (r.priority, r.name))

    def candidates(self, request: NormalizedRequest) -> List[Deployment]:
        """The ordered fallback chain, after applying the constraints a rule cannot
        express: residency and per-deployment classification ceilings."""
        for rule in self.rules:
            if not rule.matches(request):
                continue
            chain = [self.deployments[name] for name in rule.deployments]
            chain = [d for d in chain if self._admissible(d, request)]
            if chain:
                return chain
        return []

    def _admissible(self, deployment: Deployment, request: NormalizedRequest) -> bool:
        if request.residency != "any" and deployment.region != request.residency:
            return False
        if classification_rank(deployment.max_classification) < classification_rank(request.data_classification):
            return False
        return True


# ======================================================================================
# 5. Rate limiting and quotas
# ======================================================================================


class TokenBucket:
    """Capacity ``C``, refill rate ``r`` per second. Never goes negative."""

    def __init__(self, capacity: float, refill_per_second: float, *, now: Callable[[], float]) -> None:
        if capacity <= 0 or refill_per_second <= 0:
            raise ValueError("capacity and refill_per_second must be > 0")
        self.capacity = float(capacity)
        self.refill_per_second = float(refill_per_second)
        self.now = now
        self.tokens = float(capacity)
        self.last = now()

    def _refill(self) -> None:
        current = self.now()
        elapsed = max(0.0, current - self.last)
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_per_second)
        self.last = current

    def try_consume(self, amount: float) -> bool:
        if amount < 0:
            raise ValueError("amount must be >= 0")
        self._refill()
        if self.tokens >= amount:
            self.tokens -= amount
            return True
        return False

    def retry_after_seconds(self, amount: float) -> float:
        self._refill()
        deficit = amount - self.tokens
        return max(0.0, deficit / self.refill_per_second)


@dataclass
class TenantLimits:
    """Both limits are needed. One request can be 100 000 tokens, so an RPM-only limit
    does not protect the provider — and a TPM-only limit does not protect you from a
    flood of tiny requests."""

    requests_per_minute: int
    tokens_per_minute: int
    monthly_budget_micros: int


class RateLimiter:
    def __init__(self, limits: Mapping[str, TenantLimits], *, now: Callable[[], float]) -> None:
        self.limits = dict(limits)
        self.now = now
        self._rpm: Dict[str, TokenBucket] = {}
        self._tpm: Dict[str, TokenBucket] = {}

    def _buckets(self, tenant: str) -> Tuple[TokenBucket, TokenBucket]:
        limits = self.limits.get(tenant)
        if limits is None:
            raise QuotaExceeded(f"tenant {tenant!r} has no configured limits")
        if tenant not in self._rpm:
            self._rpm[tenant] = TokenBucket(limits.requests_per_minute,
                                            limits.requests_per_minute / 60.0, now=self.now)
            self._tpm[tenant] = TokenBucket(limits.tokens_per_minute,
                                            limits.tokens_per_minute / 60.0, now=self.now)
        return self._rpm[tenant], self._tpm[tenant]

    def admit(self, tenant: str, estimated_tokens: int) -> None:
        """Raise RateLimited if either bucket refuses. Consumes only when BOTH admit —
        otherwise a rejected request still spends the request budget."""
        rpm, tpm = self._buckets(tenant)
        if rpm.tokens < 1 or tpm.tokens < estimated_tokens:
            rpm._refill()
            tpm._refill()
            if rpm.tokens < 1:
                raise RateLimited(
                    f"tenant {tenant!r} over request rate; retry after "
                    f"{rpm.retry_after_seconds(1):.2f}s")
            if tpm.tokens < estimated_tokens:
                raise RateLimited(
                    f"tenant {tenant!r} over token rate; retry after "
                    f"{tpm.retry_after_seconds(estimated_tokens):.2f}s")
        rpm.try_consume(1)
        tpm.try_consume(estimated_tokens)


class QuotaLedger:
    """Per-tenant monthly spend, with a hard stop.

    Unbounded consumption is an availability risk as much as a budget one: one tenant
    burning the provider's shared capacity degrades everybody.
    """

    def __init__(self, limits: Mapping[str, TenantLimits]) -> None:
        self.limits = dict(limits)
        self._spent: Dict[str, int] = {}

    def check(self, tenant: str) -> None:
        limits = self.limits.get(tenant)
        if limits is None:
            raise QuotaExceeded(f"tenant {tenant!r} has no configured budget")
        if self._spent.get(tenant, 0) >= limits.monthly_budget_micros:
            raise QuotaExceeded(
                f"tenant {tenant!r} has exhausted its monthly budget "
                f"({limits.monthly_budget_micros} micro-USD)")

    def record(self, tenant: str, cost_micros: int) -> None:
        self._spent[tenant] = self._spent.get(tenant, 0) + cost_micros

    def spent(self, tenant: str) -> int:
        return self._spent.get(tenant, 0)

    def remaining(self, tenant: str) -> int:
        limits = self.limits[tenant]
        return max(0, limits.monthly_budget_micros - self.spent(tenant))


# ======================================================================================
# 6. Caching
# ======================================================================================


def hash_embed(text: str, dimensions: int = 64) -> List[float]:
    """A deterministic hashing bag-of-words embedder.

    Real gateways call an embedding model. What matters here is that similarity is a
    function of the text and nothing else, so the cache's behaviour is testable.
    """
    vector = [0.0] * dimensions
    for token in text.lower().split():
        digest = hashlib.blake2b(token.encode("utf-8"), digest_size=8).digest()
        index = int.from_bytes(digest[:4], "big") % dimensions
        sign = 1.0 if digest[4] % 2 == 0 else -1.0
        vector[index] += sign
    norm = math.sqrt(sum(v * v for v in vector))
    if norm == 0.0:
        return vector
    return [v / norm for v in vector]


def cosine(a: Sequence[float], b: Sequence[float]) -> float:
    return sum(x * y for x, y in zip(a, b))


def cache_key(request: NormalizedRequest, deployment_name: str) -> str:
    """Tenant FIRST. Every cache key in a multi-tenant platform starts with the tenant —
    a semantic cache that can cross a tenant boundary is a data breach with an excellent
    hit rate."""
    material = "|".join([
        request.tenant, deployment_name, request.task_class.value,
        f"{request.temperature:.4f}", str(request.max_output_tokens),
        request.prompt_text(),
    ])
    return hashlib.blake2b(material.encode("utf-8"), digest_size=16).hexdigest()


class ExactCache:
    def __init__(self, *, ttl_seconds: float, now: Callable[[], float], capacity: int = 1024) -> None:
        self.ttl = ttl_seconds
        self.now = now
        self.capacity = capacity
        self._entries: Dict[str, Tuple[float, NormalizedResponse]] = {}
        self.hits = 0
        self.misses = 0

    def get(self, key: str) -> Optional[NormalizedResponse]:
        entry = self._entries.get(key)
        if entry is None:
            self.misses += 1
            return None
        stored_at, response = entry
        if self.now() - stored_at > self.ttl:
            del self._entries[key]
            self.misses += 1
            return None
        self.hits += 1
        return response

    def put(self, key: str, response: NormalizedResponse) -> None:
        if len(self._entries) >= self.capacity:
            oldest = min(self._entries, key=lambda k: self._entries[k][0])
            del self._entries[oldest]
        self._entries[key] = (self.now(), response)


@dataclass
class SemanticEntry:
    tenant: str
    vector: Tuple[float, ...]
    response: NormalizedResponse
    stored_at: float


class SemanticCache:
    """Similarity-keyed cache. Three non-negotiables, all enforced here:

    1. **tenant-scoped** — entries are partitioned, never merely filtered;
    2. **a similarity floor** — tuned against negative examples, not guessed;
    3. **never for entitlement-dependent answers** — the caller marks a request
       ``cacheable=False`` and the gateway obeys.
    """

    def __init__(self, *, threshold: float, ttl_seconds: float, now: Callable[[], float],
                 capacity_per_tenant: int = 256) -> None:
        if not 0.0 < threshold <= 1.0:
            raise ValueError("threshold must be in (0, 1]")
        self.threshold = threshold
        self.ttl = ttl_seconds
        self.now = now
        self.capacity_per_tenant = capacity_per_tenant
        self._by_tenant: Dict[str, List[SemanticEntry]] = {}
        self.hits = 0
        self.misses = 0

    def get(self, request: NormalizedRequest) -> Optional[NormalizedResponse]:
        entries = self._by_tenant.get(request.tenant, [])
        live = [e for e in entries if self.now() - e.stored_at <= self.ttl]
        self._by_tenant[request.tenant] = live
        if not live:
            self.misses += 1
            return None
        query = hash_embed(request.prompt_text())
        best: Optional[Tuple[float, SemanticEntry]] = None
        for entry in live:
            score = cosine(query, entry.vector)
            if best is None or score > best[0]:
                best = (score, entry)
        if best is None or best[0] < self.threshold:
            self.misses += 1
            return None
        self.hits += 1
        return best[1].response

    def put(self, request: NormalizedRequest, response: NormalizedResponse) -> None:
        entries = self._by_tenant.setdefault(request.tenant, [])
        if len(entries) >= self.capacity_per_tenant:
            entries.pop(0)
        entries.append(SemanticEntry(request.tenant,
                                     tuple(hash_embed(request.prompt_text())),
                                     response, self.now()))


# ======================================================================================
# 7. Accounting
# ======================================================================================


@dataclass(frozen=True)
class AccountingRecord:
    tenant: str
    agent_id: str
    deployment: str
    provider: str
    model: str
    task_class: TaskClass
    usage: Usage
    cost_micros: int
    latency_ms: int
    cache: str
    attempts: Tuple[str, ...]
    outcome: str            # "ok" | error class name


class Accounting:
    """Token accounting and cost attribution.

    Records EVERY outcome, including failures — a cost model that only counts successes
    under-reports exactly during an incident, when the provider produced tokens before
    the timeout.
    """

    def __init__(self) -> None:
        self.records: List[AccountingRecord] = []

    def record(self, record: AccountingRecord) -> None:
        self.records.append(record)

    def cost_by(self, key: str) -> Dict[str, int]:
        if key not in ("tenant", "agent_id", "deployment", "provider", "model"):
            raise ValueError(f"cannot attribute by {key!r}")
        out: Dict[str, int] = {}
        for record in self.records:
            value = getattr(record, key)
            value = value.value if isinstance(value, Enum) else value
            out[value] = out.get(value, 0) + record.cost_micros
        return dict(sorted(out.items()))

    def tokens_by_tenant(self) -> Dict[str, int]:
        out: Dict[str, int] = {}
        for record in self.records:
            out[record.tenant] = out.get(record.tenant, 0) + record.usage.total
        return dict(sorted(out.items()))

    def cache_hit_rate(self) -> float:
        if not self.records:
            return 0.0
        hits = sum(1 for r in self.records if r.cache != "miss")
        return hits / len(self.records)

    def failover_rate(self) -> float:
        """The metric that tells you a provider is degrading before the error rate does."""
        if not self.records:
            return 0.0
        failed_over = sum(1 for r in self.records if len(r.attempts) > 1)
        return failed_over / len(self.records)


# ======================================================================================
# 8. The gateway
# ======================================================================================


def estimate_tokens(text: str) -> int:
    return (len(text) + 3) // 4


class Gateway:
    def __init__(
        self,
        *,
        router: Router,
        adapters: Mapping[str, ProviderAdapter],
        rate_limiter: RateLimiter,
        quotas: QuotaLedger,
        accounting: Accounting,
        now: Callable[[], float],
        exact_cache: Optional[ExactCache] = None,
        semantic_cache: Optional[SemanticCache] = None,
    ) -> None:
        self.router = router
        self.adapters = dict(adapters)
        self.rate_limiter = rate_limiter
        self.quotas = quotas
        self.accounting = accounting
        self.now = now
        self.exact_cache = exact_cache
        self.semantic_cache = semantic_cache

    def complete(self, request: NormalizedRequest) -> NormalizedResponse:
        """The full path, in the order that matters.

        Rate limit and quota come FIRST — they are the cheapest checks and they protect
        capacity. The cache comes before routing, because a hit needs no route. Routing,
        then budget-aware fallback. Accounting happens on every outcome.
        """
        started = self.now()
        estimated = estimate_tokens(request.prompt_text()) + request.max_output_tokens

        try:
            self.quotas.check(request.tenant)
            self.rate_limiter.admit(request.tenant, estimated)
        except GatewayError as exc:
            self._record_failure(request, exc, started, ())
            raise

        candidates = self.router.candidates(request)
        if not candidates:
            exc = NoRouteAvailable(
                f"no deployment satisfies tenant={request.tenant!r} "
                f"class={request.data_classification!r} residency={request.residency!r}")
            self._record_failure(request, exc, started, ())
            raise exc

        cached = self._cache_lookup(request, candidates[0])
        if cached is not None:
            self.accounting.record(AccountingRecord(
                tenant=request.tenant, agent_id=request.agent_id,
                deployment=cached.deployment, provider=cached.provider,
                model=cached.model, task_class=request.task_class,
                usage=Usage(), cost_micros=0,
                latency_ms=self._elapsed_ms(started), cache=cached.cache,
                attempts=(), outcome="ok"))
            return cached

        response = self._execute_with_fallback(request, candidates, started)
        self._cache_store(request, candidates[0], response)
        return response

    # -- internals ----------------------------------------------------------------
    def _elapsed_ms(self, started: float) -> int:
        return int(round((self.now() - started) * 1000))

    def _cache_lookup(self, request: NormalizedRequest, primary: Deployment) -> Optional[NormalizedResponse]:
        if not request.cacheable:
            return None
        # A hit reports cost_micros=0: `cost` means "what THIS call cost", and a served
        # cache entry cost nothing. Reporting the original cost double-counts spend.
        if self.exact_cache is not None:
            hit = self.exact_cache.get(cache_key(request, primary.name))
            if hit is not None:
                return replace(hit, cache="exact", cost_micros=0, attempts=())
        if self.semantic_cache is not None:
            hit = self.semantic_cache.get(request)
            if hit is not None:
                return replace(hit, cache="semantic", cost_micros=0, attempts=())
        return None

    def _cache_store(self, request: NormalizedRequest, primary: Deployment,
                     response: NormalizedResponse) -> None:
        if not request.cacheable:
            return
        # Never cache a truncated or filtered answer: it is not the answer.
        if response.finish_reason is not FinishReason.STOP:
            return
        if self.exact_cache is not None:
            self.exact_cache.put(cache_key(request, primary.name), response)
        if self.semantic_cache is not None:
            self.semantic_cache.put(request, response)

    def _execute_with_fallback(self, request: NormalizedRequest,
                               candidates: Sequence[Deployment],
                               started: float) -> NormalizedResponse:
        attempts: List[str] = []
        last: Optional[GatewayError] = None

        for index, deployment in enumerate(candidates):
            if index > 0:
                # Two independent reasons to refuse a fallback.
                if request.side_effecting:
                    exc = last or ProviderUnavailable("primary failed")
                    self._record_failure(request, exc, started, tuple(attempts))
                    raise exc
                remaining = request.latency_budget_ms - self._elapsed_ms(started)
                if remaining < deployment.expected_latency_ms:
                    exc = BudgetExhausted(
                        f"{remaining}ms left; {deployment.name} needs "
                        f"{deployment.expected_latency_ms}ms")
                    self._record_failure(request, exc, started, tuple(attempts))
                    raise exc

            attempts.append(deployment.name)
            adapter = self.adapters.get(deployment.provider)
            if adapter is None:
                last = InvalidRequest(f"no adapter for provider {deployment.provider!r}")
                continue
            try:
                response = adapter(request, deployment)
            except GatewayError as exc:
                last = exc
                if not exc.fall_over:
                    self._record_failure(request, exc, started, tuple(attempts))
                    raise
                continue

            cost = deployment.cost_micros(response.usage)
            final = replace(response, cost_micros=cost, attempts=tuple(attempts),
                            latency_ms=self._elapsed_ms(started))
            self.quotas.record(request.tenant, cost)
            self.accounting.record(AccountingRecord(
                tenant=request.tenant, agent_id=request.agent_id,
                deployment=deployment.name, provider=deployment.provider,
                model=deployment.model, task_class=request.task_class,
                usage=response.usage, cost_micros=cost, latency_ms=final.latency_ms,
                cache="miss", attempts=tuple(attempts), outcome="ok"))
            return final

        exc = last or NoRouteAvailable("every candidate failed")
        self._record_failure(request, exc, started, tuple(attempts))
        raise exc

    def _record_failure(self, request: NormalizedRequest, exc: GatewayError,
                        started: float, attempts: Tuple[str, ...]) -> None:
        self.accounting.record(AccountingRecord(
            tenant=request.tenant, agent_id=request.agent_id,
            deployment=attempts[-1] if attempts else "-", provider="-", model="-",
            task_class=request.task_class, usage=Usage(), cost_micros=0,
            latency_ms=self._elapsed_ms(started), cache="miss",
            attempts=attempts, outcome=type(exc).__name__))


# ======================================================================================
# 9. Provider adapters — the normalization work, made concrete
# ======================================================================================


def make_scripted_adapter(
    provider: str,
    *,
    reply: Callable[[NormalizedRequest], str],
    failures: Sequence[Optional[GatewayError]] = (),
    input_tokens: Optional[Callable[[NormalizedRequest], int]] = None,
    output_tokens: int = 64,
    cached_fraction: float = 0.0,
    finish_reason: FinishReason = FinishReason.STOP,
) -> ProviderAdapter:
    """Build a deterministic provider adapter.

    ``failures`` is consumed one entry per call: a GatewayError is raised, None succeeds.
    That is how a test scripts "the primary 429s twice, then works".
    """
    pending = list(failures)

    def adapter(request: NormalizedRequest, deployment: Deployment) -> NormalizedResponse:
        if pending:
            failure = pending.pop(0)
            if failure is not None:
                raise failure
        raw_input = (input_tokens or (lambda r: estimate_tokens(r.prompt_text())))(request)
        cached = int(raw_input * cached_fraction)
        return NormalizedResponse(
            text=reply(request),
            finish_reason=finish_reason,
            usage=Usage(input_tokens=raw_input, cached_input_tokens=cached,
                        output_tokens=output_tokens),
            deployment=deployment.name, provider=provider, model=deployment.model,
            latency_ms=deployment.expected_latency_ms,
        )

    return adapter


# ======================================================================================
# Worked example
# ======================================================================================


def _clock(step: float = 0.05) -> Callable[[], float]:
    state = {"t": -step}

    def now() -> float:
        state["t"] += step
        return round(state["t"], 6)

    return now


def _build(now):
    deployments = {
        "azure-gpt-uae-ptu": Deployment(
            "azure-gpt-uae-ptu", "azure", "gpt-frontier", "uae-north", Capacity.PROVISIONED,
            input_micros_per_1k=2500, cached_input_micros_per_1k=250,
            output_micros_per_1k=10000, expected_latency_ms=700),
        "azure-gpt-uae-payg": Deployment(
            "azure-gpt-uae-payg", "azure", "gpt-frontier", "uae-north", Capacity.PAYG,
            input_micros_per_1k=3000, cached_input_micros_per_1k=300,
            output_micros_per_1k=12000, expected_latency_ms=900),
        "anthropic-eu": Deployment(
            "anthropic-eu", "anthropic", "claude-frontier", "eu-west", Capacity.PAYG,
            input_micros_per_1k=3000, cached_input_micros_per_1k=300,
            output_micros_per_1k=15000, expected_latency_ms=800,
            max_classification="confidential"),
        "self-hosted-uae": Deployment(
            "self-hosted-uae", "vllm", "llama-open", "uae-north", Capacity.SELF_HOSTED,
            input_micros_per_1k=400, cached_input_micros_per_1k=400,
            output_micros_per_1k=800, expected_latency_ms=1400),
    }
    rules = [
        RoutingRule("restricted-must-stay-onshore",
                    deployments=("azure-gpt-uae-ptu", "azure-gpt-uae-payg", "self-hosted-uae"),
                    classifications=("restricted",), priority=10),
        RoutingRule("cheap-classification",
                    deployments=("self-hosted-uae", "azure-gpt-uae-payg"),
                    task_classes=(TaskClass.CLASSIFICATION,), priority=20),
        RoutingRule("default",
                    deployments=("azure-gpt-uae-ptu", "anthropic-eu", "azure-gpt-uae-payg"),
                    priority=100),
    ]
    limits = {
        "wholesale": TenantLimits(requests_per_minute=60, tokens_per_minute=120_000,
                                  monthly_budget_micros=50_000_000),
        "retail": TenantLimits(requests_per_minute=6, tokens_per_minute=6_000,
                               monthly_budget_micros=1_000_000),
    }
    accounting = Accounting()
    gateway = Gateway(
        router=Router(deployments, rules),
        adapters={
            "azure": make_scripted_adapter("azure", reply=lambda r: "azure says: held pending review",
                                           cached_fraction=0.4),
            "anthropic": make_scripted_adapter("anthropic", reply=lambda r: "anthropic says: held"),
            "vllm": make_scripted_adapter("vllm", reply=lambda r: "llama says: held"),
        },
        rate_limiter=RateLimiter(limits, now=now),
        quotas=QuotaLedger(limits),
        accounting=accounting,
        now=now,
        exact_cache=ExactCache(ttl_seconds=300, now=now),
        semantic_cache=SemanticCache(threshold=0.92, ttl_seconds=300, now=now),
    )
    return gateway, deployments, accounting


def _request(**kwargs) -> NormalizedRequest:
    kwargs.setdefault("messages", (Message("system", "You are a payments investigator."),
                                   Message("user", "Why is payment PMT-771 held?")))
    kwargs.setdefault("task_class", TaskClass.REASONING)
    kwargs.setdefault("tenant", "wholesale")
    kwargs.setdefault("agent_id", "payments-investigator")
    return NormalizedRequest(**kwargs)


def main() -> None:  # pragma: no cover - narrative output
    now = _clock()
    gateway, deployments, accounting = _build(now)

    print("=" * 78)
    print("1. ONE INTERFACE, MANY PROVIDERS")
    print("=" * 78)
    response = gateway.complete(_request())
    print(f"  routed to   : {response.deployment} ({response.provider}/{response.model})")
    print(f"  finish      : {response.finish_reason.value}")
    print(f"  usage       : in={response.usage.input_tokens} "
          f"cached={response.usage.cached_input_tokens} out={response.usage.output_tokens}")
    print(f"  cost        : {response.cost_micros} micro-USD")
    print(f"  attempts    : {list(response.attempts)}")

    print()
    print("=" * 78)
    print("2. ROUTING IS A POLICY, NOT A MODEL NAME")
    print("=" * 78)
    for label, req in [
        ("default reasoning", _request()),
        ("classification (cheap)", _request(task_class=TaskClass.CLASSIFICATION)),
        ("restricted data", _request(data_classification="restricted")),
        ("residency: uae-north", _request(residency="uae-north")),
    ]:
        chain = gateway.router.candidates(req)
        print(f"  {label:<24} -> {[d.name for d in chain]}")
    blocked = _request(data_classification="restricted", residency="eu-west")
    print(f"  {'restricted + eu-west':<24} -> {[d.name for d in gateway.router.candidates(blocked)]}"
          f"  (nothing satisfies both)")

    print()
    print("=" * 78)
    print("3. BUDGET-AWARE FALLBACK")
    print("=" * 78)
    now2 = _clock()
    gw2, _, acc2 = _build(now2)
    gw2.adapters["azure"] = make_scripted_adapter(
        "azure", reply=lambda r: "recovered",
        failures=[RateLimited("429 from azure", provider="azure")])
    ok = gw2.complete(_request())
    print(f"  primary 429 -> fell over to {ok.deployment}, attempts={list(ok.attempts)}")

    now3 = _clock(step=0.6)      # 600 ms per clock read: the budget burns fast
    gw3, _, _ = _build(now3)
    gw3.adapters["azure"] = make_scripted_adapter(
        "azure", reply=lambda r: "recovered",
        failures=[ProviderTimeout("timeout", provider="azure")])
    try:
        gw3.complete(_request(latency_budget_ms=1000))
    except BudgetExhausted as exc:
        print(f"  no headroom -> {type(exc).__name__}: {exc.message}")

    now4 = _clock()
    gw4, _, _ = _build(now4)
    gw4.adapters["azure"] = make_scripted_adapter(
        "azure", reply=lambda r: "recovered",
        failures=[ProviderTimeout("timeout", provider="azure")])
    try:
        gw4.complete(_request(side_effecting=True))
    except ProviderTimeout as exc:
        print(f"  side-effecting -> refused to fall over: {exc.message}")

    now5 = _clock()
    gw5, _, _ = _build(now5)
    gw5.adapters["azure"] = make_scripted_adapter(
        "azure", reply=lambda r: "x",
        failures=[ContentFiltered("blocked by provider safety", provider="azure")])
    try:
        gw5.complete(_request())
    except ContentFiltered as exc:
        print(f"  content filter -> no failover (never shop for a compliant model)")

    print()
    print("=" * 78)
    print("4. CACHING")
    print("=" * 78)
    now6 = _clock()
    gw6, _, acc6 = _build(now6)
    first = gw6.complete(_request())
    second = gw6.complete(_request())
    print(f"  identical request  -> cache={second.cache}, cost={second.cost_micros}")
    near = _request(messages=(Message("system", "You are a payments investigator."),
                              Message("user", "Why is payment PMT-771 held?  ")))
    third = gw6.complete(near)
    print(f"  near-duplicate     -> cache={third.cache}")
    other = _request(tenant="retail")
    fourth = gw6.complete(other)
    print(f"  same text, tenant 'retail' -> cache={fourth.cache}  "
          f"(tenant is the first component of every key)")
    print(f"  exact hits/misses  : {gw6.exact_cache.hits}/{gw6.exact_cache.misses}")
    print(f"  semantic hits/miss : {gw6.semantic_cache.hits}/{gw6.semantic_cache.misses}")
    uncacheable = gw6.complete(_request(cacheable=False))
    print(f"  cacheable=False    -> cache={uncacheable.cache} (entitlement-dependent answers)")

    print()
    print("=" * 78)
    print("5. RATE LIMITS AND QUOTAS")
    print("=" * 78)
    now7 = _clock(step=0.0)      # frozen clock: no refill
    gw7, _, _ = _build(now7)
    admitted = 0
    try:
        for _ in range(20):
            gw7.complete(_request(tenant="retail", cacheable=False,
                                  messages=(Message("user", f"q{admitted}"),)))
            admitted += 1
    except RateLimited as exc:
        print(f"  retail admitted {admitted} requests, then: {exc.message}")

    now8 = _clock()
    gw8, _, _ = _build(now8)
    gw8.quotas.record("retail", 1_000_000)
    try:
        gw8.complete(_request(tenant="retail"))
    except QuotaExceeded as exc:
        print(f"  budget exhausted -> {exc.message}")

    print()
    print("=" * 78)
    print("6. ACCOUNTING AND ATTRIBUTION")
    print("=" * 78)
    now9 = _clock()
    gw9, _, acc9 = _build(now9)
    for tenant, agent in [("wholesale", "payments-investigator"),
                          ("wholesale", "kyc-refresh"),
                          ("retail", "collections")]:
        for i in range(3):
            gw9.complete(_request(tenant=tenant, agent_id=agent, cacheable=False,
                                  messages=(Message("user", f"{agent} question {i}"),)))
    print(f"  cost by tenant     : {acc9.cost_by('tenant')}")
    print(f"  cost by agent      : {acc9.cost_by('agent_id')}")
    print(f"  cost by deployment : {acc9.cost_by('deployment')}")
    print(f"  tokens by tenant   : {acc9.tokens_by_tenant()}")
    print(f"  cache hit rate     : {acc9.cache_hit_rate():.0%}")
    print(f"  failover rate      : {acc9.failover_rate():.0%}")

    print()
    print("=" * 78)
    print("7. FAILURES ARE ACCOUNTED TOO")
    print("=" * 78)
    now10 = _clock()
    gw10, _, acc10 = _build(now10)
    gw10.adapters["azure"] = make_scripted_adapter(
        "azure", reply=lambda r: "x",
        failures=[ContentFiltered("blocked", provider="azure")])
    try:
        gw10.complete(_request())
    except ContentFiltered:
        pass
    for record in acc10.records:
        print(f"  outcome={record.outcome:<16} attempts={list(record.attempts)} "
              f"cost={record.cost_micros} latency={record.latency_ms}ms")
    print("  -> a cost model that counts only successes under-reports during incidents.")


if __name__ == "__main__":  # pragma: no cover
    main()
