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