dselect/pkgdepcon.cc

   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 <string.h>
  26 #include <stdio.h>
  27
  28 #include <dpkg/dpkg.h>
  29 #include <dpkg/dpkg-db.h>
  30
  31 #include "dselect.h"
  32 #include "pkglist.h"
  33
  34 bool
  35 packagelist::useavailable(pkginfo *pkg)
  36 {
  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))
  45     return true;
  46   else
  47     return false;
  48 }
  49
  50 pkgbin *
  51 packagelist::find_pkgbin(pkginfo *pkg)
  52 {
  53   pkgbin *pkgbin;
  54
  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));
  58
  59   return pkgbin;
  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 maxchangemade = 0;
  85
  86   for (;;) {
  87     int changemade = 0;
  88     int index;
  89
  90     for (index=0; index<nitems; index++) {
  91       if (!table[index]->pkg->set->name)
  92         continue;
  93       debug(dbg_depcon, "packagelist[%p]::resolvesuggest() loop[%i] %s / %d",
  94             this, index, pkg_name(table[index]->pkg, pnaw_always), changemade);
  95       dependency *depends;
  96       for (depends = find_pkgbin(table[index]->pkg)->depends;
  97            depends;
  98            depends= depends->next) {
  99         changemade = max(changemade, resolvedepcon(depends));
 100       }
 101       changemade= checkdependers(table[index]->pkg,changemade);
 102       for (depends = find_pkgbin(table[index]->pkg)->depends;
 103            depends;
 104            depends= depends->next) {
 105         if (depends->type != dep_provides) continue;
 106         changemade = checkdependers(&depends->list->ed->pkg, changemade);
 107       }
 108       debug(dbg_depcon, "packagelist[%p]::resolvesuggest() loop[%i] %s / -> %d",
 109             this, index, pkg_name(table[index]->pkg, pnaw_always), changemade);
 110     }
 111     if (!changemade) break;
 112     maxchangemade = max(maxchangemade, changemade);
 113   }
 114   debug(dbg_general, "packagelist[%p]::resolvesuggest() done; maxchangemade=%d",
 115         this, maxchangemade);
 116   return maxchangemade;
 117 }
 118
 119 static bool
 120 dep_update_best_to_change_stop(perpackagestate *& best, pkginfo *trythis)
 121 {
 122   // There's no point trying to select a pure virtual package.
 123   if (!trythis->clientdata)
 124     return false;
 125
 126   debug(dbg_depcon, "update_best_to_change(best=%s{%d}, test=%s{%d});",
 127         best ? pkg_name(best->pkg, pnaw_always) : "",
 128         best ? best->spriority : -1,
 129         trythis->set->name, trythis->clientdata->spriority);
 130
 131   // If the problem is caused by us deselecting one of these packages
 132   // we should not try to select another one instead.
 133   if (trythis->clientdata->spriority == sp_deselecting)
 134     return true;
 135
 136   // If we haven't found anything yet then this is our best so far.
 137   if (!best) goto yes;
 138
 139   // If only one of the packages is available, use that one
 140   if (!pkg_is_informative(trythis, &trythis->available) &&
 141       pkg_is_informative(best->pkg, &best->pkg->available))
 142     return false;
 143   if (pkg_is_informative(trythis, &trythis->available) &&
 144       !pkg_is_informative(best->pkg, &best->pkg->available))
 145     goto yes;
 146
 147   // Select the package with the lowest priority (i.e., the one of whom
 148   // we were least sure we wanted it deselected).
 149   if (trythis->clientdata->spriority > best->spriority)
 150     return false;
 151   if (trythis->clientdata->spriority < best->spriority) goto yes;
 152
 153   // Pick the package with the must fundamental recommendation level.
 154   if (trythis->priority > best->pkg->priority)
 155     return false;
 156   if (trythis->priority < best->pkg->priority) goto yes;
 157
 158   // If we're still unsure we'll change the first one in the list.
 159   return false;
 160
 161  yes:
 162   debug(dbg_depcon, "update_best_to_change(); yes");
 163
 164   best = trythis->clientdata;
 165   return false;
 166 }
 167
 168 int
 169 packagelist::deselect_one_of(pkginfo *per, pkginfo *ped, dependency *dep)
 170 {
 171   perpackagestate *er= per->clientdata;
 172   perpackagestate *ed= ped->clientdata;
 173
 174   if (!er || !would_like_to_install(er->selected,per) ||
 175       !ed || !would_like_to_install(ed->selected,ped)) return 0;
 176
 177   add(dep, dp_must);
 178
 179   er= per->clientdata;  // these can be changed by add
 180   ed= ped->clientdata;
 181
 182   debug(dbg_depcon,
 183         "packagelist[%p]::deselect_one_of(): er %s{%d} ed %s{%d} [%p]",
 184         this, pkg_name(er->pkg, pnaw_always), er->spriority,
 185         pkg_name(ed->pkg, pnaw_always), ed->spriority, dep);
 186
 187   perpackagestate *best;
 188
 189   // Try not keep packages needing reinstallation.
 190   if (per->eflag & PKG_EFLAG_REINSTREQ)
 191     best = ed;
 192   else if (ped->eflag & PKG_EFLAG_REINSTREQ)
 193     best = er;
 194   // We'd rather change the one with the lowest priority.
 195   else if (er->spriority > ed->spriority)
 196     best = ed;
 197   else if (er->spriority < ed->spriority)
 198     best = er;
 199   // ... failing that the one with the highest priority.
 200   else if (er->pkg->priority < ed->pkg->priority)
 201     best = ed;
 202   else if (er->pkg->priority > ed->pkg->priority)
 203     best = er;
 204   // ... failing that, the second.
 205   else
 206     best = ed;
 207
 208   debug(dbg_depcon, "packagelist[%p]::deselect_one_of(): best %s{%d}",
 209         this, pkg_name(best->pkg, pnaw_always), best->spriority);
 210
 211   if (best->spriority >= sp_deselecting) return 0;
 212   best->suggested=
 213     best->pkg->status == PKG_STAT_NOTINSTALLED
 214       ? PKG_WANT_PURGE : PKG_WANT_DEINSTALL; // FIXME: configurable.
 215   best->selected= best->suggested;
 216   best->spriority= sp_deselecting;
 217
 218   return 2;
 219 }
 220
 221 int packagelist::resolvedepcon(dependency *depends) {
 222   perpackagestate *best, *fixbyupgrade;
 223   deppossi *possi, *provider;
 224   bool foundany;
 225   int rc;
 226
 227   if (debug_has_flag(dbg_depcon)) {
 228     varbuf pkg_names;
 229
 230     for (possi = depends->list; possi; possi = possi->next) {
 231       pkg_names(' ');
 232       pkg_names(possi->ed->name);
 233     }
 234
 235     debug(dbg_depcon,
 236           "packagelist[%p]::resolvedepcon([%p] %s --%s-->%s); (ing)->want=%s",
 237           this, depends, pkg_name(depends->up, pnaw_always),
 238           relatestrings[depends->type],
 239           pkg_names.string(), depends->up->clientdata ?
 240           wantstrings[depends->up->clientdata->suggested] : "(no clientdata)");
 241   }
 242
 243   if (!depends->up->clientdata) return 0;
 244
 245   switch (depends->type) {
 246   case dep_provides:
 247   case dep_replaces:
 248     return 0;
 249
 250   case dep_enhances:
 251   case dep_suggests:
 252   case dep_recommends:
 253   case dep_depends:
 254   case dep_predepends:
 255     if (would_like_to_install(depends->up->clientdata->selected,depends->up) <= 0)
 256       return 0;
 257
 258     fixbyupgrade = nullptr;
 259
 260     possi = depends->list;
 261     while (possi && !deppossatisfied(possi, &fixbyupgrade))
 262       possi = possi->next;
 263     debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): depends found %s",
 264           this, depends, possi ? possi->ed->name : "[none]");
 265     if (possi) return 0;
 266
 267     // Ensures all in the recursive list; adds info strings; ups priorities
 268     switch (depends->type) {
 269     case dep_enhances:
 270     case dep_suggests:
 271       rc = add(depends, dp_may);
 272       return rc;
 273     case dep_recommends:
 274       rc = add(depends, dp_should);
 275         break;
 276     default:
 277       rc = add(depends, dp_must);
 278     }
 279
 280     if (fixbyupgrade) {
 281       debug(dbg_depcon,
 282             "packagelist[%p]::resolvedepcon([%p]): fixbyupgrade %s",
 283             this, depends, pkg_name(fixbyupgrade->pkg, pnaw_always));
 284       best= fixbyupgrade;
 285     } else {
 286       best = nullptr;
 287       for (possi= depends->list;
 288            possi;
 289            possi= possi->next) {
 290         foundany = false;
 291         if (possi->ed->pkg.clientdata)
 292           foundany = true;
 293         if (dep_update_best_to_change_stop(best, &possi->ed->pkg))
 294           goto mustdeselect;
 295         for (provider = possi->ed->depended.available;
 296              provider;
 297              provider = provider->rev_next) {
 298           if (provider->up->type != dep_provides) continue;
 299           if (provider->up->up->clientdata)
 300             foundany = true;
 301           if (dep_update_best_to_change_stop(best, provider->up->up)) goto mustdeselect;
 302         }
 303         if (!foundany) addunavailable(possi);
 304       }
 305       if (!best) {
 306         debug(dbg_depcon,
 307               "packagelist[%p]::resolvedepcon([%p]): mustdeselect nobest",
 308               this, depends);
 309         return rc;
 310       }
 311     }
 312     debug(dbg_depcon,
 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)
 316       return rc;
 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;
 322     }
 323     return rc ? 2 : 0;
 324
 325   mustdeselect:
 326     best= depends->up->clientdata;
 327     debug(dbg_depcon,
 328           "packagelist[%p]::resolvedepcon([%p]): mustdeselect best=%s{%d}",
 329           this, depends, pkg_name(best->pkg, pnaw_always), best->spriority);
 330
 331     if (best->spriority >= sp_deselecting)
 332       return rc;
 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;
 339     }
 340     return rc ? 2 : 0;
 341
 342   case dep_conflicts:
 343   case dep_breaks:
 344     debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): conflict",
 345           this, depends);
 346
 347     if (would_like_to_install(depends->up->clientdata->selected,depends->up) == 0)
 348       return 0;
 349
 350     debug(dbg_depcon,
 351           "packagelist[%p]::resolvedepcon([%p]): conflict installing 1",
 352           this, depends);
 353
 354     if (!deppossatisfied(depends->list, nullptr))
 355       return 0;
 356
 357     debug(dbg_depcon,
 358           "packagelist[%p]::resolvedepcon([%p]): conflict satisfied - ouch",
 359           this, depends);
 360
 361     if (depends->up->set != depends->list->ed) {
 362       rc = deselect_one_of(depends->up, &depends->list->ed->pkg, depends);
 363       if (rc)
 364         return rc;
 365     }
 366     for (provider = depends->list->ed->depended.available;
 367          provider;
 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);
 372       if (rc)
 373         return rc;
 374     }
 375     debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): no desel",
 376           this, depends);
 377     return 0;
 378
 379   default:
 380     internerr("unknown deptype %d", depends->type);
 381   }
 382   /* never reached, make gcc happy */
 383   return 1;
 384 }
 385
 386 bool
 387 packagelist::deppossatisfied(deppossi *possi, perpackagestate **fixbyupgrade)
 388 {
 389   // ‘satisfied’ here for Conflicts and Breaks means that the
 390   //  restriction is violated, that is, that the target package is wanted
 391   int would;
 392   pkgwant want = PKG_WANT_PURGE;
 393
 394   if (possi->ed->pkg.clientdata) {
 395     want = possi->ed->pkg.clientdata->selected;
 396     would = would_like_to_install(want, &possi->ed->pkg);
 397   } else {
 398     would= 0;
 399   }
 400
 401   if ((possi->up->type == dep_conflicts || possi->up->type == dep_breaks)
 402       ? possi->up->up->set != possi->ed && would != 0
 403       : 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
 407     // anyway.
 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);
 412     } else {
 413       if (versionsatisfied(&possi->ed->pkg.installed, possi))
 414         return true;
 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;
 420       return false;
 421     }
 422   }
 423
 424   deppossi *provider;
 425
 426   for (provider = possi->ed->depended.installed;
 427        provider;
 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,
 435                               provider->up->up) &&
 436         pkg_virtual_deppossi_satisfied(possi, provider))
 437       return true;
 438   }
 439   for (provider = possi->ed->depended.available;
 440        provider;
 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,
 447                                provider->up->up) ||
 448         !pkg_virtual_deppossi_satisfied(possi, provider))
 449       continue;
 450     if (useavailable(provider->up->up))
 451       return true;
 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;
 459   }
 460   return false;
 461 }