apt-pkg/algorithms.cc

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