nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
15 kB
411 lines
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: 2025 The Gleam contributors
3
4use crate::error::wrap;
5use ecow::EcoString;
6use hexpm::version::Version;
7use im::HashSet;
8use itertools::Itertools;
9use petgraph::Direction;
10use petgraph::algo::all_simple_paths;
11use petgraph::graph::NodeIndex;
12use petgraph::prelude::StableGraph;
13use pubgrub::External;
14use pubgrub::{DerivationTree, Derived, Ranges};
15use std::collections::HashMap;
16use std::hash::RandomState;
17use std::ops::Bound::{Excluded, Included, Unbounded};
18use std::sync::Arc;
19
20macro_rules! wrap_format {
21 ($($tts:tt)*) => {
22 wrap(&format!($($tts)*))
23 }
24}
25
26/// Makes a best effort at turning a derivation tree into a nice readable error
27/// message.
28///
29pub struct DerivationTreePrinter {
30 derivation_tree: DerivationTree<String, Ranges<Version>, String>,
31
32 /// The name of the root package for which we're trying to add new
33 /// dependencies. This is the starting point we use to find and report
34 /// dependency conflicts!
35 root_package_name: EcoString,
36
37 /// The graph of dependencies built from the derivation tree. The nodes are
38 /// packages and the arcs connecting them represent a dependency:
39 ///
40 /// ```txt
41 /// wibble ---- (range1, range2) ---> wobble
42 /// ```
43 ///
44 /// Means "package wibble with version `range1` requires package wobble
45 /// with version `range2`".
46 ///
47 dependencies: StableGraph<String, (Ranges<Version>, Ranges<Version>)>,
48
49 /// A map going from package name to its index in the dependencies graph.
50 ///
51 nodes: HashMap<String, NodeIndex>,
52}
53
54impl DerivationTreePrinter {
55 pub fn new(
56 root_package_name: EcoString,
57 mut derivation_tree: DerivationTree<String, Ranges<Version>, String>,
58 ) -> Self {
59 // We start by trying to simplify the derivation tree as much as
60 // possible.
61 derivation_tree.collapse_no_versions();
62 simplify_derivation_tree(&mut derivation_tree);
63
64 let mut dependencies = StableGraph::new();
65 let mut nodes = HashMap::new();
66 build_dependencies_graph(&derivation_tree, &mut dependencies, &mut nodes);
67
68 DerivationTreePrinter {
69 root_package_name,
70 derivation_tree,
71 dependencies,
72 nodes,
73 }
74 }
75
76 pub fn print(&self) -> String {
77 self.explanation_for_missing_version()
78 .or_else(|| self.explanation_for_complex_failure())
79 .unwrap_or_else(|| self.fallback_explanation())
80 }
81
82 /// This catches the case in which we try adding a dependency's version that
83 /// doesn't exist. That produces a very simple decision tree with just two
84 /// nodes and can have an ad hoc explanation, telling the user the version
85 /// they tried adding doesn't exist!
86 ///
87 fn explanation_for_missing_version(&self) -> Option<String> {
88 if let DerivationTree::External(External::FromDependencyOf(
89 base,
90 _,
91 package,
92 package_ranges,
93 )) = &self.derivation_tree
94 && *base == self.root_package_name
95 {
96 let pretty_range = pretty_range(package_ranges);
97 let message = if is_single_version(package_ranges) {
98 format!("The package `{package}` doesn't have a version {pretty_range}.")
99 } else {
100 format!("The package `{package}` has no versions in the range {pretty_range}.",)
101 };
102 Some(message)
103 } else {
104 None
105 }
106 }
107
108 /// Tries and print a pretty explanation for the given resolution tree.
109 /// If for some reason our heuristic to produce a nice error message fails
110 /// we return `None` so we can still produce a good enough error message!
111 ///
112 fn explanation_for_complex_failure(&self) -> Option<String> {
113 let root_package_index = self.nodes.get(self.root_package_name.as_str())?;
114 let unresolvable_nodes = self.find_unresolvable_nodes();
115 if unresolvable_nodes.is_empty() {
116 return None;
117 }
118
119 let mut unresolvable = vec![];
120 for unresolvable_node in unresolvable_nodes {
121 let paths = all_simple_paths::<Vec<_>, _, RandomState>(
122 &self.dependencies,
123 *root_package_index,
124 unresolvable_node,
125 0,
126 None,
127 );
128
129 let package = self
130 .dependencies
131 .node_weight(unresolvable_node)
132 .expect("package is in the graph");
133
134 let heading = format!("There's no compatible version of `{package}`:");
135 let explanation = paths.sorted().map(|path| self.pretty_path(path)).join("\n");
136 unresolvable.push(format!("{heading}\n{explanation}"));
137 }
138 Some(unresolvable.join("\n\n"))
139 }
140
141 fn pretty_path(&self, path: Vec<NodeIndex>) -> String {
142 let (you, dependee, rest) = match path.as_slice() {
143 [you, dependee, rest @ ..] => (you, dependee, rest),
144 _ => panic!("path with less than two nodes"),
145 };
146
147 let dependee_name = self
148 .dependencies
149 .node_weight(*dependee)
150 .expect("path node is in the graph");
151 let (_, dependee_range) = self
152 .ranges_between(you, dependee)
153 .expect("path edge is in the graph");
154
155 let mut message = format!(
156 " - You require {dependee_name} {}",
157 pretty_range(dependee_range)
158 );
159
160 let mut previous = dependee;
161 for next in rest {
162 let previous_name = self
163 .dependencies
164 .node_weight(*previous)
165 .expect("path node is in the graph");
166 let next_name = self
167 .dependencies
168 .node_weight(*next)
169 .expect("path node is in the graph");
170 let (_, next_range) = self
171 .ranges_between(previous, next)
172 .expect("path edge is in the graph");
173
174 message.push_str("\n - ");
175 message.push_str(previous_name);
176 message.push_str(" requires ");
177 message.push_str(next_name);
178 message.push(' ');
179 message.push_str(&pretty_range(next_range));
180
181 previous = next;
182 }
183 message
184 }
185
186 fn find_unresolvable_nodes(&self) -> Vec<NodeIndex> {
187 self.dependencies
188 .node_indices()
189 .filter(|node_index| {
190 self.dependencies
191 .neighbors_directed(*node_index, Direction::Incoming)
192 .count()
193 > 1
194 })
195 .sorted()
196 .collect_vec()
197 }
198
199 fn ranges_between(
200 &self,
201 one: &NodeIndex,
202 other: &NodeIndex,
203 ) -> Option<(&Ranges<Version>, &Ranges<Version>)> {
204 let edge = self.dependencies.find_edge(*one, *other)?;
205 self.dependencies
206 .edge_weight(edge)
207 .map(|(one, other)| (one, other))
208 }
209
210 /// A good enough explanation in case we're not able to produce anything
211 /// nicer.
212 fn fallback_explanation(&self) -> String {
213 let mut conflicting_packages = HashSet::new();
214 collect_conflicting_packages(&self.derivation_tree, &mut conflicting_packages);
215
216 wrap_format!(
217 "Unable to find compatible versions for \
218the version constraints in your gleam.toml. \
219The conflicting packages are:
220
221{}
222",
223 conflicting_packages
224 .into_iter()
225 .map(|s| format!("- {s}"))
226 .join("\n")
227 )
228 }
229}
230
231fn build_dependencies_graph(
232 derivation_tree: &DerivationTree<String, Ranges<Version>, String>,
233 graph: &mut StableGraph<String, (Ranges<Version>, Ranges<Version>)>,
234 nodes: &mut HashMap<String, NodeIndex<u32>>,
235) {
236 match derivation_tree {
237 DerivationTree::External(External::FromDependencyOf(
238 one,
239 range_one,
240 other,
241 range_other,
242 )) => {
243 let one_index = match nodes.get(one) {
244 Some(index) => *index,
245 None => {
246 let index = graph.add_node(one.clone());
247 let _ = nodes.insert(one.clone(), index);
248 index
249 }
250 };
251
252 let other_index = match nodes.get(other) {
253 Some(index) => *index,
254 None => {
255 let index = graph.add_node(other.clone());
256 let _ = nodes.insert(other.clone(), index);
257 index
258 }
259 };
260
261 let edges = graph.edges_connecting(one_index, other_index);
262 let edge_weight = match edges.peekable().peek() {
263 Some(edge) => {
264 let (old_range_one, old_range_other) = edge.weight();
265 (
266 range_one.union(old_range_one),
267 range_other.union(old_range_other),
268 )
269 }
270 None => (range_one.clone(), range_other.clone()),
271 };
272
273 let _ = graph.update_edge(one_index, other_index, edge_weight);
274 }
275 DerivationTree::External(_) => (),
276 DerivationTree::Derived(Derived { cause1, cause2, .. }) => {
277 build_dependencies_graph(cause1, graph, nodes);
278 build_dependencies_graph(cause2, graph, nodes);
279 }
280 }
281}
282
283/// This function collapses adjacent levels of a derivation tree that are all
284/// relative to the same dependency.
285///
286/// By default a derivation tree might have many nodes for a specific package,
287/// each node referring to a specific version range. For example:
288///
289/// - package_wibble `>= 1.0.0 and < 1.1.0` requires package_wobble `>= 1.1.0`
290/// - package_wibble `>= 1.1.0 and < 1.2.0` requires package_wobble `>= 1.2.0`
291/// - package_wibble `1.1.0` requires package_wobble `>= 1.1.0`
292///
293/// This level of fine-grained detail would be quite overwhelming in the vast
294/// majority of cases so we're fine with collapsing all these details into a
295/// single node taking the union of all the ranges that are there:
296///
297/// - package_wibble `>= 1.0.0 and < 1.2.0` requires package_wobble `>= 1.1.0`
298///
299/// This way we can print an error message that is way more concise and still
300/// informative about what went wrong, at the cost of
301///
302fn simplify_derivation_tree(derivation_tree: &mut DerivationTree<String, Ranges<Version>, String>) {
303 match derivation_tree {
304 DerivationTree::External(_) => {}
305 DerivationTree::Derived(derived) => {
306 simplify_derivation_tree(Arc::make_mut(&mut derived.cause1));
307 simplify_derivation_tree(Arc::make_mut(&mut derived.cause2));
308 simplify_derivation_tree_outer(derivation_tree);
309 }
310 }
311}
312
313fn simplify_derivation_tree_outer(
314 derivation_tree: &mut DerivationTree<String, Ranges<Version>, String>,
315) {
316 match derivation_tree {
317 DerivationTree::External(_) => {}
318 DerivationTree::Derived(derived) => {
319 match (
320 Arc::make_mut(&mut derived.cause1),
321 Arc::make_mut(&mut derived.cause2),
322 ) {
323 (
324 DerivationTree::External(External::FromDependencyOf(
325 package,
326 package_range,
327 required_package,
328 required_package_range,
329 )),
330 DerivationTree::External(External::FromDependencyOf(
331 maybe_package,
332 other_package_range,
333 maybe_required_package,
334 other_required_package_range,
335 )),
336 ) if package == maybe_package && required_package == maybe_required_package => {
337 *derivation_tree = DerivationTree::External(External::FromDependencyOf(
338 package.clone(),
339 package_range.union(other_package_range),
340 required_package.clone(),
341 required_package_range.union(other_required_package_range),
342 ));
343 }
344
345 _ => {}
346 }
347 }
348 }
349}
350
351fn collect_conflicting_packages<'dt>(
352 derivation_tree: &'dt DerivationTree<String, Ranges<Version>, String>,
353 conflicting_packages: &mut HashSet<&'dt String>,
354) {
355 match derivation_tree {
356 DerivationTree::External(external) => match external {
357 External::NotRoot(package, _)
358 | External::NoVersions(package, _)
359 | External::Custom(package, _, _) => {
360 let _ = conflicting_packages.insert(package);
361 }
362 External::FromDependencyOf(package, _, dep_package, _) => {
363 let _ = conflicting_packages.insert(package);
364 let _ = conflicting_packages.insert(dep_package);
365 }
366 },
367 DerivationTree::Derived(derived) => {
368 collect_conflicting_packages(&derived.cause1, conflicting_packages);
369 collect_conflicting_packages(&derived.cause2, conflicting_packages);
370 }
371 }
372}
373
374fn pretty_range(range: &Ranges<Version>) -> String {
375 range
376 .iter()
377 .map(|(lower, upper)| match (lower, upper) {
378 (Included(lower), Included(upper)) if lower == upper => format!("{lower}"),
379 (Included(lower), Included(upper)) => format!(">= {lower} and <= {upper}"),
380 (Included(lower), Excluded(upper)) => format!(">= {lower} and < {upper}"),
381 (Excluded(lower), Included(upper)) => format!("> {lower} and <= {upper}"),
382 (Excluded(lower), Excluded(upper)) => format!("> {lower} and < {upper}"),
383
384 (Included(version), Unbounded) => format!(">= {version}"),
385 (Excluded(version), Unbounded) => format!("> {version}"),
386 (Unbounded, Included(version)) => format!("<= {version}"),
387 (Unbounded, Excluded(version)) => format!("< {version}"),
388
389 (Unbounded, Unbounded) => "".into(),
390 })
391 .join(" or ")
392}
393
394fn is_single_version(range: &Ranges<Version>) -> bool {
395 // Note: at the time of writing this, `Ranges` has a method called
396 // `as_singleton` which, according to its doc, should do the same thing.
397 // However, it strangely seems to consider as a single version ranges like
398 // this one `> 11.0.0 and <= 12.0.0`. To me this doesn't read as a single
399 // version!
400
401 // The range needs to have exactly one segment that includes exactly one
402 // version number.
403 let mut segments = range.iter();
404 if let Some((Included(lower), Included(upper))) = segments.next()
405 && segments.next().is_none()
406 {
407 lower == upper
408 } else {
409 false
410 }
411}