apt-pkg/depcache.cc

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