1use super::{
2 CandidateIndex, CandidateMetadata, Incompatibility, RequirementPath, ResolutionRequest,
3};
4use crate::{ContentDigest, DependencyGroup, PackageAlias, ResolutionRequirement};
5use serde::{Deserialize, Serialize};
6use std::collections::{BTreeMap, BTreeSet};
7
8#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
9pub struct ResolutionPackage {
10 pub candidate: CandidateMetadata,
11 pub enabled_features: BTreeSet<String>,
12}
13
14#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
15pub struct ResolutionEdge {
16 #[serde(skip_serializing_if = "Option::is_none")]
17 pub from: Option<ContentDigest>,
18 pub alias: PackageAlias,
19 pub to: ContentDigest,
20 pub group: DependencyGroup,
21}
22
23#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
24pub struct Resolution {
25 pub packages: BTreeMap<ContentDigest, ResolutionPackage>,
26 pub edges: Vec<ResolutionEdge>,
27}
28
29#[derive(Debug, Clone, Default)]
30struct SolverState {
31 packages: BTreeMap<ContentDigest, ResolutionPackage>,
32 by_package: BTreeMap<crate::CanonicalPackageId, Vec<ContentDigest>>,
33 edges: BTreeSet<ResolutionEdge>,
34 paths: BTreeMap<ContentDigest, BTreeSet<RequirementPath>>,
35}
36
37pub fn resolve(
38 request: &ResolutionRequest,
39 candidates: &CandidateIndex,
40) -> Result<Resolution, Incompatibility> {
41 let mut state = SolverState::default();
42 let mut requirements = request.requirements.clone();
43 requirements.sort_by(|left, right| left.alias.cmp(&right.alias));
44 for requirement in requirements {
45 if !requirement_applies(&requirement, request) {
46 continue;
47 }
48 let path = RequirementPath {
49 root: request.root.clone(),
50 aliases: vec![requirement.alias.clone()],
51 };
52 resolve_requirement(
53 &mut state,
54 request,
55 candidates,
56 &requirement,
57 None,
58 path,
59 &mut Vec::new(),
60 )?;
61 }
62 Ok(Resolution {
63 packages: state.packages,
64 edges: state.edges.into_iter().collect(),
65 })
66}
67
68fn resolve_requirement(
69 state: &mut SolverState,
70 request: &ResolutionRequest,
71 index: &CandidateIndex,
72 requirement: &ResolutionRequirement,
73 from: Option<ContentDigest>,
74 path: RequirementPath,
75 active: &mut Vec<ContentDigest>,
76) -> Result<ContentDigest, Incompatibility> {
77 let requested_features = requested_features(requirement);
78 if let Some(existing) = state
79 .by_package
80 .get(&requirement.package)
81 .into_iter()
82 .flatten()
83 .filter_map(|identity| state.packages.get(identity))
84 .find(|package| candidate_matches(&package.candidate, requirement, request))
85 .map(|package| package.candidate.instance.identity_digest.clone())
86 {
87 add_edge(state, from, requirement, existing.clone(), &path)?;
88 state
89 .paths
90 .entry(existing.clone())
91 .or_default()
92 .insert(path.clone());
93 let changed = {
94 let package = state.packages.get_mut(&existing).expect("indexed package");
95 let before = package.enabled_features.len();
96 package
97 .enabled_features
98 .extend(requested_features.iter().cloned());
99 before != package.enabled_features.len()
100 };
101 if changed {
102 expand_candidate(state, request, index, &existing, path, active)?;
103 }
104 return Ok(existing);
105 }
106
107 let mut eligible = index
108 .candidates(&requirement.package)
109 .iter()
110 .filter(|candidate| candidate_matches(candidate, requirement, request))
111 .cloned()
112 .collect::<Vec<_>>();
113 let locked_for_package = index
114 .candidates(&requirement.package)
115 .iter()
116 .filter(|candidate| {
117 request
118 .locked_instances
119 .contains(&candidate.instance.identity_digest)
120 })
121 .map(|candidate| candidate.instance.identity_digest.clone())
122 .collect::<BTreeSet<_>>();
123 if request.update_packages.as_ref().is_some_and(|packages| {
124 !packages.contains(&requirement.package) && !locked_for_package.is_empty()
125 }) {
126 eligible
127 .retain(|candidate| locked_for_package.contains(&candidate.instance.identity_digest));
128 }
129 eligible.sort_by(|left, right| {
130 right
131 .instance
132 .version
133 .cmp(&left.instance.version)
134 .then_with(|| {
135 left.instance
136 .identity_digest
137 .cmp(&right.instance.identity_digest)
138 })
139 });
140 let mut last_conflict = None;
141 for candidate in eligible {
142 if let Some(mut paths) = singleton_conflict_paths(state, &candidate) {
143 paths.push(path.clone());
144 paths.sort();
145 paths.dedup();
146 last_conflict = Some(Incompatibility {
147 package: Box::new(requirement.package.clone()),
148 requirement: Box::new(requirement.version.clone()),
149 paths,
150 reason: "a singleton/native package would require multiple instances".to_string(),
151 });
152 continue;
153 }
154 let mut trial = state.clone();
155 let identity = candidate.instance.identity_digest.clone();
156 trial
157 .by_package
158 .entry(candidate.instance.package.clone())
159 .or_default()
160 .push(identity.clone());
161 trial.packages.insert(
162 identity.clone(),
163 ResolutionPackage {
164 candidate,
165 enabled_features: requested_features.clone(),
166 },
167 );
168 trial
169 .paths
170 .entry(identity.clone())
171 .or_default()
172 .insert(path.clone());
173 if let Err(error) = add_edge(
174 &mut trial,
175 from.clone(),
176 requirement,
177 identity.clone(),
178 &path,
179 )
180 .and_then(|_| expand_candidate(&mut trial, request, index, &identity, path.clone(), active))
181 {
182 last_conflict = Some(error);
183 continue;
184 }
185 *state = trial;
186 return Ok(identity);
187 }
188 Err(last_conflict.unwrap_or_else(|| {
189 conflict(
190 requirement,
191 path,
192 "no eligible candidate satisfies version, target, capability, RunMat, yank, and offline policy",
193 )
194 }))
195}
196
197fn expand_candidate(
198 state: &mut SolverState,
199 request: &ResolutionRequest,
200 index: &CandidateIndex,
201 identity: &ContentDigest,
202 path: RequirementPath,
203 active: &mut Vec<ContentDigest>,
204) -> Result<(), Incompatibility> {
205 if active.contains(identity) {
206 let package = &state.packages[identity].candidate.instance.package;
207 return Err(Incompatibility {
208 package: Box::new(package.clone()),
209 requirement: Box::new(semver::VersionReq::STAR),
210 paths: vec![path],
211 reason: "dependency cycle detected".to_string(),
212 });
213 }
214 active.push(identity.clone());
215 let package = state.packages[identity].clone();
216 let activation = feature_activation(&package, &path)?;
217 let mut dependencies = package.candidate.dependencies.clone();
218 dependencies.sort_by(|left, right| left.alias.cmp(&right.alias));
219 for mut dependency in dependencies {
220 if !requirement_applies(&dependency, request) {
221 continue;
222 }
223 if dependency.optional && !activation.contains_key(dependency.alias.as_str()) {
224 continue;
225 }
226 if let Some(features) = activation.get(dependency.alias.as_str()) {
227 dependency.features.extend(features.iter().cloned());
228 }
229 let mut child_path = path.clone();
230 child_path.aliases.push(dependency.alias.clone());
231 resolve_requirement(
232 state,
233 request,
234 index,
235 &dependency,
236 Some(identity.clone()),
237 child_path,
238 active,
239 )?;
240 }
241 active.pop();
242 Ok(())
243}
244
245fn feature_activation(
246 package: &ResolutionPackage,
247 path: &RequirementPath,
248) -> Result<BTreeMap<String, BTreeSet<String>>, Incompatibility> {
249 let aliases = package
250 .candidate
251 .dependencies
252 .iter()
253 .map(|dependency| dependency.alias.as_str())
254 .collect::<BTreeSet<_>>();
255 let mut activation = BTreeMap::<String, BTreeSet<String>>::new();
256 for feature in &package.enabled_features {
257 let Some(requests) = package.candidate.features.get(feature) else {
258 if feature == "default" {
259 continue;
260 }
261 return Err(Incompatibility {
262 package: Box::new(package.candidate.instance.package.clone()),
263 requirement: Box::new(semver::VersionReq::STAR),
264 paths: vec![path.clone()],
265 reason: format!("requested feature `{feature}` is not declared"),
266 });
267 };
268 for request in requests {
269 let (alias, dependency_feature) = request
270 .split_once('/')
271 .map_or((request.as_str(), None), |(alias, feature)| {
272 (alias, Some(feature))
273 });
274 if !aliases.contains(alias) {
275 return Err(Incompatibility {
276 package: Box::new(package.candidate.instance.package.clone()),
277 requirement: Box::new(semver::VersionReq::STAR),
278 paths: vec![path.clone()],
279 reason: format!(
280 "feature `{feature}` activates unknown dependency alias `{alias}`"
281 ),
282 });
283 }
284 let features = activation.entry(alias.to_string()).or_default();
285 if let Some(dependency_feature) = dependency_feature {
286 features.insert(dependency_feature.to_string());
287 }
288 }
289 }
290 Ok(activation)
291}
292
293fn requested_features(requirement: &ResolutionRequirement) -> BTreeSet<String> {
294 let mut features = requirement.features.clone();
295 if requirement.default_features {
296 features.insert("default".to_string());
297 }
298 features
299}
300
301fn requirement_applies(requirement: &ResolutionRequirement, request: &ResolutionRequest) -> bool {
302 request.groups.contains(&requirement.group)
303 && requirement
304 .target
305 .as_ref()
306 .is_none_or(|target| request.environment.supports(target))
307}
308
309fn candidate_matches(
310 candidate: &CandidateMetadata,
311 requirement: &ResolutionRequirement,
312 request: &ResolutionRequest,
313) -> bool {
314 let Some(version) = candidate.instance.version.as_ref() else {
315 return false;
316 };
317 requirement.version.matches(version.as_semver())
318 && (!candidate.yanked)
319 && (!request.offline || candidate.available_offline)
320 && candidate
321 .runmat_version
322 .as_ref()
323 .is_none_or(|required| required.matches(&request.runmat_version))
324 && candidate
325 .required_capabilities
326 .is_subset(&request.environment.capabilities)
327 && (candidate.target_artifacts.is_empty()
328 || candidate
329 .target_artifacts
330 .iter()
331 .any(|target| request.environment.supports(target)))
332}
333
334fn singleton_conflict_paths(
335 state: &SolverState,
336 candidate: &CandidateMetadata,
337) -> Option<Vec<RequirementPath>> {
338 let conflicting = state
339 .by_package
340 .get(&candidate.instance.package)
341 .into_iter()
342 .flatten()
343 .filter_map(|identity| state.packages.get(identity))
344 .any(|selected| selected.candidate.singleton || candidate.singleton);
345 conflicting.then(|| {
346 state
347 .by_package
348 .get(&candidate.instance.package)
349 .into_iter()
350 .flatten()
351 .flat_map(|identity| state.paths.get(identity).into_iter().flatten().cloned())
352 .collect()
353 })
354}
355
356fn add_edge(
357 state: &mut SolverState,
358 from: Option<ContentDigest>,
359 requirement: &ResolutionRequirement,
360 to: ContentDigest,
361 path: &RequirementPath,
362) -> Result<(), Incompatibility> {
363 if state
364 .edges
365 .iter()
366 .any(|edge| edge.from == from && edge.alias == requirement.alias && edge.to != to)
367 {
368 return Err(conflict(
369 requirement,
370 path.clone(),
371 "one package cannot bind the same edge-local alias to two instances",
372 ));
373 }
374 state.edges.insert(ResolutionEdge {
375 from,
376 alias: requirement.alias.clone(),
377 to,
378 group: requirement.group,
379 });
380 Ok(())
381}
382
383fn conflict(
384 requirement: &ResolutionRequirement,
385 path: RequirementPath,
386 reason: impl Into<String>,
387) -> Incompatibility {
388 Incompatibility {
389 package: Box::new(requirement.package.clone()),
390 requirement: Box::new(requirement.version.clone()),
391 paths: vec![path],
392 reason: reason.into(),
393 }
394}