a3s_code_core/capability/
readiness.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use super::{
4    CapabilityId, CapabilityProjectionError, CapabilitySet, CodeCatalogGeneration, Sha256Digest,
5    MAX_CAPABILITIES, MAX_CAPABILITY_DEPENDENCY_EDGES,
6};
7
8pub const CAPABILITY_READINESS_PLAN_SCHEMA: &str = "a3s.code.capability-readiness-plan.v1";
9pub const MAX_CAPABILITY_READINESS_WAVES: usize = MAX_CAPABILITIES;
10
11/// Deterministic dependency-first ordering for one immutable capability set.
12///
13/// The plan reads only descriptor-level surface edges already published in a
14/// [`CapabilitySet`]. It does not inspect package manifests, select versions,
15/// resolve A3S Use dependencies, or provide a service container.
16#[derive(Clone, Debug, Eq, PartialEq)]
17pub struct CapabilityReadinessPlan {
18    generation: CodeCatalogGeneration,
19    digest: Sha256Digest,
20    waves: Vec<Vec<CapabilityId>>,
21    activation_order: Vec<CapabilityId>,
22    edge_count: usize,
23    max_wave_width: usize,
24}
25
26impl CapabilityReadinessPlan {
27    /// Build the bounded, minimal readiness waves for one exact catalog.
28    ///
29    /// Kahn's algorithm is iterative so the configured maximum-depth chain
30    /// cannot consume the call stack. `BTreeMap` and `BTreeSet` make both wave
31    /// membership and the flattened activation order platform-independent.
32    pub fn from_set(set: &CapabilitySet) -> Result<Self, CapabilityProjectionError> {
33        if set.len() > MAX_CAPABILITIES {
34            return Err(CapabilityProjectionError::ReadinessBoundExceeded {
35                field: "capabilities",
36                max: MAX_CAPABILITIES,
37            });
38        }
39
40        let mut remaining_dependencies = BTreeMap::<CapabilityId, usize>::new();
41        let mut dependents = BTreeMap::<CapabilityId, Vec<CapabilityId>>::new();
42        for (id, descriptor) in set.iter() {
43            remaining_dependencies.insert(id.clone(), descriptor.dependencies().len());
44            dependents.insert(id.clone(), Vec::new());
45        }
46
47        let mut edge_count = 0_usize;
48        for (id, descriptor) in set.iter() {
49            for dependency in descriptor.dependencies() {
50                edge_count = edge_count.checked_add(1).ok_or(
51                    CapabilityProjectionError::ReadinessBoundExceeded {
52                        field: "dependency_edges",
53                        max: MAX_CAPABILITY_DEPENDENCY_EDGES,
54                    },
55                )?;
56                if edge_count > MAX_CAPABILITY_DEPENDENCY_EDGES {
57                    return Err(CapabilityProjectionError::ReadinessBoundExceeded {
58                        field: "dependency_edges",
59                        max: MAX_CAPABILITY_DEPENDENCY_EDGES,
60                    });
61                }
62                let Some(consumers) = dependents.get_mut(dependency) else {
63                    return Err(CapabilityProjectionError::ReadinessDependencyMissing {
64                        capability: id.to_string(),
65                        dependency: dependency.to_string(),
66                    });
67                };
68                consumers.push(id.clone());
69            }
70        }
71        for consumers in dependents.values_mut() {
72            consumers.sort();
73        }
74
75        let mut ready = remaining_dependencies
76            .iter()
77            .filter_map(|(id, count)| (*count == 0).then_some(id.clone()))
78            .collect::<BTreeSet<_>>();
79        let mut waves = Vec::new();
80        let mut activation_order = Vec::with_capacity(set.len());
81        let mut max_wave_width = 0_usize;
82
83        while !ready.is_empty() {
84            if waves.len() >= MAX_CAPABILITY_READINESS_WAVES {
85                return Err(CapabilityProjectionError::ReadinessBoundExceeded {
86                    field: "readiness_waves",
87                    max: MAX_CAPABILITY_READINESS_WAVES,
88                });
89            }
90            let wave = std::mem::take(&mut ready).into_iter().collect::<Vec<_>>();
91            max_wave_width = max_wave_width.max(wave.len());
92            let mut next = BTreeSet::new();
93
94            for id in &wave {
95                activation_order.push(id.clone());
96                let Some(consumers) = dependents.get(id) else {
97                    return Err(CapabilityProjectionError::ReadinessGraphInvariant {
98                        message: "a planned capability has no dependent index entry",
99                    });
100                };
101                for consumer in consumers {
102                    let Some(count) = remaining_dependencies.get_mut(consumer) else {
103                        return Err(CapabilityProjectionError::ReadinessGraphInvariant {
104                            message: "a dependent capability has no readiness counter",
105                        });
106                    };
107                    let Some(updated) = count.checked_sub(1) else {
108                        return Err(CapabilityProjectionError::ReadinessGraphInvariant {
109                            message: "a dependency edge was released more than once",
110                        });
111                    };
112                    *count = updated;
113                    if updated == 0 {
114                        next.insert(consumer.clone());
115                    }
116                }
117            }
118
119            waves.push(wave);
120            ready = next;
121        }
122
123        if activation_order.len() != set.len() {
124            let blocked_count = set.len() - activation_order.len();
125            let Some(first_blocked) = remaining_dependencies
126                .iter()
127                .find_map(|(id, count)| (*count > 0).then_some(id.to_string()))
128            else {
129                return Err(CapabilityProjectionError::ReadinessGraphInvariant {
130                    message: "readiness traversal stopped with unaccounted capabilities",
131                });
132            };
133            return Err(CapabilityProjectionError::DependencyCycle {
134                first_blocked,
135                blocked_count,
136            });
137        }
138
139        Ok(Self {
140            generation: set.generation(),
141            digest: set.digest().clone(),
142            waves,
143            activation_order,
144            edge_count,
145            max_wave_width,
146        })
147    }
148
149    pub const fn schema(&self) -> &'static str {
150        CAPABILITY_READINESS_PLAN_SCHEMA
151    }
152
153    pub const fn generation(&self) -> CodeCatalogGeneration {
154        self.generation
155    }
156
157    pub fn digest(&self) -> &Sha256Digest {
158        &self.digest
159    }
160
161    pub fn capability_count(&self) -> usize {
162        self.activation_order.len()
163    }
164
165    pub fn is_empty(&self) -> bool {
166        self.activation_order.is_empty()
167    }
168
169    pub const fn edge_count(&self) -> usize {
170        self.edge_count
171    }
172
173    pub fn depth(&self) -> usize {
174        self.waves.len()
175    }
176
177    pub const fn max_wave_width(&self) -> usize {
178        self.max_wave_width
179    }
180
181    pub fn waves(&self) -> &[Vec<CapabilityId>] {
182        &self.waves
183    }
184
185    pub fn activation_order(&self) -> &[CapabilityId] {
186        &self.activation_order
187    }
188
189    pub(super) fn matches(&self, set: &CapabilitySet) -> bool {
190        self.generation == set.generation() && self.digest == *set.digest()
191    }
192}
a3s_code_core/capability/readiness.rs

a3s_code_core/capability/
readiness.rs
