]> git.saurik.com Git - apt.git/blob - apt-pkg/algorithms.cc
projects / apt.git / blob
? search:


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