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