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