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       unsigned int aa, ab;
  60       aa = pool_arch2score(pool, sa->arch);
  61       ab = pool_arch2score(pool, sb->arch);
  62       if (aa != ab && aa > 1 && ab > 1)
  63         return aa < ab ? -1 : 1;        /* 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->dupinvolvedmap_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->dupinvolvedmap_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           name = pool->solvables[plist->elements[i]].name;
 206           if (pq.count > 2)
 207             solver_prune_to_highest_prio(solv, &pq);
 208           for (k = 0; k < pq.count; k++)
 209             plist->elements[j++] = pq.elements[k];
 210           queue_empty(&pq);
 211         }
 212       queue_push(&pq, plist->elements[i]);
 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   Id p;
 236   int i, qcnt;
 237
 238 #if 0
 239   printf("check_complex_dep %s\n", pool_dep2str(pool, dep));
 240 #endif
 241   queue_init(&q);
 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 static int
 457 sort_by_favor_cmp(const void *ap, const void *bp, void *dp)
 458 {
 459   const Id *a = ap, *b = bp, *d = dp;
 460   return d[b[0]] - d[a[0]];
 461 }
 462
 463 /* bring favored packages to front and disfavored packages to back */
 464 void
 465 policy_prefer_favored(Solver *solv, Queue *plist)
 466 {
 467   if (solv->favormap && plist->count > 1)
 468     solv_sort(plist->elements, plist->count, sizeof(Id), sort_by_favor_cmp, solv->favormap);
 469 }
 470
 471 /*
 472  * prune to recommended/suggested packages.
 473  * does not prune installed packages (they are also somewhat recommended).
 474  */
 475 static void
 476 prune_to_recommended(Solver *solv, Queue *plist)
 477 {
 478   Pool *pool = solv->pool;
 479   int i, j, k, ninst;
 480   Solvable *s;
 481   Id p;
 482
 483   ninst = 0;
 484   if (pool->installed)
 485     {
 486       for (i = 0; i < plist->count; i++)
 487         {
 488           p = plist->elements[i];
 489           s = pool->solvables + p;
 490           if (pool->installed && s->repo == pool->installed)
 491             ninst++;
 492         }
 493     }
 494   if (plist->count - ninst < 2)
 495     return;
 496
 497   /* update our recommendsmap/suggestsmap */
 498   if (solv->recommends_index < solv->decisionq.count)
 499     policy_update_recommendsmap(solv);
 500
 501   /* prune to recommended/supplemented */
 502   ninst = 0;
 503   for (i = j = 0; i < plist->count; i++)
 504     {
 505       p = plist->elements[i];
 506       s = pool->solvables + p;
 507       if (pool->installed && s->repo == pool->installed)
 508         {
 509           ninst++;
 510           if (j)
 511             plist->elements[j++] = p;
 512           continue;
 513         }
 514       if (!MAPTST(&solv->recommendsmap, p))
 515         if (!solver_is_supplementing(solv, s))
 516           continue;
 517       if (!j && ninst)
 518         {
 519           for (k = 0; j < ninst; k++)
 520             {
 521               s = pool->solvables + plist->elements[k];
 522               if (pool->installed && s->repo == pool->installed)
 523                 plist->elements[j++] = plist->elements[k];
 524             }
 525         }
 526       plist->elements[j++] = p;
 527     }
 528   if (j)
 529     plist->count = j;
 530
 531 #if 0
 532   /* anything left to prune? */
 533   if (plist->count - ninst < 2)
 534     return;
 535
 536   /* prune to suggested/enhanced */
 537   ninst = 0;
 538   for (i = j = 0; i < plist->count; i++)
 539     {
 540       p = plist->elements[i];
 541       s = pool->solvables + p;
 542       if (pool->installed && s->repo == pool->installed)
 543         {
 544           ninst++;
 545           if (j)
 546             plist->elements[j++] = p;
 547           continue;
 548         }
 549       if (!MAPTST(&solv->suggestsmap, p))
 550         if (!solver_is_enhancing(solv, s))
 551           continue;
 552       if (!j && ninst)
 553         {
 554           for (k = 0; j < ninst; k++)
 555             {
 556               s = pool->solvables + plist->elements[k];
 557               if (pool->installed && s->repo == pool->installed)
 558                 plist->elements[j++] = plist->elements[k];
 559             }
 560         }
 561       plist->elements[j++] = p;
 562     }
 563   if (j)
 564     plist->count = j;
 565 #endif
 566 }
 567
 568 static void
 569 prune_to_best_arch(const Pool *pool, Queue *plist)
 570 {
 571   Id a, bestscore;
 572   Solvable *s;
 573   int i, j;
 574
 575   if (!pool->id2arch || plist->count < 2)
 576     return;
 577   bestscore = 0;
 578   for (i = 0; i < plist->count; i++)
 579     {
 580       s = pool->solvables + plist->elements[i];
 581       a = pool_arch2score(pool, s->arch);
 582       if (a && a != 1 && (!bestscore || a < bestscore))
 583         bestscore = a;
 584     }
 585   if (!bestscore)
 586     return;
 587   for (i = j = 0; i < plist->count; i++)
 588     {
 589       s = pool->solvables + plist->elements[i];
 590       a = pool_arch2score(pool, s->arch);
 591       if (!a)
 592         continue;
 593       /* a == 1 -> noarch */
 594       if (a != 1 && ((a ^ bestscore) & 0xffff0000) != 0)
 595         continue;
 596       plist->elements[j++] = plist->elements[i];
 597     }
 598   if (j)
 599     plist->count = j;
 600 }
 601
 602
 603 struct trj_data {
 604   Pool *pool;
 605   Queue *plist;
 606   Id *stack;
 607   Id nstack;
 608   Id *low;
 609   Id firstidx;
 610   Id idx;
 611 };
 612
 613 /* This is Tarjan's SCC algorithm, slightly modified */
 614 static void
 615 trj_visit(struct trj_data *trj, Id node)
 616 {
 617   Id *low = trj->low;
 618   Pool *pool = trj->pool;
 619   Queue *plist = trj->plist;
 620   Id myidx, stackstart;
 621   Solvable *s;
 622   int i;
 623   Id p, pp, obs, *obsp;
 624
 625   low[node] = myidx = trj->idx++;
 626   trj->stack[(stackstart = trj->nstack++)] = node;
 627
 628   s = pool->solvables + plist->elements[node];
 629   if (s->obsoletes)
 630     {
 631       obsp = s->repo->idarraydata + s->obsoletes;
 632       while ((obs = *obsp++) != 0)
 633         {
 634           FOR_PROVIDES(p, pp, obs)
 635             {
 636               Solvable *ps = pool->solvables + p;
 637               if (ps->name == s->name)
 638                 continue;
 639               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
 640                 continue;
 641               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 642                 continue;
 643               /* hmm, expensive. should use hash if plist is big */
 644               for (i = 0; i < plist->count; i++)
 645                 {
 646                   if (node != i && plist->elements[i] == p)
 647                     {
 648                       Id l = low[i];
 649                       if (!l)
 650                         {
 651                           if (!ps->obsoletes)
 652                             {
 653                               /* don't bother */
 654                               trj->idx++;
 655                               low[i] = -1;
 656                               continue;
 657                             }
 658                           trj_visit(trj, i);
 659                           l = low[i];
 660                         }
 661                       if (l < 0)
 662                         continue;
 663                       if (l < trj->firstidx)
 664                         {
 665                           int k;
 666                           /* this means we have reached an old SCC found earlier.
 667                            * delete it as we obsolete it */
 668                           for (k = l; ; k++)
 669                             {
 670                               if (low[trj->stack[k]] == l)
 671                                 low[trj->stack[k]] = -1;
 672                               else
 673                                 break;
 674                             }
 675                         }
 676                       else if (l < low[node])
 677                         low[node] = l;
 678                     }
 679                 }
 680             }
 681         }
 682     }
 683   if (low[node] == myidx)       /* found a SCC? */
 684     {
 685       /* we're only interested in SCCs that contain the first node,
 686        * as all others are "obsoleted" */
 687       if (myidx != trj->firstidx)
 688         myidx = -1;
 689       for (i = stackstart; i < trj->nstack; i++)
 690         low[trj->stack[i]] = myidx;
 691       trj->nstack = stackstart; /* empty stack */
 692     }
 693 }
 694
 695 /*
 696  * remove entries from plist that are obsoleted by other entries
 697  * with different name.
 698  */
 699 static void
 700 prune_obsoleted(Pool *pool, Queue *plist)
 701 {
 702   Id data_buf[2 * 16], *data;
 703   struct trj_data trj;
 704   int i, j;
 705   Solvable *s;
 706
 707   if (plist->count <= 16)
 708     {
 709       memset(data_buf, 0, sizeof(data_buf));
 710       data = data_buf;
 711     }
 712   else
 713     data = solv_calloc(plist->count, 2 * sizeof(Id));
 714   trj.pool = pool;
 715   trj.plist = plist;
 716   trj.low = data;
 717   trj.idx = 1;
 718   trj.stack = data + plist->count - 1;  /* -1 so we can index with idx (which starts with 1) */
 719   for (i = 0; i < plist->count; i++)
 720     {
 721       if (trj.low[i])
 722         continue;
 723       s = pool->solvables + plist->elements[i];
 724       if (s->obsoletes)
 725         {
 726           trj.firstidx = trj.nstack = trj.idx;
 727           trj_visit(&trj, i);
 728         }
 729       else
 730         {
 731           Id myidx = trj.idx++;
 732           trj.low[i] = myidx;
 733           trj.stack[myidx] = i;
 734         }
 735     }
 736   for (i = j = 0; i < plist->count; i++)
 737     if (trj.low[i] >= 0)
 738       plist->elements[j++] = plist->elements[i];
 739   plist->count = j;
 740   if (data != data_buf)
 741     solv_free(data);
 742 }
 743
 744 /* this is prune_obsoleted special-cased for two elements */
 745 static void
 746 prune_obsoleted_2(Pool *pool, Queue *plist)
 747 {
 748   int i;
 749   Solvable *s;
 750   Id p, pp, obs, *obsp;
 751   Id other;
 752   int obmap = 0;
 753
 754   for (i = 0; i < 2; i++)
 755     {
 756       s = pool->solvables + plist->elements[i];
 757       other = plist->elements[1 - i];
 758       if (s->obsoletes)
 759         {
 760           obsp = s->repo->idarraydata + s->obsoletes;
 761           while ((obs = *obsp++) != 0)
 762             {
 763               FOR_PROVIDES(p, pp, obs)
 764                 {
 765                   Solvable *ps;
 766                   if (p != other)
 767                     continue;
 768                   ps = pool->solvables + p;
 769                   if (ps->name == s->name)
 770                     continue;
 771                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
 772                     continue;
 773                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 774                     continue;
 775                   obmap |= 1 << i;
 776                   break;
 777                 }
 778               if (p)
 779                 break;
 780             }
 781         }
 782     }
 783   if (obmap == 0 || obmap == 3)
 784     return;
 785   if (obmap == 2)
 786     plist->elements[0] = plist->elements[1];
 787   plist->count = 1;
 788 }
 789
 790 /*
 791  * bring those elements to the front of the queue that
 792  * have a installed solvable with the same name
 793  */
 794 static void
 795 move_installed_to_front(Pool *pool, Queue *plist)
 796 {
 797   int i, j;
 798   Solvable *s;
 799   Id p, pp;
 800
 801   if (!pool->installed)
 802     return;
 803   for (i = j = 0; i < plist->count; i++)
 804     {
 805       s = pool->solvables + plist->elements[i];
 806       if (s->repo != pool->installed)
 807         {
 808           FOR_PROVIDES(p, pp, s->name)
 809             {
 810               Solvable *ps = pool->solvables + p;
 811               if (s->name == ps->name && ps->repo == pool->installed)
 812                 {
 813                   s = ps;
 814                   break;
 815                 }
 816             }
 817         }
 818       if (s->repo == pool->installed)
 819         {
 820           if (i != j)
 821             {
 822               p = plist->elements[i];
 823               if (i - j == 1)
 824                 plist->elements[i] = plist->elements[j];
 825               else
 826                 memmove(plist->elements + j + 1, plist->elements + j, (i - j) * sizeof(Id));
 827               plist->elements[j] = p;
 828             }
 829           else if (j + 2 == plist->count)
 830             break;      /* no need to check last element if all prev ones are installed */
 831           j++;
 832         }
 833     }
 834 }
 835
 836 #ifdef ENABLE_CONDA
 837 static int
 838 pool_featurecountcmp(Pool *pool, Solvable *s1, Solvable *s2)
 839 {
 840   unsigned int cnt1, cnt2;
 841   cnt1 = solvable_lookup_count(s1, SOLVABLE_TRACK_FEATURES);
 842   cnt2 = solvable_lookup_count(s2, SOLVABLE_TRACK_FEATURES);
 843   return cnt1 == cnt2 ? 0 : cnt1 > cnt2 ? -1 : 1;
 844 }
 845
 846 static int
 847 pool_buildversioncmp(Pool *pool, Solvable *s1, Solvable *s2)
 848 {
 849   const char *bv1, *bv2;
 850   bv1 = solvable_lookup_str(s1, SOLVABLE_BUILDVERSION);
 851   bv2 = solvable_lookup_str(s2, SOLVABLE_BUILDVERSION);
 852   if (!bv1 && !bv2)
 853     return 0;
 854   return pool_evrcmp_str(pool, bv1 ? bv1 : "" , bv2 ? bv2 : "", EVRCMP_COMPARE);
 855 }
 856
 857 static int
 858 pool_buildflavorcmp(Pool *pool, Solvable *s1, Solvable *s2)
 859 {
 860   const char *f1 = solvable_lookup_str(s1, SOLVABLE_BUILDFLAVOR);
 861   const char *f2 = solvable_lookup_str(s2, SOLVABLE_BUILDFLAVOR);
 862   if (!f1 && !f2)
 863     return 0;
 864   return pool_evrcmp_str(pool, f1 ? f1 : "" , f2 ? f2 : "", EVRCMP_COMPARE);
 865 }
 866 #endif
 867
 868 /*
 869  * prune_to_best_version
 870  *
 871  * sort list of packages (given through plist) by name and evr
 872  * return result through plist
 873  */
 874 void
 875 prune_to_best_version(Pool *pool, Queue *plist)
 876 {
 877   int i, j, r;
 878   Solvable *s, *best;
 879
 880   if (plist->count < 2)         /* no need to prune for a single entry */
 881     return;
 882   POOL_DEBUG(SOLV_DEBUG_POLICY, "prune_to_best_version %d\n", plist->count);
 883
 884   /* sort by name first, prefer installed */
 885   solv_sort(plist->elements, plist->count, sizeof(Id), prune_to_best_version_sortcmp, pool);
 886
 887   /* now find best 'per name' */
 888   best = 0;
 889   for (i = j = 0; i < plist->count; i++)
 890     {
 891       s = pool->solvables + plist->elements[i];
 892
 893       POOL_DEBUG(SOLV_DEBUG_POLICY, "- %s [%d]%s\n",
 894                  pool_solvable2str(pool, s), plist->elements[i],
 895                  (pool->installed && s->repo == pool->installed) ? "I" : "");
 896
 897       if (!best)                /* if no best yet, the current is best */
 898         {
 899           best = s;
 900           continue;
 901         }
 902
 903       /* name switch: finish group, re-init */
 904       if (best->name != s->name)   /* new name */
 905         {
 906           plist->elements[j++] = best - pool->solvables; /* move old best to front */
 907           best = s;             /* take current as new best */
 908           continue;
 909         }
 910
 911       r = 0;
 912 #ifdef ENABLE_CONDA
 913       if (pool->disttype == DISTTYPE_CONDA)
 914         r = pool_featurecountcmp(pool, best, s);
 915 #endif
 916       if (r == 0)
 917         r = best->evr != s->evr ? pool_evrcmp(pool, best->evr, s->evr, EVRCMP_COMPARE) : 0;
 918 #ifdef ENABLE_LINKED_PKGS
 919       if (r == 0 && has_package_link(pool, s))
 920         r = pool_link_evrcmp(pool, best, s);
 921 #endif
 922 #ifdef ENABLE_CONDA
 923       if (pool->disttype == DISTTYPE_CONDA)
 924         {
 925           if (r == 0)
 926             r = (best->repo ? best->repo->subpriority : 0) - (s->repo ? s->repo->subpriority : 0);
 927           if (r == 0)
 928             r = pool_buildversioncmp(pool, best, s);
 929           if (r == 0)
 930             r = pool_buildflavorcmp(pool, best, s);
 931         }
 932 #endif
 933       if (r < 0)
 934         best = s;
 935     }
 936   plist->elements[j++] = best - pool->solvables;        /* finish last group */
 937   plist->count = j;
 938
 939   /* we reduced the list to one package per name, now look at
 940    * package obsoletes */
 941   if (plist->count > 1)
 942     {
 943       if (plist->count == 2)
 944         prune_obsoleted_2(pool, plist);
 945       else
 946         prune_obsoleted(pool, plist);
 947     }
 948 }
 949
 950
 951 static int
 952 sort_by_name_evr_sortcmp(const void *ap, const void *bp, void *dp)
 953 {
 954   Pool *pool = dp;
 955   Id a, *aa = (Id *)ap;
 956   Id b, *bb = (Id *)bp;
 957   Id r = aa[1] - bb[1];
 958   if (r)
 959     return r < 0 ? -1 : 1;
 960   if (aa[2] == bb[2])
 961     return 0;
 962   a = aa[2] < 0 ? -aa[2] : aa[2];
 963   b = bb[2] < 0 ? -bb[2] : bb[2];
 964   r = pool_evrcmp(pool, b, a, pool->disttype != DISTTYPE_DEB ? EVRCMP_MATCH_RELEASE : EVRCMP_COMPARE);
 965   if (!r && (aa[2] < 0 || bb[2] < 0))
 966     {
 967       if (bb[2] >= 0)
 968         return 1;
 969       if (aa[2] >= 0)
 970         return -1;
 971     }
 972   return r;
 973 }
 974
 975 /* common end of sort_by_srcversion and sort_by_common_dep */
 976 static void
 977 sort_by_name_evr_array(Pool *pool, Queue *plist, int count, int ent)
 978 {
 979   Id lastname;
 980   int i, j, bad, havebad;
 981   Id *pp, *elements = plist->elements;
 982
 983   if (ent < 2)
 984     {
 985       queue_truncate(plist, count);
 986       return;
 987     }
 988   solv_sort(elements + count * 2, ent, sizeof(Id) * 3, sort_by_name_evr_sortcmp, pool);
 989   lastname = 0;
 990   bad = havebad = 0;
 991   for (i = 0, pp = elements + count * 2; i < ent; i++, pp += 3)
 992     {
 993       if (lastname && pp[1] == lastname)
 994         {
 995           if (pp[0] != pp[-3] && sort_by_name_evr_sortcmp(pp - 3, pp, pool) == -1)
 996             {
 997 #if 0
 998               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]));
 999 #endif
1000               bad++;
1001               havebad = 1;
1002             }
1003         }
1004       else
1005         {
1006           bad = 0;
1007           lastname = pp[1];
1008         }
1009       elements[count + pp[0]] += bad;
1010     }
1011
1012 #if 0
1013 for (i = 0; i < count; i++)
1014   printf("%s badness %d\n", pool_solvid2str(pool, elements[i]), elements[count + i]);
1015 #endif
1016
1017   if (havebad)
1018     {
1019       /* simple stable insertion sort */
1020       if (pool->installed)
1021         for (i = 0; i < count; i++)
1022           if (pool->solvables[elements[i]].repo == pool->installed)
1023             elements[i + count] = 0;
1024       for (i = 1; i < count; i++)
1025         for (j = i, pp = elements + count + j; j > 0; j--, pp--)
1026           if (pp[-1] > pp[0])
1027             {
1028               Id *pp2 = pp - count;
1029               Id p = pp[-1];
1030               pp[-1] = pp[0];
1031               pp[0] = p;
1032               p = pp2[-1];
1033               pp2[-1] = pp2[0];
1034               pp2[0] = p;
1035             }
1036           else
1037             break;
1038     }
1039   queue_truncate(plist, count);
1040 }
1041
1042 #if 0
1043 static void
1044 sort_by_srcversion(Pool *pool, Queue *plist)
1045 {
1046   int i, count = plist->count, ent = 0;
1047   queue_insertn(plist, count, count, 0);
1048   for (i = 0; i < count; i++)
1049     {
1050       Id name, evr, p = plist->elements[i];
1051       Solvable *s = pool->solvables + p;
1052       if (solvable_lookup_void(s, SOLVABLE_SOURCENAME))
1053         name = s->name;
1054       else
1055         name = solvable_lookup_id(s, SOLVABLE_SOURCENAME);
1056       if (solvable_lookup_void(s, SOLVABLE_SOURCEEVR))
1057         evr = s->evr;
1058       else
1059         evr = solvable_lookup_id(s, SOLVABLE_SOURCEEVR);
1060       if (!name || !evr || ISRELDEP(evr))
1061         continue;
1062       queue_push(plist, i);
1063       queue_push2(plist, name, evr);
1064       ent++;
1065     }
1066   sort_by_name_evr_array(pool, plist, count, ent);
1067 }
1068 #endif
1069
1070 static void
1071 sort_by_common_dep(Pool *pool, Queue *plist)
1072 {
1073   int i, count = plist->count, ent = 0;
1074   Id id, *dp;
1075   queue_insertn(plist, count, count, 0);
1076   for (i = 0; i < count; i++)
1077     {
1078       Id p = plist->elements[i];
1079       Solvable *s = pool->solvables + p;
1080       if (!s->provides)
1081         continue;
1082       for (dp = s->repo->idarraydata + s->provides; (id = *dp++) != 0; )
1083         {
1084           Reldep *rd;
1085           if (!ISRELDEP(id))
1086             continue;
1087           rd = GETRELDEP(pool, id);
1088           if ((rd->flags == REL_EQ || rd->flags == (REL_EQ | REL_LT) || rd->flags == REL_LT) && !ISRELDEP(rd->evr))
1089             {
1090               if (rd->flags == REL_EQ)
1091                 {
1092                   /* ignore hashes */
1093                   const char *s = pool_id2str(pool, rd->evr);
1094                   if (strlen(s) >= 4)
1095                     {
1096                       while ((*s >= 'a' && *s <= 'f') || (*s >= '0' && *s <= '9'))
1097                         s++;
1098                       if (!*s)
1099                         continue;
1100                     }
1101                 }
1102               queue_push(plist, i);
1103               queue_push2(plist, rd->name, rd->flags == REL_LT ? -rd->evr : rd->evr);
1104               ent++;
1105             }
1106         }
1107     }
1108   sort_by_name_evr_array(pool, plist, count, ent);
1109 }
1110
1111 /* check if we have an update candidate */
1112 static void
1113 dislike_old_versions(Pool *pool, Queue *plist)
1114 {
1115   int i, count;
1116
1117   for (i = 0, count = plist->count; i < count; i++)
1118     {
1119       Id p = plist->elements[i];
1120       Solvable *s = pool->solvables + p;
1121       Repo *repo = s->repo;
1122       Id q, qq;
1123       int bad = 0;
1124
1125       if (!repo || repo == pool->installed)
1126         continue;
1127       FOR_PROVIDES(q, qq, s->name)
1128         {
1129           Solvable *qs = pool->solvables + q;
1130           if (q == p)
1131             continue;
1132           if (s->name != qs->name || s->arch != qs->arch)
1133             continue;
1134           if (repo->priority != qs->repo->priority)
1135             {
1136               if (repo->priority > qs->repo->priority)
1137                 continue;
1138               bad = 1;
1139               break;
1140             }
1141           if (pool_evrcmp(pool, qs->evr, s->evr, EVRCMP_COMPARE) > 0)
1142             {
1143               bad = 1;
1144               break;
1145             }
1146         }
1147       if (!bad)
1148         continue;
1149       /* bring to back */
1150       if (i < plist->count - 1)
1151         {
1152           memmove(plist->elements + i, plist->elements + i + 1, (plist->count - 1 - i) * sizeof(Id));
1153           plist->elements[plist->count - 1] = p;
1154         }
1155       i--;
1156       count--;
1157     }
1158 }
1159
1160
1161 /* special lang package handling for urpm */
1162 /* see https://bugs.mageia.org/show_bug.cgi?id=18315 */
1163
1164 static int
1165 urpm_reorder_cmp(const void *ap, const void *bp, void *dp)
1166 {
1167   return ((Id *)bp)[1] - ((Id *)ap)[1];
1168 }
1169
1170 static void
1171 urpm_reorder(Solver *solv, Queue *plist)
1172 {
1173   Pool *pool = solv->pool;
1174   int i, count = plist->count;
1175   /* add locale score to packages */
1176   queue_insertn(plist, count, count, 0);
1177   for (i = count - 1; i >= 0; i--)
1178     {
1179       Solvable *s = pool->solvables + plist->elements[i];
1180       int score = 1;
1181       const char *sn = pool_id2str(pool, s->name);
1182
1183       if (!strncmp(sn, "kernel-", 7))
1184         {
1185           const char *devel = strstr(sn, "-devel-");
1186           if (devel && strlen(sn) < 256)
1187             {
1188               char kn[256];
1189               Id p, pp, knid;
1190               memcpy(kn, sn, devel - sn);
1191               strcpy(kn + (devel - sn), devel + 6);
1192               knid = pool_str2id(pool, kn, 0);
1193               if (knid)
1194                 {
1195                   FOR_PROVIDES(p, pp, knid)
1196                     {
1197                       if (solv->decisionmap[p] > 0)
1198                         {
1199                           score = 4;
1200                           break;
1201                         }
1202                       else if (pool->installed && pool->solvables[p].repo == pool->installed)
1203                         score = 3;
1204                     }
1205                 }
1206             }
1207         }
1208       else if ((sn = strstr(sn, "-kernel-")) != 0)
1209         {
1210           sn += 8;
1211           if (strlen(sn) < 256 - 8 && *sn >= '0' && *sn <= '9' && sn[1] == '.')
1212             {
1213               const char *flavor = strchr(sn, '-');
1214               if (flavor)
1215                 {
1216                   const char *release = strchr(flavor + 1, '-');
1217                   if (release)
1218                     {
1219                       char kn[256];
1220                       Id p, pp, knid;
1221                       memcpy(kn, "kernel", 7);
1222                       memcpy(kn + 6, flavor, release - flavor + 1);
1223                       memcpy(kn + 6 + (release - flavor) + 1, sn, flavor - sn);
1224                       strcpy(kn + 6 + (release + 1 - sn), release);
1225                       knid = pool_str2id(pool, kn, 0);
1226                       if (knid)
1227                         {
1228                           FOR_PROVIDES(p, pp, knid)
1229                             {
1230                               if (solv->decisionmap[p] > 0)
1231                                 {
1232                                   score = 4;
1233                                   break;
1234                                 }
1235                               if (pool->installed && pool->solvables[p].repo == pool->installed)
1236                                 score = 3;
1237                             }
1238                         }
1239                     }
1240                 }
1241             }
1242         }
1243       if (score == 1 && s->requires)
1244         {
1245           Id id, *idp, p, pp;
1246           const char *deps;
1247           for (idp = s->repo->idarraydata + s->requires; (id = *idp) != 0; idp++)
1248             {
1249               while (ISRELDEP(id))
1250                 {
1251                   Reldep *rd = GETRELDEP(pool, id);
1252                   id = rd->name;
1253                 }
1254               deps = strstr(pool_id2str(pool, id), "locales-");
1255               if (!deps)
1256                 continue;
1257               if (!strncmp(deps + 8, "en", 2))
1258                 score = 2;
1259               else
1260                 {
1261                   score = 0;
1262                   FOR_PROVIDES(p, pp, id)
1263                     {
1264                       if (solv->decisionmap[p] > 0)
1265                         {
1266                           score = 4;
1267                           break;
1268                         }
1269                       if (pool->installed && pool->solvables[p].repo == pool->installed)
1270                         score = 3;
1271                     }
1272                   break;
1273                 }
1274             }
1275         }
1276       plist->elements[i * 2] = plist->elements[i];
1277       plist->elements[i * 2 + 1] = score;
1278     }
1279   solv_sort(plist->elements, count, sizeof(Id) * 2, urpm_reorder_cmp, pool);
1280   for (i = 0; i < count; i++)
1281     plist->elements[i] = plist->elements[2 * i];
1282   queue_truncate(plist, count);
1283 }
1284
1285 /* support multiple favor groups by calling policy_filter_unwanted on
1286  * each of them and combining the result */
1287 static void
1288 policy_filter_unwanted_favored(Solver *solv, Queue *plist, int mode)
1289 {
1290   int i, j, f;
1291   Queue qin, qprune;
1292   queue_init_clone(&qin, plist);
1293   queue_empty(plist);
1294   /* sort by favor group */
1295   solv_sort(qin.elements, qin.count, sizeof(Id), sort_by_favor_cmp, solv->favormap);
1296   /* go over groups */
1297   queue_init(&qprune);
1298   for (i = 0; i < qin.count; i = j)
1299     {
1300       /* find end of group */
1301       f = solv->favormap[qin.elements[i]];
1302       for (j = i + 1; j < qin.count; j++)
1303         if (solv->favormap[qin.elements[j]] != f)
1304           break;
1305       /* prune this group */
1306       queue_empty(&qprune);
1307       queue_insertn(&qprune, 0, j, qin.elements);
1308       policy_filter_unwanted(solv, &qprune, mode | POLICY_MODE_FAVOR_REC);
1309       for (i = 0; i < qprune.count; i++)
1310         if (solv->favormap[qprune.elements[i]] == f)
1311           queue_push(plist, qprune.elements[i]);
1312     }
1313   queue_free(&qprune);
1314   queue_free(&qin);
1315 }
1316
1317 /*
1318  *  POLICY_MODE_CHOOSE:     default, do all pruning steps
1319  *  POLICY_MODE_RECOMMEND:  leave out prune_to_recommended
1320  *  POLICY_MODE_SUGGEST:    leave out prune_to_recommended, do prio pruning just per name
1321  */
1322 void
1323 policy_filter_unwanted(Solver *solv, Queue *plist, int mode)
1324 {
1325   Pool *pool = solv->pool;
1326   if (mode == POLICY_MODE_SUPPLEMENT)
1327     {
1328       /* reorder only */
1329       dislike_old_versions(pool, plist);
1330       sort_by_common_dep(pool, plist);
1331       if (solv->urpmreorder)
1332         urpm_reorder(solv, plist);
1333       prefer_suggested(solv, plist);
1334       policy_prefer_favored(solv, plist);
1335       return;
1336     }
1337   if (mode & POLICY_MODE_FAVOR_REC)
1338     mode ^= POLICY_MODE_FAVOR_REC;
1339   else if (solv->favormap && plist->count > 1)
1340     {
1341       /* check if we have multiple favor groups */
1342       int i, f = solv->favormap[plist->elements[0]];
1343       for (i = 1; i < plist->count; i++)
1344         if (solv->favormap[plist->elements[i]] != f)
1345           break;
1346       if (i < plist->count)
1347         {
1348           policy_filter_unwanted_favored(solv, plist, mode);
1349           return;
1350         }
1351     }
1352   if (plist->count > 1)
1353     {
1354       if (mode != POLICY_MODE_SUGGEST)
1355         solver_prune_to_highest_prio(solv, plist);
1356       else
1357         solver_prune_to_highest_prio_per_name(solv, plist);
1358     }
1359   if (plist->count > 1)
1360     prune_to_best_arch(pool, plist);
1361   if (plist->count > 1)
1362     prune_to_best_version(pool, plist);
1363   if (plist->count > 1 && (mode == POLICY_MODE_CHOOSE || mode == POLICY_MODE_CHOOSE_NOREORDER))
1364     {
1365       prune_to_recommended(solv, plist);
1366       if (plist->count > 1 && mode != POLICY_MODE_CHOOSE_NOREORDER)
1367         {
1368           /* do some fancy reordering */
1369 #if 0
1370           sort_by_srcversion(pool, plist);
1371 #endif
1372           dislike_old_versions(pool, plist);
1373           sort_by_common_dep(pool, plist);
1374           move_installed_to_front(pool, plist);
1375           if (solv->urpmreorder)
1376             urpm_reorder(solv, plist);
1377           prefer_suggested(solv, plist);
1378           policy_prefer_favored(solv, plist);
1379         }
1380     }
1381 }
1382
1383 void
1384 pool_best_solvables(Pool *pool, Queue *plist, int flags)
1385 {
1386   if (plist->count > 1)
1387     prune_to_highest_prio(pool, plist);
1388   if (plist->count > 1)
1389     prune_to_best_arch(pool, plist);
1390   if (plist->count > 1)
1391     prune_to_best_version(pool, plist);
1392   if (plist->count > 1)
1393     {
1394       dislike_old_versions(pool, plist);
1395       sort_by_common_dep(pool, plist);
1396       move_installed_to_front(pool, plist);
1397     }
1398 }
1399
1400
1401 /* check if there is an illegal architecture change if
1402  * installed solvable s1 is replaced by s2 */
1403 int
1404 policy_illegal_archchange(Solver *solv, Solvable *s1, Solvable *s2)
1405 {
1406   Pool *pool = solv->pool;
1407   Id a1 = s1->arch, a2 = s2->arch;
1408
1409   /* we allow changes to/from noarch */
1410   if (a1 == a2 || a1 == pool->noarchid || a2 == pool->noarchid)
1411     return 0;
1412   if (!pool->id2arch)
1413     return 0;
1414   a1 = pool_arch2score(pool, a1);
1415   a2 = pool_arch2score(pool, a2);
1416   if (((a1 ^ a2) & 0xffff0000) != 0)
1417     return 1;
1418   return 0;
1419 }
1420
1421 /* check if there is an illegal vendor change if
1422  * installed solvable s1 is replaced by s2 */
1423 int
1424 policy_illegal_vendorchange(Solver *solv, Solvable *s1, Solvable *s2)
1425 {
1426   Pool *pool = solv->pool;
1427   Id v1, v2;
1428   Id vendormask1, vendormask2;
1429
1430   if (pool->custom_vendorcheck)
1431      return pool->custom_vendorcheck(pool, s1, s2);
1432
1433   /* treat a missing vendor as empty string */
1434   v1 = s1->vendor ? s1->vendor : ID_EMPTY;
1435   v2 = s2->vendor ? s2->vendor : ID_EMPTY;
1436   if (v1 == v2)
1437     return 0;
1438   vendormask1 = pool_vendor2mask(pool, v1);
1439   if (!vendormask1)
1440     return 1;   /* can't match */
1441   vendormask2 = pool_vendor2mask(pool, v2);
1442   if ((vendormask1 & vendormask2) != 0)
1443     return 0;
1444   return 1;     /* no class matches */
1445 }
1446
1447 /* check if it is illegal to replace installed
1448  * package "is" with package "s" (which must obsolete "is")
1449  */
1450 int
1451 policy_is_illegal(Solver *solv, Solvable *is, Solvable *s, int ignore)
1452 {
1453   Pool *pool = solv->pool;
1454   int ret = 0;
1455   int duppkg = solv->dupinvolvedmap_all || (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, is - pool->solvables));
1456   if (!(ignore & POLICY_ILLEGAL_DOWNGRADE) && !(duppkg ? solv->dup_allowdowngrade : solv->allowdowngrade))
1457     {
1458       if (is->name == s->name && pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE) > 0)
1459         ret |= POLICY_ILLEGAL_DOWNGRADE;
1460     }
1461   if (!(ignore & POLICY_ILLEGAL_ARCHCHANGE) && !(duppkg ? solv->dup_allowarchchange : solv->allowarchchange))
1462     {
1463       if (is->arch != s->arch && policy_illegal_archchange(solv, is, s))
1464         ret |= POLICY_ILLEGAL_ARCHCHANGE;
1465     }
1466   if (!(ignore & POLICY_ILLEGAL_VENDORCHANGE) && !(duppkg ? solv->dup_allowvendorchange : solv->allowvendorchange))
1467     {
1468       if (is->vendor != s->vendor && policy_illegal_vendorchange(solv, is, s))
1469         ret |= POLICY_ILLEGAL_VENDORCHANGE;
1470     }
1471   if (!(ignore & POLICY_ILLEGAL_NAMECHANGE) && !(duppkg ? solv->dup_allownamechange : solv->allownamechange))
1472     {
1473       if (is->name != s->name)
1474         ret |= POLICY_ILLEGAL_NAMECHANGE;
1475     }
1476   return ret;
1477 }
1478
1479 /*-------------------------------------------------------------------
1480  *
1481  * create reverse obsoletes map for installed solvables
1482  *
1483  * For each installed solvable find which packages with *different* names
1484  * obsolete the solvable.
1485  * This index is used in policy_findupdatepackages() below.
1486  */
1487 void
1488 policy_create_obsolete_index(Solver *solv)
1489 {
1490   Pool *pool = solv->pool;
1491   Solvable *s;
1492   Repo *installed = solv->installed;
1493   Id p, pp, obs, *obsp, *obsoletes, *obsoletes_data;
1494   int i, n, cnt;
1495
1496   solv->obsoletes = solv_free(solv->obsoletes);
1497   solv->obsoletes_data = solv_free(solv->obsoletes_data);
1498   if (!installed || installed->start == installed->end)
1499     return;
1500   cnt = installed->end - installed->start;
1501   solv->obsoletes = obsoletes = solv_calloc(cnt, sizeof(Id));
1502   for (i = 1; i < pool->nsolvables; i++)
1503     {
1504       s = pool->solvables + i;
1505       if (!s->obsoletes)
1506         continue;
1507       if (!pool_installable(pool, s))
1508         continue;
1509       obsp = s->repo->idarraydata + s->obsoletes;
1510       while ((obs = *obsp++) != 0)
1511         {
1512           FOR_PROVIDES(p, pp, obs)
1513             {
1514               Solvable *ps = pool->solvables + p;
1515               if (ps->repo != installed)
1516                 continue;
1517               if (ps->name == s->name)
1518                 continue;
1519               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1520                 continue;
1521               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1522                 continue;
1523               obsoletes[p - installed->start]++;
1524             }
1525         }
1526     }
1527   n = 0;
1528   for (i = 0; i < cnt; i++)
1529     if (obsoletes[i])
1530       {
1531         n += obsoletes[i] + 1;
1532         obsoletes[i] = n;
1533       }
1534   solv->obsoletes_data = obsoletes_data = solv_calloc(n + 1, sizeof(Id));
1535   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
1536   for (i = pool->nsolvables - 1; i > 0; i--)
1537     {
1538       s = pool->solvables + i;
1539       if (!s->obsoletes)
1540         continue;
1541       if (!pool_installable(pool, s))
1542         continue;
1543       obsp = s->repo->idarraydata + s->obsoletes;
1544       while ((obs = *obsp++) != 0)
1545         {
1546           FOR_PROVIDES(p, pp, obs)
1547             {
1548               Solvable *ps = pool->solvables + p;
1549               if (ps->repo != installed)
1550                 continue;
1551               if (ps->name == s->name)
1552                 continue;
1553               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1554                 continue;
1555               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1556                 continue;
1557               if (obsoletes_data[obsoletes[p - installed->start]] != i)
1558                 obsoletes_data[--obsoletes[p - installed->start]] = i;
1559             }
1560         }
1561     }
1562 }
1563
1564
1565 /* return true if solvable s obsoletes solvable with id pi */
1566 static inline int
1567 is_obsoleting(Pool *pool, Solvable *s, Id pi)
1568 {
1569   Id p, pp, obs, *obsp;
1570   Solvable *si = pool->solvables + pi;
1571   if (pool->obsoleteusescolors && !pool_colormatch(pool, si, s))
1572     return 0;
1573   obsp = s->repo->idarraydata + s->obsoletes;
1574   while ((obs = *obsp++) != 0)  /* for all obsoletes */
1575     {
1576       FOR_PROVIDES(p, pp, obs)   /* and all matching providers of the obsoletes */
1577         {
1578           if (p != pi)
1579             continue;
1580           if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
1581             continue;
1582           return 1;
1583         }
1584     }
1585   return 0;
1586 }
1587
1588 /*
1589  * find update candidates
1590  *
1591  * s: installed solvable to be updated
1592  * qs: [out] queue to hold Ids of candidates
1593  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
1594  *            2 = dup mode
1595  *
1596  */
1597 void
1598 policy_findupdatepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
1599 {
1600   /* installed packages get a special upgrade allowed rule */
1601   Pool *pool = solv->pool;
1602   Id p, pp, n;
1603   Solvable *ps;
1604   int haveprovobs = 0;
1605   int allowdowngrade = allow_all ? 1 : solv->allowdowngrade;
1606   int allownamechange = allow_all ? 1 : solv->allownamechange;
1607   int allowarchchange = allow_all ? 1 : solv->allowarchchange;
1608   int allowvendorchange = allow_all ? 1 : solv->allowvendorchange;
1609   if (allow_all == 2)
1610     {
1611       allowdowngrade = solv->dup_allowdowngrade;
1612       allownamechange = solv->dup_allownamechange;
1613       allowarchchange = solv->dup_allowarchchange;
1614       allowvendorchange = solv->dup_allowvendorchange;
1615     }
1616
1617   queue_empty(qs);
1618
1619   n = s - pool->solvables;
1620
1621   /*
1622    * look for updates for s
1623    */
1624   FOR_PROVIDES(p, pp, s->name)  /* every provider of s' name */
1625     {
1626       if (p == n)               /* skip itself */
1627         continue;
1628
1629       ps = pool->solvables + p;
1630       if (pool->considered && pool->whatprovideswithdisabled && ps->repo != pool->installed && pool_disabled_solvable(pool, ps))
1631         continue;
1632       if (s->name == ps->name)  /* name match */
1633         {
1634           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
1635             continue;
1636           if (!allowdowngrade && pool_evrcmp(pool, s->evr, ps->evr, EVRCMP_COMPARE) > 0)
1637             continue;
1638         }
1639       else if (!allownamechange)
1640         continue;
1641       else if ((!solv->noupdateprovide || solv->needupdateprovide) && ps->obsoletes)   /* provides/obsoletes combination ? */
1642         {
1643           /* check if package ps that provides s->name obsoletes installed package s */
1644           /* implicitobsoleteusescolors is somewhat wrong here, but we nevertheless
1645            * use it to limit our update candidates */
1646           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
1647             continue;
1648           if (!is_obsoleting(pool, ps, n))
1649             continue;
1650           haveprovobs = 1;              /* have matching provides/obsoletes combination */
1651         }
1652       else
1653         continue;
1654       if (!allowarchchange && s->arch != ps->arch && policy_illegal_archchange(solv, s, ps))
1655         continue;
1656       if (!allowvendorchange && s->vendor != ps->vendor && policy_illegal_vendorchange(solv, s, ps))
1657         continue;
1658       queue_push(qs, p);
1659     }
1660   if (!allownamechange)
1661     return;
1662   /* if we have found some valid candidates and noupdateprovide is not set, we're
1663      done. otherwise we fallback to all obsoletes */
1664   if (solv->needupdateprovide || (!solv->noupdateprovide && haveprovobs))
1665     return;
1666   if (solv->obsoletes && solv->obsoletes[n - solv->installed->start])
1667     {
1668       Id *opp;
1669       for (opp = solv->obsoletes_data + solv->obsoletes[n - solv->installed->start]; (p = *opp++) != 0;)
1670         {
1671           ps = pool->solvables + p;
1672           /* implicitobsoleteusescolors is somewhat wrong here, but we nevertheless
1673            * use it to limit our update candidates */
1674           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
1675             continue;
1676           if (!allowarchchange && s->arch != ps->arch && policy_illegal_archchange(solv, s, ps))
1677             continue;
1678           if (!allowvendorchange && s->vendor != ps->vendor && policy_illegal_vendorchange(solv, s, ps))
1679             continue;
1680           queue_push(qs, p);
1681         }
1682     }
1683 }
1684
1685 const char *
1686 policy_illegal2str(Solver *solv, int illegal, Solvable *s, Solvable *rs)
1687 {
1688   Pool *pool = solv->pool;
1689   const char *str;
1690   if (illegal == POLICY_ILLEGAL_DOWNGRADE)
1691     {
1692       str = pool_tmpjoin(pool, "downgrade of ", pool_solvable2str(pool, s), 0);
1693       return pool_tmpappend(pool, str, " to ", pool_solvable2str(pool, rs));
1694     }
1695   if (illegal == POLICY_ILLEGAL_NAMECHANGE)
1696     {
1697       str = pool_tmpjoin(pool, "name change of ", pool_solvable2str(pool, s), 0);
1698       return pool_tmpappend(pool, str, " to ", pool_solvable2str(pool, rs));
1699     }
1700   if (illegal == POLICY_ILLEGAL_ARCHCHANGE)
1701     {
1702       str = pool_tmpjoin(pool, "architecture change of ", pool_solvable2str(pool, s), 0);
1703       return pool_tmpappend(pool, str, " to ", pool_solvable2str(pool, rs));
1704     }
1705   if (illegal == POLICY_ILLEGAL_VENDORCHANGE)
1706     {
1707       str = pool_tmpjoin(pool, "vendor change from '", pool_id2str(pool, s->vendor), "' (");
1708       if (rs->vendor)
1709         {
1710           str = pool_tmpappend(pool, str, pool_solvable2str(pool, s), ") to '");
1711           str = pool_tmpappend(pool, str, pool_id2str(pool, rs->vendor), "' (");
1712         }
1713       else
1714         str = pool_tmpappend(pool, str, pool_solvable2str(pool, s), ") to no vendor (");
1715       return pool_tmpappend(pool, str, pool_solvable2str(pool, rs), ")");
1716     }
1717   return "unknown illegal change";
1718 }
1719