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