1use super::{DependencyPath, GraphEdge, GraphPackage, PackageGraph};
2use crate::{
3 CanonicalPackageId, ContentDigest, DependencyGroup, GraphError, HostCapability,
4 NormalizedRelativePath, PackageAlias, PackageInstanceId, PackageVersion, PathSourceId,
5 SourceId, TargetPredicate,
6};
7use std::collections::{BTreeMap, BTreeSet};
8
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub struct PathPackageInput {
11 pub package: CanonicalPackageId,
12 pub local_name: String,
13 pub workspace_path: NormalizedRelativePath,
14 pub manifest_digest: ContentDigest,
15 pub tree_digest: ContentDigest,
16 pub version: Option<PackageVersion>,
17 pub dependencies: BTreeMap<PackageAlias, String>,
18 pub required_capabilities: BTreeSet<HostCapability>,
19 pub singleton: bool,
20}
21
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub struct PathGraphInput {
24 pub root: String,
25 pub packages: BTreeMap<String, PathPackageInput>,
26 pub host_capabilities: BTreeSet<HostCapability>,
27}
28
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct ResolvedDependencyInput {
31 pub alias: PackageAlias,
32 pub target: String,
33 pub group: DependencyGroup,
34 pub optional: bool,
35 pub target_predicate: Option<TargetPredicate>,
36}
37
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct ResolvedPackageInput {
40 pub instance: PackageInstanceId,
41 pub local_name: String,
42 pub dependencies: Vec<ResolvedDependencyInput>,
43 pub required_capabilities: BTreeSet<HostCapability>,
44 pub singleton: bool,
45}
46
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub struct ResolvedGraphInput {
49 pub root: String,
50 pub packages: BTreeMap<String, ResolvedPackageInput>,
51 pub host_capabilities: BTreeSet<HostCapability>,
52}
53
54pub fn build_path_graph(input: PathGraphInput) -> Result<PackageGraph, GraphError> {
55 if !input.packages.contains_key(&input.root) {
56 return Err(GraphError::Invalid(format!(
57 "root package key `{}` does not exist",
58 input.root
59 )));
60 }
61 let mut resolved = BTreeMap::new();
62 for (key, package) in &input.packages {
63 let instance = PackageInstanceId::new(
64 package.package.clone(),
65 SourceId::Path(PathSourceId {
66 workspace_path: package.workspace_path.clone(),
67 manifest_digest: package.manifest_digest.clone(),
68 tree_digest: package.tree_digest.clone(),
69 }),
70 package.version.clone(),
71 package.tree_digest.clone(),
72 );
73 resolved.insert(
74 key.clone(),
75 ResolvedPackageInput {
76 instance,
77 local_name: package.local_name.clone(),
78 dependencies: package
79 .dependencies
80 .iter()
81 .map(|(alias, target)| ResolvedDependencyInput {
82 alias: alias.clone(),
83 target: target.clone(),
84 group: DependencyGroup::Runtime,
85 optional: false,
86 target_predicate: None,
87 })
88 .collect(),
89 required_capabilities: package.required_capabilities.clone(),
90 singleton: package.singleton,
91 },
92 );
93 }
94 build_resolved_graph(ResolvedGraphInput {
95 root: input.root,
96 packages: resolved,
97 host_capabilities: input.host_capabilities,
98 })
99}
100
101pub fn build_resolved_graph(input: ResolvedGraphInput) -> Result<PackageGraph, GraphError> {
102 if !input.packages.contains_key(&input.root) {
103 return Err(GraphError::Invalid(format!(
104 "root package key `{}` does not exist",
105 input.root
106 )));
107 }
108 let mut packages = BTreeMap::new();
109 let mut instances_by_key = BTreeMap::new();
110 for (key, package) in &input.packages {
111 let missing = package
112 .required_capabilities
113 .difference(&input.host_capabilities)
114 .copied()
115 .collect::<Vec<_>>();
116 if !missing.is_empty() {
117 let path = resolved_dependency_path(&input, key);
118 return Err(GraphError::UnavailableCapabilities {
119 dependency_path: path.to_string(),
120 capabilities: missing
121 .iter()
122 .map(ToString::to_string)
123 .collect::<Vec<_>>()
124 .join(", "),
125 });
126 }
127 instances_by_key.insert(key.clone(), package.instance.identity_digest.clone());
128 if packages
129 .insert(
130 package.instance.identity_digest.clone(),
131 GraphPackage {
132 instance: package.instance.clone(),
133 local_name: package.local_name.clone(),
134 required_capabilities: package.required_capabilities.clone(),
135 singleton: package.singleton,
136 },
137 )
138 .is_some()
139 {
140 return Err(GraphError::Invalid(format!(
141 "package key `{key}` resolves to a duplicate instance"
142 )));
143 }
144 }
145 validate_singletons(&packages)?;
146 let mut edges = Vec::new();
147 for (key, package) in &input.packages {
148 let from = instances_by_key[key].clone();
149 for dependency in &package.dependencies {
150 let Some(to) = instances_by_key.get(&dependency.target) else {
151 return Err(GraphError::Invalid(format!(
152 "dependency `{}` of `{key}` references missing package key `{}`",
153 dependency.alias, dependency.target
154 )));
155 };
156 edges.push(GraphEdge {
157 from: from.clone(),
158 alias: dependency.alias.clone(),
159 to: to.clone(),
160 group: dependency.group,
161 optional: dependency.optional,
162 target: dependency.target_predicate.clone(),
163 });
164 }
165 }
166 PackageGraph::finish(instances_by_key[&input.root].clone(), packages, edges)
167}
168
169fn resolved_dependency_path(input: &ResolvedGraphInput, target: &str) -> DependencyPath {
170 if target == input.root {
171 return DependencyPath {
172 root: input.root.clone(),
173 aliases: Vec::new(),
174 };
175 }
176 let mut queue = vec![(input.root.clone(), Vec::new())];
177 let mut visited = BTreeSet::new();
178 while let Some((key, path)) = queue.pop() {
179 if !visited.insert(key.clone()) {
180 continue;
181 }
182 if let Some(package) = input.packages.get(&key) {
183 for dependency in &package.dependencies {
184 let mut next = path.clone();
185 next.push(dependency.alias.clone());
186 if dependency.target == target {
187 return DependencyPath {
188 root: input.root.clone(),
189 aliases: next,
190 };
191 }
192 queue.push((dependency.target.clone(), next));
193 }
194 }
195 }
196 DependencyPath {
197 root: input.root.clone(),
198 aliases: Vec::new(),
199 }
200}
201
202fn validate_singletons(packages: &BTreeMap<ContentDigest, GraphPackage>) -> Result<(), GraphError> {
203 let mut counts = BTreeMap::new();
204 let mut singletons = BTreeSet::new();
205 for package in packages.values() {
206 *counts.entry(package.instance.package.clone()).or_insert(0) += 1;
207 if package.singleton {
208 singletons.insert(package.instance.package.clone());
209 }
210 }
211 for singleton in singletons {
212 if counts[&singleton] > 1 {
213 return Err(GraphError::Invalid(format!(
214 "singleton package {singleton} resolves to multiple instances"
215 )));
216 }
217 }
218 Ok(())
219}