1 /*
2 * Copyright (c) 2007-2009, Novell Inc.
3 *
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
6 */
7
8 /*
9 * problems.c
10 *
11 */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <unistd.h>
16 #include <string.h>
17 #include <assert.h>
18
19 #include "solver.h"
20 #include "solver_private.h"
21 #include "bitmap.h"
22 #include "pool.h"
23 #include "util.h"
24 #include "evr.h"
25 #include "solverdebug.h"
26
27
28 /**********************************************************************************/
29
30 /* a problem is an item on the solver's problem list. It can either be >0, in that
31 * case it is a update/infarch/dup rule, or it can be <0, which makes it refer to a job
32 * consisting of multiple job rules.
33 */
34
35 void
solver_disableproblem(Solver * solv,Id v)36 solver_disableproblem(Solver *solv, Id v)
37 {
38 Rule *r;
39 int i;
40 Id *jp;
41
42 if (v > 0)
43 {
44 if (v >= solv->infarchrules && v < solv->infarchrules_end)
45 {
46 Pool *pool = solv->pool;
47 Id name = pool->solvables[-solv->rules[v].p].name;
48 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
49 v--;
50 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
51 solver_disablerule(solv, solv->rules + v);
52 return;
53 }
54 if (v >= solv->duprules && v < solv->duprules_end)
55 {
56 Pool *pool = solv->pool;
57 Id name = pool->solvables[-solv->rules[v].p].name;
58 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
59 v--;
60 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
61 solver_disablerule(solv, solv->rules + v);
62 return;
63 }
64 solver_disablerule(solv, solv->rules + v);
65 #if 0
66 /* XXX: doesn't work */
67 if (v >= solv->updaterules && v < solv->updaterules_end)
68 {
69 /* enable feature rule if we disabled the update rule */
70 r = solv->rules + (v - solv->updaterules + solv->featurerules);
71 if (r->p)
72 solver_enablerule(solv, r);
73 }
74 #endif
75 return;
76 }
77 v = -(v + 1);
78 jp = solv->ruletojob.elements;
79 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
80 if (*jp == v)
81 solver_disablerule(solv, r);
82 }
83
84 /*-------------------------------------------------------------------
85 * enableproblem
86 */
87
88 void
solver_enableproblem(Solver * solv,Id v)89 solver_enableproblem(Solver *solv, Id v)
90 {
91 Rule *r;
92 int i;
93 Id *jp;
94
95 if (v > 0)
96 {
97 if (v >= solv->infarchrules && v < solv->infarchrules_end)
98 {
99 Pool *pool = solv->pool;
100 Id name = pool->solvables[-solv->rules[v].p].name;
101 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
102 v--;
103 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
104 solver_enablerule(solv, solv->rules + v);
105 return;
106 }
107 if (v >= solv->duprules && v < solv->duprules_end)
108 {
109 Pool *pool = solv->pool;
110 Id name = pool->solvables[-solv->rules[v].p].name;
111 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
112 v--;
113 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
114 solver_enablerule(solv, solv->rules + v);
115 return;
116 }
117 if (v >= solv->featurerules && v < solv->featurerules_end)
118 {
119 /* do not enable feature rule if update rule is enabled */
120 r = solv->rules + (v - solv->featurerules + solv->updaterules);
121 if (r->d >= 0)
122 return;
123 }
124 solver_enablerule(solv, solv->rules + v);
125 if (v >= solv->updaterules && v < solv->updaterules_end)
126 {
127 /* disable feature rule when enabling update rule */
128 r = solv->rules + (v - solv->updaterules + solv->featurerules);
129 if (r->p)
130 solver_disablerule(solv, r);
131 }
132 return;
133 }
134 v = -(v + 1);
135 jp = solv->ruletojob.elements;
136 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
137 if (*jp == v)
138 solver_enablerule(solv, r);
139 }
140
141
142 /*-------------------------------------------------------------------
143 * enable weak rules
144 *
145 * Reenable all disabled weak rules (marked in weakrulemap)
146 *
147 */
148
149 static void
enableweakrules(Solver * solv)150 enableweakrules(Solver *solv)
151 {
152 int i;
153 Rule *r;
154
155 for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
156 {
157 if (r->d >= 0) /* already enabled? */
158 continue;
159 if (!MAPTST(&solv->weakrulemap, i))
160 continue;
161 solver_enablerule(solv, r);
162 }
163 }
164
165
166 /*-------------------------------------------------------------------
167 *
168 * refine_suggestion
169 *
170 * at this point, all rules that led to conflicts are disabled.
171 * we re-enable all rules of a problem set but rule "sug", then
172 * continue to disable more rules until there as again a solution.
173 */
174
175 /* FIXME: think about conflicting assertions */
176
177 static void
refine_suggestion(Solver * solv,Id * problem,Id sug,Queue * refined,int essentialok)178 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok)
179 {
180 Pool *pool = solv->pool;
181 int i, j;
182 Id v;
183 Queue disabled;
184 int disabledcnt;
185
186 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
187 {
188 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion start\n");
189 for (i = 0; problem[i]; i++)
190 {
191 if (problem[i] == sug)
192 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "=> ");
193 solver_printproblem(solv, problem[i]);
194 }
195 }
196 queue_empty(refined);
197 if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0)
198 return;
199 queue_init(&disabled);
200 queue_push(refined, sug);
201
202 /* re-enable all problem rules with the exception of "sug"(gestion) */
203 solver_reset(solv);
204
205 for (i = 0; problem[i]; i++)
206 if (problem[i] != sug)
207 solver_enableproblem(solv, problem[i]);
208
209 if (sug < 0)
210 solver_reenablepolicyrules(solv, -sug);
211 else if (sug >= solv->updaterules && sug < solv->updaterules_end)
212 {
213 /* enable feature rule */
214 Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
215 if (r->p)
216 solver_enablerule(solv, r);
217 }
218
219 enableweakrules(solv);
220
221 for (;;)
222 {
223 int njob, nfeature, nupdate, pass;
224 queue_empty(&solv->problems);
225 solver_reset(solv);
226
227 if (!solv->problems.count)
228 solver_run_sat(solv, 0, 0);
229
230 if (!solv->problems.count)
231 {
232 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no more problems!\n");
233 break; /* great, no more problems */
234 }
235 disabledcnt = disabled.count;
236 /* start with 1 to skip over proof index */
237 njob = nfeature = nupdate = 0;
238 for (pass = 0; pass < 2; pass++)
239 {
240 for (i = 1; i < solv->problems.count - 1; i++)
241 {
242 /* ignore solutions in refined */
243 v = solv->problems.elements[i];
244 if (v == 0)
245 break; /* end of problem reached */
246 if (sug != v)
247 {
248 /* check if v is in the given problems list
249 * we allow disabling all problem rules *after* sug in
250 * pass 2, to prevent getting the same solution twice */
251 for (j = 0; problem[j]; j++)
252 if (problem[j] == v || (pass && problem[j] == sug))
253 break;
254 if (problem[j] == v)
255 continue;
256 }
257 if (v >= solv->featurerules && v < solv->featurerules_end)
258 nfeature++;
259 else if (v > 0)
260 nupdate++;
261 else
262 {
263 if (!essentialok && (solv->job.elements[-v - 1] & SOLVER_ESSENTIAL) != 0)
264 continue; /* not that one! */
265 njob++;
266 }
267 queue_push(&disabled, v);
268 }
269 if (disabled.count != disabledcnt)
270 break;
271 }
272 if (disabled.count == disabledcnt)
273 {
274 /* no solution found, this was an invalid suggestion! */
275 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no solution found!\n");
276 refined->count = 0;
277 break;
278 }
279 if (!njob && nupdate && nfeature)
280 {
281 /* got only update rules, filter out feature rules */
282 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "throwing away feature rules\n");
283 for (i = j = disabledcnt; i < disabled.count; i++)
284 {
285 v = disabled.elements[i];
286 if (v < solv->featurerules || v >= solv->featurerules_end)
287 disabled.elements[j++] = v;
288 }
289 disabled.count = j;
290 nfeature = 0;
291 }
292 if (disabled.count == disabledcnt + 1)
293 {
294 /* just one suggestion, add it to refined list */
295 v = disabled.elements[disabledcnt];
296 if (!nfeature && v != sug)
297 queue_push(refined, v); /* do not record feature rules */
298 solver_disableproblem(solv, v);
299 if (v >= solv->updaterules && v < solv->updaterules_end)
300 {
301 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
302 if (r->p)
303 solver_enablerule(solv, r); /* enable corresponding feature rule */
304 }
305 if (v < 0)
306 solver_reenablepolicyrules(solv, -v);
307 }
308 else
309 {
310 /* more than one solution, disable all */
311 /* do not push anything on refine list, as we do not know which solution to choose */
312 /* thus, the user will get another problem if he selects this solution, where he
313 * can choose the right one */
314 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
315 {
316 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "more than one solution found:\n");
317 for (i = disabledcnt; i < disabled.count; i++)
318 solver_printproblem(solv, disabled.elements[i]);
319 }
320 for (i = disabledcnt; i < disabled.count; i++)
321 {
322 v = disabled.elements[i];
323 solver_disableproblem(solv, v);
324 if (v >= solv->updaterules && v < solv->updaterules_end)
325 {
326 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
327 if (r->p)
328 solver_enablerule(solv, r);
329 }
330 }
331 }
332 }
333 /* all done, get us back into the same state as before */
334 /* enable refined rules again */
335 for (i = 0; i < disabled.count; i++)
336 solver_enableproblem(solv, disabled.elements[i]);
337 queue_free(&disabled);
338 /* reset policy rules */
339 for (i = 0; problem[i]; i++)
340 solver_enableproblem(solv, problem[i]);
341 solver_disablepolicyrules(solv);
342 /* disable problem rules again */
343 for (i = 0; problem[i]; i++)
344 solver_disableproblem(solv, problem[i]);
345 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion end\n");
346 }
347
348
349 /*-------------------------------------------------------------------
350 * sorting helper for problems
351 *
352 * bring update rules before job rules
353 * make essential job rules last
354 */
355
356 static int
problems_sortcmp(const void * ap,const void * bp,void * dp)357 problems_sortcmp(const void *ap, const void *bp, void *dp)
358 {
359 Queue *job = dp;
360 Id a = *(Id *)ap, b = *(Id *)bp;
361 if (a < 0 && b > 0)
362 return 1;
363 if (a > 0 && b < 0)
364 return -1;
365 if (a < 0 && b < 0)
366 {
367 int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
368 int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
369 int x = af - bf;
370 if (x)
371 return x;
372 }
373 return a - b;
374 }
375
376 /*
377 * convert a solution rule into a job modifier
378 */
379 static void
convertsolution(Solver * solv,Id why,Queue * solutionq)380 convertsolution(Solver *solv, Id why, Queue *solutionq)
381 {
382 Pool *pool = solv->pool;
383 if (why < 0)
384 {
385 why = -why;
386 if (why < solv->pooljobcnt)
387 {
388 queue_push(solutionq, SOLVER_SOLUTION_POOLJOB);
389 queue_push(solutionq, why);
390 }
391 else
392 {
393 queue_push(solutionq, SOLVER_SOLUTION_JOB);
394 queue_push(solutionq, why - solv->pooljobcnt);
395 }
396 return;
397 }
398 if (why >= solv->infarchrules && why < solv->infarchrules_end)
399 {
400 Id p, name;
401 /* infarch rule, find replacement */
402 assert(solv->rules[why].p < 0);
403 name = pool->solvables[-solv->rules[why].p].name;
404 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
405 why--;
406 p = 0;
407 for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
408 if (solv->decisionmap[-solv->rules[why].p] > 0)
409 {
410 p = -solv->rules[why].p;
411 break;
412 }
413 if (!p)
414 return; /* false alarm */
415 queue_push(solutionq, SOLVER_SOLUTION_INFARCH);
416 queue_push(solutionq, p);
417 return;
418 }
419 if (why >= solv->duprules && why < solv->duprules_end)
420 {
421 Id p, name;
422 /* dist upgrade rule, find replacement */
423 assert(solv->rules[why].p < 0);
424 name = pool->solvables[-solv->rules[why].p].name;
425 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
426 why--;
427 p = 0;
428 for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
429 if (solv->decisionmap[-solv->rules[why].p] > 0)
430 {
431 p = -solv->rules[why].p;
432 break;
433 }
434 if (!p)
435 return; /* false alarm */
436 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
437 queue_push(solutionq, p);
438 return;
439 }
440 if (why >= solv->updaterules && why < solv->updaterules_end)
441 {
442 /* update rule, find replacement package */
443 Id p, pp, rp = 0;
444 Rule *rr;
445
446 /* check if this is a false positive, i.e. the update rule is fulfilled */
447 rr = solv->rules + why;
448 FOR_RULELITERALS(p, pp, rr)
449 if (p > 0 && solv->decisionmap[p] > 0)
450 return; /* false alarm */
451
452 p = solv->installed->start + (why - solv->updaterules);
453 if (solv->dupmap_all && solv->rules[why].p != p && solv->decisionmap[p] > 0)
454 {
455 /* distupgrade case, allow to keep old package */
456 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
457 queue_push(solutionq, p);
458 return;
459 }
460 if (solv->decisionmap[p] > 0)
461 return; /* false alarm, turned out we can keep the package */
462 rr = solv->rules + solv->featurerules + (why - solv->updaterules);
463 if (!rr->p)
464 rr = solv->rules + why;
465 if (rr->w2)
466 {
467 int mvrp = 0; /* multi-version replacement */
468 FOR_RULELITERALS(rp, pp, rr)
469 {
470 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
471 {
472 mvrp = rp;
473 if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))
474 break;
475 }
476 }
477 if (!rp && mvrp)
478 {
479 /* found only multi-version replacements */
480 /* have to split solution into two parts */
481 queue_push(solutionq, p);
482 queue_push(solutionq, mvrp);
483 }
484 }
485 queue_push(solutionq, p);
486 queue_push(solutionq, rp);
487 return;
488 }
489 if (why >= solv->bestrules && why < solv->bestrules_end)
490 {
491 int mvrp;
492 Id p, pp, rp = 0;
493 Rule *rr;
494 /* check false positive */
495 rr = solv->rules + why;
496 FOR_RULELITERALS(p, pp, rr)
497 if (p > 0 && solv->decisionmap[p] > 0)
498 return; /* false alarm */
499 /* check update/feature rule */
500 p = solv->bestrules_pkg[why - solv->bestrules];
501 if (p < 0)
502 {
503 /* install job */
504 queue_push(solutionq, 0);
505 queue_push(solutionq, solv->ruletojob.elements[-p - solv->jobrules] + 1);
506 return;
507 }
508 if (solv->decisionmap[p] > 0)
509 {
510 /* disable best rule by keeping the old package */
511 queue_push(solutionq, SOLVER_SOLUTION_BEST);
512 queue_push(solutionq, p);
513 return;
514 }
515 rr = solv->rules + solv->featurerules + (p - solv->installed->start);
516 if (!rr->p)
517 rr = solv->rules + solv->updaterules + (p - solv->installed->start);
518 mvrp = 0; /* multi-version replacement */
519 FOR_RULELITERALS(rp, pp, rr)
520 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
521 {
522 mvrp = rp;
523 if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))
524 break;
525 }
526 if (!rp && mvrp)
527 {
528 queue_push(solutionq, SOLVER_SOLUTION_BEST); /* split, see above */
529 queue_push(solutionq, mvrp);
530 queue_push(solutionq, p);
531 queue_push(solutionq, 0);
532 return;
533 }
534 if (rp)
535 {
536 queue_push(solutionq, SOLVER_SOLUTION_BEST);
537 queue_push(solutionq, rp);
538 }
539 return;
540 }
541 }
542
543 /*
544 * convert problem data into a form usable for refining.
545 * Returns the number of problems.
546 */
547 int
solver_prepare_solutions(Solver * solv)548 solver_prepare_solutions(Solver *solv)
549 {
550 int i, j = 1, idx;
551
552 if (!solv->problems.count)
553 return 0;
554 queue_empty(&solv->solutions);
555 queue_push(&solv->solutions, 0); /* dummy so idx is always nonzero */
556 idx = solv->solutions.count;
557 queue_push(&solv->solutions, -1); /* unrefined */
558 /* proofidx stays in position, thus we start with 1 */
559 for (i = 1; i < solv->problems.count; i++)
560 {
561 Id p = solv->problems.elements[i];
562 queue_push(&solv->solutions, p);
563 if (p)
564 continue;
565 /* end of problem reached */
566 solv->problems.elements[j++] = idx;
567 if (i + 1 >= solv->problems.count)
568 break;
569 /* start another problem */
570 solv->problems.elements[j++] = solv->problems.elements[++i]; /* copy proofidx */
571 idx = solv->solutions.count;
572 queue_push(&solv->solutions, -1); /* unrefined */
573 }
574 solv->problems.count = j;
575 return j / 2;
576 }
577
578 /*
579 * refine the simple solution rule list provided by
580 * the solver into multiple lists of job modifiers.
581 */
582 static void
create_solutions(Solver * solv,int probnr,int solidx)583 create_solutions(Solver *solv, int probnr, int solidx)
584 {
585 Pool *pool = solv->pool;
586 Queue redoq;
587 Queue problem, solution, problems_save;
588 int i, j, nsol;
589 int essentialok;
590 unsigned int now;
591 int oldmistakes = solv->cleandeps_mistakes ? solv->cleandeps_mistakes->count : 0;
592 Id extraflags = -1;
593
594 now = solv_timems(0);
595 queue_init(&redoq);
596 /* save decisionq, decisionq_why, decisionmap */
597 for (i = 0; i < solv->decisionq.count; i++)
598 {
599 Id p = solv->decisionq.elements[i];
600 queue_push(&redoq, p);
601 queue_push(&redoq, solv->decisionq_why.elements[i]);
602 queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
603 }
604 /* save problems queue */
605 problems_save = solv->problems;
606 memset(&solv->problems, 0, sizeof(solv->problems));
607
608 /* extract problem from queue */
609 queue_init(&problem);
610 for (i = solidx + 1; i < solv->solutions.count; i++)
611 {
612 Id v = solv->solutions.elements[i];
613 if (!v)
614 break;
615 queue_push(&problem, v);
616 if (v < 0)
617 extraflags &= solv->job.elements[-v - 1];
618 }
619 if (extraflags == -1)
620 extraflags = 0;
621 if (problem.count > 1)
622 solv_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);
623 queue_push(&problem, 0); /* mark end for refine_suggestion */
624 problem.count--;
625 #if 0
626 for (i = 0; i < problem.count; i++)
627 printf("PP %d %d\n", i, problem.elements[i]);
628 #endif
629
630 /* refine each solution element */
631 nsol = 0;
632 essentialok = 0;
633 queue_init(&solution);
634 for (i = 0; i < problem.count; i++)
635 {
636 int solstart = solv->solutions.count;
637 refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok);
638 queue_push(&solv->solutions, 0); /* reserve room for number of elements */
639 for (j = 0; j < solution.count; j++)
640 convertsolution(solv, solution.elements[j], &solv->solutions);
641 if (solv->solutions.count == solstart + 1)
642 {
643 solv->solutions.count--; /* this one did not work out */
644 if (nsol || i + 1 < problem.count)
645 continue; /* got one or still hope */
646 if (!essentialok)
647 {
648 /* nothing found, start over */
649 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n");
650 essentialok = 1;
651 i = -1;
652 continue;
653 }
654 /* this is bad, we found no solution */
655 /* for now just offer a rule */
656 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n");
657 queue_push(&solv->solutions, 0);
658 for (j = 0; j < problem.count; j++)
659 {
660 convertsolution(solv, problem.elements[j], &solv->solutions);
661 if (solv->solutions.count > solstart + 1)
662 break;
663 }
664 if (solv->solutions.count == solstart + 1)
665 {
666 solv->solutions.count--;
667 continue; /* sorry */
668 }
669 }
670 /* patch in number of solution elements */
671 solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;
672 queue_push(&solv->solutions, 0); /* add end marker */
673 queue_push(&solv->solutions, 0); /* add end marker */
674 queue_push(&solv->solutions, problem.elements[i]); /* just for bookkeeping */
675 queue_push(&solv->solutions, extraflags & SOLVER_CLEANDEPS); /* our extraflags */
676 solv->solutions.elements[solidx + 1 + nsol++] = solstart;
677 }
678 solv->solutions.elements[solidx + 1 + nsol] = 0; /* end marker */
679 solv->solutions.elements[solidx] = nsol;
680 queue_free(&problem);
681 queue_free(&solution);
682
683 /* restore decisions */
684 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
685 queue_empty(&solv->decisionq);
686 queue_empty(&solv->decisionq_why);
687 for (i = 0; i < redoq.count; i += 3)
688 {
689 Id p = redoq.elements[i];
690 queue_push(&solv->decisionq, p);
691 queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
692 solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
693 }
694 queue_free(&redoq);
695 /* restore problems */
696 queue_free(&solv->problems);
697 solv->problems = problems_save;
698
699 if (solv->cleandeps_mistakes)
700 {
701 if (oldmistakes)
702 queue_truncate(solv->cleandeps_mistakes, oldmistakes);
703 else
704 {
705 queue_free(solv->cleandeps_mistakes);
706 solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
707 }
708 }
709
710 POOL_DEBUG(SOLV_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, solv_timems(now));
711 }
712
713
714 /**************************************************************************/
715
716 unsigned int
solver_problem_count(Solver * solv)717 solver_problem_count(Solver *solv)
718 {
719 return solv->problems.count / 2;
720 }
721
722 Id
solver_next_problem(Solver * solv,Id problem)723 solver_next_problem(Solver *solv, Id problem)
724 {
725 if (!problem)
726 return solv->problems.count ? 1 : 0;
727 return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0;
728 }
729
730 unsigned int
solver_solution_count(Solver * solv,Id problem)731 solver_solution_count(Solver *solv, Id problem)
732 {
733 Id solidx = solv->problems.elements[problem * 2 - 1];
734 if (solv->solutions.elements[solidx] < 0)
735 create_solutions(solv, problem, solidx);
736 return solv->solutions.elements[solidx];
737 }
738
739 Id
solver_next_solution(Solver * solv,Id problem,Id solution)740 solver_next_solution(Solver *solv, Id problem, Id solution)
741 {
742 Id solidx = solv->problems.elements[problem * 2 - 1];
743 if (solv->solutions.elements[solidx] < 0)
744 create_solutions(solv, problem, solidx);
745 return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0;
746 }
747
748 unsigned int
solver_solutionelement_count(Solver * solv,Id problem,Id solution)749 solver_solutionelement_count(Solver *solv, Id problem, Id solution)
750 {
751 Id solidx = solv->problems.elements[problem * 2 - 1];
752 solidx = solv->solutions.elements[solidx + solution];
753 return solv->solutions.elements[solidx];
754 }
755
756 Id
solver_solutionelement_internalid(Solver * solv,Id problem,Id solution)757 solver_solutionelement_internalid(Solver *solv, Id problem, Id solution)
758 {
759 Id solidx = solv->problems.elements[problem * 2 - 1];
760 solidx = solv->solutions.elements[solidx + solution];
761 return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 3];
762 }
763
764 Id
solver_solutionelement_extrajobflags(Solver * solv,Id problem,Id solution)765 solver_solutionelement_extrajobflags(Solver *solv, Id problem, Id solution)
766 {
767 Id solidx = solv->problems.elements[problem * 2 - 1];
768 solidx = solv->solutions.elements[solidx + solution];
769 return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 4];
770 }
771
772
773 /*
774 * return the next item of the proposed solution
775 * here are the possibilities for p / rp and what
776 * the solver expects the application to do:
777 * p rp
778 * -------------------------------------------------------
779 * SOLVER_SOLUTION_INFARCH pkgid
780 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
781 * SOLVER_SOLUTION_DISTUPGRADE pkgid
782 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
783 * SOLVER_SOLUTION_BEST pkgid
784 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
785 * SOLVER_SOLUTION_JOB jobidx
786 * -> remove job (jobidx - 1, jobidx) from job queue
787 * SOLVER_SOLUTION_POOLJOB jobidx
788 * -> remove job (jobidx - 1, jobidx) from pool job queue
789 * pkgid (> 0) 0
790 * -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
791 * pkgid (> 0) pkgid (> 0)
792 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
793 * (this will replace package p)
794 *
795 * Thus, the solver will either ask the application to remove
796 * a specific job from the job queue, or ask to add an install/erase
797 * job to it.
798 *
799 */
800
801 Id
solver_next_solutionelement(Solver * solv,Id problem,Id solution,Id element,Id * p,Id * rp)802 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
803 {
804 Id solidx = solv->problems.elements[problem * 2 - 1];
805 solidx = solv->solutions.elements[solidx + solution];
806 if (!solidx)
807 return 0;
808 solidx += 1 + element * 2;
809 if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
810 return 0;
811 *p = solv->solutions.elements[solidx];
812 *rp = solv->solutions.elements[solidx + 1];
813 return element + 1;
814 }
815
816 void
solver_take_solutionelement(Solver * solv,Id p,Id rp,Id extrajobflags,Queue * job)817 solver_take_solutionelement(Solver *solv, Id p, Id rp, Id extrajobflags, Queue *job)
818 {
819 int i;
820
821 if (p == SOLVER_SOLUTION_POOLJOB)
822 {
823 solv->pool->pooljobs.elements[rp - 1] = SOLVER_NOOP;
824 solv->pool->pooljobs.elements[rp] = 0;
825 return;
826 }
827 if (p == SOLVER_SOLUTION_JOB)
828 {
829 job->elements[rp - 1] = SOLVER_NOOP;
830 job->elements[rp] = 0;
831 return;
832 }
833 if (rp <= 0 && p <= 0)
834 return; /* just in case */
835 if (rp > 0)
836 p = SOLVER_INSTALL|SOLVER_SOLVABLE|extrajobflags;
837 else
838 {
839 rp = p;
840 p = SOLVER_ERASE|SOLVER_SOLVABLE|extrajobflags;
841 }
842 for (i = 0; i < job->count; i += 2)
843 if (job->elements[i] == p && job->elements[i + 1] == rp)
844 return;
845 queue_push2(job, p, rp);
846 }
847
848 void
solver_take_solution(Solver * solv,Id problem,Id solution,Queue * job)849 solver_take_solution(Solver *solv, Id problem, Id solution, Queue *job)
850 {
851 Id p, rp, element = 0;
852 Id extrajobflags = solver_solutionelement_extrajobflags(solv, problem, solution);
853 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
854 solver_take_solutionelement(solv, p, rp, extrajobflags, job);
855 }
856
857
858 /*-------------------------------------------------------------------
859 *
860 * find problem rule
861 */
862
863 static void
findproblemrule_internal(Solver * solv,Id idx,Id * reqrp,Id * conrp,Id * sysrp,Id * jobrp,Map * rseen)864 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp, Map *rseen)
865 {
866 Id rid, d;
867 Id lreqr, lconr, lsysr, ljobr;
868 Rule *r;
869 Id jobassert = 0;
870 int i, reqset = 0; /* 0: unset, 1: installed, 2: jobassert, 3: assert */
871
872 /* find us a jobassert rule */
873 for (i = idx; (rid = solv->learnt_pool.elements[i]) != 0; i++)
874 {
875 if (rid < solv->jobrules || rid >= solv->jobrules_end)
876 continue;
877 r = solv->rules + rid;
878 d = r->d < 0 ? -r->d - 1 : r->d;
879 if (!d && r->w2 == 0 && r->p > 0)
880 {
881 jobassert = r->p;
882 break;
883 }
884 }
885
886 /* the problem rules are somewhat ordered from "near to the problem" to
887 * "near to the job" */
888 lreqr = lconr = lsysr = ljobr = 0;
889 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
890 {
891 assert(rid > 0);
892 if (rid >= solv->learntrules)
893 {
894 if (MAPTST(rseen, rid - solv->learntrules))
895 continue;
896 MAPSET(rseen, rid - solv->learntrules);
897 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr, rseen);
898 }
899 else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end) || (rid >= solv->bestrules && rid < solv->bestrules_end))
900 {
901 if (!*jobrp)
902 *jobrp = rid;
903 }
904 else if (rid >= solv->updaterules && rid < solv->updaterules_end)
905 {
906 if (!*sysrp)
907 *sysrp = rid;
908 }
909 else
910 {
911 assert(rid < solv->rpmrules_end);
912 r = solv->rules + rid;
913 d = r->d < 0 ? -r->d - 1 : r->d;
914 if (!d && r->w2 < 0)
915 {
916 if (!*conrp)
917 *conrp = rid;
918 }
919 else
920 {
921 if (!d && r->w2 == 0 && reqset < 3)
922 {
923 if (*reqrp > 0 && r->p < -1)
924 {
925 Id op = -solv->rules[*reqrp].p;
926 if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
927 continue; /* different arch, skip */
928 }
929 /* prefer assertions */
930 *reqrp = rid;
931 reqset = 3;
932 }
933 else if (jobassert && r->p == -jobassert)
934 {
935 /* prefer rules of job assertions */
936 *reqrp = rid;
937 reqset = 2;
938 }
939 else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && reqset <= 1)
940 {
941 /* prefer rules of job installed package so that the user doesn't get confused by strange packages */
942 *reqrp = rid;
943 reqset = 1;
944 }
945 else if (!*reqrp)
946 *reqrp = rid;
947 }
948 }
949 }
950 if (!*reqrp && lreqr)
951 *reqrp = lreqr;
952 if (!*conrp && lconr)
953 *conrp = lconr;
954 if (!*jobrp && ljobr)
955 *jobrp = ljobr;
956 if (!*sysrp && lsysr)
957 *sysrp = lsysr;
958 }
959
960 /*
961 * find problem rule
962 *
963 * search for a rule that describes the problem to the
964 * user. Actually a pretty hopeless task that may leave the user
965 * puzzled. To get all of the needed information use
966 * solver_findallproblemrules() instead.
967 */
968
969 Id
solver_findproblemrule(Solver * solv,Id problem)970 solver_findproblemrule(Solver *solv, Id problem)
971 {
972 Id reqr, conr, sysr, jobr;
973 Id idx = solv->problems.elements[2 * problem - 2];
974 Map rseen;
975 reqr = conr = sysr = jobr = 0;
976 map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
977 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr, &rseen);
978 map_free(&rseen);
979 if (reqr)
980 return reqr; /* some requires */
981 if (conr)
982 return conr; /* some conflict */
983 if (sysr)
984 return sysr; /* an update rule */
985 if (jobr)
986 return jobr; /* a user request */
987 assert(0);
988 return 0;
989 }
990
991 /*-------------------------------------------------------------------*/
992
993 static void
findallproblemrules_internal(Solver * solv,Id idx,Queue * rules,Map * rseen)994 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules, Map *rseen)
995 {
996 Id rid;
997 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
998 {
999 if (rid >= solv->learntrules)
1000 {
1001 if (MAPTST(rseen, rid - solv->learntrules))
1002 continue;
1003 MAPSET(rseen, rid - solv->learntrules);
1004 findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules, rseen);
1005 continue;
1006 }
1007 queue_pushunique(rules, rid);
1008 }
1009 }
1010
1011 /*
1012 * find all problem rule
1013 *
1014 * return all rules that lead to the problem. This gives the user
1015 * all of the information to understand the problem, but the result
1016 * can be a large number of rules.
1017 */
1018
1019 void
solver_findallproblemrules(Solver * solv,Id problem,Queue * rules)1020 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
1021 {
1022 Map rseen;
1023 queue_empty(rules);
1024 map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1025 findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules, &rseen);
1026 map_free(&rseen);
1027 }
1028
1029 /* EOF */
1030