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