Commit | Line | Data |
---|---|---|
1479465f GJ |
1 | /* |
2 | * dselect - Debian package maintenance user interface | |
3 | * pkgdepcon.cc - dependency and conflict resolution | |
4 | * | |
5 | * Copyright © 1995 Ian Jackson <ijackson@chiark.greenend.org.uk> | |
6 | * Copyright © 2008-2014 Guillem Jover <guillem@debian.org> | |
7 | * | |
8 | * This is free software; you can redistribute it and/or modify | |
9 | * it under the terms of the GNU General Public License as published by | |
10 | * the Free Software Foundation; either version 2 of the License, or | |
11 | * (at your option) any later version. | |
12 | * | |
13 | * This is distributed in the hope that it will be useful, | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | * GNU General Public License for more details. | |
17 | * | |
18 | * You should have received a copy of the GNU General Public License | |
19 | * along with this program. If not, see <https://www.gnu.org/licenses/>. | |
20 | */ | |
21 | ||
22 | #include <config.h> | |
23 | #include <compat.h> | |
24 | ||
25 | #include <assert.h> | |
26 | #include <string.h> | |
27 | #include <stdio.h> | |
28 | ||
29 | #include <dpkg/dpkg.h> | |
30 | #include <dpkg/dpkg-db.h> | |
31 | ||
32 | #include "dselect.h" | |
33 | #include "pkglist.h" | |
34 | ||
35 | bool | |
36 | packagelist::useavailable(pkginfo *pkg) | |
37 | { | |
38 | if (pkg->clientdata && | |
39 | pkg->clientdata->selected == PKG_WANT_INSTALL && | |
40 | pkg_is_informative(pkg, &pkg->available) && | |
41 | (!(pkg->status == PKG_STAT_INSTALLED || | |
42 | pkg->status == PKG_STAT_TRIGGERSAWAITED || | |
43 | pkg->status == PKG_STAT_TRIGGERSPENDING) || | |
44 | dpkg_version_compare(&pkg->available.version, | |
45 | &pkg->installed.version) > 0)) | |
46 | return true; | |
47 | else | |
48 | return false; | |
49 | } | |
50 | ||
51 | pkgbin * | |
52 | packagelist::find_pkgbin(pkginfo *pkg) | |
53 | { | |
54 | pkgbin *r; | |
55 | r= useavailable(pkg) ? &pkg->available : &pkg->installed; | |
56 | debug(dbg_general, "packagelist[%p]::find_pkgbin(%s) useavailable=%d", | |
57 | this, pkgbin_name(pkg, r, pnaw_always), useavailable(pkg)); | |
58 | ||
59 | return r; | |
60 | } | |
61 | ||
62 | int packagelist::checkdependers(pkginfo *pkg, int changemade) { | |
63 | struct deppossi *possi; | |
64 | ||
65 | for (possi = pkg->set->depended.available; possi; possi = possi->rev_next) { | |
66 | if (!useavailable(possi->up->up)) | |
67 | continue; | |
68 | changemade = max(changemade, resolvedepcon(possi->up)); | |
69 | } | |
70 | for (possi = pkg->set->depended.installed; possi; possi = possi->rev_next) { | |
71 | if (useavailable(possi->up->up)) | |
72 | continue; | |
73 | changemade = max(changemade, resolvedepcon(possi->up)); | |
74 | } | |
75 | return changemade; | |
76 | } | |
77 | ||
78 | int packagelist::resolvesuggest() { | |
79 | // We continually go around looking for things to change, but we may | |
80 | // only change the ‘suggested’ value if we also increase the ‘priority’ | |
81 | // Return 2 if we made a change due to a Recommended, Depends or Conflicts, | |
82 | // or 1 if we offered or made a change because of an Optional line. | |
83 | debug(dbg_general, "packagelist[%p]::resolvesuggest()", this); | |
84 | int changemade, maxchangemade; | |
85 | maxchangemade= 0; | |
86 | for (;;) { | |
87 | changemade= 0; | |
88 | int index; | |
89 | for (index=0; index<nitems; index++) { | |
90 | if (!table[index]->pkg->set->name) | |
91 | continue; | |
92 | debug(dbg_depcon, "packagelist[%p]::resolvesuggest() loop[%i] %s / %d", | |
93 | this, index, pkg_name(table[index]->pkg, pnaw_always), changemade); | |
94 | dependency *depends; | |
95 | for (depends = find_pkgbin(table[index]->pkg)->depends; | |
96 | depends; | |
97 | depends= depends->next) { | |
98 | changemade = max(changemade, resolvedepcon(depends)); | |
99 | } | |
100 | changemade= checkdependers(table[index]->pkg,changemade); | |
101 | for (depends = find_pkgbin(table[index]->pkg)->depends; | |
102 | depends; | |
103 | depends= depends->next) { | |
104 | if (depends->type != dep_provides) continue; | |
105 | changemade = checkdependers(&depends->list->ed->pkg, changemade); | |
106 | } | |
107 | debug(dbg_depcon, "packagelist[%p]::resolvesuggest() loop[%i] %s / -> %d", | |
108 | this, index, pkg_name(table[index]->pkg, pnaw_always), changemade); | |
109 | } | |
110 | if (!changemade) break; | |
111 | maxchangemade = max(maxchangemade, changemade); | |
112 | } | |
113 | debug(dbg_general, "packagelist[%p]::resolvesuggest() done; maxchangemade=%d", | |
114 | this, maxchangemade); | |
115 | return maxchangemade; | |
116 | } | |
117 | ||
118 | static bool | |
119 | dep_update_best_to_change_stop(perpackagestate *& best, pkginfo *trythis) | |
120 | { | |
121 | // There's no point trying to select a pure virtual package. | |
122 | if (!trythis->clientdata) | |
123 | return false; | |
124 | ||
125 | debug(dbg_depcon, "update_best_to_change(best=%s{%d}, test=%s{%d});", | |
126 | best ? pkg_name(best->pkg, pnaw_always) : "", | |
127 | best ? (int)best->spriority : -1, | |
128 | trythis->set->name, trythis->clientdata->spriority); | |
129 | ||
130 | // If the problem is caused by us deselecting one of these packages | |
131 | // we should not try to select another one instead. | |
132 | if (trythis->clientdata->spriority == sp_deselecting) | |
133 | return true; | |
134 | ||
135 | // If we haven't found anything yet then this is our best so far. | |
136 | if (!best) goto yes; | |
137 | ||
138 | // If only one of the packages is available, use that one | |
139 | if (!pkg_is_informative(trythis, &trythis->available) && | |
140 | pkg_is_informative(best->pkg, &best->pkg->available)) | |
141 | return false; | |
142 | if (pkg_is_informative(trythis, &trythis->available) && | |
143 | !pkg_is_informative(best->pkg, &best->pkg->available)) | |
144 | goto yes; | |
145 | ||
146 | // Select the package with the lowest priority (ie, the one of whom | |
147 | // we were least sure we wanted it deselected). | |
148 | if (trythis->clientdata->spriority > best->spriority) | |
149 | return false; | |
150 | if (trythis->clientdata->spriority < best->spriority) goto yes; | |
151 | ||
152 | // Pick the package with the must fundamental recommendation level. | |
153 | if (trythis->priority > best->pkg->priority) | |
154 | return false; | |
155 | if (trythis->priority < best->pkg->priority) goto yes; | |
156 | ||
157 | // If we're still unsure we'll change the first one in the list. | |
158 | return false; | |
159 | ||
160 | yes: | |
161 | debug(dbg_depcon, "update_best_to_change(); yes"); | |
162 | ||
163 | best = trythis->clientdata; | |
164 | return false; | |
165 | } | |
166 | ||
167 | int | |
168 | packagelist::deselect_one_of(pkginfo *per, pkginfo *ped, dependency *dep) | |
169 | { | |
170 | perpackagestate *er= per->clientdata; | |
171 | perpackagestate *ed= ped->clientdata; | |
172 | ||
173 | if (!er || !would_like_to_install(er->selected,per) || | |
174 | !ed || !would_like_to_install(ed->selected,ped)) return 0; | |
175 | ||
176 | add(dep, dp_must); | |
177 | ||
178 | er= per->clientdata; // these can be changed by add | |
179 | ed= ped->clientdata; | |
180 | ||
181 | debug(dbg_depcon, | |
182 | "packagelist[%p]::deselect_one_of(): er %s{%d} ed %s{%d} [%p]", | |
183 | this, pkg_name(er->pkg, pnaw_always), er->spriority, | |
184 | pkg_name(ed->pkg, pnaw_always), ed->spriority, dep); | |
185 | ||
186 | perpackagestate *best; | |
187 | ||
188 | // Try not keep packages needing reinstallation. | |
189 | if (per->eflag & PKG_EFLAG_REINSTREQ) | |
190 | best = ed; | |
191 | else if (ped->eflag & PKG_EFLAG_REINSTREQ) | |
192 | best = er; | |
193 | else if (er->spriority < ed->spriority) best= er; // We'd rather change the | |
194 | else if (er->spriority > ed->spriority) best= ed; // one with the lowest priority. | |
195 | // ... failing that the one with the highest priority | |
196 | else if (er->pkg->priority > ed->pkg->priority) | |
197 | best = er; | |
198 | else if (er->pkg->priority < ed->pkg->priority) | |
199 | best = ed; | |
200 | else best= ed; // ... failing that, the second | |
201 | ||
202 | debug(dbg_depcon, "packagelist[%p]::deselect_one_of(): best %s{%d}", | |
203 | this, pkg_name(best->pkg, pnaw_always), best->spriority); | |
204 | ||
205 | if (best->spriority >= sp_deselecting) return 0; | |
206 | best->suggested= | |
207 | best->pkg->status == PKG_STAT_NOTINSTALLED | |
208 | ? PKG_WANT_PURGE : PKG_WANT_DEINSTALL; // FIXME: configurable. | |
209 | best->selected= best->suggested; | |
210 | best->spriority= sp_deselecting; | |
211 | ||
212 | return 2; | |
213 | } | |
214 | ||
215 | int packagelist::resolvedepcon(dependency *depends) { | |
216 | perpackagestate *best, *fixbyupgrade; | |
217 | deppossi *possi, *provider; | |
218 | bool foundany; | |
219 | int rc; | |
220 | ||
221 | if (debug_has_flag(dbg_depcon)) { | |
222 | varbuf pkg_names; | |
223 | ||
224 | for (possi = depends->list; possi; possi = possi->next) { | |
225 | pkg_names(' '); | |
226 | pkg_names(possi->ed->name); | |
227 | } | |
228 | ||
229 | debug(dbg_depcon, | |
230 | "packagelist[%p]::resolvedepcon([%p] %s --%s-->%s); (ing)->want=%s", | |
231 | this, depends, pkg_name(depends->up, pnaw_always), | |
232 | relatestrings[depends->type], | |
233 | pkg_names.string(), depends->up->clientdata ? | |
234 | wantstrings[depends->up->clientdata->suggested] : "(no clientdata)"); | |
235 | } | |
236 | ||
237 | if (!depends->up->clientdata) return 0; | |
238 | ||
239 | switch (depends->type) { | |
240 | ||
241 | case dep_provides: | |
242 | case dep_replaces: | |
243 | return 0; | |
244 | ||
245 | case dep_enhances: | |
246 | case dep_suggests: | |
247 | case dep_recommends: | |
248 | case dep_depends: | |
249 | case dep_predepends: | |
250 | if (would_like_to_install(depends->up->clientdata->selected,depends->up) <= 0) | |
251 | return 0; | |
252 | ||
253 | fixbyupgrade = nullptr; | |
254 | ||
255 | possi = depends->list; | |
256 | while (possi && !deppossatisfied(possi, &fixbyupgrade)) | |
257 | possi = possi->next; | |
258 | debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): depends found %s", | |
259 | this, depends, possi ? possi->ed->name : "[none]"); | |
260 | if (possi) return 0; | |
261 | ||
262 | // Ensures all in the recursive list; adds info strings; ups priorities | |
263 | switch (depends->type) { | |
264 | case dep_enhances: | |
265 | case dep_suggests: | |
266 | rc = add(depends, dp_may); | |
267 | return rc; | |
268 | case dep_recommends: | |
269 | rc = add(depends, dp_should); | |
270 | break; | |
271 | default: | |
272 | rc = add(depends, dp_must); | |
273 | } | |
274 | ||
275 | if (fixbyupgrade) { | |
276 | debug(dbg_depcon, | |
277 | "packagelist[%p]::resolvedepcon([%p]): fixbyupgrade %s", | |
278 | this, depends, pkg_name(fixbyupgrade->pkg, pnaw_always)); | |
279 | best= fixbyupgrade; | |
280 | } else { | |
281 | best = nullptr; | |
282 | for (possi= depends->list; | |
283 | possi; | |
284 | possi= possi->next) { | |
285 | foundany = false; | |
286 | if (possi->ed->pkg.clientdata) | |
287 | foundany = true; | |
288 | if (dep_update_best_to_change_stop(best, &possi->ed->pkg)) | |
289 | goto mustdeselect; | |
290 | for (provider = possi->ed->depended.available; | |
291 | provider; | |
292 | provider = provider->rev_next) { | |
293 | if (provider->up->type != dep_provides) continue; | |
294 | if (provider->up->up->clientdata) | |
295 | foundany = true; | |
296 | if (dep_update_best_to_change_stop(best, provider->up->up)) goto mustdeselect; | |
297 | } | |
298 | if (!foundany) addunavailable(possi); | |
299 | } | |
300 | if (!best) { | |
301 | debug(dbg_depcon, | |
302 | "packagelist[%p]::resolvedepcon([%p]): mustdeselect nobest", | |
303 | this, depends); | |
304 | return rc; | |
305 | } | |
306 | } | |
307 | debug(dbg_depcon, | |
308 | "packagelist[%p]::resolvedepcon([%p]): select best=%s{%d}", | |
309 | this, depends, pkg_name(best->pkg, pnaw_always), best->spriority); | |
310 | if (best->spriority >= sp_selecting) | |
311 | return rc; | |
312 | /* Always select depends. Only select recommends if we got here because | |
313 | * of a manually-initiated install request. */ | |
314 | if (depends->type != dep_recommends || manual_install) { | |
315 | best->selected = best->suggested = PKG_WANT_INSTALL; | |
316 | best->spriority= sp_selecting; | |
317 | } | |
318 | return rc ? 2 : 0; | |
319 | ||
320 | mustdeselect: | |
321 | best= depends->up->clientdata; | |
322 | debug(dbg_depcon, | |
323 | "packagelist[%p]::resolvedepcon([%p]): mustdeselect best=%s{%d}", | |
324 | this, depends, pkg_name(best->pkg, pnaw_always), best->spriority); | |
325 | ||
326 | if (best->spriority >= sp_deselecting) | |
327 | return rc; | |
328 | /* Always remove depends, but never remove recommends. */ | |
329 | if (depends->type != dep_recommends) { | |
330 | best->selected= best->suggested= | |
331 | best->pkg->status == PKG_STAT_NOTINSTALLED | |
332 | ? PKG_WANT_PURGE : PKG_WANT_DEINSTALL; // FIXME: configurable | |
333 | best->spriority= sp_deselecting; | |
334 | } | |
335 | return rc ? 2 : 0; | |
336 | ||
337 | case dep_conflicts: | |
338 | case dep_breaks: | |
339 | debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): conflict", | |
340 | this, depends); | |
341 | ||
342 | if (would_like_to_install(depends->up->clientdata->selected,depends->up) == 0) | |
343 | return 0; | |
344 | ||
345 | debug(dbg_depcon, | |
346 | "packagelist[%p]::resolvedepcon([%p]): conflict installing 1", | |
347 | this, depends); | |
348 | ||
349 | if (!deppossatisfied(depends->list, nullptr)) | |
350 | return 0; | |
351 | ||
352 | debug(dbg_depcon, | |
353 | "packagelist[%p]::resolvedepcon([%p]): conflict satisfied - ouch", | |
354 | this, depends); | |
355 | ||
356 | if (depends->up->set != depends->list->ed) { | |
357 | rc = deselect_one_of(depends->up, &depends->list->ed->pkg, depends); | |
358 | if (rc) | |
359 | return rc; | |
360 | } | |
361 | for (provider = depends->list->ed->depended.available; | |
362 | provider; | |
363 | provider = provider->rev_next) { | |
364 | if (provider->up->type != dep_provides) continue; | |
365 | if (provider->up->up == depends->up) continue; // conflicts & provides same thing | |
366 | rc = deselect_one_of(depends->up, provider->up->up, depends); | |
367 | if (rc) | |
368 | return rc; | |
369 | } | |
370 | debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): no desel", | |
371 | this, depends); | |
372 | return 0; | |
373 | ||
374 | default: | |
375 | internerr("unknown deptype %d", depends->type); | |
376 | } | |
377 | /* never reached, make gcc happy */ | |
378 | return 1; | |
379 | } | |
380 | ||
381 | bool | |
382 | packagelist::deppossatisfied(deppossi *possi, perpackagestate **fixbyupgrade) | |
383 | { | |
384 | // ‘satisfied’ here for Conflicts and Breaks means that the | |
385 | // restriction is violated ie that the target package is wanted | |
386 | int would; | |
387 | pkgwant want = PKG_WANT_PURGE; | |
388 | ||
389 | if (possi->ed->pkg.clientdata) { | |
390 | want = possi->ed->pkg.clientdata->selected; | |
391 | would = would_like_to_install(want, &possi->ed->pkg); | |
392 | } else { | |
393 | would= 0; | |
394 | } | |
395 | ||
396 | if ((possi->up->type == dep_conflicts || possi->up->type == dep_breaks) | |
397 | ? possi->up->up->set != possi->ed && would != 0 | |
398 | : would > 0) { | |
399 | // If it's to be installed or left installed, then either it's of | |
400 | // the right version, and therefore OK, or a version must have | |
401 | // been specified, in which case we don't need to look at the rest | |
402 | // anyway. | |
403 | if (useavailable(&possi->ed->pkg)) { | |
404 | assert(want == PKG_WANT_INSTALL); | |
405 | return versionsatisfied(&possi->ed->pkg.available, possi); | |
406 | } else { | |
407 | if (versionsatisfied(&possi->ed->pkg.installed, possi)) | |
408 | return true; | |
409 | if (want == PKG_WANT_HOLD && fixbyupgrade && !*fixbyupgrade && | |
410 | versionsatisfied(&possi->ed->pkg.available, possi) && | |
411 | dpkg_version_compare(&possi->ed->pkg.available.version, | |
412 | &possi->ed->pkg.installed.version) > 1) | |
413 | *fixbyupgrade = possi->ed->pkg.clientdata; | |
414 | return false; | |
415 | } | |
416 | } | |
417 | ||
418 | deppossi *provider; | |
419 | ||
420 | for (provider = possi->ed->depended.installed; | |
421 | provider; | |
422 | provider = provider->rev_next) { | |
423 | if (provider->up->type == dep_provides && | |
424 | ((possi->up->type != dep_conflicts && possi->up->type != dep_breaks) || | |
425 | provider->up->up->set != possi->up->up->set) && | |
426 | provider->up->up->clientdata && | |
427 | !useavailable(provider->up->up) && | |
428 | would_like_to_install(provider->up->up->clientdata->selected, | |
429 | provider->up->up) && | |
430 | pkg_virtual_deppossi_satisfied(possi, provider)) | |
431 | return true; | |
432 | } | |
433 | for (provider = possi->ed->depended.available; | |
434 | provider; | |
435 | provider = provider->rev_next) { | |
436 | if (provider->up->type != dep_provides || | |
437 | ((possi->up->type == dep_conflicts || possi->up->type == dep_breaks) && | |
438 | provider->up->up->set == possi->up->up->set) || | |
439 | !provider->up->up->clientdata || | |
440 | !would_like_to_install(provider->up->up->clientdata->selected, | |
441 | provider->up->up) || | |
442 | !pkg_virtual_deppossi_satisfied(possi, provider)) | |
443 | continue; | |
444 | if (useavailable(provider->up->up)) | |
445 | return true; | |
446 | if (fixbyupgrade && !*fixbyupgrade && | |
447 | (!(provider->up->up->status == PKG_STAT_INSTALLED || | |
448 | provider->up->up->status == PKG_STAT_TRIGGERSPENDING || | |
449 | provider->up->up->status == PKG_STAT_TRIGGERSAWAITED) || | |
450 | dpkg_version_compare(&provider->up->up->available.version, | |
451 | &provider->up->up->installed.version) > 1)) | |
452 | *fixbyupgrade = provider->up->up->clientdata; | |
453 | } | |
454 | return false; | |
455 | } |