Skip to main content

switchyard_libsy/core/
algorithm.rs

1// SPDX-FileCopyrightText: Copyright (c) 2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
2// SPDX-License-Identifier: Apache-2.0
3
4//! Routing algorithms request external work through [`Driver`] and receive typed replies.
5//! Hosts execute that work, keeping routing policy independent of transport.
6
7use std::{
8    collections::HashMap, future::Future, panic::AssertUnwindSafe, pin::Pin, sync::Arc,
9    time::Instant,
10};
11
12use async_trait::async_trait;
13use futures::{FutureExt, Stream, StreamExt};
14use parking_lot::Mutex;
15use serde_json::Value;
16use tokio::sync::{mpsc, oneshot};
17use tokio_stream::wrappers::ReceiverStream;
18use tracing::Instrument;
19
20/// The request/response protocol types come from [`switchyard_protocol`].
21/// [`switchyard_protocol::LlmRequest`] is the normalized request;
22/// [`switchyard_protocol::AggLlmResponse`] is the buffered response;
23/// [`switchyard_protocol::LlmResponseChunk`] is normalized streaming content;
24/// [`switchyard_protocol::LlmResponseStreamEvent`] is its host/algorithm envelope; and
25/// [`switchyard_protocol::LlmResponse`] carries either a live
26/// [`switchyard_protocol::LlmResponseStream`] or the terminal aggregate.
27use switchyard_protocol::{
28    AggLlmResponse, Category, ContentBlock, DecisionRequest, DecisionResponse, ModelId, Request,
29    Response, StopReason,
30};
31
32use crate::{DriverError, LibsyError, Result, State, observability};
33
34/// A boxed, `Send` stream of [`Step`]s — the output of
35/// [`Algorithm::run_stream`]. Boxed so the trait method that produces it keeps
36/// `Arc<dyn Algorithm>` object-safe.
37pub type StepStream = Pin<Box<dyn Stream<Item = Result<Step>> + Send>>;
38
39/// The models one algorithm run may use, grouped by [`Category`]. Within a
40/// category they are ordered best-first.
41///
42/// Delegated sub-agent work gets its own groups, reachable only through
43/// [`Driver::for_subagent`]. Keeping them separate is what stops a sub-agent's
44/// `capable` from resolving to the parent's, and stops the parent falling back
45/// onto a model only its sub-agents were given.
46///
47/// One run's driver clones all read the same value, so it is passed as
48/// `Arc<RuntimeModels>` rather than cloned per driver.
49#[derive(Clone, Debug, Default)]
50pub struct RuntimeModels {
51    /// When using subagents this is the parent agent category.
52    by_category: HashMap<Category, Vec<ModelId>>,
53    subagent: Option<HashMap<Category, Vec<ModelId>>>,
54    has_target_restriction: bool,
55    provider_models: HashMap<ModelId, ModelId>,
56}
57
58impl RuntimeModels {
59    /// The models available to the algorithm itself.
60    pub fn new(by_category: HashMap<Category, Vec<ModelId>>) -> Self {
61        Self {
62            by_category,
63            subagent: None,
64            has_target_restriction: false,
65            provider_models: HashMap::new(),
66        }
67    }
68
69    /// Supplies provider identities for telemetry while routing keeps using target keys.
70    pub fn with_provider_models(mut self, models: HashMap<ModelId, ModelId>) -> Self {
71        self.provider_models = models;
72        self
73    }
74
75    /// Returns the provider model for a routing key, or the key for direct library callers.
76    pub fn provider_model<'a>(&'a self, target: &'a ModelId) -> &'a ModelId {
77        self.provider_models.get(target).unwrap_or(target)
78    }
79
80    /// Adds the groups used for delegated sub-agent work.
81    pub fn with_subagent(mut self, models: HashMap<Category, Vec<ModelId>>) -> Self {
82        self.subagent = Some(models);
83        self
84    }
85
86    /// Rejects routing calls and completion candidates outside the configured model groups.
87    /// Enforced by the driver and [`drive`]; hosts bind IDs to permitted deployments.
88    pub fn with_target_restriction(mut self) -> Self {
89        self.has_target_restriction = true;
90        self
91    }
92
93    fn check_targets(&self, targets: &[ModelId]) -> Result<()> {
94        if !self.has_target_restriction {
95            return Ok(());
96        }
97        // Include delegated groups: the parent driver publishes subagent outcomes too.
98        for target in targets {
99            if !self
100                .by_category
101                .values()
102                .chain(self.subagent.iter().flat_map(HashMap::values))
103                .any(|models| models.contains(target))
104            {
105                return Err(LibsyError::TargetNotFound {
106                    target: target.clone(),
107                });
108            }
109        }
110        Ok(())
111    }
112
113    fn check_request_targets(&self, request: &Request, targets: &[ModelId]) -> Result<()> {
114        self.check_targets(targets)?;
115        if self.has_target_restriction {
116            let selected = targets.first().ok_or(LibsyError::NoTargets)?;
117            if request.llm_request.model.as_deref() != Some(selected.as_str()) {
118                return Err(LibsyError::AlgorithmError {
119                    message: "request model does not match selected target".into(),
120                });
121            }
122        }
123        Ok(())
124    }
125
126    /// The models in `category`, ordered best-first.
127    pub fn models_for(&self, category: &Category) -> &[ModelId] {
128        self.by_category.get(category).map_or(&[], Vec::as_slice)
129    }
130
131    /// The models delegated sub-agent work uses for `category`, ordered best-first.
132    pub fn subagent_models_for(&self, category: &Category) -> &[ModelId] {
133        self.subagent
134            .as_ref()
135            .and_then(|models| models.get(category))
136            .map_or(&[], Vec::as_slice)
137    }
138}
139
140impl From<HashMap<Category, Vec<ModelId>>> for RuntimeModels {
141    fn from(by_category: HashMap<Category, Vec<ModelId>>) -> Self {
142        Self::new(by_category)
143    }
144}
145
146/// Which of a [`RuntimeModels`]' groups a driver reads.
147#[derive(Clone, Copy)]
148enum Scope {
149    Parent,
150    Subagent,
151}
152
153/// An offloaded model call, surfaced inside [`Step::CallModel`].
154///
155/// The host reads the public fields and passes its model-call future to
156/// [`respond`](Self::respond), unblocking the algorithm's [`Driver::call_model`] on the
157/// other side. `switchyard-llm-client`'s `run` is the ready-made consumer that does this for
158/// you.
159///
160/// [`Driver::call_model`] stamps the first candidate model onto the request before publishing
161/// the call. A consumer that falls through to a later candidate must re-stamp it.
162pub struct CallModel {
163    /// The name of the algorithm that produced this call, so a host instrumenting the
164    /// calls it serves can attribute its own spans to the algorithm behind them.
165    pub algorithm: String,
166    /// The request to serve; its `model` is stamped with the first candidate.
167    pub request: Request,
168    /// Candidate models in fallback order. Never empty.
169    ///
170    /// The host owns candidate execution and fallback. The native
171    /// `switchyard-llm-client` consumer calls only the first candidate during routing.
172    /// A failure stops its run unless [`Self::recover_errors`] is enabled, which
173    /// returns the error to the algorithm without trying later candidates.
174    /// Terminal completion fallback is handled separately.
175    pub models: Vec<ModelId>,
176    /// Return client errors to the algorithm so it can apply its fallback policy.
177    pub recover_errors: bool,
178    telemetry_model: ModelId,
179    /// How to send the response back to the algorithm. `None` once the call is recorded.
180    reply: Option<oneshot::Sender<Result<Response>>>,
181    started: Instant,
182    // Retain the originating span even if the waiting algorithm is cancelled first.
183    span: tracing::Span,
184}
185
186impl CallModel {
187    /// Run host work until it completes or the algorithm stops waiting for this call.
188    /// Dropping the waiting [`Driver::call_model`] future drops `work` and returns `Ok(())`.
189    /// Errors stop the host's run unless [`Self::recover_errors`] is enabled.
190    /// Use `std::future::ready(result)` for an already available response.
191    /// A delivered response stream owns its subsequent lifetime.
192    pub async fn respond(mut self, work: impl Future<Output = Result<Response>>) -> Result<()> {
193        let reply = self.reply.as_mut().ok_or(DriverError::ResponseDropped)?;
194        let result = tokio::select! {
195            biased;
196            _ = reply.closed() => return Ok(()),
197            result = work => result,
198        };
199        if self.reply.as_ref().is_some_and(oneshot::Sender::is_closed) {
200            return Ok(());
201        }
202        if !self.recover_errors
203            && let Err(error) = result
204        {
205            return self.fail(error);
206        }
207        self.record(result.is_ok());
208        if let Ok(response) = &result {
209            observability::record_llm_response(response, &self.span);
210        }
211        self.reply
212            .take()
213            .ok_or(DriverError::ResponseDropped)?
214            .send(result)
215            .ok();
216        Ok(())
217    }
218
219    /// Record a failed call and return its error to stop [`drive`].
220    /// Leaves the promise unfulfilled so the driver can cancel the algorithm.
221    pub fn fail(mut self, error: LibsyError) -> Result<()> {
222        self.reply = None;
223        self.record(false);
224        Err(error)
225    }
226
227    fn record(&self, is_ok: bool) {
228        observability::record_llm_call(
229            &self.algorithm,
230            self.telemetry_model.as_str(),
231            self.started.elapsed(),
232            is_ok,
233        );
234        self.span
235            .record("outcome", if is_ok { "ok" } else { "error" });
236    }
237}
238
239impl Drop for CallModel {
240    fn drop(&mut self) {
241        if self.reply.is_some() {
242            self.record(false);
243        }
244    }
245}
246
247/// A host-owned decision call. Dropping it without replying yields [`DriverError::ResponseDropped`].
248/// Completion or drop records one call and its duration, including time waiting for the host.
249pub struct CallDecision {
250    /// Algorithm name for attributing host telemetry.
251    pub algorithm: String,
252    /// Its model is set to [`Self::model`] before dispatch.
253    pub request: DecisionRequest,
254    /// Target ID for client lookup.
255    pub model: ModelId,
256    reply: Option<oneshot::Sender<Result<DecisionResponse>>>,
257    started: Instant,
258    // Retain the originating span even if the waiting algorithm is cancelled first.
259    span: tracing::Span,
260}
261
262impl CallDecision {
263    /// Run host work and return its response or error to the algorithm.
264    /// Dropping the waiting [`Driver::call_decision`] future drops `work` and returns `Ok(())`.
265    /// Use `std::future::ready(result)` for an already available response.
266    pub async fn respond(
267        mut self,
268        work: impl Future<Output = Result<DecisionResponse>>,
269    ) -> Result<()> {
270        let reply = self.reply.as_mut().ok_or(DriverError::ResponseDropped)?;
271        let result = tokio::select! {
272            biased;
273            _ = reply.closed() => return Ok(()),
274            result = work => result,
275        };
276        self.record(result.is_ok());
277        if let Ok(response) = &result {
278            observability::record_decision_response(response, &self.span);
279        }
280        self.reply
281            .take()
282            .ok_or(DriverError::ResponseDropped)?
283            .send(result)
284            .ok();
285        Ok(())
286    }
287
288    /// Returning this error from the host handler aborts [`drive`].
289    pub fn fail(mut self, error: LibsyError) -> Result<()> {
290        self.reply = None;
291        self.record(false);
292        Err(error)
293    }
294
295    fn record(&self, is_ok: bool) {
296        observability::record_decision_call(
297            &self.algorithm,
298            &self.model,
299            self.started.elapsed(),
300            is_ok,
301        );
302        self.span
303            .record("outcome", if is_ok { "ok" } else { "error" });
304    }
305}
306
307impl Drop for CallDecision {
308    fn drop(&mut self) {
309        if self.reply.is_some() {
310            self.record(false);
311        }
312    }
313}
314
315/// The terminal result of routing.
316pub struct RoutingOutcome {
317    /// Models selected by the algorithm, ordered best model first.
318    pub selected_model_ids: Vec<ModelId>,
319    /// The request after all routing-time rewrites, stamped with the selected model.
320    pub request: Request,
321    /// The request the fallback candidates receive instead of `request`, when routing
322    /// rewrote `request` for the selected model only.
323    /// Content-policy denials do not advance to these fallback candidates.
324    pub fallback_request: Option<Request>,
325    /// Candidate-specific requests, including model-specific instructions.
326    pub candidate_requests: HashMap<ModelId, Request>,
327    /// A response produced while routing, or `None` when the client must make the answer call.
328    pub response: Option<Response>,
329    /// Outcome identity and optional algorithm evidence.
330    ///
331    /// Constructors leave this empty; [`Algorithm::run_stream`] fills it before publishing a
332    /// successful outcome.
333    pub metadata: Option<crate::OutcomeMetadata>,
334    /// Routing state after the run, for hosts that store state outside the algorithm.
335    pub state: State,
336}
337
338impl RoutingOutcome {
339    /// The model the algorithm recommends, the best model for this request.
340    /// `LibsyError::NoTargets` if the algorithm selected no models, which should be impossible.
341    pub fn selected_model_id(&self) -> Result<&ModelId> {
342        self.selected_model_ids.first().ok_or(LibsyError::NoTargets)
343    }
344
345    /// The decision is that client should send this `request`. The `selected_model_id`
346    /// will be written into it by this function.
347    /// If that fails client should try the `fallback_models` in order.
348    pub fn route_to(
349        selected_model_id: ModelId,
350        fallback_models: Vec<ModelId>,
351        mut request: Request,
352    ) -> Self {
353        request.llm_request.model = Some(selected_model_id.to_string());
354        let mut selected_model_ids = Vec::with_capacity(1 + fallback_models.len());
355        selected_model_ids.push(selected_model_id);
356        selected_model_ids.extend(fallback_models);
357        Self {
358            selected_model_ids,
359            request,
360            fallback_request: None,
361            candidate_requests: HashMap::new(),
362            response: None,
363            metadata: None,
364            state: State::default(),
365        }
366    }
367
368    /// Algorithm generated the response as part of the routing decision. Here it is.
369    /// The `request` will have the `selected_model_id` written into it by this function.
370    pub fn answered(selected_model_id: ModelId, mut request: Request, response: Response) -> Self {
371        request.llm_request.model = Some(selected_model_id.to_string());
372        Self {
373            selected_model_ids: vec![selected_model_id],
374            request,
375            fallback_request: None,
376            candidate_requests: HashMap::new(),
377            response: Some(response),
378            metadata: None,
379            state: State::default(),
380        }
381    }
382}
383
384/// What the host saw of the answer it served for a routed request.
385#[derive(Clone, Copy, Debug, Eq, PartialEq)]
386pub struct AnswerSummary {
387    /// The answer ended its turn with visible text and requested no tool call.
388    pub final_reply: bool,
389}
390
391impl AnswerSummary {
392    /// Summarizes a completed answer.
393    pub fn of(response: &AggLlmResponse) -> Self {
394        let final_reply = response.outputs.iter().all(|output| {
395            matches!(output.stop_reason, None | Some(StopReason::EndTurn))
396                && !output
397                    .content
398                    .iter()
399                    .any(|block| matches!(block, ContentBlock::ToolCall(_)))
400        }) && response.outputs.iter().any(|output| {
401            output.role == switchyard_protocol::Role::Assistant
402                && output.content.iter().any(
403                    |block| matches!(block, ContentBlock::Text { text } if !text.trim().is_empty()),
404                )
405        });
406        Self { final_reply }
407    }
408}
409
410#[derive(Default)]
411struct RunEvidence {
412    outcome: Option<Value>,
413    judgments: Vec<crate::JudgeDecision>,
414}
415
416/// An algorithm's handle for requesting external work and awaiting the host's typed replies.
417#[derive(Clone)]
418pub struct Driver {
419    step_tx: mpsc::Sender<Result<Step>>,
420
421    /// The owning algorithm's telemetry label, stamped onto every call this driver publishes.
422    algorithm: String,
423
424    /// Run-scoped evidence shared by driver clones and attached only to a successful outcome.
425    evidence: Arc<Mutex<RunEvidence>>,
426
427    /// Caller-supplied routing state, read and updated when a request carries no session ID.
428    state: Arc<Mutex<State>>,
429
430    /// Every group this run may route over, shared by all driver clones.
431    models: Arc<RuntimeModels>,
432
433    /// Which of those groups this driver reads.
434    scope: Scope,
435    judge: Option<ModelId>,
436}
437
438impl Driver {
439    /// Build an empty driver with its step channel ready. Created per call by
440    /// [`run_stream`](Algorithm::run_stream). Also returns the Step receiver.
441    pub(crate) fn new(
442        algorithm: &str,
443        models: Arc<RuntimeModels>,
444    ) -> (Self, mpsc::Receiver<Result<Step>>) {
445        // Capacity one keeps the algorithm paced by the stream consumer. It limits queued steps,
446        // not model calls already pulled from the stream, which can still run at the same time.
447        // A larger buffer would use more memory and let the algorithm run farther ahead with
448        // little benefit because reading a step is cheap compared with serving a model call.
449        let (step_tx, step_rx) = mpsc::channel(1);
450        (
451            Self {
452                step_tx,
453                algorithm: algorithm.to_string(),
454                evidence: Arc::new(Mutex::new(RunEvidence::default())),
455                state: Arc::new(Mutex::new(State::default())),
456                models,
457                scope: Scope::Parent,
458                judge: None,
459            },
460            step_rx,
461        )
462    }
463
464    pub(crate) fn take_state(&self) -> State {
465        std::mem::take(&mut *self.state.lock())
466    }
467
468    pub(crate) fn set_state(&self, state: State) {
469        *self.state.lock() = state;
470    }
471
472    /// Replace the current run's evidence when a component makes the final decision.
473    pub(crate) fn set_evidence(&self, evidence: Value) {
474        self.evidence.lock().outcome = Some(evidence);
475    }
476
477    /// Supply fallback evidence without replacing a decision made earlier in the cascade.
478    pub(crate) fn set_evidence_if_empty(&self, evidence: Value) {
479        let mut current = self.evidence.lock();
480        if current.outcome.is_none() {
481            current.outcome = Some(evidence);
482        }
483    }
484
485    pub(crate) fn record_judgment(&self, selected: Option<crate::Score>, evidence: Option<Value>) {
486        let (target, category) = selected
487            .map(|score| (Some(score.target), score.category))
488            .unwrap_or_default();
489        self.evidence.lock().judgments.push(crate::JudgeDecision {
490            target,
491            category: category.map(|category| category.as_str().to_string()),
492            evidence,
493        });
494    }
495
496    /// Publish a model call and await the consumer's response.
497    ///
498    /// Errors if the stream is closed or the call failed.
499    /// The await is wrapped in a `libsy.llm_call` span measuring *fulfillment* as
500    /// the algorithm observes it (host queueing/serving included; a streamed
501    /// response resolves when its stream handle arrives). The host records call metrics,
502    /// outcome, and buffered token usage when it completes or drops the call, even if the
503    /// waiting algorithm has been cancelled. The provider call itself is the
504    /// host's, and is instrumented by whoever makes it.
505    pub async fn call_model(&self, request: Request, models: Vec<ModelId>) -> Result<Response> {
506        self.call_model_with_error_recovery(request, models, false)
507            .await
508    }
509
510    /// Allows a routing policy to handle a failed call when recovery is enabled.
511    #[tracing::instrument(
512        target = "libsy",
513        name = "libsy.llm_call",
514        skip_all,
515        fields(
516            algorithm = self.algorithm,
517            selected_model = %models.first().map(|model| self.provider_model(model).as_str()).unwrap_or("NoTargets"),
518            openinference.span.kind = "CHAIN",
519            outcome = tracing::field::Empty,
520            input_tokens = tracing::field::Empty,
521            output_tokens = tracing::field::Empty,
522            total_tokens = tracing::field::Empty,
523            reasoning_tokens = tracing::field::Empty,
524        )
525    )]
526    pub(crate) async fn call_model_with_error_recovery(
527        &self,
528        mut request: Request,
529        models: Vec<ModelId>,
530        recover_errors: bool,
531    ) -> Result<Response> {
532        let Some(selected_model_id) = models.first() else {
533            return Err(LibsyError::NoTargets);
534        };
535        self.models.check_targets(&models)?;
536        request.llm_request.model = Some(selected_model_id.to_string());
537        let started = Instant::now();
538        let (reply, response) = oneshot::channel::<Result<Response>>();
539        let call = CallModel {
540            algorithm: self.algorithm.clone(),
541            request,
542            telemetry_model: self.provider_model(selected_model_id).clone(),
543            models,
544            recover_errors,
545            reply: Some(reply),
546            started,
547            span: tracing::Span::current(),
548        };
549        self.step_tx
550            .send(Ok(Step::CallModel(Box::new(call))))
551            .await
552            .map_err(|_| DriverError::StreamClosed)?;
553        response
554            .await
555            .map_err(|_| LibsyError::from(DriverError::ResponseDropped))?
556    }
557
558    /// Override the request's model with `model` and wait for the host to reply.
559    #[tracing::instrument(
560        target = "libsy",
561        name = "libsy.decision_call",
562        skip_all,
563        fields(
564            algorithm = self.algorithm,
565            selected_model = %model,
566            openinference.span.kind = "CHAIN",
567            outcome = tracing::field::Empty,
568            input_tokens = tracing::field::Empty,
569            output_tokens = tracing::field::Empty,
570            total_tokens = tracing::field::Empty,
571            reasoning_tokens = tracing::field::Empty,
572            gen_ai.response.id = tracing::field::Empty,
573            gen_ai.response.model = tracing::field::Empty,
574        ),
575    )]
576    pub async fn call_decision(
577        &self,
578        mut request: DecisionRequest,
579        model: ModelId,
580    ) -> Result<DecisionResponse> {
581        self.models.check_targets(std::slice::from_ref(&model))?;
582        request.model = Some(model.clone());
583        let started = Instant::now();
584        let (reply, response) = oneshot::channel();
585        let call = CallDecision {
586            algorithm: self.algorithm.clone(),
587            request,
588            model,
589            reply: Some(reply),
590            started,
591            span: tracing::Span::current(),
592        };
593        self.step_tx
594            .send(Ok(Step::CallDecision(Box::new(call))))
595            .await
596            .map_err(|_| DriverError::StreamClosed)?;
597        response
598            .await
599            .map_err(|_| LibsyError::from(DriverError::ResponseDropped))?
600    }
601
602    /// Provider identity for telemetry; algorithms still route on the original target key.
603    pub fn provider_model<'a>(&'a self, target: &'a ModelId) -> &'a ModelId {
604        self.models.provider_model(target)
605    }
606
607    /// The available models for this category, typically ordered best-first.
608    pub fn models_for(&self, category: &Category) -> &[ModelId] {
609        if *category == Category::Judge
610            && let Some(judge) = &self.judge
611        {
612            return std::slice::from_ref(judge);
613        }
614        match self.scope {
615            Scope::Parent => self.models.models_for(category),
616            Scope::Subagent => self.models.subagent_models_for(category),
617        }
618    }
619
620    pub(crate) fn for_judge(&self, judge: ModelId) -> Self {
621        Self {
622            judge: Some(judge),
623            ..self.clone()
624        }
625    }
626
627    /// The first available model for `category`.
628    pub fn first_model_for(&self, category: &Category) -> Result<&ModelId> {
629        self.models_for(category)
630            .first()
631            .ok_or_else(|| LibsyError::AlgorithmError {
632                message: format!("no models available for category {}", category.as_str()),
633            })
634    }
635
636    /// A driver scoped to delegated sub-agent work: its categories are the
637    /// sub-agent's own, and the parent's are no longer reachable through it.
638    pub fn for_subagent(&self) -> Result<Self> {
639        if self.models.subagent.is_none() {
640            return Err(LibsyError::AlgorithmError {
641                message: "delegated work has no sub-agent models".to_string(),
642            });
643        }
644        Ok(Self {
645            scope: Scope::Subagent,
646            ..self.clone()
647        })
648    }
649
650    /// Emit the terminal step: [`Step::Done`] on `Ok`, or an `Err` stream
651    /// item on failure. Internal: called once by [`run_stream`](Algorithm::run_stream)
652    /// when the algorithm finishes.
653    pub(crate) async fn finish(&self, result: Result<RoutingOutcome>) -> Result<()> {
654        let result = result.map(|mut outcome| {
655            outcome.state = self.take_state();
656            let evidence = std::mem::take(&mut *self.evidence.lock());
657            let metadata = outcome.metadata.get_or_insert_with(|| {
658                crate::OutcomeMetadata::new(self.algorithm.clone(), evidence.outcome)
659            });
660            metadata.judgments.extend(evidence.judgments);
661            let provider_models = outcome
662                .selected_model_ids
663                .iter()
664                .map(|target| self.provider_model(target).clone())
665                .collect::<Vec<_>>();
666            observability::record_outcome(metadata, &provider_models);
667            outcome
668        });
669        let selected_model = result
670            .as_ref()
671            .ok()
672            .and_then(|outcome| outcome.selected_model_id().ok().cloned());
673        let step = result.map(|outcome| Step::Done(Box::new(outcome)));
674        self.step_tx
675            .send(step)
676            .await
677            .map_err(|_| DriverError::StreamClosed)?;
678        if let Some(selected_model) = selected_model {
679            observability::record_decision(&self.algorithm, self.provider_model(&selected_model));
680        }
681        Ok(())
682    }
683}
684
685/// Work requests and the terminal outcome of [`Algorithm::run_stream`].
686/// Each call carries its own reply channel, so the host can execute calls concurrently.
687pub enum Step {
688    /// The algorithm needs this model call performed. The host serves it and fulfills
689    /// it with [`CallModel::respond`]. Boxed: it is by far the largest variant.
690    CallModel(Box<CallModel>),
691    /// The host fulfills this decision call with [`CallDecision::respond`].
692    CallDecision(Box<CallDecision>),
693    /// The algorithm finished with its routing outcome — the last step of a run.
694    Done(Box<RoutingOutcome>),
695}
696
697/// Work dispatched through one host handler, with a typed reply channel per variant.
698/// [`drive`] handles terminal outcomes separately; the handler only executes calls.
699pub enum Call {
700    /// Fulfilled with an LLM [`Response`].
701    Model(Box<CallModel>),
702    /// Fulfilled with a [`DecisionResponse`].
703    Decision(Box<CallDecision>),
704}
705
706/// Drive [`Algorithm::run_stream`] to its routing outcome, serving calls concurrently.
707///
708/// The shared execution loop lets hosts supply clients or test doubles through `serve`
709/// without reimplementing stream handling and cancellation.
710///
711/// `serve` owns each [`Call`] and performs its I/O. Passing an error to `respond`
712/// lets the algorithm fall back; returning an error from `serve` aborts the run.
713///
714/// Dropping this future cancels the algorithm and pending handler futures.
715pub async fn drive<F, Fut>(
716    algorithm: Arc<dyn Algorithm>,
717    request: Request,
718    models: Arc<RuntimeModels>,
719    serve: F,
720) -> Result<RoutingOutcome>
721where
722    F: Fn(Call) -> Fut,
723    Fut: Future<Output = Result<()>>,
724{
725    drive_with_state(algorithm, request, models, State::default(), serve).await
726}
727
728/// [`drive`] starting from caller-supplied `state`.
729pub(crate) async fn drive_with_state<F, Fut>(
730    algorithm: Arc<dyn Algorithm>,
731    request: Request,
732    models: Arc<RuntimeModels>,
733    state: State,
734    serve: F,
735) -> Result<RoutingOutcome>
736where
737    F: Fn(Call) -> Fut,
738    Fut: Future<Output = Result<()>>,
739{
740    let stream = algorithm.run_stream(request, Arc::clone(&models), state);
741    tokio::pin!(stream);
742
743    let mut in_flight = futures::stream::FuturesUnordered::new();
744    let mut final_outcome: Option<RoutingOutcome> = None;
745
746    loop {
747        tokio::select! {
748            Some(result) = in_flight.next() => match result {
749                Ok(()) => {}, // Call completed successfully
750                Err(err) => return Err(err), // Call failed, propagate the error
751            },
752            step = stream.next() => {
753                match step {
754                    None => break, // stream has ended, no more steps
755                    Some(item) => match item? {
756                        Step::CallModel(call) => {
757                            models.check_request_targets(&call.request, &call.models)?;
758                            in_flight.push(serve(Call::Model(call)));
759                        }
760                        Step::CallDecision(call) => {
761                            models.check_targets(std::slice::from_ref(&call.model))?;
762                            if models.has_target_restriction
763                                && call.request.model.as_ref() != Some(&call.model)
764                            {
765                                return Err(LibsyError::AlgorithmError {
766                                    message: "decision payload model does not match selected target".into(),
767                                });
768                            }
769                            in_flight.push(serve(Call::Decision(call)));
770                        }
771                        Step::Done(outcome) => {
772                            if outcome.response.is_none() {
773                                models.check_request_targets(&outcome.request, &outcome.selected_model_ids)?;
774                            }
775                            final_outcome = Some(*outcome);
776                            break;
777                        }
778                    }
779                }
780            },
781        }
782    }
783    final_outcome.ok_or(LibsyError::MissingFinalResponse)
784}
785
786/// Recover the message from an algorithm's panic.
787fn panic_message(payload: &(dyn std::any::Any + Send)) -> String {
788    payload
789        .downcast_ref::<&'static str>()
790        .map(|message| (*message).to_string())
791        .or_else(|| payload.downcast_ref::<String>().cloned())
792        .unwrap_or_else(|| "unknown panic payload".to_string())
793}
794
795/// Abort guard
796struct AbortOnDrop(tokio::task::AbortHandle);
797
798impl Drop for AbortOnDrop {
799    fn drop(&mut self) {
800        self.0.abort();
801    }
802}
803
804/// Errors unless `targets` contains `name`.
805///
806/// Config target names must be resolved before an algorithm is built. This list contains
807/// model IDs, not target names.
808pub(crate) fn ensure_model_is_target(targets: &[ModelId], name: &ModelId) -> Result<()> {
809    targets
810        .iter()
811        .any(|target| target == name)
812        .then_some(())
813        .ok_or_else(|| LibsyError::TargetNotFound {
814            target: name.clone(),
815        })
816}
817
818/// Key for routing affinity: a root request by its session, a child request by its session
819/// and agent.
820#[derive(Clone, Hash, PartialEq, Eq)]
821pub(crate) enum RoutingIdentity {
822    /// Root request, keyed by session ID.
823    Session(String),
824    /// Child request, keyed by session and agent IDs.
825    Subagent { session: String, agent: String },
826}
827
828impl RoutingIdentity {
829    /// Builds a root or child identity from non-empty request metadata.
830    ///
831    /// A child request missing either ID returns `None`, so it keeps no routing history
832    /// rather than sharing the parent's.
833    pub(crate) fn from_request(request: &Request) -> Option<Self> {
834        let metadata = request.metadata.as_ref()?;
835        let session = metadata.session_id.as_deref().filter(|id| !id.is_empty())?;
836        if metadata.is_subagent {
837            let agent = metadata.agent_id.as_deref().filter(|id| !id.is_empty())?;
838            Some(Self::Subagent {
839                session: session.to_string(),
840                agent: agent.to_string(),
841            })
842        } else {
843            Some(Self::Session(session.to_string()))
844        }
845    }
846}
847
848/// Routing policy independent of how external calls are executed.
849/// Implement [`route`](Self::route), using [`Driver`] to request work from the host.
850/// Hosts can use [`drive`] for the shared execution loop or consume
851/// [`run_stream`](Self::run_stream) for custom execution.
852///
853/// Methods take `self: Arc<Self>`: one algorithm (`Arc<dyn Algorithm>`) is shared across
854/// requests and run concurrently, so it owns its thread-safety and any shared state.
855///
856/// # Concurrency
857///
858/// A host may run the same algorithm concurrently for many requests. Implementations
859/// must synchronize their own mutable shared state. Each call to [`run_stream`](Self::run_stream)
860/// creates an independent [`Driver`], so model-call promises and emitted [`Step`]s cannot
861/// cross between runs.
862///
863/// # Observability
864///
865/// [`run_stream`](Self::run_stream) creates a `libsy.run` span, and each offloaded model
866/// call creates a nested span for its call kind, with outcome and available token usage.
867/// Call metrics include host queueing and count unfulfilled drops as errors.
868/// Successful outcomes record their
869/// [`OutcomeMetadata::outcome_id`](crate::OutcomeMetadata::outcome_id) on `libsy.run`,
870/// alongside `selected_model_ids` (an ordered OpenTelemetry string array).
871/// `algorithm` and `switchyard.algorithm` retain the run's [`Algorithm::name`].
872/// Optional `evidence.source`, `evidence.verdict`, `evidence.trigger`, and
873/// `evidence.reason_code` are strings; `evidence.score`, `evidence.confidence`,
874/// `evidence.threshold`, `evidence.capable_score`, and `evidence.capable_threshold`
875/// are numbers. Unknown evidence fields are not exported.
876/// These fields are span attributes, never metric labels.
877///
878/// The run/call observability helpers retain `outcome` status and operational metrics,
879/// but omit error details and arbitrary request extra metadata. Algorithms and hosts
880/// may emit their own logs. Errors still reach the caller unchanged.
881/// The host controls the tracing subscriber and global OpenTelemetry
882/// meter provider; libsy installs no exporter and performs no telemetry network I/O.
883#[async_trait]
884pub trait Algorithm: Send + Sync + 'static {
885    /// Stable, low-cardinality name identifying this algorithm — the
886    /// `algorithm` attribute on every span, metric, and log line the crate
887    /// emits for its runs.
888    fn name(&self) -> &str;
889
890    /// Select a route, requesting external work through [`Driver`] as needed.
891    /// [`run_stream`](Self::run_stream) runs this method and exposes its work to the host.
892    async fn route(self: Arc<Self>, driver: Driver, request: Request) -> Result<RoutingOutcome>;
893
894    /// Whether the host should summarize served answers for [`Self::observe_answer`].
895    fn tracks_answers(&self) -> bool {
896        false
897    }
898
899    /// Records the answer the host served for a request in `session_id`.
900    ///
901    /// The host reports a streamed answer before forwarding its final chunk, so the
902    /// session's next request is routed with this answer already recorded.
903    async fn observe_answer(&self, _session_id: &str, _answer: AnswerSummary) {}
904
905    /// Expose work requests and the final outcome so the host can control execution.
906    ///
907    /// Each call waits for its host reply. A run ends with one terminal item — [`Step::Done`] on
908    /// success, an `Err` item on failure, including when the algorithm panics. Dropping
909    /// the stream aborts the spawned algorithm task.
910    ///
911    /// Every invocation owns a separate [`Driver`].
912    fn run_stream(
913        self: Arc<Self>,
914        request: Request,
915        models: Arc<RuntimeModels>,
916        state: State,
917    ) -> StepStream {
918        let (driver, step_rx) = Driver::new(self.name(), models);
919        driver.set_state(state);
920        let span = observability::run_span(self.name(), &request);
921        let handle = tokio::spawn(
922            async move {
923                let algorithm = self.name().to_string();
924                // Catch a panicking algorithm so the run still publishes a terminal step.
925                let route = AssertUnwindSafe(self.route(driver.clone(), request)).catch_unwind();
926                let result = observability::observe_run(&algorithm, async {
927                    let outcome = route.await.unwrap_or_else(|payload| {
928                        Err(LibsyError::AlgorithmError {
929                            message: format!(
930                                "algorithm task panicked: {}",
931                                panic_message(payload.as_ref())
932                            ),
933                        })
934                    })?;
935                    if outcome.response.is_none() {
936                        driver
937                            .models
938                            .check_request_targets(&outcome.request, &outcome.selected_model_ids)?;
939                    }
940                    Ok(outcome)
941                })
942                .await;
943
944                let _ = driver.finish(result).await;
945            }
946            .instrument(span),
947        );
948        // Dropping the stream aborts the algorithm task when its consumer goes away.
949        let abort_guard = AbortOnDrop(handle.abort_handle());
950        Box::pin(ReceiverStream::new(step_rx).map(move |step| {
951            // link abort guard to stream
952            let _keep_alive = &abort_guard;
953            step
954        }))
955    }
956}
957
958#[cfg(test)]
959mod tests {
960    use std::collections::HashMap;
961
962    use super::*;
963    use crate::core::testing::{Serve, ServeResult, echo, reply, serve_decision, test_drive};
964    use futures::StreamExt;
965    use switchyard_protocol::{
966        LlmResponse, LlmResponseChunk, completion_text, text_request, text_response,
967    };
968
969    #[test]
970    fn a_final_answer_has_text_and_no_unfinished_or_tool_output() {
971        let mut answer = text_response(None, "done");
972        assert!(AnswerSummary::of(&answer).final_reply);
973        answer.outputs[0].stop_reason = Some(StopReason::MaxTokens);
974        assert!(!AnswerSummary::of(&answer).final_reply);
975        answer.outputs[0].stop_reason = Some(StopReason::EndTurn);
976        let mut tool = answer.outputs[0].clone();
977        tool.content = vec![ContentBlock::ToolCall(switchyard_protocol::ToolCall {
978            id: "call".into(),
979            name: "bash".into(),
980            arguments: serde_json::json!({}),
981        })];
982        answer.outputs.push(tool);
983        assert!(!AnswerSummary::of(&answer).final_reply);
984        answer.outputs.pop();
985        answer.outputs[0].content = vec![ContentBlock::Text { text: "  ".into() }];
986        assert!(!AnswerSummary::of(&answer).final_reply);
987        assert!(!AnswerSummary::of(&AggLlmResponse::default()).final_reply);
988    }
989
990    #[derive(Debug, thiserror::Error)]
991    #[error("{0}")]
992    struct TestError(&'static str);
993
994    fn test_error(message: &'static str) -> LibsyError {
995        LibsyError::external("test", TestError(message))
996    }
997
998    /// Trivial algo used only to exercise the orchestrator: calls the first target
999    /// and returns its response as the routing outcome.
1000    struct TestAlgo {
1001        target_set: Vec<ModelId>,
1002    }
1003
1004    #[async_trait]
1005    impl Algorithm for TestAlgo {
1006        fn name(&self) -> &str {
1007            "test"
1008        }
1009
1010        async fn route(
1011            self: Arc<Self>,
1012            driver: Driver,
1013            request: Request,
1014        ) -> Result<RoutingOutcome> {
1015            let target = self
1016                .target_set
1017                .first()
1018                .ok_or(LibsyError::NoTargets)?
1019                .clone();
1020            let response = driver
1021                .call_model(request.clone(), vec![target.clone()])
1022                .await?;
1023            driver.record_judgment(
1024                Some(crate::Score {
1025                    target: target.clone(),
1026                    category: Some(Category::Capable),
1027                    confidence: 1.0,
1028                }),
1029                Some(serde_json::json!({"source": "judge"})),
1030            );
1031            driver.set_evidence(serde_json::json!({"source": "test"}));
1032            driver.set_evidence_if_empty(serde_json::json!({"source": "ignored"}));
1033            Ok(RoutingOutcome::answered(target, request, response))
1034        }
1035    }
1036
1037    /// Build a shared `TestAlgo` over the given target set.
1038    fn orch(target_set: Vec<ModelId>) -> Arc<dyn Algorithm> {
1039        Arc::new(TestAlgo { target_set })
1040    }
1041
1042    fn request() -> Request {
1043        Request {
1044            llm_request: text_request(Some("auto".to_string()), "hi".to_string()),
1045            raw_request: None,
1046            metadata: None,
1047        }
1048    }
1049
1050    #[test]
1051    fn routing_outcome_constructors_stamp_selection_and_preserve_payloads() {
1052        let outcome = RoutingOutcome::route_to(
1053            "selected".into(),
1054            target_set(&["fallback-one", "fallback-two"]),
1055            request(),
1056        );
1057
1058        assert_eq!(
1059            outcome.selected_model_ids,
1060            target_set(&["selected", "fallback-one", "fallback-two"])
1061        );
1062        assert_eq!(outcome.request.model_id().as_deref(), Some("selected"));
1063        assert!(outcome.response.is_none());
1064        assert!(outcome.metadata.is_none());
1065
1066        let outcome = RoutingOutcome::route_to("only".into(), Vec::new(), request());
1067        assert_eq!(outcome.selected_model_ids, target_set(&["only"]));
1068
1069        let outcome = RoutingOutcome::answered(
1070            "answered".into(),
1071            request(),
1072            Response {
1073                llm_response: LlmResponse::Agg(text_response(None, "existing")),
1074                metadata: None,
1075                upstream_headers: http::HeaderMap::new(),
1076            },
1077        );
1078
1079        assert_eq!(outcome.selected_model_ids, target_set(&["answered"]));
1080        assert_eq!(outcome.request.model_id().as_deref(), Some("answered"));
1081        assert_eq!(
1082            outcome
1083                .response
1084                .as_ref()
1085                .and_then(|response| response.llm_response.as_agg())
1086                .map(completion_text),
1087            Some("existing".to_string())
1088        );
1089    }
1090
1091    fn target_set(names: &[&str]) -> Vec<ModelId> {
1092        names.iter().map(|name| ModelId::from(*name)).collect()
1093    }
1094
1095    enum TargetProbe {
1096        Model(&'static [&'static str]),
1097        Decision(&'static str),
1098        Completion(&'static [&'static str]),
1099        MismatchedCompletion,
1100    }
1101
1102    #[async_trait]
1103    impl Algorithm for TargetProbe {
1104        fn name(&self) -> &str {
1105            "target_probe"
1106        }
1107
1108        async fn route(
1109            self: Arc<Self>,
1110            driver: Driver,
1111            request: Request,
1112        ) -> Result<RoutingOutcome> {
1113            match &*self {
1114                Self::Model(models) => {
1115                    let response = driver
1116                        .call_model(request.clone(), target_set(models))
1117                        .await?;
1118                    Ok(RoutingOutcome::answered(
1119                        models[0].into(),
1120                        request,
1121                        response,
1122                    ))
1123                }
1124                Self::Decision(model) => {
1125                    driver
1126                        .call_decision(
1127                            DecisionRequest {
1128                                model: None,
1129                                input: Value::Null,
1130                                questions: Default::default(),
1131                            },
1132                            (*model).into(),
1133                        )
1134                        .await?;
1135                    Ok(RoutingOutcome::route_to("allowed".into(), vec![], request))
1136                }
1137                Self::Completion(models) => Ok(RoutingOutcome::route_to(
1138                    models[0].into(),
1139                    target_set(&models[1..]),
1140                    request,
1141                )),
1142                Self::MismatchedCompletion => {
1143                    let mut outcome = RoutingOutcome::route_to("allowed".into(), vec![], request);
1144                    outcome.request.llm_request.model = Some("outside".into());
1145                    Ok(outcome)
1146                }
1147            }
1148        }
1149    }
1150
1151    struct RewrittenSteps(Arc<TargetProbe>, fn(&mut Step));
1152
1153    #[async_trait]
1154    impl Algorithm for RewrittenSteps {
1155        fn name(&self) -> &str {
1156            "rewritten_steps"
1157        }
1158
1159        async fn route(
1160            self: Arc<Self>,
1161            driver: Driver,
1162            request: Request,
1163        ) -> Result<RoutingOutcome> {
1164            Arc::clone(&self.0).route(driver, request).await
1165        }
1166
1167        fn run_stream(
1168            self: Arc<Self>,
1169            request: Request,
1170            models: Arc<RuntimeModels>,
1171            state: State,
1172        ) -> StepStream {
1173            Box::pin(
1174                Arc::clone(&self.0)
1175                    .run_stream(request, models, state)
1176                    .map(move |step| {
1177                        step.map(|mut step| {
1178                            (self.1)(&mut step);
1179                            step
1180                        })
1181                    }),
1182            )
1183        }
1184    }
1185
1186    fn restricted_models() -> RuntimeModels {
1187        RuntimeModels::new(HashMap::from([
1188            (Category::Any, target_set(&["allowed", "fallback"])),
1189            (Category::Judge, target_set(&["judge"])),
1190        ]))
1191        .with_target_restriction()
1192        .with_subagent(HashMap::from([(Category::Any, target_set(&["subagent"]))]))
1193    }
1194
1195    #[tokio::test]
1196    async fn target_restriction_checks_default_streams() {
1197        for probe in [
1198            TargetProbe::Model(&["outside"]),
1199            TargetProbe::Model(&["allowed", "outside"]),
1200            TargetProbe::Decision("outside"),
1201            TargetProbe::Completion(&["outside"]),
1202            TargetProbe::Completion(&["allowed", "outside"]),
1203        ] {
1204            let mut stream = Arc::new(probe).run_stream(
1205                request(),
1206                Arc::new(restricted_models()),
1207                State::default(),
1208            );
1209            assert!(matches!(
1210                stream.next().await,
1211                Some(Err(LibsyError::TargetNotFound { target })) if target == "outside"
1212            ));
1213            assert!(stream.next().await.is_none());
1214        }
1215        let mut stream = Arc::new(TargetProbe::MismatchedCompletion).run_stream(
1216            request(),
1217            Arc::new(restricted_models()),
1218            State::default(),
1219        );
1220        assert!(matches!(
1221            stream.next().await,
1222            Some(Err(LibsyError::AlgorithmError { .. }))
1223        ));
1224
1225        let mut stream = Arc::new(TargetProbe::Model(&["outside"])).run_stream(
1226            request(),
1227            Arc::new(RuntimeModels::default()),
1228            State::default(),
1229        );
1230        assert!(matches!(stream.next().await, Some(Ok(Step::CallModel(_)))));
1231    }
1232
1233    #[tokio::test]
1234    async fn target_restriction_rechecks_rewritten_steps() {
1235        for probe in [
1236            TargetProbe::Model(&["allowed"]),
1237            TargetProbe::Decision("judge"),
1238            TargetProbe::Completion(&["allowed"]),
1239        ] {
1240            let probe = Arc::new(probe);
1241            let run = |rewrite| {
1242                drive(
1243                    Arc::new(RewrittenSteps(Arc::clone(&probe), rewrite)),
1244                    request(),
1245                    Arc::new(restricted_models()),
1246                    |_| async { panic!("invalid work must not reach the host") },
1247                )
1248            };
1249            let result = run(|step| match step {
1250                Step::CallModel(call) => call.models.push("outside".into()),
1251                Step::CallDecision(call) => call.model = "outside".into(),
1252                Step::Done(outcome) => outcome.selected_model_ids.push("outside".into()),
1253            })
1254            .await;
1255            assert!(
1256                matches!(result, Err(LibsyError::TargetNotFound { target }) if target == "outside")
1257            );
1258
1259            let result = run(|step| match step {
1260                Step::CallModel(call) => call.request.llm_request.model = Some("outside".into()),
1261                Step::CallDecision(call) => call.request.model = Some("allowed".into()),
1262                Step::Done(outcome) => outcome.request.llm_request.model = Some("outside".into()),
1263            })
1264            .await;
1265            assert!(matches!(result, Err(LibsyError::AlgorithmError { .. })));
1266        }
1267    }
1268
1269    #[tokio::test]
1270    async fn target_restriction_preserves_allowed_work() -> Result<()> {
1271        for (probe, expected) in [
1272            (
1273                TargetProbe::Model(&["allowed", "fallback"]),
1274                &["allowed"][..],
1275            ),
1276            (TargetProbe::Model(&["judge"]), &["judge"][..]),
1277            (TargetProbe::Decision("judge"), &["allowed"][..]),
1278            (
1279                TargetProbe::Completion(&["allowed", "fallback"]),
1280                &["allowed", "fallback"][..],
1281            ),
1282            (TargetProbe::Completion(&["subagent"]), &["subagent"][..]),
1283        ] {
1284            let outcome = drive(
1285                Arc::new(probe),
1286                request(),
1287                Arc::new(restricted_models()),
1288                |call| async move {
1289                    match call {
1290                        Call::Model(call) => {
1291                            call.respond(std::future::ready(Ok(reply("ok")))).await
1292                        }
1293                        Call::Decision(call) => serve_decision(*call).await,
1294                    }
1295                },
1296            )
1297            .await?;
1298            assert_eq!(outcome.selected_model_ids, target_set(expected));
1299        }
1300        let outcome = drive(
1301            Arc::new(crate::Noop {}),
1302            request(),
1303            Arc::new(RuntimeModels::default().with_target_restriction()),
1304            |_| async { panic!("Noop must not request model calls") },
1305        )
1306        .await?;
1307        assert!(outcome.response.is_some());
1308        Ok(())
1309    }
1310
1311    #[tokio::test]
1312    async fn typed_driver_preserves_call_and_stream_boundaries() -> Result<()> {
1313        tokio::time::timeout(std::time::Duration::from_secs(1), async {
1314            // Distinct oneshots keep reverse-order replies paired with their producers, and a
1315            // retained call remains pending until the host responds.
1316            let (driver, mut step_rx) = Driver::new("test", Arc::new(RuntimeModels::default()));
1317            let first_driver = driver.clone();
1318            let mut first = tokio::spawn(async move {
1319                first_driver
1320                    .call_model(request(), vec![ModelId::from("first")])
1321                    .await
1322            });
1323            let second = tokio::spawn(async move {
1324                driver
1325                    .call_model(request(), vec![ModelId::from("second")])
1326                    .await
1327            });
1328
1329            let mut calls = HashMap::new();
1330            for _ in 0..2 {
1331                let step = step_rx.recv().await.ok_or(DriverError::StreamClosed)??;
1332                let Step::CallModel(call) = step else {
1333                    return Err(test_error("expected a CallModel step"));
1334                };
1335                let selected_model = call
1336                    .models
1337                    .first()
1338                    .ok_or_else(|| test_error("model call has no candidates"))?
1339                    .to_string();
1340                calls.insert(selected_model, call);
1341            }
1342            assert!(
1343                tokio::time::timeout(std::time::Duration::from_millis(20), &mut first)
1344                    .await
1345                    .is_err(),
1346                "call completed before the host responded"
1347            );
1348            calls
1349                .remove("second")
1350                .ok_or_else(|| test_error("missing second call"))?
1351                .respond(std::future::ready(Ok(reply("second response")))).await?;
1352            calls
1353                .remove("first")
1354                .ok_or_else(|| test_error("missing first call"))?
1355                .respond(std::future::ready(Ok(reply("first response")))).await?;
1356
1357            let first_response = first
1358                .await
1359                .map_err(|source| LibsyError::external("joining a test task", source))??;
1360            let second_response = second
1361                .await
1362                .map_err(|source| LibsyError::external("joining a test task", source))??;
1363            assert_eq!(
1364                first_response.llm_response.as_agg().map(completion_text),
1365                Some("first response".to_string())
1366            );
1367            assert_eq!(
1368                second_response.llm_response.as_agg().map(completion_text),
1369                Some("second response".to_string())
1370            );
1371
1372            // Dropping the host-facing promise closes only that call's reply channel.
1373            let (driver, mut step_rx) = Driver::new("test", Arc::new(RuntimeModels::default()));
1374            let producer = tokio::spawn(async move {
1375                driver
1376                    .call_model(request(), vec![ModelId::from("dropped")])
1377                    .await
1378            });
1379            let step = step_rx.recv().await.ok_or(DriverError::StreamClosed)??;
1380            let Step::CallModel(call) = step else {
1381                return Err(test_error("expected a CallModel step"));
1382            };
1383            drop(call);
1384            let result = producer
1385                .await
1386                .map_err(|source| LibsyError::external("joining a test task", source))?;
1387            assert!(matches!(
1388                result,
1389                Err(LibsyError::Driver(DriverError::ResponseDropped))
1390            ));
1391
1392            // A standalone driver reports the typed step receiver disappearing at its next call.
1393            let (driver, step_rx) = Driver::new("test", Arc::new(RuntimeModels::default()));
1394            drop(step_rx);
1395            let result = driver
1396                .call_model(request(), vec![ModelId::from("closed")])
1397                .await;
1398            assert!(matches!(
1399                result,
1400                Err(LibsyError::Driver(DriverError::StreamClosed))
1401            ));
1402
1403            fn decision_request() -> DecisionRequest {
1404                DecisionRequest {
1405                    model: Some("overwritten".into()),
1406                    input: serde_json::json!({"task": "choose a route"}),
1407                    questions: Default::default(),
1408                }
1409            }
1410
1411            fn decision_response() -> DecisionResponse {
1412                DecisionResponse {
1413                    id: Some("decision-1".to_string()),
1414                    model: Some("provider-model".into()),
1415                    answers: [(
1416                        "p_solve".to_string(),
1417                        switchyard_protocol::DecisionAnswer {
1418                            value: switchyard_protocol::DecisionValue::Boolean(
1419                                switchyard_protocol::BooleanEstimate::ProbabilityTrue(
1420                                    switchyard_protocol::Probability(0.8),
1421                                ),
1422                            ),
1423                            provider_confidence: None,
1424                        },
1425                    )]
1426                    .into(),
1427                    usage: Default::default(),
1428                }
1429            }
1430
1431            struct MixedCalls(&'static str);
1432
1433            #[async_trait]
1434            impl Algorithm for MixedCalls {
1435                fn name(&self) -> &str {
1436                    "mixed"
1437                }
1438
1439                async fn route(
1440                    self: Arc<Self>,
1441                    driver: Driver,
1442                    request: Request,
1443                ) -> Result<RoutingOutcome> {
1444                    let (llm, decision) = tokio::join!(
1445                        driver.call_model(request.clone(), vec!["llm".into()]),
1446                        driver.call_decision(decision_request(), "decision".into()),
1447                    );
1448                    assert_eq!(
1449                        llm?.llm_response.as_agg().map(completion_text),
1450                        Some("llm reply".into())
1451                    );
1452                    match self.0 {
1453                        "mock" => assert_eq!(decision?, DecisionResponse {
1454                            id: None,
1455                            model: Some("decision".into()),
1456                            answers: Default::default(),
1457                            usage: Default::default(),
1458                        }),
1459                        "reply" => assert_eq!(decision?, decision_response()),
1460                        "error" => assert!(matches!(
1461                            decision,
1462                            Err(LibsyError::AlgorithmError { message }) if message == "provider failed"
1463                        )),
1464                        "drop" => assert!(matches!(
1465                            decision,
1466                            Err(LibsyError::Driver(DriverError::ResponseDropped))
1467                        )),
1468                        "abort" => return std::future::pending().await,
1469                        _ => unreachable!(),
1470                    }
1471                    Ok(RoutingOutcome::route_to("answer".into(), vec![], request))
1472                }
1473            }
1474
1475            for mode in ["mock", "reply", "error", "drop", "abort"] {
1476                // Serial dispatch would deadlock here and fail the enclosing timeout.
1477                let barrier = Arc::new(tokio::sync::Barrier::new(2));
1478                let outcome = drive(
1479                    Arc::new(MixedCalls(mode)),
1480                    request(),
1481                    Arc::new(RuntimeModels::default()),
1482                    move |call| {
1483                        let barrier = barrier.clone();
1484                        async move {
1485                            barrier.wait().await;
1486                            let call = match call {
1487                                Call::Model(call) => return call.respond(std::future::ready(Ok(reply("llm reply")))).await,
1488                                Call::Decision(call) => *call,
1489                            };
1490                            assert_eq!(call.algorithm, "mixed");
1491                            assert_eq!(call.model, "decision");
1492                            assert_eq!(call.request.model, Some("decision".into()));
1493                            assert_eq!(call.request.input, decision_request().input);
1494                            match mode {
1495                                "mock" => serve_decision(call).await,
1496                                "reply" => call.respond(std::future::ready(Ok(decision_response()))).await,
1497                                "error" => call.respond(std::future::ready(Err(LibsyError::AlgorithmError {
1498                                    message: "provider failed".into(),
1499                                }))).await,
1500                                "drop" => {
1501                                    drop(call);
1502                                    Ok(())
1503                                }
1504                                "abort" => call.fail(test_error("host aborted")),
1505                                _ => unreachable!(),
1506                            }
1507                        }
1508                    },
1509                )
1510                .await;
1511                if mode == "abort" {
1512                    assert!(matches!(outcome, Err(LibsyError::External { .. })));
1513                } else {
1514                    assert_eq!(outcome?.selected_model_id()?, "answer");
1515                }
1516            }
1517
1518            let (driver, mut steps) = Driver::new("test", Arc::new(RuntimeModels::default()));
1519            let mut pending = Box::pin(driver.call_decision(decision_request(), "decision".into()));
1520            assert!(futures::poll!(&mut pending).is_pending());
1521            let Some(Ok(Step::CallDecision(call))) = steps.recv().await else {
1522                return Err(test_error("expected a decision call"));
1523            };
1524            drop(pending);
1525            call.respond(async { panic!("cancelled work must not be polled") }).await?;
1526            drop(steps);
1527            assert!(matches!(
1528                driver.call_decision(decision_request(), "decision".into()).await,
1529                Err(LibsyError::Driver(DriverError::StreamClosed))
1530            ));
1531            Ok(())
1532        })
1533        .await
1534        .map_err(|error| LibsyError::external("waiting for typed driver boundaries", error))?
1535    }
1536
1537    #[test]
1538    fn target_lookup_returns_the_missing_target() {
1539        let error = ensure_model_is_target(&target_set(&[]), &ModelId::from("missing")).err();
1540        assert!(matches!(
1541            error,
1542            Some(LibsyError::TargetNotFound { target }) if target == "missing"
1543        ));
1544    }
1545
1546    /// Build a single-target algo, plus a `serve` that answers it as a token stream
1547    /// replaying `chunks` in order (as `Ok` items).
1548    fn streaming_orch(chunks: Vec<LlmResponseChunk>) -> (Arc<dyn Algorithm>, impl Serve) {
1549        let algo = orch(target_set(&["stream/model"]));
1550        let serve = move |_target: ModelId, _request: Request| {
1551            let chunks = chunks.clone();
1552            async move {
1553                let stream =
1554                    futures::stream::iter(chunks.into_iter().map(|chunk| Ok(chunk.into()))).boxed();
1555                Ok(Response {
1556                    llm_response: LlmResponse::Stream(stream),
1557                    metadata: None,
1558                    upstream_headers: http::HeaderMap::new(),
1559                })
1560            }
1561        };
1562        (algo, serve)
1563    }
1564
1565    #[tokio::test]
1566    async fn run_returns_a_streamed_response_the_caller_aggregates() -> Result<()> {
1567        // A streaming client -> its chunks flow through the promise and `Done`,
1568        // and `run` returns the live stream untouched for the caller to fold.
1569        let (orch, serve) = streaming_orch(vec![
1570            LlmResponseChunk::MessageStart {
1571                id: Some("m1".to_string()),
1572                model: Some("stream/model".to_string()),
1573            },
1574            LlmResponseChunk::TextDelta {
1575                index: 0,
1576                text: "hel".to_string(),
1577            },
1578            LlmResponseChunk::TextDelta {
1579                index: 0,
1580                text: "lo".to_string(),
1581            },
1582            LlmResponseChunk::MessageStop {
1583                reason: Some("stop".to_string()),
1584            },
1585        ]);
1586        let (selected_model, response) = test_drive(orch, request(), serve).await?;
1587        // The run handed back the live stream; the caller folds it to a buffered aggregate.
1588        let agg = response
1589            .llm_response
1590            .into_agg()
1591            .await
1592            .map_err(|error| LibsyError::external("aggregating response stream", error))?;
1593        assert_eq!(completion_text(&agg), "hello");
1594        assert_eq!(agg.model.as_deref(), Some("stream/model"));
1595        assert_eq!(selected_model, "stream/model");
1596        Ok(())
1597    }
1598
1599    #[tokio::test]
1600    async fn aggregating_a_streamed_response_propagates_a_mid_stream_error() -> Result<()> {
1601        // The run succeeds and returns the stream; the in-band `Error` chunk surfaces only
1602        // when the caller aggregates it.
1603        let (orch, serve) = streaming_orch(vec![
1604            LlmResponseChunk::TextDelta {
1605                index: 0,
1606                text: "partial".to_string(),
1607            },
1608            LlmResponseChunk::StreamError {
1609                message: "upstream exploded".to_string(),
1610            },
1611        ]);
1612        let (_, response) = test_drive(orch, request(), serve).await?;
1613        match response.llm_response.into_agg().await {
1614            Ok(_) => panic!("expected a mid-stream error, got an aggregate"),
1615            Err(err) => {
1616                assert!(err.to_string().contains("upstream exploded"));
1617                Ok(())
1618            }
1619        }
1620    }
1621
1622    #[tokio::test]
1623    async fn run_offloads_via_promise_then_finishes() -> Result<()> {
1624        // Every call is offloaded via a promise the orchestrator surfaces as a
1625        // `CallModel` step for us to fulfill.
1626        let stream = orch(target_set(&["offload/model"])).run_stream(
1627            request(),
1628            Arc::new(RuntimeModels::default()),
1629            State::default(),
1630        );
1631        tokio::pin!(stream);
1632
1633        let mut saw_call = false;
1634        let mut final_completion = None;
1635        while let Some(step) = stream.next().await {
1636            match step? {
1637                Step::CallDecision(_) => return Err(test_error("unexpected decision call")),
1638                Step::CallModel(call) => {
1639                    saw_call = true;
1640                    assert_eq!(call.models, vec![ModelId::from("offload/model")]);
1641                    // Fulfilling the promise is the "real" model call the caller makes.
1642                    call.respond(std::future::ready(Ok(Response {
1643                        llm_response: LlmResponse::Agg(text_response(
1644                            None,
1645                            "fulfilled".to_string(),
1646                        )),
1647                        metadata: None,
1648                        upstream_headers: http::HeaderMap::new(),
1649                    })))
1650                    .await?;
1651                }
1652                Step::Done(outcome) => {
1653                    let metadata = outcome
1654                        .metadata
1655                        .as_ref()
1656                        .expect("run_stream should attach outcome metadata");
1657                    assert_eq!(metadata.algorithm, "test");
1658                    assert_eq!(
1659                        uuid::Uuid::parse_str(metadata.outcome_id())
1660                            .expect("outcome id should be a UUID")
1661                            .get_version_num(),
1662                        7
1663                    );
1664                    assert_eq!(
1665                        metadata.evidence,
1666                        Some(serde_json::json!({"source": "test"}))
1667                    );
1668                    assert_eq!(
1669                        metadata.judgments[0].evidence,
1670                        Some(serde_json::json!({"source": "judge"}))
1671                    );
1672                    let response = outcome
1673                        .response
1674                        .ok_or_else(|| test_error("expected an answered outcome"))?;
1675                    final_completion = Some(
1676                        response
1677                            .llm_response
1678                            .as_agg()
1679                            .map(completion_text)
1680                            .unwrap_or_default(),
1681                    );
1682                }
1683            }
1684        }
1685
1686        assert!(saw_call, "expected a CallModel step before Done");
1687        assert_eq!(
1688            final_completion.ok_or_else(|| test_error("no Done step"))?,
1689            "fulfilled"
1690        );
1691        Ok(())
1692    }
1693
1694    #[tokio::test(flavor = "multi_thread", worker_threads = 12)]
1695    async fn requests_are_processed_in_parallel() -> Result<()> {
1696        use std::time::Duration;
1697        use tokio::sync::Barrier;
1698
1699        const N: usize = 12;
1700
1701        // Serving blocks until all N concurrent calls have arrived. If requests were
1702        // serialized (one algorithm behind a `Mutex`), only one call could be in flight,
1703        // the barrier would never reach N, and the test would time out. It passes only
1704        // because the shared algorithm is driven concurrently across requests.
1705        let barrier = Arc::new(Barrier::new(N));
1706        // One shared algorithm driven by many concurrent requests.
1707        let algo = orch(target_set(&["m"]));
1708
1709        let mut handles = Vec::new();
1710        for _ in 0..N {
1711            let algo = algo.clone();
1712            let barrier = barrier.clone();
1713            let serve = move |target: ModelId, _request: Request| {
1714                let barrier = barrier.clone();
1715                async move {
1716                    barrier.wait().await;
1717                    Ok(reply(target))
1718                }
1719            };
1720            handles.push(tokio::spawn(async move {
1721                test_drive(algo, request(), serve)
1722                    .await
1723                    .map(|(_, response)| {
1724                        response
1725                            .llm_response
1726                            .as_agg()
1727                            .map(completion_text)
1728                            .unwrap_or_default()
1729                    })
1730            }));
1731        }
1732
1733        for handle in handles {
1734            // The timeout turns a serialization deadlock into a failure, not a hang.
1735            let completion = tokio::time::timeout(Duration::from_secs(5), handle)
1736                .await
1737                .map_err(|error| LibsyError::external("waiting for test task", error))?
1738                .map_err(|source| LibsyError::external("joining a test task", source))??;
1739            assert_eq!(completion, "m");
1740        }
1741        Ok(())
1742    }
1743
1744    #[tokio::test]
1745    async fn offload_error_propagates_back_to_the_algorithm() -> Result<()> {
1746        // A client-less target offloads its call; we fulfill the promise with an
1747        // Err, which must flow back through `call_model_target` into the algorithm and
1748        // out as an error step — not a response.
1749        let stream = orch(target_set(&["offload/model"])).run_stream(
1750            request(),
1751            Arc::new(RuntimeModels::default()),
1752            State::default(),
1753        );
1754        tokio::pin!(stream);
1755
1756        let mut saw_error = false;
1757        while let Some(step) = stream.next().await {
1758            match step {
1759                Ok(Step::CallDecision(_)) => return Err(test_error("unexpected decision call")),
1760                Ok(Step::CallModel(mut call)) => {
1761                    call.recover_errors = true;
1762                    call.respond(std::future::ready(Err(test_error(
1763                        "upstream model call failed",
1764                    ))))
1765                    .await?;
1766                }
1767                Ok(Step::Done(..)) => {
1768                    return Err(test_error(
1769                        "expected the offload error to propagate, got a response",
1770                    ));
1771                }
1772                Err(err) => {
1773                    // The algorithm's `call_model_target` saw the error via the promise.
1774                    assert!(err.to_string().contains("upstream model call failed"));
1775                    saw_error = true;
1776                }
1777            }
1778        }
1779
1780        assert!(saw_error, "expected an error step");
1781        Ok(())
1782    }
1783
1784    #[tokio::test]
1785    async fn dropping_the_stream_cancels_the_algorithm_task() -> Result<()> {
1786        use std::sync::atomic::{AtomicBool, Ordering};
1787        use std::time::Duration;
1788        use tokio::sync::mpsc;
1789
1790        // Sets a flag when dropped, so we can observe whether the algorithm task was
1791        // cancelled/dropped.
1792        struct DropGuard(Arc<AtomicBool>);
1793        impl Drop for DropGuard {
1794            fn drop(&mut self) {
1795                self.0.store(true, Ordering::SeqCst);
1796            }
1797        }
1798
1799        struct StuckAlgo {
1800            started: mpsc::UnboundedSender<()>,
1801            dropped: Arc<AtomicBool>,
1802        }
1803
1804        #[async_trait]
1805        impl Algorithm for StuckAlgo {
1806            fn name(&self) -> &str {
1807                "stuck"
1808            }
1809
1810            async fn route(
1811                self: Arc<Self>,
1812                _driver: Driver,
1813                _request: Request,
1814            ) -> Result<RoutingOutcome> {
1815                let _guard = DropGuard(self.dropped.clone());
1816                let _ = self.started.send(());
1817                // Await forever without ever touching the driver.
1818                std::future::pending::<()>().await;
1819                unreachable!()
1820            }
1821        }
1822
1823        let (started_tx, mut started_rx) = mpsc::unbounded_channel();
1824        let dropped = Arc::new(AtomicBool::new(false));
1825        let algo: Arc<dyn Algorithm> = Arc::new(StuckAlgo {
1826            started: started_tx,
1827            dropped: dropped.clone(),
1828        });
1829
1830        let stream = algo.run_stream(
1831            request(),
1832            Arc::new(RuntimeModels::default()),
1833            State::default(),
1834        );
1835        started_rx
1836            .recv()
1837            .await
1838            .ok_or_else(|| test_error("task never started"))?;
1839        drop(stream);
1840        tokio::time::sleep(Duration::from_millis(100)).await;
1841
1842        assert!(
1843            dropped.load(Ordering::SeqCst),
1844            "algorithm task was NOT cancelled after dropping the stream"
1845        );
1846        Ok(())
1847    }
1848
1849    #[tokio::test]
1850    async fn route_panic_surfaces_as_a_stream_error() -> Result<()> {
1851        // An algorithm whose task panics must surface an `Err` step carrying the panic
1852        // message, not abort the process from an unobserved detached task.
1853        struct Panicky;
1854
1855        #[async_trait]
1856        impl Algorithm for Panicky {
1857            fn name(&self) -> &str {
1858                "panicky"
1859            }
1860
1861            async fn route(
1862                self: Arc<Self>,
1863                _driver: Driver,
1864                _request: Request,
1865            ) -> Result<RoutingOutcome> {
1866                panic!("boom");
1867            }
1868        }
1869
1870        let algo: Arc<dyn Algorithm> = Arc::new(Panicky);
1871        let stream = algo.run_stream(
1872            request(),
1873            Arc::new(RuntimeModels::default()),
1874            State::default(),
1875        );
1876        tokio::pin!(stream);
1877
1878        let mut saw_error = false;
1879        while let Some(step) = stream.next().await {
1880            match step {
1881                Err(err) => {
1882                    // The panic message is preserved, not flattened into an opaque failure.
1883                    assert!(err.to_string().contains("algorithm task panicked: boom"));
1884                    saw_error = true;
1885                }
1886                Ok(_) => return Err(test_error("expected the panic to surface as an error step")),
1887            }
1888        }
1889
1890        assert!(saw_error, "expected an error step from the panicked task");
1891        Ok(())
1892    }
1893
1894    /// A panicking algorithm must publish its terminal step even when it left a `Driver`
1895    /// clone alive in another task. That clone holds the step channel open, so a run that
1896    /// merely unwound would never terminate and the consumer would wait forever.
1897    #[tokio::test]
1898    async fn a_panic_with_a_leaked_driver_clone_still_terminates_the_run() -> Result<()> {
1899        struct LeakyPanic;
1900
1901        #[async_trait]
1902        impl Algorithm for LeakyPanic {
1903            fn name(&self) -> &str {
1904                "leaky_panic"
1905            }
1906
1907            async fn route(
1908                self: Arc<Self>,
1909                driver: Driver,
1910                _request: Request,
1911            ) -> Result<RoutingOutcome> {
1912                tokio::spawn(async move {
1913                    // Outlives the panic below, keeping a sender clone alive.
1914                    let _keep_alive = driver;
1915                    std::future::pending::<()>().await;
1916                });
1917                tokio::task::yield_now().await;
1918                panic!("boom");
1919            }
1920        }
1921
1922        let algo: Arc<dyn Algorithm> = Arc::new(LeakyPanic);
1923        // The timeout turns the hang this guards against into a failure rather than a hang.
1924        let result = tokio::time::timeout(
1925            std::time::Duration::from_secs(1),
1926            test_drive(algo, request(), echo()),
1927        )
1928        .await
1929        .map_err(|error| LibsyError::external("waiting for the panicked run to end", error))?;
1930
1931        match result {
1932            Ok(_) => Err(test_error(
1933                "expected the panic to end the run with an error",
1934            )),
1935            Err(err) => {
1936                assert!(err.to_string().contains("algorithm task panicked: boom"));
1937                Ok(())
1938            }
1939        }
1940    }
1941
1942    #[tokio::test]
1943    async fn cancelling_run_cancels_the_algorithm_task() -> Result<()> {
1944        use std::sync::atomic::{AtomicBool, Ordering};
1945        use std::time::Duration;
1946        use tokio::sync::mpsc;
1947
1948        // Sets a flag when dropped, so we can observe whether the algorithm task was
1949        // cancelled once the `run` future driving it is dropped.
1950        struct DropGuard(Arc<AtomicBool>);
1951        impl Drop for DropGuard {
1952            fn drop(&mut self) {
1953                self.0.store(true, Ordering::SeqCst);
1954            }
1955        }
1956
1957        struct StuckAlgo {
1958            started: mpsc::UnboundedSender<()>,
1959            dropped: Arc<AtomicBool>,
1960        }
1961
1962        #[async_trait]
1963        impl Algorithm for StuckAlgo {
1964            fn name(&self) -> &str {
1965                "stuck"
1966            }
1967
1968            async fn route(
1969                self: Arc<Self>,
1970                _driver: Driver,
1971                _request: Request,
1972            ) -> Result<RoutingOutcome> {
1973                let _guard = DropGuard(self.dropped.clone());
1974                let _ = self.started.send(());
1975                // Hang forever without ever touching the driver, so only cancellation
1976                // (not a dropped step channel) can stop this task.
1977                std::future::pending::<()>().await;
1978                unreachable!()
1979            }
1980        }
1981
1982        let (started_tx, mut started_rx) = mpsc::unbounded_channel();
1983        let dropped = Arc::new(AtomicBool::new(false));
1984        let algo: Arc<dyn Algorithm> = Arc::new(StuckAlgo {
1985            started: started_tx,
1986            dropped: dropped.clone(),
1987        });
1988
1989        // Drive the run on its own task, wait until the algorithm task is up, then cancel
1990        // it — dropping its future (and the `run_stream` stream it holds).
1991        let run_task = tokio::spawn(async move { test_drive(algo, request(), echo()).await });
1992        started_rx
1993            .recv()
1994            .await
1995            .ok_or_else(|| test_error("task never started"))?;
1996        run_task.abort();
1997        tokio::time::sleep(Duration::from_millis(100)).await;
1998
1999        assert!(
2000            dropped.load(Ordering::SeqCst),
2001            "algorithm task was NOT cancelled after cancelling run"
2002        );
2003        Ok(())
2004    }
2005
2006    // --- first-wins hedging: `run` must not wait on losing speculative calls -------------
2007
2008    /// Offloads two targets concurrently and returns the first to resolve, dropping the
2009    /// loser's call (first-wins hedging).
2010    struct Hedge {
2011        winner: String,
2012        loser: String,
2013    }
2014
2015    #[async_trait]
2016    impl Algorithm for Hedge {
2017        fn name(&self) -> &str {
2018            "hedge"
2019        }
2020
2021        async fn route(
2022            self: Arc<Self>,
2023            driver: Driver,
2024            request: Request,
2025        ) -> Result<RoutingOutcome> {
2026            let outcome_request = request.clone();
2027            let win = driver.call_model(request.clone(), vec![self.winner.clone().into()]);
2028            let lose = driver.call_model(request, vec![self.loser.clone().into()]);
2029            // First to resolve wins; `select!` drops the losing future (and its promise).
2030            tokio::select! {
2031                res = win => Ok(RoutingOutcome::answered(
2032                    self.winner.clone().into(),
2033                    outcome_request,
2034                    res?,
2035                )),
2036                res = lose => Ok(RoutingOutcome::answered(
2037                    self.loser.clone().into(),
2038                    outcome_request,
2039                    res?,
2040                )),
2041            }
2042        }
2043    }
2044
2045    /// Builds a hedging algo and the `serve` that drives it: the winner is gated behind the
2046    /// loser starting (so the loser's serve is guaranteed in flight when the winner wins),
2047    /// and the loser finishes after `loser_delay` — or never, when `None`.
2048    fn hedge(loser_delay: Option<std::time::Duration>) -> (Arc<dyn Algorithm>, impl Serve) {
2049        let started = Arc::new(tokio::sync::Notify::new());
2050        let algo = Arc::new(Hedge {
2051            winner: "winner".to_string(),
2052            loser: "loser".to_string(),
2053        });
2054        let serve = move |target: ModelId, _request: Request| {
2055            let started = started.clone();
2056            async move {
2057                if target == "loser" {
2058                    started.notify_one();
2059                    match loser_delay {
2060                        Some(delay) => tokio::time::sleep(delay).await,
2061                        None => std::future::pending::<()>().await,
2062                    }
2063                } else {
2064                    started.notified().await;
2065                }
2066                Ok(reply(target))
2067            }
2068        };
2069        (algo, serve)
2070    }
2071
2072    #[tokio::test]
2073    async fn run_returns_the_winner_without_a_late_loser_overwriting_it() -> Result<()> {
2074        // The loser responds 50ms after the winner has already won. `run` must return the
2075        // winner, not the loser's `respond`-to-a-dropped-receiver error.
2076        let (algo, serve) = hedge(Some(std::time::Duration::from_millis(50)));
2077        let (_, response) = test_drive(algo, request(), serve).await?;
2078        assert_eq!(
2079            response
2080                .llm_response
2081                .as_agg()
2082                .map(completion_text)
2083                .unwrap_or_default(),
2084            "winner"
2085        );
2086        Ok(())
2087    }
2088
2089    #[tokio::test]
2090    async fn run_returns_the_winner_without_hanging_on_a_pending_loser() -> Result<()> {
2091        // The loser never resolves. `run` must return the winner promptly, not hang
2092        // waiting for the in-flight loser.
2093        let (algo, serve) = hedge(None);
2094        let run = test_drive(algo, request(), serve);
2095        let (_, response) = tokio::time::timeout(std::time::Duration::from_secs(1), run)
2096            .await
2097            .map_err(|error| LibsyError::external("waiting for pending loser", error))??;
2098        assert_eq!(
2099            response
2100                .llm_response
2101                .as_agg()
2102                .map(completion_text)
2103                .unwrap_or_default(),
2104            "winner"
2105        );
2106        Ok(())
2107    }
2108
2109    #[tokio::test]
2110    async fn run_surfaces_a_terminal_error_with_many_calls_in_flight() -> Result<()> {
2111        use std::sync::atomic::{AtomicUsize, Ordering};
2112
2113        // A large fan-out (10 matched the old, now-removed concurrency cap). The terminal
2114        // error must still reach the caller with all of these calls pending.
2115        const N: usize = 10;
2116
2117        // Fans out N calls, then errors as soon as all N are in flight — exercising a
2118        // terminal failure emitted while the offloaded calls are still pending.
2119        struct FanOutThenError {
2120            all_started: Arc<tokio::sync::Notify>,
2121            n: usize,
2122        }
2123
2124        #[async_trait]
2125        impl Algorithm for FanOutThenError {
2126            fn name(&self) -> &str {
2127                "fan_out_then_error"
2128            }
2129
2130            async fn route(
2131                self: Arc<Self>,
2132                driver: Driver,
2133                request: Request,
2134            ) -> Result<RoutingOutcome> {
2135                let offloads = futures::future::join_all(
2136                    (0..self.n)
2137                        .map(|i| driver.call_model(request.clone(), vec![format!("m{i}").into()])),
2138                );
2139                tokio::select! {
2140                    _ = offloads => Err(test_error("offloads unexpectedly completed")),
2141                    _ = self.all_started.notified() => {
2142                        Err(test_error("terminal error while calls pending"))
2143                    }
2144                }
2145            }
2146        }
2147
2148        let all_started = Arc::new(tokio::sync::Notify::new());
2149        let algo: Arc<dyn Algorithm> = Arc::new(FanOutThenError {
2150            all_started: all_started.clone(),
2151            n: N,
2152        });
2153
2154        // Serving enters each call; once all N are in flight it signals, then pends forever.
2155        let started = Arc::new(AtomicUsize::new(0));
2156        let serve = move |_target: ModelId, _request: Request| {
2157            let started = started.clone();
2158            let all_started = all_started.clone();
2159            async move {
2160                if started.fetch_add(1, Ordering::SeqCst) + 1 == N {
2161                    all_started.notify_one();
2162                }
2163                std::future::pending::<ServeResult>().await
2164            }
2165        };
2166
2167        // With the cap gone, the driver keeps polling the stream even with N calls in
2168        // flight, so the terminal error surfaces promptly instead of hanging.
2169        let run = test_drive(algo, request(), serve);
2170        let result = tokio::time::timeout(std::time::Duration::from_millis(500), run)
2171            .await
2172            .map_err(|error| {
2173                LibsyError::external("waiting for terminal error with full call cap", error)
2174            })?;
2175        match result {
2176            Ok(_) => Err(test_error("expected the terminal error, got a response")),
2177            Err(err) => {
2178                assert!(
2179                    err.to_string()
2180                        .contains("terminal error while calls pending")
2181                );
2182                Ok(())
2183            }
2184        }
2185    }
2186}