satsolver 0.16.3
|
00001 /* 00002 * Copyright (c) 2007-2009, Novell Inc. 00003 * 00004 * This program is licensed under the BSD license, read LICENSE.BSD 00005 * for further information 00006 */ 00007 00008 /* 00009 * rules.c 00010 * 00011 * SAT based dependency solver 00012 */ 00013 00014 #include <stdio.h> 00015 #include <stdlib.h> 00016 #include <unistd.h> 00017 #include <string.h> 00018 #include <assert.h> 00019 00020 #include "solver.h" 00021 #include "bitmap.h" 00022 #include "pool.h" 00023 #include "poolarch.h" 00024 #include "util.h" 00025 #include "evr.h" 00026 #include "policy.h" 00027 #include "solverdebug.h" 00028 00029 #define RULES_BLOCK 63 00030 00031 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep); 00032 static void solver_createcleandepsmap(Solver *solv); 00033 00034 /*------------------------------------------------------------------- 00035 * Check if dependency is possible 00036 * 00037 * mirrors solver_dep_fulfilled but uses map m instead of the decisionmap 00038 */ 00039 00040 static inline int 00041 dep_possible(Solver *solv, Id dep, Map *m) 00042 { 00043 Pool *pool = solv->pool; 00044 Id p, pp; 00045 00046 if (ISRELDEP(dep)) 00047 { 00048 Reldep *rd = GETRELDEP(pool, dep); 00049 if (rd->flags == REL_AND) 00050 { 00051 if (!dep_possible(solv, rd->name, m)) 00052 return 0; 00053 return dep_possible(solv, rd->evr, m); 00054 } 00055 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES) 00056 return solver_splitprovides(solv, rd->evr); 00057 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED) 00058 return solver_dep_installed(solv, rd->evr); 00059 } 00060 FOR_PROVIDES(p, pp, dep) 00061 { 00062 if (MAPTST(m, p)) 00063 return 1; 00064 } 00065 return 0; 00066 } 00067 00068 /******************************************************************** 00069 * 00070 * Rule handling 00071 * 00072 * - unify rules, remove duplicates 00073 */ 00074 00075 /*------------------------------------------------------------------- 00076 * 00077 * compare rules for unification sort 00078 * 00079 */ 00080 00081 static int 00082 unifyrules_sortcmp(const void *ap, const void *bp, void *dp) 00083 { 00084 Pool *pool = dp; 00085 Rule *a = (Rule *)ap; 00086 Rule *b = (Rule *)bp; 00087 Id *ad, *bd; 00088 int x; 00089 00090 x = a->p - b->p; 00091 if (x) 00092 return x; /* p differs */ 00093 00094 /* identical p */ 00095 if (a->d == 0 && b->d == 0) 00096 return a->w2 - b->w2; /* assertion: return w2 diff */ 00097 00098 if (a->d == 0) /* a is assertion, b not */ 00099 { 00100 x = a->w2 - pool->whatprovidesdata[b->d]; 00101 return x ? x : -1; 00102 } 00103 00104 if (b->d == 0) /* b is assertion, a not */ 00105 { 00106 x = pool->whatprovidesdata[a->d] - b->w2; 00107 return x ? x : 1; 00108 } 00109 00110 /* compare whatprovidesdata */ 00111 ad = pool->whatprovidesdata + a->d; 00112 bd = pool->whatprovidesdata + b->d; 00113 while (*bd) 00114 if ((x = *ad++ - *bd++) != 0) 00115 return x; 00116 return *ad; 00117 } 00118 00119 int 00120 solver_samerule(Solver *solv, Rule *r1, Rule *r2) 00121 { 00122 return unifyrules_sortcmp(r1, r2, solv->pool); 00123 } 00124 00125 00126 /*------------------------------------------------------------------- 00127 * 00128 * unify rules 00129 * go over all rules and remove duplicates 00130 */ 00131 00132 void 00133 solver_unifyrules(Solver *solv) 00134 { 00135 Pool *pool = solv->pool; 00136 int i, j; 00137 Rule *ir, *jr; 00138 00139 if (solv->nrules <= 1) /* nothing to unify */ 00140 return; 00141 00142 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n"); 00143 00144 /* sort rules first */ 00145 sat_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool); 00146 00147 /* prune rules 00148 * i = unpruned 00149 * j = pruned 00150 */ 00151 jr = 0; 00152 for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++) 00153 { 00154 if (jr && !unifyrules_sortcmp(ir, jr, pool)) 00155 continue; /* prune! */ 00156 jr = solv->rules + j++; /* keep! */ 00157 if (ir != jr) 00158 *jr = *ir; 00159 } 00160 00161 /* reduced count from nrules to j rules */ 00162 POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j); 00163 00164 /* adapt rule buffer */ 00165 solv->nrules = j; 00166 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK); 00167 00168 /* 00169 * debug: log rule statistics 00170 */ 00171 IF_POOLDEBUG (SAT_DEBUG_STATS) 00172 { 00173 int binr = 0; 00174 int lits = 0; 00175 Id *dp; 00176 Rule *r; 00177 00178 for (i = 1; i < solv->nrules; i++) 00179 { 00180 r = solv->rules + i; 00181 if (r->d == 0) 00182 binr++; 00183 else 00184 { 00185 dp = solv->pool->whatprovidesdata + r->d; 00186 while (*dp++) 00187 lits++; 00188 } 00189 } 00190 POOL_DEBUG(SAT_DEBUG_STATS, " binary: %d\n", binr); 00191 POOL_DEBUG(SAT_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits); 00192 } 00193 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n"); 00194 } 00195 00196 #if 0 00197 00198 /* 00199 * hash rule 00200 */ 00201 00202 static Hashval 00203 hashrule(Solver *solv, Id p, Id d, int n) 00204 { 00205 unsigned int x = (unsigned int)p; 00206 int *dp; 00207 00208 if (n <= 1) 00209 return (x * 37) ^ (unsigned int)d; 00210 dp = solv->pool->whatprovidesdata + d; 00211 while (*dp) 00212 x = (x * 37) ^ (unsigned int)*dp++; 00213 return x; 00214 } 00215 #endif 00216 00217 00218 /*------------------------------------------------------------------- 00219 * 00220 */ 00221 00222 /* 00223 * add rule 00224 * p = direct literal; always < 0 for installed rpm rules 00225 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only) 00226 * 00227 * 00228 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3) 00229 * 00230 * p < 0 : pkg id of A 00231 * d > 0 : Offset in whatprovidesdata (list of providers of b) 00232 * 00233 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3) 00234 * p < 0 : pkg id of A 00235 * d < 0 : Id of solvable (e.g. B1) 00236 * 00237 * d == 0: unary rule, assertion => (A) or (-A) 00238 * 00239 * Install: p > 0, d = 0 (A) user requested install 00240 * Remove: p < 0, d = 0 (-A) user requested remove (also: uninstallable) 00241 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p> 00242 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p> 00243 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule) 00244 * also used for obsoletes 00245 * ?: p > 0, d < 0 (A|-B) 00246 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder) 00247 * 00248 * resulting watches: 00249 * ------------------ 00250 * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0 00251 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p 00252 * every other : w1 = p, w2 = whatprovidesdata[d]; 00253 * Disabled rule: w1 = 0 00254 * 00255 * always returns a rule for non-rpm rules 00256 */ 00257 00258 Rule * 00259 solver_addrule(Solver *solv, Id p, Id d) 00260 { 00261 Pool *pool = solv->pool; 00262 Rule *r = 0; 00263 Id *dp = 0; 00264 00265 int n = 0; /* number of literals in rule - 1 00266 0 = direct assertion (single literal) 00267 1 = binary rule 00268 >1 = 00269 */ 00270 00271 /* it often happenes that requires lead to adding the same rpm rule 00272 * multiple times, so we prune those duplicates right away to make 00273 * the work for unifyrules a bit easier */ 00274 00275 if (solv->nrules /* we already have rules */ 00276 && !solv->rpmrules_end) /* but are not done with rpm rules */ 00277 { 00278 r = solv->rules + solv->nrules - 1; /* get the last added rule */ 00279 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */ 00280 return r; 00281 } 00282 00283 /* 00284 * compute number of literals (n) in rule 00285 */ 00286 00287 if (d < 0) 00288 { 00289 /* always a binary rule */ 00290 if (p == d) 00291 return 0; /* ignore self conflict */ 00292 n = 1; 00293 } 00294 else if (d > 0) 00295 { 00296 for (dp = pool->whatprovidesdata + d; *dp; dp++, n++) 00297 if (*dp == -p) 00298 return 0; /* rule is self-fulfilling */ 00299 00300 if (n == 1) /* have single provider */ 00301 d = dp[-1]; /* take single literal */ 00302 } 00303 00304 if (n == 1 && p > d && !solv->rpmrules_end) 00305 { 00306 /* smallest literal first so we can find dups */ 00307 n = p; p = d; d = n; /* p <-> d */ 00308 n = 1; /* re-set n, was used as temp var */ 00309 } 00310 00311 /* 00312 * check for duplicate 00313 */ 00314 00315 /* check if the last added rule (r) is exactly the same as what we're looking for. */ 00316 if (r && n == 1 && !r->d && r->p == p && r->w2 == d) 00317 return r; /* binary rule */ 00318 00319 /* have n-ary rule with same first literal, check other literals */ 00320 if (r && n > 1 && r->d && r->p == p) 00321 { 00322 /* Rule where d is an offset in whatprovidesdata */ 00323 Id *dp2; 00324 if (d == r->d) 00325 return r; 00326 dp2 = pool->whatprovidesdata + r->d; 00327 for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++) 00328 if (*dp != *dp2) 00329 break; 00330 if (*dp == *dp2) 00331 return r; 00332 } 00333 00334 /* 00335 * allocate new rule 00336 */ 00337 00338 /* extend rule buffer */ 00339 solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK); 00340 r = solv->rules + solv->nrules++; /* point to rule space */ 00341 00342 /* 00343 * r = new rule 00344 */ 00345 00346 r->p = p; 00347 if (n == 0) 00348 { 00349 /* direct assertion, no watch needed */ 00350 r->d = 0; 00351 r->w1 = p; 00352 r->w2 = 0; 00353 } 00354 else if (n == 1) 00355 { 00356 /* binary rule */ 00357 r->d = 0; 00358 r->w1 = p; 00359 r->w2 = d; 00360 } 00361 else 00362 { 00363 r->d = d; 00364 r->w1 = p; 00365 r->w2 = pool->whatprovidesdata[d]; 00366 } 00367 r->n1 = 0; 00368 r->n2 = 0; 00369 00370 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION) 00371 { 00372 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: "); 00373 solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r); 00374 } 00375 00376 return r; 00377 } 00378 00379 00380 /****************************************************************************** 00381 *** 00382 *** rpm rule part: create rules representing the package dependencies 00383 *** 00384 ***/ 00385 00386 /* 00387 * special multiversion patch conflict handling: 00388 * a patch conflict is also satisfied if some other 00389 * version with the same name/arch that doesn't conflict 00390 * gets installed. The generated rule is thus: 00391 * -patch|-cpack|opack1|opack2|... 00392 */ 00393 static Id 00394 makemultiversionconflict(Solver *solv, Id n, Id con) 00395 { 00396 Pool *pool = solv->pool; 00397 Solvable *s, *sn; 00398 Queue q; 00399 Id p, pp, qbuf[64]; 00400 00401 sn = pool->solvables + n; 00402 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf)); 00403 queue_push(&q, -n); 00404 FOR_PROVIDES(p, pp, sn->name) 00405 { 00406 s = pool->solvables + p; 00407 if (s->name != sn->name || s->arch != sn->arch) 00408 continue; 00409 if (!MAPTST(&solv->noobsoletes, p)) 00410 continue; 00411 if (pool_match_nevr(pool, pool->solvables + p, con)) 00412 continue; 00413 /* here we have a multiversion solvable that doesn't conflict */ 00414 /* thus we're not in conflict if it is installed */ 00415 queue_push(&q, p); 00416 } 00417 if (q.count == 1) 00418 return -n; /* no other package found, generate normal conflict */ 00419 return pool_queuetowhatprovides(pool, &q); 00420 } 00421 00422 static inline void 00423 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep) 00424 { 00425 if (!solv->ruleinfoq) 00426 solver_addrule(solv, p, d); 00427 else 00428 addrpmruleinfo(solv, p, d, type, dep); 00429 } 00430 00431 /*------------------------------------------------------------------- 00432 * 00433 * add (install) rules for solvable 00434 * 00435 * s: Solvable for which to add rules 00436 * m: m[s] = 1 for solvables which have rules, prevent rule duplication 00437 * 00438 * Algorithm: 'visit all nodes of a graph'. The graph nodes are 00439 * solvables, the edges their dependencies. 00440 * Starting from an installed solvable, this will create all rules 00441 * representing the graph created by the solvables dependencies. 00442 * 00443 * for unfulfilled requirements, conflicts, obsoletes,.... 00444 * add a negative assertion for solvables that are not installable 00445 * 00446 * It will also create rules for all solvables referenced by 's' 00447 * i.e. descend to all providers of requirements of 's' 00448 * 00449 */ 00450 00451 void 00452 solver_addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m) 00453 { 00454 Pool *pool = solv->pool; 00455 Repo *installed = solv->installed; 00456 00457 /* 'work' queue. keeps Ids of solvables we still have to work on. 00458 And buffer for it. */ 00459 Queue workq; 00460 Id workqbuf[64]; 00461 00462 int i; 00463 /* if to add rules for broken deps ('rpm -V' functionality) 00464 * 0 = yes, 1 = no 00465 */ 00466 int dontfix; 00467 /* Id var and pointer for each dependency 00468 * (not used in parallel) 00469 */ 00470 Id req, *reqp; 00471 Id con, *conp; 00472 Id obs, *obsp; 00473 Id rec, *recp; 00474 Id sug, *sugp; 00475 Id p, pp; /* whatprovides loops */ 00476 Id *dp; /* ptr to 'whatprovides' */ 00477 Id n; /* Id for current solvable 's' */ 00478 00479 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n"); 00480 00481 queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf)); 00482 queue_push(&workq, s - pool->solvables); /* push solvable Id to work queue */ 00483 00484 /* loop until there's no more work left */ 00485 while (workq.count) 00486 { 00487 /* 00488 * n: Id of solvable 00489 * s: Pointer to solvable 00490 */ 00491 00492 n = queue_shift(&workq); /* 'pop' next solvable to work on from queue */ 00493 if (m) 00494 { 00495 if (MAPTST(m, n)) /* continue if already visited */ 00496 continue; 00497 MAPSET(m, n); /* mark as visited */ 00498 } 00499 00500 s = pool->solvables + n; /* s = Solvable in question */ 00501 00502 dontfix = 0; 00503 if (installed /* Installed system available */ 00504 && s->repo == installed /* solvable is installed */ 00505 && !solv->fixmap_all /* NOT repair errors in rpm dependency graph */ 00506 && !(solv->fixmap.size && MAPTST(&solv->fixmap, n - installed->start))) 00507 { 00508 dontfix = 1; /* dont care about broken rpm deps */ 00509 } 00510 00511 if (!dontfix 00512 && s->arch != ARCH_SRC 00513 && s->arch != ARCH_NOSRC 00514 && !pool_installable(pool, s)) 00515 { 00516 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables)); 00517 addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0); 00518 } 00519 00520 /* yet another SUSE hack, sigh */ 00521 if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8)) 00522 { 00523 Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n); 00524 if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables) 00525 { 00526 addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n)); 00527 addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy)); 00528 if (m && !MAPTST(m, buddy)) 00529 queue_push(&workq, buddy); 00530 } 00531 } 00532 00533 /*----------------------------------------- 00534 * check requires of s 00535 */ 00536 00537 if (s->requires) 00538 { 00539 reqp = s->repo->idarraydata + s->requires; 00540 while ((req = *reqp++) != 0) /* go through all requires */ 00541 { 00542 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */ 00543 continue; 00544 00545 /* find list of solvables providing 'req' */ 00546 dp = pool_whatprovides_ptr(pool, req); 00547 00548 if (*dp == SYSTEMSOLVABLE) /* always installed */ 00549 continue; 00550 00551 if (dontfix) 00552 { 00553 /* the strategy here is to not insist on dependencies 00554 * that are already broken. so if we find one provider 00555 * that was already installed, we know that the 00556 * dependency was not broken before so we enforce it */ 00557 00558 /* check if any of the providers for 'req' is installed */ 00559 for (i = 0; (p = dp[i]) != 0; i++) 00560 { 00561 if (pool->solvables[p].repo == installed) 00562 break; /* provider was installed */ 00563 } 00564 /* didn't find an installed provider: previously broken dependency */ 00565 if (!p) 00566 { 00567 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s)); 00568 continue; 00569 } 00570 } 00571 00572 if (!*dp) 00573 { 00574 /* nothing provides req! */ 00575 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req)); 00576 addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req); 00577 continue; 00578 } 00579 00580 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION) 00581 { 00582 POOL_DEBUG(SAT_DEBUG_RULE_CREATION," %s requires %s\n", solvable2str(pool, s), dep2str(pool, req)); 00583 for (i = 0; dp[i]; i++) 00584 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " provided by %s\n", solvid2str(pool, dp[i])); 00585 } 00586 00587 /* add 'requires' dependency */ 00588 /* rule: (-requestor|provider1|provider2|...|providerN) */ 00589 addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req); 00590 00591 /* descend the dependency tree 00592 push all non-visited providers on the work queue */ 00593 if (m) 00594 { 00595 for (; *dp; dp++) 00596 { 00597 if (!MAPTST(m, *dp)) 00598 queue_push(&workq, *dp); 00599 } 00600 } 00601 00602 } /* while, requirements of n */ 00603 00604 } /* if, requirements */ 00605 00606 /* that's all we check for src packages */ 00607 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC) 00608 continue; 00609 00610 /*----------------------------------------- 00611 * check conflicts of s 00612 */ 00613 00614 if (s->conflicts) 00615 { 00616 int ispatch = 0; 00617 00618 /* we treat conflicts in patches a bit differen: 00619 * - nevr matching 00620 * - multiversion handling 00621 * XXX: we should really handle this different, looking 00622 * at the name is a bad hack 00623 */ 00624 if (!strncmp("patch:", id2str(pool, s->name), 6)) 00625 ispatch = 1; 00626 conp = s->repo->idarraydata + s->conflicts; 00627 /* foreach conflicts of 's' */ 00628 while ((con = *conp++) != 0) 00629 { 00630 /* foreach providers of a conflict of 's' */ 00631 FOR_PROVIDES(p, pp, con) 00632 { 00633 if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con)) 00634 continue; 00635 /* dontfix: dont care about conflicts with already installed packs */ 00636 if (dontfix && pool->solvables[p].repo == installed) 00637 continue; 00638 /* p == n: self conflict */ 00639 if (p == n && !pool->allowselfconflicts) 00640 { 00641 if (ISRELDEP(con)) 00642 { 00643 Reldep *rd = GETRELDEP(pool, con); 00644 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS) 00645 continue; 00646 } 00647 p = 0; /* make it a negative assertion, aka 'uninstallable' */ 00648 } 00649 if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con)) 00650 { 00651 /* our patch conflicts with a noobsoletes (aka multiversion) package */ 00652 p = -makemultiversionconflict(solv, p, con); 00653 } 00654 /* rule: -n|-p: either solvable _or_ provider of conflict */ 00655 addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con); 00656 } 00657 } 00658 } 00659 00660 /*----------------------------------------- 00661 * check obsoletes and implicit obsoletes of a package 00662 * if ignoreinstalledsobsoletes is not set, we're also checking 00663 * obsoletes of installed packages (like newer rpm versions) 00664 */ 00665 if ((!installed || s->repo != installed) || !pool->noinstalledobsoletes) 00666 { 00667 int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n); 00668 int isinstalled = (installed && s->repo == installed); 00669 if (s->obsoletes && !noobs) 00670 { 00671 obsp = s->repo->idarraydata + s->obsoletes; 00672 /* foreach obsoletes */ 00673 while ((obs = *obsp++) != 0) 00674 { 00675 /* foreach provider of an obsoletes of 's' */ 00676 FOR_PROVIDES(p, pp, obs) 00677 { 00678 Solvable *ps = pool->solvables + p; 00679 if (p == n) 00680 continue; 00681 if (isinstalled && dontfix && ps->repo == installed) 00682 continue; /* don't repair installed/installed problems */ 00683 if (!pool->obsoleteusesprovides /* obsoletes are matched names, not provides */ 00684 && !pool_match_nevr(pool, ps, obs)) 00685 continue; 00686 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 00687 continue; 00688 if (!isinstalled) 00689 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs); 00690 else 00691 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_INSTALLEDPKG_OBSOLETES, obs); 00692 } 00693 } 00694 } 00695 /* check implicit obsoletes 00696 * for installed packages we only need to check installed/installed problems (and 00697 * only when dontfix is not set), as the others are picked up when looking at the 00698 * uninstalled package. 00699 */ 00700 if (!isinstalled || !dontfix) 00701 { 00702 FOR_PROVIDES(p, pp, s->name) 00703 { 00704 Solvable *ps = pool->solvables + p; 00705 if (p == n) 00706 continue; 00707 if (isinstalled && ps->repo != installed) 00708 continue; 00709 /* we still obsolete packages with same nevra, like rpm does */ 00710 /* (actually, rpm mixes those packages. yuck...) */ 00711 if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch)) 00712 continue; 00713 if (!pool->implicitobsoleteusesprovides && s->name != ps->name) 00714 continue; 00715 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 00716 continue; 00717 if (s->name == ps->name) 00718 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0); 00719 else 00720 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name); 00721 } 00722 } 00723 } 00724 00725 /*----------------------------------------- 00726 * add recommends to the work queue 00727 */ 00728 if (s->recommends && m) 00729 { 00730 recp = s->repo->idarraydata + s->recommends; 00731 while ((rec = *recp++) != 0) 00732 { 00733 FOR_PROVIDES(p, pp, rec) 00734 if (!MAPTST(m, p)) 00735 queue_push(&workq, p); 00736 } 00737 } 00738 if (s->suggests && m) 00739 { 00740 sugp = s->repo->idarraydata + s->suggests; 00741 while ((sug = *sugp++) != 0) 00742 { 00743 FOR_PROVIDES(p, pp, sug) 00744 if (!MAPTST(m, p)) 00745 queue_push(&workq, p); 00746 } 00747 } 00748 } 00749 queue_free(&workq); 00750 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n"); 00751 } 00752 00753 00754 /*------------------------------------------------------------------- 00755 * 00756 * Add package rules for weak rules 00757 * 00758 * m: visited solvables 00759 */ 00760 00761 void 00762 solver_addrpmrulesforweak(Solver *solv, Map *m) 00763 { 00764 Pool *pool = solv->pool; 00765 Solvable *s; 00766 Id sup, *supp; 00767 int i, n; 00768 00769 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n"); 00770 /* foreach solvable in pool */ 00771 for (i = n = 1; n < pool->nsolvables; i++, n++) 00772 { 00773 if (i == pool->nsolvables) /* wrap i */ 00774 i = 1; 00775 if (MAPTST(m, i)) /* been there */ 00776 continue; 00777 00778 s = pool->solvables + i; 00779 if (!pool_installable(pool, s)) /* only look at installable ones */ 00780 continue; 00781 00782 sup = 0; 00783 if (s->supplements) 00784 { 00785 /* find possible supplements */ 00786 supp = s->repo->idarraydata + s->supplements; 00787 while ((sup = *supp++) != ID_NULL) 00788 if (dep_possible(solv, sup, m)) 00789 break; 00790 } 00791 00792 /* if nothing found, check for enhances */ 00793 if (!sup && s->enhances) 00794 { 00795 supp = s->repo->idarraydata + s->enhances; 00796 while ((sup = *supp++) != ID_NULL) 00797 if (dep_possible(solv, sup, m)) 00798 break; 00799 } 00800 /* if nothing found, goto next solvables */ 00801 if (!sup) 00802 continue; 00803 solver_addrpmrulesforsolvable(solv, s, m); 00804 n = 0; /* check all solvables again */ 00805 } 00806 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n"); 00807 } 00808 00809 00810 /*------------------------------------------------------------------- 00811 * 00812 * add package rules for possible updates 00813 * 00814 * s: solvable 00815 * m: map of already visited solvables 00816 * allow_all: 0 = dont allow downgrades, 1 = allow all candidates 00817 */ 00818 00819 void 00820 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all) 00821 { 00822 Pool *pool = solv->pool; 00823 int i; 00824 /* queue and buffer for it */ 00825 Queue qs; 00826 Id qsbuf[64]; 00827 00828 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n"); 00829 00830 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf)); 00831 /* find update candidates for 's' */ 00832 policy_findupdatepackages(solv, s, &qs, allow_all); 00833 /* add rule for 's' if not already done */ 00834 if (!MAPTST(m, s - pool->solvables)) 00835 solver_addrpmrulesforsolvable(solv, s, m); 00836 /* foreach update candidate, add rule if not already done */ 00837 for (i = 0; i < qs.count; i++) 00838 if (!MAPTST(m, qs.elements[i])) 00839 solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m); 00840 queue_free(&qs); 00841 00842 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n"); 00843 } 00844 00845 00846 /*********************************************************************** 00847 *** 00848 *** Update/Feature rule part 00849 *** 00850 *** Those rules make sure an installed package isn't silently deleted 00851 *** 00852 ***/ 00853 00854 static Id 00855 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all) 00856 { 00857 Pool *pool = solv->pool; 00858 int i; 00859 00860 policy_findupdatepackages(solv, s, qs, allow_all); 00861 if (!qs->count) 00862 { 00863 if (allow_all) 00864 return 0; /* orphaned, don't create feature rule */ 00865 /* check if this is an orphaned package */ 00866 policy_findupdatepackages(solv, s, qs, 1); 00867 if (!qs->count) 00868 return 0; /* orphaned, don't create update rule */ 00869 qs->count = 0; 00870 return -SYSTEMSOLVABLE; /* supported but not installable */ 00871 } 00872 if (allow_all) 00873 return s - pool->solvables; 00874 /* check if it is ok to keep the installed package */ 00875 for (i = 0; i < qs->count; i++) 00876 { 00877 Solvable *ns = pool->solvables + qs->elements[i]; 00878 if (s->evr == ns->evr && solvable_identical(s, ns)) 00879 return s - pool->solvables; 00880 } 00881 /* nope, it must be some other package */ 00882 return -SYSTEMSOLVABLE; 00883 } 00884 00885 /* add packages from the dup repositories to the update candidates 00886 * this isn't needed for the global dup mode as all packages are 00887 * from dup repos in that case */ 00888 static void 00889 addduppackages(Solver *solv, Solvable *s, Queue *qs) 00890 { 00891 Queue dupqs; 00892 Id p, dupqsbuf[64]; 00893 int i; 00894 int oldnoupdateprovide = solv->noupdateprovide; 00895 00896 queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf)); 00897 solv->noupdateprovide = 1; 00898 policy_findupdatepackages(solv, s, &dupqs, 2); 00899 solv->noupdateprovide = oldnoupdateprovide; 00900 for (i = 0; i < dupqs.count; i++) 00901 { 00902 p = dupqs.elements[i]; 00903 if (MAPTST(&solv->dupmap, p)) 00904 queue_pushunique(qs, p); 00905 } 00906 queue_free(&dupqs); 00907 } 00908 00909 /*------------------------------------------------------------------- 00910 * 00911 * add rule for update 00912 * (A|A1|A2|A3...) An = update candidates for A 00913 * 00914 * s = (installed) solvable 00915 */ 00916 00917 void 00918 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all) 00919 { 00920 /* installed packages get a special upgrade allowed rule */ 00921 Pool *pool = solv->pool; 00922 Id p, d; 00923 Queue qs; 00924 Id qsbuf[64]; 00925 00926 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n"); 00927 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf)); 00928 p = s - pool->solvables; 00929 /* find update candidates for 's' */ 00930 if (solv->dupmap_all) 00931 p = finddistupgradepackages(solv, s, &qs, allow_all); 00932 else 00933 policy_findupdatepackages(solv, s, &qs, allow_all); 00934 if (!allow_all && !solv->dupmap_all && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)) 00935 addduppackages(solv, s, &qs); 00936 00937 if (!allow_all && qs.count && solv->noobsoletes.size) 00938 { 00939 int i, j; 00940 00941 d = pool_queuetowhatprovides(pool, &qs); 00942 /* filter out all noobsoletes packages as they don't update */ 00943 for (i = j = 0; i < qs.count; i++) 00944 { 00945 if (MAPTST(&solv->noobsoletes, qs.elements[i])) 00946 { 00947 /* it's ok if they have same nevra */ 00948 Solvable *ps = pool->solvables + qs.elements[i]; 00949 if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch) 00950 continue; 00951 } 00952 qs.elements[j++] = qs.elements[i]; 00953 } 00954 if (j < qs.count) 00955 { 00956 if (d && solv->installed && s->repo == solv->installed && 00957 (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, s - pool->solvables - solv->installed->start)))) 00958 { 00959 if (!solv->multiversionupdaters) 00960 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id)); 00961 solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d; 00962 } 00963 if (j == 0 && p == -SYSTEMSOLVABLE && solv->dupmap_all) 00964 { 00965 queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */ 00966 j = qs.count; 00967 } 00968 qs.count = j; 00969 } 00970 } 00971 if (qs.count && p == -SYSTEMSOLVABLE) 00972 p = queue_shift(&qs); 00973 d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0; 00974 queue_free(&qs); 00975 solver_addrule(solv, p, d); /* allow update of s */ 00976 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n"); 00977 } 00978 00979 static inline void 00980 disableupdaterule(Solver *solv, Id p) 00981 { 00982 Rule *r; 00983 00984 MAPSET(&solv->noupdate, p - solv->installed->start); 00985 r = solv->rules + solv->updaterules + (p - solv->installed->start); 00986 if (r->p && r->d >= 0) 00987 solver_disablerule(solv, r); 00988 r = solv->rules + solv->featurerules + (p - solv->installed->start); 00989 if (r->p && r->d >= 0) 00990 solver_disablerule(solv, r); 00991 } 00992 00993 static inline void 00994 reenableupdaterule(Solver *solv, Id p) 00995 { 00996 Pool *pool = solv->pool; 00997 Rule *r; 00998 00999 MAPCLR(&solv->noupdate, p - solv->installed->start); 01000 r = solv->rules + solv->updaterules + (p - solv->installed->start); 01001 if (r->p) 01002 { 01003 if (r->d >= 0) 01004 return; 01005 solver_enablerule(solv, r); 01006 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) 01007 { 01008 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); 01009 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r); 01010 } 01011 return; 01012 } 01013 r = solv->rules + solv->featurerules + (p - solv->installed->start); 01014 if (r->p && r->d < 0) 01015 { 01016 solver_enablerule(solv, r); 01017 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) 01018 { 01019 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); 01020 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r); 01021 } 01022 } 01023 } 01024 01025 01026 /*********************************************************************** 01027 *** 01028 *** Infarch rule part 01029 *** 01030 *** Infarch rules make sure the solver uses the best architecture of 01031 *** a package if multiple archetectures are available 01032 *** 01033 ***/ 01034 01035 void 01036 solver_addinfarchrules(Solver *solv, Map *addedmap) 01037 { 01038 Pool *pool = solv->pool; 01039 int first, i, j; 01040 Id p, pp, a, aa, bestarch; 01041 Solvable *s, *ps, *bests; 01042 Queue badq, allowedarchs; 01043 01044 queue_init(&badq); 01045 queue_init(&allowedarchs); 01046 solv->infarchrules = solv->nrules; 01047 for (i = 1; i < pool->nsolvables; i++) 01048 { 01049 if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i)) 01050 continue; 01051 s = pool->solvables + i; 01052 first = i; 01053 bestarch = 0; 01054 bests = 0; 01055 queue_empty(&allowedarchs); 01056 FOR_PROVIDES(p, pp, s->name) 01057 { 01058 ps = pool->solvables + p; 01059 if (ps->name != s->name || !MAPTST(addedmap, p)) 01060 continue; 01061 if (p == i) 01062 first = 0; 01063 if (first) 01064 break; 01065 a = ps->arch; 01066 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0; 01067 if (a != 1 && pool->installed && ps->repo == pool->installed) 01068 { 01069 if (!solv->dupmap_all && !(solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))) 01070 queue_pushunique(&allowedarchs, ps->arch); /* also ok to keep this architecture */ 01071 continue; /* ignore installed solvables when calculating the best arch */ 01072 } 01073 if (a && a != 1 && (!bestarch || a < bestarch)) 01074 { 01075 bestarch = a; 01076 bests = ps; 01077 } 01078 } 01079 if (first) 01080 continue; 01081 /* speed up common case where installed package already has best arch */ 01082 if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch) 01083 allowedarchs.count--; /* installed arch is best */ 01084 queue_empty(&badq); 01085 FOR_PROVIDES(p, pp, s->name) 01086 { 01087 ps = pool->solvables + p; 01088 if (ps->name != s->name || !MAPTST(addedmap, p)) 01089 continue; 01090 a = ps->arch; 01091 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0; 01092 if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0) 01093 { 01094 if (pool->installed && ps->repo == pool->installed) 01095 continue; /* always ok to keep an installed package */ 01096 for (j = 0; j < allowedarchs.count; j++) 01097 { 01098 aa = allowedarchs.elements[j]; 01099 if (ps->arch == aa) 01100 break; 01101 aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0; 01102 if (aa && ((a ^ aa) & 0xffff0000) == 0) 01103 break; /* compatible */ 01104 } 01105 if (j == allowedarchs.count) 01106 queue_push(&badq, p); 01107 } 01108 } 01109 if (!badq.count) 01110 continue; 01111 /* block all solvables in the badq! */ 01112 for (j = 0; j < badq.count; j++) 01113 { 01114 p = badq.elements[j]; 01115 solver_addrule(solv, -p, 0); 01116 } 01117 } 01118 queue_free(&badq); 01119 queue_free(&allowedarchs); 01120 solv->infarchrules_end = solv->nrules; 01121 } 01122 01123 static inline void 01124 disableinfarchrule(Solver *solv, Id name) 01125 { 01126 Pool *pool = solv->pool; 01127 Rule *r; 01128 int i; 01129 for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++) 01130 { 01131 if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name) 01132 solver_disablerule(solv, r); 01133 } 01134 } 01135 01136 static inline void 01137 reenableinfarchrule(Solver *solv, Id name) 01138 { 01139 Pool *pool = solv->pool; 01140 Rule *r; 01141 int i; 01142 for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++) 01143 { 01144 if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name) 01145 { 01146 solver_enablerule(solv, r); 01147 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) 01148 { 01149 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); 01150 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r); 01151 } 01152 } 01153 } 01154 } 01155 01156 01157 /*********************************************************************** 01158 *** 01159 *** Dup rule part 01160 *** 01161 *** Dup rules make sure a package is selected from the specified dup 01162 *** repositories if an update candidate is included in one of them. 01163 *** 01164 ***/ 01165 01166 void 01167 solver_createdupmaps(Solver *solv) 01168 { 01169 Queue *job = &solv->job; 01170 Pool *pool = solv->pool; 01171 Repo *repo; 01172 Id how, what, p, pi, pp, obs, *obsp; 01173 Solvable *s, *ps; 01174 int i; 01175 01176 map_init(&solv->dupmap, pool->nsolvables); 01177 map_init(&solv->dupinvolvedmap, pool->nsolvables); 01178 for (i = 0; i < job->count; i += 2) 01179 { 01180 how = job->elements[i]; 01181 what = job->elements[i + 1]; 01182 switch (how & SOLVER_JOBMASK) 01183 { 01184 case SOLVER_DISTUPGRADE: 01185 if ((how & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_REPO) 01186 break; 01187 if (what <= 0 || what > pool->nrepos) 01188 break; 01189 repo = pool_id2repo(pool, what); 01190 FOR_REPO_SOLVABLES(repo, p, s) 01191 { 01192 MAPSET(&solv->dupmap, p); 01193 FOR_PROVIDES(pi, pp, s->name) 01194 { 01195 ps = pool->solvables + pi; 01196 if (ps->name != s->name) 01197 continue; 01198 MAPSET(&solv->dupinvolvedmap, pi); 01199 } 01200 if (s->obsoletes) 01201 { 01202 /* FIXME: check obsoletes/provides combination */ 01203 obsp = s->repo->idarraydata + s->obsoletes; 01204 while ((obs = *obsp++) != 0) 01205 { 01206 FOR_PROVIDES(pi, pp, obs) 01207 { 01208 Solvable *pis = pool->solvables + pi; 01209 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pis, obs)) 01210 continue; 01211 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pis)) 01212 continue; 01213 MAPSET(&solv->dupinvolvedmap, pi); 01214 } 01215 } 01216 } 01217 } 01218 break; 01219 default: 01220 break; 01221 } 01222 } 01223 MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE); 01224 } 01225 01226 void 01227 solver_freedupmaps(Solver *solv) 01228 { 01229 map_free(&solv->dupmap); 01230 /* we no longer free solv->dupinvolvedmap as we need it in 01231 * policy's priority pruning code. sigh. */ 01232 } 01233 01234 void 01235 solver_addduprules(Solver *solv, Map *addedmap) 01236 { 01237 Pool *pool = solv->pool; 01238 Id p, pp; 01239 Solvable *s, *ps; 01240 int first, i; 01241 01242 solv->duprules = solv->nrules; 01243 for (i = 1; i < pool->nsolvables; i++) 01244 { 01245 if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i)) 01246 continue; 01247 s = pool->solvables + i; 01248 first = i; 01249 FOR_PROVIDES(p, pp, s->name) 01250 { 01251 ps = pool->solvables + p; 01252 if (ps->name != s->name || !MAPTST(addedmap, p)) 01253 continue; 01254 if (p == i) 01255 first = 0; 01256 if (first) 01257 break; 01258 if (!MAPTST(&solv->dupinvolvedmap, p)) 01259 continue; 01260 if (solv->installed && ps->repo == solv->installed) 01261 { 01262 if (!solv->updatemap.size) 01263 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start); 01264 MAPSET(&solv->updatemap, p - solv->installed->start); 01265 if (!MAPTST(&solv->dupmap, p)) 01266 { 01267 Id ip, ipp; 01268 /* is installed identical to a good one? */ 01269 FOR_PROVIDES(ip, ipp, ps->name) 01270 { 01271 Solvable *is = pool->solvables + ip; 01272 if (!MAPTST(&solv->dupmap, ip)) 01273 continue; 01274 if (is->evr == ps->evr && solvable_identical(ps, is)) 01275 break; 01276 } 01277 if (!ip) 01278 solver_addrule(solv, -p, 0); /* no match, sorry */ 01279 } 01280 } 01281 else if (!MAPTST(&solv->dupmap, p)) 01282 solver_addrule(solv, -p, 0); 01283 } 01284 } 01285 solv->duprules_end = solv->nrules; 01286 } 01287 01288 01289 static inline void 01290 disableduprule(Solver *solv, Id name) 01291 { 01292 Pool *pool = solv->pool; 01293 Rule *r; 01294 int i; 01295 for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++) 01296 { 01297 if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name) 01298 solver_disablerule(solv, r); 01299 } 01300 } 01301 01302 static inline void 01303 reenableduprule(Solver *solv, Id name) 01304 { 01305 Pool *pool = solv->pool; 01306 Rule *r; 01307 int i; 01308 for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++) 01309 { 01310 if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name) 01311 { 01312 solver_enablerule(solv, r); 01313 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) 01314 { 01315 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); 01316 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r); 01317 } 01318 } 01319 } 01320 } 01321 01322 01323 /*********************************************************************** 01324 *** 01325 *** Policy rule disabling/reenabling 01326 *** 01327 *** Disable all policy rules that conflict with our jobs. If a job 01328 *** gets disabled later on, reenable the involved policy rules again. 01329 *** 01330 ***/ 01331 01332 #define DISABLE_UPDATE 1 01333 #define DISABLE_INFARCH 2 01334 #define DISABLE_DUP 3 01335 01336 static void 01337 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q) 01338 { 01339 Pool *pool = solv->pool; 01340 Id select, p, pp; 01341 Repo *installed; 01342 Solvable *s; 01343 int i, j, set, qstart, pass; 01344 Map omap; 01345 01346 installed = solv->installed; 01347 select = how & SOLVER_SELECTMASK; 01348 switch (how & SOLVER_JOBMASK) 01349 { 01350 case SOLVER_INSTALL: 01351 set = how & SOLVER_SETMASK; 01352 if (!(set & SOLVER_NOAUTOSET)) 01353 { 01354 /* automatically add set bits by analysing the job */ 01355 if (select == SOLVER_SOLVABLE) 01356 set |= SOLVER_SETARCH | SOLVER_SETVENDOR | SOLVER_SETREPO | SOLVER_SETEVR; 01357 else if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(what)) 01358 { 01359 Reldep *rd = GETRELDEP(pool, what); 01360 if (rd->flags == REL_EQ && select == SOLVER_SOLVABLE_NAME) 01361 { 01362 #if !defined(DEBIAN_SEMANTICS) 01363 const char *evr = id2str(pool, rd->evr); 01364 if (strchr(evr, '-')) 01365 set |= SOLVER_SETEVR; 01366 else 01367 set |= SOLVER_SETEV; 01368 #else 01369 set |= SOLVER_SETEVR; 01370 #endif 01371 } 01372 if (rd->flags <= 7 && ISRELDEP(rd->name)) 01373 rd = GETRELDEP(pool, rd->name); 01374 if (rd->flags == REL_ARCH) 01375 set |= SOLVER_SETARCH; 01376 } 01377 } 01378 else 01379 set &= ~SOLVER_NOAUTOSET; 01380 if (!set) 01381 return; 01382 if ((set & SOLVER_SETARCH) != 0 && solv->infarchrules != solv->infarchrules_end) 01383 { 01384 if (select == SOLVER_SOLVABLE) 01385 queue_push2(q, DISABLE_INFARCH, pool->solvables[what].name); 01386 else 01387 { 01388 int qcnt = q->count; 01389 FOR_JOB_SELECT(p, pp, select, what) 01390 { 01391 s = pool->solvables + p; 01392 /* unify names */ 01393 for (i = qcnt; i < q->count; i += 2) 01394 if (q->elements[i + 1] == s->name) 01395 break; 01396 if (i < q->count) 01397 continue; 01398 queue_push2(q, DISABLE_INFARCH, s->name); 01399 } 01400 } 01401 } 01402 if ((set & SOLVER_SETREPO) != 0 && solv->duprules != solv->duprules_end) 01403 { 01404 if (select == SOLVER_SOLVABLE) 01405 queue_push2(q, DISABLE_DUP, pool->solvables[what].name); 01406 else 01407 { 01408 int qcnt = q->count; 01409 FOR_JOB_SELECT(p, pp, select, what) 01410 { 01411 s = pool->solvables + p; 01412 /* unify names */ 01413 for (i = qcnt; i < q->count; i += 2) 01414 if (q->elements[i + 1] == s->name) 01415 break; 01416 if (i < q->count) 01417 continue; 01418 queue_push2(q, DISABLE_DUP, s->name); 01419 } 01420 } 01421 } 01422 if (!installed) 01423 return; 01424 /* now the hard part: disable some update rules */ 01425 01426 /* first check if we have noobs or installed packages in the job */ 01427 FOR_JOB_SELECT(p, pp, select, what) 01428 { 01429 if (pool->solvables[p].repo == installed) 01430 { 01431 if (select == SOLVER_SOLVABLE) 01432 queue_push2(q, DISABLE_UPDATE, what); 01433 return; 01434 } 01435 if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p)) 01436 return; 01437 } 01438 01439 /* all job packages obsolete */ 01440 qstart = q->count; 01441 pass = 0; 01442 memset(&omap, 0, sizeof(omap)); 01443 FOR_JOB_SELECT(p, pp, select, what) 01444 { 01445 Id p2, pp2; 01446 01447 if (pass == 1) 01448 map_grow(&omap, installed->end - installed->start); 01449 s = pool->solvables + p; 01450 if (s->obsoletes) 01451 { 01452 Id obs, *obsp; 01453 obsp = s->repo->idarraydata + s->obsoletes; 01454 while ((obs = *obsp++) != 0) 01455 FOR_PROVIDES(p2, pp2, obs) 01456 { 01457 Solvable *ps = pool->solvables + p2; 01458 if (ps->repo != installed) 01459 continue; 01460 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs)) 01461 continue; 01462 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 01463 continue; 01464 if (pass) 01465 MAPSET(&omap, p2 - installed->start); 01466 else 01467 queue_push2(q, DISABLE_UPDATE, p2); 01468 } 01469 } 01470 FOR_PROVIDES(p2, pp2, s->name) 01471 { 01472 Solvable *ps = pool->solvables + p2; 01473 if (ps->repo != installed) 01474 continue; 01475 if (!pool->implicitobsoleteusesprovides && ps->name != s->name) 01476 continue; 01477 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 01478 continue; 01479 if (pass) 01480 MAPSET(&omap, p2 - installed->start); 01481 else 01482 queue_push2(q, DISABLE_UPDATE, p2); 01483 } 01484 if (pass) 01485 { 01486 for (i = j = qstart; i < q->count; i += 2) 01487 { 01488 if (MAPTST(&omap, q->elements[i + 1] - installed->start)) 01489 { 01490 MAPCLR(&omap, q->elements[i + 1] - installed->start); 01491 q->elements[j + 1] = q->elements[i + 1]; 01492 j += 2; 01493 } 01494 } 01495 queue_truncate(q, j); 01496 } 01497 if (q->count == qstart) 01498 break; 01499 pass++; 01500 } 01501 if (omap.size) 01502 map_free(&omap); 01503 01504 if (qstart == q->count) 01505 return; /* nothing to prune */ 01506 if ((set & (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) == (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) 01507 return; /* all is set */ 01508 01509 /* now that we know which installed packages are obsoleted check each of them */ 01510 for (i = j = qstart; i < q->count; i += 2) 01511 { 01512 Solvable *is = pool->solvables + q->elements[i + 1]; 01513 FOR_JOB_SELECT(p, pp, select, what) 01514 { 01515 int illegal = 0; 01516 s = pool->solvables + p; 01517 if ((set & SOLVER_SETEVR) != 0) 01518 illegal |= POLICY_ILLEGAL_DOWNGRADE; /* ignore */ 01519 if ((set & SOLVER_SETARCH) != 0) 01520 illegal |= POLICY_ILLEGAL_ARCHCHANGE; /* ignore */ 01521 if ((set & SOLVER_SETVENDOR) != 0) 01522 illegal |= POLICY_ILLEGAL_VENDORCHANGE; /* ignore */ 01523 illegal = policy_is_illegal(solv, is, s, illegal); 01524 if (illegal && illegal == POLICY_ILLEGAL_DOWNGRADE && (set & SOLVER_SETEV) != 0) 01525 { 01526 /* it's ok if the EV is different */ 01527 if (evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE_EVONLY) != 0) 01528 illegal = 0; 01529 } 01530 if (illegal) 01531 break; 01532 } 01533 if (!p) 01534 { 01535 /* no package conflicts with the update rule */ 01536 /* thus keep the DISABLE_UPDATE */ 01537 q->elements[j + 1] = q->elements[i + 1]; 01538 j += 2; 01539 } 01540 } 01541 queue_truncate(q, j); 01542 return; 01543 01544 case SOLVER_ERASE: 01545 if (!installed) 01546 break; 01547 FOR_JOB_SELECT(p, pp, select, what) 01548 if (pool->solvables[p].repo == installed) 01549 queue_push2(q, DISABLE_UPDATE, p); 01550 return; 01551 default: 01552 return; 01553 } 01554 } 01555 01556 /* disable all policy rules that are in conflict with our job list */ 01557 void 01558 solver_disablepolicyrules(Solver *solv) 01559 { 01560 Queue *job = &solv->job; 01561 int i, j; 01562 Queue allq; 01563 Rule *r; 01564 Id lastjob = -1; 01565 Id allqbuf[128]; 01566 01567 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf)); 01568 01569 for (i = solv->jobrules; i < solv->jobrules_end; i++) 01570 { 01571 r = solv->rules + i; 01572 if (r->d < 0) /* disabled? */ 01573 continue; 01574 j = solv->ruletojob.elements[i - solv->jobrules]; 01575 if (j == lastjob) 01576 continue; 01577 lastjob = j; 01578 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq); 01579 } 01580 if (solv->cleandepsmap.size) 01581 { 01582 solver_createcleandepsmap(solv); 01583 for (i = solv->installed->start; i < solv->installed->end; i++) 01584 if (MAPTST(&solv->cleandepsmap, i - solv->installed->start)) 01585 queue_push2(&allq, DISABLE_UPDATE, i); 01586 } 01587 MAPZERO(&solv->noupdate); 01588 for (i = 0; i < allq.count; i += 2) 01589 { 01590 Id type = allq.elements[i], arg = allq.elements[i + 1]; 01591 switch(type) 01592 { 01593 case DISABLE_UPDATE: 01594 disableupdaterule(solv, arg); 01595 break; 01596 case DISABLE_INFARCH: 01597 disableinfarchrule(solv, arg); 01598 break; 01599 case DISABLE_DUP: 01600 disableduprule(solv, arg); 01601 break; 01602 default: 01603 break; 01604 } 01605 } 01606 queue_free(&allq); 01607 } 01608 01609 /* we just disabled job #jobidx, now reenable all policy rules that were 01610 * disabled because of this job */ 01611 void 01612 solver_reenablepolicyrules(Solver *solv, int jobidx) 01613 { 01614 Queue *job = &solv->job; 01615 int i, j; 01616 Queue q, allq; 01617 Rule *r; 01618 Id lastjob = -1; 01619 Id qbuf[32], allqbuf[128]; 01620 01621 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf)); 01622 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf)); 01623 jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q); 01624 if (!q.count) 01625 return; 01626 for (i = solv->jobrules; i < solv->jobrules_end; i++) 01627 { 01628 r = solv->rules + i; 01629 if (r->d < 0) /* disabled? */ 01630 continue; 01631 j = solv->ruletojob.elements[i - solv->jobrules]; 01632 if (j == lastjob) 01633 continue; 01634 lastjob = j; 01635 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq); 01636 } 01637 if (solv->cleandepsmap.size) 01638 { 01639 solver_createcleandepsmap(solv); 01640 for (i = solv->installed->start; i < solv->installed->end; i++) 01641 if (MAPTST(&solv->cleandepsmap, i - solv->installed->start)) 01642 queue_push2(&allq, DISABLE_UPDATE, i); 01643 } 01644 for (j = 0; j < q.count; j += 2) 01645 { 01646 Id type = q.elements[j], arg = q.elements[j + 1]; 01647 for (i = 0; i < allq.count; i += 2) 01648 if (allq.elements[i] == type && allq.elements[i + 1] == arg) 01649 break; 01650 if (i < allq.count) 01651 continue; /* still disabled */ 01652 switch(type) 01653 { 01654 case DISABLE_UPDATE: 01655 reenableupdaterule(solv, arg); 01656 break; 01657 case DISABLE_INFARCH: 01658 reenableinfarchrule(solv, arg); 01659 break; 01660 case DISABLE_DUP: 01661 reenableduprule(solv, arg); 01662 break; 01663 } 01664 } 01665 queue_free(&allq); 01666 queue_free(&q); 01667 } 01668 01669 01670 /*********************************************************************** 01671 *** 01672 *** Rule info part, tell the user what the rule is about. 01673 *** 01674 ***/ 01675 01676 static void 01677 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep) 01678 { 01679 Pool *pool = solv->pool; 01680 Rule *r; 01681 Id w2, op, od, ow2; 01682 01683 /* check if this creates the rule we're searching for */ 01684 r = solv->rules + solv->ruleinfoq->elements[0]; 01685 op = r->p; 01686 od = r->d < 0 ? -r->d - 1 : r->d; 01687 ow2 = 0; 01688 01689 /* normalize */ 01690 w2 = d > 0 ? 0 : d; 01691 if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1])) 01692 { 01693 w2 = pool->whatprovidesdata[d]; 01694 d = 0; 01695 01696 } 01697 if (p > 0 && d < 0) /* this hack is used for buddy deps */ 01698 { 01699 w2 = p; 01700 p = d; 01701 } 01702 01703 if (d > 0) 01704 { 01705 if (p != op && !od) 01706 return; 01707 if (d != od) 01708 { 01709 Id *dp = pool->whatprovidesdata + d; 01710 Id *odp = pool->whatprovidesdata + od; 01711 while (*dp) 01712 if (*dp++ != *odp++) 01713 return; 01714 if (*odp) 01715 return; 01716 } 01717 w2 = 0; 01718 /* handle multiversion conflict rules */ 01719 if (p < 0 && pool->whatprovidesdata[d] < 0) 01720 { 01721 w2 = pool->whatprovidesdata[d]; 01722 /* XXX: free memory */ 01723 } 01724 } 01725 else 01726 { 01727 if (od) 01728 return; 01729 ow2 = r->w2; 01730 if (p > w2) 01731 { 01732 if (w2 != op || p != ow2) 01733 return; 01734 } 01735 else 01736 { 01737 if (p != op || w2 != ow2) 01738 return; 01739 } 01740 } 01741 /* yep, rule matches. record info */ 01742 queue_push(solv->ruleinfoq, type); 01743 if (type == SOLVER_RULE_RPM_SAME_NAME) 01744 { 01745 /* we normalize same name order */ 01746 queue_push(solv->ruleinfoq, op < 0 ? -op : 0); 01747 queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0); 01748 } 01749 else 01750 { 01751 queue_push(solv->ruleinfoq, p < 0 ? -p : 0); 01752 queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0); 01753 } 01754 queue_push(solv->ruleinfoq, dep); 01755 } 01756 01757 static int 01758 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp) 01759 { 01760 const Id *a = ap, *b = bp; 01761 int r; 01762 01763 r = a[0] - b[0]; 01764 if (r) 01765 return r; 01766 r = a[1] - b[1]; 01767 if (r) 01768 return r; 01769 r = a[2] - b[2]; 01770 if (r) 01771 return r; 01772 r = a[3] - b[3]; 01773 if (r) 01774 return r; 01775 return 0; 01776 } 01777 01778 int 01779 solver_allruleinfos(Solver *solv, Id rid, Queue *rq) 01780 { 01781 Pool *pool = solv->pool; 01782 Rule *r = solv->rules + rid; 01783 int i, j; 01784 01785 queue_empty(rq); 01786 if (rid <= 0 || rid >= solv->rpmrules_end) 01787 { 01788 Id type, from, to, dep; 01789 type = solver_ruleinfo(solv, rid, &from, &to, &dep); 01790 queue_push(rq, type); 01791 queue_push(rq, from); 01792 queue_push(rq, to); 01793 queue_push(rq, dep); 01794 return 1; 01795 } 01796 if (r->p >= 0) 01797 return 0; 01798 queue_push(rq, rid); 01799 solv->ruleinfoq = rq; 01800 solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0); 01801 /* also try reverse direction for conflicts */ 01802 if ((r->d == 0 || r->d == -1) && r->w2 < 0) 01803 solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0); 01804 solv->ruleinfoq = 0; 01805 queue_shift(rq); 01806 /* now sort & unify em */ 01807 if (!rq->count) 01808 return 0; 01809 sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0); 01810 /* throw out identical entries */ 01811 for (i = j = 0; i < rq->count; i += 4) 01812 { 01813 if (j) 01814 { 01815 if (rq->elements[i] == rq->elements[j - 4] && 01816 rq->elements[i + 1] == rq->elements[j - 3] && 01817 rq->elements[i + 2] == rq->elements[j - 2] && 01818 rq->elements[i + 3] == rq->elements[j - 1]) 01819 continue; 01820 } 01821 rq->elements[j++] = rq->elements[i]; 01822 rq->elements[j++] = rq->elements[i + 1]; 01823 rq->elements[j++] = rq->elements[i + 2]; 01824 rq->elements[j++] = rq->elements[i + 3]; 01825 } 01826 rq->count = j; 01827 return j / 4; 01828 } 01829 01830 SolverRuleinfo 01831 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp) 01832 { 01833 Pool *pool = solv->pool; 01834 Rule *r = solv->rules + rid; 01835 SolverRuleinfo type = SOLVER_RULE_UNKNOWN; 01836 01837 if (fromp) 01838 *fromp = 0; 01839 if (top) 01840 *top = 0; 01841 if (depp) 01842 *depp = 0; 01843 if (rid > 0 && rid < solv->rpmrules_end) 01844 { 01845 Queue rq; 01846 int i; 01847 01848 if (r->p >= 0) 01849 return SOLVER_RULE_RPM; 01850 if (fromp) 01851 *fromp = -r->p; 01852 queue_init(&rq); 01853 queue_push(&rq, rid); 01854 solv->ruleinfoq = &rq; 01855 solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0); 01856 /* also try reverse direction for conflicts */ 01857 if ((r->d == 0 || r->d == -1) && r->w2 < 0) 01858 solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0); 01859 solv->ruleinfoq = 0; 01860 type = SOLVER_RULE_RPM; 01861 for (i = 1; i < rq.count; i += 4) 01862 { 01863 Id qt, qo, qp, qd; 01864 qt = rq.elements[i]; 01865 qp = rq.elements[i + 1]; 01866 qo = rq.elements[i + 2]; 01867 qd = rq.elements[i + 3]; 01868 if (type == SOLVER_RULE_RPM || type > qt) 01869 { 01870 type = qt; 01871 if (fromp) 01872 *fromp = qp; 01873 if (top) 01874 *top = qo; 01875 if (depp) 01876 *depp = qd; 01877 } 01878 } 01879 queue_free(&rq); 01880 return type; 01881 } 01882 if (rid >= solv->jobrules && rid < solv->jobrules_end) 01883 { 01884 Id jidx = solv->ruletojob.elements[rid - solv->jobrules]; 01885 if (fromp) 01886 *fromp = jidx; 01887 if (top) 01888 *top = solv->job.elements[jidx]; 01889 if (depp) 01890 *depp = solv->job.elements[jidx + 1]; 01891 if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF) 01892 return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP; 01893 return SOLVER_RULE_JOB; 01894 } 01895 if (rid >= solv->updaterules && rid < solv->updaterules_end) 01896 { 01897 if (fromp) 01898 *fromp = solv->installed->start + (rid - solv->updaterules); 01899 return SOLVER_RULE_UPDATE; 01900 } 01901 if (rid >= solv->featurerules && rid < solv->featurerules_end) 01902 { 01903 if (fromp) 01904 *fromp = solv->installed->start + (rid - solv->featurerules); 01905 return SOLVER_RULE_FEATURE; 01906 } 01907 if (rid >= solv->duprules && rid < solv->duprules_end) 01908 { 01909 if (fromp) 01910 *fromp = -r->p; 01911 if (depp) 01912 *depp = pool->solvables[-r->p].name; 01913 return SOLVER_RULE_DISTUPGRADE; 01914 } 01915 if (rid >= solv->infarchrules && rid < solv->infarchrules_end) 01916 { 01917 if (fromp) 01918 *fromp = -r->p; 01919 if (depp) 01920 *depp = pool->solvables[-r->p].name; 01921 return SOLVER_RULE_INFARCH; 01922 } 01923 if (rid >= solv->choicerules && rid < solv->choicerules_end) 01924 { 01925 return SOLVER_RULE_CHOICE; 01926 } 01927 if (rid >= solv->learntrules) 01928 { 01929 return SOLVER_RULE_LEARNT; 01930 } 01931 return SOLVER_RULE_UNKNOWN; 01932 } 01933 01934 void 01935 solver_addchoicerules(Solver *solv) 01936 { 01937 Pool *pool = solv->pool; 01938 Map m, mneg; 01939 Rule *r; 01940 Queue q, qi; 01941 int i, j, rid, havechoice; 01942 Id p, d, *pp; 01943 Id p2, pp2; 01944 Solvable *s, *s2; 01945 01946 solv->choicerules = solv->nrules; 01947 if (!pool->installed) 01948 { 01949 solv->choicerules_end = solv->nrules; 01950 return; 01951 } 01952 solv->choicerules_ref = sat_calloc(solv->rpmrules_end, sizeof(Id)); 01953 queue_init(&q); 01954 queue_init(&qi); 01955 map_init(&m, pool->nsolvables); 01956 map_init(&mneg, pool->nsolvables); 01957 /* set up negative assertion map from infarch and dup rules */ 01958 for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++) 01959 if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1)) 01960 MAPSET(&mneg, -r->p); 01961 for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++) 01962 if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1)) 01963 MAPSET(&mneg, -r->p); 01964 for (rid = 1; rid < solv->rpmrules_end ; rid++) 01965 { 01966 r = solv->rules + rid; 01967 if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0)) 01968 continue; /* only look at requires rules */ 01969 // solver_printrule(solv, SAT_DEBUG_RESULT, r); 01970 queue_empty(&q); 01971 queue_empty(&qi); 01972 havechoice = 0; 01973 FOR_RULELITERALS(p, pp, r) 01974 { 01975 if (p < 0) 01976 continue; 01977 s = pool->solvables + p; 01978 if (!s->repo) 01979 continue; 01980 if (s->repo == pool->installed) 01981 { 01982 queue_push(&q, p); 01983 continue; 01984 } 01985 /* check if this package is "blocked" by a installed package */ 01986 s2 = 0; 01987 FOR_PROVIDES(p2, pp2, s->name) 01988 { 01989 s2 = pool->solvables + p2; 01990 if (s2->repo != pool->installed) 01991 continue; 01992 if (!pool->implicitobsoleteusesprovides && s->name != s2->name) 01993 continue; 01994 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2)) 01995 continue; 01996 break; 01997 } 01998 if (p2) 01999 { 02000 /* found installed package p2 that we can update to p */ 02001 if (MAPTST(&mneg, p)) 02002 continue; 02003 if (policy_is_illegal(solv, s2, s, 0)) 02004 continue; 02005 queue_push(&qi, p2); 02006 queue_push(&q, p); 02007 continue; 02008 } 02009 if (s->obsoletes) 02010 { 02011 Id obs, *obsp = s->repo->idarraydata + s->obsoletes; 02012 s2 = 0; 02013 while ((obs = *obsp++) != 0) 02014 { 02015 FOR_PROVIDES(p2, pp2, obs) 02016 { 02017 s2 = pool->solvables + p2; 02018 if (s2->repo != pool->installed) 02019 continue; 02020 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs)) 02021 continue; 02022 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2)) 02023 continue; 02024 break; 02025 } 02026 if (p2) 02027 break; 02028 } 02029 if (obs) 02030 { 02031 /* found installed package p2 that we can update to p */ 02032 if (MAPTST(&mneg, p)) 02033 continue; 02034 if (policy_is_illegal(solv, s2, s, 0)) 02035 continue; 02036 queue_push(&qi, p2); 02037 queue_push(&q, p); 02038 continue; 02039 } 02040 } 02041 /* package p is independent of the installed ones */ 02042 havechoice = 1; 02043 } 02044 if (!havechoice || !q.count) 02045 continue; /* no choice */ 02046 02047 /* now check the update rules of the installed package. 02048 * if all packages of the update rules are contained in 02049 * the dependency rules, there's no need to set up the choice rule */ 02050 map_empty(&m); 02051 FOR_RULELITERALS(p, pp, r) 02052 if (p > 0) 02053 MAPSET(&m, p); 02054 for (i = 0; i < qi.count; i++) 02055 { 02056 if (!qi.elements[i]) 02057 continue; 02058 Rule *ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start); 02059 if (!ur->p) 02060 ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start); 02061 if (!ur->p) 02062 continue; 02063 FOR_RULELITERALS(p, pp, ur) 02064 if (!MAPTST(&m, p)) 02065 break; 02066 if (p) 02067 break; 02068 for (j = i + 1; j < qi.count; j++) 02069 if (qi.elements[i] == qi.elements[j]) 02070 qi.elements[j] = 0; 02071 } 02072 if (i == qi.count) 02073 { 02074 #if 0 02075 printf("skipping choice "); 02076 solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid); 02077 #endif 02078 continue; 02079 } 02080 d = q.count ? pool_queuetowhatprovides(pool, &q) : 0; 02081 solver_addrule(solv, r->p, d); 02082 queue_push(&solv->weakruleq, solv->nrules - 1); 02083 solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid; 02084 #if 0 02085 printf("OLD "); 02086 solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid); 02087 printf("WEAK CHOICE "); 02088 solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + solv->nrules - 1); 02089 #endif 02090 } 02091 queue_free(&q); 02092 queue_free(&qi); 02093 map_free(&m); 02094 map_free(&mneg); 02095 solv->choicerules_end = solv->nrules; 02096 } 02097 02098 /* called when a choice rule is disabled by analyze_unsolvable. We also 02099 * have to disable all other choice rules so that the best packages get 02100 * picked */ 02101 void 02102 solver_disablechoicerules(Solver *solv, Rule *r) 02103 { 02104 Id rid, p, *pp; 02105 Pool *pool = solv->pool; 02106 Map m; 02107 Rule *or; 02108 02109 or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules]; 02110 map_init(&m, pool->nsolvables); 02111 FOR_RULELITERALS(p, pp, or) 02112 if (p > 0) 02113 MAPSET(&m, p); 02114 FOR_RULELITERALS(p, pp, r) 02115 if (p > 0) 02116 MAPCLR(&m, p); 02117 for (rid = solv->choicerules; rid < solv->choicerules_end; rid++) 02118 { 02119 r = solv->rules + rid; 02120 if (r->d < 0) 02121 continue; 02122 or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules]; 02123 FOR_RULELITERALS(p, pp, or) 02124 if (p > 0 && MAPTST(&m, p)) 02125 break; 02126 if (p) 02127 solver_disablerule(solv, r); 02128 } 02129 } 02130 02131 static void solver_createcleandepsmap(Solver *solv) 02132 { 02133 Pool *pool = solv->pool; 02134 Repo *installed = solv->installed; 02135 Queue *job = &solv->job; 02136 Map userinstalled; 02137 Map im; 02138 Map installedm; 02139 Rule *r; 02140 Id rid, how, what, select; 02141 Id p, pp, ip, *jp; 02142 Id req, *reqp, sup, *supp; 02143 Solvable *s; 02144 Queue iq; 02145 int i; 02146 02147 map_init(&userinstalled, installed->end - installed->start); 02148 map_init(&im, pool->nsolvables); 02149 map_init(&installedm, pool->nsolvables); 02150 map_empty(&solv->cleandepsmap); 02151 queue_init(&iq); 02152 02153 for (i = 0; i < job->count; i += 2) 02154 { 02155 how = job->elements[i]; 02156 if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED) 02157 { 02158 what = job->elements[i + 1]; 02159 select = how & SOLVER_SELECTMASK; 02160 FOR_JOB_SELECT(p, pp, select, what) 02161 if (pool->solvables[p].repo == installed) 02162 MAPSET(&userinstalled, p - installed->start); 02163 } 02164 } 02165 /* add all positive elements (e.g. locks) to "userinstalled" */ 02166 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++) 02167 { 02168 r = solv->rules + rid; 02169 if (r->d < 0) 02170 continue; 02171 FOR_RULELITERALS(p, jp, r) 02172 if (p > 0 && pool->solvables[p].repo == installed) 02173 MAPSET(&userinstalled, p - installed->start); 02174 } 02175 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++) 02176 { 02177 r = solv->rules + rid; 02178 if (r->p >= 0 || r->d != 0) 02179 continue; /* disabled or not erase */ 02180 p = -r->p; 02181 if (pool->solvables[p].repo != installed) 02182 continue; 02183 MAPCLR(&userinstalled, p - installed->start); 02184 i = solv->ruletojob.elements[rid - solv->jobrules]; 02185 how = job->elements[i]; 02186 if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS)) 02187 queue_push(&iq, p); 02188 } 02189 for (p = installed->start; p < installed->end; p++) 02190 { 02191 if (pool->solvables[p].repo != installed) 02192 continue; 02193 MAPSET(&installedm, p); 02194 MAPSET(&im, p); 02195 } 02196 02197 while (iq.count) 02198 { 02199 ip = queue_shift(&iq); 02200 s = pool->solvables + ip; 02201 if (!MAPTST(&im, ip)) 02202 continue; 02203 if (!MAPTST(&installedm, ip)) 02204 continue; 02205 if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start)) 02206 continue; 02207 MAPCLR(&im, ip); 02208 #ifdef CLEANDEPSDEBUG 02209 printf("hello %s\n", solvable2str(pool, s)); 02210 #endif 02211 if (s->requires) 02212 { 02213 reqp = s->repo->idarraydata + s->requires; 02214 while ((req = *reqp++) != 0) 02215 { 02216 if (req == SOLVABLE_PREREQMARKER) 02217 continue; 02218 #if 0 02219 /* count number of installed packages that match */ 02220 count = 0; 02221 FOR_PROVIDES(p, pp, req) 02222 if (MAPTST(&installedm, p)) 02223 count++; 02224 if (count > 1) 02225 continue; 02226 #endif 02227 FOR_PROVIDES(p, pp, req) 02228 { 02229 if (MAPTST(&im, p)) 02230 { 02231 #ifdef CLEANDEPSDEBUG 02232 printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p)); 02233 #endif 02234 queue_push(&iq, p); 02235 } 02236 } 02237 } 02238 } 02239 if (s->recommends) 02240 { 02241 reqp = s->repo->idarraydata + s->recommends; 02242 while ((req = *reqp++) != 0) 02243 { 02244 #if 0 02245 count = 0; 02246 FOR_PROVIDES(p, pp, req) 02247 if (MAPTST(&installedm, p)) 02248 count++; 02249 if (count > 1) 02250 continue; 02251 #endif 02252 FOR_PROVIDES(p, pp, req) 02253 { 02254 if (MAPTST(&im, p)) 02255 { 02256 #ifdef CLEANDEPSDEBUG 02257 printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p)); 02258 #endif 02259 queue_push(&iq, p); 02260 } 02261 } 02262 } 02263 } 02264 if (!iq.count) 02265 { 02266 /* supplements pass */ 02267 for (ip = solv->installed->start; ip < solv->installed->end; ip++) 02268 { 02269 if (!MAPTST(&installedm, ip)) 02270 continue; 02271 s = pool->solvables + ip; 02272 if (!s->supplements) 02273 continue; 02274 if (!MAPTST(&im, ip)) 02275 continue; 02276 supp = s->repo->idarraydata + s->supplements; 02277 while ((sup = *supp++) != 0) 02278 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm)) 02279 break; 02280 /* no longer supplemented, also erase */ 02281 if (sup) 02282 { 02283 #ifdef CLEANDEPSDEBUG 02284 printf("%s supplemented\n", solvid2str(pool, ip)); 02285 #endif 02286 queue_push(&iq, ip); 02287 } 02288 } 02289 } 02290 } 02291 02292 /* turn userinstalled into remove set for pruning */ 02293 map_empty(&userinstalled); 02294 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++) 02295 { 02296 r = solv->rules + rid; 02297 if (r->p >= 0 || r->d != 0) 02298 continue; /* disabled or not erase */ 02299 p = -r->p; 02300 MAPCLR(&im, p); 02301 if (pool->solvables[p].repo == installed) 02302 MAPSET(&userinstalled, p - installed->start); 02303 } 02304 for (p = installed->start; p < installed->end; p++) 02305 if (MAPTST(&im, p)) 02306 queue_push(&iq, p); 02307 for (rid = solv->jobrules; rid < solv->jobrules_end; rid++) 02308 { 02309 r = solv->rules + rid; 02310 if (r->d < 0) 02311 continue; 02312 FOR_RULELITERALS(p, jp, r) 02313 if (p > 0) 02314 queue_push(&iq, p); 02315 } 02316 /* also put directly addressed packages on the install queue 02317 * so we can mark patterns as installed */ 02318 for (i = 0; i < job->count; i += 2) 02319 { 02320 how = job->elements[i]; 02321 if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED) 02322 { 02323 what = job->elements[i + 1]; 02324 select = how & SOLVER_SELECTMASK; 02325 if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed) 02326 queue_push(&iq, what); 02327 } 02328 } 02329 while (iq.count) 02330 { 02331 ip = queue_shift(&iq); 02332 s = pool->solvables + ip; 02333 #ifdef CLEANDEPSDEBUG 02334 printf("bye %s\n", solvable2str(pool, s)); 02335 #endif 02336 if (s->requires) 02337 { 02338 reqp = s->repo->idarraydata + s->requires; 02339 while ((req = *reqp++) != 0) 02340 { 02341 FOR_PROVIDES(p, pp, req) 02342 { 02343 if (!MAPTST(&im, p) && MAPTST(&installedm, p)) 02344 { 02345 if (p == ip) 02346 continue; 02347 if (MAPTST(&userinstalled, p - installed->start)) 02348 continue; 02349 #ifdef CLEANDEPSDEBUG 02350 printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p)); 02351 #endif 02352 MAPSET(&im, p); 02353 queue_push(&iq, p); 02354 } 02355 } 02356 } 02357 } 02358 if (s->recommends) 02359 { 02360 reqp = s->repo->idarraydata + s->recommends; 02361 while ((req = *reqp++) != 0) 02362 { 02363 FOR_PROVIDES(p, pp, req) 02364 { 02365 if (!MAPTST(&im, p) && MAPTST(&installedm, p)) 02366 { 02367 if (p == ip) 02368 continue; 02369 if (MAPTST(&userinstalled, p - installed->start)) 02370 continue; 02371 #ifdef CLEANDEPSDEBUG 02372 printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p)); 02373 #endif 02374 MAPSET(&im, p); 02375 queue_push(&iq, p); 02376 } 02377 } 02378 } 02379 } 02380 if (!iq.count) 02381 { 02382 /* supplements pass */ 02383 for (ip = installed->start; ip < installed->end; ip++) 02384 { 02385 if (!MAPTST(&installedm, ip)) 02386 continue; 02387 if (MAPTST(&userinstalled, ip - installed->start)) 02388 continue; 02389 s = pool->solvables + ip; 02390 if (!s->supplements) 02391 continue; 02392 if (MAPTST(&im, ip) || !MAPTST(&installedm, ip)) 02393 continue; 02394 supp = s->repo->idarraydata + s->supplements; 02395 while ((sup = *supp++) != 0) 02396 if (dep_possible(solv, sup, &im)) 02397 break; 02398 if (sup) 02399 { 02400 #ifdef CLEANDEPSDEBUG 02401 printf("%s supplemented\n", solvid2str(pool, ip)); 02402 #endif 02403 MAPSET(&im, ip); 02404 queue_push(&iq, ip); 02405 } 02406 } 02407 } 02408 } 02409 02410 queue_free(&iq); 02411 for (p = installed->start; p < installed->end; p++) 02412 { 02413 if (pool->solvables[p].repo != installed) 02414 continue; 02415 if (!MAPTST(&im, p)) 02416 MAPSET(&solv->cleandepsmap, p - installed->start); 02417 } 02418 map_free(&im); 02419 map_free(&installedm); 02420 map_free(&userinstalled); 02421 } 02422 02423 02424 /* EOF */