00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
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 "util.h"
00024 #include "policy.h"
00025 #include "solverdebug.h"
00026
00027 #define RULES_BLOCK 63
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044 int
00045 solver_splitprovides(Solver *solv, Id dep)
00046 {
00047 Pool *pool = solv->pool;
00048 Id p, pp;
00049 Reldep *rd;
00050 Solvable *s;
00051
00052 if (!solv->dosplitprovides || !solv->installed || (!solv->updatesystem && !solv->updatemap.size))
00053 return 0;
00054 if (!ISRELDEP(dep))
00055 return 0;
00056 rd = GETRELDEP(pool, dep);
00057 if (rd->flags != REL_WITH)
00058 return 0;
00059 FOR_PROVIDES(p, pp, dep)
00060 {
00061
00062
00063 s = pool->solvables + p;
00064 if (s->repo == solv->installed && s->name == rd->name &&
00065 (solv->updatesystem || (solv->updatemap.size && MAPTST(&solv->updatemap, p - solv->installed->start))))
00066 return 1;
00067 }
00068 return 0;
00069 }
00070
00071
00072
00073
00074
00075
00076 int
00077 solver_dep_installed(Solver *solv, Id dep)
00078 {
00079 #if 0
00080 Pool *pool = solv->pool;
00081 Id p, pp;
00082
00083 if (ISRELDEP(dep))
00084 {
00085 Reldep *rd = GETRELDEP(pool, dep);
00086 if (rd->flags == REL_AND)
00087 {
00088 if (!solver_dep_installed(solv, rd->name))
00089 return 0;
00090 return solver_dep_installed(solv, rd->evr);
00091 }
00092 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
00093 return solver_dep_installed(solv, rd->evr);
00094 }
00095 FOR_PROVIDES(p, pp, dep)
00096 {
00097 if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
00098 return 1;
00099 }
00100 #endif
00101 return 0;
00102 }
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115 static void
00116 makeruledecisions(Solver *solv)
00117 {
00118 Pool *pool = solv->pool;
00119 int i, ri, ii;
00120 Rule *r, *rr;
00121 Id v, vv;
00122 int decisionstart;
00123
00124 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
00125
00126
00127 assert(solv->decisionq.count == 0);
00128 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
00129 queue_push(&solv->decisionq_why, 0);
00130 solv->decisionmap[SYSTEMSOLVABLE] = 1;
00131
00132 decisionstart = solv->decisionq.count;
00133 for (ii = 0; ii < solv->ruleassertions.count; ii++)
00134 {
00135 ri = solv->ruleassertions.elements[ii];
00136 r = solv->rules + ri;
00137
00138 if (r->d < 0 || !r->p || r->w2)
00139 continue;
00140
00141 if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
00142 continue;
00143
00144 v = r->p;
00145 vv = v > 0 ? v : -v;
00146
00147 if (!solv->decisionmap[vv])
00148 {
00149
00150
00151
00152 queue_push(&solv->decisionq, v);
00153 queue_push(&solv->decisionq_why, r - solv->rules);
00154 solv->decisionmap[vv] = v > 0 ? 1 : -1;
00155 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
00156 {
00157 Solvable *s = solv->pool->solvables + vv;
00158 if (v < 0)
00159 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
00160 else
00161 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s));
00162 }
00163 continue;
00164 }
00165
00166
00167
00168
00169 if (v > 0 && solv->decisionmap[vv] > 0)
00170 continue;
00171 if (v < 0 && solv->decisionmap[vv] < 0)
00172 continue;
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182 if (ri >= solv->learntrules)
00183 {
00184
00185
00186
00187
00188 solver_disablerule(solv, r);
00189 continue;
00190 }
00191
00192
00193
00194
00195
00196 for (i = 0; i < solv->decisionq.count; i++)
00197 if (solv->decisionq.elements[i] == -v)
00198 break;
00199 assert(i < solv->decisionq.count);
00200
00201
00202
00203
00204
00205 if (v == -SYSTEMSOLVABLE) {
00206
00207 queue_push(&solv->problems, solv->learnt_pool.count);
00208 queue_push(&solv->learnt_pool, ri);
00209 queue_push(&solv->learnt_pool, 0);
00210 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
00211 if (ri >= solv->jobrules && ri < solv->jobrules_end)
00212 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
00213 else
00214 v = ri;
00215 queue_push(&solv->problems, v);
00216 queue_push(&solv->problems, 0);
00217 solver_disableproblem(solv, v);
00218 continue;
00219 }
00220
00221 assert(solv->decisionq_why.elements[i] > 0);
00222
00223
00224
00225
00226
00227 if (solv->decisionq_why.elements[i] < solv->rpmrules_end)
00228 {
00229
00230 queue_push(&solv->problems, solv->learnt_pool.count);
00231 queue_push(&solv->learnt_pool, ri);
00232 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
00233 queue_push(&solv->learnt_pool, 0);
00234 assert(v > 0 || v == -SYSTEMSOLVABLE);
00235 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
00236 if (ri >= solv->jobrules && ri < solv->jobrules_end)
00237 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
00238 else
00239 v = ri;
00240 queue_push(&solv->problems, v);
00241 queue_push(&solv->problems, 0);
00242 solver_disableproblem(solv, v);
00243 continue;
00244 }
00245
00246
00247
00248
00249
00250
00251 queue_push(&solv->problems, solv->learnt_pool.count);
00252 queue_push(&solv->learnt_pool, ri);
00253 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
00254 queue_push(&solv->learnt_pool, 0);
00255
00256 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
00257
00258
00259
00260
00261
00262
00263 for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
00264 {
00265 if (rr->d < 0
00266 || rr->w2)
00267 continue;
00268 if (rr->p != vv
00269 && rr->p != -vv)
00270 continue;
00271 if (MAPTST(&solv->weakrulemap, i))
00272 continue;
00273
00274 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
00275
00276 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + i);
00277
00278 v = i;
00279
00280 if (i >= solv->jobrules && i < solv->jobrules_end)
00281 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
00282
00283 queue_push(&solv->problems, v);
00284 solver_disableproblem(solv, v);
00285 }
00286 queue_push(&solv->problems, 0);
00287
00288
00289
00290
00291
00292 while (solv->decisionq.count > decisionstart)
00293 {
00294 v = solv->decisionq.elements[--solv->decisionq.count];
00295 --solv->decisionq_why.count;
00296 vv = v > 0 ? v : -v;
00297 solv->decisionmap[vv] = 0;
00298 }
00299 ii = -1;
00300 }
00301
00302
00303
00304
00305 for (ii = 0; ii < solv->ruleassertions.count; ii++)
00306 {
00307 ri = solv->ruleassertions.elements[ii];
00308 r = solv->rules + ri;
00309 if (r->d < 0 || r->w2)
00310 continue;
00311 if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri))
00312 continue;
00313 v = r->p;
00314 vv = v > 0 ? v : -v;
00315
00316
00317
00318
00319 if (!solv->decisionmap[vv])
00320 {
00321 queue_push(&solv->decisionq, v);
00322 queue_push(&solv->decisionq_why, r - solv->rules);
00323 solv->decisionmap[vv] = v > 0 ? 1 : -1;
00324 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
00325 {
00326 Solvable *s = solv->pool->solvables + vv;
00327 if (v < 0)
00328 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", solvable2str(solv->pool, s));
00329 else
00330 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", solvable2str(solv->pool, s));
00331 }
00332 continue;
00333 }
00334
00335
00336
00337 if (v > 0 && solv->decisionmap[vv] > 0)
00338 continue;
00339 if (v < 0 && solv->decisionmap[vv] < 0)
00340 continue;
00341
00342 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
00343 solver_printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
00344
00345 if (ri >= solv->jobrules && ri < solv->jobrules_end)
00346 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
00347 else
00348 v = ri;
00349 solver_disableproblem(solv, v);
00350 if (v < 0)
00351 solver_reenablepolicyrules(solv, -(v + 1));
00352 }
00353
00354 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
00355 }
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365 static void
00366 enabledisablelearntrules(Solver *solv)
00367 {
00368 Pool *pool = solv->pool;
00369 Rule *r;
00370 Id why, *whyp;
00371 int i;
00372
00373 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
00374 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
00375 {
00376 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
00377 while ((why = *whyp++) != 0)
00378 {
00379 assert(why > 0 && why < i);
00380 if (solv->rules[why].d < 0)
00381 break;
00382 }
00383
00384 if (why && r->d >= 0)
00385 {
00386 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
00387 {
00388 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling ");
00389 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
00390 }
00391 solver_disablerule(solv, r);
00392 }
00393 else if (!why && r->d < 0)
00394 {
00395 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
00396 {
00397 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling ");
00398 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
00399 }
00400 solver_enablerule(solv, r);
00401 }
00402 }
00403 }
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416 static void
00417 makewatches(Solver *solv)
00418 {
00419 Rule *r;
00420 int i;
00421 int nsolvables = solv->pool->nsolvables;
00422
00423 sat_free(solv->watches);
00424
00425 solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
00426 #if 1
00427
00428 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
00429 #else
00430 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
00431 #endif
00432 {
00433 if (!r->w2)
00434 continue;
00435
00436
00437 r->n1 = solv->watches[nsolvables + r->w1];
00438 solv->watches[nsolvables + r->w1] = r - solv->rules;
00439
00440 r->n2 = solv->watches[nsolvables + r->w2];
00441 solv->watches[nsolvables + r->w2] = r - solv->rules;
00442 }
00443 }
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
00454 static inline void
00455 addwatches_rule(Solver *solv, Rule *r)
00456 {
00457 int nsolvables = solv->pool->nsolvables;
00458
00459 r->n1 = solv->watches[nsolvables + r->w1];
00460 solv->watches[nsolvables + r->w1] = r - solv->rules;
00461
00462 r->n2 = solv->watches[nsolvables + r->w2];
00463 solv->watches[nsolvables + r->w2] = r - solv->rules;
00464 }
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
00477 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
00478 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495
00496 static Rule *
00497 propagate(Solver *solv, int level)
00498 {
00499 Pool *pool = solv->pool;
00500 Id *rp, *next_rp;
00501 Rule *r;
00502 Id p, pkg, other_watch;
00503 Id *dp;
00504 Id *decisionmap = solv->decisionmap;
00505
00506 Id *watches = solv->watches + pool->nsolvables;
00507
00508 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
00509
00510
00511 while (solv->propagate_index < solv->decisionq.count)
00512 {
00513
00514
00515
00516
00517 pkg = -solv->decisionq.elements[solv->propagate_index++];
00518
00519 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
00520 {
00521 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
00522 solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
00523 }
00524
00525
00526 for (rp = watches + pkg; *rp; rp = next_rp)
00527 {
00528 r = solv->rules + *rp;
00529 if (r->d < 0)
00530 {
00531
00532 if (pkg == r->w1)
00533 next_rp = &r->n1;
00534 else
00535 next_rp = &r->n2;
00536 continue;
00537 }
00538
00539 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
00540 {
00541 POOL_DEBUG(SAT_DEBUG_PROPAGATE," watch triggered ");
00542 solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
00543 }
00544
00545
00546
00547
00548
00549
00550 if (pkg == r->w1)
00551 {
00552 other_watch = r->w2;
00553 next_rp = &r->n1;
00554 }
00555 else
00556 {
00557 other_watch = r->w1;
00558 next_rp = &r->n2;
00559 }
00560
00561
00562
00563
00564
00565 if (DECISIONMAP_TRUE(other_watch))
00566 continue;
00567
00568
00569
00570
00571
00572
00573 if (r->d)
00574 {
00575
00576
00577
00578
00579
00580
00581
00582
00583 if (r->p
00584 && r->p != other_watch
00585 && !DECISIONMAP_FALSE(r->p))
00586 {
00587 p = r->p;
00588 }
00589 else
00590 {
00591
00592
00593
00594 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
00595 {
00596 if (p != other_watch
00597 && !DECISIONMAP_FALSE(p))
00598 break;
00599 }
00600 }
00601
00602 if (p)
00603 {
00604
00605
00606
00607
00608 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
00609 {
00610 if (p > 0)
00611 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvid2str(pool, p));
00612 else
00613 POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvid2str(pool, -p));
00614 }
00615
00616 *rp = *next_rp;
00617 next_rp = rp;
00618
00619 if (pkg == r->w1)
00620 {
00621 r->w1 = p;
00622 r->n1 = watches[p];
00623 }
00624 else
00625 {
00626 r->w2 = p;
00627 r->n2 = watches[p];
00628 }
00629 watches[p] = r - solv->rules;
00630 continue;
00631 }
00632
00633
00634 }
00635
00636
00637
00638
00639
00640 if (DECISIONMAP_FALSE(other_watch))
00641 return r;
00642
00643 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
00644 {
00645 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " unit ");
00646 solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
00647 }
00648
00649 if (other_watch > 0)
00650 decisionmap[other_watch] = level;
00651 else
00652 decisionmap[-other_watch] = -level;
00653
00654 queue_push(&solv->decisionq, other_watch);
00655 queue_push(&solv->decisionq_why, r - solv->rules);
00656
00657 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
00658 {
00659 if (other_watch > 0)
00660 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvid2str(pool, other_watch));
00661 else
00662 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvid2str(pool, -other_watch));
00663 }
00664
00665 }
00666
00667 }
00668
00669 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
00670
00671 return 0;
00672 }
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684 static int
00685 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
00686 {
00687 Pool *pool = solv->pool;
00688 Queue r;
00689 int rlevel = 1;
00690 Map seen;
00691 Id d, v, vv, *dp, why;
00692 int l, i, idx;
00693 int num = 0, l1num = 0;
00694 int learnt_why = solv->learnt_pool.count;
00695 Id *decisionmap = solv->decisionmap;
00696
00697 queue_init(&r);
00698
00699 POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
00700 map_init(&seen, pool->nsolvables);
00701 idx = solv->decisionq.count;
00702 for (;;)
00703 {
00704 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
00705 solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c);
00706 queue_push(&solv->learnt_pool, c - solv->rules);
00707 d = c->d < 0 ? -c->d - 1 : c->d;
00708 dp = d ? pool->whatprovidesdata + d : 0;
00709
00710 for (i = -1; ; i++)
00711 {
00712 if (i == -1)
00713 v = c->p;
00714 else if (d == 0)
00715 v = i ? 0 : c->w2;
00716 else
00717 v = *dp++;
00718 if (v == 0)
00719 break;
00720
00721 if (DECISIONMAP_TRUE(v))
00722 continue;
00723 vv = v > 0 ? v : -v;
00724 if (MAPTST(&seen, vv))
00725 continue;
00726 l = solv->decisionmap[vv];
00727 if (l < 0)
00728 l = -l;
00729 MAPSET(&seen, vv);
00730 if (l == 1)
00731 l1num++;
00732 else if (l == level)
00733 num++;
00734 else
00735 {
00736 queue_push(&r, v);
00737 if (l > rlevel)
00738 rlevel = l;
00739 }
00740 }
00741 l1retry:
00742 if (!num && !--l1num)
00743 break;
00744 for (;;)
00745 {
00746 assert(idx > 0);
00747 v = solv->decisionq.elements[--idx];
00748 vv = v > 0 ? v : -v;
00749 if (MAPTST(&seen, vv))
00750 break;
00751 }
00752 MAPCLR(&seen, vv);
00753 if (num && --num == 0)
00754 {
00755 *pr = -v;
00756 if (!l1num)
00757 break;
00758 POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
00759 for (i = 0; i < r.count; i++)
00760 {
00761 v = r.elements[i];
00762 MAPCLR(&seen, v > 0 ? v : -v);
00763 }
00764
00765 l1num++;
00766 goto l1retry;
00767 }
00768 why = solv->decisionq_why.elements[idx];
00769 if (why <= 0)
00770 goto l1retry;
00771 c = solv->rules + why;
00772 }
00773 map_free(&seen);
00774
00775 if (r.count == 0)
00776 *dr = 0;
00777 else if (r.count == 1 && r.elements[0] < 0)
00778 *dr = r.elements[0];
00779 else
00780 *dr = pool_queuetowhatprovides(pool, &r);
00781 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
00782 {
00783 POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
00784 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
00785 for (i = 0; i < r.count; i++)
00786 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
00787 }
00788
00789 queue_push(&solv->learnt_pool, 0);
00790 if (whyp)
00791 *whyp = learnt_why;
00792 solv->stats_learned++;
00793 return rlevel;
00794 }
00795
00796
00797
00798
00799
00800
00801
00802
00803
00804
00805 void
00806 solver_reset(Solver *solv)
00807 {
00808 Pool *pool = solv->pool;
00809 int i;
00810 Id v;
00811
00812
00813 for (i = solv->decisionq.count - 1; i >= 0; i--)
00814 {
00815 v = solv->decisionq.elements[i];
00816 solv->decisionmap[v > 0 ? v : -v] = 0;
00817 }
00818 solv->decisionq_why.count = 0;
00819 solv->decisionq.count = 0;
00820 solv->recommends_index = -1;
00821 solv->propagate_index = 0;
00822 solv->recommendations.count = 0;
00823 solv->branches.count = 0;
00824
00825
00826 enabledisablelearntrules(solv);
00827
00828
00829 makeruledecisions(solv);
00830 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
00831 }
00832
00833
00834
00835
00836
00837
00838
00839 static void
00840 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp)
00841 {
00842 Pool *pool = solv->pool;
00843 int i;
00844 Id why = r - solv->rules;
00845
00846 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
00847 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
00848 if (solv->learntrules && why >= solv->learntrules)
00849 {
00850 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
00851 if (solv->learnt_pool.elements[i] > 0)
00852 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp);
00853 return;
00854 }
00855 if (MAPTST(&solv->weakrulemap, why))
00856 if (!*lastweakp || why > *lastweakp)
00857 *lastweakp = why;
00858
00859 if (why < solv->rpmrules_end)
00860 return;
00861
00862 if (why >= solv->jobrules && why < solv->jobrules_end)
00863 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
00864
00865 if (why > solv->infarchrules && why < solv->infarchrules_end)
00866 {
00867 Id name = pool->solvables[-solv->rules[why].p].name;
00868 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
00869 why--;
00870 }
00871 if (why > solv->duprules && why < solv->duprules_end)
00872 {
00873 Id name = pool->solvables[-solv->rules[why].p].name;
00874 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
00875 why--;
00876 }
00877
00878
00879 if (solv->problems.count)
00880 {
00881 for (i = solv->problems.count - 1; i >= 0; i--)
00882 if (solv->problems.elements[i] == 0)
00883 break;
00884 else if (solv->problems.elements[i] == why)
00885 return;
00886 }
00887 queue_push(&solv->problems, why);
00888 }
00889
00890
00891
00892
00893
00894
00895
00896
00897
00898
00899 static int
00900 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
00901 {
00902 Pool *pool = solv->pool;
00903 Rule *r;
00904 Map seen;
00905 Id d, v, vv, *dp, why;
00906 int l, i, idx;
00907 Id *decisionmap = solv->decisionmap;
00908 int oldproblemcount;
00909 int oldlearntpoolcount;
00910 Id lastweak;
00911
00912 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
00913 solv->stats_unsolvable++;
00914 oldproblemcount = solv->problems.count;
00915 oldlearntpoolcount = solv->learnt_pool.count;
00916
00917
00918
00919
00920 queue_push(&solv->problems, 0);
00921
00922 r = cr;
00923 map_init(&seen, pool->nsolvables);
00924 queue_push(&solv->learnt_pool, r - solv->rules);
00925 lastweak = 0;
00926 analyze_unsolvable_rule(solv, r, &lastweak);
00927 d = r->d < 0 ? -r->d - 1 : r->d;
00928 dp = d ? pool->whatprovidesdata + d : 0;
00929 for (i = -1; ; i++)
00930 {
00931 if (i == -1)
00932 v = r->p;
00933 else if (d == 0)
00934 v = i ? 0 : r->w2;
00935 else
00936 v = *dp++;
00937 if (v == 0)
00938 break;
00939 if (DECISIONMAP_TRUE(v))
00940 continue;
00941 vv = v > 0 ? v : -v;
00942 l = solv->decisionmap[vv];
00943 if (l < 0)
00944 l = -l;
00945 MAPSET(&seen, vv);
00946 }
00947 idx = solv->decisionq.count;
00948 while (idx > 0)
00949 {
00950 v = solv->decisionq.elements[--idx];
00951 vv = v > 0 ? v : -v;
00952 if (!MAPTST(&seen, vv))
00953 continue;
00954 why = solv->decisionq_why.elements[idx];
00955 assert(why > 0);
00956 queue_push(&solv->learnt_pool, why);
00957 r = solv->rules + why;
00958 analyze_unsolvable_rule(solv, r, &lastweak);
00959 d = r->d < 0 ? -r->d - 1 : r->d;
00960 dp = d ? pool->whatprovidesdata + d : 0;
00961 for (i = -1; ; i++)
00962 {
00963 if (i == -1)
00964 v = r->p;
00965 else if (d == 0)
00966 v = i ? 0 : r->w2;
00967 else
00968 v = *dp++;
00969 if (v == 0)
00970 break;
00971 if (DECISIONMAP_TRUE(v))
00972 continue;
00973 vv = v > 0 ? v : -v;
00974 l = solv->decisionmap[vv];
00975 if (l < 0)
00976 l = -l;
00977 MAPSET(&seen, vv);
00978 }
00979 }
00980 map_free(&seen);
00981 queue_push(&solv->problems, 0);
00982
00983 if (lastweak)
00984 {
00985 Id v;
00986 extern void disablechoicerules(Solver *solv, Rule *r);
00987
00988 solv->problems.count = oldproblemcount;
00989 solv->learnt_pool.count = oldlearntpoolcount;
00990 if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
00991 v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
00992 else
00993 v = lastweak;
00994 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling ");
00995 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + lastweak);
00996 if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
00997 disablechoicerules(solv, solv->rules + lastweak);
00998 solver_disableproblem(solv, v);
00999 if (v < 0)
01000 solver_reenablepolicyrules(solv, -(v + 1));
01001 solver_reset(solv);
01002 return 1;
01003 }
01004
01005
01006 queue_push(&solv->learnt_pool, 0);
01007 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
01008
01009 if (disablerules)
01010 {
01011 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
01012 solver_disableproblem(solv, solv->problems.elements[i]);
01013
01014 solver_reset(solv);
01015 return 1;
01016 }
01017 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
01018 return 0;
01019 }
01020
01021
01022
01023
01024
01025
01026
01027
01028
01029
01030
01031 static void
01032 revert(Solver *solv, int level)
01033 {
01034 Pool *pool = solv->pool;
01035 Id v, vv;
01036 while (solv->decisionq.count)
01037 {
01038 v = solv->decisionq.elements[solv->decisionq.count - 1];
01039 vv = v > 0 ? v : -v;
01040 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
01041 break;
01042 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
01043 if (v > 0 && solv->recommendations.count && v == solv->recommendations.elements[solv->recommendations.count - 1])
01044 solv->recommendations.count--;
01045 solv->decisionmap[vv] = 0;
01046 solv->decisionq.count--;
01047 solv->decisionq_why.count--;
01048 solv->propagate_index = solv->decisionq.count;
01049 }
01050 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
01051 {
01052 solv->branches.count--;
01053 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
01054 solv->branches.count--;
01055 }
01056 solv->recommends_index = -1;
01057 }
01058
01059
01060
01061
01062
01063
01064
01065 static inline void
01066 watch2onhighest(Solver *solv, Rule *r)
01067 {
01068 int l, wl = 0;
01069 Id d, v, *dp;
01070
01071 d = r->d < 0 ? -r->d - 1 : r->d;
01072 if (!d)
01073 return;
01074 dp = solv->pool->whatprovidesdata + d;
01075 while ((v = *dp++) != 0)
01076 {
01077 l = solv->decisionmap[v < 0 ? -v : v];
01078 if (l < 0)
01079 l = -l;
01080 if (l > wl)
01081 {
01082 r->w2 = dp[-1];
01083 wl = l;
01084 }
01085 }
01086 }
01087
01088
01089
01090
01091
01092
01093
01094
01095
01096
01097
01098
01099
01100
01101
01102
01103
01104
01105 static int
01106 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
01107 {
01108 Pool *pool = solv->pool;
01109 Rule *r;
01110 Id p = 0, d = 0;
01111 int l, why;
01112
01113 assert(ruleid >= 0);
01114 if (decision)
01115 {
01116 level++;
01117 if (decision > 0)
01118 solv->decisionmap[decision] = level;
01119 else
01120 solv->decisionmap[-decision] = -level;
01121 queue_push(&solv->decisionq, decision);
01122 queue_push(&solv->decisionq_why, -ruleid);
01123 }
01124 for (;;)
01125 {
01126 r = propagate(solv, level);
01127 if (!r)
01128 break;
01129 if (level == 1)
01130 return analyze_unsolvable(solv, r, disablerules);
01131 POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
01132 l = analyze(solv, level, r, &p, &d, &why);
01133 assert(l > 0 && l < level);
01134 POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
01135 level = l;
01136 revert(solv, level);
01137 r = solver_addrule(solv, p, d);
01138 assert(r);
01139 assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
01140 queue_push(&solv->learnt_why, why);
01141 if (d)
01142 {
01143
01144 watch2onhighest(solv, r);
01145 addwatches_rule(solv, r);
01146 }
01147 else
01148 {
01149
01150 queue_push(&solv->ruleassertions, r - solv->rules);
01151 }
01152
01153 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
01154 queue_push(&solv->decisionq, p);
01155 queue_push(&solv->decisionq_why, r - solv->rules);
01156 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
01157 {
01158 POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
01159 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
01160 POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
01161 solver_printrule(solv, SAT_DEBUG_ANALYZE, r);
01162 }
01163 }
01164 return level;
01165 }
01166
01167
01168
01169
01170
01171
01172
01173
01174
01175
01176
01177
01178
01179 static int
01180 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
01181 {
01182 Pool *pool = solv->pool;
01183 Id p;
01184 int i;
01185
01186 if (dq->count > 1)
01187 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
01188 if (dq->count > 1)
01189 {
01190
01191
01192
01193
01194 for (i = 0; i < dq->count; i++)
01195 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
01196 {
01197 dq->elements[0] = dq->elements[i];
01198 dq->count = 1;
01199 break;
01200 }
01201 }
01202 if (dq->count > 1)
01203 {
01204
01205 for (i = 1; i < dq->count; i++)
01206 queue_push(&solv->branches, dq->elements[i]);
01207 queue_push(&solv->branches, -level);
01208 }
01209 p = dq->elements[0];
01210
01211 POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvid2str(pool, p));
01212
01213 return setpropagatelearn(solv, level, p, disablerules, ruleid);
01214 }
01215
01216
01217
01218
01219
01220
01221
01222
01223
01224
01225
01226
01227
01228
01229
01230
01231
01232
01233
01234 Solver *
01235 solver_create(Pool *pool)
01236 {
01237 Solver *solv;
01238 solv = (Solver *)sat_calloc(1, sizeof(Solver));
01239 solv->pool = pool;
01240 solv->installed = pool->installed;
01241
01242 transaction_init(&solv->trans, pool);
01243 queue_init(&solv->ruletojob);
01244 queue_init(&solv->decisionq);
01245 queue_init(&solv->decisionq_why);
01246 queue_init(&solv->problems);
01247 queue_init(&solv->suggestions);
01248 queue_init(&solv->recommendations);
01249 queue_init(&solv->orphaned);
01250 queue_init(&solv->learnt_why);
01251 queue_init(&solv->learnt_pool);
01252 queue_init(&solv->branches);
01253 queue_init(&solv->covenantq);
01254 queue_init(&solv->weakruleq);
01255 queue_init(&solv->ruleassertions);
01256
01257 map_init(&solv->recommendsmap, pool->nsolvables);
01258 map_init(&solv->suggestsmap, pool->nsolvables);
01259 map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
01260 solv->recommends_index = 0;
01261
01262 solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
01263 solv->nrules = 1;
01264 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
01265 memset(solv->rules, 0, sizeof(Rule));
01266
01267 return solv;
01268 }
01269
01270
01271
01272
01273
01274
01275
01276 void
01277 solver_free(Solver *solv)
01278 {
01279 transaction_free(&solv->trans);
01280 queue_free(&solv->job);
01281 queue_free(&solv->ruletojob);
01282 queue_free(&solv->decisionq);
01283 queue_free(&solv->decisionq_why);
01284 queue_free(&solv->learnt_why);
01285 queue_free(&solv->learnt_pool);
01286 queue_free(&solv->problems);
01287 queue_free(&solv->solutions);
01288 queue_free(&solv->suggestions);
01289 queue_free(&solv->recommendations);
01290 queue_free(&solv->orphaned);
01291 queue_free(&solv->branches);
01292 queue_free(&solv->covenantq);
01293 queue_free(&solv->weakruleq);
01294 queue_free(&solv->ruleassertions);
01295
01296 map_free(&solv->recommendsmap);
01297 map_free(&solv->suggestsmap);
01298 map_free(&solv->noupdate);
01299 map_free(&solv->weakrulemap);
01300 map_free(&solv->noobsoletes);
01301
01302 map_free(&solv->updatemap);
01303 map_free(&solv->fixmap);
01304 map_free(&solv->dupmap);
01305 map_free(&solv->dupinvolvedmap);
01306 map_free(&solv->droporphanedmap);
01307
01308 sat_free(solv->decisionmap);
01309 sat_free(solv->rules);
01310 sat_free(solv->watches);
01311 sat_free(solv->obsoletes);
01312 sat_free(solv->obsoletes_data);
01313 sat_free(solv->multiversionupdaters);
01314 sat_free(solv->choicerules_ref);
01315 sat_free(solv);
01316 }
01317
01318
01319
01320
01321
01322
01323
01324
01325
01326
01327 void
01328 solver_run_sat(Solver *solv, int disablerules, int doweak)
01329 {
01330 Queue dq;
01331 Queue dqs;
01332 int systemlevel;
01333 int level, olevel;
01334 Rule *r;
01335 int i, j, n;
01336 Solvable *s;
01337 Pool *pool = solv->pool;
01338 Id p, *dp;
01339 int minimizationsteps;
01340 int installedpos = solv->installed ? solv->installed->start : 0;
01341
01342 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
01343 {
01344 POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
01345 for (i = 1; i < solv->nrules; i++)
01346 solver_printruleclass(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
01347 }
01348
01349 POOL_DEBUG(SAT_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count);
01350
01351 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
01352 solver_printdecisions(solv);
01353
01354
01355 level = 1;
01356 systemlevel = level + 1;
01357 POOL_DEBUG(SAT_DEBUG_SOLVER, "solving...\n");
01358
01359 queue_init(&dq);
01360 queue_init(&dqs);
01361
01362
01363
01364
01365
01366
01367
01368
01369
01370
01371
01372
01373
01374 minimizationsteps = 0;
01375 for (;;)
01376 {
01377
01378
01379
01380 if (level == 1)
01381 {
01382 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
01383 if ((r = propagate(solv, level)) != 0)
01384 {
01385 if (analyze_unsolvable(solv, r, disablerules))
01386 continue;
01387 queue_free(&dq);
01388 queue_free(&dqs);
01389 return;
01390 }
01391 }
01392
01393
01394
01395
01396 if (level < systemlevel)
01397 {
01398 POOL_DEBUG(SAT_DEBUG_SOLVER, "resolving job rules\n");
01399 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
01400 {
01401 Id l;
01402 if (r->d < 0)
01403 continue;
01404 queue_empty(&dq);
01405 FOR_RULELITERALS(l, dp, r)
01406 {
01407 if (l < 0)
01408 {
01409 if (solv->decisionmap[-l] <= 0)
01410 break;
01411 }
01412 else
01413 {
01414 if (solv->decisionmap[l] > 0)
01415 break;
01416 if (solv->decisionmap[l] == 0)
01417 queue_push(&dq, l);
01418 }
01419 }
01420 if (l || !dq.count)
01421 continue;
01422
01423 if (!solv->updatesystem && solv->installed && dq.count > 1)
01424 {
01425 int j, k;
01426 for (j = k = 0; j < dq.count; j++)
01427 {
01428 Solvable *s = pool->solvables + dq.elements[j];
01429 if (s->repo == solv->installed)
01430 dq.elements[k++] = dq.elements[j];
01431 }
01432 if (k)
01433 dq.count = k;
01434 }
01435 olevel = level;
01436 level = selectandinstall(solv, level, &dq, disablerules, i);
01437 if (level == 0)
01438 {
01439 queue_free(&dq);
01440 queue_free(&dqs);
01441 return;
01442 }
01443 if (level <= olevel)
01444 break;
01445 }
01446 systemlevel = level + 1;
01447 if (i < solv->jobrules_end)
01448 continue;
01449 }
01450
01451
01452
01453
01454
01455 if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
01456 {
01457 Repo *installed = solv->installed;
01458 int pass;
01459
01460 POOL_DEBUG(SAT_DEBUG_SOLVER, "resolving installed packages\n");
01461
01462
01463 for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
01464 {
01465 int passlevel = level;
01466
01467 for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
01468 {
01469 Rule *rr;
01470 Id d;
01471
01472 if (i == installed->end)
01473 i = installed->start;
01474 s = pool->solvables + i;
01475 if (s->repo != installed)
01476 continue;
01477
01478 if (solv->decisionmap[i] > 0)
01479 continue;
01480
01481
01482 if (MAPTST(&solv->noupdate, i - installed->start))
01483 continue;
01484 if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
01485 continue;
01486 r = solv->rules + solv->updaterules + (i - installed->start);
01487 rr = r;
01488 if (!rr->p || rr->d < 0)
01489 rr -= solv->installed->end - solv->installed->start;
01490 if (!rr->p)
01491 rr = r;
01492 if (!rr->p)
01493 continue;
01494
01495 queue_empty(&dq);
01496 if (solv->decisionmap[i] < 0 || solv->updatesystem || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || rr->p != i)
01497 {
01498 if (solv->noobsoletes.size && solv->multiversionupdaters
01499 && (d = solv->multiversionupdaters[i - installed->start]) != 0)
01500 {
01501
01502 queue_push(&dq, i);
01503 while ((p = pool->whatprovidesdata[d++]) != 0)
01504 if (solv->decisionmap[p] >= 0)
01505 queue_push(&dq, p);
01506 policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
01507 p = dq.elements[0];
01508 if (p != i && solv->decisionmap[p] == 0)
01509 {
01510 rr = solv->rules + solv->featurerules + (i - solv->installed->start);
01511 if (!rr->p)
01512 rr = rr - solv->featurerules + solv->updaterules;
01513 dq.count = 1;
01514 }
01515 else
01516 dq.count = 0;
01517 }
01518 else
01519 {
01520
01521 FOR_RULELITERALS(p, dp, rr)
01522 {
01523 if (solv->decisionmap[p] > 0)
01524 {
01525 dq.count = 0;
01526 break;
01527 }
01528 if (!solv->decisionmap[p])
01529 queue_push(&dq, p);
01530 }
01531 }
01532 }
01533
01534 if (dq.count)
01535 {
01536 olevel = level;
01537 level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
01538 if (level == 0)
01539 {
01540 queue_free(&dq);
01541 queue_free(&dqs);
01542 return;
01543 }
01544 if (level <= olevel)
01545 {
01546 if (level == 1 || level < passlevel)
01547 break;
01548 if (level < olevel)
01549 n = installed->start;
01550 i--;
01551 n--;
01552 continue;
01553 }
01554 }
01555
01556 if (solv->decisionmap[i] == 0)
01557 {
01558 olevel = level;
01559 POOL_DEBUG(SAT_DEBUG_POLICY, "keeping %s\n", solvid2str(pool, i));
01560 level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
01561 if (level == 0)
01562 {
01563 queue_free(&dq);
01564 queue_free(&dqs);
01565 return;
01566 }
01567 if (level <= olevel)
01568 {
01569 if (level == 1 || level < passlevel)
01570 break;
01571 if (level < olevel)
01572 n = installed->start;
01573 i--;
01574 n--;
01575 continue;
01576 }
01577 }
01578 }
01579 if (n < installed->end)
01580 {
01581 installedpos = i;
01582 break;
01583 }
01584 installedpos = installed->start;
01585 }
01586 systemlevel = level + 1;
01587 if (pass < 2)
01588 continue;
01589 }
01590
01591 if (level < systemlevel)
01592 systemlevel = level;
01593
01594
01595
01596
01597 POOL_DEBUG(SAT_DEBUG_POLICY, "deciding unresolved rules\n");
01598 for (i = 1, n = 1; n < solv->nrules; i++, n++)
01599 {
01600 if (i == solv->nrules)
01601 i = 1;
01602 r = solv->rules + i;
01603 if (r->d < 0)
01604 continue;
01605 queue_empty(&dq);
01606 if (r->d == 0)
01607 {
01608
01609
01610 if (r->p < 0 || r->w2 <= 0)
01611 continue;
01612 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
01613 continue;
01614 queue_push(&dq, r->p);
01615 queue_push(&dq, r->w2);
01616 }
01617 else
01618 {
01619
01620
01621
01622
01623
01624
01625 if (r->p < 0)
01626 {
01627 if (solv->decisionmap[-r->p] <= 0)
01628 continue;
01629 }
01630 else
01631 {
01632 if (solv->decisionmap[r->p] > 0)
01633 continue;
01634 if (solv->decisionmap[r->p] == 0)
01635 queue_push(&dq, r->p);
01636 }
01637 dp = pool->whatprovidesdata + r->d;
01638 while ((p = *dp++) != 0)
01639 {
01640 if (p < 0)
01641 {
01642 if (solv->decisionmap[-p] <= 0)
01643 break;
01644 }
01645 else
01646 {
01647 if (solv->decisionmap[p] > 0)
01648 break;
01649 if (solv->decisionmap[p] == 0)
01650 queue_push(&dq, p);
01651 }
01652 }
01653 if (p)
01654 continue;
01655 }
01656 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
01657 {
01658 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
01659 solver_printruleclass(solv, SAT_DEBUG_PROPAGATE, r);
01660 }
01661
01662
01663 assert(dq.count > 1);
01664
01665 olevel = level;
01666 level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
01667 if (level == 0)
01668 {
01669 queue_free(&dq);
01670 queue_free(&dqs);
01671 return;
01672 }
01673 if (level < systemlevel || level == 1)
01674 break;
01675
01676 n = 0;
01677 }
01678
01679 if (n != solv->nrules)
01680 continue;
01681
01682
01683
01684 if (doweak)
01685 {
01686 int qcount;
01687
01688 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended packages\n");
01689 queue_empty(&dq);
01690 queue_empty(&dqs);
01691 for (i = 1; i < pool->nsolvables; i++)
01692 {
01693 if (solv->decisionmap[i] < 0)
01694 continue;
01695 if (solv->decisionmap[i] > 0)
01696 {
01697
01698 Id *recp, rec, pp, p;
01699 s = pool->solvables + i;
01700 if (solv->ignorealreadyrecommended && s->repo == solv->installed)
01701 continue;
01702
01703 if (s->recommends)
01704 {
01705 recp = s->repo->idarraydata + s->recommends;
01706 while ((rec = *recp++) != 0)
01707 {
01708 qcount = dq.count;
01709 FOR_PROVIDES(p, pp, rec)
01710 {
01711 if (solv->decisionmap[p] > 0)
01712 {
01713 dq.count = qcount;
01714 break;
01715 }
01716 else if (solv->decisionmap[p] == 0)
01717 {
01718 queue_pushunique(&dq, p);
01719 }
01720 }
01721 }
01722 }
01723 }
01724 else
01725 {
01726 s = pool->solvables + i;
01727 if (!s->supplements)
01728 continue;
01729 if (!pool_installable(pool, s))
01730 continue;
01731 if (!solver_is_supplementing(solv, s))
01732 continue;
01733 queue_push(&dqs, i);
01734 }
01735 }
01736
01737
01738
01739 if ((dqs.count || dq.count) && solv->installed)
01740 {
01741 Map obsmap;
01742 Id obs, *obsp, po, ppo;
01743
01744 map_init(&obsmap, pool->nsolvables);
01745 for (p = solv->installed->start; p < solv->installed->end; p++)
01746 {
01747 s = pool->solvables + p;
01748 if (s->repo != solv->installed || !s->obsoletes)
01749 continue;
01750 if (solv->decisionmap[p] <= 0)
01751 continue;
01752 if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
01753 continue;
01754 obsp = s->repo->idarraydata + s->obsoletes;
01755
01756 while ((obs = *obsp++) != 0)
01757 FOR_PROVIDES(po, ppo, obs)
01758 MAPSET(&obsmap, po);
01759 }
01760 for (i = j = 0; i < dqs.count; i++)
01761 if (!MAPTST(&obsmap, dqs.elements[i]))
01762 dqs.elements[j++] = dqs.elements[i];
01763 dqs.count = j;
01764 for (i = j = 0; i < dq.count; i++)
01765 if (!MAPTST(&obsmap, dq.elements[i]))
01766 dq.elements[j++] = dq.elements[i];
01767 dq.count = j;
01768 map_free(&obsmap);
01769 }
01770
01771
01772 if (solv->ignorealreadyrecommended && dqs.count)
01773 {
01774
01775 for (i = 0; i < solv->decisionq.count; i++)
01776 {
01777 p = solv->decisionq.elements[i];
01778 if (p < 0)
01779 continue;
01780 s = pool->solvables + p;
01781 if (s->repo && s->repo != solv->installed)
01782 solv->decisionmap[p] = -solv->decisionmap[p];
01783 }
01784
01785 for (i = j = 0; i < dqs.count; i++)
01786 {
01787 p = dqs.elements[i];
01788 s = pool->solvables + p;
01789 if (!s->supplements)
01790 continue;
01791 if (!solver_is_supplementing(solv, s))
01792 dqs.elements[j++] = p;
01793 }
01794 dqs.count = j;
01795
01796 for (i = 0; i < solv->decisionq.count; i++)
01797 {
01798 p = solv->decisionq.elements[i];
01799 if (p < 0)
01800 continue;
01801 s = pool->solvables + p;
01802 if (s->repo && s->repo != solv->installed)
01803 solv->decisionmap[p] = -solv->decisionmap[p];
01804 }
01805 }
01806
01807
01808
01809
01810 if (dqs.count && solv->noobsoletes.size)
01811 {
01812 for (i = j = 0; i < dqs.count; i++)
01813 {
01814 p = dqs.elements[i];
01815 if (MAPTST(&solv->noobsoletes, p))
01816 {
01817 Id p2, pp2;
01818 s = pool->solvables + p;
01819 FOR_PROVIDES(p2, pp2, s->name)
01820 if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
01821 break;
01822 if (p2)
01823 continue;
01824 }
01825 dqs.elements[j++] = p;
01826 }
01827 dqs.count = j;
01828 }
01829
01830
01831 if (dqs.count)
01832 {
01833 for (i = 0; i < dqs.count; i++)
01834 queue_pushunique(&dq, dqs.elements[i]);
01835 }
01836
01837 if (dq.count)
01838 {
01839 Map dqmap;
01840 int decisioncount = solv->decisionq.count;
01841
01842 if (dq.count == 1)
01843 {
01844
01845 p = dq.elements[0];
01846 if (dqs.count)
01847 POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvid2str(pool, p));
01848 else
01849 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvid2str(pool, p));
01850 queue_push(&solv->recommendations, p);
01851 level = setpropagatelearn(solv, level, p, 0, 0);
01852 continue;
01853 }
01854
01855
01856 policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
01857
01858
01859 map_init(&dqmap, pool->nsolvables);
01860 for (i = 0; i < dq.count; i++)
01861 MAPSET(&dqmap, dq.elements[i]);
01862
01863
01864 for (i = 0; i < dqs.count; i++)
01865 {
01866 p = dqs.elements[i];
01867 if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
01868 continue;
01869 POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvid2str(pool, p));
01870 queue_push(&solv->recommendations, p);
01871 olevel = level;
01872 level = setpropagatelearn(solv, level, p, 0, 0);
01873 if (level <= olevel)
01874 break;
01875 }
01876 if (i < dqs.count || solv->decisionq.count < decisioncount)
01877 {
01878 map_free(&dqmap);
01879 continue;
01880 }
01881
01882
01883
01884
01885 for (i = 0; i < decisioncount; i++)
01886 {
01887 Id rec, *recp, pp;
01888 p = solv->decisionq.elements[i];
01889 if (p < 0)
01890 continue;
01891 s = pool->solvables + p;
01892 if (!s->repo || (solv->ignorealreadyrecommended && s->repo == solv->installed))
01893 continue;
01894 if (!s->recommends)
01895 continue;
01896 recp = s->repo->idarraydata + s->recommends;
01897 while ((rec = *recp++) != 0)
01898 {
01899 queue_empty(&dq);
01900 FOR_PROVIDES(p, pp, rec)
01901 {
01902 if (solv->decisionmap[p] > 0)
01903 {
01904 dq.count = 0;
01905 break;
01906 }
01907 else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
01908 queue_pushunique(&dq, p);
01909 }
01910 if (!dq.count)
01911 continue;
01912 if (dq.count > 1)
01913 {
01914
01915 for (i = 1; i < dq.count; i++)
01916 queue_push(&solv->branches, dq.elements[i]);
01917 queue_push(&solv->branches, -level);
01918 }
01919 p = dq.elements[0];
01920 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvid2str(pool, p));
01921 queue_push(&solv->recommendations, p);
01922 olevel = level;
01923 level = setpropagatelearn(solv, level, p, 0, 0);
01924 if (level <= olevel || solv->decisionq.count < decisioncount)
01925 break;
01926 }
01927 if (rec)
01928 break;
01929 }
01930 map_free(&dqmap);
01931
01932 continue;
01933 }
01934 }
01935
01936 if (solv->distupgrade && solv->installed)
01937 {
01938 int installedone = 0;
01939
01940
01941 POOL_DEBUG(SAT_DEBUG_SOLVER, "deciding orphaned packages\n");
01942 for (i = 0; i < solv->orphaned.count; i++)
01943 {
01944 p = solv->orphaned.elements[i];
01945 if (solv->decisionmap[p])
01946 continue;
01947 olevel = level;
01948 if (solv->distupgrade_removeunsupported)
01949 continue;
01950 if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
01951 continue;
01952 POOL_DEBUG(SAT_DEBUG_SOLVER, "keeping orphaned %s\n", solvid2str(pool, p));
01953 level = setpropagatelearn(solv, level, p, 0, 0);
01954 installedone = 1;
01955 if (level < olevel)
01956 break;
01957 }
01958 if (installedone || i < solv->orphaned.count)
01959 continue;
01960 for (i = 0; i < solv->orphaned.count; i++)
01961 {
01962 p = solv->orphaned.elements[i];
01963 if (solv->decisionmap[p])
01964 continue;
01965 POOL_DEBUG(SAT_DEBUG_SOLVER, "removing orphaned %s\n", solvid2str(pool, p));
01966 olevel = level;
01967 level = setpropagatelearn(solv, level, -p, 0, 0);
01968 if (level < olevel)
01969 break;
01970 }
01971 if (i < solv->orphaned.count)
01972 continue;
01973 }
01974
01975 if (solv->solution_callback)
01976 {
01977 solv->solution_callback(solv, solv->solution_callback_data);
01978 if (solv->branches.count)
01979 {
01980 int i = solv->branches.count - 1;
01981 int l = -solv->branches.elements[i];
01982 Id why;
01983
01984 for (; i > 0; i--)
01985 if (solv->branches.elements[i - 1] < 0)
01986 break;
01987 p = solv->branches.elements[i];
01988 POOL_DEBUG(SAT_DEBUG_SOLVER, "branching with %s\n", solvid2str(pool, p));
01989 queue_empty(&dq);
01990 for (j = i + 1; j < solv->branches.count; j++)
01991 queue_push(&dq, solv->branches.elements[j]);
01992 solv->branches.count = i;
01993 level = l;
01994 revert(solv, level);
01995 if (dq.count > 1)
01996 for (j = 0; j < dq.count; j++)
01997 queue_push(&solv->branches, dq.elements[j]);
01998 olevel = level;
01999 why = -solv->decisionq_why.elements[solv->decisionq_why.count];
02000 assert(why >= 0);
02001 level = setpropagatelearn(solv, level, p, disablerules, why);
02002 if (level == 0)
02003 {
02004 queue_free(&dq);
02005 queue_free(&dqs);
02006 return;
02007 }
02008 continue;
02009 }
02010
02011 break;
02012 }
02013
02014
02015 if (solv->branches.count)
02016 {
02017 int l = 0, lasti = -1, lastl = -1;
02018 Id why;
02019
02020 p = 0;
02021 for (i = solv->branches.count - 1; i >= 0; i--)
02022 {
02023 p = solv->branches.elements[i];
02024 if (p < 0)
02025 l = -p;
02026 else if (p > 0 && solv->decisionmap[p] > l + 1)
02027 {
02028 lasti = i;
02029 lastl = l;
02030 }
02031 }
02032 if (lasti >= 0)
02033 {
02034
02035 p = solv->branches.elements[lasti];
02036 solv->branches.elements[lasti] = 0;
02037 POOL_DEBUG(SAT_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, solvid2str(pool, p));
02038 minimizationsteps++;
02039
02040 level = lastl;
02041 revert(solv, level);
02042 why = -solv->decisionq_why.elements[solv->decisionq_why.count];
02043 assert(why >= 0);
02044 olevel = level;
02045 level = setpropagatelearn(solv, level, p, disablerules, why);
02046 if (level == 0)
02047 {
02048 queue_free(&dq);
02049 queue_free(&dqs);
02050 return;
02051 }
02052 continue;
02053 }
02054 }
02055
02056 break;
02057 }
02058
02059 POOL_DEBUG(SAT_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
02060
02061 POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n");
02062 queue_free(&dq);
02063 queue_free(&dqs);
02064 #if 0
02065 solver_printdecisionq(solv, SAT_DEBUG_RESULT);
02066 #endif
02067 }
02068
02069
02070
02071
02072
02073
02074
02075
02076
02077
02078
02079 static void
02080 removedisabledconflicts(Solver *solv, Queue *removed)
02081 {
02082 Pool *pool = solv->pool;
02083 int i, n;
02084 Id p, why, *dp;
02085 Id new;
02086 Rule *r;
02087 Id *decisionmap = solv->decisionmap;
02088
02089 POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n");
02090 queue_empty(removed);
02091 for (i = 0; i < solv->decisionq.count; i++)
02092 {
02093 p = solv->decisionq.elements[i];
02094 if (p > 0)
02095 continue;
02096 why = solv->decisionq_why.elements[i];
02097 if (why == 0)
02098 {
02099
02100 continue;
02101 }
02102
02103
02104 assert(why > 0);
02105 r = solv->rules + why;
02106 if (r->d < 0 && decisionmap[-p])
02107 {
02108
02109 POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvid2str(pool, -p), -p);
02110 queue_push(removed, -p);
02111 queue_push(removed, decisionmap[-p]);
02112 decisionmap[-p] = 0;
02113 }
02114 }
02115 if (!removed->count)
02116 return;
02117
02118
02119 new = 0;
02120 for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
02121 {
02122 if (i == solv->nrules)
02123 {
02124 i = 1;
02125 r = solv->rules + i;
02126 }
02127 if (r->d < 0)
02128 continue;
02129 if (!r->w2)
02130 {
02131 if (r->p < 0 && !decisionmap[-r->p])
02132 new = r->p;
02133 }
02134 else if (!r->d)
02135 {
02136
02137 if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
02138 new = r->p;
02139 else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
02140 new = r->w2;
02141 }
02142 else
02143 {
02144 if (r->p < 0 && decisionmap[-r->p] == 0)
02145 new = r->p;
02146 if (new || DECISIONMAP_FALSE(r->p))
02147 {
02148 dp = pool->whatprovidesdata + r->d;
02149 while ((p = *dp++) != 0)
02150 {
02151 if (new && p == new)
02152 continue;
02153 if (p < 0 && decisionmap[-p] == 0)
02154 {
02155 if (new)
02156 {
02157 new = 0;
02158 break;
02159 }
02160 new = p;
02161 }
02162 else if (!DECISIONMAP_FALSE(p))
02163 {
02164 new = 0;
02165 break;
02166 }
02167 }
02168 }
02169 }
02170 if (new)
02171 {
02172 POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvid2str(pool, -new), -new);
02173 decisionmap[-new] = -1;
02174 new = 0;
02175 n = 0;
02176 }
02177 }
02178 }
02179
02180 static inline void
02181 undo_removedisabledconflicts(Solver *solv, Queue *removed)
02182 {
02183 int i;
02184 for (i = 0; i < removed->count; i += 2)
02185 solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
02186 }
02187
02188
02189
02190
02191
02192
02193
02194 static void
02195 weaken_solvable_deps(Solver *solv, Id p)
02196 {
02197 int i;
02198 Rule *r;
02199
02200 for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
02201 {
02202 if (r->p != -p)
02203 continue;
02204 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
02205 continue;
02206 queue_push(&solv->weakruleq, i);
02207 }
02208 }
02209
02210
02211
02212
02213
02214
02215 static void
02216 findrecommendedsuggested(Solver *solv)
02217 {
02218 Pool *pool = solv->pool;
02219 Queue redoq, disabledq;
02220 int goterase, i;
02221 Solvable *s;
02222 Rule *r;
02223 Map obsmap;
02224
02225 map_init(&obsmap, pool->nsolvables);
02226 if (solv->installed)
02227 {
02228 Id obs, *obsp, p, po, ppo;
02229 for (p = solv->installed->start; p < solv->installed->end; p++)
02230 {
02231 s = pool->solvables + p;
02232 if (s->repo != solv->installed || !s->obsoletes)
02233 continue;
02234 if (solv->decisionmap[p] <= 0)
02235 continue;
02236 if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
02237 continue;
02238 obsp = s->repo->idarraydata + s->obsoletes;
02239
02240 while ((obs = *obsp++) != 0)
02241 FOR_PROVIDES(po, ppo, obs)
02242 MAPSET(&obsmap, po);
02243 }
02244 }
02245
02246 queue_init(&redoq);
02247 queue_init(&disabledq);
02248 goterase = 0;
02249
02250 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
02251 {
02252 if (r->d < 0)
02253 continue;
02254 if (r->p >= 0)
02255 continue;
02256 queue_push(&disabledq, i);
02257 solver_disablerule(solv, r);
02258 goterase++;
02259 }
02260
02261 if (goterase)
02262 {
02263 enabledisablelearntrules(solv);
02264 removedisabledconflicts(solv, &redoq);
02265 }
02266
02267
02268
02269
02270
02271
02272
02273 if (redoq.count || solv->dontinstallrecommended || !solv->dontshowinstalledrecommended || solv->ignorealreadyrecommended)
02274 {
02275 Id rec, *recp, p, pp;
02276
02277
02278 solv->recommends_index = -1;
02279 MAPZERO(&solv->recommendsmap);
02280 for (i = 0; i < solv->decisionq.count; i++)
02281 {
02282 p = solv->decisionq.elements[i];
02283 if (p < 0)
02284 continue;
02285 s = pool->solvables + p;
02286 if (s->recommends)
02287 {
02288 recp = s->repo->idarraydata + s->recommends;
02289 while ((rec = *recp++) != 0)
02290 {
02291 FOR_PROVIDES(p, pp, rec)
02292 if (solv->decisionmap[p] > 0)
02293 break;
02294 if (p)
02295 {
02296 if (!solv->dontshowinstalledrecommended)
02297 {
02298 FOR_PROVIDES(p, pp, rec)
02299 if (solv->decisionmap[p] > 0)
02300 MAPSET(&solv->recommendsmap, p);
02301 }
02302 continue;
02303 }
02304 FOR_PROVIDES(p, pp, rec)
02305 MAPSET(&solv->recommendsmap, p);
02306 }
02307 }
02308 }
02309 for (i = 1; i < pool->nsolvables; i++)
02310 {
02311 if (solv->decisionmap[i] < 0)
02312 continue;
02313 if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
02314 continue;
02315 if (MAPTST(&obsmap, i))
02316 continue;
02317 s = pool->solvables + i;
02318 if (!MAPTST(&solv->recommendsmap, i))
02319 {
02320 if (!s->supplements)
02321 continue;
02322 if (!pool_installable(pool, s))
02323 continue;
02324 if (!solver_is_supplementing(solv, s))
02325 continue;
02326 }
02327 if (solv->dontinstallrecommended)
02328 queue_push(&solv->recommendations, i);
02329 else
02330 queue_pushunique(&solv->recommendations, i);
02331 }
02332
02333 policy_filter_unwanted(solv, &solv->recommendations, POLICY_MODE_SUGGEST);
02334 }
02335
02336
02337
02338
02339
02340 if (1)
02341 {
02342 Id sug, *sugp, p, pp;
02343
02344
02345 solv->recommends_index = -1;
02346 MAPZERO(&solv->suggestsmap);
02347 for (i = 0; i < solv->decisionq.count; i++)
02348 {
02349 p = solv->decisionq.elements[i];
02350 if (p < 0)
02351 continue;
02352 s = pool->solvables + p;
02353 if (s->suggests)
02354 {
02355 sugp = s->repo->idarraydata + s->suggests;
02356 while ((sug = *sugp++) != 0)
02357 {
02358 FOR_PROVIDES(p, pp, sug)
02359 if (solv->decisionmap[p] > 0)
02360 break;
02361 if (p)
02362 {
02363 if (!solv->dontshowinstalledrecommended)
02364 {
02365 FOR_PROVIDES(p, pp, sug)
02366 if (solv->decisionmap[p] > 0)
02367 MAPSET(&solv->suggestsmap, p);
02368 }
02369 continue;
02370 }
02371 FOR_PROVIDES(p, pp, sug)
02372 MAPSET(&solv->suggestsmap, p);
02373 }
02374 }
02375 }
02376 for (i = 1; i < pool->nsolvables; i++)
02377 {
02378 if (solv->decisionmap[i] < 0)
02379 continue;
02380 if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
02381 continue;
02382 if (MAPTST(&obsmap, i))
02383 continue;
02384 s = pool->solvables + i;
02385 if (!MAPTST(&solv->suggestsmap, i))
02386 {
02387 if (!s->enhances)
02388 continue;
02389 if (!pool_installable(pool, s))
02390 continue;
02391 if (!solver_is_enhancing(solv, s))
02392 continue;
02393 }
02394 queue_push(&solv->suggestions, i);
02395 }
02396 policy_filter_unwanted(solv, &solv->suggestions, POLICY_MODE_SUGGEST);
02397 }
02398
02399
02400 if (redoq.count)
02401 undo_removedisabledconflicts(solv, &redoq);
02402 queue_free(&redoq);
02403
02404
02405 for (i = 0; i < disabledq.count; i++)
02406 solver_enablerule(solv, solv->rules + disabledq.elements[i]);
02407 queue_free(&disabledq);
02408 map_free(&obsmap);
02409 }
02410
02411 void
02412 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *noobsmap)
02413 {
02414 int i;
02415 Id how, what, select;
02416 Id p, pp;
02417 for (i = 0; i < job->count; i += 2)
02418 {
02419 how = job->elements[i];
02420 if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
02421 continue;
02422 what = job->elements[i + 1];
02423 select = how & SOLVER_SELECTMASK;
02424 if (!noobsmap->size)
02425 map_grow(noobsmap, pool->nsolvables);
02426 FOR_JOB_SELECT(p, pp, select, what)
02427 MAPSET(noobsmap, p);
02428 }
02429 }
02430
02431
02432
02433
02434
02435
02436
02437 void
02438 solver_solve(Solver *solv, Queue *job)
02439 {
02440 Pool *pool = solv->pool;
02441 Repo *installed = solv->installed;
02442 int i;
02443 int oldnrules;
02444 Map addedmap;
02445 Map installcandidatemap;
02446 Id how, what, select, name, weak, p, pp, d;
02447 Queue q;
02448 Solvable *s;
02449 Rule *r;
02450 int now, solve_start;
02451 int hasdupjob = 0;
02452
02453 solve_start = sat_timems(0);
02454
02455
02456 POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n");
02457 POOL_DEBUG(SAT_DEBUG_STATS, "fixsystem=%d updatesystem=%d dosplitprovides=%d, noupdateprovide=%d noinfarchcheck=%d\n", solv->fixsystem, solv->updatesystem, solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
02458 POOL_DEBUG(SAT_DEBUG_STATS, "distupgrade=%d distupgrade_removeunsupported=%d\n", solv->distupgrade, solv->distupgrade_removeunsupported);
02459 POOL_DEBUG(SAT_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
02460 POOL_DEBUG(SAT_DEBUG_STATS, "promoteepoch=%d, novirtualconflicts=%d, allowselfconflicts=%d\n", pool->promoteepoch, pool->novirtualconflicts, pool->allowselfconflicts);
02461 POOL_DEBUG(SAT_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors);
02462 POOL_DEBUG(SAT_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d, dontshowinstalledrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended, solv->dontshowinstalledrecommended);
02463
02464
02465 if (!pool->whatprovides)
02466 pool_createwhatprovides(pool);
02467
02468
02469 policy_create_obsolete_index(solv);
02470
02471
02472 queue_free(&solv->job);
02473 queue_init_clone(&solv->job, job);
02474
02475
02476
02477
02478
02479
02480
02481 solver_calculate_noobsmap(pool, job, &solv->noobsoletes);
02482
02483 map_init(&addedmap, pool->nsolvables);
02484 MAPSET(&addedmap, SYSTEMSOLVABLE);
02485
02486 map_init(&installcandidatemap, pool->nsolvables);
02487 queue_init(&q);
02488
02489 now = sat_timems(0);
02490
02491
02492
02493
02494
02495 if (installed)
02496 {
02497
02498 for (i = 0; i < job->count; i += 2)
02499 {
02500 how = job->elements[i];
02501 what = job->elements[i + 1];
02502 select = how & SOLVER_SELECTMASK;
02503 switch (how & SOLVER_JOBMASK)
02504 {
02505 case SOLVER_VERIFY:
02506 FOR_JOB_SELECT(p, pp, select, what)
02507 {
02508 s = pool->solvables + p;
02509 if (!solv->installed || s->repo != solv->installed)
02510 continue;
02511 if (!solv->fixmap.size)
02512 map_grow(&solv->fixmap, solv->installed->end - solv->installed->start);
02513 MAPSET(&solv->fixmap, p - solv->installed->start);
02514 }
02515 break;
02516 default:
02517 break;
02518 }
02519 }
02520
02521 oldnrules = solv->nrules;
02522 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
02523 FOR_REPO_SOLVABLES(installed, p, s)
02524 solver_addrpmrulesforsolvable(solv, s, &addedmap);
02525 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
02526 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
02527 oldnrules = solv->nrules;
02528 FOR_REPO_SOLVABLES(installed, p, s)
02529 solver_addrpmrulesforupdaters(solv, s, &addedmap, 1);
02530 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
02531 }
02532
02533
02534
02535
02536
02537
02538 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
02539 oldnrules = solv->nrules;
02540 for (i = 0; i < job->count; i += 2)
02541 {
02542 how = job->elements[i];
02543 what = job->elements[i + 1];
02544 select = how & SOLVER_SELECTMASK;
02545
02546 switch (how & SOLVER_JOBMASK)
02547 {
02548 case SOLVER_INSTALL:
02549 FOR_JOB_SELECT(p, pp, select, what)
02550 {
02551 MAPSET(&installcandidatemap, p);
02552 solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
02553 }
02554 break;
02555 case SOLVER_DISTUPGRADE:
02556 if (!solv->distupgrade)
02557 hasdupjob = 1;
02558 break;
02559 default:
02560 break;
02561 }
02562 }
02563 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
02564
02565
02566
02567
02568
02569 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for suggested/enhanced packages ***\n");
02570 oldnrules = solv->nrules;
02571 solver_addrpmrulesforweak(solv, &addedmap);
02572 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
02573
02574
02575
02576
02577
02578
02579
02580
02581
02582 IF_POOLDEBUG (SAT_DEBUG_STATS)
02583 {
02584 int possible = 0, installable = 0;
02585 for (i = 1; i < pool->nsolvables; i++)
02586 {
02587 if (pool_installable(pool, pool->solvables + i))
02588 installable++;
02589 if (MAPTST(&addedmap, i))
02590 possible++;
02591 }
02592 POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
02593 }
02594
02595 solver_unifyrules(solv);
02596 solv->rpmrules_end = solv->nrules;
02597
02598 POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
02599 POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule creation took %d ms\n", sat_timems(now));
02600
02601
02602
02603 if (hasdupjob)
02604 solver_createdupmaps(solv);
02605
02606
02607
02608
02609
02610
02611
02612
02613
02614
02615
02616
02617
02618 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add feature rules ***\n");
02619 solv->featurerules = solv->nrules;
02620 if (installed)
02621 {
02622
02623 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
02624 {
02625 if (s->repo != installed)
02626 {
02627 solver_addrule(solv, 0, 0);
02628 continue;
02629 }
02630 solver_addupdaterule(solv, s, 1);
02631 }
02632
02633 assert(solv->nrules - solv->featurerules == installed->end - installed->start);
02634 }
02635 solv->featurerules_end = solv->nrules;
02636
02637
02638
02639
02640
02641
02642
02643
02644 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n");
02645 solv->updaterules = solv->nrules;
02646
02647 if (installed)
02648 {
02649
02650 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
02651 {
02652 Rule *sr;
02653
02654 if (s->repo != installed)
02655 {
02656 solver_addrule(solv, 0, 0);
02657 continue;
02658 }
02659 solver_addupdaterule(solv, s, 0);
02660
02661
02662
02663 r = solv->rules + solv->nrules - 1;
02664 sr = r - (installed->end - installed->start);
02665
02666
02667 if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
02668 queue_push(&solv->orphaned, i);
02669 if (!r->p)
02670 {
02671 assert(solv->distupgrade && !sr->p);
02672 continue;
02673 }
02674 if (!solver_samerule(solv, r, sr))
02675 {
02676
02677 if (solv->allowuninstall)
02678 {
02679
02680 memset(r, 0, sizeof(*r));
02681 queue_push(&solv->weakruleq, sr - solv->rules);
02682 }
02683 else
02684 {
02685
02686 memset(sr, 0, sizeof(*sr));
02687 }
02688 }
02689 else if (solv->allowuninstall)
02690 {
02691
02692 queue_push(&solv->weakruleq, r - solv->rules);
02693 queue_push(&solv->weakruleq, sr - solv->rules);
02694 }
02695 else
02696 solver_disablerule(solv, sr);
02697 }
02698
02699 assert(solv->nrules - solv->updaterules == installed->end - installed->start);
02700 }
02701 solv->updaterules_end = solv->nrules;
02702
02703
02704
02705
02706
02707
02708 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
02709
02710 solv->jobrules = solv->nrules;
02711 for (i = 0; i < job->count; i += 2)
02712 {
02713 oldnrules = solv->nrules;
02714
02715 how = job->elements[i];
02716 what = job->elements[i + 1];
02717 weak = how & SOLVER_WEAK;
02718 select = how & SOLVER_SELECTMASK;
02719 switch (how & SOLVER_JOBMASK)
02720 {
02721 case SOLVER_INSTALL:
02722 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
02723 if (select == SOLVER_SOLVABLE)
02724 {
02725 p = what;
02726 d = 0;
02727 }
02728 else
02729 {
02730 queue_empty(&q);
02731 FOR_JOB_SELECT(p, pp, select, what)
02732 queue_push(&q, p);
02733 if (!q.count)
02734 {
02735
02736 queue_push(&q, -SYSTEMSOLVABLE);
02737 }
02738 p = queue_shift(&q);
02739 d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);
02740 }
02741 solver_addrule(solv, p, d);
02742 queue_push(&solv->ruletojob, i);
02743 if (weak)
02744 queue_push(&solv->weakruleq, solv->nrules - 1);
02745 break;
02746 case SOLVER_ERASE:
02747 POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
02748 if (select == SOLVER_SOLVABLE && solv->installed && pool->solvables[what].repo == solv->installed)
02749 {
02750
02751
02752
02753 name = pool->solvables[what].name;
02754 FOR_PROVIDES(p, pp, name)
02755 {
02756 if (p == what)
02757 continue;
02758 s = pool->solvables + p;
02759 if (s->name != name)
02760 continue;
02761
02762 if (s->repo == solv->installed)
02763 continue;
02764
02765 if (MAPTST(&installcandidatemap, p))
02766 continue;
02767 solver_addrule(solv, -p, 0);
02768 queue_push(&solv->ruletojob, i);
02769 if (weak)
02770 queue_push(&solv->weakruleq, solv->nrules - 1);
02771 }
02772 }
02773 FOR_JOB_SELECT(p, pp, select, what)
02774 {
02775 solver_addrule(solv, -p, 0);
02776 queue_push(&solv->ruletojob, i);
02777 if (weak)
02778 queue_push(&solv->weakruleq, solv->nrules - 1);
02779 }
02780 break;
02781
02782 case SOLVER_UPDATE:
02783 POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
02784 FOR_JOB_SELECT(p, pp, select, what)
02785 {
02786 s = pool->solvables + p;
02787 if (!solv->installed || s->repo != solv->installed)
02788 continue;
02789 if (!solv->updatemap.size)
02790 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
02791 MAPSET(&solv->updatemap, p - solv->installed->start);
02792 }
02793 break;
02794 case SOLVER_VERIFY:
02795 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
02796 break;
02797 case SOLVER_WEAKENDEPS:
02798 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
02799 if (select != SOLVER_SOLVABLE)
02800 break;
02801 s = pool->solvables + what;
02802 weaken_solvable_deps(solv, what);
02803 break;
02804 case SOLVER_NOOBSOLETES:
02805 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
02806 break;
02807 case SOLVER_LOCK:
02808 POOL_DEBUG(SAT_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
02809 FOR_JOB_SELECT(p, pp, select, what)
02810 {
02811 s = pool->solvables + p;
02812 if (installed && s->repo == installed)
02813 solver_addrule(solv, p, 0);
02814 else
02815 solver_addrule(solv, -p, 0);
02816 queue_push(&solv->ruletojob, i);
02817 if (weak)
02818 queue_push(&solv->weakruleq, solv->nrules - 1);
02819 }
02820 break;
02821 case SOLVER_DISTUPGRADE:
02822 POOL_DEBUG(SAT_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(solv, select, what));
02823 break;
02824 case SOLVER_DROP_ORPHANED:
02825 POOL_DEBUG(SAT_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(solv, select, what));
02826 FOR_JOB_SELECT(p, pp, select, what)
02827 {
02828 s = pool->solvables + p;
02829 if (!installed || s->repo != installed)
02830 continue;
02831 if (!solv->droporphanedmap.size)
02832 map_grow(&solv->droporphanedmap, installed->end - installed->start);
02833 MAPSET(&solv->droporphanedmap, p - installed->start);
02834 }
02835 break;
02836 default:
02837 POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n");
02838 break;
02839 }
02840
02841
02842
02843
02844
02845 IF_POOLDEBUG (SAT_DEBUG_JOB)
02846 {
02847 int j;
02848 if (solv->nrules == oldnrules)
02849 POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n");
02850 for (j = oldnrules; j < solv->nrules; j++)
02851 {
02852 POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
02853 solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
02854 }
02855 }
02856 }
02857 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
02858 solv->jobrules_end = solv->nrules;
02859
02860
02861 if (!solv->noinfarchcheck)
02862 {
02863 solver_addinfarchrules(solv, &addedmap);
02864 if (pool->obsoleteusescolors)
02865 {
02866
02867
02868 for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
02869 queue_push(&solv->weakruleq, i);
02870 }
02871 }
02872 else
02873 solv->infarchrules = solv->infarchrules_end = solv->nrules;
02874
02875 if (hasdupjob)
02876 {
02877 solver_addduprules(solv, &addedmap);
02878 solver_freedupmaps(solv);
02879 }
02880 else
02881 solv->duprules = solv->duprules_end = solv->nrules;
02882
02883 if (1)
02884 {
02885 extern void addchoicerules(Solver *solv);
02886 addchoicerules(solv);
02887 }
02888 else
02889 solv->choicerules = solv->choicerules_end = solv->nrules;
02890
02891
02892
02893
02894
02895
02896
02897 map_free(&addedmap);
02898 map_free(&installcandidatemap);
02899 queue_free(&q);
02900
02901 POOL_DEBUG(SAT_DEBUG_STATS, "%d rpm rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules\n", solv->rpmrules_end - 1, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules, solv->choicerules_end - solv->choicerules);
02902
02903
02904 map_init(&solv->weakrulemap, solv->nrules);
02905 for (i = 0; i < solv->weakruleq.count; i++)
02906 {
02907 p = solv->weakruleq.elements[i];
02908 MAPSET(&solv->weakrulemap, p);
02909 }
02910
02911
02912 solv->learntrules = solv->nrules;
02913
02914
02915 makewatches(solv);
02916
02917
02918
02919 for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
02920 if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
02921 queue_push(&solv->ruleassertions, i);
02922
02923
02924 solver_disablepolicyrules(solv);
02925
02926
02927 makeruledecisions(solv);
02928 POOL_DEBUG(SAT_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
02929
02930
02931
02932
02933
02934
02935
02936 now = sat_timems(0);
02937 solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
02938 POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now));
02939
02940
02941
02942
02943 findrecommendedsuggested(solv);
02944
02945
02946
02947
02948 solver_prepare_solutions(solv);
02949
02950
02951
02952
02953 transaction_calculate(&solv->trans, &solv->decisionq, &solv->noobsoletes);
02954
02955 POOL_DEBUG(SAT_DEBUG_STATS, "final solver statistics: %d problems, %d learned rules, %d unsolvable\n", solv->problems.count / 2, solv->stats_learned, solv->stats_unsolvable);
02956 POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start));
02957 }
02958
02959
02960
02961
02962
02963
02964
02965
02966
02967 void
02968 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
02969 {
02970 Map installedmap;
02971
02972 solver_create_state_maps(solv, &installedmap, 0);
02973 pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
02974 map_free(&installedmap);
02975 }
02976
02977
02978
02979
02980
02981
02982
02983 int
02984 solver_calc_installsizechange(Solver *solv)
02985 {
02986 Map installedmap;
02987 int change;
02988
02989 solver_create_state_maps(solv, &installedmap, 0);
02990 change = pool_calc_installsizechange(solv->pool, &installedmap);
02991 map_free(&installedmap);
02992 return change;
02993 }
02994
02995 void
02996 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
02997 {
02998 Map installedmap;
02999 solver_create_state_maps(solv, &installedmap, 0);
03000 pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
03001 map_free(&installedmap);
03002 }
03003
03004
03005 #if 0
03006 #define FIND_INVOLVED_DEBUG 0
03007 void
03008 solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q)
03009 {
03010 Pool *pool = solv->pool;
03011 Map im;
03012 Map installedm;
03013 Solvable *s;
03014 Queue iq;
03015 Queue installedq_internal;
03016 Id tp, ip, p, pp, req, *reqp, sup, *supp;
03017 int i, count;
03018
03019 tp = ts - pool->solvables;
03020 queue_init(&iq);
03021 queue_init(&installedq_internal);
03022 map_init(&im, pool->nsolvables);
03023 map_init(&installedm, pool->nsolvables);
03024
03025 if (!installedq)
03026 {
03027 installedq = &installedq_internal;
03028 if (solv->installed)
03029 {
03030 for (ip = solv->installed->start; ip < solv->installed->end; ip++)
03031 {
03032 s = pool->solvables + ip;
03033 if (s->repo != solv->installed)
03034 continue;
03035 queue_push(installedq, ip);
03036 }
03037 }
03038 }
03039 for (i = 0; i < installedq->count; i++)
03040 {
03041 ip = installedq->elements[i];
03042 MAPSET(&installedm, ip);
03043 MAPSET(&im, ip);
03044 }
03045
03046 queue_push(&iq, ts - pool->solvables);
03047 while (iq.count)
03048 {
03049 ip = queue_shift(&iq);
03050 if (!MAPTST(&im, ip))
03051 continue;
03052 if (!MAPTST(&installedm, ip))
03053 continue;
03054 MAPCLR(&im, ip);
03055 s = pool->solvables + ip;
03056 #if FIND_INVOLVED_DEBUG
03057 printf("hello %s\n", solvable2str(pool, s));
03058 #endif
03059 if (s->requires)
03060 {
03061 reqp = s->repo->idarraydata + s->requires;
03062 while ((req = *reqp++) != 0)
03063 {
03064 if (req == SOLVABLE_PREREQMARKER)
03065 continue;
03066
03067 count = 0;
03068 FOR_PROVIDES(p, pp, req)
03069 if (MAPTST(&installedm, p))
03070 count++;
03071 if (count > 1)
03072 continue;
03073 FOR_PROVIDES(p, pp, req)
03074 {
03075 if (MAPTST(&im, p))
03076 {
03077 #if FIND_INVOLVED_DEBUG
03078 printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p));
03079 #endif
03080 queue_push(&iq, p);
03081 }
03082 }
03083 }
03084 }
03085 if (s->recommends)
03086 {
03087 reqp = s->repo->idarraydata + s->recommends;
03088 while ((req = *reqp++) != 0)
03089 {
03090 count = 0;
03091 FOR_PROVIDES(p, pp, req)
03092 if (MAPTST(&installedm, p))
03093 count++;
03094 if (count > 1)
03095 continue;
03096 FOR_PROVIDES(p, pp, req)
03097 {
03098 if (MAPTST(&im, p))
03099 {
03100 #if FIND_INVOLVED_DEBUG
03101 printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p));
03102 #endif
03103 queue_push(&iq, p);
03104 }
03105 }
03106 }
03107 }
03108 if (!iq.count)
03109 {
03110
03111 for (i = 0; i < installedq->count; i++)
03112 {
03113 ip = installedq->elements[i];
03114 s = pool->solvables + ip;
03115 if (!s->supplements)
03116 continue;
03117 if (!MAPTST(&im, ip))
03118 continue;
03119 supp = s->repo->idarraydata + s->supplements;
03120 while ((sup = *supp++) != 0)
03121 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
03122 break;
03123
03124 if (sup)
03125 {
03126 #if FIND_INVOLVED_DEBUG
03127 printf("%s supplemented\n", solvid2str(pool, ip));
03128 #endif
03129 queue_push(&iq, ip);
03130 }
03131 }
03132 }
03133 }
03134
03135 for (i = 0; i < installedq->count; i++)
03136 {
03137 ip = installedq->elements[i];
03138 if (MAPTST(&im, ip))
03139 queue_push(&iq, ip);
03140 }
03141
03142 while (iq.count)
03143 {
03144 ip = queue_shift(&iq);
03145 if (!MAPTST(&installedm, ip))
03146 continue;
03147 s = pool->solvables + ip;
03148 #if FIND_INVOLVED_DEBUG
03149 printf("bye %s\n", solvable2str(pool, s));
03150 #endif
03151 if (s->requires)
03152 {
03153 reqp = s->repo->idarraydata + s->requires;
03154 while ((req = *reqp++) != 0)
03155 {
03156 FOR_PROVIDES(p, pp, req)
03157 {
03158 if (!MAPTST(&im, p))
03159 {
03160 if (p == tp)
03161 continue;
03162 #if FIND_INVOLVED_DEBUG
03163 printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p));
03164 #endif
03165 MAPSET(&im, p);
03166 queue_push(&iq, p);
03167 }
03168 }
03169 }
03170 }
03171 if (s->recommends)
03172 {
03173 reqp = s->repo->idarraydata + s->recommends;
03174 while ((req = *reqp++) != 0)
03175 {
03176 FOR_PROVIDES(p, pp, req)
03177 {
03178 if (!MAPTST(&im, p))
03179 {
03180 if (p == tp)
03181 continue;
03182 #if FIND_INVOLVED_DEBUG
03183 printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p));
03184 #endif
03185 MAPSET(&im, p);
03186 queue_push(&iq, p);
03187 }
03188 }
03189 }
03190 }
03191 if (!iq.count)
03192 {
03193
03194 for (i = 0; i < installedq->count; i++)
03195 {
03196 ip = installedq->elements[i];
03197 if (ip == tp)
03198 continue;
03199 s = pool->solvables + ip;
03200 if (!s->supplements)
03201 continue;
03202 if (MAPTST(&im, ip))
03203 continue;
03204 supp = s->repo->idarraydata + s->supplements;
03205 while ((sup = *supp++) != 0)
03206 if (dep_possible(solv, sup, &im))
03207 break;
03208 if (sup)
03209 {
03210 #if FIND_INVOLVED_DEBUG
03211 printf("%s supplemented\n", solvid2str(pool, ip));
03212 #endif
03213 MAPSET(&im, ip);
03214 queue_push(&iq, ip);
03215 }
03216 }
03217 }
03218 }
03219
03220 queue_free(&iq);
03221
03222
03223 for (i = 0; i < installedq->count; i++)
03224 {
03225 ip = installedq->elements[i];
03226 if (MAPTST(&im, ip))
03227 continue;
03228 if (ip == ts - pool->solvables)
03229 continue;
03230 queue_push(q, ip);
03231 }
03232 map_free(&im);
03233 map_free(&installedm);
03234 queue_free(&installedq_internal);
03235 }
03236 #endif
03237