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