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    iUsrSize(0), iDownloadSize(0), iInstCount(0), iDelCount(0), iKeepCount(0),
 100    iBrokenCount(0), iPolicyBrokenCount(0), iBadCount(0)
 101 {
 102    DebugMarker = _config->FindB("Debug::pkgDepCache::Marker", false);
 103    DebugAutoInstall = _config->FindB("Debug::pkgDepCache::AutoInstall", false);
 104    delLocalPolicy = 0;
 105    LocalPolicy = Plcy;
 106    if (LocalPolicy == 0)
 107       delLocalPolicy = LocalPolicy = new Policy;
 108 }
 109                                                                         /*}}}*/
 110 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
 111 // ---------------------------------------------------------------------
 112 /* */
 113 pkgDepCache::~pkgDepCache()
 114 {
 115    delete [] PkgState;
 116    delete [] DepState;
 117    delete delLocalPolicy;
 118 }
 119                                                                         /*}}}*/
 120 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
 121 // ---------------------------------------------------------------------
 122 /* This allocats the extension buffers and initializes them. */
 123 bool pkgDepCache::Init(OpProgress *Prog)
 124 {
 125    // Suppress mark updates during this operation (just in case) and
 126    // run a mark operation when Init terminates.
 127    ActionGroup actions(*this);
 128
 129    delete [] PkgState;
 130    delete [] DepState;
 131    PkgState = new StateCache[Head().PackageCount];
 132    DepState = new unsigned char[Head().DependsCount];
 133    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
 134    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
 135
 136    if (Prog != 0)
 137    {
 138       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
 139                             _("Building dependency tree"));
 140       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 141    }
 142
 143    /* Set the current state of everything. In this state all of the
 144       packages are kept exactly as is. See AllUpgrade */
 145    int Done = 0;
 146    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 147    {
 148       if (Prog != 0 && Done%20 == 0)
 149          Prog->Progress(Done);
 150
 151       // Find the proper cache slot
 152       StateCache &State = PkgState[I->ID];
 153       State.iFlags = 0;
 154
 155       // Figure out the install version
 156       State.CandidateVer = GetCandidateVer(I);
 157       State.InstallVer = I.CurrentVer();
 158       State.Mode = ModeKeep;
 159
 160       State.Update(I,*this);
 161    }
 162
 163    if (Prog != 0)
 164    {
 165
 166       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
 167                             Head().PackageCount,
 168                             _("Building dependency tree"));
 169       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
 170    }
 171
 172    Update(Prog);
 173
 174    if(Prog != 0)
 175       Prog->Done();
 176
 177    return true;
 178 }
 179                                                                         /*}}}*/
 180 bool pkgDepCache::readStateFile(OpProgress *Prog)                       /*{{{*/
 181 {
 182    FileFd state_file;
 183    string const state = _config->FindFile("Dir::State::extended_states");
 184    if(RealFileExists(state)) {
 185       state_file.Open(state, FileFd::ReadOnly);
 186       off_t const file_size = state_file.Size();
 187       if(Prog != NULL)
 188          Prog->OverallProgress(0, file_size, 1,
 189                                _("Reading state information"));
 190
 191       pkgTagFile tagfile(&state_file);
 192       pkgTagSection section;
 193       off_t amt = 0;
 194       bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 195       while(tagfile.Step(section)) {
 196          string const pkgname = section.FindS("Package");
 197          string pkgarch = section.FindS("Architecture");
 198          if (pkgarch.empty() == true)
 199             pkgarch = "any";
 200          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 201          // Silently ignore unknown packages and packages with no actual version.
 202          if(pkg.end() == true || pkg->VersionList == 0)
 203             continue;
 204
 205          short const reason = section.FindI("Auto-Installed", 0);
 206          if(reason > 0)
 207          {
 208             PkgState[pkg->ID].Flags |= Flag::Auto;
 209             if (unlikely(debug_autoremove))
 210                std::clog << "Auto-Installed : " << pkg.FullName() << std::endl;
 211             if (pkgarch == "any")
 212             {
 213                pkgCache::GrpIterator G = pkg.Group();
 214                for (pkg = G.NextPkg(pkg); pkg.end() != true; pkg = G.NextPkg(pkg))
 215                   if (pkg->VersionList != 0)
 216                      PkgState[pkg->ID].Flags |= Flag::Auto;
 217             }
 218          }
 219          amt += section.size();
 220          if(Prog != NULL)
 221             Prog->OverallProgress(amt, file_size, 1,
 222                                   _("Reading state information"));
 223       }
 224       if(Prog != NULL)
 225          Prog->OverallProgress(file_size, file_size, 1,
 226                                _("Reading state information"));
 227    }
 228
 229    return true;
 230 }
 231                                                                         /*}}}*/
 232 bool pkgDepCache::writeStateFile(OpProgress * /*prog*/, bool InstalledOnly)     /*{{{*/
 233 {
 234    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 235
 236    if(debug_autoremove)
 237       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 238
 239    FileFd StateFile;
 240    string const state = _config->FindFile("Dir::State::extended_states");
 241    if (CreateAPTDirectoryIfNeeded(_config->FindDir("Dir::State"), flNotFile(state)) == false)
 242       return false;
 243
 244    // if it does not exist, create a empty one
 245    if(!RealFileExists(state))
 246    {
 247       StateFile.Open(state, FileFd::WriteAtomic);
 248       StateFile.Close();
 249    }
 250
 251    // open it
 252    if(!StateFile.Open(state, FileFd::ReadOnly))
 253       return _error->Error(_("Failed to open StateFile %s"),
 254                            state.c_str());
 255
 256    FileFd OutFile(state, FileFd::ReadWrite | FileFd::Atomic);
 257    if (OutFile.IsOpen() == false || OutFile.Failed() == true)
 258       return _error->Error(_("Failed to write temporary StateFile %s"), state.c_str());
 259
 260    // first merge with the existing sections
 261    pkgTagFile tagfile(&StateFile);
 262    pkgTagSection section;
 263    std::set<string> pkgs_seen;
 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
 294          std::vector<pkgTagSection::Tag> rewrite;
 295          rewrite.push_back(pkgTagSection::Tag::Rewrite("Architecture", pkg.Arch()));
 296          rewrite.push_back(pkgTagSection::Tag::Rewrite("Auto-Installed", newAuto ? "1" : "0"));
 297          section.Write(OutFile, NULL, rewrite);
 298          if (OutFile.Write("\n", 1) == false)
 299             return false;
 300          pkgs_seen.insert(pkg.FullName());
 301    }
 302
 303    // then write the ones we have not seen yet
 304    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end(); ++pkg) {
 305       StateCache const &P = PkgState[pkg->ID];
 306       if(P.Flags & Flag::Auto) {
 307          if (pkgs_seen.find(pkg.FullName()) != pkgs_seen.end()) {
 308             if(debug_autoremove)
 309                std::clog << "Skipping already written " << pkg.FullName() << std::endl;
 310             continue;
 311          }
 312          // skip not installed ones if requested
 313          if (InstalledOnly && (
 314              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 315              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 316             continue;
 317          const char* const pkgarch = pkg.Arch();
 318          if (strcmp(pkgarch, "all") == 0)
 319             continue;
 320          if(debug_autoremove)
 321             std::clog << "Writing new AutoInstall: " << pkg.FullName() << std::endl;
 322          std::string stanza = "Package: ";
 323          stanza.append(pkg.Name())
 324               .append("\nArchitecture: ").append(pkgarch)
 325               .append("\nAuto-Installed: 1\n\n");
 326          if (OutFile.Write(stanza.c_str(), stanza.length()) == false)
 327             return false;
 328       }
 329    }
 330    if (OutFile.Close() == false)
 331       return false;
 332    chmod(state.c_str(), 0644);
 333    return true;
 334 }
 335                                                                         /*}}}*/
 336 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 337 // ---------------------------------------------------------------------
 338 /* This first checks the dependency against the main target package and
 339    then walks along the package provides list and checks if each provides
 340    will be installed then checks the provides against the dep. Res will be
 341    set to the package which was used to satisfy the dep. */
 342 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 343 {
 344    Res = Dep.TargetPkg();
 345
 346    /* Check simple depends. A depends -should- never self match but
 347       we allow it anyhow because dpkg does. Technically it is a packaging
 348       bug. Conflicts may never self match */
 349    if (Dep.IsIgnorable(Res) == false)
 350    {
 351       PkgIterator Pkg = Dep.TargetPkg();
 352       // Check the base package
 353       if (Type == NowVersion && Pkg->CurrentVer != 0)
 354          if (Dep.IsSatisfied(Pkg.CurrentVer()) == true)
 355             return true;
 356
 357       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 358          if (Dep.IsSatisfied(PkgState[Pkg->ID].InstVerIter(*this)) == true)
 359             return true;
 360
 361       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 362          if (Dep.IsSatisfied(PkgState[Pkg->ID].CandidateVerIter(*this)) == true)
 363             return true;
 364    }
 365
 366    if (Dep->Type == Dep::Obsoletes)
 367       return false;
 368
 369    // Check the providing packages
 370    PrvIterator P = Dep.TargetPkg().ProvidesList();
 371    for (; P.end() != true; ++P)
 372    {
 373       if (Dep.IsIgnorable(P) == true)
 374          continue;
 375
 376       // Check if the provides is a hit
 377       if (Type == NowVersion)
 378       {
 379          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 380             continue;
 381       }
 382
 383       if (Type == InstallVersion)
 384       {
 385          StateCache &State = PkgState[P.OwnerPkg()->ID];
 386          if (State.InstallVer != (Version *)P.OwnerVer())
 387             continue;
 388       }
 389
 390       if (Type == CandidateVersion)
 391       {
 392          StateCache &State = PkgState[P.OwnerPkg()->ID];
 393          if (State.CandidateVer != (Version *)P.OwnerVer())
 394             continue;
 395       }
 396
 397       // Compare the versions.
 398       if (Dep.IsSatisfied(P) == true)
 399       {
 400          Res = P.OwnerPkg();
 401          return true;
 402       }
 403    }
 404
 405    return false;
 406 }
 407                                                                         /*}}}*/
 408 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 409 // ---------------------------------------------------------------------
 410 /* Call with Inverse = true to preform the inverse opration */
 411 void pkgDepCache::AddSizes(const PkgIterator &Pkg, bool const Inverse)
 412 {
 413    StateCache &P = PkgState[Pkg->ID];
 414
 415    if (Pkg->VersionList == 0)
 416       return;
 417
 418    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 419        P.Keep() == true)
 420       return;
 421
 422    // Compute the size data
 423    if (P.NewInstall() == true)
 424    {
 425       if (Inverse == false) {
 426          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 427          iDownloadSize += P.InstVerIter(*this)->Size;
 428       } else {
 429          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 430          iDownloadSize -= P.InstVerIter(*this)->Size;
 431       }
 432       return;
 433    }
 434
 435    // Upgrading
 436    if (Pkg->CurrentVer != 0 &&
 437        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 438         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 439    {
 440       if (Inverse == false) {
 441          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 442          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 443          iDownloadSize += P.InstVerIter(*this)->Size;
 444       } else {
 445          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 446          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 447          iDownloadSize -= P.InstVerIter(*this)->Size;
 448       }
 449       return;
 450    }
 451
 452    // Reinstall
 453    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 454        P.Delete() == false)
 455    {
 456       if (Inverse == false)
 457          iDownloadSize += P.InstVerIter(*this)->Size;
 458       else
 459          iDownloadSize -= P.InstVerIter(*this)->Size;
 460       return;
 461    }
 462
 463    // Removing
 464    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 465    {
 466       if (Inverse == false)
 467          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 468       else
 469          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 470       return;
 471    }
 472 }
 473                                                                         /*}}}*/
 474 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 475 // ---------------------------------------------------------------------
 476 /* This routine is tricky to use, you must make sure that it is never
 477    called twice for the same package. This means the Remove/Add section
 478    should be as short as possible and not encompass any code that will
 479    calld Remove/Add itself. Remember, dependencies can be circular so
 480    while processing a dep for Pkg it is possible that Add/Remove
 481    will be called on Pkg */
 482 void pkgDepCache::AddStates(const PkgIterator &Pkg, bool const Invert)
 483 {
 484    signed char const Add = (Invert == false) ? 1 : -1;
 485    StateCache &State = PkgState[Pkg->ID];
 486
 487    // The Package is broken (either minimal dep or policy dep)
 488    if ((State.DepState & DepInstMin) != DepInstMin)
 489       iBrokenCount += Add;
 490    if ((State.DepState & DepInstPolicy) != DepInstPolicy)
 491       iPolicyBrokenCount += Add;
 492
 493    // Bad state
 494    if (Pkg.State() != PkgIterator::NeedsNothing)
 495       iBadCount += Add;
 496
 497    // Not installed
 498    if (Pkg->CurrentVer == 0)
 499    {
 500       if (State.Mode == ModeDelete &&
 501           (State.iFlags & Purge) == Purge && Pkg.Purge() == false)
 502          iDelCount += Add;
 503
 504       if (State.Mode == ModeInstall)
 505          iInstCount += Add;
 506       return;
 507    }
 508
 509    // Installed, no upgrade
 510    if (State.Status == 0)
 511    {
 512       if (State.Mode == ModeDelete)
 513          iDelCount += Add;
 514       else
 515          if ((State.iFlags & ReInstall) == ReInstall)
 516             iInstCount += Add;
 517
 518       return;
 519    }
 520
 521    // Alll 3 are possible
 522    if (State.Mode == ModeDelete)
 523       iDelCount += Add;
 524    if (State.Mode == ModeKeep)
 525       iKeepCount += Add;
 526    if (State.Mode == ModeInstall)
 527       iInstCount += Add;
 528 }
 529                                                                         /*}}}*/
 530 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 531 // ---------------------------------------------------------------------
 532 /* The or group results are stored in the last item of the or group. This
 533    allows easy detection of the state of a whole or'd group. */
 534 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 535 {
 536    unsigned char Group = 0;
 537
 538    for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 539    {
 540       // Build the dependency state.
 541       unsigned char &State = DepState[D->ID];
 542
 543       /* Invert for Conflicts. We have to do this twice to get the
 544          right sense for a conflicts group */
 545       if (D.IsNegative() == true)
 546          State = ~State;
 547
 548       // Add to the group if we are within an or..
 549       State &= 0x7;
 550       Group |= State;
 551       State |= Group << 3;
 552       if ((D->CompareOp & Dep::Or) != Dep::Or)
 553          Group = 0;
 554
 555       // Invert for Conflicts
 556       if (D.IsNegative() == true)
 557          State = ~State;
 558    }
 559 }
 560                                                                         /*}}}*/
 561 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 562 // ---------------------------------------------------------------------
 563 /* This is used to run over a dependency list and determine the dep
 564    state of the list, filtering it through both a Min check and a Policy
 565    check. The return result will have SetMin/SetPolicy low if a check
 566    fails. It uses the DepState cache for it's computations. */
 567 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 568                                        unsigned char SetMin,
 569                                        unsigned char SetPolicy)
 570 {
 571    unsigned char Dep = 0xFF;
 572
 573    while (D.end() != true)
 574    {
 575       // Compute a single dependency element (glob or)
 576       DepIterator Start = D;
 577       unsigned char State = 0;
 578       for (bool LastOR = true; D.end() == false && LastOR == true; ++D)
 579       {
 580          State |= DepState[D->ID];
 581          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 582       }
 583
 584       // Minimum deps that must be satisfied to have a working package
 585       if (Start.IsCritical() == true)
 586          if ((State & Check) != Check)
 587             Dep &= ~SetMin;
 588
 589       // Policy deps that must be satisfied to install the package
 590       if (IsImportantDep(Start) == true &&
 591           (State & Check) != Check)
 592          Dep &= ~SetPolicy;
 593    }
 594
 595    return Dep;
 596 }
 597                                                                         /*}}}*/
 598 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 599 // ---------------------------------------------------------------------
 600 /* This is the main dependency computation bit. It computes the 3 main
 601    results for a dependencys, Now, Install and Candidate. Callers must
 602    invert the result if dealing with conflicts. */
 603 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 604 {
 605    unsigned char State = 0;
 606
 607    if (CheckDep(D,NowVersion) == true)
 608       State |= DepNow;
 609    if (CheckDep(D,InstallVersion) == true)
 610       State |= DepInstall;
 611    if (CheckDep(D,CandidateVersion) == true)
 612       State |= DepCVer;
 613
 614    return State;
 615 }
 616                                                                         /*}}}*/
 617 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 618 // ---------------------------------------------------------------------
 619 /* This determines the combined dependency representation of a package
 620    for its two states now and install. This is done by using the pre-generated
 621    dependency information. */
 622 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 623 {
 624    // Empty deps are always true
 625    StateCache &State = PkgState[Pkg->ID];
 626    State.DepState = 0xFF;
 627
 628    // Check the Current state
 629    if (Pkg->CurrentVer != 0)
 630    {
 631       DepIterator D = Pkg.CurrentVer().DependsList();
 632       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 633    }
 634
 635    /* Check the candidate state. We do not compare against the whole as
 636       a candidate state but check the candidate version against the
 637       install states */
 638    if (State.CandidateVer != 0)
 639    {
 640       DepIterator D = State.CandidateVerIter(*this).DependsList();
 641       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 642    }
 643
 644    // Check target state which can only be current or installed
 645    if (State.InstallVer != 0)
 646    {
 647       DepIterator D = State.InstVerIter(*this).DependsList();
 648       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 649    }
 650 }
 651                                                                         /*}}}*/
 652 // DepCache::Update - Figure out all the state information              /*{{{*/
 653 // ---------------------------------------------------------------------
 654 /* This will figure out the state of all the packages and all the
 655    dependencies based on the current policy. */
 656 void pkgDepCache::Update(OpProgress *Prog)
 657 {
 658    iUsrSize = 0;
 659    iDownloadSize = 0;
 660    iInstCount = 0;
 661    iDelCount = 0;
 662    iKeepCount = 0;
 663    iBrokenCount = 0;
 664    iPolicyBrokenCount = 0;
 665    iBadCount = 0;
 666
 667    // Perform the depends pass
 668    int Done = 0;
 669    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 670    {
 671       if (Prog != 0 && Done%20 == 0)
 672          Prog->Progress(Done);
 673       for (VerIterator V = I.VersionList(); V.end() != true; ++V)
 674       {
 675          unsigned char Group = 0;
 676
 677          for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 678          {
 679             // Build the dependency state.
 680             unsigned char &State = DepState[D->ID];
 681             State = DependencyState(D);
 682
 683             // Add to the group if we are within an or..
 684             Group |= State;
 685             State |= Group << 3;
 686             if ((D->CompareOp & Dep::Or) != Dep::Or)
 687                Group = 0;
 688
 689             // Invert for Conflicts
 690             if (D.IsNegative() == true)
 691                State = ~State;
 692          }
 693       }
 694
 695       // Compute the package dependency state and size additions
 696       AddSizes(I);
 697       UpdateVerState(I);
 698       AddStates(I);
 699    }
 700
 701    if (Prog != 0)
 702       Prog->Progress(Done);
 703
 704    readStateFile(Prog);
 705 }
 706                                                                         /*}}}*/
 707 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 708 // ---------------------------------------------------------------------
 709 /* This is a helper for update that only does the dep portion of the scan.
 710    It is mainly meant to scan reverse dependencies. */
 711 void pkgDepCache::Update(DepIterator D)
 712 {
 713    // Update the reverse deps
 714    for (;D.end() != true; ++D)
 715    {
 716       unsigned char &State = DepState[D->ID];
 717       State = DependencyState(D);
 718
 719       // Invert for Conflicts
 720       if (D.IsNegative() == true)
 721          State = ~State;
 722
 723       RemoveStates(D.ParentPkg());
 724       BuildGroupOrs(D.ParentVer());
 725       UpdateVerState(D.ParentPkg());
 726       AddStates(D.ParentPkg());
 727    }
 728 }
 729                                                                         /*}}}*/
 730 // DepCache::Update - Update the related deps of a package              /*{{{*/
 731 // ---------------------------------------------------------------------
 732 /* This is called whenever the state of a package changes. It updates
 733    all cached dependencies related to this package. */
 734 void pkgDepCache::Update(PkgIterator const &Pkg)
 735 {
 736    // Recompute the dep of the package
 737    RemoveStates(Pkg);
 738    UpdateVerState(Pkg);
 739    AddStates(Pkg);
 740
 741    // Update the reverse deps
 742    Update(Pkg.RevDependsList());
 743
 744    // Update the provides map for the current ver
 745    if (Pkg->CurrentVer != 0)
 746       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 747            P.end() != true; ++P)
 748          Update(P.ParentPkg().RevDependsList());
 749
 750    // Update the provides map for the candidate ver
 751    if (PkgState[Pkg->ID].CandidateVer != 0)
 752       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 753            P.end() != true; ++P)
 754          Update(P.ParentPkg().RevDependsList());
 755 }
 756                                                                         /*}}}*/
 757 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 758 // ---------------------------------------------------------------------
 759 /* */
 760 bool pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 761                            unsigned long Depth)
 762 {
 763    if (IsModeChangeOk(ModeKeep, Pkg, Depth, FromUser) == false)
 764       return false;
 765
 766    /* Reject an attempt to keep a non-source broken installed package, those
 767       must be upgraded */
 768    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 769        Pkg.CurrentVer().Downloadable() == false)
 770       return false;
 771
 772    /* We changed the soft state all the time so the UI is a bit nicer
 773       to use */
 774    StateCache &P = PkgState[Pkg->ID];
 775
 776    // Check that it is not already kept
 777    if (P.Mode == ModeKeep)
 778       return true;
 779
 780    if (Soft == true)
 781       P.iFlags |= AutoKept;
 782    else
 783       P.iFlags &= ~AutoKept;
 784
 785    ActionGroup group(*this);
 786
 787 #if 0 // reseting the autoflag here means we lose the
 788       // auto-mark information if a user selects a package for removal
 789       // but changes  his mind then and sets it for keep again
 790       // - this makes sense as default when all Garbage dependencies
 791       //   are automatically marked for removal (as aptitude does).
 792       //   setting a package for keep then makes it no longer autoinstalled
 793       //   for all other use-case this action is rather surprising
 794    if(FromUser && !P.Marked)
 795      P.Flags &= ~Flag::Auto;
 796 #endif
 797
 798    if (DebugMarker == true)
 799       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 800
 801    RemoveSizes(Pkg);
 802    RemoveStates(Pkg);
 803
 804    P.Mode = ModeKeep;
 805    if (Pkg->CurrentVer == 0)
 806       P.InstallVer = 0;
 807    else
 808       P.InstallVer = Pkg.CurrentVer();
 809
 810    AddStates(Pkg);
 811    Update(Pkg);
 812    AddSizes(Pkg);
 813
 814    return true;
 815 }
 816                                                                         /*}}}*/
 817 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 818 // ---------------------------------------------------------------------
 819 /* */
 820 bool pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 821                              unsigned long Depth, bool FromUser)
 822 {
 823    if (IsModeChangeOk(ModeDelete, Pkg, Depth, FromUser) == false)
 824       return false;
 825
 826    StateCache &P = PkgState[Pkg->ID];
 827
 828    // Check that it is not already marked for delete
 829    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 830        (Pkg.Purge() == true || rPurge == false))
 831       return true;
 832
 833    // check if we are allowed to remove the package
 834    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
 835       return false;
 836
 837    P.iFlags &= ~(AutoKept | Purge);
 838    if (rPurge == true)
 839       P.iFlags |= Purge;
 840
 841    ActionGroup group(*this);
 842
 843    if (DebugMarker == true)
 844       std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << Pkg << " FU=" << FromUser << std::endl;
 845
 846    RemoveSizes(Pkg);
 847    RemoveStates(Pkg);
 848
 849    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 850       P.Mode = ModeKeep;
 851    else
 852       P.Mode = ModeDelete;
 853    P.InstallVer = 0;
 854
 855    AddStates(Pkg);
 856    Update(Pkg);
 857    AddSizes(Pkg);
 858
 859    return true;
 860 }
 861                                                                         /*}}}*/
 862 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 863 // ---------------------------------------------------------------------
 864 /* The default implementation tries to prevent deletion of install requests.
 865    dpkg holds are enforced by the private IsModeChangeOk */
 866 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 867                               unsigned long Depth, bool FromUser)
 868 {
 869    return IsDeleteOkProtectInstallRequests(Pkg, rPurge, Depth, FromUser);
 870 }
 871 bool pkgDepCache::IsDeleteOkProtectInstallRequests(PkgIterator const &Pkg,
 872       bool const /*rPurge*/, unsigned long const Depth, bool const FromUser)
 873 {
 874    if (FromUser == false && Pkg->CurrentVer == 0)
 875    {
 876       StateCache &P = PkgState[Pkg->ID];
 877       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
 878       {
 879          if (DebugMarker == true)
 880             std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << Pkg << std::endl;
 881          return false;
 882       }
 883    }
 884    return true;
 885 }
 886                                                                         /*}}}*/
 887 // DepCache::IsModeChangeOk - check if it is ok to change the mode      /*{{{*/
 888 // ---------------------------------------------------------------------
 889 /* this is used by all Mark methods on the very first line to check sanity
 890    and prevents mode changes for packages on hold for example.
 891    If you want to check Mode specific stuff you can use the virtual public
 892    Is<Mode>Ok methods instead */
 893 static char const* PrintMode(char const mode)
 894 {
 895          switch (mode)
 896          {
 897          case pkgDepCache::ModeInstall: return "Install";
 898          case pkgDepCache::ModeKeep: return "Keep";
 899          case pkgDepCache::ModeDelete: return "Delete";
 900          case pkgDepCache::ModeGarbage: return "Garbage";
 901          default: return "UNKNOWN";
 902          }
 903 }
 904 bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
 905                                  unsigned long const Depth, bool const FromUser)
 906 {
 907    // we are not trying to hard…
 908    if (unlikely(Depth > 100))
 909       return false;
 910
 911    // general sanity
 912    if (unlikely(Pkg.end() == true || Pkg->VersionList == 0))
 913       return false;
 914
 915    // the user is always right
 916    if (FromUser == true)
 917       return true;
 918
 919    StateCache &P = PkgState[Pkg->ID];
 920    // not changing the mode is obviously also fine as we might want to call
 921    // e.g. MarkInstall multiple times with different arguments for the same package
 922    if (P.Mode == mode)
 923       return true;
 924
 925    // if previous state was set by user only user can reset it
 926    if ((P.iFlags & Protected) == Protected)
 927    {
 928       if (unlikely(DebugMarker == true))
 929          std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
 930                    << " of " << Pkg << " as its mode (" << PrintMode(P.Mode)
 931                    << ") is protected" << std::endl;
 932       return false;
 933    }
 934    // enforce dpkg holds
 935    else if (mode != ModeKeep && Pkg->SelectedState == pkgCache::State::Hold &&
 936             _config->FindB("APT::Ignore-Hold",false) == false)
 937    {
 938       if (unlikely(DebugMarker == true))
 939          std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
 940                    << " of " << Pkg << std::endl;
 941       return false;
 942    }
 943
 944    return true;
 945 }
 946                                                                         /*}}}*/
 947 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 948 // ---------------------------------------------------------------------
 949 /* */
 950 struct CompareProviders {
 951    pkgCache::PkgIterator const Pkg;
 952    explicit CompareProviders(pkgCache::DepIterator const &Dep) : Pkg(Dep.TargetPkg()) {};
 953    //bool operator() (APT::VersionList::iterator const &AV, APT::VersionList::iterator const &BV)
 954    bool operator() (pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
 955    {
 956       pkgCache::PkgIterator const A = AV.ParentPkg();
 957       pkgCache::PkgIterator const B = BV.ParentPkg();
 958       // Prefer MA:same packages if other architectures for it are installed
 959       if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same ||
 960           (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 961       {
 962          bool instA = false;
 963          if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 964          {
 965             pkgCache::GrpIterator Grp = A.Group();
 966             for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
 967                if (P->CurrentVer != 0)
 968                {
 969                   instA = true;
 970                   break;
 971                }
 972          }
 973          bool instB = false;
 974          if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 975          {
 976             pkgCache::GrpIterator Grp = B.Group();
 977             for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
 978             {
 979                if (P->CurrentVer != 0)
 980                {
 981                   instB = true;
 982                   break;
 983                }
 984             }
 985          }
 986          if (instA != instB)
 987             return instA == false;
 988       }
 989       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
 990       if (A->Group != B->Group)
 991       {
 992          if (A->Group == Pkg->Group && B->Group != Pkg->Group)
 993             return false;
 994          else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
 995             return true;
 996       }
 997       // we like essentials
 998       if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
 999       {
1000          if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1001             return false;
1002          else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1003             return true;
1004       }
1005       if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
1006       {
1007          if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1008             return false;
1009          else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1010             return true;
1011       }
1012       // prefer native architecture
1013       if (strcmp(A.Arch(), B.Arch()) != 0)
1014       {
1015          if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
1016             return false;
1017          else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
1018             return true;
1019          std::vector<std::string> archs = APT::Configuration::getArchitectures();
1020          for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
1021             if (*a == A.Arch())
1022                return false;
1023             else if (*a == B.Arch())
1024                return true;
1025       }
1026       // higher priority seems like a good idea
1027       if (AV->Priority != BV->Priority)
1028          return AV->Priority > BV->Priority;
1029       // unable to decide…
1030       return A->ID < B->ID;
1031    }
1032 };
1033 bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
1034                               unsigned long Depth, bool FromUser,
1035                               bool ForceImportantDeps)
1036 {
1037    if (IsModeChangeOk(ModeInstall, Pkg, Depth, FromUser) == false)
1038       return false;
1039
1040    StateCache &P = PkgState[Pkg->ID];
1041
1042    // See if there is even any possible instalation candidate
1043    if (P.CandidateVer == 0)
1044       return false;
1045
1046    /* Check that it is not already marked for install and that it can be
1047       installed */
1048    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1049        (P.Mode == ModeInstall ||
1050         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1051    {
1052       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1053          return MarkKeep(Pkg, false, FromUser, Depth+1);
1054       return true;
1055    }
1056
1057    // check if we are allowed to install the package
1058    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1059       return false;
1060
1061    ActionGroup group(*this);
1062    P.iFlags &= ~AutoKept;
1063
1064    /* Target the candidate version and remove the autoflag. We reset the
1065       autoflag below if this was called recursively. Otherwise the user
1066       should have the ability to de-auto a package by changing its state */
1067    RemoveSizes(Pkg);
1068    RemoveStates(Pkg);
1069
1070    P.Mode = ModeInstall;
1071    P.InstallVer = P.CandidateVer;
1072
1073    if(FromUser)
1074      {
1075        // Set it to manual if it's a new install or already installed,
1076        // but only if its not marked by the autoremover (aptitude depend on this behavior)
1077        // or if we do automatic installation (aptitude never does it)
1078        if(P.Status == 2 || (Pkg->CurrentVer != 0 && (AutoInst == true || P.Marked == false)))
1079          P.Flags &= ~Flag::Auto;
1080      }
1081    else
1082      {
1083        // Set it to auto if this is a new install.
1084        if(P.Status == 2)
1085          P.Flags |= Flag::Auto;
1086      }
1087    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1088       P.Mode = ModeKeep;
1089
1090    AddStates(Pkg);
1091    Update(Pkg);
1092    AddSizes(Pkg);
1093
1094    if (AutoInst == false || _config->Find("APT::Solver", "internal") != "internal")
1095       return true;
1096
1097    if (DebugMarker == true)
1098       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1099
1100    DepIterator Dep = P.InstVerIter(*this).DependsList();
1101    for (; Dep.end() != true;)
1102    {
1103       // Grok or groups
1104       DepIterator Start = Dep;
1105       bool Result = true;
1106       unsigned Ors = 0;
1107       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1108       {
1109          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1110
1111          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1112             Result = false;
1113       }
1114
1115       // Dep is satisfied okay.
1116       if (Result == false)
1117          continue;
1118
1119       /* Check if this dep should be consider for install. If it is a user
1120          defined important dep and we are installed a new package then
1121          it will be installed. Otherwise we only check for important
1122          deps that have changed from the installed version */
1123       if (IsImportantDep(Start) == false)
1124          continue;
1125
1126       /* If we are in an or group locate the first or that can
1127          succeed. We have already cached this… */
1128       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1129          ++Start;
1130
1131       /* unsatisfiable dependency: IsInstallOkDependenciesSatisfiableByCandidates
1132          would have prevented us to get here if not overridden, so just skip
1133          over the problem here as the frontend will know what it is doing */
1134       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
1135          continue;
1136
1137       /* Check if any ImportantDep() (but not Critical) were added
1138        * since we installed the package.  Also check for deps that
1139        * were satisfied in the past: for instance, if a version
1140        * restriction in a Recommends was tightened, upgrading the
1141        * package should follow that Recommends rather than causing the
1142        * dependency to be removed. (bug #470115)
1143        */
1144       if (Pkg->CurrentVer != 0 && ForceImportantDeps == false && Start.IsCritical() == false)
1145       {
1146          bool isNewImportantDep = true;
1147          bool isPreviouslySatisfiedImportantDep = false;
1148          for (DepIterator D = Pkg.CurrentVer().DependsList(); D.end() != true; ++D)
1149          {
1150             //FIXME: Should we handle or-group better here?
1151             // We do not check if the package we look for is part of the same or-group
1152             // we might find while searching, but could that really be a problem?
1153             if (D.IsCritical() == true || IsImportantDep(D) == false ||
1154                 Start.TargetPkg() != D.TargetPkg())
1155                continue;
1156
1157             isNewImportantDep = false;
1158
1159             while ((D->CompareOp & Dep::Or) != 0)
1160                ++D;
1161
1162             isPreviouslySatisfiedImportantDep = (((*this)[D] & DepGNow) != 0);
1163             if (isPreviouslySatisfiedImportantDep == true)
1164                break;
1165          }
1166
1167          if(isNewImportantDep == true)
1168          {
1169             if (DebugAutoInstall == true)
1170                std::clog << OutputInDepth(Depth) << "new important dependency: "
1171                          << Start.TargetPkg().FullName() << std::endl;
1172          }
1173          else if(isPreviouslySatisfiedImportantDep == true)
1174          {
1175             if (DebugAutoInstall == true)
1176                std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1177                          << Start.TargetPkg().FullName() << std::endl;
1178          }
1179          else
1180          {
1181             if (DebugAutoInstall == true)
1182                std::clog << OutputInDepth(Depth) << "ignore old unsatisfied important dependency on "
1183                          << Start.TargetPkg().FullName() << std::endl;
1184             continue;
1185          }
1186       }
1187
1188       /* This bit is for processing the possibility of an install/upgrade
1189          fixing the problem for "positive" dependencies */
1190       if (Start.IsNegative() == false && (DepState[Start->ID] & DepCVer) == DepCVer)
1191       {
1192          APT::VersionList verlist;
1193          pkgCache::VerIterator Cand = PkgState[Start.TargetPkg()->ID].CandidateVerIter(*this);
1194          if (Cand.end() == false && Start.IsSatisfied(Cand) == true)
1195             verlist.insert(Cand);
1196          for (PrvIterator Prv = Start.TargetPkg().ProvidesList(); Prv.end() != true; ++Prv)
1197          {
1198             pkgCache::VerIterator V = Prv.OwnerVer();
1199             pkgCache::VerIterator Cand = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1200             if (Cand.end() == true || V != Cand || Start.IsSatisfied(Prv) == false)
1201                continue;
1202             verlist.insert(Cand);
1203          }
1204          CompareProviders comp(Start);
1205
1206          do {
1207             APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
1208
1209             if (InstVer == verlist.end())
1210                break;
1211
1212             pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
1213             if(DebugAutoInstall == true)
1214                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1215                          << " as " << Start.DepType() << " of " << Pkg.Name()
1216                          << std::endl;
1217             if (MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps) == false)
1218             {
1219                verlist.erase(InstVer);
1220                continue;
1221             }
1222             // now check if we should consider it a automatic dependency or not
1223             if(InstPkg->CurrentVer == 0 && InstVer->Section != 0 && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", InstVer.Section()))
1224             {
1225                if(DebugAutoInstall == true)
1226                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1227                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1228                MarkAuto(InstPkg, false);
1229             }
1230             break;
1231          } while(true);
1232          continue;
1233       }
1234       /* Negative dependencies have no or-group
1235          If the dependency isn't versioned, we try if an upgrade might solve the problem.
1236          Otherwise we remove the offender if needed */
1237       else if (Start.IsNegative() == true && Start->Type != pkgCache::Dep::Obsoletes)
1238       {
1239          SPtrArray<Version *> List = Start.AllTargets();
1240          pkgCache::PkgIterator TrgPkg = Start.TargetPkg();
1241          for (Version **I = List; *I != 0; I++)
1242          {
1243             VerIterator Ver(*this,*I);
1244             PkgIterator Pkg = Ver.ParentPkg();
1245
1246             /* The List includes all packages providing this dependency,
1247                even providers which are not installed, so skip them. */
1248             if (PkgState[Pkg->ID].InstallVer == 0)
1249                continue;
1250
1251             /* Ignore negative dependencies that we are not going to
1252                get installed */
1253             if (PkgState[Pkg->ID].InstallVer != *I)
1254                continue;
1255
1256             if ((Start->Version != 0 || TrgPkg != Pkg) &&
1257                 PkgState[Pkg->ID].CandidateVer != PkgState[Pkg->ID].InstallVer &&
1258                 PkgState[Pkg->ID].CandidateVer != *I &&
1259                 MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps) == true)
1260                continue;
1261             else if (Start->Type == pkgCache::Dep::Conflicts ||
1262                      Start->Type == pkgCache::Dep::DpkgBreaks)
1263             {
1264                if(DebugAutoInstall == true)
1265                   std::clog << OutputInDepth(Depth)
1266                             << " Removing: " << Pkg.Name()
1267                             << std::endl;
1268                if (MarkDelete(Pkg,false,Depth + 1, false) == false)
1269                   break;
1270             }
1271          }
1272          continue;
1273       }
1274    }
1275
1276    return Dep.end() == true;
1277 }
1278                                                                         /*}}}*/
1279 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1280 // ---------------------------------------------------------------------
1281 /* The default implementation checks if the installation of an M-A:same
1282    package would lead us into a version-screw and if so forbids it.
1283    dpkg holds are enforced by the private IsModeChangeOk */
1284 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1285                               unsigned long Depth, bool FromUser)
1286 {
1287    return IsInstallOkMultiArchSameVersionSynced(Pkg,AutoInst, Depth, FromUser) &&
1288       IsInstallOkDependenciesSatisfiableByCandidates(Pkg,AutoInst, Depth, FromUser);
1289 }
1290 bool pkgDepCache::IsInstallOkMultiArchSameVersionSynced(PkgIterator const &Pkg,
1291       bool const /*AutoInst*/, unsigned long const Depth, bool const FromUser)
1292 {
1293    if (FromUser == true) // as always: user is always right
1294       return true;
1295
1296    // if we have checked before and it was okay, it will still be okay
1297    if (PkgState[Pkg->ID].Mode == ModeInstall &&
1298          PkgState[Pkg->ID].InstallVer == PkgState[Pkg->ID].CandidateVer)
1299       return true;
1300
1301    // ignore packages with none-M-A:same candidates
1302    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1303    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer() ||
1304          (CandVer->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1305       return true;
1306
1307    GrpIterator const Grp = Pkg.Group();
1308    for (PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1309    {
1310       // not installed or self-check: fine by definition
1311       if (P->CurrentVer == 0 || P == Pkg)
1312          continue;
1313
1314       // not having a candidate or being in sync
1315       // (simple string-compare as stuff like '1' == '0:1-0' can't happen here)
1316       VerIterator CV = PkgState[P->ID].CandidateVerIter(*this);
1317       if (CV.end() == true || strcmp(Pkg.CandVersion(), CV.VerStr()) == 0)
1318          continue;
1319
1320       // packages losing M-A:same can be out-of-sync
1321       if ((CV->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1322          continue;
1323
1324       // not downloadable means the package is obsolete, so allow out-of-sync
1325       if (CV.Downloadable() == false)
1326          continue;
1327
1328       PkgState[Pkg->ID].iFlags |= AutoKept;
1329       if (unlikely(DebugMarker == true))
1330          std::clog << OutputInDepth(Depth) << "Ignore MarkInstall of " << Pkg
1331             << " as it is not in sync with its M-A:same sibling " << P
1332             << " (" << Pkg.CandVersion() << " != " << CV.VerStr() << ")" << 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 && (PkgState[Pkg->ID].iFlags & Protected) != Protected)
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().Flagged(Flag::NotSource))
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().Flagged(Flag::NotAutomatic) ||
1696              J.File().Flagged(Flag::ButAutomaticUpgrades))
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                                                                         /*}}}*/
1963 // DepCache::MarkAndSweep                                               /*{{{*/
1964 bool pkgDepCache::MarkAndSweep(InRootSetFunc &rootFunc)
1965 {
1966    return MarkRequired(rootFunc) && Sweep();
1967 }
1968 bool pkgDepCache::MarkAndSweep()
1969 {
1970    std::auto_ptr<InRootSetFunc> f(GetRootSetFunc());
1971    if(f.get() != NULL)
1972       return MarkAndSweep(*f.get());
1973    else
1974       return false;
1975 }
1976                                                                         /*}}}*/