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 #ifdef __GNUG__
  12 #pragma implementation "apt-pkg/depcache.h"
  13 #endif
  14 #include <apt-pkg/depcache.h>
  15 #include <apt-pkg/version.h>
  16 #include <apt-pkg/error.h>
  17 #include <apt-pkg/sptr.h>
  18 #include <apt-pkg/algorithms.h>
  19
  20 #include <apt-pkg/fileutl.h>
  21 #include <apt-pkg/configuration.h>
  22 #include <apt-pkg/tagfile.h>
  23
  24 #include <iostream>
  25 #include <sstream>
  26 #include <apti18n.h>
  27                                                                         /*}}}*/
  28
  29 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  30 // ---------------------------------------------------------------------
  31 /* */
  32 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  33                 Cache(pCache), PkgState(0), DepState(0)
  34 {
  35    delLocalPolicy = 0;
  36    LocalPolicy = Plcy;
  37    if (LocalPolicy == 0)
  38       delLocalPolicy = LocalPolicy = new Policy;
  39 }
  40                                                                         /*}}}*/
  41 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
  42 // ---------------------------------------------------------------------
  43 /* */
  44 pkgDepCache::~pkgDepCache()
  45 {
  46    delete [] PkgState;
  47    delete [] DepState;
  48    delete delLocalPolicy;
  49 }
  50                                                                         /*}}}*/
  51 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
  52 // ---------------------------------------------------------------------
  53 /* This allocats the extension buffers and initializes them. */
  54 bool pkgDepCache::Init(OpProgress *Prog)
  55 {
  56    delete [] PkgState;
  57    delete [] DepState;
  58    PkgState = new StateCache[Head().PackageCount];
  59    DepState = new unsigned char[Head().DependsCount];
  60    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
  61    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
  62
  63    if (Prog != 0)
  64    {
  65       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
  66                             _("Building dependency tree"));
  67       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
  68    }
  69
  70    /* Set the current state of everything. In this state all of the
  71       packages are kept exactly as is. See AllUpgrade */
  72    int Done = 0;
  73    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
  74    {
  75       if (Prog != 0)
  76          Prog->Progress(Done);
  77
  78       // Find the proper cache slot
  79       StateCache &State = PkgState[I->ID];
  80       State.iFlags = 0;
  81
  82       // Figure out the install version
  83       State.CandidateVer = GetCandidateVer(I);
  84       State.InstallVer = I.CurrentVer();
  85       State.Mode = ModeKeep;
  86
  87       State.Update(I,*this);
  88    }
  89
  90    if (Prog != 0)
  91    {
  92
  93       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
  94                             Head().PackageCount,
  95                             _("Building dependency tree"));
  96       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
  97    }
  98
  99    Update(Prog);
 100
 101    if(Prog != 0)
 102       Prog->Done();
 103
 104    return true;
 105 }
 106                                                                         /*}}}*/
 107
 108 bool pkgDepCache::readStateFile(OpProgress *Prog)
 109 {
 110    FileFd state_file;
 111    string state = _config->FindDir("Dir::State") + "pkgstates";
 112    if(FileExists(state)) {
 113       state_file.Open(state, FileFd::ReadOnly);
 114       int file_size = state_file.Size();
 115       Prog->OverallProgress(0, file_size, 1,
 116                             _("Reading state information"));
 117
 118       pkgTagFile tagfile(&state_file);
 119       pkgTagSection section;
 120       int amt=0;
 121       while(tagfile.Step(section)) {
 122          string pkgname = section.FindS("Package");
 123          pkgCache::PkgIterator pkg=Cache->FindPkg(pkgname);
 124          // Silently ignore unknown packages and packages with no actual
 125          // version.
 126          if(!pkg.end() && !pkg.VersionList().end()) {
 127             short reason = section.FindI("Install-Reason", 0);
 128             if(reason > 0)
 129                PkgState[pkg->ID].Flags  |= pkgCache::Flag::Auto;
 130             if(_config->FindB("Debug::pkgAutoRemove",false))
 131                std::cout << "Install-Reason for: " << pkgname
 132                          << " is " << reason << std::endl;
 133             amt+=section.size();
 134             Prog->OverallProgress(amt, file_size, 1,
 135                                   _("Reading state information"));
 136          }
 137          Prog->OverallProgress(file_size, file_size, 1,
 138                                _("Reading state information"));
 139       }
 140    }
 141
 142    return true;
 143 }
 144
 145 bool pkgDepCache::writeStateFile(OpProgress *prog)
 146 {
 147    FileFd StateFile;
 148    string state = _config->FindDir("Dir::State") + "pkgstates";
 149
 150    if(_config->FindB("Debug::pkgAutoRemove",false))
 151       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 152
 153    if(!StateFile.Open(state, FileFd::WriteEmpty))
 154       return _error->Error(_("Failed to write StateFile %s"),
 155                            state.c_str());
 156
 157    std::ostringstream ostr;
 158    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end();pkg++) {
 159
 160       if(PkgState[pkg->ID].Flags & pkgCache::Flag::Auto) {
 161          if(_config->FindB("Debug::pkgAutoRemove",false))
 162             std::clog << "AutoInstal: " << pkg.Name() << std::endl;
 163          ostr.str(string(""));
 164          ostr << "Package: " << pkg.Name()
 165               << "\nInstall-Reason: 1\n\n";
 166          StateFile.Write(ostr.str().c_str(), ostr.str().size());
 167       }
 168    }
 169    return true;
 170 }
 171
 172 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 173 // ---------------------------------------------------------------------
 174 /* This first checks the dependency against the main target package and
 175    then walks along the package provides list and checks if each provides
 176    will be installed then checks the provides against the dep. Res will be
 177    set to the package which was used to satisfy the dep. */
 178 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 179 {
 180    Res = Dep.TargetPkg();
 181
 182    /* Check simple depends. A depends -should- never self match but
 183       we allow it anyhow because dpkg does. Technically it is a packaging
 184       bug. Conflicts may never self match */
 185    if (Dep.TargetPkg() != Dep.ParentPkg() ||
 186        (Dep->Type != Dep::Conflicts && Dep->Type != Dep::Obsoletes))
 187    {
 188       PkgIterator Pkg = Dep.TargetPkg();
 189       // Check the base package
 190       if (Type == NowVersion && Pkg->CurrentVer != 0)
 191          if (VS().CheckDep(Pkg.CurrentVer().VerStr(),Dep->CompareOp,
 192                                  Dep.TargetVer()) == true)
 193             return true;
 194
 195       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 196          if (VS().CheckDep(PkgState[Pkg->ID].InstVerIter(*this).VerStr(),
 197                                  Dep->CompareOp,Dep.TargetVer()) == true)
 198             return true;
 199
 200       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 201          if (VS().CheckDep(PkgState[Pkg->ID].CandidateVerIter(*this).VerStr(),
 202                                  Dep->CompareOp,Dep.TargetVer()) == true)
 203             return true;
 204    }
 205
 206    if (Dep->Type == Dep::Obsoletes)
 207       return false;
 208
 209    // Check the providing packages
 210    PrvIterator P = Dep.TargetPkg().ProvidesList();
 211    PkgIterator Pkg = Dep.ParentPkg();
 212    for (; P.end() != true; P++)
 213    {
 214       /* Provides may never be applied against the same package if it is
 215          a conflicts. See the comment above. */
 216       if (P.OwnerPkg() == Pkg && Dep->Type == Dep::Conflicts)
 217          continue;
 218
 219       // Check if the provides is a hit
 220       if (Type == NowVersion)
 221       {
 222          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 223             continue;
 224       }
 225
 226       if (Type == InstallVersion)
 227       {
 228          StateCache &State = PkgState[P.OwnerPkg()->ID];
 229          if (State.InstallVer != (Version *)P.OwnerVer())
 230             continue;
 231       }
 232
 233       if (Type == CandidateVersion)
 234       {
 235          StateCache &State = PkgState[P.OwnerPkg()->ID];
 236          if (State.CandidateVer != (Version *)P.OwnerVer())
 237             continue;
 238       }
 239
 240       // Compare the versions.
 241       if (VS().CheckDep(P.ProvideVersion(),Dep->CompareOp,Dep.TargetVer()) == true)
 242       {
 243          Res = P.OwnerPkg();
 244          return true;
 245       }
 246    }
 247
 248    return false;
 249 }
 250                                                                         /*}}}*/
 251 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 252 // ---------------------------------------------------------------------
 253 /* Call with Mult = -1 to preform the inverse opration */
 254 void pkgDepCache::AddSizes(const PkgIterator &Pkg,signed long Mult)
 255 {
 256    StateCache &P = PkgState[Pkg->ID];
 257
 258    if (Pkg->VersionList == 0)
 259       return;
 260
 261    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 262        P.Keep() == true)
 263       return;
 264
 265    // Compute the size data
 266    if (P.NewInstall() == true)
 267    {
 268       iUsrSize += (signed)(Mult*P.InstVerIter(*this)->InstalledSize);
 269       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 270       return;
 271    }
 272
 273    // Upgrading
 274    if (Pkg->CurrentVer != 0 &&
 275        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 276         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 277    {
 278       iUsrSize += (signed)(Mult*((signed)P.InstVerIter(*this)->InstalledSize -
 279                         (signed)Pkg.CurrentVer()->InstalledSize));
 280       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 281       return;
 282    }
 283
 284    // Reinstall
 285    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 286        P.Delete() == false)
 287    {
 288       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 289       return;
 290    }
 291
 292    // Removing
 293    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 294    {
 295       iUsrSize -= (signed)(Mult*Pkg.CurrentVer()->InstalledSize);
 296       return;
 297    }
 298 }
 299                                                                         /*}}}*/
 300 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 301 // ---------------------------------------------------------------------
 302 /* This routine is tricky to use, you must make sure that it is never
 303    called twice for the same package. This means the Remove/Add section
 304    should be as short as possible and not encompass any code that will
 305    calld Remove/Add itself. Remember, dependencies can be circular so
 306    while processing a dep for Pkg it is possible that Add/Remove
 307    will be called on Pkg */
 308 void pkgDepCache::AddStates(const PkgIterator &Pkg,int Add)
 309 {
 310    StateCache &State = PkgState[Pkg->ID];
 311
 312    // The Package is broken
 313    if ((State.DepState & DepInstMin) != DepInstMin)
 314       iBrokenCount += Add;
 315
 316    // Bad state
 317    if (Pkg.State() != PkgIterator::NeedsNothing)
 318       iBadCount += Add;
 319
 320    // Not installed
 321    if (Pkg->CurrentVer == 0)
 322    {
 323       if (State.Mode == ModeDelete &&
 324           (State.iFlags | Purge) == Purge && Pkg.Purge() == false)
 325          iDelCount += Add;
 326
 327       if (State.Mode == ModeInstall)
 328          iInstCount += Add;
 329       return;
 330    }
 331
 332    // Installed, no upgrade
 333    if (State.Status == 0)
 334    {
 335       if (State.Mode == ModeDelete)
 336          iDelCount += Add;
 337       else
 338          if ((State.iFlags & ReInstall) == ReInstall)
 339             iInstCount += Add;
 340
 341       return;
 342    }
 343
 344    // Alll 3 are possible
 345    if (State.Mode == ModeDelete)
 346       iDelCount += Add;
 347    if (State.Mode == ModeKeep)
 348       iKeepCount += Add;
 349    if (State.Mode == ModeInstall)
 350       iInstCount += Add;
 351 }
 352                                                                         /*}}}*/
 353 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 354 // ---------------------------------------------------------------------
 355 /* The or group results are stored in the last item of the or group. This
 356    allows easy detection of the state of a whole or'd group. */
 357 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 358 {
 359    unsigned char Group = 0;
 360
 361    for (DepIterator D = V.DependsList(); D.end() != true; D++)
 362    {
 363       // Build the dependency state.
 364       unsigned char &State = DepState[D->ID];
 365
 366       /* Invert for Conflicts. We have to do this twice to get the
 367          right sense for a conflicts group */
 368       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 369          State = ~State;
 370
 371       // Add to the group if we are within an or..
 372       State &= 0x7;
 373       Group |= State;
 374       State |= Group << 3;
 375       if ((D->CompareOp & Dep::Or) != Dep::Or)
 376          Group = 0;
 377
 378       // Invert for Conflicts
 379       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 380          State = ~State;
 381    }
 382 }
 383                                                                         /*}}}*/
 384 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 385 // ---------------------------------------------------------------------
 386 /* This is used to run over a dependency list and determine the dep
 387    state of the list, filtering it through both a Min check and a Policy
 388    check. The return result will have SetMin/SetPolicy low if a check
 389    fails. It uses the DepState cache for it's computations. */
 390 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 391                                        unsigned char SetMin,
 392                                        unsigned char SetPolicy)
 393 {
 394    unsigned char Dep = 0xFF;
 395
 396    while (D.end() != true)
 397    {
 398       // Compute a single dependency element (glob or)
 399       DepIterator Start = D;
 400       unsigned char State = 0;
 401       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 402       {
 403          State |= DepState[D->ID];
 404          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 405       }
 406
 407       // Minimum deps that must be satisfied to have a working package
 408       if (Start.IsCritical() == true)
 409          if ((State & Check) != Check)
 410             Dep &= ~SetMin;
 411
 412       // Policy deps that must be satisfied to install the package
 413       if (IsImportantDep(Start) == true &&
 414           (State & Check) != Check)
 415          Dep &= ~SetPolicy;
 416    }
 417
 418    return Dep;
 419 }
 420                                                                         /*}}}*/
 421 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 422 // ---------------------------------------------------------------------
 423 /* This is the main dependency computation bit. It computes the 3 main
 424    results for a dependencys, Now, Install and Candidate. Callers must
 425    invert the result if dealing with conflicts. */
 426 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 427 {
 428    unsigned char State = 0;
 429
 430    if (CheckDep(D,NowVersion) == true)
 431       State |= DepNow;
 432    if (CheckDep(D,InstallVersion) == true)
 433       State |= DepInstall;
 434    if (CheckDep(D,CandidateVersion) == true)
 435       State |= DepCVer;
 436
 437    return State;
 438 }
 439                                                                         /*}}}*/
 440 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 441 // ---------------------------------------------------------------------
 442 /* This determines the combined dependency representation of a package
 443    for its two states now and install. This is done by using the pre-generated
 444    dependency information. */
 445 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 446 {
 447    // Empty deps are always true
 448    StateCache &State = PkgState[Pkg->ID];
 449    State.DepState = 0xFF;
 450
 451    // Check the Current state
 452    if (Pkg->CurrentVer != 0)
 453    {
 454       DepIterator D = Pkg.CurrentVer().DependsList();
 455       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 456    }
 457
 458    /* Check the candidate state. We do not compare against the whole as
 459       a candidate state but check the candidate version against the
 460       install states */
 461    if (State.CandidateVer != 0)
 462    {
 463       DepIterator D = State.CandidateVerIter(*this).DependsList();
 464       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 465    }
 466
 467    // Check target state which can only be current or installed
 468    if (State.InstallVer != 0)
 469    {
 470       DepIterator D = State.InstVerIter(*this).DependsList();
 471       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 472    }
 473 }
 474                                                                         /*}}}*/
 475 // DepCache::Update - Figure out all the state information              /*{{{*/
 476 // ---------------------------------------------------------------------
 477 /* This will figure out the state of all the packages and all the
 478    dependencies based on the current policy. */
 479 void pkgDepCache::Update(OpProgress *Prog)
 480 {
 481    iUsrSize = 0;
 482    iDownloadSize = 0;
 483    iDelCount = 0;
 484    iInstCount = 0;
 485    iKeepCount = 0;
 486    iBrokenCount = 0;
 487    iBadCount = 0;
 488
 489    // Perform the depends pass
 490    int Done = 0;
 491    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 492    {
 493       if (Prog != 0 && Done%20 == 0)
 494          Prog->Progress(Done);
 495       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 496       {
 497          unsigned char Group = 0;
 498
 499          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 500          {
 501             // Build the dependency state.
 502             unsigned char &State = DepState[D->ID];
 503             State = DependencyState(D);
 504
 505             // Add to the group if we are within an or..
 506             Group |= State;
 507             State |= Group << 3;
 508             if ((D->CompareOp & Dep::Or) != Dep::Or)
 509                Group = 0;
 510
 511             // Invert for Conflicts
 512             if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 513                State = ~State;
 514          }
 515       }
 516
 517       // Compute the pacakge dependency state and size additions
 518       AddSizes(I);
 519       UpdateVerState(I);
 520       AddStates(I);
 521    }
 522
 523    readStateFile(Prog);
 524
 525    if (Prog != 0)
 526       Prog->Progress(Done);
 527 }
 528                                                                         /*}}}*/
 529 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 530 // ---------------------------------------------------------------------
 531 /* This is a helper for update that only does the dep portion of the scan.
 532    It is mainly ment to scan reverse dependencies. */
 533 void pkgDepCache::Update(DepIterator D)
 534 {
 535    // Update the reverse deps
 536    for (;D.end() != true; D++)
 537    {
 538       unsigned char &State = DepState[D->ID];
 539       State = DependencyState(D);
 540
 541       // Invert for Conflicts
 542       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 543          State = ~State;
 544
 545       RemoveStates(D.ParentPkg());
 546       BuildGroupOrs(D.ParentVer());
 547       UpdateVerState(D.ParentPkg());
 548       AddStates(D.ParentPkg());
 549    }
 550 }
 551                                                                         /*}}}*/
 552 // DepCache::Update - Update the related deps of a package              /*{{{*/
 553 // ---------------------------------------------------------------------
 554 /* This is called whenever the state of a package changes. It updates
 555    all cached dependencies related to this package. */
 556 void pkgDepCache::Update(PkgIterator const &Pkg)
 557 {
 558    // Recompute the dep of the package
 559    RemoveStates(Pkg);
 560    UpdateVerState(Pkg);
 561    AddStates(Pkg);
 562
 563    // Update the reverse deps
 564    Update(Pkg.RevDependsList());
 565
 566    // Update the provides map for the current ver
 567    if (Pkg->CurrentVer != 0)
 568       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 569            P.end() != true; P++)
 570          Update(P.ParentPkg().RevDependsList());
 571
 572    // Update the provides map for the candidate ver
 573    if (PkgState[Pkg->ID].CandidateVer != 0)
 574       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 575            P.end() != true; P++)
 576          Update(P.ParentPkg().RevDependsList());
 577 }
 578
 579                                                                         /*}}}*/
 580
 581 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 582 // ---------------------------------------------------------------------
 583 /* */
 584 void pkgDepCache::MarkKeep(PkgIterator const &Pkg,bool Soft)
 585 {
 586    // Simplifies other routines.
 587    if (Pkg.end() == true)
 588       return;
 589
 590    /* Reject an attempt to keep a non-source broken installed package, those
 591       must be upgraded */
 592    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 593        Pkg.CurrentVer().Downloadable() == false)
 594       return;
 595
 596    /* We changed the soft state all the time so the UI is a bit nicer
 597       to use */
 598    StateCache &P = PkgState[Pkg->ID];
 599    if (Soft == true)
 600       P.iFlags |= AutoKept;
 601    else
 602       P.iFlags &= ~AutoKept;
 603
 604    // Check that it is not already kept
 605    if (P.Mode == ModeKeep)
 606       return;
 607
 608    // We dont even try to keep virtual packages..
 609    if (Pkg->VersionList == 0)
 610       return;
 611
 612    P.Flags &= ~Flag::Auto;
 613    RemoveSizes(Pkg);
 614    RemoveStates(Pkg);
 615
 616    P.Mode = ModeKeep;
 617    if (Pkg->CurrentVer == 0)
 618       P.InstallVer = 0;
 619    else
 620       P.InstallVer = Pkg.CurrentVer();
 621
 622    AddStates(Pkg);
 623
 624    Update(Pkg);
 625
 626    AddSizes(Pkg);
 627 }
 628                                                                         /*}}}*/
 629 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 630 // ---------------------------------------------------------------------
 631 /* */
 632 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge)
 633 {
 634    // Simplifies other routines.
 635    if (Pkg.end() == true)
 636       return;
 637
 638    // Check that it is not already marked for delete
 639    StateCache &P = PkgState[Pkg->ID];
 640    P.iFlags &= ~(AutoKept | Purge);
 641    if (rPurge == true)
 642       P.iFlags |= Purge;
 643
 644    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 645        (Pkg.Purge() == true || rPurge == false))
 646       return;
 647
 648    // We dont even try to delete virtual packages..
 649    if (Pkg->VersionList == 0)
 650       return;
 651
 652    RemoveSizes(Pkg);
 653    RemoveStates(Pkg);
 654
 655    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 656       P.Mode = ModeKeep;
 657    else
 658       P.Mode = ModeDelete;
 659    P.InstallVer = 0;
 660    // This was not inverted before, but I think it should be
 661    P.Flags &= ~Flag::Auto;
 662
 663    AddStates(Pkg);
 664    Update(Pkg);
 665    AddSizes(Pkg);
 666 }
 667                                                                         /*}}}*/
 668 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 669 // ---------------------------------------------------------------------
 670 /* */
 671 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 672                               unsigned long Depth)
 673 {
 674    if (Depth > 100)
 675       return;
 676
 677    // Simplifies other routines.
 678    if (Pkg.end() == true)
 679       return;
 680
 681    /* Check that it is not already marked for install and that it can be
 682       installed */
 683    StateCache &P = PkgState[Pkg->ID];
 684    P.iFlags &= ~AutoKept;
 685    if (P.InstBroken() == false && (P.Mode == ModeInstall ||
 686         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 687    {
 688       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 689          MarkKeep(Pkg);
 690       return;
 691    }
 692
 693    // See if there is even any possible instalation candidate
 694    if (P.CandidateVer == 0)
 695       return;
 696
 697    // We dont even try to install virtual packages..
 698    if (Pkg->VersionList == 0)
 699       return;
 700
 701    /* Target the candidate version and remove the autoflag. We reset the
 702       autoflag below if this was called recursively. Otherwise the user
 703       should have the ability to de-auto a package by changing its state */
 704    RemoveSizes(Pkg);
 705    RemoveStates(Pkg);
 706
 707    P.Mode = ModeInstall;
 708    P.InstallVer = P.CandidateVer;
 709    P.Flags &= ~Flag::Auto;
 710    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
 711       P.Mode = ModeKeep;
 712
 713    AddStates(Pkg);
 714    Update(Pkg);
 715    AddSizes(Pkg);
 716
 717    if (AutoInst == false)
 718       return;
 719
 720    DepIterator Dep = P.InstVerIter(*this).DependsList();
 721    for (; Dep.end() != true;)
 722    {
 723       // Grok or groups
 724       DepIterator Start = Dep;
 725       bool Result = true;
 726       unsigned Ors = 0;
 727       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
 728       {
 729          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
 730
 731          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
 732             Result = false;
 733       }
 734
 735       // Dep is satisfied okay.
 736       if (Result == false)
 737          continue;
 738
 739       /* Check if this dep should be consider for install. If it is a user
 740          defined important dep and we are installed a new package then
 741          it will be installed. Otherwise we only worry about critical deps */
 742       if (IsImportantDep(Start) == false)
 743          continue;
 744       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false)
 745          continue;
 746
 747       /* If we are in an or group locate the first or that can
 748          succeed. We have already cached this.. */
 749       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 750          Start++;
 751
 752       /* This bit is for processing the possibilty of an install/upgrade
 753          fixing the problem */
 754       SPtrArray<Version *> List = Start.AllTargets();
 755       if ((DepState[Start->ID] & DepCVer) == DepCVer)
 756       {
 757          // Right, find the best version to install..
 758          Version **Cur = List;
 759          PkgIterator P = Start.TargetPkg();
 760          PkgIterator InstPkg(*Cache,0);
 761
 762          // See if there are direct matches (at the start of the list)
 763          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 764          {
 765             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 766             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 767                continue;
 768             InstPkg = Pkg;
 769             break;
 770          }
 771
 772          // Select the highest priority providing package
 773          if (InstPkg.end() == true)
 774          {
 775             pkgPrioSortList(*Cache,Cur);
 776             for (; *Cur != 0; Cur++)
 777             {
 778                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 779                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 780                   continue;
 781                InstPkg = Pkg;
 782                break;
 783             }
 784          }
 785
 786          if (InstPkg.end() == false)
 787          {
 788             MarkInstall(InstPkg,true,Depth + 1);
 789
 790             // Set the autoflag, after MarkInstall because MarkInstall unsets it
 791             if (P->CurrentVer == 0)
 792                PkgState[InstPkg->ID].Flags |= Flag::Auto;
 793          }
 794
 795          continue;
 796       }
 797
 798       /* For conflicts we just de-install the package and mark as auto,
 799          Conflicts may not have or groups */
 800       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes)
 801       {
 802          for (Version **I = List; *I != 0; I++)
 803          {
 804             VerIterator Ver(*this,*I);
 805             PkgIterator Pkg = Ver.ParentPkg();
 806
 807             MarkDelete(Pkg);
 808             PkgState[Pkg->ID].Flags |= Flag::Auto;
 809          }
 810          continue;
 811       }
 812    }
 813 }
 814                                                                         /*}}}*/
 815 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 816 // ---------------------------------------------------------------------
 817 /* */
 818 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 819 {
 820    RemoveSizes(Pkg);
 821    RemoveStates(Pkg);
 822
 823    StateCache &P = PkgState[Pkg->ID];
 824    if (To == true)
 825       P.iFlags |= ReInstall;
 826    else
 827       P.iFlags &= ~ReInstall;
 828
 829    AddStates(Pkg);
 830    AddSizes(Pkg);
 831 }
 832                                                                         /*}}}*/
 833 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
 834 // ---------------------------------------------------------------------
 835 /* */
 836 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
 837 {
 838    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
 839    StateCache &P = PkgState[Pkg->ID];
 840
 841    RemoveSizes(Pkg);
 842    RemoveStates(Pkg);
 843
 844    if (P.CandidateVer == P.InstallVer)
 845       P.InstallVer = (Version *)TargetVer;
 846    P.CandidateVer = (Version *)TargetVer;
 847    P.Update(Pkg,*this);
 848
 849    AddStates(Pkg);
 850    Update(Pkg);
 851    AddSizes(Pkg);
 852 }
 853                                                                         /*}}}*/
 854 // StateCache::Update - Compute the various static display things       /*{{{*/
 855 // ---------------------------------------------------------------------
 856 /* This is called whenever the Candidate version changes. */
 857 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
 858 {
 859    // Some info
 860    VerIterator Ver = CandidateVerIter(Cache);
 861
 862    // Use a null string or the version string
 863    if (Ver.end() == true)
 864       CandVersion = "";
 865    else
 866       CandVersion = Ver.VerStr();
 867
 868    // Find the current version
 869    CurVersion = "";
 870    if (Pkg->CurrentVer != 0)
 871       CurVersion = Pkg.CurrentVer().VerStr();
 872
 873    // Strip off the epochs for display
 874    CurVersion = StripEpoch(CurVersion);
 875    CandVersion = StripEpoch(CandVersion);
 876
 877    // Figure out if its up or down or equal
 878    Status = Ver.CompareVer(Pkg.CurrentVer());
 879    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
 880      Status = 2;
 881 }
 882                                                                         /*}}}*/
 883 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
 884 // ---------------------------------------------------------------------
 885 /* */
 886 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
 887 {
 888    if (Ver == 0)
 889       return 0;
 890
 891    // Strip any epoch
 892    for (const char *I = Ver; *I != 0; I++)
 893       if (*I == ':')
 894          return I + 1;
 895    return Ver;
 896 }
 897                                                                         /*}}}*/
 898
 899 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
 900 // ---------------------------------------------------------------------
 901 /* The default just returns the highest available version that is not
 902    a source and automatic. */
 903 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
 904 {
 905    /* Not source/not automatic versions cannot be a candidate version
 906       unless they are already installed */
 907    VerIterator Last(*(pkgCache *)this,0);
 908
 909    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
 910    {
 911       if (Pkg.CurrentVer() == I)
 912          return I;
 913
 914       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
 915       {
 916          if ((J.File()->Flags & Flag::NotSource) != 0)
 917             continue;
 918
 919          /* Stash the highest version of a not-automatic source, we use it
 920             if there is nothing better */
 921          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
 922          {
 923             if (Last.end() == true)
 924                Last = I;
 925             continue;
 926          }
 927
 928          return I;
 929       }
 930    }
 931
 932    return Last;
 933 }
 934                                                                         /*}}}*/
 935 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
 936 // ---------------------------------------------------------------------
 937 /* */
 938 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
 939 {
 940    return Dep.IsCritical();
 941 }
 942                                                                         /*}}}*/