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