# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/why-does-an-instance-replay-diverge-from-its-otel-trace-when-the-agent-s-tool-call-ordering-is-only-partially-ordered.md
# Remnant Warrant:    https://corpusfetch.com/c/why-does-an-instance-replay-diverge-from-its-otel-trace-when-the-agent-s-tool-call-ordering-is-only-partially-ordered.warrant.json
# Markdown SHA-256:   b1723ad70e4e350570cef489453fce5ae62c4a0586e57ea6058a1082c5ed84fe
# Code AST SHA-256:   990209ab9aefa617e7627e25847d75682bca1ecb69481c7e815652e89290a229
# Verified Classes:   ReplayLinearizationError
# Defensive Guards:   3 fail-closed invariants (zero external deps)

class ReplayLinearizationError(RuntimeError):
    """Raised when a trace cannot be deterministically linearized for replay."""


def linearize_turn_spans(spans: list[dict], turn_index: int) -> list[dict]:
    """Order sibling tool spans for a turn using explicit sequencing witnesses only.

    Timestamps are deliberately NOT used as an ordering key: they are subject to
    cross-host clock skew and do not encode happens-before for concurrent tool calls.
    """
    turn_spans = [s for s in spans if s.get("attributes", {}).get("agent.turn.index") == turn_index]
    if not turn_spans:
        raise ReplayLinearizationError(
            f"no spans found for turn {turn_index}; cannot reconstruct execution"
        )

    # Detect overlap among siblings: overlapping intervals mean the trace is a
    # partial order and requires an explicit witness to be replayable.
    ordered = sorted(turn_spans, key=lambda s: s["start_ns"])
    for prev, nxt in zip(ordered, ordered[1:]):
        if nxt["start_ns"] < prev["end_ns"]:
            # Overlap detected. Demand an explicit call index on both spans.
            for s in (prev, nxt):
                if "agent.tool.call_index" not in s.get("attributes", {}):
                    raise ReplayLinearizationError(
                        f"overlapping sibling spans {prev['span_id']} and {nxt['span_id']} "
                        f"in turn {turn_index} lack agent.tool.call_index; "
                        f"trace is a partial order and cannot be replayed deterministically"
                    )

    # If we got here, either no overlaps or every overlapping span carries a witness.
    return sorted(
        turn_spans,
        key=lambda s: s["attributes"].get("agent.tool.call_index", 0),
    )


def replay_trajectory(trace: dict) -> list[dict]:
    """Build the replay input as a total order of events, or refuse."""
    events: list[dict] = []
    turn_indices = sorted({
        s["attributes"]["agent.turn.index"]
        for s in trace["spans"]
        if "agent.turn.index" in s.get("attributes", {})
    })
    if not turn_indices:
        raise ReplayLinearizationError(
            "trace carries no agent.turn.index attributes; not a replayable agent trajectory"
        )
    for t in turn_indices:
        for span in linearize_turn_spans(trace["spans"], t):
            events.append({"turn": t, "span_id": span["span_id"], "name": span["name"]})
    return events