chiark - git - mdw - dpkg/blob - 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 <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 }