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 // AllUpgradeNoNewPackages - Upgrade but no removals or new pkgs        /*{{{*/
 426 bool pkgAllUpgradeNoNewPackages(pkgDepCache &Cache)
 427 {
 428    std::string const solver = _config->Find("APT::Solver", "internal");
 429    if (solver != "internal") {
 430       OpTextProgress Prog(*_config);
 431       return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false, &Prog);
 432    }
 433
 434    pkgDepCache::ActionGroup group(Cache);
 435
 436    pkgProblemResolver Fix(&Cache);
 437
 438    if (Cache.BrokenCount() != 0)
 439       return false;
 440
 441    // Upgrade all installed packages
 442    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 443    {
 444       if (Cache[I].Install() == true)
 445          Fix.Protect(I);
 446
 447       if (_config->FindB("APT::Ignore-Hold",false) == false)
 448          if (I->SelectedState == pkgCache::State::Hold)
 449             continue;
 450
 451       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
 452          Cache.MarkInstall(I, false, 0, false);
 453    }
 454
 455    return Fix.ResolveByKeep();
 456 }
 457                                                                         /*}}}*/
 458 // AllUpgradeWithNewInstalls - Upgrade + install new packages as needed /*{{{*/
 459 // ---------------------------------------------------------------------
 460 /* Right now the system must be consistent before this can be called.
 461  * Upgrade as much as possible without deleting anything (useful for
 462  * stable systems)
 463  */
 464 bool pkgAllUpgradeWithNewPackages(pkgDepCache &Cache)
 465 {
 466    pkgDepCache::ActionGroup group(Cache);
 467
 468    pkgProblemResolver Fix(&Cache);
 469
 470    if (Cache.BrokenCount() != 0)
 471       return false;
 472
 473    // provide the initial set of stuff we want to upgrade by marking
 474    // all upgradable packages for upgrade
 475    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 476    {
 477       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
 478       {
 479          if (_config->FindB("APT::Ignore-Hold",false) == false)
 480             if (I->SelectedState == pkgCache::State::Hold)
 481                continue;
 482
 483          Cache.MarkInstall(I, false, 0, false);
 484       }
 485    }
 486
 487    // then let auto-install loose
 488    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 489       if (Cache[I].Install())
 490          Cache.MarkInstall(I, true, 0, false);
 491
 492    // ... but it may remove stuff, we we need to clean up afterwards again
 493    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 494       if (Cache[I].Delete() == true)
 495          Cache.MarkKeep(I, false, false);
 496
 497    // resolve remaining issues via keep
 498    return Fix.ResolveByKeep();
 499 }
 500                                                                         /*}}}*/
 501 // AllUpgrade - Upgrade as many packages as possible                    /*{{{*/
 502 // ---------------------------------------------------------------------
 503 /* Right now the system must be consistent before this can be called.
 504    It also will not change packages marked for install, it only tries
 505    to install packages not marked for install */
 506 bool pkgAllUpgrade(pkgDepCache &Cache)
 507 {
 508    return pkgAllUpgradeNoNewPackages(Cache);
 509 }
 510                                                                         /*}}}*/
 511 // MinimizeUpgrade - Minimizes the set of packages to be upgraded       /*{{{*/
 512 // ---------------------------------------------------------------------
 513 /* This simply goes over the entire set of packages and tries to keep
 514    each package marked for upgrade. If a conflict is generated then
 515    the package is restored. */
 516 bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 517 {
 518    pkgDepCache::ActionGroup group(Cache);
 519
 520    if (Cache.BrokenCount() != 0)
 521       return false;
 522
 523    // We loop for 10 tries to get the minimal set size.
 524    bool Change = false;
 525    unsigned int Count = 0;
 526    do
 527    {
 528       Change = false;
 529       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 530       {
 531          // Not interesting
 532          if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
 533             continue;
 534
 535          // Keep it and see if that is OK
 536          Cache.MarkKeep(I, false, false);
 537          if (Cache.BrokenCount() != 0)
 538             Cache.MarkInstall(I, false, 0, false);
 539          else
 540          {
 541             // If keep didnt actually do anything then there was no change..
 542             if (Cache[I].Upgrade() == false)
 543                Change = true;
 544          }
 545       }
 546       ++Count;
 547    }
 548    while (Change == true && Count < 10);
 549
 550    if (Cache.BrokenCount() != 0)
 551       return _error->Error("Internal Error in pkgMinimizeUpgrade");
 552
 553    return true;
 554 }
 555                                                                         /*}}}*/
 556 // APT::Upgrade::Upgrade - Upgrade using a specific strategy            /*{{{*/
 557 bool APT::Upgrade::Upgrade(pkgDepCache &Cache, APT::Upgrade::UpgradeMode mode)
 558 {
 559    switch(mode) {
 560       case APT::Upgrade::NO_INSTALL_OR_REMOVE:
 561          return pkgAllUpgradeNoNewPackages(Cache);
 562       case APT::Upgrade::ALLOW_NEW_INSTALLS:
 563          return pkgAllUpgradeWithNewPackages(Cache);
 564       case APT::Upgrade::ALLOW_REMOVAL_AND_NEW_INSTALLS:
 565          return pkgDistUpgrade(Cache);
 566       default:
 567          _error->Error("pkgAllUpgrade called with unknwon mode %i", mode);
 568    }
 569    return false;
 570 }
 571                                                                         /*}}}*/
 572 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
 573 // ---------------------------------------------------------------------
 574 /* */
 575 pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : d(NULL), Cache(*pCache)
 576 {
 577    // Allocate memory
 578    unsigned long Size = Cache.Head().PackageCount;
 579    Scores = new int[Size];
 580    Flags = new unsigned char[Size];
 581    memset(Flags,0,sizeof(*Flags)*Size);
 582
 583    // Set debug to true to see its decision logic
 584    Debug = _config->FindB("Debug::pkgProblemResolver",false);
 585 }
 586                                                                         /*}}}*/
 587 // ProblemResolver::~pkgProblemResolver - Destructor                    /*{{{*/
 588 // ---------------------------------------------------------------------
 589 /* */
 590 pkgProblemResolver::~pkgProblemResolver()
 591 {
 592    delete [] Scores;
 593    delete [] Flags;
 594 }
 595                                                                         /*}}}*/
 596 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
 597 // ---------------------------------------------------------------------
 598 /* */
 599 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
 600 {
 601    Package const **A = (Package const **)a;
 602    Package const **B = (Package const **)b;
 603    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
 604       return -1;
 605    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
 606       return 1;
 607    return 0;
 608 }
 609                                                                         /*}}}*/
 610 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
 611 // ---------------------------------------------------------------------
 612 /* */
 613 void pkgProblemResolver::MakeScores()
 614 {
 615    unsigned long Size = Cache.Head().PackageCount;
 616    memset(Scores,0,sizeof(*Scores)*Size);
 617
 618    // maps to pkgCache::State::VerPriority:
 619    //    Required Important Standard Optional Extra
 620    int PrioMap[] = {
 621       0,
 622       _config->FindI("pkgProblemResolver::Scores::Required",3),
 623       _config->FindI("pkgProblemResolver::Scores::Important",2),
 624       _config->FindI("pkgProblemResolver::Scores::Standard",1),
 625       _config->FindI("pkgProblemResolver::Scores::Optional",-1),
 626       _config->FindI("pkgProblemResolver::Scores::Extra",-2)
 627    };
 628    int PrioEssentials = _config->FindI("pkgProblemResolver::Scores::Essentials",100);
 629    int PrioInstalledAndNotObsolete = _config->FindI("pkgProblemResolver::Scores::NotObsolete",1);
 630    int PrioDepends = _config->FindI("pkgProblemResolver::Scores::Depends",1);
 631    int PrioRecommends = _config->FindI("pkgProblemResolver::Scores::Recommends",1);
 632    int AddProtected = _config->FindI("pkgProblemResolver::Scores::AddProtected",10000);
 633    int AddEssential = _config->FindI("pkgProblemResolver::Scores::AddEssential",5000);
 634
 635    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 636       clog << "Settings used to calculate pkgProblemResolver::Scores::" << endl
 637          << "  Required => " << PrioMap[pkgCache::State::Required] << endl
 638          << "  Important => " << PrioMap[pkgCache::State::Important] << endl
 639          << "  Standard => " << PrioMap[pkgCache::State::Standard] << endl
 640          << "  Optional => " << PrioMap[pkgCache::State::Optional] << endl
 641          << "  Extra => " << PrioMap[pkgCache::State::Extra] << endl
 642          << "  Essentials => " << PrioEssentials << endl
 643          << "  InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete << endl
 644          << "  Depends => " << PrioDepends << endl
 645          << "  Recommends => " << PrioRecommends << endl
 646          << "  AddProtected => " << AddProtected << endl
 647          << "  AddEssential => " << AddEssential << endl;
 648
 649    // Generate the base scores for a package based on its properties
 650    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 651    {
 652       if (Cache[I].InstallVer == 0)
 653          continue;
 654
 655       int &Score = Scores[I->ID];
 656
 657       /* This is arbitrary, it should be high enough to elevate an
 658          essantial package above most other packages but low enough
 659          to allow an obsolete essential packages to be removed by
 660          a conflicts on a powerfull normal package (ie libc6) */
 661       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential
 662           || (I->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
 663          Score += PrioEssentials;
 664
 665       // We transform the priority
 666       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 667          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 668
 669       /* This helps to fix oddball problems with conflicting packages
 670          on the same level. We enhance the score of installed packages
 671          if those are not obsolete
 672       */
 673       if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
 674          Score += PrioInstalledAndNotObsolete;
 675    }
 676
 677    // Now that we have the base scores we go and propogate dependencies
 678    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 679    {
 680       if (Cache[I].InstallVer == 0)
 681          continue;
 682
 683       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; ++D)
 684       {
 685          if (D->Type == pkgCache::Dep::Depends ||
 686              D->Type == pkgCache::Dep::PreDepends)
 687             Scores[D.TargetPkg()->ID] += PrioDepends;
 688          else if (D->Type == pkgCache::Dep::Recommends)
 689             Scores[D.TargetPkg()->ID] += PrioRecommends;
 690       }
 691    }
 692
 693    // Copy the scores to advoid additive looping
 694    SPtrArray<int> OldScores = new int[Size];
 695    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 696
 697    /* Now we cause 1 level of dependency inheritance, that is we add the
 698       score of the packages that depend on the target Package. This
 699       fortifies high scoring packages */
 700    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 701    {
 702       if (Cache[I].InstallVer == 0)
 703          continue;
 704
 705       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; ++D)
 706       {
 707          // Only do it for the install version
 708          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 709              (D->Type != pkgCache::Dep::Depends &&
 710               D->Type != pkgCache::Dep::PreDepends &&
 711               D->Type != pkgCache::Dep::Recommends))
 712             continue;
 713
 714          // Do not propagate negative scores otherwise
 715          // an extra (-2) package might score better than an optional (-1)
 716          if (OldScores[D.ParentPkg()->ID] > 0)
 717              Scores[I->ID] += OldScores[D.ParentPkg()->ID];
 718       }
 719    }
 720
 721    /* Now we propogate along provides. This makes the packages that
 722       provide important packages extremely important */
 723    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 724    {
 725       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; ++P)
 726       {
 727          // Only do it once per package
 728          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 729             continue;
 730          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 731       }
 732    }
 733
 734    /* Protected things are pushed really high up. This number should put them
 735       ahead of everything */
 736    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 737    {
 738       if ((Flags[I->ID] & Protected) != 0)
 739          Scores[I->ID] += AddProtected;
 740       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential ||
 741           (I->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
 742          Scores[I->ID] += AddEssential;
 743    }
 744 }
 745                                                                         /*}}}*/
 746 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 747 // ---------------------------------------------------------------------
 748 /* This goes through and tries to reinstall packages to make this package
 749    installable */
 750 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 751 {
 752    pkgDepCache::ActionGroup group(Cache);
 753
 754    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 755       return false;
 756    if ((Flags[Pkg->ID] & Protected) == Protected)
 757       return false;
 758
 759    Flags[Pkg->ID] &= ~Upgradable;
 760
 761    bool WasKept = Cache[Pkg].Keep();
 762    Cache.MarkInstall(Pkg, false, 0, false);
 763
 764    // This must be a virtual package or something like that.
 765    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 766       return false;
 767
 768    // Isolate the problem dependency
 769    bool Fail = false;
 770    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 771    {
 772       // Compute a single dependency element (glob or)
 773       pkgCache::DepIterator Start = D;
 774       pkgCache::DepIterator End = D;
 775       for (bool LastOR = true; D.end() == false && LastOR == true;)
 776       {
 777          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 778          ++D;
 779          if (LastOR == true)
 780             End = D;
 781       }
 782
 783       // We only worry about critical deps.
 784       if (End.IsCritical() != true)
 785          continue;
 786
 787       // Iterate over all the members in the or group
 788       while (1)
 789       {
 790          // Dep is ok now
 791          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 792             break;
 793
 794          // Do not change protected packages
 795          PkgIterator P = Start.SmartTargetPkg();
 796          if ((Flags[P->ID] & Protected) == Protected)
 797          {
 798             if (Debug == true)
 799                clog << "    Reinst Failed because of protected " << P.FullName(false) << endl;
 800             Fail = true;
 801          }
 802          else
 803          {
 804             // Upgrade the package if the candidate version will fix the problem.
 805             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 806             {
 807                if (DoUpgrade(P) == false)
 808                {
 809                   if (Debug == true)
 810                      clog << "    Reinst Failed because of " << P.FullName(false) << endl;
 811                   Fail = true;
 812                }
 813                else
 814                {
 815                   Fail = false;
 816                   break;
 817                }
 818             }
 819             else
 820             {
 821                /* We let the algorithm deal with conflicts on its next iteration,
 822                 it is much smarter than us */
 823                if (Start.IsNegative() == true)
 824                    break;
 825
 826                if (Debug == true)
 827                   clog << "    Reinst Failed early because of " << Start.TargetPkg().FullName(false) << endl;
 828                Fail = true;
 829             }
 830          }
 831
 832          if (Start == End)
 833             break;
 834          ++Start;
 835       }
 836       if (Fail == true)
 837          break;
 838    }
 839
 840    // Undo our operations - it might be smart to undo everything this did..
 841    if (Fail == true)
 842    {
 843       if (WasKept == true)
 844          Cache.MarkKeep(Pkg, false, false);
 845       else
 846          Cache.MarkDelete(Pkg, false, 0, false);
 847       return false;
 848    }
 849
 850    if (Debug == true)
 851       clog << "  Re-Instated " << Pkg.FullName(false) << endl;
 852    return true;
 853 }
 854                                                                         /*}}}*/
 855 // ProblemResolver::Resolve - calls a resolver to fix the situation     /*{{{*/
 856 // ---------------------------------------------------------------------
 857 /* */
 858 bool pkgProblemResolver::Resolve(bool BrokenFix)
 859 {
 860    std::string const solver = _config->Find("APT::Solver", "internal");
 861    if (solver != "internal") {
 862       OpTextProgress Prog(*_config);
 863       return EDSP::ResolveExternal(solver.c_str(), Cache, false, false, false, &Prog);
 864    }
 865    return ResolveInternal(BrokenFix);
 866 }
 867                                                                         /*}}}*/
 868 // ProblemResolver::ResolveInternal - Run the resolution pass           /*{{{*/
 869 // ---------------------------------------------------------------------
 870 /* This routines works by calculating a score for each package. The score
 871    is derived by considering the package's priority and all reverse
 872    dependents giving an integer that reflects the amount of breakage that
 873    adjusting the package will inflict.
 874
 875    It goes from highest score to lowest and corrects all of the breaks by
 876    keeping or removing the dependant packages. If that fails then it removes
 877    the package itself and goes on. The routine should be able to intelligently
 878    go from any broken state to a fixed state.
 879
 880    The BrokenFix flag enables a mode where the algorithm tries to
 881    upgrade packages to advoid problems. */
 882 bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
 883 {
 884    pkgDepCache::ActionGroup group(Cache);
 885
 886    // Record which packages are marked for install
 887    bool Again = false;
 888    do
 889    {
 890       Again = false;
 891       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 892       {
 893          if (Cache[I].Install() == true)
 894             Flags[I->ID] |= PreInstalled;
 895          else
 896          {
 897             if (Cache[I].InstBroken() == true && BrokenFix == true)
 898             {
 899                Cache.MarkInstall(I, false, 0, false);
 900                if (Cache[I].Install() == true)
 901                   Again = true;
 902             }
 903
 904             Flags[I->ID] &= ~PreInstalled;
 905          }
 906          Flags[I->ID] |= Upgradable;
 907       }
 908    }
 909    while (Again == true);
 910
 911    if (Debug == true) {
 912       clog << "Starting pkgProblemResolver with broken count: "
 913            << Cache.BrokenCount() << endl;
 914    }
 915
 916    MakeScores();
 917
 918    unsigned long const Size = Cache.Head().PackageCount;
 919
 920    /* We have to order the packages so that the broken fixing pass
 921       operates from highest score to lowest. This prevents problems when
 922       high score packages cause the removal of lower score packages that
 923       would cause the removal of even lower score packages. */
 924    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 925    pkgCache::Package **PEnd = PList;
 926    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 927       *PEnd++ = I;
 928    This = this;
 929    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 930
 931    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 932    {
 933       clog << "Show Scores" << endl;
 934       for (pkgCache::Package **K = PList; K != PEnd; K++)
 935          if (Scores[(*K)->ID] != 0)
 936          {
 937            pkgCache::PkgIterator Pkg(Cache,*K);
 938            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
 939          }
 940    }
 941
 942    if (Debug == true) {
 943       clog << "Starting 2 pkgProblemResolver with broken count: "
 944            << Cache.BrokenCount() << endl;
 945    }
 946
 947    /* Now consider all broken packages. For each broken package we either
 948       remove the package or fix it's problem. We do this once, it should
 949       not be possible for a loop to form (that is a < b < c and fixing b by
 950       changing a breaks c) */
 951    bool Change = true;
 952    bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
 953    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 954    {
 955       Change = false;
 956       for (pkgCache::Package **K = PList; K != PEnd; K++)
 957       {
 958          pkgCache::PkgIterator I(Cache,*K);
 959
 960          /* We attempt to install this and see if any breaks result,
 961             this takes care of some strange cases */
 962          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 963              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 964              (Flags[I->ID] & PreInstalled) != 0 &&
 965              (Flags[I->ID] & Protected) == 0 &&
 966              (Flags[I->ID] & ReInstateTried) == 0)
 967          {
 968             if (Debug == true)
 969                clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
 970             unsigned long OldBreaks = Cache.BrokenCount();
 971             pkgCache::Version *OldVer = Cache[I].InstallVer;
 972             Flags[I->ID] &= ReInstateTried;
 973
 974             Cache.MarkInstall(I, false, 0, false);
 975             if (Cache[I].InstBroken() == true ||
 976                 OldBreaks < Cache.BrokenCount())
 977             {
 978                if (OldVer == 0)
 979                   Cache.MarkDelete(I, false, 0, false);
 980                else
 981                   Cache.MarkKeep(I, false, false);
 982             }
 983             else
 984                if (Debug == true)
 985                   clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 986          }
 987
 988          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 989             continue;
 990
 991          if (Debug == true)
 992             clog << "Investigating (" << Counter << ") " << I << endl;
 993
 994          // Isolate the problem dependency
 995          PackageKill KillList[100];
 996          PackageKill *LEnd = KillList;
 997          bool InOr = false;
 998          pkgCache::DepIterator Start;
 999          pkgCache::DepIterator End;
1000          PackageKill *OldEnd = LEnd;
1001
1002          enum {OrRemove,OrKeep} OrOp = OrRemove;
1003          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
1004               D.end() == false || InOr == true;)
1005          {
1006             // Compute a single dependency element (glob or)
1007             if (Start == End)
1008             {
1009                // Decide what to do
1010                if (InOr == true && OldEnd == LEnd)
1011                {
1012                   if (OrOp == OrRemove)
1013                   {
1014                      if ((Flags[I->ID] & Protected) != Protected)
1015                      {
1016                         if (Debug == true)
1017                            clog << "  Or group remove for " << I.FullName(false) << endl;
1018                         Cache.MarkDelete(I, false, 0, false);
1019                         Change = true;
1020                      }
1021                   }
1022                   else if (OrOp == OrKeep)
1023                   {
1024                      if (Debug == true)
1025                         clog << "  Or group keep for " << I.FullName(false) << endl;
1026                      Cache.MarkKeep(I, false, false);
1027                      Change = true;
1028                   }
1029                }
1030
1031                /* We do an extra loop (as above) to finalize the or group
1032                   processing */
1033                InOr = false;
1034                OrOp = OrRemove;
1035                D.GlobOr(Start,End);
1036                if (Start.end() == true)
1037                   break;
1038
1039                // We only worry about critical deps.
1040                if (End.IsCritical() != true)
1041                   continue;
1042
1043                InOr = Start != End;
1044                OldEnd = LEnd;
1045             }
1046             else
1047             {
1048                ++Start;
1049                // We only worry about critical deps.
1050                if (Start.IsCritical() != true)
1051                   continue;
1052             }
1053
1054             // Dep is ok
1055             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1056             {
1057                InOr = false;
1058                continue;
1059             }
1060
1061             if (Debug == true)
1062                clog << "Broken " << Start << endl;
1063
1064             /* Look across the version list. If there are no possible
1065                targets then we keep the package and bail. This is necessary
1066                if a package has a dep on another package that cant be found */
1067             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1068             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
1069                 Start.IsNegative() == false &&
1070                 Cache[I].NowBroken() == false)
1071             {
1072                if (InOr == true)
1073                {
1074                   /* No keep choice because the keep being OK could be the
1075                      result of another element in the OR group! */
1076                   continue;
1077                }
1078
1079                Change = true;
1080                Cache.MarkKeep(I, false, false);
1081                break;
1082             }
1083
1084             bool Done = false;
1085             for (pkgCache::Version **V = VList; *V != 0; V++)
1086             {
1087                pkgCache::VerIterator Ver(Cache,*V);
1088                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1089
1090                /* This is a conflicts, and the version we are looking
1091                   at is not the currently selected version of the
1092                   package, which means it is not necessary to
1093                   remove/keep */
1094                if (Cache[Pkg].InstallVer != Ver && Start.IsNegative() == true)
1095                {
1096                   if (Debug)
1097                      clog << "  Conflicts//Breaks against version "
1098                           << Ver.VerStr() << " for " << Pkg.Name()
1099                           << " but that is not InstVer, ignoring"
1100                           << endl;
1101                   continue;
1102                }
1103
1104                if (Debug == true)
1105                   clog << "  Considering " << Pkg.FullName(false) << ' ' << (int)Scores[Pkg->ID] <<
1106                   " as a solution to " << I.FullName(false) << ' ' << (int)Scores[I->ID] << endl;
1107
1108                /* Try to fix the package under consideration rather than
1109                   fiddle with the VList package */
1110                if (Scores[I->ID] <= Scores[Pkg->ID] ||
1111                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
1112                     End.IsNegative() == false))
1113                {
1114                   // Try a little harder to fix protected packages..
1115                   if ((Flags[I->ID] & Protected) == Protected)
1116                   {
1117                      if (DoUpgrade(Pkg) == true)
1118                      {
1119                         if (Scores[Pkg->ID] > Scores[I->ID])
1120                            Scores[Pkg->ID] = Scores[I->ID];
1121                         break;
1122                      }
1123
1124                      continue;
1125                   }
1126
1127                   /* See if a keep will do, unless the package is protected,
1128                      then installing it will be necessary */
1129                   bool Installed = Cache[I].Install();
1130                   Cache.MarkKeep(I, false, false);
1131                   if (Cache[I].InstBroken() == false)
1132                   {
1133                      // Unwind operation will be keep now
1134                      if (OrOp == OrRemove)
1135                         OrOp = OrKeep;
1136
1137                      // Restore
1138                      if (InOr == true && Installed == true)
1139                         Cache.MarkInstall(I, false, 0, false);
1140
1141                      if (Debug == true)
1142                         clog << "  Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1143                   }
1144                   else
1145                   {
1146                      if (BrokenFix == false || DoUpgrade(I) == false)
1147                      {
1148                         // Consider other options
1149                         if (InOr == false || Cache[I].Garbage == true)
1150                         {
1151                            if (Debug == true)
1152                               clog << "  Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1153                            Cache.MarkDelete(I, false, 0, false);
1154                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
1155                               Scores[I->ID] = Scores[Pkg->ID];
1156                         }
1157                         else if (TryFixByInstall == true &&
1158                                  Start.TargetPkg()->CurrentVer == 0 &&
1159                                  Cache[Start.TargetPkg()].Delete() == false &&
1160                                  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
1161                                  Cache.GetCandidateVer(Start.TargetPkg()).end() == false)
1162                         {
1163                            /* Before removing or keeping the package with the broken dependency
1164                               try instead to install the first not previously installed package
1165                               solving this dependency. This helps every time a previous solver
1166                               is removed by the resolver because of a conflict or alike but it is
1167                               dangerous as it could trigger new breaks/conflicts… */
1168                            if (Debug == true)
1169                               clog << "  Try Installing " << Start.TargetPkg() << " before changing " << I.FullName(false) << std::endl;
1170                            unsigned long const OldBroken = Cache.BrokenCount();
1171                            Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
1172                            // FIXME: we should undo the complete MarkInstall process here
1173                            if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
1174                               Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
1175                         }
1176                      }
1177                   }
1178
1179                   Change = true;
1180                   Done = true;
1181                   break;
1182                }
1183                else
1184                {
1185                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
1186                   {
1187                      // first, try upgradring the package, if that
1188                      // does not help, the breaks goes onto the
1189                      // kill list
1190                      //
1191                      // FIXME: use DoUpgrade(Pkg) instead?
1192                      if (Cache[End] & pkgDepCache::DepGCVer)
1193                      {
1194                         if (Debug)
1195                            clog << "  Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
1196                         Cache.MarkInstall(Pkg, false, 0, false);
1197                         continue;
1198                      }
1199                   }
1200
1201                   // Skip adding to the kill list if it is protected
1202                   if ((Flags[Pkg->ID] & Protected) != 0)
1203                      continue;
1204
1205                   if (Debug == true)
1206                      clog << "  Added " << Pkg.FullName(false) << " to the remove list" << endl;
1207
1208                   LEnd->Pkg = Pkg;
1209                   LEnd->Dep = End;
1210                   LEnd++;
1211
1212                   if (Start.IsNegative() == false)
1213                      break;
1214                }
1215             }
1216
1217             // Hm, nothing can possibly satisify this dep. Nuke it.
1218             if (VList[0] == 0 &&
1219                 Start.IsNegative() == false &&
1220                 (Flags[I->ID] & Protected) != Protected)
1221             {
1222                bool Installed = Cache[I].Install();
1223                Cache.MarkKeep(I);
1224                if (Cache[I].InstBroken() == false)
1225                {
1226                   // Unwind operation will be keep now
1227                   if (OrOp == OrRemove)
1228                      OrOp = OrKeep;
1229
1230                   // Restore
1231                   if (InOr == true && Installed == true)
1232                      Cache.MarkInstall(I, false, 0, false);
1233
1234                   if (Debug == true)
1235                      clog << "  Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1236                }
1237                else
1238                {
1239                   if (Debug == true)
1240                      clog << "  Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1241                   if (InOr == false)
1242                      Cache.MarkDelete(I, false, 0, false);
1243                }
1244
1245                Change = true;
1246                Done = true;
1247             }
1248
1249             // Try some more
1250             if (InOr == true)
1251                continue;
1252
1253             if (Done == true)
1254                break;
1255          }
1256
1257          // Apply the kill list now
1258          if (Cache[I].InstallVer != 0)
1259          {
1260             for (PackageKill *J = KillList; J != LEnd; J++)
1261             {
1262                Change = true;
1263                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1264                {
1265                   if (J->Dep.IsNegative() == true)
1266                   {
1267                      if (Debug == true)
1268                         clog << "  Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
1269                      Cache.MarkDelete(J->Pkg, false, 0, false);
1270                   }
1271                }
1272                else
1273                {
1274                   if (Debug == true)
1275                      clog << "  Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
1276                   Cache.MarkKeep(J->Pkg, false, false);
1277                }
1278
1279                if (Counter > 1)
1280                {
1281                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1282                      Scores[J->Pkg->ID] = Scores[I->ID];
1283                }
1284             }
1285          }
1286       }
1287    }
1288
1289    if (Debug == true)
1290       clog << "Done" << endl;
1291
1292    if (Cache.BrokenCount() != 0)
1293    {
1294       // See if this is the result of a hold
1295       pkgCache::PkgIterator I = Cache.PkgBegin();
1296       for (;I.end() != true; ++I)
1297       {
1298          if (Cache[I].InstBroken() == false)
1299             continue;
1300          if ((Flags[I->ID] & Protected) != Protected)
1301             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1302       }
1303       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1304    }
1305
1306    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1307    pkgCache::PkgIterator I = Cache.PkgBegin();
1308    for (;I.end() != true; ++I) {
1309       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1310          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1311             std::clog << "Resolve installed new pkg: " << I.FullName(false)
1312                       << " (now marking it as auto)" << std::endl;
1313          }
1314          Cache[I].Flags |= pkgCache::Flag::Auto;
1315       }
1316    }
1317
1318
1319    return true;
1320 }
1321                                                                         /*}}}*/
1322 // ProblemResolver::BreaksInstOrPolicy - Check if the given pkg is broken/*{{{*/
1323 // ---------------------------------------------------------------------
1324 /* This checks if the given package is broken either by a hard dependency
1325    (InstBroken()) or by introducing a new policy breakage e.g. new
1326    unsatisfied recommends for a package that was in "policy-good" state
1327
1328    Note that this is not perfect as it will ignore further breakage
1329    for already broken policy (recommends)
1330 */
1331 bool pkgProblemResolver::InstOrNewPolicyBroken(pkgCache::PkgIterator I)
1332 {
1333    // a broken install is always a problem
1334    if (Cache[I].InstBroken() == true)
1335    {
1336       if (Debug == true)
1337          std::clog << "  Dependencies are not satisfied for " << I << std::endl;
1338       return true;
1339    }
1340
1341    // a newly broken policy (recommends/suggests) is a problem
1342    if (Cache[I].NowPolicyBroken() == false &&
1343        Cache[I].InstPolicyBroken() == true)
1344    {
1345       if (Debug == true)
1346          std::clog << "  Policy breaks with upgrade of " << I << std::endl;
1347       return true;
1348    }
1349
1350    return false;
1351 }
1352                                                                         /*}}}*/
1353 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1354 // ---------------------------------------------------------------------
1355 /* This is the work horse of the soft upgrade routine. It is very gental
1356    in that it does not install or remove any packages. It is assumed that the
1357    system was non-broken previously. */
1358 bool pkgProblemResolver::ResolveByKeep()
1359 {
1360    std::string const solver = _config->Find("APT::Solver", "internal");
1361    if (solver != "internal") {
1362       OpTextProgress Prog(*_config);
1363       return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false, &Prog);
1364    }
1365    return ResolveByKeepInternal();
1366 }
1367                                                                         /*}}}*/
1368 // ProblemResolver::ResolveByKeepInternal - Resolve problems using keep /*{{{*/
1369 // ---------------------------------------------------------------------
1370 /* This is the work horse of the soft upgrade routine. It is very gental
1371    in that it does not install or remove any packages. It is assumed that the
1372    system was non-broken previously. */
1373 bool pkgProblemResolver::ResolveByKeepInternal()
1374 {
1375    pkgDepCache::ActionGroup group(Cache);
1376
1377    unsigned long Size = Cache.Head().PackageCount;
1378
1379    MakeScores();
1380
1381    /* We have to order the packages so that the broken fixing pass
1382       operates from highest score to lowest. This prevents problems when
1383       high score packages cause the removal of lower score packages that
1384       would cause the removal of even lower score packages. */
1385    pkgCache::Package **PList = new pkgCache::Package *[Size];
1386    pkgCache::Package **PEnd = PList;
1387    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1388       *PEnd++ = I;
1389    This = this;
1390    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1391
1392    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1393    {
1394       clog << "Show Scores" << endl;
1395       for (pkgCache::Package **K = PList; K != PEnd; K++)
1396          if (Scores[(*K)->ID] != 0)
1397          {
1398            pkgCache::PkgIterator Pkg(Cache,*K);
1399            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1400          }
1401    }
1402
1403    if (Debug == true)
1404       clog << "Entering ResolveByKeep" << endl;
1405
1406    // Consider each broken package
1407    pkgCache::Package **LastStop = 0;
1408    for (pkgCache::Package **K = PList; K != PEnd; K++)
1409    {
1410       pkgCache::PkgIterator I(Cache,*K);
1411
1412       if (Cache[I].InstallVer == 0)
1413          continue;
1414
1415       if (InstOrNewPolicyBroken(I) == false)
1416          continue;
1417
1418       /* Keep the package. If this works then great, otherwise we have
1419          to be significantly more agressive and manipulate its dependencies */
1420       if ((Flags[I->ID] & Protected) == 0)
1421       {
1422          if (Debug == true)
1423             clog << "Keeping package " << I.FullName(false) << endl;
1424          Cache.MarkKeep(I, false, false);
1425          if (InstOrNewPolicyBroken(I) == false)
1426          {
1427             K = PList - 1;
1428             continue;
1429          }
1430       }
1431
1432       // Isolate the problem dependencies
1433       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1434       {
1435          DepIterator Start;
1436          DepIterator End;
1437          D.GlobOr(Start,End);
1438
1439          // We only worry about critical deps.
1440          if (End.IsCritical() != true)
1441             continue;
1442
1443          // Dep is ok
1444          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1445             continue;
1446
1447          /* Hm, the group is broken.. I suppose the best thing to do is to
1448             is to try every combination of keep/not-keep for the set, but thats
1449             slow, and this never happens, just be conservative and assume the
1450             list of ors is in preference and keep till it starts to work. */
1451          while (true)
1452          {
1453             if (Debug == true)
1454                clog << "Package " << I.FullName(false) << " " << Start << endl;
1455
1456             // Look at all the possible provides on this package
1457             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1458             for (pkgCache::Version **V = VList; *V != 0; V++)
1459             {
1460                pkgCache::VerIterator Ver(Cache,*V);
1461                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1462
1463                // It is not keepable
1464                if (Cache[Pkg].InstallVer == 0 ||
1465                    Pkg->CurrentVer == 0)
1466                   continue;
1467
1468                if ((Flags[I->ID] & Protected) == 0)
1469                {
1470                   if (Debug == true)
1471                      clog << "  Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1472                   Cache.MarkKeep(Pkg, false, false);
1473                }
1474
1475                if (InstOrNewPolicyBroken(I) == false)
1476                   break;
1477             }
1478
1479             if (InstOrNewPolicyBroken(I) == false)
1480                break;
1481
1482             if (Start == End)
1483                break;
1484             ++Start;
1485          }
1486
1487          if (InstOrNewPolicyBroken(I) == false)
1488             break;
1489       }
1490
1491       if (InstOrNewPolicyBroken(I) == true)
1492          continue;
1493
1494       // Restart again.
1495       if (K == LastStop) {
1496           // I is an iterator based off our temporary package list,
1497           // so copy the name we need before deleting the temporary list
1498           std::string const LoopingPackage = I.FullName(false);
1499           delete[] PList;
1500           return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.", LoopingPackage.c_str());
1501       }
1502       LastStop = K;
1503       K = PList - 1;
1504    }
1505
1506    delete[] PList;
1507    return true;
1508 }
1509                                                                         /*}}}*/
1510 // ProblemResolver::InstallProtect - deprecated cpu-eating no-op        /*{{{*/
1511 // ---------------------------------------------------------------------
1512 /* Actions issued with FromUser bit set are protected from further
1513    modification (expect by other calls with FromUser set) nowadays , so we
1514    don't need to reissue actions here, they are already set in stone. */
1515 void pkgProblemResolver::InstallProtect()
1516 {
1517    pkgDepCache::ActionGroup group(Cache);
1518
1519    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1520    {
1521       if ((Flags[I->ID] & Protected) == Protected)
1522       {
1523          if ((Flags[I->ID] & ToRemove) == ToRemove)
1524             Cache.MarkDelete(I);
1525          else
1526          {
1527             // preserve the information whether the package was auto
1528             // or manually installed
1529             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1530             Cache.MarkInstall(I, false, 0, !autoInst);
1531          }
1532       }
1533    }
1534 }
1535                                                                         /*}}}*/
1536 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1537 // ---------------------------------------------------------------------
1538 /* This is ment to be used in conjunction with AllTargets to get a list
1539    of versions ordered by preference. */
1540 static pkgCache *PrioCache;
1541 static int PrioComp(const void *A,const void *B)
1542 {
1543    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1544    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1545
1546    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1547        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1548      return 1;
1549    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1550        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1551      return -1;
1552
1553    if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important &&
1554        (R.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important)
1555      return 1;
1556    if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important &&
1557        (R.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1558      return -1;
1559
1560    if (L->Priority != R->Priority)
1561       return R->Priority - L->Priority;
1562    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1563 }
1564 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1565 {
1566    unsigned long Count = 0;
1567    PrioCache = &Cache;
1568    for (pkgCache::Version **I = List; *I != 0; I++)
1569       Count++;
1570    qsort(List,Count,sizeof(*List),PrioComp);
1571 }
1572                                                                         /*}}}*/
1573 // ListUpdate - construct Fetcher and update the cache files            /*{{{*/
1574 // ---------------------------------------------------------------------
1575 /* This is a simple wrapper to update the cache. it will fetch stuff
1576  * from the network (or any other sources defined in sources.list)
1577  */
1578 bool ListUpdate(pkgAcquireStatus &Stat,
1579                 pkgSourceList &List,
1580                 int PulseInterval)
1581 {
1582    pkgAcquire Fetcher;
1583    if (Fetcher.Setup(&Stat, _config->FindDir("Dir::State::Lists")) == false)
1584       return false;
1585
1586    // Populate it with the source selection
1587    if (List.GetIndexes(&Fetcher) == false)
1588          return false;
1589
1590    return AcquireUpdate(Fetcher, PulseInterval, true);
1591 }
1592                                                                         /*}}}*/
1593 // AcquireUpdate - take Fetcher and update the cache files              /*{{{*/
1594 // ---------------------------------------------------------------------
1595 /* This is a simple wrapper to update the cache with a provided acquire
1596  * If you only need control over Status and the used SourcesList use
1597  * ListUpdate method instead.
1598  */
1599 bool AcquireUpdate(pkgAcquire &Fetcher, int const PulseInterval,
1600                    bool const RunUpdateScripts, bool const ListCleanup)
1601 {
1602    // Run scripts
1603    if (RunUpdateScripts == true)
1604       RunScripts("APT::Update::Pre-Invoke");
1605
1606    pkgAcquire::RunResult res;
1607    if(PulseInterval > 0)
1608       res = Fetcher.Run(PulseInterval);
1609    else
1610       res = Fetcher.Run();
1611
1612    if (res == pkgAcquire::Failed)
1613       return false;
1614
1615    bool Failed = false;
1616    bool TransientNetworkFailure = false;
1617    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin();
1618         I != Fetcher.ItemsEnd(); ++I)
1619    {
1620       if ((*I)->Status == pkgAcquire::Item::StatDone)
1621          continue;
1622
1623       (*I)->Finished();
1624
1625       ::URI uri((*I)->DescURI());
1626       uri.User.clear();
1627       uri.Password.clear();
1628       string descUri = string(uri);
1629       _error->Warning(_("Failed to fetch %s  %s\n"), descUri.c_str(),
1630               (*I)->ErrorText.c_str());
1631
1632       if ((*I)->Status == pkgAcquire::Item::StatTransientNetworkError)
1633       {
1634          TransientNetworkFailure = true;
1635          continue;
1636       }
1637
1638       Failed = true;
1639    }
1640
1641    // Clean out any old list files
1642    // Keep "APT::Get::List-Cleanup" name for compatibility, but
1643    // this is really a global option for the APT library now
1644    if (!TransientNetworkFailure && !Failed && ListCleanup == true &&
1645        (_config->FindB("APT::Get::List-Cleanup",true) == true &&
1646         _config->FindB("APT::List-Cleanup",true) == true))
1647    {
1648       if (Fetcher.Clean(_config->FindDir("Dir::State::lists")) == false ||
1649           Fetcher.Clean(_config->FindDir("Dir::State::lists") + "partial/") == false)
1650          // something went wrong with the clean
1651          return false;
1652    }
1653
1654    if (TransientNetworkFailure == true)
1655       _error->Warning(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1656    else if (Failed == true)
1657       return _error->Error(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1658
1659
1660    // Run the success scripts if all was fine
1661    if (RunUpdateScripts == true)
1662    {
1663       if(!TransientNetworkFailure && !Failed)
1664          RunScripts("APT::Update::Post-Invoke-Success");
1665
1666       // Run the other scripts
1667       RunScripts("APT::Update::Post-Invoke");
1668    }
1669    return true;
1670 }
1671                                                                         /*}}}*/