apt-pkg/depcache.cc

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