src/policy.c

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