dselect/pkgdepcon.cc

   1 /*
   2  * dselect - Debian package maintenance user interface
   3  * pkgdepcon.cc - dependency and conflict resolution
   4  *
   5  * Copyright © 1995 Ian Jackson <ian@chiark.greenend.org.uk>
   6  *
   7  * This is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19  */
  20
  21 #include <config.h>
  22 #include <compat.h>
  23
  24 #include <assert.h>
  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 == pkginfo::want_install &&
  39       pkg_is_informative(pkg, &pkg->available) &&
  40       (!(pkg->status == pkginfo::stat_installed ||
  41          pkg->status == pkginfo::stat_triggersawaited ||
  42          pkg->status == pkginfo::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 *r;
  54   r= useavailable(pkg) ? &pkg->available : &pkg->installed;
  55   debug(dbg_general, "packagelist[%p]::find_pkgbin(%s) useavailable=%d",
  56         this, pkgbin_name(pkg, r, pnaw_always), useavailable(pkg));
  57
  58   return r;
  59 }
  60
  61 int packagelist::checkdependers(pkginfo *pkg, int changemade) {
  62   struct deppossi *possi;
  63
  64   for (possi = pkg->set->depended.available; possi; possi = possi->rev_next) {
  65     if (!useavailable(possi->up->up))
  66       continue;
  67     changemade = max(changemade, resolvedepcon(possi->up));
  68   }
  69   for (possi = pkg->set->depended.installed; possi; possi = possi->rev_next) {
  70     if (useavailable(possi->up->up))
  71       continue;
  72     changemade = max(changemade, resolvedepcon(possi->up));
  73   }
  74   return changemade;
  75 }
  76
  77 int packagelist::resolvesuggest() {
  78   // We continually go around looking for things to change, but we may
  79   // only change the ‘suggested’ value if we also increase the ‘priority’
  80   // Return 2 if we made a change due to a Recommended, Depends or Conficts,
  81   // or 1 if we offered or made a change because of an Optional line.
  82   debug(dbg_general, "packagelist[%p]::resolvesuggest()", this);
  83   int changemade, maxchangemade;
  84   maxchangemade= 0;
  85   for (;;) {
  86     changemade= 0;
  87     int index;
  88     for (index=0; index<nitems; index++) {
  89       if (!table[index]->pkg->set->name)
  90         continue;
  91       debug(dbg_depcon, "packagelist[%p]::resolvesuggest() loop[%i] %s / %d",
  92             this, index, pkg_name(table[index]->pkg, pnaw_always), changemade);
  93       dependency *depends;
  94       for (depends = find_pkgbin(table[index]->pkg)->depends;
  95            depends;
  96            depends= depends->next) {
  97         changemade = max(changemade, resolvedepcon(depends));
  98       }
  99       changemade= checkdependers(table[index]->pkg,changemade);
 100       for (depends = find_pkgbin(table[index]->pkg)->depends;
 101            depends;
 102            depends= depends->next) {
 103         if (depends->type != dep_provides) continue;
 104         changemade = checkdependers(&depends->list->ed->pkg, changemade);
 105       }
 106       debug(dbg_depcon, "packagelist[%p]::resolvesuggest() loop[%i] %s / -> %d",
 107             this, index, pkg_name(table[index]->pkg, pnaw_always), changemade);
 108     }
 109     if (!changemade) break;
 110     maxchangemade = max(maxchangemade, changemade);
 111   }
 112   debug(dbg_general, "packagelist[%p]::resolvesuggest() done; maxchangemade=%d",
 113         this, maxchangemade);
 114   return maxchangemade;
 115 }
 116
 117 static int dep_update_best_to_change_stop(perpackagestate *& best, pkginfo *trythis) {
 118   // There's no point trying to select a pure virtual package.
 119   if (!trythis->clientdata) return 0;
 120
 121   debug(dbg_depcon, "update_best_to_change(best=%s{%d}, test=%s{%d});",
 122         best ? pkg_name(best->pkg, pnaw_always) : "",
 123         best ? (int)best->spriority : -1,
 124         trythis->set->name, trythis->clientdata->spriority);
 125
 126   // If the problem is caused by us deselecting one of these packages
 127   // we should not try to select another one instead.
 128   if (trythis->clientdata->spriority == sp_deselecting) return 1;
 129
 130   // If we haven't found anything yet then this is our best so far.
 131   if (!best) goto yes;
 132
 133   // If only one of the packages is available, use that one
 134   if (!pkg_is_informative(trythis, &trythis->available) &&
 135       pkg_is_informative(best->pkg, &best->pkg->available))
 136     return 0;
 137   if (pkg_is_informative(trythis, &trythis->available) &&
 138       !pkg_is_informative(best->pkg, &best->pkg->available))
 139     goto yes;
 140
 141   // Select the package with the lowest priority (ie, the one of whom
 142   // we were least sure we wanted it deselected).
 143   if (trythis->clientdata->spriority > best->spriority) return 0;
 144   if (trythis->clientdata->spriority < best->spriority) goto yes;
 145
 146   // Pick the package with the must fundamental recommendation level.
 147   if (trythis->priority > best->pkg->priority) return 0;
 148   if (trythis->priority < best->pkg->priority) goto yes;
 149
 150   // If we're still unsure we'll change the first one in the list.
 151   return 0;
 152
 153  yes:
 154   debug(dbg_depcon, "update_best_to_change(); yes");
 155
 156   best=trythis->clientdata; return 0;
 157 }
 158
 159 int
 160 packagelist::deselect_one_of(pkginfo *per, pkginfo *ped, dependency *dep)
 161 {
 162   perpackagestate *er= per->clientdata;
 163   perpackagestate *ed= ped->clientdata;
 164
 165   if (!er || !would_like_to_install(er->selected,per) ||
 166       !ed || !would_like_to_install(ed->selected,ped)) return 0;
 167
 168   add(dep, dp_must);
 169
 170   er= per->clientdata;  // these can be changed by add
 171   ed= ped->clientdata;
 172
 173   debug(dbg_depcon,
 174         "packagelist[%p]::deselect_one_of(): er %s{%d} ed %s{%d} [%p]",
 175         this, pkg_name(er->pkg, pnaw_always), er->spriority,
 176         pkg_name(ed->pkg, pnaw_always), ed->spriority, dep);
 177
 178   perpackagestate *best;
 179
 180   // Try not keep packages needing reinstallation.
 181   if (per->eflag & pkginfo::eflag_reinstreq)
 182     best = ed;
 183   else if (ped->eflag & pkginfo::eflag_reinstreq)
 184     best = er;
 185   else if (er->spriority < ed->spriority) best= er; // We'd rather change the
 186   else if (er->spriority > ed->spriority) best= ed; // one with the lowest priority.
 187   // ... failing that the one with the highest priority
 188   else if (er->pkg->priority > ed->pkg->priority)
 189     best = er;
 190   else if (er->pkg->priority < ed->pkg->priority)
 191     best = ed;
 192   else best= ed;                                      // ... failing that, the second
 193
 194   debug(dbg_depcon, "packagelist[%p]::deselect_one_of(): best %s{%d}",
 195         this, pkg_name(best->pkg, pnaw_always), best->spriority);
 196
 197   if (best->spriority >= sp_deselecting) return 0;
 198   best->suggested=
 199     best->pkg->status == pkginfo::stat_notinstalled
 200       ? pkginfo::want_purge : pkginfo::want_deinstall; // FIXME: configurable.
 201   best->selected= best->suggested;
 202   best->spriority= sp_deselecting;
 203
 204   return 2;
 205 }
 206
 207 int packagelist::resolvedepcon(dependency *depends) {
 208   perpackagestate *best, *fixbyupgrade;
 209   deppossi *possi, *provider;
 210   int r, foundany;
 211
 212   if (debug_has_flag(dbg_depcon)) {
 213     varbuf pkg_names;
 214
 215     for (possi = depends->list; possi; possi = possi->next) {
 216       pkg_names(' ');
 217       pkg_names(possi->ed->name);
 218     }
 219
 220     debug(dbg_depcon,
 221           "packagelist[%p]::resolvedepcon([%p] %s --%s-->%s); (ing)->want=%s",
 222           this, depends, pkg_name(depends->up, pnaw_always),
 223           relatestrings[depends->type],
 224           pkg_names.string(), depends->up->clientdata ?
 225           wantstrings[depends->up->clientdata->suggested] : "(no clientdata)");
 226   }
 227
 228   if (!depends->up->clientdata) return 0;
 229
 230   switch (depends->type) {
 231
 232   case dep_provides:
 233   case dep_replaces:
 234     return 0;
 235
 236   case dep_enhances:
 237   case dep_suggests:
 238   case dep_recommends:
 239   case dep_depends:
 240   case dep_predepends:
 241     if (would_like_to_install(depends->up->clientdata->selected,depends->up) <= 0)
 242       return 0;
 243
 244     fixbyupgrade= 0;
 245
 246     possi = depends->list;
 247     while (possi && !deppossatisfied(possi, &fixbyupgrade))
 248       possi = possi->next;
 249     debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): depends found %s",
 250           this, depends, possi ? possi->ed->name : "[none]");
 251     if (possi) return 0;
 252
 253     // Ensures all in the recursive list; adds info strings; ups priorities
 254     switch (depends->type) {
 255     case dep_enhances:
 256     case dep_suggests:
 257         r= add(depends, dp_may);
 258         return r;
 259     case dep_recommends:
 260         r= add(depends, dp_should);
 261         break;
 262     default:
 263         r= add(depends, dp_must);
 264     }
 265
 266     if (fixbyupgrade) {
 267       debug(dbg_depcon,
 268             "packagelist[%p]::resolvedepcon([%p]): fixbyupgrade %s",
 269             this, depends, pkg_name(fixbyupgrade->pkg, pnaw_always));
 270       best= fixbyupgrade;
 271     } else {
 272       best= 0;
 273       for (possi= depends->list;
 274            possi;
 275            possi= possi->next) {
 276         foundany= 0;
 277         if (possi->ed->pkg.clientdata)
 278           foundany = 1;
 279         if (dep_update_best_to_change_stop(best, &possi->ed->pkg))
 280           goto mustdeselect;
 281         for (provider = possi->ed->depended.available;
 282              provider;
 283              provider = provider->rev_next) {
 284           if (provider->up->type != dep_provides) continue;
 285           if (provider->up->up->clientdata) foundany= 1;
 286           if (dep_update_best_to_change_stop(best, provider->up->up)) goto mustdeselect;
 287         }
 288         if (!foundany) addunavailable(possi);
 289       }
 290       if (!best) {
 291         debug(dbg_depcon,
 292               "packagelist[%p]::resolvedepcon([%p]): mustdeselect nobest",
 293               this, depends);
 294         return r;
 295       }
 296     }
 297     debug(dbg_depcon,
 298           "packagelist[%p]::resolvedepcon([%p]): select best=%s{%d}",
 299           this, depends, pkg_name(best->pkg, pnaw_always), best->spriority);
 300     if (best->spriority >= sp_selecting) return r;
 301     /* Always select depends. Only select recommends if we got here because
 302      * of a manually-initiated install request. */
 303     if (depends->type != dep_recommends || manual_install) {
 304       best->selected= best->suggested= pkginfo::want_install;
 305       best->spriority= sp_selecting;
 306     }
 307     return r ? 2 : 0;
 308
 309   mustdeselect:
 310     best= depends->up->clientdata;
 311     debug(dbg_depcon,
 312           "packagelist[%p]::resolvedepcon([%p]): mustdeselect best=%s{%d}",
 313           this, depends, pkg_name(best->pkg, pnaw_always), best->spriority);
 314
 315     if (best->spriority >= sp_deselecting) return r;
 316     /* Always remove depends, but never remove recommends. */
 317     if (depends->type != dep_recommends) {
 318       best->selected= best->suggested=
 319         best->pkg->status == pkginfo::stat_notinstalled
 320           ? pkginfo::want_purge : pkginfo::want_deinstall; // FIXME: configurable
 321       best->spriority= sp_deselecting;
 322     }
 323     return r ? 2 : 0;
 324
 325   case dep_conflicts:
 326   case dep_breaks:
 327     debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): conflict",
 328           this, depends);
 329
 330     if (would_like_to_install(depends->up->clientdata->selected,depends->up) == 0)
 331       return 0;
 332
 333     debug(dbg_depcon,
 334           "packagelist[%p]::resolvedepcon([%p]): conflict installing 1",
 335           this, depends);
 336
 337     if (!deppossatisfied(depends->list,0)) return 0;
 338
 339     debug(dbg_depcon,
 340           "packagelist[%p]::resolvedepcon([%p]): conflict satisfied - ouch",
 341           this, depends);
 342
 343     if (depends->up->set != depends->list->ed) {
 344       r = deselect_one_of(depends->up, &depends->list->ed->pkg, depends);
 345       if (r)
 346         return r;
 347     }
 348     for (provider = depends->list->ed->depended.available;
 349          provider;
 350          provider = provider->rev_next) {
 351       if (provider->up->type != dep_provides) continue;
 352       if (provider->up->up == depends->up) continue; // conflicts & provides same thing
 353       r= deselect_one_of(depends->up, provider->up->up, depends);  if (r) return r;
 354     }
 355     debug(dbg_depcon, "packagelist[%p]::resolvedepcon([%p]): no desel",
 356           this, depends);
 357     return 0;
 358
 359   default:
 360     internerr("unknown deptype %d", depends->type);
 361   }
 362   /* never reached, make gcc happy */
 363   return 1;
 364 }
 365
 366 bool
 367 packagelist::deppossatisfied(deppossi *possi, perpackagestate **fixbyupgrade)
 368 {
 369   // ‘satisfied’ here for Conflicts and Breaks means that the
 370   //  restriction is violated ie that the target package is wanted
 371   int would;
 372   pkginfo::pkgwant want= pkginfo::want_purge;
 373
 374   if (possi->ed->pkg.clientdata) {
 375     want = possi->ed->pkg.clientdata->selected;
 376     would = would_like_to_install(want, &possi->ed->pkg);
 377   } else {
 378     would= 0;
 379   }
 380
 381   if ((possi->up->type == dep_conflicts || possi->up->type == dep_breaks)
 382       ? possi->up->up->set != possi->ed && would != 0
 383       : would > 0) {
 384     // If it's to be installed or left installed, then either it's of
 385     // the right version, and therefore OK, or a version must have
 386     // been specified, in which case we don't need to look at the rest
 387     // anyway.
 388     if (useavailable(&possi->ed->pkg)) {
 389       assert(want == pkginfo::want_install);
 390       return versionsatisfied(&possi->ed->pkg.available, possi);
 391     } else {
 392       if (versionsatisfied(&possi->ed->pkg.installed, possi))
 393         return true;
 394       if (want == pkginfo::want_hold && fixbyupgrade && !*fixbyupgrade &&
 395           versionsatisfied(&possi->ed->pkg.available, possi) &&
 396           dpkg_version_compare(&possi->ed->pkg.available.version,
 397                                &possi->ed->pkg.installed.version) > 1)
 398         *fixbyupgrade = possi->ed->pkg.clientdata;
 399       return false;
 400     }
 401   }
 402   if (possi->verrel != dpkg_relation_none)
 403     return false;
 404   deppossi *provider;
 405
 406   for (provider = possi->ed->depended.installed;
 407        provider;
 408        provider = provider->rev_next) {
 409     if (provider->up->type == dep_provides &&
 410         ((possi->up->type != dep_conflicts && possi->up->type != dep_breaks) ||
 411          provider->up->up->set != possi->up->up->set) &&
 412         provider->up->up->clientdata &&
 413         !useavailable(provider->up->up) &&
 414         would_like_to_install(provider->up->up->clientdata->selected,
 415                               provider->up->up))
 416       return true;
 417   }
 418   for (provider = possi->ed->depended.available;
 419        provider;
 420        provider = provider->rev_next) {
 421     if (provider->up->type != dep_provides ||
 422         ((possi->up->type == dep_conflicts || possi->up->type == dep_breaks) &&
 423          provider->up->up->set == possi->up->up->set) ||
 424         !provider->up->up->clientdata ||
 425         !would_like_to_install(provider->up->up->clientdata->selected,
 426                                provider->up->up))
 427       continue;
 428     if (useavailable(provider->up->up))
 429       return true;
 430     if (fixbyupgrade && !*fixbyupgrade &&
 431         (!(provider->up->up->status == pkginfo::stat_installed ||
 432            provider->up->up->status == pkginfo::stat_triggerspending ||
 433            provider->up->up->status == pkginfo::stat_triggersawaited) ||
 434          dpkg_version_compare(&provider->up->up->available.version,
 435                               &provider->up->up->installed.version) > 1))
 436       *fixbyupgrade = provider->up->up->clientdata;
 437   }
 438   return false;
 439 }