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