apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.32 2001/02/20 07:03:17 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().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().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 indefinately 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                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 864                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 865                     End->Type != pkgCache::Dep::Conflicts &&
 866                     End->Type != pkgCache::Dep::Obsoletes))
 867                {
 868                   // Try a little harder to fix protected packages..
 869                   if ((Flags[I->ID] & Protected) == Protected)
 870                   {
 871                      if (DoUpgrade(Pkg) == true)
 872                      {
 873                         if (Scores[Pkg->ID] > Scores[I->ID])
 874                            Scores[Pkg->ID] = Scores[I->ID];
 875                         break;
 876                      }
 877
 878                      continue;
 879                   }
 880
 881                   /* See if a keep will do, unless the package is protected,
 882                      then installing it will be necessary */
 883                   bool Installed = Cache[I].Install();
 884                   Cache.MarkKeep(I);
 885                   if (Cache[I].InstBroken() == false)
 886                   {
 887                      // Unwind operation will be keep now
 888                      if (OrOp == OrRemove)
 889                         OrOp = OrKeep;
 890
 891                      // Restore
 892                      if (InOr == true && Installed == true)
 893                         Cache.MarkInstall(I,false);
 894
 895                      if (Debug == true)
 896                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 897                   }
 898                   else
 899                   {
 900                      if (BrokenFix == false || DoUpgrade(I) == false)
 901                      {
 902                         // Consider other options
 903                         if (InOr == false)
 904                         {
 905                            if (Debug == true)
 906                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 907                            Cache.MarkDelete(I);
 908                            if (Counter > 1)
 909                            {
 910                               if (Scores[Pkg->ID] > Scores[I->ID])
 911                                  Scores[I->ID] = Scores[Pkg->ID];
 912                            }
 913                         }
 914                      }
 915                   }
 916
 917                   Change = true;
 918                   Done = true;
 919                   break;
 920                }
 921                else
 922                {
 923                   if (Debug == true)
 924                      clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
 925                   // Skip adding to the kill list if it is protected
 926                   if ((Flags[Pkg->ID] & Protected) != 0)
 927                      continue;
 928
 929                   LEnd->Pkg = Pkg;
 930                   LEnd->Dep = End;
 931                   LEnd++;
 932
 933                   if (Start->Type != pkgCache::Dep::Conflicts &&
 934                       Start->Type != pkgCache::Dep::Obsoletes)
 935                      break;
 936                }
 937             }
 938
 939             // Hm, nothing can possibly satisify this dep. Nuke it.
 940             if (VList[0] == 0 &&
 941                 Start->Type != pkgCache::Dep::Conflicts &&
 942                 Start->Type != pkgCache::Dep::Obsoletes &&
 943                 (Flags[I->ID] & Protected) != Protected)
 944             {
 945                bool Installed = Cache[I].Install();
 946                Cache.MarkKeep(I);
 947                if (Cache[I].InstBroken() == false)
 948                {
 949                   // Unwind operation will be keep now
 950                   if (OrOp == OrRemove)
 951                      OrOp = OrKeep;
 952
 953                   // Restore
 954                   if (InOr == true && Installed == true)
 955                      Cache.MarkInstall(I,false);
 956
 957                   if (Debug == true)
 958                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 959                }
 960                else
 961                {
 962                   if (Debug == true)
 963                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 964                   if (InOr == false)
 965                      Cache.MarkDelete(I);
 966                }
 967
 968                Change = true;
 969                Done = true;
 970             }
 971
 972             // Try some more
 973             if (InOr == true)
 974                continue;
 975
 976             if (Done == true)
 977                break;
 978          }
 979
 980          // Apply the kill list now
 981          if (Cache[I].InstallVer != 0)
 982          {
 983             for (PackageKill *J = KillList; J != LEnd; J++)
 984             {
 985                Change = true;
 986                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 987                {
 988                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
 989                       J->Dep->Type == pkgCache::Dep::Obsoletes)
 990                   {
 991                      if (Debug == true)
 992                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 993                      Cache.MarkDelete(J->Pkg);
 994                   }
 995                }
 996                else
 997                {
 998                   if (Debug == true)
 999                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
1000                   Cache.MarkKeep(J->Pkg);
1001                }
1002
1003                if (Counter > 1)
1004                {
1005                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1006                      Scores[J->Pkg->ID] = Scores[I->ID];
1007                }
1008             }
1009          }
1010       }
1011    }
1012
1013    if (Debug == true)
1014       clog << "Done" << endl;
1015
1016    if (Cache.BrokenCount() != 0)
1017    {
1018       // See if this is the result of a hold
1019       pkgCache::PkgIterator I = Cache.PkgBegin();
1020       for (;I.end() != true; I++)
1021       {
1022          if (Cache[I].InstBroken() == false)
1023             continue;
1024          if ((Flags[I->ID] & Protected) != Protected)
1025             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1026       }
1027       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1028    }
1029
1030    return true;
1031 }
1032                                                                         /*}}}*/
1033 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1034 // ---------------------------------------------------------------------
1035 /* This is the work horse of the soft upgrade routine. It is very gental
1036    in that it does not install or remove any packages. It is assumed that the
1037    system was non-broken previously. */
1038 bool pkgProblemResolver::ResolveByKeep()
1039 {
1040    unsigned long Size = Cache.Head().PackageCount;
1041
1042    if (Debug == true)
1043       clog << "Entering ResolveByKeep" << endl;
1044
1045    MakeScores();
1046
1047    /* We have to order the packages so that the broken fixing pass
1048       operates from highest score to lowest. This prevents problems when
1049       high score packages cause the removal of lower score packages that
1050       would cause the removal of even lower score packages. */
1051    pkgCache::Package **PList = new pkgCache::Package *[Size];
1052    pkgCache::Package **PEnd = PList;
1053    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1054       *PEnd++ = I;
1055    This = this;
1056    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1057
1058    // Consider each broken package
1059    pkgCache::Package **LastStop = 0;
1060    for (pkgCache::Package **K = PList; K != PEnd; K++)
1061    {
1062       pkgCache::PkgIterator I(Cache,*K);
1063
1064       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1065          continue;
1066
1067       /* Keep the package. If this works then great, otherwise we have
1068          to be significantly more agressive and manipulate its dependencies */
1069       if ((Flags[I->ID] & Protected) == 0)
1070       {
1071          if (Debug == true)
1072             clog << "Keeping package " << I.Name() << endl;
1073          Cache.MarkKeep(I);
1074          if (Cache[I].InstBroken() == false)
1075          {
1076             K = PList - 1;
1077             continue;
1078          }
1079       }
1080
1081       // Isolate the problem dependencies
1082       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1083       {
1084          // Compute a single dependency element (glob or)
1085          pkgCache::DepIterator Start = D;
1086          pkgCache::DepIterator End = D;
1087          unsigned char State = 0;
1088          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
1089          {
1090             State |= Cache[D];
1091             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
1092             if (LastOR == true)
1093                End = D;
1094          }
1095
1096          // We only worry about critical deps.
1097          if (End.IsCritical() != true)
1098             continue;
1099
1100          // Dep is ok
1101          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1102             continue;
1103
1104          // Hm, the group is broken.. I have no idea how to handle this
1105          if (Start != End)
1106          {
1107             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
1108             if ((Flags[I->ID] & Protected) == 0)
1109                Cache.MarkKeep(I);
1110             break;
1111          }
1112
1113          if (Debug == true)
1114             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
1115
1116          // Look at all the possible provides on this package
1117          SPtrArray<pkgCache::Version *> VList = End.AllTargets();
1118          for (pkgCache::Version **V = VList; *V != 0; V++)
1119          {
1120             pkgCache::VerIterator Ver(Cache,*V);
1121             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1122
1123             // It is not keepable
1124             if (Cache[Pkg].InstallVer == 0 ||
1125                 Pkg->CurrentVer == 0)
1126                continue;
1127
1128             if ((Flags[I->ID] & Protected) == 0)
1129             {
1130                if (Debug == true)
1131                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1132                Cache.MarkKeep(Pkg);
1133             }
1134
1135             if (Cache[I].InstBroken() == false)
1136                break;
1137          }
1138
1139          if (Cache[I].InstBroken() == false)
1140             break;
1141       }
1142
1143       if (Cache[I].InstBroken() == true)
1144          continue;
1145
1146       // Restart again.
1147       if (K == LastStop)
1148          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1149       LastStop = K;
1150       K = PList - 1;
1151    }
1152
1153    return true;
1154 }
1155                                                                         /*}}}*/
1156 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1157 // ---------------------------------------------------------------------
1158 /* This is used to make sure protected packages are installed */
1159 void pkgProblemResolver::InstallProtect()
1160 {
1161    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1162    {
1163       if ((Flags[I->ID] & Protected) == Protected)
1164       {
1165          if ((Flags[I->ID] & ToRemove) == ToRemove)
1166             Cache.MarkDelete(I);
1167          else
1168             Cache.MarkInstall(I,false);
1169       }
1170    }
1171 }
1172                                                                         /*}}}*/
1173
1174 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1175 // ---------------------------------------------------------------------
1176 /* This is ment to be used in conjunction with AllTargets to get a list
1177    of versions ordered by preference. */
1178 static pkgCache *PrioCache;
1179 static int PrioComp(const void *A,const void *B)
1180 {
1181    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1182    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1183
1184    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1185        (L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1186    return 1;
1187    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1188        (L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1189    return -1;
1190
1191    if (L->Priority != R->Priority)
1192       return L->Priority - R->Priority;
1193    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1194 }
1195 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1196 {
1197    unsigned long Count = 0;
1198    PrioCache = &Cache;
1199    for (pkgCache::Version **I = List; *I != 0; I++)
1200       Count++;
1201    qsort(List,Count,sizeof(*List),PrioComp);
1202 }
1203                                                                         /*}}}*/