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::Custom(_, r, reason)) => Some(
145                DerivationTree::External(External::Custom(package, set.union(&r), reason)),
146            ),
147            DerivationTree::External(External::FromDependencyOf(p1, r1, p2, r2)) => {
148                if p1 == package {
149                    Some(DerivationTree::External(External::FromDependencyOf(
150                        p1,
151                        r1.union(&set),
152                        p2,
153                        r2,
154                    )))
155                } else {
156                    Some(DerivationTree::External(External::FromDependencyOf(
157                        p1,
158                        r1,
159                        p2,
160                        r2.union(&set),
161                    )))
162                }
163            }
164        }
165    }
166}
167
168impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> Display for External<P, VS, M> {
169    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
170        match self {
171            Self::NotRoot(package, version) => {
172                write!(f, "we are solving dependencies of {package} {version}")
173            }
174            Self::NoVersions(package, set) => {
175                if set == &VS::full() {
176                    write!(f, "there is no available version for {package}")
177                } else {
178                    write!(f, "there is no version of {package} in {set}")
179                }
180            }
181            Self::Custom(package, set, metadata) => {
182                if set == &VS::full() {
183                    write!(f, "dependencies of {package} are unavailable {metadata}")
184                } else {
185                    write!(
186                        f,
187                        "dependencies of {package} at version {set} are unavailable {metadata}"
188                    )
189                }
190            }
191            Self::FromDependencyOf(p, set_p, dep, set_dep) => {
192                if set_p == &VS::full() && set_dep == &VS::full() {
193                    write!(f, "{p} depends on {dep}")
194                } else if set_p == &VS::full() {
195                    write!(f, "{p} depends on {dep} {set_dep}")
196                } else if set_dep == &VS::full() {
197                    write!(f, "{p} {set_p} depends on {dep}")
198                } else {
199                    write!(f, "{p} {set_p} depends on {dep} {set_dep}")
200                }
201            }
202        }
203    }
204}
205
206/// Trait for formatting outputs in the reporter.
207pub trait ReportFormatter<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
208    /// Output type of the report.
209    type Output;
210
211    /// Format an [External] incompatibility.
212    fn format_external(&self, external: &External<P, VS, M>) -> Self::Output;
213
214    /// Format terms of an incompatibility.
215    fn format_terms(&self, terms: &Map<P, Term<VS>>) -> Self::Output;
216
217    /// Simplest case, we just combine two external incompatibilities.
218    fn explain_both_external(
219        &self,
220        external1: &External<P, VS, M>,
221        external2: &External<P, VS, M>,
222        current_terms: &Map<P, Term<VS>>,
223    ) -> Self::Output;
224
225    /// Both causes have already been explained so we use their refs.
226    fn explain_both_ref(
227        &self,
228        ref_id1: usize,
229        derived1: &Derived<P, VS, M>,
230        ref_id2: usize,
231        derived2: &Derived<P, VS, M>,
232        current_terms: &Map<P, Term<VS>>,
233    ) -> Self::Output;
234
235    /// One cause is derived (already explained so one-line),
236    /// the other is a one-line external cause,
237    /// and finally we conclude with the current incompatibility.
238    fn explain_ref_and_external(
239        &self,
240        ref_id: usize,
241        derived: &Derived<P, VS, M>,
242        external: &External<P, VS, M>,
243        current_terms: &Map<P, Term<VS>>,
244    ) -> Self::Output;
245
246    /// Add an external cause to the chain of explanations.
247    fn and_explain_external(
248        &self,
249        external: &External<P, VS, M>,
250        current_terms: &Map<P, Term<VS>>,
251    ) -> Self::Output;
252
253    /// Add an already explained incompat to the chain of explanations.
254    fn and_explain_ref(
255        &self,
256        ref_id: usize,
257        derived: &Derived<P, VS, M>,
258        current_terms: &Map<P, Term<VS>>,
259    ) -> Self::Output;
260
261    /// Add an already explained incompat to the chain of explanations.
262    fn and_explain_prior_and_external(
263        &self,
264        prior_external: &External<P, VS, M>,
265        external: &External<P, VS, M>,
266        current_terms: &Map<P, Term<VS>>,
267    ) -> Self::Output;
268}
269
270/// Default formatter for the default reporter.
271#[derive(Default, Debug)]
272pub struct DefaultStringReportFormatter;
273
274impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> ReportFormatter<P, VS, M>
275    for DefaultStringReportFormatter
276{
277    type Output = String;
278
279    fn format_external(&self, external: &External<P, VS, M>) -> String {
280        external.to_string()
281    }
282
283    fn format_terms(&self, terms: &Map<P, Term<VS>>) -> Self::Output {
284        let terms_vec: Vec<_> = terms.iter().collect();
285        match terms_vec.as_slice() {
286            [] => "version solving failed".into(),
287            // TODO: special case when that unique package is root.
288            [(package, Term::Positive(range))] => format!("{package} {range} is forbidden"),
289            [(package, Term::Negative(range))] => format!("{package} {range} is mandatory"),
290            [(p1, Term::Positive(r1)), (p2, Term::Negative(r2))] => self.format_external(
291                &External::<_, _, M>::FromDependencyOf(p1, r1.clone(), p2, r2.clone()),
292            ),
293            [(p1, Term::Negative(r1)), (p2, Term::Positive(r2))] => self.format_external(
294                &External::<_, _, M>::FromDependencyOf(p2, r2.clone(), p1, r1.clone()),
295            ),
296            slice => {
297                let str_terms: Vec<_> = slice.iter().map(|(p, t)| format!("{p} {t}")).collect();
298                str_terms.join(", ") + " are incompatible"
299            }
300        }
301    }
302
303    /// Simplest case, we just combine two external incompatibilities.
304    fn explain_both_external(
305        &self,
306        external1: &External<P, VS, M>,
307        external2: &External<P, VS, M>,
308        current_terms: &Map<P, Term<VS>>,
309    ) -> String {
310        // TODO: order should be chosen to make it more logical.
311        format!(
312            "Because {} and {}, {}.",
313            self.format_external(external1),
314            self.format_external(external2),
315            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
316        )
317    }
318
319    /// Both causes have already been explained so we use their refs.
320    fn explain_both_ref(
321        &self,
322        ref_id1: usize,
323        derived1: &Derived<P, VS, M>,
324        ref_id2: usize,
325        derived2: &Derived<P, VS, M>,
326        current_terms: &Map<P, Term<VS>>,
327    ) -> String {
328        // TODO: order should be chosen to make it more logical.
329        format!(
330            "Because {} ({}) and {} ({}), {}.",
331            ReportFormatter::<P, VS, M>::format_terms(self, &derived1.terms),
332            ref_id1,
333            ReportFormatter::<P, VS, M>::format_terms(self, &derived2.terms),
334            ref_id2,
335            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
336        )
337    }
338
339    /// One cause is derived (already explained so one-line),
340    /// the other is a one-line external cause,
341    /// and finally we conclude with the current incompatibility.
342    fn explain_ref_and_external(
343        &self,
344        ref_id: usize,
345        derived: &Derived<P, VS, M>,
346        external: &External<P, VS, M>,
347        current_terms: &Map<P, Term<VS>>,
348    ) -> String {
349        // TODO: order should be chosen to make it more logical.
350        format!(
351            "Because {} ({}) and {}, {}.",
352            ReportFormatter::<P, VS, M>::format_terms(self, &derived.terms),
353            ref_id,
354            self.format_external(external),
355            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
356        )
357    }
358
359    /// Add an external cause to the chain of explanations.
360    fn and_explain_external(
361        &self,
362        external: &External<P, VS, M>,
363        current_terms: &Map<P, Term<VS>>,
364    ) -> String {
365        format!(
366            "And because {}, {}.",
367            self.format_external(external),
368            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
369        )
370    }
371
372    /// Add an already explained incompat to the chain of explanations.
373    fn and_explain_ref(
374        &self,
375        ref_id: usize,
376        derived: &Derived<P, VS, M>,
377        current_terms: &Map<P, Term<VS>>,
378    ) -> String {
379        format!(
380            "And because {} ({}), {}.",
381            ReportFormatter::<P, VS, M>::format_terms(self, &derived.terms),
382            ref_id,
383            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
384        )
385    }
386
387    /// Add an already explained incompat to the chain of explanations.
388    fn and_explain_prior_and_external(
389        &self,
390        prior_external: &External<P, VS, M>,
391        external: &External<P, VS, M>,
392        current_terms: &Map<P, Term<VS>>,
393    ) -> String {
394        format!(
395            "And because {} and {}, {}.",
396            self.format_external(prior_external),
397            self.format_external(external),
398            ReportFormatter::<P, VS, M>::format_terms(self, current_terms)
399        )
400    }
401}
402
403/// Default reporter able to generate an explanation as a [String].
404pub struct DefaultStringReporter {
405    /// Number of explanations already with a line reference.
406    ref_count: usize,
407    /// Shared nodes that have already been marked with a line reference.
408    /// The incompatibility ids are the keys, and the line references are the values.
409    shared_with_ref: Map<usize, usize>,
410    /// Accumulated lines of the report already generated.
411    lines: Vec<String>,
412}
413
414impl DefaultStringReporter {
415    /// Initialize the reporter.
416    fn new() -> Self {
417        Self {
418            ref_count: 0,
419            shared_with_ref: Map::default(),
420            lines: Vec::new(),
421        }
422    }
423
424    fn build_recursive<
425        P: Package,
426        VS: VersionSet,
427        M: Eq + Clone + Debug + Display,
428        F: ReportFormatter<P, VS, M, Output = String>,
429    >(
430        &mut self,
431        derived: &Derived<P, VS, M>,
432        formatter: &F,
433    ) {
434        self.build_recursive_helper(derived, formatter);
435        if let Some(id) = derived.shared_id {
436            #[allow(clippy::map_entry)] // `add_line_ref` not compatible with proposed fix.
437            if !self.shared_with_ref.contains_key(&id) {
438                self.add_line_ref();
439                self.shared_with_ref.insert(id, self.ref_count);
440            }
441        };
442    }
443
444    fn build_recursive_helper<
445        P: Package,
446        VS: VersionSet,
447        M: Eq + Clone + Debug + Display,
448        F: ReportFormatter<P, VS, M, Output = String>,
449    >(
450        &mut self,
451        current: &Derived<P, VS, M>,
452        formatter: &F,
453    ) {
454        match (current.cause1.deref(), current.cause2.deref()) {
455            (DerivationTree::External(external1), DerivationTree::External(external2)) => {
456                // Simplest case, we just combine two external incompatibilities.
457                self.lines.push(formatter.explain_both_external(
458                    external1,
459                    external2,
460                    &current.terms,
461                ));
462            }
463            (DerivationTree::Derived(derived), DerivationTree::External(external)) => {
464                // One cause is derived, so we explain this first
465                // then we add the one-line external part
466                // and finally conclude with the current incompatibility.
467                self.report_one_each(derived, external, &current.terms, formatter);
468            }
469            (DerivationTree::External(external), DerivationTree::Derived(derived)) => {
470                self.report_one_each(derived, external, &current.terms, formatter);
471            }
472            (DerivationTree::Derived(derived1), DerivationTree::Derived(derived2)) => {
473                // This is the most complex case since both causes are also derived.
474                match (
475                    self.line_ref_of(derived1.shared_id),
476                    self.line_ref_of(derived2.shared_id),
477                ) {
478                    // If both causes already have been referenced (shared_id),
479                    // the explanation simply uses those references.
480                    (Some(ref1), Some(ref2)) => self.lines.push(formatter.explain_both_ref(
481                        ref1,
482                        derived1,
483                        ref2,
484                        derived2,
485                        &current.terms,
486                    )),
487                    // Otherwise, if one only has a line number reference,
488                    // we recursively call the one without reference and then
489                    // add the one with reference to conclude.
490                    (Some(ref1), None) => {
491                        self.build_recursive(derived2, formatter);
492                        self.lines
493                            .push(formatter.and_explain_ref(ref1, derived1, &current.terms));
494                    }
495                    (None, Some(ref2)) => {
496                        self.build_recursive(derived1, formatter);
497                        self.lines
498                            .push(formatter.and_explain_ref(ref2, derived2, &current.terms));
499                    }
500                    // Finally, if no line reference exists yet,
501                    // we call recursively the first one and then,
502                    //   - if this was a shared node, it will get a line ref
503                    //     and we can simply recall this with the current node.
504                    //   - otherwise, we add a line reference to it,
505                    //     recursively call on the second node,
506                    //     and finally conclude.
507                    (None, None) => {
508                        self.build_recursive(derived1, formatter);
509                        if derived1.shared_id.is_some() {
510                            self.lines.push("".into());
511                            self.build_recursive(current, formatter);
512                        } else {
513                            self.add_line_ref();
514                            let ref1 = self.ref_count;
515                            self.lines.push("".into());
516                            self.build_recursive(derived2, formatter);
517                            self.lines.push(formatter.and_explain_ref(
518                                ref1,
519                                derived1,
520                                &current.terms,
521                            ));
522                        }
523                    }
524                }
525            }
526        }
527    }
528
529    /// Report a derived and an external incompatibility.
530    ///
531    /// The result will depend on the fact that the derived incompatibility
532    /// has already been explained or not.
533    fn report_one_each<
534        P: Package,
535        VS: VersionSet,
536        M: Eq + Clone + Debug + Display,
537        F: ReportFormatter<P, VS, M, Output = String>,
538    >(
539        &mut self,
540        derived: &Derived<P, VS, M>,
541        external: &External<P, VS, M>,
542        current_terms: &Map<P, Term<VS>>,
543        formatter: &F,
544    ) {
545        match self.line_ref_of(derived.shared_id) {
546            Some(ref_id) => self.lines.push(formatter.explain_ref_and_external(
547                ref_id,
548                derived,
549                external,
550                current_terms,
551            )),
552            None => self.report_recurse_one_each(derived, external, current_terms, formatter),
553        }
554    }
555
556    /// Report one derived (without a line ref yet) and one external.
557    fn report_recurse_one_each<
558        P: Package,
559        VS: VersionSet,
560        M: Eq + Clone + Debug + Display,
561        F: ReportFormatter<P, VS, M, Output = String>,
562    >(
563        &mut self,
564        derived: &Derived<P, VS, M>,
565        external: &External<P, VS, M>,
566        current_terms: &Map<P, Term<VS>>,
567        formatter: &F,
568    ) {
569        match (derived.cause1.deref(), derived.cause2.deref()) {
570            // If the derived cause has itself one external prior cause,
571            // we can chain the external explanations.
572            (DerivationTree::Derived(prior_derived), DerivationTree::External(prior_external)) => {
573                self.build_recursive(prior_derived, formatter);
574                self.lines.push(formatter.and_explain_prior_and_external(
575                    prior_external,
576                    external,
577                    current_terms,
578                ));
579            }
580            // If the derived cause has itself one external prior cause,
581            // we can chain the external explanations.
582            (DerivationTree::External(prior_external), DerivationTree::Derived(prior_derived)) => {
583                self.build_recursive(prior_derived, formatter);
584                self.lines.push(formatter.and_explain_prior_and_external(
585                    prior_external,
586                    external,
587                    current_terms,
588                ));
589            }
590            _ => {
591                self.build_recursive(derived, formatter);
592                self.lines
593                    .push(formatter.and_explain_external(external, current_terms));
594            }
595        }
596    }
597
598    // Helper functions ########################################################
599
600    fn add_line_ref(&mut self) {
601        let new_count = self.ref_count + 1;
602        self.ref_count = new_count;
603        if let Some(line) = self.lines.last_mut() {
604            *line = format!("{line} ({new_count})");
605        }
606    }
607
608    fn line_ref_of(&self, shared_id: Option<usize>) -> Option<usize> {
609        shared_id.and_then(|id| self.shared_with_ref.get(&id).cloned())
610    }
611}
612
613impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> Reporter<P, VS, M>
614    for DefaultStringReporter
615{
616    type Output = String;
617
618    fn report(derivation_tree: &DerivationTree<P, VS, M>) -> Self::Output {
619        let formatter = DefaultStringReportFormatter;
620        match derivation_tree {
621            DerivationTree::External(external) => formatter.format_external(external),
622            DerivationTree::Derived(derived) => {
623                let mut reporter = Self::new();
624                reporter.build_recursive(derived, &formatter);
625                reporter.lines.join("\n")
626            }
627        }
628    }
629
630    fn report_with_formatter(
631        derivation_tree: &DerivationTree<P, VS, M>,
632        formatter: &impl ReportFormatter<P, VS, M, Output = Self::Output>,
633    ) -> Self::Output {
634        match derivation_tree {
635            DerivationTree::External(external) => formatter.format_external(external),
636            DerivationTree::Derived(derived) => {
637                let mut reporter = Self::new();
638                reporter.build_recursive(derived, formatter);
639                reporter.lines.join("\n")
640            }
641        }
642    }
643}
pubgrub/report.rs

pubgrub/
report.rs
