apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.44 2002/11/28 18:49:16 jgg Exp $
   4 /* ######################################################################
   5
   6    Algorithms - A set of misc algorithms
   7
   8    The pkgProblemResolver class has become insanely complex and
   9    very sophisticated, it handles every test case I have thrown at it
  10    to my satisfaction. Understanding exactly why all the steps the class
  11    does are required is difficult and changing though not very risky
  12    may result in other cases not working.
  13
  14    ##################################################################### */
  15                                                                         /*}}}*/
  16 // Include Files                                                        /*{{{*/
  17 #include <apt-pkg/algorithms.h>
  18 #include <apt-pkg/error.h>
  19 #include <apt-pkg/configuration.h>
  20 #include <apt-pkg/version.h>
  21 #include <apt-pkg/sptr.h>
  22 #include <apt-pkg/acquire-item.h>
  23
  24 #include <apti18n.h>
  25 #include <sys/types.h>
  26 #include <cstdlib>
  27 #include <algorithm>
  28 #include <iostream>
  29                                                                         /*}}}*/
  30 using namespace std;
  31
  32 pkgProblemResolver *pkgProblemResolver::This = 0;
  33
  34 // Simulate::Simulate - Constructor                                     /*{{{*/
  35 // ---------------------------------------------------------------------
  36 /* The legacy translations here of input Pkg iterators is obsolete,
  37    this is not necessary since the pkgCaches are fully shared now. */
  38 pkgSimulate::pkgSimulate(pkgDepCache *Cache) : pkgPackageManager(Cache),
  39                             iPolicy(Cache),
  40                             Sim(&Cache->GetCache(),&iPolicy),
  41                             group(Sim)
  42 {
  43    Sim.Init(0);
  44    Flags = new unsigned char[Cache->Head().PackageCount];
  45    memset(Flags,0,sizeof(*Flags)*Cache->Head().PackageCount);
  46
  47    // Fake a filename so as not to activate the media swapping
  48    string Jnk = "SIMULATE";
  49    for (unsigned int I = 0; I != Cache->Head().PackageCount; I++)
  50       FileNames[I] = Jnk;
  51 }
  52                                                                         /*}}}*/
  53 // Simulate::Describe - Describe a package                              /*{{{*/
  54 // ---------------------------------------------------------------------
  55 /* Parameter Current == true displays the current package version,
  56    Parameter Candidate == true displays the candidate package version */
  57 void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Current,bool Candidate)
  58 {
  59    VerIterator Ver(Sim);
  60
  61    out << Pkg.FullName(true);
  62
  63    if (Current == true)
  64    {
  65       Ver = Pkg.CurrentVer();
  66       if (Ver.end() == false)
  67          out << " [" << Ver.VerStr() << ']';
  68    }
  69
  70    if (Candidate == true)
  71    {
  72       Ver = Sim[Pkg].CandidateVerIter(Sim);
  73       if (Ver.end() == true)
  74          return;
  75
  76       out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')';
  77    }
  78 }
  79                                                                         /*}}}*/
  80 // Simulate::Install - Simulate unpacking of a package                  /*{{{*/
  81 // ---------------------------------------------------------------------
  82 /* */
  83 bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/)
  84 {
  85    // Adapt the iterator
  86    PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
  87    Flags[Pkg->ID] = 1;
  88
  89    cout << "Inst ";
  90    Describe(Pkg,cout,true,true);
  91    Sim.MarkInstall(Pkg,false);
  92
  93    if (strcmp(Pkg.Arch(),"all") == 0)
  94    {
  95       pkgCache::GrpIterator G = Pkg.Group();
  96       pkgCache::GrpIterator iG = iPkg.Group();
  97       for (pkgCache::PkgIterator P = G.FindPkg("any"); P.end() != true; P = G.NextPkg(P))
  98       {
  99          if (strcmp(P.Arch(), "all") == 0)
 100             continue;
 101          if (iG.FindPkg(P.Arch())->CurrentVer == 0)
 102             continue;
 103          Flags[P->ID] = 1;
 104          Sim.MarkInstall(P, false);
 105       }
 106    }
 107
 108    // Look for broken conflicts+predepends.
 109    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
 110    {
 111       if (Sim[I].InstallVer == 0)
 112          continue;
 113
 114       for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false;)
 115       {
 116          DepIterator Start;
 117          DepIterator End;
 118          D.GlobOr(Start,End);
 119          if (Start->Type == pkgCache::Dep::Conflicts ||
 120              Start->Type == pkgCache::Dep::DpkgBreaks ||
 121              Start->Type == pkgCache::Dep::Obsoletes ||
 122              End->Type == pkgCache::Dep::PreDepends)
 123          {
 124             if ((Sim[End] & pkgDepCache::DepGInstall) == 0)
 125             {
 126                cout << " [" << I.FullName(false) << " on " << Start.TargetPkg().FullName(false) << ']';
 127                if (Start->Type == pkgCache::Dep::Conflicts)
 128                   _error->Error("Fatal, conflicts violated %s",I.FullName(false).c_str());
 129             }
 130          }
 131       }
 132    }
 133
 134    if (Sim.BrokenCount() != 0)
 135       ShortBreaks();
 136    else
 137       cout << endl;
 138    return true;
 139 }
 140                                                                         /*}}}*/
 141 // Simulate::Configure - Simulate configuration of a Package            /*{{{*/
 142 // ---------------------------------------------------------------------
 143 /* This is not an acurate simulation of relatity, we should really not
 144    install the package.. For some investigations it may be necessary
 145    however. */
 146 bool pkgSimulate::Configure(PkgIterator iPkg)
 147 {
 148    // Adapt the iterator
 149    PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
 150
 151    Flags[Pkg->ID] = 2;
 152
 153    if (strcmp(Pkg.Arch(),"all") == 0)
 154    {
 155       pkgCache::GrpIterator G = Pkg.Group();
 156       for (pkgCache::PkgIterator P = G.FindPkg("any"); P.end() != true; P = G.NextPkg(P))
 157       {
 158          if (strcmp(P.Arch(), "all") == 0)
 159             continue;
 160          if (Flags[P->ID] == 1)
 161             Flags[P->ID] = 2;
 162       }
 163    }
 164
 165    if (Sim[Pkg].InstBroken() == true)
 166    {
 167       /* We don't call Configure for Pseudo packages and if the 'all' is already installed
 168          the simulation will think the pseudo package is not installed, so if something is
 169          broken we walk over the dependencies and search for not installed pseudo packages */
 170       for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; D++)
 171       {
 172          if (Sim.IsImportantDep(D) == false ||
 173              (Sim[D] & pkgDepCache::DepInstall) != 0)
 174             continue;
 175          pkgCache::PkgIterator T = D.TargetPkg();
 176          if (T.end() == true || T->CurrentVer != 0 || Flags[T->ID] != 0)
 177             continue;
 178          pkgCache::PkgIterator A = T.Group().FindPkg("all");
 179          if (A.end() == true || A->VersionList == 0 || A->CurrentVer == 0 ||
 180              Cache.VS().CheckDep(A.CurVersion(), pkgCache::Dep::Equals, T.CandVersion()) == false)
 181             continue;
 182          Sim.MarkInstall(T, false);
 183          Flags[T->ID] = 2;
 184       }
 185    }
 186
 187    if (Sim[Pkg].InstBroken() == true)
 188    {
 189       cout << "Conf " << Pkg.FullName(false) << " broken" << endl;
 190
 191       Sim.Update();
 192
 193       // Print out each package and the failed dependencies
 194       for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; D++)
 195       {
 196          if (Sim.IsImportantDep(D) == false ||
 197              (Sim[D] & pkgDepCache::DepInstall) != 0)
 198             continue;
 199
 200          if (D->Type == pkgCache::Dep::Obsoletes)
 201             cout << " Obsoletes:" << D.TargetPkg().FullName(false);
 202          else if (D->Type == pkgCache::Dep::Conflicts)
 203             cout << " Conflicts:" << D.TargetPkg().FullName(false);
 204          else if (D->Type == pkgCache::Dep::DpkgBreaks)
 205             cout << " Breaks:" << D.TargetPkg().FullName(false);
 206          else
 207             cout << " Depends:" << D.TargetPkg().FullName(false);
 208       }
 209       cout << endl;
 210
 211       _error->Error("Conf Broken %s",Pkg.FullName(false).c_str());
 212    }
 213    else
 214    {
 215       cout << "Conf ";
 216       Describe(Pkg,cout,false,true);
 217    }
 218
 219    if (Sim.BrokenCount() != 0)
 220       ShortBreaks();
 221    else
 222       cout << endl;
 223
 224    return true;
 225 }
 226                                                                         /*}}}*/
 227 // Simulate::Remove - Simulate the removal of a package                 /*{{{*/
 228 // ---------------------------------------------------------------------
 229 /* */
 230 bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)
 231 {
 232    // Adapt the iterator
 233    PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
 234
 235    Flags[Pkg->ID] = 3;
 236    Sim.MarkDelete(Pkg);
 237
 238    if (strcmp(Pkg.Arch(),"all") == 0)
 239    {
 240       pkgCache::GrpIterator G = Pkg.Group();
 241       pkgCache::GrpIterator iG = iPkg.Group();
 242       for (pkgCache::PkgIterator P = G.FindPkg("any"); P.end() != true; P = G.NextPkg(P))
 243       {
 244          if (strcmp(P.Arch(), "all") == 0)
 245             continue;
 246          if (iG.FindPkg(P.Arch())->CurrentVer == 0)
 247             continue;
 248          Flags[P->ID] = 3;
 249          Sim.MarkDelete(P);
 250       }
 251    }
 252
 253    if (Purge == true)
 254       cout << "Purg ";
 255    else
 256       cout << "Remv ";
 257    Describe(Pkg,cout,true,false);
 258
 259    if (Sim.BrokenCount() != 0)
 260       ShortBreaks();
 261    else
 262       cout << endl;
 263
 264    return true;
 265 }
 266                                                                         /*}}}*/
 267 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
 268 // ---------------------------------------------------------------------
 269 /* */
 270 void pkgSimulate::ShortBreaks()
 271 {
 272    cout << " [";
 273    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
 274    {
 275       if (Sim[I].InstBroken() == true)
 276       {
 277          if (Flags[I->ID] == 0)
 278             cout << I.FullName(false) << ' ';
 279 /*       else
 280             cout << I.Name() << "! ";*/
 281       }
 282    }
 283    cout << ']' << endl;
 284 }
 285                                                                         /*}}}*/
 286 // ApplyStatus - Adjust for non-ok packages                             /*{{{*/
 287 // ---------------------------------------------------------------------
 288 /* We attempt to change the state of the all packages that have failed
 289    installation toward their real state. The ordering code will perform
 290    the necessary calculations to deal with the problems. */
 291 bool pkgApplyStatus(pkgDepCache &Cache)
 292 {
 293    pkgDepCache::ActionGroup group(Cache);
 294
 295    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 296    {
 297       if (I->VersionList == 0)
 298          continue;
 299
 300       // Only choice for a ReInstReq package is to reinstall
 301       if (I->InstState == pkgCache::State::ReInstReq ||
 302           I->InstState == pkgCache::State::HoldReInstReq)
 303       {
 304          if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true)
 305             Cache.MarkKeep(I, false, false);
 306          else
 307          {
 308             // Is this right? Will dpkg choke on an upgrade?
 309             if (Cache[I].CandidateVer != 0 &&
 310                  Cache[I].CandidateVerIter(Cache).Downloadable() == true)
 311                Cache.MarkInstall(I, false, 0, false);
 312             else
 313                return _error->Error(_("The package %s needs to be reinstalled, "
 314                                     "but I can't find an archive for it."),I.FullName(true).c_str());
 315          }
 316
 317          continue;
 318       }
 319
 320       switch (I->CurrentState)
 321       {
 322          /* This means installation failed somehow - it does not need to be
 323             re-unpacked (probably) */
 324          case pkgCache::State::UnPacked:
 325          case pkgCache::State::HalfConfigured:
 326          case pkgCache::State::TriggersAwaited:
 327          case pkgCache::State::TriggersPending:
 328          if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) ||
 329              I.State() != pkgCache::PkgIterator::NeedsUnpack)
 330             Cache.MarkKeep(I, false, false);
 331          else
 332          {
 333             if (Cache[I].CandidateVer != 0 &&
 334                  Cache[I].CandidateVerIter(Cache).Downloadable() == true)
 335                Cache.MarkInstall(I, true, 0, false);
 336             else
 337                Cache.MarkDelete(I);
 338          }
 339          break;
 340
 341          // This means removal failed
 342          case pkgCache::State::HalfInstalled:
 343          Cache.MarkDelete(I);
 344          break;
 345
 346          default:
 347          if (I->InstState != pkgCache::State::Ok)
 348             return _error->Error("The package %s is not ok and I "
 349                                  "don't know how to fix it!",I.FullName(false).c_str());
 350       }
 351    }
 352    return true;
 353 }
 354                                                                         /*}}}*/
 355 // FixBroken - Fix broken packages                                      /*{{{*/
 356 // ---------------------------------------------------------------------
 357 /* This autoinstalls every broken package and then runs the problem resolver
 358    on the result. */
 359 bool pkgFixBroken(pkgDepCache &Cache)
 360 {
 361    pkgDepCache::ActionGroup group(Cache);
 362
 363    // Auto upgrade all broken packages
 364    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 365       if (Cache[I].NowBroken() == true)
 366          Cache.MarkInstall(I, true, 0, false);
 367
 368    /* Fix packages that are in a NeedArchive state but don't have a
 369       downloadable install version */
 370    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 371    {
 372       if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
 373           Cache[I].Delete() == true)
 374          continue;
 375
 376       if (Cache[I].InstVerIter(Cache).Downloadable() == false)
 377          continue;
 378
 379       Cache.MarkInstall(I, true, 0, false);
 380    }
 381
 382    pkgProblemResolver Fix(&Cache);
 383    return Fix.Resolve(true);
 384 }
 385                                                                         /*}}}*/
 386 // DistUpgrade - Distribution upgrade                                   /*{{{*/
 387 // ---------------------------------------------------------------------
 388 /* This autoinstalls every package and then force installs every
 389    pre-existing package. This creates the initial set of conditions which
 390    most likely contain problems because too many things were installed.
 391
 392    The problem resolver is used to resolve the problems.
 393  */
 394 bool pkgDistUpgrade(pkgDepCache &Cache)
 395 {
 396    pkgDepCache::ActionGroup group(Cache);
 397
 398    /* Upgrade all installed packages first without autoinst to help the resolver
 399       in versioned or-groups to upgrade the old solver instead of installing
 400       a new one (if the old solver is not the first one [anymore]) */
 401    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 402       if (I->CurrentVer != 0)
 403          Cache.MarkInstall(I, false, 0, false);
 404
 405    /* Auto upgrade all installed packages, this provides the basis
 406       for the installation */
 407    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 408       if (I->CurrentVer != 0)
 409          Cache.MarkInstall(I, true, 0, false);
 410
 411    /* Now, auto upgrade all essential packages - this ensures that
 412       the essential packages are present and working */
 413    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 414       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 415          Cache.MarkInstall(I, true, 0, false);
 416
 417    /* We do it again over all previously installed packages to force
 418       conflict resolution on them all. */
 419    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 420       if (I->CurrentVer != 0)
 421          Cache.MarkInstall(I, false, 0, false);
 422
 423    pkgProblemResolver Fix(&Cache);
 424
 425    // Hold back held packages.
 426    if (_config->FindB("APT::Ignore-Hold",false) == false)
 427    {
 428       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 429       {
 430          if (I->SelectedState == pkgCache::State::Hold)
 431          {
 432             Fix.Protect(I);
 433             Cache.MarkKeep(I, false, false);
 434          }
 435       }
 436    }
 437
 438    return Fix.Resolve();
 439 }
 440                                                                         /*}}}*/
 441 // AllUpgrade - Upgrade as many packages as possible                    /*{{{*/
 442 // ---------------------------------------------------------------------
 443 /* Right now the system must be consistent before this can be called.
 444    It also will not change packages marked for install, it only tries
 445    to install packages not marked for install */
 446 bool pkgAllUpgrade(pkgDepCache &Cache)
 447 {
 448    pkgDepCache::ActionGroup group(Cache);
 449
 450    pkgProblemResolver Fix(&Cache);
 451
 452    if (Cache.BrokenCount() != 0)
 453       return false;
 454
 455    // Upgrade all installed packages
 456    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 457    {
 458       if (Cache[I].Install() == true)
 459          Fix.Protect(I);
 460
 461       if (_config->FindB("APT::Ignore-Hold",false) == false)
 462          if (I->SelectedState == pkgCache::State::Hold)
 463             continue;
 464
 465       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
 466          Cache.MarkInstall(I, false, 0, false);
 467    }
 468
 469    return Fix.ResolveByKeep();
 470 }
 471                                                                         /*}}}*/
 472 // MinimizeUpgrade - Minimizes the set of packages to be upgraded       /*{{{*/
 473 // ---------------------------------------------------------------------
 474 /* This simply goes over the entire set of packages and tries to keep
 475    each package marked for upgrade. If a conflict is generated then
 476    the package is restored. */
 477 bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 478 {
 479    pkgDepCache::ActionGroup group(Cache);
 480
 481    if (Cache.BrokenCount() != 0)
 482       return false;
 483
 484    // We loop for 10 tries to get the minimal set size.
 485    bool Change = false;
 486    unsigned int Count = 0;
 487    do
 488    {
 489       Change = false;
 490       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 491       {
 492          // Not interesting
 493          if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
 494             continue;
 495
 496          // Keep it and see if that is OK
 497          Cache.MarkKeep(I, false, false);
 498          if (Cache.BrokenCount() != 0)
 499             Cache.MarkInstall(I, false, 0, false);
 500          else
 501          {
 502             // If keep didnt actually do anything then there was no change..
 503             if (Cache[I].Upgrade() == false)
 504                Change = true;
 505          }
 506       }
 507       Count++;
 508    }
 509    while (Change == true && Count < 10);
 510
 511    if (Cache.BrokenCount() != 0)
 512       return _error->Error("Internal Error in pkgMinimizeUpgrade");
 513
 514    return true;
 515 }
 516                                                                         /*}}}*/
 517 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
 518 // ---------------------------------------------------------------------
 519 /* */
 520 pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : Cache(*pCache)
 521 {
 522    // Allocate memory
 523    unsigned long Size = Cache.Head().PackageCount;
 524    Scores = new signed short[Size];
 525    Flags = new unsigned char[Size];
 526    memset(Flags,0,sizeof(*Flags)*Size);
 527
 528    // Set debug to true to see its decision logic
 529    Debug = _config->FindB("Debug::pkgProblemResolver",false);
 530 }
 531                                                                         /*}}}*/
 532 // ProblemResolver::~pkgProblemResolver - Destructor                    /*{{{*/
 533 // ---------------------------------------------------------------------
 534 /* */
 535 pkgProblemResolver::~pkgProblemResolver()
 536 {
 537    delete [] Scores;
 538    delete [] Flags;
 539 }
 540                                                                         /*}}}*/
 541 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
 542 // ---------------------------------------------------------------------
 543 /* */
 544 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
 545 {
 546    Package const **A = (Package const **)a;
 547    Package const **B = (Package const **)b;
 548    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
 549       return -1;
 550    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
 551       return 1;
 552    return 0;
 553 }
 554                                                                         /*}}}*/
 555 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
 556 // ---------------------------------------------------------------------
 557 /* */
 558 void pkgProblemResolver::MakeScores()
 559 {
 560    unsigned long Size = Cache.Head().PackageCount;
 561    memset(Scores,0,sizeof(*Scores)*Size);
 562
 563    // Important Required Standard Optional Extra
 564    signed short PrioMap[] = {
 565       0,
 566       (signed short) _config->FindI("pkgProblemResolver::Scores::Important",3),
 567       (signed short) _config->FindI("pkgProblemResolver::Scores::Required",2),
 568       (signed short) _config->FindI("pkgProblemResolver::Scores::Standard",1),
 569       (signed short) _config->FindI("pkgProblemResolver::Scores::Optional",-1),
 570       (signed short) _config->FindI("pkgProblemResolver::Scores::Extra",-2)
 571    };
 572    signed short PrioEssentials = _config->FindI("pkgProblemResolver::Scores::Essentials",100);
 573    signed short PrioInstalledAndNotObsolete = _config->FindI("pkgProblemResolver::Scores::NotObsolete",1);
 574    signed short PrioDepends = _config->FindI("pkgProblemResolver::Scores::Depends",1);
 575    signed short PrioRecommends = _config->FindI("pkgProblemResolver::Scores::Recommends",1);
 576    signed short AddProtected = _config->FindI("pkgProblemResolver::Scores::AddProtected",10000);
 577    signed short AddEssential = _config->FindI("pkgProblemResolver::Scores::AddEssential",5000);
 578
 579    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 580       clog << "Settings used to calculate pkgProblemResolver::Scores::" << endl
 581          << "  Important => " << PrioMap[1] << endl
 582          << "  Required => " << PrioMap[2] << endl
 583          << "  Standard => " << PrioMap[3] << endl
 584          << "  Optional => " << PrioMap[4] << endl
 585          << "  Extra => " << PrioMap[5] << endl
 586          << "  Essentials => " << PrioEssentials << endl
 587          << "  InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete << endl
 588          << "  Depends => " << PrioDepends << endl
 589          << "  Recommends => " << PrioRecommends << endl
 590          << "  AddProtected => " << AddProtected << endl
 591          << "  AddEssential => " << AddEssential << endl;
 592
 593    // Generate the base scores for a package based on its properties
 594    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 595    {
 596       if (Cache[I].InstallVer == 0)
 597          continue;
 598
 599       signed short &Score = Scores[I->ID];
 600
 601       /* This is arbitrary, it should be high enough to elevate an
 602          essantial package above most other packages but low enough
 603          to allow an obsolete essential packages to be removed by
 604          a conflicts on a powerfull normal package (ie libc6) */
 605       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 606          Score += PrioEssentials;
 607
 608       // We transform the priority
 609       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 610          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 611
 612       /* This helps to fix oddball problems with conflicting packages
 613          on the same level. We enhance the score of installed packages
 614          if those are not obsolete
 615       */
 616       if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
 617          Score += PrioInstalledAndNotObsolete;
 618    }
 619
 620    // Now that we have the base scores we go and propogate dependencies
 621    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 622    {
 623       if (Cache[I].InstallVer == 0)
 624          continue;
 625
 626       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 627       {
 628          if (D->Type == pkgCache::Dep::Depends ||
 629              D->Type == pkgCache::Dep::PreDepends)
 630             Scores[D.TargetPkg()->ID] += PrioDepends;
 631          else if (D->Type == pkgCache::Dep::Recommends)
 632             Scores[D.TargetPkg()->ID] += PrioRecommends;
 633       }
 634    }
 635
 636    // Copy the scores to advoid additive looping
 637    SPtrArray<signed short> OldScores = new signed short[Size];
 638    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 639
 640    /* Now we cause 1 level of dependency inheritance, that is we add the
 641       score of the packages that depend on the target Package. This
 642       fortifies high scoring packages */
 643    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 644    {
 645       if (Cache[I].InstallVer == 0)
 646          continue;
 647
 648       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 649       {
 650          // Only do it for the install version
 651          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 652              (D->Type != pkgCache::Dep::Depends &&
 653               D->Type != pkgCache::Dep::PreDepends &&
 654               D->Type != pkgCache::Dep::Recommends))
 655             continue;
 656
 657          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 658       }
 659    }
 660
 661    /* Now we propogate along provides. This makes the packages that
 662       provide important packages extremely important */
 663    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 664    {
 665       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 666       {
 667          // Only do it once per package
 668          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 669             continue;
 670          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 671       }
 672    }
 673
 674    /* Protected things are pushed really high up. This number should put them
 675       ahead of everything */
 676    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 677    {
 678       if ((Flags[I->ID] & Protected) != 0)
 679          Scores[I->ID] += AddProtected;
 680       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 681          Scores[I->ID] += AddEssential;
 682    }
 683 }
 684                                                                         /*}}}*/
 685 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 686 // ---------------------------------------------------------------------
 687 /* This goes through and tries to reinstall packages to make this package
 688    installable */
 689 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 690 {
 691    pkgDepCache::ActionGroup group(Cache);
 692
 693    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 694       return false;
 695    if ((Flags[Pkg->ID] & Protected) == Protected)
 696       return false;
 697
 698    Flags[Pkg->ID] &= ~Upgradable;
 699
 700    bool WasKept = Cache[Pkg].Keep();
 701    Cache.MarkInstall(Pkg, false, 0, false);
 702
 703    // This must be a virtual package or something like that.
 704    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 705       return false;
 706
 707    // Isolate the problem dependency
 708    bool Fail = false;
 709    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 710    {
 711       // Compute a single dependency element (glob or)
 712       pkgCache::DepIterator Start = D;
 713       pkgCache::DepIterator End = D;
 714       unsigned char State = 0;
 715       for (bool LastOR = true; D.end() == false && LastOR == true;)
 716       {
 717          State |= Cache[D];
 718          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 719          D++;
 720          if (LastOR == true)
 721             End = D;
 722       }
 723
 724       // We only worry about critical deps.
 725       if (End.IsCritical() != true)
 726          continue;
 727
 728       // Iterate over all the members in the or group
 729       while (1)
 730       {
 731          // Dep is ok now
 732          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 733             break;
 734
 735          // Do not change protected packages
 736          PkgIterator P = Start.SmartTargetPkg();
 737          if ((Flags[P->ID] & Protected) == Protected)
 738          {
 739             if (Debug == true)
 740                clog << "    Reinst Failed because of protected " << P.FullName(false) << endl;
 741             Fail = true;
 742          }
 743          else
 744          {
 745             // Upgrade the package if the candidate version will fix the problem.
 746             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 747             {
 748                if (DoUpgrade(P) == false)
 749                {
 750                   if (Debug == true)
 751                      clog << "    Reinst Failed because of " << P.FullName(false) << endl;
 752                   Fail = true;
 753                }
 754                else
 755                {
 756                   Fail = false;
 757                   break;
 758                }
 759             }
 760             else
 761             {
 762                /* We let the algorithm deal with conflicts on its next iteration,
 763                 it is much smarter than us */
 764                if (Start->Type == pkgCache::Dep::Conflicts ||
 765                    Start->Type == pkgCache::Dep::DpkgBreaks ||
 766                    Start->Type == pkgCache::Dep::Obsoletes)
 767                    break;
 768
 769                if (Debug == true)
 770                   clog << "    Reinst Failed early because of " << Start.TargetPkg().FullName(false) << endl;
 771                Fail = true;
 772             }
 773          }
 774
 775          if (Start == End)
 776             break;
 777          Start++;
 778       }
 779       if (Fail == true)
 780          break;
 781    }
 782
 783    // Undo our operations - it might be smart to undo everything this did..
 784    if (Fail == true)
 785    {
 786       if (WasKept == true)
 787          Cache.MarkKeep(Pkg, false, false);
 788       else
 789          Cache.MarkDelete(Pkg);
 790       return false;
 791    }
 792
 793    if (Debug == true)
 794       clog << "  Re-Instated " << Pkg.FullName(false) << endl;
 795    return true;
 796 }
 797                                                                         /*}}}*/
 798 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 799 // ---------------------------------------------------------------------
 800 /* This routines works by calculating a score for each package. The score
 801    is derived by considering the package's priority and all reverse
 802    dependents giving an integer that reflects the amount of breakage that
 803    adjusting the package will inflict.
 804
 805    It goes from highest score to lowest and corrects all of the breaks by
 806    keeping or removing the dependant packages. If that fails then it removes
 807    the package itself and goes on. The routine should be able to intelligently
 808    go from any broken state to a fixed state.
 809
 810    The BrokenFix flag enables a mode where the algorithm tries to
 811    upgrade packages to advoid problems. */
 812 bool pkgProblemResolver::Resolve(bool BrokenFix)
 813 {
 814    pkgDepCache::ActionGroup group(Cache);
 815
 816    unsigned long Size = Cache.Head().PackageCount;
 817
 818    // Record which packages are marked for install
 819    bool Again = false;
 820    do
 821    {
 822       Again = false;
 823       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 824       {
 825          if (Cache[I].Install() == true)
 826             Flags[I->ID] |= PreInstalled;
 827          else
 828          {
 829             if (Cache[I].InstBroken() == true && BrokenFix == true)
 830             {
 831                Cache.MarkInstall(I, false, 0, false);
 832                if (Cache[I].Install() == true)
 833                   Again = true;
 834             }
 835
 836             Flags[I->ID] &= ~PreInstalled;
 837          }
 838          Flags[I->ID] |= Upgradable;
 839       }
 840    }
 841    while (Again == true);
 842
 843    if (Debug == true)
 844       clog << "Starting" << endl;
 845
 846    MakeScores();
 847
 848    /* We have to order the packages so that the broken fixing pass
 849       operates from highest score to lowest. This prevents problems when
 850       high score packages cause the removal of lower score packages that
 851       would cause the removal of even lower score packages. */
 852    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 853    pkgCache::Package **PEnd = PList;
 854    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 855       *PEnd++ = I;
 856    This = this;
 857    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 858
 859    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 860    {
 861       clog << "Show Scores" << endl;
 862       for (pkgCache::Package **K = PList; K != PEnd; K++)
 863          if (Scores[(*K)->ID] != 0)
 864          {
 865            pkgCache::PkgIterator Pkg(Cache,*K);
 866            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
 867          }
 868    }
 869
 870    if (Debug == true)
 871       clog << "Starting 2" << endl;
 872
 873    /* Now consider all broken packages. For each broken package we either
 874       remove the package or fix it's problem. We do this once, it should
 875       not be possible for a loop to form (that is a < b < c and fixing b by
 876       changing a breaks c) */
 877    bool Change = true;
 878    bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
 879    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 880    {
 881       Change = false;
 882       for (pkgCache::Package **K = PList; K != PEnd; K++)
 883       {
 884          pkgCache::PkgIterator I(Cache,*K);
 885
 886          /* We attempt to install this and see if any breaks result,
 887             this takes care of some strange cases */
 888          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 889              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 890              (Flags[I->ID] & PreInstalled) != 0 &&
 891              (Flags[I->ID] & Protected) == 0 &&
 892              (Flags[I->ID] & ReInstateTried) == 0)
 893          {
 894             if (Debug == true)
 895                clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
 896             unsigned long OldBreaks = Cache.BrokenCount();
 897             pkgCache::Version *OldVer = Cache[I].InstallVer;
 898             Flags[I->ID] &= ReInstateTried;
 899
 900             Cache.MarkInstall(I, false, 0, false);
 901             if (Cache[I].InstBroken() == true ||
 902                 OldBreaks < Cache.BrokenCount())
 903             {
 904                if (OldVer == 0)
 905                   Cache.MarkDelete(I);
 906                else
 907                   Cache.MarkKeep(I, false, false);
 908             }
 909             else
 910                if (Debug == true)
 911                   clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 912          }
 913
 914          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 915             continue;
 916
 917          if (Debug == true)
 918             clog << "Investigating (" << Counter << ") " << I << endl;
 919
 920          // Isolate the problem dependency
 921          PackageKill KillList[100];
 922          PackageKill *LEnd = KillList;
 923          bool InOr = false;
 924          pkgCache::DepIterator Start;
 925          pkgCache::DepIterator End;
 926          PackageKill *OldEnd = LEnd;
 927
 928          enum {OrRemove,OrKeep} OrOp = OrRemove;
 929          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 930               D.end() == false || InOr == true;)
 931          {
 932             // Compute a single dependency element (glob or)
 933             if (Start == End)
 934             {
 935                // Decide what to do
 936                if (InOr == true && OldEnd == LEnd)
 937                {
 938                   if (OrOp == OrRemove)
 939                   {
 940                      if ((Flags[I->ID] & Protected) != Protected)
 941                      {
 942                         if (Debug == true)
 943                            clog << "  Or group remove for " << I.FullName(false) << endl;
 944                         Cache.MarkDelete(I);
 945                         Change = true;
 946                      }
 947                   }
 948                   else if (OrOp == OrKeep)
 949                   {
 950                      if (Debug == true)
 951                         clog << "  Or group keep for " << I.FullName(false) << endl;
 952                      Cache.MarkKeep(I, false, false);
 953                      Change = true;
 954                   }
 955                }
 956
 957                /* We do an extra loop (as above) to finalize the or group
 958                   processing */
 959                InOr = false;
 960                OrOp = OrRemove;
 961                D.GlobOr(Start,End);
 962                if (Start.end() == true)
 963                   break;
 964
 965                // We only worry about critical deps.
 966                if (End.IsCritical() != true)
 967                   continue;
 968
 969                InOr = Start != End;
 970                OldEnd = LEnd;
 971             }
 972             else
 973             {
 974                Start++;
 975                // We only worry about critical deps.
 976                if (Start.IsCritical() != true)
 977                   continue;
 978             }
 979
 980             // Dep is ok
 981             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 982             {
 983                InOr = false;
 984                continue;
 985             }
 986
 987             if (Debug == true)
 988                clog << "Broken " << Start << endl;
 989
 990             /* Look across the version list. If there are no possible
 991                targets then we keep the package and bail. This is necessary
 992                if a package has a dep on another package that cant be found */
 993             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 994             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 995                 Start->Type != pkgCache::Dep::Conflicts &&
 996                 Start->Type != pkgCache::Dep::DpkgBreaks &&
 997                 Start->Type != pkgCache::Dep::Obsoletes &&
 998                 Cache[I].NowBroken() == false)
 999             {
1000                if (InOr == true)
1001                {
1002                   /* No keep choice because the keep being OK could be the
1003                      result of another element in the OR group! */
1004                   continue;
1005                }
1006
1007                Change = true;
1008                Cache.MarkKeep(I, false, false);
1009                break;
1010             }
1011
1012             bool Done = false;
1013             for (pkgCache::Version **V = VList; *V != 0; V++)
1014             {
1015                pkgCache::VerIterator Ver(Cache,*V);
1016                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1017
1018                /* This is a conflicts, and the version we are looking
1019                   at is not the currently selected version of the
1020                   package, which means it is not necessary to
1021                   remove/keep */
1022                if (Cache[Pkg].InstallVer != Ver &&
1023                    (Start->Type == pkgCache::Dep::Conflicts ||
1024                     Start->Type == pkgCache::Dep::DpkgBreaks ||
1025                     Start->Type == pkgCache::Dep::Obsoletes))
1026                {
1027                   if (Debug)
1028                      clog << "  Conflicts//Breaks against version "
1029                           << Ver.VerStr() << " for " << Pkg.Name()
1030                           << " but that is not InstVer, ignoring"
1031                           << endl;
1032                   continue;
1033                }
1034
1035                if (Debug == true)
1036                   clog << "  Considering " << Pkg.FullName(false) << ' ' << (int)Scores[Pkg->ID] <<
1037                   " as a solution to " << I.FullName(false) << ' ' << (int)Scores[I->ID] << endl;
1038
1039                /* Try to fix the package under consideration rather than
1040                   fiddle with the VList package */
1041                if (Scores[I->ID] <= Scores[Pkg->ID] ||
1042                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
1043                     End->Type != pkgCache::Dep::Conflicts &&
1044                     End->Type != pkgCache::Dep::DpkgBreaks &&
1045                     End->Type != pkgCache::Dep::Obsoletes))
1046                {
1047                   // Try a little harder to fix protected packages..
1048                   if ((Flags[I->ID] & Protected) == Protected)
1049                   {
1050                      if (DoUpgrade(Pkg) == true)
1051                      {
1052                         if (Scores[Pkg->ID] > Scores[I->ID])
1053                            Scores[Pkg->ID] = Scores[I->ID];
1054                         break;
1055                      }
1056
1057                      continue;
1058                   }
1059
1060                   /* See if a keep will do, unless the package is protected,
1061                      then installing it will be necessary */
1062                   bool Installed = Cache[I].Install();
1063                   Cache.MarkKeep(I, false, false);
1064                   if (Cache[I].InstBroken() == false)
1065                   {
1066                      // Unwind operation will be keep now
1067                      if (OrOp == OrRemove)
1068                         OrOp = OrKeep;
1069
1070                      // Restore
1071                      if (InOr == true && Installed == true)
1072                         Cache.MarkInstall(I, false, 0, false);
1073
1074                      if (Debug == true)
1075                         clog << "  Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1076                   }
1077                   else
1078                   {
1079                      if (BrokenFix == false || DoUpgrade(I) == false)
1080                      {
1081                         // Consider other options
1082                         if (InOr == false)
1083                         {
1084                            if (Debug == true)
1085                               clog << "  Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1086                            Cache.MarkDelete(I);
1087                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
1088                               Scores[I->ID] = Scores[Pkg->ID];
1089                         }
1090                         else if (TryFixByInstall == true &&
1091                                  Start.TargetPkg()->CurrentVer == 0 &&
1092                                  Cache[Start.TargetPkg()].Delete() == false &&
1093                                  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
1094                                  Cache.GetCandidateVer(Start.TargetPkg()).end() == false)
1095                         {
1096                            /* Before removing or keeping the package with the broken dependency
1097                               try instead to install the first not previously installed package
1098                               solving this dependency. This helps every time a previous solver
1099                               is removed by the resolver because of a conflict or alike but it is
1100                               dangerous as it could trigger new breaks/conflicts… */
1101                            if (Debug == true)
1102                               clog << "  Try Installing " << Start.TargetPkg() << " before changing " << I.FullName(false) << std::endl;
1103                            unsigned long const OldBroken = Cache.BrokenCount();
1104                            Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
1105                            // FIXME: we should undo the complete MarkInstall process here
1106                            if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
1107                               Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
1108                         }
1109                      }
1110                   }
1111
1112                   Change = true;
1113                   Done = true;
1114                   break;
1115                }
1116                else
1117                {
1118                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
1119                   {
1120                      // first, try upgradring the package, if that
1121                      // does not help, the breaks goes onto the
1122                      // kill list
1123                      //
1124                      // FIXME: use DoUpgrade(Pkg) instead?
1125                      if (Cache[End] & pkgDepCache::DepGCVer)
1126                      {
1127                         if (Debug)
1128                            clog << "  Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
1129                         Cache.MarkInstall(Pkg, false, 0, false);
1130                         continue;
1131                      }
1132                   }
1133
1134                   // Skip adding to the kill list if it is protected
1135                   if ((Flags[Pkg->ID] & Protected) != 0)
1136                      continue;
1137
1138                   if (Debug == true)
1139                      clog << "  Added " << Pkg.FullName(false) << " to the remove list" << endl;
1140
1141                   LEnd->Pkg = Pkg;
1142                   LEnd->Dep = End;
1143                   LEnd++;
1144
1145                   if (Start->Type != pkgCache::Dep::Conflicts &&
1146                       Start->Type != pkgCache::Dep::Obsoletes)
1147                      break;
1148                }
1149             }
1150
1151             // Hm, nothing can possibly satisify this dep. Nuke it.
1152             if (VList[0] == 0 &&
1153                 Start->Type != pkgCache::Dep::Conflicts &&
1154                 Start->Type != pkgCache::Dep::DpkgBreaks &&
1155                 Start->Type != pkgCache::Dep::Obsoletes &&
1156                 (Flags[I->ID] & Protected) != Protected)
1157             {
1158                bool Installed = Cache[I].Install();
1159                Cache.MarkKeep(I);
1160                if (Cache[I].InstBroken() == false)
1161                {
1162                   // Unwind operation will be keep now
1163                   if (OrOp == OrRemove)
1164                      OrOp = OrKeep;
1165
1166                   // Restore
1167                   if (InOr == true && Installed == true)
1168                      Cache.MarkInstall(I, false, 0, false);
1169
1170                   if (Debug == true)
1171                      clog << "  Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1172                }
1173                else
1174                {
1175                   if (Debug == true)
1176                      clog << "  Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1177                   if (InOr == false)
1178                      Cache.MarkDelete(I);
1179                }
1180
1181                Change = true;
1182                Done = true;
1183             }
1184
1185             // Try some more
1186             if (InOr == true)
1187                continue;
1188
1189             if (Done == true)
1190                break;
1191          }
1192
1193          // Apply the kill list now
1194          if (Cache[I].InstallVer != 0)
1195          {
1196             for (PackageKill *J = KillList; J != LEnd; J++)
1197             {
1198                Change = true;
1199                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1200                {
1201                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1202                       J->Dep->Type == pkgCache::Dep::DpkgBreaks ||
1203                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1204                   {
1205                      if (Debug == true)
1206                         clog << "  Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
1207                      Cache.MarkDelete(J->Pkg);
1208                   }
1209                }
1210                else
1211                {
1212                   if (Debug == true)
1213                      clog << "  Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
1214                   Cache.MarkKeep(J->Pkg, false, false);
1215                }
1216
1217                if (Counter > 1)
1218                {
1219                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1220                      Scores[J->Pkg->ID] = Scores[I->ID];
1221                }
1222             }
1223          }
1224       }
1225    }
1226
1227    if (Debug == true)
1228       clog << "Done" << endl;
1229
1230    if (Cache.BrokenCount() != 0)
1231    {
1232       // See if this is the result of a hold
1233       pkgCache::PkgIterator I = Cache.PkgBegin();
1234       for (;I.end() != true; I++)
1235       {
1236          if (Cache[I].InstBroken() == false)
1237             continue;
1238          if ((Flags[I->ID] & Protected) != Protected)
1239             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1240       }
1241       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1242    }
1243
1244    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1245    pkgCache::PkgIterator I = Cache.PkgBegin();
1246    for (;I.end() != true; I++) {
1247       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1248          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1249             std::clog << "Resolve installed new pkg: " << I.FullName(false)
1250                       << " (now marking it as auto)" << std::endl;
1251          }
1252          Cache[I].Flags |= pkgCache::Flag::Auto;
1253       }
1254    }
1255
1256
1257    return true;
1258 }
1259                                                                         /*}}}*/
1260 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1261 // ---------------------------------------------------------------------
1262 /* This is the work horse of the soft upgrade routine. It is very gental
1263    in that it does not install or remove any packages. It is assumed that the
1264    system was non-broken previously. */
1265 bool pkgProblemResolver::ResolveByKeep()
1266 {
1267    pkgDepCache::ActionGroup group(Cache);
1268
1269    unsigned long Size = Cache.Head().PackageCount;
1270
1271    MakeScores();
1272
1273    /* We have to order the packages so that the broken fixing pass
1274       operates from highest score to lowest. This prevents problems when
1275       high score packages cause the removal of lower score packages that
1276       would cause the removal of even lower score packages. */
1277    pkgCache::Package **PList = new pkgCache::Package *[Size];
1278    pkgCache::Package **PEnd = PList;
1279    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1280       *PEnd++ = I;
1281    This = this;
1282    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1283
1284    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1285    {
1286       clog << "Show Scores" << endl;
1287       for (pkgCache::Package **K = PList; K != PEnd; K++)
1288          if (Scores[(*K)->ID] != 0)
1289          {
1290            pkgCache::PkgIterator Pkg(Cache,*K);
1291            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1292          }
1293    }
1294
1295    if (Debug == true)
1296       clog << "Entering ResolveByKeep" << endl;
1297
1298    // Consider each broken package
1299    pkgCache::Package **LastStop = 0;
1300    for (pkgCache::Package **K = PList; K != PEnd; K++)
1301    {
1302       pkgCache::PkgIterator I(Cache,*K);
1303
1304       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1305          continue;
1306
1307       /* Keep the package. If this works then great, otherwise we have
1308          to be significantly more agressive and manipulate its dependencies */
1309       if ((Flags[I->ID] & Protected) == 0)
1310       {
1311          if (Debug == true)
1312             clog << "Keeping package " << I.FullName(false) << endl;
1313          Cache.MarkKeep(I, false, false);
1314          if (Cache[I].InstBroken() == false)
1315          {
1316             K = PList - 1;
1317             continue;
1318          }
1319       }
1320
1321       // Isolate the problem dependencies
1322       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1323       {
1324          DepIterator Start;
1325          DepIterator End;
1326          D.GlobOr(Start,End);
1327
1328          // We only worry about critical deps.
1329          if (End.IsCritical() != true)
1330             continue;
1331
1332          // Dep is ok
1333          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1334             continue;
1335
1336          /* Hm, the group is broken.. I suppose the best thing to do is to
1337             is to try every combination of keep/not-keep for the set, but thats
1338             slow, and this never happens, just be conservative and assume the
1339             list of ors is in preference and keep till it starts to work. */
1340          while (true)
1341          {
1342             if (Debug == true)
1343                clog << "Package " << I.FullName(false) << " " << Start << endl;
1344
1345             // Look at all the possible provides on this package
1346             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1347             for (pkgCache::Version **V = VList; *V != 0; V++)
1348             {
1349                pkgCache::VerIterator Ver(Cache,*V);
1350                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1351
1352                // It is not keepable
1353                if (Cache[Pkg].InstallVer == 0 ||
1354                    Pkg->CurrentVer == 0)
1355                   continue;
1356
1357                if ((Flags[I->ID] & Protected) == 0)
1358                {
1359                   if (Debug == true)
1360                      clog << "  Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1361                   Cache.MarkKeep(Pkg, false, false);
1362                }
1363
1364                if (Cache[I].InstBroken() == false)
1365                   break;
1366             }
1367
1368             if (Cache[I].InstBroken() == false)
1369                break;
1370
1371             if (Start == End)
1372                break;
1373             Start++;
1374          }
1375
1376          if (Cache[I].InstBroken() == false)
1377             break;
1378       }
1379
1380       if (Cache[I].InstBroken() == true)
1381          continue;
1382
1383       // Restart again.
1384       if (K == LastStop)
1385          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.FullName(false).c_str());
1386       LastStop = K;
1387       K = PList - 1;
1388    }
1389
1390    return true;
1391 }
1392                                                                         /*}}}*/
1393 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1394 // ---------------------------------------------------------------------
1395 /* This is used to make sure protected packages are installed */
1396 void pkgProblemResolver::InstallProtect()
1397 {
1398    pkgDepCache::ActionGroup group(Cache);
1399
1400    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1401    {
1402       if ((Flags[I->ID] & Protected) == Protected)
1403       {
1404          if ((Flags[I->ID] & ToRemove) == ToRemove)
1405             Cache.MarkDelete(I);
1406          else
1407          {
1408             // preserve the information whether the package was auto
1409             // or manually installed
1410             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1411             Cache.MarkInstall(I, false, 0, !autoInst);
1412          }
1413       }
1414    }
1415 }
1416                                                                         /*}}}*/
1417 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1418 // ---------------------------------------------------------------------
1419 /* This is ment to be used in conjunction with AllTargets to get a list
1420    of versions ordered by preference. */
1421 static pkgCache *PrioCache;
1422 static int PrioComp(const void *A,const void *B)
1423 {
1424    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1425    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1426
1427    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1428        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1429      return 1;
1430    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1431        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1432      return -1;
1433
1434    if (L->Priority != R->Priority)
1435       return R->Priority - L->Priority;
1436    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1437 }
1438 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1439 {
1440    unsigned long Count = 0;
1441    PrioCache = &Cache;
1442    for (pkgCache::Version **I = List; *I != 0; I++)
1443       Count++;
1444    qsort(List,Count,sizeof(*List),PrioComp);
1445 }
1446                                                                         /*}}}*/
1447 // CacheFile::ListUpdate - update the cache files                       /*{{{*/
1448 // ---------------------------------------------------------------------
1449 /* This is a simple wrapper to update the cache. it will fetch stuff
1450  * from the network (or any other sources defined in sources.list)
1451  */
1452 bool ListUpdate(pkgAcquireStatus &Stat,
1453                 pkgSourceList &List,
1454                 int PulseInterval)
1455 {
1456    pkgAcquire::RunResult res;
1457    pkgAcquire Fetcher;
1458    if (Fetcher.Setup(&Stat, _config->FindDir("Dir::State::Lists")) == false)
1459       return false;
1460
1461    // Populate it with the source selection
1462    if (List.GetIndexes(&Fetcher) == false)
1463          return false;
1464
1465    // Run scripts
1466    RunScripts("APT::Update::Pre-Invoke");
1467
1468    // check arguments
1469    if(PulseInterval>0)
1470       res = Fetcher.Run(PulseInterval);
1471    else
1472       res = Fetcher.Run();
1473
1474    if (res == pkgAcquire::Failed)
1475       return false;
1476
1477    bool Failed = false;
1478    bool TransientNetworkFailure = false;
1479    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin();
1480         I != Fetcher.ItemsEnd(); I++)
1481    {
1482       if ((*I)->Status == pkgAcquire::Item::StatDone)
1483          continue;
1484
1485       (*I)->Finished();
1486
1487       ::URI uri((*I)->DescURI());
1488       uri.User.clear();
1489       uri.Password.clear();
1490       string descUri = string(uri);
1491       _error->Warning(_("Failed to fetch %s  %s\n"), descUri.c_str(),
1492               (*I)->ErrorText.c_str());
1493
1494       if ((*I)->Status == pkgAcquire::Item::StatTransientNetworkError)
1495       {
1496          TransientNetworkFailure = true;
1497          continue;
1498       }
1499
1500       Failed = true;
1501    }
1502
1503    // Clean out any old list files
1504    // Keep "APT::Get::List-Cleanup" name for compatibility, but
1505    // this is really a global option for the APT library now
1506    if (!TransientNetworkFailure && !Failed &&
1507        (_config->FindB("APT::Get::List-Cleanup",true) == true &&
1508         _config->FindB("APT::List-Cleanup",true) == true))
1509    {
1510       if (Fetcher.Clean(_config->FindDir("Dir::State::lists")) == false ||
1511           Fetcher.Clean(_config->FindDir("Dir::State::lists") + "partial/") == false)
1512          // something went wrong with the clean
1513          return false;
1514    }
1515
1516    if (TransientNetworkFailure == true)
1517       _error->Warning(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1518    else if (Failed == true)
1519       return _error->Error(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1520
1521
1522    // Run the success scripts if all was fine
1523    if(!TransientNetworkFailure && !Failed)
1524       RunScripts("APT::Update::Post-Invoke-Success");
1525
1526    // Run the other scripts
1527    RunScripts("APT::Update::Post-Invoke");
1528    return true;
1529 }
1530                                                                         /*}}}*/