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