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