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 "solver_private.h"
  20 #include "evr.h"
  21 #include "policy.h"
  22 #include "poolvendor.h"
  23 #include "poolarch.h"
  24 #include "linkedpkg.h"
  25 #include "cplxdeps.h"
  26
  27
  28
  29 /*-----------------------------------------------------------------*/
  30
  31 /*
  32  * prep for prune_best_version
  33  *   sort by name
  34  */
  35
  36 static int
  37 prune_to_best_version_sortcmp(const void *ap, const void *bp, void *dp)
  38 {
  39   Pool *pool = dp;
  40   int r;
  41   Id a = *(Id *)ap;
  42   Id b = *(Id *)bp;
  43   Solvable *sa, *sb;
  44
  45   sa = pool->solvables + a;
  46   sb = pool->solvables + b;
  47   r = sa->name - sb->name;
  48   if (r)
  49     {
  50       const char *na, *nb;
  51       /* different names. We use real strcmp here so that the result
  52        * is not depending on some random solvable order */
  53       na = pool_id2str(pool, sa->name);
  54       nb = pool_id2str(pool, sb->name);
  55       return strcmp(na, nb);
  56     }
  57   if (sa->arch != sb->arch)
  58     {
  59       int aa, ab;
  60       aa = (sa->arch <= pool->lastarch) ? pool->id2arch[sa->arch] : 0;
  61       ab = (sb->arch <= pool->lastarch) ? pool->id2arch[sb->arch] : 0;
  62       if (aa != ab && aa > 1 && ab > 1)
  63         return aa - ab;         /* lowest score first */
  64     }
  65
  66   /* the same name, bring installed solvables to the front */
  67   if (pool->installed)
  68     {
  69       if (sa->repo == pool->installed)
  70         {
  71           if (sb->repo != pool->installed)
  72             return -1;
  73         }
  74       else if (sb->repo == pool->installed)
  75         return 1;
  76     }
  77   /* sort by repository sub-prio (installed repo handled above) */
  78   r = (sb->repo ? sb->repo->subpriority : 0) - (sa->repo ? sa->repo->subpriority : 0);
  79   if (r)
  80     return r;
  81   /* no idea about the order, sort by id */
  82   return a - b;
  83 }
  84
  85
  86 /*
  87  * prune to repository with highest priority.
  88  * does not prune installed solvables.
  89  */
  90
  91 static void
  92 prune_to_highest_prio(Pool *pool, Queue *plist)
  93 {
  94   int i, j;
  95   Solvable *s;
  96   int bestprio = 0, bestprioset = 0;
  97
  98   /* prune to highest priority */
  99   for (i = 0; i < plist->count; i++)  /* find highest prio in queue */
 100     {
 101       s = pool->solvables + plist->elements[i];
 102       if (pool->installed && s->repo == pool->installed)
 103         continue;
 104       if (!bestprioset || s->repo->priority > bestprio)
 105         {
 106           bestprio = s->repo->priority;
 107           bestprioset = 1;
 108         }
 109     }
 110   if (!bestprioset)
 111     return;
 112   for (i = j = 0; i < plist->count; i++) /* remove all with lower prio */
 113     {
 114       s = pool->solvables + plist->elements[i];
 115       if (s->repo->priority == bestprio || (pool->installed && s->repo == pool->installed))
 116         plist->elements[j++] = plist->elements[i];
 117     }
 118   plist->count = j;
 119 }
 120
 121
 122 /* installed packages involed in a dup operation can only be kept
 123  * if they are identical to a non-installed one */
 124 static void
 125 solver_prune_installed_dup_packages(Solver *solv, Queue *plist)
 126 {
 127   Pool *pool = solv->pool;
 128   int i, j, bestprio = 0;
 129
 130   /* find bestprio (again) */
 131   for (i = 0; i < plist->count; i++)
 132     {
 133       Solvable *s = pool->solvables + plist->elements[i];
 134       if (s->repo != pool->installed)
 135         {
 136           bestprio = s->repo->priority;
 137           break;
 138         }
 139     }
 140   if (i == plist->count)
 141     return;     /* only installed packages, could not find prio */
 142   for (i = j = 0; i < plist->count; i++)
 143     {
 144       Id p = plist->elements[i];
 145       Solvable *s = pool->solvables + p;
 146       if (s->repo != pool->installed && s->repo->priority < bestprio)
 147         continue;
 148       if (s->repo == pool->installed && (solv->dupmap_all || (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))))
 149         {
 150           Id p2, pp2;
 151           int keepit = 0;
 152           FOR_PROVIDES(p2, pp2, s->name)
 153             {
 154               Solvable *s2 = pool->solvables + p2;
 155               if (s2->repo == pool->installed || s2->evr != s->evr || s2->repo->priority < bestprio)
 156                 continue;
 157               if (!solvable_identical(s, s2))
 158                 continue;
 159               keepit = 1;
 160               if (s2->repo->priority > bestprio)
 161                 {
 162                   /* new max prio! */
 163                   bestprio = s2->repo->priority;
 164                   j = 0;
 165                 }
 166             }
 167           if (!keepit)
 168             continue;   /* no identical package found, ignore installed package */
 169         }
 170       plist->elements[j++] = p;
 171     }
 172   if (j)
 173     plist->count = j;
 174 }
 175
 176 /*
 177  * like prune_to_highest_prio, but calls solver prune_installed_dup_packages
 178  * when there are dup packages
 179  */
 180 static inline void
 181 solver_prune_to_highest_prio(Solver *solv, Queue *plist)
 182 {
 183   prune_to_highest_prio(solv->pool, plist);
 184   if (plist->count > 1 && solv->pool->installed && (solv->dupmap_all || solv->dupinvolvedmap.size))
 185     solver_prune_installed_dup_packages(solv, plist);
 186 }
 187
 188
 189 static void
 190 solver_prune_to_highest_prio_per_name(Solver *solv, Queue *plist)
 191 {
 192   Pool *pool = solv->pool;
 193   Queue pq;
 194   int i, j, k;
 195   Id name;
 196
 197   queue_init(&pq);
 198   solv_sort(plist->elements, plist->count, sizeof(Id), prune_to_best_version_sortcmp, pool);
 199   queue_push(&pq, plist->elements[0]);
 200   name = pool->solvables[pq.elements[0]].name;
 201   for (i = 1, j = 0; i < plist->count; i++)
 202     {
 203       if (pool->solvables[plist->elements[i]].name != name)
 204         {
 205           if (pq.count > 2)
 206             solver_prune_to_highest_prio(solv, &pq);
 207           for (k = 0; k < pq.count; k++)
 208             plist->elements[j++] = pq.elements[k];
 209           queue_empty(&pq);
 210           queue_push(&pq, plist->elements[i]);
 211           name = pool->solvables[pq.elements[0]].name;
 212         }
 213     }
 214   if (pq.count > 2)
 215     solver_prune_to_highest_prio(solv, &pq);
 216   for (k = 0; k < pq.count; k++)
 217     plist->elements[j++] = pq.elements[k];
 218   queue_free(&pq);
 219   plist->count = j;
 220 }
 221
 222
 223 #ifdef ENABLE_COMPLEX_DEPS
 224
 225 /* simple fixed-size hash for package ids */
 226 #define CPLXDEPHASH_EMPTY(elements) (memset(elements, 0, sizeof(Id) * 256))
 227 #define CPLXDEPHASH_SET(elements, p) (elements[(p) & 255] |= (1 << ((p) >> 8 & 31)))
 228 #define CPLXDEPHASH_TST(elements, p) (elements[(p) & 255] && (elements[(p) & 255] & (1 << ((p) >> 8 & 31))))
 229
 230 static void
 231 check_complex_dep(Solver *solv, Id dep, Map *m, Queue **cqp)
 232 {
 233   Pool *pool = solv->pool;
 234   Queue q;
 235   queue_init(&q);
 236   Id p;
 237   int i, qcnt;
 238
 239 #if 0
 240   printf("check_complex_dep %s\n", pool_dep2str(pool, dep));
 241 #endif
 242   i = pool_normalize_complex_dep(pool, dep, &q, CPLXDEPS_EXPAND);
 243   if (i == 0 || i == 1)
 244     {
 245       queue_free(&q);
 246       return;
 247     }
 248   qcnt = q.count;
 249   for (i = 0; i < qcnt; i++)
 250     {
 251       /* we rely on the fact that blocks are ordered here.
 252        * if we reach a positive element, we know that we
 253        * saw all negative ones */
 254       for (; (p = q.elements[i]) < 0; i++)
 255         {
 256           if (solv->decisionmap[-p] < 0)
 257             break;
 258           if (solv->decisionmap[-p] == 0)
 259             queue_push(&q, -p);         /* undecided negative literal */
 260         }
 261       if (p <= 0)
 262         {
 263 #if 0
 264           printf("complex dep block cannot be true or no pos literals\n");
 265 #endif
 266           while (q.elements[i])
 267             i++;
 268           if (qcnt != q.count)
 269             queue_truncate(&q, qcnt);
 270           continue;
 271         }
 272       if (qcnt == q.count)
 273         {
 274           /* all negative literals installed, add positive literals to map */
 275           for (; (p = q.elements[i]) != 0; i++)
 276             MAPSET(m, p);
 277         }
 278       else
 279         {
 280           /* at least one undecided negative literal, postpone */
 281           int j, k;
 282           Queue *cq;
 283 #if 0
 284           printf("add new complex dep block\n");
 285           for (j = qcnt; j < q.count; j++)
 286             printf("  - %s\n", pool_solvid2str(pool, q.elements[j]));
 287 #endif
 288           while (q.elements[i])
 289             i++;
 290           if (!(cq = *cqp))
 291             {
 292               cq = solv_calloc(1, sizeof(Queue));
 293               queue_init(cq);
 294               queue_insertn(cq, 0, 256, 0);     /* allocate hash area */
 295               *cqp = cq;
 296             }
 297           for (j = qcnt; j < q.count; j++)
 298             {
 299               p = q.elements[j];
 300               /* check if we already have this (dep, p) entry */
 301               for (k = 256; k < cq->count; k += 2)
 302                 if (cq->elements[k + 1] == dep && cq->elements[k] == p)
 303                   break;
 304               if (k == cq->count)
 305                 {
 306                   /* a new one. add to cq and hash */
 307                   queue_push2(cq, p, dep);
 308                   CPLXDEPHASH_SET(cq->elements, p);
 309                 }
 310             }
 311           queue_truncate(&q, qcnt);
 312         }
 313     }
 314   queue_free(&q);
 315 }
 316
 317 static void
 318 recheck_complex_deps(Solver *solv, Id p, Map *m, Queue **cqp)
 319 {
 320   Queue *cq = *cqp;
 321   Id pp;
 322   int i;
 323 #if 0
 324   printf("recheck_complex_deps for package %s\n", pool_solvid2str(solv->pool, p));
 325 #endif
 326   /* make sure that we don't have a false hit */
 327   for (i = 256; i < cq->count; i += 2)
 328     if (cq->elements[i] == p)
 329       break;
 330   if (i == cq->count)
 331     return;     /* false alert */
 332   if (solv->decisionmap[p] <= 0)
 333     return;     /* just in case... */
 334
 335   /* rebuild the hash, call check_complex_dep for our package */
 336   CPLXDEPHASH_EMPTY(cq->elements);
 337   for (i = 256; i < cq->count; i += 2)
 338     if ((pp = cq->elements[i]) == p)
 339       {
 340         Id dep = cq->elements[i + 1];
 341         queue_deleten(cq, i, 2);
 342         i -= 2;
 343         check_complex_dep(solv, dep, m, &cq);
 344       }
 345     else
 346       CPLXDEPHASH_SET(cq->elements, pp);
 347 }
 348
 349 #endif
 350
 351
 352 void
 353 policy_update_recommendsmap(Solver *solv)
 354 {
 355   Pool *pool = solv->pool;
 356   Solvable *s;
 357   Id p, pp, rec, *recp, sug, *sugp;
 358
 359   if (solv->recommends_index < 0)
 360     {
 361       MAPZERO(&solv->recommendsmap);
 362       MAPZERO(&solv->suggestsmap);
 363 #ifdef ENABLE_COMPLEX_DEPS
 364       if (solv->recommendscplxq)
 365         {
 366           queue_free(solv->recommendscplxq);
 367           solv->recommendscplxq = solv_free(solv->recommendscplxq);
 368         }
 369       if (solv->suggestscplxq)
 370         {
 371           queue_free(solv->suggestscplxq);
 372           solv->suggestscplxq = solv_free(solv->suggestscplxq);
 373         }
 374 #endif
 375       solv->recommends_index = 0;
 376     }
 377   while (solv->recommends_index < solv->decisionq.count)
 378     {
 379       p = solv->decisionq.elements[solv->recommends_index++];
 380       if (p < 0)
 381         continue;
 382       s = pool->solvables + p;
 383 #ifdef ENABLE_COMPLEX_DEPS
 384       /* re-check postponed complex blocks */
 385       if (solv->recommendscplxq && CPLXDEPHASH_TST(solv->recommendscplxq->elements, p))
 386         recheck_complex_deps(solv, p, &solv->recommendsmap, &solv->recommendscplxq);
 387       if (solv->suggestscplxq && CPLXDEPHASH_TST(solv->suggestscplxq->elements, p))
 388         recheck_complex_deps(solv, p, &solv->suggestsmap, &solv->suggestscplxq);
 389 #endif
 390       if (s->recommends)
 391         {
 392           recp = s->repo->idarraydata + s->recommends;
 393           while ((rec = *recp++) != 0)
 394             {
 395 #ifdef ENABLE_COMPLEX_DEPS
 396               if (pool_is_complex_dep(pool, rec))
 397                 {
 398                   check_complex_dep(solv, rec, &solv->recommendsmap, &solv->recommendscplxq);
 399                   continue;
 400                 }
 401 #endif
 402               FOR_PROVIDES(p, pp, rec)
 403                 MAPSET(&solv->recommendsmap, p);
 404             }
 405         }
 406       if (s->suggests)
 407         {
 408           sugp = s->repo->idarraydata + s->suggests;
 409           while ((sug = *sugp++) != 0)
 410             {
 411 #ifdef ENABLE_COMPLEX_DEPS
 412               if (pool_is_complex_dep(pool, sug))
 413                 {
 414                   check_complex_dep(solv, sug, &solv->suggestsmap, &solv->suggestscplxq);
 415                   continue;
 416                 }
 417 #endif
 418               FOR_PROVIDES(p, pp, sug)
 419                 MAPSET(&solv->suggestsmap, p);
 420             }
 421         }
 422     }
 423 }
 424
 425 /* bring suggested/enhanced packages to front
 426  * installed packages count as suggested */
 427 static void
 428 prefer_suggested(Solver *solv, Queue *plist)
 429 {
 430   Pool *pool = solv->pool;
 431   int i, count;
 432
 433   /* update our recommendsmap/suggestsmap */
 434   if (solv->recommends_index < solv->decisionq.count)
 435     policy_update_recommendsmap(solv);
 436
 437   for (i = 0, count = plist->count; i < count; i++)
 438     {
 439       Id p = plist->elements[i];
 440       Solvable *s = pool->solvables + p;
 441       if ((pool->installed && s->repo == pool->installed) ||
 442           MAPTST(&solv->suggestsmap, p) ||
 443           solver_is_enhancing(solv, s))
 444         continue;       /* good package */
 445       /* bring to back */
 446      if (i < plist->count - 1)
 447         {
 448           memmove(plist->elements + i, plist->elements + i + 1, (plist->count - 1 - i) * sizeof(Id));
 449           plist->elements[plist->count - 1] = p;
 450         }
 451       i--;
 452       count--;
 453     }
 454 }
 455
 456 /*
 457  * prune to recommended/suggested packages.
 458  * does not prune installed packages (they are also somewhat recommended).
 459  */
 460 static void
 461 prune_to_recommended(Solver *solv, Queue *plist)
 462 {
 463   Pool *pool = solv->pool;
 464   int i, j, k, ninst;
 465   Solvable *s;
 466   Id p;
 467
 468   ninst = 0;
 469   if (pool->installed)
 470     {
 471       for (i = 0; i < plist->count; i++)
 472         {
 473           p = plist->elements[i];
 474           s = pool->solvables + p;
 475           if (pool->installed && s->repo == pool->installed)
 476             ninst++;
 477         }
 478     }
 479   if (plist->count - ninst < 2)
 480     return;
 481
 482   /* update our recommendsmap/suggestsmap */
 483   if (solv->recommends_index < solv->decisionq.count)
 484     policy_update_recommendsmap(solv);
 485
 486   /* prune to recommended/supplemented */
 487   ninst = 0;
 488   for (i = j = 0; i < plist->count; i++)
 489     {
 490       p = plist->elements[i];
 491       s = pool->solvables + p;
 492       if (pool->installed && s->repo == pool->installed)
 493         {
 494           ninst++;
 495           if (j)
 496             plist->elements[j++] = p;
 497           continue;
 498         }
 499       if (!MAPTST(&solv->recommendsmap, p))
 500         if (!solver_is_supplementing(solv, s))
 501           continue;
 502       if (!j && ninst)
 503         {
 504           for (k = 0; j < ninst; k++)
 505             {
 506               s = pool->solvables + plist->elements[k];
 507               if (pool->installed && s->repo == pool->installed)
 508                 plist->elements[j++] = plist->elements[k];
 509             }
 510         }
 511       plist->elements[j++] = p;
 512     }
 513   if (j)
 514     plist->count = j;
 515
 516 #if 0
 517   /* anything left to prune? */
 518   if (plist->count - ninst < 2)
 519     return;
 520
 521   /* prune to suggested/enhanced */
 522   ninst = 0;
 523   for (i = j = 0; i < plist->count; i++)
 524     {
 525       p = plist->elements[i];
 526       s = pool->solvables + p;
 527       if (pool->installed && s->repo == pool->installed)
 528         {
 529           ninst++;
 530           if (j)
 531             plist->elements[j++] = p;
 532           continue;
 533         }
 534       if (!MAPTST(&solv->suggestsmap, p))
 535         if (!solver_is_enhancing(solv, s))
 536           continue;
 537       if (!j && ninst)
 538         {
 539           for (k = 0; j < ninst; k++)
 540             {
 541               s = pool->solvables + plist->elements[k];
 542               if (pool->installed && s->repo == pool->installed)
 543                 plist->elements[j++] = plist->elements[k];
 544             }
 545         }
 546       plist->elements[j++] = p;
 547     }
 548   if (j)
 549     plist->count = j;
 550 #endif
 551 }
 552
 553 static void
 554 prune_to_best_arch(const Pool *pool, Queue *plist)
 555 {
 556   Id a, bestscore;
 557   Solvable *s;
 558   int i, j;
 559
 560   if (!pool->id2arch || plist->count < 2)
 561     return;
 562   bestscore = 0;
 563   for (i = 0; i < plist->count; i++)
 564     {
 565       s = pool->solvables + plist->elements[i];
 566       a = s->arch;
 567       a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
 568       if (a && a != 1 && (!bestscore || a < bestscore))
 569         bestscore = a;
 570     }
 571   if (!bestscore)
 572     return;
 573   for (i = j = 0; i < plist->count; i++)
 574     {
 575       s = pool->solvables + plist->elements[i];
 576       a = s->arch;
 577       if (a > pool->lastarch)
 578         continue;
 579       a = pool->id2arch[a];
 580       /* a == 1 -> noarch */
 581       if (a != 1 && ((a ^ bestscore) & 0xffff0000) != 0)
 582         continue;
 583       plist->elements[j++] = plist->elements[i];
 584     }
 585   if (j)
 586     plist->count = j;
 587 }
 588
 589
 590 struct trj_data {
 591   Pool *pool;
 592   Queue *plist;
 593   Id *stack;
 594   Id nstack;
 595   Id *low;
 596   Id firstidx;
 597   Id idx;
 598 };
 599
 600 /* This is Tarjan's SCC algorithm, slightly modified */
 601 static void
 602 trj_visit(struct trj_data *trj, Id node)
 603 {
 604   Id *low = trj->low;
 605   Pool *pool = trj->pool;
 606   Queue *plist = trj->plist;
 607   Id myidx, stackstart;
 608   Solvable *s;
 609   int i;
 610   Id p, pp, obs, *obsp;
 611
 612   low[node] = myidx = trj->idx++;
 613   trj->stack[(stackstart = trj->nstack++)] = node;
 614
 615   s = pool->solvables + plist->elements[node];
 616   if (s->obsoletes)
 617     {
 618       obsp = s->repo->idarraydata + s->obsoletes;
 619       while ((obs = *obsp++) != 0)
 620         {
 621           FOR_PROVIDES(p, pp, obs)
 622             {
 623               Solvable *ps = pool->solvables + p;
 624               if (ps->name == s->name)
 625                 continue;
 626               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
 627                 continue;
 628               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 629                 continue;
 630               /* hmm, expensive. should use hash if plist is big */
 631               for (i = 0; i < plist->count; i++)
 632                 {
 633                   if (node != i && plist->elements[i] == p)
 634                     {
 635                       Id l = low[i];
 636                       if (!l)
 637                         {
 638                           if (!ps->obsoletes)
 639                             {
 640                               /* don't bother */
 641                               trj->idx++;
 642                               low[i] = -1;
 643                               continue;
 644                             }
 645                           trj_visit(trj, i);
 646                           l = low[i];
 647                         }
 648                       if (l < 0)
 649                         continue;
 650                       if (l < trj->firstidx)
 651                         {
 652                           int k;
 653                           /* this means we have reached an old SCC found earlier.
 654                            * delete it as we obsolete it */
 655                           for (k = l; ; k++)
 656                             {
 657                               if (low[trj->stack[k]] == l)
 658                                 low[trj->stack[k]] = -1;
 659                               else
 660                                 break;
 661                             }
 662                         }
 663                       else if (l < low[node])
 664                         low[node] = l;
 665                     }
 666                 }
 667             }
 668         }
 669     }
 670   if (low[node] == myidx)       /* found a SCC? */
 671     {
 672       /* we're only interested in SCCs that contain the first node,
 673        * as all others are "obsoleted" */
 674       if (myidx != trj->firstidx)
 675         myidx = -1;
 676       for (i = stackstart; i < trj->nstack; i++)
 677         low[trj->stack[i]] = myidx;
 678       trj->nstack = stackstart; /* empty stack */
 679     }
 680 }
 681
 682 /*
 683  * remove entries from plist that are obsoleted by other entries
 684  * with different name.
 685  */
 686 static void
 687 prune_obsoleted(Pool *pool, Queue *plist)
 688 {
 689   Id data_buf[2 * 16], *data;
 690   struct trj_data trj;
 691   int i, j;
 692   Solvable *s;
 693
 694   if (plist->count <= 16)
 695     {
 696       memset(data_buf, 0, sizeof(data_buf));
 697       data = data_buf;
 698     }
 699   else
 700     data = solv_calloc(plist->count, 2 * sizeof(Id));
 701   trj.pool = pool;
 702   trj.plist = plist;
 703   trj.low = data;
 704   trj.idx = 1;
 705   trj.stack = data + plist->count - 1;  /* -1 so we can index with idx (which starts with 1) */
 706   for (i = 0; i < plist->count; i++)
 707     {
 708       if (trj.low[i])
 709         continue;
 710       s = pool->solvables + plist->elements[i];
 711       if (s->obsoletes)
 712         {
 713           trj.firstidx = trj.nstack = trj.idx;
 714           trj_visit(&trj, i);
 715         }
 716       else
 717         {
 718           Id myidx = trj.idx++;
 719           trj.low[i] = myidx;
 720           trj.stack[myidx] = i;
 721         }
 722     }
 723   for (i = j = 0; i < plist->count; i++)
 724     if (trj.low[i] >= 0)
 725       plist->elements[j++] = plist->elements[i];
 726   plist->count = j;
 727   if (data != data_buf)
 728     solv_free(data);
 729 }
 730
 731 /* this is prune_obsoleted special-cased for two elements */
 732 static void
 733 prune_obsoleted_2(Pool *pool, Queue *plist)
 734 {
 735   int i;
 736   Solvable *s;
 737   Id p, pp, obs, *obsp;
 738   Id other;
 739   int obmap = 0;
 740
 741   for (i = 0; i < 2; i++)
 742     {
 743       s = pool->solvables + plist->elements[i];
 744       other = plist->elements[1 - i];
 745       if (s->obsoletes)
 746         {
 747           obsp = s->repo->idarraydata + s->obsoletes;
 748           while ((obs = *obsp++) != 0)
 749             {
 750               FOR_PROVIDES(p, pp, obs)
 751                 {
 752                   Solvable *ps;
 753                   if (p != other)
 754                     continue;
 755                   ps = pool->solvables + p;
 756                   if (ps->name == s->name)
 757                     continue;
 758                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
 759                     continue;
 760                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 761                     continue;
 762                   obmap |= 1 << i;
 763                   break;
 764                 }
 765               if (p)
 766                 break;
 767             }
 768         }
 769     }
 770   if (obmap == 0 || obmap == 3)
 771     return;
 772   if (obmap == 2)
 773     plist->elements[0] = plist->elements[1];
 774   plist->count = 1;
 775 }
 776
 777 /*
 778  * bring those elements to the front of the queue that
 779  * have a installed solvable with the same name
 780  */
 781 static void
 782 move_installed_to_front(Pool *pool, Queue *plist)
 783 {
 784   int i, j;
 785   Solvable *s;
 786   Id p, pp;
 787
 788   for (i = j = 0; i < plist->count; i++)
 789     {
 790       s = pool->solvables + plist->elements[i];
 791       if (s->repo != pool->installed)
 792         {
 793           FOR_PROVIDES(p, pp, s->name)
 794             {
 795               Solvable *ps = pool->solvables + p;
 796               if (s->name == ps->name && ps->repo == pool->installed)
 797                 {
 798                   s = ps;
 799                   break;
 800                 }
 801             }
 802         }
 803       if (s->repo == pool->installed)
 804         {
 805           if (i != j)
 806             {
 807               p = plist->elements[i];
 808               if (i - j == 1)
 809                 plist->elements[i] = plist->elements[j];
 810               else
 811                 memmove(plist->elements + j + 1, plist->elements + j, (i - j) * sizeof(Id));
 812               plist->elements[j] = p;
 813             }
 814           else if (j + 2 == plist->count)
 815             break;      /* no need to check last element if all prev ones are installed */
 816           j++;
 817         }
 818     }
 819 }
 820
 821 /*
 822  * prune_to_best_version
 823  *
 824  * sort list of packages (given through plist) by name and evr
 825  * return result through plist
 826  */
 827 void
 828 prune_to_best_version(Pool *pool, Queue *plist)
 829 {
 830   int i, j, r;
 831   Solvable *s, *best;
 832
 833   if (plist->count < 2)         /* no need to prune for a single entry */
 834     return;
 835   POOL_DEBUG(SOLV_DEBUG_POLICY, "prune_to_best_version %d\n", plist->count);
 836
 837   /* sort by name first, prefer installed */
 838   solv_sort(plist->elements, plist->count, sizeof(Id), prune_to_best_version_sortcmp, pool);
 839
 840   /* now find best 'per name' */
 841   best = 0;
 842   for (i = j = 0; i < plist->count; i++)
 843     {
 844       s = pool->solvables + plist->elements[i];
 845
 846       POOL_DEBUG(SOLV_DEBUG_POLICY, "- %s[%s]\n",
 847                  pool_solvable2str(pool, s),
 848                  (pool->installed && s->repo == pool->installed) ? "installed" : "not installed");
 849
 850       if (!best)                /* if no best yet, the current is best */
 851         {
 852           best = s;
 853           continue;
 854         }
 855
 856       /* name switch: finish group, re-init */
 857       if (best->name != s->name)   /* new name */
 858         {
 859           plist->elements[j++] = best - pool->solvables; /* move old best to front */
 860           best = s;             /* take current as new best */
 861           continue;
 862         }
 863       r = best->evr != s->evr ? pool_evrcmp(pool, best->evr, s->evr, EVRCMP_COMPARE) : 0;
 864 #ifdef ENABLE_LINKED_PKGS
 865       if (r == 0 && has_package_link(pool, s))
 866         r = pool_link_evrcmp(pool, best, s);
 867 #endif
 868       if (r < 0)
 869         best = s;
 870     }
 871   plist->elements[j++] = best - pool->solvables;        /* finish last group */
 872   plist->count = j;
 873
 874   /* we reduced the list to one package per name, now look at
 875    * package obsoletes */
 876   if (plist->count > 1)
 877     {
 878       if (plist->count == 2)
 879         prune_obsoleted_2(pool, plist);
 880       else
 881         prune_obsoleted(pool, plist);
 882     }
 883   if (plist->count > 1 && pool->installed)
 884     move_installed_to_front(pool, plist);
 885 }
 886
 887
 888 static int
 889 sort_by_name_evr_sortcmp(const void *ap, const void *bp, void *dp)
 890 {
 891   Pool *pool = dp;
 892   Id a, *aa = (Id *)ap;
 893   Id b, *bb = (Id *)bp;
 894   Id r = aa[1] - bb[1];
 895   if (r)
 896     return r < 0 ? -1 : 1;
 897   if (aa[2] == bb[2])
 898     return 0;
 899   a = aa[2] < 0 ? -aa[2] : aa[2];
 900   b = bb[2] < 0 ? -bb[2] : bb[2];
 901   if (pool->disttype != DISTTYPE_DEB && a != b)
 902     {
 903       /* treat release-less versions different */
 904       const char *as = pool_id2str(pool, a);
 905       const char *bs = pool_id2str(pool, b);
 906       if (strchr(as, '-'))
 907         {
 908           if (!strchr(bs, '-'))
 909             return -2;
 910         }
 911       else
 912         {
 913           if (strchr(bs, '-'))
 914             return 2;
 915         }
 916     }
 917   r = pool_evrcmp(pool, b, a, EVRCMP_COMPARE);
 918   if (!r && (aa[2] < 0 || bb[2] < 0))
 919     {
 920       if (bb[2] >= 0)
 921         return 1;
 922       if (aa[2] >= 0)
 923         return -1;
 924     }
 925   if (r)
 926     return r < 0 ? -1 : 1;
 927   return 0;
 928 }
 929
 930 /* common end of sort_by_srcversion and sort_by_common_dep */
 931 static void
 932 sort_by_name_evr_array(Pool *pool, Queue *plist, int count, int ent)
 933 {
 934   Id lastname;
 935   int i, j, bad, havebad;
 936   Id *pp, *elements = plist->elements;
 937
 938   if (ent < 2)
 939     {
 940       queue_truncate(plist, count);
 941       return;
 942     }
 943   solv_sort(elements + count * 2, ent, sizeof(Id) * 3, sort_by_name_evr_sortcmp, pool);
 944   lastname = 0;
 945   bad = havebad = 0;
 946   for (i = 0, pp = elements + count * 2; i < ent; i++, pp += 3)
 947     {
 948       if (lastname && pp[1] == lastname)
 949         {
 950           if (pp[0] != pp[-3] && sort_by_name_evr_sortcmp(pp - 3, pp, pool) == -1)
 951             {
 952 #if 0
 953               printf("%s - %s: bad %s %s - %s\n", pool_solvid2str(pool, elements[pp[-3]]), pool_solvid2str(pool, elements[pp[0]]), pool_dep2str(pool, lastname), pool_id2str(pool, pp[-1] < 0 ? -pp[-1] : pp[-1]), pool_id2str(pool, pp[2] < 0 ? -pp[2] : pp[2]));
 954 #endif
 955               bad++;
 956               havebad = 1;
 957             }
 958         }
 959       else
 960         {
 961           bad = 0;
 962           lastname = pp[1];
 963         }
 964       elements[count + pp[0]] += bad;
 965     }
 966
 967 #if 0
 968 for (i = 0; i < count; i++)
 969   printf("%s badness %d\n", pool_solvid2str(pool, elements[i]), elements[count + i]);
 970 #endif
 971
 972   if (havebad)
 973     {
 974       /* simple stable insertion sort */
 975       if (pool->installed)
 976         for (i = 0; i < count; i++)
 977           if (pool->solvables[elements[i]].repo == pool->installed)
 978             elements[i + count] = 0;
 979       for (i = 1; i < count; i++)
 980         for (j = i, pp = elements + count + j; j > 0; j--, pp--)
 981           if (pp[-1] > pp[0])
 982             {
 983               Id *pp2 = pp - count;
 984               Id p = pp[-1];
 985               pp[-1] = pp[0];
 986               pp[0] = p;
 987               p = pp2[-1];
 988               pp2[-1] = pp2[0];
 989               pp2[0] = p;
 990             }
 991           else
 992             break;
 993     }
 994   queue_truncate(plist, count);
 995 }
 996
 997 #if 0
 998 static void
 999 sort_by_srcversion(Pool *pool, Queue *plist)
1000 {
1001   int i, count = plist->count, ent = 0;
1002   queue_insertn(plist, count, count, 0);
1003   for (i = 0; i < count; i++)
1004     {
1005       Id name, evr, p = plist->elements[i];
1006       Solvable *s = pool->solvables + p;
1007       if (solvable_lookup_void(s, SOLVABLE_SOURCENAME))
1008         name = s->name;
1009       else
1010         name = solvable_lookup_id(s, SOLVABLE_SOURCENAME);
1011       if (solvable_lookup_void(s, SOLVABLE_SOURCEEVR))
1012         evr = s->evr;
1013       else
1014         evr = solvable_lookup_id(s, SOLVABLE_SOURCEEVR);
1015       if (!name || !evr || ISRELDEP(evr))
1016         continue;
1017       queue_push(plist, i);
1018       queue_push2(plist, name, evr);
1019       ent++;
1020     }
1021   sort_by_name_evr_array(pool, plist, count, ent);
1022 }
1023 #endif
1024
1025 static void
1026 sort_by_common_dep(Pool *pool, Queue *plist)
1027 {
1028   int i, count = plist->count, ent = 0;
1029   Id id, *dp;
1030   queue_insertn(plist, count, count, 0);
1031   for (i = 0; i < count; i++)
1032     {
1033       Id p = plist->elements[i];
1034       Solvable *s = pool->solvables + p;
1035       if (!s->provides)
1036         continue;
1037       for (dp = s->repo->idarraydata + s->provides; (id = *dp++) != 0; )
1038         {
1039           Reldep *rd;
1040           if (!ISRELDEP(id))
1041             continue;
1042           rd = GETRELDEP(pool, id);
1043           if ((rd->flags == REL_EQ || rd->flags == (REL_EQ | REL_LT) || rd->flags == REL_LT) && !ISRELDEP(rd->evr))
1044             {
1045               if (rd->flags == REL_EQ)
1046                 {
1047                   /* ignore hashes */
1048                   const char *s = pool_id2str(pool, rd->evr);
1049                   if (strlen(s) >= 4)
1050                     {
1051                       while ((*s >= 'a' && *s <= 'f') || (*s >= '0' && *s <= '9'))
1052                         s++;
1053                       if (!*s)
1054                         continue;
1055                     }
1056                 }
1057               queue_push(plist, i);
1058               queue_push2(plist, rd->name, rd->flags == REL_LT ? -rd->evr : rd->evr);
1059               ent++;
1060             }
1061         }
1062     }
1063   sort_by_name_evr_array(pool, plist, count, ent);
1064 }
1065
1066 /* check if we have an update candidate */
1067 static void
1068 dislike_old_versions(Pool *pool, Queue *plist)
1069 {
1070   int i, count;
1071
1072   for (i = 0, count = plist->count; i < count; i++)
1073     {
1074       Id p = plist->elements[i];
1075       Solvable *s = pool->solvables + p;
1076       Repo *repo = s->repo;
1077       Id q, qq;
1078       int bad = 0;
1079
1080       if (!repo || repo == pool->installed)
1081         continue;
1082       FOR_PROVIDES(q, qq, s->name)
1083         {
1084           Solvable *qs = pool->solvables + q;
1085           if (q == p)
1086             continue;
1087           if (s->name != qs->name || s->arch != qs->arch)
1088             continue;
1089           if (repo->priority != qs->repo->priority)
1090             {
1091               if (repo->priority > qs->repo->priority)
1092                 continue;
1093               bad = 1;
1094               break;
1095             }
1096           if (pool_evrcmp(pool, qs->evr, s->evr, EVRCMP_COMPARE) > 0)
1097             {
1098               bad = 1;
1099               break;
1100             }
1101         }
1102       if (!bad)
1103         continue;
1104       /* bring to back */
1105       if (i < plist->count - 1)
1106         {
1107           memmove(plist->elements + i, plist->elements + i + 1, (plist->count - 1 - i) * sizeof(Id));
1108           plist->elements[plist->count - 1] = p;
1109         }
1110       i--;
1111       count--;
1112     }
1113 }
1114
1115 /*
1116  *  POLICY_MODE_CHOOSE:     default, do all pruning steps
1117  *  POLICY_MODE_RECOMMEND:  leave out prune_to_recommended
1118  *  POLICY_MODE_SUGGEST:    leave out prune_to_recommended, do prio pruning just per name
1119  */
1120 void
1121 policy_filter_unwanted(Solver *solv, Queue *plist, int mode)
1122 {
1123   Pool *pool = solv->pool;
1124   if (plist->count > 1)
1125     {
1126       if (mode != POLICY_MODE_SUGGEST)
1127         solver_prune_to_highest_prio(solv, plist);
1128       else
1129         solver_prune_to_highest_prio_per_name(solv, plist);
1130     }
1131   if (plist->count > 1)
1132     prune_to_best_arch(pool, plist);
1133   if (plist->count > 1)
1134     prune_to_best_version(pool, plist);
1135   if (plist->count > 1 && (mode == POLICY_MODE_CHOOSE || mode == POLICY_MODE_CHOOSE_NOREORDER))
1136     {
1137       prune_to_recommended(solv, plist);
1138       if (plist->count > 1 && mode != POLICY_MODE_CHOOSE_NOREORDER)
1139         {
1140           /* do some fancy reordering */
1141 #if 0
1142           sort_by_srcversion(pool, plist);
1143 #endif
1144           dislike_old_versions(pool, plist);
1145           sort_by_common_dep(pool, plist);
1146           prefer_suggested(solv, plist);
1147         }
1148     }
1149 }
1150
1151
1152 /* check if there is an illegal architecture change if
1153  * installed solvable s1 is replaced by s2 */
1154 int
1155 policy_illegal_archchange(Solver *solv, Solvable *s1, Solvable *s2)
1156 {
1157   Pool *pool = solv->pool;
1158   Id a1 = s1->arch, a2 = s2->arch;
1159
1160   /* we allow changes to/from noarch */
1161   if (a1 == a2 || a1 == pool->noarchid || a2 == pool->noarchid)
1162     return 0;
1163   if (!pool->id2arch)
1164     return 0;
1165   a1 = a1 <= pool->lastarch ? pool->id2arch[a1] : 0;
1166   a2 = a2 <= pool->lastarch ? pool->id2arch[a2] : 0;
1167   if (((a1 ^ a2) & 0xffff0000) != 0)
1168     return 1;
1169   return 0;
1170 }
1171
1172 /* check if there is an illegal vendor change if
1173  * installed solvable s1 is replaced by s2 */
1174 int
1175 policy_illegal_vendorchange(Solver *solv, Solvable *s1, Solvable *s2)
1176 {
1177   Pool *pool = solv->pool;
1178   Id v1, v2;
1179   Id vendormask1, vendormask2;
1180
1181   if (pool->custom_vendorcheck)
1182      return pool->custom_vendorcheck(pool, s1, s2);
1183
1184   /* treat a missing vendor as empty string */
1185   v1 = s1->vendor ? s1->vendor : ID_EMPTY;
1186   v2 = s2->vendor ? s2->vendor : ID_EMPTY;
1187   if (v1 == v2)
1188     return 0;
1189   vendormask1 = pool_vendor2mask(pool, v1);
1190   if (!vendormask1)
1191     return 1;   /* can't match */
1192   vendormask2 = pool_vendor2mask(pool, v2);
1193   if ((vendormask1 & vendormask2) != 0)
1194     return 0;
1195   return 1;     /* no class matches */
1196 }
1197
1198 /* check if it is illegal to replace installed
1199  * package "is" with package "s" (which must obsolete "is")
1200  */
1201 int
1202 policy_is_illegal(Solver *solv, Solvable *is, Solvable *s, int ignore)
1203 {
1204   Pool *pool = solv->pool;
1205   int ret = 0;
1206   int duppkg = solv->dupmap_all ? 1 : 0;
1207   if (!(ignore & POLICY_ILLEGAL_DOWNGRADE) && !(duppkg ? solv->dup_allowdowngrade : solv->allowdowngrade))
1208     {
1209       if (is->name == s->name && pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE) > 0)
1210         ret |= POLICY_ILLEGAL_DOWNGRADE;
1211     }
1212   if (!(ignore & POLICY_ILLEGAL_ARCHCHANGE) && !(duppkg ? solv->dup_allowarchchange : solv->allowarchchange))
1213     {
1214       if (is->arch != s->arch && policy_illegal_archchange(solv, is, s))
1215         ret |= POLICY_ILLEGAL_ARCHCHANGE;
1216     }
1217   if (!(ignore & POLICY_ILLEGAL_VENDORCHANGE) && !(duppkg ? solv->dup_allowvendorchange : solv->allowvendorchange))
1218     {
1219       if (is->vendor != s->vendor && policy_illegal_vendorchange(solv, is, s))
1220         ret |= POLICY_ILLEGAL_VENDORCHANGE;
1221     }
1222   if (!(ignore & POLICY_ILLEGAL_NAMECHANGE) && !(duppkg ? solv->dup_allownamechange : solv->allownamechange))
1223     {
1224       if (is->name != s->name)
1225         ret |= POLICY_ILLEGAL_NAMECHANGE;
1226     }
1227   return ret;
1228 }
1229
1230 /*-------------------------------------------------------------------
1231  *
1232  * create reverse obsoletes map for installed solvables
1233  *
1234  * For each installed solvable find which packages with *different* names
1235  * obsolete the solvable.
1236  * This index is used in policy_findupdatepackages() below.
1237  */
1238 void
1239 policy_create_obsolete_index(Solver *solv)
1240 {
1241   Pool *pool = solv->pool;
1242   Solvable *s;
1243   Repo *installed = solv->installed;
1244   Id p, pp, obs, *obsp, *obsoletes, *obsoletes_data;
1245   int i, n, cnt;
1246
1247   solv->obsoletes = solv_free(solv->obsoletes);
1248   solv->obsoletes_data = solv_free(solv->obsoletes_data);
1249   if (!installed || installed->start == installed->end)
1250     return;
1251   cnt = installed->end - installed->start;
1252   solv->obsoletes = obsoletes = solv_calloc(cnt, sizeof(Id));
1253   for (i = 1; i < pool->nsolvables; i++)
1254     {
1255       s = pool->solvables + i;
1256       if (!s->obsoletes)
1257         continue;
1258       if (!pool_installable(pool, s))
1259         continue;
1260       obsp = s->repo->idarraydata + s->obsoletes;
1261       while ((obs = *obsp++) != 0)
1262         {
1263           FOR_PROVIDES(p, pp, obs)
1264             {
1265               Solvable *ps = pool->solvables + p;;
1266               if (ps->repo != installed)
1267                 continue;
1268               if (ps->name == s->name)
1269                 continue;
1270               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1271                 continue;
1272               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1273                 continue;
1274               obsoletes[p - installed->start]++;
1275             }
1276         }
1277     }
1278   n = 0;
1279   for (i = 0; i < cnt; i++)
1280     if (obsoletes[i])
1281       {
1282         n += obsoletes[i] + 1;
1283         obsoletes[i] = n;
1284       }
1285   solv->obsoletes_data = obsoletes_data = solv_calloc(n + 1, sizeof(Id));
1286   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
1287   for (i = pool->nsolvables - 1; i > 0; i--)
1288     {
1289       s = pool->solvables + i;
1290       if (!s->obsoletes)
1291         continue;
1292       if (!pool_installable(pool, s))
1293         continue;
1294       obsp = s->repo->idarraydata + s->obsoletes;
1295       while ((obs = *obsp++) != 0)
1296         {
1297           FOR_PROVIDES(p, pp, obs)
1298             {
1299               Solvable *ps = pool->solvables + p;;
1300               if (ps->repo != installed)
1301                 continue;
1302               if (ps->name == s->name)
1303                 continue;
1304               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1305                 continue;
1306               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1307                 continue;
1308               if (obsoletes_data[obsoletes[p - installed->start]] != i)
1309                 obsoletes_data[--obsoletes[p - installed->start]] = i;
1310             }
1311         }
1312     }
1313 }
1314
1315
1316 /*
1317  * find update candidates
1318  *
1319  * s: installed solvable to be updated
1320  * qs: [out] queue to hold Ids of candidates
1321  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
1322  *            2 = dup mode
1323  *
1324  */
1325 void
1326 policy_findupdatepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
1327 {
1328   /* installed packages get a special upgrade allowed rule */
1329   Pool *pool = solv->pool;
1330   Id p, pp, n, p2, pp2;
1331   Id obs, *obsp;
1332   Solvable *ps;
1333   int haveprovobs = 0;
1334   int allowdowngrade = allow_all ? 1 : solv->allowdowngrade;
1335   int allownamechange = allow_all ? 1 : solv->allownamechange;
1336   int allowarchchange = allow_all ? 1 : solv->allowarchchange;
1337   int allowvendorchange = allow_all ? 1 : solv->allowvendorchange;
1338   if (allow_all == 2)
1339     {
1340       allowdowngrade = solv->dup_allowdowngrade;
1341       allownamechange = solv->dup_allownamechange;
1342       allowarchchange = solv->dup_allowarchchange;
1343       allowvendorchange = solv->dup_allowvendorchange;
1344     }
1345
1346   queue_empty(qs);
1347
1348   n = s - pool->solvables;
1349
1350   /*
1351    * look for updates for s
1352    */
1353   FOR_PROVIDES(p, pp, s->name)  /* every provider of s' name */
1354     {
1355       if (p == n)               /* skip itself */
1356         continue;
1357
1358       ps = pool->solvables + p;
1359       if (s->name == ps->name)  /* name match */
1360         {
1361           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
1362             continue;
1363           if (!allowdowngrade && pool_evrcmp(pool, s->evr, ps->evr, EVRCMP_COMPARE) > 0)
1364             continue;
1365         }
1366       else if (!allownamechange)
1367         continue;
1368       else if ((!solv->noupdateprovide || solv->needupdateprovide) && ps->obsoletes)   /* provides/obsoletes combination ? */
1369         {
1370           /* check if package ps obsoletes installed package s */
1371           /* implicitobsoleteusescolors is somewhat wrong here, but we nevertheless
1372            * use it to limit our update candidates */
1373           if ((pool->obsoleteusescolors || pool->implicitobsoleteusescolors) && !pool_colormatch(pool, s, ps))
1374             continue;
1375           obsp = ps->repo->idarraydata + ps->obsoletes;
1376           while ((obs = *obsp++) != 0)  /* for all obsoletes */
1377             {
1378               FOR_PROVIDES(p2, pp2, obs)   /* and all matching providers of the obsoletes */
1379                 {
1380                   Solvable *ps2 = pool->solvables + p2;
1381                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps2, obs))
1382                     continue;
1383                   if (p2 == n)          /* match ! */
1384                     break;
1385                 }
1386               if (p2)                   /* match! */
1387                 break;
1388             }
1389           if (!obs)                     /* continue if no match */
1390             continue;
1391           /* here we have 'p' with a matching provides/obsoletes combination
1392            * thus flagging p as a valid update candidate for s
1393            */
1394           haveprovobs = 1;
1395         }
1396       else
1397         continue;
1398       if (!allowarchchange && s->arch != ps->arch && policy_illegal_archchange(solv, s, ps))
1399         continue;
1400       if (!allowvendorchange && s->vendor != ps->vendor && policy_illegal_vendorchange(solv, s, ps))
1401         continue;
1402       queue_push(qs, p);
1403     }
1404   if (!allownamechange)
1405     return;
1406   /* if we have found some valid candidates and noupdateprovide is not set, we're
1407      done. otherwise we fallback to all obsoletes */
1408   if (solv->needupdateprovide || (!solv->noupdateprovide && haveprovobs))
1409     return;
1410   if (solv->obsoletes && solv->obsoletes[n - solv->installed->start])
1411     {
1412       Id *opp;
1413       for (opp = solv->obsoletes_data + solv->obsoletes[n - solv->installed->start]; (p = *opp++) != 0;)
1414         {
1415           ps = pool->solvables + p;
1416           if (!allowarchchange && s->arch != ps->arch && policy_illegal_archchange(solv, s, ps))
1417             continue;
1418           if (!allowvendorchange && s->vendor != ps->vendor && policy_illegal_vendorchange(solv, s, ps))
1419             continue;
1420           /* implicitobsoleteusescolors is somewhat wrong here, but we nevertheless
1421            * use it to limit our update candidates */
1422           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
1423             continue;
1424           queue_push(qs, p);
1425         }
1426     }
1427 }
1428
1429 const char *
1430 policy_illegal2str(Solver *solv, int illegal, Solvable *s, Solvable *rs)
1431 {
1432   Pool *pool = solv->pool;
1433   const char *str;
1434   if (illegal == POLICY_ILLEGAL_DOWNGRADE)
1435     {
1436       str = pool_tmpjoin(pool, "downgrade of ", pool_solvable2str(pool, s), 0);
1437       return pool_tmpappend(pool, str, " to ", pool_solvable2str(pool, rs));
1438     }
1439   if (illegal == POLICY_ILLEGAL_NAMECHANGE)
1440     {
1441       str = pool_tmpjoin(pool, "name change of ", pool_solvable2str(pool, s), 0);
1442       return pool_tmpappend(pool, str, " to ", pool_solvable2str(pool, rs));
1443     }
1444   if (illegal == POLICY_ILLEGAL_ARCHCHANGE)
1445     {
1446       str = pool_tmpjoin(pool, "architecture change of ", pool_solvable2str(pool, s), 0);
1447       return pool_tmpappend(pool, str, " to ", pool_solvable2str(pool, rs));
1448     }
1449   if (illegal == POLICY_ILLEGAL_VENDORCHANGE)
1450     {
1451       str = pool_tmpjoin(pool, "vendor change from '", pool_id2str(pool, s->vendor), "' (");
1452       if (rs->vendor)
1453         {
1454           str = pool_tmpappend(pool, str, pool_solvable2str(pool, s), ") to '");
1455           str = pool_tmpappend(pool, str, pool_id2str(pool, rs->vendor), "' (");
1456         }
1457       else
1458         str = pool_tmpappend(pool, str, pool_solvable2str(pool, s), ") to no vendor (");
1459       return pool_tmpappend(pool, str, pool_solvable2str(pool, rs), ")");
1460     }
1461   return "unknown illegal change";
1462 }
1463