pubgrub/internal/
incompatibility.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! An incompatibility is a set of terms for different packages
4//! that should never be satisfied all together.
5
6use std::fmt::{Debug, Display};
7use std::sync::Arc;
8
9use crate::internal::{Arena, HashArena, Id, SmallMap};
10use crate::{
11    DependencyProvider, DerivationTree, Derived, External, Map, Package, Set, Term, VersionSet,
12    term,
13};
14
15/// An incompatibility is a set of terms for different packages
16/// that should never be satisfied all together.
17/// An incompatibility usually originates from a package dependency.
18/// For example, if package A at version 1 depends on package B
19/// at version 2, you can never have both terms `A = 1`
20/// and `not B = 2` satisfied at the same time in a partial solution.
21/// This would mean that we found a solution with package A at version 1
22/// but not with package B at version 2.
23/// Yet A at version 1 depends on B at version 2 so this is not possible.
24/// Therefore, the set `{ A = 1, not B = 2 }` is an incompatibility,
25/// defined from dependencies of A at version 1.
26///
27/// Incompatibilities can also be derived from two other incompatibilities
28/// during conflict resolution. More about all this in
29/// [PubGrub documentation](https://github.com/dart-lang/pub/blob/master/doc/solver.md#incompatibility).
30#[derive(Debug, Clone)]
31pub struct Incompatibility<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
32    package_terms: SmallMap<Id<P>, Term<VS>>,
33    /// The reason for the incompatibility.
34    pub kind: Kind<P, VS, M>,
35}
36
37/// Type alias of unique identifiers for incompatibilities.
38pub type IncompId<P, VS, M> = Id<Incompatibility<P, VS, M>>;
39
40pub(crate) type IncompDpId<DP> = IncompId<
41    <DP as DependencyProvider>::P,
42    <DP as DependencyProvider>::VS,
43    <DP as DependencyProvider>::M,
44>;
45
46/// The reason for the incompatibility.
47#[derive(Debug, Clone)]
48pub enum Kind<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
49    /// Initial incompatibility aiming at picking the root package for the first decision.
50    ///
51    /// This incompatibility drives the resolution, it requires that we pick the (virtual) root
52    /// packages.
53    NotRoot(Id<P>, VS::V),
54    /// There are no versions in the given range for this package.
55    ///
56    /// This incompatibility is used when we tried all versions in a range and no version
57    /// worked, so we have to backtrack
58    NoVersions(Id<P>, VS),
59    /// Incompatibility coming from the dependencies of a given package.
60    ///
61    /// If a@1 depends on b>=1,<2, we create an incompatibility with terms `{a 1, b <1,>=2}` with
62    /// kind `FromDependencyOf(a, 1, b, >=1,<2)`.
63    ///
64    /// We can merge multiple dependents with the same version. For example, if a@1 depends on b and
65    /// a@2 depends on b, we can say instead a@1||2 depends on b.
66    FromDependencyOf(Id<P>, VS, Id<P>, VS),
67    /// Derived from two causes. Stores cause ids.
68    ///
69    /// For example, if a -> b and b -> c, we can derive a -> c.
70    DerivedFrom(IncompId<P, VS, M>, IncompId<P, VS, M>),
71    /// The package is unavailable for reasons outside pubgrub.
72    ///
73    /// Examples:
74    /// * The version would require building the package, but builds are disabled.
75    /// * The package is not available in the cache, but internet access has been disabled.
76    Custom(Id<P>, VS, M),
77}
78
79/// A Relation describes how a set of terms can be compared to an incompatibility.
80/// Typically, the set of terms comes from the partial solution.
81#[derive(Eq, PartialEq, Debug)]
82pub(crate) enum Relation<P: Package> {
83    /// We say that a set of terms S satisfies an incompatibility I
84    /// if S satisfies every term in I.
85    Satisfied,
86    /// We say that S contradicts I
87    /// if S contradicts at least one term in I.
88    Contradicted(Id<P>),
89    /// If S satisfies all but one of I's terms and is inconclusive for the remaining term,
90    /// we say S "almost satisfies" I and we call the remaining term the "unsatisfied term".
91    AlmostSatisfied(Id<P>),
92    /// Otherwise, we say that their relation is inconclusive.
93    Inconclusive,
94}
95
96impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> Incompatibility<P, VS, M> {
97    /// Create the initial "not Root" incompatibility.
98    pub(crate) fn not_root(package: Id<P>, version: VS::V) -> Self {
99        Self {
100            package_terms: SmallMap::One([(
101                package,
102                Term::Negative(VS::singleton(version.clone())),
103            )]),
104            kind: Kind::NotRoot(package, version),
105        }
106    }
107
108    /// Create an incompatibility to remember that a given set does not contain any version.
109    pub fn no_versions(package: Id<P>, term: Term<VS>) -> Self {
110        let set = match &term {
111            Term::Positive(r) => r.clone(),
112            Term::Negative(_) => panic!("No version should have a positive term"),
113        };
114        Self {
115            package_terms: SmallMap::One([(package, term)]),
116            kind: Kind::NoVersions(package, set),
117        }
118    }
119
120    /// Create an incompatibility for a reason outside pubgrub.
121    #[allow(dead_code)] // Used by uv
122    pub fn custom_term(package: Id<P>, term: Term<VS>, metadata: M) -> Self {
123        let set = match &term {
124            Term::Positive(r) => r.clone(),
125            Term::Negative(_) => panic!("No version should have a positive term"),
126        };
127        Self {
128            package_terms: SmallMap::One([(package, term)]),
129            kind: Kind::Custom(package, set, metadata),
130        }
131    }
132
133    /// Create an incompatibility for a reason outside pubgrub.
134    pub fn custom_version(package: Id<P>, version: VS::V, metadata: M) -> Self {
135        let set = VS::singleton(version);
136        let term = Term::Positive(set.clone());
137        Self {
138            package_terms: SmallMap::One([(package, term)]),
139            kind: Kind::Custom(package, set, metadata),
140        }
141    }
142
143    /// Build an incompatibility from a given dependency.
144    pub fn from_dependency(package: Id<P>, versions: VS, dep: (Id<P>, VS)) -> Self {
145        let (p2, set2) = dep;
146        Self {
147            package_terms: if set2 == VS::empty() {
148                SmallMap::One([(package, Term::Positive(versions.clone()))])
149            } else {
150                SmallMap::Two([
151                    (package, Term::Positive(versions.clone())),
152                    (p2, Term::Negative(set2.clone())),
153                ])
154            },
155            kind: Kind::FromDependencyOf(package, versions, p2, set2),
156        }
157    }
158
159    pub(crate) fn as_dependency(&self) -> Option<(Id<P>, Id<P>)> {
160        match &self.kind {
161            Kind::FromDependencyOf(p1, _, p2, _) => Some((*p1, *p2)),
162            _ => None,
163        }
164    }
165
166    /// Merge dependant versions with the same dependency.
167    ///
168    /// When multiple versions of a package depend on the same range of another package,
169    /// we can merge the two into a single incompatibility.
170    /// For example, if a@1 depends on b and a@2 depends on b, we can say instead
171    /// a@1||2 depends on b.
172    ///
173    /// It is a special case of prior cause computation where the unified package
174    /// is the common dependant in the two incompatibilities expressing dependencies.
175    pub(crate) fn merge_dependents(&self, other: &Self) -> Option<Self> {
176        // It is almost certainly a bug to call this method without checking that self is a dependency
177        debug_assert!(self.as_dependency().is_some());
178        // Check that both incompatibilities are of the shape p1 depends on p2,
179        // with the same p1 and p2.
180        let self_pkgs = self.as_dependency()?;
181        if self_pkgs != other.as_dependency()? {
182            return None;
183        }
184        let (p1, p2) = self_pkgs;
185        // We ignore self-dependencies. They are always either trivially true or trivially false,
186        // as the package version implies whether the constraint will always be fulfilled or always
187        // violated.
188        // At time of writing, the public crate API only allowed a map of dependencies,
189        // meaning it can't hit this branch, which requires two self-dependencies.
190        if p1 == p2 {
191            return None;
192        }
193        let dep_term = self.get(p2);
194        // The dependency range for p2 must be the same in both case
195        // to be able to merge multiple p1 ranges.
196        if dep_term != other.get(p2) {
197            return None;
198        }
199        Some(Self::from_dependency(
200            p1,
201            self.get(p1)
202                .unwrap()
203                .unwrap_positive()
204                .union(other.get(p1).unwrap().unwrap_positive()), // It is safe to `simplify` here
205            (
206                p2,
207                dep_term.map_or(VS::empty(), |v| v.unwrap_negative().clone()),
208            ),
209        ))
210    }
211
212    /// Prior cause of two incompatibilities using the rule of resolution.
213    pub(crate) fn prior_cause(
214        incompat: Id<Self>,
215        satisfier_cause: Id<Self>,
216        package: Id<P>,
217        incompatibility_store: &Arena<Self>,
218    ) -> Self {
219        let kind = Kind::DerivedFrom(incompat, satisfier_cause);
220        // Optimization to avoid cloning and dropping t1
221        let (t1, mut package_terms) = incompatibility_store[incompat]
222            .package_terms
223            .split_one(&package)
224            .unwrap();
225        let satisfier_cause_terms = &incompatibility_store[satisfier_cause].package_terms;
226        package_terms.merge(
227            satisfier_cause_terms.iter().filter(|(p, _)| p != &&package),
228            |t1, t2| Some(t1.intersection(t2)),
229        );
230        let term = t1.union(satisfier_cause_terms.get(&package).unwrap());
231        if term != Term::any() {
232            package_terms.insert(package, term);
233        }
234        Self {
235            package_terms,
236            kind,
237        }
238    }
239
240    /// Check if an incompatibility should mark the end of the algorithm
241    /// because it satisfies the root package.
242    pub(crate) fn is_terminal(&self, root_package: Id<P>, root_version: &VS::V) -> bool {
243        if self.package_terms.len() == 0 {
244            true
245        } else if self.package_terms.len() > 1 {
246            false
247        } else {
248            let (package, term) = self.package_terms.iter().next().unwrap();
249            (package == &root_package) && term.contains(root_version)
250        }
251    }
252
253    /// Get the term related to a given package (if it exists).
254    pub(crate) fn get(&self, package: Id<P>) -> Option<&Term<VS>> {
255        self.package_terms.get(&package)
256    }
257
258    /// Iterate over packages.
259    pub fn iter(&self) -> impl Iterator<Item = (Id<P>, &Term<VS>)> {
260        self.package_terms
261            .iter()
262            .map(|(package, term)| (*package, term))
263    }
264
265    // Reporting ###############################################################
266
267    /// Retrieve parent causes if of type DerivedFrom.
268    pub(crate) fn causes(&self) -> Option<(Id<Self>, Id<Self>)> {
269        match self.kind {
270            Kind::DerivedFrom(id1, id2) => Some((id1, id2)),
271            _ => None,
272        }
273    }
274
275    /// Build a derivation tree for error reporting.
276    pub(crate) fn build_derivation_tree(
277        self_id: Id<Self>,
278        shared_ids: &Set<Id<Self>>,
279        store: &Arena<Self>,
280        package_store: &HashArena<P>,
281        precomputed: &Map<Id<Self>, Arc<DerivationTree<P, VS, M>>>,
282    ) -> DerivationTree<P, VS, M> {
283        match store[self_id].kind.clone() {
284            Kind::DerivedFrom(id1, id2) => {
285                let derived: Derived<P, VS, M> = Derived {
286                    terms: store[self_id]
287                        .package_terms
288                        .iter()
289                        .map(|(&a, b)| (package_store[a].clone(), b.clone()))
290                        .collect(),
291                    shared_id: shared_ids.get(&self_id).map(|id| id.into_raw()),
292                    cause1: precomputed
293                        .get(&id1)
294                        .expect("Non-topological calls building tree")
295                        .clone(),
296                    cause2: precomputed
297                        .get(&id2)
298                        .expect("Non-topological calls building tree")
299                        .clone(),
300                };
301                DerivationTree::Derived(derived)
302            }
303            Kind::NotRoot(package, version) => {
304                DerivationTree::External(External::NotRoot(package_store[package].clone(), version))
305            }
306            Kind::NoVersions(package, set) => DerivationTree::External(External::NoVersions(
307                package_store[package].clone(),
308                set.clone(),
309            )),
310            Kind::FromDependencyOf(package, set, dep_package, dep_set) => {
311                DerivationTree::External(External::FromDependencyOf(
312                    package_store[package].clone(),
313                    set.clone(),
314                    package_store[dep_package].clone(),
315                    dep_set.clone(),
316                ))
317            }
318            Kind::Custom(package, set, metadata) => DerivationTree::External(External::Custom(
319                package_store[package].clone(),
320                set.clone(),
321                metadata.clone(),
322            )),
323        }
324    }
325}
326
327impl<'a, P: Package, VS: VersionSet + 'a, M: Eq + Clone + Debug + Display + 'a>
328    Incompatibility<P, VS, M>
329{
330    /// CF definition of Relation enum.
331    pub(crate) fn relation(&self, terms: impl Fn(Id<P>) -> Option<&'a Term<VS>>) -> Relation<P> {
332        let mut relation = Relation::Satisfied;
333        for (&package, incompat_term) in self.package_terms.iter() {
334            match terms(package).map(|term| incompat_term.relation_with(term)) {
335                Some(term::Relation::Satisfied) => {}
336                Some(term::Relation::Contradicted) => {
337                    return Relation::Contradicted(package);
338                }
339                None | Some(term::Relation::Inconclusive) => {
340                    // If a package is not present, the intersection is the same as [Term::any].
341                    // According to the rules of satisfactions, the relation would be inconclusive.
342                    // It could also be satisfied if the incompatibility term was also [Term::any],
343                    // but we systematically remove those from incompatibilities
344                    // so we're safe on that front.
345                    if relation == Relation::Satisfied {
346                        relation = Relation::AlmostSatisfied(package);
347                    } else {
348                        return Relation::Inconclusive;
349                    }
350                }
351            }
352        }
353        relation
354    }
355}
356
357impl<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> Incompatibility<P, VS, M> {
358    /// Display the incompatibility.
359    pub fn display<'a>(&'a self, package_store: &'a HashArena<P>) -> impl Display + 'a {
360        match self.iter().collect::<Vec<_>>().as_slice() {
361            [] => "version solving failed".into(),
362            // TODO: special case when that unique package is root.
363            [(package, Term::Positive(range))] => {
364                format!("{} {} is forbidden", package_store[*package], range)
365            }
366            [(package, Term::Negative(range))] => {
367                format!("{} {} is mandatory", package_store[*package], range)
368            }
369            [
370                (p_pos, Term::Positive(r_pos)),
371                (p_neg, Term::Negative(r_neg)),
372            ]
373            | [
374                (p_neg, Term::Negative(r_neg)),
375                (p_pos, Term::Positive(r_pos)),
376            ] => External::<_, _, M>::FromDependencyOf(
377                &package_store[*p_pos],
378                r_pos.clone(),
379                &package_store[*p_neg],
380                r_neg.clone(),
381            )
382            .to_string(),
383            slice => {
384                let str_terms: Vec<_> = slice
385                    .iter()
386                    .map(|(p, t)| format!("{} {}", package_store[*p], t))
387                    .collect();
388                str_terms.join(", ") + " are incompatible"
389            }
390        }
391    }
392}
393
394// TESTS #######################################################################
395
396#[cfg(test)]
397pub(crate) mod tests {
398    use proptest::prelude::*;
399    use std::cmp::Reverse;
400    use std::collections::BTreeMap;
401
402    use super::*;
403    use crate::internal::State;
404    use crate::term::tests::strategy as term_strat;
405    use crate::{OfflineDependencyProvider, Ranges};
406
407    proptest! {
408
409        /// For any three different packages p1, p2 and p3,
410        /// for any three terms t1, t2 and t3,
411        /// if we have the two following incompatibilities:
412        ///    { p1: t1, p2: not t2 }
413        ///    { p2: t2, p3: t3 }
414        /// the rule of resolution says that we can deduce the following incompatibility:
415        ///    { p1: t1, p3: t3 }
416        #[test]
417        fn rule_of_resolution(t1 in term_strat(), t2 in term_strat(), t3 in term_strat()) {
418            let mut store = Arena::new();
419            let mut package_store = HashArena::new();
420            let p1 = package_store.alloc("p1");
421            let p2 = package_store.alloc("p2");
422            let p3 = package_store.alloc("p3");
423            let i1 = store.alloc(Incompatibility {
424                package_terms: SmallMap::Two([(p1, t1.clone()), (p2, t2.negate())]),
425                kind: Kind::<_, _, String>::FromDependencyOf(p1, Ranges::full(), p2, Ranges::full())
426            });
427
428            let i2 = store.alloc(Incompatibility {
429                package_terms: SmallMap::Two([(p2, t2), (p3, t3.clone())]),
430                kind: Kind::<_, _, String>::FromDependencyOf(p2, Ranges::full(), p3, Ranges::full())
431            });
432
433            let mut i3 = Map::default();
434            i3.insert(p1, t1);
435            i3.insert(p3, t3);
436
437            let i_resolution = Incompatibility::prior_cause(i1, i2, p2, &store);
438            assert_eq!(i_resolution.package_terms.iter().map(|(&k, v)|(k, v.clone())).collect::<Map<_, _>>(), i3);
439        }
440
441    }
442
443    /// Check that multiple self-dependencies are supported.
444    ///
445    /// The current public API deduplicates dependencies through a map, so we test them here
446    /// manually.
447    ///
448    /// https://github.com/astral-sh/uv/issues/13344
449    #[test]
450    fn package_depend_on_self() {
451        let cases: &[Vec<(String, Ranges<usize>)>] = &[
452            vec![("foo".to_string(), Ranges::full())],
453            vec![
454                ("foo".to_string(), Ranges::full()),
455                ("foo".to_string(), Ranges::full()),
456            ],
457            vec![
458                ("foo".to_string(), Ranges::full()),
459                ("foo".to_string(), Ranges::singleton(1usize)),
460            ],
461            vec![
462                ("foo".to_string(), Ranges::singleton(1usize)),
463                ("foo".to_string(), Ranges::from_range_bounds(1usize..2)),
464                ("foo".to_string(), Ranges::from_range_bounds(1usize..3)),
465            ],
466        ];
467
468        for case in cases {
469            let mut state: State<OfflineDependencyProvider<String, Ranges<usize>>> =
470                State::init("root".to_string(), 0);
471            state.unit_propagation(state.root_package).unwrap();
472
473            // Add the root package
474            state.add_package_version_dependencies(
475                state.root_package,
476                0,
477                [("foo".to_string(), Ranges::singleton(1usize))],
478            );
479            state.unit_propagation(state.root_package).unwrap();
480
481            // Add a package that depends on itself twice
482            let (next, _) = state
483                .partial_solution
484                .pick_highest_priority_pkg(|_p, _r| (0, Reverse(0)))
485                .unwrap();
486            state.add_package_version_dependencies(next, 1, case.clone());
487            state.unit_propagation(next).unwrap();
488
489            assert!(
490                state
491                    .partial_solution
492                    .pick_highest_priority_pkg(|_p, _r| (0, Reverse(0)))
493                    .is_none()
494            );
495
496            let solution: BTreeMap<String, usize> = state
497                .partial_solution
498                .extract_solution()
499                .map(|(p, v)| (state.package_store[p].clone(), v))
500                .collect();
501            let expected = BTreeMap::from([("root".to_string(), 0), ("foo".to_string(), 1)]);
502
503            assert_eq!(solution, expected, "{case:?}");
504        }
505    }
506}
pubgrub/internal/incompatibility.rs

pubgrub/internal/
incompatibility.rs
