1 // SPDX-License-Identifier: MPL-2.0
2 
3 use pubgrub::range::Range;
4 use pubgrub::solver::{resolve, OfflineDependencyProvider};
5 use pubgrub::type_aliases::Map;
6 use pubgrub::version::{NumberVersion, SemanticVersion};
7 
8 #[test]
9 /// https://github.com/dart-lang/pub/blob/master/doc/solver.md#no-conflicts
no_conflict()10 fn no_conflict() {
11     let mut dependency_provider = OfflineDependencyProvider::<&str, SemanticVersion>::new();
12     #[rustfmt::skip]
13         dependency_provider.add_dependencies(
14         "root", (1, 0, 0),
15         vec![("foo", Range::between((1, 0, 0), (2, 0, 0)))],
16     );
17     #[rustfmt::skip]
18         dependency_provider.add_dependencies(
19         "foo", (1, 0, 0),
20         vec![("bar", Range::between((1, 0, 0), (2, 0, 0)))],
21     );
22     dependency_provider.add_dependencies("bar", (1, 0, 0), vec![]);
23     dependency_provider.add_dependencies("bar", (2, 0, 0), vec![]);
24 
25     // Run the algorithm.
26     let computed_solution = resolve(&dependency_provider, "root", (1, 0, 0)).unwrap();
27 
28     // Solution.
29     let mut expected_solution = Map::default();
30     expected_solution.insert("root", (1, 0, 0).into());
31     expected_solution.insert("foo", (1, 0, 0).into());
32     expected_solution.insert("bar", (1, 0, 0).into());
33 
34     // Comparing the true solution with the one computed by the algorithm.
35     assert_eq!(expected_solution, computed_solution);
36 }
37 
38 #[test]
39 /// https://github.com/dart-lang/pub/blob/master/doc/solver.md#avoiding-conflict-during-decision-making
avoiding_conflict_during_decision_making()40 fn avoiding_conflict_during_decision_making() {
41     let mut dependency_provider = OfflineDependencyProvider::<&str, SemanticVersion>::new();
42     #[rustfmt::skip]
43         dependency_provider.add_dependencies(
44         "root", (1, 0, 0),
45         vec![
46             ("foo", Range::between((1, 0, 0), (2, 0, 0))),
47             ("bar", Range::between((1, 0, 0), (2, 0, 0))),
48         ],
49     );
50     #[rustfmt::skip]
51         dependency_provider.add_dependencies(
52         "foo", (1, 1, 0),
53         vec![("bar", Range::between((2, 0, 0), (3, 0, 0)))],
54     );
55     dependency_provider.add_dependencies("foo", (1, 0, 0), vec![]);
56     dependency_provider.add_dependencies("bar", (1, 0, 0), vec![]);
57     dependency_provider.add_dependencies("bar", (1, 1, 0), vec![]);
58     dependency_provider.add_dependencies("bar", (2, 0, 0), vec![]);
59 
60     // Run the algorithm.
61     let computed_solution = resolve(&dependency_provider, "root", (1, 0, 0)).unwrap();
62 
63     // Solution.
64     let mut expected_solution = Map::default();
65     expected_solution.insert("root", (1, 0, 0).into());
66     expected_solution.insert("foo", (1, 0, 0).into());
67     expected_solution.insert("bar", (1, 1, 0).into());
68 
69     // Comparing the true solution with the one computed by the algorithm.
70     assert_eq!(expected_solution, computed_solution);
71 }
72 
73 #[test]
74 /// https://github.com/dart-lang/pub/blob/master/doc/solver.md#performing-conflict-resolution
conflict_resolution()75 fn conflict_resolution() {
76     let mut dependency_provider = OfflineDependencyProvider::<&str, SemanticVersion>::new();
77     #[rustfmt::skip]
78         dependency_provider.add_dependencies(
79         "root", (1, 0, 0),
80         vec![("foo", Range::higher_than((1, 0, 0)))],
81     );
82     #[rustfmt::skip]
83         dependency_provider.add_dependencies(
84         "foo", (2, 0, 0),
85         vec![("bar", Range::between((1, 0, 0), (2, 0, 0)))],
86     );
87     dependency_provider.add_dependencies("foo", (1, 0, 0), vec![]);
88     #[rustfmt::skip]
89         dependency_provider.add_dependencies(
90         "bar", (1, 0, 0),
91         vec![("foo", Range::between((1, 0, 0), (2, 0, 0)))],
92     );
93 
94     // Run the algorithm.
95     let computed_solution = resolve(&dependency_provider, "root", (1, 0, 0)).unwrap();
96 
97     // Solution.
98     let mut expected_solution = Map::default();
99     expected_solution.insert("root", (1, 0, 0).into());
100     expected_solution.insert("foo", (1, 0, 0).into());
101 
102     // Comparing the true solution with the one computed by the algorithm.
103     assert_eq!(expected_solution, computed_solution);
104 }
105 
106 #[test]
107 /// https://github.com/dart-lang/pub/blob/master/doc/solver.md#conflict-resolution-with-a-partial-satisfier
conflict_with_partial_satisfier()108 fn conflict_with_partial_satisfier() {
109     let mut dependency_provider = OfflineDependencyProvider::<&str, SemanticVersion>::new();
110     #[rustfmt::skip]
111     // root 1.0.0 depends on foo ^1.0.0 and target ^2.0.0
112         dependency_provider.add_dependencies(
113         "root", (1, 0, 0),
114         vec![
115             ("foo", Range::between((1, 0, 0), (2, 0, 0))),
116             ("target", Range::between((2, 0, 0), (3, 0, 0))),
117         ],
118     );
119     #[rustfmt::skip]
120     // foo 1.1.0 depends on left ^1.0.0 and right ^1.0.0
121         dependency_provider.add_dependencies(
122         "foo", (1, 1, 0),
123         vec![
124             ("left", Range::between((1, 0, 0), (2, 0, 0))),
125             ("right", Range::between((1, 0, 0), (2, 0, 0))),
126         ],
127     );
128     dependency_provider.add_dependencies("foo", (1, 0, 0), vec![]);
129     #[rustfmt::skip]
130     // left 1.0.0 depends on shared >=1.0.0
131         dependency_provider.add_dependencies(
132         "left", (1, 0, 0),
133         vec![("shared", Range::higher_than((1, 0, 0)))],
134     );
135     #[rustfmt::skip]
136     // right 1.0.0 depends on shared <2.0.0
137         dependency_provider.add_dependencies(
138         "right", (1, 0, 0),
139         vec![("shared", Range::strictly_lower_than((2, 0, 0)))],
140     );
141     dependency_provider.add_dependencies("shared", (2, 0, 0), vec![]);
142     #[rustfmt::skip]
143     // shared 1.0.0 depends on target ^1.0.0
144         dependency_provider.add_dependencies(
145         "shared", (1, 0, 0),
146         vec![("target", Range::between((1, 0, 0), (2, 0, 0)))],
147     );
148     dependency_provider.add_dependencies("target", (2, 0, 0), vec![]);
149     dependency_provider.add_dependencies("target", (1, 0, 0), vec![]);
150 
151     // Run the algorithm.
152     let computed_solution = resolve(&dependency_provider, "root", (1, 0, 0)).unwrap();
153 
154     // Solution.
155     let mut expected_solution = Map::default();
156     expected_solution.insert("root", (1, 0, 0).into());
157     expected_solution.insert("foo", (1, 0, 0).into());
158     expected_solution.insert("target", (2, 0, 0).into());
159 
160     // Comparing the true solution with the one computed by the algorithm.
161     assert_eq!(expected_solution, computed_solution);
162 }
163 
164 #[test]
165 /// a0 dep on b and c
166 /// b0 dep on d0
167 /// b1 dep on d1 (not existing)
168 /// c0 has no dep
169 /// c1 dep on d2 (not existing)
170 /// d0 has no dep
171 ///
172 /// Solution: a0, b0, c0, d0
double_choices()173 fn double_choices() {
174     let mut dependency_provider = OfflineDependencyProvider::<&str, NumberVersion>::new();
175     dependency_provider.add_dependencies("a", 0, vec![("b", Range::any()), ("c", Range::any())]);
176     dependency_provider.add_dependencies("b", 0, vec![("d", Range::exact(0))]);
177     dependency_provider.add_dependencies("b", 1, vec![("d", Range::exact(1))]);
178     dependency_provider.add_dependencies("c", 0, vec![]);
179     dependency_provider.add_dependencies("c", 1, vec![("d", Range::exact(2))]);
180     dependency_provider.add_dependencies("d", 0, vec![]);
181 
182     // Solution.
183     let mut expected_solution = Map::default();
184     expected_solution.insert("a", 0.into());
185     expected_solution.insert("b", 0.into());
186     expected_solution.insert("c", 0.into());
187     expected_solution.insert("d", 0.into());
188 
189     // Run the algorithm.
190     let computed_solution = resolve(&dependency_provider, "a", 0).unwrap();
191     assert_eq!(expected_solution, computed_solution);
192 }
193