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