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