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