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::vector<std::string> const solverDirs = _config->FindVector("Dir::Bin::Solvers");
 747       std::string file;
 748       for (std::vector<std::string>::const_iterator dir = solverDirs.begin();
 749            dir != solverDirs.end(); ++dir) {
 750          file = flCombine(*dir, solver);
 751          if (RealFileExists(file.c_str()) == true)
 752             break;
 753          file.clear();
 754       }
 755
 756       if (file.empty() == true)
 757          return _error->Error("Can't call external solver '%s' as it is not in a configured directory!", solver.c_str());
 758       int external[4] = {-1, -1, -1, -1};
 759       if (pipe(external) != 0 || pipe(external + 2) != 0)
 760          return _error->Errno("Resolve", "Can't create needed IPC pipes for EDSP");
 761       for (int i = 0; i < 4; ++i)
 762          SetCloseExec(external[i], true);
 763
 764       pid_t Solver = ExecFork();
 765       if (Solver == 0)
 766       {
 767          dup2(external[0], STDIN_FILENO);
 768          dup2(external[3], STDOUT_FILENO);
 769          const char* calling[2] = { file.c_str(), 0 };
 770          execv(calling[0], (char**) calling);
 771          std::cerr << "Failed to execute solver '" << solver << "'!" << std::endl;
 772          _exit(100);
 773       }
 774       close(external[0]);
 775       close(external[3]);
 776
 777       if (WaitFd(external[1], true, 5) == false)
 778          return _error->Errno("Resolve", "Waiting on availability of solver stdin timed out");
 779
 780       FILE* output = fdopen(external[1], "w");
 781       if (output == NULL)
 782          return _error->Errno("Resolve", "fdopen on solver stdin failed");
 783       EDSP::WriteRequest(Cache, output);
 784       EDSP::WriteScenario(Cache, output);
 785       fclose(output);
 786
 787       if (EDSP::ReadResponse(external[2], Cache) == false)
 788          return _error->Error("Reading solver response failed");
 789
 790       return ExecWait(Solver, solver.c_str(), false);
 791    }
 792    return ResolveInternal(BrokenFix);
 793 }
 794                                                                         /*}}}*/
 795 // ProblemResolver::ResolveInternal - Run the resolution pass           /*{{{*/
 796 // ---------------------------------------------------------------------
 797 /* This routines works by calculating a score for each package. The score
 798    is derived by considering the package's priority and all reverse
 799    dependents giving an integer that reflects the amount of breakage that
 800    adjusting the package will inflict.
 801
 802    It goes from highest score to lowest and corrects all of the breaks by
 803    keeping or removing the dependant packages. If that fails then it removes
 804    the package itself and goes on. The routine should be able to intelligently
 805    go from any broken state to a fixed state.
 806
 807    The BrokenFix flag enables a mode where the algorithm tries to
 808    upgrade packages to advoid problems. */
 809 bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
 810 {
 811    pkgDepCache::ActionGroup group(Cache);
 812
 813    // Record which packages are marked for install
 814    bool Again = false;
 815    do
 816    {
 817       Again = false;
 818       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 819       {
 820          if (Cache[I].Install() == true)
 821             Flags[I->ID] |= PreInstalled;
 822          else
 823          {
 824             if (Cache[I].InstBroken() == true && BrokenFix == true)
 825             {
 826                Cache.MarkInstall(I, false, 0, false);
 827                if (Cache[I].Install() == true)
 828                   Again = true;
 829             }
 830
 831             Flags[I->ID] &= ~PreInstalled;
 832          }
 833          Flags[I->ID] |= Upgradable;
 834       }
 835    }
 836    while (Again == true);
 837
 838    if (Debug == true)
 839       clog << "Starting" << endl;
 840
 841    MakeScores();
 842
 843    unsigned long const Size = Cache.Head().PackageCount;
 844
 845    /* We have to order the packages so that the broken fixing pass
 846       operates from highest score to lowest. This prevents problems when
 847       high score packages cause the removal of lower score packages that
 848       would cause the removal of even lower score packages. */
 849    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 850    pkgCache::Package **PEnd = PList;
 851    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 852       *PEnd++ = I;
 853    This = this;
 854    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 855
 856    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 857    {
 858       clog << "Show Scores" << endl;
 859       for (pkgCache::Package **K = PList; K != PEnd; K++)
 860          if (Scores[(*K)->ID] != 0)
 861          {
 862            pkgCache::PkgIterator Pkg(Cache,*K);
 863            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
 864          }
 865    }
 866
 867    if (Debug == true)
 868       clog << "Starting 2" << endl;
 869
 870    /* Now consider all broken packages. For each broken package we either
 871       remove the package or fix it's problem. We do this once, it should
 872       not be possible for a loop to form (that is a < b < c and fixing b by
 873       changing a breaks c) */
 874    bool Change = true;
 875    bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
 876    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 877    {
 878       Change = false;
 879       for (pkgCache::Package **K = PList; K != PEnd; K++)
 880       {
 881          pkgCache::PkgIterator I(Cache,*K);
 882
 883          /* We attempt to install this and see if any breaks result,
 884             this takes care of some strange cases */
 885          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 886              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 887              (Flags[I->ID] & PreInstalled) != 0 &&
 888              (Flags[I->ID] & Protected) == 0 &&
 889              (Flags[I->ID] & ReInstateTried) == 0)
 890          {
 891             if (Debug == true)
 892                clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
 893             unsigned long OldBreaks = Cache.BrokenCount();
 894             pkgCache::Version *OldVer = Cache[I].InstallVer;
 895             Flags[I->ID] &= ReInstateTried;
 896
 897             Cache.MarkInstall(I, false, 0, false);
 898             if (Cache[I].InstBroken() == true ||
 899                 OldBreaks < Cache.BrokenCount())
 900             {
 901                if (OldVer == 0)
 902                   Cache.MarkDelete(I);
 903                else
 904                   Cache.MarkKeep(I, false, false);
 905             }
 906             else
 907                if (Debug == true)
 908                   clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 909          }
 910
 911          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 912             continue;
 913
 914          if (Debug == true)
 915             clog << "Investigating (" << Counter << ") " << I << endl;
 916
 917          // Isolate the problem dependency
 918          PackageKill KillList[100];
 919          PackageKill *LEnd = KillList;
 920          bool InOr = false;
 921          pkgCache::DepIterator Start;
 922          pkgCache::DepIterator End;
 923          PackageKill *OldEnd = LEnd;
 924
 925          enum {OrRemove,OrKeep} OrOp = OrRemove;
 926          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 927               D.end() == false || InOr == true;)
 928          {
 929             // Compute a single dependency element (glob or)
 930             if (Start == End)
 931             {
 932                // Decide what to do
 933                if (InOr == true && OldEnd == LEnd)
 934                {
 935                   if (OrOp == OrRemove)
 936                   {
 937                      if ((Flags[I->ID] & Protected) != Protected)
 938                      {
 939                         if (Debug == true)
 940                            clog << "  Or group remove for " << I.FullName(false) << endl;
 941                         Cache.MarkDelete(I);
 942                         Change = true;
 943                      }
 944                   }
 945                   else if (OrOp == OrKeep)
 946                   {
 947                      if (Debug == true)
 948                         clog << "  Or group keep for " << I.FullName(false) << endl;
 949                      Cache.MarkKeep(I, false, false);
 950                      Change = true;
 951                   }
 952                }
 953
 954                /* We do an extra loop (as above) to finalize the or group
 955                   processing */
 956                InOr = false;
 957                OrOp = OrRemove;
 958                D.GlobOr(Start,End);
 959                if (Start.end() == true)
 960                   break;
 961
 962                // We only worry about critical deps.
 963                if (End.IsCritical() != true)
 964                   continue;
 965
 966                InOr = Start != End;
 967                OldEnd = LEnd;
 968             }
 969             else
 970             {
 971                Start++;
 972                // We only worry about critical deps.
 973                if (Start.IsCritical() != true)
 974                   continue;
 975             }
 976
 977             // Dep is ok
 978             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 979             {
 980                InOr = false;
 981                continue;
 982             }
 983
 984             if (Debug == true)
 985                clog << "Broken " << Start << endl;
 986
 987             /* Look across the version list. If there are no possible
 988                targets then we keep the package and bail. This is necessary
 989                if a package has a dep on another package that cant be found */
 990             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 991             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 992                 Start->Type != pkgCache::Dep::Conflicts &&
 993                 Start->Type != pkgCache::Dep::DpkgBreaks &&
 994                 Start->Type != pkgCache::Dep::Obsoletes &&
 995                 Cache[I].NowBroken() == false)
 996             {
 997                if (InOr == true)
 998                {
 999                   /* No keep choice because the keep being OK could be the
1000                      result of another element in the OR group! */
1001                   continue;
1002                }
1003
1004                Change = true;
1005                Cache.MarkKeep(I, false, false);
1006                break;
1007             }
1008
1009             bool Done = false;
1010             for (pkgCache::Version **V = VList; *V != 0; V++)
1011             {
1012                pkgCache::VerIterator Ver(Cache,*V);
1013                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1014
1015                /* This is a conflicts, and the version we are looking
1016                   at is not the currently selected version of the
1017                   package, which means it is not necessary to
1018                   remove/keep */
1019                if (Cache[Pkg].InstallVer != Ver &&
1020                    (Start->Type == pkgCache::Dep::Conflicts ||
1021                     Start->Type == pkgCache::Dep::DpkgBreaks ||
1022                     Start->Type == pkgCache::Dep::Obsoletes))
1023                {
1024                   if (Debug)
1025                      clog << "  Conflicts//Breaks against version "
1026                           << Ver.VerStr() << " for " << Pkg.Name()
1027                           << " but that is not InstVer, ignoring"
1028                           << endl;
1029                   continue;
1030                }
1031
1032                if (Debug == true)
1033                   clog << "  Considering " << Pkg.FullName(false) << ' ' << (int)Scores[Pkg->ID] <<
1034                   " as a solution to " << I.FullName(false) << ' ' << (int)Scores[I->ID] << endl;
1035
1036                /* Try to fix the package under consideration rather than
1037                   fiddle with the VList package */
1038                if (Scores[I->ID] <= Scores[Pkg->ID] ||
1039                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
1040                     End->Type != pkgCache::Dep::Conflicts &&
1041                     End->Type != pkgCache::Dep::DpkgBreaks &&
1042                     End->Type != pkgCache::Dep::Obsoletes))
1043                {
1044                   // Try a little harder to fix protected packages..
1045                   if ((Flags[I->ID] & Protected) == Protected)
1046                   {
1047                      if (DoUpgrade(Pkg) == true)
1048                      {
1049                         if (Scores[Pkg->ID] > Scores[I->ID])
1050                            Scores[Pkg->ID] = Scores[I->ID];
1051                         break;
1052                      }
1053
1054                      continue;
1055                   }
1056
1057                   /* See if a keep will do, unless the package is protected,
1058                      then installing it will be necessary */
1059                   bool Installed = Cache[I].Install();
1060                   Cache.MarkKeep(I, false, false);
1061                   if (Cache[I].InstBroken() == false)
1062                   {
1063                      // Unwind operation will be keep now
1064                      if (OrOp == OrRemove)
1065                         OrOp = OrKeep;
1066
1067                      // Restore
1068                      if (InOr == true && Installed == true)
1069                         Cache.MarkInstall(I, false, 0, false);
1070
1071                      if (Debug == true)
1072                         clog << "  Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1073                   }
1074                   else
1075                   {
1076                      if (BrokenFix == false || DoUpgrade(I) == false)
1077                      {
1078                         // Consider other options
1079                         if (InOr == false)
1080                         {
1081                            if (Debug == true)
1082                               clog << "  Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1083                            Cache.MarkDelete(I);
1084                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
1085                               Scores[I->ID] = Scores[Pkg->ID];
1086                         }
1087                         else if (TryFixByInstall == true &&
1088                                  Start.TargetPkg()->CurrentVer == 0 &&
1089                                  Cache[Start.TargetPkg()].Delete() == false &&
1090                                  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
1091                                  Cache.GetCandidateVer(Start.TargetPkg()).end() == false)
1092                         {
1093                            /* Before removing or keeping the package with the broken dependency
1094                               try instead to install the first not previously installed package
1095                               solving this dependency. This helps every time a previous solver
1096                               is removed by the resolver because of a conflict or alike but it is
1097                               dangerous as it could trigger new breaks/conflicts… */
1098                            if (Debug == true)
1099                               clog << "  Try Installing " << Start.TargetPkg() << " before changing " << I.FullName(false) << std::endl;
1100                            unsigned long const OldBroken = Cache.BrokenCount();
1101                            Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
1102                            // FIXME: we should undo the complete MarkInstall process here
1103                            if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
1104                               Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
1105                         }
1106                      }
1107                   }
1108
1109                   Change = true;
1110                   Done = true;
1111                   break;
1112                }
1113                else
1114                {
1115                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
1116                   {
1117                      // first, try upgradring the package, if that
1118                      // does not help, the breaks goes onto the
1119                      // kill list
1120                      //
1121                      // FIXME: use DoUpgrade(Pkg) instead?
1122                      if (Cache[End] & pkgDepCache::DepGCVer)
1123                      {
1124                         if (Debug)
1125                            clog << "  Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
1126                         Cache.MarkInstall(Pkg, false, 0, false);
1127                         continue;
1128                      }
1129                   }
1130
1131                   // Skip adding to the kill list if it is protected
1132                   if ((Flags[Pkg->ID] & Protected) != 0)
1133                      continue;
1134
1135                   if (Debug == true)
1136                      clog << "  Added " << Pkg.FullName(false) << " to the remove list" << endl;
1137
1138                   LEnd->Pkg = Pkg;
1139                   LEnd->Dep = End;
1140                   LEnd++;
1141
1142                   if (Start->Type != pkgCache::Dep::Conflicts &&
1143                       Start->Type != pkgCache::Dep::Obsoletes)
1144                      break;
1145                }
1146             }
1147
1148             // Hm, nothing can possibly satisify this dep. Nuke it.
1149             if (VList[0] == 0 &&
1150                 Start->Type != pkgCache::Dep::Conflicts &&
1151                 Start->Type != pkgCache::Dep::DpkgBreaks &&
1152                 Start->Type != pkgCache::Dep::Obsoletes &&
1153                 (Flags[I->ID] & Protected) != Protected)
1154             {
1155                bool Installed = Cache[I].Install();
1156                Cache.MarkKeep(I);
1157                if (Cache[I].InstBroken() == false)
1158                {
1159                   // Unwind operation will be keep now
1160                   if (OrOp == OrRemove)
1161                      OrOp = OrKeep;
1162
1163                   // Restore
1164                   if (InOr == true && Installed == true)
1165                      Cache.MarkInstall(I, false, 0, false);
1166
1167                   if (Debug == true)
1168                      clog << "  Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1169                }
1170                else
1171                {
1172                   if (Debug == true)
1173                      clog << "  Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1174                   if (InOr == false)
1175                      Cache.MarkDelete(I);
1176                }
1177
1178                Change = true;
1179                Done = true;
1180             }
1181
1182             // Try some more
1183             if (InOr == true)
1184                continue;
1185
1186             if (Done == true)
1187                break;
1188          }
1189
1190          // Apply the kill list now
1191          if (Cache[I].InstallVer != 0)
1192          {
1193             for (PackageKill *J = KillList; J != LEnd; J++)
1194             {
1195                Change = true;
1196                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1197                {
1198                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1199                       J->Dep->Type == pkgCache::Dep::DpkgBreaks ||
1200                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1201                   {
1202                      if (Debug == true)
1203                         clog << "  Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
1204                      Cache.MarkDelete(J->Pkg);
1205                   }
1206                }
1207                else
1208                {
1209                   if (Debug == true)
1210                      clog << "  Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
1211                   Cache.MarkKeep(J->Pkg, false, false);
1212                }
1213
1214                if (Counter > 1)
1215                {
1216                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1217                      Scores[J->Pkg->ID] = Scores[I->ID];
1218                }
1219             }
1220          }
1221       }
1222    }
1223
1224    if (Debug == true)
1225       clog << "Done" << endl;
1226
1227    if (Cache.BrokenCount() != 0)
1228    {
1229       // See if this is the result of a hold
1230       pkgCache::PkgIterator I = Cache.PkgBegin();
1231       for (;I.end() != true; I++)
1232       {
1233          if (Cache[I].InstBroken() == false)
1234             continue;
1235          if ((Flags[I->ID] & Protected) != Protected)
1236             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1237       }
1238       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1239    }
1240
1241    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1242    pkgCache::PkgIterator I = Cache.PkgBegin();
1243    for (;I.end() != true; I++) {
1244       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1245          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1246             std::clog << "Resolve installed new pkg: " << I.FullName(false)
1247                       << " (now marking it as auto)" << std::endl;
1248          }
1249          Cache[I].Flags |= pkgCache::Flag::Auto;
1250       }
1251    }
1252
1253
1254    return true;
1255 }
1256                                                                         /*}}}*/
1257 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1258 // ---------------------------------------------------------------------
1259 /* This is the work horse of the soft upgrade routine. It is very gental
1260    in that it does not install or remove any packages. It is assumed that the
1261    system was non-broken previously. */
1262 bool pkgProblemResolver::ResolveByKeep()
1263 {
1264    pkgDepCache::ActionGroup group(Cache);
1265
1266    unsigned long Size = Cache.Head().PackageCount;
1267
1268    MakeScores();
1269
1270    /* We have to order the packages so that the broken fixing pass
1271       operates from highest score to lowest. This prevents problems when
1272       high score packages cause the removal of lower score packages that
1273       would cause the removal of even lower score packages. */
1274    pkgCache::Package **PList = new pkgCache::Package *[Size];
1275    pkgCache::Package **PEnd = PList;
1276    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1277       *PEnd++ = I;
1278    This = this;
1279    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1280
1281    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1282    {
1283       clog << "Show Scores" << endl;
1284       for (pkgCache::Package **K = PList; K != PEnd; K++)
1285          if (Scores[(*K)->ID] != 0)
1286          {
1287            pkgCache::PkgIterator Pkg(Cache,*K);
1288            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1289          }
1290    }
1291
1292    if (Debug == true)
1293       clog << "Entering ResolveByKeep" << endl;
1294
1295    // Consider each broken package
1296    pkgCache::Package **LastStop = 0;
1297    for (pkgCache::Package **K = PList; K != PEnd; K++)
1298    {
1299       pkgCache::PkgIterator I(Cache,*K);
1300
1301       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1302          continue;
1303
1304       /* Keep the package. If this works then great, otherwise we have
1305          to be significantly more agressive and manipulate its dependencies */
1306       if ((Flags[I->ID] & Protected) == 0)
1307       {
1308          if (Debug == true)
1309             clog << "Keeping package " << I.FullName(false) << endl;
1310          Cache.MarkKeep(I, false, false);
1311          if (Cache[I].InstBroken() == false)
1312          {
1313             K = PList - 1;
1314             continue;
1315          }
1316       }
1317
1318       // Isolate the problem dependencies
1319       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1320       {
1321          DepIterator Start;
1322          DepIterator End;
1323          D.GlobOr(Start,End);
1324
1325          // We only worry about critical deps.
1326          if (End.IsCritical() != true)
1327             continue;
1328
1329          // Dep is ok
1330          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1331             continue;
1332
1333          /* Hm, the group is broken.. I suppose the best thing to do is to
1334             is to try every combination of keep/not-keep for the set, but thats
1335             slow, and this never happens, just be conservative and assume the
1336             list of ors is in preference and keep till it starts to work. */
1337          while (true)
1338          {
1339             if (Debug == true)
1340                clog << "Package " << I.FullName(false) << " " << Start << endl;
1341
1342             // Look at all the possible provides on this package
1343             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1344             for (pkgCache::Version **V = VList; *V != 0; V++)
1345             {
1346                pkgCache::VerIterator Ver(Cache,*V);
1347                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1348
1349                // It is not keepable
1350                if (Cache[Pkg].InstallVer == 0 ||
1351                    Pkg->CurrentVer == 0)
1352                   continue;
1353
1354                if ((Flags[I->ID] & Protected) == 0)
1355                {
1356                   if (Debug == true)
1357                      clog << "  Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1358                   Cache.MarkKeep(Pkg, false, false);
1359                }
1360
1361                if (Cache[I].InstBroken() == false)
1362                   break;
1363             }
1364
1365             if (Cache[I].InstBroken() == false)
1366                break;
1367
1368             if (Start == End)
1369                break;
1370             Start++;
1371          }
1372
1373          if (Cache[I].InstBroken() == false)
1374             break;
1375       }
1376
1377       if (Cache[I].InstBroken() == true)
1378          continue;
1379
1380       // Restart again.
1381       if (K == LastStop)
1382          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.FullName(false).c_str());
1383       LastStop = K;
1384       K = PList - 1;
1385    }
1386
1387    return true;
1388 }
1389                                                                         /*}}}*/
1390 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1391 // ---------------------------------------------------------------------
1392 /* This is used to make sure protected packages are installed */
1393 void pkgProblemResolver::InstallProtect()
1394 {
1395    pkgDepCache::ActionGroup group(Cache);
1396
1397    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1398    {
1399       if ((Flags[I->ID] & Protected) == Protected)
1400       {
1401          if ((Flags[I->ID] & ToRemove) == ToRemove)
1402             Cache.MarkDelete(I);
1403          else
1404          {
1405             // preserve the information whether the package was auto
1406             // or manually installed
1407             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1408             Cache.MarkInstall(I, false, 0, !autoInst);
1409          }
1410       }
1411    }
1412 }
1413                                                                         /*}}}*/
1414 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1415 // ---------------------------------------------------------------------
1416 /* This is ment to be used in conjunction with AllTargets to get a list
1417    of versions ordered by preference. */
1418 static pkgCache *PrioCache;
1419 static int PrioComp(const void *A,const void *B)
1420 {
1421    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1422    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1423
1424    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1425        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1426      return 1;
1427    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1428        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1429      return -1;
1430
1431    if (L->Priority != R->Priority)
1432       return R->Priority - L->Priority;
1433    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1434 }
1435 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1436 {
1437    unsigned long Count = 0;
1438    PrioCache = &Cache;
1439    for (pkgCache::Version **I = List; *I != 0; I++)
1440       Count++;
1441    qsort(List,Count,sizeof(*List),PrioComp);
1442 }
1443                                                                         /*}}}*/
1444 // CacheFile::ListUpdate - update the cache files                       /*{{{*/
1445 // ---------------------------------------------------------------------
1446 /* This is a simple wrapper to update the cache. it will fetch stuff
1447  * from the network (or any other sources defined in sources.list)
1448  */
1449 bool ListUpdate(pkgAcquireStatus &Stat,
1450                 pkgSourceList &List,
1451                 int PulseInterval)
1452 {
1453    pkgAcquire::RunResult res;
1454    pkgAcquire Fetcher;
1455    if (Fetcher.Setup(&Stat, _config->FindDir("Dir::State::Lists")) == false)
1456       return false;
1457
1458    // Populate it with the source selection
1459    if (List.GetIndexes(&Fetcher) == false)
1460          return false;
1461
1462    // Run scripts
1463    RunScripts("APT::Update::Pre-Invoke");
1464
1465    // check arguments
1466    if(PulseInterval>0)
1467       res = Fetcher.Run(PulseInterval);
1468    else
1469       res = Fetcher.Run();
1470
1471    if (res == pkgAcquire::Failed)
1472       return false;
1473
1474    bool Failed = false;
1475    bool TransientNetworkFailure = false;
1476    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin();
1477         I != Fetcher.ItemsEnd(); I++)
1478    {
1479       if ((*I)->Status == pkgAcquire::Item::StatDone)
1480          continue;
1481
1482       (*I)->Finished();
1483
1484       ::URI uri((*I)->DescURI());
1485       uri.User.clear();
1486       uri.Password.clear();
1487       string descUri = string(uri);
1488       _error->Warning(_("Failed to fetch %s  %s\n"), descUri.c_str(),
1489               (*I)->ErrorText.c_str());
1490
1491       if ((*I)->Status == pkgAcquire::Item::StatTransientNetworkError)
1492       {
1493          TransientNetworkFailure = true;
1494          continue;
1495       }
1496
1497       Failed = true;
1498    }
1499
1500    // Clean out any old list files
1501    // Keep "APT::Get::List-Cleanup" name for compatibility, but
1502    // this is really a global option for the APT library now
1503    if (!TransientNetworkFailure && !Failed &&
1504        (_config->FindB("APT::Get::List-Cleanup",true) == true &&
1505         _config->FindB("APT::List-Cleanup",true) == true))
1506    {
1507       if (Fetcher.Clean(_config->FindDir("Dir::State::lists")) == false ||
1508           Fetcher.Clean(_config->FindDir("Dir::State::lists") + "partial/") == false)
1509          // something went wrong with the clean
1510          return false;
1511    }
1512
1513    if (TransientNetworkFailure == true)
1514       _error->Warning(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1515    else if (Failed == true)
1516       return _error->Error(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1517
1518
1519    // Run the success scripts if all was fine
1520    if(!TransientNetworkFailure && !Failed)
1521       RunScripts("APT::Update::Post-Invoke-Success");
1522
1523    // Run the other scripts
1524    RunScripts("APT::Update::Post-Invoke");
1525    return true;
1526 }
1527                                                                         /*}}}*/