1#![allow(
3 clippy::missing_errors_doc,
4 clippy::missing_panics_doc,
5 clippy::too_many_lines
6)]
7
8use sha2::{Digest as _, Sha256};
9use std::collections::{BTreeMap, BTreeSet};
10
11pub const WORKSPACE_MANIFEST_V1_SCHEMA: &str = "presolve.workspace-manifest";
12pub const MAX_WORKSPACE_PACKAGES: usize = 256;
13pub const MAX_WORKSPACE_EDGES: usize = 4096;
14#[derive(Debug, Clone, PartialEq, Eq)]
15pub struct WorkspacePackageDescriptorV1 {
16 pub package_id: String,
17 pub session_id: String,
18 pub display_name: Option<String>,
19 pub configuration_identity_hint: Option<String>,
20 pub metadata: BTreeMap<String, String>,
21}
22#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
23pub struct WorkspaceDependencyEdgeV1 {
24 pub dependency_package_id: String,
25 pub dependent_package_id: String,
26}
27#[derive(Debug, Clone, PartialEq, Eq)]
28pub struct WorkspacePolicyV1 {
29 pub failure_mode: String,
30 pub execution_mode: String,
31 pub result_detail: String,
32}
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub struct WorkspaceManifestV1 {
35 pub schema: String,
36 pub version: u32,
37 pub workspace_id: String,
38 pub packages: Vec<WorkspacePackageDescriptorV1>,
39 pub dependencies: Vec<WorkspaceDependencyEdgeV1>,
40 pub policy: WorkspacePolicyV1,
41}
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub struct WorkspacePackageGraphV1 {
44 pub workspace_id: String,
45 pub manifest_identity: String,
46 pub packages: Vec<WorkspacePackageDescriptorV1>,
47 pub edges: Vec<WorkspaceDependencyEdgeV1>,
48 pub reverse_edges: Vec<WorkspaceDependencyEdgeV1>,
49 pub roots: Vec<String>,
50 pub leaves: Vec<String>,
51 pub topological_order: Vec<String>,
52 pub graph_identity: String,
53}
54#[derive(Debug, Clone, PartialEq, Eq)]
55pub struct WorkspaceBuildStageV1 {
56 pub stage_index: u32,
57 pub packages: Vec<String>,
58}
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct WorkspaceBuildPlanV1 {
61 pub manifest_identity: String,
62 pub graph_identity: String,
63 pub stages: Vec<WorkspaceBuildStageV1>,
64 pub request_fingerprints: Vec<(String, String)>,
65 pub plan_identity: String,
66}
67#[derive(Debug, Clone, PartialEq, Eq)]
68pub enum WorkspaceErrorV1 {
69 Cycle { members: Vec<String> },
70 Code(&'static str),
71}
72impl WorkspaceErrorV1 {
73 #[must_use]
74 pub const fn code(&self) -> &'static str {
75 match self {
76 Self::Cycle { .. } => "L7W001_WORKSPACE_DEPENDENCY_CYCLE",
77 Self::Code(code) => code,
78 }
79 }
80}
81fn norm(value: &str) -> Result<String, WorkspaceErrorV1> {
82 let value = value.trim();
83 if value.is_empty() || value.bytes().any(|b| b.is_ascii_control()) {
84 Err(WorkspaceErrorV1::Code(
85 "L7W012_INVALID_WORKSPACE_IDENTIFIER",
86 ))
87 } else {
88 Ok(value.into())
89 }
90}
91fn digest(value: impl AsRef<[u8]>) -> String {
92 format!("sha256:{:x}", Sha256::digest(value))
93}
94impl WorkspaceManifestV1 {
95 pub fn normalize_validate(&self) -> Result<Self, WorkspaceErrorV1> {
96 if self.schema != WORKSPACE_MANIFEST_V1_SCHEMA || self.version != 1 {
97 return Err(WorkspaceErrorV1::Code(
98 "L7W009_UNSUPPORTED_WORKSPACE_SCHEMA",
99 ));
100 }
101 if self.packages.len() > MAX_WORKSPACE_PACKAGES
102 || self.dependencies.len() > MAX_WORKSPACE_EDGES
103 {
104 return Err(WorkspaceErrorV1::Code(
105 "L7W012_INVALID_WORKSPACE_IDENTIFIER",
106 ));
107 }
108 if self.policy.failure_mode != "fail_fast"
109 || self.policy.execution_mode != "deterministic_serial"
110 || !matches!(self.policy.result_detail.as_str(), "summary" | "full")
111 {
112 return Err(WorkspaceErrorV1::Code("L7W010_INVALID_WORKSPACE_POLICY"));
113 }
114 let mut out = self.clone();
115 out.workspace_id = norm(&out.workspace_id)?;
116 for p in &mut out.packages {
117 p.package_id = norm(&p.package_id)?;
118 p.session_id = norm(&p.session_id)?;
119 if !p.metadata.is_empty() {
120 return Err(WorkspaceErrorV1::Code("L7W010_INVALID_WORKSPACE_POLICY"));
121 }
122 }
123 out.packages.sort_by(|a, b| a.package_id.cmp(&b.package_id));
124 if out
125 .packages
126 .windows(2)
127 .any(|p| p[0].package_id == p[1].package_id)
128 {
129 return Err(WorkspaceErrorV1::Code("L7W002_DUPLICATE_PACKAGE_ID"));
130 }
131 let sessions = out
132 .packages
133 .iter()
134 .map(|p| p.session_id.clone())
135 .collect::<BTreeSet<_>>();
136 if sessions.len() != out.packages.len() {
137 return Err(WorkspaceErrorV1::Code("L7W003_DUPLICATE_SESSION_ID"));
138 }
139 let ids = out
140 .packages
141 .iter()
142 .map(|p| p.package_id.clone())
143 .collect::<BTreeSet<_>>();
144 for e in &mut out.dependencies {
145 e.dependency_package_id = norm(&e.dependency_package_id)?;
146 e.dependent_package_id = norm(&e.dependent_package_id)?;
147 if e.dependency_package_id == e.dependent_package_id {
148 return Err(WorkspaceErrorV1::Code("L7W005_SELF_DEPENDENCY"));
149 }
150 if !ids.contains(&e.dependency_package_id) || !ids.contains(&e.dependent_package_id) {
151 return Err(WorkspaceErrorV1::Code("L7W004_UNKNOWN_EDGE_PACKAGE"));
152 }
153 }
154 out.dependencies.sort();
155 if out.dependencies.windows(2).any(|e| e[0] == e[1]) {
156 return Err(WorkspaceErrorV1::Code("L7W006_DUPLICATE_DEPENDENCY_EDGE"));
157 }
158 Ok(out)
159 }
160 #[must_use]
161 pub fn identity(&self) -> String {
162 digest(self.canonical_json())
163 }
164 #[must_use]
165 pub fn canonical_json(&self) -> Vec<u8> {
166 let q = |s: &str| serde_json::to_string(s).expect("strings serialize");
167 let p = self
168 .packages
169 .iter()
170 .map(|x| format!("{}:{}", x.package_id, x.session_id))
171 .collect::<Vec<_>>()
172 .join(",");
173 let e = self
174 .dependencies
175 .iter()
176 .map(|x| format!("{}>{}", x.dependency_package_id, x.dependent_package_id))
177 .collect::<Vec<_>>()
178 .join(",");
179 format!("{{\"schema\":{},\"version\":1,\"workspace_id\":{},\"packages\":{},\"dependencies\":{},\"policy\":{}/{}/{}}}\n",q(&self.schema),q(&self.workspace_id),q(&p),q(&e),self.policy.failure_mode,self.policy.execution_mode,self.policy.result_detail).into_bytes()
180 }
181}
182pub fn graph(manifest: &WorkspaceManifestV1) -> Result<WorkspacePackageGraphV1, WorkspaceErrorV1> {
183 let m = manifest.normalize_validate()?;
184 let mut indegree = m
185 .packages
186 .iter()
187 .map(|p| (p.package_id.clone(), 0usize))
188 .collect::<BTreeMap<_, _>>();
189 let mut forward = BTreeMap::<String, Vec<String>>::new();
190 for e in &m.dependencies {
191 *indegree.get_mut(&e.dependent_package_id).expect("valid") += 1;
192 forward
193 .entry(e.dependency_package_id.clone())
194 .or_default()
195 .push(e.dependent_package_id.clone());
196 }
197 for v in forward.values_mut() {
198 v.sort();
199 }
200 let mut remaining = indegree.clone();
201 let mut order = Vec::new();
202 while !remaining.is_empty() {
203 let now = remaining
204 .iter()
205 .filter(|(_, n)| **n == 0)
206 .map(|(k, _)| k.clone())
207 .collect::<Vec<_>>();
208 if now.is_empty() {
209 return Err(WorkspaceErrorV1::Cycle {
210 members: remaining.into_keys().collect(),
211 });
212 }
213 for id in now {
214 remaining.remove(&id);
215 if let Some(next) = forward.get(&id) {
216 for n in next {
217 if let Some(v) = remaining.get_mut(n) {
218 *v -= 1;
219 }
220 }
221 }
222 order.push(id);
223 }
224 }
225 let roots = m
226 .packages
227 .iter()
228 .filter(|p| {
229 !m.dependencies
230 .iter()
231 .any(|e| e.dependent_package_id == p.package_id)
232 })
233 .map(|p| p.package_id.clone())
234 .collect();
235 let leaves = m
236 .packages
237 .iter()
238 .filter(|p| {
239 !m.dependencies
240 .iter()
241 .any(|e| e.dependency_package_id == p.package_id)
242 })
243 .map(|p| p.package_id.clone())
244 .collect();
245 let mut reverse = m
246 .dependencies
247 .iter()
248 .map(|e| WorkspaceDependencyEdgeV1 {
249 dependency_package_id: e.dependent_package_id.clone(),
250 dependent_package_id: e.dependency_package_id.clone(),
251 })
252 .collect::<Vec<_>>();
253 reverse.sort();
254 let manifest_identity = m.identity();
255 let id = digest(format!("{}|{:?}", manifest_identity, m.dependencies));
256 Ok(WorkspacePackageGraphV1 {
257 workspace_id: m.workspace_id,
258 manifest_identity,
259 packages: m.packages,
260 edges: m.dependencies,
261 reverse_edges: reverse,
262 roots,
263 leaves,
264 topological_order: order,
265 graph_identity: id,
266 })
267}
268#[must_use]
269pub fn plan(
270 g: &WorkspacePackageGraphV1,
271 mut requests: Vec<(String, String)>,
272) -> WorkspaceBuildPlanV1 {
273 requests.sort();
274 let mut indegree = g
275 .packages
276 .iter()
277 .map(|p| (p.package_id.clone(), 0usize))
278 .collect::<BTreeMap<_, _>>();
279 let mut forward = BTreeMap::<String, Vec<String>>::new();
280 for e in &g.edges {
281 *indegree.get_mut(&e.dependent_package_id).expect("graph") += 1;
282 forward
283 .entry(e.dependency_package_id.clone())
284 .or_default()
285 .push(e.dependent_package_id.clone());
286 }
287 for v in forward.values_mut() {
288 v.sort();
289 }
290 let mut stages = Vec::new();
291 let mut index = 0;
292 while !indegree.is_empty() {
293 let now = indegree
294 .iter()
295 .filter(|(_, n)| **n == 0)
296 .map(|(k, _)| k.clone())
297 .collect::<Vec<_>>();
298 for id in &now {
299 indegree.remove(id);
300 if let Some(next) = forward.get(id) {
301 for n in next {
302 if let Some(v) = indegree.get_mut(n) {
303 *v -= 1;
304 }
305 }
306 }
307 }
308 stages.push(WorkspaceBuildStageV1 {
309 stage_index: index,
310 packages: now,
311 });
312 index += 1;
313 }
314 let id = digest(format!(
315 "{}|{}|{:?}|{:?}",
316 g.manifest_identity, g.graph_identity, stages, requests
317 ));
318 WorkspaceBuildPlanV1 {
319 manifest_identity: g.manifest_identity.clone(),
320 graph_identity: g.graph_identity.clone(),
321 stages,
322 request_fingerprints: requests,
323 plan_identity: id,
324 }
325}
326
327#[cfg(test)]
328mod tests {
329 use super::*;
330 fn manifest(packages: Vec<&str>, edges: Vec<(&str, &str)>) -> WorkspaceManifestV1 {
331 WorkspaceManifestV1 {
332 schema: WORKSPACE_MANIFEST_V1_SCHEMA.into(),
333 version: 1,
334 workspace_id: "demo".into(),
335 packages: packages
336 .into_iter()
337 .map(|id| WorkspacePackageDescriptorV1 {
338 package_id: id.into(),
339 session_id: format!("session-{id}"),
340 display_name: None,
341 configuration_identity_hint: None,
342 metadata: BTreeMap::new(),
343 })
344 .collect(),
345 dependencies: edges
346 .into_iter()
347 .map(|(a, b)| WorkspaceDependencyEdgeV1 {
348 dependency_package_id: a.into(),
349 dependent_package_id: b.into(),
350 })
351 .collect(),
352 policy: WorkspacePolicyV1 {
353 failure_mode: "fail_fast".into(),
354 execution_mode: "deterministic_serial".into(),
355 result_detail: "full".into(),
356 },
357 }
358 }
359 #[test]
360 fn l7_chain_and_permutations_are_deterministic() {
361 let a = manifest(
362 vec!["app", "foundation", "feature"],
363 vec![("feature", "app"), ("foundation", "feature")],
364 );
365 let b = manifest(
366 vec!["feature", "app", "foundation"],
367 vec![("foundation", "feature"), ("feature", "app")],
368 );
369 let ga = graph(&a).unwrap();
370 let gb = graph(&b).unwrap();
371 assert_eq!(ga.graph_identity, gb.graph_identity);
372 let plan = super::plan(
373 &ga,
374 vec![
375 ("app".into(), "a".into()),
376 ("foundation".into(), "f".into()),
377 ("feature".into(), "x".into()),
378 ],
379 );
380 assert_eq!(plan.stages[0].packages, vec!["foundation"]);
381 assert_eq!(plan.stages[2].packages, vec!["app"]);
382 }
383 #[test]
384 fn l7_cycle_is_canonical() {
385 let error = graph(&manifest(vec!["a", "b"], vec![("a", "b"), ("b", "a")])).unwrap_err();
386 assert_eq!(error.code(), "L7W001_WORKSPACE_DEPENDENCY_CYCLE");
387 }
388}