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