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