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