summaryrefslogtreecommitdiffstats
path: root/dselect/pkgdepcon.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--dselect/pkgdepcon.cc456
1 files changed, 456 insertions, 0 deletions
diff --git a/dselect/pkgdepcon.cc b/dselect/pkgdepcon.cc
new file mode 100644
index 0000000..3b54e7f
--- /dev/null
+++ b/dselect/pkgdepcon.cc
@@ -0,0 +1,456 @@
+/*
+ * dselect - Debian package maintenance user interface
+ * pkgdepcon.cc - dependency and conflict resolution
+ *
+ * Copyright © 1995 Ian Jackson <ijackson@chiark.greenend.org.uk>
+ * Copyright © 2008-2014 Guillem Jover <guillem@debian.org>
+ *
+ * This is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#include <compat.h>
+
+#include <string.h>
+#include <stdio.h>
+
+#include <dpkg/dpkg.h>
+#include <dpkg/dpkg-db.h>
+
+#include "dselect.h"
+#include "pkglist.h"
+
+bool
+packagelist::useavailable(pkginfo *pkg)
+{
+ if (pkg->clientdata &&
+ pkg->clientdata->selected == PKG_WANT_INSTALL &&
+ pkg_is_informative(pkg, &pkg->available) &&
+ (!(pkg->status == PKG_STAT_INSTALLED ||
+ pkg->status == PKG_STAT_TRIGGERSAWAITED ||
+ pkg->status == PKG_STAT_TRIGGERSPENDING) ||
+ dpkg_version_compare(&pkg->available.version,
+ &pkg->installed.version) > 0))
+ return true;
+ else
+ return false;
+}
+
+pkgbin *
+packagelist::find_pkgbin(pkginfo *pkg)
+{
+ pkgbin *pkgbin;
+
+ pkgbin = useavailable(pkg) ? &pkg->available : &pkg->installed;
+ debug(dbg_general, "packagelist[%p]::find_pkgbin(%s) useavailable=%d",
+ this, pkgbin_name(pkg, pkgbin, pnaw_always), useavailable(pkg));
+
+ return pkgbin;
+}
+
+int packagelist::checkdependers(pkginfo *pkg, int changemade) {
+ struct deppossi *possi;
+
+ for (possi = pkg->set->depended.available; possi; possi = possi->rev_next) {
+ if (!useavailable(possi->up->up))
+ continue;
+ changemade = max(changemade, resolvedepcon(possi->up));
+ }
+ for (possi = pkg->set->depended.installed; possi; possi = possi->rev_next) {
+ if (useavailable(possi->up->up))
+ continue;
+ changemade = max(changemade, resolvedepcon(possi->up));
+ }
+ return changemade;
+}
+
+int packagelist::resolvesuggest() {
+ // We continually go around looking for things to change, but we may
+ // only change the ‘suggested’ value if we also increase the ‘priority’
+ // Return 2 if we made a change due to a Recommended, Depends or Conflicts,
+ // or 1 if we offered or made a change because of an Optional line.
+ debug(dbg_general, "packagelist[%p]::resolvesuggest()", this);
+ int changemade, maxchangemade;
+ maxchangemade= 0;
+ for (;;) {
+ changemade= 0;
+ int index;
+ for (index=0; index<nitems; index++) {
+ if (!table[index]->pkg->set->name)
+ continue;
+ debug(dbg_depcon, "packagelist[%p]::resolvesuggest() loop[%i] %s / %d",
+ this, index, pkg_name(table[index]->pkg, pnaw_always), changemade);
+ dependency *depends;
+ for (depends = find_pkgbin(table[index]->pkg)->depends;
+ depends;
+ depends= depends->next) {
+ changemade = max(changemade, resolvedepcon(depends));
+ }
+ changemade= checkdependers(table[index]->pkg,changemade);
+ for (depends = find_pkgbin(table[index]->pkg)->depends;
+ depends;
+ depends= depends->next) {
+ if (depends->type != dep_provides) continue;
+ changemade = checkdependers(&depends->list->ed->pkg, changemade);
+ }
+ debug(dbg_depcon, "packagelist[%p]::resolvesuggest() loop[%i] %s / -> %d",
+ this, index, pkg_name(table[index]->pkg, pnaw_always), changemade);
+ }
+ if (!changemade) break;
+ maxchangemade = max(maxchangemade, changemade);
+ }
+ debug(dbg_general, "packagelist[%p]::resolvesuggest() done; maxchangemade=%d",
+ this, maxchangemade);
+ return maxchangemade;
+}
+
+static bool
+dep_update_best_to_change_stop(perpackagestate *& best, pkginfo *trythis)
+{
+ // There's no point trying to select a pure virtual package.
+ if (!trythis->clientdata)
+ return false;
+
+ debug(dbg_depcon, "update_best_to_change(best=%s{%d}, test=%s{%d});",
+ best ? pkg_name(best->pkg, pnaw_always) : "",
+ best ? (int)best->spriority : -1,
+ trythis->set->name, trythis->clientdata->spriority);
+
+ // If the problem is caused by us deselecting one of these packages
+ // we should not try to select another one instead.
+ if (trythis->clientdata->spriority == sp_deselecting)
+ return true;
+
+ // If we haven't found anything yet then this is our best so far.
+ if (!best) goto yes;
+
+ // If only one of the packages is available, use that one
+ if (!pkg_is_informative(trythis, &trythis->available) &&
+ pkg_is_informative(best->pkg, &best->pkg->available))
+ return false;
+ if (pkg_is_informative(trythis, &trythis->available) &&
+ !pkg_is_informative(best->pkg, &best->pkg->available))
+ goto yes;
+
+ // Select the package with the lowest priority (ie, the one of whom
+ // we were least sure we wanted it deselected).
+ if (trythis->clientdata->spriority > best->spriority)
+ return false;
+ if (trythis->clientdata->spriority < best->spriority) goto yes;
+
+ // Pick the package with the must fundamental recommendation level.
+ if (trythis->priority > best->pkg->priority)
+ return false;
+ if (trythis->priority < best->pkg->priority) goto yes;
+
+ // If we're still unsure we'll change the first one in the list.
+ return false;
+
+ yes:
+ debug(dbg_depcon, "update_best_to_change(); yes");
+
+ best = trythis->clientdata;
+ return false;
+}
+
+int
+packagelist::deselect_one_of(pkginfo *per, pkginfo *ped, dependency *dep)
+{
+ perpackagestate *er= per->clientdata;
+ perpackagestate *ed= ped->clientdata;
+
+ if (!er || !would_like_to_install(er->selected,per) ||
+ !ed || !would_like_to_install(ed->selected,ped)) return 0;
+
+ add(dep, dp_must);
+
+ er= per->clientdata; // these can be changed by add
+ ed= ped->clientdata;
+
+ debug(dbg_depcon,
+ "packagelist[%p]::deselect_one_of(): er %s{%d} ed %s{%d} [%p]",
+ this, pkg_name(er->pkg, pnaw_always), er->spriority,
+ pkg_name(ed->pkg, pnaw_always), ed->spriority, dep);
+
+ perpackagestate *best;
+
+ // Try not keep packages needing reinstallation.
+ if (per->eflag & PKG_EFLAG_REINSTREQ)
+ best = ed;
+ else if (ped->eflag & PKG_EFLAG_REINSTREQ)
+ best = er;
+ else if (er->spriority < ed->spriority) best= er; // We'd rather change the
+ else if (er->spriority > ed->spriority) best= ed; // one with the lowest priority.
+ // ... failing that the one with the highest priority
+ else if (er->pkg->priority > ed->pkg->priority)
+ best = er;
+ else if (er->pkg->priority < ed->pkg->priority)
+ best = ed;
+ else best= ed; // ... failing that, the second
+
+ debug(dbg_depcon, "packagelist[%p]::deselect_one_of(): best %s{%d}",
+ this, pkg_name(best->pkg, pnaw_always), best->spriority);
+
+ if (best->spriority >= sp_deselecting) return 0;
+ best->suggested=
+ best->pkg->status == PKG_STAT_NOTINSTALLED
+ ? PKG_WANT_PURGE : PKG_WANT_DEINSTALL; // FIXME: configurable.
+ best->selected= best->suggested;
+ best->spriority= sp_deselecting;
+
+ return 2;
+}
+
+int packagelist::resolvedepcon(dependency *depends) {
+ perpackagestate *best, *fixbyupgrade;
+ deppossi *possi, *provider;
+ bool foundany;
+ int rc;
+
+ if (debug_has_flag(dbg_depcon)) {
+ varbuf pkg_names;
+
+ for (possi = depends->list; possi; possi = possi->next) {
+ pkg_names(' ');
+ pkg_names(possi->ed->name);
+ }
+
+ debug(dbg_depcon,
+ "packagelist[%p]::resolvedepcon([%p] %s --%s-->%s); (ing)->want=%s",
+ this, depends, pkg_name(depends->up, pnaw_always),
+ relatestrings[depends->type],
+ pkg_names.string(), depends->up->clientdata ?
+ wantstrings[depends->up->clientdata->suggested] : "(no clientdata)");
+ }
+
+ if (!depends->up->clientdata) return 0;
+
+ switch (depends->type) {
+
+ case dep_provides:
+ case dep_replaces:
+ return 0;
+
+ case dep_enhances:
+ case dep_suggests:
+ case dep_recommends:
+ case dep_depends:
+ case dep_predepends:
+ if (would_like_to_install(depends->up->clientdata->selected,depends->up) <= 0)
+ return 0;
+
+ fixbyupgrade = nullptr;
+
+ possi = depends->list;
+ while (possi && !deppossatisfied(possi, &fixbyupgrade))
+ possi = possi->next;
+ debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): depends found %s",
+ this, depends, possi ? possi->ed->name : "[none]");
+ if (possi) return 0;
+
+ // Ensures all in the recursive list; adds info strings; ups priorities
+ switch (depends->type) {
+ case dep_enhances:
+ case dep_suggests:
+ rc = add(depends, dp_may);
+ return rc;
+ case dep_recommends:
+ rc = add(depends, dp_should);
+ break;
+ default:
+ rc = add(depends, dp_must);
+ }
+
+ if (fixbyupgrade) {
+ debug(dbg_depcon,
+ "packagelist[%p]::resolvedepcon([%p]): fixbyupgrade %s",
+ this, depends, pkg_name(fixbyupgrade->pkg, pnaw_always));
+ best= fixbyupgrade;
+ } else {
+ best = nullptr;
+ for (possi= depends->list;
+ possi;
+ possi= possi->next) {
+ foundany = false;
+ if (possi->ed->pkg.clientdata)
+ foundany = true;
+ if (dep_update_best_to_change_stop(best, &possi->ed->pkg))
+ goto mustdeselect;
+ for (provider = possi->ed->depended.available;
+ provider;
+ provider = provider->rev_next) {
+ if (provider->up->type != dep_provides) continue;
+ if (provider->up->up->clientdata)
+ foundany = true;
+ if (dep_update_best_to_change_stop(best, provider->up->up)) goto mustdeselect;
+ }
+ if (!foundany) addunavailable(possi);
+ }
+ if (!best) {
+ debug(dbg_depcon,
+ "packagelist[%p]::resolvedepcon([%p]): mustdeselect nobest",
+ this, depends);
+ return rc;
+ }
+ }
+ debug(dbg_depcon,
+ "packagelist[%p]::resolvedepcon([%p]): select best=%s{%d}",
+ this, depends, pkg_name(best->pkg, pnaw_always), best->spriority);
+ if (best->spriority >= sp_selecting)
+ return rc;
+ /* Always select depends. Only select recommends if we got here because
+ * of a manually-initiated install request. */
+ if (depends->type != dep_recommends || manual_install) {
+ best->selected = best->suggested = PKG_WANT_INSTALL;
+ best->spriority= sp_selecting;
+ }
+ return rc ? 2 : 0;
+
+ mustdeselect:
+ best= depends->up->clientdata;
+ debug(dbg_depcon,
+ "packagelist[%p]::resolvedepcon([%p]): mustdeselect best=%s{%d}",
+ this, depends, pkg_name(best->pkg, pnaw_always), best->spriority);
+
+ if (best->spriority >= sp_deselecting)
+ return rc;
+ /* Always remove depends, but never remove recommends. */
+ if (depends->type != dep_recommends) {
+ best->selected= best->suggested=
+ best->pkg->status == PKG_STAT_NOTINSTALLED
+ ? PKG_WANT_PURGE : PKG_WANT_DEINSTALL; // FIXME: configurable
+ best->spriority= sp_deselecting;
+ }
+ return rc ? 2 : 0;
+
+ case dep_conflicts:
+ case dep_breaks:
+ debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): conflict",
+ this, depends);
+
+ if (would_like_to_install(depends->up->clientdata->selected,depends->up) == 0)
+ return 0;
+
+ debug(dbg_depcon,
+ "packagelist[%p]::resolvedepcon([%p]): conflict installing 1",
+ this, depends);
+
+ if (!deppossatisfied(depends->list, nullptr))
+ return 0;
+
+ debug(dbg_depcon,
+ "packagelist[%p]::resolvedepcon([%p]): conflict satisfied - ouch",
+ this, depends);
+
+ if (depends->up->set != depends->list->ed) {
+ rc = deselect_one_of(depends->up, &depends->list->ed->pkg, depends);
+ if (rc)
+ return rc;
+ }
+ for (provider = depends->list->ed->depended.available;
+ provider;
+ provider = provider->rev_next) {
+ if (provider->up->type != dep_provides) continue;
+ if (provider->up->up == depends->up) continue; // conflicts & provides same thing
+ rc = deselect_one_of(depends->up, provider->up->up, depends);
+ if (rc)
+ return rc;
+ }
+ debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): no desel",
+ this, depends);
+ return 0;
+
+ default:
+ internerr("unknown deptype %d", depends->type);
+ }
+ /* never reached, make gcc happy */
+ return 1;
+}
+
+bool
+packagelist::deppossatisfied(deppossi *possi, perpackagestate **fixbyupgrade)
+{
+ // ‘satisfied’ here for Conflicts and Breaks means that the
+ // restriction is violated ie that the target package is wanted
+ int would;
+ pkgwant want = PKG_WANT_PURGE;
+
+ if (possi->ed->pkg.clientdata) {
+ want = possi->ed->pkg.clientdata->selected;
+ would = would_like_to_install(want, &possi->ed->pkg);
+ } else {
+ would= 0;
+ }
+
+ if ((possi->up->type == dep_conflicts || possi->up->type == dep_breaks)
+ ? possi->up->up->set != possi->ed && would != 0
+ : would > 0) {
+ // If it's to be installed or left installed, then either it's of
+ // the right version, and therefore OK, or a version must have
+ // been specified, in which case we don't need to look at the rest
+ // anyway.
+ if (useavailable(&possi->ed->pkg)) {
+ if (want != PKG_WANT_INSTALL)
+ internerr("depossi package is not want-install, is %d", want);
+ return versionsatisfied(&possi->ed->pkg.available, possi);
+ } else {
+ if (versionsatisfied(&possi->ed->pkg.installed, possi))
+ return true;
+ if (want == PKG_WANT_HOLD && fixbyupgrade && !*fixbyupgrade &&
+ versionsatisfied(&possi->ed->pkg.available, possi) &&
+ dpkg_version_compare(&possi->ed->pkg.available.version,
+ &possi->ed->pkg.installed.version) > 1)
+ *fixbyupgrade = possi->ed->pkg.clientdata;
+ return false;
+ }
+ }
+
+ deppossi *provider;
+
+ for (provider = possi->ed->depended.installed;
+ provider;
+ provider = provider->rev_next) {
+ if (provider->up->type == dep_provides &&
+ ((possi->up->type != dep_conflicts && possi->up->type != dep_breaks) ||
+ provider->up->up->set != possi->up->up->set) &&
+ provider->up->up->clientdata &&
+ !useavailable(provider->up->up) &&
+ would_like_to_install(provider->up->up->clientdata->selected,
+ provider->up->up) &&
+ pkg_virtual_deppossi_satisfied(possi, provider))
+ return true;
+ }
+ for (provider = possi->ed->depended.available;
+ provider;
+ provider = provider->rev_next) {
+ if (provider->up->type != dep_provides ||
+ ((possi->up->type == dep_conflicts || possi->up->type == dep_breaks) &&
+ provider->up->up->set == possi->up->up->set) ||
+ !provider->up->up->clientdata ||
+ !would_like_to_install(provider->up->up->clientdata->selected,
+ provider->up->up) ||
+ !pkg_virtual_deppossi_satisfied(possi, provider))
+ continue;
+ if (useavailable(provider->up->up))
+ return true;
+ if (fixbyupgrade && !*fixbyupgrade &&
+ (!(provider->up->up->status == PKG_STAT_INSTALLED ||
+ provider->up->up->status == PKG_STAT_TRIGGERSPENDING ||
+ provider->up->up->status == PKG_STAT_TRIGGERSAWAITED) ||
+ dpkg_version_compare(&provider->up->up->available.version,
+ &provider->up->up->installed.version) > 1))
+ *fixbyupgrade = provider->up->up->clientdata;
+ }
+ return false;
+}