apt-pkg/depcache.cc

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