apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.44 2002/11/28 18:49:16 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 #include <apt-pkg/algorithms.h>
  18 #include <apt-pkg/error.h>
  19 #include <apt-pkg/configuration.h>
  20 #include <apt-pkg/version.h>
  21 #include <apt-pkg/sptr.h>
  22 #include <apt-pkg/acquire-item.h>
  23 #include <apt-pkg/edsp.h>
  24
  25 #include <apti18n.h>
  26 #include <sys/types.h>
  27 #include <cstdlib>
  28 #include <algorithm>
  29 #include <iostream>
  30
  31 #include <stdio.h>
  32                                                                         /*}}}*/
  33 using namespace std;
  34
  35 pkgProblemResolver *pkgProblemResolver::This = 0;
  36
  37 // Simulate::Simulate - Constructor                                     /*{{{*/
  38 // ---------------------------------------------------------------------
  39 /* The legacy translations here of input Pkg iterators is obsolete,
  40    this is not necessary since the pkgCaches are fully shared now. */
  41 pkgSimulate::pkgSimulate(pkgDepCache *Cache) : pkgPackageManager(Cache),
  42                             iPolicy(Cache),
  43                             Sim(&Cache->GetCache(),&iPolicy),
  44                             group(Sim)
  45 {
  46    Sim.Init(0);
  47    Flags = new unsigned char[Cache->Head().PackageCount];
  48    memset(Flags,0,sizeof(*Flags)*Cache->Head().PackageCount);
  49
  50    // Fake a filename so as not to activate the media swapping
  51    string Jnk = "SIMULATE";
  52    for (unsigned int I = 0; I != Cache->Head().PackageCount; I++)
  53       FileNames[I] = Jnk;
  54 }
  55                                                                         /*}}}*/
  56 // Simulate::Describe - Describe a package                              /*{{{*/
  57 // ---------------------------------------------------------------------
  58 /* Parameter Current == true displays the current package version,
  59    Parameter Candidate == true displays the candidate package version */
  60 void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Current,bool Candidate)
  61 {
  62    VerIterator Ver(Sim);
  63
  64    out << Pkg.FullName(true);
  65
  66    if (Current == true)
  67    {
  68       Ver = Pkg.CurrentVer();
  69       if (Ver.end() == false)
  70          out << " [" << Ver.VerStr() << ']';
  71    }
  72
  73    if (Candidate == true)
  74    {
  75       Ver = Sim[Pkg].CandidateVerIter(Sim);
  76       if (Ver.end() == true)
  77          return;
  78
  79       out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')';
  80    }
  81 }
  82                                                                         /*}}}*/
  83 // Simulate::Install - Simulate unpacking of a package                  /*{{{*/
  84 // ---------------------------------------------------------------------
  85 /* */
  86 bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/)
  87 {
  88    // Adapt the iterator
  89    PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
  90    Flags[Pkg->ID] = 1;
  91
  92    cout << "Inst ";
  93    Describe(Pkg,cout,true,true);
  94    Sim.MarkInstall(Pkg,false);
  95
  96    // Look for broken conflicts+predepends.
  97    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
  98    {
  99       if (Sim[I].InstallVer == 0)
 100          continue;
 101
 102       for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false;)
 103       {
 104          DepIterator Start;
 105          DepIterator End;
 106          D.GlobOr(Start,End);
 107          if (Start->Type == pkgCache::Dep::Conflicts ||
 108              Start->Type == pkgCache::Dep::DpkgBreaks ||
 109              Start->Type == pkgCache::Dep::Obsoletes ||
 110              End->Type == pkgCache::Dep::PreDepends)
 111          {
 112             if ((Sim[End] & pkgDepCache::DepGInstall) == 0)
 113             {
 114                cout << " [" << I.FullName(false) << " on " << Start.TargetPkg().FullName(false) << ']';
 115                if (Start->Type == pkgCache::Dep::Conflicts)
 116                   _error->Error("Fatal, conflicts violated %s",I.FullName(false).c_str());
 117             }
 118          }
 119       }
 120    }
 121
 122    if (Sim.BrokenCount() != 0)
 123       ShortBreaks();
 124    else
 125       cout << endl;
 126    return true;
 127 }
 128                                                                         /*}}}*/
 129 // Simulate::Configure - Simulate configuration of a Package            /*{{{*/
 130 // ---------------------------------------------------------------------
 131 /* This is not an acurate simulation of relatity, we should really not
 132    install the package.. For some investigations it may be necessary
 133    however. */
 134 bool pkgSimulate::Configure(PkgIterator iPkg)
 135 {
 136    // Adapt the iterator
 137    PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
 138
 139    Flags[Pkg->ID] = 2;
 140
 141    if (Sim[Pkg].InstBroken() == true)
 142    {
 143       cout << "Conf " << Pkg.FullName(false) << " broken" << endl;
 144
 145       Sim.Update();
 146
 147       // Print out each package and the failed dependencies
 148       for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; D++)
 149       {
 150          if (Sim.IsImportantDep(D) == false ||
 151              (Sim[D] & pkgDepCache::DepInstall) != 0)
 152             continue;
 153
 154          if (D->Type == pkgCache::Dep::Obsoletes)
 155             cout << " Obsoletes:" << D.TargetPkg().FullName(false);
 156          else if (D->Type == pkgCache::Dep::Conflicts)
 157             cout << " Conflicts:" << D.TargetPkg().FullName(false);
 158          else if (D->Type == pkgCache::Dep::DpkgBreaks)
 159             cout << " Breaks:" << D.TargetPkg().FullName(false);
 160          else
 161             cout << " Depends:" << D.TargetPkg().FullName(false);
 162       }
 163       cout << endl;
 164
 165       _error->Error("Conf Broken %s",Pkg.FullName(false).c_str());
 166    }
 167    else
 168    {
 169       cout << "Conf ";
 170       Describe(Pkg,cout,false,true);
 171    }
 172
 173    if (Sim.BrokenCount() != 0)
 174       ShortBreaks();
 175    else
 176       cout << endl;
 177
 178    return true;
 179 }
 180                                                                         /*}}}*/
 181 // Simulate::Remove - Simulate the removal of a package                 /*{{{*/
 182 // ---------------------------------------------------------------------
 183 /* */
 184 bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)
 185 {
 186    // Adapt the iterator
 187    PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
 188
 189    Flags[Pkg->ID] = 3;
 190    Sim.MarkDelete(Pkg);
 191
 192    if (Purge == true)
 193       cout << "Purg ";
 194    else
 195       cout << "Remv ";
 196    Describe(Pkg,cout,true,false);
 197
 198    if (Sim.BrokenCount() != 0)
 199       ShortBreaks();
 200    else
 201       cout << endl;
 202
 203    return true;
 204 }
 205                                                                         /*}}}*/
 206 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
 207 // ---------------------------------------------------------------------
 208 /* */
 209 void pkgSimulate::ShortBreaks()
 210 {
 211    cout << " [";
 212    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
 213    {
 214       if (Sim[I].InstBroken() == true)
 215       {
 216          if (Flags[I->ID] == 0)
 217             cout << I.FullName(false) << ' ';
 218 /*       else
 219             cout << I.Name() << "! ";*/
 220       }
 221    }
 222    cout << ']' << endl;
 223 }
 224                                                                         /*}}}*/
 225 // ApplyStatus - Adjust for non-ok packages                             /*{{{*/
 226 // ---------------------------------------------------------------------
 227 /* We attempt to change the state of the all packages that have failed
 228    installation toward their real state. The ordering code will perform
 229    the necessary calculations to deal with the problems. */
 230 bool pkgApplyStatus(pkgDepCache &Cache)
 231 {
 232    pkgDepCache::ActionGroup group(Cache);
 233
 234    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 235    {
 236       if (I->VersionList == 0)
 237          continue;
 238
 239       // Only choice for a ReInstReq package is to reinstall
 240       if (I->InstState == pkgCache::State::ReInstReq ||
 241           I->InstState == pkgCache::State::HoldReInstReq)
 242       {
 243          if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true)
 244             Cache.MarkKeep(I, false, false);
 245          else
 246          {
 247             // Is this right? Will dpkg choke on an upgrade?
 248             if (Cache[I].CandidateVer != 0 &&
 249                  Cache[I].CandidateVerIter(Cache).Downloadable() == true)
 250                Cache.MarkInstall(I, false, 0, false);
 251             else
 252                return _error->Error(_("The package %s needs to be reinstalled, "
 253                                     "but I can't find an archive for it."),I.FullName(true).c_str());
 254          }
 255
 256          continue;
 257       }
 258
 259       switch (I->CurrentState)
 260       {
 261          /* This means installation failed somehow - it does not need to be
 262             re-unpacked (probably) */
 263          case pkgCache::State::UnPacked:
 264          case pkgCache::State::HalfConfigured:
 265          case pkgCache::State::TriggersAwaited:
 266          case pkgCache::State::TriggersPending:
 267          if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) ||
 268              I.State() != pkgCache::PkgIterator::NeedsUnpack)
 269             Cache.MarkKeep(I, false, false);
 270          else
 271          {
 272             if (Cache[I].CandidateVer != 0 &&
 273                  Cache[I].CandidateVerIter(Cache).Downloadable() == true)
 274                Cache.MarkInstall(I, true, 0, false);
 275             else
 276                Cache.MarkDelete(I);
 277          }
 278          break;
 279
 280          // This means removal failed
 281          case pkgCache::State::HalfInstalled:
 282          Cache.MarkDelete(I);
 283          break;
 284
 285          default:
 286          if (I->InstState != pkgCache::State::Ok)
 287             return _error->Error("The package %s is not ok and I "
 288                                  "don't know how to fix it!",I.FullName(false).c_str());
 289       }
 290    }
 291    return true;
 292 }
 293                                                                         /*}}}*/
 294 // FixBroken - Fix broken packages                                      /*{{{*/
 295 // ---------------------------------------------------------------------
 296 /* This autoinstalls every broken package and then runs the problem resolver
 297    on the result. */
 298 bool pkgFixBroken(pkgDepCache &Cache)
 299 {
 300    pkgDepCache::ActionGroup group(Cache);
 301
 302    // Auto upgrade all broken packages
 303    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 304       if (Cache[I].NowBroken() == true)
 305          Cache.MarkInstall(I, true, 0, false);
 306
 307    /* Fix packages that are in a NeedArchive state but don't have a
 308       downloadable install version */
 309    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 310    {
 311       if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
 312           Cache[I].Delete() == true)
 313          continue;
 314
 315       if (Cache[I].InstVerIter(Cache).Downloadable() == false)
 316          continue;
 317
 318       Cache.MarkInstall(I, true, 0, false);
 319    }
 320
 321    pkgProblemResolver Fix(&Cache);
 322    return Fix.Resolve(true);
 323 }
 324                                                                         /*}}}*/
 325 // DistUpgrade - Distribution upgrade                                   /*{{{*/
 326 // ---------------------------------------------------------------------
 327 /* This autoinstalls every package and then force installs every
 328    pre-existing package. This creates the initial set of conditions which
 329    most likely contain problems because too many things were installed.
 330
 331    The problem resolver is used to resolve the problems.
 332  */
 333 bool pkgDistUpgrade(pkgDepCache &Cache)
 334 {
 335    pkgDepCache::ActionGroup group(Cache);
 336
 337    /* Upgrade all installed packages first without autoinst to help the resolver
 338       in versioned or-groups to upgrade the old solver instead of installing
 339       a new one (if the old solver is not the first one [anymore]) */
 340    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 341       if (I->CurrentVer != 0)
 342          Cache.MarkInstall(I, false, 0, false);
 343
 344    /* Auto upgrade all installed packages, this provides the basis
 345       for the installation */
 346    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 347       if (I->CurrentVer != 0)
 348          Cache.MarkInstall(I, true, 0, false);
 349
 350    /* Now, auto upgrade all essential packages - this ensures that
 351       the essential packages are present and working */
 352    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 353       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 354          Cache.MarkInstall(I, true, 0, false);
 355
 356    /* We do it again over all previously installed packages to force
 357       conflict resolution on them all. */
 358    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 359       if (I->CurrentVer != 0)
 360          Cache.MarkInstall(I, false, 0, false);
 361
 362    pkgProblemResolver Fix(&Cache);
 363
 364    // Hold back held packages.
 365    if (_config->FindB("APT::Ignore-Hold",false) == false)
 366    {
 367       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 368       {
 369          if (I->SelectedState == pkgCache::State::Hold)
 370          {
 371             Fix.Protect(I);
 372             Cache.MarkKeep(I, false, false);
 373          }
 374       }
 375    }
 376
 377    return Fix.Resolve();
 378 }
 379                                                                         /*}}}*/
 380 // AllUpgrade - Upgrade as many packages as possible                    /*{{{*/
 381 // ---------------------------------------------------------------------
 382 /* Right now the system must be consistent before this can be called.
 383    It also will not change packages marked for install, it only tries
 384    to install packages not marked for install */
 385 bool pkgAllUpgrade(pkgDepCache &Cache)
 386 {
 387    pkgDepCache::ActionGroup group(Cache);
 388
 389    pkgProblemResolver Fix(&Cache);
 390
 391    if (Cache.BrokenCount() != 0)
 392       return false;
 393
 394    // Upgrade all installed packages
 395    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 396    {
 397       if (Cache[I].Install() == true)
 398          Fix.Protect(I);
 399
 400       if (_config->FindB("APT::Ignore-Hold",false) == false)
 401          if (I->SelectedState == pkgCache::State::Hold)
 402             continue;
 403
 404       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
 405          Cache.MarkInstall(I, false, 0, false);
 406    }
 407
 408    return Fix.ResolveByKeep();
 409 }
 410                                                                         /*}}}*/
 411 // MinimizeUpgrade - Minimizes the set of packages to be upgraded       /*{{{*/
 412 // ---------------------------------------------------------------------
 413 /* This simply goes over the entire set of packages and tries to keep
 414    each package marked for upgrade. If a conflict is generated then
 415    the package is restored. */
 416 bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 417 {
 418    pkgDepCache::ActionGroup group(Cache);
 419
 420    if (Cache.BrokenCount() != 0)
 421       return false;
 422
 423    // We loop for 10 tries to get the minimal set size.
 424    bool Change = false;
 425    unsigned int Count = 0;
 426    do
 427    {
 428       Change = false;
 429       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 430       {
 431          // Not interesting
 432          if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
 433             continue;
 434
 435          // Keep it and see if that is OK
 436          Cache.MarkKeep(I, false, false);
 437          if (Cache.BrokenCount() != 0)
 438             Cache.MarkInstall(I, false, 0, false);
 439          else
 440          {
 441             // If keep didnt actually do anything then there was no change..
 442             if (Cache[I].Upgrade() == false)
 443                Change = true;
 444          }
 445       }
 446       Count++;
 447    }
 448    while (Change == true && Count < 10);
 449
 450    if (Cache.BrokenCount() != 0)
 451       return _error->Error("Internal Error in pkgMinimizeUpgrade");
 452
 453    return true;
 454 }
 455                                                                         /*}}}*/
 456 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
 457 // ---------------------------------------------------------------------
 458 /* */
 459 pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : Cache(*pCache)
 460 {
 461    // Allocate memory
 462    unsigned long Size = Cache.Head().PackageCount;
 463    Scores = new signed short[Size];
 464    Flags = new unsigned char[Size];
 465    memset(Flags,0,sizeof(*Flags)*Size);
 466
 467    // Set debug to true to see its decision logic
 468    Debug = _config->FindB("Debug::pkgProblemResolver",false);
 469 }
 470                                                                         /*}}}*/
 471 // ProblemResolver::~pkgProblemResolver - Destructor                    /*{{{*/
 472 // ---------------------------------------------------------------------
 473 /* */
 474 pkgProblemResolver::~pkgProblemResolver()
 475 {
 476    delete [] Scores;
 477    delete [] Flags;
 478 }
 479                                                                         /*}}}*/
 480 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
 481 // ---------------------------------------------------------------------
 482 /* */
 483 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
 484 {
 485    Package const **A = (Package const **)a;
 486    Package const **B = (Package const **)b;
 487    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
 488       return -1;
 489    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
 490       return 1;
 491    return 0;
 492 }
 493                                                                         /*}}}*/
 494 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
 495 // ---------------------------------------------------------------------
 496 /* */
 497 void pkgProblemResolver::MakeScores()
 498 {
 499    unsigned long Size = Cache.Head().PackageCount;
 500    memset(Scores,0,sizeof(*Scores)*Size);
 501
 502    // Important Required Standard Optional Extra
 503    signed short PrioMap[] = {
 504       0,
 505       (signed short) _config->FindI("pkgProblemResolver::Scores::Important",3),
 506       (signed short) _config->FindI("pkgProblemResolver::Scores::Required",2),
 507       (signed short) _config->FindI("pkgProblemResolver::Scores::Standard",1),
 508       (signed short) _config->FindI("pkgProblemResolver::Scores::Optional",-1),
 509       (signed short) _config->FindI("pkgProblemResolver::Scores::Extra",-2)
 510    };
 511    signed short PrioEssentials = _config->FindI("pkgProblemResolver::Scores::Essentials",100);
 512    signed short PrioInstalledAndNotObsolete = _config->FindI("pkgProblemResolver::Scores::NotObsolete",1);
 513    signed short PrioDepends = _config->FindI("pkgProblemResolver::Scores::Depends",1);
 514    signed short PrioRecommends = _config->FindI("pkgProblemResolver::Scores::Recommends",1);
 515    signed short AddProtected = _config->FindI("pkgProblemResolver::Scores::AddProtected",10000);
 516    signed short AddEssential = _config->FindI("pkgProblemResolver::Scores::AddEssential",5000);
 517
 518    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 519       clog << "Settings used to calculate pkgProblemResolver::Scores::" << endl
 520          << "  Important => " << PrioMap[1] << endl
 521          << "  Required => " << PrioMap[2] << endl
 522          << "  Standard => " << PrioMap[3] << endl
 523          << "  Optional => " << PrioMap[4] << endl
 524          << "  Extra => " << PrioMap[5] << endl
 525          << "  Essentials => " << PrioEssentials << endl
 526          << "  InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete << endl
 527          << "  Depends => " << PrioDepends << endl
 528          << "  Recommends => " << PrioRecommends << endl
 529          << "  AddProtected => " << AddProtected << endl
 530          << "  AddEssential => " << AddEssential << endl;
 531
 532    // Generate the base scores for a package based on its properties
 533    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 534    {
 535       if (Cache[I].InstallVer == 0)
 536          continue;
 537
 538       signed short &Score = Scores[I->ID];
 539
 540       /* This is arbitrary, it should be high enough to elevate an
 541          essantial package above most other packages but low enough
 542          to allow an obsolete essential packages to be removed by
 543          a conflicts on a powerfull normal package (ie libc6) */
 544       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 545          Score += PrioEssentials;
 546
 547       // We transform the priority
 548       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 549          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 550
 551       /* This helps to fix oddball problems with conflicting packages
 552          on the same level. We enhance the score of installed packages
 553          if those are not obsolete
 554       */
 555       if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
 556          Score += PrioInstalledAndNotObsolete;
 557    }
 558
 559    // Now that we have the base scores we go and propogate dependencies
 560    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 561    {
 562       if (Cache[I].InstallVer == 0)
 563          continue;
 564
 565       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 566       {
 567          if (D->Type == pkgCache::Dep::Depends ||
 568              D->Type == pkgCache::Dep::PreDepends)
 569             Scores[D.TargetPkg()->ID] += PrioDepends;
 570          else if (D->Type == pkgCache::Dep::Recommends)
 571             Scores[D.TargetPkg()->ID] += PrioRecommends;
 572       }
 573    }
 574
 575    // Copy the scores to advoid additive looping
 576    SPtrArray<signed short> OldScores = new signed short[Size];
 577    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 578
 579    /* Now we cause 1 level of dependency inheritance, that is we add the
 580       score of the packages that depend on the target Package. This
 581       fortifies high scoring packages */
 582    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 583    {
 584       if (Cache[I].InstallVer == 0)
 585          continue;
 586
 587       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 588       {
 589          // Only do it for the install version
 590          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 591              (D->Type != pkgCache::Dep::Depends &&
 592               D->Type != pkgCache::Dep::PreDepends &&
 593               D->Type != pkgCache::Dep::Recommends))
 594             continue;
 595
 596          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 597       }
 598    }
 599
 600    /* Now we propogate along provides. This makes the packages that
 601       provide important packages extremely important */
 602    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 603    {
 604       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 605       {
 606          // Only do it once per package
 607          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 608             continue;
 609          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 610       }
 611    }
 612
 613    /* Protected things are pushed really high up. This number should put them
 614       ahead of everything */
 615    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 616    {
 617       if ((Flags[I->ID] & Protected) != 0)
 618          Scores[I->ID] += AddProtected;
 619       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 620          Scores[I->ID] += AddEssential;
 621    }
 622 }
 623                                                                         /*}}}*/
 624 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 625 // ---------------------------------------------------------------------
 626 /* This goes through and tries to reinstall packages to make this package
 627    installable */
 628 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 629 {
 630    pkgDepCache::ActionGroup group(Cache);
 631
 632    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 633       return false;
 634    if ((Flags[Pkg->ID] & Protected) == Protected)
 635       return false;
 636
 637    Flags[Pkg->ID] &= ~Upgradable;
 638
 639    bool WasKept = Cache[Pkg].Keep();
 640    Cache.MarkInstall(Pkg, false, 0, false);
 641
 642    // This must be a virtual package or something like that.
 643    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 644       return false;
 645
 646    // Isolate the problem dependency
 647    bool Fail = false;
 648    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 649    {
 650       // Compute a single dependency element (glob or)
 651       pkgCache::DepIterator Start = D;
 652       pkgCache::DepIterator End = D;
 653       unsigned char State = 0;
 654       for (bool LastOR = true; D.end() == false && LastOR == true;)
 655       {
 656          State |= Cache[D];
 657          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 658          D++;
 659          if (LastOR == true)
 660             End = D;
 661       }
 662
 663       // We only worry about critical deps.
 664       if (End.IsCritical() != true)
 665          continue;
 666
 667       // Iterate over all the members in the or group
 668       while (1)
 669       {
 670          // Dep is ok now
 671          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 672             break;
 673
 674          // Do not change protected packages
 675          PkgIterator P = Start.SmartTargetPkg();
 676          if ((Flags[P->ID] & Protected) == Protected)
 677          {
 678             if (Debug == true)
 679                clog << "    Reinst Failed because of protected " << P.FullName(false) << endl;
 680             Fail = true;
 681          }
 682          else
 683          {
 684             // Upgrade the package if the candidate version will fix the problem.
 685             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 686             {
 687                if (DoUpgrade(P) == false)
 688                {
 689                   if (Debug == true)
 690                      clog << "    Reinst Failed because of " << P.FullName(false) << endl;
 691                   Fail = true;
 692                }
 693                else
 694                {
 695                   Fail = false;
 696                   break;
 697                }
 698             }
 699             else
 700             {
 701                /* We let the algorithm deal with conflicts on its next iteration,
 702                 it is much smarter than us */
 703                if (Start->Type == pkgCache::Dep::Conflicts ||
 704                    Start->Type == pkgCache::Dep::DpkgBreaks ||
 705                    Start->Type == pkgCache::Dep::Obsoletes)
 706                    break;
 707
 708                if (Debug == true)
 709                   clog << "    Reinst Failed early because of " << Start.TargetPkg().FullName(false) << endl;
 710                Fail = true;
 711             }
 712          }
 713
 714          if (Start == End)
 715             break;
 716          Start++;
 717       }
 718       if (Fail == true)
 719          break;
 720    }
 721
 722    // Undo our operations - it might be smart to undo everything this did..
 723    if (Fail == true)
 724    {
 725       if (WasKept == true)
 726          Cache.MarkKeep(Pkg, false, false);
 727       else
 728          Cache.MarkDelete(Pkg);
 729       return false;
 730    }
 731
 732    if (Debug == true)
 733       clog << "  Re-Instated " << Pkg.FullName(false) << endl;
 734    return true;
 735 }
 736                                                                         /*}}}*/
 737 // ProblemResolver::Resolve - calls a resolver to fix the situation     /*{{{*/
 738 // ---------------------------------------------------------------------
 739 /* */
 740 bool pkgProblemResolver::Resolve(bool BrokenFix)
 741 {
 742    std::string const solver = _config->Find("APT::Solver::Name", "internal");
 743
 744    if (solver != "internal")
 745    {
 746 //       std::string const file = _config->FindDir("Dir::Bin::Solvers") + solver;
 747       std::string const file = solver;
 748       if (RealFileExists(file.c_str()) == false)
 749          return _error->Error("Can't call external solver '%s' as it is not available: %s", solver.c_str(), file.c_str());
 750       int external[4] = {-1, -1, -1, -1};
 751       if (pipe(external) != 0 || pipe(external + 2) != 0)
 752          return _error->Errno("Resolve", "Can't create needed IPC pipes for EDSP");
 753       for (int i = 0; i < 4; ++i)
 754          SetCloseExec(external[i], true);
 755
 756       pid_t Solver = ExecFork();
 757       if (Solver == 0)
 758       {
 759          dup2(external[0], STDIN_FILENO);
 760          dup2(external[3], STDOUT_FILENO);
 761          const char* calling[2] = { file.c_str(), 0 };
 762          execv(calling[0], (char**) calling);
 763          std::cerr << "Failed to execute solver '" << solver << "'!" << std::endl;
 764          _exit(100);
 765       }
 766       close(external[0]);
 767       close(external[3]);
 768
 769       if (WaitFd(external[1], true, 5) == false)
 770          return _error->Errno("Resolve", "Waiting on availability of solver stdin timed out");
 771
 772       FILE* output = fdopen(external[1], "w");
 773       if (output == NULL)
 774          return _error->Errno("Resolve", "fdopen on solver stdin failed");
 775       EDSP::WriteRequest(Cache, output);
 776       EDSP::WriteScenario(Cache, output);
 777       fclose(output);
 778
 779       if (EDSP::ReadResponse(external[2], Cache) == false)
 780          return _error->Error("Reading solver response failed");
 781
 782       return ExecWait(Solver, solver.c_str(), false);
 783    }
 784    return ResolveInternal(BrokenFix);
 785 }
 786                                                                         /*}}}*/
 787 // ProblemResolver::ResolveInternal - Run the resolution pass           /*{{{*/
 788 // ---------------------------------------------------------------------
 789 /* This routines works by calculating a score for each package. The score
 790    is derived by considering the package's priority and all reverse
 791    dependents giving an integer that reflects the amount of breakage that
 792    adjusting the package will inflict.
 793
 794    It goes from highest score to lowest and corrects all of the breaks by
 795    keeping or removing the dependant packages. If that fails then it removes
 796    the package itself and goes on. The routine should be able to intelligently
 797    go from any broken state to a fixed state.
 798
 799    The BrokenFix flag enables a mode where the algorithm tries to
 800    upgrade packages to advoid problems. */
 801 bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
 802 {
 803    pkgDepCache::ActionGroup group(Cache);
 804
 805    // Record which packages are marked for install
 806    bool Again = false;
 807    do
 808    {
 809       Again = false;
 810       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 811       {
 812          if (Cache[I].Install() == true)
 813             Flags[I->ID] |= PreInstalled;
 814          else
 815          {
 816             if (Cache[I].InstBroken() == true && BrokenFix == true)
 817             {
 818                Cache.MarkInstall(I, false, 0, false);
 819                if (Cache[I].Install() == true)
 820                   Again = true;
 821             }
 822
 823             Flags[I->ID] &= ~PreInstalled;
 824          }
 825          Flags[I->ID] |= Upgradable;
 826       }
 827    }
 828    while (Again == true);
 829
 830    if (Debug == true)
 831       clog << "Starting" << endl;
 832
 833    MakeScores();
 834
 835    unsigned long const Size = Cache.Head().PackageCount;
 836
 837    /* We have to order the packages so that the broken fixing pass
 838       operates from highest score to lowest. This prevents problems when
 839       high score packages cause the removal of lower score packages that
 840       would cause the removal of even lower score packages. */
 841    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 842    pkgCache::Package **PEnd = PList;
 843    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 844       *PEnd++ = I;
 845    This = this;
 846    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 847
 848    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 849    {
 850       clog << "Show Scores" << endl;
 851       for (pkgCache::Package **K = PList; K != PEnd; K++)
 852          if (Scores[(*K)->ID] != 0)
 853          {
 854            pkgCache::PkgIterator Pkg(Cache,*K);
 855            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
 856          }
 857    }
 858
 859    if (Debug == true)
 860       clog << "Starting 2" << endl;
 861
 862    /* Now consider all broken packages. For each broken package we either
 863       remove the package or fix it's problem. We do this once, it should
 864       not be possible for a loop to form (that is a < b < c and fixing b by
 865       changing a breaks c) */
 866    bool Change = true;
 867    bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
 868    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 869    {
 870       Change = false;
 871       for (pkgCache::Package **K = PList; K != PEnd; K++)
 872       {
 873          pkgCache::PkgIterator I(Cache,*K);
 874
 875          /* We attempt to install this and see if any breaks result,
 876             this takes care of some strange cases */
 877          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 878              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 879              (Flags[I->ID] & PreInstalled) != 0 &&
 880              (Flags[I->ID] & Protected) == 0 &&
 881              (Flags[I->ID] & ReInstateTried) == 0)
 882          {
 883             if (Debug == true)
 884                clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
 885             unsigned long OldBreaks = Cache.BrokenCount();
 886             pkgCache::Version *OldVer = Cache[I].InstallVer;
 887             Flags[I->ID] &= ReInstateTried;
 888
 889             Cache.MarkInstall(I, false, 0, false);
 890             if (Cache[I].InstBroken() == true ||
 891                 OldBreaks < Cache.BrokenCount())
 892             {
 893                if (OldVer == 0)
 894                   Cache.MarkDelete(I);
 895                else
 896                   Cache.MarkKeep(I, false, false);
 897             }
 898             else
 899                if (Debug == true)
 900                   clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 901          }
 902
 903          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 904             continue;
 905
 906          if (Debug == true)
 907             clog << "Investigating (" << Counter << ") " << I << endl;
 908
 909          // Isolate the problem dependency
 910          PackageKill KillList[100];
 911          PackageKill *LEnd = KillList;
 912          bool InOr = false;
 913          pkgCache::DepIterator Start;
 914          pkgCache::DepIterator End;
 915          PackageKill *OldEnd = LEnd;
 916
 917          enum {OrRemove,OrKeep} OrOp = OrRemove;
 918          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 919               D.end() == false || InOr == true;)
 920          {
 921             // Compute a single dependency element (glob or)
 922             if (Start == End)
 923             {
 924                // Decide what to do
 925                if (InOr == true && OldEnd == LEnd)
 926                {
 927                   if (OrOp == OrRemove)
 928                   {
 929                      if ((Flags[I->ID] & Protected) != Protected)
 930                      {
 931                         if (Debug == true)
 932                            clog << "  Or group remove for " << I.FullName(false) << endl;
 933                         Cache.MarkDelete(I);
 934                         Change = true;
 935                      }
 936                   }
 937                   else if (OrOp == OrKeep)
 938                   {
 939                      if (Debug == true)
 940                         clog << "  Or group keep for " << I.FullName(false) << endl;
 941                      Cache.MarkKeep(I, false, false);
 942                      Change = true;
 943                   }
 944                }
 945
 946                /* We do an extra loop (as above) to finalize the or group
 947                   processing */
 948                InOr = false;
 949                OrOp = OrRemove;
 950                D.GlobOr(Start,End);
 951                if (Start.end() == true)
 952                   break;
 953
 954                // We only worry about critical deps.
 955                if (End.IsCritical() != true)
 956                   continue;
 957
 958                InOr = Start != End;
 959                OldEnd = LEnd;
 960             }
 961             else
 962             {
 963                Start++;
 964                // We only worry about critical deps.
 965                if (Start.IsCritical() != true)
 966                   continue;
 967             }
 968
 969             // Dep is ok
 970             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 971             {
 972                InOr = false;
 973                continue;
 974             }
 975
 976             if (Debug == true)
 977                clog << "Broken " << Start << endl;
 978
 979             /* Look across the version list. If there are no possible
 980                targets then we keep the package and bail. This is necessary
 981                if a package has a dep on another package that cant be found */
 982             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 983             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 984                 Start->Type != pkgCache::Dep::Conflicts &&
 985                 Start->Type != pkgCache::Dep::DpkgBreaks &&
 986                 Start->Type != pkgCache::Dep::Obsoletes &&
 987                 Cache[I].NowBroken() == false)
 988             {
 989                if (InOr == true)
 990                {
 991                   /* No keep choice because the keep being OK could be the
 992                      result of another element in the OR group! */
 993                   continue;
 994                }
 995
 996                Change = true;
 997                Cache.MarkKeep(I, false, false);
 998                break;
 999             }
1000
1001             bool Done = false;
1002             for (pkgCache::Version **V = VList; *V != 0; V++)
1003             {
1004                pkgCache::VerIterator Ver(Cache,*V);
1005                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1006
1007                /* This is a conflicts, and the version we are looking
1008                   at is not the currently selected version of the
1009                   package, which means it is not necessary to
1010                   remove/keep */
1011                if (Cache[Pkg].InstallVer != Ver &&
1012                    (Start->Type == pkgCache::Dep::Conflicts ||
1013                     Start->Type == pkgCache::Dep::DpkgBreaks ||
1014                     Start->Type == pkgCache::Dep::Obsoletes))
1015                {
1016                   if (Debug)
1017                      clog << "  Conflicts//Breaks against version "
1018                           << Ver.VerStr() << " for " << Pkg.Name()
1019                           << " but that is not InstVer, ignoring"
1020                           << endl;
1021                   continue;
1022                }
1023
1024                if (Debug == true)
1025                   clog << "  Considering " << Pkg.FullName(false) << ' ' << (int)Scores[Pkg->ID] <<
1026                   " as a solution to " << I.FullName(false) << ' ' << (int)Scores[I->ID] << endl;
1027
1028                /* Try to fix the package under consideration rather than
1029                   fiddle with the VList package */
1030                if (Scores[I->ID] <= Scores[Pkg->ID] ||
1031                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
1032                     End->Type != pkgCache::Dep::Conflicts &&
1033                     End->Type != pkgCache::Dep::DpkgBreaks &&
1034                     End->Type != pkgCache::Dep::Obsoletes))
1035                {
1036                   // Try a little harder to fix protected packages..
1037                   if ((Flags[I->ID] & Protected) == Protected)
1038                   {
1039                      if (DoUpgrade(Pkg) == true)
1040                      {
1041                         if (Scores[Pkg->ID] > Scores[I->ID])
1042                            Scores[Pkg->ID] = Scores[I->ID];
1043                         break;
1044                      }
1045
1046                      continue;
1047                   }
1048
1049                   /* See if a keep will do, unless the package is protected,
1050                      then installing it will be necessary */
1051                   bool Installed = Cache[I].Install();
1052                   Cache.MarkKeep(I, false, false);
1053                   if (Cache[I].InstBroken() == false)
1054                   {
1055                      // Unwind operation will be keep now
1056                      if (OrOp == OrRemove)
1057                         OrOp = OrKeep;
1058
1059                      // Restore
1060                      if (InOr == true && Installed == true)
1061                         Cache.MarkInstall(I, false, 0, false);
1062
1063                      if (Debug == true)
1064                         clog << "  Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1065                   }
1066                   else
1067                   {
1068                      if (BrokenFix == false || DoUpgrade(I) == false)
1069                      {
1070                         // Consider other options
1071                         if (InOr == false)
1072                         {
1073                            if (Debug == true)
1074                               clog << "  Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1075                            Cache.MarkDelete(I);
1076                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
1077                               Scores[I->ID] = Scores[Pkg->ID];
1078                         }
1079                         else if (TryFixByInstall == true &&
1080                                  Start.TargetPkg()->CurrentVer == 0 &&
1081                                  Cache[Start.TargetPkg()].Delete() == false &&
1082                                  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
1083                                  Cache.GetCandidateVer(Start.TargetPkg()).end() == false)
1084                         {
1085                            /* Before removing or keeping the package with the broken dependency
1086                               try instead to install the first not previously installed package
1087                               solving this dependency. This helps every time a previous solver
1088                               is removed by the resolver because of a conflict or alike but it is
1089                               dangerous as it could trigger new breaks/conflicts… */
1090                            if (Debug == true)
1091                               clog << "  Try Installing " << Start.TargetPkg() << " before changing " << I.FullName(false) << std::endl;
1092                            unsigned long const OldBroken = Cache.BrokenCount();
1093                            Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
1094                            // FIXME: we should undo the complete MarkInstall process here
1095                            if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
1096                               Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
1097                         }
1098                      }
1099                   }
1100
1101                   Change = true;
1102                   Done = true;
1103                   break;
1104                }
1105                else
1106                {
1107                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
1108                   {
1109                      // first, try upgradring the package, if that
1110                      // does not help, the breaks goes onto the
1111                      // kill list
1112                      //
1113                      // FIXME: use DoUpgrade(Pkg) instead?
1114                      if (Cache[End] & pkgDepCache::DepGCVer)
1115                      {
1116                         if (Debug)
1117                            clog << "  Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
1118                         Cache.MarkInstall(Pkg, false, 0, false);
1119                         continue;
1120                      }
1121                   }
1122
1123                   // Skip adding to the kill list if it is protected
1124                   if ((Flags[Pkg->ID] & Protected) != 0)
1125                      continue;
1126
1127                   if (Debug == true)
1128                      clog << "  Added " << Pkg.FullName(false) << " to the remove list" << endl;
1129
1130                   LEnd->Pkg = Pkg;
1131                   LEnd->Dep = End;
1132                   LEnd++;
1133
1134                   if (Start->Type != pkgCache::Dep::Conflicts &&
1135                       Start->Type != pkgCache::Dep::Obsoletes)
1136                      break;
1137                }
1138             }
1139
1140             // Hm, nothing can possibly satisify this dep. Nuke it.
1141             if (VList[0] == 0 &&
1142                 Start->Type != pkgCache::Dep::Conflicts &&
1143                 Start->Type != pkgCache::Dep::DpkgBreaks &&
1144                 Start->Type != pkgCache::Dep::Obsoletes &&
1145                 (Flags[I->ID] & Protected) != Protected)
1146             {
1147                bool Installed = Cache[I].Install();
1148                Cache.MarkKeep(I);
1149                if (Cache[I].InstBroken() == false)
1150                {
1151                   // Unwind operation will be keep now
1152                   if (OrOp == OrRemove)
1153                      OrOp = OrKeep;
1154
1155                   // Restore
1156                   if (InOr == true && Installed == true)
1157                      Cache.MarkInstall(I, false, 0, false);
1158
1159                   if (Debug == true)
1160                      clog << "  Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1161                }
1162                else
1163                {
1164                   if (Debug == true)
1165                      clog << "  Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1166                   if (InOr == false)
1167                      Cache.MarkDelete(I);
1168                }
1169
1170                Change = true;
1171                Done = true;
1172             }
1173
1174             // Try some more
1175             if (InOr == true)
1176                continue;
1177
1178             if (Done == true)
1179                break;
1180          }
1181
1182          // Apply the kill list now
1183          if (Cache[I].InstallVer != 0)
1184          {
1185             for (PackageKill *J = KillList; J != LEnd; J++)
1186             {
1187                Change = true;
1188                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1189                {
1190                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1191                       J->Dep->Type == pkgCache::Dep::DpkgBreaks ||
1192                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1193                   {
1194                      if (Debug == true)
1195                         clog << "  Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
1196                      Cache.MarkDelete(J->Pkg);
1197                   }
1198                }
1199                else
1200                {
1201                   if (Debug == true)
1202                      clog << "  Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
1203                   Cache.MarkKeep(J->Pkg, false, false);
1204                }
1205
1206                if (Counter > 1)
1207                {
1208                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1209                      Scores[J->Pkg->ID] = Scores[I->ID];
1210                }
1211             }
1212          }
1213       }
1214    }
1215
1216    if (Debug == true)
1217       clog << "Done" << endl;
1218
1219    if (Cache.BrokenCount() != 0)
1220    {
1221       // See if this is the result of a hold
1222       pkgCache::PkgIterator I = Cache.PkgBegin();
1223       for (;I.end() != true; I++)
1224       {
1225          if (Cache[I].InstBroken() == false)
1226             continue;
1227          if ((Flags[I->ID] & Protected) != Protected)
1228             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1229       }
1230       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1231    }
1232
1233    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1234    pkgCache::PkgIterator I = Cache.PkgBegin();
1235    for (;I.end() != true; I++) {
1236       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1237          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1238             std::clog << "Resolve installed new pkg: " << I.FullName(false)
1239                       << " (now marking it as auto)" << std::endl;
1240          }
1241          Cache[I].Flags |= pkgCache::Flag::Auto;
1242       }
1243    }
1244
1245
1246    return true;
1247 }
1248                                                                         /*}}}*/
1249 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1250 // ---------------------------------------------------------------------
1251 /* This is the work horse of the soft upgrade routine. It is very gental
1252    in that it does not install or remove any packages. It is assumed that the
1253    system was non-broken previously. */
1254 bool pkgProblemResolver::ResolveByKeep()
1255 {
1256    pkgDepCache::ActionGroup group(Cache);
1257
1258    unsigned long Size = Cache.Head().PackageCount;
1259
1260    MakeScores();
1261
1262    /* We have to order the packages so that the broken fixing pass
1263       operates from highest score to lowest. This prevents problems when
1264       high score packages cause the removal of lower score packages that
1265       would cause the removal of even lower score packages. */
1266    pkgCache::Package **PList = new pkgCache::Package *[Size];
1267    pkgCache::Package **PEnd = PList;
1268    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1269       *PEnd++ = I;
1270    This = this;
1271    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1272
1273    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1274    {
1275       clog << "Show Scores" << endl;
1276       for (pkgCache::Package **K = PList; K != PEnd; K++)
1277          if (Scores[(*K)->ID] != 0)
1278          {
1279            pkgCache::PkgIterator Pkg(Cache,*K);
1280            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1281          }
1282    }
1283
1284    if (Debug == true)
1285       clog << "Entering ResolveByKeep" << endl;
1286
1287    // Consider each broken package
1288    pkgCache::Package **LastStop = 0;
1289    for (pkgCache::Package **K = PList; K != PEnd; K++)
1290    {
1291       pkgCache::PkgIterator I(Cache,*K);
1292
1293       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1294          continue;
1295
1296       /* Keep the package. If this works then great, otherwise we have
1297          to be significantly more agressive and manipulate its dependencies */
1298       if ((Flags[I->ID] & Protected) == 0)
1299       {
1300          if (Debug == true)
1301             clog << "Keeping package " << I.FullName(false) << endl;
1302          Cache.MarkKeep(I, false, false);
1303          if (Cache[I].InstBroken() == false)
1304          {
1305             K = PList - 1;
1306             continue;
1307          }
1308       }
1309
1310       // Isolate the problem dependencies
1311       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1312       {
1313          DepIterator Start;
1314          DepIterator End;
1315          D.GlobOr(Start,End);
1316
1317          // We only worry about critical deps.
1318          if (End.IsCritical() != true)
1319             continue;
1320
1321          // Dep is ok
1322          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1323             continue;
1324
1325          /* Hm, the group is broken.. I suppose the best thing to do is to
1326             is to try every combination of keep/not-keep for the set, but thats
1327             slow, and this never happens, just be conservative and assume the
1328             list of ors is in preference and keep till it starts to work. */
1329          while (true)
1330          {
1331             if (Debug == true)
1332                clog << "Package " << I.FullName(false) << " " << Start << endl;
1333
1334             // Look at all the possible provides on this package
1335             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1336             for (pkgCache::Version **V = VList; *V != 0; V++)
1337             {
1338                pkgCache::VerIterator Ver(Cache,*V);
1339                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1340
1341                // It is not keepable
1342                if (Cache[Pkg].InstallVer == 0 ||
1343                    Pkg->CurrentVer == 0)
1344                   continue;
1345
1346                if ((Flags[I->ID] & Protected) == 0)
1347                {
1348                   if (Debug == true)
1349                      clog << "  Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1350                   Cache.MarkKeep(Pkg, false, false);
1351                }
1352
1353                if (Cache[I].InstBroken() == false)
1354                   break;
1355             }
1356
1357             if (Cache[I].InstBroken() == false)
1358                break;
1359
1360             if (Start == End)
1361                break;
1362             Start++;
1363          }
1364
1365          if (Cache[I].InstBroken() == false)
1366             break;
1367       }
1368
1369       if (Cache[I].InstBroken() == true)
1370          continue;
1371
1372       // Restart again.
1373       if (K == LastStop)
1374          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.FullName(false).c_str());
1375       LastStop = K;
1376       K = PList - 1;
1377    }
1378
1379    return true;
1380 }
1381                                                                         /*}}}*/
1382 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1383 // ---------------------------------------------------------------------
1384 /* This is used to make sure protected packages are installed */
1385 void pkgProblemResolver::InstallProtect()
1386 {
1387    pkgDepCache::ActionGroup group(Cache);
1388
1389    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1390    {
1391       if ((Flags[I->ID] & Protected) == Protected)
1392       {
1393          if ((Flags[I->ID] & ToRemove) == ToRemove)
1394             Cache.MarkDelete(I);
1395          else
1396          {
1397             // preserve the information whether the package was auto
1398             // or manually installed
1399             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1400             Cache.MarkInstall(I, false, 0, !autoInst);
1401          }
1402       }
1403    }
1404 }
1405                                                                         /*}}}*/
1406 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1407 // ---------------------------------------------------------------------
1408 /* This is ment to be used in conjunction with AllTargets to get a list
1409    of versions ordered by preference. */
1410 static pkgCache *PrioCache;
1411 static int PrioComp(const void *A,const void *B)
1412 {
1413    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1414    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1415
1416    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1417        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1418      return 1;
1419    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1420        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1421      return -1;
1422
1423    if (L->Priority != R->Priority)
1424       return R->Priority - L->Priority;
1425    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1426 }
1427 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1428 {
1429    unsigned long Count = 0;
1430    PrioCache = &Cache;
1431    for (pkgCache::Version **I = List; *I != 0; I++)
1432       Count++;
1433    qsort(List,Count,sizeof(*List),PrioComp);
1434 }
1435                                                                         /*}}}*/
1436 // CacheFile::ListUpdate - update the cache files                       /*{{{*/
1437 // ---------------------------------------------------------------------
1438 /* This is a simple wrapper to update the cache. it will fetch stuff
1439  * from the network (or any other sources defined in sources.list)
1440  */
1441 bool ListUpdate(pkgAcquireStatus &Stat,
1442                 pkgSourceList &List,
1443                 int PulseInterval)
1444 {
1445    pkgAcquire::RunResult res;
1446    pkgAcquire Fetcher;
1447    if (Fetcher.Setup(&Stat, _config->FindDir("Dir::State::Lists")) == false)
1448       return false;
1449
1450    // Populate it with the source selection
1451    if (List.GetIndexes(&Fetcher) == false)
1452          return false;
1453
1454    // Run scripts
1455    RunScripts("APT::Update::Pre-Invoke");
1456
1457    // check arguments
1458    if(PulseInterval>0)
1459       res = Fetcher.Run(PulseInterval);
1460    else
1461       res = Fetcher.Run();
1462
1463    if (res == pkgAcquire::Failed)
1464       return false;
1465
1466    bool Failed = false;
1467    bool TransientNetworkFailure = false;
1468    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin();
1469         I != Fetcher.ItemsEnd(); I++)
1470    {
1471       if ((*I)->Status == pkgAcquire::Item::StatDone)
1472          continue;
1473
1474       (*I)->Finished();
1475
1476       ::URI uri((*I)->DescURI());
1477       uri.User.clear();
1478       uri.Password.clear();
1479       string descUri = string(uri);
1480       _error->Warning(_("Failed to fetch %s  %s\n"), descUri.c_str(),
1481               (*I)->ErrorText.c_str());
1482
1483       if ((*I)->Status == pkgAcquire::Item::StatTransientNetworkError)
1484       {
1485          TransientNetworkFailure = true;
1486          continue;
1487       }
1488
1489       Failed = true;
1490    }
1491
1492    // Clean out any old list files
1493    // Keep "APT::Get::List-Cleanup" name for compatibility, but
1494    // this is really a global option for the APT library now
1495    if (!TransientNetworkFailure && !Failed &&
1496        (_config->FindB("APT::Get::List-Cleanup",true) == true &&
1497         _config->FindB("APT::List-Cleanup",true) == true))
1498    {
1499       if (Fetcher.Clean(_config->FindDir("Dir::State::lists")) == false ||
1500           Fetcher.Clean(_config->FindDir("Dir::State::lists") + "partial/") == false)
1501          // something went wrong with the clean
1502          return false;
1503    }
1504
1505    if (TransientNetworkFailure == true)
1506       _error->Warning(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1507    else if (Failed == true)
1508       return _error->Error(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1509
1510
1511    // Run the success scripts if all was fine
1512    if(!TransientNetworkFailure && !Failed)
1513       RunScripts("APT::Update::Post-Invoke-Success");
1514
1515    // Run the other scripts
1516    RunScripts("APT::Update::Post-Invoke");
1517    return true;
1518 }
1519                                                                         /*}}}*/