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