]> git.saurik.com Git - apt.git/blame - apt-pkg/algorithms.cc
fix apt list output for pkgs in dpkg ^rc state
[apt.git] / apt-pkg / algorithms.cc
CommitLineData
6c139d6e
AL
1// -*- mode: cpp; mode: fold -*-
2// Description /*{{{*/
b8c0f9b7 3// $Id: algorithms.cc,v 1.44 2002/11/28 18:49:16 jgg Exp $
6c139d6e
AL
4/* ######################################################################
5
6 Algorithms - A set of misc algorithms
7
0a8e3465
AL
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
6c139d6e
AL
14 ##################################################################### */
15 /*}}}*/
16// Include Files /*{{{*/
ea542140
DK
17#include <config.h>
18
094a497d
AL
19#include <apt-pkg/algorithms.h>
20#include <apt-pkg/error.h>
0a8e3465 21#include <apt-pkg/configuration.h>
b2e465d6 22#include <apt-pkg/sptr.h>
c3b85126 23#include <apt-pkg/edsp.h>
472ff00e 24#include <apt-pkg/progress.h>
453b82a3
DK
25#include <apt-pkg/depcache.h>
26#include <apt-pkg/packagemanager.h>
27#include <apt-pkg/pkgcache.h>
28#include <apt-pkg/cacheiterators.h>
6d38011b 29
453b82a3
DK
30#include <string.h>
31#include <string>
152ab79e 32#include <cstdlib>
90f057fd 33#include <iostream>
ea542140
DK
34
35#include <apti18n.h>
6c139d6e 36 /*}}}*/
584e4558 37using namespace std;
6c139d6e
AL
38
39pkgProblemResolver *pkgProblemResolver::This = 0;
40
41// Simulate::Simulate - Constructor /*{{{*/
42// ---------------------------------------------------------------------
b2e465d6
AL
43/* The legacy translations here of input Pkg iterators is obsolete,
44 this is not necessary since the pkgCaches are fully shared now. */
45pkgSimulate::pkgSimulate(pkgDepCache *Cache) : pkgPackageManager(Cache),
46 iPolicy(Cache),
496d5c70
MV
47 Sim(&Cache->GetCache(),&iPolicy),
48 group(Sim)
6c139d6e 49{
b2e465d6
AL
50 Sim.Init(0);
51 Flags = new unsigned char[Cache->Head().PackageCount];
52 memset(Flags,0,sizeof(*Flags)*Cache->Head().PackageCount);
281daf46
AL
53
54 // Fake a filename so as not to activate the media swapping
55 string Jnk = "SIMULATE";
b2e465d6 56 for (unsigned int I = 0; I != Cache->Head().PackageCount; I++)
281daf46 57 FileNames[I] = Jnk;
6c139d6e
AL
58}
59 /*}}}*/
b270388b
MV
60// Simulate::~Simulate - Destructor /*{{{*/
61pkgSimulate::~pkgSimulate()
62{
63 delete[] Flags;
64}
65 /*}}}*/
b2e465d6
AL
66// Simulate::Describe - Describe a package /*{{{*/
67// ---------------------------------------------------------------------
3826564e
MZ
68/* Parameter Current == true displays the current package version,
69 Parameter Candidate == true displays the candidate package version */
70void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Current,bool Candidate)
b2e465d6
AL
71{
72 VerIterator Ver(Sim);
e59458f7 73
47f6d1b7 74 out << Pkg.FullName(true);
e59458f7 75
3826564e 76 if (Current == true)
e59458f7 77 {
b2e465d6 78 Ver = Pkg.CurrentVer();
e59458f7
AL
79 if (Ver.end() == false)
80 out << " [" << Ver.VerStr() << ']';
81 }
b2e465d6 82
3826564e
MZ
83 if (Candidate == true)
84 {
85 Ver = Sim[Pkg].CandidateVerIter(Sim);
86 if (Ver.end() == true)
87 return;
b2e465d6 88
3826564e
MZ
89 out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')';
90 }
b2e465d6
AL
91}
92 /*}}}*/
6c139d6e
AL
93// Simulate::Install - Simulate unpacking of a package /*{{{*/
94// ---------------------------------------------------------------------
95/* */
96bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/)
97{
98 // Adapt the iterator
803ea2a8 99 PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
6c139d6e
AL
100 Flags[Pkg->ID] = 1;
101
b2e465d6 102 cout << "Inst ";
3826564e 103 Describe(Pkg,cout,true,true);
6c139d6e 104 Sim.MarkInstall(Pkg,false);
803ea2a8 105
6c139d6e 106 // Look for broken conflicts+predepends.
f7f0d6c7 107 for (PkgIterator I = Sim.PkgBegin(); I.end() == false; ++I)
6c139d6e
AL
108 {
109 if (Sim[I].InstallVer == 0)
110 continue;
111
b2e465d6
AL
112 for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false;)
113 {
114 DepIterator Start;
115 DepIterator End;
116 D.GlobOr(Start,End);
359e46db 117 if (Start.IsNegative() == true ||
b2e465d6 118 End->Type == pkgCache::Dep::PreDepends)
6c139d6e 119 {
b2e465d6 120 if ((Sim[End] & pkgDepCache::DepGInstall) == 0)
6c139d6e 121 {
47f6d1b7 122 cout << " [" << I.FullName(false) << " on " << Start.TargetPkg().FullName(false) << ']';
b2e465d6 123 if (Start->Type == pkgCache::Dep::Conflicts)
47f6d1b7 124 _error->Error("Fatal, conflicts violated %s",I.FullName(false).c_str());
6c139d6e 125 }
b2e465d6
AL
126 }
127 }
6c139d6e
AL
128 }
129
130 if (Sim.BrokenCount() != 0)
131 ShortBreaks();
132 else
04aa15a8 133 cout << endl;
6c139d6e
AL
134 return true;
135}
136 /*}}}*/
137// Simulate::Configure - Simulate configuration of a Package /*{{{*/
138// ---------------------------------------------------------------------
139/* This is not an acurate simulation of relatity, we should really not
140 install the package.. For some investigations it may be necessary
141 however. */
142bool pkgSimulate::Configure(PkgIterator iPkg)
143{
144 // Adapt the iterator
803ea2a8 145 PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
6c139d6e
AL
146
147 Flags[Pkg->ID] = 2;
803ea2a8 148
6c139d6e
AL
149 if (Sim[Pkg].InstBroken() == true)
150 {
47f6d1b7 151 cout << "Conf " << Pkg.FullName(false) << " broken" << endl;
6c139d6e
AL
152
153 Sim.Update();
154
155 // Print out each package and the failed dependencies
f7f0d6c7 156 for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; ++D)
6c139d6e
AL
157 {
158 if (Sim.IsImportantDep(D) == false ||
159 (Sim[D] & pkgDepCache::DepInstall) != 0)
160 continue;
161
b2e465d6 162 if (D->Type == pkgCache::Dep::Obsoletes)
47f6d1b7 163 cout << " Obsoletes:" << D.TargetPkg().FullName(false);
b2e465d6 164 else if (D->Type == pkgCache::Dep::Conflicts)
47f6d1b7 165 cout << " Conflicts:" << D.TargetPkg().FullName(false);
308c7d30 166 else if (D->Type == pkgCache::Dep::DpkgBreaks)
47f6d1b7 167 cout << " Breaks:" << D.TargetPkg().FullName(false);
6c139d6e 168 else
47f6d1b7 169 cout << " Depends:" << D.TargetPkg().FullName(false);
6c139d6e 170 }
04aa15a8 171 cout << endl;
6c139d6e 172
09a10f9c 173 _error->Error("Conf Broken %s",Pkg.FullName(false).c_str());
6c139d6e
AL
174 }
175 else
b2e465d6
AL
176 {
177 cout << "Conf ";
3826564e 178 Describe(Pkg,cout,false,true);
b2e465d6 179 }
6c139d6e
AL
180
181 if (Sim.BrokenCount() != 0)
182 ShortBreaks();
183 else
04aa15a8 184 cout << endl;
6c139d6e
AL
185
186 return true;
187}
188 /*}}}*/
189// Simulate::Remove - Simulate the removal of a package /*{{{*/
190// ---------------------------------------------------------------------
191/* */
fc4b5c9f 192bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)
6c139d6e
AL
193{
194 // Adapt the iterator
803ea2a8 195 PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
c919ad6e
DK
196 if (Pkg.end() == true)
197 {
198 std::cerr << (Purge ? "Purg" : "Remv") << " invalid package " << iPkg.FullName() << std::endl;
199 return false;
200 }
6c139d6e
AL
201
202 Flags[Pkg->ID] = 3;
203 Sim.MarkDelete(Pkg);
803ea2a8 204
fc4b5c9f 205 if (Purge == true)
b2e465d6 206 cout << "Purg ";
fc4b5c9f 207 else
b2e465d6 208 cout << "Remv ";
3826564e 209 Describe(Pkg,cout,true,false);
6c139d6e
AL
210
211 if (Sim.BrokenCount() != 0)
212 ShortBreaks();
213 else
04aa15a8 214 cout << endl;
6c139d6e
AL
215
216 return true;
217}
218 /*}}}*/
219// Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
220// ---------------------------------------------------------------------
221/* */
222void pkgSimulate::ShortBreaks()
223{
04aa15a8 224 cout << " [";
f7f0d6c7 225 for (PkgIterator I = Sim.PkgBegin(); I.end() == false; ++I)
6c139d6e
AL
226 {
227 if (Sim[I].InstBroken() == true)
228 {
229 if (Flags[I->ID] == 0)
47f6d1b7 230 cout << I.FullName(false) << ' ';
6c139d6e 231/* else
04aa15a8 232 cout << I.Name() << "! ";*/
6c139d6e
AL
233 }
234 }
04aa15a8 235 cout << ']' << endl;
6c139d6e
AL
236}
237 /*}}}*/
238// ApplyStatus - Adjust for non-ok packages /*{{{*/
239// ---------------------------------------------------------------------
240/* We attempt to change the state of the all packages that have failed
241 installation toward their real state. The ordering code will perform
242 the necessary calculations to deal with the problems. */
243bool pkgApplyStatus(pkgDepCache &Cache)
244{
74a05226
MV
245 pkgDepCache::ActionGroup group(Cache);
246
f7f0d6c7 247 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
6c139d6e 248 {
e481d5b0
AL
249 if (I->VersionList == 0)
250 continue;
251
d38b7b3d
AL
252 // Only choice for a ReInstReq package is to reinstall
253 if (I->InstState == pkgCache::State::ReInstReq ||
254 I->InstState == pkgCache::State::HoldReInstReq)
255 {
5871718b 256 if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true)
74a05226 257 Cache.MarkKeep(I, false, false);
813c8eea
AL
258 else
259 {
260 // Is this right? Will dpkg choke on an upgrade?
2a3f3893
AL
261 if (Cache[I].CandidateVer != 0 &&
262 Cache[I].CandidateVerIter(Cache).Downloadable() == true)
74a05226 263 Cache.MarkInstall(I, false, 0, false);
813c8eea 264 else
b2e465d6 265 return _error->Error(_("The package %s needs to be reinstalled, "
09a10f9c 266 "but I can't find an archive for it."),I.FullName(true).c_str());
813c8eea
AL
267 }
268
d38b7b3d
AL
269 continue;
270 }
271
6c139d6e
AL
272 switch (I->CurrentState)
273 {
813c8eea
AL
274 /* This means installation failed somehow - it does not need to be
275 re-unpacked (probably) */
b518cca6
AL
276 case pkgCache::State::UnPacked:
277 case pkgCache::State::HalfConfigured:
9d06bc80
MV
278 case pkgCache::State::TriggersAwaited:
279 case pkgCache::State::TriggersPending:
5871718b 280 if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) ||
813c8eea 281 I.State() != pkgCache::PkgIterator::NeedsUnpack)
74a05226 282 Cache.MarkKeep(I, false, false);
813c8eea
AL
283 else
284 {
2a3f3893
AL
285 if (Cache[I].CandidateVer != 0 &&
286 Cache[I].CandidateVerIter(Cache).Downloadable() == true)
74a05226 287 Cache.MarkInstall(I, true, 0, false);
813c8eea 288 else
b83cad32 289 Cache.MarkDelete(I, false, 0, false);
813c8eea 290 }
6c139d6e
AL
291 break;
292
293 // This means removal failed
b518cca6 294 case pkgCache::State::HalfInstalled:
b83cad32 295 Cache.MarkDelete(I, false, 0, false);
6c139d6e
AL
296 break;
297
298 default:
b518cca6 299 if (I->InstState != pkgCache::State::Ok)
6c139d6e 300 return _error->Error("The package %s is not ok and I "
09a10f9c 301 "don't know how to fix it!",I.FullName(false).c_str());
6c139d6e
AL
302 }
303 }
304 return true;
305}
306 /*}}}*/
307// FixBroken - Fix broken packages /*{{{*/
308// ---------------------------------------------------------------------
0a8e3465
AL
309/* This autoinstalls every broken package and then runs the problem resolver
310 on the result. */
6c139d6e
AL
311bool pkgFixBroken(pkgDepCache &Cache)
312{
74a05226
MV
313 pkgDepCache::ActionGroup group(Cache);
314
6c139d6e 315 // Auto upgrade all broken packages
f7f0d6c7 316 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
6c139d6e 317 if (Cache[I].NowBroken() == true)
74a05226 318 Cache.MarkInstall(I, true, 0, false);
7e798dd7 319
6c139d6e
AL
320 /* Fix packages that are in a NeedArchive state but don't have a
321 downloadable install version */
f7f0d6c7 322 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
6c139d6e
AL
323 {
324 if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
325 Cache[I].Delete() == true)
326 continue;
327
b518cca6 328 if (Cache[I].InstVerIter(Cache).Downloadable() == false)
6c139d6e
AL
329 continue;
330
74a05226 331 Cache.MarkInstall(I, true, 0, false);
6c139d6e
AL
332 }
333
b2e465d6 334 pkgProblemResolver Fix(&Cache);
6c139d6e
AL
335 return Fix.Resolve(true);
336}
337 /*}}}*/
6c139d6e
AL
338// ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
339// ---------------------------------------------------------------------
340/* */
dcaa1185 341pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : d(NULL), Cache(*pCache)
6c139d6e
AL
342{
343 // Allocate memory
b2e465d6 344 unsigned long Size = Cache.Head().PackageCount;
d0f2c87c 345 Scores = new int[Size];
6c139d6e
AL
346 Flags = new unsigned char[Size];
347 memset(Flags,0,sizeof(*Flags)*Size);
348
349 // Set debug to true to see its decision logic
0a8e3465 350 Debug = _config->FindB("Debug::pkgProblemResolver",false);
6c139d6e
AL
351}
352 /*}}}*/
b2e465d6
AL
353// ProblemResolver::~pkgProblemResolver - Destructor /*{{{*/
354// ---------------------------------------------------------------------
355/* */
356pkgProblemResolver::~pkgProblemResolver()
357{
358 delete [] Scores;
359 delete [] Flags;
360}
361 /*}}}*/
6c139d6e
AL
362// ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
363// ---------------------------------------------------------------------
364/* */
365int pkgProblemResolver::ScoreSort(const void *a,const void *b)
366{
367 Package const **A = (Package const **)a;
368 Package const **B = (Package const **)b;
369 if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
370 return -1;
371 if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
372 return 1;
373 return 0;
374}
375 /*}}}*/
376// ProblemResolver::MakeScores - Make the score table /*{{{*/
377// ---------------------------------------------------------------------
378/* */
379void pkgProblemResolver::MakeScores()
380{
b2e465d6 381 unsigned long Size = Cache.Head().PackageCount;
6c139d6e
AL
382 memset(Scores,0,sizeof(*Scores)*Size);
383
b9179170
MV
384 // maps to pkgCache::State::VerPriority:
385 // Required Important Standard Optional Extra
d0f2c87c 386 int PrioMap[] = {
8b4894fe 387 0,
84de0cea 388 _config->FindI("pkgProblemResolver::Scores::Required",3),
b9179170 389 _config->FindI("pkgProblemResolver::Scores::Important",2),
d0f2c87c
CW
390 _config->FindI("pkgProblemResolver::Scores::Standard",1),
391 _config->FindI("pkgProblemResolver::Scores::Optional",-1),
392 _config->FindI("pkgProblemResolver::Scores::Extra",-2)
8b4894fe 393 };
d0f2c87c
CW
394 int PrioEssentials = _config->FindI("pkgProblemResolver::Scores::Essentials",100);
395 int PrioInstalledAndNotObsolete = _config->FindI("pkgProblemResolver::Scores::NotObsolete",1);
8daf68e3
DK
396 int DepMap[] = {
397 0,
398 _config->FindI("pkgProblemResolver::Scores::Depends",1),
399 _config->FindI("pkgProblemResolver::Scores::PreDepends",1),
400 _config->FindI("pkgProblemResolver::Scores::Suggests",0),
401 _config->FindI("pkgProblemResolver::Scores::Recommends",1),
402 _config->FindI("pkgProblemResolver::Scores::Conflicts",-1),
403 _config->FindI("pkgProblemResolver::Scores::Replaces",0),
404 _config->FindI("pkgProblemResolver::Scores::Obsoletes",0),
405 _config->FindI("pkgProblemResolver::Scores::Breaks",-1),
406 _config->FindI("pkgProblemResolver::Scores::Enhances",0)
407 };
d0f2c87c
CW
408 int AddProtected = _config->FindI("pkgProblemResolver::Scores::AddProtected",10000);
409 int AddEssential = _config->FindI("pkgProblemResolver::Scores::AddEssential",5000);
8b4894fe
MV
410
411 if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
412 clog << "Settings used to calculate pkgProblemResolver::Scores::" << endl
84de0cea
MV
413 << " Required => " << PrioMap[pkgCache::State::Required] << endl
414 << " Important => " << PrioMap[pkgCache::State::Important] << endl
415 << " Standard => " << PrioMap[pkgCache::State::Standard] << endl
416 << " Optional => " << PrioMap[pkgCache::State::Optional] << endl
417 << " Extra => " << PrioMap[pkgCache::State::Extra] << endl
8b4894fe
MV
418 << " Essentials => " << PrioEssentials << endl
419 << " InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete << endl
8daf68e3
DK
420 << " Pre-Depends => " << DepMap[pkgCache::Dep::PreDepends] << endl
421 << " Depends => " << DepMap[pkgCache::Dep::Depends] << endl
422 << " Recommends => " << DepMap[pkgCache::Dep::Recommends] << endl
423 << " Suggests => " << DepMap[pkgCache::Dep::Suggests] << endl
424 << " Conflicts => " << DepMap[pkgCache::Dep::Conflicts] << endl
425 << " Breaks => " << DepMap[pkgCache::Dep::DpkgBreaks] << endl
426 << " Replaces => " << DepMap[pkgCache::Dep::Replaces] << endl
427 << " Obsoletes => " << DepMap[pkgCache::Dep::Obsoletes] << endl
428 << " Enhances => " << DepMap[pkgCache::Dep::Enhances] << endl
8b4894fe
MV
429 << " AddProtected => " << AddProtected << endl
430 << " AddEssential => " << AddEssential << endl;
431
6c139d6e 432 // Generate the base scores for a package based on its properties
f7f0d6c7 433 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
6c139d6e
AL
434 {
435 if (Cache[I].InstallVer == 0)
436 continue;
437
d0f2c87c 438 int &Score = Scores[I->ID];
6c139d6e 439
7365ff46 440 /* This is arbitrary, it should be high enough to elevate an
6c139d6e
AL
441 essantial package above most other packages but low enough
442 to allow an obsolete essential packages to be removed by
1e3f4083 443 a conflicts on a powerful normal package (ie libc6) */
c5200869
JAK
444 if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential
445 || (I->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
8b4894fe 446 Score += PrioEssentials;
6c139d6e
AL
447
448 // We transform the priority
6c139d6e
AL
449 if (Cache[I].InstVerIter(Cache)->Priority <= 5)
450 Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
451
452 /* This helps to fix oddball problems with conflicting packages
4172c784
MV
453 on the same level. We enhance the score of installed packages
454 if those are not obsolete
455 */
020daa7b 456 if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
8b4894fe 457 Score += PrioInstalledAndNotObsolete;
8daf68e3 458
cb4b85b0 459 // propagate score points along dependencies
f7f0d6c7 460 for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; ++D)
9ec748ff
DK
461 {
462 if (DepMap[D->Type] == 0)
463 continue;
464 pkgCache::PkgIterator const T = D.TargetPkg();
465 if (D->Version != 0)
466 {
467 pkgCache::VerIterator const IV = Cache[T].InstVerIter(Cache);
468 if (IV.end() == true || D.IsSatisfied(IV) != D.IsNegative())
469 continue;
470 }
471 Scores[T->ID] += DepMap[D->Type];
472 }
8daf68e3
DK
473 }
474
6c139d6e 475 // Copy the scores to advoid additive looping
d0f2c87c 476 SPtrArray<int> OldScores = new int[Size];
6c139d6e
AL
477 memcpy(OldScores,Scores,sizeof(*Scores)*Size);
478
479 /* Now we cause 1 level of dependency inheritance, that is we add the
480 score of the packages that depend on the target Package. This
481 fortifies high scoring packages */
f7f0d6c7 482 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
6c139d6e
AL
483 {
484 if (Cache[I].InstallVer == 0)
485 continue;
486
f7f0d6c7 487 for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; ++D)
6c139d6e
AL
488 {
489 // Only do it for the install version
490 if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
3a998f6a
MV
491 (D->Type != pkgCache::Dep::Depends &&
492 D->Type != pkgCache::Dep::PreDepends &&
493 D->Type != pkgCache::Dep::Recommends))
6c139d6e
AL
494 continue;
495
dec5b117
MV
496 // Do not propagate negative scores otherwise
497 // an extra (-2) package might score better than an optional (-1)
498 if (OldScores[D.ParentPkg()->ID] > 0)
499 Scores[I->ID] += OldScores[D.ParentPkg()->ID];
6c139d6e
AL
500 }
501 }
502
1e3f4083 503 /* Now we propagate along provides. This makes the packages that
6c139d6e 504 provide important packages extremely important */
f7f0d6c7 505 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
6c139d6e 506 {
f7f0d6c7 507 for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; ++P)
6c139d6e
AL
508 {
509 // Only do it once per package
510 if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
511 continue;
512 Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
513 }
514 }
515
516 /* Protected things are pushed really high up. This number should put them
517 ahead of everything */
f7f0d6c7 518 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
d2685fd6 519 {
6c139d6e 520 if ((Flags[I->ID] & Protected) != 0)
8b4894fe 521 Scores[I->ID] += AddProtected;
c5200869
JAK
522 if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential ||
523 (I->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
8b4894fe
MV
524 Scores[I->ID] += AddEssential;
525 }
6c139d6e
AL
526}
527 /*}}}*/
528// ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
529// ---------------------------------------------------------------------
530/* This goes through and tries to reinstall packages to make this package
531 installable */
532bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
533{
74a05226
MV
534 pkgDepCache::ActionGroup group(Cache);
535
6c139d6e
AL
536 if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
537 return false;
3a486305
AL
538 if ((Flags[Pkg->ID] & Protected) == Protected)
539 return false;
0a8e3465 540
6c139d6e
AL
541 Flags[Pkg->ID] &= ~Upgradable;
542
543 bool WasKept = Cache[Pkg].Keep();
74a05226 544 Cache.MarkInstall(Pkg, false, 0, false);
6c139d6e 545
0a8e3465
AL
546 // This must be a virtual package or something like that.
547 if (Cache[Pkg].InstVerIter(Cache).end() == true)
548 return false;
549
6c139d6e
AL
550 // Isolate the problem dependency
551 bool Fail = false;
552 for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
553 {
554 // Compute a single dependency element (glob or)
555 pkgCache::DepIterator Start = D;
556 pkgCache::DepIterator End = D;
4b1b89c5 557 for (bool LastOR = true; D.end() == false && LastOR == true;)
6c139d6e 558 {
b518cca6 559 LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
0284eee4 560 ++D;
6c139d6e
AL
561 if (LastOR == true)
562 End = D;
563 }
564
565 // We only worry about critical deps.
566 if (End.IsCritical() != true)
567 continue;
4b1b89c5
AL
568
569 // Iterate over all the members in the or group
570 while (1)
0a8e3465 571 {
4b1b89c5
AL
572 // Dep is ok now
573 if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
574 break;
575
576 // Do not change protected packages
577 PkgIterator P = Start.SmartTargetPkg();
578 if ((Flags[P->ID] & Protected) == Protected)
579 {
580 if (Debug == true)
47f6d1b7 581 clog << " Reinst Failed because of protected " << P.FullName(false) << endl;
4b1b89c5 582 Fail = true;
4b1b89c5 583 }
648e3cb4 584 else
6c139d6e 585 {
648e3cb4
AL
586 // Upgrade the package if the candidate version will fix the problem.
587 if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
588 {
589 if (DoUpgrade(P) == false)
590 {
591 if (Debug == true)
47f6d1b7 592 clog << " Reinst Failed because of " << P.FullName(false) << endl;
648e3cb4
AL
593 Fail = true;
594 }
595 else
596 {
597 Fail = false;
598 break;
599 }
600 }
601 else
4b1b89c5 602 {
648e3cb4
AL
603 /* We let the algorithm deal with conflicts on its next iteration,
604 it is much smarter than us */
359e46db 605 if (Start.IsNegative() == true)
b2e465d6 606 break;
648e3cb4 607
4b1b89c5 608 if (Debug == true)
47f6d1b7 609 clog << " Reinst Failed early because of " << Start.TargetPkg().FullName(false) << endl;
4b1b89c5 610 Fail = true;
648e3cb4 611 }
4b1b89c5 612 }
6c139d6e 613
4b1b89c5
AL
614 if (Start == End)
615 break;
f7f0d6c7 616 ++Start;
4b1b89c5
AL
617 }
618 if (Fail == true)
6c139d6e 619 break;
6c139d6e
AL
620 }
621
622 // Undo our operations - it might be smart to undo everything this did..
623 if (Fail == true)
624 {
625 if (WasKept == true)
74a05226 626 Cache.MarkKeep(Pkg, false, false);
6c139d6e 627 else
b83cad32 628 Cache.MarkDelete(Pkg, false, 0, false);
6c139d6e
AL
629 return false;
630 }
631
632 if (Debug == true)
47f6d1b7 633 clog << " Re-Instated " << Pkg.FullName(false) << endl;
6c139d6e
AL
634 return true;
635}
636 /*}}}*/
6d38011b
DK
637// ProblemResolver::Resolve - calls a resolver to fix the situation /*{{{*/
638// ---------------------------------------------------------------------
639/* */
640bool pkgProblemResolver::Resolve(bool BrokenFix)
641{
98278a81 642 std::string const solver = _config->Find("APT::Solver", "internal");
b57c0e35
DK
643 if (solver != "internal") {
644 OpTextProgress Prog(*_config);
645 return EDSP::ResolveExternal(solver.c_str(), Cache, false, false, false, &Prog);
646 }
6d38011b
DK
647 return ResolveInternal(BrokenFix);
648}
649 /*}}}*/
650// ProblemResolver::ResolveInternal - Run the resolution pass /*{{{*/
6c139d6e
AL
651// ---------------------------------------------------------------------
652/* This routines works by calculating a score for each package. The score
653 is derived by considering the package's priority and all reverse
654 dependents giving an integer that reflects the amount of breakage that
655 adjusting the package will inflict.
656
657 It goes from highest score to lowest and corrects all of the breaks by
1e3f4083 658 keeping or removing the dependent packages. If that fails then it removes
6c139d6e
AL
659 the package itself and goes on. The routine should be able to intelligently
660 go from any broken state to a fixed state.
661
662 The BrokenFix flag enables a mode where the algorithm tries to
663 upgrade packages to advoid problems. */
6d38011b 664bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
6c139d6e 665{
74a05226
MV
666 pkgDepCache::ActionGroup group(Cache);
667
6c139d6e
AL
668 // Record which packages are marked for install
669 bool Again = false;
670 do
671 {
672 Again = false;
f7f0d6c7 673 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
6c139d6e
AL
674 {
675 if (Cache[I].Install() == true)
676 Flags[I->ID] |= PreInstalled;
677 else
678 {
679 if (Cache[I].InstBroken() == true && BrokenFix == true)
680 {
74a05226 681 Cache.MarkInstall(I, false, 0, false);
6c139d6e
AL
682 if (Cache[I].Install() == true)
683 Again = true;
684 }
685
686 Flags[I->ID] &= ~PreInstalled;
687 }
688 Flags[I->ID] |= Upgradable;
689 }
690 }
691 while (Again == true);
692
32b5dd08 693 if (Debug == true) {
49b49018
MV
694 clog << "Starting pkgProblemResolver with broken count: "
695 << Cache.BrokenCount() << endl;
32b5dd08 696 }
6c139d6e
AL
697
698 MakeScores();
6d38011b
DK
699
700 unsigned long const Size = Cache.Head().PackageCount;
701
6c139d6e
AL
702 /* We have to order the packages so that the broken fixing pass
703 operates from highest score to lowest. This prevents problems when
704 high score packages cause the removal of lower score packages that
705 would cause the removal of even lower score packages. */
b2e465d6 706 SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
6c139d6e 707 pkgCache::Package **PEnd = PList;
f7f0d6c7 708 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
6c139d6e
AL
709 *PEnd++ = I;
710 This = this;
711 qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
8b4894fe
MV
712
713 if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
714 {
715 clog << "Show Scores" << endl;
716 for (pkgCache::Package **K = PList; K != PEnd; K++)
717 if (Scores[(*K)->ID] != 0)
718 {
719 pkgCache::PkgIterator Pkg(Cache,*K);
720 clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
721 }
722 }
6c139d6e 723
32b5dd08 724 if (Debug == true) {
49b49018
MV
725 clog << "Starting 2 pkgProblemResolver with broken count: "
726 << Cache.BrokenCount() << endl;
32b5dd08 727 }
8b4894fe 728
6c139d6e
AL
729 /* Now consider all broken packages. For each broken package we either
730 remove the package or fix it's problem. We do this once, it should
731 not be possible for a loop to form (that is a < b < c and fixing b by
732 changing a breaks c) */
733 bool Change = true;
09a10f9c 734 bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
6c139d6e
AL
735 for (int Counter = 0; Counter != 10 && Change == true; Counter++)
736 {
737 Change = false;
738 for (pkgCache::Package **K = PList; K != PEnd; K++)
739 {
740 pkgCache::PkgIterator I(Cache,*K);
741
742 /* We attempt to install this and see if any breaks result,
743 this takes care of some strange cases */
744 if (Cache[I].CandidateVer != Cache[I].InstallVer &&
745 I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
746 (Flags[I->ID] & PreInstalled) != 0 &&
0a8e3465
AL
747 (Flags[I->ID] & Protected) == 0 &&
748 (Flags[I->ID] & ReInstateTried) == 0)
6c139d6e
AL
749 {
750 if (Debug == true)
09a10f9c 751 clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
a6568219 752 unsigned long OldBreaks = Cache.BrokenCount();
6c139d6e 753 pkgCache::Version *OldVer = Cache[I].InstallVer;
0a8e3465
AL
754 Flags[I->ID] &= ReInstateTried;
755
74a05226 756 Cache.MarkInstall(I, false, 0, false);
6c139d6e
AL
757 if (Cache[I].InstBroken() == true ||
758 OldBreaks < Cache.BrokenCount())
759 {
760 if (OldVer == 0)
b83cad32 761 Cache.MarkDelete(I, false, 0, false);
6c139d6e 762 else
74a05226 763 Cache.MarkKeep(I, false, false);
6c139d6e
AL
764 }
765 else
766 if (Debug == true)
47f6d1b7 767 clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
6c139d6e
AL
768 }
769
770 if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
771 continue;
772
00b47c98 773 if (Debug == true)
09a10f9c 774 clog << "Investigating (" << Counter << ") " << I << endl;
00b47c98 775
6c139d6e
AL
776 // Isolate the problem dependency
777 PackageKill KillList[100];
778 PackageKill *LEnd = KillList;
421c8d10
AL
779 bool InOr = false;
780 pkgCache::DepIterator Start;
781 pkgCache::DepIterator End;
b2e465d6 782 PackageKill *OldEnd = LEnd;
648e3cb4
AL
783
784 enum {OrRemove,OrKeep} OrOp = OrRemove;
421c8d10
AL
785 for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
786 D.end() == false || InOr == true;)
6c139d6e
AL
787 {
788 // Compute a single dependency element (glob or)
648e3cb4
AL
789 if (Start == End)
790 {
791 // Decide what to do
09a10f9c 792 if (InOr == true && OldEnd == LEnd)
648e3cb4 793 {
09a10f9c 794 if (OrOp == OrRemove)
70777d4b
AL
795 {
796 if ((Flags[I->ID] & Protected) != Protected)
00b47c98
AL
797 {
798 if (Debug == true)
47f6d1b7 799 clog << " Or group remove for " << I.FullName(false) << endl;
b83cad32 800 Cache.MarkDelete(I, false, 0, false);
cd14eaf2 801 Change = true;
09a10f9c
DK
802 }
803 }
804 else if (OrOp == OrKeep)
00b47c98
AL
805 {
806 if (Debug == true)
47f6d1b7 807 clog << " Or group keep for " << I.FullName(false) << endl;
74a05226 808 Cache.MarkKeep(I, false, false);
cd14eaf2 809 Change = true;
b2e465d6 810 }
648e3cb4
AL
811 }
812
b2e465d6
AL
813 /* We do an extra loop (as above) to finalize the or group
814 processing */
815 InOr = false;
648e3cb4 816 OrOp = OrRemove;
421c8d10 817 D.GlobOr(Start,End);
b2e465d6
AL
818 if (Start.end() == true)
819 break;
cd14eaf2 820
b2e465d6
AL
821 // We only worry about critical deps.
822 if (End.IsCritical() != true)
823 continue;
cd14eaf2 824
648e3cb4
AL
825 InOr = Start != End;
826 OldEnd = LEnd;
cd14eaf2 827 }
421c8d10 828 else
4cc152f9 829 {
f7f0d6c7 830 ++Start;
4cc152f9
MV
831 // We only worry about critical deps.
832 if (Start.IsCritical() != true)
833 continue;
834 }
cd14eaf2 835
6c139d6e
AL
836 // Dep is ok
837 if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
cd14eaf2
AL
838 {
839 InOr = false;
6c139d6e 840 continue;
cd14eaf2
AL
841 }
842
6c139d6e 843 if (Debug == true)
47f6d1b7 844 clog << "Broken " << Start << endl;
fcf85120
AL
845
846 /* Look across the version list. If there are no possible
847 targets then we keep the package and bail. This is necessary
1e3f4083 848 if a package has a dep on another package that can't be found */
b2e465d6 849 SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
fcf85120 850 if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
359e46db 851 Start.IsNegative() == false &&
fcf85120 852 Cache[I].NowBroken() == false)
648e3cb4
AL
853 {
854 if (InOr == true)
855 {
856 /* No keep choice because the keep being OK could be the
857 result of another element in the OR group! */
858 continue;
859 }
860
fcf85120 861 Change = true;
74a05226 862 Cache.MarkKeep(I, false, false);
fcf85120
AL
863 break;
864 }
865
6c139d6e
AL
866 bool Done = false;
867 for (pkgCache::Version **V = VList; *V != 0; V++)
868 {
869 pkgCache::VerIterator Ver(Cache,*V);
870 pkgCache::PkgIterator Pkg = Ver.ParentPkg();
a6bfe583 871
2ba99db8
MV
872 /* This is a conflicts, and the version we are looking
873 at is not the currently selected version of the
874 package, which means it is not necessary to
875 remove/keep */
359e46db 876 if (Cache[Pkg].InstallVer != Ver && Start.IsNegative() == true)
4429616b 877 {
2ba99db8
MV
878 if (Debug)
879 clog << " Conflicts//Breaks against version "
880 << Ver.VerStr() << " for " << Pkg.Name()
881 << " but that is not InstVer, ignoring"
24e93662 882 << endl;
2ba99db8 883 continue;
4429616b
MV
884 }
885
6c139d6e 886 if (Debug == true)
e788a834
DK
887 clog << " Considering " << Pkg.FullName(false) << ' ' << Scores[Pkg->ID] <<
888 " as a solution to " << I.FullName(false) << ' ' << Scores[I->ID] << endl;
a6bfe583
AL
889
890 /* Try to fix the package under consideration rather than
891 fiddle with the VList package */
6c139d6e 892 if (Scores[I->ID] <= Scores[Pkg->ID] ||
421c8d10 893 ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
359e46db 894 End.IsNegative() == false))
6c139d6e 895 {
200f8c52 896 // Try a little harder to fix protected packages..
3b5421b4 897 if ((Flags[I->ID] & Protected) == Protected)
200f8c52
AL
898 {
899 if (DoUpgrade(Pkg) == true)
0296c633 900 {
b2e465d6
AL
901 if (Scores[Pkg->ID] > Scores[I->ID])
902 Scores[Pkg->ID] = Scores[I->ID];
0296c633
AL
903 break;
904 }
905
6c139d6e 906 continue;
200f8c52
AL
907 }
908
909 /* See if a keep will do, unless the package is protected,
648e3cb4
AL
910 then installing it will be necessary */
911 bool Installed = Cache[I].Install();
74a05226 912 Cache.MarkKeep(I, false, false);
6c139d6e
AL
913 if (Cache[I].InstBroken() == false)
914 {
648e3cb4
AL
915 // Unwind operation will be keep now
916 if (OrOp == OrRemove)
917 OrOp = OrKeep;
918
919 // Restore
920 if (InOr == true && Installed == true)
74a05226 921 Cache.MarkInstall(I, false, 0, false);
648e3cb4 922
6c139d6e 923 if (Debug == true)
47f6d1b7 924 clog << " Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
6c139d6e
AL
925 }
926 else
421c8d10 927 {
6c139d6e
AL
928 if (BrokenFix == false || DoUpgrade(I) == false)
929 {
421c8d10 930 // Consider other options
87da7451 931 if (InOr == false || Cache[I].Garbage == true)
421c8d10 932 {
6910a2ac 933 if (Debug == true)
47f6d1b7 934 clog << " Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
b83cad32 935 Cache.MarkDelete(I, false, 0, false);
6910a2ac
DK
936 if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
937 Scores[I->ID] = Scores[Pkg->ID];
d6ebeb21 938 }
09a10f9c
DK
939 else if (TryFixByInstall == true &&
940 Start.TargetPkg()->CurrentVer == 0 &&
941 Cache[Start.TargetPkg()].Delete() == false &&
a3f1a6cc 942 (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
09a10f9c
DK
943 Cache.GetCandidateVer(Start.TargetPkg()).end() == false)
944 {
945 /* Before removing or keeping the package with the broken dependency
946 try instead to install the first not previously installed package
947 solving this dependency. This helps every time a previous solver
948 is removed by the resolver because of a conflict or alike but it is
949 dangerous as it could trigger new breaks/conflicts… */
443266ef
DK
950 if (Debug == true)
951 clog << " Try Installing " << Start.TargetPkg() << " before changing " << I.FullName(false) << std::endl;
09a10f9c
DK
952 unsigned long const OldBroken = Cache.BrokenCount();
953 Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
954 // FIXME: we should undo the complete MarkInstall process here
955 if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
956 Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
957 }
0a8e3465 958 }
6c139d6e 959 }
b5dc9785 960
6c139d6e
AL
961 Change = true;
962 Done = true;
963 break;
964 }
965 else
966 {
308c7d30
IJ
967 if (Start->Type == pkgCache::Dep::DpkgBreaks)
968 {
76264cb7
MV
969 // first, try upgradring the package, if that
970 // does not help, the breaks goes onto the
971 // kill list
2ba99db8 972 //
76264cb7 973 // FIXME: use DoUpgrade(Pkg) instead?
2ba99db8 974 if (Cache[End] & pkgDepCache::DepGCVer)
76264cb7 975 {
308c7d30 976 if (Debug)
47f6d1b7 977 clog << " Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
308c7d30
IJ
978 Cache.MarkInstall(Pkg, false, 0, false);
979 continue;
980 }
308c7d30
IJ
981 }
982
648e3cb4 983 // Skip adding to the kill list if it is protected
6c139d6e
AL
984 if ((Flags[Pkg->ID] & Protected) != 0)
985 continue;
a6bfe583
AL
986
987 if (Debug == true)
47f6d1b7 988 clog << " Added " << Pkg.FullName(false) << " to the remove list" << endl;
6c139d6e
AL
989
990 LEnd->Pkg = Pkg;
991 LEnd->Dep = End;
992 LEnd++;
0a8e3465 993
b47053bd 994 if (Start.IsNegative() == false)
6c139d6e
AL
995 break;
996 }
997 }
998
999 // Hm, nothing can possibly satisify this dep. Nuke it.
359e46db
DK
1000 if (VList[0] == 0 &&
1001 Start.IsNegative() == false &&
648e3cb4 1002 (Flags[I->ID] & Protected) != Protected)
6c139d6e 1003 {
648e3cb4 1004 bool Installed = Cache[I].Install();
6c139d6e
AL
1005 Cache.MarkKeep(I);
1006 if (Cache[I].InstBroken() == false)
1007 {
648e3cb4
AL
1008 // Unwind operation will be keep now
1009 if (OrOp == OrRemove)
1010 OrOp = OrKeep;
1011
1012 // Restore
1013 if (InOr == true && Installed == true)
74a05226 1014 Cache.MarkInstall(I, false, 0, false);
648e3cb4 1015
6c139d6e 1016 if (Debug == true)
47f6d1b7 1017 clog << " Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
6c139d6e
AL
1018 }
1019 else
1020 {
1021 if (Debug == true)
47f6d1b7 1022 clog << " Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
648e3cb4 1023 if (InOr == false)
b83cad32 1024 Cache.MarkDelete(I, false, 0, false);
6c139d6e
AL
1025 }
1026
1027 Change = true;
1028 Done = true;
1029 }
1030
421c8d10
AL
1031 // Try some more
1032 if (InOr == true)
1033 continue;
1034
6c139d6e
AL
1035 if (Done == true)
1036 break;
1037 }
1038
1039 // Apply the kill list now
1040 if (Cache[I].InstallVer != 0)
648e3cb4 1041 {
6c139d6e 1042 for (PackageKill *J = KillList; J != LEnd; J++)
6c139d6e 1043 {
648e3cb4
AL
1044 Change = true;
1045 if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1046 {
359e46db 1047 if (J->Dep.IsNegative() == true)
648e3cb4
AL
1048 {
1049 if (Debug == true)
47f6d1b7 1050 clog << " Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
b83cad32 1051 Cache.MarkDelete(J->Pkg, false, 0, false);
648e3cb4
AL
1052 }
1053 }
1054 else
6c139d6e
AL
1055 {
1056 if (Debug == true)
47f6d1b7 1057 clog << " Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
74a05226 1058 Cache.MarkKeep(J->Pkg, false, false);
6c139d6e 1059 }
b2e465d6 1060
648e3cb4 1061 if (Counter > 1)
b2e465d6
AL
1062 {
1063 if (Scores[I->ID] > Scores[J->Pkg->ID])
1064 Scores[J->Pkg->ID] = Scores[I->ID];
1065 }
648e3cb4
AL
1066 }
1067 }
1068 }
6c139d6e
AL
1069 }
1070
1071 if (Debug == true)
0a8e3465 1072 clog << "Done" << endl;
b2e465d6 1073
6c139d6e 1074 if (Cache.BrokenCount() != 0)
b5dc9785
AL
1075 {
1076 // See if this is the result of a hold
1077 pkgCache::PkgIterator I = Cache.PkgBegin();
f7f0d6c7 1078 for (;I.end() != true; ++I)
b5dc9785
AL
1079 {
1080 if (Cache[I].InstBroken() == false)
1081 continue;
1082 if ((Flags[I->ID] & Protected) != Protected)
b2e465d6 1083 return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
b5dc9785 1084 }
b2e465d6 1085 return _error->Error(_("Unable to correct problems, you have held broken packages."));
b5dc9785
AL
1086 }
1087
fce72602 1088 // set the auto-flags (mvo: I'm not sure if we _really_ need this)
80fa0d8a 1089 pkgCache::PkgIterator I = Cache.PkgBegin();
f7f0d6c7 1090 for (;I.end() != true; ++I) {
80fa0d8a 1091 if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
120365ce 1092 if(_config->FindI("Debug::pkgAutoRemove",false)) {
47f6d1b7 1093 std::clog << "Resolve installed new pkg: " << I.FullName(false)
120365ce
MV
1094 << " (now marking it as auto)" << std::endl;
1095 }
80fa0d8a
MV
1096 Cache[I].Flags |= pkgCache::Flag::Auto;
1097 }
1098 }
1099
1100
0a8e3465
AL
1101 return true;
1102}
1103 /*}}}*/
953b348c
MV
1104// ProblemResolver::BreaksInstOrPolicy - Check if the given pkg is broken/*{{{*/
1105// ---------------------------------------------------------------------
1106/* This checks if the given package is broken either by a hard dependency
1107 (InstBroken()) or by introducing a new policy breakage e.g. new
1108 unsatisfied recommends for a package that was in "policy-good" state
1109
1110 Note that this is not perfect as it will ignore further breakage
1111 for already broken policy (recommends)
1112*/
1113bool pkgProblemResolver::InstOrNewPolicyBroken(pkgCache::PkgIterator I)
1114{
953b348c
MV
1115 // a broken install is always a problem
1116 if (Cache[I].InstBroken() == true)
deec6474
DK
1117 {
1118 if (Debug == true)
1119 std::clog << " Dependencies are not satisfied for " << I << std::endl;
953b348c 1120 return true;
deec6474 1121 }
953b348c
MV
1122
1123 // a newly broken policy (recommends/suggests) is a problem
1124 if (Cache[I].NowPolicyBroken() == false &&
1125 Cache[I].InstPolicyBroken() == true)
deec6474
DK
1126 {
1127 if (Debug == true)
1128 std::clog << " Policy breaks with upgrade of " << I << std::endl;
953b348c 1129 return true;
deec6474
DK
1130 }
1131
953b348c
MV
1132 return false;
1133}
36a171e1 1134 /*}}}*/
0a8e3465
AL
1135// ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
1136// ---------------------------------------------------------------------
1137/* This is the work horse of the soft upgrade routine. It is very gental
1138 in that it does not install or remove any packages. It is assumed that the
1139 system was non-broken previously. */
1140bool pkgProblemResolver::ResolveByKeep()
741b7da9 1141{
98278a81 1142 std::string const solver = _config->Find("APT::Solver", "internal");
b57c0e35
DK
1143 if (solver != "internal") {
1144 OpTextProgress Prog(*_config);
1145 return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false, &Prog);
1146 }
741b7da9
DK
1147 return ResolveByKeepInternal();
1148}
1149 /*}}}*/
1150// ProblemResolver::ResolveByKeepInternal - Resolve problems using keep /*{{{*/
1151// ---------------------------------------------------------------------
1152/* This is the work horse of the soft upgrade routine. It is very gental
1153 in that it does not install or remove any packages. It is assumed that the
1154 system was non-broken previously. */
1155bool pkgProblemResolver::ResolveByKeepInternal()
0a8e3465 1156{
74a05226
MV
1157 pkgDepCache::ActionGroup group(Cache);
1158
b2e465d6 1159 unsigned long Size = Cache.Head().PackageCount;
0a8e3465 1160
0a8e3465
AL
1161 MakeScores();
1162
1163 /* We have to order the packages so that the broken fixing pass
1164 operates from highest score to lowest. This prevents problems when
1165 high score packages cause the removal of lower score packages that
1166 would cause the removal of even lower score packages. */
1167 pkgCache::Package **PList = new pkgCache::Package *[Size];
1168 pkgCache::Package **PEnd = PList;
f7f0d6c7 1169 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
0a8e3465
AL
1170 *PEnd++ = I;
1171 This = this;
1172 qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
8b4894fe
MV
1173
1174 if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1175 {
1176 clog << "Show Scores" << endl;
1177 for (pkgCache::Package **K = PList; K != PEnd; K++)
1178 if (Scores[(*K)->ID] != 0)
1179 {
1180 pkgCache::PkgIterator Pkg(Cache,*K);
1181 clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1182 }
1183 }
1184
1185 if (Debug == true)
1186 clog << "Entering ResolveByKeep" << endl;
1187
0a8e3465
AL
1188 // Consider each broken package
1189 pkgCache::Package **LastStop = 0;
1190 for (pkgCache::Package **K = PList; K != PEnd; K++)
1191 {
1192 pkgCache::PkgIterator I(Cache,*K);
1193
953b348c 1194 if (Cache[I].InstallVer == 0)
0a8e3465
AL
1195 continue;
1196
953b348c
MV
1197 if (InstOrNewPolicyBroken(I) == false)
1198 continue;
1199
0a8e3465 1200 /* Keep the package. If this works then great, otherwise we have
1e3f4083 1201 to be significantly more aggressive and manipulate its dependencies */
0a8e3465
AL
1202 if ((Flags[I->ID] & Protected) == 0)
1203 {
1204 if (Debug == true)
47f6d1b7 1205 clog << "Keeping package " << I.FullName(false) << endl;
74a05226 1206 Cache.MarkKeep(I, false, false);
953b348c 1207 if (InstOrNewPolicyBroken(I) == false)
0a8e3465 1208 {
b2e465d6 1209 K = PList - 1;
0a8e3465
AL
1210 continue;
1211 }
1212 }
1213
1214 // Isolate the problem dependencies
1215 for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1216 {
c5532863
AL
1217 DepIterator Start;
1218 DepIterator End;
1219 D.GlobOr(Start,End);
1220
0a8e3465
AL
1221 // We only worry about critical deps.
1222 if (End.IsCritical() != true)
1223 continue;
1224
1225 // Dep is ok
1226 if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1227 continue;
c5532863
AL
1228
1229 /* Hm, the group is broken.. I suppose the best thing to do is to
1230 is to try every combination of keep/not-keep for the set, but thats
1231 slow, and this never happens, just be conservative and assume the
1232 list of ors is in preference and keep till it starts to work. */
1233 while (true)
0a8e3465 1234 {
c5532863 1235 if (Debug == true)
47f6d1b7 1236 clog << "Package " << I.FullName(false) << " " << Start << endl;
8b4894fe 1237
c5532863
AL
1238 // Look at all the possible provides on this package
1239 SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1240 for (pkgCache::Version **V = VList; *V != 0; V++)
0a8e3465 1241 {
c5532863
AL
1242 pkgCache::VerIterator Ver(Cache,*V);
1243 pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1244
1245 // It is not keepable
1246 if (Cache[Pkg].InstallVer == 0 ||
1247 Pkg->CurrentVer == 0)
1248 continue;
1249
1250 if ((Flags[I->ID] & Protected) == 0)
1251 {
1252 if (Debug == true)
47f6d1b7 1253 clog << " Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
74a05226 1254 Cache.MarkKeep(Pkg, false, false);
c5532863
AL
1255 }
1256
953b348c 1257 if (InstOrNewPolicyBroken(I) == false)
c5532863 1258 break;
0a8e3465
AL
1259 }
1260
953b348c 1261 if (InstOrNewPolicyBroken(I) == false)
0a8e3465 1262 break;
0a8e3465 1263
c5532863
AL
1264 if (Start == End)
1265 break;
f7f0d6c7 1266 ++Start;
c5532863
AL
1267 }
1268
953b348c 1269 if (InstOrNewPolicyBroken(I) == false)
0a8e3465
AL
1270 break;
1271 }
1272
953b348c 1273 if (InstOrNewPolicyBroken(I) == true)
0a8e3465
AL
1274 continue;
1275
1276 // Restart again.
0291f645
JT
1277 if (K == LastStop) {
1278 // I is an iterator based off our temporary package list,
1279 // so copy the name we need before deleting the temporary list
1280 std::string const LoopingPackage = I.FullName(false);
1281 delete[] PList;
1282 return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.", LoopingPackage.c_str());
1283 }
0a8e3465 1284 LastStop = K;
b2e465d6 1285 K = PList - 1;
0291f645 1286 }
6c139d6e 1287
0291f645 1288 delete[] PList;
6c139d6e
AL
1289 return true;
1290}
1291 /*}}}*/
f3c736f9 1292// ProblemResolver::InstallProtect - deprecated cpu-eating no-op /*{{{*/
3b5421b4 1293// ---------------------------------------------------------------------
f3c736f9
DK
1294/* Actions issued with FromUser bit set are protected from further
1295 modification (expect by other calls with FromUser set) nowadays , so we
1296 don't need to reissue actions here, they are already set in stone. */
3b5421b4
AL
1297void pkgProblemResolver::InstallProtect()
1298{
74a05226
MV
1299 pkgDepCache::ActionGroup group(Cache);
1300
f7f0d6c7 1301 for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
3b5421b4
AL
1302 {
1303 if ((Flags[I->ID] & Protected) == Protected)
1304 {
1305 if ((Flags[I->ID] & ToRemove) == ToRemove)
1306 Cache.MarkDelete(I);
c15f5690
MV
1307 else
1308 {
da543ed8
OS
1309 // preserve the information whether the package was auto
1310 // or manually installed
c15f5690
MV
1311 bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1312 Cache.MarkInstall(I, false, 0, !autoInst);
1313 }
3b5421b4
AL
1314 }
1315 }
1316}
1317 /*}}}*/
b2e465d6
AL
1318// PrioSortList - Sort a list of versions by priority /*{{{*/
1319// ---------------------------------------------------------------------
1320/* This is ment to be used in conjunction with AllTargets to get a list
1321 of versions ordered by preference. */
1322static pkgCache *PrioCache;
1323static int PrioComp(const void *A,const void *B)
1324{
1325 pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1326 pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1327
1328 if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
b8c0f9b7
AL
1329 (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1330 return 1;
b2e465d6 1331 if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
b8c0f9b7
AL
1332 (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1333 return -1;
c5200869
JAK
1334
1335 if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important &&
1336 (R.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important)
1337 return 1;
1338 if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important &&
1339 (R.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1340 return -1;
b2e465d6
AL
1341
1342 if (L->Priority != R->Priority)
b8c0f9b7 1343 return R->Priority - L->Priority;
b2e465d6
AL
1344 return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1345}
1346void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1347{
1348 unsigned long Count = 0;
1349 PrioCache = &Cache;
1350 for (pkgCache::Version **I = List; *I != 0; I++)
1351 Count++;
1352 qsort(List,Count,sizeof(*List),PrioComp);
1353}
1354 /*}}}*/