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