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