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