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