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