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::Update - Figure out all the state information              /*{{{*/
 709 // ---------------------------------------------------------------------
 710 /* This will figure out the state of all the packages and all the
 711    dependencies based on the current policy. */
 712 void pkgDepCache::Update(OpProgress *Prog)
 713 {
 714    iUsrSize = 0;
 715    iDownloadSize = 0;
 716    iDelCount = 0;
 717    iInstCount = 0;
 718    iKeepCount = 0;
 719    iBrokenCount = 0;
 720    iBadCount = 0;
 721
 722    // Perform the depends pass
 723    int Done = 0;
 724    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 725    {
 726       if (Prog != 0 && Done%20 == 0)
 727          Prog->Progress(Done);
 728       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 729       {
 730          unsigned char Group = 0;
 731
 732          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 733          {
 734             // Build the dependency state.
 735             unsigned char &State = DepState[D->ID];
 736             State = DependencyState(D);
 737
 738             // Add to the group if we are within an or..
 739             Group |= State;
 740             State |= Group << 3;
 741             if ((D->CompareOp & Dep::Or) != Dep::Or)
 742                Group = 0;
 743
 744             // Invert for Conflicts
 745             if (D->Type == Dep::Conflicts ||
 746                 D->Type == Dep::DpkgBreaks ||
 747                 D->Type == Dep::Obsoletes)
 748                State = ~State;
 749          }
 750       }
 751
 752       // Compute the package dependency state and size additions
 753       AddSizes(I);
 754       UpdateVerState(I);
 755       AddStates(I);
 756    }
 757
 758    if (Prog != 0)
 759       Prog->Progress(Done);
 760
 761    readStateFile(Prog);
 762 }
 763                                                                         /*}}}*/
 764 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 765 // ---------------------------------------------------------------------
 766 /* This is a helper for update that only does the dep portion of the scan.
 767    It is mainly meant to scan reverse dependencies. */
 768 void pkgDepCache::Update(DepIterator D)
 769 {
 770    // Update the reverse deps
 771    for (;D.end() != true; D++)
 772    {
 773       unsigned char &State = DepState[D->ID];
 774       State = DependencyState(D);
 775
 776       // Invert for Conflicts
 777       if (D->Type == Dep::Conflicts ||
 778           D->Type == Dep::DpkgBreaks ||
 779           D->Type == Dep::Obsoletes)
 780          State = ~State;
 781
 782       RemoveStates(D.ParentPkg());
 783       BuildGroupOrs(D.ParentVer());
 784       UpdateVerState(D.ParentPkg());
 785       AddStates(D.ParentPkg());
 786    }
 787 }
 788                                                                         /*}}}*/
 789 // DepCache::Update - Update the related deps of a package              /*{{{*/
 790 // ---------------------------------------------------------------------
 791 /* This is called whenever the state of a package changes. It updates
 792    all cached dependencies related to this package. */
 793 void pkgDepCache::Update(PkgIterator const &Pkg)
 794 {
 795    // Recompute the dep of the package
 796    RemoveStates(Pkg);
 797    UpdateVerState(Pkg);
 798    AddStates(Pkg);
 799
 800    // Update the reverse deps
 801    Update(Pkg.RevDependsList());
 802
 803    // Update the provides map for the current ver
 804    if (Pkg->CurrentVer != 0)
 805       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 806            P.end() != true; P++)
 807          Update(P.ParentPkg().RevDependsList());
 808
 809    // Update the provides map for the candidate ver
 810    if (PkgState[Pkg->ID].CandidateVer != 0)
 811       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 812            P.end() != true; P++)
 813          Update(P.ParentPkg().RevDependsList());
 814 }
 815                                                                         /*}}}*/
 816 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 817 // ---------------------------------------------------------------------
 818 /* */
 819 void pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 820                            unsigned long Depth)
 821 {
 822    // Simplifies other routines.
 823    if (Pkg.end() == true)
 824       return;
 825
 826    /* Reject an attempt to keep a non-source broken installed package, those
 827       must be upgraded */
 828    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 829        Pkg.CurrentVer().Downloadable() == false)
 830       return;
 831
 832    /** \todo Can this be moved later in the method? */
 833    ActionGroup group(*this);
 834
 835    /* We changed the soft state all the time so the UI is a bit nicer
 836       to use */
 837    StateCache &P = PkgState[Pkg->ID];
 838    if (Soft == true)
 839       P.iFlags |= AutoKept;
 840    else
 841       P.iFlags &= ~AutoKept;
 842
 843    // Check that it is not already kept
 844    if (P.Mode == ModeKeep)
 845       return;
 846
 847    // We dont even try to keep virtual packages..
 848    if (Pkg->VersionList == 0)
 849       return;
 850 #if 0 // reseting the autoflag here means we lose the
 851       // auto-mark information if a user selects a package for removal
 852       // but changes  his mind then and sets it for keep again
 853       // - this makes sense as default when all Garbage dependencies
 854       //   are automatically marked for removal (as aptitude does).
 855       //   setting a package for keep then makes it no longer autoinstalled
 856       //   for all other use-case this action is rather suprising
 857    if(FromUser && !P.Marked)
 858      P.Flags &= ~Flag::Auto;
 859 #endif
 860
 861    if (DebugMarker == true)
 862       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 863
 864    RemoveSizes(Pkg);
 865    RemoveStates(Pkg);
 866
 867    P.Mode = ModeKeep;
 868    if (Pkg->CurrentVer == 0)
 869       P.InstallVer = 0;
 870    else
 871       P.InstallVer = Pkg.CurrentVer();
 872
 873    AddStates(Pkg);
 874
 875    Update(Pkg);
 876
 877    AddSizes(Pkg);
 878 }
 879                                                                         /*}}}*/
 880 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 881 // ---------------------------------------------------------------------
 882 /* */
 883 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 884                              unsigned long Depth, bool FromUser)
 885 {
 886    // Simplifies other routines.
 887    if (Pkg.end() == true)
 888       return;
 889
 890    ActionGroup group(*this);
 891
 892    // Check that it is not already marked for delete
 893    StateCache &P = PkgState[Pkg->ID];
 894    P.iFlags &= ~(AutoKept | Purge);
 895    if (rPurge == true)
 896       P.iFlags |= Purge;
 897
 898    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 899        (Pkg.Purge() == true || rPurge == false))
 900       return;
 901
 902    // We dont even try to delete virtual packages..
 903    if (Pkg->VersionList == 0)
 904       return;
 905
 906    // check if we are allowed to install the package
 907    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
 908       return;
 909
 910    if (DebugMarker == true)
 911       std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << Pkg << " FU=" << FromUser << std::endl;
 912
 913    RemoveSizes(Pkg);
 914    RemoveStates(Pkg);
 915
 916    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 917       P.Mode = ModeKeep;
 918    else
 919       P.Mode = ModeDelete;
 920    P.InstallVer = 0;
 921
 922    AddStates(Pkg);
 923    Update(Pkg);
 924    AddSizes(Pkg);
 925
 926 }
 927                                                                         /*}}}*/
 928 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 929 // ---------------------------------------------------------------------
 930 /* The default implementation just honors dpkg hold
 931    But an application using this library can override this method
 932    to control the MarkDelete behaviour */
 933 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 934                               unsigned long Depth, bool FromUser)
 935 {
 936    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
 937    {
 938       if (DebugMarker == true)
 939          std::clog << OutputInDepth(Depth) << "Hold prevents MarkDelete of " << Pkg << " FU=" << FromUser << std::endl;
 940       return false;
 941    }
 942    // if the removal is not explictely requested by the user, protect
 943    // explicit new-install package from accidental removal by the
 944    // problemresolver
 945    else if (FromUser == false && Pkg->CurrentVer == 0)
 946    {
 947       StateCache &P = PkgState[Pkg->ID];
 948       // Status == 2 means this applies for new installs only
 949       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
 950       {
 951          if (DebugMarker == true)
 952             std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << Pkg << std::endl;
 953          return false;
 954       }
 955    }
 956    return true;
 957 }
 958                                                                         /*}}}*/
 959 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 960 // ---------------------------------------------------------------------
 961 /* */
 962 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 963                               unsigned long Depth, bool FromUser,
 964                               bool ForceImportantDeps)
 965 {
 966    if (Depth > 100)
 967       return;
 968
 969    // Simplifies other routines.
 970    if (Pkg.end() == true)
 971       return;
 972
 973    ActionGroup group(*this);
 974
 975    /* Check that it is not already marked for install and that it can be
 976       installed */
 977    StateCache &P = PkgState[Pkg->ID];
 978    P.iFlags &= ~AutoKept;
 979    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
 980        (P.Mode == ModeInstall ||
 981         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 982    {
 983       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 984          MarkKeep(Pkg, false, FromUser, Depth+1);
 985       return;
 986    }
 987
 988    // See if there is even any possible instalation candidate
 989    if (P.CandidateVer == 0)
 990       return;
 991    // We dont even try to install virtual packages..
 992    if (Pkg->VersionList == 0)
 993       return;
 994
 995    // check if we are allowed to install the package
 996    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
 997       return;
 998
 999    /* Target the candidate version and remove the autoflag. We reset the
1000       autoflag below if this was called recursively. Otherwise the user
1001       should have the ability to de-auto a package by changing its state */
1002    RemoveSizes(Pkg);
1003    RemoveStates(Pkg);
1004
1005    P.Mode = ModeInstall;
1006    P.InstallVer = P.CandidateVer;
1007
1008    if(FromUser)
1009      {
1010        // Set it to manual if it's a new install or already installed,
1011        // but only if its not marked by the autoremover (aptitude depend on this behavior)
1012        // or if we do automatic installation (aptitude never does it)
1013        if(P.Status == 2 || (Pkg->CurrentVer != 0 && (AutoInst == true || P.Marked == false)))
1014          P.Flags &= ~Flag::Auto;
1015      }
1016    else
1017      {
1018        // Set it to auto if this is a new install.
1019        if(P.Status == 2)
1020          P.Flags |= Flag::Auto;
1021      }
1022    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1023       P.Mode = ModeKeep;
1024
1025    AddStates(Pkg);
1026    Update(Pkg);
1027    AddSizes(Pkg);
1028
1029    if (AutoInst == false)
1030       return;
1031
1032    if (DebugMarker == true)
1033       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1034
1035    DepIterator Dep = P.InstVerIter(*this).DependsList();
1036    for (; Dep.end() != true;)
1037    {
1038       // Grok or groups
1039       DepIterator Start = Dep;
1040       bool Result = true;
1041       unsigned Ors = 0;
1042       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
1043       {
1044          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1045
1046          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1047             Result = false;
1048       }
1049
1050       // Dep is satisfied okay.
1051       if (Result == false)
1052          continue;
1053
1054       /* Check if this dep should be consider for install. If it is a user
1055          defined important dep and we are installed a new package then
1056          it will be installed. Otherwise we only check for important
1057          deps that have changed from the installed version
1058       */
1059       if (IsImportantDep(Start) == false)
1060          continue;
1061
1062       /* Check if any ImportantDep() (but not Critical) were added
1063        * since we installed the package.  Also check for deps that
1064        * were satisfied in the past: for instance, if a version
1065        * restriction in a Recommends was tightened, upgrading the
1066        * package should follow that Recommends rather than causing the
1067        * dependency to be removed. (bug #470115)
1068        */
1069       bool isNewImportantDep = false;
1070       bool isPreviouslySatisfiedImportantDep = false;
1071       if(!ForceImportantDeps && !Start.IsCritical())
1072       {
1073          bool found=false;
1074          VerIterator instVer = Pkg.CurrentVer();
1075          if(!instVer.end())
1076          {
1077            for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
1078              {
1079                //FIXME: deal better with or-groups(?)
1080                if(IsImportantDep(D) && !D.IsCritical() &&
1081                   Start.TargetPkg() == D.TargetPkg())
1082                  {
1083                    if(!isPreviouslySatisfiedImportantDep)
1084                      {
1085                        DepIterator D2 = D;
1086                        while((D2->CompareOp & Dep::Or) != 0)
1087                          ++D2;
1088
1089                        isPreviouslySatisfiedImportantDep =
1090                          (((*this)[D2] & DepGNow) != 0);
1091                      }
1092
1093                    found=true;
1094                  }
1095              }
1096             // this is a new dep if it was not found to be already
1097             // a important dep of the installed pacakge
1098             isNewImportantDep = !found;
1099          }
1100       }
1101       if(isNewImportantDep)
1102          if(DebugAutoInstall == true)
1103             std::clog << OutputInDepth(Depth) << "new important dependency: "
1104                       << Start.TargetPkg().Name() << std::endl;
1105       if(isPreviouslySatisfiedImportantDep)
1106         if(DebugAutoInstall == true)
1107           std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1108                     << Start.TargetPkg().Name() << std::endl;
1109
1110       // skip important deps if the package is already installed
1111       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
1112           && !isNewImportantDep && !isPreviouslySatisfiedImportantDep
1113           && !ForceImportantDeps)
1114          continue;
1115
1116       /* If we are in an or group locate the first or that can
1117          succeed. We have already cached this.. */
1118       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
1119          Start++;
1120
1121       /* This bit is for processing the possibilty of an install/upgrade
1122          fixing the problem */
1123       SPtrArray<Version *> List = Start.AllTargets();
1124       if (Start->Type != Dep::DpkgBreaks &&
1125           (DepState[Start->ID] & DepCVer) == DepCVer)
1126       {
1127          // Right, find the best version to install..
1128          Version **Cur = List;
1129          PkgIterator P = Start.TargetPkg();
1130          PkgIterator InstPkg(*Cache,0);
1131
1132          // See if there are direct matches (at the start of the list)
1133          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
1134          {
1135             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1136             if (PkgState[Pkg->ID].CandidateVer != *Cur)
1137                continue;
1138             InstPkg = Pkg;
1139             break;
1140          }
1141
1142          // Select the highest priority providing package
1143          if (InstPkg.end() == true)
1144          {
1145             pkgPrioSortList(*Cache,Cur);
1146             for (; *Cur != 0; Cur++)
1147             {
1148                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1149                if (PkgState[Pkg->ID].CandidateVer != *Cur)
1150                   continue;
1151                InstPkg = Pkg;
1152                break;
1153             }
1154          }
1155
1156          if (InstPkg.end() == false)
1157          {
1158             if(DebugAutoInstall == true)
1159                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1160                          << " as " << Start.DepType() << " of " << Pkg.Name()
1161                          << std::endl;
1162             // now check if we should consider it a automatic dependency or not
1163             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1164             {
1165                if(DebugAutoInstall == true)
1166                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1167                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1168                MarkInstall(InstPkg,true,Depth + 1, true);
1169             }
1170             else
1171             {
1172                // mark automatic dependency
1173                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1174                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1175                if (P->CurrentVer == 0)
1176                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1177             }
1178          }
1179          continue;
1180       }
1181
1182       /* For conflicts we just de-install the package and mark as auto,
1183          Conflicts may not have or groups.  For dpkg's Breaks we try to
1184          upgrade the package. */
1185       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
1186           Start->Type == Dep::DpkgBreaks)
1187       {
1188          for (Version **I = List; *I != 0; I++)
1189          {
1190             VerIterator Ver(*this,*I);
1191             PkgIterator Pkg = Ver.ParentPkg();
1192
1193             /* The List includes all packages providing this dependency,
1194                even providers which are not installed, so skip them. */
1195             if (PkgState[Pkg->ID].InstallVer == 0)
1196                continue;
1197
1198             if (PkgState[Pkg->ID].CandidateVer != *I &&
1199                 Start->Type == Dep::DpkgBreaks)
1200                MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
1201             else
1202                MarkDelete(Pkg,false,Depth + 1, false);
1203          }
1204          continue;
1205       }
1206    }
1207 }
1208                                                                         /*}}}*/
1209 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1210 // ---------------------------------------------------------------------
1211 /* The default implementation just honors dpkg hold
1212    But an application using this library can override this method
1213    to control the MarkInstall behaviour */
1214 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1215                               unsigned long Depth, bool FromUser)
1216 {
1217    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
1218    {
1219       if (DebugMarker == true)
1220          std::clog << OutputInDepth(Depth) << "Hold prevents MarkInstall of " << Pkg << " FU=" << FromUser << std::endl;
1221       return false;
1222    }
1223    return true;
1224 }
1225                                                                         /*}}}*/
1226 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1227 // ---------------------------------------------------------------------
1228 /* */
1229 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1230 {
1231    if (unlikely(Pkg.end() == true))
1232       return;
1233
1234    ActionGroup group(*this);
1235
1236    RemoveSizes(Pkg);
1237    RemoveStates(Pkg);
1238
1239    StateCache &P = PkgState[Pkg->ID];
1240    if (To == true)
1241       P.iFlags |= ReInstall;
1242    else
1243       P.iFlags &= ~ReInstall;
1244
1245    AddStates(Pkg);
1246    AddSizes(Pkg);
1247
1248    if (unlikely(Pkg.CurrentVer().end() == true))
1249       return;
1250
1251    SetReInstall(Pkg.Group().FindPkg("all"), To);
1252 }
1253                                                                         /*}}}*/
1254 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1255 // ---------------------------------------------------------------------
1256 /* */
1257 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer, bool const &Pseudo)
1258 {
1259    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1260    StateCache &P = PkgState[Pkg->ID];
1261
1262    if (P.CandidateVer == TargetVer)
1263       return;
1264
1265    ActionGroup group(*this);
1266
1267    RemoveSizes(Pkg);
1268    RemoveStates(Pkg);
1269
1270    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1271       P.InstallVer = (Version *)TargetVer;
1272    P.CandidateVer = (Version *)TargetVer;
1273    P.Update(Pkg,*this);
1274
1275    AddStates(Pkg);
1276    Update(Pkg);
1277    AddSizes(Pkg);
1278
1279 }
1280                                                                         /*}}}*/
1281 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1282 // ---------------------------------------------------------------------
1283 /* changes the candidate of a package and walks over all its dependencies
1284    to check if it needs to change the candidate of the dependency, too,
1285    to reach a installable versionstate */
1286 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1287                                         std::string const &TargetRel)
1288 {
1289    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1290    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1291 }
1292 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1293                                         std::string const &TargetRel,
1294                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1295 {
1296    ActionGroup group(*this);
1297    SetCandidateVersion(TargetVer);
1298
1299    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1300       return true;
1301
1302    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1303    // save the position of the last element we will not undo - if we have to
1304    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1305
1306    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1307    {
1308       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1309           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1310            IsImportantDep(D) == false))
1311          continue;
1312
1313       // walk over an or-group and check if we need to do anything
1314       // for simpilicity no or-group is handled as a or-group including one dependency
1315       pkgCache::DepIterator Start = D;
1316       bool itsFine = false;
1317       for (bool stillOr = true; stillOr == true; ++Start)
1318       {
1319          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1320          pkgCache::PkgIterator const P = Start.TargetPkg();
1321          // virtual packages can't be a solution
1322          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1323             continue;
1324          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1325          // no versioned dependency - but is it installable?
1326          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1327          {
1328             // Check if one of the providers is installable
1329             if (P->ProvidesList != 0)
1330             {
1331                pkgCache::PrvIterator Prv = P.ProvidesList();
1332                for (; Prv.end() == false; ++Prv)
1333                {
1334                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1335                   if (C.end() == true || C != Prv.OwnerVer() ||
1336                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1337                      continue;
1338                   break;
1339                }
1340                if (Prv.end() == true)
1341                   continue;
1342             }
1343             // no providers, so check if we have an installable candidate version
1344             else if (Cand.end() == true ||
1345                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1346                continue;
1347             itsFine = true;
1348             break;
1349          }
1350          if (Cand.end() == true)
1351             continue;
1352          // check if the current candidate is enough for the versioned dependency - and installable?
1353          if (VS().CheckDep(P.CandVersion(), Start->CompareOp, Start.TargetVer()) == true &&
1354              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1355          {
1356             itsFine = true;
1357             break;
1358          }
1359       }
1360
1361       if (itsFine == true) {
1362          // something in the or-group was fine, skip all other members
1363          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1364          continue;
1365       }
1366
1367       // walk again over the or-group and check each if a candidate switch would help
1368       itsFine = false;
1369       for (bool stillOr = true; stillOr == true; ++D)
1370       {
1371          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1372          // changing candidate will not help if the dependency is not versioned
1373          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1374          {
1375             if (stillOr == true)
1376                continue;
1377             break;
1378          }
1379
1380          pkgCache::VerIterator V;
1381          if (TargetRel == "newest")
1382             V = D.TargetPkg().VersionList();
1383          else
1384             V = Match.Find(D.TargetPkg());
1385
1386          // check if the version from this release could satisfy the dependency
1387          if (V.end() == true || VS().CheckDep(V.VerStr(), D->CompareOp, D.TargetVer()) == false)
1388          {
1389             if (stillOr == true)
1390                continue;
1391             break;
1392          }
1393
1394          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1395          if (V == oldCand)
1396          {
1397             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1398             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1399                  c != Changed.end(); ++c)
1400             {
1401                if (c->first->ParentPkg != V->ParentPkg)
1402                   continue;
1403                itsFine = true;
1404                break;
1405             }
1406          }
1407
1408          if (itsFine == false)
1409          {
1410             // change the candidate
1411             Changed.push_back(make_pair(oldCand, TargetVer));
1412             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1413             {
1414                if (stillOr == false)
1415                   break;
1416                // undo the candidate changing
1417                SetCandidateVersion(oldCand);
1418                Changed.pop_back();
1419                continue;
1420             }
1421             itsFine = true;
1422          }
1423
1424          // something in the or-group was fine, skip all other members
1425          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1426          break;
1427       }
1428
1429       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1430       {
1431          // undo all changes which aren't lead to a solution
1432          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1433               c != Changed.end(); ++c)
1434             SetCandidateVersion(c->first);
1435          Changed.erase(newChanged, Changed.end());
1436          return false;
1437       }
1438    }
1439    return true;
1440 }
1441                                                                         /*}}}*/
1442 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1443 // ---------------------------------------------------------------------
1444 /* */
1445 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1446 {
1447   StateCache &state = PkgState[Pkg->ID];
1448
1449   ActionGroup group(*this);
1450
1451   if(Auto)
1452     state.Flags |= Flag::Auto;
1453   else
1454     state.Flags &= ~Flag::Auto;
1455 }
1456                                                                         /*}}}*/
1457 // StateCache::Update - Compute the various static display things       /*{{{*/
1458 // ---------------------------------------------------------------------
1459 /* This is called whenever the Candidate version changes. */
1460 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1461 {
1462    // Some info
1463    VerIterator Ver = CandidateVerIter(Cache);
1464
1465    // Use a null string or the version string
1466    if (Ver.end() == true)
1467       CandVersion = "";
1468    else
1469       CandVersion = Ver.VerStr();
1470
1471    // Find the current version
1472    CurVersion = "";
1473    if (Pkg->CurrentVer != 0)
1474       CurVersion = Pkg.CurrentVer().VerStr();
1475
1476    // Strip off the epochs for display
1477    CurVersion = StripEpoch(CurVersion);
1478    CandVersion = StripEpoch(CandVersion);
1479
1480    // Figure out if its up or down or equal
1481    Status = Ver.CompareVer(Pkg.CurrentVer());
1482    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1483      Status = 2;
1484 }
1485                                                                         /*}}}*/
1486 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1487 // ---------------------------------------------------------------------
1488 /* */
1489 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1490 {
1491    if (Ver == 0)
1492       return 0;
1493
1494    // Strip any epoch
1495    for (const char *I = Ver; *I != 0; I++)
1496       if (*I == ':')
1497          return I + 1;
1498    return Ver;
1499 }
1500                                                                         /*}}}*/
1501 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1502 // ---------------------------------------------------------------------
1503 /* The default just returns the highest available version that is not
1504    a source and automatic. */
1505 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1506 {
1507    /* Not source/not automatic versions cannot be a candidate version
1508       unless they are already installed */
1509    VerIterator Last(*(pkgCache *)this,0);
1510
1511    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1512    {
1513       if (Pkg.CurrentVer() == I)
1514          return I;
1515
1516       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1517       {
1518          if ((J.File()->Flags & Flag::NotSource) != 0)
1519             continue;
1520
1521          /* Stash the highest version of a not-automatic source, we use it
1522             if there is nothing better */
1523          if ((J.File()->Flags & Flag::NotAutomatic) != 0 ||
1524              (J.File()->Flags & Flag::ButAutomaticUpgrades) != 0)
1525          {
1526             if (Last.end() == true)
1527                Last = I;
1528             continue;
1529          }
1530
1531          return I;
1532       }
1533    }
1534
1535    return Last;
1536 }
1537                                                                         /*}}}*/
1538 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1539 // ---------------------------------------------------------------------
1540 /* */
1541 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
1542 {
1543    if(Dep.IsCritical())
1544       return true;
1545    else if(Dep->Type == pkgCache::Dep::Recommends)
1546    {
1547       if ( _config->FindB("APT::Install-Recommends", false))
1548          return true;
1549       // we suport a special mode to only install-recommends for certain
1550       // sections
1551       // FIXME: this is a meant as a temporarly solution until the
1552       //        recommends are cleaned up
1553       const char *sec = Dep.ParentVer().Section();
1554       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1555          return true;
1556    }
1557    else if(Dep->Type == pkgCache::Dep::Suggests)
1558      return _config->FindB("APT::Install-Suggests", false);
1559
1560    return false;
1561 }
1562                                                                         /*}}}*/
1563 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1564 {
1565   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1566   if(f->wasConstructedSuccessfully())
1567     return f;
1568   else
1569     {
1570       delete f;
1571       return NULL;
1572     }
1573 }
1574                                                                         /*}}}*/
1575 bool pkgDepCache::MarkFollowsRecommends()
1576 {
1577   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1578 }
1579
1580 bool pkgDepCache::MarkFollowsSuggests()
1581 {
1582   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1583 }
1584
1585 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1586 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1587 {
1588    bool follow_recommends;
1589    bool follow_suggests;
1590    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1591
1592    // init the states
1593    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1594    {
1595       PkgState[p->ID].Marked  = false;
1596       PkgState[p->ID].Garbage = false;
1597
1598       // debug output
1599       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1600          std::clog << "AutoDep: " << p.FullName() << std::endl;
1601    }
1602
1603    // init vars
1604    follow_recommends = MarkFollowsRecommends();
1605    follow_suggests   = MarkFollowsSuggests();
1606
1607
1608
1609    // do the mark part, this is the core bit of the algorithm
1610    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1611    {
1612       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1613           (p->Flags & Flag::Essential) ||
1614           userFunc.InRootSet(p) ||
1615           // be nice even then a required package violates the policy (#583517)
1616           // and do the full mark process also for required packages
1617           (p.CurrentVer().end() != true &&
1618            p.CurrentVer()->Priority == pkgCache::State::Required))
1619       {
1620          // the package is installed (and set to keep)
1621          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1622             MarkPackage(p, p.CurrentVer(),
1623                         follow_recommends, follow_suggests);
1624          // the package is to be installed
1625          else if(PkgState[p->ID].Install())
1626             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1627                         follow_recommends, follow_suggests);
1628       }
1629    }
1630
1631    return true;
1632 }
1633                                                                         /*}}}*/
1634 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1635 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1636                               const pkgCache::VerIterator &ver,
1637                               bool const &follow_recommends,
1638                               bool const &follow_suggests)
1639 {
1640    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1641
1642    // if we are marked already we are done
1643    if(state.Marked)
1644       return;
1645
1646    VerIterator const currver = pkg.CurrentVer();
1647    VerIterator const instver = state.InstVerIter(*this);
1648
1649 #if 0
1650    VerIterator const candver = state.CandidateVerIter(*this);
1651
1652    // If a package was garbage-collected but is now being marked, we
1653    // should re-select it
1654    // For cases when a pkg is set to upgrade and this trigger the
1655    // removal of a no-longer used dependency.  if the pkg is set to
1656    // keep again later it will result in broken deps
1657    if(state.Delete() && state.RemoveReason = Unused)
1658    {
1659       if(ver==candver)
1660          mark_install(pkg, false, false, NULL);
1661       else if(ver==pkg.CurrentVer())
1662          MarkKeep(pkg, false, false);
1663
1664       instver=state.InstVerIter(*this);
1665    }
1666 #endif
1667
1668    // For packages that are not going to be removed, ignore versions
1669    // other than the InstVer.  For packages that are going to be
1670    // removed, ignore versions other than the current version.
1671    if(!(ver == instver && !instver.end()) &&
1672       !(ver == currver && instver.end() && !ver.end()))
1673       return;
1674
1675    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1676
1677    if(debug_autoremove)
1678      {
1679        std::clog << "Marking: " << pkg.FullName();
1680        if(!ver.end())
1681          std::clog << " " << ver.VerStr();
1682        if(!currver.end())
1683          std::clog << ", Curr=" << currver.VerStr();
1684        if(!instver.end())
1685          std::clog << ", Inst=" << instver.VerStr();
1686        std::clog << std::endl;
1687      }
1688
1689    state.Marked=true;
1690
1691    if(ver.end() == true)
1692       return;
1693
1694      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1695      {
1696         if(d->Type == Dep::Depends ||
1697            d->Type == Dep::PreDepends ||
1698            (follow_recommends &&
1699             d->Type == Dep::Recommends) ||
1700            (follow_suggests &&
1701             d->Type == Dep::Suggests))
1702         {
1703            // Try all versions of this package.
1704            for(VerIterator V = d.TargetPkg().VersionList();
1705                !V.end(); ++V)
1706            {
1707               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1708               {
1709                 if(debug_autoremove)
1710                   {
1711                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1712                               << " " << d.ParentVer().VerStr() << " "
1713                               << d.DepType() << " " << d.TargetPkg().FullName();
1714                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1715                       {
1716                         std::clog << " (" << d.CompType() << " "
1717                                   << d.TargetVer() << ")";
1718                       }
1719                     std::clog << std::endl;
1720                   }
1721                  MarkPackage(V.ParentPkg(), V,
1722                              follow_recommends, follow_suggests);
1723               }
1724            }
1725            // Now try virtual packages
1726            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1727                !prv.end(); ++prv)
1728            {
1729               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1730                                        d.TargetVer()))
1731               {
1732                 if(debug_autoremove)
1733                   {
1734                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1735                               << d.ParentVer().VerStr() << " "
1736                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1737                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1738                       {
1739                         std::clog << " (" << d.CompType() << " "
1740                                   << d.TargetVer() << ")";
1741                       }
1742                     std::clog << ", provided by "
1743                               << prv.OwnerPkg().FullName() << " "
1744                               << prv.OwnerVer().VerStr()
1745                               << std::endl;
1746                   }
1747
1748                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1749                              follow_recommends, follow_suggests);
1750               }
1751            }
1752         }
1753      }
1754 }
1755                                                                         /*}}}*/
1756 bool pkgDepCache::Sweep()                                               /*{{{*/
1757 {
1758    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1759
1760    // do the sweep
1761    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1762    {
1763      StateCache &state=PkgState[p->ID];
1764
1765      // skip required packages
1766      if (!p.CurrentVer().end() &&
1767          (p.CurrentVer()->Priority == pkgCache::State::Required))
1768         continue;
1769
1770      // if it is not marked and it is installed, it's garbage
1771      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1772      {
1773         state.Garbage=true;
1774         if(debug_autoremove)
1775            std::clog << "Garbage: " << p.FullName() << std::endl;
1776      }
1777   }
1778
1779    return true;
1780 }
1781                                                                         /*}}}*/