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          for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
 684          {
 685             //FIXME: deal better with or-groups(?)
 686             DepIterator LocalStart = D;
 687
 688             if(IsImportantDep(D) && Start.TargetPkg() == D.TargetPkg())
 689                found=true;
 690          }
 691          // this is a new dep if it was not found to be already
 692          // a important dep of the installed pacakge
 693          isNewImportantDep = !found;
 694       }
 695       if(isNewImportantDep)
 696          if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 697             std::clog << "new important dependency: "
 698                       << Start.TargetPkg().Name() << std::endl;
 699
 700       // skip important deps if the package is already installed
 701       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
 702           && !isNewImportantDep && !ForceImportantDeps)
 703          continue;
 704
 705       /* If we are in an or group locate the first or that can
 706          succeed. We have already cached this.. */
 707       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 708          Start++;
 709
 710       /* This bit is for processing the possibilty of an install/upgrade
 711          fixing the problem */
 712       SPtrArray<Version *> List = Start.AllTargets();
 713       if ((DepState[Start->ID] & DepCVer) == DepCVer)
 714       {
 715          // Right, find the best version to install..
 716          Version **Cur = List;
 717          PkgIterator P = Start.TargetPkg();
 718          PkgIterator InstPkg(*Cache,0);
 719
 720          // See if there are direct matches (at the start of the list)
 721          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 722          {
 723             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 724             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 725                continue;
 726             InstPkg = Pkg;
 727             break;
 728          }
 729
 730          // Select the highest priority providing package
 731          if (InstPkg.end() == true)
 732          {
 733             pkgPrioSortList(*Cache,Cur);
 734             for (; *Cur != 0; Cur++)
 735             {
 736                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 737                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 738                   continue;
 739                InstPkg = Pkg;
 740                break;
 741             }
 742          }
 743
 744          if (InstPkg.end() == false)
 745          {
 746             if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 747                std::clog << "Installing " << InstPkg.Name()
 748                          << " as dep of " << Pkg.Name()
 749                          << std::endl;
 750             MarkInstall(InstPkg,true,Depth + 1, ForceImportantDeps);
 751
 752             // Set the autoflag, after MarkInstall because MarkInstall unsets it
 753             if (P->CurrentVer == 0)
 754                PkgState[InstPkg->ID].Flags |= Flag::Auto;
 755          }
 756
 757          continue;
 758       }
 759
 760       /* For conflicts we just de-install the package and mark as auto,
 761          Conflicts may not have or groups */
 762       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes)
 763       {
 764          for (Version **I = List; *I != 0; I++)
 765          {
 766             VerIterator Ver(*this,*I);
 767             PkgIterator Pkg = Ver.ParentPkg();
 768
 769             MarkDelete(Pkg);
 770             PkgState[Pkg->ID].Flags |= Flag::Auto;
 771          }
 772          continue;
 773       }
 774    }
 775 }
 776                                                                         /*}}}*/
 777 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 778 // ---------------------------------------------------------------------
 779 /* */
 780 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 781 {
 782    RemoveSizes(Pkg);
 783    RemoveStates(Pkg);
 784
 785    StateCache &P = PkgState[Pkg->ID];
 786    if (To == true)
 787       P.iFlags |= ReInstall;
 788    else
 789       P.iFlags &= ~ReInstall;
 790
 791    AddStates(Pkg);
 792    AddSizes(Pkg);
 793 }
 794                                                                         /*}}}*/
 795 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
 796 // ---------------------------------------------------------------------
 797 /* */
 798 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
 799 {
 800    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
 801    StateCache &P = PkgState[Pkg->ID];
 802
 803    RemoveSizes(Pkg);
 804    RemoveStates(Pkg);
 805
 806    if (P.CandidateVer == P.InstallVer)
 807       P.InstallVer = (Version *)TargetVer;
 808    P.CandidateVer = (Version *)TargetVer;
 809    P.Update(Pkg,*this);
 810
 811    AddStates(Pkg);
 812    Update(Pkg);
 813    AddSizes(Pkg);
 814 }
 815                                                                         /*}}}*/
 816 // StateCache::Update - Compute the various static display things       /*{{{*/
 817 // ---------------------------------------------------------------------
 818 /* This is called whenever the Candidate version changes. */
 819 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
 820 {
 821    // Some info
 822    VerIterator Ver = CandidateVerIter(Cache);
 823
 824    // Use a null string or the version string
 825    if (Ver.end() == true)
 826       CandVersion = "";
 827    else
 828       CandVersion = Ver.VerStr();
 829
 830    // Find the current version
 831    CurVersion = "";
 832    if (Pkg->CurrentVer != 0)
 833       CurVersion = Pkg.CurrentVer().VerStr();
 834
 835    // Strip off the epochs for display
 836    CurVersion = StripEpoch(CurVersion);
 837    CandVersion = StripEpoch(CandVersion);
 838
 839    // Figure out if its up or down or equal
 840    Status = Ver.CompareVer(Pkg.CurrentVer());
 841    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
 842      Status = 2;
 843 }
 844                                                                         /*}}}*/
 845 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
 846 // ---------------------------------------------------------------------
 847 /* */
 848 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
 849 {
 850    if (Ver == 0)
 851       return 0;
 852
 853    // Strip any epoch
 854    for (const char *I = Ver; *I != 0; I++)
 855       if (*I == ':')
 856          return I + 1;
 857    return Ver;
 858 }
 859                                                                         /*}}}*/
 860
 861 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
 862 // ---------------------------------------------------------------------
 863 /* The default just returns the highest available version that is not
 864    a source and automatic. */
 865 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
 866 {
 867    /* Not source/not automatic versions cannot be a candidate version
 868       unless they are already installed */
 869    VerIterator Last(*(pkgCache *)this,0);
 870
 871    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
 872    {
 873       if (Pkg.CurrentVer() == I)
 874          return I;
 875
 876       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
 877       {
 878          if ((J.File()->Flags & Flag::NotSource) != 0)
 879             continue;
 880
 881          /* Stash the highest version of a not-automatic source, we use it
 882             if there is nothing better */
 883          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
 884          {
 885             if (Last.end() == true)
 886                Last = I;
 887             continue;
 888          }
 889
 890          return I;
 891       }
 892    }
 893
 894    return Last;
 895 }
 896                                                                         /*}}}*/
 897 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
 898 // ---------------------------------------------------------------------
 899 /* */
 900 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
 901 {
 902    if(Dep.IsCritical())
 903       return true;
 904    else if(Dep->Type == pkgCache::Dep::Recommends)
 905       return  _config->FindB("APT::Install-Recommends", false);
 906    else if(Dep->Type == pkgCache::Dep::Suggests)
 907      return _config->FindB("APT::Install-Suggests", false);
 908
 909    return false;
 910 }
 911                                                                         /*}}}*/