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/>.
29 #include <dpkg/dpkg.h>
30 #include <dpkg/dpkg-db.h>
36 packagelist
::useavailable(pkginfo
*pkg
)
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))
52 packagelist
::find_pkgbin(pkginfo
*pkg
)
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
));
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 ?
(int)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 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
)
198 else if (er
->pkg
->priority
< ed
->pkg
->priority
)
200 else best
= ed
; // ... failing that, the second
202 debug(dbg_depcon
, "packagelist[%p]::deselect_one_of(): best %s{%d}",
203 this, pkg_name(best
->pkg
, pnaw_always
), best
->spriority
);
205 if (best
->spriority
>= sp_deselecting
) return 0;
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
;
215 int packagelist
::resolvedepcon(dependency
*depends
) {
216 perpackagestate
*best
, *fixbyupgrade
;
217 deppossi
*possi
, *provider
;
221 if (debug_has_flag(dbg_depcon
)) {
224 for (possi
= depends
->list
; possi
; possi
= possi
->next
) {
226 pkg_names(possi
->ed
->name
);
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)");
237 if (!depends
->up
->clientdata
) return 0;
239 switch (depends
->type
) {
250 if (would_like_to_install(depends
->up
->clientdata
->selected
,depends
->up
) <= 0)
253 fixbyupgrade
= nullptr;
255 possi
= depends
->list
;
256 while (possi
&& !deppossatisfied(possi
, &fixbyupgrade
))
258 debug(dbg_depcon
, "packagelist[%p]::resolvedepcon([%p]): depends found %s",
259 this, depends
, possi ? possi
->ed
->name
: "[none]");
262 // Ensures all in the recursive list; adds info strings; ups priorities
263 switch (depends
->type
) {
266 rc
= add(depends
, dp_may
);
269 rc
= add(depends
, dp_should
);
272 rc
= add(depends
, dp_must
);
277 "packagelist[%p]::resolvedepcon([%p]): fixbyupgrade %s",
278 this, depends
, pkg_name(fixbyupgrade
->pkg
, pnaw_always
));
282 for (possi
= depends
->list
;
284 possi
= possi
->next
) {
286 if (possi
->ed
->pkg
.clientdata
)
288 if (dep_update_best_to_change_stop(best
, &possi
->ed
->pkg
))
290 for (provider
= possi
->ed
->depended
.available
;
292 provider
= provider
->rev_next
) {
293 if (provider
->up
->type
!= dep_provides
) continue;
294 if (provider
->up
->up
->clientdata
)
296 if (dep_update_best_to_change_stop(best
, provider
->up
->up
)) goto mustdeselect
;
298 if (!foundany
) addunavailable(possi
);
302 "packagelist[%p]::resolvedepcon([%p]): mustdeselect nobest",
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
)
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
;
321 best
= depends
->up
->clientdata
;
323 "packagelist[%p]::resolvedepcon([%p]): mustdeselect best=%s{%d}",
324 this, depends
, pkg_name(best
->pkg
, pnaw_always
), best
->spriority
);
326 if (best
->spriority
>= sp_deselecting
)
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
;
339 debug(dbg_depcon
, "packagelist[%p]::resolvedepcon([%p]): conflict",
342 if (would_like_to_install(depends
->up
->clientdata
->selected
,depends
->up
) == 0)
346 "packagelist[%p]::resolvedepcon([%p]): conflict installing 1",
349 if (!deppossatisfied(depends
->list
, nullptr))
353 "packagelist[%p]::resolvedepcon([%p]): conflict satisfied - ouch",
356 if (depends
->up
->set
!= depends
->list
->ed
) {
357 rc
= deselect_one_of(depends
->up
, &depends
->list
->ed
->pkg
, depends
);
361 for (provider
= depends
->list
->ed
->depended
.available
;
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
);
370 debug(dbg_depcon
, "packagelist[%p]::resolvedepcon([%p]): no desel",
375 internerr("unknown deptype %d", depends
->type
);
377 /* never reached, make gcc happy */
382 packagelist
::deppossatisfied(deppossi
*possi
, perpackagestate
**fixbyupgrade
)
384 // ‘satisfied’ here for Conflicts and Breaks means that the
385 // restriction is violated ie that the target package is wanted
387 pkgwant want
= PKG_WANT_PURGE
;
389 if (possi
->ed
->pkg
.clientdata
) {
390 want
= possi
->ed
->pkg
.clientdata
->selected
;
391 would
= would_like_to_install(want
, &possi
->ed
->pkg
);
396 if ((possi
->up
->type
== dep_conflicts
|| possi
->up
->type
== dep_breaks
)
397 ? possi
->up
->up
->set
!= possi
->ed
&& 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
403 if (useavailable(&possi
->ed
->pkg
)) {
404 assert(want
== PKG_WANT_INSTALL
);
405 return versionsatisfied(&possi
->ed
->pkg
.available
, possi
);
407 if (versionsatisfied(&possi
->ed
->pkg
.installed
, possi
))
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
;
420 for (provider
= possi
->ed
->depended
.installed
;
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
,
430 pkg_virtual_deppossi_satisfied(possi
, provider
))
433 for (provider
= possi
->ed
->depended
.available
;
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
,
442 !pkg_virtual_deppossi_satisfied(possi
, provider
))
444 if (useavailable(provider
->up
->up
))
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
;