]>
Commit | Line | Data |
---|---|---|
6c139d6e AL |
1 | // -*- mode: cpp; mode: fold -*- |
2 | // Description /*{{{*/ | |
b8c0f9b7 | 3 | // $Id: algorithms.cc,v 1.44 2002/11/28 18:49:16 jgg Exp $ |
6c139d6e AL |
4 | /* ###################################################################### |
5 | ||
6 | Algorithms - A set of misc algorithms | |
7 | ||
0a8e3465 AL |
8 | The pkgProblemResolver class has become insanely complex and |
9 | very sophisticated, it handles every test case I have thrown at it | |
10 | to my satisfaction. Understanding exactly why all the steps the class | |
11 | does are required is difficult and changing though not very risky | |
12 | may result in other cases not working. | |
13 | ||
6c139d6e AL |
14 | ##################################################################### */ |
15 | /*}}}*/ | |
16 | // Include Files /*{{{*/ | |
17 | #ifdef __GNUG__ | |
094a497d | 18 | #pragma implementation "apt-pkg/algorithms.h" |
6c139d6e | 19 | #endif |
094a497d AL |
20 | #include <apt-pkg/algorithms.h> |
21 | #include <apt-pkg/error.h> | |
0a8e3465 | 22 | #include <apt-pkg/configuration.h> |
b2e465d6 AL |
23 | #include <apt-pkg/sptr.h> |
24 | ||
25 | #include <apti18n.h> | |
26 | ||
152ab79e MV |
27 | #include <cstdlib> |
28 | #include <algorithm> | |
90f057fd | 29 | #include <iostream> |
6c139d6e | 30 | /*}}}*/ |
584e4558 | 31 | using namespace std; |
6c139d6e AL |
32 | |
33 | pkgProblemResolver *pkgProblemResolver::This = 0; | |
34 | ||
35 | // Simulate::Simulate - Constructor /*{{{*/ | |
36 | // --------------------------------------------------------------------- | |
b2e465d6 AL |
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) | |
6c139d6e | 42 | { |
b2e465d6 AL |
43 | Sim.Init(0); |
44 | Flags = new unsigned char[Cache->Head().PackageCount]; | |
45 | memset(Flags,0,sizeof(*Flags)*Cache->Head().PackageCount); | |
281daf46 AL |
46 | |
47 | // Fake a filename so as not to activate the media swapping | |
48 | string Jnk = "SIMULATE"; | |
b2e465d6 | 49 | for (unsigned int I = 0; I != Cache->Head().PackageCount; I++) |
281daf46 | 50 | FileNames[I] = Jnk; |
6c139d6e AL |
51 | } |
52 | /*}}}*/ | |
b2e465d6 AL |
53 | // Simulate::Describe - Describe a package /*{{{*/ |
54 | // --------------------------------------------------------------------- | |
b3d44315 MV |
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) | |
b2e465d6 AL |
58 | { |
59 | VerIterator Ver(Sim); | |
e59458f7 AL |
60 | |
61 | out << Pkg.Name(); | |
62 | ||
b3d44315 | 63 | if (Current == true) |
e59458f7 | 64 | { |
b2e465d6 | 65 | Ver = Pkg.CurrentVer(); |
e59458f7 AL |
66 | if (Ver.end() == false) |
67 | out << " [" << Ver.VerStr() << ']'; | |
68 | } | |
b2e465d6 | 69 | |
b3d44315 MV |
70 | if (Candidate == true) |
71 | { | |
72 | Ver = Sim[Pkg].CandidateVerIter(Sim); | |
73 | if (Ver.end() == true) | |
74 | return; | |
b2e465d6 | 75 | |
b3d44315 MV |
76 | out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')'; |
77 | } | |
b2e465d6 AL |
78 | } |
79 | /*}}}*/ | |
6c139d6e AL |
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 | ||
b2e465d6 | 89 | cout << "Inst "; |
b3d44315 | 90 | Describe(Pkg,cout,true,true); |
6c139d6e AL |
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 | ||
b2e465d6 AL |
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) | |
6c139d6e | 107 | { |
b2e465d6 | 108 | if ((Sim[End] & pkgDepCache::DepGInstall) == 0) |
6c139d6e | 109 | { |
b2e465d6 AL |
110 | cout << " [" << I.Name() << " on " << Start.TargetPkg().Name() << ']'; |
111 | if (Start->Type == pkgCache::Dep::Conflicts) | |
6c139d6e AL |
112 | _error->Error("Fatal, conflicts violated %s",I.Name()); |
113 | } | |
b2e465d6 AL |
114 | } |
115 | } | |
6c139d6e AL |
116 | } |
117 | ||
118 | if (Sim.BrokenCount() != 0) | |
119 | ShortBreaks(); | |
120 | else | |
04aa15a8 | 121 | cout << endl; |
6c139d6e AL |
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 | { | |
04aa15a8 | 139 | cout << "Conf " << Pkg.Name() << " broken" << endl; |
6c139d6e AL |
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 | ||
b2e465d6 AL |
150 | if (D->Type == pkgCache::Dep::Obsoletes) |
151 | cout << " Obsoletes:" << D.TargetPkg().Name(); | |
152 | else if (D->Type == pkgCache::Dep::Conflicts) | |
04aa15a8 | 153 | cout << " Conflicts:" << D.TargetPkg().Name(); |
6c139d6e | 154 | else |
04aa15a8 | 155 | cout << " Depends:" << D.TargetPkg().Name(); |
6c139d6e | 156 | } |
04aa15a8 | 157 | cout << endl; |
6c139d6e AL |
158 | |
159 | _error->Error("Conf Broken %s",Pkg.Name()); | |
160 | } | |
161 | else | |
b2e465d6 AL |
162 | { |
163 | cout << "Conf "; | |
b3d44315 | 164 | Describe(Pkg,cout,false,true); |
b2e465d6 | 165 | } |
6c139d6e AL |
166 | |
167 | if (Sim.BrokenCount() != 0) | |
168 | ShortBreaks(); | |
169 | else | |
04aa15a8 | 170 | cout << endl; |
6c139d6e AL |
171 | |
172 | return true; | |
173 | } | |
174 | /*}}}*/ | |
175 | // Simulate::Remove - Simulate the removal of a package /*{{{*/ | |
176 | // --------------------------------------------------------------------- | |
177 | /* */ | |
fc4b5c9f | 178 | bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge) |
6c139d6e AL |
179 | { |
180 | // Adapt the iterator | |
181 | PkgIterator Pkg = Sim.FindPkg(iPkg.Name()); | |
182 | ||
183 | Flags[Pkg->ID] = 3; | |
184 | Sim.MarkDelete(Pkg); | |
fc4b5c9f | 185 | if (Purge == true) |
b2e465d6 | 186 | cout << "Purg "; |
fc4b5c9f | 187 | else |
b2e465d6 | 188 | cout << "Remv "; |
b3d44315 | 189 | Describe(Pkg,cout,true,false); |
6c139d6e AL |
190 | |
191 | if (Sim.BrokenCount() != 0) | |
192 | ShortBreaks(); | |
193 | else | |
04aa15a8 | 194 | cout << endl; |
6c139d6e AL |
195 | |
196 | return true; | |
197 | } | |
198 | /*}}}*/ | |
199 | // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/ | |
200 | // --------------------------------------------------------------------- | |
201 | /* */ | |
202 | void pkgSimulate::ShortBreaks() | |
203 | { | |
04aa15a8 | 204 | cout << " ["; |
6c139d6e AL |
205 | for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++) |
206 | { | |
207 | if (Sim[I].InstBroken() == true) | |
208 | { | |
209 | if (Flags[I->ID] == 0) | |
04aa15a8 | 210 | cout << I.Name() << ' '; |
6c139d6e | 211 | /* else |
04aa15a8 | 212 | cout << I.Name() << "! ";*/ |
6c139d6e AL |
213 | } |
214 | } | |
04aa15a8 | 215 | cout << ']' << endl; |
6c139d6e AL |
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 | { | |
e481d5b0 AL |
227 | if (I->VersionList == 0) |
228 | continue; | |
229 | ||
d38b7b3d AL |
230 | // Only choice for a ReInstReq package is to reinstall |
231 | if (I->InstState == pkgCache::State::ReInstReq || | |
232 | I->InstState == pkgCache::State::HoldReInstReq) | |
233 | { | |
5871718b | 234 | if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) |
813c8eea AL |
235 | Cache.MarkKeep(I); |
236 | else | |
237 | { | |
238 | // Is this right? Will dpkg choke on an upgrade? | |
2a3f3893 AL |
239 | if (Cache[I].CandidateVer != 0 && |
240 | Cache[I].CandidateVerIter(Cache).Downloadable() == true) | |
813c8eea AL |
241 | Cache.MarkInstall(I); |
242 | else | |
b2e465d6 AL |
243 | return _error->Error(_("The package %s needs to be reinstalled, " |
244 | "but I can't find an archive for it."),I.Name()); | |
813c8eea AL |
245 | } |
246 | ||
d38b7b3d AL |
247 | continue; |
248 | } | |
249 | ||
6c139d6e AL |
250 | switch (I->CurrentState) |
251 | { | |
813c8eea AL |
252 | /* This means installation failed somehow - it does not need to be |
253 | re-unpacked (probably) */ | |
b518cca6 AL |
254 | case pkgCache::State::UnPacked: |
255 | case pkgCache::State::HalfConfigured: | |
5871718b | 256 | if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) || |
813c8eea AL |
257 | I.State() != pkgCache::PkgIterator::NeedsUnpack) |
258 | Cache.MarkKeep(I); | |
259 | else | |
260 | { | |
2a3f3893 AL |
261 | if (Cache[I].CandidateVer != 0 && |
262 | Cache[I].CandidateVerIter(Cache).Downloadable() == true) | |
813c8eea AL |
263 | Cache.MarkInstall(I); |
264 | else | |
265 | Cache.MarkDelete(I); | |
266 | } | |
6c139d6e AL |
267 | break; |
268 | ||
269 | // This means removal failed | |
b518cca6 | 270 | case pkgCache::State::HalfInstalled: |
6c139d6e AL |
271 | Cache.MarkDelete(I); |
272 | break; | |
273 | ||
274 | default: | |
b518cca6 | 275 | if (I->InstState != pkgCache::State::Ok) |
6c139d6e AL |
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 | // --------------------------------------------------------------------- | |
0a8e3465 AL |
285 | /* This autoinstalls every broken package and then runs the problem resolver |
286 | on the result. */ | |
6c139d6e AL |
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); | |
7e798dd7 | 293 | |
6c139d6e AL |
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 | ||
b518cca6 | 302 | if (Cache[I].InstVerIter(Cache).Downloadable() == false) |
6c139d6e AL |
303 | continue; |
304 | ||
7e798dd7 | 305 | Cache.MarkInstall(I,true); |
6c139d6e AL |
306 | } |
307 | ||
b2e465d6 | 308 | pkgProblemResolver Fix(&Cache); |
6c139d6e AL |
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 | ||
0a8e3465 | 318 | The problem resolver is used to resolve the problems. |
6c139d6e AL |
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++) | |
b518cca6 | 331 | if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) |
6c139d6e AL |
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 | ||
b2e465d6 | 340 | pkgProblemResolver Fix(&Cache); |
c88edf1d | 341 | |
6c139d6e | 342 | // Hold back held packages. |
4490f2de | 343 | if (_config->FindB("APT::Ignore-Hold",false) == false) |
6c139d6e | 344 | { |
c88edf1d | 345 | for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) |
6c139d6e | 346 | { |
c88edf1d AL |
347 | if (I->SelectedState == pkgCache::State::Hold) |
348 | { | |
349 | Fix.Protect(I); | |
350 | Cache.MarkKeep(I); | |
351 | } | |
6c139d6e AL |
352 | } |
353 | } | |
354 | ||
355 | return Fix.Resolve(); | |
356 | } | |
357 | /*}}}*/ | |
0a8e3465 AL |
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 | { | |
b2e465d6 | 365 | pkgProblemResolver Fix(&Cache); |
0a8e3465 AL |
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 | ||
b2e465d6 | 376 | if (_config->FindB("APT::Ignore-Hold",false) == false) |
c88edf1d AL |
377 | if (I->SelectedState == pkgCache::State::Hold) |
378 | continue; | |
0a8e3465 AL |
379 | |
380 | if (I->CurrentVer != 0 && Cache[I].InstallVer != 0) | |
381 | Cache.MarkInstall(I,false); | |
382 | } | |
383 | ||
384 | return Fix.ResolveByKeep(); | |
385 | } | |
386 | /*}}}*/ | |
7e798dd7 AL |
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 | ||
abc8419e | 397 | // We loop for 10 tries to get the minimal set size. |
7e798dd7 | 398 | bool Change = false; |
a005475e | 399 | unsigned int Count = 0; |
7e798dd7 AL |
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; | |
a005475e | 408 | |
7e798dd7 AL |
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 | |
a005475e AL |
414 | { |
415 | // If keep didnt actually do anything then there was no change.. | |
416 | if (Cache[I].Upgrade() == false) | |
417 | Change = true; | |
418 | } | |
7e798dd7 | 419 | } |
a005475e | 420 | Count++; |
7e798dd7 | 421 | } |
a005475e | 422 | while (Change == true && Count < 10); |
7e798dd7 AL |
423 | |
424 | if (Cache.BrokenCount() != 0) | |
425 | return _error->Error("Internal Error in pkgMinimizeUpgrade"); | |
426 | ||
427 | return true; | |
428 | } | |
429 | /*}}}*/ | |
6c139d6e AL |
430 | |
431 | // ProblemResolver::pkgProblemResolver - Constructor /*{{{*/ | |
432 | // --------------------------------------------------------------------- | |
433 | /* */ | |
b2e465d6 | 434 | pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : Cache(*pCache) |
6c139d6e AL |
435 | { |
436 | // Allocate memory | |
b2e465d6 | 437 | unsigned long Size = Cache.Head().PackageCount; |
6c139d6e AL |
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 | |
0a8e3465 | 443 | Debug = _config->FindB("Debug::pkgProblemResolver",false); |
6c139d6e AL |
444 | } |
445 | /*}}}*/ | |
b2e465d6 AL |
446 | // ProblemResolver::~pkgProblemResolver - Destructor /*{{{*/ |
447 | // --------------------------------------------------------------------- | |
448 | /* */ | |
449 | pkgProblemResolver::~pkgProblemResolver() | |
450 | { | |
451 | delete [] Scores; | |
452 | delete [] Flags; | |
453 | } | |
454 | /*}}}*/ | |
6c139d6e AL |
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 | { | |
b2e465d6 | 474 | unsigned long Size = Cache.Head().PackageCount; |
6c139d6e AL |
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) */ | |
b518cca6 | 489 | if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) |
6c139d6e AL |
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 | |
4172c784 MV |
499 | on the same level. We enhance the score of installed packages |
500 | if those are not obsolete | |
501 | */ | |
020daa7b | 502 | if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable()) |
6c139d6e AL |
503 | Score += 1; |
504 | } | |
505 | ||
506 | // Now that we have the base scores we go and propogate dependencies | |
507 | for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) | |
508 | { | |
509 | if (Cache[I].InstallVer == 0) | |
510 | continue; | |
511 | ||
512 | for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++) | |
513 | { | |
b518cca6 | 514 | if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends) |
6c139d6e AL |
515 | Scores[D.TargetPkg()->ID]++; |
516 | } | |
517 | } | |
518 | ||
519 | // Copy the scores to advoid additive looping | |
b2e465d6 | 520 | SPtrArray<signed short> OldScores = new signed short[Size]; |
6c139d6e AL |
521 | memcpy(OldScores,Scores,sizeof(*Scores)*Size); |
522 | ||
523 | /* Now we cause 1 level of dependency inheritance, that is we add the | |
524 | score of the packages that depend on the target Package. This | |
525 | fortifies high scoring packages */ | |
526 | for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) | |
527 | { | |
528 | if (Cache[I].InstallVer == 0) | |
529 | continue; | |
530 | ||
531 | for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++) | |
532 | { | |
533 | // Only do it for the install version | |
534 | if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer || | |
b518cca6 | 535 | (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends)) |
6c139d6e AL |
536 | continue; |
537 | ||
538 | Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]); | |
539 | } | |
540 | } | |
541 | ||
542 | /* Now we propogate along provides. This makes the packages that | |
543 | provide important packages extremely important */ | |
544 | for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) | |
545 | { | |
546 | for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++) | |
547 | { | |
548 | // Only do it once per package | |
549 | if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer) | |
550 | continue; | |
551 | Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]); | |
552 | } | |
553 | } | |
554 | ||
555 | /* Protected things are pushed really high up. This number should put them | |
556 | ahead of everything */ | |
557 | for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) | |
d2685fd6 | 558 | { |
6c139d6e AL |
559 | if ((Flags[I->ID] & Protected) != 0) |
560 | Scores[I->ID] += 10000; | |
d2685fd6 AL |
561 | if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) |
562 | Scores[I->ID] += 5000; | |
b2e465d6 | 563 | } |
6c139d6e AL |
564 | } |
565 | /*}}}*/ | |
566 | // ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/ | |
567 | // --------------------------------------------------------------------- | |
568 | /* This goes through and tries to reinstall packages to make this package | |
569 | installable */ | |
570 | bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg) | |
571 | { | |
572 | if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false) | |
573 | return false; | |
3a486305 AL |
574 | if ((Flags[Pkg->ID] & Protected) == Protected) |
575 | return false; | |
0a8e3465 | 576 | |
6c139d6e AL |
577 | Flags[Pkg->ID] &= ~Upgradable; |
578 | ||
579 | bool WasKept = Cache[Pkg].Keep(); | |
580 | Cache.MarkInstall(Pkg,false); | |
581 | ||
0a8e3465 AL |
582 | // This must be a virtual package or something like that. |
583 | if (Cache[Pkg].InstVerIter(Cache).end() == true) | |
584 | return false; | |
585 | ||
6c139d6e AL |
586 | // Isolate the problem dependency |
587 | bool Fail = false; | |
588 | for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;) | |
589 | { | |
590 | // Compute a single dependency element (glob or) | |
591 | pkgCache::DepIterator Start = D; | |
592 | pkgCache::DepIterator End = D; | |
593 | unsigned char State = 0; | |
4b1b89c5 | 594 | for (bool LastOR = true; D.end() == false && LastOR == true;) |
6c139d6e AL |
595 | { |
596 | State |= Cache[D]; | |
b518cca6 | 597 | LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; |
4b1b89c5 | 598 | D++; |
6c139d6e AL |
599 | if (LastOR == true) |
600 | End = D; | |
601 | } | |
602 | ||
603 | // We only worry about critical deps. | |
604 | if (End.IsCritical() != true) | |
605 | continue; | |
4b1b89c5 AL |
606 | |
607 | // Iterate over all the members in the or group | |
608 | while (1) | |
0a8e3465 | 609 | { |
4b1b89c5 AL |
610 | // Dep is ok now |
611 | if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall) | |
612 | break; | |
613 | ||
614 | // Do not change protected packages | |
615 | PkgIterator P = Start.SmartTargetPkg(); | |
616 | if ((Flags[P->ID] & Protected) == Protected) | |
617 | { | |
618 | if (Debug == true) | |
648e3cb4 | 619 | clog << " Reinst Failed because of protected " << P.Name() << endl; |
4b1b89c5 | 620 | Fail = true; |
4b1b89c5 | 621 | } |
648e3cb4 | 622 | else |
6c139d6e | 623 | { |
648e3cb4 AL |
624 | // Upgrade the package if the candidate version will fix the problem. |
625 | if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer) | |
626 | { | |
627 | if (DoUpgrade(P) == false) | |
628 | { | |
629 | if (Debug == true) | |
630 | clog << " Reinst Failed because of " << P.Name() << endl; | |
631 | Fail = true; | |
632 | } | |
633 | else | |
634 | { | |
635 | Fail = false; | |
636 | break; | |
637 | } | |
638 | } | |
639 | else | |
4b1b89c5 | 640 | { |
648e3cb4 AL |
641 | /* We let the algorithm deal with conflicts on its next iteration, |
642 | it is much smarter than us */ | |
b2e465d6 AL |
643 | if (Start->Type == pkgCache::Dep::Conflicts || |
644 | Start->Type == pkgCache::Dep::Obsoletes) | |
645 | break; | |
648e3cb4 | 646 | |
4b1b89c5 | 647 | if (Debug == true) |
648e3cb4 | 648 | clog << " Reinst Failed early because of " << Start.TargetPkg().Name() << endl; |
4b1b89c5 | 649 | Fail = true; |
648e3cb4 | 650 | } |
4b1b89c5 | 651 | } |
6c139d6e | 652 | |
4b1b89c5 AL |
653 | if (Start == End) |
654 | break; | |
655 | Start++; | |
656 | } | |
657 | if (Fail == true) | |
6c139d6e | 658 | break; |
6c139d6e AL |
659 | } |
660 | ||
661 | // Undo our operations - it might be smart to undo everything this did.. | |
662 | if (Fail == true) | |
663 | { | |
664 | if (WasKept == true) | |
665 | Cache.MarkKeep(Pkg); | |
666 | else | |
667 | Cache.MarkDelete(Pkg); | |
668 | return false; | |
669 | } | |
670 | ||
671 | if (Debug == true) | |
0a8e3465 | 672 | clog << " Re-Instated " << Pkg.Name() << endl; |
6c139d6e AL |
673 | return true; |
674 | } | |
675 | /*}}}*/ | |
676 | // ProblemResolver::Resolve - Run the resolution pass /*{{{*/ | |
677 | // --------------------------------------------------------------------- | |
678 | /* This routines works by calculating a score for each package. The score | |
679 | is derived by considering the package's priority and all reverse | |
680 | dependents giving an integer that reflects the amount of breakage that | |
681 | adjusting the package will inflict. | |
682 | ||
683 | It goes from highest score to lowest and corrects all of the breaks by | |
684 | keeping or removing the dependant packages. If that fails then it removes | |
685 | the package itself and goes on. The routine should be able to intelligently | |
686 | go from any broken state to a fixed state. | |
687 | ||
688 | The BrokenFix flag enables a mode where the algorithm tries to | |
689 | upgrade packages to advoid problems. */ | |
690 | bool pkgProblemResolver::Resolve(bool BrokenFix) | |
691 | { | |
b2e465d6 | 692 | unsigned long Size = Cache.Head().PackageCount; |
6c139d6e AL |
693 | |
694 | // Record which packages are marked for install | |
695 | bool Again = false; | |
696 | do | |
697 | { | |
698 | Again = false; | |
699 | for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) | |
700 | { | |
701 | if (Cache[I].Install() == true) | |
702 | Flags[I->ID] |= PreInstalled; | |
703 | else | |
704 | { | |
705 | if (Cache[I].InstBroken() == true && BrokenFix == true) | |
706 | { | |
707 | Cache.MarkInstall(I,false); | |
708 | if (Cache[I].Install() == true) | |
709 | Again = true; | |
710 | } | |
711 | ||
712 | Flags[I->ID] &= ~PreInstalled; | |
713 | } | |
714 | Flags[I->ID] |= Upgradable; | |
715 | } | |
716 | } | |
717 | while (Again == true); | |
718 | ||
719 | if (Debug == true) | |
0a8e3465 | 720 | clog << "Starting" << endl; |
6c139d6e AL |
721 | |
722 | MakeScores(); | |
723 | ||
724 | /* We have to order the packages so that the broken fixing pass | |
725 | operates from highest score to lowest. This prevents problems when | |
726 | high score packages cause the removal of lower score packages that | |
727 | would cause the removal of even lower score packages. */ | |
b2e465d6 | 728 | SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size]; |
6c139d6e AL |
729 | pkgCache::Package **PEnd = PList; |
730 | for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) | |
731 | *PEnd++ = I; | |
732 | This = this; | |
733 | qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort); | |
734 | ||
735 | /* for (pkgCache::Package **K = PList; K != PEnd; K++) | |
736 | if (Scores[(*K)->ID] != 0) | |
737 | { | |
738 | pkgCache::PkgIterator Pkg(Cache,*K); | |
0a8e3465 | 739 | clog << Scores[(*K)->ID] << ' ' << Pkg.Name() << |
6c139d6e AL |
740 | ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' << |
741 | Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl; | |
742 | } */ | |
743 | ||
744 | if (Debug == true) | |
0a8e3465 | 745 | clog << "Starting 2" << endl; |
6c139d6e AL |
746 | |
747 | /* Now consider all broken packages. For each broken package we either | |
748 | remove the package or fix it's problem. We do this once, it should | |
749 | not be possible for a loop to form (that is a < b < c and fixing b by | |
750 | changing a breaks c) */ | |
751 | bool Change = true; | |
752 | for (int Counter = 0; Counter != 10 && Change == true; Counter++) | |
753 | { | |
754 | Change = false; | |
755 | for (pkgCache::Package **K = PList; K != PEnd; K++) | |
756 | { | |
757 | pkgCache::PkgIterator I(Cache,*K); | |
758 | ||
759 | /* We attempt to install this and see if any breaks result, | |
760 | this takes care of some strange cases */ | |
761 | if (Cache[I].CandidateVer != Cache[I].InstallVer && | |
762 | I->CurrentVer != 0 && Cache[I].InstallVer != 0 && | |
763 | (Flags[I->ID] & PreInstalled) != 0 && | |
0a8e3465 AL |
764 | (Flags[I->ID] & Protected) == 0 && |
765 | (Flags[I->ID] & ReInstateTried) == 0) | |
6c139d6e AL |
766 | { |
767 | if (Debug == true) | |
0a8e3465 | 768 | clog << " Try to Re-Instate " << I.Name() << endl; |
a6568219 | 769 | unsigned long OldBreaks = Cache.BrokenCount(); |
6c139d6e | 770 | pkgCache::Version *OldVer = Cache[I].InstallVer; |
0a8e3465 AL |
771 | Flags[I->ID] &= ReInstateTried; |
772 | ||
6c139d6e AL |
773 | Cache.MarkInstall(I,false); |
774 | if (Cache[I].InstBroken() == true || | |
775 | OldBreaks < Cache.BrokenCount()) | |
776 | { | |
777 | if (OldVer == 0) | |
778 | Cache.MarkDelete(I); | |
779 | else | |
780 | Cache.MarkKeep(I); | |
781 | } | |
782 | else | |
783 | if (Debug == true) | |
0a8e3465 | 784 | clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl; |
6c139d6e AL |
785 | } |
786 | ||
787 | if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false) | |
788 | continue; | |
789 | ||
00b47c98 | 790 | if (Debug == true) |
d2de5a76 | 791 | clog << "Investigating " << I.Name() << endl; |
00b47c98 | 792 | |
6c139d6e AL |
793 | // Isolate the problem dependency |
794 | PackageKill KillList[100]; | |
795 | PackageKill *LEnd = KillList; | |
421c8d10 AL |
796 | bool InOr = false; |
797 | pkgCache::DepIterator Start; | |
798 | pkgCache::DepIterator End; | |
b2e465d6 | 799 | PackageKill *OldEnd = LEnd; |
648e3cb4 AL |
800 | |
801 | enum {OrRemove,OrKeep} OrOp = OrRemove; | |
421c8d10 AL |
802 | for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); |
803 | D.end() == false || InOr == true;) | |
6c139d6e AL |
804 | { |
805 | // Compute a single dependency element (glob or) | |
648e3cb4 AL |
806 | if (Start == End) |
807 | { | |
808 | // Decide what to do | |
809 | if (InOr == true) | |
810 | { | |
811 | if (OldEnd == LEnd && OrOp == OrRemove) | |
70777d4b AL |
812 | { |
813 | if ((Flags[I->ID] & Protected) != Protected) | |
00b47c98 AL |
814 | { |
815 | if (Debug == true) | |
816 | clog << " Or group remove for " << I.Name() << endl; | |
70777d4b | 817 | Cache.MarkDelete(I); |
cd14eaf2 | 818 | Change = true; |
00b47c98 | 819 | } |
70777d4b | 820 | } |
648e3cb4 | 821 | if (OldEnd == LEnd && OrOp == OrKeep) |
00b47c98 AL |
822 | { |
823 | if (Debug == true) | |
824 | clog << " Or group keep for " << I.Name() << endl; | |
648e3cb4 | 825 | Cache.MarkKeep(I); |
cd14eaf2 | 826 | Change = true; |
b2e465d6 | 827 | } |
648e3cb4 AL |
828 | } |
829 | ||
b2e465d6 AL |
830 | /* We do an extra loop (as above) to finalize the or group |
831 | processing */ | |
832 | InOr = false; | |
648e3cb4 | 833 | OrOp = OrRemove; |
421c8d10 | 834 | D.GlobOr(Start,End); |
b2e465d6 AL |
835 | if (Start.end() == true) |
836 | break; | |
cd14eaf2 | 837 | |
b2e465d6 AL |
838 | // We only worry about critical deps. |
839 | if (End.IsCritical() != true) | |
840 | continue; | |
cd14eaf2 | 841 | |
648e3cb4 AL |
842 | InOr = Start != End; |
843 | OldEnd = LEnd; | |
cd14eaf2 | 844 | } |
421c8d10 | 845 | else |
4cc152f9 | 846 | { |
421c8d10 | 847 | Start++; |
4cc152f9 MV |
848 | // We only worry about critical deps. |
849 | if (Start.IsCritical() != true) | |
850 | continue; | |
851 | } | |
cd14eaf2 | 852 | |
6c139d6e AL |
853 | // Dep is ok |
854 | if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall) | |
cd14eaf2 AL |
855 | { |
856 | InOr = false; | |
6c139d6e | 857 | continue; |
cd14eaf2 AL |
858 | } |
859 | ||
6c139d6e | 860 | if (Debug == true) |
421c8d10 | 861 | clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl; |
fcf85120 AL |
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 */ | |
b2e465d6 | 866 | SPtrArray<pkgCache::Version *> VList = Start.AllTargets(); |
fcf85120 | 867 | if (*VList == 0 && (Flags[I->ID] & Protected) != Protected && |
648e3cb4 | 868 | Start->Type != pkgCache::Dep::Conflicts && |
b2e465d6 | 869 | Start->Type != pkgCache::Dep::Obsoletes && |
fcf85120 | 870 | Cache[I].NowBroken() == false) |
648e3cb4 AL |
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 | ||
fcf85120 | 879 | Change = true; |
648e3cb4 | 880 | Cache.MarkKeep(I); |
fcf85120 AL |
881 | break; |
882 | } | |
883 | ||
6c139d6e AL |
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(); | |
a6bfe583 | 889 | |
6c139d6e | 890 | if (Debug == true) |
421c8d10 | 891 | clog << " Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] << |
6c139d6e | 892 | " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl; |
a6bfe583 AL |
893 | |
894 | /* Try to fix the package under consideration rather than | |
895 | fiddle with the VList package */ | |
6c139d6e | 896 | if (Scores[I->ID] <= Scores[Pkg->ID] || |
421c8d10 | 897 | ((Cache[Start] & pkgDepCache::DepNow) == 0 && |
b2e465d6 AL |
898 | End->Type != pkgCache::Dep::Conflicts && |
899 | End->Type != pkgCache::Dep::Obsoletes)) | |
6c139d6e | 900 | { |
200f8c52 | 901 | // Try a little harder to fix protected packages.. |
3b5421b4 | 902 | if ((Flags[I->ID] & Protected) == Protected) |
200f8c52 AL |
903 | { |
904 | if (DoUpgrade(Pkg) == true) | |
0296c633 | 905 | { |
b2e465d6 AL |
906 | if (Scores[Pkg->ID] > Scores[I->ID]) |
907 | Scores[Pkg->ID] = Scores[I->ID]; | |
0296c633 AL |
908 | break; |
909 | } | |
910 | ||
6c139d6e | 911 | continue; |
200f8c52 AL |
912 | } |
913 | ||
914 | /* See if a keep will do, unless the package is protected, | |
648e3cb4 AL |
915 | then installing it will be necessary */ |
916 | bool Installed = Cache[I].Install(); | |
6c139d6e AL |
917 | Cache.MarkKeep(I); |
918 | if (Cache[I].InstBroken() == false) | |
919 | { | |
648e3cb4 AL |
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 | ||
6c139d6e | 928 | if (Debug == true) |
421c8d10 | 929 | clog << " Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl; |
6c139d6e AL |
930 | } |
931 | else | |
421c8d10 | 932 | { |
6c139d6e AL |
933 | if (BrokenFix == false || DoUpgrade(I) == false) |
934 | { | |
421c8d10 AL |
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) | |
b2e465d6 AL |
942 | { |
943 | if (Scores[Pkg->ID] > Scores[I->ID]) | |
944 | Scores[I->ID] = Scores[Pkg->ID]; | |
945 | } | |
421c8d10 | 946 | } |
0a8e3465 | 947 | } |
6c139d6e | 948 | } |
b5dc9785 | 949 | |
6c139d6e AL |
950 | Change = true; |
951 | Done = true; | |
952 | break; | |
953 | } | |
954 | else | |
955 | { | |
a6bfe583 AL |
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 | ||
648e3cb4 | 965 | // Skip adding to the kill list if it is protected |
6c139d6e AL |
966 | if ((Flags[Pkg->ID] & Protected) != 0) |
967 | continue; | |
a6bfe583 AL |
968 | |
969 | if (Debug == true) | |
970 | clog << " Added " << Pkg.Name() << " to the remove list" << endl; | |
6c139d6e AL |
971 | |
972 | LEnd->Pkg = Pkg; | |
973 | LEnd->Dep = End; | |
974 | LEnd++; | |
0a8e3465 | 975 | |
b2e465d6 AL |
976 | if (Start->Type != pkgCache::Dep::Conflicts && |
977 | Start->Type != pkgCache::Dep::Obsoletes) | |
6c139d6e AL |
978 | break; |
979 | } | |
980 | } | |
981 | ||
982 | // Hm, nothing can possibly satisify this dep. Nuke it. | |
b2e465d6 AL |
983 | if (VList[0] == 0 && |
984 | Start->Type != pkgCache::Dep::Conflicts && | |
985 | Start->Type != pkgCache::Dep::Obsoletes && | |
648e3cb4 | 986 | (Flags[I->ID] & Protected) != Protected) |
6c139d6e | 987 | { |
648e3cb4 | 988 | bool Installed = Cache[I].Install(); |
6c139d6e AL |
989 | Cache.MarkKeep(I); |
990 | if (Cache[I].InstBroken() == false) | |
991 | { | |
648e3cb4 AL |
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 | ||
6c139d6e | 1000 | if (Debug == true) |
421c8d10 | 1001 | clog << " Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl; |
6c139d6e AL |
1002 | } |
1003 | else | |
1004 | { | |
1005 | if (Debug == true) | |
421c8d10 | 1006 | clog << " Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl; |
648e3cb4 AL |
1007 | if (InOr == false) |
1008 | Cache.MarkDelete(I); | |
6c139d6e AL |
1009 | } |
1010 | ||
1011 | Change = true; | |
1012 | Done = true; | |
1013 | } | |
1014 | ||
421c8d10 AL |
1015 | // Try some more |
1016 | if (InOr == true) | |
1017 | continue; | |
1018 | ||
6c139d6e AL |
1019 | if (Done == true) |
1020 | break; | |
1021 | } | |
1022 | ||
1023 | // Apply the kill list now | |
1024 | if (Cache[I].InstallVer != 0) | |
648e3cb4 | 1025 | { |
6c139d6e | 1026 | for (PackageKill *J = KillList; J != LEnd; J++) |
6c139d6e | 1027 | { |
648e3cb4 AL |
1028 | Change = true; |
1029 | if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0) | |
1030 | { | |
b2e465d6 AL |
1031 | if (J->Dep->Type == pkgCache::Dep::Conflicts || |
1032 | J->Dep->Type == pkgCache::Dep::Obsoletes) | |
648e3cb4 AL |
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 | |
6c139d6e AL |
1040 | { |
1041 | if (Debug == true) | |
648e3cb4 AL |
1042 | clog << " Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl; |
1043 | Cache.MarkKeep(J->Pkg); | |
6c139d6e | 1044 | } |
b2e465d6 | 1045 | |
648e3cb4 | 1046 | if (Counter > 1) |
b2e465d6 AL |
1047 | { |
1048 | if (Scores[I->ID] > Scores[J->Pkg->ID]) | |
1049 | Scores[J->Pkg->ID] = Scores[I->ID]; | |
1050 | } | |
648e3cb4 AL |
1051 | } |
1052 | } | |
1053 | } | |
6c139d6e AL |
1054 | } |
1055 | ||
1056 | if (Debug == true) | |
0a8e3465 | 1057 | clog << "Done" << endl; |
b2e465d6 | 1058 | |
6c139d6e | 1059 | if (Cache.BrokenCount() != 0) |
b5dc9785 AL |
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) | |
b2e465d6 | 1068 | return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.")); |
b5dc9785 | 1069 | } |
b2e465d6 | 1070 | return _error->Error(_("Unable to correct problems, you have held broken packages.")); |
b5dc9785 AL |
1071 | } |
1072 | ||
0a8e3465 AL |
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 | { | |
b2e465d6 | 1083 | unsigned long Size = Cache.Head().PackageCount; |
0a8e3465 AL |
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 | |
b2e465d6 | 1111 | to be significantly more agressive and manipulate its dependencies */ |
0a8e3465 AL |
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 | { | |
b2e465d6 | 1119 | K = PList - 1; |
0a8e3465 AL |
1120 | continue; |
1121 | } | |
1122 | } | |
1123 | ||
1124 | // Isolate the problem dependencies | |
1125 | for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;) | |
1126 | { | |
c5532863 AL |
1127 | DepIterator Start; |
1128 | DepIterator End; | |
1129 | D.GlobOr(Start,End); | |
1130 | ||
0a8e3465 AL |
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; | |
c5532863 AL |
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) | |
0a8e3465 | 1144 | { |
c5532863 AL |
1145 | if (Debug == true) |
1146 | clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl; | |
0a8e3465 | 1147 | |
c5532863 AL |
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++) | |
0a8e3465 | 1151 | { |
c5532863 AL |
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; | |
0a8e3465 AL |
1169 | } |
1170 | ||
1171 | if (Cache[I].InstBroken() == false) | |
1172 | break; | |
0a8e3465 | 1173 | |
c5532863 AL |
1174 | if (Start == End) |
1175 | break; | |
1176 | Start++; | |
1177 | } | |
1178 | ||
0a8e3465 AL |
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; | |
b2e465d6 | 1190 | K = PList - 1; |
0a8e3465 | 1191 | } |
6c139d6e AL |
1192 | |
1193 | return true; | |
1194 | } | |
1195 | /*}}}*/ | |
3b5421b4 AL |
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 | /*}}}*/ | |
b2e465d6 AL |
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 && | |
b8c0f9b7 AL |
1225 | (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential) |
1226 | return 1; | |
b2e465d6 | 1227 | if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential && |
b8c0f9b7 AL |
1228 | (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) |
1229 | return -1; | |
b2e465d6 AL |
1230 | |
1231 | if (L->Priority != R->Priority) | |
b8c0f9b7 | 1232 | return R->Priority - L->Priority; |
b2e465d6 AL |
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 | /*}}}*/ |