move stringification functions from solverdebug to more correct places
[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 "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
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
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
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
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
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
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
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
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
717 solver_problem_count(Solver *solv)
718 {
719   return solv->problems.count / 2;
720 }
721
722 Id
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
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
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
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
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
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
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
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
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
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
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
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
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 const char *
1030 solver_problemruleinfo2str(Solver *solv, SolverRuleinfo type, Id source, Id target, Id dep)
1031 {
1032   Pool *pool = solv->pool;
1033   char *s;
1034   switch (type)
1035     {
1036     case SOLVER_RULE_DISTUPGRADE:
1037       return pool_tmpjoin(pool, pool_solvid2str(pool, source), " does not belong to a distupgrade repository", 0);
1038     case SOLVER_RULE_INFARCH:
1039       return pool_tmpjoin(pool, pool_solvid2str(pool, source), " has inferior architecture", 0);
1040     case SOLVER_RULE_UPDATE:
1041       return pool_tmpjoin(pool, "problem with installed package ", pool_solvid2str(pool, source), 0);
1042     case SOLVER_RULE_JOB:
1043       return "conflicting requests";
1044     case SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP:
1045       return pool_tmpjoin(pool, "nothing provides requested ", pool_dep2str(pool, dep), 0);
1046     case SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM:
1047       return pool_tmpjoin(pool, pool_dep2str(pool, dep), " is provided by the system", 0);
1048     case SOLVER_RULE_RPM:
1049       return "some dependency problem";
1050     case SOLVER_RULE_RPM_NOT_INSTALLABLE:
1051       return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " is not installable");
1052     case SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP:
1053       s = pool_tmpjoin(pool, "nothing provides ", pool_dep2str(pool, dep), 0);
1054       return pool_tmpappend(pool, s, " needed by ", pool_solvid2str(pool, source));
1055     case SOLVER_RULE_RPM_SAME_NAME:
1056       s = pool_tmpjoin(pool, "cannot install both ", pool_solvid2str(pool, source), 0);
1057       return pool_tmpappend(pool, s, " and ", pool_solvid2str(pool, target));
1058     case SOLVER_RULE_RPM_PACKAGE_CONFLICT:
1059       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1060       s = pool_tmpappend(pool, s, " conflicts with ", pool_dep2str(pool, dep));
1061       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1062     case SOLVER_RULE_RPM_PACKAGE_OBSOLETES:
1063       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1064       s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
1065       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1066     case SOLVER_RULE_RPM_INSTALLEDPKG_OBSOLETES:
1067       s = pool_tmpjoin(pool, "installed package ", pool_solvid2str(pool, source), 0);
1068       s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
1069       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1070     case SOLVER_RULE_RPM_IMPLICIT_OBSOLETES:
1071       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1072       s = pool_tmpappend(pool, s, " implicitly obsoletes ", pool_dep2str(pool, dep));
1073       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1074     case SOLVER_RULE_RPM_PACKAGE_REQUIRES:
1075       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " requires ");
1076       return pool_tmpappend(pool, s, pool_dep2str(pool, dep), ", but none of the providers can be installed");
1077     case SOLVER_RULE_RPM_SELF_CONFLICT:
1078       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " conflicts with ");
1079       return pool_tmpappend(pool, s, pool_dep2str(pool, dep), " provided by itself");
1080     default:
1081       return "bad problem rule type";
1082     }
1083 }
1084
1085 const char *
1086 solver_solutionelement2str(Solver *solv, Id p, Id rp)
1087 {
1088   Pool *pool = solv->pool;
1089   if (p == SOLVER_SOLUTION_JOB || p == SOLVER_SOLUTION_POOLJOB)
1090     {
1091       Id how, what;
1092       if (p == SOLVER_SOLUTION_JOB)
1093         rp += solv->pooljobcnt;
1094       how = solv->job.elements[rp - 1];
1095       what = solv->job.elements[rp];
1096       return pool_tmpjoin(pool, "do not ask to ", pool_job2str(pool, how, what, 0), 0);
1097     }
1098   else if (p == SOLVER_SOLUTION_INFARCH)
1099     {
1100       Solvable *s = pool->solvables + rp;
1101       if (solv->installed && s->repo == solv->installed)
1102         return pool_tmpjoin(pool, "keep ", pool_solvable2str(pool, s), " despite the inferior architecture");
1103       else
1104         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the inferior architecture");
1105     }
1106   else if (p == SOLVER_SOLUTION_DISTUPGRADE)
1107     {
1108       Solvable *s = pool->solvables + rp;
1109       if (solv->installed && s->repo == solv->installed)
1110         return pool_tmpjoin(pool, "keep obsolete ", pool_solvable2str(pool, s), 0);
1111       else
1112         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " from excluded repository");
1113     }
1114   else if (p == SOLVER_SOLUTION_BEST)
1115     {
1116       Solvable *s = pool->solvables + rp;
1117       if (solv->installed && s->repo == solv->installed)
1118         return pool_tmpjoin(pool, "keep old ", pool_solvable2str(pool, s), 0);
1119       else
1120         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the old version");
1121     }
1122   else if (p > 0 && rp == 0)
1123     return pool_tmpjoin(pool, "allow deinstallation of ", pool_solvid2str(pool, p), 0);
1124   else if (p > 0 && rp > 0)
1125     {
1126       const char *sp = pool_solvid2str(pool, p);
1127       const char *srp = pool_solvid2str(pool, rp);
1128       const char *str = pool_tmpjoin(pool, "allow replacement of ", sp, 0);
1129       return pool_tmpappend(pool, str, " with ", srp);
1130     }
1131   else
1132     return "bad solution element";
1133 }
1134