nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
15 kB
408 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(&format!(
175 "\n - {previous_name} requires {next_name} {}",
176 pretty_range(next_range)
177 ));
178 previous = next;
179 }
180 message
181 }
182
183 fn find_unresolvable_nodes(&self) -> Vec<NodeIndex> {
184 self.dependencies
185 .node_indices()
186 .filter(|node_index| {
187 self.dependencies
188 .neighbors_directed(*node_index, Direction::Incoming)
189 .count()
190 > 1
191 })
192 .sorted()
193 .collect_vec()
194 }
195
196 fn ranges_between(
197 &self,
198 one: &NodeIndex,
199 other: &NodeIndex,
200 ) -> Option<(&Ranges<Version>, &Ranges<Version>)> {
201 let edge = self.dependencies.find_edge(*one, *other)?;
202 self.dependencies
203 .edge_weight(edge)
204 .map(|(one, other)| (one, other))
205 }
206
207 /// A good enough explanation in case we're not able to produce anything
208 /// nicer.
209 fn fallback_explanation(&self) -> String {
210 let mut conflicting_packages = HashSet::new();
211 collect_conflicting_packages(&self.derivation_tree, &mut conflicting_packages);
212
213 wrap_format!(
214 "Unable to find compatible versions for \
215the version constraints in your gleam.toml. \
216The conflicting packages are:
217
218{}
219",
220 conflicting_packages
221 .into_iter()
222 .map(|s| format!("- {s}"))
223 .join("\n")
224 )
225 }
226}
227
228fn build_dependencies_graph(
229 derivation_tree: &DerivationTree<String, Ranges<Version>, String>,
230 graph: &mut StableGraph<String, (Ranges<Version>, Ranges<Version>)>,
231 nodes: &mut HashMap<String, NodeIndex<u32>>,
232) {
233 match derivation_tree {
234 DerivationTree::External(External::FromDependencyOf(
235 one,
236 range_one,
237 other,
238 range_other,
239 )) => {
240 let one_index = match nodes.get(one) {
241 Some(index) => *index,
242 None => {
243 let index = graph.add_node(one.clone());
244 let _ = nodes.insert(one.clone(), index);
245 index
246 }
247 };
248
249 let other_index = match nodes.get(other) {
250 Some(index) => *index,
251 None => {
252 let index = graph.add_node(other.clone());
253 let _ = nodes.insert(other.clone(), index);
254 index
255 }
256 };
257
258 let edges = graph.edges_connecting(one_index, other_index);
259 let edge_weight = match edges.peekable().peek() {
260 Some(edge) => {
261 let (old_range_one, old_range_other) = edge.weight();
262 (
263 range_one.union(old_range_one),
264 range_other.union(old_range_other),
265 )
266 }
267 None => (range_one.clone(), range_other.clone()),
268 };
269
270 let _ = graph.update_edge(one_index, other_index, edge_weight);
271 }
272 DerivationTree::External(_) => (),
273 DerivationTree::Derived(Derived { cause1, cause2, .. }) => {
274 build_dependencies_graph(cause1, graph, nodes);
275 build_dependencies_graph(cause2, graph, nodes);
276 }
277 }
278}
279
280/// This function collapses adjacent levels of a derivation tree that are all
281/// relative to the same dependency.
282///
283/// By default a derivation tree might have many nodes for a specific package,
284/// each node referring to a specific version range. For example:
285///
286/// - package_wibble `>= 1.0.0 and < 1.1.0` requires package_wobble `>= 1.1.0`
287/// - package_wibble `>= 1.1.0 and < 1.2.0` requires package_wobble `>= 1.2.0`
288/// - package_wibble `1.1.0` requires package_wobble `>= 1.1.0`
289///
290/// This level of fine-grained detail would be quite overwhelming in the vast
291/// majority of cases so we're fine with collapsing all these details into a
292/// single node taking the union of all the ranges that are there:
293///
294/// - package_wibble `>= 1.0.0 and < 1.2.0` requires package_wobble `>= 1.1.0`
295///
296/// This way we can print an error message that is way more concise and still
297/// informative about what went wrong, at the cost of
298///
299fn simplify_derivation_tree(derivation_tree: &mut DerivationTree<String, Ranges<Version>, String>) {
300 match derivation_tree {
301 DerivationTree::External(_) => {}
302 DerivationTree::Derived(derived) => {
303 simplify_derivation_tree(Arc::make_mut(&mut derived.cause1));
304 simplify_derivation_tree(Arc::make_mut(&mut derived.cause2));
305 simplify_derivation_tree_outer(derivation_tree);
306 }
307 }
308}
309
310fn simplify_derivation_tree_outer(
311 derivation_tree: &mut DerivationTree<String, Ranges<Version>, String>,
312) {
313 match derivation_tree {
314 DerivationTree::External(_) => {}
315 DerivationTree::Derived(derived) => {
316 match (
317 Arc::make_mut(&mut derived.cause1),
318 Arc::make_mut(&mut derived.cause2),
319 ) {
320 (
321 DerivationTree::External(External::FromDependencyOf(
322 package,
323 package_range,
324 required_package,
325 required_package_range,
326 )),
327 DerivationTree::External(External::FromDependencyOf(
328 maybe_package,
329 other_package_range,
330 maybe_required_package,
331 other_required_package_range,
332 )),
333 ) if package == maybe_package && required_package == maybe_required_package => {
334 *derivation_tree = DerivationTree::External(External::FromDependencyOf(
335 package.clone(),
336 package_range.union(other_package_range),
337 required_package.clone(),
338 required_package_range.union(other_required_package_range),
339 ))
340 }
341
342 _ => {}
343 }
344 }
345 }
346}
347
348fn collect_conflicting_packages<'dt>(
349 derivation_tree: &'dt DerivationTree<String, Ranges<Version>, String>,
350 conflicting_packages: &mut HashSet<&'dt String>,
351) {
352 match derivation_tree {
353 DerivationTree::External(external) => match external {
354 External::NotRoot(package, _)
355 | External::NoVersions(package, _)
356 | External::Custom(package, _, _) => {
357 let _ = conflicting_packages.insert(package);
358 }
359 External::FromDependencyOf(package, _, dep_package, _) => {
360 let _ = conflicting_packages.insert(package);
361 let _ = conflicting_packages.insert(dep_package);
362 }
363 },
364 DerivationTree::Derived(derived) => {
365 collect_conflicting_packages(&derived.cause1, conflicting_packages);
366 collect_conflicting_packages(&derived.cause2, conflicting_packages);
367 }
368 }
369}
370
371fn pretty_range(range: &Ranges<Version>) -> String {
372 range
373 .iter()
374 .map(|(lower, upper)| match (lower, upper) {
375 (Included(lower), Included(upper)) if lower == upper => format!("{lower}"),
376 (Included(lower), Included(upper)) => format!(">= {lower} and <= {upper}"),
377 (Included(lower), Excluded(upper)) => format!(">= {lower} and < {upper}"),
378 (Excluded(lower), Included(upper)) => format!("> {lower} and <= {upper}"),
379 (Excluded(lower), Excluded(upper)) => format!("> {lower} and < {upper}"),
380
381 (Included(version), Unbounded) => format!(">= {version}"),
382 (Excluded(version), Unbounded) => format!("> {version}"),
383 (Unbounded, Included(version)) => format!("<= {version}"),
384 (Unbounded, Excluded(version)) => format!("< {version}"),
385
386 (Unbounded, Unbounded) => "".into(),
387 })
388 .join(" or ")
389}
390
391fn is_single_version(range: &Ranges<Version>) -> bool {
392 // Note: at the time of writing this, `Ranges` has a method called
393 // `as_singleton` which, according to its doc, should do the same thing.
394 // However, it strangely seems to consider as a single version ranges like
395 // this one `> 11.0.0 and <= 12.0.0`. To me this doesn't read as a single
396 // version!
397
398 // The range needs to have exactly one segment that includes exactly one
399 // version number.
400 let mut segments = range.iter();
401 if let Some((Included(lower), Included(upper))) = segments.next()
402 && segments.next().is_none()
403 {
404 lower == upper
405 } else {
406 false
407 }
408}