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() || Dep.IsNegative() == false)
 343    {
 344       PkgIterator Pkg = Dep.TargetPkg();
 345       // Check the base package
 346       if (Type == NowVersion && Pkg->CurrentVer != 0)
 347          if (VS().CheckDep(Pkg.CurrentVer().VerStr(),Dep->CompareOp,
 348                                  Dep.TargetVer()) == true)
 349             return true;
 350
 351       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 352          if (VS().CheckDep(PkgState[Pkg->ID].InstVerIter(*this).VerStr(),
 353                                  Dep->CompareOp,Dep.TargetVer()) == true)
 354             return true;
 355
 356       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 357          if (VS().CheckDep(PkgState[Pkg->ID].CandidateVerIter(*this).VerStr(),
 358                                  Dep->CompareOp,Dep.TargetVer()) == true)
 359             return true;
 360    }
 361
 362    if (Dep->Type == Dep::Obsoletes)
 363       return false;
 364
 365    // Check the providing packages
 366    PrvIterator P = Dep.TargetPkg().ProvidesList();
 367    PkgIterator Pkg = Dep.ParentPkg();
 368    for (; P.end() != true; P++)
 369    {
 370       /* Provides may never be applied against the same package (or group)
 371          if it is a conflicts. See the comment above. */
 372       if (P.OwnerPkg()->Group == Pkg->Group && Dep.IsNegative() == true)
 373          continue;
 374
 375       // Check if the provides is a hit
 376       if (Type == NowVersion)
 377       {
 378          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 379             continue;
 380       }
 381
 382       if (Type == InstallVersion)
 383       {
 384          StateCache &State = PkgState[P.OwnerPkg()->ID];
 385          if (State.InstallVer != (Version *)P.OwnerVer())
 386             continue;
 387       }
 388
 389       if (Type == CandidateVersion)
 390       {
 391          StateCache &State = PkgState[P.OwnerPkg()->ID];
 392          if (State.CandidateVer != (Version *)P.OwnerVer())
 393             continue;
 394       }
 395
 396       // Compare the versions.
 397       if (VS().CheckDep(P.ProvideVersion(),Dep->CompareOp,Dep.TargetVer()) == true)
 398       {
 399          Res = P.OwnerPkg();
 400          return true;
 401       }
 402    }
 403
 404    return false;
 405 }
 406                                                                         /*}}}*/
 407 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 408 // ---------------------------------------------------------------------
 409 /* Call with Mult = -1 to preform the inverse opration
 410    The Mult increases the complexity of the calulations here and is unused -
 411    or do we really have a usecase for removing the size of a package two
 412    times? So let us replace it with a simple bool and be done with it… */
 413 __deprecated void pkgDepCache::AddSizes(const PkgIterator &Pkg,signed long Mult)
 414 {
 415    StateCache &P = PkgState[Pkg->ID];
 416
 417    if (Pkg->VersionList == 0)
 418       return;
 419
 420    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 421        P.Keep() == true)
 422       return;
 423
 424    // Compute the size data
 425    if (P.NewInstall() == true)
 426    {
 427       iUsrSize += (signed long long)(Mult*P.InstVerIter(*this)->InstalledSize);
 428       iDownloadSize += (signed long long)(Mult*P.InstVerIter(*this)->Size);
 429       return;
 430    }
 431
 432    // Upgrading
 433    if (Pkg->CurrentVer != 0 &&
 434        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 435         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 436    {
 437       iUsrSize += (signed long long)(Mult*((signed long long)P.InstVerIter(*this)->InstalledSize -
 438                         (signed long long)Pkg.CurrentVer()->InstalledSize));
 439       iDownloadSize += (signed long long)(Mult*P.InstVerIter(*this)->Size);
 440       return;
 441    }
 442
 443    // Reinstall
 444    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 445        P.Delete() == false)
 446    {
 447       iDownloadSize += (signed long long)(Mult*P.InstVerIter(*this)->Size);
 448       return;
 449    }
 450
 451    // Removing
 452    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 453    {
 454       iUsrSize -= (signed long long)(Mult*Pkg.CurrentVer()->InstalledSize);
 455       return;
 456    }
 457 }
 458                                                                         /*}}}*/
 459 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 460 // ---------------------------------------------------------------------
 461 /* Call with Inverse = true to preform the inverse opration */
 462 void pkgDepCache::AddSizes(const PkgIterator &Pkg, bool const &Inverse)
 463 {
 464    StateCache &P = PkgState[Pkg->ID];
 465
 466    if (Pkg->VersionList == 0)
 467       return;
 468
 469    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 470        P.Keep() == true)
 471       return;
 472
 473    // Compute the size data
 474    if (P.NewInstall() == true)
 475    {
 476       if (Inverse == false) {
 477          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 478          iDownloadSize += P.InstVerIter(*this)->Size;
 479       } else {
 480          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 481          iDownloadSize -= P.InstVerIter(*this)->Size;
 482       }
 483       return;
 484    }
 485
 486    // Upgrading
 487    if (Pkg->CurrentVer != 0 &&
 488        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 489         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 490    {
 491       if (Inverse == false) {
 492          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 493          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 494          iDownloadSize += P.InstVerIter(*this)->Size;
 495       } else {
 496          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 497          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 498          iDownloadSize -= P.InstVerIter(*this)->Size;
 499       }
 500       return;
 501    }
 502
 503    // Reinstall
 504    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 505        P.Delete() == false)
 506    {
 507       if (Inverse == false)
 508          iDownloadSize += P.InstVerIter(*this)->Size;
 509       else
 510          iDownloadSize -= P.InstVerIter(*this)->Size;
 511       return;
 512    }
 513
 514    // Removing
 515    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 516    {
 517       if (Inverse == false)
 518          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 519       else
 520          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 521       return;
 522    }
 523 }
 524                                                                         /*}}}*/
 525 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 526 // ---------------------------------------------------------------------
 527 /* This routine is tricky to use, you must make sure that it is never
 528    called twice for the same package. This means the Remove/Add section
 529    should be as short as possible and not encompass any code that will
 530    calld Remove/Add itself. Remember, dependencies can be circular so
 531    while processing a dep for Pkg it is possible that Add/Remove
 532    will be called on Pkg */
 533 void pkgDepCache::AddStates(const PkgIterator &Pkg,int Add)
 534 {
 535    StateCache &State = PkgState[Pkg->ID];
 536
 537    // The Package is broken (either minimal dep or policy dep)
 538    if ((State.DepState & DepInstMin) != DepInstMin)
 539       iBrokenCount += Add;
 540    if ((State.DepState & DepInstPolicy) != DepInstPolicy)
 541       iPolicyBrokenCount += Add;
 542
 543    // Bad state
 544    if (Pkg.State() != PkgIterator::NeedsNothing)
 545       iBadCount += Add;
 546
 547    // Not installed
 548    if (Pkg->CurrentVer == 0)
 549    {
 550       if (State.Mode == ModeDelete &&
 551           (State.iFlags & Purge) == Purge && Pkg.Purge() == false)
 552          iDelCount += Add;
 553
 554       if (State.Mode == ModeInstall)
 555          iInstCount += Add;
 556       return;
 557    }
 558
 559    // Installed, no upgrade
 560    if (State.Status == 0)
 561    {
 562       if (State.Mode == ModeDelete)
 563          iDelCount += Add;
 564       else
 565          if ((State.iFlags & ReInstall) == ReInstall)
 566             iInstCount += Add;
 567
 568       return;
 569    }
 570
 571    // Alll 3 are possible
 572    if (State.Mode == ModeDelete)
 573       iDelCount += Add;
 574    if (State.Mode == ModeKeep)
 575       iKeepCount += Add;
 576    if (State.Mode == ModeInstall)
 577       iInstCount += Add;
 578 }
 579                                                                         /*}}}*/
 580 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 581 // ---------------------------------------------------------------------
 582 /* The or group results are stored in the last item of the or group. This
 583    allows easy detection of the state of a whole or'd group. */
 584 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 585 {
 586    unsigned char Group = 0;
 587
 588    for (DepIterator D = V.DependsList(); D.end() != true; D++)
 589    {
 590       // Build the dependency state.
 591       unsigned char &State = DepState[D->ID];
 592
 593       /* Invert for Conflicts. We have to do this twice to get the
 594          right sense for a conflicts group */
 595       if (D.IsNegative() == true)
 596          State = ~State;
 597
 598       // Add to the group if we are within an or..
 599       State &= 0x7;
 600       Group |= State;
 601       State |= Group << 3;
 602       if ((D->CompareOp & Dep::Or) != Dep::Or)
 603          Group = 0;
 604
 605       // Invert for Conflicts
 606       if (D.IsNegative() == true)
 607          State = ~State;
 608    }
 609 }
 610                                                                         /*}}}*/
 611 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 612 // ---------------------------------------------------------------------
 613 /* This is used to run over a dependency list and determine the dep
 614    state of the list, filtering it through both a Min check and a Policy
 615    check. The return result will have SetMin/SetPolicy low if a check
 616    fails. It uses the DepState cache for it's computations. */
 617 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 618                                        unsigned char SetMin,
 619                                        unsigned char SetPolicy)
 620 {
 621    unsigned char Dep = 0xFF;
 622
 623    while (D.end() != true)
 624    {
 625       // Compute a single dependency element (glob or)
 626       DepIterator Start = D;
 627       unsigned char State = 0;
 628       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 629       {
 630          State |= DepState[D->ID];
 631          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 632       }
 633
 634       // Minimum deps that must be satisfied to have a working package
 635       if (Start.IsCritical() == true)
 636          if ((State & Check) != Check)
 637             Dep &= ~SetMin;
 638
 639       // Policy deps that must be satisfied to install the package
 640       if (IsImportantDep(Start) == true &&
 641           (State & Check) != Check)
 642          Dep &= ~SetPolicy;
 643    }
 644
 645    return Dep;
 646 }
 647                                                                         /*}}}*/
 648 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 649 // ---------------------------------------------------------------------
 650 /* This is the main dependency computation bit. It computes the 3 main
 651    results for a dependencys, Now, Install and Candidate. Callers must
 652    invert the result if dealing with conflicts. */
 653 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 654 {
 655    unsigned char State = 0;
 656
 657    if (CheckDep(D,NowVersion) == true)
 658       State |= DepNow;
 659    if (CheckDep(D,InstallVersion) == true)
 660       State |= DepInstall;
 661    if (CheckDep(D,CandidateVersion) == true)
 662       State |= DepCVer;
 663
 664    return State;
 665 }
 666                                                                         /*}}}*/
 667 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 668 // ---------------------------------------------------------------------
 669 /* This determines the combined dependency representation of a package
 670    for its two states now and install. This is done by using the pre-generated
 671    dependency information. */
 672 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 673 {
 674    // Empty deps are always true
 675    StateCache &State = PkgState[Pkg->ID];
 676    State.DepState = 0xFF;
 677
 678    // Check the Current state
 679    if (Pkg->CurrentVer != 0)
 680    {
 681       DepIterator D = Pkg.CurrentVer().DependsList();
 682       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 683    }
 684
 685    /* Check the candidate state. We do not compare against the whole as
 686       a candidate state but check the candidate version against the
 687       install states */
 688    if (State.CandidateVer != 0)
 689    {
 690       DepIterator D = State.CandidateVerIter(*this).DependsList();
 691       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 692    }
 693
 694    // Check target state which can only be current or installed
 695    if (State.InstallVer != 0)
 696    {
 697       DepIterator D = State.InstVerIter(*this).DependsList();
 698       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 699    }
 700 }
 701                                                                         /*}}}*/
 702 // DepCache::Update - Figure out all the state information              /*{{{*/
 703 // ---------------------------------------------------------------------
 704 /* This will figure out the state of all the packages and all the
 705    dependencies based on the current policy. */
 706 void pkgDepCache::Update(OpProgress *Prog)
 707 {
 708    iUsrSize = 0;
 709    iDownloadSize = 0;
 710    iDelCount = 0;
 711    iInstCount = 0;
 712    iKeepCount = 0;
 713    iBrokenCount = 0;
 714    iBadCount = 0;
 715
 716    // Perform the depends pass
 717    int Done = 0;
 718    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 719    {
 720       if (Prog != 0 && Done%20 == 0)
 721          Prog->Progress(Done);
 722       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 723       {
 724          unsigned char Group = 0;
 725
 726          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 727          {
 728             // Build the dependency state.
 729             unsigned char &State = DepState[D->ID];
 730             State = DependencyState(D);
 731
 732             // Add to the group if we are within an or..
 733             Group |= State;
 734             State |= Group << 3;
 735             if ((D->CompareOp & Dep::Or) != Dep::Or)
 736                Group = 0;
 737
 738             // Invert for Conflicts
 739             if (D.IsNegative() == true)
 740                State = ~State;
 741          }
 742       }
 743
 744       // Compute the package dependency state and size additions
 745       AddSizes(I);
 746       UpdateVerState(I);
 747       AddStates(I);
 748    }
 749
 750    if (Prog != 0)
 751       Prog->Progress(Done);
 752
 753    readStateFile(Prog);
 754 }
 755                                                                         /*}}}*/
 756 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 757 // ---------------------------------------------------------------------
 758 /* This is a helper for update that only does the dep portion of the scan.
 759    It is mainly meant to scan reverse dependencies. */
 760 void pkgDepCache::Update(DepIterator D)
 761 {
 762    // Update the reverse deps
 763    for (;D.end() != true; D++)
 764    {
 765       unsigned char &State = DepState[D->ID];
 766       State = DependencyState(D);
 767
 768       // Invert for Conflicts
 769       if (D.IsNegative() == true)
 770          State = ~State;
 771
 772       RemoveStates(D.ParentPkg());
 773       BuildGroupOrs(D.ParentVer());
 774       UpdateVerState(D.ParentPkg());
 775       AddStates(D.ParentPkg());
 776    }
 777 }
 778                                                                         /*}}}*/
 779 // DepCache::Update - Update the related deps of a package              /*{{{*/
 780 // ---------------------------------------------------------------------
 781 /* This is called whenever the state of a package changes. It updates
 782    all cached dependencies related to this package. */
 783 void pkgDepCache::Update(PkgIterator const &Pkg)
 784 {
 785    // Recompute the dep of the package
 786    RemoveStates(Pkg);
 787    UpdateVerState(Pkg);
 788    AddStates(Pkg);
 789
 790    // Update the reverse deps
 791    Update(Pkg.RevDependsList());
 792
 793    // Update the provides map for the current ver
 794    if (Pkg->CurrentVer != 0)
 795       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 796            P.end() != true; P++)
 797          Update(P.ParentPkg().RevDependsList());
 798
 799    // Update the provides map for the candidate ver
 800    if (PkgState[Pkg->ID].CandidateVer != 0)
 801       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 802            P.end() != true; P++)
 803          Update(P.ParentPkg().RevDependsList());
 804 }
 805                                                                         /*}}}*/
 806 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 807 // ---------------------------------------------------------------------
 808 /* */
 809 void pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 810                            unsigned long Depth)
 811 {
 812    if (IsModeChangeOk(ModeKeep, Pkg, Depth, FromUser) == false)
 813       return;
 814
 815    /* Reject an attempt to keep a non-source broken installed package, those
 816       must be upgraded */
 817    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 818        Pkg.CurrentVer().Downloadable() == false)
 819       return;
 820
 821    /* We changed the soft state all the time so the UI is a bit nicer
 822       to use */
 823    StateCache &P = PkgState[Pkg->ID];
 824
 825    // Check that it is not already kept
 826    if (P.Mode == ModeKeep)
 827       return;
 828
 829    if (Soft == true)
 830       P.iFlags |= AutoKept;
 831    else
 832       P.iFlags &= ~AutoKept;
 833
 834    ActionGroup group(*this);
 835
 836 #if 0 // reseting the autoflag here means we lose the
 837       // auto-mark information if a user selects a package for removal
 838       // but changes  his mind then and sets it for keep again
 839       // - this makes sense as default when all Garbage dependencies
 840       //   are automatically marked for removal (as aptitude does).
 841       //   setting a package for keep then makes it no longer autoinstalled
 842       //   for all other use-case this action is rather suprising
 843    if(FromUser && !P.Marked)
 844      P.Flags &= ~Flag::Auto;
 845 #endif
 846
 847    if (DebugMarker == true)
 848       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 849
 850    RemoveSizes(Pkg);
 851    RemoveStates(Pkg);
 852
 853    P.Mode = ModeKeep;
 854    if (Pkg->CurrentVer == 0)
 855       P.InstallVer = 0;
 856    else
 857       P.InstallVer = Pkg.CurrentVer();
 858
 859    AddStates(Pkg);
 860
 861    Update(Pkg);
 862
 863    AddSizes(Pkg);
 864 }
 865                                                                         /*}}}*/
 866 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 867 // ---------------------------------------------------------------------
 868 /* */
 869 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 870                              unsigned long Depth, bool FromUser)
 871 {
 872    if (IsModeChangeOk(ModeDelete, Pkg, Depth, FromUser) == false)
 873       return;
 874
 875    StateCache &P = PkgState[Pkg->ID];
 876
 877    // Check that it is not already marked for delete
 878    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 879        (Pkg.Purge() == true || rPurge == false))
 880       return;
 881
 882    // check if we are allowed to remove the package
 883    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
 884       return;
 885
 886    P.iFlags &= ~(AutoKept | Purge);
 887    if (rPurge == true)
 888       P.iFlags |= Purge;
 889
 890    ActionGroup group(*this);
 891
 892    if (DebugMarker == true)
 893       std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << Pkg << " FU=" << FromUser << std::endl;
 894
 895    RemoveSizes(Pkg);
 896    RemoveStates(Pkg);
 897
 898    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 899       P.Mode = ModeKeep;
 900    else
 901       P.Mode = ModeDelete;
 902    P.InstallVer = 0;
 903
 904    AddStates(Pkg);
 905    Update(Pkg);
 906    AddSizes(Pkg);
 907
 908 }
 909                                                                         /*}}}*/
 910 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 911 // ---------------------------------------------------------------------
 912 /* The default implementation tries to prevent deletion of install requests.
 913    dpkg holds are enforced by the private IsModeChangeOk */
 914 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 915                               unsigned long Depth, bool FromUser)
 916 {
 917    if (FromUser == false && Pkg->CurrentVer == 0)
 918    {
 919       StateCache &P = PkgState[Pkg->ID];
 920       // Status == 2 means this applies for new installs only
 921       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
 922       {
 923          if (DebugMarker == true)
 924             std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << Pkg << std::endl;
 925          return false;
 926       }
 927    }
 928    return true;
 929 }
 930                                                                         /*}}}*/
 931 // DepCache::IsModeChangeOk - check if it is ok to change the mode      /*{{{*/
 932 // ---------------------------------------------------------------------
 933 /* this is used by all Mark methods on the very first line to check sanity
 934    and prevents mode changes for packages on hold for example.
 935    If you want to check Mode specific stuff you can use the virtual public
 936    Is<Mode>Ok methods instead */
 937 char const* PrintMode(char const mode)
 938 {
 939          switch (mode)
 940          {
 941          case pkgDepCache::ModeInstall: return "Install";
 942          case pkgDepCache::ModeKeep: return "Keep";
 943          case pkgDepCache::ModeDelete: return "Delete";
 944          default: return "UNKNOWN";
 945          }
 946 }
 947 bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
 948                                  unsigned long const Depth, bool const FromUser)
 949 {
 950    // we are not trying to hard…
 951    if (unlikely(Depth > 100))
 952       return false;
 953
 954    // general sanity
 955    if (unlikely(Pkg.end() == true || Pkg->VersionList == 0))
 956       return false;
 957
 958    // the user is always right
 959    if (FromUser == true)
 960       return true;
 961
 962    StateCache &P = PkgState[Pkg->ID];
 963
 964    // if previous state was set by user only user can reset it
 965    if ((P.iFlags & Protected) == Protected)
 966    {
 967       if (unlikely(DebugMarker == true) && P.Mode != mode)
 968          std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
 969                    << " of " << Pkg << " as its mode (" << PrintMode(P.Mode)
 970                    << ") is protected" << std::endl;
 971       return false;
 972    }
 973    // enforce dpkg holds
 974    else if (mode != ModeKeep && Pkg->SelectedState == pkgCache::State::Hold &&
 975             _config->FindB("APT::Ignore-Hold",false) == false)
 976    {
 977       if (unlikely(DebugMarker == true) && P.Mode != mode)
 978          std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
 979                    << " of " << Pkg << std::endl;
 980       return false;
 981    }
 982
 983    return true;
 984 }
 985                                                                         /*}}}*/
 986 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 987 // ---------------------------------------------------------------------
 988 /* */
 989 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 990                               unsigned long Depth, bool FromUser,
 991                               bool ForceImportantDeps)
 992 {
 993    if (IsModeChangeOk(ModeInstall, Pkg, Depth, FromUser) == false)
 994       return;
 995
 996    StateCache &P = PkgState[Pkg->ID];
 997
 998    // See if there is even any possible instalation candidate
 999    if (P.CandidateVer == 0)
1000       return;
1001
1002    /* Check that it is not already marked for install and that it can be
1003       installed */
1004    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1005        (P.Mode == ModeInstall ||
1006         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1007    {
1008       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1009          MarkKeep(Pkg, false, FromUser, Depth+1);
1010       return;
1011    }
1012
1013    // check if we are allowed to install the package
1014    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1015       return;
1016
1017    ActionGroup group(*this);
1018    P.iFlags &= ~AutoKept;
1019
1020    /* Target the candidate version and remove the autoflag. We reset the
1021       autoflag below if this was called recursively. Otherwise the user
1022       should have the ability to de-auto a package by changing its state */
1023    RemoveSizes(Pkg);
1024    RemoveStates(Pkg);
1025
1026    P.Mode = ModeInstall;
1027    P.InstallVer = P.CandidateVer;
1028
1029    if(FromUser)
1030      {
1031        // Set it to manual if it's a new install or already installed,
1032        // but only if its not marked by the autoremover (aptitude depend on this behavior)
1033        // or if we do automatic installation (aptitude never does it)
1034        if(P.Status == 2 || (Pkg->CurrentVer != 0 && (AutoInst == true || P.Marked == false)))
1035          P.Flags &= ~Flag::Auto;
1036      }
1037    else
1038      {
1039        // Set it to auto if this is a new install.
1040        if(P.Status == 2)
1041          P.Flags |= Flag::Auto;
1042      }
1043    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1044       P.Mode = ModeKeep;
1045
1046    AddStates(Pkg);
1047    Update(Pkg);
1048    AddSizes(Pkg);
1049
1050    if (AutoInst == false)
1051       return;
1052
1053    if (DebugMarker == true)
1054       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1055
1056    DepIterator Dep = P.InstVerIter(*this).DependsList();
1057    for (; Dep.end() != true;)
1058    {
1059       // Grok or groups
1060       DepIterator Start = Dep;
1061       bool Result = true;
1062       unsigned Ors = 0;
1063       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
1064       {
1065          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1066
1067          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1068             Result = false;
1069       }
1070
1071       // Dep is satisfied okay.
1072       if (Result == false)
1073          continue;
1074
1075       /* Check if this dep should be consider for install. If it is a user
1076          defined important dep and we are installed a new package then
1077          it will be installed. Otherwise we only check for important
1078          deps that have changed from the installed version
1079       */
1080       if (IsImportantDep(Start) == false)
1081          continue;
1082
1083       /* If we are in an or group locate the first or that can
1084          succeed. We have already cached this.. */
1085       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1086          ++Start;
1087       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
1088       {
1089          if(DebugAutoInstall == true)
1090             std::clog << OutputInDepth(Depth) << Start << " can't be satisfied!" << std::endl;
1091          if (Start.IsCritical() == false)
1092             continue;
1093          // if the dependency was critical, we can't install it, so remove it again
1094          MarkDelete(Pkg,false,Depth + 1, false);
1095          return;
1096       }
1097
1098       /* Check if any ImportantDep() (but not Critical) were added
1099        * since we installed the package.  Also check for deps that
1100        * were satisfied in the past: for instance, if a version
1101        * restriction in a Recommends was tightened, upgrading the
1102        * package should follow that Recommends rather than causing the
1103        * dependency to be removed. (bug #470115)
1104        */
1105       if (Pkg->CurrentVer != 0 && ForceImportantDeps == false && Start.IsCritical() == false)
1106       {
1107          bool isNewImportantDep = true;
1108          bool isPreviouslySatisfiedImportantDep = false;
1109          for (DepIterator D = Pkg.CurrentVer().DependsList(); D.end() != true; ++D)
1110          {
1111             //FIXME: Should we handle or-group better here?
1112             // We do not check if the package we look for is part of the same or-group
1113             // we might find while searching, but could that really be a problem?
1114             if (D.IsCritical() == true || IsImportantDep(D) == false ||
1115                 Start.TargetPkg() != D.TargetPkg())
1116                continue;
1117
1118             isNewImportantDep = false;
1119
1120             while ((D->CompareOp & Dep::Or) != 0)
1121                ++D;
1122
1123             isPreviouslySatisfiedImportantDep = (((*this)[D] & DepGNow) != 0);
1124             if (isPreviouslySatisfiedImportantDep == true)
1125                break;
1126          }
1127
1128          if(isNewImportantDep == true)
1129          {
1130             if (DebugAutoInstall == true)
1131                std::clog << OutputInDepth(Depth) << "new important dependency: "
1132                          << Start.TargetPkg().FullName() << std::endl;
1133          }
1134          else if(isPreviouslySatisfiedImportantDep == true)
1135          {
1136             if (DebugAutoInstall == true)
1137                std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1138                          << Start.TargetPkg().FullName() << std::endl;
1139          }
1140          else
1141          {
1142             if (DebugAutoInstall == true)
1143                std::clog << OutputInDepth(Depth) << "ignore old unsatisfied important dependency on "
1144                          << Start.TargetPkg().FullName() << std::endl;
1145             continue;
1146          }
1147       }
1148
1149       /* This bit is for processing the possibilty of an install/upgrade
1150          fixing the problem */
1151       SPtrArray<Version *> List = Start.AllTargets();
1152       if (Start->Type != Dep::DpkgBreaks &&
1153           (DepState[Start->ID] & DepCVer) == DepCVer)
1154       {
1155          // Right, find the best version to install..
1156          Version **Cur = List;
1157          PkgIterator P = Start.TargetPkg();
1158          PkgIterator InstPkg(*Cache,0);
1159
1160          // See if there are direct matches (at the start of the list)
1161          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
1162          {
1163             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1164             if (PkgState[Pkg->ID].CandidateVer != *Cur)
1165                continue;
1166             InstPkg = Pkg;
1167             break;
1168          }
1169
1170          // Select the highest priority providing package
1171          if (InstPkg.end() == true)
1172          {
1173             pkgPrioSortList(*Cache,Cur);
1174             for (; *Cur != 0; Cur++)
1175             {
1176                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1177                if (PkgState[Pkg->ID].CandidateVer != *Cur)
1178                   continue;
1179                InstPkg = Pkg;
1180                break;
1181             }
1182          }
1183
1184          if (InstPkg.end() == false)
1185          {
1186             if(DebugAutoInstall == true)
1187                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1188                          << " as " << Start.DepType() << " of " << Pkg.Name()
1189                          << std::endl;
1190             // now check if we should consider it a automatic dependency or not
1191             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1192             {
1193                if(DebugAutoInstall == true)
1194                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1195                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1196                MarkInstall(InstPkg,true,Depth + 1, true);
1197             }
1198             else
1199             {
1200                // mark automatic dependency
1201                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1202                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1203                if (P->CurrentVer == 0)
1204                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1205             }
1206          }
1207          continue;
1208       }
1209
1210       /* For conflicts we just de-install the package and mark as auto,
1211          Conflicts may not have or groups.  For dpkg's Breaks we try to
1212          upgrade the package. */
1213       if (Start.IsNegative() == true)
1214       {
1215          for (Version **I = List; *I != 0; I++)
1216          {
1217             VerIterator Ver(*this,*I);
1218             PkgIterator Pkg = Ver.ParentPkg();
1219
1220             /* The List includes all packages providing this dependency,
1221                even providers which are not installed, so skip them. */
1222             if (PkgState[Pkg->ID].InstallVer == 0)
1223                continue;
1224
1225             if (PkgState[Pkg->ID].CandidateVer != *I &&
1226                 Start->Type == Dep::DpkgBreaks)
1227                MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
1228             else
1229                MarkDelete(Pkg,false,Depth + 1, false);
1230          }
1231          continue;
1232       }
1233    }
1234 }
1235                                                                         /*}}}*/
1236 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1237 // ---------------------------------------------------------------------
1238 /* The default implementation does nothing.
1239    dpkg holds are enforced by the private IsModeChangeOk */
1240 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1241                               unsigned long Depth, bool FromUser)
1242 {
1243    return true;
1244 }
1245                                                                         /*}}}*/
1246 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1247 // ---------------------------------------------------------------------
1248 /* */
1249 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1250 {
1251    if (unlikely(Pkg.end() == true))
1252       return;
1253
1254    ActionGroup group(*this);
1255
1256    RemoveSizes(Pkg);
1257    RemoveStates(Pkg);
1258
1259    StateCache &P = PkgState[Pkg->ID];
1260    if (To == true)
1261       P.iFlags |= ReInstall;
1262    else
1263       P.iFlags &= ~ReInstall;
1264
1265    AddStates(Pkg);
1266    AddSizes(Pkg);
1267 }
1268                                                                         /*}}}*/
1269 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1270 // ---------------------------------------------------------------------
1271 /* */
1272 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer, bool const &Pseudo)
1273 {
1274    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1275    StateCache &P = PkgState[Pkg->ID];
1276
1277    if (P.CandidateVer == TargetVer)
1278       return;
1279
1280    ActionGroup group(*this);
1281
1282    RemoveSizes(Pkg);
1283    RemoveStates(Pkg);
1284
1285    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1286       P.InstallVer = (Version *)TargetVer;
1287    P.CandidateVer = (Version *)TargetVer;
1288    P.Update(Pkg,*this);
1289
1290    AddStates(Pkg);
1291    Update(Pkg);
1292    AddSizes(Pkg);
1293
1294 }
1295                                                                         /*}}}*/
1296 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1297 // ---------------------------------------------------------------------
1298 /* changes the candidate of a package and walks over all its dependencies
1299    to check if it needs to change the candidate of the dependency, too,
1300    to reach a installable versionstate */
1301 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1302                                         std::string const &TargetRel)
1303 {
1304    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1305    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1306 }
1307 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1308                                         std::string const &TargetRel,
1309                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1310 {
1311    ActionGroup group(*this);
1312    SetCandidateVersion(TargetVer);
1313
1314    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1315       return true;
1316
1317    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1318    // save the position of the last element we will not undo - if we have to
1319    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1320
1321    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1322    {
1323       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1324           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1325            IsImportantDep(D) == false))
1326          continue;
1327
1328       // walk over an or-group and check if we need to do anything
1329       // for simpilicity no or-group is handled as a or-group including one dependency
1330       pkgCache::DepIterator Start = D;
1331       bool itsFine = false;
1332       for (bool stillOr = true; stillOr == true; ++Start)
1333       {
1334          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1335          pkgCache::PkgIterator const P = Start.TargetPkg();
1336          // virtual packages can't be a solution
1337          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1338             continue;
1339          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1340          // no versioned dependency - but is it installable?
1341          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1342          {
1343             // Check if one of the providers is installable
1344             if (P->ProvidesList != 0)
1345             {
1346                pkgCache::PrvIterator Prv = P.ProvidesList();
1347                for (; Prv.end() == false; ++Prv)
1348                {
1349                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1350                   if (C.end() == true || C != Prv.OwnerVer() ||
1351                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1352                      continue;
1353                   break;
1354                }
1355                if (Prv.end() == true)
1356                   continue;
1357             }
1358             // no providers, so check if we have an installable candidate version
1359             else if (Cand.end() == true ||
1360                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1361                continue;
1362             itsFine = true;
1363             break;
1364          }
1365          if (Cand.end() == true)
1366             continue;
1367          // check if the current candidate is enough for the versioned dependency - and installable?
1368          if (VS().CheckDep(P.CandVersion(), Start->CompareOp, Start.TargetVer()) == true &&
1369              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1370          {
1371             itsFine = true;
1372             break;
1373          }
1374       }
1375
1376       if (itsFine == true) {
1377          // something in the or-group was fine, skip all other members
1378          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1379          continue;
1380       }
1381
1382       // walk again over the or-group and check each if a candidate switch would help
1383       itsFine = false;
1384       for (bool stillOr = true; stillOr == true; ++D)
1385       {
1386          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1387          // changing candidate will not help if the dependency is not versioned
1388          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1389          {
1390             if (stillOr == true)
1391                continue;
1392             break;
1393          }
1394
1395          pkgCache::VerIterator V;
1396          if (TargetRel == "newest")
1397             V = D.TargetPkg().VersionList();
1398          else
1399             V = Match.Find(D.TargetPkg());
1400
1401          // check if the version from this release could satisfy the dependency
1402          if (V.end() == true || VS().CheckDep(V.VerStr(), D->CompareOp, D.TargetVer()) == false)
1403          {
1404             if (stillOr == true)
1405                continue;
1406             break;
1407          }
1408
1409          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1410          if (V == oldCand)
1411          {
1412             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1413             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1414                  c != Changed.end(); ++c)
1415             {
1416                if (c->first->ParentPkg != V->ParentPkg)
1417                   continue;
1418                itsFine = true;
1419                break;
1420             }
1421          }
1422
1423          if (itsFine == false)
1424          {
1425             // change the candidate
1426             Changed.push_back(make_pair(oldCand, TargetVer));
1427             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1428             {
1429                if (stillOr == false)
1430                   break;
1431                // undo the candidate changing
1432                SetCandidateVersion(oldCand);
1433                Changed.pop_back();
1434                continue;
1435             }
1436             itsFine = true;
1437          }
1438
1439          // something in the or-group was fine, skip all other members
1440          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1441          break;
1442       }
1443
1444       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1445       {
1446          // undo all changes which aren't lead to a solution
1447          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1448               c != Changed.end(); ++c)
1449             SetCandidateVersion(c->first);
1450          Changed.erase(newChanged, Changed.end());
1451          return false;
1452       }
1453    }
1454    return true;
1455 }
1456                                                                         /*}}}*/
1457 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1458 // ---------------------------------------------------------------------
1459 /* */
1460 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1461 {
1462   StateCache &state = PkgState[Pkg->ID];
1463
1464   ActionGroup group(*this);
1465
1466   if(Auto)
1467     state.Flags |= Flag::Auto;
1468   else
1469     state.Flags &= ~Flag::Auto;
1470 }
1471                                                                         /*}}}*/
1472 // StateCache::Update - Compute the various static display things       /*{{{*/
1473 // ---------------------------------------------------------------------
1474 /* This is called whenever the Candidate version changes. */
1475 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1476 {
1477    // Some info
1478    VerIterator Ver = CandidateVerIter(Cache);
1479
1480    // Use a null string or the version string
1481    if (Ver.end() == true)
1482       CandVersion = "";
1483    else
1484       CandVersion = Ver.VerStr();
1485
1486    // Find the current version
1487    CurVersion = "";
1488    if (Pkg->CurrentVer != 0)
1489       CurVersion = Pkg.CurrentVer().VerStr();
1490
1491    // Strip off the epochs for display
1492    CurVersion = StripEpoch(CurVersion);
1493    CandVersion = StripEpoch(CandVersion);
1494
1495    // Figure out if its up or down or equal
1496    Status = Ver.CompareVer(Pkg.CurrentVer());
1497    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1498      Status = 2;
1499 }
1500                                                                         /*}}}*/
1501 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1502 // ---------------------------------------------------------------------
1503 /* */
1504 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1505 {
1506    if (Ver == 0)
1507       return 0;
1508
1509    // Strip any epoch
1510    for (const char *I = Ver; *I != 0; I++)
1511       if (*I == ':')
1512          return I + 1;
1513    return Ver;
1514 }
1515                                                                         /*}}}*/
1516 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1517 // ---------------------------------------------------------------------
1518 /* The default just returns the highest available version that is not
1519    a source and automatic. */
1520 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1521 {
1522    /* Not source/not automatic versions cannot be a candidate version
1523       unless they are already installed */
1524    VerIterator Last(*(pkgCache *)this,0);
1525
1526    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1527    {
1528       if (Pkg.CurrentVer() == I)
1529          return I;
1530
1531       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1532       {
1533          if ((J.File()->Flags & Flag::NotSource) != 0)
1534             continue;
1535
1536          /* Stash the highest version of a not-automatic source, we use it
1537             if there is nothing better */
1538          if ((J.File()->Flags & Flag::NotAutomatic) != 0 ||
1539              (J.File()->Flags & Flag::ButAutomaticUpgrades) != 0)
1540          {
1541             if (Last.end() == true)
1542                Last = I;
1543             continue;
1544          }
1545
1546          return I;
1547       }
1548    }
1549
1550    return Last;
1551 }
1552                                                                         /*}}}*/
1553 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1554 // ---------------------------------------------------------------------
1555 /* */
1556 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
1557 {
1558    if(Dep.IsCritical())
1559       return true;
1560    else if(Dep->Type == pkgCache::Dep::Recommends)
1561    {
1562       if ( _config->FindB("APT::Install-Recommends", false))
1563          return true;
1564       // we suport a special mode to only install-recommends for certain
1565       // sections
1566       // FIXME: this is a meant as a temporarly solution until the
1567       //        recommends are cleaned up
1568       const char *sec = Dep.ParentVer().Section();
1569       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1570          return true;
1571    }
1572    else if(Dep->Type == pkgCache::Dep::Suggests)
1573      return _config->FindB("APT::Install-Suggests", false);
1574
1575    return false;
1576 }
1577                                                                         /*}}}*/
1578 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1579 {
1580   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1581   if(f->wasConstructedSuccessfully())
1582     return f;
1583   else
1584     {
1585       delete f;
1586       return NULL;
1587     }
1588 }
1589                                                                         /*}}}*/
1590 bool pkgDepCache::MarkFollowsRecommends()
1591 {
1592   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1593 }
1594
1595 bool pkgDepCache::MarkFollowsSuggests()
1596 {
1597   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1598 }
1599
1600 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1601 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1602 {
1603    bool follow_recommends;
1604    bool follow_suggests;
1605    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1606
1607    // init the states
1608    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1609    {
1610       PkgState[p->ID].Marked  = false;
1611       PkgState[p->ID].Garbage = false;
1612
1613       // debug output
1614       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1615          std::clog << "AutoDep: " << p.FullName() << std::endl;
1616    }
1617
1618    // init vars
1619    follow_recommends = MarkFollowsRecommends();
1620    follow_suggests   = MarkFollowsSuggests();
1621
1622
1623
1624    // do the mark part, this is the core bit of the algorithm
1625    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1626    {
1627       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1628           (p->Flags & Flag::Essential) ||
1629           userFunc.InRootSet(p) ||
1630           // be nice even then a required package violates the policy (#583517)
1631           // and do the full mark process also for required packages
1632           (p.CurrentVer().end() != true &&
1633            p.CurrentVer()->Priority == pkgCache::State::Required))
1634       {
1635          // the package is installed (and set to keep)
1636          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1637             MarkPackage(p, p.CurrentVer(),
1638                         follow_recommends, follow_suggests);
1639          // the package is to be installed
1640          else if(PkgState[p->ID].Install())
1641             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1642                         follow_recommends, follow_suggests);
1643       }
1644    }
1645
1646    return true;
1647 }
1648                                                                         /*}}}*/
1649 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1650 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1651                               const pkgCache::VerIterator &ver,
1652                               bool const &follow_recommends,
1653                               bool const &follow_suggests)
1654 {
1655    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1656
1657    // if we are marked already we are done
1658    if(state.Marked)
1659       return;
1660
1661    VerIterator const currver = pkg.CurrentVer();
1662    VerIterator const instver = state.InstVerIter(*this);
1663
1664 #if 0
1665    VerIterator const candver = state.CandidateVerIter(*this);
1666
1667    // If a package was garbage-collected but is now being marked, we
1668    // should re-select it
1669    // For cases when a pkg is set to upgrade and this trigger the
1670    // removal of a no-longer used dependency.  if the pkg is set to
1671    // keep again later it will result in broken deps
1672    if(state.Delete() && state.RemoveReason = Unused)
1673    {
1674       if(ver==candver)
1675          mark_install(pkg, false, false, NULL);
1676       else if(ver==pkg.CurrentVer())
1677          MarkKeep(pkg, false, false);
1678
1679       instver=state.InstVerIter(*this);
1680    }
1681 #endif
1682
1683    // For packages that are not going to be removed, ignore versions
1684    // other than the InstVer.  For packages that are going to be
1685    // removed, ignore versions other than the current version.
1686    if(!(ver == instver && !instver.end()) &&
1687       !(ver == currver && instver.end() && !ver.end()))
1688       return;
1689
1690    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1691
1692    if(debug_autoremove)
1693      {
1694        std::clog << "Marking: " << pkg.FullName();
1695        if(!ver.end())
1696          std::clog << " " << ver.VerStr();
1697        if(!currver.end())
1698          std::clog << ", Curr=" << currver.VerStr();
1699        if(!instver.end())
1700          std::clog << ", Inst=" << instver.VerStr();
1701        std::clog << std::endl;
1702      }
1703
1704    state.Marked=true;
1705
1706    if(ver.end() == true)
1707       return;
1708
1709      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1710      {
1711         if(d->Type == Dep::Depends ||
1712            d->Type == Dep::PreDepends ||
1713            (follow_recommends &&
1714             d->Type == Dep::Recommends) ||
1715            (follow_suggests &&
1716             d->Type == Dep::Suggests))
1717         {
1718            // Try all versions of this package.
1719            for(VerIterator V = d.TargetPkg().VersionList();
1720                !V.end(); ++V)
1721            {
1722               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1723               {
1724                 if(debug_autoremove)
1725                   {
1726                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1727                               << " " << d.ParentVer().VerStr() << " "
1728                               << d.DepType() << " " << d.TargetPkg().FullName();
1729                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1730                       {
1731                         std::clog << " (" << d.CompType() << " "
1732                                   << d.TargetVer() << ")";
1733                       }
1734                     std::clog << std::endl;
1735                   }
1736                  MarkPackage(V.ParentPkg(), V,
1737                              follow_recommends, follow_suggests);
1738               }
1739            }
1740            // Now try virtual packages
1741            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1742                !prv.end(); ++prv)
1743            {
1744               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1745                                        d.TargetVer()))
1746               {
1747                 if(debug_autoremove)
1748                   {
1749                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1750                               << d.ParentVer().VerStr() << " "
1751                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1752                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1753                       {
1754                         std::clog << " (" << d.CompType() << " "
1755                                   << d.TargetVer() << ")";
1756                       }
1757                     std::clog << ", provided by "
1758                               << prv.OwnerPkg().FullName() << " "
1759                               << prv.OwnerVer().VerStr()
1760                               << std::endl;
1761                   }
1762
1763                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1764                              follow_recommends, follow_suggests);
1765               }
1766            }
1767         }
1768      }
1769 }
1770                                                                         /*}}}*/
1771 bool pkgDepCache::Sweep()                                               /*{{{*/
1772 {
1773    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1774
1775    // do the sweep
1776    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1777    {
1778      StateCache &state=PkgState[p->ID];
1779
1780      // skip required packages
1781      if (!p.CurrentVer().end() &&
1782          (p.CurrentVer()->Priority == pkgCache::State::Required))
1783         continue;
1784
1785      // if it is not marked and it is installed, it's garbage
1786      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1787      {
1788         state.Garbage=true;
1789         if(debug_autoremove)
1790            std::clog << "Garbage: " << p.FullName() << std::endl;
1791      }
1792   }
1793
1794    return true;
1795 }
1796                                                                         /*}}}*/