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 "solver_private.h"
20 #include "evr.h"
21 #include "policy.h"
22 #include "poolvendor.h"
23 #include "poolarch.h"
24
25
26 /*-----------------------------------------------------------------*/
27
28 /*
29 * prep for prune_best_version
30 * sort by name
31 */
32
33 static int
prune_to_best_version_sortcmp(const void * ap,const void * bp,void * dp)34 prune_to_best_version_sortcmp(const void *ap, const void *bp, void *dp)
35 {
36 Pool *pool = dp;
37 int r;
38 Id a = *(Id *)ap;
39 Id b = *(Id *)bp;
40 Solvable *sa, *sb;
41
42 sa = pool->solvables + a;
43 sb = pool->solvables + b;
44 r = sa->name - sb->name;
45 if (r)
46 {
47 const char *na, *nb;
48 /* different names. We use real strcmp here so that the result
49 * is not depending on some random solvable order */
50 na = pool_id2str(pool, sa->name);
51 nb = pool_id2str(pool, sb->name);
52 return strcmp(na, nb);
53 }
54 /* the same name, bring installed solvables to the front */
55 if (pool->installed)
56 {
57 if (sa->repo == pool->installed)
58 {
59 if (sb->repo != pool->installed)
60 return -1;
61 }
62 else if (sb->repo == pool->installed)
63 return 1;
64 }
65 /* sort by repository sub-prio (installed repo handled above) */
66 r = (sb->repo ? sb->repo->subpriority : 0) - (sa->repo ? sa->repo->subpriority : 0);
67 if (r)
68 return r;
69 /* no idea about the order, sort by id */
70 return a - b;
71 }
72
73
74 /*
75 * prune to repository with highest priority.
76 * does not prune installed solvables.
77 */
78
79 static void
prune_to_highest_prio(Pool * pool,Queue * plist)80 prune_to_highest_prio(Pool *pool, Queue *plist)
81 {
82 int i, j;
83 Solvable *s;
84 int bestprio = 0, bestprioset = 0;
85
86 /* prune to highest priority */
87 for (i = 0; i < plist->count; i++) /* find highest prio in queue */
88 {
89 s = pool->solvables + plist->elements[i];
90 if (pool->installed && s->repo == pool->installed)
91 continue;
92 if (!bestprioset || s->repo->priority > bestprio)
93 {
94 bestprio = s->repo->priority;
95 bestprioset = 1;
96 }
97 }
98 if (!bestprioset)
99 return;
100 for (i = j = 0; i < plist->count; i++) /* remove all with lower prio */
101 {
102 s = pool->solvables + plist->elements[i];
103 if (s->repo->priority == bestprio || (pool->installed && s->repo == pool->installed))
104 plist->elements[j++] = plist->elements[i];
105 }
106 plist->count = j;
107 }
108
109 static void
prune_to_highest_prio_per_name(Pool * pool,Queue * plist)110 prune_to_highest_prio_per_name(Pool *pool, Queue *plist)
111 {
112 Queue pq;
113 int i, j, k;
114 Id name;
115
116 queue_init(&pq);
117 solv_sort(plist->elements, plist->count, sizeof(Id), prune_to_best_version_sortcmp, pool);
118 queue_push(&pq, plist->elements[0]);
119 name = pool->solvables[pq.elements[0]].name;
120 for (i = 1, j = 0; i < plist->count; i++)
121 {
122 if (pool->solvables[plist->elements[i]].name != name)
123 {
124 if (pq.count > 2)
125 prune_to_highest_prio(pool, &pq);
126 for (k = 0; k < pq.count; k++)
127 plist->elements[j++] = pq.elements[k];
128 queue_empty(&pq);
129 queue_push(&pq, plist->elements[i]);
130 name = pool->solvables[pq.elements[0]].name;
131 }
132 }
133 if (pq.count > 2)
134 prune_to_highest_prio(pool, &pq);
135 for (k = 0; k < pq.count; k++)
136 plist->elements[j++] = pq.elements[k];
137 queue_free(&pq);
138 plist->count = j;
139 }
140
141
142 /*
143 * prune to recommended/suggested packages.
144 * does not prune installed packages (they are also somewhat recommended).
145 */
146
147 static void
prune_to_recommended(Solver * solv,Queue * plist)148 prune_to_recommended(Solver *solv, Queue *plist)
149 {
150 Pool *pool = solv->pool;
151 int i, j, k, ninst;
152 Solvable *s;
153 Id p, pp, rec, *recp, sug, *sugp;
154
155 ninst = 0;
156 if (pool->installed)
157 {
158 for (i = 0; i < plist->count; i++)
159 {
160 p = plist->elements[i];
161 s = pool->solvables + p;
162 if (pool->installed && s->repo == pool->installed)
163 ninst++;
164 }
165 }
166 if (plist->count - ninst < 2)
167 return;
168
169 /* update our recommendsmap/suggestsmap */
170 if (solv->recommends_index < 0)
171 {
172 MAPZERO(&solv->recommendsmap);
173 MAPZERO(&solv->suggestsmap);
174 solv->recommends_index = 0;
175 }
176 while (solv->recommends_index < solv->decisionq.count)
177 {
178 p = solv->decisionq.elements[solv->recommends_index++];
179 if (p < 0)
180 continue;
181 s = pool->solvables + p;
182 if (s->recommends)
183 {
184 recp = s->repo->idarraydata + s->recommends;
185 while ((rec = *recp++) != 0)
186 FOR_PROVIDES(p, pp, rec)
187 MAPSET(&solv->recommendsmap, p);
188 }
189 if (s->suggests)
190 {
191 sugp = s->repo->idarraydata + s->suggests;
192 while ((sug = *sugp++) != 0)
193 FOR_PROVIDES(p, pp, sug)
194 MAPSET(&solv->suggestsmap, p);
195 }
196 }
197
198 /* prune to recommended/supplemented */
199 ninst = 0;
200 for (i = j = 0; i < plist->count; i++)
201 {
202 p = plist->elements[i];
203 s = pool->solvables + p;
204 if (pool->installed && s->repo == pool->installed)
205 {
206 ninst++;
207 if (j)
208 plist->elements[j++] = p;
209 continue;
210 }
211 if (!MAPTST(&solv->recommendsmap, p))
212 if (!solver_is_supplementing(solv, s))
213 continue;
214 if (!j && ninst)
215 {
216 for (k = 0; j < ninst; k++)
217 {
218 s = pool->solvables + plist->elements[k];
219 if (pool->installed && s->repo == pool->installed)
220 plist->elements[j++] = plist->elements[k];
221 }
222 }
223 plist->elements[j++] = p;
224 }
225 if (j)
226 plist->count = j;
227
228 /* anything left to prune? */
229 if (plist->count - ninst < 2)
230 return;
231
232 /* prune to suggested/enhanced */
233 ninst = 0;
234 for (i = j = 0; i < plist->count; i++)
235 {
236 p = plist->elements[i];
237 s = pool->solvables + p;
238 if (pool->installed && s->repo == pool->installed)
239 {
240 ninst++;
241 if (j)
242 plist->elements[j++] = p;
243 continue;
244 }
245 if (!MAPTST(&solv->suggestsmap, p))
246 if (!solver_is_enhancing(solv, s))
247 continue;
248 if (!j && ninst)
249 {
250 for (k = 0; j < ninst; k++)
251 {
252 s = pool->solvables + plist->elements[k];
253 if (pool->installed && s->repo == pool->installed)
254 plist->elements[j++] = plist->elements[k];
255 }
256 }
257 plist->elements[j++] = p;
258 }
259 if (j)
260 plist->count = j;
261 }
262
263 static void
prune_to_best_arch(const Pool * pool,Queue * plist)264 prune_to_best_arch(const Pool *pool, Queue *plist)
265 {
266 Id a, bestscore;
267 Solvable *s;
268 int i, j;
269
270 if (!pool->id2arch || plist->count < 2)
271 return;
272 bestscore = 0;
273 for (i = 0; i < plist->count; i++)
274 {
275 s = pool->solvables + plist->elements[i];
276 a = s->arch;
277 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
278 if (a && a != 1 && (!bestscore || a < bestscore))
279 bestscore = a;
280 }
281 if (!bestscore)
282 return;
283 for (i = j = 0; i < plist->count; i++)
284 {
285 s = pool->solvables + plist->elements[i];
286 a = s->arch;
287 if (a > pool->lastarch)
288 continue;
289 a = pool->id2arch[a];
290 /* a == 1 -> noarch */
291 if (a != 1 && ((a ^ bestscore) & 0xffff0000) != 0)
292 continue;
293 plist->elements[j++] = plist->elements[i];
294 }
295 if (j)
296 plist->count = j;
297 }
298
299
300 struct trj_data {
301 Pool *pool;
302 Queue *plist;
303 Id *stack;
304 Id nstack;
305 Id *low;
306 Id firstidx;
307 Id idx;
308 };
309
310 /* This is Tarjan's SCC algorithm, slightly modified */
311 static void
trj_visit(struct trj_data * trj,Id node)312 trj_visit(struct trj_data *trj, Id node)
313 {
314 Id *low = trj->low;
315 Pool *pool = trj->pool;
316 Queue *plist = trj->plist;
317 Id myidx, stackstart;
318 Solvable *s;
319 int i;
320 Id p, pp, obs, *obsp;
321
322 low[node] = myidx = trj->idx++;
323 trj->stack[(stackstart = trj->nstack++)] = node;
324
325 s = pool->solvables + plist->elements[node];
326 if (s->obsoletes)
327 {
328 obsp = s->repo->idarraydata + s->obsoletes;
329 while ((obs = *obsp++) != 0)
330 {
331 FOR_PROVIDES(p, pp, obs)
332 {
333 Solvable *ps = pool->solvables + p;
334 if (ps->name == s->name)
335 continue;
336 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
337 continue;
338 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
339 continue;
340 /* hmm, expensive. should use hash if plist is big */
341 for (i = 0; i < plist->count; i++)
342 {
343 if (node != i && plist->elements[i] == p)
344 {
345 Id l = low[i];
346 if (!l)
347 {
348 if (!ps->obsoletes)
349 {
350 /* don't bother */
351 trj->idx++;
352 low[i] = -1;
353 continue;
354 }
355 trj_visit(trj, i);
356 l = low[i];
357 }
358 if (l < 0)
359 continue;
360 if (l < trj->firstidx)
361 {
362 int k;
363 /* this means we have reached an old SCC found earlier.
364 * delete it as we obsolete it */
365 for (k = l; ; k++)
366 {
367 if (low[trj->stack[k]] == l)
368 low[trj->stack[k]] = -1;
369 else
370 break;
371 }
372 }
373 else if (l < low[node])
374 low[node] = l;
375 }
376 }
377 }
378 }
379 }
380 if (low[node] == myidx) /* found a SCC? */
381 {
382 /* we're only interested in SCCs that contain the first node,
383 * as all others are "obsoleted" */
384 if (myidx != trj->firstidx)
385 myidx = -1;
386 for (i = stackstart; i < trj->nstack; i++)
387 low[trj->stack[i]] = myidx;
388 trj->nstack = stackstart; /* empty stack */
389 }
390 }
391
392 /*
393 * remove entries from plist that are obsoleted by other entries
394 * with different name.
395 */
396 static void
prune_obsoleted(Pool * pool,Queue * plist)397 prune_obsoleted(Pool *pool, Queue *plist)
398 {
399 Id data_buf[2 * 16], *data;
400 struct trj_data trj;
401 int i, j;
402 Solvable *s;
403
404 if (plist->count <= 16)
405 {
406 memset(data_buf, 0, sizeof(data_buf));
407 data = data_buf;
408 }
409 else
410 data = solv_calloc(plist->count, 2 * sizeof(Id));
411 trj.pool = pool;
412 trj.plist = plist;
413 trj.low = data;
414 trj.idx = 1;
415 trj.stack = data + plist->count - 1; /* -1 so we can index with idx (which starts with 1) */
416 for (i = 0; i < plist->count; i++)
417 {
418 if (trj.low[i])
419 continue;
420 s = pool->solvables + plist->elements[i];
421 if (s->obsoletes)
422 {
423 trj.firstidx = trj.nstack = trj.idx;
424 trj_visit(&trj, i);
425 }
426 else
427 {
428 Id myidx = trj.idx++;
429 trj.low[i] = myidx;
430 trj.stack[myidx] = i;
431 }
432 }
433 for (i = j = 0; i < plist->count; i++)
434 if (trj.low[i] >= 0)
435 plist->elements[j++] = plist->elements[i];
436 plist->count = j;
437 if (data != data_buf)
438 solv_free(data);
439 }
440
441 /* this is prune_obsoleted special-cased for two elements */
442 static void
prune_obsoleted_2(Pool * pool,Queue * plist)443 prune_obsoleted_2(Pool *pool, Queue *plist)
444 {
445 int i;
446 Solvable *s;
447 Id p, pp, obs, *obsp;
448 Id other;
449 int obmap = 0;
450
451 for (i = 0; i < 2; i++)
452 {
453 s = pool->solvables + plist->elements[i];
454 other = plist->elements[1 - i];
455 if (s->obsoletes)
456 {
457 obsp = s->repo->idarraydata + s->obsoletes;
458 while ((obs = *obsp++) != 0)
459 {
460 FOR_PROVIDES(p, pp, obs)
461 {
462 Solvable *ps;
463 if (p != other)
464 continue;
465 ps = pool->solvables + p;
466 if (ps->name == s->name)
467 continue;
468 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
469 continue;
470 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
471 continue;
472 obmap |= 1 << i;
473 break;
474 }
475 if (p)
476 break;
477 }
478 }
479 }
480 if (obmap == 0 || obmap == 3)
481 return;
482 if (obmap == 2)
483 plist->elements[0] = plist->elements[1];
484 plist->count = 1;
485 }
486
487 /*
488 * bring those elements to the front of the queue that
489 * have a installed solvable with the same name
490 */
491 static void
move_installed_to_front(Pool * pool,Queue * plist)492 move_installed_to_front(Pool *pool, Queue *plist)
493 {
494 int i, j;
495 Solvable *s;
496 Id p, pp;
497
498 for (i = j = 0; i < plist->count; i++)
499 {
500 s = pool->solvables + plist->elements[i];
501 if (s->repo != pool->installed)
502 {
503 FOR_PROVIDES(p, pp, s->name)
504 {
505 Solvable *ps = pool->solvables + p;
506 if (s->name == ps->name && ps->repo == pool->installed)
507 {
508 s = ps;
509 break;
510 }
511 }
512 }
513 if (s->repo == pool->installed)
514 {
515 if (i != j)
516 {
517 p = plist->elements[i];
518 if (i - j == 1)
519 plist->elements[i] = plist->elements[j];
520 else
521 memmove(plist->elements + j + 1, plist->elements + j, (i - j) * sizeof(Id));
522 plist->elements[j] = p;
523 }
524 else if (j + 2 == plist->count)
525 break; /* no need to check last element if all prev ones are installed */
526 j++;
527 }
528 }
529 }
530
531 /*
532 * prune_to_best_version
533 *
534 * sort list of packages (given through plist) by name and evr
535 * return result through plist
536 */
537 static void
prune_to_best_version(Pool * pool,Queue * plist)538 prune_to_best_version(Pool *pool, Queue *plist)
539 {
540 int i, j;
541 Solvable *s, *best;
542
543 if (plist->count < 2) /* no need to prune for a single entry */
544 return;
545 POOL_DEBUG(SOLV_DEBUG_POLICY, "prune_to_best_version %d\n", plist->count);
546
547 /* sort by name first, prefer installed */
548 solv_sort(plist->elements, plist->count, sizeof(Id), prune_to_best_version_sortcmp, pool);
549
550 /* now find best 'per name' */
551 best = 0;
552 for (i = j = 0; i < plist->count; i++)
553 {
554 s = pool->solvables + plist->elements[i];
555
556 POOL_DEBUG(SOLV_DEBUG_POLICY, "- %s[%s]\n",
557 pool_solvable2str(pool, s),
558 (pool->installed && s->repo == pool->installed) ? "installed" : "not installed");
559
560 if (!best) /* if no best yet, the current is best */
561 {
562 best = s;
563 continue;
564 }
565
566 /* name switch: finish group, re-init */
567 if (best->name != s->name) /* new name */
568 {
569 plist->elements[j++] = best - pool->solvables; /* move old best to front */
570 best = s; /* take current as new best */
571 continue;
572 }
573
574 if (best->evr != s->evr) /* compare evr */
575 {
576 if (pool_evrcmp(pool, best->evr, s->evr, EVRCMP_COMPARE) < 0)
577 best = s;
578 }
579 }
580 plist->elements[j++] = best - pool->solvables; /* finish last group */
581 plist->count = j;
582
583 /* we reduced the list to one package per name, now look at
584 * package obsoletes */
585 if (plist->count > 1)
586 {
587 if (plist->count == 2)
588 prune_obsoleted_2(pool, plist);
589 else
590 prune_obsoleted(pool, plist);
591 }
592 if (plist->count > 1 && pool->installed)
593 move_installed_to_front(pool, plist);
594 }
595
596
597 /* legacy, do not use anymore!
598 * (rates arch higher than version, but thats a policy)
599 */
600
601 static void
prune_best_arch_name_version(const Solver * solv,Pool * pool,Queue * plist)602 prune_best_arch_name_version(const Solver *solv, Pool *pool, Queue *plist)
603 {
604 if (plist->count > 1)
605 prune_to_best_arch(pool, plist);
606 if (plist->count > 1)
607 prune_to_best_version(pool, plist);
608 }
609
610 /* installed packages involed in a dup operation can only be kept
611 * if they are identical to a non-installed one */
612 static void
prune_installed_dup_packages(Solver * solv,Queue * plist)613 prune_installed_dup_packages(Solver *solv, Queue *plist)
614 {
615 Pool *pool = solv->pool;
616 int i, j, k;
617
618 for (i = j = 0; i < plist->count; i++)
619 {
620 Id p = plist->elements[i];
621 Solvable *s = pool->solvables + p;
622 if (s->repo == pool->installed && (solv->dupmap_all || (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))))
623 {
624 for (k = 0; k < plist->count; k++)
625 {
626 Solvable *s2 = pool->solvables + plist->elements[k];
627 if (s2->repo != pool->installed && solvable_identical(s, s2))
628 break;
629 }
630 if (k == plist->count)
631 continue; /* no identical package found, ignore installed package */
632 }
633 plist->elements[j++] = p;
634 }
635 if (j)
636 plist->count = j;
637 }
638
639 /*
640 * POLICY_MODE_CHOOSE: default, do all pruning steps
641 * POLICY_MODE_RECOMMEND: leave out prune_to_recommended
642 * POLICY_MODE_SUGGEST: leave out prune_to_recommended, do prio pruning just per name
643 */
644 void
policy_filter_unwanted(Solver * solv,Queue * plist,int mode)645 policy_filter_unwanted(Solver *solv, Queue *plist, int mode)
646 {
647 Pool *pool = solv->pool;
648 if (plist->count > 1)
649 {
650 if (mode != POLICY_MODE_SUGGEST)
651 prune_to_highest_prio(pool, plist);
652 else
653 prune_to_highest_prio_per_name(pool, plist);
654 /* installed dup packages need special treatment as prio pruning
655 * does not prune installed packages */
656 if (plist->count > 1 && pool->installed && (solv->dupmap_all || solv->dupinvolvedmap.size))
657 prune_installed_dup_packages(solv, plist);
658 }
659 if (plist->count > 1 && mode == POLICY_MODE_CHOOSE)
660 prune_to_recommended(solv, plist);
661 prune_best_arch_name_version(solv, pool, plist);
662 }
663
664
665 /* check if there is an illegal architecture change if
666 * installed solvable s1 is replaced by s2 */
667 int
policy_illegal_archchange(Solver * solv,Solvable * s1,Solvable * s2)668 policy_illegal_archchange(Solver *solv, Solvable *s1, Solvable *s2)
669 {
670 Pool *pool = solv->pool;
671 Id a1 = s1->arch, a2 = s2->arch;
672
673 /* we allow changes to/from noarch */
674 if (a1 == a2 || a1 == pool->noarchid || a2 == pool->noarchid)
675 return 0;
676 if (!pool->id2arch)
677 return 0;
678 a1 = a1 <= pool->lastarch ? pool->id2arch[a1] : 0;
679 a2 = a2 <= pool->lastarch ? pool->id2arch[a2] : 0;
680 if (((a1 ^ a2) & 0xffff0000) != 0)
681 return 1;
682 return 0;
683 }
684
685 /* check if there is an illegal vendor change if
686 * installed solvable s1 is replaced by s2 */
687 int
policy_illegal_vendorchange(Solver * solv,Solvable * s1,Solvable * s2)688 policy_illegal_vendorchange(Solver *solv, Solvable *s1, Solvable *s2)
689 {
690 Pool *pool = solv->pool;
691 Id v1, v2;
692 Id vendormask1, vendormask2;
693
694 if (pool->custom_vendorcheck)
695 return pool->custom_vendorcheck(pool, s1, s2);
696
697 /* treat a missing vendor as empty string */
698 v1 = s1->vendor ? s1->vendor : ID_EMPTY;
699 v2 = s2->vendor ? s2->vendor : ID_EMPTY;
700 if (v1 == v2)
701 return 0;
702 vendormask1 = pool_vendor2mask(pool, v1);
703 if (!vendormask1)
704 return 1; /* can't match */
705 vendormask2 = pool_vendor2mask(pool, v2);
706 if ((vendormask1 & vendormask2) != 0)
707 return 0;
708 return 1; /* no class matches */
709 }
710
711 /* check if it is illegal to replace installed
712 * package "is" with package "s" (which must obsolete "is")
713 */
714 int
policy_is_illegal(Solver * solv,Solvable * is,Solvable * s,int ignore)715 policy_is_illegal(Solver *solv, Solvable *is, Solvable *s, int ignore)
716 {
717 Pool *pool = solv->pool;
718 int ret = 0;
719 int duppkg = solv->dupmap_all ? 1 : 0;
720 if (!(ignore & POLICY_ILLEGAL_DOWNGRADE) && !(duppkg ? solv->dup_allowdowngrade : solv->allowdowngrade))
721 {
722 if (is->name == s->name && pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE) > 0)
723 ret |= POLICY_ILLEGAL_DOWNGRADE;
724 }
725 if (!(ignore & POLICY_ILLEGAL_ARCHCHANGE) && !(duppkg ? solv->dup_allowarchchange : solv->allowarchchange))
726 {
727 if (is->arch != s->arch && policy_illegal_archchange(solv, is, s))
728 ret |= POLICY_ILLEGAL_ARCHCHANGE;
729 }
730 if (!(ignore & POLICY_ILLEGAL_VENDORCHANGE) && !(duppkg ? solv->dup_allowvendorchange : solv->allowvendorchange))
731 {
732 if (is->vendor != s->vendor && policy_illegal_vendorchange(solv, is, s))
733 ret |= POLICY_ILLEGAL_VENDORCHANGE;
734 }
735 if (!(ignore & POLICY_ILLEGAL_NAMECHANGE) && !(duppkg ? solv->dup_allownamechange : solv->allownamechange))
736 {
737 if (is->name != s->name)
738 ret |= POLICY_ILLEGAL_NAMECHANGE;
739 }
740 return ret;
741 }
742
743 /*-------------------------------------------------------------------
744 *
745 * create reverse obsoletes map for installed solvables
746 *
747 * For each installed solvable find which packages with *different* names
748 * obsolete the solvable.
749 * This index is used in policy_findupdatepackages() below.
750 */
751 void
policy_create_obsolete_index(Solver * solv)752 policy_create_obsolete_index(Solver *solv)
753 {
754 Pool *pool = solv->pool;
755 Solvable *s;
756 Repo *installed = solv->installed;
757 Id p, pp, obs, *obsp, *obsoletes, *obsoletes_data;
758 int i, n, cnt;
759
760 solv->obsoletes = solv_free(solv->obsoletes);
761 solv->obsoletes_data = solv_free(solv->obsoletes_data);
762 if (!installed || installed->start == installed->end)
763 return;
764 cnt = installed->end - installed->start;
765 solv->obsoletes = obsoletes = solv_calloc(cnt, sizeof(Id));
766 for (i = 1; i < pool->nsolvables; i++)
767 {
768 s = pool->solvables + i;
769 if (!s->obsoletes)
770 continue;
771 if (!pool_installable(pool, s))
772 continue;
773 obsp = s->repo->idarraydata + s->obsoletes;
774 while ((obs = *obsp++) != 0)
775 {
776 FOR_PROVIDES(p, pp, obs)
777 {
778 Solvable *ps = pool->solvables + p;;
779 if (ps->repo != installed)
780 continue;
781 if (ps->name == s->name)
782 continue;
783 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
784 continue;
785 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
786 continue;
787 obsoletes[p - installed->start]++;
788 }
789 }
790 }
791 n = 0;
792 for (i = 0; i < cnt; i++)
793 if (obsoletes[i])
794 {
795 n += obsoletes[i] + 1;
796 obsoletes[i] = n;
797 }
798 solv->obsoletes_data = obsoletes_data = solv_calloc(n + 1, sizeof(Id));
799 POOL_DEBUG(SOLV_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
800 for (i = pool->nsolvables - 1; i > 0; i--)
801 {
802 s = pool->solvables + i;
803 if (!s->obsoletes)
804 continue;
805 if (!pool_installable(pool, s))
806 continue;
807 obsp = s->repo->idarraydata + s->obsoletes;
808 while ((obs = *obsp++) != 0)
809 {
810 FOR_PROVIDES(p, pp, obs)
811 {
812 Solvable *ps = pool->solvables + p;;
813 if (ps->repo != installed)
814 continue;
815 if (ps->name == s->name)
816 continue;
817 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
818 continue;
819 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
820 continue;
821 if (obsoletes_data[obsoletes[p - installed->start]] != i)
822 obsoletes_data[--obsoletes[p - installed->start]] = i;
823 }
824 }
825 }
826 }
827
828
829 /*
830 * find update candidates
831 *
832 * s: installed solvable to be updated
833 * qs: [out] queue to hold Ids of candidates
834 * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
835 * 2 = dup mode
836 *
837 */
838 void
policy_findupdatepackages(Solver * solv,Solvable * s,Queue * qs,int allow_all)839 policy_findupdatepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
840 {
841 /* installed packages get a special upgrade allowed rule */
842 Pool *pool = solv->pool;
843 Id p, pp, n, p2, pp2;
844 Id obs, *obsp;
845 Solvable *ps;
846 int haveprovobs = 0;
847 int allowdowngrade = allow_all ? 1 : solv->allowdowngrade;
848 int allownamechange = allow_all ? 1 : solv->allownamechange;
849 int allowarchchange = allow_all ? 1 : solv->allowarchchange;
850 int allowvendorchange = allow_all ? 1 : solv->allowvendorchange;
851 if (allow_all == 2)
852 {
853 allowdowngrade = solv->dup_allowdowngrade;
854 allownamechange = solv->dup_allownamechange;
855 allowarchchange = solv->dup_allowarchchange;
856 allowvendorchange = solv->dup_allowvendorchange;
857 }
858
859 queue_empty(qs);
860
861 n = s - pool->solvables;
862
863 /*
864 * look for updates for s
865 */
866 FOR_PROVIDES(p, pp, s->name) /* every provider of s' name */
867 {
868 if (p == n) /* skip itself */
869 continue;
870
871 ps = pool->solvables + p;
872 if (s->name == ps->name) /* name match */
873 {
874 if (!allowdowngrade && pool_evrcmp(pool, s->evr, ps->evr, EVRCMP_COMPARE) > 0)
875 continue;
876 }
877 else if (!allownamechange)
878 continue;
879 else if (!solv->noupdateprovide && ps->obsoletes) /* provides/obsoletes combination ? */
880 {
881 obsp = ps->repo->idarraydata + ps->obsoletes;
882 while ((obs = *obsp++) != 0) /* for all obsoletes */
883 {
884 FOR_PROVIDES(p2, pp2, obs) /* and all matching providers of the obsoletes */
885 {
886 Solvable *ps2 = pool->solvables + p2;
887 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps2, obs))
888 continue;
889 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps2))
890 continue;
891 if (p2 == n) /* match ! */
892 break;
893 }
894 if (p2) /* match! */
895 break;
896 }
897 if (!obs) /* continue if no match */
898 continue;
899 /* here we have 'p' with a matching provides/obsoletes combination
900 * thus flagging p as a valid update candidate for s
901 */
902 haveprovobs = 1;
903 }
904 else
905 continue;
906 if (!allowarchchange && s->arch != ps->arch && policy_illegal_archchange(solv, s, ps))
907 continue;
908 if (!allowvendorchange && s->vendor != ps->vendor && policy_illegal_vendorchange(solv, s, ps))
909 continue;
910 queue_push(qs, p);
911 }
912 if (!allownamechange)
913 return;
914 /* if we have found some valid candidates and noupdateprovide is not set, we're
915 done. otherwise we fallback to all obsoletes */
916 if (!solv->noupdateprovide && haveprovobs)
917 return;
918 if (solv->obsoletes && solv->obsoletes[n - solv->installed->start])
919 {
920 Id *opp;
921 for (opp = solv->obsoletes_data + solv->obsoletes[n - solv->installed->start]; (p = *opp++) != 0;)
922 {
923 ps = pool->solvables + p;
924 if (!allowarchchange && s->arch != ps->arch && policy_illegal_archchange(solv, s, ps))
925 continue;
926 if (!allowvendorchange && s->vendor != ps->vendor && policy_illegal_vendorchange(solv, s, ps))
927 continue;
928 queue_push(qs, p);
929 }
930 }
931 }
932
933