src/solver_util.c

   1 /*
   2  * Copyright (c) 2017, SUSE Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * solver_util.c
  10  *
  11  * Dependency solver helper functions
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <unistd.h>
  17 #include <string.h>
  18
  19 #include "solver.h"
  20 #include "solver_private.h"
  21 #include "bitmap.h"
  22 #include "pool.h"
  23 #include "poolarch.h"
  24 #include "util.h"
  25
  26
  27 /*-------------------------------------------------------------------
  28  * check if a installed package p is being updated
  29  */
  30 static int
  31 solver_is_updating(Solver *solv, Id p)
  32 {
  33   /* check if the update rule is true */
  34   Pool *pool = solv->pool;
  35   Rule *r;
  36   Id l, pp;
  37   if (solv->decisionmap[p] >= 0)
  38     return 0;   /* old package stayed */
  39   r = solv->rules + solv->updaterules + (p - solv->installed->start);
  40   FOR_RULELITERALS(l, pp, r)
  41     if (l > 0 && l != p && solv->decisionmap[l] > 0)
  42       return 1;
  43   return 0;
  44 }
  45
  46 /*-------------------------------------------------------------------
  47  * handle split provides
  48  *
  49  * a splitprovides dep looks like
  50  *     namespace:splitprovides(pkg REL_WITH path)
  51  * and is only true if pkg is installed and contains the specified path.
  52  * we also make sure that pkg is selected for an update, otherwise the
  53  * update would always be forced onto the user.
  54  * Map m is the map used when called from dep_possible.
  55  */
  56 int
  57 solver_splitprovides(Solver *solv, Id dep, Map *m)
  58 {
  59   Pool *pool = solv->pool;
  60   Id p, pp;
  61   Reldep *rd;
  62   Solvable *s;
  63
  64   if (!solv->dosplitprovides || !solv->installed)
  65     return 0;
  66   if (!ISRELDEP(dep))
  67     return 0;
  68   rd = GETRELDEP(pool, dep);
  69   if (rd->flags != REL_WITH)
  70     return 0;
  71   /*
  72    * things are a bit tricky here if pool->addedprovides == 1, because most split-provides are in
  73    * a non-standard location. If we simply call pool_whatprovides, we'll drag in the complete
  74    * file list. Instead we rely on pool_addfileprovides ignoring the addfileprovidesfiltered flag
  75    * for installed packages and check the lazywhatprovidesq (ignoring the REL_WITH part, but
  76    * we filter the package name further down anyway).
  77    */
  78   if (pool->addedfileprovides == 1 && !ISRELDEP(rd->evr) && !pool->whatprovides[rd->evr])
  79     pp = pool_searchlazywhatprovidesq(pool, rd->evr);
  80   else
  81     pp = pool_whatprovides(pool, dep);
  82   while ((p = pool->whatprovidesdata[pp++]) != 0)
  83     {
  84       /* here we have packages that provide the correct name and contain the path,
  85        * now do extra filtering */
  86       s = pool->solvables + p;
  87       if (s->repo != solv->installed || s->name != rd->name)
  88         continue;
  89       /* check if the package is updated. if m is set, we're called from dep_possible */
  90       if (m || solver_is_updating(solv, p))
  91         return 1;
  92     }
  93   return 0;
  94 }
  95
  96 int
  97 solver_dep_possible_slow(Solver *solv, Id dep, Map *m)
  98 {
  99   Pool *pool = solv->pool;
 100   Id p, pp;
 101
 102   if (ISRELDEP(dep))
 103     {
 104       Reldep *rd = GETRELDEP(pool, dep);
 105       if (rd->flags >= 8)
 106          {
 107           if (rd->flags == REL_COND || rd->flags == REL_UNLESS)
 108             return 1;
 109           if (rd->flags == REL_AND)
 110             {
 111               if (!solver_dep_possible_slow(solv, rd->name, m))
 112                 return 0;
 113               return solver_dep_possible_slow(solv, rd->evr, m);
 114             }
 115           if (rd->flags == REL_OR)
 116             {
 117               if (solver_dep_possible_slow(solv, rd->name, m))
 118                 return 1;
 119               return solver_dep_possible_slow(solv, rd->evr, m);
 120             }
 121           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
 122             return solver_splitprovides(solv, rd->evr, m);
 123         }
 124     }
 125   FOR_PROVIDES(p, pp, dep)
 126     {
 127       if (MAPTST(m, p))
 128         return 1;
 129     }
 130   return 0;
 131 }
 132
 133 int
 134 solver_dep_fulfilled_cplx(Solver *solv, Reldep *rd)
 135 {
 136   Pool *pool = solv->pool;
 137   if (rd->flags == REL_COND)
 138     {
 139       if (ISRELDEP(rd->evr))
 140         {
 141           Reldep *rd2 = GETRELDEP(pool, rd->evr);
 142           if (rd2->flags == REL_ELSE)
 143             {
 144               if (solver_dep_fulfilled(solv, rd2->name))
 145                 return solver_dep_fulfilled(solv, rd->name);
 146               return solver_dep_fulfilled(solv, rd2->evr);
 147             }
 148         }
 149       if (solver_dep_fulfilled(solv, rd->name))
 150         return 1;
 151       return !solver_dep_fulfilled(solv, rd->evr);
 152     }
 153   if (rd->flags == REL_UNLESS)
 154     {
 155       if (ISRELDEP(rd->evr))
 156         {
 157           Reldep *rd2 = GETRELDEP(pool, rd->evr);
 158           if (rd2->flags == REL_ELSE)
 159             {
 160               if (!solver_dep_fulfilled(solv, rd2->name))
 161                 return solver_dep_fulfilled(solv, rd->name);
 162               return solver_dep_fulfilled(solv, rd2->evr);
 163             }
 164         }
 165       if (!solver_dep_fulfilled(solv, rd->name))
 166         return 0;
 167       return !solver_dep_fulfilled(solv, rd->evr);
 168     }
 169   if (rd->flags == REL_AND)
 170     {
 171       if (!solver_dep_fulfilled(solv, rd->name))
 172         return 0;
 173       return solver_dep_fulfilled(solv, rd->evr);
 174     }
 175   if (rd->flags == REL_OR)
 176     {
 177       if (solver_dep_fulfilled(solv, rd->name))
 178         return 1;
 179       return solver_dep_fulfilled(solv, rd->evr);
 180     }
 181   return 0;
 182 }
 183
 184 static int
 185 solver_dep_fulfilled_complex_func(Solver *solv, Reldep *rd, int (*dep_fullfilled)(Solver *, Id))
 186 {
 187   Pool *pool = solv->pool;
 188   int r1, r2;
 189   if (rd->flags == REL_COND)
 190     {
 191       if (ISRELDEP(rd->evr))
 192         {
 193           Reldep *rd2 = GETRELDEP(pool, rd->evr);
 194           if (rd2->flags == REL_ELSE)
 195             {
 196               r1 = dep_fullfilled(solv, rd2->name);
 197               if (r1)
 198                 {
 199                   r2 = dep_fullfilled(solv, rd->name);
 200                   return r2 && r1 == 2 ? 2 : r2;
 201                 }
 202               return dep_fullfilled(solv, rd2->evr);
 203             }
 204         }
 205       r1 = dep_fullfilled(solv, rd->name);
 206       r2 = !dep_fullfilled(solv, rd->evr);
 207       if (!r1 && !r2)
 208         return 0;
 209       return r1 == 2 ? 2 : 1;
 210     }
 211   if (rd->flags == REL_UNLESS)
 212     {
 213       if (ISRELDEP(rd->evr))
 214         {
 215           Reldep *rd2 = GETRELDEP(pool, rd->evr);
 216           if (rd2->flags == REL_ELSE)
 217             {
 218               r1 = dep_fullfilled(solv, rd2->name);
 219               if (r1)
 220                 {
 221                   r2 = dep_fullfilled(solv, rd2->evr);
 222                   return r2 && r1 == 2 ? 2 : r2;
 223                 }
 224               return dep_fullfilled(solv, rd->name);
 225             }
 226         }
 227       /* A AND NOT(B) */
 228       r1 = dep_fullfilled(solv, rd->name);
 229       r2 = !dep_fullfilled(solv, rd->evr);
 230       if (!r1 || !r2)
 231         return 0;
 232       return r1 == 2 ? 2 : 1;
 233     }
 234   if (rd->flags == REL_AND)
 235     {
 236       r1 = dep_fullfilled(solv, rd->name);
 237       if (!r1)
 238         return 0;
 239       r2 = dep_fullfilled(solv, rd->evr);
 240       if (!r2)
 241         return 0;
 242       return r1 == 2 || r2 == 2 ? 2 : 1;
 243     }
 244   if (rd->flags == REL_OR)
 245     {
 246       r1 = dep_fullfilled(solv, rd->name);
 247       r2 = dep_fullfilled(solv, rd->evr);
 248       if (!r1 && !r2)
 249         return 0;
 250       return r1 == 2 || r2 == 2 ? 2 : 1;
 251     }
 252   return 0;
 253 }
 254
 255 /* mirrors solver_dep_fulfilled, but returns 2 if a new package
 256  * was involved */
 257 static int
 258 solver_dep_fulfilled_alreadyinstalled(Solver *solv, Id dep)
 259 {
 260   Pool *pool = solv->pool;
 261   Id p, pp;
 262   int r;
 263
 264   if (ISRELDEP(dep))
 265     {
 266       Reldep *rd = GETRELDEP(pool, dep);
 267       if (rd->flags == REL_COND || rd->flags == REL_UNLESS || rd->flags == REL_AND || rd->flags == REL_OR)
 268         return solver_dep_fulfilled_complex_func(solv, rd, solver_dep_fulfilled_alreadyinstalled);
 269       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
 270         return solver_splitprovides(solv, rd->evr, 0) ? 2 : 0;
 271       if (rd->flags == REL_NAMESPACE && solv->installsuppdepq)
 272         {
 273           Queue *q = solv->installsuppdepq;
 274           int i;
 275           for (i = 0; i < q->count; i++)
 276             if (q->elements[i] == dep || q->elements[i] == rd->name)
 277               return 2;
 278         }
 279     }
 280   r = 0;
 281   FOR_PROVIDES(p, pp, dep)
 282     if (solv->decisionmap[p] > 0)
 283       {
 284         Solvable *s = pool->solvables + p;
 285         if (s->repo && s->repo != solv->installed)
 286           return 2;
 287         r = 1;
 288       }
 289   return r;
 290 }
 291
 292 static int
 293 solver_dep_fulfilled_namespace(Solver *solv, Id dep)
 294 {
 295   Pool *pool = solv->pool;
 296   Id p, pp;
 297   int r = 1;
 298
 299   if (ISRELDEP(dep))
 300     {
 301       Reldep *rd = GETRELDEP(pool, dep);
 302       if (rd->flags == REL_COND || rd->flags == REL_UNLESS || rd->flags == REL_AND || rd->flags == REL_OR)
 303         return solver_dep_fulfilled_complex_func(solv, rd, solver_dep_fulfilled_namespace);
 304       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
 305         return solver_splitprovides(solv, rd->evr, 0) ? 2 : 0;
 306       if (rd->flags == REL_NAMESPACE)
 307         r = 2;
 308     }
 309   FOR_PROVIDES(p, pp, dep)
 310     if (solv->decisionmap[p] > 0)
 311       return r;
 312   return 0;
 313 }
 314
 315 int
 316 solver_is_supplementing_alreadyinstalled(Solver *solv, Solvable *s)
 317 {
 318   Id sup, *supp;
 319   supp = s->repo->idarraydata + s->supplements;
 320   while ((sup = *supp++) != 0)
 321     {
 322       if (!solv->addalreadyrecommended && solver_dep_fulfilled_alreadyinstalled(solv, sup) != 2)
 323         continue;
 324       if (solv->only_namespace_recommended && solver_dep_fulfilled_namespace(solv, sup) != 2)
 325         continue;
 326       return 1;
 327     }
 328   return 0;
 329 }
 330
 331 int
 332 solver_is_namespace_dep_slow(Solver *solv, Reldep *rd)
 333 {
 334   Pool *pool = solv->pool;
 335   for (;;)
 336     {
 337       if (rd->flags == REL_NAMESPACE)
 338         return 1;
 339       if (ISRELDEP(rd->name) && solver_is_namespace_dep_slow(solv, GETRELDEP(pool, rd->name)))
 340         return 1;
 341       if (!ISRELDEP(rd->evr))
 342         return 0;
 343       rd = GETRELDEP(pool, rd->evr);
 344     }
 345 }
 346
 347 /*
 348  * add all installed packages that package p obsoletes to Queue q.
 349  * Package p is not installed. Also, we know that if
 350  * solv->keepexplicitobsoletes is not set, p is not in the multiversion map.
 351  * Entries may get added multiple times.
 352  */
 353 static void
 354 solver_add_obsoleted(Solver *solv, Id p, Queue *q)
 355 {
 356   Pool *pool = solv->pool;
 357   Repo *installed = solv->installed;
 358   Id p2, pp2;
 359   Solvable *s = pool->solvables + p;
 360   Id obs, *obsp;
 361   Id lastp2 = 0;
 362
 363   if (!solv->keepexplicitobsoletes || !(solv->multiversion.size && MAPTST(&solv->multiversion, p)))
 364     {
 365       FOR_PROVIDES(p2, pp2, s->name)
 366         {
 367           Solvable *ps = pool->solvables + p2;
 368           if (ps->repo != installed)
 369             continue;
 370           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
 371             continue;
 372           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
 373             continue;
 374           queue_push(q, p2);
 375           lastp2 = p2;
 376         }
 377     }
 378   if (!s->obsoletes)
 379     return;
 380   obsp = s->repo->idarraydata + s->obsoletes;
 381   while ((obs = *obsp++) != 0)
 382     FOR_PROVIDES(p2, pp2, obs)
 383       {
 384         Solvable *ps = pool->solvables + p2;
 385         if (ps->repo != installed)
 386           continue;
 387         if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
 388           continue;
 389         if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 390           continue;
 391         if (p2 == lastp2)
 392           continue;
 393         queue_push(q, p2);
 394         lastp2 = p2;
 395       }
 396 }
 397
 398 /*
 399  * Call solver_add_obsoleted and intersect the result with the
 400  * elements in Queue q starting at qstart.
 401  * Assumes that it's the first call if qstart == q->count.
 402  * May use auxillary map m for the intersection process, all
 403  * elements of q starting at qstart must have their bit cleared.
 404  * (This is also true after the function returns.)
 405  * (See solver_add_obsoleted for limitations of the package p)
 406  */
 407 void
 408 solver_intersect_obsoleted(Solver *solv, Id p, Queue *q, int qstart, Map *m)
 409 {
 410   int i, j;
 411   int qcount = q->count;
 412
 413   solver_add_obsoleted(solv, p, q);
 414   if (qcount == qstart)
 415     return;     /* first call */
 416   if (qcount == q->count)
 417     j = qstart;
 418   else if (qcount == qstart + 1)
 419     {
 420       /* easy if there's just one element */
 421       j = qstart;
 422       for (i = qcount; i < q->count; i++)
 423         if (q->elements[i] == q->elements[qstart])
 424           {
 425             j++;        /* keep the element */
 426             break;
 427           }
 428     }
 429   else if (!m || (!m->size && q->count - qstart <= 8))
 430     {
 431       /* faster than a map most of the time */
 432       int k;
 433       for (i = j = qstart; i < qcount; i++)
 434         {
 435           Id ip = q->elements[i];
 436           for (k = qcount; k < q->count; k++)
 437             if (q->elements[k] == ip)
 438               {
 439                 q->elements[j++] = ip;
 440                 break;
 441               }
 442         }
 443     }
 444   else
 445     {
 446       /* for the really pathologic cases we use the map */
 447       Repo *installed = solv->installed;
 448       if (!m->size)
 449         map_init(m, installed->end - installed->start);
 450       for (i = qcount; i < q->count; i++)
 451         MAPSET(m, q->elements[i] - installed->start);
 452       for (i = j = qstart; i < qcount; i++)
 453         if (MAPTST(m, q->elements[i] - installed->start))
 454           {
 455             MAPCLR(m, q->elements[i] - installed->start);
 456             q->elements[j++] = q->elements[i];
 457           }
 458     }
 459   queue_truncate(q, j);
 460 }
 461