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    iDelCount = 0;
 667    iInstCount = 0;
 668    iKeepCount = 0;
 669    iBrokenCount = 0;
 670    iBadCount = 0;
 671
 672    // Perform the depends pass
 673    int Done = 0;
 674    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 675    {
 676       if (Prog != 0 && Done%20 == 0)
 677          Prog->Progress(Done);
 678       for (VerIterator V = I.VersionList(); V.end() != true; ++V)
 679       {
 680          unsigned char Group = 0;
 681
 682          for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 683          {
 684             // Build the dependency state.
 685             unsigned char &State = DepState[D->ID];
 686             State = DependencyState(D);
 687
 688             // Add to the group if we are within an or..
 689             Group |= State;
 690             State |= Group << 3;
 691             if ((D->CompareOp & Dep::Or) != Dep::Or)
 692                Group = 0;
 693
 694             // Invert for Conflicts
 695             if (D.IsNegative() == true)
 696                State = ~State;
 697          }
 698       }
 699
 700       // Compute the package dependency state and size additions
 701       AddSizes(I);
 702       UpdateVerState(I);
 703       AddStates(I);
 704    }
 705
 706    if (Prog != 0)
 707       Prog->Progress(Done);
 708
 709    readStateFile(Prog);
 710 }
 711                                                                         /*}}}*/
 712 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 713 // ---------------------------------------------------------------------
 714 /* This is a helper for update that only does the dep portion of the scan.
 715    It is mainly meant to scan reverse dependencies. */
 716 void pkgDepCache::Update(DepIterator D)
 717 {
 718    // Update the reverse deps
 719    for (;D.end() != true; ++D)
 720    {
 721       unsigned char &State = DepState[D->ID];
 722       State = DependencyState(D);
 723
 724       // Invert for Conflicts
 725       if (D.IsNegative() == true)
 726          State = ~State;
 727
 728       RemoveStates(D.ParentPkg());
 729       BuildGroupOrs(D.ParentVer());
 730       UpdateVerState(D.ParentPkg());
 731       AddStates(D.ParentPkg());
 732    }
 733 }
 734                                                                         /*}}}*/
 735 // DepCache::Update - Update the related deps of a package              /*{{{*/
 736 // ---------------------------------------------------------------------
 737 /* This is called whenever the state of a package changes. It updates
 738    all cached dependencies related to this package. */
 739 void pkgDepCache::Update(PkgIterator const &Pkg)
 740 {
 741    // Recompute the dep of the package
 742    RemoveStates(Pkg);
 743    UpdateVerState(Pkg);
 744    AddStates(Pkg);
 745
 746    // Update the reverse deps
 747    Update(Pkg.RevDependsList());
 748
 749    // Update the provides map for the current ver
 750    if (Pkg->CurrentVer != 0)
 751       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 752            P.end() != true; ++P)
 753          Update(P.ParentPkg().RevDependsList());
 754
 755    // Update the provides map for the candidate ver
 756    if (PkgState[Pkg->ID].CandidateVer != 0)
 757       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 758            P.end() != true; ++P)
 759          Update(P.ParentPkg().RevDependsList());
 760 }
 761                                                                         /*}}}*/
 762 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 763 // ---------------------------------------------------------------------
 764 /* */
 765 bool pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 766                            unsigned long Depth)
 767 {
 768    if (IsModeChangeOk(ModeKeep, Pkg, Depth, FromUser) == false)
 769       return false;
 770
 771    /* Reject an attempt to keep a non-source broken installed package, those
 772       must be upgraded */
 773    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 774        Pkg.CurrentVer().Downloadable() == false)
 775       return false;
 776
 777    /* We changed the soft state all the time so the UI is a bit nicer
 778       to use */
 779    StateCache &P = PkgState[Pkg->ID];
 780
 781    // Check that it is not already kept
 782    if (P.Mode == ModeKeep)
 783       return true;
 784
 785    if (Soft == true)
 786       P.iFlags |= AutoKept;
 787    else
 788       P.iFlags &= ~AutoKept;
 789
 790    ActionGroup group(*this);
 791
 792 #if 0 // reseting the autoflag here means we lose the
 793       // auto-mark information if a user selects a package for removal
 794       // but changes  his mind then and sets it for keep again
 795       // - this makes sense as default when all Garbage dependencies
 796       //   are automatically marked for removal (as aptitude does).
 797       //   setting a package for keep then makes it no longer autoinstalled
 798       //   for all other use-case this action is rather surprising
 799    if(FromUser && !P.Marked)
 800      P.Flags &= ~Flag::Auto;
 801 #endif
 802
 803    if (DebugMarker == true)
 804       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 805
 806    RemoveSizes(Pkg);
 807    RemoveStates(Pkg);
 808
 809    P.Mode = ModeKeep;
 810    if (Pkg->CurrentVer == 0)
 811       P.InstallVer = 0;
 812    else
 813       P.InstallVer = Pkg.CurrentVer();
 814
 815    AddStates(Pkg);
 816    Update(Pkg);
 817    AddSizes(Pkg);
 818
 819    return true;
 820 }
 821                                                                         /*}}}*/
 822 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 823 // ---------------------------------------------------------------------
 824 /* */
 825 bool pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 826                              unsigned long Depth, bool FromUser)
 827 {
 828    if (IsModeChangeOk(ModeDelete, Pkg, Depth, FromUser) == false)
 829       return false;
 830
 831    StateCache &P = PkgState[Pkg->ID];
 832
 833    // Check that it is not already marked for delete
 834    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 835        (Pkg.Purge() == true || rPurge == false))
 836       return true;
 837
 838    // check if we are allowed to remove the package
 839    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
 840       return false;
 841
 842    P.iFlags &= ~(AutoKept | Purge);
 843    if (rPurge == true)
 844       P.iFlags |= Purge;
 845
 846    ActionGroup group(*this);
 847
 848    if (DebugMarker == true)
 849       std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << Pkg << " FU=" << FromUser << std::endl;
 850
 851    RemoveSizes(Pkg);
 852    RemoveStates(Pkg);
 853
 854    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 855       P.Mode = ModeKeep;
 856    else
 857       P.Mode = ModeDelete;
 858    P.InstallVer = 0;
 859
 860    AddStates(Pkg);
 861    Update(Pkg);
 862    AddSizes(Pkg);
 863
 864    return true;
 865 }
 866                                                                         /*}}}*/
 867 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 868 // ---------------------------------------------------------------------
 869 /* The default implementation tries to prevent deletion of install requests.
 870    dpkg holds are enforced by the private IsModeChangeOk */
 871 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 872                               unsigned long Depth, bool FromUser)
 873 {
 874    return IsDeleteOkProtectInstallRequests(Pkg, rPurge, Depth, FromUser);
 875 }
 876 bool pkgDepCache::IsDeleteOkProtectInstallRequests(PkgIterator const &Pkg,
 877       bool const /*rPurge*/, unsigned long const Depth, bool const FromUser)
 878 {
 879    if (FromUser == false && Pkg->CurrentVer == 0)
 880    {
 881       StateCache &P = PkgState[Pkg->ID];
 882       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
 883       {
 884          if (DebugMarker == true)
 885             std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << Pkg << std::endl;
 886          return false;
 887       }
 888    }
 889    return true;
 890 }
 891                                                                         /*}}}*/
 892 // DepCache::IsModeChangeOk - check if it is ok to change the mode      /*{{{*/
 893 // ---------------------------------------------------------------------
 894 /* this is used by all Mark methods on the very first line to check sanity
 895    and prevents mode changes for packages on hold for example.
 896    If you want to check Mode specific stuff you can use the virtual public
 897    Is<Mode>Ok methods instead */
 898 static char const* PrintMode(char const mode)
 899 {
 900          switch (mode)
 901          {
 902          case pkgDepCache::ModeInstall: return "Install";
 903          case pkgDepCache::ModeKeep: return "Keep";
 904          case pkgDepCache::ModeDelete: return "Delete";
 905          case pkgDepCache::ModeGarbage: return "Garbage";
 906          default: return "UNKNOWN";
 907          }
 908 }
 909 bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
 910                                  unsigned long const Depth, bool const FromUser)
 911 {
 912    // we are not trying to hard…
 913    if (unlikely(Depth > 100))
 914       return false;
 915
 916    // general sanity
 917    if (unlikely(Pkg.end() == true || Pkg->VersionList == 0))
 918       return false;
 919
 920    // the user is always right
 921    if (FromUser == true)
 922       return true;
 923
 924    StateCache &P = PkgState[Pkg->ID];
 925    // not changing the mode is obviously also fine as we might want to call
 926    // e.g. MarkInstall multiple times with different arguments for the same package
 927    if (P.Mode == mode)
 928       return true;
 929
 930    // if previous state was set by user only user can reset it
 931    if ((P.iFlags & Protected) == Protected)
 932    {
 933       if (unlikely(DebugMarker == true))
 934          std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
 935                    << " of " << Pkg << " as its mode (" << PrintMode(P.Mode)
 936                    << ") is protected" << std::endl;
 937       return false;
 938    }
 939    // enforce dpkg holds
 940    else if (mode != ModeKeep && Pkg->SelectedState == pkgCache::State::Hold &&
 941             _config->FindB("APT::Ignore-Hold",false) == false)
 942    {
 943       if (unlikely(DebugMarker == true))
 944          std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
 945                    << " of " << Pkg << std::endl;
 946       return false;
 947    }
 948
 949    return true;
 950 }
 951                                                                         /*}}}*/
 952 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 953 // ---------------------------------------------------------------------
 954 /* */
 955 struct CompareProviders {
 956    pkgCache::PkgIterator const Pkg;
 957    CompareProviders(pkgCache::DepIterator const &Dep) : Pkg(Dep.TargetPkg()) {};
 958    //bool operator() (APT::VersionList::iterator const &AV, APT::VersionList::iterator const &BV)
 959    bool operator() (pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
 960    {
 961       pkgCache::PkgIterator const A = AV.ParentPkg();
 962       pkgCache::PkgIterator const B = BV.ParentPkg();
 963       // Prefer MA:same packages if other architectures for it are installed
 964       if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same ||
 965           (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 966       {
 967          bool instA = false;
 968          if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 969          {
 970             pkgCache::GrpIterator Grp = A.Group();
 971             for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
 972                if (P->CurrentVer != 0)
 973                {
 974                   instA = true;
 975                   break;
 976                }
 977          }
 978          bool instB = false;
 979          if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 980          {
 981             pkgCache::GrpIterator Grp = B.Group();
 982             for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
 983             {
 984                if (P->CurrentVer != 0)
 985                {
 986                   instB = true;
 987                   break;
 988                }
 989             }
 990          }
 991          if (instA != instB)
 992             return instA == false;
 993       }
 994       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
 995       if (A->Group != B->Group)
 996       {
 997          if (A->Group == Pkg->Group && B->Group != Pkg->Group)
 998             return false;
 999          else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
1000             return true;
1001       }
1002       // we like essentials
1003       if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
1004       {
1005          if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1006             return false;
1007          else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1008             return true;
1009       }
1010       if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
1011       {
1012          if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1013             return false;
1014          else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1015             return true;
1016       }
1017       // prefer native architecture
1018       if (strcmp(A.Arch(), B.Arch()) != 0)
1019       {
1020          if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
1021             return false;
1022          else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
1023             return true;
1024          std::vector<std::string> archs = APT::Configuration::getArchitectures();
1025          for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
1026             if (*a == A.Arch())
1027                return false;
1028             else if (*a == B.Arch())
1029                return true;
1030       }
1031       // higher priority seems like a good idea
1032       if (AV->Priority != BV->Priority)
1033          return AV->Priority > BV->Priority;
1034       // unable to decide…
1035       return A->ID < B->ID;
1036    }
1037 };
1038 bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
1039                               unsigned long Depth, bool FromUser,
1040                               bool ForceImportantDeps)
1041 {
1042    if (IsModeChangeOk(ModeInstall, Pkg, Depth, FromUser) == false)
1043       return false;
1044
1045    StateCache &P = PkgState[Pkg->ID];
1046
1047    // See if there is even any possible instalation candidate
1048    if (P.CandidateVer == 0)
1049       return false;
1050
1051    /* Check that it is not already marked for install and that it can be
1052       installed */
1053    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1054        (P.Mode == ModeInstall ||
1055         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1056    {
1057       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1058          return MarkKeep(Pkg, false, FromUser, Depth+1);
1059       return true;
1060    }
1061
1062    // check if we are allowed to install the package
1063    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1064       return false;
1065
1066    ActionGroup group(*this);
1067    P.iFlags &= ~AutoKept;
1068
1069    /* Target the candidate version and remove the autoflag. We reset the
1070       autoflag below if this was called recursively. Otherwise the user
1071       should have the ability to de-auto a package by changing its state */
1072    RemoveSizes(Pkg);
1073    RemoveStates(Pkg);
1074
1075    P.Mode = ModeInstall;
1076    P.InstallVer = P.CandidateVer;
1077
1078    if(FromUser)
1079      {
1080        // Set it to manual if it's a new install or already installed,
1081        // but only if its not marked by the autoremover (aptitude depend on this behavior)
1082        // or if we do automatic installation (aptitude never does it)
1083        if(P.Status == 2 || (Pkg->CurrentVer != 0 && (AutoInst == true || P.Marked == false)))
1084          P.Flags &= ~Flag::Auto;
1085      }
1086    else
1087      {
1088        // Set it to auto if this is a new install.
1089        if(P.Status == 2)
1090          P.Flags |= Flag::Auto;
1091      }
1092    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1093       P.Mode = ModeKeep;
1094
1095    AddStates(Pkg);
1096    Update(Pkg);
1097    AddSizes(Pkg);
1098
1099    if (AutoInst == false || _config->Find("APT::Solver", "internal") != "internal")
1100       return true;
1101
1102    if (DebugMarker == true)
1103       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1104
1105    DepIterator Dep = P.InstVerIter(*this).DependsList();
1106    for (; Dep.end() != true;)
1107    {
1108       // Grok or groups
1109       DepIterator Start = Dep;
1110       bool Result = true;
1111       unsigned Ors = 0;
1112       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1113       {
1114          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1115
1116          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1117             Result = false;
1118       }
1119
1120       // Dep is satisfied okay.
1121       if (Result == false)
1122          continue;
1123
1124       /* Check if this dep should be consider for install. If it is a user
1125          defined important dep and we are installed a new package then
1126          it will be installed. Otherwise we only check for important
1127          deps that have changed from the installed version */
1128       if (IsImportantDep(Start) == false)
1129          continue;
1130
1131       /* If we are in an or group locate the first or that can
1132          succeed. We have already cached this… */
1133       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1134          ++Start;
1135
1136       /* unsatisfiable dependency: IsInstallOkDependenciesSatisfiableByCandidates
1137          would have prevented us to get here if not overridden, so just skip
1138          over the problem here as the frontend will know what it is doing */
1139       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
1140          continue;
1141
1142       /* Check if any ImportantDep() (but not Critical) were added
1143        * since we installed the package.  Also check for deps that
1144        * were satisfied in the past: for instance, if a version
1145        * restriction in a Recommends was tightened, upgrading the
1146        * package should follow that Recommends rather than causing the
1147        * dependency to be removed. (bug #470115)
1148        */
1149       if (Pkg->CurrentVer != 0 && ForceImportantDeps == false && Start.IsCritical() == false)
1150       {
1151          bool isNewImportantDep = true;
1152          bool isPreviouslySatisfiedImportantDep = false;
1153          for (DepIterator D = Pkg.CurrentVer().DependsList(); D.end() != true; ++D)
1154          {
1155             //FIXME: Should we handle or-group better here?
1156             // We do not check if the package we look for is part of the same or-group
1157             // we might find while searching, but could that really be a problem?
1158             if (D.IsCritical() == true || IsImportantDep(D) == false ||
1159                 Start.TargetPkg() != D.TargetPkg())
1160                continue;
1161
1162             isNewImportantDep = false;
1163
1164             while ((D->CompareOp & Dep::Or) != 0)
1165                ++D;
1166
1167             isPreviouslySatisfiedImportantDep = (((*this)[D] & DepGNow) != 0);
1168             if (isPreviouslySatisfiedImportantDep == true)
1169                break;
1170          }
1171
1172          if(isNewImportantDep == true)
1173          {
1174             if (DebugAutoInstall == true)
1175                std::clog << OutputInDepth(Depth) << "new important dependency: "
1176                          << Start.TargetPkg().FullName() << std::endl;
1177          }
1178          else if(isPreviouslySatisfiedImportantDep == true)
1179          {
1180             if (DebugAutoInstall == true)
1181                std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1182                          << Start.TargetPkg().FullName() << std::endl;
1183          }
1184          else
1185          {
1186             if (DebugAutoInstall == true)
1187                std::clog << OutputInDepth(Depth) << "ignore old unsatisfied important dependency on "
1188                          << Start.TargetPkg().FullName() << std::endl;
1189             continue;
1190          }
1191       }
1192
1193       /* This bit is for processing the possibility of an install/upgrade
1194          fixing the problem for "positive" dependencies */
1195       if (Start.IsNegative() == false && (DepState[Start->ID] & DepCVer) == DepCVer)
1196       {
1197          APT::VersionList verlist;
1198          pkgCache::VerIterator Cand = PkgState[Start.TargetPkg()->ID].CandidateVerIter(*this);
1199          if (Cand.end() == false && Start.IsSatisfied(Cand) == true)
1200             verlist.insert(Cand);
1201          for (PrvIterator Prv = Start.TargetPkg().ProvidesList(); Prv.end() != true; ++Prv)
1202          {
1203             pkgCache::VerIterator V = Prv.OwnerVer();
1204             pkgCache::VerIterator Cand = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1205             if (Cand.end() == true || V != Cand || Start.IsSatisfied(Prv) == false)
1206                continue;
1207             verlist.insert(Cand);
1208          }
1209          CompareProviders comp(Start);
1210
1211          do {
1212             APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
1213
1214             if (InstVer == verlist.end())
1215                break;
1216
1217             pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
1218             if(DebugAutoInstall == true)
1219                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1220                          << " as " << Start.DepType() << " of " << Pkg.Name()
1221                          << std::endl;
1222             if (MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps) == false)
1223             {
1224                verlist.erase(InstVer);
1225                continue;
1226             }
1227             // now check if we should consider it a automatic dependency or not
1228             if(InstPkg->CurrentVer == 0 && Pkg->Section != 0 && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1229             {
1230                if(DebugAutoInstall == true)
1231                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1232                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1233                MarkAuto(InstPkg, false);
1234             }
1235             break;
1236          } while(true);
1237          continue;
1238       }
1239       /* Negative dependencies have no or-group
1240          If the dependency isn't versioned, we try if an upgrade might solve the problem.
1241          Otherwise we remove the offender if needed */
1242       else if (Start.IsNegative() == true && Start->Type != pkgCache::Dep::Obsoletes)
1243       {
1244          SPtrArray<Version *> List = Start.AllTargets();
1245          pkgCache::PkgIterator TrgPkg = Start.TargetPkg();
1246          for (Version **I = List; *I != 0; I++)
1247          {
1248             VerIterator Ver(*this,*I);
1249             PkgIterator Pkg = Ver.ParentPkg();
1250
1251             /* The List includes all packages providing this dependency,
1252                even providers which are not installed, so skip them. */
1253             if (PkgState[Pkg->ID].InstallVer == 0)
1254                continue;
1255
1256             /* Ignore negative dependencies that we are not going to
1257                get installed */
1258             if (PkgState[Pkg->ID].InstallVer != *I)
1259                continue;
1260
1261             if ((Start->Version != 0 || TrgPkg != Pkg) &&
1262                 PkgState[Pkg->ID].CandidateVer != PkgState[Pkg->ID].InstallVer &&
1263                 PkgState[Pkg->ID].CandidateVer != *I &&
1264                 MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps) == true)
1265                continue;
1266             else if (Start->Type == pkgCache::Dep::Conflicts ||
1267                      Start->Type == pkgCache::Dep::DpkgBreaks)
1268             {
1269                if(DebugAutoInstall == true)
1270                   std::clog << OutputInDepth(Depth)
1271                             << " Removing: " << Pkg.Name()
1272                             << std::endl;
1273                if (MarkDelete(Pkg,false,Depth + 1, false) == false)
1274                   break;
1275             }
1276          }
1277          continue;
1278       }
1279    }
1280
1281    return Dep.end() == true;
1282 }
1283                                                                         /*}}}*/
1284 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1285 // ---------------------------------------------------------------------
1286 /* The default implementation checks if the installation of an M-A:same
1287    package would lead us into a version-screw and if so forbids it.
1288    dpkg holds are enforced by the private IsModeChangeOk */
1289 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1290                               unsigned long Depth, bool FromUser)
1291 {
1292    return IsInstallOkMultiArchSameVersionSynced(Pkg,AutoInst, Depth, FromUser) &&
1293       IsInstallOkDependenciesSatisfiableByCandidates(Pkg,AutoInst, Depth, FromUser);
1294 }
1295 bool pkgDepCache::IsInstallOkMultiArchSameVersionSynced(PkgIterator const &Pkg,
1296       bool const /*AutoInst*/, unsigned long const Depth, bool const FromUser)
1297 {
1298    if (FromUser == true) // as always: user is always right
1299       return true;
1300
1301    // if we have checked before and it was okay, it will still be okay
1302    if (PkgState[Pkg->ID].Mode == ModeInstall &&
1303          PkgState[Pkg->ID].InstallVer == PkgState[Pkg->ID].CandidateVer)
1304       return true;
1305
1306    // ignore packages with none-M-A:same candidates
1307    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1308    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer() ||
1309          (CandVer->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1310       return true;
1311
1312    GrpIterator const Grp = Pkg.Group();
1313    for (PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1314    {
1315       // not installed or version synced: fine by definition
1316       // (simple string-compare as stuff like '1' == '0:1-0' can't happen here)
1317       if (P->CurrentVer == 0 || strcmp(Pkg.CandVersion(), P.CandVersion()) == 0)
1318          continue;
1319       // packages losing M-A:same can be out-of-sync
1320       VerIterator CV = PkgState[P->ID].CandidateVerIter(*this);
1321       if (unlikely(CV.end() == true) ||
1322             (CV->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1323          continue;
1324
1325       // not downloadable means the package is obsolete, so allow out-of-sync
1326       if (CV.Downloadable() == false)
1327          continue;
1328
1329       PkgState[Pkg->ID].iFlags |= AutoKept;
1330       if (unlikely(DebugMarker == true))
1331          std::clog << OutputInDepth(Depth) << "Ignore MarkInstall of " << Pkg
1332             << " as its M-A:same siblings are not version-synced" << std::endl;
1333       return false;
1334    }
1335
1336    return true;
1337 }
1338 bool pkgDepCache::IsInstallOkDependenciesSatisfiableByCandidates(PkgIterator const &Pkg,
1339       bool const AutoInst, unsigned long const Depth, bool const /*FromUser*/)
1340 {
1341    if (AutoInst == false)
1342       return true;
1343
1344    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1345    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer())
1346       return true;
1347
1348    for (DepIterator Dep = CandVer.DependsList(); Dep.end() != true;)
1349    {
1350       // Grok or groups
1351       DepIterator Start = Dep;
1352       bool Result = true;
1353       unsigned Ors = 0;
1354       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1355       {
1356          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1357
1358          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1359             Result = false;
1360       }
1361
1362       if (Start.IsCritical() == false || Start.IsNegative() == true || Result == false)
1363          continue;
1364
1365       /* If we are in an or group locate the first or that can succeed.
1366          We have already cached this… */
1367       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1368          ++Start;
1369
1370       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer)
1371       {
1372          if (DebugAutoInstall == true)
1373             std::clog << OutputInDepth(Depth) << Start << " can't be satisfied!" << std::endl;
1374
1375          // the dependency is critical, but can't be installed, so discard the candidate
1376          // as the problemresolver will trip over it otherwise trying to install it (#735967)
1377          if (Pkg->CurrentVer != 0)
1378             SetCandidateVersion(Pkg.CurrentVer());
1379          return false;
1380       }
1381    }
1382
1383    return true;
1384 }
1385                                                                         /*}}}*/
1386 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1387 // ---------------------------------------------------------------------
1388 /* */
1389 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1390 {
1391    if (unlikely(Pkg.end() == true))
1392       return;
1393
1394    APT::PackageList pkglist;
1395    if (Pkg->CurrentVer != 0 &&
1396        (Pkg.CurrentVer()-> MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
1397    {
1398       pkgCache::GrpIterator Grp = Pkg.Group();
1399       for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1400       {
1401          if (P->CurrentVer != 0)
1402             pkglist.insert(P);
1403       }
1404    }
1405    else
1406       pkglist.insert(Pkg);
1407
1408    ActionGroup group(*this);
1409
1410    for (APT::PackageList::const_iterator Pkg = pkglist.begin(); Pkg != pkglist.end(); ++Pkg)
1411    {
1412       RemoveSizes(Pkg);
1413       RemoveStates(Pkg);
1414
1415       StateCache &P = PkgState[Pkg->ID];
1416       if (To == true)
1417          P.iFlags |= ReInstall;
1418       else
1419          P.iFlags &= ~ReInstall;
1420
1421       AddStates(Pkg);
1422       AddSizes(Pkg);
1423    }
1424 }
1425                                                                         /*}}}*/
1426 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1427 // ---------------------------------------------------------------------
1428 /* */
1429 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1430 {
1431    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1432    StateCache &P = PkgState[Pkg->ID];
1433
1434    if (P.CandidateVer == TargetVer)
1435       return;
1436
1437    ActionGroup group(*this);
1438
1439    RemoveSizes(Pkg);
1440    RemoveStates(Pkg);
1441
1442    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1443       P.InstallVer = (Version *)TargetVer;
1444    P.CandidateVer = (Version *)TargetVer;
1445    P.Update(Pkg,*this);
1446
1447    AddStates(Pkg);
1448    Update(Pkg);
1449    AddSizes(Pkg);
1450
1451 }
1452                                                                         /*}}}*/
1453 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1454 // ---------------------------------------------------------------------
1455 /* changes the candidate of a package and walks over all its dependencies
1456    to check if it needs to change the candidate of the dependency, too,
1457    to reach a installable versionstate */
1458 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1459                                         std::string const &TargetRel)
1460 {
1461    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1462    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1463 }
1464 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1465                                         std::string const &TargetRel,
1466                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1467 {
1468    ActionGroup group(*this);
1469    SetCandidateVersion(TargetVer);
1470
1471    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1472       return true;
1473
1474    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1475    // save the position of the last element we will not undo - if we have to
1476    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1477
1478    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1479    {
1480       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1481           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1482            IsImportantDep(D) == false))
1483          continue;
1484
1485       // walk over an or-group and check if we need to do anything
1486       // for simpilicity no or-group is handled as a or-group including one dependency
1487       pkgCache::DepIterator Start = D;
1488       bool itsFine = false;
1489       for (bool stillOr = true; stillOr == true; ++Start)
1490       {
1491          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1492          pkgCache::PkgIterator const P = Start.TargetPkg();
1493          // virtual packages can't be a solution
1494          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1495             continue;
1496          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1497          // no versioned dependency - but is it installable?
1498          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1499          {
1500             // Check if one of the providers is installable
1501             if (P->ProvidesList != 0)
1502             {
1503                pkgCache::PrvIterator Prv = P.ProvidesList();
1504                for (; Prv.end() == false; ++Prv)
1505                {
1506                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1507                   if (C.end() == true || C != Prv.OwnerVer() ||
1508                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1509                      continue;
1510                   break;
1511                }
1512                if (Prv.end() == true)
1513                   continue;
1514             }
1515             // no providers, so check if we have an installable candidate version
1516             else if (Cand.end() == true ||
1517                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1518                continue;
1519             itsFine = true;
1520             break;
1521          }
1522          if (Cand.end() == true)
1523             continue;
1524          // check if the current candidate is enough for the versioned dependency - and installable?
1525          if (Start.IsSatisfied(Cand) == true &&
1526              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1527          {
1528             itsFine = true;
1529             break;
1530          }
1531       }
1532
1533       if (itsFine == true) {
1534          // something in the or-group was fine, skip all other members
1535          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1536          continue;
1537       }
1538
1539       // walk again over the or-group and check each if a candidate switch would help
1540       itsFine = false;
1541       for (bool stillOr = true; stillOr == true; ++D)
1542       {
1543          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1544          // changing candidate will not help if the dependency is not versioned
1545          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1546          {
1547             if (stillOr == true)
1548                continue;
1549             break;
1550          }
1551
1552          pkgCache::VerIterator V;
1553          if (TargetRel == "newest")
1554             V = D.TargetPkg().VersionList();
1555          else
1556             V = Match.Find(D.TargetPkg());
1557
1558          // check if the version from this release could satisfy the dependency
1559          if (V.end() == true || D.IsSatisfied(V) == false)
1560          {
1561             if (stillOr == true)
1562                continue;
1563             break;
1564          }
1565
1566          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1567          if (V == oldCand)
1568          {
1569             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1570             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1571                  c != Changed.end(); ++c)
1572             {
1573                if (c->first->ParentPkg != V->ParentPkg)
1574                   continue;
1575                itsFine = true;
1576                break;
1577             }
1578          }
1579
1580          if (itsFine == false)
1581          {
1582             // change the candidate
1583             Changed.push_back(make_pair(V, TargetVer));
1584             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1585             {
1586                if (stillOr == false)
1587                   break;
1588                // undo the candidate changing
1589                SetCandidateVersion(oldCand);
1590                Changed.pop_back();
1591                continue;
1592             }
1593             itsFine = true;
1594          }
1595
1596          // something in the or-group was fine, skip all other members
1597          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1598          break;
1599       }
1600
1601       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1602       {
1603          // undo all changes which aren't lead to a solution
1604          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1605               c != Changed.end(); ++c)
1606             SetCandidateVersion(c->first);
1607          Changed.erase(newChanged, Changed.end());
1608          return false;
1609       }
1610    }
1611    return true;
1612 }
1613                                                                         /*}}}*/
1614 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1615 // ---------------------------------------------------------------------
1616 /* */
1617 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1618 {
1619   StateCache &state = PkgState[Pkg->ID];
1620
1621   ActionGroup group(*this);
1622
1623   if(Auto)
1624     state.Flags |= Flag::Auto;
1625   else
1626     state.Flags &= ~Flag::Auto;
1627 }
1628                                                                         /*}}}*/
1629 // StateCache::Update - Compute the various static display things       /*{{{*/
1630 // ---------------------------------------------------------------------
1631 /* This is called whenever the Candidate version changes. */
1632 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1633 {
1634    // Some info
1635    VerIterator Ver = CandidateVerIter(Cache);
1636
1637    // Use a null string or the version string
1638    if (Ver.end() == true)
1639       CandVersion = "";
1640    else
1641       CandVersion = Ver.VerStr();
1642
1643    // Find the current version
1644    CurVersion = "";
1645    if (Pkg->CurrentVer != 0)
1646       CurVersion = Pkg.CurrentVer().VerStr();
1647
1648    // Strip off the epochs for display
1649    CurVersion = StripEpoch(CurVersion);
1650    CandVersion = StripEpoch(CandVersion);
1651
1652    // Figure out if its up or down or equal
1653    Status = Ver.CompareVer(Pkg.CurrentVer());
1654    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1655      Status = 2;
1656 }
1657                                                                         /*}}}*/
1658 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1659 // ---------------------------------------------------------------------
1660 /* */
1661 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1662 {
1663    if (Ver == 0)
1664       return 0;
1665
1666    // Strip any epoch
1667    for (const char *I = Ver; *I != 0; I++)
1668       if (*I == ':')
1669          return I + 1;
1670    return Ver;
1671 }
1672                                                                         /*}}}*/
1673 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1674 // ---------------------------------------------------------------------
1675 /* The default just returns the highest available version that is not
1676    a source and automatic. */
1677 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1678 {
1679    /* Not source/not automatic versions cannot be a candidate version
1680       unless they are already installed */
1681    VerIterator Last;
1682
1683    for (VerIterator I = Pkg.VersionList(); I.end() == false; ++I)
1684    {
1685       if (Pkg.CurrentVer() == I)
1686          return I;
1687
1688       for (VerFileIterator J = I.FileList(); J.end() == false; ++J)
1689       {
1690          if ((J.File()->Flags & Flag::NotSource) != 0)
1691             continue;
1692
1693          /* Stash the highest version of a not-automatic source, we use it
1694             if there is nothing better */
1695          if ((J.File()->Flags & Flag::NotAutomatic) != 0 ||
1696              (J.File()->Flags & Flag::ButAutomaticUpgrades) != 0)
1697          {
1698             if (Last.end() == true)
1699                Last = I;
1700             continue;
1701          }
1702
1703          return I;
1704       }
1705    }
1706
1707    return Last;
1708 }
1709                                                                         /*}}}*/
1710 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1711 // ---------------------------------------------------------------------
1712 /* */
1713 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
1714 {
1715    if(Dep.IsCritical())
1716       return true;
1717    else if(Dep->Type == pkgCache::Dep::Recommends)
1718    {
1719       if (InstallRecommends)
1720          return true;
1721       // we suport a special mode to only install-recommends for certain
1722       // sections
1723       // FIXME: this is a meant as a temporarly solution until the
1724       //        recommends are cleaned up
1725       const char *sec = Dep.ParentVer().Section();
1726       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1727          return true;
1728    }
1729    else if(Dep->Type == pkgCache::Dep::Suggests)
1730       return InstallSuggests;
1731
1732    return false;
1733 }
1734                                                                         /*}}}*/
1735 // Policy::GetPriority - Get the priority of the package pin            /*{{{*/
1736 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &/*Pkg*/)
1737 { return 0; }
1738 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &/*File*/)
1739 { return 0; }
1740                                                                         /*}}}*/
1741 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1742 {
1743   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1744   if(f->wasConstructedSuccessfully())
1745     return f;
1746   else
1747     {
1748       delete f;
1749       return NULL;
1750     }
1751 }
1752                                                                         /*}}}*/
1753 bool pkgDepCache::MarkFollowsRecommends()
1754 {
1755   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1756 }
1757
1758 bool pkgDepCache::MarkFollowsSuggests()
1759 {
1760   return _config->FindB("APT::AutoRemove::SuggestsImportant", true);
1761 }
1762
1763 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1764 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1765 {
1766    if (_config->Find("APT::Solver", "internal") != "internal")
1767       return true;
1768
1769    bool follow_recommends;
1770    bool follow_suggests;
1771    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1772
1773    // init the states
1774    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1775    {
1776       PkgState[p->ID].Marked  = false;
1777       PkgState[p->ID].Garbage = false;
1778
1779       // debug output
1780       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1781          std::clog << "AutoDep: " << p.FullName() << std::endl;
1782    }
1783
1784    // init vars
1785    follow_recommends = MarkFollowsRecommends();
1786    follow_suggests   = MarkFollowsSuggests();
1787
1788    // do the mark part, this is the core bit of the algorithm
1789    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1790    {
1791       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1792           (p->Flags & Flag::Essential) ||
1793           (p->Flags & Flag::Important) ||
1794           userFunc.InRootSet(p) ||
1795           // be nice even then a required package violates the policy (#583517)
1796           // and do the full mark process also for required packages
1797           (p.CurrentVer().end() != true &&
1798            p.CurrentVer()->Priority == pkgCache::State::Required) ||
1799           // packages which can't be changed (like holds) can't be garbage
1800           (IsModeChangeOk(ModeGarbage, p, 0, false) == false))
1801       {
1802          // the package is installed (and set to keep)
1803          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1804             MarkPackage(p, p.CurrentVer(),
1805                         follow_recommends, follow_suggests);
1806          // the package is to be installed
1807          else if(PkgState[p->ID].Install())
1808             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1809                         follow_recommends, follow_suggests);
1810       }
1811    }
1812
1813    return true;
1814 }
1815                                                                         /*}}}*/
1816 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1817 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1818                               const pkgCache::VerIterator &ver,
1819                               bool const &follow_recommends,
1820                               bool const &follow_suggests)
1821 {
1822    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1823
1824    // if we are marked already we are done
1825    if(state.Marked)
1826       return;
1827
1828    VerIterator const currver = pkg.CurrentVer();
1829    VerIterator const instver = state.InstVerIter(*this);
1830
1831 #if 0
1832    VerIterator const candver = state.CandidateVerIter(*this);
1833
1834    // If a package was garbage-collected but is now being marked, we
1835    // should re-select it
1836    // For cases when a pkg is set to upgrade and this trigger the
1837    // removal of a no-longer used dependency.  if the pkg is set to
1838    // keep again later it will result in broken deps
1839    if(state.Delete() && state.RemoveReason = Unused)
1840    {
1841       if(ver==candver)
1842          mark_install(pkg, false, false, NULL);
1843       else if(ver==pkg.CurrentVer())
1844          MarkKeep(pkg, false, false);
1845
1846       instver=state.InstVerIter(*this);
1847    }
1848 #endif
1849
1850    // For packages that are not going to be removed, ignore versions
1851    // other than the InstVer.  For packages that are going to be
1852    // removed, ignore versions other than the current version.
1853    if(!(ver == instver && !instver.end()) &&
1854       !(ver == currver && instver.end() && !ver.end()))
1855       return;
1856
1857    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1858
1859    if(debug_autoremove)
1860      {
1861        std::clog << "Marking: " << pkg.FullName();
1862        if(!ver.end())
1863          std::clog << " " << ver.VerStr();
1864        if(!currver.end())
1865          std::clog << ", Curr=" << currver.VerStr();
1866        if(!instver.end())
1867          std::clog << ", Inst=" << instver.VerStr();
1868        std::clog << std::endl;
1869      }
1870
1871    state.Marked=true;
1872
1873    if(ver.end() == true)
1874       return;
1875
1876      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1877      {
1878         if(d->Type == Dep::Depends ||
1879            d->Type == Dep::PreDepends ||
1880            (follow_recommends &&
1881             d->Type == Dep::Recommends) ||
1882            (follow_suggests &&
1883             d->Type == Dep::Suggests))
1884         {
1885            // Try all versions of this package.
1886            for(VerIterator V = d.TargetPkg().VersionList();
1887                !V.end(); ++V)
1888            {
1889               if(d.IsSatisfied(V))
1890               {
1891                 if(debug_autoremove)
1892                   {
1893                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1894                               << " " << d.ParentVer().VerStr() << " "
1895                               << d.DepType() << " " << d.TargetPkg().FullName();
1896                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1897                       {
1898                         std::clog << " (" << d.CompType() << " "
1899                                   << d.TargetVer() << ")";
1900                       }
1901                     std::clog << std::endl;
1902                   }
1903                  MarkPackage(V.ParentPkg(), V,
1904                              follow_recommends, follow_suggests);
1905               }
1906            }
1907            // Now try virtual packages
1908            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1909                !prv.end(); ++prv)
1910            {
1911               if(d.IsSatisfied(prv))
1912               {
1913                 if(debug_autoremove)
1914                   {
1915                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1916                               << d.ParentVer().VerStr() << " "
1917                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1918                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1919                       {
1920                         std::clog << " (" << d.CompType() << " "
1921                                   << d.TargetVer() << ")";
1922                       }
1923                     std::clog << ", provided by "
1924                               << prv.OwnerPkg().FullName() << " "
1925                               << prv.OwnerVer().VerStr()
1926                               << std::endl;
1927                   }
1928
1929                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1930                              follow_recommends, follow_suggests);
1931               }
1932            }
1933         }
1934      }
1935 }
1936                                                                         /*}}}*/
1937 bool pkgDepCache::Sweep()                                               /*{{{*/
1938 {
1939    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1940
1941    // do the sweep
1942    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1943    {
1944      StateCache &state=PkgState[p->ID];
1945
1946      // skip required packages
1947      if (!p.CurrentVer().end() &&
1948          (p.CurrentVer()->Priority == pkgCache::State::Required))
1949         continue;
1950
1951      // if it is not marked and it is installed, it's garbage
1952      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1953      {
1954         state.Garbage=true;
1955         if(debug_autoremove)
1956            std::clog << "Garbage: " << p.FullName() << std::endl;
1957      }
1958   }
1959
1960    return true;
1961 }
1962                                                                         /*}}}*/