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