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    std::string const solver = _config->Find("APT::Solver::Name", "internal");
 336    if (solver != "internal")
 337       return EDSP::ResolveExternal(solver.c_str(), Cache, false, true, false);
 338
 339    pkgDepCache::ActionGroup group(Cache);
 340
 341    /* Upgrade all installed packages first without autoinst to help the resolver
 342       in versioned or-groups to upgrade the old solver instead of installing
 343       a new one (if the old solver is not the first one [anymore]) */
 344    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 345       if (I->CurrentVer != 0)
 346          Cache.MarkInstall(I, false, 0, false);
 347
 348    /* Auto upgrade all installed packages, this provides the basis
 349       for the installation */
 350    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 351       if (I->CurrentVer != 0)
 352          Cache.MarkInstall(I, true, 0, false);
 353
 354    /* Now, auto upgrade all essential packages - this ensures that
 355       the essential packages are present and working */
 356    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 357       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 358          Cache.MarkInstall(I, true, 0, false);
 359
 360    /* We do it again over all previously installed packages to force
 361       conflict resolution on them all. */
 362    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 363       if (I->CurrentVer != 0)
 364          Cache.MarkInstall(I, false, 0, false);
 365
 366    pkgProblemResolver Fix(&Cache);
 367
 368    // Hold back held packages.
 369    if (_config->FindB("APT::Ignore-Hold",false) == false)
 370    {
 371       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 372       {
 373          if (I->SelectedState == pkgCache::State::Hold)
 374          {
 375             Fix.Protect(I);
 376             Cache.MarkKeep(I, false, false);
 377          }
 378       }
 379    }
 380
 381    return Fix.Resolve();
 382 }
 383                                                                         /*}}}*/
 384 // AllUpgrade - Upgrade as many packages as possible                    /*{{{*/
 385 // ---------------------------------------------------------------------
 386 /* Right now the system must be consistent before this can be called.
 387    It also will not change packages marked for install, it only tries
 388    to install packages not marked for install */
 389 bool pkgAllUpgrade(pkgDepCache &Cache)
 390 {
 391    std::string const solver = _config->Find("APT::Solver::Name", "internal");
 392    if (solver != "internal")
 393       return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false);
 394
 395    pkgDepCache::ActionGroup group(Cache);
 396
 397    pkgProblemResolver Fix(&Cache);
 398
 399    if (Cache.BrokenCount() != 0)
 400       return false;
 401
 402    // Upgrade all installed packages
 403    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 404    {
 405       if (Cache[I].Install() == true)
 406          Fix.Protect(I);
 407
 408       if (_config->FindB("APT::Ignore-Hold",false) == false)
 409          if (I->SelectedState == pkgCache::State::Hold)
 410             continue;
 411
 412       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
 413          Cache.MarkInstall(I, false, 0, false);
 414    }
 415
 416    return Fix.ResolveByKeep();
 417 }
 418                                                                         /*}}}*/
 419 // MinimizeUpgrade - Minimizes the set of packages to be upgraded       /*{{{*/
 420 // ---------------------------------------------------------------------
 421 /* This simply goes over the entire set of packages and tries to keep
 422    each package marked for upgrade. If a conflict is generated then
 423    the package is restored. */
 424 bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 425 {
 426    pkgDepCache::ActionGroup group(Cache);
 427
 428    if (Cache.BrokenCount() != 0)
 429       return false;
 430
 431    // We loop for 10 tries to get the minimal set size.
 432    bool Change = false;
 433    unsigned int Count = 0;
 434    do
 435    {
 436       Change = false;
 437       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 438       {
 439          // Not interesting
 440          if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
 441             continue;
 442
 443          // Keep it and see if that is OK
 444          Cache.MarkKeep(I, false, false);
 445          if (Cache.BrokenCount() != 0)
 446             Cache.MarkInstall(I, false, 0, false);
 447          else
 448          {
 449             // If keep didnt actually do anything then there was no change..
 450             if (Cache[I].Upgrade() == false)
 451                Change = true;
 452          }
 453       }
 454       Count++;
 455    }
 456    while (Change == true && Count < 10);
 457
 458    if (Cache.BrokenCount() != 0)
 459       return _error->Error("Internal Error in pkgMinimizeUpgrade");
 460
 461    return true;
 462 }
 463                                                                         /*}}}*/
 464 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
 465 // ---------------------------------------------------------------------
 466 /* */
 467 pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : Cache(*pCache)
 468 {
 469    // Allocate memory
 470    unsigned long Size = Cache.Head().PackageCount;
 471    Scores = new signed short[Size];
 472    Flags = new unsigned char[Size];
 473    memset(Flags,0,sizeof(*Flags)*Size);
 474
 475    // Set debug to true to see its decision logic
 476    Debug = _config->FindB("Debug::pkgProblemResolver",false);
 477 }
 478                                                                         /*}}}*/
 479 // ProblemResolver::~pkgProblemResolver - Destructor                    /*{{{*/
 480 // ---------------------------------------------------------------------
 481 /* */
 482 pkgProblemResolver::~pkgProblemResolver()
 483 {
 484    delete [] Scores;
 485    delete [] Flags;
 486 }
 487                                                                         /*}}}*/
 488 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
 489 // ---------------------------------------------------------------------
 490 /* */
 491 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
 492 {
 493    Package const **A = (Package const **)a;
 494    Package const **B = (Package const **)b;
 495    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
 496       return -1;
 497    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
 498       return 1;
 499    return 0;
 500 }
 501                                                                         /*}}}*/
 502 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
 503 // ---------------------------------------------------------------------
 504 /* */
 505 void pkgProblemResolver::MakeScores()
 506 {
 507    unsigned long Size = Cache.Head().PackageCount;
 508    memset(Scores,0,sizeof(*Scores)*Size);
 509
 510    // Important Required Standard Optional Extra
 511    signed short PrioMap[] = {
 512       0,
 513       (signed short) _config->FindI("pkgProblemResolver::Scores::Important",3),
 514       (signed short) _config->FindI("pkgProblemResolver::Scores::Required",2),
 515       (signed short) _config->FindI("pkgProblemResolver::Scores::Standard",1),
 516       (signed short) _config->FindI("pkgProblemResolver::Scores::Optional",-1),
 517       (signed short) _config->FindI("pkgProblemResolver::Scores::Extra",-2)
 518    };
 519    signed short PrioEssentials = _config->FindI("pkgProblemResolver::Scores::Essentials",100);
 520    signed short PrioInstalledAndNotObsolete = _config->FindI("pkgProblemResolver::Scores::NotObsolete",1);
 521    signed short PrioDepends = _config->FindI("pkgProblemResolver::Scores::Depends",1);
 522    signed short PrioRecommends = _config->FindI("pkgProblemResolver::Scores::Recommends",1);
 523    signed short AddProtected = _config->FindI("pkgProblemResolver::Scores::AddProtected",10000);
 524    signed short AddEssential = _config->FindI("pkgProblemResolver::Scores::AddEssential",5000);
 525
 526    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 527       clog << "Settings used to calculate pkgProblemResolver::Scores::" << endl
 528          << "  Important => " << PrioMap[1] << endl
 529          << "  Required => " << PrioMap[2] << endl
 530          << "  Standard => " << PrioMap[3] << endl
 531          << "  Optional => " << PrioMap[4] << endl
 532          << "  Extra => " << PrioMap[5] << endl
 533          << "  Essentials => " << PrioEssentials << endl
 534          << "  InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete << endl
 535          << "  Depends => " << PrioDepends << endl
 536          << "  Recommends => " << PrioRecommends << endl
 537          << "  AddProtected => " << AddProtected << endl
 538          << "  AddEssential => " << AddEssential << endl;
 539
 540    // Generate the base scores for a package based on its properties
 541    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 542    {
 543       if (Cache[I].InstallVer == 0)
 544          continue;
 545
 546       signed short &Score = Scores[I->ID];
 547
 548       /* This is arbitrary, it should be high enough to elevate an
 549          essantial package above most other packages but low enough
 550          to allow an obsolete essential packages to be removed by
 551          a conflicts on a powerfull normal package (ie libc6) */
 552       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 553          Score += PrioEssentials;
 554
 555       // We transform the priority
 556       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 557          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 558
 559       /* This helps to fix oddball problems with conflicting packages
 560          on the same level. We enhance the score of installed packages
 561          if those are not obsolete
 562       */
 563       if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
 564          Score += PrioInstalledAndNotObsolete;
 565    }
 566
 567    // Now that we have the base scores we go and propogate dependencies
 568    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 569    {
 570       if (Cache[I].InstallVer == 0)
 571          continue;
 572
 573       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 574       {
 575          if (D->Type == pkgCache::Dep::Depends ||
 576              D->Type == pkgCache::Dep::PreDepends)
 577             Scores[D.TargetPkg()->ID] += PrioDepends;
 578          else if (D->Type == pkgCache::Dep::Recommends)
 579             Scores[D.TargetPkg()->ID] += PrioRecommends;
 580       }
 581    }
 582
 583    // Copy the scores to advoid additive looping
 584    SPtrArray<signed short> OldScores = new signed short[Size];
 585    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 586
 587    /* Now we cause 1 level of dependency inheritance, that is we add the
 588       score of the packages that depend on the target Package. This
 589       fortifies high scoring packages */
 590    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 591    {
 592       if (Cache[I].InstallVer == 0)
 593          continue;
 594
 595       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 596       {
 597          // Only do it for the install version
 598          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 599              (D->Type != pkgCache::Dep::Depends &&
 600               D->Type != pkgCache::Dep::PreDepends &&
 601               D->Type != pkgCache::Dep::Recommends))
 602             continue;
 603
 604          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 605       }
 606    }
 607
 608    /* Now we propogate along provides. This makes the packages that
 609       provide important packages extremely important */
 610    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 611    {
 612       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 613       {
 614          // Only do it once per package
 615          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 616             continue;
 617          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 618       }
 619    }
 620
 621    /* Protected things are pushed really high up. This number should put them
 622       ahead of everything */
 623    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 624    {
 625       if ((Flags[I->ID] & Protected) != 0)
 626          Scores[I->ID] += AddProtected;
 627       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 628          Scores[I->ID] += AddEssential;
 629    }
 630 }
 631                                                                         /*}}}*/
 632 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 633 // ---------------------------------------------------------------------
 634 /* This goes through and tries to reinstall packages to make this package
 635    installable */
 636 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 637 {
 638    pkgDepCache::ActionGroup group(Cache);
 639
 640    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 641       return false;
 642    if ((Flags[Pkg->ID] & Protected) == Protected)
 643       return false;
 644
 645    Flags[Pkg->ID] &= ~Upgradable;
 646
 647    bool WasKept = Cache[Pkg].Keep();
 648    Cache.MarkInstall(Pkg, false, 0, false);
 649
 650    // This must be a virtual package or something like that.
 651    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 652       return false;
 653
 654    // Isolate the problem dependency
 655    bool Fail = false;
 656    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 657    {
 658       // Compute a single dependency element (glob or)
 659       pkgCache::DepIterator Start = D;
 660       pkgCache::DepIterator End = D;
 661       unsigned char State = 0;
 662       for (bool LastOR = true; D.end() == false && LastOR == true;)
 663       {
 664          State |= Cache[D];
 665          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 666          D++;
 667          if (LastOR == true)
 668             End = D;
 669       }
 670
 671       // We only worry about critical deps.
 672       if (End.IsCritical() != true)
 673          continue;
 674
 675       // Iterate over all the members in the or group
 676       while (1)
 677       {
 678          // Dep is ok now
 679          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 680             break;
 681
 682          // Do not change protected packages
 683          PkgIterator P = Start.SmartTargetPkg();
 684          if ((Flags[P->ID] & Protected) == Protected)
 685          {
 686             if (Debug == true)
 687                clog << "    Reinst Failed because of protected " << P.FullName(false) << endl;
 688             Fail = true;
 689          }
 690          else
 691          {
 692             // Upgrade the package if the candidate version will fix the problem.
 693             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 694             {
 695                if (DoUpgrade(P) == false)
 696                {
 697                   if (Debug == true)
 698                      clog << "    Reinst Failed because of " << P.FullName(false) << endl;
 699                   Fail = true;
 700                }
 701                else
 702                {
 703                   Fail = false;
 704                   break;
 705                }
 706             }
 707             else
 708             {
 709                /* We let the algorithm deal with conflicts on its next iteration,
 710                 it is much smarter than us */
 711                if (Start->Type == pkgCache::Dep::Conflicts ||
 712                    Start->Type == pkgCache::Dep::DpkgBreaks ||
 713                    Start->Type == pkgCache::Dep::Obsoletes)
 714                    break;
 715
 716                if (Debug == true)
 717                   clog << "    Reinst Failed early because of " << Start.TargetPkg().FullName(false) << endl;
 718                Fail = true;
 719             }
 720          }
 721
 722          if (Start == End)
 723             break;
 724          Start++;
 725       }
 726       if (Fail == true)
 727          break;
 728    }
 729
 730    // Undo our operations - it might be smart to undo everything this did..
 731    if (Fail == true)
 732    {
 733       if (WasKept == true)
 734          Cache.MarkKeep(Pkg, false, false);
 735       else
 736          Cache.MarkDelete(Pkg);
 737       return false;
 738    }
 739
 740    if (Debug == true)
 741       clog << "  Re-Instated " << Pkg.FullName(false) << endl;
 742    return true;
 743 }
 744                                                                         /*}}}*/
 745 // ProblemResolver::Resolve - calls a resolver to fix the situation     /*{{{*/
 746 // ---------------------------------------------------------------------
 747 /* */
 748 bool pkgProblemResolver::Resolve(bool BrokenFix)
 749 {
 750    std::string const solver = _config->Find("APT::Solver::Name", "internal");
 751    if (solver != "internal")
 752       return EDSP::ResolveExternal(solver.c_str(), Cache, false, false, false);
 753    return ResolveInternal(BrokenFix);
 754 }
 755                                                                         /*}}}*/
 756 // ProblemResolver::ResolveInternal - Run the resolution pass           /*{{{*/
 757 // ---------------------------------------------------------------------
 758 /* This routines works by calculating a score for each package. The score
 759    is derived by considering the package's priority and all reverse
 760    dependents giving an integer that reflects the amount of breakage that
 761    adjusting the package will inflict.
 762
 763    It goes from highest score to lowest and corrects all of the breaks by
 764    keeping or removing the dependant packages. If that fails then it removes
 765    the package itself and goes on. The routine should be able to intelligently
 766    go from any broken state to a fixed state.
 767
 768    The BrokenFix flag enables a mode where the algorithm tries to
 769    upgrade packages to advoid problems. */
 770 bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
 771 {
 772    pkgDepCache::ActionGroup group(Cache);
 773
 774    // Record which packages are marked for install
 775    bool Again = false;
 776    do
 777    {
 778       Again = false;
 779       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 780       {
 781          if (Cache[I].Install() == true)
 782             Flags[I->ID] |= PreInstalled;
 783          else
 784          {
 785             if (Cache[I].InstBroken() == true && BrokenFix == true)
 786             {
 787                Cache.MarkInstall(I, false, 0, false);
 788                if (Cache[I].Install() == true)
 789                   Again = true;
 790             }
 791
 792             Flags[I->ID] &= ~PreInstalled;
 793          }
 794          Flags[I->ID] |= Upgradable;
 795       }
 796    }
 797    while (Again == true);
 798
 799    if (Debug == true)
 800       clog << "Starting" << endl;
 801
 802    MakeScores();
 803
 804    unsigned long const Size = Cache.Head().PackageCount;
 805
 806    /* We have to order the packages so that the broken fixing pass
 807       operates from highest score to lowest. This prevents problems when
 808       high score packages cause the removal of lower score packages that
 809       would cause the removal of even lower score packages. */
 810    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 811    pkgCache::Package **PEnd = PList;
 812    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 813       *PEnd++ = I;
 814    This = this;
 815    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 816
 817    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 818    {
 819       clog << "Show Scores" << endl;
 820       for (pkgCache::Package **K = PList; K != PEnd; K++)
 821          if (Scores[(*K)->ID] != 0)
 822          {
 823            pkgCache::PkgIterator Pkg(Cache,*K);
 824            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
 825          }
 826    }
 827
 828    if (Debug == true)
 829       clog << "Starting 2" << endl;
 830
 831    /* Now consider all broken packages. For each broken package we either
 832       remove the package or fix it's problem. We do this once, it should
 833       not be possible for a loop to form (that is a < b < c and fixing b by
 834       changing a breaks c) */
 835    bool Change = true;
 836    bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
 837    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 838    {
 839       Change = false;
 840       for (pkgCache::Package **K = PList; K != PEnd; K++)
 841       {
 842          pkgCache::PkgIterator I(Cache,*K);
 843
 844          /* We attempt to install this and see if any breaks result,
 845             this takes care of some strange cases */
 846          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 847              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 848              (Flags[I->ID] & PreInstalled) != 0 &&
 849              (Flags[I->ID] & Protected) == 0 &&
 850              (Flags[I->ID] & ReInstateTried) == 0)
 851          {
 852             if (Debug == true)
 853                clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
 854             unsigned long OldBreaks = Cache.BrokenCount();
 855             pkgCache::Version *OldVer = Cache[I].InstallVer;
 856             Flags[I->ID] &= ReInstateTried;
 857
 858             Cache.MarkInstall(I, false, 0, false);
 859             if (Cache[I].InstBroken() == true ||
 860                 OldBreaks < Cache.BrokenCount())
 861             {
 862                if (OldVer == 0)
 863                   Cache.MarkDelete(I);
 864                else
 865                   Cache.MarkKeep(I, false, false);
 866             }
 867             else
 868                if (Debug == true)
 869                   clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 870          }
 871
 872          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 873             continue;
 874
 875          if (Debug == true)
 876             clog << "Investigating (" << Counter << ") " << I << endl;
 877
 878          // Isolate the problem dependency
 879          PackageKill KillList[100];
 880          PackageKill *LEnd = KillList;
 881          bool InOr = false;
 882          pkgCache::DepIterator Start;
 883          pkgCache::DepIterator End;
 884          PackageKill *OldEnd = LEnd;
 885
 886          enum {OrRemove,OrKeep} OrOp = OrRemove;
 887          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 888               D.end() == false || InOr == true;)
 889          {
 890             // Compute a single dependency element (glob or)
 891             if (Start == End)
 892             {
 893                // Decide what to do
 894                if (InOr == true && OldEnd == LEnd)
 895                {
 896                   if (OrOp == OrRemove)
 897                   {
 898                      if ((Flags[I->ID] & Protected) != Protected)
 899                      {
 900                         if (Debug == true)
 901                            clog << "  Or group remove for " << I.FullName(false) << endl;
 902                         Cache.MarkDelete(I);
 903                         Change = true;
 904                      }
 905                   }
 906                   else if (OrOp == OrKeep)
 907                   {
 908                      if (Debug == true)
 909                         clog << "  Or group keep for " << I.FullName(false) << endl;
 910                      Cache.MarkKeep(I, false, false);
 911                      Change = true;
 912                   }
 913                }
 914
 915                /* We do an extra loop (as above) to finalize the or group
 916                   processing */
 917                InOr = false;
 918                OrOp = OrRemove;
 919                D.GlobOr(Start,End);
 920                if (Start.end() == true)
 921                   break;
 922
 923                // We only worry about critical deps.
 924                if (End.IsCritical() != true)
 925                   continue;
 926
 927                InOr = Start != End;
 928                OldEnd = LEnd;
 929             }
 930             else
 931             {
 932                Start++;
 933                // We only worry about critical deps.
 934                if (Start.IsCritical() != true)
 935                   continue;
 936             }
 937
 938             // Dep is ok
 939             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 940             {
 941                InOr = false;
 942                continue;
 943             }
 944
 945             if (Debug == true)
 946                clog << "Broken " << Start << endl;
 947
 948             /* Look across the version list. If there are no possible
 949                targets then we keep the package and bail. This is necessary
 950                if a package has a dep on another package that cant be found */
 951             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 952             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 953                 Start->Type != pkgCache::Dep::Conflicts &&
 954                 Start->Type != pkgCache::Dep::DpkgBreaks &&
 955                 Start->Type != pkgCache::Dep::Obsoletes &&
 956                 Cache[I].NowBroken() == false)
 957             {
 958                if (InOr == true)
 959                {
 960                   /* No keep choice because the keep being OK could be the
 961                      result of another element in the OR group! */
 962                   continue;
 963                }
 964
 965                Change = true;
 966                Cache.MarkKeep(I, false, false);
 967                break;
 968             }
 969
 970             bool Done = false;
 971             for (pkgCache::Version **V = VList; *V != 0; V++)
 972             {
 973                pkgCache::VerIterator Ver(Cache,*V);
 974                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 975
 976                /* This is a conflicts, and the version we are looking
 977                   at is not the currently selected version of the
 978                   package, which means it is not necessary to
 979                   remove/keep */
 980                if (Cache[Pkg].InstallVer != Ver &&
 981                    (Start->Type == pkgCache::Dep::Conflicts ||
 982                     Start->Type == pkgCache::Dep::DpkgBreaks ||
 983                     Start->Type == pkgCache::Dep::Obsoletes))
 984                {
 985                   if (Debug)
 986                      clog << "  Conflicts//Breaks against version "
 987                           << Ver.VerStr() << " for " << Pkg.Name()
 988                           << " but that is not InstVer, ignoring"
 989                           << endl;
 990                   continue;
 991                }
 992
 993                if (Debug == true)
 994                   clog << "  Considering " << Pkg.FullName(false) << ' ' << (int)Scores[Pkg->ID] <<
 995                   " as a solution to " << I.FullName(false) << ' ' << (int)Scores[I->ID] << endl;
 996
 997                /* Try to fix the package under consideration rather than
 998                   fiddle with the VList package */
 999                if (Scores[I->ID] <= Scores[Pkg->ID] ||
1000                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
1001                     End->Type != pkgCache::Dep::Conflicts &&
1002                     End->Type != pkgCache::Dep::DpkgBreaks &&
1003                     End->Type != pkgCache::Dep::Obsoletes))
1004                {
1005                   // Try a little harder to fix protected packages..
1006                   if ((Flags[I->ID] & Protected) == Protected)
1007                   {
1008                      if (DoUpgrade(Pkg) == true)
1009                      {
1010                         if (Scores[Pkg->ID] > Scores[I->ID])
1011                            Scores[Pkg->ID] = Scores[I->ID];
1012                         break;
1013                      }
1014
1015                      continue;
1016                   }
1017
1018                   /* See if a keep will do, unless the package is protected,
1019                      then installing it will be necessary */
1020                   bool Installed = Cache[I].Install();
1021                   Cache.MarkKeep(I, false, false);
1022                   if (Cache[I].InstBroken() == false)
1023                   {
1024                      // Unwind operation will be keep now
1025                      if (OrOp == OrRemove)
1026                         OrOp = OrKeep;
1027
1028                      // Restore
1029                      if (InOr == true && Installed == true)
1030                         Cache.MarkInstall(I, false, 0, false);
1031
1032                      if (Debug == true)
1033                         clog << "  Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1034                   }
1035                   else
1036                   {
1037                      if (BrokenFix == false || DoUpgrade(I) == false)
1038                      {
1039                         // Consider other options
1040                         if (InOr == false)
1041                         {
1042                            if (Debug == true)
1043                               clog << "  Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1044                            Cache.MarkDelete(I);
1045                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
1046                               Scores[I->ID] = Scores[Pkg->ID];
1047                         }
1048                         else if (TryFixByInstall == true &&
1049                                  Start.TargetPkg()->CurrentVer == 0 &&
1050                                  Cache[Start.TargetPkg()].Delete() == false &&
1051                                  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
1052                                  Cache.GetCandidateVer(Start.TargetPkg()).end() == false)
1053                         {
1054                            /* Before removing or keeping the package with the broken dependency
1055                               try instead to install the first not previously installed package
1056                               solving this dependency. This helps every time a previous solver
1057                               is removed by the resolver because of a conflict or alike but it is
1058                               dangerous as it could trigger new breaks/conflicts… */
1059                            if (Debug == true)
1060                               clog << "  Try Installing " << Start.TargetPkg() << " before changing " << I.FullName(false) << std::endl;
1061                            unsigned long const OldBroken = Cache.BrokenCount();
1062                            Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
1063                            // FIXME: we should undo the complete MarkInstall process here
1064                            if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
1065                               Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
1066                         }
1067                      }
1068                   }
1069
1070                   Change = true;
1071                   Done = true;
1072                   break;
1073                }
1074                else
1075                {
1076                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
1077                   {
1078                      // first, try upgradring the package, if that
1079                      // does not help, the breaks goes onto the
1080                      // kill list
1081                      //
1082                      // FIXME: use DoUpgrade(Pkg) instead?
1083                      if (Cache[End] & pkgDepCache::DepGCVer)
1084                      {
1085                         if (Debug)
1086                            clog << "  Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
1087                         Cache.MarkInstall(Pkg, false, 0, false);
1088                         continue;
1089                      }
1090                   }
1091
1092                   // Skip adding to the kill list if it is protected
1093                   if ((Flags[Pkg->ID] & Protected) != 0)
1094                      continue;
1095
1096                   if (Debug == true)
1097                      clog << "  Added " << Pkg.FullName(false) << " to the remove list" << endl;
1098
1099                   LEnd->Pkg = Pkg;
1100                   LEnd->Dep = End;
1101                   LEnd++;
1102
1103                   if (Start->Type != pkgCache::Dep::Conflicts &&
1104                       Start->Type != pkgCache::Dep::Obsoletes)
1105                      break;
1106                }
1107             }
1108
1109             // Hm, nothing can possibly satisify this dep. Nuke it.
1110             if (VList[0] == 0 &&
1111                 Start->Type != pkgCache::Dep::Conflicts &&
1112                 Start->Type != pkgCache::Dep::DpkgBreaks &&
1113                 Start->Type != pkgCache::Dep::Obsoletes &&
1114                 (Flags[I->ID] & Protected) != Protected)
1115             {
1116                bool Installed = Cache[I].Install();
1117                Cache.MarkKeep(I);
1118                if (Cache[I].InstBroken() == false)
1119                {
1120                   // Unwind operation will be keep now
1121                   if (OrOp == OrRemove)
1122                      OrOp = OrKeep;
1123
1124                   // Restore
1125                   if (InOr == true && Installed == true)
1126                      Cache.MarkInstall(I, false, 0, false);
1127
1128                   if (Debug == true)
1129                      clog << "  Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1130                }
1131                else
1132                {
1133                   if (Debug == true)
1134                      clog << "  Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1135                   if (InOr == false)
1136                      Cache.MarkDelete(I);
1137                }
1138
1139                Change = true;
1140                Done = true;
1141             }
1142
1143             // Try some more
1144             if (InOr == true)
1145                continue;
1146
1147             if (Done == true)
1148                break;
1149          }
1150
1151          // Apply the kill list now
1152          if (Cache[I].InstallVer != 0)
1153          {
1154             for (PackageKill *J = KillList; J != LEnd; J++)
1155             {
1156                Change = true;
1157                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1158                {
1159                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1160                       J->Dep->Type == pkgCache::Dep::DpkgBreaks ||
1161                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1162                   {
1163                      if (Debug == true)
1164                         clog << "  Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
1165                      Cache.MarkDelete(J->Pkg);
1166                   }
1167                }
1168                else
1169                {
1170                   if (Debug == true)
1171                      clog << "  Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
1172                   Cache.MarkKeep(J->Pkg, false, false);
1173                }
1174
1175                if (Counter > 1)
1176                {
1177                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1178                      Scores[J->Pkg->ID] = Scores[I->ID];
1179                }
1180             }
1181          }
1182       }
1183    }
1184
1185    if (Debug == true)
1186       clog << "Done" << endl;
1187
1188    if (Cache.BrokenCount() != 0)
1189    {
1190       // See if this is the result of a hold
1191       pkgCache::PkgIterator I = Cache.PkgBegin();
1192       for (;I.end() != true; I++)
1193       {
1194          if (Cache[I].InstBroken() == false)
1195             continue;
1196          if ((Flags[I->ID] & Protected) != Protected)
1197             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1198       }
1199       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1200    }
1201
1202    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1203    pkgCache::PkgIterator I = Cache.PkgBegin();
1204    for (;I.end() != true; I++) {
1205       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1206          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1207             std::clog << "Resolve installed new pkg: " << I.FullName(false)
1208                       << " (now marking it as auto)" << std::endl;
1209          }
1210          Cache[I].Flags |= pkgCache::Flag::Auto;
1211       }
1212    }
1213
1214
1215    return true;
1216 }
1217                                                                         /*}}}*/
1218 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1219 // ---------------------------------------------------------------------
1220 /* This is the work horse of the soft upgrade routine. It is very gental
1221    in that it does not install or remove any packages. It is assumed that the
1222    system was non-broken previously. */
1223 bool pkgProblemResolver::ResolveByKeep()
1224 {
1225    std::string const solver = _config->Find("APT::Solver::Name", "internal");
1226    if (solver != "internal")
1227       return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false);
1228    return ResolveByKeepInternal();
1229 }
1230                                                                         /*}}}*/
1231 // ProblemResolver::ResolveByKeepInternal - Resolve problems using keep /*{{{*/
1232 // ---------------------------------------------------------------------
1233 /* This is the work horse of the soft upgrade routine. It is very gental
1234    in that it does not install or remove any packages. It is assumed that the
1235    system was non-broken previously. */
1236 bool pkgProblemResolver::ResolveByKeepInternal()
1237 {
1238    pkgDepCache::ActionGroup group(Cache);
1239
1240    unsigned long Size = Cache.Head().PackageCount;
1241
1242    MakeScores();
1243
1244    /* We have to order the packages so that the broken fixing pass
1245       operates from highest score to lowest. This prevents problems when
1246       high score packages cause the removal of lower score packages that
1247       would cause the removal of even lower score packages. */
1248    pkgCache::Package **PList = new pkgCache::Package *[Size];
1249    pkgCache::Package **PEnd = PList;
1250    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1251       *PEnd++ = I;
1252    This = this;
1253    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1254
1255    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1256    {
1257       clog << "Show Scores" << endl;
1258       for (pkgCache::Package **K = PList; K != PEnd; K++)
1259          if (Scores[(*K)->ID] != 0)
1260          {
1261            pkgCache::PkgIterator Pkg(Cache,*K);
1262            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1263          }
1264    }
1265
1266    if (Debug == true)
1267       clog << "Entering ResolveByKeep" << endl;
1268
1269    // Consider each broken package
1270    pkgCache::Package **LastStop = 0;
1271    for (pkgCache::Package **K = PList; K != PEnd; K++)
1272    {
1273       pkgCache::PkgIterator I(Cache,*K);
1274
1275       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1276          continue;
1277
1278       /* Keep the package. If this works then great, otherwise we have
1279          to be significantly more agressive and manipulate its dependencies */
1280       if ((Flags[I->ID] & Protected) == 0)
1281       {
1282          if (Debug == true)
1283             clog << "Keeping package " << I.FullName(false) << endl;
1284          Cache.MarkKeep(I, false, false);
1285          if (Cache[I].InstBroken() == false)
1286          {
1287             K = PList - 1;
1288             continue;
1289          }
1290       }
1291
1292       // Isolate the problem dependencies
1293       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1294       {
1295          DepIterator Start;
1296          DepIterator End;
1297          D.GlobOr(Start,End);
1298
1299          // We only worry about critical deps.
1300          if (End.IsCritical() != true)
1301             continue;
1302
1303          // Dep is ok
1304          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1305             continue;
1306
1307          /* Hm, the group is broken.. I suppose the best thing to do is to
1308             is to try every combination of keep/not-keep for the set, but thats
1309             slow, and this never happens, just be conservative and assume the
1310             list of ors is in preference and keep till it starts to work. */
1311          while (true)
1312          {
1313             if (Debug == true)
1314                clog << "Package " << I.FullName(false) << " " << Start << endl;
1315
1316             // Look at all the possible provides on this package
1317             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1318             for (pkgCache::Version **V = VList; *V != 0; V++)
1319             {
1320                pkgCache::VerIterator Ver(Cache,*V);
1321                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1322
1323                // It is not keepable
1324                if (Cache[Pkg].InstallVer == 0 ||
1325                    Pkg->CurrentVer == 0)
1326                   continue;
1327
1328                if ((Flags[I->ID] & Protected) == 0)
1329                {
1330                   if (Debug == true)
1331                      clog << "  Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1332                   Cache.MarkKeep(Pkg, false, false);
1333                }
1334
1335                if (Cache[I].InstBroken() == false)
1336                   break;
1337             }
1338
1339             if (Cache[I].InstBroken() == false)
1340                break;
1341
1342             if (Start == End)
1343                break;
1344             Start++;
1345          }
1346
1347          if (Cache[I].InstBroken() == false)
1348             break;
1349       }
1350
1351       if (Cache[I].InstBroken() == true)
1352          continue;
1353
1354       // Restart again.
1355       if (K == LastStop)
1356          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.FullName(false).c_str());
1357       LastStop = K;
1358       K = PList - 1;
1359    }
1360
1361    return true;
1362 }
1363                                                                         /*}}}*/
1364 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1365 // ---------------------------------------------------------------------
1366 /* This is used to make sure protected packages are installed */
1367 void pkgProblemResolver::InstallProtect()
1368 {
1369    pkgDepCache::ActionGroup group(Cache);
1370
1371    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1372    {
1373       if ((Flags[I->ID] & Protected) == Protected)
1374       {
1375          if ((Flags[I->ID] & ToRemove) == ToRemove)
1376             Cache.MarkDelete(I);
1377          else
1378          {
1379             // preserve the information whether the package was auto
1380             // or manually installed
1381             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1382             Cache.MarkInstall(I, false, 0, !autoInst);
1383          }
1384       }
1385    }
1386 }
1387                                                                         /*}}}*/
1388 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1389 // ---------------------------------------------------------------------
1390 /* This is ment to be used in conjunction with AllTargets to get a list
1391    of versions ordered by preference. */
1392 static pkgCache *PrioCache;
1393 static int PrioComp(const void *A,const void *B)
1394 {
1395    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1396    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1397
1398    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1399        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1400      return 1;
1401    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1402        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1403      return -1;
1404
1405    if (L->Priority != R->Priority)
1406       return R->Priority - L->Priority;
1407    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1408 }
1409 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1410 {
1411    unsigned long Count = 0;
1412    PrioCache = &Cache;
1413    for (pkgCache::Version **I = List; *I != 0; I++)
1414       Count++;
1415    qsort(List,Count,sizeof(*List),PrioComp);
1416 }
1417                                                                         /*}}}*/
1418 // CacheFile::ListUpdate - update the cache files                       /*{{{*/
1419 // ---------------------------------------------------------------------
1420 /* This is a simple wrapper to update the cache. it will fetch stuff
1421  * from the network (or any other sources defined in sources.list)
1422  */
1423 bool ListUpdate(pkgAcquireStatus &Stat,
1424                 pkgSourceList &List,
1425                 int PulseInterval)
1426 {
1427    pkgAcquire::RunResult res;
1428    pkgAcquire Fetcher;
1429    if (Fetcher.Setup(&Stat, _config->FindDir("Dir::State::Lists")) == false)
1430       return false;
1431
1432    // Populate it with the source selection
1433    if (List.GetIndexes(&Fetcher) == false)
1434          return false;
1435
1436    // Run scripts
1437    RunScripts("APT::Update::Pre-Invoke");
1438
1439    // check arguments
1440    if(PulseInterval>0)
1441       res = Fetcher.Run(PulseInterval);
1442    else
1443       res = Fetcher.Run();
1444
1445    if (res == pkgAcquire::Failed)
1446       return false;
1447
1448    bool Failed = false;
1449    bool TransientNetworkFailure = false;
1450    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin();
1451         I != Fetcher.ItemsEnd(); I++)
1452    {
1453       if ((*I)->Status == pkgAcquire::Item::StatDone)
1454          continue;
1455
1456       (*I)->Finished();
1457
1458       ::URI uri((*I)->DescURI());
1459       uri.User.clear();
1460       uri.Password.clear();
1461       string descUri = string(uri);
1462       _error->Warning(_("Failed to fetch %s  %s\n"), descUri.c_str(),
1463               (*I)->ErrorText.c_str());
1464
1465       if ((*I)->Status == pkgAcquire::Item::StatTransientNetworkError)
1466       {
1467          TransientNetworkFailure = true;
1468          continue;
1469       }
1470
1471       Failed = true;
1472    }
1473
1474    // Clean out any old list files
1475    // Keep "APT::Get::List-Cleanup" name for compatibility, but
1476    // this is really a global option for the APT library now
1477    if (!TransientNetworkFailure && !Failed &&
1478        (_config->FindB("APT::Get::List-Cleanup",true) == true &&
1479         _config->FindB("APT::List-Cleanup",true) == true))
1480    {
1481       if (Fetcher.Clean(_config->FindDir("Dir::State::lists")) == false ||
1482           Fetcher.Clean(_config->FindDir("Dir::State::lists") + "partial/") == false)
1483          // something went wrong with the clean
1484          return false;
1485    }
1486
1487    if (TransientNetworkFailure == true)
1488       _error->Warning(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1489    else if (Failed == true)
1490       return _error->Error(_("Some index files failed to download. They have been ignored, or old ones used instead."));
1491
1492
1493    // Run the success scripts if all was fine
1494    if(!TransientNetworkFailure && !Failed)
1495       RunScripts("APT::Update::Post-Invoke-Success");
1496
1497    // Run the other scripts
1498    RunScripts("APT::Update::Post-Invoke");
1499    return true;
1500 }
1501                                                                         /*}}}*/