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