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