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                                                                         /*}}}*/
 901 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 902 // ---------------------------------------------------------------------
 903 /* The default implementation just honors dpkg hold
 904    But an application using this library can override this method
 905    to control the MarkDelete behaviour */
 906 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 907                               unsigned long Depth, bool FromUser)
 908 {
 909    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
 910    {
 911       if (DebugMarker == true)
 912          std::clog << OutputInDepth(Depth) << "Hold prevents MarkDelete of " << Pkg << " FU=" << FromUser << std::endl;
 913       return false;
 914    }
 915    return true;
 916 }
 917                                                                         /*}}}*/
 918 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 919 // ---------------------------------------------------------------------
 920 /* */
 921 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 922                               unsigned long Depth, bool FromUser,
 923                               bool ForceImportantDeps)
 924 {
 925    if (Depth > 100)
 926       return;
 927
 928    // Simplifies other routines.
 929    if (Pkg.end() == true)
 930       return;
 931
 932    ActionGroup group(*this);
 933
 934    /* Check that it is not already marked for install and that it can be
 935       installed */
 936    StateCache &P = PkgState[Pkg->ID];
 937    P.iFlags &= ~AutoKept;
 938    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
 939        (P.Mode == ModeInstall ||
 940         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 941    {
 942       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 943          MarkKeep(Pkg, false, FromUser, Depth+1);
 944       return;
 945    }
 946
 947    // See if there is even any possible instalation candidate
 948    if (P.CandidateVer == 0)
 949       return;
 950    // We dont even try to install virtual packages..
 951    if (Pkg->VersionList == 0)
 952       return;
 953
 954    // check if we are allowed to install the package
 955    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
 956       return;
 957
 958    /* Target the candidate version and remove the autoflag. We reset the
 959       autoflag below if this was called recursively. Otherwise the user
 960       should have the ability to de-auto a package by changing its state */
 961    RemoveSizes(Pkg);
 962    RemoveStates(Pkg);
 963
 964    P.Mode = ModeInstall;
 965    P.InstallVer = P.CandidateVer;
 966
 967    if(FromUser)
 968      {
 969        // Set it to manual if it's a new install or cancelling the
 970        // removal of a garbage package.
 971        if(P.Status == 2 || (!Pkg.CurrentVer().end() && !P.Marked))
 972          P.Flags &= ~Flag::Auto;
 973      }
 974    else
 975      {
 976        // Set it to auto if this is a new install.
 977        if(P.Status == 2)
 978          P.Flags |= Flag::Auto;
 979      }
 980    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
 981       P.Mode = ModeKeep;
 982
 983    AddStates(Pkg);
 984    Update(Pkg);
 985    AddSizes(Pkg);
 986
 987    if (AutoInst == false)
 988       return;
 989
 990    if (DebugMarker == true)
 991       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
 992
 993    DepIterator Dep = P.InstVerIter(*this).DependsList();
 994    for (; Dep.end() != true;)
 995    {
 996       // Grok or groups
 997       DepIterator Start = Dep;
 998       bool Result = true;
 999       unsigned Ors = 0;
1000       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
1001       {
1002          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1003
1004          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1005             Result = false;
1006       }
1007
1008       // Dep is satisfied okay.
1009       if (Result == false)
1010          continue;
1011
1012       /* Check if this dep should be consider for install. If it is a user
1013          defined important dep and we are installed a new package then
1014          it will be installed. Otherwise we only check for important
1015          deps that have changed from the installed version
1016       */
1017       if (IsImportantDep(Start) == false)
1018          continue;
1019
1020       /* Check if any ImportantDep() (but not Critical) were added
1021        * since we installed the package.  Also check for deps that
1022        * were satisfied in the past: for instance, if a version
1023        * restriction in a Recommends was tightened, upgrading the
1024        * package should follow that Recommends rather than causing the
1025        * dependency to be removed. (bug #470115)
1026        */
1027       bool isNewImportantDep = false;
1028       bool isPreviouslySatisfiedImportantDep = false;
1029       if(!ForceImportantDeps && !Start.IsCritical())
1030       {
1031          bool found=false;
1032          VerIterator instVer = Pkg.CurrentVer();
1033          if(!instVer.end())
1034          {
1035            for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
1036              {
1037                //FIXME: deal better with or-groups(?)
1038                DepIterator LocalStart = D;
1039
1040                if(IsImportantDep(D) && !D.IsCritical() &&
1041                   Start.TargetPkg() == D.TargetPkg())
1042                  {
1043                    if(!isPreviouslySatisfiedImportantDep)
1044                      {
1045                        DepIterator D2 = D;
1046                        while((D2->CompareOp & Dep::Or) != 0)
1047                          ++D2;
1048
1049                        isPreviouslySatisfiedImportantDep =
1050                          (((*this)[D2] & DepGNow) != 0);
1051                      }
1052
1053                    found=true;
1054                  }
1055              }
1056             // this is a new dep if it was not found to be already
1057             // a important dep of the installed pacakge
1058             isNewImportantDep = !found;
1059          }
1060       }
1061       if(isNewImportantDep)
1062          if(DebugAutoInstall == true)
1063             std::clog << OutputInDepth(Depth) << "new important dependency: "
1064                       << Start.TargetPkg().Name() << std::endl;
1065       if(isPreviouslySatisfiedImportantDep)
1066         if(DebugAutoInstall == true)
1067           std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1068                     << Start.TargetPkg().Name() << std::endl;
1069
1070       // skip important deps if the package is already installed
1071       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
1072           && !isNewImportantDep && !isPreviouslySatisfiedImportantDep
1073           && !ForceImportantDeps)
1074          continue;
1075
1076       /* If we are in an or group locate the first or that can
1077          succeed. We have already cached this.. */
1078       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
1079          Start++;
1080
1081       /* This bit is for processing the possibilty of an install/upgrade
1082          fixing the problem */
1083       SPtrArray<Version *> List = Start.AllTargets();
1084       if (Start->Type != Dep::DpkgBreaks &&
1085           (DepState[Start->ID] & DepCVer) == DepCVer)
1086       {
1087          // Right, find the best version to install..
1088          Version **Cur = List;
1089          PkgIterator P = Start.TargetPkg();
1090          PkgIterator InstPkg(*Cache,0);
1091
1092          // See if there are direct matches (at the start of the list)
1093          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
1094          {
1095             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1096             if (PkgState[Pkg->ID].CandidateVer != *Cur)
1097                continue;
1098             InstPkg = Pkg;
1099             break;
1100          }
1101
1102          // Select the highest priority providing package
1103          if (InstPkg.end() == true)
1104          {
1105             pkgPrioSortList(*Cache,Cur);
1106             for (; *Cur != 0; Cur++)
1107             {
1108                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1109                if (PkgState[Pkg->ID].CandidateVer != *Cur)
1110                   continue;
1111                InstPkg = Pkg;
1112                break;
1113             }
1114          }
1115
1116          if (InstPkg.end() == false)
1117          {
1118             if(DebugAutoInstall == true)
1119                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1120                          << " as " << Start.DepType() << " of " << Pkg.Name()
1121                          << std::endl;
1122             // now check if we should consider it a automatic dependency or not
1123             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1124             {
1125                if(DebugAutoInstall == true)
1126                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1127                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1128                MarkInstall(InstPkg,true,Depth + 1, true);
1129             }
1130             else
1131             {
1132                // mark automatic dependency
1133                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1134                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1135                if (P->CurrentVer == 0)
1136                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1137             }
1138          }
1139          continue;
1140       }
1141
1142       /* For conflicts we just de-install the package and mark as auto,
1143          Conflicts may not have or groups.  For dpkg's Breaks we try to
1144          upgrade the package. */
1145       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
1146           Start->Type == Dep::DpkgBreaks)
1147       {
1148          for (Version **I = List; *I != 0; I++)
1149          {
1150             VerIterator Ver(*this,*I);
1151             PkgIterator Pkg = Ver.ParentPkg();
1152
1153             if (Start->Type != Dep::DpkgBreaks)
1154                MarkDelete(Pkg,false,Depth + 1, false);
1155             else if (PkgState[Pkg->ID].CandidateVer != *I)
1156                MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
1157          }
1158          continue;
1159       }
1160    }
1161 }
1162                                                                         /*}}}*/
1163 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1164 // ---------------------------------------------------------------------
1165 /* The default implementation just honors dpkg hold
1166    But an application using this library can override this method
1167    to control the MarkInstall behaviour */
1168 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1169                               unsigned long Depth, bool FromUser)
1170 {
1171    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
1172    {
1173       if (DebugMarker == true)
1174          std::clog << OutputInDepth(Depth) << "Hold prevents MarkInstall of " << Pkg << " FU=" << FromUser << std::endl;
1175       return false;
1176    }
1177    return true;
1178 }
1179                                                                         /*}}}*/
1180 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1181 // ---------------------------------------------------------------------
1182 /* */
1183 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1184 {
1185    ActionGroup group(*this);
1186
1187    RemoveSizes(Pkg);
1188    RemoveStates(Pkg);
1189
1190    StateCache &P = PkgState[Pkg->ID];
1191    if (To == true)
1192       P.iFlags |= ReInstall;
1193    else
1194       P.iFlags &= ~ReInstall;
1195
1196    AddStates(Pkg);
1197    AddSizes(Pkg);
1198 }
1199                                                                         /*}}}*/
1200 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1201 // ---------------------------------------------------------------------
1202 /* */
1203 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1204 {
1205    ActionGroup group(*this);
1206
1207    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1208    StateCache &P = PkgState[Pkg->ID];
1209
1210    RemoveSizes(Pkg);
1211    RemoveStates(Pkg);
1212
1213    if (P.CandidateVer == P.InstallVer)
1214       P.InstallVer = (Version *)TargetVer;
1215    P.CandidateVer = (Version *)TargetVer;
1216    P.Update(Pkg,*this);
1217
1218    AddStates(Pkg);
1219    Update(Pkg);
1220    AddSizes(Pkg);
1221 }
1222
1223 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1224 {
1225   StateCache &state = PkgState[Pkg->ID];
1226
1227   ActionGroup group(*this);
1228
1229   if(Auto)
1230     state.Flags |= Flag::Auto;
1231   else
1232     state.Flags &= ~Flag::Auto;
1233 }
1234                                                                         /*}}}*/
1235 // StateCache::Update - Compute the various static display things       /*{{{*/
1236 // ---------------------------------------------------------------------
1237 /* This is called whenever the Candidate version changes. */
1238 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1239 {
1240    // Some info
1241    VerIterator Ver = CandidateVerIter(Cache);
1242
1243    // Use a null string or the version string
1244    if (Ver.end() == true)
1245       CandVersion = "";
1246    else
1247       CandVersion = Ver.VerStr();
1248
1249    // Find the current version
1250    CurVersion = "";
1251    if (Pkg->CurrentVer != 0)
1252       CurVersion = Pkg.CurrentVer().VerStr();
1253
1254    // Strip off the epochs for display
1255    CurVersion = StripEpoch(CurVersion);
1256    CandVersion = StripEpoch(CandVersion);
1257
1258    // Figure out if its up or down or equal
1259    Status = Ver.CompareVer(Pkg.CurrentVer());
1260    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1261      Status = 2;
1262 }
1263                                                                         /*}}}*/
1264 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1265 // ---------------------------------------------------------------------
1266 /* */
1267 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1268 {
1269    if (Ver == 0)
1270       return 0;
1271
1272    // Strip any epoch
1273    for (const char *I = Ver; *I != 0; I++)
1274       if (*I == ':')
1275          return I + 1;
1276    return Ver;
1277 }
1278                                                                         /*}}}*/
1279 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1280 // ---------------------------------------------------------------------
1281 /* The default just returns the highest available version that is not
1282    a source and automatic. */
1283 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1284 {
1285    /* Not source/not automatic versions cannot be a candidate version
1286       unless they are already installed */
1287    VerIterator Last(*(pkgCache *)this,0);
1288
1289    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1290    {
1291       if (Pkg.CurrentVer() == I)
1292          return I;
1293
1294       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1295       {
1296          if ((J.File()->Flags & Flag::NotSource) != 0)
1297             continue;
1298
1299          /* Stash the highest version of a not-automatic source, we use it
1300             if there is nothing better */
1301          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1302          {
1303             if (Last.end() == true)
1304                Last = I;
1305             continue;
1306          }
1307
1308          return I;
1309       }
1310    }
1311
1312    return Last;
1313 }
1314                                                                         /*}}}*/
1315 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1316 // ---------------------------------------------------------------------
1317 /* */
1318 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1319 {
1320    if(Dep.IsCritical())
1321       return true;
1322    else if(Dep->Type == pkgCache::Dep::Recommends)
1323    {
1324       if ( _config->FindB("APT::Install-Recommends", false))
1325          return true;
1326       // we suport a special mode to only install-recommends for certain
1327       // sections
1328       // FIXME: this is a meant as a temporarly solution until the
1329       //        recommends are cleaned up
1330       const char *sec = Dep.ParentVer().Section();
1331       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1332          return true;
1333    }
1334    else if(Dep->Type == pkgCache::Dep::Suggests)
1335      return _config->FindB("APT::Install-Suggests", false);
1336
1337    return false;
1338 }
1339                                                                         /*}}}*/
1340 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()                   /*{{{*/
1341   : constructedSuccessfully(false)
1342 {
1343   Configuration::Item const *Opts;
1344   Opts = _config->Tree("APT::NeverAutoRemove");
1345   if (Opts != 0 && Opts->Child != 0)
1346     {
1347       Opts = Opts->Child;
1348       for (; Opts != 0; Opts = Opts->Next)
1349         {
1350           if (Opts->Value.empty() == true)
1351             continue;
1352
1353           regex_t *p = new regex_t;
1354           if(regcomp(p,Opts->Value.c_str(),
1355                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1356             {
1357               regfree(p);
1358               delete p;
1359               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1360               return;
1361             }
1362
1363           rootSetRegexp.push_back(p);
1364         }
1365     }
1366
1367   constructedSuccessfully = true;
1368 }
1369                                                                         /*}}}*/
1370 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()                  /*{{{*/
1371 {
1372   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1373     {
1374       regfree(rootSetRegexp[i]);
1375       delete rootSetRegexp[i];
1376     }
1377 }
1378                                                                         /*}}}*/
1379 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg) /*{{{*/
1380 {
1381    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1382       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1383          return true;
1384
1385    return false;
1386 }
1387                                                                         /*}}}*/
1388 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1389 {
1390   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1391   if(f->wasConstructedSuccessfully())
1392     return f;
1393   else
1394     {
1395       delete f;
1396       return NULL;
1397     }
1398 }
1399                                                                         /*}}}*/
1400 bool pkgDepCache::MarkFollowsRecommends()
1401 {
1402   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1403 }
1404
1405 bool pkgDepCache::MarkFollowsSuggests()
1406 {
1407   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1408 }
1409
1410 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1411 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1412 {
1413    bool follow_recommends;
1414    bool follow_suggests;
1415    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1416
1417    // init the states
1418    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1419    {
1420       PkgState[p->ID].Marked  = false;
1421       PkgState[p->ID].Garbage = false;
1422
1423       // debug output
1424       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1425          std::clog << "AutoDep: " << p.Name() << std::endl;
1426    }
1427
1428    // init vars
1429    follow_recommends = MarkFollowsRecommends();
1430    follow_suggests   = MarkFollowsSuggests();
1431
1432
1433
1434    // do the mark part, this is the core bit of the algorithm
1435    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1436    {
1437       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1438           (p->Flags & Flag::Essential) ||
1439           userFunc.InRootSet(p))
1440
1441       {
1442          // the package is installed (and set to keep)
1443          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1444             MarkPackage(p, p.CurrentVer(),
1445                         follow_recommends, follow_suggests);
1446          // the package is to be installed
1447          else if(PkgState[p->ID].Install())
1448             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1449                         follow_recommends, follow_suggests);
1450       }
1451    }
1452
1453    return true;
1454 }
1455                                                                         /*}}}*/
1456 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1457 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1458                               const pkgCache::VerIterator &ver,
1459                               bool follow_recommends,
1460                               bool follow_suggests)
1461 {
1462    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1463    VerIterator currver            = pkg.CurrentVer();
1464    VerIterator candver            = state.CandidateVerIter(*this);
1465    VerIterator instver            = state.InstVerIter(*this);
1466
1467 #if 0
1468    // If a package was garbage-collected but is now being marked, we
1469    // should re-select it
1470    // For cases when a pkg is set to upgrade and this trigger the
1471    // removal of a no-longer used dependency.  if the pkg is set to
1472    // keep again later it will result in broken deps
1473    if(state.Delete() && state.RemoveReason = Unused)
1474    {
1475       if(ver==candver)
1476          mark_install(pkg, false, false, NULL);
1477       else if(ver==pkg.CurrentVer())
1478          MarkKeep(pkg, false, false);
1479
1480       instver=state.InstVerIter(*this);
1481    }
1482 #endif
1483
1484    // For packages that are not going to be removed, ignore versions
1485    // other than the InstVer.  For packages that are going to be
1486    // removed, ignore versions other than the current version.
1487    if(!(ver == instver && !instver.end()) &&
1488       !(ver == currver && instver.end() && !ver.end()))
1489       return;
1490
1491    // if we are marked already we are done
1492    if(state.Marked)
1493       return;
1494
1495    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1496
1497    if(debug_autoremove)
1498      {
1499        std::clog << "Marking: " << pkg.Name();
1500        if(!ver.end())
1501          std::clog << " " << ver.VerStr();
1502        if(!currver.end())
1503          std::clog << ", Curr=" << currver.VerStr();
1504        if(!instver.end())
1505          std::clog << ", Inst=" << instver.VerStr();
1506        std::clog << std::endl;
1507      }
1508
1509    state.Marked=true;
1510
1511    if(!ver.end())
1512    {
1513      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1514      {
1515         if(d->Type == Dep::Depends ||
1516            d->Type == Dep::PreDepends ||
1517            (follow_recommends &&
1518             d->Type == Dep::Recommends) ||
1519            (follow_suggests &&
1520             d->Type == Dep::Suggests))
1521         {
1522            // Try all versions of this package.
1523            for(VerIterator V = d.TargetPkg().VersionList();
1524                !V.end(); ++V)
1525            {
1526               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1527               {
1528                 if(debug_autoremove)
1529                   {
1530                     std::clog << "Following dep: " << d.ParentPkg().Name()
1531                               << " " << d.ParentVer().VerStr() << " "
1532                               << d.DepType() << " "
1533                               << d.TargetPkg().Name();
1534                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1535                       {
1536                         std::clog << " (" << d.CompType() << " "
1537                                   << d.TargetVer() << ")";
1538                       }
1539                     std::clog << std::endl;
1540                   }
1541                  MarkPackage(V.ParentPkg(), V,
1542                              follow_recommends, follow_suggests);
1543               }
1544            }
1545            // Now try virtual packages
1546            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1547                !prv.end(); ++prv)
1548            {
1549               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1550                                        d.TargetVer()))
1551               {
1552                 if(debug_autoremove)
1553                   {
1554                     std::clog << "Following dep: " << d.ParentPkg().Name()
1555                               << " " << d.ParentVer().VerStr() << " "
1556                               << d.DepType() << " "
1557                               << d.TargetPkg().Name();
1558                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1559                       {
1560                         std::clog << " (" << d.CompType() << " "
1561                                   << d.TargetVer() << ")";
1562                       }
1563                     std::clog << ", provided by "
1564                               << prv.OwnerPkg().Name() << " "
1565                               << prv.OwnerVer().VerStr()
1566                               << std::endl;
1567                   }
1568
1569                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1570                              follow_recommends, follow_suggests);
1571               }
1572            }
1573         }
1574      }
1575    }
1576 }
1577                                                                         /*}}}*/
1578 bool pkgDepCache::Sweep()                                               /*{{{*/
1579 {
1580    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1581
1582    // do the sweep
1583    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1584    {
1585      StateCache &state=PkgState[p->ID];
1586
1587      // skip required packages
1588      if (!p.CurrentVer().end() &&
1589          (p.CurrentVer()->Priority == pkgCache::State::Required))
1590         continue;
1591
1592      // if it is not marked and it is installed, it's garbage
1593      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1594      {
1595         state.Garbage=true;
1596         if(debug_autoremove)
1597            std::cout << "Garbage: " << p.Name() << std::endl;
1598      }
1599   }
1600
1601    return true;
1602 }
1603                                                                         /*}}}*/