starweaver_runtime/capability/
ordering.rs

1//! Capability ordering resolution.
2
3use std::{
4    collections::{BTreeMap, BTreeSet},
5    sync::Arc,
6};
7
8use thiserror::Error;
9
10use super::{AgentCapability, CapabilityId};
11
12/// Capability ordering diagnostics.
13#[derive(Debug, Error)]
14pub enum CapabilityOrderError {
15    /// Capability ids must be unique inside one run graph.
16    #[error("capability id '{0}' is duplicated")]
17    DuplicateId(String),
18    /// Ordering constraint referenced a missing capability id.
19    #[error("capability '{capability}' references missing dependency '{dependency}'")]
20    MissingDependency {
21        /// Capability that declared the dependency.
22        capability: String,
23        /// Missing dependency id.
24        dependency: String,
25    },
26    /// Ordering constraints contain a cycle.
27    #[error("capability ordering cycle detected among {0}")]
28    Cycle(String),
29}
30
31/// Resolve capability order from stable specs.
32///
33/// # Errors
34///
35/// Returns duplicate-id, missing-dependency, or cycle diagnostics.
36pub fn resolve_capability_order(
37    capabilities: &[Arc<dyn AgentCapability>],
38) -> Result<Vec<Arc<dyn AgentCapability>>, CapabilityOrderError> {
39    let mut ids = Vec::with_capacity(capabilities.len());
40    let mut by_id = BTreeMap::new();
41    for (index, capability) in capabilities.iter().enumerate() {
42        let id = capability.spec().id;
43        if by_id.insert(id.clone(), index).is_some() {
44            return Err(CapabilityOrderError::DuplicateId(id.as_str().to_string()));
45        }
46        ids.push(id);
47    }
48
49    let mut outgoing = BTreeMap::<CapabilityId, BTreeSet<CapabilityId>>::new();
50    let mut incoming = BTreeMap::<CapabilityId, usize>::new();
51    for id in &ids {
52        outgoing.entry(id.clone()).or_default();
53        incoming.entry(id.clone()).or_default();
54    }
55
56    for (index, capability) in capabilities.iter().enumerate() {
57        let spec = capability.spec();
58        let current = ids[index].clone();
59        for dependency in spec.ordering.after {
60            if !by_id.contains_key(&dependency) {
61                return Err(CapabilityOrderError::MissingDependency {
62                    capability: current.as_str().to_string(),
63                    dependency: dependency.as_str().to_string(),
64                });
65            }
66            if outgoing
67                .entry(dependency.clone())
68                .or_default()
69                .insert(current.clone())
70            {
71                *incoming.entry(current.clone()).or_default() += 1;
72            }
73        }
74        for target in spec.ordering.before {
75            if !by_id.contains_key(&target) {
76                return Err(CapabilityOrderError::MissingDependency {
77                    capability: current.as_str().to_string(),
78                    dependency: target.as_str().to_string(),
79                });
80            }
81            if outgoing
82                .entry(current.clone())
83                .or_default()
84                .insert(target.clone())
85            {
86                *incoming.entry(target).or_default() += 1;
87            }
88        }
89    }
90
91    let mut emitted = BTreeSet::<CapabilityId>::new();
92    let mut ordered = Vec::with_capacity(capabilities.len());
93    while ordered.len() < capabilities.len() {
94        let Some(next) = ids
95            .iter()
96            .find(|id| !emitted.contains(*id) && incoming.get(*id).copied().unwrap_or(0) == 0)
97            .cloned()
98        else {
99            let cycle = ids
100                .iter()
101                .filter(|id| !emitted.contains(*id))
102                .map(|id| id.as_str().to_string())
103                .collect::<Vec<_>>()
104                .join(",");
105            return Err(CapabilityOrderError::Cycle(cycle));
106        };
107        emitted.insert(next.clone());
108        let index = by_id[&next];
109        ordered.push(capabilities[index].clone());
110        if let Some(targets) = outgoing.get(&next) {
111            for target in targets {
112                if let Some(count) = incoming.get_mut(target) {
113                    *count = count.saturating_sub(1);
114                }
115            }
116        }
117    }
118    Ok(ordered)
119}
starweaver_runtime/capability/ordering.rs

starweaver_runtime/capability/
ordering.rs
