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 static const int depdebug= 1;
  35
  36 int packagelist::useavailable(pkginfo *pkg) {
  37   if (pkg->clientdata &&
  38       pkg->clientdata->selected == pkginfo::want_install &&
  39       informative(pkg,&pkg->available) &&
  40       (!(pkg->status == pkginfo::stat_installed ||
  41          pkg->status == pkginfo::stat_triggersawaited ||
  42          pkg->status == pkginfo::stat_triggerspending) ||
  43        versioncompare(&pkg->available.version,&pkg->installed.version) > 0))
  44     return 1;
  45   else
  46     return 0;
  47 }
  48
  49 pkginfoperfile *packagelist::findinfo(pkginfo *pkg) {
  50   pkginfoperfile *r;
  51   r= useavailable(pkg) ? &pkg->available : &pkg->installed;
  52   if (debug)
  53     fprintf(debug,"packagelist[%p]::findinfo(%s) useavailable=%d\n",this,pkg->name,useavailable(pkg));
  54   if (!r->valid) blankpackageperfile(r);
  55   return r;
  56 }
  57
  58 int packagelist::checkdependers(pkginfo *pkg, int changemade) {
  59   struct deppossi *possi;
  60
  61   if (pkg->available.valid) {
  62     for (possi= pkg->available.depended; possi; possi= possi->nextrev) {
  63       if (!useavailable(possi->up->up)) continue;
  64       changemade= greaterint(changemade,resolvedepcon(possi->up));
  65     }
  66   }
  67   if (pkg->installed.valid) {
  68     for (possi= pkg->installed.depended; possi; possi= possi->nextrev) {
  69       if (useavailable(possi->up->up)) continue;
  70       changemade= greaterint(changemade,resolvedepcon(possi->up));
  71     }
  72   }
  73   return changemade;
  74 }
  75
  76 int packagelist::resolvesuggest() {
  77   // We continually go around looking for things to change, but we may
  78   // only change the `suggested' value if we also increase the `priority'
  79   // Return 2 if we made a change due to a Recommended, Depends or Conficts,
  80   // or 1 if we offered or made a change because of an Optional line.
  81   if (debug)
  82     fprintf(debug,"packagelist[%p]::resolvesuggest()\n",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->name) continue;
  90       if (depdebug && debug)
  91         fprintf(debug,"packagelist[%p]::resolvesuggest() loop[%i] %s / %d\n",
  92                 this, index, table[index]->pkg->name, changemade);
  93       dependency *depends;
  94       for (depends= findinfo(table[index]->pkg)->depends;
  95            depends;
  96            depends= depends->next) {
  97         changemade= greaterint(changemade,resolvedepcon(depends));
  98       }
  99       changemade= checkdependers(table[index]->pkg,changemade);
 100       for (depends= findinfo(table[index]->pkg)->depends;
 101            depends;
 102            depends= depends->next) {
 103         if (depends->type != dep_provides) continue;
 104         changemade= checkdependers(depends->list->ed,changemade);
 105       }
 106       if (depdebug && debug)
 107         fprintf(debug,"packagelist[%p]::resolvesuggest() loop[%i] %s / -> %d\n",
 108                 this, index, table[index]->pkg->name, changemade);
 109     }
 110     if (!changemade) break;
 111     maxchangemade= greaterint(maxchangemade, changemade);
 112   }
 113   if (debug)
 114     fprintf(debug,"packagelist[%p]::resolvesuggest() done; maxchangemade=%d\n",
 115             this,maxchangemade);
 116   return maxchangemade;
 117 }
 118
 119 static int dep_update_best_to_change_stop(perpackagestate *& best, pkginfo *trythis) {
 120   // There's no point trying to select a pure virtual package.
 121   if (!trythis->clientdata) return 0;
 122
 123   if (depdebug && debug)
 124     fprintf(debug,"update_best_to_change(best=%s{%d}, test=%s{%d});\n",
 125             best ? best->pkg->name : "", best ? (int)best->spriority : -1,
 126             trythis->name, trythis->clientdata->spriority);
 127
 128   // If the problem is caused by us deselecting one of these packages
 129   // we should not try to select another one instead.
 130   if (trythis->clientdata->spriority == sp_deselecting) return 1;
 131
 132   // If we haven't found anything yet then this is our best so far.
 133   if (!best) goto yes;
 134
 135   // If only one of the packages is available, use that one
 136   if (!informative(trythis,&trythis->available) &&
 137       informative(best->pkg,&best->pkg->available)) return 0;
 138   if (informative(trythis,&trythis->available) &&
 139       !informative(best->pkg,&best->pkg->available)) 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   if (depdebug && debug) fprintf(debug,"update_best_to_change(); yes\n");
 155
 156   best=trythis->clientdata; return 0;
 157 }
 158
 159 int packagelist::deselect_one_of(pkginfo *per, pkginfo *ped, dependency *display) {
 160   perpackagestate *er= per->clientdata;
 161   perpackagestate *ed= ped->clientdata;
 162
 163   if (!er || !would_like_to_install(er->selected,per) ||
 164       !ed || !would_like_to_install(ed->selected,ped)) return 0;
 165
 166   add(display,dp_must);
 167
 168   er= per->clientdata;  // these can be changed by add
 169   ed= ped->clientdata;
 170
 171   if (depdebug && debug)
 172     fprintf(debug,"packagelist[%p]::deselect_one_of(): er %s{%d} ed %s{%d} [%p]\n",
 173             this, er->pkg->name, er->spriority, ed->pkg->name, ed->spriority, display);
 174
 175   perpackagestate *best;
 176
 177   // Try not keep packages needing reinstallation.
 178   if (per->eflag & pkginfo::eflag_reinstreq)
 179     best = ed;
 180   else if (ped->eflag & pkginfo::eflag_reinstreq)
 181     best = er;
 182   else if (er->spriority < ed->spriority) best= er; // We'd rather change the
 183   else if (er->spriority > ed->spriority) best= ed; // one with the lowest priority.
 184   // ... failing that the one with the highest priority
 185   else if (er->pkg->priority > ed->pkg->priority)
 186     best = er;
 187   else if (er->pkg->priority < ed->pkg->priority)
 188     best = ed;
 189   else best= ed;                                      // ... failing that, the second
 190
 191   if (depdebug && debug)
 192     fprintf(debug,"packagelist[%p]::deselect_one_of(): best %s{%d}\n",
 193             this, best->pkg->name, best->spriority);
 194
 195   if (best->spriority >= sp_deselecting) return 0;
 196   best->suggested=
 197     best->pkg->status == pkginfo::stat_notinstalled
 198       ? pkginfo::want_purge : pkginfo::want_deinstall; // FIXME: configurable.
 199   best->selected= best->suggested;
 200   best->spriority= sp_deselecting;
 201
 202   return 2;
 203 }
 204
 205 int packagelist::resolvedepcon(dependency *depends) {
 206   perpackagestate *best, *fixbyupgrade;
 207   deppossi *possi, *provider;
 208   int r, foundany;
 209
 210   if (depdebug && debug) {
 211     fprintf(debug,"packagelist[%p]::resolvedepcon([%p] %s --%s-->",
 212             this, depends, depends->up->name, relatestrings[depends->type]);
 213     for (possi=depends->list; possi; possi=possi->next)
 214       fprintf(debug," %s",possi->ed->name);
 215     fprintf(debug,"); (ing)->want=%s\n",
 216             depends->up->clientdata
 217             ? wantstrings[depends->up->clientdata->suggested]
 218             : "(no clientdata)");
 219   }
 220
 221   if (!depends->up->clientdata) return 0;
 222
 223   switch (depends->type) {
 224
 225   case dep_provides:
 226   case dep_replaces:
 227     return 0;
 228
 229   case dep_enhances:
 230   case dep_suggests:
 231   case dep_recommends:
 232   case dep_depends:
 233   case dep_predepends:
 234     if (would_like_to_install(depends->up->clientdata->selected,depends->up) <= 0)
 235       return 0;
 236
 237     fixbyupgrade= 0;
 238
 239     possi = depends->list;
 240     while (possi && !deppossatisfied(possi, &fixbyupgrade))
 241       possi = possi->next;
 242     if (depdebug && debug)
 243       fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): depends found %s\n",
 244               this,depends,
 245               possi ? possi->ed->name : "[none]");
 246     if (possi) return 0;
 247
 248     // Ensures all in the recursive list; adds info strings; ups priorities
 249     switch (depends->type) {
 250     case dep_enhances:
 251     case dep_suggests:
 252         r= add(depends, dp_may);
 253         return r;
 254     case dep_recommends:
 255         r= add(depends, dp_should);
 256         break;
 257     default:
 258         r= add(depends, dp_must);
 259     }
 260
 261     if (fixbyupgrade) {
 262       if (depdebug && debug) fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): "
 263                             "fixbyupgrade %s\n", this,depends,fixbyupgrade->pkg->name);
 264       best= fixbyupgrade;
 265     } else {
 266       best= 0;
 267       for (possi= depends->list;
 268            possi;
 269            possi= possi->next) {
 270         foundany= 0;
 271         if (possi->ed->clientdata) foundany= 1;
 272         if (dep_update_best_to_change_stop(best, possi->ed)) goto mustdeselect;
 273         for (provider= possi->ed->available.valid ? possi->ed->available.depended : 0;
 274              provider;
 275              provider= provider->nextrev) {
 276           if (provider->up->type != dep_provides) continue;
 277           if (provider->up->up->clientdata) foundany= 1;
 278           if (dep_update_best_to_change_stop(best, provider->up->up)) goto mustdeselect;
 279         }
 280         if (!foundany) addunavailable(possi);
 281       }
 282       if (!best) {
 283         if (depdebug && debug) fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): "
 284                               "mustdeselect nobest\n", this,depends);
 285         return r;
 286       }
 287     }
 288     if (depdebug && debug)
 289       fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): select best=%s{%d}\n",
 290               this,depends, best->pkg->name, best->spriority);
 291     if (best->spriority >= sp_selecting) return r;
 292     /* Always select depends. Only select recommends if we got here because
 293      * of a manually-initiated install request. */
 294     if (depends->type != dep_recommends || manual_install) {
 295       best->selected= best->suggested= pkginfo::want_install;
 296       best->spriority= sp_selecting;
 297     }
 298     return r ? 2 : 0;
 299
 300   mustdeselect:
 301     best= depends->up->clientdata;
 302     if (depdebug && debug)
 303       fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): mustdeselect best=%s{%d}\n",
 304               this,depends, best->pkg->name, best->spriority);
 305
 306     if (best->spriority >= sp_deselecting) return r;
 307     /* Always remove depends, but never remove recommends. */
 308     if (depends->type != dep_recommends) {
 309       best->selected= best->suggested=
 310         best->pkg->status == pkginfo::stat_notinstalled
 311           ? pkginfo::want_purge : pkginfo::want_deinstall; // FIXME: configurable
 312       best->spriority= sp_deselecting;
 313     }
 314     return r ? 2 : 0;
 315
 316   case dep_conflicts:
 317   case dep_breaks:
 318
 319     if (depdebug && debug)
 320       fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): conflict\n",
 321               this,depends);
 322
 323     if (would_like_to_install(depends->up->clientdata->selected,depends->up) == 0)
 324       return 0;
 325
 326     if (depdebug && debug)
 327       fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): conflict installing 1\n",
 328               this,depends);
 329
 330     if (!deppossatisfied(depends->list,0)) return 0;
 331
 332     if (depdebug && debug)
 333       fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): conflict satisfied - ouch\n",
 334               this,depends);
 335
 336     if (depends->up != depends->list->ed) {
 337       r= deselect_one_of(depends->up, depends->list->ed, depends);  if (r) return r;
 338     }
 339     for (provider= depends->list->ed->available.valid ?
 340                    depends->list->ed->available.depended : 0;
 341          provider;
 342          provider= provider->nextrev) {
 343       if (provider->up->type != dep_provides) continue;
 344       if (provider->up->up == depends->up) continue; // conflicts & provides same thing
 345       r= deselect_one_of(depends->up, provider->up->up, depends);  if (r) return r;
 346     }
 347     if (depdebug && debug)
 348       fprintf(debug,"packagelist[%p]::resolvedepcon([%p]): no desel\n", this,depends);
 349     return 0;
 350
 351   default:
 352     internerr("unknown deptype");
 353   }
 354   /* never reached, make gcc happy */
 355   return 1;
 356 }
 357
 358 int packagelist::deppossatisfied(deppossi *possi, perpackagestate **fixbyupgrade) {
 359   // `satisfied' here for Conflicts and Breaks means that the
 360   //  restriction is violated ie that the target package is wanted
 361   int would;
 362   pkginfo::pkgwant want= pkginfo::want_purge;
 363
 364   if (possi->ed->clientdata) {
 365     want= possi->ed->clientdata->selected;
 366     would= would_like_to_install(want,possi->ed);
 367   } else {
 368     would= 0;
 369   }
 370
 371   if ((possi->up->type == dep_conflicts || possi->up->type == dep_breaks)
 372       ? possi->up->up != possi->ed && would != 0
 373       : would > 0) {
 374     // If it's to be installed or left installed, then either it's of
 375     // the right version, and therefore OK, or a version must have
 376     // been specified, in which case we don't need to look at the rest
 377     // anyway.
 378     if (useavailable(possi->ed)) {
 379       assert(want == pkginfo::want_install);
 380       return versionsatisfied(&possi->ed->available,possi);
 381     } else {
 382       if (versionsatisfied(&possi->ed->installed,possi)) return 1;
 383       if (want == pkginfo::want_hold && fixbyupgrade && !*fixbyupgrade &&
 384           versionsatisfied(&possi->ed->available,possi) &&
 385           versioncompare(&possi->ed->available.version,
 386                          &possi->ed->installed.version) > 1)
 387         *fixbyupgrade= possi->ed->clientdata;
 388       return 0;
 389     }
 390   }
 391   if (possi->verrel != dvr_none) return 0;
 392   deppossi *provider;
 393   if (possi->ed->installed.valid) {
 394     for (provider= possi->ed->installed.depended;
 395          provider;
 396          provider= provider->nextrev) {
 397       if (provider->up->type == dep_provides &&
 398           provider->up->up->clientdata &&
 399           !useavailable(provider->up->up) &&
 400           would_like_to_install(provider->up->up->clientdata->selected,
 401                                 provider->up->up))
 402         return 1;
 403     }
 404   }
 405   if (possi->ed->available.valid) {
 406     for (provider= possi->ed->available.depended;
 407          provider;
 408          provider= provider->nextrev) {
 409       if (provider->up->type != dep_provides ||
 410           !provider->up->up->clientdata ||
 411           !would_like_to_install(provider->up->up->clientdata->selected,
 412                                  provider->up->up))
 413         continue;
 414       if (useavailable(provider->up->up))
 415         return 1;
 416       if (fixbyupgrade && !*fixbyupgrade &&
 417           (!(provider->up->up->status == pkginfo::stat_installed ||
 418              provider->up->up->status == pkginfo::stat_triggerspending ||
 419              provider->up->up->status == pkginfo::stat_triggersawaited) ||
 420            versioncompare(&provider->up->up->available.version,
 421                           &provider->up->up->installed.version) > 1))
 422         *fixbyupgrade= provider->up->up->clientdata;
 423     }
 424   }
 425   return 0;
 426 }