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);
1177             else
1178                MarkDelete(Pkg,false,Depth + 1, false);
1179          }
1180          continue;
1181       }
1182    }
1183
1184    return true;
1185 }
1186                                                                         /*}}}*/
1187 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1188 // ---------------------------------------------------------------------
1189 /* The default implementation does nothing.
1190    dpkg holds are enforced by the private IsModeChangeOk */
1191 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1192                               unsigned long Depth, bool FromUser)
1193 {
1194    return true;
1195 }
1196                                                                         /*}}}*/
1197 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1198 // ---------------------------------------------------------------------
1199 /* */
1200 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1201 {
1202    if (unlikely(Pkg.end() == true))
1203       return;
1204
1205    ActionGroup group(*this);
1206
1207    RemoveSizes(Pkg);
1208    RemoveStates(Pkg);
1209
1210    StateCache &P = PkgState[Pkg->ID];
1211    if (To == true)
1212       P.iFlags |= ReInstall;
1213    else
1214       P.iFlags &= ~ReInstall;
1215
1216    AddStates(Pkg);
1217    AddSizes(Pkg);
1218 }
1219                                                                         /*}}}*/
1220 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1221 // ---------------------------------------------------------------------
1222 /* */
1223 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1224 {
1225    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1226    StateCache &P = PkgState[Pkg->ID];
1227
1228    if (P.CandidateVer == TargetVer)
1229       return;
1230
1231    ActionGroup group(*this);
1232
1233    RemoveSizes(Pkg);
1234    RemoveStates(Pkg);
1235
1236    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1237       P.InstallVer = (Version *)TargetVer;
1238    P.CandidateVer = (Version *)TargetVer;
1239    P.Update(Pkg,*this);
1240
1241    AddStates(Pkg);
1242    Update(Pkg);
1243    AddSizes(Pkg);
1244
1245 }
1246                                                                         /*}}}*/
1247 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1248 // ---------------------------------------------------------------------
1249 /* changes the candidate of a package and walks over all its dependencies
1250    to check if it needs to change the candidate of the dependency, too,
1251    to reach a installable versionstate */
1252 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1253                                         std::string const &TargetRel)
1254 {
1255    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1256    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1257 }
1258 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1259                                         std::string const &TargetRel,
1260                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1261 {
1262    ActionGroup group(*this);
1263    SetCandidateVersion(TargetVer);
1264
1265    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1266       return true;
1267
1268    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1269    // save the position of the last element we will not undo - if we have to
1270    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1271
1272    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1273    {
1274       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1275           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1276            IsImportantDep(D) == false))
1277          continue;
1278
1279       // walk over an or-group and check if we need to do anything
1280       // for simpilicity no or-group is handled as a or-group including one dependency
1281       pkgCache::DepIterator Start = D;
1282       bool itsFine = false;
1283       for (bool stillOr = true; stillOr == true; ++Start)
1284       {
1285          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1286          pkgCache::PkgIterator const P = Start.TargetPkg();
1287          // virtual packages can't be a solution
1288          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1289             continue;
1290          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1291          // no versioned dependency - but is it installable?
1292          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1293          {
1294             // Check if one of the providers is installable
1295             if (P->ProvidesList != 0)
1296             {
1297                pkgCache::PrvIterator Prv = P.ProvidesList();
1298                for (; Prv.end() == false; ++Prv)
1299                {
1300                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1301                   if (C.end() == true || C != Prv.OwnerVer() ||
1302                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1303                      continue;
1304                   break;
1305                }
1306                if (Prv.end() == true)
1307                   continue;
1308             }
1309             // no providers, so check if we have an installable candidate version
1310             else if (Cand.end() == true ||
1311                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1312                continue;
1313             itsFine = true;
1314             break;
1315          }
1316          if (Cand.end() == true)
1317             continue;
1318          // check if the current candidate is enough for the versioned dependency - and installable?
1319          if (VS().CheckDep(P.CandVersion(), Start->CompareOp, Start.TargetVer()) == true &&
1320              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1321          {
1322             itsFine = true;
1323             break;
1324          }
1325       }
1326
1327       if (itsFine == true) {
1328          // something in the or-group was fine, skip all other members
1329          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1330          continue;
1331       }
1332
1333       // walk again over the or-group and check each if a candidate switch would help
1334       itsFine = false;
1335       for (bool stillOr = true; stillOr == true; ++D)
1336       {
1337          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1338          // changing candidate will not help if the dependency is not versioned
1339          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1340          {
1341             if (stillOr == true)
1342                continue;
1343             break;
1344          }
1345
1346          pkgCache::VerIterator V;
1347          if (TargetRel == "newest")
1348             V = D.TargetPkg().VersionList();
1349          else
1350             V = Match.Find(D.TargetPkg());
1351
1352          // check if the version from this release could satisfy the dependency
1353          if (V.end() == true || VS().CheckDep(V.VerStr(), D->CompareOp, D.TargetVer()) == false)
1354          {
1355             if (stillOr == true)
1356                continue;
1357             break;
1358          }
1359
1360          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1361          if (V == oldCand)
1362          {
1363             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1364             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1365                  c != Changed.end(); ++c)
1366             {
1367                if (c->first->ParentPkg != V->ParentPkg)
1368                   continue;
1369                itsFine = true;
1370                break;
1371             }
1372          }
1373
1374          if (itsFine == false)
1375          {
1376             // change the candidate
1377             Changed.push_back(make_pair(oldCand, TargetVer));
1378             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1379             {
1380                if (stillOr == false)
1381                   break;
1382                // undo the candidate changing
1383                SetCandidateVersion(oldCand);
1384                Changed.pop_back();
1385                continue;
1386             }
1387             itsFine = true;
1388          }
1389
1390          // something in the or-group was fine, skip all other members
1391          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1392          break;
1393       }
1394
1395       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1396       {
1397          // undo all changes which aren't lead to a solution
1398          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1399               c != Changed.end(); ++c)
1400             SetCandidateVersion(c->first);
1401          Changed.erase(newChanged, Changed.end());
1402          return false;
1403       }
1404    }
1405    return true;
1406 }
1407                                                                         /*}}}*/
1408 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1409 // ---------------------------------------------------------------------
1410 /* */
1411 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1412 {
1413   StateCache &state = PkgState[Pkg->ID];
1414
1415   ActionGroup group(*this);
1416
1417   if(Auto)
1418     state.Flags |= Flag::Auto;
1419   else
1420     state.Flags &= ~Flag::Auto;
1421 }
1422                                                                         /*}}}*/
1423 // StateCache::Update - Compute the various static display things       /*{{{*/
1424 // ---------------------------------------------------------------------
1425 /* This is called whenever the Candidate version changes. */
1426 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1427 {
1428    // Some info
1429    VerIterator Ver = CandidateVerIter(Cache);
1430
1431    // Use a null string or the version string
1432    if (Ver.end() == true)
1433       CandVersion = "";
1434    else
1435       CandVersion = Ver.VerStr();
1436
1437    // Find the current version
1438    CurVersion = "";
1439    if (Pkg->CurrentVer != 0)
1440       CurVersion = Pkg.CurrentVer().VerStr();
1441
1442    // Strip off the epochs for display
1443    CurVersion = StripEpoch(CurVersion);
1444    CandVersion = StripEpoch(CandVersion);
1445
1446    // Figure out if its up or down or equal
1447    Status = Ver.CompareVer(Pkg.CurrentVer());
1448    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1449      Status = 2;
1450 }
1451                                                                         /*}}}*/
1452 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1453 // ---------------------------------------------------------------------
1454 /* */
1455 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1456 {
1457    if (Ver == 0)
1458       return 0;
1459
1460    // Strip any epoch
1461    for (const char *I = Ver; *I != 0; I++)
1462       if (*I == ':')
1463          return I + 1;
1464    return Ver;
1465 }
1466                                                                         /*}}}*/
1467 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1468 // ---------------------------------------------------------------------
1469 /* The default just returns the highest available version that is not
1470    a source and automatic. */
1471 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1472 {
1473    /* Not source/not automatic versions cannot be a candidate version
1474       unless they are already installed */
1475    VerIterator Last(*(pkgCache *)this,0);
1476
1477    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1478    {
1479       if (Pkg.CurrentVer() == I)
1480          return I;
1481
1482       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1483       {
1484          if ((J.File()->Flags & Flag::NotSource) != 0)
1485             continue;
1486
1487          /* Stash the highest version of a not-automatic source, we use it
1488             if there is nothing better */
1489          if ((J.File()->Flags & Flag::NotAutomatic) != 0 ||
1490              (J.File()->Flags & Flag::ButAutomaticUpgrades) != 0)
1491          {
1492             if (Last.end() == true)
1493                Last = I;
1494             continue;
1495          }
1496
1497          return I;
1498       }
1499    }
1500
1501    return Last;
1502 }
1503                                                                         /*}}}*/
1504 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1505 // ---------------------------------------------------------------------
1506 /* */
1507 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
1508 {
1509    if(Dep.IsCritical())
1510       return true;
1511    else if(Dep->Type == pkgCache::Dep::Recommends)
1512    {
1513       if ( _config->FindB("APT::Install-Recommends", false))
1514          return true;
1515       // we suport a special mode to only install-recommends for certain
1516       // sections
1517       // FIXME: this is a meant as a temporarly solution until the
1518       //        recommends are cleaned up
1519       const char *sec = Dep.ParentVer().Section();
1520       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1521          return true;
1522    }
1523    else if(Dep->Type == pkgCache::Dep::Suggests)
1524      return _config->FindB("APT::Install-Suggests", false);
1525
1526    return false;
1527 }
1528                                                                         /*}}}*/
1529 // Policy::GetPriority - Get the priority of the package pin            /*{{{*/
1530 signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &Pkg)
1531 { return 0; };
1532 signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &File)
1533 { return 0; };
1534                                                                         /*}}}*/
1535 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1536 {
1537   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1538   if(f->wasConstructedSuccessfully())
1539     return f;
1540   else
1541     {
1542       delete f;
1543       return NULL;
1544     }
1545 }
1546                                                                         /*}}}*/
1547 bool pkgDepCache::MarkFollowsRecommends()
1548 {
1549   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1550 }
1551
1552 bool pkgDepCache::MarkFollowsSuggests()
1553 {
1554   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1555 }
1556
1557 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1558 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1559 {
1560    if (_config->Find("APT::Solver", "internal") != "internal")
1561       return true;
1562
1563    bool follow_recommends;
1564    bool follow_suggests;
1565    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1566
1567    // init the states
1568    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1569    {
1570       PkgState[p->ID].Marked  = false;
1571       PkgState[p->ID].Garbage = false;
1572
1573       // debug output
1574       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1575          std::clog << "AutoDep: " << p.FullName() << std::endl;
1576    }
1577
1578    // init vars
1579    follow_recommends = MarkFollowsRecommends();
1580    follow_suggests   = MarkFollowsSuggests();
1581
1582
1583
1584    // do the mark part, this is the core bit of the algorithm
1585    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1586    {
1587       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1588           (p->Flags & Flag::Essential) ||
1589           userFunc.InRootSet(p) ||
1590           // be nice even then a required package violates the policy (#583517)
1591           // and do the full mark process also for required packages
1592           (p.CurrentVer().end() != true &&
1593            p.CurrentVer()->Priority == pkgCache::State::Required))
1594       {
1595          // the package is installed (and set to keep)
1596          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1597             MarkPackage(p, p.CurrentVer(),
1598                         follow_recommends, follow_suggests);
1599          // the package is to be installed
1600          else if(PkgState[p->ID].Install())
1601             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1602                         follow_recommends, follow_suggests);
1603       }
1604    }
1605
1606    return true;
1607 }
1608                                                                         /*}}}*/
1609 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1610 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1611                               const pkgCache::VerIterator &ver,
1612                               bool const &follow_recommends,
1613                               bool const &follow_suggests)
1614 {
1615    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1616
1617    // if we are marked already we are done
1618    if(state.Marked)
1619       return;
1620
1621    VerIterator const currver = pkg.CurrentVer();
1622    VerIterator const instver = state.InstVerIter(*this);
1623
1624 #if 0
1625    VerIterator const candver = state.CandidateVerIter(*this);
1626
1627    // If a package was garbage-collected but is now being marked, we
1628    // should re-select it
1629    // For cases when a pkg is set to upgrade and this trigger the
1630    // removal of a no-longer used dependency.  if the pkg is set to
1631    // keep again later it will result in broken deps
1632    if(state.Delete() && state.RemoveReason = Unused)
1633    {
1634       if(ver==candver)
1635          mark_install(pkg, false, false, NULL);
1636       else if(ver==pkg.CurrentVer())
1637          MarkKeep(pkg, false, false);
1638
1639       instver=state.InstVerIter(*this);
1640    }
1641 #endif
1642
1643    // For packages that are not going to be removed, ignore versions
1644    // other than the InstVer.  For packages that are going to be
1645    // removed, ignore versions other than the current version.
1646    if(!(ver == instver && !instver.end()) &&
1647       !(ver == currver && instver.end() && !ver.end()))
1648       return;
1649
1650    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1651
1652    if(debug_autoremove)
1653      {
1654        std::clog << "Marking: " << pkg.FullName();
1655        if(!ver.end())
1656          std::clog << " " << ver.VerStr();
1657        if(!currver.end())
1658          std::clog << ", Curr=" << currver.VerStr();
1659        if(!instver.end())
1660          std::clog << ", Inst=" << instver.VerStr();
1661        std::clog << std::endl;
1662      }
1663
1664    state.Marked=true;
1665
1666    if(ver.end() == true)
1667       return;
1668
1669      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1670      {
1671         if(d->Type == Dep::Depends ||
1672            d->Type == Dep::PreDepends ||
1673            (follow_recommends &&
1674             d->Type == Dep::Recommends) ||
1675            (follow_suggests &&
1676             d->Type == Dep::Suggests))
1677         {
1678            // Try all versions of this package.
1679            for(VerIterator V = d.TargetPkg().VersionList();
1680                !V.end(); ++V)
1681            {
1682               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1683               {
1684                 if(debug_autoremove)
1685                   {
1686                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1687                               << " " << d.ParentVer().VerStr() << " "
1688                               << d.DepType() << " " << d.TargetPkg().FullName();
1689                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1690                       {
1691                         std::clog << " (" << d.CompType() << " "
1692                                   << d.TargetVer() << ")";
1693                       }
1694                     std::clog << std::endl;
1695                   }
1696                  MarkPackage(V.ParentPkg(), V,
1697                              follow_recommends, follow_suggests);
1698               }
1699            }
1700            // Now try virtual packages
1701            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1702                !prv.end(); ++prv)
1703            {
1704               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1705                                        d.TargetVer()))
1706               {
1707                 if(debug_autoremove)
1708                   {
1709                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1710                               << d.ParentVer().VerStr() << " "
1711                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1712                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1713                       {
1714                         std::clog << " (" << d.CompType() << " "
1715                                   << d.TargetVer() << ")";
1716                       }
1717                     std::clog << ", provided by "
1718                               << prv.OwnerPkg().FullName() << " "
1719                               << prv.OwnerVer().VerStr()
1720                               << std::endl;
1721                   }
1722
1723                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1724                              follow_recommends, follow_suggests);
1725               }
1726            }
1727         }
1728      }
1729 }
1730                                                                         /*}}}*/
1731 bool pkgDepCache::Sweep()                                               /*{{{*/
1732 {
1733    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1734
1735    // do the sweep
1736    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1737    {
1738      StateCache &state=PkgState[p->ID];
1739
1740      // skip required packages
1741      if (!p.CurrentVer().end() &&
1742          (p.CurrentVer()->Priority == pkgCache::State::Required))
1743         continue;
1744
1745      // if it is not marked and it is installed, it's garbage
1746      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1747      {
1748         state.Garbage=true;
1749         if(debug_autoremove)
1750            std::clog << "Garbage: " << p.FullName() << std::endl;
1751      }
1752   }
1753
1754    return true;
1755 }
1756                                                                         /*}}}*/