fix conflict
[platform/upstream/libsolv.git] / src / rules.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  * rules.c
10  *
11  * SAT based dependency solver
12  */
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <unistd.h>
17 #include <string.h>
18 #include <assert.h>
19
20 #include "solver.h"
21 #include "bitmap.h"
22 #include "pool.h"
23 #include "poolarch.h"
24 #include "util.h"
25 #include "policy.h"
26 #include "solverdebug.h"
27
28 #define RULES_BLOCK 63
29
30 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep);
31
32 /*-------------------------------------------------------------------
33  * Check if dependency is possible
34  * 
35  * mirrors solver_dep_fulfilled but uses map m instead of the decisionmap
36  */
37
38 static inline int
39 dep_possible(Solver *solv, Id dep, Map *m)
40 {
41   Pool *pool = solv->pool;
42   Id p, pp;
43
44   if (ISRELDEP(dep))
45     {
46       Reldep *rd = GETRELDEP(pool, dep);
47       if (rd->flags == REL_AND)
48         {
49           if (!dep_possible(solv, rd->name, m))
50             return 0;
51           return dep_possible(solv, rd->evr, m);
52         }
53       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
54         return solver_splitprovides(solv, rd->evr);
55       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
56         return solver_dep_installed(solv, rd->evr);
57     }
58   FOR_PROVIDES(p, pp, dep)
59     {
60       if (MAPTST(m, p))
61         return 1;
62     }
63   return 0;
64 }
65
66 /********************************************************************
67  *
68  * Rule handling
69  *
70  * - unify rules, remove duplicates
71  */
72
73 /*-------------------------------------------------------------------
74  *
75  * compare rules for unification sort
76  *
77  */
78
79 static int
80 unifyrules_sortcmp(const void *ap, const void *bp, void *dp)
81 {
82   Pool *pool = dp;
83   Rule *a = (Rule *)ap;
84   Rule *b = (Rule *)bp;
85   Id *ad, *bd;
86   int x;
87
88   x = a->p - b->p;
89   if (x)
90     return x;                          /* p differs */
91
92   /* identical p */
93   if (a->d == 0 && b->d == 0)
94     return a->w2 - b->w2;              /* assertion: return w2 diff */
95
96   if (a->d == 0)                       /* a is assertion, b not */
97     {
98       x = a->w2 - pool->whatprovidesdata[b->d];
99       return x ? x : -1;
100     }
101
102   if (b->d == 0)                       /* b is assertion, a not */
103     {
104       x = pool->whatprovidesdata[a->d] - b->w2;
105       return x ? x : 1;
106     }
107
108   /* compare whatprovidesdata */
109   ad = pool->whatprovidesdata + a->d;
110   bd = pool->whatprovidesdata + b->d;
111   while (*bd)
112     if ((x = *ad++ - *bd++) != 0)
113       return x;
114   return *ad;
115 }
116
117 int
118 solver_samerule(Solver *solv, Rule *r1, Rule *r2)
119 {
120   return unifyrules_sortcmp(r1, r2, solv->pool);
121 }
122
123
124 /*-------------------------------------------------------------------
125  *
126  * unify rules
127  * go over all rules and remove duplicates
128  */
129
130 void
131 solver_unifyrules(Solver *solv)
132 {
133   Pool *pool = solv->pool;
134   int i, j;
135   Rule *ir, *jr;
136
137   if (solv->nrules <= 1)               /* nothing to unify */
138     return;
139
140   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
141
142   /* sort rules first */
143   sat_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool);
144
145   /* prune rules
146    * i = unpruned
147    * j = pruned
148    */
149   jr = 0;
150   for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
151     {
152       if (jr && !unifyrules_sortcmp(ir, jr, pool))
153         continue;                      /* prune! */
154       jr = solv->rules + j++;          /* keep! */
155       if (ir != jr)
156         *jr = *ir;
157     }
158
159   /* reduced count from nrules to j rules */
160   POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
161
162   /* adapt rule buffer */
163   solv->nrules = j;
164   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
165
166   /*
167    * debug: log rule statistics
168    */
169   IF_POOLDEBUG (SAT_DEBUG_STATS)
170     {
171       int binr = 0;
172       int lits = 0;
173       Id *dp;
174       Rule *r;
175
176       for (i = 1; i < solv->nrules; i++)
177         {
178           r = solv->rules + i;
179           if (r->d == 0)
180             binr++;
181           else
182             {
183               dp = solv->pool->whatprovidesdata + r->d;
184               while (*dp++)
185                 lits++;
186             }
187         }
188       POOL_DEBUG(SAT_DEBUG_STATS, "  binary: %d\n", binr);
189       POOL_DEBUG(SAT_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
190     }
191   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
192 }
193
194 #if 0
195
196 /*
197  * hash rule
198  */
199
200 static Hashval
201 hashrule(Solver *solv, Id p, Id d, int n)
202 {
203   unsigned int x = (unsigned int)p;
204   int *dp;
205
206   if (n <= 1)
207     return (x * 37) ^ (unsigned int)d;
208   dp = solv->pool->whatprovidesdata + d;
209   while (*dp)
210     x = (x * 37) ^ (unsigned int)*dp++;
211   return x;
212 }
213 #endif
214
215
216 /*-------------------------------------------------------------------
217  * 
218  */
219
220 /*
221  * add rule
222  *  p = direct literal; always < 0 for installed rpm rules
223  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
224  *
225  *
226  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
227  *
228  * p < 0 : pkg id of A
229  * d > 0 : Offset in whatprovidesdata (list of providers of b)
230  *
231  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
232  * p < 0 : pkg id of A
233  * d < 0 : Id of solvable (e.g. B1)
234  *
235  * d == 0: unary rule, assertion => (A) or (-A)
236  *
237  *   Install:    p > 0, d = 0   (A)             user requested install
238  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
239  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
240  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
241  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
242  *                                              also used for obsoletes
243  *   ?:          p > 0, d < 0   (A|-B)          
244  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
245  *
246  *   resulting watches:
247  *   ------------------
248  *   Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
249  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
250  *   every other : w1 = p, w2 = whatprovidesdata[d];
251  *   Disabled rule: w1 = 0
252  *
253  *   always returns a rule for non-rpm rules
254  */
255
256 Rule *
257 solver_addrule(Solver *solv, Id p, Id d)
258 {
259   Pool *pool = solv->pool;
260   Rule *r = 0;
261   Id *dp = 0;
262
263   int n = 0;                           /* number of literals in rule - 1
264                                           0 = direct assertion (single literal)
265                                           1 = binary rule
266                                           >1 = 
267                                         */
268
269   /* it often happenes that requires lead to adding the same rpm rule
270    * multiple times, so we prune those duplicates right away to make
271    * the work for unifyrules a bit easier */
272
273   if (solv->nrules                      /* we already have rules */
274       && !solv->rpmrules_end)           /* but are not done with rpm rules */
275     {
276       r = solv->rules + solv->nrules - 1;   /* get the last added rule */
277       if (r->p == p && r->d == d && d != 0)   /* identical and not user requested */
278         return r;
279     }
280
281     /*
282      * compute number of literals (n) in rule
283      */
284     
285   if (d < 0)
286     {
287       /* always a binary rule */
288       if (p == d)
289         return 0;                      /* ignore self conflict */
290       n = 1;
291     }
292   else if (d > 0)
293     {
294       for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
295         if (*dp == -p)
296           return 0;                     /* rule is self-fulfilling */
297         
298       if (n == 1)   /* have single provider */
299         d = dp[-1];                     /* take single literal */
300     }
301
302   if (n == 1 && p > d && !solv->rpmrules_end)
303     {
304       /* smallest literal first so we can find dups */
305       n = p; p = d; d = n;             /* p <-> d */
306       n = 1;                           /* re-set n, was used as temp var */
307     }
308
309   /*
310    * check for duplicate
311    */
312     
313   /* check if the last added rule (r) is exactly the same as what we're looking for. */
314   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
315     return r;  /* binary rule */
316
317     /* have n-ary rule with same first literal, check other literals */
318   if (r && n > 1 && r->d && r->p == p)
319     {
320       /* Rule where d is an offset in whatprovidesdata */
321       Id *dp2;
322       if (d == r->d)
323         return r;
324       dp2 = pool->whatprovidesdata + r->d;
325       for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
326         if (*dp != *dp2)
327           break;
328       if (*dp == *dp2)
329         return r;
330    }
331
332   /*
333    * allocate new rule
334    */
335
336   /* extend rule buffer */
337   solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
338   r = solv->rules + solv->nrules++;    /* point to rule space */
339
340     /*
341      * r = new rule
342      */
343     
344   r->p = p;
345   if (n == 0)
346     {
347       /* direct assertion, no watch needed */
348       r->d = 0;
349       r->w1 = p;
350       r->w2 = 0;
351     }
352   else if (n == 1)
353     {
354       /* binary rule */
355       r->d = 0;
356       r->w1 = p;
357       r->w2 = d;
358     }
359   else
360     {
361       r->d = d;
362       r->w1 = p;
363       r->w2 = pool->whatprovidesdata[d];
364     }
365   r->n1 = 0;
366   r->n2 = 0;
367
368   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
369     {
370       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "  Add rule: ");
371       solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
372     }
373
374   return r;
375 }
376
377
378 /******************************************************************************
379  ***
380  *** rpm rule part: create rules representing the package dependencies
381  ***
382  ***/
383
384 /*
385  *  special multiversion patch conflict handling:
386  *  a patch conflict is also satisfied, if some other
387  *  version with the same name/arch that doesn't conflict
388  *  get's installed. The generated rule is thus:
389  *  -patch|-cpack|opack1|opack2|...
390  */
391 static Id
392 makemultiversionconflict(Solver *solv, Id n, Id con)
393 {
394   Pool *pool = solv->pool;
395   Solvable *s, *sn;
396   Queue q;
397   Id p, pp, qbuf[64];
398
399   sn = pool->solvables + n;
400   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
401   queue_push(&q, -n);
402   FOR_PROVIDES(p, pp, sn->name)
403     {
404       s = pool->solvables + p;
405       if (s->name != sn->name || s->arch != sn->arch)
406         continue;
407       if (!MAPTST(&solv->noobsoletes, p))
408         continue;
409       if (pool_match_nevr(pool, pool->solvables + p, con))
410         continue;
411       /* here we have a multiversion solvable that doesn't conflict */
412       /* thus we're not in conflict if it is installed */
413       queue_push(&q, p);
414     }
415   if (q.count == 1)
416     return -n;  /* no other package found, generate normal conflict */
417   return pool_queuetowhatprovides(pool, &q);
418 }
419
420 static inline void
421 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep)
422 {
423   if (!solv->ruleinfoq)
424     solver_addrule(solv, p, d);
425   else
426     addrpmruleinfo(solv, p, d, type, dep);
427 }
428
429 /*-------------------------------------------------------------------
430  * 
431  * add (install) rules for solvable
432  * 
433  * s: Solvable for which to add rules
434  * m: m[s] = 1 for solvables which have rules, prevent rule duplication
435  * 
436  * Algorithm: 'visit all nodes of a graph'. The graph nodes are
437  *  solvables, the edges their dependencies.
438  *  Starting from an installed solvable, this will create all rules
439  *  representing the graph created by the solvables dependencies.
440  * 
441  * for unfulfilled requirements, conflicts, obsoletes,....
442  * add a negative assertion for solvables that are not installable
443  * 
444  * It will also create rules for all solvables referenced by 's'
445  *  i.e. descend to all providers of requirements of 's'
446  *
447  */
448
449 void
450 solver_addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
451 {
452   Pool *pool = solv->pool;
453   Repo *installed = solv->installed;
454
455   /* 'work' queue. keeps Ids of solvables we still have to work on.
456      And buffer for it. */
457   Queue workq;
458   Id workqbuf[64];
459     
460   int i;
461     /* if to add rules for broken deps ('rpm -V' functionality)
462      * 0 = yes, 1 = no
463      */
464   int dontfix;
465     /* Id var and pointer for each dependency
466      * (not used in parallel)
467      */
468   Id req, *reqp;
469   Id con, *conp;
470   Id obs, *obsp;
471   Id rec, *recp;
472   Id sug, *sugp;
473   Id p, pp;             /* whatprovides loops */
474   Id *dp;               /* ptr to 'whatprovides' */
475   Id n;                 /* Id for current solvable 's' */
476
477   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
478
479   queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
480   queue_push(&workq, s - pool->solvables);      /* push solvable Id to work queue */
481
482   /* loop until there's no more work left */
483   while (workq.count)
484     {
485       /*
486        * n: Id of solvable
487        * s: Pointer to solvable
488        */
489
490       n = queue_shift(&workq);          /* 'pop' next solvable to work on from queue */
491       if (m)
492         {
493           if (MAPTST(m, n))             /* continue if already visited */
494             continue;
495           MAPSET(m, n);                 /* mark as visited */
496         }
497
498       s = pool->solvables + n;          /* s = Solvable in question */
499
500       dontfix = 0;
501       if (installed                     /* Installed system available */
502           && !solv->fixsystem           /* NOT repair errors in rpm dependency graph */
503           && s->repo == installed       /* solvable is installed */
504           && (!solv->fixmap.size || !MAPTST(&solv->fixmap, n - installed->start)))
505         {
506           dontfix = 1;                  /* dont care about broken rpm deps */
507         }
508
509       if (!dontfix
510           && s->arch != ARCH_SRC
511           && s->arch != ARCH_NOSRC
512           && !pool_installable(pool, s))
513         {
514           POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
515           addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0);
516         }
517
518       /* yet another SUSE hack, sigh */
519       if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8))
520         {
521           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
522           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
523             {
524               addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n));
525               addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy)); 
526               if (m && !MAPTST(m, buddy))
527                 queue_push(&workq, buddy);
528             }
529         }
530
531       /*-----------------------------------------
532        * check requires of s
533        */
534
535       if (s->requires)
536         {
537           reqp = s->repo->idarraydata + s->requires;
538           while ((req = *reqp++) != 0)            /* go through all requires */
539             {
540               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
541                 continue;
542
543               /* find list of solvables providing 'req' */
544               dp = pool_whatprovides_ptr(pool, req);
545
546               if (*dp == SYSTEMSOLVABLE)          /* always installed */
547                 continue;
548
549               if (dontfix)
550                 {
551                   /* the strategy here is to not insist on dependencies
552                    * that are already broken. so if we find one provider
553                    * that was already installed, we know that the
554                    * dependency was not broken before so we enforce it */
555                  
556                   /* check if any of the providers for 'req' is installed */
557                   for (i = 0; (p = dp[i]) != 0; i++)
558                     {
559                       if (pool->solvables[p].repo == installed)
560                         break;          /* provider was installed */
561                     }
562                   /* didn't find an installed provider: previously broken dependency */
563                   if (!p)
564                     {
565                       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
566                       continue;
567                     }
568                 }
569
570               if (!*dp)
571                 {
572                   /* nothing provides req! */
573                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
574                   addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req);
575                   continue;
576                 }
577
578               IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
579                 {
580                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION,"  %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
581                   for (i = 0; dp[i]; i++)
582                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", solvid2str(pool, dp[i]));
583                 }
584
585               /* add 'requires' dependency */
586               /* rule: (-requestor|provider1|provider2|...|providerN) */
587               addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req);
588
589               /* descend the dependency tree
590                  push all non-visited providers on the work queue */
591               if (m)
592                 {
593                   for (; *dp; dp++)
594                     {
595                       if (!MAPTST(m, *dp))
596                         queue_push(&workq, *dp);
597                     }
598                 }
599
600             } /* while, requirements of n */
601
602         } /* if, requirements */
603
604       /* that's all we check for src packages */
605       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
606         continue;
607
608       /*-----------------------------------------
609        * check conflicts of s
610        */
611
612       if (s->conflicts)
613         {
614           int ispatch = 0;
615
616           /* we treat conflicts in patches a bit differen:
617            * - nevr matching
618            * - multiversion handling
619            * XXX: we should really handle this different, looking
620            * at the name is a bad hack
621            */
622           if (!strncmp("patch:", id2str(pool, s->name), 6))
623             ispatch = 1;
624           conp = s->repo->idarraydata + s->conflicts;
625           /* foreach conflicts of 's' */
626           while ((con = *conp++) != 0)
627             {
628               /* foreach providers of a conflict of 's' */
629               FOR_PROVIDES(p, pp, con)
630                 {
631                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
632                     continue;
633                   /* dontfix: dont care about conflicts with already installed packs */
634                   if (dontfix && pool->solvables[p].repo == installed)
635                     continue;
636                   /* p == n: self conflict */
637                   if (p == n && !pool->allowselfconflicts)
638                     {
639                       if (ISRELDEP(con))
640                         {
641                           Reldep *rd = GETRELDEP(pool, con);
642                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
643                             continue;
644                         }
645                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
646                     }
647                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
648                     {
649                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
650                       p = -makemultiversionconflict(solv, p, con);
651                     }
652                  /* rule: -n|-p: either solvable _or_ provider of conflict */
653                   addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con);
654                 }
655             }
656         }
657
658       /*-----------------------------------------
659        * check obsoletes if not installed
660        * (only installation will trigger the obsoletes in rpm)
661        */
662       if (!installed || pool->solvables[n].repo != installed)
663         {                              /* not installed */
664           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
665           if (s->obsoletes && !noobs)
666             {
667               obsp = s->repo->idarraydata + s->obsoletes;
668               /* foreach obsoletes */
669               while ((obs = *obsp++) != 0)
670                 {
671                   /* foreach provider of an obsoletes of 's' */ 
672                   FOR_PROVIDES(p, pp, obs)
673                     {
674                       Solvable *ps = pool->solvables + p;
675                       if (!pool->obsoleteusesprovides /* obsoletes are matched names, not provides */
676                           && !pool_match_nevr(pool, ps, obs))
677                         continue;
678                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
679                         continue;
680                       addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs);
681                     }
682                 }
683             }
684           FOR_PROVIDES(p, pp, s->name)
685             {
686               Solvable *ps = pool->solvables + p;
687               /* we still obsolete packages with same nevra, like rpm does */
688               /* (actually, rpm mixes those packages. yuck...) */
689               if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
690                 continue;
691               if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
692                 continue;
693               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
694                 continue;
695               if (s->name == ps->name)
696                 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0);
697               else
698                 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name);
699             }
700         }
701
702       /*-----------------------------------------
703        * add recommends to the work queue
704        */
705       if (s->recommends && m)
706         {
707           recp = s->repo->idarraydata + s->recommends;
708           while ((rec = *recp++) != 0)
709             {
710               FOR_PROVIDES(p, pp, rec)
711                 if (!MAPTST(m, p))
712                   queue_push(&workq, p);
713             }
714         }
715       if (s->suggests && m)
716         {
717           sugp = s->repo->idarraydata + s->suggests;
718           while ((sug = *sugp++) != 0)
719             {
720               FOR_PROVIDES(p, pp, sug)
721                 if (!MAPTST(m, p))
722                   queue_push(&workq, p);
723             }
724         }
725     }
726   queue_free(&workq);
727   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
728 }
729
730
731 /*-------------------------------------------------------------------
732  * 
733  * Add package rules for weak rules
734  *
735  * m: visited solvables
736  */
737
738 void
739 solver_addrpmrulesforweak(Solver *solv, Map *m)
740 {
741   Pool *pool = solv->pool;
742   Solvable *s;
743   Id sup, *supp;
744   int i, n;
745
746   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
747     /* foreach solvable in pool */
748   for (i = n = 1; n < pool->nsolvables; i++, n++)
749     {
750       if (i == pool->nsolvables)                /* wrap i */
751         i = 1;
752       if (MAPTST(m, i))                         /* been there */
753         continue;
754
755       s = pool->solvables + i;
756       if (!pool_installable(pool, s))           /* only look at installable ones */
757         continue;
758
759       sup = 0;
760       if (s->supplements)
761         {
762           /* find possible supplements */
763           supp = s->repo->idarraydata + s->supplements;
764           while ((sup = *supp++) != ID_NULL)
765             if (dep_possible(solv, sup, m))
766               break;
767         }
768
769       /* if nothing found, check for enhances */
770       if (!sup && s->enhances)
771         {
772           supp = s->repo->idarraydata + s->enhances;
773           while ((sup = *supp++) != ID_NULL)
774             if (dep_possible(solv, sup, m))
775               break;
776         }
777       /* if nothing found, goto next solvables */
778       if (!sup)
779         continue;
780       solver_addrpmrulesforsolvable(solv, s, m);
781       n = 0;                    /* check all solvables again */
782     }
783   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
784 }
785
786
787 /*-------------------------------------------------------------------
788  * 
789  * add package rules for possible updates
790  * 
791  * s: solvable
792  * m: map of already visited solvables
793  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
794  */
795
796 void
797 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
798 {
799   Pool *pool = solv->pool;
800   int i;
801     /* queue and buffer for it */
802   Queue qs;
803   Id qsbuf[64];
804
805   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
806
807   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
808     /* find update candidates for 's' */
809   policy_findupdatepackages(solv, s, &qs, allow_all);
810     /* add rule for 's' if not already done */
811   if (!MAPTST(m, s - pool->solvables))
812     solver_addrpmrulesforsolvable(solv, s, m);
813     /* foreach update candidate, add rule if not already done */
814   for (i = 0; i < qs.count; i++)
815     if (!MAPTST(m, qs.elements[i]))
816       solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
817   queue_free(&qs);
818
819   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
820 }
821
822
823 /***********************************************************************
824  ***
825  ***  Update/Feature rule part
826  ***
827  ***  Those rules make sure an installed package isn't silently deleted
828  ***
829  ***/
830
831 static Id
832 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
833 {
834   Pool *pool = solv->pool;
835   int i;
836
837   policy_findupdatepackages(solv, s, qs, allow_all);
838   if (!qs->count)
839     {
840       if (allow_all)
841         return 0;       /* orphaned, don't create feature rule */
842       /* check if this is an orphaned package */
843       policy_findupdatepackages(solv, s, qs, 1);
844       if (!qs->count)
845         return 0;       /* orphaned, don't create update rule */
846       qs->count = 0;
847       return -SYSTEMSOLVABLE;   /* supported but not installable */
848     }
849   if (allow_all)
850     return s - pool->solvables;
851   /* check if it is ok to keep the installed package */
852   for (i = 0; i < qs->count; i++)
853     {
854       Solvable *ns = pool->solvables + qs->elements[i];
855       if (s->evr == ns->evr && solvable_identical(s, ns))
856         return s - pool->solvables;
857     }
858   /* nope, it must be some other package */
859   return -SYSTEMSOLVABLE;
860 }
861
862 /* add packages from the dup repositories to the update candidates
863  * this isn't needed for the global dup mode as all packages are
864  * from dup repos in that case */
865 static void
866 addduppackages(Solver *solv, Solvable *s, Queue *qs)
867 {
868   Queue dupqs;
869   Id p, dupqsbuf[64];
870   int i;
871   int oldnoupdateprovide = solv->noupdateprovide;
872
873   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
874   solv->noupdateprovide = 1;
875   policy_findupdatepackages(solv, s, &dupqs, 2);
876   solv->noupdateprovide = oldnoupdateprovide;
877   for (i = 0; i < dupqs.count; i++)
878     {
879       p = dupqs.elements[i];
880       if (MAPTST(&solv->dupmap, p))
881         queue_pushunique(qs, p);
882     }
883   queue_free(&dupqs);
884 }
885
886 /*-------------------------------------------------------------------
887  * 
888  * add rule for update
889  *   (A|A1|A2|A3...)  An = update candidates for A
890  *
891  * s = (installed) solvable
892  */
893
894 void
895 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all)
896 {
897   /* installed packages get a special upgrade allowed rule */
898   Pool *pool = solv->pool;
899   Id p, d;
900   Queue qs;
901   Id qsbuf[64];
902
903   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule -----\n");
904   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
905   p = s - pool->solvables;
906   /* find update candidates for 's' */
907   if (solv->distupgrade)
908     p = finddistupgradepackages(solv, s, &qs, allow_all);
909   else
910     policy_findupdatepackages(solv, s, &qs, allow_all);
911   if (!allow_all && !solv->distupgrade && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
912     addduppackages(solv, s, &qs);
913
914   if (!allow_all && qs.count && solv->noobsoletes.size)
915     {
916       int i, j;
917
918       d = pool_queuetowhatprovides(pool, &qs);
919       /* filter out all noobsoletes packages as they don't update */
920       for (i = j = 0; i < qs.count; i++)
921         {
922           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
923             {
924               /* it's ok if they have same nevra */
925               Solvable *ps = pool->solvables + qs.elements[i];
926               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
927                 continue;
928             }
929           qs.elements[j++] = qs.elements[i];
930         }
931       if (j < qs.count)
932         {
933           if (d && solv->updatesystem && solv->installed && s->repo == solv->installed)
934             {
935               if (!solv->multiversionupdaters)
936                 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
937               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
938             }
939           if (j == 0 && p == -SYSTEMSOLVABLE && solv->distupgrade)
940             {
941               queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
942               j = qs.count;
943             }
944           qs.count = j;
945         }
946     }
947   if (qs.count && p == -SYSTEMSOLVABLE)
948     p = queue_shift(&qs);
949   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
950   queue_free(&qs);
951   solver_addrule(solv, p, d);   /* allow update of s */
952   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule end -----\n");
953 }
954
955 static inline void 
956 disableupdaterule(Solver *solv, Id p)
957 {
958   Rule *r;
959
960   MAPSET(&solv->noupdate, p - solv->installed->start);
961   r = solv->rules + solv->updaterules + (p - solv->installed->start);
962   if (r->p && r->d >= 0)
963     solver_disablerule(solv, r);
964   r = solv->rules + solv->featurerules + (p - solv->installed->start);
965   if (r->p && r->d >= 0)
966     solver_disablerule(solv, r);
967 }
968
969 static inline void 
970 reenableupdaterule(Solver *solv, Id p)
971 {
972   Pool *pool = solv->pool;
973   Rule *r;
974
975   MAPCLR(&solv->noupdate, p - solv->installed->start);
976   r = solv->rules + solv->updaterules + (p - solv->installed->start);
977   if (r->p)
978     {    
979       if (r->d >= 0)
980         return;
981       solver_enablerule(solv, r);
982       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
983         {
984           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
985           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
986         }
987       return;
988     }
989   r = solv->rules + solv->featurerules + (p - solv->installed->start);
990   if (r->p && r->d < 0)
991     {
992       solver_enablerule(solv, r);
993       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
994         {
995           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
996           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
997         }
998     }
999 }
1000
1001
1002 /***********************************************************************
1003  ***
1004  ***  Infarch rule part
1005  ***
1006  ***  Infarch rules make sure the solver uses the best architecture of
1007  ***  a package if multiple archetectures are available
1008  ***
1009  ***/
1010
1011 void
1012 solver_addinfarchrules(Solver *solv, Map *addedmap)
1013 {
1014   Pool *pool = solv->pool;
1015   int first, i, j;
1016   Id p, pp, a, aa, bestarch;
1017   Solvable *s, *ps, *bests;
1018   Queue badq, allowedarchs;
1019
1020   queue_init(&badq);
1021   queue_init(&allowedarchs);
1022   solv->infarchrules = solv->nrules;
1023   for (i = 1; i < pool->nsolvables; i++)
1024     {
1025       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1026         continue;
1027       s = pool->solvables + i;
1028       first = i;
1029       bestarch = 0;
1030       bests = 0;
1031       queue_empty(&allowedarchs);
1032       FOR_PROVIDES(p, pp, s->name)
1033         {
1034           ps = pool->solvables + p;
1035           if (ps->name != s->name || !MAPTST(addedmap, p))
1036             continue;
1037           if (p == i)
1038             first = 0;
1039           if (first)
1040             break;
1041           a = ps->arch;
1042           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1043           if (a != 1 && pool->installed && ps->repo == pool->installed)
1044             {
1045               if (!solv->distupgrade)
1046                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
1047               continue;         /* ignore installed solvables when calculating the best arch */
1048             }
1049           if (a && a != 1 && (!bestarch || a < bestarch))
1050             {
1051               bestarch = a;
1052               bests = ps;
1053             }
1054         }
1055       if (first)
1056         continue;
1057       /* speed up common case where installed package already has best arch */
1058       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
1059         allowedarchs.count--;   /* installed arch is best */
1060       queue_empty(&badq);
1061       FOR_PROVIDES(p, pp, s->name)
1062         {
1063           ps = pool->solvables + p;
1064           if (ps->name != s->name || !MAPTST(addedmap, p))
1065             continue;
1066           a = ps->arch;
1067           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1068           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
1069             {
1070               if (pool->installed && ps->repo == pool->installed)
1071                 continue;       /* always ok to keep an installed package */
1072               for (j = 0; j < allowedarchs.count; j++)
1073                 {
1074                   aa = allowedarchs.elements[j];
1075                   if (ps->arch == aa)
1076                     break;
1077                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
1078                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
1079                     break;      /* compatible */
1080                 }
1081               if (j == allowedarchs.count)
1082                 queue_push(&badq, p);
1083             }
1084         }
1085       if (!badq.count)
1086         continue;
1087       /* block all solvables in the badq! */
1088       for (j = 0; j < badq.count; j++)
1089         {
1090           p = badq.elements[j];
1091           solver_addrule(solv, -p, 0);
1092         }
1093     }
1094   queue_free(&badq);
1095   queue_free(&allowedarchs);
1096   solv->infarchrules_end = solv->nrules;
1097 }
1098
1099 static inline void
1100 disableinfarchrule(Solver *solv, Id name)
1101 {
1102   Pool *pool = solv->pool;
1103   Rule *r;
1104   int i;
1105   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1106     {
1107       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1108         solver_disablerule(solv, r);
1109     }
1110 }
1111
1112 static inline void
1113 reenableinfarchrule(Solver *solv, Id name)
1114 {
1115   Pool *pool = solv->pool;
1116   Rule *r;
1117   int i;
1118   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1119     {
1120       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1121         {
1122           solver_enablerule(solv, r);
1123           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1124             {
1125               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1126               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1127             }
1128         }
1129     }
1130 }
1131
1132
1133 /***********************************************************************
1134  ***
1135  ***  Dup rule part
1136  ***
1137  ***  Dup rules make sure a package is selected from the specified dup
1138  ***  repositories if an update candidate is included in one of them.
1139  ***
1140  ***/
1141
1142 void
1143 solver_createdupmaps(Solver *solv)
1144 {
1145   Queue *job = &solv->job;
1146   Pool *pool = solv->pool;
1147   Repo *repo;
1148   Id how, what, p, pi, pp, obs, *obsp;
1149   Solvable *s, *ps;
1150   int i;
1151
1152   map_init(&solv->dupmap, pool->nsolvables);
1153   map_init(&solv->dupinvolvedmap, pool->nsolvables);
1154   for (i = 0; i < job->count; i += 2)
1155     {
1156       how = job->elements[i];
1157       what = job->elements[i + 1];
1158       switch (how & SOLVER_JOBMASK)
1159         {
1160         case SOLVER_DISTUPGRADE:
1161           if ((how & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_REPO)
1162             break;
1163           if (what <= 0 || what > pool->nrepos)
1164             break;
1165           repo = pool_id2repo(pool, what);
1166           FOR_REPO_SOLVABLES(repo, p, s)
1167             {
1168               MAPSET(&solv->dupmap, p);
1169               FOR_PROVIDES(pi, pp, s->name)
1170                 {
1171                   ps = pool->solvables + pi;
1172                   if (ps->name != s->name)
1173                     continue;
1174                   MAPSET(&solv->dupinvolvedmap, pi);
1175                 }
1176               if (s->obsoletes)
1177                 {
1178                   /* FIXME: check obsoletes/provides combination */
1179                   obsp = s->repo->idarraydata + s->obsoletes;
1180                   while ((obs = *obsp++) != 0)
1181                     {
1182                       FOR_PROVIDES(pi, pp, obs)
1183                         {
1184                           Solvable *pis = pool->solvables + pi;
1185                           if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pis, obs))
1186                             continue;
1187                           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pis))
1188                             continue;
1189                           MAPSET(&solv->dupinvolvedmap, pi);
1190                         }
1191                     }
1192                 }
1193             }
1194           break;
1195         default:
1196           break;
1197         }
1198     }
1199   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
1200 }
1201
1202 void
1203 solver_freedupmaps(Solver *solv)
1204 {
1205   map_free(&solv->dupmap);
1206   map_free(&solv->dupinvolvedmap);
1207 }
1208
1209 void
1210 solver_addduprules(Solver *solv, Map *addedmap)
1211 {
1212   Pool *pool = solv->pool;
1213   Id p, pp;
1214   Solvable *s, *ps;
1215   int first, i;
1216
1217   solv->duprules = solv->nrules;
1218   for (i = 1; i < pool->nsolvables; i++)
1219     {
1220       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1221         continue;
1222       s = pool->solvables + i;
1223       first = i;
1224       FOR_PROVIDES(p, pp, s->name)
1225         {
1226           ps = pool->solvables + p;
1227           if (ps->name != s->name || !MAPTST(addedmap, p))
1228             continue;
1229           if (p == i)
1230             first = 0;
1231           if (first)
1232             break;
1233           if (!MAPTST(&solv->dupinvolvedmap, p))
1234             continue;
1235           if (solv->installed && ps->repo == solv->installed)
1236             {
1237               if (!solv->updatemap.size)
1238                 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
1239               MAPSET(&solv->updatemap, p - solv->installed->start);
1240               if (!MAPTST(&solv->dupmap, p))
1241                 {
1242                   Id ip, ipp;
1243                   /* is installed identical to a good one? */
1244                   FOR_PROVIDES(ip, ipp, s->name)
1245                     {
1246                       Solvable *is = pool->solvables + ip;
1247                       if (!MAPTST(&solv->dupmap, ip))
1248                         continue;
1249                       if (is->evr == s->evr && solvable_identical(s, is))
1250                         break;
1251                     }
1252                   if (!ip)
1253                     solver_addrule(solv, -p, 0);        /* no match, sorry */
1254                 }
1255             }
1256           else if (!MAPTST(&solv->dupmap, p))
1257             solver_addrule(solv, -p, 0);
1258         }
1259     }
1260   solv->duprules_end = solv->nrules;
1261 }
1262
1263
1264 static inline void
1265 disableduprule(Solver *solv, Id name)
1266 {
1267   Pool *pool = solv->pool;
1268   Rule *r;
1269   int i;
1270   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++) 
1271     {    
1272       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1273         solver_disablerule(solv, r);
1274     }    
1275 }
1276
1277 static inline void 
1278 reenableduprule(Solver *solv, Id name)
1279 {
1280   Pool *pool = solv->pool;
1281   Rule *r;
1282   int i;
1283   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++) 
1284     {    
1285       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1286         {
1287           solver_enablerule(solv, r);
1288           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1289             {
1290               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1291               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1292             }
1293         }
1294     }
1295 }
1296
1297
1298 /***********************************************************************
1299  ***
1300  ***  Policy rule disabling/reenabling
1301  ***
1302  ***  Disable all policy rules that conflict with our jobs. If a job
1303  ***  gets disabled later on, reenable the involved policy rules again.
1304  ***
1305  ***/
1306
1307 #define DISABLE_UPDATE  1
1308 #define DISABLE_INFARCH 2
1309 #define DISABLE_DUP     3
1310
1311 static void
1312 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1313 {
1314   Pool *pool = solv->pool;
1315   Id select, p, pp;
1316   Repo *installed;
1317   Solvable *s;
1318   int i;
1319
1320   installed = solv->installed;
1321   select = how & SOLVER_SELECTMASK;
1322   switch (how & SOLVER_JOBMASK)
1323     {
1324     case SOLVER_INSTALL:
1325       if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && solv->infarchrules != solv->infarchrules_end && ISRELDEP(what))
1326         {
1327           Reldep *rd = GETRELDEP(pool, what);
1328           if (rd->flags == REL_ARCH)
1329             {
1330               int qcnt = q->count;
1331               FOR_JOB_SELECT(p, pp, select, what)
1332                 {
1333                   s = pool->solvables + p;
1334                   /* unify names */
1335                   for (i = qcnt; i < q->count; i += 2)
1336                     if (q->elements[i + 1] == s->name)
1337                       break;
1338                   if (i < q->count)
1339                     continue;
1340                   queue_push(q, DISABLE_INFARCH);
1341                   queue_push(q, s->name);
1342                 }
1343             }
1344         }
1345       if (select != SOLVER_SOLVABLE)
1346         break;
1347       s = pool->solvables + what;
1348       if (solv->infarchrules != solv->infarchrules_end)
1349         {
1350           queue_push(q, DISABLE_INFARCH);
1351           queue_push(q, s->name);
1352         }
1353       if (solv->duprules != solv->duprules_end)
1354         {
1355           queue_push(q, DISABLE_DUP);
1356           queue_push(q, s->name);
1357         }
1358       if (!installed)
1359         return;
1360       if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, what))
1361         {
1362           /* XXX: remove if we always do distupgrade with DUP rules */
1363           if (solv->distupgrade && s->repo == installed)
1364             {
1365               queue_push(q, DISABLE_UPDATE);
1366               queue_push(q, what);
1367               return;
1368             }
1369           return;
1370         }
1371       if (s->repo == installed)
1372         {
1373           queue_push(q, DISABLE_UPDATE);
1374           queue_push(q, what);
1375           return;
1376         }
1377       if (s->obsoletes)
1378         {
1379           Id obs, *obsp;
1380           obsp = s->repo->idarraydata + s->obsoletes;
1381           while ((obs = *obsp++) != 0)
1382             FOR_PROVIDES(p, pp, obs)
1383               {
1384                 Solvable *ps = pool->solvables + p;
1385                 if (ps->repo != installed)
1386                   continue;
1387                 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1388                   continue;
1389                 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1390                   continue;
1391                 queue_push(q, DISABLE_UPDATE);
1392                 queue_push(q, p);
1393               }
1394         }
1395       FOR_PROVIDES(p, pp, s->name)
1396         {
1397           Solvable *ps = pool->solvables + p;
1398           if (ps->repo != installed)
1399             continue;
1400           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1401             continue;
1402           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1403             continue;
1404           queue_push(q, DISABLE_UPDATE);
1405           queue_push(q, p);
1406         }
1407       return;
1408     case SOLVER_ERASE:
1409       if (!installed)
1410         break;
1411       FOR_JOB_SELECT(p, pp, select, what)
1412         if (pool->solvables[p].repo == installed)
1413           {
1414             queue_push(q, DISABLE_UPDATE);
1415             queue_push(q, p);
1416           }
1417       return;
1418     default:
1419       return;
1420     }
1421 }
1422
1423 /* disable all policy rules that are in conflict with our job list */
1424 void
1425 solver_disablepolicyrules(Solver *solv)
1426 {
1427   Queue *job = &solv->job;
1428   int i, j;
1429   Queue allq;
1430   Rule *r;
1431   Id lastjob = -1;
1432   Id allqbuf[128];
1433
1434   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1435
1436   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1437     {
1438       r = solv->rules + i;
1439       if (r->d < 0)     /* disabled? */
1440         continue;
1441       j = solv->ruletojob.elements[i - solv->jobrules];
1442       if (j == lastjob)
1443         continue;
1444       lastjob = j;
1445       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1446     }
1447   MAPZERO(&solv->noupdate);
1448   for (i = 0; i < allq.count; i += 2)
1449     {
1450       Id type = allq.elements[i], arg = allq.elements[i + 1];
1451       switch(type)
1452         {
1453         case DISABLE_UPDATE:
1454           disableupdaterule(solv, arg);
1455           break;
1456         case DISABLE_INFARCH:
1457           disableinfarchrule(solv, arg);
1458           break;
1459         case DISABLE_DUP:
1460           disableduprule(solv, arg);
1461           break;
1462         default:
1463           break;
1464         }
1465     }
1466   queue_free(&allq);
1467 }
1468
1469 /* we just disabled job #jobidx, now reenable all policy rules that were
1470  * disabled because of this job */
1471 void
1472 solver_reenablepolicyrules(Solver *solv, int jobidx)
1473 {
1474   Queue *job = &solv->job;
1475   int i, j;
1476   Queue q, allq;
1477   Rule *r;
1478   Id lastjob = -1;
1479   Id qbuf[32], allqbuf[128];
1480
1481   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1482   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1483   jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q);
1484   if (!q.count)
1485     return;
1486   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1487     {
1488       r = solv->rules + i;
1489       if (r->d < 0)     /* disabled? */
1490         continue;
1491       j = solv->ruletojob.elements[i - solv->jobrules];
1492       if (j == lastjob)
1493         continue;
1494       lastjob = j;
1495       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1496     }
1497   for (j = 0; j < q.count; j += 2)
1498     {
1499       Id type = q.elements[j], arg = q.elements[j + 1];
1500       for (i = 0; i < allq.count; i += 2)
1501         if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1502           break;
1503       if (i < allq.count)
1504         continue;       /* still disabled */
1505       switch(type)
1506         {
1507         case DISABLE_UPDATE:
1508           reenableupdaterule(solv, arg);
1509           break;
1510         case DISABLE_INFARCH:
1511           reenableinfarchrule(solv, arg);
1512           break;
1513         case DISABLE_DUP:
1514           reenableduprule(solv, arg);
1515           break;
1516         }
1517     }
1518   queue_free(&allq);
1519   queue_free(&q);
1520 }
1521
1522
1523 /***********************************************************************
1524  ***
1525  ***  Rule info part, tell the user what the rule is about.
1526  ***
1527  ***/
1528
1529 static void
1530 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
1531 {
1532   Pool *pool = solv->pool;
1533   Rule *r;
1534   Id w2, op, od, ow2;
1535
1536   /* check if this creates the rule we're searching for */
1537   r = solv->rules + solv->ruleinfoq->elements[0];
1538   op = r->p;
1539   od = r->d < 0 ? -r->d - 1 : r->d;
1540   ow2 = 0;
1541
1542   /* normalize */
1543   w2 = d > 0 ? 0 : d;
1544   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
1545     {
1546       w2 = pool->whatprovidesdata[d];
1547       d = 0;
1548
1549     }
1550   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
1551     {
1552       w2 = p;
1553       p = d;
1554     }
1555
1556   if (d > 0)
1557     {
1558       if (p != op && !od)
1559         return;
1560       if (d != od)
1561         {
1562           Id *dp = pool->whatprovidesdata + d;
1563           Id *odp = pool->whatprovidesdata + od;
1564           while (*dp)
1565             if (*dp++ != *odp++)
1566               return;
1567           if (*odp)
1568             return;
1569         }
1570       w2 = 0;
1571       /* handle multiversion conflict rules */
1572       if (p < 0 && pool->whatprovidesdata[d] < 0)
1573         {
1574           w2 = pool->whatprovidesdata[d];
1575           /* XXX: free memory */
1576         }
1577     }
1578   else
1579     {
1580       if (od)
1581         return;
1582       ow2 = r->w2;
1583       if (p > w2)
1584         {
1585           if (w2 != op || p != ow2)
1586             return;
1587         }
1588       else
1589         {
1590           if (p != op || w2 != ow2)
1591             return;
1592         }
1593     }
1594   /* yep, rule matches. record info */
1595   queue_push(solv->ruleinfoq, type);
1596   if (type == SOLVER_RULE_RPM_SAME_NAME)
1597     {
1598       /* we normalize same name order */
1599       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
1600       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
1601     }
1602   else
1603     {
1604       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
1605       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
1606     }
1607   queue_push(solv->ruleinfoq, dep);
1608 }
1609
1610 static int
1611 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
1612 {
1613   const Id *a = ap, *b = bp;
1614   int r;
1615
1616   r = a[0] - b[0];
1617   if (r)
1618     return r;
1619   r = a[1] - b[1];
1620   if (r)
1621     return r;
1622   r = a[2] - b[2];
1623   if (r)
1624     return r;
1625   r = a[3] - b[3];
1626   if (r)
1627     return r;
1628   return 0;
1629 }
1630
1631 int
1632 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
1633 {
1634   Pool *pool = solv->pool;
1635   Rule *r = solv->rules + rid;
1636   int i, j;
1637
1638   queue_empty(rq);
1639   if (rid <= 0 || rid >= solv->rpmrules_end)
1640     {
1641       Id type, from, to, dep;
1642       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
1643       queue_push(rq, type);
1644       queue_push(rq, from);
1645       queue_push(rq, to);
1646       queue_push(rq, dep);
1647       return 1;
1648     }
1649   if (r->p >= 0)
1650     return 0;
1651   queue_push(rq, rid);
1652   solv->ruleinfoq = rq;
1653   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1654   /* also try reverse direction for conflicts */
1655   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1656     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1657   solv->ruleinfoq = 0;
1658   queue_shift(rq);
1659   /* now sort & unify em */
1660   if (!rq->count)
1661     return 0;
1662   sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
1663   /* throw out identical entries */
1664   for (i = j = 0; i < rq->count; i += 4)
1665     {
1666       if (j)
1667         {
1668           if (rq->elements[i] == rq->elements[j - 4] && 
1669               rq->elements[i + 1] == rq->elements[j - 3] &&
1670               rq->elements[i + 2] == rq->elements[j - 2] &&
1671               rq->elements[i + 3] == rq->elements[j - 1])
1672             continue;
1673         }
1674       rq->elements[j++] = rq->elements[i];
1675       rq->elements[j++] = rq->elements[i + 1];
1676       rq->elements[j++] = rq->elements[i + 2];
1677       rq->elements[j++] = rq->elements[i + 3];
1678     }
1679   rq->count = j;
1680   return j / 4;
1681 }
1682
1683 SolverRuleinfo
1684 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
1685 {
1686   Pool *pool = solv->pool;
1687   Rule *r = solv->rules + rid;
1688   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
1689
1690   if (fromp)
1691     *fromp = 0;
1692   if (top)
1693     *top = 0;
1694   if (depp)
1695     *depp = 0;
1696   if (rid > 0 && rid < solv->rpmrules_end)
1697     {
1698       Queue rq;
1699       int i;
1700
1701       if (r->p >= 0)
1702         return SOLVER_RULE_RPM;
1703       if (fromp)
1704         *fromp = -r->p;
1705       queue_init(&rq);
1706       queue_push(&rq, rid);
1707       solv->ruleinfoq = &rq;
1708       solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1709       /* also try reverse direction for conflicts */
1710       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1711         solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1712       solv->ruleinfoq = 0;
1713       type = SOLVER_RULE_RPM;
1714       for (i = 1; i < rq.count; i += 4)
1715         {
1716           Id qt, qo, qp, qd;
1717           qt = rq.elements[i];
1718           qp = rq.elements[i + 1];
1719           qo = rq.elements[i + 2];
1720           qd = rq.elements[i + 3];
1721           if (type == SOLVER_RULE_RPM || type > qt)
1722             {
1723               type = qt;
1724               if (fromp)
1725                 *fromp = qp;
1726               if (top)
1727                 *top = qo;
1728               if (depp)
1729                 *depp = qd;
1730             }
1731         }
1732       queue_free(&rq);
1733       return type;
1734     }
1735   if (rid >= solv->jobrules && rid < solv->jobrules_end)
1736     {
1737       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
1738       if (fromp)
1739         *fromp = jidx;
1740       if (top)
1741         *top = solv->job.elements[jidx];
1742       if (depp)
1743         *depp = solv->job.elements[jidx + 1];
1744       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
1745         return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
1746       return SOLVER_RULE_JOB;
1747     }
1748   if (rid >= solv->updaterules && rid < solv->updaterules_end)
1749     {
1750       if (fromp)
1751         *fromp = solv->installed->start + (rid - solv->updaterules);
1752       return SOLVER_RULE_UPDATE;
1753     }
1754   if (rid >= solv->featurerules && rid < solv->featurerules_end)
1755     {
1756       if (fromp)
1757         *fromp = solv->installed->start + (rid - solv->featurerules);
1758       return SOLVER_RULE_FEATURE;
1759     }
1760   if (rid >= solv->duprules && rid < solv->duprules_end)
1761     {
1762       if (fromp)
1763         *fromp = -r->p;
1764       if (depp)
1765         *depp = pool->solvables[-r->p].name;
1766       return SOLVER_RULE_DISTUPGRADE;
1767     }
1768   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
1769     {
1770       if (fromp)
1771         *fromp = -r->p;
1772       if (depp)
1773         *depp = pool->solvables[-r->p].name;
1774       return SOLVER_RULE_INFARCH;
1775     }
1776   if (rid >= solv->choicerules && rid < solv->choicerules_end)
1777     {
1778       return SOLVER_RULE_CHOICE;
1779     }
1780   if (rid >= solv->learntrules)
1781     {
1782       return SOLVER_RULE_LEARNT;
1783     }
1784   return SOLVER_RULE_UNKNOWN;
1785 }
1786
1787 void
1788 addchoicerules(Solver *solv)
1789 {
1790   Pool *pool = solv->pool;
1791   Map m, mneg;
1792   Rule *r;
1793   Queue q, qi;
1794   int i, j, rid, havechoice;
1795   Id p, d, *pp;
1796   Id p2, pp2;
1797   Solvable *s, *s2;
1798
1799   solv->choicerules = solv->nrules;
1800   if (!pool->installed)
1801     {
1802       solv->choicerules_end = solv->nrules;
1803       return;
1804     }
1805   solv->choicerules_ref = sat_calloc(solv->rpmrules_end, sizeof(Id));
1806   queue_init(&q);
1807   queue_init(&qi);
1808   map_init(&m, pool->nsolvables);
1809   map_init(&mneg, pool->nsolvables);
1810   /* set up negative assertion map from infarch and dup rules */
1811   for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++)
1812     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
1813       MAPSET(&mneg, -r->p);
1814   for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++)
1815     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
1816       MAPSET(&mneg, -r->p);
1817   for (rid = 1; rid < solv->rpmrules_end ; rid++)
1818     {
1819       r = solv->rules + rid;
1820       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0))
1821         continue;       /* only look at requires rules */
1822       // solver_printrule(solv, SAT_DEBUG_RESULT, r);
1823       queue_empty(&q);
1824       queue_empty(&qi);
1825       havechoice = 0;
1826       FOR_RULELITERALS(p, pp, r)
1827         {
1828           if (p < 0)
1829             continue;
1830           s = pool->solvables + p;
1831           if (!s->repo)
1832             continue;
1833           if (s->repo == pool->installed)
1834             {
1835               queue_push(&q, p);
1836               continue;
1837             }
1838           /* check if this package is "blocked" by a installed package */
1839           s2 = 0;
1840           FOR_PROVIDES(p2, pp2, s->name)
1841             {
1842               s2 = pool->solvables + p2;
1843               if (s2->repo != pool->installed)
1844                 continue;
1845               if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
1846                 continue;
1847               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
1848                 continue;
1849               break;
1850             }
1851           if (p2)
1852             {
1853               /* found installed package p2 that we can update to p */
1854               if (!solv->allowarchchange && s->arch != s2->arch && policy_illegal_archchange(solv, s, s2))
1855                 continue;
1856               if (!solv->allowvendorchange && s->vendor != s2->vendor && policy_illegal_vendorchange(solv, s, s2))
1857                 continue;
1858               if (MAPTST(&mneg, p))
1859                 continue;
1860               queue_push(&qi, p2);
1861               queue_push(&q, p);
1862               continue;
1863             }
1864           if (s->obsoletes)
1865             {
1866               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
1867               s2 = 0;
1868               while ((obs = *obsp++) != 0)
1869                 {
1870                   FOR_PROVIDES(p2, pp2, obs)
1871                     {
1872                       s2 = pool->solvables + p2;
1873                       if (s2->repo != pool->installed)
1874                         continue;
1875                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
1876                         continue;
1877                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
1878                         continue;
1879                       break;
1880                     }
1881                   if (p2)
1882                     break;
1883                 }
1884               if (obs)
1885                 {
1886                   /* found installed package p2 that we can update to p */
1887                   if (!solv->allowarchchange && s->arch != s2->arch && policy_illegal_archchange(solv, s, s2))
1888                     continue;
1889                   if (!solv->allowvendorchange && s->vendor != s2->vendor && policy_illegal_vendorchange(solv, s, s2))
1890                     continue;
1891                   if (MAPTST(&mneg, p))
1892                     continue;
1893                   queue_push(&qi, p2);
1894                   queue_push(&q, p);
1895                   continue;
1896                 }
1897             }
1898           /* package p is independent of the installed ones */
1899           havechoice = 1;
1900         }
1901       if (!havechoice || !q.count)
1902         continue;       /* no choice */
1903
1904       /* now check the update rules of the installed package.
1905        * if all packages of the update rules are contained in
1906        * the dependency rules, there's no need to set up the choice rule */
1907       map_empty(&m);
1908       FOR_RULELITERALS(p, pp, r)
1909         if (p > 0)
1910           MAPSET(&m, p);
1911       for (i = 0; i < qi.count; i++)
1912         {
1913           if (!qi.elements[i])
1914             continue;
1915           Rule *ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start);
1916           if (!ur->p)
1917             ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start);
1918           if (!ur->p)
1919             continue;
1920           FOR_RULELITERALS(p, pp, ur)
1921             if (!MAPTST(&m, p))
1922               break;
1923           if (p)
1924             break;
1925           for (j = i + 1; j < qi.count; j++)
1926             if (qi.elements[i] == qi.elements[j])
1927               qi.elements[j] = 0;
1928         }
1929       if (i == qi.count)
1930         {
1931 #if 0
1932           printf("skipping choice ");
1933           solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid);
1934 #endif
1935           continue;
1936         }
1937       d = q.count ? pool_queuetowhatprovides(pool, &q) : 0;
1938       solver_addrule(solv, r->p, d);
1939       queue_push(&solv->weakruleq, solv->nrules - 1);
1940       solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid;
1941 #if 0
1942       printf("OLD ");
1943       solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid);
1944       printf("WEAK CHOICE ");
1945       solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + solv->nrules - 1);
1946 #endif
1947     }
1948   queue_free(&q);
1949   queue_free(&qi);
1950   map_free(&m);
1951   map_free(&mneg);
1952   solv->choicerules_end = solv->nrules;
1953 }
1954
1955 /* called when a choice rule is disabled by analyze_unsolvable. We also
1956  * have to disable all other choice rules so that the best packages get
1957  * picked */
1958  
1959 void
1960 disablechoicerules(Solver *solv, Rule *r)
1961 {
1962   Id rid, p, *pp;
1963   Pool *pool = solv->pool;
1964   Map m;
1965   Rule *or;
1966
1967   or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
1968   map_init(&m, pool->nsolvables);
1969   FOR_RULELITERALS(p, pp, or)
1970     if (p > 0)
1971       MAPSET(&m, p);
1972   FOR_RULELITERALS(p, pp, r)
1973     if (p > 0)
1974       MAPCLR(&m, p);
1975   for (rid = solv->choicerules; rid < solv->choicerules_end; rid++)
1976     {
1977       r = solv->rules + rid;
1978       if (r->d < 0)
1979         continue;
1980       or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
1981       FOR_RULELITERALS(p, pp, or)
1982         if (p > 0 && MAPTST(&m, p))
1983           break;
1984       if (p)
1985         solver_disablerule(solv, r);
1986     }
1987 }
1988
1989 /* EOF */