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