Merge branch 'master' of git@git.opensuse.org:projects/zypp/sat-solver
[platform/upstream/libsolv.git] / src / problems.c
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 "bitmap.h"
21 #include "pool.h"
22 #include "util.h"
23 #include "evr.h"
24 #include "solverdebug.h"
25
26
27 /**********************************************************************************/
28
29 /* a problem is an item on the solver's problem list. It can either be >0, in that
30  * case it is a update/infarch/dup rule, or it can be <0, which makes it refer to a job
31  * consisting of multiple job rules.
32  */
33
34 void
35 solver_disableproblem(Solver *solv, Id v)
36 {
37   Rule *r;
38   int i;
39   Id *jp;
40
41   if (v > 0)
42     {
43       if (v >= solv->infarchrules && v < solv->infarchrules_end)
44         {
45           Pool *pool = solv->pool;
46           Id name = pool->solvables[-solv->rules[v].p].name;
47           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
48             v--;
49           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
50             solver_disablerule(solv, solv->rules + v);
51           return;
52         }
53       if (v >= solv->duprules && v < solv->duprules_end)
54         {
55           Pool *pool = solv->pool;
56           Id name = pool->solvables[-solv->rules[v].p].name;
57           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
58             v--;
59           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
60             solver_disablerule(solv, solv->rules + v);
61           return;
62         }
63       solver_disablerule(solv, solv->rules + v);
64 #if 0
65       /* XXX: doesn't work */
66       if (v >= solv->updaterules && v < solv->updaterules_end)
67         {
68           /* enable feature rule if we disabled the update rule */
69           r = solv->rules + (v - solv->updaterules + solv->featurerules);
70           if (r->p)
71             solver_enablerule(solv, r);
72         }
73 #endif
74       return;
75     }
76   v = -(v + 1);
77   jp = solv->ruletojob.elements;
78   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
79     if (*jp == v)
80       solver_disablerule(solv, r);
81 }
82
83 /*-------------------------------------------------------------------
84  * enableproblem
85  */
86
87 void
88 solver_enableproblem(Solver *solv, Id v)
89 {
90   Rule *r;
91   int i;
92   Id *jp;
93
94   if (v > 0)
95     {
96       if (v >= solv->infarchrules && v < solv->infarchrules_end)
97         {
98           Pool *pool = solv->pool;
99           Id name = pool->solvables[-solv->rules[v].p].name;
100           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
101             v--;
102           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
103             solver_enablerule(solv, solv->rules + v);
104           return;
105         }
106       if (v >= solv->duprules && v < solv->duprules_end)
107         {
108           Pool *pool = solv->pool;
109           Id name = pool->solvables[-solv->rules[v].p].name;
110           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
111             v--;
112           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
113             solver_enablerule(solv, solv->rules + v);
114           return;
115         }
116       if (v >= solv->featurerules && v < solv->featurerules_end)
117         {
118           /* do not enable feature rule if update rule is enabled */
119           r = solv->rules + (v - solv->featurerules + solv->updaterules);
120           if (r->d >= 0)
121             return;
122         }
123       solver_enablerule(solv, solv->rules + v);
124       if (v >= solv->updaterules && v < solv->updaterules_end)
125         {
126           /* disable feature rule when enabling update rule */
127           r = solv->rules + (v - solv->updaterules + solv->featurerules);
128           if (r->p)
129             solver_disablerule(solv, r);
130         }
131       return;
132     }
133   v = -(v + 1);
134   jp = solv->ruletojob.elements;
135   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
136     if (*jp == v)
137       solver_enablerule(solv, r);
138 }
139
140
141 /*-------------------------------------------------------------------
142  * enable weak rules
143  * 
144  * Reenable all disabled weak rules (marked in weakrulemap)
145  * 
146  */
147
148 static void
149 enableweakrules(Solver *solv)
150 {
151   int i;
152   Rule *r;
153
154   for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
155     {
156       if (r->d >= 0) /* already enabled? */
157         continue;
158       if (!MAPTST(&solv->weakrulemap, i))
159         continue;
160       solver_enablerule(solv, r);
161     }
162 }
163
164
165 /*-------------------------------------------------------------------
166  * 
167  * refine_suggestion
168  * 
169  * at this point, all rules that led to conflicts are disabled.
170  * we re-enable all rules of a problem set but rule "sug", then
171  * continue to disable more rules until there as again a solution.
172  */
173
174 /* FIXME: think about conflicting assertions */
175
176 static void
177 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok)
178 {
179   Pool *pool = solv->pool;
180   int i, j;
181   Id v;
182   Queue disabled;
183   int disabledcnt;
184
185   IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
186     {
187       POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
188       for (i = 0; problem[i]; i++)
189         {
190           if (problem[i] == sug)
191             POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
192           solver_printproblem(solv, problem[i]);
193         }
194     }
195   queue_empty(refined);
196   if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0)
197     return;
198   queue_init(&disabled);
199   queue_push(refined, sug);
200
201   /* re-enable all problem rules with the exception of "sug"(gestion) */
202   solver_reset(solv);
203
204   for (i = 0; problem[i]; i++)
205     if (problem[i] != sug)
206       solver_enableproblem(solv, problem[i]);
207
208   if (sug < 0)
209     solver_reenablepolicyrules(solv, -(sug + 1));
210   else if (sug >= solv->updaterules && sug < solv->updaterules_end)
211     {
212       /* enable feature rule */
213       Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
214       if (r->p)
215         solver_enablerule(solv, r);
216     }
217
218   enableweakrules(solv);
219
220   for (;;)
221     {
222       int njob, nfeature, nupdate;
223       queue_empty(&solv->problems);
224       solver_reset(solv);
225
226       if (!solv->problems.count)
227         solver_run_sat(solv, 0, 0);
228
229       if (!solv->problems.count)
230         {
231           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
232           IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
233             solver_printdecisions(solv);
234           break;                /* great, no more problems */
235         }
236       disabledcnt = disabled.count;
237       /* start with 1 to skip over proof index */
238       njob = nfeature = nupdate = 0;
239       for (i = 1; i < solv->problems.count - 1; i++)
240         {
241           /* ignore solutions in refined */
242           v = solv->problems.elements[i];
243           if (v == 0)
244             break;      /* end of problem reached */
245           for (j = 0; problem[j]; j++)
246             if (problem[j] != sug && problem[j] == v)
247               break;
248           if (problem[j])
249             continue;
250           if (v >= solv->featurerules && v < solv->featurerules_end)
251             nfeature++;
252           else if (v > 0)
253             nupdate++;
254           else
255             {
256               if (!essentialok && (solv->job.elements[-v -1] & SOLVER_ESSENTIAL) != 0)
257                 continue;       /* not that one! */
258               njob++;
259             }
260           queue_push(&disabled, v);
261         }
262       if (disabled.count == disabledcnt)
263         {
264           /* no solution found, this was an invalid suggestion! */
265           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
266           refined->count = 0;
267           break;
268         }
269       if (!njob && nupdate && nfeature)
270         {
271           /* got only update rules, filter out feature rules */
272           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
273           for (i = j = disabledcnt; i < disabled.count; i++)
274             {
275               v = disabled.elements[i];
276               if (v < solv->featurerules || v >= solv->featurerules_end)
277                 disabled.elements[j++] = v;
278             }
279           disabled.count = j;
280           nfeature = 0;
281         }
282       if (disabled.count == disabledcnt + 1)
283         {
284           /* just one suggestion, add it to refined list */
285           v = disabled.elements[disabledcnt];
286           if (!nfeature)
287             queue_push(refined, v);     /* do not record feature rules */
288           solver_disableproblem(solv, v);
289           if (v >= solv->updaterules && v < solv->updaterules_end)
290             {
291               Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
292               if (r->p)
293                 solver_enablerule(solv, r);     /* enable corresponding feature rule */
294             }
295           if (v < 0)
296             solver_reenablepolicyrules(solv, -(v + 1));
297         }
298       else
299         {
300           /* more than one solution, disable all */
301           /* do not push anything on refine list, as we do not know which solution to choose */
302           /* thus, the user will get another problem if he selects this solution, where he
303            * can choose the right one */
304           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
305             {
306               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
307               for (i = disabledcnt; i < disabled.count; i++)
308                 solver_printproblem(solv, disabled.elements[i]);
309             }
310           for (i = disabledcnt; i < disabled.count; i++)
311             {
312               v = disabled.elements[i];
313               solver_disableproblem(solv, v);
314               if (v >= solv->updaterules && v < solv->updaterules_end)
315                 {
316                   Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
317                   if (r->p)
318                     solver_enablerule(solv, r);
319                 }
320             }
321         }
322     }
323   /* all done, get us back into the same state as before */
324   /* enable refined rules again */
325   for (i = 0; i < disabled.count; i++)
326     solver_enableproblem(solv, disabled.elements[i]);
327   queue_free(&disabled);
328   /* reset policy rules */
329   for (i = 0; problem[i]; i++)
330     solver_enableproblem(solv, problem[i]);
331   solver_disablepolicyrules(solv);
332   /* disable problem rules again */
333   for (i = 0; problem[i]; i++)
334     solver_disableproblem(solv, problem[i]);
335   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
336 }
337
338
339 /*-------------------------------------------------------------------
340  * sorting helper for problems
341  *
342  * bring update rules before job rules
343  * make essential job rules last
344  */
345
346 static int
347 problems_sortcmp(const void *ap, const void *bp, void *dp)
348 {
349   Queue *job = dp;
350   Id a = *(Id *)ap, b = *(Id *)bp;
351   if (a < 0 && b > 0)
352     return 1;
353   if (a > 0 && b < 0)
354     return -1;
355   if (a < 0 && b < 0)
356     {
357       int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
358       int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
359       int x = af - bf;
360       if (x)
361         return x;
362     }
363   return a - b;
364 }
365
366 /*
367  * convert a solution rule into a job modifier
368  */
369 static void
370 convertsolution(Solver *solv, Id why, Queue *solutionq)
371 {
372   Pool *pool = solv->pool;
373   if (why < 0)
374     {
375       queue_push(solutionq, 0);
376       queue_push(solutionq, -why);
377       return;
378     }
379   if (why >= solv->infarchrules && why < solv->infarchrules_end)
380     {
381       Id p, name;
382       /* infarch rule, find replacement */
383       assert(solv->rules[why].p < 0);
384       name = pool->solvables[-solv->rules[why].p].name;
385       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
386         why--;
387       p = 0;
388       for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
389         if (solv->decisionmap[-solv->rules[why].p] > 0)
390           {
391             p = -solv->rules[why].p;
392             break;
393           }
394       if (!p)
395         return;         /* false alarm */
396       queue_push(solutionq, SOLVER_SOLUTION_INFARCH);
397       queue_push(solutionq, p);
398       return;
399     }
400   if (why >= solv->duprules && why < solv->duprules_end)
401     {
402       Id p, name;
403       /* dist upgrade rule, find replacement */
404       assert(solv->rules[why].p < 0);
405       name = pool->solvables[-solv->rules[why].p].name;
406       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
407         why--;
408       p = 0;
409       for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
410         if (solv->decisionmap[-solv->rules[why].p] > 0)
411           {
412             p = -solv->rules[why].p;
413             break;
414           }
415       if (!p)
416         return;         /* false alarm */
417       queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
418       queue_push(solutionq, p);
419       return;
420     }
421   if (why >= solv->updaterules && why < solv->updaterules_end)
422     {
423       /* update rule, find replacement package */
424       Id p, *dp, rp = 0;
425       Rule *rr;
426
427       assert(why >= solv->updaterules && why < solv->updaterules_end);
428       /* check if this is a false positive, i.e. the update rule is fulfilled */
429       rr = solv->rules + why;
430       FOR_RULELITERALS(p, dp, rr)
431         if (p > 0 && solv->decisionmap[p] > 0)
432           break;
433       if (p)
434         return;         /* false alarm */
435
436       p = solv->installed->start + (why - solv->updaterules);
437       rr = solv->rules + solv->featurerules + (why - solv->updaterules);
438       if (!rr->p)
439         rr = solv->rules + why;
440       if (solv->distupgrade && solv->rules[why].p != p && solv->decisionmap[p] > 0)
441         {
442           /* distupgrade case, allow to keep old package */
443           queue_push(solutionq, p);
444           queue_push(solutionq, p);
445           return;
446         }
447       if (solv->decisionmap[p] > 0)
448         return;         /* false alarm, turned out we can keep the package */
449       if (rr->w2)
450         {
451           int mvrp = 0;         /* multi-version replacement */
452           FOR_RULELITERALS(rp, dp, rr)
453             {
454               if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
455                 {
456                   mvrp = rp;
457                   if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp)))
458                     break;
459                 }
460             }
461           if (!rp && mvrp)
462             {
463               /* found only multi-version replacements */
464               /* have to split solution into two parts */
465               queue_push(solutionq, p);
466               queue_push(solutionq, mvrp);
467             }
468         }
469       queue_push(solutionq, p);
470       queue_push(solutionq, rp);
471       return;
472     }
473 }
474
475 /*
476  * convert problem data into a form usable for refining.
477  * Returns the number of problems.
478  */
479 int
480 solver_prepare_solutions(Solver *solv)
481 {
482   int i, j = 1, idx = 1;  
483
484   if (!solv->problems.count)
485     return 0;
486   queue_push(&solv->solutions, 0); 
487   queue_push(&solv->solutions, -1); /* unrefined */
488   for (i = 1; i < solv->problems.count; i++) 
489     {   
490       Id p = solv->problems.elements[i];
491       queue_push(&solv->solutions, p); 
492       if (p) 
493         continue;
494       solv->problems.elements[j++] = idx; 
495       if (i + 1 >= solv->problems.count)
496         break;
497       solv->problems.elements[j++] = solv->problems.elements[++i];  /* copy proofidx */
498       idx = solv->solutions.count;
499       queue_push(&solv->solutions, -1); 
500     }   
501   solv->problems.count = j;  
502   return j / 2;
503 }
504
505 /*
506  * refine the simple solution rule list provided by
507  * the solver into multiple lists of job modifiers.
508  */
509 static void
510 create_solutions(Solver *solv, int probnr, int solidx)
511 {
512   Pool *pool = solv->pool;
513   Queue redoq;
514   Queue problem, solution, problems_save;
515   int i, j, nsol;
516   int essentialok;
517   int recocount;
518   unsigned int now;
519
520   now = sat_timems(0);
521   recocount = solv->recommendations.count;
522   solv->recommendations.count = 0;      /* so that revert() doesn't mess with it later */
523   queue_init(&redoq);
524   /* save decisionq, decisionq_why, decisionmap */
525   for (i = 0; i < solv->decisionq.count; i++)
526     {
527       Id p = solv->decisionq.elements[i];
528       queue_push(&redoq, p);
529       queue_push(&redoq, solv->decisionq_why.elements[i]);
530       queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
531     }
532   /* save problems queue */
533   problems_save = solv->problems;
534   memset(&solv->problems, 0, sizeof(solv->problems));
535
536   /* extract problem from queue */
537   queue_init(&problem);
538   for (i = solidx + 1; i < solv->solutions.count; i++)
539     {
540       Id v = solv->solutions.elements[i];
541       if (!v)
542         break;
543       queue_push(&problem, v);
544     }
545   if (problem.count > 1)
546     sat_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);
547   queue_push(&problem, 0);      /* mark end for refine_suggestion */
548   problem.count--;
549 #if 0
550   for (i = 0; i < problem.count; i++)
551     printf("PP %d %d\n", i, problem.elements[i]);
552 #endif
553
554   /* refine each solution element */
555   nsol = 0;
556   essentialok = 0;
557   queue_init(&solution);
558   for (i = 0; i < problem.count; i++)
559     {
560       int solstart = solv->solutions.count;
561       refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok);
562       queue_push(&solv->solutions, 0);  /* reserve room for number of elements */
563       for (j = 0; j < solution.count; j++)
564         convertsolution(solv, solution.elements[j], &solv->solutions);
565       if (solv->solutions.count == solstart + 1)
566         {
567           solv->solutions.count--;
568           if (!essentialok && i + 1 == problem.count && !nsol)
569             {
570               /* nothing found, start over */
571               essentialok = 1;
572               i = -1;
573             }
574           continue;
575         }
576       /* patch in number of solution elements */
577       solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;
578       queue_push(&solv->solutions, 0);  /* add end marker */
579       queue_push(&solv->solutions, 0);  /* add end marker */
580       solv->solutions.elements[solidx + 1 + nsol++] = solstart;
581     }
582   solv->solutions.elements[solidx + 1 + nsol] = 0;      /* end marker */
583   solv->solutions.elements[solidx] = nsol;
584   queue_free(&problem);
585   queue_free(&solution);
586
587   /* restore decisions */
588   memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
589   queue_empty(&solv->decisionq);
590   queue_empty(&solv->decisionq_why);
591   for (i = 0; i < redoq.count; i += 3)
592     {
593       Id p = redoq.elements[i];
594       queue_push(&solv->decisionq, p);
595       queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
596       solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
597     }
598   solv->recommendations.count = recocount;
599   queue_free(&redoq);
600   /* restore problems */
601   queue_free(&solv->problems);
602   solv->problems = problems_save;
603   POOL_DEBUG(SAT_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, sat_timems(now));
604 }
605
606
607 /**************************************************************************/
608
609 Id
610 solver_problem_count(Solver *solv)
611 {
612   return solv->problems.count / 2;
613 }
614
615 Id
616 solver_next_problem(Solver *solv, Id problem)
617 {
618   if (!problem)
619     return solv->problems.count ? 1 : 0;
620   return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0;
621 }
622
623 Id
624 solver_solution_count(Solver *solv, Id problem)
625 {
626   Id solidx = solv->problems.elements[problem * 2 - 1];
627   if (solv->solutions.elements[solidx] < 0)
628     create_solutions(solv, problem, solidx);
629   return solv->solutions.elements[solidx];
630 }
631
632 Id
633 solver_next_solution(Solver *solv, Id problem, Id solution)
634 {
635   Id solidx = solv->problems.elements[problem * 2 - 1];
636   if (solv->solutions.elements[solidx] < 0)
637     create_solutions(solv, problem, solidx);
638   return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0;
639 }
640
641 Id
642 solver_solutionelement_count(Solver *solv, Id problem, Id solution)
643 {
644   Id solidx = solv->problems.elements[problem * 2 - 1];
645   solidx = solv->solutions.elements[solidx + solution];
646   return solv->solutions.elements[solidx];
647 }
648
649
650 /*
651  *  return the next item of the proposed solution
652  *  here are the possibilities for p / rp and what
653  *  the solver expects the application to do:
654  *    p                             rp
655  *  -------------------------------------------------------
656  *    SOLVER_SOLUTION_INFARCH       pkgid
657  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
658  *    SOLVER_SOLUTION_DISTUPGRADE   pkgid
659  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
660  *    SOLVER_SOLUTION_JOB           jobidx
661  *    -> remove job (jobidx - 1, jobidx) from job queue
662  *    pkgid (> 0)                   0
663  *    -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
664  *    pkgid (> 0)                   pkgid (> 0)
665  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
666  *       (this will replace package p)
667  *         
668  * Thus, the solver will either ask the application to remove
669  * a specific job from the job queue, or ask to add an install/erase
670  * job to it.
671  *
672  */
673
674 Id
675 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
676 {
677   Id solidx = solv->problems.elements[problem * 2 - 1];
678   solidx = solv->solutions.elements[solidx + solution];
679   if (!solidx)
680     return 0;
681   solidx += 1 + element * 2;
682   if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
683     return 0;
684   *p = solv->solutions.elements[solidx];
685   *rp = solv->solutions.elements[solidx + 1];
686   return element + 1;
687 }
688
689 /*-------------------------------------------------------------------
690  * 
691  * find problem rule
692  */
693
694 static void
695 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
696 {
697   Id rid, d;
698   Id lreqr, lconr, lsysr, ljobr;
699   Rule *r;
700   int reqassert = 0;
701
702   lreqr = lconr = lsysr = ljobr = 0;
703   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
704     {
705       assert(rid > 0);
706       if (rid >= solv->learntrules)
707         findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
708       else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
709         {
710           if (!*jobrp)
711             *jobrp = rid;
712         }
713       else if (rid >= solv->updaterules && rid < solv->updaterules_end)
714         {
715           if (!*sysrp)
716             *sysrp = rid;
717         }
718       else
719         {
720           assert(rid < solv->rpmrules_end);
721           r = solv->rules + rid;
722           d = r->d < 0 ? -r->d - 1 : r->d;
723           if (!d && r->w2 < 0)
724             {
725               if (!*conrp)
726                 *conrp = rid;
727             }
728           else
729             {
730               if (!d && r->w2 == 0 && !reqassert)
731                 {
732                   if (*reqrp > 0 && r->p < -1)
733                     {
734                       Id op = -solv->rules[*reqrp].p;
735                       if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
736                         continue;       /* different arch, skip */
737                     }
738                   /* prefer assertions */
739                   *reqrp = rid;
740                   reqassert = 1;
741                 }
742               if (!*reqrp)
743                 *reqrp = rid;
744               else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && !reqassert)
745                 {
746                   /* prefer rules of installed packages */
747                   *reqrp = rid;
748                 }
749             }
750         }
751     }
752   if (!*reqrp && lreqr)
753     *reqrp = lreqr;
754   if (!*conrp && lconr)
755     *conrp = lconr;
756   if (!*jobrp && ljobr)
757     *jobrp = ljobr;
758   if (!*sysrp && lsysr)
759     *sysrp = lsysr;
760 }
761
762 /* 
763  * find problem rule
764  *
765  * search for a rule that describes the problem to the
766  * user. Actually a pretty hopeless task that may leave the user
767  * puzzled. To get all of the needed information use
768  * solver_findallproblemrules() instead.
769  */
770
771 Id
772 solver_findproblemrule(Solver *solv, Id problem)
773 {
774   Id reqr, conr, sysr, jobr;
775   Id idx = solv->problems.elements[2 * problem - 2];
776   reqr = conr = sysr = jobr = 0;
777   findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
778   if (reqr)
779     return reqr;        /* some requires */
780   if (conr)
781     return conr;        /* some conflict */
782   if (sysr)
783     return sysr;        /* an update rule */
784   if (jobr)
785     return jobr;        /* a user request */
786   assert(0);
787 }
788
789 /*-------------------------------------------------------------------*/
790
791 static void
792 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
793 {
794   Id rid;
795   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
796     {
797       if (rid >= solv->learntrules)
798         {
799           findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
800           continue;
801         }
802       queue_pushunique(rules, rid);
803     }
804 }
805
806 /*
807  * find all problem rule
808  *
809  * return all rules that lead to the problem. This gives the user
810  * all of the information to understand the problem, but the result
811  * can be a large number of rules.
812  */
813
814 void
815 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
816 {
817   queue_empty(rules);
818   findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules);
819 }
820
821 /* obsolete function */
822 SolverRuleinfo
823 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
824 {
825   return solver_ruleinfo(solv, rid, sourcep, targetp, depp);
826 }
827
828 /* EOF */