1 /* 2 * Copyright (c) 2007-2009, Novell Inc. 3 * 4 * This program is licensed under the BSD license, read LICENSE.BSD 5 * for further information 6 */ 7 8 /* 9 * rules.c 10 * 11 * SAT based dependency solver 12 */ 13 14 #include <stdio.h> 15 #include <stdlib.h> 16 #include <unistd.h> 17 #include <string.h> 18 #include <assert.h> 19 20 #include "solver.h" 21 #include "solver_private.h" 22 #include "bitmap.h" 23 #include "pool.h" 24 #include "poolarch.h" 25 #include "util.h" 26 #include "evr.h" 27 #include "policy.h" 28 #include "solverdebug.h" 29 30 #define RULES_BLOCK 63 31 32 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep); 33 static void solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded); 34 35 /*------------------------------------------------------------------- 36 * Check if dependency is possible 37 * 38 * mirrors solver_dep_fulfilled but uses map m instead of the decisionmap. 39 * used in solver_addrpmrulesforweak and solver_createcleandepsmap. 40 */ 41 42 static inline int 43 dep_possible(Solver *solv, Id dep, Map *m) 44 { 45 Pool *pool = solv->pool; 46 Id p, pp; 47 48 if (ISRELDEP(dep)) 49 { 50 Reldep *rd = GETRELDEP(pool, dep); 51 if (rd->flags >= 8) 52 { 53 if (rd->flags == REL_AND) 54 { 55 if (!dep_possible(solv, rd->name, m)) 56 return 0; 57 return dep_possible(solv, rd->evr, m); 58 } 59 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES) 60 return solver_splitprovides(solv, rd->evr); 61 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED) 62 return solver_dep_installed(solv, rd->evr); 63 } 64 } 65 FOR_PROVIDES(p, pp, dep) 66 { 67 if (MAPTST(m, p)) 68 return 1; 69 } 70 return 0; 71 } 72 73 /******************************************************************** 74 * 75 * Rule handling 76 * 77 * - unify rules, remove duplicates 78 */ 79 80 /*------------------------------------------------------------------- 81 * 82 * compare rules for unification sort 83 * 84 */ 85 86 static int 87 unifyrules_sortcmp(const void *ap, const void *bp, void *dp) 88 { 89 Pool *pool = dp; 90 Rule *a = (Rule *)ap; 91 Rule *b = (Rule *)bp; 92 Id *ad, *bd; 93 int x; 94 95 x = a->p - b->p; 96 if (x) 97 return x; /* p differs */ 98 99 /* identical p */ 100 if (a->d == 0 && b->d == 0) 101 return a->w2 - b->w2; /* assertion: return w2 diff */ 102 103 if (a->d == 0) /* a is assertion, b not */ 104 { 105 x = a->w2 - pool->whatprovidesdata[b->d]; 106 return x ? x : -1; 107 } 108 109 if (b->d == 0) /* b is assertion, a not */ 110 { 111 x = pool->whatprovidesdata[a->d] - b->w2; 112 return x ? x : 1; 113 } 114 115 /* compare whatprovidesdata */ 116 ad = pool->whatprovidesdata + a->d; 117 bd = pool->whatprovidesdata + b->d; 118 while (*bd) 119 if ((x = *ad++ - *bd++) != 0) 120 return x; 121 return *ad; 122 } 123 124 int 125 solver_rulecmp(Solver *solv, Rule *r1, Rule *r2) 126 { 127 return unifyrules_sortcmp(r1, r2, solv->pool); 128 } 129 130 131 /*------------------------------------------------------------------- 132 * 133 * unify rules 134 * go over all rules and remove duplicates 135 */ 136 137 void 138 solver_unifyrules(Solver *solv) 139 { 140 Pool *pool = solv->pool; 141 int i, j; 142 Rule *ir, *jr; 143 144 if (solv->nrules <= 2) /* nothing to unify */ 145 return; 146 147 /* sort rules first */ 148 solv_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool); 149 150 /* prune rules 151 * i = unpruned 152 * j = pruned 153 */ 154 jr = 0; 155 for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++) 156 { 157 if (jr && !unifyrules_sortcmp(ir, jr, pool)) 158 continue; /* prune! */ 159 jr = solv->rules + j++; /* keep! */ 160 if (ir != jr) 161 *jr = *ir; 162 } 163 164 /* reduced count from nrules to j rules */ 165 POOL_DEBUG(SOLV_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j); 166 167 /* adapt rule buffer */ 168 solv->nrules = j; 169 solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK); 170 171 /* 172 * debug: log rule statistics 173 */ 174 IF_POOLDEBUG (SOLV_DEBUG_STATS) 175 { 176 int binr = 0; 177 int lits = 0; 178 Id *dp; 179 Rule *r; 180 181 for (i = 1; i < solv->nrules; i++) 182 { 183 r = solv->rules + i; 184 if (r->d == 0) 185 binr++; 186 else 187 { 188 dp = solv->pool->whatprovidesdata + r->d; 189 while (*dp++) 190 lits++; 191 } 192 } 193 POOL_DEBUG(SOLV_DEBUG_STATS, " binary: %d\n", binr); 194 POOL_DEBUG(SOLV_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits); 195 } 196 } 197 198 #if 0 199 200 /* 201 * hash rule 202 */ 203 204 static Hashval 205 hashrule(Solver *solv, Id p, Id d, int n) 206 { 207 unsigned int x = (unsigned int)p; 208 int *dp; 209 210 if (n <= 1) 211 return (x * 37) ^ (unsigned int)d; 212 dp = solv->pool->whatprovidesdata + d; 213 while (*dp) 214 x = (x * 37) ^ (unsigned int)*dp++; 215 return x; 216 } 217 #endif 218 219 220 /*------------------------------------------------------------------- 221 * 222 */ 223 224 /* 225 * add rule 226 * p = direct literal; always < 0 for installed rpm rules 227 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only) 228 * 229 * 230 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3) 231 * 232 * p < 0 : pkg id of A 233 * d > 0 : Offset in whatprovidesdata (list of providers of b) 234 * 235 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3) 236 * p < 0 : pkg id of A 237 * d < 0 : Id of solvable (e.g. B1) 238 * 239 * d == 0: unary rule, assertion => (A) or (-A) 240 * 241 * Install: p > 0, d = 0 (A) user requested install 242 * Remove: p < 0, d = 0 (-A) user requested remove (also: uninstallable) 243 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p> 244 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p> 245 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule) 246 * also used for obsoletes 247 * ?: p > 0, d < 0 (A|-B) 248 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder) 249 * 250 * resulting watches: 251 * ------------------ 252 * Direct assertion (no watch needed) --> d = 0, w1 = p, w2 = 0 253 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p 254 * every other : w1 = p, w2 = whatprovidesdata[d]; 255 * Disabled rule: w1 = 0 256 * 257 * always returns a rule for non-rpm rules 258 */ 259 260 Rule * 261 solver_addrule(Solver *solv, Id p, Id d) 262 { 263 Pool *pool = solv->pool; 264 Rule *r = 0; 265 Id *dp = 0; 266 267 int n = 0; /* number of literals in rule - 1 268 0 = direct assertion (single literal) 269 1 = binary rule 270 >1 = 271 */ 272 273 /* it often happenes that requires lead to adding the same rpm rule 274 * multiple times, so we prune those duplicates right away to make 275 * the work for unifyrules a bit easier */ 276 277 if (!solv->rpmrules_end) /* we add rpm rules */ 278 { 279 r = solv->rules + solv->nrules - 1; /* get the last added rule */ 280 if (r->p == p && r->d == d && (d != 0 || !r->w2)) 281 return r; 282 } 283 284 /* 285 * compute number of literals (n) in rule 286 */ 287 288 if (d < 0) 289 { 290 /* always a binary rule */ 291 if (p == d) 292 return 0; /* ignore self conflict */ 293 n = 1; 294 } 295 else if (d > 0) 296 { 297 for (dp = pool->whatprovidesdata + d; *dp; dp++, n++) 298 if (*dp == -p) 299 return 0; /* rule is self-fulfilling */ 300 301 if (n == 1) /* convert to binary rule */ 302 d = dp[-1]; 303 } 304 305 if (n == 1 && p > d && !solv->rpmrules_end) 306 { 307 /* smallest literal first so we can find dups */ 308 n = p; p = d; d = n; /* p <-> d */ 309 n = 1; /* re-set n, was used as temp var */ 310 } 311 312 /* 313 * check for duplicate 314 */ 315 316 /* check if the last added rule (r) is exactly the same as what we're looking for. */ 317 if (r && n == 1 && !r->d && r->p == p && r->w2 == d) 318 return r; /* binary rule */ 319 320 /* have n-ary rule with same first literal, check other literals */ 321 if (r && n > 1 && r->d && r->p == p) 322 { 323 /* Rule where d is an offset in whatprovidesdata */ 324 Id *dp2; 325 if (d == r->d) 326 return r; 327 dp2 = pool->whatprovidesdata + r->d; 328 for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++) 329 if (*dp != *dp2) 330 break; 331 if (*dp == *dp2) 332 return r; 333 } 334 335 /* 336 * allocate new rule 337 */ 338 339 /* extend rule buffer */ 340 solv->rules = solv_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK); 341 r = solv->rules + solv->nrules++; /* point to rule space */ 342 343 /* 344 * r = new rule 345 */ 346 347 r->p = p; 348 if (n == 0) 349 { 350 /* direct assertion, no watch needed */ 351 r->d = 0; 352 r->w1 = p; 353 r->w2 = 0; 354 } 355 else if (n == 1) 356 { 357 /* binary rule */ 358 r->d = 0; 359 r->w1 = p; 360 r->w2 = d; 361 } 362 else 363 { 364 r->d = d; 365 r->w1 = p; 366 r->w2 = pool->whatprovidesdata[d]; 367 } 368 r->n1 = 0; 369 r->n2 = 0; 370 371 IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION) 372 { 373 POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, " Add rule: "); 374 solver_printrule(solv, SOLV_DEBUG_RULE_CREATION, r); 375 } 376 377 return r; 378 } 379 380 void 381 solver_shrinkrules(Solver *solv, int nrules) 382 { 383 solv->nrules = nrules; 384 solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK); 385 } 386 387 /****************************************************************************** 388 *** 389 *** rpm rule part: create rules representing the package dependencies 390 *** 391 ***/ 392 393 /* 394 * special multiversion patch conflict handling: 395 * a patch conflict is also satisfied if some other 396 * version with the same name/arch that doesn't conflict 397 * gets installed. The generated rule is thus: 398 * -patch|-cpack|opack1|opack2|... 399 */ 400 static Id 401 makemultiversionconflict(Solver *solv, Id n, Id con) 402 { 403 Pool *pool = solv->pool; 404 Solvable *s, *sn; 405 Queue q; 406 Id p, pp, qbuf[64]; 407 408 sn = pool->solvables + n; 409 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf)); 410 queue_push(&q, -n); 411 FOR_PROVIDES(p, pp, sn->name) 412 { 413 s = pool->solvables + p; 414 if (s->name != sn->name || s->arch != sn->arch) 415 continue; 416 if (!MAPTST(&solv->multiversion, p)) 417 continue; 418 if (pool_match_nevr(pool, pool->solvables + p, con)) 419 continue; 420 /* here we have a multiversion solvable that doesn't conflict */ 421 /* thus we're not in conflict if it is installed */ 422 queue_push(&q, p); 423 } 424 if (q.count == 1) 425 return -n; /* no other package found, generate normal conflict */ 426 return pool_queuetowhatprovides(pool, &q); 427 } 428 429 static inline void 430 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep) 431 { 432 if (!solv->ruleinfoq) 433 solver_addrule(solv, p, d); 434 else 435 addrpmruleinfo(solv, p, d, type, dep); 436 } 437 438 /*------------------------------------------------------------------- 439 * 440 * add (install) rules for solvable 441 * 442 * s: Solvable for which to add rules 443 * m: m[s] = 1 for solvables which have rules, prevent rule duplication 444 * 445 * Algorithm: 'visit all nodes of a graph'. The graph nodes are 446 * solvables, the edges their dependencies. 447 * Starting from an installed solvable, this will create all rules 448 * representing the graph created by the solvables dependencies. 449 * 450 * for unfulfilled requirements, conflicts, obsoletes,.... 451 * add a negative assertion for solvables that are not installable 452 * 453 * It will also create rules for all solvables referenced by 's' 454 * i.e. descend to all providers of requirements of 's' 455 * 456 */ 457 458 void 459 solver_addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m) 460 { 461 Pool *pool = solv->pool; 462 Repo *installed = solv->installed; 463 464 /* 'work' queue. keeps Ids of solvables we still have to work on. 465 And buffer for it. */ 466 Queue workq; 467 Id workqbuf[64]; 468 469 int i; 470 /* if to add rules for broken deps ('rpm -V' functionality) 471 * 0 = yes, 1 = no 472 */ 473 int dontfix; 474 /* Id var and pointer for each dependency 475 * (not used in parallel) 476 */ 477 Id req, *reqp; 478 Id con, *conp; 479 Id obs, *obsp; 480 Id rec, *recp; 481 Id sug, *sugp; 482 Id p, pp; /* whatprovides loops */ 483 Id *dp; /* ptr to 'whatprovides' */ 484 Id n; /* Id for current solvable 's' */ 485 486 queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf)); 487 queue_push(&workq, s - pool->solvables); /* push solvable Id to work queue */ 488 489 /* loop until there's no more work left */ 490 while (workq.count) 491 { 492 /* 493 * n: Id of solvable 494 * s: Pointer to solvable 495 */ 496 497 n = queue_shift(&workq); /* 'pop' next solvable to work on from queue */ 498 if (m) 499 { 500 if (MAPTST(m, n)) /* continue if already visited */ 501 continue; 502 MAPSET(m, n); /* mark as visited */ 503 } 504 505 s = pool->solvables + n; /* s = Solvable in question */ 506 507 dontfix = 0; 508 if (installed /* Installed system available */ 509 && s->repo == installed /* solvable is installed */ 510 && !solv->fixmap_all /* NOT repair errors in rpm dependency graph */ 511 && !(solv->fixmap.size && MAPTST(&solv->fixmap, n - installed->start))) 512 { 513 dontfix = 1; /* dont care about broken rpm deps */ 514 } 515 516 if (!dontfix) 517 { 518 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC 519 ? pool_disabled_solvable(pool, s) 520 : !pool_installable(pool, s)) 521 { 522 POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", pool_solvable2str(pool, s), (Id)(s - pool->solvables)); 523 addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0); 524 } 525 } 526 527 /* yet another SUSE hack, sigh */ 528 if (pool->nscallback && !strncmp("product:", pool_id2str(pool, s->name), 8)) 529 { 530 Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n); 531 if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables) 532 { 533 addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n)); 534 addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy)); 535 if (m && !MAPTST(m, buddy)) 536 queue_push(&workq, buddy); 537 } 538 } 539 540 /*----------------------------------------- 541 * check requires of s 542 */ 543 544 if (s->requires) 545 { 546 reqp = s->repo->idarraydata + s->requires; 547 while ((req = *reqp++) != 0) /* go through all requires */ 548 { 549 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */ 550 continue; 551 552 /* find list of solvables providing 'req' */ 553 dp = pool_whatprovides_ptr(pool, req); 554 555 if (*dp == SYSTEMSOLVABLE) /* always installed */ 556 continue; 557 558 if (dontfix) 559 { 560 /* the strategy here is to not insist on dependencies 561 * that are already broken. so if we find one provider 562 * that was already installed, we know that the 563 * dependency was not broken before so we enforce it */ 564 565 /* check if any of the providers for 'req' is installed */ 566 for (i = 0; (p = dp[i]) != 0; i++) 567 { 568 if (pool->solvables[p].repo == installed) 569 break; /* provider was installed */ 570 } 571 /* didn't find an installed provider: previously broken dependency */ 572 if (!p) 573 { 574 POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", pool_dep2str(pool, req), pool_solvable2str(pool, s)); 575 continue; 576 } 577 } 578 579 if (!*dp) 580 { 581 /* nothing provides req! */ 582 POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", pool_solvable2str(pool, s), (Id)(s - pool->solvables), pool_dep2str(pool, req)); 583 addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req); 584 continue; 585 } 586 587 IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION) 588 { 589 POOL_DEBUG(SOLV_DEBUG_RULE_CREATION," %s requires %s\n", pool_solvable2str(pool, s), pool_dep2str(pool, req)); 590 for (i = 0; dp[i]; i++) 591 POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, " provided by %s\n", pool_solvid2str(pool, dp[i])); 592 } 593 594 /* add 'requires' dependency */ 595 /* rule: (-requestor|provider1|provider2|...|providerN) */ 596 addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req); 597 598 /* descend the dependency tree 599 push all non-visited providers on the work queue */ 600 if (m) 601 { 602 for (; *dp; dp++) 603 { 604 if (!MAPTST(m, *dp)) 605 queue_push(&workq, *dp); 606 } 607 } 608 609 } /* while, requirements of n */ 610 611 } /* if, requirements */ 612 613 /* that's all we check for src packages */ 614 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC) 615 continue; 616 617 /*----------------------------------------- 618 * check conflicts of s 619 */ 620 621 if (s->conflicts) 622 { 623 int ispatch = 0; 624 625 /* we treat conflicts in patches a bit differen: 626 * - nevr matching 627 * - multiversion handling 628 * XXX: we should really handle this different, looking 629 * at the name is a bad hack 630 */ 631 if (!strncmp("patch:", pool_id2str(pool, s->name), 6)) 632 ispatch = 1; 633 conp = s->repo->idarraydata + s->conflicts; 634 /* foreach conflicts of 's' */ 635 while ((con = *conp++) != 0) 636 { 637 /* foreach providers of a conflict of 's' */ 638 FOR_PROVIDES(p, pp, con) 639 { 640 if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con)) 641 continue; 642 /* dontfix: dont care about conflicts with already installed packs */ 643 if (dontfix && pool->solvables[p].repo == installed) 644 continue; 645 /* p == n: self conflict */ 646 if (p == n && pool->forbidselfconflicts) 647 { 648 if (ISRELDEP(con)) 649 { 650 Reldep *rd = GETRELDEP(pool, con); 651 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS) 652 continue; 653 } 654 p = 0; /* make it a negative assertion, aka 'uninstallable' */ 655 } 656 if (p && ispatch && solv->multiversion.size && MAPTST(&solv->multiversion, p) && ISRELDEP(con)) 657 { 658 /* our patch conflicts with a multiversion package */ 659 p = -makemultiversionconflict(solv, p, con); 660 } 661 /* rule: -n|-p: either solvable _or_ provider of conflict */ 662 addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con); 663 } 664 } 665 } 666 667 /*----------------------------------------- 668 * check obsoletes and implicit obsoletes of a package 669 * if ignoreinstalledsobsoletes is not set, we're also checking 670 * obsoletes of installed packages (like newer rpm versions) 671 */ 672 if ((!installed || s->repo != installed) || !pool->noinstalledobsoletes) 673 { 674 int multi = solv->multiversion.size && MAPTST(&solv->multiversion, n); 675 int isinstalled = (installed && s->repo == installed); 676 if (s->obsoletes && (!multi || solv->keepexplicitobsoletes)) 677 { 678 obsp = s->repo->idarraydata + s->obsoletes; 679 /* foreach obsoletes */ 680 while ((obs = *obsp++) != 0) 681 { 682 /* foreach provider of an obsoletes of 's' */ 683 FOR_PROVIDES(p, pp, obs) 684 { 685 Solvable *ps = pool->solvables + p; 686 if (p == n) 687 continue; 688 if (isinstalled && dontfix && ps->repo == installed) 689 continue; /* don't repair installed/installed problems */ 690 if (!pool->obsoleteusesprovides /* obsoletes are matched names, not provides */ 691 && !pool_match_nevr(pool, ps, obs)) 692 continue; 693 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 694 continue; 695 if (!isinstalled) 696 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs); 697 else 698 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_INSTALLEDPKG_OBSOLETES, obs); 699 } 700 } 701 } 702 /* check implicit obsoletes 703 * for installed packages we only need to check installed/installed problems (and 704 * only when dontfix is not set), as the others are picked up when looking at the 705 * uninstalled package. 706 */ 707 if (!isinstalled || !dontfix) 708 { 709 FOR_PROVIDES(p, pp, s->name) 710 { 711 Solvable *ps = pool->solvables + p; 712 if (p == n) 713 continue; 714 if (isinstalled && ps->repo != installed) 715 continue; 716 /* we still obsolete packages with same nevra, like rpm does */ 717 /* (actually, rpm mixes those packages. yuck...) */ 718 if (multi && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch)) 719 continue; 720 if (!pool->implicitobsoleteusesprovides && s->name != ps->name) 721 continue; 722 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 723 continue; 724 if (s->name == ps->name) 725 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0); 726 else 727 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name); 728 } 729 } 730 } 731 732 /*----------------------------------------- 733 * add recommends to the work queue 734 */ 735 if (s->recommends && m) 736 { 737 recp = s->repo->idarraydata + s->recommends; 738 while ((rec = *recp++) != 0) 739 { 740 FOR_PROVIDES(p, pp, rec) 741 if (!MAPTST(m, p)) 742 queue_push(&workq, p); 743 } 744 } 745 if (s->suggests && m) 746 { 747 sugp = s->repo->idarraydata + s->suggests; 748 while ((sug = *sugp++) != 0) 749 { 750 FOR_PROVIDES(p, pp, sug) 751 if (!MAPTST(m, p)) 752 queue_push(&workq, p); 753 } 754 } 755 } 756 queue_free(&workq); 757 } 758 759 760 /*------------------------------------------------------------------- 761 * 762 * Add rules for packages possibly selected in by weak dependencies 763 * 764 * m: already added solvables 765 */ 766 767 void 768 solver_addrpmrulesforweak(Solver *solv, Map *m) 769 { 770 Pool *pool = solv->pool; 771 Solvable *s; 772 Id sup, *supp; 773 int i, n; 774 775 /* foreach solvable in pool */ 776 for (i = n = 1; n < pool->nsolvables; i++, n++) 777 { 778 if (i == pool->nsolvables) /* wrap i */ 779 i = 1; 780 if (MAPTST(m, i)) /* already added that one */ 781 continue; 782 783 s = pool->solvables + i; 784 if (!s->repo) 785 continue; 786 if (s->repo != pool->installed && !pool_installable(pool, s)) 787 continue; /* only look at installable ones */ 788 789 sup = 0; 790 if (s->supplements) 791 { 792 /* find possible supplements */ 793 supp = s->repo->idarraydata + s->supplements; 794 while ((sup = *supp++) != 0) 795 if (dep_possible(solv, sup, m)) 796 break; 797 } 798 799 /* if nothing found, check for enhances */ 800 if (!sup && s->enhances) 801 { 802 supp = s->repo->idarraydata + s->enhances; 803 while ((sup = *supp++) != 0) 804 if (dep_possible(solv, sup, m)) 805 break; 806 } 807 /* if nothing found, goto next solvables */ 808 if (!sup) 809 continue; 810 solver_addrpmrulesforsolvable(solv, s, m); 811 n = 0; /* check all solvables again because we added solvables to m */ 812 } 813 } 814 815 816 /*------------------------------------------------------------------- 817 * 818 * add package rules for possible updates 819 * 820 * s: solvable 821 * m: map of already visited solvables 822 * allow_all: 0 = dont allow downgrades, 1 = allow all candidates 823 */ 824 825 void 826 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all) 827 { 828 Pool *pool = solv->pool; 829 int i; 830 /* queue and buffer for it */ 831 Queue qs; 832 Id qsbuf[64]; 833 834 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf)); 835 /* find update candidates for 's' */ 836 policy_findupdatepackages(solv, s, &qs, allow_all); 837 /* add rule for 's' if not already done */ 838 if (!MAPTST(m, s - pool->solvables)) 839 solver_addrpmrulesforsolvable(solv, s, m); 840 /* foreach update candidate, add rule if not already done */ 841 for (i = 0; i < qs.count; i++) 842 if (!MAPTST(m, qs.elements[i])) 843 solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m); 844 queue_free(&qs); 845 } 846 847 848 /*********************************************************************** 849 *** 850 *** Update/Feature rule part 851 *** 852 *** Those rules make sure an installed package isn't silently deleted 853 *** 854 ***/ 855 856 static Id 857 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all) 858 { 859 Pool *pool = solv->pool; 860 int i; 861 862 policy_findupdatepackages(solv, s, qs, allow_all ? allow_all : 2); 863 if (!qs->count) 864 { 865 if (allow_all) 866 return 0; /* orphaned, don't create feature rule */ 867 /* check if this is an orphaned package */ 868 policy_findupdatepackages(solv, s, qs, 1); 869 if (!qs->count) 870 return 0; /* orphaned, don't create update rule */ 871 qs->count = 0; 872 return -SYSTEMSOLVABLE; /* supported but not installable */ 873 } 874 if (allow_all) 875 return s - pool->solvables; 876 /* check if it is ok to keep the installed package */ 877 for (i = 0; i < qs->count; i++) 878 { 879 Solvable *ns = pool->solvables + qs->elements[i]; 880 if (s->evr == ns->evr && solvable_identical(s, ns)) 881 return s - pool->solvables; 882 } 883 /* nope, it must be some other package */ 884 return -SYSTEMSOLVABLE; 885 } 886 887 /* add packages from the dup repositories to the update candidates 888 * this isn't needed for the global dup mode as all packages are 889 * from dup repos in that case */ 890 static void 891 addduppackages(Solver *solv, Solvable *s, Queue *qs) 892 { 893 Queue dupqs; 894 Id p, dupqsbuf[64]; 895 int i; 896 int oldnoupdateprovide = solv->noupdateprovide; 897 898 queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf)); 899 solv->noupdateprovide = 1; 900 policy_findupdatepackages(solv, s, &dupqs, 2); 901 solv->noupdateprovide = oldnoupdateprovide; 902 for (i = 0; i < dupqs.count; i++) 903 { 904 p = dupqs.elements[i]; 905 if (MAPTST(&solv->dupmap, p)) 906 queue_pushunique(qs, p); 907 } 908 queue_free(&dupqs); 909 } 910 911 /*------------------------------------------------------------------- 912 * 913 * add rule for update 914 * (A|A1|A2|A3...) An = update candidates for A 915 * 916 * s = (installed) solvable 917 */ 918 919 void 920 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all) 921 { 922 /* installed packages get a special upgrade allowed rule */ 923 Pool *pool = solv->pool; 924 Id p, d; 925 Queue qs; 926 Id qsbuf[64]; 927 928 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf)); 929 p = s - pool->solvables; 930 /* find update candidates for 's' */ 931 if (solv->dupmap_all) 932 p = finddistupgradepackages(solv, s, &qs, allow_all); 933 else 934 policy_findupdatepackages(solv, s, &qs, allow_all); 935 if (!allow_all && !solv->dupmap_all && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)) 936 addduppackages(solv, s, &qs); 937 938 if (!allow_all && qs.count && solv->multiversion.size) 939 { 940 int i, j; 941 942 d = pool_queuetowhatprovides(pool, &qs); 943 /* filter out all multiversion packages as they don't update */ 944 for (i = j = 0; i < qs.count; i++) 945 { 946 if (MAPTST(&solv->multiversion, qs.elements[i])) 947 { 948 /* it's ok if they have same nevra */ 949 Solvable *ps = pool->solvables + qs.elements[i]; 950 if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch) 951 continue; 952 } 953 qs.elements[j++] = qs.elements[i]; 954 } 955 if (j < qs.count) 956 { 957 if (d && solv->installed && s->repo == solv->installed && 958 (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, s - pool->solvables - solv->installed->start)))) 959 { 960 if (!solv->multiversionupdaters) 961 solv->multiversionupdaters = solv_calloc(solv->installed->end - solv->installed->start, sizeof(Id)); 962 solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d; 963 } 964 if (j == 0 && p == -SYSTEMSOLVABLE && solv->dupmap_all) 965 { 966 queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */ 967 j = qs.count; 968 } 969 qs.count = j; 970 } 971 else if (p != -SYSTEMSOLVABLE) 972 { 973 /* could fallthrough, but then we would do pool_queuetowhatprovides twice */ 974 queue_free(&qs); 975 solver_addrule(solv, p, d); /* allow update of s */ 976 return; 977 } 978 } 979 if (qs.count && p == -SYSTEMSOLVABLE) 980 p = queue_shift(&qs); 981 d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0; 982 queue_free(&qs); 983 solver_addrule(solv, p, d); /* allow update of s */ 984 } 985 986 static inline void 987 disableupdaterule(Solver *solv, Id p) 988 { 989 Rule *r; 990 991 MAPSET(&solv->noupdate, p - solv->installed->start); 992 r = solv->rules + solv->updaterules + (p - solv->installed->start); 993 if (r->p && r->d >= 0) 994 solver_disablerule(solv, r); 995 r = solv->rules + solv->featurerules + (p - solv->installed->start); 996 if (r->p && r->d >= 0) 997 solver_disablerule(solv, r); 998 if (solv->bestrules_pkg) 999 { 1000 int i, ni; 1001 ni = solv->bestrules_end - solv->bestrules; 1002 for (i = 0; i < ni; i++) 1003 if (solv->bestrules_pkg[i] == p) 1004 solver_disablerule(solv, solv->rules + solv->bestrules + i); 1005 } 1006 } 1007 1008 static inline void 1009 reenableupdaterule(Solver *solv, Id p) 1010 { 1011 Pool *pool = solv->pool; 1012 Rule *r; 1013 1014 MAPCLR(&solv->noupdate, p - solv->installed->start); 1015 r = solv->rules + solv->updaterules + (p - solv->installed->start); 1016 if (r->p) 1017 { 1018 if (r->d < 0) 1019 { 1020 solver_enablerule(solv, r); 1021 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS) 1022 { 1023 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling "); 1024 solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r); 1025 } 1026 } 1027 } 1028 else 1029 { 1030 r = solv->rules + solv->featurerules + (p - solv->installed->start); 1031 if (r->p && r->d < 0) 1032 { 1033 solver_enablerule(solv, r); 1034 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS) 1035 { 1036 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling "); 1037 solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r); 1038 } 1039 } 1040 } 1041 if (solv->bestrules_pkg) 1042 { 1043 int i, ni; 1044 ni = solv->bestrules_end - solv->bestrules; 1045 for (i = 0; i < ni; i++) 1046 if (solv->bestrules_pkg[i] == p) 1047 solver_enablerule(solv, solv->rules + solv->bestrules + i); 1048 } 1049 } 1050 1051 1052 /*********************************************************************** 1053 *** 1054 *** Infarch rule part 1055 *** 1056 *** Infarch rules make sure the solver uses the best architecture of 1057 *** a package if multiple archetectures are available 1058 *** 1059 ***/ 1060 1061 void 1062 solver_addinfarchrules(Solver *solv, Map *addedmap) 1063 { 1064 Pool *pool = solv->pool; 1065 int first, i, j; 1066 Id p, pp, a, aa, bestarch; 1067 Solvable *s, *ps, *bests; 1068 Queue badq, allowedarchs; 1069 1070 queue_init(&badq); 1071 queue_init(&allowedarchs); 1072 solv->infarchrules = solv->nrules; 1073 for (i = 1; i < pool->nsolvables; i++) 1074 { 1075 if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i)) 1076 continue; 1077 s = pool->solvables + i; 1078 first = i; 1079 bestarch = 0; 1080 bests = 0; 1081 queue_empty(&allowedarchs); 1082 FOR_PROVIDES(p, pp, s->name) 1083 { 1084 ps = pool->solvables + p; 1085 if (ps->name != s->name || !MAPTST(addedmap, p)) 1086 continue; 1087 if (p == i) 1088 first = 0; 1089 if (first) 1090 break; 1091 a = ps->arch; 1092 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0; 1093 if (a != 1 && pool->installed && ps->repo == pool->installed) 1094 { 1095 if (!solv->dupmap_all && !(solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))) 1096 queue_pushunique(&allowedarchs, ps->arch); /* also ok to keep this architecture */ 1097 continue; /* ignore installed solvables when calculating the best arch */ 1098 } 1099 if (a && a != 1 && (!bestarch || a < bestarch)) 1100 { 1101 bestarch = a; 1102 bests = ps; 1103 } 1104 } 1105 if (first) 1106 continue; 1107 /* speed up common case where installed package already has best arch */ 1108 if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch) 1109 allowedarchs.count--; /* installed arch is best */ 1110 queue_empty(&badq); 1111 FOR_PROVIDES(p, pp, s->name) 1112 { 1113 ps = pool->solvables + p; 1114 if (ps->name != s->name || !MAPTST(addedmap, p)) 1115 continue; 1116 a = ps->arch; 1117 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0; 1118 if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0) 1119 { 1120 if (pool->installed && ps->repo == pool->installed) 1121 continue; /* always ok to keep an installed package */ 1122 for (j = 0; j < allowedarchs.count; j++) 1123 { 1124 aa = allowedarchs.elements[j]; 1125 if (ps->arch == aa) 1126 break; 1127 aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0; 1128 if (aa && ((a ^ aa) & 0xffff0000) == 0) 1129 break; /* compatible */ 1130 } 1131 if (j == allowedarchs.count) 1132 queue_push(&badq, p); 1133 } 1134 } 1135 if (!badq.count) 1136 continue; 1137 /* block all solvables in the badq! */ 1138 for (j = 0; j < badq.count; j++) 1139 { 1140 p = badq.elements[j]; 1141 solver_addrule(solv, -p, 0); 1142 } 1143 } 1144 queue_free(&badq); 1145 queue_free(&allowedarchs); 1146 solv->infarchrules_end = solv->nrules; 1147 } 1148 1149 static inline void 1150 disableinfarchrule(Solver *solv, Id name) 1151 { 1152 Pool *pool = solv->pool; 1153 Rule *r; 1154 int i; 1155 for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++) 1156 { 1157 if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name) 1158 solver_disablerule(solv, r); 1159 } 1160 } 1161 1162 static inline void 1163 reenableinfarchrule(Solver *solv, Id name) 1164 { 1165 Pool *pool = solv->pool; 1166 Rule *r; 1167 int i; 1168 for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++) 1169 { 1170 if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name) 1171 { 1172 solver_enablerule(solv, r); 1173 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS) 1174 { 1175 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling "); 1176 solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r); 1177 } 1178 } 1179 } 1180 } 1181 1182 1183 /*********************************************************************** 1184 *** 1185 *** Dup rule part 1186 *** 1187 *** Dup rules make sure a package is selected from the specified dup 1188 *** repositories if an update candidate is included in one of them. 1189 *** 1190 ***/ 1191 1192 static inline void 1193 add_cleandeps_package(Solver *solv, Id p) 1194 { 1195 if (!solv->cleandeps_updatepkgs) 1196 { 1197 solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue)); 1198 queue_init(solv->cleandeps_updatepkgs); 1199 } 1200 queue_pushunique(solv->cleandeps_updatepkgs, p); 1201 } 1202 1203 static inline void 1204 solver_addtodupmaps(Solver *solv, Id p, Id how, int targeted) 1205 { 1206 Pool *pool = solv->pool; 1207 Solvable *ps, *s = pool->solvables + p; 1208 Repo *installed = solv->installed; 1209 Id pi, pip, obs, *obsp; 1210 1211 MAPSET(&solv->dupinvolvedmap, p); 1212 if (targeted) 1213 MAPSET(&solv->dupmap, p); 1214 FOR_PROVIDES(pi, pip, s->name) 1215 { 1216 ps = pool->solvables + pi; 1217 if (ps->name != s->name) 1218 continue; 1219 MAPSET(&solv->dupinvolvedmap, pi); 1220 if (targeted && ps->repo == installed && solv->obsoletes && solv->obsoletes[pi - installed->start]) 1221 { 1222 Id *opp, pi2; 1223 for (opp = solv->obsoletes_data + solv->obsoletes[pi - installed->start]; (pi2 = *opp++) != 0;) 1224 if (pool->solvables[pi2].repo != installed) 1225 MAPSET(&solv->dupinvolvedmap, pi2); 1226 } 1227 if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0) 1228 { 1229 if (!solv->bestupdatemap.size) 1230 map_grow(&solv->bestupdatemap, installed->end - installed->start); 1231 MAPSET(&solv->bestupdatemap, pi - installed->start); 1232 } 1233 if (ps->repo == installed && (how & SOLVER_CLEANDEPS) != 0) 1234 add_cleandeps_package(solv, pi); 1235 if (!targeted && ps->repo != installed) 1236 MAPSET(&solv->dupmap, pi); 1237 } 1238 if (s->repo == installed && solv->obsoletes && solv->obsoletes[p - installed->start]) 1239 { 1240 Id *opp; 1241 for (opp = solv->obsoletes_data + solv->obsoletes[p - installed->start]; (pi = *opp++) != 0;) 1242 { 1243 ps = pool->solvables + pi; 1244 if (ps->repo == installed) 1245 continue; 1246 MAPSET(&solv->dupinvolvedmap, pi); 1247 if (!targeted) 1248 MAPSET(&solv->dupmap, pi); 1249 } 1250 } 1251 if (targeted && s->repo != installed && s->obsoletes) 1252 { 1253 /* XXX: check obsoletes/provides combination */ 1254 obsp = s->repo->idarraydata + s->obsoletes; 1255 while ((obs = *obsp++) != 0) 1256 { 1257 FOR_PROVIDES(pi, pip, obs) 1258 { 1259 Solvable *ps = pool->solvables + pi; 1260 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs)) 1261 continue; 1262 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 1263 continue; 1264 MAPSET(&solv->dupinvolvedmap, pi); 1265 if (targeted && ps->repo == installed && solv->obsoletes && solv->obsoletes[pi - installed->start]) 1266 { 1267 Id *opp, pi2; 1268 for (opp = solv->obsoletes_data + solv->obsoletes[pi - installed->start]; (pi2 = *opp++) != 0;) 1269 if (pool->solvables[pi2].repo != installed) 1270 MAPSET(&solv->dupinvolvedmap, pi2); 1271 } 1272 if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0) 1273 { 1274 if (!solv->bestupdatemap.size) 1275 map_grow(&solv->bestupdatemap, installed->end - installed->start); 1276 MAPSET(&solv->bestupdatemap, pi - installed->start); 1277 } 1278 if (ps->repo == installed && (how & SOLVER_CLEANDEPS) != 0) 1279 add_cleandeps_package(solv, pi); 1280 } 1281 } 1282 } 1283 } 1284 1285 void 1286 solver_createdupmaps(Solver *solv) 1287 { 1288 Queue *job = &solv->job; 1289 Pool *pool = solv->pool; 1290 Repo *installed = solv->installed; 1291 Id select, how, what, p, pp; 1292 Solvable *s; 1293 int i, targeted; 1294 1295 map_init(&solv->dupmap, pool->nsolvables); 1296 map_init(&solv->dupinvolvedmap, pool->nsolvables); 1297 for (i = 0; i < job->count; i += 2) 1298 { 1299 how = job->elements[i]; 1300 select = job->elements[i] & SOLVER_SELECTMASK; 1301 what = job->elements[i + 1]; 1302 switch (how & SOLVER_JOBMASK) 1303 { 1304 case SOLVER_DISTUPGRADE: 1305 if (select == SOLVER_SOLVABLE_REPO) 1306 { 1307 Repo *repo; 1308 if (what <= 0 || what > pool->nrepos) 1309 break; 1310 repo = pool_id2repo(pool, what); 1311 if (!repo) 1312 break; 1313 if (repo != installed && !(how & SOLVER_TARGETED) && solv->noautotarget) 1314 break; 1315 targeted = repo != installed || (how & SOLVER_TARGETED) != 0; 1316 FOR_REPO_SOLVABLES(repo, p, s) 1317 { 1318 if (repo != installed && !pool_installable(pool, s)) 1319 continue; 1320 solver_addtodupmaps(solv, p, how, targeted); 1321 } 1322 } 1323 else 1324 { 1325 targeted = how & SOLVER_TARGETED ? 1 : 0; 1326 if (installed && !targeted && !solv->noautotarget) 1327 { 1328 FOR_JOB_SELECT(p, pp, select, what) 1329 if (pool->solvables[p].repo == installed) 1330 break; 1331 targeted = p == 0; 1332 } 1333 else if (!installed && !solv->noautotarget) 1334 targeted = 1; 1335 FOR_JOB_SELECT(p, pp, select, what) 1336 { 1337 Solvable *s = pool->solvables + p; 1338 if (!s->repo) 1339 continue; 1340 if (s->repo != installed && !targeted) 1341 continue; 1342 if (s->repo != installed && !pool_installable(pool, s)) 1343 continue; 1344 solver_addtodupmaps(solv, p, how, targeted); 1345 } 1346 } 1347 break; 1348 default: 1349 break; 1350 } 1351 } 1352 MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE); 1353 } 1354 1355 void 1356 solver_freedupmaps(Solver *solv) 1357 { 1358 map_free(&solv->dupmap); 1359 /* we no longer free solv->dupinvolvedmap as we need it in 1360 * policy's priority pruning code. sigh. */ 1361 } 1362 1363 void 1364 solver_addduprules(Solver *solv, Map *addedmap) 1365 { 1366 Pool *pool = solv->pool; 1367 Id p, pp; 1368 Solvable *s, *ps; 1369 int first, i; 1370 1371 solv->duprules = solv->nrules; 1372 for (i = 1; i < pool->nsolvables; i++) 1373 { 1374 if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i)) 1375 continue; 1376 s = pool->solvables + i; 1377 first = i; 1378 FOR_PROVIDES(p, pp, s->name) 1379 { 1380 ps = pool->solvables + p; 1381 if (ps->name != s->name || !MAPTST(addedmap, p)) 1382 continue; 1383 if (p == i) 1384 first = 0; 1385 if (first) 1386 break; 1387 if (!MAPTST(&solv->dupinvolvedmap, p)) 1388 continue; 1389 if (solv->installed && ps->repo == solv->installed) 1390 { 1391 if (!solv->updatemap.size) 1392 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start); 1393 MAPSET(&solv->updatemap, p - solv->installed->start); 1394 if (!MAPTST(&solv->dupmap, p)) 1395 { 1396 Id ip, ipp; 1397 /* is installed identical to a good one? */ 1398 FOR_PROVIDES(ip, ipp, ps->name) 1399 { 1400 Solvable *is = pool->solvables + ip; 1401 if (!MAPTST(&solv->dupmap, ip)) 1402 continue; 1403 if (is->evr == ps->evr && solvable_identical(ps, is)) 1404 break; 1405 } 1406 if (!ip) 1407 solver_addrule(solv, -p, 0); /* no match, sorry */ 1408 else 1409 MAPSET(&solv->dupmap, p); /* for best rules processing */ 1410 } 1411 } 1412 else if (!MAPTST(&solv->dupmap, p)) 1413 solver_addrule(solv, -p, 0); 1414 } 1415 } 1416 solv->duprules_end = solv->nrules; 1417 } 1418 1419 1420 static inline void 1421 disableduprule(Solver *solv, Id name) 1422 { 1423 Pool *pool = solv->pool; 1424 Rule *r; 1425 int i; 1426 for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++) 1427 { 1428 if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name) 1429 solver_disablerule(solv, r); 1430 } 1431 } 1432 1433 static inline void 1434 reenableduprule(Solver *solv, Id name) 1435 { 1436 Pool *pool = solv->pool; 1437 Rule *r; 1438 int i; 1439 for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++) 1440 { 1441 if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name) 1442 { 1443 solver_enablerule(solv, r); 1444 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS) 1445 { 1446 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling "); 1447 solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r); 1448 } 1449 } 1450 } 1451 } 1452 1453 1454 /*********************************************************************** 1455 *** 1456 *** Policy rule disabling/reenabling 1457 *** 1458 *** Disable all policy rules that conflict with our jobs. If a job 1459 *** gets disabled later on, reenable the involved policy rules again. 1460 *** 1461 ***/ 1462 1463 #define DISABLE_UPDATE 1 1464 #define DISABLE_INFARCH 2 1465 #define DISABLE_DUP 3 1466 1467 /* 1468 * add all installed packages that package p obsoletes to Queue q. 1469 * Package p is not installed. Also, we know that if 1470 * solv->keepexplicitobsoletes is not set, p is not in the multiversion map. 1471 * Entries may get added multiple times. 1472 */ 1473 static void 1474 add_obsoletes(Solver *solv, Id p, Queue *q) 1475 { 1476 Pool *pool = solv->pool; 1477 Repo *installed = solv->installed; 1478 Id p2, pp2; 1479 Solvable *s = pool->solvables + p; 1480 Id obs, *obsp; 1481 Id lastp2 = 0; 1482 1483 if (!solv->keepexplicitobsoletes || !(solv->multiversion.size && MAPTST(&solv->multiversion, p))) 1484 { 1485 FOR_PROVIDES(p2, pp2, s->name) 1486 { 1487 Solvable *ps = pool->solvables + p2; 1488 if (ps->repo != installed) 1489 continue; 1490 if (!pool->implicitobsoleteusesprovides && ps->name != s->name) 1491 continue; 1492 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 1493 continue; 1494 queue_push(q, p2); 1495 lastp2 = p2; 1496 } 1497 } 1498 if (!s->obsoletes) 1499 return; 1500 obsp = s->repo->idarraydata + s->obsoletes; 1501 while ((obs = *obsp++) != 0) 1502 FOR_PROVIDES(p2, pp2, obs) 1503 { 1504 Solvable *ps = pool->solvables + p2; 1505 if (ps->repo != installed) 1506 continue; 1507 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs)) 1508 continue; 1509 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 1510 continue; 1511 if (p2 == lastp2) 1512 continue; 1513 queue_push(q, p2); 1514 lastp2 = p2; 1515 } 1516 } 1517 1518 /* 1519 * Call add_obsoletes and intersect the result with the 1520 * elements in Queue q starting at qstart. 1521 * Assumes that it's the first call if qstart == q->count. 1522 * May use auxillary map m for the intersection process, all 1523 * elements of q starting at qstart must have their bit cleared. 1524 * (This is also true after the function returns.) 1525 */ 1526 static void 1527 intersect_obsoletes(Solver *solv, Id p, Queue *q, int qstart, Map *m) 1528 { 1529 int i, j; 1530 int qcount = q->count; 1531 1532 add_obsoletes(solv, p, q); 1533 if (qcount == qstart) 1534 return; /* first call */ 1535 if (qcount == q->count) 1536 j = qstart; 1537 else if (qcount == qstart + 1) 1538 { 1539 /* easy if there's just one element */ 1540 j = qstart; 1541 for (i = qcount; i < q->count; i++) 1542 if (q->elements[i] == q->elements[qstart]) 1543 { 1544 j++; /* keep the element */ 1545 break; 1546 } 1547 } 1548 else if (!m->size && q->count - qstart <= 8) 1549 { 1550 /* faster than a map most of the time */ 1551 int k; 1552 for (i = j = qstart; i < qcount; i++) 1553 { 1554 Id ip = q->elements[i]; 1555 for (k = qcount; k < q->count; k++) 1556 if (q->elements[k] == ip) 1557 { 1558 q->elements[j++] = ip; 1559 break; 1560 } 1561 } 1562 } 1563 else 1564 { 1565 /* for the really pathologic cases we use the map */ 1566 Repo *installed = solv->installed; 1567 if (!m->size) 1568 map_init(m, installed->end - installed->start); 1569 for (i = qcount; i < q->count; i++) 1570 MAPSET(m, q->elements[i] - installed->start); 1571 for (i = j = qstart; i < qcount; i++) 1572 if (MAPTST(m, q->elements[i] - installed->start)) 1573 { 1574 MAPCLR(m, q->elements[i] - installed->start); 1575 q->elements[j++] = q->elements[i]; 1576 } 1577 } 1578 queue_truncate(q, j); 1579 } 1580 1581 static void 1582 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q) 1583 { 1584 Pool *pool = solv->pool; 1585 Id select, p, pp; 1586 Repo *installed; 1587 Solvable *s; 1588 int i, j, set, qstart; 1589 Map omap; 1590 1591 installed = solv->installed; 1592 select = how & SOLVER_SELECTMASK; 1593 switch (how & SOLVER_JOBMASK) 1594 { 1595 case SOLVER_INSTALL: 1596 set = how & SOLVER_SETMASK; 1597 if (!(set & SOLVER_NOAUTOSET)) 1598 { 1599 /* automatically add set bits by analysing the job */ 1600 if (select == SOLVER_SOLVABLE_NAME) 1601 set |= SOLVER_SETNAME; 1602 if (select == SOLVER_SOLVABLE) 1603 set |= SOLVER_SETNAME | SOLVER_SETARCH | SOLVER_SETVENDOR | SOLVER_SETREPO | SOLVER_SETEVR; 1604 else if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(what)) 1605 { 1606 Reldep *rd = GETRELDEP(pool, what); 1607 if (rd->flags == REL_EQ && select == SOLVER_SOLVABLE_NAME) 1608 { 1609 if (pool->disttype != DISTTYPE_DEB) 1610 { 1611 const char *rel = strrchr(pool_id2str(pool, rd->evr), '-'); 1612 set |= rel ? SOLVER_SETEVR : SOLVER_SETEV; 1613 } 1614 else 1615 set |= SOLVER_SETEVR; 1616 } 1617 if (rd->flags <= 7 && ISRELDEP(rd->name)) 1618 rd = GETRELDEP(pool, rd->name); 1619 if (rd->flags == REL_ARCH) 1620 set |= SOLVER_SETARCH; 1621 } 1622 } 1623 else 1624 set &= ~SOLVER_NOAUTOSET; 1625 if (!set) 1626 return; 1627 if ((set & SOLVER_SETARCH) != 0 && solv->infarchrules != solv->infarchrules_end) 1628 { 1629 if (select == SOLVER_SOLVABLE) 1630 queue_push2(q, DISABLE_INFARCH, pool->solvables[what].name); 1631 else 1632 { 1633 int qcnt = q->count; 1634 /* does not work for SOLVER_SOLVABLE_ALL and SOLVER_SOLVABLE_REPO, but 1635 they are not useful for SOLVER_INSTALL jobs anyway */ 1636 FOR_JOB_SELECT(p, pp, select, what) 1637 { 1638 s = pool->solvables + p; 1639 /* unify names */ 1640 for (i = qcnt; i < q->count; i += 2) 1641 if (q->elements[i + 1] == s->name) 1642 break; 1643 if (i < q->count) 1644 continue; 1645 queue_push2(q, DISABLE_INFARCH, s->name); 1646 } 1647 } 1648 } 1649 if ((set & SOLVER_SETREPO) != 0 && solv->duprules != solv->duprules_end) 1650 { 1651 if (select == SOLVER_SOLVABLE) 1652 queue_push2(q, DISABLE_DUP, pool->solvables[what].name); 1653 else 1654 { 1655 int qcnt = q->count; 1656 FOR_JOB_SELECT(p, pp, select, what) 1657 { 1658 s = pool->solvables + p; 1659 /* unify names */ 1660 for (i = qcnt; i < q->count; i += 2) 1661 if (q->elements[i + 1] == s->name) 1662 break; 1663 if (i < q->count) 1664 continue; 1665 queue_push2(q, DISABLE_DUP, s->name); 1666 } 1667 } 1668 } 1669 if (!installed || installed->end == installed->start) 1670 return; 1671 /* now the hard part: disable some update rules */ 1672 1673 /* first check if we have multiversion or installed packages in the job */ 1674 i = j = 0; 1675 FOR_JOB_SELECT(p, pp, select, what) 1676 { 1677 if (pool->solvables[p].repo == installed) 1678 j = p; 1679 else if (solv->multiversion.size && MAPTST(&solv->multiversion, p) && !solv->keepexplicitobsoletes) 1680 return; 1681 i++; 1682 } 1683 if (j) /* have installed packages */ 1684 { 1685 /* this is for dupmap_all jobs, it can go away if we create 1686 * duprules for them */ 1687 if (i == 1 && (set & SOLVER_SETREPO) != 0) 1688 queue_push2(q, DISABLE_UPDATE, j); 1689 return; 1690 } 1691 1692 omap.size = 0; 1693 qstart = q->count; 1694 FOR_JOB_SELECT(p, pp, select, what) 1695 { 1696 intersect_obsoletes(solv, p, q, qstart, &omap); 1697 if (q->count == qstart) 1698 break; 1699 } 1700 if (omap.size) 1701 map_free(&omap); 1702 1703 if (qstart == q->count) 1704 return; /* nothing to prune */ 1705 1706 /* convert result to (DISABLE_UPDATE, p) pairs */ 1707 i = q->count; 1708 for (j = qstart; j < i; j++) 1709 queue_push(q, q->elements[j]); 1710 for (j = qstart; j < q->count; j += 2) 1711 { 1712 q->elements[j] = DISABLE_UPDATE; 1713 q->elements[j + 1] = q->elements[i++]; 1714 } 1715 1716 /* now that we know which installed packages are obsoleted check each of them */ 1717 if ((set & (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) == (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) 1718 return; /* all is set, nothing to do */ 1719 1720 for (i = j = qstart; i < q->count; i += 2) 1721 { 1722 Solvable *is = pool->solvables + q->elements[i + 1]; 1723 FOR_JOB_SELECT(p, pp, select, what) 1724 { 1725 int illegal = 0; 1726 s = pool->solvables + p; 1727 if ((set & SOLVER_SETEVR) != 0) 1728 illegal |= POLICY_ILLEGAL_DOWNGRADE; /* ignore */ 1729 if ((set & SOLVER_SETNAME) != 0) 1730 illegal |= POLICY_ILLEGAL_NAMECHANGE; /* ignore */ 1731 if ((set & SOLVER_SETARCH) != 0) 1732 illegal |= POLICY_ILLEGAL_ARCHCHANGE; /* ignore */ 1733 if ((set & SOLVER_SETVENDOR) != 0) 1734 illegal |= POLICY_ILLEGAL_VENDORCHANGE; /* ignore */ 1735 illegal = policy_is_illegal(solv, is, s, illegal); 1736 if (illegal && illegal == POLICY_ILLEGAL_DOWNGRADE && (set & SOLVER_SETEV) != 0) 1737 { 1738 /* it's ok if the EV is different */ 1739 if (pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE_EVONLY) != 0) 1740 illegal = 0; 1741 } 1742 if (illegal) 1743 break; 1744 } 1745 if (!p) 1746 { 1747 /* no package conflicts with the update rule */ 1748 /* thus keep the DISABLE_UPDATE */ 1749 q->elements[j + 1] = q->elements[i + 1]; 1750 j += 2; 1751 } 1752 } 1753 queue_truncate(q, j); 1754 return; 1755 1756 case SOLVER_ERASE: 1757 if (!installed) 1758 break; 1759 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid)) 1760 FOR_REPO_SOLVABLES(installed, p, s) 1761 queue_push2(q, DISABLE_UPDATE, p); 1762 FOR_JOB_SELECT(p, pp, select, what) 1763 if (pool->solvables[p].repo == installed) 1764 queue_push2(q, DISABLE_UPDATE, p); 1765 return; 1766 default: 1767 return; 1768 } 1769 } 1770 1771 /* disable all policy rules that are in conflict with our job list */ 1772 void 1773 solver_disablepolicyrules(Solver *solv) 1774 { 1775 Queue *job = &solv->job; 1776 int i, j; 1777 Queue allq; 1778 Rule *r; 1779 Id lastjob = -1; 1780 Id allqbuf[128]; 1781 1782 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf)); 1783 1784 for (i = solv->jobrules; i < solv->jobrules_end; i++) 1785 { 1786 r = solv->rules + i; 1787 if (r->d < 0) /* disabled? */ 1788 continue; 1789 j = solv->ruletojob.elements[i - solv->jobrules]; 1790 if (j == lastjob) 1791 continue; 1792 lastjob = j; 1793 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq); 1794 } 1795 if (solv->cleandepsmap.size) 1796 { 1797 solver_createcleandepsmap(solv, &solv->cleandepsmap, 0); 1798 for (i = solv->installed->start; i < solv->installed->end; i++) 1799 if (MAPTST(&solv->cleandepsmap, i - solv->installed->start)) 1800 queue_push2(&allq, DISABLE_UPDATE, i); 1801 } 1802 MAPZERO(&solv->noupdate); 1803 for (i = 0; i < allq.count; i += 2) 1804 { 1805 Id type = allq.elements[i], arg = allq.elements[i + 1]; 1806 switch(type) 1807 { 1808 case DISABLE_UPDATE: 1809 disableupdaterule(solv, arg); 1810 break; 1811 case DISABLE_INFARCH: 1812 disableinfarchrule(solv, arg); 1813 break; 1814 case DISABLE_DUP: 1815 disableduprule(solv, arg); 1816 break; 1817 default: 1818 break; 1819 } 1820 } 1821 queue_free(&allq); 1822 } 1823 1824 /* we just disabled job #jobidx, now reenable all policy rules that were 1825 * disabled because of this job */ 1826 void 1827 solver_reenablepolicyrules(Solver *solv, int jobidx) 1828 { 1829 Queue *job = &solv->job; 1830 int i, j, k, ai; 1831 Queue q, allq; 1832 Rule *r; 1833 Id lastjob = -1; 1834 Id qbuf[32], allqbuf[32]; 1835 1836 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf)); 1837 jobtodisablelist(solv, job->elements[jobidx - 1], job->elements[jobidx], &q); 1838 if (!q.count) 1839 { 1840 queue_free(&q); 1841 return; 1842 } 1843 /* now remove everything from q that is disabled by other jobs */ 1844 1845 /* first remove cleandeps packages, they count as DISABLE_UPDATE */ 1846 if (solv->cleandepsmap.size) 1847 { 1848 solver_createcleandepsmap(solv, &solv->cleandepsmap, 0); 1849 for (j = k = 0; j < q.count; j += 2) 1850 { 1851 if (q.elements[j] == DISABLE_UPDATE) 1852 { 1853 Id p = q.elements[j + 1]; 1854 if (p >= solv->installed->start && p < solv->installed->end && MAPTST(&solv->cleandepsmap, p - solv->installed->start)) 1855 continue; /* remove element from q */ 1856 } 1857 q.elements[k++] = q.elements[j]; 1858 q.elements[k++] = q.elements[j + 1]; 1859 } 1860 q.count = k; 1861 if (!q.count) 1862 { 1863 queue_free(&q); 1864 return; 1865 } 1866 } 1867 1868 /* now go through the disable list of all other jobs */ 1869 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf)); 1870 for (i = solv->jobrules; i < solv->jobrules_end; i++) 1871 { 1872 r = solv->rules + i; 1873 if (r->d < 0) /* disabled? */ 1874 continue; 1875 j = solv->ruletojob.elements[i - solv->jobrules]; 1876 if (j == lastjob) 1877 continue; 1878 lastjob = j; 1879 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq); 1880 if (!allq.count) 1881 continue; 1882 /* remove all elements in allq from q */ 1883 for (j = k = 0; j < q.count; j += 2) 1884 { 1885 Id type = q.elements[j], arg = q.elements[j + 1]; 1886 for (ai = 0; ai < allq.count; ai += 2) 1887 if (allq.elements[ai] == type && allq.elements[ai + 1] == arg) 1888 break; 1889 if (ai < allq.count) 1890 continue; /* found it in allq, remove element from q */ 1891 q.elements[k++] = q.elements[j]; 1892 q.elements[k++] = q.elements[j + 1]; 1893 } 1894 q.count = k; 1895 if (!q.count) 1896 { 1897 queue_free(&q); 1898 queue_free(&allq); 1899 return; 1900 } 1901 queue_empty(&allq); 1902 } 1903 queue_free(&allq); 1904 1905 /* now re-enable anything that's left in q */ 1906 for (j = 0; j < q.count; j += 2) 1907 { 1908 Id type = q.elements[j], arg = q.elements[j + 1]; 1909 switch(type) 1910 { 1911 case DISABLE_UPDATE: 1912 reenableupdaterule(solv, arg); 1913 break; 1914 case DISABLE_INFARCH: 1915 reenableinfarchrule(solv, arg); 1916 break; 1917 case DISABLE_DUP: 1918 reenableduprule(solv, arg); 1919 break; 1920 } 1921 } 1922 queue_free(&q); 1923 } 1924 1925 /* we just removed a package from the cleandeps map, now reenable all policy rules that were 1926 * disabled because of this */ 1927 void 1928 solver_reenablepolicyrules_cleandeps(Solver *solv, Id pkg) 1929 { 1930 Queue *job = &solv->job; 1931 int i, j; 1932 Queue allq; 1933 Rule *r; 1934 Id lastjob = -1; 1935 Id allqbuf[128]; 1936 1937 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf)); 1938 for (i = solv->jobrules; i < solv->jobrules_end; i++) 1939 { 1940 r = solv->rules + i; 1941 if (r->d < 0) /* disabled? */ 1942 continue; 1943 j = solv->ruletojob.elements[i - solv->jobrules]; 1944 if (j == lastjob) 1945 continue; 1946 lastjob = j; 1947 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq); 1948 } 1949 for (i = 0; i < allq.count; i += 2) 1950 if (allq.elements[i] == DISABLE_UPDATE && allq.elements[i + 1] == pkg) 1951 break; 1952 if (i == allq.count) 1953 reenableupdaterule(solv, pkg); 1954 queue_free(&allq); 1955 } 1956 1957 1958 /*********************************************************************** 1959 *** 1960 *** Rule info part, tell the user what the rule is about. 1961 *** 1962 ***/ 1963 1964 static void 1965 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep) 1966 { 1967 Pool *pool = solv->pool; 1968 Rule *r; 1969 Id w2, op, od, ow2; 1970 1971 /* check if this creates the rule we're searching for */ 1972 r = solv->rules + solv->ruleinfoq->elements[0]; 1973 op = r->p; 1974 od = r->d < 0 ? -r->d - 1 : r->d; 1975 ow2 = 0; 1976 1977 /* normalize */ 1978 w2 = d > 0 ? 0 : d; 1979 if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1])) 1980 { 1981 w2 = pool->whatprovidesdata[d]; 1982 d = 0; 1983 1984 } 1985 if (p > 0 && d < 0) /* this hack is used for buddy deps */ 1986 { 1987 w2 = p; 1988 p = d; 1989 } 1990 1991 if (d > 0) 1992 { 1993 if (p != op && !od) 1994 return; 1995 if (d != od) 1996 { 1997 Id *dp = pool->whatprovidesdata + d; 1998 Id *odp = pool->whatprovidesdata + od; 1999 while (*dp) 2000 if (*dp++ != *odp++) 2001 return; 2002 if (*odp) 2003 return; 2004 } 2005 w2 = 0; 2006 /* handle multiversion conflict rules */ 2007 if (p < 0 && pool->whatprovidesdata[d] < 0) 2008 { 2009 w2 = pool->whatprovidesdata[d]; 2010 /* XXX: free memory */ 2011 } 2012 } 2013 else 2014 { 2015 if (od) 2016 return; 2017 ow2 = r->w2; 2018 if (p > w2) 2019 { 2020 if (w2 != op || p != ow2) 2021 return; 2022 } 2023 else 2024 { 2025 if (p != op || w2 != ow2) 2026 return; 2027 } 2028 } 2029 /* yep, rule matches. record info */ 2030 queue_push(solv->ruleinfoq, type); 2031 if (type == SOLVER_RULE_RPM_SAME_NAME) 2032 { 2033 /* we normalize same name order */ 2034 queue_push(solv->ruleinfoq, op < 0 ? -op : 0); 2035 queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0); 2036 } 2037 else 2038 { 2039 queue_push(solv->ruleinfoq, p < 0 ? -p : 0); 2040 queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0); 2041 } 2042 queue_push(solv->ruleinfoq, dep); 2043 } 2044 2045 static int 2046 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp) 2047 { 2048 const Id *a = ap, *b = bp; 2049 int r; 2050 2051 r = a[0] - b[0]; 2052 if (r) 2053 return r; 2054 r = a[1] - b[1]; 2055 if (r) 2056 return r; 2057 r = a[2] - b[2]; 2058 if (r) 2059 return r; 2060 r = a[3] - b[3]; 2061 if (r) 2062 return r; 2063 return 0; 2064 } 2065 2066 int 2067 solver_allruleinfos(Solver *solv, Id rid, Queue *rq) 2068 { 2069 Pool *pool = solv->pool; 2070 Rule *r = solv->rules + rid; 2071 int i, j; 2072 2073 queue_empty(rq); 2074 if (rid <= 0 || rid >= solv->rpmrules_end) 2075 { 2076 Id type, from, to, dep; 2077 type = solver_ruleinfo(solv, rid, &from, &to, &dep); 2078 queue_push(rq, type); 2079 queue_push(rq, from); 2080 queue_push(rq, to); 2081 queue_push(rq, dep); 2082 return 1; 2083 } 2084 if (r->p >= 0) 2085 return 0; 2086 queue_push(rq, rid); 2087 solv->ruleinfoq = rq; 2088 solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0); 2089 /* also try reverse direction for conflicts */ 2090 if ((r->d == 0 || r->d == -1) && r->w2 < 0) 2091 solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0); 2092 solv->ruleinfoq = 0; 2093 queue_shift(rq); 2094 /* now sort & unify em */ 2095 if (!rq->count) 2096 return 0; 2097 solv_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0); 2098 /* throw out identical entries */ 2099 for (i = j = 0; i < rq->count; i += 4) 2100 { 2101 if (j) 2102 { 2103 if (rq->elements[i] == rq->elements[j - 4] && 2104 rq->elements[i + 1] == rq->elements[j - 3] && 2105 rq->elements[i + 2] == rq->elements[j - 2] && 2106 rq->elements[i + 3] == rq->elements[j - 1]) 2107 continue; 2108 } 2109 rq->elements[j++] = rq->elements[i]; 2110 rq->elements[j++] = rq->elements[i + 1]; 2111 rq->elements[j++] = rq->elements[i + 2]; 2112 rq->elements[j++] = rq->elements[i + 3]; 2113 } 2114 rq->count = j; 2115 return j / 4; 2116 } 2117 2118 SolverRuleinfo 2119 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp) 2120 { 2121 Pool *pool = solv->pool; 2122 Rule *r = solv->rules + rid; 2123 SolverRuleinfo type = SOLVER_RULE_UNKNOWN; 2124 2125 if (fromp) 2126 *fromp = 0; 2127 if (top) 2128 *top = 0; 2129 if (depp) 2130 *depp = 0; 2131 if (rid > 0 && rid < solv->rpmrules_end) 2132 { 2133 Queue rq; 2134 int i; 2135 2136 if (r->p >= 0) 2137 return SOLVER_RULE_RPM; 2138 if (fromp) 2139 *fromp = -r->p; 2140 queue_init(&rq); 2141 queue_push(&rq, rid); 2142 solv->ruleinfoq = &rq; 2143 solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0); 2144 /* also try reverse direction for conflicts */ 2145 if ((r->d == 0 || r->d == -1) && r->w2 < 0) 2146 solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0); 2147 solv->ruleinfoq = 0; 2148 type = SOLVER_RULE_RPM; 2149 for (i = 1; i < rq.count; i += 4) 2150 { 2151 Id qt, qo, qp, qd; 2152 qt = rq.elements[i]; 2153 qp = rq.elements[i + 1]; 2154 qo = rq.elements[i + 2]; 2155 qd = rq.elements[i + 3]; 2156 if (type == SOLVER_RULE_RPM || type > qt) 2157 { 2158 type = qt; 2159 if (fromp) 2160 *fromp = qp; 2161 if (top) 2162 *top = qo; 2163 if (depp) 2164 *depp = qd; 2165 } 2166 } 2167 queue_free(&rq); 2168 return type; 2169 } 2170 if (rid >= solv->jobrules && rid < solv->jobrules_end) 2171 { 2172 Id jidx = solv->ruletojob.elements[rid - solv->jobrules]; 2173 if (fromp) 2174 *fromp = jidx; 2175 if (top) 2176 *top = solv->job.elements[jidx]; 2177 if (depp) 2178 *depp = solv->job.elements[jidx + 1]; 2179 if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE) 2180 { 2181 if ((solv->job.elements[jidx] & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_INSTALL|SOLVER_SOLVABLE_NAME)) 2182 return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP; 2183 if ((solv->job.elements[jidx] & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_INSTALL|SOLVER_SOLVABLE_PROVIDES)) 2184 return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP; 2185 if ((solv->job.elements[jidx] & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_ERASE|SOLVER_SOLVABLE_NAME)) 2186 return SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM; 2187 if ((solv->job.elements[jidx] & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_ERASE|SOLVER_SOLVABLE_PROVIDES)) 2188 return SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM; 2189 } 2190 return SOLVER_RULE_JOB; 2191 } 2192 if (rid >= solv->updaterules && rid < solv->updaterules_end) 2193 { 2194 if (fromp) 2195 *fromp = solv->installed->start + (rid - solv->updaterules); 2196 return SOLVER_RULE_UPDATE; 2197 } 2198 if (rid >= solv->featurerules && rid < solv->featurerules_end) 2199 { 2200 if (fromp) 2201 *fromp = solv->installed->start + (rid - solv->featurerules); 2202 return SOLVER_RULE_FEATURE; 2203 } 2204 if (rid >= solv->duprules && rid < solv->duprules_end) 2205 { 2206 if (fromp) 2207 *fromp = -r->p; 2208 if (depp) 2209 *depp = pool->solvables[-r->p].name; 2210 return SOLVER_RULE_DISTUPGRADE; 2211 } 2212 if (rid >= solv->infarchrules && rid < solv->infarchrules_end) 2213 { 2214 if (fromp) 2215 *fromp = -r->p; 2216 if (depp) 2217 *depp = pool->solvables[-r->p].name; 2218 return SOLVER_RULE_INFARCH; 2219 } 2220 if (rid >= solv->bestrules && rid < solv->bestrules_end) 2221 { 2222 return SOLVER_RULE_BEST; 2223 } 2224 if (rid >= solv->choicerules && rid < solv->choicerules_end) 2225 { 2226 return SOLVER_RULE_CHOICE; 2227 } 2228 if (rid >= solv->learntrules) 2229 { 2230 return SOLVER_RULE_LEARNT; 2231 } 2232 return SOLVER_RULE_UNKNOWN; 2233 } 2234 2235 SolverRuleinfo 2236 solver_ruleclass(Solver *solv, Id rid) 2237 { 2238 if (rid <= 0) 2239 return SOLVER_RULE_UNKNOWN; 2240 if (rid > 0 && rid < solv->rpmrules_end) 2241 return SOLVER_RULE_RPM; 2242 if (rid >= solv->jobrules && rid < solv->jobrules_end) 2243 return SOLVER_RULE_JOB; 2244 if (rid >= solv->updaterules && rid < solv->updaterules_end) 2245 return SOLVER_RULE_UPDATE; 2246 if (rid >= solv->featurerules && rid < solv->featurerules_end) 2247 return SOLVER_RULE_FEATURE; 2248 if (rid >= solv->duprules && rid < solv->duprules_end) 2249 return SOLVER_RULE_DISTUPGRADE; 2250 if (rid >= solv->infarchrules && rid < solv->infarchrules_end) 2251 return SOLVER_RULE_INFARCH; 2252 if (rid >= solv->bestrules && rid < solv->bestrules_end) 2253 return SOLVER_RULE_BEST; 2254 if (rid >= solv->choicerules && rid < solv->choicerules_end) 2255 return SOLVER_RULE_CHOICE; 2256 if (rid >= solv->learntrules) 2257 return SOLVER_RULE_LEARNT; 2258 return SOLVER_RULE_UNKNOWN; 2259 } 2260 2261 void 2262 solver_ruleliterals(Solver *solv, Id rid, Queue *q) 2263 { 2264 Pool *pool = solv->pool; 2265 Id p, pp; 2266 Rule *r; 2267 2268 queue_empty(q); 2269 r = solv->rules + rid; 2270 FOR_RULELITERALS(p, pp, r) 2271 if (p != -SYSTEMSOLVABLE) 2272 queue_push(q, p); 2273 if (!q->count) 2274 queue_push(q, -SYSTEMSOLVABLE); /* hmm, better to return an empty result? */ 2275 } 2276 2277 int 2278 solver_rule2jobidx(Solver *solv, Id rid) 2279 { 2280 if (rid < solv->jobrules || rid >= solv->jobrules_end) 2281 return 0; 2282 return solv->ruletojob.elements[rid - solv->jobrules] + 1; 2283 } 2284 2285 Id 2286 solver_rule2job(Solver *solv, Id rid, Id *whatp) 2287 { 2288 int idx; 2289 if (rid < solv->jobrules || rid >= solv->jobrules_end) 2290 { 2291 if (whatp) 2292 *whatp = 0; 2293 return 0; 2294 } 2295 idx = solv->ruletojob.elements[rid - solv->jobrules]; 2296 if (whatp) 2297 *whatp = solv->job.elements[idx + 1]; 2298 return solv->job.elements[idx]; 2299 } 2300 2301 /* check if the newest versions of pi still provides the dependency we're looking for */ 2302 static int 2303 solver_choicerulecheck(Solver *solv, Id pi, Rule *r, Map *m) 2304 { 2305 Pool *pool = solv->pool; 2306 Rule *ur; 2307 Queue q; 2308 Id p, pp, qbuf[32]; 2309 int i; 2310 2311 ur = solv->rules + solv->updaterules + (pi - pool->installed->start); 2312 if (!ur->p) 2313 ur = solv->rules + solv->featurerules + (pi - pool->installed->start); 2314 if (!ur->p) 2315 return 0; 2316 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf)); 2317 FOR_RULELITERALS(p, pp, ur) 2318 if (p > 0) 2319 queue_push(&q, p); 2320 if (q.count > 1) 2321 policy_filter_unwanted(solv, &q, POLICY_MODE_CHOOSE); 2322 for (i = 0; i < q.count; i++) 2323 if (MAPTST(m, q.elements[i])) 2324 break; 2325 /* 1: none of the newest versions provide it */ 2326 i = i == q.count ? 1 : 0; 2327 queue_free(&q); 2328 return i; 2329 } 2330 2331 static inline void 2332 queue_removeelement(Queue *q, Id el) 2333 { 2334 int i, j; 2335 for (i = 0; i < q->count; i++) 2336 if (q->elements[i] == el) 2337 break; 2338 if (i < q->count) 2339 { 2340 for (j = i++; i < q->count; i++) 2341 if (q->elements[i] != el) 2342 q->elements[j++] = q->elements[i]; 2343 queue_truncate(q, j); 2344 } 2345 } 2346 2347 void 2348 solver_addchoicerules(Solver *solv) 2349 { 2350 Pool *pool = solv->pool; 2351 Map m, mneg; 2352 Rule *r; 2353 Queue q, qi; 2354 int i, j, rid, havechoice; 2355 Id p, d, pp; 2356 Id p2, pp2; 2357 Solvable *s, *s2; 2358 Id lastaddedp, lastaddedd; 2359 int lastaddedcnt; 2360 unsigned int now; 2361 2362 solv->choicerules = solv->nrules; 2363 if (!pool->installed) 2364 { 2365 solv->choicerules_end = solv->nrules; 2366 return; 2367 } 2368 now = solv_timems(0); 2369 solv->choicerules_ref = solv_calloc(solv->rpmrules_end, sizeof(Id)); 2370 queue_init(&q); 2371 queue_init(&qi); 2372 map_init(&m, pool->nsolvables); 2373 map_init(&mneg, pool->nsolvables); 2374 /* set up negative assertion map from infarch and dup rules */ 2375 for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++) 2376 if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1)) 2377 MAPSET(&mneg, -r->p); 2378 for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++) 2379 if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1)) 2380 MAPSET(&mneg, -r->p); 2381 lastaddedp = 0; 2382 lastaddedd = 0; 2383 lastaddedcnt = 0; 2384 for (rid = 1; rid < solv->rpmrules_end ; rid++) 2385 { 2386 r = solv->rules + rid; 2387 if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0)) 2388 continue; /* only look at requires rules */ 2389 /* solver_printrule(solv, SOLV_DEBUG_RESULT, r); */ 2390 queue_empty(&q); 2391 queue_empty(&qi); 2392 havechoice = 0; 2393 FOR_RULELITERALS(p, pp, r) 2394 { 2395 if (p < 0) 2396 continue; 2397 s = pool->solvables + p; 2398 if (!s->repo) 2399 continue; 2400 if (s->repo == pool->installed) 2401 { 2402 queue_push(&q, p); 2403 continue; 2404 } 2405 /* check if this package is "blocked" by a installed package */ 2406 s2 = 0; 2407 FOR_PROVIDES(p2, pp2, s->name) 2408 { 2409 s2 = pool->solvables + p2; 2410 if (s2->repo != pool->installed) 2411 continue; 2412 if (!pool->implicitobsoleteusesprovides && s->name != s2->name) 2413 continue; 2414 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2)) 2415 continue; 2416 break; 2417 } 2418 if (p2) 2419 { 2420 /* found installed package p2 that we can update to p */ 2421 if (MAPTST(&mneg, p)) 2422 continue; 2423 if (policy_is_illegal(solv, s2, s, 0)) 2424 continue; 2425 #if 0 2426 if (solver_choicerulecheck(solv, p2, r, &m)) 2427 continue; 2428 queue_push(&qi, p2); 2429 #else 2430 queue_push2(&qi, p2, p); 2431 #endif 2432 queue_push(&q, p); 2433 continue; 2434 } 2435 if (s->obsoletes) 2436 { 2437 Id obs, *obsp = s->repo->idarraydata + s->obsoletes; 2438 s2 = 0; 2439 while ((obs = *obsp++) != 0) 2440 { 2441 FOR_PROVIDES(p2, pp2, obs) 2442 { 2443 s2 = pool->solvables + p2; 2444 if (s2->repo != pool->installed) 2445 continue; 2446 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs)) 2447 continue; 2448 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2)) 2449 continue; 2450 break; 2451 } 2452 if (p2) 2453 break; 2454 } 2455 if (obs) 2456 { 2457 /* found installed package p2 that we can update to p */ 2458 if (MAPTST(&mneg, p)) 2459 continue; 2460 if (policy_is_illegal(solv, s2, s, 0)) 2461 continue; 2462 #if 0 2463 if (solver_choicerulecheck(solv, p2, r, &m)) 2464 continue; 2465 queue_push(&qi, p2); 2466 #else 2467 queue_push2(&qi, p2, p); 2468 #endif 2469 queue_push(&q, p); 2470 continue; 2471 } 2472 } 2473 /* package p is independent of the installed ones */ 2474 havechoice = 1; 2475 } 2476 if (!havechoice || !q.count || !qi.count) 2477 continue; /* no choice */ 2478 2479 FOR_RULELITERALS(p, pp, r) 2480 if (p > 0) 2481 MAPSET(&m, p); 2482 2483 /* do extra checking */ 2484 for (i = j = 0; i < qi.count; i += 2) 2485 { 2486 p2 = qi.elements[i]; 2487 if (!p2) 2488 continue; 2489 if (solver_choicerulecheck(solv, p2, r, &m)) 2490 { 2491 /* oops, remove element p from q */ 2492 queue_removeelement(&q, qi.elements[i + 1]); 2493 continue; 2494 } 2495 qi.elements[j++] = p2; 2496 } 2497 queue_truncate(&qi, j); 2498 if (!q.count || !qi.count) 2499 { 2500 FOR_RULELITERALS(p, pp, r) 2501 if (p > 0) 2502 MAPCLR(&m, p); 2503 continue; 2504 } 2505 2506 2507 /* now check the update rules of the installed package. 2508 * if all packages of the update rules are contained in 2509 * the dependency rules, there's no need to set up the choice rule */ 2510 for (i = 0; i < qi.count; i++) 2511 { 2512 Rule *ur; 2513 if (!qi.elements[i]) 2514 continue; 2515 ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start); 2516 if (!ur->p) 2517 ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start); 2518 if (!ur->p) 2519 continue; 2520 FOR_RULELITERALS(p, pp, ur) 2521 if (!MAPTST(&m, p)) 2522 break; 2523 if (p) 2524 break; 2525 for (j = i + 1; j < qi.count; j++) 2526 if (qi.elements[i] == qi.elements[j]) 2527 qi.elements[j] = 0; 2528 } 2529 /* empty map again */ 2530 FOR_RULELITERALS(p, pp, r) 2531 if (p > 0) 2532 MAPCLR(&m, p); 2533 if (i == qi.count) 2534 { 2535 #if 0 2536 printf("skipping choice "); 2537 solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid); 2538 #endif 2539 continue; 2540 } 2541 2542 /* don't add identical rules */ 2543 if (lastaddedp == r->p && lastaddedcnt == q.count) 2544 { 2545 for (i = 0; i < q.count; i++) 2546 if (q.elements[i] != pool->whatprovidesdata[lastaddedd + i]) 2547 break; 2548 if (i == q.count) 2549 continue; /* already added that one */ 2550 } 2551 d = q.count ? pool_queuetowhatprovides(pool, &q) : 0; 2552 2553 lastaddedp = r->p; 2554 lastaddedd = d; 2555 lastaddedcnt = q.count; 2556 2557 solver_addrule(solv, r->p, d); 2558 queue_push(&solv->weakruleq, solv->nrules - 1); 2559 solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid; 2560 #if 0 2561 printf("OLD "); 2562 solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid); 2563 printf("WEAK CHOICE "); 2564 solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + solv->nrules - 1); 2565 #endif 2566 } 2567 queue_free(&q); 2568 queue_free(&qi); 2569 map_free(&m); 2570 map_free(&mneg); 2571 solv->choicerules_end = solv->nrules; 2572 /* shrink choicerules_ref */ 2573 solv->choicerules_ref = solv_realloc2(solv->choicerules_ref, solv->choicerules_end - solv->choicerules, sizeof(Id)); 2574 POOL_DEBUG(SOLV_DEBUG_STATS, "choice rule creation took %d ms\n", solv_timems(now)); 2575 } 2576 2577 /* called when a choice rule is disabled by analyze_unsolvable. We also 2578 * have to disable all other choice rules so that the best packages get 2579 * picked */ 2580 void 2581 solver_disablechoicerules(Solver *solv, Rule *r) 2582 { 2583 Id rid, p, pp; 2584 Pool *pool = solv->pool; 2585 Map m; 2586 Rule *or; 2587 2588 or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules]; 2589 map_init(&m, pool->nsolvables); 2590 FOR_RULELITERALS(p, pp, or) 2591 if (p > 0) 2592 MAPSET(&m, p); 2593 FOR_RULELITERALS(p, pp, r) 2594 if (p > 0) 2595 MAPCLR(&m, p); 2596 for (rid = solv->choicerules; rid < solv->choicerules_end; rid++) 2597 { 2598 r = solv->rules + rid; 2599 if (r->d < 0) 2600 continue; 2601 or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules]; 2602 FOR_RULELITERALS(p, pp, or) 2603 if (p > 0 && MAPTST(&m, p)) 2604 break; 2605 if (p) 2606 solver_disablerule(solv, r); 2607 } 2608 } 2609 2610 static void 2611 prune_to_update_targets(Solver *solv, Id *cp, Queue *q) 2612 { 2613 int i, j; 2614 Id p, *cp2; 2615 for (i = j = 0; i < q->count; i++) 2616 { 2617 p = q->elements[i]; 2618 for (cp2 = cp; *cp2; cp2++) 2619 if (*cp2 == p) 2620 { 2621 q->elements[j++] = p; 2622 break; 2623 } 2624 } 2625 queue_truncate(q, j); 2626 } 2627 2628 static void 2629 prune_to_dup_packages(Solver *solv, Id p, Queue *q) 2630 { 2631 int i, j; 2632 for (i = j = 0; i < q->count; i++) 2633 { 2634 Id p = q->elements[i]; 2635 if (MAPTST(&solv->dupmap, p)) 2636 q->elements[j++] = p; 2637 } 2638 queue_truncate(q, j); 2639 } 2640 2641 void 2642 solver_addbestrules(Solver *solv, int havebestinstalljobs) 2643 { 2644 Pool *pool = solv->pool; 2645 Id p; 2646 Solvable *s; 2647 Repo *installed = solv->installed; 2648 Queue q, q2; 2649 Rule *r; 2650 Queue r2pkg; 2651 int i, oldcnt; 2652 2653 solv->bestrules = solv->nrules; 2654 if (!installed) 2655 { 2656 solv->bestrules_end = solv->nrules; 2657 return; 2658 } 2659 queue_init(&q); 2660 queue_init(&q2); 2661 queue_init(&r2pkg); 2662 2663 if (havebestinstalljobs) 2664 { 2665 for (i = 0; i < solv->job.count; i += 2) 2666 { 2667 if ((solv->job.elements[i] & (SOLVER_JOBMASK | SOLVER_FORCEBEST)) == (SOLVER_INSTALL | SOLVER_FORCEBEST)) 2668 { 2669 int j; 2670 Id p2, pp2; 2671 for (j = 0; j < solv->ruletojob.count; j++) 2672 if (solv->ruletojob.elements[j] == i) 2673 break; 2674 if (j == solv->ruletojob.count) 2675 continue; 2676 r = solv->rules + solv->jobrules + j; 2677 queue_empty(&q); 2678 FOR_RULELITERALS(p2, pp2, r) 2679 if (p2 > 0) 2680 queue_push(&q, p2); 2681 if (!q.count) 2682 continue; /* orphaned */ 2683 /* select best packages, just look at prio and version */ 2684 oldcnt = q.count; 2685 policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND); 2686 if (q.count == oldcnt) 2687 continue; /* nothing filtered */ 2688 p2 = queue_shift(&q); 2689 solver_addrule(solv, p2, q.count ? pool_queuetowhatprovides(pool, &q) : 0); 2690 queue_push(&r2pkg, -(solv->jobrules + j)); 2691 } 2692 } 2693 } 2694 2695 if (solv->bestupdatemap_all || solv->bestupdatemap.size) 2696 { 2697 FOR_REPO_SOLVABLES(installed, p, s) 2698 { 2699 Id d, p2, pp2; 2700 if (!solv->updatemap_all && (!solv->updatemap.size || !MAPTST(&solv->updatemap, p - installed->start))) 2701 continue; 2702 if (!solv->bestupdatemap_all && (!solv->bestupdatemap.size || !MAPTST(&solv->bestupdatemap, p - installed->start))) 2703 continue; 2704 queue_empty(&q); 2705 if (solv->bestobeypolicy) 2706 r = solv->rules + solv->updaterules + (p - installed->start); 2707 else 2708 { 2709 r = solv->rules + solv->featurerules + (p - installed->start); 2710 if (!r->p) /* identical to update rule? */ 2711 r = solv->rules + solv->updaterules + (p - installed->start); 2712 } 2713 if (solv->multiversionupdaters && (d = solv->multiversionupdaters[p - installed->start]) != 0 && r == solv->rules + solv->updaterules + (p - installed->start)) 2714 { 2715 /* need to check multiversionupdaters */ 2716 if (r->p == p) /* be careful with the dup case */ 2717 queue_push(&q, p); 2718 while ((p2 = pool->whatprovidesdata[d++]) != 0) 2719 queue_push(&q, p2); 2720 } 2721 else 2722 { 2723 FOR_RULELITERALS(p2, pp2, r) 2724 if (p2 > 0) 2725 queue_push(&q, p2); 2726 } 2727 if (solv->update_targets && solv->update_targets->elements[p - installed->start]) 2728 prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q); 2729 if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)) 2730 prune_to_dup_packages(solv, p, &q); 2731 /* select best packages, just look at prio and version */ 2732 policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND); 2733 if (!q.count) 2734 continue; /* orphaned */ 2735 if (solv->bestobeypolicy) 2736 { 2737 /* also filter the best of the feature rule packages and add them */ 2738 r = solv->rules + solv->featurerules + (p - installed->start); 2739 if (r->p) 2740 { 2741 int j; 2742 queue_empty(&q2); 2743 FOR_RULELITERALS(p2, pp2, r) 2744 if (p2 > 0) 2745 queue_push(&q2, p2); 2746 if (solv->update_targets && solv->update_targets->elements[p - installed->start]) 2747 prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q2); 2748 if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)) 2749 prune_to_dup_packages(solv, p, &q); 2750 policy_filter_unwanted(solv, &q2, POLICY_MODE_RECOMMEND); 2751 for (j = 0; j < q2.count; j++) 2752 queue_pushunique(&q, q2.elements[j]); 2753 } 2754 } 2755 p2 = queue_shift(&q); 2756 solver_addrule(solv, p2, q.count ? pool_queuetowhatprovides(pool, &q) : 0); 2757 queue_push(&r2pkg, p); 2758 } 2759 } 2760 if (r2pkg.count) 2761 { 2762 solv->bestrules_pkg = solv_calloc(r2pkg.count, sizeof(Id)); 2763 memcpy(solv->bestrules_pkg, r2pkg.elements, r2pkg.count * sizeof(Id)); 2764 } 2765 solv->bestrules_end = solv->nrules; 2766 queue_free(&q); 2767 queue_free(&q2); 2768 queue_free(&r2pkg); 2769 } 2770 2771 #undef CLEANDEPSDEBUG 2772 2773 /* 2774 * This functions collects all packages that are looked at 2775 * when a dependency is checked. We need it to "pin" installed 2776 * packages when removing a supplemented package in createcleandepsmap. 2777 * Here's an not uncommon example: 2778 * A contains "Supplements: packageand(B, C)" 2779 * B contains "Requires: A" 2780 * Now if we remove C, the supplements is no longer true, 2781 * thus we also remove A. Without the dep_pkgcheck function, we 2782 * would now also remove B, but this is wrong, as adding back 2783 * C doesn't make the supplements true again. Thus we "pin" B 2784 * when we remove A. 2785 * There's probably a better way to do this, but I haven't come 2786 * up with it yet ;) 2787 */ 2788 static inline void 2789 dep_pkgcheck(Solver *solv, Id dep, Map *m, Queue *q) 2790 { 2791 Pool *pool = solv->pool; 2792 Id p, pp; 2793 2794 if (ISRELDEP(dep)) 2795 { 2796 Reldep *rd = GETRELDEP(pool, dep); 2797 if (rd->flags >= 8) 2798 { 2799 if (rd->flags == REL_AND) 2800 { 2801 dep_pkgcheck(solv, rd->name, m, q); 2802 dep_pkgcheck(solv, rd->evr, m, q); 2803 return; 2804 } 2805 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES) 2806 return; 2807 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED) 2808 return; 2809 } 2810 } 2811 FOR_PROVIDES(p, pp, dep) 2812 if (!m || MAPTST(m, p)) 2813 queue_push(q, p); 2814 } 2815 2816 static int 2817 check_xsupp(Solver *solv, Queue *depq, Id dep) 2818 { 2819 Pool *pool = solv->pool; 2820 Id p, pp; 2821 2822 if (ISRELDEP(dep)) 2823 { 2824 Reldep *rd = GETRELDEP(pool, dep); 2825 if (rd->flags >= 8) 2826 { 2827 if (rd->flags == REL_AND) 2828 { 2829 if (!check_xsupp(solv, depq, rd->name)) 2830 return 0; 2831 return check_xsupp(solv, depq, rd->evr); 2832 } 2833 if (rd->flags == REL_OR) 2834 { 2835 if (check_xsupp(solv, depq, rd->name)) 2836 return 1; 2837 return check_xsupp(solv, depq, rd->evr); 2838 } 2839 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES) 2840 return solver_splitprovides(solv, rd->evr); 2841 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED) 2842 return solver_dep_installed(solv, rd->evr); 2843 } 2844 if (depq && rd->flags == REL_NAMESPACE) 2845 { 2846 int i; 2847 for (i = 0; i < depq->count; i++) 2848 if (depq->elements[i] == dep || depq->elements[i] == rd->name) 2849 return 1; 2850 } 2851 } 2852 FOR_PROVIDES(p, pp, dep) 2853 if (p == SYSTEMSOLVABLE || pool->solvables[p].repo == solv->installed) 2854 return 1; 2855 return 0; 2856 } 2857 2858 static inline int 2859 queue_contains(Queue *q, Id id) 2860 { 2861 int i; 2862 for (i = 0; i < q->count; i++) 2863 if (q->elements[i] == id) 2864 return 1; 2865 return 0; 2866 } 2867 2868 2869 /* 2870 * Find all installed packages that are no longer 2871 * needed regarding the current solver job. 2872 * 2873 * The algorithm is: 2874 * - remove pass: remove all packages that could have 2875 * been dragged in by the obsoleted packages. 2876 * i.e. if package A is obsolete and contains "Requires: B", 2877 * also remove B, as installing A will have pulled in B. 2878 * after this pass, we have a set of still installed packages 2879 * with broken dependencies. 2880 * - add back pass: 2881 * now add back all packages that the still installed packages 2882 * require. 2883 * 2884 * The cleandeps packages are the packages removed in the first 2885 * pass and not added back in the second pass. 2886 * 2887 * If we search for unneeded packages (unneeded is true), we 2888 * simply remove all packages except the userinstalled ones in 2889 * the first pass. 2890 */ 2891 static void 2892 solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded) 2893 { 2894 Pool *pool = solv->pool; 2895 Repo *installed = solv->installed; 2896 Queue *job = &solv->job; 2897 Map userinstalled; 2898 Map im; 2899 Map installedm; 2900 Rule *r; 2901 Id rid, how, what, select; 2902 Id p, pp, ip, jp; 2903 Id req, *reqp, sup, *supp; 2904 Solvable *s; 2905 Queue iq, iqcopy, xsuppq; 2906 int i; 2907 2908 map_empty(cleandepsmap); 2909 if (!installed || installed->end == installed->start) 2910 return; 2911 map_init(&userinstalled, installed->end - installed->start); 2912 map_init(&im, pool->nsolvables); 2913 map_init(&installedm, pool->nsolvables); 2914 queue_init(&iq); 2915 queue_init(&xsuppq); 2916 2917 for (i = 0; i < job->count; i += 2) 2918 { 2919 how = job->elements[i]; 2920 if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED) 2921 { 2922 what = job->elements[i + 1]; 2923 select = how & SOLVER_SELECTMASK; 2924 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid)) 2925 FOR_REPO_SOLVABLES(installed, p, s) 2926 MAPSET(&userinstalled, p - installed->start); 2927 FOR_JOB_SELECT(p, pp, select, what) 2928 if (pool->solvables[p].repo == installed) 2929 MAPSET(&userinstalled, p - installed->start); 2930 } 2931 if ((how & (SOLVER_JOBMASK | SOLVER_SELECTMASK)) == (SOLVER_ERASE | SOLVER_SOLVABLE_PROVIDES)) 2932 { 2933 what = job->elements[i + 1]; 2934 if (ISRELDEP(what)) 2935 { 2936 Reldep *rd = GETRELDEP(pool, what); 2937 if (rd->flags != REL_NAMESPACE) 2938 continue; 2939 if (rd->evr == 0) 2940 { 2941 queue_pushunique(&iq, rd->name); 2942 continue; 2943 } 2944 FOR_PROVIDES(p, pp, what) 2945 if (p) 2946 break; 2947 if (p) 2948 continue; 2949 queue_pushunique(&iq, what); 2950 } 2951 } 2952 } 2953 2954 /* have special namespace cleandeps erases */ 2955 if (iq.count) 2956 { 2957 for (ip = solv->installed->start; ip < solv->installed->end; ip++) 2958 { 2959 s = pool->solvables + ip; 2960 if (s->repo != installed) 2961 continue; 2962 if (!s->supplements) 2963 continue; 2964 supp = s->repo->idarraydata + s->supplements; 2965 while ((sup = *supp++) != 0) 2966 if (check_xsupp(solv, &iq, sup) && !check_xsupp(solv, 0, sup)) 2967 { 2968 #ifdef CLEANDEPSDEBUG 2969 printf("xsupp %s from %s\n", pool_dep2str(pool, sup), pool_solvid2str(pool, ip)); 2970 #endif 2971 queue_pushunique(&xsuppq, sup); 2972 } 2973 } 2974 queue_empty(&iq); 2975 } 2976 2977 /* also add visible patterns to userinstalled for openSUSE */ 2978 if (1) 2979 { 2980 Dataiterator di; 2981 dataiterator_init(&di, pool, 0, 0, SOLVABLE_ISVISIBLE, 0, 0); 2982 while (dataiterator_step(&di)) 2983 { 2984 Id *dp; 2985 if (di.solvid <= 0) 2986 continue; 2987 s = pool->solvables + di.solvid; 2988 if (!s->repo || !s->requires) 2989 continue; 2990 if (s->repo != installed && !pool_installable(pool, s)) 2991 continue; 2992 if (strncmp(pool_id2str(pool, s->name), "pattern:", 8) != 0) 2993 continue; 2994 dp = s->repo->idarraydata + s->requires; 2995 for (dp = s->repo->idarraydata + s->requires; *dp; dp++) 2996 FOR_PROVIDES(p, pp, *dp) 2997 if (pool->solvables[p].repo == installed) 2998 { 2999 if (strncmp(pool_id2str(pool, pool->solvables[p].name), "pattern", 7) != 0) 3000 continue; 3001 MAPSET(&userinstalled, p - installed->start); 3002 } 3003 } 3004 dataiterator_free(&di); 3005 } 3006 if (1) 3007 { 3008 /* all products and their buddies are userinstalled */ 3009 for (p = installed->start; p < installed->end; p++) 3010 { 3011 Solvable *s = pool->solvables + p; 3012 if (s->repo != installed) 3013 continue; 3014 if (!strncmp("product:", pool_id2str(pool, s->name), 8)) 3015 { 3016 MAPSET(&userinstalled, p - installed->start); 3017 if (pool->nscallback) 3018 { 3019 Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, p); 3020 if (buddy >= installed->start && buddy < installed->end && pool->solvables[buddy].repo == installed) 3021 MAPSET(&userinstalled, buddy - installed->start); 3022 } 3023 } 3024 } 3025 } 3026 3027 /* add all positive elements (e.g. locks) to "userinstalled" */ 3028 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++) 3029 { 3030 r = solv->rules + rid; 3031 if (r->d < 0) 3032 continue; 3033 i = solv->ruletojob.elements[rid - solv->jobrules]; 3034 if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS) 3035 continue; 3036 FOR_RULELITERALS(p, jp, r) 3037 if (p > 0 && pool->solvables[p].repo == installed) 3038 MAPSET(&userinstalled, p - installed->start); 3039 } 3040 3041 /* add all cleandeps candidates to iq */ 3042 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++) 3043 { 3044 r = solv->rules + rid; 3045 if (r->d < 0) /* disabled? */ 3046 continue; 3047 if (r->d == 0 && r->p < 0 && r->w2 == 0) /* negative assertion (erase job)? */ 3048 { 3049 p = -r->p; 3050 if (pool->solvables[p].repo != installed) 3051 continue; 3052 MAPCLR(&userinstalled, p - installed->start); 3053 if (unneeded) 3054 continue; 3055 i = solv->ruletojob.elements[rid - solv->jobrules]; 3056 how = job->elements[i]; 3057 if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS)) 3058 queue_push(&iq, p); 3059 } 3060 else if (r->p > 0) /* install job */ 3061 { 3062 if (unneeded) 3063 continue; 3064 i = solv->ruletojob.elements[rid - solv->jobrules]; 3065 if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS) 3066 { 3067 /* check if the literals all obsolete some installed package */ 3068 Map om; 3069 int iqstart; 3070 3071 /* just one installed literal */ 3072 if (r->d == 0 && r->w2 == 0 && pool->solvables[r->p].repo == installed) 3073 continue; 3074 /* multiversion is bad */ 3075 if (solv->multiversion.size && !solv->keepexplicitobsoletes) 3076 { 3077 FOR_RULELITERALS(p, jp, r) 3078 if (MAPTST(&solv->multiversion, p)) 3079 break; 3080 if (p) 3081 continue; 3082 } 3083 3084 om.size = 0; 3085 iqstart = iq.count; 3086 FOR_RULELITERALS(p, jp, r) 3087 { 3088 if (p < 0) 3089 { 3090 queue_truncate(&iq, iqstart); /* abort */ 3091 break; 3092 } 3093 if (pool->solvables[p].repo == installed) 3094 { 3095 if (iq.count == iqstart) 3096 queue_push(&iq, p); 3097 else 3098 { 3099 for (i = iqstart; i < iq.count; i++) 3100 if (iq.elements[i] == p) 3101 break; 3102 queue_truncate(&iq, iqstart); 3103 if (i < iq.count) 3104 queue_push(&iq, p); 3105 } 3106 } 3107 else 3108 intersect_obsoletes(solv, p, &iq, iqstart, &om); 3109 if (iq.count == iqstart) 3110 break; 3111 } 3112 if (om.size) 3113 map_free(&om); 3114 } 3115 } 3116 } 3117 queue_init_clone(&iqcopy, &iq); 3118 3119 if (!unneeded) 3120 { 3121 if (solv->cleandeps_updatepkgs) 3122 for (i = 0; i < solv->cleandeps_updatepkgs->count; i++) 3123 queue_push(&iq, solv->cleandeps_updatepkgs->elements[i]); 3124 } 3125 3126 if (unneeded) 3127 queue_empty(&iq); /* just in case... */ 3128 3129 /* clear userinstalled bit for the packages we really want to delete/update */ 3130 for (i = 0; i < iq.count; i++) 3131 { 3132 p = iq.elements[i]; 3133 if (pool->solvables[p].repo != installed) 3134 continue; 3135 MAPCLR(&userinstalled, p - installed->start); 3136 } 3137 3138 for (p = installed->start; p < installed->end; p++) 3139 { 3140 if (pool->solvables[p].repo != installed) 3141 continue; 3142 MAPSET(&installedm, p); 3143 if (unneeded && !MAPTST(&userinstalled, p - installed->start)) 3144 continue; 3145 MAPSET(&im, p); 3146 } 3147 MAPSET(&installedm, SYSTEMSOLVABLE); 3148 MAPSET(&im, SYSTEMSOLVABLE); 3149 3150 #ifdef CLEANDEPSDEBUG 3151 printf("REMOVE PASS\n"); 3152 #endif 3153 3154 for (;;) 3155 { 3156 if (!iq.count) 3157 { 3158 if (unneeded) 3159 break; 3160 /* supplements pass */ 3161 for (ip = installed->start; ip < installed->end; ip++) 3162 { 3163 if (!MAPTST(&installedm, ip)) 3164 continue; 3165 s = pool->solvables + ip; 3166 if (!s->supplements) 3167 continue; 3168 if (!MAPTST(&im, ip)) 3169 continue; 3170 if (MAPTST(&userinstalled, ip - installed->start)) 3171 continue; 3172 supp = s->repo->idarraydata + s->supplements; 3173 while ((sup = *supp++) != 0) 3174 if (dep_possible(solv, sup, &im)) 3175 break; 3176 if (!sup) 3177 { 3178 supp = s->repo->idarraydata + s->supplements; 3179 while ((sup = *supp++) != 0) 3180 if (dep_possible(solv, sup, &installedm) || (xsuppq.count && queue_contains(&xsuppq, sup))) 3181 { 3182 /* no longer supplemented, also erase */ 3183 int iqcount = iq.count; 3184 /* pin packages, see comment above dep_pkgcheck */ 3185 dep_pkgcheck(solv, sup, &im, &iq); 3186 for (i = iqcount; i < iq.count; i++) 3187 { 3188 Id pqp = iq.elements[i]; 3189 if (pool->solvables[pqp].repo == installed) 3190 MAPSET(&userinstalled, pqp - installed->start); 3191 } 3192 queue_truncate(&iq, iqcount); 3193 #ifdef CLEANDEPSDEBUG 3194 printf("%s supplemented [%s]\n", pool_solvid2str(pool, ip), pool_dep2str(pool, sup)); 3195 #endif 3196 queue_push(&iq, ip); 3197 } 3198 } 3199 } 3200 if (!iq.count) 3201 break; /* no supplementing package found, we're done */ 3202 } 3203 ip = queue_shift(&iq); 3204 s = pool->solvables + ip; 3205 if (!MAPTST(&im, ip)) 3206 continue; 3207 if (!MAPTST(&installedm, ip)) 3208 continue; 3209 if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start)) 3210 continue; 3211 MAPCLR(&im, ip); 3212 #ifdef CLEANDEPSDEBUG 3213 printf("removing %s\n", pool_solvable2str(pool, s)); 3214 #endif 3215 if (s->requires) 3216 { 3217 reqp = s->repo->idarraydata + s->requires; 3218 while ((req = *reqp++) != 0) 3219 { 3220 if (req == SOLVABLE_PREREQMARKER) 3221 continue; 3222 #if 0 3223 /* count number of installed packages that match */ 3224 count = 0; 3225 FOR_PROVIDES(p, pp, req) 3226 if (MAPTST(&installedm, p)) 3227 count++; 3228 if (count > 1) 3229 continue; 3230 #endif 3231 FOR_PROVIDES(p, pp, req) 3232 { 3233 if (p != SYSTEMSOLVABLE && MAPTST(&im, p)) 3234 { 3235 #ifdef CLEANDEPSDEBUG 3236 printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p)); 3237 #endif 3238 queue_push(&iq, p); 3239 } 3240 } 3241 } 3242 } 3243 if (s->recommends) 3244 { 3245 reqp = s->repo->idarraydata + s->recommends; 3246 while ((req = *reqp++) != 0) 3247 { 3248 #if 0 3249 count = 0; 3250 FOR_PROVIDES(p, pp, req) 3251 if (MAPTST(&installedm, p)) 3252 count++; 3253 if (count > 1) 3254 continue; 3255 #endif 3256 FOR_PROVIDES(p, pp, req) 3257 { 3258 if (p != SYSTEMSOLVABLE && MAPTST(&im, p)) 3259 { 3260 #ifdef CLEANDEPSDEBUG 3261 printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p)); 3262 #endif 3263 queue_push(&iq, p); 3264 } 3265 } 3266 } 3267 } 3268 } 3269 3270 /* turn userinstalled into remove set for pruning */ 3271 map_empty(&userinstalled); 3272 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++) 3273 { 3274 r = solv->rules + rid; 3275 if (r->p >= 0 || r->d != 0 || r->w2 != 0) 3276 continue; /* disabled or not erase */ 3277 p = -r->p; 3278 MAPCLR(&im, p); 3279 if (pool->solvables[p].repo == installed) 3280 MAPSET(&userinstalled, p - installed->start); 3281 } 3282 MAPSET(&im, SYSTEMSOLVABLE); /* in case we cleared it above */ 3283 for (p = installed->start; p < installed->end; p++) 3284 if (MAPTST(&im, p)) 3285 queue_push(&iq, p); 3286 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++) 3287 { 3288 r = solv->rules + rid; 3289 if (r->d < 0) 3290 continue; 3291 FOR_RULELITERALS(p, jp, r) 3292 if (p > 0) 3293 queue_push(&iq, p); 3294 } 3295 /* also put directly addressed packages on the install queue 3296 * so we can mark patterns as installed */ 3297 for (i = 0; i < job->count; i += 2) 3298 { 3299 how = job->elements[i]; 3300 if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED) 3301 { 3302 what = job->elements[i + 1]; 3303 select = how & SOLVER_SELECTMASK; 3304 if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed) 3305 queue_push(&iq, what); 3306 } 3307 } 3308 3309 #ifdef CLEANDEPSDEBUG 3310 printf("ADDBACK PASS\n"); 3311 #endif 3312 for (;;) 3313 { 3314 if (!iq.count) 3315 { 3316 /* supplements pass */ 3317 for (ip = installed->start; ip < installed->end; ip++) 3318 { 3319 if (!MAPTST(&installedm, ip)) 3320 continue; 3321 if (MAPTST(&userinstalled, ip - installed->start)) 3322 continue; 3323 s = pool->solvables + ip; 3324 if (!s->supplements) 3325 continue; 3326 if (MAPTST(&im, ip)) 3327 continue; 3328 supp = s->repo->idarraydata + s->supplements; 3329 while ((sup = *supp++) != 0) 3330 if (dep_possible(solv, sup, &im)) 3331 break; 3332 if (sup) 3333 { 3334 #ifdef CLEANDEPSDEBUG 3335 printf("%s supplemented\n", pool_solvid2str(pool, ip)); 3336 #endif 3337 MAPSET(&im, ip); 3338 queue_push(&iq, ip); 3339 } 3340 } 3341 if (!iq.count) 3342 break; 3343 } 3344 ip = queue_shift(&iq); 3345 s = pool->solvables + ip; 3346 #ifdef CLEANDEPSDEBUG 3347 printf("adding back %s\n", pool_solvable2str(pool, s)); 3348 #endif 3349 if (s->requires) 3350 { 3351 reqp = s->repo->idarraydata + s->requires; 3352 while ((req = *reqp++) != 0) 3353 { 3354 FOR_PROVIDES(p, pp, req) 3355 if (MAPTST(&im, p)) 3356 break; 3357 if (p) 3358 continue; 3359 FOR_PROVIDES(p, pp, req) 3360 { 3361 if (!MAPTST(&im, p) && MAPTST(&installedm, p)) 3362 { 3363 if (p == ip) 3364 continue; 3365 if (MAPTST(&userinstalled, p - installed->start)) 3366 continue; 3367 #ifdef CLEANDEPSDEBUG 3368 printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p)); 3369 #endif 3370 MAPSET(&im, p); 3371 queue_push(&iq, p); 3372 } 3373 } 3374 } 3375 } 3376 if (s->recommends) 3377 { 3378 reqp = s->repo->idarraydata + s->recommends; 3379 while ((req = *reqp++) != 0) 3380 { 3381 FOR_PROVIDES(p, pp, req) 3382 if (MAPTST(&im, p)) 3383 break; 3384 if (p) 3385 continue; 3386 FOR_PROVIDES(p, pp, req) 3387 { 3388 if (!MAPTST(&im, p) && MAPTST(&installedm, p)) 3389 { 3390 if (p == ip) 3391 continue; 3392 if (MAPTST(&userinstalled, p - installed->start)) 3393 continue; 3394 #ifdef CLEANDEPSDEBUG 3395 printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p)); 3396 #endif 3397 MAPSET(&im, p); 3398 queue_push(&iq, p); 3399 } 3400 } 3401 } 3402 } 3403 } 3404 3405 queue_free(&iq); 3406 /* make sure the updatepkgs and mistakes are not in the cleandeps map */ 3407 if (solv->cleandeps_updatepkgs) 3408 for (i = 0; i < solv->cleandeps_updatepkgs->count; i++) 3409 MAPSET(&im, solv->cleandeps_updatepkgs->elements[i]); 3410 if (solv->cleandeps_mistakes) 3411 for (i = 0; i < solv->cleandeps_mistakes->count; i++) 3412 MAPSET(&im, solv->cleandeps_mistakes->elements[i]); 3413 /* also remove original iq packages */ 3414 for (i = 0; i < iqcopy.count; i++) 3415 MAPSET(&im, iqcopy.elements[i]); 3416 queue_free(&iqcopy); 3417 for (p = installed->start; p < installed->end; p++) 3418 { 3419 if (pool->solvables[p].repo != installed) 3420 continue; 3421 if (!MAPTST(&im, p)) 3422 MAPSET(cleandepsmap, p - installed->start); 3423 } 3424 map_free(&im); 3425 map_free(&installedm); 3426 map_free(&userinstalled); 3427 queue_free(&xsuppq); 3428 #ifdef CLEANDEPSDEBUG 3429 printf("=== final cleandeps map:\n"); 3430 for (p = installed->start; p < installed->end; p++) 3431 if (MAPTST(cleandepsmap, p - installed->start)) 3432 printf(" - %s\n", pool_solvid2str(pool, p)); 3433 #endif 3434 } 3435 3436 3437 struct trj_data { 3438 Queue *edges; 3439 Id *low; 3440 Id idx; 3441 Id nstack; 3442 Id firstidx; 3443 }; 3444 3445 /* Tarjan's SCC algorithm, slightly modifed */ 3446 static void 3447 trj_visit(struct trj_data *trj, Id node) 3448 { 3449 Id *low = trj->low; 3450 Queue *edges = trj->edges; 3451 Id nnode, myidx, stackstart; 3452 int i; 3453 3454 low[node] = myidx = trj->idx++; 3455 low[(stackstart = trj->nstack++)] = node; 3456 for (i = edges->elements[node]; (nnode = edges->elements[i]) != 0; i++) 3457 { 3458 Id l = low[nnode]; 3459 if (!l) 3460 { 3461 if (!edges->elements[edges->elements[nnode]]) 3462 { 3463 trj->idx++; 3464 low[nnode] = -1; 3465 continue; 3466 } 3467 trj_visit(trj, nnode); 3468 l = low[nnode]; 3469 } 3470 if (l < 0) 3471 continue; 3472 if (l < trj->firstidx) 3473 { 3474 int k; 3475 for (k = l; low[low[k]] == l; k++) 3476 low[low[k]] = -1; 3477 } 3478 else if (l < low[node]) 3479 low[node] = l; 3480 } 3481 if (low[node] == myidx) 3482 { 3483 if (myidx != trj->firstidx) 3484 myidx = -1; 3485 for (i = stackstart; i < trj->nstack; i++) 3486 low[low[i]] = myidx; 3487 trj->nstack = stackstart; 3488 } 3489 } 3490 3491 3492 void 3493 solver_get_unneeded(Solver *solv, Queue *unneededq, int filtered) 3494 { 3495 Repo *installed = solv->installed; 3496 int i; 3497 Map cleandepsmap; 3498 3499 queue_empty(unneededq); 3500 if (!installed || installed->end == installed->start) 3501 return; 3502 3503 map_init(&cleandepsmap, installed->end - installed->start); 3504 solver_createcleandepsmap(solv, &cleandepsmap, 1); 3505 for (i = installed->start; i < installed->end; i++) 3506 if (MAPTST(&cleandepsmap, i - installed->start)) 3507 queue_push(unneededq, i); 3508 3509 if (filtered && unneededq->count > 1) 3510 { 3511 Pool *pool = solv->pool; 3512 Queue edges; 3513 Id *nrequires; 3514 Map installedm; 3515 int j, pass, count = unneededq->count; 3516 Id *low; 3517 3518 map_init(&installedm, pool->nsolvables); 3519 for (i = installed->start; i < installed->end; i++) 3520 if (pool->solvables[i].repo == installed) 3521 MAPSET(&installedm, i); 3522 3523 nrequires = solv_calloc(count, sizeof(Id)); 3524 queue_init(&edges); 3525 queue_prealloc(&edges, count * 4 + 10); /* pre-size */ 3526 3527 /* 3528 * Go through the solvables in the nodes queue and create edges for 3529 * all requires/recommends/supplements between the nodes. 3530 * The edges are stored in the edges queue, we add 1 to the node 3531 * index so that nodes in the edges queue are != 0 and we can 3532 * terminate the edge list with 0. 3533 * Thus for node element 5, the edges are stored starting at 3534 * edges.elements[6] and are 0-terminated. 3535 */ 3536 /* leave first element zero to make things easier */ 3537 /* also add trailing zero */ 3538 queue_insertn(&edges, 0, 1 + count + 1, 0); 3539 3540 /* first requires and recommends */ 3541 for (i = 0; i < count; i++) 3542 { 3543 Solvable *s = pool->solvables + unneededq->elements[i]; 3544 edges.elements[i + 1] = edges.count; 3545 for (pass = 0; pass < 2; pass++) 3546 { 3547 int num = 0; 3548 unsigned int off = pass == 0 ? s->requires : s->recommends; 3549 Id p, pp, *dp; 3550 if (off) 3551 for (dp = s->repo->idarraydata + off; *dp; dp++) 3552 FOR_PROVIDES(p, pp, *dp) 3553 { 3554 Solvable *sp = pool->solvables + p; 3555 if (s == sp || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start)) 3556 continue; 3557 for (j = 0; j < count; j++) 3558 if (p == unneededq->elements[j]) 3559 break; 3560 if (j == count) 3561 continue; 3562 if (num && edges.elements[edges.count - 1] == j + 1) 3563 continue; 3564 queue_push(&edges, j + 1); 3565 num++; 3566 } 3567 if (pass == 0) 3568 nrequires[i] = num; 3569 } 3570 queue_push(&edges, 0); 3571 } 3572 #if 0 3573 printf("requires + recommends\n"); 3574 for (i = 0; i < count; i++) 3575 { 3576 int j; 3577 printf(" %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]); 3578 for (j = edges.elements[i + 1]; edges.elements[j]; j++) 3579 printf(" - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1])); 3580 } 3581 #endif 3582 3583 /* then add supplements */ 3584 for (i = 0; i < count; i++) 3585 { 3586 Solvable *s = pool->solvables + unneededq->elements[i]; 3587 if (s->supplements) 3588 { 3589 Id *dp; 3590 int k; 3591 for (dp = s->repo->idarraydata + s->supplements; *dp; dp++) 3592 if (dep_possible(solv, *dp, &installedm)) 3593 { 3594 Queue iq; 3595 Id iqbuf[16]; 3596 queue_init_buffer(&iq, iqbuf, sizeof(iqbuf)/sizeof(*iqbuf)); 3597 dep_pkgcheck(solv, *dp, 0, &iq); 3598 for (k = 0; k < iq.count; k++) 3599 { 3600 Id p = iq.elements[k]; 3601 Solvable *sp = pool->solvables + p; 3602 if (p == unneededq->elements[i] || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start)) 3603 continue; 3604 for (j = 0; j < count; j++) 3605 if (p == unneededq->elements[j]) 3606 break; 3607 /* now add edge from j + 1 to i + 1 */ 3608 queue_insert(&edges, edges.elements[j + 1] + nrequires[j], i + 1); 3609 /* addapt following edge pointers */ 3610 for (k = j + 2; k < count + 2; k++) 3611 edges.elements[k]++; 3612 } 3613 queue_free(&iq); 3614 } 3615 } 3616 } 3617 #if 0 3618 /* print result */ 3619 printf("+ supplements\n"); 3620 for (i = 0; i < count; i++) 3621 { 3622 int j; 3623 printf(" %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]); 3624 for (j = edges.elements[i + 1]; edges.elements[j]; j++) 3625 printf(" - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1])); 3626 } 3627 #endif 3628 map_free(&installedm); 3629 3630 /* now run SCC algo two times, first with requires+recommends+supplements, 3631 * then again without the requires. We run it the second time to get rid 3632 * of packages that got dragged in via recommends/supplements */ 3633 /* 3634 * low will contain the result of the SCC search. 3635 * it must be of at least size 2 * (count + 1) and 3636 * must be zero initialized. 3637 * The layout is: 3638 * 0 low low ... low stack stack ...stack 0 3639 * count count 3640 */ 3641 low = solv_calloc(count + 1, 2 * sizeof(Id)); 3642 for (pass = 0; pass < 2; pass++) 3643 { 3644 struct trj_data trj; 3645 if (pass) 3646 { 3647 memset(low, 0, (count + 1) * (2 * sizeof(Id))); 3648 for (i = 0; i < count; i++) 3649 { 3650 edges.elements[i + 1] += nrequires[i]; 3651 if (!unneededq->elements[i]) 3652 low[i + 1] = -1; /* ignore this node */ 3653 } 3654 } 3655 trj.edges = &edges; 3656 trj.low = low; 3657 trj.idx = count + 1; /* stack starts here */ 3658 for (i = 1; i <= count; i++) 3659 { 3660 if (low[i]) 3661 continue; 3662 if (edges.elements[edges.elements[i]]) 3663 { 3664 trj.firstidx = trj.nstack = trj.idx; 3665 trj_visit(&trj, i); 3666 } 3667 else 3668 { 3669 Id myidx = trj.idx++; 3670 low[i] = myidx; 3671 low[myidx] = i; 3672 } 3673 } 3674 /* prune packages */ 3675 for (i = 0; i < count; i++) 3676 if (low[i + 1] <= 0) 3677 unneededq->elements[i] = 0; 3678 } 3679 solv_free(low); 3680 solv_free(nrequires); 3681 queue_free(&edges); 3682 3683 /* finally remove all pruned entries from unneededq */ 3684 for (i = j = 0; i < count; i++) 3685 if (unneededq->elements[i]) 3686 unneededq->elements[j++] = unneededq->elements[i]; 3687 queue_truncate(unneededq, j); 3688 } 3689 map_free(&cleandepsmap); 3690 } 3691 3692 /* EOF */ 3693