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