apt-pkg/algorithms.cc

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