2 * dselect - Debian package maintenance user interface
3 * pkgdepcon.cc - dependency and conflict resolution
5 * Copyright © 1995 Ian Jackson <ijackson@chiark.greenend.org.uk>
6 * Copyright © 2008-2014 Guillem Jover <guillem@debian.org>
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.
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.
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/>.
28 #include <dpkg/dpkg.h>
29 #include <dpkg/dpkg-db.h>
35 packagelist::useavailable(pkginfo
*pkg
)
37 if (pkg
->clientdata
&&
38 pkg
->clientdata
->selected
== PKG_WANT_INSTALL
&&
39 pkg_is_informative(pkg
, &pkg
->available
) &&
40 (!(pkg
->status
== PKG_STAT_INSTALLED
||
41 pkg
->status
== PKG_STAT_TRIGGERSAWAITED
||
42 pkg
->status
== PKG_STAT_TRIGGERSPENDING
) ||
43 dpkg_version_compare(&pkg
->available
.version
,
44 &pkg
->installed
.version
) > 0))
51 packagelist::find_pkgbin(pkginfo
*pkg
)
55 pkgbin
= useavailable(pkg
) ? &pkg
->available
: &pkg
->installed
;
56 debug(dbg_general
, "packagelist[%p]::find_pkgbin(%s) useavailable=%d",
57 this, pkgbin_name(pkg
, pkgbin
, pnaw_always
), useavailable(pkg
));
62 int packagelist::checkdependers(pkginfo
*pkg
, int changemade
) {
63 struct deppossi
*possi
;
65 for (possi
= pkg
->set
->depended
.available
; possi
; possi
= possi
->rev_next
) {
66 if (!useavailable(possi
->up
->up
))
68 changemade
= max(changemade
, resolvedepcon(possi
->up
));
70 for (possi
= pkg
->set
->depended
.installed
; possi
; possi
= possi
->rev_next
) {
71 if (useavailable(possi
->up
->up
))
73 changemade
= max(changemade
, resolvedepcon(possi
->up
));
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
;
89 for (index
=0; index
<nitems
; index
++) {
90 if (!table
[index
]->pkg
->set
->name
)
92 debug(dbg_depcon
, "packagelist[%p]::resolvesuggest() loop[%i] %s / %d",
93 this, index
, pkg_name(table
[index
]->pkg
, pnaw_always
), changemade
);
95 for (depends
= find_pkgbin(table
[index
]->pkg
)->depends
;
97 depends
= depends
->next
) {
98 changemade
= max(changemade
, resolvedepcon(depends
));
100 changemade
= checkdependers(table
[index
]->pkg
,changemade
);
101 for (depends
= find_pkgbin(table
[index
]->pkg
)->depends
;
103 depends
= depends
->next
) {
104 if (depends
->type
!= dep_provides
) continue;
105 changemade
= checkdependers(&depends
->list
->ed
->pkg
, changemade
);
107 debug(dbg_depcon
, "packagelist[%p]::resolvesuggest() loop[%i] %s / -> %d",
108 this, index
, pkg_name(table
[index
]->pkg
, pnaw_always
), changemade
);
110 if (!changemade
) break;
111 maxchangemade
= max(maxchangemade
, changemade
);
113 debug(dbg_general
, "packagelist[%p]::resolvesuggest() done; maxchangemade=%d",
114 this, maxchangemade
);
115 return maxchangemade
;
119 dep_update_best_to_change_stop(perpackagestate
*& best
, pkginfo
*trythis
)
121 // There's no point trying to select a pure virtual package.
122 if (!trythis
->clientdata
)
125 debug(dbg_depcon
, "update_best_to_change(best=%s{%d}, test=%s{%d});",
126 best
? pkg_name(best
->pkg
, pnaw_always
) : "",
127 best
? best
->spriority
: -1,
128 trythis
->set
->name
, trythis
->clientdata
->spriority
);
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
)
135 // If we haven't found anything yet then this is our best so far.
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
))
142 if (pkg_is_informative(trythis
, &trythis
->available
) &&
143 !pkg_is_informative(best
->pkg
, &best
->pkg
->available
))
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
)
150 if (trythis
->clientdata
->spriority
< best
->spriority
) goto yes
;
152 // Pick the package with the must fundamental recommendation level.
153 if (trythis
->priority
> best
->pkg
->priority
)
155 if (trythis
->priority
< best
->pkg
->priority
) goto yes
;
157 // If we're still unsure we'll change the first one in the list.
161 debug(dbg_depcon
, "update_best_to_change(); yes");
163 best
= trythis
->clientdata
;
168 packagelist::deselect_one_of(pkginfo
*per
, pkginfo
*ped
, dependency
*dep
)
170 perpackagestate
*er
= per
->clientdata
;
171 perpackagestate
*ed
= ped
->clientdata
;
173 if (!er
|| !would_like_to_install(er
->selected
,per
) ||
174 !ed
|| !would_like_to_install(ed
->selected
,ped
)) return 0;
178 er
= per
->clientdata
; // these can be changed by add
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
);
186 perpackagestate
*best
;
188 // Try not keep packages needing reinstallation.
189 if (per
->eflag
& PKG_EFLAG_REINSTREQ
)
191 else if (ped
->eflag
& PKG_EFLAG_REINSTREQ
)
193 // We'd rather change the one with the lowest priority.
194 else if (er
->spriority
> ed
->spriority
)
196 else if (er
->spriority
< ed
->spriority
)
198 // ... failing that the one with the highest priority.
199 else if (er
->pkg
->priority
< ed
->pkg
->priority
)
201 else if (er
->pkg
->priority
> ed
->pkg
->priority
)
203 // ... failing that, the second.
207 debug(dbg_depcon
, "packagelist[%p]::deselect_one_of(): best %s{%d}",
208 this, pkg_name(best
->pkg
, pnaw_always
), best
->spriority
);
210 if (best
->spriority
>= sp_deselecting
) return 0;
212 best
->pkg
->status
== PKG_STAT_NOTINSTALLED
213 ? PKG_WANT_PURGE
: PKG_WANT_DEINSTALL
; // FIXME: configurable.
214 best
->selected
= best
->suggested
;
215 best
->spriority
= sp_deselecting
;
220 int packagelist::resolvedepcon(dependency
*depends
) {
221 perpackagestate
*best
, *fixbyupgrade
;
222 deppossi
*possi
, *provider
;
226 if (debug_has_flag(dbg_depcon
)) {
229 for (possi
= depends
->list
; possi
; possi
= possi
->next
) {
231 pkg_names(possi
->ed
->name
);
235 "packagelist[%p]::resolvedepcon([%p] %s --%s-->%s); (ing)->want=%s",
236 this, depends
, pkg_name(depends
->up
, pnaw_always
),
237 relatestrings
[depends
->type
],
238 pkg_names
.string(), depends
->up
->clientdata
?
239 wantstrings
[depends
->up
->clientdata
->suggested
] : "(no clientdata)");
242 if (!depends
->up
->clientdata
) return 0;
244 switch (depends
->type
) {
255 if (would_like_to_install(depends
->up
->clientdata
->selected
,depends
->up
) <= 0)
258 fixbyupgrade
= nullptr;
260 possi
= depends
->list
;
261 while (possi
&& !deppossatisfied(possi
, &fixbyupgrade
))
263 debug(dbg_depcon
, "packagelist[%p]::resolvedepcon([%p]): depends found %s",
264 this, depends
, possi
? possi
->ed
->name
: "[none]");
267 // Ensures all in the recursive list; adds info strings; ups priorities
268 switch (depends
->type
) {
271 rc
= add(depends
, dp_may
);
274 rc
= add(depends
, dp_should
);
277 rc
= add(depends
, dp_must
);
282 "packagelist[%p]::resolvedepcon([%p]): fixbyupgrade %s",
283 this, depends
, pkg_name(fixbyupgrade
->pkg
, pnaw_always
));
287 for (possi
= depends
->list
;
289 possi
= possi
->next
) {
291 if (possi
->ed
->pkg
.clientdata
)
293 if (dep_update_best_to_change_stop(best
, &possi
->ed
->pkg
))
295 for (provider
= possi
->ed
->depended
.available
;
297 provider
= provider
->rev_next
) {
298 if (provider
->up
->type
!= dep_provides
) continue;
299 if (provider
->up
->up
->clientdata
)
301 if (dep_update_best_to_change_stop(best
, provider
->up
->up
)) goto mustdeselect
;
303 if (!foundany
) addunavailable(possi
);
307 "packagelist[%p]::resolvedepcon([%p]): mustdeselect nobest",
313 "packagelist[%p]::resolvedepcon([%p]): select best=%s{%d}",
314 this, depends
, pkg_name(best
->pkg
, pnaw_always
), best
->spriority
);
315 if (best
->spriority
>= sp_selecting
)
317 /* Always select depends. Only select recommends if we got here because
318 * of a manually-initiated install request. */
319 if (depends
->type
!= dep_recommends
|| manual_install
) {
320 best
->selected
= best
->suggested
= PKG_WANT_INSTALL
;
321 best
->spriority
= sp_selecting
;
326 best
= depends
->up
->clientdata
;
328 "packagelist[%p]::resolvedepcon([%p]): mustdeselect best=%s{%d}",
329 this, depends
, pkg_name(best
->pkg
, pnaw_always
), best
->spriority
);
331 if (best
->spriority
>= sp_deselecting
)
333 /* Always remove depends, but never remove recommends. */
334 if (depends
->type
!= dep_recommends
) {
335 best
->selected
= best
->suggested
=
336 best
->pkg
->status
== PKG_STAT_NOTINSTALLED
337 ? PKG_WANT_PURGE
: PKG_WANT_DEINSTALL
; // FIXME: configurable
338 best
->spriority
= sp_deselecting
;
344 debug(dbg_depcon
, "packagelist[%p]::resolvedepcon([%p]): conflict",
347 if (would_like_to_install(depends
->up
->clientdata
->selected
,depends
->up
) == 0)
351 "packagelist[%p]::resolvedepcon([%p]): conflict installing 1",
354 if (!deppossatisfied(depends
->list
, nullptr))
358 "packagelist[%p]::resolvedepcon([%p]): conflict satisfied - ouch",
361 if (depends
->up
->set
!= depends
->list
->ed
) {
362 rc
= deselect_one_of(depends
->up
, &depends
->list
->ed
->pkg
, depends
);
366 for (provider
= depends
->list
->ed
->depended
.available
;
368 provider
= provider
->rev_next
) {
369 if (provider
->up
->type
!= dep_provides
) continue;
370 if (provider
->up
->up
== depends
->up
) continue; // conflicts & provides same thing
371 rc
= deselect_one_of(depends
->up
, provider
->up
->up
, depends
);
375 debug(dbg_depcon
, "packagelist[%p]::resolvedepcon([%p]): no desel",
380 internerr("unknown deptype %d", depends
->type
);
382 /* never reached, make gcc happy */
387 packagelist::deppossatisfied(deppossi
*possi
, perpackagestate
**fixbyupgrade
)
389 // ‘satisfied’ here for Conflicts and Breaks means that the
390 // restriction is violated ie that the target package is wanted
392 pkgwant want
= PKG_WANT_PURGE
;
394 if (possi
->ed
->pkg
.clientdata
) {
395 want
= possi
->ed
->pkg
.clientdata
->selected
;
396 would
= would_like_to_install(want
, &possi
->ed
->pkg
);
401 if ((possi
->up
->type
== dep_conflicts
|| possi
->up
->type
== dep_breaks
)
402 ? possi
->up
->up
->set
!= possi
->ed
&& would
!= 0
404 // If it's to be installed or left installed, then either it's of
405 // the right version, and therefore OK, or a version must have
406 // been specified, in which case we don't need to look at the rest
408 if (useavailable(&possi
->ed
->pkg
)) {
409 if (want
!= PKG_WANT_INSTALL
)
410 internerr("depossi package is not want-install, is %d", want
);
411 return versionsatisfied(&possi
->ed
->pkg
.available
, possi
);
413 if (versionsatisfied(&possi
->ed
->pkg
.installed
, possi
))
415 if (want
== PKG_WANT_HOLD
&& fixbyupgrade
&& !*fixbyupgrade
&&
416 versionsatisfied(&possi
->ed
->pkg
.available
, possi
) &&
417 dpkg_version_compare(&possi
->ed
->pkg
.available
.version
,
418 &possi
->ed
->pkg
.installed
.version
) > 1)
419 *fixbyupgrade
= possi
->ed
->pkg
.clientdata
;
426 for (provider
= possi
->ed
->depended
.installed
;
428 provider
= provider
->rev_next
) {
429 if (provider
->up
->type
== dep_provides
&&
430 ((possi
->up
->type
!= dep_conflicts
&& possi
->up
->type
!= dep_breaks
) ||
431 provider
->up
->up
->set
!= possi
->up
->up
->set
) &&
432 provider
->up
->up
->clientdata
&&
433 !useavailable(provider
->up
->up
) &&
434 would_like_to_install(provider
->up
->up
->clientdata
->selected
,
436 pkg_virtual_deppossi_satisfied(possi
, provider
))
439 for (provider
= possi
->ed
->depended
.available
;
441 provider
= provider
->rev_next
) {
442 if (provider
->up
->type
!= dep_provides
||
443 ((possi
->up
->type
== dep_conflicts
|| possi
->up
->type
== dep_breaks
) &&
444 provider
->up
->up
->set
== possi
->up
->up
->set
) ||
445 !provider
->up
->up
->clientdata
||
446 !would_like_to_install(provider
->up
->up
->clientdata
->selected
,
448 !pkg_virtual_deppossi_satisfied(possi
, provider
))
450 if (useavailable(provider
->up
->up
))
452 if (fixbyupgrade
&& !*fixbyupgrade
&&
453 (!(provider
->up
->up
->status
== PKG_STAT_INSTALLED
||
454 provider
->up
->up
->status
== PKG_STAT_TRIGGERSPENDING
||
455 provider
->up
->up
->status
== PKG_STAT_TRIGGERSAWAITED
) ||
456 dpkg_version_compare(&provider
->up
->up
->available
.version
,
457 &provider
->up
->up
->installed
.version
) > 1))
458 *fixbyupgrade
= provider
->up
->up
->clientdata
;