apt-pkg/depcache.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: depcache.cc,v 1.25 2001/05/27 05:36:04 jgg Exp $
   4 /* ######################################################################
   5
   6    Dependency Cache - Caches Dependency information.
   7
   8    ##################################################################### */
   9                                                                         /*}}}*/
  10 // Include Files                                                        /*{{{*/
  11 #include<config.h>
  12
  13 #include <apt-pkg/depcache.h>
  14 #include <apt-pkg/versionmatch.h>
  15 #include <apt-pkg/error.h>
  16 #include <apt-pkg/sptr.h>
  17 #include <apt-pkg/fileutl.h>
  18 #include <apt-pkg/strutl.h>
  19 #include <apt-pkg/configuration.h>
  20 #include <apt-pkg/aptconfiguration.h>
  21 #include <apt-pkg/tagfile.h>
  22 #include <apt-pkg/progress.h>
  23 #include <apt-pkg/cacheset.h>
  24 #include <apt-pkg/pkgcache.h>
  25 #include <apt-pkg/cacheiterators.h>
  26 #include <apt-pkg/cachefile.h>
  27 #include <apt-pkg/macros.h>
  28
  29 #include <stdio.h>
  30 #include <string.h>
  31 #include <list>
  32 #include <string>
  33 #include <utility>
  34 #include <vector>
  35 #include <algorithm>
  36 #include <iostream>
  37 #include <set>
  38
  39 #include <sys/stat.h>
  40
  41 #include <apti18n.h>
  42                                                                         /*}}}*/
  43
  44 using std::string;
  45
  46 // helper for Install-Recommends-Sections and Never-MarkAuto-Sections   /*{{{*/
  47 static bool
  48 ConfigValueInSubTree(const char* SubTree, const char *needle)
  49 {
  50    Configuration::Item const *Opts;
  51    Opts = _config->Tree(SubTree);
  52    if (Opts != 0 && Opts->Child != 0)
  53    {
  54       Opts = Opts->Child;
  55       for (; Opts != 0; Opts = Opts->Next)
  56       {
  57          if (Opts->Value.empty() == true)
  58             continue;
  59          if (strcmp(needle, Opts->Value.c_str()) == 0)
  60             return true;
  61       }
  62    }
  63    return false;
  64 }
  65                                                                         /*}}}*/
  66 pkgDepCache::ActionGroup::ActionGroup(pkgDepCache &cache) :             /*{{{*/
  67   d(NULL), cache(cache), released(false)
  68 {
  69   ++cache.group_level;
  70 }
  71
  72 void pkgDepCache::ActionGroup::release()
  73 {
  74   if(!released)
  75     {
  76       if(cache.group_level == 0)
  77         std::cerr << "W: Unbalanced action groups, expect badness" << std::endl;
  78       else
  79         {
  80           --cache.group_level;
  81
  82           if(cache.group_level == 0)
  83             cache.MarkAndSweep();
  84         }
  85
  86       released = true;
  87     }
  88 }
  89
  90 pkgDepCache::ActionGroup::~ActionGroup()
  91 {
  92   release();
  93 }
  94                                                                         /*}}}*/
  95 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  96 // ---------------------------------------------------------------------
  97 /* */
  98 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  99   group_level(0), Cache(pCache), PkgState(0), DepState(0),
 100    iUsrSize(0), iDownloadSize(0), iInstCount(0), iDelCount(0), iKeepCount(0),
 101    iBrokenCount(0), iPolicyBrokenCount(0), iBadCount(0), d(NULL)
 102 {
 103    DebugMarker = _config->FindB("Debug::pkgDepCache::Marker", false);
 104    DebugAutoInstall = _config->FindB("Debug::pkgDepCache::AutoInstall", false);
 105    delLocalPolicy = 0;
 106    LocalPolicy = Plcy;
 107    if (LocalPolicy == 0)
 108       delLocalPolicy = LocalPolicy = new Policy;
 109 }
 110                                                                         /*}}}*/
 111 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
 112 // ---------------------------------------------------------------------
 113 /* */
 114 pkgDepCache::~pkgDepCache()
 115 {
 116    delete [] PkgState;
 117    delete [] DepState;
 118    delete delLocalPolicy;
 119 }
 120                                                                         /*}}}*/
 121 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
 122 // ---------------------------------------------------------------------
 123 /* This allocats the extension buffers and initializes them. */
 124 bool pkgDepCache::Init(OpProgress *Prog)
 125 {
 126    // Suppress mark updates during this operation (just in case) and
 127    // run a mark operation when Init terminates.
 128    ActionGroup actions(*this);
 129
 130    delete [] PkgState;
 131    delete [] DepState;
 132    PkgState = new StateCache[Head().PackageCount];
 133    DepState = new unsigned char[Head().DependsCount];
 134    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
 135    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
 136
 137    if (Prog != 0)
 138    {
 139       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
 140                             _("Building dependency tree"));
 141       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 142    }
 143
 144    /* Set the current state of everything. In this state all of the
 145       packages are kept exactly as is. See AllUpgrade */
 146    int Done = 0;
 147    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 148    {
 149       if (Prog != 0 && Done%20 == 0)
 150          Prog->Progress(Done);
 151
 152       // Find the proper cache slot
 153       StateCache &State = PkgState[I->ID];
 154       State.iFlags = 0;
 155
 156       // Figure out the install version
 157       State.CandidateVer = GetCandidateVer(I);
 158       State.InstallVer = I.CurrentVer();
 159       State.Mode = ModeKeep;
 160
 161       State.Update(I,*this);
 162    }
 163
 164    if (Prog != 0)
 165    {
 166
 167       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
 168                             Head().PackageCount,
 169                             _("Building dependency tree"));
 170       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
 171    }
 172
 173    Update(Prog);
 174
 175    if(Prog != 0)
 176       Prog->Done();
 177
 178    return true;
 179 }
 180                                                                         /*}}}*/
 181 bool pkgDepCache::readStateFile(OpProgress *Prog)                       /*{{{*/
 182 {
 183    FileFd state_file;
 184    string const state = _config->FindFile("Dir::State::extended_states");
 185    if(RealFileExists(state)) {
 186       state_file.Open(state, FileFd::ReadOnly);
 187       off_t const file_size = state_file.Size();
 188       if(Prog != NULL)
 189          Prog->OverallProgress(0, file_size, 1,
 190                                _("Reading state information"));
 191
 192       pkgTagFile tagfile(&state_file);
 193       pkgTagSection section;
 194       off_t amt = 0;
 195       bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 196       while(tagfile.Step(section)) {
 197          string const pkgname = section.FindS("Package");
 198          string pkgarch = section.FindS("Architecture");
 199          if (pkgarch.empty() == true)
 200             pkgarch = "any";
 201          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 202          // Silently ignore unknown packages and packages with no actual version.
 203          if(pkg.end() == true || pkg->VersionList == 0)
 204             continue;
 205
 206          short const reason = section.FindI("Auto-Installed", 0);
 207          if(reason > 0)
 208          {
 209             PkgState[pkg->ID].Flags |= Flag::Auto;
 210             if (unlikely(debug_autoremove))
 211                std::clog << "Auto-Installed : " << pkg.FullName() << std::endl;
 212             if (pkgarch == "any")
 213             {
 214                pkgCache::GrpIterator G = pkg.Group();
 215                for (pkg = G.NextPkg(pkg); pkg.end() != true; pkg = G.NextPkg(pkg))
 216                   if (pkg->VersionList != 0)
 217                      PkgState[pkg->ID].Flags |= Flag::Auto;
 218             }
 219          }
 220          amt += section.size();
 221          if(Prog != NULL)
 222             Prog->OverallProgress(amt, file_size, 1,
 223                                   _("Reading state information"));
 224       }
 225       if(Prog != NULL)
 226          Prog->OverallProgress(file_size, file_size, 1,
 227                                _("Reading state information"));
 228    }
 229
 230    return true;
 231 }
 232                                                                         /*}}}*/
 233 bool pkgDepCache::writeStateFile(OpProgress * /*prog*/, bool InstalledOnly)     /*{{{*/
 234 {
 235    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 236
 237    if(debug_autoremove)
 238       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 239
 240    FileFd StateFile;
 241    string const state = _config->FindFile("Dir::State::extended_states");
 242    if (CreateAPTDirectoryIfNeeded(_config->FindDir("Dir::State"), flNotFile(state)) == false)
 243       return false;
 244
 245    // if it does not exist, create a empty one
 246    if(!RealFileExists(state))
 247    {
 248       StateFile.Open(state, FileFd::WriteAtomic);
 249       StateFile.Close();
 250    }
 251
 252    // open it
 253    if(!StateFile.Open(state, FileFd::ReadOnly))
 254       return _error->Error(_("Failed to open StateFile %s"),
 255                            state.c_str());
 256
 257    FileFd OutFile(state, FileFd::ReadWrite | FileFd::Atomic);
 258    if (OutFile.IsOpen() == false || OutFile.Failed() == true)
 259       return _error->Error(_("Failed to write temporary StateFile %s"), state.c_str());
 260
 261    // first merge with the existing sections
 262    pkgTagFile tagfile(&StateFile);
 263    pkgTagSection section;
 264    std::set<string> pkgs_seen;
 265    while(tagfile.Step(section)) {
 266          string const pkgname = section.FindS("Package");
 267          string pkgarch = section.FindS("Architecture");
 268          if (pkgarch.empty() == true)
 269             pkgarch = "native";
 270          // Silently ignore unknown packages and packages with no actual
 271          // version.
 272          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 273          if(pkg.end() || pkg.VersionList().end())
 274             continue;
 275          StateCache const &P = PkgState[pkg->ID];
 276          bool newAuto = (P.Flags & Flag::Auto);
 277          // skip not installed or now-removed ones if requested
 278          if (InstalledOnly && (
 279              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 280              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 281          {
 282             // The section is obsolete if it contains no other tag
 283             unsigned int const count = section.Count();
 284             if (count < 2 ||
 285                 (count == 2 && section.Exists("Auto-Installed")) ||
 286                 (count == 3 && section.Exists("Auto-Installed") && section.Exists("Architecture")))
 287                continue;
 288             else
 289                newAuto = false;
 290          }
 291          if(_config->FindB("Debug::pkgAutoRemove",false))
 292             std::clog << "Update existing AutoInstall info: "
 293                       << pkg.FullName() << std::endl;
 294
 295          std::vector<pkgTagSection::Tag> rewrite;
 296          rewrite.push_back(pkgTagSection::Tag::Rewrite("Architecture", pkg.Arch()));
 297          rewrite.push_back(pkgTagSection::Tag::Rewrite("Auto-Installed", newAuto ? "1" : "0"));
 298          section.Write(OutFile, NULL, rewrite);
 299          if (OutFile.Write("\n", 1) == false)
 300             return false;
 301          pkgs_seen.insert(pkg.FullName());
 302    }
 303
 304    // then write the ones we have not seen yet
 305    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end(); ++pkg) {
 306       StateCache const &P = PkgState[pkg->ID];
 307       if(P.Flags & Flag::Auto) {
 308          if (pkgs_seen.find(pkg.FullName()) != pkgs_seen.end()) {
 309             if(debug_autoremove)
 310                std::clog << "Skipping already written " << pkg.FullName() << std::endl;
 311             continue;
 312          }
 313          // skip not installed ones if requested
 314          if (InstalledOnly && (
 315              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 316              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 317             continue;
 318          const char* const pkgarch = pkg.Arch();
 319          if (strcmp(pkgarch, "all") == 0)
 320             continue;
 321          if(debug_autoremove)
 322             std::clog << "Writing new AutoInstall: " << pkg.FullName() << std::endl;
 323          std::string stanza = "Package: ";
 324          stanza.append(pkg.Name())
 325               .append("\nArchitecture: ").append(pkgarch)
 326               .append("\nAuto-Installed: 1\n\n");
 327          if (OutFile.Write(stanza.c_str(), stanza.length()) == false)
 328             return false;
 329       }
 330    }
 331    if (OutFile.Close() == false)
 332       return false;
 333    chmod(state.c_str(), 0644);
 334    return true;
 335 }
 336                                                                         /*}}}*/
 337 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 338 // ---------------------------------------------------------------------
 339 /* This first checks the dependency against the main target package and
 340    then walks along the package provides list and checks if each provides
 341    will be installed then checks the provides against the dep. Res will be
 342    set to the package which was used to satisfy the dep. */
 343 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 344 {
 345    Res = Dep.TargetPkg();
 346
 347    /* Check simple depends. A depends -should- never self match but
 348       we allow it anyhow because dpkg does. Technically it is a packaging
 349       bug. Conflicts may never self match */
 350    if (Dep.IsIgnorable(Res) == false)
 351    {
 352       PkgIterator Pkg = Dep.TargetPkg();
 353       // Check the base package
 354       if (Type == NowVersion && Pkg->CurrentVer != 0)
 355          if (Dep.IsSatisfied(Pkg.CurrentVer()) == true)
 356             return true;
 357
 358       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 359          if (Dep.IsSatisfied(PkgState[Pkg->ID].InstVerIter(*this)) == true)
 360             return true;
 361
 362       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 363          if (Dep.IsSatisfied(PkgState[Pkg->ID].CandidateVerIter(*this)) == true)
 364             return true;
 365    }
 366
 367    if (Dep->Type == Dep::Obsoletes)
 368       return false;
 369
 370    // Check the providing packages
 371    PrvIterator P = Dep.TargetPkg().ProvidesList();
 372    for (; P.end() != true; ++P)
 373    {
 374       if (Dep.IsIgnorable(P) == true)
 375          continue;
 376
 377       // Check if the provides is a hit
 378       if (Type == NowVersion)
 379       {
 380          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 381             continue;
 382       }
 383
 384       if (Type == InstallVersion)
 385       {
 386          StateCache &State = PkgState[P.OwnerPkg()->ID];
 387          if (State.InstallVer != (Version *)P.OwnerVer())
 388             continue;
 389       }
 390
 391       if (Type == CandidateVersion)
 392       {
 393          StateCache &State = PkgState[P.OwnerPkg()->ID];
 394          if (State.CandidateVer != (Version *)P.OwnerVer())
 395             continue;
 396       }
 397
 398       // Compare the versions.
 399       if (Dep.IsSatisfied(P) == true)
 400       {
 401          Res = P.OwnerPkg();
 402          return true;
 403       }
 404    }
 405
 406    return false;
 407 }
 408                                                                         /*}}}*/
 409 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 410 // ---------------------------------------------------------------------
 411 /* Call with Inverse = true to preform the inverse opration */
 412 void pkgDepCache::AddSizes(const PkgIterator &Pkg, bool const Inverse)
 413 {
 414    StateCache &P = PkgState[Pkg->ID];
 415
 416    if (Pkg->VersionList == 0)
 417       return;
 418
 419    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 420        P.Keep() == true)
 421       return;
 422
 423    // Compute the size data
 424    if (P.NewInstall() == true)
 425    {
 426       if (Inverse == false) {
 427          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 428          iDownloadSize += P.InstVerIter(*this)->Size;
 429       } else {
 430          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 431          iDownloadSize -= P.InstVerIter(*this)->Size;
 432       }
 433       return;
 434    }
 435
 436    // Upgrading
 437    if (Pkg->CurrentVer != 0 &&
 438        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 439         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 440    {
 441       if (Inverse == false) {
 442          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 443          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 444          iDownloadSize += P.InstVerIter(*this)->Size;
 445       } else {
 446          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 447          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 448          iDownloadSize -= P.InstVerIter(*this)->Size;
 449       }
 450       return;
 451    }
 452
 453    // Reinstall
 454    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 455        P.Delete() == false)
 456    {
 457       if (Inverse == false)
 458          iDownloadSize += P.InstVerIter(*this)->Size;
 459       else
 460          iDownloadSize -= P.InstVerIter(*this)->Size;
 461       return;
 462    }
 463
 464    // Removing
 465    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 466    {
 467       if (Inverse == false)
 468          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 469       else
 470          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 471       return;
 472    }
 473 }
 474                                                                         /*}}}*/
 475 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 476 // ---------------------------------------------------------------------
 477 /* This routine is tricky to use, you must make sure that it is never
 478    called twice for the same package. This means the Remove/Add section
 479    should be as short as possible and not encompass any code that will
 480    calld Remove/Add itself. Remember, dependencies can be circular so
 481    while processing a dep for Pkg it is possible that Add/Remove
 482    will be called on Pkg */
 483 void pkgDepCache::AddStates(const PkgIterator &Pkg, bool const Invert)
 484 {
 485    signed char const Add = (Invert == false) ? 1 : -1;
 486    StateCache &State = PkgState[Pkg->ID];
 487
 488    // The Package is broken (either minimal dep or policy dep)
 489    if ((State.DepState & DepInstMin) != DepInstMin)
 490       iBrokenCount += Add;
 491    if ((State.DepState & DepInstPolicy) != DepInstPolicy)
 492       iPolicyBrokenCount += Add;
 493
 494    // Bad state
 495    if (Pkg.State() != PkgIterator::NeedsNothing)
 496       iBadCount += Add;
 497
 498    // Not installed
 499    if (Pkg->CurrentVer == 0)
 500    {
 501       if (State.Mode == ModeDelete &&
 502           (State.iFlags & Purge) == Purge && Pkg.Purge() == false)
 503          iDelCount += Add;
 504
 505       if (State.Mode == ModeInstall)
 506          iInstCount += Add;
 507       return;
 508    }
 509
 510    // Installed, no upgrade
 511    if (State.Status == 0)
 512    {
 513       if (State.Mode == ModeDelete)
 514          iDelCount += Add;
 515       else
 516          if ((State.iFlags & ReInstall) == ReInstall)
 517             iInstCount += Add;
 518
 519       return;
 520    }
 521
 522    // Alll 3 are possible
 523    if (State.Mode == ModeDelete)
 524       iDelCount += Add;
 525    if (State.Mode == ModeKeep)
 526       iKeepCount += Add;
 527    if (State.Mode == ModeInstall)
 528       iInstCount += Add;
 529 }
 530                                                                         /*}}}*/
 531 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 532 // ---------------------------------------------------------------------
 533 /* The or group results are stored in the last item of the or group. This
 534    allows easy detection of the state of a whole or'd group. */
 535 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 536 {
 537    unsigned char Group = 0;
 538
 539    for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 540    {
 541       // Build the dependency state.
 542       unsigned char &State = DepState[D->ID];
 543
 544       /* Invert for Conflicts. We have to do this twice to get the
 545          right sense for a conflicts group */
 546       if (D.IsNegative() == true)
 547          State = ~State;
 548
 549       // Add to the group if we are within an or..
 550       State &= 0x7;
 551       Group |= State;
 552       State |= Group << 3;
 553       if ((D->CompareOp & Dep::Or) != Dep::Or)
 554          Group = 0;
 555
 556       // Invert for Conflicts
 557       if (D.IsNegative() == true)
 558          State = ~State;
 559    }
 560 }
 561                                                                         /*}}}*/
 562 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 563 // ---------------------------------------------------------------------
 564 /* This is used to run over a dependency list and determine the dep
 565    state of the list, filtering it through both a Min check and a Policy
 566    check. The return result will have SetMin/SetPolicy low if a check
 567    fails. It uses the DepState cache for it's computations. */
 568 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 569                                        unsigned char SetMin,
 570                                        unsigned char SetPolicy)
 571 {
 572    unsigned char Dep = 0xFF;
 573
 574    while (D.end() != true)
 575    {
 576       // Compute a single dependency element (glob or)
 577       DepIterator Start = D;
 578       unsigned char State = 0;
 579       for (bool LastOR = true; D.end() == false && LastOR == true; ++D)
 580       {
 581          State |= DepState[D->ID];
 582          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 583       }
 584
 585       // Minimum deps that must be satisfied to have a working package
 586       if (Start.IsCritical() == true)
 587          if ((State & Check) != Check)
 588             Dep &= ~SetMin;
 589
 590       // Policy deps that must be satisfied to install the package
 591       if (IsImportantDep(Start) == true &&
 592           (State & Check) != Check)
 593          Dep &= ~SetPolicy;
 594    }
 595
 596    return Dep;
 597 }
 598                                                                         /*}}}*/
 599 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 600 // ---------------------------------------------------------------------
 601 /* This is the main dependency computation bit. It computes the 3 main
 602    results for a dependencys, Now, Install and Candidate. Callers must
 603    invert the result if dealing with conflicts. */
 604 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 605 {
 606    unsigned char State = 0;
 607
 608    if (CheckDep(D,NowVersion) == true)
 609       State |= DepNow;
 610    if (CheckDep(D,InstallVersion) == true)
 611       State |= DepInstall;
 612    if (CheckDep(D,CandidateVersion) == true)
 613       State |= DepCVer;
 614
 615    return State;
 616 }
 617                                                                         /*}}}*/
 618 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 619 // ---------------------------------------------------------------------
 620 /* This determines the combined dependency representation of a package
 621    for its two states now and install. This is done by using the pre-generated
 622    dependency information. */
 623 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 624 {
 625    // Empty deps are always true
 626    StateCache &State = PkgState[Pkg->ID];
 627    State.DepState = 0xFF;
 628
 629    // Check the Current state
 630    if (Pkg->CurrentVer != 0)
 631    {
 632       DepIterator D = Pkg.CurrentVer().DependsList();
 633       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 634    }
 635
 636    /* Check the candidate state. We do not compare against the whole as
 637       a candidate state but check the candidate version against the
 638       install states */
 639    if (State.CandidateVer != 0)
 640    {
 641       DepIterator D = State.CandidateVerIter(*this).DependsList();
 642       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 643    }
 644
 645    // Check target state which can only be current or installed
 646    if (State.InstallVer != 0)
 647    {
 648       DepIterator D = State.InstVerIter(*this).DependsList();
 649       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 650    }
 651 }
 652                                                                         /*}}}*/
 653 // DepCache::Update - Figure out all the state information              /*{{{*/
 654 // ---------------------------------------------------------------------
 655 /* This will figure out the state of all the packages and all the
 656    dependencies based on the current policy. */
 657 void pkgDepCache::Update(OpProgress *Prog)
 658 {
 659    iUsrSize = 0;
 660    iDownloadSize = 0;
 661    iInstCount = 0;
 662    iDelCount = 0;
 663    iKeepCount = 0;
 664    iBrokenCount = 0;
 665    iPolicyBrokenCount = 0;
 666    iBadCount = 0;
 667
 668    // Perform the depends pass
 669    int Done = 0;
 670    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 671    {
 672       if (Prog != 0 && Done%20 == 0)
 673          Prog->Progress(Done);
 674       for (VerIterator V = I.VersionList(); V.end() != true; ++V)
 675       {
 676          unsigned char Group = 0;
 677
 678          for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 679          {
 680             // Build the dependency state.
 681             unsigned char &State = DepState[D->ID];
 682             State = DependencyState(D);
 683
 684             // Add to the group if we are within an or..
 685             Group |= State;
 686             State |= Group << 3;
 687             if ((D->CompareOp & Dep::Or) != Dep::Or)
 688                Group = 0;
 689
 690             // Invert for Conflicts
 691             if (D.IsNegative() == true)
 692                State = ~State;
 693          }
 694       }
 695
 696       // Compute the package dependency state and size additions
 697       AddSizes(I);
 698       UpdateVerState(I);
 699       AddStates(I);
 700    }
 701
 702    if (Prog != 0)
 703       Prog->Progress(Done);
 704
 705    readStateFile(Prog);
 706 }
 707                                                                         /*}}}*/
 708 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 709 // ---------------------------------------------------------------------
 710 /* This is a helper for update that only does the dep portion of the scan.
 711    It is mainly meant to scan reverse dependencies. */
 712 void pkgDepCache::Update(DepIterator D)
 713 {
 714    // Update the reverse deps
 715    for (;D.end() != true; ++D)
 716    {
 717       unsigned char &State = DepState[D->ID];
 718       State = DependencyState(D);
 719
 720       // Invert for Conflicts
 721       if (D.IsNegative() == true)
 722          State = ~State;
 723
 724       RemoveStates(D.ParentPkg());
 725       BuildGroupOrs(D.ParentVer());
 726       UpdateVerState(D.ParentPkg());
 727       AddStates(D.ParentPkg());
 728    }
 729 }
 730                                                                         /*}}}*/
 731 // DepCache::Update - Update the related deps of a package              /*{{{*/
 732 // ---------------------------------------------------------------------
 733 /* This is called whenever the state of a package changes. It updates
 734    all cached dependencies related to this package. */
 735 void pkgDepCache::Update(PkgIterator const &Pkg)
 736 {
 737    // Recompute the dep of the package
 738    RemoveStates(Pkg);
 739    UpdateVerState(Pkg);
 740    AddStates(Pkg);
 741
 742    // Update the reverse deps
 743    Update(Pkg.RevDependsList());
 744
 745    // Update the provides map for the current ver
 746    if (Pkg->CurrentVer != 0)
 747       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 748            P.end() != true; ++P)
 749          Update(P.ParentPkg().RevDependsList());
 750
 751    // Update the provides map for the candidate ver
 752    if (PkgState[Pkg->ID].CandidateVer != 0)
 753       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 754            P.end() != true; ++P)
 755          Update(P.ParentPkg().RevDependsList());
 756 }
 757                                                                         /*}}}*/
 758 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 759 // ---------------------------------------------------------------------
 760 /* */
 761 bool pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 762                            unsigned long Depth)
 763 {
 764    if (IsModeChangeOk(ModeKeep, Pkg, Depth, FromUser) == false)
 765       return false;
 766
 767    /* Reject an attempt to keep a non-source broken installed package, those
 768       must be upgraded */
 769    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 770        Pkg.CurrentVer().Downloadable() == false)
 771       return false;
 772
 773    /* We changed the soft state all the time so the UI is a bit nicer
 774       to use */
 775    StateCache &P = PkgState[Pkg->ID];
 776
 777    // Check that it is not already kept
 778    if (P.Mode == ModeKeep)
 779       return true;
 780
 781    if (Soft == true)
 782       P.iFlags |= AutoKept;
 783    else
 784       P.iFlags &= ~AutoKept;
 785
 786    ActionGroup group(*this);
 787
 788 #if 0 // reseting the autoflag here means we lose the
 789       // auto-mark information if a user selects a package for removal
 790       // but changes  his mind then and sets it for keep again
 791       // - this makes sense as default when all Garbage dependencies
 792       //   are automatically marked for removal (as aptitude does).
 793       //   setting a package for keep then makes it no longer autoinstalled
 794       //   for all other use-case this action is rather surprising
 795    if(FromUser && !P.Marked)
 796      P.Flags &= ~Flag::Auto;
 797 #endif
 798
 799    if (DebugMarker == true)
 800       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 801
 802    RemoveSizes(Pkg);
 803    RemoveStates(Pkg);
 804
 805    P.Mode = ModeKeep;
 806    if (Pkg->CurrentVer == 0)
 807       P.InstallVer = 0;
 808    else
 809       P.InstallVer = Pkg.CurrentVer();
 810
 811    AddStates(Pkg);
 812    Update(Pkg);
 813    AddSizes(Pkg);
 814
 815    return true;
 816 }
 817                                                                         /*}}}*/
 818 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 819 // ---------------------------------------------------------------------
 820 /* */
 821 bool pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 822                              unsigned long Depth, bool FromUser)
 823 {
 824    if (IsModeChangeOk(ModeDelete, Pkg, Depth, FromUser) == false)
 825       return false;
 826
 827    StateCache &P = PkgState[Pkg->ID];
 828
 829    // Check that it is not already marked for delete
 830    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 831        (Pkg.Purge() == true || rPurge == false))
 832       return true;
 833
 834    // check if we are allowed to remove the package
 835    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
 836       return false;
 837
 838    P.iFlags &= ~(AutoKept | Purge);
 839    if (rPurge == true)
 840       P.iFlags |= Purge;
 841
 842    ActionGroup group(*this);
 843
 844    if (DebugMarker == true)
 845       std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << Pkg << " FU=" << FromUser << std::endl;
 846
 847    RemoveSizes(Pkg);
 848    RemoveStates(Pkg);
 849
 850    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 851       P.Mode = ModeKeep;
 852    else
 853       P.Mode = ModeDelete;
 854    P.InstallVer = 0;
 855
 856    AddStates(Pkg);
 857    Update(Pkg);
 858    AddSizes(Pkg);
 859
 860    return true;
 861 }
 862                                                                         /*}}}*/
 863 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 864 // ---------------------------------------------------------------------
 865 /* The default implementation tries to prevent deletion of install requests.
 866    dpkg holds are enforced by the private IsModeChangeOk */
 867 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 868                               unsigned long Depth, bool FromUser)
 869 {
 870    return IsDeleteOkProtectInstallRequests(Pkg, rPurge, Depth, FromUser);
 871 }
 872 bool pkgDepCache::IsDeleteOkProtectInstallRequests(PkgIterator const &Pkg,
 873       bool const /*rPurge*/, unsigned long const Depth, bool const FromUser)
 874 {
 875    if (FromUser == false && Pkg->CurrentVer == 0)
 876    {
 877       StateCache &P = PkgState[Pkg->ID];
 878       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
 879       {
 880          if (DebugMarker == true)
 881             std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << Pkg << std::endl;
 882          return false;
 883       }
 884    }
 885    return true;
 886 }
 887                                                                         /*}}}*/
 888 // DepCache::IsModeChangeOk - check if it is ok to change the mode      /*{{{*/
 889 // ---------------------------------------------------------------------
 890 /* this is used by all Mark methods on the very first line to check sanity
 891    and prevents mode changes for packages on hold for example.
 892    If you want to check Mode specific stuff you can use the virtual public
 893    Is<Mode>Ok methods instead */
 894 static char const* PrintMode(char const mode)
 895 {
 896          switch (mode)
 897          {
 898          case pkgDepCache::ModeInstall: return "Install";
 899          case pkgDepCache::ModeKeep: return "Keep";
 900          case pkgDepCache::ModeDelete: return "Delete";
 901          case pkgDepCache::ModeGarbage: return "Garbage";
 902          default: return "UNKNOWN";
 903          }
 904 }
 905 bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
 906                                  unsigned long const Depth, bool const FromUser)
 907 {
 908    // we are not trying to hard…
 909    if (unlikely(Depth > 100))
 910       return false;
 911
 912    // general sanity
 913    if (unlikely(Pkg.end() == true || Pkg->VersionList == 0))
 914       return false;
 915
 916    // the user is always right
 917    if (FromUser == true)
 918       return true;
 919
 920    StateCache &P = PkgState[Pkg->ID];
 921    // not changing the mode is obviously also fine as we might want to call
 922    // e.g. MarkInstall multiple times with different arguments for the same package
 923    if (P.Mode == mode)
 924       return true;
 925
 926    // if previous state was set by user only user can reset it
 927    if ((P.iFlags & Protected) == Protected)
 928    {
 929       if (unlikely(DebugMarker == true))
 930          std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
 931                    << " of " << Pkg << " as its mode (" << PrintMode(P.Mode)
 932                    << ") is protected" << std::endl;
 933       return false;
 934    }
 935    // enforce dpkg holds
 936    else if (mode != ModeKeep && Pkg->SelectedState == pkgCache::State::Hold &&
 937             _config->FindB("APT::Ignore-Hold",false) == false)
 938    {
 939       if (unlikely(DebugMarker == true))
 940          std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
 941                    << " of " << Pkg << std::endl;
 942       return false;
 943    }
 944
 945    return true;
 946 }
 947                                                                         /*}}}*/
 948 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 949 // ---------------------------------------------------------------------
 950 /* */
 951 struct CompareProviders {
 952    pkgCache::PkgIterator const Pkg;
 953    explicit CompareProviders(pkgCache::DepIterator const &Dep) : Pkg(Dep.TargetPkg()) {};
 954    //bool operator() (APT::VersionList::iterator const &AV, APT::VersionList::iterator const &BV)
 955    bool operator() (pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
 956    {
 957       pkgCache::PkgIterator const A = AV.ParentPkg();
 958       pkgCache::PkgIterator const B = BV.ParentPkg();
 959       // Prefer MA:same packages if other architectures for it are installed
 960       if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same ||
 961           (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 962       {
 963          bool instA = false;
 964          if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 965          {
 966             pkgCache::GrpIterator Grp = A.Group();
 967             for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
 968                if (P->CurrentVer != 0)
 969                {
 970                   instA = true;
 971                   break;
 972                }
 973          }
 974          bool instB = false;
 975          if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 976          {
 977             pkgCache::GrpIterator Grp = B.Group();
 978             for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
 979             {
 980                if (P->CurrentVer != 0)
 981                {
 982                   instB = true;
 983                   break;
 984                }
 985             }
 986          }
 987          if (instA != instB)
 988             return instA == false;
 989       }
 990       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
 991       if (A->Group != B->Group)
 992       {
 993          if (A->Group == Pkg->Group && B->Group != Pkg->Group)
 994             return false;
 995          else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
 996             return true;
 997       }
 998       // we like essentials
 999       if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
1000       {
1001          if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1002             return false;
1003          else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1004             return true;
1005       }
1006       if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
1007       {
1008          if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1009             return false;
1010          else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1011             return true;
1012       }
1013       // prefer native architecture
1014       if (strcmp(A.Arch(), B.Arch()) != 0)
1015       {
1016          if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
1017             return false;
1018          else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
1019             return true;
1020          std::vector<std::string> archs = APT::Configuration::getArchitectures();
1021          for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
1022             if (*a == A.Arch())
1023                return false;
1024             else if (*a == B.Arch())
1025                return true;
1026       }
1027       // higher priority seems like a good idea
1028       if (AV->Priority != BV->Priority)
1029          return AV->Priority > BV->Priority;
1030       // unable to decide…
1031       return A->ID < B->ID;
1032    }
1033 };
1034 bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
1035                               unsigned long Depth, bool FromUser,
1036                               bool ForceImportantDeps)
1037 {
1038    if (IsModeChangeOk(ModeInstall, Pkg, Depth, FromUser) == false)
1039       return false;
1040
1041    StateCache &P = PkgState[Pkg->ID];
1042
1043    // See if there is even any possible instalation candidate
1044    if (P.CandidateVer == 0)
1045       return false;
1046
1047    /* Check that it is not already marked for install and that it can be
1048       installed */
1049    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1050        (P.Mode == ModeInstall ||
1051         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1052    {
1053       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1054          return MarkKeep(Pkg, false, FromUser, Depth+1);
1055       return true;
1056    }
1057
1058    // check if we are allowed to install the package
1059    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1060       return false;
1061
1062    ActionGroup group(*this);
1063    P.iFlags &= ~AutoKept;
1064
1065    /* Target the candidate version and remove the autoflag. We reset the
1066       autoflag below if this was called recursively. Otherwise the user
1067       should have the ability to de-auto a package by changing its state */
1068    RemoveSizes(Pkg);
1069    RemoveStates(Pkg);
1070
1071    P.Mode = ModeInstall;
1072    P.InstallVer = P.CandidateVer;
1073
1074    if(FromUser)
1075      {
1076        // Set it to manual if it's a new install or already installed,
1077        // but only if its not marked by the autoremover (aptitude depend on this behavior)
1078        // or if we do automatic installation (aptitude never does it)
1079        if(P.Status == 2 || (Pkg->CurrentVer != 0 && (AutoInst == true || P.Marked == false)))
1080          P.Flags &= ~Flag::Auto;
1081      }
1082    else
1083      {
1084        // Set it to auto if this is a new install.
1085        if(P.Status == 2)
1086          P.Flags |= Flag::Auto;
1087      }
1088    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1089       P.Mode = ModeKeep;
1090
1091    AddStates(Pkg);
1092    Update(Pkg);
1093    AddSizes(Pkg);
1094
1095    if (AutoInst == false || _config->Find("APT::Solver", "internal") != "internal")
1096       return true;
1097
1098    if (DebugMarker == true)
1099       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1100
1101    DepIterator Dep = P.InstVerIter(*this).DependsList();
1102    for (; Dep.end() != true;)
1103    {
1104       // Grok or groups
1105       DepIterator Start = Dep;
1106       bool Result = true;
1107       unsigned Ors = 0;
1108       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1109       {
1110          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1111
1112          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1113             Result = false;
1114       }
1115
1116       // Dep is satisfied okay.
1117       if (Result == false)
1118          continue;
1119
1120       /* Check if this dep should be consider for install. If it is a user
1121          defined important dep and we are installed a new package then
1122          it will be installed. Otherwise we only check for important
1123          deps that have changed from the installed version */
1124       if (IsImportantDep(Start) == false)
1125          continue;
1126
1127       /* If we are in an or group locate the first or that can
1128          succeed. We have already cached this… */
1129       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1130          ++Start;
1131
1132       /* unsatisfiable dependency: IsInstallOkDependenciesSatisfiableByCandidates
1133          would have prevented us to get here if not overridden, so just skip
1134          over the problem here as the frontend will know what it is doing */
1135       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
1136          continue;
1137
1138       /* Check if any ImportantDep() (but not Critical) were added
1139        * since we installed the package.  Also check for deps that
1140        * were satisfied in the past: for instance, if a version
1141        * restriction in a Recommends was tightened, upgrading the
1142        * package should follow that Recommends rather than causing the
1143        * dependency to be removed. (bug #470115)
1144        */
1145       if (Pkg->CurrentVer != 0 && ForceImportantDeps == false && Start.IsCritical() == false)
1146       {
1147          bool isNewImportantDep = true;
1148          bool isPreviouslySatisfiedImportantDep = false;
1149          for (DepIterator D = Pkg.CurrentVer().DependsList(); D.end() != true; ++D)
1150          {
1151             //FIXME: Should we handle or-group better here?
1152             // We do not check if the package we look for is part of the same or-group
1153             // we might find while searching, but could that really be a problem?
1154             if (D.IsCritical() == true || IsImportantDep(D) == false ||
1155                 Start.TargetPkg() != D.TargetPkg())
1156                continue;
1157
1158             isNewImportantDep = false;
1159
1160             while ((D->CompareOp & Dep::Or) != 0)
1161                ++D;
1162
1163             isPreviouslySatisfiedImportantDep = (((*this)[D] & DepGNow) != 0);
1164             if (isPreviouslySatisfiedImportantDep == true)
1165                break;
1166          }
1167
1168          if(isNewImportantDep == true)
1169          {
1170             if (DebugAutoInstall == true)
1171                std::clog << OutputInDepth(Depth) << "new important dependency: "
1172                          << Start.TargetPkg().FullName() << std::endl;
1173          }
1174          else if(isPreviouslySatisfiedImportantDep == true)
1175          {
1176             if (DebugAutoInstall == true)
1177                std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1178                          << Start.TargetPkg().FullName() << std::endl;
1179          }
1180          else
1181          {
1182             if (DebugAutoInstall == true)
1183                std::clog << OutputInDepth(Depth) << "ignore old unsatisfied important dependency on "
1184                          << Start.TargetPkg().FullName() << std::endl;
1185             continue;
1186          }
1187       }
1188
1189       /* This bit is for processing the possibility of an install/upgrade
1190          fixing the problem for "positive" dependencies */
1191       if (Start.IsNegative() == false && (DepState[Start->ID] & DepCVer) == DepCVer)
1192       {
1193          pkgCacheFile CacheFile(this);
1194          APT::VersionList verlist = APT::VersionList::FromDependency(CacheFile, Start, APT::CacheSetHelper::CANDIDATE);
1195          CompareProviders comp(Start);
1196
1197          do {
1198             APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
1199
1200             if (InstVer == verlist.end())
1201                break;
1202
1203             pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
1204             if(DebugAutoInstall == true)
1205                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1206                          << " as " << Start.DepType() << " of " << Pkg.Name()
1207                          << std::endl;
1208             if (MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps) == false)
1209             {
1210                verlist.erase(InstVer);
1211                continue;
1212             }
1213             // now check if we should consider it a automatic dependency or not
1214             if(InstPkg->CurrentVer == 0 && InstVer->Section != 0 && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", InstVer.Section()))
1215             {
1216                if(DebugAutoInstall == true)
1217                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1218                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1219                MarkAuto(InstPkg, false);
1220             }
1221             break;
1222          } while(true);
1223          continue;
1224       }
1225       /* Negative dependencies have no or-group
1226          If the dependency isn't versioned, we try if an upgrade might solve the problem.
1227          Otherwise we remove the offender if needed */
1228       else if (Start.IsNegative() == true && Start->Type != pkgCache::Dep::Obsoletes)
1229       {
1230          SPtrArray<Version *> List = Start.AllTargets();
1231          pkgCache::PkgIterator TrgPkg = Start.TargetPkg();
1232          for (Version **I = List; *I != 0; I++)
1233          {
1234             VerIterator Ver(*this,*I);
1235             PkgIterator Pkg = Ver.ParentPkg();
1236
1237             /* The List includes all packages providing this dependency,
1238                even providers which are not installed, so skip them. */
1239             if (PkgState[Pkg->ID].InstallVer == 0)
1240                continue;
1241
1242             /* Ignore negative dependencies that we are not going to
1243                get installed */
1244             if (PkgState[Pkg->ID].InstallVer != *I)
1245                continue;
1246
1247             if ((Start->Version != 0 || TrgPkg != Pkg) &&
1248                 PkgState[Pkg->ID].CandidateVer != PkgState[Pkg->ID].InstallVer &&
1249                 PkgState[Pkg->ID].CandidateVer != *I &&
1250                 MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps) == true)
1251                continue;
1252             else if (Start->Type == pkgCache::Dep::Conflicts ||
1253                      Start->Type == pkgCache::Dep::DpkgBreaks)
1254             {
1255                if(DebugAutoInstall == true)
1256                   std::clog << OutputInDepth(Depth)
1257                             << " Removing: " << Pkg.Name()
1258                             << std::endl;
1259                if (MarkDelete(Pkg,false,Depth + 1, false) == false)
1260                   break;
1261             }
1262          }
1263          continue;
1264       }
1265    }
1266
1267    return Dep.end() == true;
1268 }
1269                                                                         /*}}}*/
1270 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1271 // ---------------------------------------------------------------------
1272 /* The default implementation checks if the installation of an M-A:same
1273    package would lead us into a version-screw and if so forbids it.
1274    dpkg holds are enforced by the private IsModeChangeOk */
1275 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1276                               unsigned long Depth, bool FromUser)
1277 {
1278    return IsInstallOkMultiArchSameVersionSynced(Pkg,AutoInst, Depth, FromUser) &&
1279       IsInstallOkDependenciesSatisfiableByCandidates(Pkg,AutoInst, Depth, FromUser);
1280 }
1281 bool pkgDepCache::IsInstallOkMultiArchSameVersionSynced(PkgIterator const &Pkg,
1282       bool const /*AutoInst*/, unsigned long const Depth, bool const FromUser)
1283 {
1284    if (FromUser == true) // as always: user is always right
1285       return true;
1286
1287    // if we have checked before and it was okay, it will still be okay
1288    if (PkgState[Pkg->ID].Mode == ModeInstall &&
1289          PkgState[Pkg->ID].InstallVer == PkgState[Pkg->ID].CandidateVer)
1290       return true;
1291
1292    // ignore packages with none-M-A:same candidates
1293    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1294    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer() ||
1295          (CandVer->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1296       return true;
1297
1298    GrpIterator const Grp = Pkg.Group();
1299    for (PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1300    {
1301       // not installed or self-check: fine by definition
1302       if (P->CurrentVer == 0 || P == Pkg)
1303          continue;
1304
1305       // not having a candidate or being in sync
1306       // (simple string-compare as stuff like '1' == '0:1-0' can't happen here)
1307       VerIterator CV = PkgState[P->ID].CandidateVerIter(*this);
1308       if (CV.end() == true || strcmp(Pkg.CandVersion(), CV.VerStr()) == 0)
1309          continue;
1310
1311       // packages losing M-A:same can be out-of-sync
1312       if ((CV->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1313          continue;
1314
1315       // not downloadable means the package is obsolete, so allow out-of-sync
1316       if (CV.Downloadable() == false)
1317          continue;
1318
1319       PkgState[Pkg->ID].iFlags |= AutoKept;
1320       if (unlikely(DebugMarker == true))
1321          std::clog << OutputInDepth(Depth) << "Ignore MarkInstall of " << Pkg
1322             << " as it is not in sync with its M-A:same sibling " << P
1323             << " (" << Pkg.CandVersion() << " != " << CV.VerStr() << ")" << std::endl;
1324       return false;
1325    }
1326
1327    return true;
1328 }
1329 bool pkgDepCache::IsInstallOkDependenciesSatisfiableByCandidates(PkgIterator const &Pkg,
1330       bool const AutoInst, unsigned long const Depth, bool const /*FromUser*/)
1331 {
1332    if (AutoInst == false)
1333       return true;
1334
1335    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1336    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer())
1337       return true;
1338
1339    for (DepIterator Dep = CandVer.DependsList(); Dep.end() != true;)
1340    {
1341       // Grok or groups
1342       DepIterator Start = Dep;
1343       bool Result = true;
1344       unsigned Ors = 0;
1345       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1346       {
1347          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1348
1349          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1350             Result = false;
1351       }
1352
1353       if (Start.IsCritical() == false || Start.IsNegative() == true || Result == false)
1354          continue;
1355
1356       /* If we are in an or group locate the first or that can succeed.
1357          We have already cached this… */
1358       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1359          ++Start;
1360
1361       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer)
1362       {
1363          if (DebugAutoInstall == true)
1364             std::clog << OutputInDepth(Depth) << Start << " can't be satisfied!" << std::endl;
1365
1366          // the dependency is critical, but can't be installed, so discard the candidate
1367          // as the problemresolver will trip over it otherwise trying to install it (#735967)
1368          if (Pkg->CurrentVer != 0 && (PkgState[Pkg->ID].iFlags & Protected) != Protected)
1369             SetCandidateVersion(Pkg.CurrentVer());
1370          return false;
1371       }
1372    }
1373
1374    return true;
1375 }
1376                                                                         /*}}}*/
1377 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1378 // ---------------------------------------------------------------------
1379 /* */
1380 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1381 {
1382    if (unlikely(Pkg.end() == true))
1383       return;
1384
1385    APT::PackageList pkglist;
1386    if (Pkg->CurrentVer != 0 &&
1387        (Pkg.CurrentVer()-> MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
1388    {
1389       pkgCache::GrpIterator Grp = Pkg.Group();
1390       for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1391       {
1392          if (P->CurrentVer != 0)
1393             pkglist.insert(P);
1394       }
1395    }
1396    else
1397       pkglist.insert(Pkg);
1398
1399    ActionGroup group(*this);
1400
1401    for (APT::PackageList::const_iterator Pkg = pkglist.begin(); Pkg != pkglist.end(); ++Pkg)
1402    {
1403       RemoveSizes(Pkg);
1404       RemoveStates(Pkg);
1405
1406       StateCache &P = PkgState[Pkg->ID];
1407       if (To == true)
1408          P.iFlags |= ReInstall;
1409       else
1410          P.iFlags &= ~ReInstall;
1411
1412       AddStates(Pkg);
1413       AddSizes(Pkg);
1414    }
1415 }
1416                                                                         /*}}}*/
1417 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1418 // ---------------------------------------------------------------------
1419 /* */
1420 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1421 {
1422    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1423    StateCache &P = PkgState[Pkg->ID];
1424
1425    if (P.CandidateVer == TargetVer)
1426       return;
1427
1428    ActionGroup group(*this);
1429
1430    RemoveSizes(Pkg);
1431    RemoveStates(Pkg);
1432
1433    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1434       P.InstallVer = (Version *)TargetVer;
1435    P.CandidateVer = (Version *)TargetVer;
1436    P.Update(Pkg,*this);
1437
1438    AddStates(Pkg);
1439    Update(Pkg);
1440    AddSizes(Pkg);
1441
1442 }
1443                                                                         /*}}}*/
1444 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1445 // ---------------------------------------------------------------------
1446 /* changes the candidate of a package and walks over all its dependencies
1447    to check if it needs to change the candidate of the dependency, too,
1448    to reach a installable versionstate */
1449 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1450                                         std::string const &TargetRel)
1451 {
1452    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1453    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1454 }
1455 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1456                                         std::string const &TargetRel,
1457                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1458 {
1459    ActionGroup group(*this);
1460    SetCandidateVersion(TargetVer);
1461
1462    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1463       return true;
1464
1465    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1466    // save the position of the last element we will not undo - if we have to
1467    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1468
1469    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1470    {
1471       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1472           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1473            IsImportantDep(D) == false))
1474          continue;
1475
1476       // walk over an or-group and check if we need to do anything
1477       // for simpilicity no or-group is handled as a or-group including one dependency
1478       pkgCache::DepIterator Start = D;
1479       bool itsFine = false;
1480       for (bool stillOr = true; stillOr == true; ++Start)
1481       {
1482          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1483          pkgCache::PkgIterator const P = Start.TargetPkg();
1484          // virtual packages can't be a solution
1485          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1486             continue;
1487          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1488          // no versioned dependency - but is it installable?
1489          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1490          {
1491             // Check if one of the providers is installable
1492             if (P->ProvidesList != 0)
1493             {
1494                pkgCache::PrvIterator Prv = P.ProvidesList();
1495                for (; Prv.end() == false; ++Prv)
1496                {
1497                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1498                   if (C.end() == true || C != Prv.OwnerVer() ||
1499                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1500                      continue;
1501                   break;
1502                }
1503                if (Prv.end() == true)
1504                   continue;
1505             }
1506             // no providers, so check if we have an installable candidate version
1507             else if (Cand.end() == true ||
1508                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1509                continue;
1510             itsFine = true;
1511             break;
1512          }
1513          if (Cand.end() == true)
1514             continue;
1515          // check if the current candidate is enough for the versioned dependency - and installable?
1516          if (Start.IsSatisfied(Cand) == true &&
1517              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1518          {
1519             itsFine = true;
1520             break;
1521          }
1522       }
1523
1524       if (itsFine == true) {
1525          // something in the or-group was fine, skip all other members
1526          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1527          continue;
1528       }
1529
1530       // walk again over the or-group and check each if a candidate switch would help
1531       itsFine = false;
1532       for (bool stillOr = true; stillOr == true; ++D)
1533       {
1534          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1535          // changing candidate will not help if the dependency is not versioned
1536          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1537          {
1538             if (stillOr == true)
1539                continue;
1540             break;
1541          }
1542
1543          pkgCache::VerIterator V;
1544          if (TargetRel == "newest")
1545             V = D.TargetPkg().VersionList();
1546          else
1547             V = Match.Find(D.TargetPkg());
1548
1549          // check if the version from this release could satisfy the dependency
1550          if (V.end() == true || D.IsSatisfied(V) == false)
1551          {
1552             if (stillOr == true)
1553                continue;
1554             break;
1555          }
1556
1557          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1558          if (V == oldCand)
1559          {
1560             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1561             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1562                  c != Changed.end(); ++c)
1563             {
1564                if (c->first->ParentPkg != V->ParentPkg)
1565                   continue;
1566                itsFine = true;
1567                break;
1568             }
1569          }
1570
1571          if (itsFine == false)
1572          {
1573             // change the candidate
1574             Changed.push_back(make_pair(V, TargetVer));
1575             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1576             {
1577                if (stillOr == false)
1578                   break;
1579                // undo the candidate changing
1580                SetCandidateVersion(oldCand);
1581                Changed.pop_back();
1582                continue;
1583             }
1584             itsFine = true;
1585          }
1586
1587          // something in the or-group was fine, skip all other members
1588          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1589          break;
1590       }
1591
1592       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1593       {
1594          // undo all changes which aren't lead to a solution
1595          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1596               c != Changed.end(); ++c)
1597             SetCandidateVersion(c->first);
1598          Changed.erase(newChanged, Changed.end());
1599          return false;
1600       }
1601    }
1602    return true;
1603 }
1604                                                                         /*}}}*/
1605 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1606 // ---------------------------------------------------------------------
1607 /* */
1608 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1609 {
1610   StateCache &state = PkgState[Pkg->ID];
1611
1612   ActionGroup group(*this);
1613
1614   if(Auto)
1615     state.Flags |= Flag::Auto;
1616   else
1617     state.Flags &= ~Flag::Auto;
1618 }
1619                                                                         /*}}}*/
1620 // StateCache::Update - Compute the various static display things       /*{{{*/
1621 // ---------------------------------------------------------------------
1622 /* This is called whenever the Candidate version changes. */
1623 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1624 {
1625    // Some info
1626    VerIterator Ver = CandidateVerIter(Cache);
1627
1628    // Use a null string or the version string
1629    if (Ver.end() == true)
1630       CandVersion = "";
1631    else
1632       CandVersion = Ver.VerStr();
1633
1634    // Find the current version
1635    CurVersion = "";
1636    if (Pkg->CurrentVer != 0)
1637       CurVersion = Pkg.CurrentVer().VerStr();
1638
1639    // Strip off the epochs for display
1640    CurVersion = StripEpoch(CurVersion);
1641    CandVersion = StripEpoch(CandVersion);
1642
1643    // Figure out if its up or down or equal
1644    Status = Ver.CompareVer(Pkg.CurrentVer());
1645    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1646      Status = 2;
1647 }
1648                                                                         /*}}}*/
1649 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1650 // ---------------------------------------------------------------------
1651 /* */
1652 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1653 {
1654    if (Ver == 0)
1655       return 0;
1656
1657    // Strip any epoch
1658    for (const char *I = Ver; *I != 0; I++)
1659       if (*I == ':')
1660          return I + 1;
1661    return Ver;
1662 }
1663                                                                         /*}}}*/
1664 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1665 // ---------------------------------------------------------------------
1666 /* The default just returns the highest available version that is not
1667    a source and automatic. */
1668 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1669 {
1670    /* Not source/not automatic versions cannot be a candidate version
1671       unless they are already installed */
1672    VerIterator Last;
1673
1674    for (VerIterator I = Pkg.VersionList(); I.end() == false; ++I)
1675    {
1676       if (Pkg.CurrentVer() == I)
1677          return I;
1678
1679       for (VerFileIterator J = I.FileList(); J.end() == false; ++J)
1680       {
1681          if (J.File().Flagged(Flag::NotSource))
1682             continue;
1683
1684          /* Stash the highest version of a not-automatic source, we use it
1685             if there is nothing better */
1686          if (J.File().Flagged(Flag::NotAutomatic) ||
1687              J.File().Flagged(Flag::ButAutomaticUpgrades))
1688          {
1689             if (Last.end() == true)
1690                Last = I;
1691             continue;
1692          }
1693
1694          return I;
1695       }
1696    }
1697
1698    return Last;
1699 }
1700                                                                         /*}}}*/
1701 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1702 // ---------------------------------------------------------------------
1703 /* */
1704 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
1705 {
1706    if(Dep.IsCritical())
1707       return true;
1708    else if(Dep->Type == pkgCache::Dep::Recommends)
1709    {
1710       if (InstallRecommends)
1711          return true;
1712       // we suport a special mode to only install-recommends for certain
1713       // sections
1714       // FIXME: this is a meant as a temporarly solution until the
1715       //        recommends are cleaned up
1716       const char *sec = Dep.ParentVer().Section();
1717       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1718          return true;
1719    }
1720    else if(Dep->Type == pkgCache::Dep::Suggests)
1721       return InstallSuggests;
1722
1723    return false;
1724 }
1725                                                                         /*}}}*/
1726 // Policy::GetPriority - Get the priority of the package pin            /*{{{*/
1727 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &/*Pkg*/)
1728 { return 0; }
1729 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &/*File*/)
1730 { return 0; }
1731                                                                         /*}}}*/
1732 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1733 {
1734   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1735   if(f->wasConstructedSuccessfully())
1736     return f;
1737   else
1738     {
1739       delete f;
1740       return NULL;
1741     }
1742 }
1743                                                                         /*}}}*/
1744 bool pkgDepCache::MarkFollowsRecommends()
1745 {
1746   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1747 }
1748
1749 bool pkgDepCache::MarkFollowsSuggests()
1750 {
1751   return _config->FindB("APT::AutoRemove::SuggestsImportant", true);
1752 }
1753
1754 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1755 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1756 {
1757    if (_config->Find("APT::Solver", "internal") != "internal")
1758       return true;
1759
1760    bool follow_recommends;
1761    bool follow_suggests;
1762    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1763
1764    // init the states
1765    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1766    {
1767       PkgState[p->ID].Marked  = false;
1768       PkgState[p->ID].Garbage = false;
1769
1770       // debug output
1771       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1772          std::clog << "AutoDep: " << p.FullName() << std::endl;
1773    }
1774
1775    // init vars
1776    follow_recommends = MarkFollowsRecommends();
1777    follow_suggests   = MarkFollowsSuggests();
1778
1779    // do the mark part, this is the core bit of the algorithm
1780    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1781    {
1782       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1783           (p->Flags & Flag::Essential) ||
1784           (p->Flags & Flag::Important) ||
1785           userFunc.InRootSet(p) ||
1786           // be nice even then a required package violates the policy (#583517)
1787           // and do the full mark process also for required packages
1788           (p.CurrentVer().end() != true &&
1789            p.CurrentVer()->Priority == pkgCache::State::Required) ||
1790           // packages which can't be changed (like holds) can't be garbage
1791           (IsModeChangeOk(ModeGarbage, p, 0, false) == false))
1792       {
1793          // the package is installed (and set to keep)
1794          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1795             MarkPackage(p, p.CurrentVer(),
1796                         follow_recommends, follow_suggests);
1797          // the package is to be installed
1798          else if(PkgState[p->ID].Install())
1799             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1800                         follow_recommends, follow_suggests);
1801       }
1802    }
1803
1804    return true;
1805 }
1806                                                                         /*}}}*/
1807 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1808 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1809                               const pkgCache::VerIterator &ver,
1810                               bool const &follow_recommends,
1811                               bool const &follow_suggests)
1812 {
1813    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1814
1815    // if we are marked already we are done
1816    if(state.Marked)
1817       return;
1818
1819    VerIterator const currver = pkg.CurrentVer();
1820    VerIterator const instver = state.InstVerIter(*this);
1821
1822 #if 0
1823    VerIterator const candver = state.CandidateVerIter(*this);
1824
1825    // If a package was garbage-collected but is now being marked, we
1826    // should re-select it
1827    // For cases when a pkg is set to upgrade and this trigger the
1828    // removal of a no-longer used dependency.  if the pkg is set to
1829    // keep again later it will result in broken deps
1830    if(state.Delete() && state.RemoveReason = Unused)
1831    {
1832       if(ver==candver)
1833          mark_install(pkg, false, false, NULL);
1834       else if(ver==pkg.CurrentVer())
1835          MarkKeep(pkg, false, false);
1836
1837       instver=state.InstVerIter(*this);
1838    }
1839 #endif
1840
1841    // For packages that are not going to be removed, ignore versions
1842    // other than the InstVer.  For packages that are going to be
1843    // removed, ignore versions other than the current version.
1844    if(!(ver == instver && !instver.end()) &&
1845       !(ver == currver && instver.end() && !ver.end()))
1846       return;
1847
1848    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1849
1850    if(debug_autoremove)
1851      {
1852        std::clog << "Marking: " << pkg.FullName();
1853        if(!ver.end())
1854          std::clog << " " << ver.VerStr();
1855        if(!currver.end())
1856          std::clog << ", Curr=" << currver.VerStr();
1857        if(!instver.end())
1858          std::clog << ", Inst=" << instver.VerStr();
1859        std::clog << std::endl;
1860      }
1861
1862    state.Marked=true;
1863
1864    if(ver.end() == true)
1865       return;
1866
1867      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1868      {
1869         if(d->Type == Dep::Depends ||
1870            d->Type == Dep::PreDepends ||
1871            (follow_recommends &&
1872             d->Type == Dep::Recommends) ||
1873            (follow_suggests &&
1874             d->Type == Dep::Suggests))
1875         {
1876            // Try all versions of this package.
1877            for(VerIterator V = d.TargetPkg().VersionList();
1878                !V.end(); ++V)
1879            {
1880               if(d.IsSatisfied(V))
1881               {
1882                 if(debug_autoremove)
1883                   {
1884                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1885                               << " " << d.ParentVer().VerStr() << " "
1886                               << d.DepType() << " " << d.TargetPkg().FullName();
1887                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1888                       {
1889                         std::clog << " (" << d.CompType() << " "
1890                                   << d.TargetVer() << ")";
1891                       }
1892                     std::clog << std::endl;
1893                   }
1894                  MarkPackage(V.ParentPkg(), V,
1895                              follow_recommends, follow_suggests);
1896               }
1897            }
1898            // Now try virtual packages
1899            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1900                !prv.end(); ++prv)
1901            {
1902               if(d.IsSatisfied(prv))
1903               {
1904                 if(debug_autoremove)
1905                   {
1906                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1907                               << d.ParentVer().VerStr() << " "
1908                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1909                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1910                       {
1911                         std::clog << " (" << d.CompType() << " "
1912                                   << d.TargetVer() << ")";
1913                       }
1914                     std::clog << ", provided by "
1915                               << prv.OwnerPkg().FullName() << " "
1916                               << prv.OwnerVer().VerStr()
1917                               << std::endl;
1918                   }
1919
1920                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1921                              follow_recommends, follow_suggests);
1922               }
1923            }
1924         }
1925      }
1926 }
1927                                                                         /*}}}*/
1928 bool pkgDepCache::Sweep()                                               /*{{{*/
1929 {
1930    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1931
1932    // do the sweep
1933    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1934    {
1935      StateCache &state=PkgState[p->ID];
1936
1937      // skip required packages
1938      if (!p.CurrentVer().end() &&
1939          (p.CurrentVer()->Priority == pkgCache::State::Required))
1940         continue;
1941
1942      // if it is not marked and it is installed, it's garbage
1943      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1944      {
1945         state.Garbage=true;
1946         if(debug_autoremove)
1947            std::clog << "Garbage: " << p.FullName() << std::endl;
1948      }
1949   }
1950
1951    return true;
1952 }
1953                                                                         /*}}}*/
1954 // DepCache::MarkAndSweep                                               /*{{{*/
1955 bool pkgDepCache::MarkAndSweep(InRootSetFunc &rootFunc)
1956 {
1957    return MarkRequired(rootFunc) && Sweep();
1958 }
1959 bool pkgDepCache::MarkAndSweep()
1960 {
1961    std::auto_ptr<InRootSetFunc> f(GetRootSetFunc());
1962    if(f.get() != NULL)
1963       return MarkAndSweep(*f.get());
1964    else
1965       return false;
1966 }
1967                                                                         /*}}}*/