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(RealFileExists(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(!RealFileExists(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() != Dep.ParentPkg() ||
 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 already installed
1261        if(P.Status == 2 || Pkg->CurrentVer != 0)
1262          P.Flags &= ~Flag::Auto;
1263      }
1264    else
1265      {
1266        // Set it to auto if this is a new install.
1267        if(P.Status == 2)
1268          P.Flags |= Flag::Auto;
1269      }
1270    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1271       P.Mode = ModeKeep;
1272
1273    AddStates(Pkg);
1274    Update(Pkg);
1275    AddSizes(Pkg);
1276
1277    // always trigger the install of the all package for a pseudo package
1278    if (P.CandidateVerIter(*Cache).Pseudo() == true)
1279       MarkInstall(Pkg.Group().FindPkg("all"), AutoInst, Depth, FromUser, ForceImportantDeps);
1280
1281    if (AutoInst == false)
1282       return;
1283
1284    if (DebugMarker == true)
1285       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1286
1287    DepIterator Dep = P.InstVerIter(*this).DependsList();
1288    for (; Dep.end() != true;)
1289    {
1290       // Grok or groups
1291       DepIterator Start = Dep;
1292       bool Result = true;
1293       unsigned Ors = 0;
1294       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
1295       {
1296          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1297
1298          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1299             Result = false;
1300       }
1301
1302       // Dep is satisfied okay.
1303       if (Result == false)
1304          continue;
1305
1306       /* Check if this dep should be consider for install. If it is a user
1307          defined important dep and we are installed a new package then
1308          it will be installed. Otherwise we only check for important
1309          deps that have changed from the installed version
1310       */
1311       if (IsImportantDep(Start) == false)
1312          continue;
1313
1314       /* Check if any ImportantDep() (but not Critical) were added
1315        * since we installed the package.  Also check for deps that
1316        * were satisfied in the past: for instance, if a version
1317        * restriction in a Recommends was tightened, upgrading the
1318        * package should follow that Recommends rather than causing the
1319        * dependency to be removed. (bug #470115)
1320        */
1321       bool isNewImportantDep = false;
1322       bool isPreviouslySatisfiedImportantDep = false;
1323       if(!ForceImportantDeps && !Start.IsCritical())
1324       {
1325          bool found=false;
1326          VerIterator instVer = Pkg.CurrentVer();
1327          if(!instVer.end())
1328          {
1329            for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
1330              {
1331                //FIXME: deal better with or-groups(?)
1332                if(IsImportantDep(D) && !D.IsCritical() &&
1333                   Start.TargetPkg() == D.TargetPkg())
1334                  {
1335                    if(!isPreviouslySatisfiedImportantDep)
1336                      {
1337                        DepIterator D2 = D;
1338                        while((D2->CompareOp & Dep::Or) != 0)
1339                          ++D2;
1340
1341                        isPreviouslySatisfiedImportantDep =
1342                          (((*this)[D2] & DepGNow) != 0);
1343                      }
1344
1345                    found=true;
1346                  }
1347              }
1348             // this is a new dep if it was not found to be already
1349             // a important dep of the installed pacakge
1350             isNewImportantDep = !found;
1351          }
1352       }
1353       if(isNewImportantDep)
1354          if(DebugAutoInstall == true)
1355             std::clog << OutputInDepth(Depth) << "new important dependency: "
1356                       << Start.TargetPkg().Name() << std::endl;
1357       if(isPreviouslySatisfiedImportantDep)
1358         if(DebugAutoInstall == true)
1359           std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1360                     << Start.TargetPkg().Name() << std::endl;
1361
1362       // skip important deps if the package is already installed
1363       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
1364           && !isNewImportantDep && !isPreviouslySatisfiedImportantDep
1365           && !ForceImportantDeps)
1366          continue;
1367
1368       /* If we are in an or group locate the first or that can
1369          succeed. We have already cached this.. */
1370       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
1371          Start++;
1372
1373       /* This bit is for processing the possibilty of an install/upgrade
1374          fixing the problem */
1375       SPtrArray<Version *> List = Start.AllTargets();
1376       if (Start->Type != Dep::DpkgBreaks &&
1377           (DepState[Start->ID] & DepCVer) == DepCVer)
1378       {
1379          // Right, find the best version to install..
1380          Version **Cur = List;
1381          PkgIterator P = Start.TargetPkg();
1382          PkgIterator InstPkg(*Cache,0);
1383
1384          // See if there are direct matches (at the start of the list)
1385          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
1386          {
1387             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1388             if (PkgState[Pkg->ID].CandidateVer != *Cur)
1389                continue;
1390             InstPkg = Pkg;
1391             break;
1392          }
1393
1394          // Select the highest priority providing package
1395          if (InstPkg.end() == true)
1396          {
1397             pkgPrioSortList(*Cache,Cur);
1398             for (; *Cur != 0; Cur++)
1399             {
1400                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1401                if (PkgState[Pkg->ID].CandidateVer != *Cur)
1402                   continue;
1403                InstPkg = Pkg;
1404                break;
1405             }
1406          }
1407
1408          if (InstPkg.end() == false)
1409          {
1410             if(DebugAutoInstall == true)
1411                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1412                          << " as " << Start.DepType() << " of " << Pkg.Name()
1413                          << std::endl;
1414             // now check if we should consider it a automatic dependency or not
1415             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1416             {
1417                if(DebugAutoInstall == true)
1418                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1419                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1420                MarkInstall(InstPkg,true,Depth + 1, true);
1421             }
1422             else
1423             {
1424                // mark automatic dependency
1425                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1426                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1427                if (P->CurrentVer == 0)
1428                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1429             }
1430          }
1431          continue;
1432       }
1433
1434       /* For conflicts we just de-install the package and mark as auto,
1435          Conflicts may not have or groups.  For dpkg's Breaks we try to
1436          upgrade the package. */
1437       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
1438           Start->Type == Dep::DpkgBreaks)
1439       {
1440          for (Version **I = List; *I != 0; I++)
1441          {
1442             VerIterator Ver(*this,*I);
1443             PkgIterator Pkg = Ver.ParentPkg();
1444
1445             /* The List includes all packages providing this dependency,
1446                even providers which are not installed, so skip them. */
1447             if (PkgState[Pkg->ID].InstallVer == 0)
1448                continue;
1449
1450             if (PkgState[Pkg->ID].CandidateVer != *I &&
1451                 Start->Type == Dep::DpkgBreaks)
1452                MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
1453             else
1454                MarkDelete(Pkg,false,Depth + 1, false);
1455          }
1456          continue;
1457       }
1458    }
1459 }
1460                                                                         /*}}}*/
1461 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1462 // ---------------------------------------------------------------------
1463 /* The default implementation just honors dpkg hold
1464    But an application using this library can override this method
1465    to control the MarkInstall behaviour */
1466 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1467                               unsigned long Depth, bool FromUser)
1468 {
1469    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
1470    {
1471       if (DebugMarker == true)
1472          std::clog << OutputInDepth(Depth) << "Hold prevents MarkInstall of " << Pkg << " FU=" << FromUser << std::endl;
1473       return false;
1474    }
1475    return true;
1476 }
1477                                                                         /*}}}*/
1478 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1479 // ---------------------------------------------------------------------
1480 /* */
1481 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1482 {
1483    if (unlikely(Pkg.end() == true))
1484       return;
1485
1486    ActionGroup group(*this);
1487
1488    RemoveSizes(Pkg);
1489    RemoveStates(Pkg);
1490
1491    StateCache &P = PkgState[Pkg->ID];
1492    if (To == true)
1493       P.iFlags |= ReInstall;
1494    else
1495       P.iFlags &= ~ReInstall;
1496
1497    AddStates(Pkg);
1498    AddSizes(Pkg);
1499
1500    if (unlikely(Pkg.CurrentVer().end() == true) || Pkg.CurrentVer().Pseudo() == false)
1501       return;
1502
1503    SetReInstall(Pkg.Group().FindPkg("all"), To);
1504 }
1505                                                                         /*}}}*/
1506 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1507 // ---------------------------------------------------------------------
1508 /* */
1509 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer, bool const &Pseudo)
1510 {
1511
1512    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1513    StateCache &P = PkgState[Pkg->ID];
1514
1515    if (P.CandidateVer == TargetVer)
1516       return;
1517
1518    ActionGroup group(*this);
1519
1520    RemoveSizes(Pkg);
1521    RemoveStates(Pkg);
1522
1523    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1524       P.InstallVer = (Version *)TargetVer;
1525    P.CandidateVer = (Version *)TargetVer;
1526    P.Update(Pkg,*this);
1527
1528    AddStates(Pkg);
1529    Update(Pkg);
1530    AddSizes(Pkg);
1531
1532    if (TargetVer.Pseudo() == false || Pseudo == false)
1533       return;
1534
1535    // the version was pseudo: set all other pseudos also
1536    pkgCache::GrpIterator Grp = Pkg.Group();
1537    for (Pkg = Grp.FindPkg("any"); Pkg.end() == false; ++Pkg)
1538    {
1539       StateCache &P = PkgState[Pkg->ID];
1540       if (TargetVer.SimilarVer(P.CandidateVerIter(*this)) == true ||
1541           (P.CandidateVerIter(*this).Pseudo() == false &&
1542            strcmp(Pkg.Arch(), "all") != 0))
1543          continue;
1544
1545       for (pkgCache::VerIterator Ver = Pkg.VersionList(); Ver.end() == false; ++Ver)
1546       {
1547          if (TargetVer.SimilarVer(Ver) == false)
1548             continue;
1549          SetCandidateVersion(Ver, false);
1550          break;
1551       }
1552    }
1553 }
1554                                                                         /*}}}*/
1555 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1556 // ---------------------------------------------------------------------
1557 /* changes the candidate of a package and walks over all its dependencies
1558    to check if it needs to change the candidate of the dependency, too,
1559    to reach a installable versionstate */
1560 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1561                                         std::string const &TargetRel)
1562 {
1563    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1564    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1565 }
1566 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1567                                         std::string const &TargetRel,
1568                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1569 {
1570    ActionGroup group(*this);
1571    SetCandidateVersion(TargetVer);
1572
1573    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1574       return true;
1575
1576    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1577    // save the position of the last element we will not undo - if we have to
1578    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1579
1580    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1581    {
1582       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1583           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1584            IsImportantDep(D) == false))
1585          continue;
1586
1587       // walk over an or-group and check if we need to do anything
1588       // for simpilicity no or-group is handled as a or-group including one dependency
1589       pkgCache::DepIterator Start = D;
1590       bool itsFine = false;
1591       for (bool stillOr = true; stillOr == true; ++Start)
1592       {
1593          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1594          pkgCache::PkgIterator const P = Start.TargetPkg();
1595          // virtual packages can't be a solution
1596          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1597             continue;
1598          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1599          // no versioned dependency - but is it installable?
1600          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1601          {
1602             // Check if one of the providers is installable
1603             if (P->ProvidesList != 0)
1604             {
1605                pkgCache::PrvIterator Prv = P.ProvidesList();
1606                for (; Prv.end() == false; ++Prv)
1607                {
1608                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1609                   if (C.end() == true || C != Prv.OwnerVer() ||
1610                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1611                      continue;
1612                   break;
1613                }
1614                if (Prv.end() == true)
1615                   continue;
1616             }
1617             // no providers, so check if we have an installable candidate version
1618             else if (Cand.end() == true ||
1619                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1620                continue;
1621             itsFine = true;
1622             break;
1623          }
1624          if (Cand.end() == true)
1625             continue;
1626          // check if the current candidate is enough for the versioned dependency - and installable?
1627          if (VS().CheckDep(P.CandVersion(), Start->CompareOp, Start.TargetVer()) == true &&
1628              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1629          {
1630             itsFine = true;
1631             break;
1632          }
1633       }
1634
1635       if (itsFine == true) {
1636          // something in the or-group was fine, skip all other members
1637          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1638          continue;
1639       }
1640
1641       // walk again over the or-group and check each if a candidate switch would help
1642       itsFine = false;
1643       for (bool stillOr = true; stillOr == true; ++D)
1644       {
1645          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1646          // changing candidate will not help if the dependency is not versioned
1647          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1648          {
1649             if (stillOr == true)
1650                continue;
1651             break;
1652          }
1653
1654          pkgCache::VerIterator V;
1655          if (TargetRel == "newest")
1656             V = D.TargetPkg().VersionList();
1657          else
1658             V = Match.Find(D.TargetPkg());
1659
1660          // check if the version from this release could satisfy the dependency
1661          if (V.end() == true || VS().CheckDep(V.VerStr(), D->CompareOp, D.TargetVer()) == false)
1662          {
1663             if (stillOr == true)
1664                continue;
1665             break;
1666          }
1667
1668          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1669          if (V == oldCand)
1670          {
1671             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1672             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1673                  c != Changed.end(); ++c)
1674             {
1675                if (c->first->ParentPkg != V->ParentPkg)
1676                   continue;
1677                itsFine = true;
1678                break;
1679             }
1680          }
1681
1682          if (itsFine == false)
1683          {
1684             // change the candidate
1685             Changed.push_back(make_pair(oldCand, TargetVer));
1686             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1687             {
1688                if (stillOr == false)
1689                   break;
1690                // undo the candidate changing
1691                SetCandidateVersion(oldCand);
1692                Changed.pop_back();
1693                continue;
1694             }
1695             itsFine = true;
1696          }
1697
1698          // something in the or-group was fine, skip all other members
1699          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1700          break;
1701       }
1702
1703       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1704       {
1705          // undo all changes which aren't lead to a solution
1706          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1707               c != Changed.end(); ++c)
1708             SetCandidateVersion(c->first);
1709          Changed.erase(newChanged, Changed.end());
1710          return false;
1711       }
1712    }
1713    return true;
1714 }
1715                                                                         /*}}}*/
1716 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1717 // ---------------------------------------------------------------------
1718 /* */
1719 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1720 {
1721   StateCache &state = PkgState[Pkg->ID];
1722
1723   ActionGroup group(*this);
1724
1725   if(Auto)
1726     state.Flags |= Flag::Auto;
1727   else
1728     state.Flags &= ~Flag::Auto;
1729 }
1730                                                                         /*}}}*/
1731 // StateCache::Update - Compute the various static display things       /*{{{*/
1732 // ---------------------------------------------------------------------
1733 /* This is called whenever the Candidate version changes. */
1734 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1735 {
1736    // Some info
1737    VerIterator Ver = CandidateVerIter(Cache);
1738
1739    // Use a null string or the version string
1740    if (Ver.end() == true)
1741       CandVersion = "";
1742    else
1743       CandVersion = Ver.VerStr();
1744
1745    // Find the current version
1746    CurVersion = "";
1747    if (Pkg->CurrentVer != 0)
1748       CurVersion = Pkg.CurrentVer().VerStr();
1749
1750    // Strip off the epochs for display
1751    CurVersion = StripEpoch(CurVersion);
1752    CandVersion = StripEpoch(CandVersion);
1753
1754    // Figure out if its up or down or equal
1755    Status = Ver.CompareVer(Pkg.CurrentVer());
1756    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1757      Status = 2;
1758 }
1759                                                                         /*}}}*/
1760 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1761 // ---------------------------------------------------------------------
1762 /* */
1763 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1764 {
1765    if (Ver == 0)
1766       return 0;
1767
1768    // Strip any epoch
1769    for (const char *I = Ver; *I != 0; I++)
1770       if (*I == ':')
1771          return I + 1;
1772    return Ver;
1773 }
1774                                                                         /*}}}*/
1775 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1776 // ---------------------------------------------------------------------
1777 /* The default just returns the highest available version that is not
1778    a source and automatic. */
1779 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1780 {
1781    /* Not source/not automatic versions cannot be a candidate version
1782       unless they are already installed */
1783    VerIterator Last(*(pkgCache *)this,0);
1784
1785    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1786    {
1787       if (Pkg.CurrentVer() == I)
1788          return I;
1789
1790       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1791       {
1792          if ((J.File()->Flags & Flag::NotSource) != 0)
1793             continue;
1794
1795          /* Stash the highest version of a not-automatic source, we use it
1796             if there is nothing better */
1797          if ((J.File()->Flags & Flag::NotAutomatic) != 0 ||
1798              (J.File()->Flags & Flag::ButAutomaticUpgrades) != 0)
1799          {
1800             if (Last.end() == true)
1801                Last = I;
1802             continue;
1803          }
1804
1805          return I;
1806       }
1807    }
1808
1809    return Last;
1810 }
1811                                                                         /*}}}*/
1812 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1813 // ---------------------------------------------------------------------
1814 /* */
1815 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
1816 {
1817    if(Dep.IsCritical())
1818       return true;
1819    else if(Dep->Type == pkgCache::Dep::Recommends)
1820    {
1821       if ( _config->FindB("APT::Install-Recommends", false))
1822          return true;
1823       // we suport a special mode to only install-recommends for certain
1824       // sections
1825       // FIXME: this is a meant as a temporarly solution until the
1826       //        recommends are cleaned up
1827       const char *sec = Dep.ParentVer().Section();
1828       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1829          return true;
1830    }
1831    else if(Dep->Type == pkgCache::Dep::Suggests)
1832      return _config->FindB("APT::Install-Suggests", false);
1833
1834    return false;
1835 }
1836                                                                         /*}}}*/
1837 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1838 {
1839   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1840   if(f->wasConstructedSuccessfully())
1841     return f;
1842   else
1843     {
1844       delete f;
1845       return NULL;
1846     }
1847 }
1848                                                                         /*}}}*/
1849 bool pkgDepCache::MarkFollowsRecommends()
1850 {
1851   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1852 }
1853
1854 bool pkgDepCache::MarkFollowsSuggests()
1855 {
1856   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1857 }
1858
1859 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1860 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1861 {
1862    bool follow_recommends;
1863    bool follow_suggests;
1864    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1865
1866    // init the states
1867    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1868    {
1869       PkgState[p->ID].Marked  = false;
1870       PkgState[p->ID].Garbage = false;
1871
1872       // debug output
1873       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1874          std::clog << "AutoDep: " << p.FullName() << std::endl;
1875    }
1876
1877    // init vars
1878    follow_recommends = MarkFollowsRecommends();
1879    follow_suggests   = MarkFollowsSuggests();
1880
1881
1882
1883    // do the mark part, this is the core bit of the algorithm
1884    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1885    {
1886       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1887           (p->Flags & Flag::Essential) ||
1888           userFunc.InRootSet(p) ||
1889           // be nice even then a required package violates the policy (#583517)
1890           // and do the full mark process also for required packages
1891           (p.CurrentVer().end() != true &&
1892            p.CurrentVer()->Priority == pkgCache::State::Required))
1893       {
1894          // the package is installed (and set to keep)
1895          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1896             MarkPackage(p, p.CurrentVer(),
1897                         follow_recommends, follow_suggests);
1898          // the package is to be installed
1899          else if(PkgState[p->ID].Install())
1900             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1901                         follow_recommends, follow_suggests);
1902       }
1903    }
1904
1905    return true;
1906 }
1907                                                                         /*}}}*/
1908 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1909 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1910                               const pkgCache::VerIterator &ver,
1911                               bool const &follow_recommends,
1912                               bool const &follow_suggests)
1913 {
1914    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1915
1916    // if we are marked already we are done
1917    if(state.Marked)
1918       return;
1919
1920    VerIterator const currver = pkg.CurrentVer();
1921    VerIterator const instver = state.InstVerIter(*this);
1922
1923 #if 0
1924    VerIterator const candver = state.CandidateVerIter(*this);
1925
1926    // If a package was garbage-collected but is now being marked, we
1927    // should re-select it
1928    // For cases when a pkg is set to upgrade and this trigger the
1929    // removal of a no-longer used dependency.  if the pkg is set to
1930    // keep again later it will result in broken deps
1931    if(state.Delete() && state.RemoveReason = Unused)
1932    {
1933       if(ver==candver)
1934          mark_install(pkg, false, false, NULL);
1935       else if(ver==pkg.CurrentVer())
1936          MarkKeep(pkg, false, false);
1937
1938       instver=state.InstVerIter(*this);
1939    }
1940 #endif
1941
1942    // For packages that are not going to be removed, ignore versions
1943    // other than the InstVer.  For packages that are going to be
1944    // removed, ignore versions other than the current version.
1945    if(!(ver == instver && !instver.end()) &&
1946       !(ver == currver && instver.end() && !ver.end()))
1947       return;
1948
1949    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1950
1951    if(debug_autoremove)
1952      {
1953        std::clog << "Marking: " << pkg.FullName();
1954        if(!ver.end())
1955          std::clog << " " << ver.VerStr();
1956        if(!currver.end())
1957          std::clog << ", Curr=" << currver.VerStr();
1958        if(!instver.end())
1959          std::clog << ", Inst=" << instver.VerStr();
1960        std::clog << std::endl;
1961      }
1962
1963    state.Marked=true;
1964
1965    if(ver.end() == true)
1966       return;
1967
1968    // If the version belongs to a Multi-Arch all package
1969    // we will mark all others in this Group with this version also
1970    if (ver->MultiArch == pkgCache::Version::All &&
1971         strcmp(ver.Arch(true), "all") == 0)
1972    {
1973       GrpIterator G = pkg.Group();
1974       const char* const VerStr = ver.VerStr();
1975       for (PkgIterator P = G.FindPkg("any");
1976            P.end() != true; P = G.NextPkg(P))
1977       {
1978          for (VerIterator V = P.VersionList();
1979               V.end() != true; ++V)
1980          {
1981             if (ver->Hash != V->Hash ||
1982                 strcmp(VerStr, V.VerStr()) != 0)
1983                continue;
1984             MarkPackage(P, V, follow_recommends, follow_suggests);
1985             break;
1986          }
1987       }
1988    }
1989
1990      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1991      {
1992         if(d->Type == Dep::Depends ||
1993            d->Type == Dep::PreDepends ||
1994            (follow_recommends &&
1995             d->Type == Dep::Recommends) ||
1996            (follow_suggests &&
1997             d->Type == Dep::Suggests))
1998         {
1999            // Try all versions of this package.
2000            for(VerIterator V = d.TargetPkg().VersionList();
2001                !V.end(); ++V)
2002            {
2003               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
2004               {
2005                 if(debug_autoremove)
2006                   {
2007                     std::clog << "Following dep: " << d.ParentPkg().FullName()
2008                               << " " << d.ParentVer().VerStr() << " "
2009                               << d.DepType() << " " << d.TargetPkg().FullName();
2010                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
2011                       {
2012                         std::clog << " (" << d.CompType() << " "
2013                                   << d.TargetVer() << ")";
2014                       }
2015                     std::clog << std::endl;
2016                   }
2017                  MarkPackage(V.ParentPkg(), V,
2018                              follow_recommends, follow_suggests);
2019               }
2020            }
2021            // Now try virtual packages
2022            for(PrvIterator prv=d.TargetPkg().ProvidesList();
2023                !prv.end(); ++prv)
2024            {
2025               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
2026                                        d.TargetVer()))
2027               {
2028                 if(debug_autoremove)
2029                   {
2030                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
2031                               << d.ParentVer().VerStr() << " "
2032                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
2033                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
2034                       {
2035                         std::clog << " (" << d.CompType() << " "
2036                                   << d.TargetVer() << ")";
2037                       }
2038                     std::clog << ", provided by "
2039                               << prv.OwnerPkg().FullName() << " "
2040                               << prv.OwnerVer().VerStr()
2041                               << std::endl;
2042                   }
2043
2044                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
2045                              follow_recommends, follow_suggests);
2046               }
2047            }
2048         }
2049      }
2050 }
2051                                                                         /*}}}*/
2052 bool pkgDepCache::Sweep()                                               /*{{{*/
2053 {
2054    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
2055
2056    // do the sweep
2057    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
2058    {
2059      StateCache &state=PkgState[p->ID];
2060
2061      // skip required packages
2062      if (!p.CurrentVer().end() &&
2063          (p.CurrentVer()->Priority == pkgCache::State::Required))
2064         continue;
2065
2066      // if it is not marked and it is installed, it's garbage
2067      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
2068      {
2069         state.Garbage=true;
2070         if(debug_autoremove)
2071            std::clog << "Garbage: " << p.FullName() << std::endl;
2072      }
2073   }
2074
2075    return true;
2076 }
2077                                                                         /*}}}*/