d4ad920171550a1cc9fc8ed7cc6aded6be7362ab
[platform/upstream/libsolv.git] / src / policy.c
1 /*
2  * Copyright (c) 2007, Novell Inc.
3  *
4  * This program is licensed under the BSD license, read LICENSE.BSD
5  * for further information
6  */
7
8 /*
9  * Generic policy interface for SAT solver
10  *
11  */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <unistd.h>
16 #include <string.h>
17
18 #include "solver.h"
19 #include "evr.h"
20 #include "policy.h"
21 #include "poolvendor.h"
22 #include "poolarch.h"
23
24
25 static Solver *prune_best_version_arch_sortcmp_data;
26
27 /*-----------------------------------------------------------------*/
28
29 /*
30  * prep for prune_best_version_arch
31  *   sort by name
32  */
33
34 static int
35 prune_best_version_arch_sortcmp(const void *ap, const void *bp)
36 {
37   Solver *solv = prune_best_version_arch_sortcmp_data;
38   Pool *pool = solv->pool;
39   int r;
40   Id a = *(Id *)ap;
41   Id b = *(Id *)bp;
42   r = pool->solvables[a].name - pool->solvables[b].name;
43   if (r)
44     {
45       const char *na, *nb;
46       /* different names. We use real strcmp here so that the result
47        * is not depending on some random solvable order */
48       na = id2str(pool, pool->solvables[a].name);
49       nb = id2str(pool, pool->solvables[b].name);
50       /* bring patterns to the front */
51       /* XXX: no longer needed? */
52       if (!strncmp(na, "pattern:", 8))
53         {
54           if (strncmp(nb, "pattern:", 8))
55             return -1;
56         }
57       else if (!strncmp(nb, "pattern:", 8))
58         {
59           if (strncmp(na, "pattern:", 8))
60             return 1;
61         }
62       return strcmp(na, nb);
63     }
64   /* the same name */
65   if (pool->solvables[a].evr == pool->solvables[b].evr && solv->installed)
66     {
67         /* prefer installed solvables */
68       if (pool->solvables[a].repo == solv->installed)
69         return -1;
70       if (pool->solvables[b].repo == solv->installed)
71         return 1;       
72     }
73   return a - b;
74 }
75
76
77 /*
78  * prune to repository with highest priority
79  * 
80  */
81
82 static void
83 prune_to_highest_prio(Pool *pool, Queue *plist)
84 {
85   int i, j;
86   Solvable *s;
87   int bestprio = 0;
88
89   /* prune to highest priority */
90   for (i = 0; i < plist->count; i++)  /* find highest prio in queue */
91     {
92       s = pool->solvables + plist->elements[i];
93       if (i == 0 || s->repo->priority > bestprio)
94         bestprio = s->repo->priority;
95     }
96   for (i = j = 0; i < plist->count; i++) /* remove all with lower prio */
97     {
98       s = pool->solvables + plist->elements[i];
99       if (s->repo->priority == bestprio)
100         plist->elements[j++] = plist->elements[i];
101     }
102   plist->count = j;
103 }
104
105
106 /*
107  * prune_to_recommended
108  *
109  * XXX: should we prune to requires/suggests that are already
110  * fulfilled by other packages?
111  */
112
113 static void
114 prune_to_recommended(Solver *solv, Queue *plist)
115 {
116   Pool *pool = solv->pool;
117   int i, j;
118   Solvable *s;
119   Id p, *pp, rec, *recp, sug, *sugp;
120
121   if (solv->recommends_index < 0)
122     {
123       MAPZERO(&solv->recommendsmap);
124       MAPZERO(&solv->suggestsmap);
125       solv->recommends_index = 0;
126     }
127   while (solv->recommends_index < solv->decisionq.count)
128     {
129       p = solv->decisionq.elements[solv->recommends_index++];
130       if (p < 0)
131         continue;
132       s = pool->solvables + p;
133       if (s->recommends)
134         {
135           recp = s->repo->idarraydata + s->recommends;
136           while ((rec = *recp++) != 0)
137             FOR_PROVIDES(p, pp, rec)
138               MAPSET(&solv->recommendsmap, p);
139         }
140       if (s->suggests)
141         {
142           sugp = s->repo->idarraydata + s->suggests;
143           while ((sug = *sugp++) != 0)
144             FOR_PROVIDES(p, pp, sug)
145               MAPSET(&solv->suggestsmap, p);
146         }
147     }
148   /* prune to recommended/supplemented */
149   for (i = j = 0; i < plist->count; i++)
150     {
151       p = plist->elements[i];
152       if (MAPTST(&solv->recommendsmap, p))
153         {
154           plist->elements[j++] = p;
155           continue;
156         }
157       if (solver_is_supplementing(solv, pool->solvables + p))
158         plist->elements[j++] = p;
159     }
160   if (j)
161     plist->count = j;
162
163   /* prune to suggested/enhanced*/
164   if (plist->count < 2)
165     return;
166   for (i = j = 0; i < plist->count; i++)
167     {
168       p = plist->elements[i];
169       if (MAPTST(&solv->suggestsmap, p))
170         {
171           plist->elements[j++] = p;
172           continue;
173         }
174       if (solver_is_enhancing(solv, pool->solvables + p))
175         plist->elements[j++] = p;
176     }
177   if (j)
178     plist->count = j;
179 }
180
181 void
182 prune_to_best_arch(Pool *pool, Queue *plist)
183 {
184   Id a, bestscore;
185   Solvable *s;
186   int i, j;
187
188   if (!pool->id2arch || plist->count < 2)
189     return;
190   bestscore = 0;
191   for (i = 0; i < plist->count; i++)
192     {
193       s = pool->solvables + plist->elements[i];
194       a = s->arch;
195       a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
196       if (a && a != 1 && (!bestscore || a < bestscore))
197         bestscore = a;
198     }
199   for (i = j = 0; i < plist->count; i++)
200     {
201       s = pool->solvables + plist->elements[i];
202       a = s->arch;
203       if (a > pool->lastarch)
204         continue;
205       a = pool->id2arch[a];
206       /* a == 1 -> noarch */
207       if (a != 1 && ((a ^ bestscore) & 0xffff0000) != 0)
208         continue;
209       plist->elements[j++] = plist->elements[i];
210     }
211   if (j)
212     plist->count = j;
213 }
214
215 /*
216  * prune_best_version_arch
217  *
218  * sort list of packages (given through plist) by name and evr
219  * return result through plist
220  *
221  */
222
223 void
224 prune_to_best_version(Solver *solv, Queue *plist)
225 {
226   Pool *pool = solv->pool;
227   Id best = ID_NULL;
228   int i, j;
229   Solvable *s;
230
231   if (plist->count < 2)         /* no need to prune for a single entry */
232     return;
233   POOL_DEBUG(SAT_DEBUG_POLICY, "prune_to_best_version %d\n", plist->count);
234
235   prune_best_version_arch_sortcmp_data = solv;
236   /* sort by name first, prefer installed */
237   qsort(plist->elements, plist->count, sizeof(Id), prune_best_version_arch_sortcmp);
238
239   /* delete obsoleted. hmm, looks expensive! */
240   /* FIXME maybe also check provides depending on noupdateprovide? */
241   /* FIXME do not prune cycles */
242   for (i = 0; i < plist->count; i++)
243     {
244       Id p, *pp, obs, *obsp;
245       s = pool->solvables + plist->elements[i];
246       if (!s->obsoletes)
247         continue;
248       obsp = s->repo->idarraydata + s->obsoletes;
249       while ((obs = *obsp++) != 0)
250         {
251           FOR_PROVIDES(p, pp, obs)
252             {
253               if (pool->solvables[p].name == s->name)
254                 continue;
255               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
256                 continue;
257               for (j = 0; j < plist->count; j++)
258                 {
259                   if (i == j)
260                     continue;
261                   if (plist->elements[j] == p)
262                     plist->elements[j] = 0;
263                 }
264             }
265         }
266     }
267   for (i = j = 0; i < plist->count; i++)
268     if (plist->elements[i])
269       plist->elements[j++] = plist->elements[i];
270   plist->count = j;
271
272   /* now find best 'per name' */
273   for (i = j = 0; i < plist->count; i++)
274     {
275       s = pool->solvables + plist->elements[i];
276
277       POOL_DEBUG(SAT_DEBUG_POLICY, "- %s[%s]\n",
278                  solvable2str(pool, s),
279                  (solv->installed && s->repo == solv->installed) ? "installed" : "not installed");
280
281       if (!best)                       /* if no best yet, the current is best */
282         {
283           best = plist->elements[i];
284           continue;
285         }
286
287       /* name switch: re-init */
288       if (pool->solvables[best].name != s->name)   /* new name */
289         {
290           plist->elements[j++] = best; /* move old best to front */
291           best = plist->elements[i];   /* take current as new best */
292           continue;
293         }
294
295       if (pool->solvables[best].evr != s->evr)   /* compare evr */
296         {
297           if (evrcmp(pool, pool->solvables[best].evr, s->evr, EVRCMP_MATCH_RELEASE) < 0)
298             best = plist->elements[i];
299         }
300     }
301
302   if (best == ID_NULL)
303     best = plist->elements[0];
304
305   plist->elements[j++] = best;
306   plist->count = j;
307 }
308
309
310 /* legacy, do not use anymore!
311  * (rates arch higher than version, but thats a policy)
312  */
313
314 void
315 prune_best_arch_name_version(Solver *solv, Pool *pool, Queue *plist)
316 {
317   if (solv && solv->bestSolvableCb)
318     { /* The application is responsible for */
319       return solv->bestSolvableCb(solv->pool, plist);
320     }
321
322   if (plist->count > 1)
323     prune_to_best_arch(pool, plist);
324   if (plist->count > 1)
325     prune_to_best_version(solv, plist);
326 }
327
328
329 void
330 policy_filter_unwanted(Solver *solv, Queue *plist, Id inst, int mode)
331 {
332   Pool *pool = solv->pool;
333   if (plist->count > 1 && mode != POLICY_MODE_SUGGEST)
334     prune_to_highest_prio(pool, plist);
335   if (plist->count > 1 && mode == POLICY_MODE_CHOOSE)
336     prune_to_recommended(solv, plist);
337   /* FIXME: do this different! */
338   if (inst)
339     queue_push(plist, inst);
340
341   prune_best_arch_name_version(solv, pool, plist);
342 }
343
344
345 int
346 policy_illegal_archchange(Solver *solv, Solvable *s1, Solvable *s2)
347 {
348   Pool *pool = solv->pool;
349   Id a1 = s1->arch, a2 = s2->arch;
350
351   if (solv && solv->archCheckCb)
352     { /* The application is responsible for */
353       return solv->archCheckCb(solv->pool, s1, s2);
354     }
355
356   /* we allow changes to/from noarch */
357   if (a1 == a2 || a1 == ARCH_NOARCH || a2 == ARCH_NOARCH)
358     return 0;
359   if (!pool->id2arch)
360     return 0;
361   a1 = a1 <= pool->lastarch ? pool->id2arch[a1] : 0;
362   a2 = a2 <= pool->lastarch ? pool->id2arch[a2] : 0;
363   if (((a1 ^ a2) & 0xffff0000) != 0)
364     return 1;
365   return 0;
366 }
367
368 int
369 policy_illegal_vendorchange(Solver *solv, Solvable *s1, Solvable *s2)
370 {
371   Pool *pool = solv->pool;
372   Id vendormask1, vendormask2;
373
374   if (solv && solv->vendorCheckCb)
375    {   /* The application is responsible for */
376      return solv->vendorCheckCb(solv->pool, s1, s2);
377    }
378
379   if (s1->vendor == s2->vendor)
380     return 0;
381   vendormask1 = pool_vendor2mask(pool, s1->vendor);
382   if (!vendormask1)
383     return 0;
384   vendormask2 = pool_vendor2mask(pool, s2->vendor);
385   if ((vendormask1 & vendormask2) == 0)
386     return 0;
387   return 1;
388 }
389
390
391 /*
392  * find update candidates
393  * 
394  * s: solvable to be updated
395  * qs: [out] queue to hold Ids of candidates
396  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
397  * 
398  */
399 void
400 policy_findupdatepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
401 {
402   /* installed packages get a special upgrade allowed rule */
403   Pool *pool = solv->pool;
404   Id p, *pp, n, p2, *pp2;
405   Id obs, *obsp;
406   Solvable *ps;
407   Id vendormask;
408
409   queue_empty(qs);
410
411   if (solv && solv->updateCandidateCb)
412     { /* The application is responsible for */
413       return solv->updateCandidateCb(solv->pool, s, qs);
414     }
415
416   /*
417    * s = solvable ptr
418    * n = solvable Id
419    */
420   n = s - pool->solvables;
421   vendormask = pool_vendor2mask(pool, s->vendor);
422
423   /*
424    * look for updates for s
425    */
426   FOR_PROVIDES(p, pp, s->name)  /* every provider of s' name */
427     {
428       if (p == n)               /* skip itself */
429         continue;
430
431       ps = pool->solvables + p;
432       if (s->name == ps->name)  /* name match */
433         {
434           if (!allow_all)
435             {
436               if (!solv->allowdowngrade && evrcmp(pool, s->evr, ps->evr, EVRCMP_MATCH_RELEASE) > 0)
437                 continue;
438               if (!solv->allowarchchange && s->arch != ps->arch && policy_illegal_archchange(solv, s, ps))
439                 continue;
440               if (!solv->allowvendorchange && s->vendor != ps->vendor && policy_illegal_vendorchange(solv, s, ps))
441                 continue;
442             }
443         }
444       else if (!solv->noupdateprovide && ps->obsoletes)   /* provides/obsoletes combination ? */
445         {
446           obsp = ps->repo->idarraydata + ps->obsoletes;
447           while ((obs = *obsp++) != 0)  /* for all obsoletes */
448             {
449               FOR_PROVIDES(p2, pp2, obs)   /* and all matching providers of the obsoletes */
450                 {
451                   if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
452                     continue;
453                   if (p2 == n)          /* match ! */
454                     break;
455                 }
456               if (p2)                   /* match! */
457                 break;
458             }
459           if (!obs)                     /* continue if no match */
460             continue;
461           /* here we have 'p' with a matching provides/obsoletes combination
462            * thus flagging p as a valid update candidate for s
463            */
464         }
465       else
466         continue;
467       queue_push(qs, p);
468     }
469   if (solv->noupdateprovide && solv->obsoletes && solv->obsoletes[n - solv->installed->start])
470     {
471       for (pp = solv->obsoletes_data + solv->obsoletes[n - solv->installed->start]; (p = *pp++) != 0;)
472         queue_push(qs, p);
473     }
474 }
475