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