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