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, broken count: " << Cache.BrokenCount() << endl;
 850    }
 851
 852    MakeScores();
 853
 854    unsigned long const Size = Cache.Head().PackageCount;
 855
 856    /* We have to order the packages so that the broken fixing pass
 857       operates from highest score to lowest. This prevents problems when
 858       high score packages cause the removal of lower score packages that
 859       would cause the removal of even lower score packages. */
 860    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 861    pkgCache::Package **PEnd = PList;
 862    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 863       *PEnd++ = I;
 864    This = this;
 865    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 866
 867    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 868    {
 869       clog << "Show Scores" << endl;
 870       for (pkgCache::Package **K = PList; K != PEnd; K++)
 871          if (Scores[(*K)->ID] != 0)
 872          {
 873            pkgCache::PkgIterator Pkg(Cache,*K);
 874            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
 875          }
 876    }
 877
 878    if (Debug == true) {
 879       clog << "Starting 2, broken count: " << Cache.BrokenCount() << endl;
 880    }
 881
 882    /* Now consider all broken packages. For each broken package we either
 883       remove the package or fix it's problem. We do this once, it should
 884       not be possible for a loop to form (that is a < b < c and fixing b by
 885       changing a breaks c) */
 886    bool Change = true;
 887    bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
 888    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 889    {
 890       Change = false;
 891       for (pkgCache::Package **K = PList; K != PEnd; K++)
 892       {
 893          pkgCache::PkgIterator I(Cache,*K);
 894
 895          /* We attempt to install this and see if any breaks result,
 896             this takes care of some strange cases */
 897          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 898              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 899              (Flags[I->ID] & PreInstalled) != 0 &&
 900              (Flags[I->ID] & Protected) == 0 &&
 901              (Flags[I->ID] & ReInstateTried) == 0)
 902          {
 903             if (Debug == true)
 904                clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
 905             unsigned long OldBreaks = Cache.BrokenCount();
 906             pkgCache::Version *OldVer = Cache[I].InstallVer;
 907             Flags[I->ID] &= ReInstateTried;
 908
 909             Cache.MarkInstall(I, false, 0, false);
 910             if (Cache[I].InstBroken() == true ||
 911                 OldBreaks < Cache.BrokenCount())
 912             {
 913                if (OldVer == 0)
 914                   Cache.MarkDelete(I, false, 0, false);
 915                else
 916                   Cache.MarkKeep(I, false, false);
 917             }
 918             else
 919                if (Debug == true)
 920                   clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 921          }
 922
 923          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 924             continue;
 925
 926          if (Debug == true)
 927             clog << "Investigating (" << Counter << ") " << I << endl;
 928
 929          // Isolate the problem dependency
 930          PackageKill KillList[100];
 931          PackageKill *LEnd = KillList;
 932          bool InOr = false;
 933          pkgCache::DepIterator Start;
 934          pkgCache::DepIterator End;
 935          PackageKill *OldEnd = LEnd;
 936
 937          enum {OrRemove,OrKeep} OrOp = OrRemove;
 938          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 939               D.end() == false || InOr == true;)
 940          {
 941             // Compute a single dependency element (glob or)
 942             if (Start == End)
 943             {
 944                // Decide what to do
 945                if (InOr == true && OldEnd == LEnd)
 946                {
 947                   if (OrOp == OrRemove)
 948                   {
 949                      if ((Flags[I->ID] & Protected) != Protected)
 950                      {
 951                         if (Debug == true)
 952                            clog << "  Or group remove for " << I.FullName(false) << endl;
 953                         Cache.MarkDelete(I, false, 0, false);
 954                         Change = true;
 955                      }
 956                   }
 957                   else if (OrOp == OrKeep)
 958                   {
 959                      if (Debug == true)
 960                         clog << "  Or group keep for " << I.FullName(false) << endl;
 961                      Cache.MarkKeep(I, false, false);
 962                      Change = true;
 963                   }
 964                }
 965
 966                /* We do an extra loop (as above) to finalize the or group
 967                   processing */
 968                InOr = false;
 969                OrOp = OrRemove;
 970                D.GlobOr(Start,End);
 971                if (Start.end() == true)
 972                   break;
 973
 974                // We only worry about critical deps.
 975                if (End.IsCritical() != true)
 976                   continue;
 977
 978                InOr = Start != End;
 979                OldEnd = LEnd;
 980             }
 981             else
 982             {
 983                ++Start;
 984                // We only worry about critical deps.
 985                if (Start.IsCritical() != true)
 986                   continue;
 987             }
 988
 989             // Dep is ok
 990             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 991             {
 992                InOr = false;
 993                continue;
 994             }
 995
 996             if (Debug == true)
 997                clog << "Broken " << Start << endl;
 998
 999             /* Look across the version list. If there are no possible
1000                targets then we keep the package and bail. This is necessary
1001                if a package has a dep on another package that cant be found */
1002             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1003             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
1004                 Start.IsNegative() == false &&
1005                 Cache[I].NowBroken() == false)
1006             {
1007                if (InOr == true)
1008                {
1009                   /* No keep choice because the keep being OK could be the
1010                      result of another element in the OR group! */
1011                   continue;
1012                }
1013
1014                Change = true;
1015                Cache.MarkKeep(I, false, false);
1016                break;
1017             }
1018
1019             bool Done = false;
1020             for (pkgCache::Version **V = VList; *V != 0; V++)
1021             {
1022                pkgCache::VerIterator Ver(Cache,*V);
1023                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1024
1025                /* This is a conflicts, and the version we are looking
1026                   at is not the currently selected version of the
1027                   package, which means it is not necessary to
1028                   remove/keep */
1029                if (Cache[Pkg].InstallVer != Ver && Start.IsNegative() == true)
1030                {
1031                   if (Debug)
1032                      clog << "  Conflicts//Breaks against version "
1033                           << Ver.VerStr() << " for " << Pkg.Name()
1034                           << " but that is not InstVer, ignoring"
1035                           << endl;
1036                   continue;
1037                }
1038
1039                if (Debug == true)
1040                   clog << "  Considering " << Pkg.FullName(false) << ' ' << (int)Scores[Pkg->ID] <<
1041                   " as a solution to " << I.FullName(false) << ' ' << (int)Scores[I->ID] << endl;
1042
1043                /* Try to fix the package under consideration rather than
1044                   fiddle with the VList package */
1045                if (Scores[I->ID] <= Scores[Pkg->ID] ||
1046                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
1047                     End.IsNegative() == false))
1048                {
1049                   // Try a little harder to fix protected packages..
1050                   if ((Flags[I->ID] & Protected) == Protected)
1051                   {
1052                      if (DoUpgrade(Pkg) == true)
1053                      {
1054                         if (Scores[Pkg->ID] > Scores[I->ID])
1055                            Scores[Pkg->ID] = Scores[I->ID];
1056                         break;
1057                      }
1058
1059                      continue;
1060                   }
1061
1062                   /* See if a keep will do, unless the package is protected,
1063                      then installing it will be necessary */
1064                   bool Installed = Cache[I].Install();
1065                   Cache.MarkKeep(I, false, false);
1066                   if (Cache[I].InstBroken() == false)
1067                   {
1068                      // Unwind operation will be keep now
1069                      if (OrOp == OrRemove)
1070                         OrOp = OrKeep;
1071
1072                      // Restore
1073                      if (InOr == true && Installed == true)
1074                         Cache.MarkInstall(I, false, 0, false);
1075
1076                      if (Debug == true)
1077                         clog << "  Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1078                   }
1079                   else
1080                   {
1081                      if (BrokenFix == false || DoUpgrade(I) == false)
1082                      {
1083                         // Consider other options
1084                         if (InOr == false || Cache[I].Garbage == true)
1085                         {
1086                            if (Debug == true)
1087                               clog << "  Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1088                            Cache.MarkDelete(I, false, 0, false);
1089                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
1090                               Scores[I->ID] = Scores[Pkg->ID];
1091                         }
1092                         else if (TryFixByInstall == true &&
1093                                  Start.TargetPkg()->CurrentVer == 0 &&
1094                                  Cache[Start.TargetPkg()].Delete() == false &&
1095                                  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
1096                                  Cache.GetCandidateVer(Start.TargetPkg()).end() == false)
1097                         {
1098                            /* Before removing or keeping the package with the broken dependency
1099                               try instead to install the first not previously installed package
1100                               solving this dependency. This helps every time a previous solver
1101                               is removed by the resolver because of a conflict or alike but it is
1102                               dangerous as it could trigger new breaks/conflicts… */
1103                            if (Debug == true)
1104                               clog << "  Try Installing " << Start.TargetPkg() << " before changing " << I.FullName(false) << std::endl;
1105                            unsigned long const OldBroken = Cache.BrokenCount();
1106                            Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
1107                            // FIXME: we should undo the complete MarkInstall process here
1108                            if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
1109                               Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
1110                         }
1111                      }
1112                   }
1113
1114                   Change = true;
1115                   Done = true;
1116                   break;
1117                }
1118                else
1119                {
1120                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
1121                   {
1122                      // first, try upgradring the package, if that
1123                      // does not help, the breaks goes onto the
1124                      // kill list
1125                      //
1126                      // FIXME: use DoUpgrade(Pkg) instead?
1127                      if (Cache[End] & pkgDepCache::DepGCVer)
1128                      {
1129                         if (Debug)
1130                            clog << "  Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
1131                         Cache.MarkInstall(Pkg, false, 0, false);
1132                         continue;
1133                      }
1134                   }
1135
1136                   // Skip adding to the kill list if it is protected
1137                   if ((Flags[Pkg->ID] & Protected) != 0)
1138                      continue;
1139
1140                   if (Debug == true)
1141                      clog << "  Added " << Pkg.FullName(false) << " to the remove list" << endl;
1142
1143                   LEnd->Pkg = Pkg;
1144                   LEnd->Dep = End;
1145                   LEnd++;
1146
1147                   if (Start.IsNegative() == false)
1148                      break;
1149                }
1150             }
1151
1152             // Hm, nothing can possibly satisify this dep. Nuke it.
1153             if (VList[0] == 0 &&
1154                 Start.IsNegative() == false &&
1155                 (Flags[I->ID] & Protected) != Protected)
1156             {
1157                bool Installed = Cache[I].Install();
1158                Cache.MarkKeep(I);
1159                if (Cache[I].InstBroken() == false)
1160                {
1161                   // Unwind operation will be keep now
1162                   if (OrOp == OrRemove)
1163                      OrOp = OrKeep;
1164
1165                   // Restore
1166                   if (InOr == true && Installed == true)
1167                      Cache.MarkInstall(I, false, 0, false);
1168
1169                   if (Debug == true)
1170                      clog << "  Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1171                }
1172                else
1173                {
1174                   if (Debug == true)
1175                      clog << "  Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1176                   if (InOr == false)
1177                      Cache.MarkDelete(I, false, 0, false);
1178                }
1179
1180                Change = true;
1181                Done = true;
1182             }
1183
1184             // Try some more
1185             if (InOr == true)
1186                continue;
1187
1188             if (Done == true)
1189                break;
1190          }
1191
1192          // Apply the kill list now
1193          if (Cache[I].InstallVer != 0)
1194          {
1195             for (PackageKill *J = KillList; J != LEnd; J++)
1196             {
1197                Change = true;
1198                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1199                {
1200                   if (J->Dep.IsNegative() == true)
1201                   {
1202                      if (Debug == true)
1203                         clog << "  Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
1204                      Cache.MarkDelete(J->Pkg, false, 0, false);
1205                   }
1206                }
1207                else
1208                {
1209                   if (Debug == true)
1210                      clog << "  Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
1211                   Cache.MarkKeep(J->Pkg, false, false);
1212                }
1213
1214                if (Counter > 1)
1215                {
1216                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1217                      Scores[J->Pkg->ID] = Scores[I->ID];
1218                }
1219             }
1220          }
1221       }
1222    }
1223
1224    if (Debug == true)
1225       clog << "Done" << endl;
1226
1227    if (Cache.BrokenCount() != 0)
1228    {
1229       // See if this is the result of a hold
1230       pkgCache::PkgIterator I = Cache.PkgBegin();
1231       for (;I.end() != true; ++I)
1232       {
1233          if (Cache[I].InstBroken() == false)
1234             continue;
1235          if ((Flags[I->ID] & Protected) != Protected)
1236             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1237       }
1238       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1239    }
1240
1241    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1242    pkgCache::PkgIterator I = Cache.PkgBegin();
1243    for (;I.end() != true; ++I) {
1244       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1245          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1246             std::clog << "Resolve installed new pkg: " << I.FullName(false)
1247                       << " (now marking it as auto)" << std::endl;
1248          }
1249          Cache[I].Flags |= pkgCache::Flag::Auto;
1250       }
1251    }
1252
1253
1254    return true;
1255 }
1256                                                                         /*}}}*/
1257 // ProblemResolver::BreaksInstOrPolicy - Check if the given pkg is broken/*{{{*/
1258 // ---------------------------------------------------------------------
1259 /* This checks if the given package is broken either by a hard dependency
1260    (InstBroken()) or by introducing a new policy breakage e.g. new
1261    unsatisfied recommends for a package that was in "policy-good" state
1262
1263    Note that this is not perfect as it will ignore further breakage
1264    for already broken policy (recommends)
1265 */
1266 bool pkgProblemResolver::InstOrNewPolicyBroken(pkgCache::PkgIterator I)
1267 {
1268    // a broken install is always a problem
1269    if (Cache[I].InstBroken() == true)
1270    {
1271       if (Debug == true)
1272          std::clog << "  Dependencies are not satisfied for " << I << std::endl;
1273       return true;
1274    }
1275
1276    // a newly broken policy (recommends/suggests) is a problem
1277    if (Cache[I].NowPolicyBroken() == false &&
1278        Cache[I].InstPolicyBroken() == true)
1279    {
1280       if (Debug == true)
1281          std::clog << "  Policy breaks with upgrade of " << I << std::endl;
1282       return true;
1283    }
1284
1285    return false;
1286 }
1287                                                                         /*}}}*/
1288 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1289 // ---------------------------------------------------------------------
1290 /* This is the work horse of the soft upgrade routine. It is very gental
1291    in that it does not install or remove any packages. It is assumed that the
1292    system was non-broken previously. */
1293 bool pkgProblemResolver::ResolveByKeep()
1294 {
1295    std::string const solver = _config->Find("APT::Solver", "internal");
1296    if (solver != "internal") {
1297       OpTextProgress Prog(*_config);
1298       return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false, &Prog);
1299    }
1300    return ResolveByKeepInternal();
1301 }
1302                                                                         /*}}}*/
1303 // ProblemResolver::ResolveByKeepInternal - Resolve problems using keep /*{{{*/
1304 // ---------------------------------------------------------------------
1305 /* This is the work horse of the soft upgrade routine. It is very gental
1306    in that it does not install or remove any packages. It is assumed that the
1307    system was non-broken previously. */
1308 bool pkgProblemResolver::ResolveByKeepInternal()
1309 {
1310    pkgDepCache::ActionGroup group(Cache);
1311
1312    unsigned long Size = Cache.Head().PackageCount;
1313
1314    MakeScores();
1315
1316    /* We have to order the packages so that the broken fixing pass
1317       operates from highest score to lowest. This prevents problems when
1318       high score packages cause the removal of lower score packages that
1319       would cause the removal of even lower score packages. */
1320    pkgCache::Package **PList = new pkgCache::Package *[Size];
1321    pkgCache::Package **PEnd = PList;
1322    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1323       *PEnd++ = I;
1324    This = this;
1325    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1326
1327    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1328    {
1329       clog << "Show Scores" << endl;
1330       for (pkgCache::Package **K = PList; K != PEnd; K++)
1331          if (Scores[(*K)->ID] != 0)
1332          {
1333            pkgCache::PkgIterator Pkg(Cache,*K);
1334            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1335          }
1336    }
1337
1338    if (Debug == true)
1339       clog << "Entering ResolveByKeep" << endl;
1340
1341    // Consider each broken package
1342    pkgCache::Package **LastStop = 0;
1343    for (pkgCache::Package **K = PList; K != PEnd; K++)
1344    {
1345       pkgCache::PkgIterator I(Cache,*K);
1346
1347       if (Cache[I].InstallVer == 0)
1348          continue;
1349
1350       if (InstOrNewPolicyBroken(I) == false)
1351          continue;
1352
1353       /* Keep the package. If this works then great, otherwise we have
1354          to be significantly more agressive and manipulate its dependencies */
1355       if ((Flags[I->ID] & Protected) == 0)
1356       {
1357          if (Debug == true)
1358             clog << "Keeping package " << I.FullName(false) << endl;
1359          Cache.MarkKeep(I, false, false);
1360          if (InstOrNewPolicyBroken(I) == false)
1361          {
1362             K = PList - 1;
1363             continue;
1364          }
1365       }
1366
1367       // Isolate the problem dependencies
1368       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1369       {
1370          DepIterator Start;
1371          DepIterator End;
1372          D.GlobOr(Start,End);
1373
1374          // We only worry about critical deps.
1375          if (End.IsCritical() != true)
1376             continue;
1377
1378          // Dep is ok
1379          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1380             continue;
1381
1382          /* Hm, the group is broken.. I suppose the best thing to do is to
1383             is to try every combination of keep/not-keep for the set, but thats
1384             slow, and this never happens, just be conservative and assume the
1385             list of ors is in preference and keep till it starts to work. */
1386          while (true)
1387          {
1388             if (Debug == true)
1389                clog << "Package " << I.FullName(false) << " " << Start << endl;
1390
1391             // Look at all the possible provides on this package
1392             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1393             for (pkgCache::Version **V = VList; *V != 0; V++)
1394             {
1395                pkgCache::VerIterator Ver(Cache,*V);
1396                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1397
1398                // It is not keepable
1399                if (Cache[Pkg].InstallVer == 0 ||
1400                    Pkg->CurrentVer == 0)
1401                   continue;
1402
1403                if ((Flags[I->ID] & Protected) == 0)
1404                {
1405                   if (Debug == true)
1406                      clog << "  Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1407                   Cache.MarkKeep(Pkg, false, false);
1408                }
1409
1410                if (InstOrNewPolicyBroken(I) == false)
1411                   break;
1412             }
1413
1414             if (InstOrNewPolicyBroken(I) == false)
1415                break;
1416
1417             if (Start == End)
1418                break;
1419             ++Start;
1420          }
1421
1422          if (InstOrNewPolicyBroken(I) == false)
1423             break;
1424       }
1425
1426       if (InstOrNewPolicyBroken(I) == true)
1427          continue;
1428
1429       // Restart again.
1430       if (K == LastStop) {
1431           // I is an iterator based off our temporary package list,
1432           // so copy the name we need before deleting the temporary list
1433           std::string const LoopingPackage = I.FullName(false);
1434           delete[] PList;
1435           return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.", LoopingPackage.c_str());
1436       }
1437       LastStop = K;
1438       K = PList - 1;
1439    }
1440
1441    delete[] PList;
1442    return true;
1443 }
1444                                                                         /*}}}*/
1445 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1446 // ---------------------------------------------------------------------
1447 /* This is used to make sure protected packages are installed */
1448 void pkgProblemResolver::InstallProtect()
1449 {
1450    pkgDepCache::ActionGroup group(Cache);
1451
1452    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1453    {
1454       if ((Flags[I->ID] & Protected) == Protected)
1455       {
1456          if ((Flags[I->ID] & ToRemove) == ToRemove)
1457             Cache.MarkDelete(I);
1458          else
1459          {
1460             // preserve the information whether the package was auto
1461             // or manually installed
1462             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1463             Cache.MarkInstall(I, false, 0, !autoInst);
1464          }
1465       }
1466    }
1467 }
1468                                                                         /*}}}*/
1469 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1470 // ---------------------------------------------------------------------
1471 /* This is ment to be used in conjunction with AllTargets to get a list
1472    of versions ordered by preference. */
1473 static pkgCache *PrioCache;
1474 static int PrioComp(const void *A,const void *B)
1475 {
1476    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1477    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1478
1479    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1480        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1481      return 1;
1482    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1483        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1484      return -1;
1485
1486    if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important &&
1487        (R.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important)
1488      return 1;
1489    if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important &&
1490        (R.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1491      return -1;
1492
1493    if (L->Priority != R->Priority)
1494       return R->Priority - L->Priority;
1495    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1496 }
1497 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1498 {
1499    unsigned long Count = 0;
1500    PrioCache = &Cache;
1501    for (pkgCache::Version **I = List; *I != 0; I++)
1502       Count++;
1503    qsort(List,Count,sizeof(*List),PrioComp);
1504 }
1505                                                                         /*}}}*/
1506 // ListUpdate - construct Fetcher and update the cache files            /*{{{*/
1507 // ---------------------------------------------------------------------
1508 /* This is a simple wrapper to update the cache. it will fetch stuff
1509  * from the network (or any other sources defined in sources.list)
1510  */
1511 bool ListUpdate(pkgAcquireStatus &Stat,
1512                 pkgSourceList &List,
1513                 int PulseInterval)
1514 {
1515    pkgAcquire Fetcher;
1516    if (Fetcher.Setup(&Stat, _config->FindDir("Dir::State::Lists")) == false)
1517       return false;
1518
1519    // Populate it with the source selection
1520    if (List.GetIndexes(&Fetcher) == false)
1521          return false;
1522
1523    return AcquireUpdate(Fetcher, PulseInterval, true);
1524 }
1525                                                                         /*}}}*/
1526 // AcquireUpdate - take Fetcher and update the cache files              /*{{{*/
1527 // ---------------------------------------------------------------------
1528 /* This is a simple wrapper to update the cache with a provided acquire
1529  * If you only need control over Status and the used SourcesList use
1530  * ListUpdate method instead.
1531  */
1532 bool AcquireUpdate(pkgAcquire &Fetcher, int const PulseInterval,
1533                    bool const RunUpdateScripts, bool const ListCleanup)
1534 {
1535    // Run scripts
1536    if (RunUpdateScripts == true)
1537       RunScripts("APT::Update::Pre-Invoke");
1538
1539    pkgAcquire::RunResult res;
1540    if(PulseInterval > 0)
1541       res = Fetcher.Run(PulseInterval);
1542    else
1543       res = Fetcher.Run();
1544
1545    if (res == pkgAcquire::Failed)
1546       return false;
1547
1548    bool Failed = false;
1549    bool TransientNetworkFailure = false;
1550    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin();
1551         I != Fetcher.ItemsEnd(); ++I)
1552    {
1553       if ((*I)->Status == pkgAcquire::Item::StatDone)
1554          continue;
1555
1556       (*I)->Finished();
1557
1558       ::URI uri((*I)->DescURI());
1559       uri.User.clear();
1560       uri.Password.clear();
1561       string descUri = string(uri);
1562       _error->Warning(_("Failed to fetch %s  %s\n"), descUri.c_str(),
1563               (*I)->ErrorText.c_str());
1564
1565       if ((*I)->Status == pkgAcquire::Item::StatTransientNetworkError)
1566       {
1567          TransientNetworkFailure = true;
1568          continue;
1569       }
1570
1571       Failed = true;
1572    }
1573
1574    // Clean out any old list files
1575    // Keep "APT::Get::List-Cleanup" name for compatibility, but
1576    // this is really a global option for the APT library now
1577    if (!TransientNetworkFailure && !Failed && ListCleanup == true &&
1578        (_config->FindB("APT::Get::List-Cleanup",true) == true &&
1579         _config->FindB("APT::List-Cleanup",true) == true))
1580    {
1581       if (Fetcher.Clean(_config->FindDir("Dir::State::lists")) == false ||
1582           Fetcher.Clean(_config->FindDir("Dir::State::lists") + "partial/") == false)
1583          // something went wrong with the clean
1584          return false;
1585    }
1586
1587    if (TransientNetworkFailure == true)
1588       _error->Warning(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1589    else if (Failed == true)
1590       return _error->Error(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1591
1592
1593    // Run the success scripts if all was fine
1594    if (RunUpdateScripts == true)
1595    {
1596       if(!TransientNetworkFailure && !Failed)
1597          RunScripts("APT::Update::Post-Invoke-Success");
1598
1599       // Run the other scripts
1600       RunScripts("APT::Update::Post-Invoke");
1601    }
1602    return true;
1603 }
1604                                                                         /*}}}*/