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 #include <apt-pkg/configuration.h>
  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 (either minimal dep or policy dep)
 243    if ((State.DepState & DepInstMin) != DepInstMin)
 244       iBrokenCount += Add;
 245    if ((State.DepState & DepInstPolicy) != DepInstPolicy)
 246       iPolicyBrokenCount += Add;
 247
 248    // Bad state
 249    if (Pkg.State() != PkgIterator::NeedsNothing)
 250       iBadCount += Add;
 251
 252    // Not installed
 253    if (Pkg->CurrentVer == 0)
 254    {
 255       if (State.Mode == ModeDelete &&
 256           (State.iFlags | Purge) == Purge && Pkg.Purge() == false)
 257          iDelCount += Add;
 258
 259       if (State.Mode == ModeInstall)
 260          iInstCount += Add;
 261       return;
 262    }
 263
 264    // Installed, no upgrade
 265    if (State.Status == 0)
 266    {
 267       if (State.Mode == ModeDelete)
 268          iDelCount += Add;
 269       else
 270          if ((State.iFlags & ReInstall) == ReInstall)
 271             iInstCount += Add;
 272
 273       return;
 274    }
 275
 276    // Alll 3 are possible
 277    if (State.Mode == ModeDelete)
 278       iDelCount += Add;
 279    if (State.Mode == ModeKeep)
 280       iKeepCount += Add;
 281    if (State.Mode == ModeInstall)
 282       iInstCount += Add;
 283 }
 284                                                                         /*}}}*/
 285 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 286 // ---------------------------------------------------------------------
 287 /* The or group results are stored in the last item of the or group. This
 288    allows easy detection of the state of a whole or'd group. */
 289 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 290 {
 291    unsigned char Group = 0;
 292
 293    for (DepIterator D = V.DependsList(); D.end() != true; D++)
 294    {
 295       // Build the dependency state.
 296       unsigned char &State = DepState[D->ID];
 297
 298       /* Invert for Conflicts. We have to do this twice to get the
 299          right sense for a conflicts group */
 300       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 301          State = ~State;
 302
 303       // Add to the group if we are within an or..
 304       State &= 0x7;
 305       Group |= State;
 306       State |= Group << 3;
 307       if ((D->CompareOp & Dep::Or) != Dep::Or)
 308          Group = 0;
 309
 310       // Invert for Conflicts
 311       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 312          State = ~State;
 313    }
 314 }
 315                                                                         /*}}}*/
 316 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 317 // ---------------------------------------------------------------------
 318 /* This is used to run over a dependency list and determine the dep
 319    state of the list, filtering it through both a Min check and a Policy
 320    check. The return result will have SetMin/SetPolicy low if a check
 321    fails. It uses the DepState cache for it's computations. */
 322 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 323                                        unsigned char SetMin,
 324                                        unsigned char SetPolicy)
 325 {
 326    unsigned char Dep = 0xFF;
 327
 328    while (D.end() != true)
 329    {
 330       // Compute a single dependency element (glob or)
 331       DepIterator Start = D;
 332       unsigned char State = 0;
 333       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 334       {
 335          State |= DepState[D->ID];
 336          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 337       }
 338
 339       // Minimum deps that must be satisfied to have a working package
 340       if (Start.IsCritical() == true)
 341          if ((State & Check) != Check)
 342             Dep &= ~SetMin;
 343
 344       // Policy deps that must be satisfied to install the package
 345       if (IsImportantDep(Start) == true &&
 346           (State & Check) != Check)
 347          Dep &= ~SetPolicy;
 348    }
 349
 350    return Dep;
 351 }
 352                                                                         /*}}}*/
 353 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 354 // ---------------------------------------------------------------------
 355 /* This is the main dependency computation bit. It computes the 3 main
 356    results for a dependencys, Now, Install and Candidate. Callers must
 357    invert the result if dealing with conflicts. */
 358 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 359 {
 360    unsigned char State = 0;
 361
 362    if (CheckDep(D,NowVersion) == true)
 363       State |= DepNow;
 364    if (CheckDep(D,InstallVersion) == true)
 365       State |= DepInstall;
 366    if (CheckDep(D,CandidateVersion) == true)
 367       State |= DepCVer;
 368
 369    return State;
 370 }
 371                                                                         /*}}}*/
 372 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 373 // ---------------------------------------------------------------------
 374 /* This determines the combined dependency representation of a package
 375    for its two states now and install. This is done by using the pre-generated
 376    dependency information. */
 377 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 378 {
 379    // Empty deps are always true
 380    StateCache &State = PkgState[Pkg->ID];
 381    State.DepState = 0xFF;
 382
 383    // Check the Current state
 384    if (Pkg->CurrentVer != 0)
 385    {
 386       DepIterator D = Pkg.CurrentVer().DependsList();
 387       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 388    }
 389
 390    /* Check the candidate state. We do not compare against the whole as
 391       a candidate state but check the candidate version against the
 392       install states */
 393    if (State.CandidateVer != 0)
 394    {
 395       DepIterator D = State.CandidateVerIter(*this).DependsList();
 396       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 397    }
 398
 399    // Check target state which can only be current or installed
 400    if (State.InstallVer != 0)
 401    {
 402       DepIterator D = State.InstVerIter(*this).DependsList();
 403       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 404    }
 405 }
 406                                                                         /*}}}*/
 407 // DepCache::Update - Figure out all the state information              /*{{{*/
 408 // ---------------------------------------------------------------------
 409 /* This will figure out the state of all the packages and all the
 410    dependencies based on the current policy. */
 411 void pkgDepCache::Update(OpProgress *Prog)
 412 {
 413    iUsrSize = 0;
 414    iDownloadSize = 0;
 415    iDelCount = 0;
 416    iInstCount = 0;
 417    iKeepCount = 0;
 418    iBrokenCount = 0;
 419    iBadCount = 0;
 420
 421    // Perform the depends pass
 422    int Done = 0;
 423    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 424    {
 425       if (Prog != 0 && Done%20 == 0)
 426          Prog->Progress(Done);
 427       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 428       {
 429          unsigned char Group = 0;
 430
 431          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 432          {
 433             // Build the dependency state.
 434             unsigned char &State = DepState[D->ID];
 435             State = DependencyState(D);
 436
 437             // Add to the group if we are within an or..
 438             Group |= State;
 439             State |= Group << 3;
 440             if ((D->CompareOp & Dep::Or) != Dep::Or)
 441                Group = 0;
 442
 443             // Invert for Conflicts
 444             if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 445                State = ~State;
 446          }
 447       }
 448
 449       // Compute the pacakge dependency state and size additions
 450       AddSizes(I);
 451       UpdateVerState(I);
 452       AddStates(I);
 453    }
 454
 455    if (Prog != 0)
 456       Prog->Progress(Done);
 457 }
 458                                                                         /*}}}*/
 459 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 460 // ---------------------------------------------------------------------
 461 /* This is a helper for update that only does the dep portion of the scan.
 462    It is mainly ment to scan reverse dependencies. */
 463 void pkgDepCache::Update(DepIterator D)
 464 {
 465    // Update the reverse deps
 466    for (;D.end() != true; D++)
 467    {
 468       unsigned char &State = DepState[D->ID];
 469       State = DependencyState(D);
 470
 471       // Invert for Conflicts
 472       if (D->Type == Dep::Conflicts || D->Type == Dep::Obsoletes)
 473          State = ~State;
 474
 475       RemoveStates(D.ParentPkg());
 476       BuildGroupOrs(D.ParentVer());
 477       UpdateVerState(D.ParentPkg());
 478       AddStates(D.ParentPkg());
 479    }
 480 }
 481                                                                         /*}}}*/
 482 // DepCache::Update - Update the related deps of a package              /*{{{*/
 483 // ---------------------------------------------------------------------
 484 /* This is called whenever the state of a package changes. It updates
 485    all cached dependencies related to this package. */
 486 void pkgDepCache::Update(PkgIterator const &Pkg)
 487 {
 488    // Recompute the dep of the package
 489    RemoveStates(Pkg);
 490    UpdateVerState(Pkg);
 491    AddStates(Pkg);
 492
 493    // Update the reverse deps
 494    Update(Pkg.RevDependsList());
 495
 496    // Update the provides map for the current ver
 497    if (Pkg->CurrentVer != 0)
 498       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 499            P.end() != true; P++)
 500          Update(P.ParentPkg().RevDependsList());
 501
 502    // Update the provides map for the candidate ver
 503    if (PkgState[Pkg->ID].CandidateVer != 0)
 504       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 505            P.end() != true; P++)
 506          Update(P.ParentPkg().RevDependsList());
 507 }
 508
 509                                                                         /*}}}*/
 510
 511 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 512 // ---------------------------------------------------------------------
 513 /* */
 514 void pkgDepCache::MarkKeep(PkgIterator const &Pkg,bool Soft)
 515 {
 516    // Simplifies other routines.
 517    if (Pkg.end() == true)
 518       return;
 519
 520    /* Reject an attempt to keep a non-source broken installed package, those
 521       must be upgraded */
 522    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 523        Pkg.CurrentVer().Downloadable() == false)
 524       return;
 525
 526    /* We changed the soft state all the time so the UI is a bit nicer
 527       to use */
 528    StateCache &P = PkgState[Pkg->ID];
 529    if (Soft == true)
 530       P.iFlags |= AutoKept;
 531    else
 532       P.iFlags &= ~AutoKept;
 533
 534    // Check that it is not already kept
 535    if (P.Mode == ModeKeep)
 536       return;
 537
 538    // We dont even try to keep virtual packages..
 539    if (Pkg->VersionList == 0)
 540       return;
 541
 542    P.Flags &= ~Flag::Auto;
 543    RemoveSizes(Pkg);
 544    RemoveStates(Pkg);
 545
 546    P.Mode = ModeKeep;
 547    if (Pkg->CurrentVer == 0)
 548       P.InstallVer = 0;
 549    else
 550       P.InstallVer = Pkg.CurrentVer();
 551
 552    AddStates(Pkg);
 553
 554    Update(Pkg);
 555
 556    AddSizes(Pkg);
 557 }
 558                                                                         /*}}}*/
 559 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 560 // ---------------------------------------------------------------------
 561 /* */
 562 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge)
 563 {
 564    // Simplifies other routines.
 565    if (Pkg.end() == true)
 566       return;
 567
 568    // Check that it is not already marked for delete
 569    StateCache &P = PkgState[Pkg->ID];
 570    P.iFlags &= ~(AutoKept | Purge);
 571    if (rPurge == true)
 572       P.iFlags |= Purge;
 573
 574    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 575        (Pkg.Purge() == true || rPurge == false))
 576       return;
 577
 578    // We dont even try to delete virtual packages..
 579    if (Pkg->VersionList == 0)
 580       return;
 581
 582    RemoveSizes(Pkg);
 583    RemoveStates(Pkg);
 584
 585    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 586       P.Mode = ModeKeep;
 587    else
 588       P.Mode = ModeDelete;
 589    P.InstallVer = 0;
 590    P.Flags &= Flag::Auto;
 591
 592    AddStates(Pkg);
 593    Update(Pkg);
 594    AddSizes(Pkg);
 595 }
 596                                                                         /*}}}*/
 597 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 598 // ---------------------------------------------------------------------
 599 /* */
 600 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 601                               unsigned long Depth, bool ForceImportantDeps)
 602 {
 603    if (Depth > 100)
 604       return;
 605
 606    // Simplifies other routines.
 607    if (Pkg.end() == true)
 608       return;
 609
 610    /* Check that it is not already marked for install and that it can be
 611       installed */
 612    StateCache &P = PkgState[Pkg->ID];
 613    P.iFlags &= ~AutoKept;
 614    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
 615        (P.Mode == ModeInstall ||
 616         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 617    {
 618       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 619          MarkKeep(Pkg);
 620       return;
 621    }
 622
 623    // See if there is even any possible instalation candidate
 624    if (P.CandidateVer == 0)
 625       return;
 626    // We dont even try to install virtual packages..
 627    if (Pkg->VersionList == 0)
 628       return;
 629    /* Target the candidate version and remove the autoflag. We reset the
 630       autoflag below if this was called recursively. Otherwise the user
 631       should have the ability to de-auto a package by changing its state */
 632    RemoveSizes(Pkg);
 633    RemoveStates(Pkg);
 634
 635    P.Mode = ModeInstall;
 636    P.InstallVer = P.CandidateVer;
 637    P.Flags &= ~Flag::Auto;
 638    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
 639       P.Mode = ModeKeep;
 640
 641    AddStates(Pkg);
 642    Update(Pkg);
 643    AddSizes(Pkg);
 644
 645    if (AutoInst == false)
 646       return;
 647
 648    DepIterator Dep = P.InstVerIter(*this).DependsList();
 649    for (; Dep.end() != true;)
 650    {
 651       // Grok or groups
 652       DepIterator Start = Dep;
 653       bool Result = true;
 654       unsigned Ors = 0;
 655       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
 656       {
 657          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
 658
 659          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
 660             Result = false;
 661       }
 662
 663       // Dep is satisfied okay.
 664       if (Result == false)
 665          continue;
 666
 667       /* Check if this dep should be consider for install. If it is a user
 668          defined important dep and we are installed a new package then
 669          it will be installed. Otherwise we only check for important
 670          deps that have changed from the installed version
 671       */
 672       if (IsImportantDep(Start) == false)
 673          continue;
 674
 675       /* check if any ImportantDep() (but not Critial) where added
 676        * since we installed the package
 677        */
 678       bool isNewImportantDep = false;
 679       if(!ForceImportantDeps && !Start.IsCritical())
 680       {
 681          bool found=false;
 682          VerIterator instVer = Pkg.CurrentVer();
 683          if(!instVer.end())
 684             for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
 685             {
 686                //FIXME: deal better with or-groups(?)
 687                DepIterator LocalStart = D;
 688
 689                if(IsImportantDep(D) && Start.TargetPkg() == D.TargetPkg())
 690                   found=true;
 691             }
 692          // this is a new dep if it was not found to be already
 693          // a important dep of the installed pacakge
 694          isNewImportantDep = !found;
 695       }
 696       if(isNewImportantDep)
 697          if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 698             std::clog << "new important dependency: "
 699                       << Start.TargetPkg().Name() << std::endl;
 700
 701       // skip important deps if the package is already installed
 702       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
 703           && !isNewImportantDep && !ForceImportantDeps)
 704          continue;
 705
 706       /* If we are in an or group locate the first or that can
 707          succeed. We have already cached this.. */
 708       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 709          Start++;
 710
 711       /* This bit is for processing the possibilty of an install/upgrade
 712          fixing the problem */
 713       SPtrArray<Version *> List = Start.AllTargets();
 714       if ((DepState[Start->ID] & DepCVer) == DepCVer)
 715       {
 716          // Right, find the best version to install..
 717          Version **Cur = List;
 718          PkgIterator P = Start.TargetPkg();
 719          PkgIterator InstPkg(*Cache,0);
 720
 721          // See if there are direct matches (at the start of the list)
 722          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 723          {
 724             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 725             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 726                continue;
 727             InstPkg = Pkg;
 728             break;
 729          }
 730
 731          // Select the highest priority providing package
 732          if (InstPkg.end() == true)
 733          {
 734             pkgPrioSortList(*Cache,Cur);
 735             for (; *Cur != 0; Cur++)
 736             {
 737                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 738                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 739                   continue;
 740                InstPkg = Pkg;
 741                break;
 742             }
 743          }
 744
 745          if (InstPkg.end() == false)
 746          {
 747             if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 748                std::clog << "Installing " << InstPkg.Name()
 749                          << " as dep of " << Pkg.Name()
 750                          << std::endl;
 751             MarkInstall(InstPkg,true,Depth + 1, ForceImportantDeps);
 752
 753             // Set the autoflag, after MarkInstall because MarkInstall unsets it
 754             if (P->CurrentVer == 0)
 755                PkgState[InstPkg->ID].Flags |= Flag::Auto;
 756          }
 757
 758          continue;
 759       }
 760
 761       /* For conflicts we just de-install the package and mark as auto,
 762          Conflicts may not have or groups */
 763       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes)
 764       {
 765          for (Version **I = List; *I != 0; I++)
 766          {
 767             VerIterator Ver(*this,*I);
 768             PkgIterator Pkg = Ver.ParentPkg();
 769
 770             MarkDelete(Pkg);
 771             PkgState[Pkg->ID].Flags |= Flag::Auto;
 772          }
 773          continue;
 774       }
 775    }
 776 }
 777                                                                         /*}}}*/
 778 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 779 // ---------------------------------------------------------------------
 780 /* */
 781 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 782 {
 783    RemoveSizes(Pkg);
 784    RemoveStates(Pkg);
 785
 786    StateCache &P = PkgState[Pkg->ID];
 787    if (To == true)
 788       P.iFlags |= ReInstall;
 789    else
 790       P.iFlags &= ~ReInstall;
 791
 792    AddStates(Pkg);
 793    AddSizes(Pkg);
 794 }
 795                                                                         /*}}}*/
 796 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
 797 // ---------------------------------------------------------------------
 798 /* */
 799 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
 800 {
 801    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
 802    StateCache &P = PkgState[Pkg->ID];
 803
 804    RemoveSizes(Pkg);
 805    RemoveStates(Pkg);
 806
 807    if (P.CandidateVer == P.InstallVer)
 808       P.InstallVer = (Version *)TargetVer;
 809    P.CandidateVer = (Version *)TargetVer;
 810    P.Update(Pkg,*this);
 811
 812    AddStates(Pkg);
 813    Update(Pkg);
 814    AddSizes(Pkg);
 815 }
 816                                                                         /*}}}*/
 817 // StateCache::Update - Compute the various static display things       /*{{{*/
 818 // ---------------------------------------------------------------------
 819 /* This is called whenever the Candidate version changes. */
 820 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
 821 {
 822    // Some info
 823    VerIterator Ver = CandidateVerIter(Cache);
 824
 825    // Use a null string or the version string
 826    if (Ver.end() == true)
 827       CandVersion = "";
 828    else
 829       CandVersion = Ver.VerStr();
 830
 831    // Find the current version
 832    CurVersion = "";
 833    if (Pkg->CurrentVer != 0)
 834       CurVersion = Pkg.CurrentVer().VerStr();
 835
 836    // Strip off the epochs for display
 837    CurVersion = StripEpoch(CurVersion);
 838    CandVersion = StripEpoch(CandVersion);
 839
 840    // Figure out if its up or down or equal
 841    Status = Ver.CompareVer(Pkg.CurrentVer());
 842    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
 843      Status = 2;
 844 }
 845                                                                         /*}}}*/
 846 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
 847 // ---------------------------------------------------------------------
 848 /* */
 849 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
 850 {
 851    if (Ver == 0)
 852       return 0;
 853
 854    // Strip any epoch
 855    for (const char *I = Ver; *I != 0; I++)
 856       if (*I == ':')
 857          return I + 1;
 858    return Ver;
 859 }
 860                                                                         /*}}}*/
 861
 862 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
 863 // ---------------------------------------------------------------------
 864 /* The default just returns the highest available version that is not
 865    a source and automatic. */
 866 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
 867 {
 868    /* Not source/not automatic versions cannot be a candidate version
 869       unless they are already installed */
 870    VerIterator Last(*(pkgCache *)this,0);
 871
 872    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
 873    {
 874       if (Pkg.CurrentVer() == I)
 875          return I;
 876
 877       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
 878       {
 879          if ((J.File()->Flags & Flag::NotSource) != 0)
 880             continue;
 881
 882          /* Stash the highest version of a not-automatic source, we use it
 883             if there is nothing better */
 884          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
 885          {
 886             if (Last.end() == true)
 887                Last = I;
 888             continue;
 889          }
 890
 891          return I;
 892       }
 893    }
 894
 895    return Last;
 896 }
 897                                                                         /*}}}*/
 898 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
 899 // ---------------------------------------------------------------------
 900 /* */
 901 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
 902 {
 903    if(Dep.IsCritical())
 904       return true;
 905    else if(Dep->Type == pkgCache::Dep::Recommends)
 906       return  _config->FindB("APT::Install-Recommends", false);
 907    else if(Dep->Type == pkgCache::Dep::Suggests)
 908      return _config->FindB("APT::Install-Suggests", false);
 909
 910    return false;
 911 }
 912                                                                         /*}}}*/