pubgrub/
report.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! Build a report as clear as possible as to why
4//! dependency solving failed.
5
6use std::fmt::{self, Debug, Display};
7use std::ops::Deref;
8use std::sync::Arc;
9
10use crate::{Map, Package, Set, Term, VersionSet};
11
12/// Reporter trait.
13pub trait Reporter<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
14    /// Output type of the report.
15    type Output;
16
17    /// Generate a report from the derivation tree
18    /// describing the resolution failure using the default formatter.
19    fn report(derivation_tree: &DerivationTree<P, VS, M>) -> Self::Output;
20
21    /// Generate a report from the derivation tree
22    /// describing the resolution failure using a custom formatter.
23    fn report_with_formatter(
24        derivation_tree: &DerivationTree<P, VS, M>,
25        formatter: &impl ReportFormatter<P, VS, M, Output = Self::Output>,
26    ) -> Self::Output;
27}
28
29/// Derivation tree resulting in the impossibility to solve the dependencies of our root package.
30#[derive(Debug, Clone)]
31pub enum DerivationTree<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
32    /// External incompatibility.
33    External(External<P, VS, M>),
34    /// Incompatibility derived from two others.
35    Derived(Derived<P, VS, M>),
36}
37
38/// Incompatibility that is not derived from other incompatibilities.
39#[derive(Debug, Clone)]
40pub enum External<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
41    /// Initial incompatibility aiming at picking the root package for the first decision.
42    NotRoot(P, VS::V),
43    /// There are no versions in the given set for this package.
44    NoVersions(P, VS),
45    /// Incompatibility coming from the dependencies of a given package.
46    FromDependencyOf(P, VS, P, VS),
47    /// The package is unusable for reasons outside pubgrub.
48    Custom(P, VS, M),
49}
50
51/// Incompatibility derived from two others.
52#[derive(Debug, Clone)]
53pub struct Derived<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
54    /// Terms of the incompatibility.
55    pub terms: Map<P, Term<VS>>,
56    /// Indicate if the incompatibility is present multiple times in the derivation tree.
57    ///
58    /// If that is the case, the number is a unique id. This can be used to only explain this
59    /// incompatibility once, then refer to the explanation for the other times.
60    pub shared_id: Option<usize>,
61    /// First cause.
62    pub cause1: Arc<DerivationTree<P, VS, M>>,
63    /// Second cause.
64    pub cause2: Arc<DerivationTree<P, VS, M>>,
65}
66
67impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> DerivationTree<P, VS, M> {
68    /// Get all packages referred to in the derivation tree.
69    pub fn packages(&self) -> Set<&P> {
70        let mut packages = Set::default();
71        match self {
72            Self::External(external) => match external {
73                External::FromDependencyOf(p, _, p2, _) => {
74                    packages.insert(p);
75                    packages.insert(p2);
76                }
77                External::NoVersions(p, _)
78                | External::NotRoot(p, _)
79                | External::Custom(p, _, _) => {
80                    packages.insert(p);
81                }
82            },
83            Self::Derived(derived) => {
84                // Less efficient than recursing with a `&mut Set<&P>`, but it's sufficient for
85                // small to medium-sized inputs such as a single `DerivationTree`.
86                packages.extend(derived.terms.keys());
87                packages.extend(derived.cause1.packages().iter());
88                packages.extend(derived.cause2.packages().iter());
89            }
90        }
91        packages
92    }
93
94    /// Merge the [NoVersions](External::NoVersions) external incompatibilities
95    /// with the other one they are matched with
96    /// in a derived incompatibility.
97    /// This cleans up quite nicely the generated report.
98    /// You might want to do this if you know that the
99    /// [DependencyProvider](crate::solver::DependencyProvider)
100    /// was not run in some kind of offline mode that may not
101    /// have access to all versions existing.
102    pub fn collapse_no_versions(&mut self) {
103        match self {
104            DerivationTree::External(_) => {}
105            DerivationTree::Derived(derived) => {
106                match (
107                    Arc::make_mut(&mut derived.cause1),
108                    Arc::make_mut(&mut derived.cause2),
109                ) {
110                    (DerivationTree::External(External::NoVersions(p, r)), ref mut cause2) => {
111                        cause2.collapse_no_versions();
112                        *self = cause2
113                            .clone()
114                            .merge_no_versions(p.to_owned(), r.to_owned())
115                            .unwrap_or_else(|| self.to_owned());
116                    }
117                    (ref mut cause1, DerivationTree::External(External::NoVersions(p, r))) => {
118                        cause1.collapse_no_versions();
119                        *self = cause1
120                            .clone()
121                            .merge_no_versions(p.to_owned(), r.to_owned())
122                            .unwrap_or_else(|| self.to_owned());
123                    }
124                    _ => {
125                        Arc::make_mut(&mut derived.cause1).collapse_no_versions();
126                        Arc::make_mut(&mut derived.cause2).collapse_no_versions();
127                    }
128                }
129            }
130        }
131    }
132
133    fn merge_no_versions(self, package: P, set: VS) -> Option<Self> {
134        match self {
135            // TODO: take care of the Derived case.
136            // Once done, we can remove the Option.
137            DerivationTree::Derived(_) => Some(self),
138            DerivationTree::External(External::NotRoot(_, _)) => {
139                panic!("How did we end up with a NoVersions merged with a NotRoot?")
140            }
141            //
142            // Cannot be merged because the reason may not match
143            DerivationTree::External(External::NoVersions(_, _)) => None,
144            DerivationTree::External(External::FromDependencyOf(p1, r1, p2, r2)) => {
145                if p1 == package {
146                    Some(DerivationTree::External(External::FromDependencyOf(
147                        p1,
148                        r1.union(&set),
149                        p2,
150                        r2,
151                    )))
152                } else {
153                    Some(DerivationTree::External(External::FromDependencyOf(
154                        p1,
155                        r1,
156                        p2,
157                        r2.union(&set),
158                    )))
159                }
160            }
161            // Cannot be merged because the reason may not match
162            DerivationTree::External(External::Custom(_, _, _)) => None,
163        }
164    }
165}
166
167impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> Display for External<P, VS, M> {
168    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
169        match self {
170            Self::NotRoot(package, version) => {
171                write!(f, "we are solving dependencies of {} {}", package, version)
172            }
173            Self::NoVersions(package, set) => {
174                if set == &VS::full() {
175                    write!(f, "there is no available version for {}", package)
176                } else {
177                    write!(f, "there is no version of {} in {}", package, set)
178                }
179            }
180            Self::Custom(package, set, metadata) => {
181                if set == &VS::full() {
182                    write!(
183                        f,
184                        "dependencies of {} are unavailable {}",
185                        package, metadata
186                    )
187                } else {
188                    write!(
189                        f,
190                        "dependencies of {} at version {} are unavailable {}",
191                        package, set, metadata
192                    )
193                }
194            }
195            Self::FromDependencyOf(p, set_p, dep, set_dep) => {
196                if set_p == &VS::full() && set_dep == &VS::full() {
197                    write!(f, "{} depends on {}", p, dep)
198                } else if set_p == &VS::full() {
199                    write!(f, "{} depends on {} {}", p, dep, set_dep)
200                } else if set_dep == &VS::full() {
201                    write!(f, "{} {} depends on {}", p, set_p, dep)
202                } else {
203                    write!(f, "{} {} depends on {} {}", p, set_p, dep, set_dep)
204                }
205            }
206        }
207    }
208}
209
210/// Trait for formatting outputs in the reporter.
211pub trait ReportFormatter<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
212    /// Output type of the report.
213    type Output;
214
215    /// Format an [External] incompatibility.
216    fn format_external(&self, external: &External<P, VS, M>) -> Self::Output;
217
218    /// Format terms of an incompatibility.
219    fn format_terms(&self, terms: &Map<P, Term<VS>>) -> Self::Output;
220
221    /// Simplest case, we just combine two external incompatibilities.
222    fn explain_both_external(
223        &self,
224        external1: &External<P, VS, M>,
225        external2: &External<P, VS, M>,
226        current_terms: &Map<P, Term<VS>>,
227    ) -> Self::Output;
228
229    /// Both causes have already been explained so we use their refs.
230    fn explain_both_ref(
231        &self,
232        ref_id1: usize,
233        derived1: &Derived<P, VS, M>,
234        ref_id2: usize,
235        derived2: &Derived<P, VS, M>,
236        current_terms: &Map<P, Term<VS>>,
237    ) -> Self::Output;
238
239    /// One cause is derived (already explained so one-line),
240    /// the other is a one-line external cause,
241    /// and finally we conclude with the current incompatibility.
242    fn explain_ref_and_external(
243        &self,
244        ref_id: usize,
245        derived: &Derived<P, VS, M>,
246        external: &External<P, VS, M>,
247        current_terms: &Map<P, Term<VS>>,
248    ) -> Self::Output;
249
250    /// Add an external cause to the chain of explanations.
251    fn and_explain_external(
252        &self,
253        external: &External<P, VS, M>,
254        current_terms: &Map<P, Term<VS>>,
255    ) -> Self::Output;
256
257    /// Add an already explained incompat to the chain of explanations.
258    fn and_explain_ref(
259        &self,
260        ref_id: usize,
261        derived: &Derived<P, VS, M>,
262        current_terms: &Map<P, Term<VS>>,
263    ) -> Self::Output;
264
265    /// Add an already explained incompat to the chain of explanations.
266    fn and_explain_prior_and_external(
267        &self,
268        prior_external: &External<P, VS, M>,
269        external: &External<P, VS, M>,
270        current_terms: &Map<P, Term<VS>>,
271    ) -> Self::Output;
272}
273
274/// Default formatter for the default reporter.
275#[derive(Default, Debug)]
276pub struct DefaultStringReportFormatter;
277
278impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> ReportFormatter<P, VS, M>
279    for DefaultStringReportFormatter
280{
281    type Output = String;
282
283    fn format_external(&self, external: &External<P, VS, M>) -> String {
284        external.to_string()
285    }
286
287    fn format_terms(&self, terms: &Map<P, Term<VS>>) -> Self::Output {
288        let terms_vec: Vec<_> = terms.iter().collect();
289        match terms_vec.as_slice() {
290            [] => "version solving failed".into(),
291            // TODO: special case when that unique package is root.
292            [(package, Term::Positive(range))] => format!("{} {} is forbidden", package, range),
293            [(package, Term::Negative(range))] => format!("{} {} is mandatory", package, range),
294            [(p1, Term::Positive(r1)), (p2, Term::Negative(r2))] => self.format_external(
295                &External::<_, _, M>::FromDependencyOf(p1, r1.clone(), p2, r2.clone()),
296            ),
297            [(p1, Term::Negative(r1)), (p2, Term::Positive(r2))] => self.format_external(
298                &External::<_, _, M>::FromDependencyOf(p2, r2.clone(), p1, r1.clone()),
299            ),
300            slice => {
301                let str_terms: Vec<_> = slice.iter().map(|(p, t)| format!("{} {}", p, t)).collect();
302                str_terms.join(", ") + " are incompatible"
303            }
304        }
305    }
306
307    /// Simplest case, we just combine two external incompatibilities.
308    fn explain_both_external(
309        &self,
310        external1: &External<P, VS, M>,
311        external2: &External<P, VS, M>,
312        current_terms: &Map<P, Term<VS>>,
313    ) -> String {
314        // TODO: order should be chosen to make it more logical.
315        format!(
316            "Because {} and {}, {}.",
317            self.format_external(external1),
318            self.format_external(external2),
319            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
320        )
321    }
322
323    /// Both causes have already been explained so we use their refs.
324    fn explain_both_ref(
325        &self,
326        ref_id1: usize,
327        derived1: &Derived<P, VS, M>,
328        ref_id2: usize,
329        derived2: &Derived<P, VS, M>,
330        current_terms: &Map<P, Term<VS>>,
331    ) -> String {
332        // TODO: order should be chosen to make it more logical.
333        format!(
334            "Because {} ({}) and {} ({}), {}.",
335            ReportFormatter::<P, VS, M>::format_terms(self, &derived1.terms),
336            ref_id1,
337            ReportFormatter::<P, VS, M>::format_terms(self, &derived2.terms),
338            ref_id2,
339            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
340        )
341    }
342
343    /// One cause is derived (already explained so one-line),
344    /// the other is a one-line external cause,
345    /// and finally we conclude with the current incompatibility.
346    fn explain_ref_and_external(
347        &self,
348        ref_id: usize,
349        derived: &Derived<P, VS, M>,
350        external: &External<P, VS, M>,
351        current_terms: &Map<P, Term<VS>>,
352    ) -> String {
353        // TODO: order should be chosen to make it more logical.
354        format!(
355            "Because {} ({}) and {}, {}.",
356            ReportFormatter::<P, VS, M>::format_terms(self, &derived.terms),
357            ref_id,
358            self.format_external(external),
359            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
360        )
361    }
362
363    /// Add an external cause to the chain of explanations.
364    fn and_explain_external(
365        &self,
366        external: &External<P, VS, M>,
367        current_terms: &Map<P, Term<VS>>,
368    ) -> String {
369        format!(
370            "And because {}, {}.",
371            self.format_external(external),
372            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
373        )
374    }
375
376    /// Add an already explained incompat to the chain of explanations.
377    fn and_explain_ref(
378        &self,
379        ref_id: usize,
380        derived: &Derived<P, VS, M>,
381        current_terms: &Map<P, Term<VS>>,
382    ) -> String {
383        format!(
384            "And because {} ({}), {}.",
385            ReportFormatter::<P, VS, M>::format_terms(self, &derived.terms),
386            ref_id,
387            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
388        )
389    }
390
391    /// Add an already explained incompat to the chain of explanations.
392    fn and_explain_prior_and_external(
393        &self,
394        prior_external: &External<P, VS, M>,
395        external: &External<P, VS, M>,
396        current_terms: &Map<P, Term<VS>>,
397    ) -> String {
398        format!(
399            "And because {} and {}, {}.",
400            self.format_external(prior_external),
401            self.format_external(external),
402            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
403        )
404    }
405}
406
407/// Default reporter able to generate an explanation as a [String].
408pub struct DefaultStringReporter {
409    /// Number of explanations already with a line reference.
410    ref_count: usize,
411    /// Shared nodes that have already been marked with a line reference.
412    /// The incompatibility ids are the keys, and the line references are the values.
413    shared_with_ref: Map<usize, usize>,
414    /// Accumulated lines of the report already generated.
415    lines: Vec<String>,
416}
417
418impl DefaultStringReporter {
419    /// Initialize the reporter.
420    fn new() -> Self {
421        Self {
422            ref_count: 0,
423            shared_with_ref: Map::default(),
424            lines: Vec::new(),
425        }
426    }
427
428    fn build_recursive<
429        P: Package,
430        VS: VersionSet,
431        M: Eq + Clone + Debug + Display,
432        F: ReportFormatter<P, VS, M, Output = String>,
433    >(
434        &mut self,
435        derived: &Derived<P, VS, M>,
436        formatter: &F,
437    ) {
438        self.build_recursive_helper(derived, formatter);
439        if let Some(id) = derived.shared_id {
440            #[allow(clippy::map_entry)] // `add_line_ref` not compatible with proposed fix.
441            if !self.shared_with_ref.contains_key(&id) {
442                self.add_line_ref();
443                self.shared_with_ref.insert(id, self.ref_count);
444            }
445        };
446    }
447
448    fn build_recursive_helper<
449        P: Package,
450        VS: VersionSet,
451        M: Eq + Clone + Debug + Display,
452        F: ReportFormatter<P, VS, M, Output = String>,
453    >(
454        &mut self,
455        current: &Derived<P, VS, M>,
456        formatter: &F,
457    ) {
458        match (current.cause1.deref(), current.cause2.deref()) {
459            (DerivationTree::External(external1), DerivationTree::External(external2)) => {
460                // Simplest case, we just combine two external incompatibilities.
461                self.lines.push(formatter.explain_both_external(
462                    external1,
463                    external2,
464                    &current.terms,
465                ));
466            }
467            (DerivationTree::Derived(derived), DerivationTree::External(external)) => {
468                // One cause is derived, so we explain this first
469                // then we add the one-line external part
470                // and finally conclude with the current incompatibility.
471                self.report_one_each(derived, external, &current.terms, formatter);
472            }
473            (DerivationTree::External(external), DerivationTree::Derived(derived)) => {
474                self.report_one_each(derived, external, &current.terms, formatter);
475            }
476            (DerivationTree::Derived(derived1), DerivationTree::Derived(derived2)) => {
477                // This is the most complex case since both causes are also derived.
478                match (
479                    self.line_ref_of(derived1.shared_id),
480                    self.line_ref_of(derived2.shared_id),
481                ) {
482                    // If both causes already have been referenced (shared_id),
483                    // the explanation simply uses those references.
484                    (Some(ref1), Some(ref2)) => self.lines.push(formatter.explain_both_ref(
485                        ref1,
486                        derived1,
487                        ref2,
488                        derived2,
489                        &current.terms,
490                    )),
491                    // Otherwise, if one only has a line number reference,
492                    // we recursively call the one without reference and then
493                    // add the one with reference to conclude.
494                    (Some(ref1), None) => {
495                        self.build_recursive(derived2, formatter);
496                        self.lines
497                            .push(formatter.and_explain_ref(ref1, derived1, &current.terms));
498                    }
499                    (None, Some(ref2)) => {
500                        self.build_recursive(derived1, formatter);
501                        self.lines
502                            .push(formatter.and_explain_ref(ref2, derived2, &current.terms));
503                    }
504                    // Finally, if no line reference exists yet,
505                    // we call recursively the first one and then,
506                    //   - if this was a shared node, it will get a line ref
507                    //     and we can simply recall this with the current node.
508                    //   - otherwise, we add a line reference to it,
509                    //     recursively call on the second node,
510                    //     and finally conclude.
511                    (None, None) => {
512                        self.build_recursive(derived1, formatter);
513                        if derived1.shared_id.is_some() {
514                            self.lines.push("".into());
515                            self.build_recursive(current, formatter);
516                        } else {
517                            self.add_line_ref();
518                            let ref1 = self.ref_count;
519                            self.lines.push("".into());
520                            self.build_recursive(derived2, formatter);
521                            self.lines.push(formatter.and_explain_ref(
522                                ref1,
523                                derived1,
524                                &current.terms,
525                            ));
526                        }
527                    }
528                }
529            }
530        }
531    }
532
533    /// Report a derived and an external incompatibility.
534    ///
535    /// The result will depend on the fact that the derived incompatibility
536    /// has already been explained or not.
537    fn report_one_each<
538        P: Package,
539        VS: VersionSet,
540        M: Eq + Clone + Debug + Display,
541        F: ReportFormatter<P, VS, M, Output = String>,
542    >(
543        &mut self,
544        derived: &Derived<P, VS, M>,
545        external: &External<P, VS, M>,
546        current_terms: &Map<P, Term<VS>>,
547        formatter: &F,
548    ) {
549        match self.line_ref_of(derived.shared_id) {
550            Some(ref_id) => self.lines.push(formatter.explain_ref_and_external(
551                ref_id,
552                derived,
553                external,
554                current_terms,
555            )),
556            None => self.report_recurse_one_each(derived, external, current_terms, formatter),
557        }
558    }
559
560    /// Report one derived (without a line ref yet) and one external.
561    fn report_recurse_one_each<
562        P: Package,
563        VS: VersionSet,
564        M: Eq + Clone + Debug + Display,
565        F: ReportFormatter<P, VS, M, Output = String>,
566    >(
567        &mut self,
568        derived: &Derived<P, VS, M>,
569        external: &External<P, VS, M>,
570        current_terms: &Map<P, Term<VS>>,
571        formatter: &F,
572    ) {
573        match (derived.cause1.deref(), derived.cause2.deref()) {
574            // If the derived cause has itself one external prior cause,
575            // we can chain the external explanations.
576            (DerivationTree::Derived(prior_derived), DerivationTree::External(prior_external)) => {
577                self.build_recursive(prior_derived, formatter);
578                self.lines.push(formatter.and_explain_prior_and_external(
579                    prior_external,
580                    external,
581                    current_terms,
582                ));
583            }
584            // If the derived cause has itself one external prior cause,
585            // we can chain the external explanations.
586            (DerivationTree::External(prior_external), DerivationTree::Derived(prior_derived)) => {
587                self.build_recursive(prior_derived, formatter);
588                self.lines.push(formatter.and_explain_prior_and_external(
589                    prior_external,
590                    external,
591                    current_terms,
592                ));
593            }
594            _ => {
595                self.build_recursive(derived, formatter);
596                self.lines
597                    .push(formatter.and_explain_external(external, current_terms));
598            }
599        }
600    }
601
602    // Helper functions ########################################################
603
604    fn add_line_ref(&mut self) {
605        let new_count = self.ref_count + 1;
606        self.ref_count = new_count;
607        if let Some(line) = self.lines.last_mut() {
608            *line = format!("{} ({})", line, new_count);
609        }
610    }
611
612    fn line_ref_of(&self, shared_id: Option<usize>) -> Option<usize> {
613        shared_id.and_then(|id| self.shared_with_ref.get(&id).cloned())
614    }
615}
616
617impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> Reporter<P, VS, M>
618    for DefaultStringReporter
619{
620    type Output = String;
621
622    fn report(derivation_tree: &DerivationTree<P, VS, M>) -> Self::Output {
623        let formatter = DefaultStringReportFormatter;
624        match derivation_tree {
625            DerivationTree::External(external) => formatter.format_external(external),
626            DerivationTree::Derived(derived) => {
627                let mut reporter = Self::new();
628                reporter.build_recursive(derived, &formatter);
629                reporter.lines.join("\n")
630            }
631        }
632    }
633
634    fn report_with_formatter(
635        derivation_tree: &DerivationTree<P, VS, M>,
636        formatter: &impl ReportFormatter<P, VS, M, Output = Self::Output>,
637    ) -> Self::Output {
638        match derivation_tree {
639            DerivationTree::External(external) => formatter.format_external(external),
640            DerivationTree::Derived(derived) => {
641                let mut reporter = Self::new();
642                reporter.build_recursive(derived, formatter);
643                reporter.lines.join("\n")
644            }
645        }
646    }
647}
pubgrub/report.rs

pubgrub/
report.rs
