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<config.h>
  12
  13 #include <apt-pkg/depcache.h>
  14 #include <apt-pkg/version.h>
  15 #include <apt-pkg/versionmatch.h>
  16 #include <apt-pkg/error.h>
  17 #include <apt-pkg/sptr.h>
  18 #include <apt-pkg/algorithms.h>
  19 #include <apt-pkg/fileutl.h>
  20 #include <apt-pkg/strutl.h>
  21 #include <apt-pkg/configuration.h>
  22 #include <apt-pkg/aptconfiguration.h>
  23 #include <apt-pkg/pkgsystem.h>
  24 #include <apt-pkg/tagfile.h>
  25 #include <apt-pkg/progress.h>
  26 #include <apt-pkg/cacheset.h>
  27
  28 #include <algorithm>
  29 #include <iostream>
  30 #include <sstream>
  31 #include <set>
  32
  33 #include <sys/stat.h>
  34
  35 #include <apti18n.h>
  36                                                                         /*}}}*/
  37
  38 using std::string;
  39
  40 // helper for Install-Recommends-Sections and Never-MarkAuto-Sections   /*{{{*/
  41 static bool
  42 ConfigValueInSubTree(const char* SubTree, const char *needle)
  43 {
  44    Configuration::Item const *Opts;
  45    Opts = _config->Tree(SubTree);
  46    if (Opts != 0 && Opts->Child != 0)
  47    {
  48       Opts = Opts->Child;
  49       for (; Opts != 0; Opts = Opts->Next)
  50       {
  51          if (Opts->Value.empty() == true)
  52             continue;
  53          if (strcmp(needle, Opts->Value.c_str()) == 0)
  54             return true;
  55       }
  56    }
  57    return false;
  58 }
  59                                                                         /*}}}*/
  60 pkgDepCache::ActionGroup::ActionGroup(pkgDepCache &cache) :             /*{{{*/
  61   cache(cache), released(false)
  62 {
  63   ++cache.group_level;
  64 }
  65
  66 void pkgDepCache::ActionGroup::release()
  67 {
  68   if(!released)
  69     {
  70       if(cache.group_level == 0)
  71         std::cerr << "W: Unbalanced action groups, expect badness" << std::endl;
  72       else
  73         {
  74           --cache.group_level;
  75
  76           if(cache.group_level == 0)
  77             cache.MarkAndSweep();
  78         }
  79
  80       released = true;
  81     }
  82 }
  83
  84 pkgDepCache::ActionGroup::~ActionGroup()
  85 {
  86   release();
  87 }
  88                                                                         /*}}}*/
  89 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  90 // ---------------------------------------------------------------------
  91 /* */
  92 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  93   group_level(0), Cache(pCache), PkgState(0), DepState(0)
  94 {
  95    DebugMarker = _config->FindB("Debug::pkgDepCache::Marker", false);
  96    DebugAutoInstall = _config->FindB("Debug::pkgDepCache::AutoInstall", false);
  97    delLocalPolicy = 0;
  98    LocalPolicy = Plcy;
  99    if (LocalPolicy == 0)
 100       delLocalPolicy = LocalPolicy = new Policy;
 101 }
 102                                                                         /*}}}*/
 103 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
 104 // ---------------------------------------------------------------------
 105 /* */
 106 pkgDepCache::~pkgDepCache()
 107 {
 108    delete [] PkgState;
 109    delete [] DepState;
 110    delete delLocalPolicy;
 111 }
 112                                                                         /*}}}*/
 113 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
 114 // ---------------------------------------------------------------------
 115 /* This allocats the extension buffers and initializes them. */
 116 bool pkgDepCache::Init(OpProgress *Prog)
 117 {
 118    // Suppress mark updates during this operation (just in case) and
 119    // run a mark operation when Init terminates.
 120    ActionGroup actions(*this);
 121
 122    delete [] PkgState;
 123    delete [] DepState;
 124    PkgState = new StateCache[Head().PackageCount];
 125    DepState = new unsigned char[Head().DependsCount];
 126    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
 127    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
 128
 129    if (Prog != 0)
 130    {
 131       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
 132                             _("Building dependency tree"));
 133       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 134    }
 135
 136    /* Set the current state of everything. In this state all of the
 137       packages are kept exactly as is. See AllUpgrade */
 138    int Done = 0;
 139    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 140    {
 141       if (Prog != 0 && Done%20 == 0)
 142          Prog->Progress(Done);
 143
 144       // Find the proper cache slot
 145       StateCache &State = PkgState[I->ID];
 146       State.iFlags = 0;
 147
 148       // Figure out the install version
 149       State.CandidateVer = GetCandidateVer(I);
 150       State.InstallVer = I.CurrentVer();
 151       State.Mode = ModeKeep;
 152
 153       State.Update(I,*this);
 154    }
 155
 156    if (Prog != 0)
 157    {
 158
 159       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
 160                             Head().PackageCount,
 161                             _("Building dependency tree"));
 162       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
 163    }
 164
 165    Update(Prog);
 166
 167    if(Prog != 0)
 168       Prog->Done();
 169
 170    return true;
 171 }
 172                                                                         /*}}}*/
 173 bool pkgDepCache::readStateFile(OpProgress *Prog)                       /*{{{*/
 174 {
 175    FileFd state_file;
 176    string const state = _config->FindFile("Dir::State::extended_states");
 177    if(RealFileExists(state)) {
 178       state_file.Open(state, FileFd::ReadOnly);
 179       off_t const file_size = state_file.Size();
 180       if(Prog != NULL)
 181          Prog->OverallProgress(0, file_size, 1,
 182                                _("Reading state information"));
 183
 184       pkgTagFile tagfile(&state_file);
 185       pkgTagSection section;
 186       off_t amt = 0;
 187       bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 188       while(tagfile.Step(section)) {
 189          string const pkgname = section.FindS("Package");
 190          string pkgarch = section.FindS("Architecture");
 191          if (pkgarch.empty() == true)
 192             pkgarch = "any";
 193          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 194          // Silently ignore unknown packages and packages with no actual version.
 195          if(pkg.end() == true || pkg->VersionList == 0)
 196             continue;
 197
 198          short const reason = section.FindI("Auto-Installed", 0);
 199          if(reason > 0)
 200          {
 201             PkgState[pkg->ID].Flags |= Flag::Auto;
 202             if (unlikely(debug_autoremove))
 203                std::clog << "Auto-Installed : " << pkg.FullName() << std::endl;
 204             if (pkgarch == "any")
 205             {
 206                pkgCache::GrpIterator G = pkg.Group();
 207                for (pkg = G.NextPkg(pkg); pkg.end() != true; pkg = G.NextPkg(pkg))
 208                   if (pkg->VersionList != 0)
 209                      PkgState[pkg->ID].Flags |= Flag::Auto;
 210             }
 211          }
 212          amt += section.size();
 213          if(Prog != NULL)
 214             Prog->OverallProgress(amt, file_size, 1,
 215                                   _("Reading state information"));
 216       }
 217       if(Prog != NULL)
 218          Prog->OverallProgress(file_size, file_size, 1,
 219                                _("Reading state information"));
 220    }
 221
 222    return true;
 223 }
 224                                                                         /*}}}*/
 225 bool pkgDepCache::writeStateFile(OpProgress *prog, bool InstalledOnly)  /*{{{*/
 226 {
 227    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 228
 229    if(debug_autoremove)
 230       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 231
 232    FileFd StateFile;
 233    string const state = _config->FindFile("Dir::State::extended_states");
 234
 235    // if it does not exist, create a empty one
 236    if(!RealFileExists(state))
 237    {
 238       StateFile.Open(state, FileFd::WriteAtomic);
 239       StateFile.Close();
 240    }
 241
 242    // open it
 243    if(!StateFile.Open(state, FileFd::ReadOnly))
 244       return _error->Error(_("Failed to open StateFile %s"),
 245                            state.c_str());
 246
 247    FILE *OutFile;
 248    string const outfile = state + ".tmp";
 249    if((OutFile = fopen(outfile.c_str(),"w")) == NULL)
 250       return _error->Error(_("Failed to write temporary StateFile %s"),
 251                            outfile.c_str());
 252
 253    // first merge with the existing sections
 254    pkgTagFile tagfile(&StateFile);
 255    pkgTagSection section;
 256    std::set<string> pkgs_seen;
 257    const char *nullreorderlist[] = {0};
 258    while(tagfile.Step(section)) {
 259          string const pkgname = section.FindS("Package");
 260          string pkgarch = section.FindS("Architecture");
 261          if (pkgarch.empty() == true)
 262             pkgarch = "native";
 263          // Silently ignore unknown packages and packages with no actual
 264          // version.
 265          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 266          if(pkg.end() || pkg.VersionList().end())
 267             continue;
 268          StateCache const &P = PkgState[pkg->ID];
 269          bool newAuto = (P.Flags & Flag::Auto);
 270          // skip not installed or now-removed ones if requested
 271          if (InstalledOnly && (
 272              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 273              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 274          {
 275             // The section is obsolete if it contains no other tag
 276             unsigned int const count = section.Count();
 277             if (count < 2 ||
 278                 (count == 2 && section.Exists("Auto-Installed")) ||
 279                 (count == 3 && section.Exists("Auto-Installed") && section.Exists("Architecture")))
 280                continue;
 281             else
 282                newAuto = false;
 283          }
 284          if(_config->FindB("Debug::pkgAutoRemove",false))
 285             std::clog << "Update existing AutoInstall info: "
 286                       << pkg.FullName() << std::endl;
 287          TFRewriteData rewrite[3];
 288          rewrite[0].Tag = "Architecture";
 289          rewrite[0].Rewrite = pkg.Arch();
 290          rewrite[0].NewTag = 0;
 291          rewrite[1].Tag = "Auto-Installed";
 292          rewrite[1].Rewrite = newAuto ? "1" : "0";
 293          rewrite[1].NewTag = 0;
 294          rewrite[2].Tag = 0;
 295          TFRewrite(OutFile, section, nullreorderlist, rewrite);
 296          fprintf(OutFile,"\n");
 297          pkgs_seen.insert(pkg.FullName());
 298    }
 299
 300    // then write the ones we have not seen yet
 301    std::ostringstream ostr;
 302    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end(); ++pkg) {
 303       StateCache const &P = PkgState[pkg->ID];
 304       if(P.Flags & Flag::Auto) {
 305          if (pkgs_seen.find(pkg.FullName()) != pkgs_seen.end()) {
 306             if(debug_autoremove)
 307                std::clog << "Skipping already written " << pkg.FullName() << std::endl;
 308             continue;
 309          }
 310          // skip not installed ones if requested
 311          if (InstalledOnly && (
 312              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 313              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 314             continue;
 315          const char* const pkgarch = pkg.Arch();
 316          if (strcmp(pkgarch, "all") == 0)
 317             continue;
 318          if(debug_autoremove)
 319             std::clog << "Writing new AutoInstall: " << pkg.FullName() << std::endl;
 320          ostr.str(string(""));
 321          ostr << "Package: " << pkg.Name()
 322               << "\nArchitecture: " << pkgarch
 323               << "\nAuto-Installed: 1\n\n";
 324          fprintf(OutFile,"%s",ostr.str().c_str());
 325       }
 326    }
 327    fclose(OutFile);
 328
 329    // move the outfile over the real file and set permissions
 330    rename(outfile.c_str(), state.c_str());
 331    chmod(state.c_str(), 0644);
 332
 333    return true;
 334 }
 335                                                                         /*}}}*/
 336 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 337 // ---------------------------------------------------------------------
 338 /* This first checks the dependency against the main target package and
 339    then walks along the package provides list and checks if each provides
 340    will be installed then checks the provides against the dep. Res will be
 341    set to the package which was used to satisfy the dep. */
 342 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 343 {
 344    Res = Dep.TargetPkg();
 345
 346    /* Check simple depends. A depends -should- never self match but
 347       we allow it anyhow because dpkg does. Technically it is a packaging
 348       bug. Conflicts may never self match */
 349    if (Dep.TargetPkg() != Dep.ParentPkg() || Dep.IsNegative() == false)
 350    {
 351       PkgIterator Pkg = Dep.TargetPkg();
 352       // Check the base package
 353       if (Type == NowVersion && Pkg->CurrentVer != 0)
 354          if (VS().CheckDep(Pkg.CurrentVer().VerStr(),Dep->CompareOp,
 355                                  Dep.TargetVer()) == true)
 356             return true;
 357
 358       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 359          if (VS().CheckDep(PkgState[Pkg->ID].InstVerIter(*this).VerStr(),
 360                                  Dep->CompareOp,Dep.TargetVer()) == true)
 361             return true;
 362
 363       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 364          if (VS().CheckDep(PkgState[Pkg->ID].CandidateVerIter(*this).VerStr(),
 365                                  Dep->CompareOp,Dep.TargetVer()) == true)
 366             return true;
 367    }
 368
 369    if (Dep->Type == Dep::Obsoletes)
 370       return false;
 371
 372    // Check the providing packages
 373    PrvIterator P = Dep.TargetPkg().ProvidesList();
 374    PkgIterator Pkg = Dep.ParentPkg();
 375    for (; P.end() != true; ++P)
 376    {
 377       /* Provides may never be applied against the same package (or group)
 378          if it is a conflicts. See the comment above. */
 379       if (P.OwnerPkg()->Group == Pkg->Group && Dep.IsNegative() == true)
 380          continue;
 381
 382       // Check if the provides is a hit
 383       if (Type == NowVersion)
 384       {
 385          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 386             continue;
 387       }
 388
 389       if (Type == InstallVersion)
 390       {
 391          StateCache &State = PkgState[P.OwnerPkg()->ID];
 392          if (State.InstallVer != (Version *)P.OwnerVer())
 393             continue;
 394       }
 395
 396       if (Type == CandidateVersion)
 397       {
 398          StateCache &State = PkgState[P.OwnerPkg()->ID];
 399          if (State.CandidateVer != (Version *)P.OwnerVer())
 400             continue;
 401       }
 402
 403       // Compare the versions.
 404       if (VS().CheckDep(P.ProvideVersion(),Dep->CompareOp,Dep.TargetVer()) == true)
 405       {
 406          Res = P.OwnerPkg();
 407          return true;
 408       }
 409    }
 410
 411    return false;
 412 }
 413                                                                         /*}}}*/
 414 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 415 // ---------------------------------------------------------------------
 416 /* Call with Inverse = true to preform the inverse opration */
 417 void pkgDepCache::AddSizes(const PkgIterator &Pkg, bool const Inverse)
 418 {
 419    StateCache &P = PkgState[Pkg->ID];
 420
 421    if (Pkg->VersionList == 0)
 422       return;
 423
 424    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 425        P.Keep() == true)
 426       return;
 427
 428    // Compute the size data
 429    if (P.NewInstall() == true)
 430    {
 431       if (Inverse == false) {
 432          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 433          iDownloadSize += P.InstVerIter(*this)->Size;
 434       } else {
 435          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 436          iDownloadSize -= P.InstVerIter(*this)->Size;
 437       }
 438       return;
 439    }
 440
 441    // Upgrading
 442    if (Pkg->CurrentVer != 0 &&
 443        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 444         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 445    {
 446       if (Inverse == false) {
 447          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 448          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 449          iDownloadSize += P.InstVerIter(*this)->Size;
 450       } else {
 451          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 452          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 453          iDownloadSize -= P.InstVerIter(*this)->Size;
 454       }
 455       return;
 456    }
 457
 458    // Reinstall
 459    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 460        P.Delete() == false)
 461    {
 462       if (Inverse == false)
 463          iDownloadSize += P.InstVerIter(*this)->Size;
 464       else
 465          iDownloadSize -= P.InstVerIter(*this)->Size;
 466       return;
 467    }
 468
 469    // Removing
 470    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 471    {
 472       if (Inverse == false)
 473          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 474       else
 475          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 476       return;
 477    }
 478 }
 479                                                                         /*}}}*/
 480 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 481 // ---------------------------------------------------------------------
 482 /* This routine is tricky to use, you must make sure that it is never
 483    called twice for the same package. This means the Remove/Add section
 484    should be as short as possible and not encompass any code that will
 485    calld Remove/Add itself. Remember, dependencies can be circular so
 486    while processing a dep for Pkg it is possible that Add/Remove
 487    will be called on Pkg */
 488 void pkgDepCache::AddStates(const PkgIterator &Pkg, bool const Invert)
 489 {
 490    signed char const Add = (Invert == false) ? 1 : -1;
 491    StateCache &State = PkgState[Pkg->ID];
 492
 493    // The Package is broken (either minimal dep or policy dep)
 494    if ((State.DepState & DepInstMin) != DepInstMin)
 495       iBrokenCount += Add;
 496    if ((State.DepState & DepInstPolicy) != DepInstPolicy)
 497       iPolicyBrokenCount += Add;
 498
 499    // Bad state
 500    if (Pkg.State() != PkgIterator::NeedsNothing)
 501       iBadCount += Add;
 502
 503    // Not installed
 504    if (Pkg->CurrentVer == 0)
 505    {
 506       if (State.Mode == ModeDelete &&
 507           (State.iFlags & Purge) == Purge && Pkg.Purge() == false)
 508          iDelCount += Add;
 509
 510       if (State.Mode == ModeInstall)
 511          iInstCount += Add;
 512       return;
 513    }
 514
 515    // Installed, no upgrade
 516    if (State.Status == 0)
 517    {
 518       if (State.Mode == ModeDelete)
 519          iDelCount += Add;
 520       else
 521          if ((State.iFlags & ReInstall) == ReInstall)
 522             iInstCount += Add;
 523
 524       return;
 525    }
 526
 527    // Alll 3 are possible
 528    if (State.Mode == ModeDelete)
 529       iDelCount += Add;
 530    if (State.Mode == ModeKeep)
 531       iKeepCount += Add;
 532    if (State.Mode == ModeInstall)
 533       iInstCount += Add;
 534 }
 535                                                                         /*}}}*/
 536 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 537 // ---------------------------------------------------------------------
 538 /* The or group results are stored in the last item of the or group. This
 539    allows easy detection of the state of a whole or'd group. */
 540 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 541 {
 542    unsigned char Group = 0;
 543
 544    for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 545    {
 546       // Build the dependency state.
 547       unsigned char &State = DepState[D->ID];
 548
 549       /* Invert for Conflicts. We have to do this twice to get the
 550          right sense for a conflicts group */
 551       if (D.IsNegative() == true)
 552          State = ~State;
 553
 554       // Add to the group if we are within an or..
 555       State &= 0x7;
 556       Group |= State;
 557       State |= Group << 3;
 558       if ((D->CompareOp & Dep::Or) != Dep::Or)
 559          Group = 0;
 560
 561       // Invert for Conflicts
 562       if (D.IsNegative() == true)
 563          State = ~State;
 564    }
 565 }
 566                                                                         /*}}}*/
 567 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 568 // ---------------------------------------------------------------------
 569 /* This is used to run over a dependency list and determine the dep
 570    state of the list, filtering it through both a Min check and a Policy
 571    check. The return result will have SetMin/SetPolicy low if a check
 572    fails. It uses the DepState cache for it's computations. */
 573 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 574                                        unsigned char SetMin,
 575                                        unsigned char SetPolicy)
 576 {
 577    unsigned char Dep = 0xFF;
 578
 579    while (D.end() != true)
 580    {
 581       // Compute a single dependency element (glob or)
 582       DepIterator Start = D;
 583       unsigned char State = 0;
 584       for (bool LastOR = true; D.end() == false && LastOR == true; ++D)
 585       {
 586          State |= DepState[D->ID];
 587          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 588       }
 589
 590       // Minimum deps that must be satisfied to have a working package
 591       if (Start.IsCritical() == true)
 592          if ((State & Check) != Check)
 593             Dep &= ~SetMin;
 594
 595       // Policy deps that must be satisfied to install the package
 596       if (IsImportantDep(Start) == true &&
 597           (State & Check) != Check)
 598          Dep &= ~SetPolicy;
 599    }
 600
 601    return Dep;
 602 }
 603                                                                         /*}}}*/
 604 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 605 // ---------------------------------------------------------------------
 606 /* This is the main dependency computation bit. It computes the 3 main
 607    results for a dependencys, Now, Install and Candidate. Callers must
 608    invert the result if dealing with conflicts. */
 609 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 610 {
 611    unsigned char State = 0;
 612
 613    if (CheckDep(D,NowVersion) == true)
 614       State |= DepNow;
 615    if (CheckDep(D,InstallVersion) == true)
 616       State |= DepInstall;
 617    if (CheckDep(D,CandidateVersion) == true)
 618       State |= DepCVer;
 619
 620    return State;
 621 }
 622                                                                         /*}}}*/
 623 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 624 // ---------------------------------------------------------------------
 625 /* This determines the combined dependency representation of a package
 626    for its two states now and install. This is done by using the pre-generated
 627    dependency information. */
 628 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 629 {
 630    // Empty deps are always true
 631    StateCache &State = PkgState[Pkg->ID];
 632    State.DepState = 0xFF;
 633
 634    // Check the Current state
 635    if (Pkg->CurrentVer != 0)
 636    {
 637       DepIterator D = Pkg.CurrentVer().DependsList();
 638       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 639    }
 640
 641    /* Check the candidate state. We do not compare against the whole as
 642       a candidate state but check the candidate version against the
 643       install states */
 644    if (State.CandidateVer != 0)
 645    {
 646       DepIterator D = State.CandidateVerIter(*this).DependsList();
 647       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 648    }
 649
 650    // Check target state which can only be current or installed
 651    if (State.InstallVer != 0)
 652    {
 653       DepIterator D = State.InstVerIter(*this).DependsList();
 654       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 655    }
 656 }
 657                                                                         /*}}}*/
 658 // DepCache::Update - Figure out all the state information              /*{{{*/
 659 // ---------------------------------------------------------------------
 660 /* This will figure out the state of all the packages and all the
 661    dependencies based on the current policy. */
 662 void pkgDepCache::Update(OpProgress *Prog)
 663 {
 664    iUsrSize = 0;
 665    iDownloadSize = 0;
 666    iDelCount = 0;
 667    iInstCount = 0;
 668    iKeepCount = 0;
 669    iBrokenCount = 0;
 670    iBadCount = 0;
 671
 672    // Perform the depends pass
 673    int Done = 0;
 674    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 675    {
 676       if (Prog != 0 && Done%20 == 0)
 677          Prog->Progress(Done);
 678       for (VerIterator V = I.VersionList(); V.end() != true; ++V)
 679       {
 680          unsigned char Group = 0;
 681
 682          for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 683          {
 684             // Build the dependency state.
 685             unsigned char &State = DepState[D->ID];
 686             State = DependencyState(D);
 687
 688             // Add to the group if we are within an or..
 689             Group |= State;
 690             State |= Group << 3;
 691             if ((D->CompareOp & Dep::Or) != Dep::Or)
 692                Group = 0;
 693
 694             // Invert for Conflicts
 695             if (D.IsNegative() == true)
 696                State = ~State;
 697          }
 698       }
 699
 700       // Compute the package dependency state and size additions
 701       AddSizes(I);
 702       UpdateVerState(I);
 703       AddStates(I);
 704    }
 705
 706    if (Prog != 0)
 707       Prog->Progress(Done);
 708
 709    readStateFile(Prog);
 710 }
 711                                                                         /*}}}*/
 712 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 713 // ---------------------------------------------------------------------
 714 /* This is a helper for update that only does the dep portion of the scan.
 715    It is mainly meant to scan reverse dependencies. */
 716 void pkgDepCache::Update(DepIterator D)
 717 {
 718    // Update the reverse deps
 719    for (;D.end() != true; ++D)
 720    {
 721       unsigned char &State = DepState[D->ID];
 722       State = DependencyState(D);
 723
 724       // Invert for Conflicts
 725       if (D.IsNegative() == true)
 726          State = ~State;
 727
 728       RemoveStates(D.ParentPkg());
 729       BuildGroupOrs(D.ParentVer());
 730       UpdateVerState(D.ParentPkg());
 731       AddStates(D.ParentPkg());
 732    }
 733 }
 734                                                                         /*}}}*/
 735 // DepCache::Update - Update the related deps of a package              /*{{{*/
 736 // ---------------------------------------------------------------------
 737 /* This is called whenever the state of a package changes. It updates
 738    all cached dependencies related to this package. */
 739 void pkgDepCache::Update(PkgIterator const &Pkg)
 740 {
 741    // Recompute the dep of the package
 742    RemoveStates(Pkg);
 743    UpdateVerState(Pkg);
 744    AddStates(Pkg);
 745
 746    // Update the reverse deps
 747    Update(Pkg.RevDependsList());
 748
 749    // Update the provides map for the current ver
 750    if (Pkg->CurrentVer != 0)
 751       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 752            P.end() != true; ++P)
 753          Update(P.ParentPkg().RevDependsList());
 754
 755    // Update the provides map for the candidate ver
 756    if (PkgState[Pkg->ID].CandidateVer != 0)
 757       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 758            P.end() != true; ++P)
 759          Update(P.ParentPkg().RevDependsList());
 760 }
 761                                                                         /*}}}*/
 762 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 763 // ---------------------------------------------------------------------
 764 /* */
 765 bool pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 766                            unsigned long Depth)
 767 {
 768    if (IsModeChangeOk(ModeKeep, Pkg, Depth, FromUser) == false)
 769       return false;
 770
 771    /* Reject an attempt to keep a non-source broken installed package, those
 772       must be upgraded */
 773    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 774        Pkg.CurrentVer().Downloadable() == false)
 775       return false;
 776
 777    /* We changed the soft state all the time so the UI is a bit nicer
 778       to use */
 779    StateCache &P = PkgState[Pkg->ID];
 780
 781    // Check that it is not already kept
 782    if (P.Mode == ModeKeep)
 783       return true;
 784
 785    if (Soft == true)
 786       P.iFlags |= AutoKept;
 787    else
 788       P.iFlags &= ~AutoKept;
 789
 790    ActionGroup group(*this);
 791
 792 #if 0 // reseting the autoflag here means we lose the
 793       // auto-mark information if a user selects a package for removal
 794       // but changes  his mind then and sets it for keep again
 795       // - this makes sense as default when all Garbage dependencies
 796       //   are automatically marked for removal (as aptitude does).
 797       //   setting a package for keep then makes it no longer autoinstalled
 798       //   for all other use-case this action is rather suprising
 799    if(FromUser && !P.Marked)
 800      P.Flags &= ~Flag::Auto;
 801 #endif
 802
 803    if (DebugMarker == true)
 804       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 805
 806    RemoveSizes(Pkg);
 807    RemoveStates(Pkg);
 808
 809    P.Mode = ModeKeep;
 810    if (Pkg->CurrentVer == 0)
 811       P.InstallVer = 0;
 812    else
 813       P.InstallVer = Pkg.CurrentVer();
 814
 815    AddStates(Pkg);
 816    Update(Pkg);
 817    AddSizes(Pkg);
 818
 819    return true;
 820 }
 821                                                                         /*}}}*/
 822 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 823 // ---------------------------------------------------------------------
 824 /* */
 825 bool pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 826                              unsigned long Depth, bool FromUser)
 827 {
 828    if (IsModeChangeOk(ModeDelete, Pkg, Depth, FromUser) == false)
 829       return false;
 830
 831    StateCache &P = PkgState[Pkg->ID];
 832
 833    // Check that it is not already marked for delete
 834    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 835        (Pkg.Purge() == true || rPurge == false))
 836       return true;
 837
 838    // check if we are allowed to remove the package
 839    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
 840       return false;
 841
 842    P.iFlags &= ~(AutoKept | Purge);
 843    if (rPurge == true)
 844       P.iFlags |= Purge;
 845
 846    ActionGroup group(*this);
 847
 848    if (DebugMarker == true)
 849       std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << Pkg << " FU=" << FromUser << std::endl;
 850
 851    RemoveSizes(Pkg);
 852    RemoveStates(Pkg);
 853
 854    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 855       P.Mode = ModeKeep;
 856    else
 857       P.Mode = ModeDelete;
 858    P.InstallVer = 0;
 859
 860    AddStates(Pkg);
 861    Update(Pkg);
 862    AddSizes(Pkg);
 863
 864    return true;
 865 }
 866                                                                         /*}}}*/
 867 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 868 // ---------------------------------------------------------------------
 869 /* The default implementation tries to prevent deletion of install requests.
 870    dpkg holds are enforced by the private IsModeChangeOk */
 871 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 872                               unsigned long Depth, bool FromUser)
 873 {
 874    if (FromUser == false && Pkg->CurrentVer == 0)
 875    {
 876       StateCache &P = PkgState[Pkg->ID];
 877       // Status == 2 means this applies for new installs only
 878       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
 879       {
 880          if (DebugMarker == true)
 881             std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << Pkg << std::endl;
 882          return false;
 883       }
 884    }
 885    return true;
 886 }
 887                                                                         /*}}}*/
 888 // DepCache::IsModeChangeOk - check if it is ok to change the mode      /*{{{*/
 889 // ---------------------------------------------------------------------
 890 /* this is used by all Mark methods on the very first line to check sanity
 891    and prevents mode changes for packages on hold for example.
 892    If you want to check Mode specific stuff you can use the virtual public
 893    Is<Mode>Ok methods instead */
 894 char const* PrintMode(char const mode)
 895 {
 896          switch (mode)
 897          {
 898          case pkgDepCache::ModeInstall: return "Install";
 899          case pkgDepCache::ModeKeep: return "Keep";
 900          case pkgDepCache::ModeDelete: return "Delete";
 901          default: return "UNKNOWN";
 902          }
 903 }
 904 bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
 905                                  unsigned long const Depth, bool const FromUser)
 906 {
 907    // we are not trying to hard…
 908    if (unlikely(Depth > 100))
 909       return false;
 910
 911    // general sanity
 912    if (unlikely(Pkg.end() == true || Pkg->VersionList == 0))
 913       return false;
 914
 915    // the user is always right
 916    if (FromUser == true)
 917       return true;
 918
 919    StateCache &P = PkgState[Pkg->ID];
 920
 921    // if previous state was set by user only user can reset it
 922    if ((P.iFlags & Protected) == Protected)
 923    {
 924       if (unlikely(DebugMarker == true) && P.Mode != mode)
 925          std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
 926                    << " of " << Pkg << " as its mode (" << PrintMode(P.Mode)
 927                    << ") is protected" << std::endl;
 928       return false;
 929    }
 930    // enforce dpkg holds
 931    else if (mode != ModeKeep && Pkg->SelectedState == pkgCache::State::Hold &&
 932             _config->FindB("APT::Ignore-Hold",false) == false)
 933    {
 934       if (unlikely(DebugMarker == true) && P.Mode != mode)
 935          std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
 936                    << " of " << Pkg << std::endl;
 937       return false;
 938    }
 939
 940    return true;
 941 }
 942                                                                         /*}}}*/
 943 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 944 // ---------------------------------------------------------------------
 945 /* */
 946 struct CompareProviders {
 947    pkgCache::PkgIterator const Pkg;
 948    CompareProviders(pkgCache::DepIterator const &Dep) : Pkg(Dep.TargetPkg()) {};
 949    //bool operator() (APT::VersionList::iterator const &AV, APT::VersionList::iterator const &BV)
 950    bool operator() (pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
 951    {
 952       pkgCache::PkgIterator const A = AV.ParentPkg();
 953       pkgCache::PkgIterator const B = BV.ParentPkg();
 954       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
 955       if (A->Group != B->Group)
 956       {
 957          if (A->Group == Pkg->Group && B->Group != Pkg->Group)
 958             return false;
 959          else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
 960             return true;
 961       }
 962       // we like essentials
 963       if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
 964       {
 965          if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 966             return false;
 967          else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 968             return true;
 969       }
 970       // higher priority seems like a good idea
 971       if (AV->Priority != BV->Priority)
 972          return AV->Priority < BV->Priority;
 973       // prefer native architecture
 974       if (strcmp(A.Arch(), B.Arch()) != 0)
 975       {
 976          if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
 977             return false;
 978          else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
 979             return true;
 980          std::vector<std::string> archs = APT::Configuration::getArchitectures();
 981          for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
 982             if (*a == A.Arch())
 983                return false;
 984             else if (*a == B.Arch())
 985                return true;
 986       }
 987       // unable to decide…
 988       return A->ID < B->ID;
 989    }
 990 };
 991 bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 992                               unsigned long Depth, bool FromUser,
 993                               bool ForceImportantDeps)
 994 {
 995    if (IsModeChangeOk(ModeInstall, Pkg, Depth, FromUser) == false)
 996       return false;
 997
 998    StateCache &P = PkgState[Pkg->ID];
 999
1000    // See if there is even any possible instalation candidate
1001    if (P.CandidateVer == 0)
1002       return false;
1003
1004    /* Check that it is not already marked for install and that it can be
1005       installed */
1006    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1007        (P.Mode == ModeInstall ||
1008         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1009    {
1010       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1011          return MarkKeep(Pkg, false, FromUser, Depth+1);
1012       return true;
1013    }
1014
1015    // check if we are allowed to install the package
1016    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1017       return false;
1018
1019    ActionGroup group(*this);
1020    P.iFlags &= ~AutoKept;
1021
1022    /* Target the candidate version and remove the autoflag. We reset the
1023       autoflag below if this was called recursively. Otherwise the user
1024       should have the ability to de-auto a package by changing its state */
1025    RemoveSizes(Pkg);
1026    RemoveStates(Pkg);
1027
1028    P.Mode = ModeInstall;
1029    P.InstallVer = P.CandidateVer;
1030
1031    if(FromUser)
1032      {
1033        // Set it to manual if it's a new install or already installed,
1034        // but only if its not marked by the autoremover (aptitude depend on this behavior)
1035        // or if we do automatic installation (aptitude never does it)
1036        if(P.Status == 2 || (Pkg->CurrentVer != 0 && (AutoInst == true || P.Marked == false)))
1037          P.Flags &= ~Flag::Auto;
1038      }
1039    else
1040      {
1041        // Set it to auto if this is a new install.
1042        if(P.Status == 2)
1043          P.Flags |= Flag::Auto;
1044      }
1045    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1046       P.Mode = ModeKeep;
1047
1048    AddStates(Pkg);
1049    Update(Pkg);
1050    AddSizes(Pkg);
1051
1052    if (AutoInst == false || _config->Find("APT::Solver", "internal") != "internal")
1053       return true;
1054
1055    if (DebugMarker == true)
1056       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1057
1058    DepIterator Dep = P.InstVerIter(*this).DependsList();
1059    for (; Dep.end() != true;)
1060    {
1061       // Grok or groups
1062       DepIterator Start = Dep;
1063       bool Result = true;
1064       unsigned Ors = 0;
1065       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1066       {
1067          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1068
1069          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1070             Result = false;
1071       }
1072
1073       // Dep is satisfied okay.
1074       if (Result == false)
1075          continue;
1076
1077       /* Check if this dep should be consider for install. If it is a user
1078          defined important dep and we are installed a new package then
1079          it will be installed. Otherwise we only check for important
1080          deps that have changed from the installed version
1081       */
1082       if (IsImportantDep(Start) == false)
1083          continue;
1084
1085       /* If we are in an or group locate the first or that can
1086          succeed. We have already cached this.. */
1087       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1088          ++Start;
1089       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
1090       {
1091          if(DebugAutoInstall == true)
1092             std::clog << OutputInDepth(Depth) << Start << " can't be satisfied!" << std::endl;
1093          if (Start.IsCritical() == false)
1094             continue;
1095          // if the dependency was critical, we can't install it, so remove it again
1096          MarkDelete(Pkg,false,Depth + 1, false);
1097          return false;
1098       }
1099
1100       /* Check if any ImportantDep() (but not Critical) were added
1101        * since we installed the package.  Also check for deps that
1102        * were satisfied in the past: for instance, if a version
1103        * restriction in a Recommends was tightened, upgrading the
1104        * package should follow that Recommends rather than causing the
1105        * dependency to be removed. (bug #470115)
1106        */
1107       if (Pkg->CurrentVer != 0 && ForceImportantDeps == false && Start.IsCritical() == false)
1108       {
1109          bool isNewImportantDep = true;
1110          bool isPreviouslySatisfiedImportantDep = false;
1111          for (DepIterator D = Pkg.CurrentVer().DependsList(); D.end() != true; ++D)
1112          {
1113             //FIXME: Should we handle or-group better here?
1114             // We do not check if the package we look for is part of the same or-group
1115             // we might find while searching, but could that really be a problem?
1116             if (D.IsCritical() == true || IsImportantDep(D) == false ||
1117                 Start.TargetPkg() != D.TargetPkg())
1118                continue;
1119
1120             isNewImportantDep = false;
1121
1122             while ((D->CompareOp & Dep::Or) != 0)
1123                ++D;
1124
1125             isPreviouslySatisfiedImportantDep = (((*this)[D] & DepGNow) != 0);
1126             if (isPreviouslySatisfiedImportantDep == true)
1127                break;
1128          }
1129
1130          if(isNewImportantDep == true)
1131          {
1132             if (DebugAutoInstall == true)
1133                std::clog << OutputInDepth(Depth) << "new important dependency: "
1134                          << Start.TargetPkg().FullName() << std::endl;
1135          }
1136          else if(isPreviouslySatisfiedImportantDep == true)
1137          {
1138             if (DebugAutoInstall == true)
1139                std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1140                          << Start.TargetPkg().FullName() << std::endl;
1141          }
1142          else
1143          {
1144             if (DebugAutoInstall == true)
1145                std::clog << OutputInDepth(Depth) << "ignore old unsatisfied important dependency on "
1146                          << Start.TargetPkg().FullName() << std::endl;
1147             continue;
1148          }
1149       }
1150
1151       /* This bit is for processing the possibilty of an install/upgrade
1152          fixing the problem */
1153       if (Start->Type != Dep::DpkgBreaks &&
1154           (DepState[Start->ID] & DepCVer) == DepCVer)
1155       {
1156          APT::VersionList verlist;
1157          pkgCache::VerIterator Cand = PkgState[Start.TargetPkg()->ID].CandidateVerIter(*this);
1158          if (Cand.end() == false && VS().CheckDep(Cand.VerStr(), Start->CompareOp, Start.TargetVer()) == true)
1159             verlist.insert(Cand);
1160          for (PrvIterator Prv = Start.TargetPkg().ProvidesList(); Prv.end() != true; ++Prv)
1161          {
1162             pkgCache::VerIterator V = Prv.OwnerVer();
1163             pkgCache::VerIterator Cand = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1164             if (Cand.end() == true || V != Cand ||
1165                 VS().CheckDep(Cand.VerStr(), Start->CompareOp, Start.TargetVer()) == false)
1166                continue;
1167             verlist.insert(Cand);
1168          }
1169          CompareProviders comp(Start);
1170          APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
1171
1172          if (InstVer != verlist.end())
1173          {
1174             pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
1175             if(DebugAutoInstall == true)
1176                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1177                          << " as " << Start.DepType() << " of " << Pkg.Name()
1178                          << std::endl;
1179             // now check if we should consider it a automatic dependency or not
1180             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1181             {
1182                if(DebugAutoInstall == true)
1183                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1184                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1185                MarkInstall(InstPkg,true,Depth + 1, true);
1186             }
1187             else
1188             {
1189                // mark automatic dependency
1190                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1191                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1192                if (InstPkg->CurrentVer == 0)
1193                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1194             }
1195          }
1196          continue;
1197       }
1198
1199       /* For conflicts we just de-install the package and mark as auto,
1200          Conflicts may not have or groups.  For dpkg's Breaks we try to
1201          upgrade the package. */
1202       if (Start.IsNegative() == true)
1203       {
1204          SPtrArray<Version *> List = Start.AllTargets();
1205          for (Version **I = List; *I != 0; I++)
1206          {
1207             VerIterator Ver(*this,*I);
1208             PkgIterator Pkg = Ver.ParentPkg();
1209
1210             /* The List includes all packages providing this dependency,
1211                even providers which are not installed, so skip them. */
1212             if (PkgState[Pkg->ID].InstallVer == 0)
1213                continue;
1214
1215             if (PkgState[Pkg->ID].CandidateVer != *I &&
1216                 Start->Type == Dep::DpkgBreaks &&
1217                 MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps) == true)
1218                continue;
1219             else if (MarkDelete(Pkg,false,Depth + 1, false) == false)
1220                break;
1221          }
1222          continue;
1223       }
1224    }
1225
1226    return Dep.end() == true;
1227 }
1228                                                                         /*}}}*/
1229 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1230 // ---------------------------------------------------------------------
1231 /* The default implementation does nothing.
1232    dpkg holds are enforced by the private IsModeChangeOk */
1233 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1234                               unsigned long Depth, bool FromUser)
1235 {
1236    return true;
1237 }
1238                                                                         /*}}}*/
1239 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1240 // ---------------------------------------------------------------------
1241 /* */
1242 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1243 {
1244    if (unlikely(Pkg.end() == true))
1245       return;
1246
1247    ActionGroup group(*this);
1248
1249    RemoveSizes(Pkg);
1250    RemoveStates(Pkg);
1251
1252    StateCache &P = PkgState[Pkg->ID];
1253    if (To == true)
1254       P.iFlags |= ReInstall;
1255    else
1256       P.iFlags &= ~ReInstall;
1257
1258    AddStates(Pkg);
1259    AddSizes(Pkg);
1260 }
1261                                                                         /*}}}*/
1262 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1263 // ---------------------------------------------------------------------
1264 /* */
1265 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1266 {
1267    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1268    StateCache &P = PkgState[Pkg->ID];
1269
1270    if (P.CandidateVer == TargetVer)
1271       return;
1272
1273    ActionGroup group(*this);
1274
1275    RemoveSizes(Pkg);
1276    RemoveStates(Pkg);
1277
1278    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1279       P.InstallVer = (Version *)TargetVer;
1280    P.CandidateVer = (Version *)TargetVer;
1281    P.Update(Pkg,*this);
1282
1283    AddStates(Pkg);
1284    Update(Pkg);
1285    AddSizes(Pkg);
1286
1287 }
1288                                                                         /*}}}*/
1289 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1290 // ---------------------------------------------------------------------
1291 /* changes the candidate of a package and walks over all its dependencies
1292    to check if it needs to change the candidate of the dependency, too,
1293    to reach a installable versionstate */
1294 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1295                                         std::string const &TargetRel)
1296 {
1297    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1298    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1299 }
1300 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1301                                         std::string const &TargetRel,
1302                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1303 {
1304    ActionGroup group(*this);
1305    SetCandidateVersion(TargetVer);
1306
1307    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1308       return true;
1309
1310    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1311    // save the position of the last element we will not undo - if we have to
1312    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1313
1314    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1315    {
1316       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1317           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1318            IsImportantDep(D) == false))
1319          continue;
1320
1321       // walk over an or-group and check if we need to do anything
1322       // for simpilicity no or-group is handled as a or-group including one dependency
1323       pkgCache::DepIterator Start = D;
1324       bool itsFine = false;
1325       for (bool stillOr = true; stillOr == true; ++Start)
1326       {
1327          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1328          pkgCache::PkgIterator const P = Start.TargetPkg();
1329          // virtual packages can't be a solution
1330          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1331             continue;
1332          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1333          // no versioned dependency - but is it installable?
1334          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1335          {
1336             // Check if one of the providers is installable
1337             if (P->ProvidesList != 0)
1338             {
1339                pkgCache::PrvIterator Prv = P.ProvidesList();
1340                for (; Prv.end() == false; ++Prv)
1341                {
1342                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1343                   if (C.end() == true || C != Prv.OwnerVer() ||
1344                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1345                      continue;
1346                   break;
1347                }
1348                if (Prv.end() == true)
1349                   continue;
1350             }
1351             // no providers, so check if we have an installable candidate version
1352             else if (Cand.end() == true ||
1353                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1354                continue;
1355             itsFine = true;
1356             break;
1357          }
1358          if (Cand.end() == true)
1359             continue;
1360          // check if the current candidate is enough for the versioned dependency - and installable?
1361          if (VS().CheckDep(P.CandVersion(), Start->CompareOp, Start.TargetVer()) == true &&
1362              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1363          {
1364             itsFine = true;
1365             break;
1366          }
1367       }
1368
1369       if (itsFine == true) {
1370          // something in the or-group was fine, skip all other members
1371          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1372          continue;
1373       }
1374
1375       // walk again over the or-group and check each if a candidate switch would help
1376       itsFine = false;
1377       for (bool stillOr = true; stillOr == true; ++D)
1378       {
1379          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1380          // changing candidate will not help if the dependency is not versioned
1381          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1382          {
1383             if (stillOr == true)
1384                continue;
1385             break;
1386          }
1387
1388          pkgCache::VerIterator V;
1389          if (TargetRel == "newest")
1390             V = D.TargetPkg().VersionList();
1391          else
1392             V = Match.Find(D.TargetPkg());
1393
1394          // check if the version from this release could satisfy the dependency
1395          if (V.end() == true || VS().CheckDep(V.VerStr(), D->CompareOp, D.TargetVer()) == false)
1396          {
1397             if (stillOr == true)
1398                continue;
1399             break;
1400          }
1401
1402          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1403          if (V == oldCand)
1404          {
1405             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1406             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1407                  c != Changed.end(); ++c)
1408             {
1409                if (c->first->ParentPkg != V->ParentPkg)
1410                   continue;
1411                itsFine = true;
1412                break;
1413             }
1414          }
1415
1416          if (itsFine == false)
1417          {
1418             // change the candidate
1419             Changed.push_back(make_pair(oldCand, TargetVer));
1420             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1421             {
1422                if (stillOr == false)
1423                   break;
1424                // undo the candidate changing
1425                SetCandidateVersion(oldCand);
1426                Changed.pop_back();
1427                continue;
1428             }
1429             itsFine = true;
1430          }
1431
1432          // something in the or-group was fine, skip all other members
1433          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1434          break;
1435       }
1436
1437       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1438       {
1439          // undo all changes which aren't lead to a solution
1440          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1441               c != Changed.end(); ++c)
1442             SetCandidateVersion(c->first);
1443          Changed.erase(newChanged, Changed.end());
1444          return false;
1445       }
1446    }
1447    return true;
1448 }
1449                                                                         /*}}}*/
1450 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1451 // ---------------------------------------------------------------------
1452 /* */
1453 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1454 {
1455   StateCache &state = PkgState[Pkg->ID];
1456
1457   ActionGroup group(*this);
1458
1459   if(Auto)
1460     state.Flags |= Flag::Auto;
1461   else
1462     state.Flags &= ~Flag::Auto;
1463 }
1464                                                                         /*}}}*/
1465 // StateCache::Update - Compute the various static display things       /*{{{*/
1466 // ---------------------------------------------------------------------
1467 /* This is called whenever the Candidate version changes. */
1468 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1469 {
1470    // Some info
1471    VerIterator Ver = CandidateVerIter(Cache);
1472
1473    // Use a null string or the version string
1474    if (Ver.end() == true)
1475       CandVersion = "";
1476    else
1477       CandVersion = Ver.VerStr();
1478
1479    // Find the current version
1480    CurVersion = "";
1481    if (Pkg->CurrentVer != 0)
1482       CurVersion = Pkg.CurrentVer().VerStr();
1483
1484    // Strip off the epochs for display
1485    CurVersion = StripEpoch(CurVersion);
1486    CandVersion = StripEpoch(CandVersion);
1487
1488    // Figure out if its up or down or equal
1489    Status = Ver.CompareVer(Pkg.CurrentVer());
1490    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1491      Status = 2;
1492 }
1493                                                                         /*}}}*/
1494 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1495 // ---------------------------------------------------------------------
1496 /* */
1497 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1498 {
1499    if (Ver == 0)
1500       return 0;
1501
1502    // Strip any epoch
1503    for (const char *I = Ver; *I != 0; I++)
1504       if (*I == ':')
1505          return I + 1;
1506    return Ver;
1507 }
1508                                                                         /*}}}*/
1509 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1510 // ---------------------------------------------------------------------
1511 /* The default just returns the highest available version that is not
1512    a source and automatic. */
1513 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1514 {
1515    /* Not source/not automatic versions cannot be a candidate version
1516       unless they are already installed */
1517    VerIterator Last(*(pkgCache *)this,0);
1518
1519    for (VerIterator I = Pkg.VersionList(); I.end() == false; ++I)
1520    {
1521       if (Pkg.CurrentVer() == I)
1522          return I;
1523
1524       for (VerFileIterator J = I.FileList(); J.end() == false; ++J)
1525       {
1526          if ((J.File()->Flags & Flag::NotSource) != 0)
1527             continue;
1528
1529          /* Stash the highest version of a not-automatic source, we use it
1530             if there is nothing better */
1531          if ((J.File()->Flags & Flag::NotAutomatic) != 0 ||
1532              (J.File()->Flags & Flag::ButAutomaticUpgrades) != 0)
1533          {
1534             if (Last.end() == true)
1535                Last = I;
1536             continue;
1537          }
1538
1539          return I;
1540       }
1541    }
1542
1543    return Last;
1544 }
1545                                                                         /*}}}*/
1546 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1547 // ---------------------------------------------------------------------
1548 /* */
1549 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
1550 {
1551    if(Dep.IsCritical())
1552       return true;
1553    else if(Dep->Type == pkgCache::Dep::Recommends)
1554    {
1555       if (InstallRecommends)
1556          return true;
1557       // we suport a special mode to only install-recommends for certain
1558       // sections
1559       // FIXME: this is a meant as a temporarly solution until the
1560       //        recommends are cleaned up
1561       const char *sec = Dep.ParentVer().Section();
1562       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1563          return true;
1564    }
1565    else if(Dep->Type == pkgCache::Dep::Suggests)
1566       return InstallSuggests;
1567
1568    return false;
1569 }
1570                                                                         /*}}}*/
1571 // Policy::GetPriority - Get the priority of the package pin            /*{{{*/
1572 signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &Pkg)
1573 { return 0; };
1574 signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &File)
1575 { return 0; };
1576                                                                         /*}}}*/
1577 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1578 {
1579   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1580   if(f->wasConstructedSuccessfully())
1581     return f;
1582   else
1583     {
1584       delete f;
1585       return NULL;
1586     }
1587 }
1588                                                                         /*}}}*/
1589 bool pkgDepCache::MarkFollowsRecommends()
1590 {
1591   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1592 }
1593
1594 bool pkgDepCache::MarkFollowsSuggests()
1595 {
1596   return _config->FindB("APT::AutoRemove::SuggestsImportant", true);
1597 }
1598
1599 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1600 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1601 {
1602    if (_config->Find("APT::Solver", "internal") != "internal")
1603       return true;
1604
1605    bool follow_recommends;
1606    bool follow_suggests;
1607    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1608
1609    // init the states
1610    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1611    {
1612       PkgState[p->ID].Marked  = false;
1613       PkgState[p->ID].Garbage = false;
1614
1615       // debug output
1616       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1617          std::clog << "AutoDep: " << p.FullName() << std::endl;
1618    }
1619
1620    // init vars
1621    follow_recommends = MarkFollowsRecommends();
1622    follow_suggests   = MarkFollowsSuggests();
1623
1624
1625
1626    // do the mark part, this is the core bit of the algorithm
1627    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1628    {
1629       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1630           (p->Flags & Flag::Essential) ||
1631           userFunc.InRootSet(p) ||
1632           // be nice even then a required package violates the policy (#583517)
1633           // and do the full mark process also for required packages
1634           (p.CurrentVer().end() != true &&
1635            p.CurrentVer()->Priority == pkgCache::State::Required))
1636       {
1637          // the package is installed (and set to keep)
1638          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1639             MarkPackage(p, p.CurrentVer(),
1640                         follow_recommends, follow_suggests);
1641          // the package is to be installed
1642          else if(PkgState[p->ID].Install())
1643             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1644                         follow_recommends, follow_suggests);
1645       }
1646    }
1647
1648    return true;
1649 }
1650                                                                         /*}}}*/
1651 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1652 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1653                               const pkgCache::VerIterator &ver,
1654                               bool const &follow_recommends,
1655                               bool const &follow_suggests)
1656 {
1657    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1658
1659    // if we are marked already we are done
1660    if(state.Marked)
1661       return;
1662
1663    VerIterator const currver = pkg.CurrentVer();
1664    VerIterator const instver = state.InstVerIter(*this);
1665
1666 #if 0
1667    VerIterator const candver = state.CandidateVerIter(*this);
1668
1669    // If a package was garbage-collected but is now being marked, we
1670    // should re-select it
1671    // For cases when a pkg is set to upgrade and this trigger the
1672    // removal of a no-longer used dependency.  if the pkg is set to
1673    // keep again later it will result in broken deps
1674    if(state.Delete() && state.RemoveReason = Unused)
1675    {
1676       if(ver==candver)
1677          mark_install(pkg, false, false, NULL);
1678       else if(ver==pkg.CurrentVer())
1679          MarkKeep(pkg, false, false);
1680
1681       instver=state.InstVerIter(*this);
1682    }
1683 #endif
1684
1685    // For packages that are not going to be removed, ignore versions
1686    // other than the InstVer.  For packages that are going to be
1687    // removed, ignore versions other than the current version.
1688    if(!(ver == instver && !instver.end()) &&
1689       !(ver == currver && instver.end() && !ver.end()))
1690       return;
1691
1692    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1693
1694    if(debug_autoremove)
1695      {
1696        std::clog << "Marking: " << pkg.FullName();
1697        if(!ver.end())
1698          std::clog << " " << ver.VerStr();
1699        if(!currver.end())
1700          std::clog << ", Curr=" << currver.VerStr();
1701        if(!instver.end())
1702          std::clog << ", Inst=" << instver.VerStr();
1703        std::clog << std::endl;
1704      }
1705
1706    state.Marked=true;
1707
1708    if(ver.end() == true)
1709       return;
1710
1711      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1712      {
1713         if(d->Type == Dep::Depends ||
1714            d->Type == Dep::PreDepends ||
1715            (follow_recommends &&
1716             d->Type == Dep::Recommends) ||
1717            (follow_suggests &&
1718             d->Type == Dep::Suggests))
1719         {
1720            // Try all versions of this package.
1721            for(VerIterator V = d.TargetPkg().VersionList();
1722                !V.end(); ++V)
1723            {
1724               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1725               {
1726                 if(debug_autoremove)
1727                   {
1728                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1729                               << " " << d.ParentVer().VerStr() << " "
1730                               << d.DepType() << " " << d.TargetPkg().FullName();
1731                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1732                       {
1733                         std::clog << " (" << d.CompType() << " "
1734                                   << d.TargetVer() << ")";
1735                       }
1736                     std::clog << std::endl;
1737                   }
1738                  MarkPackage(V.ParentPkg(), V,
1739                              follow_recommends, follow_suggests);
1740               }
1741            }
1742            // Now try virtual packages
1743            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1744                !prv.end(); ++prv)
1745            {
1746               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1747                                        d.TargetVer()))
1748               {
1749                 if(debug_autoremove)
1750                   {
1751                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1752                               << d.ParentVer().VerStr() << " "
1753                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1754                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1755                       {
1756                         std::clog << " (" << d.CompType() << " "
1757                                   << d.TargetVer() << ")";
1758                       }
1759                     std::clog << ", provided by "
1760                               << prv.OwnerPkg().FullName() << " "
1761                               << prv.OwnerVer().VerStr()
1762                               << std::endl;
1763                   }
1764
1765                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1766                              follow_recommends, follow_suggests);
1767               }
1768            }
1769         }
1770      }
1771 }
1772                                                                         /*}}}*/
1773 bool pkgDepCache::Sweep()                                               /*{{{*/
1774 {
1775    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1776
1777    // do the sweep
1778    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1779    {
1780      StateCache &state=PkgState[p->ID];
1781
1782      // skip required packages
1783      if (!p.CurrentVer().end() &&
1784          (p.CurrentVer()->Priority == pkgCache::State::Required))
1785         continue;
1786
1787      // if it is not marked and it is installed, it's garbage
1788      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1789      {
1790         state.Garbage=true;
1791         if(debug_autoremove)
1792            std::clog << "Garbage: " << p.FullName() << std::endl;
1793      }
1794   }
1795
1796    return true;
1797 }
1798                                                                         /*}}}*/