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