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