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