apt-pkg/depcache.cc

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