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