]>
Commit | Line | Data |
---|---|---|
1 | // -*- mode: cpp; mode: fold -*- | |
2 | // Description /*{{{*/ | |
3 | // $Id: orderlist.cc,v 1.14 2001/05/07 05:49:43 jgg Exp $ | |
4 | /* ###################################################################### | |
5 | ||
6 | Order List - Represents and Manipulates an ordered list of packages. | |
7 | ||
8 | A list of packages can be ordered by a number of conflicting criteria | |
9 | each given a specific priority. Each package also has a set of flags | |
10 | indicating some useful things about it that are derived in the | |
11 | course of sorting. The pkgPackageManager class uses this class for | |
12 | all of it's installation ordering needs. | |
13 | ||
14 | This is a modified version of Manoj's Routine B. It consists of four | |
15 | independent ordering algorithms that can be applied at for different | |
16 | points in the ordering. By appling progressivly fewer ordering | |
17 | operations it is possible to give each consideration it's own | |
18 | priority and create an order that satisfies the lowest applicable | |
19 | consideration. | |
20 | ||
21 | The rules for unpacking ordering are: | |
22 | 1) Unpacking ignores Depends: on all packages | |
23 | 2) Unpacking requires Conflicts: on -ALL- packages to be satisfied | |
24 | 3) Unpacking requires PreDepends: on this package only to be satisfied | |
25 | 4) Removing requires that no packages depend on the package to be | |
26 | removed. | |
27 | ||
28 | And the rule for configuration ordering is: | |
29 | 1) Configuring requires that the Depends: of the package be satisfied | |
30 | Conflicts+PreDepends are ignored because unpacking says they are | |
31 | already correct [exageration, it does check but we need not be | |
32 | concerned] | |
33 | ||
34 | And some features that are valuable for unpacking ordering. | |
35 | f1) Unpacking a new package should advoid breaking dependencies of | |
36 | configured packages | |
37 | f2) Removal should not require a force, corrolory of f1 | |
38 | f3) Unpacking should order by depends rather than fall back to random | |
39 | ordering. | |
40 | ||
41 | Each of the features can be enabled in the sorting routine at an | |
42 | arbitrary priority to give quite abit of control over the final unpacking | |
43 | order. | |
44 | ||
45 | The rules listed above may never be violated and are called Critical. | |
46 | When a critical rule is violated then a loop condition is recorded | |
47 | and will have to be delt with in the caller. | |
48 | ||
49 | The ordering keeps two lists, the main list and the 'After List'. The | |
50 | purpose of the after list is to allow packages to be delayed. This is done | |
51 | by setting the after flag on the package. Any package which requires this | |
52 | package to be ordered before will inherit the after flag and so on. This | |
53 | is used for CD swap ordering where all packages on a second CD have the | |
54 | after flag set. This forces them and all their dependents to be ordered | |
55 | toward the end. | |
56 | ||
57 | There are complications in this algorithm when presented with cycles. | |
58 | For all known practical cases it works, all cases where it doesn't work | |
59 | is fixable by tweaking the package descriptions. However, it should be | |
60 | possible to impove this further to make some better choices when | |
61 | presented with cycles. | |
62 | ||
63 | ##################################################################### */ | |
64 | /*}}}*/ | |
65 | // Include Files /*{{{*/ | |
66 | #include <apt-pkg/orderlist.h> | |
67 | #include <apt-pkg/depcache.h> | |
68 | #include <apt-pkg/error.h> | |
69 | #include <apt-pkg/version.h> | |
70 | #include <apt-pkg/sptr.h> | |
71 | #include <apt-pkg/configuration.h> | |
72 | ||
73 | #include <iostream> | |
74 | /*}}}*/ | |
75 | ||
76 | using namespace std; | |
77 | ||
78 | pkgOrderList *pkgOrderList::Me = 0; | |
79 | ||
80 | // OrderList::pkgOrderList - Constructor /*{{{*/ | |
81 | // --------------------------------------------------------------------- | |
82 | /* */ | |
83 | pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache) | |
84 | { | |
85 | FileList = 0; | |
86 | Primary = 0; | |
87 | Secondary = 0; | |
88 | RevDepends = 0; | |
89 | Remove = 0; | |
90 | LoopCount = -1; | |
91 | Debug = _config->FindB("Debug::pkgOrderList",false); | |
92 | ||
93 | /* Construct the arrays, egcs 1.0.1 bug requires the package count | |
94 | hack */ | |
95 | unsigned long Size = Cache.Head().PackageCount; | |
96 | Flags = new unsigned short[Size]; | |
97 | End = List = new Package *[Size]; | |
98 | memset(Flags,0,sizeof(*Flags)*Size); | |
99 | } | |
100 | /*}}}*/ | |
101 | // OrderList::~pkgOrderList - Destructor /*{{{*/ | |
102 | // --------------------------------------------------------------------- | |
103 | /* */ | |
104 | pkgOrderList::~pkgOrderList() | |
105 | { | |
106 | delete [] List; | |
107 | delete [] Flags; | |
108 | } | |
109 | /*}}}*/ | |
110 | // OrderList::IsMissing - Check if a file is missing /*{{{*/ | |
111 | // --------------------------------------------------------------------- | |
112 | /* */ | |
113 | bool pkgOrderList::IsMissing(PkgIterator Pkg) | |
114 | { | |
115 | // Skip packages to erase | |
116 | if (Cache[Pkg].Delete() == true) | |
117 | return false; | |
118 | ||
119 | // Skip Packages that need configure only. | |
120 | if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure && | |
121 | Cache[Pkg].Keep() == true) | |
122 | return false; | |
123 | ||
124 | if (FileList == 0) | |
125 | return false; | |
126 | ||
127 | if (FileList[Pkg->ID].empty() == false) | |
128 | return false; | |
129 | ||
130 | // Missing Pseudo packages are missing if the real package is missing | |
131 | if (pkgCache::VerIterator(Cache, Cache[Pkg].CandidateVer).Pseudo() == true) | |
132 | return IsMissing(Pkg.Group().FindPkg("all")); | |
133 | ||
134 | return true; | |
135 | } | |
136 | /*}}}*/ | |
137 | // OrderList::DoRun - Does an order run /*{{{*/ | |
138 | // --------------------------------------------------------------------- | |
139 | /* The caller is expeted to have setup the desired probe state */ | |
140 | bool pkgOrderList::DoRun() | |
141 | { | |
142 | // Temp list | |
143 | unsigned long Size = Cache.Head().PackageCount; | |
144 | SPtrArray<Package *> NList = new Package *[Size]; | |
145 | SPtrArray<Package *> AfterList = new Package *[Size]; | |
146 | AfterEnd = AfterList; | |
147 | ||
148 | Depth = 0; | |
149 | WipeFlags(Added | AddPending | Loop | InList); | |
150 | ||
151 | for (iterator I = List; I != End; I++) | |
152 | Flag(*I,InList); | |
153 | ||
154 | // Rebuild the main list into the temp list. | |
155 | iterator OldEnd = End; | |
156 | End = NList; | |
157 | for (iterator I = List; I != OldEnd; I++) | |
158 | if (VisitNode(PkgIterator(Cache,*I)) == false) | |
159 | { | |
160 | End = OldEnd; | |
161 | return false; | |
162 | } | |
163 | ||
164 | // Copy the after list to the end of the main list | |
165 | for (Package **I = AfterList; I != AfterEnd; I++) | |
166 | *End++ = *I; | |
167 | ||
168 | // Swap the main list to the new list | |
169 | delete [] List; | |
170 | List = NList.UnGuard(); | |
171 | return true; | |
172 | } | |
173 | /*}}}*/ | |
174 | // OrderList::OrderCritical - Perform critical unpacking ordering /*{{{*/ | |
175 | // --------------------------------------------------------------------- | |
176 | /* This performs predepends and immediate configuration ordering only. | |
177 | This is termed critical unpacking ordering. Any loops that form are | |
178 | fatal and indicate that the packages cannot be installed. */ | |
179 | bool pkgOrderList::OrderCritical() | |
180 | { | |
181 | FileList = 0; | |
182 | ||
183 | Primary = &pkgOrderList::DepUnPackPreD; | |
184 | Secondary = 0; | |
185 | RevDepends = 0; | |
186 | Remove = 0; | |
187 | LoopCount = 0; | |
188 | ||
189 | // Sort | |
190 | Me = this; | |
191 | qsort(List,End - List,sizeof(*List),&OrderCompareB); | |
192 | ||
193 | if (DoRun() == false) | |
194 | return false; | |
195 | ||
196 | if (LoopCount != 0) | |
197 | return _error->Error("Fatal, predepends looping detected"); | |
198 | ||
199 | if (Debug == true) | |
200 | { | |
201 | clog << "** Critical Unpack ordering done" << endl; | |
202 | ||
203 | for (iterator I = List; I != End; I++) | |
204 | { | |
205 | PkgIterator P(Cache,*I); | |
206 | if (IsNow(P) == true) | |
207 | clog << " " << P.FullName() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl; | |
208 | } | |
209 | } | |
210 | ||
211 | return true; | |
212 | } | |
213 | /*}}}*/ | |
214 | // OrderList::OrderUnpack - Perform complete unpacking ordering /*{{{*/ | |
215 | // --------------------------------------------------------------------- | |
216 | /* This performs complete unpacking ordering and creates an order that is | |
217 | suitable for unpacking */ | |
218 | bool pkgOrderList::OrderUnpack(string *FileList) | |
219 | { | |
220 | this->FileList = FileList; | |
221 | ||
222 | // Setup the after flags | |
223 | if (FileList != 0) | |
224 | { | |
225 | WipeFlags(After); | |
226 | ||
227 | // Set the inlist flag | |
228 | for (iterator I = List; I != End; I++) | |
229 | { | |
230 | PkgIterator P(Cache,*I); | |
231 | if (IsMissing(P) == true && IsNow(P) == true) | |
232 | Flag(*I,After); | |
233 | } | |
234 | } | |
235 | ||
236 | Primary = &pkgOrderList::DepUnPackCrit; | |
237 | Secondary = &pkgOrderList::DepConfigure; | |
238 | RevDepends = &pkgOrderList::DepUnPackDep; | |
239 | Remove = &pkgOrderList::DepRemove; | |
240 | LoopCount = -1; | |
241 | ||
242 | // Sort | |
243 | Me = this; | |
244 | qsort(List,End - List,sizeof(*List),&OrderCompareA); | |
245 | ||
246 | if (Debug == true) | |
247 | clog << "** Pass A" << endl; | |
248 | if (DoRun() == false) | |
249 | return false; | |
250 | ||
251 | if (Debug == true) | |
252 | clog << "** Pass B" << endl; | |
253 | Secondary = 0; | |
254 | if (DoRun() == false) | |
255 | return false; | |
256 | ||
257 | if (Debug == true) | |
258 | clog << "** Pass C" << endl; | |
259 | LoopCount = 0; | |
260 | RevDepends = 0; | |
261 | Remove = 0; // Otherwise the libreadline remove problem occures | |
262 | if (DoRun() == false) | |
263 | return false; | |
264 | ||
265 | if (Debug == true) | |
266 | clog << "** Pass D" << endl; | |
267 | LoopCount = 0; | |
268 | Primary = &pkgOrderList::DepUnPackPre; | |
269 | if (DoRun() == false) | |
270 | return false; | |
271 | ||
272 | if (Debug == true) | |
273 | { | |
274 | clog << "** Unpack ordering done" << endl; | |
275 | ||
276 | for (iterator I = List; I != End; I++) | |
277 | { | |
278 | PkgIterator P(Cache,*I); | |
279 | if (IsNow(P) == true) | |
280 | clog << " " << P.FullName() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl; | |
281 | } | |
282 | } | |
283 | ||
284 | return true; | |
285 | } | |
286 | /*}}}*/ | |
287 | // OrderList::OrderConfigure - Perform configuration ordering /*{{{*/ | |
288 | // --------------------------------------------------------------------- | |
289 | /* This orders by depends only and produces an order which is suitable | |
290 | for configuration */ | |
291 | bool pkgOrderList::OrderConfigure() | |
292 | { | |
293 | FileList = 0; | |
294 | Primary = &pkgOrderList::DepConfigure; | |
295 | Secondary = 0; | |
296 | RevDepends = 0; | |
297 | Remove = 0; | |
298 | LoopCount = -1; | |
299 | return DoRun(); | |
300 | } | |
301 | /*}}}*/ | |
302 | // OrderList::Score - Score the package for sorting /*{{{*/ | |
303 | // --------------------------------------------------------------------- | |
304 | /* Higher scores order earlier */ | |
305 | int pkgOrderList::Score(PkgIterator Pkg) | |
306 | { | |
307 | static int const ScoreDelete = _config->FindI("OrderList::Score::Delete", 500); | |
308 | ||
309 | // Removal is always done first | |
310 | if (Cache[Pkg].Delete() == true) | |
311 | return ScoreDelete; | |
312 | ||
313 | // This should never happen.. | |
314 | if (Cache[Pkg].InstVerIter(Cache).end() == true) | |
315 | return -1; | |
316 | ||
317 | static int const ScoreEssential = _config->FindI("OrderList::Score::Essential", 200); | |
318 | static int const ScoreImmediate = _config->FindI("OrderList::Score::Immediate", 10); | |
319 | static int const ScorePreDepends = _config->FindI("OrderList::Score::PreDepends", 50); | |
320 | ||
321 | int Score = 0; | |
322 | if ((Pkg->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) | |
323 | Score += ScoreEssential; | |
324 | ||
325 | if (IsFlag(Pkg,Immediate) == true) | |
326 | Score += ScoreImmediate; | |
327 | ||
328 | for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); | |
329 | D.end() == false; D++) | |
330 | if (D->Type == pkgCache::Dep::PreDepends) | |
331 | { | |
332 | Score += ScorePreDepends; | |
333 | break; | |
334 | } | |
335 | ||
336 | // Important Required Standard Optional Extra | |
337 | signed short PrioMap[] = {0,5,4,3,1,0}; | |
338 | if (Cache[Pkg].InstVerIter(Cache)->Priority <= 5) | |
339 | Score += PrioMap[Cache[Pkg].InstVerIter(Cache)->Priority]; | |
340 | return Score; | |
341 | } | |
342 | /*}}}*/ | |
343 | // OrderList::FileCmp - Compare by package file /*{{{*/ | |
344 | // --------------------------------------------------------------------- | |
345 | /* This compares by the package file that the install version is in. */ | |
346 | int pkgOrderList::FileCmp(PkgIterator A,PkgIterator B) | |
347 | { | |
348 | if (Cache[A].Delete() == true && Cache[B].Delete() == true) | |
349 | return 0; | |
350 | if (Cache[A].Delete() == true) | |
351 | return -1; | |
352 | if (Cache[B].Delete() == true) | |
353 | return 1; | |
354 | ||
355 | if (Cache[A].InstVerIter(Cache).FileList().end() == true) | |
356 | return -1; | |
357 | if (Cache[B].InstVerIter(Cache).FileList().end() == true) | |
358 | return 1; | |
359 | ||
360 | pkgCache::PackageFile *FA = Cache[A].InstVerIter(Cache).FileList().File(); | |
361 | pkgCache::PackageFile *FB = Cache[B].InstVerIter(Cache).FileList().File(); | |
362 | if (FA < FB) | |
363 | return -1; | |
364 | if (FA > FB) | |
365 | return 1; | |
366 | return 0; | |
367 | } | |
368 | /*}}}*/ | |
369 | // BoolCompare - Comparison function for two booleans /*{{{*/ | |
370 | // --------------------------------------------------------------------- | |
371 | /* */ | |
372 | static int BoolCompare(bool A,bool B) | |
373 | { | |
374 | if (A == B) | |
375 | return 0; | |
376 | if (A == false) | |
377 | return -1; | |
378 | return 1; | |
379 | } | |
380 | /*}}}*/ | |
381 | // OrderList::OrderCompareA - Order the installation by op /*{{{*/ | |
382 | // --------------------------------------------------------------------- | |
383 | /* This provides a first-pass sort of the list and gives a decent starting | |
384 | point for further complete ordering. It is used by OrderUnpack only */ | |
385 | int pkgOrderList::OrderCompareA(const void *a, const void *b) | |
386 | { | |
387 | PkgIterator A(Me->Cache,*(Package **)a); | |
388 | PkgIterator B(Me->Cache,*(Package **)b); | |
389 | ||
390 | // We order packages with a set state toward the front | |
391 | int Res; | |
392 | if ((Res = BoolCompare(Me->IsNow(A),Me->IsNow(B))) != 0) | |
393 | return -1*Res; | |
394 | ||
395 | // We order missing files to toward the end | |
396 | /* if (Me->FileList != 0) | |
397 | { | |
398 | if ((Res = BoolCompare(Me->IsMissing(A), | |
399 | Me->IsMissing(B))) != 0) | |
400 | return Res; | |
401 | }*/ | |
402 | ||
403 | if (A.State() != pkgCache::PkgIterator::NeedsNothing && | |
404 | B.State() == pkgCache::PkgIterator::NeedsNothing) | |
405 | return -1; | |
406 | ||
407 | if (A.State() == pkgCache::PkgIterator::NeedsNothing && | |
408 | B.State() != pkgCache::PkgIterator::NeedsNothing) | |
409 | return 1; | |
410 | ||
411 | int ScoreA = Me->Score(A); | |
412 | int ScoreB = Me->Score(B); | |
413 | ||
414 | if (ScoreA > ScoreB) | |
415 | return -1; | |
416 | ||
417 | if (ScoreA < ScoreB) | |
418 | return 1; | |
419 | ||
420 | return strcmp(A.Name(),B.Name()); | |
421 | } | |
422 | /*}}}*/ | |
423 | // OrderList::OrderCompareB - Order the installation by source /*{{{*/ | |
424 | // --------------------------------------------------------------------- | |
425 | /* This orders by installation source. This is useful to handle | |
426 | inter-source breaks */ | |
427 | int pkgOrderList::OrderCompareB(const void *a, const void *b) | |
428 | { | |
429 | PkgIterator A(Me->Cache,*(Package **)a); | |
430 | PkgIterator B(Me->Cache,*(Package **)b); | |
431 | ||
432 | if (A.State() != pkgCache::PkgIterator::NeedsNothing && | |
433 | B.State() == pkgCache::PkgIterator::NeedsNothing) | |
434 | return -1; | |
435 | ||
436 | if (A.State() == pkgCache::PkgIterator::NeedsNothing && | |
437 | B.State() != pkgCache::PkgIterator::NeedsNothing) | |
438 | return 1; | |
439 | ||
440 | int F = Me->FileCmp(A,B); | |
441 | if (F != 0) | |
442 | { | |
443 | if (F > 0) | |
444 | return -1; | |
445 | return 1; | |
446 | } | |
447 | ||
448 | int ScoreA = Me->Score(A); | |
449 | int ScoreB = Me->Score(B); | |
450 | ||
451 | if (ScoreA > ScoreB) | |
452 | return -1; | |
453 | ||
454 | if (ScoreA < ScoreB) | |
455 | return 1; | |
456 | ||
457 | return strcmp(A.Name(),B.Name()); | |
458 | } | |
459 | /*}}}*/ | |
460 | // OrderList::VisitDeps - Visit forward install dependencies /*{{{*/ | |
461 | // --------------------------------------------------------------------- | |
462 | /* This calls the dependency function for the normal forwards dependencies | |
463 | of the package */ | |
464 | bool pkgOrderList::VisitDeps(DepFunc F,PkgIterator Pkg) | |
465 | { | |
466 | if (F == 0 || Pkg.end() == true || Cache[Pkg].InstallVer == 0) | |
467 | return true; | |
468 | ||
469 | return (this->*F)(Cache[Pkg].InstVerIter(Cache).DependsList()); | |
470 | } | |
471 | /*}}}*/ | |
472 | // OrderList::VisitRDeps - Visit reverse dependencies /*{{{*/ | |
473 | // --------------------------------------------------------------------- | |
474 | /* This calls the dependency function for all of the normal reverse depends | |
475 | of the package */ | |
476 | bool pkgOrderList::VisitRDeps(DepFunc F,PkgIterator Pkg) | |
477 | { | |
478 | if (F == 0 || Pkg.end() == true) | |
479 | return true; | |
480 | ||
481 | return (this->*F)(Pkg.RevDependsList()); | |
482 | } | |
483 | /*}}}*/ | |
484 | // OrderList::VisitRProvides - Visit provides reverse dependencies /*{{{*/ | |
485 | // --------------------------------------------------------------------- | |
486 | /* This calls the dependency function for all reverse dependencies | |
487 | generated by the provides line on the package. */ | |
488 | bool pkgOrderList::VisitRProvides(DepFunc F,VerIterator Ver) | |
489 | { | |
490 | if (F == 0 || Ver.end() == true) | |
491 | return true; | |
492 | ||
493 | bool Res = true; | |
494 | for (PrvIterator P = Ver.ProvidesList(); P.end() == false; P++) | |
495 | Res &= (this->*F)(P.ParentPkg().RevDependsList()); | |
496 | return true; | |
497 | } | |
498 | /*}}}*/ | |
499 | // OrderList::VisitProvides - Visit all of the providing packages /*{{{*/ | |
500 | // --------------------------------------------------------------------- | |
501 | /* This routine calls visit on all providing packages. */ | |
502 | bool pkgOrderList::VisitProvides(DepIterator D,bool Critical) | |
503 | { | |
504 | SPtrArray<Version *> List = D.AllTargets(); | |
505 | for (Version **I = List; *I != 0; I++) | |
506 | { | |
507 | VerIterator Ver(Cache,*I); | |
508 | PkgIterator Pkg = Ver.ParentPkg(); | |
509 | ||
510 | if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing) | |
511 | continue; | |
512 | ||
513 | if (D->Type != pkgCache::Dep::Conflicts && | |
514 | D->Type != pkgCache::Dep::DpkgBreaks && | |
515 | D->Type != pkgCache::Dep::Obsoletes && | |
516 | Cache[Pkg].InstallVer != *I) | |
517 | continue; | |
518 | ||
519 | if ((D->Type == pkgCache::Dep::Conflicts || | |
520 | D->Type == pkgCache::Dep::DpkgBreaks || | |
521 | D->Type == pkgCache::Dep::Obsoletes) && | |
522 | (Version *)Pkg.CurrentVer() != *I) | |
523 | continue; | |
524 | ||
525 | // Skip over missing files | |
526 | if (Critical == false && IsMissing(D.ParentPkg()) == true) | |
527 | continue; | |
528 | ||
529 | if (VisitNode(Pkg) == false) | |
530 | return false; | |
531 | } | |
532 | return true; | |
533 | } | |
534 | /*}}}*/ | |
535 | // OrderList::VisitNode - Recursive ordering director /*{{{*/ | |
536 | // --------------------------------------------------------------------- | |
537 | /* This is the core ordering routine. It calls the set dependency | |
538 | consideration functions which then potentialy call this again. Finite | |
539 | depth is achived through the colouring mechinism. */ | |
540 | bool pkgOrderList::VisitNode(PkgIterator Pkg) | |
541 | { | |
542 | // Looping or irrelevent. | |
543 | // This should probably trancend not installed packages | |
544 | if (Pkg.end() == true || IsFlag(Pkg,Added) == true || | |
545 | IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false) | |
546 | return true; | |
547 | ||
548 | if (Debug == true) | |
549 | { | |
550 | for (int j = 0; j != Depth; j++) clog << ' '; | |
551 | clog << "Visit " << Pkg.FullName() << endl; | |
552 | } | |
553 | ||
554 | Depth++; | |
555 | ||
556 | // Color grey | |
557 | Flag(Pkg,AddPending); | |
558 | ||
559 | DepFunc Old = Primary; | |
560 | ||
561 | // Perform immedate configuration of the package if so flagged. | |
562 | if (IsFlag(Pkg,Immediate) == true && Primary != &pkgOrderList::DepUnPackPre) | |
563 | Primary = &pkgOrderList::DepUnPackPreD; | |
564 | ||
565 | if (IsNow(Pkg) == true) | |
566 | { | |
567 | bool Res = true; | |
568 | if (Cache[Pkg].Delete() == false) | |
569 | { | |
570 | // Primary | |
571 | Res &= Res && VisitDeps(Primary,Pkg); | |
572 | Res &= Res && VisitRDeps(Primary,Pkg); | |
573 | Res &= Res && VisitRProvides(Primary,Pkg.CurrentVer()); | |
574 | Res &= Res && VisitRProvides(Primary,Cache[Pkg].InstVerIter(Cache)); | |
575 | ||
576 | // RevDep | |
577 | Res &= Res && VisitRDeps(RevDepends,Pkg); | |
578 | Res &= Res && VisitRProvides(RevDepends,Pkg.CurrentVer()); | |
579 | Res &= Res && VisitRProvides(RevDepends,Cache[Pkg].InstVerIter(Cache)); | |
580 | ||
581 | // Secondary | |
582 | Res &= Res && VisitDeps(Secondary,Pkg); | |
583 | Res &= Res && VisitRDeps(Secondary,Pkg); | |
584 | Res &= Res && VisitRProvides(Secondary,Pkg.CurrentVer()); | |
585 | Res &= Res && VisitRProvides(Secondary,Cache[Pkg].InstVerIter(Cache)); | |
586 | } | |
587 | else | |
588 | { | |
589 | // RevDep | |
590 | Res &= Res && VisitRDeps(Remove,Pkg); | |
591 | Res &= Res && VisitRProvides(Remove,Pkg.CurrentVer()); | |
592 | } | |
593 | } | |
594 | ||
595 | if (IsFlag(Pkg,Added) == false) | |
596 | { | |
597 | Flag(Pkg,Added,Added | AddPending); | |
598 | if (IsFlag(Pkg,After) == true) | |
599 | *AfterEnd++ = Pkg; | |
600 | else | |
601 | *End++ = Pkg; | |
602 | } | |
603 | ||
604 | Primary = Old; | |
605 | Depth--; | |
606 | ||
607 | if (Debug == true) | |
608 | { | |
609 | for (int j = 0; j != Depth; j++) clog << ' '; | |
610 | clog << "Leave " << Pkg.FullName() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl; | |
611 | } | |
612 | ||
613 | return true; | |
614 | } | |
615 | /*}}}*/ | |
616 | // OrderList::DepUnPackCrit - Critical UnPacking ordering /*{{{*/ | |
617 | // --------------------------------------------------------------------- | |
618 | /* Critical unpacking ordering strives to satisfy Conflicts: and | |
619 | PreDepends: only. When a prdepends is encountered the Primary | |
620 | DepFunc is changed to be DepUnPackPreD. | |
621 | ||
622 | Loops are preprocessed and logged. */ | |
623 | bool pkgOrderList::DepUnPackCrit(DepIterator D) | |
624 | { | |
625 | for (; D.end() == false; D++) | |
626 | { | |
627 | if (D.Reverse() == true) | |
628 | { | |
629 | /* Reverse depenanices are only interested in conflicts, | |
630 | predepend breakage is ignored here */ | |
631 | if (D->Type != pkgCache::Dep::Conflicts && | |
632 | D->Type != pkgCache::Dep::Obsoletes) | |
633 | continue; | |
634 | ||
635 | // Duplication elimination, consider only the current version | |
636 | if (D.ParentPkg().CurrentVer() != D.ParentVer()) | |
637 | continue; | |
638 | ||
639 | /* For reverse dependencies we wish to check if the | |
640 | dependency is satisifed in the install state. The | |
641 | target package (caller) is going to be in the installed | |
642 | state. */ | |
643 | if (CheckDep(D) == true) | |
644 | continue; | |
645 | ||
646 | if (VisitNode(D.ParentPkg()) == false) | |
647 | return false; | |
648 | } | |
649 | else | |
650 | { | |
651 | /* Forward critical dependencies MUST be correct before the | |
652 | package can be unpacked. */ | |
653 | if (D->Type != pkgCache::Dep::Conflicts && | |
654 | D->Type != pkgCache::Dep::DpkgBreaks && | |
655 | D->Type != pkgCache::Dep::Obsoletes && | |
656 | D->Type != pkgCache::Dep::PreDepends) | |
657 | continue; | |
658 | ||
659 | /* We wish to check if the dep is okay in the now state of the | |
660 | target package against the install state of this package. */ | |
661 | if (CheckDep(D) == true) | |
662 | { | |
663 | /* We want to catch predepends loops with the code below. | |
664 | Conflicts loops that are Dep OK are ignored */ | |
665 | if (IsFlag(D.TargetPkg(),AddPending) == false || | |
666 | D->Type != pkgCache::Dep::PreDepends) | |
667 | continue; | |
668 | } | |
669 | ||
670 | // This is the loop detection | |
671 | if (IsFlag(D.TargetPkg(),Added) == true || | |
672 | IsFlag(D.TargetPkg(),AddPending) == true) | |
673 | { | |
674 | if (IsFlag(D.TargetPkg(),AddPending) == true) | |
675 | AddLoop(D); | |
676 | continue; | |
677 | } | |
678 | ||
679 | /* Predepends require a special ordering stage, they must have | |
680 | all dependents installed as well */ | |
681 | DepFunc Old = Primary; | |
682 | bool Res = false; | |
683 | if (D->Type == pkgCache::Dep::PreDepends) | |
684 | Primary = &pkgOrderList::DepUnPackPreD; | |
685 | Res = VisitProvides(D,true); | |
686 | Primary = Old; | |
687 | if (Res == false) | |
688 | return false; | |
689 | } | |
690 | } | |
691 | return true; | |
692 | } | |
693 | /*}}}*/ | |
694 | // OrderList::DepUnPackPreD - Critical UnPacking ordering with depends /*{{{*/ | |
695 | // --------------------------------------------------------------------- | |
696 | /* Critical PreDepends (also configure immediate and essential) strives to | |
697 | ensure not only that all conflicts+predepends are met but that this | |
698 | package will be immediately configurable when it is unpacked. | |
699 | Loops are preprocessed and logged. */ | |
700 | bool pkgOrderList::DepUnPackPreD(DepIterator D) | |
701 | { | |
702 | if (D.Reverse() == true) | |
703 | return DepUnPackCrit(D); | |
704 | ||
705 | for (; D.end() == false; D++) | |
706 | { | |
707 | if (D.IsCritical() == false) | |
708 | continue; | |
709 | ||
710 | /* We wish to check if the dep is okay in the now state of the | |
711 | target package against the install state of this package. */ | |
712 | if (CheckDep(D) == true) | |
713 | { | |
714 | /* We want to catch predepends loops with the code below. | |
715 | Conflicts loops that are Dep OK are ignored */ | |
716 | if (IsFlag(D.TargetPkg(),AddPending) == false || | |
717 | D->Type != pkgCache::Dep::PreDepends) | |
718 | continue; | |
719 | } | |
720 | ||
721 | // This is the loop detection | |
722 | if (IsFlag(D.TargetPkg(),Added) == true || | |
723 | IsFlag(D.TargetPkg(),AddPending) == true) | |
724 | { | |
725 | if (IsFlag(D.TargetPkg(),AddPending) == true) | |
726 | AddLoop(D); | |
727 | continue; | |
728 | } | |
729 | ||
730 | if (VisitProvides(D,true) == false) | |
731 | return false; | |
732 | } | |
733 | return true; | |
734 | } | |
735 | /*}}}*/ | |
736 | // OrderList::DepUnPackPre - Critical Predepends ordering /*{{{*/ | |
737 | // --------------------------------------------------------------------- | |
738 | /* Critical PreDepends (also configure immediate and essential) strives to | |
739 | ensure not only that all conflicts+predepends are met but that this | |
740 | package will be immediately configurable when it is unpacked. | |
741 | ||
742 | Loops are preprocessed and logged. All loops will be fatal. */ | |
743 | bool pkgOrderList::DepUnPackPre(DepIterator D) | |
744 | { | |
745 | if (D.Reverse() == true) | |
746 | return true; | |
747 | ||
748 | for (; D.end() == false; D++) | |
749 | { | |
750 | /* Only consider the PreDepends or Depends. Depends are only | |
751 | considered at the lowest depth or in the case of immediate | |
752 | configure */ | |
753 | if (D->Type != pkgCache::Dep::PreDepends) | |
754 | { | |
755 | if (D->Type == pkgCache::Dep::Depends) | |
756 | { | |
757 | if (Depth == 1 && IsFlag(D.ParentPkg(),Immediate) == false) | |
758 | continue; | |
759 | } | |
760 | else | |
761 | continue; | |
762 | } | |
763 | ||
764 | /* We wish to check if the dep is okay in the now state of the | |
765 | target package against the install state of this package. */ | |
766 | if (CheckDep(D) == true) | |
767 | { | |
768 | /* We want to catch predepends loops with the code below. | |
769 | Conflicts loops that are Dep OK are ignored */ | |
770 | if (IsFlag(D.TargetPkg(),AddPending) == false) | |
771 | continue; | |
772 | } | |
773 | ||
774 | // This is the loop detection | |
775 | if (IsFlag(D.TargetPkg(),Added) == true || | |
776 | IsFlag(D.TargetPkg(),AddPending) == true) | |
777 | { | |
778 | if (IsFlag(D.TargetPkg(),AddPending) == true) | |
779 | AddLoop(D); | |
780 | continue; | |
781 | } | |
782 | ||
783 | if (VisitProvides(D,true) == false) | |
784 | return false; | |
785 | } | |
786 | return true; | |
787 | } | |
788 | /*}}}*/ | |
789 | // OrderList::DepUnPackDep - Reverse dependency considerations /*{{{*/ | |
790 | // --------------------------------------------------------------------- | |
791 | /* Reverse dependencies are considered to determine if unpacking this | |
792 | package will break any existing dependencies. If so then those | |
793 | packages are ordered before this one so that they are in the | |
794 | UnPacked state. | |
795 | ||
796 | The forwards depends loop is designed to bring the packages dependents | |
797 | close to the package. This helps reduce deconfigure time. | |
798 | ||
799 | Loops are irrelevent to this. */ | |
800 | bool pkgOrderList::DepUnPackDep(DepIterator D) | |
801 | { | |
802 | ||
803 | for (; D.end() == false; D++) | |
804 | if (D.IsCritical() == true) | |
805 | { | |
806 | if (D.Reverse() == true) | |
807 | { | |
808 | /* Duplication prevention. We consider rev deps only on | |
809 | the current version, a not installed package | |
810 | cannot break */ | |
811 | if (D.ParentPkg()->CurrentVer == 0 || | |
812 | D.ParentPkg().CurrentVer() != D.ParentVer()) | |
813 | continue; | |
814 | ||
815 | // The dep will not break so it is irrelevent. | |
816 | if (CheckDep(D) == true) | |
817 | continue; | |
818 | ||
819 | // Skip over missing files | |
820 | if (IsMissing(D.ParentPkg()) == true) | |
821 | continue; | |
822 | ||
823 | if (VisitNode(D.ParentPkg()) == false) | |
824 | return false; | |
825 | } | |
826 | else | |
827 | { | |
828 | if (D->Type == pkgCache::Dep::Depends) | |
829 | if (VisitProvides(D,false) == false) | |
830 | return false; | |
831 | ||
832 | if (D->Type == pkgCache::Dep::DpkgBreaks) | |
833 | { | |
834 | if (CheckDep(D) == true) | |
835 | continue; | |
836 | ||
837 | if (VisitNode(D.TargetPkg()) == false) | |
838 | return false; | |
839 | } | |
840 | } | |
841 | } | |
842 | return true; | |
843 | } | |
844 | /*}}}*/ | |
845 | // OrderList::DepConfigure - Configuration ordering /*{{{*/ | |
846 | // --------------------------------------------------------------------- | |
847 | /* Configuration only ordering orders by the Depends: line only. It | |
848 | orders configuration so that when a package comes to be configured it's | |
849 | dependents are configured. | |
850 | ||
851 | Loops are ingored. Depends loop entry points are chaotic. */ | |
852 | bool pkgOrderList::DepConfigure(DepIterator D) | |
853 | { | |
854 | // Never consider reverse configuration dependencies. | |
855 | if (D.Reverse() == true) | |
856 | return true; | |
857 | ||
858 | for (; D.end() == false; D++) | |
859 | if (D->Type == pkgCache::Dep::Depends) | |
860 | if (VisitProvides(D,false) == false) | |
861 | return false; | |
862 | return true; | |
863 | } | |
864 | /*}}}*/ | |
865 | // OrderList::DepRemove - Removal ordering /*{{{*/ | |
866 | // --------------------------------------------------------------------- | |
867 | /* Removal visits all reverse depends. It considers if the dependency | |
868 | of the Now state version to see if it is okay with removing this | |
869 | package. This check should always fail, but is provided for symetery | |
870 | with the other critical handlers. | |
871 | ||
872 | Loops are preprocessed and logged. Removal loops can also be | |
873 | detected in the critical handler. They are characterized by an | |
874 | old version of A depending on B but the new version of A conflicting | |
875 | with B, thus either A or B must break to install. */ | |
876 | bool pkgOrderList::DepRemove(DepIterator D) | |
877 | { | |
878 | if (D.Reverse() == false) | |
879 | return true; | |
880 | for (; D.end() == false; D++) | |
881 | if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends) | |
882 | { | |
883 | // Duplication elimination, consider the current version only | |
884 | if (D.ParentPkg().CurrentVer() != D.ParentVer()) | |
885 | continue; | |
886 | ||
887 | /* We wish to see if the dep on the parent package is okay | |
888 | in the removed (install) state of the target pkg. */ | |
889 | if (CheckDep(D) == true) | |
890 | { | |
891 | // We want to catch loops with the code below. | |
892 | if (IsFlag(D.ParentPkg(),AddPending) == false) | |
893 | continue; | |
894 | } | |
895 | ||
896 | // This is the loop detection | |
897 | if (IsFlag(D.ParentPkg(),Added) == true || | |
898 | IsFlag(D.ParentPkg(),AddPending) == true) | |
899 | { | |
900 | if (IsFlag(D.ParentPkg(),AddPending) == true) | |
901 | AddLoop(D); | |
902 | continue; | |
903 | } | |
904 | ||
905 | // Skip over missing files | |
906 | if (IsMissing(D.ParentPkg()) == true) | |
907 | continue; | |
908 | ||
909 | if (VisitNode(D.ParentPkg()) == false) | |
910 | return false; | |
911 | } | |
912 | ||
913 | return true; | |
914 | } | |
915 | /*}}}*/ | |
916 | // OrderList::AddLoop - Add a loop to the loop list /*{{{*/ | |
917 | // --------------------------------------------------------------------- | |
918 | /* We record the loops. This is a relic since loop breaking is done | |
919 | genericaly as part of the safety routines. */ | |
920 | bool pkgOrderList::AddLoop(DepIterator D) | |
921 | { | |
922 | if (LoopCount < 0 || LoopCount >= 20) | |
923 | return false; | |
924 | ||
925 | // Skip dups | |
926 | if (LoopCount != 0) | |
927 | { | |
928 | if (Loops[LoopCount - 1].ParentPkg() == D.ParentPkg() || | |
929 | Loops[LoopCount - 1].TargetPkg() == D.ParentPkg()) | |
930 | return true; | |
931 | } | |
932 | ||
933 | Loops[LoopCount++] = D; | |
934 | ||
935 | // Mark the packages as being part of a loop. | |
936 | Flag(D.TargetPkg(),Loop); | |
937 | Flag(D.ParentPkg(),Loop); | |
938 | return true; | |
939 | } | |
940 | /*}}}*/ | |
941 | // OrderList::WipeFlags - Unset the given flags from all packages /*{{{*/ | |
942 | // --------------------------------------------------------------------- | |
943 | /* */ | |
944 | void pkgOrderList::WipeFlags(unsigned long F) | |
945 | { | |
946 | unsigned long Size = Cache.Head().PackageCount; | |
947 | for (unsigned long I = 0; I != Size; I++) | |
948 | Flags[I] &= ~F; | |
949 | } | |
950 | /*}}}*/ | |
951 | // OrderList::CheckDep - Check a dependency for truth /*{{{*/ | |
952 | // --------------------------------------------------------------------- | |
953 | /* This performs a complete analysis of the dependency wrt to the | |
954 | current add list. It returns true if after all events are | |
955 | performed it is still true. This sort of routine can be approximated | |
956 | by examining the DepCache, however in convoluted cases of provides | |
957 | this fails to produce a suitable result. */ | |
958 | bool pkgOrderList::CheckDep(DepIterator D) | |
959 | { | |
960 | SPtrArray<Version *> List = D.AllTargets(); | |
961 | bool Hit = false; | |
962 | for (Version **I = List; *I != 0; I++) | |
963 | { | |
964 | VerIterator Ver(Cache,*I); | |
965 | PkgIterator Pkg = Ver.ParentPkg(); | |
966 | ||
967 | /* The meaning of Added and AddPending is subtle. AddPending is | |
968 | an indication that the package is looping. Because of the | |
969 | way ordering works Added means the package will be unpacked | |
970 | before this one and AddPending means after. It is therefore | |
971 | correct to ignore AddPending in all cases, but that exposes | |
972 | reverse-ordering loops which should be ignored. */ | |
973 | if (IsFlag(Pkg,Added) == true || | |
974 | (IsFlag(Pkg,AddPending) == true && D.Reverse() == true)) | |
975 | { | |
976 | if (Cache[Pkg].InstallVer != *I) | |
977 | continue; | |
978 | } | |
979 | else | |
980 | if ((Version *)Pkg.CurrentVer() != *I || | |
981 | Pkg.State() != PkgIterator::NeedsNothing) | |
982 | continue; | |
983 | ||
984 | /* Conflicts requires that all versions are not present, depends | |
985 | just needs one */ | |
986 | if (D->Type != pkgCache::Dep::Conflicts && | |
987 | D->Type != pkgCache::Dep::DpkgBreaks && | |
988 | D->Type != pkgCache::Dep::Obsoletes) | |
989 | { | |
990 | /* Try to find something that does not have the after flag set | |
991 | if at all possible */ | |
992 | if (IsFlag(Pkg,After) == true) | |
993 | { | |
994 | Hit = true; | |
995 | continue; | |
996 | } | |
997 | ||
998 | return true; | |
999 | } | |
1000 | else | |
1001 | { | |
1002 | if (IsFlag(Pkg,After) == true) | |
1003 | Flag(D.ParentPkg(),After); | |
1004 | ||
1005 | return false; | |
1006 | } | |
1007 | } | |
1008 | ||
1009 | // We found a hit, but it had the after flag set | |
1010 | if (Hit == true && D->Type == pkgCache::Dep::PreDepends) | |
1011 | { | |
1012 | Flag(D.ParentPkg(),After); | |
1013 | return true; | |
1014 | } | |
1015 | ||
1016 | /* Conflicts requires that all versions are not present, depends | |
1017 | just needs one */ | |
1018 | if (D->Type == pkgCache::Dep::Conflicts || | |
1019 | D->Type == pkgCache::Dep::Obsoletes) | |
1020 | return true; | |
1021 | return false; | |
1022 | } | |
1023 | /*}}}*/ |