apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.35 2001/05/07 02:15:33 jgg Exp $
   4 /* ######################################################################
   5
   6    Algorithms - A set of misc algorithms
   7
   8    The pkgProblemResolver class has become insanely complex and
   9    very sophisticated, it handles every test case I have thrown at it
  10    to my satisfaction. Understanding exactly why all the steps the class
  11    does are required is difficult and changing though not very risky
  12    may result in other cases not working.
  13
  14    ##################################################################### */
  15                                                                         /*}}}*/
  16 // Include Files                                                        /*{{{*/
  17 #ifdef __GNUG__
  18 #pragma implementation "apt-pkg/algorithms.h"
  19 #endif
  20 #include <apt-pkg/algorithms.h>
  21 #include <apt-pkg/error.h>
  22 #include <apt-pkg/configuration.h>
  23 #include <apt-pkg/sptr.h>
  24
  25 #include <apti18n.h>
  26
  27 #include <iostream.h>
  28                                                                         /*}}}*/
  29
  30 pkgProblemResolver *pkgProblemResolver::This = 0;
  31
  32 // Simulate::Simulate - Constructor                                     /*{{{*/
  33 // ---------------------------------------------------------------------
  34 /* The legacy translations here of input Pkg iterators is obsolete,
  35    this is not necessary since the pkgCaches are fully shared now. */
  36 pkgSimulate::pkgSimulate(pkgDepCache *Cache) : pkgPackageManager(Cache),
  37                             iPolicy(Cache),
  38                             Sim(&Cache->GetCache(),&iPolicy)
  39 {
  40    Sim.Init(0);
  41    Flags = new unsigned char[Cache->Head().PackageCount];
  42    memset(Flags,0,sizeof(*Flags)*Cache->Head().PackageCount);
  43
  44    // Fake a filename so as not to activate the media swapping
  45    string Jnk = "SIMULATE";
  46    for (unsigned int I = 0; I != Cache->Head().PackageCount; I++)
  47       FileNames[I] = Jnk;
  48 }
  49                                                                         /*}}}*/
  50 // Simulate::Describe - Describe a package                              /*{{{*/
  51 // ---------------------------------------------------------------------
  52 /* */
  53 void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Now)
  54 {
  55    VerIterator Ver(Sim);
  56    if (Now == true)
  57       Ver = Pkg.CurrentVer();
  58    else
  59       Ver = Sim[Pkg].CandidateVerIter(Sim);
  60
  61    out << Pkg.Name();
  62
  63    if (Ver.end() == true)
  64       return;
  65
  66    out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')';
  67 }
  68                                                                         /*}}}*/
  69 // Simulate::Install - Simulate unpacking of a package                  /*{{{*/
  70 // ---------------------------------------------------------------------
  71 /* */
  72 bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/)
  73 {
  74    // Adapt the iterator
  75    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
  76    Flags[Pkg->ID] = 1;
  77
  78    cout << "Inst ";
  79    Describe(Pkg,cout,false);
  80    Sim.MarkInstall(Pkg,false);
  81
  82    // Look for broken conflicts+predepends.
  83    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
  84    {
  85       if (Sim[I].InstallVer == 0)
  86          continue;
  87
  88       for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false;)
  89       {
  90          DepIterator Start;
  91          DepIterator End;
  92          D.GlobOr(Start,End);
  93          if (Start->Type == pkgCache::Dep::Conflicts ||
  94              Start->Type == pkgCache::Dep::Obsoletes ||
  95              End->Type == pkgCache::Dep::PreDepends)
  96          {
  97             if ((Sim[End] & pkgDepCache::DepGInstall) == 0)
  98             {
  99                cout << " [" << I.Name() << " on " << Start.TargetPkg().Name() << ']';
 100                if (Start->Type == pkgCache::Dep::Conflicts)
 101                   _error->Error("Fatal, conflicts violated %s",I.Name());
 102             }
 103          }
 104       }
 105    }
 106
 107    if (Sim.BrokenCount() != 0)
 108       ShortBreaks();
 109    else
 110       cout << endl;
 111    return true;
 112 }
 113                                                                         /*}}}*/
 114 // Simulate::Configure - Simulate configuration of a Package            /*{{{*/
 115 // ---------------------------------------------------------------------
 116 /* This is not an acurate simulation of relatity, we should really not
 117    install the package.. For some investigations it may be necessary
 118    however. */
 119 bool pkgSimulate::Configure(PkgIterator iPkg)
 120 {
 121    // Adapt the iterator
 122    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
 123
 124    Flags[Pkg->ID] = 2;
 125 //   Sim.MarkInstall(Pkg,false);
 126    if (Sim[Pkg].InstBroken() == true)
 127    {
 128       cout << "Conf " << Pkg.Name() << " broken" << endl;
 129
 130       Sim.Update();
 131
 132       // Print out each package and the failed dependencies
 133       for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; D++)
 134       {
 135          if (Sim.IsImportantDep(D) == false ||
 136              (Sim[D] & pkgDepCache::DepInstall) != 0)
 137             continue;
 138
 139          if (D->Type == pkgCache::Dep::Obsoletes)
 140             cout << " Obsoletes:" << D.TargetPkg().Name();
 141          else if (D->Type == pkgCache::Dep::Conflicts)
 142             cout << " Conflicts:" << D.TargetPkg().Name();
 143          else
 144             cout << " Depends:" << D.TargetPkg().Name();
 145       }
 146       cout << endl;
 147
 148       _error->Error("Conf Broken %s",Pkg.Name());
 149    }
 150    else
 151    {
 152       cout << "Conf ";
 153       Describe(Pkg,cout,false);
 154    }
 155
 156    if (Sim.BrokenCount() != 0)
 157       ShortBreaks();
 158    else
 159       cout << endl;
 160
 161    return true;
 162 }
 163                                                                         /*}}}*/
 164 // Simulate::Remove - Simulate the removal of a package                 /*{{{*/
 165 // ---------------------------------------------------------------------
 166 /* */
 167 bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)
 168 {
 169    // Adapt the iterator
 170    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
 171
 172    Flags[Pkg->ID] = 3;
 173    Sim.MarkDelete(Pkg);
 174    if (Purge == true)
 175       cout << "Purg ";
 176    else
 177       cout << "Remv ";
 178    Describe(Pkg,cout,false);
 179
 180    if (Sim.BrokenCount() != 0)
 181       ShortBreaks();
 182    else
 183       cout << endl;
 184
 185    return true;
 186 }
 187                                                                         /*}}}*/
 188 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
 189 // ---------------------------------------------------------------------
 190 /* */
 191 void pkgSimulate::ShortBreaks()
 192 {
 193    cout << " [";
 194    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
 195    {
 196       if (Sim[I].InstBroken() == true)
 197       {
 198          if (Flags[I->ID] == 0)
 199             cout << I.Name() << ' ';
 200 /*       else
 201             cout << I.Name() << "! ";*/
 202       }
 203    }
 204    cout << ']' << endl;
 205 }
 206                                                                         /*}}}*/
 207 // ApplyStatus - Adjust for non-ok packages                             /*{{{*/
 208 // ---------------------------------------------------------------------
 209 /* We attempt to change the state of the all packages that have failed
 210    installation toward their real state. The ordering code will perform
 211    the necessary calculations to deal with the problems. */
 212 bool pkgApplyStatus(pkgDepCache &Cache)
 213 {
 214    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 215    {
 216       // Only choice for a ReInstReq package is to reinstall
 217       if (I->InstState == pkgCache::State::ReInstReq ||
 218           I->InstState == pkgCache::State::HoldReInstReq)
 219       {
 220          if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true)
 221             Cache.MarkKeep(I);
 222          else
 223          {
 224             // Is this right? Will dpkg choke on an upgrade?
 225             if (Cache[I].CandidateVerIter(Cache).Downloadable() == true)
 226                Cache.MarkInstall(I);
 227             else
 228                return _error->Error(_("The package %s needs to be reinstalled, "
 229                                     "but I can't find an archive for it."),I.Name());
 230          }
 231
 232          continue;
 233       }
 234
 235       switch (I->CurrentState)
 236       {
 237          /* This means installation failed somehow - it does not need to be
 238             re-unpacked (probably) */
 239          case pkgCache::State::UnPacked:
 240          case pkgCache::State::HalfConfigured:
 241          if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) ||
 242              I.State() != pkgCache::PkgIterator::NeedsUnpack)
 243             Cache.MarkKeep(I);
 244          else
 245          {
 246             if (Cache[I].CandidateVerIter(Cache).Downloadable() == true)
 247                Cache.MarkInstall(I);
 248             else
 249                Cache.MarkDelete(I);
 250          }
 251          break;
 252
 253          // This means removal failed
 254          case pkgCache::State::HalfInstalled:
 255          Cache.MarkDelete(I);
 256          break;
 257
 258          default:
 259          if (I->InstState != pkgCache::State::Ok)
 260             return _error->Error("The package %s is not ok and I "
 261                                  "don't know how to fix it!",I.Name());
 262       }
 263    }
 264    return true;
 265 }
 266                                                                         /*}}}*/
 267 // FixBroken - Fix broken packages                                      /*{{{*/
 268 // ---------------------------------------------------------------------
 269 /* This autoinstalls every broken package and then runs the problem resolver
 270    on the result. */
 271 bool pkgFixBroken(pkgDepCache &Cache)
 272 {
 273    // Auto upgrade all broken packages
 274    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 275       if (Cache[I].NowBroken() == true)
 276          Cache.MarkInstall(I,true);
 277
 278    /* Fix packages that are in a NeedArchive state but don't have a
 279       downloadable install version */
 280    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 281    {
 282       if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
 283           Cache[I].Delete() == true)
 284          continue;
 285
 286       if (Cache[I].InstVerIter(Cache).Downloadable() == false)
 287          continue;
 288
 289       Cache.MarkInstall(I,true);
 290    }
 291
 292    pkgProblemResolver Fix(&Cache);
 293    return Fix.Resolve(true);
 294 }
 295                                                                         /*}}}*/
 296 // DistUpgrade - Distribution upgrade                                   /*{{{*/
 297 // ---------------------------------------------------------------------
 298 /* This autoinstalls every package and then force installs every
 299    pre-existing package. This creates the initial set of conditions which
 300    most likely contain problems because too many things were installed.
 301
 302    The problem resolver is used to resolve the problems.
 303  */
 304 bool pkgDistUpgrade(pkgDepCache &Cache)
 305 {
 306    /* Auto upgrade all installed packages, this provides the basis
 307       for the installation */
 308    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 309       if (I->CurrentVer != 0)
 310          Cache.MarkInstall(I,true);
 311
 312    /* Now, auto upgrade all essential packages - this ensures that
 313       the essential packages are present and working */
 314    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 315       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 316          Cache.MarkInstall(I,true);
 317
 318    /* We do it again over all previously installed packages to force
 319       conflict resolution on them all. */
 320    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 321       if (I->CurrentVer != 0)
 322          Cache.MarkInstall(I,false);
 323
 324    pkgProblemResolver Fix(&Cache);
 325
 326    // Hold back held packages.
 327    if (_config->FindB("APT::Ignore-Hold",false) == false)
 328    {
 329       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 330       {
 331          if (I->SelectedState == pkgCache::State::Hold)
 332          {
 333             Fix.Protect(I);
 334             Cache.MarkKeep(I);
 335          }
 336       }
 337    }
 338
 339    return Fix.Resolve();
 340 }
 341                                                                         /*}}}*/
 342 // AllUpgrade - Upgrade as many packages as possible                    /*{{{*/
 343 // ---------------------------------------------------------------------
 344 /* Right now the system must be consistent before this can be called.
 345    It also will not change packages marked for install, it only tries
 346    to install packages not marked for install */
 347 bool pkgAllUpgrade(pkgDepCache &Cache)
 348 {
 349    pkgProblemResolver Fix(&Cache);
 350
 351    if (Cache.BrokenCount() != 0)
 352       return false;
 353
 354    // Upgrade all installed packages
 355    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 356    {
 357       if (Cache[I].Install() == true)
 358          Fix.Protect(I);
 359
 360       if (_config->FindB("APT::Ignore-Hold",false) == false)
 361          if (I->SelectedState == pkgCache::State::Hold)
 362             continue;
 363
 364       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
 365          Cache.MarkInstall(I,false);
 366    }
 367
 368    return Fix.ResolveByKeep();
 369 }
 370                                                                         /*}}}*/
 371 // MinimizeUpgrade - Minimizes the set of packages to be upgraded       /*{{{*/
 372 // ---------------------------------------------------------------------
 373 /* This simply goes over the entire set of packages and tries to keep
 374    each package marked for upgrade. If a conflict is generated then
 375    the package is restored. */
 376 bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 377 {
 378    if (Cache.BrokenCount() != 0)
 379       return false;
 380
 381    // We loop for 10 tries to get the minimal set size.
 382    bool Change = false;
 383    unsigned int Count = 0;
 384    do
 385    {
 386       Change = false;
 387       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 388       {
 389          // Not interesting
 390          if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
 391             continue;
 392
 393          // Keep it and see if that is OK
 394          Cache.MarkKeep(I);
 395          if (Cache.BrokenCount() != 0)
 396             Cache.MarkInstall(I,false);
 397          else
 398          {
 399             // If keep didnt actually do anything then there was no change..
 400             if (Cache[I].Upgrade() == false)
 401                Change = true;
 402          }
 403       }
 404       Count++;
 405    }
 406    while (Change == true && Count < 10);
 407
 408    if (Cache.BrokenCount() != 0)
 409       return _error->Error("Internal Error in pkgMinimizeUpgrade");
 410
 411    return true;
 412 }
 413                                                                         /*}}}*/
 414
 415 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
 416 // ---------------------------------------------------------------------
 417 /* */
 418 pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : Cache(*pCache)
 419 {
 420    // Allocate memory
 421    unsigned long Size = Cache.Head().PackageCount;
 422    Scores = new signed short[Size];
 423    Flags = new unsigned char[Size];
 424    memset(Flags,0,sizeof(*Flags)*Size);
 425
 426    // Set debug to true to see its decision logic
 427    Debug = _config->FindB("Debug::pkgProblemResolver",false);
 428 }
 429                                                                         /*}}}*/
 430 // ProblemResolver::~pkgProblemResolver - Destructor                    /*{{{*/
 431 // ---------------------------------------------------------------------
 432 /* */
 433 pkgProblemResolver::~pkgProblemResolver()
 434 {
 435    delete [] Scores;
 436    delete [] Flags;
 437 }
 438                                                                         /*}}}*/
 439 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
 440 // ---------------------------------------------------------------------
 441 /* */
 442 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
 443 {
 444    Package const **A = (Package const **)a;
 445    Package const **B = (Package const **)b;
 446    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
 447       return -1;
 448    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
 449       return 1;
 450    return 0;
 451 }
 452                                                                         /*}}}*/
 453 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
 454 // ---------------------------------------------------------------------
 455 /* */
 456 void pkgProblemResolver::MakeScores()
 457 {
 458    unsigned long Size = Cache.Head().PackageCount;
 459    memset(Scores,0,sizeof(*Scores)*Size);
 460
 461    // Generate the base scores for a package based on its properties
 462    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 463    {
 464       if (Cache[I].InstallVer == 0)
 465          continue;
 466
 467       signed short &Score = Scores[I->ID];
 468
 469       /* This is arbitary, it should be high enough to elevate an
 470          essantial package above most other packages but low enough
 471          to allow an obsolete essential packages to be removed by
 472          a conflicts on a powerfull normal package (ie libc6) */
 473       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 474          Score += 100;
 475
 476       // We transform the priority
 477       // Important Required Standard Optional Extra
 478       signed short PrioMap[] = {0,3,2,1,-1,-2};
 479       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 480          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 481
 482       /* This helps to fix oddball problems with conflicting packages
 483          on the same level. We enhance the score of installed packages */
 484       if (I->CurrentVer != 0)
 485          Score += 1;
 486    }
 487
 488    // Now that we have the base scores we go and propogate dependencies
 489    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 490    {
 491       if (Cache[I].InstallVer == 0)
 492          continue;
 493
 494       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 495       {
 496          if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 497             Scores[D.TargetPkg()->ID]++;
 498       }
 499    }
 500
 501    // Copy the scores to advoid additive looping
 502    SPtrArray<signed short> OldScores = new signed short[Size];
 503    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 504
 505    /* Now we cause 1 level of dependency inheritance, that is we add the
 506       score of the packages that depend on the target Package. This
 507       fortifies high scoring packages */
 508    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 509    {
 510       if (Cache[I].InstallVer == 0)
 511          continue;
 512
 513       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 514       {
 515          // Only do it for the install version
 516          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 517              (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends))
 518             continue;
 519
 520          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 521       }
 522    }
 523
 524    /* Now we propogate along provides. This makes the packages that
 525       provide important packages extremely important */
 526    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 527    {
 528       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 529       {
 530          // Only do it once per package
 531          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 532             continue;
 533          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 534       }
 535    }
 536
 537    /* Protected things are pushed really high up. This number should put them
 538       ahead of everything */
 539    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 540    {
 541       if ((Flags[I->ID] & Protected) != 0)
 542          Scores[I->ID] += 10000;
 543       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 544          Scores[I->ID] += 5000;
 545    }
 546 }
 547                                                                         /*}}}*/
 548 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 549 // ---------------------------------------------------------------------
 550 /* This goes through and tries to reinstall packages to make this package
 551    installable */
 552 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 553 {
 554    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 555       return false;
 556
 557    Flags[Pkg->ID] &= ~Upgradable;
 558
 559    bool WasKept = Cache[Pkg].Keep();
 560    Cache.MarkInstall(Pkg,false);
 561
 562    // This must be a virtual package or something like that.
 563    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 564       return false;
 565
 566    // Isolate the problem dependency
 567    bool Fail = false;
 568    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 569    {
 570       // Compute a single dependency element (glob or)
 571       pkgCache::DepIterator Start = D;
 572       pkgCache::DepIterator End = D;
 573       unsigned char State = 0;
 574       for (bool LastOR = true; D.end() == false && LastOR == true;)
 575       {
 576          State |= Cache[D];
 577          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 578          D++;
 579          if (LastOR == true)
 580             End = D;
 581       }
 582
 583       // We only worry about critical deps.
 584       if (End.IsCritical() != true)
 585          continue;
 586
 587       // Iterate over all the members in the or group
 588       while (1)
 589       {
 590          // Dep is ok now
 591          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 592             break;
 593
 594          // Do not change protected packages
 595          PkgIterator P = Start.SmartTargetPkg();
 596          if ((Flags[P->ID] & Protected) == Protected)
 597          {
 598             if (Debug == true)
 599                clog << "    Reinst Failed because of protected " << P.Name() << endl;
 600             Fail = true;
 601          }
 602          else
 603          {
 604             // Upgrade the package if the candidate version will fix the problem.
 605             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 606             {
 607                if (DoUpgrade(P) == false)
 608                {
 609                   if (Debug == true)
 610                      clog << "    Reinst Failed because of " << P.Name() << endl;
 611                   Fail = true;
 612                }
 613                else
 614                {
 615                   Fail = false;
 616                   break;
 617                }
 618             }
 619             else
 620             {
 621                /* We let the algorithm deal with conflicts on its next iteration,
 622                 it is much smarter than us */
 623                if (Start->Type == pkgCache::Dep::Conflicts ||
 624                    Start->Type == pkgCache::Dep::Obsoletes)
 625                    break;
 626
 627                if (Debug == true)
 628                   clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 629                Fail = true;
 630             }
 631          }
 632
 633          if (Start == End)
 634             break;
 635          Start++;
 636       }
 637       if (Fail == true)
 638          break;
 639    }
 640
 641    // Undo our operations - it might be smart to undo everything this did..
 642    if (Fail == true)
 643    {
 644       if (WasKept == true)
 645          Cache.MarkKeep(Pkg);
 646       else
 647          Cache.MarkDelete(Pkg);
 648       return false;
 649    }
 650
 651    if (Debug == true)
 652       clog << "  Re-Instated " << Pkg.Name() << endl;
 653    return true;
 654 }
 655                                                                         /*}}}*/
 656 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 657 // ---------------------------------------------------------------------
 658 /* This routines works by calculating a score for each package. The score
 659    is derived by considering the package's priority and all reverse
 660    dependents giving an integer that reflects the amount of breakage that
 661    adjusting the package will inflict.
 662
 663    It goes from highest score to lowest and corrects all of the breaks by
 664    keeping or removing the dependant packages. If that fails then it removes
 665    the package itself and goes on. The routine should be able to intelligently
 666    go from any broken state to a fixed state.
 667
 668    The BrokenFix flag enables a mode where the algorithm tries to
 669    upgrade packages to advoid problems. */
 670 bool pkgProblemResolver::Resolve(bool BrokenFix)
 671 {
 672    unsigned long Size = Cache.Head().PackageCount;
 673
 674    // Record which packages are marked for install
 675    bool Again = false;
 676    do
 677    {
 678       Again = false;
 679       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 680       {
 681          if (Cache[I].Install() == true)
 682             Flags[I->ID] |= PreInstalled;
 683          else
 684          {
 685             if (Cache[I].InstBroken() == true && BrokenFix == true)
 686             {
 687                Cache.MarkInstall(I,false);
 688                if (Cache[I].Install() == true)
 689                   Again = true;
 690             }
 691
 692             Flags[I->ID] &= ~PreInstalled;
 693          }
 694          Flags[I->ID] |= Upgradable;
 695       }
 696    }
 697    while (Again == true);
 698
 699    if (Debug == true)
 700       clog << "Starting" << endl;
 701
 702    MakeScores();
 703
 704    /* We have to order the packages so that the broken fixing pass
 705       operates from highest score to lowest. This prevents problems when
 706       high score packages cause the removal of lower score packages that
 707       would cause the removal of even lower score packages. */
 708    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 709    pkgCache::Package **PEnd = PList;
 710    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 711       *PEnd++ = I;
 712    This = this;
 713    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 714
 715 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
 716       if (Scores[(*K)->ID] != 0)
 717       {
 718          pkgCache::PkgIterator Pkg(Cache,*K);
 719          clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
 720             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
 721             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
 722       } */
 723
 724    if (Debug == true)
 725       clog << "Starting 2" << endl;
 726
 727    /* Now consider all broken packages. For each broken package we either
 728       remove the package or fix it's problem. We do this once, it should
 729       not be possible for a loop to form (that is a < b < c and fixing b by
 730       changing a breaks c) */
 731    bool Change = true;
 732    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 733    {
 734       Change = false;
 735       for (pkgCache::Package **K = PList; K != PEnd; K++)
 736       {
 737          pkgCache::PkgIterator I(Cache,*K);
 738
 739          /* We attempt to install this and see if any breaks result,
 740             this takes care of some strange cases */
 741          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 742              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 743              (Flags[I->ID] & PreInstalled) != 0 &&
 744              (Flags[I->ID] & Protected) == 0 &&
 745              (Flags[I->ID] & ReInstateTried) == 0)
 746          {
 747             if (Debug == true)
 748                clog << " Try to Re-Instate " << I.Name() << endl;
 749             unsigned long OldBreaks = Cache.BrokenCount();
 750             pkgCache::Version *OldVer = Cache[I].InstallVer;
 751             Flags[I->ID] &= ReInstateTried;
 752
 753             Cache.MarkInstall(I,false);
 754             if (Cache[I].InstBroken() == true ||
 755                 OldBreaks < Cache.BrokenCount())
 756             {
 757                if (OldVer == 0)
 758                   Cache.MarkDelete(I);
 759                else
 760                   Cache.MarkKeep(I);
 761             }
 762             else
 763                if (Debug == true)
 764                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 765          }
 766
 767          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 768             continue;
 769
 770          if (Debug == true)
 771             cout << "Investigating " << I.Name() << endl;
 772
 773          // Isolate the problem dependency
 774          PackageKill KillList[100];
 775          PackageKill *LEnd = KillList;
 776          bool InOr = false;
 777          pkgCache::DepIterator Start;
 778          pkgCache::DepIterator End;
 779          PackageKill *OldEnd = LEnd;
 780
 781          enum {OrRemove,OrKeep} OrOp = OrRemove;
 782          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 783               D.end() == false || InOr == true;)
 784          {
 785             // Compute a single dependency element (glob or)
 786             if (Start == End)
 787             {
 788                // Decide what to do
 789                if (InOr == true)
 790                {
 791                   if (OldEnd == LEnd && OrOp == OrRemove)
 792                   {
 793                      if ((Flags[I->ID] & Protected) != Protected)
 794                      {
 795                         if (Debug == true)
 796                            clog << "  Or group remove for " << I.Name() << endl;
 797                         Cache.MarkDelete(I);
 798                      }
 799                   }
 800                   if (OldEnd == LEnd && OrOp == OrKeep)
 801                   {
 802                      if (Debug == true)
 803                         clog << "  Or group keep for " << I.Name() << endl;
 804                      Cache.MarkKeep(I);
 805                   }
 806                }
 807
 808                /* We do an extra loop (as above) to finalize the or group
 809                   processing */
 810                InOr = false;
 811                OrOp = OrRemove;
 812                D.GlobOr(Start,End);
 813                if (Start.end() == true)
 814                   break;
 815
 816                // We only worry about critical deps.
 817                if (End.IsCritical() != true)
 818                   continue;
 819
 820                InOr = Start != End;
 821                OldEnd = LEnd;
 822             }
 823             else
 824                Start++;
 825
 826             // Dep is ok
 827             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 828                continue;
 829
 830             if (Debug == true)
 831                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
 832
 833             /* Look across the version list. If there are no possible
 834                targets then we keep the package and bail. This is necessary
 835                if a package has a dep on another package that cant be found */
 836             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 837             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 838                 Start->Type != pkgCache::Dep::Conflicts &&
 839                 Start->Type != pkgCache::Dep::Obsoletes &&
 840                 Cache[I].NowBroken() == false)
 841             {
 842                if (InOr == true)
 843                {
 844                   /* No keep choice because the keep being OK could be the
 845                      result of another element in the OR group! */
 846                   continue;
 847                }
 848
 849                Change = true;
 850                Cache.MarkKeep(I);
 851                break;
 852             }
 853
 854             bool Done = false;
 855             for (pkgCache::Version **V = VList; *V != 0; V++)
 856             {
 857                pkgCache::VerIterator Ver(Cache,*V);
 858                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 859
 860                if (Debug == true)
 861                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 862                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 863
 864                /* Try to fix the package under consideration rather than
 865                   fiddle with the VList package */
 866                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 867                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 868                     End->Type != pkgCache::Dep::Conflicts &&
 869                     End->Type != pkgCache::Dep::Obsoletes))
 870                {
 871                   // Try a little harder to fix protected packages..
 872                   if ((Flags[I->ID] & Protected) == Protected)
 873                   {
 874                      if (DoUpgrade(Pkg) == true)
 875                      {
 876                         if (Scores[Pkg->ID] > Scores[I->ID])
 877                            Scores[Pkg->ID] = Scores[I->ID];
 878                         break;
 879                      }
 880
 881                      continue;
 882                   }
 883
 884                   /* See if a keep will do, unless the package is protected,
 885                      then installing it will be necessary */
 886                   bool Installed = Cache[I].Install();
 887                   Cache.MarkKeep(I);
 888                   if (Cache[I].InstBroken() == false)
 889                   {
 890                      // Unwind operation will be keep now
 891                      if (OrOp == OrRemove)
 892                         OrOp = OrKeep;
 893
 894                      // Restore
 895                      if (InOr == true && Installed == true)
 896                         Cache.MarkInstall(I,false);
 897
 898                      if (Debug == true)
 899                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 900                   }
 901                   else
 902                   {
 903                      if (BrokenFix == false || DoUpgrade(I) == false)
 904                      {
 905                         // Consider other options
 906                         if (InOr == false)
 907                         {
 908                            if (Debug == true)
 909                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 910                            Cache.MarkDelete(I);
 911                            if (Counter > 1)
 912                            {
 913                               if (Scores[Pkg->ID] > Scores[I->ID])
 914                                  Scores[I->ID] = Scores[Pkg->ID];
 915                            }
 916                         }
 917                      }
 918                   }
 919
 920                   Change = true;
 921                   Done = true;
 922                   break;
 923                }
 924                else
 925                {
 926                   /* This is a conflicts, and the version we are looking
 927                      at is not the currently selected version of the
 928                      package, which means it is not necessary to
 929                      remove/keep */
 930                   if (Cache[Pkg].InstallVer != Ver &&
 931                       (Start->Type == pkgCache::Dep::Conflicts ||
 932                        Start->Type == pkgCache::Dep::Obsoletes))
 933                      continue;
 934
 935                   // Skip adding to the kill list if it is protected
 936                   if ((Flags[Pkg->ID] & Protected) != 0)
 937                      continue;
 938
 939                   if (Debug == true)
 940                      clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
 941
 942                   LEnd->Pkg = Pkg;
 943                   LEnd->Dep = End;
 944                   LEnd++;
 945
 946                   if (Start->Type != pkgCache::Dep::Conflicts &&
 947                       Start->Type != pkgCache::Dep::Obsoletes)
 948                      break;
 949                }
 950             }
 951
 952             // Hm, nothing can possibly satisify this dep. Nuke it.
 953             if (VList[0] == 0 &&
 954                 Start->Type != pkgCache::Dep::Conflicts &&
 955                 Start->Type != pkgCache::Dep::Obsoletes &&
 956                 (Flags[I->ID] & Protected) != Protected)
 957             {
 958                bool Installed = Cache[I].Install();
 959                Cache.MarkKeep(I);
 960                if (Cache[I].InstBroken() == false)
 961                {
 962                   // Unwind operation will be keep now
 963                   if (OrOp == OrRemove)
 964                      OrOp = OrKeep;
 965
 966                   // Restore
 967                   if (InOr == true && Installed == true)
 968                      Cache.MarkInstall(I,false);
 969
 970                   if (Debug == true)
 971                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 972                }
 973                else
 974                {
 975                   if (Debug == true)
 976                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 977                   if (InOr == false)
 978                      Cache.MarkDelete(I);
 979                }
 980
 981                Change = true;
 982                Done = true;
 983             }
 984
 985             // Try some more
 986             if (InOr == true)
 987                continue;
 988
 989             if (Done == true)
 990                break;
 991          }
 992
 993          // Apply the kill list now
 994          if (Cache[I].InstallVer != 0)
 995          {
 996             for (PackageKill *J = KillList; J != LEnd; J++)
 997             {
 998                Change = true;
 999                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1000                {
1001                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1002                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1003                   {
1004                      if (Debug == true)
1005                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
1006                      Cache.MarkDelete(J->Pkg);
1007                   }
1008                }
1009                else
1010                {
1011                   if (Debug == true)
1012                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
1013                   Cache.MarkKeep(J->Pkg);
1014                }
1015
1016                if (Counter > 1)
1017                {
1018                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1019                      Scores[J->Pkg->ID] = Scores[I->ID];
1020                }
1021             }
1022          }
1023       }
1024    }
1025
1026    if (Debug == true)
1027       clog << "Done" << endl;
1028
1029    if (Cache.BrokenCount() != 0)
1030    {
1031       // See if this is the result of a hold
1032       pkgCache::PkgIterator I = Cache.PkgBegin();
1033       for (;I.end() != true; I++)
1034       {
1035          if (Cache[I].InstBroken() == false)
1036             continue;
1037          if ((Flags[I->ID] & Protected) != Protected)
1038             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1039       }
1040       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1041    }
1042
1043    return true;
1044 }
1045                                                                         /*}}}*/
1046 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1047 // ---------------------------------------------------------------------
1048 /* This is the work horse of the soft upgrade routine. It is very gental
1049    in that it does not install or remove any packages. It is assumed that the
1050    system was non-broken previously. */
1051 bool pkgProblemResolver::ResolveByKeep()
1052 {
1053    unsigned long Size = Cache.Head().PackageCount;
1054
1055    if (Debug == true)
1056       clog << "Entering ResolveByKeep" << endl;
1057
1058    MakeScores();
1059
1060    /* We have to order the packages so that the broken fixing pass
1061       operates from highest score to lowest. This prevents problems when
1062       high score packages cause the removal of lower score packages that
1063       would cause the removal of even lower score packages. */
1064    pkgCache::Package **PList = new pkgCache::Package *[Size];
1065    pkgCache::Package **PEnd = PList;
1066    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1067       *PEnd++ = I;
1068    This = this;
1069    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1070
1071    // Consider each broken package
1072    pkgCache::Package **LastStop = 0;
1073    for (pkgCache::Package **K = PList; K != PEnd; K++)
1074    {
1075       pkgCache::PkgIterator I(Cache,*K);
1076
1077       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1078          continue;
1079
1080       /* Keep the package. If this works then great, otherwise we have
1081          to be significantly more agressive and manipulate its dependencies */
1082       if ((Flags[I->ID] & Protected) == 0)
1083       {
1084          if (Debug == true)
1085             clog << "Keeping package " << I.Name() << endl;
1086          Cache.MarkKeep(I);
1087          if (Cache[I].InstBroken() == false)
1088          {
1089             K = PList - 1;
1090             continue;
1091          }
1092       }
1093
1094       // Isolate the problem dependencies
1095       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1096       {
1097          // Compute a single dependency element (glob or)
1098          pkgCache::DepIterator Start = D;
1099          pkgCache::DepIterator End = D;
1100          unsigned char State = 0;
1101          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
1102          {
1103             State |= Cache[D];
1104             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
1105             if (LastOR == true)
1106                End = D;
1107          }
1108
1109          // We only worry about critical deps.
1110          if (End.IsCritical() != true)
1111             continue;
1112
1113          // Dep is ok
1114          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1115             continue;
1116
1117          // Hm, the group is broken.. I have no idea how to handle this
1118          if (Start != End)
1119          {
1120             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
1121             if ((Flags[I->ID] & Protected) == 0)
1122                Cache.MarkKeep(I);
1123             break;
1124          }
1125
1126          if (Debug == true)
1127             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
1128
1129          // Look at all the possible provides on this package
1130          SPtrArray<pkgCache::Version *> VList = End.AllTargets();
1131          for (pkgCache::Version **V = VList; *V != 0; V++)
1132          {
1133             pkgCache::VerIterator Ver(Cache,*V);
1134             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1135
1136             // It is not keepable
1137             if (Cache[Pkg].InstallVer == 0 ||
1138                 Pkg->CurrentVer == 0)
1139                continue;
1140
1141             if ((Flags[I->ID] & Protected) == 0)
1142             {
1143                if (Debug == true)
1144                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1145                Cache.MarkKeep(Pkg);
1146             }
1147
1148             if (Cache[I].InstBroken() == false)
1149                break;
1150          }
1151
1152          if (Cache[I].InstBroken() == false)
1153             break;
1154       }
1155
1156       if (Cache[I].InstBroken() == true)
1157          continue;
1158
1159       // Restart again.
1160       if (K == LastStop)
1161          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1162       LastStop = K;
1163       K = PList - 1;
1164    }
1165
1166    return true;
1167 }
1168                                                                         /*}}}*/
1169 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1170 // ---------------------------------------------------------------------
1171 /* This is used to make sure protected packages are installed */
1172 void pkgProblemResolver::InstallProtect()
1173 {
1174    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1175    {
1176       if ((Flags[I->ID] & Protected) == Protected)
1177       {
1178          if ((Flags[I->ID] & ToRemove) == ToRemove)
1179             Cache.MarkDelete(I);
1180          else
1181             Cache.MarkInstall(I,false);
1182       }
1183    }
1184 }
1185                                                                         /*}}}*/
1186
1187 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1188 // ---------------------------------------------------------------------
1189 /* This is ment to be used in conjunction with AllTargets to get a list
1190    of versions ordered by preference. */
1191 static pkgCache *PrioCache;
1192 static int PrioComp(const void *A,const void *B)
1193 {
1194    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1195    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1196
1197    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1198        (L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1199    return 1;
1200    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1201        (L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1202    return -1;
1203
1204    if (L->Priority != R->Priority)
1205       return L->Priority - R->Priority;
1206    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1207 }
1208 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1209 {
1210    unsigned long Count = 0;
1211    PrioCache = &Cache;
1212    for (pkgCache::Version **I = List; *I != 0; I++)
1213       Count++;
1214    qsort(List,Count,sizeof(*List),PrioComp);
1215 }
1216                                                                         /*}}}*/