make FORCEBEST work with targeted up/dup
[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 "solver_private.h"
22 #include "bitmap.h"
23 #include "pool.h"
24 #include "poolarch.h"
25 #include "util.h"
26 #include "evr.h"
27 #include "policy.h"
28 #include "solverdebug.h"
29
30 #define RULES_BLOCK 63
31
32 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep);
33 static void solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded);
34
35 /*-------------------------------------------------------------------
36  * Check if dependency is possible
37  * 
38  * mirrors solver_dep_fulfilled but uses map m instead of the decisionmap
39  * used in solver_addrpmrulesforweak and solver_createcleandepsmap
40  */
41
42 static inline int
43 dep_possible(Solver *solv, Id dep, Map *m)
44 {
45   Pool *pool = solv->pool;
46   Id p, pp;
47
48   if (ISRELDEP(dep))
49     {
50       Reldep *rd = GETRELDEP(pool, dep);
51       if (rd->flags >= 8)
52         {
53           if (rd->flags == REL_AND)
54             {
55               if (!dep_possible(solv, rd->name, m))
56                 return 0;
57               return dep_possible(solv, rd->evr, m);
58             }
59           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
60             return solver_splitprovides(solv, rd->evr);
61           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
62             return solver_dep_installed(solv, rd->evr);
63         }
64     }
65   FOR_PROVIDES(p, pp, dep)
66     {
67       if (MAPTST(m, p))
68         return 1;
69     }
70   return 0;
71 }
72
73 /********************************************************************
74  *
75  * Rule handling
76  *
77  * - unify rules, remove duplicates
78  */
79
80 /*-------------------------------------------------------------------
81  *
82  * compare rules for unification sort
83  *
84  */
85
86 static int
87 unifyrules_sortcmp(const void *ap, const void *bp, void *dp)
88 {
89   Pool *pool = dp;
90   Rule *a = (Rule *)ap;
91   Rule *b = (Rule *)bp;
92   Id *ad, *bd;
93   int x;
94
95   x = a->p - b->p;
96   if (x)
97     return x;                          /* p differs */
98
99   /* identical p */
100   if (a->d == 0 && b->d == 0)
101     return a->w2 - b->w2;              /* assertion: return w2 diff */
102
103   if (a->d == 0)                       /* a is assertion, b not */
104     {
105       x = a->w2 - pool->whatprovidesdata[b->d];
106       return x ? x : -1;
107     }
108
109   if (b->d == 0)                       /* b is assertion, a not */
110     {
111       x = pool->whatprovidesdata[a->d] - b->w2;
112       return x ? x : 1;
113     }
114
115   /* compare whatprovidesdata */
116   ad = pool->whatprovidesdata + a->d;
117   bd = pool->whatprovidesdata + b->d;
118   while (*bd)
119     if ((x = *ad++ - *bd++) != 0)
120       return x;
121   return *ad;
122 }
123
124 int
125 solver_samerule(Solver *solv, Rule *r1, Rule *r2)
126 {
127   return unifyrules_sortcmp(r1, r2, solv->pool);
128 }
129
130
131 /*-------------------------------------------------------------------
132  *
133  * unify rules
134  * go over all rules and remove duplicates
135  */
136
137 void
138 solver_unifyrules(Solver *solv)
139 {
140   Pool *pool = solv->pool;
141   int i, j;
142   Rule *ir, *jr;
143
144   if (solv->nrules <= 2)               /* nothing to unify */
145     return;
146
147   /* sort rules first */
148   solv_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool);
149
150   /* prune rules
151    * i = unpruned
152    * j = pruned
153    */
154   jr = 0;
155   for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
156     {
157       if (jr && !unifyrules_sortcmp(ir, jr, pool))
158         continue;                      /* prune! */
159       jr = solv->rules + j++;          /* keep! */
160       if (ir != jr)
161         *jr = *ir;
162     }
163
164   /* reduced count from nrules to j rules */
165   POOL_DEBUG(SOLV_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
166
167   /* adapt rule buffer */
168   solv->nrules = j;
169   solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
170
171   /*
172    * debug: log rule statistics
173    */
174   IF_POOLDEBUG (SOLV_DEBUG_STATS)
175     {
176       int binr = 0;
177       int lits = 0;
178       Id *dp;
179       Rule *r;
180
181       for (i = 1; i < solv->nrules; i++)
182         {
183           r = solv->rules + i;
184           if (r->d == 0)
185             binr++;
186           else
187             {
188               dp = solv->pool->whatprovidesdata + r->d;
189               while (*dp++)
190                 lits++;
191             }
192         }
193       POOL_DEBUG(SOLV_DEBUG_STATS, "  binary: %d\n", binr);
194       POOL_DEBUG(SOLV_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
195     }
196 }
197
198 #if 0
199
200 /*
201  * hash rule
202  */
203
204 static Hashval
205 hashrule(Solver *solv, Id p, Id d, int n)
206 {
207   unsigned int x = (unsigned int)p;
208   int *dp;
209
210   if (n <= 1)
211     return (x * 37) ^ (unsigned int)d;
212   dp = solv->pool->whatprovidesdata + d;
213   while (*dp)
214     x = (x * 37) ^ (unsigned int)*dp++;
215   return x;
216 }
217 #endif
218
219
220 /*-------------------------------------------------------------------
221  * 
222  */
223
224 /*
225  * add rule
226  *  p = direct literal; always < 0 for installed rpm rules
227  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
228  *
229  *
230  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
231  *
232  * p < 0 : pkg id of A
233  * d > 0 : Offset in whatprovidesdata (list of providers of b)
234  *
235  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
236  * p < 0 : pkg id of A
237  * d < 0 : Id of solvable (e.g. B1)
238  *
239  * d == 0: unary rule, assertion => (A) or (-A)
240  *
241  *   Install:    p > 0, d = 0   (A)             user requested install
242  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
243  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
244  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
245  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
246  *                                              also used for obsoletes
247  *   ?:          p > 0, d < 0   (A|-B)          
248  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
249  *
250  *   resulting watches:
251  *   ------------------
252  *   Direct assertion (no watch needed) --> d = 0, w1 = p, w2 = 0
253  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
254  *   every other : w1 = p, w2 = whatprovidesdata[d];
255  *   Disabled rule: w1 = 0
256  *
257  *   always returns a rule for non-rpm rules
258  */
259
260 Rule *
261 solver_addrule(Solver *solv, Id p, Id d)
262 {
263   Pool *pool = solv->pool;
264   Rule *r = 0;
265   Id *dp = 0;
266
267   int n = 0;                           /* number of literals in rule - 1
268                                           0 = direct assertion (single literal)
269                                           1 = binary rule
270                                           >1 = 
271                                         */
272
273   /* it often happenes that requires lead to adding the same rpm rule
274    * multiple times, so we prune those duplicates right away to make
275    * the work for unifyrules a bit easier */
276
277   if (!solv->rpmrules_end)              /* we add rpm rules */
278     {
279       r = solv->rules + solv->nrules - 1;       /* get the last added rule */
280       if (r->p == p && r->d == d && (d != 0 || !r->w2))
281         return r;
282     }
283
284     /*
285      * compute number of literals (n) in rule
286      */
287     
288   if (d < 0)
289     {
290       /* always a binary rule */
291       if (p == d)
292         return 0;                      /* ignore self conflict */
293       n = 1;
294     }
295   else if (d > 0)
296     {
297       for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
298         if (*dp == -p)
299           return 0;                     /* rule is self-fulfilling */
300         
301       if (n == 1)                       /* convert to binary rule */
302         d = dp[-1];
303     }
304
305   if (n == 1 && p > d && !solv->rpmrules_end)
306     {
307       /* smallest literal first so we can find dups */
308       n = p; p = d; d = n;             /* p <-> d */
309       n = 1;                           /* re-set n, was used as temp var */
310     }
311
312   /*
313    * check for duplicate
314    */
315     
316   /* check if the last added rule (r) is exactly the same as what we're looking for. */
317   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
318     return r;  /* binary rule */
319
320     /* have n-ary rule with same first literal, check other literals */
321   if (r && n > 1 && r->d && r->p == p)
322     {
323       /* Rule where d is an offset in whatprovidesdata */
324       Id *dp2;
325       if (d == r->d)
326         return r;
327       dp2 = pool->whatprovidesdata + r->d;
328       for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
329         if (*dp != *dp2)
330           break;
331       if (*dp == *dp2)
332         return r;
333    }
334
335   /*
336    * allocate new rule
337    */
338
339   /* extend rule buffer */
340   solv->rules = solv_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
341   r = solv->rules + solv->nrules++;    /* point to rule space */
342
343     /*
344      * r = new rule
345      */
346     
347   r->p = p;
348   if (n == 0)
349     {
350       /* direct assertion, no watch needed */
351       r->d = 0;
352       r->w1 = p;
353       r->w2 = 0;
354     }
355   else if (n == 1)
356     {
357       /* binary rule */
358       r->d = 0;
359       r->w1 = p;
360       r->w2 = d;
361     }
362   else
363     {
364       r->d = d;
365       r->w1 = p;
366       r->w2 = pool->whatprovidesdata[d];
367     }
368   r->n1 = 0;
369   r->n2 = 0;
370
371   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
372     {
373       POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "  Add rule: ");
374       solver_printrule(solv, SOLV_DEBUG_RULE_CREATION, r);
375     }
376
377   return r;
378 }
379
380
381 /******************************************************************************
382  ***
383  *** rpm rule part: create rules representing the package dependencies
384  ***
385  ***/
386
387 /*
388  *  special multiversion patch conflict handling:
389  *  a patch conflict is also satisfied if some other
390  *  version with the same name/arch that doesn't conflict
391  *  gets installed. The generated rule is thus:
392  *  -patch|-cpack|opack1|opack2|...
393  */
394 static Id
395 makemultiversionconflict(Solver *solv, Id n, Id con)
396 {
397   Pool *pool = solv->pool;
398   Solvable *s, *sn;
399   Queue q;
400   Id p, pp, qbuf[64];
401
402   sn = pool->solvables + n;
403   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
404   queue_push(&q, -n);
405   FOR_PROVIDES(p, pp, sn->name)
406     {
407       s = pool->solvables + p;
408       if (s->name != sn->name || s->arch != sn->arch)
409         continue;
410       if (!MAPTST(&solv->noobsoletes, p))
411         continue;
412       if (pool_match_nevr(pool, pool->solvables + p, con))
413         continue;
414       /* here we have a multiversion solvable that doesn't conflict */
415       /* thus we're not in conflict if it is installed */
416       queue_push(&q, p);
417     }
418   if (q.count == 1)
419     return -n;  /* no other package found, generate normal conflict */
420   return pool_queuetowhatprovides(pool, &q);
421 }
422
423 static inline void
424 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep)
425 {
426   if (!solv->ruleinfoq)
427     solver_addrule(solv, p, d);
428   else
429     addrpmruleinfo(solv, p, d, type, dep);
430 }
431
432 /*-------------------------------------------------------------------
433  * 
434  * add (install) rules for solvable
435  * 
436  * s: Solvable for which to add rules
437  * m: m[s] = 1 for solvables which have rules, prevent rule duplication
438  * 
439  * Algorithm: 'visit all nodes of a graph'. The graph nodes are
440  *  solvables, the edges their dependencies.
441  *  Starting from an installed solvable, this will create all rules
442  *  representing the graph created by the solvables dependencies.
443  * 
444  * for unfulfilled requirements, conflicts, obsoletes,....
445  * add a negative assertion for solvables that are not installable
446  * 
447  * It will also create rules for all solvables referenced by 's'
448  *  i.e. descend to all providers of requirements of 's'
449  *
450  */
451
452 void
453 solver_addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
454 {
455   Pool *pool = solv->pool;
456   Repo *installed = solv->installed;
457
458   /* 'work' queue. keeps Ids of solvables we still have to work on.
459      And buffer for it. */
460   Queue workq;
461   Id workqbuf[64];
462     
463   int i;
464     /* if to add rules for broken deps ('rpm -V' functionality)
465      * 0 = yes, 1 = no
466      */
467   int dontfix;
468     /* Id var and pointer for each dependency
469      * (not used in parallel)
470      */
471   Id req, *reqp;
472   Id con, *conp;
473   Id obs, *obsp;
474   Id rec, *recp;
475   Id sug, *sugp;
476   Id p, pp;             /* whatprovides loops */
477   Id *dp;               /* ptr to 'whatprovides' */
478   Id n;                 /* Id for current solvable 's' */
479
480   queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
481   queue_push(&workq, s - pool->solvables);      /* push solvable Id to work queue */
482
483   /* loop until there's no more work left */
484   while (workq.count)
485     {
486       /*
487        * n: Id of solvable
488        * s: Pointer to solvable
489        */
490
491       n = queue_shift(&workq);          /* 'pop' next solvable to work on from queue */
492       if (m)
493         {
494           if (MAPTST(m, n))             /* continue if already visited */
495             continue;
496           MAPSET(m, n);                 /* mark as visited */
497         }
498
499       s = pool->solvables + n;          /* s = Solvable in question */
500
501       dontfix = 0;
502       if (installed                     /* Installed system available */
503           && s->repo == installed       /* solvable is installed */
504           && !solv->fixmap_all          /* NOT repair errors in rpm dependency graph */
505           && !(solv->fixmap.size && MAPTST(&solv->fixmap, n - installed->start)))
506         {
507           dontfix = 1;                  /* dont care about broken rpm deps */
508         }
509
510       if (!dontfix
511           && s->arch != ARCH_SRC
512           && s->arch != ARCH_NOSRC
513           && !pool_installable(pool, s))
514         {
515           POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", pool_solvable2str(pool, s), (Id)(s - pool->solvables));
516           addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0);
517         }
518
519       /* yet another SUSE hack, sigh */
520       if (pool->nscallback && !strncmp("product:", pool_id2str(pool, s->name), 8))
521         {
522           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
523           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
524             {
525               addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n));
526               addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy)); 
527               if (m && !MAPTST(m, buddy))
528                 queue_push(&workq, buddy);
529             }
530         }
531
532       /*-----------------------------------------
533        * check requires of s
534        */
535
536       if (s->requires)
537         {
538           reqp = s->repo->idarraydata + s->requires;
539           while ((req = *reqp++) != 0)            /* go through all requires */
540             {
541               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
542                 continue;
543
544               /* find list of solvables providing 'req' */
545               dp = pool_whatprovides_ptr(pool, req);
546
547               if (*dp == SYSTEMSOLVABLE)          /* always installed */
548                 continue;
549
550               if (dontfix)
551                 {
552                   /* the strategy here is to not insist on dependencies
553                    * that are already broken. so if we find one provider
554                    * that was already installed, we know that the
555                    * dependency was not broken before so we enforce it */
556                  
557                   /* check if any of the providers for 'req' is installed */
558                   for (i = 0; (p = dp[i]) != 0; i++)
559                     {
560                       if (pool->solvables[p].repo == installed)
561                         break;          /* provider was installed */
562                     }
563                   /* didn't find an installed provider: previously broken dependency */
564                   if (!p)
565                     {
566                       POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", pool_dep2str(pool, req), pool_solvable2str(pool, s));
567                       continue;
568                     }
569                 }
570
571               if (!*dp)
572                 {
573                   /* nothing provides req! */
574                   POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", pool_solvable2str(pool, s), (Id)(s - pool->solvables), pool_dep2str(pool, req));
575                   addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req);
576                   continue;
577                 }
578
579               IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
580                 {
581                   POOL_DEBUG(SOLV_DEBUG_RULE_CREATION,"  %s requires %s\n", pool_solvable2str(pool, s), pool_dep2str(pool, req));
582                   for (i = 0; dp[i]; i++)
583                     POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "   provided by %s\n", pool_solvid2str(pool, dp[i]));
584                 }
585
586               /* add 'requires' dependency */
587               /* rule: (-requestor|provider1|provider2|...|providerN) */
588               addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req);
589
590               /* descend the dependency tree
591                  push all non-visited providers on the work queue */
592               if (m)
593                 {
594                   for (; *dp; dp++)
595                     {
596                       if (!MAPTST(m, *dp))
597                         queue_push(&workq, *dp);
598                     }
599                 }
600
601             } /* while, requirements of n */
602
603         } /* if, requirements */
604
605       /* that's all we check for src packages */
606       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
607         continue;
608
609       /*-----------------------------------------
610        * check conflicts of s
611        */
612
613       if (s->conflicts)
614         {
615           int ispatch = 0;
616
617           /* we treat conflicts in patches a bit differen:
618            * - nevr matching
619            * - multiversion handling
620            * XXX: we should really handle this different, looking
621            * at the name is a bad hack
622            */
623           if (!strncmp("patch:", pool_id2str(pool, s->name), 6))
624             ispatch = 1;
625           conp = s->repo->idarraydata + s->conflicts;
626           /* foreach conflicts of 's' */
627           while ((con = *conp++) != 0)
628             {
629               /* foreach providers of a conflict of 's' */
630               FOR_PROVIDES(p, pp, con)
631                 {
632                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
633                     continue;
634                   /* dontfix: dont care about conflicts with already installed packs */
635                   if (dontfix && pool->solvables[p].repo == installed)
636                     continue;
637                   /* p == n: self conflict */
638                   if (p == n && pool->forbidselfconflicts)
639                     {
640                       if (ISRELDEP(con))
641                         {
642                           Reldep *rd = GETRELDEP(pool, con);
643                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
644                             continue;
645                         }
646                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
647                     }
648                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
649                     {
650                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
651                       p = -makemultiversionconflict(solv, p, con);
652                     }
653                  /* rule: -n|-p: either solvable _or_ provider of conflict */
654                   addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con);
655                 }
656             }
657         }
658
659       /*-----------------------------------------
660        * check obsoletes and implicit obsoletes of a package
661        * if ignoreinstalledsobsoletes is not set, we're also checking
662        * obsoletes of installed packages (like newer rpm versions)
663        */
664       if ((!installed || s->repo != installed) || !pool->noinstalledobsoletes)
665         {
666           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
667           int isinstalled = (installed && s->repo == installed);
668           if (s->obsoletes && (!noobs || solv->keepexplicitobsoletes))
669             {
670               obsp = s->repo->idarraydata + s->obsoletes;
671               /* foreach obsoletes */
672               while ((obs = *obsp++) != 0)
673                 {
674                   /* foreach provider of an obsoletes of 's' */ 
675                   FOR_PROVIDES(p, pp, obs)
676                     {
677                       Solvable *ps = pool->solvables + p;
678                       if (p == n)
679                         continue;
680                       if (isinstalled && dontfix && ps->repo == installed)
681                         continue;       /* don't repair installed/installed problems */
682                       if (!pool->obsoleteusesprovides /* obsoletes are matched names, not provides */
683                           && !pool_match_nevr(pool, ps, obs))
684                         continue;
685                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
686                         continue;
687                       if (!isinstalled)
688                         addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs);
689                       else
690                         addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_INSTALLEDPKG_OBSOLETES, obs);
691                     }
692                 }
693             }
694           /* check implicit obsoletes
695            * for installed packages we only need to check installed/installed problems (and
696            * only when dontfix is not set), as the others are picked up when looking at the
697            * uninstalled package.
698            */
699           if (!isinstalled || !dontfix)
700             {
701               FOR_PROVIDES(p, pp, s->name)
702                 {
703                   Solvable *ps = pool->solvables + p;
704                   if (p == n)
705                     continue;
706                   if (isinstalled && ps->repo != installed)
707                     continue;
708                   /* we still obsolete packages with same nevra, like rpm does */
709                   /* (actually, rpm mixes those packages. yuck...) */
710                   if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
711                     continue;
712                   if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
713                     continue;
714                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
715                     continue;
716                   if (s->name == ps->name)
717                     addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0);
718                   else
719                     addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name);
720                 }
721             }
722         }
723
724       /*-----------------------------------------
725        * add recommends to the work queue
726        */
727       if (s->recommends && m)
728         {
729           recp = s->repo->idarraydata + s->recommends;
730           while ((rec = *recp++) != 0)
731             {
732               FOR_PROVIDES(p, pp, rec)
733                 if (!MAPTST(m, p))
734                   queue_push(&workq, p);
735             }
736         }
737       if (s->suggests && m)
738         {
739           sugp = s->repo->idarraydata + s->suggests;
740           while ((sug = *sugp++) != 0)
741             {
742               FOR_PROVIDES(p, pp, sug)
743                 if (!MAPTST(m, p))
744                   queue_push(&workq, p);
745             }
746         }
747     }
748   queue_free(&workq);
749 }
750
751
752 /*-------------------------------------------------------------------
753  * 
754  * Add rules for packages possibly selected in by weak dependencies
755  *
756  * m: already added solvables
757  */
758
759 void
760 solver_addrpmrulesforweak(Solver *solv, Map *m)
761 {
762   Pool *pool = solv->pool;
763   Solvable *s;
764   Id sup, *supp;
765   int i, n;
766
767   /* foreach solvable in pool */
768   for (i = n = 1; n < pool->nsolvables; i++, n++)
769     {
770       if (i == pool->nsolvables)                /* wrap i */
771         i = 1;
772       if (MAPTST(m, i))                         /* already added that one */
773         continue;
774
775       s = pool->solvables + i;
776       if (!pool_installable(pool, s))           /* only look at installable ones */
777         continue;
778
779       sup = 0;
780       if (s->supplements)
781         {
782           /* find possible supplements */
783           supp = s->repo->idarraydata + s->supplements;
784           while ((sup = *supp++) != 0)
785             if (dep_possible(solv, sup, m))
786               break;
787         }
788
789       /* if nothing found, check for enhances */
790       if (!sup && s->enhances)
791         {
792           supp = s->repo->idarraydata + s->enhances;
793           while ((sup = *supp++) != 0)
794             if (dep_possible(solv, sup, m))
795               break;
796         }
797       /* if nothing found, goto next solvables */
798       if (!sup)
799         continue;
800       solver_addrpmrulesforsolvable(solv, s, m);
801       n = 0;                    /* check all solvables again because we added solvables to m */
802     }
803 }
804
805
806 /*-------------------------------------------------------------------
807  * 
808  * add package rules for possible updates
809  * 
810  * s: solvable
811  * m: map of already visited solvables
812  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
813  */
814
815 void
816 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
817 {
818   Pool *pool = solv->pool;
819   int i;
820     /* queue and buffer for it */
821   Queue qs;
822   Id qsbuf[64];
823
824   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
825     /* find update candidates for 's' */
826   policy_findupdatepackages(solv, s, &qs, allow_all);
827     /* add rule for 's' if not already done */
828   if (!MAPTST(m, s - pool->solvables))
829     solver_addrpmrulesforsolvable(solv, s, m);
830     /* foreach update candidate, add rule if not already done */
831   for (i = 0; i < qs.count; i++)
832     if (!MAPTST(m, qs.elements[i]))
833       solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
834   queue_free(&qs);
835 }
836
837
838 /***********************************************************************
839  ***
840  ***  Update/Feature rule part
841  ***
842  ***  Those rules make sure an installed package isn't silently deleted
843  ***
844  ***/
845
846 static Id
847 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
848 {
849   Pool *pool = solv->pool;
850   int i;
851
852   policy_findupdatepackages(solv, s, qs, allow_all ? allow_all : 2);
853   if (!qs->count)
854     {
855       if (allow_all)
856         return 0;       /* orphaned, don't create feature rule */
857       /* check if this is an orphaned package */
858       policy_findupdatepackages(solv, s, qs, 1);
859       if (!qs->count)
860         return 0;       /* orphaned, don't create update rule */
861       qs->count = 0;
862       return -SYSTEMSOLVABLE;   /* supported but not installable */
863     }
864   if (allow_all)
865     return s - pool->solvables;
866   /* check if it is ok to keep the installed package */
867   for (i = 0; i < qs->count; i++)
868     {
869       Solvable *ns = pool->solvables + qs->elements[i];
870       if (s->evr == ns->evr && solvable_identical(s, ns))
871         return s - pool->solvables;
872     }
873   /* nope, it must be some other package */
874   return -SYSTEMSOLVABLE;
875 }
876
877 /* add packages from the dup repositories to the update candidates
878  * this isn't needed for the global dup mode as all packages are
879  * from dup repos in that case */
880 static void
881 addduppackages(Solver *solv, Solvable *s, Queue *qs)
882 {
883   Queue dupqs;
884   Id p, dupqsbuf[64];
885   int i;
886   int oldnoupdateprovide = solv->noupdateprovide;
887
888   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
889   solv->noupdateprovide = 1;
890   policy_findupdatepackages(solv, s, &dupqs, 2);
891   solv->noupdateprovide = oldnoupdateprovide;
892   for (i = 0; i < dupqs.count; i++)
893     {
894       p = dupqs.elements[i];
895       if (MAPTST(&solv->dupmap, p))
896         queue_pushunique(qs, p);
897     }
898   queue_free(&dupqs);
899 }
900
901 /*-------------------------------------------------------------------
902  * 
903  * add rule for update
904  *   (A|A1|A2|A3...)  An = update candidates for A
905  *
906  * s = (installed) solvable
907  */
908
909 void
910 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all)
911 {
912   /* installed packages get a special upgrade allowed rule */
913   Pool *pool = solv->pool;
914   Id p, d;
915   Queue qs;
916   Id qsbuf[64];
917
918   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
919   p = s - pool->solvables;
920   /* find update candidates for 's' */
921   if (solv->dupmap_all)
922     p = finddistupgradepackages(solv, s, &qs, allow_all);
923   else
924     policy_findupdatepackages(solv, s, &qs, allow_all);
925   if (!allow_all && !solv->dupmap_all && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
926     addduppackages(solv, s, &qs);
927
928   if (!allow_all && qs.count && solv->noobsoletes.size)
929     {
930       int i, j;
931
932       d = pool_queuetowhatprovides(pool, &qs);
933       /* filter out all noobsoletes packages as they don't update */
934       for (i = j = 0; i < qs.count; i++)
935         {
936           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
937             {
938               /* it's ok if they have same nevra */
939               Solvable *ps = pool->solvables + qs.elements[i];
940               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
941                 continue;
942             }
943           qs.elements[j++] = qs.elements[i];
944         }
945       if (j < qs.count)
946         {
947           if (d && solv->installed && s->repo == solv->installed &&
948               (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, s - pool->solvables - solv->installed->start))))
949             {
950               if (!solv->multiversionupdaters)
951                 solv->multiversionupdaters = solv_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
952               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
953             }
954           if (j == 0 && p == -SYSTEMSOLVABLE && solv->dupmap_all)
955             {
956               queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
957               j = qs.count;
958             }
959           qs.count = j;
960         }
961       else if (p != -SYSTEMSOLVABLE)
962         {
963           /* could fallthrough, but then we would do pool_queuetowhatprovides twice */
964           queue_free(&qs);
965           solver_addrule(solv, p, d);   /* allow update of s */
966           return;
967         }
968     }
969   if (qs.count && p == -SYSTEMSOLVABLE)
970     p = queue_shift(&qs);
971   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
972   queue_free(&qs);
973   solver_addrule(solv, p, d);   /* allow update of s */
974 }
975
976 static inline void 
977 disableupdaterule(Solver *solv, Id p)
978 {
979   Rule *r;
980
981   MAPSET(&solv->noupdate, p - solv->installed->start);
982   r = solv->rules + solv->updaterules + (p - solv->installed->start);
983   if (r->p && r->d >= 0)
984     solver_disablerule(solv, r);
985   r = solv->rules + solv->featurerules + (p - solv->installed->start);
986   if (r->p && r->d >= 0)
987     solver_disablerule(solv, r);
988   if (solv->bestrules_pkg)
989     {
990       int i, ni;
991       ni = solv->bestrules_end - solv->bestrules;
992       for (i = 0; i < ni; i++)
993         if (solv->bestrules_pkg[i] == p)
994           solver_disablerule(solv, solv->rules + solv->bestrules + i);
995     }
996 }
997
998 static inline void 
999 reenableupdaterule(Solver *solv, Id p)
1000 {
1001   Pool *pool = solv->pool;
1002   Rule *r;
1003
1004   MAPCLR(&solv->noupdate, p - solv->installed->start);
1005   r = solv->rules + solv->updaterules + (p - solv->installed->start);
1006   if (r->p)
1007     {    
1008       if (r->d < 0)
1009         {
1010           solver_enablerule(solv, r);
1011           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1012             {
1013               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1014               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1015             }
1016         }
1017     }
1018   else
1019     {
1020       r = solv->rules + solv->featurerules + (p - solv->installed->start);
1021       if (r->p && r->d < 0)
1022         {
1023           solver_enablerule(solv, r);
1024           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1025             {
1026               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1027               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1028             }
1029         }
1030     }
1031   if (solv->bestrules_pkg)
1032     {
1033       int i, ni;
1034       ni = solv->bestrules_end - solv->bestrules;
1035       for (i = 0; i < ni; i++)
1036         if (solv->bestrules_pkg[i] == p)
1037           solver_enablerule(solv, solv->rules + solv->bestrules + i);
1038     }
1039 }
1040
1041
1042 /***********************************************************************
1043  ***
1044  ***  Infarch rule part
1045  ***
1046  ***  Infarch rules make sure the solver uses the best architecture of
1047  ***  a package if multiple archetectures are available
1048  ***
1049  ***/
1050
1051 void
1052 solver_addinfarchrules(Solver *solv, Map *addedmap)
1053 {
1054   Pool *pool = solv->pool;
1055   int first, i, j;
1056   Id p, pp, a, aa, bestarch;
1057   Solvable *s, *ps, *bests;
1058   Queue badq, allowedarchs;
1059
1060   queue_init(&badq);
1061   queue_init(&allowedarchs);
1062   solv->infarchrules = solv->nrules;
1063   for (i = 1; i < pool->nsolvables; i++)
1064     {
1065       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1066         continue;
1067       s = pool->solvables + i;
1068       first = i;
1069       bestarch = 0;
1070       bests = 0;
1071       queue_empty(&allowedarchs);
1072       FOR_PROVIDES(p, pp, s->name)
1073         {
1074           ps = pool->solvables + p;
1075           if (ps->name != s->name || !MAPTST(addedmap, p))
1076             continue;
1077           if (p == i)
1078             first = 0;
1079           if (first)
1080             break;
1081           a = ps->arch;
1082           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1083           if (a != 1 && pool->installed && ps->repo == pool->installed)
1084             {
1085               if (!solv->dupmap_all && !(solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)))
1086                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
1087               continue;         /* ignore installed solvables when calculating the best arch */
1088             }
1089           if (a && a != 1 && (!bestarch || a < bestarch))
1090             {
1091               bestarch = a;
1092               bests = ps;
1093             }
1094         }
1095       if (first)
1096         continue;
1097       /* speed up common case where installed package already has best arch */
1098       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
1099         allowedarchs.count--;   /* installed arch is best */
1100       queue_empty(&badq);
1101       FOR_PROVIDES(p, pp, s->name)
1102         {
1103           ps = pool->solvables + p;
1104           if (ps->name != s->name || !MAPTST(addedmap, p))
1105             continue;
1106           a = ps->arch;
1107           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1108           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
1109             {
1110               if (pool->installed && ps->repo == pool->installed)
1111                 continue;       /* always ok to keep an installed package */
1112               for (j = 0; j < allowedarchs.count; j++)
1113                 {
1114                   aa = allowedarchs.elements[j];
1115                   if (ps->arch == aa)
1116                     break;
1117                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
1118                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
1119                     break;      /* compatible */
1120                 }
1121               if (j == allowedarchs.count)
1122                 queue_push(&badq, p);
1123             }
1124         }
1125       if (!badq.count)
1126         continue;
1127       /* block all solvables in the badq! */
1128       for (j = 0; j < badq.count; j++)
1129         {
1130           p = badq.elements[j];
1131           solver_addrule(solv, -p, 0);
1132         }
1133     }
1134   queue_free(&badq);
1135   queue_free(&allowedarchs);
1136   solv->infarchrules_end = solv->nrules;
1137 }
1138
1139 static inline void
1140 disableinfarchrule(Solver *solv, Id name)
1141 {
1142   Pool *pool = solv->pool;
1143   Rule *r;
1144   int i;
1145   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1146     {
1147       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1148         solver_disablerule(solv, r);
1149     }
1150 }
1151
1152 static inline void
1153 reenableinfarchrule(Solver *solv, Id name)
1154 {
1155   Pool *pool = solv->pool;
1156   Rule *r;
1157   int i;
1158   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1159     {
1160       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1161         {
1162           solver_enablerule(solv, r);
1163           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1164             {
1165               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1166               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1167             }
1168         }
1169     }
1170 }
1171
1172
1173 /***********************************************************************
1174  ***
1175  ***  Dup rule part
1176  ***
1177  ***  Dup rules make sure a package is selected from the specified dup
1178  ***  repositories if an update candidate is included in one of them.
1179  ***
1180  ***/
1181
1182 void
1183 solver_createdupmaps(Solver *solv)
1184 {
1185   Queue *job = &solv->job;
1186   Pool *pool = solv->pool;
1187   Repo *repo;
1188   Repo *installed = solv->installed;
1189   Id select, how, what, p, pi, pp, pip, obs, *obsp;
1190   Solvable *s, *ps;
1191   int i;
1192
1193   map_init(&solv->dupmap, pool->nsolvables);
1194   map_init(&solv->dupinvolvedmap, pool->nsolvables);
1195   for (i = 0; i < job->count; i += 2)
1196     {
1197       how = job->elements[i];
1198       select = job->elements[i] & SOLVER_SELECTMASK;
1199       what = job->elements[i + 1];
1200       switch (how & SOLVER_JOBMASK)
1201         {
1202         case SOLVER_DISTUPGRADE:
1203           if (select != SOLVER_SOLVABLE_REPO)
1204             {
1205               int haveinstalled;
1206               p = 0;
1207               if (installed)
1208                 {
1209                   FOR_JOB_SELECT(p, pp, select, what)
1210                     if (pool->solvables[p].repo == installed)
1211                       break;
1212                 }
1213               haveinstalled = p != 0;
1214               FOR_JOB_SELECT(p, pp, select, what)
1215                 {
1216                   Solvable *s = pool->solvables + p;
1217                   if (!s->repo)
1218                     continue;
1219                   if (haveinstalled && s->repo != installed)
1220                     continue;
1221                   if (s->repo != installed && !pool_installable(pool, s))
1222                     continue;
1223                   MAPSET(&solv->dupinvolvedmap, p);
1224                   if (!haveinstalled)
1225                     MAPSET(&solv->dupmap, p);
1226                   FOR_PROVIDES(pi, pip, s->name)
1227                     {
1228                       ps = pool->solvables + pi;
1229                       if (ps->name != s->name)
1230                         continue;
1231                       MAPSET(&solv->dupinvolvedmap, pi);
1232                       if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0)
1233                         {
1234                           if (!solv->bestupdatemap.size)
1235                             map_grow(&solv->bestupdatemap, installed->end - installed->start);
1236                           MAPSET(&solv->bestupdatemap, pi - installed->start);
1237                         }
1238                       if (haveinstalled && ps->repo != installed)
1239                         MAPSET(&solv->dupmap, pi);
1240                     }
1241                   if (haveinstalled)
1242                     {
1243                       if (solv->obsoletes && solv->obsoletes[p - installed->start])
1244                         {
1245                           Id *opp;
1246                           for (opp = solv->obsoletes_data + solv->obsoletes[p - installed->start]; (pi = *opp++) != 0;)
1247                             {
1248                               ps = pool->solvables + pi;
1249                               if (ps->repo == installed)
1250                                 continue;
1251                               MAPSET(&solv->dupinvolvedmap, pi);
1252                               MAPSET(&solv->dupmap, pi);
1253                             }
1254                         }
1255                     }
1256                   else if (s->obsoletes)
1257                     {
1258                       /* XXX: check obsoletes/provides combination */
1259                       obsp = s->repo->idarraydata + s->obsoletes;
1260                       while ((obs = *obsp++) != 0)
1261                         {
1262                           FOR_PROVIDES(pi, pp, obs)
1263                             {
1264                               Solvable *ps = pool->solvables + pi;
1265                               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1266                                 continue;
1267                               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1268                                 continue;
1269                               MAPSET(&solv->dupinvolvedmap, pi);
1270                               if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0)
1271                                 {
1272                                   if (!solv->bestupdatemap.size)
1273                                     map_grow(&solv->bestupdatemap, installed->end - installed->start);
1274                                   MAPSET(&solv->bestupdatemap, pi - installed->start);
1275                                 }
1276                             }
1277                         }
1278                     }
1279                 }
1280               break;
1281             }
1282           if (what <= 0 || what > pool->nrepos)
1283             break;
1284           repo = pool_id2repo(pool, what);
1285           FOR_REPO_SOLVABLES(repo, p, s)
1286             {
1287               if (repo != installed && !pool_installable(pool, s))
1288                 continue;
1289               MAPSET(&solv->dupmap, p);
1290               FOR_PROVIDES(pi, pip, s->name)
1291                 {
1292                   ps = pool->solvables + pi;
1293                   if (ps->name != s->name)
1294                     continue;
1295                   MAPSET(&solv->dupinvolvedmap, pi);
1296                   if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0)
1297                     {
1298                       if (!solv->bestupdatemap.size)
1299                         map_grow(&solv->bestupdatemap, installed->end - installed->start);
1300                       MAPSET(&solv->bestupdatemap, pi - installed->start);
1301                     }
1302                 }
1303               if (s->obsoletes)
1304                 {
1305                   /* XXX: check obsoletes/provides combination */
1306                   obsp = s->repo->idarraydata + s->obsoletes;
1307                   while ((obs = *obsp++) != 0)
1308                     {
1309                       FOR_PROVIDES(pi, pp, obs)
1310                         {
1311                           Solvable *ps = pool->solvables + pi;
1312                           if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1313                             continue;
1314                           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1315                             continue;
1316                           MAPSET(&solv->dupinvolvedmap, pi);
1317                           if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0)
1318                             {
1319                               if (!solv->bestupdatemap.size)
1320                                 map_grow(&solv->bestupdatemap, installed->end - installed->start);
1321                               MAPSET(&solv->bestupdatemap, pi - installed->start);
1322                             }
1323                         }
1324                     }
1325                 }
1326             }
1327           break;
1328         default:
1329           break;
1330         }
1331     }
1332   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
1333 }
1334
1335 void
1336 solver_freedupmaps(Solver *solv)
1337 {
1338   map_free(&solv->dupmap);
1339   /* we no longer free solv->dupinvolvedmap as we need it in
1340    * policy's priority pruning code. sigh. */
1341 }
1342
1343 void
1344 solver_addduprules(Solver *solv, Map *addedmap)
1345 {
1346   Pool *pool = solv->pool;
1347   Id p, pp;
1348   Solvable *s, *ps;
1349   int first, i;
1350
1351   solv->duprules = solv->nrules;
1352   for (i = 1; i < pool->nsolvables; i++)
1353     {
1354       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1355         continue;
1356       s = pool->solvables + i;
1357       first = i;
1358       FOR_PROVIDES(p, pp, s->name)
1359         {
1360           ps = pool->solvables + p;
1361           if (ps->name != s->name || !MAPTST(addedmap, p))
1362             continue;
1363           if (p == i)
1364             first = 0;
1365           if (first)
1366             break;
1367           if (!MAPTST(&solv->dupinvolvedmap, p))
1368             continue;
1369           if (solv->installed && ps->repo == solv->installed)
1370             {
1371               if (!solv->updatemap.size)
1372                 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
1373               MAPSET(&solv->updatemap, p - solv->installed->start);
1374               if (!MAPTST(&solv->dupmap, p))
1375                 {
1376                   Id ip, ipp;
1377                   /* is installed identical to a good one? */
1378                   FOR_PROVIDES(ip, ipp, ps->name)
1379                     {
1380                       Solvable *is = pool->solvables + ip;
1381                       if (!MAPTST(&solv->dupmap, ip))
1382                         continue;
1383                       if (is->evr == ps->evr && solvable_identical(ps, is))
1384                         break;
1385                     }
1386                   if (!ip)
1387                     solver_addrule(solv, -p, 0);        /* no match, sorry */
1388                   else
1389                     MAPSET(&solv->dupmap, p);           /* for best rules processing */
1390                 }
1391             }
1392           else if (!MAPTST(&solv->dupmap, p))
1393             solver_addrule(solv, -p, 0);
1394         }
1395     }
1396   solv->duprules_end = solv->nrules;
1397 }
1398
1399
1400 static inline void
1401 disableduprule(Solver *solv, Id name)
1402 {
1403   Pool *pool = solv->pool;
1404   Rule *r;
1405   int i;
1406   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++) 
1407     {    
1408       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1409         solver_disablerule(solv, r);
1410     }    
1411 }
1412
1413 static inline void 
1414 reenableduprule(Solver *solv, Id name)
1415 {
1416   Pool *pool = solv->pool;
1417   Rule *r;
1418   int i;
1419   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++) 
1420     {    
1421       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1422         {
1423           solver_enablerule(solv, r);
1424           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1425             {
1426               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1427               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1428             }
1429         }
1430     }
1431 }
1432
1433
1434 /***********************************************************************
1435  ***
1436  ***  Policy rule disabling/reenabling
1437  ***
1438  ***  Disable all policy rules that conflict with our jobs. If a job
1439  ***  gets disabled later on, reenable the involved policy rules again.
1440  ***
1441  ***/
1442
1443 #define DISABLE_UPDATE  1
1444 #define DISABLE_INFARCH 2
1445 #define DISABLE_DUP     3
1446
1447 /* 
1448  * add all installed packages that package p obsoletes to Queue q.
1449  * Package p is not installed. Also, we know that if
1450  * solv->keepexplicitobsoletes is not set, p is not in the noobs map.
1451  * Entries may get added multiple times.
1452  */
1453 static void
1454 add_obsoletes(Solver *solv, Id p, Queue *q)
1455 {
1456   Pool *pool = solv->pool;
1457   Repo *installed = solv->installed;
1458   Id p2, pp2;
1459   Solvable *s = pool->solvables + p;
1460   Id obs, *obsp;
1461   Id lastp2 = 0;
1462
1463   if (!solv->keepexplicitobsoletes || !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p)))
1464     {
1465       FOR_PROVIDES(p2, pp2, s->name)
1466         {
1467           Solvable *ps = pool->solvables + p2;
1468           if (ps->repo != installed)
1469             continue;
1470           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1471             continue;
1472           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 
1473             continue;
1474           queue_push(q, p2);
1475           lastp2 = p2;
1476         }
1477     }
1478   if (!s->obsoletes)
1479     return;
1480   obsp = s->repo->idarraydata + s->obsoletes;
1481   while ((obs = *obsp++) != 0)
1482     FOR_PROVIDES(p2, pp2, obs) 
1483       {
1484         Solvable *ps = pool->solvables + p2;
1485         if (ps->repo != installed)
1486           continue;
1487         if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1488           continue;
1489         if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) 
1490           continue;
1491         if (p2 == lastp2)
1492           continue;
1493         queue_push(q, p2);
1494         lastp2 = p2;
1495       }
1496 }
1497
1498 /*
1499  * Call add_obsoletes and intersect the result with the
1500  * elements in Queue q starting at qstart.
1501  * Assumes that it's the first call if qstart == q->count.
1502  * May use auxillary map m for the intersection process, all
1503  * elements of q starting at qstart must have their bit cleared.
1504  * (This is also true after the function returns.)
1505  */
1506 static void
1507 intersect_obsoletes(Solver *solv, Id p, Queue *q, int qstart, Map *m)
1508 {
1509   int i, j;
1510   int qcount = q->count;
1511
1512   add_obsoletes(solv, p, q);
1513   if (qcount == qstart)
1514     return;     /* first call */
1515   if (qcount == q->count)
1516     j = qstart; 
1517   else if (qcount == qstart + 1)
1518     {
1519       /* easy if there's just one element */
1520       j = qstart;
1521       for (i = qcount; i < q->count; i++)
1522         if (q->elements[i] == q->elements[qstart])
1523           {
1524             j++;        /* keep the element */
1525             break;
1526           }
1527     }
1528   else if (!m->size && q->count - qstart <= 8)
1529     {
1530       /* faster than a map most of the time */
1531       int k;
1532       for (i = j = qstart; i < qcount; i++)
1533         {
1534           Id ip = q->elements[i];
1535           for (k = qcount; k < q->count; k++)
1536             if (q->elements[k] == ip)
1537               {
1538                 q->elements[j++] = ip;
1539                 break;
1540               }
1541         }
1542     }
1543   else
1544     {
1545       /* for the really pathologic cases we use the map */
1546       Repo *installed = solv->installed;
1547       if (!m->size)
1548         map_init(m, installed->end - installed->start);
1549       for (i = qcount; i < q->count; i++)
1550         MAPSET(m, q->elements[i] - installed->start);
1551       for (i = j = qstart; i < qcount; i++)
1552         if (MAPTST(m, q->elements[i] - installed->start))
1553           {
1554             MAPCLR(m, q->elements[i] - installed->start);
1555             q->elements[j++] = q->elements[i];
1556           }
1557     }
1558   queue_truncate(q, j);
1559 }
1560
1561 static void
1562 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1563 {
1564   Pool *pool = solv->pool;
1565   Id select, p, pp;
1566   Repo *installed;
1567   Solvable *s;
1568   int i, j, set, qstart;
1569   Map omap;
1570
1571   installed = solv->installed;
1572   select = how & SOLVER_SELECTMASK;
1573   switch (how & SOLVER_JOBMASK)
1574     {
1575     case SOLVER_INSTALL:
1576       set = how & SOLVER_SETMASK;
1577       if (!(set & SOLVER_NOAUTOSET))
1578         {
1579           /* automatically add set bits by analysing the job */
1580           if (select == SOLVER_SOLVABLE_NAME)
1581             set |= SOLVER_SETNAME;
1582           if (select == SOLVER_SOLVABLE)
1583             set |= SOLVER_SETNAME | SOLVER_SETARCH | SOLVER_SETVENDOR | SOLVER_SETREPO | SOLVER_SETEVR;
1584           else if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(what))
1585             {
1586               Reldep *rd = GETRELDEP(pool, what);
1587               if (rd->flags == REL_EQ && select == SOLVER_SOLVABLE_NAME)
1588                 {
1589                   if (pool->disttype != DISTTYPE_DEB)
1590                     {
1591                       const char *evr = pool_id2str(pool, rd->evr);
1592                       if (strchr(evr, '-'))
1593                         set |= SOLVER_SETEVR;
1594                       else
1595                         set |= SOLVER_SETEV;
1596                     }
1597                   else
1598                     set |= SOLVER_SETEVR;
1599                 }
1600               if (rd->flags <= 7 && ISRELDEP(rd->name))
1601                 rd = GETRELDEP(pool, rd->name);
1602               if (rd->flags == REL_ARCH)
1603                 set |= SOLVER_SETARCH;
1604             }
1605         }
1606       else
1607         set &= ~SOLVER_NOAUTOSET;
1608       if (!set)
1609         return;
1610       if ((set & SOLVER_SETARCH) != 0 && solv->infarchrules != solv->infarchrules_end)
1611         {
1612           if (select == SOLVER_SOLVABLE)
1613             queue_push2(q, DISABLE_INFARCH, pool->solvables[what].name);
1614           else
1615             {
1616               int qcnt = q->count;
1617               /* does not work for SOLVER_SOLVABLE_ALL and SOLVER_SOLVABLE_REPO, but
1618                  they are not useful for SOLVER_INSTALL jobs anyway */
1619               FOR_JOB_SELECT(p, pp, select, what)
1620                 {
1621                   s = pool->solvables + p;
1622                   /* unify names */
1623                   for (i = qcnt; i < q->count; i += 2)
1624                     if (q->elements[i + 1] == s->name)
1625                       break;
1626                   if (i < q->count)
1627                     continue;
1628                   queue_push2(q, DISABLE_INFARCH, s->name);
1629                 }
1630             }
1631         }
1632       if ((set & SOLVER_SETREPO) != 0 && solv->duprules != solv->duprules_end)
1633         {
1634           if (select == SOLVER_SOLVABLE)
1635             queue_push2(q, DISABLE_DUP, pool->solvables[what].name);
1636           else
1637             {
1638               int qcnt = q->count;
1639               FOR_JOB_SELECT(p, pp, select, what)
1640                 {
1641                   s = pool->solvables + p;
1642                   /* unify names */
1643                   for (i = qcnt; i < q->count; i += 2)
1644                     if (q->elements[i + 1] == s->name)
1645                       break;
1646                   if (i < q->count)
1647                     continue;
1648                   queue_push2(q, DISABLE_DUP, s->name);
1649                 }
1650             }
1651         }
1652       if (!installed || installed->end == installed->start)
1653         return;
1654       /* now the hard part: disable some update rules */
1655
1656       /* first check if we have noobs or installed packages in the job */
1657       i = j = 0;
1658       FOR_JOB_SELECT(p, pp, select, what)
1659         {
1660           if (pool->solvables[p].repo == installed)
1661             j = p;
1662           else if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && !solv->keepexplicitobsoletes)
1663             return;
1664           i++;
1665         }
1666       if (j)    /* have installed packages */
1667         {
1668           /* this is for dupmap_all jobs, it can go away if we create
1669            * duprules for them */
1670           if (i == 1 && (set & SOLVER_SETREPO) != 0)
1671             queue_push2(q, DISABLE_UPDATE, j);
1672           return;
1673         }
1674
1675       omap.size = 0;
1676       qstart = q->count;
1677       FOR_JOB_SELECT(p, pp, select, what)
1678         {
1679           intersect_obsoletes(solv, p, q, qstart, &omap);
1680           if (q->count == qstart)
1681             break;
1682         }
1683       if (omap.size)
1684         map_free(&omap);
1685
1686       if (qstart == q->count)
1687         return;         /* nothing to prune */
1688
1689       /* convert result to (DISABLE_UPDATE, p) pairs */
1690       i = q->count;
1691       for (j = qstart; j < i; j++)
1692         queue_push(q, q->elements[j]);
1693       for (j = qstart; j < q->count; j += 2)
1694         {
1695           q->elements[j] = DISABLE_UPDATE;
1696           q->elements[j + 1] = q->elements[i++];
1697         }
1698
1699       /* now that we know which installed packages are obsoleted check each of them */
1700       if ((set & (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) == (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR))
1701         return;         /* all is set, nothing to do */
1702
1703       for (i = j = qstart; i < q->count; i += 2)
1704         {
1705           Solvable *is = pool->solvables + q->elements[i + 1];
1706           FOR_JOB_SELECT(p, pp, select, what)
1707             {
1708               int illegal = 0;
1709               s = pool->solvables + p;
1710               if ((set & SOLVER_SETEVR) != 0)
1711                 illegal |= POLICY_ILLEGAL_DOWNGRADE;    /* ignore */
1712               if ((set & SOLVER_SETNAME) != 0)
1713                 illegal |= POLICY_ILLEGAL_NAMECHANGE;   /* ignore */
1714               if ((set & SOLVER_SETARCH) != 0)
1715                 illegal |= POLICY_ILLEGAL_ARCHCHANGE;   /* ignore */
1716               if ((set & SOLVER_SETVENDOR) != 0)
1717                 illegal |= POLICY_ILLEGAL_VENDORCHANGE; /* ignore */
1718               illegal = policy_is_illegal(solv, is, s, illegal);
1719               if (illegal && illegal == POLICY_ILLEGAL_DOWNGRADE && (set & SOLVER_SETEV) != 0)
1720                 {
1721                   /* it's ok if the EV is different */
1722                   if (pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE_EVONLY) != 0)
1723                     illegal = 0;
1724                 }
1725               if (illegal)
1726                 break;
1727             }
1728           if (!p)
1729             {   
1730               /* no package conflicts with the update rule */
1731               /* thus keep the DISABLE_UPDATE */
1732               q->elements[j + 1] = q->elements[i + 1];
1733               j += 2;
1734             }
1735         }
1736       queue_truncate(q, j);
1737       return;
1738
1739     case SOLVER_ERASE:
1740       if (!installed)
1741         break;
1742       if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
1743         FOR_REPO_SOLVABLES(installed, p, s)
1744           queue_push2(q, DISABLE_UPDATE, p);
1745       FOR_JOB_SELECT(p, pp, select, what)
1746         if (pool->solvables[p].repo == installed)
1747           queue_push2(q, DISABLE_UPDATE, p);
1748       return;
1749     default:
1750       return;
1751     }
1752 }
1753
1754 /* disable all policy rules that are in conflict with our job list */
1755 void
1756 solver_disablepolicyrules(Solver *solv)
1757 {
1758   Queue *job = &solv->job;
1759   int i, j;
1760   Queue allq;
1761   Rule *r;
1762   Id lastjob = -1;
1763   Id allqbuf[128];
1764
1765   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1766
1767   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1768     {
1769       r = solv->rules + i;
1770       if (r->d < 0)     /* disabled? */
1771         continue;
1772       j = solv->ruletojob.elements[i - solv->jobrules];
1773       if (j == lastjob)
1774         continue;
1775       lastjob = j;
1776       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1777     }
1778   if (solv->cleandepsmap.size)
1779     {
1780       solver_createcleandepsmap(solv, &solv->cleandepsmap, 0);
1781       for (i = solv->installed->start; i < solv->installed->end; i++)
1782         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1783           queue_push2(&allq, DISABLE_UPDATE, i);
1784     }
1785   MAPZERO(&solv->noupdate);
1786   for (i = 0; i < allq.count; i += 2)
1787     {
1788       Id type = allq.elements[i], arg = allq.elements[i + 1];
1789       switch(type)
1790         {
1791         case DISABLE_UPDATE:
1792           disableupdaterule(solv, arg);
1793           break;
1794         case DISABLE_INFARCH:
1795           disableinfarchrule(solv, arg);
1796           break;
1797         case DISABLE_DUP:
1798           disableduprule(solv, arg);
1799           break;
1800         default:
1801           break;
1802         }
1803     }
1804   queue_free(&allq);
1805 }
1806
1807 /* we just disabled job #jobidx, now reenable all policy rules that were
1808  * disabled because of this job */
1809 void
1810 solver_reenablepolicyrules(Solver *solv, int jobidx)
1811 {
1812   Queue *job = &solv->job;
1813   int i, j;
1814   Queue q, allq;
1815   Rule *r;
1816   Id lastjob = -1;
1817   Id qbuf[32], allqbuf[128];
1818
1819   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1820   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1821   jobtodisablelist(solv, job->elements[jobidx - 1], job->elements[jobidx], &q);
1822   if (!q.count)
1823     return;
1824   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1825     {
1826       r = solv->rules + i;
1827       if (r->d < 0)     /* disabled? */
1828         continue;
1829       j = solv->ruletojob.elements[i - solv->jobrules];
1830       if (j == lastjob)
1831         continue;
1832       lastjob = j;
1833       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1834     }
1835   if (solv->cleandepsmap.size)
1836     {
1837       solver_createcleandepsmap(solv, &solv->cleandepsmap, 0);
1838       for (i = solv->installed->start; i < solv->installed->end; i++)
1839         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1840           queue_push2(&allq, DISABLE_UPDATE, i);
1841     }
1842   for (j = 0; j < q.count; j += 2)
1843     {
1844       Id type = q.elements[j], arg = q.elements[j + 1];
1845       for (i = 0; i < allq.count; i += 2)
1846         if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1847           break;
1848       if (i < allq.count)
1849         continue;       /* still disabled */
1850       switch(type)
1851         {
1852         case DISABLE_UPDATE:
1853           reenableupdaterule(solv, arg);
1854           break;
1855         case DISABLE_INFARCH:
1856           reenableinfarchrule(solv, arg);
1857           break;
1858         case DISABLE_DUP:
1859           reenableduprule(solv, arg);
1860           break;
1861         }
1862     }
1863   queue_free(&allq);
1864   queue_free(&q);
1865 }
1866
1867 /* we just removed a package from the cleandeps map, now reenable all policy rules that were
1868  * disabled because of this */
1869 void
1870 solver_reenablepolicyrules_cleandeps(Solver *solv, Id pkg)
1871 {
1872   Queue *job = &solv->job;
1873   int i, j;
1874   Queue allq;
1875   Rule *r;
1876   Id lastjob = -1;
1877   Id allqbuf[128];
1878
1879   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1880   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1881     {
1882       r = solv->rules + i;
1883       if (r->d < 0)     /* disabled? */
1884         continue;
1885       j = solv->ruletojob.elements[i - solv->jobrules];
1886       if (j == lastjob)
1887         continue;
1888       lastjob = j;
1889       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1890     }
1891   for (i = 0; i < allq.count; i += 2)
1892     if (allq.elements[i] == DISABLE_UPDATE && allq.elements[i + 1] == pkg)
1893       break;
1894   if (i == allq.count)
1895     reenableupdaterule(solv, pkg);
1896   queue_free(&allq);
1897 }
1898
1899
1900 /***********************************************************************
1901  ***
1902  ***  Rule info part, tell the user what the rule is about.
1903  ***
1904  ***/
1905
1906 static void
1907 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
1908 {
1909   Pool *pool = solv->pool;
1910   Rule *r;
1911   Id w2, op, od, ow2;
1912
1913   /* check if this creates the rule we're searching for */
1914   r = solv->rules + solv->ruleinfoq->elements[0];
1915   op = r->p;
1916   od = r->d < 0 ? -r->d - 1 : r->d;
1917   ow2 = 0;
1918
1919   /* normalize */
1920   w2 = d > 0 ? 0 : d;
1921   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
1922     {
1923       w2 = pool->whatprovidesdata[d];
1924       d = 0;
1925
1926     }
1927   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
1928     {
1929       w2 = p;
1930       p = d;
1931     }
1932
1933   if (d > 0)
1934     {
1935       if (p != op && !od)
1936         return;
1937       if (d != od)
1938         {
1939           Id *dp = pool->whatprovidesdata + d;
1940           Id *odp = pool->whatprovidesdata + od;
1941           while (*dp)
1942             if (*dp++ != *odp++)
1943               return;
1944           if (*odp)
1945             return;
1946         }
1947       w2 = 0;
1948       /* handle multiversion conflict rules */
1949       if (p < 0 && pool->whatprovidesdata[d] < 0)
1950         {
1951           w2 = pool->whatprovidesdata[d];
1952           /* XXX: free memory */
1953         }
1954     }
1955   else
1956     {
1957       if (od)
1958         return;
1959       ow2 = r->w2;
1960       if (p > w2)
1961         {
1962           if (w2 != op || p != ow2)
1963             return;
1964         }
1965       else
1966         {
1967           if (p != op || w2 != ow2)
1968             return;
1969         }
1970     }
1971   /* yep, rule matches. record info */
1972   queue_push(solv->ruleinfoq, type);
1973   if (type == SOLVER_RULE_RPM_SAME_NAME)
1974     {
1975       /* we normalize same name order */
1976       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
1977       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
1978     }
1979   else
1980     {
1981       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
1982       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
1983     }
1984   queue_push(solv->ruleinfoq, dep);
1985 }
1986
1987 static int
1988 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
1989 {
1990   const Id *a = ap, *b = bp;
1991   int r;
1992
1993   r = a[0] - b[0];
1994   if (r)
1995     return r;
1996   r = a[1] - b[1];
1997   if (r)
1998     return r;
1999   r = a[2] - b[2];
2000   if (r)
2001     return r;
2002   r = a[3] - b[3];
2003   if (r)
2004     return r;
2005   return 0;
2006 }
2007
2008 int
2009 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
2010 {
2011   Pool *pool = solv->pool;
2012   Rule *r = solv->rules + rid;
2013   int i, j;
2014
2015   queue_empty(rq);
2016   if (rid <= 0 || rid >= solv->rpmrules_end)
2017     {
2018       Id type, from, to, dep;
2019       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
2020       queue_push(rq, type);
2021       queue_push(rq, from);
2022       queue_push(rq, to);
2023       queue_push(rq, dep);
2024       return 1;
2025     }
2026   if (r->p >= 0)
2027     return 0;
2028   queue_push(rq, rid);
2029   solv->ruleinfoq = rq;
2030   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
2031   /* also try reverse direction for conflicts */
2032   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2033     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
2034   solv->ruleinfoq = 0;
2035   queue_shift(rq);
2036   /* now sort & unify em */
2037   if (!rq->count)
2038     return 0;
2039   solv_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
2040   /* throw out identical entries */
2041   for (i = j = 0; i < rq->count; i += 4)
2042     {
2043       if (j)
2044         {
2045           if (rq->elements[i] == rq->elements[j - 4] && 
2046               rq->elements[i + 1] == rq->elements[j - 3] &&
2047               rq->elements[i + 2] == rq->elements[j - 2] &&
2048               rq->elements[i + 3] == rq->elements[j - 1])
2049             continue;
2050         }
2051       rq->elements[j++] = rq->elements[i];
2052       rq->elements[j++] = rq->elements[i + 1];
2053       rq->elements[j++] = rq->elements[i + 2];
2054       rq->elements[j++] = rq->elements[i + 3];
2055     }
2056   rq->count = j;
2057   return j / 4;
2058 }
2059
2060 SolverRuleinfo
2061 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
2062 {
2063   Pool *pool = solv->pool;
2064   Rule *r = solv->rules + rid;
2065   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
2066
2067   if (fromp)
2068     *fromp = 0;
2069   if (top)
2070     *top = 0;
2071   if (depp)
2072     *depp = 0;
2073   if (rid > 0 && rid < solv->rpmrules_end)
2074     {
2075       Queue rq;
2076       int i;
2077
2078       if (r->p >= 0)
2079         return SOLVER_RULE_RPM;
2080       if (fromp)
2081         *fromp = -r->p;
2082       queue_init(&rq);
2083       queue_push(&rq, rid);
2084       solv->ruleinfoq = &rq;
2085       solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
2086       /* also try reverse direction for conflicts */
2087       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2088         solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
2089       solv->ruleinfoq = 0;
2090       type = SOLVER_RULE_RPM;
2091       for (i = 1; i < rq.count; i += 4)
2092         {
2093           Id qt, qo, qp, qd;
2094           qt = rq.elements[i];
2095           qp = rq.elements[i + 1];
2096           qo = rq.elements[i + 2];
2097           qd = rq.elements[i + 3];
2098           if (type == SOLVER_RULE_RPM || type > qt)
2099             {
2100               type = qt;
2101               if (fromp)
2102                 *fromp = qp;
2103               if (top)
2104                 *top = qo;
2105               if (depp)
2106                 *depp = qd;
2107             }
2108         }
2109       queue_free(&rq);
2110       return type;
2111     }
2112   if (rid >= solv->jobrules && rid < solv->jobrules_end)
2113     {
2114       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
2115       if (fromp)
2116         *fromp = jidx;
2117       if (top)
2118         *top = solv->job.elements[jidx];
2119       if (depp)
2120         *depp = solv->job.elements[jidx + 1];
2121       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE)
2122         {
2123           if ((solv->job.elements[jidx] & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_NAME)
2124             return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
2125           if ((solv->job.elements[jidx] & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_PROVIDES)
2126             return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
2127         }
2128       return SOLVER_RULE_JOB;
2129     }
2130   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2131     {
2132       if (fromp)
2133         *fromp = solv->installed->start + (rid - solv->updaterules);
2134       return SOLVER_RULE_UPDATE;
2135     }
2136   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2137     {
2138       if (fromp)
2139         *fromp = solv->installed->start + (rid - solv->featurerules);
2140       return SOLVER_RULE_FEATURE;
2141     }
2142   if (rid >= solv->duprules && rid < solv->duprules_end)
2143     {
2144       if (fromp)
2145         *fromp = -r->p;
2146       if (depp)
2147         *depp = pool->solvables[-r->p].name;
2148       return SOLVER_RULE_DISTUPGRADE;
2149     }
2150   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
2151     {
2152       if (fromp)
2153         *fromp = -r->p;
2154       if (depp)
2155         *depp = pool->solvables[-r->p].name;
2156       return SOLVER_RULE_INFARCH;
2157     }
2158   if (rid >= solv->bestrules && rid < solv->bestrules_end)
2159     {
2160       return SOLVER_RULE_BEST;
2161     }
2162   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2163     {
2164       return SOLVER_RULE_CHOICE;
2165     }
2166   if (rid >= solv->learntrules)
2167     {
2168       return SOLVER_RULE_LEARNT;
2169     }
2170   return SOLVER_RULE_UNKNOWN;
2171 }
2172
2173 SolverRuleinfo
2174 solver_ruleclass(Solver *solv, Id rid)
2175 {
2176   if (rid <= 0)
2177     return SOLVER_RULE_UNKNOWN;
2178   if (rid > 0 && rid < solv->rpmrules_end)
2179     return SOLVER_RULE_RPM;
2180   if (rid >= solv->jobrules && rid < solv->jobrules_end)
2181     return SOLVER_RULE_JOB;
2182   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2183     return SOLVER_RULE_UPDATE;
2184   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2185     return SOLVER_RULE_FEATURE;
2186   if (rid >= solv->duprules && rid < solv->duprules_end)
2187     return SOLVER_RULE_DISTUPGRADE;
2188   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
2189     return SOLVER_RULE_INFARCH;
2190   if (rid >= solv->bestrules && rid < solv->bestrules_end)
2191     return SOLVER_RULE_BEST;
2192   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2193     return SOLVER_RULE_CHOICE;
2194   if (rid >= solv->learntrules)
2195     return SOLVER_RULE_LEARNT;
2196   return SOLVER_RULE_UNKNOWN;
2197 }
2198
2199 void
2200 solver_ruleliterals(Solver *solv, Id rid, Queue *q)
2201 {
2202   Pool *pool = solv->pool;
2203   Id p, *pp;
2204   Rule *r;
2205
2206   queue_empty(q);
2207   r = solv->rules + rid;
2208   FOR_RULELITERALS(p, pp, r)
2209     if (p != -SYSTEMSOLVABLE)
2210       queue_push(q, p);
2211   if (!q->count)
2212     queue_push(q, -SYSTEMSOLVABLE);     /* hmm, better to return an empty result? */
2213 }
2214
2215 int
2216 solver_rule2jobidx(Solver *solv, Id rid)
2217 {
2218   if (rid < solv->jobrules || rid >= solv->jobrules_end)
2219     return 0;
2220   return solv->ruletojob.elements[rid - solv->jobrules] + 1;
2221 }
2222
2223 Id
2224 solver_rule2job(Solver *solv, Id rid, Id *whatp)
2225 {
2226   int idx;
2227   if (rid < solv->jobrules || rid >= solv->jobrules_end)
2228     {
2229       if (whatp)
2230         *whatp = 0;
2231       return 0;
2232     }
2233   idx = solv->ruletojob.elements[rid - solv->jobrules];
2234   if (whatp)
2235     *whatp = solv->job.elements[idx + 1];
2236   return solv->job.elements[idx];
2237 }
2238
2239 void
2240 solver_addchoicerules(Solver *solv)
2241 {
2242   Pool *pool = solv->pool;
2243   Map m, mneg;
2244   Rule *r;
2245   Queue q, qi;
2246   int i, j, rid, havechoice;
2247   Id p, d, *pp;
2248   Id p2, pp2;
2249   Solvable *s, *s2;
2250
2251   solv->choicerules = solv->nrules;
2252   if (!pool->installed)
2253     {
2254       solv->choicerules_end = solv->nrules;
2255       return;
2256     }
2257   solv->choicerules_ref = solv_calloc(solv->rpmrules_end, sizeof(Id));
2258   queue_init(&q);
2259   queue_init(&qi);
2260   map_init(&m, pool->nsolvables);
2261   map_init(&mneg, pool->nsolvables);
2262   /* set up negative assertion map from infarch and dup rules */
2263   for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++)
2264     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
2265       MAPSET(&mneg, -r->p);
2266   for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++)
2267     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
2268       MAPSET(&mneg, -r->p);
2269   for (rid = 1; rid < solv->rpmrules_end ; rid++)
2270     {
2271       r = solv->rules + rid;
2272       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0))
2273         continue;       /* only look at requires rules */
2274       /* solver_printrule(solv, SOLV_DEBUG_RESULT, r); */
2275       queue_empty(&q);
2276       queue_empty(&qi);
2277       havechoice = 0;
2278       FOR_RULELITERALS(p, pp, r)
2279         {
2280           if (p < 0)
2281             continue;
2282           s = pool->solvables + p;
2283           if (!s->repo)
2284             continue;
2285           if (s->repo == pool->installed)
2286             {
2287               queue_push(&q, p);
2288               continue;
2289             }
2290           /* check if this package is "blocked" by a installed package */
2291           s2 = 0;
2292           FOR_PROVIDES(p2, pp2, s->name)
2293             {
2294               s2 = pool->solvables + p2;
2295               if (s2->repo != pool->installed)
2296                 continue;
2297               if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
2298                 continue;
2299               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
2300                 continue;
2301               break;
2302             }
2303           if (p2)
2304             {
2305               /* found installed package p2 that we can update to p */
2306               if (MAPTST(&mneg, p))
2307                 continue;
2308               if (policy_is_illegal(solv, s2, s, 0))
2309                 continue;
2310               queue_push(&qi, p2);
2311               queue_push(&q, p);
2312               continue;
2313             }
2314           if (s->obsoletes)
2315             {
2316               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
2317               s2 = 0;
2318               while ((obs = *obsp++) != 0)
2319                 {
2320                   FOR_PROVIDES(p2, pp2, obs)
2321                     {
2322                       s2 = pool->solvables + p2;
2323                       if (s2->repo != pool->installed)
2324                         continue;
2325                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
2326                         continue;
2327                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
2328                         continue;
2329                       break;
2330                     }
2331                   if (p2)
2332                     break;
2333                 }
2334               if (obs)
2335                 {
2336                   /* found installed package p2 that we can update to p */
2337                   if (MAPTST(&mneg, p))
2338                     continue;
2339                   if (policy_is_illegal(solv, s2, s, 0))
2340                     continue;
2341                   queue_push(&qi, p2);
2342                   queue_push(&q, p);
2343                   continue;
2344                 }
2345             }
2346           /* package p is independent of the installed ones */
2347           havechoice = 1;
2348         }
2349       if (!havechoice || !q.count)
2350         continue;       /* no choice */
2351
2352       /* now check the update rules of the installed package.
2353        * if all packages of the update rules are contained in
2354        * the dependency rules, there's no need to set up the choice rule */
2355       map_empty(&m);
2356       FOR_RULELITERALS(p, pp, r)
2357         if (p > 0)
2358           MAPSET(&m, p);
2359       for (i = 0; i < qi.count; i++)
2360         {
2361           Rule *ur;
2362           if (!qi.elements[i])
2363             continue;
2364           ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start);
2365           if (!ur->p)
2366             ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start);
2367           if (!ur->p)
2368             continue;
2369           FOR_RULELITERALS(p, pp, ur)
2370             if (!MAPTST(&m, p))
2371               break;
2372           if (p)
2373             break;
2374           for (j = i + 1; j < qi.count; j++)
2375             if (qi.elements[i] == qi.elements[j])
2376               qi.elements[j] = 0;
2377         }
2378       if (i == qi.count)
2379         {
2380 #if 0
2381           printf("skipping choice ");
2382           solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid);
2383 #endif
2384           continue;
2385         }
2386       d = q.count ? pool_queuetowhatprovides(pool, &q) : 0;
2387       solver_addrule(solv, r->p, d);
2388       queue_push(&solv->weakruleq, solv->nrules - 1);
2389       solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid;
2390 #if 0
2391       printf("OLD ");
2392       solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid);
2393       printf("WEAK CHOICE ");
2394       solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + solv->nrules - 1);
2395 #endif
2396     }
2397   queue_free(&q);
2398   queue_free(&qi);
2399   map_free(&m);
2400   map_free(&mneg);
2401   solv->choicerules_end = solv->nrules;
2402 }
2403
2404 /* called when a choice rule is disabled by analyze_unsolvable. We also
2405  * have to disable all other choice rules so that the best packages get
2406  * picked */
2407 void
2408 solver_disablechoicerules(Solver *solv, Rule *r)
2409 {
2410   Id rid, p, *pp;
2411   Pool *pool = solv->pool;
2412   Map m;
2413   Rule *or;
2414
2415   or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2416   map_init(&m, pool->nsolvables);
2417   FOR_RULELITERALS(p, pp, or)
2418     if (p > 0)
2419       MAPSET(&m, p);
2420   FOR_RULELITERALS(p, pp, r)
2421     if (p > 0)
2422       MAPCLR(&m, p);
2423   for (rid = solv->choicerules; rid < solv->choicerules_end; rid++)
2424     {
2425       r = solv->rules + rid;
2426       if (r->d < 0)
2427         continue;
2428       or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2429       FOR_RULELITERALS(p, pp, or)
2430         if (p > 0 && MAPTST(&m, p))
2431           break;
2432       if (p)
2433         solver_disablerule(solv, r);
2434     }
2435 }
2436
2437 static void
2438 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
2439 {
2440   int i, j;
2441   Id p, *cp2; 
2442   for (i = j = 0; i < q->count; i++)
2443     {  
2444       p = q->elements[i];
2445       for (cp2 = cp; *cp2; cp2++)
2446         if (*cp2 == p)
2447           {
2448             q->elements[j++] = p;
2449             break;
2450           }
2451     }
2452   queue_truncate(q, j);
2453 }
2454
2455 static void
2456 prune_to_dup_packages(Solver *solv, Id p, Queue *q)
2457 {
2458   int i, j;
2459   for (i = j = 0; i < q->count; i++)
2460     {
2461       Id p = q->elements[i];
2462       if (MAPTST(&solv->dupmap, p))
2463         q->elements[j++] = p;
2464     }
2465   queue_truncate(q, j);
2466 }
2467
2468 void
2469 solver_addbestrules(Solver *solv, int havebestinstalljobs)
2470 {
2471   Pool *pool = solv->pool;
2472   Id p;
2473   Solvable *s;
2474   Repo *installed = solv->installed;
2475   Queue q, q2;
2476   Rule *r;
2477   Queue r2pkg;
2478   int i, oldcnt;
2479
2480   solv->bestrules = solv->nrules;
2481   if (!installed)
2482     {
2483       solv->bestrules_end = solv->nrules;
2484       return;
2485     }
2486   queue_init(&q);
2487   queue_init(&q2);
2488   queue_init(&r2pkg);
2489
2490   if (havebestinstalljobs)
2491     {
2492       for (i = 0; i < solv->job.count; i += 2)
2493         {
2494           if ((solv->job.elements[i] & (SOLVER_JOBMASK | SOLVER_FORCEBEST)) == (SOLVER_INSTALL | SOLVER_FORCEBEST))
2495             {
2496               int j;
2497               Id p2, *pp2;
2498               for (j = 0; j < solv->ruletojob.count; j++)
2499                 if (solv->ruletojob.elements[j] == i)
2500                   break;
2501               if (j == solv->ruletojob.count)
2502                 continue;
2503               r = solv->rules + solv->jobrules + j;
2504               queue_empty(&q);
2505               FOR_RULELITERALS(p2, pp2, r)
2506                 if (p2 > 0)
2507                   queue_push(&q, p2);
2508               if (!q.count)
2509                 continue;       /* orphaned */
2510               /* select best packages, just look at prio and version */
2511               oldcnt = q.count;
2512               policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND);
2513               if (q.count == oldcnt)
2514                 continue;       /* nothing filtered */
2515               p2 = queue_shift(&q);
2516               solver_addrule(solv, p2, q.count ? pool_queuetowhatprovides(pool, &q) : 0);
2517               queue_push(&r2pkg, -(solv->jobrules + j));
2518             }
2519         }
2520     }
2521
2522   if (solv->bestupdatemap_all || solv->bestupdatemap.size)
2523     {
2524       FOR_REPO_SOLVABLES(installed, p, s)
2525         {
2526           Id d, p2, *pp2;
2527           if (!solv->updatemap_all && (!solv->updatemap.size || !MAPTST(&solv->updatemap, p - installed->start)))
2528             continue;
2529           if (!solv->bestupdatemap_all && (!solv->bestupdatemap.size || !MAPTST(&solv->bestupdatemap, p - installed->start)))
2530             continue;
2531           queue_empty(&q);
2532           if (solv->bestobeypolicy)
2533             r = solv->rules + solv->updaterules + (p - installed->start);
2534           else
2535             {
2536               r = solv->rules + solv->featurerules + (p - installed->start);
2537               if (!r->p)        /* identical to update rule? */
2538                 r = solv->rules + solv->updaterules + (p - installed->start);
2539             }
2540           if (solv->multiversionupdaters && (d = solv->multiversionupdaters[p - installed->start]) != 0 && r == solv->rules + solv->updaterules + (p - installed->start))
2541             {
2542               /* need to check multiversionupdaters */
2543               if (r->p == p)    /* be careful with the dup case */
2544                 queue_push(&q, p);
2545               while ((p2 = pool->whatprovidesdata[d++]) != 0)
2546                 queue_push(&q, p2);
2547             }
2548           else
2549             {
2550               FOR_RULELITERALS(p2, pp2, r)
2551                 if (p2 > 0)
2552                   queue_push(&q, p2);
2553             }
2554           if (solv->update_targets && solv->update_targets->elements[p - installed->start])
2555             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q);
2556           if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
2557             prune_to_dup_packages(solv, p, &q);
2558           /* select best packages, just look at prio and version */
2559           policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND);
2560           if (!q.count)
2561             continue;   /* orphaned */
2562           if (solv->bestobeypolicy)
2563             {
2564               /* also filter the best of the feature rule packages and add them */
2565               r = solv->rules + solv->featurerules + (p - installed->start);
2566               if (r->p)
2567                 {
2568                   int j;
2569                   queue_empty(&q2);
2570                   FOR_RULELITERALS(p2, pp2, r)
2571                     if (p2 > 0)
2572                       queue_push(&q2, p2);
2573                   if (solv->update_targets && solv->update_targets->elements[p - installed->start])
2574                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q2);
2575                   if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
2576                     prune_to_dup_packages(solv, p, &q);
2577                   policy_filter_unwanted(solv, &q2, POLICY_MODE_RECOMMEND);
2578                   for (j = 0; j < q2.count; j++)
2579                     queue_pushunique(&q, q2.elements[j]);
2580                 }
2581             }
2582           p2 = queue_shift(&q);
2583           solver_addrule(solv, p2, q.count ? pool_queuetowhatprovides(pool, &q) : 0);
2584           queue_push(&r2pkg, p);
2585         }
2586     }
2587   if (r2pkg.count)
2588     {
2589       solv->bestrules_pkg = solv_calloc(r2pkg.count, sizeof(Id));
2590       memcpy(solv->bestrules_pkg, r2pkg.elements, r2pkg.count * sizeof(Id));
2591     }
2592   solv->bestrules_end = solv->nrules;
2593   queue_free(&q);
2594   queue_free(&q2);
2595   queue_free(&r2pkg);
2596 }
2597
2598 #undef CLEANDEPSDEBUG
2599
2600 /*
2601  * This functions collects all packages that are looked at
2602  * when a dependency is checked. We need it to "pin" installed
2603  * packages when removing a supplemented package in createcleandepsmap.
2604  * Here's an not uncommon example:
2605  *   A contains "Supplements: packageand(B, C)"
2606  *   B contains "Requires: A"
2607  * Now if we remove C, the supplements is no longer true,
2608  * thus we also remove A. Without the dep_pkgcheck function, we
2609  * would now also remove B, but this is wrong, as adding back
2610  * C doesn't make the supplements true again. Thus we "pin" B
2611  * when we remove A.
2612  * There's probably a better way to do this, but I haven't come
2613  * up with it yet ;)
2614  */
2615 static inline void
2616 dep_pkgcheck(Solver *solv, Id dep, Map *m, Queue *q)
2617 {
2618   Pool *pool = solv->pool;
2619   Id p, pp;
2620
2621   if (ISRELDEP(dep))
2622     {
2623       Reldep *rd = GETRELDEP(pool, dep);
2624       if (rd->flags >= 8)
2625         {
2626           if (rd->flags == REL_AND)
2627             {
2628               dep_pkgcheck(solv, rd->name, m, q);
2629               dep_pkgcheck(solv, rd->evr, m, q);
2630               return;
2631             }
2632           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
2633             return;
2634           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
2635             return;
2636         }
2637     }
2638   FOR_PROVIDES(p, pp, dep)
2639     if (!m || MAPTST(m, p))
2640       queue_push(q, p);
2641 }
2642
2643 /*
2644  * Find all installed packages that are no longer
2645  * needed regarding the current solver job.
2646  *
2647  * The algorithm is:
2648  * - remove pass: remove all packages that could have
2649  *   been dragged in by the obsoleted packages.
2650  *   i.e. if package A is obsolete and contains "Requires: B",
2651  *   also remove B, as installing A will have pulled in B.
2652  *   after this pass, we have a set of still installed packages
2653  *   with broken dependencies.
2654  * - add back pass:
2655  *   now add back all packages that the still installed packages
2656  *   require.
2657  *
2658  * The cleandeps packages are the packages removed in the first
2659  * pass and not added back in the second pass.
2660  *
2661  * If we search for unneeded packages (unneeded is true), we
2662  * simply remove all packages except the userinstalled ones in
2663  * the first pass.
2664  */
2665 static void
2666 solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded)
2667 {
2668   Pool *pool = solv->pool;
2669   Repo *installed = solv->installed;
2670   Queue *job = &solv->job;
2671   Map userinstalled;
2672   Map im;
2673   Map installedm;
2674   Rule *r;
2675   Id rid, how, what, select;
2676   Id p, pp, ip, *jp;
2677   Id req, *reqp, sup, *supp;
2678   Solvable *s;
2679   Queue iq;
2680   int i;
2681
2682   map_empty(cleandepsmap);
2683   if (!installed || installed->end == installed->start)
2684     return;
2685   map_init(&userinstalled, installed->end - installed->start);
2686   map_init(&im, pool->nsolvables);
2687   map_init(&installedm, pool->nsolvables);
2688   queue_init(&iq);
2689
2690   for (i = 0; i < job->count; i += 2)
2691     {
2692       how = job->elements[i];
2693       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
2694         {
2695           what = job->elements[i + 1];
2696           select = how & SOLVER_SELECTMASK;
2697           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
2698             FOR_REPO_SOLVABLES(installed, p, s)
2699               MAPSET(&userinstalled, p - installed->start);
2700           FOR_JOB_SELECT(p, pp, select, what)
2701             if (pool->solvables[p].repo == installed)
2702               MAPSET(&userinstalled, p - installed->start);
2703         }
2704     }
2705
2706   /* also add visible patterns to userinstalled for openSUSE */
2707   if (1)
2708     {
2709       Dataiterator di;
2710       dataiterator_init(&di, pool, 0, 0, SOLVABLE_ISVISIBLE, 0, 0);
2711       while (dataiterator_step(&di))
2712         {
2713           Id *dp;
2714           if (di.solvid <= 0)
2715             continue;
2716           s = pool->solvables + di.solvid;
2717           if (!s->requires)
2718             continue;
2719           if (!pool_installable(pool, s))
2720             continue;
2721           if (strncmp(pool_id2str(pool, s->name), "pattern:", 8) != 0)
2722             continue;
2723           dp = s->repo->idarraydata + s->requires;
2724           for (dp = s->repo->idarraydata + s->requires; *dp; dp++)
2725             FOR_PROVIDES(p, pp, *dp)
2726               if (pool->solvables[p].repo == installed)
2727                 {
2728                   if (strncmp(pool_id2str(pool, pool->solvables[p].name), "pattern", 7) != 0)
2729                     continue;
2730                   MAPSET(&userinstalled, p - installed->start);
2731                 }
2732         }
2733       dataiterator_free(&di);
2734     }
2735   if (1)
2736     {
2737       /* all products and their buddies are userinstalled */
2738       for (p = installed->start; p < installed->end; p++)
2739         {
2740           Solvable *s = pool->solvables + p;
2741           if (s->repo != installed)
2742             continue;
2743           if (!strncmp("product:", pool_id2str(pool, s->name), 8))
2744             {
2745               MAPSET(&userinstalled, p - installed->start);
2746               if (pool->nscallback)
2747                 {
2748                   Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, p);
2749                   if (buddy >= installed->start && buddy < installed->end && pool->solvables[buddy].repo == installed)
2750                     MAPSET(&userinstalled, buddy - installed->start);
2751                 }
2752             }
2753         }
2754     }
2755   
2756   /* add all positive elements (e.g. locks) to "userinstalled" */
2757   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2758     {
2759       r = solv->rules + rid;
2760       if (r->d < 0)
2761         continue;
2762       i = solv->ruletojob.elements[rid - solv->jobrules];
2763       if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
2764         continue;
2765       FOR_RULELITERALS(p, jp, r)
2766         if (p > 0 && pool->solvables[p].repo == installed)
2767           MAPSET(&userinstalled, p - installed->start);
2768     }
2769
2770   /* add all cleandeps candidates to iq */
2771   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2772     {
2773       r = solv->rules + rid;
2774       if (r->d < 0)
2775         continue;
2776       if (r->d == 0 && r->p < 0 && r->w2 == 0)
2777         {
2778           p = -r->p;
2779           if (pool->solvables[p].repo != installed)
2780             continue;
2781           MAPCLR(&userinstalled, p - installed->start);
2782           if (unneeded)
2783             continue;
2784           i = solv->ruletojob.elements[rid - solv->jobrules];
2785           how = job->elements[i];
2786           if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS))
2787             queue_push(&iq, p);
2788         }
2789       else if (r->p > 0)
2790         {
2791           if (unneeded)
2792             continue;
2793           i = solv->ruletojob.elements[rid - solv->jobrules];
2794           if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
2795             {
2796               /* check if the literals all obsolete some installed package */
2797               Map om;
2798               int iqstart;
2799
2800               /* just one installed literal */
2801               if (r->d == 0 && r->w2 == 0 && pool->solvables[r->p].repo == installed)
2802                 continue;
2803               /* noobs is bad */
2804               if (solv->noobsoletes.size && !solv->keepexplicitobsoletes)
2805                 {
2806                   FOR_RULELITERALS(p, jp, r)
2807                     if (MAPTST(&solv->noobsoletes, p))
2808                       break;
2809                   if (p)
2810                     continue;
2811                 }
2812
2813               om.size = 0;
2814               iqstart = iq.count;
2815               FOR_RULELITERALS(p, jp, r)
2816                 {
2817                   if (p < 0)
2818                     {
2819                       queue_truncate(&iq, iqstart);     /* abort */
2820                       break;
2821                     }
2822                   if (pool->solvables[p].repo == installed)
2823                     {
2824                       if (iq.count == iqstart)
2825                         queue_push(&iq, p);
2826                       else
2827                         {
2828                           for (i = iqstart; i < iq.count; i++)
2829                             if (iq.elements[i] == p)
2830                               break;
2831                           queue_truncate(&iq, iqstart);
2832                           if (i < iq.count)
2833                             queue_push(&iq, p);
2834                         }
2835                     }
2836                   else
2837                     intersect_obsoletes(solv, p, &iq, iqstart, &om);
2838                   if (iq.count == iqstart)
2839                     break;
2840                 }
2841               if (om.size)
2842                 map_free(&om);
2843             }
2844         }
2845     }
2846
2847   if (!unneeded)
2848     {
2849       if (solv->cleandeps_updatepkgs)
2850         for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
2851           queue_push(&iq, solv->cleandeps_updatepkgs->elements[i]);
2852     }
2853
2854   if (unneeded)
2855     queue_empty(&iq);   /* just in case... */
2856
2857   /* clear userinstalled bit for the packages we really want to delete/update */
2858   for (i = 0; i < iq.count; i++)
2859     {
2860       p = iq.elements[i];
2861       if (pool->solvables[p].repo != installed)
2862         continue;
2863       MAPCLR(&userinstalled, p - installed->start);
2864     }
2865
2866   for (p = installed->start; p < installed->end; p++)
2867     {
2868       if (pool->solvables[p].repo != installed)
2869         continue;
2870       MAPSET(&installedm, p);
2871       if (unneeded && !MAPTST(&userinstalled, p - installed->start))
2872         continue;
2873       MAPSET(&im, p);
2874     }
2875
2876 #ifdef CLEANDEPSDEBUG
2877   printf("REMOVE PASS\n");
2878 #endif
2879
2880   for (;;)
2881     {
2882       if (!iq.count)
2883         {
2884           if (unneeded)
2885             break;
2886           /* supplements pass */
2887           for (ip = solv->installed->start; ip < solv->installed->end; ip++)
2888             {
2889               if (!MAPTST(&installedm, ip))
2890                 continue;
2891               s = pool->solvables + ip;
2892               if (!s->supplements)
2893                 continue;
2894               if (!MAPTST(&im, ip))
2895                 continue;
2896               if (MAPTST(&userinstalled, ip - installed->start))
2897                 continue;
2898               supp = s->repo->idarraydata + s->supplements;
2899               while ((sup = *supp++) != 0)
2900                 if (dep_possible(solv, sup, &im))
2901                   break;
2902               if (!sup)
2903                 {
2904                   supp = s->repo->idarraydata + s->supplements;
2905                   while ((sup = *supp++) != 0)
2906                     if (dep_possible(solv, sup, &installedm))
2907                       {
2908                         /* no longer supplemented, also erase */
2909                         int iqcount = iq.count;
2910                         /* pin packages, see comment above dep_pkgcheck */
2911                         dep_pkgcheck(solv, sup, &im, &iq);
2912                         for (i = iqcount; i < iq.count; i++)
2913                           {
2914                             Id pqp = iq.elements[i];
2915                             if (pool->solvables[pqp].repo == installed)
2916                               MAPSET(&userinstalled, pqp - installed->start);
2917                           }
2918                         queue_truncate(&iq, iqcount);
2919 #ifdef CLEANDEPSDEBUG
2920                         printf("%s supplemented\n", pool_solvid2str(pool, ip));
2921 #endif
2922                         queue_push(&iq, ip);
2923                       }
2924                 }
2925             }
2926           if (!iq.count)
2927             break;
2928         }
2929       ip = queue_shift(&iq);
2930       s = pool->solvables + ip;
2931       if (!MAPTST(&im, ip))
2932         continue;
2933       if (!MAPTST(&installedm, ip))
2934         continue;
2935       if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start))
2936         continue;
2937       MAPCLR(&im, ip);
2938 #ifdef CLEANDEPSDEBUG
2939       printf("removing %s\n", pool_solvable2str(pool, s));
2940 #endif
2941       if (s->requires)
2942         {
2943           reqp = s->repo->idarraydata + s->requires;
2944           while ((req = *reqp++) != 0)
2945             {
2946               if (req == SOLVABLE_PREREQMARKER)
2947                 continue;
2948 #if 0
2949               /* count number of installed packages that match */
2950               count = 0;
2951               FOR_PROVIDES(p, pp, req)
2952                 if (MAPTST(&installedm, p))
2953                   count++;
2954               if (count > 1)
2955                 continue;
2956 #endif
2957               FOR_PROVIDES(p, pp, req)
2958                 {
2959                   if (MAPTST(&im, p))
2960                     {
2961 #ifdef CLEANDEPSDEBUG
2962                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2963 #endif
2964                       queue_push(&iq, p);
2965                     }
2966                 }
2967             }
2968         }
2969       if (s->recommends)
2970         {
2971           reqp = s->repo->idarraydata + s->recommends;
2972           while ((req = *reqp++) != 0)
2973             {
2974 #if 0
2975               count = 0;
2976               FOR_PROVIDES(p, pp, req)
2977                 if (MAPTST(&installedm, p))
2978                   count++;
2979               if (count > 1)
2980                 continue;
2981 #endif
2982               FOR_PROVIDES(p, pp, req)
2983                 {
2984                   if (MAPTST(&im, p))
2985                     {
2986 #ifdef CLEANDEPSDEBUG
2987                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2988 #endif
2989                       queue_push(&iq, p);
2990                     }
2991                 }
2992             }
2993         }
2994     }
2995
2996   /* turn userinstalled into remove set for pruning */
2997   map_empty(&userinstalled);
2998   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2999     {
3000       r = solv->rules + rid;
3001       if (r->p >= 0 || r->d != 0 || r->w2 != 0)
3002         continue;       /* disabled or not erase */
3003       p = -r->p;
3004       MAPCLR(&im, p);
3005       if (pool->solvables[p].repo == installed)
3006         MAPSET(&userinstalled, p - installed->start);
3007     }
3008   for (p = installed->start; p < installed->end; p++)
3009     if (MAPTST(&im, p))
3010       queue_push(&iq, p);
3011   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3012     {
3013       r = solv->rules + rid;
3014       if (r->d < 0)
3015         continue;
3016       FOR_RULELITERALS(p, jp, r)
3017         if (p > 0)
3018           queue_push(&iq, p);
3019     }
3020   /* also put directly addressed packages on the install queue
3021    * so we can mark patterns as installed */
3022   for (i = 0; i < job->count; i += 2)
3023     {
3024       how = job->elements[i];
3025       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
3026         {
3027           what = job->elements[i + 1];
3028           select = how & SOLVER_SELECTMASK;
3029           if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed)
3030             queue_push(&iq, what);
3031         }
3032     }
3033
3034 #ifdef CLEANDEPSDEBUG
3035   printf("ADDBACK PASS\n");
3036 #endif
3037   for (;;)
3038     {
3039       if (!iq.count)
3040         {
3041           /* supplements pass */
3042           for (ip = installed->start; ip < installed->end; ip++)
3043             {
3044               if (!MAPTST(&installedm, ip))
3045                 continue;
3046               if (MAPTST(&userinstalled, ip - installed->start))
3047                 continue;
3048               s = pool->solvables + ip;
3049               if (!s->supplements)
3050                 continue;
3051               if (MAPTST(&im, ip))
3052                 continue;
3053               supp = s->repo->idarraydata + s->supplements;
3054               while ((sup = *supp++) != 0)
3055                 if (dep_possible(solv, sup, &im))
3056                   break;
3057               if (sup)
3058                 {
3059 #ifdef CLEANDEPSDEBUG
3060                   printf("%s supplemented\n", pool_solvid2str(pool, ip));
3061 #endif
3062                   MAPSET(&im, ip);
3063                   queue_push(&iq, ip);
3064                 }
3065             }
3066           if (!iq.count)
3067             break;
3068         }
3069       ip = queue_shift(&iq);
3070       s = pool->solvables + ip;
3071 #ifdef CLEANDEPSDEBUG
3072       printf("adding back %s\n", pool_solvable2str(pool, s));
3073 #endif
3074       if (s->requires)
3075         {
3076           reqp = s->repo->idarraydata + s->requires;
3077           while ((req = *reqp++) != 0)
3078             {
3079               FOR_PROVIDES(p, pp, req)
3080                 {
3081                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
3082                     {
3083                       if (p == ip)
3084                         continue;
3085                       if (MAPTST(&userinstalled, p - installed->start))
3086                         continue;
3087 #ifdef CLEANDEPSDEBUG
3088                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3089 #endif
3090                       MAPSET(&im, p);
3091                       queue_push(&iq, p);
3092                     }
3093                 }
3094             }
3095         }
3096       if (s->recommends)
3097         {
3098           reqp = s->repo->idarraydata + s->recommends;
3099           while ((req = *reqp++) != 0)
3100             {
3101               FOR_PROVIDES(p, pp, req)
3102                 {
3103                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
3104                     {
3105                       if (p == ip)
3106                         continue;
3107                       if (MAPTST(&userinstalled, p - installed->start))
3108                         continue;
3109 #ifdef CLEANDEPSDEBUG
3110                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3111 #endif
3112                       MAPSET(&im, p);
3113                       queue_push(&iq, p);
3114                     }
3115                 }
3116             }
3117         }
3118     }
3119     
3120   queue_free(&iq);
3121   if (solv->cleandeps_updatepkgs)
3122     for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
3123       MAPSET(&im, solv->cleandeps_updatepkgs->elements[i]);
3124   if (solv->cleandeps_mistakes)
3125     for (i = 0; i < solv->cleandeps_mistakes->count; i++)
3126       MAPSET(&im, solv->cleandeps_mistakes->elements[i]);
3127   for (p = installed->start; p < installed->end; p++)
3128     {
3129       if (pool->solvables[p].repo != installed)
3130         continue;
3131       if (!MAPTST(&im, p))
3132         MAPSET(cleandepsmap, p - installed->start);
3133     }
3134   map_free(&im);
3135   map_free(&installedm);
3136   map_free(&userinstalled);
3137 }
3138
3139
3140 struct trj_data {
3141   Queue *edges;
3142   Id *low;
3143   Id idx;
3144   Id nstack;
3145   Id firstidx;
3146 };
3147
3148 /* Tarjan's SCC algorithm, slightly modifed */
3149 static void
3150 trj_visit(struct trj_data *trj, Id node)
3151 {
3152   Id *low = trj->low;
3153   Queue *edges = trj->edges;
3154   Id nnode, myidx, stackstart;
3155   int i;
3156
3157   low[node] = myidx = trj->idx++;
3158   low[(stackstart = trj->nstack++)] = node;
3159   for (i = edges->elements[node]; (nnode = edges->elements[i]) != 0; i++)
3160     {
3161       Id l = low[nnode];
3162       if (!l)
3163         {
3164           if (!edges->elements[edges->elements[nnode]])
3165             {
3166               trj->idx++;
3167               low[nnode] = -1;
3168               continue;
3169             }
3170           trj_visit(trj, nnode);
3171           l = low[nnode];
3172         }
3173       if (l < 0)
3174         continue;
3175       if (l < trj->firstidx)
3176         {
3177           int k;
3178           for (k = l; low[low[k]] == l; k++)
3179             low[low[k]] = -1;
3180         }
3181       else if (l < low[node])
3182         low[node] = l;
3183     }
3184   if (low[node] == myidx)
3185     {
3186       if (myidx != trj->firstidx)
3187         myidx = -1;
3188       for (i = stackstart; i < trj->nstack; i++)
3189         low[low[i]] = myidx;
3190       trj->nstack = stackstart;
3191     }
3192 }
3193
3194
3195 void
3196 solver_get_unneeded(Solver *solv, Queue *unneededq, int filtered)
3197 {
3198   Repo *installed = solv->installed;
3199   int i;
3200   Map cleandepsmap;
3201
3202   queue_empty(unneededq);
3203   if (!installed || installed->end == installed->start)
3204     return;
3205
3206   map_init(&cleandepsmap, installed->end - installed->start);
3207   solver_createcleandepsmap(solv, &cleandepsmap, 1);
3208   for (i = installed->start; i < installed->end; i++)
3209     if (MAPTST(&cleandepsmap, i - installed->start))
3210       queue_push(unneededq, i);
3211
3212   if (filtered && unneededq->count > 1)
3213     {
3214       Pool *pool = solv->pool;
3215       Queue edges;
3216       Id *nrequires;
3217       Map installedm;
3218       int j, pass, count = unneededq->count;
3219       Id *low;
3220
3221       map_init(&installedm, pool->nsolvables);
3222       for (i = installed->start; i < installed->end; i++)
3223         if (pool->solvables[i].repo == installed)
3224           MAPSET(&installedm, i);
3225
3226       nrequires = solv_calloc(count, sizeof(Id));
3227       queue_init(&edges);
3228       queue_prealloc(&edges, count * 4 + 10);   /* pre-size */
3229
3230       /*
3231        * Go through the solvables in the nodes queue and create edges for
3232        * all requires/recommends/supplements between the nodes.
3233        * The edges are stored in the edges queue, we add 1 to the node
3234        * index so that nodes in the edges queue are != 0 and we can
3235        * terminate the edge list with 0.
3236        * Thus for node element 5, the edges are stored starting at
3237        * edges.elements[6] and are 0-terminated.
3238        */
3239       /* leave first element zero to make things easier */
3240       /* also add trailing zero */
3241       queue_insertn(&edges, 0, 1 + count + 1);
3242
3243       /* first requires and recommends */
3244       for (i = 0; i < count; i++)
3245         {
3246           Solvable *s = pool->solvables + unneededq->elements[i];
3247           edges.elements[i + 1] = edges.count;
3248           for (pass = 0; pass < 2; pass++)
3249             {
3250               int num = 0;
3251               unsigned int off = pass == 0 ? s->requires : s->recommends;
3252               Id p, pp, *dp;
3253               if (off)
3254                 for (dp = s->repo->idarraydata + off; *dp; dp++)
3255                   FOR_PROVIDES(p, pp, *dp)
3256                     {
3257                       Solvable *sp = pool->solvables + p;
3258                       if (s == sp || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start))
3259                         continue;
3260                       for (j = 0; j < count; j++)
3261                         if (p == unneededq->elements[j])
3262                           break;
3263                       if (j == count)
3264                         continue;
3265                       if (num && edges.elements[edges.count - 1] == j + 1)
3266                         continue;
3267                       queue_push(&edges, j + 1);
3268                       num++;
3269                     }
3270                 if (pass == 0)
3271                   nrequires[i] = num;
3272             }
3273           queue_push(&edges, 0);
3274         }
3275 #if 0
3276       printf("requires + recommends\n");
3277       for (i = 0; i < count; i++)
3278         {
3279           int j;
3280           printf("  %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
3281           for (j = edges.elements[i + 1]; edges.elements[j]; j++)
3282             printf("    - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
3283         }
3284 #endif
3285
3286       /* then add supplements */
3287       for (i = 0; i < count; i++)
3288         {
3289           Solvable *s = pool->solvables + unneededq->elements[i];
3290           if (s->supplements)
3291             {
3292               Id *dp;
3293               int k;
3294               for (dp = s->repo->idarraydata + s->supplements; *dp; dp++)
3295                 if (dep_possible(solv, *dp, &installedm))
3296                   {
3297                     Queue iq;
3298                     Id iqbuf[16];
3299                     queue_init_buffer(&iq, iqbuf, sizeof(iqbuf)/sizeof(*iqbuf));
3300                     dep_pkgcheck(solv, *dp, 0, &iq);
3301                     for (k = 0; k < iq.count; k++)
3302                       {
3303                         Id p = iq.elements[k];
3304                         Solvable *sp = pool->solvables + p;
3305                         if (p == unneededq->elements[i] || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start))
3306                           continue;
3307                         for (j = 0; j < count; j++)
3308                           if (p == unneededq->elements[j])
3309                             break;
3310                         /* now add edge from j + 1 to i + 1 */
3311                         queue_insert(&edges, edges.elements[j + 1] + nrequires[j], i + 1);
3312                         /* addapt following edge pointers */
3313                         for (k = j + 2; k < count + 2; k++)
3314                           edges.elements[k]++;
3315                       }
3316                     queue_free(&iq);
3317                   }
3318             }
3319         }
3320 #if 0
3321       /* print result */
3322       printf("+ supplements\n");
3323       for (i = 0; i < count; i++)
3324         {
3325           int j;
3326           printf("  %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
3327           for (j = edges.elements[i + 1]; edges.elements[j]; j++)
3328             printf("    - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
3329     }
3330 #endif
3331       map_free(&installedm);
3332
3333       /* now run SCC algo two times, first with requires+recommends+supplements,
3334        * then again without the requires. We run it the second time to get rid
3335        * of packages that got dragged in via recommends/supplements */
3336       /*
3337        * low will contain the result of the SCC search.
3338        * it must be of at least size 2 * (count + 1) and
3339        * must be zero initialized.
3340        * The layout is:
3341        *    0  low low ... low stack stack ...stack 0
3342        *            count              count
3343        */
3344       low = solv_calloc(count + 1, 2 * sizeof(Id));
3345       for (pass = 0; pass < 2; pass++)
3346         {
3347           struct trj_data trj;
3348           if (pass)
3349             {
3350               memset(low, 0, (count + 1) * (2 * sizeof(Id)));
3351               for (i = 0; i < count; i++)
3352                 {
3353                   edges.elements[i + 1] += nrequires[i];
3354                   if (!unneededq->elements[i])
3355                     low[i + 1] = -1;    /* ignore this node */
3356                 }
3357             }
3358           trj.edges = &edges;
3359           trj.low = low;
3360           trj.idx = count + 1;  /* stack starts here */
3361           for (i = 1; i <= count; i++)
3362             {
3363               if (low[i])
3364                 continue;
3365               if (edges.elements[edges.elements[i]])
3366                 {
3367                   trj.firstidx = trj.nstack = trj.idx;
3368                   trj_visit(&trj, i);
3369                 }
3370               else
3371                 {
3372                   Id myidx = trj.idx++;
3373                   low[i] = myidx;
3374                   low[myidx] = i;
3375                 }
3376             }
3377           /* prune packages */
3378           for (i = 0; i < count; i++)
3379             if (low[i + 1] <= 0)
3380               unneededq->elements[i] = 0;
3381         }
3382       solv_free(low);
3383       solv_free(nrequires);
3384       queue_free(&edges);
3385
3386       /* finally remove all pruned entries from unneededq */
3387       for (i = j = 0; i < count; i++)
3388         if (unneededq->elements[i])
3389           unneededq->elements[j++] = unneededq->elements[i];
3390       queue_truncate(unneededq, j);
3391     }
3392   map_free(&cleandepsmap);
3393 }
3394
3395 /* EOF */