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